JPH047847B2 - - Google Patents
Info
- Publication number
- JPH047847B2 JPH047847B2 JP60262168A JP26216885A JPH047847B2 JP H047847 B2 JPH047847 B2 JP H047847B2 JP 60262168 A JP60262168 A JP 60262168A JP 26216885 A JP26216885 A JP 26216885A JP H047847 B2 JPH047847 B2 JP H047847B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- circuit
- signal line
- error
- syndrome
- 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 - Lifetime
Links
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Description
【発明の詳細な説明】
〔産業上の利用分野〕
この発明は誤り制御符号の復号化装置に関する
ものである。
ものである。
第６図は、例えば文献（木村、今井、土肥；
“シストリツクアルゴリズムに基づくReed−
Solomon符号の復号器の構成法”、信学技報
Vol84，No.321、AL84−76、PP.55−62、1985.3）
によるシストリツクアルゴリズムに基づくｔ重誤
り訂正復号器の構成を示したものである。
“シストリツクアルゴリズムに基づくReed−
Solomon符号の復号器の構成法”、信学技報
Vol84，No.321、AL84−76、PP.55−62、1985.3）
によるシストリツクアルゴリズムに基づくｔ重誤
り訂正復号器の構成を示したものである。
図において、１はシンドロームセル回路で、２
は受信データ入力端子rin、３はコマンド入力端
子COMin、４はデータ入力端子yin、５はシンド
ローム出力信号線yout、６はコマンド出力信号
線COMoutである。７はGCD（Greatest
Common Divisor）セル回路で、８は次数デー
タの入力信号線degin、９はコマンド入力信号線
startin、１０は変数データ入力信号線Verin、１
１は次数データ出力信号線degout、１２はコマ
ンド出力信号線Startout、１３は誤り位置多項式
σ（ｘ）及び誤り数値多項式ｎ（ｘ）を出力する信
号線veroutである。１４はガロア体の元αi（ｉ＝
１，２，……，ｎ；ｎは符号長）を記憶した
ROM、１５はアドレスデータ入力信号線ADinで
ある。１６はEvaluation（評価）セル回路で、１
７はROMデータの入力信号線Xin、１８はコマ
ンド入力信号線COMin、１９は誤り位置多項式
σ（ｘ）、誤り数値多項式ｎ（ｘ）、及び誤り位置多
項式の微分σ′（ｘ）の入力信号線fin、２０はｎ
（αi）、σ′（αi）の出力信号線、２１はσ（αi）
の出
力信号線である。２２は誤りであると推定される
位置ｉにおいての誤り数値を求める回路及び出力
するためのゲート回路、２３は誤り数値の出力信
号線、２４はバツフアメモリ、２５はバツフア出
力信号線、２６はガロア体の加算器、２７は復号
データ出力端子Doutである。また、２８はシン
ドローム−GCDインターフエイス回路、２９は
GCD−Evaluationインターフエイス回路である。
は受信データ入力端子rin、３はコマンド入力端
子COMin、４はデータ入力端子yin、５はシンド
ローム出力信号線yout、６はコマンド出力信号
線COMoutである。７はGCD（Greatest
Common Divisor）セル回路で、８は次数デー
タの入力信号線degin、９はコマンド入力信号線
startin、１０は変数データ入力信号線Verin、１
１は次数データ出力信号線degout、１２はコマ
ンド出力信号線Startout、１３は誤り位置多項式
σ（ｘ）及び誤り数値多項式ｎ（ｘ）を出力する信
号線veroutである。１４はガロア体の元αi（ｉ＝
１，２，……，ｎ；ｎは符号長）を記憶した
ROM、１５はアドレスデータ入力信号線ADinで
ある。１６はEvaluation（評価）セル回路で、１
７はROMデータの入力信号線Xin、１８はコマ
ンド入力信号線COMin、１９は誤り位置多項式
σ（ｘ）、誤り数値多項式ｎ（ｘ）、及び誤り位置多
項式の微分σ′（ｘ）の入力信号線fin、２０はｎ
（αi）、σ′（αi）の出力信号線、２１はσ（αi）
の出
力信号線である。２２は誤りであると推定される
位置ｉにおいての誤り数値を求める回路及び出力
するためのゲート回路、２３は誤り数値の出力信
号線、２４はバツフアメモリ、２５はバツフア出
力信号線、２６はガロア体の加算器、２７は復号
データ出力端子Doutである。また、２８はシン
ドローム−GCDインターフエイス回路、２９は
GCD−Evaluationインターフエイス回路である。
第７図の３０はシンドロームセル回路１を構成
するサブセルのモデルで、３１は前段の受信デー
タの入力信号線、３２はコマンド入力信号線、３
３は前段のシンドローム入力信号線、３４はシン
ドロームSiに対して、生成多項式の項αiをストア
するレジスタ、３５はシンドロームSiの中間計算
結果をストアするレジスタ、３６はシンドローム
Siをストアするレジスタ、３７は次段への受信デ
ータの出力信号線、３８はコマンド出力信号線、
３９は次段へのシンドローム出力信号線である。
するサブセルのモデルで、３１は前段の受信デー
タの入力信号線、３２はコマンド入力信号線、３
３は前段のシンドローム入力信号線、３４はシン
ドロームSiに対して、生成多項式の項αiをストア
するレジスタ、３５はシンドロームSiの中間計算
結果をストアするレジスタ、３６はシンドローム
Siをストアするレジスタ、３７は次段への受信デ
ータの出力信号線、３８はコマンド出力信号線、
３９は次段へのシンドローム出力信号線である。
第８図の４０はGCDセル回路７を構成するサ
ブセルのモデルで、４１〜４４はそれぞれ各多項
式の係数データの入力信号線（ain，bin，lin，
min）、４５はコマンド入力信号線startin、４６
〜４９は各多項式の次数の入力信号線（degAin，
degBin，degLni，degMin）、５０はサブセルの
処理モードを貯えるレジスタstate、５１，５２
は処理上使用する定数を貯えるレジスタ、５３〜
６３は各々入力データの遅延用レジスタ（ａ，
ｂ，ｌ，ｍ，start，degA，degB，degL，
degM）６４〜６７は各多項式のの係数の出力信
号線（aout，bout，lout，mout）、６８はコマン
ド出力信号線startout，６９〜７２はサブセルで
処理後の次数の出力信号線（degAout，
degBout，degLout，degMout）である。
ブセルのモデルで、４１〜４４はそれぞれ各多項
式の係数データの入力信号線（ain，bin，lin，
min）、４５はコマンド入力信号線startin、４６
〜４９は各多項式の次数の入力信号線（degAin，
degBin，degLni，degMin）、５０はサブセルの
処理モードを貯えるレジスタstate、５１，５２
は処理上使用する定数を貯えるレジスタ、５３〜
６３は各々入力データの遅延用レジスタ（ａ，
ｂ，ｌ，ｍ，start，degA，degB，degL，
degM）６４〜６７は各多項式のの係数の出力信
号線（aout，bout，lout，mout）、６８はコマン
ド出力信号線startout，６９〜７２はサブセルで
処理後の次数の出力信号線（degAout，
degBout，degLout，degMout）である。
第９図の７３はEvaluationセル回路を構成す
るサブセルのモデルで、７４は位置ｉに対応した
ガロア体の元αiを入力する信号線Xin、７５はコ
マンド入力信号線COMin、７６はデータ入力端
子fin、７７は誤り位置多項式σ（ｘ）、その微分
σ′（ｘ）、誤り数値多項式ｎ（ｘ）のｉ次の係数を
貯えるレジスタfi、７８はαi出力信号線Xout、７
９はコマンド出力信号線COMout、８０は処理デ
ータの出力信号線foutである。
るサブセルのモデルで、７４は位置ｉに対応した
ガロア体の元αiを入力する信号線Xin、７５はコ
マンド入力信号線COMin、７６はデータ入力端
子fin、７７は誤り位置多項式σ（ｘ）、その微分
σ′（ｘ）、誤り数値多項式ｎ（ｘ）のｉ次の係数を
貯えるレジスタfi、７８はαi出力信号線Xout、７
９はコマンド出力信号線COMout、８０は処理デ
ータの出力信号線foutである。
第１０図は、GCDセル回路７とその前後のイ
ンターフエイス２８，２９の演算アルゴリズムを
示している。ここでステツプ81はシンドローム−
GCDインターフエイス回路の操作、ステツプ82
〜85はGCDセル回路の操作、ステツプ86〜88は
GCD−Evaluationインターフエイス回路の操作
を示す。
ンターフエイス２８，２９の演算アルゴリズムを
示している。ここでステツプ81はシンドローム−
GCDインターフエイス回路の操作、ステツプ82
〜85はGCDセル回路の操作、ステツプ86〜88は
GCD−Evaluationインターフエイス回路の操作
を示す。
次に動作について説明する。第６図において受
信データの先頭と共にコマンド入力端子３に‘
start'コマンドを入力する。受信データは受信デ
ータ入力端子２によりシンドロームセル回路１に
入力すると共に、バツフアメモリ２４にも蓄え
る。またデータ入力端子４には常に零が入力され
る。
信データの先頭と共にコマンド入力端子３に‘
start'コマンドを入力する。受信データは受信デ
ータ入力端子２によりシンドロームセル回路１に
入力すると共に、バツフアメモリ２４にも蓄え
る。またデータ入力端子４には常に零が入力され
る。
このとき第７図においてナンバー＃０〜＃2t−
１（ｔ＝ｄ−１／２）のサブセル３０で構成されるシ ンドロームセル回路１は、それぞれS0〜S2t-1の
シンドロームを計算する。先頭データと共に上記
‘start'コマンドを受けとつたサブセル３０はそ
のデータをレジスタＳ３５にストアする。次の受
信データからは‘calc'コマンドをコマンド入力
端子３より入力する。このときサブセル３０は受
信データ入力端子rin２から入力された入力デー
タに対してＳ＝Ｓ・Ｘ＋rinの積和演算を施す。
ここでＸはレジスタＸ３４のデータで生成多項式
の根がストアされている。この間シンドローム入
力信号線yin３３、シンドローム出力信号線yout
３９、及びレジスタｙ３６は零である。符号長ｎ
としてｎ番目のデータが入力されるとき、コマン
ド入力信号線３２には‘end'が入力される。この
ときＳについての積和演算結果は、レジスタｙ３
６にストアされ順次シンドローム−GCDインタ
ーフエイス回路２８へシンドローム出力信号線
yout５から出力される。
１（ｔ＝ｄ−１／２）のサブセル３０で構成されるシ ンドロームセル回路１は、それぞれS0〜S2t-1の
シンドロームを計算する。先頭データと共に上記
‘start'コマンドを受けとつたサブセル３０はそ
のデータをレジスタＳ３５にストアする。次の受
信データからは‘calc'コマンドをコマンド入力
端子３より入力する。このときサブセル３０は受
信データ入力端子rin２から入力された入力デー
タに対してＳ＝Ｓ・Ｘ＋rinの積和演算を施す。
ここでＸはレジスタＸ３４のデータで生成多項式
の根がストアされている。この間シンドローム入
力信号線yin３３、シンドローム出力信号線yout
３９、及びレジスタｙ３６は零である。符号長ｎ
としてｎ番目のデータが入力されるとき、コマン
ド入力信号線３２には‘end'が入力される。この
ときＳについての積和演算結果は、レジスタｙ３
６にストアされ順次シンドローム−GCDインタ
ーフエイス回路２８へシンドローム出力信号線
yout５から出力される。
シンドローム−GCDインターフエイス回路２
８は、第１０図のアルゴリズムの８１の操作を行
う。ここでシンドローム多項式Ｓ（ｘ）は、シン
ドロームに対してＳ（ｘ）＝S2t-1X2t-1＋……＋
S1X＋S0としたものである。またＡ，Ｂ，Ｌ，Ｍ
の多項式の最大次数も調べる。シンドローム−
GCDインターフエイス回路２８はコマンド出力
信号線６で‘end'の信号を受けた後、コマンド入
力信号線９に‘start＝1'を入力すると共に、変
数データ入力信号線１０にＡ，Ｂ，Ｌ，Ｍの多項
式の最大次数のデータ、及び次数データ入力信号
線８に各多項式の最大次数データを出力する。
８は、第１０図のアルゴリズムの８１の操作を行
う。ここでシンドローム多項式Ｓ（ｘ）は、シン
ドロームに対してＳ（ｘ）＝S2t-1X2t-1＋……＋
S1X＋S0としたものである。またＡ，Ｂ，Ｌ，Ｍ
の多項式の最大次数も調べる。シンドローム−
GCDインターフエイス回路２８はコマンド出力
信号線６で‘end'の信号を受けた後、コマンド入
力信号線９に‘start＝1'を入力すると共に、変
数データ入力信号線１０にＡ，Ｂ，Ｌ，Ｍの多項
式の最大次数のデータ、及び次数データ入力信号
線８に各多項式の最大次数データを出力する。
ここで第８図のサブセル４０で構成される
GCDセル回路７は第１０図のアルゴリズムの各
ステツプ82〜85の操作を行う。上記コマンド‘
start＝1'においては入力信号線bin４２より入力
された多項式Ｂの最大次係数をαレジスタ５１、
入力信号線ain４１より入力された多項式Ａの最
大次係数をβレジスタ５２にストアする。また入
力される入力信号線degAin４６、入力信号線
degBin４７のデータを比較して、いずれかがｔ
（ｔ（ｄ−１）／２，ｄ：最小距離）より小さ
ければ演算を行わない、‘nop'、degAdegB＞
ｔならば第１０図のステツプ83の演算を行う。ま
た、‘reduceA'、degB＞degA＞ｔならば第１
０図のステツプ84の演算を行う。また‘
reduceB'をstateレジスタ５０にストアする。こ
れらのデータは次のコマンド‘start＝1'がくる
まで保持し、stateレジスタ５０に沿つた演算を
行う。入力データ１〜2t−１においてコマンド入
力信号線９，４５は‘start＝0'を入力し、次数
データの入力信号線８、入力信号線４６〜４９は
零を入力する。一つのサブセル４０では、Ａある
いはＢいずれかの次数が一つ小さくなり、Ｌある
いはＭいずれかの次数が一つ大きくなるので、次
段に対して最大次数データをＡ，Ｂ，Ｌ，Ｍ同時
に出力できるように遅延レジスタ５３〜６３を用
いて出力信号線６４〜７２に出力する。
GCDセル回路７は第１０図のアルゴリズムの各
ステツプ82〜85の操作を行う。上記コマンド‘
start＝1'においては入力信号線bin４２より入力
された多項式Ｂの最大次係数をαレジスタ５１、
入力信号線ain４１より入力された多項式Ａの最
大次係数をβレジスタ５２にストアする。また入
力される入力信号線degAin４６、入力信号線
degBin４７のデータを比較して、いずれかがｔ
（ｔ（ｄ−１）／２，ｄ：最小距離）より小さ
ければ演算を行わない、‘nop'、degAdegB＞
ｔならば第１０図のステツプ83の演算を行う。ま
た、‘reduceA'、degB＞degA＞ｔならば第１
０図のステツプ84の演算を行う。また‘
reduceB'をstateレジスタ５０にストアする。こ
れらのデータは次のコマンド‘start＝1'がくる
まで保持し、stateレジスタ５０に沿つた演算を
行う。入力データ１〜2t−１においてコマンド入
力信号線９，４５は‘start＝0'を入力し、次数
データの入力信号線８、入力信号線４６〜４９は
零を入力する。一つのサブセル４０では、Ａある
いはＢいずれかの次数が一つ小さくなり、Ｌある
いはＭいずれかの次数が一つ大きくなるので、次
段に対して最大次数データをＡ，Ｂ，Ｌ，Ｍ同時
に出力できるように遅延レジスタ５３〜６３を用
いて出力信号線６４〜７２に出力する。
GCDセル回路７のコマンド出力信号線１２よ
り‘start＝1'が出力されると、GCD−Evalution
インターフエイス回路２９は、GCDセル回路７
の次数データ出力信号線１１で、入力される
degA，degB，degL，degM及び変数データ出力
信号線１３より入力されるＡ，Ｂ，Ｌ，Ｍより第
１０図のステツプ86，87，88を行う。さらに誤り
位置多項式σ（ｘ）に対して微分し、誤り位置多
項式の微分σ′（ｘ）を求める。出力はコマンド‘
start＝1'を受けとるとEvalutionセル回路１６の
コマンド入力信号線１８に対してコマンド‘load
＃i'（ｉ＝ｔ，……，１，０）を出力し、その後
‘calc'をｎ回出力する。この‘calc'を送るとき
には、ROM１４に対して位置ｉ（ｉ＝ｎ，……，
２，１）に対する元αiを入力信号線１７に出力す
るようアドレスデータをアドレスデータ入力信号
線１５に送る。
り‘start＝1'が出力されると、GCD−Evalution
インターフエイス回路２９は、GCDセル回路７
の次数データ出力信号線１１で、入力される
degA，degB，degL，degM及び変数データ出力
信号線１３より入力されるＡ，Ｂ，Ｌ，Ｍより第
１０図のステツプ86，87，88を行う。さらに誤り
位置多項式σ（ｘ）に対して微分し、誤り位置多
項式の微分σ′（ｘ）を求める。出力はコマンド‘
start＝1'を受けとるとEvalutionセル回路１６の
コマンド入力信号線１８に対してコマンド‘load
＃i'（ｉ＝ｔ，……，１，０）を出力し、その後
‘calc'をｎ回出力する。この‘calc'を送るとき
には、ROM１４に対して位置ｉ（ｉ＝ｎ，……，
２，１）に対する元αiを入力信号線１７に出力す
るようアドレスデータをアドレスデータ入力信号
線１５に送る。
Evalutionセル回路１６は、ナンバー＃０〜
＃ｔのサブセル７３によつて構成される。ナンバ
ー＃ｉのレジスタfi７７は、‘load＃i'のコマン
ド時の誤り位置多項式σ（ｘ）、誤り位置多項式の
微分σ′（ｘ）、誤り数値多項式ｎ（ｘ）の係数デー
タをストアする。コマンド入力信号線１８に‘
celc'が入力されると同時にROM１４のデータが
入力信号線Xin１７に入力される。そのとき入力
信号線fin１９には１が入力される。‘calc'が入
力されたサブセル７３は、fout80＝fin76・Xin74
＋fi77の演算を行い、COMout79＝COMin75、
Xout78＝Xin74として出力信号線７８〜８０に
出力する。これをナンバー＃ｔのサブセルまで行
つたときそのfoutの出力線２１には誤り位置多項
式σ（αi）が、＃ｔ−１のfoutの出力線２０では
誤り数値多項式ｎ（αi）、誤り位置多項式の微分
σ′（αi）が得られる。ここでαiはROM１４より出
力される位置ｉに対応してガロア体の元である。
（ｉ＝１，２，……，ｎ） 位置ｉにおける誤り数値を求めるゲート回路２
２は、得られた誤り位置多項式σ（αi）が零のと
き位置ｉに誤りが生じているものと判断し、誤り
数値をｎ（αi）／σ′（αi）の演算により求め、ゲー
ト回路２２を開いて誤り数値を出力信号線２３に
出力し、バツフアメモリ２４より信号線２５に出
力される位置ｉのデータとガロア体の加算器２６
によつて訂正し、復号データ出力端子２７より出
力する。
＃ｔのサブセル７３によつて構成される。ナンバ
ー＃ｉのレジスタfi７７は、‘load＃i'のコマン
ド時の誤り位置多項式σ（ｘ）、誤り位置多項式の
微分σ′（ｘ）、誤り数値多項式ｎ（ｘ）の係数デー
タをストアする。コマンド入力信号線１８に‘
celc'が入力されると同時にROM１４のデータが
入力信号線Xin１７に入力される。そのとき入力
信号線fin１９には１が入力される。‘calc'が入
力されたサブセル７３は、fout80＝fin76・Xin74
＋fi77の演算を行い、COMout79＝COMin75、
Xout78＝Xin74として出力信号線７８〜８０に
出力する。これをナンバー＃ｔのサブセルまで行
つたときそのfoutの出力線２１には誤り位置多項
式σ（αi）が、＃ｔ−１のfoutの出力線２０では
誤り数値多項式ｎ（αi）、誤り位置多項式の微分
σ′（αi）が得られる。ここでαiはROM１４より出
力される位置ｉに対応してガロア体の元である。
（ｉ＝１，２，……，ｎ） 位置ｉにおける誤り数値を求めるゲート回路２
２は、得られた誤り位置多項式σ（αi）が零のと
き位置ｉに誤りが生じているものと判断し、誤り
数値をｎ（αi）／σ′（αi）の演算により求め、ゲー
ト回路２２を開いて誤り数値を出力信号線２３に
出力し、バツフアメモリ２４より信号線２５に出
力される位置ｉのデータとガロア体の加算器２６
によつて訂正し、復号データ出力端子２７より出
力する。
従来のシストリツクアルゴリズムに基づいた復
号化装置は以上のように構成されているので、誤
りの訂正のみかし行えず消失に対する訂正機能を
持つていないという問題点があつた。
号化装置は以上のように構成されているので、誤
りの訂正のみかし行えず消失に対する訂正機能を
持つていないという問題点があつた。
この発明は上記のような問題点を解消するため
になされたもので、誤り訂正ができるとともに消
失訂正できるシストリツクアルゴリズムに基づく
復号化装置を得ることを目的とする。
になされたもので、誤り訂正ができるとともに消
失訂正できるシストリツクアルゴリズムに基づく
復号化装置を得ることを目的とする。
受信データを入力してシンドロームを求めるシ
ンドロームセル回路と、上記受信データと消失位
置に対するフラグ信号を出力するフラグ信号出力
回路と、上記フラグ信号に対応する消失位置シン
ボルデータを生成する消失位置発生回路と、上記
シンドロームセル回路から出力されるシンドロー
ムのデータ系列から消失位置の情報を除く修正シ
ンドロームを出力する修正シンドロームセル回路
と、上記修正シンドロームのデータ系列から誤り
位置多項式σe（ｘ）及び誤り消失数値多項式ｎ
（ｘ）の係数のデータ系列を求めるGCDセル回路
と、上記誤り位置多項式σe（ｘ）のデータ系列と
上記消失位置シンボルデータの消失位置データ系
列とから誤り消失位置多項式σ（ｘ）の係数デー
タを出力する乗算セル回路と、誤り消失位置多項
式σ（ｘ）及び誤り消失数値多項式ｎ（ｘ）の係数
データとから誤り消失位置及び数値を求める評価
セル回路と、評価セル回路によつて求められた誤
り消失位置及び数値に基づいて上記受信データを
訂正するためのゲート回路とを具備したことを特
徴とするものである。
ンドロームセル回路と、上記受信データと消失位
置に対するフラグ信号を出力するフラグ信号出力
回路と、上記フラグ信号に対応する消失位置シン
ボルデータを生成する消失位置発生回路と、上記
シンドロームセル回路から出力されるシンドロー
ムのデータ系列から消失位置の情報を除く修正シ
ンドロームを出力する修正シンドロームセル回路
と、上記修正シンドロームのデータ系列から誤り
位置多項式σe（ｘ）及び誤り消失数値多項式ｎ
（ｘ）の係数のデータ系列を求めるGCDセル回路
と、上記誤り位置多項式σe（ｘ）のデータ系列と
上記消失位置シンボルデータの消失位置データ系
列とから誤り消失位置多項式σ（ｘ）の係数デー
タを出力する乗算セル回路と、誤り消失位置多項
式σ（ｘ）及び誤り消失数値多項式ｎ（ｘ）の係数
データとから誤り消失位置及び数値を求める評価
セル回路と、評価セル回路によつて求められた誤
り消失位置及び数値に基づいて上記受信データを
訂正するためのゲート回路とを具備したことを特
徴とするものである。
この発明にかかるシンドロームセル回路は受信
データを入力してシンドロームを出力する。
データを入力してシンドロームを出力する。
またフラグ信号出力回路は上記受信データとこ
の受信データの消失位置に対するフラグ信号を出
力する。
の受信データの消失位置に対するフラグ信号を出
力する。
ここにおいて消失位置発生回路は、フラグ信号
に対応する消失位置シンボルデータを生成し、修
正シンドロームセル回路は上記シンドロームセル
回路から出力されるシンドロームのデータ系列か
ら消失位置の情報を除く修正シンドロームを出力
する。GCDセル回路は上記修正シンドロームの
データ系列から誤り位置多項式σe（ｘ）及び誤り
消失数値多項式ｎ（ｘ）の係数のデータ系列を求
め、乗算セル回路に出力する。乗算セル回路は上
記誤り位置多項式σe（ｘ）のデータ系列と上記消
失位置シンボルデータの消失位置データ系列とか
ら誤り消失位置多項式σ（ｘ）の係数データを
Evaluationセル回路に出力する。
に対応する消失位置シンボルデータを生成し、修
正シンドロームセル回路は上記シンドロームセル
回路から出力されるシンドロームのデータ系列か
ら消失位置の情報を除く修正シンドロームを出力
する。GCDセル回路は上記修正シンドロームの
データ系列から誤り位置多項式σe（ｘ）及び誤り
消失数値多項式ｎ（ｘ）の係数のデータ系列を求
め、乗算セル回路に出力する。乗算セル回路は上
記誤り位置多項式σe（ｘ）のデータ系列と上記消
失位置シンボルデータの消失位置データ系列とか
ら誤り消失位置多項式σ（ｘ）の係数データを
Evaluationセル回路に出力する。
Evaluationセル回路は誤り消失位置多項式σ
（ｘ）及び誤り消失数値多項式ｎ（ｘ）の係数デー
タとから誤り消失位置及び数値を求め、ゲート回
路に出力する。ゲート回路はEvaluationセル回
路によつて求められた誤り消失位置及び数値に基
づいて上記受信データを訂正する。
（ｘ）及び誤り消失数値多項式ｎ（ｘ）の係数デー
タとから誤り消失位置及び数値を求め、ゲート回
路に出力する。ゲート回路はEvaluationセル回
路によつて求められた誤り消失位置及び数値に基
づいて上記受信データを訂正する。
以下図面に基づいて本発明の一実施例を説明す
る。
る。
先ず本発明の解法アルゴリズムについて説明す
る。
る。
先述の従来装置の誤り訂正の解法アルゴリズム
は、一般にユークリツド復号法と呼ばれるもので
ある。（文献：Ｙ：Sugiyama，M.Kasahara，S.
Hirasawa and T.Namekawa，“Ａ Method
for Solving Key Equation for Decoding
Goppa Codes”，Inform.Conter.，Vol27，pp.87
−99，Jan.1975）このアルゴリズムは、誤り−消
失訂正においても、誤り個数ne、消失個数nε、
符号の最小距離ｄ＝2t＋１とすると、2ne＋nε＜
ｄであれば、修正シンドロームSε（ｘ）、Sε（ｘ）
＝σε（ｘ）・Ｓ（ｘ）modg（ｘ）、ｇ（ｘ）＝X2tを
計
算すればGCDの解法アルゴリズムにより、訂正
可能であることが文献に示されている（文献：
Y.Sugiyama，M.Kasahara，S.Hirasawa and
N.Namekawa，“An Erasures−Errors
Decoding Algorithm for Goppa Codes”，
IEEE Trans，Inform.Theory（Corresp.）to
appear，Mar，1976）。ここでσε（ｘ）は消失位
置多項式、Ｓ（ｘ）はシンドローム多項式である。
は、一般にユークリツド復号法と呼ばれるもので
ある。（文献：Ｙ：Sugiyama，M.Kasahara，S.
Hirasawa and T.Namekawa，“Ａ Method
for Solving Key Equation for Decoding
Goppa Codes”，Inform.Conter.，Vol27，pp.87
−99，Jan.1975）このアルゴリズムは、誤り−消
失訂正においても、誤り個数ne、消失個数nε、
符号の最小距離ｄ＝2t＋１とすると、2ne＋nε＜
ｄであれば、修正シンドロームSε（ｘ）、Sε（ｘ）
＝σε（ｘ）・Ｓ（ｘ）modg（ｘ）、ｇ（ｘ）＝X2tを
計
算すればGCDの解法アルゴリズムにより、訂正
可能であることが文献に示されている（文献：
Y.Sugiyama，M.Kasahara，S.Hirasawa and
N.Namekawa，“An Erasures−Errors
Decoding Algorithm for Goppa Codes”，
IEEE Trans，Inform.Theory（Corresp.）to
appear，Mar，1976）。ここでσε（ｘ）は消失位
置多項式、Ｓ（ｘ）はシンドローム多項式である。
これをもとに以下、この発明の一実施例を図を
用いて説明する。
用いて説明する。
第１図は本発明によるシストリツクアルゴリズ
ムに基づいてｔ重誤り消失訂正回路の構成図を示
したものである。
ムに基づいてｔ重誤り消失訂正回路の構成図を示
したものである。
１〜２７は構成上第６図と同じものである。８
９は消失位置ij（ｊ＝１，２，……，ｄ−１）に
対するガロア体の元αijを発生する消失位置発生
回路、９０は消失位置のフラグ信号を出力するフ
ラグ信号出力回路、９１は消失位置係数出力信号
線LDout、９２はシンドローム−修正シンドロー
ムインターフエイス回路、９３は消失位置係数ラ
ツチ回路、９４は修正シンドロームセル回路、９
５は消失位置係数入力信号線LDin、９６はコマ
ンド入力信号線COMin、９７は消失位置出力信
号線LSout、９８はシンドローム入力信号線Yin、
９９は修正シンドローム出力信号線Yout、１０
０はコマンド出力信号線COMout、１０１は消失
位置係数出力信号線LDout、１０２は修正シンド
ローム−GCDインターフエイス回路、１０３は
消失位置係数ラツチ、１０４は消失位置入力信号
線LDin、１０５は消失位置出力信号線LDout、
１０６はGCD−乗算インターフエイス回路、１
０７は乗算セル回路、１０８は誤り−消失数値多
項式ラツチ、１０９は誤り−消失数値多項式ｎ
（ｘ）の入力信号線EEin、１１０はコマンド入力
信号線COMin、１１１は誤り位置多項式σe（ｘ）
の係数入力信号線ELin、１１２は消失位置係数
入力信号線LDin、１１３は誤り−消失数値多項
式ｎ（ｘ）の出力信号線EEout、１１４は誤り−
消失位置多項式σ（ｘ）の出力信号線ELout、１
１５はコマンド出力信号線COMout、１１６は乗
算−Evaluationインターフエイスである。
９は消失位置ij（ｊ＝１，２，……，ｄ−１）に
対するガロア体の元αijを発生する消失位置発生
回路、９０は消失位置のフラグ信号を出力するフ
ラグ信号出力回路、９１は消失位置係数出力信号
線LDout、９２はシンドローム−修正シンドロー
ムインターフエイス回路、９３は消失位置係数ラ
ツチ回路、９４は修正シンドロームセル回路、９
５は消失位置係数入力信号線LDin、９６はコマ
ンド入力信号線COMin、９７は消失位置出力信
号線LSout、９８はシンドローム入力信号線Yin、
９９は修正シンドローム出力信号線Yout、１０
０はコマンド出力信号線COMout、１０１は消失
位置係数出力信号線LDout、１０２は修正シンド
ローム−GCDインターフエイス回路、１０３は
消失位置係数ラツチ、１０４は消失位置入力信号
線LDin、１０５は消失位置出力信号線LDout、
１０６はGCD−乗算インターフエイス回路、１
０７は乗算セル回路、１０８は誤り−消失数値多
項式ラツチ、１０９は誤り−消失数値多項式ｎ
（ｘ）の入力信号線EEin、１１０はコマンド入力
信号線COMin、１１１は誤り位置多項式σe（ｘ）
の係数入力信号線ELin、１１２は消失位置係数
入力信号線LDin、１１３は誤り−消失数値多項
式ｎ（ｘ）の出力信号線EEout、１１４は誤り−
消失位置多項式σ（ｘ）の出力信号線ELout、１
１５はコマンド出力信号線COMout、１１６は乗
算−Evaluationインターフエイスである。
第２図は消失位置発生回路８９の構成の一例
で、３，９０，９１は第１図と同一であり、１１
７は制御回路、１１８はラツチに関するラツチ制
御回路、１１９はガロア体の元αiを発生させるαi
発生回路、１２０は＃０〜＃2t−１のラツチ群、
１２１はαi発生回路に関する制御信号線、１２２
は制御回路５６から出力されるラツチ制御回路の
制御信号線、１２３はラツチ制御信号線、１２４
はαiデータ信号線である。
で、３，９０，９１は第１図と同一であり、１１
７は制御回路、１１８はラツチに関するラツチ制
御回路、１１９はガロア体の元αiを発生させるαi
発生回路、１２０は＃０〜＃2t−１のラツチ群、
１２１はαi発生回路に関する制御信号線、１２２
は制御回路５６から出力されるラツチ制御回路の
制御信号線、１２３はラツチ制御信号線、１２４
はαiデータ信号線である。
第３図は消失位置係数ラツチ９３の構成図の一
例で、１２５はラツチ、１２６は制御回路、１２
７はセレクタ回路、１２８はラツチのトリガ信号
線、１２９はセレクタ制御信号線で、９５，９
６，９７，１０１は第１図のそれと同一である。
例で、１２５はラツチ、１２６は制御回路、１２
７はセレクタ回路、１２８はラツチのトリガ信号
線、１２９はセレクタ制御信号線で、９５，９
６，９７，１０１は第１図のそれと同一である。
第４図の１３０は修正シンドローム回路、乗算
セル回路のサブセルの構成の一例で、１３１はコ
マンド入力信号線COMin、１３２は消失位置係
数入力信号線Xin、１３３はデータ転送入力信号
線Yin、１３４〜１３６は入力データ用のラツ
チ、１３７は制御回路、１３８はラツチＡ、１３
９はラツチＢ、１４０はガロア体の加算回路、１
４１はガロア体の乗算回路、１４２はセレクタ回
路、１４３はラツチのトリガ信号線、１４４はセ
レクタ制御信号線、１４５〜１４７は出力データ
用ラツチ、１４８はコマンド出力端子COMout、
１４９は消失位置係数出力信号線Xout、１５０
はデータ転送出力信号線Youtである。
セル回路のサブセルの構成の一例で、１３１はコ
マンド入力信号線COMin、１３２は消失位置係
数入力信号線Xin、１３３はデータ転送入力信号
線Yin、１３４〜１３６は入力データ用のラツ
チ、１３７は制御回路、１３８はラツチＡ、１３
９はラツチＢ、１４０はガロア体の加算回路、１
４１はガロア体の乗算回路、１４２はセレクタ回
路、１４３はラツチのトリガ信号線、１４４はセ
レクタ制御信号線、１４５〜１４７は出力データ
用ラツチ、１４８はコマンド出力端子COMout、
１４９は消失位置係数出力信号線Xout、１５０
はデータ転送出力信号線Youtである。
第５図の１５０は第１図のGCDセル回路７の
サブセルのモデルで１５１のtin入力信号線、１
５２のｔ遅延ラツチ、１５３のtout出力信号線を
除き第８図のGCDのサブセル４０のモデルと同
一である。
サブセルのモデルで１５１のtin入力信号線、１
５２のｔ遅延ラツチ、１５３のtout出力信号線を
除き第８図のGCDのサブセル４０のモデルと同
一である。
次に動作について説明する。ここでは、誤りシ
ンボル数をne、消失シンボル数をnεとしたとき、
2ne＋nε＜ｄ（ｄは符号の最小距離）を満たして
いるものとする。
ンボル数をne、消失シンボル数をnεとしたとき、
2ne＋nε＜ｄ（ｄは符号の最小距離）を満たして
いるものとする。
フラグ信号出力回路９０から出力される消失の
フラグ信号は、入力端子２より入力される受信デ
ータと同期している。シンドロームセル１の動作
は従来装置と同じである。一方本発明で付加した
消失位置発生回路８９は、コマンド入力端子３よ
り‘start'コマンドを受けると制御回路１１７に
より制御信号線１２１を通じてαi発生回路１１９
がON状態となり、受信データと同期して位置ｉ
に対応したガロア体の元αiをαiデータ信号線１２
４に出力する。位置ijが消失のときすなわちフラ
グ信号出力回路９０から出力されたフラグ信号が
たつているとき、ラツチ制御回路１１８を通じて
ラツチ制御信号線１２３にラツチ信号を出力し、
その位置を示すαijをレジスタ５９に貯える。コ
マンド入力端子３から、‘end'が入力された後、
制御回路５６は制御信号線１２２に信号を出力
し、ラツチ制御回路５７によりラツチ制御信号線
１２３にシフト信号を2t回出力し、消失位置係数
αijを消失位置係数出力信号線９１に出力する。
フラグ信号は、入力端子２より入力される受信デ
ータと同期している。シンドロームセル１の動作
は従来装置と同じである。一方本発明で付加した
消失位置発生回路８９は、コマンド入力端子３よ
り‘start'コマンドを受けると制御回路１１７に
より制御信号線１２１を通じてαi発生回路１１９
がON状態となり、受信データと同期して位置ｉ
に対応したガロア体の元αiをαiデータ信号線１２
４に出力する。位置ijが消失のときすなわちフラ
グ信号出力回路９０から出力されたフラグ信号が
たつているとき、ラツチ制御回路１１８を通じて
ラツチ制御信号線１２３にラツチ信号を出力し、
その位置を示すαijをレジスタ５９に貯える。コ
マンド入力端子３から、‘end'が入力された後、
制御回路５６は制御信号線１２２に信号を出力
し、ラツチ制御回路５７によりラツチ制御信号線
１２３にシフト信号を2t回出力し、消失位置係数
αijを消失位置係数出力信号線９１に出力する。
シンドローム−修正シンドロームインターフエ
イス回路９２ではシンドロームセル１から‘end'
コマンドを受けた後、コマンド入力信号線９６に
‘load＃i'（ｉ＝2t−１〜０）コマンドを出力す
ると共に、シンドローム出力信号線５から入力し
たシンドロームSi（ｉ＝2t−１〜０）を修正シン
ドロームセル回路９４の入力信号線９８に出力す
る。また同時に、消失位置係数の出力信号線９１
から入力したデータを消失位置係数ラツチ回路９
３の入力信号線９５に入力し、ラツチ群１２５に
貯える。
イス回路９２ではシンドロームセル１から‘end'
コマンドを受けた後、コマンド入力信号線９６に
‘load＃i'（ｉ＝2t−１〜０）コマンドを出力す
ると共に、シンドローム出力信号線５から入力し
たシンドロームSi（ｉ＝2t−１〜０）を修正シン
ドロームセル回路９４の入力信号線９８に出力す
る。また同時に、消失位置係数の出力信号線９１
から入力したデータを消失位置係数ラツチ回路９
３の入力信号線９５に入力し、ラツチ群１２５に
貯える。
本発明による修正シンドロームセル回路９４は
ナンバー＃０〜＃2t−１のサブセル１３０から構
成されており、ナンバー＃ｉのサブセルはコマン
ド入力信号線１３２に‘load＃i'が入力されると
制御回路１３７よりラツチ信号線１４３にラツチ
信号が出力され、Yinラツチ１３６にラツチされ
ているSiデータをラツチＡ１３８に貯える。この
ときセレクタ回路１４２は、零がYoutラツチ１
４７に入力されるようにする。またSo（ｊ≠ｉ）
の場合は、SoがYoutラツチ１４７に入力される
ように制御回路１３７がセレクタ制御信号線によ
り制御する。コマンド入力信号線９６は、コマン
ド‘load＃0'まで入力された後は、‘calc'コマ
ンドが入力される。このとき消失位置係数ラツチ
回路９３の制御回路１２６はセレクタ制御信号線
１２９を通じて消失位置係数データのうちの一つ
のセレクタ回路１２７で選択し出力信号線９７に
出力する。この出力されたデータは修正シンドロ
ームセル回路９４のサブセル１３０＃０のXinラ
ツチ１３５に入力される。同時にCOMinラツチ
１３４には信号‘calc'が入力され、Yinラツチ１
３６には零が入力される。Xinラツチ１３５が零
でなければ制御回路１３７はラツチ信号線１４３
にラツチ信号を出力し、ラツチＡ１３８にYinラ
ツチ１３６のデータをラツチＢ１３９に加算器１
４０の出力データをラツチする。またYoutラツ
チ１４７にも、この出力データをラツチするよう
セレクタ回路１４２で選択する。このときXinラ
ツチ１３５のデータはXoutラツチ１４９にラツ
チし、COMinラツチ１３４のコマンドを
COMoutラツチ１４５にラツチする。ラツチＢ１
３９にストアされたデータは、乗算器１４１で
Xinラツチ１３５のデータとガロア体の乗算をし
てその出力を加算器１４０に入力してラツチＡ１
３８のデータとガロア体の加算を行う。これをサ
ブセル＃１〜＃2t−１も同様に行う。ただし、
COMin１３１，Xin１３２、Yin１３３の各入力
信号線は、それぞれ前段のCOMout１４８、
Xout１４９、Yout１５０の各出力信号線と接続
されている。ある消失位置係数αijについてナン
バー＃2t−１のサブセルまで行うことによつて、
演算（Ｘ−αi）・Ｓ（ｘ）modX2t（ｔ＝ｄ−１／２） を行つたことになる。‘calc'コマンドを2t回入
力して、ラツチ群１２５のデータをすべて出力信
号線９７より出力した後、コマンド入力信号線９
５には‘end'コマンドが入力される。このとき消
失位置係数ラツチ回路９３の制御回路１２６は、
ラツチ制御信号線１２８にシフト信号を出力し、
ラツチ群６４のデータを出力信号線１０１に次々
と出力する。このとき入力信号線LDin９５には
零が入力される。一方修正シンドロームセル９４
のサブセル１３０＃０では‘end'コマンドがコマ
ンド入力線１３１からCOMinラツチ１３４に入
力されると制御回路１３７によりラツチ信号線１
４３にラツチ信号を出力しラツチＡ１３８にYin
ラツチ１３６のデータを入力すると共にYoutラ
ツチ１４７に加算器１４０の出力データをラツチ
する。このときXinラツチ１３５、Yinラツチ１
３６には零が入力される。ナンバー＃１〜＃2t−
１のサブセル１３３０もCOMin１３４、Xin１
３２、Yin１３３の各ラツチに前段のCOMout１
４５、Xout１４６、Youtの各ラツチのデータが
入力されるだけで同様の動作をする。この‘end'
コマンドを2t回出力することにより修正シンドロ
ームSε（ｘ）は出力信号線９９より出力される。
ナンバー＃０〜＃2t−１のサブセル１３０から構
成されており、ナンバー＃ｉのサブセルはコマン
ド入力信号線１３２に‘load＃i'が入力されると
制御回路１３７よりラツチ信号線１４３にラツチ
信号が出力され、Yinラツチ１３６にラツチされ
ているSiデータをラツチＡ１３８に貯える。この
ときセレクタ回路１４２は、零がYoutラツチ１
４７に入力されるようにする。またSo（ｊ≠ｉ）
の場合は、SoがYoutラツチ１４７に入力される
ように制御回路１３７がセレクタ制御信号線によ
り制御する。コマンド入力信号線９６は、コマン
ド‘load＃0'まで入力された後は、‘calc'コマ
ンドが入力される。このとき消失位置係数ラツチ
回路９３の制御回路１２６はセレクタ制御信号線
１２９を通じて消失位置係数データのうちの一つ
のセレクタ回路１２７で選択し出力信号線９７に
出力する。この出力されたデータは修正シンドロ
ームセル回路９４のサブセル１３０＃０のXinラ
ツチ１３５に入力される。同時にCOMinラツチ
１３４には信号‘calc'が入力され、Yinラツチ１
３６には零が入力される。Xinラツチ１３５が零
でなければ制御回路１３７はラツチ信号線１４３
にラツチ信号を出力し、ラツチＡ１３８にYinラ
ツチ１３６のデータをラツチＢ１３９に加算器１
４０の出力データをラツチする。またYoutラツ
チ１４７にも、この出力データをラツチするよう
セレクタ回路１４２で選択する。このときXinラ
ツチ１３５のデータはXoutラツチ１４９にラツ
チし、COMinラツチ１３４のコマンドを
COMoutラツチ１４５にラツチする。ラツチＢ１
３９にストアされたデータは、乗算器１４１で
Xinラツチ１３５のデータとガロア体の乗算をし
てその出力を加算器１４０に入力してラツチＡ１
３８のデータとガロア体の加算を行う。これをサ
ブセル＃１〜＃2t−１も同様に行う。ただし、
COMin１３１，Xin１３２、Yin１３３の各入力
信号線は、それぞれ前段のCOMout１４８、
Xout１４９、Yout１５０の各出力信号線と接続
されている。ある消失位置係数αijについてナン
バー＃2t−１のサブセルまで行うことによつて、
演算（Ｘ−αi）・Ｓ（ｘ）modX2t（ｔ＝ｄ−１／２） を行つたことになる。‘calc'コマンドを2t回入
力して、ラツチ群１２５のデータをすべて出力信
号線９７より出力した後、コマンド入力信号線９
５には‘end'コマンドが入力される。このとき消
失位置係数ラツチ回路９３の制御回路１２６は、
ラツチ制御信号線１２８にシフト信号を出力し、
ラツチ群６４のデータを出力信号線１０１に次々
と出力する。このとき入力信号線LDin９５には
零が入力される。一方修正シンドロームセル９４
のサブセル１３０＃０では‘end'コマンドがコマ
ンド入力線１３１からCOMinラツチ１３４に入
力されると制御回路１３７によりラツチ信号線１
４３にラツチ信号を出力しラツチＡ１３８にYin
ラツチ１３６のデータを入力すると共にYoutラ
ツチ１４７に加算器１４０の出力データをラツチ
する。このときXinラツチ１３５、Yinラツチ１
３６には零が入力される。ナンバー＃１〜＃2t−
１のサブセル１３３０もCOMin１３４、Xin１
３２、Yin１３３の各ラツチに前段のCOMout１
４５、Xout１４６、Youtの各ラツチのデータが
入力されるだけで同様の動作をする。この‘end'
コマンドを2t回出力することにより修正シンドロ
ームSε（ｘ）は出力信号線９９より出力される。
修正シンドローム−GCDインターフエイス回
路１０２は従来装置のシンドローム−GCDイン
ターフエイス回路１２６の機能を有すると共に、
消失位置係数ラツチ回路９３の出力信号線１０１
から入力されるdijを次段の消失位置係数ラツチ
回路１０３へ送る。また消失の個数nεを調べte＝
ｔ＋「nε／２（「はガウス記号で正整数切り
上げを示し、また、ｔは消失個数nεが０のとき
の訂正可能なシンボル数、teは誤り消失位置多項
式σ（ｘ）がとりかえる最大次数である）を求め
GCDセル回路７へ次数データと共に次数入力信
号線８へ出力する。GCDセル回路７は従来装置
と同じ働きをするがそのサブセル１５０は構造が
本発明においては異なり、入力信号線tin１５１、
ｔ遅延ラツチ１５２、出力信号線tout１５３を有
し、入力信号線tin１５１からteを‘start＝1'コ
マンドと共に入力する。このteは、従来装置のｔ
データにとつて変わるものである。
路１０２は従来装置のシンドローム−GCDイン
ターフエイス回路１２６の機能を有すると共に、
消失位置係数ラツチ回路９３の出力信号線１０１
から入力されるdijを次段の消失位置係数ラツチ
回路１０３へ送る。また消失の個数nεを調べte＝
ｔ＋「nε／２（「はガウス記号で正整数切り
上げを示し、また、ｔは消失個数nεが０のとき
の訂正可能なシンボル数、teは誤り消失位置多項
式σ（ｘ）がとりかえる最大次数である）を求め
GCDセル回路７へ次数データと共に次数入力信
号線８へ出力する。GCDセル回路７は従来装置
と同じ働きをするがそのサブセル１５０は構造が
本発明においては異なり、入力信号線tin１５１、
ｔ遅延ラツチ１５２、出力信号線tout１５３を有
し、入力信号線tin１５１からteを‘start＝1'コ
マンドと共に入力する。このteは、従来装置のｔ
データにとつて変わるものである。
消失位置係数ラツチ回路１０３は、前段の消失
位置係数ラツチ回路９３のセレクタ回路を除いた
構成であり、制御回路は‘start＝1'コマンドが
コマンド入力信号線９に入力されたのち2t回のラ
ツチ信号を出力してαiをラツチし、‘start＝1'コ
マンドがGCD−乗算インターフエイス回路１０
６にコマンド出力信号線１２から入力されるとき
同時に消失位置係数αiも出力信号線１０５から出
力する。
位置係数ラツチ回路９３のセレクタ回路を除いた
構成であり、制御回路は‘start＝1'コマンドが
コマンド入力信号線９に入力されたのち2t回のラ
ツチ信号を出力してαiをラツチし、‘start＝1'コ
マンドがGCD−乗算インターフエイス回路１０
６にコマンド出力信号線１２から入力されるとき
同時に消失位置係数αiも出力信号線１０５から出
力する。
GCD−乗算インターフエイス回路１０６は
GCDセル回路７のコマンド出力信号線１２より
‘start＝1'コマンドが入力されると同時に次数
データ出力信号線１１より出力される次数データ
（degA，degB，degL，degM及びte）から、第
１０図の８６，８７，８８の演算を行う。ただし
演算８５及び演算８６のｔはteにおきかわる。こ
うして誤り−消失数値多項式ｎ（ｘ）と誤り位置
多項式σe（ｘ）に識別後コマンド入力信号線１１
０に‘load＃1'（ｉ＝2t〜０）を入力し、誤り−
消失数値多項式ｎ（ｘ）は入力信号線１０９より、
誤り−消失数値多項式係数ラツチ１０８にラツチ
され、誤り位置多項式σe（ｘ）は乗算セル回路１
０７の入力信号線１１１より入力する。
GCDセル回路７のコマンド出力信号線１２より
‘start＝1'コマンドが入力されると同時に次数
データ出力信号線１１より出力される次数データ
（degA，degB，degL，degM及びte）から、第
１０図の８６，８７，８８の演算を行う。ただし
演算８５及び演算８６のｔはteにおきかわる。こ
うして誤り−消失数値多項式ｎ（ｘ）と誤り位置
多項式σe（ｘ）に識別後コマンド入力信号線１１
０に‘load＃1'（ｉ＝2t〜０）を入力し、誤り−
消失数値多項式ｎ（ｘ）は入力信号線１０９より、
誤り−消失数値多項式係数ラツチ１０８にラツチ
され、誤り位置多項式σe（ｘ）は乗算セル回路１
０７の入力信号線１１１より入力する。
本発明において付加した誤り−消失位置多項式
σ（ｘ）を求める乗算セル回路１０７のサブセル
＃０〜＃2tは、修正シンドロームのサブセル１３
０と同じ構造であり、その動作は修正シンドロー
ムセル回路９４と同じである。
σ（ｘ）を求める乗算セル回路１０７のサブセル
＃０〜＃2tは、修正シンドロームのサブセル１３
０と同じ構造であり、その動作は修正シンドロー
ムセル回路９４と同じである。
乗算−Evaluationインターフエイス回路１１
６は出力信号線１１４より入力される誤り位置多
項式σ（ｘ）よりその誤り位置多項式の微分
σ′（ｘ）を求めて、誤り−消失数値多項式ｎ（ｘ）
ともどもEvaluationセル回路１６に入力する。
以降のデータ処理は従来装置と同様である。ただ
し、Evaluationセル回路１６はナンバー＃０〜
＃2tのサブセル７３により構成され、σ（αi）は
＃2tのサブセル出力、ｎ（αi）、σ′（αi）は＃2t−
１
のサブセル出力となる。
６は出力信号線１１４より入力される誤り位置多
項式σ（ｘ）よりその誤り位置多項式の微分
σ′（ｘ）を求めて、誤り−消失数値多項式ｎ（ｘ）
ともどもEvaluationセル回路１６に入力する。
以降のデータ処理は従来装置と同様である。ただ
し、Evaluationセル回路１６はナンバー＃０〜
＃2tのサブセル７３により構成され、σ（αi）は
＃2tのサブセル出力、ｎ（αi）、σ′（αi）は＃2t−
１
のサブセル出力となる。
なお、上記実施例では、GFROM１４を用いた
が、これは第２図のαi発生回路１１９を用いても
よい。
が、これは第２図のαi発生回路１１９を用いても
よい。
以上述べたようにこの発明は、受信データを入
力してシンドロームを求めるシンドロームセル回
路と、上記受信データと消失位置に対するフラグ
信号を出力するフラグ信号出力回路と、上記フラ
グ信号に対応する消失位置シンボルデータを生成
する消失位置発生回路と、上記シンドロームセル
回路から出力されるシンドロームのデータ系列か
ら消失位置の情報を除く修正シンドロームを出力
する修正シンドロームセル回路と、上記修正シン
ドロームのデータ系列から誤り位置多項式σe
（ｘ）及び誤り消失数値多項式ｎ（ｘ）の係数のデ
ータ系列を求めるGCDセル回路と、上記誤り位
置多項式σe（ｘ）のデータ系列と上記消失位置シ
ンボルデータの消失位置データ系列とから誤り消
失位置多項式σ（ｘ）の係数データを出力する乗
算セル回路と、誤り消失位置多項式σ（ｘ）及び
誤り消失数値多項式ｎ（ｘ）の係数データとから
誤り消失位置及び数値を求めるEvaluationセル
回路と、Evaluationセル回路によつて求められ
た誤り消失位置及び数値に基づいて上記受信デー
タを訂正するためのゲート回路とを具備したの
で、誤り−消失訂正を簡単な制御でパイプライン
方式の処理ができ、VLSI化がしやすいという効
果がある。
力してシンドロームを求めるシンドロームセル回
路と、上記受信データと消失位置に対するフラグ
信号を出力するフラグ信号出力回路と、上記フラ
グ信号に対応する消失位置シンボルデータを生成
する消失位置発生回路と、上記シンドロームセル
回路から出力されるシンドロームのデータ系列か
ら消失位置の情報を除く修正シンドロームを出力
する修正シンドロームセル回路と、上記修正シン
ドロームのデータ系列から誤り位置多項式σe
（ｘ）及び誤り消失数値多項式ｎ（ｘ）の係数のデ
ータ系列を求めるGCDセル回路と、上記誤り位
置多項式σe（ｘ）のデータ系列と上記消失位置シ
ンボルデータの消失位置データ系列とから誤り消
失位置多項式σ（ｘ）の係数データを出力する乗
算セル回路と、誤り消失位置多項式σ（ｘ）及び
誤り消失数値多項式ｎ（ｘ）の係数データとから
誤り消失位置及び数値を求めるEvaluationセル
回路と、Evaluationセル回路によつて求められ
た誤り消失位置及び数値に基づいて上記受信デー
タを訂正するためのゲート回路とを具備したの
で、誤り−消失訂正を簡単な制御でパイプライン
方式の処理ができ、VLSI化がしやすいという効
果がある。
第１図はこの発明の一実施例によるシストリツ
クアルゴリズムに基づいた復号化装置を示す構成
図、第２図はこの発明における消失位置係数発生
回路の構成図、第３図はこの発明における消失位
置係数ラツチ回路の構成図、第４図はこの発明に
おける修正シンドロームセル回路、乗算セル回路
のサブセル回路を示す構成図、第５図はこの発明
におけるGCDセル回路のサブセル回路のモデル
図、第６図は従来のシストリツクアルゴリズムに
基づいた復号化装置の構成図、第７図はシンドロ
ームセル回路のサブセルモデル図、第８図は従来
装置のGCDセル回路のサブセルのモデル図、第
９図はEvalutionセル回路のサブセルのモデル図、
第１０図は従来装置のGCD問題の解法アルゴリ
ズムのフローチヤートである。 １…シンドロームセル回路、９０…フラグ信号
発生回路、８９…消失位置発生回路、９４…修正
シンドロームセル回路、７…GCDセル回路、１
０７…乗算セル回路、１６…Evalutionセル回路、
２２…ゲート回路。なお、各図中同一符号は、同
一または相当部分を示す。
クアルゴリズムに基づいた復号化装置を示す構成
図、第２図はこの発明における消失位置係数発生
回路の構成図、第３図はこの発明における消失位
置係数ラツチ回路の構成図、第４図はこの発明に
おける修正シンドロームセル回路、乗算セル回路
のサブセル回路を示す構成図、第５図はこの発明
におけるGCDセル回路のサブセル回路のモデル
図、第６図は従来のシストリツクアルゴリズムに
基づいた復号化装置の構成図、第７図はシンドロ
ームセル回路のサブセルモデル図、第８図は従来
装置のGCDセル回路のサブセルのモデル図、第
９図はEvalutionセル回路のサブセルのモデル図、
第１０図は従来装置のGCD問題の解法アルゴリ
ズムのフローチヤートである。 １…シンドロームセル回路、９０…フラグ信号
発生回路、８９…消失位置発生回路、９４…修正
シンドロームセル回路、７…GCDセル回路、１
０７…乗算セル回路、１６…Evalutionセル回路、
２２…ゲート回路。なお、各図中同一符号は、同
一または相当部分を示す。
Claims (1)
- 【特許請求の範囲】 １ 受信データを入力してシンドロームを求める
シンドロームセル回路と、上記受信データと消失
位置に対するフラグ信号を出力するフラグ信号出
力回路と、上記フラグ信号に対応する消失位置シ
ンボルデータを生成する消失位置発生回路と、上
記シンドロームセル回路から出力されるシンドロ
ームのデータ系列から消失位置の情報を除く修正
シンドロームを出力する修正シンドロームセル回
路と、上記修正シンドロームのデータ系列から誤
り位置多項式σe（ｘ）及び誤り消失数値多項式ｎ
（ｘ）の係数のデータ系列を求めるGCDセル回路
と、上記誤り位置多項式σe（ｘ）のデータ系列と
上記消失位置シンボルデータの消失位置データ系
列とから誤り消失位置多項式σ（ｘ）の係数デー
タを出力する乗算セル回路と、誤り消失位置多項
式σ（ｘ）及び誤り消失数値多項式ｎ（ｘ）の係数
データとから誤り消失位置及び数値を求める評価
セル回路と、評価セル回路によつて求められた誤
り消失位置及び数値に基づいて上記受信データを
訂正するためのゲート回路とを具備したことを特
徴とする復号化装置。 ２ 上記修正シンドロームセル回路は、シンドロ
ームのデータ系列をストアするレジスタと、上記
消失位置シンボルデータが入力されたときレジス
タのデータをシフトするシフト回路と、レジスタ
のデータと消失位置シンボルデータとを乗算する
乗算回路と、乗算回路の出力と上記シフト回路の
出力とを加算する加算器とを備えたことを特徴と
する特許請求の範囲第１項記載の復号化装置。 ３ 上記GCDセル回路は、nεを消失個数、ｔを
消失個数が０のときの訂正可能なシンボル数、te
を誤り消失位置多項式σ（ｘ）がとりかえる最大
次数とするとき、 te＝ｔ＋「nε／２ （ただし、「はガウス記号で正整数切り上げ
を示す） の演算を行う演算回路を備えていることを特徴と
する特許請求の範囲第１項または第２項記載の復
号化装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60262168A JPS62122332A (ja) | 1985-11-21 | 1985-11-21 | 復号化装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60262168A JPS62122332A (ja) | 1985-11-21 | 1985-11-21 | 復号化装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS62122332A JPS62122332A (ja) | 1987-06-03 |
| JPH047847B2 true JPH047847B2 (ja) | 1992-02-13 |
Family
ID=17372003
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60262168A Granted JPS62122332A (ja) | 1985-11-21 | 1985-11-21 | 復号化装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS62122332A (ja) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH07112160B2 (ja) * | 1986-04-21 | 1995-11-29 | ソニー株式会社 | 誤り訂正符号の復号方法 |
| JPS641334A (en) * | 1987-06-24 | 1989-01-05 | Matsushita Electric Ind Co Ltd | Error corrector |
| JP2775432B2 (ja) * | 1987-11-23 | 1998-07-16 | 博一 岡野 | 誤り訂正／誤り検出／消失誤り訂正を同時に行うリード・ソロモン符号の復号装置 |
| JPH0831804B2 (ja) * | 1989-05-09 | 1996-03-27 | 三菱電機株式会社 | 消失誤り訂正回路 |
| US5115436A (en) * | 1990-05-04 | 1992-05-19 | Bell Communications Research | Forward error correction code system |
-
1985
- 1985-11-21 JP JP60262168A patent/JPS62122332A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS62122332A (ja) | 1987-06-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0114938B1 (en) | On-the-fly multibyte error correction | |
| EP1131893B1 (en) | Forward error corrector | |
| US5517509A (en) | Decoder for decoding ECC using Euclid's algorithm | |
| JP3970337B2 (ja) | 大規模データ・ブロックのためのハードウェア最適化リード・ソロモン・デコーダ | |
| EP0729611A1 (en) | Reed-solomon decoder | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| CN102684709B (zh) | 一种译码方法及其译码装置 | |
| US4841300A (en) | Error correction encoder/decoder | |
| CN1653699B (zh) | 软判定解码里德-索洛蒙码的方法 | |
| JP2004032737A (ja) | リード−ソロモン復号器 | |
| US6263471B1 (en) | Method and apparatus for decoding an error correction code | |
| JPH047847B2 (ja) | ||
| JP2800723B2 (ja) | リードソロモン復号器の誤り位置検出回路 | |
| Zhu et al. | High-speed re-encoder design for algebraic soft-decision Reed-Solomon decoding | |
| JP2000020333A (ja) | 復号装置、演算装置およびこれらの方法 | |
| US20020029367A1 (en) | Decoding circuit and decoding method thereof | |
| US20050050131A1 (en) | Data processing system and method | |
| JPS5975732A (ja) | 復号器 | |
| JPH0750595A (ja) | 復号化装置 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| KR940011659B1 (ko) | 유클리드 알고리즘 연산장치 | |
| JPS6217256B2 (ja) | ||
| JP2000295116A (ja) | 誤り修正符号化方法 | |
| JP2710176B2 (ja) | 誤り位置及び誤りパターン導出回路 | |
| JPH08139612A (ja) | リード・ソロモン誤り訂正符号復号化回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |