JPS645334B2 - - Google Patents

Description

【発明の詳細な説明】

この発明は、ガロア体GF（2^m）上の元の乗算又
は除算を行なう演算回路に関する。 この演算回路は、BCH符号などの符号化或い
は復号化に用いられる。従来のこの種の演算回路
は、多数のゲート回路を組み合わせた構成のもの
であり、IC化したときにチツプ上の面積が大き
くなる欠点があつた。 この発明は、GF（2^m）が位数（2^m−１）の乗法
群をなすことに着目し、ROM或いはPLA（プロ
グラマブル・ロジツク・アレー）と加算回路とを
用いる等簡単な構成の演算回路の実現を目的とす
るものである。この発明が適用された演算回路
は、IC化したときにチツプ上の面積が小となる
と共に、パターンが規則的なものとなり、IC化
に好適なるものである。 この発明の説明に先立ち、ガロア体GF（p^m）に
ついて簡単にふれる。ガロア体GF（p^m）は、ベク
トルと巡回群との何れかによつて表現することが
できる。 まずベクトル表現を用いる。GF（p^m）は、GF
（ｐ）の上のｍ次の既約多項式Ｆ（ｘ）を法とする
多項式環である。したがつてＦ（ｘ）の根をα＝
｛ｘ｝（｛ｘ｝は剰余類の意味）とすれば、GF（p^m）
の元は、１、α＝｛ｘ｝、α²＝｛x²｝、……、α^m-1＝
｛x^m-1｝の線形結合で表わすことができる。即ち a_n-1｛x^m-1｝＋a_n-2｛x^m-2｝＋…＋a₁｛ｘ｝＋a₀ ＝a_n-1α^m-1＋a_n-2α^m-2＋…＋a₁α＋a₀ と表わせる。要するに （a_n-1、a_n-2、……、a₁、a₀） のようにベクトルで表現できる。ここで a_n-1、a_n-2、……、a₁、a₀∈GF（ｐ） である。 次に、巡回群により表現する。GF（p^m）から０
元を除いた残りの元は、位数p^m−１の乗法群を
なす。この乗法群は巡回群である。乗法群Ｇにお
いて、Ｇに属するすべての元がＧのある元αのベ
き乗であらわされるとき、Ｇを巡回群とよび、α
を原始元とよぶと定義される。 例えばGF(2)上の既約多項式Ｆ（ｘ）＝x³＋ｘ＋
１について、Ｆ（ｘ）＝０とする根αを考える。即
ちＧ（α）＝α³＋α＋１＝０（mod.α³＋α＋１）か
ら、各元のコードは、下記のものとなる。

【表】 なお、αのべき乗は、巡回群による表現であ
る。 本願出願人は、GF（2^m）上で定義されるエラー
検出、訂正符号として、バーストエラー及びラン
ダムエラーの何れに対してもエラー訂正能力が高
く、然もエラー検出の見逃し又は誤つた訂正を行
なうおそれが低減されたものを先に提案してい
る。 この符号では、ｍビツトを１ワードとし、ｎワ
ードで１ブロツクを構成するとき、下記のパリテ
イ検査行列Ｈにもとずいてｋ個のチエツクワード
を発生するようにしている。 更に、４個（ｋ＝４）のチエツクワードを用い
る場合を例にとると、パリテイ検査行列Ｈは となる。受信データの１ブロツクを列ベクトルＶ
＝（W^_o-1、W^_o-2、……、W^₁、W^₀）（但しW^i＝Wi
＋ei、ei：エラーパターン）とすると受信側で発
生する４個のシンドロームS₀，S₁，S₂，S₃は となる。この誤り訂正符号は、ひとつのエラー訂
正ブロツク内の２ワードエラーまでのエラー訂正
が可能であり、エラーロケーシヨンがわかつてい
るときには、３ワードエラー又は４ワードエラー
の訂正が可能である。 １ブロツク中に４個のチエツクワード（ｐ＝
W₃、ｑ＝W₂、ｒ＝W₁、ｓ＝W₀）が含まれる。
このチエツクワードは、下記のようにして求めら
れる。但し、Σは_o-1 〓ⁱ⁼⁴ を意味する。 ｐ＋ｑ＋ｒ＋ｓ＝ΣWi＝ａ α³p＋α²q＋αr＋ｓ＝ΣαⁱWi＝ｂ α⁶p＋α⁴q＋α²r＋ｓ＝Σα²ⁱWi＝ｃ α⁹p＋α⁶q＋α³r＋ｓ＝Σα³ⁱWi＝ｄ 計算過程を省略し、結果のみを示すと となる。このようにしてチエツクワードｐ，ｑ，
ｒ，ｓを形成するのが送信側に設けられた符号器
の役目である。 次に、上述のように形成されたチエツクワード
を含むデータが伝送され、受信された場合のエラ
ー訂正のアルゴリズムについて説明すると、２ワ
ードエラーei，ejの場合のシンドロームに関する
式は S₀＝ei＋ej S₁＝αⁱei＋α^jej S₂＝α²ⁱei＋α^2jej S₃＝α³ⁱei＋α^3jej この式を変形すると （αⁱS₀＋S₁）（αⁱS₂＋S₃）＝（αⁱS₁＋S₂）² 更に変形して下記のエラーロケーシヨン多項式
を求むる。 （S₀S₂＋S₁ ²）α²ⁱ＋（S₁S₂＋S₀S₃）αⁱ ＋（S₁S₃＋S₂ ²）＝０ ここで、各式の係数を S₀S₂＋S₁ ²＝Ａ S₁S₂＋S₀S₃＝Ｂ S₁S₃＋S₂ ²＝Ｃ とおく。上式の各係数Ａ、Ｂ、Ｃを用いることに
より２ワードエラーの場合のエラーロケーシヨン
を求めることができる。 〔1〕 エラーがない場合： Ａ＝Ｂ＝Ｃ＝０、S₀＝０、S₃＝０ 〔2〕 １ワードエラーの場合： Ａ＝Ｂ＝Ｃ＝０、S₀≠０、S₃≠０ のときに１ワードエラーと判定される。（αⁱ＝
S₁／S₀）からエラーロケーシヨンｉが分かり、（ei ＝S₀）を用いてエラー訂正がなされる。 〔3〕 ２ワードエラーの場合： ２ワード以上のエラーの場合には、（Ａ≠０、
Ｂ≠０、Ｃ≠０）が成立し、その判定が頗る簡
単となる。またこのとき Aα²ⁱ＋Bαⁱ＋Ｃ＝０（但し、ｉ＝０〜（ｎ−
１）） が成立している。ここで（Ｂ／Ａ＝Ｄ、Ｃ／Ａ＝Ｅ） とおくと Ｄ＝αⁱ＋α^j、Ｅ＝αⁱ・α^j であり α²ⁱ＋Dαⁱ＋Ｅ＝０ となる。ここで、２つのエラーロケーシヨンの
差がｔであるつまり（ｊ＝ｉ＋ｔ）とすると Ｄ＝αⁱ（１＋α^t）、Ｅ＝α^2i+t と変形される。したがつて D²／Ｅ＝（１＋α^t）²／α^t＝α^-t＋α^t となる。ROMに（ｔ＝１〜（ｎ−１））の
夫々に関する、α^-t及びα^tの値を予め書込んで
おき、ROMの出力から求められた（α^-t＋α^t）
と受信ワードから演算された（D²／Ｅ）の値との 一致を検出することでｔが求まる。もし、この
一致関係が成立しなければ、３ワード以上のエ
ラーである。そこで Ｘ＝１＋α^t Ｙ＝１＋α^-t＝D²／Ｅ＋Ｘ とおくことにより αⁱ＝Ｄ／Ｘ、α^j＝Ｄ／Ｙ となり、エラーロケーシヨンｉ及びｊが求めら
れる。エラーパターンei、ejは ei＝（α^jS₀＋S₁）／Ｄ＝S₀／Ｙ＋S₁／Ｄ ej＝（αⁱS₀＋S₁）／Ｄ＝S₀／Ｘ＋S₁／Ｄ と求められ、エラー訂正を行なうことができ
る。 上述のエラー検出訂正符号では、１ワードを８
ビツト（16ビツトを１ワードとするときには、そ
の上位と下位とで２分割して得られる８ビツト）
とし、GF（2⁸）を考え、既約多項式をＦ（ｘ）＝x⁸
＋x⁴＋x³＋x²＋１としている。これは、位数255
の巡回群となつている。 上述の符号化及び復号化では、元αⁱ，α^j同士の
演算が必要とされる。この場合の乗除算の演算回
路について図面を参照して説明する。第１図乃至
第４図の各図において、１Ａは、元αⁱが供給され
るときにその指数ｉを発生する変換ROMを示
し、１Ｂは、元α^jが供給されるときに、その指数
ｊを発生する変換ROMを示す。指数ｉ、ｊは、
夫々ｍビツトのバイナリーコードである。また、
２は、mod.（2^m−１）の加算回路を示し、３は、
入力される指数を有するαのべき乗の出力データ
を発生する逆変換ROMを示す。ROMの代わり
にPLAを用いても良い。 第１図に示す構成は、変換ROM１Ａ，１Ｂの
夫々から発生する指数ｉ、ｊを加算回路２で加算
した出力（ｉ＋ｊ）を逆変換ROM３に入力し、
出力データとして乗算出力（α^i+j＝αⁱ・α^j）を得
るようにしたものである。 第２図に示す構成は、変換ROM１Ｂから出力
される指数ｊを反転回路４Ａにより反転して加算
回路２に供給し、その出力（ｉ−ｊ）を逆変換
ROM３に供給し、出力データとして除算出力
（α^i-j＝αⁱ／α^j）を得るようにしたものである。 第３図に示す構成は、変換ROM１Ａから出力
される指数ｉを反転回路４Ｂにより反転して加算
回路２に供給し、その出力（ｊ−ｉ）を逆変換
ROM３に供給し、出力データとして除算出力
（α^j-i＝α^j／αⁱ）を得るようにしたものである。 第４図に示す構成は、変換ROM１Ａ，１Ｂの
出力を加算回路２に供給し、その出力（ｉ＋ｊ）
を反転回路４Ｃで反転して逆変換ROM３に供給
し、出力データとして（α^-(i+j)＝１／α^i+j）を得る
よ うにしたものである。 更に、第１図乃至第４図の各構成は、反転回路
４Ａ，４Ｂ，４Ｃとして外部からのコントロール
信号によつて非反転動作も行ないうる構成のもの
を使用することによつて、ひとつの回路構成のも
のとでき、上述のコントロール信号に応じて乗算
又は除算を切替えるようになしうる。先に説明し
たエラー検出訂正符号の復号における１ワードエ
ラーの場合には、（αⁱ＝S₁／S₀）の演算を行ない、 （αⁱ）からエラーロケーシヨンを求める必要があ
るが、上述した除算回路（第２図又は第３図）を
適用することによつて、加算回路２から直ちにエ
ラーロケーシヨンｉのデータを得ることができ
る。 以下、第５図を参照してこの発明の一実施例に
ついて説明する。この実施例では、上述のよう
に、反転動作と非反転動作とがコントロール信号
CTL２によつて（CTL2＝“０”で非反転、
CTL2＝“１”で反転）のように切替えられる反
転制御回路４が設けられて乗算又は除算の何れも
行ないうるようにされていると共に、必要とする
変換ROMを１個ですませるように時分割処理を
行なう構成とされている。 第５図において、５は、データバスを示し、６
及び７は、指数データが貯えられるレジスタを示
し、８及び９は、元データが貯えられるレジスタ
を示す。データバス５からの入力データは、変換
ROM１及び０元検出回路１０に供給される。０
元検出回路１０は、入力データが０元の場合に
“１”となり、そうでないときに“０”となる１
ビツトの検出信号DETを発生する。この検出信
号DETは、変換ROM１からの指数データ（例え
ば８ビツト）と共に、レジスタ６に貯えられる。
このレジスタ６のデータが反転制御回路４を介し
てmod.（2^m−１）例えば（mod.255）の加算回路
２の一方の入力Ａとして供給される。加算回路２
の他方の入力Ｂとして、次段のレジスタ７に貯え
られているデータがゲート回路１１を介して供給
される。 このゲート回路１１は、コントロール信号
CTL１により制御され、（CTL1＝“１”）のとき
にレジスタ７のデータを通過させて加算回路２の
入力Ｂとして与え、出力（Ａ＋Ｂ）が発生し、
（CTL1＝“０”）のときに、データの通過を阻止
し、その出力データを０とし、このとき出力Ａ即
ち入力データがそのまま加算回路２からレジスタ
７に供給される。また、検出信号DETは、オア
ゲート１２を介してレジスタ７に供給されると共
に、レジスタ７に貯えられている以前の検出信号
がアンドゲート１３を介してオアゲート１２に供
給される。このアンドゲート１３の他の入力とし
てコントロール信号CTL１が供給され、（CTL1
＝“１”）の場合には、レジスタ７の検出信号が０
元であることを示すときでも、オアゲート１２の
出力が“１”となる。 （mod.2^m−１）例えば（mod.255）の加算回
路２は、８ビツトのフルアダーを用い、そのキヤ
リー出力Coを自己のキヤリー入力Ciに正帰還す
る構成とすることができる。加算出力の値によつ
て加算回路２は、下記のように動作する。 ０≦Ａ＋Ｂ≦254 Σ＝Ａ＋Ｂ Co＝０ Ａ＋Ｂ＝255 Σ255 Co＝０ Ａ＋Ｂ＝256（Σ＝０、Co＝１）となつて後、 （Σ＝１、Co＝１）となる。 256＜Ａ＋Ｂ≦510 Σ＝Ａ＋Ｂ＋１ Co＝１ そしてレジスタ７に貯えられている加算出力デ
ータが逆変換ROM３に供給され、この加算出力
を指数とする元データが出力される。この逆変換
ROM３に対しては、反転制御回路４に対して供
給される乗除算切替用のコントロール信号CTL
２が制御用として与えられている。逆変換ROM
３の出力データがゲート回路１４を介して出力
OUT１に取り出されると共に、レジスタ８に供
給される。ゲート回路１４は、レジスタ７に貯え
られている検出信号DETが“１”のときには、
ゲート回路１４の出力データを強制的に０元とす
るものである。 この実施例では、更に２つの元データの
（mod.2）の加算出力も出力OUT２として得るよ
うにしている。レジスタ８の出力データとレジス
タ９に貯えられているデータであつてゲート回路
１５を介されたものとが（mod.2）の加算回路１
６に供給され、この加算回路１６の加算出力を得
るようにしている。ゲート回路１５は、コントロ
ール信号CTL３によつて制御され、加算出力を
得るときにのみ、レジスタ９に貯えられているデ
ータを通過させて加算回路１６に供給する。 上述のこの発明の一実施例において、乗算動作
を行なうときには、反転制御回路４に供給される
コントロール信号CTL２が“０”とされて、こ
れが非反転動作を行なうようにされる。データバ
ス５から、まず８ビツトのデータα^jが供給され、
次に８ビツトのデータαⁱが供給される。したがつ
て、データαⁱが変換ROM１に供給され、その指
数データｉ及び検出信号DET_iがレジスタ６に貯
えられた状態において、レジスタ７には、指数デ
ータｊ及び検出信号DET_jが貯えられる。次に、
（CTL1＝“１”）とされて指数データｉ，ｊの加
算出力（ｉ＋ｊ）が加算回路２で形成される。更
に次のタイミングでこの加算出力（ｉ＋ｊ）及び
オアゲート１２の出力がレジスタ７に貯えられ
る。逆変換ROM３は、（ｉ＋ｊ）からα^i+jの出力
データを発生する。２つの入力データαⁱ，α^jの何
れもが０元でないときには、逆変換ROM３の出
力データα^i+jが出力OUT１に取り出される。他
方、αⁱ，α^jの一方が０元であるときには、逆変換
ROM３からαⁱ又はα^jの出力が現れるが、ゲート
回路１４に対して供給される検出信号によつて出
力ゲータは、強制的に０元となされる。 また、除算動作を行なうときには、コントロー
ル信号CTL２が“１”とされて変換ROM１で発
生した指数データが反転制御回路４を介すること
で、“０”と“１”とが反転される。つまり、
α^j／αⁱの除算は、α^jに対して逆元α^-iを乗ずること
であり、この逆元α^-iは、（αⁱ・α^-i＝α⁰＝１）とな
り、（−ｉ）は、１の補数即ち“０”と“１”と
が反転された関係のものである。したがつて、こ
れ以外の処理は、前述の乗算動作の場合と同様で
ある。勿論、反転制御回路４において、ｊを−ｊ
とすれば、αⁱ／α^jの除算出力が得られる。 除算においては、０元を扱うことができない。
即ちαⁱ／０或いは０／０は定義することができな
い。この実施例では、０元が入力されたことを検
出し、０元を演算した場合には、ゲート回路１４
によつて演算出力を強制的に０としている。除算
出力は、必らず０元でないので、０元が出力に現
れることは、異常であり、したがつて除算出力が
供給される他の回路では、０元でないことを確認
することによつて所定の動作を行なうことにな
る。 上述の一実施例の説明から理解されるように、
この発明に依れば、従来のように、多数のゲート
回路を組み合わせたものと異なり、対数変換して
ガロア体上の元の乗除算の演算を行なうガロア体
の演算回路であつて、夫々の指数に対しmod.（2^m
−１）の加算を行なう加算手段を、ガロア体GF
（2^m）に対応したｍビツトからなる夫々の信号が
供給されるフルアダーで構成するとともに、その
キヤリー出力をそのキヤリー入力に帰還させるこ
とでmod.（2^m−１）の加算演算を行なつており、
構成簡単にしてIC化に適したガロア体の演算回
路が実現できる。 また、この発明ではmod.（2^m−１）の加算回路
ｍビツトのフルアダーを１個用い（１ビツトのフ
ルアダーをｍ個用いてもよい）、そのキヤリー出
力Coを自己のキヤリー入力Ciに正帰還する構成
としており、このmod.（2^m−１）の加算回路の点
でも、より構成の簡略化を図ることができる。

【図面の簡単な説明】

第１図、第２図、第３図及び第４図の夫々は、
この発明に用いる元αⁱ、α^j同志の演算回路のいく
つかの例を示すブロツク図、第５図はこの発明の
一実施例のブロツク図である。 １，１Ａ，１Ｂは変換ROM、２は加算回路、
３は逆変換ROM、４は反転制御回路、４Ａ，４
Ｂ，４Ｃは反転回路である。

Claims (1)

1. 【特許請求の範囲】 １ ガロア体GF（2^m）上の元α^kに対し、その指数
   ｋを得る変換手段と、 この変換手段から出力される夫々の指数に対
   し、mod.（2^m−１）の加算を行なう加算手段と、 この加算手段から出力される指数ｌに対し、元
   α^lを得る逆変換手段とを備えるガロア体の演算回
   路において、 上記加算手段は、ガロア体GF（2^m）に対応した
   ｍビツトからなる夫々の信号が入力信号とされる
   とともに、そのキヤリー出力がそのキヤリー入力
   に帰還されるフルアダーにて構成されて、上記
   夫々の指数のmod.（2^m−１）の加算を行なうもの
   であることを特徴とするガロア体の演算回路。