JP3280470B2 - 誤り訂正回路 - Google Patents
誤り訂正回路Info
- Publication number
- JP3280470B2 JP3280470B2 JP13790593A JP13790593A JP3280470B2 JP 3280470 B2 JP3280470 B2 JP 3280470B2 JP 13790593 A JP13790593 A JP 13790593A JP 13790593 A JP13790593 A JP 13790593A JP 3280470 B2 JP3280470 B2 JP 3280470B2
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- exclusive
- output
- gates
- gate
- 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
- 238000012937 correction Methods 0.000 title claims description 35
- 208000011580 syndromic disease Diseases 0.000 claims description 49
- 238000001514 detection method Methods 0.000 claims description 21
- 238000009795 derivation Methods 0.000 claims description 16
- 230000004044 response Effects 0.000 claims description 3
- 102100039579 ETS translocation variant 2 Human genes 0.000 claims description 2
- 101000813735 Homo sapiens ETS translocation variant 2 Proteins 0.000 claims description 2
- 238000010586 diagram Methods 0.000 description 30
- 238000004364 calculation method Methods 0.000 description 5
- 238000000034 method Methods 0.000 description 5
- 230000000694 effects Effects 0.000 description 3
- 241000352333 Amegilla alpha Species 0.000 description 2
- 230000006870 function Effects 0.000 description 2
- 239000011159 matrix material Substances 0.000 description 2
- 238000004891 communication Methods 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
Landscapes
- Detection And Prevention Of Errors In Transmission (AREA)
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Description
【０００１】
【産業上の利用分野】本発明は、αをｍ次のガロア拡大
体ＧＦ（２m）の原始元とし、α，α3を根にもつ２重誤
り訂正（ｎ，ｋ）ＢＣＨ符号の復号を行うための誤り訂
正回路に関する。
体ＧＦ（２m）の原始元とし、α，α3を根にもつ２重誤
り訂正（ｎ，ｋ）ＢＣＨ符号の復号を行うための誤り訂
正回路に関する。
【０００２】
【従来の技術】ｔビット訂正ＢＣＨ（Bose-Chauduri-Ho
cqenghem Codes）符号のパラメータに関して、符号長ｎ
は、 ｎ ＝ ２m − １ …（１） であり、情報数ｋは、 ｋ ≧ ｎ − ｍｔ …（２） であり、このような符号長ｎ、情報数ｋのＢＣＨ符号
は、（ｎ，ｋ）ＢＣＨ符号と呼ばれる。
cqenghem Codes）符号のパラメータに関して、符号長ｎ
は、 ｎ ＝ ２m − １ …（１） であり、情報数ｋは、 ｋ ≧ ｎ − ｍｔ …（２） であり、このような符号長ｎ、情報数ｋのＢＣＨ符号
は、（ｎ，ｋ）ＢＣＨ符号と呼ばれる。
【０００３】誤り訂正符号の中でも、ＢＣＨ符号は、実
用上、極めて重要なものであり、通信、記録分野に多く
用いられている。その中でも特に２重誤り訂正符号は、
復号の際に用いる誤り位置多項式の係数とシンドローム
の関係が明らかにされており、ハード化の検討が比較的
容易である。しかしその復号には、ガロア体上での加
算、乗算、除算なの演算が必要であるので、先行技術で
は、（ａ）べき数←→ベクトル表現、逆元などをリード
オンリメモリに記憶させておき、外部からアクセスする
構成、または（ｂ）シンドロームと誤りの位置を表に求
め、同様にリードオンリメモリを外部からアクセスする
構成が実現されている。このような先行技術では、ハー
ド化する場合、リードオンリメモリに多くのメモリ容量
を必要とし、訂正数に対しコストが多くかかることにな
る。
用上、極めて重要なものであり、通信、記録分野に多く
用いられている。その中でも特に２重誤り訂正符号は、
復号の際に用いる誤り位置多項式の係数とシンドローム
の関係が明らかにされており、ハード化の検討が比較的
容易である。しかしその復号には、ガロア体上での加
算、乗算、除算なの演算が必要であるので、先行技術で
は、（ａ）べき数←→ベクトル表現、逆元などをリード
オンリメモリに記憶させておき、外部からアクセスする
構成、または（ｂ）シンドロームと誤りの位置を表に求
め、同様にリードオンリメモリを外部からアクセスする
構成が実現されている。このような先行技術では、ハー
ド化する場合、リードオンリメモリに多くのメモリ容量
を必要とし、訂正数に対しコストが多くかかることにな
る。
【０００４】たとえば図１９の先行技術では、ＢＣＨ符
号信号がライン１から与えられるシンドロームＳ１のレ
ジスタ２と、シンドロームＳ３のレジスタ３と、リード
オンリメモリ４とが備えられ、その受信されたＢＣＨ符
号信号をストアするデータレジスタ５が備えられ、訂正
後のＢＣＨ符号信号を導出する排他的論理和ゲート回路
６が備えられる。このような図１９に示される先行技術
では、前述の先行技術（ｂ）を実現するものであって、
上述のようにリードオンリメモリ４のメモリ容量を大き
くする必要があるという問題がある。
号信号がライン１から与えられるシンドロームＳ１のレ
ジスタ２と、シンドロームＳ３のレジスタ３と、リード
オンリメモリ４とが備えられ、その受信されたＢＣＨ符
号信号をストアするデータレジスタ５が備えられ、訂正
後のＢＣＨ符号信号を導出する排他的論理和ゲート回路
６が備えられる。このような図１９に示される先行技術
では、前述の先行技術（ｂ）を実現するものであって、
上述のようにリードオンリメモリ４のメモリ容量を大き
くする必要があるという問題がある。
【０００５】
【発明が解決しようとする課題】本発明の目的は、ガロ
ア拡大体ＧＦ（２m ）上の加算、乗算、除算などの操作
が簡単な構成で実現することができるようにした誤り訂
正回路を提供することである。
ア拡大体ＧＦ（２m ）上の加算、乗算、除算などの操作
が簡単な構成で実現することができるようにした誤り訂
正回路を提供することである。
【０００６】また従来から、誤り位置の導出には、チエ
ン探索法が用いられており、この方法を実現する構成で
は、外部クロック信号を必要とし、したがってリアルタ
イム処理ができないという問題がある。
ン探索法が用いられており、この方法を実現する構成で
は、外部クロック信号を必要とし、したがってリアルタ
イム処理ができないという問題がある。
【０００７】また本発明の目的は、ＢＣＨ符号信号の読
み込みと同時に誤り位置の探索が可能になるようにした
誤り訂正回路を提供することである。
み込みと同時に誤り位置の探索が可能になるようにした
誤り訂正回路を提供することである。
【０００８】
【課題を解決するための手段】本発明は、（ａ）ＢＣＨ
符号信号を（ｘ−α）によって割り算して第１シンドロ
ームＳ１を求める第１シンドロームレジスタ９と、 （ｂ）前記ＢＣＨ符号信号を（ｘ−α3 ）による割り算
を行って第２シンドロームＳ３を求める第２シンドロー
ムレジスタ１０と、 （ｃ）誤り位置多項式の係数導出回路１２であって、 （ｃ１）αをｍ次のガロア拡大体ＧＦ（２m）の原始元
とし、α，α3を根にもつ２重誤り訂正（ｎ，ｋ）ＢＣ
Ｈ符号の復号において、（２m −１）個の第１α乗算器
ＭＸ１〜ＭＸｉを直列につなぎ、初段の第１α乗算器Ｍ
Ｘ１にα0を与えることによって、ＧＦ（２m）の元α〜
α（２m−１）（以下、αの（２m−１）乗を表す）を作
成する元作成回路１９と、 （ｃ２）第１シンドロームＳ１と元作成回路１９の出力
とに応答し、Ｓ１α〜Ｓ１α（２m−１）を求めるべき
乗回路２１であって、（２m−１）個の第１加算器ＡＤ
０〜ＡＤｉを有し、各加算器ＡＤ０〜ＡＤｉは、Ｓ１の
各ビットａ０〜ａ３と、α１〜α（２m−１）の各ビッ
トｂ０〜ｂ３とが与えられる第１排他的論理和ゲートＥ
Ｒ０〜ＥＲ３と、これらの第１排他的論理和ゲートＥＲ
０〜ＥＲ３の出力が与えられる第１ＮＡＮＤゲートＧ０
とを有し、各第１加算器ＡＤ０〜ＡＤｉは、出力Ｌ０〜
Ｌｉを導出するべき乗回路２１と、 （ｃ３）第１シンドロームＳ１とＧＦ（２m）上の（２m
−１）個の元を乗算する第１乗算回路２３であって、
（２m−１）個の第２α乗算器ＭＸ１１〜ＭＸ１ｉを直
列につなぎ、初段の第２α乗算器ＭＸ１１に第１シンド
ロームＳ１を与える第１乗算回路２３と、 （ｃ４）第１乗算回路２３の結果と、べき乗回路２１の
結果とに基づいて、Ｓ１2 を求めるＳ１2サーチ回路２
２であって、各第２α乗算器ＭＸ１１〜ＭＸ１ｉの出力
と、べき乗回路２１の各第１加算器ＡＤ０〜ＡＤｉの出
力Ｌ０〜Ｌｉとが、与えられる第１ＡＮＤゲートＧ１０
〜Ｇ１ｉと、第１ＡＮＤゲートＧ１０〜Ｇ１ｉの出力が
与えられ、Ｓ１2を出力する第２排他的論理和ゲートＥ
Ｒ１０とを有するＳ１2サーチ回路２２と、 （ｃ５）Ｓ１の逆元を求める逆元サーチ回路２５であっ
て、（２m−１）個の第３排他的論理和ゲートＥＲ３０
〜ＥＲ３ｉであって、各第３排他的論理和ゲートＥＲ３
０〜ＥＲ３ｉには、α0と、第１乗算回路２３の第２乗
算器ＭＸ１１〜ＭＸ１ｉの出力とが与えられる第３排他
的論理和ゲートＥＲ３０〜ＥＲ３ｉと、第３排他的論理
和ゲートＥＲ３０〜ＥＲ３ｉの各出力の全ビットが論理
「０」となることを検出するＮＡＮＤゲートによって実
現される全零検知回路ＡＺ０〜ＡＺｉとを有する逆元サ
ーチ回路２５と、 （ｃ６）第２シンドロームＳ３とＧＦ（２m）上の（２m
−１）個の元を乗算する第２乗算回路２７であって、
（２m−１）個の第３α乗算器ＭＸ２１〜ＭＸ２ｉを直
列につなぎ、初段の第３α乗算器ＭＸ２１に、第２シン
ドロームＳ３を与える第２乗算回路２７と、 （ｃ７）第２乗算回路２７の結果と逆元サーチ回路２５
からの結果とに基づいてＳ３／Ｓ１を求めるＳ３／Ｓ１
サーチ回路２６であって、 （ｃ７−１）（２m−１）個の第２ＡＮＤゲートＧ２０
〜Ｇ２ｉであって、各第２ＡＮＤゲートＧ２０〜Ｇ２ｉ
は、逆元サーチ回路２５の各全零検知回路ＡＺ０〜ＡＺ
ｉの出力Ｌ２０〜Ｌ２ｉと、第２乗算回路２７の第３α
乗算器ＭＸ２１〜ＭＸ２ｉからの出力とが与えられる第
２ＡＮＤゲートＧ２０〜Ｇ２ｉと、 （ｃ７−２）第２ＡＮＤゲートＧ２０〜Ｇ２ｉの出力が
与えられ、Ｓ３／Ｓ１を導出する第４排他的論理和ゲー
トＥＲ５とを有するＳ３／Ｓ１サーチ回路２６と、 （ｃ８）Ｓ１2 とＳ３／Ｓ１との結果を加算する回路２
８であって、Ｓ１2サーチ回路２２の第２排他的論理和
ゲートＥＲ１０の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路
２６の第４排他的論理和ゲートＥＲ５の出力Ｓ３／Ｓ１
とが、各ビット毎に与えられ、（Ｓ１2＋Ｓ３／Ｓ１）
を出力する第５排他的論理和ゲートＥＲ６０〜ＥＲ６３
を有する加算回路２８とを含む誤り位置多項式の係数導
出回路１２と、 （ｄ）前記誤り位置多項式の係数導出回路の出力に応答
してチエン探索を行い、誤り位置を表すチエン探索回路
１３と、 （ｅ）前記ＢＣＨ符号信号を受信してストアするデータ
のレジスタ１１と、 （ｆ）チエン探索回路の出力とデータレジスタの出力と
を演算して訂正後のＢＣＨ符号信号を得る演算回路１４
とを含むことを特徴とする誤り訂正回路である。
符号信号を（ｘ−α）によって割り算して第１シンドロ
ームＳ１を求める第１シンドロームレジスタ９と、 （ｂ）前記ＢＣＨ符号信号を（ｘ−α3 ）による割り算
を行って第２シンドロームＳ３を求める第２シンドロー
ムレジスタ１０と、 （ｃ）誤り位置多項式の係数導出回路１２であって、 （ｃ１）αをｍ次のガロア拡大体ＧＦ（２m）の原始元
とし、α，α3を根にもつ２重誤り訂正（ｎ，ｋ）ＢＣ
Ｈ符号の復号において、（２m −１）個の第１α乗算器
ＭＸ１〜ＭＸｉを直列につなぎ、初段の第１α乗算器Ｍ
Ｘ１にα0を与えることによって、ＧＦ（２m）の元α〜
α（２m−１）（以下、αの（２m−１）乗を表す）を作
成する元作成回路１９と、 （ｃ２）第１シンドロームＳ１と元作成回路１９の出力
とに応答し、Ｓ１α〜Ｓ１α（２m−１）を求めるべき
乗回路２１であって、（２m−１）個の第１加算器ＡＤ
０〜ＡＤｉを有し、各加算器ＡＤ０〜ＡＤｉは、Ｓ１の
各ビットａ０〜ａ３と、α１〜α（２m−１）の各ビッ
トｂ０〜ｂ３とが与えられる第１排他的論理和ゲートＥ
Ｒ０〜ＥＲ３と、これらの第１排他的論理和ゲートＥＲ
０〜ＥＲ３の出力が与えられる第１ＮＡＮＤゲートＧ０
とを有し、各第１加算器ＡＤ０〜ＡＤｉは、出力Ｌ０〜
Ｌｉを導出するべき乗回路２１と、 （ｃ３）第１シンドロームＳ１とＧＦ（２m）上の（２m
−１）個の元を乗算する第１乗算回路２３であって、
（２m−１）個の第２α乗算器ＭＸ１１〜ＭＸ１ｉを直
列につなぎ、初段の第２α乗算器ＭＸ１１に第１シンド
ロームＳ１を与える第１乗算回路２３と、 （ｃ４）第１乗算回路２３の結果と、べき乗回路２１の
結果とに基づいて、Ｓ１2 を求めるＳ１2サーチ回路２
２であって、各第２α乗算器ＭＸ１１〜ＭＸ１ｉの出力
と、べき乗回路２１の各第１加算器ＡＤ０〜ＡＤｉの出
力Ｌ０〜Ｌｉとが、与えられる第１ＡＮＤゲートＧ１０
〜Ｇ１ｉと、第１ＡＮＤゲートＧ１０〜Ｇ１ｉの出力が
与えられ、Ｓ１2を出力する第２排他的論理和ゲートＥ
Ｒ１０とを有するＳ１2サーチ回路２２と、 （ｃ５）Ｓ１の逆元を求める逆元サーチ回路２５であっ
て、（２m−１）個の第３排他的論理和ゲートＥＲ３０
〜ＥＲ３ｉであって、各第３排他的論理和ゲートＥＲ３
０〜ＥＲ３ｉには、α0と、第１乗算回路２３の第２乗
算器ＭＸ１１〜ＭＸ１ｉの出力とが与えられる第３排他
的論理和ゲートＥＲ３０〜ＥＲ３ｉと、第３排他的論理
和ゲートＥＲ３０〜ＥＲ３ｉの各出力の全ビットが論理
「０」となることを検出するＮＡＮＤゲートによって実
現される全零検知回路ＡＺ０〜ＡＺｉとを有する逆元サ
ーチ回路２５と、 （ｃ６）第２シンドロームＳ３とＧＦ（２m）上の（２m
−１）個の元を乗算する第２乗算回路２７であって、
（２m−１）個の第３α乗算器ＭＸ２１〜ＭＸ２ｉを直
列につなぎ、初段の第３α乗算器ＭＸ２１に、第２シン
ドロームＳ３を与える第２乗算回路２７と、 （ｃ７）第２乗算回路２７の結果と逆元サーチ回路２５
からの結果とに基づいてＳ３／Ｓ１を求めるＳ３／Ｓ１
サーチ回路２６であって、 （ｃ７−１）（２m−１）個の第２ＡＮＤゲートＧ２０
〜Ｇ２ｉであって、各第２ＡＮＤゲートＧ２０〜Ｇ２ｉ
は、逆元サーチ回路２５の各全零検知回路ＡＺ０〜ＡＺ
ｉの出力Ｌ２０〜Ｌ２ｉと、第２乗算回路２７の第３α
乗算器ＭＸ２１〜ＭＸ２ｉからの出力とが与えられる第
２ＡＮＤゲートＧ２０〜Ｇ２ｉと、 （ｃ７−２）第２ＡＮＤゲートＧ２０〜Ｇ２ｉの出力が
与えられ、Ｓ３／Ｓ１を導出する第４排他的論理和ゲー
トＥＲ５とを有するＳ３／Ｓ１サーチ回路２６と、 （ｃ８）Ｓ１2 とＳ３／Ｓ１との結果を加算する回路２
８であって、Ｓ１2サーチ回路２２の第２排他的論理和
ゲートＥＲ１０の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路
２６の第４排他的論理和ゲートＥＲ５の出力Ｓ３／Ｓ１
とが、各ビット毎に与えられ、（Ｓ１2＋Ｓ３／Ｓ１）
を出力する第５排他的論理和ゲートＥＲ６０〜ＥＲ６３
を有する加算回路２８とを含む誤り位置多項式の係数導
出回路１２と、 （ｄ）前記誤り位置多項式の係数導出回路の出力に応答
してチエン探索を行い、誤り位置を表すチエン探索回路
１３と、 （ｅ）前記ＢＣＨ符号信号を受信してストアするデータ
のレジスタ１１と、 （ｆ）チエン探索回路の出力とデータレジスタの出力と
を演算して訂正後のＢＣＨ符号信号を得る演算回路１４
とを含むことを特徴とする誤り訂正回路である。
【０００９】また本発明は、（ａ）ＢＣＨ符号信号を
（ｘ−α）によって割り算して第１シンドロームＳ１を
求める第１シンドロームレジスタ９と、 （ｂ）前記ＢＣＨ符号信号を（ｘ−α3 ）による割り算
を行って第２シンドロームＳ３を求める第２シンドロー
ムレジスタ１０と、 （ｃ）誤り位置多項式の係数導出回路１２であって、 （ｃ１）αをｍ次のガロア拡大体ＧＦ（２m）の原始元
とし、α，α3を根にもつ２重誤り訂正（ｎ，ｋ）ＢＣ
Ｈ符号の復号において、（２m −１）個の第１α乗算器
ＭＸ１〜ＭＸｉを直列につなぎ、初段の第１α乗算器Ｍ
Ｘ１にα0を与えることによって、ＧＦ（２m）の元α〜
α（２m−１）（以下、αの（２m−１）乗を表す）を作
成する元作成回路１９と、 （ｃ２）第１シンドロームＳ１と元作成回路１９の出力
とに応答し、Ｓ１α〜Ｓ１α（２m−１）を求めるべき
乗回路２１であって、（２m−１）個の第１加算器ＡＤ
０〜ＡＤｉを有し、各加算器ＡＤ０〜ＡＤｉは、Ｓ１の
各ビットａ０〜ａ３と、α１〜α（２m−１）の各ビッ
トｂ０〜ｂ３とが与えられる第１排他的論理和ゲートＥ
Ｒ０〜ＥＲ３と、これらの第１排他的論理和ゲートＥＲ
０〜ＥＲ３の出力が与えられる第１ＮＡＮＤゲートＧ０
とを有し、各第１加算器ＡＤ０〜ＡＤｉは、出力Ｌ０〜
Ｌｉを導出するべき乗回路２１と、 （ｃ３）第１シンドロームＳ１とＧＦ（２m）上の（２m
−１）個の元を乗算する第１乗算回路２３であって、
（２m−１）個の第２α乗算器ＭＸ１１〜ＭＸ１ｉを直
列につなぎ、初段の第２α乗算器ＭＸ１１に第１シンド
ロームＳ１を与える第１乗算回路２３と、 （ｃ４）第１乗算回路２３の結果と、べき乗回路２１の
結果とに基づいて、Ｓ１2 を求めるＳ１2サーチ回路２
２であって、各第２α乗算器ＭＸ１１〜ＭＸ１ｉの出力
と、べき乗回路２１の各第１加算器ＡＤ０〜ＡＤｉの出
力Ｌ０〜Ｌｉとが、与えられる第１ＡＮＤゲートＧ１０
〜Ｇ１ｉと、第１ＡＮＤゲートＧ１０〜Ｇ１ｉの出力が
与えられ、Ｓ１2を出力する第２排他的論理和ゲートＥ
Ｒ１０とを有するＳ１2サーチ回路２２と、 （ｃ５）Ｓ１の逆元を求める逆元サーチ回路２５であっ
て、（２m−１）個の第３排他的論理和ゲートＥＲ３０
〜ＥＲ３ｉであって、各第３排他的論理和ゲートＥＲ３
０〜ＥＲ３ｉには、α0と、第１乗算回路２３の第２乗
算器ＭＸ１１〜ＭＸ１ｉの出力とが与えられる第３排他
的論理和ゲートＥＲ３０〜ＥＲ３ｉと、第３排他的論理
和ゲートＥＲ３０〜ＥＲ３ｉの各出力の全ビットが論理
「０」となることを検出するＮＡＮＤゲートによって実
現される全零検知回路ＡＺ０〜ＡＺｉとを有する逆元サ
ーチ回路２５と、 （ｃ６）第２シンドロームＳ３とＧＦ（２m）上の（２m
−１）個の元を乗算する第２乗算回路２７であって、
（２m−１）個の第３α乗算器ＭＸ２１〜ＭＸ２ｉを直
列につなぎ、初段の第３α乗算器ＭＸ２１に、第２シン
ドロームＳ３を与える第２乗算回路２７と、 （ｃ７）第２乗算回路２７の結果と逆元サーチ回路２５
からの結果とに基づいてＳ３／Ｓ１を求めるＳ３／Ｓ１
サーチ回路２６であって、 （ｃ７−１）（２m−１）個の第２ＡＮＤゲートＧ２０
〜Ｇ２ｉであって、各第２ＡＮＤゲートＧ２０〜Ｇ２ｉ
は、逆元サーチ回路２５の各全零検知回路ＡＺ０〜ＡＺ
ｉの出力Ｌ２０〜Ｌ２ｉと、第２乗算回路２７の第３α
乗算器ＭＸ２１〜ＭＸ２ｉからの出力とが与えられる第
２ＡＮＤゲートＧ２０〜Ｇ２ｉと、 （ｃ７−２）第２ＡＮＤゲートＧ２０〜Ｇ２ｉの出力が
与えられ、Ｓ３／Ｓ１を導出する第４排他的論理和ゲー
トＥＲ５とを有するＳ３／Ｓ１サーチ回路２６と、 （ｃ８）Ｓ１2 とＳ３／Ｓ１との結果を加算する回路２
８であって、Ｓ１2サーチ回路２２の第２排他的論理和
ゲートＥＲ１０の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路
２６の第４排他的論理和ゲートＥＲ５の出力Ｓ３／Ｓ１
とが、各ビット毎に与えられ、（Ｓ１2＋Ｓ３／Ｓ１）
を出力する第５排他的論理和ゲートＥＲ６０〜ＥＲ６３
を有する加算回路２８とを含む誤り位置多項式の係数導
出回路１２と、 （ｄ）誤り位置検出回路であって、 （ｄ１）その誤り位置多項式を σ（ｚ） ＝ １ ＋ Ａｚ ＋ Ｂｚ2 としたとき、（２m −２）個の第４α乗算器ＭＸ３１〜
ＭＸ３ｉを直列につなぎ、初段の第４α乗算器ＭＸ３１
に、Ｓ１2サーチ回路２２の第２排他的論理和ゲートＥ
Ｒ１０の出力Ｓ１2であるＡを与えることによってＡαi
（ｉ＝０，１，２，…，２m−２）を出力する第１演算
回路４１と、 （ｄ２）（２m −２）個の第５α乗算器を直列につな
ぎ、初段の第５α乗算器に、加算回路２８の第５排他的
論理和ゲートＥＲ６０〜ＥＲ６３からの出力（Ｓ１2＋
Ｓ３／Ｓ１）であるＢを与えることによってＢαj（ｊ
＝０，１，２，…，２m−２）を出力する第２演算回路
４２と、 （ｄ３）Ｂαk（ｋ＝０，１，２，…，２m−２）に対し
第６α乗算器ＭＸ４１；ＭＸ５１，ＭＸ５２；ＭＸ６
１，ＭＸ６２，ＭＸ６３；…をｋ個つなぐことによって
Ｂ（αk）2を出力する第３演算回路４３と、 （ｄ４）第１演算回路４１と第３演算回路４３との出力
に基づいて、前記誤り位置多項式が、 σ（αL）＝０ （Ｌ＝０，１，２，…，２m−２） となるＬを判別し、受信符号語の誤り位置を指示する出
力を導出する回路４４であって、ＡαiおよびＢ（αi）
2（ｉ＝０，１，…，２m−２）が与えられる第３加算器
ＡＤ１０〜ＡＤ１ｉを有し、各第３加算器ＡＤ１０〜Ａ
Ｄ１ｉは、ＡαiおよびＢ（αi）2の各ビットが与えら
れる各ビット毎の第６排他的論理和ゲートＥＲ７０〜Ｅ
Ｒ７m-1と、第２ビット以降のビットａ１〜ａm-1，ｂ１
〜ｂm-1が与えられる第６排他的論理和ゲートＥＲ７１
〜ＥＲ７m-1の出力が与えられる第２ＮＡＮＤゲートＧ
３と、第１ビットａ０，ｂ０が与えられる第６排他的論
理和ゲートＥＲ７０と、第２ＮＡＮＤゲートＧ３との出
力が与えられるＡＮＤゲートＧ２とを有する誤り位置指
示出力導出回路４４とを含む誤り位置検出回路５３と、 （ｅ）Ｓ１＝０，Ｓ３≠０のとき、訂正不可能な誤りが
生じたとして訂正出力をクリアする訂正制御回路１７
と、 （ｆ）ＢＣＨ符号信号をストアして誤り位置検出回路と
訂正制御回路の出力によって訂正を行って訂正後のＢＣ
Ｈ符号信号を得るデータレジスタ１８とを含むことを特
徴とする誤り訂正回路である。
（ｘ−α）によって割り算して第１シンドロームＳ１を
求める第１シンドロームレジスタ９と、 （ｂ）前記ＢＣＨ符号信号を（ｘ−α3 ）による割り算
を行って第２シンドロームＳ３を求める第２シンドロー
ムレジスタ１０と、 （ｃ）誤り位置多項式の係数導出回路１２であって、 （ｃ１）αをｍ次のガロア拡大体ＧＦ（２m）の原始元
とし、α，α3を根にもつ２重誤り訂正（ｎ，ｋ）ＢＣ
Ｈ符号の復号において、（２m −１）個の第１α乗算器
ＭＸ１〜ＭＸｉを直列につなぎ、初段の第１α乗算器Ｍ
Ｘ１にα0を与えることによって、ＧＦ（２m）の元α〜
α（２m−１）（以下、αの（２m−１）乗を表す）を作
成する元作成回路１９と、 （ｃ２）第１シンドロームＳ１と元作成回路１９の出力
とに応答し、Ｓ１α〜Ｓ１α（２m−１）を求めるべき
乗回路２１であって、（２m−１）個の第１加算器ＡＤ
０〜ＡＤｉを有し、各加算器ＡＤ０〜ＡＤｉは、Ｓ１の
各ビットａ０〜ａ３と、α１〜α（２m−１）の各ビッ
トｂ０〜ｂ３とが与えられる第１排他的論理和ゲートＥ
Ｒ０〜ＥＲ３と、これらの第１排他的論理和ゲートＥＲ
０〜ＥＲ３の出力が与えられる第１ＮＡＮＤゲートＧ０
とを有し、各第１加算器ＡＤ０〜ＡＤｉは、出力Ｌ０〜
Ｌｉを導出するべき乗回路２１と、 （ｃ３）第１シンドロームＳ１とＧＦ（２m）上の（２m
−１）個の元を乗算する第１乗算回路２３であって、
（２m−１）個の第２α乗算器ＭＸ１１〜ＭＸ１ｉを直
列につなぎ、初段の第２α乗算器ＭＸ１１に第１シンド
ロームＳ１を与える第１乗算回路２３と、 （ｃ４）第１乗算回路２３の結果と、べき乗回路２１の
結果とに基づいて、Ｓ１2 を求めるＳ１2サーチ回路２
２であって、各第２α乗算器ＭＸ１１〜ＭＸ１ｉの出力
と、べき乗回路２１の各第１加算器ＡＤ０〜ＡＤｉの出
力Ｌ０〜Ｌｉとが、与えられる第１ＡＮＤゲートＧ１０
〜Ｇ１ｉと、第１ＡＮＤゲートＧ１０〜Ｇ１ｉの出力が
与えられ、Ｓ１2を出力する第２排他的論理和ゲートＥ
Ｒ１０とを有するＳ１2サーチ回路２２と、 （ｃ５）Ｓ１の逆元を求める逆元サーチ回路２５であっ
て、（２m−１）個の第３排他的論理和ゲートＥＲ３０
〜ＥＲ３ｉであって、各第３排他的論理和ゲートＥＲ３
０〜ＥＲ３ｉには、α0と、第１乗算回路２３の第２乗
算器ＭＸ１１〜ＭＸ１ｉの出力とが与えられる第３排他
的論理和ゲートＥＲ３０〜ＥＲ３ｉと、第３排他的論理
和ゲートＥＲ３０〜ＥＲ３ｉの各出力の全ビットが論理
「０」となることを検出するＮＡＮＤゲートによって実
現される全零検知回路ＡＺ０〜ＡＺｉとを有する逆元サ
ーチ回路２５と、 （ｃ６）第２シンドロームＳ３とＧＦ（２m）上の（２m
−１）個の元を乗算する第２乗算回路２７であって、
（２m−１）個の第３α乗算器ＭＸ２１〜ＭＸ２ｉを直
列につなぎ、初段の第３α乗算器ＭＸ２１に、第２シン
ドロームＳ３を与える第２乗算回路２７と、 （ｃ７）第２乗算回路２７の結果と逆元サーチ回路２５
からの結果とに基づいてＳ３／Ｓ１を求めるＳ３／Ｓ１
サーチ回路２６であって、 （ｃ７−１）（２m−１）個の第２ＡＮＤゲートＧ２０
〜Ｇ２ｉであって、各第２ＡＮＤゲートＧ２０〜Ｇ２ｉ
は、逆元サーチ回路２５の各全零検知回路ＡＺ０〜ＡＺ
ｉの出力Ｌ２０〜Ｌ２ｉと、第２乗算回路２７の第３α
乗算器ＭＸ２１〜ＭＸ２ｉからの出力とが与えられる第
２ＡＮＤゲートＧ２０〜Ｇ２ｉと、 （ｃ７−２）第２ＡＮＤゲートＧ２０〜Ｇ２ｉの出力が
与えられ、Ｓ３／Ｓ１を導出する第４排他的論理和ゲー
トＥＲ５とを有するＳ３／Ｓ１サーチ回路２６と、 （ｃ８）Ｓ１2 とＳ３／Ｓ１との結果を加算する回路２
８であって、Ｓ１2サーチ回路２２の第２排他的論理和
ゲートＥＲ１０の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路
２６の第４排他的論理和ゲートＥＲ５の出力Ｓ３／Ｓ１
とが、各ビット毎に与えられ、（Ｓ１2＋Ｓ３／Ｓ１）
を出力する第５排他的論理和ゲートＥＲ６０〜ＥＲ６３
を有する加算回路２８とを含む誤り位置多項式の係数導
出回路１２と、 （ｄ）誤り位置検出回路であって、 （ｄ１）その誤り位置多項式を σ（ｚ） ＝ １ ＋ Ａｚ ＋ Ｂｚ2 としたとき、（２m −２）個の第４α乗算器ＭＸ３１〜
ＭＸ３ｉを直列につなぎ、初段の第４α乗算器ＭＸ３１
に、Ｓ１2サーチ回路２２の第２排他的論理和ゲートＥ
Ｒ１０の出力Ｓ１2であるＡを与えることによってＡαi
（ｉ＝０，１，２，…，２m−２）を出力する第１演算
回路４１と、 （ｄ２）（２m −２）個の第５α乗算器を直列につな
ぎ、初段の第５α乗算器に、加算回路２８の第５排他的
論理和ゲートＥＲ６０〜ＥＲ６３からの出力（Ｓ１2＋
Ｓ３／Ｓ１）であるＢを与えることによってＢαj（ｊ
＝０，１，２，…，２m−２）を出力する第２演算回路
４２と、 （ｄ３）Ｂαk（ｋ＝０，１，２，…，２m−２）に対し
第６α乗算器ＭＸ４１；ＭＸ５１，ＭＸ５２；ＭＸ６
１，ＭＸ６２，ＭＸ６３；…をｋ個つなぐことによって
Ｂ（αk）2を出力する第３演算回路４３と、 （ｄ４）第１演算回路４１と第３演算回路４３との出力
に基づいて、前記誤り位置多項式が、 σ（αL）＝０ （Ｌ＝０，１，２，…，２m−２） となるＬを判別し、受信符号語の誤り位置を指示する出
力を導出する回路４４であって、ＡαiおよびＢ（αi）
2（ｉ＝０，１，…，２m−２）が与えられる第３加算器
ＡＤ１０〜ＡＤ１ｉを有し、各第３加算器ＡＤ１０〜Ａ
Ｄ１ｉは、ＡαiおよびＢ（αi）2の各ビットが与えら
れる各ビット毎の第６排他的論理和ゲートＥＲ７０〜Ｅ
Ｒ７m-1と、第２ビット以降のビットａ１〜ａm-1，ｂ１
〜ｂm-1が与えられる第６排他的論理和ゲートＥＲ７１
〜ＥＲ７m-1の出力が与えられる第２ＮＡＮＤゲートＧ
３と、第１ビットａ０，ｂ０が与えられる第６排他的論
理和ゲートＥＲ７０と、第２ＮＡＮＤゲートＧ３との出
力が与えられるＡＮＤゲートＧ２とを有する誤り位置指
示出力導出回路４４とを含む誤り位置検出回路５３と、 （ｅ）Ｓ１＝０，Ｓ３≠０のとき、訂正不可能な誤りが
生じたとして訂正出力をクリアする訂正制御回路１７
と、 （ｆ）ＢＣＨ符号信号をストアして誤り位置検出回路と
訂正制御回路の出力によって訂正を行って訂正後のＢＣ
Ｈ符号信号を得るデータレジスタ１８とを含むことを特
徴とする誤り訂正回路である。
【００１０】
【００１１】
【００１２】
【作用】誤り位置多項式導出回路についてまず説明す
る。２重誤り訂正ＢＣＨ符号は、ガロア拡大体ＧＦ（２
m）のαを原始元とするとき、α，α3を根にもつ。い
ま、誤り位置をＬ１，Ｌ２とするとき、シンドロームＳ
１，Ｓ３は、 Ｓ１ ＝ αL1 ＋ αL2 …（３） Ｓ３ ＝ α3L1 ＋ α3L2 …（４） となる。これを用いて誤り位置多項式は、 σ（ｘ） ＝ １ ＋ Ｓ１ｘ ＋ （Ｓ１2 ＋Ｓ３／Ｓ１）ｘ2 …（５） となる。ｘの係数Ｓ１は求められているので、（Ｓ１2
＋Ｓ３／Ｓ１）を求めればよい。この計算に、従来はＲ
ＯＭによる参照が行われていた。しかしゲート回路によ
り直接Ｓ１2 およびＳ３／Ｓ１の演算は難しい。そこで
本発明では次のように構成する。
る。２重誤り訂正ＢＣＨ符号は、ガロア拡大体ＧＦ（２
m）のαを原始元とするとき、α，α3を根にもつ。い
ま、誤り位置をＬ１，Ｌ２とするとき、シンドロームＳ
１，Ｓ３は、 Ｓ１ ＝ αL1 ＋ αL2 …（３） Ｓ３ ＝ α3L1 ＋ α3L2 …（４） となる。これを用いて誤り位置多項式は、 σ（ｘ） ＝ １ ＋ Ｓ１ｘ ＋ （Ｓ１2 ＋Ｓ３／Ｓ１）ｘ2 …（５） となる。ｘの係数Ｓ１は求められているので、（Ｓ１2
＋Ｓ３／Ｓ１）を求めればよい。この計算に、従来はＲ
ＯＭによる参照が行われていた。しかしゲート回路によ
り直接Ｓ１2 およびＳ３／Ｓ１の演算は難しい。そこで
本発明では次のように構成する。
【００１３】まず、Ｓ１2 であるが、Ｓ１はガロア拡大
体のＧＦ（２m）上の（２m−１）個の元のいずれかであ
る。よってα乗算回路ＭＸ１〜ＭＸｉを（２m −１）個
直列につなぐことにより、
体のＧＦ（２m）上の（２m−１）個の元のいずれかであ
る。よってα乗算回路ＭＸ１〜ＭＸｉを（２m −１）個
直列につなぐことにより、
【００１４】
【数１】
【００１５】を求めればＳ12はこのうちのいずれかであ
る。今、Ｓ１＝αiとすると、 Ｓ１2 ＝ Ｓ１αi ｍｏｄ ２m −１ …（６） であるから、前記グループＧＲ１のうち、αiの演算結
果がＳ１2になる。前述の式６においてｍｏｄは、元の
べき数の演算結果を２m −１で割った剰余をとることを
意味する。
る。今、Ｓ１＝αiとすると、 Ｓ１2 ＝ Ｓ１αi ｍｏｄ ２m −１ …（６） であるから、前記グループＧＲ１のうち、αiの演算結
果がＳ１2になる。前述の式６においてｍｏｄは、元の
べき数の演算結果を２m −１で割った剰余をとることを
意味する。
【００１６】一方、Ｓ３／Ｓ１を演算するにはＳ１の逆
元を求める必要がある。前述と同様にＳ１＝αiとする
と、αiの逆元αjは、 αi・αj ＝ αo ｍｏｄ ２m −１ …（７） となるものであり、これによって、Ｓ３／Ｓ１は、 Ｓ３／Ｓ１ ＝ Ｓ３・α-i ＝ Ｓ３・αj ｍｏｄ ２m −１ …（８） で求められる。
元を求める必要がある。前述と同様にＳ１＝αiとする
と、αiの逆元αjは、 αi・αj ＝ αo ｍｏｄ ２m −１ …（７） となるものであり、これによって、Ｓ３／Ｓ１は、 Ｓ３／Ｓ１ ＝ Ｓ３・α-i ＝ Ｓ３・αj ｍｏｄ ２m −１ …（８） で求められる。
【００１７】まず、前述のグループＧＲ１と同様に、
【００１８】
【数２】
【００１９】を求めておく。そしてグループＧＲ１の中
から Ｓ１αj ＝ αo ｍｏｄ ２m −１ …（９） となるαjを探す。そうすればαjがＳ１の逆元であるか
らグループＧＲ２のうち、αjによるＳ３との乗算結果
が求めるＳ３／Ｓ１である。
から Ｓ１αj ＝ αo ｍｏｄ ２m −１ …（９） となるαjを探す。そうすればαjがＳ１の逆元であるか
らグループＧＲ２のうち、αjによるＳ３との乗算結果
が求めるＳ３／Ｓ１である。
【００２０】以上のようにして演算したＳ１2とＳ３／
Ｓ１を加算すれば、それが式５のｘ2についての係数と
なる。
Ｓ１を加算すれば、それが式５のｘ2についての係数と
なる。
【００２１】次に誤り位置検出回路について説明する。
【００２２】前述の式５に対して σ（αi ） ＝ ０ （ｉ＝０，１，…，２m −２） …（10） となるとき、 ｉ＋ｊ ｍｏｄ ２m−１＝０ となるｊが誤りの位置を示す。よって誤り位置の導出に
は、αi（ｉ＝１，２，…，２m−２）を逐次代入し、σ
（αi）＝０を調べればよい。
は、αi（ｉ＝１，２，…，２m−２）を逐次代入し、σ
（αi）＝０を調べればよい。
【００２３】これをハード的に実現するため、チエン探
索法が用いられるが、符号長分のクロックが必要とな
る。そこで、本発明では、次のようにした。
索法が用いられるが、符号長分のクロックが必要とな
る。そこで、本発明では、次のようにした。
【００２４】まず、Ａ，Ｂに対し、α乗算回路を２m−
２個直列に入力することで
２個直列に入力することで
【００２５】
【数３】
【００２６】が同時に計算できる。Ａα0，Ｂα0は、
Ａ，Ｂそのものと考える。
Ａ，Ｂそのものと考える。
【００２７】前述のグループＧＲ３は、式５の第２項目
をすべてのαi（ｉ＝０，１，…，２m−２）について計
算したものである。しかし式５の３項目を求めるには、
αi（ｉ＝０，１，…，２m−２）の２乗が必要である。
をすべてのαi（ｉ＝０，１，…，２m−２）について計
算したものである。しかし式５の３項目を求めるには、
αi（ｉ＝０，１，…，２m−２）の２乗が必要である。
【００２８】本発明では、前述のグループＧＲ４のＢα
i（ｉ＝０，１，…，２m−２）に対し、α乗算器をｉ個
直列につなぐことにより、 （Ｂαi）・αi ＝ Ｂ（αi）2 (ｉ＝０，１，…，２m−２) …（11） を得ている。
i（ｉ＝０，１，…，２m−２）に対し、α乗算器をｉ個
直列につなぐことにより、 （Ｂαi）・αi ＝ Ｂ（αi）2 (ｉ＝０，１，…，２m−２) …（11） を得ている。
【００２９】Ａαi，Ｂ（αi）2（ｉ＝０，１，…，２m
−２）が計算できたので、これを各々のｉについて加算
し、 １ ＋ Ａαi ＋ Ｂ（αi）2 ＝ ０ …（12） つまり、 となれば、ｉ＋ｊ ｍｏｄ ２m −１を満たすｊが誤り
の位置を示す。
−２）が計算できたので、これを各々のｉについて加算
し、 １ ＋ Ａαi ＋ Ｂ（αi）2 ＝ ０ …（12） つまり、 となれば、ｉ＋ｊ ｍｏｄ ２m −１を満たすｊが誤り
の位置を示す。
【００３０】以上の演算はすべてのαi（ｉ＝０，１，
…，２m −２）に対し、同時に行うため、誤り位置の探
索が高速にできる。
…，２m −２）に対し、同時に行うため、誤り位置の探
索が高速にできる。
【００３１】
【実施例】図１は、本発明の一実施例の誤り訂正回路の
全体の構成を示すブロック図である。ＢＣＨ符号信号
は、ライン８から入力され、（ｘ−α）によって割り算
してシンドロームＳ１を求めるｍビットのシンドローム
レジスタ９と、（ｘ−α3 ）によるＢＣＨ符号信号の割
り算を行ってシンドロームＳ３を求めるｍビットのシン
ドロームレジスタ１０とに与えられる。またこの誤り訂
正回路には、ＢＣＨ符号信号が与えられるｎビットデー
タレジスタ１１が備えられ、さらに各シンドロームレジ
スタ９，１０からのシンドロームＳ１，Ｓ３がそれぞれ
与えられる誤り位置多項式の係数導出回路１２が設けら
れる。この誤り位置多項式の係数導出回路１２の出力Ｓ
１，Ｓ１2 ＋Ｓ３／Ｓ１は、チエン探索回路１３に与え
られ、排他的論理和ゲート１４は、チエン探索回路１３
の出力とデータレジスタ１１の出力とを演算して訂正後
のＢＣＨ符号信号を得る。こうしてｎビット符号語が読
み込まれた時点で、シンドロームレジスタ９，１０によ
ってシンドロームＳ１，Ｓ３が計算され、さらに誤り位
置多項式の係数も同時に計算される。その後、α-i（ｉ
＝０，１，…，２m −２）を代入してゆき、σ（αi ）
＝０となるｉが誤り位置を表す。この演算は、チエン探
索回路１３で容易に実現することができる。チエン探索
回路は、たとえば今井秀樹著「符号理論」第１６６頁に
開示されている。
全体の構成を示すブロック図である。ＢＣＨ符号信号
は、ライン８から入力され、（ｘ−α）によって割り算
してシンドロームＳ１を求めるｍビットのシンドローム
レジスタ９と、（ｘ−α3 ）によるＢＣＨ符号信号の割
り算を行ってシンドロームＳ３を求めるｍビットのシン
ドロームレジスタ１０とに与えられる。またこの誤り訂
正回路には、ＢＣＨ符号信号が与えられるｎビットデー
タレジスタ１１が備えられ、さらに各シンドロームレジ
スタ９，１０からのシンドロームＳ１，Ｓ３がそれぞれ
与えられる誤り位置多項式の係数導出回路１２が設けら
れる。この誤り位置多項式の係数導出回路１２の出力Ｓ
１，Ｓ１2 ＋Ｓ３／Ｓ１は、チエン探索回路１３に与え
られ、排他的論理和ゲート１４は、チエン探索回路１３
の出力とデータレジスタ１１の出力とを演算して訂正後
のＢＣＨ符号信号を得る。こうしてｎビット符号語が読
み込まれた時点で、シンドロームレジスタ９，１０によ
ってシンドロームＳ１，Ｓ３が計算され、さらに誤り位
置多項式の係数も同時に計算される。その後、α-i（ｉ
＝０，１，…，２m −２）を代入してゆき、σ（αi ）
＝０となるｉが誤り位置を表す。この演算は、チエン探
索回路１３で容易に実現することができる。チエン探索
回路は、たとえば今井秀樹著「符号理論」第１６６頁に
開示されている。
【００３２】図２はまた、本発明の他の実施例の誤り訂
正回路の全体の構成を示すブロック図である。この実施
例は、図１に示される実施例に類似し、対応する部分に
は同一の参照符を付す。この実施例では、前述のチエン
探索回路１３を用いる代りに、誤り位置検出回路５３が
備えられる。誤り位置多項式係数導出回路１２からライ
ン１６には、Ｓ１＝０，Ｓ３≠０のとき、訂正不可能な
誤りが生じたとして訂正出力をクリアする信号を導出
し、訂正制御回路１７に与える。この訂正制御回路１７
の出力は、受信符号語のデータレジスタ１８に与えられ
る。このような図２に示される構成によれば、図１に示
される実施例におけるチエン探索回路１３を用いる必要
がなく、したがってチエン探索回路において必要とされ
る外部クロック信号が図２の実施例では不要となり、そ
のため誤り位置の検出がリアルタイムで可能となる。
正回路の全体の構成を示すブロック図である。この実施
例は、図１に示される実施例に類似し、対応する部分に
は同一の参照符を付す。この実施例では、前述のチエン
探索回路１３を用いる代りに、誤り位置検出回路５３が
備えられる。誤り位置多項式係数導出回路１２からライ
ン１６には、Ｓ１＝０，Ｓ３≠０のとき、訂正不可能な
誤りが生じたとして訂正出力をクリアする信号を導出
し、訂正制御回路１７に与える。この訂正制御回路１７
の出力は、受信符号語のデータレジスタ１８に与えられ
る。このような図２に示される構成によれば、図１に示
される実施例におけるチエン探索回路１３を用いる必要
がなく、したがってチエン探索回路において必要とされ
る外部クロック信号が図２の実施例では不要となり、そ
のため誤り位置の検出がリアルタイムで可能となる。
【００３３】図３は、図１および図２の各実施例におけ
る誤り位置多項式の係数導出回路１２の具体的な構成を
示すブロック図である。元作成回路１９は、ｍ次のガロ
ア拡大体ＧＦ（２m）のすべての元を表す回路である。
この元作成回路１９は、（２m−１）個のα乗算器ＭＸ
１〜ＭＸｉを直列に接続することによって実現される。
図３およびその他の図面における二重線矢印は、ガロア
拡大体ＧＦ（２m ）上のｍビットの並列データの流れを
示している。
る誤り位置多項式の係数導出回路１２の具体的な構成を
示すブロック図である。元作成回路１９は、ｍ次のガロ
ア拡大体ＧＦ（２m）のすべての元を表す回路である。
この元作成回路１９は、（２m−１）個のα乗算器ＭＸ
１〜ＭＸｉを直列に接続することによって実現される。
図３およびその他の図面における二重線矢印は、ガロア
拡大体ＧＦ（２m ）上のｍビットの並列データの流れを
示している。
【００３４】図４は、α乗算器ＭＸ１の具体的な構成を
示し、これは（１５，７）ＢＣＨ符号（ｍ＝４）におけ
る構成を示す。α乗算器ＭＸ１は、排他的論理和ゲート
２０を備え、随伴行列を用いることによって簡単な構成
によって実現することができる。
示し、これは（１５，７）ＢＣＨ符号（ｍ＝４）におけ
る構成を示す。α乗算器ＭＸ１は、排他的論理和ゲート
２０を備え、随伴行列を用いることによって簡単な構成
によって実現することができる。
【００３５】べき乗回路２１は、シンドロームＳ１とガ
ロア拡大体ＧＦ（２m ）上の元を乗算するものであっ
て、シンドロームＳ１がガロア拡大体ＧＦ（２m ）上の
どの元と等しいかを探す働きをする。
ロア拡大体ＧＦ（２m ）上の元を乗算するものであっ
て、シンドロームＳ１がガロア拡大体ＧＦ（２m ）上の
どの元と等しいかを探す働きをする。
【００３６】図５は、べき乗回路２１の具体的な構成を
示すブロック図である。このべき乗回路２１は、加算器
ＡＤ０〜ＡＤｉを有し、Ｓ１＝（ａm-1，…，ａ0）、α
i ＝（ｂm-1，…，ｂ0）としたとき、 ａi ＝ （ｂｉ）（ｉ＝０，１，２，…，ｍ−１） …（14） となるαi を求める構成を実現すればよいことになる。
示すブロック図である。このべき乗回路２１は、加算器
ＡＤ０〜ＡＤｉを有し、Ｓ１＝（ａm-1，…，ａ0）、α
i ＝（ｂm-1，…，ｂ0）としたとき、 ａi ＝ （ｂｉ）（ｉ＝０，１，２，…，ｍ−１） …（14） となるαi を求める構成を実現すればよいことになる。
【００３７】図６は、加算器ＡＤ０の具体的な構成を示
す。加算器ＡＤ０は、各ビットａ０〜ａ３，ｂ０〜ｂ３
を、排他的論理和ゲートＥＲ０〜ＥＲ３で演算し、全出
力が論理「０」であればよい。この図６の構成では、
（１５，７）ＢＣＨ符号（ｍ＝４）における構成を示
す。排他的論理和ゲートＥＲ０〜ＥＲ３の出力はＮＡＮ
ＤゲートＧ０に与えられる。各加算器ＡＤ０〜ＡＤｉの
出力ラインＬ０〜Ｌｉにおける制御信号は、 Ｓ１ ＝ αi …（15） となるｉについてのみ後述のＳ１2 サーチ回路２２に与
えられる制御信号が論理「１」になる。
す。加算器ＡＤ０は、各ビットａ０〜ａ３，ｂ０〜ｂ３
を、排他的論理和ゲートＥＲ０〜ＥＲ３で演算し、全出
力が論理「０」であればよい。この図６の構成では、
（１５，７）ＢＣＨ符号（ｍ＝４）における構成を示
す。排他的論理和ゲートＥＲ０〜ＥＲ３の出力はＮＡＮ
ＤゲートＧ０に与えられる。各加算器ＡＤ０〜ＡＤｉの
出力ラインＬ０〜Ｌｉにおける制御信号は、 Ｓ１ ＝ αi …（15） となるｉについてのみ後述のＳ１2 サーチ回路２２に与
えられる制御信号が論理「１」になる。
【００３８】第１乗算回路２３は、シンドロームＳ１と
ガロア拡大体ＧＦ（２m）上の（２m−１）個の元を乗算
する。この第１乗算回路２３は、（２m −１）個のα乗
算器ＭＸ１１，ＭＸ１ｉを直列につないで実現され、そ
の構成は、前述の元作成回路１９のα乗算器ＭＸ１〜Ｍ
Ｘｉと同様である。
ガロア拡大体ＧＦ（２m）上の（２m−１）個の元を乗算
する。この第１乗算回路２３は、（２m −１）個のα乗
算器ＭＸ１１，ＭＸ１ｉを直列につないで実現され、そ
の構成は、前述の元作成回路１９のα乗算器ＭＸ１〜Ｍ
Ｘｉと同様である。
【００３９】図７は、Ｓ１2 サーチ回路２２の具体的な
構成を示すブロック図である。このＳ１2 サーチ回路２
２は、第１乗算回路２３の結果と、べき乗回路２１の結
果とに基づいて、Ｓ１2 を求めるもとのであって、Ｓ１
αi（ｉ＝０，１，…，２m−２）からＳ１2 となるもの
を選ぶ働きをし、ＡＮＤゲートＧ１０〜Ｇ１ｉに、ライ
ンＬ０〜Ｌｉの制御信号が与えられ、また第１乗算回路
２３のα乗算器ＭＸ１１〜ＭＸ１ｉからの各出力がそれ
ぞれ与えられ、排他的論理和ゲートＥＲ１０に、それら
のＡＮＤゲートＧ１０〜Ｇ１ｉの出力が与えられ、こう
して排他的論理和ゲートＥＲ１０からライン１０には、
Ｓ１2 の出力が導出される。
構成を示すブロック図である。このＳ１2 サーチ回路２
２は、第１乗算回路２３の結果と、べき乗回路２１の結
果とに基づいて、Ｓ１2 を求めるもとのであって、Ｓ１
αi（ｉ＝０，１，…，２m−２）からＳ１2 となるもの
を選ぶ働きをし、ＡＮＤゲートＧ１０〜Ｇ１ｉに、ライ
ンＬ０〜Ｌｉの制御信号が与えられ、また第１乗算回路
２３のα乗算器ＭＸ１１〜ＭＸ１ｉからの各出力がそれ
ぞれ与えられ、排他的論理和ゲートＥＲ１０に、それら
のＡＮＤゲートＧ１０〜Ｇ１ｉの出力が与えられ、こう
して排他的論理和ゲートＥＲ１０からライン１０には、
Ｓ１2 の出力が導出される。
【００４０】図８は、図７に示されるＳ１2 サーチ回路
２２の一部をもっと具体的に示す電気回路図である。
（１５，７）ＢＣＨ符号（ｍ＝４）を用いるとき、前述
のＡＮＤゲートＧ１０は、ＡＮＤゲートＧ２０〜Ｇ２３
によって実現され、排他的論理和ゲートＥＲ２０〜ＥＲ
２３には、各ＡＮＤゲートＧ２０〜Ｇ２３の出力と、次
のＡＮＤゲートＧ１１に関連して接続される排他的論理
和ゲートの出力が与えられる。こうして排他的論理和ゲ
ートＥＲ２０〜ＥＲ２３は、出力Ｓ１2 を導出する。
２２の一部をもっと具体的に示す電気回路図である。
（１５，７）ＢＣＨ符号（ｍ＝４）を用いるとき、前述
のＡＮＤゲートＧ１０は、ＡＮＤゲートＧ２０〜Ｇ２３
によって実現され、排他的論理和ゲートＥＲ２０〜ＥＲ
２３には、各ＡＮＤゲートＧ２０〜Ｇ２３の出力と、次
のＡＮＤゲートＧ１１に関連して接続される排他的論理
和ゲートの出力が与えられる。こうして排他的論理和ゲ
ートＥＲ２０〜ＥＲ２３は、出力Ｓ１2 を導出する。
【００４１】Ｓ１逆元サーチ回路２５は、Ｓ１αk（ｉ
＝０，１，…，２m−２）から Ｓ１αi ＝ ｉ0 …（16） となるもの、つまりＳ１の逆元となるαiを求める。
＝０，１，…，２m−２）から Ｓ１αi ＝ ｉ0 …（16） となるもの、つまりＳ１の逆元となるαiを求める。
【００４２】図９は、Ｓ１逆元サーチ回路２５の具体的
な構成を示すブロック図である。Ｓ１逆元サーチ回路２
５は、前述の図７に示されるＳ１サーチ回路２２に類似
し、 Ｓ１αi ＝（ａm-1，…，ａ0）， α0 ＝（０，…，１） としたとき、前述の式１６が成立するαi を求めればよ
い。したがって第１乗算回路２３の各α乗算器ＭＸ１１
〜ＭＸ１ｉからの出力は、排他的論理和ゲートＥＲ３０
〜ＥＲ３ｉに、α0 とともに与えられ、すなわち各ビッ
トを排他的論理和演算し、全出力が全零検知回路ＡＺ０
〜ＡＺｉで、論理「０」となることを検出し、その出力
をラインＬ２０〜Ｌ２ｉからそれぞれ導出する。
な構成を示すブロック図である。Ｓ１逆元サーチ回路２
５は、前述の図７に示されるＳ１サーチ回路２２に類似
し、 Ｓ１αi ＝（ａm-1，…，ａ0）， α0 ＝（０，…，１） としたとき、前述の式１６が成立するαi を求めればよ
い。したがって第１乗算回路２３の各α乗算器ＭＸ１１
〜ＭＸ１ｉからの出力は、排他的論理和ゲートＥＲ３０
〜ＥＲ３ｉに、α0 とともに与えられ、すなわち各ビッ
トを排他的論理和演算し、全出力が全零検知回路ＡＺ０
〜ＡＺｉで、論理「０」となることを検出し、その出力
をラインＬ２０〜Ｌ２ｉからそれぞれ導出する。
【００４３】図１０は、排他的論理和ゲートＥＲ３０と
全零検知回路ＡＺ０の具体的な構成を示す電気回路図で
ある。
全零検知回路ＡＺ０の具体的な構成を示す電気回路図で
ある。
【００４４】（１５，７）ＢＣＨ符号（ｍ＝４）の信号
処理のために、排他的論理和ゲートＥＲ３０には、各ビ
ット毎の排他的論理和ゲートＥＲ４０〜ＥＲ４４が備え
られ、また全零検知回路ＡＺ０は、ＮＡＮＤゲートによ
って実現される。前述の式１６が成立するｉについての
み、後述のＳ３／Ｓ１サーチ回路２６に与えられる制御
信号が論理「１」になる。
処理のために、排他的論理和ゲートＥＲ３０には、各ビ
ット毎の排他的論理和ゲートＥＲ４０〜ＥＲ４４が備え
られ、また全零検知回路ＡＺ０は、ＮＡＮＤゲートによ
って実現される。前述の式１６が成立するｉについての
み、後述のＳ３／Ｓ１サーチ回路２６に与えられる制御
信号が論理「１」になる。
【００４５】第２乗算回路２７は、シンドロームＳ３と
ガロア拡大体ＧＦ（２m）の（２m−１）個の元を乗算す
る。この第２乗算回路２７は、α乗算器ＭＸ２１〜ＭＸ
２ｉを備え、その構成は、前述の元作成回路１９と同様
である。
ガロア拡大体ＧＦ（２m）の（２m−１）個の元を乗算す
る。この第２乗算回路２７は、α乗算器ＭＸ２１〜ＭＸ
２ｉを備え、その構成は、前述の元作成回路１９と同様
である。
【００４６】Ｓ３／Ｓ１サーチ回路２６は、Ｓ３α
i（ｉ＝０，１，…，２m−２）からＳ３／Ｓ１の演算結
果となるものを選ぶ働きをする。
i（ｉ＝０，１，…，２m−２）からＳ３／Ｓ１の演算結
果となるものを選ぶ働きをする。
【００４７】図１１は、Ｓ３／Ｓ１サーチ回路２６の全
体の構成を示すブロック図である。このＳ３／Ｓ１サー
チ回路２６は、前述のＳ１2 サーチ回路２２の構成に類
似し、Ｓ１逆元サーチ回路２５のラインＬ２０〜Ｌ２ｉ
の出力と第２乗算回路２７の各α乗算器ＭＸ２１〜ＭＸ
２ｉの各出力とが与えられるＡＮＤゲートＧ２０〜Ｇ２
ｉと、排他的論理和ゲートＥＲ５とが備えられ、ライン
Ｌ３０からは、Ｓ３／Ｓ１が導出される。すなわち、ラ
インＬ２０〜Ｌ２１からの制御信号が論理「１」である
Ｓ３αi がＳ３／Ｓ１であり、この出力だけが選択され
る。
体の構成を示すブロック図である。このＳ３／Ｓ１サー
チ回路２６は、前述のＳ１2 サーチ回路２２の構成に類
似し、Ｓ１逆元サーチ回路２５のラインＬ２０〜Ｌ２ｉ
の出力と第２乗算回路２７の各α乗算器ＭＸ２１〜ＭＸ
２ｉの各出力とが与えられるＡＮＤゲートＧ２０〜Ｇ２
ｉと、排他的論理和ゲートＥＲ５とが備えられ、ライン
Ｌ３０からは、Ｓ３／Ｓ１が導出される。すなわち、ラ
インＬ２０〜Ｌ２１からの制御信号が論理「１」である
Ｓ３αi がＳ３／Ｓ１であり、この出力だけが選択され
る。
【００４８】Ｓ１2サーチ回路２２のラインＬ１０から
の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路２６のラインＬ
３０からの出力Ｓ３／Ｓ１とは、排他的論理和ゲート２
８によって実現される加算回路２８に与えられ、これに
よって（Ｓ１2 ＋Ｓ３／Ｓ１）が出力される。この排他
的論理和ゲート２８の具体的な構成は、（１５，７）Ｂ
ＣＨ符号（ｍ＝４）の場合、図１２に示されるように、
各ビット毎に排他的論理和ゲートＥＲ６０〜ＥＲ６３に
よって実現される。これらの排他的論理和ゲートＥＲ６
０〜ＥＲ６３の出力は、ラインＬ４０から導出されて、
（Ｓ１2 ＋Ｓ３／Ｓ１）が得られる。
の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路２６のラインＬ
３０からの出力Ｓ３／Ｓ１とは、排他的論理和ゲート２
８によって実現される加算回路２８に与えられ、これに
よって（Ｓ１2 ＋Ｓ３／Ｓ１）が出力される。この排他
的論理和ゲート２８の具体的な構成は、（１５，７）Ｂ
ＣＨ符号（ｍ＝４）の場合、図１２に示されるように、
各ビット毎に排他的論理和ゲートＥＲ６０〜ＥＲ６３に
よって実現される。これらの排他的論理和ゲートＥＲ６
０〜ＥＲ６３の出力は、ラインＬ４０から導出されて、
（Ｓ１2 ＋Ｓ３／Ｓ１）が得られる。
【００４９】図１３は、チエン探索回路１３の具体的な
構成を示すブロック図である。Ｓ１2 サーチ回路２２の
ラインＬ１０を介する出力Ｓ１2 と、排他的論理和ゲー
ト２８のラインＬ４０からの出力（Ｓ１2 ＋Ｓ３／Ｓ
１）とは、初期値としてそれらの値がストアされるｍビ
ットのデータレジスタ２９，３０にそれぞれストアされ
る。これらのレジスタ２９，３０には、カウンタによっ
て実現されるクロック発生器３１からのクロック信号が
与えられる。各レジスタ２９，３０には、α乗算器３２
およびα2 乗算器３３がそれぞれ接続されて閉ループ３
４，３５が構成され、それらの出力は、位数ｍのガロア
拡大体ＧＦ（２m ）の加算回路３６に与えられ、ライン
３７から、前述の図１に示される排他的論理和ゲート１
４に与えられる。加算回路３６は、排他的論理和ゲート
によって実現される。
構成を示すブロック図である。Ｓ１2 サーチ回路２２の
ラインＬ１０を介する出力Ｓ１2 と、排他的論理和ゲー
ト２８のラインＬ４０からの出力（Ｓ１2 ＋Ｓ３／Ｓ
１）とは、初期値としてそれらの値がストアされるｍビ
ットのデータレジスタ２９，３０にそれぞれストアされ
る。これらのレジスタ２９，３０には、カウンタによっ
て実現されるクロック発生器３１からのクロック信号が
与えられる。各レジスタ２９，３０には、α乗算器３２
およびα2 乗算器３３がそれぞれ接続されて閉ループ３
４，３５が構成され、それらの出力は、位数ｍのガロア
拡大体ＧＦ（２m ）の加算回路３６に与えられ、ライン
３７から、前述の図１に示される排他的論理和ゲート１
４に与えられる。加算回路３６は、排他的論理和ゲート
によって実現される。
【００５０】前述の図２に示される誤り位置検出回路５
３の具体的な構成は、図１４に示されている。第１の演
算回路４１には、誤り位置多項式係数導出回路１２に含
まれているＳ１2 サーチ回路２２からラインＬ１０を介
してＳ１2 が与えられる。この演算回路４１は、図１５
に示されるように、α乗算器ＭＸ３１，ＭＸ３２，…，
ＭＸ３ｉが直列に接続されて構成され、こうしてすべて
のαi （ｉ＝０，１，…，２m−２）に対してＡαiの演
算を行い、ラインＬ５０〜Ｌ５ｉにそれぞれ導出する。
３の具体的な構成は、図１４に示されている。第１の演
算回路４１には、誤り位置多項式係数導出回路１２に含
まれているＳ１2 サーチ回路２２からラインＬ１０を介
してＳ１2 が与えられる。この演算回路４１は、図１５
に示されるように、α乗算器ＭＸ３１，ＭＸ３２，…，
ＭＸ３ｉが直列に接続されて構成され、こうしてすべて
のαi （ｉ＝０，１，…，２m−２）に対してＡαiの演
算を行い、ラインＬ５０〜Ｌ５ｉにそれぞれ導出する。
【００５１】もう１つの演算回路４２もまた、上述の演
算回路４１と同様な構成を有し、誤り位置多項式係数導
出回路１２の排他的論理和ゲート２８（前述の図３参
照）におけるラインＬ４０からの（Ｓ１2 ＋Ｓ３／Ｓ
１）が与えられて、Ｂαi （ｉ＝０，１，…，２m−
２）を、ラインＬ６０〜Ｌ６ｉにそれぞれ導出する。
算回路４１と同様な構成を有し、誤り位置多項式係数導
出回路１２の排他的論理和ゲート２８（前述の図３参
照）におけるラインＬ４０からの（Ｓ１2 ＋Ｓ３／Ｓ
１）が与えられて、Ｂαi （ｉ＝０，１，…，２m−
２）を、ラインＬ６０〜Ｌ６ｉにそれぞれ導出する。
【００５２】演算回路４３は、演算回路４２からのＢα
iの出力に応答して、Ｂ（αi）2 を求める。この演算回
路４３の具体的な構成は、図１６に示されている。Ｂα
1 に対して、Ｂ（αi）2を求めるには、Ｂαi にｉ個の
α乗算器ＭＸ４１；ＭＸ５１，ＭＸ５２；ＭＸ６１，Ｍ
Ｘ６２，ＭＸ６３；…を用いる。これはｉ個のα乗算を
行列で用意しておき、αi 回路を構成することで実現す
るようにしてもよい。
iの出力に応答して、Ｂ（αi）2 を求める。この演算回
路４３の具体的な構成は、図１６に示されている。Ｂα
1 に対して、Ｂ（αi）2を求めるには、Ｂαi にｉ個の
α乗算器ＭＸ４１；ＭＸ５１，ＭＸ５２；ＭＸ６１，Ｍ
Ｘ６２，ＭＸ６３；…を用いる。これはｉ個のα乗算を
行列で用意しておき、αi 回路を構成することで実現す
るようにしてもよい。
【００５３】誤り位置検出器４４は、すべてのＡαiお
よびＢ（αi）2 （ｉ＝０，１，…，２m −２）から前
述の式１０の条件を満たすｉを求める働きをする。この
誤り位置検出器４４の具体的な構成は、図１７に示され
る。
よびＢ（αi）2 （ｉ＝０，１，…，２m −２）から前
述の式１０の条件を満たすｉを求める働きをする。この
誤り位置検出器４４の具体的な構成は、図１７に示され
る。
【００５４】図１７に示される誤り位置検出器４４は、
式１０の条件が満たされるｉについて論理「１」の信号
をラインＬ８０〜Ｌ８ｉに導出する働きをする。この働
きを達成するために、誤り位置検出器４４の各ビット毎
に加算器ＡＤ１０〜ＡＤ１ｉが設けられる。
式１０の条件が満たされるｉについて論理「１」の信号
をラインＬ８０〜Ｌ８ｉに導出する働きをする。この働
きを達成するために、誤り位置検出器４４の各ビット毎
に加算器ＡＤ１０〜ＡＤ１ｉが設けられる。
【００５５】図１８は、誤り位置検出器４４に備えられ
る加算器ＡＤ１０の具体的構成を示す電気回路図であ
る。各ビットＡ０〜Ａm-1およびＢ０〜Ｂm-1の出力は、
加算回路を構成する排他的論理和ゲートをＥＲ７０〜Ｅ
Ｒ７m-1 にそれぞれ与えられ、それらの出力は、ＡＮＤ
ゲートＧ２およびＮＡＮＤゲートＧ３にそれぞれ与えら
れる。ＮＡＮＤゲートＧ３には、第２ビット以降のビッ
トａ１〜ａm-1，ｂ１〜ｂm-1が与えられる。ＡＮＤゲー
トＧ２には、第１ビットａ０，ｂ０が与えられる。
る加算器ＡＤ１０の具体的構成を示す電気回路図であ
る。各ビットＡ０〜Ａm-1およびＢ０〜Ｂm-1の出力は、
加算回路を構成する排他的論理和ゲートをＥＲ７０〜Ｅ
Ｒ７m-1 にそれぞれ与えられ、それらの出力は、ＡＮＤ
ゲートＧ２およびＮＡＮＤゲートＧ３にそれぞれ与えら
れる。ＮＡＮＤゲートＧ３には、第２ビット以降のビッ
トａ１〜ａm-1，ｂ１〜ｂm-1が与えられる。ＡＮＤゲー
トＧ２には、第１ビットａ０，ｂ０が与えられる。
【００５６】Ａαi＝（ａm-1，ａm-2，…，ａ０）、 Ｂ（ａi）2＝（ｂm-1，ｂm-2，…，ｂ０） としたとき、 ａ０＋ｂ０ ＝ １ ｍｏｄ ２ …（17） ａｊ＋ｂｊ ＝ ０ ｍｏｄ ２ (ｊ＝１，２，…，ｍ−１) …（18） の２つの条件が満たされれば、式１０が成立したことと
なり、論理「１」が出力される。
なり、論理「１」が出力される。
【００５７】 受信語Ｙ＝（ｙm-1，ｙm-2，…，ｙ０）（ｍ＝符号長） として、ラインＬ８０〜Ｌ８ｉからの出力のうち、ｉ＝
Ｌ１，ｉ＝Ｌ２が論理「１」、 ０ ≦ Ｌ１ ＜ Ｌ２ ＜ ２m − ２ となれば、
Ｌ１，ｉ＝Ｌ２が論理「１」、 ０ ≦ Ｌ１ ＜ Ｌ２ ＜ ２m − ２ となれば、
【００５８】
【数４】
【００５９】のビットが誤りであり、それを反転すれば
よいことになる。この反転動作は、データレジスタ１８
において達成される。
よいことになる。この反転動作は、データレジスタ１８
において達成される。
【００６０】本発明は、上述の２重誤り訂正符号のため
だけでなく、もっと訂正数の大きい符号に対しても、ユ
ークリッド法、バーレカンプ・マツシイ法によって誤り
位置多項式の係数とシンドロームの関係を求めることに
よって、ハード化のために本発明を実施することができ
る。
だけでなく、もっと訂正数の大きい符号に対しても、ユ
ークリッド法、バーレカンプ・マツシイ法によって誤り
位置多項式の係数とシンドロームの関係を求めることに
よって、ハード化のために本発明を実施することができ
る。
【００６１】
【発明の効果】以上のように本発明の誤り位置多項式の
係数導出回路によれば、ガロア拡大体ＧＦ（２m ）上の
加算、乗算、および逆元の導出のための除算という操作
が、単純なゲート回路で実現され、したがってその演算
を高速度で行うことができる。またこのゲート回路など
の構成は、α乗算器を中心とする単純な回路構成である
という効果もまた、達成される。さらに本発明によれ
ば、外部のリードオンリメモリによるアクセスの必要が
なくなる。さらに本発明の構成は、集積回路によって実
現することが容易であり、またコストが低いという効果
もある。
係数導出回路によれば、ガロア拡大体ＧＦ（２m ）上の
加算、乗算、および逆元の導出のための除算という操作
が、単純なゲート回路で実現され、したがってその演算
を高速度で行うことができる。またこのゲート回路など
の構成は、α乗算器を中心とする単純な回路構成である
という効果もまた、達成される。さらに本発明によれ
ば、外部のリードオンリメモリによるアクセスの必要が
なくなる。さらに本発明の構成は、集積回路によって実
現することが容易であり、またコストが低いという効果
もある。
【００６２】さらに本発明の誤り位置検出回路によれ
ば、誤り位置の検出をリアルタイムで行うことができ、
外部クロックを必要とせず、さらにまたゲート回路だけ
で構成することができ、集積回路化が容易であり、コス
トが低減されるという効果が達成される。このように本
発明によれば、具体的な回路構成によって、ＢＣＨ符号
信号の読み込みと同時に誤り位置の探索が可能になる。
ば、誤り位置の検出をリアルタイムで行うことができ、
外部クロックを必要とせず、さらにまたゲート回路だけ
で構成することができ、集積回路化が容易であり、コス
トが低減されるという効果が達成される。このように本
発明によれば、具体的な回路構成によって、ＢＣＨ符号
信号の読み込みと同時に誤り位置の探索が可能になる。
【図１】本発明の一実施例の誤り訂正回路の全体の構成
を示すブロック図である。
を示すブロック図である。
【図２】本発明の他の実施例の誤り訂正回路の全体の構
成を示すブロック図である。
成を示すブロック図である。
【図３】誤り位置多項式の係数導出回路１２の具体的な
構成を示すブロック図である。
構成を示すブロック図である。
【図４】元作成回路１９に含まれるα乗算器ＭＸ１の具
体的な構成を示す電気回路図である。
体的な構成を示す電気回路図である。
【図５】べき乗回路２１の具体的構成を示すブロック図
である。
である。
【図６】べき乗回路２１に含まれる加算器ＡＤ０の具体
的構成を示すブロック図である。
的構成を示すブロック図である。
【図７】Ｓ１2 サーチ回路２２の具体的構成を示すブロ
ック図である。
ック図である。
【図８】図７に示されるＳ１2 サーチ回路２２のもっと
具体的な構成を示す電気回路図である。
具体的な構成を示す電気回路図である。
【図９】Ｓ１逆元サーチ回路２５の具体的構成を示すブ
ロック図である。
ロック図である。
【図１０】図９に示されるＳ１逆元サーチ回路２５に含
まれる排他的論理和ゲートＥＲ３０および全零検知回路
ＡＺ０の具体的構成を示す電気回路図である。
まれる排他的論理和ゲートＥＲ３０および全零検知回路
ＡＺ０の具体的構成を示す電気回路図である。
【図１１】Ｓ３／Ｓ１サーチ回路２６の具体的な構成を
示すブロック図である。
示すブロック図である。
【図１２】加算回路２８の具体的な構成を示す電気回路
図である。
図である。
【図１３】図１のチエン探索回路１３の具体的構成を示
すブロック図である。
すブロック図である。
【図１４】図２に示される誤り位置検出回路５３の具体
的構成を示す全体のブロック図である。
的構成を示す全体のブロック図である。
【図１５】図１４に示される演算回路４１の具体的構成
を示すブロック図である。
を示すブロック図である。
【図１６】２乗回路４３の具体的構成を示すブロック図
である。
である。
【図１７】誤り位置検出器４４の具体的な構成を示すブ
ロック図である。
ロック図である。
【図１８】図１７に示される誤り位置検出器４４に含ま
れる加算器ＡＤ１０の具体的構成を示す電気回路図であ
る。
れる加算器ＡＤ１０の具体的構成を示す電気回路図であ
る。
【図１９】先行技術の誤り訂正回路の全体の構成を示す
ブロック図である。
ブロック図である。
９，１０ シンドロームレジスタ １１ ｎビットデータレジスタ １２ 誤り位置多項式の係数導出回路 １３ チエン探索回路 １４ 加算回路 １７ 訂正制御回路 １８ データレジスタ １９ 元作成回路 ２１ べき乗回路 ２２ Ｓ１2サーチ回路 ２３ 乗算回路 ２５ Ｓ１逆元サーチ回路 ２６ Ｓ３／Ｓ１サーチ回路 ２７ 乗算回路 ２８ 加算回路 ４１，４２ 演算回路 ４３ ２乗回路 ４４ 誤り位置検出器 ５３ 誤り位置検出回路
───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.7，ＤＢ名) H03M 13/00 G06F 11/10 330 H04L 1/00
Claims (2)
- 【請求項１】 （ａ）ＢＣＨ符号信号を（ｘ−α）によ
って割り算して第１シンドロームＳ１を求める第１シン
ドロームレジスタ９と、 （ｂ）前記ＢＣＨ符号信号を（ｘ−α3 ）による割り算
を行って第２シンドロームＳ３を求める第２シンドロー
ムレジスタ１０と、 （ｃ）誤り位置多項式の係数導出回路１２であって、 （ｃ１）αをｍ次のガロア拡大体ＧＦ（２m）の原始元
とし、α，α3を根にもつ２重誤り訂正（ｎ，ｋ）ＢＣ
Ｈ符号の復号において、（２m −１）個の第１α乗算器
ＭＸ１〜ＭＸｉを直列につなぎ、初段の第１α乗算器Ｍ
Ｘ１にα0を与えることによって、ＧＦ（２m）の元α〜
α（２m−１）（以下、αの（２m−１）乗を表す）を作
成する元作成回路１９と、 （ｃ２）第１シンドロームＳ１と元作成回路１９の出力
とに応答し、Ｓ１α〜Ｓ１α（２m−１）を求めるべき
乗回路２１であって、 （２m−１）個の第１加算器ＡＤ０〜ＡＤｉを有し、 各加算器ＡＤ０〜ＡＤｉは、 Ｓ１の各ビットａ０〜ａ３と、α１〜α（２m−１）の
各ビットｂ０〜ｂ３とが与えられる第１排他的論理和ゲ
ートＥＲ０〜ＥＲ３と、 これらの第１排他的論理和ゲートＥＲ０〜ＥＲ３の出力
が与えられる第１ＮＡＮＤゲートＧ０とを有し、 各第１加算器ＡＤ０〜ＡＤｉは、出力Ｌ０〜Ｌｉを導出
するべき乗回路２１と、 （ｃ３）第１シンドロームＳ１とＧＦ（２m）上の（２m
−１）個の元を乗算する第１乗算回路２３であって、
（２m−１）個の第２α乗算器ＭＸ１１〜ＭＸ１ｉを直
列につなぎ、初段の第２α乗算器ＭＸ１１に第１シンド
ロームＳ１を与える第１乗算回路２３と、 （ｃ４）第１乗算回路２３の結果と、べき乗回路２１の
結果とに基づいて、Ｓ１2 を求めるＳ１2サーチ回路２
２であって、 各第２α乗算器ＭＸ１１〜ＭＸ１ｉの出力と、べき乗回
路２１の各第１加算器ＡＤ０〜ＡＤｉの出力Ｌ０〜Ｌｉ
とが、与えられる第１ＡＮＤゲートＧ１０〜Ｇ１ｉと、 第１ＡＮＤゲートＧ１０〜Ｇ１ｉの出力が与えられ、Ｓ
１2を出力する第２排他的論理和ゲートＥＲ１０とを有
するＳ１2サーチ回路２２と、 （ｃ５）Ｓ１の逆元を求める逆元サーチ回路２５であっ
て、 （２m−１）個の第３排他的論理和ゲートＥＲ３０〜Ｅ
Ｒ３ｉであって、各第３排他的論理和ゲートＥＲ３０〜
ＥＲ３ｉには、α0と、第１乗算回路２３の第２乗算器
ＭＸ１１〜ＭＸ１ｉの出力とが与えられる第３排他的論
理和ゲートＥＲ３０〜ＥＲ３ｉと、 第３排他的論理和ゲートＥＲ３０〜ＥＲ３ｉの各出力の
全ビットが論理「０」となることを検出するＮＡＮＤゲ
ートによって実現される全零検知回路ＡＺ０〜ＡＺｉと
を有する逆元サーチ回路２５と、 （ｃ６）第２シンドロームＳ３とＧＦ（２m）上の（２m
−１）個の元を乗算する第２乗算回路２７であって、
（２m−１）個の第３α乗算器ＭＸ２１〜ＭＸ２ｉを直
列につなぎ、初段の第３α乗算器ＭＸ２１に、第２シン
ドロームＳ３を与える第２乗算回路２７と、 （ｃ７）第２乗算回路２７の結果と逆元サーチ回路２５
からの結果とに基づいてＳ３／Ｓ１を求めるＳ３／Ｓ１
サーチ回路２６であって、 （ｃ７−１）（２m−１）個の第２ＡＮＤゲートＧ２０
〜Ｇ２ｉであって、各第２ＡＮＤゲートＧ２０〜Ｇ２ｉ
は、逆元サーチ回路２５の各全零検知回路ＡＺ０〜ＡＺ
ｉの出力Ｌ２０〜Ｌ２ｉと、 第２乗算回路２７の第３α乗算器ＭＸ２１〜ＭＸ２ｉか
らの出力とが与えられる第２ＡＮＤゲートＧ２０〜Ｇ２
ｉと、 （ｃ７−２）第２ＡＮＤゲートＧ２０〜Ｇ２ｉの出力が
与えられ、Ｓ３／Ｓ１を導出する第４排他的論理和ゲー
トＥＲ５とを有するＳ３／Ｓ１サーチ回路２６と、 （ｃ８）Ｓ１2 とＳ３／Ｓ１との結果を加算する回路２
８であって、 Ｓ１2サーチ回路２２の第２排他的論理和ゲートＥＲ１
０の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路２６の第４排
他的論理和ゲートＥＲ５の出力Ｓ３／Ｓ１とが、各ビッ
ト毎に与えられ、（Ｓ１2＋Ｓ３／Ｓ１）を出力する第
５排他的論理和ゲートＥＲ６０〜ＥＲ６３を有する加算
回路２８とを含む誤り位置多項式の係数導出回路１２
と、 （ｄ）前記誤り位置多項式の係数導出回路の出力に応答
してチエン探索を行い、誤り位置を表すチエン探索回路
１３と、 （ｅ）前記ＢＣＨ符号信号を受信してストアするデータ
のレジスタ１１と、 （ｆ）チエン探索回路の出力とデータレジスタの出力と
を演算して訂正後のＢＣＨ符号信号を得る演算回路１４
とを含むことを特徴とする誤り訂正回路。 - 【請求項２】 （ａ）ＢＣＨ符号信号を（ｘ−α）によ
って割り算して第１シンドロームＳ１を求める第１シン
ドロームレジスタ９と、 （ｂ）前記ＢＣＨ符号信号を（ｘ−α3 ）による割り算
を行って第２シンドロームＳ３を求める第２シンドロー
ムレジスタ１０と、 （ｃ）誤り位置多項式の係数導出回路１２であって、 （ｃ１）αをｍ次のガロア拡大体ＧＦ（２m）の原始元
とし、α，α3を根にもつ２重誤り訂正（ｎ，ｋ）ＢＣ
Ｈ符号の復号において、（２m −１）個の第１α乗算器
ＭＸ１〜ＭＸｉを直列につなぎ、初段の第１α乗算器Ｍ
Ｘ１にα0を与えることによって、ＧＦ（２m）の元α〜
α（２m−１）（以下、αの（２m−１）乗を表す）を作
成する元作成回路１９と、 （ｃ２）第１シンドロームＳ１と元作成回路１９の出力
とに応答し、Ｓ１α〜Ｓ１α（２m−１）を求めるべき
乗回路２１であって、 （２m−１）個の第１加算器ＡＤ０〜ＡＤｉを有し、 各加算器ＡＤ０〜ＡＤｉは、 Ｓ１の各ビットａ０〜ａ３と、α１〜α（２m−１）の
各ビットｂ０〜ｂ３とが与えられる第１排他的論理和ゲ
ートＥＲ０〜ＥＲ３と、 これらの第１排他的論理和ゲートＥＲ０〜ＥＲ３の出力
が与えられる第１ＮＡＮＤゲートＧ０とを有し、 各第１加算器ＡＤ０〜ＡＤｉは、出力Ｌ０〜Ｌｉを導出
するべき乗回路２１と、 （ｃ３）第１シンドロームＳ１とＧＦ（２m）上の（２m
−１）個の元を乗算する第１乗算回路２３であって、
（２m−１）個の第２α乗算器ＭＸ１１〜ＭＸ１ｉを直
列につなぎ、初段の第２α乗算器ＭＸ１１に第１シンド
ロームＳ１を与える第１乗算回路２３と、 （ｃ４）第１乗算回路２３の結果と、べき乗回路２１の
結果とに基づいて、Ｓ１2 を求めるＳ１2サーチ回路２
２であって、 各第２α乗算器ＭＸ１１〜ＭＸ１ｉの出力と、べき乗回
路２１の各第１加算器ＡＤ０〜ＡＤｉの出力Ｌ０〜Ｌｉ
とが、与えられる第１ＡＮＤゲートＧ１０〜Ｇ１ｉと、 第１ＡＮＤゲートＧ１０〜Ｇ１ｉの出力が与えられ、Ｓ
１2を出力する第２排他的論理和ゲートＥＲ１０とを有
するＳ１2サーチ回路２２と、 （ｃ５）Ｓ１の逆元を求める逆元サーチ回路２５であっ
て、 （２m−１）個の第３排他的論理和ゲートＥＲ３０〜Ｅ
Ｒ３ｉであって、各第３排他的論理和ゲートＥＲ３０〜
ＥＲ３ｉには、α0と、第１乗算回路２３の第２乗算器
ＭＸ１１〜ＭＸ１ｉの出力とが与えられる第３排他的論
理和ゲートＥＲ３０〜ＥＲ３ｉと、 第３排他的論理和ゲートＥＲ３０〜ＥＲ３ｉの各出力の
全ビットが論理「０」となることを検出するＮＡＮＤゲ
ートによって実現される全零検知回路ＡＺ０〜ＡＺｉと
を有する逆元サーチ回路２５と、 （ｃ６）第２シンドロームＳ３とＧＦ（２m）上の（２m
−１）個の元を乗算する第２乗算回路２７であって、
（２m−１）個の第３α乗算器ＭＸ２１〜ＭＸ２ｉを直
列につなぎ、初段の第３α乗算器ＭＸ２１に、第２シン
ドロームＳ３を与える第２乗算回路２７と、 （ｃ７）第２乗算回路２７の結果と逆元サーチ回路２５
からの結果とに基づいてＳ３／Ｓ１を求めるＳ３／Ｓ１
サーチ回路２６であって、 （ｃ７−１）（２m−１）個の第２ＡＮＤゲートＧ２０
〜Ｇ２ｉであって、各第２ＡＮＤゲートＧ２０〜Ｇ２ｉ
は、逆元サーチ回路２５の各全零検知回路ＡＺ０〜ＡＺ
ｉの出力Ｌ２０〜Ｌ２ｉと、 第２乗算回路２７の第３α乗算器ＭＸ２１〜ＭＸ２ｉか
らの出力とが与えられる第２ＡＮＤゲートＧ２０〜Ｇ２
ｉと、 （ｃ７−２）第２ＡＮＤゲートＧ２０〜Ｇ２ｉの出力が
与えられ、Ｓ３／Ｓ１を導出する第４排他的論理和ゲー
トＥＲ５とを有するＳ３／Ｓ１サーチ回路２６と、 （ｃ８）Ｓ１2 とＳ３／Ｓ１との結果を加算する回路２
８であって、 Ｓ１2サーチ回路２２の第２排他的論理和ゲートＥＲ１
０の出力Ｓ１2と、Ｓ３／Ｓ１サーチ回路２６の第４排
他的論理和ゲートＥＲ５の出力Ｓ３／Ｓ１とが、各ビッ
ト毎に与えられ、（Ｓ１2＋Ｓ３／Ｓ１）を出力する第
５排他的論理和ゲートＥＲ６０〜ＥＲ６３を有する加算
回路２８とを含む誤り位置多項式の係数導出回路１２
と、 （ｄ）誤り位置検出回路であって、 （ｄ１）その誤り位置多項式を σ（ｚ） ＝ １ ＋ Ａｚ ＋ Ｂｚ2 としたとき、（２m −２）個の第４α乗算器ＭＸ３１〜
ＭＸ３ｉを直列につなぎ、初段の第４α乗算器ＭＸ３１
に、Ｓ１2サーチ回路２２の第２排他的論理和ゲートＥ
Ｒ１０の出力Ｓ１2であるＡを与えることによってＡαi
（ｉ＝０，１，２，…，２m−２）を出力する第１演算
回路４１と、 （ｄ２）（２m −２）個の第５α乗算器を直列につな
ぎ、初段の第５α乗算器に、加算回路２８の第５排他的
論理和ゲートＥＲ６０〜ＥＲ６３からの出力（Ｓ１2＋
Ｓ３／Ｓ１）であるＢを与えることによってＢαj（ｊ
＝０，１，２，…，２m−２）を出力する第２演算回路
４２と、 （ｄ３）Ｂαk（ｋ＝０，１，２，…，２m−２）に対し
第６α乗算器ＭＸ４１；ＭＸ５１，ＭＸ５２；ＭＸ６
１，ＭＸ６２，ＭＸ６３；…をｋ個つなぐことによって
Ｂ（αk）2を出力する第３演算回路４３と、 （ｄ４）第１演算回路４１と第３演算回路４３との出力
に基づいて、前記誤り位置多項式が、 σ（αL）＝０ （Ｌ＝０，１，２，…，２m−２） となるＬを判別し、受信符号語の誤り位置を指示する出
力を導出する回路４４であって、ＡαiおよびＢ（αi）
2（ｉ＝０，１，…，２m−２）が与えられる第３加算器
ＡＤ１０〜ＡＤ１ｉを有し、 各第３加算器ＡＤ１０〜ＡＤ１ｉは、 ＡαiおよびＢ（αi）2の各ビットが与えられる各ビッ
ト毎の第６排他的論理和ゲートＥＲ７０〜ＥＲ７
m-1と、 第２ビット以降のビットａ１〜ａm-1，ｂ１〜ｂm-1が与
えられる第６排他的論理和ゲートＥＲ７１〜ＥＲ７m-1
の出力が与えられる第２ＮＡＮＤゲートＧ３と、 第１ビットａ０，ｂ０が与えられる第６排他的論理和ゲ
ートＥＲ７０と、第２ＮＡＮＤゲートＧ３との出力が与
えられるＡＮＤゲートＧ２とを有する誤り位置指示出力
導出回路４４とを含む誤り位置検出回路５３と、 （ｅ）Ｓ１＝０，Ｓ３≠０のとき、訂正不可能な誤りが
生じたとして訂正出力をクリアする訂正制御回路１７
と、 （ｆ）ＢＣＨ符号信号をストアして誤り位置検出回路と
訂正制御回路の出力によって訂正を行って訂正後のＢＣ
Ｈ符号信号を得るデータレジスタ１８とを含むことを特
徴とする誤り訂正回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP13790593A JP3280470B2 (ja) | 1993-06-08 | 1993-06-08 | 誤り訂正回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP13790593A JP3280470B2 (ja) | 1993-06-08 | 1993-06-08 | 誤り訂正回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH06348518A JPH06348518A (ja) | 1994-12-22 |
| JP3280470B2 true JP3280470B2 (ja) | 2002-05-13 |
Family
ID=15209425
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP13790593A Expired - Fee Related JP3280470B2 (ja) | 1993-06-08 | 1993-06-08 | 誤り訂正回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3280470B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH11196006A (ja) | 1997-12-26 | 1999-07-21 | Nec Corp | 並列処理シンドロ−ム計算回路及びリ−ド・ソロモン複合化回路 |
| CN109981116B (zh) * | 2019-03-25 | 2023-04-18 | 眸芯科技（上海）有限公司 | Bch码中bm算法的求逆电路、实现方法及应用 |
-
1993
- 1993-06-08 JP JP13790593A patent/JP3280470B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH06348518A (ja) | 1994-12-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6637002B1 (en) | Decoder for error correcting block codes | |
| US5291496A (en) | Fault-tolerant corrector/detector chip for high-speed data processing | |
| EP0167627B1 (en) | Method and apparatus for decoding error correction code | |
| US4873688A (en) | High-speed real-time Reed-Solomon decoder | |
| JPH0831803B2 (ja) | 誤り訂正のための方法と装置 | |
| JP2001502153A (ja) | 大規模データ・ブロックのためのハードウェア最適化リード・ソロモン・デコーダ | |
| JP3176171B2 (ja) | 誤り訂正方法及びその装置 | |
| CN1208192A (zh) | 差错定位多项式高速计算电路 | |
| TW566008B (en) | Apparatus for solving key equation polynomials in decoding error correction codes | |
| EP0723342B1 (en) | Error correction apparatus | |
| JP3280470B2 (ja) | 誤り訂正回路 | |
| JPH10112660A (ja) | リード・ソロモン符号を利用した誤り復号方法および装置 | |
| US20030159103A1 (en) | Efficient method for fast decoding of BCH binary codes | |
| JP3343857B2 (ja) | 復号装置、演算装置およびこれらの方法 | |
| US5666369A (en) | Method and arrangement of determining error locations and the corresponding error patterns of received code words | |
| WO1994015406A1 (en) | Method of and circuit for correcting errors | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JPH10322226A (ja) | リードソロモン復号方法 | |
| US10623018B2 (en) | Method of arrangement of an algorithm in cyclic redundancy check | |
| KR100335482B1 (ko) | 에러정정시스템 | |
| JPS6217256B2 (ja) | ||
| JP3230888B2 (ja) | ユークリッド互除回路 | |
| JP2553571B2 (ja) | ガロア体演算装置 | |
| JP3135552B2 (ja) | リードソロモン符号の誤り検出及び訂正装置 | |
| JPH05268101A (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: 20020205 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080222 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090222 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090222 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100222 Year of fee payment: 8 |
|
| LAPS | Cancellation because of no payment of annual fees |