(57)【特許請求の範囲】
【請求項１】
情報の連続流を表すデータパケットの系列を符号化する方法であって、各データパケットはそれに対応する前記情報流のセグメントを表すセットのペイロード情報を含み、各セットのペイロード情報は複数の対応する個別のペイロード情報部分に同様に分割され；この方法が：
複数の前記データパケットを符号化するステップを含み、前記データパケットの各々の符号化が、それらの前記複数の個々のペイロード情報部分の少なくとも一つを符号化することで、その中に含まれる前記セットのペイロード情報を符号化するステップを含み、この方法がさらに
前記データパケットの追加の一つを符号化するステップを含み、この追加のデータパケットが前記系列内において前記複数の各々のデータパケットの後に続き、このため前記複数のデータパケットは前記追加のデータパケットに先行し、前記追加のデータパケットの符号化がその中に含まれる前記セットのペイロード情報を符号化するステップを含み、前記符号化された追加のデータパケットがさらに前記複数の先行するデータパケット内に含まれる前記ペイロード情報に対する順方向誤り訂正能力を提供する追加のセットのペイロード情報を含み、
前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報が前記先行する２つあるいはそれ以上のデータパケット内に含まれる前記ペイロード情報の組合せに基づいており、前記追加のセットのペイロード情報が基づく前記先行する少なくとも２つのデータパケット内に含まれる前記ペイロード情報がそれらの異なる個別のペイロード情報部分からのペイロード情報を含むことを特徴とする方法。
【請求項２】
符号化されるべき各データパケット内に含まれる前記セットのペイロード情報がｍ個の対応する個別のペイロード情報部分に同様に分割され、ここでｍは１より大きな整数を表し、前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報がｍ個の前記複数のデータパケットのｍ個の異なる個別のペイロード情報部分の検査合計を含み、この検査合計が単一パリティ検査ブロック符号に基づき、結果としてレートｍ／（ｍ＋１）順方向誤り訂正符号が得られることを特徴とする請求項１記載の方法。
【請求項３】
前記ｍが２に等しく、前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報が前記複数のデータパケットの第一の一つの第一の個別のペイロード情報部分と前記複数のデータパケットの第二の一つの第二の個別のペイロード情報部分の検査合計を含み、結果としてレート２／３順方向誤り訂正符号が得られることを特徴とする請求項２記載の方法。
【請求項４】
符号化されるべき各データパケット内に含まれる前記セットのペイロード情報がｍ個の対応する個別のペイロード情報に同様に分割され、ｍは１より大きな整数を表し、前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報が最大距離分離可能ブロック符号に基づく検査合計を含むことを特徴とする請求項１記載の方法。
【請求項５】
前記追加の一つのデータパケット内に含まれる前記追加のセットのペイロード情報が前記先行する２つあるいはそれ以上のデータパケットとは別のデータパケットに基づく一つあるいはそれ以上の追加のセットのペイロード情報にてインタリーブされることを特徴とする請求項１記載の方法。
【請求項６】
データパケットの符号化された系列を、この系列内の前記一つあるいはそれ以上の前記データパケットが消失したことに応答して、復号するための方法であって、前記データパケットの系列は情報の連続流を表し、それらに対する符号化された順方向誤り訂正データを含み、各符号化されたデータパケットはセットのペイロード情報を含み、このセットのペイロード情報は各々の複数の対応する個別のペイロード情報部分に同様に分割され、各データパケットの前記個別のペイロード情報部分の２つあるいはそれ以上が前記情報流の対応するセグメントを表し、各データパケットの前記個別のペイロード部分の別の一つあるいはそれ以上が前記順方向誤り訂正データを表し、前記データパケットの符号化系列が、
（ａ）複数の前記データパケットを符号化するステップと、
（ｂ）前記データパケットの追加の一つを符号化するステップとを含む方法によって符号化されており、
前記ステップ（ａ）において、前記データパケットの各々の符号化が、それらの前記複数の個々のペイロード情報部分の少なくとも一つを符号化することで、その中に含まれる前記セットのペイロード情報を符号化するステップを含み、
前記ステップ（ｂ）において、前記追加のデータパケットが前記系列内において前記複数の各々のデータパケットの後に続き、このため前記複数のデータパケットは前記追加のデータパケットに先行し、前記追加のデータパケットの符号化がその中に含まれる前記セットのペイロード情報を符号化するステップを含み、前記符号化された追加のデータパケットがさらに前記複数の先行するデータパケット内に含まれる前記ペイロード情報に対する前記順方向誤り訂正データ能力を表す追加のセットのペイロード情報を含み、
前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報が前記先行する２つあるいはそれ以上のデータパケット内に含まれる前記ペイロード情報の組合せに基づいており、前記追加のセットのペイロード情報が基づく前記先行する少なくとも２つのデータパケット内に含まれる前記ペイロード情報がそれらの異なる個別のペイロード情報部分からのペイロード情報を含み、
この復号方法が：
前記データパケットの前記符号化された追加の一つを復号するステップを含み、前記データパケットの前記追加の一つが前記系列内において前記消失したデータパケットの少なくとも一つの後に続き、これによって、前記データパケットの前記個別のペイロード情報部分の、前記順方向誤り訂正データを表す、少なくとも一つが生成され；この復号方法がさらに
前記データパケットの前記復号された追加の一つの少なくとも一つの前記生成された個別のペイロード情報部分に基づいて前記消失したデータパケットの前記少なくとも一つを再生するステップを含むことを特徴とする方法。
【請求項７】
情報の連続流を表すデータパケットの系列を符号化するための装置であって、各データパケットはそれに対応する前記情報流のセグメントを表すセットのペイロード情報を含み、各セットのペイロード情報は複数の対応する個別のペイロード情報部分に同様に分割され；この装置が：
複数の前記データパケットの各々を、その中に前記複数の個々のペイロード情報部分の少なくとも一つを符号化することによって含まれる前記セットのペイロード情報を符号化することで符号化する符号器を含み、この装置がさらに
前記データパケットの追加の一つを、その中に含まれる前記セットのペイロード情報を符号化することによって符号化する符号器を含み、前記追加のデータパケットが前記系列内において前記複数の各々のデータパケットの後に続き、前記複数のデータパケットがこのために前記追加のデータパケットに先行し、前記符号化された追加のデータパケットがさらに前記複数の先行するデータパケット内に含まれる前記ペイロード情報に対する順方向誤り訂正能力を提供する追加のセットのペイロード情報を含み、
前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報が前記先行する２つあるいはそれ以上のデータパケット内に含まれる前記ペイロード情報の組合せに基づいており、前記追加のセットのペイロード情報が基づく前記先行する少なくとも２つのデータパケット内に含まれる前記ペイロード情報がそれらの異なる個別のペイロード情報部分からのペイロード情報を含むことを特徴とする装置。
【請求項８】
符号化されるべき各データパケット内に含まれる前記セットのペイロード情報がｍ個の対応する個別のペイロード情報部分に同様に分割され、ここでｍは１より大きな整数を表し、前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報がｍ個の前記複数のデータパケットのｍ個の異なる個別のペイロード情報部分の検査合計を含み、この検査合計が単一パリティ検査ブロック符号に基づき、結果としてレートｍ／（ｍ＋１）順方向誤り訂正符号が得られることを特徴とする請求項７記載の装置。
【請求項９】
符号化されるべき各データパケット内に含まれる前記セットのペイロード情報がｍ個の対応する個別のペイロード情報に同様に分割され、ｍは１より大きな整数を表し、前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報が最大距離分離可能ブロック符号に基づく検査合計を含むことを特徴とする請求項７記載の装置。
【請求項１０】
前記追加の一つのデータパケット内に含まれる前記追加のセットのペイロード情報が前記先行する２つあるいはそれ以上のデータパケットとは別のデータパケットに基づく一つあるいはそれ以上の追加のセットのペイロード情報にてインタリーブされることを特徴とする請求項７記載の装置。
【請求項１１】
データパケットの符号化された系列を、この系列内の一つあるいはそれ以上の前記データパケットが消失したことに応答して、復号するための装置であって、前記データパケットの系列は情報の連続流を表し、それらに対する符号化された順方向誤り訂正データを含み、各符号化されたデータパケットはセットのペイロード情報を含み、このセットのペイロード情報は各々の複数の対応する個別のペイロード情報部分に同様に分割され、各データパケットの前記個別のペイロード情報部分の２つあるいはそれ以上が前記情報流の対応するセグメントを表し、各データパケットの前記個別のペイロード部分の別の一つあるいはそれ以上が前記順方向誤り訂正データを表し、前記データパケットの符号化系列が、
（ａ）複数の前記データパケットの各々を、その中に前記複数の個々のペイロード情報部分の少なくとも一つを符号化することによって含まれる前記セットのペイロード情報を符号化することによって、符号化する符号器と、
（ｂ）前記データパケットの追加の一つを、その中に含まれる前記セットのペイロード情報を符号化することによって符号化する符号器とを含む装置によって符号化されており、
前記追加のデータパケットが前記系列内において前記複数の各々のデータパケットの後に続き、前記複数のデータパケットはこのため前記追加のデータパケットに先行し、前記符号化された追加のデータパケットがさらに前記複数の先行するデータパケット内に含まれる前記ペイロード情報に対する前記順方向誤り訂正データ能力を表す追加のセットのペイロード情報を含み、
前記符号化された追加のデータパケット内に含まれる前記追加のセットのペイロード情報が前記先行する２つあるいはそれ以上のデータパケット内に含まれる前記ペイロード情報の組合せに基づいており、前記追加のセットのペイロード情報が基づく前記先行する少なくとも２つのデータパケット内に含まれる前記ペイロード情報がそれらの異なる個別のペイロード情報部分からのペイロード情報を含み、
この復号装置が：
前記データパケットの前記符号化された追加の一つを復号する復号器を含み、前記データパケットの前記追加の一つが前記系列内において前記消失したデータパケットの少なくとも一つの後に続き、これによって前記データパケットの前記個別のペイロード情報部分の、前記順方向誤り訂正データを表す、少なくとも一つが生成され、この復号器がさらに前記データパケットの前記復号された追加の一つの少なくとも一つの前記生成された個別のペイロード情報部分に基づいて前記消失したデータパケットの前記少なくとも一つを再生することを特徴とする装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的には、データ伝送用の誤り訂正符号の分野、より詳細には、リアルタイムマルチメディア通信を提供するデータパケットベースの網内で用いるためのパケット損失回復技法に関する。
【０００２】
【従来の技術】
データパケットベースの通信網、例えばインターネット、内で扱われなければならない最も重要な問題の一つはパケット損失に起因する誤り訂正の問題である。各データパケットは網内を独立的に（潜在的に完全に異なる網ルートを経由して）伝送されるために、宛先位置において、しばしば、一つあるいは複数のデータパケットの系列を受信することに失敗したり、異常に大きな遅延の後に幾つかのこれらパケットが受信されることがある。そして、このような網がリアルタイムマルチメディア通信、例えば、音声通信を提供するために採用される場合、幾つかのデータパケットを大きな遅延の後に受信することは、受信機は、典型的には、後続データパケットの処理の開始を待つことはできないために、これらを全く受信しなかったのと同じこととなる。
【０００３】
パケット損失問題を含む誤り訂正の一般問題を解決するために、常にある種の冗長符号化を伴う幾つかの技法が採用されている。典型的には、パケット損失通信路（packet loss channel）は、通信路符号化用語を用いると消失通信路（erasure channel）として認識される。全て当業者においては周知のバイナリブロック符号（binary block codes）、畳込み符号（convolutional code）およびリードソロモン符号（Reed Solomon codes）などの従来の誤り訂正符号を消失訂正モードにて用いることができる。これに関しては、例えば、E.Ayanoglu et al.“Diversity Coding for Transparent Self-Healing and Fault-Tolerant Communication Networks”,IEEE Transactions on Communications,vol.41,no.11,pp.1677-1685,November,1993；および１９９７年７月１５日付けで出願された、本発明の譲受人に譲渡された、R.Urbankらの“Methods and Apparatus for Packetizing Data for Transmission Through an Erasure Broadcast Channel”なる名称の本発明の譲受人を同一とする係属中の合衆国特許出願Ser.No.０８／８９２８５５を参照されたい。ただし、実は、消失の訂正は、他のタイプの誤り（例えば、一つあるいは複数のシンボルの“ランダム（random）”な変更（モディフィケーション）を訂正するように遥かに単純である。誤りの場合は、最初に誤りの箇所を決定する必要があるが、消失（例えば、受信されなかったデータパケット）の場合は位置は既知である。
【０００４】
典型的にはランダム誤り訂正符号は、ある与えられたブロック内の誤りの約２倍の消失を訂正することができる。ただし、データパケットの系列を網間で伝送するという文脈においては、あるパケットの損失は、結果として消失シンボルの連続ストリング（“バースト（burst）”）の発生もたらす。殆どの従来の通信路符号はランダム誤り（あるいはランダム消失）の訂正を対象として設計されているために、パケット損失問題を扱う従来の技術によるアプローチは、典型的にはパケットの比較的長い系列に関してある形式のインタリービング（並べ替え）を遂行する。こうすることで、関連する消失（つまり、消失シンボルの一連のストリング）を持つパケット損失通信路が見かけ上ランダムな消失通信路に変換される。ただし、不幸なことに、このようなインタリービング過程を遂行した場合、復号器がデータパケットの元の系列を再生するために受信されたデータをデインタリーブすることを要求され、宛先の所で大きな遅延が発生する。
【０００５】
従って、通信路符号、例えば、リードソロモン符号の使用は、事実上順番に送られる多数のパケットを横断して適用された場合は、必然的に受信機の所で比較的長い遅延が発生することとなる。上述のように、このような長い遅延はリアルタイムアプリケーション、例えば、インターネットプロトコル（ＩＰ）に基づく網を通じての音声通信では、致命的になり得る。このような背景から、最近、１９９９年２月９日付けでG.M.Shusterらに交付された合衆国特許第５，８７０，４１２(“Foward Error Correction System for Packet Based Real Time Media”)(以降、“Shusterら”と呼ぶ)において、バース性パケット網内でデータを回復するための（他の従来の技術と比較して）短い遅延を持つ方法が開示された。
【０００６】
より詳細には、Shusterらは、順方向誤り訂正を各データパケットに検査合計情報を付加することで遂行し、この検査合計情報は、先行する所定の数のデータパケットからの情報部分(“ペイロード(payload)”)のビット毎の排他的論理和を取ることで定義される。（先行するパケットからの情報ペイロードの長さが等しくない場合は、このより短なペイロードに基づくビットパディングが用いられる）。一例として、図１は、Shusterらによって採用される従来の技術によるパケット損失回復技法に従って符号化されたデータパケットの編成を示す。示されるデータパケットは、符号化情報とこれに続く順方向誤り訂正の目的でデータパケットに付加された検査合計情報を含む。上で説明したように、Shusterらの技法の場合、この検査合計情報は、より具体的には、先行する所定の複数個のデータパケットからのペイロード情報の排他的論理和から成る。
【０００７】
こうしてShusterらの技法を用いた場合、長さｗ＋１のパケットインスタンスの単一ビット消失訂正符号が形成されるが、これは最大ｗ個までの損失データパケットのバーストを（このバーストの後にｗ個のデータパケットのストリングが正常に受信されることを前提に）最大２ｗ−１パケットなる復号遅延にて訂正する能力を持つ。明らかなように、Shusterらの方法では、情報ペイロードのビットのみと比較して、ビットボリームにおいて、少なくとも１００％（ビットパディングが要求される場合はそれ以上）のオーバヘッドが発生する。加えて、Shusterらの方法では、排他的論理和の等式を解くことが要求される。
【０００８】
H-L.LouおよびC-E.W.Sundbergによって１９９９年１０月２１日付けで出願された、本発明と譲受人を同一とし、本発明の譲受人に譲渡された“Packet Loss Control Method For Real-Time Multimedia Communications”なる名称の係属中の合衆国特許出願Ser.No.０９／４２５，１４３号（以降“Louら”と呼ぶ）においては、Shusterらの技法と比較して著しく改善された技法が開示される。この特許出願についても参照されたいが、解説のために、図２は、Louらによって採用される従来の技術によるパケット損失回復技法に従って符号化されたデータパケットの編成を示す。
【０００９】
より具体的には、Shusterらは複数の先行するデータパケットからのペイロード情報を“結合（combining）”すること（例えば、これらに関して排他的論理和演算を遂行すること）で検査合計情報を生成するが、Louらは、後のパケット内で先行するデータパケットの特定の一つからの情報内容を単に“反復(repeats)”する。より具体的には、Louらの技法によると、ある与えられたデータパケットｋと関連する情報ペイロードが同一にコピーされ、データパケットｋ＋ｗに付加される。（つまり、この情報ペイロードがｗ個の送信パケットに相当する遅延にて反復される）。この改善されたアプローチでは、長所として、最高ｗ個までの損失データパケットのバーストを訂正できる（Shusterらの方法も同じ）一方で、復号遅延は、Shusterらの方法では２ｗ−１の復号遅延が要求されるのとは対照的にｗ個のパケットに改善される。事実、Louらの技法によって要求される復号遅延は、正常に訂正できる一連の損失パケットの数に対して、実際に、最適であることを示すことができる。（これら従来の技術のアプローチの両方において、現存のパケットに順方向誤り訂正データは付加されるが、追加のパケットは付加されないことに注意する）。
【００１０】
【発明が解決しようとする課題】
ただし、上述の従来の技術によるアプローチの両方とも（つまり、ShusterらのアプローチとLouらの改善された方法の両方とも）、レート１／２の畳込み順方向誤り訂正（ＦＥＣ）符号しか提供することができない。（当業者においては周知のように、誤り訂正符号の“レート(rate)”は、符号化されるべき与えられたセットのデータを符号化するために用いられるビットの総数とこの内の符号化されるべき情報ビットの数の比に基づいて決定される）。ただし、伝送効率を高める目的で１／２より大きなレートを持つ誤り訂正符号を採用することがしばしば要望される。従って、Louらのレート１／２技法と同様に、長所として、バースト消失に対する比較的高レベルの通信路保護を（最適ではないとしても）比較的低い復号遅延にて提供でき、しかも現存の送信パケットの数と現存のパケット構造を維持できる、１／２より大きなレートを持つ順方向誤り訂正通信路符号を考案することが強く要望される。
【００１１】
【課題を解決するための手段】
本発明の原理によると、バースト消失に対する高レベルの通信路保護を比較的低い復号遅延にて提供することができる１／２より大きな符号化レートを持つ新規のクラスの順方向誤り訂正符号が提供される。より具体的には、本発明の幾つかの実施例による通信路符号化のための新規の方法によると、符号化されるべき各データパケット内に含まれるソース情報（つまり、データ）が類似に複数の（類似の）対応する部分に分割され、次に、複数のデータパケットを通じて“検査合計（checksums）”が計算される。この検査合計は、これら複数のパケットの内の少なくとも２つのパケットの異なる（つまり、非対応）部分に基づく。次に、これら“検査合計”が、好ましくは、（上述の従来の技術による技法と同様に）符号化されるべき様々な後続データパケットに付加される。ただし、それから検査合計が計算される複数のパケットの異なる部分を用いることで（検査合計が複数のパケットの異なる部分に基づいて計算されるために）、長所として、１／２より大きなレートを持つが、ただし、バースト消失に対する高いレベルの通信路保護を、低い復号遅延にて提供できる順方向誤り訂正符号が提供される。本発明の復号器実施例によると、消失データパケットは、こうして付加された“検査合計”データを含む一つあるいは複数の後続の（正常に受信された）データパケットの復号に基づいて再生される。
【００１２】
より具体的には、本発明によると、情報の連続流を表すデータパケットの系列を符号化する方法あるいは装置か提供される。ここで、各データパケットはそれに対応する前記情報流のセグメントを表すセットのペイロード情報を含み、各セットのペイロード情報は、複数の対応する個別のペイロード情報部分に類似に分割される。この方法あるいは装置は、複数の前記データパケットを符号化するためのステップあるいは手段を含み、前記データパケットの各々の符号化は、その中に含まれる前記セットのペイロード情報を符号化するために、それらの前記複数の個々のペイロード情報部分の少なくとも一つを符号化するステップを含む。この方法あるいは装置はさらに、前記データパケットの追加の一つを符号化するステップあるいは手段を含み、この追加のデータパケットは前記系列内において前記複数の各々のデータパケットの後に続き、このため前記複数のデータパケットは前記追加のデータパケットに先行する。前記追加のデータパケットの符号化は、その中に含まれる前記セットのペイロード情報を符号化することからなり、前記符号化された追加のデータパケットは、さらに前記複数の先行するデータパケット内に含まれる前記ペイロード情報に対する順方向誤り訂正能力を提供する追加のセットのペイロード情報を含む。前記符号化された追加のパケット内に含まれる前記追加のセットのペイロード情報は、前記先行する２つあるいはそれ以上のデータパケット内に含まれる前記ペイロード情報の組合せに基づき、前記追加のセットのペイロード情報がそれに基づく前記先行する少なくとも２つのデータパケット内に含まれる前記ペイロード情報は、それらの異なる個別のペイロード情報部分からのペイロード情報を含む。
【００１３】
加えて、本発明によると、データパケットの符号化された系列を、この系列内の前記一つあるいはそれ以上のデータパケットが消失した状況において、復号するための方法あるいは装置が開示される。前記データパケットの系列は、上述の符号化技法を用いて符号化されており、この方法あるいは装置は前記データパケットの前記符号化された追加の一つを復号するためのステップあるいは手段を含み、前記データパケットの前記追加の一つは前記系列内において前記消失したデータパケットの少なくとも一つの後に続き、これによって、前記データパケットの前記個別のペイロード情報部分の、前記順方向誤り訂正データを表す、少なくとも一つが生成される。この装置あるいは装置はさらに前記データパケットの前記復号された追加の一つの少なくとも一つの前記生成された個別のペイロード情報部分に基づいて前記消失したデータパケットの前記少なくとも一つを再生するステップあるいは手段を含む。
【００１４】
【実施例】
表記法
任意のシンボルｓに対して、ｓｘは、ｓをちょうどｘ回反復することで得られるストリングであるものと定義する（例えば、｛００｝２＝｛００００｝）。我々は２つのストリング、ａとｂの連接（concatenation）を◇として表記する(例えば、｛０１｝◇｛１１｝＝｛０１１１｝)。
【外１】
0004009895.tif 000002
【００１５】
消失の系列ｅ１＋ｌ，ｅ１＋２，．．．，ｅ１＋ｓは、以下が満たされるとき、長さｇの“保護スペース(guard space)”に関する長さｓの“消失バースト(erasure burst”)”と呼ばれる：
１．ｅ１＋ｌ＝ｅ１＋ｓ＝１
２．ｅ１＋ｌに先行するｇ個のシンボルとｅ１＋ｓに続くｇ個のシンボルが全て０である。
３．ｅ１＋ｌからｅ１＋ｓまでのｓ個のシンボルがｇ個の０の部分系列（subsequence）を含まない。
【００１６】
0004009895.tif 000003
我々はＤを用いて、遅延演算子（delay operator）を表す。こうして、時刻０と時刻１における２個のシンボルが非零であり、他の全てのシンボルは０である情報系列は以下のように書かれる：
【数１】
0004009895.tif 000004
同様に対応する反復符号（repetition code）に対する符号化シーケンスは以下のように書かれる：
【数２】
0004009895.tif 000005
0004009895.tif 000006
【００１７】
【外４】
0004009895.tif 000007
我々は同一の表記法を用いて、系列間のハミング距離（Hamming distance）も表す。２つの系列間のハミング距離は、シンボル間の距離の総和として以下のように定義される：
【数３】
0004009895.tif 000008
距離の評価においてはシンボルのサイズも関係することに注意する。例えば、
【数４】
0004009895.tif 000009
【００１８】
幾つかの従来の技術の幾つかの有益な基準との関連での再検討
バースト消失通信路（burst erasure channels）として特性化されるする大きなクラスの潜在的通信路が存在し、一般通信路に対するある与えられた順方向誤り訂正符号（forward error correcting code）の品質を特定化（評価）するために様々な尺度（メトリック）を用いることができる。ただし、一つの一般的な有益な基準として、しばしば、誤り訂正符号は、好ましくは、一定の遅延および保護スペースの下で、その符号によって訂正できる最長消失バースト（longest erasure burst）を測定することで評価される。こうして、我々は、我々の“目標（goal）”を固定された（および好ましくは最小の）復号遅延という制約の下で、バースト消失通信路（つまり、複数の連続する消失が発生する傾向のある通信路）を通じて情報を伝送する際の信頼性として明確に定義する。
【００１９】
図１は、Shusterらによって開示される従来の技術によるパケット損失回復技法（packet loss recovery technique）に従って符号化された符号化データパケット（encoded data packets）の系列の編成を示す。ここに開示される特定の技法は、（例えば）長さ3の消失バーストを、レート１／２組織的誤り訂正符号（systematic error correcting code）にて訂正するように設計される。明らかなように、レート１／２の符号を用い、同一の情報レート（information rate）を維持するためには、パケットペーロードサイズ（packet payload size）を2倍にする必要がある。情報ビット（information bits）はパケットペイロードの“左”（つまり、第一）の半分を占有するシンボルｘ［ｉ］にグループ化され、パリティ検査ビット（parity check bits）はパケットペイロードの“右”（つまり、第二）の半分を占有するシンボルにグループ化される。例えば、図１からわかるように、Shusterらの技法に従ってｉ番目の符号化パケットを生成するための規則は以下の通りである：
0004009895.tif 000010
【００２０】
図２は、Lou etらによって開示される従来の技術によるパケット損失回復技法に従って符号化された符号化データパケットの系列の編成を示す。より具体的には、Louらは “複製・遅延（duplicate and delay）”符号と呼ばれる符号を提唱する。
【外６】
0004009895.tif 000011
ｘ［ｉ＋ｊ］は、ｙ１［ｉ＋ｊ＋３］（ここでｊ∈｛１，２，３｝）から回復されることに注意する。こうして、Shusterらによって開示される技法では復号遅延は５であるのに対して、Louらの技法の復号遅延は、長所として３となる。このため、この単純な“複製・遅延”符号は、Shusterらによって開示される符号よりも（我々によって採用される基準あるいは“目標”の観点からは）優れていることがわかる。つまり、両符号とも３個の消失のバーストを訂正することができるが、“複製・遅延”符号の方が復号遅延は短かくなる。
【００２１】
本発明の実施例のクラスの概要
本発明の原理によると、組織的線形時不変畳込み符号（systematic,linear,time-invariant,convolutional codes）のクラスを構成する技法が開示される。これらクラスの符号は、長所として、“最大限に短かい（maximally short）”。我々は、これら符号をこれらが長所として一定の消失バースト長の下で、可能な限り最短の復号遅延と可能な限り最短の保護長を持つために“最大限に短かい（maximally short、MS）”と呼ぶ。この技法は、１／２より大きな様々な符号化レートを持つ符号のクラスを提供するが、あるさらなる概念を導入するためおよび幾つかの鍵となるアイデアを導入するために、以下では、最初に、本発明の第一と第二の実施例による対のレート２／３の符号、並びに本発明の第三の実施例によるレート３／５の符号について詳細に説明し、最後に、これら符号の一般クラスについて説明する。
【００２２】
より具体的には、我々は、ＭＳ符号が、長所として形式Ｒ＝（ｍｓ＋１）／（ｍｓ＋１＋ｓ）（ここで、ｍとｓは任意の正の整数を表す）なる全てのレートに対して、どのようにして構成されるかについて説明する。我々は、以降、レート（ｍｓ＋１）／（ｍｓ＋１＋ｓ）の符号をＭＳ（ｍ，ｓ）符号と呼ぶ。これら符号は、長所として、長さｓの消失バーストを、以下のような保護長（ｇ）および復号遅延（ｔ）にて訂正する能力があることが示される：
ｇ＝Ｔ＝ｍｓ＋１
本発明の幾つかの実施例において、我々は、ある与えられ係数λだけのアップサンプリングに対応する単純な周期的インタリービング技法（simple periodic interleaving technique）についても開示する。提唱されるやり方にてインタリービングすることで、本発明に原理に従って展開される、長さｓの消失バーストを保護長ｇおよび復号遅延Ｔにて訂正することができるＭＳ（ｍ，ｓ）符号を、長所として長さλｓの消失バーストを対応する保護長λｇと復号遅延λＴにて訂正できる関連する符号に変換することが示される。
【００２３】
本発明による一例としての構成は、長所として、組織的、線形、最大距離分離可能（systematic,linear,maximum distance separable（MDS））ブロック符号を広範に利用する。ＭＤＳ符号は当業者においては周知であり、ＭＤＳ符号は有益な特性を持ち、リードソロモン符号（Reed-Solomon codes）として構成できるために、有益な構築ブロックである。（リードソロモン符号についても当業者においては周知である）。より具体的には、周知のように、線形組織的リードソロモン符号（linear,systematic,Reed-Solomon codes）は、ＧＦ（ｑ＝２ｒ）上のｑ−元シンボルを用いて（ｎ，ｋ，ｄ＝ｎ−ｋ＋１）の全ての値に対して構成することができる。
【００２４】
第一の実施例によるレート２／３の符号
線形時不変畳込み符号を考察する場合、当業者において周知の、全て０の状態から開始する符号器の出力から成る、零状態応答（zero state response、ZSR）が有益なツールとなる。我々は、時刻０においてのみ非零である入力に対する零状態応答（ＺＳＲ０）を用いることである符号を完全に指定することができる。ただし、符号の解析は、単に時刻０における入力の代わりに、入力シンボルのストリームに対してＺＳＲを書き出す方が通常は容易である。例えば、本発明の第一の実施例によるレート２／３パリティ検査符号について考察する。より具体的には、以降ＭＳ（１，１）と呼ばれるこの一例としての符号は以下のＺＳＲ０を持つものとして定義される：
【数５】
0004009895.tif 000012
【００２５】
図３は本発明の第一の実施例に従って構成された符号の一例としての零状態応答を示す。より具体的には、図には時刻０から開始する情報シンボルのストリームに対するＺＳＲが示される。
【００２６】
図４は、図３に示すＺＳＲにて明確に定義される、本発明の第一の実施例に従って符号化された符号化データパケットの系列の編成を示す。図４からわかるように、この一例としてのＭＳ（１，１）符号は、長所として、長さ１の消失バーストを、保護スペース２および復号遅延２にて、訂正することができる。
【外７】
0004009895.tif 000013
【００２７】
明らかなように、本発明の第一の実施例に対して要求される復号遅延はＴ＝２となる。要求される保護スペースは、この復号“規則(rule)”は、消失の後の２個のシンボルと消失の前の１個のシンボルのみが消失しないことのみを要求するため、ｇ＝２となる。この一例としてのＭＳ（１，１）符号は、これら採択された基準の観点から、長所として“最適（optimal）”であることが容易にわかる。
【００２８】
第二の実施例によるインタリーブドレート２／３符号
実は、１個の消失のみを訂正する符号は、“バースト消失（burst erasure）”訂正符号の直観的意味を満たさない。ただし、程度（degree）λの周期的インタリービングを用いることで、長所として、本発明の原理に従って導かれた、それぞれ、保護長ｇと復号遅延Ｔを持つｓ消失バースト符号を、それぞれ、保護長λｇと復号遅延λＴを持つλｓ消失バースト符号に変換することができる。より具体的には、本発明の第二の実施例においては、このようなインタリービング過程が用いられるが、これは、長所として、単にアップシンプリングから成る。
【外８】
0004009895.tif 000014
【００２９】
図５は、本発明の第二の実施例に従って符号化された符号化データパケットの系列の編成を示す。この第二の実施例においては、ＭＳ（１，１）符号（つまり、本発明の第一の実施例のレート２／３符号）をλ＝２だけアップサンプリングすることで、ＺＳＲ０
【数６】
0004009895.tif 000015
が得られる。
【００３０】
本発明の第二の実施例によると、２個の消失のバーストが、例えば、時刻ｔ＝４において始まった場合、この消失シンボルは、本発明の第一の実施例（つまり、アップサンプリングされないレート２／３の符号）との関連で上で説明したのと類似のやり方で回復することができる。このアップサンプルド符号（upsampled code）に対して要求される復号遅延および保護長は、明らかに、“ベース（base）”の符号に対して要求されるそれの二倍となる。こうして、第二の実施例によるアップサンプルド符号は、ｇ／ｓ＝Ｔ／ｓ＝４／２＝２を持つレート２／３の符号となり、この符号も、長所として、採択された基準の観点から“最適”となる。
【００３１】
当業者においては明らかなように、一般に、レートＲ＝（ｍ＋１）／｛ｍ＋２｝のＭＳ（ｍ，１）符号を、長所として、ｍ≧１の任意の値に対して、本発明の原理に従って、本発明の第一の実施例の説明において上で説明されたそれ（つまり、レート２／３の符号）と類似の単一パリティ検査符号を用いて構成することができる。これも当業者においては明らかなように、これら符号は、復号遅延Ｔ＝ｍ＋１を持ち、保護スペースｇ＝ｍ＋１を要求し、これら符号も、長所として、上に説明の“最適性（optimality）”基準を満足する。さらに、これら符号も、長所として、任意の倍数λ＝ｓにてアップサンプルすることで、任意のｓ≧１に対して、長さｓの消失バーストを訂正する符号を生成することができ、明らかなように、これら符号も、長所として、上述の“最適性（optimality）”基準を満足する。
【００３２】
第三の実施例によるレート３／５の符号
本発明の第一の実施例に従って上のように定義されるＭＳ（１，１）符号は、当業者においては周知の（３，２）単一パリティ検査（single parity check、SPC）ブロック符号に基づく。ただし、例えば、図４から分かるように、これらパリティ検査シンボルは、シンボルの“行（rows）”あるいは“列（columns）”に基づいてではなく、長所として、シンボルの“対角（diagonals）”に基づいて計算される。ＭＳ（１，１）符号を、この望ましい性能特性を維持したまま２／３以外の符号レートに一般化するために、我々は、長所として、パケットを横断して計算されたブロック符号を使用するという概念は維持するが、ただし、ＳＰＣブロック符号の代わりに、（これも当業者においては周知の）最大距離分離可能（maximum distance separable、MDS）ブロック符号を用いることに発想を転換する。より具体的には、Ｃは、組織的（ｎ，ｋ，ｄ）＝（６，４，３）ブロック符号を表すものとする。（当業者においては周知のように、（６，４，３）ＭＤＳ符号は、最初、ＧＦ（２３）上の（８，４，５）組織的リードソロモン符号を構成し、次に、最後の２個のパリティ検査シンボルをパンクチャリングすることで構成することができる）。我々は、４個の情報シンボル（ｘ０，ｘ１，ｘ２，ｘ３）に対応するＣの２個のパリティ検査シンボルをＰ｛ｘ０，ｘ１，ｘ２，ｘ３｝として表す。
【００３３】
本発明の第三の実施例によるレート３／５，ＭＳ（１，２）符号に対するＺＳＲ０は以下の通りである：
【数７】
0004009895.tif 000016
【００３４】
図６は、この一例としてのＭＳ（１，２）符号および上述のＺＳＲ０に基づいて、本発明の第三の実施例に従って符号化された符号化データパケットの系列の編成を示す。図６はさらに長さ２の与えられた消失バーストを復号する一例としての過程も示す。
【外９】
0004009895.tif 000017
ｘ０［４］は前のステップにおいて回復されており、ｘ０［５］は消失しないため、ｘ１，２［３］は正常に回復される。最後に、復号器がｙ３，４［７］＝Ｐ｛ｘ０［６］，ｘ０［５］，ｘ１［４］，ｘ２［４］｝が受信された時点で、復号器は、長所として、ｘ０［５］とｘ０［６］も（一例として）消失しないために、ｘ１，２［４］を正常に回復する。
【００３５】
図６を調べることで容易に分かるように、時刻ｔから始まる長さ２の消失バーストに対しては、ここに説明される一例としての復号規則は、シンボルｔ＋２，ｔ＋３およびｔ−１は消失しないことを要求する。従って、要求される保護スペースは、明らかにｇ＝２であることがわかる。同様に、復号遅延もＴ＝２であることも分かる。これら値は上述の“最適性”基準を満足し（従って、説明の一例としてのＭＳ（１，２）符号は、事実、“最大限に短な（maximally short）”符号である）。
【００３６】
このＭＳ（１，２）符号は、長所として、本発明の第二の実施例において遂行されるＭＳ（１，１）のアップサンプリングと同様なやり方にてアップサンプリングすることができる。より具体的には、本発明のもう一つの実施例によると、このＭＳ（１，２）をλだけアップサンプリングすることで、長さｓλの消失バーストを、保護スペースｇλおよび復号遅延Ｔλにて、訂正することができるレート３／５符号が得られる。（ここでも、“ベース（base）”符号は最大限に短なため、こうしてアップサンプリングされた符号も長所として最大限に短くなることに注意する）。
【００３７】
本発明の一般化クラスの実施例
図７は、本発明の一般クラスの１つの実施例に従って符号化された符号化データパケットの系列の編成の一般図を示す。より具体的には、以下では、本発明の原理に従って、一般ＭＳ（Ｍ，Ｓ）符号を全てのｍ≧１および全てのｓ≧１に対して構成するための技法について説明する。本発明の一つの好ましい実施例においては、この構成に基づいて、一つのクラスの符号器および復号器が導かれる。上に説明のＭＳ（１，１）およびＭＳ（１，２）符号と同様に、これら一般化ＭＳ（ｍ，ｓ）符号（並びにこれらのアップサンプリングされた“バージョン”）は、全て“最大限に短く（maximally short）”、従って、上述の基準の観点から“最適（optimal）”である。より具体的には、この一例としての手続きによって構成される全てのＭＳ（ｍ，ｓ）符号は、レートＲ＝（ｍｓ＋１）／（ｍｓ＋１＋ｓ）を持ち、これらは、長所として、長さｓの消失バーストを、保護スペースｇ＝ｍｓ＋１および復号遅延Ｔ＝ｍｓ＋１にて、訂正することができる。
【００３８】
より具体的には、本発明の原理に従って一例としてのＭＳ（ｍ，ｓ）符号を構成するためには、我々は、最初に、パラメータ（ｎ，ｋ，ｄ）＝（２ｓ＋ｋ−１，ｋ＋ｓ−１，ｓ＋１）を持つ組織的ＭＤＳブロック符号Ｃを構成する。
【外１０】
0004009895.tif 000018
当業者においては周知のように、ＧＦ（２ｒ）上のリードソロモン符号は全ての（ｎ≦２ｒ，ｋ≦ｎ，ｎ−ｋ＋１）に対して構成することができる。ｒビットのグループが、この符号に対する個々のシンボルに写像される。パケットサイズがrビットの倍数でない場合は、一つの好ましい実施例においては、パケットの終わりの所にあるパディング（padding）が追加される。
【００３９】
今、Ｐ｛ｘ０，ｘ１，．．．，ｘｋ｝がＣに対するｎ−ｋ＝ｓ個のパリティ検査シンボルを表すものとする。このとき、このＭＳ（ｍ，ｓ）符号に対するＺＳＲ０は以下によって与えられる：
【数８】
0004009895.tif 000019
上に示すようなＺＳＲ０が与えられた場合、本発明の原理に従って、容易に一般クラスのＭＳ（ｍ，ｓ）符号を導くことができる。次に、これから符号器および復号器を簡単に導くことができる。上のＺＳＲ０および図７に示すような一例としての符号化を調べることで、時刻iにおける符号化シンボルはより具体的には以下のようになることがわかる：
【数９】
0004009895.tif 000020
【００４０】
上のやり方で定義されるＭＳ（０，ｓ）符号は、Louらによって開示される遅延・複製符号（つまり、１／２反復符号）と同様にレート１／（ｓ＋１）反復符号である。一般に、１／２以下のレートに対するＭＳ符号は反復符号であるが、本発明の様々な好ましい実施例によると１／２以上のレートに対するＭＳ符号は適当な“検査合計（checksum）”の計算を伴う。このためＭＳ符号は、広い意味において遅延・複製符号の“一般化（generalization）”と見ることもできる。例えば、レートＭＳ（ｍ，１）符号はレート（ｍ＋１）／（ｍ＋２）単一パリティ検査畳込み符号であり、このパリティ検査は上で図４との関連で説明した一例としての２／３レート符号と同様に対角に基づいて計算されることに注意する。
【００４１】
詳細な説明に対する付録
上述の説明は単に本発明の一般原理を解説するものであることに注意する。理解できるように、当業者においては、ここには明示的には説明されなかったが、本発明の原理を具現し、本発明の精神および範囲に含まれる他の様々な構成を考案できるものである。さらに、ここに示される全ての実施例および条件を述べる言語は、主として、教示を目的とするもの、つまり、本発明の原理および発明者の当分野の進歩への貢献の概念を理解することを助けるのを目的とし、本発明はここに具体的に示される実施例および条件に制限されるものと解されるべきではない。さらに、本発明の原理、特徴、実施例、およびこの具体例を説明する全ての記述は、これらの構造上および機能上の両方の同等物も包含するものである。加えて、これら同等物には現在知られている同等物と将来開発されるであろう同等物の両方、つまり同一の機能を遂行する開発されたあらゆる要素が、構造とは関係なく、含まれるものである。
【００４２】
例えば、当業者においては理解できるようにブロック図は本発明の原理を具現する一例としての回路の概念図である。同様に、当業者においては理解できるように任意のフローチャート、フローダイアグラム、状態遷移図、疑似コード等は、コンピュータあるいはプロセッサが明示的に示されているか否かに関係なく、本質的にコンピュータにて読み出し可能な媒体内に表現され、コンピュータあるいはプロセッサによって実行される様々な過程を表す。
【００４３】
図面に示される様々な要素の機能は、“プロセッサ”あるいは“モジュール”としてラベルされる機能ブロックも含めて、専用のハードウエアを用いて提供することも、ソフトウエアを実行する能力のあるハードウエアを適当なソフトウエアとの関連で用いて提供することもできる。プロセッサによって提供される場合でも、これら機能は、単一の専用のプロセッサにて提供することも、単一の共有プロセッサにて提供することも、幾つかが共有される複数の個別のプロセッサにて提供することもできる。さらに、“プロセッサ”あるいは“コントローラ”なる用語の明示的な使用は、ソフトウエアを実行する能力を持つハードウエアを排他的に指すのではなく、これには暗黙的にこれに制限されるものではなが、デジタル信号プロセッサ（ＤＳＰ）ハードウエア、ソフトウエアを格納するための読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）および不揮発性メモリも含まれるものである。他の従来のおよび／あるいはカスタムハードウエアも含まれるものである。同様に、図面に示される任意のスイッチも単に概念的なものであり、これらの機能は、プログラム論理の動作（演算）を通じて遂行することも、専用の論理を通じて遂行することも、プログラムコントロールと専用論理の相互作用を通じて遂行することも、さらには手操作にて遂行することもでき、具体的にどのような技法を用いるかは具体的な背景に基づいて実装者によって選択できるものであるする。
【００４４】
クレーム中、指定される機能を遂行するための手段として表現される要素は、例えば、（ａ）その機能を遂行する回路要素の組合せ、あるいは（ｂ）その機能を遂行するための、あらゆる形式の、従ってファームウエア、マイクロコードその他を含むソフトウエアとそのソフトウエアを実行するための適当な回路の組合せを含む、その機能を遂行するためのあらゆるやり方を含むものと解されるべきである。これらクレームによって定義される発明は、様々な記載される手段によって提供される機能が、請求されるやりにて結合および一体化されるところにある。出願人は、従って、これら機能を提供できるあらゆる手段を（３５  Ｕ．Ｓ．Ｃ．１１２パラグラフ６において使用される用語の意味内で）ここに明示的に開示されるそれらと同等であるとみなすものである。
【図面の簡単な説明】
【図１】第一の従来の技術によるパケット損失回復技法を用いて符号化された符号化データパケットの系列の編成を示す図である。
【図２】第二の従来の技術によるパケット損失回復技法を用いて符号化された符号化データパケットの系列の編成を示す図である。
【図３】本発明の第一の実施例に従って構成された符号の一例としての零状態応答を示す図である。
【図４】本発明の第一の実施例に従って符号化された符号化データパケットの系列の編成を示す図である。
【図５】本発明の第二の実施例に従って符号化された符号化データパケットの系列の編成を示す図である。
【図６】本発明の第三の実施例に従って符号化された符号化データパケットの系列の編成を示す図である。
【図７】本発明の一般クラスの実施例の一つに従って符号化された符号化データパケットの系列の編成を示す図である。
【図１】
0004009895.tif 000021
【図２】
0004009895.tif 000022
【図３】
0004009895.tif 000023
【図４】
0004009895.tif 000024
【図５】
0004009895.tif 000025
【図６】
0004009895.tif 000026
【図７】
0004009895.tif 000027