説明

復号器

【課題】復号処理部において復号処理の反復を行いつつも、処理能力を向上させる。
【解決手段】復号処理部11が、符号化された入力データに対する復号処理を反復して行う復号器5であって、前記復号処理部11は、前記復号処理が分割された複数の部分処理を順次実行するための複数のステージ11a,11b,11cを有し、前記復号処理を反復できるように、最終ステージ11cと先頭ステージ11aとが接続されており、先に前記復号処理部に入力された入力データに対する復号処理の反復が終了する前のタイミングであって、先に前記復号処理部に入力された入力データについての処理データが、前記先頭ステージ以外のステージに存在しているタイミングにおいて、新たな入力データが前記先頭ステージにおいて処理されるよう構成されている。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、復号処理部が、入力データに対する復号処理を反復して行う復号器に関するものである。
【背景技術】
【0002】
デジタル通信の分野では、有線及び無線を問わず、高速通信、低消費電力及び高い通信品質(ビット誤り率)が望まれている。誤り訂正技術は、これらの要求を満足させるための技術の一つとして、無線、有線及び記録システム等において幅広く利用されている。
かかる誤り訂正技術の一つとして、低密度パリティ検査(LDPC:Low-Density Parity-Check)符号と、その復号法であるサムプロダクト(sum-product)復号法とが注目されている(特許文献1並びに非特許文献1及び2)。
【0003】
このLDPC符号では、白色ガウス通信路のシャノン(Shannon)限界まで、0.004dBという復号特性が得られることが知られている(非特許文献3)。
また、サムプログラム復号法は、並列処理による復号処理を実行するため、符号長を長くすることができるとともに、処理能力を向上させることができる。また、復号法としては、サムプロダクト復号法を簡略化した、ミニサム(min-sum)復号法も知られている。
【0004】
上記復号法では、受信信号から計算した対数尤度比を、行処理及び列処理からなる復号処理を行う復号処理部に与え、当該復号処理部において、行処理及び列処理の復号処理を繰り返し行うことで誤り訂正を行う。このようなLDPC符号の誤り訂正復号を行う復号器は、特許文献1に開示されている。
上記のような復号器では、行処理及び列処理の復号処理は、反復して繰り返し行われる。そして、行処理及び列処理の繰り返し回数が所定値(反復可能回数)に到達するか、又は所定値に達する前であっても所定の条件を満たすと、行処理及び列処理の反復が終了する。
【0005】
【特許文献1】特開2007−325011号公報
【非特許文献1】和田山正 「低密度パリティ検査符号とその復号法について」 信学技報
【非特許文献2】Engling Yeo “VLSI Architectures for Iterative Decoders in Magnetic Recording Channels” IEEE Trans. On Magnetics, vol.37, NO2. March 2001
【非特許文献3】S.Y.Chung “On the design of low-density parity-check codes within 0.0045dB of the Shannon limit”IEEE Communications Letters,Vol.5,No.2,Februaly 2001
【発明の開示】
【発明が解決しようとする課題】
【0006】
LDPC符号の復号器のように、復号処理を繰り返し行う必要があるものでは、復号処理の反復のため、復号器全体の処理速度が低下するという問題がある。
例えば、図10に示すように、復号処理部(Decoder)101が、入力誤り訂正を行う復号処理を10回反復する復号器100を想定する。
【0007】
なお、図10の復号処理部101は、全並列型であり、一つのパラレル符号データを、全並列的に処理できるものとする。
また、図10の復号器100では、復号処理部101の入力側に、S/P変換部(シリアル/パラレル変換部)102が設けられ、復号処理部102の出力側に、P/S変換部(パラレル/シリアル変換部)103が設けられている。S/P変換部102により、シリアルの入力データは、パラレルの入力データに変換される。復号処理部101は、パラレルの入力データに対して並列的に復号処理を行い、パラレルの出力データを出力する。パラレルの出力データは、P/S変換部103により、シリアルの出力データに変換される。
【0008】
図10の場合、復号対象の入力データは、復号処理部101において繰り返し処理されているため、その入力データについて処理中のデータは、10回の反復が終了するまで、当該復号処理部101内部に滞留している。
したがって、復号処理部101における反復が終了するまでは、新たな入力データを、復号処理部101に与えることができない。
【0009】
このため、図10の全並列型復号器の処理能力は、次の計算式によって計算される。
処理能力=(F×符号長)/(N×Y)
ただし、
「F」は、復号処理部101の動作クロック周波数
「N」は、復号処理の反復回数
「Y」は、1回の復号処理の所要サイクル数(所要クロック数)
である。
【0010】
例えば、動作クロック周波数Fが100[MHz]、符号長が1000[bit]、反復回数Nが10回、復号処理の所要サイクル数Yが1、とすると、復号器100の処理能力は、次の通りである。
処理能力=(100[MHz]×1000[bit])/(10×1)
=10[Gbit/s]
【0011】
処理能力に関する上記式によれば、ある符号長において、処理能力を向上させるには、(1)動作クロック周波数Fを上げる、(2)反復回数Nを少なくする、(3)復号処理の所要サイクル数Yを少なくする、ことの3つが考えられる。
【0012】
しかし、動作クロック周波数Fの高速化は、半導体回路技術の進歩を待つ必要があり、復号器自体の改良で対処できる範疇の方策ではない。
また、復号処理の反復回数Nを少なくすると、復号精度を低下させるため、復号精度を下げてまで、復号器の処理能力を上げるという方策は、採用し難いものである。具体的には、反復回数は最悪の場合で、例えば10回程度は確保したいところである。
【0013】
そうすると、上記式の観点からは、1回の復号処理の所要サイクル数(所要クロック数)Yを、小さくすることが、処理能力向上のための復号器自体の改良としては、現実的な唯一の方策となる。
【0014】
しかし、復号処理の所要サイクル数Yを小さくするにしても、復号処理の所要サイクル数Yは、「1」が最小値であるから、当該所要サイクル数を「1」にしてしまうと、それ以上の処理能力向上が図れない。つまり、上記数値例によって求めた10[Gbit/s]程度が、現実的な限界処理能力(限界速度)となってしまう。
【0015】
もっとも、復号処理の反復回数分の複数の復号処理部(例えば、10個の復号処理部)を並べた復号器(「超全並列復号器」というものとする)であれば、個々の復号処理部では、復号処理を反復させずに、複数の復号処理部においてパイプライン処理を行い、全体として処理能力を向上させることも考えられる。この場合、反復がないため、処理能力をさらに向上させることができる。
しかし、復号処理部は、元来、大規模な回路であり、そのような復号処理部を複数具備させることは、回路規模が非現実的なほど大きくなってしまう。
したがって、超全並列復号器も、現実的な方策ではない。
【0016】
そこで、本発明は、復号処理部において復号処理の反復を行いつつも、処理能力を向上させることができる復号器等を提供することを目的とする。
【課題を解決するための手段】
【0017】
(1)本発明は、復号処理部が、符号化された入力データに対する復号処理を反復して行う復号器であって、前記復号処理部は、反復の対象である前記復号処理が分割された複数の部分処理を、復号処理部の動作クロックに従って順次実行するための複数のステージを有し、前記複数のステージは、前記復号処理における最初の部分処理を実行する先頭ステージと、前記復号処理における最後の部分処理を実行する最終ステージと、を含み、前記復号処理を反復できるように、前記最終ステージの出力を前記先頭ステージに与えるべく、前記最終ステージと前記先頭ステージとが接続されており、先に前記復号処理部に入力された入力データに対する復号処理の反復が終了する前のタイミングであって、先に前記復号処理部に入力された入力データについての処理データが、前記先頭ステージ以外のステージに存在しているタイミングにおいて、新たな入力データが前記先頭ステージにおいて処理されるよう構成されていることを特徴とする復号器である。
【0018】
上記本発明によれば、ある入力データについての復号処理の反復の終了を待つことなく、次の入力データの復号処理を開始することができる。したがって、復号器の処理能力を向上させることができる。
【0019】
(2)前記入力データが前記復号処理部に与えられる入力時間間隔を、Xとし、
復号処理の反復時間間隔を、Yとし、
復号処理の反復可能回数を、Nとしたときに、
下記式を満たすように構成されている復号器であるのが好ましい。
式 : (Y × N) < XとYの最小公倍数
この場合、データの衝突を確実に回避することができる。
【0020】
(3)上記(2)において、前記Xと前記Yは互いに素であるのが好ましい。この場合、XとYの最小公倍数が大きくなり、Y×Nを大きくとることができる。
【0021】
(4)前記復号処理部の動作クロック周波数を調整して、前記入力データが前記復号処理部に与えられる入力時間間隔を調整する手段を備えているのが好ましい。この場合、動作クロック周波数の調整で、入力時間間隔を調整することができる。
【発明の効果】
【0022】
本発明によれば、復号処理部において復号処理の反復を行いつつも、処理能力を向上させることができる。
【発明を実施するための最良の形態】
【0023】
以下、図面を参照しつつ、本発明の実施形態を説明する。
図1は、本発明の実施形態に係る復号器を有する、通信システムの構成例を示す図である。図1に示すように、この通信システムは、符号化データを送信する送信装置(送信側通信装置)Sと、符号化データを受信して復号する受信装置(受信側通信装置)Rとを備えている。
【0024】
上記送信装置Sは、送信情報に誤り訂正用の冗長ビットを付加して送信符号(符号化データ)を生成する符号化器1と、この符号化器1からの(K+M)ビットの符号を所定の方式に従って変調して通信路3へ出力する変調器2とを含む。
符号化器1は、Kビットの情報に対し、パリティ計算用の冗長ビットMビットを付加して、(K+M)ビットのLDPC(低密度パリティ検査)符号化データを生成する。低密度パリティ検査行列においては、行が冗長ビットに対応し、列が符号ビットに対応する。
【0025】
なお、(K+M)ビットのLDPC符号化データのどのビットに、K個の情報ビット及びM個の冗長ビットを配置するかは、送信側と受信側で取り決めていれば、どのように配置してもよい。
変調器2は、この通信路3の構成に応じて、振幅変調、位相変調、コード変調、周波数変調または直交周波数分割多重変調などの変調を行なう。
【0026】
例えば、通信路3が光ファイバの場合、変調器2においては、レーザダイオードの輝度を送信情報ビット値に応じて変更させることにより、光の強度変調(一種の振幅変調)を行なっている。すなわち、送信データビットが“0”の場合には、”+1”に変換して、レーザダイオードの発光強度を強くして送信し、また送信データビットが“1”の場合、”−1”に変換して、レーザダイオードの発光強度を弱くして送信する。
【0027】
前記受信装置Rは、通信路3を介して送信された変調信号に復調処理を施して、(K+M)ビットのデジタル符号を復調する復調器4と、この復調器4からの(K+M)ビットの符号にパリティ検査行列に基づく復号処理を施して元のKビットの情報を再生する復号器5とを備えている。
復調器4は、この通信路3における送信形態に応じて復調処理を行なう。例えば、振幅変調、位相変調、コード変調、周波数変調および直交周波数分割多重変調等の場合、復調器4において、振幅復調、位相復調、コード復調、および周波数復調等の処理が行なわれる。
【0028】
図2は、通信路3が光ファイバである場合の、変調器2及び復調器4の出力データの対応関係を一覧にして示す図である。
図2において、上述のように、通信路3が光ファイバの場合、変調器2においては、送信データが“0”のときには、”1”に変換され、送信用のレーザダイオード(発光ダイオード)の発光強度が強くなり、また送信データビットが“1”のときには、”−1”に変換され、レーザダイオードの発光強度を弱くして送信する。
【0029】
この通信路3における伝送損失等により、復調器4に伝達される光強度は、最も強い強度から最も弱い強度までの間のアナログ的な強度分布を有する。復調器4においては、この入力された光信号に、量子化処理(アナログ/デジタル変換)を行なって、この受光レベルを検出する。
図2においては、8段階に受光レベルが量子化された場合の受信信号強度を示す。すなわち、受光レベルがデータ“7”のときには、発光強度がかなり強く、受光レベルが“0”のときには、光強度がかなり弱い状態である。
【0030】
各受光レベルは符号付きデータに対応づけられ、復調器4から出力される。この復調器4の出力は、受光レベルが“7”のときにはデータ“3”が出力され、受光レベルが“0”のときには、データ“−4”が出力される。従って、この復調器4からは、1ビットの受信信号に対し、多値量子化された信号が出力される。
復号器5は、この復調器4から与えられた(K+M)ビットの受信符号化データ(各ビットは、多値情報を含む)の入力を受け、サムプロダクト(sum-product)復号法、或いは、これの変形アルゴリズムであるミニサム(min-sum)復号法又はファーストミニサム(fast mini-sum)復号法に従ってLDPCパリティ検査行列を適用して、元のKビットの情報を復元(誤り訂正)する。
【0031】
なお、この図2においては、復調器4において、8レベルに量子化されたビットが生成されている。しかしながら、一般に、この復調器4においては、L値(L≧2)に量子化されたビットを用いて復号処理を行なうことができる。
また、図2においては、比較器を用いて、ある閾値を使って受信信号のレベルを判定し、2値信号を生成してもよい。
【0032】
図3は、上記復号器5の基本機能を概略的に示す図である。
この図3においては、復調器4および通信路3も併せて示している。
復調器4は、通信路3から与えられた信号を復調する復調回路4aと、この復調回路4aにより生成されたアナログ復調信号をデジタル信号に変換するアナログ/デジタル変換回路4bを含み、このアナログ/デジタル変換回路4bの出力データ(符号化データ)Xnが復号器5へ与えられる。
【0033】
復号器5へ与えられる符号化データXnはL値(L≧2)のデータである。この符号化データXnは多値量子化データであるため、以下においては、当該データXnをシンボルと称することがある。
【0034】
復号器5は、上記入力シンボルXnに対して、いわゆるサムプロダクト復号法、ミニサム復号法などの復号法に従って復号処理を行ない、符号ビットCnを復号データとして生成する。
また、復号器5は、復調器4からの復調シンボルXnの対数尤度比λnを生成する対数尤度比算出部6(単に、算出部6と表記することがある。)と、算出部6から出力されたシリアルの対数尤度比λnを、符号長分のパラレルデータに変換するS/P変換部7、パラレルの対数尤度比λnのデータを複数個記憶できる対数尤度比記憶部8と、パラレルの対数尤度比λnを入力データとして復号処理を行う復号処理部11(単に、処理部11と表記することがある。)と、を含む。
【0035】
対数尤度比λnの算出部6は、上記受信信号のノイズ情報と独立に、対数尤度比λnを生成する。通常、ノイズ情報を考慮した場合には、対数尤度比λnは、Xn/(2・σ・σ)で与えられる。ここで、σはノイズの分散を示す。
しかし、本実施形態においては、この対数尤度比算出部6は、定数乗算回路で形成され、対数尤度比λnは、Xn・fで与えられる。ここで、fは非ゼロの正の数である。
【0036】
前記復号処理部11は、パリティ検査行列の行処理を行処理部9と、パリティ検査行列の列処理を行う列処理部10とを備えている。
本実施形態の復号処理部11は、列処理部10の出力が行処理部9にフィードバック入力されるようになっている。すなわち、行処理部9と列処理部10とは、ループ状に接続されている。
【0037】
復号法がサムプロダクト復号法である場合、行処理部9及び列処理部10は、次の式(1)及び(2)に従って演算処理を行い、パリティ検査行列の行の各要素についての処理(行処理)と、列についての各要素についての処理(列処理)を繰り返し実行する。
具体的には、行処理部9が、式(1)による外部値対数比(第1変数)αmnを算出する演算を行い、列処理部10が、式(2)による事前値対数比βmnを算出する演算を行う。
【数1】

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

【0039】
また、集合A(m)およびB(n)は、2元M・N行列 H=[Hmn]を復号対象のLDPC符号の検査行列とした場合、集合[1,N]={1,2,…,N}の部分集合である。
A(m)={n:Hmn=1} …(4)
B(n)={m:Hmn=1} …(5)
【0040】
すなわち、上記部分集合A(m)は、検査行列Hの第m行目において1(非零要素)が立っている列インデックスの集合を意味し、部分集合B(n)は、検査行列Hの第n列目において1(非零要素)が立っている行インデックスの集合を示す。
より具体的に説明するために、例えば図4に示す検査行列Hを考える。
この図4の検査行列Hにおいては、第1行の第1列から第3列に“1”が立ち、また第2行の第3列および第4列に“1”が立ち、また第3行の第4列から第6列に、“1”が立つ。従って、この場合、部分集合A(m)は以下のようになる。
【0041】
A(1)={1,2,3}
A(2)={3,4}
A(3)={4,5,6}
【0042】
同様に、部分集合B(n)については、以下のようになる。
B(1)=B(2)={1}
B(3)={1,2}
B(4)={2,3}
B(5)=B(6)={3}
【0043】
この検査行列Hにおいて、タナー(Tanner)グラフを用いた場合、列に対応する変数ノードと行に対応するチェックノードの接続関係が、この“1”により示される。これを、本明細書においては「“1”が立つ」と称している。
すなわち、図5に示すように、変数ノード1,2,3は、チェックノードX(第1行)に接続され、変数ノード3,4が、チェックノードY(第2行)に接続される。変数ノード4,5,6が、チェックノードZ(第3行)に接続される。
【0044】
この変数ノードが検査行列Hの列に対応し、チェックノードX,YおよびZが、この検査行列Hの各行に対応する。従って、図4に示す検査行列は、情報ビットが3ビット、冗長ビットが3ビットの合計6ビットの符号長の符号に対して適用される。
LDPCの検査行列Hでは、“1”の数は少なく、低密度の検査行列であり、これにより、計算量を低減できる。この変数ノードとチェックノードの間で各条件確率P(Xi|Yi)を伝播させ、MAPアルゴリズムに従って、尤もらしい符号を各変数ノードについて決定する。ここで、条件付確率P(Xi|Yi)は、Yiの条件下でXiとなる確率を示す。
【0045】
一方、復号法がミニサム復号法である場合には、行処理部9及び列処理部10は、次の式(6)及び(7)に従って演算処理を行う。
【数3】

【0046】
式(1)と式(6)とを比較すれば明らかな通り、ミニサム復号法は、外部値対数比αmnの演算において、ギャラガのf関数に関する項を近似値に置き換えたものであり、これによって演算負荷が軽減される。従って、ミニサム復号法はサムプロダクト復号法の簡易な実装形式の一つである。
なお、式(6)において、関数minは最小値を求める演算子である。また、サムプロダクト復号法の式(2)とミニサム復号法の式(7)とは同じものである。
【0047】
図3に示すように、前記復号器5は、行処理及び列処理からなる復号演算の反復終了を判定する判定部12を備えている。
この判定部13は、行処理及び列処理からなる復号処理(復号演算)の反復回数が、終了回数に達したか否かを判定し、行処理と列処理の反復回数が終了回数に達すると、復号処理部11による復号処理の反復を終了させる。なお、反復回数が、所定の終了回数に達する前であっても、十分な精度の復号結果が得られた場合には、反復を打ち切るように反復を制御してもよい。
【0048】
判定部12は、復号演算の反復が終了した後、外部値対数比αmn(または事前値対数比βmn)と対数尤度比λnとを用いて符号を判定する機能を有している。
具体的には、判定部12は、次の式(8)に従ってQnを算出する。
【数4】

【0049】
更に、判定部12は、次の式(9)に従って、復号データである推定符号Cnを算出する。
【数5】

【0050】
算出された推定符号Cn(パラレルデータ)は、P/S変換部13によって、シリアルデータに変換され、復号器5から出力される。
【0051】
次に、上述の復号器5の基本機能を前提とし、図6に基づき、本実施形態の復号器5を更に詳細に説明する。
図3の復号処理部11においては、機能的な面に着目して、行処理部9と列処理部10とを書き分けたが、図6では、復号処理部11のハードウェア構成として分けられる複数のステージを示した。本実施形態の復号処理部11は、3つのステージ11a,11b,11cを有している。
これら3つのステージ11a,11b,11cは、それぞれ、1回の復号処理(1回の行処理及び1回の列処理)が分割された部分処理を実行するためのものである。例えば、複数のステージのうち、先頭ステージ11aは行処理の前半を実行し、第2ステージ11bは、行処理の後半を実行し、最終ステージ11cは、列処理全体を実行するものとする。
【0052】
前記先頭ステージ11aは、対数尤度比記憶部8から出力されたλnと、最終ステージ11cから出力されたβmn(初期値は0)との和を入力として受け付けるため、最終ステージ11cの出力と、先頭ステージ11aの入力とは、λnとβmnを加算するための加算部16を介して接続されている。これにより、復号処理部11は、最終ステージ11cの出力βmnに基づいて、復号処理を反復して行うことができる。
なお、加算部16は、先頭ステージ11aの一部として考えても良い。このように考えた場合、先頭ステージ11aは、λnとβmnとをそれぞれ入力として受け付けることになる。
【0053】
上記の各ステージ11a,11b,11cは、動作クロック15に従って、各ステージにおける処理を順次実行する。つまり、各ステージ11a,11b,11cに与えられた各入力に基づいて、各ステージが処理結果を出力するには、1クロックを要するようよう構成されている。
したがって、図6の復号処理部11では、1回の復号処理(1回の反復処理)を完了するのに、3クロック(3サイクル)要する。
【0054】
なお、サムプロダクト復号法やミニサム復号法において、列処理は、足し算だけで行える。足し算は、順序回路を用いなくても、組み合わせ論理回路によって実現可能である。組み合わせ論理回路によって構成された列処理回路では、入力が与えられると、クロックを待つことなく、演算結果が出力される。
一方、本実施形態に係るステージ11a,11b,11cは、クロックが与えられたときの入力に応じて、当該ステージが担当する部分処理に係る演算を行い、その演算結果を出力するものである。
したがって、列処理を行う前記最終ステージ11cには、組み合わせ論理回路によって構成された列処理回路に加えて、クロックを待ってから出力するためのメモリが付加されることになる。
【0055】
なお、図6におけるステージ数は、単なる例示であって、これに限定されるものではない。ステージ数は、2つであってもよいし、4以上であってもよい。
また、復号処理が複数のステージによって実行されていれば足り、行処理及び/又は列処理が分割されている必要はない。例えば、行処理及び列処理を1クロック(1サイクル)で実行できる一つのステージと、遅延回路からなる1又は複数のステージとで、複数のステージを構成してもよい。
さらに、行処理や列処理を分割する場合、分割された部分処理それぞれは、機能的に意味のある単位である必要はない。
【0056】
また、前記対数尤度比記憶部(入力データ記憶部)8は、先頭ステージ11aの入力に与えるための対数尤度比λn(パラレルデータ)を記憶するものである。この対数尤度比記憶部8から出力された対数尤度比(入力データ)λnが、先頭ステージ11a又はその他のステージに与えられ、先頭ステージ11a等における演算に用いられる。
この対数尤度比記憶部8は、複数の対数尤度比(パラレルデータ)λn−A,λn−B,λn−Cを蓄積することができ、蓄積された複数の対数尤度比のうちの一の対数尤度比を、選択的に、必要なステージ11aに与えることができる。対数尤度比記憶部8では、復号処理部11において処理対象となっている入力データ(対数尤度比)を全て記憶できるように、対数尤度比記憶部8に記憶可能な対数尤度比の数は、ステージ数以上の数に設定される。
【0057】
対数尤度比記憶部8から、先頭ステージ11aに出力される対数尤度比は、制御部14によって選択される。制御部14は、記憶された複数の対数尤度比のうち、先頭ステージ11a等における演算に必要とされる対数尤度比を選択して、記憶部8から出力させる。
なお、図6においては、動作クロック15によって動作する範囲を、反復処理部20として示した。反復処理部20には、対数尤度比記憶部8、復号処理部11、判定部12、制御部14など反復処理に必要なものが含まれる。
【0058】
図7は、図6の反復処理部20において、パラレルの入力データ(対数尤度比λn)が、入力される入力間隔Xを示している。ここでは、LDPC符号の符号長を550bitとし、受信機Rの通信路の伝送速度を10Gbit/sとする。
この場合、反復処理部20における動作クロック15の周波数(処理速度)を200MHzとした場合、S/P変換部から、復号処理部11の処理対象とするパラレルの入力データ(対数尤度比λn)が、S/P変換部7から出力されて反復処理部20に与えられる間隔(入力間隔)Xは、下記式のように、11サイクル(11クロック)となる。
入力間隔X=(550bit/10GHz)/(1/200MHz)=11サイクル
【0059】
図7は、上記例における入力間隔Xを示している。図7の横軸の一目盛りは、1サイクル(動作クロック15の1クロック)であり、11サイクルごとに、入力データが、発生し、復号処理部11の先頭ステージ11aに与えられる。
【0060】
図8及び図9は、本実施形態の復号処理部11の処理の流れを示している。図8及び図9において、ループ状に接続された3つの丸が、先頭ステージ11a、第2ステージ11b、最終ステージ11cを示している。また、内部数字付きの□は第1入力データついての当該ステージでの処理データ、内部数字付きの△は第2入力データについての当該ステージでの処理データ、内部数字付きの○は第3入力データについての当該ステージでの処理データ、内部数字付きの◇は第4入力データについての当該ステージでの処理データを示している。□、△、○、◇内の各数値は、復号処理の反復回数を示している。
【0061】
まず、CLK=0において、先頭ステージ11aの入力側に、第1入力データ□が与えられ、CLK=1〜CLK3の間に、1回目の復号処理がおこなわれる。CLK=1では、復号処理のうち、先頭ステージ11aが分担する部分処理の演算が行われ、その処理結果が、先頭ステージ11aから出力される。CLK=2では、復号処理のうち、第2ステージ11bが分担する部分処理の演算が行われ、その処理結果が、第2ステージ11bから出力される。CLK=3では、復号処理のうち、最終ステージ11cが分担する部分処理の演算が行われ、その処理結果(βmn)が最終ステージ11cから出力され、先頭ステージ11a側に与えられる。以上によって、復号処理の1回目の復号処理が完了する。
【0062】
さらに、CLK=4〜CLK=6の間に、第1入力データ□についての2回目の復号処理がおこなわれる。CLK=4では、1回目の復号処理の演算結果(βmn)と、対数尤度比記憶部8から選択的に出力される第1入力データとしての対数尤度比λnとから、先頭ステージ11aにおける部分演算が行われ、以下、1回目の復号処理と同様の処理が行われる。
【0063】
さらに、CLK=7〜CLK9の間に、第1入力データ□についての3回目の復号処理がおこなわれ、CLK=10〜CLK12の間に、第1入力データ□についての4回目の復号処理が行われる。以上の間において、対数尤度比記憶部8からは、常時、第1入力データとしての対数尤度比λnが出力されている。
【0064】
4回目の復号処理中であるCLK=11において、対数尤度比記憶部8から先頭ステージ11aの入力側に、新たな入力データとして、第2入力データ△が与えられ、CLK=12において、第2入力データ△に対する先頭ステージ11aの演算(1回目の復号処理)が行われる。このCLK=12の時点で、第1入力データ□についての処理データは、最終ステージ11cに存在するため、第1入力データの処理データと第2入力データの処理データとの衝突が回避されている。
【0065】
CLK=13では、第1入力データ□についての5回目の復号処理のうち、先頭ステージ11aにおける演算が実行される。このとき、先頭ステージ11aにおける演算に用いるため、対数尤度比記憶部8からは、第1入力データとしての対数尤度比λnが選択的に出力されている。
また、図示はしないが、CLK=15などで、先頭ステージ11aにおいて第2入力データ△についての処理が行われる場合には、対数尤度比記憶部8からは、第2入力データとしての対数尤度比λnが選択的に出力される。
【0066】
以上のようにして、CLK=16〜CLK=18においては、第1入力データについての6回目の復号処理が行われ、CLK=19〜CLK=21においては、第1入力データについての7回目の復号処理が行われる。また、これと同時に、第2入力データについての第2〜第4回目の復号処理も進行する。
【0067】
さらに、CLK=22〜CLK=24では、第1入力データについての8回目の復号処理が行われる。この8回目の復号処理中であるCLK=22において、対数尤度比記憶部8から先頭ステージ11aの入力側に、新たな入力データとして、第3入力データ○が与えられ、CLK=23において、第3入力データ○に対する先頭ステージ11aの演算(1回目の復号処理)が行われる。
このCLK=23の時点で、第1入力データ□についての処理データは、第2ステージ11bに存在し、第2入力データ△についての処理データは最終ステージ11cに存在するめ、新たな入力データである第3入力データについての処理データと、先に入力された第1及び第2データの処理データとの衝突が回避されている。
【0068】
CLK=24では、第2入力データ△についての5回目の復号処理のうち、先頭ステージ11aにおける演算が実行される。このとき、先頭ステージ11aにおける演算に用いるため、対数尤度比記憶部8からは、第2入力データとしての対数尤度比λnが選択的に出力されている。
また、CLK=25,28などで、先頭ステージ11aにおいて第1入力データ□についての処理が行われる場合には、対数尤度比記憶部8からは、第1入力データとしての対数尤度比λnが選択的に出力される。
また、CLK=26,29などで、先頭ステージ11aにおいて第3入力データ○についての処理が行われる場合には、対数尤度比記憶部8からは、第3入力データとしての対数尤度比λnが選択的に出力される。
【0069】
以上のようにして、CLK=25〜CLK=27においては、第1入力データ□についての9回目の復号処理が行われ、CLK=28〜CLK=30においては、第1入力データ□についての10回目の復号処理が行われる。また、これと同時に、第2入力データ△についての第5〜第7回目の復号処理と、第3入力データ○についての第1〜第3回目の復号処理が進行する。
【0070】
CLK=30では、対数尤度比記憶部8から先頭ステージ11aの入力側に、新たな入力データとして、第4入力データ◇が与えられ、CLK=31において、第4入力データ◇に対する先頭ステージ11aの演算(1回目の復号処理)が行われる。
CLK=30の時点では、第1入力データ□についての10回目(反復回数の上限)の復号処理の最終ステージ11cにおける処理が完了している。このため、第1入力データについての処理データは、破棄され、先頭ステージ11aの入力に反映されない。したがって、次のCLK=31の時点では、先頭ステージ11aには、処理中のデータが存在しない。
したがって、新たに入力された第4入力データと、先に入力されたデータとの衝突が回避されている。
【0071】
以上のように、本実施形態の復号処理部11では、先に入力されたデータについての処理データと、新たに入力されたデータとの衝突が回避されているため、一つの入力データについての反復復号処理が完了する前に、次のデータを復号処理部11に受け入れて、複数(3つ)の入力データを処理することができる。
【0072】
したがって、多数の入力データを処理する場合、本実施形態に係る復号器5の処理速度は、(動作クロック15の周波数)×(符号長)のオーダーとなり、復号処理の反復回数Nや、1回の復号処理の所要サイクル数(所要クロック数)Yによる処理速度劣化が生じない。
【0073】
また、本実施形態の復号処理部11では、入力データを復号処理部11へ与えるタイミングの制御など特別な制御を行うことなくても、データの衝突を回避できる。つまり、本実施形態では、順次発生する入力データを復号処理部11にて、単に順次処理しても、先に復号処理部11に入力されたデータについての処理データと、新たに入力されたデータとの衝突を回避することができる。
【0074】
この衝突を回避するための条件は、下記条件式の通りである。
条件式 : (Y × N) < XとYの最小公倍数
X:入力データが先頭ステージに与えられる入力時間間隔
Y:復号処理の反復時間間隔(ステージ数)
N:復号処理の反復可能回数
なお、図6の例では、X=11、Y=3、N=10であった。
【0075】
上記条件式の左辺である「Y×N」は、一つの入力データについての処理データが、反復される復号処理のために復号処理部11内に滞留する最大時間である。
また、上記条件式の右辺である「XとYの最小公倍数」=LCM(Y,X)は、復号処理部11への入力が、復号処理部における反復と衝突する間隔である。
LCM(Y,X)で求まる衝突間隔よりも、ある入力データについての処理データが、反復される復号処理のために復号処理部11内に滞留する最大時間を短くすることで、衝突が発生する前に、復号処理部11のステージを新たな入力データに開放することができ、データの衝突を防止できる。
【0076】
なお、図6の例では、LCM(3,11)=33サイクルである。33サイクル目(CLK=33)は、第1入力データについてみると、11回目の反復に相当するが、図6の例では、最大の反復回数Nを10に設定しているため、図9に示すように、衝突が発生する11回目の反復の前(10回目の反復終了時)に、第1入力データについての処理データが復号処理部11内から消去され、衝突が回避されている。
【0077】
上記条件式を満たすように、X,Y,Nの各値を設定することで、処理速度に優れた復号器を設計することができる。このとき、反復可能回数数Nを大きくとるため、X,Yは互いに素であるのが好ましい。XとYが互いに素であれば、LCM(Y,X)が大きくなり、反復可能回数Nも大きくとれる。
【0078】
上記本実施形態によれば、復号処理部11において1回の復号処理を実行する時間Yを最小値「1」にしなくても、処理の高速化が実現でき、復号処理部11の設計が容易になる。
【0079】
ここで、復号器5の設計の際に、所望の反復回数Nをまず決めた場合、所定の入力間隔Xのときに、所望の反復回数Nを得るための最小の復号処理の反復間隔(ステージ数)Yを設定すればよい。
【0080】
また、復号器5の設計の際に、入力間隔Xを調整するには、復号処理部11の設計を変更せずに、動作クロック15の周波数を調整してもよい。
【0081】
(例1)
例えば、図6の復号器5の設計後に、図6通信路4の伝送速度を上げたくなった場合を考える。伝送速度が上がった場合、同じ動作クロック周波数であれば、S/P変換部7からパラレルの入力データが出力されるサイクル間隔(クロック数)は、小さくなる。
仮に、図6においてX=11であった入力間隔Xが9サイクルになった場合、LCM(Y,X)=LCM(3,9)=9である。この場合、反復可能回数Nの最大値を、上記条件式から求めると、反復可能回数N=2となる。
【0082】
つまり、条件式:(Y × N) < XとYの最小公倍数
3 × N < LCM(3,9)=9
N < 3
【0083】
(例2)
また、図6通信路4の伝送速度をさらに上げたくなった場合を考える。さらに伝送速度が上がった場合、同じ動作クロック周波数であれば、S/P変換部7からパラレルの入力データが出力されるサイクル間隔(クロック数)は、さらに小さくなる。ここでは、仮に、入力間隔X=8になったとする。この場合、反復可能回数N=8となる。
【0084】
この場合、条件式:(Y × N) < XとYの最小公倍数
3 × N < LCM(3,8)=24
N < 9
【0085】
図6の場合では10回の反復回数が確保できていたのに、上記例1では、伝送速度が高速になったために、反復可能回数Nが減少した。この結果、反復回数の不足のため復号精度が低下することになる。一方、上記例2では、例1よりも伝送速度を更に上げると、反復可能回数Nが、例1よりも大きくなった。
【0086】
そこで、例1の場合、動作クロック15の周波数を低下させて、復号処理部15の動作速度を低下させて、入力間隔Xを9よりも更に低下させ、例2のようにX=8とすることで、例2のように、反復可能回数N=8とすることができる。このように、動作クロックの周波数の変更によって、復号処理部11の構成を変更せずに、反復可能回数Nとして適切な数値を確保できる。
【0087】
また、例1,2とは逆に、伝送速度が低速になった場合は、入力間隔Xが大きくなる。入力間隔Xが大きくなって、LCM(Y,X)も大きくなった場合、反復可能回数Nも多くとれることになるが、反復は、ある程度の回数(例、10回)を行うと、それ以上の復元精度向上を期待できず、あまり多い反復は必要とされない。
そこで、伝送速度が低速になった場合、十分な反復回数が確保できる場合には、故意に、動作クロック15の周波数を低下させて、入力間隔Xが大きくなるのを抑制する(例えば、X=11を維持する)ことができる。この場合、動作クロック周波数が低くできるため、復号器5の消費電力を抑えることができる。
【0088】
なお、本実施形態では、制御部14は、通信路の伝送速度に応じて、動作クロック15の周波数を調整する機能を有している。したがって、復号器5の動作時において、入力間隔(サイクル数)Xを動的に調整して、必要な反復回数を確保したり、復号器5の消費電力を低減させることができる。
【0089】
これまで開示した実施形態はすべて例示であって制限的なものではない。本発明の範囲は特許請求の範囲によって示され、特許請求の範囲の構成と均等の範囲内のすべての変更が本発明に含まれる。
例えば、本発明の復号器の復号器は、LDPC符号の復号器に限られるものではなく、ターボ復号器のように他の反復復号型の復号器であってもよい。
また、上記実施形態では、復号処理部11の外部にある対数尤度比記憶部8から、先頭ステージ11aに対数尤度比λnを与えたが、各ステージ11a,11,11cがλnの記憶部を備えておき、処理対象となっている入力データについての対数尤度比λnを、処理データの一部としてとして、各ステージ11a,11b,11cが保持できるようにしてもよい。また、復号処理として、1回目の反復では対数尤度比を用いるが、2回目の反復では対数尤度比λnを用いない方式を採用する場合、対数尤度比記憶部8は不要である。
さらに、上記実施形態では、復号処理部11は、全並列型のものを示したが、部分並列型であってもよい。
【図面の簡単な説明】
【0090】
【図1】第一実施形態の通信システムの概略構成図である。
【図2】送信データと復調データの対応の一例を示す図である。
【図3】復号器の構成図である。
【図4】検査行列の一例を示す図である。
【図5】図4に示す検査行列のタナーグラフである。
【図6】復号器の詳細な構成図である。
【図7】復号処理部への入力間隔の説明図である。
【図8】復号処理部での処理の流れを示す図である。
【図9】復号処理部での処理の流れを示す図である。
【図10】反復復号処理を行う復号器の基本構成図である。
【符号の説明】
【0091】
1:符号化器 2:変調器 3:通信路 4:復調器
4a:復調回路 4b:アナログ/デジタル変換回路
5:復号器 6:対数尤度比算出部 7:S/P変換部 8:対数尤度比記憶部
9:行処理部 10:列処理部 11:復号処理部 11a:先頭ステージ
11b:第2ステージ 11c:最終ステージ 12:判定部
13:P/S変換部 14:制御部 15:動作クロック 16:加算部
20:反復処理部 S:送信装置 R:受信装置 Xn:符号化データ
Cn:復号データ λn:対数尤度比

【特許請求の範囲】
【請求項1】
復号処理部が、符号化された入力データに対する復号処理を反復して行う復号器であって、
前記復号処理部は、反復の対象である前記復号処理が分割された複数の部分処理を、復号処理部の動作クロックに従って順次実行するための複数のステージを有し、
前記複数のステージは、前記復号処理における最初の部分処理を実行する先頭ステージと、前記復号処理における最後の部分処理を実行する最終ステージと、を含み、
前記復号処理を反復できるように、前記最終ステージの出力を前記先頭ステージに与えるべく、前記最終ステージと前記先頭ステージとが接続されており、
先に前記復号処理部に入力された入力データに対する復号処理の反復が終了する前のタイミングであって、先に前記復号処理部に入力された入力データについての処理データが、前記先頭ステージ以外のステージに存在しているタイミングにおいて、新たな入力データが前記先頭ステージにおいて処理されるよう構成されている
ことを特徴とする復号器。
【請求項2】
前記入力データが前記復号処理部に与えられる入力時間間隔を、Xとし、
復号処理の反復時間間隔を、Yとし、
復号処理の反復可能回数を、Nとしたときに、
下記式を満たすように構成されていることを特徴とする請求項1記載の復号器。
式 : (Y × N) < XとYの最小公倍数
【請求項3】
前記Xと前記Yは互いに素である請求項2記載の復号器。
【請求項4】
前記復号処理部の動作クロック周波数を調整して、前記入力データが前記復号処理部に与えられる入力時間間隔を調整する手段を備えていることを特徴とする請求項1〜3のいずれか1項に記載の復号器。

【図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