図面 (/)

技術 低密度パリティチェック符号復号装置及び方法

出願人 株式会社モバイルテクノ
発明者 杉谷敦彦
出願日 2006年8月21日 (14年4ヶ月経過) 出願番号 2006-224431
公開日 2008年2月28日 (12年9ヶ月経過) 公開番号 2008-048346
状態 特許登録済
技術分野 符号誤り検出・訂正
主要キーワード 多面構成 監視サイクル 繰返しカウンタ パリティ判定 行処理結果 確率伝搬 パリティチェック結果 ブロック番
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2008年2月28日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (6)

課題

品質下げることなく処理スループットを向上させるLDPC符号復号装置を提供する。

解決手段

本発明は、LDPC符号における復号アルゴリズムとして、行処理毎に復号結果を更新するアルゴリズムを適用した装置である。そして、復号処理を実行する復号処理手段と、復号するLDPC符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持する処理待ち情報保持手段と、この処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、復号処理手段に、対象となる行の復号処理の開始を指示する開始指示延期手段とを有することを特徴とする。

概要

背景

LDPC符号における復号アルゴリズムとして、Belief Propagation(BP)アルゴリズムが知られている(非特許文献1参照)。BPアルゴリズムは、(1)式〜(3)式に示す行処理と、(4)式に示す列処理とを繰り返すことにより、信頼度更新を行う確率伝搬アルゴリズムである。

ここで、iは復号繰返し数、Zinはn番目ビットにおけるi回復号処理を行った後の事後対尤度比(事後LLR)、Fnは通信路値、Rimnはm行のn番目のビットにおけるi回復号処理を行った後の行処理結果である(初期値Z0n=Fn、R0mn=0)。

BPアルゴリズムを適用した復号方法では、上式に示すように、事後LLRを復号繰返し毎に更新するものである。

これに対し、非特許文献2に示されるTurbo Decoding Message Passing(TDMP)アルゴリズムは、上述した(1)式〜(4)式におけるiを、復号繰返し数ではなく、m番目の行の処理を行う時刻サイクル)として処理するアルゴリズムである。すなわち、事後LLRを行処理毎に更新するものである。TDMPアルゴリズムは収束特性に優れているため、BPアルゴリズムよりも少ない繰返し数で同等の誤り特性を得ることが知られている。
R.G.Gallager, “Low−Density Parity−Check Codes”, IRE Trans. Info. Theory, vol.IT−8, pp.21−28, 1962
M.M.Mansour and N.R.Shanbhag, “High Throughput LDPC Decoder,”IEEE Trans.VLSISystems, vol.11, No.6, Dec.2003

概要

品質下げることなく処理スループットを向上させるLDPC符号復号装置を提供する。 本発明は、LDPC符号における復号アルゴリズムとして、行処理毎に復号結果を更新するアルゴリズムを適用した装置である。そして、復号処理を実行する復号処理手段と、復号するLDPC符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持する処理待ち情報保持手段と、この処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、復号処理手段に、対象となる行の復号処理の開始を指示する開始指示延期手段とを有することを特徴とする。

目的

そのため、品質を下げることなく処理スループットを向上させることができる低密度パリティチェック(LDPC)符号復号装置及び方法が望まれている。

効果

実績

技術文献被引用数
2件
牽制数
2件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

低密度パリティチェック符号における復号アルゴリズムとして、行処理毎に復号結果を更新するアルゴリズムを適用した低密度パリティチェック符号復号装置であって、復号処理を実行する復号処理手段と、復号する低密度パリティチェック符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持する処理待ち情報保持手段と、この処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、上記復号処理手段に、対象となる行の復号処理の開始を指示する開始指示延期手段とを有することを特徴とする低密度パリティチェック符号復号装置。

請求項2

複数の復号ブロックの復号処理を並行的に実行する低密度パリティチェック符号復号装置であって、復号処理を実行する復号処理手段と、上記各復号ブロック毎に付与された優先度情報を保持する優先度情報保持手段と、復号処理に供する複数の復号ブロックに付与された優先度情報に基づき、上記復号処理手段が復号処理する復号ブロックを決定する処理復号ブロック決定手段とを有することを特徴とする低密度パリティチェック符号復号装置。

請求項3

上記復号処理手段は、行処理毎に復号結果を更新するアルゴリズムを適用したものであると共に、復号する低密度パリティチェック符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持する、各復号ブロック毎の処理待ち情報保持手段と、この処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、上記復号処理手段に、対象となる行の復号処理の開始を指示する、各復号ブロック毎の開始指示延期手段とをさらに備え、上記処理復号ブロック決定手段は、上記開始指示延期手段が指示を送出した復号ブロックの中から、その優先度情報に基づき、上記復号処理手段が復号処理する復号ブロックを決定することを特徴とする請求項2に記載の低密度パリティチェック符号復号装置。

請求項4

上記復号処理手段が復号処理を繰返す毎に処理を行った行に対するパリティチェックを行い、そのパリティチェック結果がOKとなる連続回数を測定する誤りなし連続回数計測手段と、上記連続回数が予め設定された値となったときに復号処理を終了させる終了指示手段とをさらに有することを特徴とする請求項1又は3に記載の低密度パリティチェック符号復号装置。

請求項5

低密度パリティチェック符号における復号アルゴリズムとして、行処理毎に復号結果を更新するアルゴリズムを適用した低密度パリティチェック符号復号方法であって、復号処理手段、処理待ち情報保持手段及び開始指示延期手段を有し、上記復号処理手段は復号処理を実行し、上記処理待ち情報保持手段は、復号する低密度パリティチェック符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持し、上記開始指示延期手段が、上記処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、上記復号処理手段に、対象となる行の復号処理の開始を指示することを特徴とする低密度パリティチェック符号復号方法。

請求項6

複数の復号ブロックの復号処理を並行的に実行する低密度パリティチェック符号復号方法であって、復号処理手段、優先度情報保持手段及び処理復号ブロック決定手段を有し、上記復号処理手段は復号処理を実行し、上記優先度情報保持手段は、上記各復号ブロック毎に付与された優先度情報を保持し、上記処理復号ブロック決定手段は、復号処理に供する複数の復号ブロックに付与された優先度情報に基づき、上記復号処理手段が復号処理する復号ブロックを決定することを特徴とする低密度パリティチェック符号復号方法。

請求項7

上記復号処理手段は、行処理毎に復号結果を更新するアルゴリズムを適用したものであると共に、各復号ブロック毎の処理待ち情報保持手段及び各復号ブロック毎の開始指示延期手段をさらに有し、上記各処理待ち情報保持手段は、復号する低密度パリティチェック符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持し、上記各開始指示延期手段は、対応する処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、上記復号処理手段に、対象となる行の復号処理の開始を指示し、上記処理復号ブロック決定手段は、上記開始指示延期手段が指示を送出した復号ブロックの中から、その優先度情報に基づき、上記復号処理手段が復号処理する復号ブロックを決定することを特徴とする請求項6に記載の低密度パリティチェック符号復号方法。

請求項8

誤りなし連続回数計測手段及び終了指示手段をさらに有し、上記誤りなし連続回数計測手段は、上記復号処理手段が復号処理の繰返す毎に処理を行った行に対するパリティチェックを行い、そのパリティチェック結果がOKとなる連続回数を測定し、上記終了指示手段は、上記連続回数が予め設定された値となったときに復号処理を終了させることを特徴とする請求項5又は7に記載の低密度パリティチェック符号復号方法。

技術分野

0001

本発明は低密度パリティチェック(LDPC)符号復号装置及び方法に関し、特に、品質下げることなく処理スループットを向上しようにしたものである。

背景技術

0002

LDPC符号における復号アルゴリズムとして、Belief Propagation(BP)アルゴリズムが知られている(非特許文献1参照)。BPアルゴリズムは、(1)式〜(3)式に示す行処理と、(4)式に示す列処理とを繰り返すことにより、信頼度更新を行う確率伝搬アルゴリズムである。

0003

ここで、iは復号繰返し数、Zinはn番目ビットにおけるi回復号処理を行った後の事後対尤度比(事後LLR)、Fnは通信路値、Rimnはm行のn番目のビットにおけるi回復号処理を行った後の行処理結果である(初期値Z0n=Fn、R0mn=0)。

0004

BPアルゴリズムを適用した復号方法では、上式に示すように、事後LLRを復号繰返し毎に更新するものである。

0005

これに対し、非特許文献2に示されるTurbo Decoding Message Passing(TDMP)アルゴリズムは、上述した(1)式〜(4)式におけるiを、復号繰返し数ではなく、m番目の行の処理を行う時刻サイクル)として処理するアルゴリズムである。すなわち、事後LLRを行処理毎に更新するものである。TDMPアルゴリズムは収束特性に優れているため、BPアルゴリズムよりも少ない繰返し数で同等の誤り特性を得ることが知られている。
R.G.Gallager, “Low−Density Parity−Check Codes”, IRE Trans. Info. Theory, vol.IT−8, pp.21−28, 1962
M.M.Mansour and N.R.Shanbhag, “High Throughput LDPC Decoder,”IEEE Trans.VLSISystems, vol.11, No.6, Dec.2003

発明が解決しようとする課題

0006

しかしながら、TDMPアルゴリズムでは、行処理を行う際には、対象とする行に含まれるビットノードと同じビットノードを含む行及び列の処理が完了するまでの間はその行処理を行うことができない。

0007

また、TDMPアルゴリズムでも、設定されている繰返し数の復号処理を実行して復号処理を終了させる。しかしながら、当初から、誤りがほとんどないような場合には、所定数の繰返し数の復号処理が無駄になっていることもある。

0008

さらに、誤り検出を行う際には、一旦復号処理を停止して誤り検出を行う必要がある。このため、誤り検出処理時間分だけ、復号処理が遅くなり、頻繁に誤り検出処理を行えないという問題がある。

0009

そのため、品質を下げることなく処理スループットを向上させることができる低密度パリティチェック(LDPC)符号復号装置及び方法が望まれている。

課題を解決するための手段

0010

かかる課題を解決するため、第1の本発明は、低密度パリティチェック符号における復号アルゴリズムとして、行処理毎に復号結果を更新するアルゴリズムを適用した低密度パリティチェック符号復号装置であって、(1)復号処理を実行する復号処理手段と、(2)復号する低密度パリティチェック符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持する処理待ち情報保持手段と、(3)この処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、上記復号処理手段に、対象となる行の復号処理の開始を指示する開始指示延期手段とを有することを特徴とする。

0011

第2の本発明は、複数の復号ブロックの復号処理を並行的に実行する低密度パリティチェック符号復号装置であって、(1)復号処理を実行する復号処理手段と、(2)上記各復号ブロック毎に付与された優先度情報を保持する優先度情報保持手段と、(3)復号処理に供する複数の復号ブロックに付与された優先度情報に基づき、上記復号処理手段が復号処理する復号ブロックを決定する処理復号ブロック決定手段とを有することを特徴とする。

0012

第3の本発明は、低密度パリティチェック符号における復号アルゴリズムとして、行処理毎に復号結果を更新するアルゴリズムを適用した低密度パリティチェック符号復号方法であって、(0)復号処理手段、処理待ち情報保持手段及び開始指示延期手段を有し、(2)上記復号処理手段は復号処理を実行し、(1)上記処理待ち情報保持手段は、復号する低密度パリティチェック符号に対する検査行列の情報から定まる、対象となる行の前の行が復号処理を開始してから対象となる行が処理開始可能となる時間情報を保持し、(3)上記開始指示延期手段が、上記処理待ち情報保持手段が保持した時間情報分だけを少なくとも待って、上記復号処理手段に、対象となる行の復号処理の開始を指示することを特徴とする。

0013

第4の本発明は、複数の復号ブロックの復号処理を並行的に実行する低密度パリティチェック符号復号方法であって、(0)復号処理手段、優先度情報保持手段及び処理復号ブロック決定手段を有し、(1)上記復号処理手段は復号処理を実行し、(2)上記優先度情報保持手段は、上記各復号ブロック毎に付与された優先度情報を保持し、(3)上記処理復号ブロック決定手段は、復号処理に供する複数の復号ブロックに付与された優先度情報に基づき、上記復号処理手段が復号処理する復号ブロックを決定することを特徴とする。

発明の効果

0014

本発明の低密度パリティチェック符号復号装置及び方法によれば、品質を下げることなく処理スループットを向上させることができる。

発明を実施するための最良の形態

0015

(A)主たる実施形態
以下、本発明による低密度パリティチェック(LDPC)符号復号装置及び方法の一実施形態を、図面を参照しながら詳述する。

0016

(A−1)実施形態の構成
図1は、実施形態に係るLDPC符号復号装置の全体構成を示すブロック図であり、図2は、図1における復号処理制御部の詳細構成を示すブロック図である。

0017

図1において、実施形態のLDPC符号復号装置1は、復号器入力インタフェース部(復号器入力IF)10、Fn格納メモリ11、復号処理制御部12、セレクタ13、行処理回路14、第1のバッファ15、加算部16、Zn格納メモリ17、第2のバッファ18、Rmn格納メモリ19、第3のバッファ20、減算部21、硬判定部22、パリティ判定部23、硬判定データ格納メモリ24及び復号器出力インタフェース部(復号器出力IF)25を有する。

0018

復号器入力インタフェース部10は、各復号ブロックのデータ(通信路値)と各復号ブロックに関する復号情報を取り込み、通信路値をFn格納メモリ11に与え、復号情報を復号処理制御部12に与えるものである。

0019

ここで、復号ブロックとは、同一の検査行列を適用して復号を行うデータの固まり(復号対象)である。すなわち、この実施形態のLDPC符号復号装置1では、複数の復号ブロックに対して、時分割的に並行して復号を行うことができるものである。また、復号情報とは、(a)検査行列情報、(b)最大復号繰返し数、(c)優先度情報及び(d)パリティ監視サイクルである。検査行列情報は、その復号ブロックに係る検査行列の情報である。最大復号繰返し数は、復号処理を繰り返す繰り返し回数の上限数である。優先度情報とは、復号ブロック間の復号処理についての優先度の情報である。パリティ監視サイクルとは、処理を行った行に対するパリティチェック結果がOKとなった連続回数と比較される予め設定された値であり、OKの連続回数がパリティ監視サイクルとなったときに復号処理を終了させるように用いられるものである。

0020

Fn格納メモリ11は、復号器入力インタフェース部10を介して外部から与えられた通信路値を格納するものであり、また、復号処理制御部12の制御下で、格納している通信路値Fnを読み出してセレクタ13に与えるものである。

0021

復号処理制御部12は、復号処理を行うブロックと行を決定する機能を担っているものであり、図2に示すような詳細構成を有する。復号処理制御部12の詳細構成については後述する。

0022

セレクタ13は、復号処理制御部12の制御下で、Fn格納メモリ11から読み出されたデータ(通信路値)又は減算部21の出力データを選択し、行処理回路14及び第1のバッファ15に与えるものである。セレクタ13がFn格納メモリ11から読み出されたデータ(通信路値)を選択する場合は、上述した(1)式を最初(i−1=0)に演算する場合と、処理対象行等の通信路値Fnを第1のバッファ15に転送させる場合とである。

0023

行処理回路14は、上述した(2)式の演算を実行するものである。この実施形態の場合、行列処理演算方法には特徴はなく、その詳細な説明は省略する。(2)式の演算に必要な(3)式の演算は、ルックアップテーブルなどを利用して実行するものであっても良い。また、(2)式そのものではなく、(2)式の近似式を演算するものであっても良い。行処理回路14による行処理結果Rmnは、加算部16及びRmn格納メモリ19に与えられる。

0024

第1のバッファ15は、上述した(4)式の演算で必要となる通信路値Fnをバッファリングし、その通信路値Fnが加算部16に与えられるタイミングを調整するものである。

0025

加算部16は、複数個加算器でなり、行処理回路14による行処理結果Rmnと、第1のバッファ15がバッファリングしている通信路値Fnとを加算するものである。すなわち、加算部16は、上述した(4)式を実行するものである。加算部16によって得られた列処理結果Znは、Zn格納メモリ17及び硬判定部22に与えられる。

0026

Zn格納メモリ17は、復号処理制御部12から与えられたアドレスエリアに、加算部16からの列処理結果Znを格納するものである。また、Zn格納メモリ17は、第2のバッファ18から出力されたアドレスのエリアから、列処理結果Znを読み出して減算部21に被減算入力として与えるものである。

0027

第2のバッファ18は、Zn格納メモリ17への書込みアドレスをバッファリングしてタイミングを調整し、バッファリングしたアドレスを、Zn格納メモリ17、パリティ判定部23及び硬判定データ格納メモリ24に与えるものである。

0028

Rmn格納メモリ19は、復号処理制御部12から与えられたアドレスのエリアに、行処理回路14による行処理結果Rmnを格納するものである。また、Rmn格納メモリ19は、第3のバッファ20から出力されたアドレスのエリアから、行処理結果Rmnを読み出して減算部21に減算入力として与えるものである。

0029

第3のバッファ20は、Rmn格納メモリ19への書込みアドレスをバッファリングしてタイミングを調整し、バッファリングしたアドレスをRmn格納メモリ19に与えるものである。

0030

減算部21は、複数個の減算器でなり、Zn格納メモリ17から読み出された列処理結果Znから、Rmn格納メモリ19から読み出された行処理結果Rmnを減算して、セレクタ13に選択入力として与えるものである。すなわち、減算部21は、上述した(1)式の演算を実行しているものである。

0031

硬判定部22は、加算部16から出力された列処理結果Znに対し、後述する(5)式に従った硬判定を行うものであり、得られた硬判定データをパリティ判定部23及び硬判定データ格納メモリ24に与えるものである。

0032

パリティ判定部23は、硬判定部22からの硬判定データと、第2のバッファ18から出力されたアドレスに基づき、復号処理の繰返し毎に、誤り検出(パリティ判定)を行うものである。第2のバッファ18から出力されたアドレスは、後述するように、復号処理制御部12が検査対象の復号ブロックや検査行列情報をも利用して形成したものであり、検査行列の情報(ビットノードの情報)が盛り込まれており、誤り検出を行うことができる。パリティ判定部23は、パリティ判定結果及びパリティチェックブロック番号を復号処理制御部12に与えるものである。ここで、パリティ判定部23は、第2のバッファ18から出力されたアドレスをパリティチェックブロック番号に変換するための情報(例えばテーブル情報)を保持しており、これにより、パリティチェックブロック番号を生成する。なお、アドレスをパリティチェックブロック番号に変換する機能を、復号処理制御部12が備えるようにしても良い。

0033

LDPC符号は、検査行列Hと、(5)式に示すように硬判定を行った復号結果X^=(x^1,…,x^n,…,x^N)を用いて、HX=0であるかどうかを判定することにより、誤り検出が可能である。すなわち、最大の繰返し数の復号処理を行わなくても、復号繰返し毎に処理を行った行に対する誤り検出を行い、誤り検出結果のOKが所定回連続するような場合であれば、復号処理を終了させても良い。この実施形態は、このような点に鑑み、復号処理の繰返し毎に、処理を行った行に対する誤り検出(パリティ判定)を行い、復号処理制御部11側で、パリティ判定結果に基づいて、最大の繰返し数の復号処理を繰り返す前に復号処理を終了させるか否かを判断させることとした。

0034

硬判定データ格納メモリ24は、硬判定部22からの硬判定データを、第2のバッファ18から出力されたアドレスのエリアに格納するものである。

0035

復号器出力インタフェース部(復号器出力IF)25は、復号処理制御部12から復号終了通知が与えられたときに、硬判定データ格納メモリ24に格納されている硬判定データを、復号データとして読み出して出力するものである。

0036

この実施形態の場合、複数の復号ブロックに対して、時分割的に並行して復号を行うことができるので、Fn格納メモリ11、Zn格納メモリ17、Rmn格納メモリ19、硬判定データ格納メモリ24等は、複数の復号ブロックのデータを同時に格納できる程度の容量に選定されている。

0037

上述したように、復号処理を行うブロックと行を決定する機能を担っている復号処理制御部12は、図2に示すような詳細構成を有する。

0038

図2において、復号処理制御部12は、復号ブロック(Code Block)毎の復号情報格納部30−0〜30−(B−1)、復号ブロック毎の復号処理監視部31−0〜31−(B−1)、スケジューラ32及びアドレス生成部33を有する。なお、図2では、復号ブロック#0についてのみ、復号情報格納部(30−0)及び復号処理監視部(31−0)を示している。

0039

各復号情報格納部30(30−0〜30−(B−1))は、復号器入力インタフェース部10を介して外部から与えられた、当該復号ブロックのパリティ監視サイクル、最大復号繰返し数、優先度情報、検査行列情報を格納しておく部分である。

0040

各復号処理監視部31(31−0〜31−(B−1))は、当該復号ブロックの復号処理を実行するタイミングを監視したり、復号処理の終了判定などを行ったりするものである。各復号処理監視部31(31−0〜31−(B−1))は、復号処理監視部31−0について図2に示すように、機能的に、パリティカウンタ40(40−0〜40−(B−1))、復号繰返しカウンタ41(41−0〜41−(B−1))、行カウンタ42(42−0〜42−(B−1))、Waitサイクル演算部43(43−0〜43−(B−1))及びWaitカウンタ44(44−0〜44−(B−1))を有する。復号処理監視部31の機能については、動作説明の項で詳述する。

0041

スケジューラ32は、全復号ブロックの復号処理監視部31−0〜31−(B−1)からの情報に基づいて、行単位の復号処理のスケジュールを生成するものであり、現時点で、復号処理を実行させる復号ブロックの番号(ブロック番号)、行番号、検査行列情報をアドレス生成部33に与えると共に、上述した図1のセレクタ13に対するセレクタ制御信号も形成するものである。現時点で、復号処理を実行させる復号ブロックの番号は、全復号ブロックの復号処理監視部31−0〜31−(B−1)にフィードバックされるようになされている。

0042

アドレス生成部33は、スケジューラ32から与えられたブロック番号、行番号及び検査行列情報に基づいて、上述した図1のFn格納メモリ11、Zn格納メモリ17、Rmn格納メモリ19に対するメモリアドレスを生成するものである。

0043

(A−2)実施形態の動作
次に、上述した図1及び図2に示す構成を有する実施形態のLDPC符号復号装置1の動作(実施形態のLDPC符号復号方法)を説明する。

0044

外部から与えられた各復号ブロックのデータ(通信路値)は、復号器入力インタフェース部10を介して、Fn格納メモリ11に書き込まれると共に、データ(通信路値)と並行して入力された復号情報は、復号処理制御部12内の該当する復号ブロックについての復号情報格納部30(30−0〜30−(B−1);以下では適宜、符号の枝番を省略して説明する)書き込まれる。

0045

復号処理制御部12における各復号処理監視部31は、対応する復号情報格納部30に復号情報が書き込まれた以降、図3に示す一連の処理を開始する。例えば、処理対象行を見直し単位時間(以下、サイクルと呼ぶ)毎に、図3に示す処理を開始する。また例えば、信号線の図示は省略しているが、その時点で復号情報が設定されて復号処理を要する全ての復号情報格納部が、スケジューラ32の制御下で、図3に示す処理を同期して実行する。なお、図3は、各復号処理監視部31の処理を示すフローチャートである。なお、サイクルは、上述したTDMPアルゴリズムで、各式における「i」を更新する周期に該当する。

0046

復号処理監視部31は、図3に示す処理を開始すると、当該復号ブロックについて、復号処理をこれから開始するのか否かを判別する(ステップ100)。

0047

これから開始する場合であると、復号処理監視部31は、内蔵する全てのカウンタ(パリティカウンタ40、復号繰返しカウンタ41、行カウンタ42、Waitカウンタ44)をリセットする(ステップ101)。

0048

これに対して、当該復号ブロックについて、復号処理を既に開始している場合には、復号処理監視部31は、スケジューラ32から与えられたブロック番号に基づき、前サイクルで行の処理がなされた復号ブロックは、当該復号ブロックか否かを判別する(ステップ102)。

0049

当該復号ブロックの行が前のサイクルで処理されていた場合には、復号処理監視部31は、行カウンタ42をカウントアップした後(ステップ103)、行カウンタ42のカウント値が検査行列の行数と一致するようになったか否かを判別する(ステップ104)。

0050

ここで、行カウンタ42のカウント値は、次に復号処理を行う当該復号ブロックでの行を表しているものであり、カウント値「0」が1行目を表しているので、カウント値が検査行列の行数と一致することは最終行の行処理が終わった直後であることを意味している。行カウンタ42のカウント値が検査行列の行数と一致していると、復号処理監視部31は、復号繰返しカウンタ41をカウントアップすると共に、行カウンタ42をリセット(1行目を指示する値「0」)にする(ステップ105)。復号繰返しカウンタ41は、復号処理を何回繰り返したかをカウントするものである。

0051

復号処理監視部31は、ステップ103でカウントアップした行カウンタ42のカウント値が検査行列の行数と一致しない場合や、復号繰返しカウンタ41のカウントアップや行カウンタ42のリセットを行った後では、復号情報格納部30に格納されている検査行列情報を読み込んでWaitサイクルをWaitサイクル演算部44によって算出させ、得られたWaitサイクルの値をWaitカウンタ44にロードする(ステップ106)。

0052

なお、Waitサイクル演算部44はハードウェアで構成されたものであっても良く、また、サブルーチンとして設けられたものであっても良い。

0053

行処理を行う際には、対象とする行に含まれるビットノードと同じビットノードを含む行及び列の処理が完了するまでの間はその対象行の処理を行うことができない。Waitサイクルとは、行カウンタ42のカウント値が指示する処理対象行が処理開始可能となるまでのサイクル数である。Waitサイクル演算部44は、検査行列の処理対象行におけるビットノードの位置、及び、そのビットノードの列上における他の行のビットノードの位置に応じて、Waitサイクルを演算する。

0054

図4は、検査行列の一例(図4(A))とその検査行列における各行に対するWaitサイクル(図4(B))を示している。図4において、Lとは、1つの行に対する行処理及び列処理が完了するサイクル数である。Lとしては、例えば、6サイクルを適用できる。

0055

1行目(行番号は「0」)では、6列目、15列目及び23列目にビットノードが存在し、これらの列ではそれぞれ、15行目、8行目、13行目にビットノードが存在する。15行目が処理対象行の場合にも、処理対象となってから、Lサイクル後にその行の処理が終了する。そのため、16行目〜18行目が処理対象となった後で、同一列にビットノードを有する1行目が処理対象行となっても、1行目の処理を直ちには開始できず、L−3サイクルを待たなければ開始できない(「3」は16行目〜18行目に係るサイクルである)。

0056

1行目の15列目と同じ列にビットノードを有する行は8行目であり、処理対象行が8行目から1行目に変化するまでには、Lサイクルより十分に長い期間があるので、この列でWaitサイクルを考慮する必要はなく、1行目の23列目についても同様である。

0057

2行目が処理対象行(行番号は「1」)になったときには、1行目がWaitサイクルを待って処理を開始しているため、同一列にビットノードを有する17行目、9行目、14行目の処理は終了しており、Waitサイクルは「0」である。3行目〜6行目についても同様である。

0058

7行目(行番号は「6」)では、10列目及び14列目にビットノードが存在し、これらの列ではそれぞれ、17行目、6行目にビットノードが存在する。6行目が処理対象行の場合にも、処理対象となってから、Lサイクル後にその行の処理が終了するため、同一列にビットノードを有する7行目が処理対象行となっても、7行目の処理を直ちには開始できず、Lサイクルを待たなければ開始できない。

0059

8行目以降も同様にしてWaitサイクルが演算によって決定され、その結果、各行のWaitサイクルを表にすると、図4(B)に示すようになる。

0060

Waitサイクル演算部44は、図4(B)に示すようなWaitサイクルを計算できるものであれば、その内部構成や処理方法は問われないものである。例えば、処理対象行の全てのビットノードの位置を認識し、次に、各ビットノードの列と同じ列にビットノードを有する行を認識すると共に、その認識行の中で最近、処理対象となった行を認識する。そして、その認識行と当該行との行数の差が所要サイクルL以下かを判別し、所要サイクルL以下でなければ「0」を設定し、所要サイクルL以下の場合には、当該行よりL行まで前の行の中に「0」以外のWaitサイクルを設定したものがあるかを検索し、所要サイクルLから、前の方での行のWaitサイクル分を除外したものをWaitサイクルとする。

0061

上述したステップ102の前サイクルで行処理がなされた復号ブロックは、当該復号ブロックか否かの判別の結果、否定結果を得た場合には、復号処理監視部31は、Waitカウンタ44のカウント値が0か否かを判別する(ステップ107)。0でなければ、復号処理監視部31は、Waitカウンタ44をカウントダウンする(ステップ108)。

0062

上述した行カウンタ42、復号繰返しカウンタ41及びWaitカウンタ44の操作が終了すると(ステップ102〜108)、復号処理監視部31は、図1のパリティ判定部23から到来したパリティチェックブロック番号が当該復号ブロックを指示しているか否かを判別する(ステップ109)。なお、パリティチェックブロック番号が到来しない場合は、到来したパリティチェックブロック番号が当該復号ブロックを指示していない場合と同様に処理する。

0063

当該復号ブロックを指示している場合には、復号処理監視部31は、さらに、パリティチェックブロック番号と共に到来したパリティ判定結果がOK(上述したHX=0であることをOKとする)か否かを判定し(ステップ110)、OKであれば、パリティカウンタ40をカウントアップし(ステップ111)、NGであれば、パリティカウンタ40をリセットする(ステップ112)。

0064

復号処理を開始したばかりであり、各種カウンタをリセットした場合(ステップ101)や、到来したパリティチェックブロック番号が当該復号ブロックを指示していない場合(ステップ109で否定結果)や、パリティカウンタ40の操作が終わった場合(ステップ111及び112)には、復号処理監視部31は、パリティカウンタ40のカウント値が復号情報格納部30に格納されているパリティ監視サイクルより小さいか否かを判別する(ステップ113)。パリティカウンタ40のカウント値がパリティ監視サイクルより小さい場合には、復号繰返しカウンタ41のカウント値が復号情報格納部30に格納されている最大復号繰返し数より小さいか否かを判別する(ステップ114)。これらのステップ113及び114の判別処理は、復号処理を終了させるか否かの判定になっている。

0065

パリティカウンタ40のカウント値がパリティ監視サイクルに到達したとき、又は、復号繰返しカウンタ41のカウント値が最大復号繰返し数に到達したときには、復号処理監視部31は、図1の復号器出力インタフェース部25に対して、当該復号ブロックを特定した復号完了通知を送出すると共に(ステップ115)、復号処理フラグを「0」(「1」が復号処理の継続中を表す)にして(ステップ116)、図3に示す一連の処理を終了する。

0066

復号処理を終了させる条件が成立していなければ、復号処理監視部31は、Waitカウンタ44のカウント値が0か否かを判別する(ステップ117)。Waitカウンタ44のカウント値が0以外であれば(言い換えると、復号処理を待っていなければならない状態であると)、復号処理監視部31は、復号処理フラグを「0」にして(ステップ116)、図3に示す一連の処理を終了する。

0067

一方、Waitカウンタ44のカウント値が0であると、復号処理監視部31は、復号処理フラグを「1」とした後(ステップ118)、スケジューラ32に与える信号を生成してスケジューラ32に出力し(ステップ119)、図3に示す一連の処理を終了する。

0068

スケジューラ32に与える信号は、復号情報格納部30に格納されている優先度情報及び検査行列情報(処理対象行の情報だけでも良い)と、行カウンタ42のカウント値(処理行番号)と、復号処理フラグと、セレクタ制御信号とである。セレクタ制御信号は、復号繰返しカウンタ41のカウント値に基づき、処理対象行の初めての復号処理のときに、Fn格納メモリ11の出力を選択させるような制御信号とする。

0069

なお、復号処理フラグを「0」にしたときにも(ステップ116)にも、復号処理監視部31は、その旨の信号をスケジューラ32に与えるようにしても良い。

0070

スケジューラ32においては、各復号処理監視部31−0〜31−(B−1)から出力された復号処理フラグと優先度情報を見て、復号処理フラグが「1」である中から最も優先度の高い復号ブロックを選択される。そして、スケジューラ32から、現時点(現サイクル)で、復号処理を実行させる復号ブロックの番号(ブロック番号)、行番号、検査行列情報がアドレス生成部33に与えられると共に、上述した図1のセレクタ13に対してはその復号ブロックについて与えられたセレクタ制御信号がそのまま与えられる。現時点で、復号処理を実行させる復号ブロックの番号は、全復号ブロックの復号処理監視部31−0〜31−(B−1)にも与えられる。

0071

なお、スケジューラ32が、現サイクルだけでなく、将来のサイクルの処理対象の復号ブロック及び行番号などをも予め定めるものであっても良い。

0072

アドレス生成部33においては、スケジューラ32から出力された情報を元に、各種メモリ11、17及び19に与えるアドレスが生成されて該当するメモリ11、17及び19に与えられ、各メモリ11、17及び19から処理対象となる復号ブロックにおける処理対象の行処理の入力に必要なデータを読み出される。

0073

スケジューラ32からのセレクタ制御信号に応じたセレクタ13によって、上述した(1)式の演算を実行する減算部21からの出力データが基本的に、行処理回路14への入力データLmnとなる。Fn格納メモリ11から読み出されたデータが行処理回路14への入力データLmnとなるので、事後対数尤度比Znとして初期値が利用されるときである。

0074

また、Fn格納メモリ11からは、(4)式の演算に必要なデータも読み出され、第1のバッファ15に格納される。

0075

行処理回路14によって、上述した(2)式の演算が実行され、M(≦L)サイクル後に行処理回路14から行処理結果Rmnが出力される。このようにして更新された行処理結果RmnがRmn格納メモリ19に格納される。また、加算部16によって、更新された行処理結果Rmnと、第1のバッファ15を介してタイミング調整されたFn格納メモリ11から読み出されたデータFnとが加算され(すなわち、(4)式が実行され)、更新された事後対数尤度比ZnがZn格納メモリ17に格納される。

0076

Zn格納メモリ17及びRmn格納メモリ19に格納された事後対数尤度比Zn及び行処理結果Rmnは、対応する第2のバッファ18及び第3のバッファ20の機能により、書込み時より遅れたタイミングで出力され、減算部21による(1)式の演算に供する。

0077

また、硬判定部22によって、事後対数尤度比Znを硬判定した結果が硬判定データ格納メモリ24に格納されると共に、パリティ判定部23によって、得られた硬判定データを用いてパリティチェックが行われ、そのパリティ判定結果が復号処理制御部12に出力する。このパリティ判定結果は、図3に対して説明したように利用される。

0078

復号器出力インタフェース部24においては、復号処理制御部12から、上述のようにして出力された復号終了通知が与えられた際には、その復号終了通知に係る復号ブロックに対する復号結果(復号データ)を、硬判定データ格納メモリ24から読み出して出力する。

0079

なお、図1では明示していないが、復号データにはどの復号ブロックに関するものかの情報を付与するようにしても良く、また、復号器出力インタフェース部24からの出力線として、復号ブロック毎の出力線を設け、該当する出力線に出力するようにしても良い。このような変形例は、復号器入力インタフェース部10についても同様である。

0080

図5(B)及び(C)はそれぞれ、復号処理制御部12が各サイクルについて決定した処理対象の復号ブロック及び行を示すタイミングチャートであり、図5(B)は、復号処理に供している復号ブロックが#0だけの場合を示しており、図5(C)は、復号処理に供している復号ブロックが#0及び#2の2つの場合であって、復号ブロック#0が復号ブロック#2より優先度が高い場合を示している。参考のために、図5(A)には、復号ブロックが#0だけの場合であってWaitサイクルを固定にしている場合(非特許文献2参照)を示している。

0081

なお、図5は、復号ブロック#0についてはその検査行列が図4(A)に示すものであり、1行の復号処理の所要サイクルLが6サイクルの場合を示している。

0082

図5(A)に示すように、Waitサイクルを復号処理の所要サイクルL(=6)に固定した場合、6行毎に常にL(=6)サイクル分のWait時間が必要となり、1回の復号処理に対し、6×3=18サイクル分のWait時間が発生する。

0083

これに対し、Waitサイクルを演算によって求め(従って、Waitサイクルは可変)、Waitサイクルを経過すると、その復号ブロックの処理を実行可能とすると、復号処理に供している復号ブロックが1つの図5(B)に示す場合に、図5(A)の固定の場合より、全体としてのWait時間(Waitサイクル数)を少なくすることができる。例えば、7行目の処理を行う前には6サイクルのWait時間となり、13行目、1行目の処理を行う前のWait時間は3サイクルとなり、1回の復号処理に対し、6+3×2=12サイクル分となって6サイクル分だけ、図5(A)よりWait時間を短くできる。

0084

さらに、複数の復号ブロックをスケジューリングしながら処理する場合であれば、ある復号ブロックの復号処理でのWait時間を、他の復号ブロックの復号処理に割り当てることができ、復号処理を実行する処理部のスループットを向上させることができる。例えば、図5(C)に示すように、復号ブロック#0の復号処理が行えないWait時間に、復号ブロック#2の復号処理を行うことができる。

0085

(A−3)実施形態の効果
上記実施形態によれば、検査行列の構成に応じて、処理対象行について復号処理が可能となったときには直ちに処理を実行できるように、Wait時間(Waitサイクル)を決定し、処理を待機するようにしたので、復号処理が可能なのに処理を待機するような無意味なWait時間を防止でき、復号処理のスループットを向上させることができる。

0086

また、上記実施形態によれば、複数の復号ブロックの復号処理をスケジューラが調整して時分割的に並行処理し得るようにしたので、ある復号ブロックのWait時間を他の復号ブロックの復号処理に利用することができ、この面でも、復号処理のスループットを向上させることができる。

0087

さらに、上記実施形態によれば、復号繰返し毎に、誤り検出を行い、検出結果がOKなことが所定回数連続したときには、最大繰返し数だけ復号処理を繰り返さなくても、復号処理を終了させるようにしたので、復号処理回数を減らした分だけ、他の復号ブロックの処理などに処理を回すことができ、この面でも、復号処理のスループットを向上させることができる。

0088

(B)他の実施形態
上記実施形態においては、復号処理の実行構成が図1に示す構成であるものを示したが、本発明は、復号処理に供する行(若しくは、ブロック及び行の組み合わせ)の決定手法に特徴を有し、復号処理の実行構成は、図1に示すものに限定されない。例えば、一部の構成(例えば、格納メモリなど)を多面構成としたものであっても良い。

0089

また、上記実施形態においては、復号情報が外部から入力されるものを示したが、復号処理制御部内に予め複数種類の復号情報を設定しておき、それを選択するようにしても良い。

0090

さらに、上記実施形態においては、図4(B)に示すようなWaitサイクルをその都度演算して求めるものを示したが、検査情報と同様に、外部から復号処理制御部に入力するようにしても良い。

0091

上記実施形態では、複数の復号ブロックに対応できるLDPC符号復号装置を示したが、1つの復号ブロックだけに対応できるLDPC符号復号装置にも本発明を適用することができる。この場合には、図2におけるスケジューラを省略すれば良い。

0092

また、上記実施形態では、スケジューラはWait状態になければ常に優先度情報に従って復号処理に供する復号ブロックを定めるものを示したが、選択した復号ブロックの優先度を1段階下げて次のサイクルの復号ブロックの決定判断に用いるなど、複数の復号ブロック間の選択方法は上記実施形態のものに限定されない。

0093

なお、行処理演算部は、(2)式の近似式の演算を実行できるものであっても良い。このような近似式の演算構成としては、例えば、文献『“Near optimum universal belief propagation based decoding of low−density parity check codes,”IEEE Trans. Commun., vol.50, pp.406−414, Mar.2002』に記載されている。

図面の簡単な説明

0094

実施形態に係るLDPC符号復号装置の全体構成を示すブロック図である。
実施形態の復号処理制御部の詳細構成を示すブロック図である。
実施形態の復号処理監視部の処理を示すフローチャートである。
実施形態の検査行列の例とその検査行列について定まるWaitサイクルの例を示す説明図である。
実施形態の効果を説明するための処理開始の復号ブロック及び行を示すタイミングチャートである。

符号の説明

0095

1…LDPC符号復号装置、12…復号処理制御部、23…パリティ判定部、30−0〜30−(B−1)…復号情報格納部、31−0〜31−(B−1)…復号処理監視部、32…スケジューラ、33…アドレス生成部。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ