JPS638648B2 - - Google Patents
Info
- Publication number
- JPS638648B2 JPS638648B2 JP57102802A JP10280282A JPS638648B2 JP S638648 B2 JPS638648 B2 JP S638648B2 JP 57102802 A JP57102802 A JP 57102802A JP 10280282 A JP10280282 A JP 10280282A JP S638648 B2 JPS638648 B2 JP S638648B2
- Authority
- JP
- Japan
- Prior art keywords
- error
- circuit
- equation
- multiplication
- signal
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Computational Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
- Optical Recording Or Reproduction (AREA)
Description
〔発明の技術分野〕
この発明は例えば光学式デジタルオーデイオデ
イスク（DAD）再生装置等に用いられるエラー
訂正符号の復号用に好適するガロア体における乗
算装置の改良に関する。 〔発明の技術的背景〕 周知のように、近時開発されている光学式
DAD再生装置（特にはCD：コンパクトデイスク
形）においては、そのエラー訂正符号としてクロ
スインターリーブリードソロモン符号（CIRC）
を採用している。 すなわち、これは従来より知られている代表的
なランダムエラー訂正符号のうちで最もエラー訂
正能力が高いものとして広範に定義されている
BCH符号の一種であるリードソロモン符号を用
いるものであるが、それにバーストエラーに対し
ても高い訂正能力を持たせるべくクロスインタリ
ーブなる信号処理を伴わせるようにしたものであ
る。 ところで、リードソロモン符号の復号つまりエ
ラー訂正はBCH符号のそれと同様になすことが
できる。 今、符号長（ｎ）、情報シンボル（ｋ）個、検
査シンボル（ｎ−ｋ）個からなるリードソロモン
符号について、その復号法を調べてみるものとす
る。但し、上記各シンボルは（ｍ）個の２進ビツ
トつまり2m個の元を有する有限体であるガロア体
GF2mの元である。 そして、この場合（ｔ）重エラー訂正リードソ
ロモン符号の生成多項式ｇ（ｘ）は、（α）をガロ
ア体GF（2m）の原始元として次の(1)式または(2)式
のように表わされる。 ｇ（ｘ）＝（ｘ＋α）（ｘ＋α2） ……（ｘ＋α2t） ……(1) ｇ（ｘ）＝（ｘ＋α0）（ｘ＋α） ……（ｘ＋α2t-） ……(2) また、送信符号語をＣ（ｘ）、受信符号語をＲ
（ｘ）で表わし、且つエラー多項式をＥ（ｘ）とす
ると、これらの間には次のような関係が成立す
る。 Ｒ（ｘ）＝Ｃ（ｘ）＋Ｅ（ｘ） ……(3) この場合、多項式の係数はガロア体GF（2m）に
含まれており、エラー多項式Ｅ（ｘ）はエラーロ
ケーシヨンおよび値（大きさ）に対応する項だけ
を含んでいる。 従つて、位置xjにおけるエラー値をYjとすると
Ｅ（ｘ）＝〓j Yjxj ……(4) となり、該(4)式でΣはエラーのすべての位置にわ
たる総和を意味している。 ここで、シンドロームSiを Si＝Ｒ（αi） 〔但しｉ＝０，１……2t−１〕 ……(5) の如く定義したとすると、上記(3)式より Si＝Ｃ（αi）＋Ｅ（αi） となる。 この場合、Ｃ（ｘ）はｇ（ｘ）で常に割り切れる
ので Ｃ（αi）＝０ であるから Si＝Ｅ（αi） となる。そこで、上記(4)式より
Si＝Ｅ（αi）＝〓j Yj（αi）j ＝〓j YjXi j ……(6) と表わすことができる。但しαj＝Xjとおいたもの
で、Xjはαjにおけるエラーロケーシヨンを表わし
ている。 ここで、エラーロケーシヨン多項式σ（ｘ）は、
エラー数をｅとして σ（ｘ）＝〓ｉ（ｘ−Xi） ＝xe＋σ1xe-1＋………＋σe ……(7) と定義される。 また、(7)式のσ1〜σeはシンドロームSiとの間で
次のように関係付けられる。 Si+e＋σ1Si+e-1 ＋……σe-1Si+1＋σeSi ……(8) つまり、以上のようなリードソロモン符号の復
号手順は （） (5)式によりシンドロームSiを計算する。 （） (8)式によりエラーロケーシヨン多項式の
係数σ1〜σeを計算する。 （） (7)式によりエラーロケーシヨン多項式の
根Xjを求める。 （） (6)式によりエラー値Yjを求め、(4)式に
よりエラー多項式を求める。 （） (3)式によりエラー訂正を行なう。 なる（）〜（）の手順に帰着せしめられる。 次に、以上のような復号手順によるエラー訂正
の具体例として、１ブロツクデータに４個の検査
シンボルを用いた場合について説明する。 すなわち、この場合の生成多項式ｇ（ｘ）は ｇ（ｘ）＝（ｘ＋１）（ｘ＋α）（ｘ＋α2）（ｘ＋
α3） となり、２重エラーまでの訂正が可能となるもの
であるが、ここではそれを〔Ａ〕，〔Ｂ〕なる二つ
の方式によつた場合について各別に述べるものと
する。 〔方式 Ａ〕 （） シンドロームS0〜S3を計算する。 （） (8)式をｅ＝１，ｅ＝２について書き直す
と、ｅ＝１の場合には S1＋σ1S0＝０ S2＋σ1S1＝０ S3＋σ1S2＝０ ……(9) となる。また、ｅ＝２の場合には
S2＋σ1S1＋σ2S0＝０ S3＋σ1S2＋σ2S1＝０ ……(10) となる。 ここで、実際の復号器がｅ＝１の場合から動作
を始めるものとすると、先ず連立方程式(9)を満足
する解σ1を求めなければならない。そして、この
解が存在しなければ、復号器は次にｅ＝２の場合
について連立方程式(10)を満足する解σ1，σ2を求め
なければならない。なお、ここでも解が得られな
い場合はｅ≧３とみなすことになる。 (9)式の解σ1は σ1＝S1／S0＝S2／S1＝S3／S2 として求め、(10)式の解σ1，σ2は σ1＝S0S3＋S1S2／S1 2＋S0S2，σ2＝S1S3＋S2 2／S1 2
＋S0S2 として求める。 （） 以上のようにしてエラーロケーシヨン多
項式の係数σiが得られたならば、次に(7)式によ
りエラーロケーシヨン多項式の根を求める。 先ず、ｅ＝１の場合は σ（ｘ）＝ｘ＋σ1＝０，∴X1＝σ1 となる。また、ｅ＝２の場合は σ（ｘ）＝x2＋σ1x＋σ2＝０ ……(11) として、該(11)式にガロア体GF（2m）の元を順次に
代入してその解を求めればよく、今この根をを
X1，X2とする。 （） エラーロケーシヨン多項式の根が求まつ
たなら、次に(6)式によりエラー値Yjを求める。 先ず、ｅ＝１の場合は S0＝Y1 ∴Y1＝S0 となる。また、ｅ＝２の場合は
S0＝Y1＋Y2 S1＝Y1X1＋Y2X2 より ∴Y1＝X2S0＋S1／X1＋X2 Y2＝S0＋Y1 （） 上述のようにして求めたエラー値Y1，
Y2により訂正を行なう。 ところで、ポインターイレージヤー法等によつ
てエラーロケーシヨンの値を正確に知ることがで
きる場合には、上述した２重エラー訂正用のリー
ドソロモン符号によつて４重エラーまでの訂正が
可能となるものであり、それが後述する〔方式
Ｂ〕である。 〔方式 Ｂ〕 （） シンドロームS0〜S3を計算する。 （）（） エラーロケーシヨンを別の検出方
法で知る。 （） (6)式によりエラー値を求める。 先ずｅ＝１，ｅ＝２の場合は上述した〔方式
Ａ〕の（）と同様である。 そして、ｅ＝３の場合 S0＝Y1＋Y2＋Y3 S1＝Y1X1＋Y2X2＋Y3X3 S2＝Y1X1 2＋Y2X2 2＋Y3X3 2 を解いて Y1＝（S2＋X3S1）＋X2（S1＋X3S0）／（X1＋X2）（X1
＋X3） Y2＝（S1＋X3S0）＋Y1（X1＋X3）／（X2＋X3） Y3＝S0＋Y1＋Y2 となる。 また、ｅ＝４の場合は S0＝Y1＋Y2＋Y3＋Y4 S1＝Y1X1＋Y2X2＋Y3X3＋Y4X4 S2＝Y1X1 2＋Y2X2 2＋Y3X3 2＋Y4X4 2 S3＝Y1X1 3＋Y2X2 3＋Y3X3 3＋Y4X4 3 を解いて Y1＝｛（S0X4＋S1）X3＋（S1X4＋S2）｝X2＋（S1X4
＋S2）X3＋（S2X4＋S3）／（X1＋X2）（X1＋X3）（X1＋
X4） Y2＝（S0X4＋S1）X3＋（S1X4＋S2）＋Y1（X1＋X3）
（X1＋X4）／（X2＋X3）（X2＋X4） Y3＝（S0X4＋S1）＋Y1（X1＋X4）＋Y2（X2＋X4）／
（X3＋X4） Y4＝S0＋Y1＋Y2＋Y3 となる。 （） 上述のようにして求めたY1〜Y4により
訂正を行なう。 第１図は以上のような原理に基くリードソロモ
ン符号の実際の復号システムでなるエラー訂正回
路を示す概略構成図である。すなわち、入力端
（IN）を介して導かれる被訂正用のデータ（エラ
ー訂正用としてリードソロモン符号が用いられて
いることは勿論である）は二分されて、一方が後
述する復号動作の間データバツフア１１に記憶さ
れると共に、他方が復号動作をなすためのシンド
ローム計算器１２以下に導かれる。 そして、シンドローム計算器１２で計算された
シンドロームはシンドロームバツフア１３に記憶
される。 ここで、シンドロームバツフア１３の出力部に
接続されたオアゲート１４はエラーの有無を指示
するもので、エラーがあると前述したような手順
によつてエラー訂正動作を開始することになる。 つまり、エラーロケーシヨン多項式計算器１５
がエラーロケーシヨン多項式σ（ｘ）の係数を計
算し、エラーロケーシヨン計算器１６がエラーロ
ケーシヨン多項式の根を計算し、エラー値計算器
１７がエラー値を計算し、これらのエラーロケー
シヨンおよびエラー値により上記データバツフア
１１から出力されるデータを訂正するものであ
る。 ところで、このような復号システムの各計算器
１２，１５，１６，１７は０か否かの検出ならび
に必要な加算、乗算および除算等の代数演算をな
すものであるが、これらについての具体例として
従来第２図に示すように構成されたエラーロケー
シヨン多項式計算器（特公昭56―20575号）が知
られている。 すなわち、第２図において２１はシンドローム
バツフアであつて、シンドロームSiを記憶するた
めのRAMでなり、該シンドロームバツフア２１
にはガロア体GF（2m）の元である各シンドローム
がそれぞれｍビツトの２進形式で記憶される。 また、２２は作業用バツフアであつて、エラー
ロケーシヨン多項式の係数を計算する際に、代数
演算の中間結果および最終結果を記憶するための
RAMでなり、後の演算で使用される部分結果も
該作業用バツフア２２に記憶される。 そして、２３は代数演算の順序を指示する順序
制御装置であつて、上記シンドロームバツフア２
１および作業用バツフア２２に対してアドレスを
供給して適切な記憶位置をアクセスすると共に、
実行された代数演算結果を調べて次の適切な演算
へ分岐せしめるのに供せられる。 さらに、２４，２５はそれぞれガロア体GF
（2m）の元の対数および真数を各別にテーブルの
形式で記憶しているROMでなる対数バツフアお
よび真数バツフアである。 ここで、前者の対数バツフア２４のアドレスは
元αiの２進表示であり、そのエントリーはαを底
とするαの対数すなわちｉであるが、後者の真数
バツフア２５のアドレスｉにおけるエントリーは
αiの２進表示である。 例えばガロア体GF（28）の法多項式Ｆ（ｘ）を Ｆ（ｘ）＝x8＋x6＋x5＋x4＋１ とすると、その０以外の元はＦ（ｘ）＝０の根αの
べき乗またはα0〜α7までの線形結合
7 〓i=0 aiαi （但しai＝０または１） で表わすことができる。 また、この場合a0〜a7までの８個の係数を取り
出して２進ベクトルとして表わすこともできる。 例えば α1＝０・α0＋１・α1＋０・α2＋０・α3＋０・α4
＋０・α5＋０・α6＋０・α7 ＝（01000000） α7＝０・α0＋……＋０・α6＋１・α7 ＝（00000001） α8＝１＋α4＋α5＋α6 （10001110） α9＝α・α8＝α＋α5＋α6＋α7 （01000111） の如くであり、これら以外の元も同様にしてベク
トル表示することができる。 そして、この場合対数テーブルのアドレス１〜
255は元αiの８ビツトの２進ベクトル表示であり、
対応するエントリは指数ｉの２進表示である。 また、真数テーブルは指数ｉをアドレスに用
い、エントリはαiの２進ベクトル表示である。 次に、第２図のエラーロケーシヨン多項式計算
器による実際の代数演算を各別に説明する。 (1) 加算 元αiおよびαjを加算する場合には、これら２つ
の元がＡレジスタ２０およびＢレジスタ２６を介
してエクスクルシブオアゲート２７により各ビツ
ト毎に排他的な論理和をとる。これによつて得ら
れる上記２つの元の和の結果はＣレジスタ１９を
介して上記作業用バツフア２２に転送される。 (2) ０であるか否かの検出 元αiが０であるか否かを調べる場合には、元αi
がＨレジスタ２８を介してオアゲート２９により
論理和がとられる。この結果はＭレジスタ３０を
介して上記作業用バツフア２２に転送される。こ
の場合、Ｍレジスタ３０の内容は元αiが０のとき
のみ０になる。 (3) 乗算 元αiおよびαjを乗算する場合には、先ずこれら
２つの元が０であるか否かが調べられる。若し、
いずれか一方の元が０であれば、実際に乗算する
までもなく、乗算結果は０である。しかるに、両
方とも０でない場合には、これらの元は上記対数
バツフア２４用のアドレスレジスタ３１に順次に
ロードされる。そして、対数バツフア２４からの
出力ｉおよびｊはＤレジスタ３２およびＥレジス
タ３３を介して１の補数加算器３４により、28−
１を法として１の補数加算が行なわれる。これに
よつて得られる結果ｉ＋ｊ＝ｔ mod（28−１）
はＬレジスタ３５を介して上記真数バツフア２５
用のアドレスレジスタ３６にロードされる。この
場合、真数バツフア２５のアドレス入力がｔであ
れば、その出力αtが乗算結果としてＧレジスタ３
７を介して上記作業用バツフア２２に転送され
る。 (4) 除算 元αjによるαiの除算（αi／αj）は基本的には上
記(3)の乗算の場合と同様であるが、上記Ｅレジス
タ３３の内容を上記Ｄレジスタ３２の内容から減
算せしめる点で異なつている。つまり、Ｅレジス
タ３３にある元αjの対数が補数化器３８により補
数化されてＦレジスタ３９を介して上記１の補数
加算器３４に送るようにした点である。そして、
以下(3)の乗算の場合と同様に処理されるものであ
るが、この場合真数バツフア２５の出力が求める
除算の結果つまり商となつているものである。 〔背景技術の問題点〕 しかしながら、以上のような従来のエラー訂正
装置は、そのエラーロケーシヨン多項式計算器に
おける代数演算のうち乗算および除算用として対
数バツフアおよび真数バツフアを必要とするもの
であるが、このために用いられるROM等のメモ
リ容量が膨大なものになるので、LSI化が阻害さ
れて大容量のメモリを外付けしなければならない
という不具合を生じていた。 これは、前述した例の如く１シンボル８ビツト
とした場合で255×８ビツト＝2040ビツトの
ROMが２つ必要になり、合計4080ビツトにもな
ることからして容易に窺い知れるところである。 つまり、従来より知られているガロア体におけ
る乗算装置および除算装置はそれらの元の対数お
よび真数を各別にテーブルの形式で記憶している
大容量メモリでなる対数バツフアや真数バツフア
を必要とするので、それだけ構成が複雑化して高
価格につくという問題を有していた。 〔発明の目的〕 そこで、この発明は以上のような点に鑑みてな
されたもので、特に大容量のメモリを必要とする
対数バツフアや真数バツフアを用いることなくガ
ロア体における乗算をなし得るようにし、以つて
構成の簡易化ならびに低価格化に寄与し得るよう
にした極めて良好なるガロア体における乗算装置
を提供することを目的としている。 〔発明の概要〕 すなわち、この発明によるガロア体における乗
算装置は、ガロア体GF（2m）の生成多項式Ｇ（ｘ）
の１根をαとする被乗数データＢ（α）（但し、Ｂ
（α）＝bn-1αm-1＋bn-2αm-2＋……＋b0）および乗
数データＣ（α）（但し、Ｃ（α）＝cn-1αm-1＋cn-2
αm-2＋……＋c0）の乗算をＢ（α）・Ｃ（α）＝αB
（α）＋Ｂ（α）（但し、＝cn-1αm-2＋cn-2
αm-4＋cn-3αm-6＋……＋c1，＝cn-2αm-2＋cn-4
αm-4＋cn-6αm-6＋…＋c0）なる第１の部分乗算
〔αB（α）〕および第２の部分乗算〔Ｂ（α）
〕の和の形に変換して処理するもので、前記第
１の部分乗算を第１のステツプで処理する第１の
手段と、前記第２の部分乗算を第２のステツプで
処理する第２の手段と、前記第１および第２の手
段の各部分乗算出力を加算する第３の手段とを具
備してなることにより、ハード化して構成を大幅
に簡易化すると共に、基本クロツク２ステツプで
処理し得るようにして処理時の短縮化を図つたこ
とを特徴としている。 〔発明の実施例〕 先ず、この発明が適用される光学式（CD形）
デジタルオーデイオデイスク（DAD）再生装置
の概要について説明する。 すなわち、第３図に示すようにデイスクモータ
１１１によつて回転駆動されるターンテーブル１
１２上に装着されたデイスク１１３は光学式ピツ
クアツプ１１４によつて再生される。この場合、
光学式ピツクアツプ１１４は半導体レーザ１１４
ａからの出射光をビームスプリツター１１４ｂ、
対物レンズ１１４ｃを介してデイスク１１３の信
号面に照射し、該デイスク１１３に所定の
（EFM）変調およびインタリーブを伴つた形態で
記録されている再生すべきオーデイオ信号のデジ
タル（PCM）化データに対応したピツト（反射
率の異なる凹凸）からの反射光を対物レンズ１１
４ｃ、ビームスプリツター１１４ｂを介して４分
割フオトデテクタ１１４ｄに導き、該４分割フオ
トデテクタ１１４ｄで光電変換された４つの再生
信号を外部に出力可能になされているもので、自
からはピツクアツプ送りモータ１１５によつてデ
イスク１１３の半径方向に直線駆動される。 そして、４分割フオトデテクタ１１４ｄからの
４つの再生信号はマトリクス回路１１６に供給さ
れて所定のマトリクス演算処理が施されることに
より、フオーカスエラー信号（Ｆ）、トラツキン
グエラー信号および高周波信号（RF）に分離さ
れる。 このうち、フオーカスエラー信号（Ｆ）はフオ
ーカスサーチ回路１１０からのフオーカスサーチ
信号と共に、前記光学式ピツクアツプ１１４のフ
オーカスサーボ系（FS）を駆動するのに供せら
れる。 また、トラツキングエラー信号（Ｔ）は後述す
るシステムコントローラ１１７を介して与えられ
るサーチ制御信号と共に、前記光学式ピツクアツ
プ１１４のトラツキングサーボ系（TS）を駆動
するのに且つ前記ピツクアツプ送りモータ１１５
を（リニアトラツキング）制御するのに供せられ
る。 そして、残る高周波信号（RF）が主再生信号
成分として再生信号処理系１１８に供給される。
すなわち、この再生信号処理系１１８は先ず再生
信号をスライスレベル（アイパターン）検出器１
１９によつて制御される波形整形回路１２０に導
いて不要なアナログ成分と必要とするデータ成分
を分離し、データ成分のみをPLL型でなる同期
クロツク再生回路１２１および第１の信号処理系
１２２のエツジ検出器１２２ａに供給する。 ここで、同期クロツク再生回路１２１からの同
期クロツクはデータ復調用として第１の信号処理
系１２２における同期信号分離用クロツク生成回
路１２２ｂに導かれて同期信号分離用クロツクを
生成するのに供せられる。 一方、上記エツジ検出器１２２ａを通つた再生
信号は同期信号検出器１２２ｃに導かれて上記同
期信号分離用クロツクにより同期信号が分離され
ると共に、復調回路１２２ｄに導かれて（EFM）
復調される。 このうち、同期信号は同期信号保護回路１２２
ｅを介して誤動作が生じないように保護された状
態で、上記同期信号分離用クロツクと共に入力デ
ータ処理用タイミング信号生成回路１２２ｆに導
かれる。 また、復調信号はデータバス入出力制御回路１
２２ｇを介して後述する第２の信号処理系１２３
の入出力制御回路１２３ａに供給されると共に、
そのうちのサブコードであるコントロール信号お
よび表示信号成分がコントロール表示処理回路１
２２ｈおよびサブコード処理回路１２２ｉに導か
れる。 そして、サブコード処理回路１２２ｉで必要な
エラー検出および訂正が施されたサブコードデー
タはシステムコントローラ用インターフエイス回
路１２２ｑを介してシステムコントローラ１１７
に供給される。 ここで、システムコントローラ１１７はマイク
ロコンピユータ，インタフエイス回路およびドラ
イバ用集積回路等を有してなり、コントロールス
イツチ１２４からの指令信号によりDAD再生装
置を所望の状態に制御すると共に、上述のサブコ
ード（例えば再生曲のインデツクス情報）を表示
器１２５に表示せしめるのに供せられている。 なお、上記入力データ処理用タイミング信号生
成回路１２２ｆからのタイミング信号はデータセ
レクト回路１２２ｊを介して上記データバス入出
力制御回路１２２ｇを制御するのに供せられると
共に、周波数検出器１２２ｋおよび位相検出器１
２２ｌならびにPWM変調器１２２ｍを介して上
記デイスクモータ１１１を線速度一定（CLV）
方式で駆動するための自動周波数制御（AFC）
および自動位相制御（APC）に供せられている。 この場合、位相検出器１２２ｌにはクリスタル
発振器１２２ｎからの発振信号に基いて動作する
システムクロツク生成回路１２２ｐからのシステ
ムクロツクが供給されている。 そして、第２の信号処理回路１２３の入出力制
御回路１２３ａを通つた復調データはエラー検出
および訂正または補正用のシンドローム検出器１
２３ｂ、エラーポインタ制御回路１２３ｃ，訂正
回路１２３ｄおよびデータ出力回路１２３ｅを介
して必要なエラー訂正、デインタリーブ、エラー
補正等の処理を受けてデジタル―アナログ（Ｄ／
Ａ）変換器１２６に導出される。 この場合、外部メモリ制御回路１２３ｆは上記
データセレクト回路１２２ｊと共働して訂正に必
要なデータが書き込まれている外部メモリ１２７
を制御することにより、上記入出力制御回路１２
３ａを介して訂正に必要なデータを取り込む如く
なされている。 また、タイミングコントロール回路１２３ｇは
前記システムクロツク生成回路１２２ｐからのシ
ステムクロツクに基いてエラー訂正および補正な
らびにＤ／Ａ変換に必要なタイミングコントロー
ル信号を供給する如くなされている。 また、ミユーテイング（検出）制御回路１２３
ｈは上記エラーポインタ制御回路１２３ｃからの
出力またはシステムコントローラ１１７を介して
与えられるコントロール信号に基いてエラー補正
時およびDAD再生装置の動作開始、終了時等に
必要となる所定のミユーテイング制御をなすのに
供せられている。 そして、上記Ｄ／Ａ変換器１２６でアナログ信
号に戻されたオーデイオ信号はローパスフイルタ
１２８、増幅器１２９を介してスピーカ１３０を
奏鳴するのに供せられる。 次に、以上のようなDAD再生装置に適用され
たエラー訂正回路について説明する。 先ず、原理について述べると、ガロア体GF
（28）における２重訂正BCH符号は多項式表現し
た場合 U0，U1，U2……Un-1，P0，P1，P2，P3……(21) の如く表わされる。但し、U0〜Un-1は情報シン
ボルで、１シンボルが８ビツトのものがｍ個まと
められているものとする。また、P0〜P3はパリ
テイシンボルで、上記ｍ個の情報シンボルに４個
分のパリテイシンボルが付加されているものとす
る。 つまり、(21)式の表現はパリテイシンボルを情
報シンボルと訂正上同一視し得ることによるもの
で、これは Wn+3，Wn+2，Wn+1……W3，W2，W1，W0……(22) の如く書き換えられる。 これによつて、送信多項式Ｆ（ｘ）は Ｆ（ｘ）＝Wn+3xm+3＋Wn+2xm+2＋……＋W1x＋W0……(
23) の如く表わすことができ、且つ受信多項式Ｆ
（ｘ）′は Ｆ（ｘ）′＝Wn+3′xm+3＋Wn+2′xm+2＋……＋W1′x
＋W0……(24) の如く表わすことができる。 ここで、ガロア体GF（28）の生成多項式Ｇ（ｘ）
の１根をαとすると、上記Ｆ（ｘ）は２訂訂正
BCH符号において、１，α，α2，α3，の４根を
有することになるから
Ｆ(1)＝n+1 〓i=0 W1＝０ Ｆ（α）＝n+3 〓i=0 Wiαi＝０ Ｆ（α2）＝n+3 〓i=0 Wi（α2）i＝０ Ｆ（α3）＝n+3 〓i=0 Wi（α3）i＝０ (25) の如くなる。 つまり、送信側では上記(25)式を満足し得るよ
うにパリテイシンボルを決定して伝送するもので
あるが、受信側では伝送系の介在によつて必ずし
もそのままの形で受信し得ないのをエラーとして
訂正するものである。 この場合、上述した２重訂正BCH符号によれ
ば、合計ｍ＋４個のシンボル中、２個までのシン
ボルエラーを訂正することが可能となる。 今、上記受信多項式中WiとWjとの２個のシン
ボルにエラーを起こして W′i＝Wi＋ei W′j＝Wj＋ej になつたとする。この場合、W′iとW′j以外のシン
ボルにはエラーがなく W′k＝Wk （但しｋ＝０〜ｍ＋４ ｋ≠ｉ，ｋ≠ｊ） で表わされるものとする。 ここで、受信多項式F′（ｘ）について送信時と
同様に１，α，α2，α3を代入してみると
F′(1)＝ei＋ej＝S0 F′（α）＝eiαj＋ejαj＝S1 F′（α2）＝eiα2i＋ejα2j＝S2 F′（α3）＝eiα3i＋ejα3j＝S3 (26) のようになる。 ここで、S0〜S3はシンドロームと称されるもの
で、２個のシンボルエラーの場合には(26)式の情
報内容を有していることになる。 ところで、BCH符号理論において２重訂正の
場合は前述したようなエラーロケーシヨン多項式
を用いる方法があり、これは σ1＝αi＋αj＝S0S3＋S1S2／S1 2＋S0S2 ……(27) σ2＝αiαj＝S1S3＋S2 2／S1 2＋S0S2 ……(28) ｆ（ｘ）＝x2＋σ1x＋σ2 ……(29) の如くである。 つまり、(27)，(28)でシンドロームS0〜S3によ
つてσ1とσ2とを求めて(29)式に代入するものであ
るが、この場合(29)式のｘについてはα0〜αm+3ま
で順に代入するものとする。 ここで、(29)式はαiとαjでｆ（ｘ）＝０となる筈
であるから、ｆ（ｘ）＝０となる点を求めれば、２
個のエラーロケーシヨンを求めることができるよ
うになる。 次に、エラーパターンを求める方法は判明して
いるとαiとαjより、上記(26)式を用いて ei＝S0αj＋S1／αi＋αj ……(30A) ej＝S0＋ei ……(30B) の如く遂行することができる。 ところで、このようなエラーロケーシヨン（多
項式）ならびにエラーパターンを求める際に必要
となるガロア体における乗算や除算を前述したよ
うな大容量メモリを用いることなくハード的な構
成でなし得るようにすることにこの発明の狙いが
ある。 しかるに、この場合大容量のメモリを用いない
で、ｇ（ｘ）を生成多項式とするガロア体におけ
る乗算および除算をなすにしても、乗算が例えば
後述するようにして比較的簡単になし得るもの
の、除算はやはり困難であるので、でき得る限り
除算を減少した方が望ましい。 そこで、次に上述したエラーロケーシヨンおよ
びエラーパターンを求める方法について除算を減
少する方向で展開してみる。 先ず、エラーロケーシヨン（多項式）の生成に
ついてであるが、上記(27)，(28)式についてそれ
ぞれの右辺の分母が等しいから
Sa＝S2 1＋S0S2 Sb＝S0S3＋S1S2 Sc＝S1S3＋S2 2 ……(31) のようにおくと、(27)，(28)式は σ1＝αi＋αj＝Sb／Sa ……(32) σ2＝αiαj＝Sc／Sa ……(33) の如くなる。この(32)，(33)式を(29)式に代入する
と ｆ（ｘ）＝x2＋Sb／Saｘ＋Sc／Sa ……(34) となる。 そして、この(34)式はｘにα0〜αm+3まで代入し
てｆ（ｘ）＝０となることをチエツクすればエラー
ロケーシヨンが求まるのであるから、これを次の
ように変形して f′（ｘ）＝Saｆ（ｘ）＝Sax2＋Sbｘ＋Sc ……(35) としても、該f′（ｘ）にα0〜αm+3を代入してやる
ことによりf′（ｘ）＝０となる点でαiとαjとが求ま
ることになる筈である。 つまり、このようにしてエラーロケーシヨン多
項式を求める際には除算をなくすことが可能とな
る。 次に、エラーパターンの生成についてである
が、上記(30A)式でeiを求める際に必要となる除
算（S0αj＋S1／αi＋αj）について、分母であるαi＋
αjの 逆数（αi＋αj）-1が予め判明していれば ei＝（S0αj＋S1）（αi＋αj）-1……(30A′) なる乗算に帰着せしめることが可能となる。 そこで、次に上記逆数（αi＋αj）-1を求める方
法についてみてみるに、上記(35)式に(32)式を入
れると f′（ｘ）＝Sax2＋Sa（αi＋αj）ｘ＋Sc ……(36) となる。そして、かかる(36)式のｘにα0〜αm+3ま
で代入する操作が上記エラーロケーシヨンを求め
るのに必要であることになるが、このα0〜αm+3ま
でを代入する間に該(36)式のSa（αi＋αj）ｘなる項
に着眼して Sa（αi＋αj）ｘ＝αr ……(37) となるｘを求める操作をしてやる。 具体的には、今、ｍ＝28とすると、(37)式のｘ
にはα0〜α31まで代入されることになるが、ガロ
ア体GF（28）では α28-1＝α255＝１ が最大で、この場合α0〜α254の巡回符号となるか
らα0〜α254までしか扱うことはない。 そして、今α0〜α31まで代入してみるのである
から、７＜255／32＜８からα32m→α-32m（但しｍ
＝０，１……７）までの逆数データ８個を下表の
ようにコード化しておくものとする。
イスク（DAD）再生装置等に用いられるエラー
訂正符号の復号用に好適するガロア体における乗
算装置の改良に関する。 〔発明の技術的背景〕 周知のように、近時開発されている光学式
DAD再生装置（特にはCD：コンパクトデイスク
形）においては、そのエラー訂正符号としてクロ
スインターリーブリードソロモン符号（CIRC）
を採用している。 すなわち、これは従来より知られている代表的
なランダムエラー訂正符号のうちで最もエラー訂
正能力が高いものとして広範に定義されている
BCH符号の一種であるリードソロモン符号を用
いるものであるが、それにバーストエラーに対し
ても高い訂正能力を持たせるべくクロスインタリ
ーブなる信号処理を伴わせるようにしたものであ
る。 ところで、リードソロモン符号の復号つまりエ
ラー訂正はBCH符号のそれと同様になすことが
できる。 今、符号長（ｎ）、情報シンボル（ｋ）個、検
査シンボル（ｎ−ｋ）個からなるリードソロモン
符号について、その復号法を調べてみるものとす
る。但し、上記各シンボルは（ｍ）個の２進ビツ
トつまり2m個の元を有する有限体であるガロア体
GF2mの元である。 そして、この場合（ｔ）重エラー訂正リードソ
ロモン符号の生成多項式ｇ（ｘ）は、（α）をガロ
ア体GF（2m）の原始元として次の(1)式または(2)式
のように表わされる。 ｇ（ｘ）＝（ｘ＋α）（ｘ＋α2） ……（ｘ＋α2t） ……(1) ｇ（ｘ）＝（ｘ＋α0）（ｘ＋α） ……（ｘ＋α2t-） ……(2) また、送信符号語をＣ（ｘ）、受信符号語をＲ
（ｘ）で表わし、且つエラー多項式をＥ（ｘ）とす
ると、これらの間には次のような関係が成立す
る。 Ｒ（ｘ）＝Ｃ（ｘ）＋Ｅ（ｘ） ……(3) この場合、多項式の係数はガロア体GF（2m）に
含まれており、エラー多項式Ｅ（ｘ）はエラーロ
ケーシヨンおよび値（大きさ）に対応する項だけ
を含んでいる。 従つて、位置xjにおけるエラー値をYjとすると
Ｅ（ｘ）＝〓j Yjxj ……(4) となり、該(4)式でΣはエラーのすべての位置にわ
たる総和を意味している。 ここで、シンドロームSiを Si＝Ｒ（αi） 〔但しｉ＝０，１……2t−１〕 ……(5) の如く定義したとすると、上記(3)式より Si＝Ｃ（αi）＋Ｅ（αi） となる。 この場合、Ｃ（ｘ）はｇ（ｘ）で常に割り切れる
ので Ｃ（αi）＝０ であるから Si＝Ｅ（αi） となる。そこで、上記(4)式より
Si＝Ｅ（αi）＝〓j Yj（αi）j ＝〓j YjXi j ……(6) と表わすことができる。但しαj＝Xjとおいたもの
で、Xjはαjにおけるエラーロケーシヨンを表わし
ている。 ここで、エラーロケーシヨン多項式σ（ｘ）は、
エラー数をｅとして σ（ｘ）＝〓ｉ（ｘ−Xi） ＝xe＋σ1xe-1＋………＋σe ……(7) と定義される。 また、(7)式のσ1〜σeはシンドロームSiとの間で
次のように関係付けられる。 Si+e＋σ1Si+e-1 ＋……σe-1Si+1＋σeSi ……(8) つまり、以上のようなリードソロモン符号の復
号手順は （） (5)式によりシンドロームSiを計算する。 （） (8)式によりエラーロケーシヨン多項式の
係数σ1〜σeを計算する。 （） (7)式によりエラーロケーシヨン多項式の
根Xjを求める。 （） (6)式によりエラー値Yjを求め、(4)式に
よりエラー多項式を求める。 （） (3)式によりエラー訂正を行なう。 なる（）〜（）の手順に帰着せしめられる。 次に、以上のような復号手順によるエラー訂正
の具体例として、１ブロツクデータに４個の検査
シンボルを用いた場合について説明する。 すなわち、この場合の生成多項式ｇ（ｘ）は ｇ（ｘ）＝（ｘ＋１）（ｘ＋α）（ｘ＋α2）（ｘ＋
α3） となり、２重エラーまでの訂正が可能となるもの
であるが、ここではそれを〔Ａ〕，〔Ｂ〕なる二つ
の方式によつた場合について各別に述べるものと
する。 〔方式 Ａ〕 （） シンドロームS0〜S3を計算する。 （） (8)式をｅ＝１，ｅ＝２について書き直す
と、ｅ＝１の場合には S1＋σ1S0＝０ S2＋σ1S1＝０ S3＋σ1S2＝０ ……(9) となる。また、ｅ＝２の場合には
S2＋σ1S1＋σ2S0＝０ S3＋σ1S2＋σ2S1＝０ ……(10) となる。 ここで、実際の復号器がｅ＝１の場合から動作
を始めるものとすると、先ず連立方程式(9)を満足
する解σ1を求めなければならない。そして、この
解が存在しなければ、復号器は次にｅ＝２の場合
について連立方程式(10)を満足する解σ1，σ2を求め
なければならない。なお、ここでも解が得られな
い場合はｅ≧３とみなすことになる。 (9)式の解σ1は σ1＝S1／S0＝S2／S1＝S3／S2 として求め、(10)式の解σ1，σ2は σ1＝S0S3＋S1S2／S1 2＋S0S2，σ2＝S1S3＋S2 2／S1 2
＋S0S2 として求める。 （） 以上のようにしてエラーロケーシヨン多
項式の係数σiが得られたならば、次に(7)式によ
りエラーロケーシヨン多項式の根を求める。 先ず、ｅ＝１の場合は σ（ｘ）＝ｘ＋σ1＝０，∴X1＝σ1 となる。また、ｅ＝２の場合は σ（ｘ）＝x2＋σ1x＋σ2＝０ ……(11) として、該(11)式にガロア体GF（2m）の元を順次に
代入してその解を求めればよく、今この根をを
X1，X2とする。 （） エラーロケーシヨン多項式の根が求まつ
たなら、次に(6)式によりエラー値Yjを求める。 先ず、ｅ＝１の場合は S0＝Y1 ∴Y1＝S0 となる。また、ｅ＝２の場合は
S0＝Y1＋Y2 S1＝Y1X1＋Y2X2 より ∴Y1＝X2S0＋S1／X1＋X2 Y2＝S0＋Y1 （） 上述のようにして求めたエラー値Y1，
Y2により訂正を行なう。 ところで、ポインターイレージヤー法等によつ
てエラーロケーシヨンの値を正確に知ることがで
きる場合には、上述した２重エラー訂正用のリー
ドソロモン符号によつて４重エラーまでの訂正が
可能となるものであり、それが後述する〔方式
Ｂ〕である。 〔方式 Ｂ〕 （） シンドロームS0〜S3を計算する。 （）（） エラーロケーシヨンを別の検出方
法で知る。 （） (6)式によりエラー値を求める。 先ずｅ＝１，ｅ＝２の場合は上述した〔方式
Ａ〕の（）と同様である。 そして、ｅ＝３の場合 S0＝Y1＋Y2＋Y3 S1＝Y1X1＋Y2X2＋Y3X3 S2＝Y1X1 2＋Y2X2 2＋Y3X3 2 を解いて Y1＝（S2＋X3S1）＋X2（S1＋X3S0）／（X1＋X2）（X1
＋X3） Y2＝（S1＋X3S0）＋Y1（X1＋X3）／（X2＋X3） Y3＝S0＋Y1＋Y2 となる。 また、ｅ＝４の場合は S0＝Y1＋Y2＋Y3＋Y4 S1＝Y1X1＋Y2X2＋Y3X3＋Y4X4 S2＝Y1X1 2＋Y2X2 2＋Y3X3 2＋Y4X4 2 S3＝Y1X1 3＋Y2X2 3＋Y3X3 3＋Y4X4 3 を解いて Y1＝｛（S0X4＋S1）X3＋（S1X4＋S2）｝X2＋（S1X4
＋S2）X3＋（S2X4＋S3）／（X1＋X2）（X1＋X3）（X1＋
X4） Y2＝（S0X4＋S1）X3＋（S1X4＋S2）＋Y1（X1＋X3）
（X1＋X4）／（X2＋X3）（X2＋X4） Y3＝（S0X4＋S1）＋Y1（X1＋X4）＋Y2（X2＋X4）／
（X3＋X4） Y4＝S0＋Y1＋Y2＋Y3 となる。 （） 上述のようにして求めたY1〜Y4により
訂正を行なう。 第１図は以上のような原理に基くリードソロモ
ン符号の実際の復号システムでなるエラー訂正回
路を示す概略構成図である。すなわち、入力端
（IN）を介して導かれる被訂正用のデータ（エラ
ー訂正用としてリードソロモン符号が用いられて
いることは勿論である）は二分されて、一方が後
述する復号動作の間データバツフア１１に記憶さ
れると共に、他方が復号動作をなすためのシンド
ローム計算器１２以下に導かれる。 そして、シンドローム計算器１２で計算された
シンドロームはシンドロームバツフア１３に記憶
される。 ここで、シンドロームバツフア１３の出力部に
接続されたオアゲート１４はエラーの有無を指示
するもので、エラーがあると前述したような手順
によつてエラー訂正動作を開始することになる。 つまり、エラーロケーシヨン多項式計算器１５
がエラーロケーシヨン多項式σ（ｘ）の係数を計
算し、エラーロケーシヨン計算器１６がエラーロ
ケーシヨン多項式の根を計算し、エラー値計算器
１７がエラー値を計算し、これらのエラーロケー
シヨンおよびエラー値により上記データバツフア
１１から出力されるデータを訂正するものであ
る。 ところで、このような復号システムの各計算器
１２，１５，１６，１７は０か否かの検出ならび
に必要な加算、乗算および除算等の代数演算をな
すものであるが、これらについての具体例として
従来第２図に示すように構成されたエラーロケー
シヨン多項式計算器（特公昭56―20575号）が知
られている。 すなわち、第２図において２１はシンドローム
バツフアであつて、シンドロームSiを記憶するた
めのRAMでなり、該シンドロームバツフア２１
にはガロア体GF（2m）の元である各シンドローム
がそれぞれｍビツトの２進形式で記憶される。 また、２２は作業用バツフアであつて、エラー
ロケーシヨン多項式の係数を計算する際に、代数
演算の中間結果および最終結果を記憶するための
RAMでなり、後の演算で使用される部分結果も
該作業用バツフア２２に記憶される。 そして、２３は代数演算の順序を指示する順序
制御装置であつて、上記シンドロームバツフア２
１および作業用バツフア２２に対してアドレスを
供給して適切な記憶位置をアクセスすると共に、
実行された代数演算結果を調べて次の適切な演算
へ分岐せしめるのに供せられる。 さらに、２４，２５はそれぞれガロア体GF
（2m）の元の対数および真数を各別にテーブルの
形式で記憶しているROMでなる対数バツフアお
よび真数バツフアである。 ここで、前者の対数バツフア２４のアドレスは
元αiの２進表示であり、そのエントリーはαを底
とするαの対数すなわちｉであるが、後者の真数
バツフア２５のアドレスｉにおけるエントリーは
αiの２進表示である。 例えばガロア体GF（28）の法多項式Ｆ（ｘ）を Ｆ（ｘ）＝x8＋x6＋x5＋x4＋１ とすると、その０以外の元はＦ（ｘ）＝０の根αの
べき乗またはα0〜α7までの線形結合
7 〓i=0 aiαi （但しai＝０または１） で表わすことができる。 また、この場合a0〜a7までの８個の係数を取り
出して２進ベクトルとして表わすこともできる。 例えば α1＝０・α0＋１・α1＋０・α2＋０・α3＋０・α4
＋０・α5＋０・α6＋０・α7 ＝（01000000） α7＝０・α0＋……＋０・α6＋１・α7 ＝（00000001） α8＝１＋α4＋α5＋α6 （10001110） α9＝α・α8＝α＋α5＋α6＋α7 （01000111） の如くであり、これら以外の元も同様にしてベク
トル表示することができる。 そして、この場合対数テーブルのアドレス１〜
255は元αiの８ビツトの２進ベクトル表示であり、
対応するエントリは指数ｉの２進表示である。 また、真数テーブルは指数ｉをアドレスに用
い、エントリはαiの２進ベクトル表示である。 次に、第２図のエラーロケーシヨン多項式計算
器による実際の代数演算を各別に説明する。 (1) 加算 元αiおよびαjを加算する場合には、これら２つ
の元がＡレジスタ２０およびＢレジスタ２６を介
してエクスクルシブオアゲート２７により各ビツ
ト毎に排他的な論理和をとる。これによつて得ら
れる上記２つの元の和の結果はＣレジスタ１９を
介して上記作業用バツフア２２に転送される。 (2) ０であるか否かの検出 元αiが０であるか否かを調べる場合には、元αi
がＨレジスタ２８を介してオアゲート２９により
論理和がとられる。この結果はＭレジスタ３０を
介して上記作業用バツフア２２に転送される。こ
の場合、Ｍレジスタ３０の内容は元αiが０のとき
のみ０になる。 (3) 乗算 元αiおよびαjを乗算する場合には、先ずこれら
２つの元が０であるか否かが調べられる。若し、
いずれか一方の元が０であれば、実際に乗算する
までもなく、乗算結果は０である。しかるに、両
方とも０でない場合には、これらの元は上記対数
バツフア２４用のアドレスレジスタ３１に順次に
ロードされる。そして、対数バツフア２４からの
出力ｉおよびｊはＤレジスタ３２およびＥレジス
タ３３を介して１の補数加算器３４により、28−
１を法として１の補数加算が行なわれる。これに
よつて得られる結果ｉ＋ｊ＝ｔ mod（28−１）
はＬレジスタ３５を介して上記真数バツフア２５
用のアドレスレジスタ３６にロードされる。この
場合、真数バツフア２５のアドレス入力がｔであ
れば、その出力αtが乗算結果としてＧレジスタ３
７を介して上記作業用バツフア２２に転送され
る。 (4) 除算 元αjによるαiの除算（αi／αj）は基本的には上
記(3)の乗算の場合と同様であるが、上記Ｅレジス
タ３３の内容を上記Ｄレジスタ３２の内容から減
算せしめる点で異なつている。つまり、Ｅレジス
タ３３にある元αjの対数が補数化器３８により補
数化されてＦレジスタ３９を介して上記１の補数
加算器３４に送るようにした点である。そして、
以下(3)の乗算の場合と同様に処理されるものであ
るが、この場合真数バツフア２５の出力が求める
除算の結果つまり商となつているものである。 〔背景技術の問題点〕 しかしながら、以上のような従来のエラー訂正
装置は、そのエラーロケーシヨン多項式計算器に
おける代数演算のうち乗算および除算用として対
数バツフアおよび真数バツフアを必要とするもの
であるが、このために用いられるROM等のメモ
リ容量が膨大なものになるので、LSI化が阻害さ
れて大容量のメモリを外付けしなければならない
という不具合を生じていた。 これは、前述した例の如く１シンボル８ビツト
とした場合で255×８ビツト＝2040ビツトの
ROMが２つ必要になり、合計4080ビツトにもな
ることからして容易に窺い知れるところである。 つまり、従来より知られているガロア体におけ
る乗算装置および除算装置はそれらの元の対数お
よび真数を各別にテーブルの形式で記憶している
大容量メモリでなる対数バツフアや真数バツフア
を必要とするので、それだけ構成が複雑化して高
価格につくという問題を有していた。 〔発明の目的〕 そこで、この発明は以上のような点に鑑みてな
されたもので、特に大容量のメモリを必要とする
対数バツフアや真数バツフアを用いることなくガ
ロア体における乗算をなし得るようにし、以つて
構成の簡易化ならびに低価格化に寄与し得るよう
にした極めて良好なるガロア体における乗算装置
を提供することを目的としている。 〔発明の概要〕 すなわち、この発明によるガロア体における乗
算装置は、ガロア体GF（2m）の生成多項式Ｇ（ｘ）
の１根をαとする被乗数データＢ（α）（但し、Ｂ
（α）＝bn-1αm-1＋bn-2αm-2＋……＋b0）および乗
数データＣ（α）（但し、Ｃ（α）＝cn-1αm-1＋cn-2
αm-2＋……＋c0）の乗算をＢ（α）・Ｃ（α）＝αB
（α）＋Ｂ（α）（但し、＝cn-1αm-2＋cn-2
αm-4＋cn-3αm-6＋……＋c1，＝cn-2αm-2＋cn-4
αm-4＋cn-6αm-6＋…＋c0）なる第１の部分乗算
〔αB（α）〕および第２の部分乗算〔Ｂ（α）
〕の和の形に変換して処理するもので、前記第
１の部分乗算を第１のステツプで処理する第１の
手段と、前記第２の部分乗算を第２のステツプで
処理する第２の手段と、前記第１および第２の手
段の各部分乗算出力を加算する第３の手段とを具
備してなることにより、ハード化して構成を大幅
に簡易化すると共に、基本クロツク２ステツプで
処理し得るようにして処理時の短縮化を図つたこ
とを特徴としている。 〔発明の実施例〕 先ず、この発明が適用される光学式（CD形）
デジタルオーデイオデイスク（DAD）再生装置
の概要について説明する。 すなわち、第３図に示すようにデイスクモータ
１１１によつて回転駆動されるターンテーブル１
１２上に装着されたデイスク１１３は光学式ピツ
クアツプ１１４によつて再生される。この場合、
光学式ピツクアツプ１１４は半導体レーザ１１４
ａからの出射光をビームスプリツター１１４ｂ、
対物レンズ１１４ｃを介してデイスク１１３の信
号面に照射し、該デイスク１１３に所定の
（EFM）変調およびインタリーブを伴つた形態で
記録されている再生すべきオーデイオ信号のデジ
タル（PCM）化データに対応したピツト（反射
率の異なる凹凸）からの反射光を対物レンズ１１
４ｃ、ビームスプリツター１１４ｂを介して４分
割フオトデテクタ１１４ｄに導き、該４分割フオ
トデテクタ１１４ｄで光電変換された４つの再生
信号を外部に出力可能になされているもので、自
からはピツクアツプ送りモータ１１５によつてデ
イスク１１３の半径方向に直線駆動される。 そして、４分割フオトデテクタ１１４ｄからの
４つの再生信号はマトリクス回路１１６に供給さ
れて所定のマトリクス演算処理が施されることに
より、フオーカスエラー信号（Ｆ）、トラツキン
グエラー信号および高周波信号（RF）に分離さ
れる。 このうち、フオーカスエラー信号（Ｆ）はフオ
ーカスサーチ回路１１０からのフオーカスサーチ
信号と共に、前記光学式ピツクアツプ１１４のフ
オーカスサーボ系（FS）を駆動するのに供せら
れる。 また、トラツキングエラー信号（Ｔ）は後述す
るシステムコントローラ１１７を介して与えられ
るサーチ制御信号と共に、前記光学式ピツクアツ
プ１１４のトラツキングサーボ系（TS）を駆動
するのに且つ前記ピツクアツプ送りモータ１１５
を（リニアトラツキング）制御するのに供せられ
る。 そして、残る高周波信号（RF）が主再生信号
成分として再生信号処理系１１８に供給される。
すなわち、この再生信号処理系１１８は先ず再生
信号をスライスレベル（アイパターン）検出器１
１９によつて制御される波形整形回路１２０に導
いて不要なアナログ成分と必要とするデータ成分
を分離し、データ成分のみをPLL型でなる同期
クロツク再生回路１２１および第１の信号処理系
１２２のエツジ検出器１２２ａに供給する。 ここで、同期クロツク再生回路１２１からの同
期クロツクはデータ復調用として第１の信号処理
系１２２における同期信号分離用クロツク生成回
路１２２ｂに導かれて同期信号分離用クロツクを
生成するのに供せられる。 一方、上記エツジ検出器１２２ａを通つた再生
信号は同期信号検出器１２２ｃに導かれて上記同
期信号分離用クロツクにより同期信号が分離され
ると共に、復調回路１２２ｄに導かれて（EFM）
復調される。 このうち、同期信号は同期信号保護回路１２２
ｅを介して誤動作が生じないように保護された状
態で、上記同期信号分離用クロツクと共に入力デ
ータ処理用タイミング信号生成回路１２２ｆに導
かれる。 また、復調信号はデータバス入出力制御回路１
２２ｇを介して後述する第２の信号処理系１２３
の入出力制御回路１２３ａに供給されると共に、
そのうちのサブコードであるコントロール信号お
よび表示信号成分がコントロール表示処理回路１
２２ｈおよびサブコード処理回路１２２ｉに導か
れる。 そして、サブコード処理回路１２２ｉで必要な
エラー検出および訂正が施されたサブコードデー
タはシステムコントローラ用インターフエイス回
路１２２ｑを介してシステムコントローラ１１７
に供給される。 ここで、システムコントローラ１１７はマイク
ロコンピユータ，インタフエイス回路およびドラ
イバ用集積回路等を有してなり、コントロールス
イツチ１２４からの指令信号によりDAD再生装
置を所望の状態に制御すると共に、上述のサブコ
ード（例えば再生曲のインデツクス情報）を表示
器１２５に表示せしめるのに供せられている。 なお、上記入力データ処理用タイミング信号生
成回路１２２ｆからのタイミング信号はデータセ
レクト回路１２２ｊを介して上記データバス入出
力制御回路１２２ｇを制御するのに供せられると
共に、周波数検出器１２２ｋおよび位相検出器１
２２ｌならびにPWM変調器１２２ｍを介して上
記デイスクモータ１１１を線速度一定（CLV）
方式で駆動するための自動周波数制御（AFC）
および自動位相制御（APC）に供せられている。 この場合、位相検出器１２２ｌにはクリスタル
発振器１２２ｎからの発振信号に基いて動作する
システムクロツク生成回路１２２ｐからのシステ
ムクロツクが供給されている。 そして、第２の信号処理回路１２３の入出力制
御回路１２３ａを通つた復調データはエラー検出
および訂正または補正用のシンドローム検出器１
２３ｂ、エラーポインタ制御回路１２３ｃ，訂正
回路１２３ｄおよびデータ出力回路１２３ｅを介
して必要なエラー訂正、デインタリーブ、エラー
補正等の処理を受けてデジタル―アナログ（Ｄ／
Ａ）変換器１２６に導出される。 この場合、外部メモリ制御回路１２３ｆは上記
データセレクト回路１２２ｊと共働して訂正に必
要なデータが書き込まれている外部メモリ１２７
を制御することにより、上記入出力制御回路１２
３ａを介して訂正に必要なデータを取り込む如く
なされている。 また、タイミングコントロール回路１２３ｇは
前記システムクロツク生成回路１２２ｐからのシ
ステムクロツクに基いてエラー訂正および補正な
らびにＤ／Ａ変換に必要なタイミングコントロー
ル信号を供給する如くなされている。 また、ミユーテイング（検出）制御回路１２３
ｈは上記エラーポインタ制御回路１２３ｃからの
出力またはシステムコントローラ１１７を介して
与えられるコントロール信号に基いてエラー補正
時およびDAD再生装置の動作開始、終了時等に
必要となる所定のミユーテイング制御をなすのに
供せられている。 そして、上記Ｄ／Ａ変換器１２６でアナログ信
号に戻されたオーデイオ信号はローパスフイルタ
１２８、増幅器１２９を介してスピーカ１３０を
奏鳴するのに供せられる。 次に、以上のようなDAD再生装置に適用され
たエラー訂正回路について説明する。 先ず、原理について述べると、ガロア体GF
（28）における２重訂正BCH符号は多項式表現し
た場合 U0，U1，U2……Un-1，P0，P1，P2，P3……(21) の如く表わされる。但し、U0〜Un-1は情報シン
ボルで、１シンボルが８ビツトのものがｍ個まと
められているものとする。また、P0〜P3はパリ
テイシンボルで、上記ｍ個の情報シンボルに４個
分のパリテイシンボルが付加されているものとす
る。 つまり、(21)式の表現はパリテイシンボルを情
報シンボルと訂正上同一視し得ることによるもの
で、これは Wn+3，Wn+2，Wn+1……W3，W2，W1，W0……(22) の如く書き換えられる。 これによつて、送信多項式Ｆ（ｘ）は Ｆ（ｘ）＝Wn+3xm+3＋Wn+2xm+2＋……＋W1x＋W0……(
23) の如く表わすことができ、且つ受信多項式Ｆ
（ｘ）′は Ｆ（ｘ）′＝Wn+3′xm+3＋Wn+2′xm+2＋……＋W1′x
＋W0……(24) の如く表わすことができる。 ここで、ガロア体GF（28）の生成多項式Ｇ（ｘ）
の１根をαとすると、上記Ｆ（ｘ）は２訂訂正
BCH符号において、１，α，α2，α3，の４根を
有することになるから
Ｆ(1)＝n+1 〓i=0 W1＝０ Ｆ（α）＝n+3 〓i=0 Wiαi＝０ Ｆ（α2）＝n+3 〓i=0 Wi（α2）i＝０ Ｆ（α3）＝n+3 〓i=0 Wi（α3）i＝０ (25) の如くなる。 つまり、送信側では上記(25)式を満足し得るよ
うにパリテイシンボルを決定して伝送するもので
あるが、受信側では伝送系の介在によつて必ずし
もそのままの形で受信し得ないのをエラーとして
訂正するものである。 この場合、上述した２重訂正BCH符号によれ
ば、合計ｍ＋４個のシンボル中、２個までのシン
ボルエラーを訂正することが可能となる。 今、上記受信多項式中WiとWjとの２個のシン
ボルにエラーを起こして W′i＝Wi＋ei W′j＝Wj＋ej になつたとする。この場合、W′iとW′j以外のシン
ボルにはエラーがなく W′k＝Wk （但しｋ＝０〜ｍ＋４ ｋ≠ｉ，ｋ≠ｊ） で表わされるものとする。 ここで、受信多項式F′（ｘ）について送信時と
同様に１，α，α2，α3を代入してみると
F′(1)＝ei＋ej＝S0 F′（α）＝eiαj＋ejαj＝S1 F′（α2）＝eiα2i＋ejα2j＝S2 F′（α3）＝eiα3i＋ejα3j＝S3 (26) のようになる。 ここで、S0〜S3はシンドロームと称されるもの
で、２個のシンボルエラーの場合には(26)式の情
報内容を有していることになる。 ところで、BCH符号理論において２重訂正の
場合は前述したようなエラーロケーシヨン多項式
を用いる方法があり、これは σ1＝αi＋αj＝S0S3＋S1S2／S1 2＋S0S2 ……(27) σ2＝αiαj＝S1S3＋S2 2／S1 2＋S0S2 ……(28) ｆ（ｘ）＝x2＋σ1x＋σ2 ……(29) の如くである。 つまり、(27)，(28)でシンドロームS0〜S3によ
つてσ1とσ2とを求めて(29)式に代入するものであ
るが、この場合(29)式のｘについてはα0〜αm+3ま
で順に代入するものとする。 ここで、(29)式はαiとαjでｆ（ｘ）＝０となる筈
であるから、ｆ（ｘ）＝０となる点を求めれば、２
個のエラーロケーシヨンを求めることができるよ
うになる。 次に、エラーパターンを求める方法は判明して
いるとαiとαjより、上記(26)式を用いて ei＝S0αj＋S1／αi＋αj ……(30A) ej＝S0＋ei ……(30B) の如く遂行することができる。 ところで、このようなエラーロケーシヨン（多
項式）ならびにエラーパターンを求める際に必要
となるガロア体における乗算や除算を前述したよ
うな大容量メモリを用いることなくハード的な構
成でなし得るようにすることにこの発明の狙いが
ある。 しかるに、この場合大容量のメモリを用いない
で、ｇ（ｘ）を生成多項式とするガロア体におけ
る乗算および除算をなすにしても、乗算が例えば
後述するようにして比較的簡単になし得るもの
の、除算はやはり困難であるので、でき得る限り
除算を減少した方が望ましい。 そこで、次に上述したエラーロケーシヨンおよ
びエラーパターンを求める方法について除算を減
少する方向で展開してみる。 先ず、エラーロケーシヨン（多項式）の生成に
ついてであるが、上記(27)，(28)式についてそれ
ぞれの右辺の分母が等しいから
Sa＝S2 1＋S0S2 Sb＝S0S3＋S1S2 Sc＝S1S3＋S2 2 ……(31) のようにおくと、(27)，(28)式は σ1＝αi＋αj＝Sb／Sa ……(32) σ2＝αiαj＝Sc／Sa ……(33) の如くなる。この(32)，(33)式を(29)式に代入する
と ｆ（ｘ）＝x2＋Sb／Saｘ＋Sc／Sa ……(34) となる。 そして、この(34)式はｘにα0〜αm+3まで代入し
てｆ（ｘ）＝０となることをチエツクすればエラー
ロケーシヨンが求まるのであるから、これを次の
ように変形して f′（ｘ）＝Saｆ（ｘ）＝Sax2＋Sbｘ＋Sc ……(35) としても、該f′（ｘ）にα0〜αm+3を代入してやる
ことによりf′（ｘ）＝０となる点でαiとαjとが求ま
ることになる筈である。 つまり、このようにしてエラーロケーシヨン多
項式を求める際には除算をなくすことが可能とな
る。 次に、エラーパターンの生成についてである
が、上記(30A)式でeiを求める際に必要となる除
算（S0αj＋S1／αi＋αj）について、分母であるαi＋
αjの 逆数（αi＋αj）-1が予め判明していれば ei＝（S0αj＋S1）（αi＋αj）-1……(30A′) なる乗算に帰着せしめることが可能となる。 そこで、次に上記逆数（αi＋αj）-1を求める方
法についてみてみるに、上記(35)式に(32)式を入
れると f′（ｘ）＝Sax2＋Sa（αi＋αj）ｘ＋Sc ……(36) となる。そして、かかる(36)式のｘにα0〜αm+3ま
で代入する操作が上記エラーロケーシヨンを求め
るのに必要であることになるが、このα0〜αm+3ま
でを代入する間に該(36)式のSa（αi＋αj）ｘなる項
に着眼して Sa（αi＋αj）ｘ＝αr ……(37) となるｘを求める操作をしてやる。 具体的には、今、ｍ＝28とすると、(37)式のｘ
にはα0〜α31まで代入されることになるが、ガロ
ア体GF（28）では α28-1＝α255＝１ が最大で、この場合α0〜α254の巡回符号となるか
らα0〜α254までしか扱うことはない。 そして、今α0〜α31まで代入してみるのである
から、７＜255／32＜８からα32m→α-32m（但しｍ
＝０，１……７）までの逆数データ８個を下表の
ようにコード化しておくものとする。
従つて、以上詳述したようにこの発明によれ
ば、大容量のメモリを必要とする対数バツフアや
真数バツフアを用いることなくガロア体における
乗算をなし得るようにし、以つて構成の簡易化な
らびに低価格化に寄与し得るようにした極めて良
好なるガロア体における乗算装置を提供すること
が可能となる。
ば、大容量のメモリを必要とする対数バツフアや
真数バツフアを用いることなくガロア体における
乗算をなし得るようにし、以つて構成の簡易化な
らびに低価格化に寄与し得るようにした極めて良
好なるガロア体における乗算装置を提供すること
が可能となる。
第１図はリードソロモン符号の復号システムで
なるエラー訂正回路を示す概略構成図、第２図は
従来のエラーロケーシヨン多項式計算器を示す構
成図、第３図はこの発明が適用されるDAD再生
装置の概要を示す構成図、第４図は第３図のエラ
ー訂正回路部の具体例を示す構成図、第５図は第
４図の動作の具体例を説明するためのタイミング
チヤート、第６図はこの発明の一実施例として第
４図の演算ユニツト部に備えられた乗算装置を示
す構成図、第７図は第６図の動作の具体例を説明
するためのタイミングチヤート、第８図，第９図
は第６図のα乗算回路、α2乗算回路の具体例を示
す構成図である。 ５１，５２，６６，６８…ラツチ回路、５３…
α乗算回路、５４，５５，５６，５９，６２，６
５…セレクト回路、５７，６０，６４…α2乗算回
路、５８，６１，６３，６７…エクスクルシブオ
ア回路。
なるエラー訂正回路を示す概略構成図、第２図は
従来のエラーロケーシヨン多項式計算器を示す構
成図、第３図はこの発明が適用されるDAD再生
装置の概要を示す構成図、第４図は第３図のエラ
ー訂正回路部の具体例を示す構成図、第５図は第
４図の動作の具体例を説明するためのタイミング
チヤート、第６図はこの発明の一実施例として第
４図の演算ユニツト部に備えられた乗算装置を示
す構成図、第７図は第６図の動作の具体例を説明
するためのタイミングチヤート、第８図，第９図
は第６図のα乗算回路、α2乗算回路の具体例を示
す構成図である。 ５１，５２，６６，６８…ラツチ回路、５３…
α乗算回路、５４，５５，５６，５９，６２，６
５…セレクト回路、５７，６０，６４…α2乗算回
路、５８，６１，６３，６７…エクスクルシブオ
ア回路。
Claims (1)
- 【特許請求の範囲】 １ ガロア体GF（2m）の生成多項式Ｇ（ｘ）の１
根をαとする被乗数データＢ（α）（但し、Ｂ（α）
＝bn-1αm-1＋bn-2αm-2＋……＋b0）および乗数デ
ータＣ（α）（但し、Ｃ（α）＝cn-1αm-1＋cn-2αm-2
＋……＋c0）の乗算をＢ（α）・Ｃ（α）＝αB（α）
＋Ｂ（α）（但し、 ＝cn-1αm-2＋cn-2αm-4＋cn-3αm-6＋……＋c1， ＝cn-2αm-2＋cn-4αm-4＋cn-6αm-6＋……＋c0） なる第１の部分乗算〔αB（α）〕および第２の
部分乗算〔Ｂ（α）〕の和の形に変換して処理
するもので、前記第１の部分乗算を第１のステツ
プで処理する第１の手段と、前記第２の部分乗算
を第２のステツプで処理する第２の手段と、前記
第１および第２の手段の各部分乗算出力を加算す
る第３の手段とを具備してなることを特徴とする
ガロア体における乗算装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57102802A JPS58219848A (ja) | 1982-06-15 | 1982-06-15 | ガロア体における乗算装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57102802A JPS58219848A (ja) | 1982-06-15 | 1982-06-15 | ガロア体における乗算装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS58219848A JPS58219848A (ja) | 1983-12-21 |
| JPS638648B2 true JPS638648B2 (ja) | 1988-02-24 |
Family
ID=14337196
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57102802A Granted JPS58219848A (ja) | 1982-06-15 | 1982-06-15 | ガロア体における乗算装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS58219848A (ja) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6130819A (ja) * | 1984-07-24 | 1986-02-13 | Nippon Columbia Co Ltd | 誤り訂正装置 |
| JPS6269728A (ja) * | 1985-09-20 | 1987-03-31 | Matsushita Graphic Commun Syst Inc | 誤り訂正回路 |
| JPS6386925A (ja) * | 1986-09-30 | 1988-04-18 | Canon Inc | ガロア体乗算回路 |
| JPH01157129A (ja) * | 1988-11-18 | 1989-06-20 | Matsushita Graphic Commun Syst Inc | 演算装置 |
| JP4472808B2 (ja) * | 1999-08-19 | 2010-06-02 | ネッツエスアイ東洋株式会社 | 積和演算装置及びこれを用いた暗号・復号装置 |
| JP4484002B2 (ja) * | 1999-10-04 | 2010-06-16 | ネッツエスアイ東洋株式会社 | 演算プロセッサ |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4142174A (en) * | 1977-08-15 | 1979-02-27 | International Business Machines Corporation | High speed decoding of Reed-Solomon codes |
| JPS5778608A (en) * | 1980-10-31 | 1982-05-17 | Matsushita Electric Ind Co Ltd | Decoding method of reed-solomon code |
-
1982
- 1982-06-15 JP JP57102802A patent/JPS58219848A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS58219848A (ja) | 1983-12-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPS638651B2 (ja) | ||
| US4574361A (en) | Apparatus for dividing the elements of a Galois field | |
| US4567568A (en) | Apparatus for dividing the elements of a Galois field | |
| JPH10500270A (ja) | 多目的誤り訂正システム | |
| US4608692A (en) | Error correction circuit | |
| US5974583A (en) | Error correcting method and device | |
| US6167548A (en) | Data error correcting method and apparatus | |
| JPH11328880A (ja) | 誤り訂正装置及び光ディスク読取装置 | |
| US5541940A (en) | Error correction method and error correction circuit | |
| JPS58219848A (ja) | ガロア体における乗算装置 | |
| JPS6237415B2 (ja) | ||
| JPS638650B2 (ja) | ||
| JPS638649B2 (ja) | ||
| JP2001044853A (ja) | チェンサーチ回路、誤り訂正装置及びディスクドライブ装置 | |
| JPS6248254B2 (ja) | ||
| JPS6246018B2 (ja) | ||
| KR920010184B1 (ko) | 유한체(有限體)의 연산회로 | |
| JPH04365139A (ja) | 誤り訂正処理用シンドローム演算回路 | |
| JPS6237414B2 (ja) | ||
| KR100215807B1 (ko) | 디지탈 신호의 에러 정정 장치 및 방법 | |
| JPS6055565A (ja) | エラ−訂正回路 | |
| JP2553571B2 (ja) | ガロア体演算装置 | |
| JPH10150367A (ja) | 誤り訂正装置 | |
| KR910009094B1 (ko) | 갈로이계 연산장치 | |
| JPS6055733A (ja) | エラ−訂正回路 |