第1および第2の終端を有するチャネルであって、前記チャネルの前記第1の終端は送信器に結合され、前記チャネルは、シンボルの集合から選択されたシンボルを前記第1の終端から前記第2の終端に送信することが可能であり、前記チャネルは、不完全な誤り発生特性を示す、チャネルと、符号語の集合からなる符号であって、前記符号語の集合の元は、1つまたは複数の符号シンボルの長さであり、前記符号シンボルは前記シンボルの集合の要素である、符号とを備え、前記チャネルの誤り発生特性を考慮した前記符号語の集合の元同士の間の最小の変形ハミング隔たりは、前記符号語の集合の元同士の間の最小のハミング距離より大きい、システム。前記符号はさらにデータ語の集合と、前記データ語の集合の元と前記符号語の元との一対一の対応付けとを含み、前記データ語の集合の大きさは、前記符号語の集合の大きさと同じである、請求項1に記載のシステム。前記シンボルの集合の大きさが少なくとも3である請求項2に記載のシステム。前記シンボルの集合の大きさが少なくとも4である請求項2に記載のシステム。前記チャネルの前記第2の終端に結合された受信器であって、チャネル復調器およびチャネル復号器を備える受信器をさらに備え、前記送信器は、チャネル変調器およびソースデータ符号器を備え、前記チャネルの前記第1の終端が前記送信器に結合され、前記チャネルは通信チャネルであり、前記送信器は、データ語を受け取り、符号語を生成することにより前記符号を実装し、前記受信器は、前記チャネルからシンボルのグループを受信し、前記送信器に受け取られたデータ語に対応するデータ語を生成することにより前記符号を実装する、請求項2に記載のシステム。前記シンボルの集合の大きさが少なくとも3である請求項5に記載のシステム。前記シンボルの集合の大きさが少なくとも4である請求項5に記載のシステム。前記符号語の集合の元同士の間の最小の変形ハミング距離が4以上である請求項1に記載のシステム。前記符号語の集合の元同士の間の最小の変形ハミング距離が5以上である請求項1に記載のシステム。複数のメモリセルを含み、各メモリセルが、記憶されたシンボルの集合の元と一対一の対応関係にある複数の記憶状態を有する、少なくとも1つのメモリ装置であって、不完全な誤り発生特性を持つ誤り機構を有するメモリ装置と、前記少なくとも1つのメモリ装置に結合されて、前記記憶されたシンボルの集合から選択されたシンボルから導出されたデータを、前記少なくとも1つのメモリ装置の複数のメモリセルから読み出させるメモリコントローラと、前記メモリコントローラに結合されて、前記少なくとも1つのメモリ装置から読み出されたデータ中の誤りを訂正するチャネル復号器であって、前記誤りは、少なくとも部分的に前記誤り機構によって生じたものである、チャネル復号器とを含み、前記チャネル復号器は、符号語の集合からなる符号を復号し、前記少なくとも1つのメモリ装置の不完全な誤り発生特性を考慮した前記符号語の集合の元同士の間の最小の変形ハミング隔たりは、前記符号語の集合の元同士の間の最小のハミング距離より大きい、システム。前記シンボルの集合の大きさが少なくとも3である請求項10に記載のシステム。前記シンボルの集合の大きさが少なくとも4である請求項10に記載のシステム。チャネル符号器をさらに備え、前記チャネル符号器は、未符号化データを受け取り、そのデータを前記符号語の集合から選択された符号語の集まりに符号化するように構成され、前記符号語がその後前記少なくとも1つのメモリ装置内の前記複数のメモリセルに書き込まれる、請求項10に記載のシステム。前記シンボルの集合の大きさが少なくとも3である請求項13に記載のシステム。前記シンボルの集合の大きさが少なくとも4である請求項13に記載のシステム。前記符号語の集合の元同士の間の最小の変形ハミング距離が4以上である請求項10に記載のシステム。前記符号語の集合の元同士の間の最小の変形ハミング距離が5以上である請求項10に記載のシステム。半導体メモリ装置であって、各メモリセルが、記憶されたシンボルの集合の要素と一対一の対応関係にある複数の記憶状態を有する、複数のメモリセルであって、前記メモリ装置は、不完全な誤り発生特性を持つ誤り機構を有する、複数のメモリセルと、前記メモリセルに結合されて、前記メモリセルから読み出されたデータ中の誤りを訂正するチャネル復号器であって、前記誤りは、少なくとも部分的に前記誤り機構によって生じたものである、チャネル復号器とを備え、前記チャネル復号器は、符号語の集合からなる符号を復号し、前記メモリセルの不完全な誤り発生特性を考慮した前記符号語の集合の元同士の間の最小の変形ハミング隔たりは、前記符号語の集合の元同士の間の最小のハミング距離より大きい、半導体メモリ装置。前記シンボルの集合の大きさが少なくとも3である請求項18に記載の半導体メモリ装置。前記シンボルの集合の大きさが少なくとも4である請求項18に記載の半導体メモリ装置。チャネル符号器をさらに備え、前記チャネル符号器は、未符号化データを受け取り、そのデータを前記符号語の集合から選択された符号語の集まりに符号化するように構成され、前記符号語がその後前記複数のメモリセルに書き込まれる、請求項18に記載の半導体メモリ装置。前記シンボルの集合の大きさが少なくとも3である請求項21に記載の半導体メモリ装置。前記前記シンボルの集合の大きさが少なくとも4である請求項21に記載の半導体メモリ装置。前記符号語の集合の元同士の間の最小の変形ハミング距離が4以上である請求項18に記載の半導体メモリ装置。前記符号語の集合の元同士の間の最小の変形ハミング距離が5以上である請求項18に記載の半導体メモリ装置。第1の終端と、第2の終端と、不完全な誤り特性を持つ誤り注入機構とを有するチャネルを操作する方法であって、前記チャネルからシンボルストリームを受信するステップであって、前記受信シンボルストリームは複数のシンボル語を含み、各シンボル語は、シンボルの集合から選択された1つまたは複数のシンボルを含む、ステップと、前記受信したシンボル語を復号して、誤り訂正およびまたは検出符号に従って訂正後データストリームを生成するステップであって、前記符号は、当該符号の最小の変形ハミング距離を持つ符号語の集合を含み、最小の変形ハミング隔たりは、前記チャネルの誤り注入機構の誤り注入特性に従って算出され、前記最小の変形ハミング距離は、前記符号のハミング距離のうち最小のハミング距離より大きい、ステップとを含み、シンボル語を復号するステップは、前記符号語の集合のうち、最小の変形ハミング距離をもたらす符号語を判定し、その符号語を出力するステップを含む、方法。データ語と符号語との一対一の対応付けに従って、未符号化データ語を符号語に変換することにより、未符号化データを符号化するステップであって、前記符号はさらに、前記対応付けと、前記チャネルの第1の終端に結合された送信器で行われる符号化とを含む、ステップと、前記誤り注入機構に従った誤りの発生を受ける前記チャネルを通じて前記符号語を送信するステップとをさらに含む請求項26に記載の方法。前記シンボルの集合の大きさが少なくとも3である請求項27に記載の方法。前記最小の変形ハミング距離が少なくとも4であり、前記ハミング距離が4未満である、請求項28に記載の方法。送信信号中の誤りを検出し、訂正する能力は、使用される符号のハミング距離として表すことができる。任意の2つの符号語間のハミング距離は、それら2つの符号語が互いと異なるシンボル位置の数である。例えば、2つの2値の符号語0011010と0010110は、2箇所で異なるため、ハミング距離は2となる。同様に、符号語abacddaとacdaddaは、3つのシンボル位置で異なるため、ハミング距離は3となる。完全なチャネルで使用する符号でt個の誤りを訂正し、t1個の誤りを検出できるようにするには、すべての符号語の最小の隔たりが少なくとも2t2でなければならないことが理解される。詳細には、よく知られた1ビット誤り訂正、2ビット誤り検出の2値のハミング符号は、すべての符号語間に最小で4の隔たりを有する。ある符号語からのハミング距離が1であるすべての受信語は、1つの誤りがあると見なされ、したがって、そのような受信データ語はすべて受信器でその符号語に訂正することができる。2つ以上の符号語から2のハミング距離を持つ受信データ語は2つの誤りがあるものと見なされる。受信符号語から2つの別個の有効符号語までのハミング距離は同じであるため、受信器は、2つの符号語のどちらがチャネル変調器によって送信されたのかを明確に判定することができない。そのような状況では、2つの誤りを検出可能であるが、訂正することはできない。本発明の目的は、非2値の不完全チャネルを通るシンボルストリームのための誤り検出およびまたは訂正符号ならびにチャネル変調を提供することである。本発明の別の目的は、非2値の不完全チャネルを有するメモリ装置内で誤りを検出およびまたは訂正するための符号を提供することである。本発明の別の目的は、不完全な誤り遷移特性を持つ多値メモリ内で誤りを検出およびまたは訂正するための符号を提供することである。本発明の別の目的は、非2値の不完全チャネルおよびメモリのための効率的な誤り訂正符号を提供することである。本発明は、非2値の不完全な通信チャネルまたはそれに相当する多値メモリ装置で発生する誤りを検出し、訂正する方法およびシステムを提供する。本発明の別の目的は、不完全な通信チャネルまたはそれに相当する多値メモリ装置で使用する符号を発見するアルゴリズムを提供することである。一態様によれば、チャネルは第1および第2の終端を有する。チャネルの第1の終端は送信器に結合される。チャネルは、シンボルの集合から選択されたシンボルを第1の終端から第2の終端に送信することが可能である。チャネルは、不完全な誤り発生特性を示す。符号は符号語の集合を含む。符号語の集合の元は、1つまたは複数の符号シンボルの長さである。符号シンボルはシンボルの集合の要素である。チャネルの誤り発生特性を考慮した符号語の集合の元同士の間の最小の変形ハミング隔たりは、符号語の集合の元同士の間の最小のハミング距離より大きい。メモリ装置、上記チャネルを使用する方法、および上記符号を生成する方法も記載される。さらなる態様では、符号はさらにデータ語の集合を含む。データ語の集合の大きさは、符号語の集合の大きさと同じである。データ語の集合の元と符号語の元との間に一対一の対応付けが存在する。さらなる態様では、シンボルの集合の大きさは少なくとも3である。さらなる態様では、シンボルの集合の大きさは少なくとも4である。さらなる態様では、受信器がチャネルの第2の終端に結合される。受信器は、チャネル復調器およびチャネル復号器を備える。送信器は、チャネル変調器およびソースデータ符号器を備える。チャネルの第1の終端が送信器に結合される。チャネルは通信チャネルである。送信器は、データ語を受け取り、符号語を生成することにより符号を実装する。受信器は、チャネルからシンボルのグループを受信し、送信器に受け取られたデータ語に対応するデータ語を生成することにより符号を実装する。さらなる態様では、シンボルの集合の大きさは少なくとも3である。さらなる態様では、シンボルの集合の大きさは少なくとも4である。さらなる態様では、符号語の集合の元同士の間の最小の変形ハミング距離は4以上である。さらなる態様では、符号語の集合の元同士の間の最小の変形ハミング距離は5以上である。追加的態様では、システムは、複数のメモリセルを含む少なくとも1つのメモリ装置を含む。各メモリセルは、記憶されたシンボルの集合の元と一対一の対応関係にある複数の記憶状態を有する。メモリ装置は、不完全な誤り発生特性を持つ誤り機構を有する。メモリコントローラが、上記少なくとも1つのメモリ装置に結合されて、記憶されたシンボルの集合から選択されたシンボルから導出されたデータを、少なくとも1つのメモリ装置の複数のメモリセルから読み出させる。チャネル復号器がメモリコントローラに結合されて、少なくとも1つのメモリ装置から読み出されたデータ中の誤りを訂正し、誤りは、少なくとも部分的に誤り機構によって生じたものである。チャネル復号器は、符号語の集合を含む符号を復号する。少なくとも1つのメモリ装置の不完全な誤り発生特性を考慮した符号語の集合の元同士の間の最小の変形ハミング隔たりは、符号語の集合の元同士の間の最小のハミング距離より大きい。さらなる態様では、シンボルの集合の大きさは少なくとも3である。さらなる態様では、シンボルの集合の大きさは少なくとも4である。さらなる態様では、チャネル符号器が、未符号化データを受け取り、そのデータを符号語の集合から選択された符号語の集まりに符号化するように構成される。符号語は、その後、少なくとも1つのメモリ装置内の複数のメモリセルに書き込まれる。さらなる態様では、符号語の集合の元同士の間の最小の変形ハミング距離は4以上である。さらなる態様では、符号語の集合の元同士の間の最小の変形ハミング距離は5以上である。追加的態様では、半導体メモリ装置が複数のメモリセルを有する。各メモリセルは、記憶されたシンボルの集合の要素と一対一の対応関係にある複数の記憶状態を有する。メモリ装置は、不完全な誤り発生特性を持つ誤り機構を有する。チャネル復号器がメモリセルに結合されて、メモリセルから読み出されたデータ中の誤りを訂正し、誤りは、少なくとも部分的に誤り機構によって生じたものである。チャネル復号器は、符号語の集合を含む符号を復号する。メモリセルの不完全な誤り発生特性を考慮した符号語の集合の元同士の間の最小の変形ハミング隔たりは、符号語の集合の元同士の間の最小のハミング距離より大きい。さらなる態様では、シンボルの集合の大きさは少なくとも3である。さらなる態様では、シンボルの集合の大きさは少なくとも4である。さらなる態様では、チャネル符号器が、未符号化データを受け取り、そのデータを符号語の集合から選択された符号語の集まりに符号化するように構成される。符号語はその後複数のメモリセルに書き込まれる。さらなる態様では、シンボルの集合の大きさは少なくとも3である。さらなる態様では、シンボルの集合の大きさは少なくとも4である。さらなる態様では、符号語の集合の元同士の間の最小の変形ハミング距離は4以上である。さらなる態様では、符号語の集合の元同士の間の最小の変形ハミング距離は5以上である。追加的態様では、第1の終端と、第2の終端と、不完全な誤り特性を持つ誤り注入機構とを有するチャネルを操作する方法は、チャネルからシンボルストリームを受信するステップであって、受信シンボルストリームは複数のシンボル語を含み、各シンボル語は、シンボルの集合から選択された1つまたは複数のシンボルを含む、ステップと、受信したシンボル語を復号して、誤り訂正およびまたは検出符号に従って訂正後データストリームを生成するステップであって、符号は、当該符号の最小の変形ハミング距離を持つ符号語の集合を含み、最小の変形ハミング隔たりは、チャネルの誤り注入機構の誤り注入特性に従って算出され、最小の変形ハミング距離は、符号のハミング距離のうち最小のハミング距離より大きい、ステップとを含み、シンボル語を復号するステップは、符号語の集合のうち、最小の変形ハミング距離をもたらす符号語を判定し、その符号語を出力するステップを含む。さらなる態様では、方法は、データ語と符号語との一対一の対応付けに従って、未符号化データ語を符号語に変換することにより未符号化データを符号化するステップであって、符号はさらに、対応付けと、チャネルの第1の終端に結合された送信器で行われる符号化とを含む、ステップと、誤り注入機構に従った誤りの発生を受けるチャネルを通じて符号語を送信するステップとをさらに含む。さらなる態様では、シンボルの集合の大きさは少なくとも3である。さらなる態様では、最小の変形ハミング距離は少なくとも4である。ハミング距離は4未満である。本発明の他の目的および利点は、含まれる図および以下の説明から明らかになろう。用語の定義本発明の説明では、以下の用語を一般に使用する。用語xを使用してソースデータストリームを表す。これは典型的には2値のビットストリームであるが、必ずしもそうとは限らない。用語uを使用して圧縮データストリームを表す。これは典型的には2値のビットストリームであるが、必ずしもそうとは限らない。用語vを使用して符号化データストリームを表す。これは典型的には2値のビットストリームであるが、必ずしもそうとは限らない。用語vを使用して、送信シンボルストリームを表す。これは通例シンボルストリームである。各シンボルは、1つの電気または物理的実体または特性で表すことができ、または各シンボルは、より小さいシンボルの集まり、例えば2値ビットの集まりからなることができる。両極端の一方では、各シンボルは2値の1ビットであり、他方では、各シンボルで元のソースデータストリームの非常に多くのビットを符号化することができる。用語rを使用して受信シンボルストリームを表すことができ、受信シンボルストリームは、完全でないチャネルおよびまたはメモリによって誤りが注入された後の送信シンボルストリームである。用語rを使用して、復調後の受信データストリームを表す。これは、通例は2値のビットストリームであるが、必ずしもそうとは限らない。用語wを使用して、チャネルまたはECC復号器から出力される訂正されたデータストリームを表す。これは通例は2値のビットストリームであるが、必ずしもそうとは限らない。符号xを使用して、最終的な受信データストリームを表す。これは通例は2値のビットストリームであるが、必ずしもそうとは限らない。符号Sを使用して、チャネルが本来通信するシンボルの集合を表す。2値チャネルの場合、シンボルの集合Sはシンボル0および1からなる。変数lを使用して、シンボルの集合の大きさを指す。用語シンボルは、1ビット分のソースデータまたは符号データの値の表現を意味する。シンボルの集合の大きさは、1つのシンボルがとることができる異なる値の数である。1つの2値シンボルの集合の大きさは、各シンボルにつき2つの値が許されるため、2となる。用語nを使用して、シンボルまたはビットを単位とした符号語の大きさを表す。用語符号語は、1つまたは複数のデータ語を表すために割り当てられ、任意で誤り検出または訂正情報を含んでいる、所定長さの符号シンボルの連続を意味する。用語kを使用してデータ語の大きさを表す。データ語は、共に符号化されてチャネルシンボルまたは記憶ビットとなるビットまたはシンボルの集まりである。用語データ語は、1ビットまたは複数のビットのソースデータを表す、所定長さのシンボルの連続を意味する。用語pおよびqを使用して、送信または記憶されるシンボルストリームの任意のシンボル位置で誤りが生じる確率を表す。用語シンボルのn組は、ソースデータの1ビットに対応するか複数ビットに対応するかに関係なく、データまたは符号のn個のシンボルからなる連続を意味する。符号の効率は、データ語kの大きさを符号語nの大きさで割った比として測定される。すなわち、符号の効率は、所与の数の未符号化データビットを送信または記憶するために必要な符号化データのビット数と、その未符号化データのビット数との比である。データ集合または送信シンボルの集合のいずれかが非2値の場合は、対応するnまたはkにそのシンボルの集合の大きさを乗算する。符号化データの場合は、シンボルの集合の大きさをlと表す。したがって、データ語が2値であり、送信されるシンボルストリームが非2値の場合は、符号の効率はknlとして算出される。用語データストリームまたはシンボルストリームを使用して、純粋な1ビット幅のシリアルストリームから、多数のシンボルが同時または並行に通信または記憶されるマルチビット並行編成にわたるすべての方式の通信または記憶機構を表す。さらに、1つまたは複数のメモリ装置を含むチャネルの場合は、符号化シンボルストリームが任意の順序でメモリの特定のアドレスに書き込まれる順番と、それらのアドレスから情報が読み出されて受信データストリームまたはシンボルストリームを形成する順番との対応付けは必ずしも存在しない。さらに、1つの入力および出力を持つブロックとしてメモリ装置303を図示することは、マルチポートメモリへの本発明の適用性を何ら制限するものではないことが理解されよう。本発明の実施形態は、非対称の誤り注入特性を示すすべての幅および編成のチャネルおよびメモリ、ならびにまたは1つの記憶セルもしくは位置につき2バイナリビット以上の情報を記憶する非2値チャネルまたはメモリに適用することができる。特に、本発明は、データの符号化および復号がメモリ内に位置するか、またはメモリコントローラ内に位置するか、またはシステム内のいずれか他の場所に位置するかに関係なく、メモリシステム内のメモリ装置へのデータの書き込みおよび読み出しのために共用データアドレスおよびまたは制御信号経路、ならびに共通もしくは共有コントローラ回路を持つ従来編成のメモリシステムに特に適用することが可能である。本願では、用語変形ハミング距離は、1対の符号語に関して、第1の符号語から第2の符号語に移動するために特定の可能なシンボル遷移図を横断するために必要な、許容される最小の数の誤りを意味するものとする。変形ハミング距離が従来のハミング距離と異なるのは、許容される誤り遷移に対応する違いのみを考慮する点である。すなわち、変形ハミング距離は、第1の語を第2の語に変えることができる、発生しうる誤りの最小数である。変形ハミング距離は不完全チャネルでは必ずしも対称にはならないことが理解されよう。図11を参照すると、aaaからbbbまでの変形ハミング距離は3である。これは、aaaは、例えば次の3回の誤り遷移、aaa→aab、次いでaab→abb、そしてabb→bbbを介してbbbに変えることができるためである。しかし、bbbをaaaに変えることができる誤り遷移の組み合わせはないため、bbbからaaaまでの変形ハミング距離は無限となる。これに対して、従来のハミング距離は対称であり、aaaとbbbは3つのシンボル位置で異なるため、aaaとbbbの間のハミング距離はシンボル遷移図に関係なく3である。1対の符号語間の変形ハミング隔たりは、両方の符号語を第3の語に変えるために必要な、許容されるまたは発生しうる誤りの最小の合計数である。第3の語は、2つの符号語のどちらか、または他の語である。例えば、図11を参照すると、語abbとbbaの変形ハミング隔たりは2である。これは、2つの許容される誤り遷移abb→bbbおよびbba→bbbの結果、両方の語が共通の語bbbに変えられるためである。同様に、語aaaとabb間の変形ハミング隔たりは、上記のようにaaaは2回の許容される誤り遷移でabbに変えることができるので2になる。変形ハミング隔たりの定義については下記でさらに説明する。1つの符号全体の変形ハミング符号語間隔は、その符号中の任意の符号語の対間の最小の変形ハミング隔たりである。不完全な誤り特性を持つチャネルまたはメモリの場合は、例えば1つの符号語を、別の符号語に1つまたは複数の誤り遷移を足した結果として表すことができない場合には、2つの符号語間の変形ハミング距離が同じ2つの符号語間の従来のハミング距離より大きくなる可能性がある。例えば、図11を参照すると、3つ組aaaとccaは、2つのシンボル位置で異なるため2のハミング距離となる。同じ2つの3つ組aaaおよびccaは、両方の3つ組ともそれぞれ2回の誤り遷移、例えばaaa→baa→bba、およびcca→bca→bbaを介して共通の3つ組bbaに変えることができるので、4の変形ハミング隔たりを持つ。本発明を制限ではなく例として添付図面の図に示す。ブロック符号は、冗長性のシンボルを追加してn個のシンボルの長さの符号語を形成することにより、ソースデータストリームuのk個のシンボルからなるグループを保護する、誤り訂正符号のグループである。ソースデータストリームにあるk個のシンボルからなるグループはデータ語となる。データシンボルと符号化シンボルが同じシンボルの集合から選択された場合、基本的に誤りからの保護をもたらす冗長シンボルの数はnkになる。2値のブロック符号は、2値のソースデータストリームに適用されて、ソースデータストリームを論理的、時間的、または物理的にkビットのデータ語に分割する。各データ語はnビットの符号語に符号化され、チャネル変調器に送られてm個のシンボルに符号化され、mシンボルの長さの送信符号語を生成する。2値チャネルで2値のソースデータストリームの場合は、mnとなる。あるいは、誤りの符号化および変調は、同時に1回の工程として行うこともできることが理解される。符号の選択は、n組の部分集合が、すべての可能なデータ語の集合と一対一の関係で対応する符号語の集合を形成し、残りの符号のn組がデータ語に対応しない、すなわち符号の一部とならないように行うことができる。この状況では、当該符号の一部でないn組の1つがチャネル復調器またはチャネル復号器またはECC復号器に受信されると、その状況が、チャネルまたはメモリにより1つまたは複数の誤りが生じたことを示す。この工程については下記でさらに詳しく説明する。図7に、対称かつ完全な3値チャネルの場合の可能な誤り遷移を示す。この様式のグラフは、送信シンボルと受信シンボルが図中で互いに重ねられている点を除いて、例えば図5と同じ情報を示す。図に表すチャネルは、双方向の矢印で示すように各シンボルがチャネルまたはメモリ内で誤りのために他のどのシンボルにも変わりうるため、完全である。各双方向の矢印は、送信シンボルストリームに注入される可能性のある2つの発生しうる誤りを表す。図8は、別の不完全な3値チャネルの場合の可能なシンボル変換グラフを示す。この場合は、シンボルaは劣化してシンボルbまたはcになる可能性があり、シンボルbは劣化してシンボルcになる可能性があるが、その他の考えられる誤り変換はどれも物理的に可能でない。このシンボル変換グラフが成立するのは、例えば、信号レベルまたは記憶された値が時間と共に、またはチャネルの長さに沿ってシンボルcで表す可能な最低の値に向かって低下して行くチャネルの場合である。以下で、3値不完全チャネルで使用する、1ビット誤り訂正2ビット誤り検出符号、および1ビット誤り訂正1ビット誤り検出符号を実現するための符号例を説明する。他の種類の誤り検出および訂正を同様にして実装することができ、q値チャネルに一般化することができ、q2であることを理解されたい。3値チャネルは、図6に示すように、送信シンボルの集合の大きさが3に設定されるチャネルである。図9に、1つのシンボルの3つの値の完全な集合を示す。一部のシンボルを囲む網掛けをした灰色の枠で示すように、1つの可能な符号はシンボルaおよびcのみを含む。シンボルbが受信されると、誤りが発生していることになるが、元の送信シンボルは特定することができず、このチャネルの可能な誤り遷移を考えると、シンボルbはシンボルaおよびシンボルcの両方から1の変形ハミング距離である。本発明の実施形態では、図10に、図6の誤り特性を持つ3値チャネルで送信されるシンボルの対から構成される符号を示す。可能なシンボル対は9つある。ソースデータビットの2つの2値の値を表す符号語としてシンボル対aaおよびccが選択された場合は、すべての可能な1ビット誤りを訂正し、すべての可能な2ビット誤りを検出することができる。この符号をTableAに示す。ソースデータビットと符号語との対応付けは完全に任意であり、また、符号語へのソースデータビット値の2通りの割り当てのどちらでも同じ最終的結果が得られることを理解されたい。また、TableAの解説欄で発生の可能性なしと表示された受信符号語は、任意の可能な符号語からの誤り遷移に基づく図9の誤り遷移図で想定されない受信符号語を表すことも理解されたい。特定の状況では、誤り遷移図で具現化されるものの他に、恐らくは低い確率の他の誤り機構がある可能性がある。通例、そのような誤り機構は、防御対象となる主要な誤り機構に比べてはるかに確率が低い。符号の基礎となる誤り遷移図で顕在化していない誤り遷移を発生させる誤り機構は、その符号では訂正できない場合がある。そのような状況では、発生の可能性なしと表示された受信符号語は訂正不可能な誤りと見なされる。また、単独で、または他の誤り機構と組み合わさって、1つの符号語を別の符号語に変えることが可能な他の誤り機構がある可能性もあり、そのような誤りまたは誤りの組み合わせは検出不可能な誤りの種別に分類される。シンボル対bbも符号語である場合は、この符号は、3つの有効な符号語を持つ、1ビット誤り検出、1ビット誤り訂正符号になる。各シンボル対は、1ビットのみのソースデータを送信することができるが、シンボル対の集まりを組み合わせて、より多くのソースデータビットを符号化することもできる。TableBに、2つのシンボル対をグループ化することで、3ビットのソースデータを送信することができ、各シンボル対で1つの誤りを検出および訂正することが可能な符号が生成されることを示す。3ソースビットを2つのシンボル対に変調するこの変調では、8通りのソースビットの組み合わせと9通りの有効符号語の組み合わせがある。符号語の組み合わせの1つは使用しないままにしておく。ソースデータビットの3つ組をシンボル対に変調する特定の変調は任意であり、他の考慮事項に応じて選択できることを理解されたい。より多くのシンボル対を共にグループ化するこのパターンでは、各シンボル対で1ビットの誤りを検出し訂正することが可能な追加的なより高次の符号が生成され、それにより、より多くのソースビットを符号化し、符号の効率を向上できることも理解されよう。このような符号のいくつかの例の特性をTableCに示す。シンボル対の値へのソースデータビット値の変調は任意であり、それに対応する変調器および復調器は従来の論理最小化技術を使用して設計できることを理解されたい。また、シンボル対の一部である個々のシンボルは、シンボルを交互に配置するか、または他の形で入れ替える、もしくは並び替えることにより時間的または空間的に離してよく、その種別の符号で検出することができない誤りの対が、論理的、物理的、または時間的に隣り合わないようにし、それにより同じシンボル対内で複数個の誤りが発生する確率を下げることも可能であることを理解されたい。図11に、3つのシンボルからなる符号語の場合に、図6に定義される3値チャネルを仮定したすべての発生しうる誤り遷移を示す。この場合、5つの符号語からなる符号は、TableDに示すように、3つのシンボル内のすべての1ビット誤りの訂正とすべての2ビット誤りの検出を可能にすることができる。例えばTableDを参照すると、受信されたシンボルの3つ組babは、両方の符号語aaaおよびcacから2つの誤り分だけ離れていることに注目されたい。具体的には、符号語aaaは、第1の誤りでbaaに変えられ、それが、今度は3番目のシンボルにおける同じ誤りタイプの別の事例によってbabに変えられる。同様にして、符号語cacは、第1および第3のシンボル位置の両方で発生するc→bの誤りにより非符号語babに変えられる。より重要な点として、シンボルbからシンボルaへの遷移は図6で定義されるチャネル特性では可能でないため、符号語bbbからシンボルの3つ組babまでの変形ハミング距離は実質的に無限である。なぜならば、図6の不完全な誤り遷移図で想定する誤りの中で、2番目のbシンボルをaのシンボルに変えることができる誤りはないためである。上記と同じ例を参照すると、図11のシンボル遷移図によると、1回の許容される誤りが真ん中のシンボルをaからbに変えることができ、それにより3つ組をbabから3つ組bbbに変えるため、シンボルの3つ組babからシンボルの3つ組bbbまでの変形ハミング距離は1になる。同様に、シンボルの3つ組bbbからシンボルの3つ組babまでの変形ハミング距離は無限であり、aaaからabbまでの変形ハミング距離は2であり、accからabbまでの変形ハミング距離は2となる。この符号の誤り検出および訂正の性質を理解するために、集約的特性を考える。上記の例では、aaaからabbまでの変形ハミング距離が2で、accからabbまでの変形ハミング距離も2であるため、非符号語abbを経由する符号語aaaとacc間の変形ハミング隔たりは、それら2つの値の和、すなわち4になる。比較として、この符号の従来のハミング距離は3を超えることはない。それは、各語が3シンボルしか含まず、したがって2つの語が異なるのは最大で3つの位置であるためである。従来のハミング距離と変形ハミング距離の重要な違いは、変形ハミング距離の計算時に、1つのシンボル位置に2つの誤りがあると距離が2になる場合があることである。例えば、図17に示す不完全な誤り遷移の集合を持つチャネルまたはメモリの場合、シンボルの3つ組caaおよびbbaは、前者が1番目のシンボルにしか誤りを含まないのにも関わらず、共にシンボルの3つ組aaaから2の距離にある。この場合の2つの誤りおよびは両方とも許され、このチャネルの定義内では、同じシンボル位置に連続して発生することができる。別の実施形態では、同じ誤り遷移図を持つ異なるチャネルまたはメモリは、送信または記憶される各シンボルに多くとも1つの誤りを注入することが可能であり、あるいは、第2の誤りがシンボルに注入される確率は、別のシンボルに第2の誤りが生じる確率よりもかなり低く、前者の種別の事象は無視することができる。変形ハミング隔たりは、特定のシンボル遷移図に照らして符号によって提供される誤り検出および訂正の程度を理解する際に重要な役割を果たす。上記の例から、符号語は4のハミング距離を持つという従来の要件が満たされない場合でも、符号は、不完全な誤り注入特性を持つチャネルで1ビット誤り訂正および2ビット誤り検出を提供できることが理解されよう。例えば、すべての符号語がすべての他の符号語から少なくとも3の変形ハミング隔たりである場合、第1の符号語中の2ビット誤りは、その他の符号語がいずれも誤りなく送信されることから区別することができる。また、符号語ではないが、ある符号語から1の変形ハミング距離を持つすべての他の可能な受信語が、すべての他の符号語から少なくとも3の変形ハミング距離を有する場合は、すべての可能な1ビット誤りは曖昧さなしに訂正可能であり、すべての他の1ビットおよび2ビット誤りから区別することができる。最後に、ある符号語から2の距離にあるすべての可能な受信語がすべての他の符号語からも少なくとも2の変形ハミング距離を有する場合は、すべての2ビット誤りは、すべてが必ずしも訂正可能でなくとも、2ビット誤りとして検出することができる。そのような2ビット誤りは、受信語が少なくとも2つの符号語から2の変形ハミング距離にある場合には訂正することができない。したがって、2つの符号語間の変形ハミング隔たりは、完全な誤り特性を持つ環境で動作する符号に対する従来のハミング距離と同様に、注入された誤りを含んでいる符号語を判別する能力に関係する。特に、2つの符号語間の変形ハミング隔たりは、第1の符号語から任意の非符号語までの変形ハミング距離と、第2の符号語から同じ非符号語までの変形ハミング距離との最小の和に等しく、その最小値がすべての発生しうる非符号語に対して取られる。代数的に表現すると、共に可能なn組Snの空間から選択されたn組である2つの符号語aとb間の変形ハミング隔たりはすべてのc∈Snc≠ac≠bについて、mHsminmHdによって与えられ、mHsは、符号語aと符号語b間の変形ハミング隔たりであり、mHdは、符号語aから符号語bまでの変形ハミング距離である。変形ハミング隔たり関数は、mHsmHsである点で対称である。1つの符号全体の変形ハミング符号語間隔は、その符号中の各符号語対間の変形ハミング隔たりのうち最小のものである。1つの符号全体の変形ハミング符号語距離は、その符号中の各符号語対の間の変形ハミング距離のうち最小のものである。代数的には、これらはすべてのab∈CC⊆Sna≠bについてmHcwsminすべてのab∈CC⊆Sna≠bについてmHcwdminによって与えられ、Cは、Sn中のn組の集合からなる符号である。符号の変形ハミング符号語間隔が4の場合は、すべての非符号語は、11つの符号語からは1つの誤りだけ離れており、すべての他の符号語からは少なくとも3つ以上の誤りだけ離れているか、21つの符号語からは2つの誤りだけ離れており、すべての他の符号語からは3つ以上の誤りだけ離れているか、32つ以上の符号語から2つの誤りだけ離れているか、または、4すべての符号語から3つ以上の誤りだけ離れているか、のいずれかになる。また、各符号語がすべての他の符号語から少なくとも3の変形ハミング距離だけ離れている場合は、受信された語が符号語であれば、その語は、異なる符号語に1つまたは2つの誤りが注入された結果ではありえないことになる。したがって、符号は、mHcws≧4かつmHcwd≧3であれば、不完全な誤り注入特性を持つチャネルまたはメモリにわたる1ビット誤り訂正、2ビット誤り検出符号になる。これらの条件がすべて満たされる場合は、すべての受信符号語は、誤りのない送信およびまたは記憶の結果であると見なすことができる。上記第1の分類にあたるすべての受信された非符号語は、1ビット誤りの結果であると見なして差し支えなく、送信または記憶された符号語で誤りが訂正されると明確に判断することができる。第2の分類にあたるすべての受信された非符号語も同様に、曖昧さなしに訂正可能な2ビット誤りの結果であると結論付けることができる。第3の分類にあたるすべての受信された非符号語は、2ビット誤りの結果であるが、送信または記憶された元の符号語は明確に特定することができない。第4の分類にあたるすべての受信された非符号語は、一部は訂正可能な多ビット誤りの結果である可能性もあるものの、訂正不可能な多ビット誤りとして扱うことができる。TableEに、上記と同じ論理に従った、符号により提供される誤り訂正および検出の度合いと、その符号の最小の変形ハミング符号語隔たりおよび最小の変形ハミング符号語距離との関係を示す。当業者には、ここに開示される論法に従って、TableEをより高い度合いの誤り訂正および検出に拡張する方法が理解されよう。誤り遷移図が不完全である結果、2つの符号語間の変形ハミング隔たりは、従来のハミング距離、すなわち2つの符号語が互いと異なっているシンボル位置の数の和よりも大きくなる可能性がある。TableDに示した先の例では、aaaとaccの間のハミング距離は、3つのシンボルのうち2つが異なるため2となる。それら2つの符号語は、要求される3のハミング隔たりを持たないため、従来の1ビット誤り訂正符号の一部にはなりえない。符号は、少なくとも4の変形ハミング符号語間隔を有する場合に1ビット誤り訂正および2ビット誤り検出符号となることができる。例えば、ある非符号語が第1の符号語から1の変形ハミング距離だけ離れており、第2の符号語から2の変形ハミング距離だけ離れている場合、チャネル復号器は、第1の符号語に伴う1ビットのシンボル誤りと、第2の符号語に伴う2ビットのシンボル誤りとを区別することができない。2つの符号語間の変形ハミング距離が従来のハミング距離より大きくなりうるのと全く同様に、符号の変形ハミング符号語間隔も、従来のハミング距離より大きくなる可能性がある。したがって、符号は、誤り遷移図が完全であるか、または符号が不完全な誤り特性を利用することができなかった場合には可能でないところまで誤りを訂正およびまたは検出することができる。TableDの例は、ハミング距離は4未満であるが、変形ハミング符号語間隔が4以上であり、変形ハミング符号語距離が3以上であるので、不完全な誤り遷移図がある場合に1ビット誤り訂正2ビット誤り検出する符号である。その理由から、TableDの符号は、その従来のハミング距離に基づくとSECDED符号とは見なされない。下記で、特定の誤り遷移図を考える時にハミング距離よりも大きい変形ハミング符号語間隔を持ち、ハミング距離のみの考慮から理解されるよりも多くの誤りを検出または訂正することができる符号の追加的な例を挙げる。引き続きTableDを参照すると、シンボルの3つ組bbbを符号語の集合から除外した場合には、すべての場合にシンボルbの受信は誤りを意味することに留意されたい。この場合、aからcまたはその逆に遷移する確率が、シンボルaおよびcからシンボルbへの許される誤り遷移の確率よりも大幅に小さくなるように、物理的なチャネル特性、例えば電圧、電流、または電荷レベルに適切なシンボルa、b、cを割り当てることができる。そのような例の1つは、一部のシンボル遷移の見込みが他のシンボル遷移よりはるかに低くなることを保証するように設計された変調器復調器と組み合わせたチャネルであり、区別は、基本的に発生しえない遷移と、非ゼロの確率の誤り遷移との区別になる。このチャネルでシンボル対を組み合わせてより多くのソース符号ビットを同時に処理することが可能な大きな符号を生成するのと同様にして、複数のシンボルの3つ組を組み合わせて、より多くの符号語を持つ符号を生成することができる。TableFに、3つ組の同じ組み合わせを示す。ソースデータビットと複数のシンボル3つ組との間の任意の変調または対応付けを本実施形態で使用できることが理解されよう。より大きなシンボルのグループを同様に組み合わせて符号語にすることができる。4以上の変形ハミング符号語間隔の場合は、符号は、1ビット誤り訂正、2ビット誤り検出符号となる。本発明の一実施形態は、図6に示す誤り特性を持つ3値チャネル上の4つのシンボル語に基づくSECDED符号である。この符号をTableGに示す。この符号は、1つのみの符号語で真ん中のシンボルbを使用する。この符号語は、3ソースデータビットをチャネル上の4つのシンボルに対応付ける変調を実装する能力を変えることなく、除去することができる。本発明の別の実施形態は、TableGに示すものと同じ符号を含むが、bbbbである符号語5は使用しない。TableGの最後の列に示すこの場合は、先の実施形態と同様に、シンボルbを使用する符号語はない。この実施形態では、シンボルbの受信を誤りを示すものとして使用することができ、誤りの性質を判定すると共に訂正可能な誤りを訂正するための追加的な分析を始動させる。この例は、ソースデータビットのグループの特定の値と特定の符号語との特定の対応付けに依拠しないことが理解されよう。別の実施形態では、同じチャネルにある5つのシンボルからなるグループをグループ化して符号語にし、TableHに列挙する符号に従って符号化することができる。この実施形態では、この種別の他の符号と同じように、各符号語間の変形ハミング隔たりは少なくとも4であり、よってこの符号はSECDED符号になる。当該チャネルの誤り特性に基づく変形ハミング符号語間隔に基づく異なる特性を持つ他の符号も可能であることが理解されよう。この種別の符号は、代わりに、各符号語中で6個以上のシンボルを使用してもよく、また、対応するチャネル符号器、チャネル変調器、チャネル復調器、およびチャネル復号器は、チャネルが通信チャネルであるかメモリ装置であるかに関係なく、公知の論理合成技術を使用して実装できることが理解されよう。また、チャネルを1つまたは複数のメモリ装置として実装する場合は、本発明の実施形態の個々の符号語はすべて1つのメモリ装置に記憶しても、または複数のメモリ装置に分散してもよいことも理解されたい。TableIに、図6で定義する特性を有するチャネルを仮定して、図18の方法で見つけられる符号の種類と有効性を示す。図12に本発明の一実施形態の3値通信チャネルのアイダイアグラムを示す。サンプル点tsampleで、着信信号の電圧をサンプリング、すなわち捕捉する。図12には、それぞれシンボルc、b、およびaとして確実にサンプリングされる3つの電圧範囲、Vcl~Vch、Vbl~Vbh、およびVal~Vahを示す。3つの電圧範囲の幅と、シンボルa、b、およびcの電圧範囲間の雑音余裕、ならびに受信器の入力回路の特性により、あるシンボルとして送信された信号が別のシンボルとして受信される条件が決まる。例えば、一実施形態では、シンボルaおよびcの許容範囲を小さくし、一方でシンボルbの範囲を増大する。それらの変更した範囲を有効化して、シンボルaとして送信されたシンボルがシンボルcとして受信される確率、およびその逆の確率を下げる。その結果、例えば図6の確率遷移図または図9~図11の変形ハミング距離グラフに示すように、送信器と受信器の対を備えたチャネルが非対称の誤り特性を持つことが保証される。したがって、本実施形態では、選択された電圧範囲は、非対称の誤り特性を利用する3値符号の使用を容易にする。これは、シンボルaからシンボルb、またはシンボルcからシンボルbへの誤り遷移の確率を増しても有利である可能性がある。本発明の実施形態は、図1、図2、および図3に示す一般的な種類のシステムで使用することができる。例えば、図1に示す種の通信システムの場合、チャネル符号器およびチャネル変調器は、チャネルの不完全な誤り特性を利用するように本発明の符号を実現する。チャネル復調器およびチャネル復号器は、符号を復号し、符号の誤り検出および訂正の限界まで、チャネルで生じた誤りを検出およびまたは訂正する。図3に示すような記憶システムの場合は、ECC符号器が、メモリ装置の不完全な誤り特性を利用するように符号を実現する。ECC復号器は、読み出したデータを復号し、符号の誤り検出および訂正の限界まで、メモリによって生じた誤りを検出およびまたは訂正する。図13に動的ランダムアクセスメモリのメモリセルの模式図を示す。DRAMは複数のメモリセルを含み、通例は各メモリセルを使用して1ビット分の情報を記憶する。1ビット分の情報は、通例、図のコンデンサに蓄えられる電荷の量で表され、VcellはVplateより大きいか、または小さい。DRAMの重要な特性は、コンデンサに蓄えられた電荷が漏洩することであり、そのためVcellはVplateに向かって変動する。一定時間が経過すると、VcellとVplateとの差は小さくなり、そのビットの情報の読み出しを担うDRAMの部分が、そのセルに当初記憶されたのが1であるか0であるかを区別するのに不十分になる。この機構および当技術分野で知られる他の機構により、書き込まれた1が0として読み出される、またはその逆の可能性がある。したがって、図1および図3に従ってチャネルの一部として考えると、DRAMは、図4の遷移確率図で示すような従来の2値の対称誤り特性を有することになる。一実施形態では、メモリセルの読み出し回路は、各メモリセルのセル電圧Vcellが3つのシンボルa、b、およびcの1つを示すものと解釈するように構成される。1つのセルにつき2ビット以上の情報を記憶するDRAMが当技術分野で知られている。図14に示すこの実施形態では、セルから読み出しが行われる時のValとVah間のセル電圧をシンボルaと解釈し、VblとVbh間のセル電圧をシンボルbと解釈し、セルから読み出しが行われる時のVclとVch間のセル電圧をシンボルcと解釈する。これらのセル電圧範囲は、Vplateがシンボルbに対応する範囲内にあり、シンボルaおよびcに対応する範囲がそれぞれVplateより上と下になるように選択する。メモリセルに書き込みが行われる時、セルにシンボルaが書き込まれる場合は、Vcellは、可能な限りVddに近い初期値に設定される。さらに、セルにシンボルcを書き込む場合は、Vcellは可能な限りGndに近い初期値に設定され、セルにシンボルbを書き込む場合は、VcellはVplateに近い初期値に設定される。コンデンサの電荷が漏洩し、電圧VcellがVplateに向かって低下して行くと、シンボルaとcはシンボルbから区別しにくくなるが、互いとの区別がつかなくなることはない。3値メモリとして動作させる場合のこのDRAMの誤り機構は、不完全な遷移確率図を持つ。この原理を、1つの重大な誤り機構の結果、信号が所定の数量または状態に向かって減衰して行く他の記憶媒体または通信チャネルに適用することが企図される。各種シンボルに対応する信号範囲は、特に所定の数量より上および下の信号値を利用できる場合には、不完全な遷移確率図を生成し、それにより非対称のチャネルを作り出すように選択することができる。DRAMは他の誤り発生機構も有する。DRAMの中には一度限りの誤りであるソフトエラーを生じるものがあり、一方で、常に同じように故障する欠陥のあるメモリセルを伴うものもある。例えば、Vcellを恒久的にVplateに短絡させるような形で故障するコンデンサを含んでいるメモリセルは、図15に示す確率遷移図を持つセルとして表される。他の実施形態は、4つの値の1つを記憶または通信するメモリまたはそれに対応するチャネルで使用するチャネルの系統を含む。DRAMおよび1つのセルにつき4つの値を記憶する他のメモリタイプが従来技術で知られている。図16に示すように、例示的メモリセルに記憶された4つの電圧範囲はそれぞれ、ここではa、b、c、およびdとする4つのシンボルの1つを表す。シンボルの集合の大きさが2の累乗であるチャネルまたはメモリの場合、チャネル変調は、符号化データストリームから整数個のビットを選択して、記憶または送信するシンボルを決定するという単純なものとすることができる。図16には、4通りの可能なチャネル変調を示し、ここでは、異なる符号化データストリームのビット対が、記憶または送信される4つのシンボル各々に対応する。これらの符号化のうち第1の符号化を、図17に示すチャネル遷移確率図に示す。この図は、記憶または送信される電圧が中央点に向かって低下することによって生じる誤り発生機構を表す。詳細には、シンボルaおよびdはそれぞれシンボルbおよびcに向かって劣化し、シンボルbおよびcは、共通の中間電圧に近づくことにより、実質上互いに向かって劣化する。この符号化チャネルビットのシンボルへのグレイコード符号化では、すべての誤り遷移が可能という訳ではない。符号化されたチャネルビットの対ごとに発生しうる誤りが4つある。これらの誤りを個々のビットから見ると、対の第1のビットについてはすべての誤りが可能であるが、各対の第2のビットについては1つのみの誤り遷移が可能であることが明らかである。このチャネルの場合に、このチャネル変調を使用すると、各対の第1のビットについてのチャネル遷移確率図は図4に示すものになり、一方、各対の第2のビットについてのチャネル遷移確率図は図5に示すものとなる。しかし、各対の第1および第2のビットで可能な誤りは対になっているので、図17の誤り遷移グラフを分解して図4および図5のグラフにすると、いくらかの情報が失われる。図17に基づく符号は、奇数のビット位置については図4、偶数のビット位置については図5に基づく2値の符号より高い情報量または良好な誤り訂正検出を有することができる。図16および図17で表す4値チャネルまたはメモリでもたらされる環境では、チャネル符号化とチャネル変調がまとめて扱われ、利便である。例えば、この場合、2値のソースデータのkビットの集まりをまとめてデータ語にすることができ、各データ語を符号化してkビットの符号語にすることができる。この場合は、kが偶数で、符号化時にチャネルメモリの誤り特性を考慮する限り、符号チャネル組み合わせの所望の誤り訂正および検出特性を得ることができる。図18に、チャネルメモリの誤り注入特性に基づいて所望レベルの誤り訂正性能を満たす符号、すなわちデータ語と符号語間の対応関係を見つける方法を示す。このアルゴリズムは、互いから適当な変形ハミング隔たりを有する符号語を見つけるために符号語空間を探索し、次いでそれらの符号語をデータ語に割り当てる。アルゴリズムはステップAで開始し、符号のパラメータ、例えば符号語の大きさ、所望または目標とする変形ハミング符号語間隔、および、得られる符号の変形ハミング符号語距離、符号語内の各ビット位置またはビット位置のグループのチャネル誤り遷移特性を決定する。これらの特性の一部は、チャネルメモリの特性、システム全体の誤り率の目標、およびメモリ編成の制約によって決まりうることが理解されよう。そのため、それらのパラメータをこのアルゴリズムに入力し、アルゴリズムは、そのパラメータを条件として符号を見つける。上記のTableEをステップAで使用して、要求される誤り訂正および検出特性を、目標とする変形ハミング符号語間隔として定量化することができる。一般には、符号語が大きいほど、所定のレベルの誤り検出および訂正を実現するためのオーバーヘッドが低くなり、結果得られる符号の効率が高くなる。さらに、各シンボル位置のチャネル誤り遷移特性が不完全であるほど、不完全な特性で、完全な誤り遷移図を想定した同等の従来の符号よりも効率的な符号を容易にできる見込みが高くなる。ステップBで、可能な符号語の1つを選択し、第1の実際の符号語に指定する。見つかった可能な符号語のうち、互いからの最小の変形ハミング隔たりの基準を1つのグループとしてすべてが満たす符号語の実際の数の現在の個数として変数Jを維持する。この最初の符号語は無作為に選択するか、またはチャネルメモリの誤り特性の何らかの洞察に従って選択するか、または単にすべて0かすべて1などの単純な既知の開始符号語として選択するか、またはすべて0もしくはすべて1から指定された変形ハミング距離の符号語を選択するか、または何らかの他の基準で選択することができる。本発明は、第1の符号語を選択するどの特定の方法にも限定されない。第1の符号語の選択は、図18のアルゴリズムで見つかる符号語の集合に影響する。最終的な符号語の集合の中には他の集合よりも多くの符号語を持ちうるものがあり、また、一部は他の集合よりもハードウェア符号器または復号器内でより容易に実装できる可能性がある点で、最終的な符号語の集合の中には他の集合よりも好ましいものがある。1つの初期符号語が別の符号語より好ましいかどうかは、チャネルの誤り遷移図、実装の制約および方法、ならびに目標とする誤り検出および訂正のレベルに応じて決まる。第1の符号語は最終的なコード設計においては変数になるため、図18のアルゴリズムは、異なる第1の符号語およびまたは異なる候補選択アルゴリズムで複数回行って、符号語の集合の好ましさの単純な基準に従って、または符号語の集合好ましさの複数の単純な基準を集約したものに従って、得られたすべての符号の中で最も好ましい符号を選択する。本発明は、符号語の集まりを他の集まりに優先して選択するためのどの特定の基準または基準の集まりにも限定されない。ステップCで、検討対象としてまだ選択されていない見込み符号語の中から新しい候補符号語を選択する。ステップAと同様に、これもいくつかの異なる方式で行うことができる。例えば、内部ループの現在の反復についての候補符号語を無作為に選択する、最後の候補符号語から増分して選択する、選択された符号語からの変形ハミング距離または隔たりが小さい候補符号語を選択する、または何らかの他の方法が可能である。例えば、符号語を複数桁の整数、基数lと見なす場合、増分による方法ではcilcilを選択し、ciはi番目の候補符号語である。代替の方法は、その後のステップCの実行で、第1の符号語w1からdの変形ハミング隔たりを有するすべての候補符号語を選択し、次いで、符号語w2から変形ハミング隔たりがdであるすべての候補符号語を選択し、以後同様にして指定された符号語wjのリストが尽きるまで選択するものである。指定された符号語のリストが尽きた時にまだ選択されていない候補符号語が残っている場合は、無作為や増分などの何らかの他の方法により、ステップCで残りのすべての未選択候補符号語を順に選択することができる。その後のステップCの実行ですべての候補符号語を順に選択することからなる別の可能な方法は、まず第1の符号語から変形ハミング隔たりが1のすべての候補符号語を選択し、次いで、第1の符号語から変形ハミング隔たりが2のすべての候補を選択し、続いて第1の符号語から変形ハミング隔たりが3のすべての候補を選択し、以後同様にして最終的にすべての候補を選択するものである。考えられる他の方法は、対応する符号器または復号器の効率的またはコンパクトな実装を容易にする候補符号語を選択するものである。候補符号語を選択する順序は結果得られる符号とその実装の容易さに影響するため、実装の状況が異なれば、異なる選択順序または基準が求められる可能性がある。本発明は、2つ目以降の候補符号語を選択するどの特定の方法にも限定されない。ステップCで候補符号語ciが選択されると、その候補符号語ciを含む見込み符号の変形ハミング符号語間隔および変形ハミング符号語距離をステップDで求める。これは、候補符号語ciとすべての事前に指定された符号語wjとの間の変形ハミング隔たりを求め、その結果を目標変形ハミング符号語間隔と比較することにより行うことができる。候補符号語を含む見込み符号の変形ハミング符号語間隔が目標変形ハミング符号語間隔より小さくなるか、大きくなるか、または等しくなるかを判定する任意の代替法を使用することができる。事前に指定された符号語と現在の候補符号語間の変形ハミング隔たりの判定は、上記のように、許される誤り遷移に基づく。同様に、候補符号語ciを含む見込み符号の変形ハミング符号語距離は事前に求めても、または当業者に知られる任意の方法で見込み符号の変形ハミング符号語間隔の判定と並行して行ってもよい。ステップEで、すべての事前に指定された符号語からの候補符号の変形ハミング隔たりと、候補符号語から事前に指定された符号語各々までの変形ハミング距離の両方を、生成しようとする符号の目標最小変形ハミング符号語間隔および目標最小変形ハミング符号語距離と比較する。変形ハミング隔たりと変形ハミング距離のどちらかが、それぞれ目標最小変形ハミング符号語間隔および目標最小変形ハミング符号語距離以上である場合は、ステップFで候補符号語ciを実際の符号語wjに指定する。変形ハミング隔たりが目標最小変形ハミング符号語間隔より小さい場合、または最小のハミング距離のどちらかが目標最小変形ハミング符号語距離より小さい場合は、候補符号語ciは拒否され、符号語にはならない。処理はステップGに進む。ステップGで、初期パラメータを満たすのに十分な数の符号語が指定されているか、または十分に多くの見込み符号語が拒否されており、所期パラメータを満たす符号を生成することができない場合、またはすべての見込み符号語が検討された場合は、符号生成処理が完了する。処理が完了した場合、処理はステップCに戻って新たに候補符号語を選択し、評価する。処理が完了し、十分な数の符号語が指定されている場合、処理はステップHに進み、指定された符号語を一対一の対応でデータ語に割り当てる。処理が完了し、十分な数の符号語が指定されていない場合は、目標特性を満たす符号が見つからなかったという意味で処理は不成功で終了する。処理は、任意で、初期パラメータを変更して制約を緩くすることにより、新たにステップAから開始してもよい。または別の第1の符号語を選択することにより新たにステップBから開始してもよい。ステップHで、一対一の対応でデータ語を符号語に割り当てる。これは、両方の集合を順に移動して、連続した符号語を連続したデータ語に割り当てることにより行うことができる。あるいは、割り当て動作は無作為に行ってもよい。あるいは、割り当ては、増分的に、得られるチャネル符号器およびチャネル復号器の実装を考慮して行って、それら両装置の一方、または他方、または両方のより効果的な実装が得られるように行ってもよい。あるいは、割り当ては、反復的に行って、複数の割り当てを試し、実施し、符号器、復号器、またはその両方の最も望ましい実装をもたらした割り当てを最終的に選択してもよい。本発明は、データ語への符号語の割り当てを行うどの特定の方法にも限定されない。別の実施形態では、図18の方法を、当技術分野で知られる論理最適化および論理合成の方法と組み合わせて、時間、面積、およびまたは電力の点で効率的な特定の状況のための符号を見つけるために、複数の符号とその符号器および復号器の実装を反復的に、または並行して探す。図18の方法の動作を説明するために、図17の誤り遷移図で説明した4値チャネル、4シンボルの符号語の大きさ、および4の最小の変形ハミング符号語間隔に基づく例を挙げる。この例では、TableJに、方法がとるステップと各ステップで行われる動作を示す。TableKに、TableJに示した図18の方法で決定される符号を示す。詳細には、これは、図17に示す誤り遷移図を持つ4値チャネルのための符号である。これは、電圧または電荷が中点値に向かってのみ低下する傾向がある、1つのセルまたは期間につき2ビットを記憶もしくは送信するメモリおよびチャネルに適用可能な符号を表す。この符号は、4の最小変形ハミング符号語間隔を持ち、すなわち、1ビット誤り訂正2ビット誤り検出符号である。詳細には、図18の方法では、すべてが互いから少なくとも3の距離にある20個の可能な符号語を見つける。TableKは、それら20個の符号語のうち16個が図18のステップHでソースデータストリームにある16個の可能な4ビットのデータ語に割り当てられることを示す。したがって、4つの4値シンボルで、各ニブルを完全にSECDED保護して、4ビットのソースデータを記憶または送信することができる。本発明は、ステップMで行われるデータ語への符号の特定の割り当てに依存せず、効率的なまたは望ましい符号器およびまたは復号器をもたらす割り当てであれば適当である。チャネルの特性が、各シンボル位置で発生しうる誤りが多くとも1つであるような場合は、ある符号語から2以上の距離以内にある可能な受信語の数は少なくなる。例えば、図17に示す誤り遷移図を持つ4値チャネルの場合、受信語caaaは、符号語aaaaからハミング距離が2であり、それらの誤りは両方とも第1の誤り位置で発生する。その結果、TableJに示すように、候補符号語daaaは、符号語aaaaからの変形ハミング隔たりが3であるため、可能な符号語にはならない。しかし、同じ符号語内で第2の誤りが発生する確率がゼロであるか、または送信または記憶された語の中の別のシンボルで第1の誤りが発生する確率より大幅に低い場合は、1つのシンボル中の複数の誤りがそのシンボル中のゼロ個の誤りまたは1つの誤りから正しく区別されない場合でも、検出されていない誤りの集まりの全確率がなお許容閾値より低い可能性がある。この例では、1つのシンボル中の複数の誤りが符号の形成時に考慮されない場合には、符号語aaaaから、発生しうる受信語caaaまでの変形ハミング距離が無限になる。その結果、TableJの項目12における符号語aaaaと候補符号語daaaとの間の変形ハミング隔たりが無限になり、図18の方法のステップFに進むことにより、候補符号語daaaを第2の符号語に指定することができる。緩やかにしたこの誤り条件のセットの下では、図18の方法で、SECDED符号の基準を満たす符号語が24個見つかる。それらの24個の符号語とデータ語への可能な割り当てをTableLに示す。さらに、符号語の大きさmが8シンボルである場合は、図18のアルゴリズムで、図17の誤り遷移図を仮定してSECDED符号を探す際に、1シンボルにつき複数の誤りが発生することを考慮する場合には1762個の可能な符号語が見つかり、1シンボルにつき複数の誤りが発生することを考慮しない場合には1866個の可能な符号語が見つかる。両方の場合とも、符号語の大きさmが4の時には、図18の方法で17個以上の可能な符号語が見つかることは重要である。符号の情報容量を符号語数のlog2と考える場合、2個の4シンボル符号の情報容量は、1シンボルにつき複数の誤りが発生することを考慮する場合としない場合とでそれぞれ4322ビットおよび4585ビットになる。チャネルが4値チャネルであるため、4シンボルを送信または記憶するために必要な正味チャネル容量は8ビットである。8ビットの送信または記憶ビットを使用するSECDEDハミング符号の情報量が4ビットであることは当技術分野でよく知られている。TableKおよびTableLに示す本発明の符号はどちらも、同等のSECDEDハミング符号に比べて高い効率を有する。ステップFに関して、代替法では、事前に選択されなかったすべての候補符号語で、新しい符号語wjからのハミング隔たりがdまたはそれ未満である符号語は、それら自体が符号語になるには既存の符号語に近すぎると標識を付けることができる。そのような符号語は、その後のステップCの実行で再度選択されないように、基本的にすでに選択された旨の標識を付けるか、または後にステップCで選択された時にステップEですぐに拒否できるように標識を付けることができる。より迅速な全体符号の発見を容易にするための他の最適化が本発明の文脈内で可能である。本発明の実施形態は、基本的に不完全な誤り注入特性を持つ他のメモリ装置および通信装置にも適用可能であることが理解されよう。他のメモリ装置および通信装置は、複数の誤り注入機構を有する可能性があり、そのうちの1つまたは複数は他の誤り注入機構よりもはるかに確率が高い。装置またはチャネルを不完全な誤り注入特性を持つものとしてモデル化するために、確率が大幅に低い機構は無視してもよい。上述の詳細な説明では、本発明について特定の実施形態を参照して説明した。本発明のより広い主旨および範囲から逸脱することなく、開示される実施形態に各種変更を加えることが可能であることは明らかであろう。したがって、上記実施形態の説明と図面は、制限的ではなく、例示的な意味で見なすものとする。