JPH10322226A - リードソロモン復号方法 - Google Patents
リードソロモン復号方法Info
- Publication number
- JPH10322226A JPH10322226A JP9124411A JP12441197A JPH10322226A JP H10322226 A JPH10322226 A JP H10322226A JP 9124411 A JP9124411 A JP 9124411A JP 12441197 A JP12441197 A JP 12441197A JP H10322226 A JPH10322226 A JP H10322226A
- Authority
- JP
- Japan
- Prior art keywords
- decoding
- erasure
- reed
- correction
- error
- 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.)
- Pending
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/158—Finite field arithmetic processing
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/1515—Reed-Solomon codes
Landscapes
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
(57)【要約】
【課題】 誤訂正を効果的に防止できるリードソロモン
復号方法を提供する。 【解決手段】 ２ｔ（正の整数）シンボルのパリティデ
ータを持つ、リードソロモン符号化系列に対して、誤り
のシンボルの位置を示す消失位置を用いて誤り訂正を行
い、復号するリードソロモン復号方法であって、前記消
失位置から誤りのシンボルの数ｎを求め（Ｓ１３）、０
≦ｍ1 ≦ｎ≦ｍ2 ≦２ｔ（ｍ1 、ｍ2 およびｎは正の整
数）である場合に（Ｓ１４，Ｓ１５，Ｓ１８）、ｎシン
ボルの消失エラー訂正の復号演算を行って誤り値を求め
（Ｓ１９）、前記誤り値および前記消失位置を用いて、
訂正操作を行う（Ｓ１７）。
復号方法を提供する。 【解決手段】 ２ｔ（正の整数）シンボルのパリティデ
ータを持つ、リードソロモン符号化系列に対して、誤り
のシンボルの位置を示す消失位置を用いて誤り訂正を行
い、復号するリードソロモン復号方法であって、前記消
失位置から誤りのシンボルの数ｎを求め（Ｓ１３）、０
≦ｍ1 ≦ｎ≦ｍ2 ≦２ｔ（ｍ1 、ｍ2 およびｎは正の整
数）である場合に（Ｓ１４，Ｓ１５，Ｓ１８）、ｎシン
ボルの消失エラー訂正の復号演算を行って誤り値を求め
（Ｓ１９）、前記誤り値および前記消失位置を用いて、
訂正操作を行う（Ｓ１７）。
Description
【０００１】
【発明の属する技術分野】本発明は、記録媒体やディジ
タル伝送の誤り訂正符号化として用いられるリードソロ
モン符号化された信号を復号するリードソロモン復号方
法に関する。
タル伝送の誤り訂正符号化として用いられるリードソロ
モン符号化された信号を復号するリードソロモン復号方
法に関する。
【０００２】
【従来の技術および発明が解決しようとする課題】リー
ド・ソロモン符号（以下ＲＳ符号）は、その符号化効率
の良さとバーストエラーに対する適正から、主に記録媒
体やディジタル伝送の外符号に用いられている。例えば
コンパクトディスクで採用されているエラー訂正符号
は、ＣＩＲＣ訂正符号（クロスインターリーブ・リード
・ソロモン符号）と称され、インターリーブの技法と組
み合わせた積符号である。その外符号としてＲＳ（２
８、２４）符号が、内符号としてＲＳ（３２、２８）符
号が採用されていて、それぞれＣ２符号及びＣ１符号と
呼ばれる。いずれの符号とも、ひとつのＲＳ符号化シン
ボルは１バイトで構成され、ひとつのＲＳ符号化ブロッ
クは４バイトのパリティ検査列を含んでいる。
ド・ソロモン符号（以下ＲＳ符号）は、その符号化効率
の良さとバーストエラーに対する適正から、主に記録媒
体やディジタル伝送の外符号に用いられている。例えば
コンパクトディスクで採用されているエラー訂正符号
は、ＣＩＲＣ訂正符号（クロスインターリーブ・リード
・ソロモン符号）と称され、インターリーブの技法と組
み合わせた積符号である。その外符号としてＲＳ（２
８、２４）符号が、内符号としてＲＳ（３２、２８）符
号が採用されていて、それぞれＣ２符号及びＣ１符号と
呼ばれる。いずれの符号とも、ひとつのＲＳ符号化シン
ボルは１バイトで構成され、ひとつのＲＳ符号化ブロッ
クは４バイトのパリティ検査列を含んでいる。
【０００３】一般に、ＲＳ符号は２ｔシンボルの検査列
でｔシンボルの訂正が可能である。ｔシンボルの訂正に
はｔ個の誤り位置とそのそれぞれの誤りに対応したｔ個
の誤りの値を知る必要がある。ＲＳ符号はｔ個の誤りの
発生に対し、復号側でシンドローム演算をすることで２
ｔ個の線形独立な方程式を得る。この方程式を解くこと
で２ｔ個の未知数である、前記ｔ個の誤り位置とそのそ
れぞれの誤り位置に対応した前記ｔ個の誤りの値を求め
ることができる。
でｔシンボルの訂正が可能である。ｔシンボルの訂正に
はｔ個の誤り位置とそのそれぞれの誤りに対応したｔ個
の誤りの値を知る必要がある。ＲＳ符号はｔ個の誤りの
発生に対し、復号側でシンドローム演算をすることで２
ｔ個の線形独立な方程式を得る。この方程式を解くこと
で２ｔ個の未知数である、前記ｔ個の誤り位置とそのそ
れぞれの誤り位置に対応した前記ｔ個の誤りの値を求め
ることができる。
【０００４】一方、ＣＩＲＣ符号のように積符号の構成
を取っているものは、内符号に対する内側ＲＳ復号にお
いて訂正できなかったＲＳ符号化ブロックや誤訂正の可
能性の比較的高いＲＳ符号化ブロックに消失フラグを付
加することで、外符号に対応した外側ＲＳ復号において
消失エラー訂正が可能になる。消失フラグが付加された
内符号の消失シンボルはデ・インターリーブによって複
数の外側のＲＳ符号化ブロックに分散される。消失エラ
ー訂正では、前記消失シンボルに誤りが存在すると仮定
してシンドローム演算から得られる連立方程式を解く。
誤り位置を既知として解くので最大２ｔ個の誤りを値を
求めることができる。即ち、２ｔシンボルの検査列を持
つＲＳ符号に対しては、消失エラー訂正を実行すること
で最大２ｔシンボルの誤り訂正が可能である。
を取っているものは、内符号に対する内側ＲＳ復号にお
いて訂正できなかったＲＳ符号化ブロックや誤訂正の可
能性の比較的高いＲＳ符号化ブロックに消失フラグを付
加することで、外符号に対応した外側ＲＳ復号において
消失エラー訂正が可能になる。消失フラグが付加された
内符号の消失シンボルはデ・インターリーブによって複
数の外側のＲＳ符号化ブロックに分散される。消失エラ
ー訂正では、前記消失シンボルに誤りが存在すると仮定
してシンドローム演算から得られる連立方程式を解く。
誤り位置を既知として解くので最大２ｔ個の誤りを値を
求めることができる。即ち、２ｔシンボルの検査列を持
つＲＳ符号に対しては、消失エラー訂正を実行すること
で最大２ｔシンボルの誤り訂正が可能である。
【０００５】ＣＩＲＣ符号を例に挙げて、消失エラー訂
正の手法を説明する。ＣＩＲＣ符号の場合、内符号であ
るＣ１符号のＲＳ復号（Ｃ１復号）において消失フラグ
を付加することで、外符号であるＣ２符号のＲＳ復号
（Ｃ２復号）で消失エラー訂正が可能である。Ｃ１符
号、Ｃ２符号ともにｔ＝２であるから、Ｃ１復号は最大
２バイトの訂正が、Ｃ２復号の消失エラー訂正では最大
４バイトの訂正がそれぞれ可能である。そのＣ２復号に
おけるシンドロームｓ0 〜ｓ3 と、誤り値ｅ1 〜ｅ4 が
次のようにして求められる。ＣＩＲＣ符号の符号生成多
項式Ｇｅ（ｘ）は、下記式（１）で示される。
正の手法を説明する。ＣＩＲＣ符号の場合、内符号であ
るＣ１符号のＲＳ復号（Ｃ１復号）において消失フラグ
を付加することで、外符号であるＣ２符号のＲＳ復号
（Ｃ２復号）で消失エラー訂正が可能である。Ｃ１符
号、Ｃ２符号ともにｔ＝２であるから、Ｃ１復号は最大
２バイトの訂正が、Ｃ２復号の消失エラー訂正では最大
４バイトの訂正がそれぞれ可能である。そのＣ２復号に
おけるシンドロームｓ0 〜ｓ3 と、誤り値ｅ1 〜ｅ4 が
次のようにして求められる。ＣＩＲＣ符号の符号生成多
項式Ｇｅ（ｘ）は、下記式（１）で示される。
【０００６】
【数１】
【０００７】ここでαはガロア体の原始元である。この
とき、受信系列からシンドローム演算により得たｓ0 〜
ｓ3 は、前記ｘ1 〜ｘ4 およびｅ1 〜ｅ4 との間に下記
式（２）で示される関係がある。
とき、受信系列からシンドローム演算により得たｓ0 〜
ｓ3 は、前記ｘ1 〜ｘ4 およびｅ1 〜ｅ4 との間に下記
式（２）で示される関係がある。
【０００８】
【数２】
【０００９】ここで記号‘・’はガロア体上の乗算を示
し、記号‘＋’はガロア体上の加算を示す。以下、ある
ガロア体の元同士の四則演算は、そのガロア体上での演
算を示すこととする。前記式（２）を連立方程式を解い
て、未知数である誤り値ｅ1 〜ｅ4 を求めると次のよう
になるまず、ｅ4 は、下記式（３）として得られる。
し、記号‘＋’はガロア体上の加算を示す。以下、ある
ガロア体の元同士の四則演算は、そのガロア体上での演
算を示すこととする。前記式（２）を連立方程式を解い
て、未知数である誤り値ｅ1 〜ｅ4 を求めると次のよう
になるまず、ｅ4 は、下記式（３）として得られる。
【００１０】
【数３】
【００１１】この得られたｅ4 を前記式（２）に代入し
て３つの等式から成る連立方程式を再構成する。即ち、
ＣＩＲＣ符号で用いられているガロア体は加算と減算が
同じであることに注意して下記式（４）のように修正す
ることで、前記式（２）の連立方程式は下記式（５）に
変形される。
て３つの等式から成る連立方程式を再構成する。即ち、
ＣＩＲＣ符号で用いられているガロア体は加算と減算が
同じであることに注意して下記式（４）のように修正す
ることで、前記式（２）の連立方程式は下記式（５）に
変形される。
【００１２】
【数４】
【００１３】
【数５】
【００１４】これは、連立方程式の解を、手計算で順に
求めるときによく用いられる手法である。次に、式
（５）の連立方程式を解いてｅ3 を求めると、下記式
（６）のようになる。
求めるときによく用いられる手法である。次に、式
（５）の連立方程式を解いてｅ3 を求めると、下記式
（６）のようになる。
【００１５】
【数６】
【００１６】同様にして修正を施すことで、前記式
（５）の連立方程式は下記式（７），（８）のように変
形される。
（５）の連立方程式は下記式（７），（８）のように変
形される。
【００１７】
【数７】
【００１８】
【数８】
【００１９】さらに、式（８）の連立方程式を解いてｅ
2 を求めると、下記式（９）となる。
2 を求めると、下記式（９）となる。
【００２０】
【数９】
【００２１】次に、この求めたｅ2 を前記式（８）に代
入して下記式（１０）を得る。
入して下記式（１０）を得る。
【００２２】
【数１０】
【００２３】このようにして、誤り値ｅ1 〜ｅ4 を順次
求めることができる。上述した手法において、情報とし
て元来もっているものと、実際の復号の際に行われる演
算操作とを区別するために、記号‘＝’と‘←’とを使
い分けている。つまり、実際の復号演算に対応するの
は、式（３）、（４）、（６）、（７）、（９）および
（１０）であり、少なくとも、ガロア体上の加算が２３
回、乗算が１７回、除算が３回必要である。一方、消去
エラー訂正を行わない場合には、Ｃ２復号で最大２バイ
トまで訂正（２重エラー訂正）ができる。このときは、
シンドロームｓ0 〜ｓ3 から、誤り値ｅ1 ，ｅ2 と誤り
位置ｘ’1 ，ｘ’2 を求める。以上は、４重消去エラー
訂正、すなわち、消去位置の数が４の場合の復号演算処
理過程である。
求めることができる。上述した手法において、情報とし
て元来もっているものと、実際の復号の際に行われる演
算操作とを区別するために、記号‘＝’と‘←’とを使
い分けている。つまり、実際の復号演算に対応するの
は、式（３）、（４）、（６）、（７）、（９）および
（１０）であり、少なくとも、ガロア体上の加算が２３
回、乗算が１７回、除算が３回必要である。一方、消去
エラー訂正を行わない場合には、Ｃ２復号で最大２バイ
トまで訂正（２重エラー訂正）ができる。このときは、
シンドロームｓ0 〜ｓ3 から、誤り値ｅ1 ，ｅ2 と誤り
位置ｘ’1 ，ｘ’2 を求める。以上は、４重消去エラー
訂正、すなわち、消去位置の数が４の場合の復号演算処
理過程である。
【００２４】従来手法による消失エラー訂正処理のフロ
ーチャートを図２に示す。図２に示すように、受信系列
からシンドロームｓ0 〜ｓ3 を計算し（ステップＳ
１）、その消失フラグから消失位置ｘ1 〜ｘ4 を得る
（ステップＳ２）。そして、消失フラグの数をカウント
し、このカウント値をｎとする（ステップＳ３）。
ーチャートを図２に示す。図２に示すように、受信系列
からシンドロームｓ0 〜ｓ3 を計算し（ステップＳ
１）、その消失フラグから消失位置ｘ1 〜ｘ4 を得る
（ステップＳ２）。そして、消失フラグの数をカウント
し、このカウント値をｎとする（ステップＳ３）。
【００２５】次に、ｎ＝４（２ｔ）の場合には（ステッ
プＳ４）、前記式（３），（４），（６），（７），
（９）および（１０）のアルゴリズムにより、４重消去
エラー訂正の復号演算を実行して、誤り値ｅ1 〜ｅ4 を
求める（ステップＳ５）。そして、誤り値ｅ1 〜ｅ4 と
消去位置ｘ1 〜ｘ4 とを用いて訂正操作を行う（ステッ
プＳ６）。
プＳ４）、前記式（３），（４），（６），（７），
（９）および（１０）のアルゴリズムにより、４重消去
エラー訂正の復号演算を実行して、誤り値ｅ1 〜ｅ4 を
求める（ステップＳ５）。そして、誤り値ｅ1 〜ｅ4 と
消去位置ｘ1 〜ｘ4 とを用いて訂正操作を行う（ステッ
プＳ６）。
【００２６】また、ｎ＝３（ｔ＜ｎ＜２ｔ）の場合には
（ステップＳ７）、前記式（６），（７），（９）およ
び（１０）のアルゴリズムにより、３重消去エラー訂正
の復号演算を実行して、誤り値ｅ1 〜ｅ3 を求める（ス
テップＳ８）。そして、誤り値ｅ1 〜ｅ3 と消去位置ｘ
1 〜ｘ3 とを用いて訂正操作を行う（ステップＳ６）。
（ステップＳ７）、前記式（６），（７），（９）およ
び（１０）のアルゴリズムにより、３重消去エラー訂正
の復号演算を実行して、誤り値ｅ1 〜ｅ3 を求める（ス
テップＳ８）。そして、誤り値ｅ1 〜ｅ3 と消去位置ｘ
1 〜ｘ3 とを用いて訂正操作を行う（ステップＳ６）。
【００２７】一方、ｎ≦２（ｔ）の場合には、これに対
応した所定の誤り訂正を実行する（ステップＳ９，Ｓ
６）。
応した所定の誤り訂正を実行する（ステップＳ９，Ｓ
６）。
【００２８】上述したように、４重消失エラー訂正では
シンドロームｓ0 〜ｓ3 の全てを使用しているが、従来
の３重消失エラー訂正ではｓ0 〜ｓ2 の３つしか使用し
ていない。また、ｎ≦２（＝ｔ）の場合の訂正方法が明
確化されていない。さらには、従来の手法では、誤った
訂正が生じた場合の対策が十分に施されていないという
問題がある。
シンドロームｓ0 〜ｓ3 の全てを使用しているが、従来
の３重消失エラー訂正ではｓ0 〜ｓ2 の３つしか使用し
ていない。また、ｎ≦２（＝ｔ）の場合の訂正方法が明
確化されていない。さらには、従来の手法では、誤った
訂正が生じた場合の対策が十分に施されていないという
問題がある。
【００２９】以下、上述した消失エラー訂正処理を行う
リードソロモン復号装置の一般的な構成について説明す
る。図３は、従来のリードソロモン復号装置１の構成図
である。図３に示すように、リードソロモン復号装置１
は、メモリブロック２、バスＩ／Ｆブロック３および復
号演算処理部４を備えている。メモリブロック２は、ス
クラッチパッドメモリ５，６およびスイッチ７，８を備
えている。スイッチ７は、入力データを選択的にスクラ
ッチパッドメモリ５，６に出力する。スイッチ８は、ス
クラッチパッドメモリ５の記憶内容を選択的に訂正操作
実行器１２に出力する。
リードソロモン復号装置の一般的な構成について説明す
る。図３は、従来のリードソロモン復号装置１の構成図
である。図３に示すように、リードソロモン復号装置１
は、メモリブロック２、バスＩ／Ｆブロック３および復
号演算処理部４を備えている。メモリブロック２は、ス
クラッチパッドメモリ５，６およびスイッチ７，８を備
えている。スイッチ７は、入力データを選択的にスクラ
ッチパッドメモリ５，６に出力する。スイッチ８は、ス
クラッチパッドメモリ５の記憶内容を選択的に訂正操作
実行器１２に出力する。
【００３０】バスＩ／Ｆブロック３は、入力パラメータ
演算器９、レジスタＢOUT １０、バイナリカウンタ１
１、訂正操作実行器１２およびレジスタＢIN１３を備え
ている。復号演算処理部４は、スイッチ１４、レジスタ
ＧIN１５、レジスタＧOUT １６および復号演算器１７を
備えている。図４は、リードソロモン復号装置１の動作
時におけるデータおよび構成要素の時系列的な状態を示
し、（Ａ）は入力データ、（Ｂ）は出力データ、（Ｃ）
はレジスタＢOUT １０の記憶状態、（Ｄ）はレジスタＢ
IN１３の記憶状態、（Ｅ）はレジスタＧOUT １６の記憶
状態、（Ｆ）はレジスタＧIN１５の記憶状態、（Ｇ）は
復号演算器１７の処理状態をそれぞれ示している。
演算器９、レジスタＢOUT １０、バイナリカウンタ１
１、訂正操作実行器１２およびレジスタＢIN１３を備え
ている。復号演算処理部４は、スイッチ１４、レジスタ
ＧIN１５、レジスタＧOUT １６および復号演算器１７を
備えている。図４は、リードソロモン復号装置１の動作
時におけるデータおよび構成要素の時系列的な状態を示
し、（Ａ）は入力データ、（Ｂ）は出力データ、（Ｃ）
はレジスタＢOUT １０の記憶状態、（Ｄ）はレジスタＢ
IN１３の記憶状態、（Ｅ）はレジスタＧOUT １６の記憶
状態、（Ｆ）はレジスタＧIN１５の記憶状態、（Ｇ）は
復号演算器１７の処理状態をそれぞれ示している。
【００３１】図４に示すように、メモリブロック２のス
クラッチパッドメモリ５においてＣ１符号に関する入力
データの入出力を行っているときには、バスＩ／Ｆブロ
ック３はＣ１符号に関する入力データ対して、入力パラ
メータ演算器９において復号演算入力パラメータの計算
を行い、訂正操作実行器１２において訂正操作を行って
いる。また、このとき、復号演算処理部４ではＣ２符号
に関する入力データについてＣ２復号処理が行われてい
る。
クラッチパッドメモリ５においてＣ１符号に関する入力
データの入出力を行っているときには、バスＩ／Ｆブロ
ック３はＣ１符号に関する入力データ対して、入力パラ
メータ演算器９において復号演算入力パラメータの計算
を行い、訂正操作実行器１２において訂正操作を行って
いる。また、このとき、復号演算処理部４ではＣ２符号
に関する入力データについてＣ２復号処理が行われてい
る。
【００３２】また、スクラッチパッドメモリ６において
Ｃ２符号に関する入力データの入出力を行っているとき
には、バスＩ／Ｆブロック３はＣ２符号に関する入力デ
ータ対して、入力パラメータ演算器９において復号演算
入力パラメータの計算を行い、訂正操作実行器１２にお
いて訂正操作を行っている。また、このとき、復号演算
処理部４ではＣ１符号に関する入力データについてＣ１
復号処理が行われている。
Ｃ２符号に関する入力データの入出力を行っているとき
には、バスＩ／Ｆブロック３はＣ２符号に関する入力デ
ータ対して、入力パラメータ演算器９において復号演算
入力パラメータの計算を行い、訂正操作実行器１２にお
いて訂正操作を行っている。また、このとき、復号演算
処理部４ではＣ１符号に関する入力データについてＣ１
復号処理が行われている。
【００３３】ここで、復号演算入力パラメータとは、具
体的には、シンドローム（Ｓ）および消失位置（Ｉ）で
ある。シンドローム（Ｓ）は、図３に示す入力パラメー
タ演算器９およびレジスタＢ OUT １０の組み合わせによ
って演算される。図５は、入力パラメータ演算器９およ
びレジスタＢOUT １０の構成図である。図５に示すよう
に、入力パラメータ演算器９は、乗算器２４〜２７、加
算器２０〜２３、消去フラグ検出器２８および分配器２
９を備えている。また、レジスタＢOUT １０は、レジス
タ３０〜３３およびレジスタ３４〜３７を備えている。
体的には、シンドローム（Ｓ）および消失位置（Ｉ）で
ある。シンドローム（Ｓ）は、図３に示す入力パラメー
タ演算器９およびレジスタＢ OUT １０の組み合わせによ
って演算される。図５は、入力パラメータ演算器９およ
びレジスタＢOUT １０の構成図である。図５に示すよう
に、入力パラメータ演算器９は、乗算器２４〜２７、加
算器２０〜２３、消去フラグ検出器２８および分配器２
９を備えている。また、レジスタＢOUT １０は、レジス
タ３０〜３３およびレジスタ３４〜３７を備えている。
【００３４】乗算器２４〜２７は、乗算係数が固定値の
ガロア体の乗算器であり、それぞれ×α0 、×α1 、×
α2 、×α3 の乗算を行う。消去フラグ検出器２８は、
入力データに含まれる消去フラグが「１」であるか否か
を検出する。分配器２９は、入力データに含まれる各Ｒ
Ｓシンボル位置と対応して動作するバイナリカウンタ１
１の出力をレジスタＢOUT １０のレジスタ３４〜３７の
いずれかに出力して記憶させる。このレジスタ３４〜３
７の記憶結果が消失位置（Ｉ）を示す。
ガロア体の乗算器であり、それぞれ×α0 、×α1 、×
α2 、×α3 の乗算を行う。消去フラグ検出器２８は、
入力データに含まれる消去フラグが「１」であるか否か
を検出する。分配器２９は、入力データに含まれる各Ｒ
Ｓシンボル位置と対応して動作するバイナリカウンタ１
１の出力をレジスタＢOUT １０のレジスタ３４〜３７の
いずれかに出力して記憶させる。このレジスタ３４〜３
７の記憶結果が消失位置（Ｉ）を示す。
【００３５】消失位置（Ｉ）は、図３に示す復号演算器
１７において、後述するコンバータにより、ガロア体の
表現に、すなわち「ｉ」から「αi 」に変換される。具
体的には、Ｉ＝｛ｉ1 ，ｉ2 ，ｉ3 ，ｉ4 ｝が、Ｘ＝
｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝に変換される。
１７において、後述するコンバータにより、ガロア体の
表現に、すなわち「ｉ」から「αi 」に変換される。具
体的には、Ｉ＝｛ｉ1 ，ｉ2 ，ｉ3 ，ｉ4 ｝が、Ｘ＝
｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝に変換される。
【００３６】４重消失エラー訂正を実行する場合の前記
式（３），（４），（６），（７）および（１０）に対
応する復号演算は、復号演算処理部４において実行さ
れ、レジスタＢOUT １０からの復号演算入力パラメータ
Ｓ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3｝と、Ｉ＝｛ｉ1 ，
ｉ2 ，ｉ3 ，ｉ4 ｝を変換して得られたＸ＝｛ｘ1 ，ｘ
2 ，ｘ3 ，ｘ4 ｝とを用いて、復号演算出力パラメータ
Ｅ＝｛ｅ1 ，ｅ2 ，ｅ3 ，ｅ 4 ｝およびＸ’＝Ｘ＝｛ｘ
1 ，ｘ2 ，ｘ3 ，ｘ4 ｝を得る。消失エラー訂正を行わ
ない場合には、前述した２重エラー訂正においては、復
号演算入力パラメータＳ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3 ｝
を用いて、復号演算出力パラメータＥ＝｛ｅ1，ｅ2 ｝
およびＸ’＝｛ｘ’1 ，ｘ’2 ｝を得る。
式（３），（４），（６），（７）および（１０）に対
応する復号演算は、復号演算処理部４において実行さ
れ、レジスタＢOUT １０からの復号演算入力パラメータ
Ｓ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3｝と、Ｉ＝｛ｉ1 ，
ｉ2 ，ｉ3 ，ｉ4 ｝を変換して得られたＸ＝｛ｘ1 ，ｘ
2 ，ｘ3 ，ｘ4 ｝とを用いて、復号演算出力パラメータ
Ｅ＝｛ｅ1 ，ｅ2 ，ｅ3 ，ｅ 4 ｝およびＸ’＝Ｘ＝｛ｘ
1 ，ｘ2 ，ｘ3 ，ｘ4 ｝を得る。消失エラー訂正を行わ
ない場合には、前述した２重エラー訂正においては、復
号演算入力パラメータＳ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3 ｝
を用いて、復号演算出力パラメータＥ＝｛ｅ1，ｅ2 ｝
およびＸ’＝｛ｘ’1 ，ｘ’2 ｝を得る。
【００３７】誤り位置ＸあるいはＸ’は、復号演算処理
部４において、後述するコンバータで、指数値に、すな
わちαi からｉに変換される。具体的には、Ｘ’＝Ｘ＝
｛ｘ 1 ，ｘ2 ，ｘ3 ，ｘ4 ｝がＩ＝｛ｉ1 ，ｉ2 ，
ｉ3 ，ｉ4 ｝に変換され、Ｘ’＝｛ｘ’1 ，ｘ’2 ｝が
Ｉ’＝｛ｉ’1 ，ｉ’2 ｝に変換される。
部４において、後述するコンバータで、指数値に、すな
わちαi からｉに変換される。具体的には、Ｘ’＝Ｘ＝
｛ｘ 1 ，ｘ2 ，ｘ3 ，ｘ4 ｝がＩ＝｛ｉ1 ，ｉ2 ，
ｉ3 ，ｉ4 ｝に変換され、Ｘ’＝｛ｘ’1 ，ｘ’2 ｝が
Ｉ’＝｛ｉ’1 ，ｉ’2 ｝に変換される。
【００３８】図６は、訂正操作実行器１２およびレジス
タＢIN１３の構成図である。図６に示すように、訂正操
作実行器１２は、比較器４０、加算器４５およびゲート
ロジック４６を備えている。また、レジスタＢIN１３
は、レジスタ４１〜４４およびレジスタ４７〜５０を備
えている。
タＢIN１３の構成図である。図６に示すように、訂正操
作実行器１２は、比較器４０、加算器４５およびゲート
ロジック４６を備えている。また、レジスタＢIN１３
は、レジスタ４１〜４４およびレジスタ４７〜５０を備
えている。
【００３９】バスＩ／Ｆブロック３は、レジスタＧOUT
１６から入力した誤り値（Ｅ）と誤り位置（Ｉ’）とを
用いて、訂正操作を実行する。バイナリカウンタ１１
は、スイッチ７，８によるスクラッチパッドメモリ５，
６からの出力の切り換わりに対応して動作し、バイナリ
カウンタ１１のバイナリカウンタ値が誤り位置（Ｉ’）
の構成要素のいずれか（ｉ’n ）と一致したときに、ゲ
ートロジック４６から対応する誤り値ｅn が加算器４５
に出力される。そして、加算器４５において、誤り値ｅ
n と、スイッチ８からのメモリブロックのデータ出力と
について、ガロア体の加算が行われ、加算結果が出力デ
ータとなる。
１６から入力した誤り値（Ｅ）と誤り位置（Ｉ’）とを
用いて、訂正操作を実行する。バイナリカウンタ１１
は、スイッチ７，８によるスクラッチパッドメモリ５，
６からの出力の切り換わりに対応して動作し、バイナリ
カウンタ１１のバイナリカウンタ値が誤り位置（Ｉ’）
の構成要素のいずれか（ｉ’n ）と一致したときに、ゲ
ートロジック４６から対応する誤り値ｅn が加算器４５
に出力される。そして、加算器４５において、誤り値ｅ
n と、スイッチ８からのメモリブロックのデータ出力と
について、ガロア体の加算が行われ、加算結果が出力デ
ータとなる。
【００４０】次に、復号演算処理部４について説明す
る。図７は、復号演算処理部４の構成図である。図７に
示すように、復号演算処理部４は、マイクロコードＲＯ
Ｍ５０、シーケンサ５１、デスティネイションコントロ
ーラ５２、ワーキングレジスタ５３、ＧＬＵ(Global Lo
gic Unit) ５４、ポート選択器５５を備えている。
る。図７は、復号演算処理部４の構成図である。図７に
示すように、復号演算処理部４は、マイクロコードＲＯ
Ｍ５０、シーケンサ５１、デスティネイションコントロ
ーラ５２、ワーキングレジスタ５３、ＧＬＵ(Global Lo
gic Unit) ５４、ポート選択器５５を備えている。
【００４１】ＣＩＲＣ符号のようにｔが４より小さく、
連立方程式から解が直接的に求められる場合で、かつ、
処理スピードが比較的遅くても良いときには、復号演算
処理部４としては、ＲＩＳＣ(Reduced Instruction Set
Computer)型のものが用いられる。復号演算処理部４で
は、各演算は逐次的に行われ、演算セットは、ＧＬＵ５
４として時分割共有化される。また、一連の演算処理
は、マイクロコード化されて、インストラクションコー
ドとしてマイクロコードＲＯＭ５０に格納され、シーケ
ンサ５１からのＲＯＭアドレスによって、処理順序（メ
モリからの読み出し順序）が制御される。
連立方程式から解が直接的に求められる場合で、かつ、
処理スピードが比較的遅くても良いときには、復号演算
処理部４としては、ＲＩＳＣ(Reduced Instruction Set
Computer)型のものが用いられる。復号演算処理部４で
は、各演算は逐次的に行われ、演算セットは、ＧＬＵ５
４として時分割共有化される。また、一連の演算処理
は、マイクロコード化されて、インストラクションコー
ドとしてマイクロコードＲＯＭ５０に格納され、シーケ
ンサ５１からのＲＯＭアドレスによって、処理順序（メ
モリからの読み出し順序）が制御される。
【００４２】また、途中の演算結果は、予め用意された
複数のワーキングレジスタ５３に一時的に記憶される
が、どのワーキングレジスタ５３に記憶するかもインス
トラクションコード内のデスティネイションコントロー
ルコードに記述されている。この手法によれば、処理ス
ピードの制限はあるものの、ＧＬＵ５４の時分割共有化
による装置の縮小化ができると共に、演算処理のマイク
ロコード化により設計の自由度を高めることができる。
例えば、２つのガロア体の元同士の加算は、各ビットの
排他的論理和に相当し、復号演算処理部４では１ステッ
プで実現できる。すなわち、ＧＬＵ５４は、ビット毎の
排他的論理和の機能を含んでいる。但し、ガロア体にお
ける乗算は、加算に比べてはるかに複雑であり、これを
ＲＯＭを用いて実現しようとすると、２バイトのアドレ
ス入力に対して１バイトの出力を得ることになり、非常
に規模が大きくなってしまう。
複数のワーキングレジスタ５３に一時的に記憶される
が、どのワーキングレジスタ５３に記憶するかもインス
トラクションコード内のデスティネイションコントロー
ルコードに記述されている。この手法によれば、処理ス
ピードの制限はあるものの、ＧＬＵ５４の時分割共有化
による装置の縮小化ができると共に、演算処理のマイク
ロコード化により設計の自由度を高めることができる。
例えば、２つのガロア体の元同士の加算は、各ビットの
排他的論理和に相当し、復号演算処理部４では１ステッ
プで実現できる。すなわち、ＧＬＵ５４は、ビット毎の
排他的論理和の機能を含んでいる。但し、ガロア体にお
ける乗算は、加算に比べてはるかに複雑であり、これを
ＲＯＭを用いて実現しようとすると、２バイトのアドレ
ス入力に対して１バイトの出力を得ることになり、非常
に規模が大きくなってしまう。
【００４３】ＧＬＵ５４の構成について説明する。図８
は、ＧＬＵ５４の構成図である。図８に示すように、Ｇ
ＬＵ５４は、オペレイションロジック６０，６１、コン
バータ６２，６３およびオペレイションセレクタ６４を
備えている。ＧＬＵ５４では、２つの入力データａ，ｂ
のガロア体の元のそれぞれを、コンバータ６２におい
て、対応する原始元の指数の値に変換、すなわちαi を
ｉに変換し、指数同士の加算を実行する。そして、その
得られた加算結果を、コンバータ６３において、対応す
るガロア体の元に変換、すなわち、ｉをαi に変換す
る。
は、ＧＬＵ５４の構成図である。図８に示すように、Ｇ
ＬＵ５４は、オペレイションロジック６０，６１、コン
バータ６２，６３およびオペレイションセレクタ６４を
備えている。ＧＬＵ５４では、２つの入力データａ，ｂ
のガロア体の元のそれぞれを、コンバータ６２におい
て、対応する原始元の指数の値に変換、すなわちαi を
ｉに変換し、指数同士の加算を実行する。そして、その
得られた加算結果を、コンバータ６３において、対応す
るガロア体の元に変換、すなわち、ｉをαi に変換す
る。
【００４４】例えば、αv とαw の乗算を実行して、α
V+W を得るには、ＧＬＵ５４において、下記式（１１）
に示す４つの演算処理が必要で、少なくとも４ステップ
を要する。
V+W を得るには、ＧＬＵ５４において、下記式（１１）
に示す４つの演算処理が必要で、少なくとも４ステップ
を要する。
【００４５】
【数１１】
【００４６】除算も同様で、乗算における加算の代わり
に減算を実行する。従って、上述した手法では、誤り値
ｅ1 〜ｅ4 を求めるには、上記式（３），（４），
（６），（７），（９）および（１０）における乗算・
除算が２０回あるので、これだけでも８０ステップ以上
必要となる。これに、２３回の加算を含めると、合計１
０３ステップ以上必要となる。
に減算を実行する。従って、上述した手法では、誤り値
ｅ1 〜ｅ4 を求めるには、上記式（３），（４），
（６），（７），（９）および（１０）における乗算・
除算が２０回あるので、これだけでも８０ステップ以上
必要となる。これに、２３回の加算を含めると、合計１
０３ステップ以上必要となる。
【００４７】本発明は、上述した従来技術に鑑みてなさ
れ、誤訂正を効果的に防止できるリードソロモン復号方
法を提供することを目的とする。また、本発明は、ｎシ
ンボルのデータ語について、ｎ≦２（＝ｔ）の場合の訂
正方法を明確化したリードソロモン復号方法を提供する
ことを目的とする。
れ、誤訂正を効果的に防止できるリードソロモン復号方
法を提供することを目的とする。また、本発明は、ｎシ
ンボルのデータ語について、ｎ≦２（＝ｔ）の場合の訂
正方法を明確化したリードソロモン復号方法を提供する
ことを目的とする。
【００４８】
【課題を解決するための手段】上述した従来技術の問題
点を解決し、上述した目的を達成するために、本発明の
リードソロモン復号方法は、２ｔ（正の整数）シンボル
のパリティデータを持つ、リードソロモン符号化系列に
対して、誤りのシンボルの位置を示す消失位置を用いて
誤り訂正を行い、復号するリードソロモン復号方法であ
って、前記消失位置から誤りのシンボルの数ｎを求め、
０≦ｍ1 ≦ｎ≦ｍ2 ≦２ｔ（ｍ1 、ｍ2およびｎは正の
整数）である場合に、ｎシンボルの消失エラー訂正の復
号演算を行って誤り値を求め、前記誤り値および前記消
失位置を用いて、訂正操作を行う。
点を解決し、上述した目的を達成するために、本発明の
リードソロモン復号方法は、２ｔ（正の整数）シンボル
のパリティデータを持つ、リードソロモン符号化系列に
対して、誤りのシンボルの位置を示す消失位置を用いて
誤り訂正を行い、復号するリードソロモン復号方法であ
って、前記消失位置から誤りのシンボルの数ｎを求め、
０≦ｍ1 ≦ｎ≦ｍ2 ≦２ｔ（ｍ1 、ｍ2およびｎは正の
整数）である場合に、ｎシンボルの消失エラー訂正の復
号演算を行って誤り値を求め、前記誤り値および前記消
失位置を用いて、訂正操作を行う。
【００４９】また、本発明のリードソロモン復号方法
は、好ましくは、ｎ＝２ｔである場合に、２ｔシンボル
の消失エラー訂正を行う。
は、好ましくは、ｎ＝２ｔである場合に、２ｔシンボル
の消失エラー訂正を行う。
【００５０】さらに、本発明のリードソロモン復号方法
は、好ましくは、ｎ＜ｍ1 あるいはｎ＞ｍ2 である場合
に、前記消失位置を用いないでｔ重以下のエラー訂正を
行う。
は、好ましくは、ｎ＜ｍ1 あるいはｎ＞ｍ2 である場合
に、前記消失位置を用いないでｔ重以下のエラー訂正を
行う。
【００５１】
【発明の実施の形態】以下、本発明の実施形態に係わる
リードソロモン復号方法について説明する。第１実施形態 図１は、本実施形態に係わるリードソロモン復号方法の
フローチャートである。なお、以下、ｍ1 ＝３、ｍ2 ＝
４およびｔ＝２の場合を例示して説明する。このリード
ソロモン復号方法では、図１に示すように、入力系列か
らシンドロームｓ0 〜ｓ3 を計算し（ステップＳ１
１）、その消去フラグから消去位置ｘ1〜ｘ4 を得る
（ステップＳ１２）。そして、消去フラグの数をカウン
トし、このカウント値をｎとする（ステップＳ１３）。
リードソロモン復号方法について説明する。第１実施形態 図１は、本実施形態に係わるリードソロモン復号方法の
フローチャートである。なお、以下、ｍ1 ＝３、ｍ2 ＝
４およびｔ＝２の場合を例示して説明する。このリード
ソロモン復号方法では、図１に示すように、入力系列か
らシンドロームｓ0 〜ｓ3 を計算し（ステップＳ１
１）、その消去フラグから消去位置ｘ1〜ｘ4 を得る
（ステップＳ１２）。そして、消去フラグの数をカウン
トし、このカウント値をｎとする（ステップＳ１３）。
【００５２】次に、ｎ＜ｍ1 あるいはｎ＞ｍ2 である
か、すなわち、ｎ＜３あるいはｎ＞４であるかを判断し
（ステップＳ１４）、ｎ＜３あるいはｎ＞４である場合
には、消去エラー訂正ができないので、訂正操作を行わ
ない（図１中実線（１））。あるいは、消去位置を用い
ないで、従来から行われているエラー訂正を実行し（図
１中点線（２））、２重以下の訂正を行う（ステップＳ
２１，２２，２３）。
か、すなわち、ｎ＜３あるいはｎ＞４であるかを判断し
（ステップＳ１４）、ｎ＜３あるいはｎ＞４である場合
には、消去エラー訂正ができないので、訂正操作を行わ
ない（図１中実線（１））。あるいは、消去位置を用い
ないで、従来から行われているエラー訂正を実行し（図
１中点線（２））、２重以下の訂正を行う（ステップＳ
２１，２２，２３）。
【００５３】一方、０≦ｍ1 ≦ｎ≦ｍ2 ≦２ｔである場
合に、すなわち、３≦ｎ≦４の場合には、ｎ＝４（２
ｔ）であるか否かを判断し（ステップＳ１５）、ｎ＝４
であれば、従来技術において述べた、式（３），
（４），（６），（７），（９）および（１０）のアル
ゴリズムにより、４重消失エラー訂正の復号演算を実行
して、誤り値ｅ1 〜ｅ4 を求める（ステップＳ１６）。
次に、この求めた誤り値ｅ1 〜ｅ4 と、前述した消失位
置（すなわち、誤りの位置）ｘ1 〜ｘ4 を用いて訂正操
作を行う（ステップＳ１７）。
合に、すなわち、３≦ｎ≦４の場合には、ｎ＝４（２
ｔ）であるか否かを判断し（ステップＳ１５）、ｎ＝４
であれば、従来技術において述べた、式（３），
（４），（６），（７），（９）および（１０）のアル
ゴリズムにより、４重消失エラー訂正の復号演算を実行
して、誤り値ｅ1 〜ｅ4 を求める（ステップＳ１６）。
次に、この求めた誤り値ｅ1 〜ｅ4 と、前述した消失位
置（すなわち、誤りの位置）ｘ1 〜ｘ4 を用いて訂正操
作を行う（ステップＳ１７）。
【００５４】また、ステップＳ１５においてｎ＝４でな
い場合には、ｎ＝３であるか否かが判断され（ステップ
Ｓ１８）、ｎ＝３である場合には、前述した式（６），
（７），（９）および（１０）のアルゴリズムにより、
３重消失エラー訂正の復号演算を実行して、誤り値ｅ1
〜ｅ3 を求める（ステップＳ１９）。ところで、消失シ
ンボル数が３の場合で、もし復号演算の結果が正しいと
き、すなわち、消失位置以外に誤りが生じていない場合
には、入力系列からシンドローム演算により得たｓ0 〜
ｓ3 と、消失位置ｘ1 〜ｘ3 および復号および復号演算
から求めた誤り値ｅ1 〜ｅ3 との間には、下記式（１２
ａ）〜（１２ｄ）に示す関係がある。
い場合には、ｎ＝３であるか否かが判断され（ステップ
Ｓ１８）、ｎ＝３である場合には、前述した式（６），
（７），（９）および（１０）のアルゴリズムにより、
３重消失エラー訂正の復号演算を実行して、誤り値ｅ1
〜ｅ3 を求める（ステップＳ１９）。ところで、消失シ
ンボル数が３の場合で、もし復号演算の結果が正しいと
き、すなわち、消失位置以外に誤りが生じていない場合
には、入力系列からシンドローム演算により得たｓ0 〜
ｓ3 と、消失位置ｘ1 〜ｘ3 および復号および復号演算
から求めた誤り値ｅ1 〜ｅ3 との間には、下記式（１２
ａ）〜（１２ｄ）に示す関係がある。
【００５５】
【数１２】
【００５６】ここで、消失位置以外に誤りが生じていて
復号演算の結果が正しくないときにも、求めたｅ1 〜ｅ
3 は前述した式（５）の解であるから上記式（１２ａ）
〜（１２ｃ）は必ず成立する。ところが、式（１２ｄ）
は、復号演算には用いられていないので必ず成立すると
は限らず、消失位置以外に誤りが生じていて復号演算の
結果が正しくないときは、むしろ成立しない確率が高
い。従って、復号演算の後に、上記式（１２ｄ）の右辺
を計算し、それが入力系列からシンドローム演算により
得たｓ3 と一致するかどうかで、正常終了判定を行う
（ステップＳ２０）。もし、正常に終了していたなら
ば、誤り値ｅ1 〜ｅ3 と消失位置ｘ1 〜ｘ3 とを用いて
訂正操作を行う（ステップＳ１７）。
復号演算の結果が正しくないときにも、求めたｅ1 〜ｅ
3 は前述した式（５）の解であるから上記式（１２ａ）
〜（１２ｃ）は必ず成立する。ところが、式（１２ｄ）
は、復号演算には用いられていないので必ず成立すると
は限らず、消失位置以外に誤りが生じていて復号演算の
結果が正しくないときは、むしろ成立しない確率が高
い。従って、復号演算の後に、上記式（１２ｄ）の右辺
を計算し、それが入力系列からシンドローム演算により
得たｓ3 と一致するかどうかで、正常終了判定を行う
（ステップＳ２０）。もし、正常に終了していたなら
ば、誤り値ｅ1 〜ｅ3 と消失位置ｘ1 〜ｘ3 とを用いて
訂正操作を行う（ステップＳ１７）。
【００５７】一方、正常に終了していない場合には、訂
正操作は行わない（図１中実線（３））。あるいは、訂
正の速度に余裕がある場合には、消失位置を用いない
で、従来から行われているエラー訂正を実行すること
で、２重以下の訂正を行う（図１中点線（４））。この
場合には、誤り値ｅ1 ，ｅ2 と共に、新たに誤り位置
ｘ’１，ｘ’２を得て、訂正操作を行う（ステップＳ２
１，２２，２３）。
正操作は行わない（図１中実線（３））。あるいは、訂
正の速度に余裕がある場合には、消失位置を用いない
で、従来から行われているエラー訂正を実行すること
で、２重以下の訂正を行う（図１中点線（４））。この
場合には、誤り値ｅ1 ，ｅ2 と共に、新たに誤り位置
ｘ’１，ｘ’２を得て、訂正操作を行う（ステップＳ２
１，２２，２３）。
【００５８】ｎ＝２のときには、２重消去エラー訂正お
よび１重エラー訂正を実行するものが考えられる。これ
は、２重消去エラー訂正のアルゴリズムで消去位置
ｘ1 ，ｘ 2 を用いて誤り値ｅ1 ，ｅ2 を求め、１重エラ
ー訂正のアルゴリズムで誤り位置ｘ’3 と誤り値ｅ3 を
得る。これらの値と入力系列からシンドローム演算によ
り得たｓ0 〜ｓ3 との間には、下記式（１３）に示すよ
うな関係がある。
よび１重エラー訂正を実行するものが考えられる。これ
は、２重消去エラー訂正のアルゴリズムで消去位置
ｘ1 ，ｘ 2 を用いて誤り値ｅ1 ，ｅ2 を求め、１重エラ
ー訂正のアルゴリズムで誤り位置ｘ’3 と誤り値ｅ3 を
得る。これらの値と入力系列からシンドローム演算によ
り得たｓ0 〜ｓ3 との間には、下記式（１３）に示すよ
うな関係がある。
【００５９】
【数１３】
【００６０】このとき、求める値は、ｅ1 〜ｅ3 とｘ’
3 の４つであるから、上記式（１３）の４つの方程式か
らなる連立方程式を解くことで上記４つのパラメータを
得ることができ、３バイトの訂正ができるはずである。
しかしながら、上記式（１３）を解くのは複雑である。
3 の４つであるから、上記式（１３）の４つの方程式か
らなる連立方程式を解くことで上記４つのパラメータを
得ることができ、３バイトの訂正ができるはずである。
しかしながら、上記式（１３）を解くのは複雑である。
【００６１】ｎ≦２（＝ｔ）の場合の簡単な方法は、図
１に示すように、消失エラー訂正を実行しないで前記２
重以下の訂正を実行することである。この方法が有効な
のは、２重消失エラー訂正のみを実行しても、訂正可能
なシンボル数は、高々２シンボルであり、かつ、消失位
置以外のシンボルに誤りが生じているときに上記（１
３）を解いて訂正するのは複雑だからである。従って、
上述した例では、ｍ1 ＞ｔとすることが望ましい。
１に示すように、消失エラー訂正を実行しないで前記２
重以下の訂正を実行することである。この方法が有効な
のは、２重消失エラー訂正のみを実行しても、訂正可能
なシンボル数は、高々２シンボルであり、かつ、消失位
置以外のシンボルに誤りが生じているときに上記（１
３）を解いて訂正するのは複雑だからである。従って、
上述した例では、ｍ1 ＞ｔとすることが望ましい。
【００６２】以上説明したように、本実施形態のリード
ソロモン復号方法によれば、誤訂正を効果的に防止でき
る。また、本実施形態のリードソロモン復号方法では、
ｎ≦２（＝ｔ）の場合の訂正方法を明確化している。
ソロモン復号方法によれば、誤訂正を効果的に防止でき
る。また、本実施形態のリードソロモン復号方法では、
ｎ≦２（＝ｔ）の場合の訂正方法を明確化している。
【００６３】上述した実施形態では、ＣＩＲＣ符号を例
に、ｔ＝２の場合について説明したが、本発明は任意の
値のｔに対して適用できる。ただし、ｔが比較的大きな
値の場合には、連立方程式の解を直接求めるのが困難で
あるため、ユークリッド復号法などの繰り返しのアルゴ
リズムを用いる。前記ユークリッド復号法については、
文献「Ｓｕｇｉｙａｍａ、Ｋａｓａｈａｒａ、Ｈｉｒａ
ｓａｗａ著、Ａ ｍｅｔｈｏｄ ｆｏｒ ｓｏｌｖｉｎ
ｇ ｋｅｙ ｅｑｕａｔｉｏｎ ｆｏｒ ｄｅｃｏｄｉ
ｎｇ Ｇｏｐｐａ ｃｏｄｅｓ、Ｉｎｆ．ａｎｄ Ｃｏ
ｎｔ．、２７、１９７５年」に、その消失訂正法につい
ては、文献「Ｓｕｇｉｙａｍａ、Ｋａｓａｈａｒａ、Ｈ
ｉｒａｓａｗａ、Ｎａｍｅｋａｗａ著、Ａｎ ｅｒａｓ
ｕｒｅｓ−ａｎｄ−ｅｒｒｏｒｓ ｄｅｃｏｄｉｎｇ
ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｇｏｐｐａ Ｃｏｄｅ
ｓ、ＩＥＥＥ Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒ
ｙ、１９７６年」に詳しい。このような繰り返しのアル
ゴリズムを用いるときには、消失位置以外のシンボルに
誤りが生じていても、訂正できる場合がある。誤りの総
数Ｎについて、Ｎ＜ｍａｘ｛（２ｔ＋ｎ）／２｝≦２ｔ
であるならば、訂正可能である。このときは、ｎ≦ｔの
ときにも、ｎ＜ｍａｘ｛（２ｔ＋ｎ）／２｝であること
から、ｍ1 ≦ｔとすることも可能である。ここで、ｍａ
ｘ｛ ｝は、ガロア記号であり、例えば、ｍａｘ｛ａ｝
は、ａを越えない最大の整数を示している。また、積符
号の内符号の復号については、所定の数Ｌに対して、復
号後に判明した誤りの数が、ｍａｘ｛（２ｔ＋ｎ）／
２｝−Ｌより大きいならば、出力の消失フラグをセット
したり、誤り訂正を行わないなどの処理も可能である。
このようにすることで、内符号の復号の誤り検出能力を
高めることができる。
に、ｔ＝２の場合について説明したが、本発明は任意の
値のｔに対して適用できる。ただし、ｔが比較的大きな
値の場合には、連立方程式の解を直接求めるのが困難で
あるため、ユークリッド復号法などの繰り返しのアルゴ
リズムを用いる。前記ユークリッド復号法については、
文献「Ｓｕｇｉｙａｍａ、Ｋａｓａｈａｒａ、Ｈｉｒａ
ｓａｗａ著、Ａ ｍｅｔｈｏｄ ｆｏｒ ｓｏｌｖｉｎ
ｇ ｋｅｙ ｅｑｕａｔｉｏｎ ｆｏｒ ｄｅｃｏｄｉ
ｎｇ Ｇｏｐｐａ ｃｏｄｅｓ、Ｉｎｆ．ａｎｄ Ｃｏ
ｎｔ．、２７、１９７５年」に、その消失訂正法につい
ては、文献「Ｓｕｇｉｙａｍａ、Ｋａｓａｈａｒａ、Ｈ
ｉｒａｓａｗａ、Ｎａｍｅｋａｗａ著、Ａｎ ｅｒａｓ
ｕｒｅｓ−ａｎｄ−ｅｒｒｏｒｓ ｄｅｃｏｄｉｎｇ
ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｇｏｐｐａ Ｃｏｄｅ
ｓ、ＩＥＥＥ Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒ
ｙ、１９７６年」に詳しい。このような繰り返しのアル
ゴリズムを用いるときには、消失位置以外のシンボルに
誤りが生じていても、訂正できる場合がある。誤りの総
数Ｎについて、Ｎ＜ｍａｘ｛（２ｔ＋ｎ）／２｝≦２ｔ
であるならば、訂正可能である。このときは、ｎ≦ｔの
ときにも、ｎ＜ｍａｘ｛（２ｔ＋ｎ）／２｝であること
から、ｍ1 ≦ｔとすることも可能である。ここで、ｍａ
ｘ｛ ｝は、ガロア記号であり、例えば、ｍａｘ｛ａ｝
は、ａを越えない最大の整数を示している。また、積符
号の内符号の復号については、所定の数Ｌに対して、復
号後に判明した誤りの数が、ｍａｘ｛（２ｔ＋ｎ）／
２｝−Ｌより大きいならば、出力の消失フラグをセット
したり、誤り訂正を行わないなどの処理も可能である。
このようにすることで、内符号の復号の誤り検出能力を
高めることができる。
【００６４】
【発明の効果】以上説明したように、本発明のリードソ
ロモン復号方法によれば、誤訂正を効果的に防止でき
る。また、本発明のリードソロモン復号方法では、ｎ≦
２（＝ｔ）の場合の訂正方法を明確化している。
ロモン復号方法によれば、誤訂正を効果的に防止でき
る。また、本発明のリードソロモン復号方法では、ｎ≦
２（＝ｔ）の場合の訂正方法を明確化している。
【図１】図１は、本発明の実施形態に係わるリードソロ
モン復号方法のフローチャートである。
モン復号方法のフローチャートである。
【図２】図２は、従来のリードソロモン復号方法のフロ
ーチャートである。
ーチャートである。
【図３】図３は、従来のリードソロモン復号装置の構成
図である。
図である。
【図４】図４は、図３に示すリードソロモン復号装置の
動作時におけるデータおよび構成要素の時系列的な状態
を示し、（Ａ）は入力データ、（Ｂ）は出力データ、
（Ｃ）はレジスタＢOUT の記憶状態、（Ｄ）はレジスタ
ＢINの記憶状態、（Ｅ）はレジスタＧOUT の記憶状態、
（Ｆ）はレジスタＧINの記憶状態、（Ｇ）は復号演算器
の処理状態をそれぞれ示している。
動作時におけるデータおよび構成要素の時系列的な状態
を示し、（Ａ）は入力データ、（Ｂ）は出力データ、
（Ｃ）はレジスタＢOUT の記憶状態、（Ｄ）はレジスタ
ＢINの記憶状態、（Ｅ）はレジスタＧOUT の記憶状態、
（Ｆ）はレジスタＧINの記憶状態、（Ｇ）は復号演算器
の処理状態をそれぞれ示している。
【図５】図５は、図３に示す入力パラメータ演算器およ
びレジスタの構成図である。
びレジスタの構成図である。
【図６】図６は、図３に示す訂正操作実行器およびレジ
スタの構成図である。
スタの構成図である。
【図７】図７は、図３に示す復号演算処理部の構成図で
ある。
ある。
【図８】図８は、図７に示すＧＬＵの構成図である。
１…リードソロモン復号装置、２…メモリブロック、３
…バスＩ／Ｆブロック、４…復号演算処理部、９…入力
パラメータ演算器、１２…訂正操作実行器、１７…復号
演算器
…バスＩ／Ｆブロック、４…復号演算処理部、９…入力
パラメータ演算器、１２…訂正操作実行器、１７…復号
演算器
Claims (3)
- 【請求項１】２ｔ（正の整数）シンボルのパリティデー
タを持つ、リードソロモン符号化系列に対して、誤りの
シンボルの位置を示す消失位置を用いて誤り訂正を行
い、復号するリードソロモン復号方法において、 前記消失位置から誤りのシンボルの数ｎを求め、 ０≦ｍ1 ≦ｎ≦ｍ2 ≦２ｔ（ｍ1 、ｍ2 およびｎは正の
整数）である場合に、 ｎシンボルの消失エラー訂正の復号演算を行って誤り値
を求め、 前記誤り値および前記消失位置を用いて、訂正操作を行
うリードソロモン復号方法。 - 【請求項２】ｎ＝２ｔである場合に、２ｔシンボルの消
失エラー訂正を行う請求項１に記載のリードソロモン復
号方法。 - 【請求項３】ｎ＜ｍ1 あるいはｎ＞ｍ2 である場合に、
前記消失位置を用いないでｔ重以下のエラー訂正を行う
請求項１に記載のリードソロモン復号方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9124411A JPH10322226A (ja) | 1997-05-14 | 1997-05-14 | リードソロモン復号方法 |
| US09/078,423 US6233710B1 (en) | 1997-05-14 | 1998-05-13 | Reed-Solomon decoding device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9124411A JPH10322226A (ja) | 1997-05-14 | 1997-05-14 | リードソロモン復号方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10322226A true JPH10322226A (ja) | 1998-12-04 |
Family
ID=14884813
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP9124411A Pending JPH10322226A (ja) | 1997-05-14 | 1997-05-14 | リードソロモン復号方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6233710B1 (ja) |
| JP (1) | JPH10322226A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6233710B1 (en) * | 1997-05-14 | 2001-05-15 | Texas Instruments Incorporated | Reed-Solomon decoding device |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100378181B1 (ko) * | 2000-06-09 | 2003-03-29 | 삼성전자주식회사 | Ｅｆｍ/ｅｆｍ+ 디코딩에 의해 검출된 에러위치를 이용한ｃ1/ｐｉ 워드의 에러정정 방법 및 장치 |
| KR100561847B1 (ko) * | 2003-10-08 | 2006-03-16 | 삼성전자주식회사 | 공개키를 이용한 데이터 암호화 및 복호화 방법 |
| US7228490B2 (en) * | 2004-02-19 | 2007-06-05 | Quantum Corporation | Error correction decoder using cells with partial syndrome generation |
| US10164660B1 (en) | 2016-12-23 | 2018-12-25 | Intel Corporation | Syndrome-based Reed-Solomon erasure decoding circuitry |
| US11962327B2 (en) * | 2022-01-13 | 2024-04-16 | Micron Technology, Inc. | Iterative decoding technique for correcting DRAM device failures |
Family Cites Families (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4541091A (en) * | 1982-06-11 | 1985-09-10 | Hitachi, Ltd. | Code error detection and correction method and apparatus |
| JP2605271B2 (ja) * | 1987-02-10 | 1997-04-30 | ソニー株式会社 | エラー訂正及びチエツク装置 |
| US5099482A (en) * | 1989-08-30 | 1992-03-24 | Idaho Research Foundation, Inc. | Apparatus for detecting uncorrectable error patterns when using Euclid's algorithm to decode Reed-Solomon (BCH) codes |
| US5589994A (en) * | 1992-08-21 | 1996-12-31 | Mitsubishi Denki Kabushiki Kaisha | Image recording method and apparatus with reduced error propagation |
| JP3154607B2 (ja) * | 1993-12-28 | 2001-04-09 | 三菱電機株式会社 | 誤り訂正復号装置及び誤り訂正復号方法 |
| US5644695A (en) * | 1994-01-03 | 1997-07-01 | International Business Machines Corporation | Array combinatorial decoding with multiple error and erasure detection and location using cyclic equivalence testing |
| JP3328093B2 (ja) * | 1994-07-12 | 2002-09-24 | 三菱電機株式会社 | エラー訂正装置 |
| KR20000011007A (ko) * | 1996-05-15 | 2000-02-25 | 토마스 에프.멀베니 | 판독 채널 성능 지시기 및 에러 정정코드를 이용한 판독 방법및 디스크 드라이브u |
| JP3850512B2 (ja) * | 1997-05-07 | 2006-11-29 | 日本テキサス・インスツルメンツ株式会社 | リードソロモン復号装置 |
| JPH10322226A (ja) * | 1997-05-14 | 1998-12-04 | Texas Instr Japan Ltd | リードソロモン復号方法 |
| US6009550A (en) * | 1997-05-20 | 1999-12-28 | Seagate Technology, Inc. | PBA recovery apparatus and method for interleaved reed-solomon codes |
| JP3813337B2 (ja) * | 1997-12-01 | 2006-08-23 | 日本テキサス・インスツルメンツ株式会社 | 消失誤り訂正方法とその装置 |
-
1997
- 1997-05-14 JP JP9124411A patent/JPH10322226A/ja active Pending
-
1998
- 1998-05-13 US US09/078,423 patent/US6233710B1/en not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6233710B1 (en) * | 1997-05-14 | 2001-05-15 | Texas Instruments Incorporated | Reed-Solomon decoding device |
Also Published As
| Publication number | Publication date |
|---|---|
| US6233710B1 (en) | 2001-05-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5020060A (en) | Error code correction device having a galois arithmetic unit | |
| EP0357461B1 (en) | Error correction circuit | |
| US5642367A (en) | Finite field polynomial processing module for error control coding | |
| EP0114938A2 (en) | On-the-fly multibyte error correction | |
| JP2001502153A (ja) | 大規模データ・ブロックのためのハードウェア最適化リード・ソロモン・デコーダ | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| CA1291819C (en) | Decoder | |
| JPH11507754A (ja) | １０ビットリード−ソロモン誤り訂正モジュール用専用ａｌｕアーキテクチャ | |
| KR100213254B1 (ko) | 에러 정정 방법 및 장치 | |
| JP3850511B2 (ja) | リードソロモン復号装置 | |
| JPH10322226A (ja) | リードソロモン復号方法 | |
| US20030159103A1 (en) | Efficient method for fast decoding of BCH binary codes | |
| EP0629052B1 (en) | Method of and circuit for correcting errors | |
| JP3850512B2 (ja) | リードソロモン復号装置 | |
| JP2605966B2 (ja) | 誤り訂正回路 | |
| JP2553565B2 (ja) | ガロア体演算装置 | |
| JP2665268B2 (ja) | サイクリックコードのステップ・バイ・ステップ型復号方法及び復号器 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JP3265273B2 (ja) | 誤り訂正回路 | |
| JP2553571B2 (ja) | ガロア体演算装置 | |
| JPH07230388A (ja) | 誤り訂正方法及び装置 | |
| KR0158639B1 (ko) | 신드롬 변환을 이용한 에러 정정 장치 및 그 방법 | |
| KR910009094B1 (ko) | 갈로이계 연산장치 | |
| KR930000220B1 (ko) | 리드-솔로몬 코드의 에러위치 정정시스템 | |
| JPH0133055B2 (ja) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20040430 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20060516 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20060530 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20061003 |