JPH11196006A - 並列処理シンドロ−ム計算回路及びリ−ド・ソロモン複合化回路 - Google Patents
並列処理シンドロ−ム計算回路及びリ−ド・ソロモン複合化回路Info
- Publication number
- JPH11196006A JPH11196006A JP9368781A JP36878197A JPH11196006A JP H11196006 A JPH11196006 A JP H11196006A JP 9368781 A JP9368781 A JP 9368781A JP 36878197 A JP36878197 A JP 36878197A JP H11196006 A JPH11196006 A JP H11196006A
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- input
- output
- signal
- galois field
- 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.)
- Pending
Links
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
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/1515—Reed-Solomon codes
-
- 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/159—Remainder calculation, e.g. for encoding and syndrome calculation
- H03M13/1595—Parallel or block-wise remainder calculation
-
- 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
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)
Abstract
(57)【要約】
【課題】高速動作可能なシンドローム多項式計算回路及
びリードソロモン復号化回路の提供。 【解決手段】高次の信号のI1,I2,I3が第１〜３ガロア体
乗算回路に入力し乗数はS0,S1,S2,S3の各々で、a^6,a^
9,a^12と^2,a^4,a^6,a^8とa,a^2,a^3,a^4となり該第１
〜第３乗算回路出力とI4は排他論理和回路に入力しその
出力はD-F/Fに入力し、その出力は第４ガロア体乗算回
路とAND回路に入力し該第４乗算回路の乗数はS0,S1,S2,
S3の各場合でa^4,a^8,a^12,a^16となり該第４乗算回路
出力は排他論理和回路の第５入力に入力し、クロックは
D-F/F及びカウンタに入力されカウンタ値はフレームパ
ルスの入力でリセットしカウンタ値が0-4の間はL、5の
時はHに変化しカウンタ出力はAND回路入力され、信号が
Hの時のみ、D-F/Fからの信号が出力される
びリードソロモン復号化回路の提供。 【解決手段】高次の信号のI1,I2,I3が第１〜３ガロア体
乗算回路に入力し乗数はS0,S1,S2,S3の各々で、a^6,a^
9,a^12と^2,a^4,a^6,a^8とa,a^2,a^3,a^4となり該第１
〜第３乗算回路出力とI4は排他論理和回路に入力しその
出力はD-F/Fに入力し、その出力は第４ガロア体乗算回
路とAND回路に入力し該第４乗算回路の乗数はS0,S1,S2,
S3の各場合でa^4,a^8,a^12,a^16となり該第４乗算回路
出力は排他論理和回路の第５入力に入力し、クロックは
D-F/F及びカウンタに入力されカウンタ値はフレームパ
ルスの入力でリセットしカウンタ値が0-4の間はL、5の
時はHに変化しカウンタ出力はAND回路入力され、信号が
Hの時のみ、D-F/Fからの信号が出力される
Description
【０００１】
【発明の属する技術分野】本発明は、シンドロ−ム多項
式計算回路及びリ−ドソロモン復号化回路に関し、特
に、高速大容量の光通信システム等、高スル−プットが
要求されるシステムに適用して好適なリ−ドソロモン復
号化回路及び該回路に用いられるシンドロ−ム多項式計
算回路に関する。
式計算回路及びリ−ドソロモン復号化回路に関し、特
に、高速大容量の光通信システム等、高スル−プットが
要求されるシステムに適用して好適なリ−ドソロモン復
号化回路及び該回路に用いられるシンドロ−ム多項式計
算回路に関する。
【０００２】
【従来の技術】従来、リ−ド・ソロモン復号化器として
は、例えば文献（“VLSＩ向きリ−ドソロモン符号化・
複合化方式”、電子情報通信学会論文誌vol.Ｊ71−Ａ、
ｐｐ.751−759）に記載されているように、入力した信
号をシストリックアレイ構造で順次処理していく方法が
知られている。
は、例えば文献（“VLSＩ向きリ−ドソロモン符号化・
複合化方式”、電子情報通信学会論文誌vol.Ｊ71−Ａ、
ｐｐ.751−759）に記載されているように、入力した信
号をシストリックアレイ構造で順次処理していく方法が
知られている。
【０００３】上記文献に記載の方式においては、図５に
示すようなＰＥと呼ばれる単位構造により処理を行う。
図５を参照すると、入力信号には７つの信号Ａ、Ｂ、
Ｃ、Ｄ、Ｅ、Ｉ、Ｊが入力され、信号Ａ、Ｂ、Ｃ、Ｄ、
Ｅはそれぞれセレクタ５０１に入力される。またセレク
タ回路５０１には制御信号Ｓ１、Ｓ２が入力される。セ
レクタ５０１の第１の出力は、第２のＤ型フリップフロ
ップ（「Ｄ−Ｆ／Ｆ」という）５０８に入力され、第２
の出力は３分岐され、それぞれ第１のガロア体のかけ算
回路５０２の第１の入力、及び第１のＤ−Ｆ/Ｆ５０５
の入力に入力され、さらに出力Ｇに出力される。
示すようなＰＥと呼ばれる単位構造により処理を行う。
図５を参照すると、入力信号には７つの信号Ａ、Ｂ、
Ｃ、Ｄ、Ｅ、Ｉ、Ｊが入力され、信号Ａ、Ｂ、Ｃ、Ｄ、
Ｅはそれぞれセレクタ５０１に入力される。またセレク
タ回路５０１には制御信号Ｓ１、Ｓ２が入力される。セ
レクタ５０１の第１の出力は、第２のＤ型フリップフロ
ップ（「Ｄ−Ｆ／Ｆ」という）５０８に入力され、第２
の出力は３分岐され、それぞれ第１のガロア体のかけ算
回路５０２の第１の入力、及び第１のＤ−Ｆ/Ｆ５０５
の入力に入力され、さらに出力Ｇに出力される。
【０００４】セレクタ５０１の第３の出力は３分岐さ
れ、それぞれ第２のガロア体かけ算回路５０３の第１の
入力、及び第５のＤ−Ｆ/Ｆ５０７の入力端子に入力さ
れ、さらに出力Ｈに出力される。
れ、それぞれ第２のガロア体かけ算回路５０３の第１の
入力、及び第５のＤ−Ｆ/Ｆ５０７の入力端子に入力さ
れ、さらに出力Ｈに出力される。
【０００５】入力信号Ｉは第１のガロア体かけ算回路５
０２の第２の入力に入力され、入力信号Ｊは第２のガロ
ア体のかけ算回路５０３の第２の入力に入力される。
０２の第２の入力に入力され、入力信号Ｊは第２のガロ
ア体のかけ算回路５０３の第２の入力に入力される。
【０００６】第１のガロア体かけ算回路５０２の出力は
排他論理和回路５０４の第１の入力に入力され、第２の
ガロア体かけ算回路５０３の出力は排他論理和回路５０
４の第２の入力に入力される。
排他論理和回路５０４の第１の入力に入力され、第２の
ガロア体かけ算回路５０３の出力は排他論理和回路５０
４の第２の入力に入力される。
【０００７】第１ないし第５のＤ−Ｆ／Ｆ５０５、５０
８、５０６、５０９、５０７の出力はそれぞれ出力Ｏ、
Ｒ、Ｑ、Ｔ、Ｐとして出力される。
８、５０６、５０９、５０７の出力はそれぞれ出力Ｏ、
Ｒ、Ｑ、Ｔ、Ｐとして出力される。
【０００８】従来例では、上記のＰＥを一つの単位とし
て様々な処理を行っている。シンドロ−ム多項式計算
部、ユ−クリッド互助法計算部、チェン解法及び誤り値
計算部ともに上記のＰＥを接続することで実現する。
て様々な処理を行っている。シンドロ−ム多項式計算
部、ユ−クリッド互助法計算部、チェン解法及び誤り値
計算部ともに上記のＰＥを接続することで実現する。
【０００９】シンドロ−ム多項式は、図６に示すよう
に、ＰＥを直列に（Ｋ+1）個接続し、入力Ｉには、それ
ぞれ、ａないしａ＾（Ｋ+1）（記号＾はべき乗を示す）
を入力し、Ｃは“０”固定、Ｊは“１”固定、Ｂには前
段ＰＥのＰの出力を入力する。この時、最終段のＰＥの
Ｑ出力がシンドロ−ム多項式の出力となる。
に、ＰＥを直列に（Ｋ+1）個接続し、入力Ｉには、それ
ぞれ、ａないしａ＾（Ｋ+1）（記号＾はべき乗を示す）
を入力し、Ｃは“０”固定、Ｊは“１”固定、Ｂには前
段ＰＥのＰの出力を入力する。この時、最終段のＰＥの
Ｑ出力がシンドロ−ム多項式の出力となる。
【００１０】セレクタの出力は第１のＰＥでは、Ｘの出
力としてＣ、Ｙの出力としてＢが選択され、それ以降の
ＰＥではＸとしてＡ、ＹとしてＢが選択される。
力としてＣ、Ｙの出力としてＢが選択され、それ以降の
ＰＥではＸとしてＡ、ＹとしてＢが選択される。
【００１１】ユ−クリッド互助法計算部では、図７に示
すように、ＰＥを（Ｋ+2）個直列に接続し、それぞれ前
段のＲ、Ｑ、Ｔの出力が次段のＡ、Ｃ、Ｂに入力され
る。
すように、ＰＥを（Ｋ+2）個直列に接続し、それぞれ前
段のＲ、Ｑ、Ｔの出力が次段のＡ、Ｃ、Ｂに入力され
る。
【００１２】それぞれのＰＥでは、Ｈ及びＧの出力は、
最初に入力された値を保持するレジスタに入力され、レ
ジスタはその値を計算処理中保持し、それぞれ入力Ｉ、
Ｊに入力する。
最初に入力された値を保持するレジスタに入力され、レ
ジスタはその値を計算処理中保持し、それぞれ入力Ｉ、
Ｊに入力する。
【００１３】また、出力Ｏ、Ｐはそれぞれ入力Ｄ、Ｅに
入力される。初段のＰＥでは、Ａにはシンドロ−ム多項
式の計算結果が入力され、Ｃは“０”固定、Ｂは最初の
ビットのみ“１”を入力する。
入力される。初段のＰＥでは、Ａにはシンドロ−ム多項
式の計算結果が入力され、Ｃは“０”固定、Ｂは最初の
ビットのみ“１”を入力する。
【００１４】それぞれのＰＥにおけるセレクタは前段の
処理結果により、選択する信号が変化する。これは、各
ＰＥ毎に出力信号Ｒ、Ｑ、Ｔの次数により、モ−ド（mo
de）がnoｐ、reＤuceＡ、reＤuceBに変化し、それに伴
い、後段のセレクタはnoｐの場合、ＸはＡを、ＹはＢを
選択する。ReＤuceＡの場合はＸにＣを、ＹにＢを選択
し、reＤuceＢの場合はＸにＡを、ＹにＣを選択する。
処理結果により、選択する信号が変化する。これは、各
ＰＥ毎に出力信号Ｒ、Ｑ、Ｔの次数により、モ−ド（mo
de）がnoｐ、reＤuceＡ、reＤuceBに変化し、それに伴
い、後段のセレクタはnoｐの場合、ＸはＡを、ＹはＢを
選択する。ReＤuceＡの場合はＸにＣを、ＹにＢを選択
し、reＤuceＢの場合はＸにＡを、ＹにＣを選択する。
【００１５】これにより、最終段のＰＥのＲから誤り位
置多項式が、Ｑから誤り値多項式が出力される。
置多項式が、Ｑから誤り値多項式が出力される。
【００１６】さらに後段では、図８に示すように、ＰＥ
を２個、及びガロア体の逆数演算回路により構成され、
Ｉ、Ｊ、Ａ、Ｂにはユ−クリッド互助法で計算された多
項式、及び、その微分した値が入力される。初段のＰＥ
の出力Ｑはガロア体逆数演算回路に入力され、その出力
は次段ＰＥの入力Ｂに入力される。この時、最終段ＰＥ
の出力Ｑの信号が誤り位置及び誤り値の情報となり、こ
れから誤りの値が修正される。
を２個、及びガロア体の逆数演算回路により構成され、
Ｉ、Ｊ、Ａ、Ｂにはユ−クリッド互助法で計算された多
項式、及び、その微分した値が入力される。初段のＰＥ
の出力Ｑはガロア体逆数演算回路に入力され、その出力
は次段ＰＥの入力Ｂに入力される。この時、最終段ＰＥ
の出力Ｑの信号が誤り位置及び誤り値の情報となり、こ
れから誤りの値が修正される。
【００１７】
【発明が解決しようとする課題】しかし、上記した従来
の技術では、高速な信号を復号化するには、信号と同速
度のクロックでシンドロ−ム回路が動作しなければなら
ない。従って、Ｇｂ／Ｓクラスの大容量信号を処理する
ためには、あらかじめ信号を処理できる速度まで時分割
分離し、処理を行っている。このため、装置規模が大き
くなるという問題が生じる。
の技術では、高速な信号を復号化するには、信号と同速
度のクロックでシンドロ−ム回路が動作しなければなら
ない。従って、Ｇｂ／Ｓクラスの大容量信号を処理する
ためには、あらかじめ信号を処理できる速度まで時分割
分離し、処理を行っている。このため、装置規模が大き
くなるという問題が生じる。
【００１８】また信号を分離することによる遅延が生じ
る等の問題がある。
る等の問題がある。
【００１９】ここで、ユ−クリッド互助法回路、チェン
解法回路や誤り値計算部は処理速度自体は信号の速度に
対して遅い速度でも処理が可能なため、シンドロ−ム回
路の処理速度の高速化が復号化をする際、重要となって
くる。
解法回路や誤り値計算部は処理速度自体は信号の速度に
対して遅い速度でも処理が可能なため、シンドロ−ム回
路の処理速度の高速化が復号化をする際、重要となって
くる。
【００２０】したがって、本発明は、上記問題点に鑑み
てなされたものであって、その目的は、高速動作可能な
シンドロ−ム多項式計算回路及びリ−ドソロモン複合化
回路を提供することにある。
てなされたものであって、その目的は、高速動作可能な
シンドロ−ム多項式計算回路及びリ−ドソロモン複合化
回路を提供することにある。
【００２１】
【課題を解決するための手段】前記目的を達成するた
め、本発明のガロア体代入回路は、第１乃至第ｊからな
る複数のガロア体乗算回路と、（ｊ＋１）入力排他論理
和回路と、を備え、ｊブロックの時分割分離された信号
入力の内最初の１ブロックの信号は、前記排他論理和回
路の第１の入力に入力され、第２乃至第ｊブロックの信
号は前記第１乃至第（ｊ−１）のガロア体乗算回路に入
力され、前記第１乃至第（ｊ−１）のガロア体乗算回路
は前記排他的論理和回路の第２乃至第のｊの入力に入力
され、前記排他的論理和回路の出力を入力クロック信号
でラッチするラッチ回路と、前記入力クロック信号を１
フレ−ム分をカウントした際に出力信号を論理１とする
カウンタと、前記カウンタの前記出力信号に基づき前記
ラッチ回路の出力を選択出力するゲート回路と、を備
え、前記ラッチ回路の出力は前記第ｊのガロア体乗算回
路に入力され、前記第ｊのガロア体乗算回路の出力が前
記排他的論理和回路の第（ｊ＋１）の入力に接続され、
前記各ガロア体のかけ算回路は、ガロア体ａのべき数が
ｐないしｊｐで構成される。記１フレ−ムの入力がなさ
れた時点で、前記ラッチ回路の出力及び前記カウンタが
リセットされる。
め、本発明のガロア体代入回路は、第１乃至第ｊからな
る複数のガロア体乗算回路と、（ｊ＋１）入力排他論理
和回路と、を備え、ｊブロックの時分割分離された信号
入力の内最初の１ブロックの信号は、前記排他論理和回
路の第１の入力に入力され、第２乃至第ｊブロックの信
号は前記第１乃至第（ｊ−１）のガロア体乗算回路に入
力され、前記第１乃至第（ｊ−１）のガロア体乗算回路
は前記排他的論理和回路の第２乃至第のｊの入力に入力
され、前記排他的論理和回路の出力を入力クロック信号
でラッチするラッチ回路と、前記入力クロック信号を１
フレ−ム分をカウントした際に出力信号を論理１とする
カウンタと、前記カウンタの前記出力信号に基づき前記
ラッチ回路の出力を選択出力するゲート回路と、を備
え、前記ラッチ回路の出力は前記第ｊのガロア体乗算回
路に入力され、前記第ｊのガロア体乗算回路の出力が前
記排他的論理和回路の第（ｊ＋１）の入力に接続され、
前記各ガロア体のかけ算回路は、ガロア体ａのべき数が
ｐないしｊｐで構成される。記１フレ−ムの入力がなさ
れた時点で、前記ラッチ回路の出力及び前記カウンタが
リセットされる。
【００２２】本発明のシンドロ−ム多項式計算回路は、
ｊブロックの入力信号をそれぞれ２分岐し、一つは第２
ないし第（ｊ＋１）のＤ−Ｆ/Ｆに入力し、一つは上記
ガロア体代入回路に入力し、上記動作を行う回路をＫ個
直列に接続し、それぞれのガロア体代入回路のそれぞれ
の出力は論理和回路に入力され、論理和回路の出力がシ
ンドロ−ム多項式計算回路の出力として出力されること
を特徴とする。
ｊブロックの入力信号をそれぞれ２分岐し、一つは第２
ないし第（ｊ＋１）のＤ−Ｆ/Ｆに入力し、一つは上記
ガロア体代入回路に入力し、上記動作を行う回路をＫ個
直列に接続し、それぞれのガロア体代入回路のそれぞれ
の出力は論理和回路に入力され、論理和回路の出力がシ
ンドロ−ム多項式計算回路の出力として出力されること
を特徴とする。
【００２３】本発明のリ−ドソロモン復号化回路は、上
記したシンドロ−ム多項式計算回路と、ユ−クリッド互
助法計算回路と、第１から第Ｋのチェン解法計算回路
と、第１から第Ｋの誤り値計算回路と、信号分離回路
と、シフトレジスタ回路と誤り訂正回路とからなり、ｊ
ブロックの入力信号は２分岐され、一つはシンドロ−ム
多項式回路に一つは信号分離回路に入力され、シンドロ
−ム多項式の出力はユ−クリッド互助法計算回路に入力
され、ユ−クリッド互助法計算回路の誤り位置多項式計
算結果はＫ分岐され、それぞれ第１ないし第Ｋのチェン
解法計算回路入力され、ユ−クリッド互助法回路の誤り
値多項式計算結果はＫ分岐され、誤り値計算回路の誤り
値多項式計算部に入力され、第１ないし第Ｋのチェン解
法計算回路の出力はそれぞれ第１ないし、第Ｋの誤り値
計算回路の誤り位置入力部に入力され、信号分離回路で
は信号がＫ分岐され、その出力はシフトレジスタに入力
され、シフトレジスタ回路の出力及び第１ないし第Ｋの
誤り値計算回路の出力は誤り訂正回路に入力され、第１
ないし第Ｋのチェン解法計算部において代入するガロア
体の次数はそれぞれ１ないしＫからＫ次ずつ入力され、
チェン解法計算回路及び誤り値計算回路シフトレジスタ
及び誤り訂正部は入力信号の１／Ｋのクロックで動作す
ることを特徴とする。
記したシンドロ−ム多項式計算回路と、ユ−クリッド互
助法計算回路と、第１から第Ｋのチェン解法計算回路
と、第１から第Ｋの誤り値計算回路と、信号分離回路
と、シフトレジスタ回路と誤り訂正回路とからなり、ｊ
ブロックの入力信号は２分岐され、一つはシンドロ−ム
多項式回路に一つは信号分離回路に入力され、シンドロ
−ム多項式の出力はユ−クリッド互助法計算回路に入力
され、ユ−クリッド互助法計算回路の誤り位置多項式計
算結果はＫ分岐され、それぞれ第１ないし第Ｋのチェン
解法計算回路入力され、ユ−クリッド互助法回路の誤り
値多項式計算結果はＫ分岐され、誤り値計算回路の誤り
値多項式計算部に入力され、第１ないし第Ｋのチェン解
法計算回路の出力はそれぞれ第１ないし、第Ｋの誤り値
計算回路の誤り位置入力部に入力され、信号分離回路で
は信号がＫ分岐され、その出力はシフトレジスタに入力
され、シフトレジスタ回路の出力及び第１ないし第Ｋの
誤り値計算回路の出力は誤り訂正回路に入力され、第１
ないし第Ｋのチェン解法計算部において代入するガロア
体の次数はそれぞれ１ないしＫからＫ次ずつ入力され、
チェン解法計算回路及び誤り値計算回路シフトレジスタ
及び誤り訂正部は入力信号の１／Ｋのクロックで動作す
ることを特徴とする。
【００２４】
【発明の実施の形態】本発明の実施の形態について説明
する。本発明のガロア体代入回路は、その好ましい実施
の形態において、ｊ個のガロア体乗算算回路（図１の
１、２、３、４、図１ではｊ＝４）と、（ｊ＋１）個の
入力を持つ排他論理和（ＥｘｃｌｕｓｉｖｅＯＲ）回路
（図１の５）と、Ｄ−Ｆ／Ｆ（Ｄ型フリップフロップ）
（図の６）と、セレクタ回路（図１の７）と、を備えて
構成され、入力信号はｊブロックの時分割分離された信
号が入力され、その内最初の１ブロックの信号（Ｉ１）
は排他論理和回路（図１の５）の第１の入力に入力さ
れ、第２ないし第ｊブロックの信号はそれぞれ第１ない
し第（ｊ−１）のガロア体乗算回路（図１の１、２、
３）に入力され、第１乃至第（ｊ−１）のガロア体の乗
算回路の出力は排他論理和回路の第２乃至第ｊの入力に
入力され、排他論理和回路の出力はＤ−Ｆ/Ｆに入力さ
れ、Ｄ−Ｆ/Ｆの出力は２分岐され、一つは第ｊのガロ
ア体乗算回路（図１の４）に入力され、一つはセレクタ
回路（図１の７）の第１の入力に入力され、第ｊの乗算
回路の出力は排他論理和回路（図１の５）の第（ｊ＋
１）の入力に入力される。
する。本発明のガロア体代入回路は、その好ましい実施
の形態において、ｊ個のガロア体乗算算回路（図１の
１、２、３、４、図１ではｊ＝４）と、（ｊ＋１）個の
入力を持つ排他論理和（ＥｘｃｌｕｓｉｖｅＯＲ）回路
（図１の５）と、Ｄ−Ｆ／Ｆ（Ｄ型フリップフロップ）
（図の６）と、セレクタ回路（図１の７）と、を備えて
構成され、入力信号はｊブロックの時分割分離された信
号が入力され、その内最初の１ブロックの信号（Ｉ１）
は排他論理和回路（図１の５）の第１の入力に入力さ
れ、第２ないし第ｊブロックの信号はそれぞれ第１ない
し第（ｊ−１）のガロア体乗算回路（図１の１、２、
３）に入力され、第１乃至第（ｊ−１）のガロア体の乗
算回路の出力は排他論理和回路の第２乃至第ｊの入力に
入力され、排他論理和回路の出力はＤ−Ｆ/Ｆに入力さ
れ、Ｄ−Ｆ/Ｆの出力は２分岐され、一つは第ｊのガロ
ア体乗算回路（図１の４）に入力され、一つはセレクタ
回路（図１の７）の第１の入力に入力され、第ｊの乗算
回路の出力は排他論理和回路（図１の５）の第（ｊ＋
１）の入力に入力される。
【００２５】本発明の実施の形態において、セレクタの
第２の入力はＬｏｗに固定され、１フレ−ムの入力が終
わるまで、セレクタ回路の出力は第２の入力を選択出力
し、１フレ−ムの入力が入力された後、Ｄ−Ｆ/Ｆの出
力がリセットされると同時に、セレクタ回路は第１の入
力を１クロックの間出力し、各ガロア体の乗算算回路
は、ガロア体ａのべき数がｐないしｊｐで構成される。
第２の入力はＬｏｗに固定され、１フレ−ムの入力が終
わるまで、セレクタ回路の出力は第２の入力を選択出力
し、１フレ−ムの入力が入力された後、Ｄ−Ｆ/Ｆの出
力がリセットされると同時に、セレクタ回路は第１の入
力を１クロックの間出力し、各ガロア体の乗算算回路
は、ガロア体ａのべき数がｐないしｊｐで構成される。
【００２６】本発明のシンドロ−ム多項式計算回路は、
その好ましい実施の形態において、ｊブロックの入力信
号は、縦続接続したｊ個のＤ−Ｆ／Ｆからなるシフトレ
ジスタ（図２の９）に入力し、各段のＤ−Ｆ／Ｆの出力
をそれぞれ上記したガロア体代入回路（図２の１０、１
１、１２、１３）に入力し、前記各ガロア体代入回路の
それぞれの出力は論理和回路（図１の１４）に入力さ
れ、論理和回路の出力がシンドロ−ム多項式計算回路の
出力として出力される。
その好ましい実施の形態において、ｊブロックの入力信
号は、縦続接続したｊ個のＤ−Ｆ／Ｆからなるシフトレ
ジスタ（図２の９）に入力し、各段のＤ−Ｆ／Ｆの出力
をそれぞれ上記したガロア体代入回路（図２の１０、１
１、１２、１３）に入力し、前記各ガロア体代入回路の
それぞれの出力は論理和回路（図１の１４）に入力さ
れ、論理和回路の出力がシンドロ−ム多項式計算回路の
出力として出力される。
【００２７】本発明のリ−ドソロモン復号化回路は、そ
の好ましい実施の形態において、上記したシンドロ−ム
多項式計算回路（図３の１５）と、ユ−クリッド互助法
計算回路（図３の１６）と、第１から第Ｋのチェン解法
計算回路（図３の１７〜２０、図３ではＫ＝４）と、第
１から第Ｋの誤り値計算回路（図３の２１〜２４）と、
シフトレジスタ回路（図３の２６）と、誤り訂正回路
（図３の２５）と、を備えて構成される。
の好ましい実施の形態において、上記したシンドロ−ム
多項式計算回路（図３の１５）と、ユ−クリッド互助法
計算回路（図３の１６）と、第１から第Ｋのチェン解法
計算回路（図３の１７〜２０、図３ではＫ＝４）と、第
１から第Ｋの誤り値計算回路（図３の２１〜２４）と、
シフトレジスタ回路（図３の２６）と、誤り訂正回路
（図３の２５）と、を備えて構成される。
【００２８】ｊブロック（図３ではｊ＝４）の入力信号
は２分岐され、一方はシンドロ−ム多項式回路（図１の
１５）に、他方はシフトレジスタ（図３の２６）に入力
され、シンドロ−ム多項式の出力は、ユ−クリッド互助
法計算回路に入力され、ユ−クリッド互助法計算回路の
誤り位置多項式計算結果はＫ分岐され、それぞれ第１な
いし第Ｋのチェン解法計算回路（図３の１７〜２０）に
入力され、ユ−クリッド互助法計算回路の誤り値多項式
計算結果はＫ分岐され、誤り値計算回路（図３の２１〜
２４）の誤り値多項式計算部に入力され、第１ないし第
Ｋのチェン解法計算回路の出力はそれぞれ第１ないし、
第Ｋの誤り値計算回路の誤り位置入力部に入力される。
は２分岐され、一方はシンドロ−ム多項式回路（図１の
１５）に、他方はシフトレジスタ（図３の２６）に入力
され、シンドロ−ム多項式の出力は、ユ−クリッド互助
法計算回路に入力され、ユ−クリッド互助法計算回路の
誤り位置多項式計算結果はＫ分岐され、それぞれ第１な
いし第Ｋのチェン解法計算回路（図３の１７〜２０）に
入力され、ユ−クリッド互助法計算回路の誤り値多項式
計算結果はＫ分岐され、誤り値計算回路（図３の２１〜
２４）の誤り値多項式計算部に入力され、第１ないし第
Ｋのチェン解法計算回路の出力はそれぞれ第１ないし、
第Ｋの誤り値計算回路の誤り位置入力部に入力される。
【００２９】シフトレジスタ回路（図３の２６）の出力
及び第１ないし第Ｋの誤り値計算回路の出力は誤り訂正
回路に入力され、第１ないし第Ｋのチェン解法計算部に
おいて代入するガロア体の次数はそれぞれ１ないしＫか
らＫ次ずつ入力され、チェン解法計算回路及び誤り値計
算回路シフトレジスタ及び誤り訂正部は入力信号の１／
Ｋのクロックで動作する。
及び第１ないし第Ｋの誤り値計算回路の出力は誤り訂正
回路に入力され、第１ないし第Ｋのチェン解法計算部に
おいて代入するガロア体の次数はそれぞれ１ないしＫか
らＫ次ずつ入力され、チェン解法計算回路及び誤り値計
算回路シフトレジスタ及び誤り訂正部は入力信号の１／
Ｋのクロックで動作する。
【００３０】本発明におけるシンドロ−ム多項式は以下
の計算で説明が可能となる。
の計算で説明が可能となる。
【００３１】シンドロ−ム多項式はα、α2、…、α16
を受信語Ｙ(z)に代入することにより、求めることがで
きる。
を受信語Ｙ(z)に代入することにより、求めることがで
きる。
【００３２】すなわちシンドロ−ム多項式の係数Ｓ
Iは、
Iは、
【００３３】
【数１】
【００３４】で計算される。これを順次受信される受信
語ｒjに対して順次計算していくためには、(式１)を変
形し、
語ｒjに対して順次計算していくためには、(式１)を変
形し、
【００３５】
【数２】
【００３６】となるため、
【００３７】
【数３】
【００３８】のように、逐次計算させていけばよい。
【００３９】これを並列処理する場合に考えると、最高
次の信号には、ａ＾((ｊ−1)*(Ｉ+1))（ここでのｊは並
列処理する値）を掛け、次数が下がる毎に、(ｊ−1)の
値を１づつ下げていけばよい。
次の信号には、ａ＾((ｊ−1)*(Ｉ+1))（ここでのｊは並
列処理する値）を掛け、次数が下がる毎に、(ｊ−1)の
値を１づつ下げていけばよい。
【００４０】この後、全ての信号の排他論理和を行った
後、ａ＾(ｊ*(Ｉ+1))を掛け、次の計算結果との排他論
理和を行うことで、シンドロ−ム多項式が計算される。
後、ａ＾(ｊ*(Ｉ+1))を掛け、次の計算結果との排他論
理和を行うことで、シンドロ−ム多項式が計算される。
【００４１】上記した本発明の実施の形態について更に
詳細に説明すべく、本発明の実施例について図面を参照
して説明する。
詳細に説明すべく、本発明の実施例について図面を参照
して説明する。
【００４２】
【実施例１】本発明の第一の実施例について説明する。
本発明の第一の実施例におけるシンドロ−ム計算回路
は、ガロア体はｘ8+ｘ4＋ｘ2＋1から計算される８ビッ
トの情報に対応しているものとする。また、復号化され
る情報バイトは２８バイトで、冗長符号は４バイトとす
る。この時、誤り訂正能力は２バイト訂正可能となる。
本発明の第一の実施例におけるシンドロ−ム計算回路
は、ガロア体はｘ8+ｘ4＋ｘ2＋1から計算される８ビッ
トの情報に対応しているものとする。また、復号化され
る情報バイトは２８バイトで、冗長符号は４バイトとす
る。この時、誤り訂正能力は２バイト訂正可能となる。
【００４３】この場合、シンドロ−ム多項式は３次の多
項式となり、生成多項式を、
項式となり、生成多項式を、
【００４４】
【数４】
【００４５】とすると、シンドロ−ム多項式の係数Ｓ
0、Ｓ1、Ｓ2、Ｓ3は、それぞれ、情報信号Ｉ(x)に、
ａ、ａ＾２、ａ＾３、ａ＾４を代入することで求める。
0、Ｓ1、Ｓ2、Ｓ3は、それぞれ、情報信号Ｉ(x)に、
ａ、ａ＾２、ａ＾３、ａ＾４を代入することで求める。
【００４６】各シンドロ−ム多項式の係数を計算する回
路構成を図１に示す。シンドロ−ム計算は一度に多くの
信号を扱うために並列化している。
路構成を図１に示す。シンドロ−ム計算は一度に多くの
信号を扱うために並列化している。
【００４７】入力信号は並列に４バイトを入力し、情報
信号の高次の信号からＩ1、Ｉ2、Ｉ3、Ｉ4とする。ここ
でＩ1、Ｉ2、Ｉ3、Ｉ4はそれぞれ１バイトの信号を表
す。Ｉ1は、第１のガロア体乗算回路１に入力され、こ
の乗算回路１の乗数は、S0、S1、S2、S3のそれぞれの場
合において、ａ＾3、ａ＾6、ａ＾9、ａ＾12となる。
信号の高次の信号からＩ1、Ｉ2、Ｉ3、Ｉ4とする。ここ
でＩ1、Ｉ2、Ｉ3、Ｉ4はそれぞれ１バイトの信号を表
す。Ｉ1は、第１のガロア体乗算回路１に入力され、こ
の乗算回路１の乗数は、S0、S1、S2、S3のそれぞれの場
合において、ａ＾3、ａ＾6、ａ＾9、ａ＾12となる。
【００４８】同様に、Ｉ2は第２のガロア体乗算回路２
に入力され、乗数はS0、S1、S2、S3のそれぞれの場合に
おいて、ａ＾2、ａ＾4、ａ＾6、ａ＾8となる。
に入力され、乗数はS0、S1、S2、S3のそれぞれの場合に
おいて、ａ＾2、ａ＾4、ａ＾6、ａ＾8となる。
【００４９】Ｉ3は第３のガロア体乗算回路３に入力さ
れ、この時の乗数は、S0、S1、S2、S3のそれぞれの場合
において、ａ、ａ＾2、ａ＾3、ａ＾4となる。
れ、この時の乗数は、S0、S1、S2、S3のそれぞれの場合
において、ａ、ａ＾2、ａ＾3、ａ＾4となる。
【００５０】第１ないし第３のガロア体乗算回路１、
２、３の出力、及びＩ4は、排他的論理和（ExclusiveＯ
Ｒ）回路５の第１ないし第４の入力端に入力する。
２、３の出力、及びＩ4は、排他的論理和（ExclusiveＯ
Ｒ）回路５の第１ないし第４の入力端に入力する。
【００５１】排他的論理和回路５の出力は、Ｄ型フリッ
プフロップ６のデ−タ入力端に入力され、Ｄ型フリップ
フロップ６の出力は２分岐され、一方は、第４のガロア
体乗算回路４に入力され、他方は論理積（ＡＮＤ）回路
７の第１の入力端に入力される。第４のガロア体乗算回
路４の乗数はＳ０、Ｓ１、Ｓ２、Ｓ３のそれぞれの場合
において、ａ＾4、ａ＾8、ａ＾12、ａ＾16となる。第４
のガロア体乗算回路４の出力は排他論理和回路５の第５
の入力端に入力される。
プフロップ６のデ−タ入力端に入力され、Ｄ型フリップ
フロップ６の出力は２分岐され、一方は、第４のガロア
体乗算回路４に入力され、他方は論理積（ＡＮＤ）回路
７の第１の入力端に入力される。第４のガロア体乗算回
路４の乗数はＳ０、Ｓ１、Ｓ２、Ｓ３のそれぞれの場合
において、ａ＾4、ａ＾8、ａ＾12、ａ＾16となる。第４
のガロア体乗算回路４の出力は排他論理和回路５の第５
の入力端に入力される。
【００５２】また、クロックは、Ｄ型フリップフロップ
６のクロック入力端及びカウンタ８に入力され、カウン
タ値はフレ−ムパルスが入力されるとリセット（ゼロク
リア）し、カウンタ値が０−６間はＬｏｗレベル信号、
カウンタ値が７の時はＨｉｇｈに変化し、クロックカウ
ンタ値をリセットする。
６のクロック入力端及びカウンタ８に入力され、カウン
タ値はフレ−ムパルスが入力されるとリセット（ゼロク
リア）し、カウンタ値が０−６間はＬｏｗレベル信号、
カウンタ値が７の時はＨｉｇｈに変化し、クロックカウ
ンタ値をリセットする。
【００５３】カウンタ８の出力はＡＮＤ回路７の第２の
入力端に入力され、カウンタ８の出力信号がＨｉｇｈレ
ベルの時のみ、Ｄ型フリップフロップ６からの信号が出
力される。また、Ｄ型フリップフロップ６はフレ−ムパ
ルス入力によりリセットされる。
入力端に入力され、カウンタ８の出力信号がＨｉｇｈレ
ベルの時のみ、Ｄ型フリップフロップ６からの信号が出
力される。また、Ｄ型フリップフロップ６はフレ−ムパ
ルス入力によりリセットされる。
【００５４】この回路構成により、シンドロ−ム多項式
のそれぞれの係数を計算することができる。
のそれぞれの係数を計算することができる。
【００５５】
【実施例２】上記した実施例１におけるシンドロ−ム多
項式の係数計算回路を一つの単位として考え、図２に示
すようなブロックとして考える。
項式の係数計算回路を一つの単位として考え、図２に示
すようなブロックとして考える。
【００５６】図２に示すように、入力した４バイト並列
（３２ビット幅）の信号及びフレ−ムパルスは、４ビッ
トシフトレジスタ回路９に入力され、シフトレジスタ９
の各出力はそれぞれシンドロ−ム多項式計算回路の第１
ないし第４の係数計算回路部１０、１１、１２、１３に
入力される。
（３２ビット幅）の信号及びフレ−ムパルスは、４ビッ
トシフトレジスタ回路９に入力され、シフトレジスタ９
の各出力はそれぞれシンドロ−ム多項式計算回路の第１
ないし第４の係数計算回路部１０、１１、１２、１３に
入力される。
【００５７】第１ないし第４の係数計算回路部１０、１
１、１２、１３からの出力は、それそれ論理和（ＯＲ）
回路１４の第１ないし第4の入力端に入力する。
１、１２、１３からの出力は、それそれ論理和（ＯＲ）
回路１４の第１ないし第4の入力端に入力する。
【００５８】この時、各信号のタイムチャ−トは、図４
に示すようになり、各係数計算結果１０〜１３の出力は
シフトレジスタ９にあわせて、１クロック分だけずれる
ために、ＯＲ回路１４の出力はシリアル信号として出力
されることになる。
に示すようになり、各係数計算結果１０〜１３の出力は
シフトレジスタ９にあわせて、１クロック分だけずれる
ために、ＯＲ回路１４の出力はシリアル信号として出力
されることになる。
【００５９】
【実施例３】図３は、本発明の第３の実施例の構成を示
す図である。図３を参照すると、本実施例における復号
化回路は、シンドロ−ム多項式計算部１５、ユ−クリッ
ド互助法計算部１６、第１から第４のチェン解法部１
７、１８、１９、２０、第１から第４の誤り値計算部２
１、２２、２３、２４、シフトレジスタ２６、及び誤り
訂正部２５からなる。本実施例においても、前記実施例
１と同様に、１フレ−ムが２８バイトの情報信号に４バ
イトの冗長符号が付加された信号を取り扱うものとす
る。
す図である。図３を参照すると、本実施例における復号
化回路は、シンドロ−ム多項式計算部１５、ユ−クリッ
ド互助法計算部１６、第１から第４のチェン解法部１
７、１８、１９、２０、第１から第４の誤り値計算部２
１、２２、２３、２４、シフトレジスタ２６、及び誤り
訂正部２５からなる。本実施例においても、前記実施例
１と同様に、１フレ−ムが２８バイトの情報信号に４バ
イトの冗長符号が付加された信号を取り扱うものとす
る。
【００６０】４バイト並列の入力信号（３２ビット）は
２分岐され、一つはシンドロ−ム計算回路１５に、一つ
はシフトレジスタ２６に入力される。
２分岐され、一つはシンドロ−ム計算回路１５に、一つ
はシフトレジスタ２６に入力される。
【００６１】シンドロ−ム計算回路の１バイト並列で出
力された信号は、ユ−クリッド互助法計算回路１６に入
力され、ユ−クリッド互助法計算回路１６からは、誤り
値計算結果及び誤り位置計算結果がそれぞれ１バイト並
列で出力され、誤り位置計算結果は４分岐され、第１な
いし第４のチェン解法計算部１７〜２０に、誤り値計算
結果も４分岐され、第１ないし第４の誤り値計算部２１
〜２４に入力される。
力された信号は、ユ−クリッド互助法計算回路１６に入
力され、ユ−クリッド互助法計算回路１６からは、誤り
値計算結果及び誤り位置計算結果がそれぞれ１バイト並
列で出力され、誤り位置計算結果は４分岐され、第１な
いし第４のチェン解法計算部１７〜２０に、誤り値計算
結果も４分岐され、第１ないし第４の誤り値計算部２１
〜２４に入力される。
【００６２】第１ないし第４のチェン解法部１７〜２０
の計算結果は、それぞれ第１ないし第４の誤り値計算部
２１〜２４に入力され、それぞれの１バイト並列で出力
された信号は誤り訂正部２５に入力される。
の計算結果は、それぞれ第１ないし第４の誤り値計算部
２１〜２４に入力され、それぞれの１バイト並列で出力
された信号は誤り訂正部２５に入力される。
【００６３】なお、２分岐された４バイト並列の入力信
号の一方は、分離回路で、１：４に時分割分離した後、
シフトレジスタ２６に入力する構成としてもよい。シフ
トレジスタ２６の出力は誤り訂正部２５に入力される。
号の一方は、分離回路で、１：４に時分割分離した後、
シフトレジスタ２６に入力する構成としてもよい。シフ
トレジスタ２６の出力は誤り訂正部２５に入力される。
【００６４】この時、シンドロ−ム多項式計算、ユ−ク
リッド互助法、チェン解法、誤り値計算部で計算された
誤り情報とシフトレジスタからの出力で誤り訂正が実行
され、復号化処理結果として出力される。
リッド互助法、チェン解法、誤り値計算部で計算された
誤り情報とシフトレジスタからの出力で誤り訂正が実行
され、復号化処理結果として出力される。
【００６５】シンドロ−ム計算回路は、前記実施例２と
同じ構成であり、これにより、低速な信号速度で処理を
行うことができ、ユ−クリッド互助法もシンドロ−ム計
算結果出力の速度に応じて信号処理が可能となる。
同じ構成であり、これにより、低速な信号速度で処理を
行うことができ、ユ−クリッド互助法もシンドロ−ム計
算結果出力の速度に応じて信号処理が可能となる。
【００６６】また、チェン解法計算部や誤り値計算回路
部も、入力信号速度と同じクロックで動作させることが
できる。
部も、入力信号速度と同じクロックで動作させることが
できる。
【００６７】なお、本発明は、上記した実施例の構成に
のみ限定されるものでなく、処理する信号の並列処理の
度合いを増やすことで更に大容量の信号を処理すること
が可能となることはいうまでもない。
のみ限定されるものでなく、処理する信号の並列処理の
度合いを増やすことで更に大容量の信号を処理すること
が可能となることはいうまでもない。
【００６８】
【発明の効果】以上説明したように、本発明のシンドロ
−ム多項式計算回路を用いることにより、大容量の信号
を高速に処理することが可能なリ−ドソロモン復号化回
路を構築することができる、という効果を奏する。その
理由は、上記のように構成されてなる本発明において
は、シンドローム計算回路は入力信号と比べて低速な信
号速度で処理可能であるためである。
−ム多項式計算回路を用いることにより、大容量の信号
を高速に処理することが可能なリ−ドソロモン復号化回
路を構築することができる、という効果を奏する。その
理由は、上記のように構成されてなる本発明において
は、シンドローム計算回路は入力信号と比べて低速な信
号速度で処理可能であるためである。
【図１】本発明の第１の実施例に係るガロア体代入回路
の回路構成を示す図である。
の回路構成を示す図である。
【図２】本発明の第２の実施例に係るシンドロ−ム多項
式計算回路の回路構成を示す図である。
式計算回路の回路構成を示す図である。
【図３】本発明の第３の実施例に係るリ−ドソロモン復
号化回路の回路構成を示す図である。
号化回路の回路構成を示す図である。
【図４】本発明の第２の実施例に係るシンドロ−ム多項
式計算回路の動作の一例を示すタイミングチャ−トであ
る。
式計算回路の動作の一例を示すタイミングチャ−トであ
る。
【図５】従来技術におけるリ−ドソロモン復号化の基本
単位であるＰＥの回路構成を示す図である。
単位であるＰＥの回路構成を示す図である。
【図６】従来技術におけるシンドロ−ム計算回路の回路
構成を示す図である。
構成を示す図である。
【図７】従来技術におけるユ−クリッド互助法計算回路
の回路構成を示す図である。
の回路構成を示す図である。
【図８】従来技術における誤り訂正部計算回路の回路構
成を示す図である。
成を示す図である。
１ 第１のガロア体かけ算回路 ２ 第２のガロア体かけ算回路 ３ 第３のガロア体かけ算回路 ４ 第４のガロア体かけ算回路 ５ 排他論理和回路 ６ Ｄ−Ｆ／Ｆ（Ｄ型フリップフロップ） ７ ＡＮＤ回路 ８ カウンタ ９ シフトレジスタ １０ 第１のガロア体代入回路 １１ 第２のガロア体代入回路 １２ 第３のガロア体代入回路 １３ 第４のガロア体代入回路 １４ ＯＲ回路 １５ シンドロ−ム多項式計算回路 １６ ユ−クリッド互助法計算回路 １７ 第１のチェン解法計算回路 １８ 第２のチェン解法計算回路 １９ 第３のチェン解法計算回路 ２０ 第４のチェン解法計算回路 ２１ 第１の誤り値計算回路 ２２ 第２の誤り値計算回路 ２３ 第３の誤り値計算回路 ２４ 第４の誤り値計算回路 ２５ 誤り訂正回路 ２６ シフトレジスタ
Claims (6)
- 【請求項１】シンドロ−ム多項式計算回路におけるａ＾
ｐ（但し、＾は巾乗を示す）のガロア体代入回路におい
て、 ｊ個のガロア体掛け算回路と、 （ｊ＋１）個の入力を持つ排他論理和回路と、 Ｄ型フリップフロップと、 セレクタ回路と、 カウンタ回路とを備え、入力信号としてｊブロックの時
分割分離された信号が入力され、その内最初の１ブロッ
クの信号は、前記排他論理和回路の第１の入力に入力さ
れ、第２ないし第ｊブロックの信号は、それぞれ第１な
いし第（ｊ−１）のガロア体掛け算回路に入力され、 前記第１ないし第（ｊ−１）のガロア体のかけ算回路の
出力は、前記排他論理和回路の第２ないし第ｊの入力に
それぞれ入力され、 前記排他論理和回路の出力はＤ型フリップフロップのデ
−タ入力端に入力され、 前記Ｄ型フリップフロップの出力は２分岐され、一つは
第ｊのかけ算回路に入力され、他の一つは前記セレクタ
回路の第１の入力端に入力され、 前記第ｊのかけ算回路の出力は、前記排他論理和回路の
第（ｊ＋１）の入力に入力され、 入力されたクロック信号は、前記カウンタ及びＤ型フリ
ップフロップのクロック端に入力され、 前記セレクタの第２の入力端は論理０固定とされ、 前記カウンタから出力される制御信号が前記セレクタ回
路に選択制御信号として入力され、 前記カウンタは１フレ−ムの信号入力をカウントし、１
フレ−ムの信号の最後の入力時のカウンタ値の時、前記
制御信号を論理１として出力し、 前記セレクタ回路は、前記制御信号が論理０の時、第２
の入力端を、論理１の時第１の入力端の信号を選択出力
し、 １フレ−ムの入力が入力された後、前記Ｄ型フリップフ
ロップの出力及びカウンタ値はリセットされ、 前記各ガロア体のかけ算回路は、ガロア体ａのべき数が
ｐないしｊｐで構成される、ことを特徴とするガロア体
代入回路。 - 【請求項２】ｊブロックの入力信号をそれぞれ２分岐
し、一つは第１ないし第ｊのＤ型フリップフロップに入
力し、一つは請求項１記載の前記ガロア体代入回路に入
力し、 上記回路をＫ個直列に接続し、前記各ガロア体代入回路
のそれぞれの出力は論理和回路に入力され、 論理和回路の出力がシンドロ−ム多項式計算回路の出力
として出力されることを特徴とするシンドロ−ム多項式
計算回路。 - 【請求項３】請求項２に記載のシンドロ−ム多項式計算
回路と、 ユ−クリッド互助法計算回路と、 第１から第Ｋのチェン解法計算回路と、 第１から第Ｋの誤り値計算回路と、 シフトレジスタ回路と、 誤り訂正回路と、を備え、ｊブロックの入力信号は２分
岐され、一方は前記シンドロ−ム多項式回路に、他方は
前記シフトレジスタに入力され、 前記シンドロ−ム多項式の出力はユ−クリッド互助法計
算回路に入力され、 前記ユ−クリッド互助法計算回路の誤り位置多項式計算
結果はＫ分岐され、それぞれ前記第１ないし第Ｋのチェ
ン解法計算回路入力され、 前記ユ−クリッド互助法計算回路の誤り値多項式計算結
果はＫ分岐され、前記誤り値計算回路の誤り値多項式計
算部に入力され、 前記第１ないし第Ｋのチェン解法計算回路の出力はそれ
ぞれ第１ないし、第Ｋの前記誤り値計算回路の誤り位置
入力部に入力され、 前記シフトレジスタ回路の出力及び前記第１ないし第Ｋ
の誤り値計算回路の出力は誤り訂正回路に入力され、 前記第１ないし第Ｋのチェン解法計算回路において代入
するガロア体の次数はそれぞれ１ないしＫからＫ次ずつ
入力され、 前記チェン解法計算回路、前記誤り値計算回路、前記シ
フトレジスタ及び前記誤り訂正部は入力信号の１／Ｋの
クロックで動作する、ことを特徴とするリ−ドソロモン
復号化回路。 - 【請求項４】シンドロ−ム多項式計算回路におけるａ＾
ｐのガロア体代入回路において、 第１乃至第ｊからなる複数のガロア体乗算回路と、 （ｊ＋１）入力排他論理和回路と、を備え、 ｊブロックの時分割分離された信号入力の内最初の１ブ
ロックの信号は、前記排他論理和回路の第１の入力に入
力され、第２乃至第ｊブロックの信号は前記第１乃至第
（ｊ−１）のガロア体乗算回路に入力され、前記第１乃
至第（ｊ−１）のガロア体乗算回路は前記排他的論理和
回路の第２乃至第のｊの入力に入力され、 前記排他的論理和回路の出力を入力クロック信号でラッ
チするラッチ回路と、 前記入力クロック信号を１フレ−ム分をカウントした際
に制御出力信号を論理１とするカウンタと、 前記カウンタの前記制御出力信号に基づき前記ラッチ回
路の出力を選択出力するゲート回路と、を備え、 前記ラッチ回路の出力は前記第ｊのガロア体乗算回路に
入力され、 前記第ｊのガロア体乗算回路の出力が前記排他的論理和
回路の第（ｊ＋１）の入力に接続され、 前記各ガロア体のかけ算回路は、ガロア体ａのべき数が
ｐないしｊｐで構成される、ことを特徴とするガロア体
代入回路。 - 【請求項５】前記１フレ−ムの入力がなされた時点で、
前記ラッチ回路の出力及び前記カウンタがリセットされ
る、ことを特徴とする請求項４記載のガロア体代入回
路。 - 【請求項６】入力信号を並列入力とするｊビット長シフ
トレジスタと、 前記シフトレジスタの各段の出力をそれぞれ入力とす
る、請求項４記載のｊ個の前記ガロア体代入回路と、 前記各ガロア体代入回路のそれぞれの出力を入力としこ
れらの論理和をシンドロ−ム多項式計算出力とする論理
和回路と、 を備えたことを特徴とするシンドロ−ム多項式計算回
路。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9368781A JPH11196006A (ja) | 1997-12-26 | 1997-12-26 | 並列処理シンドロ−ム計算回路及びリ−ド・ソロモン複合化回路 |
| US09/219,324 US6341297B1 (en) | 1997-12-26 | 1998-12-23 | Parallel processing syndrome calculating circuit and Reed-Solomon decoding circuit |
| FR9816315A FR2773284B1 (fr) | 1997-12-26 | 1998-12-23 | Circuit de calcul de polynome de syndrome et un circuit de decodage reed-solomon |
| US10/012,511 US6880121B2 (en) | 1997-12-26 | 2001-12-12 | Parallel processing syndrome calculating circuit and reed-solomon decoding circuit |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9368781A JPH11196006A (ja) | 1997-12-26 | 1997-12-26 | 並列処理シンドロ−ム計算回路及びリ−ド・ソロモン複合化回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11196006A true JPH11196006A (ja) | 1999-07-21 |
Family
ID=18492738
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP9368781A Pending JPH11196006A (ja) | 1997-12-26 | 1997-12-26 | 並列処理シンドロ−ム計算回路及びリ−ド・ソロモン複合化回路 |
Country Status (3)
| Country | Link |
|---|---|
| US (2) | US6341297B1 (ja) |
| JP (1) | JPH11196006A (ja) |
| FR (1) | FR2773284B1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104917535A (zh) * | 2014-03-14 | 2015-09-16 | 三星电子株式会社 | 用于分组码的高阶伴随式计算器和计算高阶伴随式的方法 |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000172520A (ja) * | 1998-12-04 | 2000-06-23 | Fujitsu Ltd | ガロア体演算プロセッサ |
| JP3953220B2 (ja) * | 1999-02-03 | 2007-08-08 | 沖電気工業株式会社 | ユークリッド互除法実行回路及び演算回路 |
| TW440824B (en) * | 1999-04-02 | 2001-06-16 | Via Tech Inc | Device and method for compact disk decoding synchrome calculation |
| ITTO20010667A1 (it) * | 2001-07-10 | 2003-01-10 | Telecom Italia Lab Spa | Metodo per generare circuiti elettronici. |
| US7228490B2 (en) * | 2004-02-19 | 2007-06-05 | Quantum Corporation | Error correction decoder using cells with partial syndrome generation |
| JP2008513129A (ja) * | 2004-09-17 | 2008-05-01 | ジーアイ・ダイナミックス・インコーポレーテッド | 内腔内アンカ装置 |
| US8261176B2 (en) * | 2009-06-30 | 2012-09-04 | Sandisk Il Ltd. | Polynomial division |
| KR102118605B1 (ko) * | 2014-03-14 | 2020-06-04 | 삼성전자주식회사 | 블록 코드에 대하여 저복잡도로 고차 신드롬을 계산하는 고차 신드롬 계산기 및 고차 신드롬 계산 방법 |
Family Cites Families (23)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4797848A (en) * | 1986-04-18 | 1989-01-10 | Hughes Aircraft Company | Pipelined bit-serial Galois Field multiplier |
| EP0566215B1 (en) * | 1986-09-30 | 1996-11-20 | Canon Kabushiki Kaisha | Error correction apparatus |
| US4847801A (en) * | 1987-10-26 | 1989-07-11 | Cyclotomics, Inc. | Compact galois field multiplier |
| FR2628862B1 (fr) * | 1988-03-17 | 1993-03-12 | Thomson Csf | Multiplieur-additionneur parametrable dans les corps de galois, et son utilisation dans un processeur de traitement de signal numerique |
| WO1992013344A1 (fr) * | 1991-01-22 | 1992-08-06 | Fujitsu Limited | Dispositif de traitement pour la correction d'erreurs et procede de correction d'erreurs |
| US5414719A (en) * | 1992-04-24 | 1995-05-09 | Sharp Kabushiki Kaisha | Operating circuit for galois field |
| ES2068105B1 (es) * | 1992-11-30 | 1995-11-01 | Alcatel Standard Electrica | Metodo y dispositivo de deteccion y correccion de errores en cabeceras de celulas atm. |
| JP2694792B2 (ja) | 1993-01-27 | 1997-12-24 | 日本電気株式会社 | 誤り位置多項式演算回路 |
| JP3241851B2 (ja) | 1993-03-18 | 2001-12-25 | 株式会社東芝 | 誤り訂正復号装置 |
| JP3280470B2 (ja) | 1993-06-08 | 2002-05-13 | 富士通テン株式会社 | 誤り訂正回路 |
| US5473620A (en) * | 1993-09-21 | 1995-12-05 | Cirrus Logic, Inc. | Programmable redundancy/syndrome generator |
| EP0684712B1 (en) * | 1994-05-17 | 2005-05-04 | Nippon Telegraph And Telephone Corporation | Line terminating equipment in SDH networks, using forward error correcting codes |
| JPH08167857A (ja) | 1994-12-15 | 1996-06-25 | Mitsubishi Electric Corp | 復号方式 |
| US5563892A (en) * | 1995-03-16 | 1996-10-08 | Bell Atlantic Network Services, Inc. | Method of upgrading the program transport capacity of an RF broadcast channel |
| JP3234130B2 (ja) * | 1995-05-30 | 2001-12-04 | 三菱電機株式会社 | 誤り訂正符号復号化方法およびこの方法を用いる回路 |
| JP2773701B2 (ja) | 1995-09-25 | 1998-07-09 | 日本電気株式会社 | 誤り訂正復号装置 |
| DE19536289C2 (de) | 1995-09-29 | 1999-01-07 | Krupp Werner & Pfleiderer Gmbh | Verfahren zur Durchführung von kontinuierlichen Aufbereitungsprozessen mit gleichsinnig drehenden, dicht kämmenden Doppelschneckenextrudern |
| JP3178346B2 (ja) * | 1996-06-27 | 2001-06-18 | 松下電器産業株式会社 | リードソロモン誤り訂正回路 |
| EP0911983A4 (en) * | 1996-06-27 | 2000-09-27 | Matsushita Electric Industrial Co Ltd | CIRCUIT FOR THE REED-SOLOMON ERROR CORRECTION AND METHOD AND DEVICE FOR THE MUTUAL EUCLIDIC DIVISION. |
| JP3304770B2 (ja) * | 1996-07-11 | 2002-07-22 | 松下電器産業株式会社 | ユークリッド互除方法および装置 |
| JP2907138B2 (ja) * | 1996-08-15 | 1999-06-21 | 日本電気株式会社 | 誤り訂正の演算処理方法及び処理回路 |
| GB2318954B (en) * | 1996-10-29 | 2001-05-23 | Daewoo Electronics Co Ltd | Reed-solomon decoder for use in advanced television |
| US5999959A (en) * | 1998-02-18 | 1999-12-07 | Quantum Corporation | Galois field multiplier |
-
1997
- 1997-12-26 JP JP9368781A patent/JPH11196006A/ja active Pending
-
1998
- 1998-12-23 FR FR9816315A patent/FR2773284B1/fr not_active Expired - Fee Related
- 1998-12-23 US US09/219,324 patent/US6341297B1/en not_active Expired - Lifetime
-
2001
- 2001-12-12 US US10/012,511 patent/US6880121B2/en not_active Expired - Lifetime
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104917535A (zh) * | 2014-03-14 | 2015-09-16 | 三星电子株式会社 | 用于分组码的高阶伴随式计算器和计算高阶伴随式的方法 |
| CN104917535B (zh) * | 2014-03-14 | 2019-10-25 | 三星电子株式会社 | 用于分组码的高阶伴随式计算器和计算高阶伴随式的方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| FR2773284B1 (fr) | 2001-01-26 |
| US6880121B2 (en) | 2005-04-12 |
| US6341297B1 (en) | 2002-01-22 |
| FR2773284A1 (fr) | 1999-07-02 |
| US20020042804A1 (en) | 2002-04-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5170399A (en) | Reed-Solomon Euclid algorithm decoder having a process configurable Euclid stack | |
| US5805617A (en) | Apparatus for computing error correction syndromes | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| JP2687941B2 (ja) | リード−ソロモン・デコーダ | |
| EP0720759B1 (en) | Programmable redundancy/syndrome generator | |
| US6341297B1 (en) | Parallel processing syndrome calculating circuit and Reed-Solomon decoding circuit | |
| KR100258951B1 (ko) | 리드-솔로몬(rs) 복호기와 그 복호방법 | |
| US6219816B1 (en) | Device and method for carrying out Reed-Solomon encoding | |
| EP0991196B1 (en) | Method of correcting lost data and circuit thereof | |
| EP1175015B1 (en) | Decoding circuit and decoding method thereof | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| US20010023497A1 (en) | Parallel processing reed-solomon encoding circuit and method | |
| JPH07226687A (ja) | 誤り訂正処理装置 | |
| JPH0750595A (ja) | 復号化装置 | |
| JP2591611B2 (ja) | ｔ重誤り訂正符号の符号化復号化回路 | |
| CN113068046B (zh) | Mpeg-2同步字节解码器中伴随式的并行产生装置和方法 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| TWI523437B (zh) | Ｂｃｈ碼編碼與癥狀計算共用設計電路及決定該共用設計電路的方法 | |
| Lee | An ultra high-speed Reed-Solomon decoder | |
| Lee et al. | An efficient recursive cell architecture of modified Euclid's algorithm for decoding Reed-Solomon codes | |
| Hsu et al. | An area-efficient VLSI architecture for decoding of Reed-Solomon codes | |
| JPH0764810A (ja) | ガロア体演算器 | |
| JP2603243B2 (ja) | 誤り訂正装置 | |
| JP2797570B2 (ja) | ユークリッドの互除回路 | |
| US20060041824A1 (en) | Method and apparatus for computing parity characters for a codeword of a cyclic code |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20010925 |