(57)【要約】【課題】統合的に、圧縮、暗号化及び誤り制御符号化処理することができる統合符号化及び復号装置を提供する。【解決手段】本発明は、前処理を施した入力情報と予め設計した行列との積をとることにより、情報源符号化、暗号化及び通信路符号化を行って符号語を生成する符号化手段と、情報伝送中に誤りが発生した符号語を受信語として入力して通信路誤り訂正・検出、暗号復号及び圧縮データ伸長を行い復号語を生成する復号手段とからなる。典型的には、符号化手段は、前処理によりエントロピー１未満を有する２元列ベクトルmが生成されていることを前提とし、２元非正則行列Aと２元列ベクトルmとの積をとり、c = A・m の関係により２元符号語cを生成し、復号手段は、非正則行列Aに対する因数分解により得られる線形誤り制御符号の生成行列及び検査行列を用いて、受信語を入力として線形誤り制御符号の復号アルゴリズム及び行列演算を実行して復号語を出力する。【選択図】図２
2008242034.tif 000002
【特許請求の範囲】
【請求項１】
ベクトルデータとして表現される入力情報に対し、情報源符号化処理、暗号化処理、及び通信路符号化処理のうちの少なくとも２以上の処理を行うための符号化装置であって、
前記入力情報と符号化のための所定の行列との積算処理により符号化を行う積算符号化処理部を備え、
前記積算符号化処理部の積演算処理により、前記入力情報に対して情報源符号化処理、暗号化処理、及び通信路符号化処理のうちの少なくとも２以上の処理が実行されたこととなる符号語が生成されることを特徴とする符号化装置。
【請求項２】
前記入力情報は長さNsを有する列ベクトルmであり、前記符号化のための行列はNc行Ns列を有する非正則行列Aであり、前記符号語は長さNcを有する列ベクトルc=A・mであることを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記入力情報mは、情報語をエントロピー h < 1を有する２元ベクトルへ変換する機構によって生成された入力情報であることを特徴とする請求項２に記載の符号化装置。
【請求項４】
前記行列Aは、
A = Q-1・GcT・D-1・Hs・T-1
として与えられることを特徴とする請求項２または請求項３に記載の符号化装置。ここで、Q-1はNc行Nc列を有する置換行列Qの逆行列、GcTは線形符号Ccの生成行列Gcの転置行列として定義されるNc行Kc列を有する行列、D-1はKc行Kc列を有する正則行列Dの逆行列、HsはMs行Ns列を有する線形符号Csの検査行列、T-1はNs行Ns列を有する置換行列Tの逆行列であり、Kc=Msである。
【請求項５】
前記行列A, Q-1，GcT，D-1，Hs及びT-1を暗号鍵とすることにより、共通鍵暗号化機能を有することを特徴とする請求項４に記載の符号化装置。
【請求項６】
前記行列Aを公開鍵とし、前記行列Q-1，GcT，D-1，Hs及びT-1のうちの２個以上を秘密鍵とすることにより、公開鍵暗号化機能を有することを特徴とする請求項４に記載の符号化装置。
【請求項７】
前記符号Ccまたは／及び前記符号Csは低密度パリティ検査符号であることを特徴とする請求項４〜請求項６のいずれか１項に記載の符号化装置。
【請求項８】
前記符号Csは、複数の完全符号の検査行列を組み合わせて構成した符号であることを特徴とする請求項４〜請求項６のいずれか１項に記載の符号化装置。
【請求項９】
前記行列D-1は低密度な正則行列Dの逆行列であることを特徴とする請求項４〜請求項８のいずれか１項に記載の符号化装置。
【請求項１０】
前記入力情報は、元の入力情報に対しハッシュ値を付加したものであることを特徴とする請求項１〜請求項９のいずれか１項に記載の符号化装置。
【請求項１１】
前記入力情報は、元の入力情報に対し復号誤り訂正のための符号化処理を施したものであることを特徴とする請求項１〜請求項１０のいずれか１項に記載の符号化装置。
【請求項１２】
受信語に対して通信路符号復号処理、暗号復号処理及び情報源符号復号処理のうちの少なくとも２以上の処理を行って情報語を復号するための復号装置であって、
行列Aに基づいて前記情報語を推定する推定処理部を備え、
前記推定処理部は、長さNsを有する情報語mに対する符号語が長さNcを有する列ベクトル
c = A・m
として与えられるとき、受信語
c’= c + n
を基にしてAの因数分解により得られる複数の行列を用いて情報語mの推定処理を行うことにより、前記情報語を復号することを特徴とする復号装置。
ここで、AはNc行Ns列を有する行列、mは長さNsを有する列ベクトル、nは通信路における雑音を表す長さNcを有するベクトルである。
【請求項１３】
前記行列Aは式
A = Q-1・GcT・D-1・Hs・T-1
で与えられ、前記推定処理部における推定処理は、Gcを生成行列とする線形符号Ccに対する復号処理及びブロック符号
2008242034.tif 000052
に対する復号処理に基づいた処理であることを特徴とする請求項１２に記載の復号装置。
ここで、Q-1はNc行Nc列を有する置換行列Qの逆行列、GcTは線形符号Ccの生成行列Gcの転置行列として定義されるNc行Kc列を有する行列、D-1はKc行Kc列を有する正則行列Dの逆行列、HsはMs行Ns列を有する線形符号Csの検査行列、T-1はNs行Ns列を有する置換行列Tの逆行列、vは長さMsを有する列ベクトルであり、Kc=Msである。
【請求項１４】
前記行列Gcは低密度パリティ検査符号Ccの生成行列であり、前記行列Hsは低密度パリティ検査符号Csの検査行列であり、前記Dは低密度な正則行列であり、前記推定処理は行列Hc，D及びHsに対するグラフ上の確率伝播アルゴリズムに基づいた処理であることを特徴とする請求項１３に記載の復号装置。ここで、Hcは符号Ccの検査行列である。
【請求項１５】
ベクトルデータとして表現される入力情報mに対し、情報源符号化処理、暗号化処理、及び通信路符号化処理のうちの少なくとも２以上の符号化処理を行うための符号化処理方法であって、
長さNsビットを有する2元列ベクトルとして表現される入力情報mを、Nc行Ns列を有する2元行列
A = Q-1・GcT・D-1・Hs・T-1
を用いて、式
c = A・m
の関係により変換することにより、前記入力情報に対して情報源符号化、暗号化及び通信路符号化のうちの少なくとも２以上の符号化処理が実行されたこととなる符号化処理が行なわれることを特徴とする符号化処理方法。
ここで、Q-1はNc行Nc列を有する置換行列Qの逆行列、GcTは線形符号Ccの生成行列Gcの転置行列として定義されるNc行Kc列を有する行列、D-1はKc行Kc列を有する正則行列Dの逆行列、HsはMs行Ns列を有する線形符号Csの検査行列、T-1はNs行Ns列を有する置換行列Tの逆行列であり、Kc=Msである。
【請求項１６】
前記行列Aを公開鍵とし、前記行列Q-1，GcT，D-1，Hs及びT-1のうちの2個以上を秘密鍵とすることにより、公開鍵暗号化機能を有することを特徴とする請求項１５に記載の符号化方法。
【請求項１７】
受信語に対し通信路符号復号処理、暗号復号処理、及び情報源符号復号処理のうちの少なくとも２以上の処理を行って情報語を復号するための復号処理方法であって、
長さNsを有する情報語mに対する符号語が、長さNcを有する列ベクトル
c = A・m = (Q-1・GcT・D-1・Hs・T-1)・m
として与えられ、符号語cに対する受信語が
c’= c + n
として与えられたとき、Gcを生成行列として持つ符号Ccの復号方法及びブロック符号
2008242034.tif 000053
に対する復号方法に基づいて、c’からmを推定して前記情報語の復号を行うことを特徴とする復号処理方法。
ここで、Q-1はNc行Nc列を有する置換行列Qの逆行列、GcTは符号Ccの生成行列Gcの転置行列として定義されるNc行Kc列を有する行列、D-1はKc行Kc列を有する正則行列Dの逆行列、HsはMs行Ns列を有する符号Csの検査行列、T-1はNs行Ns列を有する置換行列Tの逆行列、vは長さMsを有する列ベクトルであり、Kc=Msである。
【請求項１８】
前記符号Cc及びCsは低密度パリティ検査符号であり、前記行列Dは低密度の正則行列であり、前記推定の方法は、行列Hc,D及びHsに対するグラフ上の確率伝播アルゴリズムに基づいた推定であることを特徴とする、請求項１７に記載の復号処理方法。ここでHcは符号Ccの検査行列である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、情報の符号化技術に関し、より詳細には、情報源符号化（データ圧縮及び伸張）、暗号化（及び復号）、通信路符号化（誤り制御符号化及び誤り訂正・検出）を行う符号化技術に関する。
【背景技術】
【０００２】
従来、情報通信システムにおいては、情報を効率的に伝送及び記録するために、種々の情報源符号化技術、すなわちデータ圧縮技術が使用されている。また、高信頼な情報伝送及び記録を行うために、種々の通信路符号化技術、すなわち誤り制御符号化技術が使用されている。さらに、システム外部からの盗聴や改ざんを排除して安全に情報伝送及び記録を行うために、種々の暗号化技術が使用されている。これらの技術については、非特許文献１において網羅的に述べられている。
【０００３】
情報源符号化の要素技術としては、Huffman符号化、算術符号化、辞書式符号化、離散コサイン変換、ウェーブレット変換、動き予測／補償等が知られており、これらの技術を基に、LZ77，LZ78，LZSS，BWT/MTF，等の文書圧縮方式、JPEG，JPEG2000，JPEG-LS等の静止画像圧縮方式、MPEG-1/2/4やH.264/MPEG-4 AVC，等の動画像圧縮方式が標準化されている（例えば、非特許文献２及び３を参照）。
【０００４】
通信路符号化技術としては、パリティ検査符号やHamming符号をはじめとして、BCH符号、半導体メモリ用誤り制御符号、Reed-Solomon符号、Fire符号、畳込み符号、ターボ符号、低密度パリティ検査(LDPC)符号等が既に提案され、実用化されている（例えば、特許文献１及び非特許文献４、５を参照）。
【０００５】
暗号化技術に関しては、共通鍵暗号であるRC4，DES(Data Encryption Standard)，TDES(Triple DES)及びAES(Advanced Encryption Standard)や、公開鍵暗号であるRSA暗号、等が標準化されている（例えば、非特許文献６を参照）。
【０００６】
また、本発明に関連する符号化技術として、通信路符号化に用いられるLDPC符号の検査行列を用いて動画像情報を圧縮する技術や、情報源符号化と通信路符号化を単一の行列演算で行う技術についての提案がなされている（例えば、特許文献２、非特許文献７を参照）。さらに、線形誤り制御符号であるGoppa符号を用いた暗号化技術（例えば、非特許文献８を参照）や、LDPC符号を用いた暗号化技術（例えば、非特許文献９を参照）も提案されている。一方で、線形誤り制御符号を用いた暗号化技術においては、長さNビットを有する暗号文に対し、階数Nを有する行列Gを乗じて圧縮処理を行うため、暗号文再送等によりGの部分行列に対する逆行列が推定できると、暗号文が容易に解読できてしまうという原理的な危険性も指摘されている（例えば、非特許文献８を参照）。
【０００７】
【特許文献１】特開２００６−２４４２５９号公報
【特許文献２】特開２００６−２１７３６３号公報
【非特許文献１】今井秀樹: 情報・符号・暗号の理論; コロナ社, 2004年。
【非特許文献２】植松友彦: 文書データ圧縮アルゴリズム入門; ＣＱ出版社, 1994年。
【非特許文献３】酒井善則, 吉田俊之: 映像情報符号化; オーム社, 2001年。
【非特許文献４】E. Fujiwara, Code Design for Dependable Systems, Wiley, 2006.
【非特許文献５】S. Lin and D. J. Costello, Jr., Error Control Coding, Prentice-Hall, 1983.
【非特許文献６】岡本栄司: 暗号理論入門; 共立出版, 2002年。
【非特許文献７】D. J. C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Trans. Information Theory, Vol.45, N0.2, pp.399-431, March 1999.
【非特許文献８】K. Kobara and H. Imai, “Semantically Secure McEliece Public-Key Cryptosystem,” IEICE Trans. Fundamentals, Vol.E85-A, No.1, pp.74-83, Jan. 2002.
【非特許文献９】N. S. Skantzos, D. Saad and Y. Kabashima, “Analysis of Common Attacks in Public-Key Cryptosystems Based on Low-Density Parity-Check Codes,” Physical Review, E68, 056125, 2003.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記技術背景のもと、情報の符号化処理における演算量は、近年の通信ネットワークの広帯域化と集積回路の高性能化に伴って、急速に増加の一途を辿っている。
【０００９】
例えば、情報源符号化の最終段階で用いるエントロピー符号化方式について、JPEGではHuffman符号を用いているのに対し、JPEG 2000では圧縮効率の高い算術符号が採用されているが、ここで、Huffman符号は情報語シンボルを２元ビット列へ置換することにより圧縮処理を行うのに対し、算術符号化処理においては各種算術演算を行う必要があるので、Huffman符号と比較して多くの演算処理を必要とするという課題がある。
【００１０】
また、暗号化技術に関しては、DESやTDESに代わってAESが推奨される傾向にあるが、このAESの暗号化及び復号処理においては、ガロア体上の演算が必要であり、従来のDESやTDESと比較して演算量が大幅に増大するという課題を有している。また、インターネット等で公開鍵暗号として使用されているRSAは、符号化及び復号処理において冪乗演算が必要であり、処理の高速化を阻害する原因ともなっている。
【００１１】
さらに、通信路符号化技術としては、従来の畳み込み符号やTurbo符号に代わって、LDPC符号が採用される傾向があるが、ここで、高性能なLDPC符号を構成するためには、一般に符号長を数千から数万ビット程度と大きくする必要があり、このようなサイズの大きい符号語を確率計算に基づいて一括して復号するためには、大規模な符号化及び復号回路が必要となっている。
【００１２】
上記課題は、特に、近年広く普及している携帯電話に代表される小型携帯機器において深刻である。つまり、かかる小型携帯機器においては、機器の小型軽量化及び低消費電力化が強く求められる場合が多いことから、機器の高機能化及び性能向上のために上記のような大量の演算を必要とする符号化技術を採用することは、必ずしも最善の解決策にならないことが多い。従って、今後の小型携帯機器の開発においては、より少ない計算量を有する情報源符号化、暗号化及び通信路符号化方式が求められることが予想される。また、一般に集積回路の故障発生率は回路の複雑度に相関することから、医療機器、航空宇宙関連機器等の高信頼性能を要求される分野においては、計算量を抑えた符号化方式を採用して集積回路の複雑化に歯止めをかける必要がある。
【００１３】
加えて、従来の有線通信システムにおいては、一般的に、物理層等の下位のネットワークレイヤにも誤り訂正・検出のための機構を有しているが、通常、暗号化は必要に応じてトランスポート層より上位で行われている。したがって、例えば、安全な通信を行うためのSSL(Secure Socket Layer)，TLS(Transport Layer Security)はトランスポート層のプロトコルとなっている。しかしながら、より安全に情報を伝送するためには、下位のレイヤにおいても暗号化機能を持たせることが望ましい。つまり、例えば、上位レイヤで暗号化を行っていない場合でも下位レイヤにより自動的に暗号化されることにより、平文がネットワーク上を流れることをなくすという具体的解決手段の提供が望まれている。さらに、上位レイヤでSSL等の暗号化を行う場合には、下位レイヤの暗号と併せて情報が二重に暗号化されることにより情報の安全性がより向上する。また、通信システムに入力されるデータは必ずしも圧縮処理されたものではないため、下位レイヤにおいて情報源符号化処理も併せて行えば、効率の高いデータ伝送が可能である。通信システムの下位レイヤにおいては、一般に高スループットのパケット処理が必要であり複雑な計算処理を行えない。
これらの観点から通信システム等を構築するためにも、少ない計算処理量の情報源符号化、暗号化及び通信路符号化手段が必要とされている。
【００１４】
さらに、近年の計算機システムにおいては、機密情報や著作権を有する情報を扱う機会も増加しており、これらの情報の安全性を保障するために、よりハードウェアに近いレベルで暗号化技術を取り入れることが有効である。例えば、プロセッサのデータ入出力部に暗号化・復号回路を組み込むことにより、主記憶上のデータ及びプログラムがプロセッサ固有の鍵で暗号化され、データ共有ソフトやクラッキング等による情報の漏洩を防止することができる。また、計算機システムのデータバスや主記憶装置においては、高クロック化及び集積回路の低電圧化が進んでおり、電磁ノイズや放射線等の影響によりソフトエラーの発生が多くなると予想されることから、上記の暗号化処理に併せて誤り制御符号化処理を施すことが望ましい。さらに、計算機システムの記憶装置を効率的に利用するためには、冗長なデータを圧縮することが求められる。また、計算機のプロセッサ周辺回路は非常に高スループットでデータを処理する必要がある。
以上の観点からも、少ない計算量の情報源符号化、暗号化及び通信路符号化手段の提供が求められている。
【００１５】
そこで、上述の一連の課題を解決すべく、本発明は、従来、多段階で複雑な演算処理を必要としていた情報源符号化、暗号化及び情報源符号化の各処理に関し、これら一連の段階の処理を統合するバイナリの行列演算を主体とした演算処理手段を実現することにより、高スループット、高信頼性を有する低消費電力な符号化・復号方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明にかかる統合符号化及び復号装置、並びに方法（以下、「統合符号化及び復号装置等」、「本発明にかかる装置」、「本発明にかかるシステム」ともいう。なお、本明細書において「装置」又は「システム」というときは、かかる装置又はシステムの動作に対応する処理手順（方法）をも含むものとする。また、単に「処理」というときも、特に断らない限り、「本発明にかかる装置」、「本発明にかかるシステム」等のハードウェア上で実行させるための処理をいうものとする。さらに、「処理」には、その全部又は一部をコンピュータ等のハードウェアに実行させるためのプログラムが含まれる。）によれば、ベクトルデータとして表現される入力情報に対し、情報源符号化処理、暗号化処理、及び通信路符号化処理のうちの少なくとも２以上の処理を行うための符号化装置であって、前記入力情報と符号化のための所定の行列との積算処理により符号化を行う積算符号化処理部を備え、前記積算符号化処理部の積演算処理により、前記入力情報に対して情報源符号化処理、暗号化処理、及び通信路符号化処理のうちの少なくとも２以上の処理が実行されたこととなる符号語が生成されることを特徴とする符号化装置等を提供する。
【発明の効果】
【００１７】
本発明にかかる統合符号化及び復号装置、並びに方法よれば、従来複雑な処理を必要としていた情報源符号化処理、暗号化処理及び通信路符号化処理を、行列演算を主体とした処理で統合的かつ簡便に処理することが可能となり、従来技術に比して符号化演算処理量を格段に減らすことができる。換言すれば、本発明により、線形誤り制御符号の符号化処理と略同等の演算処理量で、情報源符号化、暗号化及び通信路符号化の各処理を統合的に処理することができ、従来技術に比して符号化処理回路または符号化処理プログラムを大幅に簡略化することが可能となり、本発明による復号装置等においては、誤り制御符号の復号処理と略同等のスループットで誤り訂正・検出処理、暗号の復号処理及び圧縮データ伸長処理を行うことが可能となる。それゆえ、高スループット、高信頼性を有する低消費電力な統合符号化・復号方法及び装置を提供することができる。
【発明を実施するための最良の形態】
【００１８】
（実施例１）
［本発明にかかる装置又はシステムの構成例］
本発明は、典型的には集積回路に必要な機能を組み込むことにより構成される。ここで、集積回路にはASIC、ゲートアレイ、FPGAを含む。なお、集積回路に組み込まれるべき機能の一部またはすべてをプロセッサ上でプログラムを実行することにより置き換えることもできる。本発明にかかる装置は例えば、携帯電話機、ルータ、等の通信機器、及びコンピュータ内部のメモリコントローラや入出力コントローラ、ビデオカメラ、監視カメラ、センサネットワーク、等に組み込むことができる。
【００１９】
また、後述の実施例において適宜参照される、本発明を構成する機能ごとの電子回路は、典型的なハードウェアによる一実施形態であるが、この電子回路の持つ機能の全部又は一部をプロセッサ上で実行可能なプログラムによって実施することができることは言うまでもない。つまり、本発明を構成する全ての機能（技術的要素）は、全てを集積回路等のハードウェアで実施することも可能であるし、最低限のハードウェア構成を除いた全てをソフトウェア（プログラム）で実施することも可能である。特に、ハードウェアを制御するためのプログラムとしての本発明は、そのプログラム自体、物の発明として独立して成立し得る。
【００２０】
後述の実施形態において処理手順として説明されている技術要素は、いくつかの例示によっても明らかなように、個々の電子回路として実施することができる。また、個々の電子回路例として説明した技術要素は、当該電子回路が実施する論理演算等の処理手順をプログラムとして記憶装置等に記憶させておき、必要に応じてメモリに読み出して適宜プロセッサ上で実行させることもできる。
【００２１】
［本発明にかかる装置又はシステムにおける技術的意義］
次に、本発明にかかる装置又は情報通信システムにおける技術的意義について述べる。本発明は、簡潔に説明すると、例えば、情報通信システムにおいて広く利用されている情報源符号化、暗号化及び通信路符号化の各処理を統合し、これら一連の処理を、より簡易なベクトル演算処理又は行列演算処理等の処理に置換するものということができる。例えば、図１に、従来の一般的な情報伝送手順を示す。送信データは必要に応じて圧縮（情報源符号化）及び暗号化が施され、これに誤り制御符号化（通信路符号化）を施したものを通信路へ送信するか、または記憶装置に記憶する。受信側においては送信側と逆の手順で復号を行い受信データを得る。これに対し、本発明は、例えば、図２に示すように従来の情報源符号化処理、暗号化処理及び通信路符号化処理を統合して、これら３種の処理を誤り制御符号の符号化処理と類似の処理により実現するものである。また、本発明は計算機システム内部にも適用可能である。例えば、図３に示すように、プロセッサのデータ入出力部に本発明の符号化・復号回路を挿入することにより、メインメモリ及び外部記憶装置等のすべてのデータを、圧縮、暗号化及び誤り制御符号化することができ、データの安全性及び信頼性が向上するとともに、記憶領域の有効利用を可能にする。
【００２２】
「本発明の構成要素」
本発明は、符号化装置及び復号装置からなる。本発明の符号化装置及び復号装置を構成するためには、多種のベクトル演算、行列演算、等が必要である。装置構成のために必要となるこれらの演算は、例えば一般的なコンピュータとソフトウェアにより実行することができる。ここで重要なことは、これらの演算処理は装置を設計する際に一度だけ行うものであり、実際の装置の動作においては複雑な行列演算処理（例えば、逆行列の計算）は不要であるということである。すなわち、符号化装置及び復号装置が実際に動作するときに行う処理は、バイナリベクトルに対する変形処理、及び誤り制御符号の復号処理が主であり、集積回路またはプログラムのどちらによっても装置を実装することができる。
【００２３】
［本発明の実施形態における演算等］
ここで、本発明における「ベクトル」「行列」に対する典型的な演算例を示す。例えば、いまここに、次のような２行２列の２つの行列Ａ及びＢがあるものとする。
2008242034.tif 000003
2008242034.tif 000004
【００２４】
例えば、行列Ａ及び行列Ｂの乗算（積、積算、product、「かける（掛ける）」）は以下のように定義される。
2008242034.tif 000005
【００２５】
ここで、上記演算は例えばガロア体GF(2)上で行う。すなわち、加算及び乗算は以下のように定義される。
2008242034.tif 000006
2008242034.tif 000007
これより、上記の演算は排他的論理和(EX-OR)ゲート及び論理積(AND)ゲートを用いて容易に集積回路で実装できることがわかる。以上の演算例は、行及び列の数が異なる場合であっても、また、ベクトル演算であっても同様である。
【００２６】
また、行列等の「反転」、「転置」、行又は列の「変形」、逆行列、正則行列、検査行列、単位行列等の「生成」等の各種処理についても、後述するような本発明に必要な符号設計のために実行される。以上述べた演算処理等のハードウェア及びソフトウェア上の実施例は、本発明の実施形態においてその組み合わせの全てを記載することはできないが、代表的な実施例については可能な限り例示する。したがって、本実施形態において例示した実施例は、それ自体、本発明の範囲を不当に限定するものではなく、以上述べた観点から、発明の本質を明らかにすることを目的とするものである。
【００２７】
また、本明細書において「手段」と明記されたものは言うまでもなく、演算／変形／変換等についての「処理」もまた、その処理単体で、又は複数種類の処理の任意の組み合わせにおいて、本発明の手段（あるいは、処理部）として構成されうる。具体的には、一実施形態として例示された１又は複数の電子（論理）回路、あるいは、実行手順又は判断基準として明記された方法の全部又は一部を実行するプログラムモジュールは、その任意の組み合わせにおいて本発明の手段（あるいは、処理部）、又は段階を構成しうる。
【００２８】
そして、上述したような基本的な演算処理等をどのように組み合わせて（いかなる制御のもと）本発明を構成する一連の処理を実行するかについては、まず、本発明を構成する本質的機能について概説し、続いて、本発明を構成する各機能について詳細に述べるという順序で、以下に詳述する。
【００２９】
（実施例２）
［本発明を構成する機能概要］
まず、本発明の本質的機能の概要について説明する。各機能の詳細については必要に応じて後述する。本項の説明は、本発明が機能しうる構成を維持する範囲で、可能な限り上位の技術概念を用いて、その技術的機能の説明を試みるものである。
【００３０】
本発明は、相関性除去及びエントロピー変換などの前処理を施した入力情報と予め設計した行列との積をとることにより、情報源符号化、暗号化及び通信路符号化を行って符号語を生成する符号化手段と、情報伝送中に誤りが発生した前記符号語を受信語として入力して通信路誤り訂正・検出、暗号復号及び圧縮データ伸長を行い復号語を生成する復号手段とからなる。本発明の目的は、前記符号化手段として、前処理によりエントロピー1未満を有する2元列ベクトルmが生成されていることを前提とし、２元非正則行列Aと前記２元列ベクトルmとの積をとり、
c = A・m
の関係により２元符号語cを生成する手段を備えることにより、また、前記復号手段として、前記非正則行列Aに対する因数分解により得られる線形誤り制御符号の生成行列及び検査行列を用いて、前記受信語を入力として線形誤り制御符号の復号アルゴリズム及び行列とベクトルとの乗算演算を実行して前記復号語を出力する手段を備えることにより効果的に達成される。
【００３１】
ここで、行列及びベクトルに対する演算は、ガロア体GF(2)上で定義される。また、２元情報系列のエントロピーENTは、「0」の出現確率をq0、「1」の出現確率をq1とすると、ENT=-q0log2(q0)-q1log2(q1)として定義される。完全にランダムな系列はエントロピーENT=1を有し、「0」と「1」の出現に偏りがある場合は、エントロピーは1以下となる。以下では一般性を失わず、q0>q1であるとする。
【００３２】
前記非正則行列Aは、例えば式（１）により構成できる。
A = Q-1・GcT・D-1・Hs・T-1    …（１）
ここで、AはNc行Ns列を有する非正則行列、Q-1はNc行Nc列を有する置換行列Qの逆行列、GcTは線形誤り制御符号Ccの生成行列Gcの転置行列として定義されるNc行Kc列を有する行列、D-1はKc行Kc列を有する正則行列Dの逆行列、HsはMs行Ns列を有する線形誤り制御符号Csの検査行列、T-1はNs行Ns列を有する置換行列Tの逆行列であり、Ms=Kcである。ただし、符号Ccは通信路誤りを訂正するための線形符号であり、符号Csは1以下のエントロピーを有する２元ベクトルmを圧縮するための線形符号である。符号Cc及びCsは、例えばLDPC符号、Reed-Solomon符号、BCH符号、ビット／バイト誤り制御符号、Hamming符号、等を基に構成することができる。前記各行列は、符号化装置及び復号装置の設計時に予め生成して適切な回路またはプログラムとして装置に組み込んでおく。よって、装置が実際に動作して符号化・復号処理を行う際に、逆行列演算、転置行列生成、等の処理をその都度行う必要はない。このことは後述する符号化・復号手順において具体的に示している。
【００３３】
ここで、行列A, Q-1, GcT, D-1, Hs及びT-1をすべて暗号鍵とすることにより共通鍵暗号方式を実現できる。また、行列Aを公開鍵とし、それ以外の２個以上の行列を秘密鍵とすることにより、公開鍵暗号方式を実現できることが、本発明の重要な特徴のひとつである。
非正則行列Aが式（１）により与えられるとき、秘密鍵を有する正当な受信者は、列ベクトルとして表現される受信語
c’= c + n
を以下の手順により復号することができる。ただし、nは通信路誤りを表す列ベクトルである。はじめに、前記受信語c’を
c”= Q・c’
の関係によりベクトルc”へ変換する。ここで、式（１）に示す非正則行列Aの構成より、c”は符号Ccの符号語に誤りベクトルQ・nを加えたベクトルとなっているから、ベクトルc”を入力として前記線形誤り制御符号Ccに対する復号アルゴリズムを実行することにより、通信路誤りを訂正して長さNcビットを有する中間復号語uを生成できる。次に、前記中間復号語uの情報部u1を
v = D・u1
の関係によりベクトルvへ変換する。ここで、v=Hs・T-1・mが成立しているから、前記ベクトルvにより決定されるブロック符号
2008242034.tif 000008
について、受信語を全零として復号アルゴリズムを実行することにより後段復号語w=T-1・mを生成できる。最後に、前記後段復号語wを
m’ = T・w
の関係により復号語m’=mが得られる。
【００３４】
前記復号手順において、行列とベクトルの積算処理が必要であるが、この演算は組み合わせ回路により容易に実現できる。回路の構成例は、後述の例で示している。
【００３５】
また、前記線形誤り制御符号Cc及びCsがLDPC符号であり、かつ前記正則行列Dが低密度な行列であるとき、前記LDPC符号Ccの検査行列Hc、前記正則行列D及び前記LDPC符号Csの検査行列Hsから導出される単一のグラフGを用いて、前記受信語c’を入力として前記グラフG上での確率伝播アルゴリズムを実行することにより前記復号語m’を生成することも可能である。
【００３６】
本発明の実施方法の例を簡単にまとめると以下のとおりとなる。
１．符号化装置及び復号装置の設計を行う。すなわち、置換行列Q及びT、正則行列D、線形誤り制御符号の生成行列Gc、及び線形誤り制御符号の検査行列Hsを構成する。次に、式（１）に従って行列Aを構成する。なお、この処理は装置設計時に一回だけ行う。
２．符号化装置は、入力情報mに対して、符号語c = A・mを計算して出力する。
３．復号装置は、符号語c’を入力して前記の復号処理を行い、復号語m’を出力する。
【００３７】
上記の符号化・復号手段は、入力情報、符号語及びすべての行列をガロア体GF(2)上で定義する場合について述べているが、これを任意の体GF(q)へ拡張することによっても本発明の目的が達成できることは明らかである。また、前記線形符号Cc及びCsとして、regular LDPC符号，irregular LDPC符号，repeat-accumulate符号，等の各種線形符号を用いることによって本発明の目的が達成できることも明らかである。さらに、本発明による公開鍵暗号の安全性を高めるため、入力情報にあらかじめハッシュ値を付加して符号化を行うことも可能である。
【００３８】
（実施例３）
［本発明を構成する各機能の詳細］
以下、本発明を実施するための最良の形態について、図面を参照し、処理の流れを含めて、各機能（又は当該機能を実現する電子回路）に着目しながら詳細に説明する。
【００３９】
まず、本発明における符号化及び復号の全体の流れを図４に示す。本発明の実施例における符号化装置への入力情報は、エントロピーENTを有する長さNsビットの２元列ベクトルm=(m0,m1,...,mNs-1)であるとする。ただし、ENTは0以上1未満の実数である。列ベクトルmは、例えば以下の手順で生成できる。まず、動画像情報、静止画像情報、文書情報、音声情報、等の各種情報源に対し適切な相関性除去処理適用することによりシンボル間の相関性を十分に除去した情報系列Mを生成する。
【００４０】
次に、情報系列Mのそれぞれのシンボルを固定長の2元ベクトルへ変換することにより列ベクトルmを生成する。このとき、出現確率の高いシンボルから順にHamming重みの小さい2元ベクトルを割り当てることにより、1未満のエントロピーを有する２元列ベクトルmを生成できる。２元列ベクトルmの生成例を図５に示す。
【００４１】
また、情報系列Mに対し、情報源のコスト付き符号化の概念（例えば、非特許文献「植松友彦: 情報源のコスト付き符号化とその応用; 電子情報通信学会論文誌A, Vol.J87-A, No.5, pp.588-596, 2004年5月」を参照）を利用して適切な変換を施すことによっても２元列ベクトルmを生成することができる。なお、入力情報がエントロピーの高い（すなわち、ENT≒1であるような）バイナリ情報である場合は、完全符号であるHamming符号またはGolay符号の検査行列H、あるいはベクトル変換のためのルックアップテーブル等を用いて列ベクトルmを生成することができる。例えば、完全符号の検査行列Hを用いて生成する場合には、バイナリ情報系列Mと列ベクトルmがH・m=Mの関係を満たすように変換を行うことにより、２元列ベクトルmを生成できる（図６を参照）。
【００４２】
以下では、２元入力情報における「0」の出現確率をq0、「1」の出現確率をq1とし、q0>q1であるとする。なお、q0<q1である場合には入力情報を反転すればよい。このとき２元入力情報系列のエントロピーはENT=-q0log2(q0)-q1log2(q1)であり、符号化率R=Ns/Ncを有する符号を用いて誤り率が十分に低い情報伝送を行うためには、通信路容量CAPはCAP>ENT×Rを満足する必要がある。
【００４３】
次に、本発明を実施するための最良の形態を示すため、本発明の符号化及び復号に用いる行列を定める。符号長Ncビット、検査長Mcビットを有する線形誤り制御符号Ccの検査行列をHcとする。ただし、符号Cc及びその符号長Ncと検査長Mcは想定された通信路または記憶装置において正確な情報伝送・記憶ができるように定めるものとし、Hcの右側Mc列は線形独立であるとする。符号Ccとしては、例えば、パリティ検査符号、Hamming符号、BCH符号、Reed-Solomon符号、Fire符号、半導体メモリ用符号（例えば、非特許文献「E. Fujiwara, Code Design for Dependable Systems, Wiley, 2006」を参照）、LDPC符号、等を使用できる。検査行列Hcに対し行基本変形を施し、右側Mc列が単位行列となるように構成した行列を
Hc’= [ P | IMc ]
とおく。ただし、PはMc行Kc列を有する部分行列であり、IMcはMc行Mc列を有する単位行列である。ここで、Kc=Nc-Mcである。符号Ccの生成行列は以下の式で与えられる。
Gc = [ IKc | PT ]
ただし、PTはPの転置行列、IKcはKc行Kc列を有する単位行列である。次に、符号長Nsビット、検査長Msビットを有する線形誤り制御符号Csの検査行列をHsとする。ただし、符号Cs及びその符号長Nsと検査長Msは、誤り率がq1である２元対称通信路において正確な情報伝送ができるように選択し、かつブロック符号
2008242034.tif 000009
に対する復号法は既知であるものとする。ここで、vは長さMsを有する列ベクトルである。また、HsはMs行Ns列を有する2元行列であり、Ms=Kcを満足する。符号Csとしては、例えば、LDPC符号、BCH符号、Reed-Solomon符号、ビット／バイト誤り制御符号（例えば、非特許文献「E. Fujiwara, Code Design for Dependable Systems, Wiley, 2006」を参照）や完全符号であるHamming符号及びGolay符号を基にして構成した符号を用いることができる。
【００４４】
なお、完全符号を基にした符号Csの構成法は、後述の例において示している。Nc行Nc列を有する置換行列をQとする。ただし、置換行列とは、すべての行および列がHamming重み1を有する正則行列のことである。Ns行Ns列を有する置換行列をTとする。Ms行Ms列を有する任意の正則行列をDとする。符号化のための行列Aを以下の式により定める。
A = Q-1・GcT・D-1・Hs・T-1  …（２）
ただし、AはNc行Ns列を有する行列であり、Q-1はQの逆行列、GcTはGcの転置行列、D-1はDの逆行列、T-1はTの逆行列である。
【００４５】
上記の行列A, Q-1, GcT, D-1, Hs及びT-1を暗号鍵とすることにより、共通鍵暗号方式を実現できる。また、Aを公開鍵とし、それ以外の行列を秘密鍵とすることにより公開鍵暗号方式を実現できる。上記の行列構成について図７に示す。
【００４６】
なお、上記の行列Q,Gc,D,Hs及びTを適切に選択することにより、符号化装置が有する情報源符号化機能、暗号化機能及び通信路符号化機能を調整することができる。すなわち、符号化装置において、情報源符号化、暗号化及び通信路符号化を行う場合は上述のように、行列Q及びTは置換行列、行列Dは正則行列、行列Gcは線形誤り制御符号の生成行列、行列Hsは線形誤り制御符号の検査行列とする。符号化装置において情報源符号化と暗号化のみを行う場合は、行列Q及びTは置換行列、行列Dは正則行列、行列Gcは単位行列、行列Hsは線形誤り制御符号の検査行列とする。符号化装置において情報源符号化と通信路符号化のみを行う場合は、行列Q,T及びDは単位行列、行列Gcは線形誤り制御符号の生成行列、行列Hsは線形誤り制御符号の検査行列とする。符号化装置において暗号化と通信路符号化のみを行う場合は、行列Q及びTは置換行列、行列Dは正則行列、行列Gcは線形誤り制御符号の生成行列、行列Hsは線形誤り制御符号の検査行列とし、入力情報にエントロピー変換を施す。符号化装置の機能に応じた行列Q,Gc,D,Hs及びTの選択方法を図８まとめる。
【００４７】
上記の準備のもと、本発明の最適な実施形態における符号化の手順は以下のように非常にシンプルに定義できる。長さNsビットを有する２元入力情報を m=(m0, m1, ..., mNs-1)T とする。ここでmのエントロピーはENTであり、列ベクトルとして表現する。入力情報mは以下の式により符号化する。
c = A・m
ここで、cは符号語である（図９を参照）。
【００４８】
なお、暗号の改ざん攻撃等に対する耐性を高めるため、情報ビット数をNs-Bビットとし、mの最後のBビットを情報ビットに対するハッシュ値（例えばSHA-1により生成した値）とすることもできる。また、これ以外にも、暗号の安全性を高めるための処理、情報語のエントロピーを調整するための処理、復号誤りを訂正するための連接符号化処理、等を、mに対してあらかじめ適用した後、上記符号化処理を行うこともできることは明らかである。
【００４９】
次に、正当な受信者が雑音を有する受信語
c’= c + n  … （３）
から、情報語mを復元するための復号法を図１０に示す流れに沿って説明する。ただし、nは通信路における雑音を示す長さNcを有する列ベクトルである。はじめに、受信語c’の左から行列Qをかける。このとき、式（２）及び式（３）より、以下の関係が成立する。
c”= Q・c’= Q・c + Q・n = (GcT・D-1・Hs・T-1・m) + Q・n … （４）
【００５０】
なお、復号装置において、ベクトルm,c及びnは未知、それ以外の行列及びベクトルは既知である。式（４）より、c”は符号Ccの符号語に雑音Q・nが重畳されたものであることがわかる。ここで、Qは置換行列であり、雑音のエントロピーは変化しないことから、c”を符号Ccの復号法により復号することにより、雑音成分Q・nを除去することができる。なお、Ccの復号法が軟判定復号である場合、受信語c’とQからsoft-input情報を生成できることは明らかである。ベクトルc”から雑音を除去したベクトルをuとすると、uは以下の式で表現できる。
u = GcT・D-1・Hs・T-1・m
【００５１】
なお、復号装置においてmは未知、それ以外の行列及びベクトルは既知である。生成行列GcTの上側Kc行は単位行列であるから、以下の式が成立する。
u1 = D-1・Hs・T-1・m
ただし、u1はuの先頭Kcビットである。次に、ベクトルu1の左から行列Dをかけることにより以下の式を得る。
v = D・u1 = Hs・T-1・m
ここで、
w= T-1・m
とおくと、T-1は置換行列であるから、mとwのエントロピーは等しい。従って、
v = Hs・w
の関係を用いて、ブロック符号
2008242034.tif 000010
に対する復号を行うことによりwを得ることができる。すなわち、受信語を全零としてブロック符号
2008242034.tif 000011
の復号を行うことにより、wが得られる。最後にTとwの積をとり以下の式により復号語m’を復元する。
m’= T・w= m
以上の手順により入力情報mが復元される。
【００５２】
符号Cc及びCsがLDPC符号であり、Dが低密度な正則行列である場合、上記の復号アルゴリズムよりもさらに低い復号誤り率を与える復号アルゴリズムが存在する。本アルゴリズムは、図１１に示すような３層のTannerグラフ上の確率伝播アルゴリズムを用いて実行する。ここで、第１層は符号Ccに対するTannerグラフ、第２層は低密度正則行列Dに対するTannerグラフ、第３層は符号Csに対するTannerグラフである。なお、Tannerグラフ上の確率伝播アルゴリズム（sum-productアルゴリズム）に関しては、例えば、非特許文献「D. J. C. Mackay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Transactions of Information Theory, Vol.45, No.2, pp.399-431, March 1999」に開示されている。
【００５３】
アルゴリズムの初期値として、第１層の各Vノードの初期値log(p0/p1)を受信語c”= Q・c’に基づいて、一般的なsum-productアルゴリズムと同様に決定する。ただし、p0は受信ビットが「0」である確率、p1は受信ビットが「1」である確率である。また、第３層のVノードの初期値をlog(q0/q1)とする。ただし、q0及びq1はそれぞれ２元入力情報において「0」及び「1」が出現する確率である。
【００５４】
設定した初期値に基づいて、sum-productアルゴリズムと同様に各ノードで外部情報(extrinsic information)に基づいて確率の更新を行う。この更新処理を十分な回数反復して行うと、第３層Vノードにおける最終的な確率値を利用して、復号結果であるベクトルwを決定できる。最後にベクトルwの左から行列Tをかけることにより、復号語m’= T・wを得ることができる。
【００５５】
なお、上記の実施形態においては、入力情報及び符号語が２元ベクトルとして表現される場合について述べているが、これらのベクトルがガロア体GF(q)上のベクトルとして与えられる場合は、各行列をガロア体GF(q)上で定義することにより、符号化・復号を行うことができる。ただし、qは素数または素数のべき乗である。
【００５６】
本発明の実施形態により実現できる情報源符号化及び通信路符号化装置の性能について通信理論の観点から簡単に述べる。符号Cc及びCsがShannon限界に漸近する最適な機能を有すると仮定すると、以下の２式が成立する。
ENT ≒ Ms/Ns
CAP ≒ Kc/Nc
ただし、ENTは入力情報のエントロピー、CAPは通信路容量である。ここで、Ms=Kcより本符号化法の符号化率Rは以下の式で与えられる。
R = Ns/Nc = (Kc/Nc)/(Ms/Ns) ≒ CAP/ENT
よって、本符号化法もShannon限界に漸近する。従って、符号Cc及びCsとしてShannon限界に近い符号を用いると、本符号化法によりShannon限界に近い効率的な情報源符号化及び通信路符号化がおこなえることがわかる。すなわち、本発明は、性能のよい誤り制御符号を組み合わせることにより、情報源符号化、暗号化及び通信路符号化のうちの、２以上の複合機能を有する高効率な符号化・復号装置を提供できることが大きな特徴となっている。
【００５７】
次に、暗号の安全性について簡単に述べる。本発明による暗号化を公開鍵暗号として用いる場合、公開鍵Aから秘密鍵Hc,Gc,Hs,Q,D及びTが推定できてはならない。一般に、2個以上のランダムな行列の積から元の行列を推定すること（すなわち行列の因数分解）は困難であることが証明されているから、本発明における秘密鍵は、行列Hc,Gc,Hs,Q,D及びTのうち2個以上の行列がランダムに構成されていれば安全であることがわかる。次に、暗号文の安全性について述べる。本発明における平文（情報語）mと暗号文（符号語）cの関係は以下の式で表される。
c = A・m  …（５）
ここで、Aの階数rank(A)がベクトルmの長さNsよりも小さいことから、Aとcからmを求めることは困難である。なぜならば、式（５）においてAとcからmを求める問題は、低密度ではないランダムな検査行列Aで定義される線形誤り制御符号の復号問題と等価であり、この問題を効率的に解くアルゴリズムは知られていないからである。
【００５８】
以上のことから、符号Cc及びCsに求められる条件をまとめると以下のとおりとなる。
(1) 符号Ccは線形符号であること。
(2) 符号Ccは情報伝送に用いる伝送路において、できるだけShannon限界に近い符号化率で情報伝送が可能であること。
(3) 符号Csは線形符号であり、かつCsの検査行列をHsとしたとき、任意の列ベクトルvについてブロック符号
2008242034.tif 000012
に対する復号法が存在すること。
(4) ブロック符号
2008242034.tif 000013
は、2元対称通信路において、
できるだけShannon限界に近い符号化率で情報伝送が可能であること。
(5) 符号Ccの生成行列及び符号Csの検査行列は、高いランダム性を有すること。
【００５９】
上記のような条件を満たす符号として、irregular LDPC符号が存在する（例えば、非特許文献「T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes,” IEEE Trans. Information Theory, Vol.47, No.2, pp.619-637, Feb. 2001」を参照）。すなわち、本発明は符号Cc及び符号Csとしてirregular LDPC符号を用いることにより、効果的に実施できる。なお、上記の条件はあくまでもShannon限界に近い情報伝送を行うためのものであり、実用上は必須ではない場合もある。たとえば、本発明を半導体メモリ装置に適用する場合、符号Ccは少数のビット誤りまたはバイト誤りを訂正・検出できれば十分であり、この場合は符号Ccとしてスポッティバイト誤り制御符号（例えば、特許文献、「特許第3879082号明細書」及び「特許第3743915号明細書」を参照）等を用いることができる。
【００６０】
ここでは、具体的な例を用いて本発明で開示する手法により符号化及び復号が行えることを示す。なお、以下に示す手順はあくまで一例であって、本発明がこれに限定されないことは言うまでもない。以下の例では、説明を簡単にするために入力情報m=(m0,m1,...,m9)Tは長さNs=10ビットを有し、mのHamming重み（すなわちmに含まれる「1」の数）は0または1であるとする。また、符号語c=(c0,c1,...,c9)Tの長さもNc=10ビットであり、符号語cに対する受信語
2008242034.tif 000014
は高々1ビットの誤りを有するものとする。また、Kc=Mc=Ms=5であるとする。なお、実際に効率が良く安全な情報伝送を行うためにはNs及びNcを十分大きな数（例えば10000ビット）とする必要がある。
【００６１】
はじめに、符号化及び復号に用いる行列を構成する。符号Ccの検査行列Hcを以下のように定める。
2008242034.tif 000015
【００６２】
ここで、Hcは1ビット誤り訂正Hamming符号の検査行列を短縮化して構成した行列である。符号Ccの生成行列Gcは次の式により与えられる。
2008242034.tif 000016
【００６３】
これより、生成行列Gcの転置行列は次の式により与えられる。
2008242034.tif 000017
【００６４】
符号Csの検査行列Hsを以下のように定める。
2008242034.tif 000018
【００６５】
ただし、Hsは1ビット誤り訂正Hamming符号の検査行列を短縮化して構成した行列である。置換行列Qを以下の式により定める。
2008242034.tif 000019
【００６６】
置換行列Qの逆行列Q-1は以下の式により与えられる。
2008242034.tif 000020
【００６７】
正則行列Dを以下の式により定める。
2008242034.tif 000021
【００６８】
正則行列Dの逆行列D-1は以下の式により与えられる。
2008242034.tif 000022
【００６９】
置換行列Tを以下の式により定める。
2008242034.tif 000023
【００７０】
置換行列Tの逆行列T-1は以下の式により与えられる。
2008242034.tif 000024
【００７１】
行列Aを以下の式により定める。
2008242034.tif 000025
【００７２】
行列Aを公開鍵とし、それ以外のすべての行列を秘密鍵とすることにより、公開鍵暗号方式を実現できる。なお、行列Aは実用的には大きな行列（例えば5000行5000列を有する行列）となるため、公開鍵Aを因数分解して秘密鍵を推定することは非常に困難である。
【００７３】
前記の各行列をひとたび構成すれば、符号化は以下に示すように簡単に行える。長さNs=10ビットを有する入力情報が以下の列ベクトルとして与えられるとする。
2008242034.tif 000026
【００７４】
長さNc=10ビットを有する符号語cは以下の式により容易に得られる。
2008242034.tif 000027
【００７５】
行列Aを用いた符号化回路の例を図１２に示す。ここでは、説明を簡単にするためにmのHamming重みを1と定めたため、cがAの列ベクトルと一致することからcからmが容易に推定できてしまう。実際にはmのHamming重みが一定値以上となるように制約することにより、このような脆弱性は回避できる。
【００７６】
復号手順の例を、図１３に示す復号回路のブロック図に従って説明する。長さNc=10ビットを有する受信語が以下の式により与えられるものとする。
2008242034.tif 000028
【００７７】
ここで、通信路誤りは受信語の最後のビットに存在する。受信語c'の左からQをかけ、以下の列ベクトルc”を得る。
2008242034.tif 000029
【００７８】
この演算は図１４に示す置換回路Qにより実現できる。次に、ベクトルc”を符号Ccにより復号する。ここでは、符号CcとしてHamming符号を用いているため、まず以下の式によりシンドロームsを計算して復号を行う。
2008242034.tif 000030
【００７９】
シンドロームsは検査行列Hcの第3列と一致する。よって、c”の第3ビットを反転し以下の列ベクトルuを得る。
2008242034.tif 000031
【００８０】
符号Ccの復号回路の例を図１５に示す。なお、符号CcとしてLDPC符号を用いる場合は、sum-product復号器により復号する（例えば、非特許文献「D. J. C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Trans. Information Theory, Vol.45, No.2, pp.399-431, March 1999」を参照）。列ベクトルuの先頭Kc=5ビットを取り出し、以下の列ベクトルu1を得る。
2008242034.tif 000032
【００８１】
列ベクトルu1の左から正則行列Dをかけ、以下の列ベクトルvを得る。
2008242034.tif 000033
【００８２】
正則行列Dと列ベクトルu1の積を計算するための回路を図１６に示す。続いて、ブロック符号
2008242034.tif 000034
の復号を行う。すなわちCs(v)の符号語のうちHamming重み0または1を有する語を検索する。この結果、以下の列ベクトルwが復号結果として得られる。
2008242034.tif 000035
【００８３】
ブロック符号Cs(v)の符号語の中から、Hamming重み0または1を有する語を検索するための回路の例を図１７に示す。なお、符号CsとしてLDPC符号を用いている場合は、sum-productアルゴリズムにより復号を行うことができる。最後に列ベクトルwの左から置換行列Tをかけ、以下のように復号語m’を得る。
2008242034.tif 000036
【００８４】
この演算は図１８に示す置換回路Tにより実現できる。以上の例から、復号語m’は入力情報mと一致することがわかる。
【００８５】
なお、図１３から明らかなように、復号処理はパイプライン化が容易であるため、高スループットを有する復号回路の構築が可能である。また、上記の符号化処理及び復号処理の一部またはすべてをソフトウェアにより処理することも可能である。
【００８６】
以下では、本発明を計算機システムのプロセッサのデータ入出力部に適用し、メインメモリ（主記憶装置）の内容を、情報源符号化、暗号化及び通信路符号化する例を具体的に示す。図１９に示すように、プロセッサのデータ入出力幅は16ビットであるとし、メインメモリのデータ入出力幅は22ビットであるとする。図１９のエントロピー変換部は、任意のHamming重みを有する長さ16ビットのベクトルを入力し、Hamming重み4を有する長さ60ビットのベクトルを出力する機能と、その逆変換を行う機能を有する。また、図１９の符号化装置はHamming重み4以下を有する長さ60ビットのベクトルmに対し、情報源符号化、暗号化及び通信路符号化を適用し、長さ22ビットを有する符号語cを出力する。よって、本システムは22-16=6ビットの冗長ビットを有する。なお、実際のシステムにおいては、データ入出力幅は上記の値よりも大きい場合が多いが、以下では説明を簡単にするため小さなデータ入出力幅を仮定する。メインメモリの内容を暗号化するとともに、メインメモリ上で長さ22ビットを有するワード上に発生した任意の１ビット誤りを訂正し、２ビット誤りを検出するための符号化・復号装置の構成を以下に示す。なお、以下では説明を簡単にするためにデータの圧縮率は固定とする。データの圧縮率を変えるためには、メモリアドレスの動的変換が必要であるが、このための手法は、例えば、非特許文献「R. B. Tremaine, P. A. Franaszek, J. T. Robinson, C. O. Schulz, T. B. Smith, M. E. Wazlowski, and P. M. Bland, “ IBM Memory Expansion Technology (MXT),” IBM Journal of Research and Development, Vol.45, No.2, pp.271-285, March 2001」に開示されている。
【００８７】
符号化・復号回路とプロセッサとの間にはエントロピー変換回路を挿入する。すなわち、プロセッサからメインメモリへの書き込みを行う場合は、プロセッサから出力される16ビットの情報を、エントロピーの低い長さ60ビットのベクトルへ変換して符号化回路へ入力する。また、メインメモリから読み出しを行う場合には、復号回路から出力される長さ60ビットのベクトルを、エントロピーの高い長さ16ビットのベクトルへ変換する。このエントロピー変換部は、図２０に示すように、図６に示すエントロピー変換機構を4個並列に備えることにより実現できる。図６のエントロピー変換機構の具体的な回路構成を図２１に示す。すなわち、図２１に示す回路は、図６に示す関係に従って、長さ4を有するベクトル(M0,M1,M2,M3)を長さ15を有するベクトル(m0,m1,...,m14)に変換する機能、及び長さ15を有するベクトル
2008242034.tif 000037
を長さ4を有するベクトル
2008242034.tif 000038
へ変換する機能を有する。ここで、(m0,m1,...,m14)のHamming重みは高々1である。
【００８８】
次に、符号化及び復号に用いる行列を構成する。符号Ccの検査行列Hcは符号長32ビット、検査長6ビットを有する奇数重み列１ビット誤り訂正・２ビット誤り検出(SEC-DED)符号の検査行列（例えば、非特許文献「E. Fujiwara, Code Design for Dependable Systems, Wiley, 2006」を参照）から、ランダムに22個の列ベクトルを選択することにより構成する。ただし、行列の右端は6行6列を有する単位行列となるようにする。これによりMc=6行Nc=22列を有する組織形の検査行列Hcを構成する。検査行列Hcの例を図２２に、生成行列の転置行列GcTの例を図２３に示す。 
【００８９】
行列Hsは16行60列を有する行列であり、図２４に示すように4行15列を有する部分行列を縦方向及び横方向に4個並べた構造を有する。ここで、行列の対角成分にあたる部分行列Hs(i)は4行15列を有する1ビット誤り訂正Hamming符号の検査行列をランダムに行置換することにより構成した行列であり、それ以外の部分行列は零行列である。行列Hsの例を図２５に示す。なお、上記行列Hsは、エントロピー変換部の構成に依存して決定する。すなわち、上記エントロピー変換部は下記のような長さN=n×bビットを有するベクトルmを出力すると仮定する。
2008242034.tif 000039
ただし、
2008242034.tif 000040
のHamming重みは高々tである。例えば、上記の例ではb=15，n=4，t=1である。このとき、Hsを構成する部分行列Hs(i)は、符号長bビット、検査長rビットを有するtビット誤り訂正符号の検査行列の列ベクトルをランダムに置換して構成する行列とし、Oは同一の大きさを有する零行列とする。行列Hsは図２４に示す構成法に従ってHs(i)及びOを縦方向及び横方向にそれぞれn個並べることにより構成する。
【００９０】
行列Qを22行22列を有する置換行列とする。行列Qとその逆行列Q-1の例を図２６に示す。行列Dを16行16列を有する正則行列とする。行列Dとその逆行列D-1の例を図２７に示す。行列Tを以下の式により定めるブロック置換行列とする。
2008242034.tif 000041
【００９１】
ただし、Tは60行60列を有するブロック置換行列、T'は4行4列を有する置換行列、Iは15行15列を有する単位行列であり、
2008242034.tif 000042
はテンソル積を表す。図２８にブロック置換行列Tの構成を示す。長さ60を有する列ベクトルxに対しブロック置換行列Tを左から乗じると、xの要素は長さ15ビットのブロック単位で置換される（図２９を参照）。ブロック置換行列によりブロック内のHamming重みが変化しないような置換が可能である。ブロック置換行列Tとその逆行列T-1の例を図３０に示す。なお、行列Tはエントロピー変換部の構成に依存して決定する。すなわちエントロピー変換部が式（６）に示すベクトルを出力すると仮定すると、T'はn行n列を有する置換行列、Iはb行b列を有する単位ベクトルとし、nb行nb列を有するブロック置換行列Tを構成する。
【００９２】
符号化のための行列Aは以下の式により定める。
2008242034.tif 000043
行列Aの例を図３１に示す。
【００９３】
次に、長さ16ビットを有する下記の情報語Mがプロセッサから出力されたものとして、これを符号化してメインメモリへ書き込む符号語を生成する手順を示す。
M=(1101001001100111)
上記情報語を、図２０に示すエントロピー変換部を用いて長さ60ビットを有する下記の列ベクトルmを生成する。
m=(000000000000100010000000000000000001000000000000000100000000)T
【００９４】
図３１に示す行列Aを用いて符号語cを以下のように生成する。
c=A・m
=(1101111011000010010011)T
符号語cを求めるための回路は、図１２に示す回路の考え方に基づいて容易に構成できる。ここで一般にcからmを求めることは困難であり、本発明が暗号化機能を有していることがわかる。
【００９５】
以下では、メインメモリに保持された上記符号語cを復号する手順を、図３２に示す流れに従って述べる。ここで、符号語cの第2ビットに誤りが発生し、復号回路は下記の語を受信したとする。
c’=(1001111011000010010011)T
【００９６】
ベクトルc’の左から置換行列Qを乗じ以下のベクトルc”を得る。
C”=(0101101011100011100011)T
【００９７】
ベクトルc’に置換行列Qを乗じる回路は、図１４に示す回路の考え方に基づいて容易に構成できる。続いて、ベクトルc”を受信語として符号Ccの復号を行う。ここで、符号Ccは奇数重み列SEC-DED符号であるから、復号回路は図１５に示す回路の構成法に基づいて実現できる。なお、奇数重み列SEC-DED符号の復号回路は、例えば、非特許文献「E. Fujiwara, Code Design for Dependable Systems, Wiley, 2006」に詳しく述べられている。復号結果の情報部は長さ16ビットを有する下記の列ベクトルで与えられる。
u1=(0101101011100011)T
【００９８】
列ベクトルu1の左から正則行列Dを乗じ、下記の列ベクトルvを得る。
v =(0111101110101111)T
【００９９】
この演算回路は図１６に示す回路と同様の考え方で構成できる。次に、検査行列Hsを用いて以下の式を満たす長さ60ビットを有する列ベクトルwを求める。
2008242034.tif 000044
【０１００】
ここで、
2008242034.tif 000045
とおくと、すべての
2008242034.tif 000046
について
2008242034.tif 000047
のHamming重みは高々1である。また、検査行列Hsは図２４に示すように、符号長15ビット、検査長4ビットを有する1ビット誤り訂正Hamming符号の検査行列Hs(i)を部分行列として有する。よって、図３３に示すように検査行列Hs(i)に対する誤りパターン生成回路を4個用いることにより、ベクトルvからベクトルwを計算する回路を構成できる。なお、ここではベクトルvがシンドロームに対応し、ベクトルwが誤りパターンに対応する。検査行列Hs(0)が例えば下記の行列として与えられる場合、ベクトル(v0,v1,v2,v3)からベクトル
2008242034.tif 000048
を求めるための、誤りパターン生成回路の例を図３４に示す。
2008242034.tif 000049
【０１０１】
上記の回路により、長さ60ビットを有する以下のベクトルwを得る。
w = (000000000000100000000100000000010000000000000000001000000000)T
【０１０２】
ベクトルwの左からブロック置換行列Tを乗じ下記のベクトルm’を得る。
m’=(000000000000100010000000000000000001000000000000000100000000)T
【０１０３】
この演算回路は図１８に示す回路と同様に構成できる。以上により本発明による復号処理は終了する。最後にベクトルm’を図２０及び図２１に示すエントロピー変換部へ入力し、下記のベクトルM’を得る。
M’=(1101001001100111)T
上記の例より、M=M’となることが確認できる。
【０１０４】
以下では、図３５に示すように、本発明による符号化・復号装置を、計算機システムにおいてプロセッサとメインメモリを接続するメモリ・IOコントローラ部に組み込む例を簡単に示す。プロセッサのキャッシュラインサイズを考慮して、長さ128バイト(1024ビット)を有するデータに対して、暗号化及び通信路符号化を適用する例を示す。なお、以下は低密度ランダム系列発生器、ランダム系列発生器及びハッシュ関数回路を用いることにより、暗号の安全性を強化している例である。前述の実施例とは異なり、図３５に示す装置おいては、本発明の符号化・復号装置をデータの符号化・復号に直接用いるのではなく、暗号化に用いる低密度ランダム系列を情報源符号化及び暗号化するために本発明の符号化・復号装置を用いている。
【０１０５】
符号化は図３６に示す装置により、長さ1024ビットを有するベクトルとして表される情報語ｍから長さ1136ビットを有する符号語ｃを生成することにより行う。図３６に示す符号化装置の各機能ブロックにおける処理について以下に述べる。
【０１０６】
図３６の低密度ランダム系列発生器は、長さ200ビット、Hamming重み10以下を有するランダムベクトルを発生するための回路である。低密度ランダム系列発生器の構成例を図３７に示す。低密度ランダム系列発生器は、10個の乱数発生器を用いて、長さ200ビットを有するベクトルの中で値を1とするビットの位置を決定することにより、Hamming重み10以下を有するランダムベクトルｘを生成する。なお、1個の乱数発生器から10回乱数を発生させることによっても、前記の機能を実現できる。
【０１０７】
図３６のランダム系列発生器は長さ200ビットの入力ｘを種(seed)として長さ1024ビットを有する擬似乱数系列ｅを生成する回路である。
【０１０８】
図３６のEX-OR回路はGF(2)上でのベクトルの加算を示す。また、ハッシュ関数回路は、長さ1024ビットを有するベクトルｐを入力として、長さ80ビットを有するベクトルｈをハッシュ値として出力する回路である。
【０１０９】
図３６の統合符号化回路は本発明で開示する手法により圧縮及び暗号化を行う回路である。符号化のための行列Ａの構成例を以下に示す。なお、行列Ａの生成は符号設計時に一回だけ行うものであり、符号化処理のたびに再計算する必要はない。符号長255ビットを有する10ビット誤り訂正BCH符号の検査行列からランダムに55列ベクトルを削除して構成した行列をＨSとする。行列ＨSは80行200列を有する行列である。行列ＧCを80行80列を有する単位行列とする。行列Ｑを80行80列を有するランダム置換行列とする。行列Ｄを80行80列を有するランダムな正則行列とする。行列Ｔを200行200列を有する置換行列とする。符号化のための行列Ａは以下の式により定める。
2008242034.tif 000050
ここで、Ａは80行200列を有する行列である。図３６の統合符号化回路は、前記行列Ａを用いて、長さ200ビットを有する列ベクトルｘから、長さ80ビットを有する列ベクトル
2008242034.tif 000051
を生成する機能を有する。
【０１１０】
図３６の誤り制御符号化回路は、符号長1136ビット、情報長1104ビット、検査長32ビットを有するＧＦ（２8）上の2シンボル誤り訂正Reed-Solomon符号の符号化回路である。誤り制御符号化回路は長さ1104ビットを有する列ベクトルｑを符号化して、長さ1136ビットを有する符号語ｃ＝ＧTｑへ変換する。ただし、Ｇは前記2シンボル誤り訂正Reed-Solomon符号の生成行列である。
【０１１１】
前記符号化装置で生成した符号語ｃに通信路誤りが発生した語を受信語ｃ’＝ｃ＋ｎとする。長さ1136ビットを有する受信語ｃ’を復号するための復号装置を図３８に示す。図３８に示す復号装置の各機能ブロックにおける処理について以下に述べる。
【０１１２】
図３８の誤り制御符号復号回路は、符号長1136ビット、情報長1104ビット、検査長32ビットを有する前記ＧＦ（２8）上の2シンボル誤り訂正Reed-Solomon符号の復号回路である。復号回路は長さ1136ビットを有する受信語ｃ’を入力して一般的な手順で誤り訂正処理を行い、復号結果を長さ1104ビットを有するベクトルｑ’として出力する。
【０１１３】
図３８のEX-OR回路はGF(2)上でのベクトルの加算を示す。また、図３８のハッシュ関数回路は、図３６に示すハッシュ関数回路と同一の回路であり、長さ1024ビットを有するベクトルｐ’を入力として、長さ80ビットを有するベクトルｈ’を出力する回路である。ここで、ｐ’はベクトルｑ’の後半1024ビットである。
【０１１４】
図３８の統合復号回路は、本発明で開示する復号処理を行う回路であり、長さ80ビットを有するベクトルｙ’を入力し、長さ200ビットを有するベクトルｘ’を出力する。ここで、ｘ’のHamming重みは10以下となる。この統合復号回路の構成を図３９に示す。図３９の置換回路Qは、入力ベクトルｘ’に置換を施しベクトルｕ＝Ｑ・ｘ’を生成する。次に、積算回路Dは、式ｖ＝Ｄ・ｕの関係によりベクトルｖを生成する。図３９のBCH符号復号回路は、入力ベクトルｖをシンドロームとして、長さ200ビットを有する誤りパターンｗを生成する回路である。すなわち、BCH符号復号回路は、ｖ＝ＨS・ｗを満足するHamming重み10以下のベクトルｗを求める機能を有する。この機能は、従来のBCH符号の復号回路と同様に、誤り位置多項式を生成し、この多項式の根を求める回路を備えることにより実現できる。ベクトルｗは置換回路Tにより置換され、ベクトルｘ’＝Ｔ・ｗを得る。
【０１１５】
図３８のランダム系列発生器は図３６に示すランダム系列発生器と同一のものであり、長さ200ビットの入力ｘ’を種(seed)として長さ1024ビットを有する擬似乱数系列ｅ’を生成する回路である。
【０１１６】
前記復号装置により、受信語ｃ’から復号語ｍ’が得られる。ここで、受信語ｃ’に存在する誤りが2バイト以下の誤りである場合、復号語ｍ’は情報語ｍと必ず一致する。ただし、バイトとはReed-Solomon符号の1シンボルに対応する長さ8ビットを有するベクトルである。
【０１１７】
前記符号化装置及び復号装置を用いることにより、プロセッサから出力される長さ128バイトを有するキャッシュラインを暗号化できると同時に、符号語ｃに生じたランダム2バイト以下の誤りを訂正することが可能となる。
【０１１８】
以上述べたように、本発明によれば、従来、複雑な処理を必要としていた情報源符号化処理、暗号化処理及び通信路符号化処理の各処理を、行列演算を主体として統合的に処理することが可能となり、従来技術と比較して特に符号化演算処理量を格段に減らすことができる。すなわち、本発明によれば、線形誤り制御符号の符号化処理と同等の演算処理量で、情報源符号化、暗号化及び通信路符号化処理を統合的に処理することができ、従来技術と比較して符号化処理回路または符号化処理プログラムを大幅に簡略化することが可能となる。また、本発明による復号装置においては、誤り制御符号の復号処理と同等のスループットで、暗号の復号処理及び圧縮データ伸長処理を行うことが可能である。
【０１１９】
また、既に述べたように、本発明によれば、性能の高い線形符号を用いれば非常に効率の良いデータ伝送が可能となる。すなわち、Shannon限界に漸近する最適な線形符号が存在すると仮定すると、本発明における符号Cs及びCcとして、この最適な符号を用いることにより、Shannon限界に漸近するデータ伝送が可能である。現在のところShannon限界に十分に漸近する線形符号は知られていないが、例えばirregular LDPC符号を用いることにより、十分に効率の良いデータ伝送が可能である。このように、本発明においては符号Cs及びCcとして、情報源及び通信路の特性を考慮して任意の線形符号を用いることができ、上記非正則行列Aの設計において非常に高い柔軟性を有することが重要な特徴のひとつである。さらに、本発明で開示する復号方法によれば、情報源の特性を利用して通信路誤り訂正を行うこと(joint source-channel decoding)も可能となり、通信路誤りに対する耐性の強い符号化方式を実現することができる。
【０１２０】
さらに、本発明によれば、RSA暗号等の従来の一般的な公開鍵暗号方式よりも格段に少ない演算量を有する公開鍵暗号方式を実現できる。すなわち、従来の公開鍵暗号方式は一般に複雑な算術演算を必要としているのに対し、本発明で提供する公開鍵暗号機能は行列演算を主体とした処理のみで実現されることから、本発明における公開鍵暗号方式は従来のような共通鍵の交換のみでなく高速なデータ伝送にも十分使用することができる。また、本暗号化方式の安全性は、大きな行列の因数分解問題及びランダム線形符号の復号問題に基づいていることから、本発明により、高い安全性を有する公開鍵暗号方式を提供することができる。
【０１２１】
さらに、本発明によれば、高いスループットで情報源符号化処理、暗号化処理及び通信路符号処理を行えることから、従来、これらの技術を十分に活用できなかった計算機システムの内部、例えばプロセッサの周辺回路等においてもデータの圧縮、暗号化処理及び誤り制御符号化処理が可能となり、計算機システムの性能、安全性及び信頼性を大幅に向上させることができる。
【０１２２】
本発明は、上述の実施形態に限定されるものではなく、広く情報通信分野において利用可能である。すなわち、近年の情報通信システムにおいては、データを圧縮して効率的に伝送すること、情報を盗聴されないように安全に伝送すること、かつ情報を誤りなく正確に伝送することは、広く一般的に要求されている。本発明は、これらの目的を同時かつ効率的に達成するものであり、産業界における応用範囲は極めて広い。
【０１２３】
例えば、携帯電話機を用いた情報通信システムでは、小型携帯端末において、音声・画像情報等の圧縮処理、暗号化処理及び無線通信に適した強力な誤り制御符号化処理が必要であり、本発明によりこれらの処理を効率的に実現することができる。また、センサネットワーク、監視カメラシステム、インターネットを用いたデータ伝送、等においても同様に、圧縮処理、暗号化処理及び誤り制御符号化処理が必要であり、本発明の利用価値は高い。近年、自律動作可能な複数のディスク装置をネットワークに接続し、ストレージネットワークを構築するシステム等が知られているが（例えば、特許文献「特開２００６−３３０７７９号公報」を参照）、このようなシステム等においては、記憶領域を効率的に利用するために圧縮処理が必要であり、また、ネットワークに接続することから暗号化処理が必要である。さらに、ディスク装置の障害に備えて誤り制御符号化処理が必要である。それゆえ、かかるストレージネットワークの分野に対しても本発明を適用することができる。
【０１２４】
さらに、本発明は広く計算機システムに対しても適用可能である。すなわち、図４０に示したようなプロセッサ、インタフェース回路等において本発明にかかる符号化・復号回路を組み込むことにより、計算機システム内のメモリ及びデータバス上のデータの全てを効率よく符号化することができる。これにより、計算機内部データのソフトエラーに対する耐性が高まるとともに、暗号化による安全性の向上及び圧縮による処理効率の向上を図ることができる。特に、本発明により計算機内部の情報をハードウェアにより暗号化できることから、機密情報や著作物扱うシステムにおける安全性をソフトウェアに頼らずに大きく高めることができる。
【図面の簡単な説明】
【０１２５】
【図１】従来の情報伝送処理手順の例を示した図である。
【図２】本発明の一実施形態における圧縮処理と暗号化処理と誤り制御符号化処理とを処理する情報伝送処理手順を説明する説明図である。
【図３】本発明にかかる計算機システムの例を説明する説明図である。
【図４】本発明の一実施形態における符号化及び復号処理手順を説明する説明図である。
【図５】本発明の一実施形態における符号化装置への入力情報である２元ベクトルmの生成例を説明する説明図である。
【図６】本発明の一実施形態における符号化装置の入力情報に対するエントロピー変換の例を説明する説明図である。
【図７】本発明の一実施形態における符号化装置の符号化及び復号に用いる行列の構成方法を説明する説明図である。
【図８】本発明の一実施形態における符号化装置で要求される機能に応じた行列Q,Gc,D,Hs及びTの選択方法を説明する説明図である。
【図９】本発明の一実施形態における情報源符号化処理機能と暗号化処理機能と通信路符号化処理機能とを有する符号化処理手順を説明する説明図である。
【図１０】本発明の一実施形態における復号処理手順を説明する説明図である。
【図１１】本発明の一実施形態における３層のTannerグラフを用いた復号方法を説明する説明図である。
【図１２】本発明の一実施形態における符号化回路の構成例を説明する説明図である。
【図１３】本発明の一実施形態における復号回路のブロック図である。
【図１４】本発明の一実施形態における復号に用いる置換回路Qの例を説明する説明図である。
【図１５】本発明の一実施形態におけるHamming符号Ccに対する復号回路の例を説明する説明図である。
【図１６】本発明の一実施形態における正則行列Dとベクトルu1の積を計算するための回路の例を説明する説明図である。
【図１７】本発明の一実施形態におけるブロック符号ＣS（ｖ）＝｛ｃ｜ＨSｃ＝ｖ｝の符号語の中からHamming重み0または1を有する語を検索するための回路の例を説明する説明図である。
【図１８】本発明の一実施形態における復号に用いる置換回路Tの例を説明する説明図である。
【図１９】本発明の一実施形態におけるメインメモリ（主記憶装置）の暗号化及び誤り制御符号化のための回路の例を説明する説明図である。
【図２０】本発明の一実施形態におけるエントロピー変換部のブロック図である。
【図２１】本発明の一実施形態におけるエントロピー変換部の回路構成を説明する説明図である。
【図２２】本発明の一実施形態のメインメモリにおける検査行列Hcの例を説明する説明図ある。
【図２３】本発明の一実施形態における生成行列Gcの転置行列ＧCTの例を説明する説明図である。
【図２４】本発明の一実施形態における行列Hsの構成方法を説明する説明図である。
【図２５】本発明の一実施形態における行列Hsの例を説明する説明図である。
【図２６】本発明の一実施形態における置換行列Qとその逆行列Q-1の例を説明する説明図である。
【図２７】本発明の一実施形態における正則行列Dとその逆行列D-1の例を説明する説明図である。
【図２８】本発明の一実施形態におけるブロック置換行列Tの構成法を説明する説明図である。
【図２９】本発明の一実施形態におけるブロック置換行列Tによるベクトル要素の置換の例を説明する説明図である。
【図３０】本発明の一実施形態におけるブロック置換行列Tとその逆行列T-1の例を説明する説明図である。
【図３１】本発明の一実施形態における符号化のための行列Aの例を説明する説明図である。
【図３２】本発明にかかる計算機システムのメインメモリにおける符号化手順の例を説明する説明図である。
【図３３】本発明の一実施形態における検査行列Hsを用いたベクトル伸長回路の例を説明する説明図ある。
【図３４】本発明の一実施形態におけるブロック符号｛ｃ｜ＨS・ｃ＝ｖ｝の復号のための誤りパターン生成回路の例を説明する説明図である。
【図３５】本発明の一実施形態における符号化装置及び復号装置をメモリ・ＩＯコントローラに組み込む例を説明する説明図である。
【図３６】本発明の一実施形態におけるキャッシュラインデータ用符号化装置の例を説明する説明図である。
【図３７】本発明の一実施形態における符号化装置のための低密度ランダム系列発生器の構成例を説明する説明図である。
【図３８】本発明の一実施形態におけるキャッシュラインデータ用復号装置の例を説明する説明図である。
【図３９】本発明の一実施形態における復号装置のための統合復号回路を説明する説明図である。
【図４０】本発明にかかる計算機及び通信システムの例を説明する説明図である。
【図３】
2008242034.tif 000054
【図４】
2008242034.tif 000055
【図５】
2008242034.tif 000056
【図６】
2008242034.tif 000057
【図７】
2008242034.tif 000058
【図８】
2008242034.tif 000059
【図９】
2008242034.tif 000060
【図１２】
2008242034.tif 000061
【図１３】
2008242034.tif 000062
【図１４】
2008242034.tif 000063
【図１５】
2008242034.tif 000064
【図１６】
2008242034.tif 000065
【図１７】
2008242034.tif 000066
【図１８】
2008242034.tif 000067
【図１９】
2008242034.tif 000068
【図２１】
2008242034.tif 000069
【図２２】
2008242034.tif 000070
【図２３】
2008242034.tif 000071
【図２４】
2008242034.tif 000072
【図２５】
2008242034.tif 000073
【図２６】
2008242034.tif 000074
【図２７】
2008242034.tif 000075
【図２８】
2008242034.tif 000076
【図２９】
2008242034.tif 000077
【図３０】
2008242034.tif 000078
【図３１】
2008242034.tif 000079
【図３２】
2008242034.tif 000080
【図３３】
2008242034.tif 000081
【図３４】
2008242034.tif 000082
【図３５】
2008242034.tif 000083
【図３７】
2008242034.tif 000084
【図３９】
2008242034.tif 000085
【図４０】
2008242034.tif 000086
【図１】
2008242034.tif 000087
【図２】
2008242034.tif 000088
【図１０】
2008242034.tif 000089
【図１１】
2008242034.tif 000090
【図２０】
2008242034.tif 000091
【図３６】
2008242034.tif 000092
【図３８】
2008242034.tif 000093