JPS6260320A - 誤り訂正回路 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

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

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

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

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

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

〔発明の概要〕

本発明は、情報ビットと冗長ビットとで構成される受入
データを生成多項式で除算してシンドロームを求めるシ
ンドローム検出手段と、このシンドローム検出手段をア
ドレスとして入力し上記シンドロームで一意的に特定さ
れるビット誤り位置を示すデータを出力する記憶手段と
、この記憶手段からの出力データを用いて前記受入デー
タの誤りビットを訂正する誤りビット訂正手段とを具備
したことを特徴としている。

〔発明の効果〕

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

〔発明の実施例〕

以下、本発明の詳細な説明する。

ここでは−例としてＢＣＨ符号を用いる場合について考
える。

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

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

第１図は本発明の一実施例を示す図である。すなわち、
この誤り訂正回路は、受入データＭ′（Ｘ）から上述し
たシンドロームを求めるシンドローム検出回路１１と、
このシンドローム検出回路１１から出力されるシンドロ
ーム５（Ｘ）をアドレス入力してこのシンドローム５（
Ｘ）によって特定されるビット誤り位置を示すデータＥ
　（Ｘ）を出力する誤り位置検出ＲＯＭ１２と、この誤
り位置検出ＲＯＭ１２から出力されるデータＥ　（Ｘ＞
に基づいて受入データＭ’　　（Ｘ）の誤りビットを反
転させる誤りビット反転回路１３とで構成されている。

いま、受入データＭ’　　（Ｘ）が符号ビット長３１（
情報ビット長１６、冗長ビット長１５）で、３ビットま
での誤りを訂正できる（３１．１６）のＢＣＨ符号であ
るとする。そして、生成多項式を、Ｑ　（Ｘ）　＝Ｘ１
　’　＋Ｘ１１　＋ＸＩ　Ｏ＋Ｘ９＋　Ｘｌｌ　＋　Ｘ
７　＋　Ｘ５　＋　Ｘｌ　＋　Ｘ２＋ｘ＋１ とする。

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

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

すなわち、まずデータ入力に先だって遅延回路２１．２
２．２３．２４．２５が全てクリアされる。次に高次の
ビットから順次シリアルに入力された受入データは、Ｅ
Ｘ−ＯＲ回路２６において、遅延回路２５の出力信号と
排他的論理和され、遅延回路２１に与えられる。遅延回
路２１に入力されたビットデータは、所定のクロックに
従って遅延回路２２〜２５まで順次シフトされるが、遅
延回路２２と２３との間のＥＸ−ＯＲ回路２７において
再び遅延回路２５の出力と排他的論理和がとられる。シ
ンドローム５（Ｘ）は、受入データの最後のビットがシ
ンドローム検出回路１１に入力され、ざらにＥＸ−ＯＲ
回路２６を介して遅延回路２１から出力された時に遅延
回路２１〜２５の出力信号として得られる。上述した１
５次の生成多項式〇（Ｘ）の場合にも、遅延回路が１５
段になるだけで第２図の回路と全く同じ原理の検出回路
を構成することができる。

このようにして得られたシンドロームＳ（Ｘ＞は、誤り
位置検出ＲＯＭ１２にアドレスデータとして与えられる
。

例えば下位１６ビツト目が誤ったとすると、シンドロー
ムは、Ｘ１５をＱ　（Ｘ）で除算した余りであるから、 Ｓ　（Ｘ＞　＝Ｘ”　１　＋ｘｌ　Ｏ＋Ｘ９　＋Ｘ８＋
ＸＴ＋ＸＳ　＋Ｘ３　＋Ｘ２　＋Ｘ ＋１ となる。従って、ＲＯＭ１２のアドレスには、なるアド
レスデータが与えられる。そして、このアドレスで示さ
れるＲＯＭ１２の記憶場所には、ｏｏｏｏｏｏｏｏｏｏ
ｏｏｏｏｏｉｏｏｏｏｏｏｏｏｏｏｏｏｏｏ。

なるデータが記憶されており、これが出力される。

また、例えば下位４ビツト目、１６ビツト目、１７ビツ
ト目の３ビツトのデータが誤ったとすると、シンドロー
ムＳ　（Ｘ）は、×１５　＋ＸＩ　Ｓ　＋×３をＱ（Ｘ
）で割った余りであるから、Ｓ　（Ｘ）　−Ｘｌ　２＋
Ｘ７　＋Ｘ６＋Ｘ’＋Ｘ’　＋Ｘ３＋１ となる。したがってＲＯＭ１２のアドレスには、なるア
ドレスデータが与えられる。そして、このアドレスで示
されるＲＯＩｖ１１２の記憶場所には、なるデータが記
憶されており、これが出力される。

このように、全ての１ビット誤り、２ビット誤り、３ビ
ット誤りに対応するシンドロームでアドレスされるＲＯ
Ｍ１２の各記憶場所には、予めそれぞれのビット誤り位
置に“１″を立てた３１ビツトデータを記憶しておく。

訂正できる誤りは、１ビット誤りが３１通り、２ビット
誤りが３１０２　＝４６５通り、３ビット誤りが３　ｔ
　Ｃ３＝４４９５通りであるので、２１　＆　＝３２７
６８あるアドレスのうちの約１／６に相当する。なあ、
ビット誤りが生じていない場合には、シンドローム検出
回路１１からはアドレス（００・・・ＯＯ）が指定され
るので、この場所には（００・・・００）のデータを記
憶しておく。そして、これ以外のアドレスが指定される
場合は、４ビツト以上の誤りが生じたことを示しており
、この場合には誤り訂正が不可能である。したがって、
このようなアドレスで指定されるＲＯＭ１２の記憶場所
の全てには、訂正不能を知らせる特別のデータ、例えば
（１１・・・１１）のデータを記憶しておく。

ＲＯＭ１２の出力データは、誤りビット反転回路１３に
入力される。誤りビット反転回路１３は、例えば第３図
に示すように構成されている。すなわち、受入データＭ
’　　（Ｘ）は、３１ビツトのシフトレジスタ３１にシ
リアルに入力される。３１ビツトの受入データの全ての
ビットがシフトレジスタ３１に格納されたら、受入デー
タはシフトレジスタ３１から３１ビツトのラッチ回路３
２にラッチされる。そして、各ビットデータは各々ＥＸ
−○Ｒ回路３３１．３３２　、・・・、３３３１の一方
の入力に与えられる。一方、誤り位置検出ＲＯＭ１２か
らの誤り位置データＥ（Ｘ）も３１ビツトのラッチ回路
３４にラッチされ、各々ＥＸ−ＯＲ回路３３１．３３２
　、・・・、３３ヨ１の他方の入力に与えられる。また
、ラッチ回路３４の出力はＡＮＤ回路３５にも入力され
ている。

いま、受入データに誤りがないときは、ラッチ回路３４
の出力は、全て０″であるから、受入データは、ＥＸ−
ＯＲ回路３３工、３３２　、・・・。

３３３工によっては何等左右されず、そのまま出力され
る。

一方、受入データに３ビツト以下の誤りがある場合には
、ＲＯＭ１２からは誤り位置に“１″が立ったデータが
出力されるので、入力データは、ＥＸ−ＯＲ回路３３１
．３３２　、・・・、３３３１によって反転され、これ
によって誤りが訂正されたデータＭ（Ｘ＞がＥＸ−ＯＲ
回路３３ｔ　、３３２　。

・・・、３３３１から出力される。

また、４ビツト以上の誤りが生じた場合には、ラッチ回
路３４の出力が全て“′１”になるので、ＡＮＤ回路３
５の出力が“○”から１”に反転し、これが誤り検出信
号ＥＲＲとして出力される。

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

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

例えば上記実施例では３１個のＥＸ−ＯＲ回路を使用し
て受入データとビット誤り位置を示すデータとのＥＸ−
ＯＲを並列的にとるようにしたが、受入データがシリア
ルに入力されるので、誤りビット反転回路１３の出力デ
ータも１ピッ１−ずつ出力するようにすれば、ＥＸ−Ｏ
Ｒ回路は１つで足りることになる。第４図はこのような
考えに基づき構成された回路である。

すなわち、誤り位置検出ＲＯＭ４１に与えるアドレスの
うち下位１５ビツトを上記実施例と同様のシンドローム
５（Ｘ）で与え、上位５ビツトに５ビツトのカウンタ４
２からの出力を与える。そして、カウンタ４２を所定の
クロックに従って順次カウントアツプさせ、アドレスを
更新していく。

ＲＯＭ４１には、例えば第５図に示すように、データの
ビット位置を示す上位５ビツトｏｏｏｏｏ〜１１１１１
とシンドロームとが結合されて構成されたアドレスの記
憶場所に、そのシンドロームによって特定される３１ビ
ツトのビット誤り位置データのうち、上記上位５ビツト
で決まるビット位置のビットデータが１ビツトだけデー
タとして格納されている。例えば第５図に示すように、
シンドロームが、 であるとき、そのビツト誤り位置データが、であること
は前述したが、この例では上記３１ビツトのデータのう
ちのカウンタ４２の出力で特定されるビット位置の１ビ
ツトデータのみをＲＯＭ４１の内部に記憶させておくよ
うにしている。そして、このＲＯＭ４１の出力と受入デ
ータとをＥＸ−ＯＲ回路４３に入力させて誤り訂正を行
なうものとなっている。

このような構成であれば、カウンタ４２のカウントアツ
プによって３１ビツトのデータがＲＯＭ　４１からシリ
アルに出力されるので、第３図に示したような３１ビツ
トのシフトレジスタ３１、ラッチ３２．３４おにび３１
個（７）ＥＸ−ＯＲ回路３３１〜３３３１を必要としな
いという利点がある。

また、上記実施例では誤り位置を示すデータに３１ビツ
トのデータを用い、このデータのピッｌ−データが１”
の部分が誤りであることを示したが、この３１ビツトの
データを５ビツトのバイナリ−データで示すようにして
もよい。第６図にこの例を示す。

すなわち、誤り位置検出ＲＯＭ５１は、そのメモリ空間
のうちの最上位アドレスが“Ｏ１１になる第１の領域と
、１”になる第２の領域とに分割されている。そして、
２ビット誤りのうち上位の誤りビットの位置を示す５ビ
ツトのバイナリ−データが、上記第１の領域の対応する
シンドロームで特定される記憶場所に記憶され、同下位
の誤りビットの位置を示す５ビツトのバイナリ−データ
が、上記第２の領域の対応するシンドロームで特定され
る記憶場所に記憶されている。当初ＲＯＭ５１のアドレ
スの最上位ビットは“ＯＩＩに設定されている。ＲＯＭ
５１の出力は、コンパレータ５２の第１の入力端子に導
入されている。一方、コンパレータ５２の第２の入力端
子には、５ビツトのカウンタ５３からの出力が与えられ
ている。

カウンタ５３は高速クロックφによって駆動され、（０
）から（３１）までのバイナリ−コードを出力する。コ
ンパレータ５２は両人力データが一致したら１°′を出
力する。一方、受入データＭ′（Ｘ）は、シフトレジス
タ５４に導入されている。

このシフトレジスタ５４は、カウンタ５３の高速クロッ
クφで駆動されている。したがって、コンパレータ５２
から１”が出力された時に、シフトレジスタから出力さ
れているビットデータは誤りということになる。そこで
、コンパレータ５２の出力が１１１１＋になったときに
は、シフトレジスタ５４の出力をＥＸ−ＯＲ回路５５で
反転さゼれば、誤り訂正を行なうことができる。なお、
コンパレータ５２からの“１″出力は、ＲＳＳフリップ
フロラフ路５６のセット（Ｓ）端子に与えられているの
で、ＲＳＳフリップフロラフ路５６の出力はＯ″から“
１″に反転し、ＲＯＭ５１のアドレスの農上位ビットは
“１″となる。そして、再び同様の手順で２ビツト目の
誤り訂正が行われる。なお、誤り訂正が終了したら、カ
ウンタ５３とＲＳフリップフロップ５６のリセット（Ｒ
）端子に、外部らのリセット信号Ｒ８が与えられる。

訂正できる誤りビットの数が増えれば、ＲＳフリップフ
ロップの数を増やせば良い。

このような構成であれば、誤り位置検出ＲＯＭ５１の容
量を前述した各実施例のものに比べて５／３１に削減す
ることができる。

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

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

【図面の簡単な説明】

第１図は本発明の一実施例に係る誤り訂正回路のブロッ
ク図、第２図は同誤り訂正回路におけるシンドローム検
出回路の一例を示すブロック図、第３図は同誤り訂正回
路における誤りビット反転回路の一例を示すブロック図
、第４図は本発明の他の実施例に係る誤り訂正回路の一
部を示すブロック図、第５図は同誤り訂正回路における
ＲＯＭの内容を示す図、第６図は本発明の更に他の実施
例に係る誤り訂正回路の一部を示すブロック図である。 ２１〜２５・・・遅延回路、３１・・・シフトレジスタ
、３２．３４・・・ラッチ回路、５６・・・ＲＳＳフリ
ップフロラフ路。 出願人代理人　弁理士　鈴江武彦 第１図 Ｅ（Ｘ） 第４図 第５図 ５（Ｘ） 第６図

Claims (3)

【特許請求の範囲】
1. （１）情報ビットと冗長ビットとで構成された受入デー
   タを生成多項式で除算してシンドロームを求めるシンド
   ローム検出手段と、このシンドローム検出手段から出力
   される前記シンドロームをアドレスとして入力し前記シ
   ンドロームから一意的に決定する前記受入データのビッ
   ト誤り位置を示すデータを出力する記憶装置と、この記
   憶装置からの出力データを用いて前記受入データの誤り
   ビットを訂正する誤りビット訂正手段とを具備したこと
   を特徴とする誤り訂正回路。
2. （２）前記記憶装置は、前記シンドロームからビット誤
   り位置を一意的に決定できないときに前記受入データに
   誤りがあつたことだけを知らせるデータを出力するもの
   であることを特徴とする特許請求の範囲１項記載の誤り
   訂正回路。
3. （３）前記記憶装置はカウンタを備え、前記記憶装置の
   アドレスの一部に前記シンドロームを与えるとともに残
   りのアドレスに上記カウンタの出力を与え、前記シンド
   ロームで特定されるビット誤り位置を示すデータのうち
   前記カウンタで特定される位置のビットデータを出力す
   るものであることを特徴とする特許請求の範囲第１項記
   載の誤り訂正回路。