JPS6135731B2

JPS6135731B2 -

Info

Publication number: JPS6135731B2
Application number: JP56113617A
Authority: JP
Inventors: Keiichiro Koga
Original assignee: Kokusai Denshin Denwa KK
Current assignee: KDDI Corp
Priority date: 1981-07-22
Filing date: 1981-07-22
Publication date: 1986-08-14
Also published as: JPS5815352A

Description

【発明の詳細な説明】本発明はデイジタルデータの伝送や蓄積時に生
じるビツト誤りを自動的に検出し訂正する方式に
関する。

データ伝送や蓄積時に生じる誤りを自動的に訂
正する方法として誤り訂正符号化技術が用いられ
ている。これに使われる誤り訂正符号には各種あ
るが、その中でBCH（ボーゼ・チヨドーリ・ホ
ツキンジエム）符号は符号長や誤り訂正能力の選
択の自由度が大きく、また付加された検査ビツト
数のかわりに誤り訂正能力が優れた符号として知
られている。本発明はBCH符号の内、一符号語
に３つ以下のビツト誤りがある場合にその誤りを
訂正できる符号、すなわち３誤り訂正BCH符号
を用いて符号化された信号中に生じたビツト誤り
を訂正する装置すなわち復号装置に関する。

ここで３誤り訂正BCH符号について簡単に説
明しておく。

３誤り訂正BCH符号においては符号語Ｃはｋ
個の情報ビツト（a₁，a₂，…，ａ_k）とこれらの
情報ビツトから計算されたｑ個の検査ビツト（ａ
_k+1，ａ_k+2，…，ａ_k+q）より構成される。つまり
符号誤〓は〓＝（a₁，a₂，…，ａ_k，ａ_k+1，…，ａ_k+q）となる。

但しｋ、はｍを４以上の整数としてｋ＝２^m−3m−１ｑ＝3m となるよう決定される。以後符号長ｋ＝ｑ＝２^m
−１をｎで表わす。すなわち符号語〓は〓＝（a₁，a₂，……，ａ_o-1，ａ_o）となる。検査ビツトは符号語がＨ〓^T＝０を満足するよう決定される。ここで〓^Tは〓の転
置ベクトルである。Ｈはパリテイ検査行列でGF
（２^m）の原始元αを用いてと表わされる。Ｈの各要素α^w（ｗ＝０，１，
…，ｎ−１）はｍ要素の列ベクトルで表わされ
る。

ここで〓に誤りが生じて〓′となつたとする。

〓′＝（a′₁，a′₂，……，a′_o-1，a′_o）〓′は〓と誤りベクトルｅにより次のように表わ
される。

〓′＝〓＋ｅ但し〓は〓′の誤りビツトの位置では１、他の位
置では０である要素からなるベクトルである。

〓＝（e₁，e₂，……ｅ_o-1，ｅ_o）〓′が与えられた時に、もとの〓を再現するの
が復号であり、本発明はそれを実現する新しい装
置を与えるものである。

従来の３誤り訂正符号の復号は、通常、以下に
述べる方法で行なわれている。

まず次式で定義される第１、第２および第３シ
ンドロームすなわちA₁，A₂、およびA₃を計算す
る。

シンドロームA₁，A₂およびA₃は例えばF.J.
MacWilliams，N.J.A.Sloane著“The Theory of
Error―Correcting Codes，Part ”（North
Holland Publishing Company）pp.270―272に
あるようにして生成される。つまり第１シンドロ
ームA₁はαの最小多項式に対応するフイードバ
ツクシフトレジスタC′のビツトをa′₁からa′_oまで
入力し、a′_oが入力された時点でシフトレジスタ
中に完成する。第２シンドロームA₂はα^３の最
小多項式に対応するフイードバツクシフトレジス
タにC′を入力し、最後のビツトが入力された時
点でシフトレジスタ中にできあがつたビツト列を
排他的論理和回路を用いて変換して得られる。第
３シンドロームA₃も、同様に、α^５の最小多項
式に対応するフイードバツクシフトレジスタ
C′を入力し、最後のビツトが入力された時点で
シフトレジスタ中にできあがつたビツト列を排他
的論理和回路を用いて変換して得られる。次にこ
のA₁，A₂およびA₃を用いて誤り位置多項式σ
（Ｚ）を求める。

σ（Ｚ）＝１＋A₁Z （A₁ ³＋A₂＝０の場合）このσ（Ｚ）にα^t（ｔ＝１，２，……，ｎ）を
代入し、σ（Ｚ）＝０となるｔの値が誤りの位置
を示すとしてその位置のビツトを反転して誤り訂
正を行う。以上が従来の復号装置で行なわれてい
る復号動作である。しかしながらこの方法ではσ
（Ｚ）の各系数を求めるのに比較的複雑な装置が
必要であるし、時間がかかる。

従つて本発明は比較的簡単な装置を用いて短時
間に復号することの出来る３誤り訂正符号復号方
式を提供することを目的とする。

次に本発明の復号装置の行う復号動作を説明す
る。

本発明の復号装置においても第１、第２および
第３シンドロームA₁，A₂，A₃をまず計算するこ
とは従来の方法と同じである。次に第１シンドロ
ームA₁と第２シンドロームA₂を用いてA₁ ³＋A₂を
計算する。A₁ ³はROMテーブル等を用いた３乗器
にA₁を入力して計算できる。A₁ ³とA₂との加算は
排他的論理和回路を用いて容易に実現できる。さ
らにα^n-t，α^3(n-t)およびα^5(n-t)をｔ＝１から
ｎまで順次発生する。α^n-tはビツト列１で、α³
^{（ｎ−ｔ）}はビツト例２でα^5(n-t)はビツト列３で表わ
す。α^n-tの発生は例えば宮川他著符号理論（昭
晃堂）p.119にあるようにαの最小多項式に対応
するフイードバツクシフトレジスタにαⁿ＝１な
る初期値を設定してｔ回シフトすればα^n-tが得
られる。α^3(n-t)はα^n-tを例えばROMテーブル
を用いた３乗器に入力して得られる。α^5(n-t)も
同様にα^n-tを５乗器に入力して得られる。又は
宮川他著符号理論（昭晃堂）p.120にあるような
１回のシフトでα^-3あるいはα^-5を乗ずるシフト
レジスタ回路にα³ⁿ＝α⁵ⁿ＝１なる初期値を設定
してｔ回シフトすれば得られる。各ｔの値に対し
て第１シンドロームA₁、第２シンドロームA₂、
第３シンドロームA₃、α^n-t，α^3(n-t)，およびα
^5(n-t)を用いて次式で定義されるS₁，S₂およびS₃
を計算する。

S₁＝A₁＋α^n-t S₂＝A₂＋α^3(n-t) S₃＝A₃＋α^5(n-t) S₁はビツト列４で、S₂はビツト列５で、S₃はビツ
ト列６で表わされる。A₁とα^n-tの加算、A₂とα³
^{（ｎ−ｔ）}の加算、A₃とα^5(n-t)の加算は排他的論理和
回路により容易に実現される。次に次式で定義さ
れるEL（ｔ）を計算する。

EL（ｔ）＝S₁ ⁶＋S₂ ²＋S₁ ³S₂＋S₁＋S₃ EL（ｔ）はROMテーブルで構成された６乗回路
でS₁からS₁ ⁶を計算し、ROMテーブルで構成され
た２乗回路でS₂からS₂ ²を計算し、ROMテーブル
で構成された３乗および積回路でS₁とS₃から
S₁ ³S₂を計算し、同じくROMテーブルで構成され
た積回路でS₁とS₃からS₁S₃を計算し、S₁ ⁶とS₂ ²と
S₁ ³S₂とS₁S₃を排他的論理和回路を用いて加算す
れば得られる。前記A₁ ³＋A₂が０であるならば、
各ｔの値に対してS₁の値を調べS₁＝０となるｔに
おいてC′中のｔ番目のビツトa′_tにおいてC′中の
ｔ番目のビツトa′_tが誤りであるとしてa′_tを反転
して誤りの訂正を行ない、A₁ ³＋A₂が０でないな
らば、各ｔの値に対して前記EL（ｔ）の値を調
べEL（ｔ）＝０となるｔにおいてC′中のｔ番目の
ビツトa′_tが誤りであるとしてa′_tを反転して誤り
の訂正を行なうのが本発明の復号装置が行なう復
号動作である。この復号動作では比較的簡単な動
作が符号語の各ビツトに対して繰り返されるが、
従来の復号方法における誤り位置多項式を求める
ような複雑な動作がないので装置が簡単になる。

本動作により誤りのビツト数が３以下の時は必
ず正しい誤り訂正が行なわれることを以下に示
す。

まず誤りが１ビツトもないとしよう。この時は A₁＝A₂＝A₃＝０従つて、 A₁ ³＋A₂＝０従つてS₁の値に従つて誤り訂正が行なわれる。と
ころで、 S₁＝A₁＋α^n-t＝α^n-t はどんなｔの値に対しても０にならない。従つて
C′の中のどんなビツトに対しても反転はなされ
ない。

次にｉ番目のビツトa′_iだけが誤りであるとし
よう。この時 A₁＝α^n-i A₂＝α^3(n-i) 従つて A₁ ³＋A₂＝０従つてS₁の値に従つて誤り訂正が行なわれる。

この時 S₁＝A₁＋α^n-t＝α^n-iα^n-t S₁はｔ＝ｉの時だけ０となり、ｔ≠ｉでは０とな
らない。従つて正しい誤り訂正が行なわれる。

次にｉ番目とｊ番目のビツトつまりa′_iとa′_jが
誤りであるとしよう。この時 A₁＝α^n-i＋α^n-j A₂＝α^3(n-i)＋α^3(n-j) A₃＝α^5(n-i)＋α^5(n-j) A₁ ³＋A₂＝α^(n-i)・α^n-j（α^n-i＋α^n-j）ｉ≠ｊであるからA₁ ³＋A₂≠０従つてEL（ｔ）の値に従つて誤り訂正が行なわ
れる。この時、 S₁＝A₁＋α^n-t＝α^n-iα^n-j＋α^n-t S₂＝A₂＋α^3(n-t) ＝α^3(n-i)＋α^3(n-j)＋α^3(n-t) S₃＝A₃＋α^5(n-t) ＝α^5(n-i)＋α^5(n-j)＋α^5(n-t) EL（ｔ）＝S₁ ⁶＋S₂ ²＋S₁ ³S₂＋S₁S₃ ＝α^n-iα^n-jα^n-t（α^n-i＋α^n-j）（α^n-t＋α^n-i）（α^n-t＋α^n-j） EL（ｔ）はｔがｉ又はｊと一致した時だけ０と
なり、ｔが他の値をとつた時は０とならない。従
つて正しい誤り訂正が行なわれる。

次にｉ番目とｊ番目とｌ番目のビツト、すなわ
ちa′_iとa′_jとa′_lが誤りであるとしよう。この時 A₁＝α^n-i＋α^n-j＋α^n-l A₂＝α^3(n-i)＋α^3(n-j)＋α^3(n-l) A₃＝α^5(n-i)＋α^5(n-j)＋α^5(n-l) A₁ ³＋A₂＝（α^n-i＋α^n-j）（α^n-j＋α^n-l）（α^n-l＋α^n-i）ｉ≠ｊ、ｊ≠ｌ、ｌ≠ｉであるからA₁ ³＋A₂≠０
従つてEL（ｔ）の値に従つて誤り訂正が行なわ
れる。

この時 S₁＝A₁＋α^n-t＝α^n-i ＋α^n-j＋α^n-l＋α^n-t S₂＝A₂＋α^3(n-t)＝α^3(n-i) ＋α^3(n-j)＋α^3(n-l)＋α^3(n-t) S₃＝A₃＋α^5(n-t)＝α^5(n-i) ＋α^5(n-j)＋α^5(n-l)＋α^5(n-t) EL（ｔ）＝S₁ ⁶＋S₂ ²＋S₁ ³S₂＋S₁S₃ ＝（α^n-i＋α^n-j）（α^n-j＋α^n-l）（α^n-l＋α^n-i）（α^n-t＋α^n-i）（α^n-t＋α^n-j）（α^n-t＋α^n-l） EL（ｔ）はｔがｉ又はｊ又はｌと一致した時だ
け０となり、ｔが他の値をとつた時は０とならな
い。従つて正しい誤り訂正が行なわれる。以上よ
りわかるように誤りビツトの数が３以下であれば
必ず正しい復号が行なわれる。

次に本発明による復号装置を実施例の図面を参
照しながら説明する。これまで述べたように本発
明の復号装置では、その復号手順においてガロア
体の元を取り扱う。GF（２^m）の任意の元はαを
原始元として、１，α，α^２，α^m-2，α^m-1の線
形結合であらわすことができることはよく知られ
ている。本実施例においてはガロア体の元は上記
線形結合の系数列であるｍビツトであらわすもの
とする。もちろん全復号手順でガロア体の元のビ
ツト列によるあらわし方を統一する必要はなく、
むしろ部分的に異なつたあらわし方を用いること
で装置が若干簡単になることもあり得るが、ここ
では説明の簡単のため上記のあらわし方に統一す
るものとする。

図１は本発明による実施例の構成を示すブロツ
ク図である。図１において入力データαはデータ
バツフア１０１と、第１シンドローム生成回路１
０２、第２シンドローム生成回路１０４、及び第
３シンドロームの生成回路１０６に加えられる。
データバツフア１０１は、１符号語長ｎビツト
に、シンドローム生成回路で生成されたシンドロ
ームをシンドロームバツフアに移すのに必要な時
間信号を保持するための１ビツトを加えた、合計
ｎ＋１ビツトのシフトレジスタより構成される。
第１シンドローム生成回路１０２は、GF（２_n）
の原始元αの最小多項式に対応するｍ段のフイー
ドバツクシフトレジスタからなる。第２シンドロ
ーム生成回路１０４はα^３の最小多項式に対応す
るｍ段のフイードバツクシフトレジスタと排他的
論理和回路より構成されるビツト列変換回路から
なる。第３シンドローム生成回路１０６はα^５の
最小多項式に対応するフイードバツクシフトレジ
スタと排他的論理和回路より構成されるビツト列
変換回路からなる。符号語の最後のビツトがデー
タバツフア１０１に入力し終つた時、第１、第
２、および第３シンドロームは各シンドローム生
成回路により生成されている。生成された第１、
第２、および第３シンドロームは次の符号語がシ
ンドローム生成回路に入力されると破壊されるの
で、その前に各々第１、第２、および第３シンド
ロームバツフアに移される。第１シンドローム
（A₁）と第２シンドローム（A₂）は訂正条件判別回
路１０８に入力され、訂正条件判別回路１０８は
A₁ ³＋A₂が０か否かの判別を行つて、A₁ ³＋A₂が
０の時は０を、そうでない時は１を出力して選択
回路１１７に与える。訂正条件判別回路はROM
テーブルで構成された３乗回路と排他的論理和で
構成された加算回路と加算結果が全ビツト０かど
うかを判別する論理和回路よりなる。データバツ
フア１０１に格納された符号語は先頭のビツトか
ら１ビツトづつ出力され、誤り訂正回路１１８に
入力される。第ｔ番目（ｔ＝１，２，…ｎ）のビ
ツトがデータバツフア１０１より出力され誤り訂
正回路１１８に入力される時、αのベキ発生回路
１１０はα^n-tをあらわすｍビツト列であるビツ
ト列１を発生し、α^３のベキ発生回路１１２はα
^3(n-t)をあらわすｍビツトのビツト列であるビツ
ト列２を発生し、又α^５のベキ発生回路１１４は
α^5(n-t)をあらわすビツト列３を発生する。αの
ベキ発生回路１１０はαの最小多項式に対応する
フイードバツクシフトレジスタからなる。α^３の
ベキ発生回路１１２はα^３の最小多項式に対応す
るフイードバツクシフトレジスタからなる。α^５
のベキ発生回路１１４はα^５の最小多項式に対応
するフイードバツクシフトレジスタからなる。ビ
ツト列１と第１シンドロームは排他的論理和回路
１０９により対応するビツト毎に排他的論理和を
とられることで加算され、S₁＝A₁＋α^n-tをあら
わすビツト列４が生成される。同様にビツト列２
と第２シンドロームは排他的論理和回路１１１を
用いて加算されS₂＝A₂＋α^3(n-t)をあらわすビツ
ト列５が生成される。さらにビツト列３と第３シ
ンドロームは排他的論理和回路１１３を用いて加
算されて、S₃＝A₃＋α^5(n-t)をあらわすビツト列
６が生成される。ビツト列４は第１誤り検出回路
１１５と第２誤り検出回路１１６に供給され、ビ
ツト列５とビツト列６は第２誤り検出回路に供給
される。第１誤り検出回路１１５はS₁が０の時は
１を、そうでない時は０を出力して選択回路１１
７に与えるものであり、論理和回路と否定回路で
構成される。第２誤り検出回路１１６はS₁をあら
わすビツト列４、S₂をあらわすビツト列５、およ
びS₃をあらわすビツト列６を入力してS₁ ⁶＋S₂ ²＋
S₁ ³S₂＋S₁S₃が０の時は１を、そうでない時は０
を出力して選択回路１１７に与えられるものであ
る。

図２は第２誤り検出回路１１６の構成例を示
す。図２においてビツト列４は６乗回路２０１、
３乗及び積回路２０３、及び積回路２０４に供給
され、又ビツト列５は２乗回路２０２と３乗及び
積回路２０３に供給され、さらにビツト列６は積
回路２０４に供給される。６乗回路２０１はS₁ ⁶
をあらわすビツト列７を生成する。２乗回路２０
２はS₂ ²をあらわすビツト列８を生成する。３乗
及び積回路２０３はS₁ ³S₂をあらわすビツト列９
を生成する。積回路２０４はS₁S₃をあらわすビツ
ト列10を生成する。６乗回路２０１、２乗回路２
０２、３乗及び積回路２０３、及び積回路２０４
は全てROMテーブルで構成される。排他的論理
和回路２０５はビツト列７とビツト列８の対応す
るビツト毎に排他的論理和をとることで加算を行
いS₁ ⁶S₂ ²をあらわすビツト列11を作成する。排他
的論理和回路２０６はビツト列９とビツト列10の
対応するビツト毎に排他的論理和をとることで加
算を行いS₁ ³S₂＋S₁S₃をあらわすビツト列12を作
成する。排他的論理和回路２０７はビツト列11と
ビツト列12の対応するビツト毎に排他的論理和を
とることで加算を行いS₁ ⁶＋S₂ ²＋S₁ ³S₂＋S₁S₃を
あらわすビツト列13を作成する。論理和回路２０
８はビツト列13の全ビツトの論理和をとることで
S₁ ⁶＋S₂ ²＋S₁ ³S₂＋S₁S₃が０の場合は０を出力
し、他の場合は１を出力する。否定回路２０９は
論理和回路２０８の出力の極性を反転し、S₁ ⁶＋
S₂ ²＋S₁ ³S₂＋S₁S₃が０の場合は１、他の場合は０
を出力する。図１にもどつて選択回路１１７は論
理積回路、論理和回路及び否定回路より構成さ
れ、訂正条件判別回路１０８がA₁ ³＋A₂＝０であ
ると判定して０を出力している場合には第１誤り
検出回路１１５の出力をその出力とし、訂正条件
判別回路１０８がA₁ ³＋A₂≠０であると判定して
１を出力している場合には第２誤り検出回路１１
６の出力をその出力とする。誤り訂正回路１１８
は排他的論理和回路であり、データバツフア１０
１の出力である第ｔ番目のビツトa′_tと選択回路
１１７の出力との排他的論理和をとる。従つて訂
正条件判別回路１０８の出力が０でかつ第１誤り
検出回路１１５の出力が１である場合、又は訂正
条件判別回路１０８の出力が１でかつ第２誤り検
出回路１１６の出力が１である場合に誤り訂正回
路１１８の出力はデータバツフア１０１の出力で
ある第ｔ番目のビツトa′_tを反転したものとな
し、そうでない場合は誤り訂正回路１１８の出力
はデータバツフア１０１の出力a′_tそのままであ
る。誤り訂正回路１１８の出力ｕは出力データと
なる。

【図面の簡単な説明】

図１は本発明による復号装置の実施例の構成図
であり、図２は図１の中の第２誤り検出回路１１
６の構成例である。図において１０１はデータバ
ツフア、１０２は第１シンドローム生成回路、１
０３は第１シンドロームバツフア、１０４は第２
シンドローム生成回路、１０５は第２シンドロー
ムバツフア、１０６は第３シンドローム生成回
路、１０７は第３シンドロームバツフア、１０８
は訂正条件判別回路、１００９は排他的論理和回
路、１１０はαのベキ発生回路、１１１は排他的
論理和回路、１１２はα^３のベキ発生回路、１１
３は排他的論理和回路、１１４はα^５のベキ発生
回路、１１５は第１誤り検出回路、１１６は第２
誤り検出回路、１１７は選択回路、１１８は誤り
訂正回路、２０１は６乗回路、２０２は２乗回
路、２０３は３乗及び積回路、２０４は積回路、
２０５は排他的論理和回路、２０６は排他的論理
和回路、２０７は排他的論理和回路、２０８は論
理和回路、２０９は否定回路、ａは入力データ、
ｂは第１シンドローム、ｃは第２シンドローム、
ｄは第３シンドローム、ｅはビツト列、ｆはビツ
ト列２、ｇはビツト列３、ｈはビツト列４、ｐは
ビツト列５、ｒはビツト列６、ｕはビツト列７、
ｘはビツト列８、ｙはビツト列９、aaはビツト列
10、ccはビツト列12、ddはビツト列13、は復
号出力である。

Claims

【特許請求の範囲】１３誤り訂正BCH符号の符号語〓に誤りベク
トル〓が加算されて出来た入力系列〓′＝（a′₁，
a′₂，a′₃，…a′_o）、（ｎは附号長ｎ＝２^m-1、ｍは
自
然数）を復号装置に入力して誤まり訂正を行なう
復号方式において、前記入力系列〓′から第１シ
ンドロームA₁、第２シンドロームA₂、及び第３
シンドロームA₃；をシフトレジスタを用いて求め、次いでA₁ ³＋A₂
＝０であれば S₁＝A₁＋α^n-t （αは２^m個の要素よりなるガロア体GF（２^m）の
原始元、ｔは誤りかどうかを判定されるビツトを
指定する番号でｎを越えない自然数）を０とする
ｔの値があればそれに対応する入力ビツトa′_tを
誤りとして反転して他の入力ビツトはそのまま出
力し、又 A₁ ³＋A₂≠０であれば S₁＝A₁＋α^n-t S₂＝A₂＋α^3(n-t) S₃＝A₃＋α^5(n-t) として EL′（ｔ）＝S₁ ⁶＋S₂ ²＋S₁ ³S₂＋S₁S₃＝０を与える３個までのｔの値（t₁，t₂，t₃）に対応す
る入力ビツト（a′_t1，a′_t2，a′_t3）を反転し、他の
入力ビツトはそのまま出力することにより、３個
までの誤りを訂正することを特徴とする３誤り訂
正符号復号方式。