JPH03182122A

JPH03182122A - 有限体の除算回路

Info

Publication number: JPH03182122A
Application number: JP1321118A
Authority: JP
Inventors: Masayuki Hattori; 雅之服部
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1989-12-11
Filing date: 1989-12-11
Publication date: 1991-08-08

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、例えばエラー訂正符号の符号器、復号器に適
用される有限体の除算回路に関する。

〔発明の概要〕

本発明は、例えばエラー訂正符号の符号器、復号器に適
用される有限体の除算回路において、有限体Ｇ　Ｆ　（
２ｍ）上のｍビットでベクトル表現された被除数と除数
との内の除数の逆元をベクトル表現で求め、その被除数
と除数の逆元とを一方を行列表現に変換して乗算するこ
とにより、回路規模が小型化できると共に演算速度が高
速化できる様にしたものである。

〔従来の技術〕

デジタルビデオ信号、デジタルオーディオ信号などを記
録再生する際に、エラー訂正符号として隣接符号、リー
ドンロモン符号などが実用化されている。これらのエラ
ー訂正符号の符号器ではパリティデータ（冗長データ）
の発生がなされ、復号器ではパリティデータを含む受信
信号からシンドロームが発生され、このシンドロームを
用いてエラー訂正がなされる。これらのパリティ発生回
路、シンドローム発生回路及びエラー訂正回路では位数
ｐＨの有限体（ガロア体）ＧＦ（ｐ’″）の演算回路が
用いられる。有限体ＧＦ（ｐ’″〉とは、次数ｍの既約
多項式Ｐ　（Ｘ）から導かれたｐ′″個の元を有する体
であり、エラー訂正符号においては、ｐ＝２の場合のみ
が重要である。本発明はｐ＝２の有限体即ち有限体ＧＦ
（２ｍ）に適用される。

有限体ＧＦ（２ｍ）上の演算回路には、加算回路（ＧＦ
（２ｍ〉上では減算回路も同じ構造である）、乗算回路
、除算回路があるが、このうちの加算回路は排他的オア
ゲートを用いて簡単に実現できる。

しかし、乗算回路及び除算回路の構成は複雑である。

除算回路の従来例としては変換テーブルとしてのＲＯＭ
を用いた回路が知られている。有限体ＧＦ（２ｍ）の既
約多項式を０と置いた場合の根をαとすると、この有限
体のＯ以外の元はαのべき乗で表現される。そして、α
１　とαｊ　との商（αｌ／α」）を計算する場合には
、α１をＲＯＭに入力して指数ｉを得ると共にα」をＲ
ＯＭに入力して指数ｊを得た後に、減算回路により（ｉ
−ｊ）を発生し、この指数（ｉ−ｊ）をＲＯＭに入力し
てα″″ｊを出力する様な処理を行っていた。一方、有
限体Ｇ　Ｆ　（２ｍ）上の乗算回路については、特開昭
６０−１４４８３４号公報において、有限体の客死の行
列表現を用いることによって回路規模を小型化すると共
に演算速度を高速化した乗算回路が提案されている。

〔発明が解決しようとする課題〕

しかしながら、有限体Ｇ　Ｆ　（２ｍ〉上の除算回路に
ついては、上述の変換テーブル用いた回路の外に有力な
手法が提案されておらず、回路規模が大きいと共に演算
速度が遅い不都合があった。

また、実際のエラー訂正回路では同時に複数の除算を実
行することが必要になると共に、それら複数の除算にお
ける夫々の除数又は被除数が同一であることがあるが、
このような場合、単に複数個の同−Ｍ４戊の除算器を並
列に配したのでは回路規模が更に大型化する不都合があ
る。

本発明は斯かる点に鑑み、有限体ＧＦ（２ｍ）上の除算
回路の回路規模を小型化し演算速度を高速化することを
目的とする。

本発明は更に、有限体ＧＦ（２ｍ〉上で複数の除算を同
時に実行する場合で且つそれら複数の除算における夫々
の除数又は被除数が同一である場合に、より回路規模を
小型化することをも目的とする。

〔課題を解決するための手段〕

請求項１記載の有限体の除算回路は例えば第１図に示す
如く、有限体Ｇ　Ｆ　（２’）上のｍビットでベクトル
表現された第１の元ｙの逆元ｙ″′をベクトル表現で生
成する晶生回路（３）と、その第１の元ｙの逆元ｙ−１
と有限体ＧＦ（２ｍ）上の夫々ｍビットでベクトル表現
された第２の元Ｘとを一方の元を行列表現に変換して乗
算する乗算回路（１）、（２）とを有し、その第２の元
Ｘをその第１の元ｙで除した商ｘ／ｙを有限体ＣＦ　（
２’）上のｍビットのベクトル表現で得る様にしたもの
である。

請求項２記載の発明は、その乗算回路（１）、（２）が
その第２の元Ｘを行列表現に変換する様になされている
ものである。

請求項３記載の発明は、例えば第５図に示す如く、有限
体ＣＦ（２ｍ〉上のｍビットでベクトル表現された一群
の元ａ、ｃ、ｅと１つの共通の元Ｘとの夫々の商ｘ／ａ
、ｘ／ｃ、ｘ／ｅ又はａ　／　ｘ　。

ｃ／ｘ、ｅ／ｘを求める除算回路において、それら一群
の元ａ、ｃ、ｅの夫々の逆元又はその共通の元Ｘの逆元
をベクトル表現で生成する複数又は１つの逆元発生回路
（３Ａ）、　（３Ｂ）、　（３Ｃ）と、その共通の元Ｘ
を直接に又はその逆元発生回路を介して行列表現Ｔ　（
Ｘ）に変換する表現変換回路（１）と、それら一群の元
ｄ、ｃ、ｅ又はこれら一群の元の夫々の逆元１／ａ、ｌ
／ｃ、１／ｅのベクトル表現とその表現変換回路（１）
より出力される行列表現Ｔ　（Ｘ）とを乗算する複数の
乗算回路（２＾）、　（２Ｂ）、　（２Ｃ）とを設けた
ものである。

〔作用〕

請求項１記載の発明によれば、有限体ＣＦ　（２ｍ）上
の２つの元ｘ、ｙの商ｘ／ｙを求める場合、先ず逆元発
生回路（３）により第１の元ｙの逆元ｙ　−１をベクト
ル表現で発生した後に、その第２の元Ｘを行列表現に変
換し、この行列表現の元Ｘとそのベクトル表現の逆元ｙ
　−１とを乗算することにより、商ｘ／ｙがベクトル表
現で求められる。尚、その逆元ｙ　−１を行列表現に変
換して、この行列表現の逆元ｙ　−１とベクトル表現の
元Ｘとを乗算することもできる。また、逆元発生回路（
３）は変換テーブルとしてのＲＯＭ等により構成され比
較的回路規模が大きくなるが、従来例の如く３個の変換
テーブルとしてのＲＯＭを使用する回路に比較すればそ
の逆元発生回路（３）の回路規模は約１／３になり、全
体としての回路規模を小型化することができる。

また、逆元発生回路（３）は１回使用されるだけである
ため、全体としての演算速度を高速化することができる
。

更に、その乗算回路（１）、（２）がその第２の元Ｘを
行列表現に変換する場合には、例えば第１図に示す如く
、その第１の元ｙの逆元ｙ−１への変換とその第２の元
Ｘの表現の行列表現Ｔ　（Ｘ）への変換が並列に実行さ
れるため、演算速度を更に高速化することができる。

また、請求項３記載の発明によれば、例えば第５図に示
す如く、有限体ＧＦ（２″″）上で被除数又は除数を共
通とする複数の除算を同時に実行する場合に、その共通
の元Ｘ　（Ｘが被除数の場合〉又はその逆元ｘ−’（ｘ
が除数の場合〉の表現をベクトル表現から行列表現Ｔ　
（Ｘ）又はＴ（ｘ−’）に変換する表現変換回路（１）
が共通に使用される。従って、同一の除算器を複数並列
に配する場合に比べて、全体としての回路規模をより小
型化することができる。

〔実施例〕

本発明においては特開昭６０−１４４８３４号公報で開
示された有限体の客死の行列表現が使用されている。そ
こで、本発明の一実施例の理解を容易とするため、有限
体ＧＦ（２ｍ）の客死の行列表現について説明する。

一例として、０又は１（＝−１）の係数ｇ＋９ｇ２．　
ｇｓを用いて次の様な原始既約多項式ＰＯＯを定義し、
ＰＯＯ＝　１＋ｇ＋Ｘ　＋ｇ２Ｘ”＋ｇ＊Ｘ’＋Ｘ＋・
・”（１）この多項式Ｐ（Ｘ）を法多項式とする位数２
４　の有限体Ｇ’Ｆ（２’）を考える。先ずＰＯＯ＝Ｏ
の根をαとすると、αは有限体Ｇ　Ｆ　（２’）の原始
元であり、このＧＦ（２’）の０以外の客死はαのべき
乗αｉ　（＋は整数）で表わすことができる。この表現
を“べき表現”という。

この場合、Ｐ■−〇且つＣＦ　（２’）上の減算は加算
と同一であるため、 α’＝　　　１　　　ｇ＋α−ｇ２α２−ｇ３α３＝　
１　＋　ｇ　＋α十ｇ２α２＋ｇ、α３　　・・・・（
２Ａ）α５＝α・α４＝α＋ｇＩα２＋ｇ２α３＋ｇ３
α４”　ｇｓ＋（１＋　ｇ３ｇ＋）α＋（ｇ＋＋ｇ３ｇ
２）α２＋　　（ｇ２＋　ｇ３ｇｚ）α３　　　　　　
　　・・・・（２Ｂ〉等が成立している。従って、α’
　（ｉ　＝４．５．６゜・・・・）は１．α、α２．α
３の線形結合で必ず表現できるため、ＧＦ（２’）上の
任意の元をａとすると、元ａ　ｉｉＯ又は１　　（＝−
１）の係数ａ　、　〜ａ、を用いて、ａ　＝　ａｏ＋　ａ、α＋ａ２α２＋ａ３α３　　　・
・・・（３）と表現できる。式（３）の係数ａ　ｏ　”
”　ａ　！　だけを縦に並べた表現を元ａの“ベクトル
表現”という。元ａのベクトル表現をａとすると、転置
記号（・・・）ｔを用いて、と表わすことができる。Ｇ　Ｆ　（２’）の各元０．α
１（ｉ＝ｏ、１゜す。

・・・・１４）のベクトル表現を以下に示０：（００００） α０＝１　　：（１０００）　　　　　　α’：（０１
０１）αＩ＝（Ｏｌ　００）　　　　　α”：（１１１
０）α’：（００１０）　　　　　　α１１．（Ｑ　　
１　１　１）α’：（０００１）　　　　　　α”：（
１１１１）α’：（１１００）　　　　　　α”：（１
０１１）α１：（１００１）ＧＦ（２’）上のＯ以外の客死ａはα１で表現でき、こ
のα１の元の１行列表現”Ｔ（α１ン　は、α１のベク
トル表現ａｌ　を用いて次式で定義される。

Ｔ（α′）＝〔α１　　αｌ＋Ｉ　　αｌ＋２　α′＋
３〕具体的にα１の行列表現Ｔ（αｌ）は次の様になる
。

Ｔ（α′）＝〔α１　　α２　　α３　　α４　〕ＧＦ
（２’）を−膜化したＧ　Ｆ　（２ｍ）上の任意の元は
ベクトル表現ではｍビットの２進数で表現できるため、
実際の論理回路ではベクトル表現が使用される。しかし
ＣＦ　（２ｍ〉上の元ａ　（＝α′）と元ｂ（＝α」）
（ｊは整数）との乗算結果ａ−ｂ即ちα１α」を求める
場合、元α１．αｊが共にベクトル表現のままであって
はその乗算結果のベクトル表現を求める簡便な方法がな
い。しかしながら、α瓢又はαｊの一方を行列表現に変
換すると容易にその乗算結果α１・α」のベクトル表現
を求めることができる。

即ち、有限体Ｇ　Ｆ　（２’）上においてα１を係数ａ
。

〜ａ３を用いて、またαｊを係数す。−ｂ、を用夫々次
の用にベクトル表現すると、２Ｎ　’＝　　（ａｏ　　ａ、　　ａ、　　ａ３）’　
　　　　　　　、−１，（６）α””　　（ｂｏ　　ｂ
＋　　ｂ２　ｂｓ）’　　　　　　　　・・・・（７）
αｊは次の様に１．α、α２．α３の線形結合で表現で
きる。尚、α１即ちａは式（３）で表わされる。

α’＝ｂＯ＋、ｂｌα＋ｂ２α２＋ｂ、α３　・・・・
（８）従って、ａとｂとの積即ちα１　とαｊとの積は
ａＩｂ＝α１・α」＝α’（ｂｏ＋ｂｌα＋ｂ２α２＋ｂ３α３）＝α’ｂ
ｏ＋α１０１　ｂ１＋αＩ＊２　ｂ２＋αｊ＊３　ｂ。

・・・・（９）で表わされる。式（５）より、式（９）におけるα１〜
αｌ＋３　のベクトル表現は夫々次の様になる。

α””（Ｔｏ。　Ｔ　ｏ　１Ｔ　Ｏ２Ｔ　０＊　）　’
αｉ＋＋＝（Ｔ１゜　Ｔ１．Ｔ、Ｔ１．）ｔαｌ＋２＝
（７２゜　Ｔ□　Ｔｚｚ　　Ｔ２３）’α”’＝　（Ｔ
ｆｆＯＴ３１　　Ｔｓ２　　Ｔ３３）’従って、式（９
）及び式（５）を用いてａ−ｂをベクル表現に変換する
と、ト＝　〔α１　　α１・１　αｌ＋２　　α′＋３〕　　
α４＝　　　Ｔ（αｌ）αｊ　　　　　　　　　　・・
・・（１０）が得られる。従って、ａ即ちαｊを行列表
現Ｔ（α′）に変換すると単に行列とベクトルとの通常
の乗算を行なうだけで、容易にａ−ｂのベクトル表現を
求めることができる。

以下、本発明による有限体の除算回路の一実施例につき
図面を参照して説明しよう。本例は有限体ＧＦ（２’）
上の元ＸをＧ　Ｆ　（２’）上の元ｙで除算して商ｚ　
（＝ｘ／ｙ）を求める除算回路に本発明を適用したもの
である。また、本例の有限体の法多項弐Ｐ　００１−！
係数ｇ＋、ｇ２．ｇｓ　を用イテ式（１）により定義す
ると共に、入力データ及び出力データは夫々４ビツトの
２進数によってベクトル表現する。

第１図は本例の除算回路のブロック図を示し、この第１
図において、（１）はベクトル表現から行列表現への表
現変換回路であり、この表現変換回路（１）に４ビツト
でベクトル表現された被除数Ｘ及び法多項弐ＰＯＯの係
数ｇ、〜ｇｓ（ｇと総称する。）を供給し、その被除数
Ｘの行列表現Ｔ　（ａ）の各要素ＴＩＪ（０≦１．ｊ≦
３〉を生成する。

（２）は行列とベクトルとを乗算してベクトルを生成す
る乗算ユニット、（３）はベクトル表現の除数ｙをベク
トル表現の逆元ｙ　−１に変換する変換テーブルとして
の逆元発生用ＲＯＭを示し、乗算ユニット（２）の一方
の入力ポートに行列Ｔ　（ｘ）の各要素を供給し、他方
の入力ポートにベクトル表現された逆元ｙ　−１の４ビ
ツトの係数（ｙ−’）。、　（ｙ−’）２．　（ｙ−’
）ａを供給する。この乗算ユニット（２）の出力ポート
より商ｚ　（＝ｘ／ｙ）のベクトル表現の４ビツトの係
数２０〜ｚ３　が出力される。

第２図は第１図例の具体的回路構成を示し、この第２図
の表現変換回路（１）において、（５）〜（７）、（１
１）〜（１３）、　（１７）〜（１９）は夫々アンドゲ
ート、（８）〜（１０）。

〈１４）〜（１６）、　（２０）〜（２２〉は夫々排他
的オアゲート（以下、ｒＥＸＯＲεＸＯＲゲートる。）
であり、アンドゲートは２つの係数の掛算器として使用
し、εＸＯＲゲートは２つの係数のｍａｄ　　２の加算
器して使用する。この場合、被除数Ｘのベクトル表現を
（Ｘｏ　　Ｘ、ｘ２　　ｘ、）’　　とすると、アント
ゲ−）（５）。

（６）、　（７）の一方の入力端子に共通に係数ｘ３を
供給し、他方の入力端子に夫々係数ｇ＋＋　ｇｚ、　ｇ
ｓを供給し、εＸＯＲゲート（８）、　　（９）、（１
０）　　の一方の入力端子に係数ＸＯ＋　ｘＩ＋　Ｘ２
　を供給し、εＸＯＲゲート（８）、　　（９）。

（１０）の他方の入力端子に夫々アントゲ−）（５）、
　　（６）。

（７）の出力データを供給する。

法多項弐Ｐ（Ｘ）＝Ｏの根をαとして、被除数Ｘのべき
表現をα１　とすると、この被除数Ｘの行列表現Ｔ　（
Ｘ）は式（５）によって表わされる。本例では係数Ｘ　
ｏ’＝　Ｘ　ｉが夫々行列Ｔ　（Ｘ）の要素ＴＯＯ〜Ｔ
ｏｓに対応し、係数Ｘ、及びεＸＯＲゲート（８）〜（
１０〉の出力データが夫々行列Ｔ　（Ｘ）の要素Ｔ’ｔ
ｏ及び要素Ｔｌｌ〜Ｔ１１に対応する。

また、アントゲ−）　（１１）〜（１３）の一方の入力
端子にＥＸＯＲゲー）　（１０）の出力データ（要素Ｔ
　ｌ　３　）を共通に供給し、他方の入力端子に夫々係
数ｇ、〜ｇ、を供給し、εＸＯＲゲート（１４）　〜（
１６）の一方の入力端子に夫々係数Ｔｌｏ−Ｔｌ２を供
給し、ＥＸＯＲゲー）　（１４）〜（１６〉の他方の入
力端子に夫々アントゲ−）　（１１）〜（１３〉の出力
データを供給する。要素ＴＩ３及びεＸＯＲゲート（１
４）〜（１６）の出力データが夫々行列Ｔ　（ａ）の要
素Ｔ２０及びＴ　２１−　Ｔ　２　ｓに対応する。同様
に、要素Ｔ　２３及びεＸＯＲゲート（２０〉〜〈２２
〉の出力データが夫々行列Ｔ　（ａ）の要素Ｔ、。及び
Ｔ’ｓ＋〜Ｔ３５に対応する。

表現変換回路（１）により乗数ａの行列表現Ｔ　（ａ）
の要１ｈ　Ｔ　ｔ　Ｊが求められる理由につき第３図を
参照して説明するに、この第３図は第２図のアントゲ−
）　（５）　〜（７）　ヲ掛算器として、εＸＯＲゲー
ト（８）〜（１０）を加算器として示している。この場
合、式（５）より被除数Ｘ（＝α’）の行列表現Ｔ　（
ｘ）は、元＜２’、　　１２ｍ’α１゛２．α１゛３　
のベクトル表現を４列に並べたものであり、これらのベ
クトル表現の係数がそのまま行列Ｔ　（ａ）の要素とな
っている。

先ず元α１のベクトル表現は（Ｘｏ　　ＸＩ　　Ｘ２　
　Ｘ２）ｔであり、元α１　は次の様に１．α、α２．
α３の線形結合で表現できる。

ａ’＝ｘ、＋ｘ、ａ＋ｘ２ａ”＋ｘｓａ’　　　−”（
１１）この式（１１）の両辺にαを掛けることによりＣ
ｌ”’＝　Ｘａα＋　ＸｌＣｌ”＋　Ｘ２（ｌｒ’＋　
Ｘ＊α””・（１２）が得られる。αは法多項弐Ｐ（Ｘ
）＝Ｏの根であるためＧ　Ｆ　（２’）上では式（２＾
）が成立し、この式（２＾〉を式（１２）に代入するこ
とにより、式（１２〉は次の様に変形できる。

ＣＩ”　＝　Ｘ６　α＋　Ｘ　Ｉα２＋ｘ２α３十Ｘ３
（１＋ｇ＋α＋ｇ２（ｒ”＋ｇ３（ｒ３）＝Ｘ３＋（Ｘ
ｌｌ＋Ｘ３ｇ＋）α十（Ｘ＋＋Ｘ５ｇ２）α２＋　（Ｘ
２＋　Ｘ３　ｇ３）α。　　　　　・・・・（１３）式
（１３）より、元α１゛１　のベクトル表現は（Ｘ、。

Ｘｏ＋　Ｘｓｇ＋＋　ｘ、＋Ｘ３ｇ２＊　Ｘ２＋Ｘ３ｇ
５）’　であり、このベクトル表現は（Ｔｏｏ　Ｔ＋＋
　Ｔｉｔ　Ｔｉｔ）’　に対応する。この場合、第３図
において、加算器（８）。

（９）、（１０）の出力データは夫々係数Ｘｏ＋Ｘｓ　
ｇ（、Ｘ＋＋　’Ｘ　３　ｇ　２．　Ｘ　ａ　＋　Ｘ　
ｓ　ｇ　３　であるため、第３図例によって行列Ｔ（３
）の要素Ｔ、。〜Ｔ’＋ｓが求められる。

同様に、元α１゛１　のベクトル表現より元αｌ″２の
ベクトル表現（行列要素Ｔ２゜〜Ｔ２３）が求められ、
元α′１のベクトル表現より元α１１のベクトル表現（
行列要素Ｔ３０〜Ｔ３ｊ）が求められる。尚、法多項弐
Ｐ（Ｘ）としては例えばＸ’＋Ｘ＋１が使用されるが、
この場合にはｇ＋＝　１．ｇｚ＝ｇ３＝　０であるため
、第３図例は第４図例に簡略化される。

第２図に戻り、（２）は乗算ユニットを示し、この乗算
ユニット（２）に表現変換回路（１）にて生成した行列
Ｔ　（ｘ）の各要素ＴＱＯ−’−７３３を供給する。こ
の乗算ユニット（２）において、（２３〉〜（３０）、
　（３５）〜（４２）は夫々アンドゲート、（３１）〜
（３４）、　（４３）〜（５０）は夫々εＸＯＲゲート
を示し、アンドゲート（２３〉〜（２６）の一方の入力
端子に夫々行列Ｔ　（Ｘ）の要素Ｔ０゜〜ＴＯ３を供給
し、他方の入力端子に共通に除数ｙの迎入ｙ″′のベク
トル表現の係数（ｙ−’）。を供給し、これらアントゲ
−）　（２３）〜（２６〉の出力データとして（ｙ−’
）ｏ　Ｔｏｏ　〜（３’−’）ｏ　Ｔｏｏを生成する。

同様に、迎入ｙ　−１のベクトル表現の残りの係数を（
ｙ　’）＋〜（ｙ−’）ｔとすると、アンドゲート（２
７）〜（３０）により（ｙ−’）＋’ｒ＋。〜（ｙ−’
）ｌＴ１３を生威し、アンドゲート（３５）　〜（３８
）により（ｙ−”Ｌ　Ｔ２１１〜（３’−’ＬＴ　２　
ｓを生成し、アンドゲート（３９）〜（４２）により（
ｙ−’）ａ’ｒｓ。〜＜’／−’＞５Ｔｓｓを生成する
。

また、ＥＸＯＲゲー）　（３１）、　（４３）、　（４
７）によりアンドゲート（２３）、　（２７）、　（３
５）、　（３９）　　の出力データをｍｏｄ２で加算し
て係数Ｚｏ　を生威し、ＥＸＯＲゲート（３２）。

（４４）、　（４８）　　によりアントゲ−）　（２４
）、　（２８）、　（３６）。

（４０）の出力データをｍｏｄ　　２で加算して係数２
１　を生成し、巳ＸＯＲゲート（３３）　、　（４５）
、　（４９）　　ｌ、：　ヨＦ）　７　ンドゲート（２
５）、　（２９）、　（３７）、　（４１）　　の出力
データをｍｏｄ２で加算して係数２２　を生威し、ＥＸ
ＯＲゲート（３４）。

（４６）、　（５０）　　によりアンドゲート（２６）
、　（３０）、　（３８）。

〈４２〉の出力データをｆｆＩａｄ　　２で加算して係
数２．を生成する。被除数Ｘと除数ｙとの商２のベクト
ル表現は（Ｚｏ　　Ｚ、　　ｚ２　　ｚ３）’　となる
。

第２図の乗算ユニット（２）により行列Ｔ　（Ｘ）とベ
クトルｙ−’　（迎入ｙ−１のベクトル表現）との積が
求められる過程について説明するに、行列Ｔ　（Ｘ）、
ベクトルｙ−１、ベクトル２　（商２のベクトル表現）
の各係数又は要素の間には次の様な関係がある。

・・・・（１４）この式（１４）よりベクトル２の各要素ｚｔ（ｉ　＝　
。

〜３）はと表わすことができる。式（１５）によれば、例えば係
数２０　は、Ｚｏ　＝Ｔｏｏ（ｙ−’）ｏ　＋　Ｔ＋ａ（ｙ−’）　
ｌ　＋Ｔ２ｏ（ｙ−’）２十Ｔ３゜（ｙ−’）ｓ・・・・（１６）になるが、第２図の乗算ユニット（２）によって求めら
れるｚｏはその式（１６）を充足しており、同様に係数
２．〜２．についても式（１５）を充足している。

上述の様に本例の除算回路によれば、有限体Ｇ　Ｆ　（
２’）上の被除数Ｘと除数ｙとの商２のベクトル表現が
その被除数Ｘの行列表現Ｔ　（Ｘ）とその除数ｙの迎入
ｙ　”’　ｌのベクトル表現との乗算によって求められ
ている。従って、変換テーブルとしてのＲＯＭ（逆元発
生用ＲＯＭ（３））は１個で済むため、変換テーブルと
してのＲＯＭを３個使用する従来例ｔＥ較して回路規模
を小型化できると共に演算速度を高速化できる利益があ
る。

尚、上述実施例では被除数Ｘの表現をベクトル表現から
行列表現に変換しているが、逆元発生用ＲＯＭ　（３）
と乗算ユニット（２）との間に表現変換回路（１）を配
することにより、除数ｙの迎入ｙ−１の表現をベクトル
表現から行列表現に変換し、この行列表現と被除数Ｘの
ベクトル表現とを乗算する如くなしてもよい。更に、上
述実施例は容易に一般的な有限体Ｇ　Ｆ　（２ｍ）（ｍ
は１以上の整数）上の除算回路に拡張することができる
。

次に、本発明の他の実施例につき第５図を参照して説明
しよう。本例は、有限体ＧＦ（２’）上の４ビツトでベ
クトル表現された共通の元Ｘを被除数、夫々４ビツトで
ベクトル表現された３個の元ａ。

ｃ、ｅを除数として３個の商ｂ（＝ｘ／ａ）、ｄ（＝Ｘ
／Ｃ）、ｆ　　（＝Ｘ／ｅ）をベクトル表現で求める除
算回路に本発明を適用したものである。

第５図は本例の除算回路を示し、この第５ｒＸＪにおい
て、（２Ａ）〜（２Ｃ）は夫々第１図例の乗算ユニット
と同一構成の乗算ユニット、（３＾）〜（３Ｃ）は夫々
第１図例の逆元発生用ＲＯＭ　（３）と同−構成の逆元
発生用ＲＯＭであり、被除数Ｘの表現を表現変換回路（
１）を介して行列表現Ｔ　（Ｘ）に変換し、この行列表
現Ｔ　（Ｘ）の各要素を乗算ユニット（２＾〉〜（２Ｃ
〉の夫々の一方の入力ポートに供給する。また、除数ａ
。

ｃ、ｅを夫々迎え発生用ＲＯＭ（３Ａ）、　（３Ｂ）、
　（３Ｃ）を介してベクトル表現の迎え；ａ　−１、Ｃ
−１、６−１に変換し、これら迎えを夫々乗算ユニッ）
　（２Ａ）、　（２Ｂ）。

（２Ｃ〉の他方の人力ポートに供給する。乗算ユニッ）
　（２Ａ）、　（２Ｂ）、　（２Ｃ）が夫々第１図例の
乗算ユニット（２）と同様に動作するため、それら乗算
ユニット（２＾）、　（２Ｂ）、　（２Ｃ）からは夫々
商す、　ｄ、　　ｆの４ビツトのベクトル表現の係数が
出力される。

第５図例によれば表現変換回路〔１）が３個の乗算ユニ
ッ）　（２Ａ）〜（２Ｃ〉に対して共通に使用されてい
るため、単に３個の除算器を並列に配する場合に比べて
全体の回路規模をより小型化することができる利益があ
る。

尚、第５図例を変形して、逆元発生用ＲＯＭ（３Ａ〉〜
（３Ｃ）と乗算ユニット（２＾〉〜（２Ｃ〉との間に夫
々ベクトル表現を行列表現に変換するための表現変換回
路を配してもよい。また、第５図例は被除数Ｘが共通の
場合を扱っているが、複数の除算において除数が共通の
場合にも本発明は適用される。

この様に除数が共通の場合には、除数を逆元発生用ＲＯ
Ｍ及び表現変換回路を介して複数の乗算ユニットの夫々
の一方の入力ポートに供給する如くなす。

このように本発明は上述実施例に限定されず、本発明の
要旨を逸脱しない範囲で種々の構成を採り得ることは勿
論である。

〔発明の効果〕

本発明によれば、回路規模をより小型化できると共に演
算速度を高速化できる利益がある。また、乗算回路が第
２の元の側を行列表現に変換する様になされている場合
には、その第２の元の表現の変換と第１の元の迎えの発
生とが並列に実行されるため、演算速度をより高速化す
ることができる。

更に、一群の元と１つの共通の元との夫々の商を求める
除算回路において表現変換回路を共通化した場合には、
回路規模を更に小型化できる実用上の利益がある。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、第２図は
第１ｒ！Ａ例の具体的回路構成を示す回路図、第３図は
第２図中の表現変換回路（１）の要部を示す回路図、第
４図は第３図例の特別な場合を示す回路図、第５図は本
発明の他の実施例を示すブロック図である。（１）は表現変換回路、（２）、（２人）〜（２Ｃ）は
夫々乗算ユニット、（３）、　（３Ａ）〜（３Ｃ）は夫
々迎え発生用ＲＯＭである。第３図

Claims

【特許請求の範囲】１、有限体ＧＦ（２＾ｍ）上のｍビットでベクトル表現
された第１の元の逆元をベクトル表現で生成する逆元発
生回路と、上記第１の元の逆元と有限体ＧＦ（２＾ｍ）
上のｍビットでベクトル表現された第２の元とを一方の
元を行列表現に変換して乗算する乗算回路とを有し、上記第２の元を上記第１の元で除した商を有限体ＧＦ（
２＾ｍ）上のｍビットのベクトル表現で得る様にした有
限体の除算回路。２、上記乗算回路が上記第２の元を行列表現に変換する
様になされている請求項１記載の有限体の除算回路。３、有限体ＧＦ（２＾ｍ）上のｍビットでベクトル表現
された一群の元と１つの共通の元との夫々の商を求める
除算回路において、上記一群の元の夫々の逆元又は上記共通の元の逆元をベ
クトル表現で生成する複数又は１つの逆元発生回路と、
上記共通の元を直接に又は上記逆元発生回路を介して行
列表現に変換する表現変換回路と、上記一群の元又は該
一群の元の夫々の逆元のベクトル表現と上記表現変換回
路より出力される行列表現とを乗算する複数の乗算回路
とを設けた有限体の除算回路。