(57)【特許請求の範囲】
【請求項１】
通信システムの信号受信装置における信号受信方法であって、
信号を受信するステップと、
前記受信信号を、指数表示方式を用いてガロア域（ＧＦ）のエレメントを表示する非バイナリＬＤＰＣ復号方式により復号するステップと、を含み、 
前記非バイナリＬＤＰＣ復号方式は、指数表示方式を用いてＧＦのエレメントを表示する検査ノード演算を含み、
前記受信信号を非バイナリＬＤＰＣ復号方式を用いて復号するステップは、
任意の検査ノードに入力される複数のメッセージを、前記指数表示方式を用いて表示して置換するステップと、
前記置換された信号を、多項式表示方式を用いて表示してインターリーブするステップと、
前記インターリーブされた信号を、ＧＦ上において高速フーリエ変換（ＦＦＴ）するステップと、
前記ＦＦＴが行われた信号の検査ノード演算を行うステップと、
前記検査ノード演算が行われた信号を逆フーリエ変換（ＩＦＦＴ）するステップと、
前記ＩＦＦＴが行われた信号を、指数表示方式を用いて表示してデインターリーブするステップと、
前記デインターリーブされた信号を、前記置換に相応するように逆置換するステップとを含むことを特徴とする、信号受信方法。
【請求項２】
前記指数表示方式は、ＧＦ(２ｐ)の全てのエレメントの指数のみを検出し、前記検出した指数のみを使用して、前記ＧＦ(２ｐ)の全てのエレメントを表示する方式であることを特徴とする、請求項１に記載の信号受信装置における信号受信方法。
【請求項３】
前記(２ｐ)がＧＦ(２４)であり、前記ＧＦ(２４)の全てのエレメント{0,1,α,α2,α3,…,α14}が、係数のＧＦ(２)で定義された３次以下の多項式a3x3+a2x2+a1x+a0で表現される場合、前記ＧＦ(２４)の全てのエレメント{0,1,α,α2,α3,…,α14}、多項式係数{a3,a2,a1,a0}及びそれに対応する十進数表現は、下記の表１のように表現されることを特徴とする、請求項２に記載の信号受信装置における信号受信方法。
【表１】
0004402700.tif 000010
【請求項４】
前記置換された信号を、多項式表示方式を用いて表示してインターリーブするステップは、下記の表２に示すように、前記置換された信号を前記多項式表示方式を用いて表示してインターリーブするステップを含むことを特徴とする、請求項３に記載の信号受信装置における信号受信方法。
【表２】
0004402700.tif 000011
【請求項５】
通信システムの信号受信装置であって、
信号を受信する受信機と、
前記受信信号を、ＧＦのエレメントを指数表示方式を用いて表示する非バイナリＬＤＰＣ復号方式により復号する復号器とを備え、
前記非バイナリＬＤＰＣ復号方式は、前記ＧＦのエレメントを指数表示方式を用いて表示する検査ノード演算を含み、
前記復号器は、
任意の検査ノードに入力される複数のメッセージを、前記指数表示方式を用いて表示して置換する複数の掛け算器と、
前記置換された信号を、多項式表示方式を用いて表示してインターリーブする複数のインターリーバと、
前記インターリーブされた信号を、ＧＦ上において高速フーリエ変換（ＦＦＴ）する複数のＦＦＴユニットと、
前記ＦＦＴが行われた信号を、検査ノード演算を行う検査ノード処理器と、
前記検査ノード演算が行われた信号を逆高速フーリエ変換（ＩＦＦＴ）する複数のＩＦＦＴユニットと、
前記ＩＦＦＴが行われた信号を、指数表示方式を用いて表示してデインターリーブする複数のデインターリーバと、
前記デインターリーブされた信号を、前記置換に相応するように逆置換する複数の掛け算器とを備えることを特徴とする、信号受信装置。
【請求項６】
前記指数表示方式は、ＧＦ(２ｐ)の全てのエレメントの指数のみを検出し、前記検出した指数のみを使用して、前記ＧＦ(２ｐ)の全てのエレメントを表示する方式であることを特徴とする、請求項５に記載の信号受信装置。
【請求項７】
前記(２ｐ)がＧＦ(２４)であり、前記ＧＦ(２４)の全てのエレメント{0,1,α,α2,α3,…,α14}が、係数のＧＦ(２)で定義された３次以下の多項式a3x3+a2x2+a1x+a0で表現される場合、前記ＧＦ(２４)の全てのエレメント{0,1,α,α2,α3,…,α14}、多項式係数{a3,a2,a1,a0}及びそれに対応する十進数表現は、下記の表３のように表現されることを特徴とする、請求項６に記載の信号受信装置。
【表３】
0004402700.tif 000012
【請求項８】
前記複数のインターリーバは、下記の表４に示すように、前記置換された信号を、前記多項式表示方式を用いて表示してインターリーブすることを特徴とする、請求項７に記載の信号受信装置。
【表４】
0004402700.tif 000013
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システムの信号受信装置及び方法に関し、特に、非バイナリ(non−binary)低密度パリティ検査(Low Density Parity Check、以下、“ＬＤＰＣ”と称する。)符号を使用する通信システムにおいて、検査ノードの演算に必要とするメモリ容量を最小化して、非バイナリＬＤＰＣ符号を復号する信号受信装置及び方法に関する。
【背景技術】
【０００２】
次世代通信システムでは、パケットサービス通信システムの形態で開発されており、パケットサービス通信システムは、バーストパケットデータ(burst packet data)を複数の移動端末機(Mobile Station、以下、“ＭＳ”と称する。)に送信するシステムであって、大容量データの送信に適合するように設計されてきた。また、次世代通信システムでは、チャンネル符号としてターボ符号(turbo code)と共に、高速データの送信時の性能利得に優れ、送信チャンネルから発生するノイズによる誤りを效果よく訂正してデータ送信の信頼度を高めることができるＬＤＰＣ符号を使用することを積極的に考慮している。ＬＤＰＣ符号の使用を積極的に考慮している次世代通信システムとしては、ＩＥＥＥ(Institute of Electrical and Electronics Engineers)８０２.１６ｅに準拠した通信システム及びＩＥＥＥ８０２.１１ｎに準拠した通信システムなどがある。
【０００３】
ここで、図１を参照して、ＬＤＰＣ符号を使用する一般の通信システムの信号送信装置の構造について説明する。
図１は、ＬＤＰＣ符号を使用する一般の通信システムの信号送信装置の構造を示す図である。
図１によれば、信号送信装置は、符号器１１１と、変調器１１３と、送信機１１５とを含む。信号送信装置において送信しようとする情報ベクトル(s_)が発生すると、情報ベクトル(s_)は符号器１１１に伝送される。符号器１１１は、情報ベクトル(s_)を所定の符号化方式により符号化して、符号語ベクトル(c_)、すなわち、ＬＤＰＣ符号語を生成した後、変調器１１３に出力する。ここで、符号化方式は、例えばＬＤＰＣ符号化方式である。変調器１１３は、所定の変調方式により符号語ベクトル(c_)を変調して、変調ベクトル(m_)を生成した後、送信機１１５に出力する。送信機１１５は、変調器１１３から出力された変調ベクトル(m_)を入力して送信信号処理を施した後、アンテナ(ＡＮＴ)を介して信号受信装置に送信する。
【０００４】
次に、図２を参照して、ＬＤＰＣ符号を使用する一般の通信システムの信号受信装置の構造について説明する。
図２は、ＬＤＰＣ符号を使用する一般の通信システムの信号受信装置の構造を示す図である。
図２によれば、信号受信装置は、受信機２１１と、復調器２１３と、復号器２１５とを含む。信号送信装置から送信された信号は、信号受信装置のアンテナを介して受信されて受信機２１１に伝えられる。受信機２１１は、受信信号を受信信号処理した後、その受信信号処理された受信ベクトル(r_)を復調器２１３に出力する。復調器２１３は、受信機２１１から出力された受信ベクトル(r_)を入力して、信号送信装置の変調器、すなわち、変調器１１３で適用した変調方式に相応する復調方式により復調した後、その復調ベクトル(x_)を復号器２１５に出力する。復号器２１５は、復調器２１３から出力された復調ベクトル(x_)を入力して、信号送信装置の符号器、すなわち、符号器１１１で適用した符号化方式に相応する復号方式により復号した後、その復号信号を、最終的に復元された情報ベクトル
【０００５】
【数１】
0004402700.tif 000002
【０００６】
として出力する。ここで、復号方式、すなわち、ＬＤＰＣ復号方式は、和積(sum−product)アルゴリズムに基づいた反復復号(iterative decoding)アルゴリズムを使用するものである。和積アルゴリズムについては、後で具体的に説明し、その詳細な説明は省略する。
【０００７】
一方、非バイナリＬＤＰＣ符号は、大部分のエレメントが０の値を有し、それ以外の極少数のエレメントが０でなく、例えば１の値を有するパリティ検査行列により定義される符号である。したがって、非バイナリＬＤＰＣ符号のパリティ検査行列を構成するエレメントは、全部０又は１の値を有する。これとは異なり、非バイナリＬＤＰＣ符号のパリティ検査行列を構成するエレメントは、全部ガロア域(Galois Field、以下、「ＧＦ」と称する。)(q)のエレメントである。ＧＦ(q)において、qはＧＦの次数を示し、q＝２ｐである。したがって、非バイナリＬＤＰＣ符号は、大部分のエレメントが０の値を有し、それ以外の極少数のエレメントが０でなく、例えばＧＦ(q)のエレメントであるパリティ検査行列により定義される符号である。
また、非バイナリＬＤＰＣ符号の符号語Cは、ＧＦ(q)のエレメントを含んだ長さがNであるベクトルとして、下記の式（１）の条件を満足する。
【０００８】
【数２】
0004402700.tif 000003
【０００９】
上記式（１）において、hijは非バイナリＬＤＰＣ符号のパリティ検査行列のj番目行のi番目列に存在するエレメントを示し、cjは符号語Cのi番目のエレメントを示し、Mはパリティ検査行列の行数を示し、Nはパリティ検査行列の列数を示す。
ここで、パリティ検査行列のj番目行が３つの０でないエレメントを含むとし、３つの０でないエレメントの各々が、hji1, hji2, hji3とする場合、下記の式（２）のようなパリティ検査方程式が成立する。
【００１０】
【数３】
0004402700.tif 000004
【００１１】
上記式（２）において、丸付きの“＋”はＧＦ(q)上における足し算を示し、丸付きの“×”はＧＦ(q)上における掛け算を示す。
一般的に、ＧＦ(２ｐ)のエレメントを示すための方式として多項式表示方式が使用されている。ＧＦ(２ｐ)の係数は、ＧＦ(２)で定義されたp次既約多項式(irreducible polynomial)から生成され、ＧＦ(２ｐ)の全てのエレメントは、その係数がＧＦ(２)で定義されたp−１次多項式で表示される。ここで、ＧＦ(２４)を一例として、ＧＦ(２ｐ)について説明する。
【００１２】
ＧＦ(２４)は、４次既約多項式p(x)＝x４＋x＋１から生成される。ここで、４次既約多項式p(x)＝x４＋x＋１のルート(root)をαとする場合、ＧＦ(２４)の全てのエレメントは、{0,1,α,α2,α3,…,α14}である。また、ＧＦ(２４)の全てのエレメントは、係数がＧＦ(２)で定義された３次以下の多項式a3x3 +a2x2+a1x+a0で表現され得る。
ＧＦ(２４)の全てのエレメント{0,1,α,α2,α3,…,α14}、多項式係数{a3,a2,a1,a0}及びそれに対応する十進数表現は、下記の表１に示すようである。
【００１３】
【表１】
0004402700.tif 000005
【００１４】
一方、ＬＤＰＣ符号は、２部グラフ(bipartite graphs)で表現できるが、２部グラフは、変数ノードと、検査ノードと、変数ノード及び検査ノードを連結するエッジとで表現されるグラフである。
また、ＬＤＰＣ符号は、２部グラフ上において、和積アルゴリズムに基づいた反復復号アルゴリズムを使用して復号することができる。ここで、和積アルゴリズムは、メッセージ伝達アルゴリズムの一種である。メッセージ伝達アルゴリズムとは、２部グラフ上においてエッジを介してメッセージを交換し、変数ノード又は検査ノードに入力されるメッセージから出力メッセージを計算して、アップデートするアルゴリズムを示す。したがって、ＬＤＰＣ符号を復号するための復号器は、和積アルゴリズムに基づいた繰返し復号アルゴリズムを使用するため、ターボ符号の復号器に比べて構成が複雑ではなく、並列処理復号器として具現するのが容易である。
ＧＦ(２ｐ)で定義されたＬＤＰＣ符号のバイナリ２部グラフにおいて、変数ノードはＧＦ(２p)個のランダム変数であり、エッジを介して伝えられるメッセージは２ｐのサイズを有するベクトルである。２ｐのサイズを有するベクトルが含むエレメントの各々は、ランダム変数が２ｐ個のＧＦ(２ｐ)のエレメントの何れか一つを持つ確率値の各々を示す。
【００１５】
ここで、図３を参照して、非バイナリＬＤＰＣ符号におけるエッジの値によるメッセージベクトルの置換(permutation)について説明する。
図３は、一般の非バイナリＬＤＰＣ符号におけるエッジの値によるメッセージベクトルの置換(permutation)を示す図である。
図３によれば、変数ノードi及び検査ノードjは、エッジを介して連結されており、変数ノードi及び検査ノードjを連結するエッジは、ＧＦ(２ｐ)のエレメントhjiの値を有する。このように、変数ノードi及び検査ノードjを連結するエッジがＧＦ(２ｐ)のエレメントhjiの値を有するということは、ＧＦ(２ｐ)で定義されたパリティ検査行列のj 行i 列のエレメントがhjiであることを示す。ここで、変数ノードi及び検査ノードjを連結するエッジを介して伝えられるメッセージは、２ｐのサイズを有するベクトルを示し、２ｐのサイズを有するメッセージベクトルが含むエレメント{P0,…,Pq−1}の各々は、変数ノードiがＧＦ(２ｐ)のエレメント{0,1,…,q−1}を有する確率値を示す。メッセージベクトルは、そのエッジの値hjiにより置換(permutation)が遂行され、このとき、メッセージベクトルが含むエレメントは順次
【００１６】
【数４】
0004402700.tif 000006
【００１７】
になる。ここで、掛け算はＧＦ(２ｐ)上において定義され、十進数{0,1,…,q−1}は、表１に示すような多項式表示方式により表現されたＧＦ(２ｐ)のエレメントを示す。
【００１８】
次に、図４を参照して、非バイナリＬＤＰＣ符号を和積アルゴリズムを使用して復号する復号器の内部構造について説明する。
図４は、一般の非バイナリＬＤＰＣ符号を復号する復号器の内部構造を示す図である。
図４の説明に先立ち、一般的に、復号器は、検査ノード処理部と、変数ノード処理部とを含むが、図４には復号器の検査ノード処理部の構造のみが示されていることに留意すべきである。図４によれば、復号器内のノード処理部は、第１の混合ネットワーク処理部４１０と、検査ノード処理器４４０と、第２の混合ネットワーク処理部４７０とを含む。
【００１９】
第１の混合ネットワーク処理部４１０は、例えばdc個の複数の掛け算器、すなわち、掛け算器４１１−１、掛け算器４１１−２、掛け算器４１１−３、・・・、掛け算器４１１−dcのdc個の掛け算器と、例えばdc個の複数の高速フーリエ変換(Fast Fourier Transform、以下、「ＦＦＴ」と称する。)ユニット、すなわち、ＦＦＴユニット４１３−１、ＦＦＴユニット４１３−２、ＦＦＴユニット４１３−３、・・・ＦＦＴユニット４１３−dcのdc個のＦＦＴユニットとを含む。
【００２０】
第２の混合ネットワーク処理部４７０は、例えばdc個の複数の逆高速フーリエ変換(Inverse Fast Fourier Transform、以下、「ＩＦＦＴ」と称する。)ユニット、すなわち、ＩＦＦＴユニット４７１−１、ＩＦＦＴユニット４７１−２、ＩＦＦＴユニット４７１−３、・・・ＩＦＦＴユニット４７１−dcのdc個のＩＦＦＴユニットと、例えばdc個の複数の掛け算器、すなわち、掛け算器４７３−１、掛け算器４７３−２、掛け算器４７３−３、・・・、掛け算器４７３−dcのdc個の掛け算器とを含む。
なお、非バイナリＬＤＰＣ符号のパリティ検査行列においてj番目検査ノードを一例として、検査ノード処理部の動作について説明する。ここで、j番目検査ノードの次数は、dcとする。
【００２１】
まず、第１の混合ネットワーク処理部４１０に入力される入力メッセージをxi1, xi2,…, xidcとする場合、入力メッセージxi1, xi2,…, xidc は、変数ノードから検査ノードに伝えられるメッセージであり、入力メッセージxi1, xi2,…, xidcの各々は、２ｐのサイズを有するベクトルである。入力メッセージxi1, xi2,…, xidcは、掛け算器４１１−１、掛け算器４１１−２、掛け算器４１１−３、・・・、掛け算器４１１−dcに各々入力される。
【００２２】
掛け算器４１１−１、掛け算器４１１−２、掛け算器４１１−３、・・・、掛け算器４１１−dcの各々は、入力メッセージベクトルxi1, xi2,…, xidcの各々及びパリティ検査行列のエッジ値hji1, hji2,…, hjidcの各々と、ＧＦ(２ｐ)上における掛け算を遂行する。ところが、入力メッセージはＧＦ(２ｐ)上のエレメントではなく、ＧＦ(２ｐ)上のエレメントを有する確率値を示すため、実際に掛け算器４１１−１、掛け算器４１１−２、掛け算器４１１−３、・・・、掛け算器４１１−dcの各々は、入力メッセージxi1, xi2,…, xidc の各々を 置換(permutation)するものである。ここで、 置換(permutation)情報を格納するには２ｐ×２ｐ個の単位メモリが必要であり、単位メモリはｐビットからなる。したがって、 置換(permutation)情報を格納するには、計２ｐ×２ｐ×pビットを格納すべきメモリ容量が必要になる。
【００２３】
掛け算器４１１−１、掛け算器４１１−２、掛け算器４１１−３、・・・、掛け算器４１１−dcの各々は、入力メッセージxi1, xi2,…, xidc の各々を 置換(permutation)した後、ＦＦＴユニット４１３−１、ＦＦＴユニット４１３−２、ＦＦＴユニット４１３−３、・・・、ＦＦＴユニット４１３−dcの各々に出力される。ＦＦＴユニット４１３−１、ＦＦＴユニット４１３−２、ＦＦＴユニット４１３−３、・・・、ＦＦＴユニット４１３−dcの各々は、掛け算器４１１−１、掛け算器４１１−２、掛け算器４１１−３、・・・、掛け算器４１１−dcの各々から出力された信号を入力してＦＦＴを遂行した後、検査ノード処理器４４０に出力される。ここで、ＦＦＴユニット４１３−１、ＦＦＴユニット４１３−２、ＦＦＴユニット４１３−３、・・・、ＦＦＴユニット４１３−dcの各々に入力される信号は、表１で定義したような多項式表示方式により表現されたエレメントの確率値である。また、ＦＦＴユニット４１３−１、ＦＦＴユニット４１３−２、ＦＦＴユニット４１３−３、・・・、ＦＦＴユニット４１３−dcの各々で遂行されるＦＦＴは、一般のＦＦＴではないＧＦ(２ｐ)上で遂行されるＦＦＴを示し、これは、高速アダマール変換（Fast Hadamard Transform、以下、「ＦＨＴ」と称する。)と同様である。
【００２４】
検査ノード処理器４４０は、ＦＦＴユニット４１３−１、ＦＦＴユニット４１３−２、ＦＦＴユニット４１３−３、・・・、ＦＦＴユニット４１３−dcの各々から出力された信号を入力して検査ノード演算を遂行した後、その結果をＩＦＦＴユニット４７１−１、ＩＦＦＴユニット４７１−２、ＩＦＦＴユニット４７１−３、・・・、ＩＦＦＴユニット４７１−dcの各々に出力する。ＩＦＦＴユニット４７１−１、ＩＦＦＴユニット４７１−２、ＩＦＦＴユニット４７１−３、・・・、ＩＦＦＴユニット４７１−dcの各々は、検査ノード処理器４４０から出力された信号を入力してＩＦＦＴを遂行した後、掛け算器４７３−１、掛け算器４７３−２、掛け算器４７３−３、・・・、掛け算器４７３−dcの各々に出力する。ここで、ＩＦＦＴユニット４７１−１、ＩＦＦＴユニット４７１−２、ＩＦＦＴユニット４７１−３、・・・、ＩＦＦＴユニット４７１−dcの各々で遂行されるＩＦＦＴは、一般のＩＦＦＴではなく、ＧＦ(２ｐ)上で遂行されるＩＦＦＴを示す。また、ＩＦＦＴユニット４７１−１、ＩＦＦＴユニット４７１−２、ＩＦＦＴユニット４７１−３、・・・、ＩＦＦＴユニット４７１−dcの各々は、ＦＦＴユニット４１３−１、ＦＦＴユニット４１３−２、ＦＦＴユニット４１３−３、・・・、ＦＦＴユニット４１３−dcの各々の出力値が１／２ｐだけスケーリング(scaling)されることを除いては、同様な構造を持つ。
【００２５】
掛け算器４７３−１、掛け算器４７３−２、掛け算器４７３−３、・・・、掛け算器４７３−dcの各々は、ＩＦＦＴユニット４７１−１、ＩＦＦＴユニット４７１−２、ＩＦＦＴユニット４７１−３、・・、ＩＦＦＴユニット４７１−dcの各々から出力された信号及びパリティ検査行列のエッジ値hji1, hji2,…, hjidcの逆元h-1ji1, h-1ji2,…, h-1jidcの各々と、ＧＦ(２ｐ)上における掛け算を遂行する。ここで、掛け算器４７３−１、掛け算器４７３−２、掛け算器４７３−３、・・・、掛け算器４７３−dcも、ＩＦＦＴユニット４７１−１、ＩＦＦＴユニット４７１−２、ＩＦＦＴユニット４７１−３、・・・、ＩＦＦＴユニット４７１−dcから出力された信号を置換(permutation)するものであり、この置換(permutation)は、掛け算器４１１−１、掛け算器４１１−２、掛け算器４１１−３、・・・、掛け算器４１１−dcで遂行した置換(permutation)に対する逆置換(inverse permutation)である。以下、説明の便宜上、掛け算器４７３−１、掛け算器４７３−２、掛け算器４７３−３、・・・、掛け算器４７３−dcの置換(permutation)を“逆置換(inverse permutation)”と称する。逆置換(inverse permutation)情報を格納するには２ｐ×２ｐ個の単位メモリが必要であり、単位メモリはｐビットからなる。したがって、逆置換(inverse permutation)情報を格納するには、計２ｐ×２ｐ×pビットを格納すべきメモリ容量が必要になる。置換(permutation)情報及び逆置換(inverse permutation)の一方の情報は、その他方から抽出できるので、実際には何れか一つだけを格納してもよい。
【００２６】
前述したように、検査ノード演算の遂行の際、置換(permutation)情報又は逆置換(inverse permutation)情報を格納するためには、２ｐ×２ｐ×pビットを格納すべきメモリ容量が必要になる。したがって、検査ノード演算を遂行するために必要とするメモリ容量を減少させることができる復号器の必要性が要求されている。
【特許文献１】米国特許公開第ＵＳ２００５／００５０４３５Ａ１号
【発明の開示】
【発明が解決しようとする課題】
【００２７】
よって、本発明の目的は、非バイナリＬＤＰＣ符号を使用する通信システムにおける信号受信装置及び方法を提供することにある。
本発明の他の目的は、非バイナリＬＤＰＣ符号を使用する通信システムにおいて、検査ノードを演算するために必要とするメモリ容量を最小化して、非バイナリＬＤＰＣ符号を復号する信号受信装置及び方法を提供することにある。
【課題を解決するための手段】
【００２８】
前記目的を達成するために、本発明は、通信システムの信号受信装置であって、信号を受信する受信機と、前記受信信号を、ＧＦのエレメントを指数表示方式を用いて表示する非バイナリＬＤＰＣ復号方式により復号する復号器とを備えることを特徴とする。
また、本発明は、通信システムの信号受信装置における信号受信方法であって、信号を受信するステップと、前記受信信号を、指数表示方式を用いてＧＦのエレメントを表示する非バイナリＬＤＰＣ復号方式により復号するステップとを含むことを特徴とする。
【発明の効果】
【００２９】
本発明によれば、非バイナリＬＤＰＣ符号を使用する通信システムにおいて、ＧＦ(q)のエレメントを指数表示方式を用いて表示することで、非バイナリＬＤＰＣ符号を復号する復号器における検査ノード演算を遂行するために必要とするメモリ容量を最小化できる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の好適な実施形態について添付図面を参照しながら詳細に説明する。なお、下記の説明において、本発明の要旨のみを明瞭にするために、公知の機能や構成についての具体的な説明は適宜省略する。
【００３１】
本発明は、非バイナリＬＤＰＣ符号を使用する通信システムにおいて、検査ノード演算を遂行するために必要とするメモリ容量を最小化して、非バイナリＬＤＰＣ符号を復号する信号受信装置及び方法を提供する。また、本発明は、ＧＦ(q)のエレメントを指数表示方式を用いて表示することで、検査ノード演算を遂行するために必要とするメモリ容量を最小化して、非バイナリＬＤＰＣ符号を復号する信号受信装置及び方法を提供する。ＧＦ(q)において、qはＧＦの次数を示し、q＝２ｐである。
【００３２】
前述したように、従来の非バイナリＬＤＰＣ符号を使用する通信システムでは、ＧＦ(２ｐ)のエレメントを多項式表示方式を用いて表示する。ところが、多項式表示方式を用いてＧＦ(２ｐ)のエレメントを表示すると、非バイナリＬＤＰＣ符号を復号する場合、検査ノード演算を遂行するために２ｐ×２ｐ×pビットのメモリ容量が必要になる。したがって、本発明では、多項式表示方式ではない指数表示方式を用いてＧＦ(２ｐ)のエレメントを表示することで、非バイナリＬＤＰＣ符号を復号する場合、検査ノード演算を遂行するために必要とするメモリ容量が２ｐ×２ｐ×pビットのメモリ容量よりも減少される。本発明で提案する指数表示方式を用いてＧＦ(２ｐ)のエレメントを表示する方式について説明する。
【００３３】
まず、ＧＦ(２ｐ)の全てのエレメントは、{0,1,α,α2,…,αq-2}である。ＧＦ(２ｐ)の全てのエレメント{0,1,α,α2,…,αq-2}の指数のみを表示するために、全てのエレメントの各々に底(base)がαの対数(log)を取ると、{-∞,0,1,2,…,q-2}が得られ、これを用いてＧＦ(２ｐ)の全てのエレメントを表示する方式が指数表示方式である。ここで、ＧＦ(２４)を一例としてＧＦ(２ｐ)の指数表示方式について説明する。ここで、ＧＦ(２４)は、４次既約多項式p(x)=x4 +x+１から生成される。また、４次既約多項式p(x)=x4 +x+１のルートをαとする場合、ＧＦ(２４)の全てのエレメントは{0,1,α,α2,α3,…,α14}である。また、ＧＦ(２４)の全てのエレメントは係数がＧＦ(２)で定義された３次以下の多項式 a3x3+a2x2+a1x+a0で表現され得る。また、ＧＦ(２４)の全てのエレメント{0,1,α,α2,α3,…,α14}の各々に底がαの対数(log)をとると、{-∞,0,1,2,…,14}が得られる。ここで、-∞を“１５”で表示する場合、ＧＦ(２４)の全てのエレメント{0,1,α,α2,α3,…,α14}、多項式係数{a3,a2,a1,a0}及びそれに対応する十進数表現は、下記の表２に示すようである。
【００３４】
【表２】
0004402700.tif 000007
【００３５】
上記表２において、{a3, a2, a1, a0}は、指数表示方式を用いて表示された整数値を２進数に変換した値である。
表２に示すように、ＧＦ(２ｐ)のエレメントを指数表示方式を用いて表示すると、２つのＧＦエレメント間の掛け算は、単純に整数間の足し算に変換され、これは下記の式（３）のように示される。
【００３６】
【数５】
0004402700.tif 000008
【００３７】
上記式（３）において、丸付きの“×”はＧＦ(q)上における掛け算を示し、ｍｏｄはモデューロ(modulo)演算を示す。
このように、ＧＦ(q)のエレメントを指数表示方式を用いて表示する場合、非バイナリＬＤＰＣ符号を図３で説明したような和積アルゴリズムに基づいた反復復号アルゴリズムを使用して復号すると、その検査ノード演算に必要とするメモリ容量は最小化される。これを図５を参照して説明する。
【００３８】
図５は、本発明の実施形態による非バイナリＬＤＰＣ符号を復号する復号器の内部構造を示す図である。
図５の説明に先立ち、一般的に、復号器は、検査ノード処理部と変数ノード処理部とを含むが、図５には復号器の検査ノード処理部の構造のみを示したことに留意すべきである。図５によれば、復号器内のノード処理部は、第１の混合ネットワーク処理部５１０と、検査ノード処理器５４０と、第２の混合ネットワーク処理部５７０とを含む。
【００３９】
第１の混合ネットワーク処理部５１０は、例えばdc個の複数の掛け算器、すなわち掛け算器５１１−１、掛け算器５１１−２、掛け算器５１１−３、・・・、掛け算器５１１−dcのdc個の掛け算器と、dc個の複数のインターリーバ、すなわちインターリーバ５１３−１、インターリーバ５１３−２、インターリーバ５１３−３、・・・、インターリーバ５１３−dcのdc個のインターリーバと、dc個のＦＦＴユニット、すなわちＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcのdc個のＦＦＴユニットとを含む。
【００４０】
第２の混合ネットワーク処理部５７０は、例えばdc個の複数のＩＦＦＴユニット、すなわちＩＦＦＴユニット５７１−１、ＩＦＦＴユニット５７１−２、ＩＦＦＴユニット５７１−３、・・・、ＩＦＦＴユニット５７１−dcのdc個のＩＦＦＴユニットと、例えばdc個の複数のデインターリーバ、すなわちデインターリーバ５７３−１、デインターリーバ５７３−２、デインターリーバ５７３−３、・・・、デインターリーバ５７３−dcのdc個のデインターリーバと、例えばdc個の複数の掛け算器、すなわち掛け算器５７５−１、掛け算器５７５−２、掛け算器５７５−３、・・・、掛け算器５７５−dcのdc個の掛け算器とを含む。
なお、非バイナリＬＤＰＣ符号のパリティ検査行列においてj番目検査ノードを一例として検査ノード処理部の動作について説明する。ここで、j番目検査ノードの次数はdcとする。
【００４１】
まず、第１の混合ネットワーク処理部５１０に入力される入力メッセージをxi1, xi2, …, xidcとする場合、入力メッセージxi1, xi2, …, xidcは、変数ノードから検査ノードに伝えられるメッセージであり、入力メッセージxi1, xi2, …, xidcの各々は、２ｐのサイズを有するベクトルである。入力メッセージxi1, xi2, …, xidcは、掛け算器５１１−１、掛け算器５１１−２、掛け算器５１１−３、・・・、掛け算器５１１−dcに各々入力される。
【００４２】
掛け算器５１１−１、掛け算器５１１−２、掛け算器５１１−３、・・・、掛け算器５１１−dcの各々は、入力メッセージベクトルxi1, xi2, …, xidcの各々及びパリティ検査行列のエッジ値hji1, hji2,…, hjidcの各々と、ＧＦ(２ｐ)上における掛け算を遂行する。ここで、エッジ値hjiは、変数ノードi及び検査ノードjを連結するエッジが持つＧＦ(２ｐ)のエレメントを示し、変数ノードi及び検査ノードjを連結するエッジがＧＦ(２ｐ)のエレメントhjiの値を有するということは、ＧＦ(２ｐ)で定義されたパリティ検査行列のj 行i 列のエレメントがhjiであることを示す。ところが、入力メッセージはＧＦ(２ｐ)上のエレメントではなく、ＧＦ(２ｐ)上のエレメントを有する確率値を示すため、実際に掛け算器５１１−１、掛け算器５１１−２、掛け算器５１１−３、・・・、掛け算器５１１−dcの各々は、入力メッセージxi1, xi2, …, xidcの各々を置換(permutation)するものである。ここで、指数表示方式を使用する場合、ＧＦ(２ｐ)上のエレメントに対する掛け算は、上記式（３）に示すように、ｍｏｄ(ｑ−１)足し算により具現されるため、置換(permutation)はＧＦ(２ｐ)上のエレメントに対するサイズがｑ−１であるシフトレジスタで具現される。
【００４３】
掛け算器５１１−１、掛け算器５１１−２、掛け算器５１１−３、・・・、掛け算器５１１−dcの各々は、入力メッセージxi1, xi2, …, xidcの各々を置換(permutation)した後、インターリーバ５１３−１、インターリーバ５１３−２、インターリーバ５１３−３、・・・、インターリーバ５１３−dcの各々に出力される。インターリーバ５１３−１、インターリーバ５１３−２、インターリーバ５１３−３、・・・、インターリーバ５１３−dcの各々は、掛け算器５１１−１、掛け算器５１１−２、掛け算器５１１−３、・・・、掛け算器５１１−dcの各々から出力された信号を入力して、所定のインターリーブ方式によりインターリーブした後、ＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcの各々に出力される。ここで、ＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcの各々で遂行されるＦＦＴは、ＧＦ(２ｐ)のエレメントを多項式表示方式を用いて表示する場合を仮定して遂行されるため、インターリーバ５１３−１、インターリーバ５１３−２、インターリーバ５１３−３、・・・、インターリーバ５１３−dcが指数表示方式を用いて表示されたＧＦ(２ｐ)のエレメントを、更に多項式表示方式を用いて表示するためにインターリーブ動作を遂行するものである。下記の表３には、上記表１に示したような多項式表示方式と、上記表２に示したような指数表示方式とを用いて表現された十進数が示されている。
【００４４】
【表３】
0004402700.tif 000009
【００４５】
上記表３に示すように、ＧＦ(２４)を一例とする場合、インターリーバが遂行するインターリーブ情報を格納するには計１６個の単位メモリが必要であり、単位メモリは４ビットからなる。つまり、インターリーブ情報を格納するには計１６×４ビットのメモリ容量が必要になる。したがって、ＧＦ(２ｐ)において、インターリーバが遂行するインターリーブ情報を格納するには、計２ｐ個の単位メモリが必要であり、単位メモリはｐビットからなる。つまり、インターリーブ情報を格納するには、計２ｐ×pビットのメモリ容量が必要になる。
【００４６】
結果として、従来の検査ノード処理部で２ｐ×２ｐ×pビットのメモリ容量を必要とする置換(permutation)情報を、本発明のノード処理部では、ｑ−１のサイズを有するシフトレジスタと、２ｐ×pビットのメモリ容量を必要とするインターリーバーとで具現することで、必要とするメモリ容量を減少できる。
【００４７】
また、ＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcの各々は、インターリーバ５１３−１、インターリーバ５１３−２、インターリーバ５１３−３、・・・、インターリーバ５１３−dcの各々から出力された信号を入力してＦＦＴを遂行した後、検査ノード処理器５４０に出力される。ここで、ＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcの各々に入力される信号は、上記表２で定義したような指数表示方式により表現されたエレメントの確率値である。また、ＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcの各々で遂行されるＦＦＴは、一般のＦＦＴではないＧＦ(２ｐ)上で遂行されるＦＦＴを示し、これはＦＨＴと同様である。
【００４８】
検査ノード処理器５４０は、ＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcの各々から出力された信号を入力して検査ノード演算を遂行した後、その結果をＩＦＦＴユニット５７１−１、ＩＦＦＴユニット５７１−２、ＩＦＦＴユニット５７１−３、・・・、ＩＦＦＴユニット５７１−dcの各々に出力される。ＩＦＦＴユニット５７１−１、ＩＦＦＴユニット５７１−２、ＩＦＦＴユニット５７１−３、・・・、ＩＦＦＴユニット５７１−dcの各々は、検査ノード処理器５４０から出力された信号を入力してＩＦＦＴを遂行した後、デインターリーバ５７３−１、デインターリーバ５７３−２、デインターリーバ５７３−３、・・・、デインターリーバ５７３−dcの各々に出力される。ここで、ＩＦＦＴユニット５７１−１、ＩＦＦＴユニット５７１−２、ＩＦＦＴユニット５７１−３、・・・、ＩＦＦＴユニット５７１−dcの各々で遂行されるＩＦＦＴは、一般のＩＦＦＴではなく、ＧＦ(２ｐ)上で遂行されるＩＦＦＴを示す。また、ＩＦＦＴユニット５７１−１、ＩＦＦＴユニット５７１−２、ＩＦＦＴユニット５７１−３、・・・、ＩＦＦＴユニット５７１−dcの各々は、ＦＦＴユニット５１５−１、ＦＦＴユニット５１５−２、ＦＦＴユニット５１５−３、・・・、ＦＦＴユニット５１５−dcの各々の出力値が１／２ｐだけスケーリングされることを除いては、同様な構造を持つ。
【００４９】
デインターリーバ５７３−１、デインターリーバ５７３−２、デインターリーバ５７３−３、・・・、デインターリーバ５７３−dcの各々は、ＩＦＦＴユニット５７１−１、ＩＦＦＴユニット５７１−２、ＩＦＦＴユニット５７１−３、・・・、ＩＦＦＴユニット５７１−dcの各々から出力された信号を、所定のデインターリーブ方式によりデインターリーブした後、掛け算器５７５−１、掛け算器５７５−２、掛け算器５７５−３、・・・、掛け算器５７５−dcの各々に出力される。ここで、デインターリーバ５７３−１、デインターリーバ５７３−２、デインターリーバ５７３−３、・・・、デインターリーバ５７３−dcの各々で使用するデインターリーブ方式は、インターリーバ５１３−１、インターリーバ５１３−２、インターリーバ５１３−３、・・・、インターリーバ５１３−dcの各々で使用するインターリーブ方式に対応するデインターリーブ方式である。すなわち、デインターリーバ５７３−１、デインターリーバ５７３−２、デインターリーバ５７３−３、・・・、デインターリーバ５７３−dcの各々は、ＩＦＦＴユニット５７１−１、ＩＦＦＴユニット５７１−２、ＩＦＦＴユニット５７１−３、・・・、ＩＦＦＴユニット５７１−dcの各々から出力された信号が多項式表示方式を用いて表示されるので、更に指数表示方式を用いて表示するためにデインターリーブ動作を遂行する。
【００５０】
掛け算器５７５−１、掛け算器５７５−２、掛け算器５７５−３、・・・、掛け算器５７５−dcの各々は、デインターリ５７３−１、デインターリーバ５７３−２、デインターリーバ５７３−３、・・・、デインターリーバ５７３−dcの各々から出力された信号及びパリティ検査行列のエッジ値hji1, hji2,…, hjidcの逆元h-1ji1, h-1ji2,…, h-1jidcの各々と、ＧＦ(２p)上における掛け算を遂行する。ここで、掛け算器５７５−１、掛け算器５７５−２、掛け算器５７５−３、・・・、掛け算器５７５−dcも、デインターリ５７３−１、デインターリーバ５７３−２、デインターリーバ５７３−３、・・・、デインターリーバ５７３−dcから出力された信号を置換(permutation)するものであり、この置換(permutation)は、掛け算器５１１−１、掛け算器５１１−２、掛け算器５１１−３、・・・、掛け算器５１１−dcで遂行した置換(permutation)に対する逆置換(inverse permutation)である。以下、説明の便宜上、掛け算器５７５−１、掛け算器５７５−２、掛け算器５７５−３、・・・、掛け算器５７５−dcの置換(permutation)を“逆置換(inverse permutation)”と称する。よって、逆置換(inverse permutation)もＧＦ(２ｐ)上のエレメントに対するサイズがｑ−１であるシフトレジスタで具現される。置換(permutation)情報及び逆置換(inverse permutation)の何れか一方の情報は、その他方から抽出できるので、実際には何れか一つだけを格納してもよい。
【００５１】
前述したように、従来の検査ノード処理部での２ｐ×２ｐ×pビットのメモリ容量を必要とする置換(permutation)情報の格納を、ｑ−１のサイズを有するシフトレジスタ及び２ｐ×pビットのメモリ容量を必要とするインターリーバで具現し、２ｐ×２ｐ×p ビットのメモリ容量を必要とする逆置換(inverse permutation)情報の格納を、ｑ−１のサイズを有するシフトレジスタ及び２ｐ×pビットのメモリ容量を必要とするデインターリーバで具現することで、検査ノード演算を遂行するために必要とするメモリ容量を最小化きる。
【００５２】
なお、本発明の詳細な説明では具体的な実施形態について説明したが、本発明の要旨から逸脱しない範囲内で多様に変形できる。よって、本発明の範囲は、前述の実施形態に限定されるものではなく、特許請求の範囲の記載及びこれと均等なものに基づいて定められるべきである。
【図面の簡単な説明】
【００５３】
【図１】非バイナリＬＤＰＣ符号を使用する一般の通信システムの信号送信装置の構造を示す図である。
【図２】非バイナリＬＤＰＣ符号を使用する一般の通信システムの信号受信装置の構造を示す図である。
【図３】一般の非バイナリＬＤＰＣ符号でエッジの値によるメッセージベクトルの置換(permutation)を示す図である。
【図４】一般の非バイナリＬＤＰＣ符号を復号する復号器の内部構造を示す図である。
【図５】本発明の実施形態による非バイナリＬＤＰＣ符号を復号する復号器の内部構造を示す図である。
【符号の説明】
【００５４】
５１０；第１の混合ネットワーク処理部
５４０；検査ノード処理器
５７０；第２の混合ネットワーク処理部
【図１】
0004402700.tif 000014
【図２】
0004402700.tif 000015
【図３】
0004402700.tif 000016
【図４】
0004402700.tif 000017
【図５】
0004402700.tif 000018