JP4194850B2 - 部分的に演繹的に分かる情報の符号化及び復号 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、入力される多分損なわれているコードワードを復号するデコーダにより少なくとも１つの情報シンボルが演繹的に分かっている場合に、向上されたエラー訂正能力を提供するように、情報シンボルを有する情報ワードを符号化するための生成行列（generator matrix）を選択する方法に関する。本発明は、更に、情報ワードをコードワードに符号化する方法に関すると共に、コードの多分損なわれているコードワードを情報ワードに復号する方法にも関する。更に、本発明は、情報ワードを符号化するための対応する装置、多分損なわれているコードワードを復号するための対応する装置、上記方法を実施化するコンピュータプログラム、ユーザデータを記録するデータ担体及びユーザデータを伝送するための信号にも関する。
【０００２】
【従来の技術】
情報ワードをコードワードに符号化するために生成行列を使用するという概念は広く利用されており、例えば１９８４年５月、アジソン・ウエズレイのRichard E. Blahutによ“エラー制御コードの理論及び実用”から既知である。斯様な生成行列は、特に、ＣＤオーディオ規格のような規格に使用され及び記載されている。
【０００３】
エラーに対する情報の保護のための系統的な代数コードの使用に関する特別な例として、光媒体上のアドレス取り出しの分野においては、光媒体上のセクタアドレスが、エラー訂正コードにより保護されたヘッダの一部となっている。例えば連続したセクタが書き込まれ又は読み出されなければならない場合、又は大凡既知のディスク領域への強制トラックジャンプの場合等の多くの状況下では、現セクタのヘッダ情報の多くは、前に読み取られたセクタ及び内容テーブルから推測することができる。しかしながら、既知のコードに関しては、情報シンボルの部分的知識は、当該コードの改善されたエラー訂正能力には殆ど繋がらない。
【０００４】
【発明が解決しようとする課題】
従って、本発明は、シンボルエラーを生じるチャネルに対する符号化に関するもので、エンコーダには分からないサイドチャネルが、多分、送信されたコードワードにおいて符号化された情報の一部に関しデコーダに通知する。本発明の目的は、復号に先立ち幾つかの情報シンボルが分かる場合にエラー訂正能力が向上されるようなコードを設計することにある。本発明の他の目的は、情報ワードをコードワードに符号化する方法、及び斯様な符号化方法により符号化された多分損なわれているコードワードを復号する方法を提供することにある。更に、対応する装置も提供されるであろう。
【０００５】
【課題を解決するための手段】
これらの目的は、請求項１の生成行列を選択する方法により達成され、該方法によれば、上記生成行列は、上記コードの少なくとも１つのサブコードの最小ハミング距離が該コードの最小ハミング距離よりも大きくなり、上記サブコードのサブコード生成行列が前記コードの生成行列から、該生成行列の前記少なくとも１つの演繹的に既知な情報シンボルに対応する少なくとも１つの行を削除することにより派生するように選択される。更に、これらの目的は、請求項７に記載の符号化する方法及び請求項１２に記載の復号する方法によっても達成される。
【０００６】
本発明によれば、情報ワードのコードワードへのマッピングは、当該情報ワードの幾つかの情報シンボルが既知である場合に、デコーダが実効ハミング距離を向上させることができるようなものとする。しかしながら、デコーダは何のシンボル（もしあるなら）が実際にデコーダにより知られているかについて通知されないと仮定する。実効ハミング距離の斯様な向上を得るために、或る所定の（即ち、予め選択された）生成行列が使用される。この場合、上記所定の生成行列は符号化及び復号のために使用される。即ち、該生成行列は標準の生成行列として使用される必要がある。言い換えると、該生成行列は、サブコードの最小ハミング距離が完全なコードの最小ハミング距離よりも大きくなるように選択される。
【０００７】
上記所定の生成行列を使用する場合、アドレス情報は一層高信頼度で保護することができる。アドレス情報の一部、例えば最上位ビット、がデコーダにより既に分かっているなら、データ担体（例えば、ディスク）上の或るアドレスにアクセスする新たなコマンドが与えられた場合、アドレスの取り出しは一層高信頼度となり、これは書き込みの間に特に重要である。この場合、デコーダは、増加された最小ハミング距離を有するサブコードを有効に使用することができる。しかしながら、情報シンボルがデコーダにより演繹的に分かっていない場合、取り出されたコードワードの復号は通常の様に可能であり、本発明により使用されるコードのハミング距離は既知のコードのハミング距離と同一となるであろう。即ち、復号の間において、より大きな最小ハミング距離のサブコードは使用することはできない。
【０００８】
多分損なわれたコードワードを入力する場合（例えば該コードワードをデータ担体から読み取ることにより）であって、少なくとも１つの情報シンボルがデコーダにより演繹的に分かる場合（例えば、読取アドレスの最上位ビット）、当該デコーダは、先ず、前記生成行列のうちの上記情報シンボルの対応する情報ワードをコードワードに符号化するために既に使用された対応する行を使用することにより上記既知の情報シンボルを符号化し、次いで、該結果を加算して中間ワードを得る。その後、斯様な中間ワードは、復号されるべき入力コードワードから減算される。該結果は、次いで既知の復号方法により、上記情報ワードを符号化するために使用された生成行列のうちの未知の情報シンボルに対応する部分のみを有するサブコード生成器を用いて復号される。即ち、符号化のために使用された上記生成行列から、当該デコーダにより演繹的に分かる情報シンボルに対応する行が削除され、該デコーダは上記生成行列の残りの行のみを、上記減算の結果を復号するためのサブ生成行列として使用する。このことは、上記サブコード生成行列においては、上記生成行列のうちの演繹的に分かる情報シンボルに対応しない行のみが現れることを意味する。
【０００９】
上述したように生成行列を選択する場合、復号に先立ちデコーダにより幾つかの情報シンボルが分かるなら、エラー訂正能力を向上させることができる。どの及びどれだけ多くの情報シンボルがデコーダにより分かるかに依存して、異なるレベルの改善が存在し得る。
【００１０】
本発明の好ましい実施例が請求項２に記載されている。この実施例によれば、当該コードの生成行列は、全て異なる数の行を有するような少なくとも２つのサブコード生成行列を有し、斯様なサブコード生成行列の全ての行は前記生成行列の一部である。即ち、上記サブコード生成行列から派生するサブコードは、前記生成行列から派生する前記コード内で入れ子にされている。上記生成行列の各行は、各々が或る数の零を有するような多項式を表すものと見なすこともできる。本実施例によれば、或る零は、各多項式に対して、即ち上記生成行列の１行により表される多項式に対して共通となる。しかしながら、各多項式は、少なくとも１つの零においては各他の多項式とは相違する。この実施例の場合、ハミング距離が当該デコーダにより演繹的に分かる情報シンボルの数と共に増加することが成り立ち得る。
【００１１】
上記生成行列は、該マトリクスのエラー訂正能力が当該デコーダにより演繹的に分かる情報シンボルの数の増加に伴い増加するように選択することもできる。上記生成行列は、更に、該生成行列の全てではないが幾つかの行により発生される前記コードの全ての適切なサブコードのハミング距離が、該コードのハミング距離よりも大きくなるように選択することもできる。このことは、１つの情報シンボルが当該デコーダにより演繹的に分かる場合に既に、どの情報シンボルが演繹的に分かっても当該コードが、改善されたエラー訂正能力を有するという利点を有している。
【００１２】
上記生成行列を選択する方法の他の好ましい実施例は、請求項３ないし６に記載されている。本発明による情報ワードをコードワードに符号化する方法は請求項７に記載され、該方法の好ましい実施例は請求項８ないし１１に記載されている。本発明による多分損なわれているコードワードを情報ワードに復号する方法は請求項１２に記載され、該方法の好ましい実施例は請求項１３ないし１８に記載されている。
【００１３】
本発明による多分損なわれているコードワードを復号する方法は、前記情報ワードが本発明により選択された生成行列を用いて上記コードワードに符号化されると共に、上記の多分損なわれているコードワードを向上されたエラー訂正能力で復号するために、該多分損なわれているコードワードに含まれている前記少なくとも１つの演繹的に分かる情報シンボルの寄与が考慮されることを概略特徴とする。好ましい実施例においては、前記の多分損なわれているコードワードに含まれる前記少なくとも１つの演繹的に分かるシンボルの寄与は、上記多分損なわれているコードワードを復号する前に、該多分損なわれているコードワードから減算されることにより考慮される。
【００１４】
本発明の好ましい実施例は、コードパンクチャリング（間引き）に基づくものである。該実施例では、情報ワードを、通常の生成行列を用いて符号化されたコードワードよりも大きな長さを持つ中間コードワードに符号化するために一層大きな中間生成行列が使用される。しかしながら、これら中間コードワードからは、最終的なコードワードを得るために幾つかのシンボルが削除される。復号する間において、受信された多分損なわれているコードワードは、先ず、演繹的に分かる情報シンボルの使用により拡張されて擬似コードワードを求め、次いで該擬似コードワードは符号化の間に使用された前記中間生成行列を用いて復号される。その後、得られた第２擬似コードワードはエラー及び消去デコーダ（好ましくは既知の構成の）に入力され、情報ワードを取り出す。
【００１５】
この実施例の１つの主たる利点は、演繹的に分かる情報シンボルが順番に分かるか否かに関係なく、一層大きなハミング距離が達成される点にある。情報シンボルが順番に分からなくても、本発明の該実施例により生成行列が選択及び使用されれば、サブコードの最小ハミング距離は各追加の既知の情報シンボルにより増加することができる。
【００１６】
本発明の有利な用途は、特に光媒体上のアドレス検索の分野にある。本発明を使用すると、アドレス又はタイミング情報は、高いエラー訂正能力により保護することができ、アドレス検索を一層確実及び正確にすることができる。更に、本発明は、例えば電気通信システム又はインターネット等の伝送ライン上で伝送されるような直列データストリームにおけるアドレスを確実にするために使用することもできる。一般的に、本発明は、情報の一部がデコーダにより演繹的に分かる場合に、既知のコードと比較して改善されたエラー訂正能力を有するコードにより該情報を保護するために使用することができる。
【００１７】
本発明により情報ワードを符号化する装置及び多分損なわれているコードワードを復号する装置は、請求項２３及び２４に記載されている。これらの装置は、更に発展させることができると共に、請求項１による生成行列を選択する方法を参照して前述したものと同様の実施例を有することができると理解すべきである。
【００１８】
本発明による何れか又は全ての方法を実施化するための本発明によるコンピュータプログラムは請求項２５に記載されている。
【００１９】
本発明によるデータ担体は請求項２６及び２７に記載されている。斯様なデータ担体は、好ましくはオーディオ、ビデオ又はソフトウェアデータを記憶するために使用されると共に、特にＣＤ又はＤＶＤ等の光記録担体のような記録可能又は書換可能な型式のものとすることができる。特別な用途は、デジタルビデオ記録（ＤＶＲ）の分野にある。一般的に、斯様なデータ担体は、特にアドレスデータ、タイミングデータ又は位置データ等の特定のシステムデータ項目のようなシステムデータ項目を有し、これらシステムデータ項目は、当該データ担体の生産現場において該データ担体上に既に記憶されると共に、ユーザデータを記録するための空データ担体が購入される場合に既に存在している。本発明は、斯かるシステムデータ項目を符号化するために使用することができる。しかしながら、本発明はユーザデータを符号化するためにも同様に使用することができる。
【００２１】
【発明の実施の形態】
以下、本発明を、添付図面を参照して詳細に説明する。
【００２２】
図１は、例えばリードソロモンコード等の、［ｎ，ｋ］ブロックコードのコードワードの典型的な構成を示している。コードワードは、ｋ個の情報シンボルを有する情報ワードｍと、該情報ワードをコードワードｃに符号化する際に発生されるｎ−ｋのパリティシンボルを有するパリティワードｐとを有している。
【００２３】
図２は、符号化及び復号を使用する典型的なシステムのブロック図である。該システムにおいて、例えばマスタテープ又はマスタディスク上に記録された、データソース１から到来するオーディオ又はビデオデータ等のユーザデータは、例えばディスク等のデータ担体上に記憶される前に符号化されるか、又は例えば再生すべくデータ受信部（シンク）９に供給するために再度復号される前に、伝送チャネルを介して（例えばインターネットを介して）伝送される。
【００２４】
見られるように、ソース１のユーザデータは、先ずソースエンコーダ２により符号化され、次いでＥＣＣエンコーダ３によりエラー訂正符号化され、その後、該符号化されたユーザデータ（コードワード）がチャネル５に送出される前に例えばＥＦＭ変調器等の変調器４により変調されるが、上記チャネルにおいてはエラーが上記コードワードに導入される可能性がある。ここで、上記チャネル５は、伝送チャネル及び後の再生のためにデータ担体上での符号化データの記憶を含むように広く解釈されるべきである。
【００２５】
データの再生が意図される場合、ＥＣＣデコーダ７によりエラー訂正復号され、ソースデコーダ８によりソース復号される前に、上記の符号化されたデータは先ず例えばＥＦＭ復調器のような復調器６により復調されねばならない。最後に、該復号されたユーザデータは、例えば該ユーザデータの再生用のプレーヤ装置のようなシンク９に入力することができる。
【００２６】
しかしながら、斯様な一般的なシステムは、ユーザデータを符号化及び復号するために使用されるのみならず、管理データ、特にはアドレスデータのような如何なる種類のデータに対しても使用され得る。このようなアドレスデータは、データ担体上又はユーザデータのデータストリーム内における特定の位置を見付けるために使用される。書込可能又は書換可能ディスク上では、斯様なアドレスデータは、一般的に、ユーザデータが記録される前に空のディスク上に事前記録されている。
【００２７】
本発明は、データの符号化及び復号に関するものである。本発明においては、或る所定の生成行列が使用され、該マトリクスの選択も、本発明による方法により参照されるものである。本発明の特段の用途は、光記録担体上で使用されるアドレスのアドレス検索の分野にある。
【００２８】
図３は、本発明による情報ワードｍを符号化する装置の一実施例を示している。該実施例において、符号化装置１０は固定数の情報シンボルｍ_１、ｍ_２、…、ｍ_ｋを有する情報ワードｍをコードＣのコードワードｃに符号化する符号化ユニット１１を有している。改善されたエラー訂正能力を達成するために、情報ワードｍを符号化するために或る所定の生成行列Ｇが使用される。この生成行列Ｇは選択ユニット１２により、一旦、選択及び定義され、連続的な使用のために符号化装置１０及び復号装置に供給され、好ましくは記憶される。かくして、生成行列Ｇの使用により、上記情報ワードｍは符号化ユニット１１によりコードワードｃに符号化される。これらのコードワードｃは、該コードワードｃを例えばＣＤ又はＤＶＤ等の光記録担体１４上に記録する書込ユニット１３に供給することができる。
【００２９】
例示として、本発明、特に生成行列Ｇの好ましい選択を更に詳細に説明する。本例は、g(x) = x³ + x + 1 により発生される［７，４，３］二進ハミングコードＣに基づくものである。最初に該コードの“通常の”既知の使用について説明し、その後、本発明によるコードの使用を説明する。
【００３０】
通常、コードＣは系統的な形で使用され、これは、４個の（一般的にｋの）行と７個の（一般的にｎの）列とを有する生成行列：
【数１７】

に対応する。情報ワードｍ＝（ｍ_１，ｍ_２，ｍ_３，ｍ_４）はコードワードｃ＝ｍ・Ｇ_sysにマップされる。復号前に当該デコーダによりｉ番目の情報シンボルｍ_ｉが既知の場合は、該デコーダは復号に先立ち、受信されたワードｒに対するｍ_ｉの貢献を差し引くことができる。このことは、上記デコーダが、残りの受信されたワードｒ−ｍ_ｉ・Ｇ_sys ⁱ（Ｇ_sys ⁱはＧ_sysのｉ番目の行を示す）を、ｉ番目の行が生成行列Ｇ_sysから削除され場合のコードに復号することを意味する。如何なる３つの情報ビットまでの知識も、未知の情報ビットに対する訂正能力を著しく変化させることはない。何故なら、Ｇ_sysの多くて３行を削除することにより得られるコードＣの殆ど全てのサブコードＣ’も依然としてハミング距離３を有するからである。情報ビットｍ_１、ｍ_３及びｍ_４が既知である場合にのみ、ｍ_２を取り出すハミング距離が４に増加される。
【００３１】
本発明によれば、同じコードＣに対する他の生成行列Ｇ_idは、
【数１８】

として示すことができる。コードＣの符号化のために（非系統的）生成行列Ｇ_idが使用されるとしたら、或る情報ビット又は情報シンボル（情報シンボルは２ビット以上を有することができる）が既知の場合は、図４に示すような通知されたデコーダはコードＣの一層好ましいサブコードＣ’に復号することができる。例えば、当該デコーダが最初の情報ビットｍ_１を知っている場合は、該デコーダは［７，３，４］シンプレックスコードに対応する、Ｇ_idの最後の３行ｇ_２、ｇ_３、ｇ_４により発生されるサブコードＣ’を使用することができる。他の例として、当該デコーダにより最後の３ビットｍ_２、ｍ_３、ｍ_４が分かる場合は、該デコーダは［７，１，７］繰り返しコードに対応するＧ_idの最初の行により発生されるサブコードを利用し、該デコーダが３ビットエラーの存在にも拘わらずｍ_１を高信頼性で再現することを可能にすることができる。
【００３２】
読み取られた多分損なわれているコードワードを復号する装置が、図４に示されている。該図において、復号装置２０は読取ユニット２１によりデータ担体１４から読み取られた、多分損なわれているコードワードｒを入力する。コードワードｃに符号化された情報ワードｍが４つの情報シンボルｍ_１、ｍ_２、ｍ_３、ｍ_４を有すると仮定すると共に、更に、復号するための装置２０が演繹的に３つの情報シンボルｍ_２、ｍ_３、ｍ_４を知っていると仮定すると、第１ステップにおいて、上記既知の情報シンボルｍ_２、ｍ_３、ｍ_４は符号化ユニット２２により生成行列Ｇを使用して符号化される。この場合、該生成行列Ｇは、記憶ユニット２３に記憶されていると共に、データ担体１４に記憶され且つ多分損なわれているコードワードｒとして読み取られるコードワードｃを符号化するために既に使用されているものである。斯様な符号化に対して、符号化ユニット２２は生成行列Ｇのうちの上記既知の情報シンボルｍ_２、ｍ_３、ｍ_４に対応する行を使用する。
【００３３】
後続のステップにおいて、斯様な符号化の結果、即ち上記既知の情報シンボルｍ_２、ｍ_３、ｍ_４と生成行列Ｇ_idの対応する行ｇ_２、ｇ_３、ｇ_４との積、が加算ユニット２４により加算され、中間ワードｓが得られる。減算ユニット２５においては該中間ワードｓが前記の読み取られたコードワードｒから減算され、斯様な減算の結果は復号ユニット２６に供給される。該復号ユニットにおいては、サブコード生成行列Ｇ’を用いて発生されるサブコードＣ’が復号されるが、ここで、該サブコード生成行列Ｇ’は形成手段２７において生成行列Ｇから、該生成行列Ｇから上記既知の情報シンボルｍ_２、ｍ_３、ｍ_４に対応する全ての行を削除することにより（即ち、本例では行ｇ_２、ｇ_３、ｇ_４を削除することにより）生じる。従って、本例では、該サブコード生成行列Ｇ’は、生成行列Ｇの最初の行ｇ_１のみを有する。結果として、未知の情報シンボルｍ_１を、完全な情報ワードｍが最終的に分かるように、取り出すことができる。通常は、この様にして、多分損なわれているコードワードに含まれる演繹的に分かる情報シンボルの寄与が該多分損なわれているコードワードから減算され、該減算の結果が復号される。
【００３４】
上記復号方法を、例示として更に詳細に説明する。コードＣのコードワードｃは、
c = m・G = (m₁ m₂ m₃ m₄) (g₁ g₂ g₃ g₄)^T = m₁ g₁ + m₂ g₂ + m₃ g₃ + m₄ g₄
により示すことができる。
【００３５】
一般的に、生成行列Ｇはｋ個の行とｎ個の列とを有し、情報ワードｍはｋ個の列を有し、コードワードｃはｎ個の列を有している。
【００３６】
ここで、情報シンボルｍ_２、ｍ_３、ｍ_４がデコーダにより演繹的に分かり、読み取られたコードワードｒが記憶されたコードワードｃに追加のノイズｎを加えた和と仮定すると、中間ワードｓは、先ず、
s = m₂ g₂ + m₃ g₃ + m₄ g₄
と計算される。その後、読み取られた多分損なわれているコードワードｒと中間ワードｓとの間の差が、
r - s = c + n - s = m₁ g₁ + n
と計算される。この場合、情報シンボルｍ_１が１ビットを有する場合は該情報シンボルｍ_１は０又は１でしかあり得ず、生成行列Ｇの行ｇ_１は固定であり、ノイズｎは未知である。ここで、本発明により選択された先に示された生成行列Ｇ_idを使用すると、ｇ_１は(1111111)として示され、かくして、ｍ_１ｇ_１は(0000000)又は(1111111)でしかあり得ない。前述したｍ_１ｇ_１＋ｎの計算が例えば(0010011)なる結果であったら、ｍ_１ｇ_１が(0000000)として与えられ、結果としてｍ_１がビット値０を有する確率が高くなる。この例から分かるように、情報シンボルｍ_１は、残りのサブコードＣ’がハミング距離７を有することを意味する３ビットエラーにも拘わらず決定することができる。
【００３７】
本発明は、高速の信頼性のあるアドレス検索用に使用することができるような簡単な例により解説することもできる。従来は、［７，４，３］なる二進ハミングコードが生成多項式g(x) = x³ + x +1により発生されている。各コードワードは、該生成多項式g(x)の二進多項式倍数である。系統的なエンコーダが使用される場合は、情報ビットは上位位置においては変化されないまま現れ、パリティビットは下位位置におけるものとなる。
【００３８】
以下に、当該コードの全ての１６個のコードワードのリストが示され、ここで、各コードワード多項式の係数はベクトルとして示される。各コードワードにおいて最上位シンボルｃ_６は左側に、最下位シンボルｃ_０は右側に位置する。４つの最左端側ビットｃ_６…ｃ_３は４つの情報ビットｍ_４…ｍ_１に対応し、３つの最右端側ビットｃ_２、ｃ_１、ｃ_０はパリティビットｐ_３、ｐ_２、ｐ_１である。検査により、何れの２つのコードワードも少なくとも３つの位置において相違することをチェックすることができ、これは、当該コードのハミング距離が３に相当し、１つのエラーを訂正することができることを意味する。

【００３９】
一例として、上から５番目のコードワードは１・g(x)に等しく（多項式表記で）、４番目のコードワードはｘ・g(x)に等しく、１０番目のコードワードはｘ^２・g(x)に等しい。知っておくのに重要なことは、如何なる２つのコードワードの(mod2)和も再びコードワードになるということである。何故なら、これはGF(2)上での線形コードである、即ち当該コードは群を形成しているからである。各情報ビットは１ビットエラーに対して保護され、幾つかの情報ビットについての如何なる知識も他の情報ビットの訂正能力を増加させない。
【００４０】
本発明によれば、情報ビットのコードワードへのマッピングは、少なくとも１つの（本例では３つの）情報ビットに関しての知識が残りの（本例では４つの）情報ビットに対する訂正能力を増加させるように変更される。以下においては、最左端側の３つの情報ビットｍ_４、ｍ_３、ｍ_２はアドレスのＭＳＢ（最上位ビット）と呼ぶことができ、最後の情報ビットｍ_１はアドレスのＬＳＢ（最下位ビット）と呼ぶことができる。本発明によるコードの構成は、ＭＳＢが分かればＬＳＢを抽出する強力なコードが達成されるようなものである。情報ビットの何れも演繹的に分からない場合は、当該エラー訂正能力は、従来のコードのエラー訂正能力と比較して変わることはない。
【００４１】
本発明によれば、コードの線形性が利用される。ＭＳＢの符号化に対しては、上記表におけるｍ_１＝０を有する系統的コードワードが単純に使用される。これらのコードワードは８個存在することに注意すべきである。ｃ（ＭＳＢ）が該符号化の結果である場合は、ＬＳＢを符号化するために、ｃ（ＬＳＢ＝０）＝0000000及びｃ（ＬＳＢ＝１）＝1111111が選択される。送信される最終的なコードワードｃはｃ＝ｃ（ＭＳＢ）＋ｃ（ＬＳＢ）に等しく、ここで“＋”はGF(2)上でのベクトル加算を示す。当該コード（GF(2)上の）の線形性のため、ｃは再び該コード（上記表）に属することに注意すべきである。更に、ｃ（ＭＳＢ）をｃ（ＭＳＢ）に加算する効果はＭＳＢの値をスクランブルする、即ちＬＳＢ＝１ならＭＳＢの値は反転される、ことにも注意すべきである。従って、当該全体のコードは、該コードの全ての情報ビットにおいて最早系統的ではない。
【００４２】
斯様なコードワードが何らかのチャネルを介して伝送されると、該コードワードにビットエラーが取り込まれる可能性がある。このように、受信されるコードワードは損なわれる可能性があって、多分損なわれたコードワードｒと呼ばれ、該コードワードはエラー位置において上記コードワードｃとは相違する。情報ビットに関して何も分からない場合は、伝送されたコードワードｃがハミングコードに属していることのみが分かり、従って常に１ビットエラーのみを訂正することができる。受信されたワードｒからコードワードｃを多分復元するエラー訂正の後、当該情報は、上記コードワードｃにおける４番目のビットに等しいＬＳＢ（情報シンボルｍ１）を先ず抽出し、与えられたＬＳＢを用いて（0000000）又は（1111111）の何れかがＬＳＢ＝０又はＬＳＢ＝１に各々依存して上記コードワードｃから減算される。その後、ＭＳＢは当該結果の最初の３ビットとして利用可能となる。しかしながら、２以上の伝送エラーが存在する場合、常に単一エラー訂正ハミングコードで生じる当該結果にエラーを生じさせる。
【００４３】
しかしながら、復号の前にＭＳＢが分かると仮定してみよう。当該コードワードの最上位部ｃ（ＭＳＢ）がデコーダにより先ず再現され、その後、受信されたワードｒから減算される。この場合、（0000000）又は（1111111）の何れかは依然としてチャネルエラーにより損なわれたままとなる。これら２つのワードの距離は７に等しいから、３ビットエラーの存在の場合であっても、ＬＳＢを見つけることができる。このように、全体のコードに対して３個のみのパリティビットを使用することにより、ＭＳＢが分かるなら、ＬＳＢは［７，１，７］繰り返しコードにより効果的に保護される。本例においては、［７，４，３］ハミングコードは［７，１，７］サブコードと、このコードのコセット（co-set）とに分割される。
【００４４】
既に説明したように、本発明は光記録担体上で使用されるアドレスを保護するために使用することができる。しかしながら、本発明は、伝送ラインを介して伝送することが可能な如何なる直列データストリームにおけるアドレスを保護するために使用することもできる。一般的に、本発明は、情報ワードがコードに符号化されるべきであり、デコーダにより少なくとも１つの情報シンボルが分かる場合に改善されたエラー訂正能力が達成されるべきであるような如何なる用途にも適用することができる。
【００４５】
もっと一般的な言葉では、本発明は如何なる線形コード、特にはリードソロモンコードに適用することができる。［ｎ，ｋ，ｎ−ｋ＋１］ＲＳコードは、ｊ個の最上位側情報シンボルが既知なら残りのｋ−ｊ個の情報シンボルの復号に関する距離がn-k+1+jに等しくなるように複数のサブコードに分割することができる。該復号手順も、ｊ個の既知の情報シンボルを再符号化し、この再符号化の結果を受信ワードから減算し、残った大距離サブコードを復号するために適切なデコーダを使用することからなる。
【００４６】
本発明の他の実施例においては、生成行列Ｇは、少なくとも２つのサブコードが該生成行列Ｇにより発生されるコード内で入れ子にされるように選択することができる。これは、以下の例により説明される。本発明によれば、生成行列ＧはG=(g₁(x)g₂(x)g₃(x))^Tとして選択され、ここで、
g₁(x) = (x-1) (x-α) (x-α²) (x-α³) = α⁶ + α⁵x + α⁵x² + α²x³ + x⁴
g₂(x) = (x-1) (x-α) (x-α²) = α³ + α⁶x + α⁵x² + x³
g₃(x) = (x-1) (x-α) = α + α³x + x²
であり、ここでαはα^３＝１＋αを満足するＧＦ(8)内の元（element）である。かくして、対応する生成行列は、
【数１９】

となる。従って、コードＣのコードワードｃ(x)は生成多項式ｇ₃(x)の多項式倍数である。かくして、この生成行列Ｇにより発生されたコードＣは、前述したR. Blahut他の文献、第７.２節から明らかなように最小ハミング距離３を有する。
【００４７】
情報ワードｍ＝（ｍ_１ｍ_２ｍ_３）の情報シンボルｍ_３がデコーダにより知られていると仮定すると、対応するサブコード生成行列Ｇ₂’＝(ｇ_１ｇ_２)^Ｔにより発生され、最小ハミング距離４を持つサブコードＣ₂’を採用することができる。斯様なサブコードＣ₂’においては、全てのコードワードは生成多項式ｇ_１及びｇ_２の組合せとなる。
【００４８】
情報シンボルｍ_２及びｍ_３が分かる場合は、サブコード生成行列Ｇ₁’＝(ｇ_１)により発生され、最小ハミング距離５を持つサブコードＣ₁’を採用することができる。
【００４９】
生成行列Ｇの上記選択に加えて、コードワードｃ＝ｍ・Ｇの計算には少ない乗算しか必要とされない。何故なら、上記生成多項式の幾つかは他の生成多項式の多項式倍数であるからである。
【００５０】
上記例から分かるように、サブコードＣ₁’及びＣ₂’はコードＣ内で入れ子にされ、各サブコードＣ₁’、Ｃ₂’は対応するサブコード生成行列Ｇ₁’、Ｇ₂’により発生される。上記サブコード生成行列Ｇ₁’、Ｇ₂’の各々は異なる数の行を有し、全ての行は前記生成行列Ｇの一部である。通常、Ｇの選択は、各サブコード生成行列が増加する数の行を有し、各サブコード生成行列が他のサブコード生成行列から１つの行を削除することにより達成することができるようなものとすることができる。上記例においては、サブコード生成行列Ｇ₁’は、サブコード生成行列Ｇ₂’から第２行を削除することにより、即ち生成多項式ｇ₂(x)を削除することにより生じる。また、サブコード生成行列Ｇ₂’は、生成行列ＧからＧの最終行を削除することにより、即ち生成多項式ｇ₃(x)を削除することにより生じる。
【００５１】
また、生成行列Ｇは、最初のｉ行（ｉは１以上の整数）がサブコードＣ_i’を得るためのサブコード生成行列Ｇ_i’を形成し、該サブコードにおいてハミング距離が、当該生成行列Ｇの最初のｉ＋１行により形成されるサブコード生成行列Ｇ_i+1’から得られるサブコードＣ_i+1’に関するものより大きくなるように選択することもできる。
【００５２】
もっと一般的には、コードＣは生成多項式
【数２０】

のＧＦ(q)上の［ｎ≦ｑ−１，ｋ、ｎ−ｋ＋１］ＲＳであり得、ここで、αはＧＦ(q)における原始元である。コードＣのコードワードは、生成多項式ｇ_k(x)の多項式倍数であるような最大でｎ−１次の多項式ｃ(x)により表される。本発明によれば、情報シンボルｍ_０、ｍ_１、…、ｍ_k-1を
【数２１】

に符号化することが提案される。このように、情報ワードｍは、ｊ番目の行が多項式ｇ_i(x)の係数からなるような生成行列Ｇを用いて符号化される。該生成行列Ｇの上側のｗ行は多項式ｇ₁(x),ｇ₂(x),…,ｇ_j(x)を表し、これらの全てはｇ_w(x)の倍数である。結果として、これらの上側のｗ行は［ｎ，ｗ，ｎ−ｗ＋１］残留コードを発生する。従って、デコーダが（ｍ_w,…,ｍ_k-1）について通知されるなら、該デコーダは、生成多項式ｇ_w(x)を用いたＲＳコード用のデコーダを用いて０.５（ｎ−ｗ）エラーまでを訂正することができる。連続したｗに関する上記残留コードは元のＲＳコードＣの入れ子にされたサブコードであることに注意すべきである。
【００５３】
他の効率的な符号化方法は下記のステップからなる。先ず、最初のコードワードパラメータｃ₁(x)がｃ₁(x)＝ｍ_１により初期化される。その後、ｊ＝２ないしｋに対して、後続のコードワードパラメータｃ_j(x)が、
【数２２】

により計算される。最後に、コードワード多項式ｃ(x)が、
【数２３】

により計算される。上記コードワード多項式ｃ(x)の係数は、一緒になってコードＣにおけるコードワードｃ＝（ｃ_０,…,ｃ_n-1）を形成する。
【００５４】
本発明の他の好ましい実施例を図５ないし図８を参照して説明する。図５及び図６には本発明による周波数ドメイン符号化用の符号化装置の２つの実施例が、図７には対応する復号装置が示され、図８には図７の復号装置の一部である抽出ユニットが詳細に図示されている。
【００５５】
周波数ドメインの符号化及び復号を、デジタルビデオ記録（ＤＶＲ）の分野における詳細な例により説明する。該例においては、一緒になって６個の情報シンボルを形成するような５つのアドレスシンボル及び１つの補助シンボルを有するアドレス情報が、ウォブル信号に記憶されるウォブルコードに符号化される。該特定の例においては、ガロア体ＧＦ(16)上の［１１，６，６］リードソロモン型コードが使用され、ここでαは原始元である。このように、コードワードｃはc(x) = c₀ + c₁x + c₂x² + … + c₁₀x¹⁰の形態のものである。当該６つのシンボル（ユーザシンボルとも呼ばれる）は、ｍ₅,ｍ₆,…,ｍ₁₀とラベルが付される。即ち、この特定の例ではシンボルｍ_０ないしｍ_４は使用されない。生成多項式ｇ(x)は、
【数２４】

として与えられる。デコーダにより情報シンボルが分からない場合は、上記コードは６なる最小ハミング距離を有する。しかしながら、情報シンボルｍ_５が分かる場合は、最小ハミング距離は１だけ増加される。当該デコーダにより分かる各追加の順次の情報シンボルによっても、最小ハミング距離は１だけ増加される。
【００５６】
符号化規則を実施化するまえに、幾つかの定義を行わなければならず、これを以下に説明する。親生成多項式ｇ^(p)(x)が、
【数２５】

により定義される。その後、５≦ｉ≦１０に対して、成分生成多項式ｇ⁽ⁱ⁾が、
【数２６】

により定義され、ここで、
【数２７】

である。この場合、コードワードｃを符号化するための規則は、
【数２８】

により与えられる。そして、上記コードワード多項式ｃ(x)の係数が、コードＣにおけるコードワードｃを形成する。
【００５７】
フィードフォワードレジスタを用いた該符号化規則の実施化が図５に示されている。該図に見られるように、第１部分において、情報シンボルｍ_５ないしｍ₁₀が先ず或るパラメータにより乗算され、各帰還シフトレジスタに供給され、次いで総和がとられる。その後、該和は親生成多項式の係数を含むフィードフォワードレジスタに入力されて、コードワードｃ(x)を形成する。
【００５８】
ｋ個の情報シンボルｍ_n-k,ｍ_n-k+1,…,ｍ_n-1を有する情報ワードｍのＧＦ(q)上の［ｎ，ｋ，ｎ−ｋ＋１］リードソロモンコードへの周波数ドメイン符号化を実施化するための一般的定義は、以下の通りである。親生成多項式((ｇ^(p)(x)))は、
【数２９】

により与えられ、ここでαは最大でｎの次数のＧＦ(q)の非零元であり、ｂは整数である。ｎ−ｋ≦ｉ≦ｎ−１に対する成分生成多項式ｇ⁽ⁱ⁾(x)は、
【数３０】

により定義され、ここで、
【数３１】

及び
【数３２】

が成り立つ。コードワード多項式(ｃ(x))は、
【数３３】

により計算することができ、ここで、上記コードワード多項式ｃ(x)の係数は当該コードＣにおけるコードワードｃを形成する。
【００５９】
符号化装置の僅かに異なる実施例が、図６に示されている。該実施例においては、［１２，７，６］コードのための及び７個の情報シンボルｍ_５、ｍ_６、…ｍ₁₁を符号化するための符号化規則が実施化される。この場合、この特別な例のための符号化規則は、
【数３４】

により表される。図５及び図６の符号化規則の間の相違点は、図６の符号化規則においては情報シンボルｍ₁₁が直接利用され、図６の装置において実施化される符号化方法は周波数及び時間ドメイン符号化の混成方法である一方、図５の装置により実施化される符号化方法が純粋に周波数ドメインの符号化方法である点にある。
【００６０】
ｋ個の情報シンボルｍ_n-k、ｍ_n-k+1、…、ｍ_n-1を有する情報ワードｍをＧＦ(q)上の［ｎ，ｋ，ｎ−ｋ＋１］リードソロモンコードのコードワードへの混成符号化を実施化するための一般的な定義は、次の通りとなる。即ち、親生成多項式(ｇ(t)(x))は、
【数３５】

として表され、ここで、αは最大でｎ次のＧＦ(q)の非零元であり、ｂは整数である。ｎ−ｋ≦ｉ≦ｎ−２に対する成分生成多項式ｇ(i)(x)は、
【数３６】

により定義され、ここで、
【数３７】

及び
【数３８】

が成り立つ。コードワード多項式(ｃ(x))は、
【数３９】

により計算することができ、ここで、上記コードワード多項式ｃ(x)の係数は当該コードＣにおけるコードワードｃを形成する。
【００６１】
上記から分かるように、これら例においては全ての成分生成多項式は、
【数４０】

なる多項式を共通に有する。従って、親及び成分生成多項式の下記の特性を情報シンボルの抽出に使用することができる：
【数４１】

このように、情報シンボルｍ_ｉは下記のように抽出することができる：
【数４２】

対応する復号装置が図７に示されている。該図において、シンボルｒ_０、ｒ_１、…、ｒ₁₁を有する受信ワードｒ(x)は、多分損なわれたコードワードである、即ちコードワードｃにノイズｎを加えたものを含むと仮定する。該受信ワードｒからシンドローム形成ユニット３０において既知の方法によりシンドロームＳ_ｊが計算され、その場合において、0 ≦ j ≦ 4に対してはS_j = c(α^j) + n(α^j) = n(α^j)、5≦ j ≦ 10に対してはS_j = n(α^j) + m_jが成り立つ。
【００６２】
k_max-4個の情報シンボルm₅, m₆, …, m_kmaxが復号前にデコーダにより分かっているとの仮定の下では、該既知の情報シンボルｍ_ｊの寄与は、5≦ j ≦ k_maxに対して算出されたシンドロームＳ_ｊから取り除くことができる。本発明によれば、従って、シンドロームＳ_ｊはシンドローム修正ユニット３１において修正され、追加の（修正された）シンドロームＳ’_jを得る。
【００６３】
0 ≦ k ≦ 4に対しては、シンドロームは修正されない、即ちS’_k = S_kとなる。しかしながら、5 ≦ k ≦ k_maxに対してはシンドロームはS’_k = S_k - m_kにより修正される、即ち当該デコーダにより対応する情報シンボルが分かる各シンドロームＳは修正される。得られた修正されたシンドロームＳ’及び演繹的に分かるシンボルの数（ｋ_max）に関する情報は、次いで、エラー位置及びエラー値を計算するための既知の型式のエラーパターン計算ユニット３２に入力され、コードワードｃの係数c₀, c₁, …, c₁₁を得る。特定の実現例では、上記エラーパターン計算ユニット３２は、キー式を解くユニットと、チェン検索（Chien search）及びフォーニーアルゴリズム（Forney algorithm）を実施するユニットとを有することができる。前述した様に、0 ≦ k ≦ 4に対してはS’_k = S_k= n(α^k)となり、5 ≦ k ≦ k_maxに対してはS’_k = S_k - m_k = (n(α^k) + m_k ) -m_k = n(α^k)となる。従って、0 ≦ k ≦ k_maxに対してはS’_k = n(α^k)となり、これは実効的に最小ハミング距離k_max+2のコードが使用されることを意味する。
【００６４】
最後に、得られたコードワード係数c₀, c₁, …, c₁₁は、抽出ユニット３３において全ての情報シンボルm₅, m₆, …, m₁₁を抽出するために使用され、ここで、これら情報シンボルは、
【数４３】

により示される。上記抽出ユニット３３の詳細な実施例は図８に示されている。
【００６５】
先に示したように、所望のコードのハミング距離は情報シンボルm₅,m₆,…, m_{k max}が分かる場合はk_max + 2に増加し、かくして、一層信頼性のおけるアドレス認識を可能にする。ハミング距離の増加は余分な冗長性を犠牲にすることはなく、該コードのデコーダは幾つかの余分なシンドロームを計算することができるような通常のデコーダとすることができる。このように、幾つかの情報シンボルの知識は、これら情報シンボルに対応するシンドロームを更新し、続いて使用することを可能にする。
【００６６】
もっと一般的な言葉では、シンドロームＳ_ｊは、
【数４４】

により計算され、情報シンボルm_n-k, m_n-k+1, .., m_n-k+s-1が演繹的に分かる場合は、前記追加のシンドローム（Ｓ’）は、
【数４５】

により計算される。そして、情報シンボルは、
m_j = c(α^j+b) for n-k ≦ j ≦ n-2 and m_n-1 = c_n-1
又は
m_j = c(α^j+b) for n-k ≦ j ≦ n-1
により得ることができる。ここで、周波数ドメイン符号化に対応する３ｘ５生成行列に関する例を示す。ｉ＝１、２、３に対して、該生成行列のｉ番目の行は、ｉ≠ｊならば、f_i(1) = f_i(α) = 0、f_i(α^i-1) = 1となり、また1 ≦ j ≦ 3に対してはf_i(α^j+1) = 0となるようにして、最大で４次の多項式ｆ_i(x)に対応する。ここで、αはα³ = 1 + αを満足するようなＧＦ(8)の元である。下記の多項式が、これらの要件を満足する：
f₁(x) = α⁶ + α⁶x + α³x² + α²x³ + α⁵x⁴
f₂(x) = α² + α²x² + α²x³ + α²x⁴
f₃(x) = α⁶ + α⁵x + α⁵x² + α²x³ + x⁴
この結果、
【数４６】

が得られる。
【００６７】
次に、コード間引きに基づく本発明の更に他の実施例を図９及び図１０を参照して説明する。図９は情報ワードｍをコードワードｃに符号化する方法を示し、図１０は多分損なわれているコードワードｒを情報ワードｍに復号する方法を示している。
【００６８】
図９に示すように、ｋ個の情報シンボルを有する情報ワードｍは、符号化装置４０の符号化ユニット４１により中間生成行列Ｇ”を用いて符号化される。該中間生成行列Ｇ”は、選択ユニット４２により選択された生成行列Ｇから派生する。中間生成行列Ｇ”は、該行列が生成行列Ｇより少なくとも１つ多い列を有するという点で生成行列Ｇよりは大きい。通常、生成行列Ｇはｋ個の行とｎ個の列とを有するが、中間生成行列Ｇ”はｋ個の行とｎ＋ｋ個の列とを有すると共に相互に異なる位置に単一の非零エントリを備えるようなｋ個の列を有する。情報ワードｍを符号化するために上記中間生成行列Ｇ”を使用する場合、ｋ＋ｎ個のシンボルを持つ中間コードワードｔが得られる。上記中間コードワードｔからは、該中間コードワードｔから或る数のシンボルを削除することによってコードワード発生ユニット４４からコードワードｃが得られる。この場合において、削除すべきシンボルの上記数は、上記中間生成行列Ｇ”及び生成行列Ｇの列の数の間の差に相当する。このように、得られるコードワードｃはｎ個のシンボルを有する。
【００６９】
復号の間において、図１０に示す用の、ｎ個のシンボルを持つ多分損なわれているコードワードｒがデコーダにより受信される。最初のステップにおいて、受信されたワードｒは、拡張ユニット５０により第１擬似個ワードｒ’へと拡張される。該ユニットにおいては、前記エンコーダにおいて既に使用された前記中間生成行列Ｇ”が使用されて、上記擬似個ワードｒ’の長さを決定する。即ち、該擬似コードワードｒ’のシンボル数は上記中間生成行列Ｇ”の列の数に対応する、即ち、受信されたワードｒのｎ個のシンボルに対してｋ個のイレージャが加えられて擬似コードワードｒ’を得る。
【００７０】
その後、置換ユニット５１において、演繹的に分かっている情報シンボル（例えば、ｍ_１、ｍ_５、ｍ_６）が、上記擬似コードワードｒ’において、上記演繹的に分かっている情報シンボルの位置に対応するような上記イレージャの位置で置換される。このことは、イレージャ１、５及び６が、演繹的に分かっている情報シンボルｍ_１、ｍ_５、ｍ_６により置換されることを意味する。得られた第２擬似コードワードｒ”は、その後、デコーダユニット５２に入力されるが、該ユニットは、好ましくは、前記中間生成行列Ｇ”を用いて上記第２擬似コードワードｒ”をｋ個のシンボルを持つ情報ワードｍに復号するような既知のエラー及び消去デコーダとする。
【００７１】
本発明の該実施例によれば、本発明の他の実施例と較べて一層大きな中間生成行列Ｇ”が使用される。しかしながら、この実施例の利点は、前記情報シンボルが連続した順番で演繹的に分かる必要はなく、情報ワード内での情報シンボルの位置に無関係に演繹的に分かる追加の情報シンボルが、一般的に、情報シンボルが演繹的に分からない場合に使用されるコードと比較して向上された最小ハミング距離に繋がる点にある。
【００７２】
ここで、コード間引きに基づく上記実施例を別の形で説明する。以下のように定義されたガロア体ＧＦ(8)上の［８，３，６］の拡張されたリードソロモンコードＣを考察する。ベクトルｃ＝(c_-1, c₀, c₁…, c₆)は、
【数４７】

の場合、且つ、この場合にのみＣ内に存在する。ここで、αはα³ = 1 + αを満足するようなＧＦ(8)の元である。以下の中間生成行列Ｇ”が上記コードＣを発生することが分かる。
【数４８】

該中間生成行列Ｇ”の最右端側の５列は生成行列Ｇとして使用される。即ち、生成行列Ｇは、
【数４９】

となる。該生成行列Ｇにより発生されるコードは最小ハミング距離３を持つ。如何なるｊ個の情報シンボルの知識も、最小ハミング距離を３から３＋ｊに効果的に増加させる。
【図面の簡単な説明】
【図１】 図１は、コードワードの従来のフォーマットを示す。
【図２】 図２は、符号化及び復号する構成のブロック図を示す。
【図３】 図３は、本発明による情報ワードを符号化する装置を示す。
【図４】 図４は、本発明による復号する装置を示す。
【図５】 図５は、本発明による符号化する装置の他の実施例を示す。
【図６】 図６は、本発明による符号化する装置の更に他の実施例を示す。
【図７】 図７は、本発明による復号する装置の一実施例を示す。
【図８】 図８は、図７に示す復号する装置において使用されるコードワードから情報シンボルを抽出する手段を示す。
【図９】 図９は、本発明による符号化する装置の更に他の実施例を示す。
【図１０】 図１０は、本発明による復号するための対応する装置を示す。

Claims (27)

1. 情報シンボルを有する情報ワードをコードのコードワードに符号化するために生成行列を選択して、受信された多分損なわれているコードワードを復号するデコーダにより少なくとも１つの情報シンボルが演繹的に分かる場合に向上されたエラー訂正能力を提供するような方法において、前記生成行列は、前記コードの少なくとも１つのサブコードの最小ハミング距離が前記コードの最小ハミング距離よりも大きく、且つ、前記サブコードのサブコード生成行列が前記生成行列から前記少なくとも１つの演繹的に分かる情報シンボルに対応する少なくとも１つの行を削除することによって前記コードの前記生成行列から生じるように選択されることを特徴とする方法。
2. 請求項１に記載の方法において、前記生成行列は、ハミング距離が各々増加するような少なくとも２つのサブコードが存在し、これらサブコードが前記コードにおいて入れ子にされ、且つ、前記各サブコードが対応するサブコード生成行列により発生されるように選択され、前記各サブコード行列は異なる数の行を有し、これら全ての行が前記生成行列の一部であることを特徴とする方法。
3. 請求項２に記載の方法において、前記サブコード生成行列は各々増加する数の行を含み、該数は前記各サブコード生成行列に対して１づつ増加し、（ｉ−１）番目のサブコード生成行列は１つの行を削除することによりｉ番目のサブコード生成行列から生じることを特徴とする方法。
4. 請求項３に記載の方法において、前記生成行列は、全ての整数ｉに対して（ｉは１以上で最大でもｋ−１の整数であり、ｋは前記生成行列の行の数とする）ｉなる数の行が、前記生成行列のｉ＋１なる数の行により形成されるサブコード生成行列から得られるサブコードよりも大きなハミング距離を持つサブコードを得るためのサブコード生成行列を形成するように選択されることを特徴とする方法。
5. 請求項１に記載の方法において、前記生成行列はより大きな中間生成行列から派生し、該中間生成行列は、前記生成行列よりも少なくとも１列多い列を有すると共に、単一の非零エントリを持つ前記少なくとも１列を削除することにより増加された最小ハミング距離を有するようなコードを発生することを特徴とする方法。
6. 請求項５に記載の方法において、前記生成行列はｋ個の行とｎ個の列とを有し、ｋ個の行とｎ＋ｋ個の列とを備える前記中間生成行列は各々が相互に異なる位置に単一の非零エントリを持つようなｋ個の列を有し、前記生成行列は前記中間生成行列から前記ｋ個の列を削除することにより生じることを特徴とする方法。
7. 情報シンボルを有する情報ワードをコードのコードワードに符号化して、受信された多分損なわれているコードワードを復号するデコーダにより少なくとも１つの情報シンボルが演繹的に分かる場合に向上されたエラー訂正能力を提供するような方法において、請求項１に記載の方法により選択された生成行列が、前記情報ワードを前記コードワードに符号化するために使用されることを特徴とする方法。
8. 請求項７に記載の方法において、
   ａ）第１コードワードパラメータ（ｃ¹(x)）を第１の前記情報シンボル（ｍ_１）により初期化するステップと、
   ｂ）その後、後続のコードワードパラメータ（ｃ^j(x)）（但しｊ＝２〜ｋ）を、
   

   

   により計算するステップと、
   ｃ）最後に、コードワード多項式（ｃ(x)）を、
   

   

   により計算するステップと、
   を有し、ここで、αは前記コードが基づくガロア体の原始元であり、ｇ _k (x) は前記コードのための生成多項式であり、前記コードワード多項式（ｃ(x)）の係数（ｃ_ｉ）が前記コードの前記コードワードを形成することを特徴とする方法。
9. 請求項７に記載の方法において、ｋ個の情報シンボル(m_n-k, m_n-k+1,…, m_n-1)を有する情報ワード（ｍ）がＧＦ(q)上の［ｎ，ｋ，ｎ−ｋ＋１］のリードソロモンコードのコードワード（ｃ）に符号化され、該符号化するステップが、
   ａ）親生成多項式(g^(p)(x))を、
   

   

   と定義するステップであって、ここで、αが最大でｎ次のＧＦ(q)の非零元であり、ｂが整数であるようなステップと、
   ｂ）ｎ−ｋ≦ｉ≦ｎ−１に対して、
   

   

   なる成分生成多項式(g⁽ⁱ⁾)を定義するステップであって、ここで、
   

   

   及び
   

   

   であるようなステップと、
   ｃ）コードワード多項式（ｃ(x)）を、
   

   

   により計算するステップと、
   を有し、前記コードワード多項式（ｃ(x)）が前記コードにおける前記コードワード（ｃ）を形成することを特徴とする方法。
10. 請求項７に記載の方法において、ｋ個の情報シンボル(m_n-k, m_n-k+1,…, m_n-1)を有する情報ワード（ｍ）がＧＦ(q)上の［ｎ，ｋ，ｎ−ｋ＋１］リードソロモンコードのコードワード（ｃ）に符号化され、該符号化するステップが、
    ａ）親生成多項式(g^(t)(x))を、
    

    

    と定義するステップであって、ここで、αが最大でｎ次のＧＦ(q)の非零元であり、ｂが整数であるようなステップと、
    ｂ）ｎ−ｋ≦ｉ≦ｎ−２に対して、
    

    

    なる成分生成多項式(g⁽ⁱ⁾)を定義するステップであって、ここで、
    

    

    及び
    

    

    であるようなステップと、
    ｃ）コードワード多項式（ｃ(x)）を、
    

    

    により計算するステップと、
    を有し、前記コードワード多項式（ｃ(x)）が前記コードにおける前記コードワード（ｃ）を形成することを特徴とする方法。
11. 請求項７に記載の方法であって、請求項５に記載の方法により選択され且つ中間生成行列から派生する生成行列が前記情報ワードを前記コードワードに符号化するために使用されるような方法において、
    ａ）前記情報ワードを前記中間生成行列を用いて符号化することにより中間コードワードを発生するステップと、
    ｂ）前記中間コードワードから少なくとも１つのシンボルを削除することにより前記コードワードを発生するステップと、
    を有し、前記削除するシンボルの数が前記中間生成行列と前記生成行列との列の数の間の差に対応することを特徴とする方法。
12. コードの多分損なわれているコードワードを、情報シンボルを有する情報ワードに復号する方法であって、前記情報ワードは前記コードのコードワードに生成行列を用いて符号化され、復号前に少なくとも１つの情報シンボルが演繹的に分かる場合には前記コードが向上されたエラー訂正能力を備えるような方法において、前記情報ワードは請求項１に記載の方法により選択された生成行列を用いて前記コードワードに符号化され、前記多分損なわれているコードワードを向上されたエラー訂正能力で復号するために、該多分損なわれているコードワードに含まれる前記少なくとも１つの演繹的に分かる情報シンボルの寄与が考慮されることを特徴とする方法。
13. 請求項１２に記載の方法において、
    ａ）前記演繹的に分かる情報シンボルを前記コードの前記生成行列における対応する行を用いて符号化するステップと、
    ｂ）前記符号化するステップの結果を加算して、中間ワードを表すステップと、
    ｃ）前記中間ワードを、復号されるべき前記多分損なわれているコードワードから減算するステップと、
    ｄ）前記減算の結果を既知の方法により復号して、前記生成行列における前記演繹的に分かる情報シンボルに対応しない行により発生されるコードを復号するステップと、
    ｅ）前記情報ワードを復元するステップと、
    を有していることを特徴とする方法。
14. 請求項１２に記載の方法において、
    ａ）受信された多分損なわれているコードワードからシンドロームを形成するステップと、
    ｂ）前記演繹的に分かる情報シンボルと前記多分損なわれているコードワードとを用いて追加のシンドロームを形成するステップと、
    ｃ）前記情報ワードを、前記シンドロームと前記追加のシンドロームとを用いて計算するステップと、
    を有することを特徴とする方法。
15. 請求項１４に記載の方法において、前記情報ワードが、
    ｃ１）前記シンドローム及び前記追加のシンドロームを用いてエラー位置及びエラー値を計算し、前記コードワードを得るステップと、
    ｃ２）前記得られたコードワードから前記情報ワードを抽出するステップと、
    により計算されることを特徴とする方法。
16. 請求項１５に記載の方法において、前記情報ワードは請求項９に記載の方法により前記コードワードに符号化され、前記シンドロームは、
    

    

    として計算され、前記追加のシンドロームは、
    

    

    として計算され、ここで、ｒ _ｉ は前記多分損なわれているコードワードのシンボルであり、m_n-k,m_n-k+1,…,m_n-k+s-1は前記演繹的に分かる情報シンボルであり、前記情報ワードは前記得られたコードワードからm_j = c(α^j+b) （但しn-k ≦ j ≦ n-1）により抽出されることを特徴とする方法。
17. 請求項１５に記載の方法において、前記情報ワードは請求項１０に記載の方法により前記コードワードに符号化され、前記シンドロームは、
    

    

    として計算され、前記追加のシンドロームは、
    

    

    として計算され、ここで、ｒ _ｉ は前記多分損なわれているコードワードのシンボルであり、m_n-k,m_n-k+1,…,m_n-k+s-1は前記演繹的に分かる情報シンボルであり、前記情報ワードは前記得られたコードワードからm_j = c(α^j+b) （但しn-k ≦ j ≦ n-2及びm_n-1 = c_n-1）により抽出されることを特徴とする方法。
18. 請求項１２に記載の方法であって、請求項５に記載の方法により選択され且つ中間生成行列から派生する生成行列が、請求項１１に記載の方法により前記情報ワードを前記コードワードに符号化するために使用されるような方法において、
    ａ）前記生成行列を得るために前記中間生成行列において削除された前記列に対応する位置にイレージャを追加することにより、前記多分損なわれているコードワードを擬似コードワードに拡張するステップと、
    ｂ）前記イレージャを前記演繹的に分かる情報シンボルの位置において該演繹的に分かる情報シンボルにより置換して、第２擬似コードワードを得るステップと、
    ｃ）前記第２擬似コードワードを、前記中間生成行列により発生されるコードの既知のエラー及び消去復号方法により復号するステップと、
    を有していることを特徴とする方法。
19. 請求項１、７及び１２の何れか一項に記載の方法において、前記情報ワードはデータ項目を有し、その場合において、連続する情報ワードは所定の対応するデータ項目要素を、第１データ項目を有する第１情報ワードの知識が後続の情報ワードに含まれる１以上の連続したデータ項目におけるデータ項目要素の知識に繋がるように有していることを特徴とする方法。
20. 請求項１９に記載の方法において、前記情報ワードはアドレス情報、特に直列データストリームにおける位置及び／又はデータ担体上の位置のアドレス情報を有していることを特徴とする方法。
21. 請求項２０に記載の方法において、該方法が、アドレス情報をウォブル信号においてデータ担体上に記憶されるべきウォブルコードに符号化するためにデジタルビデオ記録に適用されることを特徴とする方法。
22. 請求項２０に記載の方法において、前記アドレス情報の前記情報ワードが複数ビット情報シンボルを有していることを特徴とする方法。
23. 情報シンボルを有する情報ワードをコードのコードワードに符号化して、受信された多分損なわれているコードワードを復号するデコーダにより少なくとも１つの情報シンボルが演繹的に分かる場合に向上されたエラー訂正能力を提供するような装置において、前記情報ワードを請求項１に記載の方法により選択された生成行列を用いて前記コードワードに符号化する手段を有していることを特徴とする装置。
24. コードの多分損なわれているコードワードを、情報シンボルを有する情報ワードに復号する装置であって、前記情報ワードは前記コードのコードワードに請求項１に記載の方法により選択された生成行列を用いて符号化され、復号前に少なくとも１つの情報シンボルが演繹的に分かる場合には前記コードが向上されたエラー訂正能力を備えるような装置において、前記多分損なわれているコードワードを向上されたエラー訂正能力で復号するために、該多分損なわれているコードワードに含まれる前記少なくとも１つの演繹的に分かる情報シンボルの寄与を考慮する手段を有していることを特徴とする装置。
25. 請求項１、７及び１２の少なくとも何れか一項に記載の方法を実施するコンピュータプログラム。
26. ユーザデータを記録するためのデータ担体であって、請求項７に記載の方法により符号化されたシステムデータ項目を記録していることを特徴とするデータ担体。
27. 請求項２６に記載のデータ担体において、前記システムデータ項目が当該データ担体上の位置を見付けるために使用されるアドレスデータ及び／又はタイミングデータを有していることを特徴とするデータ担体。

Images