JPH0865175A - リードソロモン復号器の誤り位置検出回路 - Google Patents
リードソロモン復号器の誤り位置検出回路Info
- Publication number
- JPH0865175A JPH0865175A JP7182225A JP18222595A JPH0865175A JP H0865175 A JPH0865175 A JP H0865175A JP 7182225 A JP7182225 A JP 7182225A JP 18222595 A JP18222595 A JP 18222595A JP H0865175 A JPH0865175 A JP H0865175A
- Authority
- JP
- Japan
- Prior art keywords
- register
- contents
- registers
- counter
- sets
- 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.)
- Granted
Links
- 238000001514 detection method Methods 0.000 title claims description 3
- 238000000034 method Methods 0.000 claims abstract description 23
- 208000011580 syndromic disease Diseases 0.000 claims abstract description 18
- 238000012937 correction Methods 0.000 claims abstract description 9
- 238000007792 addition Methods 0.000 claims description 8
- 238000004364 calculation method Methods 0.000 claims description 3
- 230000003247 decreasing effect Effects 0.000 claims description 2
- 238000012545 processing Methods 0.000 description 6
- 230000005540 biological transmission Effects 0.000 description 4
- 230000007423 decrease Effects 0.000 description 4
- 230000014509 gene expression Effects 0.000 description 4
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 238000013461 design Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000006798 recombination Effects 0.000 description 1
- 238000005215 recombination Methods 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
- 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
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)
- Transmission Systems Not Characterized By The Medium Used For Transmission (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
(57)【要約】
【目的】 リードソロモン復号器のユークリッドアルゴ
リズムを実施する回路および該回路の制御法を開示す
る。 【構成】 リードソロモン誤り訂正装置において、次数
が２ｔ−１のシンドローム多項式の係数はレジスタ内に
記憶され、係数０，０，…，０，１，０はレジスタλに
記憶され、一番目の数はカウンタに記憶される。係数
１，０，…，０はレジスタＱに記憶され、複数のゼロは
レジスタμに記憶され、一番目の数を１だけ越える数は
表示レジスタに記憶される。 （ａ）レジスタの内容が表示レジスタの内容以上であれ
ば、または最後のレジスタＲの内容がゼロであれば、値
Ｑ2t-1Ｒi-1 ＋Ｒ2t-1Ｑi-1 は各レジスタＲi に記憶さ
れ、値Ｑ2t-1λi-1 ＋Ｒ2t-1λi-1 は各レジスタλi に
記憶される。 （ｂ）他方、レジスタＲとレジスタλの内容およびカウ
ンタの内容は更にレジスタＱとレジスタμと表示レジス
タに転送される。ステップ（ａ）または（ｂ）はカウン
タの内容がｔだけ減少するまで繰り返される。
リズムを実施する回路および該回路の制御法を開示す
る。 【構成】 リードソロモン誤り訂正装置において、次数
が２ｔ−１のシンドローム多項式の係数はレジスタ内に
記憶され、係数０，０，…，０，１，０はレジスタλに
記憶され、一番目の数はカウンタに記憶される。係数
１，０，…，０はレジスタＱに記憶され、複数のゼロは
レジスタμに記憶され、一番目の数を１だけ越える数は
表示レジスタに記憶される。 （ａ）レジスタの内容が表示レジスタの内容以上であれ
ば、または最後のレジスタＲの内容がゼロであれば、値
Ｑ2t-1Ｒi-1 ＋Ｒ2t-1Ｑi-1 は各レジスタＲi に記憶さ
れ、値Ｑ2t-1λi-1 ＋Ｒ2t-1λi-1 は各レジスタλi に
記憶される。 （ｂ）他方、レジスタＲとレジスタλの内容およびカウ
ンタの内容は更にレジスタＱとレジスタμと表示レジス
タに転送される。ステップ（ａ）または（ｂ）はカウン
タの内容がｔだけ減少するまで繰り返される。
Description
【０００１】
【産業上の利用分野】本発明は（電気的、無線または他
のあらゆる適当な信号による）伝送の間デジタルデータ
に生ずる誤りを訂正するためのリードソロモン復号器に
関し、より詳細には訂正されるデータと訂正値を適当な
順序で与えるリードソロモン復号器の方法と装置に関す
る。
のあらゆる適当な信号による）伝送の間デジタルデータ
に生ずる誤りを訂正するためのリードソロモン復号器に
関し、より詳細には訂正されるデータと訂正値を適当な
順序で与えるリードソロモン復号器の方法と装置に関す
る。
【０００２】
【従来の技術】リードソロモン（ＲＳ）符号化はＲＳ符
号の形で伝送するためデータのパケットを与えることか
ら成り、該データのパケットは受信機でＲＳ符号を取り
出し訂正される。ＲＳ符号は２ｔ個の異なる根を有する
次数が２ｔの生成多項式の倍数である次数がＭ−１の多
項式の係数を含むＭ個のデジタルデータの組である。Ｒ
Ｓ符号として伝送した場合、ｔ個の誤り係数まで位置が
検出され訂正できる。
号の形で伝送するためデータのパケットを与えることか
ら成り、該データのパケットは受信機でＲＳ符号を取り
出し訂正される。ＲＳ符号は２ｔ個の異なる根を有する
次数が２ｔの生成多項式の倍数である次数がＭ−１の多
項式の係数を含むＭ個のデジタルデータの組である。Ｒ
Ｓ符号として伝送した場合、ｔ個の誤り係数まで位置が
検出され訂正できる。
【０００３】更に、ＲＳ符号の係数は有限体の要素に含
まれている。伝送される係数がｎビットならば、ＧＦ
（２n ）で示す２n 要素の有限体が使用される。この有
限体では、ＲＳ符号はＮ＝２n −１までの係数を含んで
いる。
まれている。伝送される係数がｎビットならば、ＧＦ
（２n ）で示す２n 要素の有限体が使用される。この有
限体では、ＲＳ符号はＮ＝２n −１までの係数を含んで
いる。
【０００４】有限体において、二つの数の加算は二つの
数の間でビット対ビットの排他的ＯＲで表される。従っ
て、αが有限体の任意の要素であればα＋α＝０であ
る。乗算は有限体の二つの要素の積も有限体のある要素
であるように表される。このように、有限体の非ゼロの
要素は該有限体の他の非ゼロで非単位要素の累乗であ
る。Ｎ＋１個の要素の有限体で、累乗はαが有限体の非
ゼロで非単位の要素でありｉが正または負の整数の時、
モジュールＮ、すなわちαi ＝αi+N で表される。従っ
て、Ｎ＋１個の要素の有限体の非ゼロの要素は次のよう
に書けるα0 ，α1，…，αN-1 。
数の間でビット対ビットの排他的ＯＲで表される。従っ
て、αが有限体の任意の要素であればα＋α＝０であ
る。乗算は有限体の二つの要素の積も有限体のある要素
であるように表される。このように、有限体の非ゼロの
要素は該有限体の他の非ゼロで非単位要素の累乗であ
る。Ｎ＋１個の要素の有限体で、累乗はαが有限体の非
ゼロで非単位の要素でありｉが正または負の整数の時、
モジュールＮ、すなわちαi ＝αi+N で表される。従っ
て、Ｎ＋１個の要素の有限体の非ゼロの要素は次のよう
に書けるα0 ，α1，…，αN-1 。
【０００５】ＲＳ符号に基づき、データａN-2t-1，…，
ａ0 の組を伝送するため、次の多項式を構成する： ａ（ｘ）＝ａN-2t-1ｘN-2t-1＋…＋ａ1 ｘ＋ａ0
ａ0 の組を伝送するため、次の多項式を構成する： ａ（ｘ）＝ａN-2t-1ｘN-2t-1＋…＋ａ1 ｘ＋ａ0
【０００６】ｒ（ｘ）が多項式ｘ2tａ（ｘ）を生成多項
式で割った剰余である時、多項式Ａ（ｘ） Ａ（ｘ）＝ｘ2tａ（ｘ）＋ｒ（ｘ） の係数が伝送される。このように、多項式Ａ（ｘ）の係
数ＡがＲＳ符号を構成し、２ｔからＮ−１の次数に対応
する係数が送信される係数ａである。伝送においては誤
りを受け、受信された係数Ａの幾つかは誤っている。
式で割った剰余である時、多項式Ａ（ｘ） Ａ（ｘ）＝ｘ2tａ（ｘ）＋ｒ（ｘ） の係数が伝送される。このように、多項式Ａ（ｘ）の係
数ＡがＲＳ符号を構成し、２ｔからＮ−１の次数に対応
する係数が送信される係数ａである。伝送においては誤
りを受け、受信された係数Ａの幾つかは誤っている。
【０００７】誤りの訂正は次のように行なわれる。次数
が２ｔ−１のシンドローム多項式Ｓ（ｘ）（以下ではシ
ンドロームと呼ぶ）が形成され、次数ｉ（ｉ＝０，１，
…，２ｔ−１）の項の係数は次のように書ける Ｓi ＝Ａ（αi ） ここに、α0 ，α1 ，…，α2t-1は生成多項式の根であ
る。伝送に誤りが生じなければ、生成多項式の根は多項
式Ａ（ｘ）の根でもあるのでシンドロームはゼロであ
る。
が２ｔ−１のシンドローム多項式Ｓ（ｘ）（以下ではシ
ンドロームと呼ぶ）が形成され、次数ｉ（ｉ＝０，１，
…，２ｔ−１）の項の係数は次のように書ける Ｓi ＝Ａ（αi ） ここに、α0 ，α1 ，…，α2t-1は生成多項式の根であ
る。伝送に誤りが生じなければ、生成多項式の根は多項
式Ａ（ｘ）の根でもあるのでシンドロームはゼロであ
る。
【０００８】他方、誤り位置検出多項式と呼ばれ次数が
ｔ以下である多項式λ（ｘ）と、誤り訂正多項式と呼ば
れ次数がｔ未満である多項式Ｒ（ｘ）は次のようにな
る： ｘ2tγ（ｘ）＋λ（ｘ）Ｓ（ｘ）＝Ｒ（ｘ） ここに、γ（ｘ）は決定されない多項式である。
ｔ以下である多項式λ（ｘ）と、誤り訂正多項式と呼ば
れ次数がｔ未満である多項式Ｒ（ｘ）は次のようにな
る： ｘ2tγ（ｘ）＋λ（ｘ）Ｓ（ｘ）＝Ｒ（ｘ） ここに、γ（ｘ）は決定されない多項式である。
【０００９】多項式λ（ｘ）は多くてもｔ個の異なる根
を有している。もし、αr が多項式λ（ｘ）の根であれ
ば、係数ＡN-r は誤りと共に伝送される。この係数に対
する誤りは次のように表される： ｅr ＝Ｒ（αr ）／αr λ′（αr ） （１） ここに、λ′は多項式λの導関数多項式である。
を有している。もし、αr が多項式λ（ｘ）の根であれ
ば、係数ＡN-r は誤りと共に伝送される。この係数に対
する誤りは次のように表される： ｅr ＝Ｒ（αr ）／αr λ′（αr ） （１） ここに、λ′は多項式λの導関数多項式である。
【００１０】ユークリッドアルゴリズムは多項式λ
（ｘ）とＲ（ｘ）を計算するため使用される。ユークリ
ッドアルゴリズムは次の式から出発する ０ｘ2t＋１Ｓ（ｘ）＝Ｓ（ｘ） １ｘ2t＋０Ｓ（ｘ）＝ｘ2t 更に、多くとも２ｔ個のステップのそれぞれで、式の１
つを２つの式の線形結合の式と置き換えることにより新
しい系が上記の式から形成され、右辺の次数の一番高い
項が打ち消される。２つの上記の式の中で、右辺の次数
の一番低い式が残る。この操作は次数がｔ未満の右辺の
式が得られるまで同じ方法で繰り返される。右辺は多項
式Ｒ（ｘ）であり、多項式λ（ｘ）は同じ式でＳ（ｘ）
を乗じたものである。
（ｘ）とＲ（ｘ）を計算するため使用される。ユークリ
ッドアルゴリズムは次の式から出発する ０ｘ2t＋１Ｓ（ｘ）＝Ｓ（ｘ） １ｘ2t＋０Ｓ（ｘ）＝ｘ2t 更に、多くとも２ｔ個のステップのそれぞれで、式の１
つを２つの式の線形結合の式と置き換えることにより新
しい系が上記の式から形成され、右辺の次数の一番高い
項が打ち消される。２つの上記の式の中で、右辺の次数
の一番低い式が残る。この操作は次数がｔ未満の右辺の
式が得られるまで同じ方法で繰り返される。右辺は多項
式Ｒ（ｘ）であり、多項式λ（ｘ）は同じ式でＳ（ｘ）
を乗じたものである。
【００１１】１９８５年５月のＮｏ５，ｖｏｌ．Ｃ−３
４のコンピュータ関連ＩＥＥＥ会報の記事“パイプライ
ンリードソロモン復号器のＶＬＳＩ設計”には、ユーク
リッドアルゴリズムの使用例と、この例のユークリッド
アルゴリズムを実施する回路が記載されている。この回
路はアルゴリズムの各ステップを計算するため比較的複
雑なセルを必要とするため特に複雑である。更に、各計
算セルは特別な場合（例えば、ゼロ多項式の係数）を考
慮するように設計する必要がある。
４のコンピュータ関連ＩＥＥＥ会報の記事“パイプライ
ンリードソロモン復号器のＶＬＳＩ設計”には、ユーク
リッドアルゴリズムの使用例と、この例のユークリッド
アルゴリズムを実施する回路が記載されている。この回
路はアルゴリズムの各ステップを計算するため比較的複
雑なセルを必要とするため特に複雑である。更に、各計
算セルは特別な場合（例えば、ゼロ多項式の係数）を考
慮するように設計する必要がある。
【００１２】
【課題を解決するための手段】本発明の目的はユークリ
ッドアルゴリズムを実施する特に簡単な回路を提示する
ことである。
ッドアルゴリズムを実施する特に簡単な回路を提示する
ことである。
【００１３】本発明の更に他の目的はユークリッドアル
ゴリズムを実施する該回路の制御法を提示することであ
る。
ゴリズムを実施する該回路の制御法を提示することであ
る。
【００１４】本発明の実施態様において、リードソロモ
ン符号器は、次数が２ｔ−１のシンドローム多項式の係
数に対応した値と、１に等しい二番目の値を除いて全て
がゼロである値で内容がそれぞれ初期化される一番目と
二番目のレジスタの組と、一番目と二番目のレジスタの
組の出力に接続され、１で初期化される三番目の組の最
後のレジスタの値を除いてゼロである値で内容が初期化
される三番目と四番目のレジスタの組を含んでいる。
ン符号器は、次数が２ｔ−１のシンドローム多項式の係
数に対応した値と、１に等しい二番目の値を除いて全て
がゼロである値で内容がそれぞれ初期化される一番目と
二番目のレジスタの組と、一番目と二番目のレジスタの
組の出力に接続され、１で初期化される三番目の組の最
後のレジスタの値を除いてゼロである値で内容が初期化
される三番目と四番目のレジスタの組を含んでいる。
【００１５】計算回路は、一番目と二番目の組の各レジ
スタと関係を有しており、前記一番目と二番目の組の前
のレジスタの内容と三番目の組の最後のレジスタの内容
との乗算結果と、三番目と四番目の組の当該レジスタの
内容と一番目の組の最後のレジスタの乗算結果との和を
前記一番目と二番目の組の各レジスタに与えている。
スタと関係を有しており、前記一番目と二番目の組の前
のレジスタの内容と三番目の組の最後のレジスタの内容
との乗算結果と、三番目と四番目の組の当該レジスタの
内容と一番目の組の最後のレジスタの乗算結果との和を
前記一番目と二番目の組の各レジスタに与えている。
【００１６】本実施態様は更に、一番目の数と一番目の
数を１だけ越える数でそれぞれ初期化されるカウンタと
表示レジスタを含んでおり、該表示レジスタはカウンタ
出力に接続されている。
数を１だけ越える数でそれぞれ初期化されるカウンタと
表示レジスタを含んでおり、該表示レジスタはカウンタ
出力に接続されている。
【００１７】シーケンサは、（ａ）カウンタの内容が表
示レジスタの内容以上であれば、または一番目の組の最
後のレジスタの内容がゼロであれば、一番目と二番目の
レジスタの組の書き込みを行い、カウンタの内容を減少
させるため、または、（ｂ）カウンタの内容が表示レジ
スタの内容未満であり、一番目の組の最後のレジスタの
内容がゼロでなければ、一番目、二番目、三番目、四番
目のレジスタの組と表示レジスタの書き込みを行うため
与えられている。シーケンサはカウンタの内容がｔだけ
減少すると停止する。
示レジスタの内容以上であれば、または一番目の組の最
後のレジスタの内容がゼロであれば、一番目と二番目の
レジスタの組の書き込みを行い、カウンタの内容を減少
させるため、または、（ｂ）カウンタの内容が表示レジ
スタの内容未満であり、一番目の組の最後のレジスタの
内容がゼロでなければ、一番目、二番目、三番目、四番
目のレジスタの組と表示レジスタの書き込みを行うため
与えられている。シーケンサはカウンタの内容がｔだけ
減少すると停止する。
【００１８】本発明の実施態様によれば、各計算回路
は、一番目と三番目の組の最後のレジスタのビットを連
続して受けるそれぞれ一番目と二番目のラインと、二番
目のラインが１ならば一番目と二番目の組の関連レジス
タの出力を伝える一番目のゲートの組と、二番目のライ
ンが１ならば三番目と四番目の組の関連レジスタの出力
を伝える二番目のゲートの組と、一番目と二番目のゲー
トの組の出力を受ける一番目の加算器と、一番目の加算
器の出力を乗算レジスタの内容に加える二番目の加算器
と、を含んでおり、乗算レジスタの内容は左側に連続的
にシフトされ、移動子は有限体内で乗算が行なわれるよ
うに該内容と再結合される。
は、一番目と三番目の組の最後のレジスタのビットを連
続して受けるそれぞれ一番目と二番目のラインと、二番
目のラインが１ならば一番目と二番目の組の関連レジス
タの出力を伝える一番目のゲートの組と、二番目のライ
ンが１ならば三番目と四番目の組の関連レジスタの出力
を伝える二番目のゲートの組と、一番目と二番目のゲー
トの組の出力を受ける一番目の加算器と、一番目の加算
器の出力を乗算レジスタの内容に加える二番目の加算器
と、を含んでおり、乗算レジスタの内容は左側に連続的
にシフトされ、移動子は有限体内で乗算が行なわれるよ
うに該内容と再結合される。
【００１９】本発明の実施態様によれば、カウンタは表
示レジスタの出力に接続され、シーケンサはステップ
（ｂ）でカウンタの書き込みを行い、カウンタを減少さ
せる。
示レジスタの出力に接続され、シーケンサはステップ
（ｂ）でカウンタの書き込みを行い、カウンタを減少さ
せる。
【００２０】本発明の他の実施態様はリードソロモン符
号として伝送されたデータのｔ個の誤りまで訂正するに
必要な係数を決定する方法を提示している。この方法
は、次数が２ｔ−１のシンドローム多項式の係数を決定
すること、一番目のレジスタの組にシンドローム多項式
の係数を記憶し、１に等しい二番目の係数を除き全てゼ
ロである係数を二番目のレジスタの組に記憶し、カウン
タ（ｄＲ）に一番目の数を記憶すること、１に等しい最
後の係数を除き全てゼロである係数を三番目のレジスタ
の組に記憶すること、全てゼロである係数を四番目のレ
ジスタの組に記憶すること、一番目の数を１だけ越える
数を表示レジスタに記憶すること、（ａ）カウンタの内
容が表示レジスタの内容以上であれば、または一番目の
組の最後のレジスタの内容がゼロであれば、一番目と二
番目の組の前のレジスタの内容と三番目の組の最後のレ
ジスタの内容との乗算結果と、三番目と四番目の組の当
該レジスタの内容と一番目の組の最後のレジスタの乗算
結果との和を一番目と二番目の組の各レジスタに記憶
し、カウンタを減少すること、（ｂ）一番目と二番目の
レジスタの組の内容とカウンタの内容を三番目と四番目
のレジスタの組と表示レジスタに転送すること、の各ス
テップを含み、カウンタの内容がｔだけ減少するまで
（ａ）または（ｂ）のステップを繰り返し、一番目と二
番目のレジスタの組の中で誤り訂正多項式の係数と誤り
位置検出多項式の係数を読み出すことの各ステップを含
んでいる。
号として伝送されたデータのｔ個の誤りまで訂正するに
必要な係数を決定する方法を提示している。この方法
は、次数が２ｔ−１のシンドローム多項式の係数を決定
すること、一番目のレジスタの組にシンドローム多項式
の係数を記憶し、１に等しい二番目の係数を除き全てゼ
ロである係数を二番目のレジスタの組に記憶し、カウン
タ（ｄＲ）に一番目の数を記憶すること、１に等しい最
後の係数を除き全てゼロである係数を三番目のレジスタ
の組に記憶すること、全てゼロである係数を四番目のレ
ジスタの組に記憶すること、一番目の数を１だけ越える
数を表示レジスタに記憶すること、（ａ）カウンタの内
容が表示レジスタの内容以上であれば、または一番目の
組の最後のレジスタの内容がゼロであれば、一番目と二
番目の組の前のレジスタの内容と三番目の組の最後のレ
ジスタの内容との乗算結果と、三番目と四番目の組の当
該レジスタの内容と一番目の組の最後のレジスタの乗算
結果との和を一番目と二番目の組の各レジスタに記憶
し、カウンタを減少すること、（ｂ）一番目と二番目の
レジスタの組の内容とカウンタの内容を三番目と四番目
のレジスタの組と表示レジスタに転送すること、の各ス
テップを含み、カウンタの内容がｔだけ減少するまで
（ａ）または（ｂ）のステップを繰り返し、一番目と二
番目のレジスタの組の中で誤り訂正多項式の係数と誤り
位置検出多項式の係数を読み出すことの各ステップを含
んでいる。
【００２１】本発明の実施態様によれば、一番目と三番
目の組は２ｔ−１個のレジスタを含み、二番目と四番目
の組がｔ＋１個のレジスタを含んでいる。二番目の組の
一番目のレジスタが前記二番目の組の最後のレジスタの
内容から得られた和を受ける。
目の組は２ｔ−１個のレジスタを含み、二番目と四番目
の組がｔ＋１個のレジスタを含んでいる。二番目の組の
一番目のレジスタが前記二番目の組の最後のレジスタの
内容から得られた和を受ける。
【００２２】本発明の実施態様によれば、ステップ
（ｂ）において、カウンタの内容と表示レジスタの内容
が入れ替えられ、カウンタが減少する。
（ｂ）において、カウンタの内容と表示レジスタの内容
が入れ替えられ、カウンタが減少する。
【００２３】本発明の実施態様によれば、カウンタに最
初記憶される数はｔである。
初記憶される数はｔである。
【００２４】本発明の実施態様によれば、乗算結果の和
がそれぞれ、一番目の組の最後のレジスタのビットと三
番目および四番目の組のレジスタの内容を連続して一番
目の部分的な乗算を行なうこと、三番目の組の最後のレ
ジスタのビットと一番目および二番目の組のレジスタの
内容を連続して二番目の部分的な乗算を行なうこと、一
番目と二番目の部分的な乗算結果を連続的に加算し、こ
れらの加算結果を加算毎に左にシフトされるレジスタの
内容に加えること、の各ステップに基づき得られる。
がそれぞれ、一番目の組の最後のレジスタのビットと三
番目および四番目の組のレジスタの内容を連続して一番
目の部分的な乗算を行なうこと、三番目の組の最後のレ
ジスタのビットと一番目および二番目の組のレジスタの
内容を連続して二番目の部分的な乗算を行なうこと、一
番目と二番目の部分的な乗算結果を連続的に加算し、こ
れらの加算結果を加算毎に左にシフトされるレジスタの
内容に加えること、の各ステップに基づき得られる。
【００２５】
【実施例】ユークリッドアルゴリズムの実施は次の体系
の式から発生する： ０ｘ2t＋１Ｓ（ｘ）＝Ｓ（ｘ） １ｘ2t＋０Ｓ（ｘ）＝ｘ2t
の式から発生する： ０ｘ2t＋１Ｓ（ｘ）＝Ｓ（ｘ） １ｘ2t＋０Ｓ（ｘ）＝ｘ2t
【００２６】本発明によれば、レジスタの組Ｒ、レジス
タの組λ、およびカウンタｄＲはユークリッドアルゴリ
ズムを実施することにより得られる連続した体系の一番
目の式に関係している。同様に、レジスタの組Ｑ、レジ
スタの組μ、および表示レジスタｄＱは連続した体系の
二番目の式に関係している。
タの組λ、およびカウンタｄＲはユークリッドアルゴリ
ズムを実施することにより得られる連続した体系の一番
目の式に関係している。同様に、レジスタの組Ｑ、レジ
スタの組μ、および表示レジスタｄＱは連続した体系の
二番目の式に関係している。
【００２７】レジスタの組Ｒは２ｔ個のレジスタ、Ｒ
2t-1，Ｒ2t-2，…，Ｒ0 を含んでおり、一番目のそれぞ
れの式の右辺の次数の減少した項の係数に対応してい
る。レジスタの組λはλt からλ0 のｔ＋１個のレジス
タを含んでおり、一番目のそれぞれの式のＳ（ｘ）の因
子の次数の減少した項の係数に対応している。カウンタ
ｄＲは一番目のそれぞれの式の右辺の次数を示す数を含
んでいる。
2t-1，Ｒ2t-2，…，Ｒ0 を含んでおり、一番目のそれぞ
れの式の右辺の次数の減少した項の係数に対応してい
る。レジスタの組λはλt からλ0 のｔ＋１個のレジス
タを含んでおり、一番目のそれぞれの式のＳ（ｘ）の因
子の次数の減少した項の係数に対応している。カウンタ
ｄＲは一番目のそれぞれの式の右辺の次数を示す数を含
んでいる。
【００２８】同様に、レジスタＱは二番目の式のそれぞ
れの右辺に関係しており、レジスタμは二番目のそれぞ
れの式のＳ（ｘ）の因子に関係しており、表示レジスタ
ｄＱは二番目のそれぞれの式の右辺の次数に関係してい
る。
れの右辺に関係しており、レジスタμは二番目のそれぞ
れの式のＳ（ｘ）の因子に関係しており、表示レジスタ
ｄＱは二番目のそれぞれの式の右辺の次数に関係してい
る。
【００２９】最初、次数の減少する順序で、レジスタの
組Ｒはシンドロームの係数を記憶し、レジスタの組λは
数０，０，…，０，１，０を記憶し、レジスタの組Ｑは
数１，０，…，０を記憶し、レジスタの組μはゼロを記
憶する。カウンタｄＲおよびレジスタｄＱは例えばそれ
ぞれ２ｔ−１と２ｔに初期設定される。次に、この方法
によりレジスタは２ｔ−１回のステップを動作し、各ス
テップには次のステップの１つが含まれている（式の中
で、レジスタ識別子もレジスタの内容を示している）。
組Ｒはシンドロームの係数を記憶し、レジスタの組λは
数０，０，…，０，１，０を記憶し、レジスタの組Ｑは
数１，０，…，０を記憶し、レジスタの組μはゼロを記
憶する。カウンタｄＲおよびレジスタｄＱは例えばそれ
ぞれ２ｔ−１と２ｔに初期設定される。次に、この方法
によりレジスタは２ｔ−１回のステップを動作し、各ス
テップには次のステップの１つが含まれている（式の中
で、レジスタ識別子もレジスタの内容を示している）。
【００３０】（ａ）カウンタｄＲの内容がレジスタｄＱ
の内容以上であれば、またはレジスタＲ2t-1がゼロなら
ば、各レジスタＲi （ｉ＝１，２，…，２ｔ−２）の内
容は次式に従い変更される： Ｒi ＝Ｒ2t-1Ｑi-1 ＋Ｑ2t-1Ｒi-1 レジスタＲ0 の内容は一番目のステップ（ａ）で打ち消
される。
の内容以上であれば、またはレジスタＲ2t-1がゼロなら
ば、各レジスタＲi （ｉ＝１，２，…，２ｔ−２）の内
容は次式に従い変更される： Ｒi ＝Ｒ2t-1Ｑi-1 ＋Ｑ2t-1Ｒi-1 レジスタＲ0 の内容は一番目のステップ（ａ）で打ち消
される。
【００３１】同様に、各レジスタλi （ｉ＝１，２，
…，ｔ）は次式に基づき変更される： λi ＝Ｒ2t-1μi-1 ＋Ｑ2t-1λi-1 レジスタλ0 の内容はＲ2t-1μt ＋Ｑ2t-1λt と入れ替
えられる。カウンタｄＲは１だけ減少する。
…，ｔ）は次式に基づき変更される： λi ＝Ｒ2t-1μi-1 ＋Ｑ2t-1λi-1 レジスタλ0 の内容はＲ2t-1μt ＋Ｑ2t-1λt と入れ替
えられる。カウンタｄＲは１だけ減少する。
【００３２】この場合、レジスタλの内容は循環的に変
更される、すなわちレジスタλ0 はレジスタλt の内容
から計算された値を受ける。これによりレジスタの数が
抑えられる。代わりに、ｔ−１個のレジスタをレジスタ
λおよびμのそれぞれの組の左に追加することができ
る。
更される、すなわちレジスタλ0 はレジスタλt の内容
から計算された値を受ける。これによりレジスタの数が
抑えられる。代わりに、ｔ−１個のレジスタをレジスタ
λおよびμのそれぞれの組の左に追加することができ
る。
【００３３】（ｂ）他方、カウンタｄＲの内容がレジス
タｄＱの内容より小さく、レジスタＲ2t-1の内容がゼロ
でなければ、レジスタの組Ｒとレジスタの組λの内容は
レジスタの組μにそれぞれ転送され、カウンタｄＲとレ
ジスタｄＱの内容は入れ替えられる。ステップ（ｂ）の
動作も同時に行なわれる。すなわち、ステップ（ｂ）は
ステップ（ａ）のサブステップを含んでいる。
タｄＱの内容より小さく、レジスタＲ2t-1の内容がゼロ
でなければ、レジスタの組Ｒとレジスタの組λの内容は
レジスタの組μにそれぞれ転送され、カウンタｄＲとレ
ジスタｄＱの内容は入れ替えられる。ステップ（ｂ）の
動作も同時に行なわれる。すなわち、ステップ（ｂ）は
ステップ（ａ）のサブステップを含んでいる。
【００３４】この方法はカウンタｄＲがｔ未満の次数に
対応した値（この場合ｔ−１）を含む時停止する。誤り
位置検出多項式λ（ｘ）の係数はλt からλ0 のレジス
タに記憶され、誤り訂正多項式Ｒ（ｘ）の係数はＲ2t-1
からＲt のレジスタに記憶される。
対応した値（この場合ｔ−１）を含む時停止する。誤り
位置検出多項式λ（ｘ）の係数はλt からλ0 のレジス
タに記憶され、誤り訂正多項式Ｒ（ｘ）の係数はＲ2t-1
からＲt のレジスタに記憶される。
【００３５】図１はｔ＝３のリードソロモン符号におい
て次数が５のシンドロームの例に対しこの方法を使用し
た場合を示している。使用された有限体はα0 からα14
の１５個のゼロでない要素を有している。対象とするシ
ンドロームの多項式は次式の通りである： Ｓ（ｘ）＝α7 ｘ5 ＋α12ｘ4 ＋α6 ｘ3 ＋α12ｘ2 ＋
α14ｘ＋α14
て次数が５のシンドロームの例に対しこの方法を使用し
た場合を示している。使用された有限体はα0 からα14
の１５個のゼロでない要素を有している。対象とするシ
ンドロームの多項式は次式の通りである： Ｓ（ｘ）＝α7 ｘ5 ＋α12ｘ4 ＋α6 ｘ3 ＋α12ｘ2 ＋
α14ｘ＋α14
【００３６】この例は前述のコンピュータに関するＩＥ
ＥＥ会報の記事に使用されている。計算の順序を示すた
め、この記事ではα0 からα14の要素を二値を示すテー
ブルを参照している。
ＥＥ会報の記事に使用されている。計算の順序を示すた
め、この記事ではα0 からα14の要素を二値を示すテー
ブルを参照している。
【００３７】図１は円内の番号で示すように、本発明に
よる方法の連続的なステップで、レジスタＲ，Ｑ，λ，
μ，ｄＱおよびカウンタｄＲの状態を示している。レジ
スタの指標は全てのレジスタを表している（レジスタＲ
およびＱの組に対し０から５を付けており、レジスタＲ
およびＱの組において０は一番目のレジスタを、５は最
後のレジスタを示している；レジスタλおよびμの組に
対しては０から３を付けており、レジスタλおよびμの
組において０は一番目のレジスタを、３は最後のレジス
タを示している）。
よる方法の連続的なステップで、レジスタＲ，Ｑ，λ，
μ，ｄＱおよびカウンタｄＲの状態を示している。レジ
スタの指標は全てのレジスタを表している（レジスタＲ
およびＱの組に対し０から５を付けており、レジスタＲ
およびＱの組において０は一番目のレジスタを、５は最
後のレジスタを示している；レジスタλおよびμの組に
対しては０から３を付けており、レジスタλおよびμの
組において０は一番目のレジスタを、３は最後のレジス
タを示している）。
【００３８】最初のステップ０で、シンドロームの係数
α7 ，α12，α6 ，α12，α14，α14はそれぞれＲ5 か
らＲ0 のレジスタに記憶される。数０，０，１，０はλ
3 からλ0 のレジスタに記憶される；数１，０，０，
０，０，０はＱ5 からＱ0 のレジスタに記憶される；数
０，０，０，０はレジスタμに記憶される。シンドロー
ムの次数である数５はカウンタｄＲに記憶され、数６は
レジスタｄＱに記憶される。
α7 ，α12，α6 ，α12，α14，α14はそれぞれＲ5 か
らＲ0 のレジスタに記憶される。数０，０，１，０はλ
3 からλ0 のレジスタに記憶される；数１，０，０，
０，０，０はＱ5 からＱ0 のレジスタに記憶される；数
０，０，０，０はレジスタμに記憶される。シンドロー
ムの次数である数５はカウンタｄＲに記憶され、数６は
レジスタｄＱに記憶される。
【００３９】ステップ１は、カウンタｄＲの内容がレジ
スタｄＱの内容より小さく、レジスタＲ5 の内容がゼロ
でないので前述のステップ（ｂ）に対応する。（最後の
レジスタを除き）レジスタＲのそれぞれとレジスタλの
それぞれの内容には１が掛けられ、（最後のレジスタを
除き）レジスタＱのそれぞれとレジスタμのそれぞれの
内容にはα7 が掛けられる。得られた積の和は１だけ左
にシフトされた後レジスタＲの組に入れられ、１だけ左
に循環的にシフトされた後レジスタλの組に入れられ
る。同時に、レジスタＲとλの組の前の内容はレジスタ
Ｑとμの組に転送される。カウンタｄＲとレジスタｄＱ
の内容が入れ替えられる。カウンタｄＲの内容は減少
し、レジスタＲの組の新しい内容が次数５の多項式に相
当していることを示す。
スタｄＱの内容より小さく、レジスタＲ5 の内容がゼロ
でないので前述のステップ（ｂ）に対応する。（最後の
レジスタを除き）レジスタＲのそれぞれとレジスタλの
それぞれの内容には１が掛けられ、（最後のレジスタを
除き）レジスタＱのそれぞれとレジスタμのそれぞれの
内容にはα7 が掛けられる。得られた積の和は１だけ左
にシフトされた後レジスタＲの組に入れられ、１だけ左
に循環的にシフトされた後レジスタλの組に入れられ
る。同時に、レジスタＲとλの組の前の内容はレジスタ
Ｑとμの組に転送される。カウンタｄＲとレジスタｄＱ
の内容が入れ替えられる。カウンタｄＲの内容は減少
し、レジスタＲの組の新しい内容が次数５の多項式に相
当していることを示す。
【００４０】ステップ２はカウンタｄＲとレジスタｄＱ
の内容が等しいので前述のステップ（ａ）に対応してい
る。レジスタＲの組とレジスタλの組の内容にはα7 が
掛けられ、レジスタＱの組とレジスタμの組の内容には
α12が掛けられる。得られた積の和は１だけ左にシフト
された後レジスタＲの組に入れられ、１だけ左に循環的
にシフトされた後レジスタλの組に入れられる。カウン
タｄＲが減少する。レジスタＲの組の新しい内容は次数
が４の多項式に相当している。
の内容が等しいので前述のステップ（ａ）に対応してい
る。レジスタＲの組とレジスタλの組の内容にはα7 が
掛けられ、レジスタＱの組とレジスタμの組の内容には
α12が掛けられる。得られた積の和は１だけ左にシフト
された後レジスタＲの組に入れられ、１だけ左に循環的
にシフトされた後レジスタλの組に入れられる。カウン
タｄＲが減少する。レジスタＲの組の新しい内容は次数
が４の多項式に相当している。
【００４１】次のステップ３と４はそれぞれステップ
（ｂ）とステップ（ａ）に対応している。ステップ４
で、カウンタｄＲはレジスタＲの組の内容が次数３の多
項式に相当していることを示している。しかし、この多
項式は次数２と３の項の係数がゼロであるので実際には
次数１の多項式である。
（ｂ）とステップ（ａ）に対応している。ステップ４
で、カウンタｄＲはレジスタＲの組の内容が次数３の多
項式に相当していることを示している。しかし、この多
項式は次数２と３の項の係数がゼロであるので実際には
次数１の多項式である。
【００４２】理論的にこの方法は停止するが、この特別
な場合を処理するに必要な回路は不必要に複雑になる。
一般的な場合、カウンタｄＲの内容である３はｔ＝３未
満でないので更にステップが実行される。
な場合を処理するに必要な回路は不必要に複雑になる。
一般的な場合、カウンタｄＲの内容である３はｔ＝３未
満でないので更にステップが実行される。
【００４３】ステップ５はレジスタＲ5 の内容がゼロな
ので前述のステップ（ａ）に対応する。レジスタＲの組
とレジスタλの組の内容にはα10が掛けられ、レジスタ
Ｑの組とレジスタμの組の内容には０が掛けられる。和
は１だけ左にシフト（レジスタλの組の場合循環的にシ
フト）された後レジスタＲの組およびレジスタλの組に
加えられる。カウンタｄＲの内容は減少する。この方法
はカウンタｄＲがｔ＝３未満の次数を示すので停止す
る。
ので前述のステップ（ａ）に対応する。レジスタＲの組
とレジスタλの組の内容にはα10が掛けられ、レジスタ
Ｑの組とレジスタμの組の内容には０が掛けられる。和
は１だけ左にシフト（レジスタλの組の場合循環的にシ
フト）された後レジスタＲの組およびレジスタλの組に
加えられる。カウンタｄＲの内容は減少する。この方法
はカウンタｄＲがｔ＝３未満の次数を示すので停止す
る。
【００４４】ステップ５の終わりで、レジスタＲ5 から
Ｒ3 に含まれる係数は誤り訂正多項式Ｒ（ｘ）の係数で
あり、レジスタλ3 からλ0 に含まれる係数は誤り位置
検出多項式λ（ｘ）の係数である（実際には、これらの
多項式のそれぞれにはこの場合はα10である定数が掛け
られるが誤り訂正には影響を与えない）。この例の場
合、見つけられる多項式は次の通りである： Ｒ（ｘ）＝α5 ｘ＋α λ（ｘ）＝α5 ｘ2 ＋αｘ＋α2
Ｒ3 に含まれる係数は誤り訂正多項式Ｒ（ｘ）の係数で
あり、レジスタλ3 からλ0 に含まれる係数は誤り位置
検出多項式λ（ｘ）の係数である（実際には、これらの
多項式のそれぞれにはこの場合はα10である定数が掛け
られるが誤り訂正には影響を与えない）。この例の場
合、見つけられる多項式は次の通りである： Ｒ（ｘ）＝α5 ｘ＋α λ（ｘ）＝α5 ｘ2 ＋αｘ＋α2
【００４５】多項式λ（ｘ）の根はα10とα3 であり、
これは受けた係数の中で指標１５−１０＝５および１５
−３＝１２を有するものが誤っていることを示してい
る。対応する誤りはα11とα7 である。
これは受けた係数の中で指標１５−１０＝５および１５
−３＝１２を有するものが誤っていることを示してい
る。対応する誤りはα11とα7 である。
【００４６】図２は本発明による方法を実施する回路の
実施態様を示している。この回路はあらゆるリードソロ
モン符号に容易に展開できる。Ｒ2t-2からＲ0 の各レジ
スタによりその内容がそれぞれの乗算器１０に与えられ
る：λt からλ0 の各レジスタによりその内容がそれぞ
れの乗算器１２に与えられる：Ｑ2t-2からＱ0 の各レジ
スタによりその内容がそれぞれの乗算器１４に与えられ
る：μt からμ0 の各レジスタによりその内容がそれぞ
れの乗算器１６に与えられる。レジスタＲ2t-1の内容が
乗算器１４と１６の二番目の入力に加えられ、レジスタ
Ｑ2t-1の内容が乗算器１０と１２の二番目の入力に加え
られる。レジスタＲi とＱi に関係のある乗算器１０と
１４の出力がレジスタＲi+1 に加えられる加算器１８に
加えられる。レジスタλi とレジスタμi に関係のある
乗算器１２と１６の出力は出力がレジスタλi+1 または
ｉ＝ｔならλ0 に加えられる加算器２０に加えられる。
実施態様を示している。この回路はあらゆるリードソロ
モン符号に容易に展開できる。Ｒ2t-2からＲ0 の各レジ
スタによりその内容がそれぞれの乗算器１０に与えられ
る：λt からλ0 の各レジスタによりその内容がそれぞ
れの乗算器１２に与えられる：Ｑ2t-2からＱ0 の各レジ
スタによりその内容がそれぞれの乗算器１４に与えられ
る：μt からμ0 の各レジスタによりその内容がそれぞ
れの乗算器１６に与えられる。レジスタＲ2t-1の内容が
乗算器１４と１６の二番目の入力に加えられ、レジスタ
Ｑ2t-1の内容が乗算器１０と１２の二番目の入力に加え
られる。レジスタＲi とＱi に関係のある乗算器１０と
１４の出力がレジスタＲi+1 に加えられる加算器１８に
加えられる。レジスタλi とレジスタμi に関係のある
乗算器１２と１６の出力は出力がレジスタλi+1 または
ｉ＝ｔならλ0 に加えられる加算器２０に加えられる。
【００４７】レジスタＲの組はシンドロームＳの係数に
対応する初期値を受けるように接続されている。レジス
タλの組は初期値０，０，…，０，１，０を受けるよう
に接続されている。レジスタＱの組は初期値１，０，
…，０を受けるように接続されている。最後に、レジス
タμの組はリセット入力ＲＳＴを有している。レジスタ
Ｒの組とレジスタλの組はそれぞれレジスタＱの組とレ
ジスタμの組に接続されており、レジスタＲの組とレジ
スタλの組の内容はレジスタＱとμの組に伝えられる。
図２では、カウンタｄＲとレジスタｄＱがループ状にな
っている。
対応する初期値を受けるように接続されている。レジス
タλの組は初期値０，０，…，０，１，０を受けるよう
に接続されている。レジスタＱの組は初期値１，０，
…，０を受けるように接続されている。最後に、レジス
タμの組はリセット入力ＲＳＴを有している。レジスタ
Ｒの組とレジスタλの組はそれぞれレジスタＱの組とレ
ジスタμの組に接続されており、レジスタＲの組とレジ
スタλの組の内容はレジスタＱとμの組に伝えられる。
図２では、カウンタｄＲとレジスタｄＱがループ状にな
っている。
【００４８】カウンタｄＲは漸減入力ＤＥＣを有してお
り、値ｔで初期化される。同様に、レジスタｄＱは値ｔ
＋１で初期化される。この実施態様では、この方法を停
止させる時カウンタｄＲの値をｔ−１よりも０と比較し
決定することが容易であるため、カウンタｄＲは前述の
実施態様で示したようにシンドロームの次数に相当する
２ｔ−１の代わり値ｔで初期化される。
り、値ｔで初期化される。同様に、レジスタｄＱは値ｔ
＋１で初期化される。この実施態様では、この方法を停
止させる時カウンタｄＲの値をｔ−１よりも０と比較し
決定することが容易であるため、カウンタｄＲは前述の
実施態様で示したようにシンドロームの次数に相当する
２ｔ−１の代わり値ｔで初期化される。
【００４９】シーケンサ２２はレジスタＲ2t-1の内容を
０と比較し、更にカウンタｄＲの内容をレジスタｄＱの
内容と比較しステップ（ａ）またはステップ（ｂ）を選
択する。シーケンサ２２はレジスタとカウンタを制御
し、前述の動作を得る。シーケンサは、例えばＶＨＤＬ
のような論理回路記述言語で前述の方法のステップを翻
訳できる当業者により容易に理解できる。
０と比較し、更にカウンタｄＲの内容をレジスタｄＱの
内容と比較しステップ（ａ）またはステップ（ｂ）を選
択する。シーケンサ２２はレジスタとカウンタを制御
し、前述の動作を得る。シーケンサは、例えばＶＨＤＬ
のような論理回路記述言語で前述の方法のステップを翻
訳できる当業者により容易に理解できる。
【００５０】図２の回路の乗算器と加算器は対象とする
有限体に定義された乗算と加算を実行するため接続され
ている。
有限体に定義された乗算と加算を実行するため接続され
ている。
【００５１】加算（排他的ＯＲ）は二値数の加算より容
易である；しかし乗算はより複雑である。
易である；しかし乗算はより複雑である。
【００５２】積２ｎｔ（ｎは各係数のビット数）が伝送
されたリードソロモン符号の係数の数より小さければ、
加算器１８に関連した２つの乗算器を使用する代わり、
ｎサイクル中にｎビットの２つの数を掛ける１つの系列
処理乗算器を使用することができる。系列処理乗算器に
より、多項式λとＲの決定には２ｔサイクルの代わりに
２ｎｔサイクルが必要となる。これは回路が非系列処理
乗算器よりも簡単な（系列処理）乗算器を半分含んでい
るので、２ｎｔサイクルが各リードソロモン符号の処理
に利用できるならば欠点ではない。
されたリードソロモン符号の係数の数より小さければ、
加算器１８に関連した２つの乗算器を使用する代わり、
ｎサイクル中にｎビットの２つの数を掛ける１つの系列
処理乗算器を使用することができる。系列処理乗算器に
より、多項式λとＲの決定には２ｔサイクルの代わりに
２ｎｔサイクルが必要となる。これは回路が非系列処理
乗算器よりも簡単な（系列処理）乗算器を半分含んでい
るので、２ｎｔサイクルが各リードソロモン符号の処理
に利用できるならば欠点ではない。
【００５３】図３はレジスタＲi とＱi （ｉ≠２ｔ−
１）の組に関連のある系列処理乗算器を示している。レ
ジスタＲi とＱi の出力はＡＮＤゲート３０と３２の組
にそれぞれ加えられる。ゲート３０はラインｑ2t-1が１
の時、レジスタＲi の出力を乗算器３４の一番目の入力
に伝える。ゲート３２はラインｒ2t-1が１の時、レジス
タＱi の出力を加算器３４の二番目の入力に伝える。ラ
インｑ2t-1とｒ2t-1はそれぞれレジスタＱ2t-1とＲ2t-1
の重みが減少したビットを受ける。加算器３４の出力は
加算器３６によりレジスタＰi の内容に加えられる。加
算器３６の出力は次のレジスタＲi+1 に加えられ、レジ
スタＲi は前の段の加算器３６の出力を受ける。
１）の組に関連のある系列処理乗算器を示している。レ
ジスタＲi とＱi の出力はＡＮＤゲート３０と３２の組
にそれぞれ加えられる。ゲート３０はラインｑ2t-1が１
の時、レジスタＲi の出力を乗算器３４の一番目の入力
に伝える。ゲート３２はラインｒ2t-1が１の時、レジス
タＱi の出力を加算器３４の二番目の入力に伝える。ラ
インｑ2t-1とｒ2t-1はそれぞれレジスタＱ2t-1とＲ2t-1
の重みが減少したビットを受ける。加算器３４の出力は
加算器３６によりレジスタＰi の内容に加えられる。加
算器３６の出力は次のレジスタＲi+1 に加えられ、レジ
スタＲi は前の段の加算器３６の出力を受ける。
【００５４】レジスタＱ2t-1の連続したビットは、レジ
スタＲ2t-1の連続したビットがラインｒ2t-1に加えられ
るのと同時にラインｑ2t-1に加えられる。ＡＮＤゲート
３０と３２はそれぞれレジスタＲi とＱ2t-1の内容と、
レジスタＱi とＲ2t-1の内容の部分的な乗算を行なう。
加算器３４により与えられる部分的な乗算の組の和は、
和のそれぞれを左にシフトしたレジスタＰi の内容に加
えられる。レジスタＰi はレジスタＲi およびレジスタ
Ｑi と大きさが同じであり、オーバーフローした時その
移動子はレジスタＰi のビットに再結合され、対象とす
る有限体内で乗算結果を得る。前述の１６個の要素の有
限体の例では、移動子は重み０と１のビットで再結合さ
れる。
スタＲ2t-1の連続したビットがラインｒ2t-1に加えられ
るのと同時にラインｑ2t-1に加えられる。ＡＮＤゲート
３０と３２はそれぞれレジスタＲi とＱ2t-1の内容と、
レジスタＱi とＲ2t-1の内容の部分的な乗算を行なう。
加算器３４により与えられる部分的な乗算の組の和は、
和のそれぞれを左にシフトしたレジスタＰi の内容に加
えられる。レジスタＰi はレジスタＲi およびレジスタ
Ｑi と大きさが同じであり、オーバーフローした時その
移動子はレジスタＰi のビットに再結合され、対象とす
る有限体内で乗算結果を得る。前述の１６個の要素の有
限体の例では、移動子は重み０と１のビットで再結合さ
れる。
【００５５】図示のように、スイッチ３８はレジスタＲ
i の入力に置かれている。このスイッチの一番目の位置
で、レジスタＲi は前段の加算器３６の出力を受ける
（ｉ＝０ならば、値０を受ける）。信号ＩＮＩＴをイネ
ーブルにすることにより選択される二番目の位置で、レ
ジスタＲi はシンドロームの係数Ｓi を受ける。
i の入力に置かれている。このスイッチの一番目の位置
で、レジスタＲi は前段の加算器３６の出力を受ける
（ｉ＝０ならば、値０を受ける）。信号ＩＮＩＴをイネ
ーブルにすることにより選択される二番目の位置で、レ
ジスタＲi はシンドロームの係数Ｓi を受ける。
【００５６】スイッチ４０はレジスタＱi の入力に置か
れている。スイッチ４０の一番目の位置で、レジスタＱ
i はレジスタＲi の出力を受ける。信号ＩＮＩＴをイネ
ーブルにすることにより選択されるスイッチ４０の二番
目の位置で、レジスタＲi は０を受ける（またはｉ＝２
ｔ−１ならば１を受ける）。
れている。スイッチ４０の一番目の位置で、レジスタＱ
i はレジスタＲi の出力を受ける。信号ＩＮＩＴをイネ
ーブルにすることにより選択されるスイッチ４０の二番
目の位置で、レジスタＲi は０を受ける（またはｉ＝２
ｔ−１ならば１を受ける）。
【００５７】レジスタλの組およびレジスタμの組に関
係する段は同じである。
係する段は同じである。
【００５８】最初、信号ＩＮＩＴはイネーブルされる。
レジスタＲ，Ｑ，λ，μは対応した初期値（Ｓi ，０，
１）を受け、これらの値を記憶する。
レジスタＲ，Ｑ，λ，μは対応した初期値（Ｓi ，０，
１）を受け、これらの値を記憶する。
【００５９】前述のように連続したステップ（ａ），
（ｂ）が実行される。各ステップには部分乗算のｎ個の
サブステップが含まれ、この部分乗算の間シーケンサ２
２はレジスタＲ2t-1のｎビットをラインｒ2t-1に連続に
与え、同時にレジスタＱ2t-1のｎビットをラインｑ2t-1
に与える。これらのサブステップのそれぞれで、レジス
タＰは移動子の再結合により左にシフトするようにイネ
ーブルされる。
（ｂ）が実行される。各ステップには部分乗算のｎ個の
サブステップが含まれ、この部分乗算の間シーケンサ２
２はレジスタＲ2t-1のｎビットをラインｒ2t-1に連続に
与え、同時にレジスタＱ2t-1のｎビットをラインｑ2t-1
に与える。これらのサブステップのそれぞれで、レジス
タＰは移動子の再結合により左にシフトするようにイネ
ーブルされる。
【００６０】部分乗算のｎ回のサブステップのそれぞれ
の終わりで、加算器３６は最後の結果を出力する。レジ
スタの組Ｒとλのそれぞれはシーケンサによりイネーブ
ルにされこれらの結果を受ける。ステップ（ｂ）の間、
レジスタＱの組とレジスタμの組はレジスタＲの組とレ
ジスタλの組と同時にイネーブルにされレジスタＲの組
とレジスタλの組の古い値を受ける。
の終わりで、加算器３６は最後の結果を出力する。レジ
スタの組Ｒとλのそれぞれはシーケンサによりイネーブ
ルにされこれらの結果を受ける。ステップ（ｂ）の間、
レジスタＱの組とレジスタμの組はレジスタＲの組とレ
ジスタλの組と同時にイネーブルにされレジスタＲの組
とレジスタλの組の古い値を受ける。
【００６１】当業者に明らかなように、種々の変形を前
に開示した好ましい実施態様に行なうことができる。例
えば、カウンタｄＲとレジスタｄＱの内容を入れ替えカ
ウンタｄＲを減少させる代わり、カウンタを減少させる
ことなしにカウンタｄＲの内容をレジスタｄＱに転送す
ることができる。更に、この方法の終わりを検出するた
め、カウンタｄＲの内容を制御する代わり、この装置で
は２ｔ−１回のステップ（ａ）または（ｂ）を計算する
ことができる。
に開示した好ましい実施態様に行なうことができる。例
えば、カウンタｄＲとレジスタｄＱの内容を入れ替えカ
ウンタｄＲを減少させる代わり、カウンタを減少させる
ことなしにカウンタｄＲの内容をレジスタｄＱに転送す
ることができる。更に、この方法の終わりを検出するた
め、カウンタｄＲの内容を制御する代わり、この装置で
は２ｔ−１回のステップ（ａ）または（ｂ）を計算する
ことができる。
【００６２】本発明の少なくとも１つの実施態様を図に
基づき記載したが、当業者は種々の交換、変更、改善を
容易に行なうことができる。これらの交換、変更、改善
はこの発明の内容および範囲内である。従って、前述の
記載は一例でありこれらにより制限されない。
基づき記載したが、当業者は種々の交換、変更、改善を
容易に行なうことができる。これらの交換、変更、改善
はこの発明の内容および範囲内である。従って、前述の
記載は一例でありこれらにより制限されない。
【図１】本発明による方法の連続的なステップの例を表
す図である。
す図である。
【図２】本発明による方法を実施する回路の実施態様を
表す図である。
表す図である。
【図３】本発明による方法を実施する回路の他の実施態
様の部分図である。
様の部分図である。
１０、１２、１４、１６ 乗算器 １８、２０ 加算器 ２２ シーケンサ ３０、３２ ＡＮＤゲート ３４、３６ 加算器 ３８、４０ スイッチ
Claims (9)
- 【請求項１】 次数が２ｔ−１のシンドローム多項式
（Ｓ）の係数に対応した値と、１に等しい二番目の値を
除いて全てがゼロである値で内容がそれぞれ初期化され
る一番目と二番目のレジスタの組（Ｒ，λ）と、 一番目と二番目のレジスタの組の出力に接続され、１で
初期化される三番目の組の最後のレジスタの値を除いて
ゼロである値で内容が初期化される三番目と四番目のレ
ジスタの組（Ｑ，μ）と、 一番目と二番目の組の各レジスタ（Ｒi ，λi ）と関係
を有しており、前記一番目と二番目の組の前のレジスタ
（Ｒi-1 ，λi-1 ）の内容と三番目の組の最後のレジス
タ（Ｑ2t-1）の内容との乗算結果と、三番目と四番目の
組の当該レジスタ（Ｑi-1 ，μi-1 ）の内容と一番目の
組の最後のレジスタ（Ｒ2t-1）の乗算結果との和を前記
一番目と二番目の組の各レジスタ（Ｒi ，λi ）に与え
る計算回路（１０−１８）と、 一番目の数と一番目の数を１だけ越える数でそれぞれ初
期化されるカウンタ（ｄＲ）と表示レジスタ（ｄＱ）
と、を含み、該表示レジスタはカウンタ出力に接続され
ていることを特徴とし、更に （ａ）カウンタ（ｄＲ）の内容が表示レジスタ（ｄＱ）
の内容以上であれば、または一番目の組の最後のレジス
タ（Ｒ2t-1）の内容がゼロであれば、一番目と二番目の
レジスタの組の書き込みを行い、カウンタ（ｄＲ）の内
容を減少させ、 （ｂ）カウンタ（ｄＲ）の内容が表示レジスタ（ｄＱ）
の内容未満であり、一番目の組の最後のレジスタの内容
がゼロでなければ一番目、二番目、三番目、四番目のレ
ジスタの組（Ｒ，λ，Ｑ，μ）と表示レジスタ（ｄＱ）
の書き込みを行い、 カウンタの内容がｔだけ減少すると停止する、ためのシ
ーケンサ（２２）と、を含んでいるリードソロモン復号
器。 - 【請求項２】 各計算回路が、 一番目と三番目の組（Ｒ，Ｑ）の最後のレジスタのビッ
トを連続して受けるそれぞれ一番目と二番目のライン
（ｒ2t-1，ｑ2t-1）と、 二番目のラインが１ならば一番目と二番目の組の関連レ
ジスタ（Ｒi ，λi ）の出力を伝える一番目のゲートの
組（３０）と、二番目のラインが１ならば三番目と四番
目の組の関連レジスタ（Ｑi ，μi ）の出力を伝える二
番目のゲートの組（３２）と、 一番目と二番目のゲートの組（３０、３２）の出力を受
ける一番目の加算器（３４）と、 一番目の加算器の出力を乗算レジスタ（Ｐi ）の内容に
加える二番目の加算器（３６）と、を含み、乗算レジス
タの内容が左側に連続的にシフトされ、移動子は有限体
内で乗算が行なわれるように該内容と再結合されること
を特徴とする請求項１に記載のリードソロモン復号器。 - 【請求項３】 二番目の組（λ）の一番目のレジスタと
関係を有する計算回路が二番目と四番目の組の最後のレ
ジスタの内容から計算を行なう請求項１に記載のリード
ソロモン復号器。 - 【請求項４】 カウンタ（ｄＲ）が表示レジスタ（ｄ
Ｑ）の出力に接続され、シーケンサ（２２）がステップ
（ｂ）でカウンタの書き込みを行い、カウンタを減少さ
せるように動作する請求項１に記載のリードソロモン復
号器。 - 【請求項５】 次数が２ｔ−１のシンドローム多項式の
係数を決定すること、 一番目のレジスタの組（Ｒ）にシンドローム多項式の係
数を記憶し、１に等しい二番目の係数を除き全てゼロで
ある係数を二番目のレジスタの組（λ）に記憶し、カウ
ンタ（ｄＲ）に一番目の数を記憶すること、 １に等しい最後の係数を除き全てゼロである係数を三番
目のレジスタの組（Ｑ）に記憶し、全てゼロである係数
を四番目のレジスタの組（μ）に記憶し、一番目の数を
１だけ越える数を表示レジスタ（ｄＱ）に記憶するこ
と、 （ａ）カウンタ（ｄＲ）の内容が表示レジスタ（ｄＱ）
の内容以上であれば、または一番目の組の最後のレジス
タ（Ｒ2t-1）の内容がゼロであれば、一番目と二番目の
組の前のレジスタの内容と三番目の組の最後のレジスタ
（Ｑ2t-1）の内容との乗算結果と、三番目と四番目の組
（Ｑ，μ）の当該レジスタの内容と一番目の組の最後の
レジスタ（Ｒ2t-1）の乗算結果との和を一番目と二番目
の組（Ｒ，λ）の各レジスタに記憶し、カウンタ（ｄ
Ｒ）を減少すること、 （ｂ）一番目と二番目のレジスタの組（Ｒ，λ）の内容
とカウンタ（ｄＲ）の内容を三番目と四番目のレジスタ
の組（Ｑ，μ）と表示レジスタ（ｄＱ）に転送するこ
と、の各ステップを含み、 カウンタ（ｄＲ）の内容がｔだけ減少するまで（ａ）ま
たは（ｂ）のステップを繰り返し、一番目と二番目のレ
ジスタの組の中で誤り訂正多項式（Ｒ）の係数と誤り位
置検出多項式（λ）の係数を読み出すことを特徴とする
リードソロモン符号として伝送されたデータ内のｔ個の
誤りを訂正するために必要な係数の決定方法。 - 【請求項６】 一番目と三番目の組（Ｒ，Ｑ）が２ｔ−
１個のレジスタを含み、二番目と四番目の組（λ，μ）
がｔ＋１個のレジスタを含み、二番目の組の一番目のレ
ジスタ（λ0 ）が前記二番目の組の最後のレジスタ（λ
t ）の内容から得られた和を受ける請求項５に記載の方
法。 - 【請求項７】 ステップ（ｂ）において、カウンタ（ｄ
Ｒ）の内容と表示レジスタ（ｄＱ）の内容が入れ替えら
れ、カウンタが減少する請求項５に記載の方法。 - 【請求項８】 カウンタ（ｄＲ）に最初記憶される数が
ｔである請求項５に記載の方法。 - 【請求項９】 乗算結果の和がそれぞれ、 一番目の組の最後のレジスタ（Ｒ2t-1）のビットと三番
目および四番目の組のレジスタ（Ｑi ，μi ）の内容を
連続して一番目の部分的な乗算を行なうこと、 三番目の組の最後のレジスタ（Ｒ2t-1）のビットと一番
目および二番目の組のレジスタ（Ｒi ，λi ）の内容を
連続して二番目の部分的な乗算を行なうこと、 一番目と二番目の部分的な乗算結果を連続的に加算し、
これらの加算結果を加算毎に左にシフトされるレジスタ
（Ｐ）の内容に加えること、の各ステップに基づき得ら
れる請求項５に記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR9408122A FR2721775B1 (fr) | 1994-06-27 | 1994-06-27 | Circuit de localisation d'erreurs d'un décodeur Reed-Solomon. |
| FR9408122 | 1994-06-27 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0865175A true JPH0865175A (ja) | 1996-03-08 |
| JP2800723B2 JP2800723B2 (ja) | 1998-09-21 |
Family
ID=9464883
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7182225A Expired - Fee Related JP2800723B2 (ja) | 1994-06-27 | 1995-06-27 | リードソロモン復号器の誤り位置検出回路 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US5737343A (ja) |
| EP (1) | EP0690584B1 (ja) |
| JP (1) | JP2800723B2 (ja) |
| DE (1) | DE69528796T2 (ja) |
| FR (1) | FR2721775B1 (ja) |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2751810B1 (fr) * | 1996-07-23 | 1998-10-23 | Sgs Thomson Microelectronics | Systeme de correction d'erreurs dans des trames de donnees ayant des codes de parite horizontaux et verticaux |
| JP3233860B2 (ja) * | 1996-10-25 | 2001-12-04 | 松下電器産業株式会社 | リードソロモン復号器 |
| US6061826A (en) * | 1997-07-29 | 2000-05-09 | Philips Electronics North America Corp. | Hardware-optimized reed-solomon decoder for large data blocks |
| US6263471B1 (en) * | 1999-03-05 | 2001-07-17 | Industrial Technology Research Institute | Method and apparatus for decoding an error correction code |
| US6571368B1 (en) | 2000-02-02 | 2003-05-27 | Macronix International Co., Ltd. | Systolic Reed-Solomon decoder |
| US6671850B1 (en) | 2000-05-01 | 2003-12-30 | International Business Machines Corporation | On-the-fly algebraic error correction system and method for reducing error location search |
| US6792569B2 (en) | 2001-04-24 | 2004-09-14 | International Business Machines Corporation | Root solver and associated method for solving finite field polynomial equations |
| US7146553B2 (en) * | 2001-11-21 | 2006-12-05 | Infinera Corporation | Error correction improvement for concatenated 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 |
| US9954553B1 (en) * | 2015-06-05 | 2018-04-24 | Altera Corporation | Circuitry and methods for continuous parallel decoder operation |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05165662A (ja) * | 1991-12-12 | 1993-07-02 | Sony Corp | ユークリッドの互除回路 |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4504948A (en) * | 1982-12-29 | 1985-03-12 | International Business Machines Corporation | Syndrome processing unit for multibyte error correcting systems |
| US4649541A (en) * | 1984-11-21 | 1987-03-10 | The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration | Reed-Solomon decoder |
| US4747103A (en) * | 1985-03-21 | 1988-05-24 | Canon Kabushiki Kaisha | Signal processing apparatus for correcting decoding errors |
| FR2605818B1 (fr) * | 1986-10-27 | 1992-09-18 | Thomson Csf | Codeur-decodeur algebrique de codes en blocs reed solomon et bch, applicable aux telecommunications numeriques |
| US5325373A (en) * | 1986-12-22 | 1994-06-28 | Canon Kabushiki Kaisha | Apparatus for encoding and decoding reed-solomon code |
| US4868828A (en) * | 1987-10-05 | 1989-09-19 | California Institute Of Technology | Architecture for time or transform domain decoding of reed-solomon codes |
| US5170399A (en) * | 1989-08-30 | 1992-12-08 | Idaho Research Foundation, Inc. | Reed-Solomon Euclid algorithm decoder having a process configurable Euclid stack |
| EP0431629A3 (en) * | 1989-12-08 | 1993-07-21 | Sony Corporation | Mutual division circuit |
| US5442578A (en) * | 1991-12-12 | 1995-08-15 | Sony Corporation | Calculating circuit for error correction |
| US5504758A (en) * | 1992-04-28 | 1996-04-02 | Mitsubishi Denki Kabushiki Kaisha | Error-correcting apparatus |
| US5517509A (en) * | 1993-03-31 | 1996-05-14 | Kabushiki Kaisha Toshiba | Decoder for decoding ECC using Euclid's algorithm |
-
1994
- 1994-06-27 FR FR9408122A patent/FR2721775B1/fr not_active Expired - Fee Related
-
1995
- 1995-06-21 DE DE69528796T patent/DE69528796T2/de not_active Expired - Fee Related
- 1995-06-21 EP EP95410057A patent/EP0690584B1/fr not_active Expired - Lifetime
- 1995-06-22 US US08/493,830 patent/US5737343A/en not_active Expired - Lifetime
- 1995-06-27 JP JP7182225A patent/JP2800723B2/ja not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05165662A (ja) * | 1991-12-12 | 1993-07-02 | Sony Corp | ユークリッドの互除回路 |
Also Published As
| Publication number | Publication date |
|---|---|
| DE69528796T2 (de) | 2003-09-18 |
| US5737343A (en) | 1998-04-07 |
| EP0690584A1 (fr) | 1996-01-03 |
| FR2721775B1 (fr) | 1996-09-06 |
| FR2721775A1 (fr) | 1995-12-29 |
| EP0690584B1 (fr) | 2002-11-13 |
| JP2800723B2 (ja) | 1998-09-21 |
| DE69528796D1 (de) | 2002-12-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0114938B1 (en) | On-the-fly multibyte error correction | |
| US5170399A (en) | Reed-Solomon Euclid algorithm decoder having a process configurable Euclid stack | |
| US6374383B1 (en) | Determining error locations using error correction codes | |
| US5517509A (en) | Decoder for decoding ECC using Euclid's algorithm | |
| JP3970337B2 (ja) | 大規模データ・ブロックのためのハードウェア最適化リード・ソロモン・デコーダ | |
| JP3233860B2 (ja) | リードソロモン復号器 | |
| EP0329789B1 (en) | Galois field arithmetic unit | |
| JPH0452556B2 (ja) | ||
| JP2003529233A (ja) | データを符号化及び復号化する方法及び装置 | |
| US5365529A (en) | Circuitry for detecting and correcting errors in data words occurring in Reed-Solomon coded blocks and determining when errors are uncorrectable by syndrome analysis, Euclid's algorithm and a Chien search | |
| US5818854A (en) | Reed-solomon decoder | |
| JPH0653842A (ja) | Ｒｓコードデータ信号を復号化する方法および回路 | |
| US5983389A (en) | Error correction decoding apparatus | |
| JPH1093445A (ja) | 誤り位置検出多項式計算装置 | |
| JP2800723B2 (ja) | リードソロモン復号器の誤り位置検出回路 | |
| JPS63186338A (ja) | 誤り訂正回路 | |
| EP1442528A2 (en) | Decoding method and decoder for reed solomon code | |
| EP0991196B1 (en) | Method of correcting lost data and circuit thereof | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| JPH09307458A (ja) | エラー訂正向け多項式評価装置 | |
| JP3233502B2 (ja) | 復号化装置 | |
| EP0793352B1 (en) | Apparatus for determining the error evaluator polynomial for use in a Reed-Solomon decoder | |
| JP2000295116A (ja) | 誤り修正符号化方法 | |
| JPH047847B2 (ja) | ||
| JP2591611B2 (ja) | ｔ重誤り訂正符号の符号化復号化回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 19980609 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070710 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080710 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080710 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090710 Year of fee payment: 11 |
|
| LAPS | Cancellation because of no payment of annual fees |