【手続補正書】
【提出日】平成15年8月6日(2003.8.6)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
受信されたビットあるいはシンボルを復号化するための装置であって、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で実装される１組の相互接続される処理ノードを備え、該処理ノードは、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施しており、
前記１組の相互接続される処理ノードは複数の検査ノード及び複数の変数ノードからなり、変数ノードの少なくとも一部分の各々は、復号されたビットまたはシンボルの対応する１つに関連しており、
前記ブロック並列復号プロセスは、
（ｉ）検査ノードの少なくとも一部分の各々において、その検査ノードに接続された変数ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された変数ノードへ送信することと、
（ｉｉ）検査ノードの少なくとも一部分の各々において、その変数ノードに接続された検査ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された検査ノードへ送信することとの内の少なくとも一方を含むことを特徴とする装置。
【請求項２】
受信されたビットあるいはシンボルを復号化するための装置であって、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で実装される１組の相互接続される処理ノードを備え、該処理ノードは、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施しており、
前記所与のブロックは、復号化されることになるＮ個のビットあるいはシンボルを含み、前記１組の相互接続される処理ノードはさらに、Ｎ個一組の変数ノードと、Ｔ個一組の検査ノードとを含み、前記Ｎ個の変数ノードのうちの１つは、復号化されることになる前記Ｎ個のビットあるいはシンボルそれぞれと関連しており、
前記ブロック並列復号化プロセスは、Ｒｘｉ（ｉ＝０，１、．．．、Ｎ−１）を前記受信されたビットあるいはシンボルとし、ｆ（.）を前記符号によって少なくとも部分的に決定される関数とするとき、関数ｆ（Ｒｘｉ）を前記変数ノードに接続される前記各検査ノードに送信することによって開始されており、
前記関数ｆ（.）は、閾値関数、線形換算関数および近似指数関数のうちの少なくとも１つを含むことを特徴とする装置。
【請求項３】
受信されたビットあるいはシンボルを復号化するための装置であって、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で実装される１組の相互接続される処理ノードを備え、該処理ノードは、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施しており、
前記所与のブロックは、復号化されることになるＮ個のビットあるいはシンボルを含み、前記１組の相互接続される処理ノードはさらに、Ｎ個一組の変数ノードと、Ｔ個一組の検査ノードとを含み、前記Ｎ個の変数ノードのうちの１つは、復号化されることになる前記Ｎ個のビットあるいはシンボルそれぞれと関連しており、
前記ブロック並列復号化プロセスは、全ての前記検査ノードが前記符号の制約条件を満たすときに終了することを特徴とする装置。
【請求項４】
受信されたビットあるいはシンボルを復号化するための装置であって、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で実装される１組の相互接続される処理ノードを備え、該処理ノードは、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施しており、
前記確率依存グラフは、有向確率依存グラフを含んでおり、
前記１組の相互接続された処理ノードはさらに、初期レベル、少なくとも１つの中間レベルおよび最終レベルを有する複数レベルのノードを含み、
前記レベルの前記ノードは、前記少なくとも１つの中間レベル内の前記ノードが、以前のレベルのノードからのみ入力を受信し、次に続くレベルのノードにのみ出力を供給するように構成され、順次的なブロック内依存性を有することなく前記各レベルにおいて計算を実行できるようにすることを特徴とする装置。
【請求項５】
受信されたビットあるいはシンボルを復号化するための装置であって、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で実装される１組の相互接続される処理ノードを備え、該処理ノードは、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施しており、
復号化されたビットあるいはシンボルからなるワードが前記符号の有効なコードワードであるか否かに関する判定は、指示されたパリティ制約条件が満たされるか否かを判定することにより行われる装置。
【請求項６】
受信されたビットあるいはシンボルを復号化するための装置であって、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で実装される１組の相互接続される処理ノードを備え、該処理ノードは、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施しており、
復号化されたビットあるいはシンボルからなるワードが前記符号の有効なコードワードであるか否かに関する判定は、復号化された前記ワードと前記符号のパリティ検査行列との積がゼロベクトルになるか否かを判定することにより行われる装置。
【請求項７】
受信されたビットあるいはシンボルを復号化するための方法であって、該方法は、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で構成される１組の相互接続される処理ノードに、前記受信されたビットあるいはシンボルを適用するステップと、
前記処理ノード内で、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施するステップとを備え、
前記１組の相互接続される処理ノードは複数の検査ノード及び複数の変数ノードからなり、変数ノードの少なくとも一部分の各々は、復号されたビットまたはシンボルの対応する１つに関連しており、
前記ブロック並列復号プロセスは、
（ｉ）検査ノードの少なくとも一部分の各々において、その検査ノードに接続された変数ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された変数ノードへ送信することと、
（ｉｉ）検査ノードの少なくとも一部分の各々において、その変数ノードに接続された検査ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された検査ノードへ送信することとの内の少なくとも一方を含むことを特徴とする方法。
【請求項８】
受信されたビットあるいはシンボルを復号化するための方法であって、該方法は、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で構成される１組の相互接続される処理ノードに、前記受信されたビットあるいはシンボルを適用するステップと、
前記処理ノード内で、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施するステップとを備え、
前記所与のブロックは、復号化されることになるＮ個のビットあるいはシンボルを含み、前記１組の相互接続される処理ノードはさらに、Ｎ個一組の変数ノードと、Ｔ個一組の検査ノードとを含み、前記Ｎ個の変数ノードのうちの１つは、復号化されることになる前記Ｎ個のビットあるいはシンボルそれぞれと関連しており、
前記ブロック並列復号化プロセスは、Ｒｘｉ（ｉ＝０，１、．．．、Ｎ−１）を前記受信されたビットあるいはシンボルとし、ｆ（.）を前記符号によって少なくとも部分的に決定される関数とするとき、関数ｆ（Ｒｘｉ）を前記変数ノードに接続される前記各検査ノードに送信することによって開始されており、
前記関数ｆ（.）は、閾値関数、線形換算関数および近似指数関数のうちの少なくとも１つを含むことを特徴とする方法。
【請求項９】
受信されたビットあるいはシンボルを復号化するための方法であって、該方法は、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で構成される１組の相互接続される処理ノードに、前記受信されたビットあるいはシンボルを適用するステップと、
前記処理ノード内で、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施するステップとを備え、
前記所与のブロックは、復号化されることになるＮ個のビットあるいはシンボルを含み、前記１組の相互接続される処理ノードはさらに、Ｎ個一組の変数ノードと、Ｔ個一組の検査ノードとを含み、前記Ｎ個の変数ノードのうちの１つは、復号化されることになる前記Ｎ個のビットあるいはシンボルそれぞれと関連しており、
前記ブロック並列復号化プロセスは、全ての前記検査ノードが前記符号の制約条件を満たすときに終了することを特徴とする方法。
【請求項１０】
受信されたビットあるいはシンボルを復号化するための方法であって、該方法は、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で構成される１組の相互接続される処理ノードに、前記受信されたビットあるいはシンボルを適用するステップと、
前記処理ノード内で、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施するステップとを備え、
前記確率依存グラフは、有向確率依存グラフを含み、
前記１組の相互接続された処理ノードはさらに、初期レベル、少なくとも１つの中間レベルおよび最終レベルを有する複数レベルのノードを含み、
前記レベルの前記ノードは、前記少なくとも１つの中間レベル内の前記ノードが、以前のレベルのノードからのみ入力を受信し、次に続くレベルのノードにのみ出力を供給するように構成され、順次的なブロック内依存性を有することなく前記各レベルにおいて計算を実行できるようにすることを特徴とする方法。
【請求項１１】
受信されたビットあるいはシンボルを復号化するための方法であって、該方法は、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で構成される１組の相互接続される処理ノードに、前記受信されたビットあるいはシンボルを適用するステップと、
前記処理ノード内で、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施するステップとを備え、
復号化されたビットあるいはシンボルからなるワードが前記符号の有効なコードワードであるか否かに関する判定は、指示されたパリティ制約条件が満たされるか否かを判定することにより行われることを特徴とする方法。
【請求項１２】
受信されたビットあるいはシンボルを復号化するための方法であって、該方法は、
前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる確率依存グラフの形で構成される１組の相互接続される処理ノードに、前記受信されたビットあるいはシンボルを適用するステップと、
前記処理ノード内で、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実施するステップとを備え、
復号化されたビットあるいはシンボルからなるワードが前記符号の有効なコードワードであるか否かに関する判定は、復号化された前記ワードと前記符号のパリティ検査行列との積がゼロベクトルになるか否かを判定することにより行われることを特徴とする方法。
【請求項１３】
受信されたビットあるいはシンボルを復号化するための装置であって、
確率依存グラフの形に構成される１組のノードを実装するための１つあるいは複数の計算ユニットを備え、該計算ユニットは、前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられ、前記１組のノードは、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックにブロック並列復号化プロセスを提供するように構成されており、
前記１組の相互接続される処理ノードは複数の検査ノード及び複数の変数ノードからなり、変数ノードの少なくとも一部分の各々は、復号されたビットまたはシンボルの対応する１つに関連しており、
前記ブロック並列復号プロセスは、
（ｉ）検査ノードの少なくとも一部分の各々において、その検査ノードに接続された変数ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された変数ノードへ送信することと、
（ｉｉ）検査ノードの少なくとも一部分の各々において、その変数ノードに接続された検査ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された検査ノードへ送信することとの内の少なくとも一方を含むことを特徴とする装置。
【請求項１４】
受信されたビットあるいはシンボルを復号化するための方法であって、該方法は、
確率依存グラフの形で構成される１組のノードを実装し、かつ前記ビットあるいはシンボルを符号化するために用いられる符号によって少なくとも部分的に特徴づけられる１組の１つあるいは複数の計算ユニットに、前記受信されたビットあるいはシンボルを適用するステップと、
前記ノード内に、復号化されることになる前記ビットあるいはシンボルからなる所与のブロックのためのブロック並列復号化プロセスを実装するステップとを備え、
前記１組の相互接続される処理ノードは複数の検査ノード及び複数の変数ノードからなり、変数ノードの少なくとも一部分の各々は、復号されたビットまたはシンボルの対応する１つに関連しており、
前記ブロック並列復号プロセスは、
（ｉ）検査ノードの少なくとも一部分の各々において、その検査ノードに接続された変数ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された変数ノードへ送信することと、
（ｉｉ）検査ノードの少なくとも一部分の各々において、その変数ノードに接続された検査ノードからの入力の関数を計算し、かつ平行して行われる、これらの変数ノード計算の結果を接続された検査ノードへ送信することとの内の少なくとも一方を含むことを特徴とする方法。