(57)【要約】【課題】復号化の前にいくつかの情報記号が復号器に既知である場合に、誤り訂正能力が強化される符号を設計することと、連続するセクタアドレスの多数またはすべてのビットが変わる場所においても、読み取りまたは書き込みヘッドのおよその到達場所の知識を利用することと、アドレスワードを符号ワードに符号化する方法と、このような符号化の方法によって符号化された切断されているかもしれない符号ワードを復号化する方法と、対応する装置を提供すること。【解決手段】本発明は、切断されているかもしれない受信された符号ワードを復号化する復号器に情報ワード（ｍ）の少なくとも１つの情報記号（ｍ１）が推測的に既知である場合に、強化された誤り訂正能力を提供するために、アドレス記号（ａ０， ａ１， ．．．，ａｋ−１）を有するアドレスワード（ａ）を、符号（Ｃ）の符号ワード（ｃ）に符号化する方法に関する。本発明は、さらに、切断されているかもしれない符号ワード（ｒ）を復号化する方法にも関する。いくつかの情報記号が復号化の前に復号器に既知である場合に訂正能力が向上する符号を設計するために、本発明によると、互いに近いアドレスを有するアドレスワードが複数の情報記号を共有するように、アドレスワード（ａ）が情報ワード（ｍ）に符号化されることと、この情報ワード（ｍ）が、生成行列（Ｇ）を使用して符号ワード（ｃ）に符号化されることと、この生成行列（Ｇ）が、符号（Ｃ）の少なくとも１つの部分符号（Ｃ’）の最小ハミング距離が符号（Ｃ）の最小ハミング距離より大きく、かつ、少なくとも１つの推測的に既知の情報記号（ｍ１）に対応する少なくとも１行を生成行列（Ｇ）から省略することによって、部分符号（Ｃ’）の部分符号生成行列（Ｇ’）が符号（Ｃ）の生成行列（Ｇ）から導かれるように、選択されること、が提案される。【選択図】図７
2005500730.tif 000002
【特許請求の範囲】
【請求項１】
切断されているかもしれない受信された符号ワードを復号化する復号器に、情報ワードの少なくとも１つの情報記号が推測的に既知である場合に、強化された誤り訂正能力を提供するために、アドレス記号を有するアドレスワードを、符号の符号ワードに符号化する方法であって、当該方法が、
− 互いに近いアドレスを有するアドレスワードが複数の情報記号を共有するように、前記アドレスワードを情報ワードに符号化するステップと、
− 当該符号の少なくとも１つの部分符号の最小ハミング距離が当該符号の最小ハミング距離より大きく、かつ、当該少なくとも１つの推測的に既知の情報記号に対応する少なくとも１行を当該生成行列から省略することによって、当該部分符号の部分符号生成行列が当該符号の当該生成行列から導かれるように、選択された、生成行列を使用して、当該情報ワードを符号ワードに符号化するステップと、
を有する、方法。
【請求項２】
前記アドレスワードが、前記アドレスが増加する場合に少なくとも２つの情報記号の一定のセットのうち最大で１つの情報記号が変わるように、情報ワードに符号化される、請求項１による方法。
【請求項３】
多数のアドレスワードが、アドレスワードのアドレス記号を前記それぞれの前のアドレス記号の最下位ビットのビット値が１であるときに反転することによって、情報ワードに符号化される、請求項２による方法。
【請求項４】
アドレスワードの前記アドレス記号が、アドレス記号のすべてのビットと前記それぞれの前のアドレス記号の最下位ビットの間の排他的論理和の結果を計算することによって、反転される、請求項３による方法。
【請求項５】
ｋ個の情報記号（ｍ０， ｍ１， ．．．， ｍｋ−１）を有する前記情報ワード（ｍ）が、ＧＦ（ｑ）上の［ｎ，ｋ，ｎ−ｋ＋１］リードソロモン符号の符号ワード（ｃ）に符号化され、当該符号化が、
ａ）親の生成多項式（ｇ（ｐ）（ｘ））
2005500730.tif 000108
を定義するステップであって、この式において、αは、最大ｎ次のＧＦ（ｑ）の０でない要素であり、
2005500730.tif 000109
は、ｋ／２の切り上げを示し、すなわちｋが偶数の場合は
2005500730.tif 000110
であり、ｋが奇数の場合は
2005500730.tif 000111
である、ステップと、
ｂ）０≦ｉ≦ｋ−２に対する成分生成多項式（ｇ（ｉ））を、
2005500730.tif 000112
によって定義するステップであって、この式において、ｚｉ ＝ αｎ−ｋ＋ｉ／２（ｉ が偶数の場合）、ｚｉ ＝ α−（ｉ＋１）／２（ｉが奇数の場合）に対して、
2005500730.tif 000113
かつ
2005500730.tif 000114
が成り立つ、ステップと、
ｃ）前記符号ワード多項式（ｃ（ｘ））を、式
2005500730.tif 000115
によって計算するステップであって、この式において、当該符号ワード多項式ｃ（ｘ）の前記係数が、前記符号（Ｃ）における前記符号ワード（ｃ）を形成する、ステップと、
を有する、請求項１による方法。
【請求項６】
当該方法が、ＤＶＲ（ディジタルビデオレコーディング）において使用されるアドレスワードを符号化するために、特にウォブルアドレスのアドレスワードを符号化するために使用される、請求項１による方法。
【請求項７】
９つの情報記号（ｍ０， ｍ１， ．．．， ｍ８）を有する前記情報ワード（ｍ）が、ＧＦ（ｑ）上の［１５， ９， ７］リードソロモン符号の符号ワード（ｃ）に符号化され、当該符号化が、
ａ）親の生成多項式（ｇ（ｐ）（ｘ））
2005500730.tif 000116
を定義するステップであって、この式において、αは、最大ｎ次のＧＦ（ｑ）の０でない要素である、ステップと、
ｂ）０≦ｉ≦７に対する成分生成多項式（ｇ（ｉ））を、
2005500730.tif 000117
によって定義するステップであって、この式において、ｚｉ＝αｉ／２＋６（ｉが偶数でありかつ０≦ｉ≦６の場合）
ｚｉ＝α （ｉ＋１）／２（ｉが奇数でありかつ１≦ｉ≦７の場合）
に対して、
2005500730.tif 000118
かつ
2005500730.tif 000119
が成り立つ、ステップと、
ｃ）前記符号ワード多項式（ｃ（ｘ））を、式
2005500730.tif 000120
によって計算するステップであって、この式において、当該符号ワード多項式ｃ（ｘ）の前記係数が、前記符号（Ｃ）における前記符号ワード（ｃ）を形成する、ステップと、
を有する、請求項６による方法。
【請求項８】
符号の切断されているかもしれない符号ワードを、アドレス記号を有するアドレスワードに復号化する方法であって、当該アドレスワードが、生成行列を使用して当該符号の符号ワードに符号化されていて、かつ、少なくとも１つの情報記号が復号器に推測的に既知である場合に強化された誤り訂正能力が当該符号に提供される、方法において、当該アドレスワードが、請求項１による方法を使用して当該符号ワードに符号化されていることと、当該切断されているかもしれない符号ワードに含まれる当該少なくとも１つの推測的に既知の情報記号の貢献分が、強化された誤り訂正能力を使用して当該切断されているかもしれない符号ワードを復号化するときに考慮されることとを特徴とする、方法。
【請求項９】
請求項８による方法であって、
ａ）前記切断されているかもしれない符号ワードを中間符号ワードに復号化するステップと、
ｂ）当該中間符号ワードを情報ワードに復号化するステップと、
ｃ）当該情報ワードをアドレスワードに復号化するステップと、
を有する、方法。
【請求項１０】
当該情報ワードが、情報ワードの情報記号を前記それぞれの前の情報記号の最下位ビットのビット値が１である場合に反転することによって、アドレスワード（に復号化される、請求項９による方法。
【請求項１１】
切断されているかもしれない受信された符号ワードを復号化する復号器に、情報ワードの少なくとも１つの情報記号が推測的に既知である場合に、強化された誤り訂正能力を提供するために、アドレス記号を有するアドレスワードを符号の符号ワードに符号化するための装置であって、当該装置が、当該アドレスワードを、請求項１による方法を使用して当該符号ワードに符号化するための手段を有する、装置。
【請求項１２】
符号の切断されているかもしれない符号ワードを、アドレス記号を有するアドレスワードに復号化するための装置であって、当該アドレスワードが、生成行列を使用して当該符号の符号ワードに符号化されていて、かつ、復号化の前に少なくとも１つの情報記号が推測的に既知である場合に強化された誤り訂正能力が当該符号に提供される、装置において、当該アドレスワードが、請求項１による方法を使用して当該符号ワードに符号化されていることと、当該切断されているかもしれない符号ワードに含まれる当該少なくとも１つの推測的に既知の情報記号（の貢献分が、強化された誤り訂正能力を使用して当該切断されているかもしれない符号ワードを復号化するときに考慮されることとを特徴とする、装置。
【請求項１３】
請求項１および／または９の方法をコンピュータに実行させるためのプログラムコード手段を有する、コンピュータプログラム製品。
【請求項１４】
ユーザデータを記録するためのデータキャリア、特にＤＶＲの規格に従って使用される光学データキャリアであって、当該データキャリアが、請求項１による方法によって符号化された格納されたシステムデータ項目を有する、データキャリア。
【請求項１５】
当該システムデータ項目が、当該データキャリア上の位置を見つけるために使用されるアドレスデータおよび／またはタイミングデータを有する、請求項１４によるデータキャリア。
【請求項１６】
ユーザデータを伝送するための信号であって、当該信号が、請求項１による方法によって符号化されたシステムデータ項目を含む、信号。
【発明の詳細な説明】
【発明が属する技術分野】
【０００１】
本発明は、切断されているかもしれない（ｐｏｓｓｉｂｌｙ ｍｕｔｉｌａｔｅｄ）受信された符号ワードを復号化する復号器に、情報ワードの少なくとも１つの情報記号が推測的に既知である場合に、強化された誤り訂正能力を提供するために、アドレス記号を有するアドレスワードを、符号の符号ワードに符号化する方法に関する。本発明は、さらに、符号が切断されているかもしれない符号ワードをアドレスワードに復号化する方法にも関する。さらに、本発明は、情報ワードを符号化するための対応する装置と、切断されているかもしれない符号ワードを復号化するための対応する装置と、これらの方法を実施するコンピュータプログラムと、ユーザデータを記録するためのデータキャリアと、ユーザデータを伝送するための信号とに、関する。
【０００２】
【従来の技術】
ヨーロッパ特許出願ＥＰ ０１ ２０１ ８４１．２（ＰＨＮＬ １０３３１）には、情報記号のいくつかが復号器に既知である場合に、誤り訂正符号の誤り訂正能力を強化することができる方法が説明されている。この文書の内容は、本文書に参考文献として組み込まれている。この方法は、光学メディア上のアドレス検索の分野に適用できる。光学メディアのセクタアドレスは、誤り訂正符号によって保護されるヘッダの一部である。多くの情況においては、現在のセクタのヘッダ情報の多くは、前に読み取られたセクタと目次から、または読み取りまたは書き込みヘッドがおよそ到達する位置の知識から推測できる。
【０００３】
ヨーロッパ特許出願ＥＰ ０１ ２０１ ８４１．２（ＰＨＮＬ １０３３１）に説明されている方法には、次の問題点がある。連続するセクタのアドレスは、連続する整数の２進表現であるとする。単純な例、として８ビットのアドレスについて考察するなら、アドレスが０１１１１１１１のセクタのあとに、アドレスが１０００００００のセクタが続く。読み取りまたは書き込みヘッドが、アドレス０１１１１１１１のセクタに到達する必要がある場合には、到達の誤差が１セクタに限定されていても、アドレスの１ビットも復号器に既知とならず、ヨーロッパ特許出願ＥＰ ０１ ２０１ ８４１．２（ＰＨＮＬ １０３３１）に説明されている方法は適用できない。
【０００４】
【課題を解決するための手段】
従って、本発明の目的は、復号化の前にいくつかの情報記号が復号器に既知である場合に、誤り訂正能力が強化される符号を設計することである。本発明のさらなる目的は、連続するセクタアドレスの多数またはすべてのビットが変わる場所においても、読み取りまたは書き込みヘッドのおよその到達場所の知識を利用することである。本発明のさらなる目的は、アドレスワードを符号ワードに符号化する方法と、このような符号化の方法によって符号化された切断されているかもしれない符号ワードを復号化する方法とを提供することである。さらに、対応する装置を提供する。
【０００５】
これらの目的は、請求項１の符号化の方法によって達成される。この方法によると、互いに近いアドレスを有するアドレスワードが複数の情報記号を共有するように、アドレスワードが情報ワードに符号化され、次いで、当該符号の少なくとも１つの部分符号の最小ハミング距離が当該符号の最小ハミング距離より大きく、かつ、当該少なくとも１つの推測的に既知の情報記号に対応する少なくとも１行を当該生成行列から省略することによって、当該部分符号の部分符号生成行列が当該符号の当該生成行列から導かれるように、選択された生成行列を使用して、この情報ワードが、符号ワードに符号化される。これらの目的は、さらに、請求項８に請求される復号化の方法によって達成される。
【０００６】
本発明によると、アドレスワードは、前処理され、情報ワードにマッピングされる。従って、このような前処理に従ってアドレスワードがマッピングされる情報ワードには、上述されている状況、すなわちアドレスが増加する場合に複数の最上位記号が変わる状況は起こらない。
【０００７】
さらに、本発明によると、情報ワードから符号ワードへのマッピングは、情報ワードのいくつかの情報記号が復号器に既知である場合に、有効なハミング距離が向上するものである。しかしながら、復号器に既知となる記号が実際にどれであるかについては、符号器には知らされていないものと想定される。有効なハミング距離のこのような向上を得るため、特定の事前定義された（すなわち事前に選択される）生成行列が使用される。この事前定義された生成行列は、符号化と復号化に使用され、すなわち、この行列を標準の生成行列として使用する必要がある。言い換えれば、生成行列は、部分符号の最小ハミング距離が完全な符号の最小ハミング距離よりも大きくなるように選択される。
【０００８】
情報ワードを符号ワードに符号化するために生成行列を使用するというコンセプトは、広く使用され、例えばＲｉｃｈａｒｄ Ｅ． Ｂｌａｈｕｔ氏の「Ｔｈｅｏｒｙ ａｎｄ Ｐｒａｃｔｉｃｅ ｏｆ Ｅｒｒｏｒ−Ｃｏｎｔｒｏｌ Ｃｏｄｅｓ（誤り制御符号の理論と実際）」（Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ、１９８４年５月、第３．２節）から公知である。このような生成行列は、特に、ＣＤオーディオ規格などの規格に使用されかつ記載されている。
【０００９】
この事前定義された生成行列を使用すると、アドレス情報をより高い信頼性で保護できる。データキャリア（例、ディスク）上の特定のアドレスにアクセスする新しいコマンドが与えられる場合に、アドレス情報の一部（例、最上位ビット）がすでに復号器に既知であれば、アドレス検索の信頼性がより高くなり、このことは、特に書き込み時に重要である。その場合、復号器は、最小ハミング距離が増加した部分符号を有効に利用できる。しかしながら、情報記号が復号器に推測的に既知でない場合にも、検索された符号ワードを通常に復号化することができ、その場合には、本発明によって使用される符号のハミング距離は、既知の符号のハミング距離と同じになる、すなわち、復号化するときに、最小ハミング距離がより大きい部分符号を使用することはできない。
【００１０】
切断されているかもしれない符号ワードを、例えば、データキャリアから読み取ることによって受信するとき、少なくとも１つの情報記号（例、読み取りアドレスの最上位ビット）が復号器に推測的に既知である場合には、復号器は、最初に、切断されているかもしれない符号ワードを標準のリード−ソロモン（ＲＳ）復号器を使用して中間符号ワードに復号化する。次いで、この中間符号ワードが後処理される、すなわち情報ワードに復号化される。
【００１１】
望ましい実施例、においては、この後処理には、シンドローム計算が含まれる。これにより、中間符号ワードが情報記号に対応する０において評価され、情報記号が得られる。最後に、アドレスワードを情報ワードに符号化するために使用された方法に対応する方法によって、この情報ワードからアドレスワードが得られる。
【００１２】
符号化時のアドレス前処理に起因して、アドレスが増加する場合には、情報記号の１つのみが変わる。例えば、ディスクの内側から外側にジャンプするときに、情報記号は一度に１つのみ変わる。従って、ジャンプの精度が、実際の到達場所のアドレスが目標の到達場所のアドレスから最大でｋだけ異なる程度である場合、ディスク上の各ジャンプ時に少なくともｋ−１個の情報記号が既知となる。
【００１３】
上述されているように生成行列を選択すると、復号化の前にいくつかの情報記号が復号器に既知である場合に、誤り訂正能力を強化できる。強化のレベルは、復号器に既知である情報記号のタイプと数によって異なることがある。
【００１４】
本発明の望ましい実施例、は、従属請求項に定義されている。本発明の１つの観点においては、アドレスワードは、グレイ符号を適用することによって情報ワードに符号化される。従って、アドレスワードが増加すると、１つの情報記号のみが変わる、すなわち、連続するアドレスワードに対応する情報ワードは１つの情報記号が異なる。次元ｍのｑ−ａｒｙグレイ符号は、２つの隣接するワードのハミング距離が必ず１である、ｑｌ個のｑ−ａｒｙ長ｍの文字列のシーケンスである。
【００１５】
本発明によると、アドレスワードから情報ワードへの符号化は、前記それぞれの前のアドレス記号の最下位ビットのビット値が１である場合に、アドレスワードのアドレス記号を反転することによって行われることが望ましい。これは、多数のアドレスワードについて行われる。本発明の特定の実施例、においては、アドレスワードのアドレス記号は、アドレス記号のすべてのビットと前記それぞれの前のアドレス記号の最下位ビットの間の排他的論理和の結果を計算することによって反転される。すなわち、アドレス記号のすべてのビットが個別にＸＯＲゲートに入力され、このＸＯＲゲートに、前のアドレス記号の最下位ビットが第二入力として送られる。しかしながら、留意すべき点として、アドレス記号のいくつかは変更されずに情報記号となることもあり、この変更されない記号は補助記号として使用される。
【００１６】
情報ワードを符号ワードに符号化するステップの望ましい実施例、は、請求項５と７に定義されている。切断されているかもしれない符号ワードの復号化の方法と、その具体的な実施例、は、請求項８〜１０に定義されている。
【００１７】
本発明の有利な用途は、特に光学メディア上のアドレス検索の分野にある。本発明を使用すると、アドレス検索の安全性と精度を高める、より高い誤り訂正能力によって、アドレスまたはタイミング情報を保護できる。本発明は、さらに、例えば通信ネットワークまたはインターネットなどの伝送回線を通じて伝送されるシリアルデータストリームにおけるアドレス情報の保護にも使用できる。一般に、本発明は、情報の一部が復号器に推測的に既知である場合に、公知の符号と比較して向上した誤り訂正能力を有する符号によって情報を保護するために使用できる。
【００１８】
本発明による、情報ワードを符号化するための装置と、切断されているかもしれない符号ワードを復号化するための装置は、請求項１１と１２に定義されている。これらの装置は、さらに発展させることができ、請求項１による符号化の方法を参照して前述されている実施例、と類似する実施例、を持つことができると理解されるものとする。
【００１９】
本発明による方法のいずれかまたはすべてを実施するための、本発明によるコンピュータプログラムは、請求項１３に定義されている。
【００２０】
本発明によるデータキャリアは、請求項１４と１５に定義されている。このようなデータキャリアは、望ましくは、オーディオデータ、ビデオデータ、またはソフトウェアデータを格納するために使用され、記録可能タイプまたは書き換え可能タイプの、特にＣＤまたはＤＶＤなどの光学記録担体でよい。本発明の１つの特定の用途は、光学的な記録の分野、特にＤＶＲ（ディジタルビデオレコーディング）の規格において提案されている記録と、望ましくはＤＶＲにおけるウォブル・アドレスの符号化の分野にある。一般に、このようなデータキャリアには、システムデータ項目、特にアドレスデータ、タイミングデータ、またはポジションデータのシステムデータ項目が含まれ、これらは、データキャリアの製造現場においてすでにデータキャリアに記録され、ユーザデータを記録するための空のデータキャリアを購入した時点ですでに存在する。従って、本発明は、このシステムデータ項目を符号化するために使用できる。しかしながら、本発明は、ユーザデータを符号化するために使用することもできる。
【００２１】
さらに、ユーザデータを伝送するための信号であって、当該信号が、本発明による方法によって符号化されたシステムデータ項目（例、位置データ、アドレスデータ、またはタイミングデータ）を含む、信号が、請求項１６に定義されている。
【００２２】
以下に、図面を参照しながら本発明についてさらに詳細に説明する。
【００２３】
【発明を実施するための形態】
図１は、［ｎ， ｋ］ブロック符号（例、リードソロモン符号）の符号ワードｃの代表的な方式を示す。符号ワードには、ｋ個の情報記号を有する情報ワードｍと、この情報ワードｍを符号ワードｃに符号化するときに生成されたｎ−ｋ個のパリティ記号を有するパリティワードｐとが含まれる。
【００２４】
図２は、符号化と復号化を使用する代表的なシステムのブロック図を示す。この図において、（例、マスターテープまたはマスターディスクに記録された）データ源１から入力されるユーザデータ（例、オーディオデータまたはビデオデータ）は、符号化された後、データキャリア（例、ディスク）に格納されるか、または伝送チャネル（例、インターネット）を通じて伝送され、その後、再び復号化され、（例、データを再生するために）データシンク９に転送される。
【００２５】
図から明らかなように、データ源１のユーザデータは、最初にソース符号器２によって符号化され、次にＥＣＣ符号器３によって誤り訂正符号化が行われ、次に変調器４（例、ＥＦＭ変調器）によって変調された後、この符号化されたユーザデータ（符号ワード）はチャネル５に送られる。このチャネル５において、符号ワードに誤りが発生することがある。この図におけるチャネル５は、伝送チャネルのみならず、後から再生するためにデータキャリア上に格納されている符号化されたデータなど、広く解釈するものとする。
【００２６】
データの再生を目的とするときには、符号化されたデータは、最初に復調器６（例、ＥＦＭ復調器）によって復調し、次にＥＣＣ復号器７によって誤り訂正復号化を行い、ソース復号器８によってソース復号化を行う必要がある。最後に、復号化されたユーザデータをシンク９（例、ユーザデータを再生するためのプレーヤーデバイス）に入力できる。
【００２７】
しかしながら、このような一般的なシステムは、ユーザデータの符号化と復号化に使用されるのみならず、管理データ、特にアドレスデータなどあらゆる種類のデータにも使用されることがある。このようなアドレスデータは、データキャリア上の特定の位置、またはユーザデータのデータストリームにおける特定の位置を見つけるのに使用される。記録可能または書き換え可能なディスクにおいては、このようなアドレスデータは、一般に、ユーザデータが記録される前に空のディスク上にあらかじめ記録される。
【００２８】
本発明は、データの符号化と復号化について言及する。本発明においては、特定の所定の生成行列が使用され、この行列の選択も、本発明による方法によって言及される。本発明の１つの特定の用途は、光学記録担体上に使用されるアドレスのアドレス検索の分野にある。
【００２９】
図３は、本発明によって情報ワードｍを符号化するための装置の実施例、を示す。この実施例、においては、符号化装置１０は、一定数の情報記号ｍ１， ｍ２， ．．．， ｍｋを有する情報ワードｍを符号Ｃの１つ以上の符号ワードｃに符号化するための符号化ユニット１１を有する。改良された誤り訂正能力を達成するため、情報ワードｍを符号化するために特定の事前定義された生成行列Ｇが使用される。この生成行列Ｇは、選択ユニット１２によっていったん選択されかつ定義された後、符号化装置１０と復号化装置とに供給されるか、または望ましくは、連続的に使用できるように符号化装置１０と復号化装置に格納される。
【００３０】
生成行列Ｇを使用することにより、情報ワードｍは、符号化ユニット１１によって符号ワードｃに符号化される。これらの符号ワードｃは、符号ワードｃを光学記録担体１４（例、ＣＤまたはＤＶＤ）に記録する書き込みユニット１３に送ることができる。
【００３１】
本発明の一例、として、特に生成行列Ｇの望ましい選択について、さらに詳細に説明する。以下の例、は、ｇ（ｘ） ＝ ｘ３ ＋ ｘ ＋ １によって生成される［７， ４， ３］２進ハミング符号Ｃに基づく。最初に、この符号の「普通の」公知の使用について説明した後、本発明によるこの符号の使用について説明する。
【００３２】
通常、この符号Ｃは、系統的な形式で使用され、次に示す４（一般にｋ）行、７（一般にｎ）列の生成行列に対応する。
2005500730.tif 000003
情報ワードｍ ＝ （ｍ１， ｍ２， ｍ３， ｍ４）は、符号ワードｃ ＝ ｍ・Ｇｓｙｓにマッピングされる。ｉ番目の情報記号ｍｉが復号化の前に復号器に既知である場合、復号器は、受信されるワードｒへのｍｉの貢献分を復号化の前に減算することができる。すなわち、復号器は、残りの受信ワードｒ − ｍｉ・Ｇｓｙｓｉを（ＧｓｙｓｉはＧｓｙｓのｉ番目の行を示す）符号に復号化し、この符号においては、生成行列Ｇｓｙｓからｉ番目の行が取り除かれている。最大３つの情報ビットが既知であっても、未知の情報ビットに対する訂正能力が大きく変化することはなく、なぜなら、Ｇｓｙｓの最大で３行を削除することによって得られる符号Ｃの部分符号Ｃ’のほとんどすべては、そのハミング距離が３のままであるためである。情報ビットｍ１、ｍ３、およびｍ４が既知である場合のみ、ｍ２を検索するためのハミング距離が４に増加する。
【００３３】
本発明によると、同じ符号Ｃのための別の生成行列Ｇｉｄは、次のように与えられる。
2005500730.tif 000004
【００３４】
この（非系統的な）の生成行列Ｇｉｄが符号Ｃの符号化に使用される場合、図４に示されている、情報が与えられる復号器は、特定の情報ビットまたは情報記号（１つの情報記号は複数のビットを有することがある）が既知である場合に、符号Ｃのより有利な部分符号Ｃ’に復号化することができる。例えば、復号器に最初の情報ビットｍ１が既知である場合、復号器は、Ｇｉｄの最後の３行ｇ２、ｇ３、ｇ４によって生成される部分符号Ｃ’を使用でき、この部分符号は［７， ３， ４］単純符号（ｓｉｍｐｌｅｘ ｃｏｄｅ）に対応する。別の例、として、最後の３つのビットｍ２， ｍ３， ｍ４が復号器に既知である場合には、復号器は、Ｇｉｄの第一行によって生成される部分符号（［７， １， ７］繰り返し符号（ｒｅｐｅｔｉｔｉｏｎ ｃｏｄｅ）に対応する）を利用でき、従って、３つのビット誤りが存在するときにも復号器はｍ１を高い信頼性で復元できる。
【００３５】
読み取られた切断されているかもしれない符号ワードｒを復号化するための装置が、図４に示されている。この図において、復号化装置２０は、読み取りユニット２１によってデータキャリア１４から読み取られた切断されているかもしれない符号ワードｒを受信する。いま、符号ワードｃに符号化された情報ワードｍが４つの情報記号ｍ１， ｍ２， ｍ３， ｍ４を有することと、さらに、復号化するための装置２０が推測的に３つの情報記号ｍ２， ｍ３， ｍ４を認識していると想定する。第一ステップにおいて、既知の情報記号ｍ２， ｍ３， ｍ４が、生成行列Ｇを使用して符号化ユニット２２によって符号化される。この生成行列Ｇは、復号化装置２０の中の格納ユニット２３に格納されていて、かつ、データキャリア１４に格納されかつ切断されているかもしれない符号ワードｒとして読み取られた符号ワードｃを符号化するためにすでに使用された行列である。このような符号化に対して、符号化ユニット２２は、既知の情報記号ｍ２， ｍ３， ｍ４に対応する生成行列Ｇの行を使用する。
【００３６】
次のステップにおいては、このような符号化の結果、すなわち既知の情報記号ｍ２， ｍ３， ｍ４と、生成行列Ｇｉｄのこれらに対応する行ｇ２， ｇ３， ｇ４の積が、加算ユニット２４によって加えられ、中間ワードｓが得られる。この中間ワードｓは、減算ユニット２５において、読み取られた符号ワードｒから減算され、この減算の結果が、復号化ユニット２６に送られる。復号化ユニット２６においては、部分符号生成行列Ｇ’を使用することによって生成される部分符号Ｃ’が復号化される。この部分符号生成行列Ｇ’は、形成手段２７において、既知の情報記号ｍ２， ｍ３， ｍ４に対応する行すべてを生成行列Ｇから省略することによって、すなわちこの例においてはｇ２， ｇ３， ｇ４を省略することによって、生成行列Ｇから導かれる。このため、この例、においては、部分符号生成行列Ｇ’には、生成行列Ｇの第一行ｇ１のみが含まれる。この結果として、未知の情報記号ｍ１を復元でき、従って最終的に完全な情報ワードｍが既知となる。従って、一般に、切断されているかもしれない符号ワードに含まれている推測的に既知の情報記号の貢献分が、その切断されているかもしれない符号ワードから減算され、この減算の結果が復号化される。
【００３７】
次に、復号化の方法を一例、としてさらに詳細に説明する。符号Ｃの１つ以上の符号ワードｃは、次式によって与えられるものとする。
ｃ ＝ ｍ・Ｇ ＝ （ｍ１ ｍ２ ｍ３ ｍ４） （ｇ１ ｇ２ ｇ３ ｇ４）Ｔ ＝ ｍ１ ｇ１ ＋ ｍ２ ｇ２ ＋ ｍ３ ｇ３ ＋ ｍ４ ｇ４
【００３８】
一般に、生成行列Ｇは、ｋ行、ｎ列を有し、情報ワードｍは、ｋ列を有し、符号ワードｃは、ｎ列を有する。
【００３９】
いま、情報記号ｍ２， ｍ３， ｍ４が復号器に推測的に既知であり、読み取られた符号ワードｒが、格納されている符号ワードｃと追加の雑音ｎの合計によって与えられると想定すると、最初に中間ワードｓが、次のように計算される。
ｓ ＝ ｍ２ ｇ２ ＋ ｍ３ ｇ３ ＋ ｍ４ ｇ４
【００４０】
その後、読み取られた切断されているかもしれない符号ワードｒと中間ワードｓの間の差が、次のように計算される。
ｒ − ｓ ＝ ｃ ＋ ｎ − ｓ ＝ ｍ１ ｇ１ ＋ ｎ
【００４１】
この場合に、情報記号ｍ１が１ビットを有し、かつ生成行列Ｇの行ｇ１が一定であり、かつ雑音ｎが未知である場合には、情報記号ｍ１は０または１のいずれかである。次に、本発明によって選択される先に示した生成行列Ｇｉｄを使用すると、ｇ１は（１ １ １ １ １ １ １）として与えられ、従って、ｍ１ ｇ１は（０ ０ ０ ０ ０ ０ ０）または（１ １ １ １ １ １ １）のいずれかである。前述されているｍ１ ｇ１ ＋ ｎの計算の結果が、例えば（０ ０ １ ０ ０ １ １）であるなら、ｍ１ ｇ１が（０ ０ ０ ０ ０ ０ ０）として与えられ、この結果としてｍ１のビット値は０である確率が高くなる。この例、から明らかであるように、読み取られた符号ワード内に３つのビット誤りがある、すなわち残りの部分符号Ｃ’のハミング距離が７であるにも関わらず、情報記号ｍ１を求めることができる。
【００４２】
すでに説明したように、本発明は、光学記録担体上で使用されるアドレスを保護するために使用できる。しかしながら、本発明は、伝送回線を通じて伝送されることもある任意のシリアルデータストリームにおけるアドレスを保護するためにも使用できる。一般には、本発明は、情報ワードが符号に符号化され、かつ、少なくとも１つの情報記号が復号器に推測的に既知となる場合に、改良された誤り訂正能力が達成される用途に適用できる。
【００４３】
次に、符号パンクチャリング（ｃｏｄｅ ｐｕｎｃｔｕｒｉｎｇ）に基づく本発明の実施例、について、図５と図６を参照しながら説明する。図５は、情報ワードｍを符号ワードｃに符号化する方法を図示し、図６は、切断されているかもしれない符号ワードｒを情報ワードｍに復号化する方法を図示する。
【００４４】
図５に示されているように、ｋ個の情報記号を有する情報ワードｍは、中間生成行列Ｇ’’を使用して符号化装置４０の符号化ユニット４１によって符号化される。この中間生成行列Ｇ’’は、選択ユニット４２によって選択された生成行列Ｇから導かれる。中間生成行列Ｇ’’は、生成行列Ｇよりも少なくとも１列多く有することにおいて、生成行列Ｇよりも大きい。一般に、生成行列Ｇは、ｋ行ｎ列を有するのに対し、中間生成行列Ｇ’’は、ｋ行ｎ＋ｋ列を有し、このうちｋ列は、相互に異なる位置において１つの０でないエントリを持つ。情報ワードｍを符号化するのにこの中間生成行列Ｇ’’を使用すると、ｋ＋ｎ個の記号を有する中間符号ワードｔが得られる。この中間符号ワードｔから、この中間符号ワードｔの多数の記号を省略することによって、符号ワード生成ユニット４４から符号ワードｃが得られる。このとき、省略する記号の数は、中間生成行列Ｇ’’と生成行列Ｇの数の差に一致する。従って、得られる符号ワードｃは、ｎ個の記号を有する。しかしながら、留意すべき点として、符号化装置において符号化のためにＧ’’の代わりにＧを直接使用することもできる。
【００４５】
図６に示されているように、復号化時には、ｎ個の記号を有する切断されているかもしれない符号ワードｒが復号器によって受信される。第１ステップにおいて、受信されたワードｒは、拡張ユニット５０によって第一疑似符号ワードｒ’に拡張される。この拡張においては、符号器においてすでに使用された中間生成行列Ｇ’’が使用されて、疑似符号ワードｒ’の長さが求められる。すなわち、疑似符号ワードｒ’の記号の数は、中間生成行列Ｇ’’の列の数に一致し、すなわち、疑似符号ワードｒ’は、受信されたワードｒのｎ個の記号にｋ個の消去要素（ｅｒａｓｕｒｅ）が加えられることにより得られる。符号化するためにＧ’’の代わりにＧを直接使用した場合には、疑似符号ワードｒ’は、ｋ個の消去要素が追加される受信されたワードｒのｎ個の記号に等しい。
【００４６】
その後、置換ユニット５１において、推測的に既知の情報記号（例、ｍ１， ｍ５， ｍ６）が、疑似符号ワードｒ’の中の、この推測的に既知の情報記号の位置に対応する消去要素の位置において置き換わる。すなわち、消去要素１、５、および６が、推測的に既知の情報記号ｍ１， ｍ５， ｍ６に置き換わる。これにより得られた第二疑似符号ワードｒ’’が、次いで復号器ユニット５２に入力される。この復号器ユニット５２は、望ましくは、公知の誤り／消去要素復号器であり、中間生成行列Ｇ’’を使用することにより第二疑似符号ワードｒ’’をｋ個の記号を有する情報ワードｍに復号化する。
【００４７】
本発明のこの実施例、によると、本発明の他の実施例、と比べて、より大きい中間生成行列Ｇ’’が使用される。しかしながら、この実施例、の利点は、情報記号が連続する順序で推測的に既知となる必要がなく、１つ以上の情報記号が推測的に既知になると、情報ワードにおけるそれらの位置には関係なく、情報記号が推測的に既知とならない場合に使用される符号と比較して、一般に最小ハミング距離が向上する。
【００４８】
次に、符号パンクチャリングに基づく実施例、について、別の観点から説明する。いま、次のように定義される、ガロア体ＧＦ （８）上の［８， ３， ６］拡張リード−ソロモン符号Ｃを考える。ベクトルｃ ＝ （ｃ−１， ｃ０， ｃ１…， ｃ６）は、次の場合に限りＣに含まれる。
2005500730.tif 000005
式中、αは、α３ ＝ １ ＋ αを満たすＧＦ（８）の要素である。
次の中間生成行列Ｇ’’によって符号Ｃが生成されることが理解できる。
2005500730.tif 000006
この中間生成行列Ｇ’’の右側の５列は、生成行列Ｇとして使用される。すなわち、生成行列Ｇは、次のとおりである。
2005500730.tif 000007
【００４９】
この生成行列Ｇによって生成される符号は、最小ハミング距離が３である。ｊ個の情報記号が既知であると、最小ハミング距離が３から３＋ｊに増加する。
【００５０】
本発明による符号化／復号化方式の別の実施例のブロック図が、図７に示されている。この実施例、においては、ｋ個のアドレス記号ａ０， ａ１， …， ａｋ−１を有するアドレスワードａが、アドレス前処理ユニット６１とＲＳ符号器６２とを有する符号器６０に送られる。アドレス前処理ユニット６１によって、アドレスワードａは、アドレスが増加するときに一度に１つのみの情報記号が変わるように、ｋ個の情報記号ｍ０， ｍ１， …， ｍｋ−１を有する情報ワードｍに符号化される。これは、グレイ符号を適用することによって、望ましくは、情報記号ａｉを前の記号ａｉ−１の最下位ビットのビット値が１であるときに反転することによって、達成される。
【００５１】
アドレス前処理ユニット６１の実施例が、図８に示されている。図から明らかなように、この実施例、においては、アドレス記号ａ０， ａ１， …， ａ５が、情報記号ｍ０， ｍ１， …， ｍ５にマッピングされる。この特定の例、においては、各アドレス記号ａｉは、４つのアドレスビットａｉ０， ａｉ１， ａｉ２， ａｉ３を有する。
【００５２】
同様に、各情報記号ｍｉは、４つの情報ビットを有する。第一アドレス記号ａ０のアドレスビットａ０１， …， ａ０３は、第一情報記号ｍ０の情報ビットに直接マッピングされる。これに対して、連続するアドレス記号ａ１， …， ａ５それぞれのアドレスビットは、ＸＯＲゲート７０に個別に入力され、このＸＯＲゲート７０には、前のアドレス記号の最下位ビットが第二入力として送られる。例えば、第二情報記号ｍ１の最上位情報ビットｍ１３は、第二アドレス記号ａ１の最上位ビットａ１３と第一アドレス記号ａ０の最下位ビットａ００の排他的論理和の結果である。
【００５３】
アドレスワードａがｋ＝９個のアドレス記号を有し、かつ情報ワードｍがｋ＝９個の情報記号を有する特定の用途においては、最上位アドレス記号ａ０と３つの補助アドレス記号 ａ６， ａ７， ａ８（図には示されていない）は、変化しない、すなわちｍ０＝ａ０、ｍ６＝ａ６、ｍ７＝ａ７、ｍ８＝ａ８であるのに対し、他のアドレス記号は、図８に示されているように情報記号にマッピングされる。
【００５４】
情報ワードｍは、その後、図７に示されているＲＳ符号化ユニット６２によって符号ワードｃに符号化される。符号化ユニット６２として、前述されている符号器を使用できる。しかしながら、符号化ユニット６２を少し変更することもできる。
【００５５】
ｋ個の情報記号ｍ０， ｍ１， …， ｍｋ−１を有する情報ワードｍを、ＧＦ（ｑ）上の［ｎ，ｋ，ｎ−ｋ＋１］リードソロモン符号の符号ワードｃに符号化するための符号器を実施するための一般的な定義を以下に示す。
親の生成多項式ｇ（ｐ）（ｘ）は、次式によって与えられる。
2005500730.tif 000008
式中、αは、最大ｎ次のＧＦ（ｑ）の０でない要素であり、
2005500730.tif 000009
は、ｋ／２の切り上げを示し、すなわちｋが偶数の場合は
2005500730.tif 000010
であり、ｋが奇数の場合は
2005500730.tif 000011
である。
【００５６】
０≦Ｉ≦ｋ−２に対する成分生成多項式ｇ（ｉ）は、次式によって定義される。
2005500730.tif 000012
このとき、
かつｚｉ ＝ αｎ−ｋ＋ｉ／２（ｉが偶数の場合）、ｚｉ ＝ α−（ｉ＋１）／２（ｉが奇数の場合）に対して、
2005500730.tif 000013
かつ、
2005500730.tif 000014
が成り立つ。
前記符号ワード多項式ｃ（ｘ）は、次式によって計算できる。
2005500730.tif 000015
この式において、当該符号ワード多項式ｃ（ｘ）の係数は、前記符号Ｃにおける前記符号ワードｃを形成する。
【００５７】
特定の用途として、本発明は、ＤＶＲ（ディジタルビデオレコーディング）において使用されるアドレスワードを符号化するために、特にＤＶＲにおいて使用されるウォブルアドレスのアドレスワードを符号化するために使用される。ＲＳ符号化ユニット６２は、記号が４ビットである非系統的な［１５，９，７］リードソロモン符号を使用する。９つの情報記号ｍ０， …， ｍ８は、以下のように符号ワードｃ（ｘ）に符号化される。
最初に、親の生成多項式ｇ（ｐ）（ｘ）が、次のように定義される。
2005500730.tif 000016
【００５８】
各情報記号ｍｉに対して、親の生成多項式ｇ（ｐ）（ｘ）から導かれる生成多項式ｇ（ｉ）（ｘ）が定義される。この生成多項式ｇ（ｉ）（ｘ）は、親の生成多項式から０の１つを取り除き、その結果を、ｇ（ｉ）（ｚｉ） ＝１となるように正規化することによって導かれる。取り除く０のｚｉは、次式によって与えられる。
ｚｉ＝αｉ／２＋６（ｉが偶数であり、かつ０≦ｉ≦６の場合）
ｚｉ＝α−（ｉ＋１）／２（ｉが奇数であり、かつ１≦ｉ≦７の場合）
次に、０≦Ｉ≦７について生成多項式が次式によって計算される。
2005500730.tif 000017
このとき、式
2005500730.tif 000018
かつ、
2005500730.tif 000019
が成り立つ。
【００５９】
生成多項式と親の生成多項式を使用することにより、符号ワードｃ（ｘ）を次式によって計算できる。
2005500730.tif 000020
式中、符号ワード多項式ｃ（ｘ）の係数は、符号Ｃにおける符号ワードｃを形成する。αは、原始多項式Ｐ（ｘ） ＝ ｘ４＋ｘ＋１の原始根００１０である。符号ワードの記号ｃ１４が、ディスク６３に最初に記録され、符号ワードの記号ｃ５， …， ｃ０のすべてのビットが記録の前に反転される。
【００６０】
本発明の特定の用途においては、アドレスは、長さ１５、最小ハミング距離ｄ＝７のＲＳ符号を使用して符号化される。一般に、ｋ個の０が連続する０でない符号ワードｃは、少なくともｋ＋１の重みを有する、すなわち、少なくともｋ＋１個の位置に０でない記号を有する。２つの符号ワードの間の差も符号ワードであるため、２つの符号ワードは、少なくともｋ＋１個の位置において異なる、すなわち、２つの任意の符号ワードの間の最小ハミング距離はｋ＋１である。本発明に従って使用される符号においては、すべての符号ワードはα０， …， α５において０を有し、この結果として、最小ハミング距離ｄ＝７である。２つの情報ワードｍが共通の情報記号ｍｉを有する場合、対応する符号ワードの差ベクトルは、余分な０を１つ有する。この０が既存の一連の０を拡張する場合には、ｍｉが共通であるすべての符号ワードの間の最小ハミング距離は８になる。言い換えれば、情報記号が事前に既知であると、符号のハミング距離を増加させることができる。
【００６１】
各情報記号ｍｉは、親の生成多項式ｇ（ｐ）（ｘ）における０に対応する。次の表は、各情報記号の対応する０因数を示す。
2005500730.tif 000021
【００６２】
留意すべき点として、情報記号ｍ８には対応する０がない。１つの情報記号が既知であり、かつその対応する０が既存の一連の０を拡張する場合、ハミング距離が増加する。例えば、ｍ０またはｍ１が既知である場合、ハミング距離はｄ＝８になる。（ｍ０とｍ１）または（ｍ０とｍ２）または（ｍ１とｍ３）が既知である場合には、ハミング距離はｄ＝９になる。
【００６３】
このＥＣＣ方式の復号方法は、通常の（系統的な）ＲＳ符号が使用される状況とほぼ同じである。切断されているかもしれない符号ワードｒがデータキャリア６３から読み取られると（または伝送回線を介して受信されると）、その符号ワードは、最初に標準のＲＳ復号器６４（説明されている用途においてはハミング距離が７である符号用）によって復号化される。この特定の復号化方法においては、既知であるいくつかの情報記号は、復号化の後に追加チェックとして（暗黙的に）使用されるのみである。前述されているように、この知識なしに訂正できる誤りよりも多くの誤りの訂正を試みることによって、この知識を使用することも可能である。
【００６４】
次に、得られた中間符号ワードｒ’は、ＲＳ後処理ユニット６６とアドレス後処理ユニット６７とを有する後処理ユニット６５に入力される。ＲＳ後処理ユニット６６において、情報記号に対応する０における中間符号ワードｒ’を評価することによって、すなわちシンドローム計算によって、情報記号ｍｉを得ることができる。
2005500730.tif 000022
【００６５】
最後の情報記号（説明されている例においてはｍ８）は、系統的な記号であり、ｒ’の最上位記号（この例においてはｒ’１４）をコピーすることによって、中間符号ワードから直接得ることができる。
【００６６】
その後、アドレス後処理ユニット６７において、図９に示されている回路を使用して情報記号ｍからアドレスワードａを得ることができる。この回路は、アドレスワードを前処理するために必要な構造、すなわち図８に示されている前処理ユニット６１に極めて類似している。
【００６７】
上記に説明したＥＣＣ方式を使用する利点は、アドレスの一部が復号化の前に既知である場合に、符号の距離を増加させることができることである。しかしながら、この事前の知識を実際に使用するのは駆動オプションである。この知識が得られていない場合、このステップは省略することができ、その場合、中間符号ワードからアドレスを計算するための後処理を伴う通常の復号化手順となる。
【００６８】
情報ワードの記号のいくつかが復号化の前に既知であるとき、ＲＳ符号の余分な距離を利用できる。アクセス時の駆動装置のジャンプの精度が既知であるとき、目標位置の最上位アドレス記号が既知となる。この情報は、復号化に使用できる。しかしながら、これらの記号の１つが変化して、とりうる値が２つある領域がある。さらには、１つ以上の最上位ビットが変わる位置の近くに読み取り／書き込みヘッドが到達すると、アドレス記号が１つも既知にならない状況も生じうる。一例、として、アドレスが０１１１１１１１である位置にヘッドが到達するとする。この場合、次の位置のアドレスは、従来の２進表現を使用することを想定すると１０００００００であり、このことは、復号化の前に既知になると想定できる情報記号が存在しないことを示す。
【００６９】
本発明によると、アドレスの前処理が使用される。これにより、ディスクの内側から外側にジャンプするときに、情報記号ｍ０ … ｍ５が一度に１つのみ変わる。従って、ジャンプの精度が、実際の到達場所のアドレスと目標の到達場所のアドレスとの差が最大ｋである程度の場合、各ジャンプ時に少なくともｋ−１個の記号が既知となる。
【００７０】
このことを例、を通じて説明するため、いま、ジャンプがアドレス１０００００（１６進）に行われ、このジャンプの精度が、到達しうるゾーンが０Ｆｘｘｘ（１６進）と１０ｘｘｘ（１６進）の間であるような精度とする。この場合、実際の到達アドレス（ａ０， ａ１）は、（００００， １１１１）または（０００１， ００００）のいずれかである。（ａ０， ａ１） ＝ （０００１， ００００）は、（ｍ０， ｍ１） ＝ （０００１， １１１１）に符号化され、（ａ０， ａ１） ＝ （００００， １１１１）は、（ｍ０， ｍ１） ＝ （００００， １１１１）に符号化されるため、ｍ１の値は、範囲全体について１１１１である。このｍ１の知識により、符号の有効な距離が増加する。ｄ＝７のＲＳ復号器とＲＳ後処理による復号化の後、ｍ１を使用することにより、復号化の結果が有効であるか否かをチェックできる。ｍ１＝１１１１であるか否かのチェックは、ａ０とａ１の有効な組合せ、すなわち（ｘｘｘ０， １１１１）または（ｘｘｘ１， ００００）が存在するか否かをチェックすることに等しい。言い換えれば、復号化されたアドレスが、駆動装置のジャンプの精度によって定義される範囲内にあるか否かをチェックする必要がある。
【００７１】
獲得できる余分な距離は、駆動装置のジャンプ精度に依存する。次の表は、ディスク形式の特定の例、によって区別できる３つの方式の概要を示す。
2005500730.tif 000023
【００７２】
この表は、ジャンプ精度と、ＲＳ符号のハミング距離とは相関関係があることを示す。シークが大きいとジャンプ精度が小さくなることがあり、逆にシークが小さい、または大きなシーク後にリトライがあると、ジャンプ精度が大きくなることがある。
【００７３】
復号化部分の中にいくつかの追加の（小さく単純な）ブロックを使用することで、公知の誤り訂正方式によってアドレスをより高い信頼性で読み取ることができる。この追加のブロックは、ＲＳ符号の非系統的な符号ワードからアドレス情報を得るのに必要である。ＲＳ符号の利点を利用するためには、復号化の後のアドレスのチェックのみ必要である。ジャンプ精度のため、復号化されたアドレスが予期できる範囲内にあるか否かをチェックすることによって、復号化の結果の信頼性がかなり高まる。これは、本発明によって使用されるＲＳ符号によって作成される余分な距離のためである。
【００７４】
本発明は、以下のように説明することもできる。すなわち、誤り訂正符号
2005500730.tif 000024
が一定の生成行列
2005500730.tif 000025
と共に使用され、最小ハミング距離が
2005500730.tif 000026
であると想定すると、グレイ符号は、アドレス情報のアドレスベクトル
2005500730.tif 000027
と補助データとをベクトル
2005500730.tif 000028
にマッピングする。このベクトル
2005500730.tif 000029
は、
2005500730.tif 000030
による符号化のための情報シーケンスとしての役割を果たす、すなわち、
2005500730.tif 000031
は
2005500730.tif 000032
にマッピングされる。いま、
2005500730.tif 000033
がアドレスベクトルであり、かつ△が正の整数のとき、
2005500730.tif 000034
は、
2005500730.tif 000035
のアドレスとの差が最大で△である任意の
2005500730.tif 000036
について
2005500730.tif 000037
と
2005500730.tif 000038
とが一致する一連の索引として定義される。整数△は、ジャンプ精度と見なすことができ、
2005500730.tif 000039
は、読み取りまたは書き込みヘッドが到達すべき目標アドレスと見なすことができる。
【００７５】
例えば、８ビットのアドレスを考え、
2005500730.tif 000040
番目のアドレスが整数
2005500730.tif 000041
の２進表現に対応し、
2005500730.tif 000042
であるとする。
2005500730.tif 000043
は整数１４６に対応するため、セット
2005500730.tif 000044
は、１４６−△と１４６＋△の間の数に対応する任意のベクトル
2005500730.tif 000045
について
2005500730.tif 000046
が
2005500730.tif 000047
に一致する、索引｛０，１，．．．，７｝のサブセットである。
【００７６】
原理的には、目標アドレス
2005500730.tif 000048
とジャンプ精度△から
2005500730.tif 000049
を計算でき、すべての
2005500730.tif 000050
について、ｇ（ａ’）（ａ’は実際の到達位置のアドレス）の
2005500730.tif 000051
番目の情報記号が
2005500730.tif 000052
の
2005500730.tif 000053
番目の記号に等しいことを、復号化において使用できる。しかしながら、特定の目標アドレス
2005500730.tif 000054
に対する
2005500730.tif 000055
の計算は、非常に面倒な場合がある。さらに、
2005500730.tif 000056
は
2005500730.tif 000057
に依存するため、原理的に復号化は
2005500730.tif 000058
にも依存することになる。復号化が
2005500730.tif 000059
に依存することを回避するため、最大ｔ個の誤りを復号化する従来の復号器を
2005500730.tif 000060
に使用し、その後、その復号化の結果
2005500730.tif 000061
のアドレスと
2005500730.tif 000062
のアドレスとの差が△以下であるか否かをチェックすることができる。すなわち
、
2005500730.tif 000063
の既知の情報記号に関する余分な情報が、復号化には使用されず、誤り検出目的のみに使用される。
【００７７】
2005500730.tif 000064
が実際の到達場所に対応する（壊れていない）アドレスベクトルを示す場合、
2005500730.tif 000065
ならば間違った訂正が行われることになる。このような間違った訂正は、非常に望ましくない影響を及ぼすことがあり、例えば、書き込みが間違った場所から開始されたり（
2005500730.tif 000066
の場合）、場合によっては上書きしてはいけないデータが上書きされてしまうこともある。
2005500730.tif 000067
が、
2005500730.tif 000068
によって索引化される情報記号において０を持つ
2005500730.tif 000069
の全ワードで構成される符号の最小距離を示す場合には、
2005500730.tif 000070
のアドレスと
2005500730.tif 000071
のアドレスとの差は最大で△であるため、
2005500730.tif 000072
と
2005500730.tif 000073
の間のハミング距離は少なくとも
2005500730.tif 000074
であり、従って誤った訂正が発生するのは、少なくとも
2005500730.tif 000075
個の誤りが生じた場合のみである。この条件は、
2005500730.tif 000076
が
2005500730.tif 000077
より大きければ、
2005500730.tif 000078
個の誤りが発生するよりもずっと起こりにくい。言い換えれば、誤った訂正が行われる確率は大幅に減少する。
【００７８】
【００７８】
2005500730.tif 000079
が
2005500730.tif 000080
より大きくなるためには、符号
2005500730.tif 000081
は適切に符号化される必要があり、すなわち、行列
2005500730.tif 000082
を適切に選択する必要がある。１つの方法は、符号パンクチャリングに基づく構造を使用することである。これは、
2005500730.tif 000083
行列を示し、式中のＩは
2005500730.tif 000084
単位行列、すなわち対角線上が１でそれ以外が０である
2005500730.tif 000085
行列を示す。
2005500730.tif 000086
によって生成される符号は最小距離
2005500730.tif 000087
を有すると想定する。次に、
2005500730.tif 000088
位置が一致する相異なる２つの情報ベクトル
2005500730.tif 000089
と
2005500730.tif 000090
を考える。ワード
2005500730.tif 000091
2005500730.tif 000092
と
2005500730.tif 000093
は、少なくとも
2005500730.tif 000094
位置において異なる。従って、
2005500730.tif 000095
と
2005500730.tif 000096
は、少なくとも
2005500730.tif 000097
位置において異なると結論することができる。
【００７９】
【００７９】
2005500730.tif 000098
によって生成される符号
2005500730.tif 000099
の復号化は、次のように行うことができる。このとき、情報記号のセット
2005500730.tif 000100
が既知であると想定する。長さ
2005500730.tif 000101
の受信されたベクトルに、（概念的に）
2005500730.tif 000102
個の記号を接頭部として置く。
2005500730.tif 000103
に対応する既知の記号が埋め込まれ、残りの記号は消去要素として宣言される。次に、Ｘによって生成される符号に対して誤り／消去要素復号器を適用する。このようにして、いくつかの情報記号の知識を使用することで、この知識がない場合よりも多くの誤りを修正できる。上述されているように、いくつかの情報記号の知識を誤り検出のみに採用する場合には、
2005500730.tif 000104
用の復号器が必要である。このような復号器は、次のように実施できる。受信されたベクトルに、
2005500730.tif 000105
に関係なく
2005500730.tif 000106
個の消去要素を接頭部として置き、
2005500730.tif 000107
によって生成された符号に対して誤り／消去要素復号器を適用する。
【図面の簡単な説明】
【図１】符号ワードの従来の形式を示す。
【図２】符号化／復号化方式のブロック図を示す。
【図３】本発明によって情報ワードを符号化するための装置を示す。
【図４】本発明によって復号化するための装置を示す。
【図５】本発明によって符号化するための装置の別の実施例、を示す。
【図６】本発明によって復号化するための対応する装置を示す。
【図７】本発明による符号化／復号化方式の別の実施例、のブロック図を示す。
【図８】アドレス記号を情報記号に符号化するための回路を示す。
【図９】情報記号をアドレス記号に復号化するための回路を示す。
【符号の説明】
１  データ源
２  ソース符号器
３  ＥＣＣ符号器
４  変調器
５  チャネル
６  復調器
７  ＥＣＣ復号器
８  ソース復号器
９  データシンク
１０  符号化装置
１１  符号化ユニット
１２  選択ユニット
１３  書き込みユニット
１４  データキャリア
２０  復号化装置
２１  読み取りユニット
２２  符号化ユニット
２３  格納ユニット
２４  加算ユニット
２５  減算ユニット
２６  復号化ユニット
２７  形成手段
４０  符号化装置
４１  符号化ユニット
４２  選択ユニット
４４  符号ワード生成ユニット
５０  拡張ユニット
５１  置換ユニット
５２  復号器ユニット
６０  符号器
６１  アドレス前処理ユニット
６２  ＲＳ符号器
６３  ディスク
６４  ＲＳ復号器
６５  後処理ユニット
６６  ＲＳ後処理ユニット
６７  アドレス後処理ユニット
７０  ＸＯＲゲート
ｃ  符号ワード
ｍ  情報ワード
ｒ  符号ワード
ｒ’  疑似符号ワード
ｓ  中間ワード
ｔ  中間符号ワード
ｐ  パリティワード
Ｃ  符号
Ｃ’  部分符号
Ｇ  生成行列
Ｇ’  部分符号生成行列
Ｇ’’  中間生成行列
ｎ  雑音
【図１】
2005500730.tif 000121
【図２】
2005500730.tif 000122
【図３】
2005500730.tif 000123
【図４】
2005500730.tif 000124
【図５】
2005500730.tif 000125
【図６】
2005500730.tif 000126
【図７】
2005500730.tif 000127
【図８】
2005500730.tif 000128
【図９】
2005500730.tif 000129
【国際公開パンフレット】
2005500730.tif 000130
2005500730.tif 000131
2005500730.tif 000132
2005500730.tif 000133
2005500730.tif 000134
2005500730.tif 000135
2005500730.tif 000136
2005500730.tif 000137
2005500730.tif 000138
2005500730.tif 000139
2005500730.tif 000140
2005500730.tif 000141
2005500730.tif 000142
2005500730.tif 000143
2005500730.tif 000144
2005500730.tif 000145
2005500730.tif 000146
2005500730.tif 000147
2005500730.tif 000148
2005500730.tif 000149
2005500730.tif 000150
2005500730.tif 000151
2005500730.tif 000152
2005500730.tif 000153
2005500730.tif 000154
2005500730.tif 000155
2005500730.tif 000156
2005500730.tif 000157
2005500730.tif 000158
2005500730.tif 000159
【国際公開パンフレット（コレクトバージョン）】
2005500730.tif 000160
【国際調査報告】
2005500730.tif 000161
2005500730.tif 000162