JP3352659B2 - 復号装置及び復号方法 - Google Patents
復号装置及び復号方法Info
- Publication number
- JP3352659B2 JP3352659B2 JP2000086831A JP2000086831A JP3352659B2 JP 3352659 B2 JP3352659 B2 JP 3352659B2 JP 2000086831 A JP2000086831 A JP 2000086831A JP 2000086831 A JP2000086831 A JP 2000086831A JP 3352659 B2 JP3352659 B2 JP 3352659B2
- Authority
- JP
- Japan
- Prior art keywords
- error
- data
- correction
- syndrome
- correction data
- 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 - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 30
- 238000012937 correction Methods 0.000 claims description 261
- 208000011580 syndromic disease Diseases 0.000 claims description 188
- 238000004364 calculation method Methods 0.000 claims description 51
- 238000011156 evaluation Methods 0.000 claims description 49
- 238000012545 processing Methods 0.000 claims description 42
- 238000013500 data storage Methods 0.000 claims description 24
- 238000009795 derivation Methods 0.000 claims description 7
- 238000004422 calculation algorithm Methods 0.000 claims description 3
- 238000010586 diagram Methods 0.000 description 6
- 238000001514 detection method Methods 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 1
- 238000004587 chromatography analysis Methods 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 230000000717 retained effect Effects 0.000 description 1
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
-
- 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/1555—Pipelined decoder implementations
-
- 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
-
- 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/1525—Determination and particular use of error location polynomials
- H03M13/1535—Determination and particular use of error location polynomials using the Euclid algorithm
-
- 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/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
-
- 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)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
- Detection And Correction Of Errors (AREA)
Description
【０００１】
【発明の属する技術分野】本発明は、拡大リードソロモ
ン（Reed-Solomon）符号の多重誤り訂正を行う復号技術
に関する。
ン（Reed-Solomon）符号の多重誤り訂正を行う復号技術
に関する。
【０００２】
【従来の技術】各種大容量記憶装置の記憶情報、高速通
信の伝送情報等において、多重誤り訂正を可能とする符
号としてリードソロモン符号が広く使用されている。
信の伝送情報等において、多重誤り訂正を可能とする符
号としてリードソロモン符号が広く使用されている。
【０００３】リードソロモン符号は、原始多項式をＷ
(z) とし、Ｗ(z)＝０の根をαとするとき、この根αを
原始元とするガロア体（Galois field）上の符号であっ
て、ブロック誤り訂正符号の１つである。ここで、ガロ
ア体ＧＦ（２m）の原始元をαとし、このガロア体ＧＦ
（２m）の元α0，α1，…，α＾（２m−２）の中に根を
持つリードソロモン符号を考える。この符号では、符号
長ｎ＝２m−１であり、ｍビットが１処理単位、すなわ
ち１シンボルとされる。原情報の量はｎ−２ｔシンボル
（ｔは誤り訂正数）である。
(z) とし、Ｗ(z)＝０の根をαとするとき、この根αを
原始元とするガロア体（Galois field）上の符号であっ
て、ブロック誤り訂正符号の１つである。ここで、ガロ
ア体ＧＦ（２m）の原始元をαとし、このガロア体ＧＦ
（２m）の元α0，α1，…，α＾（２m−２）の中に根を
持つリードソロモン符号を考える。この符号では、符号
長ｎ＝２m−１であり、ｍビットが１処理単位、すなわ
ち１シンボルとされる。原情報の量はｎ−２ｔシンボル
（ｔは誤り訂正数）である。
【０００４】リードソロモン符号の復号は、一般に、 （ａ）シンドローム算出 （ｂ）誤り評価多項式及び誤り位置多項式の算出 （ｃ）チェンサーチによる誤りの位置の算出 （ｄ）誤りの大きさの算出 （ｅ）誤りの位置と誤りの大きさに基づくデータの訂正 の手順で行う。この復号方法の詳細に関しては、特開平
１０−１３５８４６号公報に開示されている。
１０−１３５８４６号公報に開示されている。
【０００５】ところが、最近、ケーブルモデムやケーブ
ルテレビ等のシステムにおいて、拡大リードソロモン符
号を用いて誤り訂正を行う仕様が採用されている。拡大
リードソロモン符号は、符号長ｎが、符号の根が属する
ガロア体の元の数ｑ以上である符号であって、符号長ｎ
＝ｑの場合は１次拡大リードソロモン符号、符号長ｎ＝
ｑ＋１の場合は２次拡大リードソロモン符号と呼ばれ
る。
ルテレビ等のシステムにおいて、拡大リードソロモン符
号を用いて誤り訂正を行う仕様が採用されている。拡大
リードソロモン符号は、符号長ｎが、符号の根が属する
ガロア体の元の数ｑ以上である符号であって、符号長ｎ
＝ｑの場合は１次拡大リードソロモン符号、符号長ｎ＝
ｑ＋１の場合は２次拡大リードソロモン符号と呼ばれ
る。
【０００６】例えば、北米のケーブルテレビのシステム
では、ガロア体ＧＦ（２7）上において、原始多項式Ｐ
（ｘ）として、Ｐ（ｘ）＝ｘ7＋ｘ3＋１、生成多項式Ｇ
L（ｘ）として、ＧL（ｘ）＝（ｘ＋α）（ｘ＋α2）
（ｘ＋α3）（ｘ＋α4）（ｘ＋α5）を用いた、誤り訂
正数ｔ＝３の１次拡大リードソロモン符号が採用されて
いる。なお、この拡大リードソロモン符号では、誤り訂
正数ｔ＝３であるにもかかわらず生成多項式ＧL（ｘ）
は５次の多項式であるため、シンドローム計算の際に通
常とは異なった処理が必要となる。
では、ガロア体ＧＦ（２7）上において、原始多項式Ｐ
（ｘ）として、Ｐ（ｘ）＝ｘ7＋ｘ3＋１、生成多項式Ｇ
L（ｘ）として、ＧL（ｘ）＝（ｘ＋α）（ｘ＋α2）
（ｘ＋α3）（ｘ＋α4）（ｘ＋α5）を用いた、誤り訂
正数ｔ＝３の１次拡大リードソロモン符号が採用されて
いる。なお、この拡大リードソロモン符号では、誤り訂
正数ｔ＝３であるにもかかわらず生成多項式ＧL（ｘ）
は５次の多項式であるため、シンドローム計算の際に通
常とは異なった処理が必要となる。
【０００７】通常のリードソロモン符号は、符号長をｎ
を２mとする場合は、２m+1個の元を有するガロア体ＧＦ
（２m+1）上で符号を構成する必要があるが、拡大リー
ドソロモン符号は、ガロア体ＧＦ（２m）上であっても
符号長ｎを２m以上に伸長することが可能である。
を２mとする場合は、２m+1個の元を有するガロア体ＧＦ
（２m+1）上で符号を構成する必要があるが、拡大リー
ドソロモン符号は、ガロア体ＧＦ（２m）上であっても
符号長ｎを２m以上に伸長することが可能である。
【０００８】
【発明が解決しようとする課題】１シンボルのビット数
ｍ＝７、誤り訂正数ｔ＝３とするガロア体ＧＦ（２7）
上のリードソロモン符号を考える。
ｍ＝７、誤り訂正数ｔ＝３とするガロア体ＧＦ（２7）
上のリードソロモン符号を考える。
【０００９】通常のリードソロモン符号は、ガロア体Ｇ
Ｆ（２7）の元α0，α1，…，α126の中に根を持ち、符
号長ｎ＝１２７である。生成多項式Ｇ（ｘ）の次数は誤
り訂正数ｔの２倍であるので、誤り訂正数ｔ＝３のと
き、生成多項式Ｇ（ｘ）は、６次の多項式を用いて、Ｇ
（ｘ）＝（ｘ＋α）（ｘ＋α2）（ｘ＋α3）（ｘ＋
α4）（ｘ＋α5）（ｘ＋α6）とすることができる。
Ｆ（２7）の元α0，α1，…，α126の中に根を持ち、符
号長ｎ＝１２７である。生成多項式Ｇ（ｘ）の次数は誤
り訂正数ｔの２倍であるので、誤り訂正数ｔ＝３のと
き、生成多項式Ｇ（ｘ）は、６次の多項式を用いて、Ｇ
（ｘ）＝（ｘ＋α）（ｘ＋α2）（ｘ＋α3）（ｘ＋
α4）（ｘ＋α5）（ｘ＋α6）とすることができる。
【００１０】一方、拡大リードソロモン符号を考えれ
ば、同じガロア体ＧＦ（２7）において、より長い符号
長を持つ符号を構成し、誤り訂正を行うことが可能であ
る。例えば、符号長ｎ＝１２８とする拡大リードソロモ
ン符号を考えることができる。
ば、同じガロア体ＧＦ（２7）において、より長い符号
長を持つ符号を構成し、誤り訂正を行うことが可能であ
る。例えば、符号長ｎ＝１２８とする拡大リードソロモ
ン符号を考えることができる。
【００１１】通常のリードソロモン符号の復号において
は、誤り位置多項式の根と誤りの位置とは１対１に対応
しているため、チェンサーチによって誤り位置多項式を
解くことで誤りの位置が求まる。チェンサーチは、ガロ
ア体のすべての元を誤り位置多項式に順次代入してい
き、この式の値が零になる元を誤り位置多項式の根とし
て求める方法である。例えば、誤り訂正数ｔ＝３の場合
は、３次式となる誤り位置多項式に元を順次代入し、式
の値が零になった時に代入した元が誤り位置多項式の３
個の根として求められる。
は、誤り位置多項式の根と誤りの位置とは１対１に対応
しているため、チェンサーチによって誤り位置多項式を
解くことで誤りの位置が求まる。チェンサーチは、ガロ
ア体のすべての元を誤り位置多項式に順次代入してい
き、この式の値が零になる元を誤り位置多項式の根とし
て求める方法である。例えば、誤り訂正数ｔ＝３の場合
は、３次式となる誤り位置多項式に元を順次代入し、式
の値が零になった時に代入した元が誤り位置多項式の３
個の根として求められる。
【００１２】符号語に訂正能力を超えた誤りが付加され
た場合は、誤り評価多項式と誤り位置多項式とが正しく
導出されなかったり、チェンサーチの処理において正し
く誤り位置多項式の根が導出されないことから、誤り訂
正が不可能であることを認識することができる。この場
合は、誤り訂正処理を施さず、入力データをそのまま出
力する。
た場合は、誤り評価多項式と誤り位置多項式とが正しく
導出されなかったり、チェンサーチの処理において正し
く誤り位置多項式の根が導出されないことから、誤り訂
正が不可能であることを認識することができる。この場
合は、誤り訂正処理を施さず、入力データをそのまま出
力する。
【００１３】ところが、拡大リードソロモン符号では、
符号長ｎがガロア体ＧＦ（２7）の０以外の元の個数よ
り大きくなるため、元と誤りの位置とが１対１に対応せ
ず、チェンサーチについて通常のリードソロモン符号の
復号とは異なった処理を行う必要がある。
符号長ｎがガロア体ＧＦ（２7）の０以外の元の個数よ
り大きくなるため、元と誤りの位置とが１対１に対応せ
ず、チェンサーチについて通常のリードソロモン符号の
復号とは異なった処理を行う必要がある。
【００１４】そこで、次のように考えて、拡大リードソ
ロモン符号を復号する。例えば、符号長ｎ＝１２８の拡
大リードソロモン符号は、誤り訂正数ｔが３の場合、情
報記号１２２シンボルと冗長記号６シンボルとで構成さ
れる。ガロア体ＧＦ（２7）では、チェンサーチによっ
て訂正することができるのは１２７シンボルのみである
ので、受信語１２８シンボルのうち、冗長記号１シンボ
ルを除いた残りの１２７シンボルのみを対象として誤り
訂正を行なう。
ロモン符号を復号する。例えば、符号長ｎ＝１２８の拡
大リードソロモン符号は、誤り訂正数ｔが３の場合、情
報記号１２２シンボルと冗長記号６シンボルとで構成さ
れる。ガロア体ＧＦ（２7）では、チェンサーチによっ
て訂正することができるのは１２７シンボルのみである
ので、受信語１２８シンボルのうち、冗長記号１シンボ
ルを除いた残りの１２７シンボルのみを対象として誤り
訂正を行なう。
【００１５】しかし、１２８シンボルの符号を用いて符
号のうちの１２７シンボルを訂正することと、訂正処理
を施さない冗長記号１シンボルに対して誤りが生じる場
合もあることから、訂正が正しく行われない誤訂正が発
生するという問題がある。
号のうちの１２７シンボルを訂正することと、訂正処理
を施さない冗長記号１シンボルに対して誤りが生じる場
合もあることから、訂正が正しく行われない誤訂正が発
生するという問題がある。
【００１６】本発明は、このような問題を解決するもの
であり、拡大リードソロモン符号の受信語に対する復号
の際に、誤り訂正が可能であるか否かを判定し、誤り訂
正が可能である場合には正しく訂正処理を施したデータ
を得るとともに、誤り訂正が不可能である場合には誤訂
正を行わないようにする、復号装置及び復号方法を提供
することを課題とする。
であり、拡大リードソロモン符号の受信語に対する復号
の際に、誤り訂正が可能であるか否かを判定し、誤り訂
正が可能である場合には正しく訂正処理を施したデータ
を得るとともに、誤り訂正が不可能である場合には誤訂
正を行わないようにする、復号装置及び復号方法を提供
することを課題とする。
【００１７】
【課題を解決するための手段】前記課題を解決するた
め、請求項１の発明が講じた手段は、復号装置として、
拡大リードソロモン符号からなる受信語に対する誤りの
位置と誤りの大きさとを求め、前記誤りの位置と前記誤
りの大きさとを用いて当該受信語に誤り訂正処理を行っ
て、訂正データを生成する訂正処理部を備え、前記訂正
処理部は、生成した訂正データについて、シンドローム
を算出して、得られたシンドロームに基づいて誤りの有
無を判定し、誤りがない訂正データが生成された場合
は、当該訂正データを出力する一方、誤りがない訂正デ
ータが生成できない場合は、当該訂正データに基づい
て、これに対応した前記誤りの位置及び前記誤りの大き
さを用いて誤り訂正前の受信語を復元して出力するもの
である。
め、請求項１の発明が講じた手段は、復号装置として、
拡大リードソロモン符号からなる受信語に対する誤りの
位置と誤りの大きさとを求め、前記誤りの位置と前記誤
りの大きさとを用いて当該受信語に誤り訂正処理を行っ
て、訂正データを生成する訂正処理部を備え、前記訂正
処理部は、生成した訂正データについて、シンドローム
を算出して、得られたシンドロームに基づいて誤りの有
無を判定し、誤りがない訂正データが生成された場合
は、当該訂正データを出力する一方、誤りがない訂正デ
ータが生成できない場合は、当該訂正データに基づい
て、これに対応した前記誤りの位置及び前記誤りの大き
さを用いて誤り訂正前の受信語を復元して出力するもの
である。
【００１８】また、請求項２の発明では、請求項１に記
載の復号装置において、前記訂正処理部は、前記受信語
から生成した訂正データに誤りが存在するときは、誤り
がない訂正データが生成できないと判定する。
載の復号装置において、前記訂正処理部は、前記受信語
から生成した訂正データに誤りが存在するときは、誤り
がない訂正データが生成できないと判定する。
【００１９】また、請求項３の発明は、拡大リードソロ
モン符号からなる受信語を入力データとする復号装置で
あって、前記入力データに基づいて第１の訂正データを
求めるエラー訂正部と、前記入力データのシンドローム
を入力データシンドロームとして求め、当該入力データ
シンドロームに基づいて前記入力データに誤りが存在す
るか否かを示す第１のフラグ信号を出力するとともに、
前記エラー訂正部が求めた前記第１の訂正データに対す
るシンドロームを訂正データシンドロームとして求め、
当該訂正データシンドロームに基づいて前記第１の訂正
データに誤りが存在するか否かを示す第２のフラグ信号
を出力するシンドローム計算部と、前記入力データシン
ドロームに基づいて誤り評価多項式及び誤り位置多項式
の各次数の係数を求めるとともに、前記係数から求めら
れた誤りの評価値及び対応する誤り位置多項式微分値に
基づいて誤りの大きさを求める評価多項式・位置多項式
導出部と、前記係数に基づいて前記誤り位置多項式の根
を求めるとともに、前記誤り評価多項式に前記根のそれ
ぞれを代入して得られる誤りの評価値及び前記誤り位置
多項式の導関数に前記根のそれぞれを代入して得られる
誤り位置多項式微分値を求めるチェンサーチ部とを備
え、前記エラー訂正部は、前記第１のフラグ信号が前記
入力データに誤りが存在することを示す場合は、前記根
及び対応する前記誤りの大きさに基づいて前記入力デー
タに対して誤り訂正処理を行って得たデータを前記第１
の訂正データとして、かつ、前記第１のフラグ信号が前
記入力データに誤りが存在しないことを示す場合は、当
該入力データを前記第１の訂正データとして、前記シン
ドローム計算部に出力するとともに、前記第２のフラグ
信号が前記第１の訂正データに誤りが存在することを示
す場合は、前記第１の訂正データに対して誤り訂正処理
前のデータに戻す復元処理を行って得たデータを第２の
訂正データとして出力し、前記第２のフラグ信号が前記
第１の訂正データに誤りが存在しないことを示す場合
は、当該第１の訂正データを第２の訂正データとして出
力するものである。
モン符号からなる受信語を入力データとする復号装置で
あって、前記入力データに基づいて第１の訂正データを
求めるエラー訂正部と、前記入力データのシンドローム
を入力データシンドロームとして求め、当該入力データ
シンドロームに基づいて前記入力データに誤りが存在す
るか否かを示す第１のフラグ信号を出力するとともに、
前記エラー訂正部が求めた前記第１の訂正データに対す
るシンドロームを訂正データシンドロームとして求め、
当該訂正データシンドロームに基づいて前記第１の訂正
データに誤りが存在するか否かを示す第２のフラグ信号
を出力するシンドローム計算部と、前記入力データシン
ドロームに基づいて誤り評価多項式及び誤り位置多項式
の各次数の係数を求めるとともに、前記係数から求めら
れた誤りの評価値及び対応する誤り位置多項式微分値に
基づいて誤りの大きさを求める評価多項式・位置多項式
導出部と、前記係数に基づいて前記誤り位置多項式の根
を求めるとともに、前記誤り評価多項式に前記根のそれ
ぞれを代入して得られる誤りの評価値及び前記誤り位置
多項式の導関数に前記根のそれぞれを代入して得られる
誤り位置多項式微分値を求めるチェンサーチ部とを備
え、前記エラー訂正部は、前記第１のフラグ信号が前記
入力データに誤りが存在することを示す場合は、前記根
及び対応する前記誤りの大きさに基づいて前記入力デー
タに対して誤り訂正処理を行って得たデータを前記第１
の訂正データとして、かつ、前記第１のフラグ信号が前
記入力データに誤りが存在しないことを示す場合は、当
該入力データを前記第１の訂正データとして、前記シン
ドローム計算部に出力するとともに、前記第２のフラグ
信号が前記第１の訂正データに誤りが存在することを示
す場合は、前記第１の訂正データに対して誤り訂正処理
前のデータに戻す復元処理を行って得たデータを第２の
訂正データとして出力し、前記第２のフラグ信号が前記
第１の訂正データに誤りが存在しないことを示す場合
は、当該第１の訂正データを第２の訂正データとして出
力するものである。
【００２０】請求項３の発明によると、入力データシン
ドロームだけではなく、訂正データシンドロームをも求
めるので、誤り訂正が正しく行われたか否かを知ること
ができる。
ドロームだけではなく、訂正データシンドロームをも求
めるので、誤り訂正が正しく行われたか否かを知ること
ができる。
【００２１】また、請求項４の発明では、請求項３に記
載の復号装置において、前記シンドローム計算部は、前
記入力データ及び前記エラー訂正部が出力する前記第１
の訂正データを入力とし、これらを交互に出力するセレ
クタと、前記セレクタが出力する前記入力データ及び前
記第１の訂正データに基づいて、前記入力データシンド
ローム及び前記訂正データシンドロームをそれぞれ求め
るシンドローム演算器と、前記入力データシンドローム
を保持して出力する入力データシンドローム保持器と、
前記訂正データシンドロームを保持して出力する訂正デ
ータシンドローム保持器と、前記入力データシンドロー
ム保持器が出力する前記入力データシンドロームの成分
がすべて零である場合は前記入力データに誤りが存在し
ないことを示すように、そうでない場合は前記入力デー
タに誤りが存在することを示すように、前記第１のフラ
グ信号を出力する第１のシンドローム零検出器と、前記
訂正データシンドローム保持器が出力する前記訂正デー
タシンドロームの成分がすべて零である場合は前記第１
の訂正データに誤りが存在しないことを示すように、そ
うでない場合は前記第１の訂正データに誤りが存在する
ことを示すように、前記第２のフラグ信号を出力する第
２のシンドローム零検出器とを備える。
載の復号装置において、前記シンドローム計算部は、前
記入力データ及び前記エラー訂正部が出力する前記第１
の訂正データを入力とし、これらを交互に出力するセレ
クタと、前記セレクタが出力する前記入力データ及び前
記第１の訂正データに基づいて、前記入力データシンド
ローム及び前記訂正データシンドロームをそれぞれ求め
るシンドローム演算器と、前記入力データシンドローム
を保持して出力する入力データシンドローム保持器と、
前記訂正データシンドロームを保持して出力する訂正デ
ータシンドローム保持器と、前記入力データシンドロー
ム保持器が出力する前記入力データシンドロームの成分
がすべて零である場合は前記入力データに誤りが存在し
ないことを示すように、そうでない場合は前記入力デー
タに誤りが存在することを示すように、前記第１のフラ
グ信号を出力する第１のシンドローム零検出器と、前記
訂正データシンドローム保持器が出力する前記訂正デー
タシンドロームの成分がすべて零である場合は前記第１
の訂正データに誤りが存在しないことを示すように、そ
うでない場合は前記第１の訂正データに誤りが存在する
ことを示すように、前記第２のフラグ信号を出力する第
２のシンドローム零検出器とを備える。
【００２２】請求項４の発明によると、入力データシン
ドローム及び訂正データシンドロームを並行して求め、
第１のフラグ信号及び第２のフラグ信号を同時に出力す
るので、入力データ及び第１の訂正データに誤りが存在
するか否かを同時に知ることができる。
ドローム及び訂正データシンドロームを並行して求め、
第１のフラグ信号及び第２のフラグ信号を同時に出力す
るので、入力データ及び第１の訂正データに誤りが存在
するか否かを同時に知ることができる。
【００２３】また、請求項５の発明では、請求項３に記
載の復号装置において、前記評価多項式・位置多項式導
出部は、ユークリッド互除演算によって、前記入力デー
タシンドロームに基づいて前記誤り評価多項式及び前記
誤り位置多項式の各次数の係数を求めて出力するもので
あって、前記ユークリッド互除演算終了時に、前記誤り
位置多項式の次数が前記誤り評価多項式の次数以下であ
っても、前記係数を出力する。
載の復号装置において、前記評価多項式・位置多項式導
出部は、ユークリッド互除演算によって、前記入力デー
タシンドロームに基づいて前記誤り評価多項式及び前記
誤り位置多項式の各次数の係数を求めて出力するもので
あって、前記ユークリッド互除演算終了時に、前記誤り
位置多項式の次数が前記誤り評価多項式の次数以下であ
っても、前記係数を出力する。
【００２４】請求項５の発明によると、ユークリッド互
除演算の結果にかかわらず、誤り評価多項式及び誤り位
置多項式を得ることができるので、誤りの位置及び誤り
の大きさを求め、拡大リードソロモン符号の復号を行う
ことができる。
除演算の結果にかかわらず、誤り評価多項式及び誤り位
置多項式を得ることができるので、誤りの位置及び誤り
の大きさを求め、拡大リードソロモン符号の復号を行う
ことができる。
【００２５】また、請求項６の発明では、請求項３に記
載の復号装置において、前記チェンサーチ部は、前記誤
り位置多項式に前記拡大リードソロモン符号の根が定義
されるガロア体の元を順次代入し、前記誤り位置多項式
の値が零となる元を当該誤り位置多項式の根として求
め、当該誤り位置多項式の互いに異なる根の数が当該誤
り位置多項式の次数未満の場合であっても、当該誤り位
置多項式の根を出力する。
載の復号装置において、前記チェンサーチ部は、前記誤
り位置多項式に前記拡大リードソロモン符号の根が定義
されるガロア体の元を順次代入し、前記誤り位置多項式
の値が零となる元を当該誤り位置多項式の根として求
め、当該誤り位置多項式の互いに異なる根の数が当該誤
り位置多項式の次数未満の場合であっても、当該誤り位
置多項式の根を出力する。
【００２６】請求項６の発明によると、チェンサーチに
よって得られた誤り位置多項式の互いに異なる根の数に
かかわらず、その根を利用することができるので、誤り
の位置及び誤りの大きさを求めて、拡大リードソロモン
符号の復号を行うことができる。
よって得られた誤り位置多項式の互いに異なる根の数に
かかわらず、その根を利用することができるので、誤り
の位置及び誤りの大きさを求めて、拡大リードソロモン
符号の復号を行うことができる。
【００２７】また、請求項７の発明では、請求項３に記
載の復号装置において、前記エラー訂正部は、前記第１
のフラグ信号が前記入力データに誤りが存在することを
示す場合は、前記入力データに対して、前記根のそれぞ
れに対応する誤りの位置が示すシンボルから対応する前
記誤りの大きさを減じる誤り訂正処理を行って得られた
データを、そうでない場合は、前記入力データを、それ
ぞれ前記第１の訂正データとして出力する第１のエラー
訂正器と、前記誤りの位置を保持して出力する誤りの位
置データ保持器と、前記誤りの大きさを保持して出力す
る誤りの大きさデータ保持器と、前記第２のフラグ信号
が前記第１の訂正データに誤りが存在することを示す場
合は、前記第１の訂正データに対して、前記誤りの位置
が示すシンボルに対応する前記誤りの大きさの値を加算
して前記誤り訂正処理を行う前のデータに戻す復元処理
を行って得られたデータを、そうでない場合は、前記第
１の訂正データを、それぞれ前記第２の訂正データとし
て出力する第２のエラー訂正器とを備える。
載の復号装置において、前記エラー訂正部は、前記第１
のフラグ信号が前記入力データに誤りが存在することを
示す場合は、前記入力データに対して、前記根のそれぞ
れに対応する誤りの位置が示すシンボルから対応する前
記誤りの大きさを減じる誤り訂正処理を行って得られた
データを、そうでない場合は、前記入力データを、それ
ぞれ前記第１の訂正データとして出力する第１のエラー
訂正器と、前記誤りの位置を保持して出力する誤りの位
置データ保持器と、前記誤りの大きさを保持して出力す
る誤りの大きさデータ保持器と、前記第２のフラグ信号
が前記第１の訂正データに誤りが存在することを示す場
合は、前記第１の訂正データに対して、前記誤りの位置
が示すシンボルに対応する前記誤りの大きさの値を加算
して前記誤り訂正処理を行う前のデータに戻す復元処理
を行って得られたデータを、そうでない場合は、前記第
１の訂正データを、それぞれ前記第２の訂正データとし
て出力する第２のエラー訂正器とを備える。
【００２８】請求項７の発明によると、入力データに対
する訂正処理と、第１の訂正データに対する復元処理と
を並行して行うことができ、処理を高速に行うことがで
きる。
する訂正処理と、第１の訂正データに対する復元処理と
を並行して行うことができ、処理を高速に行うことがで
きる。
【００２９】また、請求項８の発明は、請求項３に記載
の復号装置において、前記入力データを、前記エラー訂
正部が当該入力データに対する前記第１の訂正データを
求め始めるまで保持して、前記エラー訂正部に出力し、
前記第１の訂正データを、前記エラー訂正部が当該第１
の訂正データに対する前記第２の訂正データを求め始め
るまで保持して、前記エラー訂正部に出力するデータ記
憶部を更に備えたものである。
の復号装置において、前記入力データを、前記エラー訂
正部が当該入力データに対する前記第１の訂正データを
求め始めるまで保持して、前記エラー訂正部に出力し、
前記第１の訂正データを、前記エラー訂正部が当該第１
の訂正データに対する前記第２の訂正データを求め始め
るまで保持して、前記エラー訂正部に出力するデータ記
憶部を更に備えたものである。
【００３０】請求項８の発明によると、エラー訂正部に
必要なデータを適切なタイミングで供給できる。また、
１つの受信語に関しては、入力データ又はこの入力デー
タから生成された第１の訂正データのいずれか一方を記
憶すればよいので、データ記憶部の容量を小さくするこ
とができる。
必要なデータを適切なタイミングで供給できる。また、
１つの受信語に関しては、入力データ又はこの入力デー
タから生成された第１の訂正データのいずれか一方を記
憶すればよいので、データ記憶部の容量を小さくするこ
とができる。
【００３１】また、請求項９の発明は、復号方法とし
て、拡大リードソロモン符号からなる受信語に対する誤
りの位置と誤りの大きさとを求め、前記誤りの位置と前
記誤りの大きさとを用いて当該受信語に誤り訂正処理を
行って、訂正データを生成する工程と、生成した訂正デ
ータについて、シンドロームを算出して、得られたシン
ドロームに基づいて誤りの有無を判定し、誤りがない訂
正データが生成された場合は、当該訂正データを求める
べき訂正データとして決定する一方、誤りがない訂正デ
ータが生成できない場合は、当該訂正データに基づい
て、これに対応した前記誤りの位置及び前記誤りの大き
さを用いて誤り訂正前の受信語を復元して、求めるべき
訂正データとして決定する訂正データ決定工程とを備え
たものである。
て、拡大リードソロモン符号からなる受信語に対する誤
りの位置と誤りの大きさとを求め、前記誤りの位置と前
記誤りの大きさとを用いて当該受信語に誤り訂正処理を
行って、訂正データを生成する工程と、生成した訂正デ
ータについて、シンドロームを算出して、得られたシン
ドロームに基づいて誤りの有無を判定し、誤りがない訂
正データが生成された場合は、当該訂正データを求める
べき訂正データとして決定する一方、誤りがない訂正デ
ータが生成できない場合は、当該訂正データに基づい
て、これに対応した前記誤りの位置及び前記誤りの大き
さを用いて誤り訂正前の受信語を復元して、求めるべき
訂正データとして決定する訂正データ決定工程とを備え
たものである。
【００３２】請求項１又は９の発明によると、受信語に
対し、最終的に誤りがない訂正データが生成できないと
判定した場合には、正しく訂正されなかったデータを出
力しないようにすることができる。
対し、最終的に誤りがない訂正データが生成できないと
判定した場合には、正しく訂正されなかったデータを出
力しないようにすることができる。
【００３３】また、請求項１０の発明は、請求項９に記
載の復号方法において、前記訂正データ決定工程では、
前記受信語から生成した訂正データに誤りが存在すると
きは、誤りがない訂正データが生成できないと判定する
ものである。
載の復号方法において、前記訂正データ決定工程では、
前記受信語から生成した訂正データに誤りが存在すると
きは、誤りがない訂正データが生成できないと判定する
ものである。
【００３４】請求項２又は１０の発明によると、訂正デ
ータに誤りが存在するときは、それ以上誤り訂正を行う
ことなく、誤りがない訂正データが生成できないと判定
して、誤り訂正前の受信語を復元して出力することがで
きる。
ータに誤りが存在するときは、それ以上誤り訂正を行う
ことなく、誤りがない訂正データが生成できないと判定
して、誤り訂正前の受信語を復元して出力することがで
きる。
【００３５】
【発明の実施の形態】以下、本発明の一実施形態につい
て、図面を参照しながら説明する。
て、図面を参照しながら説明する。
【００３６】図１は本実施形態に係るリードソロモン復
号装置の構成を示すブロック図である。図１のリードソ
ロモン復号装置は、シンドローム計算部１０と、評価多
項式・位置多項式導出部２０と、チェンサーチ部３０
と、エラー訂正部４０と、データ記憶部５０とを備えて
いる。シンドローム計算部１０、評価多項式・位置多項
式導出部２０、チェンサーチ部３０及びエラー訂正部４
０は、訂正処理部として動作する。
号装置の構成を示すブロック図である。図１のリードソ
ロモン復号装置は、シンドローム計算部１０と、評価多
項式・位置多項式導出部２０と、チェンサーチ部３０
と、エラー訂正部４０と、データ記憶部５０とを備えて
いる。シンドローム計算部１０、評価多項式・位置多項
式導出部２０、チェンサーチ部３０及びエラー訂正部４
０は、訂正処理部として動作する。
【００３７】図１のリードソロモン復号装置は、拡大リ
ードソロモン符号からなる受信語を入力データＤＩと
し、これを復号して第２の訂正データＣ２として出力す
るものである。以下では例として、入力される拡大リー
ドソロモン符号は、ガロア体ＧＦ（２7）上の１次拡大
リードソロモン符号であって、１シンボルのビット数ｍ
＝７、符号長ｎ＝１２８であるとする。受信語１語は１
２８シンボルで構成されている。また、誤り訂正数ｔ＝
３であるものとして説明する。したがって、この拡大リ
ードソロモン符号は、３シンボルの誤り訂正が可能であ
る。
ードソロモン符号からなる受信語を入力データＤＩと
し、これを復号して第２の訂正データＣ２として出力す
るものである。以下では例として、入力される拡大リー
ドソロモン符号は、ガロア体ＧＦ（２7）上の１次拡大
リードソロモン符号であって、１シンボルのビット数ｍ
＝７、符号長ｎ＝１２８であるとする。受信語１語は１
２８シンボルで構成されている。また、誤り訂正数ｔ＝
３であるものとして説明する。したがって、この拡大リ
ードソロモン符号は、３シンボルの誤り訂正が可能であ
る。
【００３８】図２は、図１のリードソロモン復号装置に
おける処理を説明するフローチャートである。以下で
は、図１及び図２のステップＳ１〜Ｓ１１を参照しなが
ら説明する。受信語には、受信語中の位置ｊｕのシンボ
ルに大きさがｅuの誤りが生じているとする。ただし、
ｕ＝１，２，…，ｋ（ｋ≦ｔ）である。このような受信
語中の誤りシンボルの位置ｊｕを誤りの位置という。
おける処理を説明するフローチャートである。以下で
は、図１及び図２のステップＳ１〜Ｓ１１を参照しなが
ら説明する。受信語には、受信語中の位置ｊｕのシンボ
ルに大きさがｅuの誤りが生じているとする。ただし、
ｕ＝１，２，…，ｋ（ｋ≦ｔ）である。このような受信
語中の誤りシンボルの位置ｊｕを誤りの位置という。
【００３９】シンドローム計算部１０及びデータ記憶部
５０には、入力データＤＩが入力される。データ記憶部
５０は、入力データＤＩを記憶してエラー訂正部４０に
出力する。
５０には、入力データＤＩが入力される。データ記憶部
５０は、入力データＤＩを記憶してエラー訂正部４０に
出力する。
【００４０】ステップＳ１では、シンドローム計算部１
０は、入力データＤＩのシンドロームを入力データシン
ドロームＳＩとして算出する。
０は、入力データＤＩのシンドロームを入力データシン
ドロームＳＩとして算出する。
【００４１】ステップＳ２では、シンドローム計算部１
０は、入力データシンドロームＳＩの成分がすべて零で
あるか否かを検出する。シンドローム計算部１０は、入
力データシンドロームＳＩの成分がすべて零である場合
は入力データＤＩに誤りがないと判定し、第１のフラグ
信号としての第１の無誤り状態示唆信号Ｆ１をアクティ
ブにしてエラー訂正部４０に出力し、ステップＳ３の処
理に移る。シンドローム計算部１０は、入力データシン
ドロームＳＩの成分に零ではないものがある場合は入力
データＤＩに誤りがあると判定し、第１の無誤り状態示
唆信号Ｆ１を非アクティブにしてエラー訂正部４０に出
力し、ステップＳ４の処理に移る。いずれの場合も、シ
ンドローム計算部１０は、入力データシンドロームＳＩ
を評価多項式・位置多項式導出部２０に出力する。
０は、入力データシンドロームＳＩの成分がすべて零で
あるか否かを検出する。シンドローム計算部１０は、入
力データシンドロームＳＩの成分がすべて零である場合
は入力データＤＩに誤りがないと判定し、第１のフラグ
信号としての第１の無誤り状態示唆信号Ｆ１をアクティ
ブにしてエラー訂正部４０に出力し、ステップＳ３の処
理に移る。シンドローム計算部１０は、入力データシン
ドロームＳＩの成分に零ではないものがある場合は入力
データＤＩに誤りがあると判定し、第１の無誤り状態示
唆信号Ｆ１を非アクティブにしてエラー訂正部４０に出
力し、ステップＳ４の処理に移る。いずれの場合も、シ
ンドローム計算部１０は、入力データシンドロームＳＩ
を評価多項式・位置多項式導出部２０に出力する。
【００４２】ステップＳ３では、エラー訂正部４０は、
第１の無誤り状態示唆信号Ｆ１がアクティブであること
から誤り訂正の必要がないことがわかるので、データ記
憶部５０が出力する入力データＤＩをそのまま、第１の
訂正データとしてシンドローム計算部１０及びデータ記
憶部５０に出力する。
第１の無誤り状態示唆信号Ｆ１がアクティブであること
から誤り訂正の必要がないことがわかるので、データ記
憶部５０が出力する入力データＤＩをそのまま、第１の
訂正データとしてシンドローム計算部１０及びデータ記
憶部５０に出力する。
【００４３】ステップＳ４〜Ｓ７は、第１の無誤り状態
示唆信号Ｆ１が非アクティブであり、入力データＤＩに
誤りが存在する場合の処理である。
示唆信号Ｆ１が非アクティブであり、入力データＤＩに
誤りが存在する場合の処理である。
【００４４】ステップＳ４では、評価多項式・位置多項
式導出部２０は、ユークリッド互除演算によって入力デ
ータシンドロームＳＩから誤り位置多項式σ（ｚ）及び
誤り評価多項式ω（ｚ）の各次数の係数を求め、これら
の多項式の係数をチェンサーチ部３０に出力する。
式導出部２０は、ユークリッド互除演算によって入力デ
ータシンドロームＳＩから誤り位置多項式σ（ｚ）及び
誤り評価多項式ω（ｚ）の各次数の係数を求め、これら
の多項式の係数をチェンサーチ部３０に出力する。
【００４５】評価多項式・位置多項式導出部２０は、デ
ータ保持器（図示せず）及びガロア演算器（図示せず）
を備えている。データ保持器は、入力データシンドロー
ムＳＩ及びユークリッド互除演算の中間結果を保持し、
最終的に誤り位置多項式σ（ｚ）及び誤り評価多項式ω
（ｚ）の各次数の係数を出力する。ガロア演算器は、デ
ータ保持器の出力からユークリッド互除演算を行って中
間結果を求め、データ保持器に出力する。このユークリ
ッド互除演算の詳細については、特開平１０−１３５８
４６号公報に開示されている。
ータ保持器（図示せず）及びガロア演算器（図示せず）
を備えている。データ保持器は、入力データシンドロー
ムＳＩ及びユークリッド互除演算の中間結果を保持し、
最終的に誤り位置多項式σ（ｚ）及び誤り評価多項式ω
（ｚ）の各次数の係数を出力する。ガロア演算器は、デ
ータ保持器の出力からユークリッド互除演算を行って中
間結果を求め、データ保持器に出力する。このユークリ
ッド互除演算の詳細については、特開平１０−１３５８
４６号公報に開示されている。
【００４６】なお、図１の評価多項式・位置多項式導出
部２０は、ユークリッド互除演算終了時に、誤り位置多
項式σ（ｚ）の次数が誤り評価多項式ω（ｚ）の次数以
下であっても、これらの多項式の係数を出力する。
部２０は、ユークリッド互除演算終了時に、誤り位置多
項式σ（ｚ）の次数が誤り評価多項式ω（ｚ）の次数以
下であっても、これらの多項式の係数を出力する。
【００４７】ステップＳ５では、チェンサーチ部３０
は、チェンサーチを行って、誤り位置多項式σ（ｚ）の
根α-juを求める。すなわち、チェンサーチ部３０は、
誤り位置多項式σ（ｚ）にガロア体ＧＦ（２7）の元を
順次代入し、誤り位置多項式σ（ｚ）の値が零となる元
をこの誤り位置多項式σ（ｚ）の根α-juとして求め、
エラー訂正部４０に出力する。この際、チェンサーチ部
３０は、誤り位置多項式σ（ｚ）がガロア体ＧＦ
（２7）に持つ互いに異なる根の数がこの誤り位置多項
式σ（ｚ）の次数未満の場合であっても、誤り訂正が可
能か否かを判断せず、根α-juをエラー訂正部４０に出
力する。誤り位置多項式σ（ｚ）の根α-juのそれぞれ
には、誤りの位置ｊｕが対応している。
は、チェンサーチを行って、誤り位置多項式σ（ｚ）の
根α-juを求める。すなわち、チェンサーチ部３０は、
誤り位置多項式σ（ｚ）にガロア体ＧＦ（２7）の元を
順次代入し、誤り位置多項式σ（ｚ）の値が零となる元
をこの誤り位置多項式σ（ｚ）の根α-juとして求め、
エラー訂正部４０に出力する。この際、チェンサーチ部
３０は、誤り位置多項式σ（ｚ）がガロア体ＧＦ
（２7）に持つ互いに異なる根の数がこの誤り位置多項
式σ（ｚ）の次数未満の場合であっても、誤り訂正が可
能か否かを判断せず、根α-juをエラー訂正部４０に出
力する。誤り位置多項式σ（ｚ）の根α-juのそれぞれ
には、誤りの位置ｊｕが対応している。
【００４８】また、チェンサーチ部３０は、誤り評価多
項式ω（ｚ）に誤り位置多項式σ（ｚ）の根α-juのそ
れぞれを代入して誤りの評価値ω（α-ju）を求めると
ともに、誤り位置多項式σ（ｚ）の導関数に誤り位置多
項式σ（ｚ）の根α-juのそれぞれを代入して誤り位置
多項式微分値σ'（α-ju）を求める。チェンサーチ部３
０は、誤りの評価値ω（α-ju）及び誤り位置多項式微
分値σ'（α-ju）を評価多項式・位置多項式導出部２０
に出力する。
項式ω（ｚ）に誤り位置多項式σ（ｚ）の根α-juのそ
れぞれを代入して誤りの評価値ω（α-ju）を求めると
ともに、誤り位置多項式σ（ｚ）の導関数に誤り位置多
項式σ（ｚ）の根α-juのそれぞれを代入して誤り位置
多項式微分値σ'（α-ju）を求める。チェンサーチ部３
０は、誤りの評価値ω（α-ju）及び誤り位置多項式微
分値σ'（α-ju）を評価多項式・位置多項式導出部２０
に出力する。
【００４９】ステップＳ６では、評価多項式・位置多項
式導出部２０におけるガロア演算器（図示せず）が、誤
りの評価値ω（α-ju）を対応する誤り位置多項式微分
値σ'（α-ju）で除算して、誤りの位置ｊｕのそれぞれ
のシンボル中の誤りビットを示す誤りの大きさｅuを求
め、エラー訂正部４０に出力する。
式導出部２０におけるガロア演算器（図示せず）が、誤
りの評価値ω（α-ju）を対応する誤り位置多項式微分
値σ'（α-ju）で除算して、誤りの位置ｊｕのそれぞれ
のシンボル中の誤りビットを示す誤りの大きさｅuを求
め、エラー訂正部４０に出力する。
【００５０】ステップＳ７では、エラー訂正部４０は、
チェンサーチ部３０が出力する誤り位置多項式σ（ｚ）
の根α-juのそれぞれに対応した誤りの位置ｊｕと、評
価多項式・位置多項式導出部２０が出力する誤りの大き
さｅuとに基づいて、データ記憶部５０が出力する入力
データＤＩに対して誤り訂正処理を行う。すなわち、入
力データＤＩである受信語の誤りの位置ｊｕのシンボル
から、それに対応した誤りの大きさｅuを減算する。ガ
ロア体ＧＦ（２）の拡大体上での演算であるので、誤り
の大きさｅuを減算する代わりに加算してもよい。
チェンサーチ部３０が出力する誤り位置多項式σ（ｚ）
の根α-juのそれぞれに対応した誤りの位置ｊｕと、評
価多項式・位置多項式導出部２０が出力する誤りの大き
さｅuとに基づいて、データ記憶部５０が出力する入力
データＤＩに対して誤り訂正処理を行う。すなわち、入
力データＤＩである受信語の誤りの位置ｊｕのシンボル
から、それに対応した誤りの大きさｅuを減算する。ガ
ロア体ＧＦ（２）の拡大体上での演算であるので、誤り
の大きさｅuを減算する代わりに加算してもよい。
【００５１】エラー訂正部４０は、誤り訂正処理後のデ
ータを第１の訂正データＣ１としてシンドローム計算部
１０及びデータ記憶部５０に出力する。データ記憶部５
０は、第１の訂正データＣ１を記憶し、これをエラー訂
正部４０に再び出力する。
ータを第１の訂正データＣ１としてシンドローム計算部
１０及びデータ記憶部５０に出力する。データ記憶部５
０は、第１の訂正データＣ１を記憶し、これをエラー訂
正部４０に再び出力する。
【００５２】ステップＳ８では、シンドローム計算部１
０は、第１の訂正データＣ１のシンドロームを訂正デー
タシンドロームＳＣとして算出する。
０は、第１の訂正データＣ１のシンドロームを訂正デー
タシンドロームＳＣとして算出する。
【００５３】ステップＳ９では、シンドローム計算部１
０は、訂正データシンドロームＳＣの成分がすべて零で
あるか否かを検出する。シンドローム計算部１０は、訂
正データシンドロームＳＣの成分がすべて零である場合
は、第１の訂正データＣ１に誤りがないと判定し、第２
のフラグ信号としての第２の無誤り状態示唆信号Ｆ２を
アクティブにしてエラー訂正部４０に出力し、ステップ
Ｓ１０の処理に移る。シンドローム計算部１０は、訂正
データシンドロームＳＣの成分に零ではないものがある
場合は、第１の訂正データＣ１に誤りがあると判定し、
第２の無誤り状態示唆信号Ｆ２を非アクティブにしてエ
ラー訂正部４０に出力し、ステップＳ１１の処理に移
る。
０は、訂正データシンドロームＳＣの成分がすべて零で
あるか否かを検出する。シンドローム計算部１０は、訂
正データシンドロームＳＣの成分がすべて零である場合
は、第１の訂正データＣ１に誤りがないと判定し、第２
のフラグ信号としての第２の無誤り状態示唆信号Ｆ２を
アクティブにしてエラー訂正部４０に出力し、ステップ
Ｓ１０の処理に移る。シンドローム計算部１０は、訂正
データシンドロームＳＣの成分に零ではないものがある
場合は、第１の訂正データＣ１に誤りがあると判定し、
第２の無誤り状態示唆信号Ｆ２を非アクティブにしてエ
ラー訂正部４０に出力し、ステップＳ１１の処理に移
る。
【００５４】ステップＳ１０では、エラー訂正部４０
は、第２の無誤り状態示唆信号Ｆ２がアクティブである
ことから第１の訂正データＣ１に誤りがないことがわか
るので、データ記憶部５０が出力する第１の訂正データ
Ｃ１をそのまま、第２の訂正データＣ２として出力す
る。
は、第２の無誤り状態示唆信号Ｆ２がアクティブである
ことから第１の訂正データＣ１に誤りがないことがわか
るので、データ記憶部５０が出力する第１の訂正データ
Ｃ１をそのまま、第２の訂正データＣ２として出力す
る。
【００５５】ステップＳ１１では、エラー訂正部４０
は、第２の無誤り状態示唆信号Ｆ２が非アクティブであ
ることから第１の訂正データＣ１に誤りがあることがわ
かるので、チェンサーチ部３０が出力する誤り位置多項
式σ（ｚ）の根α-juのそれぞれに対応した誤りの位置
ｊｕと、評価多項式・位置多項式導出部２０が出力する
誤りの大きさｅuとに基づいて、データ記憶部５０が出
力する第１の訂正データＣ１を訂正処理前の入力データ
ＤＩに復元する処理を行う。すなわち、第１の訂正デー
タＣ１の誤りの位置ｊｕのシンボルに対して、それに対
応した誤りの大きさｅuを加算又は減算する。エラー訂
正部４０は、復元して得られた入力データＤＩを第２の
訂正データＣ２として出力する。
は、第２の無誤り状態示唆信号Ｆ２が非アクティブであ
ることから第１の訂正データＣ１に誤りがあることがわ
かるので、チェンサーチ部３０が出力する誤り位置多項
式σ（ｚ）の根α-juのそれぞれに対応した誤りの位置
ｊｕと、評価多項式・位置多項式導出部２０が出力する
誤りの大きさｅuとに基づいて、データ記憶部５０が出
力する第１の訂正データＣ１を訂正処理前の入力データ
ＤＩに復元する処理を行う。すなわち、第１の訂正デー
タＣ１の誤りの位置ｊｕのシンボルに対して、それに対
応した誤りの大きさｅuを加算又は減算する。エラー訂
正部４０は、復元して得られた入力データＤＩを第２の
訂正データＣ２として出力する。
【００５６】図３は、図１のシンドローム計算部１０の
構成を示すブロック図である。図３のシンドローム計算
部１０は、セレクタ１１と、シンドローム演算器１２
と、入力データシンドローム保持器１３と、訂正データ
シンドローム保持器１４と、第１のシンドローム零検出
器１５と、第２のシンドローム零検出器１６とを備えて
いる。
構成を示すブロック図である。図３のシンドローム計算
部１０は、セレクタ１１と、シンドローム演算器１２
と、入力データシンドローム保持器１３と、訂正データ
シンドローム保持器１４と、第１のシンドローム零検出
器１５と、第２のシンドローム零検出器１６とを備えて
いる。
【００５７】セレクタ１１には、入力データＤＩ及び第
１の訂正データＣ１が入力されており、セレクタ１１
は、これらを交互にシンドローム演算器１２に出力す
る。シンドローム演算器１２は、セレクタ１１と同期し
て動作しており、入力データシンドロームＳＩを求める
計算と訂正データシンドロームＳＣを求める計算とを交
互に行い、計算結果を入力データシンドローム保持器１
３と訂正データシンドローム保持器１４とに出力する。
１の訂正データＣ１が入力されており、セレクタ１１
は、これらを交互にシンドローム演算器１２に出力す
る。シンドローム演算器１２は、セレクタ１１と同期し
て動作しており、入力データシンドロームＳＩを求める
計算と訂正データシンドロームＳＣを求める計算とを交
互に行い、計算結果を入力データシンドローム保持器１
３と訂正データシンドローム保持器１４とに出力する。
【００５８】入力データシンドローム保持器１３は、シ
ンドローム演算器１２の出力のうち入力データシンドロ
ームＳＩのみを取り込んで保持した後、第１のシンドロ
ーム零検出器１５に出力する。第１のシンドローム零検
出器１５は、入力データシンドロームＳＩの成分がすべ
て零の場合は、入力データＤＩに誤りが存在しないと判
定し、第１の無誤り状態示唆信号Ｆ１をアクティブにす
るとともに、入力データシンドロームＳＩの成分に零で
ないものがある場合は、入力データＤＩに誤りが存在す
ると判定し、第１の無誤り状態示唆信号Ｆ１を非アクテ
ィブにして、エラー訂正部４０に出力する。また、入力
データシンドローム保持器１３は、第１のシンドローム
零検出器１５が第１の無誤り状態示唆信号Ｆ１を出力す
るタイミングに同期して、入力データシンドロームＳＩ
を評価多項式・位置多項式導出部２０に出力する。
ンドローム演算器１２の出力のうち入力データシンドロ
ームＳＩのみを取り込んで保持した後、第１のシンドロ
ーム零検出器１５に出力する。第１のシンドローム零検
出器１５は、入力データシンドロームＳＩの成分がすべ
て零の場合は、入力データＤＩに誤りが存在しないと判
定し、第１の無誤り状態示唆信号Ｆ１をアクティブにす
るとともに、入力データシンドロームＳＩの成分に零で
ないものがある場合は、入力データＤＩに誤りが存在す
ると判定し、第１の無誤り状態示唆信号Ｆ１を非アクテ
ィブにして、エラー訂正部４０に出力する。また、入力
データシンドローム保持器１３は、第１のシンドローム
零検出器１５が第１の無誤り状態示唆信号Ｆ１を出力す
るタイミングに同期して、入力データシンドロームＳＩ
を評価多項式・位置多項式導出部２０に出力する。
【００５９】同様に、訂正データシンドローム保持器１
４は、シンドローム演算器１２の出力のうち訂正データ
シンドロームＳＣのみを取り込んで保持した後、第２の
シンドローム零検出器１６に出力する。第２のシンドロ
ーム零検出器１６は、訂正データシンドロームＳＣの成
分がすべて零の場合は第２の無誤り状態示唆信号Ｆ２を
アクティブにして、訂正データシンドロームＳＣの成分
に零でないものがある場合は第２の無誤り状態示唆信号
Ｆ２を非アクティブにして、エラー訂正部４０に出力す
る。
４は、シンドローム演算器１２の出力のうち訂正データ
シンドロームＳＣのみを取り込んで保持した後、第２の
シンドローム零検出器１６に出力する。第２のシンドロ
ーム零検出器１６は、訂正データシンドロームＳＣの成
分がすべて零の場合は第２の無誤り状態示唆信号Ｆ２を
アクティブにして、訂正データシンドロームＳＣの成分
に零でないものがある場合は第２の無誤り状態示唆信号
Ｆ２を非アクティブにして、エラー訂正部４０に出力す
る。
【００６０】図４は、図１のエラー訂正部４０の構成を
示すブロック図である。図４のエラー訂正部４０は、第
１のエラー訂正器４１と、誤りの位置データ保持器４２
と、誤りの大きさデータ保持器４３と、第２のエラー訂
正器４４とを備えている。
示すブロック図である。図４のエラー訂正部４０は、第
１のエラー訂正器４１と、誤りの位置データ保持器４２
と、誤りの大きさデータ保持器４３と、第２のエラー訂
正器４４とを備えている。
【００６１】第１のエラー訂正器４１には、第１の無誤
り状態示唆信号Ｆ１、データ記憶部５０が出力する入力
データＤＩ、チェンサーチ部３０が出力する誤り位置多
項式σ（ｚ）の根α-ju及び評価多項式・位置多項式導
出部２０が出力する誤りの大きさｅuが入力されてい
る。
り状態示唆信号Ｆ１、データ記憶部５０が出力する入力
データＤＩ、チェンサーチ部３０が出力する誤り位置多
項式σ（ｚ）の根α-ju及び評価多項式・位置多項式導
出部２０が出力する誤りの大きさｅuが入力されてい
る。
【００６２】第１のエラー訂正器４１は、第１の無誤り
状態示唆信号Ｆ１がアクティブの場合は、入力データＤ
Ｉには誤り訂正の必要がないため、入力データＤＩをそ
のまま第１の訂正データＣ１として出力する。また、第
１のエラー訂正器４１は、第１の無誤り状態示唆信号Ｆ
１が非アクティブの場合は、入力データＤＩは誤りを含
み、誤り訂正の必要があるため、入力データＤＩにおい
て根α-juに対応した誤りの位置ｊｕのそれぞれが示す
シンボルに対し、その誤りの位置ｊｕに対応する誤りの
大きさｅuを減算又は加算する誤り訂正処理を行い、訂
正処理後のデータを第１の訂正データＣ１として出力す
る。第１のエラー訂正器４１は、第１の訂正データＣ１
をシンドローム計算部１０及びデータ記憶部５０に出力
する。
状態示唆信号Ｆ１がアクティブの場合は、入力データＤ
Ｉには誤り訂正の必要がないため、入力データＤＩをそ
のまま第１の訂正データＣ１として出力する。また、第
１のエラー訂正器４１は、第１の無誤り状態示唆信号Ｆ
１が非アクティブの場合は、入力データＤＩは誤りを含
み、誤り訂正の必要があるため、入力データＤＩにおい
て根α-juに対応した誤りの位置ｊｕのそれぞれが示す
シンボルに対し、その誤りの位置ｊｕに対応する誤りの
大きさｅuを減算又は加算する誤り訂正処理を行い、訂
正処理後のデータを第１の訂正データＣ１として出力す
る。第１のエラー訂正器４１は、第１の訂正データＣ１
をシンドローム計算部１０及びデータ記憶部５０に出力
する。
【００６３】誤りの位置データ保持器４２は、根α-ju
を記憶し、第２のエラー訂正器４４に出力する。誤りの
大きさデータ保持器４３は、誤りの大きさｅuを記憶
し、第２のエラー訂正器４４に出力する。
を記憶し、第２のエラー訂正器４４に出力する。誤りの
大きさデータ保持器４３は、誤りの大きさｅuを記憶
し、第２のエラー訂正器４４に出力する。
【００６４】第２のエラー訂正器４４には、第２の無誤
り状態示唆信号Ｆ２、データ記憶部５０が出力する第１
の訂正データＣ１、誤り位置多項式σ（ｚ）の根
α-ju、誤りの大きさｅuが入力されている。
り状態示唆信号Ｆ２、データ記憶部５０が出力する第１
の訂正データＣ１、誤り位置多項式σ（ｚ）の根
α-ju、誤りの大きさｅuが入力されている。
【００６５】第２のエラー訂正器４４は、第２の無誤り
状態示唆信号Ｆ２がアクティブの場合は、第１の訂正デ
ータＣ１には誤り訂正の必要がないため、第１の訂正デ
ータＣ１をそのまま第２の訂正データＣ２として出力す
る。また、第２のエラー訂正器４４は、第２の無誤り状
態示唆信号Ｆ２が非アクティブの場合は、第１の訂正デ
ータＣ１は誤りを含み、誤り訂正の必要があるため、根
α-juに対応した誤りの位置ｊｕと誤りの大きさｅuとに
基づいて、第１の訂正データＣ１を第１のエラー訂正器
４１における訂正処理前の入力データＤＩに戻す復元処
理を行う。この処理は、第１の訂正データＣ１の誤りの
位置ｊｕのそれぞれが示すシンボルに対し、その誤りの
位置ｊｕに対応する誤りの大きさｅuを加算又は減算す
ることにより行うことができる。第２のエラー訂正器４
４は、復元して得られた入力データＤＩを第２の訂正デ
ータＣ２として出力する。
状態示唆信号Ｆ２がアクティブの場合は、第１の訂正デ
ータＣ１には誤り訂正の必要がないため、第１の訂正デ
ータＣ１をそのまま第２の訂正データＣ２として出力す
る。また、第２のエラー訂正器４４は、第２の無誤り状
態示唆信号Ｆ２が非アクティブの場合は、第１の訂正デ
ータＣ１は誤りを含み、誤り訂正の必要があるため、根
α-juに対応した誤りの位置ｊｕと誤りの大きさｅuとに
基づいて、第１の訂正データＣ１を第１のエラー訂正器
４１における訂正処理前の入力データＤＩに戻す復元処
理を行う。この処理は、第１の訂正データＣ１の誤りの
位置ｊｕのそれぞれが示すシンボルに対し、その誤りの
位置ｊｕに対応する誤りの大きさｅuを加算又は減算す
ることにより行うことができる。第２のエラー訂正器４
４は、復元して得られた入力データＤＩを第２の訂正デ
ータＣ２として出力する。
【００６６】このように、第２のエラー訂正器４４は、
第１のエラー訂正器４１において訂正処理を正しく行う
ことができず、第１の訂正データＣ１が誤りを含むとき
は、第１の訂正データＣ１ではなく、復元した入力デー
タＤＩを出力する。
第１のエラー訂正器４１において訂正処理を正しく行う
ことができず、第１の訂正データＣ１が誤りを含むとき
は、第１の訂正データＣ１ではなく、復元した入力デー
タＤＩを出力する。
【００６７】図５は、図１のリードソロモン復号装置に
おける動作を説明するタイミング図である。図５の
（ａ）はシンドローム計算部１０及びデータ記憶部５０
への入力データＤＩの入力、（ｂ）はシンドローム計算
部１０での入力データシンドロームＳＩ及び訂正データ
シンドロームＳＣの計算、（ｃ）は評価多項式・位置多
項式導出部２０での誤り評価多項式ω（ｚ）、誤り位置
多項式σ（ｚ）及び誤りの大きさｅuの計算、（ｄ）は
チェンサーチ部３０でのチェンサーチ、（ｅ）はエラー
訂正部４０の第１及び第２の訂正データＣ１，Ｃ２の出
力について表している。
おける動作を説明するタイミング図である。図５の
（ａ）はシンドローム計算部１０及びデータ記憶部５０
への入力データＤＩの入力、（ｂ）はシンドローム計算
部１０での入力データシンドロームＳＩ及び訂正データ
シンドロームＳＣの計算、（ｃ）は評価多項式・位置多
項式導出部２０での誤り評価多項式ω（ｚ）、誤り位置
多項式σ（ｚ）及び誤りの大きさｅuの計算、（ｄ）は
チェンサーチ部３０でのチェンサーチ、（ｅ）はエラー
訂正部４０の第１及び第２の訂正データＣ１，Ｃ２の出
力について表している。
【００６８】図５では、Ｐ０〜Ｐ５は、それぞれ第０〜
５番目に入力されたパケットに関する処理を実行してい
ることを示し、ｓｔｏｐは動作を行っていない状態を示
している。なお、符号長ｎ＝１２８の受信語１語を１個
のパケットとして扱っている。ここでは、特にパケット
Ｐ２に関する説明を中心に行う。
５番目に入力されたパケットに関する処理を実行してい
ることを示し、ｓｔｏｐは動作を行っていない状態を示
している。なお、符号長ｎ＝１２８の受信語１語を１個
のパケットとして扱っている。ここでは、特にパケット
Ｐ２に関する説明を中心に行う。
【００６９】第１のパイプラインステージでは、シンド
ローム計算部１０及びデータ記憶部５０にパケットＰ２
が入力データＤＩとして入力される。シンドローム計算
部１０は、パケットＰ２に関する入力データシンドロー
ムＳＩを計算する（図５（ａ），（ｂ））。
ローム計算部１０及びデータ記憶部５０にパケットＰ２
が入力データＤＩとして入力される。シンドローム計算
部１０は、パケットＰ２に関する入力データシンドロー
ムＳＩを計算する（図５（ａ），（ｂ））。
【００７０】第２のパイプラインステージでは、評価多
項式・位置多項式導出部２０は、まず、第１のパイプラ
インステージで計算されたパケットＰ２に関する入力デ
ータシンドロームＳＩを用いて、誤り評価多項式ω
（ｚ）及び誤り位置多項式σ（ｚ）の各次数の係数を算
出する（図５（ｃ））。その後、チェンサーチ部３０
は、この誤り評価多項式ω（ｚ）及び誤り位置多項式σ
（ｚ）を用い、チェンサーチによってパケットＰ２に関
する誤り位置多項式σ（ｚ）の根α-ju、誤りの評価値
ω（α-ju）、及び誤り位置多項式微分値σ'（α-ju）
を算出する（図５（ｄ））。さらに、評価多項式・位置
多項式導出部２０は、パケットＰ２に関する誤りの評価
値ω（α-ju）及び誤り位置多項式微分値σ'（α-ju）
を用いて、誤りの大きさｅuを算出する（図５
（ｃ））。第２のパイプラインステージでは、評価多項
式・位置多項式導出部２０及びチェンサーチ部３０は、
一方で演算処理が行われている間は、他方は停止状態と
なっている。
項式・位置多項式導出部２０は、まず、第１のパイプラ
インステージで計算されたパケットＰ２に関する入力デ
ータシンドロームＳＩを用いて、誤り評価多項式ω
（ｚ）及び誤り位置多項式σ（ｚ）の各次数の係数を算
出する（図５（ｃ））。その後、チェンサーチ部３０
は、この誤り評価多項式ω（ｚ）及び誤り位置多項式σ
（ｚ）を用い、チェンサーチによってパケットＰ２に関
する誤り位置多項式σ（ｚ）の根α-ju、誤りの評価値
ω（α-ju）、及び誤り位置多項式微分値σ'（α-ju）
を算出する（図５（ｄ））。さらに、評価多項式・位置
多項式導出部２０は、パケットＰ２に関する誤りの評価
値ω（α-ju）及び誤り位置多項式微分値σ'（α-ju）
を用いて、誤りの大きさｅuを算出する（図５
（ｃ））。第２のパイプラインステージでは、評価多項
式・位置多項式導出部２０及びチェンサーチ部３０は、
一方で演算処理が行われている間は、他方は停止状態と
なっている。
【００７１】このような処理を行うため、評価多項式・
位置多項式導出部２０及びチェンサーチ部３０には、基
準となるクロック信号（図示せず）の４倍の周波数のク
ロック信号（図示せず）が入力されている。
位置多項式導出部２０及びチェンサーチ部３０には、基
準となるクロック信号（図示せず）の４倍の周波数のク
ロック信号（図示せず）が入力されている。
【００７２】第３のパイプラインステージでは、エラー
訂正部４０は、第２のパイプラインステージで計算され
たパケットＰ２に関する誤り位置多項式σ（ｚ）の根α
-ju及び誤りの大きさｅuを用いて、データ記憶部５０が
保持していたパケットＰ２の入力データＤＩに、必要に
応じて誤り訂正処理を行って第１の訂正データＣ１を求
める（図５（ｅ））。エラー訂正部４０は、第１の訂正
データＣ１をシンドローム計算部１０及びデータ記憶部
５０に出力する。また、第３のパイプラインステージで
は、シンドローム計算部１０は、パケットＰ２の第１の
訂正データＣ１に基づいて、訂正データシンドロームＳ
Ｃを計算する。このとき、シンドローム計算部１０及び
データ記憶部５０にはパケットＰ４が入力されており、
シンドローム計算部１０は、パケットＰ４に関する入力
データシンドロームＳＩの計算も行う（図５（ｂ））。
訂正部４０は、第２のパイプラインステージで計算され
たパケットＰ２に関する誤り位置多項式σ（ｚ）の根α
-ju及び誤りの大きさｅuを用いて、データ記憶部５０が
保持していたパケットＰ２の入力データＤＩに、必要に
応じて誤り訂正処理を行って第１の訂正データＣ１を求
める（図５（ｅ））。エラー訂正部４０は、第１の訂正
データＣ１をシンドローム計算部１０及びデータ記憶部
５０に出力する。また、第３のパイプラインステージで
は、シンドローム計算部１０は、パケットＰ２の第１の
訂正データＣ１に基づいて、訂正データシンドロームＳ
Ｃを計算する。このとき、シンドローム計算部１０及び
データ記憶部５０にはパケットＰ４が入力されており、
シンドローム計算部１０は、パケットＰ４に関する入力
データシンドロームＳＩの計算も行う（図５（ｂ））。
【００７３】このように、入力データシンドロームＳＩ
及び訂正データシンドロームＳＣの計算を並行して行う
ため、シンドローム計算部１０には、基準となるクロッ
ク信号（図示せず）の２倍の周波数のクロック信号（図
示せず）が入力されている。
及び訂正データシンドロームＳＣの計算を並行して行う
ため、シンドローム計算部１０には、基準となるクロッ
ク信号（図示せず）の２倍の周波数のクロック信号（図
示せず）が入力されている。
【００７４】第４のパイプラインステージでは、エラー
訂正部４０は、パケットＰ２の第１の訂正データＣ１の
訂正データシンドロームＳＣの成分に零ではないものが
あるときは、データ記憶部５０が保持していた第１の訂
正データＣ１に対して復元処理を行って得た訂正処理前
の入力データＤＩを、また、訂正データシンドロームＳ
Ｃの成分がすべて零のときは、データ記憶部５０が保持
していた第１の訂正データＣ１をそのまま、第２の訂正
データＣ２として出力する。このとき、エラー訂正部４
０は、第２のパイプラインステージでシンドローム計算
部１０に入力されたパケットＰ３に関する誤り訂正処理
をも行って第１の訂正データＣ１を求める（図５
（ｅ））。
訂正部４０は、パケットＰ２の第１の訂正データＣ１の
訂正データシンドロームＳＣの成分に零ではないものが
あるときは、データ記憶部５０が保持していた第１の訂
正データＣ１に対して復元処理を行って得た訂正処理前
の入力データＤＩを、また、訂正データシンドロームＳ
Ｃの成分がすべて零のときは、データ記憶部５０が保持
していた第１の訂正データＣ１をそのまま、第２の訂正
データＣ２として出力する。このとき、エラー訂正部４
０は、第２のパイプラインステージでシンドローム計算
部１０に入力されたパケットＰ３に関する誤り訂正処理
をも行って第１の訂正データＣ１を求める（図５
（ｅ））。
【００７５】以上の４つのパイプラインステージで、パ
ケットＰ２に関する一連の処理が終了する。なお、エラ
ー訂正部４０及びデータ記憶部５０には、基準となるク
ロック信号（図示せず）が入力されている。
ケットＰ２に関する一連の処理が終了する。なお、エラ
ー訂正部４０及びデータ記憶部５０には、基準となるク
ロック信号（図示せず）が入力されている。
【００７６】図６は、図３に示すシンドローム計算部１
０の内部における動作を説明するタイミング図である。
図６の（ａ）はセレクタ１１への入力データＤＩの入
力、（ｂ）はセレクタ１１への第１の訂正データＣ１入
力、（ｃ）はシンドローム演算器１２でのシンドローム
計算、（ｄ）は入力データシンドローム保持器１３から
の入力データシンドロームＳＩの出力、（ｅ）は第１の
シンドローム零検出器１５からの第１の無誤り状態示唆
信号Ｆ１の出力、（ｆ）は訂正データシンドローム保持
器１４からの訂正データシンドロームＳＣの出力、
（ｇ）は第２のシンドローム零検出器１６からの第２の
無誤り状態示唆信号Ｆ２の出力について表している。図
６において、Ｐ０〜Ｐ５は、図５と同様にそれぞれ第０
〜５番目に入力されたパケットに関する処理を実行して
いることを示し、また、Ｐ２（ｎ）は、パケットＰ２に
おける第ｎ番目のシンボルに関する処理を実行している
ことを示している。
０の内部における動作を説明するタイミング図である。
図６の（ａ）はセレクタ１１への入力データＤＩの入
力、（ｂ）はセレクタ１１への第１の訂正データＣ１入
力、（ｃ）はシンドローム演算器１２でのシンドローム
計算、（ｄ）は入力データシンドローム保持器１３から
の入力データシンドロームＳＩの出力、（ｅ）は第１の
シンドローム零検出器１５からの第１の無誤り状態示唆
信号Ｆ１の出力、（ｆ）は訂正データシンドローム保持
器１４からの訂正データシンドロームＳＣの出力、
（ｇ）は第２のシンドローム零検出器１６からの第２の
無誤り状態示唆信号Ｆ２の出力について表している。図
６において、Ｐ０〜Ｐ５は、図５と同様にそれぞれ第０
〜５番目に入力されたパケットに関する処理を実行して
いることを示し、また、Ｐ２（ｎ）は、パケットＰ２に
おける第ｎ番目のシンボルに関する処理を実行している
ことを示している。
【００７７】第１のパイプラインステージでは、図６
（ａ），（ｂ）のように、図３のセレクタ１１には、第
２のパケットＰ２の入力データＤＩとして、パケットＰ
２のシンボルＰ２（１），Ｐ２（２），…，Ｐ２（ｎ）
が順に入力されるとともに、第０のパケットＰ０の第１
の訂正データＣ１として、パケットＰ０のシンボルＰ０
（１），Ｐ０（２），…，Ｐ０（ｎ）が順に入力され
る。
（ａ），（ｂ）のように、図３のセレクタ１１には、第
２のパケットＰ２の入力データＤＩとして、パケットＰ
２のシンボルＰ２（１），Ｐ２（２），…，Ｐ２（ｎ）
が順に入力されるとともに、第０のパケットＰ０の第１
の訂正データＣ１として、パケットＰ０のシンボルＰ０
（１），Ｐ０（２），…，Ｐ０（ｎ）が順に入力され
る。
【００７８】セレクタ１１は、Ｐ２（１），Ｐ０
（１），Ｐ２（２），Ｐ０（２），…，Ｐ０（ｎ）とい
うように、第２のパケットＰ２の入力データＤＩのシン
ボルと、第０のパケットＰ０の第１の訂正データＣ１の
シンボルとを交互にシンドローム演算器１２に出力す
る。シンドローム演算器１２は、セレクタ１１から入力
されたシンボルについて、入力された順にシンドローム
計算を行う（図６（ｃ））。シンドローム演算器１２
は、パケットＰ２に関する入力データＤＩの入力データ
シンドロームＳＩ及びパケットＰ０に関する第１の訂正
データＣ１の訂正データシンドロームＳＣを、それぞれ
の第ｎ番目のシンボルについての計算を終えたときに、
入力データシンドローム保持器１３及び訂正データシン
ドローム保持器１４にそれぞれ出力する。シンドローム
演算器１２は、１つのシンボルに対する演算処理を、入
力データＤＩのシンボルの入力レートの２倍のレートで
行う。
（１），Ｐ２（２），Ｐ０（２），…，Ｐ０（ｎ）とい
うように、第２のパケットＰ２の入力データＤＩのシン
ボルと、第０のパケットＰ０の第１の訂正データＣ１の
シンボルとを交互にシンドローム演算器１２に出力す
る。シンドローム演算器１２は、セレクタ１１から入力
されたシンボルについて、入力された順にシンドローム
計算を行う（図６（ｃ））。シンドローム演算器１２
は、パケットＰ２に関する入力データＤＩの入力データ
シンドロームＳＩ及びパケットＰ０に関する第１の訂正
データＣ１の訂正データシンドロームＳＣを、それぞれ
の第ｎ番目のシンボルについての計算を終えたときに、
入力データシンドローム保持器１３及び訂正データシン
ドローム保持器１４にそれぞれ出力する。シンドローム
演算器１２は、１つのシンボルに対する演算処理を、入
力データＤＩのシンボルの入力レートの２倍のレートで
行う。
【００７９】第２のパイプラインステージでは、入力デ
ータシンドローム保持器１３は、パケットＰ２に関する
入力データシンドロームＳＩを第１のシンドローム零検
出器１５に出力する（図６（ｄ））。訂正データシンド
ローム保持器１４は、パケットＰ０に関する訂正データ
シンドロームＳＣを第２のシンドローム零検出器１６に
出力する（図６（ｆ））。
ータシンドローム保持器１３は、パケットＰ２に関する
入力データシンドロームＳＩを第１のシンドローム零検
出器１５に出力する（図６（ｄ））。訂正データシンド
ローム保持器１４は、パケットＰ０に関する訂正データ
シンドロームＳＣを第２のシンドローム零検出器１６に
出力する（図６（ｆ））。
【００８０】また、第２のパイプラインステージでは、
第１のシンドローム零検出器１５は、パケットＰ２に関
する入力データシンドロームＳＩの成分がすべて零か否
かを検出した結果を第１の無誤り状態示唆信号Ｆ１とし
て出力する。例えば、この入力データシンドロームＳＩ
の成分がすべて零であり、パケットＰ２に誤りがないと
きは、第１のシンドローム零検出器１５は、第１の無誤
り状態示唆信号Ｆ１をアクティブにして出力する（図６
（ｅ））。同様に、第２のシンドローム零検出器１６
は、パケットＰ０に関する訂正データシンドロームＳＣ
の成分がすべて零か否かを検出した結果を第２の無誤り
状態示唆信号Ｆ２として出力する（図６（ｇ））。
第１のシンドローム零検出器１５は、パケットＰ２に関
する入力データシンドロームＳＩの成分がすべて零か否
かを検出した結果を第１の無誤り状態示唆信号Ｆ１とし
て出力する。例えば、この入力データシンドロームＳＩ
の成分がすべて零であり、パケットＰ２に誤りがないと
きは、第１のシンドローム零検出器１５は、第１の無誤
り状態示唆信号Ｆ１をアクティブにして出力する（図６
（ｅ））。同様に、第２のシンドローム零検出器１６
は、パケットＰ０に関する訂正データシンドロームＳＣ
の成分がすべて零か否かを検出した結果を第２の無誤り
状態示唆信号Ｆ２として出力する（図６（ｇ））。
【００８１】第３のパイプラインステージでは、第１の
パイプラインステージと同様に、シンドローム演算器１
２は、パケットＰ４に関する入力データシンドロームＳ
Ｉ及びパケットＰ２に関する訂正データシンドロームＳ
Ｃを算出する（図６（ｃ））。
パイプラインステージと同様に、シンドローム演算器１
２は、パケットＰ４に関する入力データシンドロームＳ
Ｉ及びパケットＰ２に関する訂正データシンドロームＳ
Ｃを算出する（図６（ｃ））。
【００８２】第４のパイプラインステージでは、第１の
シンドローム零検出器１５は、パケットＰ４に関する入
力データシンドロームＳＩが零か否かを検出した結果を
第１の無誤り状態示唆信号Ｆ１として出力する（図６
（ｅ））。第２のシンドローム零検出器１６は、パケッ
トＰ２に関する訂正データシンドロームＳＣが零か否か
を検出した結果を第２の無誤り状態示唆信号Ｆ２として
出力する（図６（ｇ））。このように、シンドローム計
算部１０は、４つのパイプラインステージで１つのパケ
ットに関する処理を終了する。
シンドローム零検出器１５は、パケットＰ４に関する入
力データシンドロームＳＩが零か否かを検出した結果を
第１の無誤り状態示唆信号Ｆ１として出力する（図６
（ｅ））。第２のシンドローム零検出器１６は、パケッ
トＰ２に関する訂正データシンドロームＳＣが零か否か
を検出した結果を第２の無誤り状態示唆信号Ｆ２として
出力する（図６（ｇ））。このように、シンドローム計
算部１０は、４つのパイプラインステージで１つのパケ
ットに関する処理を終了する。
【００８３】以上のように、本発明に係る復号装置は、
入力データＤＩに誤り訂正処理を施した後、誤り訂正さ
れたデータＣ１に対して、再度シンドローム計算を行っ
て訂正データシンドロームＳＣを求め、誤訂正を行った
と考えられる場合は誤り訂正前の入力データＤＩを出力
するため、誤った訂正データを出力することを避けるこ
とができる。
入力データＤＩに誤り訂正処理を施した後、誤り訂正さ
れたデータＣ１に対して、再度シンドローム計算を行っ
て訂正データシンドロームＳＣを求め、誤訂正を行った
と考えられる場合は誤り訂正前の入力データＤＩを出力
するため、誤った訂正データを出力することを避けるこ
とができる。
【００８４】なお、以上の実施形態では、誤り訂正を１
回行った後にのみ、生成した訂正データに誤りが含まれ
るか否かの判定を行ったが、誤り訂正を複数回行った後
にも判定することとしてもよい。すなわち、入力データ
ＤＩを記憶しておき、訂正データに誤りが検出されなく
なるまで誤り訂正を繰り返し、誤りがない訂正データが
生成された場合は、その訂正データを出力し、誤り訂正
を所定の回数繰り返しても誤りがない訂正データが生成
されない場合は、誤りがない訂正データが生成できない
と判定し、訂正前の受信語である記憶しておいた入力デ
ータＤＩを出力することとしてもよい。この場合、エラ
ー訂正部４０が訂正データを出力する毎に、シンドロー
ム計算部１０は訂正データのシンドロームを求め、シン
ドロームが零か否かを判定してエラー訂正部４０に通知
するとともに、シンドロームを評価多項式・位置多項式
導出部２０に出力する必要がある。
回行った後にのみ、生成した訂正データに誤りが含まれ
るか否かの判定を行ったが、誤り訂正を複数回行った後
にも判定することとしてもよい。すなわち、入力データ
ＤＩを記憶しておき、訂正データに誤りが検出されなく
なるまで誤り訂正を繰り返し、誤りがない訂正データが
生成された場合は、その訂正データを出力し、誤り訂正
を所定の回数繰り返しても誤りがない訂正データが生成
されない場合は、誤りがない訂正データが生成できない
と判定し、訂正前の受信語である記憶しておいた入力デ
ータＤＩを出力することとしてもよい。この場合、エラ
ー訂正部４０が訂正データを出力する毎に、シンドロー
ム計算部１０は訂正データのシンドロームを求め、シン
ドロームが零か否かを判定してエラー訂正部４０に通知
するとともに、シンドロームを評価多項式・位置多項式
導出部２０に出力する必要がある。
【００８５】なお、マイクロプロセッサ等を用いること
により、本発明に係る復号装置をソフトウェアによって
実現することも可能である。
により、本発明に係る復号装置をソフトウェアによって
実現することも可能である。
【００８６】
【発明の効果】以上、本発明に係る復号装置によれば、
誤り訂正処理後のデータに対して再度シンドローム計算
を行って誤り検出を行うことから、誤訂正を防ぐことが
でき、通常のリードソロモン符号だけではなく、拡大リ
ードソロモン符号の復号が実現可能となる。
誤り訂正処理後のデータに対して再度シンドローム計算
を行って誤り検出を行うことから、誤訂正を防ぐことが
でき、通常のリードソロモン符号だけではなく、拡大リ
ードソロモン符号の復号が実現可能となる。
【図１】本実施形態に係るリードソロモン復号装置の構
成を示すブロック図である。
成を示すブロック図である。
【図２】図１のリードソロモン復号装置における処理を
説明するフローチャートである。
説明するフローチャートである。
【図３】図１のシンドローム計算部の構成を示すブロッ
ク図である。
ク図である。
【図４】図１のエラー訂正部の構成を示すブロック図で
ある。
ある。
【図５】図１のリードソロモン復号装置における動作を
説明するタイミング図である。
説明するタイミング図である。
【図６】図３に示すシンドローム計算部の内部における
動作を説明するタイミング図である。
動作を説明するタイミング図である。
１０ シンドローム計算部 １１ セレクタ １２ シンドローム演算器 １３ 入力データシンドローム保持器 １４ 訂正データシンドローム保持器 １５ 第１のシンドローム零検出器 １６ 第２のシンドローム零検出器 ２０ 評価多項式・位置多項式導出部 ３０ チェンサーチ部 ４０ エラー訂正部 ４１ 第１のエラー訂正器 ４２ 誤りの位置データ保持器 ４３ 誤りの大きさデータ保持器 ４４ 第２のエラー訂正器 ５０ データ記憶部 ＤＩ 入力データ Ｃ１ 第１の訂正データ Ｃ２ 第２の訂正データ ＳＩ 入力データシンドローム ＳＣ 訂正データシンドローム Ｆ１ 第１の無誤り状態示唆信号（第１のフラグ信号） Ｆ２ 第２の無誤り状態示唆信号（第２のフラグ信号）
フロントページの続き (56)参考文献 特開2000−349652（ＪＰ，Ａ) 特開2000−172519（ＪＰ，Ａ) 特開 平11−3573（ＪＰ，Ａ) 特開 平10−262034（ＪＰ，Ａ) 特開 平10−163882（ＪＰ，Ａ) 特開 平９−93142（ＪＰ，Ａ) 特開 平８−8760（ＪＰ，Ａ) 特開 平７−30436（ＪＰ，Ａ) 特開 平５−189257（ＪＰ，Ａ) 特開 平３−10422（ＪＰ，Ａ) 特開 平３−10421（ＪＰ，Ａ) 国際公開97／11530（ＷＯ，Ａ１) 国際公開01／73952（ＷＯ，Ａ１) (58)調査した分野(Int.Cl.7，ＤＢ名) H03M 13/00 G06F 11/10 330 H04L 1/00
Claims (10)
- 【請求項１】 拡大リードソロモン符号からなる受信語
に対する誤りの位置と誤りの大きさとを求め、前記誤り
の位置と前記誤りの大きさとを用いて当該受信語に誤り
訂正処理を行って、訂正データを生成する訂正処理部を
備え、 前記訂正処理部は、 生成した訂正データについて、シンドロームを算出し
て、得られたシンドロームに基づいて誤りの有無を判定
し、誤りがない訂正データが生成された場合は、当該訂
正データを出力する一方、誤りがない訂正データが生成
できない場合は、当該訂正データに基づいて、これに対
応した前記誤りの位置及び前記誤りの大きさを用いて誤
り訂正前の受信語を復元して出力する復号装置。 - 【請求項２】 請求項１に記載の復号装置において、 前記訂正処理部は、 前記受信語から生成した訂正データに誤りが存在すると
きは、誤りがない訂正データが生成できないと判定する
ことを特徴とする復号装置。 - 【請求項３】 拡大リードソロモン符号からなる受信語
を入力データとする復号装置であって、 前記入力データに基づいて第１の訂正データを求めるエ
ラー訂正部と、 前記入力データのシンドロームを入力データシンドロー
ムとして求め、当該入力データシンドロームに基づいて
前記入力データに誤りが存在するか否かを示す第１のフ
ラグ信号を出力するとともに、前記エラー訂正部が求め
た前記第１の訂正データに対するシンドロームを訂正デ
ータシンドロームとして求め、当該訂正データシンドロ
ームに基づいて前記第１の訂正データに誤りが存在する
か否かを示す第２のフラグ信号を出力するシンドローム
計算部と、 前記入力データシンドロームに基づいて誤り評価多項式
及び誤り位置多項式の各次数の係数を求めるとともに、
前記係数から求められた誤りの評価値及び対応する誤り
位置多項式微分値に基づいて誤りの大きさを求める評価
多項式・位置多項式導出部と、 前記係数に基づいて前記誤り位置多項式の根を求めると
ともに、前記誤り評価多項式に前記根のそれぞれを代入
して得られる誤りの評価値及び前記誤り位置多項式の導
関数に前記根のそれぞれを代入して得られる誤り位置多
項式微分値を求めるチェンサーチ部とを備え、 前記エラー訂正部は、 前記第１のフラグ信号が前記入力データに誤りが存在す
ることを示す場合は、前記根及び対応する前記誤りの大
きさに基づいて前記入力データに対して誤り訂正処理を
行って得たデータを前記第１の訂正データとして、か
つ、前記第１のフラグ信号が前記入力データに誤りが存
在しないことを示す場合は、当該入力データを前記第１
の訂正データとして、前記シンドローム計算部に出力す
るとともに、前記第２のフラグ信号が前記第１の訂正デ
ータに誤りが存在することを示す場合は、前記第１の訂
正データに対して誤り訂正処理前のデータに戻す復元処
理を行って得たデータを第２の訂正データとして出力
し、前記第２のフラグ信号が前記第１の訂正データに誤
りが存在しないことを示す場合は、当該第１の訂正デー
タを第２の訂正データとして出力するものである復号装
置。 - 【請求項４】 請求項３に記載の復号装置において、 前記シンドローム計算部は、 前記入力データ及び前記エラー訂正部が出力する前記第
１の訂正データを入力とし、これらを交互に出力するセ
レクタと、 前記セレクタが出力する前記入力データ及び前記第１の
訂正データに基づいて、前記入力データシンドローム及
び前記訂正データシンドロームをそれぞれ求めるシンド
ローム演算器と、 前記入力データシンドロームを保持して出力する入力デ
ータシンドローム保持器と、 前記訂正データシンドロームを保持して出力する訂正デ
ータシンドローム保持器と、 前記入力データシンドローム保持器が出力する前記入力
データシンドロームの成分がすべて零である場合は前記
入力データに誤りが存在しないことを示すように、そう
でない場合は前記入力データに誤りが存在することを示
すように、前記第１のフラグ信号を出力する第１のシン
ドローム零検出器と、 前記訂正データシンドローム保持器が出力する前記訂正
データシンドロームの成分がすべて零である場合は前記
第１の訂正データに誤りが存在しないことを示すよう
に、そうでない場合は前記第１の訂正データに誤りが存
在することを示すように、前記第２のフラグ信号を出力
する第２のシンドローム零検出器とを備えたことを特徴
とする復号装置。 - 【請求項５】 請求項３に記載の復号装置において、 前記評価多項式・位置多項式導出部は、 ユークリッド互除演算によって、前記入力データシンド
ロームに基づいて前記誤り評価多項式及び前記誤り位置
多項式の各次数の係数を求めて出力するものであって、 前記ユークリッド互除演算終了時に、前記誤り位置多項
式の次数が前記誤り評価多項式の次数以下であっても、
前記係数を出力することを特徴とする復号装置。 - 【請求項６】 請求項３に記載の復号装置において、 前記チェンサーチ部は、 前記誤り位置多項式に前記拡大リードソロモン符号の根
が定義されるガロア体の元を順次代入し、前記誤り位置
多項式の値が零となる元を当該誤り位置多項式の根とし
て求め、 当該誤り位置多項式の互いに異なる根の数が当該誤り位
置多項式の次数未満の場合であっても、当該誤り位置多
項式の根を出力することを特徴とする復号装置。 - 【請求項７】 請求項３に記載の復号装置において、 前記エラー訂正部は、 前記第１のフラグ信号が前記入力データに誤りが存在す
ることを示す場合は、前記入力データに対して、前記根
のそれぞれに対応する誤りの位置が示すシンボルから対
応する前記誤りの大きさを減じる誤り訂正処理を行って
得られたデータを、そうでない場合は、前記入力データ
を、それぞれ前記第１の訂正データとして出力する第１
のエラー訂正器と、 前記誤りの位置を保持して出力する誤りの位置データ保
持器と、 前記誤りの大きさを保持して出力する誤りの大きさデー
タ保持器と、 前記第２のフラグ信号が前記第１の訂正データに誤りが
存在することを示す場合は、前記第１の訂正データに対
して、前記誤りの位置が示すシンボルに対応する前記誤
りの大きさの値を加算して前記誤り訂正処理を行う前の
データに戻す復元処理を行って得られたデータを、そう
でない場合は、前記第１の訂正データを、それぞれ前記
第２の訂正データとして出力する第２のエラー訂正器と
を備えたことを特徴とする復号装置。 - 【請求項８】 請求項３に記載の復号装置において、 前記入力データを、前記エラー訂正部が当該入力データ
に対する前記第１の訂正データを求め始めるまで保持し
て、前記エラー訂正部に出力し、前記第１の訂正データ
を、前記エラー訂正部が当該第１の訂正データに対する
前記第２の訂正データを求め始めるまで保持して、前記
エラー訂正部に出力するデータ記憶部を更に備えたこと
を特徴とする復号装置。 - 【請求項９】 拡大リードソロモン符号からなる受信語
に対する誤りの位置と誤りの大きさとを求め、前記誤り
の位置と前記誤りの大きさとを用いて当該受信語に誤り
訂正処理を行って、訂正データを生成する工程と、生 成した訂正データについて、シンドロームを算出し
て、得られたシンドロームに基づいて誤りの有無を判定
し、誤りがない訂正データが生成された場合は、当該訂
正データを求めるべき訂正データとして決定する一方、
誤りがない訂正データが生成できない場合は、当該訂正
データに基づいて、これに対応した前記誤りの位置及び
前記誤りの大きさを用いて誤り訂正前の受信語を復元し
て、求めるべき訂正データとして決定する訂正データ決
定工程とを備えた復号方法。 - 【請求項１０】 請求項９に記載の復号方法において、 前記訂正データ決定工程では、 前記受信語から生成した訂正データに誤りが存在すると
きは、誤りがない訂正データが生成できないと判定する
ことを特徴とする復号方法。
Priority Applications (8)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000086831A JP3352659B2 (ja) | 2000-03-27 | 2000-03-27 | 復号装置及び復号方法 |
| PCT/JP2001/002522 WO2001073952A1 (fr) | 2000-03-27 | 2001-03-27 | Decodeur et procede de decodage |
| CNB018073700A CN1252937C (zh) | 2000-03-27 | 2001-03-27 | 解码装置以及解码方法 |
| KR10-2002-7012764A KR100526222B1 (ko) | 2000-03-27 | 2001-03-27 | 복호장치 및 복호방법 |
| TW090107313A TW486880B (en) | 2000-03-27 | 2001-03-27 | Decoding device and decoding method |
| EP01915870A EP1280281A4 (en) | 2000-03-27 | 2001-03-27 | DECODER AND DECODING METHOD |
| US10/239,953 US20030145272A1 (en) | 2000-03-27 | 2001-03-27 | Decoder and decoding method |
| US11/244,187 US20060031742A1 (en) | 2000-03-27 | 2005-10-06 | Decoding device and decoding method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000086831A JP3352659B2 (ja) | 2000-03-27 | 2000-03-27 | 復号装置及び復号方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001274694A JP2001274694A (ja) | 2001-10-05 |
| JP3352659B2 true JP3352659B2 (ja) | 2002-12-03 |
Family
ID=18602933
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000086831A Expired - Fee Related JP3352659B2 (ja) | 2000-03-27 | 2000-03-27 | 復号装置及び復号方法 |
Country Status (7)
| Country | Link |
|---|---|
| US (2) | US20030145272A1 (ja) |
| EP (1) | EP1280281A4 (ja) |
| JP (1) | JP3352659B2 (ja) |
| KR (1) | KR100526222B1 (ja) |
| CN (1) | CN1252937C (ja) |
| TW (1) | TW486880B (ja) |
| WO (1) | WO2001073952A1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100394506C (zh) * | 2003-08-20 | 2008-06-11 | 上海乐金广电电子有限公司 | 纠错装置及方法 |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6954892B2 (en) * | 2002-06-06 | 2005-10-11 | National Chiao Tung University | Method for calculating syndrome polynomial in decoding error correction codes |
| US7206993B2 (en) | 2003-03-12 | 2007-04-17 | Matsushita Electric Industrial Co., Ltd. | Method and device for decoding Reed-Solomon code or extended Reed-Solomon code |
| CN100384116C (zh) * | 2005-03-31 | 2008-04-23 | 中国科学院空间科学与应用研究中心 | 一种高速译码芯片 |
| KR100714447B1 (ko) | 2005-11-28 | 2007-05-07 | 한국전자통신연구원 | 수정 유클리드 알고리즘 연산 장치 및 그 방법과 그를이용한 리드-솔로몬 복호 장치 |
| US20070150798A1 (en) * | 2005-12-12 | 2007-06-28 | Jia-Horng Shieh | Method for decoding an ecc block and related apparatus |
| CN101453219B (zh) * | 2007-11-30 | 2012-02-08 | 无锡华润矽科微电子有限公司 | 一种钱搜索电路及利用该电路的钱搜索方法 |
| US8370727B2 (en) * | 2009-02-03 | 2013-02-05 | Silicon Motion, Inc. | Method and circuit for decoding an error correction code |
| KR101678917B1 (ko) * | 2010-09-16 | 2016-11-24 | 삼성전자주식회사 | 디코더, 이의 동작방법, 및 이를 포함하는 장치들 |
| CN102684706A (zh) * | 2012-05-16 | 2012-09-19 | 山东华芯半导体有限公司 | 并行搜索的检错纠错方法和电路 |
| US11651830B2 (en) * | 2020-07-09 | 2023-05-16 | Synopsys, Inc. | Low latency decoder for error correcting codes |
Family Cites Families (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2751415B2 (ja) * | 1989-06-07 | 1998-05-18 | キヤノン株式会社 | 誤り検出訂正回路 |
| JP3137119B2 (ja) * | 1989-06-07 | 2001-02-19 | キヤノン株式会社 | 誤り訂正装置 |
| US5280488A (en) * | 1990-11-08 | 1994-01-18 | Neal Glover | Reed-Solomon code system employing k-bit serial techniques for encoding and burst error trapping |
| WO1995012850A1 (en) * | 1993-11-04 | 1995-05-11 | Cirrus Logic, Inc. | Reed-solomon decoder |
| JPH088760A (ja) * | 1994-06-16 | 1996-01-12 | Toshiba Corp | 誤り訂正装置 |
| WO1997011530A1 (fr) * | 1995-09-20 | 1997-03-27 | Hitachi, Ltd. | Procede de decodage d'une grappe d'erreurs du code de reed-solomon et dispositif correspondant |
| JP2773701B2 (ja) * | 1995-09-25 | 1998-07-09 | 日本電気株式会社 | 誤り訂正復号装置 |
| JP3439309B2 (ja) * | 1996-11-29 | 2003-08-25 | 日本電気株式会社 | 二重伸長リードソロモン復号装置 |
| JPH10262034A (ja) * | 1997-03-19 | 1998-09-29 | Sharp Corp | 符号化及び復号化装置 |
| US5905740A (en) * | 1997-04-08 | 1999-05-18 | Seagate Technology, Inc. | Apparatus and method for error correction |
| JPH113573A (ja) * | 1997-04-15 | 1999-01-06 | Mitsubishi Electric Corp | 拡大リードソロモン符号の誤り訂正復号方法と誤り訂正復号装置、１次伸長拡大リードソロモン符号の誤り訂正方法と誤り訂正装置、および２次伸長拡大リードソロモン符号の誤り訂正方法と誤り訂正装置 |
| US5966369A (en) * | 1997-04-23 | 1999-10-12 | Eastman Kodak Company | Reducing corrugations in optical recording discs |
| JP3265273B2 (ja) * | 1998-12-02 | 2002-03-11 | 日本電気株式会社 | 誤り訂正回路 |
| JP2000349652A (ja) * | 1999-06-07 | 2000-12-15 | Hitachi Ltd | 誤り訂正手段を備えた記憶装置 |
| KR20020065788A (ko) * | 2001-02-07 | 2002-08-14 | 삼성전자 주식회사 | 엠 또는 이엠 비트 데이터 처리 겸용 리드 솔로몬 복호기및 그 복호 방법 |
| US7206993B2 (en) * | 2003-03-12 | 2007-04-17 | Matsushita Electric Industrial Co., Ltd. | Method and device for decoding Reed-Solomon code or extended Reed-Solomon code |
-
2000
- 2000-03-27 JP JP2000086831A patent/JP3352659B2/ja not_active Expired - Fee Related
-
2001
- 2001-03-27 WO PCT/JP2001/002522 patent/WO2001073952A1/ja not_active Application Discontinuation
- 2001-03-27 TW TW090107313A patent/TW486880B/zh not_active IP Right Cessation
- 2001-03-27 US US10/239,953 patent/US20030145272A1/en not_active Abandoned
- 2001-03-27 CN CNB018073700A patent/CN1252937C/zh not_active Expired - Fee Related
- 2001-03-27 KR KR10-2002-7012764A patent/KR100526222B1/ko not_active IP Right Cessation
- 2001-03-27 EP EP01915870A patent/EP1280281A4/en not_active Withdrawn
-
2005
- 2005-10-06 US US11/244,187 patent/US20060031742A1/en not_active Abandoned
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100394506C (zh) * | 2003-08-20 | 2008-06-11 | 上海乐金广电电子有限公司 | 纠错装置及方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2001073952A1 (fr) | 2001-10-04 |
| CN1439197A (zh) | 2003-08-27 |
| US20060031742A1 (en) | 2006-02-09 |
| US20030145272A1 (en) | 2003-07-31 |
| EP1280281A1 (en) | 2003-01-29 |
| CN1252937C (zh) | 2006-04-19 |
| EP1280281A4 (en) | 2005-06-15 |
| KR100526222B1 (ko) | 2005-11-02 |
| TW486880B (en) | 2002-05-11 |
| JP2001274694A (ja) | 2001-10-05 |
| KR20030036148A (ko) | 2003-05-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5099482A (en) | Apparatus for detecting uncorrectable error patterns when using Euclid's algorithm to decode Reed-Solomon (BCH) codes | |
| US6122766A (en) | Reed-Solomon decoder having a three-stage pipeline structure | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| JP3352659B2 (ja) | 復号装置及び復号方法 | |
| US4592054A (en) | Decoder with code error correcting function | |
| JP2001524274A (ja) | 短縮ファイア符号エラートラッピング復号方法および装置 | |
| EP1458105B1 (en) | Method and device for decoding of Reed-Solomon codes | |
| JP3245290B2 (ja) | 復号方法とその装置 | |
| KR100330642B1 (ko) | 오류정정방법및오류정정장치 | |
| JP2605966B2 (ja) | 誤り訂正回路 | |
| JP3248098B2 (ja) | シンドローム計算装置 | |
| JP3398560B2 (ja) | 短縮化誤り訂正復号装置 | |
| JP4854686B2 (ja) | 復号装置及び通信システム | |
| KR100192801B1 (ko) | 리드 솔로몬 디코더의 비트 에러율 측정 회로 | |
| KR100192802B1 (ko) | 리드 솔로몬 디코더의 에러값 계산 및 정정 장치 | |
| JP3099890B2 (ja) | Ｂｃｈ符号の誤り訂正装置 | |
| JP4346396B2 (ja) | リードソロモン符号又は拡大リードソロモン符号の復号方法及び復号器 | |
| JP2599001B2 (ja) | 誤り訂正処理回路 | |
| KR100192800B1 (ko) | 리드 솔로몬 디코더의 다항식 평가 시스템 및 그 방법 | |
| KR100192793B1 (ko) | 리드 솔로몬 복호기의 에러 정정기 | |
| JP2001251196A (ja) | リードソロモン復号方法及びリードソロモン復号装置 | |
| JPH10126280A (ja) | 並列処理誤り訂正復号装置 | |
| JPH1141113A (ja) | 誤り訂正装置 | |
| KR19980075609A (ko) | 정적 램을 이용한 리드 솔로몬 디코더 | |
| JP2000148522A (ja) | ユークリッド互除演算回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080920 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080920 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090920 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090920 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100920 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110920 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |