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

Abstract

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

Description

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

〔発明の技術的背景〕

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

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

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

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

そして、この場合（１）重エラー訂正リードソロモン符
号の生成多項式Ｐ（ｘ）は、＠）をガロア体ＧＦ（ｆ′
）の原始光として次の（１）式または（２）式のように
表わされる。

Ｐ（ｘ）＝（ｘ＋α）（ｘ＋α２）・・・・・・（χ＋
α２ｔ）　　・・・・・・・・・（１）Ｐ（Ｘ）＝（ｘ
＋α０）（ｘ＋α）　−（ｘ＋α”−’）　　・・−・
−・・・−（２）また、送信符号語をＣ（Ｘ）、受信符
号語をＲ（Ｘ）で表わし、且つエラー多項式をＥ（Ｘ）
とすると、これらの間には次のような関係が成立する。

Ｒ（Ｘ）”Ｃ（Ｘ）十Ｅ（Ｘ）　　　　　””””””
””””””””””””（３）この場合、多項式の係
数はガロア体ＧＦ（２”）に含まれており、工２−多項
式Ｅ（Ｘ）はエラーロケーシ冒ンおよび値（大きさ）に
対応する項だけを含んでいる。

従って、位置ｘｊにおけるエラー値をＹｊとすると わたる総和を意味している。

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

この場合、Ｃ（Ｘ）はＰ　（ｘ）で常に割り切れるので
Ｃ（α　）＝０ であるから Ｓ、−Ｅ（α） となる。そこで、上記（４）式よシ ５−Ｅ（ａｔ）−￥Ｙｊ（ａｔ）ｊ＝￥ＹｊＸｊ１　°
°゛°°゛゛（６）一 と表わすことができる。但しαｊ＝Ｘｊ　とおいたもの
で、Ｘｊはαｊにおけるエラーロケーシ璽ンを聚わして
いる。

ここで、工２−ロケーション多項弐〇（、）は、エラー
数をｅとして と定義される。

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

Ｓ、＋８＋σ西＋。−＋　＋＝−＝・・σ。−１”ｌ＋
４＋σｅＳｌ　　　・・・・・・・・・（８）つまり、
以上のようなリードソロモン符号の復号手順は （１）　　（５）式によりシンドロームＳ、を計算する
。

（ＩＩ）　　（８）式によりエラー四ケージ日ン多項式
の係数σ、〜σ。を計算する。

０１１）　’　（７）式によシェラ−ロケーション多項
式の根Ｘ、を求める。

（ＩＶ）　　（６）式によりエラー値Ｙｊを求め、（４
）式によシェラ−多項式を求める。

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

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

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

すなわち、この場合の生成多項式’　（ｘ）はＰ　（ｘ
）＝（ｘ＋１　）　（ｘ＋α）（ｘ＋α２）（ｘ＋α５
）とな９．２重エラーまでの訂正が可能となるものであ
るが、ここではそれを（Ａ）、（Ｂ）なる二つの方式に
よった場合について各別に述べるものとする。

〔方式Ａ〕

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

（ＩＩ）　　（ｓ）式をｅ＝　１　＊　ｅ　＝　２にツ
いテ書キ直スト、ｅ＝１の場合には となる。またｅ＝２の場合には となる。

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

σ２を求めなければならない。なお、ここでも解が得ら
れない場合はｅ≧３とみなすことになる。

として求め、＜１０式の解σ４．σ２はとして求める。

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

先ず、ｅ＝１の場合は σ（、）””＋０１＝０＋　　、’−Ｘ１＝σ。

となる。また、８＝２の場合は σ（Ｘ）＝　ｘ　　＋　ａ、ｘ　＋　ｃｔ２＝　０　　
　・−−−・曲・閉曲（１１）として、該（１１）式に
ガロア体ＧＦ（２”）の元を順次に代入してその解を求
めればよく、今この根をＸ、。

Ｘ２とする。

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

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

（Ｖ）　　上述のようにして求めたエラー値Ｙ１゜Ｙ２
によシ訂正を行なう。

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

〔方式Ｂ〕 ＜１）　　シンドロームＳ。−８３を計算す・る。

（Ｉｔ）（ト）　エラーロケーシランを別の検出方法で
知る。

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

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

そして、ｅ＝３の場合 を解いて Ｙ３工Ｓ。＋Ｙ、＋Ｙ２ となる。

また、ｅ＝４の場合は を解いて となる。

（Ｖ）　　上述のようにして求めたＹ１〜Ｙ４により訂
正を行なう。

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

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

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

つまり、エラーロケーション多項式計算器１５１１ がエラーロケーシＨン多項弐〇（、）の係数を計算シ、
エラーロケーシロン計算器１６力エラーロケーシ目ン多
項式の根を計算し、エラー値計算器１７がエラー値を計
算し、これらのエラーロケ−シランおよびエラー値によ
り上記データバッファ１１から出力されるデータを訂正
するものである。

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

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

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

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

サラニ、２４　、　ｘ　５　バー１ｔソｈｉ　ａ　ｙ体
ａｒｒ（ｆ’）の元の対数および真数を各別にテーブル
の形式で記憶しているＲＯＭでなる対数バッファおよび
真数バッファである。

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

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

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

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

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

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

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

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

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

（３）　　乗算 元α１およびαｊを乗算する場合には、先ずこれら２つ
の元が０であるか否かが調べられる。若し、いずれか一
方の元が０であれば、実際に乗算するまでもなく、乗算
結果は０である。しかるに、両方とも０でない場合には
、これらの元は上記対数バッファ２４用のアドレスレジ
スタ３ノに順次にロードされる。そして、対数パ。

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

ファ２２に転送される。

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

〔背景技術の問題点〕

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

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

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

〔発明の目的〕

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

〔発明の概要〕

すな゛わち、この発明によるガロア体における除算装置
はガロア体ＧＦ（２”）における２ｒｎ個の元のうちの
２個の元α１．αｊ（但しαは法多項弐Ｆ　（Ｘ）の根
）間の除算α１÷αｊをα１・α′÷αｊ・αＭ（但し
Ｍは整数）なる第１の乗算〔α１・α”〕および第２の
乗算〔αｊ・α町の商の形に変換し、前記第２の乗算が
αｊ・α１α２”−１＝α０＝１なることを利用して結
果的にα１÷α」＝α１・α”なる乗算に変換して処理
するもので、前記元αｊが被除数データとして直接ある
いは適数個のαＮ１．α１・・・・・・乗算回路（但し
Ｎｌ　＊　Ｎ意・・・・・・は１≦Ｎｔ（Ｎｌ・・・・
・・）を介してそれぞれ毎にセットされると共に１シフ
ト毎にそれぞれαＮ６　＜但しＮ、は１（Ｎｏ　）を乗
算する形式になされた第１の線形シフトレジスタ群と、
前記元αが除数データとして直接あるいは適数個のα　
。

α１・・・・・・乗算回路を介してそれぞれ毎にセット
されると共に１シフト毎にそれぞれα　を乗算する形式
になされた第２の線形シフトレジスタ群と、前記第１の
線形シフトレジスタ群の各レジスタ毎の１出力を検出す
るｌ検出回路群と、この１検出回路群のいずれかで１出
力が検出されるまでの適数口だけ前記第１および第２の
線形シフトレジスタ群を共にシフトせしめる第１の手段
と、前記第２の線形シフトレジスタ群の各レジスタ毎の
出力と前記１検出回路群の各検出回路毎の出力とのアン
ドをとってアンドがとられたレジスタ出力を導出する第
２の手段とを具備してなることを特徴としている。

〔発明の実施例〕

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

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

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

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

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

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

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

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

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

また、復調信号はデータパース入出力制御回路１２２ｇ
を介して後述する第２の信号処理系１２３の入出力制御
回路１２３ａに供給されると共に、そのうちのサブコー
ドであるコントロール信号および表示信号成分がコント
ロール表示処理回路１２２ｈおよびサブコード処理回路
１２２１に導かれる。

そして、サブコード処理回路１２２１で必要なエラー検
出および訂正が施されたサラコードデータはシステムコ
ントローラ用インターフェイス回路１２２ｑを介してシ
ステムコントローラ１１７に供給される。

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

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

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

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

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

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

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

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

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

すなわち、第４図は第３図における第２の信号処理回路
１２３の訂正回路１２３ｄに主として含まれる前述した
よりなエラーロケ−シラン多項式計算器部を示している
もので、対数パ。

ノアや真数バッファを用いることなくガロア体における
乗算および除算がなし得るようにした乗算装置４ノおよ
び除算装置４２を備えている以外は前述した第２図のそ
れと同様である。つまり、エラー訂正符号として採用さ
れたＢＣＨ符号の一種であるリードソロモン符号の復号
（二　゛ラー訂正）のために各種の代数演算をなすのが
エラーロケ−シロン多項式計算器に与えられた役目であ
るが、このうち加算および０であるか、・、′・、。

否かの検出については第２図のそれと同様になされるの
で同一符号を付してその説明を省略するものとし、第２
図のそれとは異なる乗算および除算について以下に述べ
るものである。

先ず、ガロア体における乗興についてみてみるに、例え
ばガロア体ＧＦ（２８）の元α１とαｊとの乗算（Ｃ１
・αｊ、但しαは法多項弐Ｆ（Ｘ）”　Ｘ８＋Ｘ’＋Ｘ
’＋Ｘ’＋１の根である）は α１＝Ｃ（α）＝ｃ　ｏ　＋　ｅ　ｓα＋・・・・・・
・”　ｅ７α勺αＪ　＝　Ｄ＠＝　ｄｏ＋ｄ　、α十曲
・・・・・ｄ７α７と表わした場合（但し、ｅｇ　”’
−Ｃ７１ｄｏ””　Ｃ７は０または１とする） Ｃ１・αｊ＝ｃ＠・Ｄ（ロ） ＝ｄ、α’ｃ＠＋ａ６α’Ｃ＠・−−−−−−−・ａｏ
ｃ（α）＝α’　（ｃｘａ、ｃ（ａ）十ｄ６ｃ（ａ））
　＋ａ５α５Ｃ（（１）十・・−田＋ｄ　ｏに（（ＩＣ
）＝α５唾［’４ｄ　、Ｃ（Ｃｆ）＋　ｄ６Ｃ（ロ））
＋ｄ５Ｃ＠）＋ｄ４α４Ｃ（ロ）十曲面・・・・・・・
＋ｄｏＣ（ψ 暑 一昨〔α〔α〔α〔α〔α〔αｄ、Ｃ（ψ＋ｄ６Ｃ（財
））−１−ｄ５ｃ（ψ〕＋ｄ４Ｃ＠）＋ｄ、Ｃ＠）　＋
　ｄ２Ｃ（Ｑ）：）＋ｄ、Ｃ（（Ｉり）＋ｄ。Ｃ（（１
））となる。

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

すなわち、第５図においてＡＮＤ　ｏ　＝　ＡＮＤ　ｙ
は各一端に上記乗数Ｄ＠の係数であるｄ。−Ｃ７が上位
ビ。

トから順にシリアルに供給されると共に、各他端に上記
被乗数Ｃ（（１）の係数であるＣ３−Ｃ７が上位ビット
から順にパラレルに供給されるアンドゲートである。ま
た、ＦＦｏ＝ＦＦγは、上記各アンドグー’　トＡＮＤ
　ｏ　−ＡＮＤ　ｖからの出力が入力一端に対応して供
給されるエクスクルシブオアゲート（ＥＸ−ＯＲｏ　）
　〜（ＥＸ−ＯＲ？　）を介して縦続的に接続されると
共に帰還接続されることにより線形シフトレジスタＳＲ
ｏを構成するフリラグフロップ回路である。

この場合、４段目と５段目、５段目と６段目および６段
目と７段目のフリ、プフロ、プ回路ＦＦｓ　−ＦＦａ　
＋　ＦＦａ　−ＦＦｓ　ｒ　ＦＦ　ＩＩ−ＦＦγとの段
間は各一端が帰還路に接続されたエクスクルシブオアゲ
ートＥＸ−ＯＲ４＋　ＥＸ−ＯＲｓ’　、　ＥＸ−ＯＲ
？’がさらに介挿された状態で結合されている。また、
各７リツプフロツゾ回路ＦＦ、　−ＦＦ、のクロック入
力端ＣＫには図示しないクロック発生器からのクロック
がパラレルに供給される如くなされている。

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

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

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

次に、ガロア体における除算についてみてみるに、例え
はガロア体ＧＦ（２８）の元α１とαｊとの除算α１÷
αｊ（但しαは法多項弐Ｆ（Ｘ）＝　ｘ８＋ｘ’＋ｘ５
＋ｘ　＋１の根とする）は α１÷αｊ＝（α１・αＭ）÷（αｊ・αＭ）と同値で
ある（但し、Ｍは整数）。

この場合、αｊ・αゝ＝α２５５＝α０＝１ならばα１
÷α」＝α１ｅα′ となる。

つまり、ガロア体ＧＦ（２８）の元α１とα」との除算
（α′−！−ａｊ）をなす場合、被除数α、除数αｊに
それぞれαを何回か乗じて行く過程で、Ｍ回αを乗じた
ときにαｊ・α“＝１になったとすれば、そのときにお
ける被除数α１とα１との積であるα１・α′が除算結
果であることに外ならないことを利用して、乗算処理で
所期の除算をなせることになる。

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

ところで、この場合αｊ・α′＝α２５５＝α０＝１を
得　　。

るために必要となるαを乗じる回数は、除数αｊｌ　　
のときに最高で２５４回（つま、９Ｍ＝２５４）となる
が、単純にその通りになせるようにしたのでは乗算処理
に要する時間が徒らに長時間化してしまうので好ましく
ない。

そこで、この発明では被除数αｊ、除数α」に対し予め
適数Ｎ回だけαを乗じておくことにより、実際に必要と
なるαを乗じる回数を低減して短時間で乗算処理（延い
ては除算処理）がなせるようにしようとするものである
。

第６図は以上のようにガロア体における除算を乗算処理
で実現する除算装置の構成を示すもので、この場合上述
の（６）としてＮ１＝１１Ｎｍ＝２、Ｎ５＝３つまシα
１．α２．α５を予め乗じ仝と共に、Ｎｏ＝４つま５１
回毎にα４を乗じるようにしたものである。

すなわち、除数αｊデータは直接あるいはα１乗算回路
５１、α乗算回路５２、α　乗算回路５３を介してα４
乗算回路を構成する線形シフトレジスタＡＩ　　＋　Ａ
ｍ　　＋　Ａｓ　　ｌ　Ａ４にセットされる。

ここで、線形シフトレジスタＡｌ　　ｌＡｍ　　＋Ａｌ
ｌ＋Ａ４は第７図に示すように７リツグフロ、プ回路Ｆ
ｌ’１Ｂ−ＦＦｔｙをエクスクルシブオアゲートＥＸ−
ＯＲｓｏ−ＥＸ−ＯＲｍｘを介して適宜縦続的に且つ憚
還的に接続して構成されるもので、アンドグー）　ＡＮ
Ｄｔｏを介して与えられるクロ、クパヤスＣｐによシシ
フトされ、ｌシフト毎にα４が乗算される如くしたα４
乗算機能を有している。

そして、シフトレジスタＡＩ　　＋　Ａｍ　　＋　Ａｍ
　　＊Ａ４の各出力が供給されるｌ検出回路５４゜５５
．５６．５７は第７図に示したようにインパーク１１０
と８人カッアゲ−）ＮＯＲｔｅによって構成されている
もので、レジスタの内容が（１０００００００）＝１に
なったときに１検出出力を生じるようになされている。

この１検出回路５４．６５，５６．５７の各出力が供給
される４人カッアゲ−）　ＮＯＲ■は当核１検出出力の
いずれかが生じたときに、その出力が０”となることに
よって前記アンドグー）　ＡＮＤｌｏを介してクロ、ク
パヤスｃｐの通過をそれ迄の許容状態から禁止状態とす
る如く制御している。

また、被除数α１データも上記除数αｊデータと同様に
直接あるいはα乗算回路５８、α乗算回路５９、α３乗
算回路６０を介して第７図に示したようなα４乗算回路
を構成する線形シフトレジスタＢｌ　　＋　Ｂｌ　　＊
　Ｂｌ　　＋　Ｂ４にセットされた後、上記クロックパ
ル−スｃｐによシα４が適数同乗、算さ・れることにな
る。

ここで、シフトレジスタＢｌ　　＊　Ｂｌ　　＋　Ｂｓ
　　ｔＢ４の各出力は上記ｌ検出回路５４．５５，５６
゜６７から各出力と対応的にアンド回路６１，６２゜６
３．６４により、アンドがとられることになる。

そして、アンド回路６１，６２，６３．６４の各出力を
オア回路６５に通すことで、α１刊ｊの除算結果を得る
ことができる。

第８図は以上におけるアンド回路６１〜６４の具体例を
示すもので、各入力一端が線形シフトレジスタＢ１〜Ｂ
４からの各出力が対応的に供給されると共に、各人力他
端に１検出回路５４〜５７の各出力が対応的に共通に供
給される８個の２人カアンドグートＡＮＤ！、−ＡＮＤ
！、で構成された場合である。

第９図は以上におけるオア回路６５の具体例を示すもの
で、上記アンド回路６１〜６４の各出力が対応的に供給
される８個の４人力オアグー　）　ＯＲ１・〜０Ｒ２１
で構成された場合である。

第１０図は以上におけるα乗算回路５８の具体例を示す
もので、この場合αｊが αｊ＝ｎ＠＝ｂ、α７＋ｂ６α６＋・・・・・・・・・
＋ｂ、α＋ｂ。

で表わされるものとして、次のような原理によ（ワＩ・
・ 一＼、Ｉ っている。つまり、α・Ｂ（ロ）は α・Ｂ（α）＝ｂ７α８＋ｂ６α７＋　・・、、・・＋
ｂ、α２＋ｂｏα゛＝ｂ６α＋（ｂ５＋ｂ７）α６＋（
ｂ４＋ｂ７）α５＋（ｂ３−Ｆｂ７）α４＋ｂ２α３＋
ｂ、α２＋ｂｏα なので、第１０図に示したようなエクスクルシブオアた
）　ＥＸ−ＯＲｓ鵞〜ＥＸ−ＯＲ８４を用いて実現され
、Ｂ（α）が入力されれはα・Ｂ（ロ））なる乗算出力
を得ることができる。

なお、α２乗算回路５９、α３乗算回路６０についても
上述したα乗算回路５８に準じて容易に構成することが
できる。

而して、以上の構成において被除数α、除数αｊは直接
あるいはα、α２．α３の各乗算回路５８〜６０を介し
てα４乗算回路である線形シフトレジスタＡ　Ｉ　””
　Ａ　４　、Ｂ　ｌ〜Ｂ４に当初にセットされた後、ク
ロックパルスＣｐが入力される毎にα４が乗じられる。

そして、この過程でレジスタＡ１〜Ａ４のうちのいずれ
かの内容がα２５５＝１になった時点で１検出回路５４
〜５７によりクロックパルスｃｐが停止されると共に、
上記α２５５＝１になったレジスタ人１〜Ａ４に対応す
るレジスタＢ１〜Ｂ４の内容が除算結果としてアンド回
路６１〜６４１、オア回路６５を介・して出力される。

次に、具体例としてα１０÷α２４０＝α１Ｏ−２４０
＝α−２５０＝α２５なる除算を実行する場合について
説明する。

この場合レジスタＡ、〜Ａ４、Ｂｘ　〜Ｂ４はのように
当初セットされるがクロックツ臂ルスＣｐが３個入って
きた状態でα４・α４・α４＝α１２が乗じられること
により の如く、レジスタＡ４がα　−１となるのでこれに対応
するレジスタＢ４の内容α２５が商として出力されるも
のである。

このように、１回毎にα４を乗じることにより、必要と
なるαの乗算回数を最高でも６３回（αｊ＝α１のとき
）に低減した状態で所期の除算を乗算処理でなせるもの
である。

また、線形シフトレジスタを５組、α乗算回路を使用す
れば、必要となるαの乗算回数を最高でも５０回に低減
し得る如く、それを拡張することによってさらなる低減
を図ることが可能である。

なお、この発明は上記し且つ図示した実施例のみに限定
されることなく１．この発明の要旨を逸脱しない範囲で
種々の変形や適用が可能であることは言う迄もない。

例えば、テーゾＰＣＭ等のデジタル化された情報の伝送
や記録再生システム、計算機システム等でガロア体によ
る代数演算を必要とする機器に好適するものである。゛ 〔発明の効果〕 従って、以上詳述したようにこの発明によれば、大容量
のメモリを必要とする対数ノ々ソファや真数バッファを
用いることなくガロア体における除算をなし得るように
し、以って構成の簡易化ならびに低価格および高速処理
化に寄与し得るようにした極めて良好なるガロア体にお
ける除算装置を提供することが可能となる。

【図面の簡単な説明】

第１図はリードソロモン符号の復号システムを示す概略
構成図、第２図は従来のエラーロケーション多項式計算
器を示す構成図、第３図はこの発明が適用されるＤＡＤ
再生装置の概要を示す構成図、第４図はこの発明の一実
施例を示す構成図、第５図は第４図の乗算装置部の具体
例を示す構成図、第６図は第４図の除算装置部の具体例
を示す構成図、第７図乃至第１０図はそれぞれ第６図の
α４乗算回路を構成する線形シフトレジスタ部および１
検出回路部、アンド回路部、オア回路部、α１乗算回路
の具体例を示す構成図である。 Ａ１−Ａ４・・！（α４乗算回路用）線形シフトレジス
タ、Ｎ０Ｒ１１・・・ノアゲート、ＡＮＤ　１　ａ・・
・アンＰケ９−ト、５１．５８・・・α１乗算回路、５
２．５９・同乗算回路、５３．６０・・・α乗算回路、
５４〜５７・・・ｌ検出回路、６１〜６４・・・アンド
回路、６５・・・オア回路。 出願人代理人　　弁理士　鈴　江　武　彦第８図 ６１÷ １−６４ 第９図 ５ ？

Claims (1)

1. 【特許請求の範囲】 ガロア体ＧＦ（２ｍ）における２ｍ個の元のうちの２個
   の元α１．α」（但しαは法多項弐Ｆ　（Ｘ）の根）間
   の除算α１÷αｊをα１・α”÷αｊ・αＭ（但しＭは
   整数）なる第１の乗算〔α１・α”〕および第２の乗算
   〔αｊ・α′〕の商の形に変換し、前記第２の乗算がα
   ｊ・α”＝α２″″−１＝αＯ＝＝　１なることを利用
   して結果的にα１÷αｊ＝＝−ｃｔｌ・α”なる乗算に
   変換して処理するもので、前記元αｊが被除数データと
   して直接あるいは適数個のα１．α１・・・・・・乗算
   回路（但しＮｌ　ｅ　Ｎｌ・・・・・・はｌ≦Ｎｘ（Ｎ
   ｌ・・・・・・）を介してそれぞれ毎にセットされると
   共に１シフト毎にそれぞれαＮ０（但しＮｏは１（Ｎｏ
   ）を乗算する形式になされた第１の線形シフトレジスタ
   群と、前記ルαが除数データとして直接あるいは適数個
   のαＮｌ、α′・・・・・・乗算回路を介してそれぞれ
   毎にセットされると共に１シフト毎にそれぞれα　を乗
   算する形式になされた第２の線形シフトレジスタ群と、
   前記第１の線形シフトレジスタ群の各レジスタ毎の１出
   力を検出するｌ検出回路群と、この１検出回路群のいず
   れかで１出力が検出されるまでの適数口だけ前記第１お
   よび第２の線形シフトレジスタ群を共にシフトせしめる
   第１の手段と、前記第２の線形シフトレジスタ群の各レ
   ジスタ毎の出力と前記ｌ検出回路群の各検出回路毎の出
   力とのアンドをとってアンドがとられたレジスタ出力を
   導出する第２の手段とを具備してなることを特徴とする
   ガロア体における除算装置。