(57)【要約】【課題】同時メモリアクセスを利用したメッセージ伝達デコーディング装置及び方法が開示される。【解決手段】それぞれの記憶場所は、複数のプロセスノードを含むデコーダのプロセスノードを連結するエッジのそれぞれに割り当てられる。コーディングされた入力信号はデコーダに適用して、デコーディングされた出力信号を生成する。この際、エッジ値はプロセスノード動作中に記憶場所のうち、複数の記憶場所は、同時にアクセスされるように、記憶場所から反復的に更新され、記憶場所に提供される。プロセスノードは、可変ノードとチェックノードとを含むことができ、エッジは可変ノードとチェックノードとを連結するエッジを含む。本発明は、方法、装置、及びコンピュータプログラム製品として具体化される。【選択図】    図１４
2006340341.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセスノードを含むコーダのプロセスノードを連結するそれぞれのエッジに記憶場所をそれぞれ割り当てる段階と、
コーディングされた入力信号を前記デコーダに適用して、プロセスノード動作中に前記記憶場所のうち、多数の記憶場所が同時にアクセスされるように前記記憶場所からエッジ値を反復的に更新し、前記記憶場所にエッジ値を提供して、デコーディングされた出力信号を生成する段階と、を含むデコーディング方法。
【請求項２】
プロセスノードのエッジ値生成は、前記記憶場所のうち、多数の記憶場所から前記プロセスノードのエッジ値を同時に読み込む段階を含むことを特徴とする請求項１記載のデコーディング方法。
【請求項３】
プロセスノードのエッジ値生成は、前記記憶場所のうち、多数の記憶場所に前記プロセスノードのエッジ値を同時に書き込む段階を含むことを特徴とする請求項１記載のデコーディング方法。
【請求項４】
前記記憶場所からエッジ値を反復的に更新し、前記記憶場所にエッジ値を提供する段階は、
第１複数の保存場所からプロセスノードの複数のエッジ値を同時に読み込む段階と、
前記複数の読み込まれたエッジ値から前記プロセスノードの複数のエッジ値を演算する段階と、
第２複数の保存場所に前記複数の演算されたエッジ値を同時に書き込む段階と、を含むことを特徴とする請求項１記載のデコーディング方法。
【請求項５】
前記プロセスノードは、可変ノードとチェックノードとを含み、
前記エッジは、前記可変ノードと前記チェックノードとを連結するエッジを含むことを特徴とする請求項１記載のデコーディング方法。
【請求項６】
コーディングされた入力信号を前記デコーダに適用する段階は、第１及び第２プロセッサのそれぞれで可変ノード動作とチェックノード動作とを交互に実行する段階を含むことを特徴とする請求項５記載のデコーディング方法。
【請求項７】
コーディングされた入力信号を前記デコーダに適用する段階は、
少なくとも一つのプロセッサが可変ノード動作を実行するように構成する段階と、
前記少なくとも一つのプロセッサを利用して可変ノード出力エッジ値を演算する段階と、
前記少なくとも一つのプロセッサがチェックノード動作を行うように再構成する段階と、
前記少なくとも一つのプロセッサを利用してチェックノード出力エッジ値を演算する段階と、を含むことを特徴とする請求項５記載のデコーディング方法。
【請求項８】
それぞれの記憶場所を前記可変ノードと前記チェックノードとを連結するそれぞれのエッジに割り当てる段階は、
第１複数の記憶場所を可変ノードからチェックノードへのエッジに割り当てて、第２複数の記憶場所をチェックノードから可変ノードへのエッジに割り当てる段階を含み、
コーディングされた信号を前記デコーダに適用する段階は、
第１及び第２プロセッサのそれぞれで可変ノード動作とチェックノード動作とを同時に実行し、生成されたエッジ値を前記第１及び第２複数の記憶場所のそれぞれに保存する段階を含むことを特徴とする請求項５記載のデコーディング方法。
【請求項９】
前記可変ノードと前記チェックノードとは、パリティ検査行列によって機能的に関連させることを特徴とする請求項５記載のデコーディング方法。
【請求項１０】
前記パリティ検査行列は、低密度パリティ検査コードに対応することを特徴とする請求項９記載のデコーディング方法。
【請求項１１】
それぞれの記憶場所をプロセスノードに連結するそれぞれのエッジに割り当てる段階は、
複数の同時接近可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされ、それぞれの同時にアクセス可能な記憶装置を前記エッジのそれぞれのグループに割り当てる段階を含むことを特徴とする請求項１記載のデコーディング方法。
【請求項１２】
前記同時アクセス可能な記憶装置のそれぞれは、それぞれ異なるプロセスノード動作にアクセスする複数の記憶場所を含むことを特徴とする請求項１１記載のデコーディング方法。
【請求項１３】
コーディングされた入力信号を前記デコーダに適用してデコーディングされた出力信号を生成する段階は、通信媒体から信号を受信する段階、及び前記受信した信号のプロセスを行って前記コーディングされた入力信号を生成する段階より後に行うことを特徴とする請求項１記載のデコーディング方法。
【請求項１４】
複数のプロセスノードを含むデコーダを提供するように構成された少なくとも一つのプロセッサと、
前記プロセスノードを連結するエッジのそれぞれに割り当てられた複数の記憶場所を含むメモリと、を含み、
前記プロセッサと前記メモリとは、前記記憶場所のうち、複数の記憶場所がプロセスノード動作に同時にアクセスするように、前記記憶場所からエッジ値の更新と前記記憶場所にエッジ値の提供とを支援するように構成することを特徴とする装置。
【請求項１５】
前記少なくとも一つのプロセッサと前記メモリとは、プロセスノード動作で前記記憶場所のうち、複数の記憶場所からエッジ値を同時に読み込むことを支援するように構成することを特徴とする請求項１４記載の装置。
【請求項１６】
前記少なくとも一つのプロセッサと前記メモリとは、プロセスノード動作で前記記憶場所のうち、複数の記憶場所に複数のエッジ値を同時に書き込むことを支援するように構成することを特徴とする請求項１４記載の装置。
【請求項１７】
前記少なくとも一つのプロセッサと前記メモリとは、第１複数の記憶場所から前記プロセスノードのうち、一つのノードの複数のエッジ値を同時に読み込み、
前記複数の読み込まれたエッジ値から前記プロセスノードのうち、一つのノードの複数のエッジ値を演算し、
第２複数の記憶場所に前記複数の演算したエッジ値を同時に書き込むことを支援するように構成することを特徴とする請求項１４記載の装置。
【請求項１８】
前記プロセスノードは可変ノードとチェックノードとを含み、前記エッジは前記可変ノードと前記チェックノードとを連結するエッジを含むことを特徴とする請求項１４記載の装置。
【請求項１９】
前記少なくとも一つのプロセッサは、それぞれ可変ノード動作とチェックノード動作とを交互に実行するようにそれぞれ構成された第１及び第２プロセッサを含むことを特徴とする請求項１８記載の装置。
【請求項２０】
前記少なくとも一つのプロセッサは、可変ノード動作とチェックノード動作とを交互に実行するように構成するプロセッサを含むことを特徴とする請求項１８記載の装置。
【請求項２１】
前記メモリは、可変ノードからチェックノードへのエッジに割り当てられた第１複数の記憶場所及びチェックノードから可変ノードへのエッジに割り当てられた第２複数の記憶場所を含み
前記プロセッサは、可変ノード動作とチェックノード動作とを同時に実行し、生成されたエッジ値を前記第１及び第２複数の記憶場所にそれぞれ保存するように構成された第１及び第２プロセッサをそれぞれ含むことを特徴とする請求項１８記載の装置。
【請求項２２】
前記メモリは、前記複数の同時アクセス可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされるように、前記エッジのグループにそれぞれ割り当てられた同時アクセス可能な記憶装置をそれぞれ含むことを特徴とする請求項１４記載の装置。
【請求項２３】
前記同時アクセス可能な記憶装置のそれぞれは、複数の記憶場所を含み、
前記少なくとも一つのプロセッサは、それぞれ異なるプロセスノード動作で前記同時アクセス可能な記憶装置の前記複数の記憶場所のうち、他の記憶場所にアクセスするように構成することを特徴とする請求項２２記載の装置。
【請求項２４】
請求項１４の装置を含む通信受信機。
【請求項２５】
前記少なくとも一つのプロセッサは、ユーザが構成することができることを特徴とする請求項１４記載の装置。
【請求項２６】
保存媒体に具体化されたコンピュータプログラムコードを含み、前記コンピュータプログラムコードは、複数のプロセスノードを含むデコーダを定義し、前記プロセスノードを連結するそれぞれのエッジのそれぞれの保存場所を割り当てて、コーディングされた入力信号を前記デコーダに適用して、プロセスノード動作中に前記記憶場所のうち、複数の記憶場所が同時にアクセスされるように前記プロセスノードの動作で前記記憶場所からエッジ値を反復的に更新し、前記記憶場所にエッジ値を提供して、デコーディングされた出力信号を生成するように構成することを特徴とするコンピュータプログラム製品。
【請求項２７】
前記プログラムコードは、前記記憶場所のうち、複数の記憶場所からプロセスノードのエッジ値を同時に読み込み及び／又は書き込み動作を実行するように構成することを特徴とする請求項２６記載のコンピュータプログラム製品。
【請求項２８】
前記プロセスノードは、可変ノードとチェックノードとを含み、前記エッジは前記可変ノードと前記チェックノードとを連結するエッジを含むことを特徴とする請求項２６記載のコンピュータプログラム製品。
【請求項２９】
前記プログラムコードは、第１及び第２プロセッサのそれぞれが可変ノード動作とチェックノード動作とを交互に実行するように構成することを特徴とする請求項２８記載のコンピュータプログラム製品。
【請求項３０】
前記プログラムコードは、少なくとも一つのプロセッサが可変ノード動作を実行し、前記少なくとも一つのプロセッサを利用して可変ノード出力エッジ値を演算し、前記少なくとも一つのプロセッサがチェックノード動作を実行するように再構成し、前記少なくとも一つのプロセッサを利用してチェックノード出力エッジ値を演算するように構成することを特徴とする請求項２８記載のコンピュータプログラム製品。
【請求項３１】
前記プログラムコードは、第１複数の記憶場所を可変ノードからチェックノードへのエッジに割り当てて、第２複数の記憶場所をチェックノードから可変ノードへのエッジに割り当てて、第１及び第２プロセッサのそれぞれで可変ノード動作とチェックノード動作とを同時に実行して、生成されたエッジ値を前記第１及び第２複数の記憶場所にそれぞれ保存するように構成することを特徴とする請求項２８記載のコンピュータプログラム製品。
【請求項３２】
前記プログラムコードは、前記複数の同時にアクセス可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされ、それぞれの同時にアクセス可能な記憶装置を前記エッジのグループにそれぞれ割り当てるように構成することを特徴とする請求項２６記載のコンピュータプログラム製品。
【請求項３３】
前記同時にアクセス可能な記憶装置のそれぞれは、それぞれ異なるプロセスノード動作でアクセスする複数の記憶場所を含むことを特徴とする請求項３２記載のコンピュータプログラム製品。
【請求項３４】
デコーダのプロセスノードを連結するそれぞれのエッジに割り当てられ、前記記憶場所のうち、複数の記憶場所がプロセスノード動作と同時にアクセスできるように、前記記憶場所からエッジ値の更新と前記記憶場所にエッジ値の提供を支援するように構成された複数の記憶場所を含むメモリ。
【請求項３５】
複数の同時にアクセス可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされ、前記エッジのグループのそれぞれに割り当てられた同時アクセス可能な記憶装置をそれぞれ含むことを特徴とする請求項３４記載のメモリ。
【請求項３６】
前記同時にアクセス可能な記憶装置は、プロセッサがそれぞれ異なるプロセスノード動作と同時にアクセス可能な記憶装置で、前記複数の記憶場所のうち、他の場所にアクセスすることができるように配列された複数の記憶場所をそれぞれ含むことを特徴とする請求項３５記載のメモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデコーディング技術に係り、より詳細には、メッセージ伝達技術を利用するデコーディング装置及び方法に関する。
【背景技術】
【０００２】
従来の通信システムは、データ伝送エラーを減少させるために、主にチャンネルコーディングを利用している。主に使用されたチャンネルコードには、畳み込み符号（ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅ）とブロックコードとがある。畳み込み符号には、テイルバイティングコード（ｔａｉｌ−ｂｉｔｉｎｇ  ｃｏｄｅ）、ゼロテイリングコード（ｚｅｒｏ−ｔａｉｌｉｎｇ  ｃｏｄｅ）、及び畳み込みターボ符号等が知られている。ブロックコードには、リードソロモンコード、ＢＣＨ（Ｂｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅ  ｎｇｈｅｍ）コード、ブロックターボコード、及びＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）コード等が知られている。
【０００３】
最近に、ＬＤＰＣコーディングは、デジタルテレビ（ＤＴＶ、ｄｉｇｉｔａｌ  ｔｅｌｅｖｉｓｉｏｎ）伝送に使用されている。ＬＤＰＣコードは、「エッジ」によって連結された「可変」（又は、「メッセージ」）ノードと「チェック」ノードとを含む希少二分グラフから得られる線形的なコードである。このようなグラフ表現は、行列の形態として表現することができる。詳細には、ｎ個の可変ノードとｒ個のチェックノードとを有するグラフの場合に、二進ｒ×ｎ行列は、ｉ番目チェックノードがｊ番目可変ノードに連結された場合にのみ、特定な元素（ｉ、ｊ）が「１」である行列として定義することができる。このような行列を、パリティチェック行列と言う。ＬＤＰＣコードは、希少パリティチェック行列であることを特徴とする。
【０００４】
従来のＬＤＰＣデコーディング技術は、反復される「メッセージ伝達」アルゴリズムを典型的に利用している。このようなアルゴリズムは、一般的に一連の循環を含むが、循環における値は、可変ノードからチェックノードに、更にチェックノードから可変ノードに伝達される。可変ノードから伝達される値は、典型的に可変ノードの現在値と隣接したチェックノードから受けた値に基づいて演算される。
【０００５】
信頼伝達アルゴリズムと呼ばれるメッセージ伝達アルゴリズムのサブクラスがＬＤＰＣデコーディングを通常的に使用する。このようなアルゴリズムにおいて、ノードの間で伝達されるメッセージは確率を示す。特に、可変ノードｊからチェックノードｉに伝達されるメッセージは、可変ノードｊが可変ノードｊの観測値と以前循環でチェックノードｉではない可変ノードｊに連結されたチェックノードから可変ノードｊに伝達される値から与えられる特定な値を有する確率を示す。チェックノードｉから可変ノードｊに伝達されるメッセージは、可変ノードｊが以前循環で可変ノードｊを除いた他の可変ノードからチェックノードｉに伝達されるメッセージから与えられる特定な値を有する確率を示す。
【０００６】
特許文献１は、確率依存グラフ（例えば、可変ノードとチェックノードとを含む二分確率依存グラフ）の形態に構成され、相互連結されたプロセスノードのセットを利用するブロック並列デコーディングアルゴリズムを開示している。デコーディング過程を一回反復すると、可変ノード内で与えられたブロック内の全てのビットやシンボルの更新推定を算出することができる。可変ノードに連結されたそれぞれのチェックノードの関数ｆ（Ｒｘｉ）を送ると、デコーディング過程が始まる。Ｒｘｉは、受信したビットやシンボルを示し、ｆ（  ）は境界関数、線形スケーリング関数、又は近似指数関数のように、コード別に少なくとも一部分決定される関数を示す。デコーディング過程は、それぞれのチェックノードでチェックノードに連結された可変ノードからの入力に対して、関数ｇ（  ）（例えば、パリティチェック関数）を並列に計算する段階と、チェックノード演算の結果を連結された可変ノードに伝達する段階を含む。又、デコーディング過程は、それぞれの可変ノードで可変ノードに連結されたチェックノードからの入力に対して、関数ｈ（  ）（例えば、多数決関数又は平均関数）を並列に演算する段階と、可変ノード演算の結果を連結されたチェックノードに伝達する段階を更に含む。このような過程は、全てのチェックノードがコードの終了条件、例えば、最大反復回数を超えた時に終了することができる。終了時、可変ノードの値は、伝送されたビットやシンボルの推定を示す。相互連結されたプロセスノードの集合は、一つ以上のプログラム可能な演算単位を利用して実現することができ、それぞれのプログラム可能な演算単位は、一つのノード又は多数個のノードを実現するように構成することができる。
【特許文献１】米国特許６，５３９，３６７号
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、前述のような事情に鑑みてなされたもので、最適化されたメモリ動作を有するデコーダとデコーディング方法を提供することを目的とする。
【０００８】
また本発明は、デコーダのためのコンピュータプログラムコードを含むコンピュータプログラム製品を提供することも目的とする。
【０００９】
更に本発明は、デコーダのための最適化されたメモリ動作を有するメモリを提供することも目的とする。
【００１０】
以上の目的は、例示的なもので、本発明の目的は以上の目的に限定されない。
【課題を解決するための手段】
【００１１】
本発明の実施例によるデコーディング方法は、複数のプロセスノードを含むデコーダのプロセスノードを連結するそれぞれのエッジに記憶場所をそれぞれ割り当てる段階、及びコーディングされた入力信号をデコーダに適用して、プロセスノード動作中に記憶場所のうち、多数の記憶場所が同時にアクセスされるように記憶場所からエッジ値を反復的に更新し、記憶場所にエッジ値を提供して、デコーディングされた出力信号を生成する段階を含む。
【００１２】
プロセスノードのエッジ値生成は、記憶場所のうち、多数の記憶場所からプロセスノードのエッジ値を同時に読み込む段階を含むことができる。プロセスノードのエッジ値生成は、記憶場所のうち、多数の記憶場所にプロセスノードのエッジ値を同時に書き込む段階を含むことができる。
【００１３】
記憶場所からエッジ値を反復的に更新し、記憶場所にエッジ値を提供する段階は、第１複数の保存場所からプロセスノードの複数のエッジ値を同時に読み込む段階、複数の読み込まれたエッジ値からプロセスノードの複数のエッジ値を演算する段階、及び第２複数の保存場所に複数の演算されたエッジ値を同時に書き込む段階を含むことができる。
【００１４】
プロセスノードは、可変ノードとチェックノードとを含み、エッジは、可変ノードとチェックノードとを連結するエッジを含むことができる。
【００１５】
コーディングされた入力信号をデコーダに適用する段階は、第１及び第２プロセッサのそれぞれで可変ノード動作とチェックノード動作とを交互に実行する段階を含むことができる。コーディングされた入力信号をデコーダに適用する段階は、少なくとも一つのプロセッサが可変ノード動作を実行するように構成する段階、少なくとも一つのプロセッサを利用して可変ノード出力エッジ値を演算する段階、少なくとも一つのプロセッサがチェックノード動作を行うように再構成する段階、及び少なくとも一つのプロセッサを利用してチェックノード出力エッジ値を演算する段階を含むことができる。
【００１６】
それぞれの記憶場所を可変ノードとチェックノードとを連結するそれぞれのエッジに割り当てる段階は、第１複数の記憶場所を可変ノードからチェックノードへのエッジに割り当てて、第２複数の記憶場所をチェックノードから可変ノードへのエッジに割り当てる段階を含み、コーディングされた信号をデコーダに適用する段階は、第１及び第２プロセッサのそれぞれで可変ノード動作とチェックノード動作とを同時に実行し、生成されたエッジ値を第１及び第２複数の記憶場所のそれぞれに保存する段階を含むことができる。
【００１７】
可変ノードとチェックノードとは、パリティ検査行列によって機能的に関連させることができる。パリティ検査行列は、低密度パリティ検査コードに対応することができる。
【００１８】
それぞれの記憶場所をプロセスノードに連結するそれぞれのエッジに割り当てる段階は、複数の同時接近可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされ、それぞれの同時にアクセス可能な記憶装置をエッジのそれぞれのグループに割り当てる段階を含むことができる。同時アクセス可能な記憶装置のそれぞれは、それぞれ異なるプロセスノード動作にアクセスする複数の記憶場所を含むことができる。
【００１９】
コーディングされた入力信号をデコーダに適用してデコーディングされた出力信号を生成する段階は、通信媒体から信号を受信する段階、及び受信した信号のプロセスを行ってコーディングされた入力信号を生成する段階より後に行うことができる。
【００２０】
本発明の実施例による装置は、複数のプロセスノードを含むデコーダを提供するように構成された少なくとも一つのプロセッサとプロセスノードとを連結するエッジのそれぞれに割り当てられた複数の記憶場所を含むメモリとを含み、プロセッサとメモリとは、記憶場所のうち、複数の記憶場所がプロセスノード動作と同時にアクセスするように、記憶場所からエッジ値の更新と記憶場所にエッジ値の提供とを支援するように構成する。
【００２１】
少なくとも一つのプロセッサとメモリとは、プロセスノード動作で記憶場所のうち、複数の記憶場所からエッジ値を同時に読み込むことを支援するように構成することができる。少なくとも一つのプロセッサとメモリとは、プロセスノード動作で記憶場所のうち、複数の記憶場所に複数のエッジ値を同時に書き込むことを支援するように構成することができる。少なくとも一つのプロセッサとメモリとは、第１複数の記憶場所からプロセスノードのうち、一つのノードの複数のエッジ値を同時に読み込み、複数の読み込まれたエッジ値からプロセスノードのうち、一つのノードの複数のエッジ値を演算し、第２複数の記憶場所に複数の演算したエッジ値を同時に書き込むことを支援するように構成することができる。
【００２２】
プロセスノードは可変ノードとチェックノードとを含み、エッジは可変ノードとチェックノードとを連結するエッジを含むことができる。
【００２３】
少なくとも一つのプロセッサは、それぞれ可変ノード動作とチェックノード動作とを交互に実行するようにそれぞれ構成された第１及び第２プロセッサを含むことができる。少なくとも一つのプロセッサは、可変ノード動作とチェックノード動作とを交互に実行するように構成するプロセッサを含むことができる。
【００２４】
メモリは、可変ノードからチェックノードへのエッジに割り当てられた第１複数の記憶場所及びチェックノードから可変ノードへのエッジに割り当てられた第２複数の記憶場所を含み、プロセッサは、可変ノード動作とチェックノード動作とを同時に実行し、生成されたエッジ値を第１及び第２複数の記憶場所にそれぞれ保存するように構成された第１及び第２プロセッサをそれぞれ含むことができる。メモリは、複数の同時アクセス可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされるように、エッジのグループにそれぞれ割り当てられた同時アクセス可能な記憶装置をそれぞれ含むことができる。
【００２５】
同時アクセス可能な記憶装置のそれぞれは、複数の記憶場所を含み、少なくとも一つのプロセッサは、それぞれ異なるプロセスノード動作で同時アクセス可能な記憶装置の複数の記憶場所のうち、他の記憶場所にアクセスするように構成することができる。前記装置を含む通信受信機を提供することができる。少なくとも一つのプロセッサは、ユーザが構成することができることを特徴とする。
【００２６】
本発明の実施例によるコンピュータプログラム製品は、保存媒体に具体化されたコンピュータプログラムコードを含み、コンピュータプログラムコードは、複数のプロセスノードを含むデコーダを定義し、プロセスノードを連結するそれぞれのエッジのそれぞれの保存場所を割り当てて、コーディングされた入力信号をデコーダに適用して、プロセスノード動作中に記憶場所のうち、複数の記憶場所が同時にアクセスされるようにプロセスノードの動作で記憶場所からエッジ値を反復的に更新し、記憶場所にエッジ値を提供して、デコーディングされた出力信号を生成するように構成する。
【００２７】
プログラムコードは、記憶場所のうち、複数の記憶場所からプロセスノードのエッジ値を同時に読み込み及び／又は書き込み動作を実行するように構成することができる。
【００２８】
プロセスノードは、可変ノードとチェックノードとを含み、エッジは可変ノードとチェックノードとを連結するエッジを含むことができる。
【００２９】
プログラムコードは、第１及び第２プロセッサのそれぞれが可変ノード動作とチェックノード動作とを交互に実行するように構成することができる。プログラムコードは、少なくとも一つのプロセッサが可変ノード動作を実行し、少なくとも一つのプロセッサを利用して可変ノード出力エッジ値を演算し、少なくとも一つのプロセッサがチェックノード動作を実行するように再構成し、少なくとも一つのプロセッサを利用してチェックノード出力エッジ値を演算するように構成することができる。プログラムコードは、第１複数の記憶場所を可変ノードからチェックノードへのエッジに割り当てて、第２複数の記憶場所をチェックノードから可変ノードへのエッジに割り当てて、第１及び第２プロセッサのそれぞれで可変ノード動作とチェックノード動作とを同時に実行して、生成されたエッジ値を第１及び第２複数の記憶場所にそれぞれ保存するように構成することができる。プログラムコードは、複数の同時にアクセス可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされ、それぞれの同時にアクセス可能な記憶装置をエッジのグループにそれぞれ割り当てるように構成することができる。同時にアクセス可能な記憶装置のそれぞれは、それぞれ異なるプロセスノード動作でアクセスする複数の記憶場所を含むことができる。
【００３０】
本発明の実施例によるメモリは、デコーダのプロセスノードを連結するそれぞれのエッジに割り当てられ、記憶場所のうち、複数の記憶場所がプロセスノード動作で同時にアクセスできるように、記憶場所からエッジ値の更新と記憶場所にエッジ値の提供を支援するように構成された複数の記憶場所を含む。
【００３１】
メモリは、複数の同時にアクセス可能な記憶装置に同時にアクセスすることにより、特定プロセスノードのエッジ値が同時にアクセスされ、エッジのグループのそれぞれに割り当てられた同時アクセス可能な記憶装置をそれぞれ含むことができる。
【００３２】
同時にアクセス可能な記憶装置は、プロセッサがそれぞれ異なるプロセスノード動作で同時にアクセス可能な記憶装置で、複数の記憶場所のうち、他の場所にアクセスすることができるように配列された複数の記憶場所をそれぞれ含むことができる。
【００３３】
本文に開示されている本発明の実施例に対し、特定な構造的乃至機能的説明は、単に本発明の実施例を説明するための目的として例示されたもので、本発明の実施例は、多様な形態で実施することができ、本文に説明された実施例に限定されるものではない。
【００３４】
本発明は、多様に変更することができ、多様な形態を有することができ、特定実施例を図面に例示して、本文に詳細に説明する。しかし、これは、本発明を特定な開示形態に限定しようとするものではなく、本発明の思想及び技術範囲に含まれる全ての変更、均等物乃至代替物を含むと理解されるべきである。各図面を説明しながら、同一参照符号を構成要素に付与した。
【００３５】
第１、第２等の用語は、多様な構成要素を説明するのに使用することができるが、構成要素は、前記用語によって限定されてはならない。用語は、一つの構成要素を他の構成要素から区別する目的でのみ使用する。例えば、本発明の権利範囲から離脱しない範囲で、第１構成要素は第２構成要素と称することができ、同様に第２構成要素も第１構成要素と称することができる。
【００３６】
いかなる構成要素が他の構成要素に「連結されて」いるか、「接続されて」いると言及される時には、その他の構成要素に直接的に連結されているか、又は、接続されていることもできるが、中間に他の構成要素が存在することもできる。一方、いかなる構成要素が他の構成要素に「直接連結されて」いるか、「直接接続されて」いると言及される時には、中間に他の構成要素が存在しない。構成要素間の関係を説明する他の表現、即ち、「〜間に」と「すぐ〜間に」、又は「〜に隣接する」と「〜に直接隣接する」等も同様に解釈する。
【００３７】
本出願で使用した用語は、単に特定な実施例を説明するために使用したもので、本発明を限定しようとする意図ではない。単数の表現は、文脈上明確に異なるように定義しない限り、複数の表現を含む。本出願において、「含む」又は「有する」等の用語は、記載された特徴、数字、段階、動作、構成要素、部分、又はこれらを組合せたことが存在することを指定するもので、一つ以上の他の特徴や数字、段階、動作、構成要素、部分、又はこれらを組合したものの存在又は付加可能性を予め排除しないと理解しなければならない。
【００３８】
異なるように定義しない限り、技術的、科学的用語を含んで、ここで使用する全ての用語は、本発明の属する技術分野で通常の知識を有するものによって一般的に理解されることと同じ意味を有している。一般的に使用する辞典に定義されている用語は、関連技術の文脈上有する意味と一致する意味を有すると解釈されなければならず、本出願で明確に定義しない限り、理想的であるか、過度に形式的な意味には解釈されない。
【００３９】
本発明の実施例は、以下で本発明の実施例による方法、装置（システム）、及びコンピュータプログラム製品を支援するブロック図と流れ図を参照して説明する。流れ図及び／又はブロック図のそれぞれのブロック、及び流れ図、及び／又はブロック図でブロックの組合は、コンピュータプログラム命令によって実現することができる。このようなコンピュータプログラム命令は、一般的な目的のコンピュータ、特別な目的のコンピュータのプロセッサ、又は他のプログラム可能なデータプロセス装置に提供することができる。それによって、コンピュータプロセス又は他のプログラム可能なデータプロセス装置を介して実行する命令が流れ図及び／又はブロック図で具体化される機能／動作を実現するための手段を生成する。
【００４０】
このようなコンピュータプログラム命令は、コンピュータ又は他のプログラム可能なデータプロセス装置が特性な方式で動作するように命令することができる判読可能なメモリに保存することができる。これによって、コンピュータ−読み込み可能なメモリに保存された命令は、流れ図及び／又はブロック図に具体化された機能／動作を実現する命令手段を含む製品を生産することができる。
【００４１】
コンピュータプログラム命令は、コンピュータ又は他のプログラム可能なデータプロセス装置にローディングされ、一連の演算段階がコンピュータ又は他のプログラム可能な装置で実行されるようにして、プロセスが実現されたコンピュータを生産することができる。それによって、コンピュータ又は他のプログラム可能な装置で実行される命令は、流れ図及び／又はブロック図で具体化された機能／動作を実現するための段階を提供することができる。それぞれのブロックは、具体化された論理機能を実現するための一つ以上の実行可能な命令を含むモジュール、セグメント、又はコード部を示す。他の実施例では、ブロックに図示された機能は、図面に図示された順序と異なる順次で行うことができる。例えば、連続する２つのブロックは、事実上、実質的に同時に実行することができ、ブロックは相関関係によって逆順序に実行することもできる。
【００４２】
本発明の多様な実施例によると、受信された信号から生成されるコーディングされたデータ記号、例えば、ビットの流れのようなコーディングされたデータがプロセスノード間で伝達されるプロセスノードとエッジ値（メッセージ）とを含むメッセージ伝達演算構造を利用してデコーディングされる方法、装置、及びコンピュータプログラム製品を提供することができる。実施例は、「可変」ノードと「チェック」ノードとを含む二分構造を有するメッセージ伝達構造として説明されるＬＤＰＣコードのようなコードによるデコーディングに適用して説明することができる。しかし、本発明は、他の構造を有するコードのデコーディング動作にも適用することができると理解することができる。
【００４３】
本発明の実施例において、プロセスノード動作の複数のエッジのメモリアクセス、例えば、可変ノード、又はチェックノードの出力エッジ値の演算を含む動作は、「同時に」行われる。ここで、「同時」メモリアクセスは、少なくとも部分的に重複されるか、同時に発生する読み込み、書き込み、又は、他のメモリアクセス動作を示す。それによって、同時アクセスの少なくとも一部分は並列に発生する。
【発明を実施するための最良の形態】
【００４４】
以下、添付図面を参照して、本発明の好ましい実施例をより詳細に説明する。図面上の同一構成要素には、同一参照符号を付与して、同一構成要素についての重複説明は省略する。
【００４５】
図１乃至図３は、多様な種類のコードを二分グラフで表現した例を示す。
【００４６】
図１乃至図３は、本発明の実施例による二分デコーディング構造を利用してデコーディングすることができるコードの例の二分グラフを示す。図１は、可変ノードＶ１、Ｖ２、．．．、Ｖ８とチェックノードＣ１、Ｃ２、．．．、Ｃ４を有する規則（ｒｅｇｕｌａｒ）コード方式の二分グラフを示す。グラフは、対応するパリティ検査行列によって表示することができる。
【００４７】
【数１】
2006340341.tif 000003
【００４８】
列は、可変ノードＶ１、Ｖ２、．．．、Ｖ８に対応して、行は、チェックノードＣ１、Ｃ２、．．．、Ｃ４に対応する。図２は、不規則コード方式の二分グラフを示し、グラフはパリティチェック行列によって表示することができる。
【００４９】
【数２】
2006340341.tif 000004
【００５０】
最後に、図３はパリティチェック行列を有するブロックＬＤＰＣの二分グラフを示す。
【００５１】
【数３】
2006340341.tif 000005
【００５２】
【数４】
2006340341.tif 000006
【００５３】
【数５】
2006340341.tif 000007
【００５４】
Ｈの列は、可変ノードＶ１１、Ｖ１２、．．．、Ｖ８２、Ｖ８３のグループを示し、Ｈの行は、チェックノードＣ１１、Ｃ１２、．．．、Ｃ４２、Ｃ４３のグループを示す。
【００５５】
図４は、図１の構造に対する可変ノード演算の例を示す。詳細には、チャンネルコーティングされた値ＬＬＲ−Ｙ（例えば、ログ型値）とチェックノードからの入力エッジ値Ｃ２Ｖ１、Ｃ２Ｖ２、Ｃ２Ｖ３、及びＣ２Ｖ４とが合算される。生成された和は、入力エッジ値Ｃ２Ｖ１、Ｃ２Ｖ２、Ｃ２Ｖ３、及びＣ２Ｖ４と選択的に結合され、チェックノードに出力エッジ値Ｖ２Ｃ１、Ｖ２Ｃ２、Ｖ２Ｃ３、及びＶ２Ｃ４を提供する。
【００５６】
図５及び図６は、それぞれチェックノードのサイズと符号の演算の例を示す。可変ノードからの入力エッジ値Ｖ２Ｃ１、Ｖ２Ｃ２、．．．、Ｖ２Ｃ８は、関数Φ（  ）によってプロセスが行われ、合算された値を生成する。生成された和は、入力エッジ値Ｖ２Ｃ１、Ｖ２Ｃ２、．．．、Ｖ２Ｃ８から生成された値のうち、複数の値と選択的に結合され、逆関数Φ−１（  ）によってプロセスが行われ、可変ノードに伝達される出力エッジ値Ｃ２Ｖ１、Ｃ２Ｖ２、．．．、Ｃ２Ｖ８のサイズを決定する。図６を参照すると、可変ノードからの入力エッジ値Ｖ２Ｃ１、Ｖ２Ｃ２、．．．、Ｖ２Ｃ８は合算され、合算された値は入力エッジ値Ｖ２Ｃ１、Ｖ２Ｃ２、．．．、Ｖ２Ｃ８のうち、複数の値と選択的に結合され、可変ノードに伝達される出力エッジ値Ｃ２Ｖ１、Ｃ２Ｖ２、．．．、Ｃ２Ｖ８の符号を決定する。
【００５７】
本発明の実施例によると、図４乃至図６で示す線に沿った可変ノードとチェックノード演算を含む動作のようなノードプロセス動作ではノードプロセス動作のエッジ値（例えば、図５に表示されたエッジ値Ｖ２Ｃ１、Ｖ２Ｃ２、．．．、Ｖ２Ｃ８）に割り当てられた複数の記憶場所に同時にアクセス（読み込み及び／又は書き込み）することにより、効率性が向上される。例えば、本発明の特定な実施例において、複数の記憶場所に同時にアクセスするように構成されたメモリを利用することにより、効率性が向上されることができる。そのようなメモリは、エッジグループのそれぞれに割り当てられたそれぞれの同時にアクセス可能な記憶装置を含むことができる。それによって、複数の独立的にアドレス可能な記憶装置に同時にアクセスして特定プロセスノードのエッジ値は、同時にアクセスすることができる。本発明は、次善の解決策、例えば、メモリアクセスで最大限の同時性に及ぼさない解決策はもちろん、最善の解決策、例えば、メモリアクセスで最大限の同時性（又は、平行関係）が行われるようにする解決策を含む。
【００５８】
図７及び図８は、本発明の実施例によるデコーディング動作の例を示す。複数の可変ノードの入力エッジ値は初期化され（Ｓ７０５）、コーディングされた値は、例えば、復調器から入力される（Ｓ７１０）。可変ノードプロセス循環に進入すると、一つ又はそれ以上の可変ノードの複数の入力エッジ値は、メモリから同時に更新され（Ｓ７１５）、出力エッジ値、即ち、チェックノードに伝達されるエッジ値を演算するのに使用される（Ｓ７２０）。このような演算は、図４に示す線に沿って行うことができるが、多様な演算を使用することができる。生成された複数の出力エッジ値のうち、少なくとも一部は同時に保存される（Ｓ７２５）。仮に、残っている可変ノードがプロセスされるように残っていると、このようなノードは前述したように追加的な出力エッジ値を生成して保存するプロセスが行われる（Ｓ７３０及びＳ７１５−Ｓ７２５）。
【００５９】
一応、全ての可変ノードのプロセスが行われると、類似な反復的ループがチェックノードで実行される。詳細には、一つ以上のチェックノードの入力エッジ値、即ち、以前可変ノードプロセス（Ｓ７１５−Ｓ７２５）で生成された出力エッジ値は同時に読み込まれ（Ｓ７３５）、次の可変ノードプロセスに使用することができる出力エッジ値を演算するのに使用される（Ｓ７４０）。このような演算は、図５及び図６のような線に沿って行うことができ、他の多様な演算を含むこともできる。出力エッジ値のうち、少なくとも一部は同時に保存される（Ｓ７４５）。仮に、更に他のチェックノードがプロセスされるように残っていると、このノードは前述したようにプロセスが行われる（Ｓ７５０及びＳ７３５−Ｓ７４５）。
【００６０】
終了条件、例えば、演算されたチェックノード出力値に基づいた条件が満たされると、チェックノードプロセスの循環が終了し、デコーディングされたビットが出力される（Ｓ７６０）。しかし、仮に、終了条件が満たされないと、可変ノードプロセスから始まる更に他のノードプロセスの循環が初期化される（Ｓ７１５−Ｓ７２５）。
【００６１】
図９は、図７及び図８に表示された線に沿った動作を実行することができる装置を示す。デコーダ８２０は、一つ以上の可変ノードプロセッサ８２４、一つ以上のチェックノードプロセッサ８２６、決定部８２８、及びマルチ−アクセスメモリ８２２を含む。詳細には、メモリ８２２は、エッジ値に割り当てられた複数の保存場所に同時にアクセス（即ち、多重同時読み込み及び／又は書き込み）するように構成する。一つ以上の可変ノードプロセッサ８２４は、例えば、図７のＳ７１５乃至Ｓ７３０に示すように、バッファ８１０からコーディングされた値を受信し、メモリ８２２から可変ノードプロセスが行われる一つ以上のノードに入力エッジ値を同時に更新し演算して、メモリ８２２にエッジ値を同時に出力するように構成する。これと同様に、図８のＳ７３５乃至Ｓ７４５に示すように、一つ以上のチェックノードプロセッサ８２６は、一つ以上のチェックノードのエッジ値を同時に入力し、演算して、メモリ８２２にエッジ値を同時に出力するように構成する。決定部８２８は、可変ノードプロセッサ８２４及びチェックノードプロセッサ８２６の反復動作の終了条件を判断し、可変ノードプロセッサ８２４とチェックノードプロセッサ８２６とをそれぞれ制御して、生成したデコーディングされたビットを出力するように構成することができる。
【００６２】
図１０は、本発明の実施例による他のデコーディング装置の構成を示す。デコーダ９２０は、バッファ９１０から更新されたコーディングされた値をデコーディングする複数のノードプロセッサ９２４ａ、９２４ｂ、．．．、９２４ｎを含む。デコーダ９２０は、ノードプロセッサ９２４ａ、９２４ｂ、．．．、９２４ｎのノードプロセス動作のエッジ値を保存する複数の記憶場所に同時にアクセスすることができるように構成されたメモリ９２２を更に含む。ノードプロセッサ９２４ａ、９２４ｂ、．．．、９２４ｎは、可変及び／又はチェックノードプロセス動作を提供するように構成することができる。例えば、それぞれのプロセスノードグループは、それぞれのグループ又は可変及び／又はチェックノードに配置することができる。このような配置は、固定されるか、利用者が構成することができる。例えば、使用される特定コードに依存してノードプロセッサ９２４ａ、９２４ｂ、．．．、９２４ｎは異なるように配置することができる。デコーダ９２０は、メモリ９２２に対応してノードプロセッサ９２４ａ、９２４ｂ、．．．、９２４ｎを制御する決定部９２６を更に含む。
【００６３】
図１０に示す構成は、図７及び図８に表示された線に沿った演算を実現するのに使用することができる。例えば、ノードプロセッサ９２４ａ、９２４ｂ、．．．、９２４の各グループは、可変ノードとチェックノードとに割り当てることができ、図７及び図８に示すように交互に動作することもできる。ノードプロセッサ９２４ａ、９２４ｂ、．．．、９２４ｎは、可変ノード演算及びチェックノード演算を行うのに交互に使用することができる。例えば、与えられたプロセス循環でプロセッサ９２４ａ、９２４ｂ、．．．、９２４ｎは、まず可変ノードプロセッサで構成することができ、その後に可変ノードプロセスの遂行が完了すると、チェックノードプロセスを行うように再構成することができる。
【００６４】
図１１は、本発明の実施例による図１０の線に沿った構造を利用して行うことができるデコーディング動作の例を示す。エッジ値は初期化され（Ｓ１００５）、コーディングされた値が入力される（Ｓ１０１０）。反復ループが始まると、複数のプロセスノードの入力エッジ値が読み込まれ（Ｓ１０１５）、入力エッジ値は同時に保存される（Ｓ１０２５）出力エッジ値が演算されるのに利用される（Ｓ１０２０）。詳細には、複数のノードは複数の可変ノード、チェックノード、又はその組合せを含むことができる。可変ノードとチェックノードとがプロセスされる順序は、ノード間の関係に依存させることができる。即ち、エッジ値が演算される順序は、エッジ値が次ぎ演算に使用されることができる時期に依存することができる。特定の循環のノードプロセスが終了すると（Ｓ１０３０）、デコーダは、終了条件が満足するか否かを判断する（Ｓ１０３５）。終了条件を満足すると、デコーダは、デコーディングされたビットを出力し（Ｓ１０４０）、終了条件を満足しないと、デコーダは、ノードプロセス動作の新しい循環を始める（Ｓ１０１５以下）。
【００６５】
図１２は、本発明の実施例によるデコーダの他の構成を示す。デコーダ１１２０は、バッファ１１１０からコーディングされた値を受信する。デコーダ１１２０は、可変ノード入力／チェックノード出力エッジ値を保存するように構成される第１メモリ１１２２ａと可変ノード出力／チェックノード入力エッジ値を保存するように構成される第２メモリ１１２２ｂとを含む。ノードプロセッサ１１２４ａ、１１２４ｂ、．．．、１１２４ｎは、メモリ１１２２ａ、１１２２ｂの内部の複数のエッジ値の保存場所に同時にアクセスすることができるように構成される。デコーダ１１２０は、メモリ１１２２ａ、１１２２ｂに対応してノードプロセッサ１１２４ａ、１１２４ｂ、．．．、１１２４ｎを制御する決定部１１２６を更に含む。このような構成は、ノードプロセスに追加的な並列演算を提供することができる。
【００６６】
図１３は、図１２に示すような演算構造を利用して行うことができるノードプロセス動作の例を示す。まず、エッジ値を初期化し（Ｓ１２０５）、コーディングされた値の入力を受ける（Ｓ１２１０）。２つの反復ノードプロセスが並列に行われる。第１ループでは、第１メモリから第１ノードグループの入力エッジ値が同時に読み込まれ（Ｓ１２１５）、入力エッジ値は、出力エッジ値を演算するのに使用される（Ｓ１２２０）。出力エッジ値のうち、少なくとも一部は、第２メモリに同時に書き込まれる（Ｓ１２２５）。動作は、第１ノードグループで全てのノードプロセスが行われるまで反復される（Ｓ１２３０、Ｓ１２１５−Ｓ１２２５）。第２ループでは、第２ノードグループの入力エッジ値は、第１メモリから同時に読み込まれ（Ｓ１２３５）、入力エッジ値は、出力エッジ値を演算するのに使用される（Ｓ１２４０）。出力エッジ値は、第１メモリに同時に書き込まれる（Ｓ１２４５）。動作は、第２ノードグループで全てのノードプロセスが行われるまで反復される（Ｓ１２５０、Ｓ１２３５−Ｓ１２４５）。ループが実行される間に、一つのループに演算されるエッジ値は、並列で実行される他のループで入力エッジ値として使用することができる。終了条件が満足されると（Ｓ１２５５）、ループは終了され、デコーディングされたビットが出力される（Ｓ１２６０）。
【００６７】
メモリへの同時接近性は、多様な方法で提供することができる。例えば、メモリは同時にアクセスすることができ、独立的に制御することもできる（例えば、独立的にアドレス可能な）記憶装置を含むことができる。
【００６８】
図１４乃至図１７は、本発明の多様な実施例で使用することができるメモリ配置構造の例を示す。詳細には、図１４は、図１に図示されたコードのデコーディング動作を行うように構成したメモリ１３００を示す。図１４を参照すると、メモリ１３００は、複数の同時にアクセス可能なブロック（ＳＭＢ１、ＳＭＢ２、．．．、ＳＭＢ１５）に分けられる。記憶場所（Ａ１、Ａ２、．．．、Ａ３２、及びＢ１、Ｂ２、．．．、Ｂ３２）はエッジ値を保存するのに使用される。可変ノード（Ｖ１、Ｖ２、．．．、Ｖ８）とチェックノード（Ｃ１、Ｃ２、Ｃ３、及びＣ４）とに対応するエッジ値は、矢印で表示したように保存される。このようにして、例えば、可変ノードＶ１の出力エッジ値を演算するためには、ブロックＳＭＢ１とＳＭＢ３とを同時に読み込んで、記憶場所Ａ１及びＡ３からチェックノードＣ１及びＣ３にそれぞれ対応する入力エッジ値を更新する。次ぎに、可変ノードＶ１の演算された出力エッジ値は、ブロックＳＭＢ５及びＳＭＢ７内部のチェックノードＣ１及びＣ３の入力エッジ値の保存位置であるアドレスＢ１及びＢ３にそれぞれ同時に書き込まれる。チェックノードＣ１の場合に、入力エッジ値は、ブロックＳＭＢ５、ＳＭＢ８、ＳＭＢ９、及びＳＭＢ１２内の記憶場所Ｂ１、Ｂ１３、Ｂ１７、及びＢ２９からそれぞれ同時に読み込まれる。
【００６９】
図１５は、本発明の実施例によるメモリ構造の他の例を示す。メモリ１４００は、複数の同時にアクセス可能なメモリブロック（ＳＭＢ１、ＳＭＢ２、．．．、ＳＭＢ１５）を含む。記憶場所（Ａ１、Ａ２、．．．、Ａ３２、及びＢ１、Ｂ２、．．．、Ｂ３２）はエッジ値を保存するのに利用される。可変ノード（Ｖ１、Ｖ２、．．．、Ｖ８）とチェックノード（Ｃ１、Ｃ２、Ｃ３及びＣ４）とに対応するエッジ値は、矢印で表示したように保存される。このようにして、例えば、可変ノードＶ１の出力エッジ値を演算するために、ブロックＳＭＢ１及びＳＭＢ３を同時に読み込んで、記憶場所Ａ１及びＡ３からチェックノードＣ１及びＣ３にそれぞれ対応する入力エッジ値を更新する。その後、可変ノードＶ１の演算された出力エッジ値は、ブロックＳＭＢ５及びＳＭＢ７内のチェックノードＣ１及びＣ３の入力エッジ保存場所であるアドレスＢ１及びＢ３にそれぞれ同時に書き込まれる。チェックノードＣ１の場所、入力エッジ値は、ブロックＳＭＢ５、ＳＭＢ８、ＳＭＢ９、及びＳＭＢ１２内の記憶場所Ｂ１、Ｂ１３、Ｂ１７、及びＢ２９からそれぞれ同時に読み込まれる。図１５のメモリ配置構造は、図１４に図示されたものに対して空間−効率が良い。
【００７０】
図１６は、本発明の実施例によるメモリ構造の他の例を示す。メモリ１５００は、複数の同時アクセス可能なメモリブロック（ＳＭＢ１、ＳＭＢ２、．．．、ＳＭＢ１５）を含む。記憶場所（Ａ１、Ａ２、．．．、Ａ３２、及びＢ１、Ｂ２、．．．、Ｂ３２）はエッジ値を保存するのに使用される。可変ノード（Ｖ１、Ｖ２、．．．、Ｖ８）とチェックノード（Ｃ１、Ｃ２、Ｃ３、及びＣ４）とに対応するエッジ値は、矢印で表示したように保存される。例えば、可変ノードＶ１の出力エッジ値を演算するために、ブロックＳＭＢ８及びＳＭＢ１０は同時に読み込んで、記憶場所Ａ１及びＡ３からチェックノードＣ１及びＣ３にそれぞれ対応する入力エッジ値を更新する。次ぎに、可変ノードＶ１の演算された出力エッジ値は、ブロックＳＭＢ１２及びＳＭＢ１４内のチェックノードＣ１及びＣ３の入力エッジ保存場所である記憶場所Ｂ１及びＢ３にそれぞれ同時に書き込まれる。チェックノードＣ１の場合、入力エッジ値はブロックＳＭＢ１２、ＳＭＢ９、ＳＭＢ８、及びＳＭＢ５内の記憶場所Ｂ１、Ｂ１３、Ｂ１７、及びＢ２９からそれぞれ同時に読み込まれる。メモリ構造は、図１５のメモリ構造と空間使用効率面では同一である。
【００７１】
図１７は、本発明の実施例によるメモリ構造の他の例を示す。メモリ１６００は、複数の同時アクセス可能なブロックＳＭＢ１、ＳＭＢ２、．．．、ＳＭＢ８を含む。記憶場所（Ａ１、Ａ２、．．．、Ａ１６、及びＢ１、Ｂ２、．．．Ｂ１６）はエッジ値を保存するのに使用される。エッジ値は、図１の二分グラフのエッジ値を保存するのに最小限の記憶場所の個数（３２）に対応する。記憶場所（Ａ１、Ａ２、．．．、Ａ１６、及びＢ１、Ｂ２、．．．、Ｂ１６）は、発見的にエッジに割り当てられ、ノードプロセスの同時読み込み及び／又は書き込み動作を可能にする。発見的な配置構造は、所望する速度のメモリアクセス及び／又はメモリ１６００の効率的な空間使用を可能にすることができる（例えば、最適化された点に）。記憶場所（Ａ１、Ａ２、．．．、Ａ１６、及びＢ１、Ｂ２、．．．、Ｂ１６）の最適配置構造は、一般的なノードプロセスが実現される方法及び使用されたコードの構造に依存することは理解することができる。例えば、図１７のメモリ構造を利用して図７及び図８のプロセスを行う時には、記憶場所（Ａ１、Ａ２、．．．、Ａ１６、及びＢ１、Ｂ２、．．．、Ｂ１６）に対して、図１１のプロセスを行う場合とは異なる最適化されたエッジ構造を有することができる。
【００７２】
図１８は、本発明の実施例による適用の例を示す。通信受信機１７００、例えば、無線端子又はデジタルテレビ端子は、アンテナ１７１０でラジオ通信信号を受信する。ダウンコンバータ１７２０は、受信されたラジオ信号を中間周波数信号に変換する。中間周波数信号は、復調器１７３０によって復調され、ベースバンド信号を生成する。ベースバンド信号は、ＬＤＰＣコードのような誤り訂正コードによってコーディングすることができる。本発明の実施例によって動作するデコーダ１７４０はベースバンド信号をデコーディングして、デコーディングされた信号を生成する。デコーディングされた信号は、デコーディング後回路１７５０で処理され、例えば、オーディオ及び／又はビデオ出力を生成することができる。デコーダ１７４０は、例えば、図７乃至図１７の動作を行うことができる。又、図１８は、本発明の実施例を無線通信に適用して示しているが、本発明は、有線、光通信、データ保存、及び更新のような他の通信応用分野にも適用することができる。
【産業上の利用可能性】
【００７３】
本発明の実施例によると、デコーダはノードプロセスに最適化されたメモリを有する。従って、デコーディング過程でデコーダは、反復的なノードプロセスのためのエッジ値の読み込みと書き込みに必要な時間を最小化することができる。従って、高速で動作するデコーダを容易に実現することができる。
【００７４】
以上、本発明の実施例によって詳細に説明したが、本発明はこれに限定されず、本発明が属する技術分野において通常の知識を有するものであれば本発明の思想と精神を離れることなく、本発明を修正または変更できる。
【図面の簡単な説明】
【００７５】
【図１】多様な種類のコードの二分グラフを例を示す図である。
【図２】多様な種類のコードの二分グラフを例を示す図である。
【図３】多様な種類のコードの二分グラフを例を示す図である。
【図４】可変ノード演算の例を示す図である。
【図５】チェックノード演算の例を示す図である。
【図６】チェックノード演算の例を示す図である。
【図７】本発明の一実施例によるデコーディング動作の例を示す流れ図である。
【図８】本発明の一実施例によるデコーディング動作の例を示す流れ図である。
【図９】本発明の一実施例によるデコーダの構成を示すブロック図である。
【図１０】本発明の一実施例によるデコーダの構成を示すブロック図である。
【図１１】本発明の一実施例によるデコーディング動作の例を示す流れ図である。
【図１２】本発明の一実施例によるデコーダの構成を示すブロック図である。
【図１３】本発明の一実施例によるデコーディング動作の例を示す流れ図である。
【図１４】本発明の一実施例によるメモリの構成の例を示す概略図である。
【図１５】本発明の一実施例によるメモリの構成の例を示す概略図である。
【図１６】本発明の一実施例によるメモリの構成の例を示す概略図である。
【図１７】本発明の一実施例によるメモリの構成の例を示す概略図である。
【図１８】本発明の一実施例による通信受信機を示す概略図である。
【符号の説明】
【００７６】
８１０    バッファ
８２０    デコーダ
８２２    メモリ
８２４    可変ノードプロセッサ
８２６    チェックノードプロセッサ
８２８    決定部
【図１】
2006340341.tif 000008
【図２】
2006340341.tif 000009
【図３】
2006340341.tif 000010
【図４】
2006340341.tif 000011
【図５】
2006340341.tif 000012
【図６】
2006340341.tif 000013
【図７】
2006340341.tif 000014
【図８】
2006340341.tif 000015
【図９】
2006340341.tif 000016
【図１０】
2006340341.tif 000017
【図１１】
2006340341.tif 000018
【図１２】
2006340341.tif 000019
【図１３】
2006340341.tif 000020
【図１４】
2006340341.tif 000021
【図１５】
2006340341.tif 000022
【図１６】
2006340341.tif 000023
【図１７】
2006340341.tif 000024
【図１８】
2006340341.tif 000025