JPH0472923A - リードソロモン符号の誤り検出及び訂正装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はディジタルビデオテープレコーダー（ＤＶＴＲ
）　、ディジタルオーディオテープレコーダー（ＤＡＴ
）等において、信頼性向上のために所定の方法で生成さ
れたパリティ信号を付加されたリードソロモン符号（以
下、Ｒ８符号）からなるディジタル信号を再生する場合
に、付加したパリティ信号を基に所定の方法で誤りを検
出し、元の正しい信号に訂正する誤り検出及び訂正装置
に係り、特に誤り位置多項式の係数及び各誤りの大きさ
を算出する算術演算部の回路構成方法に関する。

〔従来の技術〕

従来、Ｒ８符号の誤り検出及び訂正については、電子通
信学会論文誌　第Ｊ６４−Ａ巻、第２号（１９８１年２
月）第１３７頁ないし第１４４頁において論じられてい
る。

該誤り検出及び訂正は、 （１）シンドロームの計算及び誤りの検出（２）誤りシ
ンボル数の判定及び誤り位置多項式のの係数算出 （３）誤り位置多項式の根の導出 （４）誤りの大きさ算出 （５）訂正の実行 の手順で行われる。ここでは、データである１１シンボ
ル（１シンボル８ビツト）に対して、生成多項式 ％式％） により生成したパリティ４シンボルを付加したＲ８符号
である、（１５，１１）Ｒ８符号の復号を例にとり、復
号動作を説明する。なお、以下の説明の中の演算はすべ
て有限体ＧＦ（２”）上で行われる。

（１）シンドロームの計算及び誤りの検出符号長１５の
符号語Ｃ＝　（ｃ、４．　ｃｍ３．−、ｃｏ）を記録し
てこれを再生したとき、再生系列Ｒ＝（ｒｘｓｒ　ｒｘ
ａｔ・・・ｌ　ｒｏ）が再生されたとする。

ここで、再生系列Ｒに含まれる誤り系列すなわち再生系
列Ｒと符号語Ｃの差をＥ＝　（ｅｉ、、ｅ□３゜・・・
１８０）とするとき、Ｒは次のように表現される。

Ｒ（Ｘ）＝　Ｃ（Ｘ）十Ｅ　（Ｘ） ここで、生成多項式Ｇ（Ｘ）が式（１）であるから、シ
ンドロームは。

Ｓ１＝Ｒ（α１） ＝Ｅ（α’）　　ｉ＝ｏ、１，２．３　　　・・・（２
）で定義される。パリティのシンボル数だけ存在するシ
ンドロームは、再生系列Ｒに誤りがない場合にはすべて
０（０ベクトル）になる。これより、シンドロームにＯ
でないものが存在した場合は、再生系列Ｒの中に誤りが
発生しているということが検出できる。

シンドロームにＯでないものが存在し、誤りが検出され
たならば、以下の（２）〜（５）に示す訂正動作が行わ
れる。

（２）誤りシンボル数の判定、及び誤り位置多項式パリ
ティを４シンボル持つ（１５，１１）Ｒ８符号は２個以
下の誤りを訂正できるが、誤りが２個かそれより多いか
を判定することはできない。

そこで、まず訂正能力最大の２個の誤りが位置ｉ。

ｊにそれぞれＥｉ、ＥＡの大きさで発生したと仮定する
と、式（２）から次式が得られる。

Ｓ　ｏ　＝　Ｅ　ｌ　＋Ｅ　Ｊ　　　　　　　　　　　
　　・・・（３）Ｓｌ−α”Ｅ＋＋α’Ｅａ　　　　　
　　　　　　　　　・・（４）Ｓ２＝α２１Ｅ、＋α２
４Ｅ、　　　　　　　　　　　・・・（５）Ｓ３＝α３
′Ｅｌ＋α３ＪＥＪ　　　　　　　　　　　・・・（６
）誤り位置を根に持つ誤り位置多項式を２次式、ａ　（
Ｘ）＝　Ｘ２＋　ａ　”　Ｘ　＋ａ　’　　　　　　　
　−（７）とすると、 σ（Ｘ）＝（Ｘ＋α１）（Ｘ＋α４） であることから、 α８＝α３＋α α　　＝　α　　α の関係を持つ。したがって、式（３）〜（６）よりα１
＋α４．α１α４をＳ。−８３の関係式で表すことがで
きれば、誤り位置多項式（７）の係数をシンドロームの
演算により求めることができる。

式（４）、（５）よりα２１．α２Ｊの項を消去すると
、Ｓ２＋（α１＋α’）ｘｓ□＝α１α’　（Ｅ　＋　
＋　Ｅ　ａ）である。したがって、 Ｓ２＝αａＳ□十α”　Ｓ　ｏ−（８）の関係がある。

また、式（４）〜（６）より、５３＝ａａＳ２＋ａｂＳ
１　　　　　　　　−（９）の関係がある。式（８）、
（９）を行列表現で表すと、となるから、 ＝　１ である。したがって、 Δ＝Ｓ、”＋５ｏＳ２　　　　　　　　　−（１０）α
３＝（ＳｉＳ２＋５ｏＳ３）／Δ　　　　　　・−（１
１）αｂ＝（Ｓｚ”５ｉＳ３）／Δ　　　　　　　・・
・（１２）である。ここで、誤りが位置ｉ、大きさＥ、
の１つであった場合は、 Δ＝（α’　Ｅ　ｔ）２＋　Ｅ　ｔα２”　Ｅ　ｔ　＝
　０となることから、Δを誤りシンボル数の判定式とし
て用いることができる。Δ＝０のときは誤りが１つの場
合であり、その誤り位置多項式、σ（Ｘ）＝Ｘ＋αａ　
　　　　　　　　・・・（１３）の定数項α１は、σ（
Ｘ）＝Ｏがα１を解に持つことから１式（３）　、　（
４）より、 αａ＝α’＝８１／Ｓ。

と簡単に求めることができる。

（３）誤り位置多項式の根の導出 誤り位置多項式の根を求める方法としては、主にＲＯＭ
利用による直接解法とチェノ（Ｃｈｉｅｎ）探索の２方
法があるが、ここでは誤り位置多項式に全ての元を代入
し、それが０となる元を根とするチェン探索法について
説明する・ 誤りが２個の場合を考えると、チェノ探索は全ての元に
対するσ（Ｘ）、 σ（α０）＝（α０）２＋α８α０＋α８σ（α１）＝
（α１）２＋α０α１＋α１σ（α１４）＝（α１４）
２＋αａα１４＋αｂを求め、それがＯとなる元を根と
する方法である。

σ（α０）〜σ（α１４）は初期値として、Ｒ２（０）
＝１．に、（０）＝αａ、　Ｋ、（０）＝αｂσ（α’
）＝に、（０）十に１（０）＋に、（０）を与えると、
次のような繰り返し計算により求めることができる。

Ｋｇ（１）＝α２に２（ｉ　−１）ｔＫｉ（ｉ）＝αに
１（１１）。

ｘｏ（ｉ）＝ｘｏ（ｉ　−ｔ） σ（α１）＝ＫＺ（１）＋　Ｋｌ（１）＋ＫＯ（１）チ
ェノ探索は符号長相当のステップ数を必要とすることか
ら、誤り検出及び訂正をリアルタイム処理することはで
きない。しかし、チェノ探索を並列に動作させる等によ
り、誤り検出及び訂正をリアルタイム処理することは可
能である。

（４）誤りの大きさ算出 有限体ＧＦ（２”）上のＲ８符号は１シンボルが８ビツ
トで構成されるため、誤りを訂正するためには誤りの位
置だけでなく、誤りの大きさも求めることが必要である
。式（３）〜（６）を見れば明かなように、誤りの大き
さは誤りの位置とシンドロームから求めることができる
。式（３）、　（４）を行列表現を用いて表すと、 となる。したがって、 より、 Ｅ１＝（α’Ｓｏ＋Ｓ、）／Δ１　　　　　　　　　−
（１６）ＥＪ＝（α’　ｓ　ｏ　＋　Ｓ　１　）　／Δ
Ｊ　　　　　　　　　−（１７）Δｌ＝ΔＪ＝α１＋α
ｊ　　　　　　　　　　　・・・（１８）となる。１誤
りの場合は式（３）から明らかに、Ｅ１＝Ｓ、である。

（５）訂正の実行 以上のように求めた再生系列Ｒのｌｙｊ位置のシンボル
からＥ＋、ＥΔをそれぞれ除くことにより、誤りを訂正
することができる。

〔発明が解決しようとする課題〕 前記従来技術の（２）誤りシンボル数の判定、及び誤り
位置多項式の係数算出において、式（１０）〜（１２）
で表される２次の誤り位置多項式の係数αａαｂは、乗
算器、加算器、ＲＯＭを用いて次の手順で求めることが
できる（括弧内は乗算、乗算十加算、ＲＯＭ参照をそれ
ぞれ１ステツプとした時のステップ数）。

（ａ）　　αａ　α１の共通分母Δの計算（２）（ｂ）
　　１／Δの計算（逆光を予め記憶したＲＯＭによる）
（１） （ｃ）　　α８の分子計算（２） （ｄ）　　α８の計算（１） （ｅ）　　α５の分子計算（２） （ｆ）　　αｂの計算（１） したがって、係数α８　α１を求めるためには合計９ス
テツプの演算を要する。さらに、誤りの数が３個、４個
と多くなると、誤り位置多項式の係数を求めるために必
要なステップ数はそれぞれ４４ステツプ、２２１ステツ
プと指数的に多くなる。これは前記従来技術の（４）誤
りの大きさ算出においても同様であり、誤りが２個、３
個、４個でそれぞれ９，３３，１２４ステツプの演算を
必要とする。しかし、Ｒ８符号の誤り検出及び訂正をリ
アルタイムで行う場合には、シンドロームの計算、誤り
の位置と大きさの計算、訂正の実行をパイプライン処理
するため、誤り位置と大きさの計算は符号長範囲内のス
テップ数で行わなければならない。

本発明の目的は誤り位置多項式の係数及び誤りの大きさ
算出に要するステップ数を低減する演算回路、及びその
効率的な回路構成法を提供することにある。

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

」二記目的はＲ８符号により符号化したディジタル信号
及び誤り検査符号からなるディジタルデータを一時的に
記憶するメモリと、該メモリに記憶された該ディジタル
データに対して所定の有限体上の演算を施すことにより
、該ディジタルデータの誤りを検出し、を個の誤りを訂
正する手段を有する誤り検出及び訂正装置において、誤
り位置多項式の係数及び各誤りの大きさを、（ｔ＋１）
個、または２ｔ個の乗算器及び加算器により並列に演算
することにより達成される。

〔作用〕

まず初めに、２　（＝ｔ）個までの誤り訂正能力を有す
るＲ８符号の誤り検出及び訂正装置の乗算器、加算器を
３　（＝ｔ＋１）並列構成にした場合に、２個の誤りが
検出された時の訂正を考える。

式（１０）〜（１２）で表される２次の誤り位置多項式
の係数α３　α５は以下の手順で求められる（括弧内は
要するステップ数）。

（ａ）　　Δ、α８の分子、α５の分子の並列計算（２
）（ｂ）　　１／Δの計算（１） （ｃ）　　α８　α５の並列計算（１）したがって、単
一の乗算器及び加算器によるステップ数の１／２以下の
合計４ステツプで係数α８　α５を求めることができる
。同様に、３個までの誤り訂正能力を有するＲ８符号の
誤り検出及び訂正装置の乗算器、加算器を４並列構成に
した場合、３次の誤り位置多項式の係数は１４ステツプ
で求めることができる。また、４個までの誤り訂正能力
を有するＲ８符号の誤り検出及び訂正装置の乗算器、加
算器を５並列構成にした場合、４次の誤り位置多項式の
係数は６２ステツプで求めることができ、いずれも単一
の乗算器及び加算器によるステップ数より大幅に低減す
ることができる。

５次以上の誤り位置多項式の各係数も分母は共通であり
、一般にｔ次の誤り位置多項式の係数はｔ個の係数の分
子を計算するｔ個の乗算器及び加算器と、共通の分母を
計算する１個の乗算器及び加算器により、ハードウェア
規模的に効率よく求めることができる。

また、誤りが２個の場合、誤りの大きさ算出に要するス
テップ数は上記誤り位置多項式の係数算出と同様な手順
により４ステツプとなり、これもまた１／２以下に低減
することができる。しかし、誤りが３個以上の場合の各
誤りの大きさの計算は、計算式の分母がそれぞれ異なる
ことから誤り位置多項式の係数算出手順とは異なる手順
を踏む。例えば誤りが４個の場合の誤りの大きさをＥ　
ｉ　ｙ　Ｅ　Ｊ　ｙＥｈ、Ｅｔそれぞれの分母をΔ１．
Δ３．Δ１．Δ、とすると、５（または４）並列構成に
した乗算器及び加算器による算出手順は以下のようにな
る。

（ａ）　　Δ４．Δ４．Δ１．Δ、の計算（１６）（ｂ
）　　１／Δ１の計算（１） （Ｃ）　　１／Δ、の計算（１） （ｄ）　　１／Δにの計算（１） （ｅ）　　１／八尤の計算（１） （ｆ）　　Ｅａｔ　ＥＪ、Ｅｋ、Ｅ兄の分子計算（］−
３）（ｇ）　　Ｅｉ、ＥＪ、Ｅｋ、Ｅｉの計算（１）し
たがって、各誤りの大きさＥ　１．　、　Ｅ　ａ　、　
Ｅ　ｋ。

Ｅｘは合計３４ステツプで求められる。ここで、上記（
ａ）と（ｆ）は並列に行うことが可能であるため、乗算
器、加算器を８（＝２ｔ）並列構成とするとさらにステ
ップ数を低減することができ、以下の手順により３４ス
テツプから２１ステツプに低減できる。

（、）　　Δ５．Δ６．Δ１．Δ、の計算、Ｅｌ、　Ｅ
Ｊ、　Ｅ＋ｔｔＥａの分子計算（１６） （ｂ）　　１／Δ１の計算（１） （ｃ）　　１／ΔＪの計算（１） （ｄ）　　１／Δにの計算（１） （ｅ）　　１／八〇の計算（１） （ｆ）　　Ｅ、、ＥＪ、Ｅｋ、Ｅ宛の計算（１）同様に
して、誤りが３個の場合は４（または３）並列構成にす
ると１３ステツプ、６並列構成にすると９ステツプで各
誤りの大きさを求めることができる。

このように、誤りが３個以上の場合、各誤りの大きさの
計算式は分母がそれぞれ異なり、各誤りの大きさは分母
を計算するｔ個と分子を計算するｔ個の合計２ｔ個の乗
算器及び加算器により効率よく求めることができる。

乗算器、加算器の並列個数を増せば増すほどハードウェ
ア規模は大きくなるため、（ｔ＋１）並列構成にするか
、２ｔ並列構成にするかはステップ数とハードウェア規
模の兼ね合いにより決定すればよい。

〔実施例〕

第１図は本発明の誤り検出及び訂正装置を、従来技術の
項で例示した（１５．１１）Ｒ８符号の復号に適用した
場合のブロック図を示したものである。Ｒ８符号の復号
は大きく分けて、シンドロームの計算及び誤りの検出、
誤りシンボル数の判定及び誤り位置多項式の係数算出、
誤り位置多項式の根の導出、各誤りの大きさ算出、入力
ディジタルデータの訂正の５つの段階を経ることにより
実行される。プログラムＲＯＭ１３０はそれら各段階に
おける回路の制御命令を予め記憶したものであり、プロ
グラムカウンタ１３１により発生するアドレスに応じて
回路の各部分に制御信号を供給する。以下第１図を用い
、本実施例の動作を各訂正段階に分けて簡単に説明する
。

（１）シンドロームの計算及び誤りの検出第１図におい
て、１０１は情報部Ｄ工。〜Ｄｏおよびパリティ部Ｐ３
〜Ｐｏからなる（１５．１１）Ｒ８符号を一時的に記憶
するメモリである。メモす１０１に記憶されたディジタ
ルデータはＤｌｏから順次読み出され、シンドローム生
成部１０２に送られる。シンドローム生成部１０２では
メモリ１０１から読み出されたディジタルデータＰＤか
ら、（１５，１１）Ｒ８符号の誤りを検出、訂正する際
に必要となる４つのシンドロームＳ。−８３を生成する
。第２図は第１図のシンドローム生成部１０２の詳細図
であり、図のようにＳＳｏ　レジスタ２０１、Ｓ８１　
レジスタ２０２、ＳＳ２　レジスタ２０３、Ｓ８３レジ
スタ２０４、加算回路２０５〜２０８、α、Ｕ２　α３
器２０９〜２１１により構成されている。ここでは−例
として、シンドロームＳ３を求める手順について説明す
る。

（ａ）まず、ＳＳｏ　レジスタ２０１、ＳＳルジスタ２
０２、Ｓ８２　レジスタ２０３、Ｓ８３　レジスタ２０
４がすべてクリアされてＯの状態となる。

（ｂ）Ｄよ。が第１図のメモリ１０１から読み出され、
加算回路２０８に入力される。一方、ＳＳ３レジスタ２
０４の内容０とＵ３の乗算がα３器２１１で行われ、こ
の結果も同時に加算回路２０８に供給される。ここで、
α３器の入力を１＝（Ｕ７．　ｔｒ６．　ｕ＝、　Ｕ４
．　Ｕ３．　Ｕ２．　Ｕ、、　Ｕ、）、出力をＯ＝　（
Ｖ７．Ｖ、、Ｖ５．Ｖ、、Ｖ３．Ｖ２．Ｖ工。

Ｖ、＞　とすると、 ０　＝　（Ｕ、、ＵｓｔｔＪｓ、ＬＪ４．Ｕ３．Ｕ２．
Ｕｔ、Ｕｏ）ｘ（０，０，０，０，１，０，０，０） ＝（Ｕ７α７＋Ｕ６α６＋Ｕ５α５＋Ｕ４α４＋Ｕ３α
３＋Ｕ２α２＋Ｕ工α＋Ｕｏ）×α ＝（Ｕ７α１１１　＋　ｕ６α９＋Ｕ、α９＋Ｕ４α７
＋Ｕ３α６＋Ｕ２α５＋Ｕ１α’＋Ｕｏα３）である。

有限体ＧＦ（２８）の原始多項式は、Ｘｓ＋Ｘ’＋Ｘ３
＋Ｘ２＋　１　＝　０であるから、 α８＝α４＋α３＋α２＋１ α９＝α５＋α４＋α３＋α α１０＝α６＋α５＋α４＋α２ である。したがって、 ０＝Ｕ、（α６＋α５＋α４＋α２）＋ＵＧ（α５＋α
４＋α＋α）＋Ｕ５（α４＋α３＋α２＋１）＋Ｕ、α
７＋Ｕ、α＋Ｕ２α’＋Ｕ１α’＋Ｕｏａ３ ＝Ｕ４α７＋（Ｕ７＋Ｕ３）α６＋（Ｕ７＋Ｕ、＋Ｕ２
）α５十（Ｕ、十Ｕ６＋ＵＳ十Ｕ１）α’＋（Ｕ６＋Ｕ
５＋Ｕ、）α３十（Ｕ７＋Ｕ５）α２＋Ｕ６α＋Ｕ５ より、 ｖ７＝Ｕ４ ｖ６＝Ｕ３＋Ｕ７ Ｖ、＝Ｕ２＋Ｕ、＋Ｕ７ ■４−Ｕ□＋Ｕ５＋Ｕ６＋Ｕ７ Ｖ３＝Ｕ、＋Ｕ５＋Ｕ６ Ｖ２＝Ｕ、＋Ｕ７ Ｖ、＝Ｕ。

Ｖ、＝ＵＳ の関係が得られる。したがって、第３図に示すようにα
３器は８個の排他的論理和３０１〜３０８で構成するこ
とができる。また、α器２０９、α２器２１０、及び以
降で用いるαのべき果樹（固定係数乗算器と呼ぶ）はす
べてこの方法で構成できる。

加算回路２０８では、２つの入力をビットごとに排他的
論理和演算しく２０５〜２０７も同様である）、その結
果を新しくＳ８３　レジスタ２０４にセットする。式で
表せば次の様になる。

ｏ×α３＋Ｄ１ｏ＝Ｄ１ｏ−）ＳＳ３ （ｃ）加算回路２０８にはメモリ１０１がら読み出され
たり、と、ＳＳ３　レジスタ２０４の内容とα３の積が
入力する。加算回路２０８は上述のようにビットごとの
排他的論理和演算（以下、単に加算と称す）を行い、そ
の結果をＳ８３　レジスタ２０４にセットする。

Ｄ１ｏ×α３＋Ｄ、→ＳＳ３ 以下同様の操作が繰り返され、最後にメモリ１０１から
Ｐ。が読み出され、最終的には次の値がＳＳ３　レジス
タ２０４にセットされる。

（・・・（（Ｄ１０Ｘα３＋Ｄ９）×α３＋ＤＩ＋）−
＋Ｐ□）Ｘα３＋Ｐ。

→Ｓ８３ すなわち、 ＤｌｏＸ（α”）１４＋ＤｇＸ（α３）１３＋−＋Ｐ□
Ｘα３＋Ｐ。

→ＳＳ３ これは、情報部Ｄ１ｏ−Ｄｏおよびパリティ部Ｐ３〜Ｐ
、からなる（１５，１１）Ｒ８符号のシンドロームＳ３
である。

他のシンドロームＳ。、Ｓ□ｔ８２　も同様に、それぞ
れに対応する演算回路において、メモリ１０１から読み
出されるデータＤ□。、・・・、Ｐｏ　がら生成され、
それぞれＳＳｏ　レジスタ２０１、ＳＳ□　レジスタ２
０２、Ｓ８２　レジスタ２０３にセラｌ〜される。

このようにして求められたシンドロームＳ。〜Ｓ３は、
５Ｓｏ−８Ｓ３レジスタ２０１〜２０４より第１図０検
出器１０３及びＳ。−８３レジスタ１０４〜１０７に供
給される。０検出器１０３はシンドロームＳ。−８３が
全てＯであるかどうかを検出する、すなわち、入力デー
タの誤りの有無を検出する回路であり、その詳細図は第
４図で示される。論理和４０１〜４０４にはシンドロー
ムＳ。

〜Ｓ３それぞれのビット成分が入力し、すべてのビット
成分がＬＬ　Ｏ″′、すなわちシンドロームが０であれ
ばｉｔ　Ｏ”を出力する。それぞれの出力はＮＯＲゲー
ト４０５に入力し、シンドロームＳ。

〜Ｓ３のすべてがＯであれば、Ｏ検出器１０３の出力Ｎ
Ｅは１１１”になる。信号ＮＥはプログラムカウンタ１
３１に供給され、ＮＥが“Ｏ”、すなわち入力データに
誤りが存在すればプログラムカウンタ１３１はカウント
を開始し、以下の訂正動作が行われる。

（２）誤り位置多項式の係数算出 誤り位置多項式の係数を求める演算は、プログラムＲＯ
Ｍ１３０の制御により乗算器、及び加算器等からなる制
御回路を３並列構成にした算術演算部１０８で行われる
。

本発明の骨子である算術演算部１０８は、従来技術の項
で記述した誤り位置多項式の係数及び誤りの大きさを算
出するために必要な演算を行う部分であり、そのブロッ
ク図は第５図に示される。

第５図において、５０１はレジスタを選択するマルチプ
レクサ、５０２〜５０４は有限体Ｇ　Ｆ　（２８）上の
乗算器、５０５〜５０７は加算器及び論理和、論理積等
からなる制御回路、５０８は入力の逆先を出力するＲＯ
Ｍ、５０９〜５１１はレジスタである。ここで、有限体
Ｇ　Ｆ　（２８）上の乗算ＵＸＶは、Ｕ＝　（Ｕ７．Ｕ
、、Ｕ５．Ｕ４．Ｕ３．Ｕ２．Ｕｌ。

Ｕｏ）、Ｖ＝（Ｖ７．　Ｖ６．　Ｖ５．　Ｖ、、　Ｖ３
．　Ｖ２．　Ｖｌ。

Ｕｏ）とすると、 Ｕ　Ｘ　Ｖ　＝　Ｕ　Ｘ　Ｖ　ｏＸ　ａ＋ＵＸＶ□×α
１ ＋ＵＸＶ１Ｘα７ と表すことができるから、第５図の乗算器５０２〜５０
４は第６図のように構成できる。６０１〜６０８は固定
係数乗算器、６４個の６０９は２人力論理積ゲート、６
１０〜６１７はパリティジェネレータ回路である。前述
のように、固定係数乗算器は排他的論理和ゲートから、
パリティジェネレータもたは排他的論理和ゲートにより
構成されるので、有限体ＧＦ（２１１）上の乗算器５０
２〜５０４は、２人力論理積ゲートと排他的論理和ゲー
トにより構成できる。以下第５図を用いて、誤りが２個
の場合の誤り位置多項式の係数、すなわち式（１０）〜
（１２）、 ％式％（１０） の算出手順を簡単に説明する。

（ａ）プログラムＲＯＭ１３０から″乗算器の命令が制
御回路５０５〜５０７に、レジスタを選択する信号がマ
ルチプレクサ５０２に出力され、乗算器５０２〜５０４
ではそれぞれＳ１×Ｓ１゜５１ＸＳ２，５２ＸＳ２ｔ計
算し、ＡＬ／ジスタ５０９〜Ｃレジスタ５１１にストア
する。

Ｓ、２　　→　Ａ Ｓ１Ｓ２→　Ｂ ５２２　→　Ｃ （ｂ）次に、プログラムＲＯＭ１３０から“乗算″十加
算″′の命令が出され、乗算器５０２〜５０４ではそれ
ぞれ５ＩＩＸ　ＳＫＩ　ＳＱＸ　Ｓｓ−ｓ、ｘＳ３　を
計算し、Ａレジスタ５０９〜Ｃレジスタ５１１の内容に
加える。

Ｓ１２＋５ｏＳ２　　→　Ａ ＳｉＳ２＋５ｏＳ３　→　　Ｂ ｓ２”＋５１ｓ３　　　→　Ｃ （Ｑ）　　“逆光”命令によりＲＯＭ５０８にはＡレジ
スタ５０９の内容、乗算器５０２〜５０４にはすべて′
０′が入力される。制御回路５０６゜５０７は乗算結果
（Ｏｊ　を出力し、Ｂレジスタ５１０、Ｃレジスタ５１
１に加える。また、制御回路５０５はＲＯＭ５０８の出
力、すなわちＡレジスタ５０９の内容の逆光を出力し、
Ａレジスタ５０９にストアする。

１　／　（ｓ　ｘ”　＋　ｓ　ｏ　Ｓ　２）　　　→　
ＡＳｉＳ、＋５ｏＳ３＋Ｏ−＋　　Ｂ ｓ２”＋５ｏＳ３＋Ｏ→　Ｃ （ｄ）最後に、″乗算器命令により乗算器５０３はＡレ
ジスタ５０９とＣレジスタ５１１の内容を、乗算器５０
４はＡレジスタ５０９とＢレジスタ５１０の内容を乗算
し、それぞれＢレジスタ５１０、Ｃレジスタ５１１にス
１−アする。また、乗算器５０２には′１′と′１″が
入力し、その乗算結果′１′をＡレジスタ５０９にスト
アする。

５１８２＋５ｆｌＳ３ １　　　　　　　　　　　　→　　Ａ 以上の手続きにより、２次の誤り位置多項式の１次の項
の係数αａがＢレジスタ５１０に、０次の項の係数α１
がＣレジスタ５１１に、また２次の項の係数′１′がＡ
レジスタ５０９にセットされる。なお、誤りが１つの場
合はＡレジスタ５０９に０、Ｂレジスタ５１０に１、Ｃ
レジスタ５１１にα８をセットする。

（３）誤り位置多項式の根の導出 算術演算部１０８で求められた誤り位置多項式の係数に
、、に、、に、は第１図チェン探索部１０９に送られる
。第７図はチェン探索部１．０９の詳細図である。チェ
ン探索部はレジスタ７０１〜７０３、固定係数乗算器７
０４，７０５、加算回路７０６゜論理和７０７．ダウン
カウンタ７０８、及びレジスタ７０９．固定係数乗算器
７１０．レジスタＡＤＲ，７１１，レジスタＡＤＲ２７
１２で構成される。

（２）で求められた誤り位置多項式の係数に２゜Ｋ１．
に、は、第５図Ａレジスタ５０９−Ｃレジスタ５１１か
らレジスタ７０１〜７０３にラッチされる。それと同時
に第１図プログラムカウンタ］−３１がホールドされ、
誤りの位置を格納するＡ、ＤＲ１レジスタ７１１．ＡＤ
Ｒ，レジスタ７１２がクリアされると共にチェン探索が
開始される。

第７図の７０４，７０５はそれぞれレジスタ７０１のα
２器、レジスタ７０２のα器である。

まず初めに、レジスタ７０１，７０２，７０３に記憶さ
れた信号、］−２α０．α５は加算回路７０６に入力す
るとともに１はα２器７０４に、α器はα器７０５に入
力する。加算回路７０６では入力を各成分ごとに排他的
論理和演算する。これが、誤り位置多項式 ％式％ のＸ−α０とした時、 σ（α０）＝（α０）２＋αａ（α０）十α１・＝１＋
α０＋α１゛ に相当する。σ（α器）はσ（α器）の各ビット成分の
論理和７０７によりＯベクトルであるかどうかを検出さ
れ、０ベクトルであれば出力信号ＥＲは（Ｌ　Ｑ　ＩＩ
、そうでなければｔＬ　１　＋＋となる。

■探索終了後、レジスタ７０１の内容はα２器７０４の
出力α２　　レジスタ７０２の内容はα器７０５の出力
α８α　となり、加算回路７０７の出力は誤り位置多項
式のＸ＝αとした時、σ（α器）＝α２＋α８α＋α５ に相当する。以下、これらの過程を繰り返し行って誤り
位置多項式にα　からα１４を代入した値を求め、それ
がＯバク１ヘルであれば論理和７０７の出力ＥＲはｔｒ
　Ｏ”となる。

一方、レジスタ７０９及びα器７１０は現在探索してい
る元の位置を求めるためのもであり、レジスタ７０９は
チェン探索開始時に’　１　’　（＝α０）にセットさ
れる。レジスタ７０９の内容はα器により１探索ごとに
α、α２．α３．・・と変化し、その時の誤り位置多項
式の値がＯベクトルであれば、ダウンカウンタ７０８の
制御によりＡＤＲｌ　レジスタ７１１、またはＡＤＲ２
レジスタ７１２にレジスタ７０９の内容をセラ１〜する
。

誤り位置多項式が２次の場合、最終的にＡＤＲ１レジス
タ７１１に誤り位置Ｐ２ＡＤＲ２レジスタ７１２に誤り
位置Ｐ３．　　（αの次数がＰｌ〈Ｐ２）が格納され、
１次の場合はＡＤＲニレジスタフ１１に誤り位置Ｐよが
格納される。

（４）各誤りの誤りの大きさの算出 チェン探索によって求められた誤りの位置Ｐ工。

Ｐ２は、第１図のＳ□　レジスタ１０６、Ｓ３　レジス
タ１０７にセラ１−される。誤りの大きさを求める演算
は（２）の誤り位置多項式の係数を求める演算と同様に
、プログラムＲＯＭ１３０の制御により第１図算術演算
部」０８で並列に行われる。従来技術の項で述べた誤り
の大きさ算出手順が予め記憶されているプログラムＲＯ
Ｍ１３０は、第５図マルチプレクサ５０１、制御回路５
０５〜５０７に制御信号を供給する。各部分はその命令
にしたがって動作し、最終的にＡレジスタ５０９とＢレ
ジスタ５１０に誤りの大きさをセットする。ここで、Ａ
レジスタ５０９にセットされる誤りの大きさは、第７図
ＡＤＲ１レジスタ７１１に格納されている誤りの位置に
対応し、Ｂレジスタ５１０はＡＤＲ２レジスタ７１２に
対応する。

（５）入力ディジタルデータの訂正 第８図は第１図訂正部１１０の詳細図である。

訂正部はＲＡＭ８０１．ＲＯＭ８０２．マルチプレクサ
８０３，８０４．コンパレータ８０５．ラッチ８０６．
カウンタ８０７，８０８．加算回路８０９から構成され
、誤りの位置Ｐ□、Ｐ２と誤りの大きさに１．に２から
入力データを訂正し、訂正後のデータＮＤを出力する回
路である。ＲＡＭ８０１はデータの位置を示すダウンカ
ウンタ８０７からアドレス信号を入力し、予め書き込ま
れた訂正前のデータＰＤを出力する。なお、ダウンカウ
ンタ８０７は初期状態で符号長にセットされている。マ
ルチプレクサ８０３，８０４はそれぞれ次回訂正する誤
りの誤りの位置と誤りの大きさを出力し、カウンタ８０
８はその制御信号を供給する。

初期状態では、カウンタ８０８はｔｔ　ｉ　Ｉ＋にセッ
トされ、マルチプレクサ８０３，８０４からはそれぞれ
Ｐ２．　Ｋ２が出力されている。マルチプレクサ８０３
の出力はＲＯＭ８０２のアドレスとして入力し、ＲＯＭ
８０２はベクトルとして記憶されている誤りの位置をα
の指数部に変換する。

訂正開始と共にＲＡＭ８０１はカウンタ８０７からアド
レス信号を入船し、格納しているデータを出力する。コ
ンパレータ８０５はカウンタ８０７の出力とＲＯＭ８０
２の出力が一致しているか、すなわちデータが誤りであ
るかどうかを調べ、加算回路８０９に制御信号を供給す
る。加算回路８０９ではその制御信号によりデータが誤
りであるかどうかを判断し、誤りであればマルチプレク
サ８０４の出力、すなわち誤りの大きさとデータの排他
的論理和をとり訂正する。

また、コンパレータの出力はラッチ８０６にも供給され
、次のクロックでラッチ８０６の出力がカウンタ８０８
のクロックとして入力する。カウンタ８０８の内容は２
となり、マルチプレクサ８０３．８０４からはＰｌ、に
１が出力される。以下、同様な処理を行いＲＡＭ８０１
からすべてのデータが出力されることにより訂正が完了
する。

〔発明の効果〕

第９図は４誤り訂正能力を持つＲ８符号の誤り検出及び
訂正装置における、算術演算部の並列数と各誤り個数に
おける演算ステップ数の関数を示したものである。図中
の係数は前記従来技術の（２）誤り位置多項式の係数算
出、大きさは（４）誤りの大きさ算出である。図を見れ
ば分かるように、並列数を増せば増すほど演算ステップ
数は少なくなるが、ハードウェア規模の点を考慮すると
最も効率の良い並列数は５（訂正能力ｔ＝４とした時の
ｔ＋１）、または８（２ｔ）であることが分かる。

【図面の簡単な説明】

第１図は本発明の誤り検出及び訂正装置を、本実施例の
（１５，１１）Ｒ８符号の復号に適用した場合のブロッ
ク図、第２図は第１図シンドローム生成部１０２、第３
図は第２図α３乗算器２１１、第４図は第１図Ｏ検出器
１０３、第５図は第１図算術演算部１０８、第６図は第
５図乗算器５０２、第７図は第１図チェン探索部１０９
、第８図は第１図訂正部１１０をより詳しく記述したブ
ロック図、第９図は従来の誤り検出及び訂正装置と本発
明による誤り検出及び訂正装置の、誤り位置多項式の係
数及び各誤りの大きさ算出に要するステン第 霞 ■ 回

Claims (1)

【特許請求の範囲】
1. １、リードソロモン符号により符号化したディジタル信
   号及び誤り検査符号からなるディジタルデータを一時的
   に記憶するメモリと、該メモリに記憶された該ディジタ
   ルデータに対して所定の有限体上の演算を施すことによ
   り、該ディジタルデータの誤りを検出し、ｔ個の誤りを
   訂正する手段を有する誤り検出及び訂正装置において、
   誤り位置多項式の係数及び各誤りの大きさを、（ｔ＋１
   ）個、または２ｔ個の乗算器及び加算器により並列に演
   算することを特徴とするリードソロモン符号の誤り検出
   及び訂正装置。