JP5062643B2 - 誤り訂正符号化装置、誤り訂正符号化方法及びプログラム - Google Patents

Description

本発明は、誤り訂正符号化装置、誤り訂正符号化方法及びプログラムに関し、詳しくは、データ表現の冗長性に基づく誤り訂正符号化装置、誤り訂正符号化方法及びプログラムに関する。

今日、あらゆるデジタル通信の分野において、通信路で発生した誤りを訂正するための誤り訂正符号の技術が用いられている。ここで、「通信」とは、一般的に有線や無線などの通信媒体を介して行われる離隔点間の情報伝送のことをいうが、本明細書では、このような狭い意味に限定しない。たとえば、コンパクトディスクなどの記録媒体に情報を記録することも「通信」の概念に含める。情報を送るとは、離れた場所に情報を運ぶことであり、記録するとは、後日の読み出しを想定して離れた（後日の）時間へ情報を運ぶことであるからであり、両者とも情報を運ぶ点で同じ意味だからである。

符号理論で取り扱うのは、デジタル化された情報である。送りたいデータは、オーディオ信号やビデオ信号などをデジタル化したもの、あるいは計算機からのデジタルデータなどであろう。これらの情報の発生源や、それをデジタル化する部分などを含めて情報源という。デジタル化された情報（送りたいデータ）は、たとえば、ＰＣＭ信号を考えれば分かるように、０，１の２種類の記号（数字）を使って、ビット列として表されていることが多い。このため、本明細書においても、送りたいデータはビット列、あるいは、より一般的にディジット列で表されているものとする。

図３は、通信系のモデルを示す図である。この図において、情報源からは、送りたいデータとして０，１のビット列（情報ビット列）が発生する。符号器（誤り訂正符号化装置）は、この情報ビット列を、ｍビットごとのブロックに区切って取り扱う。各ブロックを“送りたいデータ”と呼び、この送りたいデータをｉ＝（ｉ₁，・・・・，ｉ_m）で表す。

符号器は、送りたいデータｉに対応したｎビット（ｎ＞ｍ）の符号語ｗ＝（ｘ₁，・・・・，ｘ_n）を出力する。すなわち、この符号器で、ｎ−ｍビットの余分なビット（冗長ビット）を付加する。ｎを符号長、ｍを情報ビット数といい、この操作のことを「符号化」という。通信路に送り出された符号語を送信語ｗといい、通信路は、この送信語ｗが入力されるとｎビットの受信語ｖを出力する。伝送・記録媒体の雑音などの影響がなければ、送信語＝受信語であるが、通常は雑音などのために、送信語の各ビットの０，１がある確率で異なって受信される。これを誤りといい、この様子を、通信路において各ビットに誤りｅが加わったとして、ｖ＝ｗ＋ｅで表す。ただし、ｊ番目のビットの誤りをｅ_jとし、ｅはビット列ｅ＝（ｅ₁，・・・・，ｅ_n）を表し、誤りパターンとも呼ばれる。復号器は、受信語ｖを元に、いずれの符号語が送信されたかを推定し、送信語ｗの推定値または送りたいデータｉの推定値を出力する。

なお、実際の伝送路または記録媒体には、送信語ｗの各ビットｘ_jに対応して、たとえば“０”の場合はパルスなし、“１”の場合はパルスあり、といった信号波形として送り出されるが、説明の便宜上、本明細書では具体的な波形に言及しない。

さて、このような符号長ｎ、情報ビット数ｍの符号化のことを［ｎ，ｍ］符号化といい、２^m通りある符号語の集合のことを［ｎ，ｍ］符号という（たとえば、特許文献１、特許文献２）。

より一般的に、ガロア体ＧＦ（ｑ）上の［ｎ，ｍ］線形誤り訂正符号とは、ＧＦ（ｑ）ⁿのｍ次元線形部分空間のことである。ＧＦ（ｑ）は元の数がｑであるような有限体である。ＧＦ（ｑ）ⁿは、ＧＦ（ｑ）の元をｎ個並べてできるべクトル（数ベクトル）の集合であるが、慣習に従い、ＧＦ（ｑ）上の数ベクトルを横ベクトルで表すことにする。

線形符号を用いた従来の符号化では、次のようにデータを符号化する。まず、［ｎ，ｍ］線形誤り訂正符号（以下、線形符号Ｃという。）の基底を（ｇ₁，・・・・，ｇ_m）とする。符号化すべき長さｍのストリングを、ＧＦ（ｑ）上の数ベクトルとして、次式（１３）で表す。なお、線形符号Ｃの具体例としては、標準的な符号理論の教科書（たとえば、“Ｔｈｅ Ｔｈｅｏｒｙ ｏｆ Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅｓ”，Ｆ．Ｊ．ＭａｃＷｉｌｌｉａｍｓ ａｎｄ Ｎ．Ｊ．Ａ．Ｓｌｏａｎｅ，ＮＯＲＴＨ−ＨＯＬＬＡＮＤ，ＩＳＢＮ：０−４４４−８５１９３−３／０−４４４−８５００９−０／０−４４４−８５０１０−４）に記載されているように、ハミング符号、ＢＣＨ符号、ゴッパ符号など様々なものがある。

以下では、このようなデータを（長さｍの）ベクトル、あるいはＧＦ（ｑ）上の長さｍのベクトルと呼ぶことにする。これを、次式（１４）により、線形符号Ｃに属するベクトルｆ（ｘ）に符号化する。もちろん、演算はＧＦ（ｑ）上で行う。たとえば、ｑが素数のときは、ｑ個の数字“０，１，・・・・，ｑ−１”とｍｏｄｑ計算法のもとで行う。

ｇ_i＝（ｇ_i1，・・・・，ｇ_in）（ｉ＝１，・・・・，ｍ）のとき、次式（１５）は、線形符号Ｃの生成行列と呼ばれる。

このような公知の符号化は、既述のとおり、［ｎ，ｍ］符号化であり、特に具体的に符号化を指定するためには、上記の符号化を生成行列Ｇにより指定される［ｎ，ｍ］符号化と呼ぶ。この［ｎ，ｍ］符号化では、ｎ個のディジット（ＧＦ（ｑ）の元）を使って、ｍディジット分の情報を送っている。線形符号Ｃ（つまり生成行列Ｇにより指定される［ｎ，ｍ］符号化）は、ｑ＝２のときが最もよく用いられる。このときＧＦ（ｑ）＝｛０，１｝となる。なお、ｑ＝２のとき「ディジット」は「ビット」と呼ばれる。なお、線形符号Ｃとその生成行列Ｇの具体例も、上記の標準的な符号理論の教科書に諸々記載されている。

特開２００５−１１０２５１号公報 特許第３２８１９３８号公報

しかしながら、上述した公知の［ｎ，ｍ］符号は、誤り訂正の能力は充分であるものの、伝送途中の盗聴対策が不完全であり、セキュリティに欠けるという問題点がある。すなわち、通信路に入力された送信語ｗや通信路から出力された受信語ｖを第三者に盗聴されてしまった場合、元の送りたいデータｉを容易に推定されてしまうという問題点がある。

そこで、本発明の目的は、セキュリティ対策を講じた誤り訂正符号化装置、誤り訂正符号化方法及びプログラムを提供することにある。

請求項１記載の発明は、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル

に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、

を生成行列Ｇ_iによって指定される[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル

に符号化する第２符号化手段と、ｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる［ｗ⁽¹⁾・・・・ｗ^(N)］を符号化結果として出力する出力手段とを備えたことを特徴とする誤り訂正符号化装置である。
請求項２記載の発明は、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル

に符号化する第１符号化工程と、ｉ＝１，・・・・，Ｎに対して、

を生成行列Ｇ_iによって指定される[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル

に符号化する第２符号化工程と、ｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる［ｗ⁽¹⁾・・・・ｗ^(N)］を符号化結果として出力する出力工程とを含むことを特徴とする誤り訂正符号化方法である。
請求項３記載の発明は、コンピュータに、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル

に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、

を生成行列Ｇ_iによって指定される[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル

に符号化する第２符号化手段と、ｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる［ｗ⁽¹⁾・・・・ｗ^(N)］を符号化結果として出力する出力手段とを実現させるためのプログラムである。
請求項４記載の発明は、前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段を備えたことを特徴とする請求項１記載の誤り訂正符号化装置である。
請求項５記載の発明は、前記出力工程から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力工程を含むことを特徴とする請求項２記載の誤り訂正符号化方法である。
請求項６記載の発明は、コンピュータに、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル

に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、

を生成行列Ｇ_iによって指定される[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル

に符号化する第２符号化手段と、ｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる［ｗ⁽¹⁾・・・・ｗ^(N)］を符号化結果として出力する出力手段と、前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段とを実現させるためのプログラムである。

説明の便宜上、[[ｎ，ｋ]]符号を[[４，１]]符号とし、送りたいデータを｛０，１｝とすると共に、たとえば、送りたいデータの“０”を｛００００，１１１１｝、送りたいデータの“１”を｛００１１，１１００｝と符号化するものとする。本発明では、データを送る際に、その｛ ｝内のいずれか一つのパターンがランダムに選択されて送信される。たとえば、データ“０”のパターンは、“００００”と“１１１１”であるので、その一方をランダムに送信するなどである。このようにすれば、仮に伝送途中の第三者がそのパターンの一部を盗聴し得たとしても、元のデータを推定することはできない。これは、たとえば、“００”を盗聴できたとしても、この“００”は、データ“１”のパターンにも含まれているからである。
したがって、本発明によれば、セキュリティ対策を講じた誤り訂正符号化装置、誤り訂正符号化方法及びプログラムを提供することができる。

第１の実施形態（[[ｎ，ｋ]]符号化）の概念ブロック図である。 第２の実施形態（二段階符号化）の概念的な処理フローを示す図である。 通信系のモデルを示す図である。

以下、本発明の実施形態を説明する。
まず、言葉の定義として、長さａのベクトルｘ＝（ｘ₁，・・・・，ｘ_a）と長さｂのベクトルｙ＝（ｙ₁，・・・・，ｙ_b）を繋げてできる長さａ＋ｂのベクトル（ｘ₁，・・・・，ｘ_a，ｙ₁，・・・・，ｙ_b）を［ｘｙ］で表すことにする。このとき、ｘにｙを連接して［ｘｙ］を得るという。３つ以上のベクトルについても“［”と“］”で括ったもので、同様に連接してできるベクトルを表す。たとえば、［ｘｙｚ］は、ｘにｙを連接し、それにさらにｚを連接してできるベクトルを表す。

＜第１の実施形態（[[ｎ，ｋ]]符号化）＞
図１は、第１の実施形態（[[ｎ，ｋ]]符号化）の概念ブロック図である。このブロックは、冒頭で説明した通信系のモデル図（図３）における符号器として用いることができるものを模式的に表している。このブロックの具体的な構成については特に言及しない。たとえば、ハードロジックで構成されていてもよいし、あるいは、その全てまたはその主要な機能の一部がコンピュータで実行可能なソフトウェアで構成されていてもよい。いずれにせよ、以下に説明する機能を実現できる構成になっていればよい。

図示のブロック全体の名称は、たとえば、冒頭の通信モデルのように、符号器と呼称しても構わないが、ここでは、従来技術の［ｎ，ｍ］符号化と区別するために、二重の括弧を用いて[[ｎ，ｋ]]符号化部１と称することにし、さらに、この[[ｎ，ｋ]]符号化部１による符号化のことを、[[ｎ，ｋ]]符号化と称することにする。

[[ｎ，ｋ]]符号化部１は、少なくとも、ｕ発生部２、ｘ´生成部３及び［ｎ，ｍ］符号化部４を含む。ｕ発生部２は、たとえば、物理的な乱数発生器または疑似乱数発生器であり、［ｎ，ｍ］符号化部４は、従来技術の［ｎ，ｍ］符号化に相当する操作を行うものである。

この第１の実施形態では、情報のセキュリティを確保するため、以下の新しい符号化を行う。この方式は、簡単にいえば、冒頭で説明した公知の［ｎ，ｍ］符号化を用いてｋディジット分の情報を送るというものである。ただし、ｋ≦ｍである。

今、送りたいデータｘが、次式（２８）のようなものであるとする。

ｘ´生成部３は、このデータｘに、ｕ発生部２でランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ_k+1，・・・・，ｘ_m）を連接して、次式（２９）のｘ´を得る。

［ｎ，ｍ］符号化部４は、前記の生成行列Ｇによって指定される［ｎ，ｍ］符号化を用いて、ｘ´生成部３で演算されたｘ´を、長さｎのベクトルｆ（ｘ´）に符号化する。

このように、この第１の実施形態では、送りたいデータｘにランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ_k+1，・・・・，ｘ_m）を連接してｘ´を生成し、そのｘ´を、［ｎ，ｍ］符号化を用いて長さｎのベクトルｆ（ｘ´）に符号化し、それを出力する。

この第１の実施形態における符号化は、前記のとおり、 [[ｎ，ｋ]]符号化であり、生成行列Ｇを変えることで異なる符号化が得られるため、特に符号化を具体的に指定するためには、これを、生成行列Ｇによって指定される[[ｎ，ｋ]]符号化と呼ぶ。この[[ｎ，ｋ]]符号化のイメージは、次式（３０）のように示すことができる。

式（３０）の全体は、図１の[[ｎ，ｋ]]符号化部１に相当する。さらに、ｘ→ｘ´の部分はｘ´生成部３に相当し、ｘ´→ｆ（ｘ´）の部分は［ｎ，ｍ］符号化部４に相当する。

ここで、前記の“発明の効果”の欄で挙げた例が、この第１の実施形態の[[ｎ，ｋ]]符号化で実現できることを説明する。線形符号Ｃの基底を（ｇ₁，・・・・，ｇ_m）とし、このうち（ｇ_k+1，・・・・，ｇ_m）の張る部分空間をＢとするとともに、ｎ＝４、ｋ＝１、ｍ＝２とすれば、ｇ ₁ 、ｇ ₂ の一例は、次式（３１）、（３２）のように書き表すことができ、線形符号Ｃの一例は、次式（３３）のように書き表すことができ、また、Ｂの一例は、次式（３４）のように書き表すことができる。なお、これらは、ＧＦ（ｑ）＝ＧＦ（２）の場合の例である。

前記のとおり、ｇ₁、ｇ₂は、前式（３１）及び前式（３２）のように書き表すことができる。すると、次式（３５）のように、ｕ発生部２でｘ₂＝０，１がランダムに発生されるから、送りたいデータがｘ₁＝０であるか、ｘ₁＝１であるかに応じて、[[ｎ，ｋ]]符号化器１の出力は、｛００００，１１１１｝か｛１１００，００１１｝になる。ただし、ここでは、ベクトル（１，１，１，１）を“１１１１”と書くなどした。

このように、この第１の実施形態によれば、送りたいデータｘにランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ_k+1，・・・・，ｘ_m）を連接してｘ´を生成し、そのｘ´を、［ｎ，ｍ］符号化を用いて長さｎのベクトルｆ（ｘ´）に符号化することにより、ｋディジット分の情報を生成出力することができるので、以下の理由から、情報のセキュリティを確保することができる。

今、簡単化のために、[[ｎ，ｋ]]符号を[[４，１]]符号とし、送りたいデータを｛０，１｝とする。この場合、第１の実施形態では、たとえば、送りたいデータの“０”を｛００００，１１１１｝、送りたいデータの“１”を｛００１１，１１００｝と符号化し、データを送る際に、その｛
｝内のいずれか一つのパターンをランダムに選択して送信する。たとえば、データ“０”のパターンは、“００００”と“１１１１”であるので、その一方をランダムに送信する。仮に伝送途中の第三者がそのパターンの一部を盗聴し得たとしても、元のデータを推定することはできない。これは、たとえば、“００”を盗聴できたとしても、この“００”は、データ“１”のパターンにも含まれているからである。

したがって、この第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）においては、伝送途中の第三者による盗聴を効果的に防止し、セキュリティ対策を講じることができるので、本発明の冒頭の課題を達成することができる。

＜第２の実施形態（二段階符号化）＞
以上説明した第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）においては、セキュリティ対策を講じることができる点で有益である。一方で、理論的な解析により比較的符号長が長い方が復号誤り確率と安全性の点で有利であることは分かっているものの、符号長が長くなるにつれ、符号化や復号化の手続きの煩雑さが増していくことを否めず、この手続きの煩雑さが、実用化する上での障害となる可能性がある。上記のとおり、[[ｎ，ｋ]]符号化は、通信路上での盗聴を回避できるという従来技術にない格別有益なメリットを持つため、かかる障害要因（手続きの煩雑さ）の克服は、是非とも達成されなければならない技術課題である。以下に説明する第２の実施形態は、そのためのものである。簡潔に述べれば、この第２の実施形態は、分割統治の考え方（与えられた問題をいくつかの小さな問題に分割して解き、それをもとに統治をおこない、問題の解を得る手法のこと。分割統治法：Ｄｉｖｉｄｅ
ａｎｄ Ｃｏｎｑｕｅｒともいう。）を採用して、大きな符号長を持つ[[ｎ，ｋ]]符号化と同等の符号化の処理をいくつかの処理に分けて段階的に行うことにより、前記の障害要因を克服し、以て、産業上の利用に充分に耐え得る誤り訂正符号化の技術を提供するものである。

第２の実施形態について説明する。この第２の実施形態では、以下に詳述するように、一例として、２つの線形符号を使って符号化する方法を開示する。以下、この符号化のことを「二段階符号化」という。

この二段階符号化では、Ｎ＞０，ｎ_i≧ｍ_i≧ｋ_i≧０（ｉ＝１，・・・・，Ｎ）を整数（実用的なのは、ｎ_i，ｍ_i，ｋ_iがｉに依らない場合である。）とするとき、ｍ_i×ｎ_i生成行列Ｇ_iにより指定される[[ｎ_i，ｋ_i]]符号化と、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆにより指定される[[Ｎ´，Ｋ´]]符号化とを組み合わせて符号化する。この二段階符号化はトータルとしてＮ″ディジットを使いＫ´ディジットの情報を送っているという意味で[[Ｎ″，Ｋ´]]符号化と同等の伝送効率を持つ。ただし、Ｎ´とＮ″は、次式（３６）で与えられる。

具体的な二段階符号化の方法は、以下のようになる。ここで、送信データの長さはＫ´である。

図２は、第２の実施形態（二段階符号化）の概念的な処理フローを示す図である。この処理フローは、冒頭で説明した通信系のモデル図（図３）における符号器として用いることができるものを模式的に表している。前記の第１の実施形態と同様に、この処理フローは、ハードロジックで構成されていてもよいし、あるいは、その全てまたはその主要な機能の一部がコンピュータで実行可能なソフトウェアで構成されていてもよい。いずれにせよ、以下に説明する機能を実現できる構成になっていればよい。

この処理フローにおいて、まず、ステップＳ１の[[Ｎ´，Ｋ´]]符号化で、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、任意の送りたいデータを、長さＮ´のベクトルに符号化する。このベクトルは、Ｎ個のブロックに分割して、次式（３７）のように書くことができる。

次いで、ステップＳ２の[[ｎ_i，ｋ_i]]符号化で、ｉ＝１，・・・・，Ｎに対して、

を生成行列Ｇ_iによって指定される[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル

に符号化する。

そして、最後のステップＳ３で、ｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる［ｗ⁽¹⁾・・・・ｗ^(N)］を符号化結果として出力する。

ここで、ステップＳ１で用いる符号について、特に有用なのは、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆで指定される[[Ｎ´，Ｋ´]]符号化が、ＧＦ（ｑ）の拡大体ＧＦ（ｑ^k）上の符号に由来する場合である。この場合、たとえば、ＧＦ（ｑ^k）上のリード・ソロモン符号を使用することができる。実用上、ＧＦ（ｑ^k）上の［Ｎ，Ｋ］リード・ソロモン符号は、ＧＦ（ｑ）上の［ｋＮ，ｋＫ］符号として用いられている。たとえば、コンパクトディスクに用いられているリード・ソロモン符号などである（ｑ＝２）。

すなわち、ステップＳ１の[[Ｎ´，Ｋ´]]符号化では、従来の［ｎ，ｍ］符号化に相当する［Ｎ´，Ｍ´］符号化を用いることができるが、この部分では、ＧＦ（ｑ^k）上の［Ｎ，Ｍ］符号をＧＦ（ｑ）上の［ｋＮ，ｋＭ］符号として用いることができる。ただし、Ｎ´＝ｋＮ，Ｍ´＝ｋＭとおく。

なお、これは、ＧＦ（ｑ^k）の元を、ＧＦ（ｑ）上の長さｋのベクトルとして表現して得られるものである。具体的には、以下のとおりである。今、ＧＦ（ｑ）上の線形空間であるＧＦ（ｑ^k）の基底をｂ＝（β_j）^k _j=1とする。これを用いて、いかなる要素ζ∈ＧＦ（ｑ^k）も、次式（４０）のように書くことが可能であるので、このように得られた数の行ベクトル（ｘ₁，・・・・，ｘ_k）を、φ（ζ）の記号で示すことにする。

この変換「ζ→φ（ζ）＝（ｘ₁，・・・・，ｘ_k）」を用いた対応「ξ＝（ξ₁，・・・・，ξ_N）←→［φ（ξ₁）・・・・φ（ξ_N）］」により、ＧＦ（ｑ^k）上の長さＮのベクトルξと、ＧＦ（ｑ）上の長さｋＮのベクトル［φ（ξ₁）・・・・φ（ξ_N）］とを同一視することができるようになる。

二段階符号化の具体例を説明する。ｎ_i，ｍ_i，ｋ_iがｉに依らない場合、すなわち、ｎ≧ｍ≧ｋ≧０を整数として、ｎ_i＝ｎ，ｍ_i＝ｍ，ｋ_i＝ｋ（ｉ＝１，・・・・，Ｎ）の場合の具体例を挙げる。上記のステップＳ１では、前述したような［ｋＮ，ｋＭ］符号化を用いる。たとえば、ｑ＝２で、ｋ＝４ならば、リード・ソロモン符号による［４・１５，４Ｍ］符号化を用いることができる。ただし、０＜Ｍ≦１５である。この場合、上記のステップＳ１では、次式（４１）が得られる。

ステップＳ２では、同一の生成行列Ｇによって指定される[[ｎ，ｋ]]符号化を、ｙ₁ ⁽ⁱ⁾，・・・・，ｙ_k ⁽ⁱ⁾に適用してもよい（ｉ＝１，・・・・，Ｎ）。たとえば、ｎ＝６のとき、次式（４２）〜（４６）として、第ｉ行がg_iであるような生成行列Ｇによって指定される[[６，４]]符号化を行う。このように、生成行列Ｇによって指定される[[６，４]]符号化の出力は、ハミング重みが偶数であるようなベクトルとなる。

なお、上記において、拡大体ＧＦ（ｑ^k）上の符号について取り扱ったのは、このような符号を用いると効率の良い復号を行うことができるからである。しかし、これは、性能的に最良（ベストモード）の実施態様を例示しているに過ぎない。したがって、本発明は、この拡大体ＧＦ（ｑ^k）上の符号を使用するケースに限定されない。

以上のとおり、この第２の実施形態においては、分割統治の考え方を採用して、大きな符号長を持つ[[ｎ，ｋ]]符号化と同等の符号化の処理をいくつかの処理に分けて段階的に行うようにしたので、符号化や復号化の手続きを効率的に行うことができ、手続きの簡素化を図ることができる。したがって、先に説明した第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）の利点（セキュリティ対策を講じることができる。）を活かしつつ、[[ｎ，ｋ]]符号化の長い符号長に伴う欠点（符号化や復号化の手続きの煩雑さ）を解決し、実用に耐え得る誤り訂正符号化の技術を提供することができる。

なお、この第２の実施形態は、二段階符号化に関するものであるが、二段階に限らず、三段階以上のものも包含する。これは、三段階以上の場合、二段階符号化を手続きの一部に含むからである。したがって、発明にとって必須な事項は、二段階符号化に関する部分（図２のステップＳ１、ステップＳ２）にあるということができる。

前記第１の実施形態は[[ｎ，ｋ]]符号化に関するものであり、また、前記第２の実施形態は二段階符号化に関するものである。これら二つの実施形態は、前式（３０）で示したとおり、たとえば、従来の［ｎ，ｍ］符号化をブラックボックス化することによって極めて単純に構築することができる。これを補足すると、次式（４７）のようになる。

この式（４７）より、前記二つの実施形態は、結局、「通信路または記憶デバイス」へ入力する前の部分だけの符号化法であるということができる。

ちなみに、本発明の本質ではないものの、「復号器」についても言及すれば、前記二つの実施形態に対応する復号器の中身は、概ね次式（４８）のように書き表すことができる。

ここで、ｘ，ｕの推定値はそれぞれ、次式（４９）で与えられる。

以上のことから、二段階符号化もトータルとして見れば、次式（５０）のような方式と同等と見なすことができるので、上式（４８）の復号原理を適用することができる。

ただし、効率の点では、二段階符号化に対応した二段階の復号化を適用することが望ましい。これは、公知の二段階符号化＝連接符号の復号に類似する。

なお、前記第１の実施形態において、［ｎ，ｍ］符号化部４の［ｎ，ｍ］符号化は、“生成行列Ｇによって指定される”としてあるが、これは具体例として挙げたある特定の符号の生成行列Ｇに限定されない。［ｎ，ｍ］線形符号の生成行列であれば、ある特定の生成行列Ｇに限らず、全て使用することができる。このことは、第２の実施形態における二段階符号化でも同様である。

また、先に述べたとおり、前式（４７）は、『前記二つの実施形態が、結局、「通信路または記憶デバイス」へ入力する前の部分だけの符号化法である』ことを意味しているが、これによって、本発明の利用形態を限定的に把握してはならない。つまり、前式（４７）によれば、直接的には、[[ｎ，ｋ]]符号化したデータｆ（ｘ´）を、そのまま通信路または記憶デバイスに入力する最も単純な利用形態のみをイメージさせるかも知れないが、それは、本発明の利用形態の一例を示しているに過ぎないものである。

たとえば、暗号強度をさらに高める狙いから、本方式を別の暗号化方式と併用することも充分に考えられる利用形態の一つである。この併用形態について説明すると、今、併用する暗号化方式を表す関数をｇとする。そして、上記のｆ（ｘ´）をさらにｇ（ｆ（ｘ´））に暗号化した後に、ｇ（ｆ（ｘ´））を通信路または記憶デバイスに入力するようにすれば、ｆ（ｘ´）の暗号強度がさらにｇで補強されるので、より実用上好ましい強力な暗号化方式とすることができる。ただし、現在普及している暗号方式では一般的にｇは暗号鍵Ｋに依存し、記法としてはｇ＝ｇ_Kの形にすることが多いが、以上の説明では簡単化のために、併用する暗号化方式を表す関数を単にｇとした。したがって、このｇはｇ＝ｇ_Kの形も包含する。

１：[[ｎ，ｋ]]符号化器（誤り訂正符号化装置）
２：ｕ発生部（発生手段、発生工程）
３：ｘ´生成部（生成手段、生成工程）
４：［ｎ，ｍ］符号化部（出力手段、出力工程）
Ｓ１：ステップ（第１符号化手段、第１符号化工程）
Ｓ２：ステップ（第２符号化手段、第２符号化工程）
Ｓ３：ステップ（出力手段、出力工程）

Claims (6)

1. ｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ _k+1 ，・・・・，ｘ _m ）をランダムに発生する発生手段と、
   送りたいデータｘ＝（ｘ ₁ ，・・・・，ｘ _k ）に前記発生手段でランダムに発生したｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ _k+1 ，・・・・，ｘ _m ）を連接して、ｘ′＝[ｘｕ]＝（ｘ ₁ ，・・・・，ｘ _m ）を生成する生成手段と、
   前記生成手段で生成されたｘ′を[ｎ，ｍ]符号化して長さｎのベクトルを出力する出力手段とを備える[[ｎ，ｋ]]符号化を行う誤り訂正符号化装置に関するものであり、
   所定の符号長Ｎ″を使い、Ｋ′ディジットからなるベクトルである長さＫ′の送りたいデータを送信する[[Ｎ″，Ｋ′]]符号化と同等の伝送効率を持つ処理を分割統治法によって複数の段階に分割して行う手段であって、
   長さＫ′の送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ′×Ｎ′生成行列Ｆによって指定され、前記[[ｎ，ｋ]]符号化において変数ｎ、ｋにそれぞれＮ′、Ｋ′を代入して得られる[[Ｎ′，Ｋ′]]符号化により、長さＮ′のベクトル
   

   

   に符号化する第１符号化手段と、
   ｉ＝１，・・・・，Ｎに対して、前記第１符号化手段で得られた
   

   

   をｍ _i ×ｎ _i 生成行列Ｇ_iによって指定され、前記[[ｎ，ｋ]]符号化において変数ｎ、ｋにそれぞれｎ _i ，ｋ _i を代入して得られる[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル
   

   

   に符号化する第２符号化手段と、
   前記第２符号化手段で得られたｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる[ｗ⁽¹⁾・・・・ｗ^(N)]を符号化結果として出力する出力手段とを備え、
   ここで、変数Ｎ、ｎ_i、ｍ_i及びｋ_iは、Ｎ＞０，ｎ_i≧ｍ_i≧ｋ_i≧０（ｉ＝１，・・・・，Ｎ）を満足する整数であり、Ｎ′とＮ″は、次式（３６）で表される
   

   

   ことを特徴とする誤り訂正符号化装置。
2. ｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ _k+1 ，・・・・，ｘ _m ）をランダムに発生する発生工程と、
   送りたいデータｘ＝（ｘ ₁ ，・・・・，ｘ _k ）に前記発生工程でランダムに発生したｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ _k+1 ，・・・・，ｘ _m ）を連接して、ｘ′＝[ｘｕ]＝（ｘ ₁ ，・・・・，ｘ _m ）を生成する生成工程と、
   前記生成工程で生成されたｘ′を[ｎ，ｍ]符号化して長さｎのベクトルを出力する出力工程とを備える[[ｎ，ｋ]]符号化を行う誤り訂正符号化方法に関するものであり、
   所定の符号長Ｎ″を使い、Ｋ′ディジットからなるベクトルである長さＫ′の送りたいデータを送信する[[Ｎ″，Ｋ′]]符号化と同等の伝送効率を持つ処理を分割統治法によって複数の段階に分割して行う工程であって、
   長さＫ′の送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ′×Ｎ′生成行列Ｆによって指定され、前記[[ｎ，ｋ]]符号化において変数ｎ、ｋにそれぞれＮ′、Ｋ′を代入して得られる[[Ｎ′，Ｋ′]]符号化により、長さＮ′のベクトル
   

   

   に符号化する第１符号化工程と、
   ｉ＝１，・・・・，Ｎに対して、前記第１符号化工程で得られた
   

   

   をｍ _i ×ｎ _i 生成行列Ｇ_iによって指定され、前記[[ｎ，ｋ]]符号化において変数ｎ、ｋにそれぞれｎ _i ，ｋ _i を代入して得られる[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル
   

   

   に符号化する第２符号化工程と、
   前記第２符号化工程で得られたｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる[ｗ⁽¹⁾・・・・ｗ^(N)]を符号化結果として出力する出力工程とを備え、
   ここで、変数Ｎ、ｎ_i、ｍ_i及びｋ_iは、Ｎ＞０，ｎ_i≧ｍ_i≧ｋ_i≧０（ｉ＝１，・・・・，Ｎ）を満足する整数であり、Ｎ′とＮ″は、次式（３６）で表される
   

   

   ことを特徴とする誤り訂正符号化方法。
3. ｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ _k+1 ，・・・・，ｘ _m ）をランダムに発生する発生手段と、
   送りたいデータｘ＝（ｘ ₁ ，・・・・，ｘ _k ）に前記発生手段でランダムに発生したｍ−ｋ個のディジットからなるベクトルｕ＝（ｘ _k+1 ，・・・・，ｘ _m ）を連接して、ｘ′＝[ｘｕ]＝（ｘ ₁ ，・・・・，ｘ _m ）を生成する生成手段と、
   前記生成手段で生成されたｘ′を[ｎ，ｍ]符号化して長さｎのベクトルを出力する出力手段とを実現させる[[ｎ，ｋ]]符号化のための誤り訂正符号化プログラムに関するものであり、
   所定の符号長Ｎ″を使い、Ｋ′ディジットからなるベクトルである長さＫ′の送りたいデータを送信する[[Ｎ″，Ｋ′]]符号化と同等の伝送効率を持つ処理を分割統治法によって複数の段階に分割して行う手段であって、
   コンピュータに、
   長さＫ′の送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ′×Ｎ′生成行列Ｆによって指定され、前記[[ｎ，ｋ]]符号化において変数ｎ、ｋにそれぞれＮ′、Ｋ′を代入して得られる[[Ｎ′，Ｋ′]]符号化により、長さＮ´のベクトル
   

   

   に符号化する第１符号化手段と、
   ｉ＝１，・・・・，Ｎに対して、前記第１符号化手段で得られた
   

   

   をｍ _i ×ｎ _i 生成行列Ｇ_iによって指定され、前記[[ｎ，ｋ]]符号化において変数ｎ、ｋにそれぞれｎ _i ，ｋ _i を代入して得られる[[ｎ_i，ｋ_i]]符号化により、長さｎ_iのベクトル
   

   

   に符号化する第２符号化手段と、
   前記第２符号化手段で得られたｗ⁽¹⁾，・・・・，ｗ^(N)を連接して得られる[ｗ⁽¹⁾・・・・ｗ^(N)]を符号化結果として出力する出力手段とを実現させ、
   ここで、変数Ｎ、ｎ_i、ｍ_i及びｋ_iは、Ｎ＞０，ｎ_i≧ｍ_i≧ｋ_i≧０（ｉ＝１，・・・・，Ｎ）を満足する整数であり、Ｎ′とＮ″は、次式（３６）で表される
   

   

   ことを特徴とする誤り訂正符号化プログラム。
4. 前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段を備えることを特徴とする請求項１記載の誤り訂正符号化装置。
5. 前記出力工程から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力工程を備えることを特徴とする請求項２記載の誤り訂正符号化方法。
6. 前記コンピュータに、前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段を実現させることを特徴とする請求項３記載の誤り訂正符号化プログラム。
   
   

Images