説明

復号装置

【課題】多数の演算器を備えなくても、入力された信号の中から第1順位または第1順位の近似値を短時間で推定することができる復号装置を提供する。
【解決手段】第1変換部32は、第1の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第1変換信号を生成する。第2変換部42は、第2変換テーブルに従って、複数個の第1変換信号のビット単位の論理演算結果を表わす第2変換信号を生成する。第3変換部52は、第3の変換規則に基づいて、論理演算信号を変換して、複数個の入力信号のうちの第1順位の信号の値を表わす第3変換信号を生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、復号装置に関し、特に低密度パリティ検査符号を復号する復号装置に関する。
【背景技術】
【0002】
信号の通信システムを構築する場合には、高速通信、低消費電力、高通信品質(低ビット誤り率)等が要求される。受信符号の誤りを検出して訂正する誤り訂正技術は、これらの要求を満たす1つの技術として、無線、有線および記録システム等において幅広く利用されている。
【0003】
近年、この誤り訂正技術の1つとして、低密度パリティ検査(LDPC:Low-Density Parity-Check)符号と、sum-product復号法とが注目されている。このLDPC符号を利用する復号操作は、Chung等の非特許文献1において議論されている。この非特許文献1においては、符号化率1/2のイレギュラーLDPC符号を利用して白色ガウス通信路のシャノン(Shannon)限界まで0.04dBという復号特性が得られることが示されている。イレギュラーLDPC符号は、パリティ検査行列の行重み(行において1が立つ数)および列重み(列において1が立つ数)が、一定ではない符号を示す。行重みおよび列重みが各行および各列において一定のLDPC符号は、レギュラーLDPC符号と呼ばれる。
【0004】
この非特許文献1においては、LDPC符号をsum-product復号法に従って復号する数学的なアルゴリズムが示されているものの、その膨大な計算を具体的に行なう回路構成については何ら示していない。
【0005】
Yeo等の非特許文献2は、LDPC符号の復号装置の回路構成について検討している。この非特許文献2においては、受信系列に基づいて情報シンボルの事後確率を、トレリスに基づくMAP(最大事後確率)アルゴリズム、すなわちBCJRアルゴリズムに従って計算する。このトレリスにおいて前方向および後方向の繰返しを各状態について計算し、これらの前方向および後方向の繰返し値に基づいて、事後確率を求めている。この計算式において、加算/比較/選択/加算装置を用いて計算する。LDPC符号の算出においては、sum-product復号法に基づき、検査行列を生成し、異なるチェックノードからの値を利用して、推定値を算出するように回路を構成している。
【0006】
また、非特許文献3においては、LDPC符号とsum-product復号法を解説し、また対数領域でのmin-sum復号法が解説されている。この非特許文献3においては、加算、最小、正負の判定および正負の符号の乗算という4種類の基本演算のみでギャラガー(Gallager)のf関数に従う処理を実装することができることが示されている。
【0007】
上述の非特許文献2および3においては、パリティ検査行列を生成して1次推定語を算出するために、sum-product法に従ってギャラガー(Gallager)のf関数を用いて外部値対数比αを更新し、次いで、この外部値対数比に基づいてシンボルの事前値対数比βを算出する処理が行なわれる。このため、ギャラガー関数の演算に長時間を有し、また回路規模も増大する。
【0008】
上述の非特許文献3においては、sum-product復号法とmin-sum復号法とは等価であり、min-sum復号法を利用することにより、実装時の回路構成を簡略化することができることを示している。
【0009】
ところで、非特許文献3のmin-sum復号法を利用する場合には、パリティ検査用の検査行列を用いて最小値を算出するMin演算処理が必要となるが、各要素ごとにMin演算を行なって最小値を求めており、符号の長さが増大するのに応じて、演算対象の要素数が増大し、処理時間が長時間となる問題がある。
【0010】
これに対して、特許文献1には、Min演算において、要素間の比較を行なわずに、ビット単位の論理演算によって、入力された信号の中から最小値を算出することによって処理時間を短くできることが記載されている。
【先行技術文献】
【特許文献】
【0011】
【特許文献1】特開2007−335992号公報
【非特許文献】
【0012】
【非特許文献1】S. Y. Chung et al.,“On the Design of Low-Density Parity-Check Codes within 0.0045dB of the Shannon Limit”IEEE COMUNICATIONS LETTERS, VOL.5, No.2, Feb. 2001, pp.58-60
【非特許文献2】E. Yeo et al.,“VLSI Architectures for Iterative Decoders inMagnetic Recording Channels”IEEE Trans. Magnetics, Vol,37, No.2, March 2001, pp.748-755
【非特許文献3】和田山正、「低密度パリティ検査符号とその復号法について」、信学技報、MR2001−83、2001年12月
【発明の概要】
【発明が解決しようとする課題】
【0013】
しかしながら、この特許文献1による最小値の推定では、ビット単位の論理演算のために多数の演算器が必要となり、装置の規模が大きくなるという問題がある。
【0014】
それゆえに、本発明の目的は、多数の演算器を備えなくても、入力された信号の中から第1順位または第1順位の近似値を短時間で推定することができる復号装置を提供することである。
【課題を解決するための手段】
【0015】
上記課題を解決するために、本発明は、所定数の信号単位で復号を行なう復号装置であって、N個(Nは2以上の自然数)の尤度を表わす入力信号の絶対値を表わす絶対値信号のうち、1個を除いた(N−1)個の絶対値信号の最大または最小である第1順位の信号の値または第1順位の信号の近似値を推定する第1順位推定部と、第1順位推定部で推定された信号の値と1単位内の信号の符号とから新たな信号を生成して、新たな信号に基づいて1単位内の信号の推定信号系列を生成する受信信号推定部とを備え、第1順位推定部は、第1の変換規則に基づいて、N個の絶対値信号それぞれを変換して、N個の第1変換信号を生成する第1変換部と、第2の変換規則に基づいて、N個の第1変換信号を変換して、N個の第2変換信号を生成する第2変換部とを備え、第2の変換規則では、N個の第1変換信号のうちの1個を除いて(N−1)個の第1変換信号のビット単位の所定の論理演算の結果を表わす第2変換信号が生成され、第3の変換規則に基づいて、第2変換信号を変換して、(N−1)個の絶対値信号のうちの第1順位の信号の値または第1順位の信号の近似値を表わす第3変換信号を生成する第3変換部とを含み、第2変換部は、除かれる1個がそれぞれ相違するN種類の(N−1)個の第1変換信号を用いて、N個の第2変換信号を生成し、第3変換部は、N個の第2変換信号を変換して、N個の第3変換信号を生成し、受信信号推定部は、N個の第3変換信号に基づいてN個の新たな信号を生成し、第2変換部は、ビット単位の所定の論理演算の少なくとも一部について、入力と出力との関係を表わした第1テーブルを用いて、第2変換信号の各ビットを生成する。
【0016】
好ましくは、第1テーブルは、N個の1ビット入力とN個の1ビット出力との対応を定め、かつN個の出力の各々が、N個の入力のうちの対応する1個の入力以外の他のすべての入力についての所定の論理演算の結果を表わし、第2変換部は、N個の第1変換信号の各ビットを第1テーブルのN個の入力として用い、入力に対する第1テーブルのN個の出力をN個の第2変換信号の各ビットとして生成する。
【0017】
好ましくは、第1テーブルは、M個の第1の1ビット入力および1個の第2の1ビット入力と、M個の1ビット出力との対応を定め、かつM個の出力の各々が、M個の第1の入力のうちの対応する1個の入力以外の他のすべての入力についての所定の論理演算の結果を表わし、ただし、Mは1以上、(N−1)以下の自然数であり、第2変換部は、N個の第1変換信号のうちの(N−M)個の第1変換信号のビット単位の所定の論理演算を実行する少なくとも1つの第1の論理演算器をさらに備え、第2変換部は、少なくとも1つの第1の論理演算器の論理演算結果の各ビットをテーブルの1個の第2の入力とし、かつN個の第1変換信号のうちの残りのM個の第1変換信号の各ビットを第1テーブルのM個の第1の入力として用いることによって、M個の第2変換信号の各ビットを生成する。
【0018】
好ましくは、第1の変換規則では、絶対値信号の値と第1変換信号の値が1対1に対応し、第3の変換規則において、第2変換信号に対応する第3変換信号の値は、第1の変換規則において、第2変換信号と同一の値の第1変換信号に対応する絶対値信号の値と同一であり、第1の変換規則では、絶対値信号の取り得る値の範囲は0からA(Aは1以上の自然数)までであり、かつ第1変換信号の取り得る値はAビットで表わされ、第1の変換規則では、絶対値信号の値がk(0≦k≦A)のときに、第1変換信号の下位のk個のビットの値が第1の論理値であり、かつその他のビットの値が第2の論理値であるように変換され、第2変換部は、ビット単位の所定の論理演算の結果として、各ビットにつき、複数個の第1変換信号のビットの値がすべて第1の論理値のときには第1の論理値を出力し、それ以外のときには第2の論理値を出力する。
【0019】
好ましくは、第1の変換規則では、絶対値信号の値と第1変換信号の値が1対1に対応し、第3の変換規則において、第2変換信号に対応する第3変換信号の値は、第1の変換規則において、第2変換信号と同一の値の第1変換信号に対応する絶対値信号の値と同一であり、第1の変換規則では、絶対値信号の取り得る値は大きい順または小さい順に順序づけられる第1番目から第A番目までのA種類(Aは、2以上の自然数)であり、かつ第1変換信号の取り得る値はBビット(B≧(A−1))で表わされ、第1の変換規則では、取り得る値のうちの第K番目の絶対値信号に対応する第1変換信号のビットのうち、値が第1の論理値であるビットが存在する場合に、取り得る値のうちの第(K+1)番目の絶対値信号に対応する第1変換信号については、値が第1の論理値であるビットの位置は、第K番目の絶対値信号に対応する第1変換信号のビットのうちの値が第1の論理値であるビットの位置と、さらに少なくとも1つのビットの位置とからなり、第2変換部は、ビット単位の所定の論理演算の結果として、各ビットにつき、複数個の第1変換信号のビットの値がすべて第1の論理値のときには第1の論理値を出力し、それ以外のときには第2の論理値を出力する、ただし、Kは、1以上かつ(A−1)以下のすべての自然数である。
【0020】
好ましくは、第1の変換規則では、絶対値信号の1個または複数個が第1変換信号の1個に対応し、第3の変換規則において、第2変換信号に対応する第3変換信号の値は、第1の変換規則において第2変換信号と同一の値の第1変換信号に対応する絶対値信号が1個のときには、1個の絶対値信号の値と同一であり、第2変換信号と同一の値の第1変換信号に対応する絶対値信号が複数個のときには、複数個の絶対値信号のうちの1つの値と同一であり、第1の変換規則では、絶対値信号の取り得る値はAビット(Aは1以上の自然数)で表わされ、かつ第1変換信号の取り得る値はAビットで表わされ、第1の変換規則では、絶対値信号のビットのうち、値が1である最も上位ビットが最下位ビットからk番目(1≦k≦A)のビットのときに、第1変換信号の下位のk個のビットの値が第1の論理値であり、かつその他のビットの値が第2の論理値であるように変換され、絶対値信号のビットのうち、すべてのビットの値が0のときには、第1変換信号のすべてのビットの値が第2の論理値であるように変換され、第2変換部は、ビット単位の所定の論理演算の結果として、各ビットにつき、複数個の第1変換信号のビットの値がすべて第1の論理値のときには第1の論理値を出力し、それ以外のときには第2の論理値を出力する。
【0021】
好ましくは、第3の変換規則では、論理演算信号の取り得る値はAビットで表わされ、かつ第2変換信号の取り得る値はAビットで表わされ、第3の変換規則では、第2変換信号のビットのうち、値が第1の論理値である最も上位ビットが最下位ビットからk番目(1≦k≦A)のビットのときに、第3変換信号の最下位ビットからk番目のビットの値が1であり、かつその他のビットの値が0であるように変換され、第2変換信号のビットのうち、すべてのビットの値が第2の論理値のときには、第3変換信号のすべてのビットの値が0であるように変換される。
【0022】
好ましくは、N個の尤度を表わす入力信号の符号ビットのうち1個を除いた(N−1)個の符号ビットの排他的論理和演算の結果を表わす符号ビットを生成する符号生成部をさらに備え、符号生成部は、除かれる1個がそれぞれ相違するN種類の(N−1)個の符号ビットを用いて、N個の符号ビットを生成し、受信信号推定部は、N個の第3変換信号と生成されたN個の符号ビットに基づいて、N個の新たな信号を生成し、符号生成部は、排他的論理和演算の少なくとも一部について、入力と出力との関係を表わした第2テーブルを用いて、符号ビットを生成する。
【0023】
好ましくは、第2テーブルは、N個の1ビット入力とN個の1ビット出力との対応を定め、かつN個の出力の各々が、N個の入力のうちの対応する1個の入力以外の他のすべての入力の排他的論理和演算の結果を表わし、符号生成部は、N個の入力信号の符号ビットを第2テーブルのN個の入力として用い、入力に対する第2テーブルのN個の出力をN個の符号ビットとして生成する。
【0024】
好ましくは、第2テーブルは、M個の第1の1ビット入力および1個の第2の1ビット入力と、M個の1ビット出力との対応を定め、かつM個の出力の各々が、M個の第1の入力のうちの対応する1個の入力以外の他のすべての入力の排他的論理和演算の結果を表わし、ただし、Mは1以上、(N−1)以下の自然数であり、符号生成部は、N個の入力信号のうちの(N−M)個の入力信号の符号ビットの排他的論理和演算を実行する少なくとも1つの第2の論理演算器をさらに備え、符号生成部は、少なくとも1つの第2の論理演算器の排他的論理和演算結果を第2テーブルの1個の第2の入力とし、かつN個の入力信号のうちの残りのM個の入力信号の符号ビットを第2テーブルのM個の第1の入力として用いることによって、M個の符号ビットを生成する。
【発明の効果】
【0025】
本発明の復号装置によれば、多数の演算器を備えなくても、入力された信号の中から第1順位または第1順位の近似値を短時間で推定することができる。
【図面の簡単な説明】
【0026】
【図1】通信システムの構成の一例を示す図である。
【図2】通信路が光ファイバの場合の変調器2よび復調器の出力信号の対応関係を一覧にして示す図である。
【図3】復号化器の構成を概略的に示す図である。
【図4】行処理部の構成を表わす図である。
【図5】第m行処理部の構成を示す図である。
【図6】第1順位推定部22の構成を表わす図である。
【図7】第1の実施形態の第1変換テーブルの例を表わす図である。
【図8】第1の実施形態の第2変換テーブルの例を表わす図である。
【図9】第1の実施形態の第3変換テーブル53の例を表わす図である。
【図10】第1変換部の具体的な構成を表わす図である。
【図11】第1の実施形態の第2変換部の具体的な構成を表わす図である。
【図12】第3変換部の具体的な構成を表わす図である。
【図13】第1の実施形態の符号生成部の構成を表わす図である。
【図14】第1の実施形態の第4変換テーブルの構成を表わす図である。
【図15】復号プログラムの処理手順を表わすフローチャートである。
【図16】第1の実施形態の変形例2の第1変換テーブルの例を表わす図である。
【図17】第1の実施形態の変形例2の第2変換テーブルの例を表わす図である。
【図18】第1の実施形態の変形例2の第3変換テーブルの例を表わす図である。
【図19】第1の実施形態の変形例3の第1変換テーブルの例を表わす図である。
【図20】第1の実施形態の変形例3の第3変換テーブルの例を表わす図である。
【図21】第1の実施形態の変形例4の第1変換テーブルの例を表わす図である。
【図22】第1の実施形態の変形例4の第3変換テーブルの例を表わす図である。
【図23】第1の実施形態の変形例5の第1変換テーブルの例を表わす図である。
【図24】第1の実施形態の変形例5の第3変換テーブルの例を表わす図である。
【図25】第2の実施形態の第2変換部の構成を表わす図である。
【図26】第2の実施形態の第2変換テーブルの例を表わす図である。
【図27】第2の実施形態の第4変換部の構成を表わす図である。
【図28】第2の実施形態の第4変換テーブルの例を表わす図である。
【図29】第2の実施形態の変形例の第2変換部の第1ビット変換部の構成を表わす図である。
【図30】第2の実施形態の変形例の第2変換テーブル93の例を表わす図である。
【図31】変形例1の符号生成部を表わす図である。
【図32】変形例2の符号生成部を表わす図である。
【図33】変形例1の第1順位推定部を表わす図である。
【図34】変形例2の第1順位推定部を表わす図である。
【発明を実施するための形態】
【0027】
[第1の実施形態]
図1は、この発明に従う復号装置を用いる通信システムの構成の一例を示す図である。図1において、通信システムは、送信側において、送信情報に誤り訂正用の冗長ビットを付加して送信符号を生成する符号化器1と、この符号化器1からの(K+M)(=N)ビットの符号を所定の方式に従って変調して通信路3へ出力する変調器2とを含む。
【0028】
変調器2は、この通信路3の構成に応じて、振幅変調、位相変調、コード変調、周波数変調または直行周波数分割多重変調などの変調を行なう。たとえば、通信路3が、光ファイバの場合、変調器2においては、レーザダイオードの輝度を送信情報ビット値に応じて変更させることにより、光の強度変調(一種の振幅変調)を行なっている。たとえば、送信信号ビットが“0”の場合には、このレーザダイオードの発光強度を強くして“+1”として送信し、また送信信号ビットが“1”の場合、レーザダイオードの発光強度を弱くして、“−1”に変換して送信する。
【0029】
受信部においては、通信路3を介して送信された変調信号に復調処理を施して、(K+M)ビットのデジタル符号を復調する復調器4と、この復調器4からの(K+M)ビットの符号にパリティ検査行列演算処理を施して元のKビットの情報を再生する復号化器5が設けられる。
【0030】
復調器4は、この通信路3における送信形態に応じて復調処理を行なう。たとえば、振幅変調、位相変調、コード変調、周波数変調および直行周波数分割多重変調等の場合、復調器4において、振幅復調、位相復調、コード復調、および周波数復調等の処理が行なわれる。
【0031】
図2は、通信路3が光ファイバの場合の変調器2および復調器4の出力信号の対応関係を一覧にして示す図である。図2において、上述のように、通信路3が光ファイバの場合、変調器2においては、送信信号が“0”のときには、送信用のレーザダイオード(発光ダイオード)の発光強度を強くし、“1”を出力し、また送信信号ビットが“1”のときには、この発光強度を弱くしてビット“−1”を送信する。
【0032】
この通信路3における伝送損失等により、復調器4に伝達される光強度は、最も強い強度から最も弱い強度までの間のアナログ的な強度分布を有する。復調器4においては、この入力された光信号を量子化処理(アナログ/デジタル変換)を行なって、この受光レベルを検出する。図2においては、8段階に受光レベルが量子化された場合の受信信号強度を示す。すなわち、受光レベルが信号“7”のときには、発光強度がかなり強く、受光レベルが“0”のときには、光強度がかなり弱い状態である。各受光レベルは、符号付き信号に対応づけられ、復調器4から出力される。この復調器4の出力は、受光レベルが“7”のときには信号“3”が出力され、受光レベルが“0”のときには、信号“−4”が出力される。したがってこの復調器4からは、1ビットの受信信号に対し、多値量子化された信号が出力される。
【0033】
復号化器5は、この復調器4から与えられた(K+M)ビットの受信情報(各ビットは、多値情報を含む)を入力し、後に詳細に説明する、min-sum復号法に従ってLDPCパリティ検査行列を適用して、元のKビットの情報を復元する。パリティ検査行列の行の数をM、列の数をN、行重みをSとする。ここで、行重みとは、行方向の1の数である。
【0034】
図3は、この発明に従う復号化器5の構成を概略的に示す図である。この図3においては、復調器4および通信路3も併せて示す。復調器4は、通信路3から与えられた信号を復調する復調回路4aと、この復調回路4aにより生成されたアナログ復調信号をデジタル信号に変換するアナログ/デジタル変換回路4bを含む。このアナログ/デジタル変換回路4bの出力信号Xnが復号化器5へ与えられる。この復号化器5へ与えられる信号Xnは、L値(L≧2)の信号である。以下、信号Xnは、多値量子化信号であるため、シンボルと称す。復号化器5は、この入力シンボルXn系列に対してmin-sum復号法に従って復号処理を行なって符号ビットCnを生成する。
【0035】
復号化器5は、復調器4からの復調シンボルXnの対数尤度比λnを生成する対数尤度比算出部10と、パリティ検査行列の行処理を行なう行処理部12と、パリティ検査行列の列処理を行なう列処理部14と、対数尤度比算出部10からの対数尤度比λnと行処理部12の出力ビット(外部値対数比)αmnとに従って符号を生成するループ判定部16を含む。
【0036】
対数尤度比算出部10は、この受信信号のノイズ情報と独立に、対数尤度比λnを生成する。通常、ノイズ情報を考慮した場合、この対数尤度比λnは、Xn/2×σで与えられる。ここで、σは、ノイズの分散を示す。しかしながら、本実施の形態においては、この対数尤度比算出部10は、バッファ回路または定数乗算回路で形成され、対数尤度比λnは、Xn×fで与えられる。ここで、fは非ゼロの正の数である。このノイズ情報を利用せずに、対数尤度比を算出することにより、回路構成が簡略化され、また計算処理も簡略化される。min-sum復号方法においては、検査行列の処理において、最小値を利用して演算を行なうため、信号処理において線形性が維持される。このため、ノイズ情報に従って出力信号を正規化するなどの処理は不要である。
【0037】
行処理部12および列処理部14は、それぞれ、次式(1)および(2)に従って、演算処理を行ない、パリティ検査行列の行の各要素についての処理(行処理)および列についての各要素についての処理(列処理)を実行する。行処理部12において、列処理部14から与えられる事前値対数比βmnと対数尤度比λnとに従って外部値対数比αmnを更新する。
【0038】
【数1】

【0039】
ここで、上式(1)および(2)それぞれにおいて、n′∈A(m)\nおよびm′∈B(n)\mは、自身を除く要素を意味する。外部値対数比αmnについては、n′≠nであり、事前値対数比βmnについては、m′≠mである。また、αおよびβの行列内の位置を示す添え字“mn”は、通常は下付文字で示されるが、本明細書においては、読みやすさのために、「横並びの文字」で示す。
【0040】
また、関数sign(x)は、次式(3)で定義される。
【0041】
【数2】

【0042】
ここで、関数minは、最小値を求める演算を示す。
また、集合A(m)およびB(n)は、2元M・N行列H=[Hmn]を復号対象のLDPC符号の検査行列とした場合、集合[1,N]={1,2,…,N}の部分集合である。
【0043】
A(m)={n:Hmn=1} …(4)
B(n)={m:Hmn=1} …(5)
すなわち、部分集合A(m)は、検査行列Hの第m行目において1が立っている列インデックスの集合を意味し、部分集合B(n)は、検査行列Hの第n列目において1が立っている行インデックスの集合を示す。
【0044】
ループ判定部16は、これらの行処理部12および列処理部14における演算処理結果に基づいて、1次推定語を生成し、これらの1次推定語が符号語を構成しているかを検査する。このパリティ検査時において、シンドロームが“0”とならない場合には、再び処理を繰返し実行する。この処理の繰返し回数が所定値に到達すると、そのときの1次推定語を符号語として出力する。ループ判定部16は、この行処理部12で生成される外部値対数比αmnと対数尤度比算出部10からの対数尤度比λnとを用いて、複数の符号で構成される符号語を生成する。符号の数は、検査行列の列の数に対応する。
【0045】
これらの求められた外部値対数比αmnは、図3に示す列処理部14およびループ判定部16へ供給される。
【0046】
列処理部14は、先の式(2)において示された演算処理を行ない、検査行列Hの各行において生成された外部値対数比を用いて、自身を除く行以外の対応の列の“1”が立っている位置の外部値対数比を加算する。
【0047】
図4は、行処理部12の構成を表わす図である。
図4を参照して、行処理部12は、第1行処理部18−1〜第M行処理部18−Mを有する。
【0048】
図5は、第m行処理部18−mの構成を示す図である。他の行の行処理部もこれと同様である。
【0049】
図5を参照して、第m行処理部18−mは、加算部20と、符号生成部21と、第1順位推定部22と、結合部23とを備える。
【0050】
加算部20は、SL個の信号{βmn′:n′はHmn′=1を満たす、SL個の異なる数である}を受けて、それらと対数尤度比λn′とを加算して、加算結果{(λn′+βmn′):n′はHmn′=1を満たす、SL個の異なる数である}を出力する。ここでは、行重みSLは「4」であり、Hmn′=1を満たすn′は、n1、n2、n3、n4として説明する。すなわち、A(m)={n1,n2,n3,n4}とする。
【0051】
符号生成部21は、SL(=4)個の信号{(λn′+βmn′):n′=n1、n2、n3、n4}の符号を表わすSL個の最上位ビット、すなわち符号ビット(U1、U2、U3、U4)に基づいて、式(1)の符号部分(これをSmnとする。ただし、n=n1、n2、n3、n4である)の計算を行なう。以下では、{Smn:n=n1、n2、n3、n4}を(V1、V2、V3、V4)として説明する。
【0052】
第1順位推定部22は、SL(=4)個の信号{(λn′+βmn′):n′=n1、n2、n3、n4}のSL個の最上位ビット以外の残りのビット、すなわち絶対値を表わす信号(x1、x2、x3、x4)に基づいて、式(1)の絶対値部分(これをRmnとする。ただし、n=n1、n2、n3、n4である)の計算を行なう。以下では、{Rmn:n=n1、n2、n3、n4}を(w1、w2、w3、w4)として説明する。
【0053】
結合部23は、符号生成部21から出力されるSmn(n=n1、n2、n3、n4)と第1順位推定部22から出力されるRmn(n=n1、n2、n3、n4)のそれぞれから、外部値対数比αmnを生成して出力する。具体的には、結合部23は、Smnを正負を示す符号として取り扱い、Rmnをαmnの絶対値として、外部値対数比αmnを出力する。
【0054】
図6は、第1順位推定部22の構成を表わす図である。
図6を参照して、この第1順位推定部22は、SL個(ここでは、SL=4)の絶対値信号のうち1個を除いた(SL−1)個の絶対値信号の最小値を示す信号を出力する装置である。第1順位推定部22は、取り除く1個が相違するSL個の最小値を示す信号を出力する。
【0055】
第1順位推定部22は、第1変換部32と、第2変換部42と、第3変換部52とを備える。
【0056】
第1変換部22は、4個の絶対値信号x1、x2、x3、x4を受けて、第1変換規則を定めた第1変換テーブルで規定される対応関係で変換した第1変換信号y1、y2、y3、y4を生成する。
【0057】
図7は、第1の実施形態の第1変換テーブル33の例を表わす図である。
図7を参照して、第1変換テーブル33では、絶対値信号の値と第1変換信号の値が1対1で対応する。この第1変換テーブル33では、絶対値信号は5ビットで表され、取り得る値の範囲が0〜Lであり、第1変換信号の取り得る値はLビットで表わされる。図7では、L=31であとしたが、Lは1以上の自然数であれば、どのような値でもよい。図7において、絶対値信号および第1変換信号は、それぞれ最下位ビットを最も左側に示している。本明細書における以下の説明でも、これと同様に、最下位ビットを左側に記す。
【0058】
第1変換テーブル33によれば、絶対値信号の値がk(0≦k≦31)のときに、第1変換信号の下位のk個のビットが「1」となり、それ以外のビットが「0」となる。たとえば、絶対値信号の値が「0」ときには、第1変換信号のすべてのビットが「0」となる。絶対値信号の値が「1」のときには、第1変換信号の最下位ビットのみが「1」となる。絶対値信号の値が「2」のときには、第1変換信号の下位の2個のビットのみが「1」となる。
【0059】
第2変換部42は、第1変換部42から出力される4個の第1変換信号y1、y2、y3、y4を受けて、第2変換規則を定めた第2変換テーブルで規定される対応関係で変換した4個の第2変換信号z1、z2、z3、z4を生成する。第2の変換規則では、4個の第1変換信号のうちの1個を除いて3個の第1変換信号のビット単位の論理積の結果を表わす第2変換信号が生成される。第2変換部は、除かれる1個がそれぞれ相違する4種類の3個の第1変換信号を用いて、4個の第2変換信号を生成する。
【0060】
図8は、第1の実施形態の第2変換テーブル43の例を表わす図である。
図8を参照して、第2変換テーブル43では、4個の1ビット入力(入力1、入力2、入力3、入力4)と4個の1ビット出力(出力1、出力2、出力3、出力4)との対応関係を定める。具体的には、出力1は、入力1を除く3個の入力(入力2、入力3、入力4)のビット論理積を表わす。出力2は、入力2を除く3個の入力(入力1、入力3、入力4)のビット論理積を表わす。出力3は、入力3を除く3個の入力(入力1、入力2、入力4)のビット論理積を表わす。出力4は、入力4を除く3個の入力(入力1、入力2、入力3)のビット論理積を表わす。ここで、ビット論理積とは、入力がすべて第1の論理値のときには第1の論理値を出力し、入力がそれ以外のときには第2の論理値を出力する演算の一形態である。
【0061】
第2変換部42は、4個の第1変換信号y1、y2、y3、y4の各ビットを第2変換テーブル43の4個の入力として用い、この入力に対する第2変換テーブル43の4個の出力を4個の第2変換信号z1、z2、z3、z4の各ビットとして生成する。
【0062】
第3変換部52は、第2変換部42から出力される4個の第2変換信号z1、z2、z3、z4を受けて、第3変換規則を定めた第3変換テーブルで規定される対応関係で変換した第3変換信号w1、w2、w3、w4を生成して出力する。ここで、第3変換信号w1は、3個の絶対値信号x2、x3、x4のうちの値が最小である信号であり、第3変換信号w2は、3個の絶対値信号x1、x3、x4のうちの値が最小である信号であり、第3変換信号w3は、3個の絶対値信号x1、x2、x4のうちの値が最小である信号であり、第3変換信号w4は、3個の絶対値信号x1、x2、x3のうちの値が最小である信号である。
【0063】
図9は、第1の実施形態の第3変換テーブル53の例を表わす図である。
図9を参照して、第2変換信号(論理積信号)と第3変換信号との対応関係は、図7の第1変換テーブル33の対応関係を逆にしたものである。すなわち、第3変換テーブル53において第2変換信号に対応する第3変換信号の値は、第1変換テーブル33においてその第2変換信号と同一の値の第1変換信号に対応する絶対値信号の値と同一である。
【0064】
第3変換テーブル53によれば、第2変換信号の下位のk個(0≦k≦31)のビットが「1」で、それ以外のビットが「0」のときに、第3変換信号の値がkとなる。たとえば、第2変換信号のすべてのビットが「0」のときには、第3変換信号の値が「0」となる。第2変換信号の最下位ビットのみが「1」のときには、第3変換信号の値が「1」となる。第2変換信号の下位の2個のビットのみが「1」のときには、第3変換信号の値が「2」となる。
【0065】
図10は、第1変換部32の具体的な構成を表わす図である。
図10を参照して、第1変換部32は、4個の絶対値信号の変換を同時に並列して行なう。第1変換部32は、絶対値信号の個数分の第1メモリ部で構成される。ここでは、絶対値信号の個数が4個であるので、第1変換部32は、第1メモリ部(領域1)31−1と、第1メモリ部(領域2)31−2と、第1メモリ部(領域3)31−3と、第1メモリ部(領域4)31−4とを含む。
【0066】
第1メモリ部(領域1)31−1では、5ビットの絶対値信号x1がアドレスとして用いられ、絶対値信号x1で指定される領域にLビットの第1変換信号y1の値が格納されている。絶対値信号x1と第1変換信号y1との関係は、図7の第1変換テーブル33にしたがう。第1メモリ部(領域1)31−1は、5ビットの絶対値信号x1を受けて、絶対値信号x1に対応するLビットの第1変換信号y1(={y1L、・・・、y12、y11})を出力する。
【0067】
第1メモリ部(領域2)31−2では、5ビットの絶対値信号x2がアドレスとして用いられ、絶対値信号x2で指定される領域にLビットの第1変換信号y2の値が格納されている。絶対値信号x2と第1変換信号y2との関係は、図7の第1変換テーブル33にしたがう。第1メモリ部(領域2)31−2は、5ビットの絶対値信号x2を受けて、絶対値信号x2に対応するLビットの第1変換信号y2(={y2L、・・・、y22、y21})を出力する。
【0068】
第1メモリ部(領域3)31−3では、5ビットの絶対値信号x3がアドレスとして用いられ、絶対値信号x3で指定される領域にLビットの第1変換信号y3の値が格納されている。絶対値信号x3と第1変換信号y3との関係は、図7の第1変換テーブル33にしたがう。第1メモリ部(領域3)31−3は、5ビットの絶対値信号x3を受けて、絶対値信号x3に対応するLビットの第1変換信号y3(={y3L、・・・、y32、y31})を出力する。
【0069】
第1メモリ部(領域4)31−4では、5ビットの絶対値信号x4がアドレスとして用いられ、絶対値信号x4で指定される領域にLビットの第1変換信号y4の値が格納されている。絶対値信号x4と第1変換信号y4との関係は、図7の第1変換テーブル33にしたがう。第1メモリ部(領域4)31−4は、5ビットの絶対値信号x4を受けて、絶対値信号x4に対応するLビットの第1変換信号y4(={y4L、・・・、y42、y41})を出力する。
【0070】
図11は、第1の実施形態の第2変換部42の具体的な構成を表わす図である。
図11を参照して、第2変換部42は、4個の第1変換信号の変換を同時に並列して行なう。第2変換部42は、第1変換信号のビット数L個の変換部で構成される。すなわち、第1変換部42は、第1ビット変換部45−1と、第2ビット変換部45−2と、・・・、第Lビット変換部45−Lとを含む。
【0071】
第1ビット変換部45−1は、第2メモリ部(領域1)41−1を含む。第2メモリ部(領域1)41−1では、4個の第1変換信号y1、y2、y3、y4の第1ビット目である4ビットの信号(y41、y31、y21、y11)がアドレスとして用いられ、当該4ビットの信号に対応する領域に第2変換信号z1、z2、z3、z4の第1ビット目である4ビットの信号(z41、z31、z21、z11)の値が格納されている。4ビットの信号(y41、y31、y21、y11)と4ビットの信号(z41、z31、z21、z11)との関係は、図8の第2変換テーブル43にしたがう。第2メモリ部(領域1)41−1は、4ビットの信号(y41、y31、y21、y11)を受けて、その信号に対応する4ビットの信号(z41、z31、z21、z11)を出力する。
【0072】
第2ビット変換部45−2は、第2メモリ部(領域2)41−2を含む。第2メモリ部(領域2)41−2では、4個の第1変換信号y1、y2、y3、y4の第2ビット目である4ビットの信号(y42、y32、y22、y12)がアドレスとして用いられ、当該4ビットの信号に対応する領域に第2変換信号z1、z2、z3、z4の第2ビット目である4ビットの信号(z42、z32、z22、z12)の値が格納されている。4ビットの信号(y42、y32、y22、y12)と4ビットの信号(z42、z32、z22、z12)との関係は、図8の第2変換テーブル43にしたがう。第2メモリ部(領域1)41−2は、4ビットの信号(y42、y32、y22、y12)を受けて、その信号に対応する4ビットの信号(z42、z32、z22、z12)を出力する。
【0073】
第Lビット変換部45−Lは、第2メモリ部(領域L)41−Lを含む。第2メモリ部(領域L)41−Lでは、4個の第1変換信号y1、y2、y3、y4の第Lビット目である4ビットの信号(y4L、y3L、y2L、y1L)がアドレスとして用いられ、当該4ビットの信号に対応する領域に第2変換信号z1、z2、z3、z4の第Lビット目である4ビットの信号(z4L、z3L、z2L、z1L)の値が格納されている。4ビットの信号(y4L、y3L、y2L、y1L)と4ビットの信号(z4L、z3L、z2L、z1L)との関係は、図8の第2変換テーブル43にしたがう。第2メモリ部(領域L)41−Lは、4ビットの信号(y4L、y3L、y2L、y1L)を受けて、その信号に対応する4ビットの信号(z4L、z3L、z2L、z1L)を出力する。
【0074】
図12は、第3変換部52の具体的な構成を表わす図である。
図12を参照して、第3変換部52は、4個の第2変換信号(論理積信号)の変換を同時に並列して行なう。第3変換部52は、絶対値信号の個数分の第3のメモリ部で構成される。ここでは、絶対値信号の個数が4個であるので、第3変換部52は、第3メモリ部(領域1)51−1と、第3メモリ部(領域2)51−2と、第3メモリ部(領域3)51−3と、第3メモリ部(領域4)51−4とを含む。
【0075】
第3メモリ部(領域1)51−1では、Lビットの第2変換信号z1がアドレスとして用いられ、第2変換信号z1で指定される領域に5ビットの第3変換信号w1の値が格納されている。第2変換信号z1と第3変換信号w1との関係は、図9の第3変換テーブル53にしたがう。第3メモリ部(領域1)51−1は、Lビットの第2変換信号z1を受けて、第2変換信号z1に対応する5ビットの第3変換信号w1(={w15、・・・、w12、w11})を出力する。
【0076】
第3メモリ部(領域2)51−2では、Lビットの第2変換信号z2がアドレスとして用いられ、第2変換信号z2で指定される領域に5ビットの第3変換信号w2の値が格納されている。第2変換信号z2と第3変換信号w2との関係は、図9の第3変換テーブル53にしたがう。第3メモリ部(領域2)51−2は、Lビットの第2変換信号z2を受けて、第2変換信号z2に対応する5ビットの第3変換信号w2(={w25、・・・、w22、w21})を出力する。
【0077】
第3メモリ部(領域3)51−3では、Lビットの第2変換信号z3がアドレスとして用いられ、第2変換信号z3で指定される領域に5ビットの第3変換信号w3の値が格納されている。第2変換信号z3と第3変換信号w3との関係は、図9の第3変換テーブル53にしたがう。第3メモリ部(領域3)51−3は、Lビットの第2変換信号z3を受けて、第2変換信号z3に対応する5ビットの第3変換信号w3(={w35、・・・、w32、w31})を出力する。
【0078】
第3メモリ部(領域4)51−4では、Lビットの第2変換信号z4がアドレスとして用いられ、第2変換信号z4で指定される領域に5ビットの第3変換信号w4の値が格納されている。第2変換信号z4と第3変換信号w4との関係は、図9の第3変換テーブル53にしたがう。第3メモリ部(領域4)51−4は、Lビットの第2変換信号z4を受けて、第2変換信号z4に対応する5ビットの第3変換信号w4(={w45、・・・、w42、w41})を出力する。
【0079】
図13は、第1の実施形態の符号生成部21の構成を表わす図である。
図13を参照して、この符号生成部21は、SL個(ここでは、SL=4)の符号ビットのうち1個を除いた(SL−1)個の符号ビットの排他的論理和演算の結果を表わす符号ビットを出力する装置である。符号生成部21は、取り除く1個が相違するSL個の符号ビットを出力する。
【0080】
第4変換部62は、4個の符号ビットU1、U2、U3、U4を受けて、第4変換規則を定めた第4変換テーブル63で規定される対応関係で変換した4個の符号ビットV1、V2、V3、V4を生成する。
【0081】
第4の変換規則では、4個の符号ビットうちの1個を除いた3個の符号ビットの排他的論理和演算の結果を表わす符号ビットが生成される。第4変換部62は、除かれる1個がそれぞれ相違する4種類の3個の符号ビットを用いて、4個の符号ビットV1、V2、V3、V4を生成する。
【0082】
具体的には、第4変換部62は、第4メモリ部61を含む。第4メモリ部61では、4ビットの信号(U4、U3、U2、U1)がアドレスとして用いられ、当該4ビットの信号に対応する領域に4ビットの信号(V4、V3、V2、V1)の値が格納されている。
【0083】
4ビットの信号(U4、U3、U2、U1)と4ビットの信号(V4、V3、V2、V1)との関係は、第4変換テーブル63にしたがう。第4メモリ部61は、4ビットの信号(U4、U3、U2、U1)を受けて、その信号に対応する4ビットの信号(V4、V3、V2、V1)を出力する。
【0084】
図14は、第1の実施形態の第4変換テーブル63の例を表わす図である。
図14を参照して、第4変換テーブル63では、4個の1ビット入力(入力1、入力2、入力3、入力4)と4個の1ビット出力(出力1、出力2、出力3、出力4)との対応関係を定める。具体的には、出力1は、入力1を除く3個の入力(入力2、入力3、入力4)の排他的論理和を表わす。出力2は、入力2を除く3個の入力(入力1、入力3、入力4)の排他的論理和を表わす。出力3は、入力3を除く3個の入力(入力1、入力2、入力4)の排他的論理和を表わす。出力4は、入力4を除く3個の入力(入力1、入力2、入力3)の排他的論理和を表わす。
【0085】
第4変換部62は、4個の符号ビットを第4変換テーブル63の4個の入力として用い、この入力に対する第4変換テーブル63の4個の出力を4個の符号ビットV1、V2、V3、V4として生成する。
【0086】
以上のように、本発明の実施形態の復号化器によれば、論理積の演算の入力と出力の関係を定めた第2変換テーブルを用いることによって、Min演算を行なうので、論理積の演算を行なう論理演算器を不要にすることができる。また、符号の計算においても、排他的論理和演算の入力と出力の関係を定めた第4変換テーブルを用いることで、排他的論理和演算回路を不要にすることができる。したがって、本発明の実施形態の復号化器によれば、特許文献1に記載された方法に比べて、演算器の数を減らすことができる。
【0087】
[第1の実施形態の変形例1]
復号化器5は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から復号プログラムをメモリにインストールし、コンピュータがこの復号プログラムをメモリから読出して実行することによって、復号化器5の機能を実現することとしてもよい。この場合、復号プログラムは、図15のフローチャートで示される動作手順で動作する。
【0088】
まず、初期動作として、ループ回数および事前値対数比βmnの初期設定が行なわれる。このループ回数は、列処理部14で生成された事前値対数比βmnを用いて再び行処理部12で外部値対数比αmnを生成するループにおける演算回数を示す。このループ回数においては、最大値が予め定められる。事前値対数比βmnは、“0”に初期設定される(ステップSP1)。
【0089】
次いで、受信シンボル系列に従って、対数尤度比算出部10が対数尤度比λnを算出する(ステップSP2)。
【0090】
次に、行番号を表わすmが1とされる(ステップSP3)。
次に、第m行処理部18−m(m=1〜M)の加算部20は、SL個の信号{βmn′:n′はHmn′=1を満たす、SL個の異なる数である}を受けて、それらと対数尤度比λn′とを加算して、加算結果{(λn′+βmn′):n′はHmn′=1を満たす、SL個の異なる数である}を出力する。ここでは、行重みSLは「4」であり、Hmn′=1を満たすn′は、n1、n2、n3、n4とする(ステップSP4)。
【0091】
次に、第m行処理部18−mの第1順位推定部22の第1変換部32は、4個の絶対値信号{|λn′+βmn′|:n′はHmn′=1を満たす、4個の異なる数である}(x1、x2、x3、x4)を受けて、図7に示す第1変換テーブル33に基づいて、それぞれを変換した4個の第1変換信号y1、y2、y3、y4を生成する(ステップSP5)。
【0092】
次に、第m行処理部18−mの第1順位推定部22の第2変換部42は、第1変換部32から出力される4個の第1変換信号y1、y2、y3、y4について、図8に示す第2変換テーブル43に基づいて、1個を除いた3個の第1変換信号のビット単位の論理積を、除く1個が相違する4種類について求めて、第2変換信号z1、z2、z3、z4を生成する(ステップSP6)。
【0093】
次に、第m行処理部18−mの第1順位推定部22の第3変換部52は、第2変換部42から出力される第2変換信号z1、z2、z3、z4を受けて、これらをそれぞれ図9に示す第3変換テーブル53に基づいて変換して、4個の入力信号x1、x2、x3、x4のうちの1個を除いた最小値を表わす4個の第2変換信号w1、w2、w3、w4を生成して、式(1)の絶対値部分Rm,n1、Rm,n2、Rm,n3、Rm,n3として出力する(ステップSP7)。
【0094】
次に、第m行処理部18−mの符号生成部21の第4変換部62は、SL(=4)個の信号{(λn′+βmn′):n′=n1、n2、n3、n4}の符号を表わすSL個の符号ビット(U1、U2、U3、U4)を受けて、図14に示す第4変換テーブル63に基づいて、1個を除いた3個の符号ビットの排他的論理和を、除く1個が相違する4種類について求めて、符号ビット(V1、V2、V3、V4)を生成して、式(1)の符号部分Sm,n1、Sm,n2、Sm,n3、Sm,n3として出力する(ステップSP8)。
【0095】
次に、第m行処理部18−mの結合部23は、符号生成部21から出力されるSmn(n=n1、n2、n3、n4)と第1順位推定部22から出力されるRmn(n=n1、n2、n3、n4)のそれぞれを結合して、外部値対数比αmnを生成する(ステップSP9)。
【0096】
次に、第m行処理部18−mの結合部23は、生成された外部値対数比αmnを出力する(ステップSP10)。
【0097】
次に、m=Mでない場合には(ステップSP11でNO)、mをインクリメントして、(ステップSP12)、ステップSP4に戻る。
【0098】
次に、列処理部14が、式(2)にしたがって、事前値対数比βmnを算出する(ステップSP13)。
【0099】
次に、ループ判定部16は、対数尤度比λnおよび外部値対数比αmnに従って、演算λn+Σαmnを行なって推定受信語Qnを算出する(ステップSP14)。ここで、総和Σは、部分集合B(n)の要素mについて実行される。
【0100】
このステップSP12において算出された値Qnの正負の符号を判定し(ステップSP15)、1次推定符号Cnを生成する(ステップSP16)。この符号の正/負判定においては、たとえば、推定受信語Qnが2の補数表示されているときには、最上位ビット(符号ビット)のビット値を見ることにより、正および負の判定を行なうことができる。
【0101】
1次推定符号Cnが全て生成され、1次推定語(C1,・・・,CN)が生成されると、次いでパリティ検査を実行する(ステップSP17)。このパリティ検査においては、先の検査行列Hの転置行列を用いて、(C1,…,CN)・Ht=0を計算する。この計算により、生成されるシンドロームが0であれば、1次推定語(C1,…,CN)を復号語として出力する(ステップSP20)。
【0102】
一方、この生成されたシンドロームが0と異なる場合には、ループ回数が最大値であるかの判定が行なわれる(ステップSP18)。すなわち、この1次推定語の生成回数をカウントし、その生成回数が所定の最大回数に到達すると、その符号についての算出をそれ以上をやめて、現在生成されている1次推定語を復号語として出力する(ステップSP20)。これにより、収束性の悪いノイジーな符号に対して、不必要に演算処理時間が要するのを防止する。
【0103】
ステップSP18において、ループ回数が最大値に到達していないと判定されると、このループ回数を1だけインクリメントして(ステップSP19)、再びステップSP2からの処理を実行する。
【0104】
(本願の発明をプログラムで実行する場合の具体的な効果)
以上のように、本発明の実施形態の復号プログラムによれば、第1の実施形態と同様に、特許文献1に記載された方法に比べて、演算器の数を減らすことができる。また、一般に、複数の要素の最小値を検出する方法として、各要素の大小比較を行なうプログラムがある。このプログラムは、IF文などの分岐命令を必要とするが、分岐命令処理は、プログラムの実行クロック数を多く必要とする。そのため、このプログラムでは、最小値を検出するのに要する時間が長くなる。これに対して、本発明の実施形態の復号プログラムでは、最小値の探索を、テーブルを用いたビット論理演算によって行なうため分岐命令が不要となる。その結果、本発明の実施形態のプログラムでは、大小比較を実施する一般的なプログラムよりも、短時間で最小値を検出することができる。
【0105】
[第1の実施形態の変形例2]
本変形の構成は、図示しないが、図6に示す第1順位推定部22の構成とほぼ同様である。ただし、本変形例では、第1変換部32は、図7の第1変換テーブルとは異なる変換テーブルを用いる。第2変換部42は、図8の第2変換テーブルとは異なる変換テーブルを用いる。また、第3変換部52は、図9の第3変換テーブルとは異なる変換テーブルを用いる。
【0106】
第1変換部32は、第1の実施形態と異なる第1変換テーブルに従って、絶対値信号x1、x2、x3、x4から第1変換信号をy1、y2、y3、y4を生成する。
【0107】
図16は、第1の実施形態の変形例2の第1変換テーブル133の例を表わす図である。
【0108】
図16を参照して、第1変換テーブル133では、絶対値信号の値と第1変換信号の値が1対1で対応する。この第1変換テーブル133では、絶対値信号は5ビットで表され、取り得る値の範囲が0〜Lであり、第1変換信号の取り得る値はLビットで表わされる。図16では、L=31である。
【0109】
第1変換テーブル133によれば、絶対値信号の値がk(0≦k≦31)のときに、第1変換信号の下位のk個のビットが「0」となり、それ以外のビットが「1」となる。たとえば、絶対値信号の値が「0」ときには、第1変換信号のすべてのビットが「1」となる。絶対値信号の値が「1」のときには、第1変換信号の最下位ビットのみが「0」となる。絶対値信号の値が「2」のときには、第1変換信号の下位の2個のビットのみが「0」となる。
【0110】
第2変換部42は、第1の実施形態と異なる第2変換テーブルを用いて、第1変換信号y1、y2、y3、y4から第2変換信号z1、z2、z3、z4を生成する。
【0111】
図17は、第1の実施形態の変形例2の第2変換テーブル143の例を表わす図である。
【0112】
図17を参照して、第2変換テーブル143では、4個の1ビット入力(入力1、入力2、入力3、入力4)と4個の1ビット出力(出力1、出力2、出力3、出力4)との対応関係を定める。具体的には、出力1は、入力1を除く3個の入力(入力2、入力3、入力4)のビット論理和を表わす。出力2は、入力2を除く3個の入力(入力1、入力3、入力4)のビット論理和を表わす。出力3は、入力3を除く3個の入力(入力1、入力2、入力4)のビット論理和を表わす。出力4は、入力4を除く3個の入力(入力1、入力2、入力3)のビット論理和を表わす。
【0113】
第3変換部52は、第1の実施形態と異なる第3変換テーブルを用いて、第2変換信号z1、z2、z3、z4から第3変換信号w1、w2、w3、w4を生成する。
【0114】
図18は、第1の実施形態の変形例2の第3変換テーブル153の例を表わす図である。
【0115】
図18を参照して、第2変換信号(論理和信号)と第3変換信号との対応関係は、図16の第1変換テーブル133の対応関係を逆にしたものである。すなわち、第3変換テーブル153において第2変換信号に対応する第3変換信号の値は、第1変換テーブル133においてその第2変換信号と同一の値の第1変換信号に対応する絶対値信号の値と同一である。
【0116】
第3変換テーブル153によれば、第2変換信号の下位のk個(0≦k≦31)のビットが「0」で、それ以外のビットが「1」のときに、第3変換信号の値がkとなる。たとえば、第2変換信号のすべてのビットが「1」のときには、第3変換信号の値が「0」となる。第2変換信号の最下位ビットのみが「0」のときには、第3変換信号の値が「1」となる。第2変換信号の下位の2個のビットのみが「0」のときには、第3変換信号の値が「3」となる。
【0117】
以上のように、本変形例によれば、第1の実施形態におけるビットごとの論理積で最小値を見つける方式をビットごとの論理和で最小値を見つける方法に置き換えることができ、このように置き換えても、第1の実施形態と同様の効果が得られる。
【0118】
[第1の実施形態の変形例3]
本変形の構成は、図示しないが、図6に示す第1順位推定部22の構成とほぼ同様である。ただし、本変形例では、第1変換部32は、図7の第1変換テーブルとは異なる変換テーブルを用いる。第2変換部42は、第1の実施形態と同様である。また、第3変換部52は、図9の第3変換テーブルとは異なる変換テーブルを用いる。
【0119】
第1変換部32は、第1の実施形態と異なる第1変換テーブルに従って、絶対値信号x1、x2、x3、x4から第1変換信号をy1、y2、y3、y4を生成する。
【0120】
図19は、第1の実施形態の変形例3の第1変換テーブル233の例を表わす図である。
【0121】
図19を参照して、第1変換テーブル233では、絶対値信号の値と第1変換信号の値が1対1で対応する。
【0122】
第1変換テーブル233では、絶対値信号の取り得る値は小さい順に順序づけられる第1番目から第A番目までの(Aは、2以上の自然数)であり、かつ第1変換信号の取り得る値はBビット(B≧(A−1))で表わされる。ここでは、Aは32とし、Bは、33とする。
【0123】
第1の変換テーブル233では、取り得る値のうちの第K番目(Kは1以上(A−1)以下の自然数)の絶対値信号に対応する第1変換信号のビットのうち、値が「1」であるビットが存在する場合に、取り得る値のうちの第(K+1)番目の絶対値信号に対応する第1変換信号については、値が「1」であるビットの位置は、第K番目の絶対値信号に対応する第1変換信号のビットのうちの値が「1」であるビットの位置と、さらに少なくとも1つのビットの位置とからなる。
【0124】
たとえば、絶対値信号が「第1番目の小さな値」に対する第1変換信号の第32ビット目と第33ビット目のみが「1」である。絶対値信号が「第2番目の小さな値」に対する第1変換信号は、第32ビット目と第33ビット目に加えて、さらに第3ビット目が「1」となる。絶対値信号が「第3番目の小さな値」に対する第1変換信号は、第32ビット目と第33ビット目、第3ビット目に加えて、さらに第29ビット目が「1」となる。
【0125】
第3変換部52は、第1の実施形態と異なる第3変換テーブルを用いて、第2変換信号z1、z2、z3、z4から第3変換信号w1、w2、w3、w4を生成する。
【0126】
図20は、第1の実施形態の変形例3の第3変換テーブル253の例を表わす図である。
【0127】
図20を参照して、第2変換信号(論理積信号)と第3変換信号との対応関係は、図19の第1変換テーブル133の対応関係を逆にしたものである。すなわち、第3変換テーブル253において第2変換信号に対応する第3変換信号の値は、第1変換テーブル233においてその第2変換信号と同一の値の第1変換信号に対応する絶対値信号の値と同一である。
【0128】
たとえば、第2変換信号の第32ビット目と第33ビット目のみが「1」のときに、第3変換信号は、「第1番目の小さな値」である。第2変換信号の第32ビット目と第33ビット目と第3ビット目のみが「1」のときに、第3変換信号は、「第2番目の小さな値」である。第2変換信号の第32ビット目と第33ビット目と第3ビット目と第29ビット目のみが「1」のときに、第3変換信号は、「第3番目の小さな値」である。
【0129】
以上のように、本変形例によれば、絶対値信号の取りうる値は、連続した数でなくてもよく、順序さえ定まればよい。また、第1変換は、絶対値信号の順序の増加につれて、下位ビットから順次「1」にするのではなく、いずれかのビットを「1」にすればよい。このような方式を用いても、第1の実施形態と同様の効果が得られる。
【0130】
[第1の実施形態の変形例4]
本変形の構成は、図示しないが、図6に示す第1順位推定部22の構成とほぼ同様である。ただし、本変形例では、第1変換部32は、図7の第1変換テーブルとは異なる変換テーブルを用いる。第2変換部42は、第1の実施形態と同様である。また、第3変換部52は、図9の第3変換テーブルとは異なる変換テーブルを用いる。
【0131】
第1変換部32は、第1の実施形態と異なる第1変換テーブルに従って、絶対値信号x1、x2、x3、x4から第1変換信号をy1、y2、y3、y4を生成する。
【0132】
図21は、第1の実施形態の変形例4の第1変換テーブル333の例を表わす図である。
【0133】
図21を参照して、第1変換テーブル333では、1個または複数個の絶対値信号が1個の第1変換信号に対応している。
【0134】
第1変換テーブル333では、絶対値信号の取り得る値は5ビットで表わされ、第1変換信号の取り得る値は5ビットで表わされる。ここでは、これらの値は5ビットとしたが、Aビット(Aは1以上の自然数)であれば、どのようなものであってもよい。
【0135】
絶対値信号を構成するビットのうち、値が「1」である最も上位ビットが最下位ビットからk番目(1≦k≦5)のビットのときに、第1変換信号の下位のk個のビットが「1」となり、それ以外のビットが「0」となる。また、絶対値信号を構成するビットのうち、すべてのビットが「0」のときに、第1変換信号のすべてのビットが「0」となる。
【0136】
具体的には、絶対値信号が「00000」のときには、第1変換信号は「00000」となる。絶対値信号が「00001」のときには、第1変換信号は「00001」となる。絶対値信号が「00010」または「00011」のときには、第1変換信号は「00011」となる。絶対値信号が「00100」、「00101」、「00110」、「00111」のときには、第1変換信号は「00111」となる。絶対値信号が「01000」、「01001」、「01010」、・・・、「01111」のときには、第1変換信号は「01111」となる。絶対値信号が「10000」、「10001」、「10010」、・・・、「11111」のときには、第1変換信号は「11111」となる。
【0137】
第3変換部52は、第2変換部42から出力される4個の第2変換信号z1、z2、z3、z4を受けて、第1の実施形態と異なる第3変換テーブルで規定される対応関係で変換した第3変換信号w1、w2、w3、w4を生成して出力する。ここで、第3変換信号w1は、3個の絶対値信号x2、x3、x4のうちの値が最小である信号またはその最小値の近似値であり、第3変換信号w2は、3個の絶対値信号x1、x3、x4のうちの値が最小である信号またはその最小値の近似値であり、第3変換信号w3は、3個の絶対値信号x1、x2、x4のうちの値が最小である信号またはその最小値の近似値であり、第3変換信号w4は、3個の絶対値信号x1、x2、x3のうちの値が最小である信号またはその最小値の近似値である。
【0138】
図22は、第1の実施形態の変形例4の第3変換テーブル353の例を表わす図である。
【0139】
図22を参照して、第3変換テーブル353において第2変換信号に対応する第3変換信号の値は、第1変換テーブル333においてその第2変換信号と同一の値の第1変換信号に対応する絶対値信号が1個のときには、その1個の絶対値信号の値と同一であり、その第2変換信号と同一の値の第1変換信号に対応する絶対値信号が複数個のときには、複数個の絶対値信号のうちの1つの値と同一である。
【0140】
第2変換信号を構成するビットのうち、値が「1」である最も上位ビットが最下位ビットから第k番目(1≦k≦5)のビットのときに、第3変換信号の最下位ビットから第k番目のビットのみが「1」となり、その他のビットが「0」となる。第2変換信号を構成するビットのうち、すべてのビットが「0」のときには、第3変換信号のすべてのビットが「0」となる。
【0141】
具体的には、第2変換信号が「00000」のときには、第3変換信号の値が「00000」となる。第2変換信号が「00001」のときには、第3変換信号の値が「00001」となる。第2変換信号が「00011」のときには、第3変換信号の値が「00010」となる。第2変換信号が「00111」のときには、第3変換信号が「00100」となる。第2変換信号が「01111」のときには、第3変換信号が「01000」となる。第2変換信号が「11111」のときには、第3変換信号が「10000」となる。
【0142】
以上のように、本変形例によれば、第1の実施形態と同様の効果が得られる。また、本変形例によれば、第1変換において、絶対値信号のビット数と第1変換信号のビット数を同一にし、第3変換において、第2変換信号のビット数と第3変換信号のビット数とを同一にするので、第1の実施形態よりも、メモリ容量(つまり、テーブルサイズ)および配線数を少なくすることができる。
【0143】
[第1の実施形態の変形例5]
本変形の構成は、図示しないが、図6に示す第1順位推定部22の構成とほぼ同様である。ただし、本変形例では、第1変換部32は、図7の第1変換テーブルとは異なる変換テーブルを用いる。第2変換部42は、第1の実施形態と同様である。また、第3変換部52は、図9の第3変換テーブルとは異なる変換テーブルを用いる。
【0144】
第1変換部32は、第1の実施形態と異なる第1変換テーブルに従って、絶対値信号x1、x2、x3、x4から第1変換信号をy1、y2、y3、y4を生成する。
【0145】
図23は、第1の実施形態の変形例5の第1変換テーブル433の例を表わす図である。
【0146】
図23を参照して、第1変換テーブル433では、1個または複数個の絶対値信号が1個の第1変換信号に対応している。
【0147】
第1変換テーブル433では、絶対値信号の取り得る値は5ビットで表わされ、第1変換信号の取り得る値は5ビットで表わされる。ここでは、これらの値は5ビットとしたが、Aビット(Aは1以上の自然数)であれば、どのようなものであってもよい。
【0148】
絶対値信号を構成するビットのうち、値が「1」である最も上位ビットが最下位ビットからk番目(1≦k≦5)のビットのときに、第1変換信号のk個のビットが「1」となり、それ以外のビットが「0」となる。絶対値信号を構成するビットのうち、値が「1」である最も上位ビットが最下位ビットから(k+1)番目(1≦k≦4)のビットのときに、第1変換信号は、上記k個のビットに加えて、さらに1個のビットが「1」となり、それ以外のビットが「0」となる。
【0149】
具体的には、絶対値信号が「00000」のときには、第1変換信号は「00000」となる。絶対値信号が「00001」のときには、第1変換信号は「00100」となる。絶対値信号が「00010」または「00011」のときには、第1変換信号は「00110」となる。絶対値信号が「00100」、「00101」、「00110」、「00111」のときには、第1変換信号は「10110」となる。絶対値信号が「01000」、「01001」、「01010」、・・・、「01111」のときには、第1変換信号は「10111」となる。絶対値信号が「10000」、「10001」、「10010」、・・・、「11111」のときには、第1変換信号は「11111」となる。
【0150】
第3変換部52は、第2変換部42から出力される4個の第2変換信号z1、z2、z3、z4を受けて、第1の実施形態と異なる第3変換テーブルで規定される対応関係で変換した第3変換信号w1、w2、w3、w4を生成して出力する。ここで、第3変換信号w1は、3個の絶対値信号x2、x3、x4のうちの値が最小である信号またはその最小値の近似値であり、第3変換信号w2は、3個の絶対値信号x1、x3、x4のうちの値が最小である信号またはその最小値の近似値であり、第3変換信号w3は、3個の絶対値信号x1、x2、x4のうちの値が最小である信号またはその最小値の近似値であり、第3変換信号w4は、3個の絶対値信号x1、x2、x3のうちの値が最小である信号またはその最小値の近似値である。
【0151】
図24は、第1の実施形態の変形例5の第3変換テーブル453の例を表わす図である。
【0152】
図24を参照して、第3変換テーブル453において第2変換信号に対応する第3変換信号の値は、第1変換テーブル333においてその第2変換信号と同一の値の第1変換信号に対応する絶対値信号が1個のときには、その1個の絶対値信号の値と同一であり、その第2変換信号と同一の値の第1変換信号に対応する絶対値信号が複数個のときには、複数個の絶対値信号のうちの1つの値と同一である。
【0153】
第2変換信号を構成するビットのうち、値が「1」であるビットがk個(1≦k≦5)のビットのときに、第3変換信号の最下位ビットから第k番目のビットのみが「1」となり、その他のビットが「0」となる。第2変換信号を構成するビットのうち、すべてのビットが「0」のときには、第3変換信号のすべてのビットが「0」となる。
【0154】
具体的には、第2変換信号が「00000」のときには、第3変換信号の値が「00000」となる。第2変換信号が「00100」のときには、第3変換信号の値が「00001」となる。第2変換信号が「00110」のときには、第3変換信号の値が「00010」となる。第2変換信号が「10110」のときには、第3変換信号が「00100」となる。第2変換信号が「10111」のときには、第3変換信号が「01000」となる。第2変換信号が「11111」のときには、第3変換信号が「10000」となる。
【0155】
以上のように、本変形例によれば、変形例4と同様に、第1変換において、絶対値信号のビット数と第1変換信号のビット数を同一にし、第3変換において、第2変換信号のビット数と第3変換信号のビット数とを同一にする。また、本変形例は、第1変換は、絶対値信号の順序の増加につれて、下位ビットから順次「1」にするのではなく、いずれかのビットを「1」にする点で変形例4と相違するが。このような方式を用いても、変形例4と同様に、第1の実施形態よりも、メモリ容量および配線数を少なくすることができる。
【0156】
[第2の実施形態]
第2の実施形態は、テーブルと論理演算器の両方を用いて、第2変換信号および符号ビットを生成する復号装置に関する。
【0157】
本実施の形態では、行重みSL=6として説明する。したがって、第1変換部32には、6個の絶対値信号x1〜x6が入力され、第3変換部52から6個の第3変換信号z1〜z6が出力されるものとする。また、第4変換部62には、6個の符号ビットU1〜U6が入力されて、6個の符号ビットV1〜V6が出力されるものとする。
【0158】
図25は、第2の実施形態の第2変換部72の構成を表わす図である。
図25を参照して、第2変換部72は、第1変換部42から出力される6個の第1変換信号y1、y2、y3、y4、y5、y6を受けて、第2変換規則を定めた第2変換テーブル543で規定される対応関係で変換した6個の第2変換信号z1、z2、z3、z4、z5、z6を生成する。第2の変換規則では、6個の第1変換信号のうちの1個を除いて5個の第1変換信号のビット単位の論理積の結果を表わす第2変換信号が生成される。第2変換部72は、除かれる1個がそれぞれ相違する6種類の5個の第1変換信号を用いて、6個の第2変換信号を生成する。
【0159】
第2変換部72は、複数個の第1変換信号の変換を同時に並列して行なう。第2変換部42は、第1変換信号のビット数L個の変換部で構成される。すなわち、第2変換部72は、第1ビット変換部75−1と、第2ビット変換部75−2と、・・・、第Lビット変換部75−Lとを含む。以下では、第1ビット変換部75−1について代表して説明する。他のビット変換部も同様である。
【0160】
第1ビット変換部75−1は、論理積回路AND1−1およびAND1−2を含む。
論理積回路AND1−1は、第1変換信号y1、y2、y3の第1ビットの論理積Y1を算出する。論理積回路AND1−2は、第1変換信号y4、y5、y6の第1ビットの論理積Y2を算出する。
【0161】
第1ビット変換部75−1は、さらに第2メモリ部(領域1−1)71−1−1を含む。第2メモリ部(領域1−1)71−1−1では、3個の第1変換信号y1、y2、y3の第1ビットと論理積Y2からなる4ビットの信号(Y2、y31、y21、y11)がアドレスとして用いられ、当該4ビットの信号に対応する領域に第2変換信号z1、z2、z3の第1ビット目である3ビットの信号(z31、z21、z11)の値が格納されている。4ビットの信号(Y2、y31、y21、y11)と3ビットの信号(z31、z21、z11)との関係は、第2変換テーブル543にしたがう。第2メモリ部(領域1−1)71−1−1は、4ビットの信号(Y2、y31、y21、y11)を受けて、その信号に対応する3ビットの信号(z31、z21、z11)を出力する。
【0162】
また、第1ビット変換部75−1は、第2メモリ部(領域1−2)71−1−2を含む。第2メモリ部(領域1−2)71−1−2では、3個の第1変換信号y4、y5、y6の第1ビットと論理積Y1からなる4ビットの信号(Y1、y41、y51、y61)がアドレスとして用いられ、当該4ビットの信号に対応する領域に第2変換信号z4、z5、z6の第1ビット目である3ビットの信号(z41、z51、z61)の値が格納されている。4ビットの信号(Y1、y41、y51、y61)と3ビットの信号(z41、z51、z61)との関係は、第2変換テーブル543にしたがう。第2メモリ部(領域1−2)71−1−2は、4ビットの信号(Y1、y41、y51、y61)を受けて、その信号に対応する3ビットの信号(z41、z51、z61)を出力する。
【0163】
図26は、第2の実施形態の第2変換テーブル543の例を表わす図である。
図26を参照して、第2変換テーブル543では、3個の第1の1ビット入力(入力1、入力2、入力3)および1個の第2の1ビット入力(入力4)と3個の1ビット出力(出力1、出力2、出力3)との対応関係を定める。
【0164】
具体的には、出力1は、入力1を除く2個の第1の入力(入力2、入力3)と第2の入力(入力4)のビット論理積を表わす。出力2は、入力2を除く2個の第1の入力(入力1、入力3)と第2の入力(入力4)のビット論理積を表わす。出力3は、入力3を除く2個の第1の入力(入力1、入力2)と第2の入力(入力4)のビット論理積を表わす。
【0165】
第1ビット変換部75−1は、論理積回路AND1−2から出力される論理積Y2を第2変換テーブル543の1個の第2の入力とし、かつ第1変換信号y1、y2、y3の第1ビットを第2変換テーブル543の3個の第1の入力として用い、この入力に対する第2変換テーブル543の3個の出力を3個の第2変換信号z1、z2、z3の第1ビットとして生成する。また、第1ビット変換部75−1は、論理積回路AND1−1から出力される論理積Y1を第2変換テーブル543の1個の第2の入力とし、かつ第1変換信号y4、y5、y6の第1ビットを第2変換テーブル543の3個の第1の入力として用い、この入力に対する第2変換テーブル543の3個の出力を3個の第2変換信号z4、z5、z6の第1ビットとして生成する。
【0166】
図27は、第2の実施形態の第4変換部82の構成を表わす図である。
図27を参照して、第4変換部82は、6個の符号ビットU1、U2、U3、U4、U5、U6を受けて、第4変換規則を定めた第4変換テーブル563で規定される対応関係で変換した6個の符号ビットV1、V2、V3、V4、V5、V6を生成する。
【0167】
第4の変換規則では、6個の符号ビットうちの1個を除いた5個の符号ビットの排他的論理和演算の結果を表わす符号ビットが生成される。第4変換部82は、除かれる1個がそれぞれ相違する6種類の5個の符号ビットを用いて、6個の符号ビットV1、V2、V3、V4、V5、V6を生成する。
【0168】
第4変換部82は、排他的論理和回路EXOR1およびEXOR2を含む。
排他的論理和回路EXOR1は、符号ビットU1、U2、U3の排他的論理和ER1を算出する。排他的論理和回路EXOR2は、符号ビットU4、U5、U6の排他的論理和ER2を算出する。
【0169】
第4変換部82は、第4メモリ部(領域1)81を含む。第4メモリ部(領域1)81では、3個の符号ビットU1、U2、U3と排他的論理和ER2からなる4ビットの信号(ER2、U3、U2、U1)がアドレスとして用いられ、当該4ビットの信号に対応する領域に3ビットの信号(V3、V2、V1)の値が格納されている。4ビットの信号(ER2、U3、U2、U1)と3ビットの信号(V3、V2、V1)との関係は、第4変換テーブル563にしたがう。第4メモリ部(領域1)81は、4ビットの信号(ER2、U3、U2、U1)を受けて、その信号に対応する3ビットの信号(V3、V2、V1)を出力する。
【0170】
第4変換部82は、第4メモリ部(領域2)83を含む。第4メモリ部(領域2)83では、3個の符号ビットU4、U5、U6と排他的論理和ER1からなる4ビットの信号(ER1、U6、U5、U4)がアドレスとして用いられ、当該4ビットの信号に対応する領域に3ビットの信号(V6、V5、V4)の値が格納されている。4ビットの信号(ER1、U6、U5、U4)と3ビットの信号(V6、V5、V4)との関係は、第4変換テーブル563にしたがう。第4メモリ部(領域2)82は、4ビットの信号(ER1、U6、U5、U4)を受けて、その信号に対応する3ビットの信号(V6、V5、V4)を出力する。
【0171】
図28は、第2の実施形態の第4変換テーブル563の例を表わす図である。
図28を参照して、第4変換テーブル563では、3個の第1の1ビット入力(入力1、入力2、入力3)および1個の第2の1ビット入力(入力4)と3個の1ビット出力(出力1、出力2、出力3)との対応関係を定める。
【0172】
具体的には、出力1は、入力1を除く2個の第1の入力(入力2、入力3)と第2の入力(入力4)の排他的論理和を表わす。出力2は、入力2を除く2個の第1の入力(入力1、入力3)と第2の入力(入力4)の排他的論理和を表わす。出力3は、入力3を除く2個の第1の入力(入力1、入力2)と第2の入力(入力4)の排他的論理和を表わす。
【0173】
第4変換部82は、排他的論理和回路EXOR2から出力される排他的論理和ER2を第4変換テーブル563の1個の第2の入力とし、かつ3個の符号ビットU1、U2、U3を第4変換テーブル563の3個の第1の入力として用い、この入力に対する第4変換テーブル563の3個の出力を3個の符号ビットV1、V2、V3として生成する。また、第4変換部82は、排他的論理和回路EXOR1から出力される排他的論理和ER1を第4変換テーブル563の1個の第2の入力とし、かつ3個の符号ビットU4、U5、U6を第4変換テーブル563の3個の第1の入力として用い、この入力に対する第4変換テーブル563の3個の出力を3個の符号ビットV4、V5、V6として生成する。
【0174】
以上のように、本発明の実施形態の復号化器によれば、論理積の演算の入力と出力の関係を定めた第2変換テーブルと論理演算器を併用して、Min演算を行なうので、特許文献1に記載されたように論理積の演算をすべて論理演算器を行なう方法よりも、演算器の数を減らすことができる。また、本実施形態では、第1の実施形態のように、Min演算のすべての論理積を第2変換テーブルを用いて求める方法よりも、第2変換テーブルの容量を少なくできる。
【0175】
[第2の実施形態の変形例]
本変形例は、第2変換におけるビット論理演算をテーブルと論理演算器に分担させる分担の割合が、第2の実施形態と相違する。
【0176】
第2の実施形態によれば、第2変換部は、論理積回路が、SL(=6)個の信号のうちの(SL−M)(=3)個の信号の各ビットの論理積を算出した。そして、M(=3)個の第1の入力と、1個の第2の入力とを有する第2変換テーブルを用いて、M個の第2変換信号の各ビットを生成した。また、第4変換部は、排他的論理和回路が、SL(=6)個の信号のうちの(SL−M)(=3)個の信号の符号ビットの排他的論理和を算出した。そして、M(=3)個の第1の入力と、1個の第2の入力とを有する第4変換テーブルを用いて、M個の符号ビットを生成した。ここでは、Mは3としたが、これに限定するものではなく、Mは1以上、(SL−1)以下の自然数であればよい。以下では、Mは2の例について説明する。
【0177】
図29は、第2の実施形態の変形例の第2変換部の第1ビット変換部95−1の構成を表わす図である。他のビット変換部も、これと同様である。
【0178】
第1ビット変換部95−1は、論理積回路AND1−11〜AND1−16を含む。
論理積回路AND1−11は、第1変換信号y1、y2の第1ビットの論理積Y11を算出する。論理積回路AND1−12は、第1変換信号y3、y4の第1ビットの論理積Y12を算出する。論理積回路AND1−13は、第1変換信号y5、y6の第1ビットの論理積Y13を算出する。論理積回路AND1−14は、論理積Y12、Y13の論理積Y14を算出する。論理積回路AND1−15は、論理積Y11、Y13の論理積Y15を算出する。論理積回路AND1−16は、論理積Y11、Y12の論理積Y16を算出する。
【0179】
第1ビット変換部95−1は、第2メモリ部(領域1−1)91−1−1を含む。第2メモリ部(領域1−1)91−1−1では、2個の第1変換信号y1、y2の第1ビットと論理積Y14からなる3ビットの信号(Y14、y21、y11)がアドレスとして用いられ、当該3ビットの信号に対応する領域に第2変換信号z1、z2の第1ビット目である2ビットの信号(z21、z11)の値が格納されている。3ビットの信号(Y14、y21、y11)と2ビットの信号(z21、z11)との関係は、第2変換テーブル93にしたがう。第2メモリ部(領域1−1)91−1−1は、3ビットの信号(Y14、y21、y11)を受けて、その信号に対応する2ビットの信号(z21、z11)を出力する。
【0180】
第1ビット変換部95−1は、第2メモリ部(領域1−2)91−1−2を含む。第2メモリ部(領域1−2)91−1−2では、2個の第1変換信号y3、y4の第1ビットと論理積Y15からなる3ビットの信号(Y15、y41、y31)がアドレスとして用いられ、当該3ビットの信号に対応する領域に第2変換信号z3、z4の第1ビット目である2ビットの信号(z41、z31)の値が格納されている。3ビットの信号(Y15、y41、y31)と2ビットの信号(z41、z31)との関係は、第2変換テーブル93にしたがう。第2メモリ部(領域1−2)91−1−2は、3ビットの信号(Y15、y41、y31)を受けて、その信号に対応する2ビットの信号(z41、z31)を出力する。
【0181】
第1ビット変換部95−1は、第2メモリ部(領域1−3)91−1−3を含む。第2メモリ部(領域1−3)91−1−3では、2個の第1変換信号y5、y6の第1ビットと論理積Y16からなる3ビットの信号(Y16、y61、y51)がアドレスとして用いられ、当該3ビットの信号に対応する領域に第2変換信号z5、z6の第1ビット目である2ビットの信号(z61、z51)の値が格納されている。3ビットの信号(Y16、y61、y51)と2ビットの信号(z61、z51)との関係は、第2変換テーブル93にしたがう。第2メモリ部(領域1−3)91−1−5は、3ビットの信号(Y16、y61、y51)を受けて、その信号に対応する2ビットの信号(z61、z51)を出力する。
【0182】
図30は、第2の実施形態の変形例の第2変換テーブル93の例を表わす図である。
図30を参照して、第2変換テーブル93では、2個の第1の1ビット入力(入力1、入力2)および1個の第2の1ビット入力(入力3)と2個の1ビット出力(出力1、出力2)との対応関係を定める。
【0183】
具体的には、出力1は、入力1を除く1個の第1の入力(入力2)と第2の入力(入力3)のビット論理積を表わす。出力2は、入力2を除く1個の第1の入力(入力1)と第2の入力(入力3)のビット論理積を表わす。
【0184】
第1ビット変換部95−1は、論理積回路AND1−14から出力される論理積Y14を第2変換テーブル93の1個の第2の入力とし、かつ第1変換信号y1、y2の第1ビットを第2変換テーブル93の2個の第1の入力として用い、この入力に対する第2変換テーブル93の2個の出力を2個の第2変換信号の第1ビットz11、z21として生成する。また、第1ビット変換部95−1は、論理積回路AND1−15から出力される論理積Y15を第2変換テーブル93の1個の第2の入力とし、かつ第1変換信号y3、y4の第1ビットを第2変換テーブル93の2個の第1の入力として用い、この入力に対する第2変換テーブル93の2個の出力を2個の第2変換信号の第1ビットz31、z41として生成する。また、第1ビット変換部95−3は、論理積回路AND1−16から出力される論理積Y16を第2変換テーブル93の1個の第2の入力とし、かつ第1変換信号y5、y6の第1ビットを第2変換テーブル93の2個の第1の入力として用い、この入力に対する第2変換テーブル93の2個の出力を2個の第2変換信号の第1ビットz51、z61として生成する。
【0185】
以上のように、本変形例によれば、第2変換部は、論理積回路が、SL(=6)個の信号のうちの(SL−M)(=4)個の信号の各ビットの論理積を算出した。そして、M(=2)個の第1の入力と、1個の第2の入力とを有する第2変換テーブルを用いて、M個の第2変換信号の各ビットを生成した。また、第4変換部についても、同様にして排他的論理和回路が、SL(=6)個の信号のうちの(SL−M)(=4)個の信号の各ビットの排他的論理和を算出し、M(=2)個の第1の入力と、1個の第2の入力とを有する第4変換テーブルを用いて、M個の符号ビットを生成することとしてもよい。
【0186】
以上のように、本変形例によれば、第2の実施形態と同様の効果が得られる。すなわち、本変形例によれば、特許文献1の方法よりも演算器の数を減らすことができ、第1の実施形態の方法よりも第2変換テーブルの容量を少なくできる。
【0187】
(全体を通じての変形例)
本発明は、上記の実施の形態に限定されるものではなく、たとえば以下のような変形例を含む。
【0188】
(1) 尤度の高い信号を用いた復号
本発明の実施形態およびその変形例では、尤度が最小の信号を用いて低密度パリティ検査符号を復号する方法を説明した。この方法は、誤りがありそうな信号から順に誤り訂正を行なうので、迅速に一定精度の誤り訂正を行なうことができる。
【0189】
しかしながら、尤度が高い所定個数の信号を用いて、誤り訂正を行なうようにしてもよい。例えばターボ符号や畳み込み符号では,BCJRアルゴリズム,ビタビ復号アルゴリズムなどがあり,尤度の高い信号を基に誤り訂正を行なうMAP(最大事後確率)アルゴリズムがある。これらの方法は、確実な信号を基準にして、誤りのありそうなところを訂正するので、より確実に誤りの訂正が可能となる。
【0190】
たとえば、LDPCの復号においても自身を除いて最も大きい信号を用いる復号法(これをmax-sum復号法と呼ぶことにする)を用いてもよい。
【0191】
max-sum復号法では、min-sum復号法における式(1)の最小値を出力する演算minが、最大値を出力する演算maxに置き換えられる。そして、第1順位推定部の処理が、小さいものから第1順位である最小値またはその近似値を推定するものから、大きいものから第1順位である最大値またはその近似値を推定するものに置き換えられる。
【0192】
この置き換えは、第1変換テーブルと、第3変換テーブルを代えるだけで容易に実現できる。第1変換テーブルにおいて、絶対値信号の順番を逆にし、かつ第3変換テーブルにおいて、第2変換信号の順序を逆にすればよい。たとえば、図7の第1変換テーブルにおいて、絶対値信号の「00000」、「00001」、・・・、「11111」が、それぞれ、第1変換信号の「111・・・1111」、「011・・・1111」、・・・、「000・・・0000」に対応するように変形し、図9の第3変換テーブルにおいて、第2変換信号の「111・・・1111」、「011・・・1111」、・・・、「000・・・0000」が、それぞれ、第3変換信号の「00000」、「00001」、・・・、「11111」に対応するように変形すればよい。
【0193】
(2) テーブル
本発明の実施形態では、第1〜第4変換テーブルは、それぞれ個別のメモリ領域に保存されることとしたが、これに限定するものではなく、各変換に際して、同一のRAM(Random Access Memory)にロードすることとしてもよい。
【0194】
(3) 符号生成部の構成
本発明の実施形態の符号生成部では、外部値対数比αmnの符号を求めるために、第4変換テーブル、あるいは排他的論理和演算回路と第4変換テーブルを用いたが、排他的論理演算回路のみを用いてもよい。
【0195】
図31は、変形例1の符号生成部96を表わす図である。
図31を参照して、排他的論理和回路EXOR11は、符号ビットU2、U3の排他的論理和ER11を算出する。排他的論理和回路EXOR12は、符号ビットU1、U3の排他的論理和ER12を算出する。排他的論理和回路EXOR13は、符号ビットU1、U2の排他的論理和ER13を算出する。排他的論理和回路EXOR14は、符号ビットU1、U2の排他的論理和ER14を算出する。排他的論理和回路EXOR15は、排他的論理和ER1と符号ビットU4の排他的論理和ER15を符号ビットV1として生成する。排他的論理和回路EXOR16は、排他的論理和ER12と符号ビットU4の排他的論理和ER16を符号ビットV2として生成する。排他的論理和回路EXOR17は、排他的論理和ER3と符号ビットU4の排他的論理和ER17を符号ビットV3として生成する。排他的論理和回路EXOR18は、排他的論理和ER14と符号ビットU3の排他的論理和ER18を符号ビットV4として生成する。
【0196】
図32は、変形例2の符号生成部97を表わす図である。
排他的論理和回路EXOR19は、符号ビットU1、U2の排他的論理和ER19を算出する。排他的論理和回路EXOR20は、符号ビットU3、U4の排他的論理和ER20を算出する。排他的論理和回路EXOR21は、符号ビットU1と排他的論理和ER20の排他的論理和ER21を符号ビットV2として生成する。排他的論理和回路EXOR22は、符号ビットU2と排他的論理和ER20の排他的論理和ER22を符号ビットV1として生成する。排他的論理和回路EXOR23は、符号ビットU3と排他的論理和ER19の排他的論理和ER23を符号ビットV4として生成する。排他的論理和回路EXOR24は、符号ビットU4と排他的論理和ER19の排他的論理和ER24を符号ビットV3として生成する。
【0197】
図32の符号生成部97では、図31の符号生成部96に比べて、排他的論理和回路の個数を減らすことができる。
【0198】
(4) 第1順位推定部の構成
本発明の実施形態では、ビットごとの論理演算によって、絶対値信号の最小値を求めたが、これに限定されるものではない。
【0199】
図33は、変形例1の第1順位推定部99を表わす図である。
図33を参照して、比較器CMP1は、絶対値信号x2とx3の大きさを比較して、小さい方の信号CP1を出力する。比較器CMP1は、絶対値信号x1とx3の大きさを比較して、小さい方の信号CP2を出力する。比較器CMP3は、絶対値信号x1とx2の大きさを比較して、小さい方の信号CP3を出力する。比較器CMP4は、絶対値信号x1とx2の大きさを比較して、小さい方の信号CP4を出力する。比較器CMP5は、絶対値信号x4と信号CP1の大きさを比較して、小さい方の信号CP5を第3変換信号w1として出力する。比較器CMP6は、絶対値信号x4と信号CP2の大きさを比較して、小さい方の信号CP6を第3変換信号w2として出力する。比較器CMP7は、絶対値信号x4と信号CP3の大きさを比較して、小さい方の信号CP7を第3変換信号w3として出力する。比較器CMP8は、絶対値信号x3と信号CP4の大きさを比較して、小さい方の信号CP8を第3変換信号w4として出力する。
【0200】
図34は、変形例2の第1順位推定部98を表わす図である。
図34を参照して、比較器CMP9は、絶対値信号x1とx2の大きさを比較して、小さい方の信号CP9を出力する。比較器CMP10は、絶対値信号x3とx4の大きさを比較して、小さい方の信号CP10を出力する。比較器CMP11は、絶対値信号x1と信号CP10の大きさを比較して、小さい方の信号CP11を第3変換信号w2として出力する。比較器CMP12は、絶対値信号x2と信号CP10の大きさを比較して、小さい方の信号CP12を第3変換信号w1として出力する。比較器CMP13は、絶対値信号x3と信号CP9の大きさを比較して、小さい方の信号CP13を第3変換信号w4として出力する。比較器CMP14は、絶対値信号x4と信号CP9の大きさを比較して、小さい方の信号CP14を第3変換信号w3として出力する。
【0201】
図34の第1順位推定部98では、図33の第1順位推定部99に比べて、比較器の個数を減らすことができる。
【0202】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【0203】
1 符号化器、2 変調器、3 通信路、4 復調器、4a 復調回路、4b アナログ/デジタル変調回路、5 復号化器、10 対数尤度比算出部、12 行処理部、14 列処理部、16 ループ判定部、18−1 第1行処理部、18−2 第2行処理部、18−m 第m行処理部、18−M 第M行処理部、20 加算部、22,98,99 第1順位推定部、21,96,97 符号生成部、23 結合部、32 第1変換部、42,72 第2変換部、52 第3変換部、62,82 第4変換部、31−1〜31−4 第1メモリ部、41−1〜41−L,71−1−1,71−1−2,71−L−1,71−L−2,91−1−1,91−1−2,91−1−3 第2メモリ部、51−1〜51−4 第3メモリ部、61,81,83 第4メモリ部、45−1〜45−L 第Kビット変換部、95−1 第1ビット変換部、33,133,233,333,433 第1変換テーブル、43,93,143,543 第2変換テーブル、53,153,253,353,453 第3変換テーブル、63,563 第4変換テーブル、AND1−1,AND1−2,ANDL−1,ANDL−2,AND1−11〜AND1−16 論理積回路、EXOR1,EXOR2,EXOR11〜EXOR24 排他的論理和回路、CMP1〜CMP14 比較器。

【特許請求の範囲】
【請求項1】
所定数の信号単位で復号を行なう復号装置であって、
N個(Nは2以上の自然数)の尤度を表わす入力信号の絶対値を表わす絶対値信号のうち、1個を除いた(N−1)個の絶対値信号の最大または最小である第1順位の信号の値または前記第1順位の信号の近似値を推定する第1順位推定部と、
前記第1順位推定部で推定された信号の値と前記1単位内の信号の符号とから新たな信号を生成して、前記新たな信号に基づいて前記1単位内の信号の推定信号系列を生成する受信信号推定部とを備え、
前記第1順位推定部は、
第1の変換規則に基づいて、前記N個の絶対値信号それぞれを変換して、N個の第1変換信号を生成する第1変換部と、
第2の変換規則に基づいて、N個の第1変換信号を変換して、N個の第2変換信号を生成する第2変換部とを備え、前記第2の変換規則では、前記N個の第1変換信号のうちの1個を除いて(N−1)個の第1変換信号のビット単位の所定の論理演算の結果を表わす第2変換信号が生成され、
第3の変換規則に基づいて、前記第2変換信号を変換して、(N−1)個の絶対値信号のうちの前記第1順位の信号の値または前記第1順位の信号の近似値を表わす第3変換信号を生成する第3変換部とを含み、
前記第2変換部は、除かれる1個がそれぞれ相違するN種類の(N−1)個の第1変換信号を用いて、N個の第2変換信号を生成し、前記第3変換部は、前記N個の第2変換信号を変換して、N個の第3変換信号を生成し、前記受信信号推定部は、前記N個の第3変換信号に基づいてN個の前記新たな信号を生成し、
前記第2変換部は、前記ビット単位の所定の論理演算の少なくとも一部について、入力と出力との関係を表わした第1テーブルを用いて、前記第2変換信号の各ビットを生成する、復号装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate


【公開番号】特開2011−139544(P2011−139544A)
【公開日】平成23年7月14日(2011.7.14)
【国際特許分類】
【出願番号】特願2011−90143(P2011−90143)
【出願日】平成23年4月14日(2011.4.14)
【分割の表示】特願2008−302985(P2008−302985)の分割
【原出願日】平成20年11月27日(2008.11.27)
【出願人】(000002130)住友電気工業株式会社 (12,747)
【出願人】(504126112)住友電工システムソリューション株式会社 (78)
【Fターム(参考)】