(57)【特許請求の範囲】
【請求項１】
符号化される前の情報語を推定する復号装置において、
前記復号装置の入力として用いる値が取りうる値よりも狭い範囲に、処理する範囲を限定し、その限定された範囲内での値と、その値を所定の関数に代入したときの演算結果を関連付けたルックアップテーブルを参照した演算を行う過程を含む復号を行い、
変数ノードからチェックノードへのメッセージを計算するとき、出力する前記メッセージの範囲を制限する演算を行い、
チェックノードから変数ノードへのメッセージを演算するときに前記ルックアップテーブルを参照する
復号装置。
【請求項２】
前記復号は、LDPC符号化方式に基づく復号である
請求項１に記載の復号装置。
【請求項３】
符号化される前の情報語を推定する復号装置の復号方法において、
前記復号装置の入力として用いる値が取りうる値よりも狭い範囲に、処理する範囲を限定し、その限定された範囲内での値と、その値を所定の関数に代入したときの演算結果を関連付けたルックアップテーブルを参照した演算を行う過程を含む復号を行い、
変数ノードからチェックノードへのメッセージを計算するとき、出力する前記メッセージの範囲を制限する演算を行い、
チェックノードから変数ノードへのメッセージを演算するときに前記ルックアップテーブルを参照する
復号方法。
【請求項４】
符号化される前の情報語を推定する復号装置の復号を制御するコンピュータが読み取り可能なプログラムにおいて、
前記復号装置の入力として用いる値が取りうる値よりも狭い範囲に、処理する範囲を限定し、その限定された範囲内での値と、その値を所定の関数に代入したときの演算結果を関連付けたルックアップテーブルを参照した演算を行う過程を含む復号を行い、
変数ノードからチェックノードへのメッセージを計算するとき、出力する前記メッセージの範囲を制限する演算を行い、
チェックノードから変数ノードへのメッセージを演算するときに前記ルックアップテーブルを参照する
プログラム。
【請求項５】
請求項４に記載のプログラムが記録されている記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は復号装置および方法、プログラム、並びに記録媒体に関し、特に、復号に係わる演算を簡略化することができるようにした復号装置および方法、プログラム、並びに記録媒体に関する。
【背景技術】
【０００２】
近年、例えば、移動体通信などの通信分野、および地上波放送や衛星デジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化および復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、ＬＤＰＣ符号という）が脚光を浴びつつある。
【０００４】
LDPC符号は、R. G. Gallagerによる「R. G. Gallager, "Low-Density Parity-Check Codes", IRE Transations on Information Theory, 1962」（非特許文献１）において最初に提案されたものであり、その後、「D. J. C. MacKay, "Good error correcting codes based on very sparse matrices", Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999」や、「M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、符号長を長くしていくに従って、シャノン限界に近い性能が得られることがわかりつつある。
【非特許文献１】R. G. Gallager, "Low-Density Parity-Check Codes", IRE Transations on Information Theory, 1962
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、LDPC符号方式で符号化されたデータを復号する場合、その復号に係る演算量は、所定の関数を用いた演算などを含むため増大する傾向にある。しかしながら、演算量を低減することで、処理能力の低い装置であっても復号を行うことができるようになり、コストを低減させることができ、処理時間を短縮することができるようになる。よって、復号時の演算量の低減が望まれている。
【０００７】
本発明は、このような状況に鑑みてなされたものであり、符号化されたデータの復号に係る演算量を低減することができるようにするものである。
【課題を解決するための手段】
【０００８】
本発明の一側面の復号装置は、符号化される前の情報語を推定する復号装置において、前記復号装置の入力として用いる値が取りうる値よりも狭い範囲に、処理する範囲を限定し、その限定された範囲内での値と、その値を所定の関数に代入したときの演算結果を関連付けたルックアップテーブルを参照した演算を行う過程を含む復号を行い、変数ノードからチェックノードへのメッセージを計算するとき、出力する前記メッセージの範囲を制限する演算を行い、チェックノードから変数ノードへのメッセージを演算するときに前記ルックアップテーブルを参照する。
【０００９】
前記復号は、LDPC符号化方式に基づく復号であるようにすることができる。
【００１２】
本発明の一側面の復号方法は、符号化される前の情報語を推定する復号装置の復号方法において、前記復号装置の入力として用いる値が取りうる値よりも狭い範囲に、処理する範囲を限定し、その限定された範囲内での値と、その値を所定の関数に代入したときの演算結果を関連付けたルックアップテーブルを参照した演算を行う過程を含む復号を行い、変数ノードからチェックノードへのメッセージを計算するとき、出力する前記メッセージの範囲を制限する演算を行い、チェックノードから変数ノードへのメッセージを演算するときに前記ルックアップテーブルを参照する。
【００１３】
本発明の一側面のプログラムは、符号化される前の情報語を推定する復号装置の復号を制御するコンピュータが読み取り可能なプログラムにおいて、前記復号装置の入力として用いる値が取りうる値よりも狭い範囲に、処理する範囲を限定し、その限定された範囲内での値と、その値を所定の関数に代入したときの演算結果を関連付けたルックアップテーブルを参照した演算を行う過程を含む復号を行い、変数ノードからチェックノードへのメッセージを計算するとき、出力する前記メッセージの範囲を制限する演算を行い、チェックノードから変数ノードへのメッセージを演算するときに前記ルックアップテーブルを参照する。
【００１４】
本発明の一側面の記録媒体は、前記プログラムが記録されている。
【００１５】
本発明の一側面の復号装置および方法、プログラム、並びに記録媒体においては、復号装置の入力として用いる値が取りうる値よりも狭い範囲に、処理する範囲を限定し、その限定された範囲内での値と、その値を所定の関数に代入したときの演算結果を関連付けたルックアップテーブルを参照した演算を行う過程を含む復号が行われ、変数ノードからチェックノードへのメッセージを計算するとき、出力されるメッセージの範囲を制限する演算が行われ、チェックノードから変数ノードへのメッセージを演算するときにルックアップテーブルが参照される。
【発明の効果】
【００１６】
本発明の一側面によれば、復号に係る演算量を低減させることが可能となる。
【発明を実施するための最良の形態】
【００１７】
以下に、本発明の実施の形態について図面を参照して説明する。
【００１８】
図１は、ＬＤＰＣ(Low Density Parity Check codes)符号を用いた通信システムの一実施の形態の構成を示す図である。図１に示した通信システムは、ＬＤＰＣ符号化部１１、通信路１２、およびＬＤＰＣ符号復号部１３を含む構成とされている。送信側のＬＤＰＣ符号化部１１は、情報語をＬＤＰＣ符号化し、通信路１３に送出する。
【００１９】
受信側のＬＤＰＣ符号復号部１３は、通信路１２から雑音を含む信号を受信し、送信側で行われた符号化の規則（この場合、ＬＤＰＣ符号化部１１で行われたＬＤＰＣ符号）に基づいた復号を行い、情報語を推定して図示してない後段の処理に出力する。
【００２０】
このような通信システム、特にターボ符号やＬＤＰＣ符号などを用いた通信システムにおいては、軟判定情報を用いた繰り返し復号が行われる。
【００２１】
ＬＤＰＣ符号は図１に示したような通信システムに限らず、記録再生チャネルにも応用できる。図２は、ＬＤＰＣ符号を用いた記録再生システムの一実施の形態の構成を示す図である。図２に示した記録再生システムは、ＬＤＰＣ符号化部２１、記録／再生チャンネル２２、およびＬＤＰＣ符号復号部２３を含む構成とされている。
【００２２】
記録時には情報語がＬＤＰＣ符号化部２１で、ＬＤＰＣ符号化され、記録媒体に記録される。再生時には、ＬＤＰＣ符号復号部２３で、記録媒体から雑音を含んだ信号が読み取られ、記録時に行われた符号化の規則（この場合、ＬＤＰＣ符号化部２１で行われたＬＤＰＣ符号）に基づいた復号が行われ、情報語を推定して図示していない後段の処理に出力される。
【００２３】
ここで、ＬＤＰＣ符号について説明を加える。ＬＤＰＣ符号は、低密度パリティ検査符号であり、1962年、Robert G. Gallagerによって発表された符号化方式である。ＬＤＰＣ符号は、そのパリティ検査行列の非零の要素数が全要素数に対して少ない(低密度)ことを特徴とする線形符号である。ＬＤＰＣ符号は、パリティ検査行列の２部グラフ(bipartite graph)に短いサイクルが含まれないように構成することにより、繰り返し復号によって良好なビットエラー特性を示すことが知られている。
【００２４】
一般的に雑音や消失のある通信路では、情報語が受信側で正しく推定されるように誤り訂正符号が用いられる。
【００２５】
符号長ＮのＬＤＰＣ符号の任意の符号語ベクトルcは、Ｍ行Ｎ列のパリティ検査行列をＨとすると、
Ｈｃ＝０    ・・・（１）
を満たす。式（１）はＭ個のパリティ検査方程式を表している。
【００２６】
ＬＤＰＣ符号は、特に２元符号に限るものではないが、以下では２元符号の場合に限定して説明する。しかしながら、以下に説明する本発明が、２元符号の場合に限定されることを示しているのではない。
【００２７】
次式（２）は、ＬＤＰＣ符号のパリティ検査行列の一例を示す式である。
【数１】
0004572937.tif 000002
【００２８】
パリティ検査行列の各行はそれぞれ、パリティ検査方程式を表し、各列は符号ビットに対応する。ＬＤＰＣ符号は、パリティ検査行列あるいは２部グラフを元に、メッセージパッシング(message-passing)アルゴリズムによって復号できることが知られている。
【００２９】
Ｍ行Ｎ列のパリティ検査行列に対応する２部グラフは、チェック(check)に対応するＭ個のノード(node)と、変数(variable)に対応するＮ個のノード、およびノードを接続するエッジ(edge)により構成される。エッジは、パリティ検査行列の非零要素の場所に対応しており、第ｍ行第ｎ列の要素が零でない場合にのみｍ番目のチェックノードとｎ番目の変数ノードがエッジで接続される。ここでｍは０以上Ｍ未満の整数であり、ｎは０以上Ｎ未満の整数である。
【００３０】
図３は、式（２）のパリティ検査行列Ｈに対応した２部グラフを示している。図３中、丸はチェックノードＣを示し、四角は変数ノードＶを示している。図３に示した２部グラフは、丸で表された５個のチェックノードＣと、四角で表された１０個の変数ノードＶで構成されている。
【００３１】
メッセージパッシングアルゴリズムによるＬＤＰＣ符号の復号は、エッジで接続されたノード間にメッセージを伝搬させることによって行われ、図４に示したフローチャートに示すような手順が繰り返されることにより行われる。
【００３２】
ステップＳ１１において、変数ノードからチェックノードへのメッセージの初期化が行われる。すなわち、変数ノードからチェックノードに伝搬するメッセージＱm,nが、復号装置の入力である受信値Pnに初期化される。以下においてPnは対数尤度比であるとして扱う。
【００３３】
なお、以下の説明においては、“受信値”との記載を行うが、本発明は、受信される値のみに適用されることを示すのではなく、換言すれば、図１に示したような通信路１２を介したときに受信される値を扱う場合にのみ、本発明が適用されることを示す記載ではない。例えば、図２に示したような記録／再生チャンネル２２で再生された再生信号の値を扱う場合にも本発明を適用することは、勿論可能である。
【００３４】
ステップＳ１２において、チェックノードから変数ノードへのメッセージが計算される。この処理は、チェックノードから変数ノードに伝播するメッセージRm,nを次式（３）に基づく演算が行われることにより更新される。
【数２】
0004572937.tif 000003
【００３５】
式（３）において、Ｎ(ｍ)はｍ番目のチェックノードに接続されている変数ノード番号の集合であり、αm,n＝sign(Ｑm,n)、βm,n＝|Ｑm,n|はそれぞれＱm,nの符号、および絶対値を表し、関数fは次式（４）で与えられる。
【数３】
0004572937.tif 000004
【００３６】
ステップＳ１３において、変数ノードにおける処理として、変数ノードからチェックノードへのメッセージが計算され、復号結果の硬判定により得られる符号語の推定値のシンドロームを計算する。この計算は、事後対数尤度比Ｑnを、次式（５）により求めることで行われる。
【数４】
0004572937.tif 000005
【００３７】
式（５）において、Ｍ(ｎ)はｎ番目の変数ノードに接続されているチェックノード番号の集合である。さらに繰り返しが必要な場合、次式（６）に従って変数ノードからチェックノードに伝搬されるメッセージＱm,nが更新される。
【数５】
0004572937.tif 000006
【００３８】
メッセージパッシングアルゴリズムによる復号は、終了条件を満たすまでステップＳ１２とステップＳ１３の処理が繰り返され、最後にＱnの硬判定で符号語が推定される。ステップＳ１４において、繰り返しの処理を終了するか否かの判定が行われる。繰り返しを終了すると判断されるのは、以下の条件１または条件２が成り立つときである。
条件１．Ｑnの硬判定より得られる符号語の推定値をｚとするとき、シンドロームＨｚが０となれば終了
条件２．予め設定されている繰り返し回数に達した時点で終了
【００３９】
ステップＳ１４において、条件１または条件２のいずれか一方でも成り立ったとき、ステップＳ１５に処理が進められ、復号結果が後段の処理に出力される。ＬＤＰＣ符号を組織符号とした場合には、推定した符号語のパリティに相当する部分を取り除き情報語に相当する部分を取り出すことにより情報語の推定値を得ることができる。一方、条件１および条件２のいずれの条件も成り立っていないときには、ステップＳ１２に処理が戻され、それ以降の処理が繰り返される。
【００４０】
このような処理を行う復号装置の構成について説明する。図５は、ＬＤＰＣ符号におけるＬＤＰＣ符号復号装置の一実施の形態の構成を示す図である。図５に示したＬＤＰＣ符号復号装置５０は、メモリ５１、変数ノード処理演算器５２、メモリ５３、チェックノード処理演算器５４、メモリ５５、および硬判定復号器５６を含む構成とされている。
【００４１】
図５に示したＬＤＰＣ符号復号装置５０は、同一の装置で複数回の繰り返し復号を行うものであるが、初期化や繰り返し終了条件の判定部を省略した構成を示している。また以下の説明においては、全ての変数ノード、チェックノードにおける演算をパラレルに行うフルパラレルデコーダを想定して説明を行う。しかしながら、複数のノードの演算を１つまたは複数の演算器で処理する構成もあり、また、メモリ５１、メモリ５３のいずれか一方を持たない構成もある。そのような構成であっても、本発明を適用できるため、パラレルに行う場合のみに本発明が適用できることを限定しているわけではない。また対数尤度比やノード間を伝播するメッセージは量子化され、有限のビット数で表現されるとして説明を続ける。
【００４２】
メモリ５１には、復号装置の入力である受信値が入力され、一旦蓄積される。メモリ５１に蓄積されている受信値は、変数ノード処理演算器５２に供給される。変数ノード処理演算器５２は、図４に示したフローチャートのステップＳ１３の処理を実行する部分である。メモリ５３は、変数ノード処理演算器５２の処理が施されたデータを一旦記憶し、チェックノード処理演算器５４に供給する。
【００４３】
チェックノード処理演算器５４は、図４に示したフローチャートのステップＳ１２の処理を実行する部分である。メモリ５５は、チェックノード処理演算器５４の処理が施されたデータを一旦記憶し、変数ノード処理演算器５２に供給する。変数ノード処理演算器５２からの出力は、硬判定復号器５６に供給される。硬判定復号器５６からは、推定された符号語または情報語が後段の図示していない処理部に出力される。
【００４４】
図５に示したＬＤＰＣ符号復号装置５０には、量子化された受信値Pnが入力され、メモリ５１に一旦格納される。ステップＳ１３の処理を行う変数ノード処理演算器５２と、ステップＳ１２の処理を行うチェックノード処理演算器５４は交互に動作をし、硬判定復号結果を出力する。
【００４５】
ここでＬＤＰＣ符号復号装置５０への入力Ｐnは、例えば、A/D（Analog/Digital）コンバータでデジタル信号に変換された値Ｐnであり、例えば、量子化ステップｑ、量子化レベルの数２Ｍ1で量子化されているものとする。すなわち、受信値の量子化後の値yは、量子化前の値xとは次式（７）で関係付けられているものとする。
【数６】
0004572937.tif 000007
【００４６】
ここでＬＩＭＩＴ１は、出力を次式（８）で示される範囲に制限する演算を行う関数である。
【数７】
0004572937.tif 000008
【００４７】
ただし、ＬＤＰＣ符号復号装置５０内部での数値表現は、値ｙそのものではなく整数値を用いた方が扱いやすい。例えば、内部表現を、
ｙ’＝ｙ／ｑ−０．５
とすれば、ｙ’は、―Ｍ1からＭ1―１の間の整数値を取ることになる。よって、このように表現し、整数値を用いて処理が行えるように構成することも可能である。
【００４８】
図３に示した２部グラフにおけるチェックノードＣ0に対応するチェックノード処理演算器５４のブロック図を図６に示す。また、図３に示した２部グラフにおける変数ノードＶ0に対応する変数ノード処理演算器５２のブロック図を図７に示す。
【００４９】
図５におけるチェックノード処理演算器５４は、図６に示したチェックノード処理演算器５２と類似の回路ブロックを計５個含む。これは、図３を参照するにチェックノードがチェックノードＣ0乃至Ｃ4の５個あるからである。また、図５における変数ノード処理演算器５２は、図７に示した変数ノード処理演算器５２と類似の回路ブロックを計１０個含む。これは、図３を参照するに変数ノードが変数ノードＶ0乃至Ｖ9の１０個あるからである。
【００５０】
図６に示したチェックノード処理演算器５４は、式（３）に基づく演算を行うための構成を有している。すなわち図６に示したチェックノード処理演算器５４は、所定の関数ｆに基づく演算を行う演算部１０１−１乃至１０１−６、総和演算を行う演算部１０２、入力される２つの値のうち一方から他方を減算する減算部１０３−１乃至１０３−６、所定の関数ｆ-1に基づく演算を行う演算部１０４−１乃至１０４−６、入力される２つの値を乗算する乗算部１０５−１乃至１０５−６、入力される２つの値を乗算する乗算部１０６−１乃至１０６−６、および総積演算を行う演算部１０７を含む構成とされている。
【００５１】
図６中、Ｆ＿ＬＵＴは関数fに対応する演算を表し、F_INVは関数ｆ-1に対応する演算を表している。演算部１０１−１乃至１０１−６はそれぞれ、関数ｆに対応する演算を、入力されるβ0,0乃至β0,6に対して施し、演算部１０４−１乃至１０４−６はそれぞれ、関数ｆ-1に対応する演算を、入力される、対応する減算部１０３−１乃至１０３−６からの出力に対して施す。
【００５２】
ここで、演算部１０１−１乃至１０１―６（以下、演算部１０１−１乃至１０１−６をそれぞれ個々に区別する必要がない場合、単に演算部１０１と記述する。他の部分も同様に記述する）に入力される値が、どのような値であるかわからない場合、入力がある毎に、関数ｆに基づく演算を行う必要がある。しかしながら、ある程度、どのような値が入力されるかが想定できる場合、予め入力された値と、その値を関数ｆに代入したときの演算結果を対応付けたテーブルを用意することができ、その用意されたテーブルを参照することで、演算結果を出力することが可能となる。
【００５３】
すなわち、関数fの演算は、入力が量子化されて有限個の値をとるならば、ルックアップテーブル(LUT)を参照することで実装することができる。
【００５４】
また、関数ｆ-1の演算は、例えば、入力と固定値ｆ(0.5q), ｆ(1.5q), f(2.5q)などとの比較演算を行い、入力がf(0.5q)以上であれば0を、整数k＞0として入力がｆ(q(k+0.5))以上ｆ(q(k-0.5))未満であればkqを出力するというような構成とすることができる。
【００５５】
図７に示した変数ノード処理演算器５２は、式（５）および式（６）の演算を行うための構成を有している。すなわち、図７に示した変数ノード処理演算器５２は、入力される値の総和を演算する演算部１２１、入力される２つの値のうち一方から他方を減算する減算部１２２−１乃至１２２−３、および、所定の演算を行う演算部１２３−１乃至１２３−３を有する構成とされている。
【００５６】
演算部１２３−１乃至１２３−３は、それぞれ、式（８）で示される演算を行う。すなわちこの場合、ＬＩＭＩＴ１は、Ｆ＿ＬＵＴで参照される値が定数Ｍ1で定められる上限と下限の間の範囲に収まるように、式（６）の演算結果に対して式（８）の演算を施す。
【００５７】
一般に、量子化後の数値において隣り合うレベルの差(量子化ステップ)をより細かく取り、量子化レベルの数を多くすれば、量子化によるビット誤り率(BER)の劣化は抑えられ良好な復号特性が得られる。しかしながら、量子化ステップを細かくすると、演算が複雑になり装置は大規模になる。逆に、量子化ステップを粗く取り、量子化レベルの数を少なくすれば、演算は簡単になるが、量子化による劣化が大きくなる。
【００５８】
また、ＬＤＰＣの復号においては、チェックノードの演算において関数f、関数ｆ-1による非線形な変換が行われるため、入力値の取りうる範囲が広いほどチェックノード処理演算器５４では精度の高い演算が行われ、良好な復号特性が得られる。逆に、入力値の取りうる範囲が狭くなれば、チェックノード処理演算器５４における演算の精度も低くなり、量子化による劣化が大きくなる。
【００５９】
通常は、量子化による劣化が許容できる範囲において、演算が複雑になりすぎないように、量子化ステップと量子化レベルの数が設定される。例えば、特定の信号対雑音電力比において要求されるビット誤り率（BER）を達成できる最小のビット数で表現できる量子化ステップと量子化レベルの数が選択される。
【００６０】
以下に、具体的なＬＤＰＣ符号を用いた場合のシミュレーション結果を示す。ＬＤＰＣ符号は、符号長２４４８、情報ビット長２３１２の準巡回符号で、パリティ検査行列Ｈは次式（９）で表される１３６行２４４８列の行列が用いられる。
Ｈ＝［Ｈ0  Ｈ1  Ｈ2  ・・・Ｈ135］    ・・・（９）
【００６１】
ここで、各Ｈj（０≦ｊ＜１３６）は、それぞれ１３６行１８列の小行列を表す。Ｈ0は、次式（１０）で表される。なお式（１０）において点(.)は０を表す。
【数８】
0004572937.tif 000009
【００６２】
また、Ｈj（０＜ｊ＜１３６）の第ｓ行第ｔ列要素（０≦ｓ＜１３６，０≦ｔ＜１８）は、Ｈ0の第（ｓ＋ｊ） ｍｏｄ １３６行第ｔ列要素に等しく、次式（１１）が満たされる。
【数９】
0004572937.tif 000010
【００６３】
パリティ検査行列Ｈの行重み(column weight)は３、列重み(row weight)は５４であり、このようなパリティ検査行列Ｈで表されるＬＤＰＣ符号はregular ＬＤＰＣ符号である。
【００６４】
図８は、量子化ステップｑ＝１とし、Ｍ1を７，８，９，１０，１１，１２，１６とした場合のBPSK白色雑音通信路における復号後ＢＥＲ特性を表したグラフである。図８に示したグラフにおいて、横軸は情報１ビットあたりのエネルギー対雑音電力密度(Eb/N0)、縦軸は復号後のＢＥＲであり、繰り返し復号は、最大１６回とした。
【００６５】
図８に示したグラフより、Ｍ1の値が小さいほどＢＥＲは劣化することがわかる。しかしながら、Ｍ1が大きな値、例えば、Ｍ1＝１２のときには、入力値の範囲を制限したとしても、そのことによる劣化はほぼ見られないことがわかる。
【００６６】
図９は、シミュレーション結果からＢＥＲ＝１０−６となるＥｂ／Ｎ０の値をＭ１毎に求めてプロットしたグラフである。すなわち、図９において横軸はＭ１の値であり、縦軸はＢＥＲ＝１０−６を達成するのに必要なＥｂ／Ｎ０の値となる。
【００６７】
図９に示したグラフからも、１２未満のＭ１では、ＢＥＲ＝１０−６を達成するのに必要なＥｂ／Ｎ０の値はＭ１＝１６の場合に比べて増加し、ＢＥＲ性能が劣化するが、Ｍ１を１２以上とすれば、Ｍ１＝１６の場合とほぼ同じＢＥＲ性能が得られることがわかる。
【００６８】
表１は、Ｍ1＝１２の場合のＦ＿ＬＵＴの入出力（例えば、図６の演算部１０１−１乃至１０１−６にそれぞれ入力される値と、出力される値）を表している。
【表１】
0004572937.tif 000011
【００６９】
Ｍ1＝１２のときは、変数ノードからチェックノードへのメッセージＱm,nは−１１．５から１１．５までの２４通りの数値を取り、その絶対値βm,nは０．５から１１．５までの１２通りの数値を取る。表１に示されるＬＵＴの出力ダイナミックレンジで決まるＦ＿ＬＵＴ出力ビット数は、１５ビットであるため、Ｆ＿ＬＵＴの大きさは１２×１５＝１８０ビットの容量となる。
【００７０】
例えば、受信値およびメッセージを共に５ビットで表す場合、上記関数fによる変換は、メッセージの絶対値部分の４ビットの値に対して、それぞれ２4＝１６通りの関数値が対応される。
【００７１】
また別の例として、受信値およびメッセージを共に６ビットで表す場合、上記関数fによる変換は、メッセージの絶対値部分５ビットの値に対して、それぞれ２5＝３２通りの関数値が対応される。
【００７２】
入力ａビット、出力bビットのＬＵＴの容量は、２a×ｂの大きさとなり、入力の量子化レベルの数２aが多くなるほど、また出力のビット精度bが大きくなるほど、ＬＵＴは複雑になる可能性がある。そこで、ＬＤＰＣ符号復号装置５０のチェックノード処理演算器５４への入力を復号装置入力（受信値）が取りうる値よりも狭い範囲に制限し、チェックノード処理演算器５４の演算を簡略化する。
【００７３】
図１０は、変数ノード処理演算器５２’のブロック図である。図７に示した変数ノード処理演算器５２と比較するに、図１０に示した変数ノード処理演算器５２’は、式（６）の演算結果に対して施す演算が、ＬＩＭＩＴ１からＬＩＭＩＴ２になっている点で異なる。すなわち、図１０に示した変数ノード処理演算器５２’は、演算部２０１−１乃至２０１−３がＬＩＭＩＴ２に係わる演算を行う構成とされている点が、図７に示した変数ノード処理演算器５２と異なり、その他の構成は同じである。このような構成とされている図１０に示した変数ノード処理演算器５２’を、図５に示したＬＤＰＣ符号復号装置５０の変数ノード処理演算器５２の代わりに用いることは可能である。
【００７４】
演算部２０１で行われるＬＩＭＩＴ２に係わる演算は、Ｍ2＜Ｍ1なる整数Ｍ2とし、その出力を−ｑ（Ｍ2―０．５）からｑ（Ｍ2―０．５）の範囲に制限する演算を行う。すなわち、次式（１２）の演算を行う。
【数１０】
0004572937.tif 000012
【００７５】
関数fの入力で取りうる値の数がＭ1からＭ2へと少なくなることと、関数出力のダイナミックレンジが小さくなることから、関数fの演算に必要な回路、例えば、ＬＵＴ（ルックアップテーブル）を簡単な構成とすることが可能となる。また、関数fによる変換後のビット数が少なくなることから、チェックノード処理演算器５４における総和、減算および関数ｆ-1の演算を簡単にすることが可能となる。
【００７６】
次に、Ｍ2＜Ｍ1による制限を用いても、適切なＭ2を選択することによりＢＥＲ性能が劣化しないことを、シミュレーション結果を用いて示す。復号のシミュレーションとして用いたＬＤＰＣ符号は、上記した場合と同様に、符号長２４４８、情報ビット長２３１２の準巡回符号で、パリティ検査行列Ｈは式（９）で表される１３６行２４４８列の行列が用いられた場合である。
【００７７】
図１１は、受信値入力の量子化を量子化ステップｑ＝１、Ｍ1＝１６とし、Ｍ2を５，６，７，１６とした場合のBPSK白色雑音通信路における復号後ＢＥＲ特性を表している。Ｍ2＝１６は、上述した変数ノード処理演算器５２を用いた場合の復号方法においてＭ1＝１６とした場合と同様である。
【００７８】
図１１に示したグラフより、Ｍ2が６以下の値ではＢＥＲは劣化するが、Ｍ2を７とすればＦ＿ＬＵＴ入力の値の範囲を制限したことによる劣化は見られないことが読み取れる。
【００７９】
表２は、Ｍ2＝７の場合のＦ＿ＬＵＴの入出力を表している。
【表２】
0004572937.tif 000013
【００８０】
Ｍ2＝７のときは、変数ノードからチェックノードへのメッセージＱm,nは、−６．５から６．５までの１４通りの数値を取り、その絶対値βm,nは、０．５から６．５までの７通りの数値を取る。表２で示されるＬＵＴの出力ダイナミックレンジで決まるＦ＿ＬＵＴの出力ビット数は、８ビットであるため、Ｆ＿ＬＵＴの大きさは７×８＝５６ビットの容量となる。これは上記したＭ1＝１２の場合のＦ＿ＬＵＴの容量と比べると、約６９％の削減となることがわかる。
【００８１】
また、チェックノード処理演算器５４における総和、減算および関数ｆ-1の入力は、Ｍ1＝Ｍ2＝１２の場合より少ないビット数となり、演算を簡略化することが可能となる。
【００８２】
図１２は、シミュレーション結果からＢＥＲ＝１０-6となるＥｂ／Ｎ０の値を、Ｍ2毎に求めてプロットしたグラフである。すなわち、図１２において横軸はＭ2の値であり、縦軸はＢＥＲ＝１０-6を達成するのに必要なＥｂ／Ｎ０の値である。
【００８３】
図１２に示したグラフからも、７未満のＭ2ではＢＥＲ＝１０-6を達成するのに必要なＥｂ／Ｎ０の値は、Ｍ2＝１６の場合に比べて増加する。しかしながら、Ｍ2を７以上１６未満とすれば、Ｍ2＝１６の場合と比べてわずかに小さなＥｂ／Ｎ０の値でもＢＥＲ＝１０-6を達成することが可能となることがわかる。
【００８４】
一般のＬＤＰＣ復号の過程でチェックノードにおける演算では、式（３）において、次式（１３）の演算を行う。
【数１１】
0004572937.tif 000014
【００８５】
この式（１３）で示される演算は、βm,n'＝|Ｑm,n'|の最小値よりも小さな値となる。すなわち、変数ノードからチェックノードへのメッセージＱm,nの絶対値(信頼度の大きさ)が、全て大きな値であったとしても、式（３）によって得られるチェックノードから変数ノードへのメッセージのＲm,nの絶対値(信頼度の大きさ)は、それよりも小さくなる。
【００８６】
仮に、βm,n'＝|Ｑm,n'|が全て６．５であったとすると、Ｒm,n絶対値は、パリティ検査行列Ｈの列重みが５４であることから、次式（１４）で示す値となり、βm,n'＝|Ｑm,n'|＝６．５に比べて非常に低い信頼度となってしまう。
【数１２】
0004572937.tif 000015
【００８７】
一方、表２で定義したＬＵＴでは、βm,n'＝|Ｑm,n'|＝６．５に対応する関数fの値を０としたため、βm,n'＝|Ｑm,n'|が、全て６．５であったとした場合のF_INVは、６を出力する。従って、変数ノードからチェックノードへの信頼度が大きな値となっても信頼度の低下を抑える効果により、Ｍ2＝１６の場合と比べてＢＥＲ特性が改善されることになる。
【００８８】
このように、チェックノード処理演算器５４への入力を、ＬＤＰＣ符号復号装置５０への入力である受信値が取りうる値よりも狭い範囲に制限する（処理する範囲を制限する）ことで、復号性能を殆ど劣化させることなく、復号において関数ｆの演算、チェックノード処理演算器５４における総和、減算および関数ｆ-1の演算を簡略化することができる。
【００８９】
上述した一連の処理、例えば、ＬＵＴを参照して入力値を出力値に変換する処理などは、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【００９０】
図１３は、上述した一連の処理をプログラムにより実行するパーソナルコンピュータのハードウェアの構成の例を示すブロック図である。
【００９１】
コンピュータにおいて、ＣＰＵ（Central Processing Unit）５０１、ＲＯＭ（Read Only Memory）５０２、ＲＡＭ（Random Access Memory）５０３は、バス５０４により相互に接続されている。
【００９２】
バス５０４には、さらに、入出力インターフェース５０５が接続されている。入出力インターフェース５０５には、キーボード、マウス、マイクロホンなどよりなる入力部５０６、ディスプレイ、スピーカなどよりなる出力部５０７、ハードディスクや不揮発性のメモリなどよりなる記憶部５０８、ネットワークインタフェースなどよりなる通信部５０９、磁気ディスク、光ディスク、光磁気ディスク、あるいは半導体メモリなどのリムーバブルメディア５１１を駆動するドライブ５１０が接続されている。
【００９３】
以上のように構成されるコンピュータでは、ＣＰＵ５０１が、例えば、記憶部５０８に記憶されているプログラムを、入出力インターフェース５０５及びバス５０４を介して、ＲＡＭ５０３にロードして実行することにより、上述した一連の処理が行われる。
【００９４】
コンピュータ（ＣＰＵ５０１）が実行するプログラムは、例えば、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)等）、光磁気ディスク、もしくは半導体メモリなどよりなるパッケージメディアであるリムーバブルメディア５１１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供される。
【００９５】
そして、プログラムは、リムーバブルメディア５１１をドライブ５１０に装着することにより、入出力インターフェース５０５を介して、記憶部５０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部５０９で受信し、記憶部５０８にインストールすることができる。その他、プログラムは、ＲＯＭ５０２や記憶部５０８に、あらかじめインストールしておくことができる。
【００９６】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【００９７】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【００９８】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【００９９】
【図１】ＬＤＰＣ符号復号システムの一例を示す図である。
【図２】ＬＤＰＣ符号復号システムの一例を示す図である。
【図３】パリティ検査行列に対応した２部グラフを示す図である。
【図４】ＬＤＰＣ符号の復号アルゴリズムを説明するフローチャートである。
【図５】ＬＤＰＣ符号復号に係わる回路構成を示す図である。
【図６】チェックノード処理演算器の詳細の構成を示す図である。
【図７】変数ノード処理演算器の詳細の構成を示す図である。
【図８】ビット誤り率特性を示す図である。
【図９】ビット誤り率特性を示す図である。
【図１０】変数ノード処理演算器の詳細の構成を示す図である。
【図１１】ビット誤り率特性を示す図である。
【図１２】ビット誤り率特性を示す図である。
【図１３】記録媒体について説明するための図である。
【符号の説明】
【０１００】
５０  ＬＤＰＣ符号復号装置，  ５１  メモリ，  ５２  変数ノード処理演算器，  ５３  メモリ，  ５４  チェックノード処理演算器，  ５５  メモリ，  ５６  硬判定符号器
【図１】
0004572937.tif 000016
【図２】
0004572937.tif 000017
【図３】
0004572937.tif 000018
【図４】
0004572937.tif 000019
【図５】
0004572937.tif 000020
【図６】
0004572937.tif 000021
【図７】
0004572937.tif 000022
【図８】
0004572937.tif 000023
【図９】
0004572937.tif 000024
【図１０】
0004572937.tif 000025
【図１１】
0004572937.tif 000026
【図１２】
0004572937.tif 000027
【図１３】
0004572937.tif 000028