JPH07240692A - 誤り訂正回路 - Google Patents
誤り訂正回路Info
- Publication number
- JPH07240692A JPH07240692A JP6029871A JP2987194A JPH07240692A JP H07240692 A JPH07240692 A JP H07240692A JP 6029871 A JP6029871 A JP 6029871A JP 2987194 A JP2987194 A JP 2987194A JP H07240692 A JPH07240692 A JP H07240692A
- Authority
- JP
- Japan
- Prior art keywords
- basic arithmetic
- arithmetic circuit
- registers
- polynomial
- circuit
- 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.)
- Withdrawn
Links
- 238000012937 correction Methods 0.000 title claims abstract description 29
- 238000012545 processing Methods 0.000 claims abstract description 41
- 238000001514 detection method Methods 0.000 claims description 19
- 208000011580 syndromic disease Diseases 0.000 abstract description 11
- 238000000034 method Methods 0.000 description 65
- 238000010586 diagram Methods 0.000 description 6
- 238000007792 addition Methods 0.000 description 3
- 238000004364 calculation method Methods 0.000 description 3
- 230000001413 cellular effect Effects 0.000 description 3
- 238000012546 transfer Methods 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 238000004891 communication Methods 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000014759 maintenance of location Effects 0.000 description 1
- 230000000717 retained effect Effects 0.000 description 1
- 230000008054 signal transmission Effects 0.000 description 1
- 230000001360 synchronised effect Effects 0.000 description 1
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Abstract
(57)【要約】
【構成】 誤り訂正回路１００は、多項式Ａ（Ｌ）のみ
を処理する第１の基本演算回路１０と、多項式Ｂ（Ｍ）
のみを処理する第２の基本演算回路２とを交互にカスケ
ード接続し、初段には係数を第２段目の第１の基本演算
回路１０に与えるためだけの第３の基本演算回路３０が
接続される。各第１および第２の基本演算回路１０およ
び２０に、最高次係数保持用レジスタの書き換えのため
のイネーブル信号（Ｅ）、およびゼロ検出信号（Ｆ）を
与えるためのレジスタ１１０およびＡＮＤゲート１１１
が設けられる。 【効果】 各専用の基本演算回路を用いるので、多項式
Ａ（Ｌ）または多項式Ｂ（Ｍ）の選択器およびその制御
が不要となれ、回路および制御が簡単になる。
を処理する第１の基本演算回路１０と、多項式Ｂ（Ｍ）
のみを処理する第２の基本演算回路２とを交互にカスケ
ード接続し、初段には係数を第２段目の第１の基本演算
回路１０に与えるためだけの第３の基本演算回路３０が
接続される。各第１および第２の基本演算回路１０およ
び２０に、最高次係数保持用レジスタの書き換えのため
のイネーブル信号（Ｅ）、およびゼロ検出信号（Ｆ）を
与えるためのレジスタ１１０およびＡＮＤゲート１１１
が設けられる。 【効果】 各専用の基本演算回路を用いるので、多項式
Ａ（Ｌ）または多項式Ｂ（Ｍ）の選択器およびその制御
が不要となれ、回路および制御が簡単になる。
Description
【０００１】
【産業上の利用分野】この発明は誤り訂正回路に関し、
特にたとえば、ディジタルＶＴＲ，放送，通信等のデー
タ伝送システムに適用され、ユークリッドの互除法によ
りガロア体の元を係数とする誤り数値多項式や誤り位置
多項式を導出する、誤り訂正回路に関する。
特にたとえば、ディジタルＶＴＲ，放送，通信等のデー
タ伝送システムに適用され、ユークリッドの互除法によ
りガロア体の元を係数とする誤り数値多項式や誤り位置
多項式を導出する、誤り訂正回路に関する。
【０００２】
【従来の技術】リードソロモン符号等のロングディスタ
ンスコードを用いて多数のワード（シンボル）の誤り訂
正を行う手法としては、受信データからシンドロームを
生成し、誤り数値多項式と誤り位置多項式とのそれぞれ
の係数を導出しなければならない。
ンスコードを用いて多数のワード（シンボル）の誤り訂
正を行う手法としては、受信データからシンドロームを
生成し、誤り数値多項式と誤り位置多項式とのそれぞれ
の係数を導出しなければならない。
【０００３】そのための手法として、一般的に、２つの
多項式の最大公約多項式を求めるユークリッド互除法が
知られている。このユークリッド互除法を用いて誤り訂
正を実行するためには、ガロア体上の元を係数とする多
項式の乗算や加算を数多く行う必要がある。このような
ユークリッド互除法による多項式の演算には、従来、
(1) 誤り訂正過程のガロア体演算をプログラムに従って
マイクロプロセサによって実行する方法と、(2) ガロア
体乗算器とガロア体加算器とをそれぞれ専用のハードウ
ェアによって実現したものがある。前者は、マイクロプ
ロセサの動作速度にもよるが、比較的長時間を要する。
一方、後者は、前者に比べてその処理速度は格段に向上
するものの、それでもなお、たとえばディジタルＶＴＲ
等の伝送系に用いるには処理速度が遅く、使用できない
という問題がある。
多項式の最大公約多項式を求めるユークリッド互除法が
知られている。このユークリッド互除法を用いて誤り訂
正を実行するためには、ガロア体上の元を係数とする多
項式の乗算や加算を数多く行う必要がある。このような
ユークリッド互除法による多項式の演算には、従来、
(1) 誤り訂正過程のガロア体演算をプログラムに従って
マイクロプロセサによって実行する方法と、(2) ガロア
体乗算器とガロア体加算器とをそれぞれ専用のハードウ
ェアによって実現したものがある。前者は、マイクロプ
ロセサの動作速度にもよるが、比較的長時間を要する。
一方、後者は、前者に比べてその処理速度は格段に向上
するものの、それでもなお、たとえばディジタルＶＴＲ
等の伝送系に用いるには処理速度が遅く、使用できない
という問題がある。
【０００４】これに対して、たとえば、電子通信学会論
文誌'86 １号Vol.J69-A No.3の第420 〜第428 ページの
「シストリック・アルゴリズムに基づくReed-Solomon符
号の復号器の構成法」と題された木村等の論文におい
て、シストリックアルゴリズムを適用し、簡単な制御で
パイプライン式の処理を行う方法が提案されている。こ
の提案されたシストリックアレイを用いる従来の誤り訂
正回路は、図７のように構成され、図６に示すような基
本演算回路１を用いる。
文誌'86 １号Vol.J69-A No.3の第420 〜第428 ページの
「シストリック・アルゴリズムに基づくReed-Solomon符
号の復号器の構成法」と題された木村等の論文におい
て、シストリックアルゴリズムを適用し、簡単な制御で
パイプライン式の処理を行う方法が提案されている。こ
の提案されたシストリックアレイを用いる従来の誤り訂
正回路は、図７のように構成され、図６に示すような基
本演算回路１を用いる。
【０００５】一般に、リードソロモン符号を用いた多数
シンボルの誤り訂正の復号は、次に示す手順に従って行
われる。 (1) 受信データからシンドロームＳi を算出する。 (2) シンドロームＳi から誤り数値多項式ω（ｘ）およ
び誤り位置多項式σ（ｘ）を算出する。
シンボルの誤り訂正の復号は、次に示す手順に従って行
われる。 (1) 受信データからシンドロームＳi を算出する。 (2) シンドロームＳi から誤り数値多項式ω（ｘ）およ
び誤り位置多項式σ（ｘ）を算出する。
【０００６】(3) 誤り位置多項式σ（ｘ）から誤り位置
を探索する。 (4) 誤り位置と誤り数値多項式ω（ｘ）から誤り数値を
推定する。 (5) 誤り位置と誤り数値とから受信データを訂正する。 図６に示す基本演算回路１は、上記(2) の誤り数値多項
式ω（ｘ）および誤り位置多項式σ（ｘ）を算出するた
めの回路である。
を探索する。 (4) 誤り位置と誤り数値多項式ω（ｘ）から誤り数値を
推定する。 (5) 誤り位置と誤り数値とから受信データを訂正する。 図６に示す基本演算回路１は、上記(2) の誤り数値多項
式ω（ｘ）および誤り位置多項式σ（ｘ）を算出するた
めの回路である。
【０００７】一例として、ガロア体ＧＦ（２8 ）上の
（８５，７７，９）符号を考えると、この符号の特性と
しては、符号長８５シンボルおよび冗長８シンボルで、
４シンボル訂正可能である。上記(1) におけるシンドロ
ームＳi は、一般に、数１のように表される。
（８５，７７，９）符号を考えると、この符号の特性と
しては、符号長８５シンボルおよび冗長８シンボルで、
４シンボル訂正可能である。上記(1) におけるシンドロ
ームＳi は、一般に、数１のように表される。
【０００８】
【数１】
【０００９】α：ガロア体ＧＦ（２8 ）上の原始元 ｘi ：受信データこのようなシンドロームＳi に基づい
て、シンドローム多項式を数２のように定義する。
て、シンドローム多項式を数２のように定義する。
【００１０】
【数２】Ｓ（ｘ）＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ
4 ｘ4 ＋Ｓ3 ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 誤り数値多項式ω（ｘ）および誤り位置多項式σ（ｘ）
の算出は、最大公約多項式を求めるユークリッドの互除
法の過程で算出でき、シンドローム多項式Ｓ（ｘ）と誤
り数値多項式ω（ｘ）および誤り位置多項式σ（ｘ）と
の間には数３の関係がある。
4 ｘ4 ＋Ｓ3 ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 誤り数値多項式ω（ｘ）および誤り位置多項式σ（ｘ）
の算出は、最大公約多項式を求めるユークリッドの互除
法の過程で算出でき、シンドローム多項式Ｓ（ｘ）と誤
り数値多項式ω（ｘ）および誤り位置多項式σ（ｘ）と
の間には数３の関係がある。
【００１１】
【数３】Ａ（ｘ）ｘ2t＋σ（ｘ）Ｓ（ｘ）＝ω（ｘ） deg ω（ｘ）＜deg σ（ｘ）≦ｔ Ａ（ｘ）：任意の多項式 deg ω（ｘ），deg σ（ｘ）：各々の多項式の次数 ｔ：訂正可能な誤りシンボル数 上記数３はＡ0 ＝ｘ2tおよびＢ0 ＝Ｓ（ｘ）に対して次
の多項式Ａ，Ｂ，ＬおよびＭを定義し、図１に示すフロ
ー図に従った処理を繰り返し実行することに置き換えら
れる。なお、αは多項式Ｂの最高次係数であり、βは多
項式Ａの最高次係数である。また、減算については、モ
ジュロ２の減算であり、モジュロ２の加算と同様の結果
となるので、以下、全て、モジュロ２の加算として扱
う。
の多項式Ａ，Ｂ，ＬおよびＭを定義し、図１に示すフロ
ー図に従った処理を繰り返し実行することに置き換えら
れる。なお、αは多項式Ｂの最高次係数であり、βは多
項式Ａの最高次係数である。また、減算については、モ
ジュロ２の減算であり、モジュロ２の加算と同様の結果
となるので、以下、全て、モジュロ２の加算として扱
う。
【００１２】このような一連の処理は、入力→選択→積
和演算の繰り返しであり、したがって図６に示す基本演
算回路１が利用できるのである。図６に示す基本演算回
路１において、選択器２ａおよび２ｂは、それぞれ、入
力に応じて処理Ａおよび処理Ｂ（図１）を選択して係数
のデータを出力する。選択器２ａおよび２ｂから出力さ
れた係数データは、それぞれ、レジスタ３ａおよび３ｂ
にロードされ、保持されるとともに、ガロア体乗算器４
ａおよび４ｂに与えられる。ガロア体乗算器４ａおよび
４ｂは、さらに、レジスタ３ｂおよび３ａに保持された
係数データが与えられる。このようなガロア体乗算器４
ａおよび４ｂとしては、たとえば、セルラアレイ乗算器
(Cellular-Array Multiplier) が適している。さらに、
選択器２ａおよび２ｂから出力される係数データは、そ
のまま、レジスタ５ａならびに６ａおよびレジスタ５ｂ
ならびに６ｂを介して出力０および出力Ｐとして出力さ
れる。なお、出力Ｐは図１のフロー図の処理Ｂの係数で
ある。そして、ガロア体乗算器４ａおよび４ｂの出力
は、ガロア体加算器７に与えられる。このガロア体加算
器７は排他的論理和によって構成されている。ガロア体
加算器７の出力がレジスタ８を介して出力Ｑ、すなわち
図１のフロー図の処理Ａの係数として出力される。
和演算の繰り返しであり、したがって図６に示す基本演
算回路１が利用できるのである。図６に示す基本演算回
路１において、選択器２ａおよび２ｂは、それぞれ、入
力に応じて処理Ａおよび処理Ｂ（図１）を選択して係数
のデータを出力する。選択器２ａおよび２ｂから出力さ
れた係数データは、それぞれ、レジスタ３ａおよび３ｂ
にロードされ、保持されるとともに、ガロア体乗算器４
ａおよび４ｂに与えられる。ガロア体乗算器４ａおよび
４ｂは、さらに、レジスタ３ｂおよび３ａに保持された
係数データが与えられる。このようなガロア体乗算器４
ａおよび４ｂとしては、たとえば、セルラアレイ乗算器
(Cellular-Array Multiplier) が適している。さらに、
選択器２ａおよび２ｂから出力される係数データは、そ
のまま、レジスタ５ａならびに６ａおよびレジスタ５ｂ
ならびに６ｂを介して出力０および出力Ｐとして出力さ
れる。なお、出力Ｐは図１のフロー図の処理Ｂの係数で
ある。そして、ガロア体乗算器４ａおよび４ｂの出力
は、ガロア体加算器７に与えられる。このガロア体加算
器７は排他的論理和によって構成されている。ガロア体
加算器７の出力がレジスタ８を介して出力Ｑ、すなわち
図１のフロー図の処理Ａの係数として出力される。
【００１３】この図６の基本演算回路１において、ま
ず、誤り数値多項式を導出する第１の処理は、次のよう
に行われる。
ず、誤り数値多項式を導出する第１の処理は、次のよう
に行われる。
【００１４】
【数４】Ａ0 ＝ｘ2t＝ｘ8 Ｂ0 ＝Ｓ（ｘ）＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ4
ｘ4 ＋Ｓ3 ｘ3＋Ｓ2 ｘ2 ＋Ｓ1 ｘ＋Ｓ0 deg Ａ0 ＞deg Ｂ0 であるから処理Ａを選択 α＝Ｓ7 ，β＝１ Ａ1 ＝Ｓ6 ｘ7 ＋Ｓ5 ｘ6 ＋Ｓ4 ｘ5 ＋Ｓ3 ｘ4 ＋Ｓ2
ｘ3 ＋Ｓ1 ｘ2＋Ｓ0 ｘ Ｂ1 ＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ4 ｘ4 ＋Ｓ3
ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 図６の基本演算回路１においては、図示しないクロック
毎に処理を進めるもの（同期処理）であり、この基本演
算回路１における処理は多項式の係数のみの処理であ
り、次数はクロック毎に時系列的に進む。
ｘ4 ＋Ｓ3 ｘ3＋Ｓ2 ｘ2 ＋Ｓ1 ｘ＋Ｓ0 deg Ａ0 ＞deg Ｂ0 であるから処理Ａを選択 α＝Ｓ7 ，β＝１ Ａ1 ＝Ｓ6 ｘ7 ＋Ｓ5 ｘ6 ＋Ｓ4 ｘ5 ＋Ｓ3 ｘ4 ＋Ｓ2
ｘ3 ＋Ｓ1 ｘ2＋Ｓ0 ｘ Ｂ1 ＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ4 ｘ4 ＋Ｓ3
ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 図６の基本演算回路１においては、図示しないクロック
毎に処理を進めるもの（同期処理）であり、この基本演
算回路１における処理は多項式の係数のみの処理であ
り、次数はクロック毎に時系列的に進む。
【００１５】そして、初期入力としてＡには「１」，
「０」，「０」，「０」，「０」，「０」，「０」が、
そしてＢにはＳ7 ，Ｓ6 ，Ｓ5 ，Ｓ4 ，Ｓ3 ，Ｓ2 ，Ｓ
1 ，Ｓ 0 が、それぞれ、クロック毎に入力される。そし
て、選択器２ａおよび２ｂは、それぞれ、入力Ａまたは
Ｂが選択的に出力されるように制御される。このとき、
レジスタ３ａにはＡ0 の最高次係数「１」が、レジスタ
３ｂにはシンドロームＳ 7 が、それぞれ保持される。そ
の保持期間は誤り数値多項式および誤り位置多項式が導
出されるまでである。そして、このレジスタ３ａおよび
３ｂによる保持が完了した後、ガロア体乗算器４ａおよ
び４ｄならびにガロア体加算器７によって、１クロック
期間に、「１・Ｓ6 ＋０・Ｓ7 」の演算が行われる。こ
のような演算を、クロック毎に、入力される係数に対し
て実行し、出力ＱからはＡ1 の、出力ＰからはＢ1 の係
数がそれぞれ出力される。
「０」，「０」，「０」，「０」，「０」，「０」が、
そしてＢにはＳ7 ，Ｓ6 ，Ｓ5 ，Ｓ4 ，Ｓ3 ，Ｓ2 ，Ｓ
1 ，Ｓ 0 が、それぞれ、クロック毎に入力される。そし
て、選択器２ａおよび２ｂは、それぞれ、入力Ａまたは
Ｂが選択的に出力されるように制御される。このとき、
レジスタ３ａにはＡ0 の最高次係数「１」が、レジスタ
３ｂにはシンドロームＳ 7 が、それぞれ保持される。そ
の保持期間は誤り数値多項式および誤り位置多項式が導
出されるまでである。そして、このレジスタ３ａおよび
３ｂによる保持が完了した後、ガロア体乗算器４ａおよ
び４ｄならびにガロア体加算器７によって、１クロック
期間に、「１・Ｓ6 ＋０・Ｓ7 」の演算が行われる。こ
のような演算を、クロック毎に、入力される係数に対し
て実行し、出力ＱからはＡ1 の、出力ＰからはＢ1 の係
数がそれぞれ出力される。
【００１６】そして、第２の処理は次のように行われ
る。
る。
【００１７】
【数５】Ａ1 ＝Ｓ6 ｘ7 ＋Ｓ5 ｘ6 ＋Ｓ4 ｘ5 ＋Ｓ3 ｘ
4 ＋Ｓ2 ｘ3 ＋Ｓ1 ｘ2＋Ｓ0 ｘ Ｂ1 ＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ4 ｘ4 ＋Ｓ3
ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 deg Ａ1 ＝deg Ｂ1 であるから処理Ａを選択 α＝Ｓ7 ，β＝Ｓ6 Ａ2 ＝（Ｓ5 Ｓ7 ＋Ｓ6 2）ｘ6 ＋（Ｓ4 Ｓ7 ＋Ｓ
5 Ｓ6 ）ｘ5＋（Ｓ3 Ｓ7 ＋Ｓ4 Ｓ6 ）ｘ4 ＋（Ｓ2 Ｓ
7 ＋Ｓ3 Ｓ6 ）ｘ3＋（Ｓ1 Ｓ7 ＋Ｓ2 Ｓ6 ）ｘ2 ＋
（Ｓ0 Ｓ7 ＋Ｓ2 Ｓ6 ）ｘ＋Ｓ0 Ｓ6 Ｂ2 ＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ4 ｘ4 ＋Ｓ3
ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 このとき、第１の処理における出力０，ＰおよびＱは、
それぞれ、次段の基本演算回路の入力Ａ，ＢおよびＣに
それぞれ出力される。すなわち、図６に示す基本演算回
路１を図７に示すようにカスケード接続し、それによっ
て、入力Ｃから前段の出力Ｑ、すなわちＡ1 の係数を受
け取り、入力Ｂから前段の出力Ｐ、すなわちＢ1 の係数
を受け取り、deg Ａ1 ＝deg Ｂ1 の条件から、選択器２
ａは入力Ｃの情報がＸとして出力されるように選択し、
選択器２ｂは入力Ｂの情報が出力Ｙとして出力されるよ
うに選択する。そして、レジスタ３ａにはＳ6 が、そし
てレジスタ３ｂにはＳ7 がそれぞれ保持される。そし
て、以下、第１の処理と同様の処理を繰り返すことによ
って、出力ＱからＡ2 の係数が、出力ＰからＢ2 の係数
が、それぞれ出力される。
4 ＋Ｓ2 ｘ3 ＋Ｓ1 ｘ2＋Ｓ0 ｘ Ｂ1 ＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ4 ｘ4 ＋Ｓ3
ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 deg Ａ1 ＝deg Ｂ1 であるから処理Ａを選択 α＝Ｓ7 ，β＝Ｓ6 Ａ2 ＝（Ｓ5 Ｓ7 ＋Ｓ6 2）ｘ6 ＋（Ｓ4 Ｓ7 ＋Ｓ
5 Ｓ6 ）ｘ5＋（Ｓ3 Ｓ7 ＋Ｓ4 Ｓ6 ）ｘ4 ＋（Ｓ2 Ｓ
7 ＋Ｓ3 Ｓ6 ）ｘ3＋（Ｓ1 Ｓ7 ＋Ｓ2 Ｓ6 ）ｘ2 ＋
（Ｓ0 Ｓ7 ＋Ｓ2 Ｓ6 ）ｘ＋Ｓ0 Ｓ6 Ｂ2 ＝Ｓ7 ｘ7 ＋Ｓ6 ｘ6 ＋Ｓ5 ｘ5 ＋Ｓ4 ｘ4 ＋Ｓ3
ｘ3 ＋Ｓ2 ｘ2＋Ｓ1 ｘ＋Ｓ0 このとき、第１の処理における出力０，ＰおよびＱは、
それぞれ、次段の基本演算回路の入力Ａ，ＢおよびＣに
それぞれ出力される。すなわち、図６に示す基本演算回
路１を図７に示すようにカスケード接続し、それによっ
て、入力Ｃから前段の出力Ｑ、すなわちＡ1 の係数を受
け取り、入力Ｂから前段の出力Ｐ、すなわちＢ1 の係数
を受け取り、deg Ａ1 ＝deg Ｂ1 の条件から、選択器２
ａは入力Ｃの情報がＸとして出力されるように選択し、
選択器２ｂは入力Ｂの情報が出力Ｙとして出力されるよ
うに選択する。そして、レジスタ３ａにはＳ6 が、そし
てレジスタ３ｂにはＳ7 がそれぞれ保持される。そし
て、以下、第１の処理と同様の処理を繰り返すことによ
って、出力ＱからＡ2 の係数が、出力ＰからＢ2 の係数
が、それぞれ出力される。
【００１８】上述の第１の処理および第２の処理と同様
の処理を合計８回すなわち訂正可能なシンボル数４×２
の処理を繰り返すとdeg Ａ＜ｔとなり、したがって出力
Ｑから誤り数値多項式の係数が出力される。このため、
図６に示す基本演算回路１は、図７に示すように、８個
カスケード接続される。また、誤り数値多項式で保持さ
れている最高次係数を保持した状態で、図１に示すよう
にＡをＬに、ＢをＭに書き換えて同様の処理を実行すれ
ば、誤り位置多項式の係数を得ることができる。
の処理を合計８回すなわち訂正可能なシンボル数４×２
の処理を繰り返すとdeg Ａ＜ｔとなり、したがって出力
Ｑから誤り数値多項式の係数が出力される。このため、
図６に示す基本演算回路１は、図７に示すように、８個
カスケード接続される。また、誤り数値多項式で保持さ
れている最高次係数を保持した状態で、図１に示すよう
にＡをＬに、ＢをＭに書き換えて同様の処理を実行すれ
ば、誤り位置多項式の係数を得ることができる。
【００１９】このように、図６に示す基本演算回路１を
図７に示すように訂正可能なシンボル数×２個カスケー
ド接続することによって、図１のフロー図で示すシスト
リックアルゴリズムに従って、リードソロモン符号の誤
り訂正を行うことができる。
図７に示すように訂正可能なシンボル数×２個カスケー
ド接続することによって、図１のフロー図で示すシスト
リックアルゴリズムに従って、リードソロモン符号の誤
り訂正を行うことができる。
【００２０】
【発明が解決しようとする課題】図６および図７に示す
従来のシストリックアレイによる誤り訂正回路では、各
基本演算回路１において図１に示す処理Ａ，処理Ｂおよ
び処理終了にそれぞれ区別し、その処理Ａおよび処理Ｂ
の選択を数４や数５に示す演算過程で扱う次数差の検出
という形で別系統の回路を用いて行う必要があり、した
がって従来技術では、制御が複雑になるばかりではな
く、回路規模が大きくなって集積回路に組み込むのが困
難であるという問題点があった。
従来のシストリックアレイによる誤り訂正回路では、各
基本演算回路１において図１に示す処理Ａ，処理Ｂおよ
び処理終了にそれぞれ区別し、その処理Ａおよび処理Ｂ
の選択を数４や数５に示す演算過程で扱う次数差の検出
という形で別系統の回路を用いて行う必要があり、した
がって従来技術では、制御が複雑になるばかりではな
く、回路規模が大きくなって集積回路に組み込むのが困
難であるという問題点があった。
【００２１】それゆえに、この発明の主たる目的は、簡
単な回路および制御で実現できる、誤り訂正回路を提供
することである。この発明の他の目的は、回路規模を大
きくすることのない、誤り訂正回路を提供することであ
る。
単な回路および制御で実現できる、誤り訂正回路を提供
することである。この発明の他の目的は、回路規模を大
きくすることのない、誤り訂正回路を提供することであ
る。
【００２２】
【課題を解決するための手段】この発明は、誤り訂正処
理に際してユークリッドの互除法によりガロア体の元を
係数とする誤り数値多項式と誤り位置多項式とを導出す
る誤り訂正回路において、第１の多項式のみを処理する
ための第１の基本演算回路と、第２の多項式のみを処理
するための、第２の基本演算回路とを備え、第１の基本
演算回路と第２の基本演算回路とを交互にカスケード接
続したことを特徴とする、誤り訂正回路である。
理に際してユークリッドの互除法によりガロア体の元を
係数とする誤り数値多項式と誤り位置多項式とを導出す
る誤り訂正回路において、第１の多項式のみを処理する
ための第１の基本演算回路と、第２の多項式のみを処理
するための、第２の基本演算回路とを備え、第１の基本
演算回路と第２の基本演算回路とを交互にカスケード接
続したことを特徴とする、誤り訂正回路である。
【００２３】
【作用】第１の基本演算回路では第１の多項式、具体的
には多項式Ａ（Ｌ）のみを処理し、第２の基本演算回路
では第２の多項式Ｂ（Ｍ）のみを処理する。
には多項式Ａ（Ｌ）のみを処理し、第２の基本演算回路
では第２の多項式Ｂ（Ｍ）のみを処理する。
【００２４】
【発明の効果】この発明によれば、各専用の第１および
第２の基本演算回路を交互にカスケード接続するもので
あるため、従来のように多項式ないし処理を選択するた
めの選択器やその制御が不要となるので、回路および制
御が簡単になる。ゼロ検出器を設ければ、次数差を検出
しなくてもよいので、回路規模が大きくなることがな
い。
第２の基本演算回路を交互にカスケード接続するもので
あるため、従来のように多項式ないし処理を選択するた
めの選択器やその制御が不要となるので、回路および制
御が簡単になる。ゼロ検出器を設ければ、次数差を検出
しなくてもよいので、回路規模が大きくなることがな
い。
【００２５】この発明の上述の目的，その他の目的，特
徴および利点は、図面を参照して行う以下の実施例の詳
細な説明から一層明らかとなろう。
徴および利点は、図面を参照して行う以下の実施例の詳
細な説明から一層明らかとなろう。
【００２６】
【実施例】先に説明したように、誤り数値多項式の係数
および誤り位置多項式の係数を演算する過程において、
基本演算回路に含まれる選択器の制御（選択）は、同一
のシステムで異なる符号、たとえばdeg Ａ0 ≧deg Ｂ0
とdeg Ａ0 ＜deg Ｂ0 の処理を同じシステムで取り扱う
場合以外では、一義的に決定される。すなわち、先に述
べた例では、処理Ａ（第１の処理）→処理Ａ（第２の処
理）→処理Ｂ（第３の処理）→処理Ａ（第４の処理）→
処理Ｂ（第５の処理）→処理Ａ（第６の処理）→処理Ｂ
（第７の処理）→処理Ａ（第８の処理）のような処理手
順となる。したがって、選択器の制御（選択）は固定化
され、それを基本演算回路から削除することができる。
この点に着目して、以下に述べる実施例では、図２に示
す処理Ａのための専用の基本演算回路１０および図３に
示す処理Ｂのための専用の基本演算回路２０を用いる。
および誤り位置多項式の係数を演算する過程において、
基本演算回路に含まれる選択器の制御（選択）は、同一
のシステムで異なる符号、たとえばdeg Ａ0 ≧deg Ｂ0
とdeg Ａ0 ＜deg Ｂ0 の処理を同じシステムで取り扱う
場合以外では、一義的に決定される。すなわち、先に述
べた例では、処理Ａ（第１の処理）→処理Ａ（第２の処
理）→処理Ｂ（第３の処理）→処理Ａ（第４の処理）→
処理Ｂ（第５の処理）→処理Ａ（第６の処理）→処理Ｂ
（第７の処理）→処理Ａ（第８の処理）のような処理手
順となる。したがって、選択器の制御（選択）は固定化
され、それを基本演算回路から削除することができる。
この点に着目して、以下に述べる実施例では、図２に示
す処理Ａのための専用の基本演算回路１０および図３に
示す処理Ｂのための専用の基本演算回路２０を用いる。
【００２７】図２を参照して、処理Ａのための基本演算
回路１０は、選択器１１ａおよび１１ｂを含み、この選
択器１１ａおよび１１ｂは、それぞれ、入力された多項
式を積和計算回路に伝達するとともに、最高次係数保持
用レジスタ１２ａに最高次係数もしくは「１」を、最高
次係数保持用レジスタ１２ｂに最高次係数もしくは
「０」を保持させる。そして、この選択器１１ａおよび
１１ｂの出力は、たとえばセルラアレイ乗算器のような
ガロア体乗算器１３ａおよび１３ｂにそれぞれ与えられ
る。ガロア体乗算器１３ａおよび１３ｂには、また、レ
ジスタ１２ｂおよび１２ａで保持されている最高次係数
が入力される。
回路１０は、選択器１１ａおよび１１ｂを含み、この選
択器１１ａおよび１１ｂは、それぞれ、入力された多項
式を積和計算回路に伝達するとともに、最高次係数保持
用レジスタ１２ａに最高次係数もしくは「１」を、最高
次係数保持用レジスタ１２ｂに最高次係数もしくは
「０」を保持させる。そして、この選択器１１ａおよび
１１ｂの出力は、たとえばセルラアレイ乗算器のような
ガロア体乗算器１３ａおよび１３ｂにそれぞれ与えられ
る。ガロア体乗算器１３ａおよび１３ｂには、また、レ
ジスタ１２ｂおよび１２ａで保持されている最高次係数
が入力される。
【００２８】また、選択器１１ｂから入力された係数は
レジスタ１４および１５を介して、そのまま、出力Ｐ、
すなわち次段処理の係数として出力される。一方、ガロ
ア体乗算器１３ａおよび１３ｂの出力がガロア体加算器
１６に与えられる。したがって、処理Ａの積和演算がガ
ロア体乗算器１３ａおよび１３ｂならびにガロア体加算
器１６によって達成される。ガロア体加算器１６の出力
である積和演算の結果はレジスタ１７を介して出力Ｑ、
すなわち次段処理の係数として出力される。
レジスタ１４および１５を介して、そのまま、出力Ｐ、
すなわち次段処理の係数として出力される。一方、ガロ
ア体乗算器１３ａおよび１３ｂの出力がガロア体加算器
１６に与えられる。したがって、処理Ａの積和演算がガ
ロア体乗算器１３ａおよび１３ｂならびにガロア体加算
器１６によって達成される。ガロア体加算器１６の出力
である積和演算の結果はレジスタ１７を介して出力Ｑ、
すなわち次段処理の係数として出力される。
【００２９】図３を参照して、処理Ｂのための基本演算
回路２０は、選択器２１ａおよび２１ｂを含み、この選
択器２１ａおよび２１ｂは、それぞれ、入力された多項
式を積和計算回路に伝達するとともに、最高次係数保持
用レジスタ２２ａに最高次係数もしくは「１」を、最高
次係数保持用レジスタ２２ｂに最高次係数もしくは
「０」を保持させる。そして、この選択器２１ａおよび
２１ｂの出力は、たとえばセルラアレイ乗算器のような
ガロア体乗算器２３ａおよび２３ｂにそれぞれ与えられ
る。ガロア体乗算器２３ａおよび３３ｂには、また、レ
ジスタ２２ｂおよび２２ａで保持されている最高次係数
が入力される。
回路２０は、選択器２１ａおよび２１ｂを含み、この選
択器２１ａおよび２１ｂは、それぞれ、入力された多項
式を積和計算回路に伝達するとともに、最高次係数保持
用レジスタ２２ａに最高次係数もしくは「１」を、最高
次係数保持用レジスタ２２ｂに最高次係数もしくは
「０」を保持させる。そして、この選択器２１ａおよび
２１ｂの出力は、たとえばセルラアレイ乗算器のような
ガロア体乗算器２３ａおよび２３ｂにそれぞれ与えられ
る。ガロア体乗算器２３ａおよび３３ｂには、また、レ
ジスタ２２ｂおよび２２ａで保持されている最高次係数
が入力される。
【００３０】また、選択器２１ｂから入力された係数は
レジスタ２４および２５を介して、そのまま、出力Ｐ、
すなわち次段処理の係数として出力される。一方、ガロ
ア体乗算器２３ａおよび２３ｂの出力がガロア体加算器
２６に与えられる。したがって処理Ｂの積和演算がガロ
ア体乗算器２３ａおよび２３ｂならびにガロア体加算器
２６によって達成される。ガロア体加算器２６の出力で
ある積和演算の結果はレジスタ２７を介して出力Ｑ、す
なわち次段処理の係数として出力される。
レジスタ２４および２５を介して、そのまま、出力Ｐ、
すなわち次段処理の係数として出力される。一方、ガロ
ア体乗算器２３ａおよび２３ｂの出力がガロア体加算器
２６に与えられる。したがって処理Ｂの積和演算がガロ
ア体乗算器２３ａおよび２３ｂならびにガロア体加算器
２６によって達成される。ガロア体加算器２６の出力で
ある積和演算の結果はレジスタ２７を介して出力Ｑ、す
なわち次段処理の係数として出力される。
【００３１】図２および図３を参照して、さらに注目す
べきは、レジスタ１７およびレジスタ２７にゼロ検出器
１８および２８をそれぞれ設けたことである。より詳し
く述べると、誤りシンボル数が４個の場合には先に述べ
た固定的な処理手順で問題を生じることは特にないが、
誤りシンボル数がそれ以下すなわち１〜３個の場合に
は、最後の処理過程（第８の処理）に至る以前に図１の
フロー図の条件すなわちdeg Ａ＜ｔまたはdeg Ｂ＜ｔの
条件を満たす。このような場合には、レジスタ１７およ
び２７に保持されている、現処理で得られた結果である
多項式の各係数をそのまま次段の基本演算回路に伝達す
る必要がある。そこで、図２および図３実施例において
は、レジスタ１７および２７の出力に関連してゼロ検出
回路１８および２８を設け、レジスタ１７および２７に
伝達される演算結果が最高次係数のはずである時点で
「０」を検出した場合には、ゼロ検出回路１８および２
８からゼロ検出出力Ｚを出力するようにしている。
べきは、レジスタ１７およびレジスタ２７にゼロ検出器
１８および２８をそれぞれ設けたことである。より詳し
く述べると、誤りシンボル数が４個の場合には先に述べ
た固定的な処理手順で問題を生じることは特にないが、
誤りシンボル数がそれ以下すなわち１〜３個の場合に
は、最後の処理過程（第８の処理）に至る以前に図１の
フロー図の条件すなわちdeg Ａ＜ｔまたはdeg Ｂ＜ｔの
条件を満たす。このような場合には、レジスタ１７およ
び２７に保持されている、現処理で得られた結果である
多項式の各係数をそのまま次段の基本演算回路に伝達す
る必要がある。そこで、図２および図３実施例において
は、レジスタ１７および２７の出力に関連してゼロ検出
回路１８および２８を設け、レジスタ１７および２７に
伝達される演算結果が最高次係数のはずである時点で
「０」を検出した場合には、ゼロ検出回路１８および２
８からゼロ検出出力Ｚを出力するようにしている。
【００３２】そして、それに後続する基本演算回路にお
いてはレジスタ１２ａまたは１２ｂおよび２２ａまたは
２２ｂにその時点で得られた最高次係数すなわち「０」
を保持させることを中止し、レジスタ１７および２７の
「０」が検出された基本演算回路に後続する基本演算回
路が処理Ａ用のものすなわち図２の基本演算回路１０で
あれば、レジスタ１２ａには「１」を、レジスタ１２ｂ
には「０」をそれぞれ保持させ、後続する基本演算回路
が処理Ｂ用のものすなわち図３の基本演算回路２０であ
れば、レジスタ２２ａには「０」を、レジスタ２２ｂに
は「１」を保持させる。
いてはレジスタ１２ａまたは１２ｂおよび２２ａまたは
２２ｂにその時点で得られた最高次係数すなわち「０」
を保持させることを中止し、レジスタ１７および２７の
「０」が検出された基本演算回路に後続する基本演算回
路が処理Ａ用のものすなわち図２の基本演算回路１０で
あれば、レジスタ１２ａには「１」を、レジスタ１２ｂ
には「０」をそれぞれ保持させ、後続する基本演算回路
が処理Ｂ用のものすなわち図３の基本演算回路２０であ
れば、レジスタ２２ａには「０」を、レジスタ２２ｂに
は「１」を保持させる。
【００３３】したがって、最高次係数として「０」が検
出された基本演算回路に後続する基本演算回路において
は、得られた多項式の各係数には、一方のガロア体乗算
器１３ａ（または１３ｂ）および２３ａ（または２３
ｂ）において「１」が乗算され、他方のガロア体乗算器
１３ｂ（または１３ａ）および２３ｂ（または２３ａ）
において「０」が乗算される。したがって、「１・Ａ＋
０・Ｂ」または「０・Ａ＋１・Ｂ」の演算処理によっ
て、必要な多項式の係数を最後の基本演算回路の出力ま
で伝達することができる。
出された基本演算回路に後続する基本演算回路において
は、得られた多項式の各係数には、一方のガロア体乗算
器１３ａ（または１３ｂ）および２３ａ（または２３
ｂ）において「１」が乗算され、他方のガロア体乗算器
１３ｂ（または１３ａ）および２３ｂ（または２３ａ）
において「０」が乗算される。したがって、「１・Ａ＋
０・Ｂ」または「０・Ａ＋１・Ｂ」の演算処理によっ
て、必要な多項式の係数を最後の基本演算回路の出力ま
で伝達することができる。
【００３４】このように基本演算回路１０および２０か
らゼロ検出出力Ｚが出力されるため、基本演算回路１０
および２０の各選択器１１ａ，１１ｂ，２１ａおよび２
１ｂは、前段の基本演算回路からゼロ検出出力Ｚが得ら
れたとき、レジスタ１２ａ（または１２ｂ）および２２
ａ（または２２ｂ）に「１」（または「０」）を保持さ
せる。
らゼロ検出出力Ｚが出力されるため、基本演算回路１０
および２０の各選択器１１ａ，１１ｂ，２１ａおよび２
１ｂは、前段の基本演算回路からゼロ検出出力Ｚが得ら
れたとき、レジスタ１２ａ（または１２ｂ）および２２
ａ（または２２ｂ）に「１」（または「０」）を保持さ
せる。
【００３５】このような基本演算回路１０および２０を
用いて、図４の誤り訂正回路１００が構成される。ただ
し、第１の処理は、先の数４からもわかるように、入力
された係数をそのまま出力するだけである。したがっ
て、図４実施例において初段の基本演算回路３０は図５
に示すように、３つのレジスタ３１ａ，３１ｂおよび３
２のみによって構成される。そして、レジスタ３１ａの
出力が出力Ｑすなわち次段処理の係数となりレジスタ３
２の出力が出力Ｐすなわち次段処理の係数となる。
用いて、図４の誤り訂正回路１００が構成される。ただ
し、第１の処理は、先の数４からもわかるように、入力
された係数をそのまま出力するだけである。したがっ
て、図４実施例において初段の基本演算回路３０は図５
に示すように、３つのレジスタ３１ａ，３１ｂおよび３
２のみによって構成される。そして、レジスタ３１ａの
出力が出力Ｑすなわち次段処理の係数となりレジスタ３
２の出力が出力Ｐすなわち次段処理の係数となる。
【００３６】図４実施例の誤り訂正回路１００において
は、初段の基本演算回路として図５に示す基本演算回路
３０を用い、その入力Ａにｘ2tを、そして入力Ｂにシン
ドローム多項式を与える。そして、初段の基本演算回路
３０の出力ＱおよびＰが、次段の処理Ａ用の基本演算回
路１０の入力ＡおよびＢにそれぞれ与えられる。さら
に、第２段目の基本演算回路１０の出力ＱおよびＰが第
３段目に配置された処理Ｂのための基本演算回路２０の
入力ＡおよびＢにそれぞれ与えられる。以下同様にし
て、処理Ａ用の基本演算回路１０および処理Ｂ用の基本
演算回路２０が図４に示すように交互にカスケード接続
される。
は、初段の基本演算回路として図５に示す基本演算回路
３０を用い、その入力Ａにｘ2tを、そして入力Ｂにシン
ドローム多項式を与える。そして、初段の基本演算回路
３０の出力ＱおよびＰが、次段の処理Ａ用の基本演算回
路１０の入力ＡおよびＢにそれぞれ与えられる。さら
に、第２段目の基本演算回路１０の出力ＱおよびＰが第
３段目に配置された処理Ｂのための基本演算回路２０の
入力ＡおよびＢにそれぞれ与えられる。以下同様にし
て、処理Ａ用の基本演算回路１０および処理Ｂ用の基本
演算回路２０が図４に示すように交互にカスケード接続
される。
【００３７】誤り訂正回路１００には、さらに、複数の
レジスタ１１０が設けられる。このレジスタ１１０は、
図２および図３に示すレジスタ１２ａ（１２ｂ）および
２２ａ（２２ｂ）のためのイネーブル信号（Ｅ）を最適
なタイミングで伝達するためのレジスタである。したが
って、第２段目の基本演算回路１０には「１」であるイ
ネーブル信号が２つのレジスタ１１０を通して与えられ
る。第３段目の基本演算回路２０には、さらに２つのレ
ジスタ１１０を介してイネーブル信号が与えられる。第
２段目の基本演算回路１０と第３段目の基本演算回路２
０との間にはＡＮＤゲート１１１が設けられ、このＡＮ
Ｄゲート１１１の一方入力としては基本演算回路１０の
ゼロ検出出力Ｚが与えられ、他方入力としてはレジスタ
１１０からのイネーブル信号が与えられる。したがっ
て、第３段目の基本演算回路２０のイネーブル信号がイ
ネーブル信号入力端Ｅに入力されると同時に、もしあれ
ば、ＡＮＤゲート１１１を通して、前段の基本演算回路
１０からのゼロ検出出力Ｚがゼロ検出信号入力端Ｆに与
えられる。以下同様にして、各基本演算回路１０のイネ
ーブル信号入力端Ｅには２つのレジスタ１１０を介して
イネーブル信号が与えられ、ゼロ検出信号入力端Ｆには
ＡＮＤゲート１１１を介してゼロ検出信号が与えられ
る。
レジスタ１１０が設けられる。このレジスタ１１０は、
図２および図３に示すレジスタ１２ａ（１２ｂ）および
２２ａ（２２ｂ）のためのイネーブル信号（Ｅ）を最適
なタイミングで伝達するためのレジスタである。したが
って、第２段目の基本演算回路１０には「１」であるイ
ネーブル信号が２つのレジスタ１１０を通して与えられ
る。第３段目の基本演算回路２０には、さらに２つのレ
ジスタ１１０を介してイネーブル信号が与えられる。第
２段目の基本演算回路１０と第３段目の基本演算回路２
０との間にはＡＮＤゲート１１１が設けられ、このＡＮ
Ｄゲート１１１の一方入力としては基本演算回路１０の
ゼロ検出出力Ｚが与えられ、他方入力としてはレジスタ
１１０からのイネーブル信号が与えられる。したがっ
て、第３段目の基本演算回路２０のイネーブル信号がイ
ネーブル信号入力端Ｅに入力されると同時に、もしあれ
ば、ＡＮＤゲート１１１を通して、前段の基本演算回路
１０からのゼロ検出出力Ｚがゼロ検出信号入力端Ｆに与
えられる。以下同様にして、各基本演算回路１０のイネ
ーブル信号入力端Ｅには２つのレジスタ１１０を介して
イネーブル信号が与えられ、ゼロ検出信号入力端Ｆには
ＡＮＤゲート１１１を介してゼロ検出信号が与えられ
る。
【００３８】図４実施例において、誤り数値多項式を導
出する場合、この回路１００の初段の基本演算回路３０
に入力されるＡ0 ＝ｘ2 ｔおよびＢ0 ＝Ｓ（ｘ）におけ
る多項式の最高次係数が入力されるとき、すなわち第１
のクロックに応答して、そのときイネーブル信号として
「１」を初段のレジスタ１１０に入力する。応じて、第
２クロックが与えられたときには、初段の基本演算回路
３０の出力Ｑから、演算された最高次係数が出力される
と同時に、初段のレジスタ１１０から「１」が出力さ
れ、第３クロックに応答して、後続する第２段目の基本
演算回路１０のイネーブル信号入力端Ｅに第２段目のレ
ジスタ１１０を通してイネーブル信号「１」が与えられ
る。したがって、この第３クロックに応答して、第２段
目の基本演算回路１０に含まれるレジスタ１２ａおよび
１２ｂ（図２）には、そのイネーブル信号によって、初
段の基本演算回路３０の演算結果である誤り数値多項式
の最高次係数が伝達され、保持される。この場合、レジ
スタ１２ａおよび１２ｂは、イネーブル信号（Ｅ）が
「１」のとき最高次係数を格納し、次にそのイネーブル
信号（Ｅ）が「１」になるまでその情報を保持する。
出する場合、この回路１００の初段の基本演算回路３０
に入力されるＡ0 ＝ｘ2 ｔおよびＢ0 ＝Ｓ（ｘ）におけ
る多項式の最高次係数が入力されるとき、すなわち第１
のクロックに応答して、そのときイネーブル信号として
「１」を初段のレジスタ１１０に入力する。応じて、第
２クロックが与えられたときには、初段の基本演算回路
３０の出力Ｑから、演算された最高次係数が出力される
と同時に、初段のレジスタ１１０から「１」が出力さ
れ、第３クロックに応答して、後続する第２段目の基本
演算回路１０のイネーブル信号入力端Ｅに第２段目のレ
ジスタ１１０を通してイネーブル信号「１」が与えられ
る。したがって、この第３クロックに応答して、第２段
目の基本演算回路１０に含まれるレジスタ１２ａおよび
１２ｂ（図２）には、そのイネーブル信号によって、初
段の基本演算回路３０の演算結果である誤り数値多項式
の最高次係数が伝達され、保持される。この場合、レジ
スタ１２ａおよび１２ｂは、イネーブル信号（Ｅ）が
「１」のとき最高次係数を格納し、次にそのイネーブル
信号（Ｅ）が「１」になるまでその情報を保持する。
【００３９】このような動作を最終段のすなわち第８段
の基本演算回路１０の出力Ｑから誤り数値多項式の係数
が出力されるまで繰り返される。ただし、最終段の基本
演算回路１０においてはゼロ検出の必要はないため、図
２に示すゼロ検出回路１８は削除されてもよい。誤り数
値多項式の係数が求められると、次に、誤り位置多項式
の係数を導出する。この場合、初段の基本演算回路３０
の入力として、図１のフロー図に示すように、入力Ａに
Ｌ＝０を、入力ＢにＭ＝１をそれぞれ入力し、先に説明
した誤り数値多項式の場合と同様の演算を実行すればよ
い。ただし、誤り位置多項式を導出する場合には、イネ
ーブル信号として「０」を与える。
の基本演算回路１０の出力Ｑから誤り数値多項式の係数
が出力されるまで繰り返される。ただし、最終段の基本
演算回路１０においてはゼロ検出の必要はないため、図
２に示すゼロ検出回路１８は削除されてもよい。誤り数
値多項式の係数が求められると、次に、誤り位置多項式
の係数を導出する。この場合、初段の基本演算回路３０
の入力として、図１のフロー図に示すように、入力Ａに
Ｌ＝０を、入力ＢにＭ＝１をそれぞれ入力し、先に説明
した誤り数値多項式の場合と同様の演算を実行すればよ
い。ただし、誤り位置多項式を導出する場合には、イネ
ーブル信号として「０」を与える。
【００４０】このようにして、誤り数値多項式の係数の
導出過程で得られた各基本演算回路に保持されている最
高次係数が、誤り位置多項式の係数が導出されるまで保
持されることになる。なお、上述の例では、Ａ0 にｘ2t
が入力され、Ｂ0 にシンドロームＳ0 〜Ｓ7が存在する
（８５，７７，９）符号について説明したが、この発明
は（８５，７５，１１）符号などにも適用できる。この
場合、Ａ0 にはｘ2tが入力され、Ｂ0にはシンドローム
Ｓ0 〜Ｓ9 が存在することになり、処理Ｂ→処理Ａ→処
理Ａ→処理Ｂ→処理Ａ→…と行われる。したがって、第
３の基本演算回路３０（図５）は処理Ｂのためのものと
なる。ただし、この場合でも、基本演算回路１０および
２０が交互に接続される部分があることはいうまでもな
い。
導出過程で得られた各基本演算回路に保持されている最
高次係数が、誤り位置多項式の係数が導出されるまで保
持されることになる。なお、上述の例では、Ａ0 にｘ2t
が入力され、Ｂ0 にシンドロームＳ0 〜Ｓ7が存在する
（８５，７７，９）符号について説明したが、この発明
は（８５，７５，１１）符号などにも適用できる。この
場合、Ａ0 にはｘ2tが入力され、Ｂ0にはシンドローム
Ｓ0 〜Ｓ9 が存在することになり、処理Ｂ→処理Ａ→処
理Ａ→処理Ｂ→処理Ａ→…と行われる。したがって、第
３の基本演算回路３０（図５）は処理Ｂのためのものと
なる。ただし、この場合でも、基本演算回路１０および
２０が交互に接続される部分があることはいうまでもな
い。
【図１】シストリックアルゴリズムに基づく誤り数値多
項式および誤り位置多項式の係数を演算するためのフロ
ー図である。
項式および誤り位置多項式の係数を演算するためのフロ
ー図である。
【図２】この発明の実施例で用いられる第１の基本演算
回路を示すブロック図である。
回路を示すブロック図である。
【図３】この発明の実施例で用いられる第２の基本演算
回路を示すブロック図である。
回路を示すブロック図である。
【図４】この発明の一実施例を示すブロック図である。
【図５】図４実施例で用いられる初段の基本演算回路を
示すブロック図である。
示すブロック図である。
【図６】従来のシストリックアレイの基本演算回路を示
すブロック図である。
すブロック図である。
【図７】図６の基本演算回路を用いた従来の誤り訂正回
路を示すブロック図である。
路を示すブロック図である。
１００ …誤り訂正回路 １０ …第１の基本演算回路 ２０ …第２の基本演算回路 ３０ …第３の基本演算回路 １１ａ，１１ｂ，２１ａ，２１ｂ …選択器 １２ａ，１２ｂ，２２ａ，２２ｂ …最高次係数保持用
レジスタ １３ａ，１３ｂ，２３ａ，２３ｂ …ガロア体乗算器 １４，１５，１７，２４，２５，２７ …出力用レジス
タ １６，２６ …ガロア体加算器 １８，２８ …ゼロ検出器 １１０ …イネーブル信号伝達用レジスタ １１１ …ゼロ検出信号伝達用ＡＮＤゲート
レジスタ １３ａ，１３ｂ，２３ａ，２３ｂ …ガロア体乗算器 １４，１５，１７，２４，２５，２７ …出力用レジス
タ １６，２６ …ガロア体加算器 １８，２８ …ゼロ検出器 １１０ …イネーブル信号伝達用レジスタ １１１ …ゼロ検出信号伝達用ＡＮＤゲート
Claims (7)
- 【請求項１】誤り訂正処理に際してユークリッドの互除
法によりガロア体の元を係数とする誤り数値多項式と誤
り位置多項式とを導出する誤り訂正回路において、 第１の多項式のみを処理するための第１の基本演算回路
と、第２の多項式のみを処理するための、第２の基本演
算回路とを備え、前記第１の基本演算回路と前記第２の
基本演算回路とを交互にカスケード接続したことを特徴
とする、誤り訂正回路。 - 【請求項２】前記第１の基本演算回路は、前記第１の多
項式の係数を保持するための２個の第１のレジスタ、前
記次係数に基づいて積和演算を実現する２個のガロア体
乗算器および１個のガロア体加算器を含む積和演算手
段、および前記積和演算手段の演算結果である係数を出
力する少なくとも２個の第２のレジスタを含み、 前記第２の基本演算回路は、前記第２の多項式の係数を
保持するための２個の第３のレジスタ、前記次係数に基
づいて積和演算を実現する２個のガロア体乗算器および
１個のガロア体加算器を含む積和演算手段、および前記
積和演算手段の演算結果である係数を出力する少なくと
も２個の第４のレジスタを含む、請求項１記載の誤り訂
正回路。 - 【請求項３】前記第１の基本演算回路は前記第２のレジ
スタの１個に関連して設けられかつ当該第２のレジスタ
に格納された係数がゼロであることを検出したときゼロ
検出信号を出力する第１のゼロ検出器を含み、 前記第２の基本演算回路は前記第４のレジスタの１個に
関連して設けられかつ当該第４のレジスタに格納された
係数がゼロであることを検出したときゼロ検出信号を出
力する第２のゼロ検出器を含む、請求項２記載の誤り訂
正回路。 - 【請求項４】前記第１の基本演算回路は前記第２のゼロ
検出器から前記ゼロ検出信号が入力されたとき前記第１
のレジスタの一方には「１」を、他方には「０」を保持
させる第１の選択器を含み、 前記第２の基本演算回路は前記第１のゼロ検出器から前
記ゼロ検出信号が入力されたとき前記第３のレジスタの
一方には「１」を、他方には「０」を保持させる第２の
選択器を含み、 前記第１および第２の選択器は、前記ゼロ検出信号が入
力されないとき前記第１および第３のレジスタにそれぞ
れ前段から入力された最高次係数を保持させる、請求項
３記載の誤り訂正回路。 - 【請求項５】前記第１および第３のレジスタの各々は、
第１レベルのイネーブル信号に応答して格納し、第２レ
ベルの前記イネーブル信号に応答して格納を中止し、さ
らに前記第１および第２の基本演算回路に前記イネーブ
ル信号を順次付与するためのイネーブル信号付与手段を
備える、請求項４記載の誤り訂正回路。 - 【請求項６】前記イネーブル信号に応じて前記第１およ
び第２のゼロ検出信号を前記第２および第１の基本演算
回路に入力するゲート手段を備える、請求項５記載の誤
り訂正回路。 - 【請求項７】初段に設けられ、かつ次段の基本演算回路
に係数を入力するための少なくとも２個の第５のレジス
タを含む第３の基本演算回路を備える、請求項１ないし
６のいずれかに記載の誤り訂正回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6029871A JPH07240692A (ja) | 1994-02-28 | 1994-02-28 | 誤り訂正回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6029871A JPH07240692A (ja) | 1994-02-28 | 1994-02-28 | 誤り訂正回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH07240692A true JPH07240692A (ja) | 1995-09-12 |
Family
ID=12288044
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP6029871A Withdrawn JPH07240692A (ja) | 1994-02-28 | 1994-02-28 | 誤り訂正回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH07240692A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8335973B2 (en) | 2008-01-17 | 2012-12-18 | Hitachi, Ltd. | Processing module, error correction decoding circuit, and processing method for error locator polynomial |
-
1994
- 1994-02-28 JP JP6029871A patent/JPH07240692A/ja not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8335973B2 (en) | 2008-01-17 | 2012-12-18 | Hitachi, Ltd. | Processing module, error correction decoding circuit, and processing method for error locator polynomial |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6119262A (en) | Method and apparatus for solving key equation polynomials in decoding error correction codes | |
| JP3970337B2 (ja) | 大規模データ・ブロックのためのハードウェア最適化リード・ソロモン・デコーダ | |
| US6347389B1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| JP3233860B2 (ja) | リードソロモン復号器 | |
| US5805617A (en) | Apparatus for computing error correction syndromes | |
| WO1995012850A1 (en) | Reed-solomon decoder | |
| JPH0936755A (ja) | 復号装置及びその方法 | |
| US5983389A (en) | Error correction decoding apparatus | |
| JPH07212248A (ja) | エラー位置多項式の計算方法およびその装置 | |
| KR100970223B1 (ko) | 리드-솔로몬 코드의 소프트-결정 디코딩 방법, 리드-솔로몬 코드워드 디코더 및 컴퓨터 프로그램 제품 | |
| US4899341A (en) | Error correction circuit | |
| JPH0458619A (ja) | 誤り訂正システム | |
| JP3245290B2 (ja) | 復号方法とその装置 | |
| JP3343857B2 (ja) | 復号装置、演算装置およびこれらの方法 | |
| US20030131308A1 (en) | Method and apparatus for solving key equation polynomials in decoding error correction codes | |
| EP0989680A1 (en) | Method of correcting lost data and circuit thereof | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| JPH07240692A (ja) | 誤り訂正回路 | |
| JP3233502B2 (ja) | 復号化装置 | |
| JPH09307458A (ja) | エラー訂正向け多項式評価装置 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JPH06314978A (ja) | チェン・サーチ回路 | |
| JP2718481B2 (ja) | ロングディスタンスコードの誤り訂正装置 | |
| US20030009723A1 (en) | Simplified reed-solomon decoding circuit and method of decoding reed-solomon codes | |
| JPH047847B2 (ja) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20010508 |