JP4074252B2 - 復号および誤り訂正方法 - Google Patents

Description

本発明は保護された符号ワードに適用可能な復号および誤り訂正方法に関する。

本発明はまた、保護された符号ワードを訂正され復号されたワードに変換可能な復号および誤り訂正回路に関する。

メモリ、特にＥＥＰＲＯＭまたはFLASH ＥＥＰＲＯＭ型の電気的に消去およびプログラム可能なメモリにデータを書き込むためにデータ機密化（securisation）／訂正装置が広く使用されている。データはメモリに保存される際に機密化ビットが追加されて保護され、機密化ビットにより読み出される際に訂正される。

さらに、古典的には、特定のレベルの秘密性が必要とされる場合、データがメモリに保存される前にデータを符号化し、メモリが読み出される際にこれらのデータを復号してきた。「符号化」とは、バイナリワードをスクランブル関数（scrambling function）により符号化して符号ワードを得ることを意味する。

したがって、初期データから「保護された符号化データエントリ」、すなわち、符号化処理と機密化処理の２回の処理を経たバイナリワードを得るため、符号化関数と機密化関数（security function）を一つの装置に組み合わせることが必要になることがしばしばある。

本発明は、一般的には、符号化／復号関数をデータ機密化／訂正装置に統合することに関し、特に、ハミングアルゴリズムに基づいた装置、データ符号化／復号化および機密化／訂正装置を得ることに関する。

図１には、従来のデータ機密化／訂正装置ＥＣＣ１のブロック図が示されている。この装置ＥＣＣ１は、データ機密化回路ＷＲ１とデータ訂正回路ＲＤ１とから構成されている。回路ＷＲ１は、バイナリワードＸ１を受け取る１つの入力部ＩＮ１と、保護された符号ワードＸ２を送り出す１つの出力部ＯＵＴ１とを有している。回路ＲＤ１は、誤りＥを含む保護されたワードＸ３を受け取る１つの入力部ＩＮ２と、訂正されたワードＸ４を送り出す１つの出力部ＯＵＴ２とを有している。

回路ＷＲ１は、関数ＧをワードＸ１に行い、保護されたワードＸ２を送り出すブロックＢ１から構成される。関数Ｇは、（２^Ｋ）行（２^Ｋ＋Ｊ）列の行列で表すことができる機密化ビット生成関数である。バイナリワードＸ１を２^Ｋビットのベクトルで表すことにより、こうして得られた保護されたワードＸ２は以下の関係式で表されることになる。
X2 = X1*G = DATA(X2)//CODE(X2)
ここで「*」は行列の積であり、「//」は連接の記号であり、「DATA(X2)」は２^Ｋ個のデータビットらなるワードＸ２の第一の部分であり、「CODE(X2)」はＪ個の機密化ビットからなるワードＸ２の第二の部分を意味する。

関数Ｇは、初期ワードＸ１のデータビットを変更しないため、ワードDATA(X2)は、初期ワードＸ１のデータビットと同様のデータビットを有する。したがって、以下のように表すことができる。
X2 = X1//CODE(X2)

一例として、８ビットのワードでただ１つのビットを、ハミングアルゴリズムにより検出して訂正することを仮定する。このアルゴリズムによると、機密化ビットの数ＪはＫ＋１と等しく、２^Ｋビットのワードの１つの誤りビットのみを検出して訂正する。したがって、この例では、Ｋ＝３、Ｊ＝Ｋ＋１＝４で、ワードＸ１、Ｘ２は付録の項目１に記載のように書かれる。関数Ｇは、（２^Ｋ）行（２^Ｋ＋Ｋ＋１）列の行列、すなわち、ここでは付録の項目２に記載の８行１２列の行列となる。行列Ｇは、付録の項目３に記載のように、４つの機密化ビットｐ０、ｐ１、ｐ２、ｐ３、またはパリティビットを生成する。

次に、保護されたワードＸ２がメモリＭＥＭに保存され、そのメモリから読み出されることを仮定する。書き込まれてから、読み出されるまでの間に、ワードは変化して、誤りを有することがある。統計的に、ＥＥＰＲＯＭまたはFLASH ＥＥＰＲＯＭ型の電気的に消去およびプログラム可能なメモリでは、そのような誤りが発生することが多々ある。それは、一般的に、メモリセルの浮遊ゲートトランジスタに影響を与える不良（例えば、そのしきい値電圧の変動など）、ビットラインまたはワードラインの接続不良、などに起因する。

誤りがないと考えられる、初期の保護されたワードＸ２から読み出されるワードと区別するため、メモリから読み出されるワードをＸ３と呼び、ワードＸ２と誤りＥの合計と等しいとみなす。
X3 = X2 + E
「＋」は、先に合計を実行しない、ビット同士の加算であり、Ｅは、ワードＸ２に影響を与える誤りを表す２^Ｋ＋Ｊビットのワードである。ここで誤りはゼロの可能性もある。

Ｘ３と誤りＥは以下のように表すことができる。
X3 = DATA(X3)//CODE(X3)

E = ERR1//ERR2
DATA(X3)は、２^Ｋのデータビットからなるワード、CODE(X3)は、Ｊ個の機密化ビットからなるワード、ＥＲＲ１は、誤りＥの２^Ｋ個の第一の部分のビットからなる、データビットの誤りを表すワード、ＥＲＲ２は、続くＪ個の誤りＥのビットからなる、機密化ビットの誤りを表すワードを意味する。この結果、以下のようになる。
DATA(X3) = DATA(X2) + ERR1 = X1 + ERR1

CODE(X3) = CODE(X2) + ERR2
「＋」は、先に合計を実行しない、ビット同士の加算を意味する。

理解を容易にするため、上述の例（２^Ｋ＝８、Ｊ＝４）を使用すると、ワードＥ、ＥＲＲ１、ＥＲＲ２、DATA(X2)、DATA(X3)は、付録の項目４に記載のようになる。

（ゼロの可能性もある）誤りＥを含むワードＸ３の訂正が、誤り訂正ブロックＢ２、シンドローム生成ブロックＢ３、誤りベクター生成ブロックＢ４を備えた回路ＲＤ１で実行される。

ブロックＢ２は、それぞれが２^Ｋビットの２つの入力部Ｅ１、Ｅ２と、２^Ｋビットの一つの出力部を有している。入力部Ｅ１は、ワードＸ３のデータビット、すなわち、ワードDATA(X3)を受け取る。入力部Ｅ２は、ブロックＢ４から送られる誤りベクターＥＶを受け取る。ブロックＢ２は、初期ワードＸ１と等しい訂正されたワードＸ４を送り出す（誤りのビット数が、検出され訂正されることのできる最大ビット数以下とした場合）。

ワードＸ４は、ワードDATA(X3)とベクトルＥＶを論理的に連結することにより得られる。一般的に、この論理的な連結は排他的論理和関数（ｘor関数、記号Θ）により実行される。

ブロックＢ３はワードＸ３を入力側から受け取り、関数ＨをワードＸ３に実行し、以下のようなシンドロームＳＹＮを送り出す。ここで、関数Ｇおよび関数Ｈは直交関数で、その積Ｇ＊Ｈは０である。
SYN = X3*H
すなわち: SYN = (X2 + E)*H
すなわち: SYN = (X1*G + E)*H
すなわち: SYN = X1*G*H + E*H
すなわち: SYN = E*H

ハミングアルゴリズムで、関数Ｈは、Ｇと直交する（２^Ｋ＋Ｋ＋１）行（Ｋ＋１）列の行列である。理解を容易にするため、Ｋ＝３でＪ＝４の場合の行列Ｈを付録の項目５に記載した。この行列Ｈは、ワードごとに１つの誤りを検出し、訂正することができるＳ０、Ｓ１、Ｓ２、Ｓ３の４ビットのシンドロームＳＹＮを生成する。ビットＳ０からビットＳ４の論理値もまた、付録の項目６に記載している。

シンドロームＳＹＮは、シンドローム／ベクター変換関数EV = f(SYN)を実行し、適当なベクターＥＶを送り出すブロックＢ４に送られる。このシンドローム／ベクター変換関数は、所定の対応表に従う。理解を容易にするため、Ｋ＝３でＪ＝４の場合のシンドローム／ベクター対応表を付録の項目７に記載した。

理論的には、各誤差ベクターＥＶは一部ＥＶ１と一部ＥＶ２を有し、以下のように記すことができる。
EV = EV1//EV2
ＥＶ１は、データの誤りを表す２^Ｋビットの誤りベクターであり、ＥＶ２は、機密化ビットの誤りを表すＪビットの誤りベクターである。実際には機密化ビットの誤り訂正は不要であるため、ブロックＢ４からは誤りベクターＥＶ１のみが送り出され、ブロックＢ２の入力部Ｅ２に入力される。

ブロックＢ２が排他的論理和関数を実行する場合、誤りベクターＥＶは、誤りＥ自体と等しくなることに注意する。
DATA(X3) ΘEV1 = X1
しかしながら、
DATA(X3) ΘEV1 = X1 + ERR1 ΘEV1
これにより、
ERR1ΘEV1 = 0
すなわち、
ERR1 = EV1
「+」は、先に合計を実行しない、ビット同士の加算であり、「Θ」は、排他的論理和関数である。

図２は、さらに符号化復号化手段を備え、データ符号化／復号化および機密化／訂正装置を構成する、装置ＥＣＣ１とは異なる装置ＥＣＣ２を示している。

装置ＥＣＣ２は、データ符号化および機密化回路ＷＲ２とデータ復号化および訂正回路ＲＤ２とから構成されている。回路ＷＲ２は、バイナリワードＸ０を受け取る１つの入力部ＩＮ１と、保護された符号ワードＸ２を送り出す１つの出力部ＯＵＴ１とを有している。回路ＲＤ２は、（ゼロの可能性もある）誤りＥを含む保護された符号ワードＸ３を受け取る１つの入力部ＩＮ２と、訂正された復号化ワードＸ５を送り出す１つの出力部ＯＵＴ２とを有している。

回路ＷＲ２は、直列に接続された１つのブロックＢ０と上述のブロックＢ１を有している。ブロックＢ０は入力部で入力としてワードＸ０を受け取り、符号化関数「Ａ」をワードＸ０に実行して、符号ワードＸ１をブロックＢ１の入力部に送り出す。ブロックＢ１はワードＸ１に上述の関数Ｇを実行し、ワードＸ２を回路ＷＲ２の出力部ＯＵＴ１に送り出す。

２^Ｋ行２^Ｋ列の行列で、Ｋ＝３の場合の符号化関数Ａの一例を付録の項目８に記載する。

ワードＸ２はメモリＭＥＭに保存され、メモリから続けて読み出されるワードをＸ３とすると、Ｘ３は、誤りＥが付加されたワードＸ２と等しい。

誤りＥの訂正およびワードＸ３の復号が回路ＲＤ２により実行される。回路ＲＤ２は、復号化ブロックＢ５がブロックＢ２の出力側と出力部ＯＵＴ２の間に配置されている点で装置ＥＣＣ１の回路ＲＤ１とは異なる。ブロックＢ５は、関数Ａの逆関数である復号化関数Ａ^−１をその入力部で受け取ったデータに実行する。

復号化関数Ａ^−１が付録の項目８に記載した行列Ａの逆行列であるとした、復号化関数Ａ^−１の一例を、付録の項目９に記載する。

したがって、装置ＥＣＣ２の動作は以下の通りである。
− ブロックＢ０が初期ワードＸ０から符号ワードＸ１を生成する。
− ブロックＢ１が符号ワードＸ１から保護された符号ワードＸ２を生成する。
− ブロックＢ２が、保護された符号ワードＸ３に誤り訂正を実行し、訂正された符号ワードＸ４を送り出す。
− ブロックＢ５が、訂正された符号ワードＸ４の復号化を実行し、訂正され復号化されたワードＸ５を送り出す。

ブロックＢ１、Ｂ３、およびＢ４は、装置ＥＣＣ１のそれらと同様であり、ワードＸ１が符号ワードであることは、このワードの機密化および訂正に影響を与えない。

上述の回路ＥＣＣ１およびＥＣＣ２は、従来、配線論理ブロックとして製造された。ワードＸ１をワードＸ２に変換（機密化）する時間、およびワードＸ３をワードＸ４に変換（訂正）する時間は、入力部ＩＮ１と出力部ＯＵＴ１の間、および入力部ＩＮ２と出力部ＯＵＴ２の間のデータバスに沿って存在する論理ゲートのデータ伝搬時間により直接的に変化する。

装置ＥＣＣ２は、ブロックＢ０とブロックＢ５をデータパスに沿って追加したために、データ転送処理が遅くなるという課題がある。ブロックＢ０とブロックＢ５は、ブロックＢ１からＢ４と同様に、論理ゲートを使用して製造されており、所定のデータ転送時間を要する。事実、ブロックＢ０とブロックＢ５を追加することにより、装置ＥＣＣ２の入力部と出力部の間のデータ転送時間が、装置ＥＣＣ１と比較して、３０％から５０％増加した。

本発明は、この問題を解決することを目的としている。

より詳細には、本発明の目的は、データ処理時間を加速することができる復号および誤り訂正方法を提供することにある。

本発明の第一の対応する目的は、上述の従来の回路よりもデータ転送時間の短い復号および誤り訂正回路を提供することにある。

本発明のもう一つの目的は、上述の従来の回路よりもデータ転送時間の短い符号化および機密化回路を提供することにある。

この目的のため、本発明は、誤り訂正ステップと、前記誤り訂正ステップの前に実行され、復号化関数（Ａ ^−１ ）を保護された符号ワードに適用して、符号化された誤りを有する保護された復号化ワードを得る復号化ステップと、前記復号化ステップと同時に実行される前記符号化された誤りベクターを決定するステップとを有することを特徴とする、初期の保護された符号ワードに対して誤りを有する可能性のある保護された符号ワードに適用可能な復号および誤り訂正方法を提供する。

一つの実施の形態によれば、前記誤り訂正ステップは、符号化された誤りベクターを保護された復号化ワードに適用するステップを有する。

一つの実施の形態によれば、前記符号化された誤りベクターを決定するステップは、保護された符号ワードが復号化される前に訂正される場合、保護された符号ワードに適用することのできる符号化されていない誤りベクターを前記復号化関数により変換するステップを有する。

一つの実施の形態によれば、前記誤りベクターを決定するステップは、シンドローム算出関数を前記保護された符号ワードに適用することによりシンドロームを決定するステップと、シンドロームと符号化された誤りベクターとの直接対応表により、前記シンドロームから前記符号化された誤りベクターを直接生成するステップとを有する。

一つの実施の形態によれば、前記初期の保護された符号ワードは、符号化関数により、初期ワードを符号ワードに変換し、機密化関数により前記符号ワードを変換することにより得られる。

一つの実施の形態によれば、前記初期の保護された符号ワードは、初期ワードに、符号化関数と機密化関数を組み合わせた結果である符号化および機密化関数を適用することにより得られる。

一つの実施の形態によれば、本方法は、配線論理回路により実施される。

さらに、本発明は、復号および誤り訂正回路に関し、前記復号および誤り訂正回路において、保護された符号ワードを受け取る１つの入力部と、訂正された復号化ワードを送り出す１つの出力部とを有したデータパスと、前記データパスに沿って配置され、入力部を有し、復号化関数を前記入力部にあるワードに適用する復号化ブロックと、前記データパスに沿って配置され、訂正するワードを受け取る第一入力部と、誤りベクターを受け取る第二入力部とを有する誤り訂正ブロックと、前記データパスの前記入力部に接続した１つの入力部を有するシンドローム決定ブロックと、前記シンドローム決定ブロックの１つの出力部に接続した１つの入力部と前記誤り訂正ブロックの前記第二入力部に接続した１つの出力部を有する符号化された誤りベクターを決定する手段とを備え、前記復号化ブロックが、前記誤り訂正ブロックの上流の前記データパス上に配置され、前記誤り訂正ブロックの前記第一入力部に、符号化された誤りを有する保護された復号化ワードを送り出すことを特徴とする。

一つの実施の形態によれば、前記符号化された誤りベクターを決定する手段は、シンドロームから、前記シンドロームに対応する符号化されていない誤りベクターを前記復号化関数により変換したものと等しい、符号化された誤りベクターを送り出す。

一つの実施の形態によれば、前記符号化された誤りベクターを決定する手段は、シンドロームと符号化された誤りベクターとの直接対応表により変換を実行する１つのブロックを有する。

一つの実施の形態によれば、前記復号化ブロック、前記誤り訂正ブロック、前記シンドローム決定ブロック、および前記符号化された誤りベクターを決定する手段は、配線論理回路である。

さらに、本発明は、データ符号化／復号化および機密化／訂正装置に関し、前記データ符号化／復号化および機密化／訂正装置は、保護された符号ワードを訂正された復号化ワードに変換する、本発明に係る復号および誤り訂正回路と、初期ワードを保護された符号ワードに変換する符号化および機密化回路とを備えたことを特徴とする。

一つの実施の形態によれば、前記符号化および機密化回路は、符号化関数を初期ワードに適用し、機密化関数を符号ワードに適用する手段を備える。

一つの実施の形態によれば、前記符号化および機密化回路は、前記符号化関数と前記機密化関数の組み合わせを初期ワードに適用するように配置された１つの符号化および機密化ブロックを備える。

図３は、本発明に係るデータ符号化／復号化および機密化／訂正装置ＥＣＣ３を表している。装置ＥＣＣ３は、データ符号化および機密化回路ＷＲ３とデータ復号化および訂正回路ＲＤ３を備えている。回路ＷＲ３は、バイナリワードＸ０を受け取る１つの入力部ＩＮ１と、保護された符号ワードＸ２を送り出す１つの出力部ＯＵＴ１とを有している。回路ＲＤ３は、（ゼロの可能性もある）誤りＥを含む保護されたワードＸ３を受け取る１つの入力部ＩＮ２と、訂正され復号化されたワードＸ５を送り出す１つの出力部ＯＵＴ２とを有している。

本発明によると、回路ＷＲ３は、符号化および機密化関数Ａ＊ＧをワードＸ０に実行し、保護された符号ワードＸ２を出力部ＯＵＴ１に送り出すブロックＢ１’を有している。関数Ａ＊Ｇは、従来の符号化関数Ａと従来の機密化関数Ｇの積である。

一例として、８ビットのワードでただ１つのビットを、ハミングアルゴリズムにより検出して訂正することを仮定する。ここで、すでに前段で説明したパラメータＫおよびＪについては３および４に等しいとする。この場合、関数Ｇは、付録の項目２に記載の８行１２列の行列となる。関数Ａは、例えば、付録の項目８に記載の８行８列とする。本発明に係る対応する関数Ａ＊Ｇは、この場合、付録の項目１０に記載のＡとＧの行列積となる。

一般的に、ブロックＢ１’のデータの移動時間は、前段で説明した従来のブロックＢ０またはブロックＢ１の一つのデータの移動時間とほぼ等しい。したがって、ワードＸ０から保護された符号ワードＸ２への変換時間は、本発明では半分と大幅に短縮される。

ワードＸ２はメモリＭＥＭに保存され、メモリから続けて読み出されるワードをＸ３とすると、Ｘ３は、誤りＥが付加されたワードＸ２と等しい。誤りＥの訂正およびワードＸ３の復号化は回路ＲＤ３により実行される。

回路ＲＤ３は、誤り訂正ブロックＢ２、シンドローム生成ブロックＢ３、誤りベクターＥＶ’生成ブロックＢ４’、および復号化ブロックＢ５を有している。ブロックＢ２、Ｂ３、Ｂ５は、前段で説明した従来の回路ＥＣＣ２の対応するブロックと同一である。ブロックＢ４’は、以下の種の誤りベクターＥＶ’の有用な部分を形成する、データの誤りに対応する２^Ｋビットの誤りベクターＥＶ１’を送り出す。
EV' = EV1'//EV2'
ここで、EV2'は、機密化符号の誤りに対応するＪビットの誤りベクターである。EV2'は実際には使用されない。

本発明によると、入力部で受け取ったデータに復号化関数数Ａ^−１を実行する復号化ブロックＢ５は、回路ＲＤ３の入力部ＩＮ２と対応するブロックＢ２の入力部Ｅ１の間に配設されている。換言すると、ブロックＢ２はその入力部Ｅ１で訂正されていない復号化データを受け取る。上述の説明から理解できるように、回路ＲＤ３の入力部ＩＮ２に送られるワードＸ３は、以下のように記すことができる。
X3 = X2 + E
すなわち:
X3 = X0*A*G + E
「＋」は、先に合計を実行しない、ビット同士の加算であり、Ｅは、ワードＸ２に影響を与える誤りを表す２^Ｋ＋Ｊビットのワードである。

ワードＸ３と誤りＥは以下の式で表すことができる。
X3 = DATA(X3)//CODE(X3)
E = ERR1//ERR2
DATA(X3)は、ワードＸ３の２^Ｋ個のデータビットからなるワード、CODE(X3)は、ワードＸ３のＪ個の機密化ビットからなるワード、ＥＲＲ１は、誤りＥの２^Ｋ個の第一の部分のビットからなるワード、ＥＲＲ２は、続くＪ個の誤りのビットからなるワードである。

この結果、以下のようになる。
DATA(X3) = DATA(X2) + ERR1 = (DATA(X0)*A*G) + ERR1
CODE(X3) = CODE(X2) + ERR2
ワードDATA(X3)は、機密化ビットCODE(X3)なしに、ブロックＢ５の入力部に入力される。したがって、ブロックＢ５から出力されるＸ４’は以下のようになる。
X4' = DATA(X3)*A^-1 = (X0*A*G*A^-1) + ERR1*A^-1
ＡとＡ^−１は逆関数の関係にあるため、結果は、以下のようになる。
X4' = (X0*G) + ERR1*A^-1
機密化関数Ｇはデータビットを変えることはないため、結果は以下のようになる。
X4' = X0 + ERR1*A^-1

したがって、訂正回路Ｂ２の入力部に送られるワードＸ４’は、前の実施の例のように保護された符号ワードではなく、符号化された誤りを有する復号化ワードである。復号化ワードは、ワードＸ０で、符号化された誤りはＥＲＲ１＊Ａ^-1、すなわち、復号化関数Ａ^-1により誤りＥＲＲ１を変換したものとなる（逆関数Ａにより符号化されていない要素に適用すると、復号化関数Ａ^-1は符号化関数に相当する）。

符号化された誤りＥＲＲ１＊Ａ^-1を訂正するためにブロックＢ２の入力部Ｅ２に入力する必要のある誤りベクターＥＶ１’が次に決定される。

ワードＸ３がシンドローム生成ブロックＨ全体に適用されるため、結果は以下のようになる。

SYN = X3*H
すなわち:
SYN = (X2 + E)*H
すなわち:
SYN = (X1*A*G + E)*H
すなわち:
SYN = X1*A*G*H + E*H

関数Ｈと関数Ｇの積はゼロであるため、シンドロームＳＹＮは以下のようになる。
SYN = E*H
この結果、ブロックＢ３により生成されるシンドロームは、前段で説明した装置ＥＣＣ１および装置ＥＣＣ２により生成されるシンドロームと同一となる。

さらに、従来の誤りベクターＥＶ１は符号化されていない誤りＥＲＲ１と同一で、誤りベクターＥＶ１’は、従来の誤りベクターＥＶ１から以下のように表すことができる。
EV1' = ERR1*A^-1 = EV1*A^-1

したがって、本発明に係る誤りベクターＥＶ１は、関数Ａ^-1により従来の誤りベクターＥＶ１を変換したものと等しくなる。

したがって、実施の例では、ブロックＢ４’は、従来のブロックＢ４と関数Ａ^-1を実行するブロックとを直列に配列することにより生成することできる。本発明によると、何よりも、各シンドローム値に対してベクターＥＶ１’を与える、直接対応表を決定することが好ましい。直接対応表の各ベクターＥＶ１’は、
関数Ａ^−１を、従来の対応表により与えられるベクターＥＶ１に適用することにより算出することができる。次に、直接対応表により与えられる変換関数を実行することにより配線論理ブロックＢ４’が生成される。

理解を容易にするため、本発明に係る対応表を付録の項目１１に記載する。この対応表（表２）は、逆関数Ａ^−１を、項目７に記載の対応表（表１）のベクターＥＶに適用して得ることができる。

装置ＥＣＣ３の動作は以下の通りである。
− ブロックＢ１’が初期ワードＸ０から保護された符号ワードＸ２を生成する。
− ブロックＢ５が、保護された符号ワードＸ３の復号化を実行して、符号化された誤りＥＲＲ１＊Ａ^-1を含む訂正されていない復号化されたワードＸ４’を送り出す。
− ブロックＢ２が、符号化された誤りベクターＥＶ１の手段により符号化された誤りと同様の方法で、すなわち関数Ａ^-1を従来の誤りベクターＥＶ１に適用することにより、符号化された誤りの訂正を実行する。
− 好ましくは、ブロックＢ４’は、シンドロームＳＹＮから直接誤りベクターＥＶ１’を送り出す。

本発明に係る復号化および訂正回路ＲＤ３は、ブロックＢ３とブロックＢ４’によりシンドロームと誤りベクターＥＶ１’を決定している間、同時に、ブロックＢ５によりワードＸ３の復号化を実行するという並列構成の利点を有している。したがって、復号化ブロックＢ５が訂正ブロックの後段に配置された従来の回路ＥＣＣ２の場合の復号化動作によりデータ転送時間が遅くなるということは発生しない。

理解を容易にするため、付録に記載された関数Ａ、Ｇ、Ｈを使用した本発明に係る復号化および訂正方法を実施する例について説明する。

ここで、以下に示すワードＸ１がメモリＭＥＭに書き込まれ、読み出されるものとする。
X1 = 1 1 0 0 1 0 1 1
関数Ａ＊Ｇの手段（ブロックＢ１’）によりワードＸ０が符号化され、保護された後、以下が得られる。
X2 = 0 1 0 0 0 0 1 1 0 1 0 1
Ｘ３はメモリＭＥＭに書き込まれ、ワードが再び読み出される。
X3 = X2 + E
以下の誤りＥが発生すると仮定する。
E = 0 0 0 1 0 0 0 0 0 0 0 0
したがって、読みだされたワードＸ３は以下のようになる。
X2 = 0 1 0 0 0 0 1 1 0 1 0 1
+ E = 0 0 0 1 0 0 0 0 0 0 0 0
= X3 = 0 1 0 10 0 1 1 0 1 0 1
関数Ｈの手段（ブロックＢ３）により、対応するシンドロームＳＹＮが算出される。
X3*H = 0 1 1 0
付録の項目１１の表２の手段（ブロックＢ４’）により、符号化された誤りベクターＥＶ１’が導き出される。
EV1' = 1 0 0 1 1 1 0 1
シンドロームと誤りベクターが決定されている間、同時に、訂正されていない復号化されたワードＸ４’が関数Ａ^-1の手段（ブロック５）により決定される。
X4' = (DATA(X2) + ERR1)*A^-1 = 0 1 0 1 0 1 1 0
こうしてワードが訂正される。
X5 = X4' xor EV1'
X5 = 0 1 0 1 0 1 1 0 xor 1 0 0 1 1 1 0 1
すなわち:
X5 = 1 1 0 0 1 0 1 1
すなわち:
X5 = X1

本発明に係るデータ符号化／復号化および機密化／訂正装置は、当業者には様々な実施の形態および応用が可能であることは明かである。特に、応用として、メモリを備えた複数の集積回路において、本発明に係る装置をメモリの入力部と出力部の間に挿入することもできる。特に、これらはスマートカード、マイクロコントローラ、・・・、EPROM、EEPROM、FLASH EEPROM、メモリなどの統合メモリ、などの集積回路である。もう一つの応用の例として、回線による障害または送信問題による誤りが発生することがあるため、受信したデータを復号化および訂正するため、符号化および機密化回路ＷＲ３をデータ送信回線の一方の端部に配置し、復号化および訂正回路ＲＤ３を回線の他方の端部に配置することもできる。

明細書と一体の付録

項目１．ワードＸ１とワードＸ２
X1 = x0 x1 x2 x3 x4 x5 x6 x7
X2 = DATA(X2)//CODE(X2)
すなわち:
X2 = x0 x1 x2 x3 x4 x5 x6 x7 p0 p1 p2 p3
ここで
DATA(X2) = X1 = x0 x1 x2 x3 x4 x5 x6 x7
CODE(X2) = p0 p1 p2 p3
p0、p1、p3、P4は機密化ビット。

項目２．１つの誤りビットのみを訂正する場合で、Ｋ＝３、Ｊ＝４とした時にハミングアルゴリズムにより機密化ビットを生成する行列

項目３．行列Ｇにより生成される機密化ビット
p0 = x0 xor x1 xor x2 xor x5
p1 = x2 xor x3 xor x4 xor x7 xor x1
p2 = x4 xor x5 xor x6 xor x1 xor x3
p3 = x6 xor x7 xor x0 xor x2 xor x3
「xor」は排他的論理和（EXCLUSIVE OR）関数

項目４．ワードE, ERR1, ERR2, X3, DATA(X3), CODE(X3)
E = ERR1//ERR2 = e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11
すなわち:
ERR1 = e0 e1 e2 e3 e4 e5 e6 e7
ERR2 = e8 e9 e10 e11
***
X3 = X2 + E = (x0 + e0) (x1 + e1) (x2 + e2) (x3 + e3) (x4 + e4) (x5 + e5) (x6 + e6) (x7 + e7) (p0 + e8) (p1 + e9) (p2 + e10) (p3 + e11)
すなわち:
DATA(X3) = (x0 + e0) (x1 + e1) (x2 + e2) (x3 + e3) (x4 + e4) (x5 + e5) (x6 + e6) (x7 + e7)
CODE(X3) = (p0 + e8) (p1 + e9) (p2 + e10) (p3 + e11)

項目５．Ｋ＝３、Ｊ＝４とした時のハミング行列Ｈ

項目６．Ｋ＝３、Ｊ＝４とした時に行列Ｈにより生成されるシンドロームＳＹＮの値
SYN = S0 S1 S2 S3
S0 = x0 xor x1 xor x2 xor x5 xor p0
S1 = x2 xor x3 xor x4 xor x7 xor x1 xor p1
S2 = x4 xor x5 xor x6 xor x3 xor x1 xor p2
S3 = x6 xor x7 xor x3 xor x2 xor x0 xor p3

項目７．Ｋ＝３、Ｊ＝４とした時の従来の対応表の例

項目８．Ｋ＝３とした時の符号化関数Ａの例

項目９．Ｋ＝３とした時の復号化関数Ａ^-1の例

項目１０．Ｋ＝３とした時の符号化および機密化関数A*Gの例

項目１１．Ｋ＝３、Ｊ＝４とした時の本発明に係る対応表の例

従来のデータ符号化／復号化および機密化／訂正装置の図である。 従来の符号化および機密化回路と従来の副合かおよび訂正回路を備えた従来のデータ符号化／復号化および機密化／訂正装置の図である。 本発明に係る符号化および機密化回路と本発明に係る復号化および訂正回路を備えた本発明に係るデータ符号化／復号化および機密化／訂正装置の図である。

Claims (14)

1. 誤り訂正ステップと、
   前記誤り訂正ステップの前に実行され、復号化関数（Ａ ^−１ ）を保護された符号ワード（Ｘ３）に適用して、符号化された誤り（Ｅ＊Ａ ^−１ ）を有する保護された復号化ワード（Ｘ４’）を得る復号化ステップと、
   前記復号化ステップと同時に実行される前記符号化された誤りベクター（ＥＶ１’）を決定するステップとを有することを特徴とする、初期の保護された符号ワード（Ｘ２）に対して誤りを有する可能性のある保護された符号ワード（Ｘ３）に適用可能な復号および誤り訂正方法。
2. 前記誤り訂正ステップが、符号化された誤りベクター（ＥＶ１’）を保護された復号化ワード（Ｘ４’）に適用するステップを有することを特徴とする請求項１に記載の方法。
3. 前記符号化された誤りベクター（ＥＶ１’）を決定するステップは、保護された符号ワードが復号化される前に訂正される場合、保護された符号ワード（Ｘ３）に適用することのできる符号化されていない誤りベクター（ＥＶ１）を前記復号化関数（Ａ ^−１ ）により変換するステップを有することを特徴とする請求項２に記載の方法。
4. 前記誤りベクターを決定するステップは、
   シンドローム算出関数（Ｈ）を前記保護された符号ワード（Ｘ３）に適用することによりシンドロームを決定するステップと、
   シンドロームと符号化された誤りベクターとの直接対応表により、前記シンドロームから前記符号化された誤りベクター（ＥＶ１’）を直接生成するステップとを有することを特徴とする請求項３に記載の方法。
5. 前記初期の保護された符号ワード（Ｘ２）は、
   符号化関数（Ａ）により、初期ワード（Ｘ０）を符号ワード（Ｘ１）に変換し、機密化関数（Ｇ）により前記符号ワード（Ｘ１）を変換することにより得られることを特徴とする請求項１から請求項４までの何れか一項に記載の方法。
6. 前記初期の保護された符号ワード（Ｘ２）は、
   初期ワード（Ｘ０）に、符号化関数（Ａ）と機密化関数（Ｇ）を組み合わせた（Ａ＊Ｇ）結果である符号化および機密化関数を適用することにより得られることを特徴とする請求項１から請求項４までの何れか一項に記載の方法。
7. 配線論理回路により実施されることを特徴とする請求項１から請求項６までの何れか一項に記載の方法。
8. 復号および誤り訂正回路（ＲＤ３）において、
   保護された符号ワード（Ｘ３）を受け取る１つの入力部（ＩＮ２）と、訂正された復号化ワード（Ｘ５）を送り出す１つの出力部（ＯＵＴ２）とを有したデータパスと、
   前記データパスに沿って配置され、入力部を有し、復号化関数（Ａ ^−１ ）を前記入力部にあるワードに適用する復号化ブロック（Ｂ５）と、
   前記データパスに沿って配置され、訂正するワードを受け取る第一入力部（Ｅ１）と、誤りベクター（ＥＶ１’）を受け取る第二入力部（Ｅ２）とを有する誤り訂正ブロック（Ｂ２）と、
   前記データパスの前記入力部（ＩＮ２）に接続した１つの入力部を有するシンドローム（ＳＹＮ）決定ブロック（Ｂ３）と、
   前記シンドローム決定ブロック（Ｂ３）の１つの出力部に接続した１つの入力部と前記誤り訂正ブロック（Ｂ２）の前記第二入力部（Ｅ２）に接続した１つの出力部を有する符号化された誤りベクター（ＥＶ１’）を決定する手段（Ｂ４’）とを備え、
   前記復号化ブロック（Ｂ５）が、前記誤り訂正ブロック（Ｂ２）の上流の前記データパス上に配置され、前記誤り訂正ブロックの前記第一入力部（Ｅ１）に、符号化された誤り（Ｅ＊Ａ ^−１ ）を有する保護された復号化ワード（Ｘ４’）を送り出すことを特徴とする復号および誤り訂正回路（ＲＤ３）。
9. 前記符号化された誤りベクター（ＥＶ１’）を決定する手段（Ｂ４’）は 、シンドローム（ＳＹＮ）から、前記シンドロームに対応する符号化されていない誤りベクター（ＥＶ１）を前記復号化関数（Ａ−１）により変換したものと等しい、符号化された誤りベクター（ＥＶ１’）を送り出すことを特徴とする請求項８に記載の回路。
10. 前記符号化された誤りベクターを決定する手段は、シンドロームと符号化された誤りベクターとの直接対応表により変換を実行する１つのブロック（Ｂ４’）を有することを特徴とする請求項９に記載の回路。
11. 前記復号化ブロック、前記誤り訂正ブロック、前記シンドローム決定ブロック、および前記符号化された誤りベクターを決定する手段は、配線論理回路であることを特徴とする請求項８から請求項１０の何れか一項に記載の回路。
12. データ符号化／復号化および機密化／訂正装置（ＥＣＣ３）において、
    保護された符号ワード（Ｘ３）を訂正された復号化ワード（Ｘ５）に変換する、請求項８から請求項１１までの何れか一項に記載の復号および誤り訂正回路（ＲＤ３）と、
    初期ワード（Ｘ０）を保護された符号ワード（Ｘ２）に変換する符号化および機密化回路（ＷＲ３）と、を備えたことを特徴とするデータ符号化／復号化および機密化／訂正装置（ＥＣＣ３）。
13. 前記符号化および機密化回路（ＷＲ３）が、符号化関数（Ａ）を初期ワード（Ｘ０）に適用し、機密化関数（Ｇ）を符号ワードに適用する手段（Ｂ１’）を備えたことを特徴とする請求項１２に記載の装置。
14. 前記符号化および機密化回路（ＷＲ３）が、
    前記符号化関数（Ａ）と前記機密化関数（Ｇ）の組み合わせ（Ａ＊Ｇ）を初期ワード（Ｘ０）に適用するように配置された１つの符号化および機密化ブロック（Ｂ１’）を備えたことを特徴とする請求項１３に記載の装置。

Images