JPS6248254B2

JPS6248254B2 -

Info

Publication number: JPS6248254B2
Application number: JP57102805A
Authority: JP
Inventors: Jun Inagawa; Masahide Nanun; Tadashi Kojima
Original assignee: Tokyo Shibaura Electric Co Ltd
Current assignee: Toshiba Corp
Priority date: 1982-06-15
Filing date: 1982-06-15
Publication date: 1987-10-13
Also published as: JPS58219649A

Description

【発明の詳細な説明】

〔発明の技術分野〕この発明は例えば光学式デジタルオーデイオデ
イスク（DAD）再生装置等に用いられるエラー
訂正符号の復号用に好適するガロア体における除
算装置の改良に関する。〔発明の技術的背景〕周知のように、近時開発されている光学式
DAD再生装置（特にはCD：コンパクトデイスク
形）においては、そのエラー訂正符号としてクロ
スインターリーブリードソロモン符号（CIRC）
を採用している。すなわち、これは従来より知られている代表的
なランダムエラー訂正符号のうちで最もエラー訂
正能力が高いものとして広範に定義されている
BCH符号の一種であるリードソロモン符号を用
いるものであるが、それにバーストエラーに対し
ても高い訂正能力を持たせるべくクロスインタリ
ーブなる信号処理を伴わせるようにしたものであ
る。ところで、リードソロモン符号の復号つまりエ
ラー訂正はBCH符号のそれと同様になすことが
できる。今、符号長（ｎ）、情報シンボル（ｋ）個、検
査シンボル（ｎ−ｋ）個からなるリードソロモン
符号について、その復号法を調べてみるものとす
る。但し、上記各シンボルは（ｍ）個の２進ビツ
トつまり２^m個の元を有する有限体であるガロア
体CF（２^m）の元である。そして、この場合（ｔ）重エラー訂正リードソ
ロモン符号の生成多項式ｇ_(x)は、（α）をガロア
体GF（２^m）の原始元として次の(1)式または(2)式
のように表わされる。ｇ_(x)＝（ｘ＋α）（ｘ＋α^２） …（ｘ＋α^2t） …(1) ｇ_(x)＝（ｘ＋α_０）（ｘ＋α） …（ｘ＋α^2t-1） …(2) また、送信符号語をＣ_(x)、受信符号語をＲ_(x)
で表わし、且つエラー多項式をＥ_(x)とすると、
これらの間には次のような関係が成立する。Ｒ_(x)＝Ｃ_(x)＋Ｅ_(x) …(3) この場合、多項式の係数はガロア体GF（２^m）
に含まれており、エラー多項式Ｅ_(x)はエラーロ
ケーシヨンおよび値（大きさ）に対応する項だけ
を含んでいる。従つて、位置ｘ_jにおけるエラー値をＹ_jとする
ととなり、該(4)式でΣはエラーのすべての位置にわ
たる総和を意味している。ここで、シンドロームＳ_iをＳ_i＝Ｒ（αⁱ）〔但しｉ＝０，１…2t−１〕 …(5) の如く定義したとすると、上記(3)式よりＳ_i＝Ｃ（αⁱ）＋Ｅ（αⁱ）となる。この場合、Ｃ_(x)はｇ_(x)で常に割り切れるのでＣ（αⁱ）＝０であるからＳ_i＝Ｅ（αⁱ）となる。そこで、上記(4)式よりと表わすことができる。但し、α^j＝Ｘ_jとおいた
もので、Ｘ_jはα^jにおけるエラーロケーシヨンを
表わしている。ここで、エラーロケーシヨン多項式σ（_xは、
エラー数をｅとしてと定義される。また、(7)式のσ_１〜σ_eはシンドロームＳ_iとの
間で次のように関係付けられる。Ｓ_i+e＋σ₁S_i+e-1＋ …σ_e-1Ｓ_i+1＋σ_eＳ_i …(8) つまり、以上のようなリードソロモン符号の復
号手順は（） (5)式によりシンドロームＳ_iを計算する。（） (8)式によりエラーロケーシヨン多項式の
係数σ_１〜σ_e計算する。（） (7)式によりエラーロケーシヨン多項式の
根Ｘ_jを求める。（） (6)式によりエラー値Ｙ_jを求め、(4)式によ
りエラー多項式を求める。（） (3)式によりエラー訂正を行なう。なる（）〜（）の手順に帰着せしめられる。次に、以上のような復号手順によるエラー訂正
の具体例として、１ブロツクデータに４個の検査
シンボルを用いた場合について説明する。すなわち、この場合の生声成多項式ｇ_(x)はｇ_(x)＝（ｘ＋１）（ｘ＋α）（ｘ＋α^２）（ｘ＋α^３）となり、２重エラーまでの訂正が可能となるもの
であるが、ここではそれを〔Ａ〕，〔Ｂ〕なる二つ
の方式によつた場合について各別に述べるものと
する。〔方式Ａ〕（）シンドロームS₀〜S₃を計算する。（） (8)式をｅ＝１，ｅ＝２について書き直す
と、ｅ＝１の場合にはとなる。また、ｅ＝２の場合にはとなる。ここで、実際の復号器がｅ＝１の場合から動
作を始めるものとすると、先ず連立方程式(9)を
満足する解σ_１を求めなければならない。そし
て、この解が存在しなければ、復号器は次にｅ
＝２の場合について連立方程式(10)を満足する解
σ_１，σ_２を求めなければならない。なお、こ
こでも解が得られない場合はｅ≧３とみなすこ
とになる。 (9)式の解σ_１は σ_１＝Ｓ_１／Ｓ_０＝Ｓ_２／Ｓ_１＝Ｓ_３／Ｓ_２として求め、(10)式の解σ_１，σ_２は σ_１＝Ｓ_０Ｓ_３＋Ｓ_１Ｓ_２／Ｓ_１ ^２＋Ｓ_０Ｓ_２，σ_２＝Ｓ_１Ｓ_３＋Ｓ_２ ^２／Ｓ_１ ^２＋Ｓ_０Ｓ_２として求める。（）以上のようにしてエラーロケーシヨン多
項式の係数σ_iが得られたならば、次に(7)式に
よりエラーロケーシヨン多項式の根を求める。先ず、ｅ＝１の場合は σ_(x)＝ｘ＋σ_１＝０，∴X₁＝σ_１となる。また、ｅ＝２の場合は σ_(x)＝x²＋σ₁x＋σ_２＝０ …(11) として、該(11)式にガロア体GF（２^m）の元を順
次に代入してその解を求めればよく、今この根
をX₁，X₂とする。（）エラーロケーシヨン多項式の根が求まつ
たなら、次に(6)式によりエラー値Ｙ_jを求め
る。先ず、ｅ＝１の場合は S₀＝Y₁ ∴Y₁＝S₀ となる。また、ｅ＝２の場合は S₀＝Y₁＋Y₂ S₁＝Y₁X₁＋Y₂X₂ より ∴Y₁＝Ｘ_２Ｓ_０＋Ｓ_１／Ｘ_１＋Ｘ_２ Y₂＝S₀＋Y₁ （）上述のようにして求めたエラー値Y₁，Y₂
により訂正を行なう。ところで、ポインターイレージヤー法等によ
つてエラーロケーシヨンの値を正確に知ること
ができる場合には、上述した２重エラー訂正用
のリードソロモン符号によつて４重エラーまで
の訂正が可能となるものであり、それが後述す
る〔方式Ｂ〕である。〔方式Ｂ〕（）シンドロームS₀〜S₃を計算する。（），（）エラーロケーシヨンを別の検出方
法で知る。（） (6)式によりエラー値を求める。先ずｅ＝１，ｅ＝２の場合は上述した〔方式
Ａ〕の（）と同様である。そして、ｅ＝３の場合 S₀＝Y₁＋Y₂＋Y₃ S₁＝Y₁X₁＋Y₂X₂＋Y₃X₃ S₂＝Y₁X₁ ²＋Y₂X₂ ²＋Y₃X₃ ² を解いて Y₁＝（Ｓ_２＋Ｘ_３Ｓ_１）＋Ｘ_２（Ｓ_１＋Ｘ_３Ｓ_０）／（
Ｘ_１＋Ｘ_２）（Ｘ_１＋Ｘ_３） Y₂＝（Ｓ_１＋Ｘ_３Ｓ_０）＋Ｙ_１（Ｘ_１＋Ｘ_３）／（Ｘ_２＋Ｘ_３） Y₃＝S₀＋Y₁＋Y₂ となる。また、ｅ＝４の場合は S₀＝Y₁＋Y₂＋Y₃＋Y₄ S₁＝Y₁X₁＋Y₂X₂＋Y₃X₃＋Y₄X₄ S₂＝Y₁X₁ ²＋Y₂X₂ ²＋Y₃X₃ ²＋Y₄X₄ ² S₃＝Y₁X₁ ³＋Y₂X₂ ³＋Y₃X₃ ³＋Y₄X₄ ³ を解いて Y₁＝｛（Ｓ_０Ｘ_４＋Ｓ_１）Ｘ_３＋（Ｓ_１Ｘ_４＋Ｓ_２）｝Ｘ_２＋（Ｓ_１Ｘ_４＋Ｓ_２）Ｘ_３＋（Ｓ_２Ｘ_４＋Ｓ_３）／（Ｘ
_１＋Ｘ_２）（Ｘ_１＋Ｘ_３）（Ｘ_１＋Ｘ_４） Y₂＝（Ｓ_０Ｘ_４＋Ｓ_１）Ｘ_３＋（Ｓ_１Ｘ_４＋Ｓ_２）＋Ｙ_１（Ｘ_１＋Ｘ_３）（Ｘ_１＋Ｘ_４）／（Ｘ_２＋Ｘ_３）（Ｘ_２＋
Ｘ_４） Y₃＝（Ｓ_０Ｘ_４＋Ｓ_１）＋Ｙ_１（Ｘ_１＋Ｘ_４）＋Ｙ_２（Ｘ_２＋Ｘ_４）／（Ｘ_３ＸＸ_４） Y₄＝S₀＋Y₁＋Y₂＋Y₃ となる。（）上述のようにして求めたY₁〜Y₄により訂
正を行なう。第１図は以上のような原理に基くリードソロモ
ン符号の実際の復号システムを示す概略構成図で
ある。すなわち、入力端（IN）を介して導かれ
る被訂正用のデータ（エラー訂正用としてリード
ソロモン符号が用いられていることは勿論であ
る）は二分されて、一方が後述する復号動作の間
データバツフア１１に記憶されると共に、他方が
復号動作をなすためのシンドローム計算器１２以
下に導かれる。そして、シンドローム計算器１２で計算された
シンドロームはシンドロームバツフア１３に記憶
される。ここで、シンドロームバツフア１３の出力部に
接続されたオアゲート１４はエラーの有無を指示
するもので、エラーがあると前述したような手順
によつてエラー訂正動作を開始することになる。つまり、エラーロケーシヨン多項式計算器１５
がエラーロケーシヨン多項式σ_(x)の係数を計算
し、エラーロケーシヨン計算器１６がエラーロケ
ーシヨン多項式の根を計算し、エラー値計算器１
７がエラー値を計算し、これらのエラーロケーシ
ヨンおよびエラー値により上記データバツフア１
１から出力されるデータを訂正するものである。ところで、このような復号システムの各計算器
１２，１５，１６，１７は０か否かの検出ならび
に必要な加算、乗算および除算等の代数演算をな
すものであるが、これらについての具体例として
従来第２図に示すように構成されたエラーロケー
シヨン多項式計算器（特公昭56―20575号）が知
られている。すなわち、第２図において２１はシンドローム
バツフアであつて、シンドロームＳ_iを記憶する
ためのRAMでなり、該シンドロームバツフア２
１にはガロア体GF（２^m）の元である各シンドロ
ームがそれぞれｍビツトの２進形式で記憶され
る。また、２２は作業用バツフアであつて、エラー
ロケーシヨン多項式の係数を計算する際に、代数
演算の中間結果および最終結果を記憶するための
RAMでなり、後の演算で使用される部分結果も
該作業用バツフア２２に記憶される。そして、２３は代数演算の順序を指示する順序
制御装置であつて、上記シンドロームバツフア２
１および作業用バツフア２２に対してアドレスを
供給して適切な記憶位置をアクセスすると共に、
実行された代数演算結果を調べて次の適切な演算
へ分岐せしめるのに供せられる。さらに、２４，２５はそれぞれガロア体GF
（２^m）の元の対数および真数を各別にテーブルの
形式で記憶しているROMでなる対数バツフアお
よび真数バツフアである。ここで、前者の対数バツフア２４のアドレスは
元αⁱの２進表示であり、そのエントリーはαを
底とするαの対数すなわちｉであるが、後者の真
数バツフア２５のアドレスｉにおけるエントリー
はαⁱの２進表示である。例えばガロア体GF（2⁸）の法多項式Ｆ_(x)をＦ_(x)＝x⁸＋x⁶＋x⁵＋x⁴＋１とすると、その０以外の元はＦ_(x)＝０の根αの
べき乗またはα^０〜α^７までの線形結合

〔背景技術の問題点〕

しかしながら、以上のような従来のエラー訂正
装置は、そのエラーロケーシヨン多項式計算器に
おける代数演算のうち乗算および除算用として対
数バツフアおよび真数バツフアを必要とするもの
であるが、このために用いられるROM等のメモ
リ容量が膨大なものになるので、LSI化が阻害さ
れて大容量のメモリを外付けしなければならない
という不具合を生じていた。これは、前述した例の如く１シンボル８ビツト
とした場合で255×８ビツト＝2040ビツトのROM
が２つ必要になり、合計4080ビツトにもなること
からして容易に窺い知れるところである。つまり、従来より知られているガロア体におけ
る乗算装置および除算装置はそれらの元の対数お
よび真数を各別にテーブルの形式で記憶している
大容量メモリでなる対数バツフアや真数バツフア
を必要とするので、それだけ構成が複雑化して高
価格につくという問題を有していた。〔発明の目的〕そこで、この発明は以上のような点に鑑みてな
されたもので、特に大容量のメモリを必要とする
対数バツフアや真数バツフアを用いることなくガ
ロア体における除算をなし得るようにし、以つて
構成の簡易化ならびに低価格化および高速処理化
に寄与し得るようにした極めて良好なるガロア体
における除算装置を提供することを目的としてい
る。〔発明の概要〕すなわち、この発明によるガロア体における除
算装置は、ガロア体GF（２^m）における２^m個の
元のうちの２個の元αⁱ，α^j（但しαは法多項式
Ｆ_(x)の根）間の除算αⁱ÷α^jをαⁱ・α^M÷α^j・
α^M（但しＭは整数）なる第１の乗算〔αⁱ・α
^M〕および第２の乗算〔α^j・α^M〕の商の形に変
換し、前記第２の乗算がα^j・α^M＝α^2m-1＝α^０
＝１なることを利用して結果的にαⁱ÷α^j＝αⁱ・
α^Mなる乗算に変換して処理するもので、前記元
α^jが被除数データとして直接あるいは適数個の
α^N1，α^N2…乗算回路（但しN₁，N₂…は１＜
N₁，N₃…＜２^m-1）を介してそれぞれ毎にセツト
される第１の線形シフトレジスタ群と、前記元α
ⁱが除数データとして直接あるいは適数個のα^N
^１，α^N2…乗算回路を介してそれぞれ毎にセツト
される第２の線形シフトレジスタ群と、前記第１
の線形シフトレジスタ群の各レジスタ毎の１出力
を検出する１検出回路群と、この１検出回路群の
いずれかで１出力が検出されるまでの適数回だけ
前記第１および第２の線形シフトレジスタ群を共
にシフトせしめる第１の手段と、前記第２の線形
シフトレジスタ群の各レジスタ毎の出力と前記１
検出回路群の各検出回路毎の出力とのアンドをと
つてアンドがとられたレジスタ出力を導出する第
２の手段とを具備してなることを特徴としてい
る。〔発明の実施例〕先ず、この発明が適用される光学式（CD形）
デジタルオーデイオデイスク（DAD）再生装置
の概要について説明する。すなわち、第３図に示すようにデイスクモータ
１１１によつて回転駆動されるターンテーブル１
１２上に装着されたデイスク１１３は光学式ピツ
クアツプ１１４によつて再生される。この場合、
光学式ピツクアツプ１１４は半導体レーザ１１４
ａからの出射光をビームスプリツター１１４ｂ、
対物レンズ１１４ｃを介してデイスク１１３の信
号面に照射し、該デイスク１１３に所定の
（EFM）変調およびインタリーブを伴つた形態で
記録されている再生すべきオーデイオ信号のデジ
タル（PCM）化データに対応したピツト（反射
率の異なる凹凸）からの反射光を対物レンズ１１
４ｃ、ビームスプリツター１１４ｂを介して４分
割フオトデテクタ１１４ｄに導き、該４分割フオ
トデテクタ１１４ｄで光電変換された４つの再生
信号を外部に出力可能になされているもので、自
からはピツクアツプ送りモータ１１５によつてデ
イスク１１３の半径方向に直線駆動される。そして、４分割フオトデテクタ１１４ｄからの
４つの再生信号はマトリクス回路１１６に供給さ
れて所定のマトリクス演算処理が施されることに
より、フオーカスエラー信号Ｆ、トラツキングエ
ラー信号および高周波信号RFに分離される。このうち、フオーカスエラー信号Ｆはフオーカ
スサーチ回路１１０からのフオーカスサーチ信号
と共に、前記光学式ピツクアツプ１１４のフオー
カスサーボ系FSを駆動するのに供せられる。また、トラツキングエラー信号Ｔは後述するシ
ステムコントローラ１１７を介して与えられるサ
ーチ制御信号と共に、前記光学式ピツクアツプ１
１４のトラツキングサーボ系TSを駆動するのに
且つ前記ピツクアツプ送りモータ１１５を（リニ
アトラツキング）制御するのに供せられる。そして、残る高周波信号RFが主再生信号成分
として再生信号処理系１１８に供給される。すな
わち、この再生信号処理系１１８は先ず再生信号
をスライスレベル（アイパターン）検出器１１９
によつて制御される波形整形回路１２０に導いて
不要なアナログ成分と必要とするデータ成分を分
離し、データ成分のみをPLL型でなる同期クロツ
ク再生回路１２１および第１の信号処理系１２２
のエツジ検出器１２２ａに供給する。ここで、同期クロツク再生回路１２１からの同
期クロツクはデータ復調用として第１の信号処理
系１２２における同期信号分離用クロツク生成回
路１２２ｂに導かれて同期信号分離用クロツクを
生成するのに供せられる。一方、上記エツジ検出器１２２ａを通つた再生
信号は同期信号検出器１２２ｃに導かれて上記同
期信号分離用クロツクにより同期信号が分離され
ると共に、復調回路１２２ｄに導かれて
（EFM）復調される。このうち、同期信号は同期信号保護回路１２２
ｅを介して誤動作が生じないように保護された状
態で、上記同期信号分離用クロツクと共に入力デ
ータ処理用タイミング信号生成回路１２２ｆに導
かれる。また、復調信号はデータバス入出力制御回路１
２２ｇを介して後述する第２の信号処理系１２３
の入出力制御回路１２３ａに供給されると共に、
そのうちのサブコードであるコントロール信号お
よび表示信号成分がコントロール表示処理回路１
２２ｈおよびサブコード処理回路１２２ｉに導か
れる。そして、サブコード処理回路１２２ｉで必要な
エラー検出および訂正が施されたサブコードデー
タはシステムコントローラ用インターフエイス回
路１２２ｇを介してシステムコントローラ１１７
に供給される。ここで、システムコントローラ１１７はマイク
ロコンピユータ、インフエイス回路およびドライ
バ用集積回路等を有してなり、コントロールスイ
ツチ１２４からの指令信号によりDAD再生装置
を所望の状態に制御すると共に、上述のサブコー
ド（例えば再生曲のインデツクス情報）を表示器
１２５に表示せしめるのに供せられている。なお、上記入力データ処理用タイミング信号生
成回路１２２ｆからのタイミング信号はデータセ
レクト回路１２２ｊを介して上記データバス入出
力制御回路１２２ｇを制御するのに供せられると
共に、周波数検出器１２２ｋおよび位相検出器１
２２ｌならびにPWM変調器１２２ｍを介して上
記デイスクモータ１１１を線速度一定（CLV）
方式で駆動するための自動周波数制御AFCおよ
び自動位相制御APCに供せられている。この場合、位相検出器１２２ｌにはクリスタル
発振器１２２ｎからの発振信号に基いて動作する
システムクロツク生成回路１２２ｐからのシステ
ムクロツクが供給されている。そして、第２の信号処理回路１２３の入出力制
御回路１２３ａを通つた復調データはエラー検出
および訂正または補正用のシンドローム検出器１
２３ｂ、エラーポインタ制御回路１２３ｃ、訂正
回路１２３ｄおよびデータ出力回路１２３ｅを介
して必要なエラー訂正、デイインタリーブ、エラ
ー補正等の処理を受けてデジタル―アナログ
（Ｄ／Ａ）変換器１２６に導出される。この場合、外部メモリ制御回路１２３ｆは上記
データセレクト回路１２２ｊと共働して訂正に必
要なデータが書き込まれている外部メモリ１２７
を制御することにより、上記入出力制御回路１２
３ａを介して訂正に必要なデータを取り込む如く
なされている。また、タイミングコントロール回路１２３ｇは
前記システムクロツク生成回路１２２ｐからのシ
ステムクロツクに基いてエラー訂正および補正な
らびにＤ／Ａ変換に必要なタイミングコントロー
ル信号を供給する如くなされている。また、ミユーテイング（検出）制御回路１２３
ｈは上記エラーポインタ制御回路１２３ｃからの
出力またはシステムコントローラ１１７を介して
与えられるコントロール信号に基いてエラー補正
時およびDAD再生装置の動作開始、終了時等に
必要となる所定のミユーテイング制御をなすのに
供せられている。そして、上記Ｄ／Ａ変換器１２６でアナログ信
号に戻されたオーデイオ信号はローパスフイルタ
１２８、増幅器１２９を介してスピーカ１３０を
奏鳴するのに供せられる。次に、以上のようなDAD再生装置のエラー訂
正部に適用されたこの発明に係るガロア体におけ
る除算装置の一実施例につき図面を参照して詳細
に説明する。すなわち、第４図は第３図における第２の信号
処理回路１２３の訂正回路１２３ｄに主として含
まれる前述したようなエラーロケーシヨン多項式
計算器部を示しているもので、対数バツフアや真
数バツフアを用いることなくガロア体における乗
算および除算がなし得るようにした乗算装置４１
および除算装置４２を備えている以外は前述した
第２図のそれと同様である。つまり、エラー訂正
符号として採用されたBCH符号の一種であるリ
ードソロモン符号の復号（エラー訂正）のために
各種の代数演算をなすのがエラーロケーシヨン多
項式計算器に与えられた役目であるが、このうち
加算および０であるか否かの検出については第２
図のそれと同様になされるので同一符号を付して
その説明を省略するものとし、第２図のそれとは
異なる乗算および除算について以下に述べるもの
である。先ず、ガロア体における乗算についてみてみる
に、例えばガロア体GF（2⁸）の元αⁱとα^jとの乗
算（αⁱ・α^j，但しαは法多項式Ｆ_(x)＝X⁸＋X⁶
＋X⁵＋X⁴＋１の根である）は αⁱ＝Ｃ（α）＝c₀
＋c₁α＋……c₇α^７ α^j＝Ｄ（α）＝d₀＋d₁α＋……d₇α^７と表わした場合（但し、c₀〜c₇，d₀〜d₇は０また
は１とする） αⁱ・α^j＝Ｃ（α）・Ｄ（α）＝d₇α⁷C（α）＋d₆
α⁶C（α）……d₀C（α）＝α^６〔αd₇C（α）＋
d₆C（α）〕＋d₅α⁵C（α）＋……＋d₀C（α）＝α
^５〔α〔αd₇C（α）＋d₆C（α）〕＋d₅C（α）〕＋
d₄α⁴C（α）＋……＋d₀C（α）〓＝〔α〔α〔α〔α〔α〔α〔αd₇C（α）＋
d₆C（α）〕＋d₅C（α）〕＋d₄C（α）〕＋d₃C
（α）〕＋d₂C（α）〕＋d₁C（α）＋d₀C（α）〕となる。つまり、このようなガロア体GF（2⁸）の元αⁱ
とα^jとの乗算は線形シフトレジスタを用いて第
５図に示したように構成される乗算装置で実現し
得ることを物語つている。すなわち、第５図においてAND₀〜AND₇は各
一端に上記乗数Ｄ（α）の係数であるd₀〜d₇が上
位ビツトから順にシリアルに供給されると共に、
各他端に上記被乗数Ｃ（α）の係数であるc₀〜c₇
が上位ビツトから順にパラレルに供給されるアン
ドゲートである。また、FF₀〜FF₇は、上記各ア
ンドゲートAND₀〜AND₇からの出力が入力一端
に対応して供給されるエクスクルシブオアゲート
（EX―OR₀）〜（EX―OR₇）を介して継続的に接
続されると共に帰還接続されることにより線形シ
フトレジスタ群SR₀を構成するフリツプフロツプ
回路である。この場合、４段目と５段目、５段目と６段目お
よび６段目と７段目のフリツプフロツプ回路FF₃
―FF₄，FF₄―FF₅，FF₅―FF₇との段間は各一
端が帰還路に接続されたエクスクルシブオアゲー
ト（EX―OR₄′），（EX―OR₅′，EX―OR₆′）がさ
らに介挿された状態で結合されている。また、各
フリツプフロツプ回路FF₀〜FF₇のクロツク入力
端CKには図示しないクロツク発生器からのクロ
ツクパルスCPがパラレルに供給される如くなさ
れている。つまり、Ｃ（α）の係数c₀〜c₇がビツトシリア
ルに入力されることにより、先ずX₀が計算さ
れ、その後X₁，X₂…と続いて８ビツト入力終了
時に線形シフトレジスタSR₀にはX₇すなわちＣ
（α）・Ｄ（α）が実現されるもので、各フリツプ
フロツプ回路FF₀〜FF₇の出力x₀，x₁……x₇が乗
算結果を与えることになる。ここで、X₀〜X₇は次の通りである。 X₀＝d₇C（α） X₁＝αX₀＋d₆C（α） X₂＝αX₁＋d₅C（α） X₃＝αX₂＋d₄C（α） X₄＝αX₃＋d₃C（α） X₅＝αX₄＋d₂C（α） X₆＝αX₅＋d₁C（α） X₇＝αX₆＋d₀C（α）＝（x₀，x₁……x₇）そして、以上のようなガロア体GF（2⁸）におけ
る乗算装置はガロア体GF（2⁸）の元の対数および
真数をテーブルの形式で記憶するROM等の大容
量メモリでなる対数バツフアや真数バツフアを用
いることなく、単に線形シフトレジスタを用いる
だけでなし得るので、その構成を簡易で安価なも
のとすることができるという効用を有している。次に、ガロア体における除算についてみてみる
に、例えばガロア体GF（2⁸）の元αⁱとα^jとの除
算αⁱ÷α^j（但しαは法多項式Ｆ（ｘ）＝x⁸＋x⁶＋
x⁵＋x⁴＋１の根とする）は αⁱ÷α^j＝（αⁱ・α^M）÷（α^j・α^M）と同値である（但し、Ｍは整数）この場合、α^j・α^M＝α²⁵⁵＝α^０＝１ならば αⁱ÷α^j＝αⁱ・α^M となる。つまり、ガロア体GF（2⁸）の元αⁱとα^jとの除
算（αⁱ÷α^j）をなす場合、被除数αⁱ、除数α^j
にそれぞれαを何回は乗じて行く過程で、Ｍ回α
を乗じたときにα^j・α^M＝１になつたとすれば、
そのときにおける被除数αⁱとα^mとの積であるα
ⁱ・α^Mが除算結果であることに外ならないことを
利用して、乗算処理で所期の除算をなせることに
なる。ここで、乗算処理については前述したような線
形シフトレジスタによる乗算装置を用いてなすこ
とは言う迄もない。ところで、この場合α^j・α^M＝α²⁵⁵＝α^０＝１
を得るために必要となるαを乗じる回数は、除数
α^j＝α^１のときに最高で254回（つまりＭ＝
254）となるが、単純にその通りになせるように
したのでは乗算処理に要する時間が徒らに長時間
化してしまうので好ましくない。そこで、この発明では被除数αⁱ、除数α^jに対
し予め適数（Ｎ）回だけαを乗じておくことによ
り、実際に必要となるαを乗じる回数を低減して
短時間で乗算処理（延いては除算処理）がなせる
ようにしようとするものである。第６図は以上のようにしてガロア体における除
算を乗算処理で実現する除算装置の構成を示すも
ので、この場合上述の（Ｎ）としてN₁＝64，N₂
＝128，N₃＝192つまりα⁶⁴，α¹²⁸，α¹⁹²を予め
乗じるようにしたものである。すなわち、除数α^jデータは直接あるいはα⁶⁴
乗算回路５１、α¹²⁸乗算回路５２、α¹⁹²乗算回
路５３を介して線形シフトレジスタA₁，A₂，
A₃，A₄にセツトされる。ここで、線形シフトレ
ジスタA₁，A₂，A₃，A₄は前述した第５図の線形
シフトレジスタSR₀と同様に構成されているもの
で、アンドゲートAND₁₁を介して与えられるクロ
ツクパルスＣ_pによりシフトされ、１シフト毎に
αが乗算されることになる。そして、シフトレジスタA₁，A₂，A₃，A₄の各
出力が供給される１検出回路５４，５５，５６，
５７は、レジスタの内容が（10000000）＝１にな
つたときに１検出出力を生じるようになされてい
る。この１検出回路５４，５５，５６，５７の各
出力が供給される４入力ノアゲートNOR₁₀は、当
該１検出出力のいずれかが生じたときに、その出
力が“０”となることによつて前記アンドゲート
AND₁₀を介してクロツクパルスＣ_pの通過をそれ
迄の許容状態から禁止状態とする如く制御してい
る。また、被除数αⁱデータも上記除数α^jデータと
同様に直接あるいはα⁶⁴乗算回路５８、α¹²⁸乗算
回路５９、α¹⁹²乗算回路６０を介して線形シフ
トレジスタB₁，B₂，B₃，B₄にセツトされた後、
上記クロツクパルスＣ_pによりαが適数回乗算さ
れることになる。ここで、シフトレジスタB₁，B₂，B₃，B₄の各
出力は上記１検出回路５４，５５，５６，５７か
らの各出力と対応的にアンド回路６１，６２，６
３，６４により、アンドがとられることになる。そして、アンド回路６１，６２，６３，６４の
各出力をオア回路６５に通すことで、αⁱ÷α^jの
除算結果を得ることができる。第７図は以上における１検出回路５４〜５７の
具体例を示すもので、線形シフトレジスタA₁〜
A₄からの各出力のうちα^１に対応する出力のみ
にインバータI₁₀を介して且つそれ以外のα^２〜
α^７に対応する出力が直接的に加えられる８入力
ノアゲートNOR₁₁で構成された場合である。第８図は以上におけるアンド回路６１〜６４の
具体例を示すもので、各入力一端が線形シフトレ
ジスタB₁〜B₄からの各出力が対応的に供給され
ると共に、各入力他端に１検出回路５４〜５７の
各出力が対応的に共通に供給される８個の２入力
アンドゲートAND₂₀〜AND₂₇で構成された場合で
ある。第９図は以上におけるオア回路６５の具体例を
示すもので、上記アンド回路６１〜６４の各出力
が対応的に供給される８個の４入力オアゲート
OR₂₀〜OR₂₇で構成された場合である。第１０図は以上におけるα⁶⁴乗算回路５８の具
体例を示すもので、この場合α^jが α^j＝Ｂ（α）＝b₇α^７＋b₆α^６＋…b₁α＋b₀ で表わされるものとして、次のような原理によつ
ている（但し、b₁〜b₇は０または１である）。すなわち、α⁶⁴＝α^７＋α^６＋α^５であるので α⁶⁴・Ｂ（α）＝（α^７＋α^６＋α^５）（b₇α^７
＋…＋b₁α＋b₀）＝（b₀＋b₁＋b₅＋b₇）α^７＋（b₀＋
b₄＋b₆）α^６＋（b₀＋b₁＋b₃）α^５＋（b₁＋b₂＋b₅）α
^４＋（b₄＋b₅）α^３＋（b₃＋b₄）α^２＋（b₂＋b₃＋b₇）
α＋（b₁＋b₂＋b₆）となる。つまり、このような演算は第１０図に示
したようなエクスクルシブオア群（EX―OR₁₁）
〜（EX―OR₂₅）で実現されるもので、Ｂ（α）
が入力されれば、α⁶⁴・Ｂ（α）なる乗算出力を
得ることができる。なお、α¹²⁸乗算回路５９、α¹⁹²乗算回路６０
についても上述したα⁶⁴乗算回路５８に準じて容
易に構成することができる。次に具体例としてα²⁰⁰÷α¹⁸⁰＝α²⁰を実行する
場合について説明する。この場合、シフトレジスタA₁〜A₄，B₁〜B₄
は、次のようにセツトされる。 A₁：α¹⁸⁰ A₂：α¹⁸⁰・α⁶⁴＝α²⁴⁴ A₃：α¹⁸⁰・α¹²⁸＝α³⁰⁸＝α⁵³ A₄：α¹⁸⁰・α¹⁹²＝α³⁷²＝α¹¹⁷ B₁：α²⁰⁰ B₂：α²⁰⁰・α⁶⁴＝α²⁶⁴＝α^９ B₃：α²⁰⁰・α¹²⁸＝α³²⁸＝α⁷³ B₄：α²⁰⁰・α¹⁹²＝α³⁰²＝α¹³⁷ そして、クロツクパルスＣ_pが11個入つてきた
状態で、シフトレジスタA₂の内容がα²⁵⁵＝１と
なることによつて、それが１検出回路５５で検出
されるとクロツクパルスＣ_pの供給が停止される
ようになる。このとき、シフトレジスタB₂の内
容はα²⁰となつており、このα²⁰なる出力がアン
ド回路６２およびオア回路６５を介して出力され
るものである。このようにして、αを乗じる回数を最高でも63
回（α^j＝α^１のとき）に低減した状態で所期の
除算を乗数処理でなせるものである。この場合、線形シフトレジスタ対をさらに多く
しておけば、αを乗じる回数をより少ない回数に
軽減することができる。なお、この発明は上記し且つ図示した実施例の
みに限定されることなく、この発明の要旨を逸脱
しない範囲で種々の変形や適用が可能であること
は言う迄もない。例えば、テープPCM等のデジタル化された情
報の伝達や記録再生システム、計算機システム等
でガロア体による代数演算を必要とする機器に好
適するものである。〔発明の効果〕従つて、以上詳述したようにこの発明によれ
ば、大容量のメモリを必要とする対数バツフアや
真数バツフアを用いることなくガロア体における
除算をなし得るようにし、以つて構成の簡易化な
らびに低価格化および高速処理化に寄与し得るよ
うにした極めて良好なるガロア体における除算装
置を提供することが可能となる。

【図面の簡単な説明】

第１図はリードソロモン符号の復号システムを
示す概略構成図、第２図は従来のエラーロケーシ
ヨン多項式計算器を示す構成図、第３図はこの発
明が適用されるDAD再生装置の概要を示す構成
図、第４図はこの発明の一実施例を示す構成図、
第５図は第４図の乗算装置部の具体例を示す構成
図、第６図は第４図の除算装置部の具体例を示す
構成図、第７図乃至第１０図はそれぞれ第６図の
１検出回路部、アンド回路部、オア回路部、α⁶⁴
乗算回路部の具体例を示す構成図である。 A₁〜A₄，B₁〜B₄…線形シフトレジスタ、５
１，５８…α⁶⁴乗算回路、５２，５９…α¹²⁸乗算
回路、５３，６０…α¹⁹²乗算回路、５４〜５７
…１検出回路、６１〜６４…アンド回路、６５…
アオ回路、AND₁₁…アンドゲート、NOR₁₀…ノア
ゲート。

Claims

【特許請求の範囲】１ガロア体GF（２^m）における２^m個の元のう
ちの２個の元αⁱ，α^j（但しαは法多項式Ｆ_(x)の
根）間の除算αⁱ÷α^jをαⁱ・α^M÷α^j・α^M（但
しＭは整数）なる第１の乗算〔αⁱ・α^M〕および
第２の乗算〔α^j・α^M〕の商の形に変換し、前記
第２の乗算がα^j・α^M＝α^2m-1＝α^０＝１なるこ
とを利用して結果的にαⁱ÷α^j＝αⁱ・α^Mなる乗
算に変換して処理するもので、前記元α^jが被除
数データとして直接あるいは適数個のα^N1，α^N2
…乗算回路（但しN₁，N₂…は１＜N₁，N₂…＜２^m
^−１）を介してそれぞれ毎にセツトされる第１の線
形シフトレジスタ群と、前記元αⁱが除数データ
として直接あるいは適数個のα^N1，α^N2…乗算回
路を介してそれぞれ毎にセツトされる第２の線形
シフトレジスタ群と、前記第１の線形シフトレジ
スタ群の各レジスタ毎の１出力を検出する１検出
回路群と、この１検出回路群のいずれかで１出力
が検出されるまでの適数回だけ前記第１および第
２の線形シフトレジスタ群を共にシフトせしめる
第１の手段と、前記第２の線形シフトレジスタ群
の各レジスタ毎の出力と前記１検出回路群の各検
出回路毎の出力とのアンドをとつてアンドがとら
れたレジスタ出力を導出する第２の手段とを具備
してなることを特徴とするガロア体における除算
装置。