JPH0691471B2

JPH0691471B2 - 誤り訂正回路

Info

Publication number: JPH0691471B2
Application number: JP60200005A
Authority: JP
Inventors: 誠中村; 文夫杉山
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1985-09-10
Filing date: 1985-09-10
Publication date: 1994-11-14
Anticipated expiration: 2009-11-14
Also published as: JPS6260320A

Description

【発明の詳細な説明】〔発明の技術分野〕本発明は、誤り訂正能力を有するブロック符号データを
受入れて複号化する際に用いられる誤り訂正回路に関す
る。

〔発明の技術的背景とその問題点〕

近年、ディジタル通信技術の発展に伴い、誤り訂正符号
が盛んに利用されている。とりわけ衛星通信、移動通信
のように伝送路の信頼性が低い無線ディジタル通信にお
いては誤り訂正技術は不可欠の技術であり、さらに近年
は磁気記録装置へのディジタル信号の記録再生にも誤り
訂正技術が広く利用されている。誤り訂正符号は大きく
分けてブロック符号、畳込み符号に大別されるが、なか
でも巡回符号を用いたブロック符号は種々の冗長度や誤
り訂正能力をもつものが数多く知られており、広く利用
されている。

ところで、巡回符号のうちBCH（ポース・チョードリ・
オッケンジェム）符号は、ランダム誤りを訂正する符号
であり、２ビット以上の誤り位置決定のためのアルゴリ
ズムとしてピーターソンの方法、バーレンカンプの方
法、あるいはマッシィの方法等、種々の方式が提案され
ている。しかし、これらの方法は、いずれも学術的には
ともかくとして極めて複数な演算を必要とすることから
実用上有用な方法とは言い難く、一般には２ビット以上
の訂正にはあまり使用されていないというのが実状であ
った。

また、誤り訂正符号の全てのパターンに対応するアドレ
スを有するメモリ（ROM）の各アドレスに誤り訂正情報
を書き込んでおき、誤り訂正符号をアドレスデータとし
てメモリへ入力して誤り訂正情報を読出す方式も考えら
れている。しかし、この方式は入力データ（誤り訂正符
号）の符号ビット長が長くなると、極めて大容量のメモ
リを必要とするという問題があった。

〔発明の目的〕

本発明は、このような事情に基づきなされたもので、そ
の目的とするところは、極めて簡易な方法で、２ビット
以上の誤り位置を確定することができる誤り訂正回路を
提供することにある。

〔発明の概要〕

本発明は、情報ビットと冗長ビットとで構成された受入
データを生成多項式で除算してシンドロームを検出する
シンドローム検出手段と、このシンドローム検出手段か
ら出力される前記シンドロームをアドレスとして入力
し、前記シンドロームから決定される前記受入データの
誤りがあるビット位置の情報をバイナリデータで構成さ
せて、これを記憶し出力する記憶装置と、この記憶装置
からのバイナリデータを前記受入データの各ビット毎に
ビット誤りの有無を示すデータに変換して出力する手段
と、前記ビット誤りの有無を示すデータを用いて前記受
入データの誤りビットを訂正する誤りビット訂正手段と
を具備したことを特徴とする。

〔発明の効果〕

本発明によれば、記憶装置のアドレスにシンドロームを
与え、記憶装置からシンドロームによって決まるビット
誤り位置を示すデータを出力データとして出力するよう
にしているので、２ビット以上の誤り訂正を複雑なアル
ゴリズムを用いることなく、また大容量の記憶装置を用
いることなく行なうことができる。したがって、回路構
成の簡単化、これによる通信システム、磁気記録装置等
の信頼性向上に寄与できる。このような効果は訂正可能
なビット数が増えれば増える程一層顕著に現れる。

〔発明の実施例〕

以下、本発明の実施例を説明する。

ここでは一例としてBCH符号を用いる場合について考え
る。

いま、誤り訂正符号の符号語Ｍ（Ｘ）がガロア体GF
（ｑ）の元で構成され、その生成多項式Ｇ（Ｘ）が、GF
（ｑ）の拡大体GF（q^m）の元により定められていると
き、符号語Ｍ（Ｘ）はＧ（Ｘ）で割切れる。このような
符号語Ｍ（Ｘ）を採用すれば、入力された符号語Ｍ′
（Ｘ）が生成多項式Ｇ（Ｘ）で割切れるかどうかによっ
て誤り発生の有無がわかる。

いま、入力された符号語Ｍ′（Ｘ）が伝送誤りを含む場
合、符号語Ｍ′（Ｘ）をＧ（Ｘ）で除算した余りは０に
はならない。誤りが生じたビットを“1"、その他を“0"
とする符号列をＥ（Ｘ）とすると、Ｍ′（Ｘ）＝Ｍ（Ｘ）＋Ｅ（Ｘ）（「＋」は法２加算）であるから、Ｍ′（Ｘ）をＧ
（Ｘ）で除算した余りは、Ｅ（Ｘ）/G（Ｘ）の余りと等
しい、この余りをシンドロームＳ（Ｘ）と呼ぶ。このシ
ンドロームＳ（Ｘ）がｌビットまでの誤りの全てのパタ
ーンについて異なる値をとり得れば、シンドロームＳ
（Ｘ）からｌビットまでの誤りを訂正することができ
る。

第１図は本発明の一実施例を示す図である。この誤り訂
正回路は、受入データＭ′（Ｘ）から上述したシンドロ
ームを検出するシンドローム検出回路11と、このシンド
ローム検出回路11によって検出されるシンドロームＳ
（Ｘ）を入力として、シンドロームＳ（Ｘ）によって決
定される、受入データＭ′（Ｘ）のビット誤り位置を受
入データＭ′（Ｘ）の各ビット毎に示すデータＥ（Ｘ）
を出力する誤り位置検出回路12と、この誤り位置検出回
路12から出力されるデータＥ（Ｘ）に基づいて、受入デ
ータＭ′（Ｘ）の誤りビットを反転させて誤りビットを
訂正するビット誤り反転回路13とで構成される。誤り位
置検出回路12は、後述するようにビット誤り位置を示す
バイナリデータを記憶するためのROM（第４図参照）を
含んで構成される。（このバイナリデータとは、２進化
10進符号を意味する）いま、受入データＭ′（Ｘ）が符号ビット長31（情報ビ
ット長16、冗長ビット長15）で、３ビットまでの誤りを
訂正できる（31,16）のBCH符号であるとする。そして、
生成多項式を、ｇ（Ｘ）＝X¹⁵＋X¹¹＋X¹⁰＋X³＋X⁸＋X⁷＋X⁵＋X³＋X²＋
Ｘ＋１とする。

このような31ビットの受入データＭ′（Ｘ）が、シンド
ローム検出回路11に入力されると、シンドローム検出回
路11では受入データＭ′（Ｘ）を生成多項式ｇ（Ｘ）で
除算してシンドロームＳ（Ｘ）を算出する。シンドロー
ムＳ（Ｘ）は、生成多項式ｇ（Ｘ）の次数が15であるか
ら15ビットのデータとなる。

第２図にシンドロームＳ（Ｘ）検出の一例を示す。な
お、ここでは簡単のために生成多項式が、ｇ′（Ｘ）＝X⁵＋X²＋１である場合の例を示した。

すなわち、まずデータ入力に先だって遅延回路21,22,2
3,24,25が全てクリアされる。次に高次のビットから順
次シリアルに入力された受入データは、EX−OR回路26に
おいて、遅延回路25の出力信号と排他的論理和され、遅
延回路21に与えられる。遅延回路21に入力されたビット
データは、所定のクロックに従って遅延回路22〜25まで
順次シフトされるが、遅延回路22と23との間のEX−OR回
路27において再び遅延回路25の出力と排他的論理和がと
られる。シンドロームＳ（Ｘ）は、受入データの最後の
ビットがシンドローム検出回路11に入力され、さらにEX
−OR回路26を介して遅延回路21から出力された時に遅延
回路21〜25の出力信号として得られる。上述した15次の
生成多項式ｇ（Ｘ）の場合にも、遅延回路が15段になる
だけで第２図の回路と全く同じ原理の検出回路を構成す
ることができる。

このようにして得られたシンドロームＳ（Ｘ）は、誤り
位置検出回路12にアドレスデータとして与えられる。

例えば下位16ビット目が誤ったとすると、シンドローム
は、X¹⁵をｇ（Ｘ）で除算した余りであるから、Ｓ（Ｘ）＝X¹¹＋X¹⁰＋X³＋X⁸＋X⁷＋X⁵＋X³＋X²＋Ｘ＋１となる。従って、誤り位置検出回路12内のROMのアドレ
スには、 000111110101111 なるアドレスデータが与えられる。そして、こりアドレ
スデータで示されるROMの記憶場所には、X¹⁵の位置に誤
りがあることを示す。

01111 なるバイナリデータが記憶されており、これが読出され
出力される。このROMから出力されたバイナリデータ
は、受入データＭ′（Ｘ）の各ビット毎に誤り位置を示
すデータＥ（Ｘ）に変換されて誤り位置検出回路12から
出力される。

また、例えば下位４ビット目、16ビット目、17ビット目
の３ビットのデータが誤ったとすると、シンドロームＳ
（Ｘ）は、X¹⁶＋X¹⁵＋X³をｇ（Ｘ）で割った余りである
から、Ｓ（Ｘ）＝X¹²＋X⁷＋X⁶＋X⁵＋X⁴＋X³＋１となる。従って、ROMのアドレスには 001000011111001 なるアドレスデータが与えられる。そして、このアドレ
スデータで示されるROMの記憶場所には、 00100,10000,10001 なる３個のデータが記憶されており、これが出力され
る。

このように、全ての１ビット誤り、２ビット誤り、３ビ
ット誤りに対応するシンドロームでアドレス指定される
ROMの各記憶場所には、予めそれぞれのビット誤り位置
を示す15ビットのバイナリデータを記憶しておく。訂正
できる誤りは、１ビット誤りが31通り、２ビット誤りが
₃₁C₂＝465通り、３ビット誤りが₃₁C₃＝4495通りである
ので、2¹⁵＝32768あるアドレスのうちの約1/6に相当す
る。なお、ビット誤りが生じていない場合には、シンド
ローム検出回路11からはアドレス（00…00）が指定され
るので、この場所には（00…00）のデータを記憶してお
く。そして、これ以外のアドレスが指定される場合は、
４ビット以上の誤りが生じたことを示しており、この場
合には誤り訂正が不可能である。したがって、このよう
なアドレスで指定されるROMの記憶場所の全てに、訂正
不能を知らせる特別のデータ、例えば15ビットの全てを
“1"とした（11…11）のデータを記憶しておく。31ビッ
ト目が誤った場合には、例えば 11111,00000,00000 なるデータを記憶しているので、これと区別できる。

誤り位置検出回路12において、ROMの出力データはバイ
ナリデータであるので、これを誤り位置に対応するビッ
トを“1"、他のビットを“0"とした31ビットの誤り位置
を示すデータ、すなわち受入データＭ′（Ｘ）の各ビッ
ト毎に誤り位置を示すデータＥ（Ｘ）に変換して、誤り
ビット反転回路13に出力する。例えば前述のように、 00100,10000,10001 なるバイナリデータがROMに記憶されていれば、 0000000000000011000000000001000 なるデータが誤り位置検出回路12から出力される。ま
た、訂正不能な４ビット以上の誤りがあることを示す
（11…11）なるデータがROMから出力された時には、特
別に31ビット全てを“1"としたデータが出力される。例
えば第３図に示すように構成されている。すなわち、受
入データＭ′（Ｘ）は、31ビットのシフトレジスタ31に
シリアルに入力される。31ビットの受入データの全ての
ビットがシフトレジスタ31に格納されたら、受入データ
はシフトレジスタ31から31ビットのラッチ回路32にラッ
チされる。そして、各ビットデータは各々EX−OR回路33
₁，33₂，…，33₃₁の一方の入力に与えられる。一方、誤
り位置検出ROM12からの誤り位置データＥ（Ｘ）も31ビ
ットのラッチ回路34にラッチされ、各々EX−OR回路3
3₁，33₂，…，33₃₁の他方の入力に与えられる。また、
ラッチ回路34の出力はAND回路35にも入力されている。

いま、受入データに誤りがないときは、ラッチ回路34の
出力は、全て“0"であるから、受入データ、EX−OR回路
33₁，33₂，…，33₃₁によっては何等左右されず、そのま
ま出力される。

一方、受入データに３ビット以下の誤りがある場合に
は、誤り位置検出回路12からは誤り位置に“1"が立った
データが出力されるので、入力データは、EX−OR回路33
₁，33₂，…，33₃₁によって反転され、これによって誤り
が訂正されたデータＭ（Ｘ）がEX−OR回路33₁，33₂，
…，33₃₁から出力される。

また、４ビット以上の誤りが生じた場合には、ラッチ回
路34の出力が全て“1"になるので、AND回路35の出力が
“0"から“1"に反転し、これが誤りを検出信号ERRとし
て出力される。

このように本実施例によれば、誤り位置検出回路12を用
いた極めて簡単な回路構成によりまた複雑なアルゴリズ
ムを一切用いることなく２ビット以上のランダム誤りを
訂正でき、誤り訂正符号の実用化に大きく寄与すること
は明らかである。

なお、本発明は、上述した実施例に限定されるものでは
ない。

例えば上記実施例では31個のEX−OR回路を使用して受入
データとビット誤り位置を示すデータとのEX−ORを並列
的にとるようにしたが、受入データがシリアルに入力さ
れるので、誤りビット反転回路13の出力データも１ビッ
トずつ出力するようにすれば、EX−OR回路は１つで足り
ることになる。このような構成とすれば、第３図に示し
たような31ビットのシフトレジスタ31、ラッチ32,34お
よび31個のEX−OR回路33₁〜33₃₁を必要としないという
利点がある。この構成による本発明の実施例を第４図に
示す。

第４図において、誤り位置検出ROM51とコンパレータ52
とカウンタ53およびRSフリップフロップ56は第１図の誤
り検出回路12に相当し、シフトレジスタ54およびEX−OR
回路55は第１図の誤りビット反転回路13に相当する。こ
こで、誤り位置検出ROM51は、最上位アドレスが“0"と
なる第一の領域、つまり、00000…０から01111…１まで
のアドレスに対応する部分と、最上位アドレスが“1"と
なる第二の領域、つまり、10000…０から11111…１まで
のアドレスに対応する部分、とに分割されている。そし
て、アドレスが00000…０から01111…１の範囲に、下位
の誤りビット位置を示すデータを記憶し、アドレスが、
10000…０から11111…１の範囲に、下位の誤りビット位
置を示すデータを記憶する。（シンドロームのビット数
をｍとすると、アドレスのビット数はｍ＋１となる。）
従って、２ビット誤りのうち上位の誤りビットの位置を
示す５ビットのバイナリーデータが、上記第１の領域の
対応するシンドロームで特定される記憶場所に記憶さ
れ、同下位の誤りビットの位置を示す５ビットのバイナ
リーデータが、上記第２の領域の対応するシンドローム
で特定される記憶場所に記憶されている。当初ROM51の
アドレスの最上位ビットは“0"に設定されている。ROM5
1の出力は、コンパレータ52の第１の入力端子に導入さ
れている。一方、コンパレータ52の第２の入力端子に
は、５ビットのカウンタ53からの出力が与えられてい
る。カウンタ53は高速クロックφによって駆動され、
（０）から（31）までのバイナリーコードを出力する。
コンパレータ52は両入力データが一致したら“1"を出力
する。一方、受入データＭ′（Ｘ）は、シフトレジスタ
54に導入されている。このシフトレジスタ54は、カウン
タ53の高速クロックφで駆動されている。したがって、
コンパレータ52から“1"が出力された時に、シフトレジ
スタから出力されているビットデータは誤りということ
になる。そこで、コンパレータ52の出力が、“1"になっ
たときには、シフトレジスタ54の出力をEX−OR回路55で
反転させれば、誤り訂正を行なうもとができる。なお、
コンパレータ52からの“1"出力は、RSフリップフロップ
回路56のセット（Ｓ）端子に与えられているので、RSフ
リップフロップ回路56の出力は“0"から“1"に反転し、
ROM51のアドレスの最上位ビットは“1"となる。そし
て、再び同様の手順で２ビット目の誤り訂正が行われ
る。なお、誤り訂正が終了したら、カウンタ53とRSフリ
ップフロップ56のリセット（Ｒ）端子に、外部らのリセ
ット信号RSが与えられる。訂正できる誤りビットの数が
増えれば、RSフリップフロップの数を増やさせば良い。

このような構成であれば、31ビットのうち誤りのないビ
ットを“0"、誤りのあるビットを“1"としてROMに記憶
する方法に比較して、誤り位置検出ROM51の容量を5t/31
に削減することができる。但し、ｔは訂正可能な最大の
誤りビット数を示す。

この他、本発明はシンドロームからビット誤り位置を検
出する記憶装置としてRAMや磁気ディスクなど他の記憶
装置を用いるようにしてもよい。

また、巡回符号の種類はBCHに限らず、シンドロームか
らビット誤り位置を特定できる誤り訂正能力を有する符
号であれば、この発明を適用可能である。

【図面の簡単な説明】

第１図は本発明の一実施例に係る誤り訂正回路のブロッ
ク図、第２図は同誤り訂正回路におけるシンドローム検
出回路の一例を示すブロック図、第３図は同誤り訂正回
路における誤りビット反転回路の一例を示すブロック
図、第４図は本発明の他の実施例に係る誤り訂正回路の
一部を示すブロック図である。 21〜25…遅延回路、31…シフトレジスタ、32,34…ラッ
チ回路、56…RSフリップフロップ回路。

Claims

【特許請求の範囲】

【請求項１】情報ビットと冗長ビットとで構成された受
入データを生成多項式で除算してシンドロームを検出手
段するシンドローム検出手段と、このシンドローム検出手段から出力される前記シンドロ
ームをアドレスとして入力し、前記シンドロームから決
定される前記受入データの誤りがあるビット位置の情報
をバイナリデータで構成させて、これを記憶し出力する
記憶装置と、この記憶装置からのデイナリデータを前記受入データの
各ビット毎にビット誤りの有無を示すデータに変換して
出力する手段と、前記ビット誤りの有無を示すデータを用いて前記受入デ
ータの誤りビットを訂正する誤りビット訂正手段とを具
備したことを特徴とする誤り訂正回路。
【請求項２】前記記憶装置は、前記シンドロームから誤
りがあるビット位置を決定できないときに前記受入デー
タに誤りがあったことだけを知らせるデータを出力する
ものであることを特徴とする特許請求の範囲第１項記載
の誤り訂正回路。