JPH03186031A - 誤り訂正方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

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

【従来の技術】

データの誤りには、あるビットが０かも１或は１からＯ
に変化する誤りと、あるビットが抜けたり、余分なビッ
トが挿入されたりすることによる誤りとが考えられる。 以下では、ビットが０から１、または１から○に変化す
る誤りを単に誤りと呼び、それを訂正するための符号を
単に誤り符号と呼ぶこととし、これに対して、ビット抜
けまたはビット挿入による誤りを同期誤り、それを訂正
するための符号を同期誤り訂正符号と呼ぶこととする。 誤り訂正符号に関しては、今まで多くの研究が行なわれ
、ランダム誤りゃバースト誤りに対しては、これを訂正
するための優れた符号が提案されている。 しかしながら、従来のハミング距離的な考え方を用いる
訂正符号では、たとえ１ビツトのビット抜けまたはビッ
ト挿入であっても、それ以降のビットが全てずれてしま
うため、ビットずれ以降のビットが全て誤りとされる可
能性があり、誤り訂正能力の限界を越えてしまうため、
同期誤りに対しては有効な訂正を行なうことができなか
った。 従って、従来、同期誤りに対しては、訂正符号は用いず
、再同期を頻繁にとることによって、誤りの発生を防い
でいた。

【発明が解決しようとしている課題】

同期誤りは、その名の通り、データに対するクロック等
の同期がずれたときに起こるものと考えられる。このよ
うな誤りは、使用する通信系によっては単なる誤りより
多く発生する場合が考えられ、上述のごとき、再同期を
頻繁に取る方式は、全体の伝送効率を少なからず低下さ
せるとし）う欠点があった。 本発明は、上述の課題を解決し、簡単な符号を用いて同
期誤りが訂正可能な誤り訂正方式を提供することを目的
とする。 ［課題を解決するための手段および作用］上記課題を解
決するために、本発明の誤り訂正方式は、送信されるデ
ータの各ビットに順次ｌずつ異なる重みを乗じて加えた
パリティを生成する第１パリティ生成手段と、受信した
データの各ビットに順次１ずつ異なる重みを乗じて加え
たパリティを生成する第２パリティ生成手段と、該第２
パリティ生成手段により生成されたパリティと、前記第
１パリティ生成手段により生成されたパリティとを比較
演算する演算手段と、前記演算手段の演算結果により送
信データに対する受信データの誤りを検出する検出手段
と、該検出手段の検出結果に従って、検出された誤りを
訂正する訂正手段とを備えることにより、１ビツトのビ
ット抜けやビット挿入によって発生する同期誤りを訂正
可能としたものである。 【実施例１ 以下では１ビツトの同期誤りを訂正する符号を示す、同
期誤りにはビット抜けとビット挿入と力Ｓ考えられるが
、先ず１ビット抜けの場合につし）で説明する。 ｋビットの情報系列工を［Ｉ　、、　Ｉ　１１−１＋・
・・、工、。 ■、］として、送信側ではこの情報系列中の各ビットエ
、に重みｌを乗じた次のパリティＰ＋を付加して送信す
る。 Ｐ＋＝Σ１１１　　　　　　　　　　（１）伝送中にあ
るビットエ、が抜けるビット抜けｂ１生じたとすれば、
受信側では次のに一１ビットの情報系列工°と（１）式
に示したパリティＰｔを受は取る。 Ｉ’　　＝　［１，、Ｉｍ−＋、−・・ＩＩＪＩＩＩＩ
　　ＩＪ−ＩＩ・・・、１．．１．］ｌ′からＰ＋と同
様に、Ｌ＋Ｉｋ−’＋・・・、ＩＪ＋ｌ＋ＩＪ−１１・
・・、ＩＩ、ＩＩに、順にに、に−１，・・・、１を乗
じて加算し、Ｑ、を計算する。このとき、Ｉ　Ｊ−１以
降には、添え字より１大きい係数が掛けられ、次のよう
に計算される。 Ｑ、＝シエ、・　ｉ＋Σ−１１・（ｉ＋１）ここでＰ、
　−Ｑ、を計算すると、 （２） となる、ここで、ビット抜けが生じたＩＪがＯで■、＝
１であれば、ｊ〉Σ−１１より Ｐ　＋　−Ｑ　＋　＞　Ｏである。従って、Ｐ＋−Ｑｌ
の正負でビット抜けを起こした■４の値が分かる。 また、Ｐｌ−Ｑｌ≦Ｏ（ＩＪ　＝Ｏ）のとき、Ｉ　Ｊ−
１までの、値が１となるビットの総数を示し、■、から
数えて、　ＩＰ　＋　’−Ｑ　＋１１００１のところか
らＩ、＝Ｏのビット抜けによるビットずれが始まってい
ることが分かる。そこで、Ｐ　ｒ　−Ｑ　＋１１００１
の左にＯを挿入すれば、ビット抜けＩＪが訂正される。 Ｐ＋　−（１＞Ｏの場合、ｐｔ　−Ｑ＋　−１＝ｊ−１
−Σ−■１は１１からＩ、−３までのビットずれを起こ
したＯの総数を示す、（なぜなら、ビットずれを起こし
たビットの総数ｊ−１から、１の総数である土工、を引
けば、Ｏの総数になる。） そこで、Ｐ＋　−Ｑ＋−１個目の０の左に１を挿入すれ
ば■、＝１によるビット抜けが訂正される。 次に１ビツト挿入の場合を考える。 送信側で情報系列として、前出のに一１ビットのＩ　’
　＝　［Ｉ−、Ｌ＝−＋、・・・＋Ｌ＊ｌ＋　ＩＪ−１
＋・・・、１．．１．］とそのパリティとして次のＰｌ
を送信したとする。 ｐ、＝ΣＩ　１（ｉ−１）　　＋Σ“１１・ｉ　　　　
　（４）この情報系列の伝送中に、Ｉ、が挿入されて、
受信側では前記のＩを受は取ったと考えると、Ｉ　＝　
［Ｉｉ＋＋Ｌ＋−ｚ・・・、Ｌ−１，ＩＪ、Ｌ−１，・
・・、１．．１．］であるから、Ｑ１およびＱ、−Ｐ、
が次のように表わされる。 （６）式において、■。 Ｑ＋−Ｐ＋＝−Σ丁 ■、＝１ならば、 ＝Ｏならば、 ≦Ｏであり、 また。 Ｑ＋−Ｐ＋＝ｊ−ｔ−Σ−■、２０である。 従って、Ｑ　＋　　Ｐ　＋　＜　Ｏの場合はＩＪ　＝Ｏ
Ｑｌ　−ＰＩ　＞０の場合はＩ、＝１ であり、これらの場合は、（３）式と同様の議論により
、誤り位置を知り、そのビットを削除することによって
、ビット挿入による誤りを削除できる。 また、Ｑ＋−Ｐ＋＝Ｏの場合は、 Ｑ、−ｐＨ＝ＱかつＩ、＝Ｏならば、 −Σｌ１＝０より、　　ＩＪ−１＝・・・＝Ｉ＋＝０ま
た、Ｑ＋　　Ｐ＋＝０かつＩ、＝１ならば、Σ−Ｊ、＝
ｊ−１より、Ｉ、−１＝・・・＝　Ｉ　＋　＝　１であ
るから、いずれの場合もＩＪ＝・・・＝Ｉ、となるので
、最下位ビットを削除すればよい。 以上により１ビツト挿入の誤りが訂正できる。 次に、同期誤りではなく、１ビツトの単なる誤りが生じ
た場合を考える。 送信側で情報系列を１とし、そのパリティとして（１）
式のＰｌを送信し、伝送中にビットＩＪに誤りｅＪが付
加され、Ｉ４＋ｅＪとなったものと考える。（ｅ、はＩ
、が１のとき−１、工、が０のとき１と表わされる。） このとき、Ｑｌ及びＱ、−Ｐ、は次のように計算される
。 Ｑ、＝Σ■、・　ｉ　＋　ｅ　Ｊ　　・　ｊ　　　　　
　（７）Ｑ＋−Ｐ＋＝９．　　・　ｊ　　　　　　　　
　　　（８）ここで、ｅＪは１か−ｌであるので、（８
）式より、Ｑ、−Ｐ、の正負によってｅ、の値が分かり
、ｊ＝　　ＩＱＩ−ｐＨによって、誤りの位置ｊが分か
る。よってこれを訂正すればよい。 このようにして、１ビツトの単なる誤りが訂正可能とな
る。 以上によって、（１）式に示したごとき情報系列中のビ
ット１．に重みｉを掛けた本発明のパリティＰｌを用い
て、ビットの抜けやビットの挿入による１ビツトの同期
誤りと１ビツトの単なる誤りとが、訂正可能となった。 次に本発明を実際の回路を用いて実現する方法を示す。 第１図は、本発明の送信側で用いる符号器の構成を示す
図である。 同図において、情報系列工の各ビットエ、に、乗算器１
によって重みｉを掛け、順にレジスタ２に加えられ、パ
リティＰ、が生成される。 生成されたパリティＰ、は、情報系列工とともに、不図
示の送信機を用いて送信される。 第２図は、本発明の受信側で、１ビツトの抜けが生じた
場合に用いる復号器の構成を示す図である。 前記送信機により送信された情報系列工に、伝送中１ビ
ツトの抜けが生じて■゛となった場合、これとともにパ
リティＰ、を不図示の受信機により受信した受信側では
、符合器３によりパリティＱ１を生成する。ここで、符
号器３の構成は、送信側で用いている第１図に示したも
のと同一である。 比較器４では、符号器３で得られたパリティＱ、と受信
したパリティＰ、との大小を比較し、（３）式の議論に
従って、例えば、Ｐ、≦Ｑ、なラバ、演算器５で、Ｑｌ
−ｐ、を計算し、セレ：り７でその結果をセレクトする
。一方カウンタｊで１の数をカウントし、その結果をセ
レクタｌ（でセレクトし、比較／訂正器１１によってセ
レ＝り７及び１０の値を比較して、Ｑｌ−Ｐ１１００の
左にＯを挿入し、１ビツトの抜けが訂正さ才る。 Ｐ　＋　＞　Ｑ　Ｉの場合も、演算器６及びカウンタ≦
を用いて、同様に１ビット抜けが訂正可能とＣる。 〔発明の効果］ 本発明に用いた符号においては、 ｋ≧Ｐ、−Ｑ、≧−に＋１であるので、Ｐ。 Ｑｌは２にでモジュロをとることができる。こＣ場合、
２に一１≧Ｐ、−Ｑ、≧に＋１であ２Ｐ　＋　−Ｑ　＋
は負の値を意味し、Ｐ＋−Ｑｌ−２ｋによってその負の
値が得られ、その後は、ここに示した手順に従って誤り
の位置を求めることができる。 従って、Ｐ＋に必要なビットは１ｏｇ＊２にとなるので
、再同期を行なうことなどに比べると十分小さな冗長度
で、同期誤りを効率的に防ぐことができる。

【図面の簡単な説明】

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

Claims (1)

1. 【特許請求の範囲】 送信データに対する受信データの誤りを訂正する誤り訂
   正方式であって、 送信されるデータの各ビットに順次１ずつ異なる重みを
   乗じて加えたパリティを生成する第１パリティ生成手段
   と、 受信したデータの各ビットに順次１ずつ異なる重みを乗
   じて加えたパリティを生成する第２パリティ生成手段と
   、 該第２パリティ生成手段により生成されたパリティと、
   前記第１パリティ生成手段により生成されたパリティと
   を比較演算する演算手段と、前記演算手段の演算結果に
   より送信データに対する受信データの誤りを検出する検
   出手段と、該検出手段の検出結果に従って、検出された
   誤りを訂正する訂正手段とを備えることを特徴とする誤
   り訂正方式。