(57)【要約】消失支援ブロックコードデコーダ、およびこれに関連する方法を提供する。消失支援ブロックコードデコーダは、第１ブロックデコーダ、消失プロセッサ、および第２ブロックコードデコーダを有する。第１ブロックデコーダ、例えばリード・ソロモンデコーダは、バーストエラーによって予め影響を受けたデータ要素のブロック、例えばバイトをデコード（復号化）するよう構成する。この第１ブロックデコーダは、さらに、デコードすることができないブロックを識別するよう構成する。消失プロセッサは、消失識別プロセスにおいて、第１ブロックデコーダによって訂正された復号化ブロックにおけるデータ要素を使用することによって、復号化不能ブロックにおけるデータ要素を消失箇所として識別するよう構成する。第２ブロックデコーダ、例えば同一のリード・ソロモンデコーダまたは別のリード・ソロモンデコーダは、復号化処理において、消失プロセッサが識別した消失箇所を使用することによって、復号化不能ブロックの一つまたはそれ以上を復号化するよう構成する。
2009533796.tif 000002
【特許請求の範囲】
【請求項１】
消失支援ブロックコードデコーダにおいて、
データ要素のブロックを復号化するため、またこれらブロックのうち復号化できない復号化不能ブロックを識別する第１ブロックデコーダと、
復号化不能ブロック内におけるエラーの可能性があるデータ要素を消失箇所であると識別し、この識別は、前記第１ブロックデコーダによる復号化で訂正された復号化ブロックのデータを使用することにより行う、消失プロセッサと、および
この消失プロセッサによって識別された１個またはそれ以上の消失箇所を、復号化処理で使用して、データにおける１個またはそれ以上復号化不能ブロックを復号化する第２ブロックデコーダと、
を備えた消失支援ブロックコードデコーダ。
【請求項２】
請求項１に記載の消失支援デコーダにおいて、さらに、前記第１ブロックデコーダと前記消失プロセッサとの間に介在させたインタリーバを備えたことを特徴とする消失支援ブロックコードデコーダ。
【請求項３】
請求項２に記載の消失支援デコーダにおいて、さらに、前記消失プロセッサと前記第２ブロックデコーダとの間に介在させたデインタリーバを備えたことを特徴とする消失支援ブロックコードデコーダ。
【請求項４】
請求項１に記載の消失支援デコーダにおいて、前記第１および第２のブロックデコーダは、異なる時点で使用される物理的に同一のデコーダとしたことを特徴とする消失支援ブロックコードデコーダ。
【請求項５】
請求項１に記載の消失支援デコーダにおいて、前記第１および第２のブロックデコーダは、物理的に個別のデコーダとしたことを特徴とする消失支援ブロックコードデコーダ。
【請求項６】
請求項１に記載の消失支援デコーダにおいて、前記第１ブロックデコーダをリード・ソロモンデコーダとしたことを特徴とする消失支援ブロックコードデコーダ。
【請求項７】
請求項１に記載の消失支援デコーダにおいて、前記第２ブロックデコーダをリード・ソロモンデコーダとしたことを特徴とする消失支援ブロックコードデコーダ。
【請求項８】
消失支援ブロックコードの復号化方法において、
データ要素のブロックを復号化する第１復号化ステップと、
データ要素ブロックのうち復号化できない復号化不能ブロックを識別するステップと、
少なくとも１つの決定ルールを用いて復号化不能ブロック内のデータ要素を消失箇所として識別するステップと、および
識別した消失箇所を使用することによりデータにおける１個またはそれ以上の復号化不能ブロックを復号化する第２復号化ステップと、
を有することを特徴とする方法。
【請求項９】
請求項８に記載の方法において、さらに、消失箇所を識別するステップの前に復号化したブロックをインタリーブするステップを有することを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、さらに、消失箇所を識別するステップの後、かつ前記第２復号化ステップの前に、復号化したブロックをデインタリーブするステップを有することを特徴とする方法。
【請求項１１】
請求項８に記載の方法において、前記決定ルールは、訂正したデータ要素に隣接する復号化不能ブロック内のデータ要素を消失箇所として識別することを要求とするものとした、ことを特徴とする方法。
【請求項１２】
請求項８に記載の方法において、前記決定ルールは、訂正したデータ要素と正しいまたは訂正したデータ要素とに挟まれた復号化不能ブロック内のデータ要素を消失箇所として識別することを要求するものとした、ことを特徴とする方法。
【請求項１３】
請求項８に記載の方法において、前記決定ルールは、復号化不能なデータ要素をグループ分けしたうちの、訂正したデータ要素に隣接するグループを消失箇所として識別することを要求するものとした、ことを特徴とする方法。
【請求項１４】
消失支援ブロックコード復号化システムにおいて、
データ要素のブロックを復号化するため、またデータ要素における復号化できない復号化不能ブロックを識別する第１ブロック復号化手段と、
この第１ブロック復号化手段による復号化で訂正された復号化ブロック内のデータを使用することにより復号化不能なブロック内のデータ要素を消失箇所として識別する消失識別手段と、
この消失識別手段で識別された１個またはそれ以上の消失箇所を復号化に使用することにより、データにおける１個またはそれ以上の復号化不能ブロックを復号化する第２ブロック復号化手段と、
を備えたことを特徴とする消失支援ブロックコード復号化システム。
【請求項１５】
請求項１４に記載のシステムにおいて、前記第１および第２のブロック復号化手段は、異なる時点で使用される物理的に同一の復号化手段としたことを特徴とするシステム。
【請求項１６】
請求項１４に記載のシステムにおいて、前記第１および第２のブロック符号化手段は、物理的に個別の復号化手段としたことを特徴とするシステム。
【請求項１７】
連鎖コードデコーダにおいて、
符号化したビットを復号化する内部デコーダであって、バースト性エラーを招く傾向がある該内部デコーダと、
この内部デコーダから出力された復号化ビットを、デインタリーブしてデータブロックを生成するデインタリーバと、および
このデインタリーバにより出力されたデータのブロックを復号化する消失支援ブロックコードデコーダと、
を備え、この消失支援ブロックコードデコーダは、
データ要素のブロックを復号化し、またこれらブロックのうち復号化できない復号化不能ブロックを識別する第１ブロックデコーダと、
この第１ブロックデコーダにより出力されたブロックをインタリーブし、データ要素を復号化不能ブロック内に分散させるインタリーバと、
復号化不能ブロック内におけるエラーの可能性があるデータ要素を消失箇所であると識別し、この識別は、前記第１ブロックデコーダによる復号化で訂正された復号化ブロックのデータを使用することにより行う、消失プロセッサと、
この消失プロセッサにより出力されたデータのブロックをデインタリーブするデインタリーバと、および
前記消失プロセッサで識別された１個またはそれ以上の消失箇所を、復号化に使用することにより、データにおける１個またはそれ以上の復号化不能ブロックを復号化する第２ブロックデコーダと
を有するものとした、ことを特徴とする連鎖コードデコーダ。
【請求項１８】
請求項１７に記載の連鎖コードデコーダにおいて、前記第１および第２のブロックデコーダは、異なる時点で使用される物理的に同一のデコーダとしたことを特徴とする連鎖コードデコーダ。
【請求項１９】
請求項１７に記載の連鎖コードデコーダにおいて、前記第１および第２のブロックデコーダは、物理的に個別のデコーダとしたことを特徴とする連鎖コードデコーダ。
【請求項２０】
連鎖コードデコーダにおいて、
畳み込み符号化したビットを復号化するビタビデコーダであって、バースト性エラーを招く傾向がある該ビタビデコーダと、
このビタビデコーダから出力された復号化ビットを、デインタリーブしてデータブロックを生成するデインタリーバと、および
このデインタリーバにより出力されたデータのブロックを復号化する消失支援ブロックコードデコーダと、
を備え、この消失支援ブロックコードデコーダは、
データ要素のブロックを復号化し、またこれらブロックのうち復号化できない復号化不能ブロックを識別するリード・ソロモンブロックデコーダである第１ブロックデコーダと、
この第１ブロックデコーダにより出力された復号化ブロックをインタリーブし、データ要素を任意の復号化不能ブロック内に分散させるインタリーバと、
復号化不能ブロック内におけるデータ要素を消失箇所であると識別し、この識別は、前記第１ブロックデコーダによる復号化で訂正された復号化ブロックのデータを使用することにより行う、消失プロセッサと、
この消失プロセッサにより出力されたデータのブロックをデインタリーブするデインタリーバと、および
前記消失プロセッサで識別された１個またはそれ以上の消失箇所を、復号化に使用することにより、データにおける１個またはそれ以上の復号化不能ブロックを復号化する、リード・ソロモンブロックデコーダである第２ブロックデコーダと
を有するものとした、ことを特徴とする連鎖コードデコーダ。
【請求項２１】
請求項２０に記載の連鎖コードデコーダにおいて、前記第１および第２のブロックデコーダは、異なる時点で使用される物理的に同一のデコーダとしたことを特徴とする連鎖コードデコーダ。
【請求項２２】
請求項２０に記載の連鎖コードデコーダにおいて、前記第１および第２のブロックデコーダは、物理的に個別のデコーダとしたことを特徴とする連鎖コードデコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、ブロックコードデコーダに関し、より特別には、このようなデコーダにおける訂正可能なエラーの数を増加させることに関する。
【背景技術】
【０００２】
前方（一方向）エラー訂正コードは、トランスミッタにおけるソース情報を符号化するのに適用するコードであり、このエラー訂正コードにより、通信チャネル上での伝送によって生じるエラーをレシーバ側で行う対応する復号化によって訂正できる。コードのエラー検出および訂正の能力を高めるために、コードの組み合わせを適用することが一般的であり、このプロセスはしばしばコード連鎖と称される。コード連鎖の一例としては、外部コードをまずソース情報の符号化に適用し、次に内部コードを適用してさらに情報を符号化する。内部および外部コードは、互いに異なるエラーまたは補完のクラスに対処するよう、選択することができる。
【０００３】
図１は、外部コードおよび内部コードよりなる連鎖コードを適用するＦＥＣエンコーダ１００の例を示す。この例において、外部コードはブロックコードであり、内部コードは畳み込みコードである。エンコーダ１００は、代表的には、通信チャネル上で情報をレシーバに通信するよう構成したトランスミッタの一部をなす。エンコーダ１００は、ブロックコードエンコーダ１０２、インタリーバ１０４、および畳み込みコードエンコーダ１０６を有する。ブロックコードエンコーダ１０２への入力は、データブロックにより構成する。エンコーダ１０２は、パリティ情報を各ブロックに付加し、このパリティ情報をレシーバにおいて使用して、エラー検出および訂正を行う。インタリーバ１０４は、通信チャネルにおいて生じる（予想される）バースト性エラーの影響を減らすために、符号化したブロックを並べ替えるよう構成する。ある構成において、インタリーバ１０４は、エンコーダ１０２から送れられた符号化したブロックをバイトレベルでインタリーブするよう構成した畳み込みインタリーバとする。畳み込みエンコーダ１０６は、インタリーバ１０４から出力された、並べ替えブロックを畳み込み符号化するよう構成する。一般的に、この符号化は、ビットレベルで実行し、エラー検出および訂正に使用される所定量の冗長性を生じさせる。例えば、エンコーダ１０６は、１／２のレートの畳み込みエンコーダとすることができ、各入力に対して２個の畳み込み符号化したビットで置換し、それゆえ符号化したブロックのサイズを２倍にするが、パンクチャリングにより導入される冗長性の程度を減らすことができる。
【０００４】
図２は、エンコーダ１００により生成された符号化データを通信チャネル上で伝送した後に復号化するデコーダ２００を示す。デコーダ２００は一般的にレシーバの一部をなす。デコーダ２００は、内部デコーダ２０２、デインタリーバ２０６、およびブロックコードデコーダ２０８を有する。内部デコーダ２０２は、代表的には、ビタビデコーダであり、図１の（内部）畳み込みエンコーダ１０６により適用した畳み込み符号化を復号化するよう構成する。内部デコーダ２０２の出力２０４を、デインタリーバ２０６に入力し、このデインタリーバ２０６は、インタリーバ１０４によって導入した並べ替えを元に戻すよう構成する。このプロセスによって、デインタリーバ２０６は、通信チャネル上の通信により生じたいかなるバースト性エラーをも拡散させる。デインタリーバ２０６からのデータを、ブロックコードデコーダ２０８に入力する。このブロックコードデコーダは、図１のブロックコードエンコーダ１０２によって適用したブロックコード符号化を復号化するよう構成する。したがって、このブロックコードエンコーダ１０２がリード・ソロモンエンコーダである場合、ブロックコードデコーダ２０８も同様にリード・ソロモンデコーダを選択する。
【０００５】
デコーダ２００のエラー検出および訂正の能力は、代表的には、ブロックコードエンコーダ１０２によって付加されたパリティ情報の量によって規定される。エンコーダ１０２がＧＦ（２５６）の（ｎ，ｋ）リード・ソロモンエンコーダである場合、エンコーダはｎ−ｋバイトのパリティ情報を各ｋバイトのブロックに付加しており、ブロックコードデコーダ２０８は、（ｎ，ｋ）リード・ソロモンデコーダであり、デコーダ２００は、次式で示すエラーを検出および訂正することができる。
2009533796.tif 000003
ただし、次の記号は「フロア（床）」演算子を表し、
2009533796.tif 000004
ｄｍｉｎ＝（ｎ−ｋ＋１）である。したがって、ｄｍｉｎ＝１７であるコードに対しては、デコーダは８つのエラーまで検出および訂正することができる。
【０００６】
デコーダ２００のエラー検出および訂正の能力を高めるために、様々なスキームが提案されてきたが、どれも完全に満足のいくものではない。ある手法では、内部デコーダ２０２をその出力２０４がハードビット推定ではなくソフトビット推定の形式になるよう構成し、また一般的にはハードビット推定のみ扱うよう構成したブロックコードデコーダ２０８は、ソフトビット推定を扱うことができるように構成することを必要とする。例えば、非特許文献１、非特許文献２参照されたい。
【非特許文献１】GLOBECOM’02-ＩＥＥＥグローバル電気通信学会議事録、２００２年第２巻、第１０２６〜１０３０頁における、Ｍ.Ｋ.チェン氏らによる論文「部分的応答チャネルにおけるソフト−デシジョンによるリード・ソロモン復号化（Soft-Decision Reed-Solomon Decoding on Partial Response Channels）」
【非特許文献２】ＩＥＥＥ情報理論トランザクション、２００６年８月、第５２巻第８号、第３７４６〜２７５６頁におけるＪ.ジャン氏らによる論文「パリティチェック・マトリクスを適用することによるリード・ソロモンコードに対するインタラクティブなソフト入力およびソフト出力復号化（Interactive Soft-Input Soft-Output Decoding of Reed-Solomon Codes By Adapting the Parity Check Matrix）」
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、この手法は、理論的にはデコーダ２００のエラー検出および訂正能力を向上させることができるが、実際に実装するのは難しい、または不可能であることが明らかになっている。
【課題を解決するための手段】
【０００８】
本発明は、消失支援ブロックコードデコーダおよびこれに関連する方法を提供する。デコーダは、第１ブロックデコーダ、消失プロセッサ、および第２ブロックデコーダを有する。第１ブロックデコーダ、例えばリード・ソロモンデコーダは、データ要素、例えばバイトのブロックを復号化するよう構成する。第１ブロックデコーダは、さらに、復号化できない復号化不能ブロックを識別するよう構成する。消失プロセッサは、消失識別プロセスにおいて第１ブロックデコーダによって訂正された復号化ブロックにおけるデータ要素を使用することにより、エラーの可能性がある復号化不能ブロック内のデータ要素を消失箇所と識別するよう構成する。第１ブロックデコーダと同一または異なるデコーダとすることができる第２ブロックデコーダは、復号化において消失プロセッサで識別した消失箇所を使用することにより、１個またはそれ以上の復号化不能ブロックを復号化するよう構成する。
【０００９】
本発明の他のシステム、方法、特徴および利点は、以下の図面および詳細な説明を検討することで当業者には明らかであろう。これらすべての付加的なシステム、方法、特徴および利点は、本発明の範囲内において本明細書に含まれるものであり、添付の特許請求の範囲によって保護されるものである。
【発明を実施するための最良の形態】
【００１０】
図３につき説明すると、本発明の実施形態は、データ要素の符号化（エンコード）したブロック、例えばバイトを復号化（デコード）したブロックに復号化（デコード）するよう構成した消失支援ブロックコードデコーダ３００を有する。これは集中的な（バースト性）エラーが到来するブロックに導入されていることを仮定しており、またデコーダ３００はこれらエラーの「集中（バースト）性」を利用して、消失、すなわち訂正したデータ要素と同じエラーバーストによって影響されているためにエラー（誤り）の可能性がある復号化不能ブロック内におけるデータ要素を消失箇所であると識別する。エラーは位置および値の双方を有しているため、消失箇所の識別は、復号化不能ブロック内におけるエラー（誤り）の可能性があるエラーの位置（特定データ要素）を識別し、この識別をデコーダ３０６が復号化プロセスで有利に使用する。
【００１１】
ある構成において、消失支援ブロックコードデコーダ３０６を、図２の連鎖コードデコーダ２０２におけるブロックコードデコーダ２０８と置換し、バースト性エラーは内部デコーダ２０２によって導入される。他の構成においては、消失支援ブロックコードデコーダ３０６を、スタンドアローン（単独）型のデコーダとし、バースト性エラーは他のメカニズムによって導入される。
【００１２】
図４は、（ｎ，ｋ）リード・ソロモンエンコーダ、すなわち（ｎ−ｋ）バイトのパリティ情報をｋバイトの各バイトのブロックに加えるように構成したエンコーダによって符号化（エンコード）したデータのブロックを復号化（デコード）するよう構成した実施形態の消失支援ブロックコードデコーダ４００を示す。この実施形態において、消失支援ブロックコードデコーダ４００は、第１（ｎ，ｋ）リード・ソロモンデコーダ４０２、畳み込みバイトインタリーバ４０４、消失プロセッサ４０６、デインタリーバ４０８、および第２（ｎ，ｋ）リード・ソロモンデコーダ４１０を有する。第１（ｎ，ｋ）リード・ソロモンデコーダ４０２は、（ｎ，ｋ）リード・ソロモンエンコーダによって符号化（エンコード）されたデータのブロックを復号化（デコード）した後、通信チャネルにより伝送するよう構成する。デコーダ４０２は、符号化（エンコード）されたブロックのうち、エラー数が次式で表される個数、すなわち、
2009533796.tif 000005
ただし、ｄｍｉｎ＝（ｎ−ｋ＋１）、以下であるようなブロックを復号化（デコード）し、エラー数がデコーダのエラー検出および訂正能力を超える、すなわち上記［数３］で表される個数を超えたために復号化不能なブロックを検出する。
【００１３】
各復号化可能なブロックに対して、デコーダ４０２は、デコーダが訂正した各バイトに、特別なコードでマーク付けするよう構成し、この特別なコードを、本明細書において「Ｃｏｒｒｅｃｔｅｄ」を短縮 した「Ｃｅｄ」で表す。デコーダ４０２は、復号化（デコード）したブロック内における他の全てのバイトに対して、これらバイトが正しくデコーダによってすでに訂正した、また訂正しなかったことを示す、本明細書では「Ｃ」で表わすコードでマーク付けするよう構成する。デコーダ４０２は、さらに、復号化（デコード）不能ブロックの各バイトに対して、復号化失敗を示す、本明細書 では「Ｆ」で表わす特別なコードでマーク付けするよう構成する。復号化（デコード）可能なおよび復号化（デコード）不能なブロックは、構成バイトにおける対応マークと共に、デコーダ４０２から出力され、インタリーバ４０４に入力される。
【００１４】
インタリーバ４０４は、デコーダ４０２から出力されたブロック（復号化可能および復号化不能なブロックの双方）を並べ替え、そしてデコーダ４０２によって識別された復号化不能なブロック内のデータ要素をスプレッド（拡散）するよう構成する。このスプレッドを、図５につき説明する。図５は、デコーダ４０２によって出力されたデータ要素のブロックの例を示す。参照符号５００は、データ要素の復号化不能なブロックＹ１０、Ｏ１１およびＧ１２等を示し、これらはそれぞれ上述のように「Ｆ」でマーク付けする。参照符号５０２および５０４は、復号化に成功したデータ要素のブロックを示す。潜在的に同一バースト誤りによって影響されているデータ要素は、同一の接頭文字を有し、例えばＹの接頭文字は、関連するデータ要素における第１グループを示し、Ｏの接頭文字はデータ要素における第２グループを示し、Ｇの接頭文字は、データ要素における第３グループを示し、およびＢの接頭文字は、データ要素における第４のグループを示す。デインタリーバ２０６の作動により、これらのデータ要素は個別のブロックに仕分けされる。
【００１５】
インタリーバ４０４は、復号化不能なブロックからのデータ要素が異なるブロックに仕分けするように、このデータを図６に示すように再配置する。したがって、図６に示したように、図５におけるすべて同一の復号化不能なブロック５００からのデータ要素Ｙ１０，Ｏ１１，およびＧ１２は、インタリーバ４０４による並べ替えによって異なるブロックに移動する。
【００１６】
図７は、図６のデータ要素Ｏ１，Ｏ２，Ｏ３などの詳細な分解（ブレークダウン）状況を示し、ここでは各データ要素は１７バイトである。図示のように図７では、デコーダ４０２によって行ったマーク付けは、バイトレベルで発生することを仮定し、各バイトには、「Ｃ」，「Ｃｅｄ」、または「Ｆ」でマーク付けする。
【００１７】
ある実施形態において、インタリーバ４０４は、図８に示したタイプの畳み込みバイトインタリーバとする。図８に示した特別な実施例において、インタリーバ８００は、図示したようにｘ１，ｘ２，ｘ３等、異なる長さの複数個のＦＩＦＯシフトレジスタ８０６ａ，８０６ｂ，８０６ｃ，８０６ｄを有し、１７×１２バイトの入力ブロック８０２を受け取り、図示のような１９３×１２バイトの出力ブロック８０４を生成するように構成する。畳み込みバイトインタリーバは当業界で周知であり、本発明を理解する上で詳細に説明する必要はない。
【００１８】
消失プロセッサ４０６は、次にこのデータを処理し、消失箇所、すなわちこれらの復号化不能なブロックからの誤りのおそれがあるデータ要素を識別する。ある実施形態において、プロセッサ４０６は、これらデータ要素が同一のバースト誤りに影響されたおそれがあることを示す復号化されたブロックからの訂正されたデータ要素に隣接した復号化不能なブロックからのデータ要素を消失箇所として識別する。図７において、例えばデータ要素がバイトの場合、消失プロセッサ４０６は、バイト７０２，７０４，７０６および７０８を消失箇所として識別し、これはすなわち、これらバイトのそれぞれが復号化されたブロックからの訂正された少なくとも１つのバイトと縦方向に隣接するためである。
【００１９】
ある実施形態において、ブロック内のバイトは図７のように番号付する。（復号化不能なブロックに由来するバイトであることを示す）「Ｆ」とマーク付けした各バイトに対して、消失プロセッサ４０６は、先行バイト、現在バイト（「Ｆ」とマーク付けされたバイト）および後続バイトから「観測（オブザベーション）」をとるように構成する。「観測（オブザベーション）」を（Ｘｎ−１−Ｆ−Ｘｎ＋１） で示し、バイトを含む観測が以下の３つのパターン、すなわち（Ｃｅｄ−Ｆ−Ｃ）、（Ｃ−Ｆ−Ｃｅｄ）もしくは（Ｃｅｄ−Ｆ−Ｃｅｄ）のいずれかにマッチする場合、消失プロセッサ４０６はこの「Ｆ」とマーク付けされたバイトを消失箇所であると識別する。
【００２０】
一旦消失箇所を識別すると、データはデインタリーバ４０８に入力する。デインタリーバは、データをデインタリーブし、インタリーバ４０４によって行われた並べ替えを反転させる。この効果は、図９に示したように消失箇所が識別されていることを除いて、データを図５に示したような形式に戻すことである。
【００２１】
このとき、データを（ｎ，ｋ）リード・ソロモンデコーダ４１０に入力し、この（ｎ，ｋ）リード・ソロモンデコーダ４１０は、デコーダ４０２と物理的に同一または異なるデコーダとすることができる。識別した消失箇所を受け取ったデコーダ４１０は、図５のブロック５００のような復号化不能なブロックを復号化するのにデコーダ４０２よりも良好な状況にある。これは、エラーが位置および値を有しており、消失は位置が分かっており、あとは値を決定すればよいだけのエラーであり得るためである。したがって、（ｎ，ｋ）リード・ソロモンデコーダは、エラーと同様に消失の個数の２倍分を訂正することができる。言い換えると、｜Ｅ｜が消失の個数、｜Ｘ｜がブロック内のエラー個数とすると、以下の関係、すなわち｜Ｅ｜＋２｜Ｘ｜＜ｄｍｉｎが保持されなくてはならない。ただし、ｄｍｉｎ＝（ｎ＋ｋ−１）である。それゆえ、エラーにおけるいくつかを消失に変換することにより、消失識別プロセスの意図する結果において、元々復号化不能であったブロックが復号化可能になる。例えばｄｍｉｎ＝１７であるリード・ソロモンデコーダを考慮する。ブロック内のエラー数が９個であるために、このデコーダによって特定ブロックが復号化不能であると仮定する。これらエラーのうち１つが消失であると識別されたとすると、このブロックは復号化可能となる。これは｜Ｅ｜＋２｜Ｘ｜＝１７で、所望の通りｄｍｉｎ以下であるためである。
【００２２】
当然のことながら、図４に示した消失支援ブロックデコーダの実施形態において、インタリーバ４０４およびデインタリーバ４０８は、これら素子がなくても消失箇所の識別は可能であるために、随意である。とくに、図５につき説明すると、復号化不能なバイト（「Ｆ」とマーク付けされている）が、「Ｘ」がどのバイトともマッチするワイルドカードであるとして（Ｃｅｄ−Ｆ−Ｘ）または（Ｘ−Ｆ−Ｃｅｄ）にマッチする場合、これを消失箇所と識別する決定ルールを適用すると、Ｙ１０内のバイトは消失箇所であると識別する、または単にＹ９およびＹ１１に依存しないと識別することができる。同様に、Ｏ１１内のバイトは、消失箇所であると識別する、または単にＯ１０およびＯ１２の考察に依存しないと識別することができる。
【００２３】
さらに、当然のことながら、デコーダ４０２および４１０をリード・ソロモンデコーダ以外のブロックデコーダとする実施形態も可能である。
【００２４】
さらに当然のことながら、消失プロセッサ４０６は、メモリに格納されたソフトウェア命令にアクセスし実行するよう構成されたマイクロプロセッサもしくはマイクロコントローラ、または１つ以上の状態遷移ルールに適用された１つ以上の入力に応答して状態を変化させるように構成した有限状態機械などの、さまざまな形態で実施してもよい。それゆえ、このプロセッサは、ハードウェア、ソフトウェアまたはハードウェアとソフトウェアの組み合わせとして実施することができる。
【００２５】
消失プロセッサ４０６は、上述のルールとは異なる他の決定ルールを実装することができる。たとえば、ブロック内で識別された消失数がｄｍｉｎを超えている場合について考察する。この場合、第１の識別方法によると、（ｄｍｉｎ−１）個の消失をランダムに識別することができ、復号化が前と同じように試行する。所定回数の試行を行った後のみ、復号化失敗を宣言する。たとえば、ｄｍｉｎが１７であり、１６以上の消失が識別された場合、１６個のこのような消失がランダムに選択することができ、つぎに復号化を試行する。所定回数、例えば１回の試行が失敗となるとき、復号化の失敗を宣言する。
【００２６】
他の方法では、消失数がｄｍｉｎを超えていることを仮定し、｜Ｅ｜個の消失からＫ個を選択する。ここでＫ＜ｄｍｉｎであり、｜Ｅ｜！／（Ｋ！(｜Ｅ｜−Ｋ)！）のすべての組み合わせの復号化を試行する。この実施例においては、いずれの組み合わせにおいても復号化可能でない場合にのみ、復号化失敗が宣言される。
【００２７】
さらに、消失プロセッサ４０６は様々な可能である決定ルールに従うことができる。例えば、上述した決定ルールに付加的にまたは代替的に、プロセッサ４０６は、以下のパターン、すなわち（Ｃｅｄ−Ｆ−Ｆ−…−Ｆ−Ｘ）にマッチするすべての復号化不能なバイト（「Ｆ」とマーク付けされている）を消失箇所として識別する決定ルールに従うようにすることができる。
【００２８】
他の代替的実施形態においては、リード・ソロモンデコーダ４０２から復号化されたバイトを、３つのカテゴリ、Ｃｅｄ＿ｒｉｇｈｔ、Ｃｅｄ＿ｌｅｆｔ、Ｃｅｄ＿ｍｉｄに分類（グループ分け）する。Ｃｅｄ＿ｒｉｇｈｔバイトは最後２ビットのみ訂正したＣｅｄバイトである：（ｃ，ｃ，ｃ，ｃ，ｃ，ｃ，ｃｅｄ，ｃｅｄ）。Ｃｅｄ＿ｌｅｆｔバイトは、最初の２ビットのみ訂正したＣｅｄバイトである（ｃｅｄ，ｃｅｄ，ｃ，ｃ，ｃ，ｃ，ｃ，ｃ）。Ｃｅｄ＿ｍｉｄバイトは、Ｃｅｄ＿ｒｉｇｈｔでもＣｅｄ＿ｌｅｆｔでもないＣｅｄバイトである。この実施形態において、プロセッサ４０６は、復号化不能なバイト（「Ｆ」とマーク付けされている）が以下のパターン、すなわち（（ＣｅｄもしくはＣｅｄ＿ｒｉｇｈｔ）−Ｆ−Ｃ）、（Ｃ−Ｆ−（ＣｅｄもしくはＣｅｄ＿ｌｅｆｔ））、または（（ＣｅｄもしくはＣｅｄ＿ｒｉｇｈｔ）−Ｆ−（ＣｅｄもしくはＣｅｄ＿ｌｅｆｔ））のいずれかにマッチするときに消失箇所であると識別するような決定ルールに従う。
【００２９】
この決定ルールに付加的にもしくは代替的に、プロセッサ４０６は，以下のパターン、すなわち（（ＣｅｄもしくはＣｅｄ＿ｒｉｇｈｔ）−Ｆ−Ｆ−…−Ｆ−Ｘ）にマッチするすべての復号化不能なバイト（「Ｆ」とマーク付けされている）を消失箇所であると識別する決定ルールに従うようにすることもできる。
【００３０】
上述の決定ルールに付加的にまたは代替的に、プロセッサ４０６は，以下のパターン、すなわち（（ＣｅｄもしくはＣｅｄ＿ｒｉｇｈｔ）−Ｆ−Ｘ）、（Ｘ−Ｆ−（ＣｅｄもしくはＣｅｄ＿ｌｅｆｔ））のいずれかにマッチした復号化不能なバイト（「Ｆ」とマーク付けされている）を消失箇所であると識別する決定ルールに従うようにすることもできる。
【００３１】
図１０は、消失支援ブロックデコーダを動作させる方法における実施形態のフローチャート１０００である。この消失支援ブロックデコーダは、例えば図４に示した消失支援ブロックデコーダとすることができるが、これに限定するものではない。
【００３２】
ステップ１００２において、データ要素の到来ブロックを、リード・ソロモンデコーダ用いて復号化し、および復号化不能なブロックを識別する。
【００３３】
ステップ１００２に続くステップ１００４において、復号化不能なブロックの各バイトに、復号化失敗を示す「Ｆ」でマーク付けする。
【００３４】
ステップ１００４と同時に行うことのできるステップ１００６において、復号化したブロックの各バイトは、復号化する前から元々正しかったことを示す“Ｃ”または復号化中に訂正されたことを示す“Ｃｅｄ”でマーク付けする。
【００３５】
ステップ１００４およびステップ１００６に続くステップ１００８において、ステップ１００４およびステップ１００６でマーク付けされたブロックを統合し、ステップ１０１０において、結果として得られたデータをインタリーブし、これにより、復号化失敗としてマーク付けされたバイトを分離する。
【００３６】
ステップ１０１０に続いてステップ１０１２を行う。このステップ１０１２においては、上述した決定ルールのうち一つまたはそれ以上に基づいて、復号化失敗とマーク付けされたバイトのうち選択したものを消失箇所として識別する。
【００３７】
ステップ１０１２に続いてステップ１０１４を行う。このステップ１０１４においては、データのブロックをデインタリーブし、ステップ１０１０のインタリーブによって導入された並べ替えを元に戻す。
【００３８】
ステップ１０１４に続いてステップ１０１６を行う。このステップ１０１６においては、ステップ１０１４のデータを、ステップ１００２で使用したのと同一または異なるリード・ソロモンデコーダを用いて復号化する。このステップにおいて、識別された消失箇所を使用して、ステップ１００２において復号化不能であると見なされた、１個またはそれ以上のブロックを復号化する。
【００３９】
他の実施形態の方法も可能である。これはステップ１００２およびステップ１０１６を、同一または異なるブロックデコーダによって実施し、デコーダはリード・ソロモンブロックデコーダとは異なるブロックデコーダとし、データ要素は異なるバイトとし、およびインタリーブするステップ１０１０およびデインタリーブするステップ１０１４を用いないような実施形態も可能である。
【００４０】
本発明の様々な実施形態について記載したが、本発明の範囲において、当業者にとっては多くの実施形態および実装形態が可能であることは明らかであろう。したがって、本発明は、添付の特許請求の範囲およびその均等物を除いて、限定されるものではない。
【図面の簡単な説明】
【００４１】
【図１】外部コードおよび内部コードを有する連鎖コードを適用した前方（一方向）エラー訂正コードエンコーダであって、外部コードを例えばリード・ソロモンコードなどのブロックコードとし、内部コードを畳み込みコードとした前方（一方向）エラー訂正エンコーダの例を示すブロック図である。
【図２】図１のエンコーダにより生成される符号化データのデコーダを示すブロック図である。
【図３】消失支援ブロックコードデコーダの上位概念レベルの入出力ブロック図である。
【図４】第１リード・ソロモンブロックコードデコーダ、消失を識別するための消失プロセッサ、第２リード・ソロモンブロックコードデコーダ、第１リード・ソロモンブロックコードデコーダと消失プロセッサとの間に介在させたインタリーバ、消失プロセッサと第２リード・ソロモンデコーダとの間に介在させたデインタリーバにより特徴づけられる消失支援ブロックコードデコーダの実施形態のブロック図である。
【図５】図４に示す第１リード・ソロモンデコーダによる出力データのブロックの例を示す。
【図６】図４に示すインタリーバを通過した後の、図５のデータのブロックを示す。
【図７】図６のデータをより詳細に表示したものである。
【図８】図４に示すインタリーバの実施形態の構成及び動作を示す。
【図９】消失箇所を識別し、図４に示すデインタリーバを通過した後のデータを示す。
【図１０】消失支援ブロックコードデコーダを動作させる方法の実施形態を示すフローチャートである。
【図１】
2009533796.tif 000006
【図２】
2009533796.tif 000007
【図３】
2009533796.tif 000008
【図４】
2009533796.tif 000009
【図５】
2009533796.tif 000010
【図６】
2009533796.tif 000011
【図７】
2009533796.tif 000012
【図８】
2009533796.tif 000013
【図９】
2009533796.tif 000014
【図１０】
2009533796.tif 000015
【国際調査報告】
2009533796.tif 000016
2009533796.tif 000017
2009533796.tif 000018