図面 (/)

技術 符号化および復号プロセスのためにシンボルの永久的非活動化とともにFEC符号を採用する方法および装置

出願人 クゥアルコム・インコーポレイテッド
発明者 ルビー、マイケル・ジー.ショクローラヒ、モハンマド・アミンミンダー、ロレンツ・クリストフ
出願日 2010年8月19日 (10年5ヶ月経過) 出願番号 2012-525696
公開日 2013年1月24日 (8年0ヶ月経過) 公開番号 2013-502849
状態 特許登録済
技術分野 符号誤り検出・訂正
主要キーワード 表ラベル 電子的要素 コード構成要素 消去イベント コンピューティング要素 伝搬ネット 合成セット ランダム順序
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2013年1月24日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題・解決手段

被符号化シンボルが、中間シンボルの第1のセットから生成された第1のシンボルと、中間シンボルの第2のセットから生成された第2のシンボルとの組合せから生成され、各セットが、少なくとも1つの異なるコーディングパラメータを有し、中間シンボルがソースシンボルのセットに基づいて生成される、複数の被符号化シンボルを符号化することが提供される。また、中間シンボルのセットが、受信された被符号化シンボルのセットから復号され、中間シンボルが復号のためのシンボルの第1および第2のセットに編成され、第2のセット中の中間シンボルが、被符号化シンボルから中間シンボルを復元するための復号プロセススケジュールする目的で永久的に非活動化され、ソースシンボルの少なくともいくつかが中間シンボルの復号されたセットから復元される、データを復号する方法が提供される。

概要

背景

通信チャネルを介した送信側と受信側との間のファイルの送信のための技法は、多くの文献の主題である。好ましくは、受信側は、ある程度の確度チャネルを介して送信側によって送信されたデータの正確なコピーを受信することを望む。チャネルが、(物理的に実現可能なほとんどすべてのシステムカバーする)完全な忠実度を有していない場合、1つの懸念は、送信中に損失されたまたはゆがめられたデータをどのように処理するかということである。受信側は、破損したデータがいつ間違って受信されたかを常に把握することができるわけではないので、損失したデータ(消去)は、破損したデータ(誤り)よりも、しばしば処理しやすい。消去および/または誤りを訂正するために多数の誤り訂正符号が開発されてきた。一般に、使用される特定の符号は、データが送信されているチャネルの不忠実度と、送信されているデータの性質とに関する何らかの情報に基づいて選定される。たとえば、チャネルが長い周期の不忠実度を有することが知られている場合、バースト誤り符号がその適用例に最も適しているだろう。ごく短い、まれにしか起こらない誤りが予想される場合、単純なパリティ符号最良であろう。

本明細書で使用する「ソースデータ」は、1つまたは複数の送信側において利用可能であるデータ、および受信機を使用して、誤りおよび/または消去を伴うまたは伴わない送信シーケンスからの復元によって取得されるデータなどを指す。本明細書で使用する「被符号化データ」は、搬送され、ソースデータを復元または取得するために使用され得るデータを指す。単純なケースでは、被符号化データはソースデータのコピーであるが、受信された被符号化データが、(誤りおよび/または消去により)送信された被符号化データとは異なる場合、この単純なケースでは、ソースデータは、ソースデータに関する追加のデータがなければ、完全には回復可能でないことがある。送信は空間または時間にわたって行われ得る。より複雑なケースでは、被符号化データは、変換においてソースデータに基づいて生成され、1つまたは複数の送信側から受信機に送信される。ソースデータが被符号化データの一部であることがわかる場合、符号化は「システマティック」であると言われる。システマティック符号化の単純な例では、被符号化データを形成するためにソースデータに関する冗長情報がソースデータの末尾に付加される。

また、本明細書で使用する「入力データ」は、FEC(順方向誤り訂正エンコーダ装置またはFECエンコーダモジュール、構成要素、ステップなど(「FECエンコーダ」)の入力に存在するデータを指し、「出力データ」は、FECエンコーダの出力に存在するデータを指す。相応して、出力データは、FECデコーダの入力に存在することが予想され、FECデコーダは、それが処理した出力データに基づいて、入力データ、またはその対応物を出力することが予想されるであろう。場合によっては、入力データはソースデータであるかまたはそれを含み、場合によっては、出力データは被符号化データであるかまたはそれを含む。他の場合には、送信側デバイスまたは送信側プログラムコードは2つ以上のFECエンコーダを備え得、すなわち、ソースデータは一連の複数のFECエンコーダ中で被符号化データに変換される。同様に、受信機において、受信された被符号化データからソースデータを生成するために適用される2つ以上のFECデコーダがあり得る。

データはシンボル区分されると考えられ得る。エンコーダは、ソースシンボルまたは入力シンボルシーケンスから被符号化シンボルまたは出力シンボルを生成するコンピュータシステムデバイス電子回路などであり、デコーダは、受信または復元された被符号化シンボルまたは出力シンボルからソースシンボルまたは入力シンボルのシーケンスを復元するカウンターパートである。エンコーダとデコーダとはチャネルによって時間的および/または空間的に分離されており、受信された被符号化シンボルは、対応する送信された被符号化シンボルとまったく同じではないことがあり、それらが送信されたシーケンスとまったく同じシーケンスで受信されないことがある。シンボルが実際にビットストリームに分解されるか否かにかかわらず、シンボルの「サイズ」はビットで測定され得、シンボルが2M個のシンボルのアルファベットから選択されたとき、シンボルはMビットのサイズを有する。本明細書の多くの例では、シンボルはバイトで測定され、符号は256個の可能性の領域(256個の可能な8ビットパターンがある)を超えることがあるが、データ測定の異なる単位が使用され得ることと、様々な方法でデータを測定することがよく知られていることとを理解されたい。

Luby Iには、計算効率的、メモリ効率的および帯域幅効率的な方法で誤り訂正対処するための、連鎖反応(chain reaction)符号などの符号の使用が記載されている。連鎖反応エンコーダによって生成される被符号化シンボルの1つの特性は、受信機が、十分な被符号化シンボルが受信されるとすぐに元のファイルを復元することが可能であることである。詳細には、元のK個のソースシンボルを高い確率で復元するために、受信機は、約K+A個の被符号化シンボルを必要とする。

所与の状況についての「絶対受信オーバーヘッド」は値Aによって表され、「相対受信オーバーヘッド」は比A/Kとして計算され得る。絶対受信オーバーヘッドは、どのくらいの余分のデータが情報理論的最小データ量を超えて受信される必要があるかの測度であり、デコーダの信頼性に依存し得、ソースシンボルの数Kに応じて変動し得る。同様に、相対受信オーバーヘッドA/Kは、復元されているソースデータのサイズに対して、どのくらいの余分のデータが情報理論的最小データ量を超えて受信される必要があるかの測度であり、同じくデコーダの信頼性に依存し得、ソースシンボルの数Kに応じて変動し得る。

連鎖反応符号は、パケットベースネットワークを介した通信のために極めて有用である。しかしながら、それらは時々かなり計算集約的であり得る。連鎖反応符号または別のレートレス(rateless)符号を使用して符号化する動的エンコーダより前に静的エンコーダを使用してソースシンボルが符号化される場合、デコーダは、より頻繁にまたはより容易に復号することが可能であり得る。そのようなデコーダは、たとえば、Shokrollahi Iに示されている。そこに示されている例では、ソースシンボルは静的エンコーダへの入力シンボルであり、静的エンコーダは、動的エンコーダへの入力シンボルである出力シンボルを生成し、動的エンコーダは、被符号化シンボルである出力シンボルを生成し、ただし、動的エンコーダは、入力シンボルの数に対して固定レートでない量のいくつかの出力シンボルを生成することができるレートレスエンコーダである。静的エンコーダは、2つ以上の固定レートエンコーダを含み得る。たとえば、静的エンコーダは、ハミング(Hamming)エンコーダ、低密度パリティ検査(「LDPC:low-density parity-check」)エンコーダ、高密度パリティ検査(「HDPC:high-density parity-check」)エンコーダなどを含み得る。

連鎖反応符号は、いくつかのシンボルが受信シンボルからデコーダにおいて復元されるとき、それらのシンボルを使用して追加のシンボルを復元することが可能であり得、今度はその追加のシンボルを使用してさらに多くのシンボルを復元し得るという特性を有する。好ましくは、デコーダにおけるシンボル解決の連鎖反応は、受信シンボルのプール使い果たされる前に所望のシンボルのすべてが復元されるように続くことができる。好ましくは、連鎖反応符号化および復号プロセスを実行することの計算複雑さは低い。

デコーダにおける復元プロセスは、どのシンボルが受信されたかを判断することと、元の入力シンボルを受信された被符号化シンボルにマッピングするであろう行列を作成することと、次いで行列を反転させ、反転した行列と受信された被符号化シンボルのベクトルとの行列乗算を実行することとに関与し得る。典型的なシステムでは、これのブルートフォース(brute force)実装形態は、過大な計算作業とメモリ要件とを消費し得る。もちろん、受信された被符号化シンボルの特定のセットについて、元の入力シンボルのすべてを復元することは不可能であり得るが、それが可能である場合でも、結果を計算することは極めて計算コストが高くなり得る。

Shokrollahi IIには、復号が2つのステップで行われる「非活動化(inactivation)」と呼ばれる手法が記載されている。第1のステップでは、デコーダは、どのような受信された被符号化シンボルが利用可能であるか、行列がどのように見え得るかを評価し、受信された被符号化シンボルを仮定すれば、連鎖反応プロセスを完了させることを可能にするであろう復号ステップのシーケンスを少なくとも概算的に判断する。第2のステップでは、デコーダは、復号ステップの判断されたシーケンスに従って連鎖反応復号を実行する。これは、メモリ効率的な方法(すなわち、よりメモリ非効率的なプロセスほどには演算のためのメモリストレージを必要としない方法)で行われ得る。

非活動化手法では、第1の復号ステップは、解決され得るいくつかの入力シンボルを判断するために行列またはそれの等価物を操作することと、判断がストールしたとき、入力シンボルのうちの1つを「非活動化シンボル」として指定し、非活動化シンボルが実際は解決されると仮定して判断プロセスを継続することと、次いで最後に、ガウス消去法、または元の復号行列よりもはるかに小さい行列を反転させるための何らかの他の方法を使用して非活動化シンボルを解決することとに関与する。その判断を使用して、元の入力シンボルのすべてまたは元の入力シンボルの好適なセットのいずれかであり得る復元された入力シンボルに到達するために、受信された被符号化シンボルに対して連鎖反応シーケンスが実行され得る。

限られたメモリおよび計算能力をもつ低電力デバイス中にデコーダがある場合など、あるいは許容できる絶対または相対受信オーバーヘッドに対する厳しい制約があるときなど、デコーダに対して厳しい制約を課するいくつかの適用例では、上記で説明した非活動化手法に比較して改善された方法が示され得る。

また、ファイルまたは大きいデータブロックを、最小サブシンボルサイズに対する制約を条件として、できるだけ少数ソースブロックに区分し、さらに、これを条件として、最大サブブロックサイズに対する制約を条件として、できるだけ少数のサブブロックに分割するための方法が有用であり得る。

概要

被符号化シンボルが、中間シンボルの第1のセットから生成された第1のシンボルと、中間シンボルの第2のセットから生成された第2のシンボルとの組合せから生成され、各セットが、少なくとも1つの異なるコーディングパラメータを有し、中間シンボルがソースシンボルのセットに基づいて生成される、複数の被符号化シンボルを符号化することが提供される。また、中間シンボルのセットが、受信された被符号化シンボルのセットから復号され、中間シンボルが復号のためのシンボルの第1および第2のセットに編成され、第2のセット中の中間シンボルが、被符号化シンボルから中間シンボルを復元するための復号プロセスをスケジュールする目的で永久的に非活動化され、ソースシンボルの少なくともいくつかが中間シンボルの復号されたセットから復元される、データを復号する方法が提供される。

目的

すべてのそのような場合において、問題は、すべての送信データが受信側に対して独立に使用されること、すなわち、異なるストリームについて送信レートが非常に異なるとき、および恣意的な損失パターンがあるときでも、複数のソースデータがストリーム間冗長でないことを保証することである

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

電子信号を出力することが可能な1つまたは複数の送信機を介してデータを電子的に送信する方法であって、送信されるべき前記データがソースシンボル順序セットによって表され、前記データが、前記電子信号の少なくとも一部分を表す一連被符号化シンボルとして送信され、前記方法は、電子的に読取り可能な形態で、ソースシンボルの前記順序セットを取得することと、ソースシンボルの前記順序セットから中間シンボルのセットを生成することであって、前記ソースシンボルが中間シンボルの前記セットから再生され得る、中間シンボルのセットを生成することと、各中間シンボルが中間シンボルの前記セットのうちの1つのメンバーに指定され、少なくとも中間シンボルの第1のセットおよび中間シンボルの第2のセットがあるように、前記中間シンボルの前記セットを指定することであって、中間シンボルの各セットが、別個符号化パラメータと関連付けられており、少なくとも1つの中間シンボルをメンバーとして有する、指定することと、複数の被符号化シンボルを生成することであって、被符号化シンボルが前記中間シンボルのうちの1つまたは複数から生成され、少なくとも1つの被符号化シンボルが、直接または間接的に、中間シンボルの複数の前記セットから選択された複数の中間シンボルから生成される、複数の被符号化シンボルを生成することとを備える方法。

請求項2

中間シンボルの前記第1のセットが、信念伝搬復号のためのシンボルに指定され、中間シンボルの前記第2のセットが、信念伝搬復号のための非活動化されるべきシンボルに指定される、請求項1に記載の方法。

請求項3

各被符号化シンボルが、中間シンボルの前記第1のセットのうちの1つまたは複数から生成された第1のシンボルと、中間シンボルの前記第2のセットのうちの1つまたは複数から生成された第2のシンボルとの組合せから生成される、請求項1に記載の方法。

請求項4

各被符号化シンボルが、第1の度数分布を有する中間シンボルの前記第1のセットのうちの1つまたは複数から生成された第1のシンボルと、前記第1の度数分布とは異なる第2の度数分布を有する中間シンボルの前記第2のセットのうちの1つまたは複数から生成された第2のシンボルとの組合せから生成されるように、前記別個の符号化パラメータが少なくとも別個の度数分布を備える、請求項3に記載の方法。

請求項5

前記第1のシンボルが、中間シンボルの前記第1のセットに適用される連鎖反応符号化プロセスを使用して生成される、請求項3に記載の方法。

請求項6

前記第2のシンボルが、中間シンボルの前記第2のセットからランダム選定された固定数のシンボルのXORである、請求項3に記載の方法。

請求項7

前記第2のシンボルが、中間シンボルの前記第2のセットからランダムに選定された第1の数のシンボルのXORであり、前記第1の数が、前記第1のシンボルを生成するために前記第1のセットから選定された前記シンボルの数に等しい第2の数に依存する、請求項3に記載の方法。

請求項8

前記組合せが、前記第1のシンボルと前記第2のシンボルとの前記XORである、請求項3に記載の方法。

請求項9

前記中間シンボルが、ソースシンボルの前記順序セットと、ソースシンボルの前記順序セットから生成された冗長ソースシンボルのセットとを備える、請求項1に記載の方法。

請求項10

前記冗長シンボルの少なくともいくつかがGF[2]演算を使用して生成され、他の冗長シンボルがGF[256]演算を使用して生成される、請求項9に記載の方法。

請求項11

前記中間シンボルが、符号化中に、復号プロセスを使用して前記ソースシンボルから生成され、前記復号プロセスが、前記中間シンボルと前記ソースシンボルとの間の関係の線形セットに基づく、請求項1に記載の方法。

請求項12

前記線形関係の少なくともいくつかがGF[2]に関する関係であり、他の線形関係がGF[256]に関する関係である、請求項11に記載の方法。

請求項13

ソースシンボルの所与の順序セットから生成され得る別個の被符号化シンボルの数が、その順序セット中のソースシンボルの数とは無関係である、請求項1に記載の方法。

請求項14

被符号化シンボルを生成するために実行されるシンボル演算の平均数が、その順序セット中のソースシンボルの数とは無関係である定数によって制限される、請求項1に記載の方法。

請求項15

シンボルの前記第1のセットがシンボルの前記第2のセットよりも2桁以上大きい、請求項1に記載の方法。

請求項16

ソースからデータを受信する方法であって、前記データがパケット通信チャネルを介して宛先において受信され、ソースシンボルの順序セットから導出された被符号化シンボルのセットによって表現可能な前記データが、前記ソースから前記宛先に送られた前記データを表し、前記方法は、受信された被符号化シンボルの前記セットを取得することと、受信された被符号化シンボルの前記セットから中間シンボルのセットを復号することと、前記中間シンボルの各々を中間シンボルのセットに関連付けることであって、前記中間シンボルが少なくとも2つのセットに関連付けられ、1つのセットが、前記受信された被符号化シンボルから前記中間シンボルを復元するための復号プロセスをスケジュールするために永久非活動シンボルのセットに指定される、関連付けることと、前記復号プロセスに従って中間シンボルの前記セットから、ソースシンボルの前記順序セットの前記ソースシンボルの少なくともいくつかを復元することとを備える方法。

請求項17

前記復号プロセスは、少なくとも、永久的非活動シンボルの第2のセットと、シンボルの前記第1のセットのサブセットである動的非活動シンボルの第3のセットとに依存する、低減された被符号化シンボルのセットが生成される第1の復号段階と、低減された被符号化シンボルの前記セットが、永久的非活動シンボルの前記第2のセットと動的非活動シンボルの前記第3のセットとを復号するために使用される第2の復号段階と、永久的非活動シンボルの前記復号された第2のセット、動的非活動シンボルの前記第3のセット、および受信された被符号化シンボルの前記セットが、シンボルの前記第1のセット中にある残りの中間シンボルの少なくともいくつかを復号するために使用される第3の復号段階とを備える、請求項16に記載の方法。

請求項18

前記第1の復号段階が、非活動化復号と組み合わされた信念伝搬復号を使用し、および/または前記第2の復号段階がガウス消去法を使用する、請求項17に記載の方法。

請求項19

前記第3の復号段階が、後退代入、または後退掃引後続前進掃引を使用する、請求項17に記載の方法。

請求項20

動的非活動シンボルの第3のセット中のシンボルの数がソースシンボルの数の10%よりも少なく、および/または永久的非活動化シンボルの前記第2のセット中のシンボルの数の10%よりも少ないことを考慮して、前記復号プロセスが、動的非活動シンボルの前記第3のセットに対して演算する、請求項17に記載の方法。

請求項21

前記受信された被符号化シンボルが、LDPC符号生成シンボルまたはリードソロモン符号生成シンボルとして演算される、請求項16に記載の方法。

請求項22

受信された被符号化シンボルの前記セットの各受信された被符号化シンボルが、シンボルの前記第1のセットのうちの1つまたは複数から生成された第1のシンボルと、シンボルの前記第2のセットのうちの1つまたは複数から生成された第2のシンボルとの組合せであるものとして演算される、請求項16に記載の方法。

請求項23

各受信された被符号化シンボルが、前記第1のシンボルと前記第2のシンボルとのXORである前記組合せとして演算される、請求項22に記載の方法。

請求項24

各受信された被符号化シンボルが、前記第2のセットからランダムに選定された固定数のシンボルのXORである前記第2のシンボルとして演算される、請求項22に記載の方法。

請求項25

各受信された被符号化シンボルが、前記第2のセットからランダムに選定された第1の数のシンボルのXORである前記第2のシンボルとして演算され、シンボルの前記第1の数が、前記第1のシンボルを生成するために前記第1のセットから選定されたシンボルの前記第2の数に依存する、請求項22に記載の方法。

請求項26

前記復号プロセスは、前記第1のシンボルがシンボルの前記第1のセットから連鎖反応符号に基づいて選定されたかのように演算する、請求項22に記載の方法。

請求項27

前記復号プロセスは、永久的非活動シンボルの前記第2のセットのサイズがソースシンボルの数の平方根に比例するかのように演算する、請求項16に記載の方法。

請求項28

前記復号プロセスは、前記中間シンボルが、ソースシンボルの前記順序セットと、ソースシンボルの前記順序セットから生成された冗長シンボルのセットとを備えるかのように演算する、請求項16に記載の方法。

請求項29

前記復号プロセスは、前記冗長シンボルの少なくともいくつかがGF[2]演算を使用して生成され、他の冗長シンボルがGF[256]演算を使用して生成されたかのように演算する、請求項28に記載の方法。

請求項30

前記復号プロセスは、前記中間シンボルがソースシンボルの前記順序セットを備えるかのように演算する、請求項16に記載の方法。

請求項31

前記復号プロセスは、前記中間シンボルが、前記中間シンボルと前記ソースシンボルとの間の関係の線形セットに基づく復号プロセスを使用して前記ソースシンボルから生成されたシンボルであるかのように演算する、請求項16に記載の方法。

請求項32

前記復号プロセスは、前記線形関係の少なくともいくつかがGF[2]に関する関係であり、他の線形関係がGF[256]に関する関係であるかのように演算する、請求項31に記載の方法。

請求項33

前記復号プロセスは、受信され得る異なる可能な被符号化シンボルの数が、前記順序セット中のソースシンボルの数とは無関係であるかのように演算する、請求項16に記載の方法。

請求項34

受信された被符号化シンボルの前記セットからのソースシンボルの前記セットを復号するために実行されるシンボル演算の平均数が、ソースシンボルの数の定数倍によって制限され、前記定数がソースシンボルの数とは無関係である、請求項16に記載の方法。

請求項35

前記復号プロセスは、シンボルの前記第1のセット中のシンボルの数が、永久的非活動シンボルの前記第2のセット中のシンボルの数よりも2桁以上大きいかのように演算する、請求項16に記載の方法。

請求項36

あるK、NおよびAについて、N=K+A個の被符号化シンボルのセットからのK個のソースシンボルの前記セットのすべての復元は、A=0、1または2の場合、少なくとも下限の成功の確率1−(0.01)^(A+1)を有し、前記下限がソースシンボルの数とは無関係であるように、前記復号プロセスが演算する、請求項16に記載の方法。

請求項37

データネットワークに結合されたサーバを使用してファイルサービスするための方法であって、サービスすることが、前記ファイルのデータを1つまたは複数のブロックに編成し、ブロックの前記データに基づいて前記ブロックのための1つまたは複数の被符号化シンボルを生成することを含み、少なくとも1つのブロックが物理的にまたは論理的に複数のサブブロックに編成され、少なくとも1つの被符号化シンボルが物理的にまたは論理的に複数のサブシンボルに編成され、前記方法は、入力ファイル整数個のブロックに区分することであって、各ブロックが少なくとも1つのサブブロックを含み、各サブブロックが少なくとも1つのソースシンボルを含む、区分することと、メモリ制約に基づいてサブブロックの最大サイズを表す値WSを判断することと、値SSを判断することであって、SS*ALが、好適なメモリユニットサイズALの単位で、サブシンボルサイズの下限を表す、値SSを判断することと、前記整数個のブロックのうちのどのブロックが複数のサブブロックに編成されるべきかを判断することと、そのようなブロックごとに、ソースブロックのためのソースシンボルの数がしきい値内で等しく、前記数が前記ファイル中のソースシンボルの前記数Ktに等しいことを保証し、各サブブロックの前記サブシンボルサイズが高々SS*ALであることを保証し、各サブブロックの前記サイズが高々WSであることを保証する方法で、送られるべき被符号化シンボルのパケット内の利用可能な空間によって判断されたサイズ、各送られるパケット内で使用されるべきシンボルサイズを有する複数のサブブロックに前記ブロックを編成することと、ブロックから被符号化シンボルを生成することであって、各被符号化シンボルが1つのブロックからのデータに依存するように、サブシンボルがサブブロックから生成される、生成することと、前記生成された被符号化シンボルを出力することとを備える方法。

請求項38

データネットワークに結合されたクライアントを使用して受信機におけるデータのブロックを復元するための方法であって、ブロックが1つまたは複数のサブブロックのグルーピングを含み、前記方法は、前記ブロックから生成された複数の被符号化シンボルを受信することであって、各被符号化シンボルが、演算の共通のセットを使用して少なくとも1つのサブブロックから生成された複数のサブシンボルを含む、受信することと、メモリ制約に基づいてサブブロックの最大サイズを表す値WSを判断することと、値SSを判断することであって、SS*ALが、好適なメモリユニットサイズALの単位で、サブシンボルサイズの下限を表す、値SSを判断することと、整数個のブロックのうちのどのブロックが複数のサブブロックに編成されるべきかを判断することと、そのようなブロックごとに、パケット内の利用可能な空間を表す、送信側によって設定された第1のパラメータ、各パケット内で使用されるシンボルサイズを表す第2のパラメータによって判断されたサイズを有する複数のサブブロックに前記ブロックを編成することであって、前記パラメータは、ソースブロックのためのソースシンボルの数がしきい値内で等しく、前記数が前記ファイル中のソースシンボルの前記数Ktに等しくなるようなものである、編成することと、受信された被符号化シンボルからブロックを復号することであって、サブブロックがサブシンボルから復号され、前記サブブロックがブロックを形成し、各サブブロックの前記サブシンボルサイズが高々SS*ALであり、各サブブロックの前記サイズが高々WSである、復号することと、前記復号されたブロックを出力することとを備える方法。

技術分野

0001

相互参照
本出願は、M.Amin Shokrollahiらの、2009年10月23日に出願された「Method and Apparatus Employing FEC Codes with Permanent Inactivation of Symbols for Encoding and Decoding Processes」と題する米国特許出願第12/604,773号の一部継続出願であり、さらに、それぞれM.Amin Shokrollahiらの、それぞれ「Method and Apparatus Employing FEC Codes with Permanent Inactivation of Symbols for Encoding and Decoding Processes」と題する、2010年6月11日に出願された米国仮特許出願第61/353,910号、2009年11月2日に出願された米国仮特許出願第61/257,146号、および2009年8月19日に出願された米国仮特許出願第61/235,285号の優先権を主張する。上記の各仮出願および非仮出願は、すべての目的のために参照により本明細書に組み込まれる。

0002

以下の参考文献は、すべての目的のためにそれらの全体が参照により本明細書に組み込まれる。

0003

1)Michael G.Lubyに発行された「Information Additive Code Generator and Decoder for Communication Systems」と題する米国特許第6,307,487号(以下「Luby I」)、
2)Michael G.Lubyに発行された「Information Additive Group Code Generator and Decoder for Communication Systems」と題する米国特許第6,320,520号(以下「Luby II」)、
3)M.Amin Shokrollahiに発行された「Multi-Stage Code Generator and Decoder for Communication Systems」と題する米国特許第7,068,729号(以下「Shokrollahi I」)、
4)M.Amin Shokrollahiに発行された「Systems and Processes for Decoding a Chain Reaction Code Through Inactivation」と題する米国特許第6,856,263号(以下「Shokrollahi II」)、
5)M.Amin Shokrollahiに発行された「Systematic Encoding and Decoding of Chain Reaction Codes」と題する米国特許第6,909,383号(以下「Shokrollahi III」)、
6)Michael G.LubyおよびM.Amin Shokrollahiの、「In-Place Transformations with Applications to Encoding and Decoding Various Classes of Codes」と題する米国特許公開第2006/0280254号(以下「Luby III」)、
7)M.Amin Shokrollahiの、「Multiple-Field Based Code Generator and Decoder for Communications Systems」と題する米国特許公開第2007/0195894号(以下「Shokrollahi IV」)。

0004

本発明は、通信ステム中でデータを符号化および復号することに関し、より詳細には、効率的な方法で、通信されたデータ中の誤りおよびギャップをなくすためにデータを符号化および復号する通信システムに関する。

背景技術

0005

通信チャネルを介した送信側と受信側との間のファイルの送信のための技法は、多くの文献の主題である。好ましくは、受信側は、ある程度の確度チャネルを介して送信側によって送信されたデータの正確なコピーを受信することを望む。チャネルが、(物理的に実現可能なほとんどすべてのシステムをカバーする)完全な忠実度を有していない場合、1つの懸念は、送信中に損失されたまたはゆがめられたデータをどのように処理するかということである。受信側は、破損したデータがいつ間違って受信されたかを常に把握することができるわけではないので、損失したデータ(消去)は、破損したデータ(誤り)よりも、しばしば処理しやすい。消去および/または誤りを訂正するために多数の誤り訂正符号が開発されてきた。一般に、使用される特定の符号は、データが送信されているチャネルの不忠実度と、送信されているデータの性質とに関する何らかの情報に基づいて選定される。たとえば、チャネルが長い周期の不忠実度を有することが知られている場合、バースト誤り符号がその適用例に最も適しているだろう。ごく短い、まれにしか起こらない誤りが予想される場合、単純なパリティ符号最良であろう。

0006

本明細書で使用する「ソースデータ」は、1つまたは複数の送信側において利用可能であるデータ、および受信機を使用して、誤りおよび/または消去を伴うまたは伴わない送信シーケンスからの復元によって取得されるデータなどを指す。本明細書で使用する「被符号化データ」は、搬送され、ソースデータを復元または取得するために使用され得るデータを指す。単純なケースでは、被符号化データはソースデータのコピーであるが、受信された被符号化データが、(誤りおよび/または消去により)送信された被符号化データとは異なる場合、この単純なケースでは、ソースデータは、ソースデータに関する追加のデータがなければ、完全には回復可能でないことがある。送信は空間または時間にわたって行われ得る。より複雑なケースでは、被符号化データは、変換においてソースデータに基づいて生成され、1つまたは複数の送信側から受信機に送信される。ソースデータが被符号化データの一部であることがわかる場合、符号化は「システマティック」であると言われる。システマティック符号化の単純な例では、被符号化データを形成するためにソースデータに関する冗長情報がソースデータの末尾に付加される。

0007

また、本明細書で使用する「入力データ」は、FEC(順方向誤り訂正エンコーダ装置またはFECエンコーダモジュール、構成要素、ステップなど(「FECエンコーダ」)の入力に存在するデータを指し、「出力データ」は、FECエンコーダの出力に存在するデータを指す。相応して、出力データは、FECデコーダの入力に存在することが予想され、FECデコーダは、それが処理した出力データに基づいて、入力データ、またはその対応物を出力することが予想されるであろう。場合によっては、入力データはソースデータであるかまたはそれを含み、場合によっては、出力データは被符号化データであるかまたはそれを含む。他の場合には、送信側デバイスまたは送信側プログラムコードは2つ以上のFECエンコーダを備え得、すなわち、ソースデータは一連の複数のFECエンコーダ中で被符号化データに変換される。同様に、受信機において、受信された被符号化データからソースデータを生成するために適用される2つ以上のFECデコーダがあり得る。

0008

データはシンボル区分されると考えられ得る。エンコーダは、ソースシンボルまたは入力シンボルシーケンスから被符号化シンボルまたは出力シンボルを生成するコンピュータシステムデバイス電子回路などであり、デコーダは、受信または復元された被符号化シンボルまたは出力シンボルからソースシンボルまたは入力シンボルのシーケンスを復元するカウンターパートである。エンコーダとデコーダとはチャネルによって時間的および/または空間的に分離されており、受信された被符号化シンボルは、対応する送信された被符号化シンボルとまったく同じではないことがあり、それらが送信されたシーケンスとまったく同じシーケンスで受信されないことがある。シンボルが実際にビットストリームに分解されるか否かにかかわらず、シンボルの「サイズ」はビットで測定され得、シンボルが2M個のシンボルのアルファベットから選択されたとき、シンボルはMビットのサイズを有する。本明細書の多くの例では、シンボルはバイトで測定され、符号は256個の可能性の領域(256個の可能な8ビットパターンがある)を超えることがあるが、データ測定の異なる単位が使用され得ることと、様々な方法でデータを測定することがよく知られていることとを理解されたい。

0009

Luby Iには、計算効率的、メモリ効率的および帯域幅効率的な方法で誤り訂正対処するための、連鎖反応(chain reaction)符号などの符号の使用が記載されている。連鎖反応エンコーダによって生成される被符号化シンボルの1つの特性は、受信機が、十分な被符号化シンボルが受信されるとすぐに元のファイルを復元することが可能であることである。詳細には、元のK個のソースシンボルを高い確率で復元するために、受信機は、約K+A個の被符号化シンボルを必要とする。

0010

所与の状況についての「絶対受信オーバーヘッド」は値Aによって表され、「相対受信オーバーヘッド」は比A/Kとして計算され得る。絶対受信オーバーヘッドは、どのくらいの余分のデータが情報理論的最小データ量を超えて受信される必要があるかの測度であり、デコーダの信頼性に依存し得、ソースシンボルの数Kに応じて変動し得る。同様に、相対受信オーバーヘッドA/Kは、復元されているソースデータのサイズに対して、どのくらいの余分のデータが情報理論的最小データ量を超えて受信される必要があるかの測度であり、同じくデコーダの信頼性に依存し得、ソースシンボルの数Kに応じて変動し得る。

0011

連鎖反応符号は、パケットベースネットワークを介した通信のために極めて有用である。しかしながら、それらは時々かなり計算集約的であり得る。連鎖反応符号または別のレートレス(rateless)符号を使用して符号化する動的エンコーダより前に静的エンコーダを使用してソースシンボルが符号化される場合、デコーダは、より頻繁にまたはより容易に復号することが可能であり得る。そのようなデコーダは、たとえば、Shokrollahi Iに示されている。そこに示されている例では、ソースシンボルは静的エンコーダへの入力シンボルであり、静的エンコーダは、動的エンコーダへの入力シンボルである出力シンボルを生成し、動的エンコーダは、被符号化シンボルである出力シンボルを生成し、ただし、動的エンコーダは、入力シンボルの数に対して固定レートでない量のいくつかの出力シンボルを生成することができるレートレスエンコーダである。静的エンコーダは、2つ以上の固定レートエンコーダを含み得る。たとえば、静的エンコーダは、ハミング(Hamming)エンコーダ、低密度パリティ検査(「LDPC:low-density parity-check」)エンコーダ、高密度パリティ検査(「HDPC:high-density parity-check」)エンコーダなどを含み得る。

0012

連鎖反応符号は、いくつかのシンボルが受信シンボルからデコーダにおいて復元されるとき、それらのシンボルを使用して追加のシンボルを復元することが可能であり得、今度はその追加のシンボルを使用してさらに多くのシンボルを復元し得るという特性を有する。好ましくは、デコーダにおけるシンボル解決の連鎖反応は、受信シンボルのプール使い果たされる前に所望のシンボルのすべてが復元されるように続くことができる。好ましくは、連鎖反応符号化および復号プロセスを実行することの計算複雑さは低い。

0013

デコーダにおける復元プロセスは、どのシンボルが受信されたかを判断することと、元の入力シンボルを受信された被符号化シンボルにマッピングするであろう行列を作成することと、次いで行列を反転させ、反転した行列と受信された被符号化シンボルのベクトルとの行列乗算を実行することとに関与し得る。典型的なシステムでは、これのブルートフォース(brute force)実装形態は、過大な計算作業とメモリ要件とを消費し得る。もちろん、受信された被符号化シンボルの特定のセットについて、元の入力シンボルのすべてを復元することは不可能であり得るが、それが可能である場合でも、結果を計算することは極めて計算コストが高くなり得る。

0014

Shokrollahi IIには、復号が2つのステップで行われる「非活動化(inactivation)」と呼ばれる手法が記載されている。第1のステップでは、デコーダは、どのような受信された被符号化シンボルが利用可能であるか、行列がどのように見え得るかを評価し、受信された被符号化シンボルを仮定すれば、連鎖反応プロセスを完了させることを可能にするであろう復号ステップのシーケンスを少なくとも概算的に判断する。第2のステップでは、デコーダは、復号ステップの判断されたシーケンスに従って連鎖反応復号を実行する。これは、メモリ効率的な方法(すなわち、よりメモリ非効率的なプロセスほどには演算のためのメモリストレージを必要としない方法)で行われ得る。

0015

非活動化手法では、第1の復号ステップは、解決され得るいくつかの入力シンボルを判断するために行列またはそれの等価物を操作することと、判断がストールしたとき、入力シンボルのうちの1つを「非活動化シンボル」として指定し、非活動化シンボルが実際は解決されると仮定して判断プロセスを継続することと、次いで最後に、ガウス消去法、または元の復号行列よりもはるかに小さい行列を反転させるための何らかの他の方法を使用して非活動化シンボルを解決することとに関与する。その判断を使用して、元の入力シンボルのすべてまたは元の入力シンボルの好適なセットのいずれかであり得る復元された入力シンボルに到達するために、受信された被符号化シンボルに対して連鎖反応シーケンスが実行され得る。

0016

限られたメモリおよび計算能力をもつ低電力デバイス中にデコーダがある場合など、あるいは許容できる絶対または相対受信オーバーヘッドに対する厳しい制約があるときなど、デコーダに対して厳しい制約を課するいくつかの適用例では、上記で説明した非活動化手法に比較して改善された方法が示され得る。

0017

また、ファイルまたは大きいデータブロックを、最小サブシンボルサイズに対する制約を条件として、できるだけ少数ソースブロックに区分し、さらに、これを条件として、最大サブブロックサイズに対する制約を条件として、できるだけ少数のサブブロックに分割するための方法が有用であり得る。

0018

本発明の態様によるエンコーダの一実施形態によれば、送信側におけるエンコーダ、送信側の中のエンコーダ、または送信側のためのエンコーダが、通信チャネルを介して1つまたは複数の送信側から1つまたは複数の受信機にソースシンボルの順序セットを送信し、エンコーダは、ソースシンボルから生成される複数の被符号化シンボルを含む、送られるべきデータを生成する。第1のステップでは、中間シンボルは、可逆である方法を使用してソースシンボルから生成され、すなわち、中間シンボルからソースシンボルを生成するための逆方法もある。別のステップでは、中間シンボルは、中間シンボルの第1のセットと中間シンボルの第2のセットとに区分され、少なくとも1つの中間シンボルが中間シンボルの第1のセット中にあり、少なくとも1つの中間シンボルが中間シンボルの第2のセット中にあり、少なくとも1つの被符号化シンボルが、2つのセットの各々からの少なくとも1つの中間シンボルから生成される。いくつかの変形態では、3つ以上のセットがある。

0019

いくつかの実施形態では、一時的シンボルの第1のセットおよび第2のセットの値が生成され、一時的シンボルの第1のセットのための値が中間シンボルの第1のセットの値に依存し、一時的シンボルの第2のセットの値が中間シンボルの第2のセットの値に依存する。被符号化シンボルの値は、一時的シンボルの第1のセットおよび第2のセットから生成される。

0020

いくつかの変形態では、生成され得る被符号化シンボルの数は、ソースシンボルの数とは無関係である。

0021

また、デコーダ実施形態が提供される。本発明の態様によるデコーダの一実施形態によれば、受信機におけるデコーダ、受信機中のデコーダ、または受信機のためのデコーダが中間シンボルから生成された被符号化シンボルを受信し、中間シンボルは、可逆である方法を使用してソースシンボルから生成され、すなわち、中間シンボルからソースシンボルを生成するための逆方法もあり、中間シンボルのうちの少なくとも1つが永久非活動シンボルに指定され、永久的非活動シンボルのうちにない中間シンボルのうちの少なくとも別の1つがある。デコーダは、受信された被符号化シンボルから中間シンボルのセットを復号し、デコーダは、少なくとも1つの永久的非活動シンボルを考慮に入れ、逆方法を使用して中間シンボルの復号されたセットからソースシンボルを生成する。

0022

復号では、永久的非活動シンボルのスケジューリングを除外して、復号ステップがスケジュールされる。永久的非活動シンボルは、新規の方法または従来の方法を使用して解決され、さらには他の中間シンボルについて解決する際に使用され得る。永久的非活動シンボル(および使用する場合、他のオンザフライ非活動化)について解決する1つの手法は、非活動シンボルについて解決するためにガウス消去法を適用することであり得る。残りの中間シンボルのいくつかは、復元された永久的非活動シンボルの値と受信された被符号化シンボルの値とに基づいて復元される。

0023

復号方法のいくつかの変形態では、永久的非活動シンボルは、符号化実施形態からの中間シンボルの第2のセットを備える。復号方法のいくつかの変形態では、永久的非活動シンボルは中間シンボルのサブセットを備え、対応する符号化方法マルチステージ連鎖反応符号ではない。そのような符号化方法は、中間シンボルのサブセットのためのトルネード符号、リードソロモン符号、連鎖反応符号(Luby Iに記載されている例)などのうちの1つまたは複数を含み得る。

0024

中間シンボルは、符号化および復号のために使用され、ソースシンボルから中間シンボルを生成するための方法および対応する逆方法は、復号可能性など、パフォーマンス特性の所望のセットのために示される。いくつかの実施形態では、中間シンボルはソースシンボルを備える。いくつかの実施形態では、中間シンボルは、ソースシンボルから生成される冗長シンボルとともにソースシンボルを備え、冗長シンボルは、連鎖反応シンボル、LDPCシンボル、HDPCシンボルまたは他のタイプの冗長シンボルであり得る。代替的に、中間シンボルは、シンボル間の規定関係、たとえば、中間シンボルとソースシンボルとの間の関係、ならびに中間シンボル間の追加のLDPCおよびHDPC関係に基づき得、復号方法は、規定関係に基づいてソースシンボルから中間シンボルを生成するために使用される。

0025

電子回路によって、またはプログラミング命令を実行し、符号化および/または復号を実装するために適切な命令プログラムコードを有する処理デバイスによって、それらの方法およびシステムが実装され得る。

0026

多数の利益が本発明によって達成される。たとえば、特定の実施形態において、チャネルを介した送信のためにデータを符号化する計算費用は低減される。別の特定の実施形態では、そのようなデータを復号する計算費用は低減される。別の特定の実施形態では、絶対および相対受信オーバーヘッドは実質的に低減される。実施形態に応じて、これらの利益の1つまたは複数が達成され得る。これらおよび他の利益は、本願明細書全体にわたって、特に以下に、より詳細に与えられる。

0027

本明細書の残りの部分および添付の図面を参照すれば、本明細書で開示する本発明の性質および利点をさらに理解することができる。

図面の簡単な説明

0028

他の特徴および要素とともに、永久的非活動化を含むマルチステージコーディングを使用する通信システムのブロック図。
本明細書で様々な他の図において使用される変数アレイなどのテーブルの図。
図1に示すエンコーダの特定の実施形態のブロック図。
図3の動的エンコーダをより詳細に示すブロック図。
永久的非活動化(PI:permanent inactivation)符号化プロセスを示すフローチャート
動的符号化プロセスを示すフローチャート。
シンボル計算のための重みを計算する演算のフローチャート。
ルックアップ値に基づいてシンボルの度数を判断するために使用可能な、メモリに記憶され得るテーブルを示す図。
符号化または復号プロセスにおいて使用される行列を示す図。
特定の最小多項式について、図9に示す行列の一部を表す式を示す図。
符号化または復号において使用するアレイをセットアップするためのプロセスを示すフローチャート。
R個の静的シンボルを表す部分行列SE、またはデコーダによって知られる式を使用して、受信された被符号化シンボルを表すアレイD()から、復元されたソースシンボルを表すアレイC()を復元するためにデコーダによって解かれるべき式のセットの行列表現を示す図。
OTF非活動化を使用して、図12の行列の行/列置換から生じる行列を示す図。
図12中の行列を生成するためのプロセスを表すブロック図。
部分行列SEと永久的非活動シンボルに対応する部分行列とを使用して、受信された被符号化シンボルを表すアレイD()から、復元されたソースシンボルを表すアレイC()を復元するためにデコーダによって解かれるべき式のセットの行列表現を示す図。
図12の行列または図15の行列において使用され得るLT部分行列を生成するためのプロセスを示すフローチャート。
図15の行列において使用され得るPI部分行列を生成するためのプロセスを示すフローチャート。
行列生成器のブロック図。
SE部分行列を生成するためのプロセスを示すフローチャート。
PI部分行列を生成するためのプロセスを示すフローチャート。
デコーダにおいて復元されたシンボルについて解決するためのプロセスを示すフローチャート。
置換後に、受信された被符号化シンボルを表すアレイD()から、復元されたソースシンボルを表すアレイC()を復元するためにデコーダによって解かれるべき式のセットの行列表現を示す図。
図26に示す行列に対応する、デコーダによって解かれるべき式のセットの行列表現を示す図。
復号プロセスの一部として使用可能な行列表現を示す図。
復号プロセスの別の一部として使用可能な行列表現を示す図。
部分的解決後にデコーダによって解かれるべき式のセットの行列表現を示す図。
デコーダにおいて復元されたシンボルについて解決するための別のプロセスを示すフローチャート。
デコーダによって解かれるべき式のセットの行列表現を示す図。
デコーダによって解かれるべき式のセットの行列表現を示す図。
プログラムストアに記憶され、プロセッサによって実行されるハードウェアモジュールソフトウェアモジュール、またはプログラムコードの部分として、場合によっては、図に示すように分離されていないコードの集合的なユニットとして実装され得る例示的な符号化システムを示す図。
プログラムストアに記憶され、プロセッサによって実行されるハードウェアモジュール、ソフトウェアモジュール、またはプログラムコードの部分として、場合によっては、図に示すように分離されていないコードの集合的なユニットとして実装され得る例示的な復号システムを示す図。

実施例

0029

付録Aとして添付されているのは、データオブジェクトの信頼できる配信に対するエンコーダ/デコーダシステム誤り訂正方式、および適用例の特定の実施形態のためのコード仕様であり、時々本発明の詳細が使用されており、システマティックエンコーダ/デコーダがオブジェクト配信トランスポートにおいてどのように使用され得るかの仕様をも含む。付録A中で説明されている特定の実施形態は本発明の限定的な例ではないこと、および本発明のいくつかの態様は付録Aの教示を使用し得るが、他の態様は使用し得ないことを理解されたい。また、付録A中の限定的な記載が特定の実施形態の要件に関して限定的であり得、そのような限定的な記載は、請求される本発明に関係することも関係しないこともあり、したがって、クレーム文言は、そのような限定的な記載によって限定される必要はないことを理解されたい。

0030

本明細書で参照するエンコーダおよびデコーダの部分を実装するための詳細は、Luby I、Luby II、Shokrollahi I、Shokrollahi II、Shokrollahi III、Luby III、およびShokrollahi IVによって与えられ、簡潔のためにここで完全には繰り返さない。それらの開示全体は、すべての目的のために参照により本明細書に組み込まれ、本発明には本明細書中の実装形態が必要であるわけではなく、別段に規定されていない限り、多くの他の変形形態変更形態、または代替形態も使用され得ることを理解されたい。

0031

マルチステージ符号化は、本明細書で説明するように、ソースデータを複数のステージで符号化する。常にではないが、一般に、第1のステージは、ソースデータに所定量の冗長性を追加する。次いで、第2のステージは、連鎖反応符号などを使用して、元のソースデータと、第1のステージの符号化によって計算された冗長シンボルとから被符号化シンボルを生成する。1つの特定の実施形態では、受信データは、最初に連鎖反応復号プロセスを使用して復号される。そのプロセスが元のデータを完全に復元することに成功しなかった場合、第2の復号ステップが適用され得る。

0032

本明細書で教示する実施形態の一部は、多くの他のタイプの符号、たとえば、Internet Engineering Task Force(IETF)Request for Comments(RFC)5170に記載されている符号(以下、「IETFLDPC符号」)、ならびに米国特許第6,073,250号、6,081,909号および6,163,870号に記載されている符号(以下、「トルネード符号」)に適用され得、それらのタイプの符号の信頼性および/またはCPUおよび/またはメモリパフォーマンスが改善されることになる。

0033

本明細書で教示するいくつかの実施形態の1つの利点は、連鎖反応コーディング単独と比較して、被符号化シンボルを生成するのにより少ない算術演算が必要であることである。第1のステージの符号化と第2のステージの符号化とを含むいくつかの特定の実施形態の別の利点は、第1のステージの符号化と第2のステージの符号化とが、別の時間においておよび/または別々のデバイスによって行われ得、したがって、計算負荷を分割し、全体的な計算負荷、また、メモリサイズおよびアクセスパターン要件を最小限に抑えることである。マルチステージ符号化の実施形態では、第1のステージの符号化中に入力ファイルから冗長シンボルが生成される。これらの実施形態では、第2のステージの符号化において、入力ファイルと冗長シンボルとの組合せから被符号化シンボルが生成される。これらの実施形態のうちの一部では、必要に応じて被符号化シンボルが生成され得る。第2のステージが連鎖反応符号化を備える実施形態では、各被符号化シンボルは、他の被符号化シンボルがどのように生成されるかを顧慮せずに生成され得る。生成された後、これらの被符号化シンボルは、パケットに入れられ、それらの宛先に送信され得、各パケットは1つまたは複数の被符号化シンボルを含んでいる。代わりにまたはその上、非パケット化送信技法が使用され得る。

0034

本明細書で使用する「ファイル」という用語は、1つまたは複数のソースに記憶されており、ユニットとして1つまたは複数の宛先に配信されるべきデータを指す。したがって、ファイルサーバまたはコンピュータストレージデバイスからのドキュメント、画像、およびファイルはすべて、配信され得る「ファイル」の例である。ファイルは、(ハードディスクに記憶された1メガバイト画像など)既知のサイズであるか、または(ストリーミングソースの出力から取られたファイルなど)未知のサイズであり得る。どちらにしても、ファイルは、各ソースシンボルがファイル中の位置と値とを有する、ソースシンボルのシーケンスである。「ファイル」はまた、ストリーミングソースの短い部分を指すために使用され得、すなわち、データストリームは1秒区間に区分され得、そのような各1秒区間内のソースデータブロックは「ファイル」であると考えられ得る。別の例として、ビデオストリーミングソースからのデータブロックは、たとえばビデオストリームプレイアウトすることができるビデオシステムによって定義されたそのデータの優先度に基づいて複数の部分にさらに区分され得、各ブロックの各部分は「ファイル」であると考えられ得る。したがって、「ファイル」という用語は、一般的に使用され、広範囲にわたって限定するものではない。

0035

本明細書で使用するソースシンボルは、送信または搬送されるべきデータを表し、被符号化シンボルは、ソースシンボルの信頼できる受信および/または再生を可能にするために、通信ネットワーク上で搬送されるかまたは記憶されたソースシンボルに基づいて生成されたデータを表す。中間シンボルは、符号化プロセスまたは復号プロセスの中間ステップ中に使用または生成されるシンボルを表し、一般に、ソースシンボルから中間シンボルを生成するための方法と、中間シンボルからソースシンボルを生成するための対応する逆方法とが存在する。入力シンボルは、符号化または復号のプロセス中に1つまたは複数のステップに入力されるデータを表し、出力シンボルは、符号化または復号のプロセス中に1つまたは複数のステップから出力されるデータを表す。

0036

多くの実施形態において、これらの異なるタイプまたはラベルのシンボルは、同じであるか、または少なくとも部分的に他のタイプのシンボルから構成され得、いくつかの例では、これらの用語は互換的に使用される。一例では、送信されるべきファイルは、各文字がソースシンボルと見なされる1000文字のテキストファイルであると仮定する。それらの1000個のソースシンボルがそのままエンコーダに与えられた場合、エンコーダは、送信される被符号化シンボルを出力し、ソースシンボルは入力シンボルでもある。ただし、第1のステップにおいて1000個のソースシンボルが1000個の(またはより多いもしくはより少ない)中間シンボルに変換され、第2のステップにおいてそれらの中間シンボルがエンコーダに与えられて被符号化シンボルを生成する実施形態では、第1のステップにおいて、ソースシンボルは入力シンボルであり、中間シンボルは出力シンボルであり、第2のステップにおいて、中間シンボルは入力シンボルであり、被符号化シンボルは出力シンボルであるが、ソースシンボルは、この2ステップエンコーダへの全体的な入力シンボルであり、被符号化シンボルは、この2ステップエンコーダの全体的な出力シンボルである。この例では、エンコーダがシステマティックエンコーダである場合、被符号化シンボルは、中間シンボルから生成されたリペアシンボルとともにソースシンボルを備え得るが、中間シンボルは、ソースシンボルと被符号化シンボルの両方とは異なる。代わりに、この例において、エンコーダが非システマティックエンコーダである場合、中間シンボルは、第1のステップにおいてたとえばLDPCおよび/またはHDPCエンコーダを使用してソースシンボルから生成された冗長シンボルとともにソースシンボルを備え得るが、被符号化シンボルは、ソースシンボルと中間シンボルの両方とは異なる。

0037

他の例では、より多くのシンボルが存在し、各シンボルは2つ以上の文字を表す。いずれの場合も、送信機中にソース中間(source-to-intermediate)シンボル変換がある場合、受信機は、その逆として対応する中間ソース(intermediate-to-source)シンボル変換を有し得る。

0038

送信とは、ファイルを配信するために、チャネルを通してデータを1つまたは複数の送信側から1つまたは複数の受信側に送信するプロセスである。送信側はまた、エンコーダと呼ばれることがある。1つの送信側が、完全なチャネルによって任意の数の受信側に接続されている場合、受信データは、すべてのデータが正しく受信されるので、ソースファイルの正確なコピーになることができる。ここで、チャネルが完全ではないことを仮定し、それは、たいていの現実世界のチャネルの実情である。多くのチャネル欠陥のうち、注目する2つの欠陥は、データ消去と、(データ消去の特殊な場合として扱われ得る)データ不完全性とである。データ消去は、チャネルからデータが損失または欠落したときに発生する。データ不完全性は、データの一部が受信側を通過してしまうまで受信側がデータを受信し始めないとき、送信が終了する前に受信側がデータを受信することを停止したとき、受信側が送信データの一部分のみを受信することを選定したとき、および/または受信側がデータを受信することを間欠的に停止および再開したときに発生する。データ不完全性の一例として、移動中の衛星送信側が、ソースファイルを表すデータを送信しており、受信側がレンジ内に入る前に送信を開始することがあり得る。受信側がレンジ内に入ると、衛星がレンジ外に移動するまでデータが受信され得、衛星がレンジ外に移動した時点で、受信側は、レンジ内に移動した別の衛星によって送信されている同じ入力ファイルに関するデータを受信し始めるために、受信側のサテライトディッシュを向け直すことができる(その時間中、受信側はデータを受信していない)。本明細書を読めば明らかであるように、受信側が全時間にレンジ内にあったが、受信側がデータを受信し始めた時点まで、チャネルからすべてのデータが損失したかのように、受信側はデータ不完全性を扱うことができる(また受信側は同じ問題を有する)ので、データ不完全性はデータ消去の特殊な場合である。また、通信システム設計においてよく知られているように、検出可能な誤りは、検出可能な誤りを有するすべてのデータブロックまたはシンボルを単に欠落したことによる消去と等価であると考えられ得る。

0039

いくつかの通信システムでは、受信側は、複数の送信側によって、または複数の接続を使用する1つの送信側によって生成されたデータを受信する。たとえば、ダウンロード高速化するために、受信側は、同じファイルに関するデータを送信するために2つ以上の送信側に同時に接続し得る。別の例として、マルチキャスト送信では、複数のマルチキャストデータストリームが送信されるので、受信側は、これらのストリームのうちの1つまたは複数に接続して、アグリゲート送信レートを、受信側を送信側に接続するチャネルの帯域幅に一致させることが可能になり得る。すべてのそのような場合において、問題は、すべての送信データが受信側に対して独立に使用されること、すなわち、異なるストリームについて送信レートが非常に異なるとき、および恣意的な損失パターンがあるときでも、複数のソースデータがストリーム間冗長でないことを保証することである。

0040

概して、通信チャネルは、データ送信のために送信側と受信側とを接続するチャネルである。チャネルがデータを入手したときにチャネルがデータを送信側から受信側に移動させる場合、通信チャネルはリアルタイムチャネルであり得、あるいは通信チャネルは、送信側から受信側へのデータ輸送においてデータの一部または全部を記憶するストレージチャネルであり得る。後者の例は、ディスクストレージまたは他のストレージデバイスである。その例では、データを生成するプログラムまたはデバイスは、データをストレージデバイスに送信する送信側として考えられ得る。受信側は、ストレージデバイスからデータを読み込むプログラムまたはデバイスである。ストレージデバイス上にデータを得るために送信側が使用する機構と、ストレージデバイス自体と、ストレージデバイスからデータを得るために受信側が使用する機構とが、集合的にチャネルを形成する。それらの機構またはストレージデバイスがデータを損失し得る可能性がある場合、それは、通信チャネルにおけるデータ消去として扱われるであろう。

0041

送信側と受信側とが、シンボルが消去され得る通信チャネルによって分離されているとき、入力ファイルの正確なコピーを送信するのではなく、消去の復元を支援する入力ファイルから生成されたデータを送信することが好ましい。エンコーダは、そのタスクを処理する回路、デバイス、モジュール、またはコードセグメントである。エンコーダの演算を見る1つの方法は、エンコーダがソースシンボルから被符号化シンボルを生成することであり、ソースシンボル値のシーケンスは入力ファイルを表す。したがって、各ソースシンボルは、入力ファイル中の位置と値とを有することになる。デコーダは、受信側によって受信された被符号化シンボルからソースシンボルを再構成する回路、デバイス、モジュールまたはコードセグメントである。マルチステージコーディングでは、エンコーダとデコーダとは、時々、各々が異なるタスクを実行するサブモジュールにさらに分割される。

0042

マルチステージコーディングシステムの実施形態では、エンコーダとデコーダとは、各々が異なるタスクを実行するサブモジュールにさらに分割され得る。たとえば、いくつかの実施形態では、エンコーダは、本明細書において静的エンコーダおよび動的エンコーダと呼ぶものを備える。本明細書で使用する「静的エンコーダ」は、ソースシンボルのセットからいくつかの冗長シンボルを生成するエンコーダであって、冗長シンボルの数が符号化より前に判断される、エンコーダである。マルチステージコーディングシステムにおいて静的符号化が使用されるとき、ソースシンボルと、静的エンコーダを使用してソースシンボルから生成された冗長シンボルとの組合せは、しばしば中間シンボルと呼ばれる。潜在的な静的符号化符号の例には、リードソロモン符号、トルネード符号、ハミング符号、IETFLDPC符号などのLDPC符号がある。「静的デコーダ」という用語は、本明細書では、静的エンコーダによって符号化されたデータを復号することができるデコーダを指すために使用される。

0043

本明細書で使用する「動的エンコーダ」は、入力シンボルのセットから被符号化シンボルを生成するエンコーダであって、可能な被符号化シンボルの数が入力シンボルの数とは無関係であり、生成されるべき被符号化シンボルの数が固定である必要がない、エンコーダである。しばしば、マルチステージ符号では、入力シンボルは、静的符号を使用して生成された中間シンボルであり、被符号化シンボルは、動的エンコーダを使用して中間シンボルから生成される。動的エンコーダの一例は、Luby IおよびLuby IIにおいて教示されているエンコーダなど、連鎖反応エンコーダである。「動的デコーダ」という用語は、本明細書では、動的エンコーダによって符号化されたデータを復号することができるデコーダを指すために使用される。

0044

いくつかの実施形態では、マルチステージ符号でありシステマティックである符号化は、中間シンボルの間で静的エンコーダによって定義され、および中間シンボルとソースシンボルとの間で動的エンコーダによって定義された関係に基づいて中間シンボル値を取得するためにソースシンボルに適用された復号プロセスを使用し、次いで、動的エンコーダが、中間シンボルから追加の被符号化シンボルまたはリペアシンボルを生成するために使用される。同様に、対応するデコーダは、被符号化シンボルを受信し、中間シンボルの間で静的エンコーダによって定義され、および中間シンボルと受信された被符号化シンボルとの間で動的エンコーダによって定義された関係に基づいて中間シンボル値を受信された被符号化シンボルから復号する復号プロセスを有し、次いで、動的エンコーダが、中間シンボルから消失したソースシンボルを生成するために使用される。

0045

マルチステージコーディングの実施形態は、特定のタイプのシンボルに限定される必要はない。一般に、シンボルの値は、何らかの正の整数Mについて、2M個のシンボルのアルファベットから選択される。そのような場合、ソースシンボルは、入力ファイルからのデータのMビットのシーケンスによって表され得る。Mの値は、しばしば、たとえば、アプリケーションの使用、通信チャネル、および/または被符号化シンボルのサイズに基づいて決定される。さらに、被符号化シンボルのサイズは、しばしば、アプリケーション、チャネル、および/またはソースシンボルのサイズに基づいて決定される。場合によっては、被符号化シンボル値とソースシンボル値とが同じサイズであった(すなわち、同じビット数によって表せるかまたは同じアルファベットから選択された)場合、コーディングプロセスは簡略化され得る。そのような場合、被符号化シンボル値サイズが制限されているとき、ソースシンボル値サイズは制限される。たとえば、被符号化シンボルを、制限されたサイズのパケットに入れることが所望され得る。被符号化シンボルに関連する鍵に関する何らかのデータが、受信機において鍵を復元するために送信されるべき場合、被符号化シンボルは、好ましくは、被符号化シンボル値と鍵に関するデータとを1パケット中に収容するために十分小さくなるであろう。

0046

一例として、入力ファイルが多メガバイトファイルである場合、その入力ファイルは、数千、数万、または数十万個のソースシンボルに分解され得、各ソースシンボルは、数千、数百、またはわずか数バイトを符号化する。別の例として、パケットベースインターネットチャネルの場合、1024バイトのサイズのペイロードをもつパケットが適切であり得る(1バイトは8ビットである)。この例では、各パケットが1つの被符号化シンボルと8バイトの補助情報とを含んでいると仮定すると、8128ビットの被符号化シンボルサイズ((1024−8)*8)が適切になるであろう。したがって、ソースシンボルサイズは、M=(1024−8)*8、すなわち8128ビットとして選定され得る。別の例として、いくつかの衛星システムMPEGパケット規格を使用し、各パケットのペイロードが188バイトを備える。その例では、各パケットが1つの被符号化シンボルと4バイトの補助情報とを含んでいると仮定すると、1472ビットの被符号化シンボルサイズ((188−4)*8)が適切になるであろう。したがって、ソースシンボルサイズは、M=(188−4)*8、すなわち1472ビットとして選定され得る。マルチステージコーディングを使用した汎用通信システムでは、ソースシンボルサイズ(すなわち、ソースシンボルによって符号化されたビット数M)などの特定用途向けパラメータは、アプリケーションによって設定された変数であり得る。

0047

各被符号化シンボルは値を有する。以下で考察する1つの好適な実施形態では、各被符号化シンボルはまた、「鍵」と呼ばれる識別子をそれに関連付けている。好ましくは、受信側が1つの被符号化シンボルを他の被符号化シンボルと区別することを可能にするために、各被符号化シンボルの鍵は受信側によって容易に判断され得る。好ましくは、ある被符号化シンボルの鍵は、すべての他の被符号化シンボルの鍵とは異なる。従来技術において説明されている様々な形式キーイングが存在する。たとえば、Luby Iは、本発明の実施形態において採用され得る様々な形式のキーイングについて説明している。付録Aで説明している実施形態など、他の好適な実施形態では、被符号化シンボルの鍵は、「被符号化シンボル識別子(Encoded Symbol Identifier)」、または「符号化シンボル識別子(Encoding Symbol Identifier)」、またはより簡単に「ESI」と呼ばれる。

0048

データ消去が予想される場合、またはちょうど送信が開始および終了したときに受信側が受信を開始および終了しない場合、マルチステージコーディングは特に有用である。後者の条件は、本明細書では「データ不完全性」と呼ぶ。消去イベントに関して、マルチステージコーディングは、Luby Iにおいて教示されている連鎖反応コーディングの利益の多くを共有する。特に、マルチステージ被符号化シンボルは情報付加的であり、したがって、所望の正確度まで入力ファイルを復元するために任意の好適な数のパケットが使用され得る。マルチステージコーディングを用いて生成された被符号化シンボルは情報付加的であるので、マルチステージコーディングが使用されたとき、これらの条件は通信プロセスに悪影響を及ぼさない。たとえば、データ消去を引き起こすノイズバーストにより100個のパケットが損失した場合、そのバースト後に、消去されたパケットの損失分を置き換えるために追加の100個のパケットがピックアップされ得る。送信機が送信を開始したときに受信機が送信機に同調しなかったために数千個のパケットが損失した場合、受信機は、他の送信期間から、さらには別の送信機から、それらの数千個のパケットをただピックアップすることができる。マルチステージコーディングでは、受信機は、パケットの特定のセットをピックアップするように制約されず、したがって、受信機は、1つの送信機からいくつかのパケットを受信し、別の送信機に切り替え、いくつかのパケットを損失し、所与の送信の始端または終端を消失し、それでも入力ファイルを復元することができる。受信機送信機協調なしに送信に入り、離れる能力は、通信プロセスを簡略化するのに役立つ。

0049

いくつかの実施形態では、マルチステージコーディングを使用してファイルを送信することは、入力ファイルからソースシンボルを生成、形成または抽出することと、冗長シンボルを計算することと、ソースシンボルと冗長シンボルとを1つまたは複数の被符号化シンボルに符号化することであって、各被符号化シンボルが、すべての他の被符号化シンボルとは無関係にその各被符号化シンボルの鍵に基づいて生成される、符号化することと、チャネルを介して1つまたは複数の受信側に被符号化シンボルを送信することとを含むことができる。さらに、いくつかの実施形態では、マルチステージコーディングを使用して入力ファイルのコピーを受信(し、再構成)することは、より多くのデータストリームのうちの1つから被符号化シンボルのいくつかのセットまたはサブセットを受信することと、受信した被符号化シンボルの値と鍵とからソースシンボルを復号することとを含むことができる。

0050

システマティック符号および非システマティック符号
システマティック符号は、ソースシンボルが、送信され得る被符号化シンボルの中にある符号である。この場合、被符号化シンボルは、ソースシンボルと、ソースシンボルから生成されたリペアシンボルとも呼ばれる冗長シンボルとから構成される。システマティック符号は、様々な理由で、多くの適用例では非システマティック符号よりも好ましい。たとえば、ファイル配信適用例では、リペアデータを生成するプロセスが何らかの時間量を取り得る場合、リペアデータを生成するためにデータが使用されている間、連続順序でそのデータを送信し始めることが可能であることが有用である。別の例として、多くの適用例は、1つのチャネルに元のソースデータを連続順序でそれの無変更形式で送り、別のチャネルにリペアデータを送ることを選好する。このことの1つの典型的な理由は、ソースデータチャネルのみに入るFEC復号を組み込まないレガシー受信機サポートすることと、同時に、ソースデータチャネルとリペアデータチャネルの両方に入るFEC復号を組み込んだ拡張受信機により良いエクスペリエンスを提供することの両方である。

0051

これらおよび関係するタイプの適用例では、受信機によって受信されたソースシンボル中の損失パターンおよび損失の部分が、受信されたリペアシンボル間で遭遇される損失パターンおよび損失の部分と極めて異なる場合が時々あり得る。たとえば、ソースシンボルがリペアシンボルより前に送られたとき、チャネルのバースト的損失状態により、ソースシンボル中の損失の部分およびパターンは、リペアシンボル中の損失の対応する部分およびパターンとは極めて異なり得、ソースシンボル中の損失のパターンは、損失が一様にランダムであった場合よりも典型的であり得たものとはかけ離れ得る。別の例として、ソースデータが1つのチャネル上で送られ、リペアデータが別のチャネル上で送られるとき、それらの2つのチャネル上で極めて異なる損失状態が存在し得る。したがって、様々なタイプの損失状態の下でうまく動作するシステマティックFEC符号を有することが望ましい。

0052

本明細書の例は、(出力または被符号化シンボルがソースまたは入力シンボルを含む)システマティック符号、あるいは非システマティック符号に言及しているが、本明細書の教示は、別段に規定されていない限り、両方に適用可能であると考えられるべきである。Shokrollahi IIIでは、非システマティック符号のロバストネス性が、そのように構築されたシステマティック符号によって維持されるような方法で、非システマティック連鎖反応符号をシステマティック符号に変換するための方法を教示している。

0053

特に、Shokrollahi IIIにおいて教示されている方法を使用する場合、構築されたシステマティック符号は、損失したソースシンボルと、損失したリペアシンボルとの間でデコーダによる復元可能性に関してほとんど区別がない性質を有し、すなわち、復号復元確率は、リペアシンボル中の損失の比率と比較して、ソースシンボル中の損失の比率とはほとんど無関係に所与の総損失量に対して本質的に同じである。さらに、被符号化シンボル中の損失のパターンは、復号復元確率に有意に影響を及ぼさない。比較において、トルネード符号またはIETFLDPC符号について記述されている構成など、他のシステマティック符号の構成では、多くの場合、損失したソースシンボルと損失したリペアシンボルとの間にデコーダによる復元可能性に関して強い区別がある、すなわち、リペアシンボルの間の損失の比率と比較してソースシンボルの間の損失の比率に応じて、復号復元確率は所与の総損失量に対して同じものに対して大きく異なり得る。さらに、被符号化シンボル中の損失のパターンは、復号復元確率に強い影響を有し得る。被符号化シンボルの損失が被符号化シンボルのすべての間で一様にランダムである場合、トルネード符号とIETF LDPC符号とは適度に良好な復元特性を有するが、復元特性は、損失モデルが一様ランダム損失からそれるにつれて劣化する。したがって、この意味において、Shokrollahi IIIにおいて教示されている実施形態は、システマティック符号の他の構成よりも利点を有する。

0054

損失したソースシンボルと損失したリペアシンボルとの比率に応じて、および損失パターンに応じてデコーダによる復元可能性に関して強い影響がある特性をもつFEC符号の場合、この特性を克服するための1つの手法は、その手法が適用可能であるときは、被符号化シンボルを一様にランダムな順序で送ること、すなわち、ソースシンボルとリペアシンボルとの組合せを一様にランダムな順序で送り、このようにして、ソースシンボルをリペアシンボル間でランダムに点在させることである。ランダム順序で被符号化シンボルを送ることは、チャネル損失モデルが何であろうと、また損失がバースト的であるか、一様にランダムであるか、または何らかの他のタイプの損失であるかにかかわらず、被符号化シンボルに対する損失は依然としてランダムであるという利点を有する。ただし、上記のように、この手法は、いくつかの適用例、たとえば、リペアシンボルの前にソースシンボルを順々に送ることが望ましい適用例、または、ソースシンボルが、リペアシンボルとは異なるチャネル上で送られる適用例では望ましくない。

0055

そのような場合、被符号化シンボル中の損失のパターンがデコーダの復元特性にあまり影響を及ぼさないシステマティック符号の構成が望まれ、いくつかの例を本明細書で提供する。

0056

本明細書で使用する「ランダム」および「擬似ランダム」は、しばしば等価および/または交換可能であり、コンテキストに依存し得る。たとえば、ランダム損失は、真にランダムイベントであり得る、どのシンボルがチャネルによって損失したかを指し得、一方、シンボルネイバーランダム選択は、実際は非ランダムプロセスによる繰り返し可能な擬似ランダム選択であり得るが、それは、真ランダム選択の場合がそうであるように同じまたは同様の特性または挙動を有する。明示的にまたはコンテキストによって別段に規定されていない限り、あるものをランダムとして特徴づけることは、擬似ランダム性を除外するものではない。

0057

そのようなシステマティックFECエンコーダに対する1つの手法では、ソースシンボルは、複数のエンコーダサブブロックまたはサブプロセスを含むエンコーダによって取得され、それらの複数のエンコーダサブブロックまたはサブプロセスのうちの1つは、別のサブブロックまたはサブプロセスへの入力シンボルである中間シンボルを生成するデコーダとして動作する。次いで、中間シンボルは、被符号化シンボルが、(追加の冗長シンボルとともに)1つの一貫したプロセスから生成されたソースシンボルを含むように、中間シンボルを被符号化シンボルに符号化する別のサブブロックまたはサブプロセスに適用され、それによって、被符号化シンボルセット用にソースシンボルを得るために1つのプロセス(たとえば、コピー)を使用し、被符号化シンボルセット用に冗長シンボルを得るために別のプロセスを使用するシステマティックエンコーダであるエンコーダに勝る、ロバストネスの利益と他の利益とを提供する。

0058

出力符号化は、連鎖反応エンコーダ、静的エンコーダまたは他の変形態であり得る。付録Aは、システマティック符号実施形態について説明している。本開示を読めば、当業者は、同じくシステマティック符号であるが、より良い復元特性を有するこれらの符号の新しいバージョンを生み出すために、トルネード符号およびIETFLDPC符号などのシステマティック符号に適用するようにShokrollahi IIIの教示を容易に拡張することが可能であるはずである。特に、以下で説明する概略的な方法を適用することによって得られたこれらの符号の新しいバージョンは、リペアシンボル中の損失の比率と比較してソースシンボル中の損失の比率が、復号復元確率に有意に影響を及ぼさず、さらに、損失のパターンが復号復元確率に有意に影響を及ぼさないという特性を有するように拡張される。したがって、これらの符号は、ソースシンボルとリペアシンボルとの間の異なる部分損失量または異なる損失パターンによって強く影響されない復元特性をもつシステマティックFEC符号の使用を必要とする上記で説明した適用例において効果的に使用され得る。

0059

新しい符号化方法は、概して、新しい拡張システマティックFEC符号のための総合的符号化方法を生み出すために、システマティックFEC符号、非システマティックFEC符号、固定レートFEC符号および連鎖反応FEC符号の符号化に適用され得る。また、適用され得る対応する新しい復号方法が存在する。

0060

エンコーダ中のデコーダの例
次に、エンコーダ中のデコーダの一例を与える。

0061

符号化方法Eが、K個のソースシンボルからN個の被符号化シンボルを生成する固定レート(非システマティックまたはシステマティック)FEC符号Eのために(送信機または他の場所における)エンコーダによって使用される符号化方法であるとし、ただし、Nは少なくともKである。同様に、復号方法Eが、受信機または他の場所におけるデコーダによって使用される、FEC符号Eのための対応する復号方法であるとする。

0062

FEC符号Eは、N個の被符号化シンボルのうちのK個のランダムセットが、復号方法Eを使用して元のK個のソースシンボルを妥当な確率で復元するのに十分であるという特性を有すると仮定し、ただし、妥当な確率は、たとえば、確率1/2であり得る。妥当な確率は、使用法またはアプリケーションによる何らかの要件セットであり得、1/2以外の値であり得る。特定の符号の構成は、特定の復元確率に固有である必要はないが、アプリケーションとシステムとは、ロバストネスのそれらの特定のレベルに設計され得ることを理解されたい。いくつかの事例において、復元確率は、K個よりも多くのシンボルを考察し、次いで、復号プロセスを使用して、これらの考察されたシンボルの中から正常な復号を可能にするK個のシンボルのセットを判断することによって高められ得る。

0063

FEC符号Eのために、ESI(被符号化シンボル識別子)が各被符号化シンボルに関連付けられ、ESIはその被符号化シンボルを識別すると仮定する。一般性の損失なしに、ESIは、本明細書では、0,1,2,...,N−1で標示される。

0064

FEC符号Eのための方法を使用して生成されたシステマティックFEC符号Fのためのシステマティック符号化方法Fの一実施形態では、KおよびNが入力パラメータである。FEC符号FのソースシンボルはESI 0,...,K−1を有し、FEC符号FのリペアシンボルはESI K,...,N−1を有することになる。FEC符号Fのためのシステマティック符号化方法Fは、FEC符号Eのための符号化方法Eと復号方法Eとを使用してK個のソースシンボルC(0),...,C(K−1)からN個の被符号化シンボルを生成し、ハードウェアおよび/またはソフトウェアによって次のように実行される。

0065

(1)FEC符号Eに関連付けられたN個のESIをランダムに置換して、FEC符号E置換ESIセットX(0),...,X(N−1)に達し、この置換ESIセットは、FEC符号EのK個のソースシンボルが、ESI X(0),...,X(K−1)の置換順序に関してFEC符号Eの最初のK個の被符号化シンボルから復号され得るように編成される。

0066

(2)各i=0,...,N−1について、FEC符号FのESI iをFEC符号EのESI X(i)に関連付ける。

0067

(3)各i=0,...,K−1について、ESI X(i)をもつFEC符号Eの被符号化シンボルの値をソースシンボルC(i)の値に設定する。

0068

(4)対応するFEC符号EESI X(0),...,X(K−1)をもつソースシンボルC(0),...,C(K−1)に復号方法Eを適用して、復号シンボルE(0),...,E(K−1)を生成する。

0069

(5)復号シンボルE(0),...,E(K−1)に符号化方法Eを適用して、関連するFEC符号ESI 0,...,N−1をもつFEC符号Eの被符号化シンボルD(0),...,D(N−1)を生成する。

0070

(6)ESI 0,1,...,N−1を用いた符号化方法Fのための被符号化シンボルは、D(X(0)),D(X(1)),...,D(X(N−1))である。

0071

符号化方法Fの出力は、N個の被符号化シンボルであり、それらのN個の被符号化シンボルのうち、最初のK個は、関連するESI 0,1,...,K−1をもつソースシンボルC(0),...,C(K−1)であることに留意されたい。したがって、符号化方法Fは、ソースデータのシステマティック符号化を生成する。

0072

今説明した符号化方法Fに対応する復号方法Fの一実施形態は、次のとおりであり、ただし、KおよびNは、全体を通して使用されるこの方法への入力パラメータである。この復号方法Fは、関連するFEC符号FESI Y(0),...,Y(K−1)をもつK個の受信された被符号化シンボルD(0),...,D(K−1)からK個のソースシンボルC(0),...,C(K−1)を復元する。これらの受信シンボルは、必ずしも送信されたシンボルである必要はない。ハードウェアおよび/またはソフトウェアによって実行される本方法は次のとおりである。

0073

(1)FEC符号Eに関連付けられたN個のESIをランダムに置換して、FEC符号E置換ESIセットX(0),...,X(N−1)に達し、この置換ESIセットは、FEC符号EのK個のソースシンボルが、ESI X(0),...,X(K−1)の置換順序に関してFEC符号Eの最初のK個の被符号化シンボルから復号され得るように編成される。

0074

(2)関連するFEC符号EESI X(Y(0)),...,X(Y(K−1))をもつ被符号化シンボルD(0),...,D(K−1)に復号方法Eを適用して、復号シンボルE(0),...,E(K−1)を生成する。

0075

(3)符号化方法Eを使用して、E(0),...,E(K−1)からFEC符号EESI X(0),...,X(K−1)をもつ被符号化シンボルC(0),...,C(K−1)を生成する。

0076

(4)ESI 0,...,K−1をもつFEC符号Fの復号ソースシンボルは、C(0),...,C(K−1)である。

0077

今説明したように動作する方法および装置は、いくつかの望ましい性質を有する。たとえば、システマティック符号であるFEC符号Eであって、K個の受信された被符号化シンボルのランダムセットが高確率に復号され得るという性質を有するが、K個の被符号化シンボルが受信されたとき、受信された被符号化シンボル中のソースシンボルの比率がK/Nに近接していないという性質をも有する、FEC符号について考えると、そのFEC符号Eは高確率に復号され得ない。この場合、本実施形態は、FEC符号Eの符号化方法と復号方法とを使用する新しいFEC符号Fについて説明し、その新しいFEC符号Fは、ソースシンボルである受信された被符号化シンボルの比率とは無関係に、K個の受信された被符号化シンボルのセットから高確率に復号するという望ましい性質を有する。

0078

上記の実施形態の多くの変形態がある。たとえば、符号化方法Fのステップ(1)において、ESIのランダム置換は、擬似ランダムであり得、またはランダムでも擬似ランダムでもないESIの良好な選択を生成する何らかの他の方法に基づき得る。FEC符号Eがシステマティック符号である場合、システマティックESIの中からステップ(1)において選択された置換中の最初のK個のESIの部分は、FEC符号Eのレートに比例する、すなわち、K/Nに比例することが好ましい。ステップ(1)中の新しい符号化方法Fによって行われるESIのランダム選定は、簡潔なデータ量によって表され得る、たとえば、新しい復号方法Fが、同じシード擬似乱数発生器とESIを生成するための方法とに基づいてステップ(1)においてまったく同じESI置換選定を行うことができるように、シードと、擬似乱数発生器がどのように動作するかとに基づいてESIを選定する同意済みの方法とともに、周知または同意済みの擬似乱数発生器へのシードによって表され得ることが好ましい。概して、ESIのシーケンスを生成するためにステップ(1)中の新しい符号化方法Fにおいて使用されるプロセスと、ESIのシーケンスを生成するためにステップ(1)中の新しい復号方法Fにおいて使用されるプロセスとが、両方ともESIの同じシーケンスを生成する場合、新しい復号方法Fが新しい符号化方法Fの逆になるようにすることが好ましい。

0079

同様に、たとえば、明示的ESIを使用せず、代わりに、ある被符号化シンボルの一意の識別子が、他の被符号化シンボルに対するその被符号化シンボルの位置によるか、または他の手段による、他の変形態がある。

0080

上記の説明では、FEC符号Eの元のESIは、ソースシンボルの順序セットに連続順序でESI 0,...,K−1が割り当てられ、リペアシンボルにESI K,...,N−1が割り当てられるように、FEC符号Fによってリマッピングされる。他の変形態が可能であり、たとえば、ESIの再マッピングは、符号化方法Fが被符号化シンボルを生成した直後に、しかし被符号化シンボルが送信される前に、送信側において行われ得、ESIの逆再マッピングは、被符号化シンボルが受信されたとき、しかし被符号化シンボルが復号方法Fによって元のソースシンボルの復元のために処理される前に、受信機において行われ得る。

0081

別の変形態として、新しい符号化方法Fのステップ(1)において、最初にK+A個のFEC符号EESIを選択することによって置換が選択され得、ただし、Aは、高確率の復号可能性を保証するために選定された値であり、次いで、復号プロセスのシミュレーション中に、K+A個のESIの中からどのK個が実際に復号中に使用されるかが判断され、選択された置換は、置換の最初のK個のESIとなるべき、K+A個のESIの初期セットの中から実際に復号中に使用されるK個のESIを選択し得る。同様の変形態が、新しい復号方法Fに適用される。

0082

符号化方法Fの別の変形態として、ステップ(1)において生成されるESIの置換に関連付けられるFEC符号Eの最初のK個の被符号化シンボルが復号可能であることを保証するために、ランダム置換を生成するために使用されるシードがKの値について事前計算され、次いで、このシードは、ステップ(1)において置換を生成するために、符号化方法Fおよび対応する復号方法Fのステップ(1)におけるKについて常に使用される。そのようなシードを選定するための方法は、ステップ(1)における復号可能性を保証するシードが発見されるまでシードをランダムに選定することと、次いで、このシードを選択することとを含む。代替的に、これらの性質をもつシードが符号化方法Fによって動的に生成され得、次いで、このシードは復号方法Fに通信され得る。

0083

符号化方法Fの別の変形態として、ステップ(1)において部分置換が選択され得、すなわち、ESIのすべてと、被符号化シンボルのすべてとがステップ(5)および(6)において必要とされるのでなければ、たとえば、それらは、被符号化シンボルの一部であるソースシンボルに対応するので、またはN個未満の被符号化シンボルしか生成される必要がないので、新しい符号化方法Fのステップ(1)におけるESIのすべてが生成され、被符号化シンボルのすべてが生成される必要があるわけではない。他の変形態では、受信された被符号化シンボルの一部は、復元されているソースシンボルの一部に対応し得るので、新しい復号方法Fのステップ(3)および(4)における被符号化シンボルのすべてが再計算される必要があるわけではない。同様に、新しい復号方法Fのステップ(2)において、たとえば、ステップ(2)において復号されたシンボルの一部が、被符号化シンボルを生成するために後続のステップにおいて必要とされない場合、すべてのK個のシンボルE(0),...,E(K−1)が復号される必要があるわけではない。

0084

上記で説明した方法および実施形態は多くの適用例を有する。たとえば、符号化方法Fおよび復号方法Fならびにそれらの変形態は、改善された受信オーバーヘッドと復号失敗確率パフォーマンスとを与えるためにトルネード符号およびIETFLDPC符号に適用され得る。概して、これらの新しい方法は、任意の固定レートFEC符号に適用される。これらの新しい方法の変形態はまた、固定レートを有しないFEC符号、すなわち、生成され得る被符号化シンボルの数がソースシンボルの数とは無関係である、連鎖反応符号などのFEC符号に適用され得る。

0085

Shokrollahi IIIは、連鎖反応符号のためのシステマティック符号化および復号方法を作成するための同様の教示を含んでいる。いくつかの実施形態では、これらの符号のために使用される符号化方法および復号方法Eは、Luby I、Luby II、Shokrollahi I、Shokrollahi II、Luby III、Shokrollahi IVにおいて教示されている方法である。システマティックエンコーダについて説明するためには、符号化方法Eと復号方法Eとについて説明し、これらの方法をシステマティック符号化方法Fとシステマティック復号方法Fとに変換するために、上記で説明し、それらの文献から知られる一般的原理を使用することでしばしば十分である。したがって、本開示と引用文献とを読めば、符号化方法Eと復号方法Eとについて説明している本教示をどのように取り入れ、同教示をシステマティック符号化方法Fとシステマティック復号方法Fとに適用すべきかなどが当業者には明らかであるはずである。非活動化
Shokrollahi IIなどにおいて教示されている非活動化復号は、既知の一次方程式値のセットから未知の変数のセットについて解くときはいつでも信念伝搬と組み合わせて適用され得る一般的な方法であり、一次方程式のセットに基づいて効率的な符号化方法と復号方法とを実装するときは特に有益である。Shokrollahi IIに記載されている非活動化復号と、本明細書で以下で説明する永久的非活動化復号とを区別するために、Shokrollahi IIの方法および教示を参照するためには「オンザフライ」非活動化(所々で「OTF非活動化」と略す)を使用し、非活動化が事前に選択される本明細書の方法および教示を参照するためには「永久的非活動化」を使用する。

0086

信念伝搬復号の1つの教義は、復号プロセス中に可能であるときはいつでも、デコーダは、1つの残りの未知の変数について解くために、その変数に依存する方程式(場合によっては簡約方程式)を使用しなければならず、したがって、その方程式は、その変数に関連付けられ、次いで、解かれた変数に対するそれらの方程式の依存性をなくすことによって残りの未使用の方程式を簡約するということである。そのような単純な信念伝搬ベースの復号プロセスは、たとえば、トルネード符号、Luby I、Luby II、Shokrollahi I、Shokrollahi II、Luby III、Shokrollahi IVに記載されている連鎖反応符号、およびIETFLDPC符号の実施形態の一部において使用されている。

0087

OTF非活動化復号は複数の段階で進行する。OTF非活動化復号方法の第1の段階では、ただ1つの残りの未知の変数に依存する残りの方程式がないので信念伝搬復号プロセスが進むことができないときはいつでも、デコーダは、1つまたは複数の未知の変数を「OTF非活動化」し、それらの未知の変数を、(実際にはそうでないにもかかわらず)信念伝搬プロセスに関して「解かれ」、残りの方程式から「除去された」ものと見なし、このようにして、場合によっては信念伝搬復号プロセスが進むことを可能にする。次いで、たとえば第2の段階において、第1の段階中にOTF非活動化された変数について、たとえばガウス消去法またはより計算量的に効率的な方法を使用して解かれ、次いで、第3の段階において、これらのOTF非活動化された変数の値は、復号の第1の段階中に方程式に関連付けられた変数について完全に解くために使用される。

0088

Shokrollahi IIなどにおいてより詳細に教示されているOTF非活動化復号は、連鎖反応符号以外の多くの他のタイプの符号に適用され得る。たとえば、そのOTF非活動化復号は、LDPCおよびLDGM符号の一般的クラス、特にIETFLDPC符号およびトルネード符号に適用され得、その結果、それらのタイプの符号について信頼性が改善され(デコードに失敗する確率を減少させ)、ならびに/あるいはCPUおよび/またはメモリパフォーマンスが改善される(符号化および/または復号の速度を増加させ、および/または所要メモリサイズおよび/またはアクセスパターン要件を減少させる)。

0089

OTF非活動化復号と組み合わせた連鎖反応符号実施形態の変形態のいくつかがShokrollahi IVにおいて説明されている。本出願では他の変形態について説明する。

0090

システム概観
図1は、マルチステージコーディングを使用する通信システム100のブロック図である。このブロック図は、Shokrollahi Iに示されているものと同様であるが、この場合、エンコーダ115は、どの中間シンボルの指定が「永久的非活動化」されているかを考慮に入れ、動的符号化プロセス中に永久的非活動化されていない中間シンボルとは異なってそれらの中間シンボルに作用する。同様に、デコーダ155も、復号するときに永久的非活動化中間シンボルを考慮に入れる。

0091

図1に示すように、K個のソースシンボル(C(0),...,C(K−1))がエンコーダ115に入力され、デコーダ155が利用可能になるシンボルの復号に成功した場合、デコーダ115は、それらのK個のソースシンボルのコピーを出力することができる。いくつかの実施形態では、ストリームは、K個のシンボルブロックパースされ、いくつかの実施形態では、Kよりも大きいいくつかのソースシンボルのファイルは、Kサイズのシンボルブロックに分割され、そのように送信される。いくつかの実施形態では、K′>Kのブロックサイズが好適である場合、K′−K個のパディングシンボルがK個のソースシンボルに追加され得る。これらのパディングシンボルは、値0を有するか、あるいはエンコーダ115とデコーダ155の両方に知られている(かまたは場合によってはデコーダ155において判断されることが可能である)任意の他の固定値を有することができる。エンコーダ115は複数のエンコーダ、モジュールなどを備えることがあり、それはデコーダ155についても当てはまり得ることを理解されたい。

0092

図示のように、エンコーダ115はまた、動的鍵生成器120から動的鍵のシーケンスを、および静的鍵生成器130から静的鍵のシーケンスを受信し、動的鍵生成器120と静的鍵生成器130の各々は乱数発生器135によって駆動され得る。動的鍵生成器120の出力は単に基数シーケンスであってよいが、そうである必要はない。鍵生成器の演算は、Shokrollahi Iに示されているとおりでよい。

0093

図に示す様々な機能ブロックは、入力信号として与えられる指定された入力をもつハードウェアとして実装され得、または、命令メモリに記憶されており、対応する機能を実行するために適切な順序で実行される命令を実行するプロセッサによって実装され得ることを理解されたい。場合によっては、それらの機能を実行しおよび/またはプログラムコードを実行するための専用ハードウェアが使用される。プログラムコードおよびプロセッサは常に示されているわけではないが、当業者ならば、本開示を読めば、そのような詳細をどのように実装すべきかがわかるであろう。

0094

エンコーダ115はまた、本明細書の他の場所で説明するラインに沿って、非活動化指定器125からの入力と、システム100への他のパラメータ入力とを受信する。非活動化指定器125の出力は、復号のために「永久的非活動化」されていると指定された中間シンボルの数を表す値Pを含み得る(「PIリスト」は、中間シンボルのうちのどのP個がリスト上にあるかを示す)。他の場所で説明するように、いくつかの実施形態では、符号化プロセスのために使用される中間シンボルはK個のソースシンボルだけであるが、他の実施形態では、K個のソースシンボルをコピーするだけでなくそれらから中間シンボルを生成する何らかのタイプの処理、変換、符号化、復号などがある。

0095

入力パラメータは、(以下でより詳細に説明する)鍵生成器および/またはエンコーダの符号化プロセスによって使用されるランダムシード、生成すべき被符号化シンボルの数、生成すべきLDPCシンボルの数、生成すべきHDPCシンボルの数、生成すべき中間シンボルの数、生成すべき冗長シンボルの数などを含み得、および/またはこれらの値のいくつかは、エンコーダ115にとって利用可能な他の値から計算される。たとえば、生成されるべきLDPCシンボルの数は、固定式およびKの値から完全に計算され得る。

0096

エンコーダ115は、それの入力から被符号化シンボルのシーケンス(B(I0),B(I1),B(I2),...)を生成し、そのシーケンスを送信モジュール140に供給し、その送信モジュール140は、動的鍵生成器120から動的鍵値(I0,I1,I2,...)をも受信するが、その情報を搬送する別の方法がある場合、これは必要でないことがある。送信モジュール140は、送信モジュール140に与えられたものを、場合によっては、ここでより詳細に説明する必要がない従来の方法でチャネル145に搬送する。受信モジュール150は、被符号化シンボルと(必要な場合に)動的鍵値とを受信する。チャネル145は、(別の場所において受信されるためにある場所から送信するための)空間を通るチャネル、または(たとえば、後の時間にリプレイバックするために媒体に記録するための)時間を通るチャネルであり得る。チャネル145は、被符号化シンボルのうちの一部の損失を生じ得る。したがって、デコーダ115が受信モジュール150から受信する被符号化シンボルB(Ia),B(Ib),...は、送信モジュールが送った被符号化シンボルに等しくないことがある。これは、異なる下つき添字インデックスによって示されている。

0097

デコーダ155は、好ましくは、動的鍵再生器160と乱数発生器163と静的鍵生成器165とを使用して、(鍵が異なることがある)受信シンボルのために使用される鍵を再生し、様々な復号パラメータを入力として受信することが可能である。これらの入力のいくつかはハードコーディングされ(すなわち、デバイスの構築中に入力され)得、いくつかは変更可能な入力であり得る。

0098

図2は、他の図においておよび本開示全体にわたってほとんどの場合に使用される、表記法概要を伴う、変数、アレイなどのテーブルである。特に明記しない限り、Kは、エンコーダのソースシンボルの数を示し、Rは、静的エンコーダによって生成される冗長シンボルの数を示し、Lは、「中間シンボル」、すなわち、ソースシンボルと冗長シンボルの組合せの数であり、したがって、L=K+Rである。

0099

以下で説明するように、静的エンコーダのいくつかの実施形態では、2つのタイプの冗長シンボルが生成される。ここでの多くの例において使用される、特定の実施形態では、第1のセットはLDPCシンボルを備え、第2のセットはHDPCシンボルを備える。一般性の損失なしに、本明細書の多くの例は、SをLDPCシンボルの数として参照し、HをHDPCシンボルの数として参照する。3つ以上の冗長シンボルのタイプが存在し得、したがって、R=S+Hである必要はない。LDPCシンボルとHDPCシンボルとは異なる度数分布を有し、当業者ならば、本開示を読めば、LDPCシンボルまたはHDPCシンボルではない冗長シンボルであって、2つ(またはそれ以上)のシンボルセットを備え、各セットが他のセットの度数分布とは異なる度数分布を有する、冗長シンボルをどのように使用すべきかがわかるであろう。よく知られているように、冗長シンボルのセットの度数分布は、度数の分布を指し、冗長シンボルの度数は、冗長シンボルが依存するソースシンボルの数を指す。

0100

Pは、中間シンボルの中の永久的非活動シンボルの数を示す。永久的非活動シンボルは、信念伝搬を続ける (および次いで非活動化シンボルを解決した後に解決するために戻って くる)ために、信念伝搬ネットワークにおいて特定の処理のために指定されたシンボル、すなわち、「除外」または「非活動化」されるべきシンボルであり、永久的非活動化シンボルは、そのような処理のためにエンコーダにおいて指定されるという点で、他の非活動化シンボルとは区別される。

0101

Nは、復号の試みがデコーダ155によって行われる受信シンボルの数を示し、Aは、「オーバーヘッド」シンボルの数、すなわち、Kを超えた受信された被符号化シンボルの数である。したがって、A=N−Kである。

0102

K、R、S、H、P、NおよびAは、整数であり、典型的にはすべて1以上の整数であるが、特定の実施形態では、これらのうちのいくつかは1または0であり得る(たとえば、R=0は、冗長シンボルがない場合であり、P=0は、OTF非活動化しかない、Shokrollahi IIの場合に頼る)。

0103

ソースシンボルのベクトルは(C(0),...,C(K−1))で示され、冗長シンボルのベクトルは(C(K),...,C(L−1))で示される。したがって、システマティックな場合、(C(0),...,C(L−1))は中間シンボルのベクトルを示す。それらの中間シンボルのうちのP個は、「永久的非活動」であると指定される。「PIリスト」は、中間シンボルのうちのどれが永久的非活動シンボルであるかを示す。多くの実施形態では、PIリストは単に最後のP個の中間シンボル、すなわち、C(L−P),...,C(L−1)を指すが、これは要件ではない。その場合は、この説明の残りの部分を簡略化するためのものとのみ考えられる。

0104

PIリスト上にない中間シンボルは、本明細書では「LT中間シンボル」と呼ぶ。本例では、LT中間シンボルはC(0),...,C(L−P−1)となる。D(0),...,D(N−1)は、受信された被符号化シンボルを示す。

0105

値のアレイが「N(0),...,N(x)」などと記述される場合、それは1つまたは2つの値しかない場合を除外するものではないので、これは、少なくとも3つの値を必要とするものと考えられるべきではないことに留意されたい。

0106

永久的非活動化を使用した符号化方法
図3は、図1に示すエンコーダ115の1つの特定の実施形態のブロック図である。そこで示されているように、ソースシンボルは、入力バッファ205に記憶され、静的エンコーダ210と動的エンコーダ220とに供給され、動的エンコーダ220は、鍵入力と他の入力とをも受信する。静的エンコーダ210は、内部値プログラム命令とを記憶するための内部記憶装置215(メモリ、バッファ仮想メモリ登録記憶装置など)を含み得る。同様に、動的エンコーダ220は、内部値とプログラム命令とを記憶するための内部記憶装置225(メモリ、バッファ、仮想メモリ、登録記憶装置など)を含み得る。

0107

いくつかの実施形態では、冗長性計算器230は、作成すべき冗長シンボルの数Rを判断する。いくつかの実施形態では、静的エンコーダ210は、冗長シンボルの2つの別個のセットを生成し、特定の実施形態では、第1のセットは、最初のS個の冗長シンボル、すなわち、シンボルC(K),...,C(K+S−1)であり、それらはLDPCシンボルであるが、第2のセットは、次のH個の冗長シンボル、すなわち、C(L−H),...,C(L−1)であり、それらはHDPCシンボルである。PIリストが最後のP個の冗長シンボルである場合、(P≧Hである場合)H個の冗長シンボルのすべてがPIリスト上にあるか、または(P<Hの場合)P個の冗長シンボルのすべてがHDPCシンボルであり得る。

0108

シンボルのこれらの2つのセットの生成をもたらす演算は極めて異なり得る。たとえば、以下で説明するいくつかの実施形態では、LDPC冗長シンボルを生成するための演算はバイナリ演算であり、HDPCシンボルを生成するための演算は非バイナリ演算である。

0109

動的エンコーダ220の演算が図4にさらに詳細に説明されている。一実施形態によれば、動的エンコーダ220は、2つのエンコーダ、すなわち、PIエンコーダ240とLTエンコーダ250とを備える。いくつかの実施形態では、LTエンコーダ250は連鎖反応エンコーダであり、PIエンコーダ240は特定のタイプの連鎖反応エンコーダである。他の実施形態では、これらの2つのエンコーダは極めて同様であり得るか、またはPIエンコーダ240は連鎖反応エンコーダではない。これらのエンコーダがどのように定義されようとも、LTエンコーダ250は、永久的非活動的でないと指定されたLT中間シンボルC(0),...,C(L−P−1)からシンボルを生成し、PIエンコーダ240は、永久的非活動中間シンボルC(L−P),...,C(L−1)からシンボルを生成する。これらの2つの生成されたシンボルはコンバイナ260に入り、コンバイナ260は、最終の被符号化シンボル270を生成する。

0110

本発明のいくつかの実施形態では、永久的非活動化シンボルの一部はLT符号化プロセスに関与し、永久的非活動化シンボルでないシンボルの一部はPI符号化プロセスに関与し得る。言い換えれば、PIリストと、LT中間シンボルを備えるシンボルのセットとは、独立である必要はない。

0111

好適な実施形態では、コンバイナ260に供給されるシンボルは、同じ長さを有し得、コンバイナ260によって実行される機能は、被符号化シンボル270を生成するための、これらのシンボルに対するXOR演算である。ただし、これは、本発明の動作には不要である。同様の結果をもたらし得る他のタイプのコンバイナが想定され得る。

0112

他の実施形態では、中間シンボルは、3つ以上のセット、たとえば、各々がそれの関連するエンコーダ240をもつ、LTシンボルの1つのセットと、PIシンボルのいくつか(2つ以上)のセットとに再分割される。もちろん、各関連するエンコーダは、異なるセットのための異なるエンコーダとして働くとき、符号化プロセスに従って異なる命令に基づいて動作する、共通のコンピューティング要素またはハードウェア要素として実装され得る。

0113

PIエンコーダ240によって実行され得るPI符号化プロセス241の例示的な演算が図5に例示されている。生成されるべき被符号化シンボルに対応する鍵I_aを使用して、ステップ261において、エンコーダは、正の重みWPと、両端の値を含むLPとL−1との間のWP個の整数を含んでいるリストALPとを判断する。ステップ263において、リストALP=(t(0),...,t(WP−1))である場合、シンボルXの値を

0114

に設定し、ただし、

0115

はXOR演算を示す。

0116

いくつかの実施形態では、重みWPは、3、または4、または何らかの他の固定数など、何らかの数に固定される。他の実施形態では、重みWPは、2または3のいずれかに等しくなるように選定などされている、可能なそのような数の小さいセットに属し得る。たとえば、付録Aの実施形態に示すように、重みWPは、LTエンコーダ250によって実行され得るLT符号化プロセス251によって生成されたシンボルの重みに依存する。LTエンコーダ250によって生成された重みが2である場合、WPは、鍵I_aに応じて、2または3のいずれかとなるように選定され、WPが2であるかまたは3であるかの回数の比率はほぼ等しい。LTエンコーダ250によって生成された重みが3よりも大きい場合、WPは2となるように選定される。

0117

図6は、本発明の実施形態のうちの1つによる、Luby IとShokrollahi Iとの教示を使用したLT符号化プロセス251の一例である。ステップ267において、鍵I_aを使用して、それぞれ重みWLとリストALとを生成する。ステップ269において、リストALP=(j(0),...,j(WL−1))である場合、シンボルXの値を

0118

に設定する。

0119

図7に、重みWLを計算する演算を示す。そこで示されているように、ステップ272において、生成されるべき被符号化シンボルに関連する数vを作成し、その被符号化シンボルの鍵I_aに基づいて計算し得る。エンコーダとデコーダとが一致することができる限り、数vは、被符号化シンボルのインデックス、代表ラベルなどであるか、または別個の数であり得る。この例では、vは、0と220との間にあるが、他の例では、(0〜232などの)他の範囲が可能である。vの生成は、ランダム性生成テーブルを使用して明示的に行われ得るが、これらの乱数をどのように生成すべきかの厳密な演算は異なることができる。

0120

エンコーダはテーブルMにアクセスできるものと仮定され、それの一例が図8に与えられている。「度数分布ルックアップ」テーブルと呼ばれるテーブルMは、2つの列と複数の行とを含んでいる。左列は、重みWLの起こり得る値で標示され、右列は、両端の値を含む0と220との間の整数で標示されている。vのどんな値にも、度数分布ルックアップテーブルのM[d]列中に、M[d−1]<v≦M[d]が真である、厳密に1つのセルがある。その1つのセルに対して、d列中の対応する値があり、エンコーダは、その値を被符号化シンボルの重みWLとして使用する。たとえば、被符号化シンボルがv=900000を有する場合、その被符号化シンボルの重みはWL=7となる。

0121

静的エンコーダ210は要素SE(k,j)にアクセスでき、ただし、k=0,...,R−1およびj=0,...,L−1である。これらの要素は、α*Xがシンボルであるようにフィールドの要素αとシンボルXとの間の演算*が存在する任意の有限フィールドに属することができ、

0122

であり、ただし、

0123

はXOR演算を示す。そのようなフィールドおよび演算はShokrollahi IVに詳述されている。静的エンコーダ210の演算は、ソースシンボルC(0),...,C(K−1)の所与のシーケンスについて、式1に示す関係を満たす冗長シンボルC(K),...,C(L−1)のシーケンスを計算するものとして記述され得、ただし、Z(0),...,Z(R−1)は、エンコーダとデコーダとに知られている値(たとえば、0)である。

0124

式1では、エントリSE(k,j)はすべてバイナリであり得、またはそれらの一部はフィールドGF(2)に属することができるが、他のエントリは他のフィールドに属する。たとえば、付録Aの実施形態の対応する行列が図9に与えられている。それは、S個の行をもつ部分行列と、H個の行をもつ部分行列という、2つの部分行列を備える。上側の部分行列は2つの部分を備える。その部分行列は、あらゆる行が2つの連続する1を有する、最後のP個の列を備える(位置はモジュロPで計数される)。この行列の最初のW=L−P個の列は、S×S単位行列を伴う循環行列(circulant matrix)を備える。循環行列はB個の列を備え、各々(場合によっては最後以外)はS個の行を有する。これらの循環行列の数はceil(B/S)である。これらの循環行列中の列は、各々厳密に3つの1を有する。k番目の循環行列の第1の列は、位置0と、(k+1) mod Sと、(2k+1) mod Sとに1を有する。他の列は、第1の列の巡回(cyclic)シフトである。図9中の下側のH個の行は、H×H単位行列を伴うGF(256)中のエントリをもつ行列Qを備える。

0125

αが、最小多項式x8+x4+x3+x2+1をもつGF(256)の要素を示す場合、行列Qは、図10に与える行列に等しい。ここで、Δ1,...,ΔK+S-1は、2つの非ゼロエントリの位置が、付録Aのセクション5.3.3.3.で概説するプロシージャに従って擬似ランダムに判断される重み2の列である。(付録Aに与えたものなどの)値S、P、およびHの適切な選定のために、図10の行列は、対応する符号の優れた復元特性をもたらす。上記で説明したプロシージャは図11に例示されている。ステップ276において、行列SEを0に初期化する。ステップ278において、LDPCシンボルの数に等しい入力変数Sをプロセスに与え、ペア(i,j)について、i=j mod S、またはi=(1+floor(j/S))+j mod S、またはi=2*(1+floor(j/S))+j mod Sとなるように、SE(i,j)の値を1に設定する。このステップは、図9中の循環行列に対処する。

0126

ステップ280において、図9中の単位行列ISに対応する位置を1に設定する。ステップ282において、図9中の行列のPI部分に対応する位置を1に設定する。これらの位置は形式(i,l)および(i,t)であり、ただし、l=i mod Pおよびt=(i+1) mod Pである。ステップ284において、図9中の行列Qに対応する位置を設定する。したがって、行列Qは、このステップへの追加の入力として与えられる。ステップ286において、図9の行列中の単位行列IHに対応する位置を1に設定する。

0127

行列SEのための他の選定は、可能であり、特定の適用例と、全体的な符号に要求される要件とに依存する。式1中の行列がどのように選定されようとも、静的エンコーダ210のタスクは様々な方法で達成され得る。たとえば、本開示を読めば当業者に明らかになるように、未知の値C(K),...,C(L−1)を復元するためのプロセスとしてガウス消去法が使用され得る。

0128

復号および永久的非活動化
復号問題は、デコーダ155が、対応する鍵Ia,Ib,...とともにN個の被符号化シンボルB(Ia),B(Ib),...を有することであると述べられ得る。これらの被符号化シンボルのセット全体、またはそれらのサブセットは、デコーダによって受信されていることがあり得るが、他の被符号化シンボルは、他の手段によってデコーダに与えられていることがあり得る。デコーダの目的は、ソースシンボルC(0),...,C(K−1)を復元することである。表示を簡略化するために、受信された被符号化シンボルをD(0),...,D(N−1)によって示す。

0129

復号演算の多くは、行列とそのような行列に対する演算との言語とを使用して、特に、そのような行列をもつ連立方程式を解くことによって簡潔に記述され得る。以下の説明では、方程式は、受信された被符号化シンボルに対応することができ、変数は、受信された被符号化シンボルに基づいて解決されるべきである、ソースシンボル、または中間シンボルとしばしば呼ばれるソースシンボルとソースシンボルから生成された冗長シンボルとの合成セットに対応することができる。付録Aとして与える仕様では、被符号化シンボルは、「符号化シンボル」と呼ばれることがある(また他の変形態が存在する)が、明細書全体および付録を読めば、参考文献がどのように関係するかが明らかなはずである。また、方程式に対する行列および演算および解は、それらの数学演算に対応するコンピュータ命令として実装され得、実際には、コンピュータ、プロセッサ、ハードウェアまたは何らかの電子的要素なしにそのような演算を行うことは実用的でないことを理解されたい。

0130

永久的非活動化は、復号プロセスの第1の段階が開始される前に、永久的非活動化シンボルまたは変数と呼ばれる非活動化すべき変数のセットをデコーダにおいて判断するために使用される。以下で説明する永久的非活動化復号方法が既存の符号に適用されるか、または、符号が、永久的非活動化復号に関連してより一層良好に動作するように特別に設計され得る。永久的非活動化復号方法は、どんな連立一次方程式を解くためにも適用され得、特に、連鎖反応符号、IETFLDPC符号、およびトルネード符号に適用され得る。

0131

永久的非活動化復号は、既知の一次方程式値のセットから未知の変数のセットについて解くときはいつでも信念伝搬復号および/またはOTF非活動化復号と組み合わせて適用され得る一般的な方法であり、一次方程式のセットに基づいて効率的な符号化方法と復号方法とを実装するときは特に有益である。第1の段階では、既知の符号化方法の構造に基づいて、または受信した方程式に基づいて、未知の変数のセットが、永久的非活動化であると宣言され、永久的非活動化変数は、復号プロセスの第2の段階において、(第2の段階の一次方程式が簡約されたとき、同じ簡約が永久的非活動化変数に対して実行されることを除いて)一次方程式から除去され、「解かれた」ものと見なされる。

0132

第2の段階では、信念伝搬復号が、前に説明した信念伝搬復号を使用して永久的非活動化されていない未知の変数に適用されるか、または、OTF非活動化復号方法の第1の段階について説明したものと同様に、OTF非活動化復号が、永久的非活動化されていない未知の変数に適用され、それによって、簡約された被符号化シンボルまたは方程式のセットを生成する。第2の段階から生じた簡約された被符号化シンボルまたは方程式は、非活動化されていない変数またはシンボルへの依存性が除去され、したがって、簡約された被符号化シンボルまたは方程式は非活動化変数またはシンボルのみに依存するという特性を有する。いくつかの実装形態では、元の被符号化シンボルと簡約された被符号化シンボルとの両方が利用可能であり得るように、元の被符号化シンボルまたは方程式も保持され得ることに留意されたい。

0133

第3の段階では、OTF非活動化復号を使用して第2の段階において生成された追加のOTF非活動化変数とともに永久的非活動化変数について、簡約された被符号化シンボルまたは方程式を使用して、たとえば、ガウス消去法、または永久的非活動化変数の間の関係の特殊な構造がもしあればそれを使用して解かれ、一次方程式が、ガウス消去法を使用することによるよりも効率的に解くために使用される。

0134

第4の段階では、非活動化されなかった変数について解くために、元の被符号化シンボルまたは方程式(あるいは再導出された元の被符号化シンボルまたは方程式)とともに、解かれた非活動化変数、すなわち、OTF非活動化変数または永久的非活動化変数のいずれかの値が使用される。

0135

永久的非活動化復号方法の利点のうちの1つは、永久的非活動化以外のOTF非活動化の数wが、概して小さくなるかまたは0になり、また、どの被符号化シンボルが受信されるかとはほとんど無関係になることができるということである。これは、どの被符号化シンボルが受信されるかとは無関係に復号複雑度を一貫して小さくさせ、より信頼できる復号を可能にし、より効率的にスケジュールされ得るより予測可能で少ないメモリアクセスを可能にすることができる。第2の段階には少数のOTF非活動化しかなく、また、第2の段階におけるOTF非活動化は、概して、シンボル演算のパターンをいくぶん予測不可能にさせ得る復号プロセス中でしか判断されないので、復号中にメモリアクセスパターンがより予測可能になり、全体的により予測可能で効率的な復号プロセスが可能になる。

0136

上記の多くの変形態がある。たとえば、段階は、非連続インターリーブ順序で実行され得る。別の例として、非活動化シンボルについて、今度は、複数の追加の段階においてOTF非活動化復号または永久的非活動化復号のいずれかを使用して、第3の段階中に解決され得る。別の例として、永久的非活動化復号は、誤り訂正符号、または消去訂正符号、あるいは連立一次方程式を使用して解決され得る他の適用例のために使用され得る、連立一次方程式および変数に適用され得る。別の例として、これらの方法は、システマティック符号と非システマティック符号の両方に適用され得る。別の例として、これらの方法はまた、符号化プロセス中に、たとえば、非システマティック符号からシステマティック符号を生成するためのShokrollahi IIIにおいて教示されている方法を使用して符号化するときに適用され得る。

0137

場合によっては、永久的非活動化復号方法が特に有効となるように符号化プロセスを設計することが可能である。たとえば、信念伝搬復号は、適用され得るときはいつでも、計算量的に効率的であることが知られているが、単独で使用されると、高信頼性復号を行うことができないことも知られている。信念伝搬復号がOTF非活動化復号内で使用されるとき、信念伝搬ステップは極めて効率的に処理され得るが、信念伝搬ステップ内に点在させられたOTF非活動化ステップは、復号を減速させる可能性があり、そのようなOTF非活動化ステップがより多くあればあるほど、復号プロセスはより遅くなる。

0138

OTF非活動化復号の典型的な実施形態では、N+R個の一次方程式値を使用してK+R個の未知の変数について解くことを試みるとき、OTF非活動化ステップの数は、一般に、N=Kのとき、すなわち、ゼロオーバーヘッドを使用して変数を解くことを試みるときに最大になる。一方、NがKよりも大きくなるにつれて、一般的には、OTF非活動化ステップが場合によってはなくなる程度にNが十分大きくなるときまで、OTF非活動化復号の複雑さは、より少ないOTF非活動化ステップに起因して減少することになり、非活動化復号は、信念伝搬復号と同程度またはほぼ同程度に計算量的に効率的になる。OTF非活動化復号の他の実施形態では、NがKよりもかなり大きいときでも、OTF非活動化の数は大きいままであり得る。

0139

永久的非活動化復号の1つの好適な実施形態では、永久的非活動化変数の数Pと、一次方程式の構造とは、一次方程式のK+R個の値からOTF非活動化復号を使用して永久的非活動化されていないL−P個の変数について解くとき、OTF非活動化復号中にOTF非活動化ステップの数が小さく、場合によっては0になり、したがって、OTF非活動化復号ステップが、信念伝搬とほぼ同程度に計算量的に効率的になるように設計される。

0140

好適な実施形態では、一次方程式の構造は、OTF非活動化復号段階が信念伝搬復号とほぼ同程度に効率的になるように設計される。そのような好適な実施形態では、一次方程式に対する永久的非活動化変数の関係は、OTF非活動化復号段階からのOTF非活動化変数とともに永久的非活動化変数から構成される非活動化変数について解く段階が効率的に実行され得るものになる。さらに、好適な実施形態では、永久的非活動化シンボルの構造は、解かれた非活動化変数から非活動化されていない変数の解を完成する段階が計算量的に効率的であるものになる。

0141

永久的非活動化を用いた連鎖反応符号の復号
図12に、N個の受信された被符号化シンボルまたは式と、R個の既知の静的シンボルまたは式とを使用して、デコーダによって解かれるべき変数のセットの行列表現を示す。デコーダのタスクは、この図に与えられている連立一次方程式を解くことである。一般に、シンボル/式は、デコーダによってアクセス可能なメモリまたはストレージに記憶された値によって表され、以下で説明する行列演算は、デコーダによって実行可能な命令によって実装される。

0142

図12に示す行列は、L=K+R個の列と、N+R個の行とを備える。LT部分行列は、N個の被符号化シンボルと、LT符号化プロセス251によって判断されたL個の中間シンボルのうちのL−P個のLTシンボルとの間の関係を表す。PI部分行列は、N個の被符号化シンボルと、PI符号化プロセス241によって判断されたL個の中間シンボルのうちのP個のPIシンボルとの間の関係を表す。式1の行列SEは、静的エンコーダ210によって判断された中間シンボルの間の関係を表す。デコーダは、受信された被符号化シンボルの鍵に基づいて、および符号構成から、これらの関係を判断することができる。

0143

図12の連立一次方程式は、図13に示す形式に上記の行列を変換するために、Shokrollahi IIにおいて教示されているOTF非活動化方法を使用して、上記の行列の行/列置換によって解かれる。図13は、下三角行列LO310と、OTF非活動化に対応する(OTFIと呼ばれる)行列320を備えるいくつかの列と、永久的非活動中間シンボルのセットまたはそれのサブセットに対応する行列330PIと、行列LOをもたらす三角行列化プロセスにおいて使用されない被符号化シンボルまたは静的シンボルに対応する行列340ELとを備える。

0144

図14は、図12中の行列をもたらすプロセスを実行し得る要素について説明しているブロック図である。図14は、LT行列生成器347と、PI行列生成器349と、静的行列生成器350とを備える。鍵Ia,Ib,...を受信すると、LT行列生成器は図12中の行列LTを作成し、PI行列生成器349は図12の行列PIを作成する。これらの2つの行列の連結が静的行列生成器350に転送され、静的行列生成器350は、追加のヒントとして静的鍵S_0,S_1,...を取り得る。静的行列生成器のタスクは行列SEの作成であり、静的行列生成器の出力は、図12に与えられている完全行列である。

0145

LT行列生成器347の演算とPI行列生成器349の演算とは、図15中のLTエンコーダ250の演算とPIエンコーダ240の演算とにそれぞれ密結合される。静的行列生成器350の演算は、静的符号化のために使用される式1の行列SEの再作成である。

0146

次に、LT行列生成器347と、PI行列生成器349と、静的行列生成器とについて、それらが実行し得る演算に関してさらに詳細に説明する。

0147

図16は、LT行列生成器347によって採用される方法の一実施形態500を示すフローチャートである。ステップ505において、LT行列生成器347は、フォーマットN×(L−P)の行列LTをすべて0に初期化する。次に、ステップ510において、鍵Ia,Ib,...を使用して、重みWL(0),...,WL(N−1)とリストAL(0),...,AL(N−1)とをそれぞれ生成する。リストAL(i)の各々は、範囲0,...,L−P−1内のWL(i)個の整数(j(0),...,j(WL(i)−1))を備える。ステップ515において、これらの整数を使用して、エントリLT(i,j(0)),...,LT(i,j(WL(i)−1))を1に設定する。上記で説明したように、行列LTは、受信シンボル(D(0),...,D(N−1))に関して未知数(C(0),...,C(L−1))の連立方程式に寄与する。

0148

当業者なら諒解され得るように、ここで説明するLT行列生成器の演算は、図6のLT符号化プロセス251の演算と同様である。

0149

図17は、PI行列生成器349によって採用される方法の一実施形態600を示すフローチャートである。ステップ610において、PI行列生成器349は、フォーマットN×Pの行列PIをすべて0に初期化する。次に、ステップ615において、鍵Ia,Ib,...を使用して、重みWP(0),...,WP(N−1)とリストALP(0),...,ALP(N−1)とをそれぞれ生成する。リストALP(i)の各々は、範囲0,...,P−1内のWP(i)個の整数(j(0),...,j(WP(i)−1))を備える。ステップ620において、これらの整数を使用して、エントリPI(i,j(0)),...,PI(i,j(WP(i)−1))を1に設定する。PI行列生成器の演算は、図5中のPI符号化プロセス241の演算と同様である。

0150

上記で説明したように、行列LTおよびPIは、受信シンボル(D(0),...,D(N−1))に関して未知数(C(0),...,C(L−1))の連立方程式に寄与する。その理由は、LTエンコーダが重みWL(i)と関連リストAL(i)=(j(0),...,(WL(i)−1))とを選定し、PIエンコーダが重みWP(i)と関連リストALP(i)=(t(0),...,t(WP(i)−1))とを選定すると、対応する被符号化シンボルD(i)が、以下で示すように得られるからである。これらの式は、0とN−1との間のiのすべての値について累算されると、式2に表す所望の連立方程式を生じる。

0151

重みWLは、図7に与えられているプロシージャと同様のプロシージャを使用して計算され得る。当業者ならば、本開示を検討すれば、どのようにこれを、各々が異なる度数分布で動作している3つ以上のエンコーダがある場合に拡張すべきかがわかるであろう。

0152

行列生成器のわずかに異なる流れ図が図18に与えられている。図18は、LT行列生成器710と、静的行列生成器715と、PI行列生成器720とを備える。鍵Ia,Ib,...を受信すると、LT行列生成器710は、図15に示す行列LTを作成し、静的行列生成器715は、図15に示す行列SEを作成し、さらなる入力として追加の静的鍵S_0,S_1,...を取り得る。これらの2つの行列の連結がPI行列生成器720に転送され、PI行列生成器720は行列PIを作成する。LT行列生成器710の演算は、図16において詳述したLT行列生成器347の演算とまったく同じであり得る。静的行列生成器715の演算は、図14中の静的行列生成器350の演算とは異なり得る。具体的に、図19に、そのような演算の例示的な一実施形態を詳述する。

0153

ステップ725において、行列SEを0に初期化する。ステップ730において、LDPCシンボルの数に等しい入力変数Sをプロセスに与え、ペア(i,j)について、i=j mod S、i=(1+floor(j/S))+j mod S、またはi=2*(1+floor(j/S))+j mod Sであるとき、SE(i,j)の値を1に設定する。ステップ735において、図9中の単位行列ISに対応する位置を1に設定する。ステップ740において、行列Tに対応する位置を、このステップへの追加の入力として与える。この行列は、複数の有限フィールドにおけるエントリを有し得、異なる適用例に対して異なることができる。それは、符号に要求される要件に基づいて選定され得る。

0154

図20は、PI行列生成器720によって採用される方法の一実施形態を示す簡略流れ図である。ステップ745において、PI行列生成器349は、フォーマット(N+R)×Pの行列PIをすべて0に初期化する。次に、ステップ750において、鍵I_a,I_b,...を使用して、重みWP(0),...,WP(N−1)とリストALP(0),...,ALP(N−1)とをそれぞれ生成する。リストALP(i)の各々は、範囲0,...,P−1内のWP(i)個の整数(j(0),...,j(WP(i)−1))を備える。ステップ755において、これらの整数を使用して、エントリPI(i,j(0)),...,PI(i,j(WP(i)−1))を1に設定する。図20中のPI行列生成器の演算は、この行列生成器が、もうR個の行をもつ行列を作成し、図15中の行列と密結合されることを除いて、図17のPI行列生成器の演算と同様である。

0155

図12または図15中の連立方程式は、一般に疎であり、すなわち、関与する行列中の非ゼロエントリの数は、一般に、可能なエントリの半分よりもはるかに小さい。そのような場合、行列は直接記憶される必要がないことがあるが、これらの行列のあらゆる個々のエントリを再作成するのを助ける指示が記憶され得る。たとえば、行列LTまたはPIの行の各々について、プロセスは、図5図6において計算された重みとネイバーのリストとを記憶することを希望し得る。他の方法も可能であり、それらの方法の多くは、本明細書において、または参照により本明細書に組み込まれる開示において説明されている。

0156

行列生成器が、図12または図15によって与えられた形式で連立方程式を作成した後、デコーダのタスクは、C(0),...,C(L−1)の未知の値についてこの連立方程式を解くことである。この目的を達成するために、限定はしないが、ガウス消去法、あるいはLuby I、Luby II、Shokrollahi I、II、III、IV、またはVに記載されている方法のうちのいずれかを含む、いくつかの異なる方法が適用され得る。

0157

次に、図12または図15における連立方程式を解くための可能な方法について、図21図26を参照しながら略述する。本発明の実施形態のうちのいくつかによるデコーダの演算のフローチャートが図21に与えられている。ステップ1305において、前に説明した方法のうちのいくつかを使用して復号行列を作成する。ステップ1310において、行置換と列置換とを使用してこの行列を再構成する。上記で説明したように、行置換と列置換とを適用することによって図12中の行列または図15中の行列のいずれかからそのような行列を取得し得る。これを達成するために、Shokrollahi IIのオンザフライ非活動化復号と組み合わせた連鎖反応復号が使用され得る。したがって、図22中の式が満たされるように、セット{0,1,...,L−1}に作用する置換πと、セット{0,1,...,N+R−1}に作用する置換τとがある。

0158

本明細書では、wは、図13中の行列LOの行と列との数、すなわち、永久的非活動化もOTF非活動化もされていない中間シンボルの数を示す。ステップ1315において、図13の行列LOを使用して、対角線を下回る行列LOのすべてのエントリをゼロアウトする。そうする際に、図23中の式の右辺にあるシンボルのセットは、連立方程式の新しい右辺がD(τ(i))の一部のXORによって取得されるように、同じ演算を尊重する必要がある。

0159

図24に示すように、この演算後に、行列810は単位行列になり、840中の行列ELはそのままになり、復号プロセスが、行列LOを単位行列に簡約するのに必要であった演算に従ってこれらの行列の行を一緒にXORする必要があるので、行列OTFIおよびPIは、820中のOTFI−2および830中のPI−2に変わる。

0160

復号プロセスの次のステップはステップ1320であり得、LOを下回る残りの行列の残部を除去して、図25に示す形式の行列を得る。このステップ後に、E(0),...,E(N+R−1)と、行列EL_2の行の数uと、EL_2の列の数gとによって元のシンボルD(0),...,D(N_R−1)の置換され簡約された値を示すことにより、図25中の行列の構造は、式3に従って値C(π(L−g)),...,C(π(L−1))についてu個のより小さい連立一次方程式を生じる。

0161

図21で説明する復号プロセスなどの復号プロセスは、ステップ1330においてこの連立方程式を様々な手段で解き得、たとえば、ガウス消去法プロセス、または連鎖反応コーディングとガウス消去法との組合せを使用することによって、あるいは非活動化復号の別の適用によって、あるいは他の手段によって解き得る。ガウス消去法は、たとえば、Shokrollahi IVにおいて教示されているように、行列ELが複数のフィールドに属する要素を有する場合、GF(256)などのより大きいフィールドにおける計算からGF(2)における計算を分離するように変更され得る。

0162

式3の連立方程式が、デコーダによって採用されたプロセスを使用して解けない場合、ステップ1335において、デコーダは対策を施し得る。そのような対策は、エラーフラグを付け、プロセスを停止することを含み得るか、あるいはより多くの被符号化シンボルを要求することを含み得るか、あるいはプロセスを停止し、これまで復元することが可能であった中間シンボルまたはソースシンボルのリストを、デコーダを使用しているアプリケーションに戻し得る。連立方程式が解ける場合、デコーダは、非活動化中間シンボルの値C(π(L−g)),...,C(π(L−1))を復元し得る。いくつかの変形態では、ステップ1330において、非活動化中間シンボルの他にいくつかの他の中間シンボルが復元されることもあり得る。

0163

これらのシンボルの値が復元されると、デコーダは、後退代入に関与するステップ1340に進む。値C(π(L−g)),...,C(π(L−1))を復元すると、図26に与えられているタイプの連立方程式を生じる。この連立方程式は、一般的な連立方程式よりも解くのが容易である。たとえば、デコーダは、そのように行うために図23に示すプロセスを使用し得る。図23の右辺にある第1のベクトルを取得するプロセスは、既知のシンボルの値を連立方程式に代入するプロセスであるので、後退代入と呼ばれることがある。当業者なら本開示を読めばわかるように、図23図26とに与えられている連立方程式は数学的に等価である。

0164

図23において、デコーダは、右辺上の行列のエントリが、行列乗算のルールを使用して、すでに解決されたベクトルC(π(L−g)),...,C(π(L−1))のエントリで乗算され、得られたエントリをE(0),...,E(L−g−1)でXORするプロセスを実装することによって、未知の値C(π(0)),...,C(π(L−g−1))を取得する。得られたエントリをE(0),...,E(L−g−1)でXORし、このようにして値C(π(0)),...,C(π(L−g−1))を復元するプロセスは、図21中のデコーダのステップ1345を備える。

0165

いくつかの適用例では有用であるが、図23の右辺の行列は一般に疎でなく、したがって、要素C(π(j))の1つを得るためには、gに比例する数のXORが実行されなければならないので、この方法は、いくつかの好適な実施形態において大きい計算オーバーヘッドをもたらし得る。いくつかの実施形態では、この数は、たとえば、永久的非活動化の数Pがそもそも大きくなるように選定されており、gが少なくともPと同程度の大きさであり得るので、大きくなり得る。これは、永久的非活動化シンボルの数Pの値に厳しい制限を与える可能性があり、より小さい値のPが使用された場合、これはOTF非活動化中間シンボルの数の増加をもたらし得る。

0166

図27は、図21で説明したプロセスよりも計算量的に効率的であり得る修正された復号プロセスについて説明するものである。このプロセスのステップ1405から1435は、図14中のプロセスの対応するステップと同じであり得る。随意に、このプロセスは、将来の使用のために、図12または図15中の元の行列あるいはこの行列の関係する部分、ならびに元のシンボルD(0),...,D(N+R−1)のコピーを追加のメモリロケーション中に保持し得る。これは、このプロセスの動作には不要であるが、アプリケーションがこれらのコピーを保持するための十分なメモリリソースを有する場合、それはさらなる速度の利点をもたらし得る。代替的に、プロセスは、元のシンボルD(0),...,D(N+R−1)のコピーのみを保持し、行列のコピーを保持せず、プロセスが必要とするときにその行列を再作成し得る。ステップ1440は、図22中の元の連立方程式、または図28に与えられているこの連立方程式の最上部のみを取り戻すために、行列の記憶されたコピーを使用するかまたはステップ1415のプロセスを元に戻す。この時点で、図29に与えられている行列1510は疎であり、値C(π(w)),...,C(π(L−1))は知られており、ただし、w=L−gである。

0167

よく知られているように、図29中の式の右辺は、少数のXORのシンボル、すなわち、行列OTFI中の非ゼロエントリの数+行列PI中の非ゼロエントリの数に等しい数のXORのシンボルに関与する、計算量的に効率的なプロセスを介して計算され得る。プロセスのこのステップは、図27の1445によって示されている。このステップが完了した後、図29中の式の右辺は計算されており、未知数が値C(π(0)),...,C(π(w−1))である連立方程式を解くことになる。右辺の下三角LOが疎であるので、すなわち、この連立方程式を解くためのシンボルのXORの数が、行列LO中の非ゼロエントリの数に 等しく、この数は、一般に、可能な非ゼロエントリの最大数w*wよりもはるかに小さいので、この連立方程式は、ステップ1450において連鎖反応復号を使用して解かれ得る。

0168

永続的非活動化の数の選定
永久的非活動化の数の選定は、パフォーマンス全体に影響を及ぼすことができ、したがって重要であり得る。一方では、この数は、できるだけ大きくなるように選定される必要がある。この数が大きい場合、OTF非活動化の数は極めて小さい数に低減され、時々0にさえ低減され得る。これは、図15中のLT行列とSE行列(または図23中のそれらの対応する変形態)の組合せが、効果的にも、大きいオーバーヘッドをもつ連鎖反応符号の復号行列であるからである。このことが、OTF非活動化の数を極めて小さくさせる。OTF非活動化は、いくつかの実施形態では管理することがより困難になり得、したがって、OTF非活動化の数を低減することは、速度および/またはメモリに関して利点をもたらし得る。

0169

一方、永久的非活動化の数を増加させることは、実行時間に悪影響を有し得る。たとえば、図21の復号プロセス中のステップ1330と、図27のプロセス中の対応するステップ1430とは、少なくともP個の行および列を有する連立方程式を解くことを必要とする。これを行う1つの方法は、図25中の行列EL−2の可逆部分行列を識別し、その行列を反転させ、反転した行列を使用して中間シンボルの値C(π(L−g−1)),...,C(π(L−1))を得ることであろう。行列EL−2は実施形態の多くにおいて疎であり得ないので、中間シンボルの値を得ることは、約g×gのシンボルのXORを受け得る。gは少なくともPであるので、シンボルのXORの数は少なくともP×Pになり得、したがって、シンボルのXORの全体的な数がKにおいて線形に保持されるべき場合、良い選定は、数PをKの平方根に比例するように設定することである。付録Aの特定の実施形態は、Pを2.5*sqrt(K)程度となるように選定し、この観測歩調を合わせる。Pのこの選定を用いた場合、一般に、OTF非活動化の数は、約Pから0に極めて近くなるかまたは0に等しくなってかなり小さくなるので、これはPの良い選定である。

0170

注目する別の量は、被符号化シンボル、または静的シンボルのために存在する非活動化中間シンボルネイバーの平均数Iである。図27中の復号プロセスのステップ1445は、このステップを達成するために、復元されていない中間シンボルごとに平均してI個ほどのシンボルのXORを必要とし得る。Iが大きい場合、XORのこの数は、復号または符号化プロセスを実行しているプロセスのメモリおよび計算リソースにとって過大であり得る。一方、Iが非常に小さい場合、図25の行列EL−2は最大階数を有していないことがあり、復号可能性を危うくし得る。

0171

より詳細な分析により、永久的非活動化の重要な態様は、図15の行列PIに、列が互いに線形独立であるにように、すなわち、行列ができる限り最大階数であるように作用させることであることが明らかになっている。PIがランダムバイナリ行列である場合、可能な限界までの最大階数が達成され得ることが当業者によく知られている。一方、PIは、平均すると、Kの平方根に反比例する1の部分を各列中に有し得、依然として純ランダム行列階数特性と同じ階数特性を満たし得る。このために、付録Aにおける特定の実施形態は、Iが2と3との間の数になるように選定し、したがって、Kの平方根に比例するPを選定する場合、これは、PIの各列中の1の数が、平均するとKの平方根に反比例することを意味する。

0172

本開示を読めば当業者なら認識されるように、これらの方法の多くの変形態がある。たとえば、XORは、他の演算子、たとえば、より大きい有限フィールド上の線形演算子と置き換えられ得、または、演算子は、異なる演算子、たとえば、いくつかの演算のためのより大きい有限フィールド上のいくつかの線形演算子と、他の演算のためのより小さいより大きい有限フィールド上の他の線形演算子との混合であり得る。

0173

付録Aに関する特定の例
上記で詳述したように、永久的非活動化(すなわち、どの被符号化シンボルが、連鎖反応復号のシーケンスを判断することの一部となる行列操作の部分にならないかに関する所定の決定)がなければ、OTF非活動化の数は、極めてランダムであり得、メモリ消費量に関して潜在的な問題を生じ得る。ソースシンボルの数が極めて大きく、オーバーヘッドが極めて小さい場合、誤り確率は、容認できないほど1に近接し得る。

0174

小さいオーバーヘッドに対する高い誤り確率のために、ソースシンボルの数が大きいとき、良好なシステマティック情報を発見することがますます困難になり得る。本明細書では、システマティック情報は、Shokrollahi IIIの意味においてシステマティック符号を構築することが可能になるために、エンコーダとデコーダとに提供するために必要とされる情報を指す。その上、システマティック情報が取得されたときはいつでも、「平均」では符号はゼロオーバーヘッドにおいて失敗するはずであるので、符号の挙動が、平均的な挙動とは極めてかけ離れていることが予想される。

0175

永久的非活動化を用いた連鎖反応符号の構築のためのパラメータの一部は、図4のLTエンコーダ250のために使用される度数分布と、PIエンコーダ240のパラメータと、永久的非活動化シンボルの数の判断と、冗長静的シンボルの数およびそれらの構造の判断とを含み得、特定の方法の乱数が、発生され、図1中のエンコーダ115とデコーダ155との間で共有され得る。

0176

RQ符号を使用するエンコーダおよびデコーダ
本明細書で説明する方法を使用する、以下「RQ符号」と呼ぶ符号の好適な実施形態が、付録Aのセクション5に詳細に規定されている。付録Aの残りは、ブロードキャストまたはマルチキャストネットワークを介したオブジェクトの信頼できる配信にRQ符号を適用する1つの方法について説明している。

0177

RQ符号は、システマティック符号を実装するために以上および以下で説明する方法を使用し、システマティック符号は、すべてのソースシンボルが、生成され得る被符号化シンボルの中にあることを意味し、したがって、被符号化シンボルは、元のソースシンボルと、エンコーダによって生成されたリペアシンボルとの組合せであると見なされ得る。

0178

以上の符号のいくつかは良好な特性を有するが、それらの実際的適用を高めるいくつかの改善がある。重要な2つの潜在的な改善は、より急なオーバーヘッド障害曲線と、ソースブロック当たりのより大きい数のサポートされるソースシンボルとである。オーバーヘッドは、受信された被符号化シンボルの数と、ソースブロック中のソースシンボルの数との間の差であり、たとえば、オーバーヘッド2は、K個のソースシンボルでソースブロックを復号するためにK+2個の被符号化シンボルが受信されたことを意味する。所与のオーバーヘッドにおける失敗確率は、受信された被符号化シンボルの数がそのオーバーヘッドに対応するとき、デコーダがソースブロックを完全に復元することに失敗する確率である。オーバーヘッド障害曲線は、オーバーヘッド0において開始するオーバーヘッドの増加に応じて、失敗確率がどのように下がるかのプロットである。オーバーヘッド障害曲線は、オーバーヘッドに応じてデコーダの失敗確率が高速または急に低下する場合により優れている。

0179

ランダムバイナリコードは、作業不能な計算複雑さとともに、各追加のオーバーヘッドシンボルについて失敗確率が本質的に係数2だけ下がるオーバーヘッド失敗確率曲線を有するが、本説明の主題は、オーバーヘッド失敗確率曲線に限定され、計算複雑さには限定されない。いくつかのアプリケーションでは、これは十分なオーバーヘッド障害曲線であるが、いくつかの他のアプリケーションでは、より急なオーバーヘッド障害曲線が好適である。たとえば、ストリーミングアプリケーションでは、ソースブロック中のソースシンボルの数の範囲は広くなり得、たとえば、K=40、K=200、K=1000、K=10000になる。良好なストリーミングエクスペリエンスを提供するために、失敗確率は低いこと、たとえば、10-5または10-6の失敗確率が必要とされ得る。帯域幅はしばしばストリーミングアプリケーションのために貴重であるので、ソースシンボルの部分として送られるリペアシンボルの割合は最小限に抑えられなければならない。たとえば、K=200をもつソースブロックを使用するとき、ストリームが送られるネットワークが10%までのパケット損失に対して保護されなければならず、失敗確率が多くて10-6であることが必要とされると仮定する。ランダムバイナリコードは、10-6の失敗確率を達成するためには少なくとも20のオーバーヘッドを必要とし、すなわち、受信機は、この失敗確率で復号するために220個の被符号化シンボルを必要とする。ceil(220/(1−0.1))=245であるので、要件を満たすためにソースブロックごとに合計245個の被符号化シンボルが送られる必要がある。したがって、リペアシンボルは、ストリームの帯域幅要件に追加の22.5%を追加する。

0180

本明細書と付録Aのセクション5とにおいて説明されているRQ符号は、K′のすべてのサポートされる値について値がK=K′である場合、ならびにKの最後のサポートされる値を除くすべてについて値がK=1およびK=K′+1である場合、それぞれ、オーバーヘッド0、1、および2に対して10-2、10-4、および10-6よりも小さい失敗確率を達成する。テストは、様々な損失確率、たとえば、10%、20%、50%、70%、90%および95%の損失確率に対して行われている。

0181

RQ符号を使用する上記の例では、2のオーバーヘッドは10-6の失敗確率を達成するのに十分であり、したがって、ceil(202/(1−0.1))=225であるので、要件を満たすためにソースブロックごとに合計225個の被符号化シンボルのみが送られる必要がある。この場合、リペアシンボルは、ストリームの帯域幅要件に追加の12.5%を追加し、すなわち、ランダムバイナリコードによって必要とされる帯域幅オーバーヘッドよりも10%少ない。したがって、RQ符号改善されたオーバーヘッド障害曲線は、いくつかの極めて肯定的な実際的結果を有する。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ