JPH02214332A - 誤り訂正装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は誤り訂正装置に関し、特にその処理速度の高速
化に関するものである。

〔従来の技術〕

従来、プログラム制御形式の誤り訂正装置において、プ
ログラムのジャンプ（処理の移行）の判断及びこれに伴
うプログラムカウンタの変更はある判定結果がでる毎に
、その度実行されている。

従来の処理の過程をリードソロモン符号のシンドローム
判定を例として説明する。リードソロモツ ン符号は巡回型の多元プロ〜り符号であり、近年様々な
分野に応用され広く知られる様になった。

今、符号長（ｎ）、情報シンボル（ｋ）個、検査シンボ
ル（ｎ−ｋ）個からなるリードソロモン符号について、
その復号法を説明する。但し、上記各シンボルは（ｍ）
個の２進ビツトつまり２１個の元を有する有限体である
ガロア体ＧＦ　（２”）の元である。

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

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

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

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

ここで、シンドローム別を Ｓ＋＝Ｒ（α１）〔但しｉ＝ｏ、　　１・・・２ｔ　−
１）・・・（５）の如（定義したとすると、上記（３）
式よりＳ＋＝Ｃ（α’）　十Ｅ　（α′） となる。

この場合、Ｃ（ｘ）はｇ　（ｘ）で常に割り切れるので
Ｃ（α′）＝Ｏ であるから Ｓ＋＝Ｅ（α′） となる。そこで、上記（４）式より Ｓ＋＝Ｅ（α’）　＝ΣＹ＋（α’）’−ΣＹＩＸ、’
　・−・−（６）と表わすことができる。但し、αＩ：
　Ｘ　、とおいたもので、ｘｊはαＪにおけるエラーロ
ケーションを表わしている。

ここで、エラーロケーション多項式σ（ｘ）はエラー数
をｅとして σ　（Ｘ）　　＝　ＴＩ　　（ｘ−Ｘ＋）＝Ｘ０＋σ１
ｆ−１＋・・・＋σ８　・・・・・・・・・・・・・・
　（７）と定義される。

また、（７）式のσ１〜σ６はシンドロームＳ。

との間で次のように関係付けられる。

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

（ｎ）　（ｓ）　式によりエラーロケーション多項式の
係数σ、〜σ。を計算する。

（ｍ）（７）式によりエラーロケーション多項式の根Ｘ
ｉを求める。

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

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

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

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

すなわち、この場合の生成多項式ｇ　（Ｘ）はｇ（ｘ）
　＝（ｘ＋１）　（ｘ＋α） （Ｘ＋α２）（ｘ＋α３） となり、２重エラーまでの訂正が可能となるものである
。

今、実際に誤り訂正を行う場合を考えると、想定される
エラーの数ｅはｅ　＝　０　、　　ｅ　＝　ｌ　、　　
ｅ　＝　２　。

ｅ≧３の場合が考えられる。ｅ＝ｏの場合には受信符号
語が正しいのであるから、誤り訂正処理は行わない。ま
たｅ≧３の場合も訂正能力を越えているわけであるから
、エラーフラグを立てること以外の誤り訂正処理は行わ
ない。即ち、実際にはｅ＝１の場合とｅ＝２の場合に誤
り訂正処理を行うことになる。

誤り訂正処理としては、上述の復号手順（Ｉ）。

（ＩＩ）に対応して概路次の様な手順をふむ。

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

（ｂ）シンドロームＳ。−８３を検査し、５ｏ＝Ｓ。

＝Ｓ　２＝Ｓ　３＝Ｏの場合は、ｅ＝０と判断して誤り
訂正処理を終了する。更に、シンドローム８０〜Ｓ３の
うち、いずれか１つの値のみが０の場合はｅｆ−１であ
り、いずれか２つ以上の値が０の場合にはｅ≧３である
ことが（６）式から明らかである。

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

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

（９）式の解σ１は として求め、（ｌＯ）式の解σ８．σ２は・・・・・・
・・・・・・・・・・・・・（１１）として求める。

上述のエラーロケーション多項式の係数σ２を求める（
１１）式の演算を行う場合（Ｓ　Ｉ　Ｓ　３　＋　３２
　”　）という演算を行うことになるが、この演算を例
にとって、−数的な演算動作を説明する。

第３図は従来の一般的な演算動作を示すタイミングチャ
ートであり、以下このタイミングチャートを参照して説
明する。第３図中ＣＬＫは本例の演算処理タイミングを
決定するクロックである。

行列演算回路により生成されたシンドロームＳ。。

Ｓ、、Ｓ２．Ｓ３はシンドロームレジスタに記憶される
。まず、ｌクロック目にシンドロームＳ２をバスライン
に出力し、変換テーブルを通してガロア体の元のベクト
ル表現から指数表現への変換（ＶＥ変換）を行ってレジ
スタｌに保持する。

２クロツク目にはシンドロームＳ２をバスラインに出力
し、同様にＶＥ変換してレジスタｌに保持する。ここで
、先程レジスタｌに保持しておいたシンドロームＳ２が
レジスタ２ヘシフトされる。

３クロツク目ではレジスタｌ及びレジスタ２に保持した
シンドロームを同時に乗除算回路に送り乗算され（Ｓ２
’）、演算し′ジスタに保持する。

次に、４クロツク目ではシンドロームＳ、をバスライン
に出力し、ｖＥ変換してレジスタ１に保持する。５クロ
ツク目では°シンドロームＳ３をバスラインに出力しＶ
Ｅ変換してレジスタｌに保持する。先程レジスタｌに保
持されたＳｌをレジスタ２ヘシフトする。６クロツク目
ではレジスタｌ及びレジスタ２に保持したシンドローム
を乗除算回路に送り乗算され（Ｓ、、Ｓ３）、再び変換
テーブルを通して今度は指数表現からベクトル表現への
変換（ＥＶ変換）を９行い、レジスタｌに保持する。７
クロツク目には先程演算レジスタに保持したＳ２２をバ
スラインに出力し、変換テーブルを通してＥＶ変換し、
レジスタｌに保持する。レジスタｌに保持されていたＳ
、。

Ｓ３はレジスタ２にシフトされる。

最後に８クロツク目にてレジスタｌ及びレジスタ２に保
持したシンドロームを加算回路に送り込み加算する。こ
の様にｌクロックごとに出力、変換及び演算を行い、式
ｓ２”＋ｓ、・Ｓ３の演算が終了する。

〔発明が解決しようとしている問題点〕しかし、上述の
如き手順で演算を行ったのでは、ｌクロック毎に単一の
演算及び変換を行うために、演算全体として処理時間が
長くなってしまう。また、上記演算以降の演算について
も同様に処理時間が長（なるため、誤り訂正装置全体と
しての処理時間が長くなり、高ビットレートの受信符号
を処理することが困難であった。

例えば、従来高ビットレートの受信符号について誤り訂
正を行う場合には、誤り訂正回路を複数並列に設けて並
列処理を行っていたが、これではハードウェア量が太き
（なってしまう。

かかる背景下に於いて、本発明はハードウェア量を増大
することな（誤り訂正装置に於ける処理速度を高速化す
ることを目的とする。

〔問題点を解決するための手段〕

かかる目的下に於いて、本発明にあっては、誤り訂正符
号を含む受信符号の誤りを訂正する装置において、誤り
訂正処理途中で発生する複数の演算データが夫々出力さ
れる複数のバスラインと、該複数のバスライン上の前記
複数の演算データに従い新たな演算データを発生する手
段とを具え、該新たな演算データに従い誤り訂正処理を
行う構成とした。

〔作　用〕

上述の如（構成することにより、複数の演算データを１
ステツプでデータバスに出力すると共に１つの演算処置
がこのステップにて行える。従って、従来に比し演算処
理時間が大幅に短縮できた。

〔実施例〕

以下、本発明の実施例について説明する。

第１図は本発明の一実施例としての誤り訂正装置の要部
をなす演算部の構成を示す図である。尚、本例は２重誤
り訂正を行うために４ワードのシンドロームを用いた演
算を行う演算部を例にとっている。

第１図に於いてｌはデータメモリ、２はメモリーコント
ローラ、３は行列式演算回路であり、３ａ。

３ｂ、　３ｃ、　３ｄは訂正動作中にシンドロームＳ。

。 Ｓ、、Ｓ２．Ｓ３の値を保持するためのシンドロームレ
ジスタである。４．　５．　７は前述したＶＥ変換。

ＥＶ変換等に対応した複数の関数テーブルを持ったＲＯ
Ｍ等で構成される変換テーブル、６は乗除算回路、８は
１バイトデータを一時保持するための一時レジスタ、９
は加算回路、１０．　１１は演算結果を保持するための
演算レジスタである。

次に、この演算部の演算動作の一例として、前述したエ
ラーロケーション多項式の係数σ２を求める演算、即ち
、（ＳＩＳ３＋５２２）／　（ＳＯ３２＋ｓ　、”）の
演算を行う場合の動作について第２図のタイミングチャ
ートを用いて説明する。

まず、ｌクロック目にてレジスタ３Ｃよりシンドローム
Ｓ２を同時に２つのバスライン（データバスＡ、データ
バスＢ）に出力させ、変換テーブル４゜５に於いて夫々
ＶＥ変換し、乗除算回路６に送出する。

該回路６で乗算された演算データＳ２２は再び変換テー
ブル７にて、今度はＥＶ変換され一時レジスタ８にて一
時保持される。

２クロツク目ではシンドロームＳ１及びＳ３をレジスタ
３ｂ、３ｄから夫々データバスＡ、　Ｂに同時に出力し
、夫々変換テーブル４．５にてＶＥ変換した後、乗除算
回路６にて乗算される。乗算された演算データＳ１・Ｓ
３は変換テーブル７にてＥＶ変換され加算回路９に送ら
れる。この時、先程−時レジスタに保持させておいたＳ
２２が加算回路９に送られ、Ｓｌ・Ｓ３と加算される。

そして、加算された演算データ（ｓ　２”＋ｓ　１・Ｓ
Ｓ）は演算レジスタｌＯに供給され、保持される。

次に３クロツク目では、レジスタ３ａ、３ｃからシンド
ロームＳ。及びＳ２を同時にデータバスＡ。

Ｂに出力し、これらは変換テーブル４，５にてＶＥ変換
された後、乗除算回路６にて乗算される。乗算された演
算データＳ。−８２は変換テーブル７にてＥＶ変換され
、−時レジスタ８にて一時保持される。

４クロツク目では、レジスタ３ｂからシンドロームＳ１
を同時にデータバスＡ、　Ｂに出力させ、夫々変換テー
ブル４．５にてＶＥ変換させて乗除算回路６に送る。該
回路６で乗算された演算データＳ、２は変換テーブル７
にてＥＶ変換されて、加算回路９に送られる。これと同
時に一時レジスタ８に保持されているデータＳ０・Ｓ２
も加算回路９に送られ、上記Ｓ、２と加算される。加算
された演算データ（Ｓｏ−３２＋Ｓ、２）は演算レジス
タ１１に保持される。

最後に５クロツク目にて演算レジスタ１０．．１１に保
持されているデータ（ｓ　２”＋ｓ　、・Ｓ３）及び（
Ｓｏ　’Ｓ２　＋３１”）をそれぞれデータバスＡ、　
　Ｂに出力し、変換テーブル４，５にてＶＥ変換させて
、乗除算回路６に送る。ここで、除算が行われてσ２を
求める（Ｓ　２”＋Ｓｌ　・Ｓ３）　／　（Ｓｏ　’Ｓ
２　＋ｓ、”）の演算が終了する。

ここまでの説明で明らかな様に、上述の演算部に於いて
は以後の四則演算についても同様に高速化できる。

即ち、上述の如（構成することにより誤り訂正処理全体
としてバスラインを複数設けるだけで、／１−ドウエア
量を増加させることなく高速処理を実現でき、磁気記録
媒体等から再生されたビデオ信号等の高ビットレートで
誤りの多い受信符号に対して誤り訂正を行うことの可能
な小型の装置が得られた。

尚、上述の実施例では複数の演算データを出力可能なバ
スラインを２つ設けているが、３本以上のバスラインを
設ければ演算処理の更なる高速化が図れる。また、演算
する演算式により乗除算回路。

加算回路及び−時レジスタ等の配置を適宜変更可能であ
ることは言うまでもない。

更に、上記実施例は２誤り訂正可能なリードソロモン符
号を例にとって説明したが、他の誤り訂正符号で誤り訂
正を行う誤り訂正装置についても、演算手順及び上記各
単位演算子の配置を変更することにより、同様に本発明
を適用することができ、かつ同様の効果が得られる。

〔発明の効果〕

以上説明した様に本発明によればハードウェア規模が小
さく、かつ高速で誤り訂正処理の行える誤り訂正装置が
得られるものである。

【図面の簡単な説明】

第１図は本発明の一実施例の誤り訂正装置の要部をなす
演算部の構成を示す図、 第２図は第１図の演算部による演算動作を説明するため
のタイミングチャート、 第３図は従来の誤り訂正装置に於ける演算動作を説明す
るためのタイミングチャートである。 図中、ｌはデータメモリ、２はメモリコントローラ、３
は行列演算回路、３ａ、　３ｂ、　３ｃ、　３ｄはシン
ドロームメモリ、４．５．７は夫々変換テーブル、６は
乗除算回路、８は一時レジスタ、９は加算回路、１０．
１１は演算レジスタ、Ａ、　　Ｂは夫々データバスであ
る。

Claims (3)

【特許請求の範囲】
1. （１）誤り訂正符号を含む受信符号の誤りを訂正する装
   置であって、誤り訂正処理途中で発生する複数の演算デ
   ータが夫々出力される複数のバスラインと、該複数のバ
   スライン上の前記複数の演算データに従い新たな演算デ
   ータを発生する手段とを具え、該新たな演算データに従
   い誤り訂正処理を行う誤り訂正装置。
2. （２）前記複数の演算データは夫々シンドロームであり
   、前記新たな演算データは、エラーロケーション多項式
   の係数であることを特徴とする特許請求の範囲第（１）
   項記載の誤り訂正装置。
3. （３）前記新たな演算データを発生する手段は前記複数
   のバスラインに出力を供給する複数の演算手段を具える
   ことを特徴とする特許請求の範囲第（１）項記載の誤り
   訂正装置。