JPH01186020A - 多数ビツト誤り訂正方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ｕ）　産業上の利用分野 本発明は、多数ビット誤り訂正方式に係り、ディジタル
データ伝ａＫ用いらｎるＢＣＨ誤り訂正符号の復号方式
に関する。

口】従来の技術 一般にディジタルデータを伝送する場合、伝送系のＳＮ
比の劣化、歪等に起因して発生するビット誤りに対処す
る為に、誤り訂正能力を荷つ冗長ビット（誤り訂正ビッ
ト〕を元の情報ビットに付加して送信し、受信側でこの
訂正用ピッ）ｋ用いて誤り位置を検出して誤り訂正を行
なう方法がよく用いらｎている。

この訂正符号の中でもＢＣＨＲ号（ポーズ（Ｂｏｓｅ）
−ｆヨＹ−１（Ｃｈａｕｄｈｕｒｉ）−オックンジエム
（Ｈｏｃｑｕｅｎｇｈｅｍ））ｉ、訂正用ヒツトの長さ
（ビット数〕に対する誤り訂正能力が高いという利点が
あり、衛星放送、自動車電話機。

コードレス電話機等に広く用いられている。

このＢＣＨ符号を用Ａて訂正する復号方式としては受信
旧号列Ｖ（ｘ）を主脚多項式Ｇ（ｘ）で割り、その剰余
項（こｎをシンドロームと呼ぶ〕を求め、このシンドロ
ームの値から誤りの有無の判定、誤！１）位置の算出を
行い、誤り位置に対応するビットの値を反転して訂正す
るという手順がとらｎる。

ここで、ＢＣ）Ｉ符号のもつ符号間距離をｄとするとこ
のＢＣＩ−１符号は士已ビットの誤り迄訂正する能力を
持つ。例えば、衛星放送のデータチャンネル伝送におい
ては、送出パケットのヘッダ部には、第３図のよりに５
ピツトの情報ビットに対し、１０次の生成多項式Ｇ（２
）−Ｘ１０＋Ｘ８＋Ｘ５＋Ｘ’＋Ｘ２＋Ｘ＋１に基づく
１０ビットの訂正符号を付加しｆｃ１５ビットのデータ
に更にパリティチェック用の１ビットをｃＳＳ側に付加
し九符号が用いられている。この訂正符号は、符号間距
離ｄ−７をもちに＝３ビット講り迄の訂正能力を有し、
更にパリティチェック（偶奇判定）により、４ビット誤
りの検出能力を有するように構成さｎている。

この符号を用いて、３ピツト訂正、４ビット誤り検出の
能力？もつ１）号を行なうにぼ、■　ＢＣＨ符号におけ
る復号（１５ピツトのデータに対して〕において、１ビ
ット又は２ビット誤りの場合に框、パリティチェックは
行わず、ＢＣＥ（符号に基づき、各々１ビット又は２ビ
ットの訂正を行う ■　その他の場合には、パリティチェックにより偶奇判
定を行い、奇数誤）のときは３ビット誤りと見なして訂
正処理する。偶数誤りのときは４ビット誤りと見なして
訂正不能とする 手、屓にエフ行なえばよい。

さて、−ｆｆＫこのようなりＣＨ符号の訂正処理を行な
う方法として、第２図に示すように、受信信号Ｖ（ｘ）
をシンドローム算出回路（１）にて生成多項式Ｇ（Ｘ；
で１余した剰余項を求め、この剰余項であるシンドロー
ムの値をアドレスとして、これに対応するデータとして
予め誤り位置情報を格納し次メモリ（以下、ＲＯＭとい
う。月２１を用いて、誤り位置を求め、誤り位置処理回
路（５）に与え、受信１Ｎ号Ｖ内を遅延回路（４）で所
定量遅延させ、排他的１會理和からなる加算回路ｆ３Ｊ
で加算処壊して誤りを訂正するものである。

例えば、前記のヘッダに用いられている８ＣＨ符号にお
いては、王底多項式Ｇ伏】の次数は１０次であり、剰余
値として得られるシンドロームの数は２　個ある。１次
、ビット長は１５ビット（パリティビットは除く〕であ
るので、誤り位置１つに対しては４ビットｔ″要し、従
うて３箇所の誤りｇ、置の情報を格納するのく必要なビ
ット数／シンドロームｆ１．４Ｘ３−１２ビットとなる
。

斯る方法は、従えば、昭和６１年３月日本工業技術セン
ター発行「誤り訂正符号化技術の要点」第２８８頁乃至
Ｍ２Ｂ５頁に記載さｎている。

（／９　発明が解決しようとする課題 ところで、市販のＦｔＯＭにおける１ワードのビット数
は、一般には８ビットが多く、従、て。

上述した場合、３箇厚「（ＤＡり位置１オ報を格納する
のに、２ワードを必要とし、復号用ＲＯＭＶｃＰｇＴ要
のアドレス値ニシンドロームの数の倍にあたる２１′”
２０４８を要し、効率的ではない。

本発明は、復号用ＲＯＭへの誤り位置情報の格納法を改
良し、ＲＯＭの所要アドレスを大幅ＶＣ低減する方式を
提供するものである。

に）謀瀞を解決する次めの手段 Ｘｉ明は、ｎ＋ｋビット長でｔビット以ドの誤りパター
ンをｆＩａ記′Ｅ戊多項式で１余し九剰余値をアドレス
とし、こ、Ｄ腺りパターンのうち情報ピッ）Ｋ４応する
ｎビットの値に、更にパリティチェックを行なうか否小
のフラグｔｉ報を付しｔ値をデータとして格納し九メモ
リを備え、パリティビット部を糸い九ｎ＋ｋビット長の
受１！　ｉｆｆ号を生成多項式〇（ｘＪ′″Ｃ除しｔ剰
余値を前記メモリにアドレス値としてへカし、このメモ
リ＝９→らｎ几ｎビットの誤９パターンを受周ＩＪ号に
加算すると共に。

＠記メモリエク得ら几るパリティチェック用の）ラグ情
報を参照し、パリティチェックか不要なときは、前記力
口算結果を訂正後のデータとみなし、パリティチェック
か必要なときは、パリティチェックより得らｎた誤り数
の偶奇判定結果が、ｔの偶奇と一致のときは前記加算結
果を訂正後のデータとみなし、不一致のときは訂正不能
として処理することを特徴とする。

（ホ）作　用 本発明によれば、例えば、前述した■３図に示す衛星放
送データチャンネル伝送のヘッダ部についてｉ、Ｆ（Ｏ
Ｍのデータ領域のビット数は６ピツトで済み、従来の４
Ｘ３＝１２ビットに比べｌ／２というように、ＲＯＭの
所要容量を低減させることができる。

（へ）実施例 以下、本発明の一実施例につき、第１図および第４因に
従＾説明する。

まず、本発明の基本とするところは、以下の２つである
。

（ａＪ　　誤り位置の訂正は、情報ビットのみを正しく
訂正すればよく、訂正ビットについては、誤訂正となっ
ても実用上支障がない。

■　パリティチェックの必要性の有無の情報をＲＯＭに
格納する。

そして、かかる情報をＲＯＭのデータ領域のｎ＋１ピッ
）（ｎ：情報ビットの数〕に収容するも（ＤＴあり、例
えば前記の衛星放送データチャンネル伝送フォーマット
においては情報ビット長ｎ　−５であり、ＲＯＭのデー
タ領域は６ビットとなる。

本発明におけるｆ（ＯＭへのデータの格納方法及び復号
方法を次に説明する。

ビット長　ｍ＝ｎ＋ｋ ここでｎ：情報ビット長、ｋ：訂正ビット長（生成多項
式の次数に対応〕の符号におけるｔピッ）（１≦ｎ−１
）の誤り訂正に対し、ビット長ｍで誤り箇所がｔ個以下
の誤りパターンを生成多項式Ｇ（Ｘ）を徐し次ときの剰
余環をＲＯＭのアドレス値とする。例えば第４因は、誤
り箇所が３個の場合を示す。１４肉において誤りビット
の立置が。

２．５．８の３箇所とする。

このＲＯＭのデータ領域のうちｎビット（この領域をＡ
という。〕に対して、 ■　誤りパターンのうち、情報ビットに相当するｎビッ
ト例えば、第３図、Ｗ、４図において１Ｍ５Ｂより５ビ
ット、のパターンを格納する。

■　また、別の領域として、１ビット領域（Ｂという。

〕Ｋは、誤りパターン内のｔ４り箇所の数がｔのときＫ
は、パリティチェックが必要、あるいＨｌを未満のとき
には、パリティチェック不要のフラグ情報を格納する。

また生成多項式Ｇ（ｘＪの次数ｋに対しては、一般に２
１ｃ；［の剰余パターンが有るが一方誤り箇所の個数が
ｔ以下の誤りパターンの数は通常２に以下である。従っ
て、受信信号の剰余値（シンドローム）に対応し７ｊＲ
ＯＭのアドレスのうち、を以下の誤りパターンに対応し
ない剰余値も存在するため、この場合には例えばｎビッ
トデータ部（Ａ部〕を全てｌとして格納すればよい。

ここで、ｔ≦（ｎ−１）であるので、区別ができる。

また、復号方法としては、受信信号より算出し次シンド
ローム値より、上記ＲＯＭを用いて得られたｎ＋１ビッ
トの出力に対し、該出力値と受信信号との〃０算処理を
行う。この場合、加算する部分は受１言信号のうちのＭ
ＳＢｉのｎビットつまり情報ピットのみ若しくはｎ＋１
ビットまで加算してもどちらでも良い。そして、Ｂ領域
のパリティチェックフラグを参照し、チエツクが不要の
ときは、加算結果を訂正後のデータとして処理する。

ま之チエツクが要のときは、パリティチェックによる偶
奇判定の結果を参照し、パリティチェックによる誤り数
の偶奇判定がｔの偶奇と一致のときＫは、＠記加算結果
を訂正後のデータとして処理し、不一致のときは訂正不
能として処理する・第１図に本発明による復号回路の一
実施例を示す。図において、（１）はシンドローム算出
回路、（２）はＲＯＭであり、該ＲＯＭは前記の方ｆＥ
、により誤りパターンのデータが格納されている。（ｘ
）は加算回路、（４）は復号処理上発生する時間の遅延
を補償する回路であり、シフトレジスタ列等が用いられ
る。

また（５）はＲＯＭの出力を一旦ラッチする回路であり
、パラレル入力及びシリアル転送能力を有する（ｎ＋１
）ビットのシフトレジスタが用いらｎる６（６）はパリ
ティチェック回路であり、（７）はＲＯＭ出力における
Ｂ領域のフラグ入力及び（６）のパリティチェック回路
の偶奇結果人カエク、前記（ｘ）の加算結果を訂正後の
データとするか、訂正不能とするかを処理するディジタ
ル処理回路である。

さて受傷信号をＶ（２）、元のデータをＵ（ｘ）、また
伝送時に発生する誤ジのパターンをｇ（ｘ）とすると、
■（ｘ）−Ｕ（蜀＋Ｅ（蜀又はＵ（ト）−■（蜀＋Ｅ（
蜀となる。

復号処理におけるシンドローム値５（ｘ）は５（Ｘ）−
Ｖ図／Ｇ（蜀の剰余値 、Ｅ（蜀／Ｇ（蜀の剰余値である。

従って、受＠信号Ｖ（Ｘ）より水めたシンドローム値に
基いて、ＲＯＭ（２＋より得たパターン（但し、情報ビ
ット部に対応するもののみ）ｔ−受信信号Ｖ（ｘ）に、
ｍｘ丁れば、元の信号Ｕ（Ｘ）における情報ビット部に
ついて訂正か行なｆ）ｉｄ　。

一方、ディジタル処理回路（７）はＲＯＭ（２）のＢ領
域からのパリティチェックフラグを参照し、チエツクが
不要のときは、７ＩＯ算結果を訂正後のデータとして処
理を行なう。そして、チエツクが８畏のときは、パリテ
ィ検出口路（６）による偶奇判定の結果を参照し、パリ
ティチェックによる誤り数の偶奇判定が一致のときには
、７ＪＯＷ結果を訂正後のデータとして処理し、不一致
のときは訂正不能として処理する。

以上のように不発明に：れば、情報ビットｎ。

訂正ビットｍ、及び１ビットパリテイピツトが性別した
ｎ＋ｍ＋１ビットの符号に対し、ＲＯＭの所要データ領
域を ｌ）従来方Ｅ　　ｌ！Ｘｔビット（ＣＣＴ２’＞（ｎ＋
ｍ）となるｌの最小値ン ２）本発明の方法　　１＋１　　ビットと低減できる。

例えばｎ”ａ５　　ｍｇｌＱにおいて３ビット瞑り訂正
を行う場合、 １）従来は　４Ｘ３−１２ビット ２ン本発明　　６ビット と、”／２１ｃ　ＲＯＭ　０８＠７：）Ｅ低Ｒ”？？　
＊　ル。

（ト〕発明の効果 以上本発明に工れば、ＢＣＨ符号などにおいて多数ビッ
トの誤り訂正を行う復号に用いるＲＯＭの容重を従来方
法の場合に比べ大幅に低減することができ、実用上有用
である。

【図面の簡単な説明】

第１図は本発明に：る復号化回路の一例を示すブロック
図、第２因は従来の復号化回路を示すブロック図、第３
因はデータチャンネル伝送におけるヘッダ部の伝送フオ
マット図、第４図は誤りが発生した伝送フォーマット図
である。 １・・・シンドローム算出回路、２・・・ＲＯＭ（メモ
リフ、３・・・加算回路、４・・・遅延回路、５・・・
ラッチ回路、６・・・パリティチェック回路、７・・・
ディジタル処理回路。

Claims (1)

【特許請求の範囲】
1. （１）ビット長ｎの情報ビットに、生成多項式Ｇ（ｘ）
   （次数：ｋ）に基づく、ｋビット長の誤り訂正ビットを
   付加したｎ＋ｋビット長の符号にパリテイチェック用の
   ビットを付加したｎ＋ｋ＋１ビット長の符号のディジタ
   ルデータ伝送における復号方式であって、ｎ＋ｋビット
   長でｔビット以下の誤りパターンを前記生成多項式で徐
   した剰余値をアドレスとし、この誤りパターンのうち情
   報ビットに対応するｎビットの値に、更にパリテイチェ
   ックを行なうか否かのフラグ情報を付した値をデータと
   して格納したメモリを備え、パリテイビット部を除いた
   ｎ＋ｋビット長の受信信号を生成多項式Ｇ（ｘ）で除し
   た剰余値を補記メモリにアドレス値として入力し、この
   メモリより得られたｎビットの誤りパターンを受信信号
   に加算すると共に、前記メモリより得られるパリテイチ
   ェック用のフラグ情報を参照し、パリテイチェックが不
   要なときは、前記加算結果を訂正後のデータとみなし、
   パリテイチェックが必要なときは、パリテイチェックよ
   り得られた誤り数の偶奇判定結果が、ｔの偶奇と一致の
   ときは前記加算結果を訂正後のデータとみなし、不一致
   のときは訂正不能として処理することを特徴とする多数
   ビット誤り訂正方式。