JPS5815352A - ３誤り訂正符号復号方式 - Google Patents
３誤り訂正符号復号方式Info
- Publication number
- JPS5815352A JPS5815352A JP56113617A JP11361781A JPS5815352A JP S5815352 A JPS5815352 A JP S5815352A JP 56113617 A JP56113617 A JP 56113617A JP 11361781 A JP11361781 A JP 11361781A JP S5815352 A JPS5815352 A JP S5815352A
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- bit string
- bit
- syndrome
- error
- 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
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
Landscapes
- Physics & Mathematics (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
本発明はディジタルデータの伝送や蓄積時に生じるビッ
ト誤りを自動的に検出し訂正する方式に関する。
ト誤りを自動的に検出し訂正する方式に関する。
データ伝送や蓄積時に生じる誤りを自動的に訂正する方
法として誤り訂正符号化技術が用いられている。これに
使われる誤り訂正符号には各種あるが、その中でＢＣＨ
（ボーゼ・チョドーリ・ホッキンジェム）符号は符号長
や誤り訂正能力の選択の自由度が大きく、また付加され
た検査ビット数のわりに誤り訂正能力が優わた符号とし
て知られている。本発明はＢＣＨ符号の内、一符号語に
３つ以下のビット誤りがある場合にその誤りを訂正でき
る符号、すなわち３誤り訂正ＢＣＨ符号を用いて符号化
さねた信号中に生じたビット誤りを訂正する装置すなわ
ち復号装置に関する。
法として誤り訂正符号化技術が用いられている。これに
使われる誤り訂正符号には各種あるが、その中でＢＣＨ
（ボーゼ・チョドーリ・ホッキンジェム）符号は符号長
や誤り訂正能力の選択の自由度が大きく、また付加され
た検査ビット数のわりに誤り訂正能力が優わた符号とし
て知られている。本発明はＢＣＨ符号の内、一符号語に
３つ以下のビット誤りがある場合にその誤りを訂正でき
る符号、すなわち３誤り訂正ＢＣＨ符号を用いて符号化
さねた信号中に生じたビット誤りを訂正する装置すなわ
ち復号装置に関する。
ここで３誤り訂正ＢＣＨ符号について簡単に説明してお
く。
く。
３誤り訂正ＢＣＨ符号においては符号語Ｃはｋ個の情報
ビット（αｌ、α２．・・・・・・、αｋ）とこれらの
情報ビットから計算されたｑ個の検査ビット（αに＋１
。
ビット（αｌ、α２．・・・・・・、αｋ）とこれらの
情報ビットから計算されたｑ個の検査ビット（αに＋１
。
（Ｚｋ＋２．・・・、α＆＋ｑ）より構成される。つま
り符号語Ｃは Ｃ＝（α１．α２．・・・・・・、αに、αｉ＋１、・
・・・・・、αに＋９）となる。
り符号語Ｃは Ｃ＝（α１．α２．・・・・・・、αに、αｉ＋１、・
・・・・・、αに＋９）となる。
但しｋ、はｍを４以上の整数として
ｋ＝２−３ｍ−１
ｑ＝８ｍ
となるよう決定される。以後符号長に十ｑ＝２−１をｎ
で表わす。すなわち符号語Ｃは Ｃ＝（α１．α２．・・・・・・、α、、−１１ＬＬｎ
）となる。検査ビットは符号語が ＨＣ＝０ を満足するよう決定される。ここでＣはＣの転置ベクト
ルである。Ｈはパリティ検査行列でＧＦ（２”）の原始
元αを用いて と表わされる。Ｈの各要素α′（ｗ＝ｏ、１．−、ｓ−
１）はｍ要素の列ベクトルで表わされる。
で表わす。すなわち符号語Ｃは Ｃ＝（α１．α２．・・・・・・、α、、−１１ＬＬｎ
）となる。検査ビットは符号語が ＨＣ＝０ を満足するよう決定される。ここでＣはＣの転置ベクト
ルである。Ｈはパリティ検査行列でＧＦ（２”）の原始
元αを用いて と表わされる。Ｈの各要素α′（ｗ＝ｏ、１．−、ｓ−
１）はｍ要素の列ベクトルで表わされる。
ここでＣに誤りが生じてＣ′となったとする、Ｃ′＝（
α′１、α′２、・・・・・・、α′ｎ−１、α′ｎ）
Ｃ′はＣと誤りベクトルｅにより次のように表わされる
。
α′１、α′２、・・・・・・、α′ｎ−１、α′ｎ）
Ｃ′はＣと誤りベクトルｅにより次のように表わされる
。
Ｃ′＝Ｃ＋ｅ
但しｅはＣ′の誤りビットの位置では１．他の位置でＨ
ｏである要素からなるベクトルである。
ｏである要素からなるベクトルである。
ｅ＝（ｅｌ、ｅ２・・・・・・、ｅｎ−１、ｅｎ）Ｃ′
が与えられた時に、もとのＣを再現するのが復号であり
２本発明はそれを実現する新しい装置を与えるものであ
る。
が与えられた時に、もとのＣを再現するのが復号であり
２本発明はそれを実現する新しい装置を与えるものであ
る。
従来の３誤り訂正符号の復号は、通常、以下に述べる方
法で行なわわている。
法で行なわわている。
まず次式で定義される第１．第２、および第３シンドロ
ームすなわちＡ１、Ａ２、およびＡ３を計算する。
ームすなわちＡ１、Ａ２、およびＡ３を計算する。
シンドロームＡ１、Ａ２、およびＡ３は例えばＦ、Ｊ。
ＭａｃＷｉｌｌｉａｍｓ、Ｎ、Ｊ、Ａ、５１ｏａｎｅ著
”ＴｈｅＴｈｅｏｒｙｏｆＥｒｒｏｒ−Ｃｏｒｒｅｃｔ
ｉｎｇＣｏｄｅｓ、ＰａｒｔＩ”（Ｎｏｒｔｈ−Ｈｏｌ
ｌａｎｄＰｕｂｌｉｓｈｉｎｇＣｏｍｐａｎｙ）ｐｐ、
２７０−２７２にあるようにして生成される。つまり第
１シンドロームＡ１はαの最小多項式に対応するフィー
ドバックシフトレジスタにＣ′のビットをα′１からα
′ｎまで入力し、αこが入力された時点でシフトレジス
タ中に完成する。第２シンドロームＡ２はαの最小多項
式に対応するフィードバックシフトレジスタにＣ′を入
力し、最後のビットが入力された時点でシフトレジスタ
中にできあがったビット列を排他的論理和回路を用いて
変換して得られる。第８シンドロームＡ３も、同様に、
αの最小多項式に対応するフィードバックシフトレジス
タにＣ′を入力し。
”ＴｈｅＴｈｅｏｒｙｏｆＥｒｒｏｒ−Ｃｏｒｒｅｃｔ
ｉｎｇＣｏｄｅｓ、ＰａｒｔＩ”（Ｎｏｒｔｈ−Ｈｏｌ
ｌａｎｄＰｕｂｌｉｓｈｉｎｇＣｏｍｐａｎｙ）ｐｐ、
２７０−２７２にあるようにして生成される。つまり第
１シンドロームＡ１はαの最小多項式に対応するフィー
ドバックシフトレジスタにＣ′のビットをα′１からα
′ｎまで入力し、αこが入力された時点でシフトレジス
タ中に完成する。第２シンドロームＡ２はαの最小多項
式に対応するフィードバックシフトレジスタにＣ′を入
力し、最後のビットが入力された時点でシフトレジスタ
中にできあがったビット列を排他的論理和回路を用いて
変換して得られる。第８シンドロームＡ３も、同様に、
αの最小多項式に対応するフィードバックシフトレジス
タにＣ′を入力し。
最後のビットが入力された時点でシフトレジスタ中にで
きあがったビット列を排他的論理和回路を用いて変換し
て得られる。次にこのＡＩ、Ａ２およびＡ３を用いて誤
り位置多項式σ（Ｚ）を求める。
きあがったビット列を排他的論理和回路を用いて変換し
て得られる。次にこのＡＩ、Ａ２およびＡ３を用いて誤
り位置多項式σ（Ｚ）を求める。
このσ（Ｚ）にαｔ（ｔ＝１、２・・・・・・、ｎ）を
代入し、σ（Ｚ）＝０となるｔの値が誤りの位置を示す
としてその位置のビットを反転して誤り訂正を行う。
代入し、σ（Ｚ）＝０となるｔの値が誤りの位置を示す
としてその位置のビットを反転して誤り訂正を行う。
以上が従来の復号装置で行なわれている復号動作である
。しかしながらこの方法ではσ（Ｚ）の各糸数を求める
のに比較的複雑な装置が必要であるし。
。しかしながらこの方法ではσ（Ｚ）の各糸数を求める
のに比較的複雑な装置が必要であるし。
時間がかかる。
従って本発明は比較的簡単な装置を用いて短時間に復号
することの出来る３誤り訂正符号復号方式を提供するこ
とを目的とする。
することの出来る３誤り訂正符号復号方式を提供するこ
とを目的とする。
次に本発明の復号装置の行う復号動作を説明する。
本発明の復号装置においても第１、第２および第３シン
ドロームＡｌ、Ａ２．Ａ３をまず計算することは従来の
方法と同じである。次に第１シンドロームＡＩと第２シ
ンドロームＡ２を用いてＡｔ′＋Ａ２を計算する。Ａ１
はＲＯＭテーブル等を用いた３乗器にＡｌを入力して計
算できる。ＡｔとＡ２との加算は排他的論理和回路を用
いて容菖に実現できる。さらにαｎ−ｔ、α３（ｎ−１
）およびα５（ｎ−１）をｔ＝１からｎまで順次発生す
る。αｎ−１はビット列１で、α３（ｎ−１）はビット
列２でα５（ｎ−１）はビット列３で表わす。
ドロームＡｌ、Ａ２．Ａ３をまず計算することは従来の
方法と同じである。次に第１シンドロームＡＩと第２シ
ンドロームＡ２を用いてＡｔ′＋Ａ２を計算する。Ａ１
はＲＯＭテーブル等を用いた３乗器にＡｌを入力して計
算できる。ＡｔとＡ２との加算は排他的論理和回路を用
いて容菖に実現できる。さらにαｎ−ｔ、α３（ｎ−１
）およびα５（ｎ−１）をｔ＝１からｎまで順次発生す
る。αｎ−１はビット列１で、α３（ｎ−１）はビット
列２でα５（ｎ−１）はビット列３で表わす。
αｎ−１の発生は例えば宮用他著符号理論（昭電堂）ｐ
．１１９にあるようにαの最小多項式に対応するフィー
ドバックシフトレジスタにαｎ＝１なる初期値を設定し
てｔ回シフトすればαｎ−１が得られる。
．１１９にあるようにαの最小多項式に対応するフィー
ドバックシフトレジスタにαｎ＝１なる初期値を設定し
てｔ回シフトすればαｎ−１が得られる。
α３（ｎ−１）はαｎ−１を例えばＲＯＭテーブルを用
いた３乗器に入力して得られる。α５（ｎ−ｔ）も同様
にαｎ−１を５乗器に入力して得らｈる。又は宮用他著
符号理論（昭晃堂）ｐ、１２０にあるような１回のシフ
トでα−３あるいはα−５を乗するシフトレジスタ回路
にα３ｎ＝α５ｎ＝１なる初期値を設定してｔ回シフト
すれば得られる。各ｔの値に対して第１シンドロームＡ
ｚ、第２シンドロームＡ２．第３シンドロームＡ３、α
ｎ−１、α３（ｎ−１）およびα５（ｎ−ｔ）を用いて
次式で定義されるＳｔ、Ｓ２およびｓ３を計算する。
いた３乗器に入力して得られる。α５（ｎ−ｔ）も同様
にαｎ−１を５乗器に入力して得らｈる。又は宮用他著
符号理論（昭晃堂）ｐ、１２０にあるような１回のシフ
トでα−３あるいはα−５を乗するシフトレジスタ回路
にα３ｎ＝α５ｎ＝１なる初期値を設定してｔ回シフト
すれば得られる。各ｔの値に対して第１シンドロームＡ
ｚ、第２シンドロームＡ２．第３シンドロームＡ３、α
ｎ−１、α３（ｎ−１）およびα５（ｎ−ｔ）を用いて
次式で定義されるＳｔ、Ｓ２およびｓ３を計算する。
Ｓ１＝Ａ１＋αｎ−１
Ｓ２＝Ａ２＋α３（ｎ−ｔ）
Ｓ３＝Ａ３＋α５（ｎ−ｔ）
Ｓ１はビット列４で、Ｓｚｕビット列５で、Ｓ３はビッ
ト列６で表わされる。Ａ１とαｎ−１の加算、Ａ２とα
３（ｎ−１）の加算、Ａ３とα５（ｎ−１）の加算は排
他的論理和回路により容易に実現される。次に次式で定
義されるＥＬ（ｔ）を計算する。
ト列６で表わされる。Ａ１とαｎ−１の加算、Ａ２とα
３（ｎ−１）の加算、Ａ３とα５（ｎ−１）の加算は排
他的論理和回路により容易に実現される。次に次式で定
義されるＥＬ（ｔ）を計算する。
ＥＬ（ｔ）＝ＳＩ十Ｓ２＋ＳＩＳ２＋ＳＩ５ａＥＬ（ｔ
）はＲＯＭテーブルで構成された６乗回路でＳＩからＳ
ｔを計算し、ＲＯＭテーブルで構成された２乗回路で８
２から８２を計算し、ＲＯＭテーブルで構成された３乗
および積回路でＳｌとＳ３からｓ１３Ｓ２を計算し、同
じ＜ＲＯＭテーブルで構成された積回路でＳ１とＳ３か
らＳ１Ｓ３を計算し、Ｓ６１とＳ２２とＳ１３とＳ１Ｓ
３を排他的論理和回路を用いて加算すれば得られる。前
記ＡＩ＋Ａ２が０であるならば。
）はＲＯＭテーブルで構成された６乗回路でＳＩからＳ
ｔを計算し、ＲＯＭテーブルで構成された２乗回路で８
２から８２を計算し、ＲＯＭテーブルで構成された３乗
および積回路でＳｌとＳ３からｓ１３Ｓ２を計算し、同
じ＜ＲＯＭテーブルで構成された積回路でＳ１とＳ３か
らＳ１Ｓ３を計算し、Ｓ６１とＳ２２とＳ１３とＳ１Ｓ
３を排他的論理和回路を用いて加算すれば得られる。前
記ＡＩ＋Ａ２が０であるならば。
各ｔ値に対してＳｌの値を調べＳ１＝０となるｔにおい
てＣ′中のｔ番目のビットα′が誤りであるとしてα；
を反転して誤りの訂正を行ない、Ａ１３＋Ａ２が０でな
いならば、各ｔの値に対して前記ＥＬ（ｔ）の値を調べ
ＥＬ（ｔ）＝０となるｔにおいてＣ′中のｔ番目のビッ
トα：が誤りであるとしてａ；を反転して誤りの訂正を
行なうのが本発明の復号装置が行なう復号動作である。
てＣ′中のｔ番目のビットα′が誤りであるとしてα；
を反転して誤りの訂正を行ない、Ａ１３＋Ａ２が０でな
いならば、各ｔの値に対して前記ＥＬ（ｔ）の値を調べ
ＥＬ（ｔ）＝０となるｔにおいてＣ′中のｔ番目のビッ
トα：が誤りであるとしてａ；を反転して誤りの訂正を
行なうのが本発明の復号装置が行なう復号動作である。
との復号動作では比較的簡単な動作が符号語の各ビット
に対して繰り返されるが、従来の復号方法における誤り
位置多項式を求めるような複雑な動作がないので装置が
簡単になる。
に対して繰り返されるが、従来の復号方法における誤り
位置多項式を求めるような複雑な動作がないので装置が
簡単になる。
本動作により誤りのビット数が３以下の時必ず正しい誤
り訂正が行々われることを以下に示す。
り訂正が行々われることを以下に示す。
まず誤りが１ビットもないとしよう。この時はＡＩ＝Ａ
２＝Ａ３＝０ 従って。
２＝Ａ３＝０ 従って。
Ａｌ＋Ａ２＝０
従って８１の値に従って誤り訂正が行なわれる。ところ
で Ｓｔ＝Ａｔ＋αｎ−１＝αｎ−１ はどんなｔの値に対しても０にならない。従ってＣ′中
のどんなビットに対しても反転はなされない。
で Ｓｔ＝Ａｔ＋αｎ−１＝αｎ−１ はどんなｔの値に対しても０にならない。従ってＣ′中
のどんなビットに対しても反転はなされない。
次にｉ番目のビットα、だけが誤りであるとしよう。こ
の時 ＡＩ＝αｎ−１ Ａ２＝α３（ｎ−１） 従って Ａｌ十Ａ２＝０ 従ってＳ１の値に従って誤り訂正が行なわれる。
の時 ＡＩ＝αｎ−１ Ａ２＝α３（ｎ−１） 従って Ａｌ十Ａ２＝０ 従ってＳ１の値に従って誤り訂正が行なわれる。
この時
Ｓ１＝Ａ１＋αｎ−１＝αｎ−１＋αｎ−１Ｓ１はｔ＝
ｉの時だけ０となりｒｔ＼ｉでは０とならない。従って
正しい誤り訂正が行なわれる。
ｉの時だけ０となりｒｔ＼ｉでは０とならない。従って
正しい誤り訂正が行なわれる。
次にｉ番目とｊ番目のビットつまりα′ｉとα′ｊが誤
りであるとしよう。この時 Ａｌ＝αｎ−１＋αｎ−１ Ａ２＝α３（ｎ−１）＋α３（ｎ−ｊ）Ａ１３＋Ａ２＝
α（ｎ−１）＋αｎ−１（αｎ−１＋αｎ−１）ｉ＼ｉ
であるからＡＩ＋Ａ２＼０ 従ってＥＬ（ｔ）の値に従って誤り訂正が行なわわる。
りであるとしよう。この時 Ａｌ＝αｎ−１＋αｎ−１ Ａ２＝α３（ｎ−１）＋α３（ｎ−ｊ）Ａ１３＋Ａ２＝
α（ｎ−１）＋αｎ−１（αｎ−１＋αｎ−１）ｉ＼ｉ
であるからＡＩ＋Ａ２＼０ 従ってＥＬ（ｔ）の値に従って誤り訂正が行なわわる。
この時。
ＥＬ（ｔ）はｔがｉ又はｊと一致した時だけ０となり。
ｔが他の値をとった時は０とならない。従って正しい誤
り訂正が行なわわる。
り訂正が行なわわる。
次にｔ番目とｊ番目と１番目のビット、すなわちα；と
α；とイが誤りであるとしよう。この時従ってＥＬ、（
ｔｌの値に従って誤り訂正が行々われる。
α；とイが誤りであるとしよう。この時従ってＥＬ、（
ｔｌの値に従って誤り訂正が行々われる。
この時
ＥＬ（ｔ）はｔがｉ又はｊ又はｌと一致した時だけ０と
なり、ｔが他の値をとった時は０とならない。
なり、ｔが他の値をとった時は０とならない。
従って正しい誤り訂正が行なわハる。以上よりわかるよ
う（Ｃ誤９ビツトの数が３以下であわば必ず正しい復号
が行なわれる。
う（Ｃ誤９ビツトの数が３以下であわば必ず正しい復号
が行なわれる。
次に本発明による復号装置を実施例の図面を参照しなが
ら説明する。これまで述べたように本発明の復号装置で
は、その復号手順においてガロア体の元を取り扱う。Ｇ
Ｆ（２′）の任意の元はαを原始元としてｌｔ、α、α
２．α、αの線形結合であらわすことができることはよ
〈知られている。
ら説明する。これまで述べたように本発明の復号装置で
は、その復号手順においてガロア体の元を取り扱う。Ｇ
Ｆ（２′）の任意の元はαを原始元としてｌｔ、α、α
２．α、αの線形結合であらわすことができることはよ
〈知られている。
本実施例においてはガロア体の元は上記線形結合の系数
列であるｍビットでめられすものとする。
列であるｍビットでめられすものとする。
もちろん全復号手順でガロア体の元のビット列によるあ
らわし方を統一する必要はなく、むしろ部分的に異なっ
たあらわし方を用いることで装置が若干簡単になること
もあり得るが、ここでは説明の簡単のため上記のあらわ
し方に統一するものとする。
らわし方を統一する必要はなく、むしろ部分的に異なっ
たあらわし方を用いることで装置が若干簡単になること
もあり得るが、ここでは説明の簡単のため上記のあらわ
し方に統一するものとする。
図１は本発明による実施例の構成を示すブロック図であ
る。図１において入力データαはデータバッファ１０１
と、第１シンドローム生成回路１０２、第２シンドロー
ム生成回路１０４．及び第３シンドロームの生成回路１
０６に加えられる。データバッファ１０１は、１符号語
長ｎビットに、シンドローム生成回路で生成されたシン
ドロームをシンドロームバッファに移すのに必要々時間
信号を保持するための１ビツトを加えた、合計ｎ＋１ビ
ットのシフトレジスタより構成される。第１シンドロー
ム生成回路１０２は、ＧＦ（２ｍ）の原始元αの最小多
項式に対応する常設のフィードバックシフトレジスタか
らなる。第２シンドローム生成回路１０４はα３の最小
多項式に対応する常設のフィードバツクシフトレジスタ
と排他的論理和回路より構成されるビット列変換回路か
らなる。第８シンドローム生成回路１０６はα５の最小
多項式に対応するフィードバックシフトレジスタと排他
的論理和回路より構成されるビット列変換回路からなる
。符号語の最後のビットがデータバッファ１０１に入力
し終った時、第１．第２．および第３シンドロームは各
シンドローム生成回路により生成されている。
る。図１において入力データαはデータバッファ１０１
と、第１シンドローム生成回路１０２、第２シンドロー
ム生成回路１０４．及び第３シンドロームの生成回路１
０６に加えられる。データバッファ１０１は、１符号語
長ｎビットに、シンドローム生成回路で生成されたシン
ドロームをシンドロームバッファに移すのに必要々時間
信号を保持するための１ビツトを加えた、合計ｎ＋１ビ
ットのシフトレジスタより構成される。第１シンドロー
ム生成回路１０２は、ＧＦ（２ｍ）の原始元αの最小多
項式に対応する常設のフィードバックシフトレジスタか
らなる。第２シンドローム生成回路１０４はα３の最小
多項式に対応する常設のフィードバツクシフトレジスタ
と排他的論理和回路より構成されるビット列変換回路か
らなる。第８シンドローム生成回路１０６はα５の最小
多項式に対応するフィードバックシフトレジスタと排他
的論理和回路より構成されるビット列変換回路からなる
。符号語の最後のビットがデータバッファ１０１に入力
し終った時、第１．第２．および第３シンドロームは各
シンドローム生成回路により生成されている。
生成された第１．第２．および第３シンドロームは次の
、符号語がシンドローム生成回路に入力されると破壊さ
れるので、その前に各々第１、第２、および第８シンド
ロームバツフアに移される。第１シンドローム（Ａｌ）
と第２シンドローム（Ａ２）は訂正条件判別回路１０８
に入力され、訂正条件判別回路１０８はＡ、３＋Ａ２が
０か否がの判別を行って。
、符号語がシンドローム生成回路に入力されると破壊さ
れるので、その前に各々第１、第２、および第８シンド
ロームバツフアに移される。第１シンドローム（Ａｌ）
と第２シンドローム（Ａ２）は訂正条件判別回路１０８
に入力され、訂正条件判別回路１０８はＡ、３＋Ａ２が
０か否がの判別を行って。
ＡＩ＋Ａ２が０の時は０を、そうでない時は１を出力し
て選択回路１１７に与える。訂正条件判別回路はＲＯＭ
、テーブルで構成された８乗回路と排他的論理和で構成
された加算回路と加算結果が全ビット０かどうかを判別
する論理和回路よりなる。データバッファ１０１に格納
された符号語は先頭のビットから１ビットづつ出力さね
、誤り訂正回路１１８に入力される。第ｔ番目（ｔ＝１
，２．・・・ｎ）のビットがデータバッファ１０１より
出力され誤り訂正回路１１８に入力さする時、αのベキ
発生回路１１０はαをあらわすｍビットのビット列であ
るビット列１を発生し、α３のベキ発生回路１１２はα
３（ｎ−１）をあらわすｍビットのビット列であるビッ
ト列２を発生し、又α５のベキ発生回路１１４はα５（
ｎ−１）をあらわすビット列３を発生する。αのベキ発
生回路１１０はαの最小多項式に対応するフィードバッ
クシフトレジスタからなる。α３のベキ発生回路１１２
はα３最小多項式に対応するフィードバックシフトレジ
スタからなる。α５のベキ発生回路１１４はα２の最小
多項式に対応するフィードバックシフトレジスタからな
る。ビット列１と第１シンドロームは排他的論理和回路
１０９によシ対応するビット毎に排他的論理和をとられ
ることで加算され。
て選択回路１１７に与える。訂正条件判別回路はＲＯＭ
、テーブルで構成された８乗回路と排他的論理和で構成
された加算回路と加算結果が全ビット０かどうかを判別
する論理和回路よりなる。データバッファ１０１に格納
された符号語は先頭のビットから１ビットづつ出力さね
、誤り訂正回路１１８に入力される。第ｔ番目（ｔ＝１
，２．・・・ｎ）のビットがデータバッファ１０１より
出力され誤り訂正回路１１８に入力さする時、αのベキ
発生回路１１０はαをあらわすｍビットのビット列であ
るビット列１を発生し、α３のベキ発生回路１１２はα
３（ｎ−１）をあらわすｍビットのビット列であるビッ
ト列２を発生し、又α５のベキ発生回路１１４はα５（
ｎ−１）をあらわすビット列３を発生する。αのベキ発
生回路１１０はαの最小多項式に対応するフィードバッ
クシフトレジスタからなる。α３のベキ発生回路１１２
はα３最小多項式に対応するフィードバックシフトレジ
スタからなる。α５のベキ発生回路１１４はα２の最小
多項式に対応するフィードバックシフトレジスタからな
る。ビット列１と第１シンドロームは排他的論理和回路
１０９によシ対応するビット毎に排他的論理和をとられ
ることで加算され。
Ｓ１＝Ａｔ＋αｎ−１をあらわすビット列４が生成され
る。
る。
同様にビット列２と第２シンドロームは排他的論理和回
路１１１を用いて加算されＳ２＝Ａ２＋α３（＋ａ、−
１）′をあらわすビット列５が生成される。さらにビッ
ト列３と第３シンドロームは排他的論理和回路１１８を
用いて加算されて、Ｓ３＝Ａ３＋α５（ｎ−１）をあら
わすビット列６が生成される。ビット列４は第１誤り検
出回路１１５と第２誤り検出回路１１６に供給さ名、ビ
ット列５とビット列６は第２誤り検出回路に供給される
。第１誤り検出回路１１５はＳ１が０の時はｌを、そう
でない時は０を出力して選択回路１１７に与えるもので
あり、論理和回路と否定回路で構成される。第２誤り検
出回路１１６はＳｌをあらわすビット列４．Ｓ２をあら
わすビット列５．およびＳｓをあらわすビット列６を入
力してＳ１＋Ｓ２十５１３Ｓ２＋ＳｔＳｓが０の時はｌ
を、そうでない時は０を出力して選択回路１１７に与え
るものである。
路１１１を用いて加算されＳ２＝Ａ２＋α３（＋ａ、−
１）′をあらわすビット列５が生成される。さらにビッ
ト列３と第３シンドロームは排他的論理和回路１１８を
用いて加算されて、Ｓ３＝Ａ３＋α５（ｎ−１）をあら
わすビット列６が生成される。ビット列４は第１誤り検
出回路１１５と第２誤り検出回路１１６に供給さ名、ビ
ット列５とビット列６は第２誤り検出回路に供給される
。第１誤り検出回路１１５はＳ１が０の時はｌを、そう
でない時は０を出力して選択回路１１７に与えるもので
あり、論理和回路と否定回路で構成される。第２誤り検
出回路１１６はＳｌをあらわすビット列４．Ｓ２をあら
わすビット列５．およびＳｓをあらわすビット列６を入
力してＳ１＋Ｓ２十５１３Ｓ２＋ＳｔＳｓが０の時はｌ
を、そうでない時は０を出力して選択回路１１７に与え
るものである。
図２は第２誤り検出回路１１６の構成例を示す。
図２においてビット列４は６東回路２０１．８乗及び積
回路２０３、及び積回路２０４に供給さり、又ビット列
５は２東回路２０２と８乗及び積回路２０８に供給され
、さらにビット列６は積回路２０４に供給される。６東
回路２０１はＳ、Ｆをあらわすビット列７を生成する。
回路２０３、及び積回路２０４に供給さり、又ビット列
５は２東回路２０２と８乗及び積回路２０８に供給され
、さらにビット列６は積回路２０４に供給される。６東
回路２０１はＳ、Ｆをあらわすビット列７を生成する。
２東回路２０２はＳ２をあらわすビット列８を生成する
。８乗及び積回路２０３は５１３Ｓ２をあらわすビット
列９を生成する。積回路２０４は５ＩＳ３をあらわすビ
ット列１０を生成する。６乗回路２０１．２乗回路２０
２．８乗及び積回路２０３．及び積回路２０４は全てＲ
ＯＭテーブルで構成される。
。８乗及び積回路２０３は５１３Ｓ２をあらわすビット
列９を生成する。積回路２０４は５ＩＳ３をあらわすビ
ット列１０を生成する。６乗回路２０１．２乗回路２０
２．８乗及び積回路２０３．及び積回路２０４は全てＲ
ＯＭテーブルで構成される。
排他的論理和回路２０５はビット列７とビット列８の対
応するビット毎に排他的論理和をとることで加算を行い
ｓ、６＋Ｓ２２をあらわすビット列１１を作成する。排
他的論理和回路２０６はビット列９とビット列１０の対
応するビット毎に排他的論理和をとることで加算を行い
５１３Ｓ２＋ＳｔＳｓをあらわすビット列１２を作成す
る。排他的論理和回路２０７はビット列１１とビット列
１２の対応するビット毎に排他的論理和をとることで加
算を行いＳ′ｌ＋Ｓ２＋５１３Ｓｚ＋５ｔＳ３をあらわ
すビット列１３を作成する。論理和回路２０８はビット
列１８の全ビットの論理和をとることでＳｌ中Ｓ２＋５
ＩＳ２＋Ｓ！Ｓ３が０の場合は０を出力し、他の場合は
１を出力する。否定回路２０９は論理和回路２０８の出
力の極性を反転し、Ｓｔ＋Ｓ２＋ＳｔＳｚ”５ｔＳ３が
０の場合１、他の場合は０を出力する。図１にもどって
選択回路１１７は論理積回路、論理和回路及び否定回路
より構成され、訂正条件判別回路１０８がＡＨ３＋Ａ２
＝Ｏであると判定して０を出力している場合には第１訝
り検出回路１１５の出力をその出力とじ、訂正条件判別
回路１０８がＡＨ３＋Ａ２＼０であると判定して１４出
力している場合には第２誤り検出回路１１６の出力をそ
の出力とする。誤り訂正回路１１８は排他的論理和回路
であり、データッファ１０１の出力である第を番目のビ
ットα：と選択回路１１７の出方との排他的論理和をと
る。従って訂正条件判別回路１０８の出力が０でかつ第
１誤り検出回路１１５の出力が１である場合、又は訂正
条件判別回路１０８の出力が１でかつ第２誤り検出回路
１１６の出力が１である場合に誤り訂正回路１１８の出
力はデータバッファ１０１の出力である第を番目のビッ
トα；を反転したものとなし、そうでない場合は誤り訂
正回路１１８の出力はデータバッファ１０１の出力α；
そのままである。誤り訂正回路１１８の出力Ｕは出力デ
ータとなる。
応するビット毎に排他的論理和をとることで加算を行い
ｓ、６＋Ｓ２２をあらわすビット列１１を作成する。排
他的論理和回路２０６はビット列９とビット列１０の対
応するビット毎に排他的論理和をとることで加算を行い
５１３Ｓ２＋ＳｔＳｓをあらわすビット列１２を作成す
る。排他的論理和回路２０７はビット列１１とビット列
１２の対応するビット毎に排他的論理和をとることで加
算を行いＳ′ｌ＋Ｓ２＋５１３Ｓｚ＋５ｔＳ３をあらわ
すビット列１３を作成する。論理和回路２０８はビット
列１８の全ビットの論理和をとることでＳｌ中Ｓ２＋５
ＩＳ２＋Ｓ！Ｓ３が０の場合は０を出力し、他の場合は
１を出力する。否定回路２０９は論理和回路２０８の出
力の極性を反転し、Ｓｔ＋Ｓ２＋ＳｔＳｚ”５ｔＳ３が
０の場合１、他の場合は０を出力する。図１にもどって
選択回路１１７は論理積回路、論理和回路及び否定回路
より構成され、訂正条件判別回路１０８がＡＨ３＋Ａ２
＝Ｏであると判定して０を出力している場合には第１訝
り検出回路１１５の出力をその出力とじ、訂正条件判別
回路１０８がＡＨ３＋Ａ２＼０であると判定して１４出
力している場合には第２誤り検出回路１１６の出力をそ
の出力とする。誤り訂正回路１１８は排他的論理和回路
であり、データッファ１０１の出力である第を番目のビ
ットα：と選択回路１１７の出方との排他的論理和をと
る。従って訂正条件判別回路１０８の出力が０でかつ第
１誤り検出回路１１５の出力が１である場合、又は訂正
条件判別回路１０８の出力が１でかつ第２誤り検出回路
１１６の出力が１である場合に誤り訂正回路１１８の出
力はデータバッファ１０１の出力である第を番目のビッ
トα；を反転したものとなし、そうでない場合は誤り訂
正回路１１８の出力はデータバッファ１０１の出力α；
そのままである。誤り訂正回路１１８の出力Ｕは出力デ
ータとなる。
図１は本発明による復号装置の実施例の構成図であり１
図２は図１の中の第２誤り検出回路１１６の構成例であ
る。図において１０１はデータバッファ。 １０２は第１シンドローム生成回路、１０８は第１シン
ドロームバッファ、１０４は第２シンドローム生成回路
、１０５は第２シンドロームバッファ、１０６は第３シ
ンドローム生成回路、１０７は第３シンドロームバッフ
ァ、１０８は訂正条件判別回路、１０９は排他的論理和
回路、１１０はαのベキ発生回路。 １１１は排他的論理和回路、１１２はαのベキ発生回路
、１１３は排他的論理和回路、１１４はα５のベキ発生
回路、１１５は第１誤り検出回路、１１６は第２誤り検
出回路、１１７は選択回路、１１８は誤り訂正回路、２
０１は６乗回路、２０２は２乗回路、２０３は８乗及び
積回路、２０４は積回路、２０５は排他的論理和回路、
２０６は排他的論理和回路、２０７は排他的論理和回路
、２０８は論理和回路、２０９は否定回路。 ａは入力データ、、ｂはｆＸｌシンドローム、Ｃは第２
シンドローム、ｄは第８シンドローム、εはビット列１
．／はビット列ＬＱはビット列８．ｈはビット列′ｅＦ
はビット列５．ｒはビット列６、νはビット列７、ｚは
ビット列８．νはビット列９．８αはビット列１０．ｃ
ｃはビット列１２．ｄｄはビット列１８．ｆは復号出力
である。 特許出願人 国際電信電話株式会社 特許出願代理人 弁理士山本恵−
図２は図１の中の第２誤り検出回路１１６の構成例であ
る。図において１０１はデータバッファ。 １０２は第１シンドローム生成回路、１０８は第１シン
ドロームバッファ、１０４は第２シンドローム生成回路
、１０５は第２シンドロームバッファ、１０６は第３シ
ンドローム生成回路、１０７は第３シンドロームバッフ
ァ、１０８は訂正条件判別回路、１０９は排他的論理和
回路、１１０はαのベキ発生回路。 １１１は排他的論理和回路、１１２はαのベキ発生回路
、１１３は排他的論理和回路、１１４はα５のベキ発生
回路、１１５は第１誤り検出回路、１１６は第２誤り検
出回路、１１７は選択回路、１１８は誤り訂正回路、２
０１は６乗回路、２０２は２乗回路、２０３は８乗及び
積回路、２０４は積回路、２０５は排他的論理和回路、
２０６は排他的論理和回路、２０７は排他的論理和回路
、２０８は論理和回路、２０９は否定回路。 ａは入力データ、、ｂはｆＸｌシンドローム、Ｃは第２
シンドローム、ｄは第８シンドローム、εはビット列１
．／はビット列ＬＱはビット列８．ｈはビット列′ｅＦ
はビット列５．ｒはビット列６、νはビット列７、ｚは
ビット列８．νはビット列９．８αはビット列１０．ｃ
ｃはビット列１２．ｄｄはビット列１８．ｆは復号出力
である。 特許出願人 国際電信電話株式会社 特許出願代理人 弁理士山本恵−
Claims (1)
- 【特許請求の範囲】 ３誤り訂正ＢＣＨ符号の符号語Ｃに誤りベクトルｅが加
算されて出来た入力系列Ｃ′＝（α活、α２．α１゜・
・・α−）、（外は符号長ｎ＝２、ｒｎは自然数）を復
号装置に入力して誤まり訂正を行なう復号方式において
、前記入力系列Ｃ′から第１シンドロームＡＩ、Ｋ２シ
ンドロームＡ２．及び第３シンドロームＡ３； をシフトレジスタを用いて求め２次いでＡＩ＋Ａ２＝０
であわば （αは２′個の要素よりなるガロア体ＧＦ（２”）の原
始元、ｔは誤りかどうかを判定されるビットを指定する
番号でｎを越えない自然数）をＯとするｔの値があれば
それに対応する入力ビットαｔを誤りとして反転して他
の入力ビットはそのまま出力し、又 として ＥＬ（ｔ）＝Ｓｔ＋Ｓｚ＋ＳｔＳ２＋５ＩＳ３＝０を与
える３個までのｔの値（ｔｘ、′２＋′３）に対応する
入力ビット（α′１１．α′ｔ２．αｔ３）を反転し、
他の入力ビットはそのまま出力することにより、３個ま
での誤りを訂正することを特徴とする３誤り訂正符号復
号方式。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56113617A JPS5815352A (ja) | 1981-07-22 | 1981-07-22 | ３誤り訂正符号復号方式 |
| GB8204214A GB2093238B (en) | 1981-02-18 | 1982-02-12 | Error correcting system for simultaneous errors in a code |
| US06/349,319 US4468769A (en) | 1981-02-18 | 1982-02-16 | Error correcting system for correcting two or three simultaneous errors in a code |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56113617A JPS5815352A (ja) | 1981-07-22 | 1981-07-22 | ３誤り訂正符号復号方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS5815352A true JPS5815352A (ja) | 1983-01-28 |
| JPS6135731B2 JPS6135731B2 (ja) | 1986-08-14 |
Family
ID=14616746
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP56113617A Granted JPS5815352A (ja) | 1981-02-18 | 1981-07-22 | ３誤り訂正符号復号方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS5815352A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS62137924A (ja) * | 1985-12-12 | 1987-06-20 | Nec Home Electronics Ltd | リ−ドソロモン符号・復号方式の誤り位置決定回路 |
| JPH0239728A (ja) * | 1988-07-29 | 1990-02-08 | Canon Inc | 誤り訂正装置 |
| JPH03179923A (ja) * | 1989-12-08 | 1991-08-05 | Matsushita Electric Ind Co Ltd | Ｂｃｈ符号の復号方法および装置 |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0593739U (ja) * | 1992-05-28 | 1993-12-21 | エヌオーケー株式会社 | ワークの供給装置 |
-
1981
- 1981-07-22 JP JP56113617A patent/JPS5815352A/ja active Granted
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS62137924A (ja) * | 1985-12-12 | 1987-06-20 | Nec Home Electronics Ltd | リ−ドソロモン符号・復号方式の誤り位置決定回路 |
| JPH0239728A (ja) * | 1988-07-29 | 1990-02-08 | Canon Inc | 誤り訂正装置 |
| JPH03179923A (ja) * | 1989-12-08 | 1991-08-05 | Matsushita Electric Ind Co Ltd | Ｂｃｈ符号の復号方法および装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6135731B2 (ja) | 1986-08-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0114938B1 (en) | On-the-fly multibyte error correction | |
| JPS6327734B2 (ja) | ||
| JPH0452556B2 (ja) | ||
| US5748652A (en) | Apparatus for detecting and correcting cyclic redundancy check errors | |
| EP0753942A2 (en) | Word-wise processing for reed-solomon codes | |
| JPH0728227B2 (ja) | Ｂｃｈ符号の復号装置 | |
| CA1213673A (en) | Burst error correction using cyclic block codes | |
| JP2001524274A (ja) | 短縮ファイア符号エラートラッピング復号方法および装置 | |
| JPS5815352A (ja) | ３誤り訂正符号復号方式 | |
| JPH05183447A (ja) | 改善された誤まり検出符号化システム | |
| JP3248098B2 (ja) | シンドローム計算装置 | |
| JPH0241032A (ja) | 誤り訂正装置 | |
| Umanesan et al. | Parallel decoding cyclic burst error correcting codes | |
| JPH0361210B2 (ja) | ||
| JPS6150416B2 (ja) | ||
| KR0137354B1 (ko) | 무선 데이타 통신에서의 에러검출 및 정정방법 | |
| JP2002026741A (ja) | 誤り訂正装置、誤り訂正方法及び記録媒体 | |
| JP2534563B2 (ja) | 許容誤り逐次訂正回路 | |
| JPH01160118A (ja) | Ｂｃｈ復号器 | |
| KR100192792B1 (ko) | 리드 솔로몬 복호기의 다항식 평가 장치 | |
| KR890007345Y1 (ko) | 디지탈 오디오에서의 리드-솔로몬 엔코오더의 코오드 워드 발생회로 | |
| JPH04297164A (ja) | パケット受信機の誤り訂正回路 | |
| JPH0373902B2 (ja) | ||
| JPH01289322A (ja) | 符合誤り訂正装置 | |
| JPH0746778B2 (ja) | 誤り訂正方式および誤り訂正復号器 |