高速な符号化方法および復号方法ならびに関連する装置
本発明の符号化方法は、第1符号を使用して入力ビットシーケンス(S0)のビットに適用される第1符号化ステップ(E1)と、前記第1符号から得られたビットをインターリーバでインターリーブするインターリーブステップ(E3)と、前記インターリーバから得られたビットに第2符号を使用して適用されて前記符号化ビットシーケンス(S)を生成するパリティ第2符号化ステップ(E4)とを含む。この符号化方法は、前記パリティ第2符号化ステップ(E4)が、所定数Δのビットがインターリーブされた後に開始され、前記所定数Δのビットが、前記インターリーブステップ(E3)の1つまたは複数のパラメータに依存する第1低数Δiのビットから、前記インターリーブステップ(E3)中に処理されるビットの総数に対応する第1高数Δsのビットまでの間にわたることを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル通信の分野に関し、さらに詳細には、たとえばLDPC(Low Density Parity Check)符号を使用する高ビットレートの符号化方法および復号方法ならびに関連する符号化装置および復号装置に関する。
【背景技術】
【０００２】
現在、最高のパフォーマンスを有するデジタル通信システムは、伝送されるデータがきわめて高パフォーマンスなチャネル符号化によって保護され、重み付き出力復号器によって反復的に復号されるシステムに基づいている。チャネル符号化またはエラー訂正符号化は、所与の法則に従って、伝送されるメッセージに冗長ビットを挿入することによって、伝送品質を向上させる。
【０００３】
デジタル伝送の分野において、特に伝送チャネルが無線チャネルである場合、これらの訂正符号の主要な機能は、伝送チャネルによってもたらされる伝送されるメッセージ内のあいまいさを排除することである。伝送で使用される符号化法則を把握するチャネル復号器は、その法則が受信時に依然として順守されているか確認する。順守されていない場合、チャネル復号器は、伝送エラーが存在することを検出する。
【０００４】
これらの符号によって実現するパフォーマンスの向上は、端末の電力消費を軽減したり、伝送される情報の量を増やしたりするために利用することができる。
【０００５】
近年、LDPC(Low Density Parity Check)エラー訂正符号を使用したチャネル符号化について、かなりの研究が行われてきた。
【０００６】
これらの符号は、たとえば、きわめて高いビットレートで機能する将来のワイヤレスアクセスネットワーク(WLAN)用のIEEE 802.11n通信プロトコルおよびIEEE 802.16e(WiMAXモバイル)プロトコルの標準化に関連して、標準化団体によって現在普及が進められている。
【０００７】
文書US 2005 0216819では、外部符号化、インターリーブ、パリティ符号化、および内部符号化を直列に連接することによって生成される直列ターボ風の符号を符号化および復号するための方法および装置について説明している。
【０００８】
Keith M. Chugg他による文書「A New Class of Turbo-like Codes with Universally Good Performance and High-Speed Decoding」(IEEE Milcom 2005、2005年10月)では、S-SCP(Systematic and Serial Concatenated Parity)符号と呼ばれる新しいクラスの符号と、具体的にはパリティチェック行列Hを以下の形式
【０００９】
【数１】
【００１０】
で記述できるF-LDPC(Flexible LDPC)符号とについて説明しており、この形式で、Iは、恒等行列であり、GおよびSは、2重対角行列であり、Vは、IEEE 802.11-04/0953r4標準化文書、K. Chugg他(802.11 Task Group N、2004年9月)による3つの行列の積である。この行列Vの形式によって、符号化および復号のビットレートに制約が課される。
【００１１】
図1Aおよび図1Bはそれぞれ、従来技術の符号器10および従来技術の復号器20の構造を表している。図1Aで、符号器10は、外部符号器3と、インターリーバ5と、直列並列変換器7と、パリティ符号器9と、内部符号器11とを含む。この符号器10によって生成される符号は、外部符号器3と、パリティ符号器9と、内部符号器11とによって連続的に生成される符号を直列に連接した結果である。
【００１２】
このアーキテクチャによれば、入力ビットシーケンスDeは、最初に外部符号器3によって完全に符号化され、次にインターリーバ5によってインターリーブされてインターリーブ済みデータシーケンスDiが形成される。直列並列変換器7は、インターリーブ済みデータシーケンスDiを並列化する。パリティ符号器9は次に、直列並列変換器7の出力から抽出されたJビットのmodulo-2加算を実施することによって、パリティ計算を実行する。パリティ符号器9の出力のデータシーケンスは次に、内部符号器11によって符号化される。
【００１３】
外部復号器15と、インターリーバ/デインターリーバ17と、パリティ復号器19と、内部復号器21とを含む復号器20の構造は、図1Bに示されている。
【００１４】
復号器20は、フレキシブルデータを反復的に復号する。符号の系統的部分に対応するフレキシブルデータが外部復号器15によって使用されて外部情報I1が取得され、この外部情報I1は次に、インターリーバ17によってインターリーブされて、パリティ復号器19によって使用可能な情報I2が生み出され、パリティ復号器19は、新しい外部情報I3を計算する。この情報I3と、符号の冗長部分に対応するフレキシブルデータI4とに基づいて、内部復号器21は、メッセージI5を計算し、このメッセージI5は次に、パリティ復号器19によって復号されて、デインターリーバ17に送信されるメッセージI6が形成される。メッセージI6がデインターリーバ17によってデインターリーブされてメッセージI7が作成されることによって、復号処理の反復が完了する。
【００１５】
符号器10(および復号器20)の主要な欠点は、その直列型アーキテクチャによってもたらされる遅延であり、その影響は、符号化(および復号)のビットレートが制限されることである。
【００１６】
図2Aおよび図2Bはそれぞれ、符号器10および復号器20によってそれぞれ実行される符号化処理および復号処理のさまざまなステップのスケジューリングを示している。
【００１７】
直列に連接された符号を使用する標準の符号化では、符号化装置10の各符号器、すなわち外部符号器3、パリティ符号器9または内部符号器11は、前の符号器がそのタスクを完了したことを条件にアクティブ化される。
【００１８】
図2Aは、符号器10によって実行される符号化処理を構成するタスク(縦軸)の時間(横軸)内でのスケジューリングをきわめて概略的に表しており、これらのタスクは、図1Aの外部符号器3、パリティ符号器9および内部符号器11によって連続的に実行される。
【００１９】
このようなスケジューリングでは、最初の符号化ステップE10は、外部符号器3によって時間T10にわたって実行される。ステップE10が完全に終了すると、パリティ符号器9が計算ステップE30を時間T30にわたって実行する。ステップE30が終了すると、内部符号器11によって時間T50にわたって実行される符号化ステップE50が続く。したがって符号器10の入力でのビットのシーケンスを符号化するために必要な時間は、総計T10 + T30 + T50と等価である。したがってこのタスクのスケジューリング方法では、符号器10の符号化ビットレートが制限される。
【００２０】
図2Bは、図1Bの復号器20によって処理の1回の反復中に実行される復号タスク(縦軸)の時間(横軸)内での分布を表している。
【００２１】
図2Bによれば、外部復号器15は、復号ステップE70を時間T70にわたって実行する。ステップE70が終了すると、パリティ復号器19が計算ステップE90を時間T90にわたって実行する。ステップE90が終了すると、内部復号器21がステップE110を時間T110にわたって実行する。パリティ復号器19は次に、ステップE130を時間T130にわたって実行する。したがって復号処理の1回の反復の継続時間Tは、上述のステップE70、E90、E110、E130のそれぞれの継続時間の総計と等価であり、すなわちT = T70 + T90 + T110 + T130である。
【００２２】
上述の符号化処理および復号処理のビットレートは、符号化処理および復号処理を構成するさまざまなタスクのスケジューリング方法によって制限される。
【００２３】
さらに、符号器10および復号器20のハードウェアリソースは、各処理機能が符号器10または復号器20内で連続的に使用されないという意味で、最適に利用されない。
【特許文献１】US 2005 0216819
【非特許文献１】Keith M. Chugg他、「A New Class of Turbo-like Codes with Universally Good Performance and High-Speed Decoding」、IEEE Milcom 2005、2005年10月
【非特許文献２】K. Chugg他、IEEE 802.11-04/0953r4標準化文書、802.11 Task Group N、2004年9月
【非特許文献３】L.R. Bahl他、「Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate」、IEEE Transactions on Information Theory、Volume IT-20、1974年3月、248〜287項
【発明の開示】
【発明が解決しようとする課題】
【００２４】
したがって本発明の主要な目的は、データシーケンスをきわめて高速にかつ従来技術の方法と比較してパフォーマンスを大きく損なうことなく符号化および復号する特性を有する符号化方法および復号方法を提供することによって、上述の欠点を排除することである。
【課題を解決するための手段】
【００２５】
この目的は、入力ビットシーケンスS0を符号化して符号化ビットシーケンスSを生み出す方法によって実現され、この方法は、
第1符号を使用して入力ビットシーケンスS0のビットに適用される第1符号化ステップと、
第1符号を使用して得られたビットをインターリーブ手段でインターリーブするインターリーブステップと、
所定数Δのビットの後に開始されるように、インターリーブ手段から得られたビットに第2符号を使用して適用されて符号化ビットシーケンスSを生成する、パリティステップと呼ばれる第2符号化ステップとを含む。この所定数Δのビットは、インターリーブステップの1つまたは複数のパラメータに依存する第1低数Δiのビットから、インターリーブステップ中に処理されるビットの総数に対応する第1高数Δsのビットまでの間である。
【００２６】
この種の符号化方法では、パリティ第2符号化ステップを、インターリーブステップが終了するのを待つことなく開始することができ、この第2符号化ステップは、インターリーブステップと並列で、Δビットの相対オフセットを伴って実施される。
【００２７】
したがってこの方法では、パリティ符号化ステップとインターリーブステップとが、これらのステップに関わるタスクの処理に関連するすべての機能およびメモリを重複させる必要なく並列化されることになり、これらのタスクが逐次的にスケジュールされるアーキテクチャとは対照的である。
【００２８】
したがってこの方法では、符号化方法の複雑さが軽減され、従来技術の方法のパフォーマンスを超えるかまたは同等のパフォーマンスが実現される。
【００２９】
本発明の別の特徴によれば、パリティ第2符号化ステップは、所定数Δ'のビットが第1符号化ステップによって符号化された後に開始される。この所定数Δ'のビットは、インターリーブステップの1つまたは複数のパラメータに依存する第2低数Δi'のビットから、第1符号化ステップ中に処理されるビットの総数に対応する第2高数Δs'のビットまでの間である。
【００３０】
したがってこの符号化方法では、パリティ第2符号化ステップを、インターリーブステップが終了するのを待つことなく開始することができ、この第2符号化ステップは、第1符号化ステップと並列で、Δ'ビットのオフセットを伴って実施される。
【００３１】
第1符号化ステップの開始とインターリーブステップの開始との間のオフセットは、調整可能であり、最小オフセットは、1ビットのオフセット(Δ' - Δ≧1)である。
【００３２】
インターリーブステップは、パリティ第2符号化ステップと結合して有利に実施することができる。
【００３３】
本発明の別の特徴によれば、インターリーブステップは、第1符号を使用して得られたi番目のビットを、インターリーブ済みビットシーケンスのπ(i)番目のビットと関連付けるビットレベルの第1インターリーブ関数πを含み、最初のkビットをインターリーブすることによって、インターリーブ済みビットシーケンスの少なくとも最初のmビットが供給されるようにする。
【００３４】
したがってこの特徴によって、インターリーブステップが終了するのを待つことなく、パリティ第2符号化ステップを開始することができる。
【００３５】
本発明の別の特徴によれば、インターリーブステップおよびパリティ第2符号化ステップは、複数の恒等サブ行列を以下の形式
【００３６】
【数２】
【００３７】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]は、Null行列であり、それ以外の場合、前記サブ行列I[c(i, j)]は、c(i, j)位置を巡回的に並べ替えた恒等行列である。
【００３８】
パリティチェック行例Vの準巡回形式によって、インターリーブステップとパリティ第2符号化ステップとを並列化することが可能となり、これらのステップは、本明細書で結合的に実施される。
【００３９】
本発明の別の特徴によれば、インターリーブステップは、第1符号を使用して得られた第1組のm1ビットのパケットを、インターリーブ済みビットシーケンスの第2組のJビットのパケットと関連付けるための第2インターリーブ関数λを含み、インターリーブ済みビットシーケンスのJビットの同じパケットに属するビットが、第1組のm1ビットのパケットの異なるパケットからもたらされるようにする。
【００４０】
このパケットレベルでのインターリーブによって、パリティ符号化ステップ中の同じメモリ領域への同時アクセスが防止される。したがってこの種のインターリーブは、メモリアクセスの競合に関わる遅延を最小化することによって、符号化ビットレートを向上させる。
【００４１】
本発明のある特徴によれば、パリティチェック行列Vの同じ行についての正の係数c(i, j)は相違する。
【００４２】
メモリアクセスの競合を防ぐために、行列Vに含まれる同じパリティ方程式に含まれるビットは、同じメモリ領域からもたらされないことが必要である。この条件は、j≠kの場合に行列Vの正の係数に適用される以下の算術関係によって表される。
∀c(i, j)≧0 and ∀c(i,k)≧0 : c(i, j)≠c(i,k)
【００４３】
言い換えると、この条件によって、同じメモリに同時に2回アクセスすることが不可能であることが保障され、したがってメモリアクセスの競合に関する遅延が軽減されることによって符号化ビットレートが向上する。
【００４４】
本発明のある特徴によれば、ビット数ΔおよびΔ'を決定する前記(1つまたは複数の)パラメータは、前記パリティチェック行列Vの正の係数c(i, j)の関数である。
【００４５】
本発明の別の特徴によれば、第1符号化ステップの第1符号は、第1の複数の独立した符号で構成される。
【００４６】
したがって第1符号自体を並列化して、第1符号化ステップの符号化ビットレートをさらに向上させることができる。
【００４７】
本発明の別の特徴によれば、符号化方法は、パリティ第2符号化ステップから得られたビットに適用される第3符号を使用する第3符号化ステップを含み、この第3符号化ステップは、パリティ第2符号化ステップから得られた1つまたは複数のビットを符号化することによって開始される。
【００４８】
したがって第3符号化ステップの第3符号は、たとえば、第1符号、第2符号、および第3符号を連接することによって形成される符号の訂正能力を高めるために、第1符号化ステップの第1符号に比べて追加の特性を有するように選択することができる。
【００４９】
第3符号化ステップの第3符号は、第2の複数の独立した符号で有利に構成される。
【００５０】
したがって第3符号自体を並列化して、第3符号化ステップの符号化ビットレートをさらに向上させることができる。
【００５１】
本発明はまた、転送される情報に対応する第1部分と、冗長データを含む第2部分とで構成されるデータシーケンスを含む受信デジタル信号を復号する方法であって、
前記第1部分のデータに適用される第1復号ステップと、
第1復号ステップから得られたデータをインターリーブ手段でインターリーブするインターリーブステップと、
インターリーブ手段から得られたデータに適用される、パリティステップと呼ばれる第2復号ステップと
を含む方法を対象とする。
【００５２】
パリティ第2復号ステップは、所定数Δのデータ項目がインターリーブされた後に有利に開始される。この所定数Δのデータ項目は、インターリーブステップの1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、インターリーブステップ中に処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間である。
【００５３】
したがってこの方法では、パリティ符号化ステップとインターリーブステップとが、それらのステップに関するタスクの処理に関連するすべての機能およびメモリを重複させる必要なく並列化される。
【００５４】
本発明の別の特徴によれば、パリティ第2復号ステップは、所定数Δ'のデータ項目が第1復号ステップで復号された後に開始される。この所定数Δ'のデータ項目は、インターリーブステップの1つまたは複数のパラメータに依存する第2低数Δi'のデータ項目から、第1復号ステップ中に処理されるデータ項目の総数に対応する第2高数Δs'のデータ項目までの間である。
【００５５】
本発明の別の特徴によれば、復号方法は、パリティ第2復号ステップから得られたデータを復号する第3復号ステップを含み、この第3復号ステップは、パリティ第2復号ステップから得られた1つまたは複数のデータ項目を復号することによって開始される。
【００５６】
本発明の別の特徴によれば、インターリーブステップは、パリティ第2復号ステップと結合して実施される。
【００５７】
本発明の別の特徴によれば、インターリーブステップおよび第2復号ステップは、複数の恒等サブ行列を以下の形式
【００５８】
【数３】
【００５９】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]は、Null行列であり、それ以外の場合、前記サブ行列I[c(i, j)]は、c(i, j)位置を巡回的に並べ替えた恒等行列である。
【００６０】
本発明の別の特徴によれば、パリティチェック行列Vの同じ列についての正の係数c(i, j)は相違する。
【００６１】
遅延を発生させ、復号ビットレートの低下に反映されるメモリアクセスの競合を防ぐには、1つの変数が行列Vに含まれるm2個のパリティ方程式のグループに2回以上含まれないことが必要であり、これは、以下の算術関係によって行列Vの正の係数に反映される。
∀c(i, j)≧0 and ∀c(i, j+ 1) : c(i, j)≠c(i + 1, j) ∀i,∀j
【００６２】
本発明の別の特徴によれば、データ項目の数ΔおよびΔ'を決定する(1つまたは複数の)パラメータは、パリティチェック行列Vの正の係数c(i, j)の関数である。
【００６３】
本発明はまた、入力ビットシーケンスS0を符号化して符号化ビットシーケンスSを生み出すための装置であって、
第1符号を使用して入力ビットシーケンスS0のビットを符号化するための第1符号化手段と、
第1符号化手段から得られたビットをインターリーブするためのインターリーブ手段と、
第2符号を使用して、インターリーブ手段から得られたビットを符号化して符号化ビットシーケンスSを生成するための、パリティ手段と呼ばれる第2符号化手段と
を含む装置を対象とする。
【００６４】
インターリーブ手段は、パリティ第2符号化手段が所定数Δのビットがインターリーブされた後に符号化ビットシーケンスSを開始するように有利になされる。この所定数Δのビットは、インターリーブ手段の1つまたは複数のパラメータに依存する第1低数Δiのビットから、インターリーブ手段によって処理されるビットの総数に対応する第1高数Δsまでの間である。
【００６５】
この符号化装置は、具体的には、上述の符号化方法を実施するように適合することができる。
【００６６】
本発明はさらに、伝送される情報に対応する第1部分と、冗長データを含む第2部分とで形成されるデータシーケンスを含む受信デジタル信号を復号するための装置を対象とする。この装置は、
第1部分のデータ項目を復号するための第1復号手段と、
第1復号手段から得られたビットをインターリーブするためのインターリーブ手段と、
インターリーブ手段から得られたビットを復号するための、パリティ手段と呼ばれる第2復号手段と
を含む。
【００６７】
インターリーブ手段は、パリティ第2復号手段が所定数Δのデータ項目がインターリーブされた後にパリティ復号を開始するようになされる。この所定数Δのデータ項目は、インターリーブステップの1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、インターリーブ手段によって処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間である。
【００６８】
この復号装置は、具体的には、上述の復号方法を実行するように適合することができる。
【００６９】
本発明はまた、通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに上述の符号化方法のステップを実行するためのプログラムコード命令を含むコンピュータプログラム製品を対象とする。
【００７０】
本発明はまた、通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに上述の復号方法のステップを実行するためのプログラムコード命令を含むコンピュータプログラム製品を対象とする。
【００７１】
本発明の他の特徴および利点は、本発明の非制限的な一実施形態を示す添付の図面を参照する以下の説明から明らかになる。
【発明を実施するための最良の形態】
【００７２】
図3は、入力ビットシーケンスS0を符号化して符号化ビットシーケンスSを生み出すための本発明の符号化方法のステップ(縦軸)の時間(横軸)内でのスケジューリングを示している。
【００７３】
この方法は、第1符号を使用して入力ビットシーケンスS0のビットに適用される第1符号化ステップE1を含む。この第1符号化ステップによって作成されるビットは、インターリーブステップE3中に、インターリーブ手段33(図6を参照されたい)によってインターリーブされる。
【００７４】
インターリーブ手段33からもたらされるビットは、パリティステップと呼ばれる第2符号化ステップE4で第2符号を使用して符号化されて、符号化ビットシーケンスSが生成される。
【００７５】
パリティ第2符号化ステップE4は、所定数Δのビットをインターリーブした後に有利に開始される。この所定数Δのビットは、インターリーブステップE3の1つまたは複数のパラメータに依存する第1低数Δiのビットから、インターリーブステップE3中に処理されるビットの総数に対応する第1高数Δsのビットまでの間である。
【００７６】
図4は、本発明の符号化方法の一実施形態を構成するさまざまなステップ(縦軸)の時間(横軸)内におけるインターリーブを例として示している。
【００７７】
この符号化方法は、入力ビットシーケンスS0を符号化して符号化ビットシーケンスS'を生み出す以下のステップを含む。
【００７８】
第1符号化ステップEl(外部符号化)は、第1符号化手段30(外部符号器30)により、外部符号パリティチェック行列G1によって定義される第1符号(外部符号)を使用して、入力ビットシーケンスS0のビットに適用される。
【００７９】
インターリーブステップE3では、インターリーブ手段33(「インターリーバ」33)が外部符号からのビットをビットレベルおよびパケットレベルでインターリーブする。
【００８０】
インターリーバ33からもたらされるビットは、パリティ第2符号化ステップE4中に、パリティ第2符号化手段32(パリティ符号器32)によって、パリティ符号パリティチェック行列V内で定義されるパリティ符号を使用して符号化される。
【００８１】
第3(内部)符号化ステップE6は、内部符号パリティチェック行列G2によって定義される符号を使用して、パリティ符号器32からもたらされるビットに適用されて、符号化ビットシーケンスS'が形成される。
【００８２】
パリティ符号化ステップE4は、所定数Δのビットに比例する時間の後、すなわち最初のΔビットをインターリーブした後に、有利に開始される。この所定数Δは、第1低数Δiのビットから、インターリーブステップE3中に処理されるビットの総数に対応する第1高数Δsのビットまでの間である。したがってパリティ符号化ステップE4は、インターリーブステップE3と並列で、Δビットのオフセットを伴って実施される。
【００８３】
インターリーブステップE3は、少なくとも1ビットのオフセットを伴って(Δ' - Δ≧1)、外部符号化ステップE1と並列で開始および実施される。同様に、内部符号化ステップE6は、少なくとも1ビットのオフセットを伴って、パリティ符号化ステップE4と並列で開始および実施される。
【００８４】
好ましい実施形態において、当該の符号は、以下の形式
【００８５】
【数４】
【００８６】
のパリティチェック行列Hから構築されるLDPC(Low Density Parity Check)符号であり、この形式で、
G1は、外部符号器30(図6を参照されたい)に関連する外部符号パリティチェック行列であり、
Vは、パリティ符号およびインターリーブ関数を含む符号のパリティチェック行列であり、
G2は、内部符号器34(図6を参照されたい)に関連する内部符号パリティチェック行列である。
【００８７】
外部符号は、行列G1に基づいて定義され、この行列は、以下の形式
【００８８】
【数５】
【００８９】
のK×Kの正方行列であり、この形式で、Iは、z×zの恒等行列であり、Ipは、p位置を右または左に巡回的に並べ替えたz×zの恒等行列である。
【００９０】
オプションで、外部符号が複数の独立した符号で構成されるように数「p」の値を設定することによって外部符号化/復号ステップを並列化し、それによって符号化/復号の速度を(外部符号化/復号のレベルで)向上させることが可能である。
【００９１】
この実施例で、p = 0の場合、外部符号は、「z」個の独立した符号で構成される。それ以外の場合(すなわち、p≠0の場合)、外部符号は、「z/b」個の独立した符号で構成され、ここでbは、以下であるような最小の正のゼロ以外の整数である。
(b.p) modulo z = 0 (4)
【００９２】
たとえば、外部符号は、並列で機能する複数の独立した巡回畳み込み符号で構成し、それによって符号化ビットレートを向上させることができる。
【００９３】
内部符号は、行列G2に基づいて定義され、この行列は、以下の形式
【００９４】
【数６】
【００９５】
のM×Mの正方行列であり、この形式で、Iは、z×zの恒等行列であり、Ieは、「e」位置を非巡回的に右または左に並べ替えたz×zの恒等行列である。
【００９６】
外部符号化と同様に、オプションで、内部符号が複数の独立した符号で構成されるように数「e」の値を設定することによって内部符号化ステップを並列化し、それによって符号化速度を内部符号化のレベルで向上させることができる。
【００９７】
この実施例で、e = 0の場合、内部符号は、「z」個の独立した符号で構成される。それ以外の場合(すなわち、e≠0の場合)、内部符号は、数「e」と等価である数の独立した符号で構成される。
【００９８】
たとえば、内部符号は、並列で機能する複数の独立した再帰的な巡回畳み込み符号で構成し、それによって符号化ビットレートを向上させることができる。
【００９９】
行列Vは、複数のNull行列および/または巡回的に並べ替えた恒等行列を含む準巡回M×K行列であり、この行列Vは、以下の関係
【０１００】
【数７】
【０１０１】
によって定義され、ここで、
m1は、K = m1×z(7)であるような厳密な正の整数であり、
m2は、M = m2×z(8)であるような厳密な正の整数であり、
I[c( i, j)]は、z×zのNull行列であるか、またはz×zの巡回並べ替え恒等行列であり、c(i, j) < 0の場合、I[c(i, j)]は、Null行列であり、それ以外の場合、I[c(i, j)]は、c(i, j)位置を右または左に巡回的に並べ替えた恒等行列である。
【０１０２】
上述の行列Vの形式は、本発明によるパリティ符号とビットレベルおよびパケットレベルでのインターリーブとを含む。
【０１０３】
図5Aおよび図5Bはそれぞれ、第1関数πによるビットレベルでのインターリーブと、第2関数λによるパケットレベルでのインターリーブとを示している。
【０１０４】
図5Aでは、ビットの第1ブロックB1に属する、外部符号器の出力でのビットが、第1インターリーブ関数πを使用してインターリーブされて、インターリーブ済みビットの第2ブロックB2が形成される。
【０１０５】
この第1インターリーブ関数πは、ビットの第1ブロックB1に属するインデックス「i」の任意のビットを、インターリーブ済みビットのブロックB2のインデックスπ(i)のビットと関連付け、ビットの第1ブロックB1の最初のkビットをインターリーブすることによって、インターリーブ済みビットの第2ブロックB2の少なくとも最初のmビットが提供されるようにする。したがって、この実施例では、処理されるビットの第1ブロックB1のインデックスk + 1である次のビットは、インターリーブ済みビットの第2ブロックB2内のインデックスπ(k + 1)の位置になり、π(k + 1) > mとなる。
【０１０６】
したがって、パリティ符号化がJ = mビットのブロックによって実施される場合、このインターリーブ関数は、インターリーブ手段33からもたらされる最初のJビットの符号化を、インターリーブステップE3が終了するのを待たずに開始することができるということを意味する。上述の従来技術とは対照的に、パリティ符号化ステップE4を開始できるようになるために、外部符号器の出力時のすべてのビットがインターリーブ手段33によってインターリーブされるのを待つ必要はない。
【０１０７】
図5Bでは、外部符号器30の出力でビットの第1ブロックB1に属するビットは、第2インターリーブ関数λを使用してインターリーブされ、この第2インターリーブ関数λは、ビットの第1ブロックB1に属する第1組のm1ビットのパケット(P1、P2、P3、P4、P5)を、第2組のJインターリーブ済みビットのパケット(P10、P20、P30、P40、P50、P60)と関連付け、Jインターリーブ済みビットの同じパケットP30に属するビットのすべてが、第1組のm1ビットのパケット(P1、P2、P3、P4、P5)に属する別々のパケットからもたらされるようにする。図5Bの実施例では、パケットP30は、5つのそれぞれのパケット(P1、P2、P3、P4、P5)からもたらされる5つのビット(b1、b2、b3、b4、b5)で構成される。
【０１０８】
好ましい実施形態では、上述の行列Vの形式によって、第1関数πおよび第2関数λにそれぞれ従ってビットレベルおよびパケットレベルでインターリーブを行うことが可能となる。したがってJインターリーブ済みビットのi番目のパケットに属するインデックス「π(i)」の各ビットは、m1ビットのλ-1(i, 1)番目のパケットに属する(i)番目のビットと関連する。
【０１０９】
本発明の符号化(および復号)方法では、パリティ符号化(および復号)ステップおよび外部符号化(および復号)ステップの並列化のパラメータは、所定数のビットに対応する所定のメトリックΔによって決定される。
【０１１０】
この数Δの値は、行列Vの厳密に正である係数c(i, j)から、以下の態様で計算される。
Φ≡{ci}を、行列Vの正およびゼロ以外の係数c(i, j)を昇順で並べた集合であるとする。「d」を、x≧yである2つの点xおよびyの間の距離を計算するための関数であり、d(x, y) = (x - y)によって定義されるとする。この数Δの値は、以下の関係
Δ = Max(Δ1,c0 + z - ccard(Φ)-1) (9)
を使用して計算され、この関係において、
card(Φ)は、集合Φの要素の数を表し、
c0は、パリティチェック行列Vの最小の正のゼロ以外の係数c(i, j)であり、
zは、パリティチェック行列Vに含まれる恒等サブ行列の次元であり、
Δ1は、集合Φに属する任意の2つの隣接する要素(ciおよびci+1)の間の最大距離であり、この距離は、以下の関係
Δ1 = Max({d(ci+1, ci)}i∈[0, card(Φ)-1]) (10)
によって定義される。
【０１１１】
図6は、第1(外部)符号器30(第1符号化手段)と、インターリーバ33(インターリーブ手段)を含むパリティ符号器32(第2符号化手段)と、内部符号器34(第3符号化手段)と、外部符号器30およびパリティ符号器32の間の第1メモリ手段36と、パリティ符号器32および内部符号器34の間の第2メモリ手段38とを含む本発明の符号化装置100の一実施形態を示している。
【０１１２】
異なる実施形態では、インターリーバ33およびパリティ符号器32は別々にすることができるという点に留意されたい。
【０１１３】
第1メモリ36は、それぞれm1ビットのストレージ容量を備える「z」個の第1メモリバンク(ME1〜MEz)の第1組を含む。
【０１１４】
第2メモリ38は、それぞれm2ビットのストレージ容量を備える少なくとも2つの第2メモリバンク(MI1およびMI2)を含む。
【０１１５】
入力ビットブロックB0は、本発明の符号化装置100によって符号化されて、符号化ビットシーケンスSが生み出される。
【０１１６】
外部符号器30は、入力ビットブロックB0の符号化を開始して、外部符号器30の出力における最初の数ビットを生成し、これらのビットは、メモリ36の第1メモリバンク(ME1〜MEZ)内に、自然な順序およびm1ビットのパケット単位で直接格納される。
【０１１７】
所定数Δに比例する時間の後、パリティ符号器32は、第1組のメモリバンク(ME1〜MEZ)のサブセットの各メモリバンク内のビットを読み取り、行列V内で定義されるパリティ行によるmodulo-2加法演算によってこれらのビットを可算する(行列Vの各行は、パリティ方程式を定義する)。
【０１１８】
たとえば、パリティ符号器32は、行列Vのm2個の行に含まれるm2個のパリティ方程式を処理して、パリティ符号器32の出力でm2ビットを生成することができる。それらのm2ビットは、メモリ38の第2組のメモリバンク(MI1およびMI2)のメモリバンクMI1内に直接格納される。
【０１１９】
m2ビットがパリティ符号器32の出力でメモリバンク(MI1、MI2)に書き込まれた直後、内部符号器34は、それらのm2ビットを読み取り、それらのビットの符号化を、内部符号パリティチェック行列G2内に含まれる内部符号を使用して事実上即時に開始することができる。
【０１２０】
内部符号化操作がm2ビットに対してm2ビットが第2メモリバンク(この実施例ではMI1)に書き込まれた直後に実施されると仮定すると、ハードウェアリソースの最適な利用を可能にするには、第2メモリ38に2つのメモリブロック(MI1およびMI2)だけが含まれていれば十分であり、これら2つのメモリバンクのそれぞれは、書き込みモードまたは読み取りモードで交互に機能する。
【０１２１】
実際には、内部符号器がそのタスクをパリティ符号器と並列で開始できるためには、パリティ符号を1ビット処理すれば十分である。
【０１２２】
図7は、復号方法の特定の一実施形態を構成するさまざまなステップ(縦軸)の時間(横軸)内におけるスケジューリングのきわめて概略的な図である。
【０１２３】
この復号方法では、伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで構成されるデータシーケンスを含む受信デジタル信号を復号する。
【０１２４】
この方法では、第1(外部)復号ステップE100は、第1部分Dのデータに適用される。インターリーブ手段43(インターリーバ43)によって実施されるインターリーブステップE300は、第1(外部)復号ステップE100からもたらされるデータをインターリーブする。パリティ第2復号ステップE400は、インターリーバ43からもたらされるデータに適用される。第3(内部)復号ステップE600は、パリティ復号ステップE400からもたらされるデータに適用される。
【０１２５】
パリティ復号ステップE400は、所定数Δのデータビットをインターリーブした後に有利に開始される。この所定数Δのデータビットは、インターリーブステップE300の1つまたは複数のパラメータに依存する第1低数Δiのデータビットから、インターリーブステップE300中に処理されるデータビットの総数に対応する第1高数Δsのデータビットまでの間である。
【０１２６】
図8は、伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで構成されるデータシーケンスを含む受信デジタル信号を復号するための本発明の復号装置200の実施形態を示している。
【０１２７】
本発明の復号装置200は、外部復号器40(第1復号手段40)と、インターリーバ43(インターリーブ手段43)を含むパリティ復号器42(パリティ第2復号手段42)と、内部復号器44(第2復号手段44)と、外部復号器40および内部復号器44の入力側にある第1メモリモジュール46と、外部復号器40およびパリティ復号器42の間にある第2メモリモジュール48と、パリティ復号器42および内部復号器44の間にある第3メモリモジュール50とを含む。
【０１２８】
異なる実施形態では、インターリーバ43およびパリティ復号器42は別々にすることができるという点に留意されたい。
【０１２９】
インターリーバ43は、パリティ復号器42が所定数Δのデータビットがインターリーブされた後にパリティ復号ステップE400を開始するようになされる。この所定数Δのデータビットは、インターリーバ43の1つまたは複数のパラメータに依存する第1低数Δiのデータビットから、インターリーバ43によって処理されるデータビットの総数に対応する第1高数Δsのデータビットまでの間である。
【０１３０】
「m1×z」のフレキシブル値を含む受信デジタル信号を格納するための第1メモリモジュール46は、それぞれm1ビットのストレージ容量を備える「z」個の第1メモリバンク(M1〜Mz)を含む。
【０１３１】
外部復号器40およびパリティ復号器42の間で伝送中のデータを格納するための第2メモリモジュール48は、それぞれm1ビットのストレージ容量を備える「z」個の第2メモリバンク(ME1〜MEz)を含む。
【０１３２】
パリティ復号器42および内部復号器44の間で伝送中のデータを格納するための第3メモリモジュール50は、それぞれm2ビットのストレージ容量を備える「z」個の第3メモリバンク(MI1〜Mlz)を含む。
【０１３３】
メモリ46、48および50をそれぞれの複数のメモリバンク(M1〜Mz)、(ME1〜MEZ)、(MI1〜MIZ)に分割することによって、同じメモリへの同時アクセスが最小化されるか、場合によっては排除される。
【０１３４】
N個のフレキシブル値のフレームが、反復的に復号される。内部符号および外部符号のフレキシブルな復号は、L.R. Bahl他によって「Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate」(IEEE Transactions on Information Theory、Volume IT-20、1974年3月、248〜287項)という名称の文書で説明されているように、Bahl-Cocke-Jelinek-Ravivアルゴリズム、Forward-Backwardアルゴリズムまたは軟出力ビタビアルゴリズムなど、フレキシブル出力畳み込み符号を復号するための標準的な技法を使用して実施することができるという点に留意されたい。
【０１３５】
この方法の初期化ステップは、第1メモリモジュール46の最初の「z」個のメモリバンク(M1〜Mz)内に、自然な順序およびm1個のフレキシブル値のパケット単位で、受信信号に含まれるN = m1×z個のデータ項目を格納する段階に存する。
【０１３６】
言い換えると、受信信号の最初のm1個のフレキシブル値は、最初のメモリバンクM1内に格納され、次のm1個のフレキシブル値は、次のメモリバンクM2に格納される、というようになる。
【０１３７】
この方法は、各反復で以下のステップを含む。
【０１３８】
外部復号器40は、第1メモリモジュール46に属するメモリバンクMjに含まれるm1データビット(またはm1個のフレキシブル値)を含むインデックスjの窓上で復号を実施して第1外部データを生成し、このデータは、第2メモリモジュール48に属するメモリバンクMEjに格納される。
【０１３９】
Δ個の窓を復号した後、パリティ復号器42は、外部復号器40と並列で、かつ競合することなく機能することができる。
【０１４０】
行列V内で定義されるパリティ方程式は、外部符号器の出力で供給される変数またはデータを使用して、順番にかつm2個の方程式のグループで解決される。1つの窓の復号中に行列Vのm2個のパリティ方程式で使用されるこれらの変数のそれぞれの値は、異なるメモリバンク(ME1〜MEZ)内で読み取られる。インデックスiの各窓について、m2個の方程式のi番目のグループのm2個の方程式が、i、i + z、i + 2×z、...、i + m2×z(iは、1〜zの範囲内)の順序で解決される。
【０１４１】
m2個の方程式のi番目のグループを復号した結果は、第3メモリモジュール50に属するi番目のメモリバンクMIiに格納される。たとえば、m2個のパリティ方程式の2番目のグループを解決することによってもたらされるm2データビットは、2番目のメモリバンクMI2に格納される。
【０１４２】
パリティ復号器がインデックスiの窓上でm2個の方程式の最初のグループを解決した直後、内部復号器は、この窓上でそのタスクである復号を開始することができる。インデックスiの窓を復号することによってもたらされる外部情報は、第3メモリモジュール50に属するメモリバンクMIi内に格納される。
【０１４３】
内部復号器によるΔ個の窓の復号に続いて、行列V内で定義されるパリティ方程式に含まれる変数が更新される。
【０１４４】
パリティ復号ステップ中に同じメモリバンクへのアクセスが競合するのを防ぐには、1つの変数が、m2個のパリティ方程式の1つのグループ内に2回以上含まれていてはならない。このルールは、行列Vの同じ列についてのすべての正の係数c(i, j)は相違するという条件内に反映されている。
【０１４５】
本発明はまた、コンピュータ内で実行されたときに本発明の符号化方法および/または復号方法のステップを実行するためのプログラムコード命令を含む、通信ネットワークからダウンロード可能なコンピュータプログラムを対象とする。このコンピュータプログラムは、コンピュータ読み取り可能メディア上に格納することができる。
【０１４６】
このプログラムは、任意のプログラミング言語を使用することができ、ソースコード、オブジェクトコード、または部分コンパイル形式などのソースコードおよびオブジェクトコードの中間コードの形式か、あるいは任意の他の望ましい形式を取ることができる。
【０１４７】
本発明はまた、上述のコンピュータプログラムの命令を含むコンピュータ読み取り可能情報メディアを対象とする。
【０１４８】
この情報メディアは、プログラムを格納する能力を有する任意のエンティティまたは装置とすることができる。たとえば、このメディアは、たとえばCD ROMや超小型電子回路ROMといったROMや、たとえばディスケット(フロッピー（登録商標）ディスク)やハードディスクといった磁気ストレージ手段などのストレージ手段を含むことができる。
【０１４９】
さらに、情報メディアは、無線または他の手段によって電気ケーブルまたは光学ケーブルを介してルーティングできる電気信号または光学信号などの伝送可能なメディアとすることができる。本発明のプログラムは、特にインターネット型ネットワークを通じてダウンロードすることができる。
【０１５０】
あるいは情報メディアは、プログラムが組み込まれる集積回路とすることができ、この回路は、当該の方法を実行するように、またはその方法の実行で使用されるように適合される。
【０１５１】
符号化装置は、図9に示すように、信号Bによって制御される中央処理装置60、メモリ62、入力装置64および出力装置66を通常含むデータ処理システムFによって実装することができるという点に留意されたい。これらすべての要素は、データバス68によって相互接続される。
【０１５２】
さらに、このデータ処理システムは、本発明の符号化方法を実行するための命令を含むコンピュータプログラムを実行するために使用することができる。
【０１５３】
復号装置も、図9のデータ処理システムと同様のデータ処理システムによって実装することができるという点に留意されたい。
【０１５４】
さらに、このデータ処理システムは、本発明の復号方法を実行するための命令を含むコンピュータプログラムを実行するために使用することができる。
【図面の簡単な説明】
【０１５５】
【図１Ａ】従来技術の符号器を示す図である。
【図１Ｂ】従来技術の復号器を示す図である。
【図２Ａ】従来技術の符号化ステップのスケジューリングを示す図である。
【図２Ｂ】従来技術の復号ステップのスケジューリングを示す図である。
【図３】本発明の符号化ステップのスケジューリングを示す図である。
【図４】本発明の一実施形態の符号化ステップのスケジューリングを示す図である。
【図５Ａ】本発明によるビットレベルでのインターリーブを示す図である。
【図５Ｂ】本発明によるパケットレベルでのインターリーブを示す図である。
【図６】本発明の符号化装置を示す図である。
【図７】本発明の一実施形態の復号ステップのスケジューリングを示す図である。
【図８】本発明の復号装置を示す図である。
【図９】本発明の符号化装置および/または復号装置を使用するデータ処理システムを示す図である。
【符号の説明】
【０１５６】
3 外部符号器
5 インターリーバ
7 直列並列変換器
9 パリティ符号器
10 従来技術の符号器
11 内部符号器
15 外部復号器
17 インターリーバ/デインターリーバ
19 パリティ復号器
20 従来技術の復号器
21 内部復号器
30 第1符号化手段
32 第2符号化手段
33 インターリーブ手段
34 内部符号器
36 第1メモリ手段
38 第2メモリ手段
40 外部復号器
42 パリティ復号器
43 インターリーバ
44 内部復号器
46 第1メモリモジュール
48 第2メモリモジュール
50 第3メモリモジュール
60 中央処理装置
62 メモリ
64 入力装置
66 出力装置
68 データバス
100 本発明の符号化装置
200 本発明の復号装置
De 入力ビットシーケンス
Di インターリーブ済みデータシーケンス
I1 外部情報
I2 情報
I3 新しい外部情報
I4 フレキシブルデータ
I5 メッセージ
I6 メッセージ
I7 メッセージ
E10 符号化ステップ
E30 計算ステップ
E50 符号化ステップ
E70 復号ステップ
E90 計算ステップ
E110 ステップ
E130 ステップ
T10 時間
T30 時間
T50 時間
T70 時間
T90 時間
T110 時間
T130 時間
Δ 所定数
Δi 第1低数
Δs 第1高数
Δ' 所定数
Δi' 第1低数
Δs' 第1高数
S0 入力ビットシーケンス
S 符号化ビットシーケンス
E1 第1符号化ステップ
E3 インターリーブステップ
E4 第2符号化ステップ
E6 第3符号化ステップ
B1 ビットの第1ブロック
B2 インターリーブ済みビットの第2ブロック
P1 パケット
P2 パケット
P3 パケット
P4 パケット
P5 パケット
P10 パケット
P20 パケット
P30 パケット
P40 パケット
P50 パケット
P60 パケット
b1 ビット
b2 ビット
b3 ビット
b4 ビット
b5 ビット
ME1〜MEz 第1メモリバンク
MI1 第2メモリバンク
MI2 第2メモリバンク
E100 第1(外部)復号ステップ
E300 インターリーブステップ
E400 パリティ第2復号ステップ
E600 第3(内部)復号ステップ
M1〜Mz 第1メモリバンク
ME1〜MEz 第2メモリバンク
MI1〜MIz 第3メモリバンク
B 信号
F データ処理システム
【技術分野】
【０００１】
本発明は、デジタル通信の分野に関し、さらに詳細には、たとえばLDPC(Low Density Parity Check)符号を使用する高ビットレートの符号化方法および復号方法ならびに関連する符号化装置および復号装置に関する。
【背景技術】
【０００２】
現在、最高のパフォーマンスを有するデジタル通信システムは、伝送されるデータがきわめて高パフォーマンスなチャネル符号化によって保護され、重み付き出力復号器によって反復的に復号されるシステムに基づいている。チャネル符号化またはエラー訂正符号化は、所与の法則に従って、伝送されるメッセージに冗長ビットを挿入することによって、伝送品質を向上させる。
【０００３】
デジタル伝送の分野において、特に伝送チャネルが無線チャネルである場合、これらの訂正符号の主要な機能は、伝送チャネルによってもたらされる伝送されるメッセージ内のあいまいさを排除することである。伝送で使用される符号化法則を把握するチャネル復号器は、その法則が受信時に依然として順守されているか確認する。順守されていない場合、チャネル復号器は、伝送エラーが存在することを検出する。
【０００４】
これらの符号によって実現するパフォーマンスの向上は、端末の電力消費を軽減したり、伝送される情報の量を増やしたりするために利用することができる。
【０００５】
近年、LDPC(Low Density Parity Check)エラー訂正符号を使用したチャネル符号化について、かなりの研究が行われてきた。
【０００６】
これらの符号は、たとえば、きわめて高いビットレートで機能する将来のワイヤレスアクセスネットワーク(WLAN)用のIEEE 802.11n通信プロトコルおよびIEEE 802.16e(WiMAXモバイル)プロトコルの標準化に関連して、標準化団体によって現在普及が進められている。
【０００７】
文書US 2005 0216819では、外部符号化、インターリーブ、パリティ符号化、および内部符号化を直列に連接することによって生成される直列ターボ風の符号を符号化および復号するための方法および装置について説明している。
【０００８】
Keith M. Chugg他による文書「A New Class of Turbo-like Codes with Universally Good Performance and High-Speed Decoding」(IEEE Milcom 2005、2005年10月)では、S-SCP(Systematic and Serial Concatenated Parity)符号と呼ばれる新しいクラスの符号と、具体的にはパリティチェック行列Hを以下の形式
【０００９】
【数１】
【００１０】
で記述できるF-LDPC(Flexible LDPC)符号とについて説明しており、この形式で、Iは、恒等行列であり、GおよびSは、2重対角行列であり、Vは、IEEE 802.11-04/0953r4標準化文書、K. Chugg他(802.11 Task Group N、2004年9月)による3つの行列の積である。この行列Vの形式によって、符号化および復号のビットレートに制約が課される。
【００１１】
図1Aおよび図1Bはそれぞれ、従来技術の符号器10および従来技術の復号器20の構造を表している。図1Aで、符号器10は、外部符号器3と、インターリーバ5と、直列並列変換器7と、パリティ符号器9と、内部符号器11とを含む。この符号器10によって生成される符号は、外部符号器3と、パリティ符号器9と、内部符号器11とによって連続的に生成される符号を直列に連接した結果である。
【００１２】
このアーキテクチャによれば、入力ビットシーケンスDeは、最初に外部符号器3によって完全に符号化され、次にインターリーバ5によってインターリーブされてインターリーブ済みデータシーケンスDiが形成される。直列並列変換器7は、インターリーブ済みデータシーケンスDiを並列化する。パリティ符号器9は次に、直列並列変換器7の出力から抽出されたJビットのmodulo-2加算を実施することによって、パリティ計算を実行する。パリティ符号器9の出力のデータシーケンスは次に、内部符号器11によって符号化される。
【００１３】
外部復号器15と、インターリーバ/デインターリーバ17と、パリティ復号器19と、内部復号器21とを含む復号器20の構造は、図1Bに示されている。
【００１４】
復号器20は、フレキシブルデータを反復的に復号する。符号の系統的部分に対応するフレキシブルデータが外部復号器15によって使用されて外部情報I1が取得され、この外部情報I1は次に、インターリーバ17によってインターリーブされて、パリティ復号器19によって使用可能な情報I2が生み出され、パリティ復号器19は、新しい外部情報I3を計算する。この情報I3と、符号の冗長部分に対応するフレキシブルデータI4とに基づいて、内部復号器21は、メッセージI5を計算し、このメッセージI5は次に、パリティ復号器19によって復号されて、デインターリーバ17に送信されるメッセージI6が形成される。メッセージI6がデインターリーバ17によってデインターリーブされてメッセージI7が作成されることによって、復号処理の反復が完了する。
【００１５】
符号器10(および復号器20)の主要な欠点は、その直列型アーキテクチャによってもたらされる遅延であり、その影響は、符号化(および復号)のビットレートが制限されることである。
【００１６】
図2Aおよび図2Bはそれぞれ、符号器10および復号器20によってそれぞれ実行される符号化処理および復号処理のさまざまなステップのスケジューリングを示している。
【００１７】
直列に連接された符号を使用する標準の符号化では、符号化装置10の各符号器、すなわち外部符号器3、パリティ符号器9または内部符号器11は、前の符号器がそのタスクを完了したことを条件にアクティブ化される。
【００１８】
図2Aは、符号器10によって実行される符号化処理を構成するタスク(縦軸)の時間(横軸)内でのスケジューリングをきわめて概略的に表しており、これらのタスクは、図1Aの外部符号器3、パリティ符号器9および内部符号器11によって連続的に実行される。
【００１９】
このようなスケジューリングでは、最初の符号化ステップE10は、外部符号器3によって時間T10にわたって実行される。ステップE10が完全に終了すると、パリティ符号器9が計算ステップE30を時間T30にわたって実行する。ステップE30が終了すると、内部符号器11によって時間T50にわたって実行される符号化ステップE50が続く。したがって符号器10の入力でのビットのシーケンスを符号化するために必要な時間は、総計T10 + T30 + T50と等価である。したがってこのタスクのスケジューリング方法では、符号器10の符号化ビットレートが制限される。
【００２０】
図2Bは、図1Bの復号器20によって処理の1回の反復中に実行される復号タスク(縦軸)の時間(横軸)内での分布を表している。
【００２１】
図2Bによれば、外部復号器15は、復号ステップE70を時間T70にわたって実行する。ステップE70が終了すると、パリティ復号器19が計算ステップE90を時間T90にわたって実行する。ステップE90が終了すると、内部復号器21がステップE110を時間T110にわたって実行する。パリティ復号器19は次に、ステップE130を時間T130にわたって実行する。したがって復号処理の1回の反復の継続時間Tは、上述のステップE70、E90、E110、E130のそれぞれの継続時間の総計と等価であり、すなわちT = T70 + T90 + T110 + T130である。
【００２２】
上述の符号化処理および復号処理のビットレートは、符号化処理および復号処理を構成するさまざまなタスクのスケジューリング方法によって制限される。
【００２３】
さらに、符号器10および復号器20のハードウェアリソースは、各処理機能が符号器10または復号器20内で連続的に使用されないという意味で、最適に利用されない。
【特許文献１】US 2005 0216819
【非特許文献１】Keith M. Chugg他、「A New Class of Turbo-like Codes with Universally Good Performance and High-Speed Decoding」、IEEE Milcom 2005、2005年10月
【非特許文献２】K. Chugg他、IEEE 802.11-04/0953r4標準化文書、802.11 Task Group N、2004年9月
【非特許文献３】L.R. Bahl他、「Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate」、IEEE Transactions on Information Theory、Volume IT-20、1974年3月、248〜287項
【発明の開示】
【発明が解決しようとする課題】
【００２４】
したがって本発明の主要な目的は、データシーケンスをきわめて高速にかつ従来技術の方法と比較してパフォーマンスを大きく損なうことなく符号化および復号する特性を有する符号化方法および復号方法を提供することによって、上述の欠点を排除することである。
【課題を解決するための手段】
【００２５】
この目的は、入力ビットシーケンスS0を符号化して符号化ビットシーケンスSを生み出す方法によって実現され、この方法は、
第1符号を使用して入力ビットシーケンスS0のビットに適用される第1符号化ステップと、
第1符号を使用して得られたビットをインターリーブ手段でインターリーブするインターリーブステップと、
所定数Δのビットの後に開始されるように、インターリーブ手段から得られたビットに第2符号を使用して適用されて符号化ビットシーケンスSを生成する、パリティステップと呼ばれる第2符号化ステップとを含む。この所定数Δのビットは、インターリーブステップの1つまたは複数のパラメータに依存する第1低数Δiのビットから、インターリーブステップ中に処理されるビットの総数に対応する第1高数Δsのビットまでの間である。
【００２６】
この種の符号化方法では、パリティ第2符号化ステップを、インターリーブステップが終了するのを待つことなく開始することができ、この第2符号化ステップは、インターリーブステップと並列で、Δビットの相対オフセットを伴って実施される。
【００２７】
したがってこの方法では、パリティ符号化ステップとインターリーブステップとが、これらのステップに関わるタスクの処理に関連するすべての機能およびメモリを重複させる必要なく並列化されることになり、これらのタスクが逐次的にスケジュールされるアーキテクチャとは対照的である。
【００２８】
したがってこの方法では、符号化方法の複雑さが軽減され、従来技術の方法のパフォーマンスを超えるかまたは同等のパフォーマンスが実現される。
【００２９】
本発明の別の特徴によれば、パリティ第2符号化ステップは、所定数Δ'のビットが第1符号化ステップによって符号化された後に開始される。この所定数Δ'のビットは、インターリーブステップの1つまたは複数のパラメータに依存する第2低数Δi'のビットから、第1符号化ステップ中に処理されるビットの総数に対応する第2高数Δs'のビットまでの間である。
【００３０】
したがってこの符号化方法では、パリティ第2符号化ステップを、インターリーブステップが終了するのを待つことなく開始することができ、この第2符号化ステップは、第1符号化ステップと並列で、Δ'ビットのオフセットを伴って実施される。
【００３１】
第1符号化ステップの開始とインターリーブステップの開始との間のオフセットは、調整可能であり、最小オフセットは、1ビットのオフセット(Δ' - Δ≧1)である。
【００３２】
インターリーブステップは、パリティ第2符号化ステップと結合して有利に実施することができる。
【００３３】
本発明の別の特徴によれば、インターリーブステップは、第1符号を使用して得られたi番目のビットを、インターリーブ済みビットシーケンスのπ(i)番目のビットと関連付けるビットレベルの第1インターリーブ関数πを含み、最初のkビットをインターリーブすることによって、インターリーブ済みビットシーケンスの少なくとも最初のmビットが供給されるようにする。
【００３４】
したがってこの特徴によって、インターリーブステップが終了するのを待つことなく、パリティ第2符号化ステップを開始することができる。
【００３５】
本発明の別の特徴によれば、インターリーブステップおよびパリティ第2符号化ステップは、複数の恒等サブ行列を以下の形式
【００３６】
【数２】
【００３７】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]は、Null行列であり、それ以外の場合、前記サブ行列I[c(i, j)]は、c(i, j)位置を巡回的に並べ替えた恒等行列である。
【００３８】
パリティチェック行例Vの準巡回形式によって、インターリーブステップとパリティ第2符号化ステップとを並列化することが可能となり、これらのステップは、本明細書で結合的に実施される。
【００３９】
本発明の別の特徴によれば、インターリーブステップは、第1符号を使用して得られた第1組のm1ビットのパケットを、インターリーブ済みビットシーケンスの第2組のJビットのパケットと関連付けるための第2インターリーブ関数λを含み、インターリーブ済みビットシーケンスのJビットの同じパケットに属するビットが、第1組のm1ビットのパケットの異なるパケットからもたらされるようにする。
【００４０】
このパケットレベルでのインターリーブによって、パリティ符号化ステップ中の同じメモリ領域への同時アクセスが防止される。したがってこの種のインターリーブは、メモリアクセスの競合に関わる遅延を最小化することによって、符号化ビットレートを向上させる。
【００４１】
本発明のある特徴によれば、パリティチェック行列Vの同じ行についての正の係数c(i, j)は相違する。
【００４２】
メモリアクセスの競合を防ぐために、行列Vに含まれる同じパリティ方程式に含まれるビットは、同じメモリ領域からもたらされないことが必要である。この条件は、j≠kの場合に行列Vの正の係数に適用される以下の算術関係によって表される。
∀c(i, j)≧0 and ∀c(i,k)≧0 : c(i, j)≠c(i,k)
【００４３】
言い換えると、この条件によって、同じメモリに同時に2回アクセスすることが不可能であることが保障され、したがってメモリアクセスの競合に関する遅延が軽減されることによって符号化ビットレートが向上する。
【００４４】
本発明のある特徴によれば、ビット数ΔおよびΔ'を決定する前記(1つまたは複数の)パラメータは、前記パリティチェック行列Vの正の係数c(i, j)の関数である。
【００４５】
本発明の別の特徴によれば、第1符号化ステップの第1符号は、第1の複数の独立した符号で構成される。
【００４６】
したがって第1符号自体を並列化して、第1符号化ステップの符号化ビットレートをさらに向上させることができる。
【００４７】
本発明の別の特徴によれば、符号化方法は、パリティ第2符号化ステップから得られたビットに適用される第3符号を使用する第3符号化ステップを含み、この第3符号化ステップは、パリティ第2符号化ステップから得られた1つまたは複数のビットを符号化することによって開始される。
【００４８】
したがって第3符号化ステップの第3符号は、たとえば、第1符号、第2符号、および第3符号を連接することによって形成される符号の訂正能力を高めるために、第1符号化ステップの第1符号に比べて追加の特性を有するように選択することができる。
【００４９】
第3符号化ステップの第3符号は、第2の複数の独立した符号で有利に構成される。
【００５０】
したがって第3符号自体を並列化して、第3符号化ステップの符号化ビットレートをさらに向上させることができる。
【００５１】
本発明はまた、転送される情報に対応する第1部分と、冗長データを含む第2部分とで構成されるデータシーケンスを含む受信デジタル信号を復号する方法であって、
前記第1部分のデータに適用される第1復号ステップと、
第1復号ステップから得られたデータをインターリーブ手段でインターリーブするインターリーブステップと、
インターリーブ手段から得られたデータに適用される、パリティステップと呼ばれる第2復号ステップと
を含む方法を対象とする。
【００５２】
パリティ第2復号ステップは、所定数Δのデータ項目がインターリーブされた後に有利に開始される。この所定数Δのデータ項目は、インターリーブステップの1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、インターリーブステップ中に処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間である。
【００５３】
したがってこの方法では、パリティ符号化ステップとインターリーブステップとが、それらのステップに関するタスクの処理に関連するすべての機能およびメモリを重複させる必要なく並列化される。
【００５４】
本発明の別の特徴によれば、パリティ第2復号ステップは、所定数Δ'のデータ項目が第1復号ステップで復号された後に開始される。この所定数Δ'のデータ項目は、インターリーブステップの1つまたは複数のパラメータに依存する第2低数Δi'のデータ項目から、第1復号ステップ中に処理されるデータ項目の総数に対応する第2高数Δs'のデータ項目までの間である。
【００５５】
本発明の別の特徴によれば、復号方法は、パリティ第2復号ステップから得られたデータを復号する第3復号ステップを含み、この第3復号ステップは、パリティ第2復号ステップから得られた1つまたは複数のデータ項目を復号することによって開始される。
【００５６】
本発明の別の特徴によれば、インターリーブステップは、パリティ第2復号ステップと結合して実施される。
【００５７】
本発明の別の特徴によれば、インターリーブステップおよび第2復号ステップは、複数の恒等サブ行列を以下の形式
【００５８】
【数３】
【００５９】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]は、Null行列であり、それ以外の場合、前記サブ行列I[c(i, j)]は、c(i, j)位置を巡回的に並べ替えた恒等行列である。
【００６０】
本発明の別の特徴によれば、パリティチェック行列Vの同じ列についての正の係数c(i, j)は相違する。
【００６１】
遅延を発生させ、復号ビットレートの低下に反映されるメモリアクセスの競合を防ぐには、1つの変数が行列Vに含まれるm2個のパリティ方程式のグループに2回以上含まれないことが必要であり、これは、以下の算術関係によって行列Vの正の係数に反映される。
∀c(i, j)≧0 and ∀c(i, j+ 1) : c(i, j)≠c(i + 1, j) ∀i,∀j
【００６２】
本発明の別の特徴によれば、データ項目の数ΔおよびΔ'を決定する(1つまたは複数の)パラメータは、パリティチェック行列Vの正の係数c(i, j)の関数である。
【００６３】
本発明はまた、入力ビットシーケンスS0を符号化して符号化ビットシーケンスSを生み出すための装置であって、
第1符号を使用して入力ビットシーケンスS0のビットを符号化するための第1符号化手段と、
第1符号化手段から得られたビットをインターリーブするためのインターリーブ手段と、
第2符号を使用して、インターリーブ手段から得られたビットを符号化して符号化ビットシーケンスSを生成するための、パリティ手段と呼ばれる第2符号化手段と
を含む装置を対象とする。
【００６４】
インターリーブ手段は、パリティ第2符号化手段が所定数Δのビットがインターリーブされた後に符号化ビットシーケンスSを開始するように有利になされる。この所定数Δのビットは、インターリーブ手段の1つまたは複数のパラメータに依存する第1低数Δiのビットから、インターリーブ手段によって処理されるビットの総数に対応する第1高数Δsまでの間である。
【００６５】
この符号化装置は、具体的には、上述の符号化方法を実施するように適合することができる。
【００６６】
本発明はさらに、伝送される情報に対応する第1部分と、冗長データを含む第2部分とで形成されるデータシーケンスを含む受信デジタル信号を復号するための装置を対象とする。この装置は、
第1部分のデータ項目を復号するための第1復号手段と、
第1復号手段から得られたビットをインターリーブするためのインターリーブ手段と、
インターリーブ手段から得られたビットを復号するための、パリティ手段と呼ばれる第2復号手段と
を含む。
【００６７】
インターリーブ手段は、パリティ第2復号手段が所定数Δのデータ項目がインターリーブされた後にパリティ復号を開始するようになされる。この所定数Δのデータ項目は、インターリーブステップの1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、インターリーブ手段によって処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間である。
【００６８】
この復号装置は、具体的には、上述の復号方法を実行するように適合することができる。
【００６９】
本発明はまた、通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに上述の符号化方法のステップを実行するためのプログラムコード命令を含むコンピュータプログラム製品を対象とする。
【００７０】
本発明はまた、通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに上述の復号方法のステップを実行するためのプログラムコード命令を含むコンピュータプログラム製品を対象とする。
【００７１】
本発明の他の特徴および利点は、本発明の非制限的な一実施形態を示す添付の図面を参照する以下の説明から明らかになる。
【発明を実施するための最良の形態】
【００７２】
図3は、入力ビットシーケンスS0を符号化して符号化ビットシーケンスSを生み出すための本発明の符号化方法のステップ(縦軸)の時間(横軸)内でのスケジューリングを示している。
【００７３】
この方法は、第1符号を使用して入力ビットシーケンスS0のビットに適用される第1符号化ステップE1を含む。この第1符号化ステップによって作成されるビットは、インターリーブステップE3中に、インターリーブ手段33(図6を参照されたい)によってインターリーブされる。
【００７４】
インターリーブ手段33からもたらされるビットは、パリティステップと呼ばれる第2符号化ステップE4で第2符号を使用して符号化されて、符号化ビットシーケンスSが生成される。
【００７５】
パリティ第2符号化ステップE4は、所定数Δのビットをインターリーブした後に有利に開始される。この所定数Δのビットは、インターリーブステップE3の1つまたは複数のパラメータに依存する第1低数Δiのビットから、インターリーブステップE3中に処理されるビットの総数に対応する第1高数Δsのビットまでの間である。
【００７６】
図4は、本発明の符号化方法の一実施形態を構成するさまざまなステップ(縦軸)の時間(横軸)内におけるインターリーブを例として示している。
【００７７】
この符号化方法は、入力ビットシーケンスS0を符号化して符号化ビットシーケンスS'を生み出す以下のステップを含む。
【００７８】
第1符号化ステップEl(外部符号化)は、第1符号化手段30(外部符号器30)により、外部符号パリティチェック行列G1によって定義される第1符号(外部符号)を使用して、入力ビットシーケンスS0のビットに適用される。
【００７９】
インターリーブステップE3では、インターリーブ手段33(「インターリーバ」33)が外部符号からのビットをビットレベルおよびパケットレベルでインターリーブする。
【００８０】
インターリーバ33からもたらされるビットは、パリティ第2符号化ステップE4中に、パリティ第2符号化手段32(パリティ符号器32)によって、パリティ符号パリティチェック行列V内で定義されるパリティ符号を使用して符号化される。
【００８１】
第3(内部)符号化ステップE6は、内部符号パリティチェック行列G2によって定義される符号を使用して、パリティ符号器32からもたらされるビットに適用されて、符号化ビットシーケンスS'が形成される。
【００８２】
パリティ符号化ステップE4は、所定数Δのビットに比例する時間の後、すなわち最初のΔビットをインターリーブした後に、有利に開始される。この所定数Δは、第1低数Δiのビットから、インターリーブステップE3中に処理されるビットの総数に対応する第1高数Δsのビットまでの間である。したがってパリティ符号化ステップE4は、インターリーブステップE3と並列で、Δビットのオフセットを伴って実施される。
【００８３】
インターリーブステップE3は、少なくとも1ビットのオフセットを伴って(Δ' - Δ≧1)、外部符号化ステップE1と並列で開始および実施される。同様に、内部符号化ステップE6は、少なくとも1ビットのオフセットを伴って、パリティ符号化ステップE4と並列で開始および実施される。
【００８４】
好ましい実施形態において、当該の符号は、以下の形式
【００８５】
【数４】
【００８６】
のパリティチェック行列Hから構築されるLDPC(Low Density Parity Check)符号であり、この形式で、
G1は、外部符号器30(図6を参照されたい)に関連する外部符号パリティチェック行列であり、
Vは、パリティ符号およびインターリーブ関数を含む符号のパリティチェック行列であり、
G2は、内部符号器34(図6を参照されたい)に関連する内部符号パリティチェック行列である。
【００８７】
外部符号は、行列G1に基づいて定義され、この行列は、以下の形式
【００８８】
【数５】
【００８９】
のK×Kの正方行列であり、この形式で、Iは、z×zの恒等行列であり、Ipは、p位置を右または左に巡回的に並べ替えたz×zの恒等行列である。
【００９０】
オプションで、外部符号が複数の独立した符号で構成されるように数「p」の値を設定することによって外部符号化/復号ステップを並列化し、それによって符号化/復号の速度を(外部符号化/復号のレベルで)向上させることが可能である。
【００９１】
この実施例で、p = 0の場合、外部符号は、「z」個の独立した符号で構成される。それ以外の場合(すなわち、p≠0の場合)、外部符号は、「z/b」個の独立した符号で構成され、ここでbは、以下であるような最小の正のゼロ以外の整数である。
(b.p) modulo z = 0 (4)
【００９２】
たとえば、外部符号は、並列で機能する複数の独立した巡回畳み込み符号で構成し、それによって符号化ビットレートを向上させることができる。
【００９３】
内部符号は、行列G2に基づいて定義され、この行列は、以下の形式
【００９４】
【数６】
【００９５】
のM×Mの正方行列であり、この形式で、Iは、z×zの恒等行列であり、Ieは、「e」位置を非巡回的に右または左に並べ替えたz×zの恒等行列である。
【００９６】
外部符号化と同様に、オプションで、内部符号が複数の独立した符号で構成されるように数「e」の値を設定することによって内部符号化ステップを並列化し、それによって符号化速度を内部符号化のレベルで向上させることができる。
【００９７】
この実施例で、e = 0の場合、内部符号は、「z」個の独立した符号で構成される。それ以外の場合(すなわち、e≠0の場合)、内部符号は、数「e」と等価である数の独立した符号で構成される。
【００９８】
たとえば、内部符号は、並列で機能する複数の独立した再帰的な巡回畳み込み符号で構成し、それによって符号化ビットレートを向上させることができる。
【００９９】
行列Vは、複数のNull行列および/または巡回的に並べ替えた恒等行列を含む準巡回M×K行列であり、この行列Vは、以下の関係
【０１００】
【数７】
【０１０１】
によって定義され、ここで、
m1は、K = m1×z(7)であるような厳密な正の整数であり、
m2は、M = m2×z(8)であるような厳密な正の整数であり、
I[c( i, j)]は、z×zのNull行列であるか、またはz×zの巡回並べ替え恒等行列であり、c(i, j) < 0の場合、I[c(i, j)]は、Null行列であり、それ以外の場合、I[c(i, j)]は、c(i, j)位置を右または左に巡回的に並べ替えた恒等行列である。
【０１０２】
上述の行列Vの形式は、本発明によるパリティ符号とビットレベルおよびパケットレベルでのインターリーブとを含む。
【０１０３】
図5Aおよび図5Bはそれぞれ、第1関数πによるビットレベルでのインターリーブと、第2関数λによるパケットレベルでのインターリーブとを示している。
【０１０４】
図5Aでは、ビットの第1ブロックB1に属する、外部符号器の出力でのビットが、第1インターリーブ関数πを使用してインターリーブされて、インターリーブ済みビットの第2ブロックB2が形成される。
【０１０５】
この第1インターリーブ関数πは、ビットの第1ブロックB1に属するインデックス「i」の任意のビットを、インターリーブ済みビットのブロックB2のインデックスπ(i)のビットと関連付け、ビットの第1ブロックB1の最初のkビットをインターリーブすることによって、インターリーブ済みビットの第2ブロックB2の少なくとも最初のmビットが提供されるようにする。したがって、この実施例では、処理されるビットの第1ブロックB1のインデックスk + 1である次のビットは、インターリーブ済みビットの第2ブロックB2内のインデックスπ(k + 1)の位置になり、π(k + 1) > mとなる。
【０１０６】
したがって、パリティ符号化がJ = mビットのブロックによって実施される場合、このインターリーブ関数は、インターリーブ手段33からもたらされる最初のJビットの符号化を、インターリーブステップE3が終了するのを待たずに開始することができるということを意味する。上述の従来技術とは対照的に、パリティ符号化ステップE4を開始できるようになるために、外部符号器の出力時のすべてのビットがインターリーブ手段33によってインターリーブされるのを待つ必要はない。
【０１０７】
図5Bでは、外部符号器30の出力でビットの第1ブロックB1に属するビットは、第2インターリーブ関数λを使用してインターリーブされ、この第2インターリーブ関数λは、ビットの第1ブロックB1に属する第1組のm1ビットのパケット(P1、P2、P3、P4、P5)を、第2組のJインターリーブ済みビットのパケット(P10、P20、P30、P40、P50、P60)と関連付け、Jインターリーブ済みビットの同じパケットP30に属するビットのすべてが、第1組のm1ビットのパケット(P1、P2、P3、P4、P5)に属する別々のパケットからもたらされるようにする。図5Bの実施例では、パケットP30は、5つのそれぞれのパケット(P1、P2、P3、P4、P5)からもたらされる5つのビット(b1、b2、b3、b4、b5)で構成される。
【０１０８】
好ましい実施形態では、上述の行列Vの形式によって、第1関数πおよび第2関数λにそれぞれ従ってビットレベルおよびパケットレベルでインターリーブを行うことが可能となる。したがってJインターリーブ済みビットのi番目のパケットに属するインデックス「π(i)」の各ビットは、m1ビットのλ-1(i, 1)番目のパケットに属する(i)番目のビットと関連する。
【０１０９】
本発明の符号化(および復号)方法では、パリティ符号化(および復号)ステップおよび外部符号化(および復号)ステップの並列化のパラメータは、所定数のビットに対応する所定のメトリックΔによって決定される。
【０１１０】
この数Δの値は、行列Vの厳密に正である係数c(i, j)から、以下の態様で計算される。
Φ≡{ci}を、行列Vの正およびゼロ以外の係数c(i, j)を昇順で並べた集合であるとする。「d」を、x≧yである2つの点xおよびyの間の距離を計算するための関数であり、d(x, y) = (x - y)によって定義されるとする。この数Δの値は、以下の関係
Δ = Max(Δ1,c0 + z - ccard(Φ)-1) (9)
を使用して計算され、この関係において、
card(Φ)は、集合Φの要素の数を表し、
c0は、パリティチェック行列Vの最小の正のゼロ以外の係数c(i, j)であり、
zは、パリティチェック行列Vに含まれる恒等サブ行列の次元であり、
Δ1は、集合Φに属する任意の2つの隣接する要素(ciおよびci+1)の間の最大距離であり、この距離は、以下の関係
Δ1 = Max({d(ci+1, ci)}i∈[0, card(Φ)-1]) (10)
によって定義される。
【０１１１】
図6は、第1(外部)符号器30(第1符号化手段)と、インターリーバ33(インターリーブ手段)を含むパリティ符号器32(第2符号化手段)と、内部符号器34(第3符号化手段)と、外部符号器30およびパリティ符号器32の間の第1メモリ手段36と、パリティ符号器32および内部符号器34の間の第2メモリ手段38とを含む本発明の符号化装置100の一実施形態を示している。
【０１１２】
異なる実施形態では、インターリーバ33およびパリティ符号器32は別々にすることができるという点に留意されたい。
【０１１３】
第1メモリ36は、それぞれm1ビットのストレージ容量を備える「z」個の第1メモリバンク(ME1〜MEz)の第1組を含む。
【０１１４】
第2メモリ38は、それぞれm2ビットのストレージ容量を備える少なくとも2つの第2メモリバンク(MI1およびMI2)を含む。
【０１１５】
入力ビットブロックB0は、本発明の符号化装置100によって符号化されて、符号化ビットシーケンスSが生み出される。
【０１１６】
外部符号器30は、入力ビットブロックB0の符号化を開始して、外部符号器30の出力における最初の数ビットを生成し、これらのビットは、メモリ36の第1メモリバンク(ME1〜MEZ)内に、自然な順序およびm1ビットのパケット単位で直接格納される。
【０１１７】
所定数Δに比例する時間の後、パリティ符号器32は、第1組のメモリバンク(ME1〜MEZ)のサブセットの各メモリバンク内のビットを読み取り、行列V内で定義されるパリティ行によるmodulo-2加法演算によってこれらのビットを可算する(行列Vの各行は、パリティ方程式を定義する)。
【０１１８】
たとえば、パリティ符号器32は、行列Vのm2個の行に含まれるm2個のパリティ方程式を処理して、パリティ符号器32の出力でm2ビットを生成することができる。それらのm2ビットは、メモリ38の第2組のメモリバンク(MI1およびMI2)のメモリバンクMI1内に直接格納される。
【０１１９】
m2ビットがパリティ符号器32の出力でメモリバンク(MI1、MI2)に書き込まれた直後、内部符号器34は、それらのm2ビットを読み取り、それらのビットの符号化を、内部符号パリティチェック行列G2内に含まれる内部符号を使用して事実上即時に開始することができる。
【０１２０】
内部符号化操作がm2ビットに対してm2ビットが第2メモリバンク(この実施例ではMI1)に書き込まれた直後に実施されると仮定すると、ハードウェアリソースの最適な利用を可能にするには、第2メモリ38に2つのメモリブロック(MI1およびMI2)だけが含まれていれば十分であり、これら2つのメモリバンクのそれぞれは、書き込みモードまたは読み取りモードで交互に機能する。
【０１２１】
実際には、内部符号器がそのタスクをパリティ符号器と並列で開始できるためには、パリティ符号を1ビット処理すれば十分である。
【０１２２】
図7は、復号方法の特定の一実施形態を構成するさまざまなステップ(縦軸)の時間(横軸)内におけるスケジューリングのきわめて概略的な図である。
【０１２３】
この復号方法では、伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで構成されるデータシーケンスを含む受信デジタル信号を復号する。
【０１２４】
この方法では、第1(外部)復号ステップE100は、第1部分Dのデータに適用される。インターリーブ手段43(インターリーバ43)によって実施されるインターリーブステップE300は、第1(外部)復号ステップE100からもたらされるデータをインターリーブする。パリティ第2復号ステップE400は、インターリーバ43からもたらされるデータに適用される。第3(内部)復号ステップE600は、パリティ復号ステップE400からもたらされるデータに適用される。
【０１２５】
パリティ復号ステップE400は、所定数Δのデータビットをインターリーブした後に有利に開始される。この所定数Δのデータビットは、インターリーブステップE300の1つまたは複数のパラメータに依存する第1低数Δiのデータビットから、インターリーブステップE300中に処理されるデータビットの総数に対応する第1高数Δsのデータビットまでの間である。
【０１２６】
図8は、伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで構成されるデータシーケンスを含む受信デジタル信号を復号するための本発明の復号装置200の実施形態を示している。
【０１２７】
本発明の復号装置200は、外部復号器40(第1復号手段40)と、インターリーバ43(インターリーブ手段43)を含むパリティ復号器42(パリティ第2復号手段42)と、内部復号器44(第2復号手段44)と、外部復号器40および内部復号器44の入力側にある第1メモリモジュール46と、外部復号器40およびパリティ復号器42の間にある第2メモリモジュール48と、パリティ復号器42および内部復号器44の間にある第3メモリモジュール50とを含む。
【０１２８】
異なる実施形態では、インターリーバ43およびパリティ復号器42は別々にすることができるという点に留意されたい。
【０１２９】
インターリーバ43は、パリティ復号器42が所定数Δのデータビットがインターリーブされた後にパリティ復号ステップE400を開始するようになされる。この所定数Δのデータビットは、インターリーバ43の1つまたは複数のパラメータに依存する第1低数Δiのデータビットから、インターリーバ43によって処理されるデータビットの総数に対応する第1高数Δsのデータビットまでの間である。
【０１３０】
「m1×z」のフレキシブル値を含む受信デジタル信号を格納するための第1メモリモジュール46は、それぞれm1ビットのストレージ容量を備える「z」個の第1メモリバンク(M1〜Mz)を含む。
【０１３１】
外部復号器40およびパリティ復号器42の間で伝送中のデータを格納するための第2メモリモジュール48は、それぞれm1ビットのストレージ容量を備える「z」個の第2メモリバンク(ME1〜MEz)を含む。
【０１３２】
パリティ復号器42および内部復号器44の間で伝送中のデータを格納するための第3メモリモジュール50は、それぞれm2ビットのストレージ容量を備える「z」個の第3メモリバンク(MI1〜Mlz)を含む。
【０１３３】
メモリ46、48および50をそれぞれの複数のメモリバンク(M1〜Mz)、(ME1〜MEZ)、(MI1〜MIZ)に分割することによって、同じメモリへの同時アクセスが最小化されるか、場合によっては排除される。
【０１３４】
N個のフレキシブル値のフレームが、反復的に復号される。内部符号および外部符号のフレキシブルな復号は、L.R. Bahl他によって「Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate」(IEEE Transactions on Information Theory、Volume IT-20、1974年3月、248〜287項)という名称の文書で説明されているように、Bahl-Cocke-Jelinek-Ravivアルゴリズム、Forward-Backwardアルゴリズムまたは軟出力ビタビアルゴリズムなど、フレキシブル出力畳み込み符号を復号するための標準的な技法を使用して実施することができるという点に留意されたい。
【０１３５】
この方法の初期化ステップは、第1メモリモジュール46の最初の「z」個のメモリバンク(M1〜Mz)内に、自然な順序およびm1個のフレキシブル値のパケット単位で、受信信号に含まれるN = m1×z個のデータ項目を格納する段階に存する。
【０１３６】
言い換えると、受信信号の最初のm1個のフレキシブル値は、最初のメモリバンクM1内に格納され、次のm1個のフレキシブル値は、次のメモリバンクM2に格納される、というようになる。
【０１３７】
この方法は、各反復で以下のステップを含む。
【０１３８】
外部復号器40は、第1メモリモジュール46に属するメモリバンクMjに含まれるm1データビット(またはm1個のフレキシブル値)を含むインデックスjの窓上で復号を実施して第1外部データを生成し、このデータは、第2メモリモジュール48に属するメモリバンクMEjに格納される。
【０１３９】
Δ個の窓を復号した後、パリティ復号器42は、外部復号器40と並列で、かつ競合することなく機能することができる。
【０１４０】
行列V内で定義されるパリティ方程式は、外部符号器の出力で供給される変数またはデータを使用して、順番にかつm2個の方程式のグループで解決される。1つの窓の復号中に行列Vのm2個のパリティ方程式で使用されるこれらの変数のそれぞれの値は、異なるメモリバンク(ME1〜MEZ)内で読み取られる。インデックスiの各窓について、m2個の方程式のi番目のグループのm2個の方程式が、i、i + z、i + 2×z、...、i + m2×z(iは、1〜zの範囲内)の順序で解決される。
【０１４１】
m2個の方程式のi番目のグループを復号した結果は、第3メモリモジュール50に属するi番目のメモリバンクMIiに格納される。たとえば、m2個のパリティ方程式の2番目のグループを解決することによってもたらされるm2データビットは、2番目のメモリバンクMI2に格納される。
【０１４２】
パリティ復号器がインデックスiの窓上でm2個の方程式の最初のグループを解決した直後、内部復号器は、この窓上でそのタスクである復号を開始することができる。インデックスiの窓を復号することによってもたらされる外部情報は、第3メモリモジュール50に属するメモリバンクMIi内に格納される。
【０１４３】
内部復号器によるΔ個の窓の復号に続いて、行列V内で定義されるパリティ方程式に含まれる変数が更新される。
【０１４４】
パリティ復号ステップ中に同じメモリバンクへのアクセスが競合するのを防ぐには、1つの変数が、m2個のパリティ方程式の1つのグループ内に2回以上含まれていてはならない。このルールは、行列Vの同じ列についてのすべての正の係数c(i, j)は相違するという条件内に反映されている。
【０１４５】
本発明はまた、コンピュータ内で実行されたときに本発明の符号化方法および/または復号方法のステップを実行するためのプログラムコード命令を含む、通信ネットワークからダウンロード可能なコンピュータプログラムを対象とする。このコンピュータプログラムは、コンピュータ読み取り可能メディア上に格納することができる。
【０１４６】
このプログラムは、任意のプログラミング言語を使用することができ、ソースコード、オブジェクトコード、または部分コンパイル形式などのソースコードおよびオブジェクトコードの中間コードの形式か、あるいは任意の他の望ましい形式を取ることができる。
【０１４７】
本発明はまた、上述のコンピュータプログラムの命令を含むコンピュータ読み取り可能情報メディアを対象とする。
【０１４８】
この情報メディアは、プログラムを格納する能力を有する任意のエンティティまたは装置とすることができる。たとえば、このメディアは、たとえばCD ROMや超小型電子回路ROMといったROMや、たとえばディスケット(フロッピー（登録商標）ディスク)やハードディスクといった磁気ストレージ手段などのストレージ手段を含むことができる。
【０１４９】
さらに、情報メディアは、無線または他の手段によって電気ケーブルまたは光学ケーブルを介してルーティングできる電気信号または光学信号などの伝送可能なメディアとすることができる。本発明のプログラムは、特にインターネット型ネットワークを通じてダウンロードすることができる。
【０１５０】
あるいは情報メディアは、プログラムが組み込まれる集積回路とすることができ、この回路は、当該の方法を実行するように、またはその方法の実行で使用されるように適合される。
【０１５１】
符号化装置は、図9に示すように、信号Bによって制御される中央処理装置60、メモリ62、入力装置64および出力装置66を通常含むデータ処理システムFによって実装することができるという点に留意されたい。これらすべての要素は、データバス68によって相互接続される。
【０１５２】
さらに、このデータ処理システムは、本発明の符号化方法を実行するための命令を含むコンピュータプログラムを実行するために使用することができる。
【０１５３】
復号装置も、図9のデータ処理システムと同様のデータ処理システムによって実装することができるという点に留意されたい。
【０１５４】
さらに、このデータ処理システムは、本発明の復号方法を実行するための命令を含むコンピュータプログラムを実行するために使用することができる。
【図面の簡単な説明】
【０１５５】
【図１Ａ】従来技術の符号器を示す図である。
【図１Ｂ】従来技術の復号器を示す図である。
【図２Ａ】従来技術の符号化ステップのスケジューリングを示す図である。
【図２Ｂ】従来技術の復号ステップのスケジューリングを示す図である。
【図３】本発明の符号化ステップのスケジューリングを示す図である。
【図４】本発明の一実施形態の符号化ステップのスケジューリングを示す図である。
【図５Ａ】本発明によるビットレベルでのインターリーブを示す図である。
【図５Ｂ】本発明によるパケットレベルでのインターリーブを示す図である。
【図６】本発明の符号化装置を示す図である。
【図７】本発明の一実施形態の復号ステップのスケジューリングを示す図である。
【図８】本発明の復号装置を示す図である。
【図９】本発明の符号化装置および/または復号装置を使用するデータ処理システムを示す図である。
【符号の説明】
【０１５６】
3 外部符号器
5 インターリーバ
7 直列並列変換器
9 パリティ符号器
10 従来技術の符号器
11 内部符号器
15 外部復号器
17 インターリーバ/デインターリーバ
19 パリティ復号器
20 従来技術の復号器
21 内部復号器
30 第1符号化手段
32 第2符号化手段
33 インターリーブ手段
34 内部符号器
36 第1メモリ手段
38 第2メモリ手段
40 外部復号器
42 パリティ復号器
43 インターリーバ
44 内部復号器
46 第1メモリモジュール
48 第2メモリモジュール
50 第3メモリモジュール
60 中央処理装置
62 メモリ
64 入力装置
66 出力装置
68 データバス
100 本発明の符号化装置
200 本発明の復号装置
De 入力ビットシーケンス
Di インターリーブ済みデータシーケンス
I1 外部情報
I2 情報
I3 新しい外部情報
I4 フレキシブルデータ
I5 メッセージ
I6 メッセージ
I7 メッセージ
E10 符号化ステップ
E30 計算ステップ
E50 符号化ステップ
E70 復号ステップ
E90 計算ステップ
E110 ステップ
E130 ステップ
T10 時間
T30 時間
T50 時間
T70 時間
T90 時間
T110 時間
T130 時間
Δ 所定数
Δi 第1低数
Δs 第1高数
Δ' 所定数
Δi' 第1低数
Δs' 第1高数
S0 入力ビットシーケンス
S 符号化ビットシーケンス
E1 第1符号化ステップ
E3 インターリーブステップ
E4 第2符号化ステップ
E6 第3符号化ステップ
B1 ビットの第1ブロック
B2 インターリーブ済みビットの第2ブロック
P1 パケット
P2 パケット
P3 パケット
P4 パケット
P5 パケット
P10 パケット
P20 パケット
P30 パケット
P40 パケット
P50 パケット
P60 パケット
b1 ビット
b2 ビット
b3 ビット
b4 ビット
b5 ビット
ME1〜MEz 第1メモリバンク
MI1 第2メモリバンク
MI2 第2メモリバンク
E100 第1(外部)復号ステップ
E300 インターリーブステップ
E400 パリティ第2復号ステップ
E600 第3(内部)復号ステップ
M1〜Mz 第1メモリバンク
ME1〜MEz 第2メモリバンク
MI1〜MIz 第3メモリバンク
B 信号
F データ処理システム
【特許請求の範囲】
【請求項１】
入力ビットシーケンス(S0)を符号化して符号化ビットシーケンス(S)を生み出す方法であって、
第1符号を使用して前記入力ビットシーケンス(S0)のビットに適用される第1符号化ステップ(E1)と、
前記第1符号を使用して得られたビットをインターリーブ手段(33)でインターリーブするインターリーブステップ(E3)と、
前記インターリーブ手段(33)から得られたビットに第2符号を使用して適用されて前記符号化ビットシーケンス(S)を生成する、パリティステップと呼ばれる第2符号化ステップ(E4)と
を含み、前記パリティ第2符号化ステップ(E4)は、前記インターリーブステップ(E3)の終了を待つことなく所定数Δのビットがインターリーブされた後に開始され、前記所定数Δのビットは、前記インターリーブステップ(E3)の1つまたは複数のパラメータに依存する第1低数Δiのビットから、前記インターリーブステップ(E3)中に処理されるビットの総数に対応する第1高数Δsのビットまでの間であることを特徴とする方法。
【請求項２】
前記パリティ第2符号化ステップ(E4)は、所定数Δ'のビットが前記第1符号化ステップ(E1)によって符号化された後に開始され、前記所定数Δ'のビットは、前記インターリーブステップ(E3)の1つまたは複数のパラメータに依存する第2低数Δi'のビットから、前記第1符号化ステップ(E1)中に処理されるビットの総数に対応する第2高数Δs'のビットまでの間であることを特徴とする請求項1に記載の符号化方法。
【請求項３】
前記インターリーブステップ(E3)は、前記パリティ第2符号化ステップ(E4)と結合して実施されることを特徴とする請求項1または請求項2に記載の符号化方法。
【請求項４】
前記インターリーブステップ(E3)は、前記第1符号を使用して得られたi番目のビットを、インターリーブ済みビットシーケンス(B2)π(i)番目のビットと関連付けるビットレベルの第1インターリーブ関数πを含み、最初のkビットをインターリーブすることによって、前記インターリーブ済みビットシーケンス(B2)の少なくとも最初のmビットが供給されるようにすることを特徴とする請求項1から3のいずれか一項に記載の符号化方法。
【請求項５】
前記インターリーブステップ(E3)および前記パリティ第2符号化ステップ(E4)は、複数の恒等サブ行列を以下の形式
【数１】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]は、Null行列であり、それ以外の場合、前記サブ行列I[c(i, j)]は、c(i, j)位置を巡回的に並べ替えた恒等行列であることを特徴とする請求項3または請求項4に記載の符号化方法。
【請求項６】
前記インターリーブステップ(E3)は、前記第1符号を使用して得られた第1組のm1ビットのパケット(P1、P2、P3、P4、P5)を、前記インターリーブ済みビットシーケンス(B2)の第2組のJビットのパケット(P10、P20、P30、P40、P50)と関連付けるための第2インターリーブ関数λを含み、前記インターリーブ済みビットシーケンス(B2)のJビットの同じパケット(P30)に属するビットが、前記第1組のm1ビットのパケット(P1、P2、P3、P4、P5)の異なるパケットからもたらされるようにすることを特徴とする請求項3から5のいずれか一項に記載の符号化方法。
【請求項７】
前記パリティチェック行列Vの同じ行についての正の係数c(i, j)が相違することを特徴とする請求項5または請求項6に記載の符号化方法。
【請求項８】
数ΔおよびΔ'のビットを決定する前記(1つまたは複数の)パラメータは、前記パリティチェック行列Vの正の係数c(i, j)の関数であることを特徴とする請求項1から7のいずれか一項に記載の符号化方法。
【請求項９】
前記第1符号化ステップ(E1)の前記第1符号は、第1の複数の独立した符号で構成されることを特徴とする請求項1から8のいずれかに記載の符号化方法。
【請求項１０】
前記パリティ第2符号化ステップ(E4)から得られたビットに適用される第3符号を使用する第3符号化ステップ(E6)を含み、前記第3符号化ステップ(E6)は、前記パリティ第2符号化ステップ(E4)から得られた1つまたは複数のビットを符号化することによって開始されることを特徴とする請求項1から9のいずれかに記載の符号化方法。
【請求項１１】
前記第3符号化ステップ(E6)の前記第3符号は、第2の複数の独立した符号で構成されることを特徴とする請求項10に記載の符号化方法。
【請求項１２】
伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで形成されるデータシーケンスを含む受信デジタル信号を復号する方法であって、
前記第1部分Dのデータに適用される第1復号ステップ(E100)と、
前記第1復号ステップ(E100)から得られたデータをインターリーブ手段(43)でインターリーブするインターリーブステップ(E300)と、
前記インターリーブ手段(43)から得られたデータに適用される、パリティステップと呼ばれる第2復号ステップ(E400)と
を含むことを特徴とし、前記パリティ第2復号ステップ(E400)は、前記インターリーブステップ(E300)が終了するのを待つことなく所定数Δのデータ項目がインターリーブされた後に開始され、前記所定数Δのデータ項目は、前記インターリーブステップ(E300)の1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、前記インターリーブステップ(E300)中に処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間であることを特徴とする方法。
【請求項１３】
前記パリティ第2復号ステップ(E400)は、所定数Δ'のデータ項目が前記第1復号ステップ(E100)で復号された後に開始され、前記所定数Δ'のデータ項目は、前記インターリーブステップ(E300)の1つまたは複数のパラメータに依存する第2低数Δi'のデータ項目から、前記第1復号ステップ(E100)中に処理されるデータ項目の総数に対応する第2高数Δs'のデータ項目までの間であることを特徴とする請求項12に記載の復号方法。
【請求項１４】
前記パリティ第2復号ステップ(E400)から得られたデータを復号するための第3復号ステップ(E600)を含み、前記第3復号ステップ(E600)は、前記パリティ第2復号ステップ(E400)から得られた1つまたは複数のデータ項目を復号することによって開始されることを特徴とする請求項12または請求項13に記載の復号方法。
【請求項１５】
前記インターリーブステップ(E300)は、前記パリティ第2復号ステップ(E400)と結合して実施されることを特徴とする請求項12から14のいずれか一項に記載の復号方法。
【請求項１６】
前記インターリーブステップ(E300)および前記第2復号ステップ(E400)は、複数の恒等サブ行列を以下の形式
【数２】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]はNull行列であり、それ以外の場合、前記サブ行列I[c(i, j)]はc(i, j)位置を巡回的に並べ替えた恒等行列であることを特徴とする請求項15に記載の復号方法。
【請求項１７】
前記パリティチェック行列Vの同じ列についての正の係数c(i, j)が相違することを特徴とする請求項16に記載の復号方法。
【請求項１８】
数ΔおよびΔ'のデータ項目を決定する前記(1つまたは複数の)パラメータは、前記パリティチェック行列Vの正の係数c(i, j)の関数であることを特徴とする請求項16または請求項17に記載の復号方法。
【請求項１９】
入力ビットシーケンス(S0)を符号化して符号化ビットシーケンス(S)を生み出す装置であって、
第1符号を使用して前記入力ビットシーケンス(S0)のビットを符号化するための第1符号化手段(30)と、
前記第1符号化手段(30)から得られたビットをインターリーブするためのインターリーブ手段(33)と、
第2符号を使用して、前記インターリーブ手段(33)から得られたビットを符号化して前記符号化ビットシーケンス(S)を生成するための、パリティ手段と呼ばれる第2符号化手段(32)と
を含み、前記インターリーブ手段(33)は、前記パリティ第2符号化手段(32)がインターリーブの終了を待つことなく所定数Δのビットがインターリーブされた後に前記符号化ビットシーケンス(S)を開始するようになされており、前記所定数Δのビットは、前記インターリーブ手段(33)の1つまたは複数のパラメータに依存する第1低数Δiのビットから、前記インターリーブ手段(33)によって処理されるビットの総数に対応する第1高数Δsのビットまでの間であることを特徴とする装置。
【請求項２０】
伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで形成されるデータシーケンスを含む受信デジタル信号を復号する装置であって、
前記第1部分Dのデータ項目を復号するための第1復号手段(40)と、
前記第1復号手段から得られたビットをインターリーブするためのインターリーブ手段(43)と、
前記インターリーブ手段(43)から得られたビットを復号するための、パリティ手段と呼ばれる第2復号手段(42)と
を含み、前記インターリーブ手段(43)は、前記パリティ第2復号手段(42)がインターリーブの終了を待つことなく所定数Δのデータ項目がインターリーブされた後にパリティ復号を開始するようになされており、前記所定数Δのデータ項目は、前記インターリーブ手段(43)の1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、前記インターリーブ手段(43)によって処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間であることを特徴とする装置。
【請求項２１】
通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに請求項1から11の少なくとも一項による符号化方法のステップを実行するためのプログラムコード命令を含むことを特徴とするコンピュータプログラム製品。
【請求項２２】
通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに請求項12から18の少なくとも一項による復号方法のステップを実行するためのプログラムコード命令を含むことを特徴とするコンピュータプログラム製品。
【請求項１】
入力ビットシーケンス(S0)を符号化して符号化ビットシーケンス(S)を生み出す方法であって、
第1符号を使用して前記入力ビットシーケンス(S0)のビットに適用される第1符号化ステップ(E1)と、
前記第1符号を使用して得られたビットをインターリーブ手段(33)でインターリーブするインターリーブステップ(E3)と、
前記インターリーブ手段(33)から得られたビットに第2符号を使用して適用されて前記符号化ビットシーケンス(S)を生成する、パリティステップと呼ばれる第2符号化ステップ(E4)と
を含み、前記パリティ第2符号化ステップ(E4)は、前記インターリーブステップ(E3)の終了を待つことなく所定数Δのビットがインターリーブされた後に開始され、前記所定数Δのビットは、前記インターリーブステップ(E3)の1つまたは複数のパラメータに依存する第1低数Δiのビットから、前記インターリーブステップ(E3)中に処理されるビットの総数に対応する第1高数Δsのビットまでの間であることを特徴とする方法。
【請求項２】
前記パリティ第2符号化ステップ(E4)は、所定数Δ'のビットが前記第1符号化ステップ(E1)によって符号化された後に開始され、前記所定数Δ'のビットは、前記インターリーブステップ(E3)の1つまたは複数のパラメータに依存する第2低数Δi'のビットから、前記第1符号化ステップ(E1)中に処理されるビットの総数に対応する第2高数Δs'のビットまでの間であることを特徴とする請求項1に記載の符号化方法。
【請求項３】
前記インターリーブステップ(E3)は、前記パリティ第2符号化ステップ(E4)と結合して実施されることを特徴とする請求項1または請求項2に記載の符号化方法。
【請求項４】
前記インターリーブステップ(E3)は、前記第1符号を使用して得られたi番目のビットを、インターリーブ済みビットシーケンス(B2)π(i)番目のビットと関連付けるビットレベルの第1インターリーブ関数πを含み、最初のkビットをインターリーブすることによって、前記インターリーブ済みビットシーケンス(B2)の少なくとも最初のmビットが供給されるようにすることを特徴とする請求項1から3のいずれか一項に記載の符号化方法。
【請求項５】
前記インターリーブステップ(E3)および前記パリティ第2符号化ステップ(E4)は、複数の恒等サブ行列を以下の形式
【数１】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]は、Null行列であり、それ以外の場合、前記サブ行列I[c(i, j)]は、c(i, j)位置を巡回的に並べ替えた恒等行列であることを特徴とする請求項3または請求項4に記載の符号化方法。
【請求項６】
前記インターリーブステップ(E3)は、前記第1符号を使用して得られた第1組のm1ビットのパケット(P1、P2、P3、P4、P5)を、前記インターリーブ済みビットシーケンス(B2)の第2組のJビットのパケット(P10、P20、P30、P40、P50)と関連付けるための第2インターリーブ関数λを含み、前記インターリーブ済みビットシーケンス(B2)のJビットの同じパケット(P30)に属するビットが、前記第1組のm1ビットのパケット(P1、P2、P3、P4、P5)の異なるパケットからもたらされるようにすることを特徴とする請求項3から5のいずれか一項に記載の符号化方法。
【請求項７】
前記パリティチェック行列Vの同じ行についての正の係数c(i, j)が相違することを特徴とする請求項5または請求項6に記載の符号化方法。
【請求項８】
数ΔおよびΔ'のビットを決定する前記(1つまたは複数の)パラメータは、前記パリティチェック行列Vの正の係数c(i, j)の関数であることを特徴とする請求項1から7のいずれか一項に記載の符号化方法。
【請求項９】
前記第1符号化ステップ(E1)の前記第1符号は、第1の複数の独立した符号で構成されることを特徴とする請求項1から8のいずれかに記載の符号化方法。
【請求項１０】
前記パリティ第2符号化ステップ(E4)から得られたビットに適用される第3符号を使用する第3符号化ステップ(E6)を含み、前記第3符号化ステップ(E6)は、前記パリティ第2符号化ステップ(E4)から得られた1つまたは複数のビットを符号化することによって開始されることを特徴とする請求項1から9のいずれかに記載の符号化方法。
【請求項１１】
前記第3符号化ステップ(E6)の前記第3符号は、第2の複数の独立した符号で構成されることを特徴とする請求項10に記載の符号化方法。
【請求項１２】
伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで形成されるデータシーケンスを含む受信デジタル信号を復号する方法であって、
前記第1部分Dのデータに適用される第1復号ステップ(E100)と、
前記第1復号ステップ(E100)から得られたデータをインターリーブ手段(43)でインターリーブするインターリーブステップ(E300)と、
前記インターリーブ手段(43)から得られたデータに適用される、パリティステップと呼ばれる第2復号ステップ(E400)と
を含むことを特徴とし、前記パリティ第2復号ステップ(E400)は、前記インターリーブステップ(E300)が終了するのを待つことなく所定数Δのデータ項目がインターリーブされた後に開始され、前記所定数Δのデータ項目は、前記インターリーブステップ(E300)の1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、前記インターリーブステップ(E300)中に処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間であることを特徴とする方法。
【請求項１３】
前記パリティ第2復号ステップ(E400)は、所定数Δ'のデータ項目が前記第1復号ステップ(E100)で復号された後に開始され、前記所定数Δ'のデータ項目は、前記インターリーブステップ(E300)の1つまたは複数のパラメータに依存する第2低数Δi'のデータ項目から、前記第1復号ステップ(E100)中に処理されるデータ項目の総数に対応する第2高数Δs'のデータ項目までの間であることを特徴とする請求項12に記載の復号方法。
【請求項１４】
前記パリティ第2復号ステップ(E400)から得られたデータを復号するための第3復号ステップ(E600)を含み、前記第3復号ステップ(E600)は、前記パリティ第2復号ステップ(E400)から得られた1つまたは複数のデータ項目を復号することによって開始されることを特徴とする請求項12または請求項13に記載の復号方法。
【請求項１５】
前記インターリーブステップ(E300)は、前記パリティ第2復号ステップ(E400)と結合して実施されることを特徴とする請求項12から14のいずれか一項に記載の復号方法。
【請求項１６】
前記インターリーブステップ(E300)および前記第2復号ステップ(E400)は、複数の恒等サブ行列を以下の形式
【数２】
で含む準巡回パリティチェック行列Vを用いて実施され、1からm1までの範囲内の任意のiと、1からm2までの範囲内の任意のjとについて、係数c(i, j)が厳密に負である場合、サブ行列I[c(i, j)]はNull行列であり、それ以外の場合、前記サブ行列I[c(i, j)]はc(i, j)位置を巡回的に並べ替えた恒等行列であることを特徴とする請求項15に記載の復号方法。
【請求項１７】
前記パリティチェック行列Vの同じ列についての正の係数c(i, j)が相違することを特徴とする請求項16に記載の復号方法。
【請求項１８】
数ΔおよびΔ'のデータ項目を決定する前記(1つまたは複数の)パラメータは、前記パリティチェック行列Vの正の係数c(i, j)の関数であることを特徴とする請求項16または請求項17に記載の復号方法。
【請求項１９】
入力ビットシーケンス(S0)を符号化して符号化ビットシーケンス(S)を生み出す装置であって、
第1符号を使用して前記入力ビットシーケンス(S0)のビットを符号化するための第1符号化手段(30)と、
前記第1符号化手段(30)から得られたビットをインターリーブするためのインターリーブ手段(33)と、
第2符号を使用して、前記インターリーブ手段(33)から得られたビットを符号化して前記符号化ビットシーケンス(S)を生成するための、パリティ手段と呼ばれる第2符号化手段(32)と
を含み、前記インターリーブ手段(33)は、前記パリティ第2符号化手段(32)がインターリーブの終了を待つことなく所定数Δのビットがインターリーブされた後に前記符号化ビットシーケンス(S)を開始するようになされており、前記所定数Δのビットは、前記インターリーブ手段(33)の1つまたは複数のパラメータに依存する第1低数Δiのビットから、前記インターリーブ手段(33)によって処理されるビットの総数に対応する第1高数Δsのビットまでの間であることを特徴とする装置。
【請求項２０】
伝送される情報に対応する第1部分Dと、冗長データを含む第2部分Cとで形成されるデータシーケンスを含む受信デジタル信号を復号する装置であって、
前記第1部分Dのデータ項目を復号するための第1復号手段(40)と、
前記第1復号手段から得られたビットをインターリーブするためのインターリーブ手段(43)と、
前記インターリーブ手段(43)から得られたビットを復号するための、パリティ手段と呼ばれる第2復号手段(42)と
を含み、前記インターリーブ手段(43)は、前記パリティ第2復号手段(42)がインターリーブの終了を待つことなく所定数Δのデータ項目がインターリーブされた後にパリティ復号を開始するようになされており、前記所定数Δのデータ項目は、前記インターリーブ手段(43)の1つまたは複数のパラメータに依存する第1低数Δiのデータ項目から、前記インターリーブ手段(43)によって処理されるデータ項目の総数に対応する第1高数Δsのデータ項目までの間であることを特徴とする装置。
【請求項２１】
通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに請求項1から11の少なくとも一項による符号化方法のステップを実行するためのプログラムコード命令を含むことを特徴とするコンピュータプログラム製品。
【請求項２２】
通信ネットワークからダウンロードされるように、および/またはコンピュータ読み取り可能メディア上に格納されるように、および/またはマイクロプロセッサによって実行されるように適合されているコンピュータプログラム製品であって、コンピュータ上で実行されたときに請求項12から18の少なくとも一項による復号方法のステップを実行するためのプログラムコード命令を含むことを特徴とするコンピュータプログラム製品。
【図１Ａ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【公表番号】特表２００９−５２４３１６（Ｐ２００９−５２４３１６Ａ）
【公表日】平成２１年６月２５日（２００９．６．２５）
【国際特許分類】
【出願番号】特願２００８−５５０８２２（Ｐ２００８−５５０８２２）
【出願日】平成１９年１月１８日（２００７．１．１８）
【国際出願番号】ＰＣＴ／ＦＲ２００７／０５０６６４
【国際公開番号】ＷＯ２００７／０８３０６６
【国際公開日】平成１９年７月２６日（２００７．７．２６）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
【公表日】平成２１年６月２５日（２００９．６．２５）
【国際特許分類】
【出願日】平成１９年１月１８日（２００７．１．１８）
【国際出願番号】ＰＣＴ／ＦＲ２００７／０５０６６４
【国際公開番号】ＷＯ２００７／０８３０６６
【国際公開日】平成１９年７月２６日（２００７．７．２６）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
[ Back to top ]