JPS58219648A - ガロア体における除算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の技術分野〕 この発明は例えば光学式デジタルオーディオディスク（
ＤＡＤ　）再生装置等圧用いられるエラー訂正符号の復
号用に好適するガロア体における除算装置の改良に関す
る。

〔発明の技術的背景〕

周知のように、近時開発されている光学式ＤＡＤ再生装
置（特にはＣＤ：コンノ母りトディスク形）においては
、そのエラー訂正符号としてクロスインターリーブリー
ドソロモン符号（ＣＩＲＣ）を採用している。

すなわち、これは従来よシ知られている代表的なランダ
ムエラー訂正符号のうちで最もエラー訂正能力が高いも
のとして広範に定義されているＢＣＨ符号の一種である
リードソロモン符号を用いるものであるが、それにバー
ストエラーに対しても高い訂正能力を持たせるべくクロ
スインタリーブなる信号処理を伴わせるようにしたもの
である。

ところで、リードソロモン符号の復号つまりエラー訂正
はＢＣＩ（符号のそれと同様になすことができる。

今、符号長（ｎ）、情報シンがル（ｋ）個、検査シンゲ
ル（ｎ−ｋ）個からなるリードソロモン符号について、
その復号法を調べてみるものとする。但し、上記各シン
ボルは（ｍ）個の２進ピツトつｔ　Ｄ　２ｍ個の元を有
する有限体であるガロア体Ｇ　Ｆ　（２ｍ）の元である
。

そして、この場合（１）重エラー訂正リードソロモン符
号の生成多項式ｇ＜ｘ＞は、（α）をガロア体ＧＦ（２
ｎ１）の原始光として次の（１）式またｇ（ｘ）＝（ｘ
＋α）（ｘ＋α２）・・・（Ｘ＋α２ｔ）　　・・・（
１）ｇ（ｘ）　”　（ｘ＋α０）（ｘ＋α）・・・（Ｘ
＋α２ｊ−１）・・・（２）また、送信符号語をＣ（ｘ
）、受信符号語をＲ（Ｘ）で表わし、且つエラー多項式
をＥ（Ｘ）とすると、これらの間には次のような関係が
成立する。

”（Ｘ）　＝Ｃ（ｘ）　＋Ｅ（ｘ）　　　　　　　　　
”’　（３）この場合、多項式の係数はガロア体ＧＦ（
２ｔｙｌ）に含まれており、エラー多項式”（ｘ）はエ
ラーロケーシ璽ンおよび値（大きさ）Ｋ対応する項だけ
を含んでいる。

従って、位置ｘｊにおけるエラー値をＹ４とすると となシ、該（４）式でΣはエラーのすべての位置にわた
る総和を意味している。

ここで、シンドローム８隻を ８、＝Ｒ（αｉ）〔但し１＝０．１・・・２ｔ−１）　
　・・・（５）の如く定義したとすると、上記（３）式
よシｓ、　＝Ｃ（αｉ）’＋Ｅ（αｉ） となる。

この場合、Ｃ（え）は”（ｘ）で常に割シ切れるので Ｃ（α）＝０ であるから ｓ、＝ｇ（α） となる。そこで、上記（４）式より Ｓ−Ｆ：（αｌ）＝Σｙ、（α１）ｊ ｉ　　　　　　ｉ ＝ΣＹｊＸｊ　　　　　　　　　　　・・・（６）と表
わすことができる。但しαｊ＝Ｘｊとおいたもので、Ｘ
ｊはαｊにおけるエラーロケーシ璽ンを表わしている。

ここで、エラーロケーシ箇ｙ多項式σ（ｘ）は、エラー
数をｅとして ＝ｘｅ＋σ１ｘ　＋・・・＋σ、　　　　　・・・（７
）と定義される。

また、（７）式のσ、〜σ。はシンドロームＳｉとの間
で次のように関係付けられる。

・・・（８） ８に＋、十〇、Ｂｔ＋、−１＋・・・σ＠−１’１４１
＋σ、８ｉつまり、以上のようなリードソロモン符号の
復号手順は （Ｉ）　　（５）式によりシンドロームＳ１を計算する
。

（Ｉｆ）　　（８）式によシエラーロケーシーン多項式
の係数σ１〜σ。を計算する。

（ＩＩＤ（７）式ニよりエラーロケーシ■ン多項式の根
ｘｊを求める。

■　（６）式によりエラー値Ｙｊを求め、（４）式によ
りエラー多項式を求める。

Ｍ（３）式によりエラー訂正を行なう。

なる（１）〜（■の手順に帰着せしめられる。

次に、以上のような復号手順によるエラー訂正の具体例
として、１ブロツクデータに４個の検査シンプルを用い
た場合について説明する。

すなわち、この場合の生成多項式ｇ（ｘ）は１１　−−
（Ｘ＋１）（Ｘ＋α＞＜ｘ＋α２）（珪−）（ｘ） となり、２重エラーまでの訂正力！可能となるものであ
るが、ここではそれを（Ａ）＃（Ｂ）なる二つの方式に
よった場合について各ｙ４１に述べるものとする。

〔方式Ａ〕

（１）　　シンドロームＳ。〜Ｓ３を計算する。

ω）（８）式をｅ”１　ｅ　ｅ−””２について書き直
すと、ｅ＝１の場合には となる。また、ｅ＝２の場合には となる。

ここで、実際の復号器がｅ＝１の場合から動作を始める
ものとすると、先ず連立方程式（９）を満足する解σ、
を求めなければならなり０そして、この解が存在しなけ
れば、復号器は次に８＝２の場合について連立方程式α
１を満足する解σ、。

σ２を求めなければ表らない。なお、こむでも解が得ら
れない場合はｅ≧３と本なすことになる・（９）式の解
σ、は として求め、０１式の解σ１．σ２は として求める。

（２）　以上のようＫしてエラーロヶーシ冒ン多項式の
係数σ、が得られたならば、次に（７）式にょシエラー
ロケーシ帽ン多項式の根を求める。

先ず、ｅ＝１の場合は ａ（ｘ）＝ｘ＋ａ、＝Ｏｅ　　、’、Ｘ１＝σ１となる
。また、ｅ＝２の場合は σ（ｘ）””＋σ１ｘ＋σ２　＝　ｏ・＝　（ｉｌｌと
して、該（１心式にガロア体ｃｒ（２ｍ）の元を順次に
代入してその解を求めればよく、今この根をｘ、　、　
ｘ、とする。

勤　エラーロケーシ璽ン多項式の根が求まったなら、次
に（６）式によ、シェラ−値Ｙ、を求める。

先ず、ｅ＝１の場合は ５ｏ＝Ｙ、　　　、’、　Ｙ、　＝　８０となる。また
、ｄ＝２の場合は よシ ｙ２　＝　ｓ０＋ｙ。

（転）　上述のようＫして求めたエラー値Ｙ１　、Ｙ２
により訂正を行なう。

とむろ−て、Ｉインターイレージヤ−法等によっテｘ　
９−０ケージ「ンの値を正確に知ることができる場合に
は、上述した２重エラー訂正用のリードソロモン符号に
よって４重エラーまでの訂正が可能となるものであシ、
それが後述する〔方式Ｂ〕である。

〔方式Ｂ〕

（ｒ）　　シンドロームｓ０〜ｓｓを計算スる。

印）、（２）　エラーロヶーシ嘗ンを別の検出方法で知
る。

ＧＶ）　　（６）式によりエラー値を求める。

先ずｅ＝１　、ｅ＝２の場合は上述した〔方式Ａ〕の（
転）と同様である。

そして、ｅ＝３の場合 を解いて ｙ、＝ｓ０＋ｙ、＋ｙ２ となる。

また、６＝４の場合は を解騒て ｙ４＝　ｓ０＋ｙ１＋ｙ２＋ｙ。

となる。

関　上述のようにして求めたＹ、〜Ｙ４により訂正を行
なう。

第１図は以上のような原理、に基〈リードソロモン符号
の実際の復号システムでなるエラー訂正回路を示す概略
構成図である。すなわち、入力端（ＩＮ）を介して導か
れる被訂正用のデータ（エラー訂正用としてリードソロ
モン符号が用いられていることは勿論である）は部分さ
れて、一方が後述する復号動作の間データバッファ１１
に記憶されると共に１他方が復号動作をなすためのシン
ドローム計算器１２以下に導かれる。

そして、シンドローム計算器１２で［１−算されたシン
ドロームはシンドロームバッファ１３に記！される。

ここで、シンドロームバッファ１３の出力部に接続され
たオアゲート１４はエラーの有無を指示するもので、エ
ラーがあると前述したような手順によってエラー訂正動
作を開始することになる。

つマル、エラーロケーション多項式計算器１６がエラー
ロケーション多項式σ（Ｘ、）の係数を計算し、エラー
ロ冬ニジ胃ン計算器１６がエラーロケーション多項式の
根を計算し、エラー値計算器１１がエラー値を計算し、
これらのエラーロケ−シーンおよびエラー値により上記
データ・々ソファ１１から出力されるデータを訂正する
ものである。

ところで、このような復号システムの各計算器１２．１
５　＃　１６　ｅ　１７は０か否かの検出ならびに必要
な加算′２乗算および除算の代数演算をなすものである
が、これらについての具体例として従来第２図に示すよ
うに構成されたエラーロケーション多項式計算器（特公
昭５６−２０５７５号）が知られている。

すなわち、第２図において２１はシンドロームバッファ
であって、シンドロームｓ、　を記憶スるためのＲＡＭ
でなり、該シンドロームバッファ２１にはがロア体Ｇ　
Ｆ　（２ｍ　）の元である各シンドロームがそれぞれｍ
ビ、トの２進形式で記憶される。

また、２２は作業用バッファであって、エラーロケーシ
ョン多項式の係数を計算する際に、代数演算の中間結果
および最終結果を記憶するためのＲＡＭでな〕、後の演
算で使用される部分結果も骸作業用パ、ファ２２に記憶
される。

そして、２３は代数賃算の順序を指示する順序制御装置
であって、上記シンドロームバッファ２ノおよび作業用
バッファ２２に対してアドレスを供給して適切な記憶位
置をアクセスすると共に、実行され九代数演算結果を調
べて次の適切な演算へ分岐せしめるのに供せられる。

さらに、２４．２５はそれぞれガロア体ＧＦ（２”）の
元の対数および真数を各別にテーブルの形式で記憶して
いるＲＯＭでなる対数バッファおよび真数バッファであ
る。

ここで、前者の対数バッファ２４のアドレスは元α１の
２進表示であシ、そのエン）　リーはαを底とするαの
対数すなわち１であるが、後者の真数バッファ２５のア
ドレス１におけるエントリーはαの２進表示である。

例えばガロア体Ｇ　Ｆ　（２８）の法多項弐Ｆ（ｘ）を Ｆ（ｘ）−ｘ　＋　ｘ　　＋　ｘ　＋　ｘ　＋　１とす
ると、そのＯ以外の元はＦ（ｘ）＝０の根αのべき乗ま
たはα０〜α７までの線形結合で表わすことができる。

また、この場合ａ０〜ａ、までの８個の係数を取り出し
て２進ベクトルとして表わすこともできる。

例えば α１−０・α０＋１・α１＋０・α２＋０・α３＋０・
α４＋０・α５＋０・α６＋０・α７＝（ｏｌｏｏｏｏ
ｏｏ） α７＝０・α０＋・・・・・・・・・＋０・α６＋１・
α７＝（０００００００１） α８＝１＋α４＋α５＋α６ ＝（１０００１１１０） α９＝α・α８＝α＋α５＋α６＋α７＝（０１０００
１１１） の如くであ夛、これら以外の元も同様にしてベクトル表
示することができる。

そして、この場合対数テーブルのアドレス（１〜２５５
）は元α１の８ビツトの２進ベクトル表示であり、対応
するエン）　ＩＪは指数ｉの２進表示である。

また、真数テーブルは指数！をアドレスに用い、エンド
ＩＪはα１の２進ベクトル表示である。

次に、第２図のエラーロケーシ舊ン多項式計算器による
実際の代数演算を各別に説明する。

（１）加算 元α１およびαｊを加算する場合には、これら２つの元
がＡレジスタ２０およびＢレジスタ２６を介してエクス
クルシブオアｆ−）Ｊ７によシ各ピット毎に排他的な論
理和をとる。これによって得られる上記２つの元の和の
結果はＣレジスタ１９を介して上記作業用バッファ２２
に転送される。

（２）Ｏであるか否かの検出 元α１が０であるか否かを調べる場合には、元α１がＨ
レジスタ２８を介してオアｆ−）ｊｉ９によシ論理和が
とられる。この結果はＭレジスタ３０を介して上記作業
用バッファ２２に転送される。この場合、Ｍレジスタ３
０の内容は元α１が００ときのみ０になる。

（３）　　乗算 元α１およびα」を乗算する場合には、先ずこれら２つ
の元が０であるか否がが調べられる。

若し、いずれか一方の元が０であれば、実際に乗算する
までもなく、乗算結果は０である。しかるに、両方とも
０でない場合には、これらの元は上記対数バッファ２４
用のアドレスレジスタ３１ｔ／Ｃ順次にロードされる。

そして、対数バッファ２４からの出力ｌおよびｊはＤレ
ジスタ３２およびＥレジスタ３８を介して１の補数加算
器３４によＪ）、２８１を法として１の補数加算が行な
われる。これによって得られる結果（１＋　ｊ　＝ｔ　
ｍｏｄ（２８１））はＬレジスタ３５を介して上記真数
バッファ２５用のアドレスレジスタ３６にロードされる
。この場合、真数バッファ２５のアドレス入力がｔであ
れば、その出力α１が乗算結果としてＣレジスタ３７を
介して上記作業用・ぐ、７ア２２に転送される。

（４）除算 元αｊによるα　の除算（α’／Ｃｆｊ　）は基本的に
は上記（３）の乗算の場合と同様であるが、上記Ｅレジ
スタ３３の内容を上記Ｄレジスタ３２の内容から減算せ
しめる点で異なっている。つまり、Ｅレジスタ３３にあ
る元αｊの対数が補数化器３８によシ補数化されてＦレ
ジスタ３９を介して上記１の補数加算器３４に送るよう
にした点である。そして、以下（３）の乗算の場合と同
様に処理されるものであるが、この場合真数バッファ２
５の出力が求める除算の結果つｔｂ商となっているもの
である。

〔背景技術の問題点〕

しかしながら、以上のような従来のエラー訂正装置は、
そのエラーロケーシ嘗ン多項式計算゛器における代数演
算のうち乗算および除算用として対数ノ々ソファおよび
真数バッファを必要とするものであるが、このために用
いられるＲＯＭ等のメモリ容量が膨大なものになるので
、ＬＳＩ化が阻害されて大容量のメモリを外付けしなけ
ればならないという不具合を生じていた。

これは、前述した例の如く１シン？ル８ピットとし九場
合で２５５Ｘ８ビ、ト、、＝２０４０ビ、トのＲＯＭが
２つ必要になシ、合計４０８０ピツトにもなることから
して容易に窺い知れるところである。

つまり、従来より知られているガロア体における乗算装
置および除算装置はそれらの元の対数および真数を各別
にテーブルの形式で記憶している大容量メモリでなる対
数バッファや真数バッファを必要とするので、それだけ
構成が複雑化して高価格につくとｂう問題を有していた
。

〔発明の目的〕

そこで、この発明は以上のような点に鑑みてなされたも
ので、特に大容量のメモリを必要とする対数バッファや
真数バッファを用いることなくガロア体における除算を
なし得るようにし、以って構成の簡易化ならびに低価格
化に寄与し得るようにした極めて良好なるガロア体にお
ける除算装置を提供することを目的としている。

〔発明の概要〕

すなわち、この発明によるガロア体における除算装置は
、ガロア体における乗算装置が線形シフトレジスタを用
いて比較的簡単に構成し得るのを利用して、除数を逆数
に変換して被除数に乗算せしめる如くした乗算処理でガ
ロア体における除算がなし得るようＫしたもので、この
際に除数を逆数に変換する過程を可及的に小容量メモリ
で実現し得るように構成した点に特徴を有している。

〔発明の実施例〕

先ず、この発明が適用される光学式（ＣＤ形）デジタル
オーディオディスク（ＤＡＤ　）再生装置の概要につい
て説明する。

すなわち、第３図に示すようにディスクモータ１１１に
よって回転駆動されるターンテーブル１１２上に装着さ
れたディスク１１３は光学式ピックア、ｆｌ１４によっ
て再生される。との場合、光学式ビックア、！１１４は
半導体レーザ１１４＆からの出射光をビームスグリツタ
−１１４ｂ、対物Ｖ　７．ｅ　１１４　ｅを介しテティ
スク１１３の信号面に照射し、該ディスク１１３に所定
の（ＥＦＭ　）変調およびインタリーブを伴った形態で
記録されている再生すべきオーディオ信号のデジタル（
ＰＣＭ　）化データに対応したビット（反射率の異なる
凹凸）からの反射光を対物レンズ１１４ｅ、ビームスグ
リ、ター１１４ｂを介して４分割フォトデテクタ１１４
ｄに導き、該４分割フォトデテク！１１４ｄで光電変換
された４つの再生信号を外部に出力可能になされている
もので、自からはビ、クア、プ送シモータ１１５′に、
よってディスク１１３の半径方向に直線駆動される。

そして、４分割フォトデテ□クタ１１４ｄからの４つの
再生信号はマトリクス回路１１６に供給されて所定のマ
トリクス演算処理が施されることによシ、フォーカスエ
ラー信号（’Ｆ）、’）う、キングエラー信号および高
周波信号（ＲＦ）Ｋ分離される。

このうち、フォーカスエラー信号ＣＦ）はフォーカスサ
ーチ回路Ｉ　Ｊ　０−ｊｈらのフォーカスサーチ信号と
共に、前記光学式ピックアップ１１４のフォーカスサー
ゼ系（ＦＳ）を駆動するのに供せられる。

また、トラッキングエラー信号（Ｔ）は後述するシステ
ムコントローラ１１７を介して与えられるサーチ制御信
号と共に、前記光学式ピックアップ１１４のトラッキン
グサー♂系（Ｔ８）を駆動するのに且つ前記ピックアッ
プ送りモータ１１５を（リニアトラッキング）制御する
のに供せられる。

そして、残る高周波信号（ＲＦ）が主再生信号成分とし
て再生信号処理系１１８に供給される。

すなわち、この再生信号処理系１１８は先ず再生信号を
スライスレベル（アイパターン）検出器１１９によって
制御される波形整形回路１２０に導いて不要なアナログ
成分と必要とするデータ成分を分離し、データ成分のみ
をＰＬＬ型でなる同期クロック再生回路１２１および第
１の信号処理系１２２のエツジ検出器１２ハに供給する
。

ここで、同期クロック再生回路１２１からの同期クロッ
クはデータ復調用として第１の信号処理系１２２におけ
る同期信号分離用クロ、り生成回路１２２ｂに導かれて
同期信号分離用クロックを生成するのに供せられる。

一方、上記エッソ検出器１２２ａを通った再生信号は同
期信号検出器１２２ｃに導かれて上記同記信号分離用ク
ロックにより同期信号が分離されると共に、復調回路１
２２ｄに導かれて（ＥＦＭ）復調される。

このうち、同期信号は同期信号保護回路１２２ｅを介し
て誤動作が生じないように保護された状態で、上記同期
信号分離用クロックと共に入力データ処理用タイミング
信号生成回路１２２ｆに導かれる。

また、復調信号はデータパ〃ス入出力制御回路１２２ｇ
を介して後述する第２の信号処理系１２３０入出力制御
回路１２３ａに供給されると共に、そのうちのサグコー
ドであるコントロール信号および表示信号成分がコント
ロール表示処理回路１２２ｈおよびサブコード処理回路
１２２１そして、サブコード処理回路１２２１で必要な
エラー検出および訂正が施されたサブコードデータはシ
ステムコントローラ用インターフヱイｘ回路１２２ｇを
介してシステムコントローラ１１７に供給される。

ここで、システムコントローラ１１７はマイクロコンピ
ュータ、インタフェイス回路おヨヒドライバ用集積回路
等を有してな９、コントロールスイッチ１２４からの指
令信号によｐ　ｎＡＤ再生装置を所望の状態に制御する
と共に、上述のサブコード（例えば再生曲のインデック
ス情報）を表示器１２５に表示せしめるのに供せられて
いる。

なお、上記入力データ処理用タイミング信号生成回路１
２２ｆからのタイミング信号はデータセレクト回路１２
２ｊを介して上記データバス人出１ 力制御回路１２２ｇを制御するのに供せられると共に、
周波数検出器１２２におよび位相検出器１２２ｔならび
にＰＷＭ変調器１２２ｍを介して上記ディスクモータ１
１１金線速度一定（ＣＬＶ　）方式で駆動するための自
動周波数制御（ＡＦＣ）および自動位相制御（ＡＰＣ）
に供せられている。

この場合、位相検出器１２２ｔにはクリスタル発振器１
２２ｎからの発振信号に基いて動作するシステムクロッ
ク生成回路１２２ｐからのシステムクロックが供給され
ている。

そして、第２の信号処理回路１２３０入出力制御回路１
２３ａを通った復調データはエラー検出および訂正また
は補正用のシンドローム検出器１２３ｂ、エラーポイン
タ制御回路１２３ｅ、訂正回路１２３ｄおよびデータ出
力回路１２３ｅを介して必要なエラー訂正、デインタリ
ーブ、エラー補正等の処理を受けてデジタル−アナログ
（Ｄ／Ａ　）変換器１２６に導出される。

この場合、外部メモリ制御回路１２３ｆは上記データセ
レクト回路１２２ｊと共働して訂正に必要なデータが書
き込まれている外部メモリ１２７を制御することによシ
、上記入出力制御回路１２３ａを介して訂正に必要なデ
ータを取り込む如くなされている。

また、タイミングコントロール回路１２３ｇは前記シス
テムクロック生成回路１２２ｐからのシステムクロック
に基いてエラー訂正および補正ならびにＤ／Ａ変換に必
要なタイミングコントロール信号を供給する如くなされ
ている。

また、ミー−ティング（検出）制御回路１２３ｈは上記
エラーポインタ制御回路１２３ｃからの出力またはシス
テムコントローラ１１７を介して与えられるコントロー
ル信号に基いてエラー補正時およびＤＡＤ再生装置の動
作開始、終了時等に必要となる所定のミー−ティング制
御をなすのに供せられている。

そして、上記必変換器１２６でアナログ信号に戻された
オーディオ信号はローパスフィルタ１２８、増幅器１２
９を介してスピーカ１３０を奏鳴するのに供せられる。

次に、以上のようなりＡＤ再生装置のエラー訂正部に適
用されたこの発明に係るガロア体における除算装置の一
実施例につき図面を参照して詳細に説明する。

すなわち、第４図は第３図における第２の信号処理回路
１２３の訂正回路１２３ｄに主として含まれる前述した
ようなエラーロケーシ冒ン多項式計算器部を示している
もので、対数バッファや真数バッファを用いることなく
ガロア体における乗算および除算がなし得るようにした
乗算装置４１および除算装置４２を備えている以外は前
述した第２図のそれと同様である。つまり、エラー訂正
符号として採用されｆｃＢＣＨ符号の一種であｌ−ドソ
ロモン符号の復号（エラー訂正）のために各種の代数演
算をなすのがエラーロケ−シロン多項式計算器に与えら
れた役目であるが、このうち加算およびＯであるか否か
の検出については第２図のそれと同様になされるので同
一符号を付してその説明を省略するものとし、第２図の
それ七は異なる乗算および除算について以下に述べるも
のである。

先ず、ガロア体における乗”算についてみてみるに、例
えばガロア体ＧＦ（２）の元α１とαｊとの乗算（Ｃ１
・αｊ、但しαは法多項式 ％式％ と表わした場合（但し、ｅ□〜ｃ７ｒｄ６〜ｄ７は０ま
たは１とする） Ｃ１・αｊ−Ｃ（αルＤ（α） ＝ｄ、α７　ｃ　（α）＋ｄ６αＡ　ｃ　（α）・・・
・・・・・・ｄｏＣ（α）−Ｃ６〔αａ、Ｃ（α）＋ｄ
６Ｃ（α）〕十ｄ５α５　ｃ　（α）＋・＝・・＋ｄｏ
Ｃ（α）＝　Ｃ５〔α〔αｄ、Ｃ（α）＋ｄ６Ｃ（α）
〕十ｄ５Ｃ（α）〕十ｄ４α４　ｃ　（α）←・・＋ｄ
ｏＣ（α） 二〔α〔α〔α〔α〔α〔α（Ｃ４１，ｃ（α）＋ｄ６
Ｃ（α））＋ｄ５Ｃ（α）〕＋ｄ４Ｃ（α）〕十ｄ３Ｃ
（α）〕＋ｄ２Ｃ（α）〕＋ｄ１Ｃ（α）＋ｄｏＣ（α
）〕となる。

つまり、このようなガロア体ＧＦ（２）の冗αとαｊと
の乗算は線形シフトレジスタを用いて第５図に示したよ
うに構成される乗算装置で実現し得ることを物語ってい
る。

すなわち、第５図において（ＡＮＤ、）〜（ＡＮＤ、）
は各一端に上記乗数Ｄ（α）の係数であるｄ。〜ｄ７が
上位ビットから順にシリアルに供給されると共に、各他
端に上記被乗数Ｃ（α）の係数であるＣ８〜ｃ７が上位
ビットから順にパラレルに供給されるアンドｒ−）であ
る。また、ＦＦ０〜ＦＦ、は、上記各アンドｒ　−）　
（ＡＮＤ。）　〜（ＡＮＤ、）からの出力が入力一端に
対応して供給されるエクスクルシブオアダート（ＥＸ−
ＯＲ８）〜（ＥＸ−ＯＲ７）を介して縦続的に接続され
ると共に帰還接続されることにより線形シフトレジスタ
（ＳＲＯ）を構成するフリラグフロッグ回路である。

この場合、４段目と５段目、５段目と６段目および６段
目と７段目のフリラグフロッグ回路（ＦＦ、）−（ＦＦ
４）　、　（ＦＦ４）−（ＦＦ５）　、　（ＦＦ５）−
（ＦＦ、）との股間は各一端が帰還路に接続されたエク
スクルシブオアｆｆ　−）　（ＥＸ−ＯＲ４’　）　、
　（ＥＸ−ＯＲ５’　）　。

（Ｅｘ−ｏＲ６’　）がさらに介挿された状態で結合さ
れている。また、各７リツプフロツプ回路（Ｆ’ＦＯ）
〜（ＦＦ、）のクロック入力端（ＣＫ）には図示しない
クロック発生器からのクロックツ９ルス（ｃｐ）がノ９
ラレルに供給される如くなされている。

つｔシ、Ｃ（α）の係数（Ｃ０）〜（Ｃ７）がビットシ
リアルに入力されることによシ、先ず（Ｘｏ）が計算さ
れ、その後Ｘ１．Ｘ２・・・と続いて８ビツト入力終了
時に線形シフトレジスタ（ＳＲｏ）にはＸ７すなわちＣ
（α）・Ｄ（α）が実現されるもので、各７リツプ７０
ツノ回路（ＦＦｏ）〜（ＦＦ、）の出力（ＸＯｒｌｌ・
・・ｘ７）が乗算結果を与えることになる。

ここで、Ｘｏ〜Ｘ７は次の通シである。

Ｘｏ−ｄ７Ｃ（α） ＸにａＸｏ＋ｄ６Ｃ（α） Ｘ２−αＸ１＋ｄ５Ｃ（α） ｘ、＝αＸ２七ｄ４Ｃ（α） Ｘ４＝αｘ、　＋　ａ、ｃ（α） Ｘ５＝αＸ４＋ｄ２Ｃ（α） Ｘ６−αＸ５＋ｄ１Ｃ（α） ｘ、　＝αＸ６　＋　ａａｃ（α）”’　（３Ｅｏ　＋
　”１　”’　”７　）そして、以上のようなガロア体
ＧＦ（２）における乗算装置はガロア体ＧＦ（２８）の
元の対数および真数をテーブルの形式で記憶するＲＯＭ
等の大容量メモリでなる対数バッファや真数バッファを
用いることなく、単に線形シフトレジスタを用いるだけ
でなし得るので、その構成を簡易で安価なものとするこ
とができるという効用を有している。

次に、ガロア体における除算についてみてみ−るに、例
えばガロアＧＦ（２８）の元α１とα」との除算α１÷
αｊ（但しαは法多項式 Ｆ（ｘ）＝ｘ＋ｘ　＋ｘ　＋ｘ　＋１の根とする）は除
数αｊを逆数α−ｊに変換してα１・（α−りなる乗算
処理でなせることになる。

ここで、乗算処理については前述したような線形シフト
レジスタによる乗算装置を用いてなすことは言う迄もな
い。

ところで、この場合除数αｊの逆数α−ｊを得るために
、単純にはαｊを入力するとその逆数α−ｊ＝α２５５
−ｊを出力する如くしたＲｏｇ等でなる変換器を用いる
ことが考えられるが、若しその通りにしたとするとα１
からα２５５までの元に対応するα−１カラα−２５５
までの変換テーブルが必要とな択実際には８Ｘ２５５＝
２０４０ピツトのデコーダと同じ（８Ｘ２５５＝２０４
０ビツトのエンコーダつまりは合計で４０８０ビツトの
大容量のＲＯＭ等が必要となってしオうので好ましくな
い。

そこで、この発明ではガロア体ＧＦ（２”）における２
ｍ個の元をｎ分割し、各分割毎の特定の位置の元の逆数
データのみをテーブルの形式で変換器に記憶しておき、
該変換テーブルにない中間の元の場合には適数口Ｎのシ
フト動作によってその元に対する逆数データを得ること
ができるようにしようとするもので、これによれば変換
テーブルを記憶するＲＯＭ等のメモリ容量を１に削減し
得る。

第６図は以上のようにしてガロア体における除算を乗算
処理で実現する除算装置の構成を示すもので、図中５１
は上述した如くα〜α　をｎ分割し、各分割毎の特定の
位置（例えば１番目）の元α１が入力されるとそれの逆
数であるα２５５−ｘ’を出力するように記憶されたＲ
ＯＭ等のデコーダ５１１およびエンコーダ５１２を含ん
でなる変換器であるが、ここでは該変換器５１にｎ＝３
２として一番目をα１とした場合として元α８１（＋１
　（但しに＝０　、１　、２・・・・・・３１）につい
ての逆数変換テーブルが記憶されているものとする。

次表は、上記変換テーブルの内容を示すもので、アドレ
スは元α８に＋１の２進表示であり、そのエントリーは
α２５５−（８に＋１　）の２進表示である。

１　０１００００００　　　　２５４　０００１１１０
１９　０１０００１１１　　　　２４６　０１００１１
００１７　１１１０１００１　　　　２３８　１０００
１１１１２５　１０００１０１１　　　２３０　１００
１１１０１３３　０１１１１０１０　　　　２２２　０
１１０１０１０４１　０１０００１０１　　　　２１４
　０１０００１１０４９　１１１１００１０　　　　２
０６　０１０１１１０１５７　１０１００１１１　　　
　１９８　０１０１１１１１６５　１０００１１０１　
　　　１９０　０１１００１０１７３　０１０１０１１
１　　　　１８２　１１１１１１０１８１　００１１０
００１　　　　１７４　１１１１１１１０８９　１１１
１０１１０　　　１６６　１１０１１００１９７　１０
０１０００１　　　　１５８　００００１１０１１０５
　１１０１０１０１　　　１５０　１００００００１１
１３　１０１００１００　　　１４２　００１１１０１
１１２１　０００１０１０１　　　１３４　１００００
１０１１２９　０１１０１１０１　　　　１２６　０１
００１１１１１３７　００１１００１１　　　１１８　
１０１０１０００１４５　１１１０１１０１　　　１１
０　０１００１００１１５３　１０１１１１０１　　　
１０２　１１１００１１０１６１　００１０００１０　
　　　９４　１１１１１１００１６９　１０１１０１１
０　　　　８６　１１１０００１１１７７　１１０１０
１１０　　　　７８　１００１０１０１１８５　００１
１１１００　　　　７０　１０００００１０１９３　０
０１０１１１１　　　　６２　０００１１１００２０１
　０１１０１１１１　　　　　５４　０１０１０００１
２０９　００１０１０００　　　　４６　１１００００
１１２１７　１１０００００１　　　　３８　０００１
００１０２２５　０１００１０１０　　　　３０　１１
１１０１１１２４９　１００００１１１　　　　　６　
００００００１０なお、変換器５１は上表にある元α８
に＋１がアドレスされた場合は、それに対応する逆数デ
ータを出力するが、上表にない元がアドレスされた場合
の出力はＯとなる。

また、第６図において５２．５３はそれぞれ第５図の線
形シフトレジスタ（８Ｒｏ）と同様に構成された線形シ
フトレジスタであって、それぞれ被除数α１データおよ
び除数αｊデータがセットされる。但しαｌ、αｊは α量＝ａ６＋ａ１α＋・・・・・・十邑７α　（ａθ〜
ａ７＝＝０または１）α’＝ｂｏ＋ｂ１α＋、、、　、
、・十ｂ　、α’　（ｂｏ−ｂ７＝ｏｔたは１）のよう
に表わされるものとする。

そして上記シフトレジスタ５２の出力は乗算器６４０乗
数入力端側に供給され、且つシフトレジスタ５３の出力
は前記変換器５１のデコーダ６１１入力端に供給されて
いる。また、変換器５１のエンコーダ５１２出力側から
の出力は上記乗算器５４の被乗数入力“側に供給される
と共に、ノアｆ　−）　（ＮＯＲ１）の入力側圧供給さ
れている。このノア？　−）　（ＮＯＲ１）の出力はり
四、り（ＡＮＤ＋ｏ）を介して上記シフトレジスタ５２
．５３を制御するコントロールクロック（Ｓ−ＣＫ）を
得るのに供せられる。

なお、乗算器５４は第５図に示【７た乗算装置と同様に
構成されているものとする。

而して、以上の構成においてα１÷αｊの実行動作は、
シフトレジスタ５３にセットされた除数αｊデータが変
換器５１に記憶されている変換チーゾルにある場合には
、該変換器５１から出力されるそれの逆数データα−ｊ
を乗算器５４に被乗数データとしてそのｔ″！！供給同
じく該乗算器５４にシフトレジスタ５２を介して供給さ
れる被除数αデータつまシ乗数データα魚との乗算（Ｃ
１・α−ｊ）処理が直ちになされることによって遂行さ
れる。

また、除数αｊデータが変換器５１の変換テーブルにな
い場合にｉ、該αｊにαを何回か（但し最高ｍ回、Ｏ≦
ｍ≦７）乗じて行く過程で（α３４ｍ）がＣ８に＋１の
いずれかに一致することを利用してα−（ｊ＋ｍ）なる
逆数データを得るもので、この場合被除数αデータ側に
も予めＣ１を乗じてαｆ”＋ｍとしておけば、乗算器５
４による乗算結果はα１＋ｍ、α−（ｊ＋ｍ）＝αｉ−
ｊ となって、変換器５１にＣ１からα２５５までの全ての
変換テーブルを記憶しておかなくても所期の除算をなす
ことができる。

この場合、Ｃ１，αｊにＣ１を乗じることは線形シフト
レジスタ５２．５３をそれぞれｍ回シフトすることによ
って容易に実現することができる。つまり、線形シフト
レジスタ５２　＃　５３に対するコントロールクロック
は前述したようにノアゲート（ＮＯＲ１）の出力とクロ
ック・やヤス（Ｃ２）との論理積をとるアンドグー）　
（ＡＮＤｌｏ）の出力として、変換器５１に入力される
除数データαｊがＣ８に＋１に一致しない限ジノアダー
）　（ＮＯＲ，）の出力が１”となってクロックツやヤ
ス（Ｃ１）の通過を許容することＫよって得られるもの
で、これによってシフトレジスタ５．？＃５Ｊが適数（
ｍ）ロシフトされ、その度にセットされたα。

αｊに対してαを乗じることになるかもである。

次に、具体例としてα　τα　を実行する場合について
述べると、シフトレジスタ５２にはα”＝（１０１１０
０００）がセットされ且つシフトレジスタ５３にはα　
−（０００１１０１１）がセットされる。し、かるに、
変換器５１にはα　の逆数デー・夕がないので、シフト
レジスタｓ２．６３に対する７フト動炸がなされること
になるが、この場合３回シフトしてシフトレジスタ（Ｓ
Ｒ２）がα”＝（１１１０１００１）になった時点で変
換器５１の入力がＣ８に＋１に一致することになって変
換器５１の出力はα２５５−（８に＋１　）＝α２５５
−１７＝α２３８＝（１０００１１１１）となる。一方
、シフトレジスタ５２の出力も３回シフトされて α２５＝（０００１０１１０）となっている。そして、
これらのα　とα　　とが入力される乗算器５４０乗算
結果はα’＝（００００００１０）となシ、除算α２°
÷α１４が実現されたことになる。

第７図はかかるα２０÷α１４の除算を実行する場合の
タイミングチャートを示すもので、（ａ）はα　とα　
とをセットするセットパルス、（ｂ）はクロック／ＩＦ
　Ａ、　ス（ＣＰ）、（ｃ）はノアｅ　−）　（ＮＯＲ
１）の出力、（ｄ）はコントロールクロック（８−ＣＫ
）　、（・）。

（ｆ）はそれぞれシフトレジスタ５２．５３の内容、（
ｇ）は乗算動作である。

そして、以上のようなガロア体ＧＦ（２”）　Ｋおける
除算装置はガロア体ＧＦ（２”）の元の対数および真数
をテーブルの形式で記憶するＲＯＭ等の大容量メモリで
なる対数バッファや真数バッファを用いることなく、除
数を逆数に変換して被除数に乗算せしめる如く乗算処理
でなせるようにしたもので、この際に除数を逆数に変換
する過程を可及的に小容量メモリで実現し得るという効
用を有している。

なお、この発明は上記し且つ図示した実施例のみに限定
されることなく、この発明の要旨を逸脱しない範囲で種
々の変形や適用が可能であることは言う迄もない。“ 例えば、テーグＰＣＭ等のデジタル化された情報の伝送
や記録再生システム、計算機システム等でガロア体によ
る代数演算を必要とする機器に好適するものである。

〔発明の効果〕

従って、以上詳述したようにこの発明によれば、大容量
のメモリを必要とする対数バッファや真数バッファを用
いることなくガロア体における除算をなし得るようにし
、以って構成の簡易化ならびに低価格化に寄与し得るよ
うにした極めて良好なるガロア体における除算装置を提
供することが可能となる。

【図面の簡単な説明】

第１図はリードソロモン符号の復号システムを示す概略
構成図、第２図は従来のエラーロケーション多項式計算
器を示す構成図、第３図はこの発明が適用されるＤＡＤ
再生装置の概要を示す構成図、第４図はこの発明の一実
施例を示す構成図、第５図は第４図の乗算装置部の具体
例を示す構成図、第６図は第４図の除算装置部の、具体
例を示す構成図、第７図は第４図の動作の具体例を説明
するためのタイミングチャートである。 ５１・・・変換器、５２．５３・・・線形シフトレジス
タ、５４−・・乗算器、Ｎ０Ｒ１−／　７１”　−）　
、ＡＮＤｌ。 ・・・アンピケ９−ト。 出願人代理人　弁理士　鈴　江　武　彦第１図

Claims (1)

【特許請求の範囲】
1. ガロア体ＧＦ（２ｍ）における２ｍ個の元のうちの２個
   の元α１．α」（但しαは法多項弐Ｆ（ｘ）の根）の一
   方の元α１が被除数データとして且つ他方の元αｊが除
   数データとして各別にセットされる第１および第２の線
   形シストレジスタと、前記２ｍ個の元をｎ分割して各分
   割毎の特定の位置の元の逆数データをテーブルの形式で
   記憶している変換器と、前記第２の線形シフトレジスタ
   にセットされた元αｊなる除数データの逆数データが前
   記変換器に記憶されているか否か判別してそれが記憶さ
   れている状態では当該逆数データを変換器から出力せし
   め且つ記憶されていない状態では第２の線形シフトレジ
   スタからの出力が変換器に記憶されているいずれかの元
   の逆数データに一致するまでの所定回数Ｎ（最高ｍ回）
   だけ前記第１および第２の線形シフトレジスタを共にシ
   フトせしめる手段と、前記第１の線形シフトレジスタか
   らの元α１また杜αｌ＋Ｎなる被除数データが被乗数デ
   ータとして且つ前記交換器からの元αｊまたはαｊ＋Ｎ
   なる除数データの逆数データα−ｊまたはα−（ｊ＋Ｎ
   ）が乗数データとしてセットされる線形シフトレジスタ
   を含んでなる乗算器とを具備してなることを特徴とする
   ガロア体における除算装置。