JPH03186032A - 誤り訂正方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、光ディスクや光磁気ディスク、衛星通信等の
通信路において発生するデータの誤りを符号を用いて検
出・訂正する誤り訂正方式に関し、特にデータの同期ず
れによる誤りを検出・訂正する方式に関するものである
。

〔従来の技術１ データの誤りには、あるビットがＯから１或は１からＯ
に変化する誤りと、あるビットが抜けたり、余分なビッ
トが挿入されたりすることによる誤りとが考えられる。

以下では、ビットがＯかも１、または１から０に変化す
る誤りを単に誤りと呼び、それを訂正するための符号を
単に誤り符号と呼ぶこととし、これに対して、ビット抜
けまたはビット挿入による誤りを同期誤り、それを訂正
するための符号を同期誤り訂正符号と呼ぶこととする。

誤り訂正符号に関しては、今まで多くの研究が行なわれ
、ランダム誤りやバースト誤りに対しては、これを訂正
するための優れた符号が提案されている。

しかしながら、従来のハミング距離的な考え方を用いる
訂正６符号では、たとえ１ビツトのビット抜けまたはビ
ット挿入であっても、それ以降のビットが全てずれてし
まうため、ビットずれ以降のビットが全て誤りとされる
可能性があり、誤り訂正能力の限界を越えてしまうため
、同期誤りに対しては有効な訂正を行なうことができな
かった。

従って、従来、同期誤りに対しては、訂正符号は用いず
、再同期を頻繁にとることによって、誤りの発生を防い
でいた。

［発明が解決しようとしている課題ｊ 同期誤りは、その名の通り、データに対するクロック等
の同期がずれたときに起こるものと考えられる。このよ
うな誤りは、使用する通信系によっては単なる誤りより
多く発生する場合が考えられ、上述のごとき、再同期を
頻繁に取る方式は、全体の伝送効率を少なからず低下さ
せるという欠点があった。

本発明は、上述の課題を解決し、簡単な符号を用いて同
期誤りが訂正可能な誤り訂正方式を提供することを目的
とする。

【課題を解決するための手段および作用］上記課題を解
決するために、本発明の誤り訂正方式は、送信データの
各ビットの総和によりパリティを生成する第１パリティ
生成手段と、送信データの１シンボル内の各ビットに順
次１ずつ異なる重みを乗じて加え、更にシンボル全体に
ついて和をとってパリティを生成する第２パリティ生成
手段と、受信データの各ビットの総和によりパリティを
生成する第３パリティ生成手段と、受信データの１シン
ボル内の各ビットに順次１ずつ異なる重みを乗じて加え
、更にシンボル全体について和をとってパリティを生成
する第４パリティ生成手段と、前記第１パリティ生成手
段により生成されたパリティと、前記第３パリテイ生戒
手段により生成されたパリティとを比較演算する第１演
算手段と、前記第２パリティ生成手段により生成された
パリティと、前記第４パリティ生成手段により生成され
たパリティとを比較演算する第２演算手段と、各シンボ
ルの対応するビット同士の排他的論理和を求める第３演
算手段と、前記第１、第２及び第３の演算手段の演算結
果により送信データに対する受信データの誤りを検出す
る検出手段と、該検出手段の検出結果に従って、検出さ
れた誤りを訂正する訂正手段とを備えることにより、１
ビツトのビット抜けやビット挿入によって発生する同期
誤りを訂正可能としたものである。

［実施例］ 以下では１ビツトの同期誤りを訂正する符号を示す、同
期誤りにはビット抜けとビット挿入とが考えられるが、
先ず１ビット抜けの場合について説明する。

ｋシンボルの情報系列Ｉを［Ｉ□Ｉヶ−１・・・１、、
Ｉｌｌとする。ただし、各Ｉ、は、次のようなｑビット
からなるシンボルである。

Ｉ　＋　＝［ｒ＋、ｑ＋　Ｉｌ、＠−１＋・・・、　Ｉ
ｌｌ、　Ｉｌ、　ｌ］送信側ではこの情報系列■から次
のパリティＰ　、、Ｐ　、、Ｒｌを生成し、■に付加し
て送信する。

Ｐａ”Σ　（ｓ：Ｉｌ、ｈ）　　　　　　　　（１）Ｐ
ｌ　＝Σ　（Σ　Ｉ　、ｈ　　−ｔ）　　　　　　　　
　　（２）Ｐ　、　　＝ＥＸＯＲＩ　　Ｉ　　１ （３） ただし、ＥＸＯＲΣは、Ｉ＋の各ビットごとの排他的論
理和を示す、伝送中にあるシンボルＩ、中のあるビット
エＪ１が抜けるビット抜けが生じ、他のビットに誤りｅ
Ｊ、ＴＩが付加したとすると、シンボルＩ、のＩ４０．
を除く各ビットは工１．．ｌ＋ｅＪ、ｈと表わされる。

（ｅ４．ｈはＩＪ、１１がＯから１に誤るときｌ、ＩＪ
、１１が１からＯに誤るとき−１，誤りなしのときＯと
表わされる。）その受信データからＰ　ｏ　、Ｐ　＋　
と同様の手順によってＱ、、Ｑ、を生成すると次のよう
になる。

Ｑ　＋　　＝Ｐ　＋　　　　Ｉ　　ａ、１ｊ　　＋　Σ
　ｅ７．ｈ’ｊ　　＋　Σｈ、。

（５） 従って、Ｐａ　　Ｑ−１Ｐ＋　　Ｑｌは次のように表わ
される。

（７）式において未確定であるのは、 ｊと Σ−Ｌ、である。そこで、Ｐ、−Ｑ、≦０のときに、ｊ
をＸとし、ｘ−１までのシンボル毎の１のずれの総和で
あるΣ−Ｌ、をｙとすると、Ｘとｙの関係は、（７）式
から次のようになる。

ｙ＝　（ＱＯ−Ｐａ　）ｘ−（ｐｔ　−Ｑｌ　）　　（
ｓ）Ｐｏ−Ｑｏ≦の時、（７）式よりＰ＋−Ｑｔ≦０で
あるので、（８）式は第３図の直線ａのようにｘ＝Ｏの
とき正の値Ｑ　ＩＰ　＋から負の勾配を持ち、Ｘに従い
変化する。一方実際のシンボルの位置を表わすＸとそこ
までの１のずれの総和ｙの関係は、第３図直線すのよう
に、ｘ＝０のときｙ＝Ｏであり、Ｘに従って単調に増加
する。従って、直線ａとｂとは必ず１つの交点を持つ、
ｊは（７）式の表わす直！ａと実際のずれを表わすｂと
を同時に満足するはずであるので、直線ａとｂの交点と
なるＸの値がｊとなる。

また、Ｐａ　　Ｑ（１＞Ｏのとき、ｊ＝ｘ、ｘ−１まで
のシンボルごとのＯのずれの総和である（ｘ　−１）　
−”Ｘ−’Ｘ　１、をｙとすると、（７）式はｙ　＝−
（Ｐａ　　−Ｑｏ−１）　　ｘ＋　　（Ｐ　ＩＱ　ｌ−
１）　　　　　（９）Ｐ　ｏ　−Ｑ　−＞　Ｏのとき、
（７）式からＰ。

Ｑ　＋　　　１　＞　Ｏであるので、（９）式は（８）
式と同様に、第３図の直線ａのようにｘ＝０のとき正の
値Ｐ＋　−Ｑｌ−１から負の勾配−（ｐ、−Ｑ。

−１）を持ち、Ｘに従って変化する。

また、実際のシンボルの位置を表わすＸと、そこまでの
Ｏのずれの総和ｙとの関係も第３図のｂのように、ｘ＝
０のときｙ＝Ｑで、Ｘに従って単調増加する。従って、
Ｐ、−Ｑ、≦０のときと同様の議論が成り立ち、直線ａ
とｂとの交０点ｔ７）ｘの値がｊとなる。

以上のようにして、誤りを含む同期−誤りが生じている
位置ｊが得られる。誤りのパターンは、ずれの生じたｊ
以降のシンボルのずれを元に戻し、Ｉ、以外のシンボル
を確定し、Ｒ１に工、以外のシンボルをＥＸＯＲするこ
とにより、直接得ることができる。

ビット挿入による誤りが起こった場合も、ビット抜けの
場合の逆であると考えれば、同様の処理によって誤りを
含む同期誤りが訂正できることは明らかである。

また、ここでは同期誤りが１ビツトの場合に限って説明
してきたが、この符号は１シンボル内のランダムなＳビ
ットの同期誤りに対しても上記実施例と同様の手法で訂
正することができる。

以下に簡単な具体例を示す。

ｑ＝３、ｋ＝゛５として、次の情報系列工とパリティＰ
、　、Ｐ、　、Ｒ，を送信する。

Ｉ＝　［１１１１０１０００１００１００］Ｐ０＝７ Ｐ、＝５・３＋４・２＋３・０＋２・１　＋１−１　＝
２６旧＝０１０ ここで、伝送中にｊ＝３のシンボルＩｓ”［０００３に
誤りを含む同期誤りが生じ、Ｉｓ＝［１１］と誤ったと
すると、受信される情報系列Ｉ°とそれから計算される
Ｑ、、Ｑ、は次のようになる。

Ｉ＝　［１１１１０１１１１００１００］Ｑ０　＝　７ Ｐ、＝ｓ・３＋４・２＋３・３＋２・１＋１・１＝３４
従って、Ｐａ−Ｑ６、Ｐ、−Ｑ、は、 Ｐ、、−Ｑ、＝７−９＝−２ Ｐ＋−Ｑ、＝２６−３４＝−８ となる。

Ｐ　ｏ　−Ｑ　ｏ≦０であるので、（８）式に従い、ｙ
＝　（ｐｏ−ＱＯ’）Ｘ−（ｐ＋　−Ｑｌ　）＝−２ｘ
＋８ これとｙ’　＝”Ｘ−“１．の値を比較すると、ｘ＝：
の時のみｙとｙｏは一致する。そこでｊ＝３．！し、そ
れ以降のシンボルである１、、１．のず才を元に戻し、
■、塩以外シンボルを元に戻し、■、以外のシンボルを
次のように確定する。

［１１１１０，１７７７１００１００］Ｒ１にＩ、以外
のシンボルをＥＸＯＲすること＆により、１．＝　［０
００］が得られ、誤りを含むμｓ期誤りが訂正される。

次に本発明を実際の回路を用いて実現する方法を示す。

第１図は、本発明、の送信側で用いる符号器の構成を示
す図である。

第１ｒＩ！Ｉ（ａ）において、情報系列工の各シンボル
Ｉ、の各ビットＩ　１．Ｉ＋が、順にレジスタ２に加え
られ、パリティＰｏが生成される。第１図（ｂ）におい
て、情報系列■の各シンボルエ、の各ビットＩ　１．１
１に、乗算器３によって重みｉを掛け、順にレジスタ２
に加えられ、パリティＰ１が生成される。生成されたパ
リティＰ、、ｐ、は、情報系列工、ＥＸＯＲにょる出力
信号Ｒ，とともに、不図示の送信機を用いて送信される
。

第２図は、本発明の受信側で、１ビツトの抜けが生じた
場合に用いる復号器の構成を示す図である。

前記送信機により送信された情報系列Ｉに、伝送中１ビ
ツトの抜けが生じて■°となった場合、これとともにパ
リティＰ０、Ｐｌを不図示の受信機により受信した受信
側では、符号器３によりパリティＱ、　、Ｑ、を生成す
る。ここで、符号器３の構成は、送信側で用いている第
１図（ａ）（ｂ）に示したものと同一である。

比較器５では、符合器４で得られたパリティＱ０と受信
したパリティＰ０との大小を比較し、（７）〜（９）式
の議論に従って、例えば、Ｐ０≦Ｑ０ならば、 ｙ　＝　＜　ｐ　ｏ　−Ｑｏ　＞　ｘ　−＜　ｐ　ｒ　
−Ｑｌ）を計算し、セレクタ８でその結果をセレクトす
る。一方カウンタ９でｌの数をカウントし、その結果を
セレクタ１１でセレクトし、比較／訂正器１２によって
セレクタ８及び１１の値を比較して、両者が一致すると
きのＸの値をｊとし、する。

以上のようにして、誤りを含む同期誤りが生じている位
置ｊが得られる。誤りのパターンは、ずれの生じたｊ以
降のシンボルのずれを元に戻し、■、以外のシンボルを
確定し、ＲＩにＩ、以外のシンボルをＥＸＯＨすること
により、直接得ることができる。

［発明の効果］ 本発明に用いた符号においては、 ｑ≧Ｐａ−Ｑｏ≧−ｑであるので、ｐ、に必要なビット
は、ｌｏｇ＊２ｑとなるまた、ＰｌＲｌに必要なビット
は、各々ｌｏｇｓ　ｓｋ、ｑである。

従って、例えば、ｑ＝８．に＝２５３とした場合、必要
なパリティピット数はＰｏに対しては４ピツト、１ビツ
トずつの同期ずれ（ｓ＝＝１）のみを対象とした場合、
ＰＩ　Ｒ１に対して各々８ビツトずつ必要となるので必
要であるので、合計２０ビツト必要となる。これは、線
形の誤り符号の中で最も冗長度が低いといわれるリード
・ソロモン符号と比較しても、１シンボル訂正の場合、
リード・ソロモン符号は１６ビツト必要となり、その差
は４ビツトに過ぎない０本発明の符号は、単なる誤り訂
正符号ではなく、同期誤りをも訂正することを考えれば
、これは十分小さな冗長度であｑ、同期誤りを効率的に
防ぐことができる。

【図面の簡単な説明】

第１図（ａ）、（ｂ）は、本発明１実施例の符号器のブ
ロック構成を示す図、 第２図は、本発明ｉ実施例の復号器のブロック構成を示
す図である。 第３図は、符号の関係を表わすグラフである。 ｌ　、　２　・・・ ３　・・・ ４　・・・ ５　・・・ ６　、７　・・・ ８　、１１・・・ ９　、　ｌＯ・・・ １２・・・ レジスタ 乗算器 符合器 比較器 演算器 セレクタ カウンタ 比較／訂正器 第 ■ 図 （ ） 第 図 （ ） 第２図

Claims (1)

1. 【特許請求の範囲】 所定ビットからなるシンボルの複数によって構成される
   送信データに対する受信データの誤りを訂正する誤り訂
   正方式であって、 送信データの各ビットの総和によりパリティを生成する
   第１パリティ生成手段と、 送信データの１シンボル内の各ビットに順次１ずつ異な
   る重みを乗じて加え、更にシンボル全体について和をと
   ってパリティを生成する第２パリティ生成手段と、 受信データの各ビットの総和によりパリティを生成する
   第３パリティ生成手段と、 受信データの１シンボル内の各ビットに順次１ずつ異な
   る重みを乗じて加え、更にシンボル全体について和をと
   ってパリティを生成する第４パリティ生成手段と、 前記第１パリティ生成手段により生成されたパリティと
   、前記第３パリティ生成手段により生成されたパリティ
   とを比較演算する第１演算手段と、 前記第２パリティ生成手段により生成されたパリティと
   、前記第４パリティ生成手段により生成されたパリティ
   とを比較演算する第２演算手段と、 各シンボルの対応するビット同士の排他的論理和を求め
   る第３演算手段と、 前記第１、第２及び第３の演算手段の演算結果により送
   信データに対する受信データの誤りを検出する検出手段
   と、 該検出手段の検出結果に従って、検出された誤りを訂正
   する訂正手段とを備えることを特徴とする誤り訂正方式
   。