JPH0345019A - シンドローム算出回路 - Google Patents
シンドローム算出回路Info
- Publication number
- JPH0345019A JPH0345019A JP1181160A JP18116089A JPH0345019A JP H0345019 A JPH0345019 A JP H0345019A JP 1181160 A JP1181160 A JP 1181160A JP 18116089 A JP18116089 A JP 18116089A JP H0345019 A JPH0345019 A JP H0345019A
- Authority
- JP
- Japan
- Prior art keywords
- syndrome
- circuit
- calculation
- code
- data
- 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
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)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
［産業上の利用分野］
本発明はシンドローム算出回路に関し、より具体的には
検査マトリクスを用いて符号誤りを検出訂正する回路に
おけるシンドローム算出回路に関する。
検査マトリクスを用いて符号誤りを検出訂正する回路に
おけるシンドローム算出回路に関する。
［従来の技術］
第２図は、ディジタル信号の符号誤り検出回路のシンド
ローム計算部の従来例の構成ブロック図を示す。入力端
子１０には伝送路を介して符号が入力し、各符号語毎に
メモリ１２に書き込まれる。
ローム計算部の従来例の構成ブロック図を示す。入力端
子１０には伝送路を介して符号が入力し、各符号語毎に
メモリ１２に書き込まれる。
メモリ１２に書き込まれた符号語は順次読み出され、乗
算器１４，１６．１８に順次印加される。
算器１４，１６．１８に順次印加される。
メモリ１２の読出しと同時に、ＲＯＭ２０．２２２４か
らシンドロームＳ。−８，の検査マトリクスの係数が読
み出され、それぞれ乗算器１４，１６゜１８に印加され
る。
らシンドロームＳ。−８，の検査マトリクスの係数が読
み出され、それぞれ乗算器１４，１６゜１８に印加され
る。
乗算器１４，１６．１８はメモリ１２からのデータにＲ
ＯＭ２０，２２．２４からの係数を乗算する。乗算器１
４，１６．１８の出力は、加算器２６．２’８．３０に
印加され、各符号語単位で累積加算される。即ち、加算
器２６，２８．３０の出力は遅延回路３２，３４．３６
により加算器２６．２８．３０の加算入力に帰還されて
おり、加算器２６，２８．３０は乗算器１４，１６．１
８の出力を逐次加算して行く。加算器２６．２８３０及
び遅延回路３２，３４．３６からなる回路により各符号
語の全ての符号を累積することにより、符号誤り検出の
ためのシンドローム３０〜Ｓ−を得ることができ、それ
らはシンドローム・メモリ３８に記憶される。
ＯＭ２０，２２．２４からの係数を乗算する。乗算器１
４，１６．１８の出力は、加算器２６．２’８．３０に
印加され、各符号語単位で累積加算される。即ち、加算
器２６，２８．３０の出力は遅延回路３２，３４．３６
により加算器２６．２８．３０の加算入力に帰還されて
おり、加算器２６，２８．３０は乗算器１４，１６．１
８の出力を逐次加算して行く。加算器２６．２８３０及
び遅延回路３２，３４．３６からなる回路により各符号
語の全ての符号を累積することにより、符号誤り検出の
ためのシンドローム３０〜Ｓ−を得ることができ、それ
らはシンドローム・メモリ３８に記憶される。
［発明が解決しようとする課題］
しかし、上記従来例では、符号誤り検出のためのシンド
ロームを得るために、符号長全てに対応した検査マトリ
クスの係数との乗算、及び乗算結果の累積加算処理が必
要であり、非常に長い演算時間がかかるという欠点があ
る。
ロームを得るために、符号長全てに対応した検査マトリ
クスの係数との乗算、及び乗算結果の累積加算処理が必
要であり、非常に長い演算時間がかかるという欠点があ
る。
そこで本発明は、より高速に符号誤り検出用のシンドロ
ームを算出できるシンドローム算出回路を提示すること
を目的とする。
ームを算出できるシンドローム算出回路を提示すること
を目的とする。
［課題を解決するための手段］
本発明に係るシンドローム算出回路は、入力された符号
語を複数のデータ・グループに分割する分割手段と、当
該分割手段で分割された各データ・グループに対し、符
号誤りを検出するための検査マトリクスによるマトリク
ス演算を行なう複数の演算手段と、当該複数の演算手段
の演算結果を加算する加算手段とからなることを特徴と
する。
語を複数のデータ・グループに分割する分割手段と、当
該分割手段で分割された各データ・グループに対し、符
号誤りを検出するための検査マトリクスによるマトリク
ス演算を行なう複数の演算手段と、当該複数の演算手段
の演算結果を加算する加算手段とからなることを特徴と
する。
［作用］
上記６複数の演算手段が、分割された各データ・グルー
プに対して同時に所定のマトリクス演算を行なう。従っ
て、複数の演算手段による同時処理骨だけシンドローム
を高速に算出できる。
プに対して同時に所定のマトリクス演算を行なう。従っ
て、複数の演算手段による同時処理骨だけシンドローム
を高速に算出できる。
［実施例］
以下、図面を参照して本発明の詳細な説明する。なお、
以下では、リード・ソロモン符号を用いて符号誤りを検
出する場合を例に説明する。
以下では、リード・ソロモン符号を用いて符号誤りを検
出する場合を例に説明する。
シンボル数がｎで各シンボルをｐビットとしてＷ＝［χ
１．χ２．χ１．・・・、χ、、］と表わされる符号語
Ｗがリード・ソロモン符号を構成し、その検査マトリク
スＨがガロア・フィールドＧＦ（２’）の原始元αによ
り例えば式（１）で表わされるとする。
１．χ２．χ１．・・・、χ、、］と表わされる符号語
Ｗがリード・ソロモン符号を構成し、その検査マトリク
スＨがガロア・フィールドＧＦ（２’）の原始元αによ
り例えば式（１）で表わされるとする。
Ｈ＝
アイ
ジタル信号の符号誤りは、
次式によって求
めることができる。
Ｈ−ＷＴ＝
上記の符号誤り算出式を例えば、
次式のように２
つに分離する。
即ち
Ｈ−Ｗ”＝Ｈ，・ｗ、’＋Ｔ（、・Ｗｌ（３）
Ｈｌ・Ｗ１７＝
Ｈ２・Ｊ”−
よって、
［Ｓ、］＝［Ｓ□コ＋［Ｓ、、ｂ］
となる。
（６）
第１図は、本発明の一実施例の構成ブロック図を示して
おり、具体的には、式（４）、 （５）を使ってシンド
ロームＳｏ””ＳＩｌ中の１つのシンドロームＳ、を算
出する回路構成ブロック図である。４０は受信データの
入力端子、４２はデータ・メモリ、４４゜４６は受信デ
ータを二層変換する二層変換回路、４８．５０は乗算器
、５２．５４は検査マトリクス用の係数を出力する係数
ＲＯＭである。５６５８は加算器、６０．６２は遅延回
路であり、回路５６，５８：６０，６２により、乗算器
４８５０の出力を累積加算する回・路を構成する。６４
は加算器、６６はシンドローム・メモリである。
おり、具体的には、式（４）、 （５）を使ってシンド
ロームＳｏ””ＳＩｌ中の１つのシンドロームＳ、を算
出する回路構成ブロック図である。４０は受信データの
入力端子、４２はデータ・メモリ、４４゜４６は受信デ
ータを二層変換する二層変換回路、４８．５０は乗算器
、５２．５４は検査マトリクス用の係数を出力する係数
ＲＯＭである。５６５８は加算器、６０．６２は遅延回
路であり、回路５６，５８：６０，６２により、乗算器
４８５０の出力を累積加算する回・路を構成する。６４
は加算器、６６はシンドローム・メモリである。
受信された符号語Ｗ＝［χ１．χ２．χ３．・・・、χ
。］が入力端子４０に入力し、データ・メモリ４２に書
き込まれる。データ・メモリ４２に書き込まれたデータ
は読み出され、二層変換回路４４．４６により二層に分
割される。即ち二層変換回路４４は符号語Ｗのうちの、
データＷ、＝［χ１．χ４．・・・χ、−１］を出力し
、二層変換回路４６はデータＷ２＝［χ１．χ４．・・
・、χ７］を出力する。このように分割された最初のシ
ンボルχ１．χ２がそれぞれ乗算器４８．５０に印加さ
れ、同時に、係数ＲＯＭ５２．５４からそのシンボルに
対応する検査マトリクスの係数α５（ａ−１）、α′″
（ａ−２１が読み出され、乗算器４８．５０に供給され
る。乗算器４８はシンボルχ、に係数α５（ｓ−１１を
乗算し、乗算器５０はシンボルχ２に係数α”Ｃ″−′
）を乗算する。乗算器４８．５０は同様に、次のシンボ
ルχ３．χ４に係数αｗｒ（ｎ−１１，α′″（ａ−４
１を乗算し、以下同様に、順次、係数の乗算を実行する
。乗算器４８．５０の乗算結果は、加算器５６．５８及
び遅延回路６０゜６２により累積加算される。受信され
た符号ＨＷの全てについて累積加算した状態では、遅延
回路６０の出力は式（４）の［Ｓ、、］であり、遅延回
路６２の出力は式（５）の［Ｓ、ｂ］である。従って、
加算器６４の出力は［Ｓ、］であり、これがシンドロー
ム・メモリ６６に格納される。
。］が入力端子４０に入力し、データ・メモリ４２に書
き込まれる。データ・メモリ４２に書き込まれたデータ
は読み出され、二層変換回路４４．４６により二層に分
割される。即ち二層変換回路４４は符号語Ｗのうちの、
データＷ、＝［χ１．χ４．・・・χ、−１］を出力し
、二層変換回路４６はデータＷ２＝［χ１．χ４．・・
・、χ７］を出力する。このように分割された最初のシ
ンボルχ１．χ２がそれぞれ乗算器４８．５０に印加さ
れ、同時に、係数ＲＯＭ５２．５４からそのシンボルに
対応する検査マトリクスの係数α５（ａ−１）、α′″
（ａ−２１が読み出され、乗算器４８．５０に供給され
る。乗算器４８はシンボルχ、に係数α５（ｓ−１１を
乗算し、乗算器５０はシンボルχ２に係数α”Ｃ″−′
）を乗算する。乗算器４８．５０は同様に、次のシンボ
ルχ３．χ４に係数αｗｒ（ｎ−１１，α′″（ａ−４
１を乗算し、以下同様に、順次、係数の乗算を実行する
。乗算器４８．５０の乗算結果は、加算器５６．５８及
び遅延回路６０゜６２により累積加算される。受信され
た符号ＨＷの全てについて累積加算した状態では、遅延
回路６０の出力は式（４）の［Ｓ、、］であり、遅延回
路６２の出力は式（５）の［Ｓ、ｂ］である。従って、
加算器６４の出力は［Ｓ、］であり、これがシンドロー
ム・メモリ６６に格納される。
第１図では、シンドロームを算出する検査マトリクスを
２つに分離したが、更に分割してもよいそうすれば、よ
り高速に算出できる。また、本発明はリード・ソロモン
符号による場合に限定されない。
２つに分離したが、更に分割してもよいそうすれば、よ
り高速に算出できる。また、本発明はリード・ソロモン
符号による場合に限定されない。
［発明の効果］
以上の説明から容易に理解できるように、本発明によれ
ば、符号誤り検出のためのシンドロームを高速に算出で
き、従って符号誤り検出を高速化できる。
ば、符号誤り検出のためのシンドロームを高速に算出で
き、従って符号誤り検出を高速化できる。
第１図は本発明の一実施例の構成ブロック図、第２図は
従来例の構成ブロック図である。 ４０：入力端子 ４２：データ・メモリ ４４゜４６：
二層分割回路 ４Ｂ、５０：乗算器 ５２゜５４：係数
ＲＯＭ ５６．５８：加算器 ６０゜６２＝遅延回路
６４：加算器 ６６：シンドローム・メモリ
従来例の構成ブロック図である。 ４０：入力端子 ４２：データ・メモリ ４４゜４６：
二層分割回路 ４Ｂ、５０：乗算器 ５２゜５４：係数
ＲＯＭ ５６．５８：加算器 ６０゜６２＝遅延回路
６４：加算器 ６６：シンドローム・メモリ
Claims (1)
- 入力された符号語を複数のデータ・グループに分割する
分割手段と、当該分割手段で分割された各データ・グル
ープに対し、符号誤りを検出するための検査マトリクス
によるマトリクス演算を行なう複数の演算手段と、当該
複数の演算手段の演算結果を加算する加算手段とからな
ることを特徴とするシンドローム算出回路。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1181160A JPH0345019A (ja) | 1989-07-13 | 1989-07-13 | シンドローム算出回路 |
| US07/550,439 US5200961A (en) | 1989-07-13 | 1990-07-10 | Error detection and/or correction device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1181160A JPH0345019A (ja) | 1989-07-13 | 1989-07-13 | シンドローム算出回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0345019A true JPH0345019A (ja) | 1991-02-26 |
Family
ID=16095936
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1181160A Pending JPH0345019A (ja) | 1989-07-13 | 1989-07-13 | シンドローム算出回路 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5200961A (ja) |
| JP (1) | JPH0345019A (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0571096B1 (en) * | 1992-05-18 | 1999-06-23 | Canon Kabushiki Kaisha | Data processing apparatus |
| US5459742A (en) * | 1992-06-11 | 1995-10-17 | Quantum Corporation | Solid state disk memory using storage devices with defects |
| US5822339A (en) * | 1996-05-30 | 1998-10-13 | Rockwell International | Data decoder and method to correct inversions or phase ambiguity for M-ary transmitted data |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4397022A (en) * | 1981-01-30 | 1983-08-02 | Weng Ming I | Weighted erasure codec for the (24, 12) extended Golay code |
| US4382300A (en) * | 1981-03-18 | 1983-05-03 | Bell Telephone Laboratories Incorporated | Method and apparatus for decoding cyclic codes via syndrome chains |
| JPS6057574A (ja) * | 1983-09-08 | 1985-04-03 | Sony Corp | 信号処理装置 |
| US4706250A (en) * | 1985-09-27 | 1987-11-10 | International Business Machines Corporation | Method and apparatus for correcting multibyte errors having improved two-level code structure |
| US4736376A (en) * | 1985-10-25 | 1988-04-05 | Sequoia Systems, Inc. | Self-checking error correcting encoder/decoder |
| US4958349A (en) * | 1988-11-01 | 1990-09-18 | Ford Aerospace Corporation | High data rate BCH decoder |
-
1989
- 1989-07-13 JP JP1181160A patent/JPH0345019A/ja active Pending
-
1990
- 1990-07-10 US US07/550,439 patent/US5200961A/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| US5200961A (en) | 1993-04-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0567148A2 (en) | Operating circuit for galois field | |
| US5699368A (en) | Error-correcting encoder, error-correcting decoder, and data transmitting system with error-correcting codes | |
| US5912905A (en) | Error-correcting encoder, error-correcting decoder and data transmitting system with error-correcting codes | |
| EP0793351A1 (en) | Apparatus for computing error correction syndromes | |
| JPS645334B2 (ja) | ||
| JPH0728227B2 (ja) | Ｂｃｈ符号の復号装置 | |
| US3771126A (en) | Error correction for self-synchronized scramblers | |
| EP0169908B1 (en) | Method and circuit for decoding error coded data | |
| JP2001127645A (ja) | 誤り訂正方法および誤り訂正装置 | |
| JPH0345019A (ja) | シンドローム算出回路 | |
| KR100336234B1 (ko) | 데이터 오류 정정 장치 | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| EP0341851A2 (en) | Method and apparatus for interleaved encoding | |
| JP2662472B2 (ja) | 誤り訂正処理用シンドローム演算回路 | |
| JP3351413B2 (ja) | 並列処理リードソロモン符号化回路及びそれに用いる並列処理リードソロモン符号化方法 | |
| EP1037148B1 (en) | Error coding method | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JP3105908B2 (ja) | 有限体上の乗算器 | |
| JPH09246999A (ja) | エラー訂正向け多項式評価装置 | |
| KR970005125B1 (ko) | 리드-솔로만 부호기 | |
| JP2603243B2 (ja) | 誤り訂正装置 | |
| SU1481902A1 (ru) | Устройство дл определени многочлена локаторов стираний при декодировании недвоичных блоковых кодов | |
| JPH0764810A (ja) | ガロア体演算器 | |
| KR920007506B1 (ko) | 오류정정용 갈로이스 원소간의 곱셈 나눗셈회로 및 그 제작방법 | |
| JPH0434785B2 (ja) |