JPH1065552A - 誤り訂正の演算処理方法及び処理回路 - Google Patents
誤り訂正の演算処理方法及び処理回路Info
- Publication number
- JPH1065552A JPH1065552A JP8215629A JP21562996A JPH1065552A JP H1065552 A JPH1065552 A JP H1065552A JP 8215629 A JP8215629 A JP 8215629A JP 21562996 A JP21562996 A JP 21562996A JP H1065552 A JPH1065552 A JP H1065552A
- Authority
- JP
- Japan
- Prior art keywords
- polynomial
- error correction
- arithmetic processing
- error
- coefficients
- 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
- 238000003672 processing method Methods 0.000 title claims abstract description 8
- 238000011156 evaluation Methods 0.000 claims abstract description 16
- 230000015654 memory Effects 0.000 claims description 28
- 208000011580 syndromic disease Diseases 0.000 claims description 18
- 238000000034 method Methods 0.000 claims description 13
- 238000004364 calculation method Methods 0.000 claims description 7
- 230000003247 decreasing effect Effects 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 6
- FFBHFFJDDLITSX-UHFFFAOYSA-N benzyl N-[2-hydroxy-4-(3-oxomorpholin-4-yl)phenyl]carbamate Chemical compound OC1=C(NC(=O)OCC2=CC=CC=C2)C=CC(=C1)N1CCOCC1=O FFBHFFJDDLITSX-UHFFFAOYSA-N 0.000 description 1
- 238000006243 chemical reaction 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/1545—Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
-
- 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
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)【要約】
【課題】 誤り訂正を実現するためのユークリッドアル
ゴリズム実行には、多数回のガロア体上の演算が必要で
あるため、処理時間がかかる。多数の演算回路を用いて
同時に演算を行えば処理時間が短縮できるが、回路規模
が大きくなる。 【解決手段】 誤り位置多項式と誤り評価多項式を求め
るための乗算を各多項式ごとの乗算器７〜１０と加算器
１１，１２を用いて並列に処理し、この演算結果から多
項式の次数を求めるに必要な多項式の係数が零か否かの
判断を零チェック回路１７により演算直後において逐一
行い、演算処理と次数処理とを並列に処理する。回路規
模を縮小する一方で、高速処理が可能となる。
ゴリズム実行には、多数回のガロア体上の演算が必要で
あるため、処理時間がかかる。多数の演算回路を用いて
同時に演算を行えば処理時間が短縮できるが、回路規模
が大きくなる。 【解決手段】 誤り位置多項式と誤り評価多項式を求め
るための乗算を各多項式ごとの乗算器７〜１０と加算器
１１，１２を用いて並列に処理し、この演算結果から多
項式の次数を求めるに必要な多項式の係数が零か否かの
判断を零チェック回路１７により演算直後において逐一
行い、演算処理と次数処理とを並列に処理する。回路規
模を縮小する一方で、高速処理が可能となる。
Description
【０００１】
【発明の属する技術分野】本発明は誤り訂正の演算処理
技術に関し、特にユークリッドアルゴリズムを実現する
演算処理方法と処理回路に関する。
技術に関し、特にユークリッドアルゴリズムを実現する
演算処理方法と処理回路に関する。
【０００２】
【従来の技術】一般に、リード・ソロモン符号を用いて
誤り訂正を行うためには、次の４つの手順が一般的であ
る。 受信データからシンドロームを計算する。 シンドロームから誤り位置多項式、誤り評価多項式を
求める。 誤り位置多項式から誤り位置を求める。 誤り位置多項式、誤り評価多項式、誤り位置から誤り
数値を求め、訂正する。 訂正能力の大きいリード・ソロモン符号による誤り訂正
では、のシンドロームから誤り位置多項式、誤り評価
多項式を求める手法の１つとして、２つの多項式の最大
公約数を求めるユークリッド互除法を応用したユークリ
ッドアルゴリズムが知られている。
誤り訂正を行うためには、次の４つの手順が一般的であ
る。 受信データからシンドロームを計算する。 シンドロームから誤り位置多項式、誤り評価多項式を
求める。 誤り位置多項式から誤り位置を求める。 誤り位置多項式、誤り評価多項式、誤り位置から誤り
数値を求め、訂正する。 訂正能力の大きいリード・ソロモン符号による誤り訂正
では、のシンドロームから誤り位置多項式、誤り評価
多項式を求める手法の１つとして、２つの多項式の最大
公約数を求めるユークリッド互除法を応用したユークリ
ッドアルゴリズムが知られている。
【０００３】図５はこのような誤り訂正システムの全体
構成図である。受信データの入力から訂正までに復号遅
延が伴うため、その間データを蓄えるデータ遅延メモリ
３１、受信データからシンドロームを計算するためのシ
ンドローム計算回路３２、シンドロームから誤り位置多
項式、誤り評価多項式を求めるためのユークリッド実行
回路３３、誤り位置多項式、誤り評価多項式から誤り位
置、誤り数値を求めるチェンサーチ実行回路３４、誤り
位置、誤りの数値により訂正を行う訂正回路３５により
構成される。
構成図である。受信データの入力から訂正までに復号遅
延が伴うため、その間データを蓄えるデータ遅延メモリ
３１、受信データからシンドロームを計算するためのシ
ンドローム計算回路３２、シンドロームから誤り位置多
項式、誤り評価多項式を求めるためのユークリッド実行
回路３３、誤り位置多項式、誤り評価多項式から誤り位
置、誤り数値を求めるチェンサーチ実行回路３４、誤り
位置、誤りの数値により訂正を行う訂正回路３５により
構成される。
【０００４】ここで、ガロア体ＧＦ（２n ）上のリード
・ソロモン符号によるｔ重誤り訂正を例としたシンドロ
ームから誤り位置多項式、誤り評価多項式を求めるユー
クリッドアルゴリズムについて説明する。まず、受信デ
ータより求めたシンドロームｓ0 〜ｓ2t-1より、シンド
ローム多項式を、 Ｓ（Ｘ）＝ｓ0 ＋ｓi ｘ＋…＋ｓ2t-1ｘ2t-1…（１） とする。また、誤り位置多項式を、 σ（ｘ）＝（１−αj1ｘ）・…・（１−αjkｘ）…（２） とする。ここで、 α：原始多項式の根 j1…jk：誤りの位置。
・ソロモン符号によるｔ重誤り訂正を例としたシンドロ
ームから誤り位置多項式、誤り評価多項式を求めるユー
クリッドアルゴリズムについて説明する。まず、受信デ
ータより求めたシンドロームｓ0 〜ｓ2t-1より、シンド
ローム多項式を、 Ｓ（Ｘ）＝ｓ0 ＋ｓi ｘ＋…＋ｓ2t-1ｘ2t-1…（１） とする。また、誤り位置多項式を、 σ（ｘ）＝（１−αj1ｘ）・…・（１−αjkｘ）…（２） とする。ここで、 α：原始多項式の根 j1…jk：誤りの位置。
【０００５】このシンドローム多項式Ｓ（ｘ）と誤り位
置多項式α（ｘ）の関係は、 φ（ｘ）ｘ2t＋α（ｘ）Ｓ（ｘ）＝ω（ｘ）…（３） ｄｅｇω（ｘ）＜ｄｅｇσ（ｘ）≦ｔ−１…（４） である。ここで、 ω（ｘ）：誤り評価多項式 φ（ｘ）：ＧＦ（２n ）上の任意の多項式 ｎ：原始多項式の次数 ｔ：訂正可能な誤り数 ｄｅｇω（ｘ）：誤り評価多項式ω（ｘ）の次数 ｄｅｇσ（ｘ）：誤り位置多項式α（ｘ）の次数
置多項式α（ｘ）の関係は、 φ（ｘ）ｘ2t＋α（ｘ）Ｓ（ｘ）＝ω（ｘ）…（３） ｄｅｇω（ｘ）＜ｄｅｇσ（ｘ）≦ｔ−１…（４） である。ここで、 ω（ｘ）：誤り評価多項式 φ（ｘ）：ＧＦ（２n ）上の任意の多項式 ｎ：原始多項式の次数 ｔ：訂正可能な誤り数 ｄｅｇω（ｘ）：誤り評価多項式ω（ｘ）の次数 ｄｅｇσ（ｘ）：誤り位置多項式α（ｘ）の次数
【０００６】式（３），（４）を満たす誤り位置多項式
σ（ｘ）と誤り評価多項式ω（ｘ）はｘ2tとシンドロー
ム多項式Ｓ（ｘ）の最大公約数を求めるユークリッド互
除法の過程の中で求めることができる。 Ｒ-1（ｘ）＝ｘ2t、Ｒ0 （ｘ）＝Ｓ（ｘ）…（５） とおき、 Ａi （ｘ）Ｒ-1（ｘ）＋Ｂi （ｘ）Ｒ0 （ｘ）＝Ｒi （ｘ）…（６） を満たす、多項式Ａi ( ｘ），Ｂi （ｘ），Ｒi （ｘ）
を逐一的に求める。Ｂi（ｘ）の次数がｔ次以下、Ｒi
（ｘ）の次数がｔ−１次以下となれば、Ｂi （ｘ）、Ｒ
i （ｘ）がそれぞれ誤り位置多項式σ（ｘ）、誤り評価
多項式ω（ｘ）となりえる。
σ（ｘ）と誤り評価多項式ω（ｘ）はｘ2tとシンドロー
ム多項式Ｓ（ｘ）の最大公約数を求めるユークリッド互
除法の過程の中で求めることができる。 Ｒ-1（ｘ）＝ｘ2t、Ｒ0 （ｘ）＝Ｓ（ｘ）…（５） とおき、 Ａi （ｘ）Ｒ-1（ｘ）＋Ｂi （ｘ）Ｒ0 （ｘ）＝Ｒi （ｘ）…（６） を満たす、多項式Ａi ( ｘ），Ｂi （ｘ），Ｒi （ｘ）
を逐一的に求める。Ｂi（ｘ）の次数がｔ次以下、Ｒi
（ｘ）の次数がｔ−１次以下となれば、Ｂi （ｘ）、Ｒ
i （ｘ）がそれぞれ誤り位置多項式σ（ｘ）、誤り評価
多項式ω（ｘ）となりえる。
【０００７】式（６）を満たすＡi （ｘ），Ｂ
i （ｘ），Ｒi （ｘ）を効率的に求める方法は、以下の
演算を実行することである。 Ｑi （ｘ）＝〔Ｒi-2 （ｘ）／Ｒi-1 （ｘ）〕…（７） Ｒi （ｘ）＝Ｒi-2 （ｘ）−Ｑi （ｘ）Ｒi-1 （ｘ）…（８） Ａi （ｘ）＝Ａi-2 （ｘ）−Ｑi （ｘ）Ａi-1 （ｘ）…（９） Ｂi （ｘ）＝Ｂi-2 （ｘ）−Ｑi （ｘ）Ｂi-1 （ｘ）…（１０） ここで、 〔 〕：商多項式 ｉ：〔１，２，３，…，〕 Ａ-1（ｘ）＝１ Ａ0 （ｘ）＝０ Ｂ-1（ｘ）＝０ Ｂ0 （ｘ）＝１ この式（８）の演算を実行する操作こそが、ユークリッ
ド互除法の操作そのものである。
i （ｘ），Ｒi （ｘ）を効率的に求める方法は、以下の
演算を実行することである。 Ｑi （ｘ）＝〔Ｒi-2 （ｘ）／Ｒi-1 （ｘ）〕…（７） Ｒi （ｘ）＝Ｒi-2 （ｘ）−Ｑi （ｘ）Ｒi-1 （ｘ）…（８） Ａi （ｘ）＝Ａi-2 （ｘ）−Ｑi （ｘ）Ａi-1 （ｘ）…（９） Ｂi （ｘ）＝Ｂi-2 （ｘ）−Ｑi （ｘ）Ｂi-1 （ｘ）…（１０） ここで、 〔 〕：商多項式 ｉ：〔１，２，３，…，〕 Ａ-1（ｘ）＝１ Ａ0 （ｘ）＝０ Ｂ-1（ｘ）＝０ Ｂ0 （ｘ）＝１ この式（８）の演算を実行する操作こそが、ユークリッ
ド互除法の操作そのものである。
【０００８】図６は、ユークリッドアルゴリズムの動作
フローチャートである。図中、α，βは多項式Ｂ，Ａの
最高次係数を表し、それらを多項式Ａ，Ｂに交互に乗ず
ることにより、元来必要な除算（式（７）に相当する除
算）を省略している。同図から明らかなように、リード
・ソロモン符号を用いて誤り訂正を行う際のユークリッ
ドアルゴリズムの実行は、ガロア体上の元を係数とする
多項式の演算と、多項式の次数を求める必要がある。
フローチャートである。図中、α，βは多項式Ｂ，Ａの
最高次係数を表し、それらを多項式Ａ，Ｂに交互に乗ず
ることにより、元来必要な除算（式（７）に相当する除
算）を省略している。同図から明らかなように、リード
・ソロモン符号を用いて誤り訂正を行う際のユークリッ
ドアルゴリズムの実行は、ガロア体上の元を係数とする
多項式の演算と、多項式の次数を求める必要がある。
【０００９】
【発明が解決しようとする課題】このように、ガロア体
上の元を係数とする多項式の演算は、専用のガロア演算
ユニットを用いて、実行していた。これは、多項式の演
算を単一のガロア演算ユニットにて行うものであり、
（２×２ｔ×２ｔ）回の演算が必要となる。このため、
従来の演算処理回路では演算に時間がかかり、高速処理
に向かないという問題があった。
上の元を係数とする多項式の演算は、専用のガロア演算
ユニットを用いて、実行していた。これは、多項式の演
算を単一のガロア演算ユニットにて行うものであり、
（２×２ｔ×２ｔ）回の演算が必要となる。このため、
従来の演算処理回路では演算に時間がかかり、高速処理
に向かないという問題があった。
【００１０】これに対し、例えば特開平１−２７６８２
５号公報に示されるように、ユークリッド互除法を用い
て誤り位置多項式、誤り評価多項式を高速に求めること
を目的とした演算処理回路が提案されている。図７は、
特開平１−２７６８２５号公報に示された回路例であ
る。多項式Ａ，Ｍの係数格納用レジスタ３１、多項式
Ｂ，Ｌの係数格納用レジスタ３２、多項式Ａの最高次係
数β用レジスタ３３、多項式Ｂの最高次係数α用レジス
タ３４、零チェック回路３９，４０を有し、かつα及び
βを選択するセレクタ３５、ガロア体上乗算器３６，３
７、ガロア体上加算器３８の構成体を複数組設けてい
る。この構成では、多項式Ａ，Ｍの係数ごとにガロア体
上乗算器３６が（２ｔ＋１）個、および多項式Ｂ，Ｌの
係数毎にガロア体上乗算器３７が（２ｔ＋１）個設けら
れており、すなわち（２×（２ｔ＋１））個の乗算器に
よりユークリッド互除法による２つの多項式の演算を並
列処理している。このため、（２ｔ）回の換算で処理を
終え、処理時間の短縮が可能となる。しかしながら、こ
のような多数の演算回路を用いて同時に演算を行う構成
では、ガロア体上の乗算器は１個あたり約５００ゲート
を要するため、乗算器の数が多くなると回数規模も大き
くなる。
５号公報に示されるように、ユークリッド互除法を用い
て誤り位置多項式、誤り評価多項式を高速に求めること
を目的とした演算処理回路が提案されている。図７は、
特開平１−２７６８２５号公報に示された回路例であ
る。多項式Ａ，Ｍの係数格納用レジスタ３１、多項式
Ｂ，Ｌの係数格納用レジスタ３２、多項式Ａの最高次係
数β用レジスタ３３、多項式Ｂの最高次係数α用レジス
タ３４、零チェック回路３９，４０を有し、かつα及び
βを選択するセレクタ３５、ガロア体上乗算器３６，３
７、ガロア体上加算器３８の構成体を複数組設けてい
る。この構成では、多項式Ａ，Ｍの係数ごとにガロア体
上乗算器３６が（２ｔ＋１）個、および多項式Ｂ，Ｌの
係数毎にガロア体上乗算器３７が（２ｔ＋１）個設けら
れており、すなわち（２×（２ｔ＋１））個の乗算器に
よりユークリッド互除法による２つの多項式の演算を並
列処理している。このため、（２ｔ）回の換算で処理を
終え、処理時間の短縮が可能となる。しかしながら、こ
のような多数の演算回路を用いて同時に演算を行う構成
では、ガロア体上の乗算器は１個あたり約５００ゲート
を要するため、乗算器の数が多くなると回数規模も大き
くなる。
【００１１】本発明の目的は、演算処理回路の縮小化を
可能とする一方で演算処理の高速化を可能にした誤り訂
正の演算処理方法と処理回路を提供することにある。
可能とする一方で演算処理の高速化を可能にした誤り訂
正の演算処理方法と処理回路を提供することにある。
【００１２】
【課題を解決するための手段】本発明の演算処理方法に
おいては、リード・ソロモン符号による誤り訂正におい
て、シンドロームの計算、ユークリッドアルゴリズムの
実行とチェンサーチ実行、誤り訂正の３つの処理を並列
処理している。その上で、ユークリッドアルゴリズムに
より誤り位置多項式と誤り評価多項式を求める演算処理
においては、ガロア体上の元を係数とする２つの多項式
の演算を同時に実行することを特徴とする。また、その
演算処理においては、ガロア体上の元を係数とする多項
式の演算処理と、この演算結果である多項式の係数が零
かどうかを逐一判断してその次数を求める処理を並列し
て実行することを特徴とする。
おいては、リード・ソロモン符号による誤り訂正におい
て、シンドロームの計算、ユークリッドアルゴリズムの
実行とチェンサーチ実行、誤り訂正の３つの処理を並列
処理している。その上で、ユークリッドアルゴリズムに
より誤り位置多項式と誤り評価多項式を求める演算処理
においては、ガロア体上の元を係数とする２つの多項式
の演算を同時に実行することを特徴とする。また、その
演算処理においては、ガロア体上の元を係数とする多項
式の演算処理と、この演算結果である多項式の係数が零
かどうかを逐一判断してその次数を求める処理を並列し
て実行することを特徴とする。
【００１３】また、本発明の演算処理回路においては、
ガロア体上の元を係数とする２つの多項式の演算を多項
式ごとに行う演算器を備えることを特徴としている。す
なわち、各多項式の係数が格納される複数のメモリと、
各メモリから読み出された係数がラッチされる複数のレ
ジスタと、各レジスタにラッチされた係数を多項式ごと
に演算する複数の乗算器および加算器と、演算によって
得られた多項式の係数が零か否かを判断する零チェック
回路とを備えている。また、レジスタにラッチされた係
数のうち、所要の次数の係数を選択するセレクタを備え
ることが好ましい。
ガロア体上の元を係数とする２つの多項式の演算を多項
式ごとに行う演算器を備えることを特徴としている。す
なわち、各多項式の係数が格納される複数のメモリと、
各メモリから読み出された係数がラッチされる複数のレ
ジスタと、各レジスタにラッチされた係数を多項式ごと
に演算する複数の乗算器および加算器と、演算によって
得られた多項式の係数が零か否かを判断する零チェック
回路とを備えている。また、レジスタにラッチされた係
数のうち、所要の次数の係数を選択するセレクタを備え
ることが好ましい。
【００１４】
【発明の実施の形態】次に、本発明の実施形態を図面を
参照して説明する。図１は本発明によるユークリッドア
ルゴリズム演算処理回路の第１の実施形態である。この
実施形態では、図３に示すように、リード・ソロモン符
号による誤り訂正において、パイプライン処理にて誤り
訂正を行うと、復号遅延時間を短縮することができるこ
とに基づいている。すなわち、シンドロームの計算、ユ
ークリッドアルゴリズムの実行とチェンサーチ実行、誤
り訂正の３つの処理を並列処理することにより、処理速
度の高速化が可能となる。また、シンドロームはリード
・ソロモン符号の符号長のステップで計算されるので、
シンドローム処理にかかる時間と同等の時間でユークリ
ッドアルゴリズムおよびチェンサーチの処理を行えばよ
いことになる。
参照して説明する。図１は本発明によるユークリッドア
ルゴリズム演算処理回路の第１の実施形態である。この
実施形態では、図３に示すように、リード・ソロモン符
号による誤り訂正において、パイプライン処理にて誤り
訂正を行うと、復号遅延時間を短縮することができるこ
とに基づいている。すなわち、シンドロームの計算、ユ
ークリッドアルゴリズムの実行とチェンサーチ実行、誤
り訂正の３つの処理を並列処理することにより、処理速
度の高速化が可能となる。また、シンドロームはリード
・ソロモン符号の符号長のステップで計算されるので、
シンドローム処理にかかる時間と同等の時間でユークリ
ッドアルゴリズムおよびチェンサーチの処理を行えばよ
いことになる。
【００１５】そこで、ユークリッドアルゴリズムにおい
て、ガロア体上の元を係数とする２つの多項式の演算を
多項式ごとの乗算器で実行し、かつ演算結果が零か否か
を逐一判断することによりその多項式の次数を求めてい
る。すなわち、前記した多項式Ａ，Ｂの演算結果であ
る、多項式αＡ＋βＢｘdegA-degB 、またはαＡｘ
degB-degA ＋βＢの係数が零かを逐一判断し、多項式Ａ
または多項式Ｂの次数を求め、処理の高速化維持を図
る。また、多項式Ａ，Ｂの最高次係数β，αと多項式
Ａ，Ｂ，Ｌ，Ｍの各係数との乗算を各々の多項式ごとの
乗算器により行うことで、回路規模の小型化が可能とな
る。
て、ガロア体上の元を係数とする２つの多項式の演算を
多項式ごとの乗算器で実行し、かつ演算結果が零か否か
を逐一判断することによりその多項式の次数を求めてい
る。すなわち、前記した多項式Ａ，Ｂの演算結果であ
る、多項式αＡ＋βＢｘdegA-degB 、またはαＡｘ
degB-degA ＋βＢの係数が零かを逐一判断し、多項式Ａ
または多項式Ｂの次数を求め、処理の高速化維持を図
る。また、多項式Ａ，Ｂの最高次係数β，αと多項式
Ａ，Ｂ，Ｌ，Ｍの各係数との乗算を各々の多項式ごとの
乗算器により行うことで、回路規模の小型化が可能とな
る。
【００１６】図１において、この実施形態の演算処理回
路は、６個のレジスタ１〜６、４個のガロア体上乗算器
７〜１０、２個のガロア体上加算器１１〜１２、４個の
メモリ１３〜１６、零チェック回路１７からなる。Ａメ
モリ１３には多項式Ａの各係数ａi が、Ｂメモリ１４に
は多項式Ｂの各係数ｂi が、Ｌメモリ１５には多項式Ｌ
の各係数ｌi が、Ｍメモリ１６には多項式Ｍの各係数ｍ
i が格納されるので、Ａメモリ１３の大きさは（２ｔ＋
１）ワード、Ｂメモリ１４の大きさは（２ｔ）ワード、
Ｌメモリ１５とＭメモリ１６の大きさは（ｔ＋１）ワー
ドである。
路は、６個のレジスタ１〜６、４個のガロア体上乗算器
７〜１０、２個のガロア体上加算器１１〜１２、４個の
メモリ１３〜１６、零チェック回路１７からなる。Ａメ
モリ１３には多項式Ａの各係数ａi が、Ｂメモリ１４に
は多項式Ｂの各係数ｂi が、Ｌメモリ１５には多項式Ｌ
の各係数ｌi が、Ｍメモリ１６には多項式Ｍの各係数ｍ
i が格納されるので、Ａメモリ１３の大きさは（２ｔ＋
１）ワード、Ｂメモリ１４の大きさは（２ｔ）ワード、
Ｌメモリ１５とＭメモリ１６の大きさは（ｔ＋１）ワー
ドである。
【００１７】次に図１の動作を述べる。まず、初期状態
として各メモリに初期値が書き込まれる。すなわち、Ａ
メモリ１３にはｘ2tの係数、Ｂメモリ１４にはシンドロ
ーム多項式Ｓ（ｘ）＝ｓ0 ＋ｓ1 ｘ＋…＋ｓ2t-1ｘ2t-1
の係数、Ｌメモリ１５には０、Ｍメモリ１６には１、が
それぞれ書き込まれる（図６における処理１）。
として各メモリに初期値が書き込まれる。すなわち、Ａ
メモリ１３にはｘ2tの係数、Ｂメモリ１４にはシンドロ
ーム多項式Ｓ（ｘ）＝ｓ0 ＋ｓ1 ｘ＋…＋ｓ2t-1ｘ2t-1
の係数、Ｌメモリ１５には０、Ｍメモリ１６には１、が
それぞれ書き込まれる（図６における処理１）。
【００１８】そして、ユークリッドアルゴリズムの動作
として、多項式Ａ，ＢからαＡ＋βＢｘdegA-degB 、ま
た多項式Ｌ，ＭからαＬ＋βＭｘdegA-degB を求める動
作（図６における処理２→処理３→処理５の動作）を例
として述べる。メモリ１３〜１６から読み出された各係
数は、レジスタ１〜６にラッチされる。レジスタ１には
多項式Ａの最高次係数βが、レジスタ２には多項式Ａの
係数ａi が高次から降順で、レジスタ３には多項式Ｂの
係数ｂi が高次から降順で、レジスタ４には多項式Ｂの
最高次係数αが、レジスタ５には多項式Ｌの係数ｌi が
高次から降順で、レジスタ６には多項式Ｍの係数ｍi が
高次から降順で、それぞれラッチされる。
として、多項式Ａ，ＢからαＡ＋βＢｘdegA-degB 、ま
た多項式Ｌ，ＭからαＬ＋βＭｘdegA-degB を求める動
作（図６における処理２→処理３→処理５の動作）を例
として述べる。メモリ１３〜１６から読み出された各係
数は、レジスタ１〜６にラッチされる。レジスタ１には
多項式Ａの最高次係数βが、レジスタ２には多項式Ａの
係数ａi が高次から降順で、レジスタ３には多項式Ｂの
係数ｂi が高次から降順で、レジスタ４には多項式Ｂの
最高次係数αが、レジスタ５には多項式Ｌの係数ｌi が
高次から降順で、レジスタ６には多項式Ｍの係数ｍi が
高次から降順で、それぞれラッチされる。
【００１９】次いで、乗算器７，８、加算器１１によっ
て演算結果の多項式αＡ＋βＢｘdegA-degB の係数αａ
i ＋βｂi が高次から降順に、乗算器９，１０、加算器
１２によって多項式αＬ＋βＭｘdegA-degB の係数αｌ
i ＋βｍi が高次から降順に求まる。この演算結果はＡ
メモリ１３とＬメモリ１５に書き込まれる。さらにメモ
リに書き込むと同時に、零チェック回路１７によって多
項式αＡ＋βＢｘdegA -degB の係数αａi ＋βｂi が零
かどうかの判断をして、零でなければ、多項式αＡ＋β
ＢｘdegA-degB の次数が求まる。
て演算結果の多項式αＡ＋βＢｘdegA-degB の係数αａ
i ＋βｂi が高次から降順に、乗算器９，１０、加算器
１２によって多項式αＬ＋βＭｘdegA-degB の係数αｌ
i ＋βｍi が高次から降順に求まる。この演算結果はＡ
メモリ１３とＬメモリ１５に書き込まれる。さらにメモ
リに書き込むと同時に、零チェック回路１７によって多
項式αＡ＋βＢｘdegA -degB の係数αａi ＋βｂi が零
かどうかの判断をして、零でなければ、多項式αＡ＋β
ＢｘdegA-degB の次数が求まる。
【００２０】図２は、以上述べたユークリッドアルゴリ
ズム演算処理（図６における処理２→処理３→処理５の
処理）の多項式Ａ，Ｂに関する動作および零チェック、
多項式Ａの次数確定の動作のタイミング図である。Ａメ
モリ１３とＢメモリ１４から読み出されたデータ（Ｔ
１，Ｔ２）はそれぞれレジスタ１〜４にラッチされ（Ｔ
３，Ｔ４，Ｔ５，Ｔ６）、乗算器７，８と加算器１１に
よって演算される。Ｔ９が演算の結果であり、つまり多
項式αＡ＋βＢｘdegA-degB の係数αａi ＋βｂi であ
る。そして、零チェック回路１７においてこの係数が零
かどうかを判断し、多項式の次数を求める。このよう
に、多項式の演算処理と次数処理を並列に行うことによ
り、ｔ重誤り訂正の場合、多くとも（２ｔ×２ｔ）のス
テップにてユークリッドアルゴリズムに伴う処理は終了
する。
ズム演算処理（図６における処理２→処理３→処理５の
処理）の多項式Ａ，Ｂに関する動作および零チェック、
多項式Ａの次数確定の動作のタイミング図である。Ａメ
モリ１３とＢメモリ１４から読み出されたデータ（Ｔ
１，Ｔ２）はそれぞれレジスタ１〜４にラッチされ（Ｔ
３，Ｔ４，Ｔ５，Ｔ６）、乗算器７，８と加算器１１に
よって演算される。Ｔ９が演算の結果であり、つまり多
項式αＡ＋βＢｘdegA-degB の係数αａi ＋βｂi であ
る。そして、零チェック回路１７においてこの係数が零
かどうかを判断し、多項式の次数を求める。このよう
に、多項式の演算処理と次数処理を並列に行うことによ
り、ｔ重誤り訂正の場合、多くとも（２ｔ×２ｔ）のス
テップにてユークリッドアルゴリズムに伴う処理は終了
する。
【００２１】図４は、本発明によるユークリッドアルゴ
リズム演算処理回路の第２の実施形態である。多項式Ａ
と多項式Ｍの次数の和が常に等しく、また多項式Ｂと多
項式Ｌの次数の和が常に等しいことより、多項式Ａと多
項式Ｍ、多項式Ｂと多項式Ｌをそれぞれ大きさ（２ｔ＋
１）ワードのメモリに格納することにより、４個のレジ
スタ１〜４、２個のガロア体上乗算器７〜８、１個のガ
ロア体上加算器１１、２個のメモリ２１，２２、零チェ
ック回路１７、および多項式Ａ，Ｂの最高次係数を選択
するための２個のセレクタ１９，２０から構成され、第
１の実施形態より回路の小型化が図ることができる。因
みに、この実施形態では、（２ｔ×（２ｔ＋１））のス
テップにてユークリッドアルゴリズムに伴う処理は終了
する。
リズム演算処理回路の第２の実施形態である。多項式Ａ
と多項式Ｍの次数の和が常に等しく、また多項式Ｂと多
項式Ｌの次数の和が常に等しいことより、多項式Ａと多
項式Ｍ、多項式Ｂと多項式Ｌをそれぞれ大きさ（２ｔ＋
１）ワードのメモリに格納することにより、４個のレジ
スタ１〜４、２個のガロア体上乗算器７〜８、１個のガ
ロア体上加算器１１、２個のメモリ２１，２２、零チェ
ック回路１７、および多項式Ａ，Ｂの最高次係数を選択
するための２個のセレクタ１９，２０から構成され、第
１の実施形態より回路の小型化が図ることができる。因
みに、この実施形態では、（２ｔ×（２ｔ＋１））のス
テップにてユークリッドアルゴリズムに伴う処理は終了
する。
【００２２】
【発明の効果】以上説明したように本発明は、誤り位置
多項式と誤り評価多項式を求めるための演算を、各多項
式ごとの演算器を用いて並列に処理しているため、乗算
器の数が少なくて済み、ユークリッドアルゴリズムに伴
う演算処理回路の縮小化が実現できる。また、多項式の
次数を求めるに必要な多項式の係数が零かどうかの判断
を多項式の演算の直後に逐次行っているため、演算処理
と次数処理を並列に処理でき、ユークリッドアルゴリズ
ムに伴う演算処理と次数処理を高速に行うことが可能と
なる。
多項式と誤り評価多項式を求めるための演算を、各多項
式ごとの演算器を用いて並列に処理しているため、乗算
器の数が少なくて済み、ユークリッドアルゴリズムに伴
う演算処理回路の縮小化が実現できる。また、多項式の
次数を求めるに必要な多項式の係数が零かどうかの判断
を多項式の演算の直後に逐次行っているため、演算処理
と次数処理を並列に処理でき、ユークリッドアルゴリズ
ムに伴う演算処理と次数処理を高速に行うことが可能と
なる。
【図１】本発明の第１の実施形態の演算処理回路の回路
図である。
図である。
【図２】第１実施形態の動作を説明するためのタイミン
グ図である。
グ図である。
【図３】本発明の基本となるパイプライン処理の模式図
である。
である。
【図４】本発明の第２の実施形態の演算処理回路の回路
図である。
図である。
【図５】誤り訂正システムの全体構成を示す図である。
【図６】ユークリッドアルゴリズムの動作を説明するた
めのフローチャートである。
めのフローチャートである。
【図７】従来技術の一例を示す回路図である。
１〜６ レジスタ ７〜１０ ガロア体上乗算器 １１，１２ ガロア体上加算器 １３〜１６ メモリ １７ 零チェック回路 １９，２０ セレクタ ２１，２２ メモリ
Claims (6)
- 【請求項１】 リード・ソロモン符号による誤り訂正に
おいて、シンドロームの計算、ユークリッドアルゴリズ
ムの実行とチェンサーチ実行、誤り訂正の３つの処理を
並列処理することを特徴とする誤り訂正の演算処理方
法。 - 【請求項２】 ユークリッドアルゴリズムにより誤り位
置多項式と誤り評価多項式を求める演算処理において、
ガロア体上の元を係数とする２つの多項式の演算を同時
に実行することを特徴とする誤り訂正の演算処理方法。 - 【請求項３】 ユークリッドアルゴリズムによる誤り訂
正の演算処理において、ガロア体上の元を係数とする多
項式の演算処理と、この演算結果から多項式の係数が零
かどうかを逐一判断して次数を求める処理を並列して実
行することを特徴とする誤り訂正の演算処理方法。 - 【請求項４】 ユークリッドアルゴリズムにより誤り位
置多項式と誤り評価多項式を求める演算処理回路におい
て、ガロア体上の元を係数とする２つの多項式の演算を
多項式ごとに行う演算器を備えることを特徴とする誤り
訂正の演算処理回路。 - 【請求項５】 各多項式の係数が格納される複数のメモ
リと、各メモリから読み出された係数がラッチされる複
数のレジスタと、各レジスタにラッチされた係数を多項
式ごとに演算する複数の乗算器および加算器と、演算に
よって得られた多項式の係数が零か否かを判断する零チ
ェック回路とを備える請求項１の誤り訂正の演算処理回
路。 - 【請求項６】 レジスタにラッチされた係数のうち、所
要の次数の係数を選択するセレクタを備える請求項５の
誤り訂正の演算処理回路。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8215629A JP2907138B2 (ja) | 1996-08-15 | 1996-08-15 | 誤り訂正の演算処理方法及び処理回路 |
| EP97114081A EP0825533A1 (en) | 1996-08-15 | 1997-08-14 | Method and circuit for calculating and processing error correction |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8215629A JP2907138B2 (ja) | 1996-08-15 | 1996-08-15 | 誤り訂正の演算処理方法及び処理回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH1065552A true JPH1065552A (ja) | 1998-03-06 |
| JP2907138B2 JP2907138B2 (ja) | 1999-06-21 |
Family
ID=16675577
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP8215629A Expired - Lifetime JP2907138B2 (ja) | 1996-08-15 | 1996-08-15 | 誤り訂正の演算処理方法及び処理回路 |
Country Status (2)
| Country | Link |
|---|---|
| EP (1) | EP0825533A1 (ja) |
| JP (1) | JP2907138B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6772385B2 (en) | 2000-01-31 | 2004-08-03 | Sanyo Electric Co., Ltd. | Error-correcting device and decoder enabling fast error correction with reduced circuit scale |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH11196006A (ja) * | 1997-12-26 | 1999-07-21 | Nec Corp | 並列処理シンドロ−ム計算回路及びリ−ド・ソロモン複合化回路 |
| CN101459431B (zh) * | 2008-12-30 | 2012-03-07 | 北京大学 | 一种信道纠错码bch码和rs码的译码方法 |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0329789B1 (en) * | 1987-06-30 | 1995-02-08 | Matsushita Electric Industrial Co., Ltd. | Galois field arithmetic unit |
| 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 |
| 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 |
| JPH0427217A (ja) * | 1990-05-22 | 1992-01-30 | Toshiba Corp | 誤り位置及び誤り数値計算回路 |
| DE4140018A1 (de) * | 1991-12-04 | 1993-06-09 | Bts Broadcast Television Systems Gmbh, 6100 Darmstadt, De | Verfahren und schaltungsanordnung zum decodieren von rs-codierten datensignalen |
-
1996
- 1996-08-15 JP JP8215629A patent/JP2907138B2/ja not_active Expired - Lifetime
-
1997
- 1997-08-14 EP EP97114081A patent/EP0825533A1/en not_active Withdrawn
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6772385B2 (en) | 2000-01-31 | 2004-08-03 | Sanyo Electric Co., Ltd. | Error-correcting device and decoder enabling fast error correction with reduced circuit scale |
| US7181483B2 (en) | 2000-01-31 | 2007-02-20 | Sanyo Electric Co., Ltd. | Error-correcting device and decoder enabling fast error correction with reduced circuit scale |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0825533A1 (en) | 1998-02-25 |
| JP2907138B2 (ja) | 1999-06-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5715262A (en) | Errors and erasures correcting reed-solomon decoder | |
| US5027357A (en) | ECC/CRC error detection and correction system | |
| US5157669A (en) | Comparison of an estimated CRC syndrome to a generated CRC syndrome in an ECC/CRC system to detect uncorrectable errors | |
| US5642367A (en) | Finite field polynomial processing module for error control coding | |
| JP3233860B2 (ja) | リードソロモン復号器 | |
| JP3970337B2 (ja) | 大規模データ・ブロックのためのハードウェア最適化リード・ソロモン・デコーダ | |
| US6119262A (en) | Method and apparatus for solving key equation polynomials in decoding error correction codes | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| US5983389A (en) | Error correction decoding apparatus | |
| JP2004032737A (ja) | リード−ソロモン復号器 | |
| JP3245119B2 (ja) | 新たな多項式配列構造を採用したリード−ソロモン復号器とその復号方法 | |
| KR100258951B1 (ko) | 리드-솔로몬(rs) 복호기와 그 복호방법 | |
| JPS63186338A (ja) | 誤り訂正回路 | |
| JP3343857B2 (ja) | 復号装置、演算装置およびこれらの方法 | |
| JP2800723B2 (ja) | リードソロモン復号器の誤り位置検出回路 | |
| JP2001127645A (ja) | 誤り訂正方法および誤り訂正装置 | |
| US6915478B2 (en) | Method and apparatus for computing Reed-Solomon error magnitudes | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| JP2605966B2 (ja) | 誤り訂正回路 | |
| JP2662472B2 (ja) | 誤り訂正処理用シンドローム演算回路 | |
| JP2553565B2 (ja) | ガロア体演算装置 | |
| JP3233502B2 (ja) | 復号化装置 | |
| KR20000037517A (ko) | 리드-솔로몬 디코더 회로 | |
| JP2000295116A (ja) | 誤り修正符号化方法 |