(57)【特許請求の範囲】
【請求項１】
処理ユニットと、
メモリとを備える装置であって、
前記処理ユニットが、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成し、
前記処理ユニットが、前記符号化ビットの部分集合に応じて、前記符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するように構成され、前記部分集合が、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、
前記符号化ビットの部分集合が反転されるべきでないことを前記反転指定が示すときには、前記処理ユニットが、記憶ワードとして、前記第１のコードワードのビットを前記メモリに記憶するように構成され、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含み、
前記符号化ビットの部分集合が反転されるべきであることを前記反転指定が示すときには、前記処理ユニットが、ビット値を変更することによって前記符号化ビットの部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得するように構成され、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するように構成され、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有し、
前記メモリに書込み値を書き込んだ後、次いで前記書込み値を前記メモリから読み出して読出し値を取得した後、さらに、前記書き込まれた書込み値と前記読み出された書込み値とを比較した後に、誤りが生じていないとき、前記処理ユニットが、前記符号化ビットの前記部分集合が反転されるべきでないことを示す前記反転指定を特定するように構成される
装置。
【請求項２】
処理ユニットと、
メモリとを備える装置であって、
前記処理ユニットが、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成し、
前記処理ユニットが、前記符号化ビットの部分集合に応じて、前記符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するように構成され、前記部分集合が、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、
前記符号化ビットの部分集合が反転されるべきでないことを前記反転指定が示すときには、前記処理ユニットが、記憶ワードとして、前記第１のコードワードのビットを前記メモリに記憶するように構成され、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含み、
前記符号化ビットの部分集合が反転されるべきであることを前記反転指定が示すときには、前記処理ユニットが、ビット値を変更することによって前記符号化ビットの部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得するように構成され、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するように構成され、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有し、
前記メモリに書込み値を書き込んだ後、次いで前記書込み値を前記メモリから読み出して読出し値を取得し、さらに、前記書き込まれた書込み値と前記読み出された書込み値とを比較した後に、せいぜいＴ個の誤りが生じているとき、前記処理ユニットが、前記符号化ビットの前記部分集合が反転されるべきでないことを示す前記反転指定を特定するように構成され、ここで、Ｔは、前記線形誤り訂正符号によって訂正することができる誤りの数よりも小さい、
装置。
【請求項３】
処理ユニットと、
メモリとを備える装置であって、
前記処理ユニットが、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成し、
前記処理ユニットが、前記符号化ビットの部分集合に応じて、前記符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するように構成され、前記部分集合が、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、
前記符号化ビットの部分集合が反転されるべきでないことを前記反転指定が示すときには、前記処理ユニットが、記憶ワードとして、前記第１のコードワードのビットを前記メモリに記憶するように構成され、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含み、
前記符号化ビットの部分集合が反転されるべきであることを前記反転指定が示すときには、前記処理ユニットが、ビット値を変更することによって前記符号化ビットの部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得するように構成され、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するように構成され、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有し、
ビットの部分集合の反転されている書込み値を前記メモリに書き込んだ後、次いで前記書き込まれた反転されている書込み値を前記メモリから読み出して読出し値を取得した後、さらに、前記書き込まれた反転されている書込み値と前記読み出された反転されている書込み値とを比較した後に、直接書き込み、前記読出し値と前記書き込まれた反転されていない値とを比較した後に生じるのとせいぜい同数の誤りが生じているとき、前記処理ユニットが、前記符号化ビットの前記部分集合が反転されるべきであることを示す前記反転指定を特定するように構成される、
装置。
【請求項４】
処理ユニットと、
メモリとを備える装置であって、
前記処理ユニットが、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成し、
前記処理ユニットが、前記符号化ビットの部分集合に応じて、前記符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するように構成され、前記部分集合が、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、
前記符号化ビットの部分集合が反転されるべきでないことを前記反転指定が示すときには、前記処理ユニットが、記憶ワードとして、前記第１のコードワードのビットを前記メモリに記憶するように構成され、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含み、
前記符号化ビットの部分集合が反転されるべきであることを前記反転指定が示すときには、前記処理ユニットが、ビット値を変更することによって前記符号化ビットの部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得するように構成され、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するように構成され、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有し、
ビットの部分集合の反転された書込み値を前記メモリに書き込み、次いで前記書き込まれた反転されている書込み値を前記メモリから読み出して、読み出された反転されている書込み値を取得し、さらに、前記書き込まれた反転されている書込み値と前記読み出された値とを比較した後に、せいぜいＴ個の誤りが生じている場合、前記処理ユニットが、前記符号化ビットの前記部分集合が反転されるべきであることを示す前記反転指定を特定するように構成され、ここで、Ｔは、前記線形誤り訂正符号によって訂正することができる誤りの数よりも小さい、
装置。
【請求項５】
回路である請求項１から４のいずれか一項に記載の装置。
【請求項６】
前記符号化ビットの前記部分集合が、前記複数の符号化ビットのうちの全ての符号化ビットを含む請求項１から４のいずれか一項に記載の装置。
【請求項７】
前記符号化ビットの前記部分集合が、前記複数の符号化ビットのうちの全ての符号化ビットは含まない請求項１から４のいずれか一項に記載の装置。
【請求項８】
前記第１の所定の値が、第１の定数２進値ｂｆであり、
前記第２の所定の値が、第２の定数２進値
【数１】
0005923631.tif 000276
であり、
前記処理ユニットが、前記記憶ワードを前記メモリから読み出すように構成され、前記処理ユニットが、前記記憶ワードを読み出した後、前記指示ビットが記憶されている前記メモリ内のビット位置から読み出されているビット値が前記第２の定数２進値
【数２】
0005923631.tif 000277
であるときには、前記メモリに直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、前記指示ビットが記憶されている前記メモリ内の前記ビット位置から読み出されているビット値が前記第１の定数２進値ｂｆであるときには反転しないように構成される
請求項１から４のいずれか一項に記載の装置。
【請求項９】
前記第１の所定の値が、第１の定数２進値ｂｆであり、
前記第２の所定の値が、第２の定数２進値
【数３】
0005923631.tif 000278
であり、
前記処理ユニットが、前記記憶ワードを前記メモリから読み出すように構成され、前記処理ユニットが、前記記憶ワードの１つまたは複数のビットが誤りである場合に、前記誤り訂正符号を使用することによって前記１つまたは複数のビットを訂正するように構成され、少なくとも前記指示ビットが書き込まれている前記ビット位置に記憶されているビットが、前記ビットが誤りである場合に訂正され、
前記記憶ワードを読み出し、前記１つまたは複数のビットを訂正した後に、前記処理ユニットが、前記指示ビットが記憶されている前記メモリ内のビット位置から読み出されているビット値が前記第２の定数２進値
【数４】
0005923631.tif 000279
であるときには、前記メモリに直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、前記指示ビットが記憶されている前記メモリ内の前記ビット位置から読み出されている前記ビット値が前記第１の定数２進値ｂｆであるときには反転しないように構成される
請求項１から４のいずれか一項に記載の装置。
【請求項１０】
前記線形誤り訂正符号が、パリティチェック行列Ｈを含み、前記パリティチェック行列Ｈの行の各成分の１の数が偶数である請求項９に記載の装置。
【請求項１１】
前記メモリが、レジスタ、レジスタアレイ、またはアドレス可能なメモリである請求項１から４のいずれか一項に記載の装置。
【請求項１２】
前記メモリが、アドレス可能なメモリであり、前記処理ユニットが、前記線形誤り訂正符号を採用することによって、かつアドレスビットを使用することによって、前記複数のビットを符号化して前記複数の符号化ビットを取得するように構成される請求項１から４のいずれか一項に記載の装置。
【請求項１３】
前記メモリが、Ｆｌａｓｈメモリ、磁気ランダムアクセスメモリ（Ｍ−ＲＡＭ）、または抵抗性ランダムアクセスメモリ（Ｒ−ＲＡＭ）である請求項１から４のいずれか一項に記載の装置。
【請求項１４】
前記線形誤り訂正符号が、生成行列を含み、
前記処理ユニットが、符号化のためにその系統的形態での前記生成行列を使用することによって、前記複数のビットを符号化するように構成される
請求項１から４のいずれか一項に記載の装置。
【請求項１５】
前記線形誤り訂正符号が、ハミング符号もしくは短縮ハミング符号であり、または
前記線形誤り訂正符号が、Ｈｓｉａｏ符号もしくは短縮Ｈｓｉａｏ符号であり、または
前記線形誤り訂正符号が、ＢＣＨ符号もしくは短縮ＢＣＨ符号である
請求項１から４のいずれか一項に記載の装置。
【請求項１６】
エンコーダを使用して、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップであって、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成するステップと、
処理ユニットを使用して、前記符号化ビットの部分集合に応じて、前記符号化ビットの前記部分集合が反転されるべきか否かを示す反転指定を特定するステップであって、ここで、前記部分集合は、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきでないことを前記反転指定が示すときには、記憶ワードとして、前記第１のコードワードのビットをメモリに記憶するステップであって、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきであることを前記反転指定が示すときには、ビット値を変えることによって前記符号化ビットの前記部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得し、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するステップであって、ここで、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有する、ステップと
を含み、
前記反転指定を特定するステップは、前記メモリに書込み値を書き込んだ後、次いで前記書込み値を前記メモリから読み出して読出し値を取得した後、さらに、前記書き込まれた書込み値と前記読み出された書込み値とを比較した後に、誤りが生じていないとき、前記符号化ビットの前記部分集合が反転されるべきでないことを示す前記反転指定を特定するステップを含む、
方法。
【請求項１７】
エンコーダを使用して、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップであって、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成するステップと、
処理ユニットを使用して、前記符号化ビットの部分集合に応じて、前記符号化ビットの前記部分集合が反転されるべきか否かを示す反転指定を特定するステップであって、ここで、前記部分集合は、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきでないことを前記反転指定が示すときには、記憶ワードとして、前記第１のコードワードのビットをメモリに記憶するステップであって、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきであることを前記反転指定が示すときには、ビット値を変えることによって前記符号化ビットの前記部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得し、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するステップであって、ここで、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有する、ステップと
を含み、
前記反転指定を特定するステップは、前記メモリに書込み値を書き込んだ後、次いで前記書込み値を前記メモリから読み出して読出し値を取得し、さらに、前記書き込まれた書込み値と前記読み出された書込み値とを比較した後に、せいぜいＴ個の誤りが生じているとき、前記処理ユニットが、前記符号化ビットの前記部分集合が反転されるべきでないことを示す前記反転指定を特定するステップを含む、ここで、Ｔは、前記線形誤り訂正符号によって訂正することができる誤りの数よりも小さい、
方法。
【請求項１８】
エンコーダを使用して、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップであって、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成するステップと、
処理ユニットを使用して、前記符号化ビットの部分集合に応じて、前記符号化ビットの前記部分集合が反転されるべきか否かを示す反転指定を特定するステップであって、ここで、前記部分集合は、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきでないことを前記反転指定が示すときには、記憶ワードとして、前記第１のコードワードのビットをメモリに記憶するステップであって、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきであることを前記反転指定が示すときには、ビット値を変えることによって前記符号化ビットの前記部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得し、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するステップであって、ここで、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有する、ステップと
を含み、
前記反転指定を特定するステップは、ビットの部分集合の反転されている書込み値を前記メモリに書き込んだ後、次いで前記書き込まれた反転されている書込み値を前記メモリから読み出して読出し値を取得した後、さらに、前記書き込まれた反転されている書込み値と前記読み出された反転されている書込み値とを比較した後に、直接書き込み、前記読出し値と前記書き込まれた反転されていない値とを比較した後に生じるのとせいぜい同数の誤りが生じているとき、前記符号化ビットの前記部分集合が反転されるべきであることを示す前記反転指定を特定するステップを含む、
方法。
【請求項１９】
エンコーダを使用して、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップであって、前記複数の符号化ビットがそれぞれビット値を有し、前記線形誤り訂正符号が、少なくとも３の符号距離を有し、前記複数の符号化ビットが、前記線形誤り訂正符号の第１のコードワードを形成するステップと、
処理ユニットを使用して、前記符号化ビットの部分集合に応じて、前記符号化ビットの前記部分集合が反転されるべきか否かを示す反転指定を特定するステップであって、ここで、前記部分集合は、前記複数の符号化ビットのうちの少なくとも３つの符号化ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきでないことを前記反転指定が示すときには、記憶ワードとして、前記第１のコードワードのビットをメモリに記憶するステップであって、前記メモリに記憶される前記第１のコードワードの前記ビットが、第１の所定のビット値を有する指示ビットを含む、ステップと、
前記符号化ビットの前記部分集合が反転されるべきであることを前記反転指定が示すときには、ビット値を変えることによって前記符号化ビットの前記部分集合の各符号化ビットを反転させることによって、前記線形誤り訂正符号の前記第１のコードワードを修正して前記線形誤り訂正符号の第２のコードワードを取得し、前記記憶ワードとして、前記第２のコードワードのビットを前記メモリに記憶するステップであって、ここで、前記第２のコードワードの前記ビットが、反転された前記指示ビットを含み、それにより、前記指示ビットが、前記第１の所定のビット値とは異なる第２の所定のビット値を有する、ステップと
を含み、
前記反転指定を特定するステップは、ビットの部分集合の反転された書込み値を前記メモリに書き込み、次いで前記書き込まれた反転されている書込み値を前記メモリから読み出して、読み出された反転されている書込み値を取得し、さらに、前記書き込まれた反転されている書込み値と前記読み出された値とを比較した後に、せいぜいＴ個の誤りが生じている場合、前記処理ユニットが、前記符号化ビットの前記部分集合が反転されるべきであることを示す前記反転指定を特定するステップを含み、ここで、Ｔは、前記線形誤り訂正符号によって訂正することができる誤りの数よりも小さい、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ反転によってデータ記憶を改良するための装置および方法に関する。
【背景技術】
【０００２】
マルチビット訂正のための改良された概念を提供できれば非常に有益である。
【０００３】
メモリの信頼性を高めるとともに、新種のメモリでの電力消費を減少させることがますます重要となっている。
【０００４】
ＭＲＡＭ（磁気抵抗ランダムアクセスメモリ）、Ｒ−ＲＡＭ（抵抗性ランダムアクセスメモリ）など多くのタイプのメモリは、永久的な故障および誤りに関して非対称の挙動を示す。例えば、多くのメモリは、一般に、１縮退（ｓｔｕｃｋ−ａｔ−１）メモリ故障よりも多くの０縮退（ｓｔｕｃｋ−ａｔ−０）メモリ故障を示す。他のメモリは、一般に、０縮退メモリ故障よりも多くの１縮退メモリ故障を示す。
【０００５】
例えば、フラッシュメモリは、「１」または「０」を書き込むための電力消費に関して非対称である。すなわち、メモリに「１」が書き込まれるときと、メモリに「０」が書き込まれるときで、電力消費が異なる。Ｒ−ＲＡＭでは、誤りは単方向性であり、主に、１縮退誤りではなく０縮退誤りが生じる。ＭＲＡＭに関しても、主に、１縮退故障ではなく０縮退故障が生じる。
【０００６】
データ記憶のための改良された概念を提供できれば非常に有益である。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｌｉｎ，Ｓ．ａｎｄ  Ｃｏｓｔｅｌｌｏ，Ｄ．Ｅｒｒｏｒ  Ｃｏｎｔｒｏｌ  Ｃｏｄｉｎｇ，Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，１９８３，ｐａｇｅ  １４９
【発明の概要】
【課題を解決するための手段】
【０００８】
処理ユニットと、メモリとを備える装置が提供される。処理ユニットは、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、ここで、複数の符号化ビットはそれぞれビット値を有し、線形誤り訂正符号は、少なくとも３の符号距離を有し、複数の符号化ビットは、線形誤り訂正符号の第１のコードワードを形成する。さらに、処理ユニットは、符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定（inversion decision）を特定するように構成され、ここで、部分集合は、複数の符号化ビットのうちの少なくとも３つの符号化ビットを含む。符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、処理ユニットは、記憶ワードとして、第１のコードワードのビットをメモリに記憶するように構成され、ここで、メモリに記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含む。さらに、符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、処理ユニットは、ビット値を変更することによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得するように構成され、記憶ワードとして、第２のコードワードのビットをメモリに記憶するように構成され、ここで、第２のコードワードのビットは、反転された指示ビットを含み、それにより、指示ビットは、第１の所定のビット値とは異なる第２の所定のビット値を有する。
【０００９】
方法が提供される。この方法は、エンコーダを使用して、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップを含み、ここで、複数の符号化ビットはそれぞれビット値を有し、線形誤り訂正符号は、少なくとも３の符号距離を有し、複数の符号化ビットは、線形誤り訂正符号の第１のコードワードを形成し、方法はさらに、処理ユニットを使用して、符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するステップを含み、ここで、部分集合は、複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、方法はさらに、符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、記憶ワードとして、第１のコードワードのビットをメモリに記憶するステップを含み、ここで、メモリに記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含み、符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、ビット値を変えることによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得し、記憶ワードとして、第２のコードワードのビットをメモリに記憶するステップを含み、ここで、第２のコードワードのビットは、反転された指示ビットを含み、それにより、指示ビットは、第１の所定のビット値とは異なる第２の所定のビット値を有する。
【００１０】
処理ユニットと、メモリとを備える装置が提供される。処理ユニットは、複数のビットを符号化して複数の符号化ビットを取得するように構成され、さらに、処理ユニットは、反転指定を特定するように構成される。符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、処理ユニットは、記憶ワードとして、第１のコードワードのビットをメモリに記憶するように構成される。符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、処理ユニットは、符号化ビットの部分集合の各符号化ビットを反転させて第２のコードワードを取得し、第２のコードワードをメモリに記憶するように構成される。
【００１１】
装置が提供される。装置は、処理ユニットと、メモリとを備える。処理ユニットは、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、ここで、複数の符号化ビットはそれぞれビット値を有し、誤り訂正符号は、少なくとも３の符号距離を有し、複数の符号化ビットは、線形誤り訂正符号の第１のコードワードを形成する。さらに、処理ユニットは、符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するように構成され、ここで、符号化ビットの部分集合は、部分集合の全てのビットが反転される場合に誤り訂正符号の第１のコードワードがその符号の第２のコードワードに変換されるように決定され、部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含み、または複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、符号化ビットの部分集合のうちの１つの符号化ビットは、指示ビットであり、指示ビットのビット値は、第１の所定のビット値である。符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、処理ユニットは、記憶ワードとして、第１のコードワードのビットをメモリに記憶するように構成され、ここで、メモリに記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含む。符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、処理ユニットは、ビット値を変えることによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得するように構成され、さらに、記憶ワードとして、第２のコードワードをメモリに記憶するように構成され、ここで、第２のコードワードは、反転された指示ビットを含み、それにより、指示ビットのビット値は、第１の所定のビット値とは異なる第２の所定のビット値である。
【００１２】
さらに、別の実施形態が提供される。装置は、処理ユニットと、メモリとを備える。そのような別の実施形態では、処理ユニットは、アドレス可能なメモリにアドレスａで記憶されるペイロードデータビットｘ１，…，ｘｎを、定数値を有するｌ（ｌ≧１）個のビットｂｆ１，…，ｂｆｌによって補完するように構成される。
【００１３】
処理ユニットは、アドレスビットから導出されるビットがコードワードの形成に含まれないときには、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて、定数値を有するビットｂｆ１，…，ｂｆｌおよびペイロードデータビットｘ１，…，ｘｎをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎに符号化するように構成され、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎから決定されるチェックビットであり、さらに、処理ユニットは、アドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが符号化に含まれるときには、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて、ビットｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋにコード化するように構成され、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋから決定されるチェックビットであり、Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）は、アドレスビットから関数ｆ：｛０，１｝ｒ→｛０，１｝ｋによって決定される。
【００１４】
さらに、処理ユニットは、直接または反転されて記憶されるビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎのＫ（Ｋ≧１）個のビットグループＹ１，…，Ｙｋを定義するように構成され、それにより、所定のビットｂｆ１，…，ｂｆｌの部分集合が、これらのグループそれぞれに一意に割り振られる。
【００１５】
さらに、処理ユニットは、グループＹ１，…，Ｙｋのうちのどのビットグループが、反転されてまたは反転されずにメモリに記憶されるかを選択するように構成される。
【００１６】
処理ユニットは、メモリにアドレスａでビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎを書き込むように構成され、ここで、反転されてメモリに書き込まれるビットのグループに属するビットは、書込み前に反転され、反転されるビットを含むグループに属さないビットは、反転されずにメモリに書き込まれる。
【００１７】
さらに、処理ユニットは、メモリにアドレスａで記憶されているビットを読み出すように構成される。
【００１８】
アドレスビットから導出されるビットがコードワードの形成に含まれない場合には、処理ユニットは、同じアドレスに書き込まれた値とは誤りにより異なることがある、メモリから読み出されたビットを、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、誤り訂正符号Ｃに基づいて訂正するように構成される。
【００１９】
アドレスビットから導出されるビットがコードワードの形成に含まれる場合には、処理ユニットは、メモリから読み出された、誤りであり得る値を、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、誤り訂正符号Ｃに基づいて、誤りであり得るアドレスビットから導出されるやはり誤りであり得るビット
【数１】
0005923631.tif 000002
も使用することによって訂正するように構成される。
【００２０】
処理ユニットは、符号Ｃを使用することによって訂正され、それぞれのビットグループに一意に割り振られた読み出された定数値から、どのビットグループがメモリに直接または反転されて書き込まれているかを決定するように構成される。
【００２１】
処理ユニットは、前のステップでの書込みに際して反転したビットを含むビットグループと判断されるビットグループから読み出して訂正したビットを反転するように構成される。
【００２２】
一実施形態では、ｋ＝ｒ、および（Ａ１，…，Ａｋ）＝（ａ１，…，ａｒ）が成り立つ。
【００２３】
一実施形態によれば、ｋ＝１、Ａ１＝ｆ（ａ１，…，ａｒ）＝ａ１＋ａ２＋…＋ａｒが成り立ち、Ａ１は、アドレスビットａ１，…，ａｒのパリティである。
【００２４】
さらに、さらなる実施形態は、少なくとも１ビット誤りを訂正する線形符号Ｃのコードワードを形成するビットの部分集合をメモリセルのメモリに直接または反転させて書き込むため、および、メモリに書き込まれているビットを読み出し、直接または反転されて記憶されていた、メモリから誤り状態で読み出されていることがあるビットから、元のビットを回復するために提供される。装置は、処理ユニットと、メモリとを備える。
【００２５】
そのようなさらなる実施形態では、処理ユニットは、メモリに直接または反転させて書き込むことができる、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて符号化されたビットの部分集合の数Ｋ（Ｋ≧１）を定義するように構成される。
【００２６】
処理ユニットは、アドレスａ＝ａ１，…，ａｒ（ｒ≧２）で、少なくとも１ビット誤りを訂正する線形系統的符号のコードワードのサブワードとして記憶されるｎ個のペイロードデータビットｘ１，…，ｘｎを提供するように構成される。
【００２７】
処理ユニットは、符号Ｃの情報ビットｕ１，…，ｕＮを生成するように構成され、ここで、アドレスａが符号Ｃのコードワードの形成に含まれない場合には、データビットｘ１，…，ｘｎは、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、
ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
が成り立ち、ここで、Ｎ＝ｌ＋ｎであり、アドレスａが符号Ｃのコードワードの形成に含まれる場合には、データビットｘ１，…，ｘｎ、およびアドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、
ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋ
が成り立ち、ここで、Ｎ＝ｌ＋ｎ＋ｋであり、ここで、
Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）
は、ｒ個のアドレスビットａ１，…，ａｒの値から関数ｆによって一意に決定される２進値であり、ｌ≧１および１≦ｋ≦ｒであり、
ここで、アドレスビットが誤り検出および誤り訂正に含まれない場合には、処理ユニットは、符号Ｃのコードワードｙ１，…，ｙＰを生成するように構成され、ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、
ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
が成り立ち、ｃ１，…，ｃｍは、ｍ個のチェックビットであり、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、ｍ＝Ｐ−ＮおよびＮ＝ｎ＋ｌが成り立ち、
ここで、処理ユニットは、ビット
ｙ１，…，ｙＰ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
のＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するように構成され、
したがって、ビットｂｆ１，…，ｂｆｌの部分集合が、各部分集合Ｙ１，…，Ｙｋに一意に割り振られ、
したがって、
【数２】
0005923631.tif 000003
がビットｙ１，…，ｙＰの２進値である場合、ｋ＝１，…，Ｋおよびｊ＝１，…，Ｐに関して、ｙｊが部分集合Ｙｋの要素である場合には、
【数３】
0005923631.tif 000004
であり、ｙｊが部分集合Ｙｋの要素でない場合には、
【数４】
0005923631.tif 000005
であるとき、
【数５】
0005923631.tif 000006
は符号Ｃのコードワードであり、したがって、
【数６】
0005923631.tif 000007
が成り立ち、Ｈは、符号ＣのＨ行列であり、
ここで、処理ユニットは、ビットグループＹ１，…，Ｙｋのうちのどのグループがメモリに直接または反転されて書き込まれるかを定義するように構成され、
処理ユニットは、メモリに書き込まれるＰ個のビットｄ１，…，ｄＰを生成するように構成され、ここで、ｉ＝１，…，Ｐに関して、ｙｉが、反転されてメモリに書き込まれるビットを含むグループに属するときには、
【数７】
0005923631.tif 000008
であり、ｙｉが、反転されてメモリに書き込まれるビットを含むグループに属さないときには、ｄｉ＝ｙｉであり、
ここで、処理ユニットは、メモリにアドレスａでビットｄ１，…，ｄＰを書き込むように構成され、
ここで、処理ユニットは、アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数８】
0005923631.tif 000009
を読み出すように構成され、これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄＰから、生じ得る誤りに起因して生じており、
ここで、処理ユニットは、符号Ｃによって訂正すべきＬ個のビット位置ｋ１，…，ｋＬを定義するように構成され、ここで、ｌ≦Ｐおよび｛ｋ１，…，ｋＬ｝⊆｛１，…，Ｐ｝であり、これらのビット位置ｋ１，…，ｋＬは、値が誤りである場合には符号Ｃを使用することによって訂正され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属し、
ここで、処理ユニットは、符号Ｃによって訂正可能な誤りに関して、符号Ｃに基づいて訂正すべき所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数９】
0005923631.tif 000010
を決定するように構成され、
ここで、処理ユニットは、少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数１０】
0005923631.tif 000011
を生成するように構成され、ここで、ｏｐは、一意に可逆のブール演算であり、
ここで、処理ユニットは、既知の挿入された値ｂｆ１，…，ｂｆｌと、符号Ｃを使用することによって訂正されたそれぞれの読出し値とに基づいて、どのグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するように構成され、
ここで、処理ユニットは、
【数１１】
0005923631.tif 000012
が、メモリへの書込み中にメモリに直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数１２】
0005923631.tif 000013
を出力し、
【数１３】
0005923631.tif 000014
が、メモリへの書込み中にメモリに反転されて書き込まれているビットのグループに属する場合には、ビット
【数１４】
0005923631.tif 000015
を出力するように構成され、ここで、「ｏｐ」は、２項の一意に可逆のブール演算であり、
ここで、アドレスビットが誤り検出および誤り訂正に含まれる場合には、処理ユニットは、符号Ｃのコードワードｙ＝ｙ１，…，ｙＰを生成するように構成され、ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、
ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）・Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋ
が成り立ち、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、Ｐ＝ｎ＋ｌ＋ｍ＋ｋであり、ｃ１，…，ｃｍは、チェックビットであり、
ここで、処理ユニットは、ビット
ｙ１，…，ｙｎ＋ｌ，ｙｎ＋ｌ＋ｋ＋１，…，ｙＰ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
のＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するように構成され、
したがって、ビットｂｆ１，…，ｂｆｌの各ビットは、部分集合Ｙ１，…，ＹＫの１つのみに属し、したがって、
【数１５】
0005923631.tif 000016
がビットｙ１，…，ｙＰの２進値である場合、ｋ＝１，…，Ｋおよびｊ＝１，…，Ｐに関して、ｙｊが部分集合Ｙｋの要素である場合には、
【数１６】
0005923631.tif 000017
であり、ｙｊが部分集合Ｙｋの要素でない場合には、
【数１７】
0005923631.tif 000018
であるとき、
【数１８】
0005923631.tif 000019
は符号Ｃのコードワードであり、したがって、
【数１９】
0005923631.tif 000020
が成り立ち、Ｈは、符号ＣのＨ行列であり、
ここで、処理ユニットは、どのビットグループＹ１，…，Ｙｋがメモリに直接または反転されて書き込まれるかを定義するように構成され、
ここで、処理ユニットは、メモリに書き込まれるＰ−ｋ個のビットｄ１，…，ｄｍ＋ｌ＋ｎを生成するように構成され、ここで、ｉ＝１，…，ｍ＋ｎ＋ｌに関して、
ｙｉが、メモリに直接書き込まれるビットを含むグループに属するときには、ｄｉ＝ｙｉであり、
ｙｉが、メモリに反転されて書き込まれるビットを含むグループに属するときには、
【数２０】
0005923631.tif 000021
であり、
ここで、処理ユニットは、メモリにアドレスａでビットｄ１，…，ｄｍ＋ｎ＋ｌを書き込むように構成され、
ここで、処理ユニットは、アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数２１】
0005923631.tif 000022
を読み出すように構成され、これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄｎ＋ｌ、ｄｎ＋ｋ＋１，…，ｄＰから、生じ得る誤りに起因して生じており、
ここで、処理ユニットは、符号Ｃによって訂正すべきＬ個のビット位置ｋ１，…，ｋＬを定義するように構成され、ここで、ｌ≦Ｐ−ｋおよび｛ｋ１，…，ｋＬ｝⊆｛１，…，ｎ＋ｌ，ｎ＋ｌ＋ｋ＋１，…，Ｐ｝であり、これらのビット位置ｋ１，…，ｋＬは、値が誤りである場合には符号Ｃを使用することによって訂正され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属し、
ここで、処理ユニットは、符号Ｃによって訂正可能な誤りに関して、所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数２２】
0005923631.tif 000023
を決定するように構成され、
ここで、処理ユニットは、少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数２３】
0005923631.tif 000024
を生成するように構成され、ここで、「ｏｐ」は、２進の明瞭に可逆な演算であり、
ここで、処理ユニットは、既知の挿入された値ｂｆ１，…，ｂｆｌと、読み出され、符号Ｃを使用することによって訂正された対応する訂正値とに基づいて、どのビットグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するように構成され、
ここで、処理ユニットは、
【数２４】
0005923631.tif 000025
が、メモリへの書込み中にメモリに直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数２５】
0005923631.tif 000026
を出力し、
【数２６】
0005923631.tif 000027
が、メモリへの書込み中にメモリに反転されて書き込まれているビットのグループに属する場合には、ビット
【数２７】
0005923631.tif 000028
を出力するように構成され、ここで、「ｏｐ」は、２項の一意に可逆のブール演算である。
【００２８】
別の実施形態によれば、ビットをメモリに記憶するための装置が提供され、ここで、ビットは、線形誤り訂正符号Ｃを用いて符号化され、線形誤り訂正符号Ｃは、少なくとも３の符号距離を有し、線形誤り訂正符号Ｃを用いて符号化されたビットの部分集合がメモリに直接書き込まれるか、それともビット毎に反転されて書き込まれるかが判断され、符号Ｃは、Ｈ行列Ｈを備え、ここで、装置は、処理ユニットと、メモリとを備える。メモリに直接または反転されて書き込まれたビットの部分集合は、少なくとも１つの２進定数値を含み、この値は、ペイロードデータビットと共に、線形符号Ｃのコードワードを形成するためにコード化に使用される。処理ユニットは、それぞれのビット部分集合のビットがメモリに直接書き込まれるときに、２進定数値を２進値ｂｆとしてメモリに書き込むように構成される。処理ユニットは、それぞれのビット部分集合のビットがメモリに反転されて書き込まれるときに、２進定数値を反転値
【数２８】
0005923631.tif 000029
としてメモリに書き込むように構成される。
【００２９】
処理ユニットは、メモリに直接または反転されて書き込まれたビットの部分集合が反転されるときに、符号Ｃのコードワードを同じ符号のコードワードに変換するように構成され、符号のＨ行列は、メモリに直接または反転されて書き込まれたビットの部分集合に対応するＨ行列の行の各成分の「１」の数が偶数であるように生成される。
【００３０】
さらに、処理ユニットは、メモリからの読出し時に、メモリから読み出された、誤りであり得るビットを、線形誤り訂正符号Ｃを使用することによって訂正するように構成され、ここで、それぞれのビット部分集合がメモリに直接書き込まれているときには、少なくとも、定数２進値ｂｆが書き込まれているビット位置にあるビットが訂正され、または、それぞれのビット部分集合がメモリに反転されて書き込まれているときには、少なくとも、定数２進値
【数２９】
0005923631.tif 000030
が書き込まれているビット位置にあるビットが訂正される。
【００３１】
さらに、処理ユニットは、読出し後、定数値ｂｆまたは反転された定数値
【数３０】
0005923631.tif 000031
が記憶されているビット位置から読み出されている訂正された値が
【数３１】
0005923631.tif 000032
であるときには、メモリに直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、この値がｂｆであるときには反転しないように構成される。
【００３２】
別の実施形態によれば、方法が提供される。この方法は、以下のステップを含む。
【００３３】
線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップ。ここで、複数の符号化ビットがそれぞれビット値を有し、線形誤り訂正符号が、少なくとも３の符号距離を有し、複数の符号化ビットが、線形誤り訂正符号の第１のコードワードを形成する。
【００３４】
符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するステップ。ここで、符号化ビットの部分集合は、部分集合の全てのビットが反転される場合に誤り訂正符号の第１のコードワードがその符号の第２のコードワードに変換されるように決定され、部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含み、または複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、符号化ビットの部分集合のうちの１つの符号化ビットは、指示ビットであり、指示ビットのビット値は、第１の所定のビット値である。
【００３５】
符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、記憶ワードとして、第１のコードワードのビットをメモリに記憶するステップ。ここで、メモリに記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含む。
【００３６】
符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、ビット値を変えることによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得し、記憶ワードとして、第２のコードワードをメモリに記憶するステップ。ここで、第２のコードワードは、反転された指示ビットを含み、それにより、指示ビットのビット値は、第１の所定のビット値とは異なる第２の所定のビット値である。
【００３７】
いくつかの実施形態は、データ記憶に関してデータ反転を採用することができるという知見に基づく。いくつかの実施形態によれば、データ反転は、永久的な故障をマスクすることを可能にする。これは特に、メモリが比較的新しいときに誤り率が比較的高いときに有用である。
【００３８】
あるデータ位置で０縮退故障が生じる場合、この位置に記憶すべきビットが０である場合には誤りが生じない。しかし、記憶すべきビットが１である場合には誤りが生じる。記憶すべきビットが１である場合、反転されたデータに関しては、この位置に記憶すべきビットは０であり、したがって、ビットが反転されて記憶される場合には誤りが生じない。
【００３９】
いくつかの実施形態によれば、複数の縮退故障が存在する場合、データワード内の異なるデータグループを個別に反転する、または反転しないことが非常に有用である。これにより、データのグループを反転させることによって、記憶されるデータを、生じている故障に適合させることができる。
【００４０】
さらに、例えば「１」を記憶するのに「０」を記憶するよりも多くのエネルギーが必要である場合、またはその逆の場合に、データ反転は、電力消費を減少させることを可能にする。
【００４１】
例えば、消去状態が「１」によって表される場合、「１」を書き込むよりも「０」を書き込むのにはるかに多くのエネルギーが必要となることがある。あるいは、例えば、データワード内の「０」の数が「１」の数よりも多い場合、記憶前にデータを反転させることが有用である。
【００４２】
いくつかの実施形態によれば、データがグループ毎に反転される場合に、より良い適応を実現することができる。
【００４３】
いくつかの実施形態によれば、誤り率を減少させるためにデータ反転が採用される。誤りが単方向で生じる場合、例えば、記憶すべき「１」が例えば０縮退故障により「０」に変えられる場合、「０」のビットは誤り状態に変えられない。
【００４４】
データワード内の「１」の数が「０」の数よりも多い場合、１縮退故障よりも多くの０縮退故障が存在するときには、記憶前にデータを反転させることが有用である。それにより、反転後、「０」の数が「１」の数よりも多くなり、生じ得る誤りの数が減少される。
【００４５】
データがグループ毎に反転される場合に、より良い適応を実現することができる。
【００４６】
いくつかの実施形態によれば、「フィックスビット（ｆｉｘｂｉｔ）」がデータビットに追加される。データビットとフィックスビットは、合わせて、誤り訂正線形符号Ｃの情報ビットとして使用され、情報ビット、すなわちデータビットとフィックスビットから、チェックビットが決定される。
【００４７】
いくつかの実施形態によれば、符号Ｃは、ワードｗがコードワードである場合に、反転されたコードワード
【数３２】
0005923631.tif 000033
もコードワードであるように選択される。いくつかの実施形態では、コードワードは、直接または反転されて記憶される。
【００４８】
いくつかの実施形態では、誤りビットが生じた場合、誤り訂正符号Ｃを使用してフィックスビットも訂正される。訂正後、訂正されたフィックスビットは、メモリに記憶されるデータが反転されるべきか否かを示す。いくつかの実施形態によれば、フィックスビットは、データビットおよびチェックビットが訂正されるのと同じ線形符号Ｃによって訂正される。
【００４９】
いくつかの実施形態では、コードワードのビットのグループまたは部分集合が反転される。グループが反転されるか否かを示すフィックスビットが、あらゆるサブグループに割り当てられる。これらのフィックスビットは全て、チェックビットを決定するための情報ビットの一部である。
【００５０】
いくつかの実施形態によれば、サブグループは、サブグループのビットの反転が符号Ｃのコードワードを符号Ｃの別のコードワードに変換するように選択される。
【００５１】
いくつかの実施形態では、アドレスビットは、コードワードの一部であるが、記憶されず、アドレスビットは反転されない。
【００５２】
いくつかの実施形態によれば、フィックスビット（反転フラグビット）は、線形符号による誤り訂正の一部である。
【００５３】
いくつかの実施形態では、ビットのサブグループが反転される。
【００５４】
いくつかの実施形態によれば、サブグループのビットの反転がコードワードを別のコードワードに変換するように符号が選択される。
【００５５】
いくつかの実施形態では、チェックビットの決定にアドレスが含まれるが、それらは反転されない。
【００５６】
添付図面を使用していくつかの実施形態を詳細に述べる前に、同じまたは機能的に同一の要素は、図中で同じ参照番号を付されており、同じ参照番号を付されている要素に関する説明は繰り返さないことを指摘しておく。したがって、同じ参照番号を有する要素に関して与えられる説明は、相互に交換可能である。
【図面の簡単な説明】
【００５７】
【図１】一実施形態による装置を示す図である。
【図２】さらなる実施形態による装置を示す図である。
【図３】別の実施形態による装置を示す図である。
【図４】さらなる実施形態による装置を示す図である。
【図５】さらなる実施形態による装置を示す図である。
【図６】別のさらなる実施形態による装置を示す図である。
【発明を実施するための形態】
【００５８】
処理ユニットと、メモリとを備える装置が提供される。処理ユニットは、複数のビットを符号化して複数の符号化ビットを取得するように構成され、処理ユニットは、反転指定を特定するように構成される。符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、処理ユニットは、記憶ワードとして、第１のコードワードのビットをメモリに記憶するように構成される。符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、処理ユニットは、第１のコードワードの符号化ビットの部分集合の各符号化ビットを反転させて第２のコードワードを取得し、第２のコードワードをメモリに記憶するように構成される。
【００５９】
図１は、一実施形態による装置を示す。この装置は、処理ユニット１２０と、メモリ１１０とを備える。処理ユニット１２０は、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、ここで、複数の符号化ビットはそれぞれビット値を有し、誤り訂正符号は、少なくとも３の符号距離を有し、複数の符号化ビットは、線形誤り訂正符号の第１のコードワードを形成する。さらに、処理ユニット１２０は、符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するように構成され、ここで、符号化ビットの部分集合は、部分集合の全てのビットが反転される場合に誤り訂正符号の第１のコードワードがその符号の第２のコードワードに変換されるように決定され、部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含み、または複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、符号化ビットの部分集合のうちの１つの符号化ビットは、指示ビットであり、指示ビットのビット値は、第１の所定のビット値である。符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、処理ユニット１２０は、記憶ワードとして、第１のコードワードのビットをメモリ１１０に記憶するように構成され、ここで、メモリ１１０に記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含む。符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、処理ユニット１２０は、ビット値を変えることによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得するように構成され、さらに、記憶ワードとして、第２のコードワードをメモリ１１０に記憶するように構成され、ここで、第２のコードワードは、反転された指示ビットを含み、それにより、指示ビットのビット値は、第１の所定のビット値とは異なる第２の所定のビット値である。
【００６０】
上述したように、複数の符号化ビットが、線形誤り訂正符号の第１のコードワードを形成する。これは、複数の全ての符号化ビットのうちのいくつかの符号化ビットが、誤り訂正符号の第１のコードワードを形成することを意味する。
【００６１】
一実施形態では、処理ユニットは、例えば、反転指定として決定信号を生成するように構成されてもよく、ここで、決定信号は、例えば、符号化ビットの部分集合が反転されるべきか否かを示すことができる。
【００６２】
一実施形態によれば、装置は回路でよい。
【００６３】
一実施形態では、符号化ビットの部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含む。
【００６４】
一実施形態によれば、符号化ビットの部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含むわけではない。
【００６５】
一実施形態では、誤り訂正符号は、線形誤り訂正符号Ｃであり、第１の所定の値は、第１の定数２進値ｂｆであり、第２の所定の値は、第２の定数２進値
【数３３】
0005923631.tif 000034
であり、処理ユニット１２０は、記憶ワードをメモリ１１０から読み出すように構成され、処理ユニット１２０は、記憶ワードを読み出した後、指示ビットが記憶されているメモリ１１０内のビット位置から読み出されているビット値が第２の定数２進値
【数３４】
0005923631.tif 000035
であるときには、メモリ１１０に直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、指示ビットが記憶されているメモリ１１０内のビット位置から読み出されているビット値が第１の定数２進値ｂｆであるときには反転しないように構成される。
【００６６】
一実施形態によれば、誤り訂正符号は、線形誤り訂正符号Ｃであり、第１の所定の値は、第１の定数２進値ｂｆであり、第２の所定の値は、第２の定数２進値
【数３５】
0005923631.tif 000036
であり、処理ユニット１２０は、記憶ワードをメモリ１１０から読み出すように構成され、処理ユニット１２０は、１つまたは複数のビットが誤りである場合には、線形誤り訂正符号Ｃを使用することによって、記憶ワードの１つまたは複数のビットを訂正するように構成され、少なくとも指示ビットが書き込まれているビット位置に記憶されているビットが、前記ビットが誤りである場合に訂正され、処理ユニット１２０は、前記記憶ワードを読み出した後、かつ１つまたは複数のビットを訂正した後、指示ビットが記憶されているメモリ１１０内のビット位置から読み出されているビット値が第２の定数２進値
【数３６】
0005923631.tif 000037
であるときには、メモリ１１０に直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、指示ビットが記憶されているメモリ１１０内のビット位置から読み出されているビット値が第１の定数２進値ｂｆであるときには反転しないように構成される。
【００６７】
一実施形態では、線形誤り訂正符号Ｃは、パリティチェック行列Ｈを含み、パリティチェック行列Ｈの行の各成分の「１」の数は偶数である。
【００６８】
一実施形態によれば、メモリ１１０は、レジスタ、レジスタアレイ、またはアドレス可能なメモリ１１０である。
【００６９】
一実施形態では、メモリは、アドレス可能なメモリであり、処理ユニット１２０は、線形誤り訂正符号を採用することによって、かつアドレスビットを使用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成される。
【００７０】
一実施形態によれば、処理ユニット１２０は、符号化ビットの部分集合の「０」の数または符号化ビットの部分集合の「１」の数に応じて反転指定を特定するように構成される。
【００７１】
一実施形態では、書込み値をメモリに書き込んだ後、次いで書込み値をメモリから読み出して読出し値を取得した後、さらに、書込み値と読出し値とを比較した後に、誤りが生じていないときには、処理ユニットは、符号化ビットの部分集合が反転されるべきでないことを示す反転指定を特定するように構成される。
【００７２】
一実施形態では、書込み値をメモリに書き込んだ後、次いで書込み値をメモリから読み出して読出し値を取得した後、さらに、書込み値と読出し値とを比較した後に、せいぜいＴ（Ｔは、線形誤り訂正符号によって訂正することができる誤りの数以下である）個の誤りが生じているときには、処理ユニットは、符号化ビットの部分集合が反転されるべきでないことを示す反転指定を特定するように構成される。
【００７３】
一実施形態では、ビット部分集合の反転された書込み値をメモリ１１０に書き込んだ後、次いで書き込まれている反転されている書込み値をメモリ１１０から読み出して読出し値を取得した後、さらに、書き込まれている反転されている書込み値と読出し値とを比較した後に、直接書き込み、次いで読出し値と書込み値とを比較した後に生じるのとせいぜい同数の誤りが生じているときには、処理ユニット１２０は、符号化ビットの部分集合が反転されるべきであることを示す反転指定を特定するように構成される。
【００７４】
一実施形態によれば、ビット部分集合の反転された書込み値をメモリ１１０に書き込んだ後、次いで書き込まれている反転されている書込み値をメモリ１１０から読み出して読出し値を取得した後、さらに、書き込まれている反転されている書込み値と読出し値とを比較した後に、せいぜいＴ（Ｔは、符号Ｃによって訂正することができる誤りの数よりも小さい）個の誤りが生じているときには、処理ユニット１２０は、符号化ビットの部分集合が反転されるべきであることを示す反転指定を特定するように構成される。
【００７５】
一実施形態では、メモリ１１０はＦｌａｓｈメモリ１１０である。
【００７６】
別の実施形態によれば、メモリ１１０はＭ−ＲＡＭであり、またはメモリ１１０はＲ−ＲＡＭである。
【００７７】
一実施形態では、誤り訂正符号は、生成行列を含み、処理ユニット１２０は、符号化のために系統的形態での生成行列を使用することによって、複数のビットを符号化するように構成される。
【００７８】
別の実施形態によれば、符号Ｃは、ハミング符号または短縮ハミング符号である。
【００７９】
一実施形態では、誤り訂正符号は、Ｈｓｉａｏ符号または短縮Ｈｓｉａｏ符号である。
【００８０】
別の実施形態によれば、符号Ｃは、ＢＣＨ符号または短縮ＢＣＨ符号である。
【００８１】
さらに、別の実施形態が提供される。そのような別の実施形態では、処理ユニット１２０は、アドレス可能なメモリ１１０にアドレスａで記憶されるペイロードデータビットｘ１，…，ｘｎを、定数値を有するｌ（ここでｌ≧１）個のビットｂｆ１，…，ｂｆｌによって補完するように構成される。
【００８２】
処理ユニット１２０は、アドレスビットから導出されるビットがコードワードの形成に含まれないときには、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて、定数値を有するビットｂｆ１，…，ｂｆｌおよびペイロードデータビットｘ１，…，ｘｎをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎに符号化するように構成され、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎから決定されるチェックビットであり、さらに、処理ユニット１２０は、アドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが符号化に含まれるときには、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて、ビットｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋにコード化するように構成され、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋから決定されるチェックビットであり、Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）は、アドレスビットから関数ｆ：｛０，１｝ｒ→｛０，１｝ｋによって一意に決定される。
【００８３】
さらに、処理ユニット１２０は、直接または反転されて記憶されるビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎのＫ（Ｋ≧１）個のビットグループＹ１，…，Ｙｋを定義するように構成され、それにより、所定のビットｂｆ１，…，ｂｆｌの部分集合が、これらのグループそれぞれに一意に割り当てられる。
【００８４】
処理ユニット１２０は、ビットグループＹ１，…，ＹＫを決定するように構成され、それにより、１グループＹｊ（ｊ＝１，…，Ｋ）の全てのビットが反転される場合には、線形符号Ｃの第１のコードワードが符号Ｃの第２のコードワードに変換され、処理ユニットは、グループＹ１，…，ＹＫのうちのどのビットグループが、反転されてまたは反転されずにメモリに記憶されるかを選択するように構成される。
【００８５】
処理ユニット１２０は、メモリにアドレスａでビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎを書き込むように構成され、ここで、メモリ１１０に反転されて書き込まれるビットのグループに属するビットは、書込み前に反転され、反転されるビットを含むグループに属さないビットは、反転されずにメモリ１１０に書き込まれる。
【００８６】
さらに、処理ユニット１２０は、メモリ１１０にアドレスａで記憶されているビットを読み出すように構成される。
【００８７】
アドレスビットから導出されるビットがコードワードの形成に含まれない場合には、処理ユニット１２０は、同じアドレスに書き込まれた値とは誤りにより異なることがある、メモリ１１０から読み出されたビットを、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、誤り訂正符号Ｃに基づいて訂正するように構成される。
【００８８】
アドレスビットから導出されるビットがコードワードの形成に含まれる場合には、処理ユニット１２０は、メモリ１１０から読み出された、誤りであり得る値を、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、誤り訂正符号Ｃに基づいて、誤りであり得るアドレスビットから導出されるやはり誤りであり得るビット
【数３７】
0005923631.tif 000038
も使用することによって訂正するように構成される。
【００８９】
処理ユニット１２０は、それぞれのビットグループに一意に割り当てられた、符号Ｃを使用することによって訂正された読み出された定数値から、どのビットグループがメモリに直接または反転されて書き込まれているかを決定するように構成される。
【００９０】
処理ユニット１２０は、前のステップで書込み中に反転されているビットを含むビットグループと判断されているビットグループの読み出されて訂正されたビットを反転するように構成される。
【００９１】
一実施形態では、ｋ＝ｒ、および（Ａ１，…，Ａｋ）＝（ａ１，…，ａｒ）が成り立つ。
【００９２】
一実施形態によれば、ｋ＝１、Ａ１＝ｆ（ａ１，…，ａｒ）＝ａ１＋ａ２＋…＋ａｒが成り立ち、Ａ１は、アドレスビットａ１，…，ａｒのパリティである。
【００９３】
さらに、さらなる実施形態は、少なくとも１ビット誤りを訂正する線形符号Ｃのコードワードを形成するビットの部分集合をメモリセルのメモリ１１０に直接または反転させて書き込むため、および、メモリ１１０に書き込まれているビットを読み出し、直接または反転されて記憶されていた、メモリ１１０から誤り状態で読み出されることがあるビットから、元のビットを回復するために提供される。そのようなさらなる実施形態では、処理ユニット１２０は、メモリ１１０に直接または反転させて書き込むことができる、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて符号化されたビットの部分集合の数Ｋ（Ｋ≧１）を定義するように構成される。
【００９４】
処理ユニット１２０は、アドレスａ＝ａ１，…，ａｒ（ｒ≧２）で、少なくとも１ビット誤りを訂正する線形系統的符号のコードワードのサブワードとして記憶されるｎ個のペイロードデータビットｘ１，…，ｘｎを提供するように構成される。
【００９５】
処理ユニット１２０は、符号Ｃの情報ビットｕ１，…，ｕＮを生成するように構成され、ここで、アドレスａが符号Ｃのコードワードの形成に含まれない場合には、データビットｘ１，…，ｘｎは、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、
ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
が成り立ち、ここで、Ｎ＝ｌ＋ｎであり、アドレスａが符号Ｃのコードワードの形成に含まれる場合には、データビットｘ１，…，ｘｎ、およびアドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、
ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋ
が成り立ち、ここで、Ｎ＝ｌ＋ｎ＋ｋであり、ここで、
Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）
は、ｒ個のアドレスビットａ１，…，ａｒの値から関数ｆによって一意に決定される２進値であり、ｌ≧１および１≦ｋ≦ｒであり、
ここで、アドレスビットが誤り検出および誤り訂正に含まれない場合には、処理ユニット１２０は、符号Ｃのコードワードｙ１，…，ｙＰを生成するように構成され、ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、
ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
が成り立ち、ｃ１，…，ｃｍは、ｍ個のチェックビットであり、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、ｍ＝Ｐ−Ｎ、Ｎ＝ｎ＋ｌ、およびＰ＝ｎ＋ｍ＋ｌが成り立ち、
ここで、処理ユニット１２０は、ビット
ｙ１，…，ｙＮ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
のＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するように構成され、
したがって、ビットｂｆ１，…，ｂｆｌの部分集合が、各部分集合Ｙ１，…，Ｙｋに明瞭に割り振られ、
したがって、
【数３８】
0005923631.tif 000039
がビットｙ１，…ｙＰの２進値である場合、ｋ＝１，…，Ｋおよびｊ＝１，…，Ｐに関して、ｙｊが部分集合Ｙｋの要素である場合には、
【数３９】
0005923631.tif 000040
であり、ｙｊが部分集合Ｙｋの要素でない場合には、
【数４０】
0005923631.tif 000041
であるとき、
【数４１】
0005923631.tif 000042
は符号Ｃのコードワードであり、したがって、
【数４２】
0005923631.tif 000043
が成り立ち、Ｈは、符号ＣのＨ行列であり、
ここで、処理ユニット１２０は、ビットグループＹ１，…，Ｙｋのうちのどのグループがメモリ１１０に直接または反転されて書き込まれるかを定義するように構成され、
ここで、処理ユニット１２０は、メモリ１１０に書き込まれるＰ個のビットｄ１，…，ｄＰを生成するように構成され、ここで、ｉ＝１，…，Ｐに関して、ｙｉが、反転されてメモリ１１０に書き込まれるビットを含むグループに属するときには、
【数４３】
0005923631.tif 000044
であり、ｙｉが、反転されてメモリ１１０に書き込まれるビットを含むグループに属さないときには、ｄｉ＝ｙｉであり、
ここで、処理ユニット１２０は、メモリ１１０にアドレスａでビットｄ１，…，ｄＰを書き込むように構成され、
ここで、処理ユニット１２０は、アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数４４】
0005923631.tif 000045
を読み出すように構成され、これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄＰから、生じ得る誤りに起因して生じており、
ここで、処理ユニット１２０は、符号Ｃによって訂正すべきＬ個のビット位置ｋ１，…，ｋＬを定義するように構成され、ここで、ｌ≦Ｐおよび｛ｋ１，…，ｋＬ｝⊆｛１，…，Ｐ｝であり、これらのビット位置ｋ１，…，ｋＬは、値が誤りである場合には符号Ｃを使用することによって訂正され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属し、
ここで、処理ユニット１２０は、符号Ｃによって訂正可能な誤りに関して、符号Ｃに基づいて訂正すべき所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数４５】
0005923631.tif 000046
を決定するように構成され、
ここで、処理ユニット１２０は、少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数４６】
0005923631.tif 000047
を生成するように構成され、ここで、ｏｐは、一意に可逆のブール演算であり、
ここで、処理ユニット１２０は、既知の挿入された値ｂｆ１，…，ｂｆｌと、符号Ｃを使用することによって訂正されたそれぞれの読出し値とに基づいて、どのグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するように構成され、
ここで、処理ユニット１２０は、
【数４７】
0005923631.tif 000048
が、メモリ１１０に直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数４８】
0005923631.tif 000049
を出力し、
【数４９】
0005923631.tif 000050
が、メモリ１１０への書込み中にメモリ１１０に反転されて書き込まれているビットのグループに属する場合には、ビット
【数５０】
0005923631.tif 000051
を出力するように構成され、ここで、「ｏｐ」は、２項の一意に可逆のブール演算であり、
ここで、アドレスビットが誤り検出および誤り訂正に含まれる場合には、処理ユニット１２０は、符号Ｃのコードワードｙ＝ｙ１，…，ｙＰを生成するように構成され、ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、
ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）・Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋ
が成り立ち、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、Ｐ＝ｎ＋ｌ＋ｍ＋ｋ、Ｎ＝ｎ＋ｌ＋ｋが成り立ち、ｃ１，…，ｃｍは、チェックビットであり、
ここで、処理ユニット１２０は、ビット
ｙ１，…，ｙｎ＋ｌ，ｙｎ＋ｌ＋ｋ＋１，…，ｙＰ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
のＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するように構成され、
したがって、ビットｂｆ１，…，ｂｆｌの各ビットは、部分集合Ｙ１，…，ＹＫの１つのみに属し、したがって、
【数５１】
0005923631.tif 000052
がビットｙ１，…，ｙＰの２進値である場合、ｋ＝１，…，Ｋおよびｊ＝１，…，Ｐに関して、ｙｊが部分集合Ｙｋの要素である場合には、
【数５２】
0005923631.tif 000053
であり、ｙｊが部分集合Ｙｋの要素でない場合には、
【数５３】
0005923631.tif 000054
であるとき、
【数５４】
0005923631.tif 000055
は符号Ｃのコードワードであり、したがって、
【数５５】
0005923631.tif 000056
が成り立ち、Ｈは、符号ＣのＨ行列であり、
ここで、処理ユニット１２０は、どのビットグループＹ１，…，Ｙｋがメモリ１１０に直接または反転されて書き込まれるかを定義するように構成され、
ここで、処理ユニット１２０は、メモリ１１０に書き込まれるＰ−ｋ個のビットｄ１，…，ｄｍ＋ｌ＋ｎを生成するように構成され、ここで、ｉ＝１，…，ｍ＋ｎ＋ｌに関して、
ｙｉが、メモリ１１０に直接書き込まれるビットを含むグループに属するときには、ｄｉ＝ｙｉであり、
ｙｉが、メモリ１１０に反転されて書き込まれるビットを含むグループに属するときには、
【数５６】
0005923631.tif 000057
であり、
ここで、処理ユニット１２０は、メモリ１１０にアドレスａでビットｄ１，…，ｄｍ＋ｎ＋ｌを書き込むように構成され、
ここで、処理ユニット１２０は、アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数５７】
0005923631.tif 000058
を読み出すように構成され、これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄｎ＋ｌ、ｄｎ＋ｋ＋１，…，ｄＰから、生じ得る誤りに起因して生じており、
ここで、処理ユニット１２０は、値が誤りである場合には符号Ｃを使用することによって訂正されるＬ（Ｌ≦Ｐ−ｋ）個のビット位置ｋ１，…，ｋＬを定義するように構成され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属し、
ここで、処理ユニット１２０は、符号Ｃによって訂正可能な誤りに関して、所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数５８】
0005923631.tif 000059
を決定するように構成され、
ここで、処理ユニット１２０は、少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数５９】
0005923631.tif 000060
を生成するように構成され、ここで、「ｏｐ」は、２進の一意に可逆の演算であり、
ここで、処理ユニット１２０は、既知の挿入された値ｂｆ１，…，ｂｆｌと、読み出され、符号Ｃを使用することによって訂正された対応する訂正値とに基づいて、どのビットグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するように構成され、
ここで、処理ユニット１２０は、
【数６０】
0005923631.tif 000061
が、メモリ１１０に直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数６１】
0005923631.tif 000062
を出力し、
【数６２】
0005923631.tif 000063
が、メモリ１１０への書込み中にメモリ１１０に反転されて書き込まれているビットのグループに属する場合には、ビット
【数６３】
0005923631.tif 000064
を出力するように構成され、ここで、「ｏｐ」は、２桁の可逆の一意のブール演算である。
【００９６】
別の実施形態によれば、ビットをメモリ１１０に記憶するための装置が提供され、ここで、ビットは、線形誤り訂正符号Ｃを用いて符号化され、線形誤り訂正符号Ｃは、少なくとも３の符号距離を有し、線形誤り訂正符号Ｃを用いて符号化されたビットの部分集合がメモリ１１０に直接書き込まれるか、それともビット毎に反転されて書き込まれるかが判断され、符号Ｃは、Ｈ行列Ｈを備え、ここで、装置は、処理ユニット１２０と、メモリ１１０とを備える。メモリ１１０に直接または反転されて書き込まれたビットの部分集合は、少なくとも１つの２進定数値を含み、この値は、ペイロードデータビットと共に、線形符号Ｃのコードワードを形成するためにコード化に使用される。処理ユニット１２０は、それぞれのビット部分集合のビットがメモリ１１０に直接書き込まれるときに、２進定数値を２進値ｂｆとしてメモリ１１０に書き込むように構成される。処理ユニット１２０は、それぞれのビット部分集合のビットがメモリ１１０に反転されて書き込まれるときに、２進定数値を反転値
【数６４】
0005923631.tif 000065
としてメモリ１１０に書き込むように構成される。
【００９７】
処理ユニット１２０は、メモリ１１０に直接または反転されて書き込まれたビットの部分集合が反転されるときに、符号Ｃのコードワードを同じ符号のコードワードに変換するように構成され、符号のＨ行列は、メモリ１１０に直接または反転されて書き込まれたビットの部分集合に対応するＨ行列の行の各成分の「１」の数が偶数であるように生成される。
【００９８】
さらに、処理ユニット１２０は、メモリ１１０からの読出し時に、メモリ１１０から読み出された、誤りであり得るビットを、線形誤り訂正符号Ｃを使用することによって訂正するように構成され、ここで、それぞれのビット部分集合がメモリ１１０に直接書き込まれているときには、少なくとも、定数２進値ｂｆが書き込まれているビット位置にあるビットが訂正され、または、それぞれのビット部分集合がメモリ１１０に反転されて書き込まれているときには、少なくとも、定数２進値
【数６５】
0005923631.tif 000066
が書き込まれているビット位置にあるビットが訂正される。
【００９９】
さらに、処理ユニット１２０は、読出し後、定数値ｂｆまたは反転された定数値
【数６６】
0005923631.tif 000067
が記憶されているビット位置から読み出されている訂正された値が
【数６７】
0005923631.tif 000068
であるときには、メモリ１１０に直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、この値がｂｆであるときには反転しないように構成される。
【０１００】
別の実施形態によれば、方法が提供される。方法は、以下のステップを含む。
【０１０１】
線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップ。ここで、複数の符号化ビットがそれぞれビット値を有し、線形誤り訂正符号が、少なくとも３の符号距離を有し、複数の符号化ビットが、線形誤り訂正符号の第１のコードワードを形成する。
【０１０２】
符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するステップ。ここで、符号化ビットの部分集合は、部分集合の全てのビットが反転される場合に誤り訂正符号の第１のコードワードがその符号の第２のコードワードに変換されるように決定され、部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含み、または複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、符号化ビットの部分集合のうちの１つの符号化ビットは、指示ビットであり、指示ビットのビット値は、第１の所定のビット値である。
【０１０３】
符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、記憶ワードとして、第１のコードワードのビットをメモリに記憶するステップ。ここで、メモリに記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含む。
【０１０４】
さらに、符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、ビット値を変えることによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得し、記憶ワードとして、第２のコードワードをメモリに記憶するステップ。ここで、第２のコードワードは、反転された指示ビットを含み、それにより、指示ビットのビット値は、第１の所定のビット値とは異なる第２の所定のビット値である。
【０１０５】
以下、いくつかの実施形態の基本原理を述べる。
【０１０６】
いくつかの実施形態は、メモリへのデータの書込みおよびメモリからのデータの読出しに関する。いくつかの実施形態は、記憶すべきビットの部分集合またはグループを効果的にメモリに直接または反転させて書き込むことを可能にし、さらに、メモリから読み出すときにそれらを元の形態に復元することを可能にする。
【０１０７】
ビットの部分集合またはグループがメモリに直接記憶されるか、それとも反転されて記憶されるかは、例えば部分集合のビットの値によって決定することができ、または、例えば誤りもしくはエネルギー消費に関するメモリの特性によって決定することができ、または、例えば他の特性によって決定することができる。
【０１０８】
例えば、値０を有する永久的なメモリ誤りを、値１を有するメモリ誤りよりも頻繁に示すメモリに関しては、記憶すべきビットを（そのビットが「１」よりも「０」を多く有するときには）メモリに直接書き込むことが有利となり得る。なぜなら、それにより、ビットが０に縮退した永久的なメモリ誤りを示すメモリセルに値０が書き込まれる可能性が、そのようなメモリセルに値１が書き込まれる可能性よりも高くなるからである。それにより、永久的なメモリ誤りが誤った挙動を引き起こす可能性を減少させることができる。
【０１０９】
また、ビットを暫定的にメモリに直接書き込み、次いで反転させて書き込んで、生じている誤りがより少ない形態を決定することも可能である。
【０１１０】
従来の浮動ゲートメモリ（例えば、ＥＥＰＲＯＭ＝電気的に消去可能なプログラマブルリードオンリーメモリ、Ｆｌａｓｈ）や電荷トラップメモリ（例えば、ＭＯＮＯＳ、Ｎａｎｏｄｏｔ）など多くの不揮発性メモリの概念、さらにまた、ＭＲＡＭ（磁気抵抗ランダムアクセスメモリ）、Ｒ−ＲＡＭ、ＰＣＲＡＭ、またはＣＢＲＡＭ（導電性ブリッジングランダムアクセスメモリ）など新規のメモリ概念は、本質的に、セルの信頼性、または書込み中の電流消費に関する好ましい値を提供している。例えば、従来の浮動ゲートは、当業者によく知られている不規則ビットを示し、不規則ビットは、低いカットオフ電圧で状態をプログラミングするときにデータ破壊を示す。読出しまたは書込み中の電流消費は、プログラムすべき／読み出すべきデータパターンに大きく依存する。低いカットオフ電圧でのセルからの読出しは、本来的に、高いカットオフ電圧での読出しに比べてかなり多くの電流を必要とする。プログラミング時、この状況は、場合によっては逆になり得る。例えばホットキャリアプログラミング時、高いカットオフ電圧を有する状態にしなければならないセルのみが、プログラミング電流を必要とする。この状況は、電荷捕捉の概念に関しても同様である。同様に、磁気異方性エネルギーのエネルギー非対称性を示すＭＲＡＭなどの新規のメモリに関して、データ記憶に際し、より高いエネルギー状態は、より低いエネルギーを有する状態よりも危険である。しかし、いくつかの実施形態は、不揮発性メモリに関して採用することができるだけでなく、例えば、ＳＲＡＭもしくはＤＲＡＭ内部での永久的な誤り、または特定の状態においてより頻繁に生じる誤りに関しても使用することができる。
【０１１１】
第１の２進値ｂ１の書込み中のエネルギー消費が、第１の２進値
【数６８】
0005923631.tif 000069
の書込み中よりも高い場合、書き込むべきビットが値ｂ１をより多く含むか、値ｂ２をより多く含むかに応じて、データをメモリに直接または反転させて書き込むことが可能である。このようにすると、値ｂ２の数とせいぜい同数の値ｂ１を書き込むことが可能であり、それにより、エネルギー消費が減少される。
【０１１２】
ビットグループのビット部分集合の値ｂ１の数またはビットｂ２の数に基づいて、グループのビットをメモリに反転させて書き込むべきか、それとも直接書き込むべきかを決定することができる。これにより、ビットの部分集合がメモリに直接書き込まれるか、それとも反転されて書き込まれるかを判断するための労力を減らすことができる。
【０１１３】
いくつかの実施形態では、記憶すべきビットは、例えば、生成行列Ｇと、Ｈ行列もしくはパリティチェック行列Ｈとを有する線形誤り訂正符号Ｃを使用することによって符号化すべきであるが、ビットが記憶されるべき場所を示すアドレスビットは、符号化に含まれる必要がないことがある。例えば、系統的形態での生成行列Ｇを用いて符号化を行うことが有利となることがあり、Ｇ行列は、部分行列として単位行列を含み、Ｈ行列は、いくつかの実施形態での系統的形態を示すことがあり、他の実施形態では非系統的形態を示すことがある。メモリからビットを読み出すときに、ビット部分集合のビットがメモリに直接書き込まれているか、それとも反転されて書き込まれているかをチェックするために、ビット（これは、例えば、後に再び記憶されることがある）が、定数２進値によって補完される。ここで、補完された定数２進値は、線形符号のそれぞれのコードワードの形成に含まれる。
【０１１４】
メモリに直接または反転されて書き込まれるビットの部分集合は、メモリに反転させてまたは直接書き込むことができるビット部分集合のビットが反転されるときに、反転されていないビットから形成されている符号Ｃのコードワードがその符号Ｃの別のコードワードに変換されるように形成される。
【０１１５】
この特性により、有利には、メモリから読み出されるビットの訂正に関して、読み出されたビット部分集合からのビットがメモリに直接または反転されて書き込まれているかどうかを知る必要なく、誤り訂正符号Ｃに基づいて、メモリから読み出されているビットの訂正および場合によっては誤りビットの訂正を行うことが可能になる。
【０１１６】
メモリからデータを読み出したとき、次いで、定数値を有するビットが直接または反転されて書き込まれているビット位置で、訂正されたビットを使用することによってデータを訂正した後、ビット部分集合またはビットグループのビットがメモリに直接書き込まれているか、それとも反転されて書き込まれているかを見出すことができる。
【０１１７】
誤り訂正符号として、当業者に知られている線形誤り訂正符号が使用される。そのような符号に関する例は、ハミング符号、Ｈｓｉａｏ符号、ＢＣＨ符号などである。記憶すべきデータの所要のビット幅に符号を適合させるために、短縮ハミング符号、短縮Ｈｓｉａｏ符号、または短縮ＢＣＨ符号などの短縮符号が使用されることがよくある。短縮符号は、短縮されていない符号から、チェックビットに対応しないそれぞれのＨ行列の列を削除することによって取得することができる。
【０１１８】
使用される用語および実施形態の説明をより良く理解できるように、符号のいくつかの基本的な用語を以下に簡単に説明する。
【０１１９】
線形符号Ｃは、生成行列またはＧ行列Ｇと、Ｈ行列Ｈとを含む。Ｃが、（Ｑ，Ｎ）符号である場合、コードワードはＱ個のビットを含み、コードワードは、ｙ＝ｙ１，…，ｙＱによって表され、ｕ＝ｕ１，…，ｕＮと称されるＮ個の情報ビットが存在し、ここでＱ＞Ｎが成り立つ。
【０１２０】
Ｇ行列は、Ｎ行とＱ列を有する（Ｎ，Ｑ）行列であり、Ｈ行列は（ｍ，Ｑ）行列であり、ここで、ｍ＝Ｑ−Ｎが成り立つ。情報ビットｕから、コードワードｙは、関係
ｙ＝ｕ・Ｇ
に従って決定される。
【０１２１】
符号Ｃが系統的符号である場合、生成行列Ｇは、形態
Ｇ＝（ＰＮ，ｍ，ｌＮ）
を有し、ここで、ｍ＝Ｑ−Ｎであり、ｌＮは、Ｎ次元の単位行列であり、ＰＮ，ｍは、パリティ行列である。
【０１２２】
割り当てられたＨ行列は、
【数６９】
0005923631.tif 000070
と定義することができ、ここで、ｌｍは、ｍ次元の単位行列であり、
【数７０】
0005923631.tif 000071
は、行と列が交換された、パリティ行列ＰＮ，ｍの転置行列である。Ｎ、Ｑ、ｍの値が特に言及されない場合、またはこれらの値が文脈から分かる場合には、単にＧ＝（Ｐ，Ｉ）およびＨ＝（Ｉ，ＰＴ）と書く。
【０１２３】
系統的形態でのＧ行列およびＨ行列は、Ｇ＝（Ｉ，Ｐ）およびＨ＝（ＰＴ，Ｉ）としても使用されることが知られており、これにより、チェックビットがコードワード内で情報ビットの左に配置される、またはチェックビットがコードワード内で情報ビットの右に配置される。
【０１２４】
Ｇ行列のＮ個の行が、符号Ｃのコードワードである。
【０１２５】
系統的符号Ｃにおいて、
ｙ＝ｙ１，…，ｙＱ＝（ｕ１，…，ｕｎ）・Ｇ＝ｃ１，…，ｃｍ，ｕ１，…，ｕＮ
が成り立ち、ここで、ｃ１，…，ｃｍ，ｕ１，…，ｕＮ・Ｐが、コードワードｙ１，…，ｙＱのチェックビットである。情報ビットｕ１，…，ｕＮは、コードワードの修正されない部分であり、チェックビットが情報ビットに追加される。誤りにより、コードワードｙ＝ｙ１，…，ｙＱは、破壊されて別のワード
【数７１】
0005923631.tif 000072
になることがあり、ここで、
【数７２】
0005923631.tif 000073
としてのｅが、誤りベクトルと呼ばれ、ここで、「＋」は、成分毎のｍｏｄ２加算またはＸＯＲ演算を表す。
【０１２６】
ワードｙ’の誤りシンドロームｓは、
ｓ＝Ｈ・ｙ’
であり、ここで、ｓ＝ｓ１，…，ｓｍは、ｍ個の成分を含む。ワードｙ＊の誤りシンドロームは、ｙ＊が符号Ｃのコードワードである場合には、正確に０である。
【０１２７】
ｙがコードワードであり、ｙ’が、誤りに起因する誤りワードである（ここで、ｙ＋ｙ’＝ｅである）場合、
Ｈ・（ｙ’）＝Ｈ・（０＋ｙ’）＝Ｈ・（ｙ＋ｙ’）＝Ｈ・ｅ
が成り立ち、ワードｙ’の誤りシンドロームは、誤りベクトルｅのみに依存し、ｙ’は、コードワードｙとｅだけ異なる。
【０１２８】
ｉビット誤りが存在する場合、誤りベクトルｅの正確にｉ個のビットが１であり、他の成分は全て０である。例えば、誤りベクトルｅの正確に１つの成分が１である場合、ｅの成分が１であるビットにおいて１ビット誤りが存在する。
【０１２９】
符号Ｃが１ビット誤り訂正符号である場合、全ての１ビット誤りの誤りシンドロームは、相異なり、０とは異なり、これらの誤りシンドロームそれぞれに対して、次いで特定の１ビット誤りが一意に割り振られる。次いで、復号器回路として実装される復号器が、その入力に印加される誤りシンドロームから、どのビット位置が反転／訂正されるべきか判断する。
【０１３０】
符号Ｃが２ビット誤り訂正符号である場合、全ての２ビット誤りの誤りシンドロームは、相異なり、やはり０とは異なり、これらの誤りシンドロームそれぞれに対して、決定された２ビット誤りまたは１ビット誤りが一意に割り振られる。次いで、復号器回路として実現される復号器が、その入力に印加される誤りシンドロームから、どのビット位置が反転／訂正されるか判断する。それぞれの言明は、３ビット誤り訂正符号、４ビット誤り訂正符号などにも当てはまる。
【０１３１】
誤りシンドロームは、例えば、シンドローム生成器が、ワードｗ＝ｗ１，…，ｗＱに関して、例えばＸＯＲゲートを使用することによって関係
ｓ（ｗ）＝Ｈ・ｗ
を実施することによって決定することができる。
【０１３２】
ｙ＝ｙ１，…，ｙＱおよびｖ＝ｖ１，…，ｖＱが符号Ｃのコードワードである場合、ｙ＋ｖも符号Ｃのコードワードである。
【０１３３】
さらに、以下のことが成り立つ。
【０１３４】
ｙ＝ｙ１，…，ｙＱが符号Ｃのコードワードであり、ｗ＝ｗ１，…，ｗＱが、誤りシンドロームｓ（ｗ）＝Ｈ・ｗを有するワードである場合、ワードｗ＋ｙの誤りシンドロームは、ワードｗの誤りシンドロームｓ（ｗ）に等しい。なぜなら、
Ｈ・（ｙ＋ｗ）＝Ｈ・ｙ＋Ｈ・ｗ＝ｓ（ｗ）
が成り立つからであり、また、コードワードが、ワードへの成分毎の加算によってｍｏｄ２加算されるとき、ワードの誤りシンドロームが変化しないからである。コードワードｙ＝ｙ１，…，ｙＱをワードｗ＝ｗ１，…，ｗＱに追加することは、ｗのそれらの成分が反転されることを意味し、ここで、ｙの成分は１である。
【０１３５】
特に、
【数７３】
0005923631.tif 000074
が符号Ｃのコードワードである場合、ｙ＝ｙ１，…，ｙＱについて、
【数７４】
0005923631.tif 000075
も同様に符号Ｃのコードワードであり、ワードｗ＝ｗ１，…，ｗＱのシンドロームｓ（ｗ）は、ｗの全ての成分が反転されるときに変化しない。
【０１３６】
Ｍが、メモリに直接または反転されて書き込まれたビットを含む、誤り訂正符号Ｃのコードワードｙ＝ｙ１，…，ｙＱのビットの部分集合である場合、ワード
【数７５】
0005923631.tif 000076
が符号Ｃのコードワードであると有利である。
【０１３７】
集合Ｍに属するコードワードｙ１，…，ｙＱのビットが反転される場合、得られるワード
【数７６】
0005923631.tif 000077
もやはりコードワードである。元のコードワードｙ１，…，ｙＱがメモリに書き込まれるか、それとも集合Ｍに属するビットで反転されたコードワードがメモリに書き込まれるかに関係なく、どちらの場合にも、符号Ｃのコードワードがメモリに書き込まれる。記憶されている誤りであり得るコードワード
【数７７】
0005923631.tif 000078
または（ｙ＋ｙＭ）’を読み出すとき、符号Ｃを用いた読出しビットの訂正は、ｙ’または（ｙ＋ｙ’）から形成された誤りシンドロームに基づいて行うことができ、ｙがメモリに書き込まれているか、それとも集合Ｍに属するビットで反転されたコードワードｙ＋ｙＭがメモリに書き込まれているかを知る必要はない。なぜなら、誤りシンドロームは、生成された誤りのみに依存し、例えば、生成された誤りベクトルｅのみに依存し、どのコードワードがメモリに書き込まれているかには依存しないからである。例えば、定数２進値ｂｆ１，…，ｂｆ１が書き込まれているビット位置で読み出された値を、読出し後に訂正することができ、符号Ｃを用いた訂正後に、これらの既に訂正された値に基づいて、コードワードｙが直接記憶されているか、それともＭに属するビットで反転されて記憶されているか判断することができると有利になり得る。
【０１３８】
さらに、定数２進値が、記憶されているペイロードデータビットと同じ符号Ｃで訂正されると有利であり、チェックビットの数は通常、この訂正によって増加しない。
【数７８】
0005923631.tif 000079
が符号Ｃのコードワードである場合、アドレスビットが符号化に含まれないときには、ビットの部分集合Ｍは、コードワードｙ＝ｙ１，…，ｙＱの全てのビットからなっていてよい。
【０１３９】
コードワードをそこで反転させることができ、そこで反転されたコードワードも符号ＣのコードワードであるようなビットＭｉ（ｉ＝１，２，…）のグループは、容易に決定することができる。
【０１４０】
部分集合のビットで反転された符号Ｃのコードワードも符号Ｃのコードワードとなるようなビットのグループまたは部分集合は、容易に決定することができる。なぜなら、「１」である符号Ｃの任意のコードワードのビットの部分集合がそのような部分集合を形成するからである。
【０１４１】
そのようなビット部分集合は各コードワード毎に決定することができるので、複数の適切なビット部分集合が存在する。
【０１４２】
次に、特定の実施形態を述べる。
【０１４３】
第１の実施形態では、誤り訂正符号Ｃの一例として、Ｎ＝１１の情報ビットを有する長さＱ＝１５の１ビット誤り訂正（１５，１１）ハミング符号を考察する。
【０１４４】
考察する符号ＣのＨ行列は、
【数７９】
0005923631.tif 000080
であり、変数ｃ１、ｃ２、ｃ３、ｃ４、ｂｆ１、ｘ１、ｘ２、ｘ３、ｘ４、ｘ５、ｘ６、ｘ７、ｘ８、ｘ９、ｘ１０が、左から右に、式（１）のＨ行列の列に対応する。
【０１４５】
Ｈ行列の４つの行はそれぞれ８個の「１」を含み、８は偶数であるので、
【数８０】
0005923631.tif 000081
が符号Ｃのコードワードであり、その１５ビット全てで成分毎に反転されたコードワードも、符号Ｃのコードワードである。
【０１４６】
Ｋ＝１、およびコードワードの全てのビットを含む部分集合Ｍ１＝Ｍ＝｛ｙ１，…，ｙ１５｝が選択される。
【０１４７】
１０個のペイロードデータビットｘ１，…，ｘ１０が提供され、これらは、定数２進値ｂｆ１によって補完されて、１１個の情報ビット
ｕ＝ｕ１，…，ｕ１１＝ｂｆ１，ｘ１，…，ｘ１０
にされる。
【０１４８】
一実施形態では、定数２進値は、ｂｆ１＝０と定義される。符号Ｃは、４つのチェックビットｃ１，…，ｃ４を含む。符号化ビットｙ１，…，ｙ１５は、符号ＣのＧ行列Ｇを使用することによって、
ｙ１，…，ｙ１５＝ｃ１，…ｃ４，ｂｆ１，ｘ１，…，ｘ１０＝（ｂｆ１，ｘ１，…，ｘ１０）・Ｇ
として決定される。それにより、Ｇ行列は、行列Ｇ＝（ｌ１１，Ｐ１１，５）であり、ここで、ｌ１１は、１１次元の単位行列であり、Ｐ１１，５に関して、
【数８１】
0005923631.tif 000082
が成り立ち、
【数８２】
0005923631.tif 000083
が成り立つ。
【０１４９】
コーダは、式（３）で定義される関係に従って、情報ビットｂｆ１，ｘ１，…，ｘ１０からのチェックビットｃ１，…，ｃ４を生成する。例えば、コーダは、ＸＯＲゲートで実装されても、一般的な合成ツールを使用することによって実装されてもよい。Ｋ＝１が成り立ち、反転させるべきただ１つのビット部分集合Ｙ１＝｛ｙ１，…，ｙ１５｝が存在する。
【０１５０】
ｙ＝ｙ１，…，ｙ１５について、
【数８３】
0005923631.tif 000084
が符号Ｃのコードワードであるので、その結果、
【数８４】
0005923631.tif 000085
も符号Ｃのコードワードである。なぜなら、全てのビットｙ１，…，ｙＱ（Ｑ＝１５）がＹ１に属するからである。
【０１５１】
特定のコードワードとして、データビットｘ１，ｘ２，…，ｘ１０＝１，０，１，１，０，１，１，１，１，１から形成されるコードワード、および定数２進値ｂｆ１＝０を次に考察する。式（３）に従って、ｃ１＝１、ｃ２＝０、ｃ３＝１、およびｃ４＝０であり、したがって、それぞれのコードワードは、
ｙ１，…，ｙ１５＝１，０，１，０，０，１，０，１，１，０，１，１，１，１，１
である。
【０１５２】
コードワードは、１０個の「１」と、５個の「０」とを有する。できるだけ多くの「０」をメモリに書き込むことが有利である一例を考察する。ＭＲＡＭに当てはまるように、記憶値０が破壊されて記憶値１になることは、その逆に比べてあまり頻繁ではない。また、Ｆｌａｓｈメモリに当てはまるように、値０を書き込むことは、値１を書き込むよりもエネルギーを必要としないことがあり得る。また、メモリ内の１つまたは複数の位置に永久的な誤りが存在することもあり得る。したがって、０縮退誤りが、ビットｙＱ＝ｙ１５の位置に存在することがあり得る。Ｆｌａｓｈメモリへの書込み時に当てはまるように、例としてワード１，０，１，０，０，１，０，１，１，０，１，１，１，１，１がメモリに書き込まれる場合、および書き込まれた値が読み出された値と比較される場合、ｙ１５＝１がメモリに書き込まれているため、書き込まれた値１の代わりに値０が読み出されるので、ｙ１５の位置に０縮退誤りが存在することが分かる。しかし、Ｙ１のビット、例えばこの場合には全てのビットが反転されてメモリに書き込まれることが決定される場合、
【数８５】
0005923631.tif 000086
が、メモリにアドレスａで書き込まれ、１５番目のビットでの生じ得る０縮退誤りが影響を持たなくなる。さらなる誤りが存在せず、アドレスａで読出しが行われる場合、
【数８６】
0005923631.tif 000087
である。
例えば、読み出されたワードの誤りシンドローム
ｓ＝Ｈ・（１，０，１，１，１，０，０，１，０，０，０，０，０）＝０
を決定することによって、符号Ｃのコードワードが読み出されており、誤り訂正が必要ないことが分かる。
【０１５３】
値
【数８７】
0005923631.tif 000088
から、ワードが反転されてメモリに書き込まれていると結論付けることができる。元のワードを復元するために、全ての読み出されたビット
【数８８】
0005923631.tif 000089
を反転させるべきであり、したがって、
【数８９】
0005923631.tif 000090
が成り立つ。
【０１５４】
例えば、読み出された値
【数９０】
0005923631.tif 000091
を１から０に破壊する誤りが存在する場合、この誤りは、同じ符号Ｃによって１に訂正され、この符号Ｃは、以下により詳細に述べるように、他のビットでの誤りも訂正する。
【０１５５】
有利には、誤り訂正のための労力が小さい。コードワードのビットがメモリに直接または間接的に（反転させて）書き込まれているかどうかを示すために、定数値を有するただ１つの追加のビットしか必要ない。
【０１５６】
それにより、メモリは、例えば、レジスタ、レジスタアレイ、ＲＡＭ、Ｍ−ＲＡＭ、またはＦｌａｓｈメモリでよい。
【０１５７】
次に、図２を参照して、一例としてアドレス可能なメモリを使用して、メモリへの書込みを論じる。
【０１５８】
図２で、データビットｘ１，…，ｘｎ（ｎ＝１０）と、定数値、例えば値０を有するビットｂｆ１とが、コーダＣｏｄ１１の入力に供給され、コーダＣｏｄ１１は、
ｙ＝ｙ１，…，ｙ１５＝ｃ１，…ｃ４，ｂｆ１，ｘ１，…，ｘ１０＝（ｂｆ１，ｘ１，…，ｘ１０）・Ｇ
に従ってコードワードｙ＝ｙ１，…，ｙＱ（Ｑ＝１５）を生成するように実装され、コードワードｙは、コーダＣｏｄ１１の１５ビット幅の出力で出力される。
【０１５９】
ここで、符号Ｃがその系統的形態で与えられると仮定する。コーダ１１の出力は、第１の１５ビット幅の入力を有するＸＯＲ回路１２に供給される。さらに、ＸＯＲ回路１２は、２進反転信号Ｉｎｖが印加される第２の１ビット幅の入力を備える。さらに、ＸＯＲ回路１２は、１５ビット幅の出力を備え、この出力は、値ｄ１，…，ｄ１５を有し、メモリＭｅｍ１３の１５ビット幅のデータ入力に接続される。
【０１６０】
図２で、ＸＯＲ回路１２は、例えば、１５個のＸＯＲゲートを備えることがあり、１５個のＸＯＲゲートはそれぞれ、２つの入力と、１つの出力とを有し、これらのＸＯＲゲートそれぞれの第１の入力が、コーダＣｏｄ１１の１５個の２進出力ラインの１つに接続され、１５個のＸＯＲゲートそれぞれの第２の入力が、反転信号Ｉｎｖを有するＸＯＲ回路１２の第２の入力に接続される。
【０１６１】
Ｉｎｖ＝０である場合には、ｄ１，…，ｄ１５＝ｙ１，…，ｙ１５が成り立ち、Ｉｎｖ＝１の場合には、
【数９１】
0005923631.tif 000092
が成り立ち、したがって、反転信号に応じて、コーダによって出力されるビットは、直接（修正されず／変更されずに）または反転されてメモリに書き込まれる。
【０１６２】
データを書き込むとき、メモリＭｅｍ１３は、書込みアドレスａを提供され、メモリＭｅｍ１３のデータ入力に印加されるデータは、アドレスａに記憶される。
【０１６３】
読出しアドレスａ’が適用されるとき、およびデータを読み出すとき、読出しアドレスａ’に記憶されているデータが読み出される。書込みアドレスａが読出しアドレスａ’に等しい場合、すなわちａ＝ａ’であるとき、値
【数９２】
0005923631.tif 000093
がデータ出力で出力される。アドレスａに書き込まれたデータｄ１，…，ｄ１５と、同じアドレスａから読み出されるデータ
【数９３】
0005923631.tif 000094
とは、誤りにより異なることがあり得る。
【０１６４】
メモリＭｅｍ１３から読み出された値から、ｓ＝（ｓ１，ｓ２，ｓ３，ｓ４）として、誤りシンドローム
【数９４】
0005923631.tif 000095
および
【数９５】
0005923631.tif 000096
が成り立つ。誤りシンドロームｓ＝（ｓ１，ｓ２，ｓ３，ｓ４）は、式（４）を実現するシンドローム生成器Ｓｙｎ（図２には図示せず）によって決定される。式（４）の実施は、例えば合成ツールを使用することによって行うことができる。表１に示され、式（４）から読み取ることができるように、訂正すべきビット
【数９６】
0005923631.tif 000097
それぞれに対して、シンドロームが、一意に可逆に割り振られる。
【０１６５】
【表１】
0005923631.tif 000098
【０１６６】
ｄ１，…，ｄ１５＝０，１，０，１，１，０，１，０，０，１，０，０，０，０，０として反転された、ｙ５＝ｂｆ１＝０を有するコードワードｙ１，…，ｙ１５＝１，０，１，０，０，１，０，１，１，０，１，１，１，１，１がメモリＭｅｍ１３に書き込まれている場合、および読出しビット
【数９７】
0005923631.tif 000099
が、
【数９８】
0005923631.tif 000100
である場合、式（４）に従って、ｓ１＝０、ｓ２＝０、ｓ３＝０、およびｓ４＝０が成り立ち、読出し値は訂正されない。
【数９９】
0005923631.tif 000101
および定数値ｂｆ１＝０が、第５のビットに直接または反転されて記憶されているので、読出しワードは、成分毎に反転され、したがって、
【数１００】
0005923631.tif 000102
が成り立つ。
【０１６７】
誤りにより、ビット
【数１０１】
0005923631.tif 000103
が破壊されて０になる場合、
【数１０２】
0005923631.tif 000104
がメモリＭｅｍ１３から読み出され、シンドローム生成器が、式（４）に従って、誤りシンドロームｓ＝（１，１，１，１）を決定する。表１の最終行に従って、値
【数１０３】
0005923631.tif 000105
が
【数１０４】
0005923631.tif 000106
に訂正される。訂正された値１は、出力された訂正後のワード０，１，０，１，１，０，０，０，１，０，０，０，１，０，０，０，０，０が反転されていることを特定し、したがって、
【数１０５】
0005923631.tif 000107
が回路によって出力される。
【０１６８】
以下、データ中の誤りを考察する。例えば、誤りにより、値
【数１０６】
0005923631.tif 000108
が１である場合、ワード
【数１０７】
0005923631.tif 000109
がメモリＭｅｍ１３から読み出される。シンドローム生成器は、式（４）に従って、誤りシンドロームｓ＝（０，１，１，１）を生成し、そこに、訂正すべきビット
【数１０８】
0005923631.tif 000110
が復号器によって割り振られ、したがって、訂正されたワード
【数１０９】
0005923631.tif 000111
が、
【数１１０】
0005923631.tif 000112
に従って生成され、したがって、訂正後のワードは、
【数１１１】
0005923631.tif 000113
である。
【０１６９】
【数１１２】
0005923631.tif 000114
が成り立つので、ワードが反転され、したがって、
【数１１３】
0005923631.tif 000115
が成り立ち、適切に訂正されたワードが回路によって出力される。
【０１７０】
図３は、誤りであり得るデータ
【数１１４】
0005923631.tif 000116
を読み出すため、誤りデータを訂正するため、および書込み前にデータが反転されている場合にはデータを反転するための一実施形態による装置を示す。
【０１７１】
図２と同様に、装置は、メモリＭｅｍ１３を備え、メモリＭｅｍ１３に、データｄ１，…，ｄ１５が書き込まれている。
【０１７２】
図３において、メモリがアドレス可能なメモリであり、書込みアドレスａが書込み中に生成され、読出しアドレスａ’が読出し中に生成されると仮定する。ここで、書込みアドレスａは、読出しアドレスａ’と同じでよい。いくつかの実施形態は、さらに、書込みおよび読出しのためのイネーブル信号など、メモリＭｅｍ１３の制御信号を備える。
【０１７３】
いくつかの実施形態では、メモリＭｅｍ１３は、例えば１５個のメモリ要素を備えることがあるレジスタでよい。メモリ要素は、例えばフリップフロップまたはラッチでよい。
【０１７４】
読出しアドレスａ’を生成するとき、誤りであり得るビット
【数１１５】
0005923631.tif 000117
が、メモリＭｅｍ１３の１５個のデータ出力で出力される。ａ’＝ａが成り立ち、メモリＭｅｍ１３に書込みアドレスａで書き込まれたデータが、同じ読出しアドレスａから読み出されると仮定することができる。読み出されるビット
【数１１６】
0005923631.tif 000118
は、例えば、書き込まれたビットｄ１，…，ｄ１５とは異なることがある。なぜなら、読み出されるビットは、メモリ誤りにより、またはデータラインでの誤りにより、誤りであり得るからである。
【０１７５】
メモリＭｅｍ１３のデータ出力上に読み出されたビット
【数１１７】
0005923631.tif 000119
は、シンドローム生成器Ｓｙｎｄ２１の１５ビット幅の入力に供給され、またＸＯＲ回路２３の１５ビット幅の第１の入力にも供給される。シンドローム生成器Ｓｙｎｄ２１は、式（４）に従って誤りシンドロームｓ＝ｓ１，ｓ２，ｓ３，ｓ４を生成するように実装される。この誤りシンドロームは、シンドローム生成器Ｓｙｎｄ２１の４ビット幅の出力で提供され、この出力は、復号器Ｄｅｃ２２の４ビット幅の入力に接続される。復号器Ｄｅｃ２２は、その１５ビット幅の出力で、訂正信号ｅ＝ｅ１，…，ｅ１５を出力する。復号器Ｄｅｃ２２は、表１に従って訂正信号を生成するように構成される。ＸＯＲ回路２３は、例えば、１５個のＸＯＲゲートＸＯＲ１，…，ＸＯＲ１５を備え、１５個のＸＯＲゲートはそれぞれ、２つの入力と、１つの出力とを有する。
【０１７６】
ｉ＝１，…，１５に関して、値
【数１１８】
0005923631.tif 000120
が、ＸＯＲ回路２３のＸＯＲゲートＸＯＲｉの第１の入力に供給され、値ｅｉが、ＸＯＲゲートＸＯＲｉの第２の入力に供給され、したがって、値
【数１１９】
0005923631.tif 000121
が、ＸＯＲゲートＸＯＲｉの出力で出力される。ｂｆ１＝０が選択されているので、値
【数１２０】
0005923631.tif 000122
を有するＸＯＲ回路２３のＸＯＲゲートＸＯＲ５の出力が、ＸＯＲ回路２６の第１の１ビット幅の入力に直接供給され、ＸＯＲ回路２６は、例えば、１５個のＸＯＲゲート
【数１２１】
0005923631.tif 000123
を備えることができ、１５個のＸＯＲゲートがそれぞれ、１つの２進出力と、２つの２進入力とを有する。
【０１７７】
ＸＯＲ回路２３の１５ビット幅の出力は、ＸＯＲ回路２６の第２の１５ビット幅の入力に接続される。
【０１７８】
ｉ＝１，…，１５に関して、値
【数１２２】
0005923631.tif 000124
が、ＸＯＲゲート
【数１２３】
0005923631.tif 000125
の第１の入力に供給され、このゲートの第２の入力にＸＯＲゲートＸＯＲｉの出力が接続され、この出力は、信号
【数１２４】
0005923631.tif 000126
を有する。したがって、訂正された値
【数１２５】
0005923631.tif 000127
は、
【数１２６】
0005923631.tif 000128
の場合には反転され、
【数１２７】
0005923631.tif 000129
の場合には反転されない。図３に示されるように、シンドローム生成器Ｓｙｎｄ２１と、復号器Ｄｅｃ２２と、ＸＯＲ回路２３とが、訂正器２４を生成する。
【０１７９】
ｙ＝ｙ１，…，ｙ１５がメモリに書き込まれているか、それとも
【数１２８】
0005923631.tif 000130
がメモリに書き込まれているかに関係なく、メモリＭｅｍ１３から読み出された値
【数１２９】
0005923631.tif 000131
の訂正が訂正器２４によって行われる場合に有利である。さらに、データがメモリＭｅｍ１３に直接書き込まれているか、それとも反転されて書き込まれているかを決定するために使用することができる定数２進値が、メモリＭｅｍ１３から読み出される誤りであり得るビット
【数１３０】
0005923631.tif 000132
の線形符号Ｃによる訂正に含まれると有利であり、それにより、追加のビット、例えば追加のチェックビットが訂正に必要とされない。
【０１８０】
図３の実施形態によれば、復号器Ｄｅｃ１５は、２進訂正値ｅ＝ｅ１，…，ｅ１５を生成し、それにより、例示の場合には、ビットが誤りである場合、および誤りが符号Ｃによって訂正可能である場合には、１５個のビット
【数１３１】
0005923631.tif 000133
が全て訂正される。
【０１８１】
しかし、いくつかの実施形態によれば、ビットの一部のみ、例えば、データビットに対応するビットと、定数２進値ｂｆ１に対応するビット
【数１３２】
0005923631.tif 000134
とのみが訂正される。いくつかの実施形態では、データビットに割り振られた値の一部のみが訂正される。
【０１８２】
図３は、ｂｆ１がｂｆ１＝０に設定される場合を示す。ｂｆ１をｂｆ１＝１に設定することも可能である。次いで、ＸＯＲ回路２６の第１の入力に印加された値
【数１３３】
0005923631.tif 000135
を有するデータラインが反転される。
【０１８３】
図４は、誤り検出器ＦＥ３１が採用される一実施形態を示す。
【０１８４】
図３の回路部分に対応する回路部分は、図３におけるものと同じ参照番号で示されており、再び説明はしない。
【０１８５】
図４で、誤りシンドロームｓ＝ｓ１，ｓ２，ｓ３，ｓ４を有するシンドローム生成器Ｓｙｎｄ２１の出力が、復号器Ｄｅｃ２２の入力に接続され、さらに、誤り検出器ＦＥ３１の４ビット幅の入力に接続され、誤り検出器ＦＥ３１は、その出力でｑ（ｑ≧１）ビット幅の誤り信号Ｅを出力する。
【０１８６】
誤り検出器ＦＥ３１は、シンドロームｓがｓ≠０である場合には１ビット幅の誤り信号Ｅ＝１を出力し、シンドロームｓがｓ＝０である場合にはＥ＝０を出力するように実装することが可能である。このとき、誤り検出器ＦＥ３１は、４つの入力と１つの出力とを有するＯＲゲートによって実現することができる。
【０１８７】
一実施形態では、ｑ＝２である。そのような実施形態では、ｓ＝０のとき、Ｅ＝（Ｅ１，Ｅ２）＝０，０が出力される。ｓが符号ＣのＨ行列の列の１つに等しいとき、Ｅ＝１，０が出力される。ｓ≠０であり、Ｈ行列の列の１つに等しくないとき、Ｅ＝０，１が出力される。
【０１８８】
Ｅ＝１，０の場合、符号Ｃによって訂正可能な誤りが検出される。Ｅ＝０，１の場合、符号Ｃによって訂正可能でない誤りが検出される。Ｅ＝０，０の場合、これは、検出可能な誤りが存在しないことを意味する。
【０１８９】
いくつかの実施形態によれば、誤り検出器ＦＥ３１は、ｑ＝２が成り立つように実装することができ、例えば、Ｅ＝０，０およびＥ＝１，１は、誤りが存在しないことを示し、Ｅ＝０，１またはＥ＝１，０は、誤りが存在することを示す。
【０１９０】
以下、符号Ｃが８個のデータビットｘ１，…，ｘ８と６個のチェックビットｃ１，…，ｃ６とを有するさらなる実施形態を説明する。
【０１９１】
Ｋ＝２個のビット部分集合Ｙ１、Ｙ２が生成され、これらを、メモリＭｅｍ１３に直接または反転させて書き込むことができると定義する。８個のデータビットｘ１，…，ｘ８は、２つの定数２進値ｂｆ１、ｂｆ２によって保管されて、１０個の情報ビットｕ１，…，ｕ１０を生成し、したがって、
ｕ１，…，ｕ１０＝ｂｆ１，ｂｆ２，ｘ１，…，ｘ８
である。
【０１９２】
考察される符号ＣのＨ行列は、例えば、
【数１３４】
0005923631.tif 000136
と定義することができる。
【０１９３】
左から右に、変数ｃ１、ｃ２、ｃ３、ｃ４、ｃ５、ｃ６、ｂｆ１、ｂｆ２、ｘ１、ｘ２、ｘ３、ｘ４、ｘ５、ｘ６、ｘ７、ｘ８が、左から右へのＨ行列（５）の列にそれぞれ対応し、したがって、ｃ１が第１の列に対応し、ｃ２が第２の列に対応し、以下同様である。
【０１９４】
この実施形態の符号Ｃは、短縮Ｈｓｉａｏ符号である。Ｈ行列の全ての列が、対として異なり、各列は、１個または３個の「１」を有するので、奇数個の「１」を有する。
【０１９５】
Ｈ行列の各行が偶数個の「１」を含むので、
【数１３５】
0005923631.tif 000137
は符号Ｃのコードベクトルであり、したがって、ｙ＝ｙ１，…，ｙ１６が符号Ｃのコードワードである場合、
【数１３６】
0005923631.tif 000138
も符号Ｃのコードワードである。なぜなら、線形符号の２つのコードワードの成分毎のＸＯＲ和もこの符号のコードワードであるからである。
【０１９６】
一例として、集合Ｙ１＝｛ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６，ｂｆ１，ｘ４｝が、メモリに直接または反転されて書き込まれるビットの第１の部分集合Ｙ１として選択され、集合Ｙ２＝｛ｂｆ２，ｘ１，ｘ２，ｘ３，ｘ５，ｘ６，ｘ７，ｘ８｝が、第２の部分集合として選択される。
【０１９７】
それに対応して、Ｈ行列の第１〜第７、および第１２の列が、集合Ｙ１に割り振られる。これらの列それぞれの成分に２つの「１」が存在し、したがって、Ｈ行列のこれらの列の成分毎のｍｏｄ２の和は０であり、ここで、
ｈ１＋ｈ２＋ｈ３＋ｈ４＋ｈ５＋ｈ６＋ｈ７＋ｈ１２＝０
であり、ここで、
Ｈ・（１，１，１，１，１，１，１，０，０，０，０，１，０，０，０，０）Ｔ＝０
が成り立ち、（１，１，１，１，１，１，１，０，０，０，０，１，０，０，０，０）がコードワードである。
【０１９８】
Ｈ行列の第８〜第１１および第１３〜第１６の列は、集合Ｙ２に割り振られる。これらの列それぞれの成分において、４つの「１」が存在し、したがって、Ｈ行列のこれらの列の成分毎のｍｏｄ２の和は０であり、ここで、
ｈ８＋ｈ９＋ｈ１０＋ｈ１１＋ｈ１３＋ｈ１４＋ｈ１５＋ｈ１６＝０
であり、ここで、
Ｈ・（０，０，０，０，０，０，０，１，１，１，１，０，１，１，１，１）Ｔ＝０
が成り立ち、（０，０，０，０，０，０，０，１，１，１，１，０，１，１，１，１）も、考察される符号のコードワードである。
【０１９９】
集合Ｙ１とＹ２は異なり、それらの和集合は、コードワードの１６成分全てを含む。
【０２００】
ここで、メモリＭｅｍ１３に直接または反転させて書き込むことができるビットの第３の集合Ｙ３を選択することも可能である。そのような集合Ｙ３は、コードワードの全てのビットを含むこともある。メモリから読み出されている訂正された値
【数１３７】
0005923631.tif 000139
は、ビットのどの部分集合がメモリＭｅｍ１３に反転されて書き込まれており、ビットのどの部分集合がメモリＭｅｍ１３に直接書き込まれているかを決定する。
【０２０１】
そのような実施形態において、コードワードｙ１，…，ｙ１６をメモリに直接、一部反転させて、または完全に反転させて書き込む４つの異なるオプションが存在する。ｙ７とｙ８が、定数２進値ｙ７＝ｂｆ１＝０、ｙ８＝ｂｆ２＝０に設定されると仮定する。
【０２０２】
ワード
【数１３８】
0005923631.tif 000140
をメモリに書き込むことができる。
【０２０３】
ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６，０，０，ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８が符号Ｃのコードワードである場合、ビットのどの部分集合が反転されているかに関係なく、メモリに書き込まれている値ｄ１，…，ｄ１６が符号Ｃのコードワードであるので、メモリから読み出される誤りであり得る値
【数１３９】
0005923631.tif 000141
は、どのビットグループがメモリに直接書き込まれており、どのビットグループが反転されてメモリに書き込まれているかを知る必要なく、符号Ｃを使用することによって訂正することができる。
【０２０４】
特に、読み出された値
【数１４０】
0005923631.tif 000142
を
【数１４１】
0005923631.tif 000143
に訂正することができ、ここで、
【数１４２】
0005923631.tif 000144
は、どのビットグループのビットも反転されていないことを示し、
【数１４３】
0005923631.tif 000145
は、ビットグループＹ１のビットが反転されていることを示し、
【数１４４】
0005923631.tif 000146
は、ビットグループＹ２のビットが反転されていることを示し、
【数１４５】
0005923631.tif 000147
は、ビットグループＹ３＝Ｙ１∪Ｙ２のビットが反転されていることを示す。
【０２０５】
次に、以下の実施形態を参照して一態様を論じる。４つのチェックビット（ｃ１、ｃ２、ｃ３、ｃ４）と、６つのデータビット（ｘ１、ｘ２、ｘ３、ｘ４、ｘ５、ｘ６）と、２つの定数２進値（ｂｆ１、ｂｆ２）と、１つのＨ行列Ｈとを有する１ビット誤り訂正符号Ｃを考察し、ここで、
【数１４６】
0005923631.tif 000148
であり、変数ｃ１、ｃ２、ｃ３、ｃ４、ｂｆ１、ｂｆ２、ｘ１、ｘ２、ｘ３、ｘ４、ｘ５、ｘ６が、式（６）のＨ行列Ｈの列に対応する。
【０２０６】
Ｈ行列の第３の列および第４の列の「１」の数は奇数であり、ｙ＝ｙ１，…，ｙ１２＝ｃ１，…，ｃ４，ｂｆ１，ｂｆ２，ｘ１，…，ｘ６が符号Ｃのコードワードである場合、
【数１４７】
0005923631.tif 000149
は、コードワードでない。ビットの２つの部分集合Ｙ１およびＹ２をメモリに直接または反転させて書き込むことができると定義される。ここで、
【数１４８】
0005923631.tif 000150
が符号Ｃのコードベクトルである必要はない。
【０２０７】
部分集合Ｙ１は、例えば、
Ｙ１＝｛ｃ１，ｃ２，ｃ３，ｃ４，ｂｆ１，ｘ１｝
と定義することができ、部分集合Ｙ２は、例えば、
Ｙ２＝｛ｃ３，ｃ４，ｂｆ２，ｘ３，ｘ４，ｘ５，ｘ６｝
と定義することができる。
【０２０８】
集合Ｙ１とＹ２は、ビットｃ３とおよびｃ４を共通して有するので、互いに素ではない。
【０２０９】
以下のことが成り立つ。ｙ＝ｙ１，…，ｙ１２が符号Ｃのコードワードである場合、Ｙ１に属するビットを反転させることによってｙから得られるワードもコードワードである。
【０２１０】
同様に、以下のことが成り立つ。ｙ＝ｙ１，…，ｙ１２が符号Ｃのコードワードである場合、Ｙ２に属するビットを反転することによってｙから得られるワードもコードワードである。
【０２１１】
以下、コードワードｙ＊＝１，０，１，１，１，１，１，１，０，１，０，１が、メモリに例えばアドレスａで直接または反転されて記憶される場合を考察する。テストにおいて、例えば、第１２のビットｙ＊１２が０縮退誤りを有すると特定されていると仮定する。このとき、コードワード
ｙ＊＝１，０，１，１，１，１，１，１，０，１，０，１＝ｃ１，ｃ２，ｃ３，ｃ４，ｂｆ１，ｂｆ２，ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６
の代わりに、コードワード
【数１４９】
0005923631.tif 000151
をメモリに記憶することができ、これは、部分集合Ｙ２のビットで反転され、第１２のビットでの値は０である。これにより、このビット位置での０縮退誤りは影響を持たなくなる。
【０２１２】
さらなる誤りが存在しない場合、アドレスａから読み出すときに、ワード
【数１５０】
0005923631.tif 000152
が読み出される。
【数１５１】
0005923631.tif 000153
が符号Ｃのコードワードであるので、
【数１５２】
0005923631.tif 000154
および値
【数１５３】
0005923631.tif 000155
は、部分集合Ｙ２のビットが反転されていることを示し、したがって、
【数１５４】
0005923631.tif 000156
が成り立つ。部分集合Ｙ２のビットで反転されたビットをメモリに書き込むことによって、また、行われている反転を定数２進値に基づいて元に戻すことによって、（０縮退）誤りは影響を持たず、許容することができる。
【０２１３】
ここで、既に述べたように、誤りがテストによって検出されていることがあり得る。
【０２１４】
一実施形態によれば、コードワードｙ１，…，ｙＱがメモリに直接書き込まれ、その後、それぞれの値が読み出されて、書き込まれた値と比較されて、誤りが生じているか否かおよびどこで誤りが生じているかを決定する。
【０２１５】
誤り検出器が存在する場合、以下のように処理を進めることができる。
【０２１６】
誤り検出器が、アドレスａにコードワードｙ１，…，ｙＱを書き込んだ後に、アドレスａからの読出し時に誤りを示さない場合、アドレスａに新たなワードは書き込まれない。誤り検出器が誤りを示す場合、Ｙ１のビットで反転されたワードが、メモリにアドレスａで書き込まれる。ここで、そのアドレスからの読出し時に誤り検出器が誤りを示さない場合、メモリにさらなるワードは書き込まれない。誤り検出器が、アドレスａに記憶されているワードを読み出すときに誤りを示す場合、Ｙ２のビットで反転されたワードがメモリに書き込まれる。ここで、そのアドレスからの読出し時に誤り検出器が誤りを示さない場合、メモリにさらなるワードは書き込まれない。これは、読出し中に誤りが示されなくなるまで、または反転されたビットのさらなる部分集合ＹＫが存在しなくなるまで続けられる。
【０２１７】
さらに、以下の手順が可能である。
【０２１８】
アドレスａで、コードワードｙ１，…，ｙＱ、または部分集合Ｙｉのビットで反転されたコードワードがメモリに書き込まれ、この書き込まれたワードは、誤り検出器がいくつかの誤りを示し、それらの誤りが符号Ｃによって訂正可能であるときには、保たれる。
【０２１９】
また、誤りが特定の数を越えていないことを誤り検出器が示すときには、メモリに書き込まれたビットを保つことも可能である。符号Ｃが２ビット誤り訂正符号である場合、誤り検出器がせいぜい１ビット誤りを示すときには、メモリに書き込まれているワードを保つことができる。なぜなら、このとき、さらなるランダムな誤りを訂正することができるからである。
【０２２０】
誤り処理のために、いくつかの異なる部分集合Ｙ１，…，Ｙｋ（ｋ＞１）が存在すると有利であり、それらの部分集合のビットはそれぞれ、メモリに直接または反転させて書き込むことができ、これは、永久的であり得る様々な誤りへの良好な適応を可能にする。
【０２２１】
以下、さらなる実施形態を述べる。
【０２２２】
メモリにアドレスａ＝ａ１，…，ａ５で直接または反転されて記憶される、５つのチェックビットｃ１，…，ｃ５と、８つのペイロードデータビットｘ１，…，ｘ８と、定数２進値ｂｆ１とを有する短縮ハミング符号を、符号Ｃとして考察する。そのような実施形態では、アドレスビットａ１，…，ａ５が符号化に含まれる。
【０２２３】
符号のＨ行列Ｈは、
【数１５５】
0005923631.tif 000157
であり、ここで、Ｈ行列の列をｈ１，…，ｈ１４と呼ぶ。変数ｃ１、ｃ２、ｃ３、ｃ４、ｃ５、ｂｆ１、ｘ１、ｘ２、ｘ３、ｘ４、ｘ５、ｘ６、ｘ７、ｘ８、ａ１、ａ２、ａ３、ａ４、ａ５が、左から右へ、Ｈ行列（７）のそれぞれの列に対応する。系統的形態での対応するＧ行列Ｇは、
Ｇ＝（Ｐ１４，５，ｌ１４）
であり、ここで、ｌ１４は、１４次元の単位行列であり、Ｐ１４，５は、形式
【数１５６】
0005923631.tif 000158
を有する。
【０２２４】
メモリへの書込み時、データがメモリに書き込まれるメモリアドレスのアドレスビットａ１，…，ａ５を採用することによって、符号Ｃのコードワードは、
【数１５７】
0005923631.tif 000159
と定義され、ここで、
ｃ１＝ｂｆ１＋ｘ１＋ｘ２＋ｘ３＋ｘ５＋ｘ７＋ａ１＋ａ３＋ａ５
ｃ２＝ｂｆ１＋ｘ１＋ｘ２＋ｘ３＋ｘ４＋ｘ５＋ｘ８＋ａ２＋ａ４＋ａ５
ｃ３＝ｂｆ１＋ｘ１＋ｘ３＋ｘ４＋ｘ６＋ｘ７＋ａ２＋ａ４＋ａ５
ｃ４＝ｂｆ１＋ｘ２＋ｘ３＋ｘ４＋ｘ６＋ｘ８＋ａ１＋ａ４＋ａ５
ｃ５＝ｘ１＋ｘ２＋ｘ３＋ｘ４＋ｘ６＋ｘ８＋ａ２＋ａ３＋ａ５
が成り立ち、ａ１，…，ａ５を書込みアドレスと呼ぶ。
【０２２５】
ビットの集合
Ｙ１＝｛ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｂｆ１，ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８｝
が定義され、それにより、この集合のビットを、メモリに直接または反転させて書き込むことができる。ｂｆ１は、定数値ｂｆ１＝１に設定される。
【０２２６】
ｖ＝ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｂｆ１，ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ａ１，ａ２，ａ３，ａ４，ａ５
が符号Ｃのコードワードである場合、
【数１５８】
0005923631.tif 000160
も符号Ｃのコードワードである。
【０２２７】
アドレスａ＝ａ１，…，ａ５で、ビットが直接記憶されるときには、ビット
ｄ１＝ｃ１、ｄ２＝ｃ２、ｄ３＝ｃ３、ｄ４＝ｃ４、ｄ５＝ｃ５、ｄ６＝ｂｆ１＝１、ｄ７＝ｘ１、ｄ８＝ｘ２、ｄ９＝ｘ３、ｄ１０＝ｘ４、ｄ１１＝ｘ５、ｄ１２＝ｘ６、ｄ１３＝ｘ７、ｄ１４＝ｘ８
がメモリに書き込まれ、
または、アドレスａで、ビット
【数１５９】
0005923631.tif 000161
がメモリに書き込まれる。
【０２２８】
次いで、読出しアドレスａ’でメモリから読み出すとき、ａ＝ａ’であり、誤りが存在しないときには、ｉ＝１，…，１４に関して、ビット
【数１６０】
0005923631.tif 000162
が読み出され、ビット
【数１６１】
0005923631.tif 000163
が、符号Ｃのコードワードを形成する。
【０２２９】
ビット
【数１６２】
0005923631.tif 000164
に、符号Ｃによって訂正することができる誤りが存在する場合、ワード
【数１６３】
0005923631.tif 000165
の誤りが訂正されて
【数１６４】
0005923631.tif 000166
とされ、値
【数１６５】
0005923631.tif 000167
に基づいて、データがメモリに直接または反転されて書き込まれているかどうかが判断される。例えば、
【数１６６】
0005923631.tif 000168
の場合、データはメモリに直接書き込まれており、
【数１６７】
0005923631.tif 000169
の場合、データはメモリに反転されて書き込まれている。アドレスビットでの誤りは訂正されない。それらは、誤りが符号Ｃによって検出可能であるときに検出される。
【０２３０】
例えば、１ビット誤りがアドレスビットａ１に存在する場合、関連の誤りシンドロームは［１，０，０，１，０］Ｔである。Ｈ行列の列ｈ１，…，ｈ１４はどれも［１，０，０，１，０］Ｔに等しくないので、ビット
【数１６８】
0005923631.tif 000170
の「１」の訂正は行われず、誤りは、訂正不可能な誤りとして示される。これにより、例えば、読出しアドレスと書込みアドレスが一致せず、符号Ｃによって検出可能な誤りの位置で異なることを検出することができる。
【０２３１】
図５は、一実施形態に関して、アドレスビットａ＝ａ１，…，ａ５が、記憶されるデータの符号化に含まれる様子を示す。図５の回路は、９ビット幅の第１の入力と、５ビット幅の第２の入力と、１４ビット幅の出力とを有するコーダＣｏｄ４１を備える。さらに、図５の回路は、１４ビット幅の第１の入力と、１ビット幅の第２の入力と、１４ビット幅の出力とを有する反転回路４２を備える。さらに、図５の回路は、１４個のデータ入力と、１４個のデータ出力と、書込みアドレスおよび読出しアドレス用の５ビット幅のアドレス入力とを有するアドレス可能なメモリＭｅｍ４３を備える。
【０２３２】
例えば、８個のペイロードデータビットｘ１，…，ｘ８が記憶される。ペイロードデータビットは、定数２進値を有するビットｂｆ１によって保管され、ここでは、定数値は、例えばｂｆ１＝１である。
【０２３３】
ビットｂｆ１，ｘ１，…，ｘ８は、コーダＣｏｄ４１の９ビット幅の第１の入力に印加され、書込みアドレスのビットａ１，…，ａ５は、コーダＣｏｄ４１の５ビット幅の第２の入力に印加される。
【０２３４】
コーダＣｏｄ４１は、その１４個の出力で、コードワードｃ１，…，ｃ５，ｂｆ１＝１，ｘ１，…，ｘ８，ａ１，…，ａ５のビットｃ１，…，ｃ５，ｂｆ１＝１，ｘ１，…，ｘ８を出力するように構成され、ここで、コードワードは、
（ｃ１，…，ｃ５，１，ｘ１，…，ｘ８，ａ１，…，ａ５）＝（１、ｘ１，…，ｘ８，ａ１，…，ａ５）・Ｇ
に従って生成され、ここで、Ｇは、考察される符号の生成行列である。
【０２３５】
符号Ｃがその系統的形態で提供されると仮定する。
【０２３６】
符号Ｃｏｄ４１の１４ビット幅の出力は、ＸＯＲ回路４２の第１の１４ビット幅の入力に接続され、ＸＯＲ回路４２の第２の１ビット幅の入力に、反転信号Ｉｎｖが印加される。
【０２３７】
値ｄ１，…，ｄ１４を有するＸＯＲ回路１２の１４ビット幅の出力が、メモリＭｅｍ４３の１４ビット幅のデータ入力に接続される。
【０２３８】
ここで、ＸＯＲ回路４２は、それぞれ２つの入力と１つの出力とを有する１４個のＸＯＲゲートを備え、これらのＸＯＲゲートそれぞれの第１の入力は、コーダＣｏｄ４１の１４個の２進出力ラインの１つにそれぞれ接続され、これらのＸＯＲゲートの第２の入力は、反転信号Ｉｎｖを有するＸＯＲ回路４２の第２の入力にそれぞれ接続される。
【０２３９】
Ｉｎｖ＝０に関しては、ｄ１，…，ｄ１４＝ｃ１，…，ｃ５，１，ｘ１，…，ｘ８が成り立ち、一方、Ｉｎｖ＝１に関しては、
【数１６９】
0005923631.tif 000171
が成り立ち、したがって、反転信号に応じて、符号によって出力されるビットは、直接、すなわち修正されずに、または反転されてメモリに書き込まれる。
【０２４０】
ここで、いくつかの実施形態によれば、コーダは、
ｃ１，…，ｃ５，１，ｘ１，…，ｘ８，ａ１，…，ａ５
が符号Ｃのコードワードである場合に、
【数１７０】
0005923631.tif 000172
も符号Ｃのコードワードであるように実装される。
【０２４１】
一実施形態では、データの書込み時、メモリＭｅｍ４３は、書込みアドレスａを提供され、したがって、メモリＭｅｍ４３のデータ入力に印加されたデータは、アドレスａ＝ａ１，…，ａ５に記憶される。書込みアドレスのビットａ１，…，ａ５は、符号の情報ビット
ｕ１，…，ｕ１４＝ｂｆ１，ｘ１，…，ｘ８，ａ１，…，ａ５
の一部である。
【０２４２】
データの読出し時、読出しアドレスａ’が印加されるときに、読出しアドレス
【数１７１】
0005923631.tif 000173
に記憶されているデータがメモリから読み出される。
【０２４３】
書込みアドレスａと読出しアドレスａ’が一致する場合、すなわちａ＝ａ’であるとき、値
【数１７２】
0005923631.tif 000174
がデータ出力で出力される。アドレスａに書き込まれたデータｄ１，…，ｄ１５と、同じアドレスａから読み出されるデータ
【数１７３】
0005923631.tif 000175
とは、誤りにより異なることがある。誤りが生じていない場合、読出し値
【数１７４】
0005923631.tif 000176
は、データがメモリに直接書き込まれているか、それとも反転されて書き込まれているかを示す。符号によって訂正可能な誤りが生じている場合、メモリから読み出され、
【数１７５】
0005923631.tif 000177
に基づいて訂正されたデータに応じて、誤りが符号Ｃによって訂正可能であるときにデータがメモリに反転されて書き込まれているか、それとも直接書き込まれているかを検出することができる。
【０２４４】
図５の装置の補完として、図６は、誤りであり得るビット
【数１７６】
0005923631.tif 000178
を読み出すため、誤りビットを訂正するため、および、メモリへの書込み前にビットが反転されている場合にはビットを反転するための一実施形態による装置を示す。図５を参照して既に説明したように、アドレスビットａ１，…，ａ５は、符号Ｃのコードワードの形成に含まれる。ビットｄ１，…，ｄ１４がメモリＭｅｍ４３に書き込まれる。
【０２４５】
読出しアドレスａ’がメモリＭｅｍ４３に提供され、誤りであり得るビット
【数１７７】
0005923631.tif 000179
が読み出される。誤りであり得るビット
【数１７８】
0005923631.tif 000180
は、メモリＭｅｍ４３の１４個の２進データ出力で出力される。ａ＝ａ’が成り立ち、書込みアドレスａで書き込まれたビットが、同じアドレスａ’＝ａから読み出されると仮定することができる。例えば永久的または非永久的もしくは一時的なメモリ誤りにより、読み出されたビットｄ’は誤りであり得るので、読み出されたビット
【数１７９】
0005923631.tif 000181
は、書き込まれたビットｄ１，…，ｄ１４に必ずしも等しくない。
【０２４６】
誤りが存在しない場合、
【数１８０】
0005923631.tif 000182
が符号Ｃのコードワードである。
【０２４７】
（ｄ’，ａ’）が符号のコードワードでない場合、メモリＭｅｍ４３に誤りが存在するか、またはアドレスの決定時に誤りが生じている。
【０２４８】
メモリ４３のデータ出力で出力されるビット
【数１８１】
0005923631.tif 000183
は、同時に、シンドローム生成器Ｓｙｎｄ５１の１４ビット幅の第１の入力に供給され、シンドローム生成器Ｓｙｎｄ５１の５ビット幅の第２の入力には、読出しアドレスａ’のビット
【数１８２】
0005923631.tif 000184
が供給される。シンドローム生成器Ｓｙｎｄ５１は、その５ビット幅の出力で、５ビット幅の誤りシンドロームｓ＝（ｓ１，…，ｓ５）を出力する。ここで、シンドローム生成器Ｓｙｎｄ５１は、
【数１８３】
0005923631.tif 000185
に従って誤りシンドロームを生成するように構成され、ここで、例えば式（７）のＨ行列Ｈを使用することができる。読出しアドレスａ’は、シンドローム形成に含まれる。
【０２４９】
シンドローム生成器Ｓｙｎｄ５１の５ビット幅の出力は、復号器Ｄｅｃ５２の５ビット幅の入力に接続され、復号器Ｄｅｃ５２は、例えば、シンドローム生成器Ｓｙｎｄ５１が、メモリから読み出されたビット
【数１８４】
0005923631.tif 000186
に関する訂正ビットｅ６，ｅ７，…，ｅ１４を備える訂正ベクトルｅ＝（ｅ６，ｅ７，…，ｅ１４）を生成するように実装することができる。
【０２５０】
チェックビットも訂正すべきときには、訂正器がさらに訂正信号ｅ１，…，ｅ５も生成することが可能である。
【０２５１】
さらに、訂正器がアドレスビット
【数１８５】
0005923631.tif 000187
に関する訂正ビットも生成することが可能であり、ここで、アドレスビットに関する０ではない訂正信号は、アドレス誤りが存在することを示し、誤りアドレスａ’から読み出されたビットはさらには使用されない。
【０２５２】
図６で、ＸＯＲ回路５３は、例えば９個のＸＯＲゲートＸＯＲ６，…，ＸＯＲ１４を備えることができ、９個のＸＯＲゲートそれぞれが、２つの入力と１つの出力とを有する（図６には、９個のＸＯＲゲートは個々には図示されていない）。ｉ＝６，…，１４に関して、値
【数１８６】
0005923631.tif 000188
がＸＯＲゲートＸＯＲｉの第１の入力に供給され、値ｅｉが第２の入力に供給され、したがって、値
【数１８７】
0005923631.tif 000189
が第ｉのＸＯＲゲートＸＯＲｉの出力で出力される。シンドローム生成器Ｓｙｎｄ５１と、復号器Ｄｅｃ５２と、ＸＯＲ回路５３とは、一体となって訂正器５４を形成する回路部分とみなすことができる。訂正器５４は、図６に示されるように誤り検出器ＦＥ５７も備えることができる。
【０２５３】
ＸＯＲ回路５３の最下位の出力、すなわち、値
【数１８８】
0005923631.tif 000190
を有するＸＯＲゲートＸＯＲ６の出力は、インバータ５５の入力に供給され、インバータ５５は、その出力で値
【数１８９】
0005923631.tif 000191
を出力する。ＸＯＲ回路５３の８個のより上位の出力、すなわち、値
【数１９０】
0005923631.tif 000192
を有するＸＯＲゲートＸＯＲ７，…，ＸＯＲ１４の出力は、図６ではそれぞれ２つの入力と１つの出力とを有する８個のＸＯＲゲート
【数１９１】
0005923631.tif 000193
を備える反転回路５４の第１の８ビット幅の入力に接続され、反転回路５４の第２の１ビット幅の入力は、インバータ５５の出力に接続される。
【０２５４】
ｉ＝７，…，１４に関して、値
【数１９２】
0005923631.tif 000194
が、ＸＯＲゲート
【数１９３】
0005923631.tif 000195
の第１の入力に印加され、インバータ５５によって出力される値
【数１９４】
0005923631.tif 000196
が、第２の入力に供給される。ＸＯＲゲート
【数１９５】
0005923631.tif 000197
は、その出力で値
【数１９６】
0005923631.tif 000198
を出力する。
【０２５５】
図６は、定数２進値ｂｆ１とペイロードデータビットｘ１，…，ｘ８とが記憶されているビット位置が訂正されることを示す。
【０２５６】
また、さらなるビット、例えばチェックビットも訂正される、またはペイロードデータビットの部分集合のみが訂正されることもあり得る。
【０２５７】
図６に示される実施形態では、誤り検出器ＦＥ５７が存在し、その５ビット幅の入力がシンドローム生成器５１の出力に接続され、そのｑビット幅の出力で誤り信号Ｅを出力し、ここでｑ≧１が成り立つ。
【０２５８】
いくつかの実施形態に関して、書込みアドレスａのビットａ１，…，ａ４、および読出しアドレスのビット
【数１９７】
0005923631.tif 000199
（ｒ＝５）が、符号化および復号化に含まれ、それにより、チェックビットが、情報ビットから、例えば、
ｕ１，…，ｕ１４＝ｂｆ１，ｘ１，…，ｘ８，ａ１，…，ａ５
に従って決定されることが示されている。
【０２５９】
また、ビットが、関数ｆ：｛０，１｝ｒ→｛０，１｝ｔ（ｔ＜ｒ）によって、アドレスビットａ１，…，ａｒから導出されてもよく、前記導出されるビット
Ａ１，…，Ａｔ＝ｆ（ａ１，…，ａｒ）
は、
ｕ１，…，ｕｋ＝ｂｆ１，ｘ１，…，ｘｎ，Ａ１，…，Ａｔ
が、線形符号Ｃの情報ビットを形成するように決定される。したがって、例えば、ｔ＝１とすることができ、
Ａ１＝ａ１＋ａ２＋…＋ａｒ
に従って定義されるＡ１が、アドレスビットのパリティである。
【０２６０】
次に、いくつかの実施形態のさらなる態様を、ＢＣＨ符号に関して論じる。
【０２６１】
１ビットおよび２ビット誤りを訂正することができる（１５，７）ＢＣＨ符号ＣのＨ行列は、Ｈ行列Ｈ
【数１９８】
0005923631.tif 000200
である（（非特許文献１）参照）。
【０２６２】
変数ｙ１，…，ｙ１５が、左から右へのＨ行列の列に割り振られる。
【０２６３】
このＢＣＨ符号ＣのＨ行列の各行は、６個、８個、または１２個の「１」を含み、したがって偶数個の「１」を含むので、
【数１９９】
0005923631.tif 000201
が符号Ｃのコードワードであり、ビットｄ１，…，ｄ１５としてメモリに直接または反転させて書き込むことができる全てのビットの集合
【数２００】
0005923631.tif 000202
を形成することができる。式（１０）のＨ行列が８行を有するので、ＢＣＨ符号は、８個のチェックビットと、７個の情報ビットとを有する。ｙ１５＝ｂｆ１が定数値として選択される場合、６個のペイロードデータビットを記憶することができる。誤りであり得るビット
【数２０１】
0005923631.tif 000203
をメモリから読み出した後、１ビットおよび２ビット誤りをＢＣＨ符号によって訂正することができる。例えば、
【数２０２】
0005923631.tif 000204
が誤りである場合、
【数２０３】
0005923631.tif 000205
は、さらなるビットが誤りである場合でさえ、訂正値
【数２０４】
0005923631.tif 000206
に訂正される。
【０２６４】
いくつかの実施形態は、メモリに直接または反転されて書き込まれたビットの集合Ｙｉを識別するためにｔ個の定数値ｂｆ１，…，ｂｆｔ（ｔ＞１）が使用されるさらなる態様を実施することができる。メモリから読み出されている値
【数２０５】
0005923631.tif 000207
が、誤り訂正符号Ｃに従って訂正された後、定数値ｂｆ１，…，ｂｆｔに対応する訂正されたビットから、ビットグループＹｉのビットが反転されるべきか否かを決定することができる。これにより、Ｙｉのビットが反転されべきるか否かに関する言明の信頼性を高めることができる。
【０２６５】
例えば、ｔ＝３であり、符号Ｃは、符号距離５を有する２ビット誤り訂正符号でよい。部分集合Ｙｉの定数２進値ｂｆｉ１、ｂｆｉ２、ｂｆｉ３に関して、ｂｆｉ１＝ｂｆｉ２＝ｂｆｉ３＝０を適用することができる。１ビット誤りまたは２ビット誤りの場合、全ての１ビットおよび全ての２ビット誤りが符号Ｃによって訂正されるので、定数２進値が直接または反転されて記憶されているビット位置でのビット
【数２０６】
0005923631.tif 000208
全てが同じわけではないことがある。それにより、有利には、Ｙｉのビットがメモリに直接または反転されて書き込まれているかどうかの決定の信頼性が特に高くなる。
【０２６６】
以下、アドレスビットが符号化に含まれない一実施形態の後続の方法ステップを述べる。
【０２６７】
記憶すべきデータビットを提供し、それらのデータビットを定数２進値によって補完するステップ。
【０２６８】
誤り訂正符号Ｃを用いてデータビットおよび定数２進値を符号化するステップ。
【０２６９】
記憶すべきビットの部分集合のビットが反転されるべきかどうか判断するステップと、
ビット部分集合のビットが反転されるべきであるときには、部分集合のビットを反転させるステップと、
ビット部分集合のビットが反転されるべきでないときには、部分集合のビットを反転させないステップと
によって、記憶すべきビットを生成するステップ。
４．記憶すべきビットをメモリに書き込むステップ。
５．記憶されている、場合によってば誤りのビットをメモリから読み出すステップ。
６．読み出された、誤りであり得るビットを、誤り訂正符号Ｃを使用することによって訂正するステップ。ここで、生じている誤りが符号Ｃによって訂正可能である場合には、定数２進ビットが記憶されているビット位置と、データビットが記憶されている少なくとも１つのビット位置とが訂正される。
７．記憶されるビットの値を反転する、または反転しないステップ。ここで、定数値が記憶されているビット位置での訂正されたビットに基づいて、ビットの部分集合が反転されるべきか反転されないべきかが決定される。
【０２７０】
以下、アドレスビットが符号化に含まれるさらなる実施形態の後続の方法ステップを述べる。
【０２７１】
記憶すべきデータビットを提供し、それらのデータビットを定数２進値によって補完するステップ。
【０２７２】
誤り訂正符号Ｃを用いて、データビット、定数２進値、および書込みアドレスのアドレスビットを符号化するステップ。
【０２７３】
記憶すべきビットの部分集合のビットが反転されるべきかどうか判断するステップと、
ビット部分集合のビットが反転されるべきであるときには、部分集合のビットを反転させるステップと、
ビット部分集合のビットが反転されるべきでないときには、部分集合のビットを反転させないステップと
によって、記憶すべきビットを生成するステップであって、アドレスビットが、記憶すべきビットに属さないステップ。
４．符号化に含まれる書込みアドレスで、記憶すべきビットをメモリに書き込むステップ。
５．読出しアドレスで、記憶されている、場合によってば誤りのビットをメモリから読み出すステップ。
６．誤り訂正符号Ｃを使用することによって、読出しアドレスを考慮に入れて、読み出された、誤りであり得るビットを訂正するステップ。ここで、生じている誤りが符号Ｃによって訂正可能である場合には、定数２進ビットが記憶されているビット位置と、データビットが記憶されている少なくとも１つのビット位置とが訂正される。
７．記憶されるビットの値を反転する、または反転しないステップ。ここで、定数値が記憶されているビット位置での訂正されたビットに基づいて、ビットの部分集合が反転されるべきか反転されないべきかが決定される。
【０２７４】
以下に、いくつかの実施形態をまとめる。
【０２７５】
一実施形態によれば、ビットをメモリに記憶するための方法が提供され、ここで、ビットは、線形誤り訂正符号Ｃを用いて符号化され、線形誤り訂正符号Ｃは、少なくとも３の符号距離を有し、線形誤り訂正符号Ｃを用いて符号化されたビットの部分集合が直接書き込まれるか、それともビット毎に反転されてメモリに書き込まれるかが判断され、符号Ｃは、Ｈ行列Ｈを備え、ここで、
メモリに直接または反転されて書き込まれたビットの部分集合は、少なくとも１つの２進定数値を含み、この値は、ペイロードデータビットと共に、線形符号Ｃのコードワードを形成するためにコード化に使用され、ここで、それぞれのビット部分集合のビットがメモリに直接書き込まれるときには、２進定数値が２進値ｂｆとしてメモリに書き込まれ、それぞれのビット部分集合のビットが反転されてメモリに書き込まれるときには、２進値ｂｆが反転値
【数２０７】
0005923631.tif 000209
としてメモリに書き込まれ、
ここで、メモリに直接または反転されて書き込まれたビットの部分集合が反転されるときに、符号Ｃのコードワードが同じ符号のコードワードに変換され、符号のＨ行列は、メモリに直接または反転されて書き込まれたビットの部分集合に対応するＨ行列の行の各成分の「１」の数が偶数であるように生成され、
２．メモリからの読出し時に、線形誤り訂正符号Ｃを使用することによって、メモリから読み出された、誤りであり得るビットが訂正され、ここで、それぞれのビット部分集合がメモリに直接書き込まれているときには、少なくとも、定数２進値ｂｆが書き込まれているビット位置にあるビットが訂正され、または、それぞれのビット部分集合がメモリに反転されて書き込まれているときには、少なくとも、定数２進値
【数２０８】
0005923631.tif 000210
が書き込まれているビット位置にあるビットが訂正され、
３．読出し後、定数値ｂｆまたは反転された定数値
【数２０９】
0005923631.tif 000211
が記憶されているビット位置から読み出されている訂正された値が
【数２１０】
0005923631.tif 000212
であるときには、メモリに直接または反転されて書き込まれているビット部分集合のビットが反転され、この値がｂｆであるときには反転されない。
【０２７６】
一実施形態によれば、メモリは、レジスタである。
【０２７７】
別の実施形態によれば、メモリは、レジスタアレイである。
【０２７８】
さらなる実施形態によれば、メモリは、アドレス可能なメモリである。
【０２７９】
一実施形態では、誤り訂正符号Ｃを用いて符号化されたビットは、アドレスビットを使用することによって符号化される。
【０２８０】
一実施形態によれば、メモリに直接または反転されて書き込まれるビット部分集合のうちの１つのビット部分集合内の「０」の数または「１」の数が、その部分集合がメモリに直接書き込まれるか、それとも反転されて書き込まれるかを決定する。
【０２８１】
一実施形態では、直接書き込み、次いで読み出し、書込み値と読出し値とを比較した後に、誤りが生じていないときには、ビットの部分集合は、メモリに直接書き込まれる。
【０２８２】
一実施形態によれば、直接書き込み、次いで読み出し、書込み値と読出し値とを比較した後に、せいぜいＴ（Ｔは、符号Ｃによって訂正することができる誤りの数よりも小さい）個の誤りが生じているときには、ビットの部分集合は、メモリに直接書き込まれる。
【０２８３】
一実施形態では、反転させて書き込み、次いで読み出し、書込み値と読出し値とを比較した後に、直接書き込み、次いで読出し値と書込み値とを比較した後に生じるのとせいぜい同数の誤りが生じているときには、ビットの部分集合は、メモリに反転されて書き込まれる。
【０２８４】
一実施形態によれば、反転させて書き込み、次いで読み出し、書込み値と読出し値とを比較した後に、せいぜいＴ（Ｔは、符号Ｃによって訂正することができる誤りの数よりも小さい）個の誤りが生じているときには、ビットの部分集合は、反転されてメモリに書き込まれる。
【０２８５】
さらに、別の実施形態によれば、さらなる方法が提供される。この方法は、以下のステップを含む。
【０２８６】
アドレス可能なメモリにアドレスａで記憶されるペイロードデータビットｘ１，…，ｘｎを、定数値を有するｌ（ｌ≧１）個のビットｂｆ１，…，ｂｆｌによって補完するステップ。
【０２８７】
アドレスビットから導出されるビットがコードワードの形成に含まれないときには、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて、定数値を有するビットｂｆ１，…，ｂｆｌおよびペイロードデータビットｘ１，…，ｘｎをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎに符号化するステップ。ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎから決定されるチェックビットである。さらに、アドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが符号化に含まれるときには、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて、ビットｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋにコード化するステップ。ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋから決定されるチェックビットであり、Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）は、アドレスビットから関数ｆ：｛０，１｝ｒ→｛０，１｝ｋによって一意に決定される。
【０２８８】
直接または反転されて記憶されるビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎのＫ（Ｋ≧１）個のビットグループＹ１，…，Ｙｋを定義するステップ。それにより、所定のビットｂｆ１，…，ｂｆｌの部分集合が、これらのグループそれぞれに一意に割り振られる。
【０２８９】
グループＹ１，…，Ｙｋのうちのどのビットグループが、メモリに反転されてまたは反転されずに記憶されるかを選択するステップ。
【０２９０】
メモリにアドレスａでビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎを書き込むステップ。ここで、反転されてメモリに書き込まれるビットのグループに属するビットは、書込み前に反転され、反転されるビットを含むグループに属さないビットは、直接、すなわち反転されずにメモリに書き込まれる。
【０２９１】
メモリにアドレスａで記憶されているビットを読み出すステップ。
【０２９２】
アドレスビットから導出されるビットがコードワードの形成に含まれない場合には、ステップ８に進む。アドレスビットから導出されるビットがコードワードの形成に含まれる場合には、ステップ１０に進む。
【０２９３】
同じアドレスに書き込まれた値とは誤りにより異なることがある、メモリから読み出されたビットを、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、誤り訂正符号Ｃに基づいて訂正するステップ。
【０２９４】
ステップ１１に進む。
【０２９５】
メモリから読み出された、誤りであり得る値を、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、誤り訂正符号Ｃに基づいて、誤りであり得るアドレスビットから導出されるやはり誤りであり得るビット
【数２１１】
0005923631.tif 000213
も使用することによって訂正するステップ。
【０２９６】
それぞれのビットグループに一意に割り当てられた符号Ｃを使用することによって訂正された読み出された定数値から、どのビットグループがメモリに直接または反転されて書き込まれているかを決定するステップ。
【０２９７】
前のステップで書込み中に反転されているビットを含むビットグループと判断されているビットグループの読み出されて訂正されたビットを反転するステップ。
【０２９８】
方法が終了する。
【０２９９】
さらに、別の実施形態によれば、少なくとも１ビット誤りを訂正する線形符号Ｃのコードワードを形成するビットの部分集合をメモリセルのメモリに直接または反転させて書き込むため、および、メモリに書き込まれているビットを読み出し、直接または反転されて記憶されていた、メモリから誤り状態で読み出されていることがあるビットから、元のビットを回復するための方法が提供され、この方法は、以下のステップを含む。
【０３００】
メモリに直接または反転させて書き込むことができる、少なくとも１ビット誤りを訂正する線形符号Ｃを用いて符号化されたビットの部分集合の数Ｋ（Ｋ≧１）を定義するステップ。
【０３０１】
アドレスａ＝ａ１，…，ａｒ（ｒ≧２）で、少なくとも１ビット誤りを訂正する線形系統的符号のコードワードのサブワードとして記憶されるｎ個のペイロードデータビットｘ１，…，ｘｎを提供するステップ。
【０３０２】
符号Ｃの情報ビットｕ１，…，ｕＮを生成するステップ。ここで、アドレスａが符号Ｃのコードワードの形成に含まれない場合には、データビットｘ１，…，ｘｎは、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、
ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
が成り立ち、ここで、Ｎ＝ｌ＋ｎであり、アドレスａが符号Ｃのコードワードの形成に含まれる場合には、データビットｘ１，…，ｘｎ、およびアドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、
ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋ
が成り立ち、ここで、Ｎ＝ｌ＋ｎ＋ｋであり、ここで、
Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）
は、ｒ個のアドレスビットａ１，…，ａｒの値から関数ｆによって一意に決定される２進値であり、ｌ≧１および１≦ｋ≦ｒである。
【０３０３】
４．アドレスａが誤り検出または誤り訂正に含まれない場合には、方法はステップ５に進み、アドレスａが誤り検出または誤り訂正に含まれる場合には、方法はステップ１６に進む。
【０３０４】
５．符号Ｃのコードワードｙ，…，ｙＰを生成するステップ。ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、
ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
が成り立ち、ｃ１，…，ｃｍは、ｍ個のチェックビットであり、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、Ｐ＝ｎ＋ｍ＋ｌ、ｍ＝Ｐ−Ｎ、Ｎ＝ｎ＋ｌ、およびｍ＝Ｐ−Ｎが成り立つ。
【０３０５】
６．ビット
ｙ１，…，ｙＰ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ
のＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するステップ。それにより、以下のことが成り立つ。
第１の所定の値を有するビットまたは複数のビットｂｆ１，…，ｂｆｌが、各部分集合Ｙ１，…，Ｙｋに１対１で割り当てられる。
【数２１２】
0005923631.tif 000214
がビットｙ１，…，ｙＰの２進値である場合、ｊ＝１，…，Ｐおよびあらゆる部分集合Ｙｑ（Ｋ≧ｑ≧１）に関して、ｙｊが部分集合Ｙｑの要素である場合には、
【数２１３】
0005923631.tif 000215
であり、ｙｊが部分集合Ｙｑの要素でない場合には、
【数２１４】
0005923631.tif 000216
であるとき、
【数２１５】
0005923631.tif 000217
は符号Ｃのコードワードである。
【０３０６】
７．ビットグループＹ１，…，Ｙｋのうちのどのグループがメモリに直接または反転されて書き込まれるかを定義するステップ。
【０３０７】
８．メモリに書き込まれるＰ個のビットｄ１，…，ｄＰを生成するステップ。ここで、ｉ＝１，…，Ｐに関して、以下のことが成り立つ。
ｙｉが、反転されてメモリに書き込まれるビットを含むグループに属するときには、
【数２１６】
0005923631.tif 000218
であり、ｙｉが、反転されてメモリに書き込まれるビットを含むグループに属さないときには、ｄｉ＝ｙｉである。
【０３０８】
９．メモリにアドレスａでビットｄ１，…，ｄＰを書き込むステップ。
【０３０９】
読出し：
１０．アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数２１７】
0005923631.tif 000219
を読み出すステップ。これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄＰから、生じ得る誤りに起因して生じている。
【０３１０】
１１．符号Ｃによって訂正すべきＬ個のビット位置ｋ１，…，ｋＬを定義するステップ。ここで、ｌ≦Ｐおよび｛ｋ１，…，ｋＬ｝⊆｛１，…，Ｐ｝であり、これらのビット位置ｋ１，…，ｋＬは、値が誤りである場合には符号Ｃを使用することによって訂正され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属する。
【０３１１】
１２．符号Ｃによって訂正可能な誤りに関して、符号Ｃに基づいて訂正すべき所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数２１８】
0005923631.tif 000220
を決定するステップ。
【０３１２】
１３．少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数２１９】
0005923631.tif 000221
を生成するステップ。ここで、ｏｐは、一意に可逆のブール演算である。
【０３１３】
１４．既知の挿入された値ｂｆ１，…，ｂｆｌと、符号Ｃを使用することによって訂正されたそれぞれの読出し値とに基づいて、どのグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するステップ。
【０３１４】
１５．
【数２２０】
0005923631.tif 000222
が、メモリへの書込み中にメモリに直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数２２１】
0005923631.tif 000223
を出力し、
【数２２２】
0005923631.tif 000224
が、メモリへの書込み中にメモリに反転されて書き込まれているビットのグループに属する場合には、ビット
【数２２３】
0005923631.tif 000225
を出力するステップ。ここで、「ｏｐ」は、２項の一意に可逆のブール演算である。方法が終了する。
【０３１５】
１６．符号Ｃのコードワードｙ＝ｙ１，…，ｙＰを生成するステップ。ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、
ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）・Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋ
が成り立ち、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、Ｐ＝ｎ＋ｌ＋ｍ＋ｋ、Ｎ＝ｎ＋ｌ＋ｋであり、ｃ１，…，ｃｍは、ｍ＝Ｐ−Ｎ個のチェックビットである。
【０３１６】
１７．ビット
ｙ１，…，ｙｎ＋ｌ＋ｍ＝ｃ１，…，ｃｍ，ｂｆ１，ｘ１，…，ｘｎ
のＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するステップ。それにより、以下のことが成り立つ。
第１の所定の値を有するビットまたは複数のビットｂｆ１，…，ｂｆｌが、各部分集合Ｙ１，…，Ｙｋに１対１で割り当てられる。
【数２２４】
0005923631.tif 000226
がビットｙ１，…，ｙＰの２進値である場合、ｊ＝１，…，Ｐおよびあらゆる部分集合Ｙｑ（Ｋ≧ｑ≧１）に関して、
【数２２５】
0005923631.tif 000227
が部分集合Ｙｑの要素である場合には、
【数２２６】
0005923631.tif 000228
であり、
【数２２７】
0005923631.tif 000229
が部分集合Ｙｑの要素でない場合には、
【数２２８】
0005923631.tif 000230
であるとき、
【数２２９】
0005923631.tif 000231
は符号Ｃのコードワードである。
【０３１７】
１８．どのビットグループＹ１，…，Ｙｋがメモリに直接または反転されて書き込まれるかを定義するステップ。
【０３１８】
１９．メモリに書き込まれるＰ−ｋ個のビットｄ１，…，ｄｍ＋ｌ＋ｎを生成するステップ。ここで、ｉ＝１，…，ｍ＋ｎ＋ｌに関して、以下のことが成り立つ。
ｙｉが、メモリに直接書き込まれるビットを含むグループに属するときには、ｄｉ＝ｙｉであり、
ｙｉが、メモリに反転されて書き込まれるビットを含むグループに属するときには、
【数２３０】
0005923631.tif 000232
である。
【０３１９】
２０．メモリにアドレスａでビットｄ１，…，ｄｍ＋ｎ＋ｌを書き込むステップ。
【０３２０】
読み出し：
２１．アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数２３１】
0005923631.tif 000233
を読み出すステップ。これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄｎ＋ｍ＋ｌから、生じ得る誤りに起因して生じている。
【０３２１】
２２．符号Ｃによって訂正すべきＬ個のビット位置ｋ１，…，ｋＬを定義するステップ。ここで、ｌ≦Ｐ−ｋおよび｛ｋ１，…，ｋＬ｝⊆｛１，…，ｎ＋ｍ＋ｌ｝であり、これらのビット位置ｋ１，…，ｋＬは、値が誤りである場合には符号Ｃを使用することによって訂正され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属する。
【０３２２】
２３．符号Ｃによって訂正可能な誤りに関して、所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数２３２】
0005923631.tif 000234
を決定するステップ。
【０３２３】
２４．少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数２３３】
0005923631.tif 000235
を生成するステップ。ここで、「ｏｐ」は、２進の一意に可逆の演算である。
【０３２４】
２５．既知の値ｂｆ１，…，ｂｆｌと、読み出され、符号Ｃを使用することによって訂正された対応する値とに基づいて、どのビットグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するステップ。
【０３２５】
２６．
【数２３４】
0005923631.tif 000236
が、メモリへの書込み中にメモリに直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数２３５】
0005923631.tif 000237
を出力し、
【数２３６】
0005923631.tif 000238
が、メモリへの書込み中にメモリに反転されて書き込まれているビットのグループに属する場合には、ビット
【数２３７】
0005923631.tif 000239
を出力するステップ。ここで、「ｏｐ」は、２項の一意に可逆のブール演算である。方法が終了する。
【０３２６】
一実施形態によれば、メモリは、フラッシュメモリである。
【０３２７】
別の実施形態によれば、メモリは、Ｍ−ＲＡＭである。
【０３２８】
さらなる実施形態によれば、メモリは、Ｒ−ＲＡＭである。
【０３２９】
一実施形態では、系統的形態での符号Ｃの生成行列は、符号化を行う働きをする。
【０３３０】
別の実施形態によれば、符号Ｃは、ハミング符号または短縮ハミング符号である。
【０３３１】
別の実施形態では、符号Ｃは、Ｈｓｉａｏ符号または短縮Ｈｓｉａｏ符号である。
【０３３２】
さらなる実施形態によれば、符号Ｃは、ＢＣＨ符号または短縮ＢＣＨ符号である。
【０３３３】
別の実施形態では、ｋ＝ｒ、および（Ａ１，…，Ａｋ）＝（ａ１，…，ａｒ）が成り立つ。
【０３３４】
別の実施形態によれば、ｋ＝１、Ａ１＝ｆ（ａ１，…，ａｒ）＝ａ１＋ａ２＋…＋ａｒが成り立ち、Ａ１は、アドレスビットａ１，…，ａｒのパリティである。
【０３３５】
第１の態様によれば、装置は、処理ユニットと、メモリとを備え、処理ユニットは、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成され、ここで、複数の符号化ビットはそれぞれビット値を有し、線形誤り訂正符号は、少なくとも３の符号距離を有し、複数の符号化ビットは、線形誤り訂正符号の第１のコードワードを形成し、ここで、処理ユニットは、符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するように構成され、ここで、符号化ビットの部分集合は、部分集合の全てのビットが反転される場合に誤り訂正符号の第１のコードワードがその符号の第２のコードワードに変換されるように決定され、部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含み、または複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、符号化ビットの部分集合の符号化ビットは、指示ビットであり、指示ビットのビット値は、第１の所定のビット値に等しく、ここで、符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、処理ユニットは、記憶ワードとして、第１のコードワードのビットをメモリに記憶するように構成され、ここで、メモリに記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含み、符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、処理ユニットは、ビット値を変えることによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得するように構成され、さらに、記憶ワードとして、第２のコードワードをメモリに記憶するように構成され、ここで、第２のコードワードは、反転された指示ビットを含み、それにより、指示ビットのビット値は、第１の所定のビット値とは異なる第２の所定のビット値である。
【０３３６】
第１の態様を再び参照したときの第２の態様によれば、装置は回路である。
【０３３７】
第１の態様を再び参照したときの第３の態様によれば、符号化ビットの部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含む。
【０３３８】
第１の態様を再び参照したときの第４の態様によれば、符号化ビットの部分集合は、複数の符号化ビットのうちの全ての符号化ビットは含まない。
【０３３９】
第１の態様を再び参照したときの第５の態様によれば、第１の所定の値は、第１の定数２進値ｂｆであり、第２の所定の値は、第２の定数２進値
【数２３８】
0005923631.tif 000240
であり、処理ユニットは、記憶ワードをメモリから読み出すように構成され、処理ユニットは、記憶ワードを読み出した後、指示ビットが記憶されているメモリ内のビット位置から読み出されているビット値が第２の定数２進値
【数２３９】
0005923631.tif 000241
であるときには、メモリに直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、指示ビットが記憶されているメモリ内のビット位置から読み出されているビット値が第１の定数２進値ｂｆであるときには反転しないように構成される。
【０３４０】
第１の態様を再び参照したときの第６の態様によれば、第１の所定の値は、第１の定数２進値ｂｆであり、第２の所定の値は、第２の定数２進値
【数２４０】
0005923631.tif 000242
であり、処理ユニットは、記憶ワードをメモリから読み出すように構成され、処理ユニットは、１つまたは複数のビットが誤りである場合には、線形誤り訂正符号を使用することによって、記憶ワードの１つまたは複数のビットを訂正するように構成され、ここで、少なくとも、指示ビットが書き込まれているビット位置に記憶されているビットが、前記ビットが誤りである場合に訂正され、処理ユニットは、記憶ワードを読み出した後、かつ１つまたは複数のビットを訂正した後、指示ビットが記憶されているメモリ内のビット位置から読み出されているビット値が第２の定数２進値
【数２４１】
0005923631.tif 000243
であるときには、メモリに直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、指示ビットが記憶されているメモリ内のビット位置から読み出されているビット値が第１の定数２進値ｂｆであるときには反転しないように構成される。
【０３４１】
第１の態様を再び参照したときの第７の態様によれば、線形誤り訂正符号は、パリティチェック行列Ｈを含み、パリティチェック行列Ｈの行の各成分の「１」の数は偶数である。
【０３４２】
第１の態様を再び参照したときの第８の態様によれば、メモリは、レジスタ、レジスタアレイ、またはアドレス可能なメモリである。
【０３４３】
第１の態様を再び参照したときの第９の態様によれば、メモリは、アドレス可能なメモリであり、処理ユニットは、線形誤り訂正符号を採用することによって、かつアドレスビットを使用することによって、複数のビットを符号化して複数の符号化ビットを取得するように構成される。
【０３４４】
第１の態様を再び参照したときの第１０の態様によれば、処理ユニットは、符号化ビットの部分集合の「０」の数または符号化ビットの部分集合の「１」の数に応じて反転指定を特定するように構成される。
【０３４５】
第１の態様を再び参照したときの第１１の態様によれば、書込み値をメモリに書き込んだ後、次いで書込み値をメモリから読み出して読出し値を取得した後、さらに、書込み値と読み出された書込み値とを比較した後に、誤りが生じていないときには、処理ユニットは、符号化ビットの部分集合が反転されるべきでないことを示す反転指定を特定するように構成される。
【０３４６】
第１の態様を再び参照したときの第１２の態様によれば、書込み値をメモリに書き込んだ後、次いで書込み値をメモリから読み出して読出し値を取得した後、さらに、書込み値と読み出された書込み値とを比較した後に、せいぜいＴ（Ｔは、線形誤り訂正符号によって訂正することができる誤りの数よりも小さい）個の誤りが生じているときには、処理ユニットは、符号化ビットの部分集合が反転されるべきでないことを示す反転指定を特定するように構成される。
【０３４７】
第１の態様を再び参照したときの第１３の態様によれば、ビット部分集合の反転された書込み値をメモリに書き込んだ後、次いで書き込まれている反転されている書込み値をメモリから読み出して読出し値を取得した後、さらに、書き込まれている反転されている書込み値と読み出された反転されている書込み値とを比較した後に、直接書き込み、次いで読出し値と書き込まれた反転されていない値とを比較した後に生じるのとせいぜい同数の誤りが生じているときには、処理ユニットは、符号化ビットの部分集合が反転されるべきであることを示す反転指定を特定するように構成される。
【０３４８】
第１の態様を再び参照したときの第１４の態様によれば、ビット部分集合の反転された書込み値をメモリに書き込んだ後、次いで書き込まれている反転されている書込み値をメモリから読み出して読出し値を取得した後、さらに、書き込まれている反転されている書込み値と読出し値とを比較した後に、せいぜいＴ（Ｔは、線形誤り訂正符号によって訂正することができる誤りの数よりも小さい）個の誤りが生じているときには、処理ユニットは、符号化ビットの部分集合が反転されるべきであることを示す反転指定を特定するように構成される。
【０３４９】
第１の態様を再び参照したときの第１５の態様によれば、メモリは、Ｆｌａｓｈメモリ、磁気ランダムアクセスメモリ（Ｍ−ＲＡＭ）、または抵抗性ランダムアクセスメモリ（Ｒ−ＲＡＭ）である。
【０３５０】
第１の態様を再び参照したときの第１６の態様によれば、誤り訂正符号は、生成行列を含み、処理ユニットは、符号化のために系統的形態での生成行列を使用することによって、複数のビットを符号化するように構成される。
【０３５１】
第１の態様を再び参照したときの第１７の態様によれば、線形誤り訂正符号は、ハミング符号または短縮ハミング符号である。
【０３５２】
第１の態様を再び参照したときの第１８の態様によれば、線形誤り訂正符号は、Ｈｓｉａｏ符号または短縮Ｈｓｉａｏ符号である。
【０３５３】
第１の態様を再び参照したときの第１９の態様によれば、線形誤り訂正符号は、ＢＣＨ符号または短縮ＢＣＨ符号である。
【０３５４】
第１の態様を再び参照したときの第２０の態様によれば、処理ユニットは、符号化ビットのさらなる部分集合に応じて、符号化ビットのさらなる部分集合が反転されるべきか否かを示すさらなる反転指定を特定するように構成される。
【０３５５】
第２１の態様によれば、装置は、処理ユニットと、メモリとを備え、処理ユニットは、メモリにアドレスａで記憶されるペイロードデータビットｘ１，…，ｘｎを、定数値を有するｌ（ここでｌ≧１）個のビットｂｆ１，…，ｂｆｌによって補完するように構成され、ここで、処理ユニットは、アドレスビットから導出されるビットがコードワードの形成に含まれないときには、少なくとも１ビット誤りを訂正する線形誤り訂正符号Ｃを用いて、定数値を有するビットｂｆ１，…，ｂｆｌおよびペイロードデータビットｘ１，…，ｘｎをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎに符号化するように構成され、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎから決定されるチェックビットであり、さらに、処理ユニットは、アドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが符号化に含まれるときには、少なくとも１ビット誤りを訂正する線形誤り訂正符号Ｃを用いて、ビットｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋにコード化するように構成され、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋから決定されるチェックビットであり、Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）は、アドレスビットから関数ｆ：｛０，１｝ｒ→｛０，１｝ｋによって一意に決定され、ここで、処理ユニットは、直接または反転されて記憶されるビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎのＫ（Ｋ≧１）個のビットグループＹ１，…，Ｙｋを定義するように構成され、それにより、所定のビットｂｆ１，…，ｂｆｌの部分集合が、これらのグループそれぞれに一意に割り当てられ、ここで、処理ユニットは、ビットグループＹ１，…，ＹＫを決定するように構成され、それにより、１グループＹｊ（ｊ＝１，…，Ｋ）の全てのビットが反転される場合には、線形誤り訂正符号Ｃの第１のコードワードが線形誤り訂正符号Ｃの第２のコードワードに変換され、処理ユニットは、グループＹ１，…，ＹＫのうちのどのビットグループが、反転されてまたは反転されずにメモリに記憶されるかを選択するように構成され、ここで、処理ユニットは、メモリにアドレスａでビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎを書き込むように構成され、ここで、メモリに反転されて書き込まれるビットのグループに属するビットは、書込み前に反転され、反転されるビットを含むグループに属さないビットは、反転されずにメモリに書き込まれ、ここで、処理ユニットは、メモリにアドレスａで記憶されているビットを読み出すように構成され、ここで、アドレスビットから導出されるビットがコードワードの形成に含まれない場合には、処理ユニットは、同じアドレスに書き込まれた値とは誤りにより異なることがある、メモリから読み出されたビットを、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、線形誤り訂正符号Ｃに基づいて訂正するように構成され、アドレスビットから導出されるビットがコードワードの形成に含まれる場合には、処理ユニットは、メモリから読み出された、誤りであり得る値を、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、線形誤り訂正符号Ｃに基づいて、誤りであり得るアドレスビットから導出されるやはり誤りであり得るビット
【数２４２】
0005923631.tif 000244
も使用することによって訂正するように構成され、処理ユニットは、それぞれのビットグループに一意に割り当てられた線形誤り訂正符号Ｃを使用することによって訂正された読み出された定数値から、どのビットグループがメモリに直接または反転されて書き込まれているかを決定するように構成され、処理ユニットは、前のステップで書込み中に反転されているビットを含むビットグループと判断されているビットグループの読み出されて訂正されたビットを反転するように構成される。
【０３５６】
第２１の態様を再び参照したときの第２２の態様によれば、ｋ＝ｒ、および（Ａ１，…，Ａｋ）＝（ａ１，…，ａｒ）が成り立つ。
【０３５７】
第２１の態様を再び参照したときの第２３の態様によれば、ｋ＝１、Ａ１＝ｆ（ａ１，…，ａｒ）＝ａ１＋ａ２＋…＋ａｒが成り立ち、Ａ１は、アドレスビットａ１，…，ａｒのパリティである。
【０３５８】
第２４の態様によれば、ビットをメモリに記憶するための装置であって、ビットが線形誤り訂正符号Ｃを用いて符号化され、線形誤り訂正符号Ｃが、少なくとも３の符号距離を有し、線形誤り訂正符号Ｃを用いて符号化されたビットの部分集合がメモリに直接書き込まれるか、それともビット毎に反転されて書き込まれるかが判断され、符号Ｃが、Ｈ行列Ｈを備える装置が、処理ユニットと、メモリとを備え、ここで、メモリに直接または反転されて書き込まれたビットの部分集合は、少なくとも１つの２進定数値を含み、この値は、データビットと共に、線形誤り訂正符号Ｃのコードワードを形成するためにコード化に使用され、処理ユニットは、それぞれのビット部分集合のビットがメモリに直接書き込まれるときに、２進定数値を２進値ｂｆとしてメモリに書き込むように構成され、処理ユニットは、それぞれのビット部分集合のビットがメモリに反転されて書き込まれるときに、２進定数値を反転値
【数２４３】
0005923631.tif 000245
としてメモリに書き込むように構成され、処理ユニットは、メモリに直接または反転されて書き込まれたビットの部分集合が反転されるときに、線形誤り訂正符号Ｃのコードワードを同じ符号のコードワードに変換するように構成され、線形誤り訂正符号ＣのＨ行列は、メモリに直接または反転されて書き込まれたビットの部分集合に対応するＨ行列の行の各成分の「１」の数が偶数であるように生成され、処理ユニットは、メモリからの読出し時に、メモリから読み出された、誤りであり得るビットを、線形誤り訂正符号Ｃを使用することによって訂正するように構成され、ここで、それぞれのビット部分集合がメモリに直接書き込まれているときには、少なくとも、定数２進値ｂｆが書き込まれているビット位置にあるビットが訂正され、または、それぞれのビット部分集合がメモリに反転されて書き込まれているときには、少なくとも、定数２進値
【数２４４】
0005923631.tif 000246
が書き込まれているビット位置にあるビットが訂正され、処理ユニットは、読出し後、定数値ｂｆまたは反転された定数値
【数２４５】
0005923631.tif 000247
が記憶されているビット位置から読み出されている訂正された値が
【数２４６】
0005923631.tif 000248
であるときには、メモリに直接または反転されて書き込まれているビット部分集合のビットを反転するように構成され、この値がｂｆであるときには反転しないように構成される。
【０３５９】
第２５の態様によれば、方法が、エンコーダを使用して、線形誤り訂正符号を採用することによって、複数のビットを符号化して複数の符号化ビットを取得するステップを含み、ここで、複数の符号化ビットはそれぞれビット値を有し、線形誤り訂正符号は、少なくとも３の符号距離を有し、複数の符号化ビットは、線形誤り訂正符号の第１のコードワードを形成し、方法はさらに、処理ユニットを使用して、符号化ビットの部分集合に応じて、符号化ビットの部分集合が反転されるべきか否かを示す反転指定を特定するステップを含み、ここで、符号化ビットの部分集合は、部分集合の全てのビットが反転される場合に線形誤り訂正符号の第１のコードワードがその符号の第２のコードワードに変換されるように決定され、部分集合は、複数の符号化ビットのうちの全ての符号化ビットを含み、または複数の符号化ビットのうちの少なくとも３つの符号化ビットを含み、符号化ビットの部分集合のうちの１つの符号化ビットは、指示ビットであり、指示ビットのビット値は、第１の所定のビット値に等しく、方法はさらに、符号化ビットの部分集合が反転されるべきでないことを反転指定が示すときには、記憶ワードとして、第１のコードワードのビットをメモリに記憶するステップを含み、ここで、メモリに記憶される第１のコードワードのビットは、第１の所定のビット値を有する指示ビットを含み、符号化ビットの部分集合が反転されるべきであることを反転指定が示すときには、ビット値を変えることによって符号化ビットの部分集合の各符号化ビットを反転させることによって、線形誤り訂正符号の第１のコードワードを修正して線形誤り訂正符号の第２のコードワードを取得し、記憶ワードとして、第２のコードワードをメモリに記憶するステップを含み、ここで、第２のコードワードは、反転された指示ビットを含み、それにより、指示ビットのビット値は、第１の所定のビット値とは異なる第２の所定のビット値である。
【０３６０】
第２６の態様によれば、方法は、アドレス可能なメモリにアドレスａで記憶されるペイロードデータビットｘ１，…，ｘｎを、定数値を有するｌ（ｌ≧１）個のビットｂｆ１，…，ｂｆｌによって補完するステップを含み、方法はさらに、エンコーダによって、アドレスビットから導出されるビットがコードワードの形成に含まれないときには、少なくとも１ビット誤りを訂正する線形誤り訂正符号Ｃを用いて、定数値を有するビットｂｆ１，…，ｂｆｌおよびペイロードデータビットｘ１，…，ｘｎをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎに符号化するステップを含み、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎから決定されるチェックビットであり、方法はさらに、アドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが符号化に含まれるときには、少なくとも１ビット誤りを訂正する線形誤り訂正符号Ｃを用いて、ビットｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋをコードワードｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋにコード化するステップを含み、ここで、ｃ１，…，ｃｍは、ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋから決定されるチェックビットであり、Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）は、アドレスビットから関数ｆ：｛０，１｝ｒ→｛０，１｝ｋによって明瞭に決定され、方法はさらに、処理ユニットを使用して、直接または反転されて記憶されるビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎのＫ（Ｋ≧１）個のビットグループＹ１，…，Ｙｋを定義するステップを含み、それにより、所定のビットｂｆ１，…，ｂｆｌの部分集合が、これらのグループそれぞれに一意に割り振られ、それにより、ビットグループのビットが反転される場合に、線形誤り訂正符号Ｃの第１のコードワードが線形誤り訂正符号Ｃの第２のコードワードに変換され、方法はさらに、処理ユニットを使用して、グループＹ１，…，Ｙｋのうちのどのビットグループが、反転されてまたは反転されずにメモリに記憶されるかを選択するステップを含み、方法はさらに、処理ユニットを使用して、メモリにアドレスａでビットｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎを書き込むステップを含み、ここで、反転されてメモリに書き込まれるビットのグループに属するビットは、書込み前に反転され、反転されるビットを含むグループに属さないビットは、直接、すなわち反転されずにメモリに書き込まれ、方法はさらに、処理ユニットを使用して、メモリにアドレスａで記憶されているビットを読み出すステップを含み、アドレスビットから導出されるビットがコードワードの形成に含まれない場合には、ｈ）に進み、アドレスビットから導出されるビットがコードワードの形成に含まれる場合には、ｊ）に進み、方法はさらに、処理ユニットを使用して、同じアドレスに書き込まれた値とは誤りにより異なることがある、メモリから読み出されたビットを、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、誤り訂正符号Ｃに基づいて訂正するステップを含み、ｋ）に進み、方法はさらに、処理ユニットを使用して、メモリから読み出された、誤りであり得る値を、少なくとも定数値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、線形誤り訂正符号Ｃに基づいて、誤りであり得るアドレスビットから導出されるやはり誤りであり得るビット
【数２４７】
0005923631.tif 000249
も使用することによって訂正するステップを含み、方法はさらに、処理ユニットを使用して、それぞれのビットグループに一意に割り当てられた線形誤り訂正符号Ｃを使用することによって訂正された読み出された定数値から、どのビットグループがメモリに直接または反転されて書き込まれているかを決定するステップを含み、方法はさらに、処理ユニットを使用して、前のステップで書込み中に反転されているビットを含むビットグループと判断されているビットグループの読み出されて訂正されたビットを反転するステップを含む。
【０３６１】
第２７の態様によれば、少なくとも１ビット誤りを訂正する線形誤り訂正符号Ｃのコードワードを形成するビットの部分集合をメモリセルのメモリに直接または反転させて書き込むため、および、メモリに書き込まれているビットを読み出し、直接または反転されて記憶されていた、メモリから誤り状態で読み出されていることがあるビットから、元のビットを回復するための方法が、処理ユニットを使用して、メモリに直接または反転させて書き込むことができる、少なくとも１ビット誤りを訂正する線形誤り訂正符号Ｃを用いて符号化されたビットの部分集合の数Ｋ（Ｋ≧１）を定義するステップを含み、方法はさらに、処理ユニットを使用して、アドレスａ＝ａ１，…，ａｒ（ｒ≧２）で、少なくとも１ビット誤りを訂正する線形系統的符号のコードワードのサブワードとして記憶されるｎ個のペイロードデータビットｘ１，…，ｘｎを提供するステップを含み、方法はさらに、処理ユニットを使用して、線形誤り訂正符号Ｃの情報ビットｕ１，…，ｕＮを生成するステップを含み、ここで、アドレスａが線形誤り訂正符号Ｃのコードワードの形成に含まれない場合には、データビットｘ１，…，ｘｎは、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎが成り立ち、ここで、Ｎ＝ｌ＋ｎであり、アドレスａが線形誤り訂正符号Ｃのコードワードの形成に含まれる場合には、データビットｘ１，…，ｘｎ、およびアドレスビットａ１，…，ａｒから導出されるビットＡ１，…，Ａｋが、ｌ個の所定の２進値ｂｆ１，…，ｂｆｌによって補完され、それにより、ｕ１，…，ｕＮ＝ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋが成り立ち、ここで、Ｎ＝ｌ＋ｎ＋ｋであり、ここで、Ａ１，…，Ａｋ＝ｆ（ａ１，…，ａｒ）は、ｒ個のアドレスビットａ１，…，ａｒの値から関数ｆによって一意に決定される２進値であり、ｌ≧１および１≦ｋ≦ｒであり、ｄ）アドレスａが誤り検出または誤り訂正に含まれない場合には、方法はステップｅ）に進み、アドレスａが誤り検出または誤り訂正に含まれる場合には、方法はステップｐ）に進み、方法はさらに、ｅ）処理ユニットを使用して、線形誤り訂正符号Ｃのコードワードｙ１，…，ｙＰを生成するステップを含み、ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎが成り立ち、ｃ１，…，ｃｍは、ｍ個のチェックビットであり、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、Ｐ＝ｎ＋ｍ＋ｌ、ｍ＝Ｐ−Ｎ、Ｎ＝ｎ＋ｌ、およびｍ＝Ｐ−Ｎが成り立ち、方法はさらに、ｆ）処理ユニットを使用して、ビットｙ１，…，ｙＰ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎのＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するステップを含み、それにより、以下のことが成り立つ：第１の所定の値を有するビットまたは複数のビットｂｆ１，…，ｂｆｌが、各部分集合Ｙ１，…，Ｙｋに１対１で割り当てられ、
【数２４８】
0005923631.tif 000250
がビットｙ１，…，ｙＰの２進値である場合、ｊ＝１，…，Ｐおよびあらゆる部分集合Ｙｑ（Ｋ≧ｑ≧１）に関して、ｙｊが部分集合Ｙｑの要素である場合には、
【数２４９】
0005923631.tif 000251
であり、ｙｊが部分集合Ｙｑの要素でない場合には、
【数２５０】
0005923631.tif 000252
であるとき、
【数２５１】
0005923631.tif 000253
は線形誤り訂正符号Ｃのコードワードである；方法はさらに、ｇ）処理ユニットを使用して、ビットグループＹ１，…，Ｙｋのうちのどのグループがメモリに直接または反転されて書き込まれるかを定義するステップを含み、方法はさらに、ｈ）処理ユニットを使用して、メモリに書き込まれるＰ個のビットｄ１，…，ｄＰを生成するステップを含み、ここで、ｉ＝１，…，Ｐに関して、以下のことが成り立つ：ｙｉが、反転されてメモリに書き込まれるビットを含むグループに属するときには、
【数２５２】
0005923631.tif 000254
であり、ｙｉが、反転されてメモリに書き込まれるビットを含むグループに属さないときには、ｄｉ＝ｙｉである；方法はさらに、処理ユニットを使用して、メモリにアドレスａでビットｄ１，…，ｄＰを書き込むステップを含み、方法はさらに読出しを行い、方法はさらに、処理ユニットを使用して、アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数２５３】
0005923631.tif 000255
を読み出すステップを含み、これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄＰから、生じ得る誤りに起因して生じており、方法はさらに、処理ユニットを使用して、線形誤り訂正符号Ｃによって訂正すべきＬ個のビット位置ｋ１，…，ｋＬを定義するステップを含み、ここで、ｌ≦Ｐおよび｛ｋ１，…，ｋＬ｝⊆｛１，…，Ｐ｝であり、これらのビット位置ｋ１，…，ｋＬは、値が誤りである場合には線形誤り訂正符号Ｃを使用することによって訂正され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属し、方法はさらに、処理ユニットを使用して、線形誤り訂正符号Ｃによって訂正可能な誤りに関して、線形誤り訂正符号Ｃに基づいて訂正すべき所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数２５４】
0005923631.tif 000256
を決定するステップを含み、方法はさらに、処理ユニットを使用して、少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数２５５】
0005923631.tif 000257
を生成するステップを含み、ここで、ｏｐは、一意に可逆のブール演算であり、方法はさらに、処理ユニットを使用して、既知の挿入された値ｂｆ１，…，ｂｆｌと、線形誤り訂正符号Ｃを使用することによって訂正されたそれぞれの読出し値とに基づいて、どのグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するステップを含み、方法はさらに、
【数２５６】
0005923631.tif 000258
が、メモリへの書込み中にメモリに直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数２５７】
0005923631.tif 000259
を出力し、
【数２５８】
0005923631.tif 000260
が、メモリへの書込み中にメモリに反転されて書き込まれているビットのグループに属する場合には、ビット
【数２５９】
0005923631.tif 000261
を出力するステップを含み、ここで、「ｏｐ」は、２項の一意に可逆のブール演算であり、方法が終了し、方法はさらに、処理ユニットを使用して、線形誤り訂正符号Ｃのコードワードｙ＝ｙ１，…，ｙＰを生成するステップを含み、ここで、Ｃは、系統的形態での生成行列Ｇと、Ｈ行列Ｈとを有する線形系統的符号であり、ここで、ｙ＝ｙ１，…，ｙＰ＝（ｕ１，…，ｕＮ）・Ｇ＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎ，Ａ１，…，Ａｋが成り立ち、生成行列Ｇは、（Ｎ，Ｐ）行列であり、Ｈ行列Ｈ＝（ｈ１，…，ｈＰ）は、（［Ｐ−Ｎ］，Ｐ）行列であり、それにより、Ｈ行列の全ての列が、相異なり、０でなく、Ｐ＝ｎ＋ｌ＋ｍ＋ｋ、Ｎ＝ｎ＋ｌ＋ｋであり、ｃ１，…，ｃｍは、ｍ＝Ｐ−Ｎ個のチェックビットであり、方法はさらに、処理ユニットを使用して、ビットｙ１，…，ｙｎ＋ｌ＋ｍ＝＝ｃ１，…，ｃｍ，ｂｆ１，…，ｂｆｌ，ｘ１，…，ｘｎのＫ個の部分集合Ｙ１＝｛ｙ１，１，…，ｙ１，ｑ１｝，…，ＹＫ＝｛ｙＫ，１，…，ｙＫ，ｑＫ｝を決定するステップを含み、それにより、以下のことが成り立つ：第１の所定の値を有するビットまたは複数のビットｂｆ１，…，ｂｆｌが、各部分集合Ｙ１，…，Ｙｋに１対１で割り当てられ、
【数２６０】
0005923631.tif 000262
がビットｙ１，…，ｙＰの２進値である場合、ｊ＝１，…，Ｐおよびあらゆる部分集合Ｙｑ（Ｋ≧ｑ≧１）に関して
【数２６１】
0005923631.tif 000263
が部分集合Ｙｑの要素である場合には、
【数２６２】
0005923631.tif 000264
であり、
【数２６３】
0005923631.tif 000265
が部分集合Ｙｑの要素でない場合には、
【数２６４】
0005923631.tif 000266
であるとき、
【数２６５】
0005923631.tif 000267
は線形誤り訂正符号Ｃのコードワードである；方法はさらに、処理ユニットを使用して、どのビットグループＹ１，…，Ｙｋがメモリに直接または反転されて書き込まれるかを定義するステップを含み、方法はさらに、処理ユニットを使用して、メモリに書き込まれるＰ−ｋ個のビットｄ１，…，ｄｍ＋ｌ＋ｎを生成するステップを含み、ここで、ｉ＝１，…，ｍ＋ｎ＋ｌに関して、以下のことが成り立つ：ｙｉが、メモリに直接書き込まれるビットを含むグループに属するときには、ｄｉ＝ｙｉであり、ｙｉが、メモリに反転されて書き込まれるビットを含むグループに属するときには、
【数２６６】
0005923631.tif 000268
である；方法はさらに、処理ユニットを使用して、メモリにアドレスａでビットｄ１，…，ｄｍ＋ｎ＋ｌを書き込むステップを含み、方法はさらに読出しを行い、方法はさらに、処理ユニットを使用して、アドレスａを作成し、アドレスａに記憶されている誤りであり得る値
【数２６７】
0005923631.tif 000269
を読み出すステップを含み、これらの値は、アドレスａに書き込まれた値ｄ１，…，ｄｎ＋ｍ＋ｌから、生じ得る誤りに起因して生じており、方法はさらに、処理ユニットを使用して、線形誤り訂正符号Ｃによって訂正すべきＬ個のビット位置ｋ１，…，ｋＬを定義するステップを含み、ここで、ｌ≦Ｐ−ｋおよび｛ｋ１，…，ｋＬ｝⊆｛１，…，ｎ＋ｍ＋ｌ｝であり、これらのビット位置ｋ１，…，ｋＬは、値が誤りである場合には符号Ｃを使用することによって訂正され、ここで、ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置が、訂正すべきビット位置に属し、方法はさらに、処理ユニットを使用して、線形誤り訂正符号Ｃによって訂正可能な誤りに関して、所定のＬ個のビット位置ｋ１，…，ｋＬの２進訂正値
【数２６８】
0005923631.tif 000270
を決定するステップを含み、方法はさらに、処理ユニットを使用して、少なくとも値ｂｆ１，…，ｂｆｌが直接または反転されて記憶されているビット位置で、訂正されたビット
【数２６９】
0005923631.tif 000271
を生成するステップを含み、ここで、「ｏｐ」は、２進の一意に可逆の演算であり、方法はさらに、処理ユニットを使用して、既知の値ｂｆ１，…，ｂｆｌと、読み出され、線形誤り訂正符号Ｃを使用することによって訂正された対応する値とに基づいて、どのビットグループＹ１，…，Ｙｋに関してビットが直接または反転されて記憶されているかを判断するステップを含み、方法はさらに、
【数２７０】
0005923631.tif 000272
が、メモリへの書込み中にメモリに直接書き込まれているビットを含むビットグループに属する場合には、ビット
【数２７１】
0005923631.tif 000273
を出力し、
【数２７２】
0005923631.tif 000274
が、メモリへの書込み中にメモリに反転されて書き込まれているビットのグループに属する場合には、ビット
【数２７３】
0005923631.tif 000275
を出力するステップを含み、ここで、「ｏｐ」は、２項の一意に可逆のブール演算であり、方法が終了する。
【０３６２】
いくつかの態様を装置の文脈で述べてきたが、これらの態様が、対応する方法の説明でもあることは明らかである。ここで、ブロックまたはデバイスは、方法ステップまたは方法ステップの特徴に対応する。同様に、方法ステップの文脈で述べられる態様は、対応する装置の対応するユニット、要素、または特徴の説明でもある。
【０３６３】
本発明の分解された信号は、デジタル記憶媒体に記憶することができ、または、インターネットなど、無線伝送媒体や有線伝送媒体などの伝送媒体で伝送することができる。
【０３６４】
特定の実装要件に応じて、いくつかの実施形態は、ハードウェアまたはソフトウェアで実装することができる。実装は、それぞれの方法が実施されるようにプログラマブルコンピュータシステムと協働する（または協働可能である）、電子的に可読の制御信号が記憶されているデジタル記憶媒体、例えば、フロッピディスク、ＤＶＤ、ＣＤ、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、またはＦＬＡＳＨメモリを使用して行うことができる。
【０３６５】
いくつかの実施形態は、本明細書で述べる方法の１つが実施されるようにプログラマブルコンピュータシステムと協働することが可能な電子的に可読の制御信号を担持する非一時的なデータキャリアを含む。
【０３６６】
一般に、本発明のいくつかの実施形態は、プログラムコードを含むコンピュータプログラム製品として実装することができ、プログラムコードは、コンピュータプログラム製品がコンピュータ上で実行されるときに方法の１つを実施するように動作可能である。プログラムコードは、例えば機械可読キャリアに記憶することができる。
【０３６７】
他の実施形態は、機械可読キャリアに記憶された、本明細書で述べる方法の１つを実施するためのコンピュータプログラムを含む。
【０３６８】
すなわち、したがって本発明の方法の一実施形態は、コンピュータプログラムがコンピュータ上で実行されるときに本明細書で述べる方法の１つを実施するためのプログラムコードを有するコンピュータプログラムである。
【０３６９】
したがって、本発明の方法のさらなる実施形態は、本明細書で述べる方法の１つを実施するためのコンピュータプログラムを記録して含むデータキャリア（またはデジタル記憶媒体もしくはコンピュータ可読媒体）である。
【０３７０】
したがって、本発明の方法のさらなる実施形態は、本明細書で述べる方法の１つを実施するためのコンピュータプログラムを表すデータストリームまたは信号シーケンスである。データストリームまたは信号シーケンスは、例えば、データ通信接続を介して、例えばインターネットを介して伝送されるように構成することができる。
【０３７１】
さらなる実施形態は、本明細書で述べる方法の１つを実施するように構成または適合された処理手段、例えばコンピュータまたはプログラマブル論理回路を含む。
【０３７２】
さらなる実施形態は、本明細書で述べる方法の１つを実施するためのコンピュータプログラムをインストールしたコンピュータを含む。
【０３７３】
いくつかの実施形態では、プログラマブル論理デバイス（例えば、フィールドプログラマブルゲートアレイ）を使用して、本明細書で述べる方法の機能のいくつかまたは全てを実施することができる。いくつかの実施形態では、フィールドプログラマブルゲートアレイは、本明細書で述べる方法の１つを実施するためにマイクロプロセッサと協働することができる。一般に、方法は、任意のハードウェア装置によって実施される。
【０３７４】
本開示をいくつかの有利な実施形態に関して述べてきたが、本開示の範囲内での変更形態、置換形態、および均等物が存在する。また、本発明の方法および組成を実施する多くの代替方法が存在することにも留意すべきである。したがって、以下の添付の特許請求の範囲は、本発明の真の精神および範囲に入る全てのそのような変更形態、置換形態、および均等物を含むものと解釈されることが意図される。
【０３７５】
上述した実施形態は、本発明の原理に関する単なる例示にすぎない。本明細書で述べる構成および詳細の修正および変更が当業者には明らかであることを理解されたい。したがって、添付の特許請求の範囲によってのみ限定を与え、本明細書における実施形態の記述および説明によって表される具体的な詳細によっては限定を与えないことが意図される。
【０３７６】
各請求項は、ただ１つの請求項のみを引用するが、本発明は、想定可能な請求項の任意の組合せをも包含する。
【符号の説明】
【０３７７】
１１  コーダ
１２  ＸＯＲ回路
１３  メモリ
２１  シンドローム生成器
２２  復号器
２３  ＸＯＲ回路
２４  訂正器
２６  ＸＯＲ回路
３１  誤り検出器
４１  コーダ
４２  反転回路
４３  メモリ
５１  シンドローム生成器
５２  復号器
５３  ＸＯＲ回路
５４  訂正器
５５  インバータ
５７  誤り検出器
１１０  メモリ
１２０  処理ユニット
【図１】
0005923631.tif 000280
【図２】
0005923631.tif 000281
【図３】
0005923631.tif 000282
【図４】
0005923631.tif 000283
【図５】
0005923631.tif 000284
【図６】
0005923631.tif 000285