(57)【特許請求の範囲】
【請求項１】
送信者はあるビット数からなる総情報ビット群を私的通信路を介して受信者に伝送し、総受信者間の合意により該総情報ビット群を系列の誤り率を考慮して各ｋビットの複数の情報ブロックに分割し、送信者側において求めた各ブロックのパリティを公衆通信路を介して受信者に伝送し、受信者は受信者側において求めたパリティと受信した上記パリティとをブロック毎に比較し、受信者はパリティの相違により誤りを含んだ情報ブロックを抽出し、どの情報ブロックが誤りを含むかを公衆通信路を介して送信者に伝送し、送信者は限界式（ｋ＝２n-k）に基づいて検査ブロックを決定し、この決定された検査ブロックに基づいて対応する含誤り情報ブロック内の誤りビットを検出して訂正し、情報ブロックのビット数はｋであり、送信者は情報ブロックＪを持っており、受信者は情報ブロックＪ’を受け取ったとの前提において、前記の誤りの訂正に際して（１）送信者は前記の限界式によりｎの値を求め、（２）検査ブロックは（ｎ−ｋ）ビットであると決定し、（３）ｋを行とし、（ｎ−ｋ）を列として完全符号の生成行列を作成し、（４）Ｊ・Ｇ＝Ｋにより検査ブロックＫを作成し、（５）送信者は公衆通信路を介してこの検査ブロックＫを受信者に伝送し、（６）受信者は自分の受け取った情報ブロックＪ’に検査ブロックＫを加算して和Ｒを得て、（７）行列Ｇを転置してＧ(T)を得て、（８）この転置系列に単位行列を付加して行列Ｈを得て、（９）Ｒの転置系列Ｒ(T)を作成し、（１０）ＨとＲ(T)の乗算により積を得て、（１１）この積と合致する行列Ｈ内の列（ｍ）を探し出し、（１２）情報ブロックＪ’のｍ番目のビットを訂正することを特徴とする情報通信における対話方式の誤り訂正方法。
【請求項２】
送信者はあるビットからなる総情報ビット群を私的通信路を介して受信者に伝送し、送受信者間の合意により該総情報ビット群を系列の誤り率を考慮して各ｋビットの複数の情報ブロックに分割し、送信者側において求めた各ブロックのパリティを公衆通信路を介して受信者側に伝送し、受信者側では受信者側において求めたパリティと受信したパリティとをブロック毎で比較し、パリティの相違により誤りを含んだ情報ブロックを抽出して、どの情報ブロックが誤りを含むかを公衆通信路を介して送信者に伝送し、送信者は限界式（ｋ＝２k-1-1）に基づいて乱数発生器により１ビットの乱数系列を作成し、この乱数系列に基づいて対応する誤りを含んだ情報ブロック内の誤りビットを検出して、訂正し、情報ブロックのビット数はｋであり、送信者は情報ブロックＪを持っており、受信者は情報ブロックＪ’を受け取ったとの前提において、前記の乱数系列Ｌの作成と誤りの訂正に際して（１）前記の限界式により乱数系列Ｌのビット数ｌの値を計算して乱数系列Ｌを求め、（２）ｋ＝ｗ＋１を満たすｗを求めて、ｌ行でｗ列の既知の完全符号の生成行列Ｇ’を定め、（３）系列Ｌと行列Ｇ’との乗算によりビット数ｗの系列Ｗを求め、（４）情報ブロックＪの最初のｗビットと系列Ｗの対応するビット毎の排他的論理和を計算して、系列Ｙを形成し、（５）この系列Ｙを送受信者間で伝送し、（６）情報ブロックＪ’の最初のｗビットと系列Ｙの対応するビット毎の排他的論理和を計算して、系列Ｚを作成し、（７）この系列Ｚを転置して系列Ｚ(T)を作成し、（８）行列Ｇ’の後半（ｗ−ｌ）ビットを転置したものに単位行列を付加して（ｗ−ｌ）行でｗ列の行列Ｈを作成し、（９）行列Ｈと系列Ｚ(T)との乗算により積を得て、（１０）この積と合致する行列Ｈ内の列（ｍ）を探し出し、（１１）情報ブロックＪ’のｍ番目のビットを訂正する。ただしこの積が全ゼロ列ベクトルとなった場合には、情報ブロックＪ’の最後のビットを訂正することを特徴とする情報通信における対話方式の誤り訂正方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は情報通信における対話方式の誤り訂正方法に関するものであり、より詳しくは送受信者間において情報の伝送のための通信は私的通信路を介し情報を訂正するための通信は公衆通信路を介して対話形式で行うシステムにおいて、パリティ照合により抽出された誤りを含んだ情報ブロック内の誤りのあるビットを決定する技術の改良に関するものである。
【０００２】
この明細書において「情報ブロック」とは送信者が受信者に伝えたい系列構成するビットからなる単位集合を言う。また「検査ブロック」とは誤り訂正を行うのに必要なビットからなる単位集合を言う。
【０００３】
上記のような通信においては一般に、送受信者間の約定により全情報ビット群を各ｋビットからなる複数個の情報ブロックに分割する。そして各情報ブロックについてパリティ照合が行われる。
【０００４】
パリティ照合は送受信者間の約定に従って行われるが、一般には情報ブロック（ｋビット）内の１の数が偶数の場合にはパリティを０とし、奇数の場合にはパリティを１とする。この約定にしたがってパリティ照合が行われて、パリティの異なる情報ブロック（すなわち誤りを含んだ情報ブロック）が抽出される。
【０００５】
ところがこの方法では情報ブロック内の誤りが１個である場合には問題ないが、２個である場合にはその情報ブロックに誤りがあるか否かの判断ができないのである。そこで最初の全情報ビット群をランダムに並び替えて、上記と同様なパリティ照合を行う。
【０００６】
このパリティ照合の繰返しは送受信者間で約定した所定回数だけ行われる。そして所定回数繰り返した後に残った情報ブロックには「誤りがない」と統計的に推定する。そしてこの所定回数のパリティ照合で抽出された情報ブロックの各々について検査ブロック内における誤りの位置（つまりビット）を検出して、そのビットについて誤りの訂正が行われる。
【０００７】
この誤りビットの検出には「二分探索法」という手法が用いられていた。この手法においては（１）誤りがあるとして抽出された情報ブロック(ｋビット)を２個の子情報ブロック（１／２ｋビット）に分割し、（２）誤りのない子情報ブロックは無視して誤りのある子情報ブロック（１／２ビット）を２個の孫情報ブロック（１／４）に分割し、（３）誤りのない孫情報ブロックは無視して誤りのある孫情報ブロック（１／４ビット）を…という分割を繰り返してゆく。
【０００８】
この繰返し回数、すなわち通信回数は（ｌｏｇ2ｋ）で表わされるが、情報ブロックのサイズ（ｋ）が大きくなると通信回数が大きくなるという問題があった。つまり二分探索法に代わる誤りビット検出法の必要性が生じてきたのである。
【０００９】
この要請に応えて提案されたのが「検査ブロック」の利用という技術思想である。つまり誤りのある情報ブロックについて検査ブロックを形成して、これに基づいて誤りビットの検出を行うという手法である。つまり情報ブロック（ｋビット）と検査ブロック（ｎ−ｋビット）により総ブロック（ｎビット）が構成されるのである。
【００１０】
この検査ブロックを用いた従来技術としてはハミングの方法が知られている。この方法ではつぎのハミングの限界式を満たす検査ブロックを決定しようとするものである。
【００１１】
【数１】
0003949937.tif 000002
【００１２】
情報ブロックが１ビットすなわちｋ＝１の場合を具体的な例として挙げると、上記の限界式から計算してｎ＝３となる。すなわち情報ブロックは１ビットであり、検査ブロックは２ビットであり、総通信ブロックは３ビットとなる。
【００１３】
【発明が解決しようとする課題】
しかしこのハミングの方法では、誤りの検出に際して検査ブロックも考慮に入れているので、それだけ処理時間ひいては通信時間が長くなるという問題がある。
【００１４】
情報ブロックと検査ブロックとを考えた場合、情報ブロックには誤りの起きる可能性はあるが、検査ブロックには誤りは起きないのである。そこでこの発明にあっては、誤りの検出に際して、検査ブロックの存在は無視できるという点に着目したのである。
【００１５】
つまりこの発明は、情報通信における対話方式の誤り訂正作業における通信時間の低減、を目的とするものである。
【００１６】
【課題を解決するための手段】
このためこの出願の第１の発明においては、送信者はあるビット数からなる総情報ビット群を私的通信路を介して受信者に伝送し、総受信者間の合意により該総情報ビット群を系列の誤り率を考慮して各ｋビットの複数の情報ブロックに分割し、送信者側において求めた各ブロックのパリティを公衆通信路を介して受信者に伝送し、受信者は受信者側において求めたパリティと受信した上記パリティとをブロック毎に比較し、受信者はパリティの相違により誤りを含んだ情報ブロックを抽出し、どの情報ブロックが誤りを含むかを公衆通信路を介して送信者に伝送し、送信者は限界式（ｋ＝２n-k）に基づいて検査ブロックを決定し、この決定された検査ブロックに基づいて対応する含誤り情報ブロック内の誤りビットを検出して訂正することを要旨とするものである。
【００１７】
また第２の発明においては、送信者はあるビットからなる総情報ビット群を私的通信路を介して受信者に伝送し、送受信者間の合意により該総情報ビット群を系列の誤り率を考慮して各ｋビットの複数の情報ブロックに分割し、送信者側において求めた各ブロックのパリティを公衆通信路を介して受信者側に伝送し、受信者側では受信者側において求めたパリティと受信したパリティとをブロック毎で比較し、パリティの相違により誤りを含んだ情報ブロックを抽出して、どの情報ブロックが誤りを含むかを公衆通信路を介して送信者に伝送し、送信者は限界式（ｋ＝２k-1-1）に基づいて乱数発生器により１ビットの乱数系列を作成し、この乱数系列に基づいて対応する誤りを含んだ情報ブロック内の誤りビットを検出して、訂正することを要旨とする。
【００１８】
【実施例】
上記したようにこの出願の第１の発明は限界式（ｋ＝２n-k）を採用するものであるが、これには（１）誤りは情報ブロックのみに存在する、および（２）誤りを含む情報ブロックには必ず１個以上の奇数個の誤りがあるという２通りの条件が基となっている。
【００１９】
具体的な例として情報ブロックが２ビット、すなわちｋ＝２の場合を考える。
上記の限界式から計算してｎ＝３となるから、検査ブロックは（ｎ−ｋ）で１ビットである。この結果（情報ブロック＝２ビット：検査ブロック＝１ビット）を前記したハミングの方法の場合（情報ブロック＝１ビットで検査ブロック＝２ビット）と比較すると、ハミングの方法に比べてこの発明の場合には、情報ブロックは倍ビットなのに検査ブロックは半ビットとなっている。
【００２０】
つまりこの発明によれば、公衆通信路で伝送するビット数（各検査ブロックのビット数の総和）を小さくすることができ、通信回数が減って、結果的に通信時間が短くなる。
【００２１】
つぎにこの第１の発明による誤りビット検出作業の手順を逐次説明する。
【００２２】
（ａ）ステップ。誤りのある情報ブロックはｋビットであるとして、送信者は情報ブロックＪを有しており、受信者は情報ブロックＪ’を受け取ったものとする。
【００２３】
（ｂ）ステップ。受信者は限界式（ｋ＝２n-k）からｎの値を計算する。
【００２４】
（ｃ）ステップ。このｎの値を用いて検査ブロックは（ｎ−ｋ）ビットであると決定する。
【００２５】
（ｄ）ステップ。ついで完全符号の生成行列Ｇを作成する。つまり行数がｋであり、列数が（ｎ−ｋ）である行列を作成する。
【００２６】
（ｅ）ステップ。Ｊ・Ｇにより検査ブロックＫを作成する。
【００２７】
（ｆ）ステップ。送信者はこの検査ブロックＫを公衆通信路を介して受信者に伝送する。
【００２８】
（ｇ）受信者は受け取った情報ブロックＪ’に検査ブロックＫを付加して和Ｒを作成する。
【００２９】
（ｈ）ついで行列Ｇを転置してＧ(T)を作成する。
【００３０】
（ｉ）この転置された行列Ｇ(T)に単位行列を付加して和Ｈを作成する。ここで単位行列には（ｎ−ｋ）の行と列を有する系列で、かつ対角線に１がある系列を用いる。
【００３１】
（ｊ）前記の和Ｒの転置系列Ｒ(T)を作成する。
【００３２】
（ｋ）行列ＨとこのＲ(T)との乗算により積を作成する。
【００３３】
（ｌ）この積と合致する行列Ｈ内の列（ｍ）を探す。
【００３４】
（ｍ）受信者が受け取った系列Ｊ’中のｍ番目のビットに誤りがある。
【００３５】
（ｎ）したがって該ｍ番目のビットを１→０または０→１と訂正する。
【００３６】
【実験例】
上記したようなこの発明の各ステップを以下具体的な値について実験した結果を次の数式により示す。
【００３７】
【数２】
0003949937.tif 000003
0003949937.tif 000004
【００３８】
ついで第２の発明のステップを説明する。（ａ）ステップ。誤りのある情報ブロックはｋビットであるとして、送信者は情報ブロックＪを有しており、受信者は情報ブロックＪ’を受け取ったものとする。
【００３９】
（ｂ）ステップ。前記の限界式により乱数系列Ｌのビット数ｌの値を計算して乱数系列Ｌを求める。
【００４０】
（ｃ）ステップ。ｋ＝ｗ＋１を満たすｗを求めて、ｌ行でｗ列の既知の完全符号の生成行列Ｇ’を定める。
【００４１】
（ｄ）ステップ。系列Ｌと行列Ｇ’との乗算によりビット数ｗの系列Ｗを求める。
【００４２】
（ｅ）ステップ。情報ブロックＪの最初のｗビットと系列Ｗの対応するビット毎の排他的論理和を計算して、系列Ｙを形成する。
【００４３】
（ｆ）ステップ。この系列Ｙを送受信者間で伝送する。
【００４４】
（ｇ）ステップ。情報ブロックＪ’の最初のｗビットと系列Ｙの対応するビット毎の排他的論理和を計算して、系列Ｚを作成する。
【００４５】
（ｈ）ステップ。この系列Ｚを転置して系列Ｚ(T)を作成する。
【００４６】
（ｉ）ステップ。行列Ｇ’の後半（ｗ−ｌ）ビットを転置したものに単位行列を付加して（ｗ−ｌ）行でｗ列の行列Ｈを作成する。
【００４７】
（ｊ）ステップ。行列Ｈと系列Ｚ(T)との乗算により積を得る。
【００４８】
（ｋ）ステップ。この積と合致する行列Ｈ内の列（ｍ）を探し出す。
【００４９】
（ｌ）ステップ。情報ブロックＪ’のｍ番目のビットを訂正する。ただしこの積が全ゼロ列ベクトルとなった場合には、情報ブロックＪ’の最後のビットを訂正する。
【００５０】
【実験例】
上記したようなこの発明のステップを以下具体的な値について実験した結果を次の数式により示す。
【００５１】
【数３】
0003949937.tif 000005
【００５２】
【発明の効果】
以上から明らかなように、この発明によれば伝送する情報量は若干増加するものの、通信回数すなわち通信時間は大幅に減少するのである。より具体的にはこの発明の方法によった場合には、ハミングの方法によった場合に比べて伝送する情報量は約７〜１４％増加するが、通信回数は約１／４に削減できる。