JPH05227041A - Ｃｒｃ演算に基づく１ビット誤り訂正回路 - Google Patents
Ｃｒｃ演算に基づく１ビット誤り訂正回路Info
- Publication number
- JPH05227041A JPH05227041A JP4058768A JP5876892A JPH05227041A JP H05227041 A JPH05227041 A JP H05227041A JP 4058768 A JP4058768 A JP 4058768A JP 5876892 A JP5876892 A JP 5876892A JP H05227041 A JPH05227041 A JP H05227041A
- Authority
- JP
- Japan
- Prior art keywords
- data
- remainder
- bit error
- register
- exclusive
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 208000011580 syndromic disease Diseases 0.000 claims abstract description 59
- 238000001514 detection method Methods 0.000 claims description 12
- 238000010586 diagram Methods 0.000 description 10
- 125000004122 cyclic group Chemical group 0.000 description 6
- 230000003111 delayed effect Effects 0.000 description 2
- 239000011159 matrix material Substances 0.000 description 2
- 238000004891 communication Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000000034 method Methods 0.000 description 1
- 230000001360 synchronised effect Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
-
- 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/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
Landscapes
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】
【目的】本発明は小規模化、かつ低コスト化を図ること
ができるＣＲＣ演算に基づく１ビット誤り訂正回路を提
供することを目的とする。 【構成】ｎ個のｍビットシリアルデータが各々変換され
たｍビットのパラレルデータのシンドロームを求めるシ
ンドローム生成手段と、シンドロームを剰余１演算手段
に巡回し、この巡回により得られる剰余データをデコー
ドして１ビット誤りデータを検出する１ビット誤り検出
手段と、シンドローム生成手段の第１〜第ｎレジスタの
所定レジスタの出力データを剰余１演算手段を介して得
られる剰余データと、所定レジスタに供給されるデータ
との排他的論理和を取って主信号であるパラレルデータ
を得る主信号再生手段と、主信号再生手段により得られ
たパラレルデータと、１ビット誤り検出手段により検出
された１ビット誤りデータとの排他的論理和を取って訂
正データを求める訂正手段とを具備して構成する。
ができるＣＲＣ演算に基づく１ビット誤り訂正回路を提
供することを目的とする。 【構成】ｎ個のｍビットシリアルデータが各々変換され
たｍビットのパラレルデータのシンドロームを求めるシ
ンドローム生成手段と、シンドロームを剰余１演算手段
に巡回し、この巡回により得られる剰余データをデコー
ドして１ビット誤りデータを検出する１ビット誤り検出
手段と、シンドローム生成手段の第１〜第ｎレジスタの
所定レジスタの出力データを剰余１演算手段を介して得
られる剰余データと、所定レジスタに供給されるデータ
との排他的論理和を取って主信号であるパラレルデータ
を得る主信号再生手段と、主信号再生手段により得られ
たパラレルデータと、１ビット誤り検出手段により検出
された１ビット誤りデータとの排他的論理和を取って訂
正データを求める訂正手段とを具備して構成する。
Description
【０００１】
【産業上の利用分野】本発明はＣＲＣ(Cyclic Redundan
cy Check) 演算に基づく１ビット誤り訂正回路に関す
る。
cy Check) 演算に基づく１ビット誤り訂正回路に関す
る。
【０００２】この１ビット誤り訂正回路は、デジタル多
重通信を行う装置等に適用されるものであり、例えばマ
ルチフレーム化されたデータを装置間で授受する際に監
視制御データとして巡回符号を付し、符号誤り検出及び
訂正を行う場合に適用される。
重通信を行う装置等に適用されるものであり、例えばマ
ルチフレーム化されたデータを装置間で授受する際に監
視制御データとして巡回符号を付し、符号誤り検出及び
訂正を行う場合に適用される。
【０００３】１ビット誤り訂正回路は、扱うデータビッ
ト数によっては回路規模が大きくなるが、これは近年の
装置小型化の要求にそぐわないものである。そこで回路
規模の小型化が図れる１ビット誤り訂正回路が要望され
ている。
ト数によっては回路規模が大きくなるが、これは近年の
装置小型化の要求にそぐわないものである。そこで回路
規模の小型化が図れる１ビット誤り訂正回路が要望され
ている。
【０００４】
【従来の技術】図４は従来のＣＲＣ演算に基づく１ビッ
ト誤り訂正回路のブロック構成図である。
ト誤り訂正回路のブロック構成図である。
【０００５】この１ビット誤り訂正回路は、打ち消し型
シンドローム（剰余）生成方法を用いたものであり、一
点鎖線枠内１１が８パラ展開の打ち消し型シンドローム
生成部となっている。
シンドローム（剰余）生成方法を用いたものであり、一
点鎖線枠内１１が８パラ展開の打ち消し型シンドローム
生成部となっている。
【０００６】この１ビット誤り訂正回路の入力データは
図５に示す３２ビットの情報部分Ｈ１〜Ｈ４と８ビット
の検査部分Ｈ５とから成る巡回符号Ｈであり、ここでは
Ｈ１〜Ｈ５の４０ビットを１フレームとして扱う。
図５に示す３２ビットの情報部分Ｈ１〜Ｈ４と８ビット
の検査部分Ｈ５とから成る巡回符号Ｈであり、ここでは
Ｈ１〜Ｈ５の４０ビットを１フレームとして扱う。
【０００７】巡回符号Ｈが図４に示す１ビット誤り訂正
回路に入力データとして入力される際は、それぞれが８
ビットパラレルにＨ１からＨ５まで順に入力される。８
パラ展開の打ち消し型シンドローム生成部１１におい
て、１２，２１は排他的論理和回路（ＥＯＲ）、１３は
シフトレジスタ（ＳＲ）、１４は第１剰余演算回路、１
５〜１９はシフトレジスタ、２０は第２剰余演算回路で
ある。
回路に入力データとして入力される際は、それぞれが８
ビットパラレルにＨ１からＨ５まで順に入力される。８
パラ展開の打ち消し型シンドローム生成部１１におい
て、１２，２１は排他的論理和回路（ＥＯＲ）、１３は
シフトレジスタ（ＳＲ）、１４は第１剰余演算回路、１
５〜１９はシフトレジスタ、２０は第２剰余演算回路で
ある。
【０００８】排他的論理和回路１２は、８ビットの入力
パラレルデータと８ビットの他の入力パラレルデータと
の排他的論理和を取って、８ビットのパラレルデータと
して出力するものであり、ここでは入力データとしてＨ
１からＨ５まで順に入力される巡回符号Ｈと、第１剰余
演算回路１４の８ビットの出力データとの排他的論理和
を取ってシフトレジスタ１３へ出力する。
パラレルデータと８ビットの他の入力パラレルデータと
の排他的論理和を取って、８ビットのパラレルデータと
して出力するものであり、ここでは入力データとしてＨ
１からＨ５まで順に入力される巡回符号Ｈと、第１剰余
演算回路１４の８ビットの出力データとの排他的論理和
を取ってシフトレジスタ１３へ出力する。
【０００９】シフトレジスタ１３は８つの１ビットフリ
ップフロップをパラレルに接続して構成したものであ
り、入力される８ビットのデータを記憶し、記憶された
８ビットのデータを出力する。
ップフロップをパラレルに接続して構成したものであ
り、入力される８ビットのデータを記憶し、記憶された
８ビットのデータを出力する。
【００１０】第１剰余演算回路１４は入力される８ビッ
トのデータを、関数ｆ(X) に基づいて剰余演算を行うも
のである。図６に示す時刻ｔ0 においてシフトレジスタ
１３から出力された初期値Ｃが、第１剰余演算回路１４
に入力されたとすると、剰余演算回路１４からは剰余ｆ
(C) が出力される。一方、初期値Ｃはシフトレジスタ１
５へも出力されて記憶される。
トのデータを、関数ｆ(X) に基づいて剰余演算を行うも
のである。図６に示す時刻ｔ0 においてシフトレジスタ
１３から出力された初期値Ｃが、第１剰余演算回路１４
に入力されたとすると、剰余演算回路１４からは剰余ｆ
(C) が出力される。一方、初期値Ｃはシフトレジスタ１
５へも出力されて記憶される。
【００１１】この時、入力データとして供給されたＨ１
とｆ(C) との排他的論理和が取られてシフトレジスタ１
３の入力側に供給されている。時刻ｔ1 において図示せ
ぬクロック信号が供給されると、H1Exｆ(C) （図６に示
すシフトレジスタ１３出力欄には、○内に＋を挿入した
符号を排他的論理和符号として記述しているが、本文に
おいてはExを排他的論理和符号とする）がシフトレジス
タ１３に記憶されて剰余演算回路１４及びシフトレジス
タ１５へ出力される。この時、シフトレジスタ１５には
Ｃが記憶される。
とｆ(C) との排他的論理和が取られてシフトレジスタ１
３の入力側に供給されている。時刻ｔ1 において図示せ
ぬクロック信号が供給されると、H1Exｆ(C) （図６に示
すシフトレジスタ１３出力欄には、○内に＋を挿入した
符号を排他的論理和符号として記述しているが、本文に
おいてはExを排他的論理和符号とする）がシフトレジス
タ１３に記憶されて剰余演算回路１４及びシフトレジス
タ１５へ出力される。この時、シフトレジスタ１５には
Ｃが記憶される。
【００１２】また、H1Exｆ(C) が入力された剰余演算回
路１４からはｆ〔H1Exｆ(C) 〕＝ｆ(H1)Exｆ2(C)が出力
され、このｆ(H1)Exｆ2(C)と、Ｈ１の次に供給されたＨ
２との排他的論理和が取られてシフトレジスタ１３の入
力側に供給される。
路１４からはｆ〔H1Exｆ(C) 〕＝ｆ(H1)Exｆ2(C)が出力
され、このｆ(H1)Exｆ2(C)と、Ｈ１の次に供給されたＨ
２との排他的論理和が取られてシフトレジスタ１３の入
力側に供給される。
【００１３】時刻ｔ2 においてクロック信号が供給され
ると、H2Exｆ(H1)Exｆ2(C)がシフトレジスタ１３に記憶
され、H2Exｆ(H1)Exｆ2(C)が剰余演算回路１４及びシフ
トレジスタ１５へ出力される。
ると、H2Exｆ(H1)Exｆ2(C)がシフトレジスタ１３に記憶
され、H2Exｆ(H1)Exｆ2(C)が剰余演算回路１４及びシフ
トレジスタ１５へ出力される。
【００１４】この時、シフトレジスタ１５にはH1Exｆ
(C) が記憶され、シフトレジスタ１５に記憶されていた
Ｃはシフトレジスタ１６に記憶される。また、H2Exｆ(H
1)Exｆ2(C)が入力された剰余演算回路１４からはｆ(H2)
Exｆ2(H1)Ex ｆ3(C)が出力され、このｆ(H2)Exｆ2(H1)E
x ｆ3(C)と、Ｈ３との排他的論理和が取られてシフトレ
ジスタ１３の入力側に供給される。
(C) が記憶され、シフトレジスタ１５に記憶されていた
Ｃはシフトレジスタ１６に記憶される。また、H2Exｆ(H
1)Exｆ2(C)が入力された剰余演算回路１４からはｆ(H2)
Exｆ2(H1)Ex ｆ3(C)が出力され、このｆ(H2)Exｆ2(H1)E
x ｆ3(C)と、Ｈ３との排他的論理和が取られてシフトレ
ジスタ１３の入力側に供給される。
【００１５】時刻ｔ3 においてクロック信号が供給され
ると、H3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)がシフトレジスタ
１３に記憶されて剰余演算回路１４及びシフトレジスタ
１５へ出力される。
ると、H3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)がシフトレジスタ
１３に記憶されて剰余演算回路１４及びシフトレジスタ
１５へ出力される。
【００１６】この時、シフトレジスタ１５にはH2Exｆ(H
1)Exｆ2(C)が記憶され、シフトレジスタ１６にはH1Exｆ
(C) が記憶され、シフトレジスタ１７にはＣが記憶され
る。また、H3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が入力された
剰余演算回路１４からはｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex
ｆ4(C)が出力され、このｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex
ｆ4(C)と、Ｈ４との排他的論理和が取られてシフトレジ
スタ１３の入力側に供給される。
1)Exｆ2(C)が記憶され、シフトレジスタ１６にはH1Exｆ
(C) が記憶され、シフトレジスタ１７にはＣが記憶され
る。また、H3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が入力された
剰余演算回路１４からはｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex
ｆ4(C)が出力され、このｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex
ｆ4(C)と、Ｈ４との排他的論理和が取られてシフトレジ
スタ１３の入力側に供給される。
【００１７】時刻ｔ4 においてクロック信号が供給され
ると、H4Exｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)がシフ
トレジスタ１３に記憶されて剰余演算回路１４及びシフ
トレジスタ１５へ出力される。
ると、H4Exｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)がシフ
トレジスタ１３に記憶されて剰余演算回路１４及びシフ
トレジスタ１５へ出力される。
【００１８】この時、シフトレジスタ１５にはH3Exｆ(H
2)Exｆ2(H1)Ex ｆ3(C)が記憶され、シフトレジスタ１６
にはH2Exｆ(H1)Exｆ2(C)が、シフトレジスタ１７にはH1
Exｆ(C) が、シフトレジスタ１８にはＣが記憶される。
2)Exｆ2(H1)Ex ｆ3(C)が記憶され、シフトレジスタ１６
にはH2Exｆ(H1)Exｆ2(C)が、シフトレジスタ１７にはH1
Exｆ(C) が、シフトレジスタ１８にはＣが記憶される。
【００１９】また、H4Exｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex
ｆ4(C)が入力された剰余演算回路１４からはｆ(H4)Exｆ
2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)が出力され、この
ｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)と、Ｈ
５との排他的論理和が取られてシフトレジスタ１３の入
力側に供給される。
ｆ4(C)が入力された剰余演算回路１４からはｆ(H4)Exｆ
2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)が出力され、この
ｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)と、Ｈ
５との排他的論理和が取られてシフトレジスタ１３の入
力側に供給される。
【００２０】時刻ｔ5 においてクロック信号が供給され
ると、H5Exｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ
5(C)がシフトレジスタ１３に記憶されて剰余演算回路１
４及びシフトレジスタ１５へ出力される。
ると、H5Exｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ
5(C)がシフトレジスタ１３に記憶されて剰余演算回路１
４及びシフトレジスタ１５へ出力される。
【００２１】この時、シフトレジスタ１５にはH4Exｆ(H
3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)が記憶され、シフトレ
ジスタ１６にはH3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が、シフ
トレジスタ１７にはH2Exｆ(H1)Exｆ2(C)が、シフトレジ
スタ１８にはH1Exｆ(C) が、シフトレジスタ１９にはＣ
が記憶される。
3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)が記憶され、シフトレ
ジスタ１６にはH3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が、シフ
トレジスタ１７にはH2Exｆ(H1)Exｆ2(C)が、シフトレジ
スタ１８にはH1Exｆ(C) が、シフトレジスタ１９にはＣ
が記憶される。
【００２２】つまり、時刻ｔ5 の時点で、シフトレジス
タ１９の入力側にH1Exｆ(C) が供給され、出力側からＣ
が出力される。第２剰余演算回路２０は入力される８ビ
ットのデータを、関数ｆ5 (X) に基づいて剰余演算を行
うものであり、時刻ｔ5 においてＣが入力されるとｆ5
(C) を排他的論理和回路２１へ出力する。
タ１９の入力側にH1Exｆ(C) が供給され、出力側からＣ
が出力される。第２剰余演算回路２０は入力される８ビ
ットのデータを、関数ｆ5 (X) に基づいて剰余演算を行
うものであり、時刻ｔ5 においてＣが入力されるとｆ5
(C) を排他的論理和回路２１へ出力する。
【００２３】この時、排他的論理和回路２１の他の入力
端にはシフトレジスタ１３から出力されたH5Exｆ(H4)Ex
ｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)が供給されてい
るので、排他的論理和回路２１によってｆ5 (C) とH5Ex
ｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)との排
他的論理和が取られる。この結果ｆ5 (C) が打ち消さ
れ、H5Exｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1) が、Ｈ
１〜Ｈ５全てのシンドローム（剰余）Ｓとして出力され
る。
端にはシフトレジスタ１３から出力されたH5Exｆ(H4)Ex
ｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)が供給されてい
るので、排他的論理和回路２１によってｆ5 (C) とH5Ex
ｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1)Ex ｆ5(C)との排
他的論理和が取られる。この結果ｆ5 (C) が打ち消さ
れ、H5Exｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ4(H1) が、Ｈ
１〜Ｈ５全てのシンドローム（剰余）Ｓとして出力され
る。
【００２４】このシンドロームＳは、余剰演算の際に用
いる関数ｆ(X) を行列α(X) とすると、図７に示す式
のように表される。ここで、例えばＨ１のビット０〜ビ
ット７の内の８ビット目（ビット７）が１ビット誤りを
起こしていた場合に、シンドロームＳを式の形式で表
すと、図７に示す式のようになる。
いる関数ｆ(X) を行列α(X) とすると、図７に示す式
のように表される。ここで、例えばＨ１のビット０〜ビ
ット７の内の８ビット目（ビット７）が１ビット誤りを
起こしていた場合に、シンドロームＳを式の形式で表
すと、図７に示す式のようになる。
【００２５】このとき式のα，α2 ，α3 ，α4 の行
列式において、全ての列が異なるパターンを持っている
ため、これらのパターンに対応した４０個のデコーダに
式で表されるシンドロームＳを通せば、Ｈ１〜Ｈ５の
どこのビットにおいて１ビット誤りが生じたのか判別で
きる。
列式において、全ての列が異なるパターンを持っている
ため、これらのパターンに対応した４０個のデコーダに
式で表されるシンドロームＳを通せば、Ｈ１〜Ｈ５の
どこのビットにおいて１ビット誤りが生じたのか判別で
きる。
【００２６】但し、１個のデコーダは８入力タイプのオ
アゲートを使用し、その８ビットの入力側に誤りパター
ンに応じてインバータを付けたタイプのものとなる。前
記した例のＨ１の８ビット目が１ビット誤りを起こして
いる場合は、オアゲートの８ビット目の入力端にインバ
ータを付加したデコーダで誤りが検出される。
アゲートを使用し、その８ビットの入力側に誤りパター
ンに応じてインバータを付けたタイプのものとなる。前
記した例のＨ１の８ビット目が１ビット誤りを起こして
いる場合は、オアゲートの８ビット目の入力端にインバ
ータを付加したデコーダで誤りが検出される。
【００２７】このような論理の下に、図４に示すデコー
ダ２２は構成されている。つまり、Ｈ１〜Ｈ５の全ての
誤りパターンに応じてインバータを付けた４０個の８入
力タイプオアゲートより構成されており、排他的論理和
回路２１の８本の出力ラインが各々のオアゲートの入力
端へ接続されている。また、デコーダ２２の出力ライン
本数は４０本となる。
ダ２２は構成されている。つまり、Ｈ１〜Ｈ５の全ての
誤りパターンに応じてインバータを付けた４０個の８入
力タイプオアゲートより構成されており、排他的論理和
回路２１の８本の出力ラインが各々のオアゲートの入力
端へ接続されている。また、デコーダ２２の出力ライン
本数は４０本となる。
【００２８】２３は誤り訂正部であり、アンド回路２４
〜２８と、シフトレジスタ２９〜３３と、排他的論理和
回路３４〜３８を具備して構成されている。各アンド回
路２４〜２８は、それぞれが２入力アンドゲートを８個
具備して構成されたものであり、８個のアンドゲートの
一方の入力端にはそれぞれデコーダ２２の出力ラインが
接続され、他方の入力端にはパルス信号Ｐ１の供給ライ
ンが接続されている。
〜２８と、シフトレジスタ２９〜３３と、排他的論理和
回路３４〜３８を具備して構成されている。各アンド回
路２４〜２８は、それぞれが２入力アンドゲートを８個
具備して構成されたものであり、８個のアンドゲートの
一方の入力端にはそれぞれデコーダ２２の出力ラインが
接続され、他方の入力端にはパルス信号Ｐ１の供給ライ
ンが接続されている。
【００２９】デコーダ２２の４０本の出力ラインは、Ｈ
１〜Ｈ５に応じて８本ずつ分類され、その内のＨ１に係
わる８本がアンド回路２８の入力側に接続され、Ｈ２に
係わる８本がアンド回路２７の入力側に、Ｈ３に係わる
８本がアンド回路２６の入力側に、Ｈ４に係わる８本が
アンド回路２５の入力側に、Ｈ５に係わる８本がアンド
回路２４の入力側に接続されている。
１〜Ｈ５に応じて８本ずつ分類され、その内のＨ１に係
わる８本がアンド回路２８の入力側に接続され、Ｈ２に
係わる８本がアンド回路２７の入力側に、Ｈ３に係わる
８本がアンド回路２６の入力側に、Ｈ４に係わる８本が
アンド回路２５の入力側に、Ｈ５に係わる８本がアンド
回路２４の入力側に接続されている。
【００３０】また、各アンド回路２４〜２８に供給され
るパルス（「Ｈ」レベル）Ｐ１は全て同期しており、上
述した時刻ｔ1 〜ｔ5 のタイミングで、時刻ｔ5 置き
（ｔ0，ｔ5 ，ｔ10，ｔ15，…）に供給されるものであ
る。但し、パルスＰ１は同時刻においてクロック信号よ
り半ビット遅れたタイミングで供給されるものとする。
るパルス（「Ｈ」レベル）Ｐ１は全て同期しており、上
述した時刻ｔ1 〜ｔ5 のタイミングで、時刻ｔ5 置き
（ｔ0，ｔ5 ，ｔ10，ｔ15，…）に供給されるものであ
る。但し、パルスＰ１は同時刻においてクロック信号よ
り半ビット遅れたタイミングで供給されるものとする。
【００３１】このような構成の誤り訂正部２３において
は、上述した時系列の時刻ｔ1 〜ｔ5 間に入力された主
信号Ｈ１〜Ｈ５が既に各シフトレジスタ２９〜３３に記
憶されている。シフトレジスタ３３にはＨ１が記憶さ
れ、シフトレジスタ３２にはＨ２が、シフトレジスタ３
１にはＨ３が、シフトレジスタ３０にはＨ４が、シフト
レジスタ２９にはＨ５が記憶されている。
は、上述した時系列の時刻ｔ1 〜ｔ5 間に入力された主
信号Ｈ１〜Ｈ５が既に各シフトレジスタ２９〜３３に記
憶されている。シフトレジスタ３３にはＨ１が記憶さ
れ、シフトレジスタ３２にはＨ２が、シフトレジスタ３
１にはＨ３が、シフトレジスタ３０にはＨ４が、シフト
レジスタ２９にはＨ５が記憶されている。
【００３２】従って、時刻ｔ5 において、パルスＰ１が
供給されることによって、アンド回路２８からシンドロ
ームＳに含まれるＨ１のシンドロームが出力され、この
Ｈ１のシンドロームとシフトレジスタ３３から出力され
るＨ１との排他的論理和が排他的論理和回路３８によっ
て取られて出力される。この時、上述したようにＨ１の
７ビット目に１ビットの誤りがあればその誤りが訂正さ
れて訂正データＨ１′として出力される。
供給されることによって、アンド回路２８からシンドロ
ームＳに含まれるＨ１のシンドロームが出力され、この
Ｈ１のシンドロームとシフトレジスタ３３から出力され
るＨ１との排他的論理和が排他的論理和回路３８によっ
て取られて出力される。この時、上述したようにＨ１の
７ビット目に１ビットの誤りがあればその誤りが訂正さ
れて訂正データＨ１′として出力される。
【００３３】また、アンド回路２７からはＨ２のシンド
ロームが出力され、このＨ２のシフトレジスタとシフト
レジスタ３２から出力されるＨ２との排他的論理和が排
他的論理和回路３７によって取られ、シフトレジスタ３
３に供給される。
ロームが出力され、このＨ２のシフトレジスタとシフト
レジスタ３２から出力されるＨ２との排他的論理和が排
他的論理和回路３７によって取られ、シフトレジスタ３
３に供給される。
【００３４】アンド回路２６からはＨ３のシンドローム
が出力され、このＨ３のシフトレジスタとシフトレジス
タ３１から出力されるＨ３との排他的論理和が排他的論
理和回路３６によって取られ、シフトレジスタ３２に供
給される。
が出力され、このＨ３のシフトレジスタとシフトレジス
タ３１から出力されるＨ３との排他的論理和が排他的論
理和回路３６によって取られ、シフトレジスタ３２に供
給される。
【００３５】アンド回路２５からはＨ４のシンドローム
が出力され、このＨ４のシフトレジスタとシフトレジス
タ３０から出力されるＨ４との排他的論理和が排他的論
理和回路３５によって取られ、シフトレジスタ３１に供
給される。
が出力され、このＨ４のシフトレジスタとシフトレジス
タ３０から出力されるＨ４との排他的論理和が排他的論
理和回路３５によって取られ、シフトレジスタ３１に供
給される。
【００３６】アンド回路２４からはＨ５のシンドローム
が出力され、このＨ５のシフトレジスタとシフトレジス
タ２９から出力されるＨ５との排他的論理和が排他的論
理和回路３４によって取られ、シフトレジスタ３０に供
給される。
が出力され、このＨ５のシフトレジスタとシフトレジス
タ２９から出力されるＨ５との排他的論理和が排他的論
理和回路３４によって取られ、シフトレジスタ３０に供
給される。
【００３７】このように排他的論理和の取られた各デー
タＨ２〜Ｈ５に例えば前記したＨ１のように誤りがあっ
たとすると、この時点で訂正されることになる。その
後、時刻ｔ6 において訂正データＨ２′が出力され、時
刻ｔ7 において訂正データＨ３′が出力され、時刻ｔ8
において訂正データＨ４′が出力され、時刻ｔ9 におい
て訂正データＨ５′が出力される。
タＨ２〜Ｈ５に例えば前記したＨ１のように誤りがあっ
たとすると、この時点で訂正されることになる。その
後、時刻ｔ6 において訂正データＨ２′が出力され、時
刻ｔ7 において訂正データＨ３′が出力され、時刻ｔ8
において訂正データＨ４′が出力され、時刻ｔ9 におい
て訂正データＨ５′が出力される。
【００３８】
【発明が解決しようとする課題】ところで、上述した図
４に示す１ビット誤り訂正回路においては、デコーダ２
２を８入力オアゲートを４０個用いて構成し、かつ、誤
り訂正部２３を、２入力アンドゲートを８個用いたアン
ド回路２４〜２８と、データＨ１〜Ｈ５遅延用のシフト
レジスタ２９〜３３と、排他的論理和回路３４〜３８と
を用いて構成しなければならないので回路全体が大規模
となり、コストも高くなるといった問題がある。
４に示す１ビット誤り訂正回路においては、デコーダ２
２を８入力オアゲートを４０個用いて構成し、かつ、誤
り訂正部２３を、２入力アンドゲートを８個用いたアン
ド回路２４〜２８と、データＨ１〜Ｈ５遅延用のシフト
レジスタ２９〜３３と、排他的論理和回路３４〜３８と
を用いて構成しなければならないので回路全体が大規模
となり、コストも高くなるといった問題がある。
【００３９】本発明は、このような点に鑑みてなされた
ものであり、小規模化、かつ低コスト化を図ることがで
きるＣＲＣ演算に基づく１ビット誤り訂正回路を提供す
ることを目的としている。
ものであり、小規模化、かつ低コスト化を図ることがで
きるＣＲＣ演算に基づく１ビット誤り訂正回路を提供す
ることを目的としている。
【００４０】
【課題を解決するための手段】図１に本発明のＣＲＣ演
算に基づく１ビット誤り訂正回路の原理図を示す。この
１ビット誤り訂正回路は、シンドローム生成手段１１
と、１ビット誤り検出手段４１と、主信号再生手段４２
と、訂正手段４３とを具備して構成されたものであり、
発明の特徴手段は、１ビット誤り検出手段４１、主信号
再生手段４２、及び訂正手段４３である。
算に基づく１ビット誤り訂正回路の原理図を示す。この
１ビット誤り訂正回路は、シンドローム生成手段１１
と、１ビット誤り検出手段４１と、主信号再生手段４２
と、訂正手段４３とを具備して構成されたものであり、
発明の特徴手段は、１ビット誤り検出手段４１、主信号
再生手段４２、及び訂正手段４３である。
【００４１】シンドローム生成手段１１は、入力される
パラレルデータＨ１〜Ｈ５、例えばＨ１を第１排他的論
理和手段及びレジスタを介して、関数ｆ(X) に基づいて
パラレルデータＨ１〜Ｈ５の剰余を求める剰余１演算手
段に入力し、剰余１演算手段から出力される剰余データ
と次に入力されるパラレルデータＨ２との排他的論理和
を該排他的論理和手段で取ってレジスタに供給するとい
った巡回を行い、この巡回によって求められる剰余デー
タをパラレルデータＨ１〜Ｈ５の個数ｎに応じて直列接
続された第１〜第ｎレジスタにより順次シフトさせて、
パラレルデータＨ１〜Ｈ５の個数ｎが乗数となる関数ｆ
n (X) に基づいてパラレルデータＨ１〜Ｈ５の剰余を求
める剰余２演算手段に入力し、剰余２演算手段から出力
される剰余データと第１排他的論理和手段の後段のレジ
スタから出力される剰余データとの排他的論理和を第２
排他的論理和手段で取ることによってシンドロームＳを
求めるものである。
パラレルデータＨ１〜Ｈ５、例えばＨ１を第１排他的論
理和手段及びレジスタを介して、関数ｆ(X) に基づいて
パラレルデータＨ１〜Ｈ５の剰余を求める剰余１演算手
段に入力し、剰余１演算手段から出力される剰余データ
と次に入力されるパラレルデータＨ２との排他的論理和
を該排他的論理和手段で取ってレジスタに供給するとい
った巡回を行い、この巡回によって求められる剰余デー
タをパラレルデータＨ１〜Ｈ５の個数ｎに応じて直列接
続された第１〜第ｎレジスタにより順次シフトさせて、
パラレルデータＨ１〜Ｈ５の個数ｎが乗数となる関数ｆ
n (X) に基づいてパラレルデータＨ１〜Ｈ５の剰余を求
める剰余２演算手段に入力し、剰余２演算手段から出力
される剰余データと第１排他的論理和手段の後段のレジ
スタから出力される剰余データとの排他的論理和を第２
排他的論理和手段で取ることによってシンドロームＳを
求めるものである。
【００４２】１ビット誤り検出手段４１は、シンドロー
ムＳを剰余１演算手段に巡回し、この巡回により得られ
る剰余データをデコードして１ビット誤りデータを検出
するものである。
ムＳを剰余１演算手段に巡回し、この巡回により得られ
る剰余データをデコードして１ビット誤りデータを検出
するものである。
【００４３】主信号再生手段４２は、シンドローム生成
手段１１の第１〜第ｎレジスタの所定レジスタの出力デ
ータを剰余１演算手段を介して得られる剰余データと、
所定レジスタに供給されるデータとの排他的論理和を取
って主信号であるパラレルデータを得るものである。
手段１１の第１〜第ｎレジスタの所定レジスタの出力デ
ータを剰余１演算手段を介して得られる剰余データと、
所定レジスタに供給されるデータとの排他的論理和を取
って主信号であるパラレルデータを得るものである。
【００４４】訂正手段４３は、主信号再生手段４２によ
り得られたパラレルデータと、１ビット誤り検出手段４
１により検出された１ビット誤りデータとの排他的論理
和を取って訂正データＨ１′〜Ｈ５′を求めるものであ
る。
り得られたパラレルデータと、１ビット誤り検出手段４
１により検出された１ビット誤りデータとの排他的論理
和を取って訂正データＨ１′〜Ｈ５′を求めるものであ
る。
【００４５】１ビット誤り検出手段４１は、剰余１演算
手段と、シンドローム生成手段１１から出力されるシン
ドロームＳとその剰余１演算手段から出力される剰余デ
ータとが供給され、所定間隔でパルスが供給された場合
にシンドロームＳを選択し、他の場合は剰余データを選
択して出力するセレクタと、セレクタから出力されるシ
ンドロームＳ又は剰余データを保持して出力するレジス
タと、ｎ個のｍビットシリアルデータの内の最上位桁を
有するパラレルデータＨ１の全ての誤りパターンをデコ
ードして出力するデコーダとによって構成するのが好ま
しい。
手段と、シンドローム生成手段１１から出力されるシン
ドロームＳとその剰余１演算手段から出力される剰余デ
ータとが供給され、所定間隔でパルスが供給された場合
にシンドロームＳを選択し、他の場合は剰余データを選
択して出力するセレクタと、セレクタから出力されるシ
ンドロームＳ又は剰余データを保持して出力するレジス
タと、ｎ個のｍビットシリアルデータの内の最上位桁を
有するパラレルデータＨ１の全ての誤りパターンをデコ
ードして出力するデコーダとによって構成するのが好ま
しい。
【００４６】主信号再生手段４２は、シンドローム生成
手段１１の第ｎレジスタの出力データが入力される剰余
１演算手段と、この剰余１演算手段から出力される剰余
データと第ｎレジスタに供給されるデータとの排他的論
理和を取る排他的論理和手段とから構成するのが好まし
い。
手段１１の第ｎレジスタの出力データが入力される剰余
１演算手段と、この剰余１演算手段から出力される剰余
データと第ｎレジスタに供給されるデータとの排他的論
理和を取る排他的論理和手段とから構成するのが好まし
い。
【００４７】訂正手段４３は、主信号再生手段４２から
出力される主信号であるパラレルデータを保持して出力
するレジスタと、このレジスタから出力されるパラレル
データと１ビット誤り検出手段４１から出力される１ビ
ット誤りデータとの排他的論理和を取る排他的論理和手
段とから構成するのが好ましい。
出力される主信号であるパラレルデータを保持して出力
するレジスタと、このレジスタから出力されるパラレル
データと１ビット誤り検出手段４１から出力される１ビ
ット誤りデータとの排他的論理和を取る排他的論理和手
段とから構成するのが好ましい。
【００４８】
【作用】上述した本発明によれば、１ビット誤り検出手
段４１を、剰余１演算手段と、セレクタと、レジスタ
と、デコーダとによって構成することができ、主信号再
生手段４２を、剰余１演算手段と、排他的論理和手段と
から構成することができ、訂正手段４３を、レジスタ
と、排他的論理和手段とから構成することができる。
段４１を、剰余１演算手段と、セレクタと、レジスタ
と、デコーダとによって構成することができ、主信号再
生手段４２を、剰余１演算手段と、排他的論理和手段と
から構成することができ、訂正手段４３を、レジスタ
と、排他的論理和手段とから構成することができる。
【００４９】これら１ビット誤り検出手段４１、主信号
再生手段４２、及び訂正手段４３の構成部品は、各手段
４１，４２，４３に対応する従来の１ビット誤り訂正回
路の誤り訂正部の構成部品よりも大幅に少ない。
再生手段４２、及び訂正手段４３の構成部品は、各手段
４１，４２，４３に対応する従来の１ビット誤り訂正回
路の誤り訂正部の構成部品よりも大幅に少ない。
【００５０】従って、本発明の１ビット誤り訂正回路
は、従来よりもかなり小型にすることができ、かつ低コ
ストで作成することができる。
は、従来よりもかなり小型にすることができ、かつ低コ
ストで作成することができる。
【００５１】
【実施例】以下、図面を参照して本発明の一実施例につ
いて説明する。図２は本発明の一実施例によるＣＲＣ演
算に基づく１ビット誤り訂正回路のブロック構成図であ
る。この図において図４に示す従来例の各部に対応する
部分には同一符号を付し、その説明を省略する。
いて説明する。図２は本発明の一実施例によるＣＲＣ演
算に基づく１ビット誤り訂正回路のブロック構成図であ
る。この図において図４に示す従来例の各部に対応する
部分には同一符号を付し、その説明を省略する。
【００５２】図２に示す実施例の１ビット誤り訂正回路
は、図６に示す８パラ展開の打ち消し型シンドローム生
成部１１と、１ビット誤り検出部４１と、主信号再生部
４２と、訂正部４２とから構成されている。
は、図６に示す８パラ展開の打ち消し型シンドローム生
成部１１と、１ビット誤り検出部４１と、主信号再生部
４２と、訂正部４２とから構成されている。
【００５３】１ビット誤り検出部４１は、セレクタ４５
と、シフトレジスタ４６と、第１剰余演算回路４７と、
デコーダ４８とを具備して構成されている。セレクタ４
５は、パルスＰ１が供給された場合に入力端Ａに供給さ
れるシンドロームＳを選択して出力するものであり、パ
ルスＰ１が供給されていない場合は入力端Ｂに供給され
る第１剰余演算回路４７からの剰余を選択して出力す
る。
と、シフトレジスタ４６と、第１剰余演算回路４７と、
デコーダ４８とを具備して構成されている。セレクタ４
５は、パルスＰ１が供給された場合に入力端Ａに供給さ
れるシンドロームＳを選択して出力するものであり、パ
ルスＰ１が供給されていない場合は入力端Ｂに供給され
る第１剰余演算回路４７からの剰余を選択して出力す
る。
【００５４】但し、パルスＰ１は従来例で説明したもの
と同様なものであり、時刻ｔ1 〜ｔ5 のタイミングで、
時刻ｔ5 置き（ｔ0 ，ｔ5 ，ｔ10，ｔ15，…）に供給さ
れ、同時刻においてクロック信号より半ビット遅れたタ
イミングで供給されるものとする。
と同様なものであり、時刻ｔ1 〜ｔ5 のタイミングで、
時刻ｔ5 置き（ｔ0 ，ｔ5 ，ｔ10，ｔ15，…）に供給さ
れ、同時刻においてクロック信号より半ビット遅れたタ
イミングで供給されるものとする。
【００５５】また、デコーダ４８は、Ｈ１の誤りパター
ンに応じて入力側にインバータを付けた８入力タイプの
オアゲートを８個用いて構成したものである。時刻ｔ5
において、従来例で説明したようにシンドローム生成部
１１からシンドロームＳが出力されてセレクタ４５に供
給されたとする。
ンに応じて入力側にインバータを付けた８入力タイプの
オアゲートを８個用いて構成したものである。時刻ｔ5
において、従来例で説明したようにシンドローム生成部
１１からシンドロームＳが出力されてセレクタ４５に供
給されたとする。
【００５６】この場合のシンドロームＳは、Ｈ４の８ビ
ット目が１ビット誤っていた場合のものとする。このシ
ンドロームＳを余剰演算の際に用いる関数ｆ(X) を行列
α(X) として式で表すと、図３に示す式のようにな
り、式′が導かれる。
ット目が１ビット誤っていた場合のものとする。このシ
ンドロームＳを余剰演算の際に用いる関数ｆ(X) を行列
α(X) として式で表すと、図３に示す式のようにな
り、式′が導かれる。
【００５７】式′の両辺にα3 を掛けると式とな
る。式の右辺は図７に示す式′と同様となる。つま
り、Ｈ４の８ビット目に誤りがあった場合のシンドロー
ムＳを３回第１剰余演算回路に通して演算すればＨ１の
８ビット目に誤りがあった場合のシンドロームＳと同様
となることがわかる。
る。式の右辺は図７に示す式′と同様となる。つま
り、Ｈ４の８ビット目に誤りがあった場合のシンドロー
ムＳを３回第１剰余演算回路に通して演算すればＨ１の
８ビット目に誤りがあった場合のシンドロームＳと同様
となることがわかる。
【００５８】従って、シンドロームＳがＨ２〜Ｈ５の誤
りによるものであれば、これらシンドロームＳをデコー
ダ４８に入力する前に、Ｈ１の誤りによるシンドローム
Ｓと同様となるように操作してやればよく、このことか
らデコーダ４８は先に記述したようにＨ１の誤りパター
ンに応じて入力側にインバータを付けた８入力タイプの
オアゲートを８個用いて構成すればよいことがわかる。
りによるものであれば、これらシンドロームＳをデコー
ダ４８に入力する前に、Ｈ１の誤りによるシンドローム
Ｓと同様となるように操作してやればよく、このことか
らデコーダ４８は先に記述したようにＨ１の誤りパター
ンに応じて入力側にインバータを付けた８入力タイプの
オアゲートを８個用いて構成すればよいことがわかる。
【００５９】時刻ｔ5 において、セレクタ４５にパルス
Ｐ１が供給されると、前記したＨ４の７ビット目に１ビ
ット誤りが有る場合のシンドロームＳが選択され、シフ
トレジスタ４６に供給される。この供給されたシンドロ
ームＳは、従来例で説明したようにH5Exｆ(H4)Exｆ2(H
3)Ex ｆ3(H2)Ex ｆ4(H1) で表される。
Ｐ１が供給されると、前記したＨ４の７ビット目に１ビ
ット誤りが有る場合のシンドロームＳが選択され、シフ
トレジスタ４６に供給される。この供給されたシンドロ
ームＳは、従来例で説明したようにH5Exｆ(H4)Exｆ2(H
3)Ex ｆ3(H2)Ex ｆ4(H1) で表される。
【００６０】時刻ｔ6 において図示せぬクロック信号が
供給されると、H5Exｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ
4(H1) がシフトレジスタ４６に記憶され、第１剰余演算
回路４７及びデコーダ４８に入力される。これによって
第１剰余演算回路４７からは、ｆH5Exｆ2(H4)Ex ｆ3(H
3)Ex ｆ4(H2)Ex ｆ5(H1) が出力される。
供給されると、H5Exｆ(H4)Exｆ2(H3)Ex ｆ3(H2)Ex ｆ
4(H1) がシフトレジスタ４６に記憶され、第１剰余演算
回路４７及びデコーダ４８に入力される。これによって
第１剰余演算回路４７からは、ｆH5Exｆ2(H4)Ex ｆ3(H
3)Ex ｆ4(H2)Ex ｆ5(H1) が出力される。
【００６１】この時、セレクタ４５は入力端Ｂへの供給
データを選択するようになっているので、ｆH5Exｆ2(H
4)Ex ｆ3(H3)Ex ｆ4(H2)Ex ｆ5(H1) が選択されてシフ
トレジスタ４６に供給される。
データを選択するようになっているので、ｆH5Exｆ2(H
4)Ex ｆ3(H3)Ex ｆ4(H2)Ex ｆ5(H1) が選択されてシフ
トレジスタ４６に供給される。
【００６２】時刻ｔ7 においてクロック信号が供給され
ると、ｆH5Exｆ2(H4)Ex ｆ3(H3)Exｆ4(H2)Ex ｆ5(H1)
がシフトレジスタ４６に記憶され、第１剰余演算回路４
７及びデコーダ４８に入力される。これによって第１剰
余演算回路４７から、ｆ2H5Ex ｆ3(H4)Ex ｆ4(H3)Ex ｆ
5(H2)Ex ｆ6(H1) が出力され、セレクタ４５を介してシ
フトレジスタ４６に供給される。
ると、ｆH5Exｆ2(H4)Ex ｆ3(H3)Exｆ4(H2)Ex ｆ5(H1)
がシフトレジスタ４６に記憶され、第１剰余演算回路４
７及びデコーダ４８に入力される。これによって第１剰
余演算回路４７から、ｆ2H5Ex ｆ3(H4)Ex ｆ4(H3)Ex ｆ
5(H2)Ex ｆ6(H1) が出力され、セレクタ４５を介してシ
フトレジスタ４６に供給される。
【００６３】時刻ｔ8 においてクロック信号が供給され
ると、ｆ2H5Ex ｆ3(H4)Ex ｆ4(H3)Ex ｆ5(H2)Ex ｆ6(H
1) がシフトレジスタ４６に記憶され、第１剰余演算回
路４７及びデコーダ４８に入力される。これによって第
１剰余演算回路４７から、ｆ3H5Ex ｆ4(H4)Ex ｆ5(H3)E
x ｆ6(H2)Ex ｆ7(H1) が出力され、セレクタ４５を介し
てシフトレジスタ４６に供給される。
ると、ｆ2H5Ex ｆ3(H4)Ex ｆ4(H3)Ex ｆ5(H2)Ex ｆ6(H
1) がシフトレジスタ４６に記憶され、第１剰余演算回
路４７及びデコーダ４８に入力される。これによって第
１剰余演算回路４７から、ｆ3H5Ex ｆ4(H4)Ex ｆ5(H3)E
x ｆ6(H2)Ex ｆ7(H1) が出力され、セレクタ４５を介し
てシフトレジスタ４６に供給される。
【００６４】このｆ3H5Ex ｆ4(H4)Ex ｆ5(H3)Ex ｆ6(H
2)Ex ｆ7(H1) は、図３に示す式の両辺にα3 を掛け
たものと同等であるので、Ｈ１の８ビット目に誤りがあ
った場合のシンドロームＳと同様となったことがわか
る。
2)Ex ｆ7(H1) は、図３に示す式の両辺にα3 を掛け
たものと同等であるので、Ｈ１の８ビット目に誤りがあ
った場合のシンドロームＳと同様となったことがわか
る。
【００６５】時刻ｔ9 においてクロック信号が供給され
ると、ｆ3H5Ex ｆ4(H4)Ex ｆ5(H3)Ex ｆ6(H2)Ex ｆ7(H
1) がシフトレジスタ４６に記憶され、第１剰余演算回
路４７及びデコーダ４８に入力される。
ると、ｆ3H5Ex ｆ4(H4)Ex ｆ5(H3)Ex ｆ6(H2)Ex ｆ7(H
1) がシフトレジスタ４６に記憶され、第１剰余演算回
路４７及びデコーダ４８に入力される。
【００６６】これによってデコーダ４８から１ビット誤
り検出データが出力される。主信号再生部４２は、第１
剰余演算回路５０と排他的論理和回路５１とから構成さ
れており、シンドローム生成部１１のシフトレジスタ１
９の出力データが第１剰余演算回路５０に入力され、剰
余演算回路５０から出力される剰余と、シフトレジスタ
１８の出力データとの排他的論理和が排他的論理和回路
５１で取られて出力されるようになっている。
り検出データが出力される。主信号再生部４２は、第１
剰余演算回路５０と排他的論理和回路５１とから構成さ
れており、シンドローム生成部１１のシフトレジスタ１
９の出力データが第１剰余演算回路５０に入力され、剰
余演算回路５０から出力される剰余と、シフトレジスタ
１８の出力データとの排他的論理和が排他的論理和回路
５１で取られて出力されるようになっている。
【００６７】訂正部４２はシフトレジスタ５３と排他的
論理和回路５４とから構成されており、主信号再生部４
２の排他的論理和回路５１の出力データがシフトレジス
タ５３に記憶され、この記憶されたデータと、先に記述
したデコーダ４８から出力されるが１ビット誤り検出デ
ータとの排他的論理和が排他的論理和回路５４で取られ
て訂正データとして主力されるようになっている。
論理和回路５４とから構成されており、主信号再生部４
２の排他的論理和回路５１の出力データがシフトレジス
タ５３に記憶され、この記憶されたデータと、先に記述
したデコーダ４８から出力されるが１ビット誤り検出デ
ータとの排他的論理和が排他的論理和回路５４で取られ
て訂正データとして主力されるようになっている。
【００６８】時刻ｔ8 において、シンドローム生成部１
１のシフトレジスタ１８にはH4Exｆ(H3)Exｆ2(H2)Ex ｆ
3(H1)Ex ｆ4(C)が記憶され、シフトレジスタ１９にはH3
Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が記憶されるので、シフト
レジスタ１９からH3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が出力
されて第１剰余演算回路５０に入力され、シフトレジス
タ１８からH4Exｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)が
出力されて排他的論理和回路５１に入力される。
１のシフトレジスタ１８にはH4Exｆ(H3)Exｆ2(H2)Ex ｆ
3(H1)Ex ｆ4(C)が記憶され、シフトレジスタ１９にはH3
Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が記憶されるので、シフト
レジスタ１９からH3Exｆ(H2)Exｆ2(H1)Ex ｆ3(C)が出力
されて第１剰余演算回路５０に入力され、シフトレジス
タ１８からH4Exｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)が
出力されて排他的論理和回路５１に入力される。
【００６９】更に、第１剰余演算回路５０からは、ｆ(H
3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)が出力されるので、こ
のｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)と、H4Exｆ(H3)
Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)との排他的論理和が排他
的論理和回路５１で取られることによって、主信号Ｈ４
が出力される。
3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)が出力されるので、こ
のｆ(H3)Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)と、H4Exｆ(H3)
Exｆ2(H2)Ex ｆ3(H1)Ex ｆ4(C)との排他的論理和が排他
的論理和回路５１で取られることによって、主信号Ｈ４
が出力される。
【００７０】そして、先のデコーダ４８から１ビット誤
り検出データが出力された時刻ｔ9において、Ｈ４がシ
フトレジスタ５３に記憶されて排他的論理和回路５４に
入力されるので、デコーダ４８から１ビット誤り検出デ
ータとＨ４との排他的論理和が取られて訂正データＨ
４′として出力される。
り検出データが出力された時刻ｔ9において、Ｈ４がシ
フトレジスタ５３に記憶されて排他的論理和回路５４に
入力されるので、デコーダ４８から１ビット誤り検出デ
ータとＨ４との排他的論理和が取られて訂正データＨ
４′として出力される。
【００７１】つまり、Ｈ４の１ビット誤りが訂正された
ことになる。以上説明した実施例の１ビット誤り訂正回
路は、図４に示す従来例の１ビット誤り訂正回路よりも
大幅に部品数が削減されて構成されていることが分か
る。
ことになる。以上説明した実施例の１ビット誤り訂正回
路は、図４に示す従来例の１ビット誤り訂正回路よりも
大幅に部品数が削減されて構成されていることが分か
る。
【００７２】尚、本発明は、シリアル処理形のＣＲＣ演
算に基づく１ビット誤り訂正回路にも適用できることは
言うまでもない。
算に基づく１ビット誤り訂正回路にも適用できることは
言うまでもない。
【００７３】
【発明の効果】以上説明したように、本発明によれば、
ＣＲＣ演算に基づく１ビット誤り訂正回路を、小規模か
つ低コストで構成することができる効果がある。
ＣＲＣ演算に基づく１ビット誤り訂正回路を、小規模か
つ低コストで構成することができる効果がある。
【図１】本発明の原理図である。
【図２】本発明の一実施例によるＣＲＣ演算に基づく１
ビット誤り訂正回路のブロック構成図である。
ビット誤り訂正回路のブロック構成図である。
【図３】図２に示すＣＲＣ演算に基づく１ビット誤り訂
正回路におけるシンドロームを説明するための図であ
る。
正回路におけるシンドロームを説明するための図であ
る。
【図４】従来例によるＣＲＣ演算に基づく１ビット誤り
訂正回路のブロック構成図である。
訂正回路のブロック構成図である。
【図５】図２及び図４に示す１ビット誤り訂正回路の入
力データとなる巡回符号の構成を示す図である。
力データとなる巡回符号の構成を示す図である。
【図６】図２及び図４に示す第１剰余演算回路から出力
される剰余を説明するための図である。
される剰余を説明するための図である。
【図７】図４に示すＣＲＣ演算に基づく１ビット誤り訂
正回路におけるシンドロームを説明するための図であ
る。
正回路におけるシンドロームを説明するための図であ
る。
１１ シンドローム生成手段 ４１ １ビット誤り検出手段 ４２ 主信号再生手段 ４３ 訂正手段 Ｈ１〜Ｈ５ 入力されるパラレルデータ Ｈ１′〜Ｈ５′ 出力される訂正データ
フロントページの続き (72)発明者 滝沢 雄二 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 内藤 英俊 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 池田 聡美 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 田島 一幸 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 山下 治雄 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 龍野 秀雄 東京都千代田区内幸町一丁目１番６号 日 本電信電話株式会社内
Claims (6)
- 【請求項１】 ｎ個のｍビットシリアルデータを各々ｍ
ビットのパラレルデータ(H1,H2,H3,H4,H5)に変換し、こ
の変換されたパラレルデータ(H1 〜H5) のシンドローム
を求め、該シンドロームによって該パラレルデータ(H1
〜H5) の１ビット誤りを訂正するＣＲＣ演算に基づく１
ビット誤り訂正回路において、 パラレルデータ(H1)を第１排他的論理和手段(12)及びレ
ジスタ(13)を介して、関数ｆ(X) に基づいてパラレルデ
ータ(H1 〜H5) の剰余を求める剰余１演算手段(14)に入
力し、該剰余１演算手段(14)から出力される剰余データ
と次に入力されるパラレルデータ(H2)との排他的論理和
を該排他的論理和手段(12)で取って該レジスタ(13)に供
給するといった巡回を行い、この巡回によって求められ
る剰余データをパラレルデータ(H1 〜H5) の個数ｎに応
じて直列接続された第１〜第ｎレジスタ(15 〜19) によ
り順次シフトさせて、パラレルデータ(H1 〜H5) の個数
ｎが乗数となる関数ｆn (X) に基づいてパラレルデータ
(H1 〜H5) の剰余を求める剰余２演算手段(20)に入力
し、該剰余２演算手段(20)から出力される剰余データと
該第１排他的論理和手段(12)の後段のレジスタ(13)から
出力される剰余データとの排他的論理和を第２排他的論
理和手段(21)で取ることによってシンドローム(S) を求
めるシンドローム生成手段(11)と、 該シンドローム(S) を剰余１演算手段に巡回し、この巡
回により得られる剰余データをデコードして１ビット誤
りデータを検出する１ビット誤り検出手段(41)と、 前記シンドローム生成手段(11)の第１〜第ｎレジスタ(1
5 〜19) の所定レジスタの出力データを剰余１演算手段
を介して得られる剰余データと、該所定レジスタに供給
されるデータとの排他的論理和を取って主信号であるパ
ラレルデータを得る主信号再生手段(42)と、 該主信号再生手段(42)により得られたパラレルデータ
と、該１ビット誤り検出手段(41)により検出された１ビ
ット誤りデータとの排他的論理和を取って訂正データ(H
1 ′〜H5′) を求める訂正手段(42)とを具備したことを
特徴とするＣＲＣ演算に基づく１ビット誤り訂正回路。 - 【請求項２】 前記１ビット誤り検出手段(41)を、 剰余１演算手段(47)と、 前記シンドローム生成手段(11)から出力されるシンドロ
ーム(S) と、該剰余１演算手段(47)から出力される剰余
データとが供給され、所定間隔でパルス(P1)が供給され
た場合に該シンドローム(S) を選択し、他の場合は該剰
余データを選択して出力するセレクタ(46)と、 該セレクタ(46)から出力されるシンドローム(S) 又は剰
余データを保持して出力するレジスタ(46)と、 前記ｎ個のｍビットシリアルデータの内の最上位桁を有
するパラレルデータ(H1)の全ての誤りパターンをデコー
ドして出力するデコーダ(48)とによって構成したことを
特徴とする請求項１記載のＣＲＣ演算に基づく１ビット
誤り訂正回路。 - 【請求項３】 前記１ビット誤り検出手段(41)のセレク
タに、前記パルス(P1)が、パラレルデータ(H1 〜H5) の
個数ｎに対応するクロック時刻ｎ毎に供給されるように
したことを特徴とする請求項２記載のＣＲＣ演算に基づ
く１ビット誤り訂正回路。 - 【請求項４】 前記主信号再生手段(42)を、 前記シンドローム生成手段(11)の第ｎレジスタ(19)の出
力データが入力される剰余１演算手段(50)と、 該剰余１演算手段(50)から出力される剰余データと、該
第ｎレジスタ(19)に供給されるデータとの排他的論理和
を取る排他的論理和手段(51)とから構成したことを特徴
とする請求項１記載のＣＲＣ演算に基づく１ビット誤り
訂正回路。 - 【請求項５】 前記訂正手段(43)を、 前記主信号再生手段(42)から出力される主信号であるパ
ラレルデータを保持して出力するレジスタ(53)と、 該レジスタ(53)から出力されるパラレルデータと、前記
１ビット誤り検出手段(41)から出力される１ビット誤り
データとの排他的論理和を取る排他的論理和手段(54)と
から構成したことを特徴とする請求項１記載のＣＲＣ演
算に基づく１ビット誤り訂正回路。 - 【請求項６】 前記主信号再生手段(42)の剰余１演算手
段(50)に入力されるデータを、前記シンドローム生成手
段(11)の第ｎレジスタ(19)の前段の第ｎ−１レジスタ(1
8)の出力データとし、該主信号再生手段(42)の排他的論
理和手段(51)に入力されるデータを、該第ｎ−１レジス
タ(18)に供給されるデータとした場合に、前記訂正手段
(43)のレジスタ(53)に同機能のレジスタを直列に接続
し、 該主信号再生手段(42)の剰余１演算手段(50)に入力され
るデータを、該シンドローム生成手段(11)の第ｎレジス
タ(19)の２段前の第ｎ−２レジスタ(17)の出力データと
し、該主信号再生手段(42)の排他的論理和手段(51)に入
力されるデータを、該第ｎ−２レジスタ(17)に供給され
るデータとした場合に、前記訂正手段(43)のレジスタ(5
3)に同機能の２個のレジスタを直列に接続し、 該主信号再生手段(42)の剰余１演算手段(50)に入力され
るデータを、該シンドローム生成手段(11)の第ｎレジス
タ(19)のＰ段前の第ｎ−Ｐレジスタの出力データとし、
該主信号再生手段(42)の排他的論理和手段(51)に入力さ
れるデータを、該第ｎ−Ｐレジスタに供給されるデータ
とした場合に、前記訂正手段(43)のレジスタ(53)に同機
能のＰ個のレジスタを直列に接続して構成することを特
徴とする請求項４又は５記載のＣＲＣ演算に基づく１ビ
ット誤り訂正回路。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP05876892A JP3279624B2 (ja) | 1992-02-13 | 1992-02-13 | Ｃｒｃ演算に基づく１ビット誤り訂正回路 |
| US08/016,871 US5408476A (en) | 1992-02-13 | 1993-02-11 | One bit error correction method having actual data reproduction function |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP05876892A JP3279624B2 (ja) | 1992-02-13 | 1992-02-13 | Ｃｒｃ演算に基づく１ビット誤り訂正回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH05227041A true JPH05227041A (ja) | 1993-09-03 |
| JP3279624B2 JP3279624B2 (ja) | 2002-04-30 |
Family
ID=13093731
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP05876892A Expired - Fee Related JP3279624B2 (ja) | 1992-02-13 | 1992-02-13 | Ｃｒｃ演算に基づく１ビット誤り訂正回路 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5408476A (ja) |
| JP (1) | JP3279624B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8699624B2 (en) | 2010-12-07 | 2014-04-15 | Fuji Xerox Co., Ltd. | Receiving apparatus and data transmission apparatus |
| US8750423B2 (en) | 2010-12-07 | 2014-06-10 | Fuji Xerox Co., Ltd. | Receiving apparatus, data transfer apparatus, data receiving method and non-transitory computer readable recording medium |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1996007254A1 (en) * | 1994-08-30 | 1996-03-07 | Seiko Instruments Inc. | Receiver |
| KR100188147B1 (ko) * | 1995-10-31 | 1999-06-01 | 김광호 | 주기적 여유 코드를 이용한 오류검출회로 |
| JP2003512693A (ja) * | 1999-10-20 | 2003-04-02 | コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ | 読出し専用型の記録担体と読出し装置 |
| US7613991B1 (en) | 2003-08-19 | 2009-11-03 | Altera Corporation | Method and apparatus for concurrent calculation of cyclic redundancy checks |
| US7320101B1 (en) * | 2003-08-19 | 2008-01-15 | Altera Corporation | Fast parallel calculation of cyclic redundancy checks |
| US7634713B1 (en) * | 2006-05-16 | 2009-12-15 | Altera Corporation | Error detection and location circuitry for configuration random-access memory |
| US7844886B1 (en) | 2006-05-16 | 2010-11-30 | Altera Corporation | Parallel processing error detection and location circuitry for configuration random-access memory |
| CN116126570A (zh) | 2021-11-12 | 2023-05-16 | 三星电子株式会社 | 安全集成电路及其操作方法、电子装置 |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2094041B (en) * | 1981-03-03 | 1985-08-21 | Sangamo Weston | Data receivers incorporating error code detection and decoding |
| US4928280A (en) * | 1988-04-29 | 1990-05-22 | International Business Machines Corporation | Fast processor for multi-bit error correction codes |
| JPH03219725A (ja) * | 1988-10-28 | 1991-09-27 | Mitsubishi Electric Corp | 誤り検査コード生成装置および伝送誤り検出装置 |
-
1992
- 1992-02-13 JP JP05876892A patent/JP3279624B2/ja not_active Expired - Fee Related
-
1993
- 1993-02-11 US US08/016,871 patent/US5408476A/en not_active Expired - Lifetime
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8699624B2 (en) | 2010-12-07 | 2014-04-15 | Fuji Xerox Co., Ltd. | Receiving apparatus and data transmission apparatus |
| US8750423B2 (en) | 2010-12-07 | 2014-06-10 | Fuji Xerox Co., Ltd. | Receiving apparatus, data transfer apparatus, data receiving method and non-transitory computer readable recording medium |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3279624B2 (ja) | 2002-04-30 |
| US5408476A (en) | 1995-04-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5430739A (en) | Real-time Reed-Solomon decoder | |
| US4751704A (en) | Method and apparatus for decoding BCH code | |
| EP0793351A1 (en) | Apparatus for computing error correction syndromes | |
| US8433974B2 (en) | Cyclic redundancy check code generating circuit and cyclic redundancy check code generating method | |
| JPH10107650A (ja) | 誤り検出回路および誤り訂正回路 | |
| JPH05227041A (ja) | Ｃｒｃ演算に基づく１ビット誤り訂正回路 | |
| JPH0221180B2 (ja) | ||
| JP3454962B2 (ja) | 誤り訂正符号の符号器及び復号器 | |
| US6360349B1 (en) | Syndrome computing apparatus | |
| JPH0738626B2 (ja) | ワード同期検出回路 | |
| JP2004173199A (ja) | 巡回符号を用いた誤り訂正回路 | |
| JP3310186B2 (ja) | リード・ソロモン符号の復号回路 | |
| JP3398560B2 (ja) | 短縮化誤り訂正復号装置 | |
| JP2858538B2 (ja) | 再シンドロームチェック方式 | |
| JP3521558B2 (ja) | 伝送装置 | |
| JP3253381B2 (ja) | 誤り訂正回路 | |
| JP3131969B2 (ja) | 演算装置 | |
| JP3452725B2 (ja) | トレリス軟判定誤り訂正回路およびトレリス変分調整方法 | |
| JP3268926B2 (ja) | 誤り訂正回路 | |
| JP2600130B2 (ja) | 誤り訂正回路 | |
| JPH10200417A (ja) | デジタル復号装置 | |
| KR100192792B1 (ko) | 리드 솔로몬 복호기의 다항식 평가 장치 | |
| JP2797569B2 (ja) | ユークリッドの互除回路 | |
| JP2710626B2 (ja) | ブロック同期回路 | |
| JPH05191297A (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 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110222 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |