JP2004343170A - 復号方法および復号装置、並びにプログラム - Google Patents

Abstract

【課題】回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行う。
【解決手段】ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号の元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、ＬＤＰＣ符号が復号される。この場合に、Ｐ×Ｐの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはＰ×Ｐの０行列を構成行列として、変換検査行列は、複数の構成行列の組合せで表される。チェックノード計算部３０２は、チェックノードの演算を、Ｐ個同時に行い、バリアブルノード計算部３０４は、バリアブルノードの演算を、Ｐ個同時に行う。
【選択図】 図１８

Description

【０００１】
【発明の属する技術分野】
本発明は、復号方法および復号装置、並びにプログラムに関し、特に、低密度パリティ検査符号による符号化が施された符号の復号を行う復号方法および復号装置、並びにプログラムに関する。
【０００２】
【従来の技術】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン（Ｃ． Ｅ． Ｓｈａｎｎｏｎ）の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号（ＰＣＣＣ（Ｐａｒａｌｌｅｌ Ｃｏｎｃａｔｅｎａｔｅｄ Ｃｏｎｖｏｌｕｔｉｏｎａｌ Ｃｏｄｅｓ））や、縦列連接畳み込み符号（ＳＣＣＣ（Ｓｅｒｉａｌｌｙ Ｃｏｎｃａｔｅｎａｔｅｄ Ｃｏｎｖｏｌｕｔｉｏｎａｌ Ｃｏｄｅｓ））といった、いわゆるターボ符号化（Ｔｕｒｂｏ ｃｏｄｉｎｇ）と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ ｃｏｄｅｓ）（以下、ＬＤＰＣ符号という）が脚光を浴びつつある。
【０００４】
ＬＤＰＣ符号は、Ｒ． Ｇ． Ｇａｌｌａｇｅｒによる「Ｒ． Ｇ． Ｇａｌｌａｇｅｒ， ”Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ”， Ｃａｍｂｒｉｄｇｅ， Ｍａｓｓａｃｈｕｓｅｔｔｓ： Ｍ． Ｉ． Ｔ． Ｐｒｅｓｓ， １９６３」において最初に提案されたものであり、その後、「Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ， ”Ｇｏｏｄ ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ ｖｅｒｙ ｓｐａｒｓｅ ｍａｔｒｉｃｅｓ”， Ｓｕｂｍｉｔｔｅｄ ｔｏ ＩＥＥＥ Ｔｒａｎｓ． Ｉｎｆ． Ｔｈｅｏｒｙ， ＩＴ−４５， ｐｐ． ３９９−４３１， １９９９」や、「Ｍ． Ｇ． Ｌｕｂｙ， Ｍ． Ｍｉｔｚｅｎｍａｃｈｅｒ， Ｍ． Ａ． Ｓｈｏｋｒｏｌｌａｈｉ ａｎｄ Ｄ． Ａ． Ｓｐｉｅｌｍａｎ， ”Ａｎａｌｙｓｉｓ ｏｆ ｌｏｗ ｄｅｎｓｉｔｙ ｃｏｄｅｓ ａｎｄ ｉｍｐｒｏｖｅｄ ｄｅｓｉｇｎｓ ｕｓｉｎｇ ｉｒｒｅｇｕｌａｒ ｇｒａｐｈｓ”， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ， ｐｐ． ２４９−２５８， １９９８」等において再注目されるに至ったものである。
【０００５】
ＬＤＰＣ符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、ＬＤＰＣ符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【０００６】
以下、このようなＬＤＰＣ符号について具体的に説明する。なお、ＬＤＰＣ符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
【０００７】
ＬＤＰＣ符号は、そのＬＤＰＣ符号を定義する検査行列（ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ）が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの”１”の個数が非常に少なく構成されるものであり、疎な検査行列をＨで表すものとすると、そのような検査行列としては、例えば、図１に示すように、各行のハミング重み（”１”の数）（ｗｅｉｇｈｔ）が”３”であり、且つ、各列のハミング重みが”６”であるもの等がある。
【０００８】
このように、各行及び各列のハミング重みが一定である検査行列Ｈによって定義されるＬＤＰＣ符号は、レギュラーＬＤＰＣ符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Ｈによって定義されるＬＤＰＣ符号は、イレギュラーＬＤＰＣ符号と称される。
【０００９】
このようなＬＤＰＣ符号による符号化は、検査行列Ｈに基づいて生成行列Ｇを生成し、この生成行列Ｇを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、ＬＤＰＣ符号による符号化を行う符号化装置は、まず、検査行列Ｈの転置行列Ｈ^Ｔとの間に、式ＧＨ^Ｔ＝０が成立する生成行列Ｇを算出する。ここで、生成行列Ｇが、ｋ×ｎ行列である場合には、符号化装置は、生成行列Ｇに対してｋビットからなる情報メッセージ（ベクトルｕ）を乗算し、ｎビットからなる符号語ｃ（＝ｕＧ）を生成する。この符号化装置によって生成された符号語は、値が”０”の符号ビットが”＋１”に、値が”１”の符号ビットが”１”にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。
【００１０】
一方、ＬＤＰＣ符号の復号は、Ｇａｌｌａｇｅｒが確率復号（Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｄｅｃｏｄｉｎｇ）と称して提案したアルゴリズムであって、バリアブルノード（ｖａｒｉａｂｌｅ ｎｏｄｅ（メッセージノード（ｍｅｓｓａｇｅ ｎｏｄｅ）ともいう。））と、チェックノード（ｃｈｅｃｋ ｎｏｄｅ）とからなる、いわゆるタナーグラフ（Ｔａｎｎｅｒ ｇｒａｐｈ）上での確率伝播（ｂｅｌｉｅｆ ｐｒｏｐａｇａｔｉｏｎ）によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
【００１１】
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのものを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Ｇａｌｌａｇｅｒは、ＬＤＰＣ符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
【００１２】
ＬＤＰＣ符号の復号は、一般的には、図２に示すような手順にしたがって行われる。なお、ここでは、受信値（受信した符号系列）をＵ_０（ｕ_０ｉ）とし、チェックノードから出力されるメッセージをｕ_ｊとし、バリアブルノードから出力されるメッセージをｖ_ｉとする。また、ここでは、メッセージとは、値の”０”らしさを、いわゆる対数尤度比（ｌｏｇ ｌｉｋｅｌｉｈｏｏｄ ｒａｔｉｏ）で表現した実数値である。
【００１３】
まず、ＬＤＰＣ符号の復号においては、図２に示すように、ステップＳ１１において、受信値Ｕ_０（ｕ_０ｉ）が受信され、メッセージｕ_ｊが”０”に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数ｋが”０”に初期化され、ステップＳ１２に進む。ステップＳ１２において、受信値Ｕ_０（ｕ_０ｉ）に基づいて、式（１）に示す演算（バリアブルノードの演算）を行うことによってメッセージｖ_ｉが求められ、さらに、このメッセージｖ_ｉに基づいて、式（２）に示す演算（チェックノードの演算）を行うことによってメッセージｕ_ｊが求められる。
【００１４】
【数１】

【００１５】
【数２】

【００１６】
ここで、式（１）と式（２）におけるｄ_ｖとｄ_ｃは、それぞれ、検査行列Ｈの縦方向（列）と横方向（行）の”１”の個数を示す任意に選択可能とされるパラメータであり、例えば、（３，６）符号の場合には、ｄ_ｖ＝３，ｄ_ｃ＝６となる。
【００１７】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝（ｅｄｇｅ）（バリアブルノードとチェックノードとを結ぶ線）から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至ｄ_ｖ−１または１乃至ｄ_ｃ−１となっている。また、式（２）に示す演算は、実際には、２入力ｖ_１，ｖ_２に対する１出力で定義される式（３）に示す関数Ｒ（ｖ_１，ｖ_２）のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００１８】
【数３】

【００１９】
【数４】

【００２０】
ステップＳ１２では、さらに、変数ｋが”１”だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数ｋが所定の繰り返し復号回数Ｎよりも大きいか否かが判定される。ステップＳ１３において、変数ｋがＮよりも大きくないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２１】
また、ステップＳ１３において、変数ｋがＮよりも大きいと判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージｖ_ｉが求められて出力され、ＬＤＰＣ符号の復号処理が終了する。
【００２２】
【数５】

【００２３】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
【００２４】
このようなＬＤＰＣ符号の復号は、例えば（３，６）符号の場合には、図３に示すように、各ノード間でメッセージの授受が行われる。なお、図３における”＝”で示すノード（バリアブルノード）では、式（１）に示した演算が行われ、”＋”で示すノード（チェックノード）では、式（２）に示した演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、”＋”で示すノードにて、ｄ_ｃ−１個の入力メッセージの排他的論理和演算を行い、”＝”で示すノードにて、受信値Ｒに対して、ｄ_ｖ−１個の入力メッセージが全て異なるビット値であった場合には、符号を反転して出力する。
【００２５】
また、一方で、近年、ＬＤＰＣ符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、ＬＤＰＣ符号の復号を摸式化して説明する。
【００２６】
図４は、（３，６）ＬＤＰＣ符号（符号化率１／２、符号長１２）の検査行列（ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ）の例である。ＬＤＰＣ符号の検査行列は、図５のように、タナーグラフを用いて書き表すことができる。ここで、図５において、”＋”で表わされるのが、チェックノードであり、”＝”で表わされるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列の行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝（ｅｄｇｅ）であり、検査行列の”１”に相当する。即ち、検査行列の第ｊ行第ｉ列のコンポーネントが１である場合には、図５において、上からｉ番目のバリアブルノード（”＝”のノード）と、上からｊ番目のチェックノード（”＋”のノード）とが、枝により接続される。枝は、バリアブルノードに対応する符号ビットが、チェックノードに対応する拘束条件を持つことを表わす。なお、図５は、図４の検査行列のタナーグラフとなっている。
【００２７】
ＬＤＰＣ符号の復号方法であるサムプロダクトアルゴリズム（Ｓｕｍ Ｐｒｏｄｕｃｔ Ａｌｇｏｒｉｔｈｍ）では、バリアブルノードの演算とチェックノードの演算とが繰り返し行われる。
【００２８】
バリアブルノードでは、図６のように、式（１）の演算（バリアブルノード演算）を行う。すなわち、図６において、計算しようとしている枝に対応するメッセージｖ_ｉは、バリアブルノードに繋がっている残りの枝からのメッセージｕ_１およびｕ_２と、受信情報ｕ_０ｉを用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００２９】
次に、チェックノードの演算について説明する前に、式（２）を、式ａ×ｂ＝ｅｘｐ｛ｌｎ（｜ａ｜）＋ｌｎ（｜ｂ｜）｝×ｓｉｇｎ（ａ）×ｓｉｇｎ（ｂ）の関係を用いて、式（６）のように書き直す。但し、ｓｉｇｎ（ｘ）は、ｘ≧０のとき１であり、ｘ＜０のとき−１である。
【００３０】
【数６】

【００３１】
更に、ｘ≧０において、φ（ｘ）＝ｌｎ（ｔａｎｈ（ｘ／２））と定義すると、φ^−１（ｘ）＝２ｔａｎｈ^−１（ｅ^−ｘ）であるから、式（６）は、式（７）のように書くことができる。
【００３２】
【数７】

【００３３】
チェックノードでは、図７のように、式（７）の演算（チェックノード演算）を行う。すなわち、図７において、計算しようとしている枝に対応するメッセージｕ_ｊは、チェックノードに繋がっている残りの枝からのメッセージｖ_１，ｖ_２，ｖ_３，ｖ_４，ｖ_５を用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００３４】
なお、関数φ（ｘ）は、φ（ｘ）＝ｌｎ（（ｅ^ｘ＋１）／（ｅ^ｘ−１））とも表すことができ、ｘ＞０において、φ（ｘ）＝φ^−１（ｘ）である。関数φ（ｘ）およびφ^−１（ｘ）をハードウェアに実装する際には、ＬＵＴ（Ｌｏｏｋ Ｕｐ Ｔａｂｌｅ）を用いて実装される場合があるが、両者共に同一のＬＵＴとなる。
【００３５】
サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）で表わされるバリアブルノード演算および式（７）で表わされるチェックノード演算とを、適度な回路規模と動作周波数で繰り返し行うことが必要である。
【００３６】
復号装置の実装の例として、まず、単純に各ノードの演算を一つずつ順次行うことによって復号を行う場合（ｆｕｌｌ ｓｅｒｉａｌ ｄｅｃｏｄｉｎｇ）の実装法について説明する。
【００３７】
なお、ここでは、例えば、図８の、３０（行）×９０（列）の検査行列で表現される符号（符号化率２／３、符号長９０）を復号することとする。図８の検査行列の１の数は２６９であり、従って、そのタナーグラフでは、枝の数は２６９個となる。ここで、図８の検査行列では（後述する図１５乃至図１７においても同様）、０を、”．”で表現している。
【００３８】
図９は、ＬＤＰＣ符号の１回復号を行う復号装置の構成例を示している。
【００３９】
図９の復号装置では、その動作する１クロック（ｃｌｏｃｋ）ごとに、１つの枝に対応するメッセージが計算される。
【００４０】
即ち、図９の復号装置は、１つの受信用メモリ１０４、２つの枝用メモリ１００および１０２、１つのチェックノード計算器１０１、１つのバリアブルノード計算器１０３からなる。
【００４１】
図９の復号装置では、枝用メモリ１００または１０２からメッセージデータが一つずつ読み出され、そのメッセージデータを用いて、所望の枝に対応するメッセージデータが計算される。そして、その計算によって求められたメッセージデータが一つずつ後段の枝用メモリ１０２または１００に格納されていく。繰り返し復号を行う際には、この１回復号を行う図９の復号装置を複数個縦列に連接するか、もしくは図９の復号装置を繰り返し用いることによって、繰り返し復号を実現する。なお、ここでは、例えば、図９の復号装置が複数個接続されているものとする。
【００４２】
枝用メモリ１００は、前段の復号装置（図示せず）のバリアブルノード計算器１０３から供給される出力メッセージＤ１００を、後段のチェックノード計算器１０１が読み出す順番に格納していく。そして、枝用メモリ１００は、チェックノード計算のフェーズでは、メッセージＤ１００を、格納してある順番通りに、メッセージ出力Ｄ１０１として、チェックノード計算器１０１に供給する。チェックノード計算器１０１は、枝用メモリ１００から供給されるメッセージＤ１０１を用いて、式（７）に従って演算を行い、その演算によって求められたメッセージＤ１０２を、後段の枝用メモリ１０２に供給する。
【００４３】
ここで、図１０は、チェックノード計算を一つずつ行う図９のチェックノード計算器１０１の構成例を示している。
【００４４】
図１０のチェックノード計算器１０１では、枝用メモリ１００から供給される、検査行列の各列に対応するバリアブルノードからのメッセージｖ_ｉを一つずつ読み込み、式（７）におけるφ（｜ｖ_ｉ｜）の演算をＬＵＴによって行う。さらに、検査行列の１行に亘る各列に対応するバリアブルノードからのメッセージｖ_ｉから求められたφ（｜ｖ_ｉ｜）が積算され、これにより、全ての枝からのメッセージｖ_ｉから求められたφ（｜ｖ_ｉ｜）の積算値が求められる。その後、その積算値から、メッセージｕ_ｊを求めたい枝から求められてＦＩＦＯ（ＦＩＦＯメモリ）で遅延されたφ（｜ｖ_ｉ｜）が減算され、これにより、メッセージｕ_ｊを求めたい枝について、式（７）におけるΣφ（｜ｖ_ｉ｜）が求められる。即ち、チェックノードへの枝すべてからのメッセージの和から、メッセージｕ_ｊを求めたい枝からのメッセージを減算することで、メッセージｕ_ｊを求めたい枝へのメッセージが求められる。さらに、ＬＵＴによって、式（７）におけるφ^−１（Σφ（｜ｖ_ｉ｜））の演算が行われる。同時に、メッセージｕ_ｊの符号ビット、即ち、式（７）におけるΠｓｉｇｎ（ｖ_ｉ）も、ＥＸＯＲ回路を用いて同様に計算される。以上のようにして、式（７）の演算が行われ、メッセージｕ_ｊが求められる。
【００４５】
なお、図１０では、各メッセージが符号ビットを合わせて合計６ビット（ｂｉｔ）に量子化されているものとして、チェックノード計算器１０１を表している。また、ここで処理の対象としている図８の検査行列の行の重み（ｒｏｗ ｗｅｉｇｈｔ）の最大は９であるため、即ち、チェックノードに供給されるメッセージの最大数は９であるため、チェックノード計算器１０１は、９個のメッセージ（φ（｜ｖ_ｉ｜））を遅延させるＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）を持っている。
【００４６】
図９に戻り、枝用メモリ１０２は、前段のチェックノード計算器１０１から供給される出力メッセージＤ１０２を、後段のバリアブルノード計算器１０３が読み出す順番に格納していく。そして、枝用メモリ１０２は、バリアブルノード計算のフェーズでは、メッセージ出力Ｄ１０２を、格納してある順番通りに、メッセージ出力Ｄ１０３として、バリアブルノード計算器１０３に供給する。
【００４７】
バリアブルノード計算器１０３は、枝用メモリ１０２から供給されるメッセージＤ１０３と受信用メモリ１０４から供給される受信データ（ＬＤＰＣ符号の受信値）Ｄ１０４を用いて式（１）に従って演算を行い、その演算の結果得られるメッセージＤ１０５を、図示せぬ後段の復号装置の枝用メモリ１００に供給する。
【００４８】
ここで、図１１は、バリアブルノード計算を一つずつ行う図９のバリアブルノード計算器１０３の構成例を示している。
【００４９】
図１１のバリアブルノード計算器１０３では、枝用メモリ１０２から供給される、検査行列の各行に対応するチェックノードからのメッセージｕ_ｊを一つずつ読み込み、検査行列の１列に亘る各行に対応するチェックノードからのメッセージを積算して、その積算値を求める。その後、その積算値から、メッセージｖ_ｉを求めたい枝から供給されてＦＩＦＯで遅延されたメッセージが減算される。さらに、その結果得られる減算値から、受信値ｕ_０ｉを加算することで、式（１）の演算が行われ、これにより、メッセージｖ_ｉが求められる。即ち、バリアブルノードへの枝すべてからのメッセージの和から、メッセージｖ_ｉを求めたい枝からのメッセージを減算することで、メッセージｖ_ｉを求めたい枝へのメッセージが求められる。
【００５０】
図１１においても、図１０における場合と同様に、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、バリアブルノード計算器１０３を表している。また、ここで処理の対象としている図８の検査行列においては、列の重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）の最大値が５であるため、バリアブル計算器１０３は、５個のメッセージを遅延させるＦＩＦＯを持っており、列の重みが５未満の列のメッセージを計算するときには、ＦＩＦＯにおける遅延量が、その列の重みの値に減らされる。
【００５１】
再び、図９に戻り、復号装置には、検査行列の重みにしたがって、図示しない制御信号が与えられる。そして、図９の復号装置によれば、枝用メモリ１００および１０２、並びにチェックノード計算器１０１およびバリアブルノード計算器１０３のＦＩＦＯの容量さえ足りれば、制御信号のみを変えることで様々な符号を復号することができる。
【００５２】
なお、図示しないが、図９の復号装置において、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【００５３】
図９の復号装置を繰り返し用いて、ＬＤＰＣ符号を復号する場合には、チェックノード演算とバリアブルノード演算とが交互に行われるため、２６９の枝を有する図８の検査行列を用いた１回の復号に、２６９×２＝５３８クロック（ｃｌｏｃｋ）を必要とする。従って、例えば、５０回の繰り返し復号を行うためには、符号長である９０個の符号情報（受信値）を受信する間に、５３８×５０＝２６９００クロック動作することが必要であり、受信周波数の約３００（≒２６９００／９０）倍の高速動作が必要になる。この場合、受信周波数が数十ＭＨｚであるとすると、ＧＨｚ以上の速度での動作を要求されることになり、実装は容易ではない。
【００５４】
また、図９の復号装置を、例えば、５０台連接して、ＬＤＰＣ符号を復号する場合には、１フレーム（ｆｒａｍｅ）目がバリアブルノード演算を行っている間に、２フレーム目はチェックノード演算を行い、３フレーム目は前段のバリアブルノード演算を行う、というように、複数のバリアブルノード演算とチェックノード演算とを同時に行うことができる。この場合、９０個の符号情報を受信する間に、２６９個の枝を計算すればよいので、復号装置は、受信周波数の約３（≒２６９／９０）倍の周波数で動作すればよいことになり、十分に実現可能である。しかしながら、この場合、回路規模が、単純には、図９の復号装置の５０倍になる。
【００５５】
次に、全ノードの演算を同時に行うことによって復号を行う場合（ｆｕｌｌ ｐａｒａｌｌｅｌ ｄｅｃｏｄｉｎｇ）の復号装置の実装法について説明する。
【００５６】
この実装法については、例えば、非特許文献１に記載されている。
【００５７】
図１２は、図８の検査行列で表現される符号（符号化率２／３、符号長９０）を復号する復号装置の一例の構成を示している。
【００５８】
図１２の復号装置では、枝用メモリ２０２または２０６から、２６９個ある枝に対応するメッセージデータを全て同時に読み出し、そのメッセージデータを用いて、２６９個の枝に対応する新たなメッセージデータを演算する。さらに、その演算の結果求められた新たなメッセージデータが全て同時に後段の枝用メモリ２０６または２０２に格納されていく。そして、図１２の復号装置を繰り返し用いることで繰り返し復号が実現される。
【００５９】
図１２において、復号装置は、１つの受信用メモリ２０５、２つの枝入れ替え装置２００および２０３、２つの枝用メモリ２０２および２０６、３０個のチェックノード計算器２０１_１乃至２０１_３０、９０個のバリアブルノード計算器２０４_１乃至２０４_９０からなる。以下、各部について詳細に説明する。
【００６０】
枝用メモリ２０６は、前段のバリアブルノード計算器２０４_１乃至２０４_９０からの出力メッセージＤ２０６_１乃至Ｄ２０６_９０を全て同時に格納し、次の時刻（次のクロックのタイミング）に、メッセージＤ２０６_１乃至Ｄ２０６_９０を、メッセージＤ２０７_１乃至Ｄ２０７_９０として読み出し、次段の枝入れ替え装置２００に、メッセージＤ２００（Ｄ２００_１乃至Ｄ２００_９０）として供給する。枝入れ替え装置２００は、枝用メモリ２０６から供給されたメッセージＤ２００_１乃至Ｄ２００_９０の順番を、図８の検査行列に従って並び替え（入れ替え）、チェックノード計算器２０１_１乃至２０１_３０に、それぞれ必要なメッセージＤ２０１_１乃至Ｄ２０１_３０を供給する。
【００６１】
チェックノード計算器２０１_１乃至２０１_３０は、枝入れ替え装置２００から供給されるメッセージＤ２０１_１乃至Ｄ２０１_３０を用いて式（７）に従って演算を行い、その演算の結果得られるメッセージＤ２０２_１乃至Ｄ２０２_３０を、枝用メモリ２０２に供給する。
【００６２】
ここで、図１３は、チェックノード演算を同時に行う図１２のチェックノード計算器２０１_ｍ（ｍ＝１，２，・・・，３０）の構成例を示している。
【００６３】
図１３のチェックノード計算器２０１_ｍでは、図１０のチェックノード計算器１０１と同様にして、式（７）のチェックノード演算が行われるが、そのチェックノード演算が、すべての枝について同時に行われる。
【００６４】
即ち、図１３のチェックノード計算器２０１_ｍでは、枝入れ替え装置２００から供給される図８の検査行列の各列に対応するバリアブルノードからのメッセージが全て同時に読み込まれ、式（７）におけるφ（｜ｖ_ｉ｜）の演算がＬＵＴによって行われる。さらに、検査行列の１行に亘る各列に対応するバリアブルノードからのメッセージｖ_ｉから求められたφ（｜ｖ_ｉ｜）が積算され、これにより、全ての枝からのメッセージｖ_ｉから求められたφ（｜ｖ_ｉ｜）の積算値が求められる。その後、その積算値から、メッセージｕ_ｊを求めたい枝から求められたφ（｜ｖ_ｉ｜）が減算され、これにより、メッセージｕ_ｊを求めたい枝について、式（７）におけるΣφ（｜ｖ_ｉ｜）が求められる。即ち、チェックノードへの枝すべてからのメッセージの和から、メッセージｕ_ｊを求めたい枝からのメッセージを減算することで、メッセージｕ_ｊを求めたい枝へのメッセージが求められる。さらに、ＬＵＴによって、式（７）におけるφ^−１（Σφ（｜ｖ_ｉ｜））の演算が行われる。同時に、メッセージｕ_ｊの符号ビット、即ち、式（７）におけるΠｓｉｇｎ（ｖ_ｉ）も、ＥＸＯＲ回路を用いて同様に計算される。以上のようにして、式（７）の演算が行われ、メッセージｕ_ｊが求められる。
【００６５】
なお、図１３では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、チェックノード計算器２０１_ｍを表している。また、図１３の回路は一つのチェックノードに相当する。ここで処理の対象としている図８の検査行列については、その行数である３０行のチェックノードが存在するから、図１２の復号装置は、図１３に示したようなチェックノード計算器２０１_ｍを３０個有している。
【００６６】
ここで、図１３のチェックノード計算器２０１_ｍでは、９個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図８の検査行列の行の重みは、第１行が８で、第２乃至第３０行が９であるため、即ち、チェックノードに供給されるメッセージの数が、８のケースが１つと、９のケースが２９あるため、チェックノード計算器２０１_１は、図１３の回路と同様の８つのメッセージを同時に計算することができる回路構成となっており、チェックノード計算器２０１_２乃至２０１_３０は、図１３の回路と同一構成となっている。
【００６７】
図１２に戻り、枝用メモリ２０２は、前段のチェックノード計算器２０１_１乃至２０１_３０から供給される出力メッセージＤ２０２_１乃至Ｄ２０２_３０を全て同時に格納し、次の時刻に、そのすべてのメッセージＤ２０２_１乃至Ｄ２０２_３０を、出力メッセージＤ２０３_１乃至Ｄ２０３_３０として、次段の枝入れ替え装置２０３に供給する。
【００６８】
枝入れ替え装置２０３は、枝用メモリ２０２から供給されたメッセージＤ２０３_１乃至Ｄ２０３_３０の順番を図８の検査行列に従って並び替え、バリアブルノード計算器２０４_１乃至２０４_９０に、それぞれ必要なメッセージＤ２０４_１乃至Ｄ２０４_９０を供給する。
【００６９】
バリアブルノード計算器２０４_１乃至２０４_９０は、枝入れ替え装置２０３から供給されるメッセージＤ２０４_１乃至Ｄ２０４_９０と、受信用メモリ２０５から供給される受信データ（受信値）Ｄ２０５_１乃至Ｄ２０５_９０を用いて式（１）に従って演算を行い、その演算の結果得られるメッセージＤ２０６_１乃至Ｄ２０６_９０を、次段の枝用メモリ２０６に供給する。
【００７０】
ここで、図１４は、バリアブルノード演算を同時に行う図１２のバリアブルノード計算器２０４_ｐ（ｐ＝１，２，・・・，９０）の構成例を示している。
【００７１】
図１４のバリアブルノード計算器２０４_ｐでは、図１１のバリアブルノード計算器１０３と同様にして、式（７）のチェックノード演算が行われるが、そのチェックノード演算が、すべての枝について同時に行われる。
【００７２】
即ち、図１４のバリアブルノード計算器２０４_ｐでは、枝入れ替え装置２０３から供給される、検査行列の各行に対応するチェックノードからのメッセージｕ_ｊが全て同時に読み込まれ、検査行列の１列に亘る各行に対応するチェックノードからのメッセージが積算されて、その積算値が求められる。その後、その積算値から、メッセージｖ_ｉを求めたい枝から供給されたメッセージが減算され、その結果得られる減算値から、受信値ｕ_０ｉを加算することで、式（１）の演算が行われ、これにより、メッセージｖ_ｉが求められる。即ち、バリアブルノードへの枝すべてからのメッセージの和から、メッセージｖ_ｉを求めたい枝からのメッセージを減算することで、メッセージｖ_ｉを求めたい枝へのメッセージが求められる。
【００７３】
なお、図１４では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、バリアブルノード計算器２０４_ｐを表している。また、図１４の回路は一つのバリアブルノードに相当する。ここで処理の対象としている図８の検査行列については、その列数である９０列のバリアブルノードが存在するから、図１２の復号装置は、図１４に示したようなバリアブルノード計算器２０４_ｐを９０個有している。
【００７４】
ここで、図１４のバリアブルノード計算器２０４_ｐでは、５個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図８の検査行列は、重みが５，３，２，１の列が、それぞれ、１５列、４５列、２９列、１列あるので、バリアブルノード計算器２０４_１乃至２０４_９０のうちの１５個は、図１４の回路と同一構成となっており、残りの４５，２９，１個は、図１４の回路と同様の３，２，１つのメッセージを同時にそれぞれ計算することができる回路構成となっている。
【００７５】
なお、図示しないが、図１２の復号装置においても、図９における場合と同様に、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が復号結果として出力される。
【００７６】
図１２の復号装置によれば、２６９個ある枝に対応するメッセージすべてを１クロックで同時に計算することができる。
【００７７】
図１２の復号装置を繰り返し用いて復号する場合には、チェックノード演算とバリアブルノード演算とを交互に行い、１回の復号を２クロックで行うことができる。従って、例えば、５０回の復号を行うためには、９０個の符号情報を受信する間に ２×５０＝１００クロック動作すれば良いことになり、ほぼ受信周波数と同一の動作周波数でよいことになる。一般的に、ＬＤＰＣ符号は、符号長が数千から数万と大きいことから、図１２の復号装置を用いれば、復号回数を極めて多くすることができ、誤り訂正性能の向上が期待できる。
【００７８】
しかしながら、図１２の復号装置は、タナーグラフのすべての枝に対応するメッセージの演算を、並列で行うため、回路規模が、符号長に比例して大きくなる。また、図１２の復号装置を、ある符号長の、ある符号化率の、ある検査行列を持つＬＤＰＣ符号の復号を行う装置として構成した場合、その復号装置において、他の符号長や、他の符号化率、他の検査行列を持つＬＤＰＣ符号の復号を行うことは困難となる。即ち、図１２の復号装置は、図９の復号装置のように、制御信号を変えるだけでは、様々な符号を復号することはできず、符号依存性が高い。
【００７９】
図９および図１２の復号装置の他に、一つでも全てでもなく、４つずつのメッセージの計算を同時に行う実装法について、例えば、非特許文献２に述べられているが、この場合、メモリの異なるアドレスからの同時読み出し、もしくは同時書き込みを避けることが一般的には容易でなく、メモリアクセス制御が困難であるという問題がある。
【００８０】
また、サムプロダクトアルゴリズムを近似して実装する方法なども提案されているが、この方法では、性能の劣化を招いてしまう。
【００８１】
【非特許文献１】
Ｃ． Ｈｏｗｌａｎｄ ａｎｄ Ａ． Ｂｌａｎｋｓｂｙ， ”Ｐａｒａｌｌｅｌ Ｄｅｃｏｄｉｎｇ Ａｒｃｈｉｔｅｃｔｕｒｅｓ ｆｏｒ Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ”， Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ， ２００１
【００８２】
【非特許文献２】
Ｅ． Ｙｅｏ， Ｐ． Ｐａｋｚａｄ， Ｂ． Ｎｉｋｏｌｉｃ ａｎｄ Ｖ． Ａｎａｎｔｈａｒａｍ， ”ＶＬＳＩ Ａｒｃｈｉｔｅｃｔｕｒｅｓ ｆｏｒ ｉｔｅｒａｔｉｖｅ Ｄｅｃｏｄｅｒｓ ｉｎ Ｍａｇｎｅｔｉｃ Ｒｅｃｏｒｄｉｎｇ Ｃｈａｎｎｅｌｓ”， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍａｇｎｅｔｉｃｓ， Ｖｏｌ． ３７， Ｎｏ． ２， Ｍａｒｃｈ ２００１
【００８３】
【発明が解決しようとする課題】
図１５は、符号長９０、符号化率２／３のＬＤＰＣ符号の検査行列の一例である。この検査行列で表されるＬＤＰＣ符号の復号装置を実装することを考える場合、枝に対応するメッセージを一つずつ計算する復号装置、もしくは枝に対応するメッセージを全て同時に計算する復号装置の設計自体は難しいことではない。
【００８４】
しかしながら、その復号装置の実現は、回路規模や動作速度の面から見て、容易ではない。
【００８５】
また、図１５の検査行列で表される符号を、ある数Ｐ個の枝を同時に計算する復号装置を用いて復号する場合、枝データ（枝に対応するメッセージ）を格納するメモリにおいては、各行または各列毎に異なる位置（アドレス）からの読み出しまたは書き込みのアクセスが必要になるため、各行または各列毎に別々のＦＩＦＯを用いることが必要になる。更に、メッセージについては、チェックノード演算で計算された順序と、次のバリアブルノード演算で使われる順番が入れ替わることもあり、メッセージを格納するメモリを、単純にＦＩＦＯで実現することも容易ではない。
【００８６】
本発明は、このような状況に鑑みてなされたものであり、ロジック、メモリ共に回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行うことができるようにするものである。
【００８７】
【課題を解決するための手段】
本発明の復号方法は、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、ＬＤＰＣ符号を復号する復号ステップを備えることを特徴とする。
【００８８】
本発明の復号装置は、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、ＬＤＰＣ符号を復号する復号手段を備えることを特徴とする。
【００８９】
本発明のプログラムは、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、ＬＤＰＣ符号を復号する復号ステップを備えることを特徴とする。
【００９０】
本発明においては、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、ＬＤＰＣ符号が復号される。
【００９１】
【発明の実施の形態】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００９２】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００９３】
請求項４に記載の復号装置は、
ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号の復号装置であって、
元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記ＬＤＰＣ符号を復号する復号手段（例えば、図１８の枝データ格納メモリ３００および３０４、チェックノード計算部３０２、サイクリックシフト回路３０３および３０８、バリアブルノード計算部３０７、並びに復号語計算部３０９）を備えることを特徴とする。
【００９４】
請求項６に記載の復号装置は、
前記復号手段は、
前記ＬＤＰＣ符号の復号のためのＰ個のチェックノードの演算を同時に行うチェックノード計算手段（例えば、図１８のチェックノード計算部３０２）と、
前記ＬＤＰＣ符号の復号のためのＰ個のバリアブルノードの演算を同時に行うバリアブルノード計算手段（例えば、図１８のバリアブルノード計算部３０７）と
を有する
ことを特徴とする。
【００９５】
請求項７に記載の復号装置は、
前記チェックノード計算手段は、チェックノードの演算を行うＰ個のチェックノード計算器（例えば、図１８のチェックノード計算器３０２_１乃至３０２_５）を有し、
前記バリアブルノード計算手段は、バリアブルノードの演算を行うＰ個のバリアブルノード計算器（例えば、図１８のバリアブルノード計算器３０７_１乃至３０７_５）を有する
ことを特徴とする。
【００９６】
請求項８に記載の復号装置は、
前記復号手段は、前記Ｐ個のチェックノードの演算、または前記Ｐ個のバリアブルノードの演算の結果得られるＰ個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段（例えば、図１８の枝データ格納メモリ３００または３０４）をさらに有する
ことを特徴とする。
【００９７】
請求項１４に記載の復号装置は、
前記復号手段は、受信情報を格納するとともに、Ｐ個の前記受信情報を同時に読み出す受信情報記憶手段（例えば、図１８の受信データ用メモリ３０６）をさらに有する
ことを特徴とする。
【００９８】
請求項１６に記載の復号装置は、
前記復号手段は、前記Ｐ個のチェックノードの演算、または前記Ｐ個のバリアブルノードの演算の結果得られるメッセージをサイクリックシフトするサイクリックシフト手段（例えば、図１８のサイクリックシフト回路３０３または３０８）をさらに有する
ことを特徴とする。
【００９９】
請求項１８に記載の復号装置は、
受信した前記ＬＤＰＣ符号の符号系列に対して、前記元の検査行列に対して行われた列置換と同一の列置換を行い、置換符号系列を出力する符号系列置換手段（例えば、図１８の受信データ並べ替え部３１０）をさらに備え、
前記復号手段は、前記変換検査行列と、前記置換符号系列とを用いて、前記符号系列を復号する
ことを特徴とする。
【０１００】
請求項１９に記載の復号装置は、
前記復号手段の出力に対して、前記元の検査行列に対して行われた列置換の逆置換を行い、最終的な復号結果を出力する逆置換手段（例えば、図１８の復号データ並べ替え部３１１）をさらに備える
ことを特徴とする。
【０１０１】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１０２】
図１６は、図１５の検査行列に、式（８）の行置換と、式（９）の列置換を施して得られる検査行列を示している。
【０１０３】
行置換：６ｘ＋ｙ＋１行目→５ｙ＋ｘ＋１行目・・・（８）
【０１０４】
列置換：６ｓ＋ｔ＋６１列目→５ｔ＋ｓ＋６１列目・・・（９）
【０１０５】
但し、式（８）および（９）において、ｘ，ｙ，ｓ，ｔは、それぞれ、０≦ｘ＜５，０≦ｙ＜６，０≦ｓ＜５，０≦ｙ＜６の範囲の整数である。
【０１０６】
式（８）の行置換によれば、６で割って余りが１になる１，７，１３，１９，２５行目を、それぞれ、１，２，３，４，５行目に、６で割って余りが２になる２，８，１４，２０，２６行目を、それぞれ、６，７，８，９，１０行目に、という具合に置換が行われる。
【０１０７】
また、式（９）の列置換によれば、６１列目以降に対して、６で割って余りが１になる６１，６７，７３，７９，８５列目を、それぞれ、６１，６２，６３，６４，６５列目に、６で割って余りが２になる６２，６８，７４，８０，８６列目を、それぞれ、６６，６７，６８，６９，７０列目に、という具合に置換が行われる。
【０１０８】
このようにして、図１５の検査行列に対して、行と列の置換を行って得られた行列（ｍａｔｒｉｘ）が、図１６の検査行列である。
【０１０９】
図１６の検査行列（以下、適宜、置換検査行列という）に対して、図１５の検査行列（以下、適宜、元の検査行列という）で表わされる符号（誤りのない元の符号）の符号語の系列に、式（９）と同一の置換を行ったものを乗じると、０ベクトルが出力されることは自明である。即ち、元の検査行列を行列Ｈで、置換検査行列を行列Ｈ’で、元の符号の符号語の系列を行ベクトルｃで、行ベクトルｃに式（９）の列置換を施して得られる行ベクトルをｃ’で、それぞれ表すこととすると、検査行列の性質から、Ｈｃ^Ｔ（上付のＴは転置を表す）は、０ベクトルとなるから、Ｈ’ｃ’^Ｔも、当然、０ベクトルとなる。
【０１１０】
そして、以上のことから、図１６の変換検査行列は、元の符号の符号語の系列ｃに、式（９）の列置換を行ったものを符号語とする符号ｃ’の検査行列になっている。
【０１１１】
従って、元の符号によって符号化されたデータを受信して復号する際に、受信した符号系列に、式（９）の列置換を行い、その列置換後の符号系列を、図１６の変換検査行列に基づく復号装置を用いて復号し、復号結果の系列に、式（２）の列置換の逆置換を行っても、元の符号の復号装置を用いた場合と復号結果に違いはないため、性能の劣化を招くことはないことになる。即ち、図１５の元の検査行列に基づく復号装置は、図１６の変換検査行列に基づく復号装置を用いて実現することができる。
【０１１２】
次に、図１７は、５×５の行列の単位に間隔を空けた、図１６の変換検査行列を示している。
【０１１３】
図１７においては、検査行列（変換検査行列）は、５×５の単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト（ｃｙｃｌｉｃ ｓｈｉｆｔ）した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上の和（以下、適宜、和行列という）、５×５の０行列の組合わせで表わされている。
【０１１４】
図１７の検査行列は、５×５の単位行列、準単位行列、シフト行列、和行列、０行列で構成されているということができる。そこで、検査行列を構成する、これらの５×５の行列を、以下、適宜、構成行列という。
【０１１５】
以上のようなＰ×Ｐの構成行列で表される検査行列で表される符号の復号には、チェックノードとバリアブルノードの計算を、Ｐ個同時に行うアーキテクチャ（ａｒｃｈｉｔｅｃｔｕｒｅ）を用いることができる。
【０１１６】
図１８は、そのような復号装置の一実施の形態の構成例を示すブロック図である。即ち、図１８は、図１５の元の検査行列に対して、行または列置換を行って得られる図１７の変換検査行列を用いて、ＬＤＰＣ符号の復号を行う復号装置の構成例を示している。
【０１１７】
この復号装置は、６つのＦＩＦＯ３００_１乃至３００_６からなる枝データ格納用メモリ３００、ＦＩＦＯ３００_１乃至３００_６を選択するセレクタ３０１、チェックノード計算部３０２、２つのサイクリックシフト回路３０３および３０８、１８個のＦＩＦＯ３０４_１乃至３０４_１８からなる枝データ格納用メモリ３０４、ＦＩＦＯ３０４_１乃至３０４_１８を選択するセレクタ３０５、受信情報を格納する受信データ用メモリ３０６、バリアブルノード計算部３０７、復号語計算部３０９、受信データ並べ替え部３１０、復号データ並べ替え部３１１からなる。
【０１１８】
この復号装置の各部について詳細に説明する前に、まず、枝データ格納用メモリ３００と３０４へのデータの格納方法について説明する。
【０１１９】
枝データ格納用メモリ３００は、図１７の変換検査行列の行数３０を構成行列の行数５で除算した数である６つのＦＩＦＯ３００_１乃至３００_６から構成されている。ＦＩＦＯ３００_ｙ（ｙ＝１，２，・・・，６）は、構成行列の行数および列数である５つの枝に対応するメッセージを同時に読み出しもしくは書き込むことができるようになっており、その長さ（段数）は、図１７の変換検査行列の行方向の１の数（ハミング重み）の最大数である９になっている。
【０１２０】
ＦＩＦＯ３００_１には、図１７の検査行列（変換検査行列）の第１行目から第５行目までの１の位置に対応するデータが、各行共に横方向に詰めた形に（０を無視した形で）格納される。すなわち、第ｊ行第ｉ列を、（ｊ，ｉ）と表すこととすると、ＦＩＦＯ３００_１の第１の要素（第１段）には、検査行列の（１，１）から（５，５）の５×５の単位行列の１の位置に対応するデータが格納される。第２の要素には、検査行列の（１，２１）から（５，２５）のシフト行列（５×５の単位行列を右方向に３つだけサイクリックシフトしたシフト行列）の１の位置に対応するデータが格納される。第３から第８の要素も同様に検査行列と対応づけてデータが格納される。そして、第９の要素には、検査行列の（１，８６）から（５，９０）のシフト行列（５×５の単位行列のうちの１行目の１を０に置き換えて１つだけ左にサイクリックシフトしたシフト行列）の１の位置に対応するデータが格納される。ここで、検査行列の（１，８６）から（５，９０）のシフト行列においては、１行目に１がないため、ＦＩＦＯ３００_１の１行目のみ要素数は８、残りの行は要素数が９となる。
【０１２１】
ＦＩＦＯ３００_２には、図１７の検査行列の第６行目から第１０行目までの１の位置に対応するデータが格納される。すなわち、ＦＩＦＯ３００_２の第１の要素には、検査行列の（６，１）から（１０，５）の和行列（５×５の単位行列を右に１つだけサイクリックシフトした第１のシフト行列と、右に２つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の１の位置に対応するデータが格納される。また、第２の要素には、検査行列の（６，１）から（１０，５）の和行列を構成する第２のシフト行列の１の位置に対応するデータが格納される。
【０１２２】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるＰ×Ｐの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージ）は、同一アドレス（ＦＩＦＯ３００_１乃至３００_６のうちの同一のＦＩＦＯ）に格納される。
【０１２３】
以下、第３から第９の要素についても、検査行列に対応づけてデータが格納される。ＦＩＦＯ３００_２は全行共に要素数は９となる。
【０１２４】
ＦＩＦＯ３００_３乃至３００_６も同様に検査行列に対応づけてデータを格納し、各ＦＩＦＯ３００_３乃至３００_６それぞれの長さは９である。
【０１２５】
枝データ格納用メモリ３０４は、検査行列の列数９０を、構成行列の列数である５で割った１８個のＦＩＦＯ３０４_１乃至３０４_１８から構成されている。ＦＩＦＯ３０４_ｘ（ｘ＝１，２，・・・，１８）は、構成行列の行数および列数である５つの枝に対応するメッセージを同時に読み出しもしくは書き込むことができるようになっている。
【０１２６】
ＦＩＦＯ３０４_１には、図１７の検査行列の第１列目から第５列目までの１の位置に対応するデータが、各列共に縦方向に詰めた形に（０を無視した形で）格納される。すなわち、ＦＩＦＯ３０４_１の第１の要素（第１段）には、検査行列の（１，１）から（５，５）の５×５の単位行列の１の位置に対応するデータが格納される。第２の要素には、検査行列の（６，１）から（１０，５）の和行列（５×５の単位行列を右に１つだけサイクリックシフトした第１のシフト行列と、右に２つだけサイクリックシフトした第２のシフト行列との和である和行列）を構成する第１のシフト行列の１の位置に対応するデータが格納される。また、第３の要素には、検査行列の（６，１）から（１０，５）の和行列を構成する第２のシフト行列の１の位置に対応するデータが格納される。
【０１２７】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるＰ×Ｐの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージ）は、同一アドレス（ＦＩＦＯ３０４_１乃至３０４_１８のうちの同一のＦＩＦＯ）に格納される。
【０１２８】
以下、第４および第５の要素についても、検査行列に対応づけて、データが格納される。このＦＩＦＯ３０４_１の要素数（段数）は、検査行列の第１列から第５列における行方向の１の数（ハミング重み）の最大数である５になっている。
【０１２９】
ＦＩＦＯ３０４_２と３０４_３も同様に検査行列に対応づけてデータを格納し、それぞれの長さ（段数）は、５である。ＦＩＦＯ３０４_４乃至３０４_１２も同様に検査行列に対応づけてデータを格納し、それぞれの長さは３である。ＦＩＦＯ３０４_１３乃至３０４_１８も同様に検査行列に対応づけてデータを格納し、それぞれの長さは２である。但し、ＦＩＦＯ３０４_１８の第１の要素は、検査行列の（１，８６）から（５，９０）に相当し、第５列目（検査行列の（１，９０）から（５，９０））に１がないため、データは格納されない。
【０１３０】
以下、図１８の復号装置の各部の動作について詳細に説明する。
【０１３１】
枝データ格納用メモリ３００は、６つのＦＩＦＯ３００_１乃至３００_６からなり、前段のサイクリックシフト回路３０８から供給される５つのメッセージデータＤ３１１が、検査行列どの行に属するかの情報（Ｍａｔｒｉｘデータ）Ｄ３１２に従って、データを格納するＦＩＦＯを、ＦＩＦＯ３００_１乃至３００_６の中から選び、選んだＦＩＦＯに５つのメッセージデータＤ３１１をまとめて順番に格納していく。また、枝データ格納用メモリ３００は、データを読み出す際には、ＦＩＦＯ３００_１から５つのメッセージデータＤ３００_１を順番に読み出し、次段のセレクタ３０１に供給する。枝データ格納用メモリ３００は、ＦＩＦＯ３００_１からのメッセージデータの読み出しの終了後、ＦＩＦＯ３００_２乃至３００_６からも、順番に、メッセージデータを読み出し、セレクタ３０１に供給する。
【０１３２】
セレクタ３０１は、セレクト信号Ｄ３０１に従って、ＦＩＦＯ３００_１乃至３００_６のうちの、現在データが読み出されているＦＩＦＯからの５つのメッセージデータを選択し、メッセージデータＤ３０２として、チェックノード計算部３０２に供給する。
【０１３３】
チェックノード計算部３０２は、５つのチェックノード計算器３０２_１乃至３０２_５からなり、セレクタ３０１を通して供給されるメッセージＤ３０２（Ｄ３０２_１乃至Ｄ３０２_５）を用いて、式（７）に従って演算を行い、その演算の結果得られる５つのメッセージＤ３０３（Ｄ３０３_１乃至Ｄ３０３_５）をサイクリックシフト回路３０３に供給する。
【０１３４】
ここで、チェックノード計算器３０２_１乃至３０２_５それぞれは、図１０に示したチェックノード計算器１０１と同様に構成される。
【０１３５】
サイクリックシフト回路３０３は、チェックノード計算部３０２で計算された５つのメッセージＤ３０３_１乃至Ｄ３０３_５を、対応する枝が検査行列において元となる単位行列を幾つサイクリックシフトしたものであるかの情報（Ｍａｔｒｉｘデータ）Ｄ３０５を元にサイクリックシフトし、その結果をメッセージＤ３０４として、枝データ格納用メモリ３０４に供給する。
【０１３６】
枝データ格納用メモリ３０４は、１８個のＦＩＦＯ３０４_１乃至３０４_１８からなり、前段のサイクリックシフト回路３０３から供給される５つのメッセージデータＤ３０４が検査行列のどの行に属するかの情報Ｄ３０５に従って、データを格納するＦＩＦＯを、ＦＩＦＯ３０４_１乃至３０４_１８の中から選び、選んだＦＩＦＯに５つのメッセージデータＤ３０４をまとめて順番に格納していく。また、枝データ格納用メモリ３０４は、データを読み出す際には、ＦＩＦＯ３０４_１から５つのメッセージＤ３０６_１を順番に読み出し、次段のセレクタ３０５に供給する。枝データ格納用メモリ３０４は、ＦＩＦＯ３０４_１からのデータの読み出しの終了後、ＦＩＦＯ３０４_２乃至３０４_１８からも、順番に、メッセージデータを読み出し、セレクタ３０５に供給する。
【０１３７】
セレクタ３０５は、セレクト信号Ｄ３０７に従って、ＦＩＦＯ３０４_１乃至３０４_１８のうちの、現在データが読み出されているＦＩＦＯからの５つのメッセージデータを選択し、メッセージデータＤ３０８として、バリアブルノード計算部３０７と復号語計算部３０９に供給する。
【０１３８】
一方、受信データ並べ替え部３１０は、通信路を通して受信したＬＤＰＣ符号の符号系列（受信データ）Ｄ３１３を、式（９）の列置換を行うことにより並べ替え、符号系列Ｄ３１４として、受信用データメモリ３０６に供給する。受信データ用メモリ３０６は、受信データ並べ替え部３１０から供給される符号系列Ｄ３１４から、受信ＬＬＲ（対数尤度比）を計算しており、その計算した受信ＬＬＲを５つまとめてデータＤ３０９として、バリアブルノード計算部３０７と復号語計算部３０９に供給する。
【０１３９】
バリアブルノード計算部３０７は、５つのバリアブルノード計算器３０７_１乃至３０７_５からなり、セレクタ３０５を通して供給されるメッセージＤ３０８（Ｄ３０８_１乃至Ｄ３０８_５）と、受信データ用メモリ３０６から供給される５つの受信ＬＬＲ Ｄ３０９を用いて、式（１）に従って演算を行い、その演算の結果得られるメッセージＤ３１０（Ｄ３１０_１乃至Ｄ３１０_５）を、サイクリックシフト回路３０８に供給する。
【０１４０】
ここで、バリアブルノード計算器３０７_１乃至３０７_５それぞれは、図１１のバリアブルノード計算器１０３と同様に構成される。
【０１４１】
サイクリックシフト回路３０８は、バリアブルノード計算部３０７で計算されたメッセージＤ３１０_１乃至Ｄ３１０_５を、対応する枝が検査行列において元となる単位行列を幾つサイクリックシフトしたものであるかの情報を元にサイクリックシフトし、その結果をメッセージＤ３１１として、枝データ格納用メモリ３００に供給する。
【０１４２】
以上の動作を１巡することで、ＬＤＰＣ符号の１回の復号を行うことができる。図１８の復号装置は、所定の回数だけＬＤＰＣ符号を復号した後、復号語計算部３０９および復号データ並べ替え部３１１において、最終的な復号結果を求めて出力する。
【０１４３】
即ち、復号語計算部３０９は、５つの復号語計算器３０９_１乃至３０９_５からなり、セレクタ３０５が出力する５つのメッセージＤ３０８（Ｄ３０８_１乃至Ｄ３０８_５）と、受信データ用メモリ３０６から供給される５つの受信ＬＬＲ Ｄ３０９を用い、複数回の復号の最終段において、式（５）に基づいて、復号結果（復号語）を計算して、その結果得られる復号データＤ３１５を、復号データ並べ替え部３１１に供給する。
【０１４４】
復号データ並べ替え部３１１は、復号語計算部３０９から供給される復号データＤ３１５を対象に、式（９）の列置換の逆置換を行うことにより、その順序を並べ替え、最終的な復号結果Ｄ３１６として出力する。
【０１４５】
なお、枝データ（枝に対応するメッセージ）が欠ている箇所に関しては、メモリ格納時（枝データ格納用メモリ３００と３０４へのデータ格納時）には、何のメッセージも格納せず、また、ノード演算時（チェックノード計算部３０２でのチェックノード演算時とバリアブルノード計算部３０７でのバリアブルノード演算時）にも何の演算も行わない。
【０１４６】
また、サイクリックシフト回路３０３および３０８には、バレルシフタを用いると回路規模を小さくしながら所望の操作を実現できる。
【０１４７】
上記説明には、枝データ格納にＦＩＦＯを用いたが（枝データ格納メモリ３００と３０４をＦＩＦＯで構成するようにしたが）、ＦＩＦＯの代わりにＲＡＭを用いても構わない。その場合、ＲＡＭには、Ｐ個の枝情報（枝に対応するメッセージ）を同時に読み出すことの出来るビット幅と、枝総数／Ｐのワード（ｗｏｒｄ）数が必要となる。さらに、ＲＡＭへの書き込みは、検査行列の情報から、書き込もうとしているデータが次に読み出される際に何番目に読み出されるかを求め、その位置に書き込む。また、ＲＡＭからの読み出しの際には、アドレスの先頭から順次データを読み出す。ＦＩＦＯの代わりにＲＡＭを用いると、セレクタ３０１および３０５は不要になる。
【０１４８】
なお、ＦＩＦＯやＲＡＭの物理的なビット幅が足りない場合には、複数のＲＡＭを用いて同じ制御信号を与えることで、論理的に１つのＲＡＭとみなすことができる。
【０１４９】
また、上述の場合には、説明を簡単にするために、Ｐが５の場合、即ち、検査行列を構成する構成行列の行数および列数が５の場合を例に挙げたが、構成行列の行数および列数Ｐは必ずしも５である必要はなく、検査行列によって異なる値を取ることもあり得る。例えば、Ｐは３６０や３９２であってもよい。
【０１５０】
また、本実施の形態では、符号長９０、符号化率２／３のＬＤＰＣ符号を用いたが、ＬＤＰＣ符号の符号長や符号化率は、幾つであっても構わない。例えば、構成行列の行数および列数Ｐが５の場合、枝総数が５以下であれば、どんな符号長、符号化率のＬＤＰＣ符号でも、制御信号を代えるだけで、図１８の復号装置を用いて復号可能である。
【０１５１】
さらに、構成行列の行数および列数Ｐが所定の値で、枝の総数がある値以下、という条件を満たすあるＬＤＰＣ符号の復号装置は、その条件を満たす、任意の符号長で、任意の符号化率のＬＤＰＣ符号を復号することができる。
【０１５２】
以上のように、検査行列（元の検査行列）に対して、行置換と列置換うちの一方または両方を施し、Ｐ×Ｐの単位行列、そのコンポーネントの１のうち１個以上が０になった準単位行列、単位行列もしくは準単位行列をサイクリックシフトしたシフト行列、単位行列、準単位行列、もしくはシフト行列の複数の和である和行列、Ｐ×Ｐの０行列の組合せ、つまり、構成行列の組み合わせで表わすことができる検査行列（変換検査行列）に変換することで、ＬＤＰＣ符号の復号を、チェックノードとバリアブルノードの演算をＰ個同時に行うアーキテクチャ（ａｒｃｈｉｔｅｃｔｕｒｅ）を採用することが可能となり、これにより、ノード演算を、Ｐ個同時に行うことで動作周波数を実現可能な範囲に抑えることができ、多数の繰り返し復号を行うことを可能にしつつ、メモリ（ＦＩＦＯやＲＡＭ）への書き込みと読み出し時に、異なるアドレスへの同時アクセスが起きることを防止することができる。
【０１５３】
即ち、上述した検査行列の行置換と列置換の双方もしくは片方を行うことで、チェックノードとバリアブルノードの演算をＰ個同時に行うことが可能となり、さらに、このようにノード演算をＰ個同時に行うことで、動作周波数を実現可能な範囲に抑えることができ、多数の繰り返し復号を行うことを可能にしつつ、メモリ（ＦＩＦＯやＲＡＭ）への書き込みと読み出し時に、異なるアドレスへの同時アクセスが起きることを防止することができる。
【０１５４】
さらに、図１７の検査行列（変換検査行列）で表わされるＬＤＰＣ符号を復号する場合には、２６９個の枝をチェックノード、バリアブルノード毎に５個ずつ演算することが可能であることから、１回の復号に、２６９／５×２≒１０８クロック動作すればよいことになる。５０回の復号には、９０個の符号情報を受信する間に、１０８×５０＝５４００クロック動作すればよいことになり、受信周波数の約６０倍の動作周波数でよいことになる。従って、図１８の復号装置によれば、各ノード演算を一つずつ行う図９の復号装置に比べて、１／５の動作周波数で済むことになる。また、回路規模の面から見ても、メモリの大きさは同じであるため、論理回路が多少大きくなっても全体への影響は小さいと言える。
【０１５５】
一般的に、ＬＤＰＣ符号は符号長が数千から数万と大きいため、Ｐの値も数百の大きさを持つものが使われる。その場合には、更に本発明に係る復号装置を用いる効果は大きくなる。
【０１５６】
以上のように、ロジック、メモリ共に回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑えることができ、メモリアクセスの制御も容易に行うことができる。
【０１５７】
また、ＬＤＰＣ符号の性質から、検査行列に行置換や列置換を施しても符号の性能は変わらない。従って、行置換または列置換によって、構成行列の組み合わせで表すことができる変換検査行列を得られる検査行列に対応するＬＤＰＣ符号については、どのような符号長、符号化率のＬＤＰＣ符号であっても、性能の劣化を招くことなく、実装が容易で、かつ効率の良い復号を行うことができる。
【０１５８】
さらに、本発明に係る復号装置は、サムプロダクトアルゴリズムを忠実に実装するものであるため、メッセージの量子化以外の復号損失が起きることはない。
【０１５９】
以上の観点から、本発明に係る復号装置を用いることで、高性能な復号が可能になる。
【０１６０】
なお、検査行列が、構成行列の行数および列数Ｐの倍数でない場合は、検査行列の端数の外側にすべて０（ａｌｌ ０）の成分を付けてＰの倍数とみなして適用できることがある。
【０１６１】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０１６２】
そこで、図１９は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０１６３】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク４０５やＲＯＭ４０３に予め記録しておくことができる。
【０１６４】
あるいはまた、プログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｃ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ Ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体４１１に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体４１１は、いわゆるパッケージソフトウエアとして提供することができる。
【０１６５】
なお、プログラムは、上述したようなリムーバブル記録媒体４１１からコンピュータにインストールする他、ダウンロードサイトから、ディジタル衛星放送用の人工衛星を介して、コンピュータに無線で転送したり、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを、通信部４０８で受信し、内蔵するハードディスク４０５にインストールすることができる。
【０１６６】
コンピュータは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）４０２を内蔵している。ＣＰＵ４０２には、バス４０１を介して、入出力インタフェース４１０が接続されており、ＣＰＵ４０２は、入出力インタフェース４１０を介して、ユーザによって、キーボードや、マウス、マイク等で構成される入力部４０７が操作等されることにより指令が入力されると、それにしたがって、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）４０３に格納されているプログラムを実行する。あるいは、また、ＣＰＵ４０２は、ハードディスク４０５に格納されているプログラム、衛星若しくはネットワークから転送され、通信部４０８で受信されてハードディスク４０５にインストールされたプログラム、またはドライブ４０９に装着されたリムーバブル記録媒体４１１から読み出されてハードディスク４０５にインストールされたプログラムを、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）４０４にロードして実行する。これにより、ＣＰＵ４０２は、上述したフローチャートにしたがった処理、あるいは上述したブロック図の構成により行われる処理を行う。そして、ＣＰＵ４０２は、その処理結果を、必要に応じて、例えば、入出力インタフェース４１０を介して、ＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）やスピーカ等で構成される出力部４０６から出力、あるいは、通信部４０８から送信、さらには、ハードディスク４０５に記録等させる。
【０１６７】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０１６８】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【０１６９】
【発明の効果】
以上の如く、本発明によれば、回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行うことが可能となる。
【図面の簡単な説明】
【図１】ＬＤＰＣ符号の検査行列Ｈを説明する図である。
【図２】ＬＤＰＣ符号の復号手順を説明するフローチャートである。
【図３】メッセージの流れを説明する図である。
【図４】ＬＤＰＣ符号の検査行列の例を示す図である。
【図５】検査行列のタナーグラフを示す図である。
【図６】バリアブルノードを示す図である。
【図７】チェックノードを示す図である。
【図８】ＬＤＰＣ符号の検査行列の例を示す図である。
【図９】ノード演算を一つずつ行うＬＤＰＣ符号の復号装置の構成例を示すブロック図である。
【図１０】メッセージを一つずつ計算するチェックノード計算器の構成例を示すブロック図である。
【図１１】メッセージを一つずつ計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１２】ノード演算を全て同時に行うＬＤＰＣ符号の復号装置の構成例を示すブロック図である。
【図１３】メッセージを同時に計算するチェックノード計算器の構成例を示すブロック図である。
【図１４】メッセージを同時に計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１５】ＬＤＰＣ符号の検査行列の例を示す図である。
【図１６】検査行列に行置換と列置換を施した行列を示す図である。
【図１７】５×５単位に分割した検査行列を示す図である。
【図１８】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図１９】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
３００ 枝データ格納用メモリ， ３０１ セレクタ， ３０２ チェックノード計算部， ３０３ サイクリックシフト回路， ３０４ 枝データ格納用メモリ， ３０５ セレクタ， ３０６ 受信データ用メモリ， ３０７ バリアブルノード計算部， ３０８ サイクリックシフト回路， ３０９ 復号語計算部， ３１０ 受信データ並べ替え部， ３１１ 復号データ並べ替え部， ４０１ バス， ４０２ ＣＰＵ， ４０３ ＲＯＭ， ４０４ ＲＡＭ， ４０５ ハードディスク， ４０６ 出力部， ４０７ 入力部， ４０８ 通信部， ４０９ ドライブ， ４１０ 入出力インタフェース， ４１１ リムーバブル記録媒体

Claims (20)

1. ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号の復号方法であって、
   元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記ＬＤＰＣ符号を復号する復号ステップを備える
   ことを特徴とする復号方法。
2. 請求項１に記載の復号方法であって、
   Ｐ×Ｐの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはＰ×Ｐの０行列を構成行列として、前記変換検査行列は、複数の前記構成行列の組合せで表される
   ことを特徴とする復号方法。
3. 請求項１に記載の復号方法であって、
   受信した前記ＬＤＰＣ符号の符号系列に対して、前記元の検査行列に対して行われた列置換と同一の列置換を行い、置換符号系列を出力する符号系列置換ステップをさらに備え、
   前記復号ステップにおいて、前記変換検査行列と、前記置換符号系列とを用いて、前記符号系列を復号する
   ことを特徴とする復号方法。
4. ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号の復号装置であって、
   元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記ＬＤＰＣ符号を復号する復号手段を備える
   ことを特徴とする復号装置。
5. 請求項４に記載の復号装置であって、
   Ｐ×Ｐの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはＰ×Ｐの０行列を構成行列として、前記変換検査行列は、複数の前記構成行列の組合せで表される
   ことを特徴とする復号装置。
6. 請求項５に記載の復号装置であって、
   前記復号手段は、
   前記ＬＤＰＣ符号の復号のためのＰ個のチェックノードの演算を同時に行うチェックノード計算手段と、
   前記ＬＤＰＣ符号の復号のためのＰ個のバリアブルノードの演算を同時に行うバリアブルノード計算手段と
   を有する
   ことを特徴とする復号装置。
7. 請求項６に記載の復号装置であって、
   前記チェックノード計算手段は、チェックノードの演算を行うＰ個のチェックノード計算器を有し、
   前記バリアブルノード計算手段は、バリアブルノードの演算を行うＰ個のバリアブルノード計算器を有する
   ことを特徴とする復号装置。
8. 請求項６に記載の復号装置であって、
   前記復号手段は、前記Ｐ個のチェックノードの演算、または前記Ｐ個のバリアブルノードの演算の結果得られるＰ個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段をさらに有する
   ことを特徴とする復号装置。
9. 請求項８に記載の復号装置であって、
   前記メッセージ記憶手段は、チェックノード演算時に読み出される枝に対応するメッセージデータを、前記変換検査行列の１を行方向に詰めるように格納する
   ことを特徴とする復号装置。
10. 請求項８に記載の復号装置であって、
    前記メッセージ記憶手段は、バリアブルノード演算時に読み出される枝に対応するメッセージデータを、前記変換検査行列の１を列方向に詰めるように格納する
    ことを特徴とする復号装置。
11. 請求項８に記載の復号装置であって、
    前記メッセージ記憶手段は、前記変換検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するＰ個の枝に対応するメッセージを、同一のアドレスに格納する
    ことを特徴とする復号装置。
12. 請求項８に記載の復号装置であって、
    前記メッセージ記憶手段は、行数／Ｐ個のＦＩＦＯと、列数／Ｐ個のＦＩＦＯとで構成され、
    前記行数／Ｐ個のＦＩＦＯと列数／Ｐ個のＦＩＦＯは、それぞれ、前記検査行列の行と列の重みに対応するワード数を有する
    ことを特徴とする復号装置。
13. 請求項８に記載の復号装置であって、
    前記メッセージ記憶手段は、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）で構成され、
    前記ＲＡＭは、前記メッセージデータを、読み出される順番に詰めて格納し、格納位置順に読み出す
    ことを特徴とする復号装置。
14. 請求項６に記載の復号装置であって、
    前記復号手段は、受信情報を格納するとともに、Ｐ個の前記受信情報を同時に読み出す受信情報記憶手段をさらに有する
    ことを特徴とする復号装置。
15. 請求項１４に記載の復号装置であって、
    前記受信情報記憶手段は、前記受信情報を、前記バリアブルノードの演算に必要となる順番に読み出すことができるように格納する
    ことを特徴とする復号装置。
16. 請求項６に記載の復号装置であって、
    前記復号手段は、前記Ｐ個のチェックノードの演算、または前記Ｐ個のバリアブルノードの演算の結果得られるメッセージをサイクリックシフトするサイクリックシフト手段をさらに有する
    ことを特徴とする復号装置。
17. 請求項１６に記載の復号装置であって、
    前記サイクリックシフト手段は、バレルシフタで構成される
    ことを特徴とする復号装置。
18. 請求項４に記載の復号装置であって、
    受信した前記ＬＤＰＣ符号の符号系列に対して、前記元の検査行列に対して行われた列置換と同一の列置換を行い、置換符号系列を出力する符号系列置換手段をさらに備え、
    前記復号手段は、前記変換検査行列と、前記置換符号系列とを用いて、前記符号系列を復号する
    ことを特徴とする復号装置。
19. 請求項１８に記載の復号装置であって、
    前記復号手段の出力に対して、前記元の検査行列に対して行われた列置換の逆置換を行い、最終的な復号結果を出力する逆置換手段をさらに備える
    ことを特徴とする復号装置。
20. ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号の復号をコンピュータに行わせるプログラムであって、
    元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記ＬＤＰＣ符号を復号する復号ステップを備える
    ことを特徴とするプログラム。

Images