(57)【特許請求の範囲】
【請求項１】
αｉを受信するための各々の入力ポートと各々の出力ポートとを持ち、原始要素αｉのべき乗をそれぞれ計算するための、第１乃至第３グループからなる複数のべき乗回路と、
前記第１グループ内の全てのべき乗回路の出力信号を掛け算し、第１の掛け算結果を生成するための第１掛け算回路と、
前記第２グループ内の全てのべき乗回路の出力信号を掛け算し、第２の掛け算結果を生成するための第２掛け算回路と、
前記第３グループ内の全てのべき乗回路の出力信号を第１クロックサイクル内に掛け算し、該第１クロックサイクル内に掛け算した結果と前記第２の掛け算結果とを第２クロックサイクル内に掛け算し、該第２クロックサイクル内に掛け算した結果と前記第１の掛け算結果とを第３クロックサイクル内に掛け算して第３の掛け算結果を生成するための第３掛け算回路と、
前記第３の掛け算結果を原始要素α＾（２ｎ−１）で割り算し、原始要素αｉの逆数を生成する手段と
を含む有限フィールドの任意原始要素の逆数具現回路。
【請求項２】
前記複数のべき乗回路は、原始要素αｉ＾２１から原始要素αｉ＾２７までをそれぞれ計算するための、第１乃至第７べき乗回路を備えることを特徴とする請求項１に記載の有限フィールドの任意原始要素の逆数具現回路。
【請求項３】
前記第１の掛け算回路は、第２及び第３べき乗回路の出力信号を掛け算して、第１の副掛け算結果を第１クロックサイクル内に生成するためのものであり、
前記第１掛け算回路は、第１の副掛け算結果と第１べき乗回路の出力信号とを掛け算して、第１掛け算結果を生成することを特徴とする請求項２に記載の有限フィールドの任意原始要素の逆数具現回路。
【請求項４】
前記第２掛け算回路は、第４及び第５のべき乗回路の出力信号とを掛け算して、第２の掛け算結果を生成することを特徴とする請求項２に記載の有限フィールドの任意原始要素の逆数具現回路。
【請求項５】
前記第３掛け算回路は、第６及び第７のべき乗回路の出力信号を掛け算して、第２の副掛け算結果を第１クロックサイクル内に生成し、
前記第３掛け算回路は、第２の副掛け算結果と第２の掛け算結果とを掛け算して、第３副掛け算結果を第２クロックサイクル内に生成し、
前記第３掛け算回路は、第３の副掛け算結果と第１の掛け算結果とを掛け算して、第３の掛け算結果を生成することを特徴とする請求項２に記載の有限フィールドの任意原始要素の逆数具現回路。
【請求項６】
有限フィールドＧＦ（２８）の任意の原始要素αｉの逆数を求める回路において、
αｉを受けるための入力ポートと出力ポートを各々備え、
原始要素（αｉ）＾（２ｌ）乃至原始要素（αｉ）＾（２７）を計算する第１乃至第７掛け算回路と、
前記第１掛け算回路の出力ポートと連結される第１入力ポート、前記第２掛け算回路と連結される第２入力ポート、出力ポートを有する第１選択器と、
前記第３掛け算回路の入力ポートと連結される第１入力ポート、第２入力ポート、そして出力ポートを有する第２選択器と、
前記第１及び第２選択器の出力信号を掛けるための第１フィールド掛け算器と、
前記第１フィールド掛け算器の出力ポートと連結される入力ポートと前記第２選択器の第２入力ポートと連結される出力ポートを有し、前記第１フィールド掛け算器の出力信号を貯蔵する第１レジスターと、
前記第４及び第５掛け算回路の出力信号を掛ける第２フィールド掛け算器と、
前記第２フィールド掛け算器の出力ポートと連結される入力ポート及び出力ポートを有し、前記第２フィールド掛け算器の出力信号を貯蔵する第２レジスターと、
前記第１レジスターの出力ポートと連結される第１入力ポート、前記第２レジスターの出力ポートと連結される第２入力ポート、前記第６掛け算回路の出力ポートと連結される第３入力ポート、出力ポートを有する第３選択器と、
前記第７掛け算回路の出力ポートと連結される第１入力ポート、第２入力ポート、そして出力ポートを有する第４選択器と、
前記第３及び第４選択器の出力信号を掛ける第３フィールド掛け算器と、
前記第３フィールド掛け算器の出力ポートと連結される入力ポート及び前記第４選択器の第２入力ポートと連結される出力ポートを有し、前記第３フィールド掛け算器の出力信号を貯蔵する第３レジスターと、
前記第３フィールド掛け算器の出力を原始要素α＾（２８−１）で割り算し、前記原始要素の逆数を発生する割り算器と
を含むことを特徴とする原始要素逆数具現回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタルデータ伝達と信号処理に関するものであり、より詳しくは、有限フィールド（ｆｉｎｉｔｅ  ｆｉｅｌｄ）の要素の逆数（ｉｎｖｅｒｓｅ）を得るための回路に関するものである。
【０００２】
【従来の技術】
ディジタル信号処理の改善において、有限フィールド動作がエラー訂正システム（ｅｒｒｏｒ  ｃｏｒｒｅｃｔｉｏｎ  ｓｙｓｔｅｍ）、暗号システム（ｃｒｙｐｔｏｇｒａｐｈｙ  ｓｙｓｔｅｍ）のような多くの応用に適用されてきた。
このようなシステムにおいて、情報伝達率を高め、同時に低いエラー率（ｌｏｗｅｒｒｏｒ  ｒａｔｅ）を維持するためエラー制御技術（ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｓｃｈｅｍｅ）の使用が必要である。例えば、有限フィールド（ｆｉｎｉｔｅ  ｆｉｅｌｄ）は、リードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）、ＢＣＨコード（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ  ｃｏｄｅｓ）のようなエラー訂正コード内でエンコードされる（ｅｎｃｏｄｅｅｄ）データが伝送される間、エラー訂正のため使用される２進数の有限単位（ｆｉｎｉｔｅ  ｓｅｔ  ｏｆ  ｂｉｎａｒｙ  ｎｕｍｂｅｒｓ）である。特に、有限フィールドの特別な有形であるガロアフィールド（Ｇａｌｏｉｓ  ｆｉｅｌｄ）ＧＦ（２m）は、上述のような応用フィールドに広く使用されてきた。
【０００３】
例えば、有限ガロアフィールドの動作のうち、リードソロモンデコーダ（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｄｅｃｏｄｅｒ）で訂正率（ｃｏｒｒｅｃｔｉｏｎ  ｃｏｅｆｆｉｃｉｅｎｔｓ）を求めるためには、Ａ／Ｂ率を求めることが必要であるが、ＡとＢは、デコーダによって求めた数であり、任意の値（ａｒｂｉｔｒａｒｙ  ｖａｌｕｅｓ）を有する場合もある。Ａは、一般的にＢの逆数（ｉｎｖｅｒｓｅ）に掛けることである。そのため、デコーダで任意の原始要素（ｐｒｉｍｉｔｉｖｅ  ｅｌｅｍｅｎｔ）の逆数を形成することが必要である。
【０００４】
ガロアフィールドＧＦ（２m）（ここで、ｍは、要素の集合数、又はコード長さを意味する。）の原始要素αiの逆数（αi）-1は、次のような数学式に示す。（αi）-1＝αn-i            …  （１）
ここで、ｎ＝２m−１
【０００５】
例えば、ＧＦ（２8）から、原始要素α2の逆数は、（α2）-1＝α255-2＝α253である。
【０００６】
ＧＦ（２m）から、要素の逆数を求めるいろいろ方法のうち１つが図１に示すようにＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ：ＲＯＭ）に存在する参照用テーブル（ｌｏｏｋ−ｕｐ  ｔａｂｌｅ）を使用することである。ＲＯＭを使用する技術は、１９８４．２月出版された“Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  ＶＬＳＩ  ｄｅｓｉｇｎ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  Ｄｅｃｏｄｅｒ”題目のＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ、Ｖｏｌ．Ｃ−３３、Ｎｏ．２、ｐｐ．１７８−１８９、に掲載されている。任意の原始要素αi、又はそれと同一なことがアドレスとしてＲＯＭの入力に印加されて逆数（αi）-1がＲＯＭから出力される。ここで、貯蔵された逆数は、アドレスと同じようにｍビットを含むため、ＲＯＭのサイズは、２m×ｍになる。
【０００７】
しかし、ＲＯＭの利用は、集積回路を設計するための一般技術に存在する他の処理回路と統合することには不適合である。このような技術を持ち、ＲＯＭは、処理回路が集積される他の要素の外部領域に位置する場合もある。さらに、ＧＦ（２m）から要素のビット数が増加すると、要求されるメモリサイズは、幾何級数的（ｇｅｏｍｅｔｒｉｃ  ｐｒｏｇｒｅｓｓｉｏｎ）に増加するようになる。
【０００８】
【発明が解決しようとする課題】
従って、本発明の目的は、大きさがより小さく費用が節減され、従来より構造が簡単な有限フィールドで任意要素の逆数を求める回路を提供することである。
【０００９】
又、本発明の目的は、３クロックサイクルの間、任意有限フィールド逆数を得ることができる回路を提供することである。
【００１０】
【課題を解決するための手段】
上述のような目的を達成するための１特徴によると、逆数回路は、原始要素（αi）＾（２l）乃至要素（αi）＾（２m-1）を計算する手段と、原始要素（αi）＾（２l）乃至要素（αi）＾（２m-1）を共に掛け算し、それに対応する出力信号を発生する手段と、そして掛け算手段の出力信号をα（２m−１）で割り算し、任意原始要素αiの逆数を発生する手段とを含む。本発明の回路は、特にロジック回路の結合である。
【００１１】
【発明の実施の形態】
最初に、本明細書中において、Ａ＾Ｂという表記が取られるが、これは、ＡBを示しており、数学的に同等のものであるとする。
【００１２】
以下、本発明の望ましい実施形態による参照図面、図２及び図３に基づいて詳細に説明する。
【００１３】
図２は、本発明による有限フィールドで任意要素の逆数を求めるための逆数回路を示す。
【００１４】
図２を参照すると、逆数回路１０は、原始要素（αi）＾（２l）乃至原始要素（αi）＾（２m-1）を求め、（αi）＾（２l）乃至（αi）＾（２m-1）を含む全ての原始要素を掛けるためのべき及び掛け算回路１００を含む。又、逆数回路１０は、べき及び掛け算回路に連結され、べき及び掛け算回路１００の出力ＭOUTを原始要素α＾（２m−１）で割るための割り算回路２００も含む。
【００１５】
図３は、有限ガロアフィールドＧＦ（２8）に適する図２のべき及び掛け算回路の構成を詳細に示す。
【００１６】
有限ガロアフィールドＧＦ（２8）の選択は、よく知られているため、本発明は特定の大きさの有限フィールドだけに限定されたことではない。
【００１７】
図３を参照すると、例えば、べき及び掛け算回路１００は、８ビットのαi（具体的に、任意原始要素）から（αi）＾（２l）乃至（αi）＾（２7）各々を求めるための第１乃至第７掛け算回路１０１−１０７を含む。（αi）＾（２l）（具体的に（αi）2）乃至（αi）＾（２7）（具体的に、（αi）128）は、次のような数式によって各々得られる。ここで、α逆数を求めようとする原始要素αiとして入力ビット値であり、ｑは、原始要素に対する出力ビット値αiとしてαとｑは、同一のｍビットである。もし、ＧＦ（２8）であると、α（０）〜α（７）は、  αiの最下位ビット（Ｌｅａｓｔ  Ｓｉｇｎｉｔｉｆｉｃａｎｔ  Ｂｉｔ）から最上位ビット（Ｍｏｓｔ  Ｓｉｇｎｉｔｉｆｉｃａｎｔ  Ｂｉｔ）までを意味し、ｑ（０）〜ｑ（７）は、（αi）nの最下位ビットから最上位ビットまでを意味する。
【００１８】
（αi）2：
ｑ（０）＝α０＋α４＋α６＋α７
ｑ（１）＝α７
ｑ（２）＝α１＋α４＋α５＋α７
ｑ（３）＝α４＋α６
ｑ（４）＝α２＋α４＋α５＋α７
ｑ（５）＝α５
ｑ（６）＝α３＋α５＋α７
ｑ（７）＝α６
【００１９】
（αi）4：
ｑ（０）＝α０＋α２＋α３＋α６
ｑ（１）＝α６
ｑ（２）＝α２＋α３＋α４＋α５＋α６
ｑ（３）＝α２＋α３＋α４＋α６＋α７
ｑ（４）＝α１＋α２＋α５＋α７
ｑ（５）＝α５
ｑ（６）＝α３＋α４
ｑ（７）＝α３＋α５＋α６
【００２０】
（αi）8：
ｑ（０）＝α０＋α１＋α３＋α４＋α７
ｑ（１）＝α３＋α５＋α６
ｑ（２）＝α１＋α２＋α３＋α４＋α６＋α７
ｑ（３）＝α１＋α２＋α３＋α４＋α５＋α７
ｑ（４）＝α１＋α４＋α７
ｑ（５）＝α５
ｑ（６）＝α２＋α５＋α６＋α７
ｑ（７）＝α３＋α４
【００２１】
（αi）16：
ｑ（０）＝α０＋α２＋α４＋α５＋α６＋α７
ｑ（１）＝α３＋α４
ｑ（２）＝α１＋α２＋α３＋α４＋α５
ｑ（３）＝α１＋α２＋α４＋α５＋α６
ｑ（４）＝α２＋α４＋α５＋α６
ｑ（５）＝α５
ｑ（６）＝α１＋α３＋α４＋α５＋α６
ｑ（７）＝α２＋α５＋α６＋α７
【００２２】
（αi）32：
ｑ（０）＝α０＋α１＋α２＋α３＋α４
ｑ（１）＝α２＋α５＋α６＋α７
ｑ（２）＝α１＋α２＋α４＋α５
ｑ（３）＝α１＋α２＋α３
ｑ（４）＝α１＋α２＋α３＋α７
ｑ（５）＝α５
ｑ（６）＝α２＋α３＋α５
ｑ（７）＝α１＋α３＋α４＋α５＋α６
【００２３】
（αi）64：
ｑ（０）＝α０＋α１＋α２＋α６＋α７
ｑ（１）＝α１＋α３＋α４＋α５＋α６
ｑ（２）＝α１＋α２＋α５＋α６
ｑ（３）＝α１＋α５＋α７
ｑ（４）＝α１＋α５＋α６＋α７
ｑ（５）＝α５
ｑ（６）＝α１
ｑ（７）＝α２＋α３＋α５
【００２４】
（αi）128：
ｑ（０）＝α０＋α１＋α３
ｑ（１）＝α２＋α３＋α５
ｑ（２）＝α１＋α３＋α４＋α５＋α７
ｑ（３）＝α５＋α６＋α７
ｑ（４）＝α３＋α７
ｑ（５）＝α５
ｑ（６）＝α７
ｑ（７）＝α１
【００２５】
続いて、図３を参照すると、べき及び掛け算回路１００は、第１乃至第４マルチプレクサ１０８、１０９、１１４、１１５と、第１乃至第３ガロアフィールド掛け算１１０、１１２、１１６、そして第１乃至第３レジスター１１１、１１３、１１７とを付加的に含む。
【００２６】
マルチプレクサ１０８の２つの入力ポートは、掛け算回路１０１、１０２の出力ポートと各々連結される。マルチプレクサ１０８の出力ポートは、フィールド掛け算器１１０の入力ポートと連結される。マルチプレクサ１０９の２つの入力ポートは、掛け算回路１０３及びレジスター１１１の出力ポートと各々連結される。マルチプレクサ１０９の出力ポートは、フィールド掛け算器１１０のほかの入力ポートと連結される。掛け算回路１０４、１０５の出力ポートは、レジスター１１３の入力ポートと連結される出力ポートを有するフィールド掛け算器１１２の入力ポートと各々連結される。マルチプレクサ１１４は、３つの入力ポートを有し、そのうち、２つはレジスター１１１、１１３の出力ポートと連結され、残りの１つは掛け算回路１０６の出力ポートと連結される。
【００２７】
マルチプレクサ１１４の出力ポートは、フィールド掛け算器１１６の入力ポートと連結される。マルチプレクサ１１５の１入力ポートは、掛け算回路１０７の出力ポートと連結され、マルチプレクサ１１５の他の入力ポートは、レジスター１１７の出力ポートと連結される。マルチプレクサ１１５の出力ポートは、出力ポートがレジスター１１７の入力ポートと連結されるフィールド掛け算器１１６の他の入力ポートと連結される。レジスター１１７の出力ポートは、又割り算回路２００にも提供される。割り算回路２００は、レジスター１１７の出力信号を原始要素α＾（２8−１）で割り算する。従来割り算回路は、割り算を行うための手段として、これは割り算回路の実行を可能にする一般的な技術のうちの１つである。
【００２８】
べき及び掛け算回路１００の全ての構成部品は、外部から印加されたクロックＣＬＫによって動作される。次の表１は、各々のクロック内で計算された値を示し、表２は、３つの掛け算器１１０、１１２、１１６の動作状態を示す。
【００２９】
【表１】
0003913921.tif 000002
【００３０】
【表２】
0003913921.tif 000003
【００３１】
表１及び表２を参照すると、第１クロックサイクルから、掛け算回路１０２、１０３、１０６、１０７の各々の出力（αi）4、（αi）8、（αi）64、（αi）128は、マルチプレクサ１０８、１０９、１１４、１１５によって各々選択される。フィールド掛け算器１１０は、（αi）4、（αi）8を掛け算し、第２フィールド掛け算器１１２は、（αi）64、（αi）128を掛け算し、掛け算器１１６は、（αi）64、（αi）128とを掛け算する。
【００３２】
第２サイクルクロックから、マルチプレクサ１０８は、掛け算回路１０１の出力（αi）2を選択し、マルチプレクサ１０９は、レジスター１１１の出力（αi）4・（αi）8を選択する。掛け算器１１０は、（αi）2と（αi）4・（αi）8を一緒に掛ける。掛け算器１１０の出力（αi）2・（αi）4・（αi）8は、レジスター１１１に貯蔵される。その上、１サイクルの間、マルチプレクサ１１４、１１５各々は、レジスター１１３、１１７から（αi）16・（αi）32及び（αi）64・（αi）128を選択する。（αi）16・（αi）32及び（αi）64・（αi）128ノ値は、掛け算器１１６によって掛け算され、その後、掛けられた結果の値（αi）16・（αi）32・（αi）64・（αi）128がレジスター１１７に貯蔵される。
【００３３】
第３サイクルの間、マルチプレクサ１１４は、レジスター１１１の出力（αi）2・（αi）4・（αi）8を選択し、マルチプレクサ１１５は、レジスター１１７の出力（αi）16・（αi）32・（αi）64・（αi）128を選択する。掛け算器１１６は、（αi）16・（αi）32・（αi）64・（αi）128と（αi）2・（αi）4・（αi）8を掛け算する。このサイクルから、掛け算器１１６の最後の出力（αi）2・（αi）4・（αi）8・（αi）16・（αi）32・（αi）64・（αi）128は、レジスター１１７（最後の出力が貯蔵される）を通して割り算回路２００に提供され、その後、最後の出力は、割り算回路２００においてα＾（２m−１）で割り算される。
【００３４】
原始要素α2の逆数が計算された場合、掛け算器１１６の最後の出力は、（α2）2・（α2）4・（α2）8・（α2）16・（α2）32・（α2）64・（α2）128＝α508になる。割り算回路２００から、掛け算器１１６の最後の出力α508は、α＾（２m−１）で割り算される。もし有限フィールドのコード長がｍ＝８ビットであると、掛け算器１１６の最後の出力α508は、α255デ割られる。その結果、原始要素α2の逆数は、割り算回路２００の出力α508-255（＝α253）になる。その結果は、式（１）によって得られる結果と同一である。
【００３５】
以上から、本発明による回路の構成及び動作を説明し、図面によって図示したが、これは例を挙げて説明したことに過ぎない。べき及び掛け算回路の配列は、有限フィールドＧＦ（２m）のコード長ｍを有し、多様に変更できる。本発明の技術的思想及び範囲を外れない範囲内で多様な変化及び変更が可能である。
【００３６】
【発明の効果】
従って、本発明によると、デコーダでのＲＯＭの使用を避けることができ、それによって有限フィールドのコード長が増加してもデコーダの回路の大きさを減らすことができる。それにより、逆数も３クロックサイクルの間内に得ることができ、高速デコーダを得ることができる利点もある。
【図面の簡単な説明】
【図１】  従来技術による有限フィールドで任意要素の逆数を発生する参照用テーブルを示すブロック図である。
【図２】  本発明による有限フィールドで任意要素の逆数を具現するためのブロック図である。
【図３】  本発明の実施形態による図２のパワー及び掛け算回路の回路図である。
【符号の説明】
１００：べき及び掛け算回路
２００：割り算回路
【図１】
0003913921.tif 000004
【図２】
0003913921.tif 000005
【図３】
0003913921.tif 000006