(57)【特許請求の範囲】
【請求項１】
第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に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶および通信の用途に適用される誤り検出および訂正符号に関し、より詳細には、発生する可能性のある誤りが記憶または通信対象のデータに関連する状況で、誤りを効率的に検出および/または訂正する方法、装置、およびシステムに関する。
【背景技術】
【０００２】
従来、誤り検出および訂正符号は、記憶データや通信データに誤りを生じさせる物理的現象および電気的現象がある時に、データに誤りが生じる確率を下げるために電子システムで使用されている。例えば、図1に通信システムの典型的な概念化を示す。通信システムの基礎となるモデルは、送信元101から送信先109にシリアルデータストリームを送信する必要があるというものである。ソースデータはまずソース符号器102にかけられ、元のシリアルソースデータストリームXの冗長性を除去することにより圧縮される。チャネル符号器103は、チャネル符号器103とチャネル復号器107の間で生じる誤りの検出を容易にし、場合によってはそのような誤りの訂正も行えるように、管理された体系的な方式で冗長性を付加する。誤りは、一般に、ノイズや他の物理的または電気的現象が原因でチャネル105から出るシンボルストリームr'をチャネル105に入るシンボルストリームv'と異なるものにしてしまう完全でないチャネル105によって生じることが想定される。そして、典型的には、チャネル符号器103でデータストリームに誤り訂正符号(ECC)を挿入する。
【０００３】
チャネル変調器104は、入ってくるビットストリームvをチャネル105の電気信号に変換するものである。2値のデジタルチャネルの場合、変調器は単純なものであり、典型的には、符号化データストリームvを変化させずに直接チャネルに渡し、v'=vとなるようにする。しかし、3つ以上の元を持つシンボルの集合から選択されたシンボルを一度に1つずつ通信するチャネルがある。例えば、通信チャネルが各データ送信期間に4つの電圧の1つを送信できる場合、シンボルの集合の大きさは4になる。一般に、送信シンボルv'[j]は、シンボルの集合S={s0, s1, s2, ...sl}から選択され、この場合シンボルの集合の大きさはlである。当業者は、特に例えば位相偏移キーイング(PSK)振幅変調や、1セルマルチビットのフラッシュメモリまたはDRAMメモリを使用するチャネルは多数あることを理解されよう。そのような場合、チャネル変調器104は、2ビット分の入力ストリームvを取得して、シンボルストリームv'の1つのシンボルを選択する。2値のデジタルチャネルの場合は、シンボルストリームv'を構成するシンボルは、それを表すのが電流であっても、電圧、電荷、または他の何らかの数量であっても、容易に2進数字0および1に対応付けることができる。2値チャネルでは、シンボルの集合の大きさl=||S||は2である。この対応付けに照らすと、上記のように、この場合v'は通例vと同じと見なすことができるが、他の関係も可能である。一般的な代替法の1つは、例えばv'をvの補数に等しくするものである。
【０００４】
下記で述べるように、シンボルの集合Sの大きさに関係なく、ノイズまたは他の原因でチャネルに生じる誤りにより、通信または記憶対象の1つのシンボルが別のシンボルに変化する。
【０００５】
チャネル復調器106の役割は、受信シンボルストリームr'を2値の受信符号化データストリームrに変換することである。チャネルによってシンボルストリームに生じた誤りの種類に応じて、受信される符号化データストリームrは、符号化データストリームvに近いが全く同じではない複製となる。ただし、rとvは、必ずそうとは限らないが時間的にずれている可能性が高い。時間ずれの量は、当該チャネルが通信チャネルであるかどうかによって異なり、通信チャネルの場合、時間遅延は、変調器104、チャネル105、および復調器106を通る際の伝搬遅延に等しい。チャネルがメモリ装置である場合は、vとr間の時間ずれは、特にシンボルストリームv'がメモリの製造時(例えばCDやDVDなど)にメモリに埋め込まれる場合には大きくなる可能性がある。
【０００６】
チャネル復号器107の役割は、訂正されたデータストリームwを生成するために、チャネル符号器103で挿入された冗長性を取り除くことである。誤り訂正符号がチャネルの特性を考慮して適切に設計されている場合は、受信シンボルストリームr'に生じた誤りが解消されて、復号データストリームwのすべてのビットが圧縮データストリームuの対応するビットと全く同じである確率が非常に高くなる。誤り訂正符号の中には、その符号で訂正することができない種別の誤りを検出できるものがある。そのような符号を使用する場合は、場合によっては、検出可能であるが訂正することができない誤りが受信シンボルストリーム中に存在する時には訂正後のデータストリームに誤りがあることが分かっており、その知識を一般に制御機構に伝えて、情報を再生成および/または再送することができるまで、誤りのある訂正データが使用されないようにする。
【０００７】
工程の最終段階はソース復号器108であり、ソース符号器102でデータストリームに行われたデータ圧縮を解除して、理想的にはソースデータストリームxと全く同じである最終受信データストリームx'を生成する。しかし、多くの通信システムおよびメモリシステムはソース符号器/ソース復号器の対を含まない。そのような状況では、チャネル符号器103への入力は未処理のソースデータストリームになり、チャネル復号器107の出力が最終受信データストリームx'となり、それがデータの送信先109に送信される。
【０００８】
図2に、通信システムまたは記憶システムの簡略図を示し、このシステムにはソース符号器もソース復号器もなく、チャネルは2値のデジタルチャネルであり、よって送信されるシンボルは符号化データストリームのビットと同じである。したがって、チャネル変調器および復調器は、実質的にシステム全体にとって重要性のない通過点としての装置である。その結果、重要性のある唯一のブロックはチャネル符号器202およびチャネル復号器204となる。この図ではチャネル203を二進加算で表しており、機能的には単一の排他的ORゲートに相当する。このチャネルおよび誤りの概念化では、誤りストリームeは、符号化データストリームvと等しい長さの2値のビットストリームである。誤りストリーム中の「1」は、データストリームのそのビット位置にチャネルによって誤りが注入されることを意味する。二進の加算機能の性質は、誤りが存在するとデータストリーム中の0を1に変え、1を0に変えるというものである。このチャネルの概念化では、符号化データストリーム中の対応する位置にあるデータビットが0であるか1であるかに関係なく、誤りストリーム中の「1」が誤りを生じさせるという点で、データから独立している。また、誤りが生じる確率は、1つのシンボルから次のシンボルにかけて一定であると見なされる。この種のチャネルを二元対称チャネル(BSC)と呼ぶ。あるビット位置における誤りの確率が、1つ前のビット位置で誤りが発生した確率に関係するという概念を含むチャネルモデルは他にもある。そのようなチャネルは、間隔の狭い誤りのバーストが発生する。
【０００９】
図3に、図1の一般的な通信システムを簡略化した別の図を示し、この場合は記憶の応用例に合わせて用語の名前を変更している。この応用例では、通信チャネルがメモリ装置303に置き換えられる。メモリ装置は、例えば1つまたは複数のCDやDVDなどの物理的に静的な装置、または例えば動的ランダムアクセスメモリ(DRAM)、フラッシュメモリ、読み出し専用メモリ(ROM)などの半導体メモリなどの動的な装置、または機能の一部としてある期間にわたって情報を記憶する他の方式の装置である。この概念化では、チャネル符号器をECC符号器302と呼ぶ。符号化データストリームは、製造時に1度のみ、使用の現場で1度のみ、または装置が使用される際に繰り返しメモリ装置に書き込まれる。受信データストリームrは一般に、メモリ装置の詳細に応じて、何らかの種類の読み出し動作を介してメモリ装置から取り出される。ランダムアクセスメモリ装置の場合、データは書き込まれた順序で取り出す必要はなく、書き込まれるシンボルと読み出されるシンボルとの対応付けは、暗黙的または明示的にアドレスによって提供される。ECC復号器は、メモリコントローラの内部、メモリ装置の集積回路の内部、またはその間のいずれかの位置に単体の装置として、またはメモリコントローラとデータの送信先の間に、制限なく存在することができることが理解されよう。
【００１０】
メモリ装置は、通例、メモリセルに情報を記憶する。大半の種類のメモリは、各メモリセルに1ビット分の情報を記憶する。そのような装置では、シンボルの集合は二進の数字0と1の集合であり、対応するチャネル変調器はない。例外は、多くの半導体メモリタイプでは符号化データビットv[i]をメモリセルに搬送する信号経路に反転があることであり、そのため、記憶されるシンボルが何らかの形で記憶セルの一部またはすべてについて符号化データビットから反転される。
【００１１】
より大きなシンボルの集合にある複数のシンボルを各メモリ位置に記憶するメモリ装置も存在し、市販されると共に当技術分野の文献に提案されている。例えば、多くのマルチレベルのフラッシュメモリ装置は、各メモリセルを4つのレベルの1つに設定することにより、2ビット分の符号化データストリームを各メモリ位置に記憶する。そのような装置では、チャネル変調器とチャネル復調器に相当するもの、すなわち、符号化データビットと記憶されるシンボルとの間の対応付けと、それに対応する、記憶シンボルと受信データストリームから読み出されるビットr[i]との対応付けを管理する回路またはアルゴリズムは、メモリコントローラの一部分であり、メモリコントローラは、メモリ装置からの読み出しと場合によっては書き込みを担う。
【００１２】
当業者は、誤り訂正符号およびチャネル変調の方式は特定チャネルの誤り特性を考慮して設計され、特定のメモリシステムまたは通信システムを設計する際には各種の符号タイプが選択肢として存在することを理解されよう。そのような誤り訂正符号は、一般に、訂正データストリームwに誤りが存在する確率をゼロに下げることはない。単に、確率を主観的に許容できる誤り率より低いレベルまで大幅に下げるに過ぎない。
【００１３】
図4に、上記で図2を参照して説明した2値の対称チャネルの確率遷移図を示す。2値の対称チャネルは、符号化データストリームのビットv[i]を、チャネルを通じて、受信データストリームのビットr[i]としてチャネル復号器に渡す。任意のビット位置において誤りが生じる確率、すなわちr[i]がv[i]と異なる確率はpであり、よって、そのビットが破損せずにチャネルを通過する確率は1-pとなる。チャネルは、符号化データビットが0であるか1であるかに関係なく誤りの確率が同じである点で対称である。
【００１４】
情報理論および符号化理論の多くは、2値の対称チャネルモデルに固有の想定に基づいて構築されている。しかし、現実には、多くの通信チャネルおよびメモリ装置は誤りの特性に関して非2値であるか、または対称でない。実際には、受信データストリームrに誤りを注入させる現象の多くは、チャネル上の異なるシンボルに選択的に作用する。例えば、2値チャネルの特性が、一方のシンボルは常に誤りなく渡されるが、他方のシンボルは確率pで一方のシンボルに変化するような場合、そのチャネルをZチャネルと呼ぶ。図5に、そのようなチャネルの確率遷移図を示し、この場合は0は常に変化せずに渡され、1は確率pで0に変化する。すべての誤りが発生しうるとは限らない誤り確率遷移図(図5など。図5では0から1に変化する誤りは可能性がないか、または考慮から除外してよいほど可能性が低い)を「不完全(incomplete)」と呼ぶ。いくつかの種類の誤り遷移のみを生じさせ、他の種類の誤り遷移は生じさせない誤り注入機構を持つチャネルおよびメモリも同様に「不完全」と呼ぶ。
【００１５】
図6に別の不完全チャネルの確率遷移図を示す。この場合は、チャネルは、3つのシンボルからなるシンボルの集合から選択したシンボルを一度に1つ送信することができる。それら3シンボルを伝達するために使用される物理的または電気的特性はチャネルの誤り特性の抽象的な分析には関連しないため、シンボルは単純にa、b、cとする。これらのシンボルは、特に、異なる電圧、電流、電荷、または位相で表すことができる。例えば、シンボルaは正の電圧、シンボルcは負の電圧、シンボルbは地電圧に近い電圧で表されることが考えられる。この例示的チャネルでは、シンボルbは常に変化せずにチャネルを通過し、一方、シンボルaおよびcはそれぞれ確率pおよびqでシンボルbに変えられる。この場合は、3値チャネルであるため、チャネル入力に入力されるシンボルは、送信シンボルストリームv'[j]中の項目であり、チャネルを出るシンボルは受信シンボルストリームr'[j]中の項目である。図6に示すような確率遷移図を特徴とするチャネルは、シンボルの集合の大きさが3以上であり、少なくとも1つの発生しうる誤り遷移の確率が実質的にゼロである点で、非2値の不完全チャネルと呼ぶ。このチャネルは、想定しうるすべての誤りが同じ発生確率を持つ訳ではない点で非対称でもある。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
送信信号中の誤りを検出し、訂正する能力は、使用される符号のハミング距離として表すことができる。任意の2つの符号語間のハミング距離(「距離」とも呼ぶ)は、それら2つの符号語が互いと異なるシンボル位置の数である。例えば、2つの2値の符号語「0011010」と「0010110」は、2箇所で異なるため、ハミング距離は2となる。同様に、符号語「abacdda」と「acdadda」は、3つのシンボル位置で異なるため、ハミング距離は3となる。完全なチャネル(シンボルの集合にあるすべてのシンボル対の間のすべての誤りが発生しうる)で使用する符号でt個の誤りを訂正し、t+1個の誤りを検出できるようにするには、すべての符号語の最小の隔たりが少なくとも2t+2でなければならないことが理解される。詳細には、よく知られた1ビット誤り訂正、2ビット誤り検出(SECDED)の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つの値(0または1)が許されるため、2となる。
【００６１】
用語「n」を使用して、シンボルまたはビットを単位とした符号語の大きさを表す。用語「符号語」は、1つまたは複数のデータ語を表すために割り当てられ、任意で誤り検出または訂正情報を含んでいる、所定長さの符号シンボルの連続を意味する。
【００６２】
用語「k」を使用してデータ語の大きさを表す。データ語は、共に符号化されてチャネルシンボルまたは記憶ビットとなるビットまたはシンボルの集まりである。用語「データ語」は、1ビットまたは複数のビットのソースデータを表す、所定長さのシンボルの連続を意味する。
【００６３】
用語「p」および「q」を使用して、送信または記憶されるシンボルストリームの任意のシンボル位置で誤りが生じる確率を表す。
【００６４】
用語「シンボルのn組」(例えば「シンボルの3つ組」)は、ソースデータの1ビットに対応するか複数ビットに対応するかに関係なく、データまたは符号のn個のシンボルからなる連続を意味する。
【００６５】
符号の効率は、データ語kの大きさを符号語nの大きさで割った比として測定される。すなわち、符号の効率は、所与の数の未符号化データビットを送信または記憶するために必要な符号化データのビット数と、その未符号化データのビット数との比である。データ集合または送信シンボルの集合のいずれかが非2値の場合は、対応するnまたはkにそのシンボルの集合の大きさを乗算する。符号化データの場合は、シンボルの集合の大きさを「l」と表す。したがって、データ語が2値であり、送信(または記憶)されるシンボルストリームが非2値の場合は、符号の効率はk/n*lとして算出される。
【００６６】
用語「データストリーム」または「シンボルストリーム」を使用して、純粋な1ビット幅のシリアルストリームから、多数のシンボルが同時または並行に通信または記憶されるマルチビット並行編成にわたるすべての方式の通信または記憶機構を表す。さらに、1つまたは複数のメモリ装置を含むチャネルの場合は、符号化シンボルストリームが任意の順序でメモリの特定のアドレスに書き込まれる順番と、それらのアドレスから情報が読み出されて受信データストリームまたはシンボルストリームを形成する順番との対応付けは必ずしも存在しない。さらに、1つの入力および出力を持つブロックとしてメモリ装置303を図示することは、マルチポートメモリへの本発明の適用性を何ら制限するものではないことが理解されよう。本発明の実施形態は、非対称の誤り注入特性を示すすべての幅および編成のチャネルおよびメモリ、ならびに/または1つの記憶セルもしくは位置につき2バイナリビット以上の情報を記憶する非2値チャネルまたはメモリに適用することができる。特に、本発明は、データの符号化および復号がメモリ内に位置するか、またはメモリコントローラ内に位置するか、またはシステム内のいずれか他の場所に位置するかに関係なく、メモリシステム内のメモリ装置へのデータの書き込みおよび読み出しのために共用データアドレスおよび/または制御信号経路、ならびに共通もしくは共有コントローラ回路を持つ従来編成のメモリシステムに特に適用することが可能である。
【００６７】
本願では、用語「変形ハミング距離」は、1対の符号語に関して、第1の符号語から第2の符号語に移動するために特定の可能なシンボル遷移図(例えば図11に示す遷移図など)を横断するために必要な、許容される最小の数の誤りを意味するものとする。変形ハミング距離が従来のハミング距離と異なるのは、許容される誤り遷移に対応する違いのみを考慮する点である。すなわち、変形ハミング距離は、第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回の誤り遷移(計4回)、例えばaaa→baa→bba、およびcca→bca→bbaを介して共通の3つ組「bba」に変えることができるので、4の変形ハミング隔たりを持つ。
【００７１】
本発明を制限ではなく例として添付図面の図に示す。
【図面の簡単な説明】
【００７２】
【図１】本発明の態様を適用することができる第1の終端間通信システムの図である。
【図２】本発明の態様を適用することができる第2の終端間通信システムの図である。
【図３】本発明の態様を適用することができるメモリシステムの図である。
【図４】2値の対称チャネルの場合の典型的な遷移確率図である。
【図５】非対称で不完全な誤り遷移確率を持つ2地チャネルの遷移確率図であり、この種の図は同義で誤り遷移図またはシンボル遷移図と呼ばれる。
【図６】3つのシンボルを記憶または送信することが可能な3値チャネルの遷移確率図であり、誤り遷移確率が非対称であり、グラフが不完全である遷移確率図である。
【図７】対称3値チャネルで送信される1つのシンボルに発生しうる誤り遷移を示す図である。
【図８】不完全な3値チャネルで送信される1つのシンボルに発生しうる誤り遷移を示す図である。
【図９】図6に示す誤り遷移を持つ不完全な3値チャネルで送信される1つのシンボルに発生しうる誤り遷移を示す図である。
【図１０】図6に示す誤り遷移を持つ不完全な3値チャネルで送信されるシンボルの対に発生しうる誤り遷移を示す図である。
【図１１】図6に示す誤り遷移を持つ不完全な3値チャネルで送信される3つのシンボル語に発生しうる誤り遷移を示す図である。
【図１２】各シンボル期間に3つのシンボルのうち1つを送信するように構成されたチャネルで送信されるシンボルについてのデータアイ(eye)を示す図である。
【図１３】従来技術のDRAMメモリセルの図である。
【図１４】DRAMの記憶セルにおけるセル電圧の3つの電圧範囲への3つのシンボルの割り当てを示す図である。
【図１５】VcellがVplateに短絡した3値DRAMメモリセルの場合の確率遷移図である。
【図１６】DRAMの記憶セルにおけるセル電圧の4つの電圧範囲への4つのシンボルの割り当てと、シンボルへのソースデータビット対の4通りの可能な割り振りを示す図である。
【図１７】4つのシンボルを記憶または送信することが可能なチャネルの遷移確率図であり、誤り遷移確率がデータに依存する場合の図である。
【図１８】非対称の誤り確率を持つチャネルで使用する符号を特定するアルゴリズムを説明する図である。
【発明を実施するための形態】
【００７３】
ブロック符号は、冗長性のシンボルを追加してn個のシンボルの長さの符号語を形成することにより、ソースデータストリームuのk個のシンボルからなるグループを保護する、誤り訂正符号のグループである。ソースデータストリームにあるk個のシンボルからなるグループはデータ語となる。データシンボルと符号化シンボルが同じシンボルの集合から選択された場合、基本的に誤りからの保護(検出および/または訂正)をもたらす冗長シンボルの数はn-kになる。2値のブロック符号は、2値のソースデータストリームに適用されて、ソースデータストリームを論理的、時間的、または物理的にkビットのデータ語に分割する。各データ語はnビットの符号語に符号化され、チャネル変調器に送られてm個のシンボルに符号化され、mシンボルの長さの送信符号語を生成する。2値チャネルで2値のソースデータストリームの場合は、m=nとなる。あるいは、誤りの符号化および変調(シンボルへのビットグループの分割)は、同時に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値チャネルに一般化することができ、q>2であることを理解されたい。3値チャネルは、図6に示すように、送信シンボルの集合の大きさが3に設定されるチャネルである。図9に、1つのシンボルの3つの値の完全な集合を示す。一部のシンボルを囲む網掛けをした灰色の枠で示すように、1つの可能な符号はシンボル「a」および「c」のみを含む。シンボル「b」が受信されると、誤りが発生していることになるが、元の送信シンボルは特定することができず、このチャネルの可能な誤り遷移を考えると、シンボル「b」はシンボル「a」およびシンボル「c」の両方から1の変形ハミング距離である。本発明の実施形態では、図10に、図6の誤り特性を持つ3値チャネルで送信されるシンボルの対から構成される符号を示す。可能なシンボル対は9つある。ソースデータビットの2つの2値の値(0または1)を表す符号語としてシンボル対「aa」および「cc」が選択された場合は、すべての可能な1ビット誤りを訂正し、すべての可能な2ビット誤りを検出することができる。この符号をTable A(表1)に示す。
【００７７】
【表１】
0005726312.tif 000002
【００７８】
ソースデータビットと符号語との対応付けは完全に任意であり、また、符号語(「aa」および「cc」)へのソースデータビット値(0および1)の2通りの割り当てのどちらでも同じ最終的結果が得られることを理解されたい。
【００７９】
また、Table A(表1)の「解説」欄で「発生の可能性なし」と表示された受信符号語は、任意の可能な符号語からの誤り遷移に基づく図9の誤り遷移図で想定されない受信符号語を表すことも理解されたい。特定の状況では、誤り遷移図で具現化されるものの他に、恐らくは低い確率の他の誤り機構がある可能性がある。通例、そのような誤り機構は、防御対象となる主要な誤り機構に比べてはるかに確率が低い。符号の基礎となる誤り遷移図で顕在化していない誤り遷移を発生させる誤り機構は、その符号では訂正できない場合がある。そのような状況では、「発生の可能性なし」と表示された受信符号語は訂正不可能な誤りと見なされる。また、単独で、または他の誤り機構と組み合わさって、1つの符号語を別の符号語に変えることが可能な他の誤り機構がある可能性もあり、そのような誤りまたは誤りの組み合わせは検出不可能な誤りの種別に分類される。
【００８０】
シンボル対「bb」も符号語である場合は、この符号は、3つの有効な符号語を持つ、1ビット誤り検出、1ビット誤り訂正符号になる。各シンボル対は、1ビットのみのソースデータを送信することができるが、シンボル対の集まりを組み合わせて、より多くのソースデータビットを符号化することもできる。Table B(表2)に、2つのシンボル対をグループ化することで、3ビットのソースデータを送信することができ、各シンボル対で1つの誤りを検出および訂正することが可能な符号が生成されることを示す。
【００８１】
【表２】
0005726312.tif 000003
【００８２】
3ソースビットを2つのシンボル対に変調するこの変調では、8通りのソースビットの組み合わせと9通りの有効符号語の組み合わせがある。符号語の組み合わせの1つは使用しないままにしておく。ソースデータビットの3つ組をシンボル対に変調する特定の変調は任意であり、他の考慮事項に応じて選択できることを理解されたい。より多くのシンボル対を共にグループ化するこのパターンでは、各シンボル対で1ビットの誤りを検出し訂正することが可能な追加的なより高次の符号が生成され、それにより、より多くのソースビットを符号化し、符号の効率を向上できることも理解されよう。このような符号のいくつかの例の特性をTable C(表3)に示す。シンボル対の値へのソースデータビット値の変調は任意であり、それに対応する変調器および復調器は従来の論理最小化技術を使用して設計できることを理解されたい。また、シンボル対の一部である個々のシンボルは、シンボルを交互に配置するか、または他の形で入れ替える、もしくは並び替えることにより時間的または空間的に離してよく、その種別の符号で検出することができない誤りの対が、論理的、物理的、または時間的に隣り合わないようにし、それにより同じシンボル対内で複数個の誤りが発生する確率を下げることも可能であることを理解されたい。
【００８３】
【表３】
0005726312.tif 000004
【００８４】
図11に、3つのシンボルからなる符号語の場合に、図6に定義される3値チャネルを仮定したすべての発生しうる誤り遷移を示す。この場合、5つの符号語からなる符号は、Table D(表4)に示すように、3つのシンボル内のすべての1ビット誤りの訂正とすべての2ビット誤りの検出を可能にすることができる。
【００８５】
例えばTable D(表4)を参照すると、受信されたシンボルの3つ組「bab」は、両方の符号語「aaa」および「cac」から2つの誤り分だけ離れていることに注目されたい。具体的には、符号語「aaa」は、第1の誤り(a→b)で「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となる。
【００８７】
【表４】
0005726312.tif 000005
【００８８】
この符号の誤り検出および訂正の性質を理解するために、集約的特性を考える。上記の例では、「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つの誤り(a→b)および(b→c)は両方とも許され、このチャネルの定義内では、同じシンボル位置に連続して発生することができる。別の実施形態では、同じ誤り遷移図を持つ異なるチャネルまたはメモリは、送信または記憶される各シンボルに多くとも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∈Sn, c≠a, c≠bについて、mHs(a, b)=min(mHd (a, c) + mHd (b, c))
によって与えられ、mHs(a, b)は、符号語「a」と符号語「b」間の変形ハミング隔たりであり、mHd(a, b)は、符号語「a」から符号語「b」までの変形ハミング距離である。
【００９４】
変形ハミング隔たり関数は、mHs(a, b)=mHs(b, a)である点で対称である。
【００９５】
1つの符号全体の変形ハミング符号語間隔は、その符号中の各符号語対間の変形ハミング隔たりのうち最小のものである。1つの符号全体の変形ハミング符号語距離は、その符号中の各符号語対の間の変形ハミング距離のうち最小のものである。代数的には、これらは
すべてのa, b∈C, C⊆Sn, a≠bについてmHcws (C) = min (mHs (a, b))
すべてのa, b∈C, C⊆Sn, a≠bについてmHcwd(C) = min (mHd (a, b))
によって与えられ、Cは、Sn中のn組の集合からなる符号である。
【００９６】
符号の変形ハミング符号語間隔が4の場合は、すべての非符号語は、1)1つの符号語からは1つの誤りだけ離れており、すべての他の符号語からは少なくとも3つ以上の誤りだけ離れているか、2)1つの符号語からは2つの誤りだけ離れており、すべての他の符号語からは3つ以上の誤りだけ離れているか、3)2つ以上の符号語から2つの誤りだけ離れているか、または、4)すべての符号語から3つ以上の誤りだけ離れているか、のいずれかになる。また、各符号語がすべての他の符号語から少なくとも3の変形ハミング距離だけ離れている場合は、受信された語が符号語であれば、その語は、異なる符号語に1つまたは2つの誤りが注入された結果ではありえないことになる。
【００９７】
したがって、符号は、
mHcws (C)≧4かつ
mHcwd(C)≧3
であれば、不完全な誤り注入特性を持つチャネルまたはメモリにわたる1ビット誤り訂正、2ビット誤り検出(SECDED)符号になる。
【００９８】
これらの条件がすべて満たされる場合は、すべての受信符号語は、誤りのない送信および/または記憶の結果であると見なすことができる。上記第1の分類にあたるすべての受信された非符号語は、1ビット誤りの結果であると見なして差し支えなく、送信または記憶された符号語で誤りが訂正されると明確に判断することができる。第2の分類にあたるすべての受信された非符号語も同様に、曖昧さなしに訂正可能な2ビット誤りの結果であると結論付けることができる。第3の分類にあたるすべての受信された非符号語は、2ビット誤りの結果であるが、送信または記憶された元の符号語は明確に特定することができない。第4の分類にあたるすべての受信された非符号語は、一部は訂正可能な多ビット誤りの結果である可能性もあるものの、訂正不可能な多ビット誤りとして扱うことができる。
【００９９】
Table E(表5)に、上記と同じ論理に従った、符号により提供される誤り訂正および検出の度合いと、その符号の最小の変形ハミング符号語隔たりおよび最小の変形ハミング符号語距離との関係を示す。当業者には、ここに開示される論法に従って、Table E(表5)をより高い度合いの誤り訂正および検出に拡張する方法が理解されよう。
【０１００】
【表５】
0005726312.tif 000006
【０１０１】
誤り遷移図が不完全である結果、2つの符号語間の変形ハミング隔たりは、従来のハミング距離、すなわち2つの符号語が互いと異なっているシンボル位置の数の和よりも大きくなる可能性がある。Table D(表4)に示した先の例では、「aaa」と「acc」の間のハミング距離は、3つのシンボルのうち2つが異なるため2となる。それら2つの符号語は、要求される3のハミング隔たりを持たないため、従来の1ビット誤り訂正符号の一部にはなりえない。
【０１０２】
符号は、少なくとも4の変形ハミング符号語間隔を有する場合に1ビット誤り訂正および2ビット誤り検出符号となることができる。例えば、ある非符号語が第1の符号語から1の変形ハミング距離だけ離れており、第2の符号語から2の変形ハミング距離だけ離れている場合(すなわち符号の変形ハミング隔たりが多くとも3の場合)、チャネル復号器は、第1の符号語に伴う1ビットのシンボル誤りと、第2の符号語に伴う2ビットのシンボル誤りとを区別することができない。2つの符号語間の変形ハミング距離が従来のハミング距離より大きくなりうるのと全く同様に、符号の変形ハミング符号語間隔も、従来のハミング距離(すなわちすべての符号語対間のハミング距離のうち最小のもの)より大きくなる可能性がある。したがって、符号は、誤り遷移図が完全であるか、または符号が不完全な誤り特性を利用することができなかった場合には可能でないところまで誤りを訂正および/または検出することができる。
【０１０３】
Table D(表4)の例は、ハミング距離は4未満であるが、変形ハミング符号語間隔が4以上であり、変形ハミング符号語距離が3以上であるので、不完全な誤り遷移図がある場合に1ビット誤り訂正2ビット誤り検出する符号である。その理由から、Table D(表4)の符号は、その従来のハミング距離に基づくとSECDED符号とは見なされない。下記で、特定の誤り遷移図を考える時にハミング距離よりも大きい変形ハミング符号語間隔を持ち、ハミング距離のみの考慮から理解されるよりも多くの誤りを検出または訂正することができる符号の追加的な例を挙げる。
【０１０４】
引き続きTable D(表4)を参照すると、シンボルの3つ組「bbb」を符号語の集合から除外した場合には、すべての場合にシンボル「b」の受信は誤りを意味することに留意されたい。この場合、「a」から「c」またはその逆に遷移する確率が、シンボル「a」および「c」からシンボル「b」への許される誤り遷移の確率よりも大幅に小さくなるように、物理的なチャネル特性、例えば電圧、電流、または電荷レベルに適切なシンボルa、b、cを割り当てることができる。そのような例の1つは、一部のシンボル遷移の見込みが他のシンボル遷移よりはるかに低くなることを保証するように設計された変調器/復調器と組み合わせたチャネルであり、区別は、基本的に発生しえない遷移と、非ゼロの確率の誤り遷移との区別になる。
【０１０５】
このチャネルでシンボル対を組み合わせてより多くのソース符号ビットを同時に処理することが可能な大きな符号を生成するのと同様にして、複数のシンボルの3つ組を組み合わせて、より多くの符号語を持つ符号を生成することができる。Table F(表6)に、3つ組の同じ組み合わせを示す。ソースデータビットと複数のシンボル3つ組との間の任意の変調または対応付けを本実施形態で使用できることが理解されよう。
【０１０６】
【表６】
0005726312.tif 000007
【０１０７】
より大きなシンボルのグループを同様に組み合わせて符号語にすることができる。4以上の変形ハミング符号語間隔の場合は、符号は、1ビット誤り訂正、2ビット誤り検出符号となる。本発明の一実施形態は、図6に示す誤り特性を持つ3値チャネル上の4つのシンボル語に基づくSECDED符号である。この符号をTable G(表7)に示す。この符号は、1つのみの符号語で真ん中のシンボル「b」を使用する。この符号語は、3ソースデータビットをチャネル上の4つのシンボルに対応付ける変調を実装する能力を変えることなく、除去することができる。本発明の別の実施形態は、Table G(表7)に示すものと同じ符号を含むが、「bbbb」である符号語5は使用しない。Table G(表7)の最後の列に示すこの場合は、先の実施形態と同様に、シンボル「b」を使用する符号語はない。この実施形態では、シンボル「b」の受信を誤りを示すものとして使用することができ、誤りの性質を判定すると共に訂正可能な誤りを訂正するための追加的な分析を始動させる。この例は、ソースデータビットのグループの特定の値と特定の符号語との特定の対応付けに依拠しないことが理解されよう。
【０１０８】
【表７】
0005726312.tif 000008
【０１０９】
別の実施形態では、同じチャネルにある5つのシンボルからなるグループをグループ化して符号語にし、Table H(表8)に列挙する符号に従って符号化することができる。この実施形態では、この種別の他の符号と同じように、各符号語間の変形ハミング隔たりは少なくとも4であり、よってこの符号はSECDED符号になる。当該チャネルの誤り特性に基づく変形ハミング符号語間隔に基づく異なる特性を持つ他の符号も可能であることが理解されよう。
【０１１０】
【表８】
0005726312.tif 000009
【０１１１】
この種別の符号は、代わりに、各符号語中で6個以上のシンボルを使用してもよく、また、対応するチャネル符号器、チャネル変調器、チャネル復調器、およびチャネル復号器は、チャネルが通信チャネルであるかメモリ装置であるかに関係なく、公知の論理合成技術を使用して実装できることが理解されよう。また、チャネルを1つまたは複数のメモリ装置として実装する場合は、本発明の実施形態の個々の符号語はすべて1つのメモリ装置に記憶しても、または複数のメモリ装置に分散してもよいことも理解されたい。Table I(表9)に、図6で定義する特性を有するチャネルを仮定して、図18の方法で見つけられる符号の種類と有効性を示す。
【０１１２】
【表９】
0005726312.tif 000010
【０１１３】
図12に本発明の一実施形態の3値通信チャネルのアイダイアグラム(eye diagram)を示す。サンプル点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)のメモリセルの模式図を示す。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の符号化(図16では「I」と表記する)を、図17に示すチャネル遷移確率図に示す。この図は、記憶または送信される電圧が中央点に向かって低下することによって生じる誤り発生機構を表す。詳細には、シンボル「a」および「d」はそれぞれシンボル「b」および「c」に向かって劣化し、シンボル「b」および「c」は、共通の中間電圧に近づくことにより、実質上互いに向かって劣化する。この符号化チャネルビットのシンボルへのグレイ(Gray)コード符号化では、すべての誤り遷移が可能という訳ではない。符号化されたチャネルビットの対ごとに発生しうる誤りが4つある(11=>10; 10 =>00; 00 =>10; 01 =>00)。これらの誤りを個々のビットから見ると、対の第1のビットについてはすべての誤りが可能である(1 => 0および0 => 1)が、各対の第2のビットについては1つのみの誤り遷移が可能である(1 => 0)ことが明らかである。このチャネルの場合に、このチャネル変調を使用すると、各対の第1のビットについてのチャネル遷移確率図は図4に示すものになり、一方、各対の第2のビットについてのチャネル遷移確率図は図5に示すものとなる。しかし、各対の第1および第2のビットで可能な誤りは対になっているので(すなわち、各対では一度に1つの誤りしか発生しえない)、図17の誤り遷移グラフを分解して図4および図5のグラフにすると、いくらかの情報が失われる。図17に基づく符号は、奇数のビット位置
については図4、偶数のビット位置については図5に基づく2値の符号より高い情報量または良好な誤り訂正/検出を有することができる。
【０１１９】
図16および図17で表す4値チャネルまたはメモリでもたらされる環境では、チャネル符号化とチャネル変調がまとめて扱われ、利便である。例えば、この場合、2値のソースデータのkビットの集まりをまとめてデータ語にすることができ、各データ語を符号化してkビットの符号語にすることができる。この場合は、kが偶数で、符号化時にチャネル/メモリの誤り特性を考慮する限り、符号/チャネル組み合わせの所望の誤り訂正および検出特性を得ることができる。
【０１２０】
図18に、チャネル/メモリの誤り注入特性に基づいて所望レベルの誤り訂正性能を満たす符号、すなわちデータ語と符号語間の対応関係を見つける方法を示す。このアルゴリズムは、互いから適当な変形ハミング隔たりを有する符号語を見つけるために符号語空間を探索し、次いでそれらの符号語をデータ語に割り当てる。アルゴリズムはステップAで開始し、符号のパラメータ、例えば符号語の大きさ、所望または目標とする変形ハミング符号語間隔、および、得られる符号の変形ハミング符号語距離、符号語内の各ビット位置またはビット位置のグループのチャネル誤り遷移特性を決定する。これらの特性の一部は、チャネル/メモリの特性、システム全体の誤り率の目標、およびメモリ編成の制約によって決まりうることが理解されよう。そのため、それらのパラメータをこのアルゴリズムに入力し、アルゴリズムは、そのパラメータを条件として符号を見つける。上記のTable E(表5)をステップAで使用して、要求される誤り訂正および検出特性を、目標とする変形ハミング符号語間隔として定量化することができる。
【０１２１】
一般には、符号語が大きいほど、所定のレベルの誤り検出および訂正を実現するためのオーバーヘッドが低くなり、結果得られる符号の効率が高くなる。さらに、各シンボル位置のチャネル誤り遷移特性が不完全であるほど、不完全な特性で、完全な誤り遷移図を想定した同等の従来の符号よりも効率的な符号を容易にできる見込みが高くなる。
【０１２２】
ステップBで、可能な符号語の1つを選択し、第1の実際の符号語に指定する。見つかった可能な符号語のうち、互いからの最小の変形ハミング隔たりの基準を1つのグループとしてすべてが満たす符号語の実際の数の現在の個数として変数Jを維持する。この最初の符号語は無作為に選択するか、またはチャネル/メモリの誤り特性の何らかの洞察に従って選択するか、または単にすべて0かすべて1などの単純な既知の開始符号語として選択するか、またはすべて0もしくはすべて1から指定された変形ハミング距離の符号語を選択するか、または何らかの他の基準で選択することができる。本発明は、第1の符号語を選択するどの特定の方法にも限定されない。第1の符号語の選択は、図18のアルゴリズムで見つかる符号語の集合に影響する。最終的な符号語の集合の中には他の集合よりも多くの符号語を持ちうるものがあり、また、一部は他の集合よりもハードウェア符号器または復号器内でより容易に実装できる可能性がある点で、最終的な符号語の集合の中には他の集合よりも好ましいものがある。1つの初期符号語が別の符号語より好ましいかどうかは、チャネルの誤り遷移図、実装の制約および方法、ならびに目標とする誤り検出および訂正のレベルに応じて決まる。
【０１２３】
第1の符号語は最終的なコード設計においては変数になるため、図18のアルゴリズムは、異なる第1の符号語および/または異なる候補選択アルゴリズム(ステップC)で複数回行って、符号語の集合の好ましさの単純な基準に従って、または符号語の集合好ましさの複数の単純な基準を集約したものに従って、得られたすべての符号の中で最も好ましい符号を選択する。本発明は、符号語の集まりを他の集まりに優先して選択するためのどの特定の基準または基準の集まりにも限定されない。
【０１２４】
ステップCで、検討対象としてまだ選択されていない見込み符号語の中から新しい候補符号語を選択する。ステップAと同様に、これもいくつかの異なる方式で行うことができる。例えば、内部ループの現在の反復についての候補符号語を無作為に選択する、最後の候補符号語から増分して選択する、選択された符号語からの変形ハミング距離または隔たりが小さい候補符号語を選択する、または何らかの他の方法が可能である。例えば、符号語を複数桁の整数、基数l(シンボルの集合の大きさ)と見なす場合、増分による方法ではci+l=ci+lを選択し、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の最小の変形ハミング符号語間隔に基づく例を挙げる。この例では、Table J(表10)に、方法がとるステップと各ステップで行われる動作を示す。
【０１３３】
【表１０Ａ】
0005726312.tif 000011
【０１３４】
【表１０Ｂ】
0005726312.tif 000012
【０１３５】
Table K(表11)に、Table J(表10)に示した図18の方法で決定される符号を示す。詳細には、これは、図17に示す誤り遷移図を持つ4値チャネルのための符号である。これは、電圧または電荷が中点値に向かってのみ低下する傾向がある、1つのセルまたは期間につき2ビットを記憶もしくは送信するメモリおよびチャネルに適用可能な符号を表す。この符号は、4の最小変形ハミング符号語間隔を持ち、すなわち、1ビット誤り訂正2ビット誤り検出符号である。詳細には、図18の方法では、すべてが互いから少なくとも3の距離にある20個の可能な符号語を見つける。Table K(表11)は、それら20個の符号語のうち16個が図18のステップHでソースデータストリームにある16個の可能な4ビットのデータ語に割り当てられることを示す。したがって、4つの4値シンボルで、各ニブル(nibble)を完全にSECDED保護して、4ビットのソースデータを記憶または送信することができる。本発明は、ステップMで行われるデータ語への符号の特定の割り当てに依存せず、効率的なまたは望ましい符号器および/または復号器をもたらす割り当てであれば適当である。
【０１３６】
【表１１】
0005726312.tif 000013
【０１３７】
チャネルの特性が、各シンボル位置で発生しうる誤りが多くとも1つであるような場合は、ある符号語から2以上の距離以内にある可能な受信語の数は少なくなる。例えば、図17に示す誤り遷移図を持つ4値チャネルの場合、受信語「caaa」は、符号語「aaaa」からハミング距離が2であり、それらの誤りは両方とも第1の誤り位置で発生する。その結果、Table J(表10)に示すように、候補符号語「daaa」は、符号語「aaaa」からの変形ハミング隔たりが3であるため、可能な符号語にはならない。しかし、同じ符号語内で第2の誤りが発生する確率がゼロであるか、または送信または記憶された語の中の別のシンボルで第1の誤りが発生する確率より大幅に低い場合は、1つのシンボル中の複数の誤りがそのシンボル中のゼロ個の誤りまたは1つの誤りから正しく区別されない場合でも、検出されていない誤りの集まりの全確率がなお許容閾値より低い可能性がある。この例では、1つのシンボル中の複数の誤りが符号の形成時に考慮されない場合には、符号語「aaaa」から、発生しうる受信語「caaa」までの変形ハミング距離が無限になる。その結果、Table J(表10)の項目12における符号語「aaaa」と候補符号語「daaa」との間の変形ハミング隔たりが無限になり、図18の方法のステップFに進むことにより、候補符号語「daaa」を第2の符号語に指定することができる。緩やかにしたこの誤り条件のセットの下では、図18の方法で、SECDED符号の基準を満たす符号語が24個見つかる。それらの24個の符号語とデータ語への可能な割り当てをTable L(表12)に示す。
【０１３８】
【表１２】
0005726312.tif 000014
【０１３９】
さらに、符号語の大きさmが8シンボルである場合は、図18のアルゴリズムで、図17の誤り遷移図を仮定してSECDED符号を探す際に、1シンボルにつき複数の誤りが発生することを考慮する場合には1762個の可能な符号語が見つかり、1シンボルにつき複数の誤りが発生することを考慮しない場合には1866個の可能な符号語が見つかる。
【０１４０】
両方の場合とも、符号語の大きさmが4の時には、図18の方法で17個以上の可能な符号語が見つかることは重要である。符号の情報容量を符号語数のlog2と考える場合、2個の4シンボル符号の情報容量は、1シンボルにつき複数の誤りが発生することを考慮する場合としない場合とでそれぞれ4.322ビットおよび4.585ビットになる。チャネルが4値チャネルであるため、4シンボルを送信または記憶するために必要な正味チャネル容量は8ビットである。8ビットの送信または記憶ビットを使用するSECDEDハミング符号の情報量が4ビットであることは当技術分野でよく知られている。Table K(表11)およびTable L(表12)に示す本発明の符号はどちらも、同等のSECDEDハミング符号に比べて高い効率を有する。
【０１４１】
ステップFに関して、代替法では、事前に選択されなかったすべての候補符号語で、新しい符号語wjからのハミング隔たりがdまたはそれ未満である符号語は、それら自体が符号語になるには既存の符号語に近すぎると標識を付けることができる。そのような符号語は、その後のステップCの実行で再度選択されないように、基本的にすでに選択され(そして暗黙的に拒否され)た旨の標識を付けるか、または後にステップCで選択された時にステップEですぐに拒否できるように標識を付けることができる。より迅速な全体符号の発見を容易にするための他の最適化が本発明の文脈内で可能である。
【０１４２】
本発明の実施形態は、基本的に不完全な誤り注入特性を持つ他のメモリ装置および通信装置にも適用可能であることが理解されよう。他のメモリ装置および通信装置は、複数の誤り注入機構を有する可能性があり、そのうちの1つまたは複数は他の誤り注入機構よりもはるかに確率が高い。装置またはチャネルを不完全な誤り注入特性を持つものとしてモデル化するために、確率が大幅に低い機構は無視してもよい。
【０１４３】
上述の詳細な説明では、本発明について特定の実施形態を参照して説明した。本発明のより広い主旨および範囲から逸脱することなく、開示される実施形態に各種変更を加えることが可能であることは明らかであろう。したがって、上記実施形態の説明と図面は、制限的ではなく、例示的な意味で見なすものとする。
【符号の説明】
【０１４４】
102  ソース符号器
103  チャネル符号器
104  チャネル変調器
105  チャネル
106  チャネル復調器
107  チャネル復号器
108  ソース復号器
202  チャネル符号器
203  チャネル
204  チャネル復号器
302  ECC符号器
303  メモリ装置
【図１】
0005726312.tif 000015
【図２】
0005726312.tif 000016
【図３】
0005726312.tif 000017
【図４】
0005726312.tif 000018
【図５】
0005726312.tif 000019
【図６】
0005726312.tif 000020
【図７】
0005726312.tif 000021
【図８】
0005726312.tif 000022
【図９】
0005726312.tif 000023
【図１０】
0005726312.tif 000024
【図１１】
0005726312.tif 000025
【図１２】
0005726312.tif 000026
【図１３】
0005726312.tif 000027
【図１４】
0005726312.tif 000028
【図１５】
0005726312.tif 000029
【図１６】
0005726312.tif 000030
【図１７】
0005726312.tif 000031
【図１８】
0005726312.tif 000032