誤り訂正符号化装置、誤り訂正符号化方法及びプログラム
【課題】セキュリティ対策を講じた誤り訂正符号化装置、誤り訂正符号化方法及びプログラムを提供する。
【解決手段】送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル（数１）に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、（数２）を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトルに符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段とを備える。
【解決手段】送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル（数１）に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、（数２）を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトルに符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り訂正符号化装置、誤り訂正符号化方法及びプログラムに関し、詳しくは、データ表現の冗長性に基づく誤り訂正符号化装置、誤り訂正符号化方法及びプログラムに関する。
【背景技術】
【０００２】
今日、あらゆるデジタル通信の分野において、通信路で発生した誤りを訂正するための誤り訂正符号の技術が用いられている。ここで、「通信」とは、一般的に有線や無線などの通信媒体を介して行われる離隔点間の情報伝送のことをいうが、本明細書では、このような狭い意味に限定しない。たとえば、コンパクトディスクなどの記録媒体に情報を記録することも「通信」の概念に含める。情報を送るとは、離れた場所に情報を運ぶことであり、記録するとは、後日の読み出しを想定して離れた（後日の）時間へ情報を運ぶことであるからであり、両者とも情報を運ぶ点で同じ意味だからである。
【０００３】
符号理論で取り扱うのは、デジタル化された情報である。送りたいデータは、オーディオ信号やビデオ信号などをデジタル化したもの、あるいは計算機からのデジタルデータなどであろう。これらの情報の発生源や、それをデジタル化する部分などを含めて情報源という。デジタル化された情報（送りたいデータ）は、たとえば、ＰＣＭ信号を考えれば分かるように、０，１の２種類の記号（数字）を使って、ビット列として表されていることが多い。このため、本明細書においても、送りたいデータはビット列、あるいは、より一般的にディジット列で表されているものとする。
【０００４】
図３は、通信系のモデルを示す図である。この図において、情報源からは、送りたいデータとして０，１のビット列（情報ビット列）が発生する。符号器（誤り訂正符号化装置）は、この情報ビット列を、ｍビットごとのブロックに区切って取り扱う。各ブロックを“送りたいデータ”と呼び、この送りたいデータをｉ＝（ｉ1，・・・・，ｉm）で表す。
【０００５】
符号器は、送りたいデータｉに対応したｎビット（ｎ＞ｍ）の符号語ｗ＝（ｘ1，・・・・，ｘn）を出力する。すなわち、この符号器で、ｎ−ｍビットの余分なビット（冗長ビット）を付加する。ｎを符号長、ｍを情報ビット数といい、この操作のことを「符号化」という。通信路に送り出された符号語を送信語ｗといい、通信路は、この送信語ｗが入力されるとｎビットの受信語ｖを出力する。伝送・記録媒体の雑音などの影響がなければ、送信語＝受信語であるが、通常は雑音などのために、送信語の各ビットの０，１がある確率で異なって受信される。これを誤りといい、この様子を、通信路において各ビットに誤りｅが加わったとして、ｖ＝ｗ＋ｅで表す。ただし、ｊ番目のビットの誤りをｅjとし、ｅはビット列ｅ＝（ｅ1，・・・・，ｅn）を表し、誤りパターンとも呼ばれる。復号器は、受信語ｖを元に、いずれの符号語が送信されたかを推定し、送信語ｗの推定値または送りたいデータｉの推定値を出力する。
【０００６】
なお、実際の伝送路または記録媒体には、送信語ｗの各ビットｘjに対応して、たとえば“０”の場合はパルスなし、“１”の場合はパルスあり、といった信号波形として送り出されるが、説明の便宜上、本明細書では具体的な波形に言及しない。
【０００７】
さて、このような符号長ｎ、情報ビット数ｍの符号化のことを［ｎ，ｍ］符号化といい、２m通りある符号語の集合のことを［ｎ，ｍ］符号という（たとえば、特許文献１、特許文献２）。
【０００８】
より一般的に、ガロア体ＧＦ（ｑ）上の［ｎ，ｍ］線形誤り訂正符号とは、ＧＦ（ｑ）nのｍ次元線形部分空間のことである。ＧＦ（ｑ）は元の数がｑであるような有限体である。ＧＦ（ｑ）nは、ＧＦ（ｑ）の元をｎ個並べてできるべクトル（数ベクトル）の集合であるが、慣習に従い、ＧＦ（ｑ）上の数ベクトルを横ベクトルで表すことにする。
【０００９】
線形符号を用いた従来の符号化では、次のようにデータを符号化する。まず、［ｎ，ｍ］線形誤り訂正符号（以下、線形符号Ｃという。）の基底を（ｇ1，・・・・，ｇm）とする。符号化すべき長さｍのストリングを、ＧＦ（ｑ）上の数ベクトルとして、次式（１３）で表す。なお、線形符号Ｃの具体例としては、標準的な符号理論の教科書（たとえば、“Ｔｈｅ Ｔｈｅｏｒｙ ｏｆ Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅｓ”，Ｆ．Ｊ．ＭａｃＷｉｌｌｉａｍｓ ａｎｄ Ｎ．Ｊ．Ａ．Ｓｌｏａｎｅ，ＮＯＲＴＨ−ＨＯＬＬＡＮＤ，ＩＳＢＮ：０−４４４−８５１９３−３／０−４４４−８５００９−０／０−４４４−８５０１０−４）に記載されているように、ハミング符号、ＢＣＨ符号、ゴッパ符号など様々なものがある。
【００１０】
【数１３】
【００１１】
以下では、このようなデータを（長さｍの）ベクトル、あるいはＧＦ（ｑ）上の長さｍのベクトルと呼ぶことにする。これを、次式（１４）により、線形符号Ｃに属するベクトルｆ（ｘ）に符号化する。もちろん、演算はＧＦ（ｑ）上で行う。たとえば、ｑが素数のときは、ｑ個の数字“０，１，・・・・，ｑ−１”とｍｏｄｑ計算法のもとで行う。
【００１２】
【数１４】
【００１３】
ｇi＝（ｇi1，・・・・，ｇin）（ｉ＝１，・・・・，ｍ）のとき、次式（１５）は、線形符号Ｃの生成行列と呼ばれる。
【００１４】
【数１５】
【００１５】
このような公知の符号化は、既述のとおり、［ｎ，ｍ］符号化であり、特に具体的に符号化を指定するためには、上記の符号化を生成行列Ｇにより指定される［ｎ，ｍ］符号化と呼ぶ。この［ｎ，ｍ］符号化では、ｎ個のディジット（ＧＦ（ｑ）の元）を使って、ｍディジット分の情報を送っている。線形符号Ｃ（つまり生成行列Ｇにより指定される［ｎ，ｍ］符号化）は、ｑ＝２のときが最もよく用いられる。このときＧＦ（ｑ）＝｛０，１｝となる。なお、ｑ＝２のとき「ディジット」は「ビット」と呼ばれる。なお、線形符号Ｃとその生成行列Ｇの具体例も、上記の標準的な符号理論の教科書に諸々記載されている。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２００５−１１０２５１号公報
【特許文献２】特許第３２８１９３８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、上述した公知の［ｎ，ｍ］符号は、誤り訂正の能力は充分であるものの、伝送途中の盗聴対策が不完全であり、セキュリティに欠けるという問題点がある。すなわち、通信路に入力された送信語ｗや通信路から出力された受信語ｖを第三者に盗聴されてしまった場合、元の送りたいデータｉを容易に推定されてしまうという問題点がある。
【００１８】
そこで、本発明の目的は、セキュリティ対策を講じた誤り訂正符号化装置、誤り訂正符号化方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１９】
請求項１記載の発明は、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００２０】
【数１６】
【００２１】
に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、
【００２２】
【数１７】
【００２３】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００２４】
【数１８】
【００２５】
に符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段とを備えたことを特徴とする誤り訂正符号化装置である。
請求項２記載の発明は、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００２６】
【数１９】
【００２７】
に符号化する第１符号化工程と、ｉ＝１，・・・・，Ｎに対して、
【００２８】
【数２０】
【００２９】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００３０】
【数２１】
【００３１】
に符号化する第２符号化工程と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力工程とを含むことを特徴とする誤り訂正符号化方法である。
請求項３記載の発明は、コンピュータに、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００３２】
【数２２】
【００３３】
に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、
【００３４】
【数２３】
【００３５】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００３６】
【数２４】
【００３７】
に符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段とを実現させるためのプログラムである。
請求項４記載の発明は、前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段を備えたことを特徴とする請求項１記載の誤り訂正符号化装置である。
請求項５記載の発明は、前記出力工程から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力工程を含むことを特徴とする請求項２記載の誤り訂正符号化方法である。
請求項６記載の発明は、コンピュータに、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００３８】
【数２５】
【００３９】
に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、
【００４０】
【数２６】
【００４１】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００４２】
【数２７】
【００４３】
に符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と、前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段とを実現させるためのプログラムである。
【発明の効果】
【００４４】
説明の便宜上、[[ｎ，ｋ]]符号を[[４，１]]符号とし、送りたいデータを｛０，１｝とすると共に、たとえば、送りたいデータの“０”を｛００００，１１１１｝、送りたいデータの“１”を｛００１１，１１００｝と符号化するものとする。本発明では、データを送る際に、その｛ ｝内のいずれか一つのパターンがランダムに選択されて送信される。たとえば、データ“０”のパターンは、“００００”と“１１１１”であるので、その一方をランダムに送信するなどである。このようにすれば、仮に伝送途中の第三者がそのパターンの一部を盗聴し得たとしても、元のデータを推定することはできない。これは、たとえば、“００”を盗聴できたとしても、この“００”は、データ“１”のパターンにも含まれているからである。
したがって、本発明によれば、セキュリティ対策を講じた誤り訂正符号化装置、誤り訂正符号化方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００４５】
【図１】第１の実施形態（[[ｎ，ｋ]]符号化）の概念ブロック図である。
【図２】第２の実施形態（二段階符号化）の概念的な処理フローを示す図である。
【図３】通信系のモデルを示す図である。
【発明を実施するための形態】
【００４６】
以下、本発明の実施形態を説明する。
まず、言葉の定義として、長さａのベクトルｘ＝（ｘ1，・・・・，ｘa）と長さｂのベクトルｙ＝（ｙ1，・・・・，ｙb）を繋げてできる長さａ＋ｂのベクトル（ｘ1，・・・・，ｘa，ｙ1，・・・・，ｙb）を［ｘｙ］で表すことにする。このとき、ｘにｙを連接して［ｘｙ］を得るという。３つ以上のベクトルについても“［”と“］”で括ったもので、同様に連接してできるベクトルを表す。たとえば、［ｘｙｚ］は、ｘにｙを連接し、それにさらにｚを連接してできるベクトルを表す。
【００４７】
＜第１の実施形態（[[ｎ，ｋ]]符号化）＞
図１は、第１の実施形態（[[ｎ，ｋ]]符号化）の概念ブロック図である。このブロックは、冒頭で説明した通信系のモデル図（図３）における符号器として用いることができるものを模式的に表している。このブロックの具体的な構成については特に言及しない。たとえば、ハードロジックで構成されていてもよいし、あるいは、その全てまたはその主要な機能の一部がコンピュータで実行可能なソフトウェアで構成されていてもよい。いずれにせよ、以下に説明する機能を実現できる構成になっていればよい。
【００４８】
図示のブロック全体の名称は、たとえば、冒頭の通信モデルのように、符号器と呼称しても構わないが、ここでは、従来技術の［ｎ，ｍ］符号化と区別するために、二重の括弧を用いて[[ｎ，ｋ]]符号化部１と称することにし、さらに、この[[ｎ，ｋ]]符号化部１による符号化のことを、[[ｎ，ｋ]]符号化と称することにする。
【００４９】
[[ｎ，ｋ]]符号化部１は、少なくとも、ｕ発生部２、ｘ´生成部３及び［ｎ，ｍ］符号化部４を含む。ｕ発生部２は、たとえば、物理的な乱数発生器または疑似乱数発生器であり、［ｎ，ｍ］符号化部４は、従来技術の［ｎ，ｍ］符号化に相当する操作を行うものである。
【００５０】
この第１の実施形態では、情報のセキュリティを確保するため、以下の新しい符号化を行う。この方式は、簡単にいえば、冒頭で説明した公知の［ｎ，ｍ］符号化を用いてｋディジット分の情報を送るというものである。ただし、ｋ≦ｍである。
【００５１】
今、送りたいデータｘが、次式（２８）のようなものであるとする。
【００５２】
【数２８】
【００５３】
ｘ´生成部３は、このデータｘに、ｕ発生部２でランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘk+1，・・・・，ｘm）を連接して、次式（２９）のｘ´を得る。
【００５４】
【数２９】
【００５５】
［ｎ，ｍ］符号化部４は、前記の生成行列Ｇによって指定される［ｎ，ｍ］符号化を用いて、ｘ´生成部３で演算されたｘ´を、長さｎのベクトルｆ（ｘ´）に符号化する。
【００５６】
このように、この第１の実施形態では、送りたいデータｘにランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘk+1，・・・・，ｘm）を連接してｘ´を生成し、そのｘ´を、［ｎ，ｍ］符号化を用いて長さｎのベクトルｆ（ｘ´）に符号化し、それを出力する。
【００５７】
この第１の実施形態における符号化は、前記のとおり、 [[ｎ，ｋ]]符号化であり、生成行列Ｇを変えることで異なる符号化が得られるため、特に符号化を具体的に指定するためには、これを、生成行列Ｇによって指定される[[ｎ，ｋ]]符号化と呼ぶ。この[[ｎ，ｋ]]符号化のイメージは、次式（３０）のように示すことができる。
【００５８】
【数３０】
【００５９】
式（３０）の全体は、図１の[[ｎ，ｋ]]符号化部１に相当する。さらに、ｘ→ｘ´の部分はｘ´生成部３に相当し、ｘ´→ｆ（ｘ´）の部分は［ｎ，ｍ］符号化部４に相当する。
【００６０】
ここで、前記の“発明の効果”の欄で挙げた例が、この第１の実施形態の[[ｎ，ｋ]]符号化で実現できることを説明する。線形符号Ｃの基底を（ｇ1，・・・・，ｇm）とし、このうち（ｇk+1，・・・・，ｇm）の張る部分空間をＢとするとともに、ｎ＝４、ｋ＝１、ｍ＝２とすれば、線形符号Ｃの一例は、次式（３１）のように書き表すことができ、また、Ｂの一例は、次式（３２）のように書き表すことができる。なお、これらは、ＧＦ（ｑ）＝ＧＦ（２）の場合の例である。
【００６１】
【数３１】
【００６２】
【数３２】
【００６３】
この場合、ｇ1、ｇ2は、次式（３３）及び次式（３４）のように書き表すことができる。すると、次式（３５）のように、ｕ発生部２でｘ2＝０，１がランダムに発生されるから、送りたいデータがｘ1＝０であるか、ｘ1＝１であるかに応じて、[[ｎ，ｋ]]符号化器１の出力は、｛００００，１１１１｝か｛１１００，００１１｝になる。ただし、ここでは、ベクトル（１，１，１，１）を“１１１１”と書くなどした。
【００６４】
【数３３】
【００６５】
【数３４】
【００６６】
【数３５】
【００６７】
このように、この第１の実施形態によれば、送りたいデータｘにランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘk+1，・・・・，ｘm）を連接してｘ´を生成し、そのｘ´を、［ｎ，ｍ］符号化を用いて長さｎのベクトルｆ（ｘ´）に符号化することにより、ｋディジット分の情報を生成出力することができるので、以下の理由から、情報のセキュリティを確保することができる。
【００６８】
今、簡単化のために、[[ｎ，ｋ]]符号を[[４，１]]符号とし、送りたいデータを｛０，１｝とする。この場合、第１の実施形態では、たとえば、送りたいデータの“０”を｛００００，１１１１｝、送りたいデータの“１”を｛００１１，１１００｝と符号化し、データを送る際に、その｛ ｝内のいずれか一つのパターンをランダムに選択して送信する。たとえば、データ“０”のパターンは、“００００”と“１１１１”であるので、その一方をランダムに送信する。仮に伝送途中の第三者がそのパターンの一部を盗聴し得たとしても、元のデータを推定することはできない。これは、たとえば、“００”を盗聴できたとしても、この“００”は、データ“１”のパターンにも含まれているからである。
【００６９】
したがって、この第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）においては、伝送途中の第三者による盗聴を効果的に防止し、セキュリティ対策を講じることができるので、本発明の冒頭の課題を達成することができる。
【００７０】
＜第２の実施形態（二段階符号化）＞
以上説明した第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）においては、セキュリティ対策を講じることができる点で有益である。一方で、理論的な解析により比較的符号長が長い方が復号誤り確率と安全性の点で有利であることは分かっているものの、符号長が長くなるにつれ、符号化や復号化の手続きの煩雑さが増していくことを否めず、この手続きの煩雑さが、実用化する上での障害となる可能性がある。上記のとおり、[[ｎ，ｋ]]符号化は、通信路上での盗聴を回避できるという従来技術にない格別有益なメリットを持つため、かかる障害要因（手続きの煩雑さ）の克服は、是非とも達成されなければならない技術課題である。以下に説明する第２の実施形態は、そのためのものである。簡潔に述べれば、この第２の実施形態は、分割統治の考え方（与えられた問題をいくつかの小さな問題に分割して解き、それをもとに統治をおこない、問題の解を得る手法のこと。分割統治法：Ｄｉｖｉｄｅ ａｎｄ Ｃｏｎｑｕｅｒともいう。）を採用して、大きな符号長を持つ[[ｎ，ｋ]]符号化の処理をいくつかの処理に分けて段階的に行うことにより、前記の障害要因を克服し、以て、産業上の利用に充分に耐え得る誤り訂正符号化の技術を提供するものである。
【００７１】
第２の実施形態について説明する。この第２の実施形態では、以下に詳述するように、一例として、２つの線形符号を使って符号化する方法を開示する。以下、この符号化のことを「二段階符号化」という。
【００７２】
この二段階符号化では、Ｎ＞０，ｎi≧ｍi≧ｋi≧０（ｉ＝１，・・・・，Ｎ）を整数（実用的なのは、ｎi，ｍi，ｋiがｉに依らない場合である。）とするとき、ｍi×ｎi生成行列Ｇiにより指定される[[ｎi，ｋi]]符号化と、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆにより指定される[[Ｎ´，Ｋ´]]符号化とを組み合わせて符号化する。これを、[[Ｎ″，Ｋ″]]符号化という。ただし、Ｎ´とＭ´は、次式（３６）で与えられる。
【００７３】
【数３６】
【００７４】
具体的な[[Ｎ´，Ｋ´]]符号化の方法は、以下のようになる。ここで、送信データの長さはＫ´である。
【００７５】
図２は、第２の実施形態（二段階符号化）の概念的な処理フローを示す図である。この処理フローは、冒頭で説明した通信系のモデル図（図３）における符号器として用いることができるものを模式的に表している。前記の第１の実施形態と同様に、この処理フローは、ハードロジックで構成されていてもよいし、あるいは、その全てまたはその主要な機能の一部がコンピュータで実行可能なソフトウェアで構成されていてもよい。いずれにせよ、以下に説明する機能を実現できる構成になっていればよい。
【００７６】
この処理フローにおいて、まず、ステップＳ１の[[Ｎ´，Ｋ´]]符号化で、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、任意の送りたいデータを、長さＮ´のベクトルに符号化する。このベクトルは、Ｎ個のブロックに分割して、次式（３７）のように書くことができる。
【００７７】
【数３７】
【００７８】
次いで、ステップＳ２の[[ｎi，ｋi]]符号化で、ｉ＝１，・・・・，Ｎに対して、
【００７９】
【数３８】
【００８０】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００８１】
【数３９】
【００８２】
に符号化する。
【００８３】
そして、最後のステップＳ３で、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する。
【００８４】
ここで、ステップＳ１で用いる符号について、特に有用なのは、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆで指定される[[Ｎ´，Ｋ´]]符号化が、ＧＦ（ｑ）の拡大体ＧＦ（ｑk）上の符号に由来する場合である。この場合、たとえば、ＧＦ（ｑk）上のリード・ソロモン符号を使用することができる。実用上、ＧＦ（ｑk）上の［Ｎ，Ｋ］リード・ソロモン符号は、ＧＦ（ｑ）上の［ｋＮ，ｋＫ］符号として用いられている。たとえば、コンパクトディスクに用いられているリード・ソロモン符号などである（ｑ＝２）。
【００８５】
すなわち、ステップＳ１の[[Ｎ´，Ｋ´]]符号化では、従来の［ｎ，ｍ］符号化に相当する［Ｎ´，Ｍ´］符号化を用いることができるが、この部分では、ＧＦ（ｑk）上の［Ｎ，Ｍ］符号をＧＦ（ｑ）上の［ｋＮ，ｋＭ］符号として用いることができる。ただし、Ｎ´＝ｋＮ，Ｍ´＝ｋＭとおく。
【００８６】
なお、これは、ＧＦ（ｑk）の元を、ＧＦ（ｑ）上の長さｋのベクトルとして表現して得られるものである。具体的には、以下のとおりである。今、ＧＦ（ｑ）上の線形空間であるＧＦ（ｑk）の基底をｂ＝（βj）kj=1とする。これを用いて、いかなる要素ζ∈ＧＦ（ｑk）も、次式（４０）のように書くことが可能であるので、このように得られた数の行ベクトル（ｘ1，・・・・，ｘk）を、φ（ζ）の記号で示すことにする。
【００８７】
【数４０】
【００８８】
この変換「ζ→φ（ζ）＝（ｘ1，・・・・，ｘk）」を用いた対応「ξ＝（ξ1，・・・・，ξN）←→［φ（ξ1）・・・・φ（ξN）］」により、ＧＦ（ｑk）上の長さＮのベクトルξと、ＧＦ（ｑ）上の長さｋＮのベクトル［φ（ξ1）・・・・φ（ξN）］とを同一視することができるようになる。
【００８９】
二段階符号化の具体例を説明する。ｎi，ｍi，ｋiがｉに依らない場合、すなわち、ｎ≧ｍ≧ｋ≧０を整数として、ｎi＝ｎ，ｍi＝ｍ，ｋi＝ｋ（ｉ＝１，・・・・，Ｎ）の場合の具体例を挙げる。上記のステップＳ１では、前述したような［ｋＮ，ｋＭ］符号化を用いる。たとえば、ｑ＝２で、ｋ＝４ならば、リード・ソロモン符号による［４・１５，４Ｍ］符号化を用いることができる。ただし、０＜Ｍ≦１５である。この場合、上記のステップＳ１では、次式（４１）が得られる。
【００９０】
【数４１】
【００９１】
ステップＳ２では、同一の生成行列Ｇによって指定される[[ｎ，ｋ]]符号化を、ｙ1(i)，・・・・，ｙk(i)に適用してもよい（ｉ＝１，・・・・，Ｎ）。たとえば、ｎ＝６のとき、次式（４２）〜（４６）として、第ｉ行がgiであるような生成行列Ｇによって指定される[[６，４]]符号化を行う。このように、生成行列Ｇによって指定される[[６，４]]符号化の出力は、ハミング重みが偶数であるようなベクトルとなる。
【００９２】
【数４２】
【００９３】
【数４３】
【００９４】
【数４４】
【００９５】
【数４５】
【００９６】
【数４６】
【００９７】
なお、上記において、拡大体ＧＦ（ｑk）上の符号について取り扱ったのは、このような符号を用いると効率の良い復号を行うことができるからである。しかし、これは、性能的に最良（ベストモード）の実施態様を例示しているに過ぎない。したがって、本発明は、この拡大体ＧＦ（ｑk）上の符号を使用するケースに限定されない。
【００９８】
以上のとおり、この第２の実施形態においては、分割統治の考え方を採用して、大きな符号長を持つ[[ｎ，ｋ]]符号化の処理をいくつかの処理に分けて段階的に行うようにしたので、符号化や復号化の手続きを効率的に行うことができ、手続きの簡素化を図ることができる。したがって、先に説明した第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）の利点（セキュリティ対策を講じることができる。）を活かしつつ、[[ｎ，ｋ]]符号化の長い符号長に伴う欠点（符号化や復号化の手続きの煩雑さ）を解決し、実用に耐え得る誤り訂正符号化の技術を提供することができる。
【００９９】
なお、この第２の実施形態は、二段階符号化に関するものであるが、二段階に限らず、三段階以上のものも包含する。これは、三段階以上の場合、二段階符号化を手続きの一部に含むからである。したがって、発明にとって必須な事項は、二段階符号化に関する部分（図２のステップＳ１、ステップＳ２）にあるということができる。
【０１００】
前記第１の実施形態は[[ｎ，ｋ]]符号化に関するものであり、また、前記第２の実施形態は二段階符号化に関するものである。これら二つの実施形態は、前式（３０）で示したとおり、たとえば、従来の［ｎ，ｍ］符号化をブラックボックス化することによって極めて単純に構築することができる。これを補足すると、次式（４７）のようになる。
【０１０１】
【数４７】
【０１０２】
この式（４７）より、前記二つの実施形態は、結局、「通信路または記憶デバイス」へ入力する前の部分だけの符号化法であるということができる。
【０１０３】
ちなみに、本発明の本質ではないものの、「復号器」についても言及すれば、前記二つの実施形態に対応する復号器の中身は、概ね次式（４８）のように書き表すことができる。
【０１０４】
【数４８】
【０１０５】
ここで、ｘ，ｕの推定値はそれぞれ、次式（４９）で与えられる。
【０１０６】
【数４９】
【０１０７】
以上のことから、二段階符号化もトータルとして見れば、次式（５０）のように書き表すことができるので、上式（４９）の復号原理を適用することができる。
【０１０８】
【数５０】
【０１０９】
ただし、効率の点では、二段階符号化に対応した二段階の復号化を適用することが望ましい。これは、公知の二段階符号化＝連接符号の復号に類似する。
【０１１０】
なお、前記第１の実施形態において、［ｎ，ｍ］符号化部４の［ｎ，ｍ］符号化は、“生成行列Ｇによって指定される”としてあるが、これは具体例として挙げたある特定の符号の生成行列Ｇに限定されない。［ｎ，ｍ］線形符号の生成行列であれば、ある特定の生成行列Ｇに限らず、全て使用することができる。このことは、第２の実施形態における二段階符号化でも同様である。
【０１１１】
また、先に述べたとおり、前式（４７）は、『前記二つの実施形態が、結局、「通信路または記憶デバイス」へ入力する前の部分だけの符号化法である』ことを意味しているが、これによって、本発明の利用形態を限定的に把握してはならない。つまり、前式（４７）によれば、直接的には、[[ｎ，ｋ]]符号化したデータｆ（ｘ´）を、そのまま通信路または記憶デバイスに入力する最も単純な利用形態のみをイメージさせるかも知れないが、それは、本発明の利用形態の一例を示しているに過ぎないものである。
【０１１２】
たとえば、暗号強度をさらに高める狙いから、本方式を別の暗号化方式と併用することも充分に考えられる利用形態の一つである。この併用形態について説明すると、今、併用する暗号化方式を表す関数をｇとする。そして、上記のｆ（ｘ´）をさらにｇ（ｆ（ｘ´））に暗号化した後に、ｇ（ｆ（ｘ´））を通信路または記憶デバイスに入力するようにすれば、ｆ（ｘ´）の暗号強度がさらにｇで補強されるので、より実用上好ましい強力な暗号化方式とすることができる。ただし、現在普及している暗号方式では一般的にｇは暗号鍵Ｋに依存し、記法としてはｇ＝ｇKの形にすることが多いが、以上の説明では簡単化のために、併用する暗号化方式を表す関数を単にｇとした。したがって、このｇはｇ＝ｇKの形も包含する。
【符号の説明】
【０１１３】
１：[[ｎ，ｋ]]符号化器（誤り訂正符号化装置）
２：ｕ発生部（発生手段、発生工程）
３：ｘ´生成部（生成手段、生成工程）
４：［ｎ，ｍ］符号化部（出力手段、出力工程）
Ｓ１：ステップ（第１符号化手段、第１符号化工程）
Ｓ２：ステップ（第２符号化手段、第２符号化工程）
Ｓ３：ステップ（出力手段、出力工程）
【技術分野】
【０００１】
本発明は、誤り訂正符号化装置、誤り訂正符号化方法及びプログラムに関し、詳しくは、データ表現の冗長性に基づく誤り訂正符号化装置、誤り訂正符号化方法及びプログラムに関する。
【背景技術】
【０００２】
今日、あらゆるデジタル通信の分野において、通信路で発生した誤りを訂正するための誤り訂正符号の技術が用いられている。ここで、「通信」とは、一般的に有線や無線などの通信媒体を介して行われる離隔点間の情報伝送のことをいうが、本明細書では、このような狭い意味に限定しない。たとえば、コンパクトディスクなどの記録媒体に情報を記録することも「通信」の概念に含める。情報を送るとは、離れた場所に情報を運ぶことであり、記録するとは、後日の読み出しを想定して離れた（後日の）時間へ情報を運ぶことであるからであり、両者とも情報を運ぶ点で同じ意味だからである。
【０００３】
符号理論で取り扱うのは、デジタル化された情報である。送りたいデータは、オーディオ信号やビデオ信号などをデジタル化したもの、あるいは計算機からのデジタルデータなどであろう。これらの情報の発生源や、それをデジタル化する部分などを含めて情報源という。デジタル化された情報（送りたいデータ）は、たとえば、ＰＣＭ信号を考えれば分かるように、０，１の２種類の記号（数字）を使って、ビット列として表されていることが多い。このため、本明細書においても、送りたいデータはビット列、あるいは、より一般的にディジット列で表されているものとする。
【０００４】
図３は、通信系のモデルを示す図である。この図において、情報源からは、送りたいデータとして０，１のビット列（情報ビット列）が発生する。符号器（誤り訂正符号化装置）は、この情報ビット列を、ｍビットごとのブロックに区切って取り扱う。各ブロックを“送りたいデータ”と呼び、この送りたいデータをｉ＝（ｉ1，・・・・，ｉm）で表す。
【０００５】
符号器は、送りたいデータｉに対応したｎビット（ｎ＞ｍ）の符号語ｗ＝（ｘ1，・・・・，ｘn）を出力する。すなわち、この符号器で、ｎ−ｍビットの余分なビット（冗長ビット）を付加する。ｎを符号長、ｍを情報ビット数といい、この操作のことを「符号化」という。通信路に送り出された符号語を送信語ｗといい、通信路は、この送信語ｗが入力されるとｎビットの受信語ｖを出力する。伝送・記録媒体の雑音などの影響がなければ、送信語＝受信語であるが、通常は雑音などのために、送信語の各ビットの０，１がある確率で異なって受信される。これを誤りといい、この様子を、通信路において各ビットに誤りｅが加わったとして、ｖ＝ｗ＋ｅで表す。ただし、ｊ番目のビットの誤りをｅjとし、ｅはビット列ｅ＝（ｅ1，・・・・，ｅn）を表し、誤りパターンとも呼ばれる。復号器は、受信語ｖを元に、いずれの符号語が送信されたかを推定し、送信語ｗの推定値または送りたいデータｉの推定値を出力する。
【０００６】
なお、実際の伝送路または記録媒体には、送信語ｗの各ビットｘjに対応して、たとえば“０”の場合はパルスなし、“１”の場合はパルスあり、といった信号波形として送り出されるが、説明の便宜上、本明細書では具体的な波形に言及しない。
【０００７】
さて、このような符号長ｎ、情報ビット数ｍの符号化のことを［ｎ，ｍ］符号化といい、２m通りある符号語の集合のことを［ｎ，ｍ］符号という（たとえば、特許文献１、特許文献２）。
【０００８】
より一般的に、ガロア体ＧＦ（ｑ）上の［ｎ，ｍ］線形誤り訂正符号とは、ＧＦ（ｑ）nのｍ次元線形部分空間のことである。ＧＦ（ｑ）は元の数がｑであるような有限体である。ＧＦ（ｑ）nは、ＧＦ（ｑ）の元をｎ個並べてできるべクトル（数ベクトル）の集合であるが、慣習に従い、ＧＦ（ｑ）上の数ベクトルを横ベクトルで表すことにする。
【０００９】
線形符号を用いた従来の符号化では、次のようにデータを符号化する。まず、［ｎ，ｍ］線形誤り訂正符号（以下、線形符号Ｃという。）の基底を（ｇ1，・・・・，ｇm）とする。符号化すべき長さｍのストリングを、ＧＦ（ｑ）上の数ベクトルとして、次式（１３）で表す。なお、線形符号Ｃの具体例としては、標準的な符号理論の教科書（たとえば、“Ｔｈｅ Ｔｈｅｏｒｙ ｏｆ Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅｓ”，Ｆ．Ｊ．ＭａｃＷｉｌｌｉａｍｓ ａｎｄ Ｎ．Ｊ．Ａ．Ｓｌｏａｎｅ，ＮＯＲＴＨ−ＨＯＬＬＡＮＤ，ＩＳＢＮ：０−４４４−８５１９３−３／０−４４４−８５００９−０／０−４４４−８５０１０−４）に記載されているように、ハミング符号、ＢＣＨ符号、ゴッパ符号など様々なものがある。
【００１０】
【数１３】
【００１１】
以下では、このようなデータを（長さｍの）ベクトル、あるいはＧＦ（ｑ）上の長さｍのベクトルと呼ぶことにする。これを、次式（１４）により、線形符号Ｃに属するベクトルｆ（ｘ）に符号化する。もちろん、演算はＧＦ（ｑ）上で行う。たとえば、ｑが素数のときは、ｑ個の数字“０，１，・・・・，ｑ−１”とｍｏｄｑ計算法のもとで行う。
【００１２】
【数１４】
【００１３】
ｇi＝（ｇi1，・・・・，ｇin）（ｉ＝１，・・・・，ｍ）のとき、次式（１５）は、線形符号Ｃの生成行列と呼ばれる。
【００１４】
【数１５】
【００１５】
このような公知の符号化は、既述のとおり、［ｎ，ｍ］符号化であり、特に具体的に符号化を指定するためには、上記の符号化を生成行列Ｇにより指定される［ｎ，ｍ］符号化と呼ぶ。この［ｎ，ｍ］符号化では、ｎ個のディジット（ＧＦ（ｑ）の元）を使って、ｍディジット分の情報を送っている。線形符号Ｃ（つまり生成行列Ｇにより指定される［ｎ，ｍ］符号化）は、ｑ＝２のときが最もよく用いられる。このときＧＦ（ｑ）＝｛０，１｝となる。なお、ｑ＝２のとき「ディジット」は「ビット」と呼ばれる。なお、線形符号Ｃとその生成行列Ｇの具体例も、上記の標準的な符号理論の教科書に諸々記載されている。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２００５−１１０２５１号公報
【特許文献２】特許第３２８１９３８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、上述した公知の［ｎ，ｍ］符号は、誤り訂正の能力は充分であるものの、伝送途中の盗聴対策が不完全であり、セキュリティに欠けるという問題点がある。すなわち、通信路に入力された送信語ｗや通信路から出力された受信語ｖを第三者に盗聴されてしまった場合、元の送りたいデータｉを容易に推定されてしまうという問題点がある。
【００１８】
そこで、本発明の目的は、セキュリティ対策を講じた誤り訂正符号化装置、誤り訂正符号化方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１９】
請求項１記載の発明は、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００２０】
【数１６】
【００２１】
に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、
【００２２】
【数１７】
【００２３】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００２４】
【数１８】
【００２５】
に符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段とを備えたことを特徴とする誤り訂正符号化装置である。
請求項２記載の発明は、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００２６】
【数１９】
【００２７】
に符号化する第１符号化工程と、ｉ＝１，・・・・，Ｎに対して、
【００２８】
【数２０】
【００２９】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００３０】
【数２１】
【００３１】
に符号化する第２符号化工程と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力工程とを含むことを特徴とする誤り訂正符号化方法である。
請求項３記載の発明は、コンピュータに、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００３２】
【数２２】
【００３３】
に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、
【００３４】
【数２３】
【００３５】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００３６】
【数２４】
【００３７】
に符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段とを実現させるためのプログラムである。
請求項４記載の発明は、前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段を備えたことを特徴とする請求項１記載の誤り訂正符号化装置である。
請求項５記載の発明は、前記出力工程から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力工程を含むことを特徴とする請求項２記載の誤り訂正符号化方法である。
請求項６記載の発明は、コンピュータに、送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【００３８】
【数２５】
【００３９】
に符号化する第１符号化手段と、ｉ＝１，・・・・，Ｎに対して、
【００４０】
【数２６】
【００４１】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００４２】
【数２７】
【００４３】
に符号化する第２符号化手段と、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と、前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段とを実現させるためのプログラムである。
【発明の効果】
【００４４】
説明の便宜上、[[ｎ，ｋ]]符号を[[４，１]]符号とし、送りたいデータを｛０，１｝とすると共に、たとえば、送りたいデータの“０”を｛００００，１１１１｝、送りたいデータの“１”を｛００１１，１１００｝と符号化するものとする。本発明では、データを送る際に、その｛ ｝内のいずれか一つのパターンがランダムに選択されて送信される。たとえば、データ“０”のパターンは、“００００”と“１１１１”であるので、その一方をランダムに送信するなどである。このようにすれば、仮に伝送途中の第三者がそのパターンの一部を盗聴し得たとしても、元のデータを推定することはできない。これは、たとえば、“００”を盗聴できたとしても、この“００”は、データ“１”のパターンにも含まれているからである。
したがって、本発明によれば、セキュリティ対策を講じた誤り訂正符号化装置、誤り訂正符号化方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００４５】
【図１】第１の実施形態（[[ｎ，ｋ]]符号化）の概念ブロック図である。
【図２】第２の実施形態（二段階符号化）の概念的な処理フローを示す図である。
【図３】通信系のモデルを示す図である。
【発明を実施するための形態】
【００４６】
以下、本発明の実施形態を説明する。
まず、言葉の定義として、長さａのベクトルｘ＝（ｘ1，・・・・，ｘa）と長さｂのベクトルｙ＝（ｙ1，・・・・，ｙb）を繋げてできる長さａ＋ｂのベクトル（ｘ1，・・・・，ｘa，ｙ1，・・・・，ｙb）を［ｘｙ］で表すことにする。このとき、ｘにｙを連接して［ｘｙ］を得るという。３つ以上のベクトルについても“［”と“］”で括ったもので、同様に連接してできるベクトルを表す。たとえば、［ｘｙｚ］は、ｘにｙを連接し、それにさらにｚを連接してできるベクトルを表す。
【００４７】
＜第１の実施形態（[[ｎ，ｋ]]符号化）＞
図１は、第１の実施形態（[[ｎ，ｋ]]符号化）の概念ブロック図である。このブロックは、冒頭で説明した通信系のモデル図（図３）における符号器として用いることができるものを模式的に表している。このブロックの具体的な構成については特に言及しない。たとえば、ハードロジックで構成されていてもよいし、あるいは、その全てまたはその主要な機能の一部がコンピュータで実行可能なソフトウェアで構成されていてもよい。いずれにせよ、以下に説明する機能を実現できる構成になっていればよい。
【００４８】
図示のブロック全体の名称は、たとえば、冒頭の通信モデルのように、符号器と呼称しても構わないが、ここでは、従来技術の［ｎ，ｍ］符号化と区別するために、二重の括弧を用いて[[ｎ，ｋ]]符号化部１と称することにし、さらに、この[[ｎ，ｋ]]符号化部１による符号化のことを、[[ｎ，ｋ]]符号化と称することにする。
【００４９】
[[ｎ，ｋ]]符号化部１は、少なくとも、ｕ発生部２、ｘ´生成部３及び［ｎ，ｍ］符号化部４を含む。ｕ発生部２は、たとえば、物理的な乱数発生器または疑似乱数発生器であり、［ｎ，ｍ］符号化部４は、従来技術の［ｎ，ｍ］符号化に相当する操作を行うものである。
【００５０】
この第１の実施形態では、情報のセキュリティを確保するため、以下の新しい符号化を行う。この方式は、簡単にいえば、冒頭で説明した公知の［ｎ，ｍ］符号化を用いてｋディジット分の情報を送るというものである。ただし、ｋ≦ｍである。
【００５１】
今、送りたいデータｘが、次式（２８）のようなものであるとする。
【００５２】
【数２８】
【００５３】
ｘ´生成部３は、このデータｘに、ｕ発生部２でランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘk+1，・・・・，ｘm）を連接して、次式（２９）のｘ´を得る。
【００５４】
【数２９】
【００５５】
［ｎ，ｍ］符号化部４は、前記の生成行列Ｇによって指定される［ｎ，ｍ］符号化を用いて、ｘ´生成部３で演算されたｘ´を、長さｎのベクトルｆ（ｘ´）に符号化する。
【００５６】
このように、この第１の実施形態では、送りたいデータｘにランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘk+1，・・・・，ｘm）を連接してｘ´を生成し、そのｘ´を、［ｎ，ｍ］符号化を用いて長さｎのベクトルｆ（ｘ´）に符号化し、それを出力する。
【００５７】
この第１の実施形態における符号化は、前記のとおり、 [[ｎ，ｋ]]符号化であり、生成行列Ｇを変えることで異なる符号化が得られるため、特に符号化を具体的に指定するためには、これを、生成行列Ｇによって指定される[[ｎ，ｋ]]符号化と呼ぶ。この[[ｎ，ｋ]]符号化のイメージは、次式（３０）のように示すことができる。
【００５８】
【数３０】
【００５９】
式（３０）の全体は、図１の[[ｎ，ｋ]]符号化部１に相当する。さらに、ｘ→ｘ´の部分はｘ´生成部３に相当し、ｘ´→ｆ（ｘ´）の部分は［ｎ，ｍ］符号化部４に相当する。
【００６０】
ここで、前記の“発明の効果”の欄で挙げた例が、この第１の実施形態の[[ｎ，ｋ]]符号化で実現できることを説明する。線形符号Ｃの基底を（ｇ1，・・・・，ｇm）とし、このうち（ｇk+1，・・・・，ｇm）の張る部分空間をＢとするとともに、ｎ＝４、ｋ＝１、ｍ＝２とすれば、線形符号Ｃの一例は、次式（３１）のように書き表すことができ、また、Ｂの一例は、次式（３２）のように書き表すことができる。なお、これらは、ＧＦ（ｑ）＝ＧＦ（２）の場合の例である。
【００６１】
【数３１】
【００６２】
【数３２】
【００６３】
この場合、ｇ1、ｇ2は、次式（３３）及び次式（３４）のように書き表すことができる。すると、次式（３５）のように、ｕ発生部２でｘ2＝０，１がランダムに発生されるから、送りたいデータがｘ1＝０であるか、ｘ1＝１であるかに応じて、[[ｎ，ｋ]]符号化器１の出力は、｛００００，１１１１｝か｛１１００，００１１｝になる。ただし、ここでは、ベクトル（１，１，１，１）を“１１１１”と書くなどした。
【００６４】
【数３３】
【００６５】
【数３４】
【００６６】
【数３５】
【００６７】
このように、この第１の実施形態によれば、送りたいデータｘにランダムに発生させたｍ−ｋ個のディジットからなるベクトルｕ＝（ｘk+1，・・・・，ｘm）を連接してｘ´を生成し、そのｘ´を、［ｎ，ｍ］符号化を用いて長さｎのベクトルｆ（ｘ´）に符号化することにより、ｋディジット分の情報を生成出力することができるので、以下の理由から、情報のセキュリティを確保することができる。
【００６８】
今、簡単化のために、[[ｎ，ｋ]]符号を[[４，１]]符号とし、送りたいデータを｛０，１｝とする。この場合、第１の実施形態では、たとえば、送りたいデータの“０”を｛００００，１１１１｝、送りたいデータの“１”を｛００１１，１１００｝と符号化し、データを送る際に、その｛ ｝内のいずれか一つのパターンをランダムに選択して送信する。たとえば、データ“０”のパターンは、“００００”と“１１１１”であるので、その一方をランダムに送信する。仮に伝送途中の第三者がそのパターンの一部を盗聴し得たとしても、元のデータを推定することはできない。これは、たとえば、“００”を盗聴できたとしても、この“００”は、データ“１”のパターンにも含まれているからである。
【００６９】
したがって、この第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）においては、伝送途中の第三者による盗聴を効果的に防止し、セキュリティ対策を講じることができるので、本発明の冒頭の課題を達成することができる。
【００７０】
＜第２の実施形態（二段階符号化）＞
以上説明した第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）においては、セキュリティ対策を講じることができる点で有益である。一方で、理論的な解析により比較的符号長が長い方が復号誤り確率と安全性の点で有利であることは分かっているものの、符号長が長くなるにつれ、符号化や復号化の手続きの煩雑さが増していくことを否めず、この手続きの煩雑さが、実用化する上での障害となる可能性がある。上記のとおり、[[ｎ，ｋ]]符号化は、通信路上での盗聴を回避できるという従来技術にない格別有益なメリットを持つため、かかる障害要因（手続きの煩雑さ）の克服は、是非とも達成されなければならない技術課題である。以下に説明する第２の実施形態は、そのためのものである。簡潔に述べれば、この第２の実施形態は、分割統治の考え方（与えられた問題をいくつかの小さな問題に分割して解き、それをもとに統治をおこない、問題の解を得る手法のこと。分割統治法：Ｄｉｖｉｄｅ ａｎｄ Ｃｏｎｑｕｅｒともいう。）を採用して、大きな符号長を持つ[[ｎ，ｋ]]符号化の処理をいくつかの処理に分けて段階的に行うことにより、前記の障害要因を克服し、以て、産業上の利用に充分に耐え得る誤り訂正符号化の技術を提供するものである。
【００７１】
第２の実施形態について説明する。この第２の実施形態では、以下に詳述するように、一例として、２つの線形符号を使って符号化する方法を開示する。以下、この符号化のことを「二段階符号化」という。
【００７２】
この二段階符号化では、Ｎ＞０，ｎi≧ｍi≧ｋi≧０（ｉ＝１，・・・・，Ｎ）を整数（実用的なのは、ｎi，ｍi，ｋiがｉに依らない場合である。）とするとき、ｍi×ｎi生成行列Ｇiにより指定される[[ｎi，ｋi]]符号化と、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆにより指定される[[Ｎ´，Ｋ´]]符号化とを組み合わせて符号化する。これを、[[Ｎ″，Ｋ″]]符号化という。ただし、Ｎ´とＭ´は、次式（３６）で与えられる。
【００７３】
【数３６】
【００７４】
具体的な[[Ｎ´，Ｋ´]]符号化の方法は、以下のようになる。ここで、送信データの長さはＫ´である。
【００７５】
図２は、第２の実施形態（二段階符号化）の概念的な処理フローを示す図である。この処理フローは、冒頭で説明した通信系のモデル図（図３）における符号器として用いることができるものを模式的に表している。前記の第１の実施形態と同様に、この処理フローは、ハードロジックで構成されていてもよいし、あるいは、その全てまたはその主要な機能の一部がコンピュータで実行可能なソフトウェアで構成されていてもよい。いずれにせよ、以下に説明する機能を実現できる構成になっていればよい。
【００７６】
この処理フローにおいて、まず、ステップＳ１の[[Ｎ´，Ｋ´]]符号化で、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、任意の送りたいデータを、長さＮ´のベクトルに符号化する。このベクトルは、Ｎ個のブロックに分割して、次式（３７）のように書くことができる。
【００７７】
【数３７】
【００７８】
次いで、ステップＳ２の[[ｎi，ｋi]]符号化で、ｉ＝１，・・・・，Ｎに対して、
【００７９】
【数３８】
【００８０】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【００８１】
【数３９】
【００８２】
に符号化する。
【００８３】
そして、最後のステップＳ３で、ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する。
【００８４】
ここで、ステップＳ１で用いる符号について、特に有用なのは、ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆで指定される[[Ｎ´，Ｋ´]]符号化が、ＧＦ（ｑ）の拡大体ＧＦ（ｑk）上の符号に由来する場合である。この場合、たとえば、ＧＦ（ｑk）上のリード・ソロモン符号を使用することができる。実用上、ＧＦ（ｑk）上の［Ｎ，Ｋ］リード・ソロモン符号は、ＧＦ（ｑ）上の［ｋＮ，ｋＫ］符号として用いられている。たとえば、コンパクトディスクに用いられているリード・ソロモン符号などである（ｑ＝２）。
【００８５】
すなわち、ステップＳ１の[[Ｎ´，Ｋ´]]符号化では、従来の［ｎ，ｍ］符号化に相当する［Ｎ´，Ｍ´］符号化を用いることができるが、この部分では、ＧＦ（ｑk）上の［Ｎ，Ｍ］符号をＧＦ（ｑ）上の［ｋＮ，ｋＭ］符号として用いることができる。ただし、Ｎ´＝ｋＮ，Ｍ´＝ｋＭとおく。
【００８６】
なお、これは、ＧＦ（ｑk）の元を、ＧＦ（ｑ）上の長さｋのベクトルとして表現して得られるものである。具体的には、以下のとおりである。今、ＧＦ（ｑ）上の線形空間であるＧＦ（ｑk）の基底をｂ＝（βj）kj=1とする。これを用いて、いかなる要素ζ∈ＧＦ（ｑk）も、次式（４０）のように書くことが可能であるので、このように得られた数の行ベクトル（ｘ1，・・・・，ｘk）を、φ（ζ）の記号で示すことにする。
【００８７】
【数４０】
【００８８】
この変換「ζ→φ（ζ）＝（ｘ1，・・・・，ｘk）」を用いた対応「ξ＝（ξ1，・・・・，ξN）←→［φ（ξ1）・・・・φ（ξN）］」により、ＧＦ（ｑk）上の長さＮのベクトルξと、ＧＦ（ｑ）上の長さｋＮのベクトル［φ（ξ1）・・・・φ（ξN）］とを同一視することができるようになる。
【００８９】
二段階符号化の具体例を説明する。ｎi，ｍi，ｋiがｉに依らない場合、すなわち、ｎ≧ｍ≧ｋ≧０を整数として、ｎi＝ｎ，ｍi＝ｍ，ｋi＝ｋ（ｉ＝１，・・・・，Ｎ）の場合の具体例を挙げる。上記のステップＳ１では、前述したような［ｋＮ，ｋＭ］符号化を用いる。たとえば、ｑ＝２で、ｋ＝４ならば、リード・ソロモン符号による［４・１５，４Ｍ］符号化を用いることができる。ただし、０＜Ｍ≦１５である。この場合、上記のステップＳ１では、次式（４１）が得られる。
【００９０】
【数４１】
【００９１】
ステップＳ２では、同一の生成行列Ｇによって指定される[[ｎ，ｋ]]符号化を、ｙ1(i)，・・・・，ｙk(i)に適用してもよい（ｉ＝１，・・・・，Ｎ）。たとえば、ｎ＝６のとき、次式（４２）〜（４６）として、第ｉ行がgiであるような生成行列Ｇによって指定される[[６，４]]符号化を行う。このように、生成行列Ｇによって指定される[[６，４]]符号化の出力は、ハミング重みが偶数であるようなベクトルとなる。
【００９２】
【数４２】
【００９３】
【数４３】
【００９４】
【数４４】
【００９５】
【数４５】
【００９６】
【数４６】
【００９７】
なお、上記において、拡大体ＧＦ（ｑk）上の符号について取り扱ったのは、このような符号を用いると効率の良い復号を行うことができるからである。しかし、これは、性能的に最良（ベストモード）の実施態様を例示しているに過ぎない。したがって、本発明は、この拡大体ＧＦ（ｑk）上の符号を使用するケースに限定されない。
【００９８】
以上のとおり、この第２の実施形態においては、分割統治の考え方を採用して、大きな符号長を持つ[[ｎ，ｋ]]符号化の処理をいくつかの処理に分けて段階的に行うようにしたので、符号化や復号化の手続きを効率的に行うことができ、手続きの簡素化を図ることができる。したがって、先に説明した第１の実施形態の符号化手法（[[ｎ，ｋ]]符号化）の利点（セキュリティ対策を講じることができる。）を活かしつつ、[[ｎ，ｋ]]符号化の長い符号長に伴う欠点（符号化や復号化の手続きの煩雑さ）を解決し、実用に耐え得る誤り訂正符号化の技術を提供することができる。
【００９９】
なお、この第２の実施形態は、二段階符号化に関するものであるが、二段階に限らず、三段階以上のものも包含する。これは、三段階以上の場合、二段階符号化を手続きの一部に含むからである。したがって、発明にとって必須な事項は、二段階符号化に関する部分（図２のステップＳ１、ステップＳ２）にあるということができる。
【０１００】
前記第１の実施形態は[[ｎ，ｋ]]符号化に関するものであり、また、前記第２の実施形態は二段階符号化に関するものである。これら二つの実施形態は、前式（３０）で示したとおり、たとえば、従来の［ｎ，ｍ］符号化をブラックボックス化することによって極めて単純に構築することができる。これを補足すると、次式（４７）のようになる。
【０１０１】
【数４７】
【０１０２】
この式（４７）より、前記二つの実施形態は、結局、「通信路または記憶デバイス」へ入力する前の部分だけの符号化法であるということができる。
【０１０３】
ちなみに、本発明の本質ではないものの、「復号器」についても言及すれば、前記二つの実施形態に対応する復号器の中身は、概ね次式（４８）のように書き表すことができる。
【０１０４】
【数４８】
【０１０５】
ここで、ｘ，ｕの推定値はそれぞれ、次式（４９）で与えられる。
【０１０６】
【数４９】
【０１０７】
以上のことから、二段階符号化もトータルとして見れば、次式（５０）のように書き表すことができるので、上式（４９）の復号原理を適用することができる。
【０１０８】
【数５０】
【０１０９】
ただし、効率の点では、二段階符号化に対応した二段階の復号化を適用することが望ましい。これは、公知の二段階符号化＝連接符号の復号に類似する。
【０１１０】
なお、前記第１の実施形態において、［ｎ，ｍ］符号化部４の［ｎ，ｍ］符号化は、“生成行列Ｇによって指定される”としてあるが、これは具体例として挙げたある特定の符号の生成行列Ｇに限定されない。［ｎ，ｍ］線形符号の生成行列であれば、ある特定の生成行列Ｇに限らず、全て使用することができる。このことは、第２の実施形態における二段階符号化でも同様である。
【０１１１】
また、先に述べたとおり、前式（４７）は、『前記二つの実施形態が、結局、「通信路または記憶デバイス」へ入力する前の部分だけの符号化法である』ことを意味しているが、これによって、本発明の利用形態を限定的に把握してはならない。つまり、前式（４７）によれば、直接的には、[[ｎ，ｋ]]符号化したデータｆ（ｘ´）を、そのまま通信路または記憶デバイスに入力する最も単純な利用形態のみをイメージさせるかも知れないが、それは、本発明の利用形態の一例を示しているに過ぎないものである。
【０１１２】
たとえば、暗号強度をさらに高める狙いから、本方式を別の暗号化方式と併用することも充分に考えられる利用形態の一つである。この併用形態について説明すると、今、併用する暗号化方式を表す関数をｇとする。そして、上記のｆ（ｘ´）をさらにｇ（ｆ（ｘ´））に暗号化した後に、ｇ（ｆ（ｘ´））を通信路または記憶デバイスに入力するようにすれば、ｆ（ｘ´）の暗号強度がさらにｇで補強されるので、より実用上好ましい強力な暗号化方式とすることができる。ただし、現在普及している暗号方式では一般的にｇは暗号鍵Ｋに依存し、記法としてはｇ＝ｇKの形にすることが多いが、以上の説明では簡単化のために、併用する暗号化方式を表す関数を単にｇとした。したがって、このｇはｇ＝ｇKの形も包含する。
【符号の説明】
【０１１３】
１：[[ｎ，ｋ]]符号化器（誤り訂正符号化装置）
２：ｕ発生部（発生手段、発生工程）
３：ｘ´生成部（生成手段、生成工程）
４：［ｎ，ｍ］符号化部（出力手段、出力工程）
Ｓ１：ステップ（第１符号化手段、第１符号化工程）
Ｓ２：ステップ（第２符号化手段、第２符号化工程）
Ｓ３：ステップ（出力手段、出力工程）
【特許請求の範囲】
【請求項１】
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数１】
に符号化する第１符号化手段と、
ｉ＝１，・・・・，Ｎに対して、
【数２】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数３】
に符号化する第２符号化手段と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と
を備えたことを特徴とする誤り訂正符号化装置。
【請求項２】
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数４】
に符号化する第１符号化工程と、
ｉ＝１，・・・・，Ｎに対して、
【数５】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数６】
に符号化する第２符号化工程と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力工程と
を含むことを特徴とする誤り訂正符号化方法。
【請求項３】
コンピュータに、
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数７】
に符号化する第１符号化手段と、
ｉ＝１，・・・・，Ｎに対して、
【数８】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数９】
に符号化する第２符号化手段と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と
を実現させるためのプログラム。
【請求項４】
前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段を備えたことを特徴とする請求項１記載の誤り訂正符号化装置。
【請求項５】
前記出力工程から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力工程を含むことを特徴とする請求項２記載の誤り訂正符号化方法。
【請求項６】
コンピュータに、
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数１０】
に符号化する第１符号化手段と、
ｉ＝１，・・・・，Ｎに対して、
【数１１】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数１２】
に符号化する第２符号化手段と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と、
前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段と
を実現させるためのプログラム。
【請求項１】
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数１】
に符号化する第１符号化手段と、
ｉ＝１，・・・・，Ｎに対して、
【数２】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数３】
に符号化する第２符号化手段と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と
を備えたことを特徴とする誤り訂正符号化装置。
【請求項２】
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数４】
に符号化する第１符号化工程と、
ｉ＝１，・・・・，Ｎに対して、
【数５】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数６】
に符号化する第２符号化工程と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力工程と
を含むことを特徴とする誤り訂正符号化方法。
【請求項３】
コンピュータに、
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数７】
に符号化する第１符号化手段と、
ｉ＝１，・・・・，Ｎに対して、
【数８】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数９】
に符号化する第２符号化手段と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と
を実現させるためのプログラム。
【請求項４】
前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段を備えたことを特徴とする請求項１記載の誤り訂正符号化装置。
【請求項５】
前記出力工程から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力工程を含むことを特徴とする請求項２記載の誤り訂正符号化方法。
【請求項６】
コンピュータに、
送りたいデータを、ガロア体ＧＦ（ｑ）上のＭ´×Ｎ´生成行列Ｆによって指定される[[Ｎ´，Ｋ´]]符号化により、長さＮ´のベクトル
【数１０】
に符号化する第１符号化手段と、
ｉ＝１，・・・・，Ｎに対して、
【数１１】
を生成行列Ｇiによって指定される[[ｎi，ｋi]]符号化により、長さｎiのベクトル
【数１２】
に符号化する第２符号化手段と、
ｗ(1)，・・・・，ｗ(N)を連接して得られる［ｗ(1)・・・・ｗ(N)］を符号化結果として出力する出力手段と、
前記出力手段から出力される符号化結果を、任意の暗号化方式を表す関数ｇでさらに暗号化して出力する第２の出力手段と
を実現させるためのプログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１１−１７２２７９（Ｐ２０１１−１７２２７９Ａ）
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願番号】特願２０１１−１０７８０７（Ｐ２０１１−１０７８０７）
【出願日】平成２３年５月１３日（２０１１．５．１３）
【分割の表示】特願２００７−１９０４９８（Ｐ２００７−１９０４９８）の分割
【原出願日】平成１９年７月２３日（２００７．７．２３）
【出願人】（５９３１７１５９２）学校法人玉川学園 (38)
【Ｆターム（参考）】
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願日】平成２３年５月１３日（２０１１．５．１３）
【分割の表示】特願２００７−１９０４９８（Ｐ２００７−１９０４９８）の分割
【原出願日】平成１９年７月２３日（２００７．７．２３）
【出願人】（５９３１７１５９２）学校法人玉川学園 (38)
【Ｆターム（参考）】
[ Back to top ]