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

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はリードソロモン符号の誤り検出及び訂正装置に
関する。詳しくはディジタルビデオテープレコーダー（
ＤＶＴＲ）　、ディジタルオーディオテープレコーダー
（Ｄ　Ａ　Ｔ）等において、信頼性向上のために所定の
方法で生成されたパリティ信号を付加されたリードソロ
モン符号からなるディジタル信号を再生する場合に、付
加したパリティ信号をもとに所定の方法で誤りを検出し
１元の正しい信号に訂正する誤り検出及び訂正装置に係
り、特に誤り位置を特定するチェン探索法を用いたリー
ドソロモン符号の誤り検出及び訂正装置に関する。

〔従来の技術〕

従来、リードソロモン符号の誤り検出及び訂正方法につ
いては、電子通信学会論文誌、第Ｊ６４−Ａ巻、第２号
（１９８１年２月）第１３７頁乃至第１４４頁において
論じられている。該リードソロモン符号の誤り検出及び
訂正方法は、（１）シンドロームの計算及び誤りの検出
（２）誤りシンボル数の判定及び誤り位置多項式の係数
算出 （３）誤り位置多項式の根の導出 （４）誤りの大きさ算出 （５）訂正の実行 の手順で行われる。ここでは、データである１１シンボ
ル（１シンボル８ビツト）に対して、生成多項式 ％式％（１） により生成したパリティ４シンボルを付加したリードソ
ロモン符号である、（１５，１１）リードソロモン符号
の復号を例にとり、復号動作を説明する。なお、以下の
説明の中の演算はすべて有限体ＧＦ　（２”）上で行わ
れる。

（１）シンドロームの計算及び誤りの検出符号長１５の
符号語Ｃ＝（０１４１０１３＋”’＋ｃｏ）を記録して
これを再生したとき、再生系列Ｒ＝（ｒ１４？ｒｉ３１
・・・ｔ　ｒｏ）が再生されたとする。ここで、再生系
列Ｒに含まれる誤り系列すなわち再生系列Ｒと符号語Ｃ
の差をＥ＝　（ｅ工４１ｅｉ３１＋ｅｏ）とするとき、
Ｒは次のように表現される。

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

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

（２）誤りシンボル数の判定、及び誤り位置多項式パリ
ティを４シンボル持つ（１５，１１）リードソロモン符
号は２個以下の誤りを訂正できるが、誤りが２個かそれ
より多いかを判定することはできない。そこで、まず訂
正能力最大の２個の誤りが位Ｍｌ−＋　ｊにそれぞれＥ
ｉ、Ｅｊの大きさで発生したと仮定すると、式（２）か
ら次式が得られる。

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

式（４）；　（５）よりα２Ｉ　　α２１の項を消去す
ると８２＋（α１＋αＪ　）　Ｘ　Ｓ□＝α１α’（Ｅ
ｉ＋Ｅｊ）である。したがって ５２＝ａａＳ□＋α’ｓｏ　　”　　　　　”’（ｓ）
の関係がある。また、式（４）〜（６）よりＳ、＝ａ”
Ｓ、＋ａ’Ｓ、　　　　　　　　　−（９）の関係があ
る。式（８）、　（９）を行列表現で表すととなるから である。したがって α’＝（、Ｓ、Ｓ、＋Ｓ、、、Ｓ３）／Δα’＝（ｓｓ
＋５ｘｓｚ）／Δ Δ＝ｓ１”十ｓ、ｓ。

である。ここで、誤りが位置ｉ、大きさＥｉの１つであ
った場合は Δ＝（α笈Ｅｉ）”＋Ｅｉα”Ｅｉ＝０となることから
、Δを誤りシンボル数の判定式として用いることができ
る。Δ＝０のときは誤りが１つの場合であり、その誤り
位置多項式６式％（１０） の定数項α２は、σ（Ｘ）＝○がα１を解に持つことか
ら、式（３）、　（４）より、 α８＝α１＝Ｓ工／Ｓ０ と簡単に求めることができる。

（３）誤り位置多項式の根の導出 誤り位置多項式の根を求める方法としては、主に以下に
述べる２つの方法がある 第１の方法は誤り位置多項式を順次計算できるようない
くつかの多項式に変形し、それぞれの多項式の根を予め
求めて記憶したＲＯＭを参照することにより解く方法で
ある。

誤りが１個の場合は式（１０）より明らかに、誤り位置
多項式の根はα８である。誤りが２個の場合の誤り位置
多項式は。

Ｘ２＋ａａＸ＋ａ’＝Ｏ−（１１） であり、α８＝Ｏの時は２乗根となる。

これより、Ｘ□＝　Ｘ、＝（ｃｚ’）”　”（７）関係
かア’Ｊ、アドレスに対してその１７２乗令出力するＲ
ＯＭを予め用意しておけば、それを参照することにより
根を求めることができる。

さて、α０≠０　の時、式（１１）の解をＲＯＭにより
求めようとするならば、α３．α５の２信号を入力する
必要が生じる。ＲＯＭのアドレスを１６ビツトにすれば
、単純にＲＯＭを参照することも可能であるが、その場
合５１２にビット（＝　２１６ワートＸ８ビツト）のＲ
ＯＭが必要となり、回路規模等の点で非常に無駄が多い
。

そこで。

Ｘ＝αａＹとおくことにより、式（１１）を。

Ｙ２＋Ｙ＋αｂ／α１＝０　　　　　　・・・（１２）
と変形する。式（１２）は定数項のみに外部から入力を
必要とする項を持ち、定数項に対する式（１２）の根Ｙ
工、Ｙ２をＲＯＭに格納しておけば。

４にビット（＝２Ｉ′ワード×８ビット）のＲＯＭによ
り効率良く解くことができる。

このように、式（１１）を式（１２）に変形することで
小容量のＲＯＭにより誤り位置多項式の根を求めること
ができる。同様に３訂正以上の場合もこの観点から解く
ことができる。詳しくは前述の公知例に述べられている
。

第２の方法は本発明のもとになる従来技術で、誤り位置
多項式に全ての元を代入し、それが０となる元を根とす
るもので、これは一般にチェノ（Ｃｈｉｅｎ）探索法と
呼ばれる。例えば誤りが２個の場合を考えると、全ての
元に対するσ（Ｘ）すなわち σ（α０）＝（α０）２＋α１α０＋α５σ（α１）＝
（α１）２＋α２α１＋α５ｃｙ　（α１４）＝（ａ”
）”＋　ａ”ｔｘ１４＋　ａ’を求めそれが０となる元
を根とする方法である。

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

Ｋ２（ｉ）＝α２に２（ｉ−１） Ｋ工（ｉ）＝αによ（ｉ−１） Ｋ、（ｉ）＝に、（ｉ−１） σ（α’）＝　Ｋｚ（ｘ　）　＋　Ｋ１（１）　＋　Ｋ
Ｏ（１）（４）誤りの大きさ算出 有限体ＧＦ（２’）上のリードソロモン符号は１シンボ
ルが８ビツトから構成されるため、誤りを訂正するため
には誤りの位置だけでなく、誤りの大きさも求めること
が必要である。式（３）〜（６）を見れば明がなように
、誤りの大きさは誤りの位置とシンドロームから求める
ことができる。式（３）　、　（４）を行列表現を用い
て表すと、 となる。したがって、 以下余白 となる。１誤りの場合は式（３）から明らかに、Ｅｉ＝
Ｓ、である。

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

〔発明が解決しようとする課題〕

上記従来技術の「（３）誤り位置多項式の根の導出」に
おいて、第１の方法であるＲＯＭを参照して多項式を解
く方法は、前述のように１，２訂正のときは小容量のＲ
ＯＭで実現することができた。

しかし、３訂正、４訂正になると、前述の方法により工
夫を凝らしても、ＲＯＭのアドレスはそれぞれ１６ビツ
ト、２４ビツトとなり、ハード化の実現が容易でないと
いう問題があった。

一方、第２の方法であるチェン探索法は、σ（α０）か
らσ（α１）、σ（α１）からσ（α２）、・・・・・
σ（αト２）からσ（αト１）を求める（Ｎは整数で符
号長）、という具合に誤り位置多項式σ（Ｘ）に全ての
元を１個ずつ代入することにより誤り位置を求めている
。すなわち符号長範囲内のすべての位置を代入するため
、訂正する誤りの個数にかかわらず符号長に応じた処理
時間を要し処理に時間がかかる。このためＤＶＴＲのよ
うな高速信号処理の要求される装置においては適用が困
難であるという問題があった。

本発明の目的は、前記第２の方法であるチェン探索法を
改良することにより誤り位置多項式の根の探索時間の短
縮を図ったリードソロモン符号の誤り検出及び訂正装置
を提供することにある。

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

上記目的は、 リードソロモン符号により符号化したディジタル信号及
び誤り検査符号からなるディジタルデータを一時的に記
憶するメモリと、該メモリに記憶された該ディジタルデ
ータに対して所定の有限体上の演算を施すことにより、
該ディジタルデータの誤りを検出し、訂正する手段を有
するリードソロモン符号の誤り検出及び訂正装置におい
て、並列チェン探索により誤り位置多項式の根を求める
ことを特徴とするリードソロモン符号の誤り検出及び訂
正装置とすることにより達成される。

ここで上記の並列チェン探索は、チェン探索を並列して
行なうものを言う。

並列チェン探索の１つの手法は まずσ（αｏ）、σ（α）、・・・・・　σ（α’−’
）（ｐは２以上の整数）を求める。

σ（α０）、σ（α）、・・・・・・　σ（αｐ−１）
からσ（α）、σ（αＦ＋１）、・・・・・・　σ（α
ｚｐ−ｔ）を求めるという具合に全ての元を代入するま
で、複数個の元を並列に代入することにより誤り位置を
求めるものである。

例えば、ｐ＝２、すなわち２並列にした場合は、従来の
直列チェン探索と同様に初期値をに２＝１．に１＝α　
１ＫＯ＝αゝ と与えると、以下のようになる。

σ（αＯ）：　Ｋ２＋　Ｋ１＋　Ｋ。

σ（α”）”　Ｋｚα２＋に□α＋に０に、＝に２α　
、に工＝に１α　、　Ｋ０＝に０σ（α２）＝に２＋に
工＋に０ σ（α３）　”　Ｋ　２α２＋に工α＋に０に２＝に２
α’、に１＝に１α２．　Ｋ、＝に０以上の繰り返し計
算で求めることができる。

並列チェン探索の他の手法として、１つの符号語を複数
個のブロックに分割し、各ブロックについて従来技術の
ごとく誤り位置多項式σ（Ｘ）に元を代入してチェン探
索を行なうこともできる。

〔作用〕

本発明によれば、チェン探索を並列に行なうため、符号
長の数より少ないステップ数ですべての元を探索するこ
とが可能である。上記並列チェン探索の上記１つの手法
においては、 σ（α１）とσ（αＺ＋ｍ＋１）　（ただしｍは負でな
い整数）が同時に求められる並列処理であることから、
すべての元に対するσ（Ｘ）を求めるステップ数を大幅
に短縮できる。例えば上記のＰ＝２の例の場合には、従
来の直列チェン探索のステップ数の約１／２に短縮でき
る。

従ってリードソロモン符号の誤り検出および訂正の処理
に要する時間が大幅に短縮され、ディジタルＶＴＲのよ
うな高速信号処理の要求される装置において適用が可能
になる。

〔実施例〕

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

（１）シンドロームの計算及び誤りの検出第１図におい
て、１０１は情報部Ｄ工。〜Ｄ。

およびパリティ部Ｐ、〜Ｐ０からなる（１５゜１１）リ
ードソロモン符号を一時的に記憶するメモリである。メ
モリ１０１に記憶されたディジタルデータはＤｌ。から
順次読み出され、シンドローム生成部１０２に送られる
。シンドローム生成部１０２ではメモリ１０１から読み
出されたディジタルデータＰＤから、（１５，１１）リ
ードソロモン符号の誤りを検出、訂正する際に必要とな
る４つのシンドロームＳＩ、〜Ｓ、を生成する。第２図
は第１図のシンドローム生成部１０２を示す図である。

図のようにＳ８０　レジスタ２０１．ＳＳ、Ｌ／ジスタ
２ｏ２．ＳＳ２　レジスタ２０３．ＳＳ３　レジスタ２
０４．加算回路２０５〜２０８．α１．α２．α３乗算
器２０９〜２１１により構成されている。ここでは−例
として、シンドロームＳ、を求める手順について説明す
る。

（ａ）まず、ＳＳ、　　レジスタ２０１．ＳＳ１　レジ
スタ２０２．ＳＳ２　レジスタ２０３．ＳＳ。

レジスタ２０４がすべてクリアされて０の状態となる。

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

Ｕ、、　Ｕ、、　Ｕｏ）、出力を０＝（ｖ７．■６．■
、。

Ｖ、、Ｖ、、Ｖ、、Ｖｌ、Ｖ、）とすると。

０：（Ｕ、、　Ｕ、、　Ｕ、、　Ｕ４．　Ｕ、、　Ｕ、
、　Ｕ工、Ｕｏ）Ｘ（０，Ｏ，Ｏ，０，１，Ｏ，Ｏ，０
）＝（Ｕ７α７＋Ｕ６α６＋Ｕ、α５＋Ｕ４α４＋Ｕ、
α１＋Ｕ２α２＋Ｕ１α１＋Ｕ、）Ｘα３ ＝（Ｕ７α１０　＋ｕ＆α９＋Ｕ５α１＋Ｕ４α７＋Ｕ
３α６＋Ｕ２α５＋Ｕ１α’＋ｕ、α３） である。有限体ＧＦ（２＠）の原始多項式は。

Ｘ’＋Ｘ’＋Ｘ’＋Ｘ”＋１＝０ であるから、 α８＝α９＋α３＋α２＋１ α９＝α５＋α４＋α３＋α α１０＝α６＋α５＋α４＋α２ ある。したがって。

０＝Ｕ、＋（α６＋α５＋α４＋α”）＋ｕｉ（α５＋
α４＋α１＋α）十Ｕ、（α１＋α３＋α２＋１）十、
ｔｒ４α７＋Ｕ、α６＋Ｕ２α５＋Ｕ工α’＋Ｕ、α３ ＝Ｕ、α’＋（Ｕ、＋Ｕ、）α’＋（Ｕ７＋Ｕ、＋Ｕ、
）αゝ＋（Ｕ、＋Ｕ、＋Ｕ、＋Ｕ１）α’　＋　（ＵＧ
十Ｕ、　＋　Ｕｎ　）α３＋（Ｕ、＋Ｕｓ）α２＋Ｕ、
　（！＋Ｕ。

より、 Ｖ、＝Ｕ、　　　　　　　　　　Ｖ、＝Ｕ０＋Ｕ、＋Ｕ
。

Ｖｓ＝　Ｕ、　十Ｕ７Ｖ、　＝　Ｕｓ＋　Ｕ。

Ｖ　ｓ　＝　Ｕ　２　＋Ｕ　ｓ　＋　Ｕ　ｖ　　　　　
Ｖ　１＝　Ｕ　ａＶ、　：　Ｕ１＋　Ｕ、　＋　Ｕ、　
＋　Ｕ７Ｖ、　＝　ｕ。

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

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

ＯＸα’＋Ｄ、。＝Ｄ、、−＋ＳＳ。

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

Ｄ工。Ｘα”＋Ｄ、→ＳＳ。

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

（”’（（Ｄｘｏ　×α’＋Ｄ、）Ｘα’＋Ｄ＝）・・
＋Ｐ、）Ｘｃｃ’＋Ｐｏ→ＳＳ。

すなわち、 Ｄ工。刈α３）１４＋Ｄ、Ｘ（α３）１３＋・・・＋ｐ
１ｘα３＋Ｐ０→ＳＳ３これは、情報部Ｄ□。〜Ｄ。　
およびパリティ部ｐ、−ｐｏからなる（１５．１１）リ
ードソロモン符号のシンドロームＳ、である。

他のシンドロームＳ０．Ｓ□＋Ｓｚも同様に。

それぞれに対応する演算回路において、メモリ１０１か
ら読み出されるデータＤ工。、・・・Ｐｏ　から生成さ
れ、それぞれＳＳｏ　レジスタ２０１、ＳＳエ　レジス
タ２０２．ＳＳ２　レジスタ２０３にセットされる。

このようにして求められたシンドロームＳ、−Ｓ、は、
５ｓｏ−ｓｓ、レジスタ２０１〜２０４より第１図Ｏ検
出器１０３及びシンドロームレジスタ１０４〜１０７に
供給される。

０検出器１０３はシンドローム８０〜Ｓ、が全てＯであ
るかどうかを検出する。すなわち、入力データの誤りの
有無を検出する回路である。第４図は０検出器１０３を
示す図である。

論理和４０１〜４０４にはシンドロームＳ。

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

（２）誤り位置多項式の係数算出 誤り位置多項式の係数を求める演算は、プログラムＲＯ
Ｍ１３０の制御により、データセレクタ１０８、算術演
算部１０９、及びＡレジスタ１１０〜Ｄレジスタ１１３
間で行われる。

算術演算部１０９は、従来技術の項で記述した、誤り位
置多項式の係数を算出するために必要な演算を行う部分
であり、そのブロック図は第５図に示される６第５図に
おいて、５０１は有限体ＧＦ（２’）上の加算器、５０
２は乗算器であり、それぞれ人力Ｕ、−Ｖの和、積を出
力する。ここで、有限体ＧＦ（２’）上の乗算ＵＸＶは
、Ｕ＝（Ｕ、、　ＵＧ、　Ｕ、、　Ｕ４．　Ｕ□ｌ　Ｕ
２１　Ｕｌ。

Ｕ、）、　Ｖ＝（Ｖ、、　Ｖ、、　Ｖ、、　Ｖ、、　Ｖ
、、　Ｖ２゜Ｖｌ、Ｖ、）とすると、 Ｕ　Ｘ　Ｖ　＝Ｕ　Ｘ　Ｖ　。Ｘ　ｔｘ　’＋ＵＸＶ工
Ｘα１ ＋　Ｕ　Ｘ　Ｖ、Ｘα７ と表すことができるから、第５図の乗算器５０２は第６
図のように構成できる。６０１〜６０８は固定係数乗算
器、６４個の６０９は２人力論理積ゲート、６１０〜６
１７はパリティジェネレータ回路である。前述のように
、固定係数乗算器は排他的論理和ゲートから、パリティ
ジェネレータもまた排他的論理和ゲートにより構成され
るので、有限体ＧＦ（２”）上の乗算器５０２は、２人
力論理積ゲートと排他的論理和ゲートにより構成できる
。また、第５図５０３は入力の逆先を出力するＲＯＭ、
５０４はデータセレクタ、５０５はレジスタセレクタで
ある。

従来技術の項で述べた誤り位置多項式の係数算出手順が
予め記憶されているプログラムＲＯＭ１３０は、データ
セレクタ５０４．レジスタセレクタ５０５及び第１図デ
ータセレクタ１０８に制御信号を供給する。各部分はそ
の命令にしたがって動作し、最終的にＢレジスタ１１１
とＣレジスタ１１２に係数をセットする。ここで、次に
誤り位置多項式の根を導出する都合上、誤りが２つの場
合はＡレジスタ１１０に１、Ｂレジスタ１１１にα１．
Ｃレジスタ１１２にα５をセットし、１つの場合はＡレ
ジスタ１１０に０、ＢＬ／ジスタ１１１に１、Ｃレジス
タ１１２にα１をセットする。

（３）誤り位置多項式の根の導出 算術演算部１０９で求められた誤り位置多項式の係数に
、、　Ｋ□＋Ｋｏ　はチェン探索部１１４に送られる。

第７図は探索を４並列にした場合の第１図のチェン探索
部１１４の詳細図である。

チェン探索部はレジスタ７０１〜７０３、固定係数乗算
器７Ｑ４〜７１１．０検出器７１２〜７１５、マルチプ
レクサ７１６，７１７、レジスタ７１８、固定係数乗算
器７１９〜７２２、マルチプレクサ７２３，７２４、レ
ジスタセレクタ７２５、レジスタＡＤＲ，７２６、ＡＤ
Ｒエフ２７及びコントロール信号発生回路７２８で構成
される。

以下、並列チェン探索の回路動作を簡単に説明する。

（２）で求められた誤り位置多項式の係数に２゜Ｋ工、
に０は、第１図Ａレジスタ１１０〜Ｃレジスタ１１２か
らレジスタ７０１〜７０３にラッチされ、プログラムカ
ウンタ１３１がホールドされると共に並列チェン探索が
開始される。第７図の７０４〜７０７はそれぞれレジス
タＡのα２器、α４器、α６器、α８器、７０８〜７１
１はレジスタＢのα１器、α２器、α３器。

α４器である。それぞれの乗算器は第３図に示したα３
器と同様に、排他的論理和グー８１０〜２０個程度で構
成できる。レジスタ７０１に記憶された値をα０．レジ
スタ７０２に記憶された値をα３とすると、各固定係数
乗算器の出力信号はそれぞれＡ工＝α”、Ａ２＝＝α９
．Ａ３＝α’ｐＡ４”α　、Ｂ工＝α１α、Ｂ２＝α１
α２Ｂ、＝ａ”ａ３．Ｂ４＝ａ”ａ’となる。

各乗算器の出力は第７図７１２〜７１５のＯ検出器、及
び７１６，７１７のマルチプレクサに供給される。０検
出器７１２〜７１５は誤りを探索する回路であり、マル
チプレクサ７１６゜７１７は並列探索後新たにレジスタ
７０１゜７０２に信号をセットする回路である。第８図
は上記の０検出器７１２の詳細図である。レジスタ７０
１，７０２，７０３に記憶された信号をそれぞれα２．
α５．α０とすると、入力端子にはそれぞれα１．α１
．α０が入力し、加算回路８０１により各成分ごとの排
他的論理和が出力される。これが、誤り位置多項式 ％式％ のＸ＝α　とした時、 σ（α０）＝α簀α０）２＋α″−（α０）＋α０＝α
８＋α５＋α０ に相当する、このσ（α０）がＯベクトルであれば、位
置α０すなわちＰ。が誤りであると言える。σ（αＧ）
はσ（α０）の各ビット成分の論理和８０２により０ベ
クトルであるかどうかを検出され、０ペクトであれば出
力信号ＥＲ０は１１０”、そうでなければ“１″となる
。同様に、○検出器７１３の入力端子にはα２α　、α
５α。

α０が入力し、 ａ　（α１）＝　ｃｒ”（α’）２＋　α’（α１）＋
　ａ’が０ベクトルであれば出力信号ＥＲ１は′０″そ
うでなければ１”となる。信号ＥＲ２ＥＲ，も同様にし
てＯ検出器７１４，７１５から出力される。

また、課題を解決する手段の項で述べたごとく、並列チ
ェン接索の他の手法として１つの符号語を複数個のブロ
ックに分割し、各ブロックごとに対応する元を１つずつ
代入する手法にすることは、言うまでもなく可能である
。

誤り位置多項式σ（Ｘ）は解を２つ持つことから、信号
ＥＲ１，，・・・ＥＲ３は最大２個まで“Ｏ”になる可
能がある。したがって、この結果をＲＯＭによりレジス
タＡＤＲ，７２６、ＡＤＲ１７２７に取り込もうとした
ならば、ＲＯＭのアドレスには出力ＥＲｏ、・・・ＥＲ
３の他に、過去に検出された根の情報としてレジスタＡ
ＤＨ１Ｉ７２６　、　ＡＤＨエフ２７の内容が必要とさ
れる。

上記のようにチェン探索を並列に行うと、根が同時に複
数個求まることがあるため、根をレジスタに格納するた
めのハードウェアはそのすべての可能性に合わせて構成
する必要がある。

例えば単純にＲＯＭで構成するならば、並列に計算した
各σ（Ｘ）がＯであるかどうかの情報の他に、どこのレ
ジスタに格納するか、すなわち根を格納するレジスタの
現在の状態の情報がアドレスとして必要となる。したが
って、誤り訂正能力の高い符号を復号する場合には根を
格納するレジスタが多くなり、符号長が長い等の理由で
多並列にした場合はσ（Ｘ）が多くなるので。

それぞれ大容量のＲＯＭが必要となる。

そこで、回路規模を抑えるために、１回の探索ではαの
指数部の小さい方から１つのみを根とする。例えば２並
列探索の場合においては、σ（α２）とσ（α３）がと
もに０であった場合にはα２のみを根とする。そして、 Ｋ２＝に、α２．に工＝に□α、　Ｋ、＝Ｋ。

とすることにより、σ（α３）が次回再び計算されるよ
うに制御する。Ｋ、、に工を制御する回路、及びその制
御信号を供給する回路は、大容量のＲＯＭに較べるとは
るかに小さな規模で構成することができる。

本実施例の２訂正、４並列チェン探索の場合では、根を
レジスタＡＤＲ，７２６、ＡＤＲエフ２７にセットする
ＲＯＭは、アドレスがＥＲ，〜ＥＲ，。

ＡＤＲｏ７２６．＾ＤＲ，７２７の６ビツト、出力がＡ
ＤＲ，７２６。

ＡＤＲエフ２７の２ビツトの２′×２　　ビットの小容
量のもので構成することができる。しかし、誤り訂正能
力の高い符号を訂正する場合や、符号長が長いために多
並列にした場合、例えば４訂正。

８並列探索とした場合には２１″×４ビツトの大容量の
ＲＯＭが必要となる。そこで、本発明では１探索で検出
する誤りを最大１個とする。αの指数部の小さい方から
１つのみを検出することで、ＲＯＭを用いずに小さなハ
ードウェア規模で並列チェン探索を構成する構成を次に
示す。

第７図はこのように構成した場合の回路図である。コン
トロール信号発生回路７２８はＥＲｏ、・・・、ＥＲｌ
から、検出する誤りの位置を示す２ビツトの信号ＣＴＬ
、、誤りの有無を示す１ビツトの信号ＣＴＬ、を発生す
る回路であり、出力信号ＣＴＬ、はマルチプレクサ７１
６゜７１７及びマルチプレクサ７２３，７２４に、ＣＴ
Ｌ工はレジスタセレクタ７２５に供給される。マルチプ
レクサ７１６，７１７は制御信号ＣＴＬ、に応じて新た
にレジスタ７０１，７０２に信号をセットする６例えば
、位置α１が誤りである（ＥＲ工＝“Ｏ”）、すなわち
σ（α１）二〇であると検出されたとする。ＣＴＬ、は
“０１”となってマルチプレクサ７１６　、７１７に入
力し、レジスタ７０１，７０２にはそれぞれα　、α１
α２がセットされ、次の探索は位置α２〜αゝが行われ
る。また、位置α３が誤りである（ＥＲ，＝“Ｏ′″）
と検出された場合、または位置α０〜α３には誤りがな
いと判断した場合には、レジスタ７０１，７０２にはそ
れぞれα６．α１α４がセットされ次の探索はα４〜α
７が行われる。

一方、レジスタ７１８．固定係数乗算器７１９〜７２２
．マルチプレクサ７２３，７２４．レジスタセレクタ７
２５では、コントロール信号発生回路の出力ＣＴＬ、、
ＣＴＬ工による制御をともなって、レジスタ＾ＤＲＩ、
７２６　、　ＡＤＲエフ２７に誤り位置のセットを行う
、第９図はレジスタセレクタ７２５の詳細図を示したも
のである。第９図に示すようにレジスタセレクタ７２５
はダウンカウンタ９０１、フリップフロップ９０２゜９
０３から構成されており、制御信号としてコントロール
信号発生回路７２８からＣＴＬ工、プログラムＲＯＭ１
３０から誤りの個数Ｎを入力する。

レジスタ７１８はレジスタ７０１〜７０３に誤り位置多
項式の係数に２．に１．に、がセットされるのと同時に
１（＝α０）にセットされる。各乗算器７１９〜７２２
はレジスタ７１８の出力信号ＳＡ、にα１〜α４を乗じ
た信号ＳＡ工〜ＳＡ４を出力し、ＳＡ、〜ＳＡ、がマル
チプレクサ７２４へ、ＳＡ工〜ＳＡ４がマルチプレクサ
７２３へ供給される。マルチプレクサ７２３は１探索終
了後にレジスタ７１８にセットする信号を出力し、マル
チプレクサ７２４は誤り位置を出力する。例えば、２誤
りでＣＴＬ、信号が“ｏｌ”、すなわち位置α１が誤り
であったならば、マルチプレクサ７２４はレジスタセレ
クタ７２５を介してＡＤＲ工にα１　をセットする。

また、マルチプレクサ７２３はα２をレジスタ７１８に
セットし、次の探索時にはマルチプレクサ７２４の入力
端子はα２〜α５が入力される。

ここで、ＣＴＬ、が“１１”、すなわち位置α３が誤り
であるか誤りが存在しない場合、マルチプレクサ７２４
はともにα　を出力するが、この場合にはレジスタセレ
クタ７１７のコントロール信号ＣＴＬ□により、α　を
レジスタＡＤＨ，７２６にセットするかしないかの制御
を行う。

（４）各誤りの誤りの大きさの算出 並列チェン探索によって求められた誤りの位置Ｐ、、Ｐ
□は、第１図のシンドロームレジスタ５２１０６．Ｓ、
１０７にセットされる。誤りの大きさを求める演算は（
２）の誤り位置多項式の係数を求める演算と同様に、プ
ログラムＲＯＭ１３０の制御により、ブータレフタ１ｏ
８．算術演算部１０９、及びＡレジスタ１１０−Ｄレジ
スタ１１３間で行われる。従来技術の項で述べた誤りの
大きさ算出手順が予め記憶されているプログラムＲＯＭ
１３０は、データセレクタ５０４．レジスタセレクタ５
０５及び第１図データセレクタ１０８に制御信号を供給
する。各部分はその命令にしたがって動作し、最終的に
Ａレジスタ１１０とＢレジスタ１１１に係数をセットす
る。

ここで、Ａレジスタ１１０にセットされる誤りの大きさ
は、レジスタＡＤＨ，７２６に格納されている誤りの位
置に対応し、Ｂレジスタ１１１はＡＤＲＬ７２７に対応
する。

（５）入力ディジタルデータの訂正 第１０図は第１図の訂正部１１５の詳細図である。訂正
部はＲＡＭ１００Ｉ　、　ＲＯＭ１００２　、マルチプ
レクサ１Ｏ０３，１００４，：ｌンパレータ１００５　
。

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

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

また、コンパレータの出力はラッチ１００６にも供給さ
れ、次のクロックでラッチ１００６の出力がカウンタ１
００８のクロックとして入力する。カウンタ１ｏ０８の
内容は２となり。

マルチプレクサ１００３．１００４からはＰ工。

Ｋ１が出力される。以下、同様な処理を行いＲＡＭＩＱ
ＯＬからすべてのデータが出力されることにより訂正が
完了する。

〔発明の効果〕

本発明で述べた並列チェン探索を行うことにより、すべ
ての位置を調べるのに必要な探索回数は、従来の直列チ
ェン探索の符号長目に対して高々。

［符号長／ｍｍ列数数回（［Ｘ］：Ｘ以上の最大整数）
になる。例えば、実施例で用いた符号長１５の符号で比
較すると、従来の直列チェン探索は１５クロツク要する
のに対して、実施例の４並列チェン探索は４クロツクで
すべての元を探索することができる。この探索回数の低
減は符号長が長くなるほどより顕在化する。

しかし、符号長が長いために多並列にした場合や、訂正
能力の高い符号の復号を行う場合には、探索結果をレジ
スタに取り込む為に必要なハードウェア量は指数的に多
くなる。それに対して本発明によれば、１度の並列探索
で決定する根を最大１個とする制御回路を設けることで
、探索回数は誤りの個数回はど多くなるが、ハードウェ
ア量の増加はごくわずかに抑えることができる。

【図面の簡単な説明】

第１図は本発明の実施例による、（１，５，１１）リー
ドソロモン符号の復号を行なう誤り検品及び訂正装置の
ブロック図、第２図は第１図のシンドローム生成部１０
２を示す図、第３図は第２図のα３乗算器２１１を示す
図、第４図は第１図のＯ検出器１０３を示す図、第５図
は第１図の算術演算部１０９を示す図、第６図は第５図
の乗算器５０２を示す図、第７図は第１図のチェン探索
部１１４の詳細図、第８図は第７図の０検出器７０６の
詳細図、第９図は第７図のレジスタセレクタ７２５の詳
細図、第１０図は第１図の訂正部１１５■ 目 築 図 ■ η ｌθ 口

Claims (1)

1. 【特許請求の範囲】 １、リードソロモン符号により符号化したディジタル信
   号及び誤り検査符号からなるディジタルデータを一時的
   に記憶するメモリと、該メモリに記憶された該ディジタ
   ルデータに対して所定の有限体上の演算を施すことによ
   り、該ディジタルデータの誤りを検出し、訂正する手段
   を有するリードソロモン符号の誤り検出及び訂正装置に
   おいて、 並列チェン探索により誤り位置多項式の根を求めること
   を特徴とするリードソロモン符号の誤り検出及び訂正装
   置。 ２、上記並列チェン探索において、一回の探索で検出す
   る根の数を最大１個とし、複数個の根が存在する場合に
   は、次の探索は検出した根の次の元から該並列チェン探
   索を行うことを特徴とする特許請求の範囲第１項記載の
   リードソロモン符号の誤り検出及び訂正装置。