(57)【要約】【課題】  符号化装置の回路規模を小さくする。【解決手段】  情報ビット格納メモリ１２１は、入力データD121を格納する。情報ビット格納メモリ１２１は、制御信号生成部１２４から供給される制御信号D125に基づいて、格納している入力データD121の各ビットのうちの、LDPC符号の検査行列にしたがったビットを読み出し、情報ビットD122-1乃至D122-7として、演算器１２２に供給する。演算器１２２は、情報ビットD122-1乃至D122-7と、シフトレジスタ１２３に記憶された１ビットのパリティビットD123とを加算することにより、LDPC符号の新たな１ビットのパリティビットD124を求め、シフトレジスタ１２３に記憶させる。本発明は、LDPC符号化を行う符号化装置に適用することができる。【選択図】図８
2005051469.tif 000002
【特許請求の範囲】
【請求項１】
所定の情報をLDPC(Low Density Parity Check)符号に符号化する符号化装置であって、
前記LDPC符号のパリティの１ビットを記憶する記憶手段と、
前記情報の各ビットのうちの、前記LDPC符号の検査行列にしたがったビットと、前記記憶手段に記憶された１ビットのパリティとを加算することにより、前記LDPC符号の新たな１ビットのパリティを求め、前記記憶手段に供給する演算手段と
を備えることを特徴とする符号化装置。
【請求項２】
請求項１に記載の符号化装置であって、
前記検査行列の、前記LDPC符号のパリティに対応するパリティ部は、階段状の構造を有する
ことを特徴とする符号化装置。
【請求項３】
請求項１に記載の符号化装置であって、
前記演算手段で用いられる前記検査行列は、元の検査行列の行置換または前記元の検査行列のパリティ部の列置換を行うことにより、パリティ部が階段状の構造を有するものにされたものである
ことを特徴とする符号化装置。
【請求項４】
請求項１に記載の符号化装置であって、
前記情報を格納し、格納した情報の各ビットが１回以上読み出される情報格納手段をさらに備える
ことを特徴とする符号化装置。
【請求項５】
請求項１に記載の符号化装置であって、
前記情報を格納し、格納した情報が1ビットずつ読み出される情報格納手段をさらに備える
ことを特徴とする符号化装置。
【請求項６】
請求項５に記載の符号化装置であって、
前記演算手段により演算された演算結果を間引く間引き手段をさらに備える
ことを特徴とする符号化装置。
【請求項７】
所定の情報をLDPC(Low Density Parity Check)符号に符号化する符号化装置の符号化方法であって、
前記LDPC符号のパリティの１ビットを記憶手段に記憶させる記憶ステップと、
前記情報の各ビットのうちの、前記LDPC符号の検査行列にしたがったビットと、前記記憶手段に記憶された１ビットのパリティとを加算することにより、前記LDPC符号の新たな１ビットのパリティを求め、前記記憶手段に供給する演算ステップと
を含むことを特徴とする符号化方法。
【請求項８】
所定の情報のLDPC(Low Density Parity Check)符号化をコンピュータに行わせるプログラムであって、
前記LDPC符号のパリティの１ビットを記憶手段に記憶させる記憶ステップと、
前記情報の各ビットのうちの、前記LDPC符号の検査行列にしたがったビットと、前記記憶手段に記憶された１ビットのパリティとを加算することにより、前記LDPC符号の新たな１ビットのパリティを求め、前記記憶手段に供給する演算ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置および符号化方法、並びにプログラムに関し、特に、所定の情報を低密度パリティ検査符号化する符号化装置および符号化方法、並びにプログラムに関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))化や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))化といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されている。
【０００４】
縦列連接畳み込み符号化は、２つの畳み込み符号化器とインターリーバとを縦列に連接して構成される装置により行われる。そして、縦列連接畳み込み符号の復号は、軟出力（soft-output）を出力する２つの復号回路を縦列に連接して構成される装置により行われ、２つの復号回路の間で情報をやり取りし、最終的な復号結果が得られる。
【０００５】
また、この縦列連接畳み込み符号化の応用として、非特許文献１に記載されているrepeat-accumulate code（ＲＡ符号）化が知られている。更に、非特許文献２はＲＡ符号化を発展させたirregular repeat-accumulate code（IRA符号）化を提案している。
【０００６】
図１は、IRA符号化を行う符号化装置の構成例を示している。
【０００７】
符号化装置１は、エンコード（repetition code）部１１、インターリーバ(interleaver)１２、およびアキュームレータ(accumulator)１３から構成されている。
【０００８】
繰り返し符号化部１１は、符号化の対象である入力データD11の第１の符号（以下、適宜、外符号と称する）化を行う。具体的には、繰り返し符号化部１１は、入力データD11の各ビットを一定ではない任意の回数だけ繰り返して、第１の符号D12としてインターリーバ１２に供給する。インターリーバ１２は、繰り返し符号化部１１から供給される第１の符号D12の順序を並べ替え、データD13として、アキュームレータ１３に供給する。アキュームレータ１３は、データD13の第２の符号（以下、適宜、内符号と称する）化を行い、第２の符号D14を出力する。
【０００９】
符号化装置１では、入力データD11に対するIRA符号化結果として、入力データD11と、アキュームレータ１３から出力される第２の符号D14とを合わせた符号系列が、通信路に出力される。
【００１０】
図２は、図１のインターリーバ１２の構成例を示している。
【００１１】
インターリーバ１２は、入力データ保持メモリ３１、置換データROM（Read Only Memory）３２、データ置換回路３３、および出力データ保持メモリ３４から構成される。
【００１２】
インターリーバ１２には、繰り返し符号化部１１から第１の符号D12が供給され、その第１の符号D12が入力データ保持メモリ３１に保持される。入力データ保持メモリ３１は、保持している第１の符号D12を読み出し、データ置換回路３３に供給する。置換データROM３２は、データ置換回路３３で行われる、第1の符号D12に対する置換の位置情報を格納している。データ置換回路３３は、置換データROM３２に格納されている置換の位置情報を読み出し、その置換の位置情報に基づいて、入力データ保持メモリ３１から供給される第1の符号D12の位置の置換（順序の並べ替え）を行う。そして、データ置換回路３３は、その置換結果を出力データ保持メモリ３４に供給して保持させる。そして、出力データ保持メモリ３４は、保持した第１の符号D12の置換結果を読み出し、データD13としてアキュームレータ１３に出力する。
【００１３】
即ち、インターリーバ１２は、繰り返し符号化部１１から供給される第1の符号D12にインターリーブを施し、その結果をデータD13としてアキュームレータ１３に供給する。
【００１４】
図３は、図１のアキュームレータ１３の構成例を示している。
【００１５】
アキュームレータ１３では、インターリーバ１２から供給されるデータD13の、例えば、連続する７個を1セットとして、その1セットの入力に対して所定の処理が施され、１個のデータが出力される。
【００１６】
アキュームレータ１３は、演算器５１とシフトレジスタ５２から構成される。演算器５１には、インターリーバ１２から７個のデータD13が供給され、そのデータD13は、演算器５１に供給される。演算器５１は、インターリーバ１２から供給される７個のデータD13と、シフトレジスタ５２から供給されたデータとをGF(2)上で加算し（排他的論理和を演算し）、その加算結果を第２の符号D14として出力するとともに、シフトレジスタ５２に供給する。シフトレジスタ５２は、演算器５１から供給された第２の符号D14を格納し、既に格納しているデータ（直前に演算器５１で加算された加算結果）を演算器５１に供給する。
【００１７】
なお、演算器５１に供給されるデータD13は、連続する７個のデータではなく、連続する何個のデータでもよい。
【００１８】
これらのターボ符号化が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、適宜、LDPC符号という）化が脚光を浴びつつある。
【００１９】
LDPC符号は、R. G. Gallagerによる非特許文献３において最初に提案されたものであり、その後、非特許文献４や非特許文献５等によって再発見されるに至ったものである。
【００２０】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【００２１】
以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
【００２２】
LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列としては、例えば、図４に示すように、各列のハミング重み（"1"の数）(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。
【００２３】
このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。
【００２４】
このようなLDPC符号への符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを２元の情報（メッセージ）に対して乗算することによって符号語cを生成することで実現される。具体的には、LDPC符号への符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列である場合には、符号化装置は、生成行列Gに対してkビットからなる情報語を乗算し、nビットからなる符号語c（＝ｕＧ）を生成する。この符号化装置によって生成された符号語cは、値が"0"の符号ビットが"+1"に、値が"1"の符号ビットが"-1"にといったようにマッピングされて送信され、所定の通信路を介して復号装置によって受信されることになる。
【００２５】
ところで、一般に、特に符号長が大きいとき、検査行列から生成行列を求めることは簡単ではない。また、生成行列が求まっても、それが低密度にならない場合が多く、その場合、符号化の演算量が膨大になる。そこで、LDPC符号を、情報に１ビット以上のパリティを付加して構成する場合には、検査行列Hと、情報をLDPC符号化した符号語cとの積が０（０ベクトル）になることを利用して、情報に付加されるパリティを求めることにより、その情報のLDPC符号化を行う方法がある。このようなLDPC符号化は、図１の符号化装置１によって行うことが可能である。
【００２６】
【非特許文献１】D.Divsalar,H.Jin,R.J.McEliece, “Coding Theorems for “Turbo-Like” Codes,” in Proc.36th Allerton Conf.on Communication,Control,and Computing, Allerton, Illinois,U.S.A.,pp.201-210,Sept.1998
【非特許文献２】H.Jin,A.Khandekar,R.J.McEliece, “Irregular Repeat-Accumulate Codes,”in Proc.2nd International Symposium on Turbo Codes & Related Topics,Brest,France,pp.1-8,Sept.2000
【非特許文献３】R. G. Gallager, “Low Density Parity Check Codes” Cambridge, Massachusetts: M. I. T. Press, 1963
【非特許文献４】D. J. C. MacKay, “Good error correcting codes based on very sparse matrices,” Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999
【非特許文献５】M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs,” Available at http://www.icsi.berkeley.edu/luby/
【発明の開示】
【発明が解決しようとする課題】
【００２７】
しかしながら、図１の符号化装置１を用いて、情報をLDPC符号化する場合、繰り返し符号化部１１は、入力データD11を一定ではない任意の回数だけ繰り返して、第１の符号D12としてインターリーバ１２に供給するため、入力データを格納するメモリが必要である。さらに、インターリーバ１２では、繰り返し符号化部１１から供給される第１の符号D12の順序を並べ替えるため、第１の符号D12を格納する入力データ保持メモリ３１と、並べ替えた第１の符号D12を保持する出力データ保持メモリ３４が必要である。そして、特に、インターリーバ１２の入力データ保持メモリ３１と出力データ保持メモリ３４としては、記憶容量の大のメモリが必要となる。
【００２８】
このように、符号化装置１では、記憶容量の大きなメモリを必要とするため、回路規模が大きくなってしまう。従って、符号化装置１では、コストが高くなったり、装置の消費電力が大きくなるといった問題があった。
【００２９】
本発明は、このような状況に鑑みてなされたものであり、符号化装置の回路規模を小さくすることができるようにするものである。
【課題を解決するための手段】
【００３０】
本発明の符号化装置は、LDPC符号のパリティの１ビットを記憶する記憶手段と、情報の各ビットのうちの、LDPC符号の検査行列にしたがったビットと、記憶手段に記憶された１ビットのパリティとを加算することにより、LDPC符号の新たな１ビットのパリティを求め、記憶手段に供給する演算手段とを備えることを特徴とする。
【００３１】
検査行列の、LDPC符号のパリティに対応するパリティ部は、階段状の構造を有するようにすることができる。
【００３２】
演算手段で用いられる検査行列は、元の検査行列の行置換または元の検査行列のパリティ部の列置換を行うことにより、パリティ部が階段状の構造を有するものにされたものであるようにすることができる。
【００３３】
情報を格納し、格納した情報の各ビットが１回以上読み出される情報格納手段をさらに備えるようにすることができる。
【００３４】
情報を格納し、格納した情報が1ビットずつ読み出される情報格納手段をさらに備えるようにすることができる。
【００３５】
演算手段により演算された演算結果を間引く間引き手段をさらに備えるようにすることができる。
【００３６】
本発明の符号化方法は、LDPC符号のパリティの１ビットを記憶手段に記憶させる記憶ステップと、情報の各ビットのうちの、LDPC符号の検査行列にしたがったビットと、記憶手段に記憶された１ビットのパリティとを加算することにより、LDPC符号の新たな１ビットのパリティを求め、記憶手段に供給する演算ステップとを含むことを特徴とする。
【００３７】
本発明のプログラムは、LDPC符号のパリティの１ビットを記憶手段に記憶させる記憶ステップと、情報の各ビットのうちの、LDPC符号の検査行列にしたがったビットと、記憶手段に記憶された１ビットのパリティとを加算することにより、LDPC符号の新たな１ビットのパリティを求め、記憶手段に供給する演算ステップとを含むことを特徴とする。
【００３８】
本発明においては、LDPC符号のパリティの１ビットが記憶され、情報の各ビットのうちの、LDPC符号の検査行列にしたがったビットと、記憶された１ビットのパリティとを加算することにより、LDPC符号の新たな１ビットのパリティが求められ、記憶される。
【発明の効果】
【００３９】
本発明によれば、所定の情報をLDPC符号化する符号化装置の回路規模を小さくすることができるので、コストを削減し、装置の消費電力を削減することができる。
【発明を実施するための最良の形態】
【００４０】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００４１】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００４２】
請求項１に記載の符号化装置は、前記LDPC符号のパリティの１ビットを記憶する記憶手段（例えば、図８のシフトレジスタ１２３）と、前記情報の各ビットのうちの、前記LDPC符号の検査行列にしたがったビットと、前記記憶手段に記憶された１ビットのパリティとを加算することにより、前記LDPC符号の新たな１ビットのパリティを求め、前記記憶手段に供給する演算手段（例えば、図８の演算器１２２）とを備えることを特徴とする。
【００４３】
請求項４に記載の符号化装置は、請求項１に記載の符号化装置であって、前記情報を格納し、格納した情報の各ビットが１回以上読み出される情報格納手段（例えば、図８の情報ビット格納メモリ１２１）をさらに備えることを特徴とする。
【００４４】
請求項５に記載の符号化装置は、請求項１に記載の符号化装置であって、前記情報を格納し、格納した情報が1ビットずつ読み出される情報格納手段（例えば、図１０の情報ビット格納メモリ１４１）をさらに備えることを特徴とする。
【００４５】
請求項６に記載の符号化装置は、請求項５に記載の符号化装置であって、前記演算手段により演算された演算結果を間引く間引き手段（例えば、図１０のパンクチャ回路１４４）をさらに備えることを特徴とする。
【００４６】
請求項７に記載の符号化方法は、所定の情報をLDPC(Low Density Parity Check)符号に符号化する符号化装置の符号化方法であって、前記LDPC符号のパリティの１ビットを記憶手段に記憶させる記憶ステップ（例えば、図９のステップＳ６）と、前記情報の各ビットのうちの、前記LDPC符号の検査行列にしたがったビットと、前記記憶手段に記憶された１ビットのパリティとを加算することにより、前記LDPC符号の新たな１ビットのパリティを求め、前記記憶手段に供給する演算ステップ（例えば、図９のステップＳ５）とを含むことを特徴とする。
【００４７】
請求項８に記載のプログラムの各ステップの具体例も、請求項７に記載の符号化方法の各ステップの発明の実施の形態における具体例と同様である。
【００４８】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００４９】
図５は、LDPC符号化に用いる検査行列Hの例を示している。
【００５０】
図５の検査行列Hは、６０ビットの情報を９０ビットのLDPC符号（符号化率2/3、符号長90）に符号化するための検査行列であり、３０（行）×９０（列）の行列である。なお、図５の検査行列では（後述する図７においても同様）、０を、"."で表現している。
【００５１】
ここで、図５の検査行列Hを用いて情報を符号化することにより得られるLDPC符号は、９０ビットの符号のうち、６０ビットの情報すべてがそのまま現れる組織符号である。即ち、LDPC符号化は、６０ビットの情報から３０ビットのパリティを生成することにより行われ、これにより、LDPC符号は、６０ビットの情報と３０ビットのパリティから構成される。
【００５２】
従って、検査行列Hは、LDPC符号の６０ビットの情報に対応する、３０（行）（１行目から３０行目まで）×６０（列）（１列目から６０列目まで）の行列である情報部と、LDPC符号の３０ビットのパリティに対応する３０（行）（１行目から３０行目まで）×３０（列）（６１列目から９０列目まで）の行列であるパリティ部とに分けることができる。
【００５３】
LDPC符号の復号にあたっては、情報部は、LDPC符号の情報（情報ビット）と乗算され、パリティ部は、LDPC符号のパリティ（パリティビット）と乗算される。
【００５４】
図５の検査行列Hでは、LDPC符号の情報に対応する情報部の各行は、７個の“１”と、５３個の“０”から構成される。パリティ部は、下三角状の構造を有する行列（下三角行列）となっている。
【００５５】
即ち、図５の検査行列Hのパリティ部は、行列の対角線の右上が全て“０”とされた行列となっており、下三角状の構造を有している。
【００５６】
ところで、上述したように、LDPC符号への符号化を行う符号化装置は、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出し、その生成行列Gに対して情報語を乗算して、符号語c（＝ｕＧ）を生成することにより、LDPC符号化を行う。従って、符号化装置は、検査行列Hとの間に、式HcT=0（上付のＴは転置を表す）が成立する符号語cを求めることにより、情報のLDPC符号化を行うことができる。
【００５７】
従って、符号化装置では、検査行列Hの各行の“１”のある位置に対応する符号語cの値のGF(2)上の和が０になる符号語cを生成すればよい。図５に示したように、パリティ部が下三角状の構造を有する検査行列Hを用いたLDPC符号化は、次のようにして行うことができる。
【００５８】
即ち、図５の検査行列Hの第１行目は、情報部である１から６０列目までに７個の“１”があり、パリティ部の１列目である６１列目に“１”がある。従って、符号化装置は、第１行目の情報部の“１”のある位置に対応する符号語cの値、即ち、符号語cの６０ビットからなる情報の値（情報ビット）のうち、情報部の“１”のある位置に対応するすべての情報ビット（７個の情報ビット）のGF(2)上の和（排他的論理和）を演算し、その値を符号語cの６１ビット目のパリティとすることにより、第１行目の“１”のある位置に対応する符号語cの値のGF(2)上の和が０になるようにすることができる。
【００５９】
例えば、第1行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が、“１”であった場合、符号化装置は、符号語cの６１ビット目のパリティを“１”にする。この場合、第1行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が“１”であり、符号語cの６１ビット目のパリティが“１”であるので、検査行列の第1行目の“１”のある位置に対応する符号語cの値のGF(2)上の和は０になる。
【００６０】
検査行列Hの第２行目は、情報部である１から６０列目までに７個の“１”があり、パリティ部の２列目である６２列目に“１”がある。従って、符号化装置は、第２行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和を計算し、その値を符号語cの６２ビット目のパリティとすることにより、第２行目の“１”のある位置に対応する符号語cの値のGF(2)上の和が０になるようにすることができる。
【００６１】
例えば、第２行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が、“０”であった場合、符号化装置は、符号語cの６２ビット目のパリティを“０”にする。この場合、第２行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が“０”であり、６２ビット目のパリティが“０”であるので、検査行列の第２行目の”1”にある位置に対応する符号語cの値のGF(2)上の和は０になる。
【００６２】
検査行列Hの第３行目は、情報部である１から６０列目までに７個の“１”があり、パリティ部の１列目と３列目である６１列目と６３列目に“１”がある。従って、符号化装置は、第３行目の情報部の“１”のある位置に対応する７個の情報ビット、既に求められたパリティ部の“１”のある位置に対応するパリティビットの値、即ち、第１行目の計算で既に求められた符号語cの６１ビット目のパリティの値のGF(2)上の和を計算し、その値を符号語cの６３ビット目のパリティとすることにより、第３行目の“１”のある位置に対応する符号語cの値のGF(2)上の和が０になるようにすることができる。
【００６３】
例えば、第３行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が、“１”であり、符号語cの６１ビット目のパリティの値が“１”であった場合、符号化装置は、符号語cの６３ビット目のパリティを“０”にする。この場合、第３行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が“１”であり、符号語cの６１ビット目のパリティが“１”、６３ビット目のパリティが“０”であるので、検査行列の第３行目の”１”にある位置に対応する符号語cの値のGF(2)上の和は０になる。
【００６４】
符号化装置は、検査行列Hの第４行目から第３０行目までにおいても、第２行目や第３行目と同様に、検査行列Hの情報部の行毎の“１”のある位置に対応する７個の情報ビットと、既に計算したパリティの任意のビット、即ち、行毎の既に求められたパリティ部の“１”のある位置に対応するパリティビットの排他的論理和を演算することにより、パリティ（ビット）を１ビットずつ求め、最終的に、３０ビットのパリティを求める。そして、符号化装置は、６０ビットの情報ビットと、３０ビットのパリティビットとを合わせて、９０ビットの符号語cを生成することにより、生成行列Gを用いずに、検査行列Hを用いて、情報をLDPC符号化することができる。
【００６５】
図６は、図５の検査行列Hを用いて、情報をLDPC符号化する符号化装置の構成例を示している。なお、図示はしないが（後述する図８と図１０においても同様）、符号化装置の後段には、符号化結果である符号語を送信する順番に応じて並び替えたり、送信シンボルにマッピングする装置が設けられている。
【００６６】
符号化装置１００は、情報ビット格納メモリ１０１、パリティビット格納メモリ１０２、演算器１０３、および制御信号生成部１０４から構成されている。
【００６７】
符号化装置１００には、LDPC符号化の対象となる情報（ビット）である６０ビット単位の入力データD101が入力され、その入力データD101は、情報ビット格納メモリ１０１に供給されて格納されるとともに、その入力データD101をLDPC符号化した符号語の一部として出力される。
【００６８】
情報ビット格納メモリ１０１には、制御信号生成部１０４から制御信号D105が供給され、情報ビット格納メモリ１０１は、制御信号D105に基づいて、格納している６０ビットの入力データD101から、図７の検査行列Hの情報部の１行目から順に、行毎の“１”のある位置に対応する入力データ（ビット）を読み出し、７個（情報部の各行の“１”の数）の１ビットの情報ビットD102-1乃至D102-7として、演算器１０３に供給する。
【００６９】
パリティビット格納メモリ１０２には、演算器１０３から１ビットのパリティビットD104が供給され、パリティビット格納メモリ１０２は、そのパリティビットD104を格納する。また、パリティビット格納メモリ１０２には、制御信号生成部１０４から制御信号D106が供給され、パリティビット格納メモリ１０２は、制御信号D106に基づいて、前回の演算までに演算器１０３から供給され、格納された行毎のパリティ部の“１”のある位置に対応するパリティビットD103を読み出し、そのパリティビットD103を演算器１０３に供給する。
【００７０】
演算器１０３には、情報ビット格納メモリ１０１から７個（７ビット）の情報ビットD102-1乃至D102-7が供給されるとともに、パリティビット格納メモリ１０２から行毎のパリティ部の“１”のある位置に対応するパリティビットD103が供給される。演算器１０３は、７ビットの情報ビットD102-1乃至D102-7と、前回の演算までに求められた行毎のパリティ部の“１”のある位置に対応するパリティビットD103のGF(2)上の和（排他的論理和）を演算し、その演算結果を新たな１ビットのパリティビットD104として、パリティビット格納メモリ１０２に供給するとともに、入力データD101をLDPC符号化した符号語の一部として出力する。
【００７１】
制御信号生成部１０４は、検査行列Hの情報部の１行目から順に、行毎の“１”のある位置に対応する入力データD101を読み出すように、情報ビット格納メモリ１０１を制御する制御信号D105を生成し、情報ビット格納メモリ１０１に供給する。また、制御信号生成部１０４は、前回の演算までに演算器１０３から供給され、格納された行毎のパリティ部の“１”のある位置に対応するパリティビットを出力するように、パリティビット格納メモリ１０２を制御する制御信号D106を生成し、パリティビット格納メモリ１０２に供給する。
【００７２】
図６の符号化装置１００では、演算器１０３が３０回演算を繰り返すことにより、３０ビットのパリティビットD104が求められる。そして、符号化装置１００は、６０ビットの入力データD101と、演算器１０３により求められた３０ビットのパリティビットD104とを合わせて、９０ビットの符号語cを生成することにより、６０ビットの入力データD101をLDPC符号化する。
【００７３】
図７は、LDPC符号化に用いる検査行列Hの他の例を示している。
【００７４】
図７の検査行列Hは、図５における場合と同様に、６０ビットの情報を９０ビットのLDPC符号（符号化率2/3、符号長90）に符号化するための検査行列であり、３０（行）×９０（列）の行列である。
【００７５】
ここで、図７の検査行列Hを用いて情報を符号化することにより得られるLDPC符号は、９０ビットの符号のうち、６０ビットの情報すべてがそのまま現れる組織符号である。即ち、LDPC符号化は、６０ビットの情報から３０ビットのパリティを生成することにより行われ、これにより、LDPC符号は、６０ビットの情報と３０ビットのパリティから構成される。
【００７６】
従って、図７の検査行列Hは、図５における場合と同様に、LDPC符号の６０ビットの情報に対応する、３０（行）（１行目から３０行目まで）×６０（列）（１列目から６０列目まで）の行列である情報部と、LDPC符号の３０ビットのパリティに対応する３０（行）（１行目から３０行目まで）×３０（列）（６１列目から９０列目まで）の行列であるパリティ部とに分けることができる。
【００７７】
LDPC符号の復号にあたっては、情報部は、LDPC符号の情報と乗算され、パリティ部は、LDPC符号のパリティと乗算される。
【００７８】
図７の検査行列Hでは、LDPC符号の情報に対応する情報部の各行は、７個の“１”と、５３個の“０”から構成される。パリティ部は、階段状の構造を有する行列となっている。
【００７９】
即ち、図７の検査行列Hのパリティ部は、単位行列の、第１行を除く各行の“１”になっているコンポーネントの１列だけ前の列も“１”とされた行列となっており、右下がり（左上がり）の階段状の構造を有している。
【００８０】
ところで、上述したように、LDPC符号への符号化を行う符号化装置は、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出し、その生成行列Gに対して情報語を乗算して、符号語c（＝ｕＧ）を生成することにより、LDPC符号化を行う。従って、符号化装置は、検査行列Hとの間に、式HcT=0（上付のＴは転置を表す）が成立する符号語cを求めることにより、情報のLDPC符号化を行うことができる。
【００８１】
従って、符号化装置では、検査行列Hの各行の“１”のある位置に対応する符号語cの値のGF(2)上の和が０になる符号語cを生成すればよい。図７に示したように、パリティ部が階段状の構造を有する検査行列Hを用いたLDPC符号化は、次のようにして行うことができる。
【００８２】
即ち、図７の検査行列Hの第１行目は、情報部である１から６０列目までに７個の“１”があり、パリティ部の１列目である６１列目に“１”がある。従って、符号化装置は、第１行目の情報部の“１”のある位置に対応する符号語cの値、即ち、符号語cの６０ビットからなる情報の値（情報ビット）のうち、情報部の“１”のある位置に対応するすべての情報ビット（７個の情報ビット）のGF(2)上の和（排他的論理和）を演算し、その値を符号語cの６１ビット目のパリティとすることにより、第1行目の“１”のある位置に対応する符号語cの値のGF(2)上の和が０になるようにすることができる。
【００８３】
例えば、第1行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が、“１”であった場合、符号化装置は、符号語cの６１ビット目のパリティを“１”にする。この場合、第1行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が“１”であり、符号語cの６１ビット目のパリティが“１”であるので、検査行列の第1行目の“１”のある位置に対応する符号語cの値のGF(2)上の和は０になる。
【００８４】
検査行列Hの第２行目は、情報部である１から６０列目までに７個の“１”があり、パリティ部の１列目と２列目である６１列目と６２列目に“１”がある。従って、符号化装置は、第２行目の情報部の“１”のある位置に対応する７個の情報ビットと、第１行目の計算で既に求められた符号語cの６１ビット目のパリティの値のGF(2)上の和を計算し、その値を符号語cの６２ビット目のパリティとすることにより、第２行目の“１”のある位置に対応する符号語cの値のGF(2)上の和が０になるようにすることができる。
【００８５】
例えば、第２行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が、“０”であり、符号語cの６１ビット目のパリティの値が“１”であった場合、符号化装置は、符号語cの６２ビット目のパリティを“１”にする。この場合、第２行目の情報部の“１”のある位置に対応する７個の情報ビットのGF(2)上の和が“０”であり、符号語cの６１ビット目のパリティが“１”、６２ビット目のパリティが“１”であるので、検査行列の第２行目の”1”にある位置に対応する符号語cの値のGF(2)上の和は０になる。
【００８６】
符号化装置は、検査行列Hの第３行目から第３０行目までにおいても、第２行目と同様に、検査行列Hの情報部の行毎の“１”のある位置に対応する７個の情報ビットと、直前に求められたパリティビットの排他的論理和を演算することにより、パリティ（ビット）を１ビットずつ求め、最終的に、３０ビットのパリティを求める。そして、符号化装置は、６０ビットの情報ビットと、３０ビットのパリティビットとを合わせて、９０ビットの符号語cを生成することにより、生成行列Gを用いずに、検査行列Hを用いて、情報をLDPC符号化することができる。
【００８７】
なお、図７の検査行列Hは、図５の検査行列Hと同様に、パリティ部が行列の対角線の右上が全て“０”とされた下三角行列となっている。従って、前述の図６の符号化装置１００を用いて、図７の検査行列Hにしたがって、情報をLDPC符号化することができる。
【００８８】
しかしながら、上述したように、図７の検査行列Hにしたがって、情報をLDPC符号化する場合、符号化装置では、図５の検査行列Hにしたがって、情報をLDPC符号化する場合とは異なり、既に計算したパリティの任意のビット、即ち、前回までに求められた行毎のパリティ部の“１”のある位置に対応するパリティビットすべてを用いて、排他的論理和を演算する必要はなく、直前に求められたパリティビットのみを用いて、排他的論理和を演算することにより、新たなパリティビットを求めることができる。従って、図７の検査行列Hにしたがって、情報をLDPC符号化する場合、直前に求められたパリティビットだけを格納すればよく、いままでに求められた全パリティを格納する必要はない。
【００８９】
そこで、図８は、本発明を適用した符号化装置の一実施の形態の構成例を示すブロック図である。
【００９０】
図８の符号化装置１２０は、パリティビット格納メモリ１０２の代わりに、直前に演算されたパリティビットのみを格納するシフトレジスタ１２３を用い、図７の検査行列Hにしたがって、入力データ（情報）をLDPC符号化する。
【００９１】
即ち、符号化装置１２０は、情報ビット格納メモリ１２１、演算器１２２、シフトレジスタ１２３、および制御信号生成部１２４から構成される。
【００９２】
符号化装置１２０には、LDPC符号化の対象となる情報（ビット）である６０ビット単位の入力データD121が入力され、その入力データD121は、情報ビット格納メモリ１２１に供給されて格納されるとともに、その入力―タD121をLDPC符号化した符号語の一部として出力される。
【００９３】
情報ビット格納メモリ１２１には、制御信号生成部１２４から制御信号D125が供給され、情報ビット格納メモリ１２１は、制御信号D125に基づいて、格納している入力データD121から、検査行列Hの情報部の1行目から順に、行毎の“１”のある位置に対応する入力データを読み出し、７個（情報部の各行の“１”の数）の1ビットの情報ビットD122-1乃至D122-7として、演算器１２２に供給する。
【００９４】
演算器１２２には、情報ビット格納メモリ１２１から７ビットの情報ビットD122-1乃至D122-7が供給されるとともに、シフトレジスタ１２３から１ビットのパリティビットD123が供給される。演算器１２２は、７ビットの情報ビットD122-1乃至D122-7それぞれと１ビットのパリティビットD123との加算、即ち、ここでは排他的論理和を演算する。そして、演算器１２２は、その演算結果を新たな１ビットのパリティ（ビット）D124として、シフトレジスタ１２３に供給するとともに、入力データD121をLDPC符号化した符号語の一部として出力する。
【００９５】
シフトレジスタ１２３には、演算器１２２から直前に演算された1ビットのパリティビットD124が供給され、シフトレジスタ１２３は、そのパリティビットD124を格納（保持）する。また、シフトレジスタ１２３は、既に格納しているパリティビットD123を演算器１２２に供給する。
【００９６】
制御信号生成部１２４は、検査行列Hの情報部の１行目から順に、行毎の“１”のある位置に対応する入力データD121を読み出すように、情報ビット格納メモリ１２１を制御する制御信号D125を生成し、情報ビット格納メモリ１２１に供給する。
【００９７】
図８の符号化装置１２０では、演算器１２２が３０回演算を繰り返すことにより、３０ビットのパリティビットD124が求められる。そして、符号化装置１２０は、６０ビットの入力データD121と、演算器１２２により求められた３０ビットのパリティビットD124とを合わせて、９０ビットの符号語cを生成することにより、６０ビットの入力データD121を９０ビットの符号語にLDPC符号化する。
【００９８】
上述したように、符号化装置１２０では、シフトレジスタ１２３は、演算器１２２で直前に演算された演算結果である１ビットのパリティビットのみを格納するので、シフトレジスタ１２３のメモリ容量は、すべてのパリティビット（図６では、３０ビット）を格納するパリティビット格納メモリ１０２に比べて小さくて済み、これにより、図６の符号化装置１００に比べて回路規模を小さくすることができる。特に、符号長が長く、パリティビット数が多い符号に符号化する場合、すべてのパリティビットを格納するパリティビット格納メモリ１０２のメモリ容量は大きくなるので、回路規模を小さくすることができるという効果は大きくなる。
【００９９】
また、演算器１２２とシフトレジスタ１２３は、図３に示すアキュームレータ１３の演算器５１とシフトレジスタ５２と同様の構成となっている。従って、符号化装置１２０は、図１の符号化装置１の繰り返し符号化部１１とインターリーバ１２を、制御信号生成部１２４と情報ビット格納メモリ１２１に代えたもので構成することができる。このように、符号化装置１２０では、符号化装置１の繰り返し符号化部１１とインターリーバ１２を代えることにより、インターリーバ１２の入力データ保持メモリ３１と出力データ保持メモリ３４（図２）を設ける必要がなくなり、符号化装置１に比べて、データを記憶する記憶容量を大きく削減することができる。これにより、符号化装置１２０では、符号化装置１に比べて回路規模を小さくすることができる。
【０１００】
図９は、図８の符号化装置１２０の符号化処理を説明するフローチャートである。この符号化処理は、例えば、LDPC符号化の対象となる情報（ビット）である６０ビットの入力データD121が符号化装置１２０に入力されたとき、開始する。
【０１０１】
ステップＳ１において、情報ビット格納メモリ１２１は、入力された６０ビットの入力データD121を格納し、ステップＳ２に進む。
【０１０２】
ステップＳ２において、制御信号生成部１２４は、図７の検査行列Hに基づいて、検査行列Hの情報部の1行目を処理の対象とする行（対象行）とし、対象行の“１”のある位置に対応する入力データD121を読み出すように制御する制御信号D125を生成し、情報ビット格納メモリ１２１に供給する。
【０１０３】
ステップＳ２の処理後は、ステップ３に進み、情報ビット格納メモリ１２１は、制御信号生成部１２４から供給される制御信号D125に基づいて、ステップＳ１で格納した入力データD121から、検査行列Hの情報部の対象行の“１”のある位置に対応する入力データD121を読み出し、即ち、７個（情報部の対象行の“１”の数）の１ビットの情報ビットD122-1乃至D122-7を読み出し、演算器１２２に供給する。そして、情報ビット格納メモリ１２１は、ステップＳ３からステップＳ４に進む。
【０１０４】
ステップＳ４において、シフトレジスタ１２３は、後述するステップＳ６で格納（記憶）した１ビットのパリティビットD123を演算器１２２に供給し、ステップＳ５に進む。なお、符号化処理の開始時には、シフトレジスタ１２３に、初期値として“０”が格納される。従って、最初のステップＳ４の処理では、シフトレジスタ１２３は、“０”を演算器１２２に供給する。
【０１０５】
ステップＳ５において、演算器１２２は、入力データD121の各ビットのうちの、図７の検査行列Hにしたがったビットと、レジスタ１２３に記憶された１ビットのパリティとを加算することにより、新たな１ビットのパリティを求める。即ち、演算器１２２は、情報ビット格納メモリ１２１から供給される７個の1ビットの情報ビットD122-1乃至D122-7と、シフトレジスタ１２３から供給される1ビットのパリティビットD123とを用いて、７個の1ビットの情報ビットD122-1乃至D122-7と、1ビットのパリティビットD123の排他的論理和を演算し、新たな1ビットのパリティビットD124、即ち、対象行を第ｎ行と表すこととすると、第ｎビット目のパリティビットD124を求める。そして、演算器１２２は、新たな1ビットのパリティビットD124をシフトレジスタ１２３に供給する。
【０１０６】
ステップＳ５の処理後は、ステップＳ６に進み、シフトレジスタ１２３は、演算器１２２から供給される新たな1ビットのパリティビットD124を、それまで記憶していたパリティビットに上書きする形で格納（保持）し、ステップＳ７に進む。ステップＳ７において、演算器１２２は、演算結果である新たな1ビットのパリティビットD124を出力し、ステップＳ８に進む。
【０１０７】
ステップＳ８において、制御信号生成部１２４は、すべてのパリティビットを出力したかどうかを判定する。即ち、制御信号生成部１２４は、検査行列Hのすべての行を対象行として、制御信号D125を生成したかどうかを判定する。
【０１０８】
ステップＳ８において、制御信号生成部１２４は、すべてのパリティビットを出力していないと判定した場合、ステップＳ２に戻り、いま、対象行となっている行の次の行を新たな対象行として、上述した処理を繰り返す。従って、情報ビット格納メモリ１２１は、対象行毎に、検査行列Hの情報部の“１”のある位置に対応する入力データD121を１回以上読み出し、７個（情報部の対象行の“１”の数）の１ビットの情報ビットD122-1乃至D122-7として、演算器１２２に供給する。
【０１０９】
符号化装置１２０では、検査行列Hの行数（図７の検査行列の場合、３０）回、上述した処理が繰り返され、合計３０ビットのパリティビットD124が出力される。
【０１１０】
一方、ステップＳ８において、制御信号生成部１２４は、すべてのパリティビットを出力したと判定した場合、処理を終了する。このとき、符号化装置１２０では、６０ビットの入力データD121と、ステップＳ７で順に出力された合計３０ビットのパリティビットD124とを合わせた９０ビットの符号語cが、符号化結果として出力される。
【０１１１】
なお、図９の符号化処理は、次に符号化すべき６０ビットの入力データD121が符号化装置に供給されるごとに繰り返される。
【０１１２】
図１０は、本発明を適用した符号化装置の他の一実施の形態の構成例を示している。
【０１１３】
図１０の符号化装置１４０は、図７の検査行列Hを用いて、入力データ（情報）をLDPC符号化する。
【０１１４】
図８の符号化装置１２０では、演算器１２２が、７ビットの入力データと１ビットのパリティビットとの排他的論理和を一度の演算によって求めるようになっているが、図１０の符号化装置１４０では、７ビットの入力データと１ビットのパリティビットとの排他的論理和が、２つの１ビットどうしの排他的論理和を順次演算することにより求められる。従って、図１０の符号化装置１４０では、２つの１ビットどうしの排他的論理和の７回目の演算結果がパリティビットとなる。
【０１１５】
即ち、検査行列Hの情報部の１行目の“１”のある位置に対応する７個の１ビットの入力データの１ビット目と２ビット目の排他的論理和が演算され、その演算結果と、３ビット目の排他的論理和が演算される。さらに、その演算結果と、４ビット目の排他的論理和が演算され、以下、同様にして、７ビットの入力データの排他的論理和が演算されることにより、１ビット目のパリティビットが求められる。次に、１ビット目のパリティビットと、検査行列Hの情報部の２行目の“１”のある位置に対応する７個の１ビットの入力データの１ビット目の排他的論理和が演算され、その演算結果と２ビット目の排他的論理和が演算される。さらに、その演算結果と３ビット目の排他的論理和が演算され、以下、同様にして、１ビット目のパリティビットと、検査行列Hの情報部の２行目の“１”のある位置に対応する７ビットの入力データとの排他的論理和が演算されることにより、２ビット目のパリティビットが求められる。他のパリティビットも、同様にして求められる。
【０１１６】
図１０において、符号化装置１４０は、情報ビット格納メモリ１４１、演算器１４２、シフトレジスタ１４３、パンクチャ回路１４４、および制御信号生成部１４５から構成されている。
【０１１７】
符号化装置１４０には、LDPC符号化の対象となる情報（ビット）である６０ビット単位の入力データD141が入力され、その入力データD141は、情報ビット格納メモリ１４１に供給されて格納されるるとともに、その入力データD141をLDPC符号化した符号語の一部として出力される。
【０１１８】
情報ビット格納メモリ１４１には、制御信号生成部１４５から制御信号D146が供給され、情報ビット格納メモリ１４１は、制御信号D146に基づいて、格納している６０ビットの入力データD141から、図７の検査行列Hの情報部の１行目から順に、行毎の“１”のある位置に対応する入力データ（ビット）を1ビットずつ読み出し、情報ビットD142として演算器１４２に供給する。情報ビット格納メモリ１４１は、例えば、RAM（Random Access Memory）から構成される。
【０１１９】
演算器１４２には、情報ビット格納メモリ１４１から1ビットの情報ビットD142が供給されるとともに、シフトレジスタ１４３から1ビットの値D144が供給される。演算器１４２は、１ビットの情報ビットD142と1ビットの値D144を用いて、１ビットの情報ビットD142と１ビットの値D144との加算、即ち、ここでは排他的論理和を演算する。そして、演算器１４２は、その演算結果を、新たな１ビットの演算結果D143として、シフトレジスタ１４３とパンクチャ回路１４４に供給する。
【０１２０】
シフトレジスタ１４３には、演算器１４２から直前に演算された1ビットの演算結果D143が供給され、シフトレジスタ１４３は、その演算結果D143を格納（保持）する。また、シフトレジスタ１４３は、既に格納している演算結果D143を演算器１４２に供給する。
【０１２１】
パンクチャ回路１４４には、演算器１４２から演算結果D143が供給される。パンクチャ回路１４４は、演算器１４２から供給される７ビットごとの演算結果D143のうち、１から６ビット目までの演算結果D143を間引き、７ビット目の演算結果D143のみをパリティビットD145として出力する。
【０１２２】
制御信号生成部１４５は、検査行列Hの情報部の１行目から順に、行毎の“１”のある位置に対応する入力データD141を１ビットずつ読み出すように、情報ビット格納メモリ１４１を制御する制御信号D146を生成し、情報ビット格納メモリ１４１に供給する。
【０１２３】
図１０の符号化装置１４０では、演算器１４２が３０×７回の２つのビットどうしの排他的論理和の演算を繰り返すことにより、３０ビットのパリティビットD145が求められる。そして、符号化装置１４０は、６０ビットの入力データD141と、３０ビットのパリティビットD145とを合わせた９０ビットの符号語cを生成することにより、６０ビットの入力データD141を９０ビットの符号語にLDPC符号化を行う。
【０１２４】
符号化装置１４０では、シフトレジスタ１４３は、演算器１４２で直前に演算された１ビットの演算結果のみを格納するので、シフトレジスタ１４３のメモリ容量は、すべてのパリティビット（図６では、３０ビット）を格納するパリティビット格納メモリ１０２に比べて小さくて済み、これにより、図６の符号化装置１００に比べて回路規模を小さくすることができる。特に、符号長が長く、パリティビット数が多い符号に符号化する場合、すべてのパリティビットを格納するパリティビット格納メモリ１０２のメモリ容量は大きくなるので、回路規模を小さくすることができるという効果は大きくなる。
【０１２５】
また、演算器１４２とシフトレジスタ１４３は、図３に示すアキュームレータ１３の演算器５１とシフトレジスタ５２と同様の構成となっている。従って、符号化装置１２０は、図１の符号化装置１の繰り返し符号化部１１とインターリーバ１２を、制御信号生成部１４５と情報ビット格納メモリ１４１に代え、パンクチャ回路１４４を加えたもので構成することができる。このように、符号化装置１４０では、符号化装置１の繰り返し符号化部１１とインターリーバ１２を代えることにより、インターリーバ１２の入力データ保持メモリ３１と出力データ保持メモリ３４（図２）を設ける必要がなくなり、符号化装置１に比べて、データを記憶する記憶容量を大きく削減することができる。これにより、符号化装置１４０では、符号化装置１に比べて回路規模を小さくすることができる。
【０１２６】
図１１は、図１０の符号化装置１４０の符号化処理を説明するフローチャートである。この符号化処理は、例えば、LDPC符号化の対象となる情報である６０ビットの入力データD141（情報ビット）が符号化装置１４０に入力されたとき、開始する。
【０１２７】
ステップＳ２１において、情報ビット格納メモリ１４１は、入力された６０ビットの入力データD141を格納し、ステップＳ２２に進む。
【０１２８】
ステップＳ２２において、パンクチャ回路１４４は、カウンタの値Ｋを０に初期化し、ステップＳ２３に進む。ステップＳ２３において、制御信号生成部１４５は、図７の検査行列Hに基づいて、検査行列Hの情報部の1行目を処理の対象とする行（対象行）とし、対象行の“１”のある位置に対応する入力データD141を1ビットずつ出力するように制御する制御信号D146を生成し、情報ビット格納メモリ１４１に供給する。
【０１２９】
ステップＳ２３の処理後は、ステップＳ２４に進み、情報ビット格納メモリ１４１は、制御信号生成部１４５から供給される制御信号D146に基づいて、ステップＳ２１で格納した入力データD141から、検査行列Hの情報部の対象行の“１”のある位置に対応する７ビットの入力データD141のうちの、まだ読み出していない1ビットを読み出し、１ビットの情報ビットD142として、演算器１４２に供給して、ステップＳ２５に進む。
【０１３０】
ステップＳ２５において、シフトレジスタ１４３は、後述するステップＳ２７で格納(記憶)した１ビットの演算結果D143を、値D144として演算器１４２に供給し、ステップＳ２６に進む。なお、符号化処理の開始時には、シフトレジスタ１４３に、初期値として“０”が格納される。従って、最初のステップＳ２５の処理では、シフトレジスタ１４３は、“０”を演算器１４２に供給する。
【０１３１】
ステップＳ２６において、演算器１４２は、情報ビット格納メモリ１４１から供給される１ビットの情報ビットD142と、シフトレジスタ１４３から供給される１ビットの値D144とを用いて、情報ビットD142と、値D144との排他的論理和を演算し、その演算結果D143をシフトレジスタ１４３とパンクチャ回路１４４に供給する。
【０１３２】
ステップＳ２６の処理後は、ステップＳ２７に進み、シフトレジスタ１４３は、演算器１４２から供給される１ビットの演算結果D143を、それまで記憶していたパリティビットに上書きする形で格納（保持）し、ステップＳ２８に進む。ステップＳ２８において、パンクチャ回路１４４は、演算器１４２から供給される演算結果D143を取得し、ステップＳ２９に進む。
【０１３３】
ステップＳ２９において、パンクチャ回路１４４は、カウンタの値Ｋを1だけインクリメントし、ステップＳ３０に進む。ステップＳ３０において、パンクチャ回路１４４は、カウンタの値Ｋが、検査行列Hの情報部の各行の“１”の数Ｎ（図７の検査行列の場合、７）以上であるかどうかを判定する。
【０１３４】
ステップＳ３０において、パンクチャ回路１４４は、カウンタの値ＫがＮ以上ではないと判定した場合、ステップＳ２３に戻り、上述した処理を繰り返す。即ち、この場合、パンクチャ回路１４４は、演算器１４２の演算結果を出力しない。
【０１３５】
一方、ステップＳ３０において、パンクチャ回路１４４は、カウンタの値ＫがＮ以上であると判定した場合、ステップＳ３１に進み、ステップＳ２８で取得した演算結果D143をパリティビットD145として出力する。即ち、パンクチャ回路１４４は、ステップＳ２３乃至ステップＳ３０のループ処理が行われることにより、演算器１４２から順次供給される７ビットの演算結果D143のうち、１から６ビット目までを間引いて、７ビット目のみを、パリティビットD145、即ち、対象行を第ｎ行と表すこととすると、第ｎビット目のパリティビットD145として出力する。
【０１３６】
ステップＳ３１の処理後は、ステップＳ３２に進み、制御信号生成部１４５は、すべてのパリティビットを出力したかどうかを判定する。即ち、制御信号生成部１４５は、検査行列Hのすべての行を対象行として、制御信号D125を生成したかどうかを判定する。
【０１３７】
ステップＳ３２において、制御信号生成部１４５は、すべてのパリティビットを出力していないと判定した場合、ステップＳ２２に戻り、いま、対象行となっている行の次の行を新たな対象行として、上述した処理を繰り返す。従って、情報ビット格納メモリ１４１は、対象行毎に、検査行列Hの情報部の“１”のある位置に対応する入力データD141を１ビットずつ1回以上読み出し、１ビットの情報ビットD142として、演算器１４２に供給する。
【０１３８】
符号化装置１４０では、検査行列Hの行数（図７の検査行列の場合、３０回）、上述した処理が繰り返され、合計３０ビットのパリティビットD145が出力される。
【０１３９】
一方、ステップＳ３２において、制御信号生成部１２４は、すべてのパリティビットを出力したと判定した場合、処理を終了する。このとき、符号化装置１４０では、６０ビットの入力データD141と、ステップＳ３１で順に出力された３０ビットのパリティビットD145を合わせた９０ビットの符号語cが、符号化結果として出力される。
【０１４０】
なお、上述した処理では、符号化装置は、図７の検査行列Hを用いて、６０ビット単位の情報を、符号化率が2/3で、符号長が90のLDPC符号に符号化したが、検査行列Hのパリティ部が階段状の行列から構成される検査行列であれば、どのような符号長、符号化率のLDPC符号にも符号化することができる。
【０１４１】
また、図１２に示す検査行列Hは、検査行列Hの行置換および検査行列Hのパリティ部の列置換を行うことにより、階段状のパリティ部を有する図７の検査行列Hに変換することができる。従って、図１２に示す検査行列を用いて、情報をLDPC符号化する場合には、図１２の検査行列（元の検査行列）を変換した図７の検査行列を用いて符号化を行い、その結果得られる符号化系列を並び替えるだけで、図８や図１０の符号化装置で符号化を行うことができる。
【０１４２】
即ち、図１２は、図７の検査行列Hに、式（１）の行置換と、式（２）の列置換を施して得られる検査行列Hを示している。
【０１４３】
行置換：６ｘ＋ｙ＋１行目→５ｙ＋ｘ＋１行目
・・・（１）
【０１４４】
列置換：６ｓ＋ｔ＋６１列目→５ｔ＋ｓ＋６１列目
・・・（２）
【０１４５】
但し、式（１）および（２）において、ｘ，ｙ，ｓ，ｔは、それぞれ０≦ｘ＜５，０≦ｙ＜６，０≦ｓ＜５，０≦ｙ＜６の範囲の整数である。
【０１４６】
式（１）の行置換によれば、６で割って余りが１になる１，７，１３，１９，２５行目を、それぞれ１，２，３，４，５行目に、６で割って余りが２になる２，８，１４，２０．２６行目を、それぞれ、６，７，８，９，１０行目に、という具合に置換が行われる。
【０１４７】
また、式（２）の列置換によれば、６１列目以降（パリティ部）に対して、６で割って余りが１になる６１，６７，７３，７９，８５列目を、それぞれ、６１，６２，６３，６４，６５列目に、６で割って余りが２になる６２，６８，７４，８０，８６列目を、それぞれ、６６，６７，６８，６９，７０列目に、という具合に置換が行われる。
【０１４８】
図７の検査行列Hは、図１２の検査行列Hに対して、式（１）の行置換の逆置換または式（２）の列置換の逆置換を行うことによって得ることができる。
【０１４９】
図７の検査行列に対して、図１２の検査行列で表された符号の符号語の系列に、式（２）の列置換の逆置換を行ったものを乗じると、０ベクトルが出力されることは自明である。即ち、図１２の検査行列を行列Hで、図７の検査行列を行列H'で、図１２の検査行列で表された符号の符号語の系列を行ベクトルcで、その行ベクトルcに式（２）の列置換の逆置換を施して得られる行ベクトルc'で、それぞれ表すこととすると、検査行列の性質からHcT（上付きのＴは転置を表す）は、０ベクトルとなるから、H'c'Tも、当然、０ベクトルとなる。
【０１５０】
そして、以上のことから、図７の検査行列は、図１２の検査行列にしたがった符号語の系列に、式（２）の列置換の逆置換を行ったものを符号語とする符号c'の検査行列になっている。
【０１５１】
従って、図１２に示す検査行列を用いて、情報をLDPC符号化する場合には、図１２の検査行列を変換した図７の検査行列を用いて符号化を行い、その結果得られる符号化系列に式（２）の列置換の逆置換を行うだけで、図８や図１０の符号化装置で符号化を行うことができる。
【０１５２】
なお、IRA符号等、LDPC符号と明示されていない符号であっても、検査行列Hのパリティ部が階段状の行列から構成される場合、図８や図１０の符号化装置で符号化することができる。
【０１５３】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０１５４】
そこで、図１３は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０１５５】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク４０５やROM４０３に予め記録しておくことができる。
【０１５６】
あるいはまた、プログラムは、フレキシブルディスク、CD-ROM(Compact Disc Read Only Memory)，MO(Magneto Optical)ディスク，DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体４１１に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体４１１は、いわゆるパッケージソフトウエアとして提供することができる。
【０１５７】
なお、プログラムは、上述したようなリムーバブル記録媒体４１１からコンピュータにインストールする他、ダウンロードサイトから、ディジタル衛星放送用の人工衛星を介して、コンピュータに無線で転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを、通信部４０８で受信し、内蔵するハードディスク４０５にインストールすることができる。
【０１５８】
コンピュータは、CPU(Central Processing Unit)４０２を内蔵している。CPU４０２には、バス４０１を介して、入出力インタフェース４１０が接続されており、CPU４０２は、入出力インタフェース４１０を介して、ユーザによって、キーボードや、マウス、マイク等で構成される入力部４０７が操作等されることにより指令が入力されると、それにしたがって、ROM(Read Only Memory)４０３に格納されているプログラムを実行する。あるいは、また、CPU４０２は、ハードディスク４０５に格納されているプログラム、衛星若しくはネットワークから転送され、通信部４０８で受信されてハードディスク４０５にインストールされたプログラム、またはドライブ４０９に装着されたリムーバブル記録媒体４１１から読み出されてハードディスク４０５にインストールされたプログラムを、RAM(Random Access Memory)４０４にロードして実行する。これにより、CPU４０２は、上述したフローチャートにしたがった処理、あるいは上述したブロック図の構成により行われる処理を行う。そして、CPU４０２は、その処理結果を、必要に応じて、例えば、入出力インタフェース４１０を介して、LCD(Liquid Crystal Display)やスピーカ等で構成される出力部４０６から出力、あるいは、通信部４０８から送信、さらには、ハードディスク４０５に記録等させる。
【０１５９】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０１６０】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【図面の簡単な説明】
【０１６１】
【図１】IRA符号化の符号化装置の構成例を示す図である。
【図２】図１のインターリーバの構成例を示す図である。
【図３】図１のアキュームレータの構成例を示す図である。
【図４】検査行列Hの例を示す図である。
【図５】検査行列Hの例を示す図である。
【図６】LDPC符号化の符号化装置の構成例を示すブロック図である。
【図７】検査行列Hの例を示す図である。
【図８】本発明を適用したLDPC符号化の符号化装置の一実施の形態の構成例を示すブロック図である。
【図９】図８の符号化装置の符号化処理を説明するフローチャートである。
【図１０】本発明を適用したLDPC符号化の符号化装置の他の一実施の形態の構成例を示すブロック図である。
【図１１】図１０の符号化装置の符号化処理を説明するフローチャートである。
【図１２】検査行列Hの例を示す図である。
【図１３】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
【０１６２】
１２０  符号化装置，  １２１  情報ビット格納メモリ，  １２２  演算器，  １２３シフトレジスタ，  １２４  制御信号生成部，  １４０  符号化装置，  １４１  情報ビット格納メモリ，  １４２  演算器，  １４３  シフトレジスタ，  １４４  パンクチャ回路，  １４５  制御信号生成部，  ４０１  バス，  ４０２  CPU，  ４０３  ROM，  ４０４  RAM，  ４０５  ハードディスク，  ４０６  出力部，  ４０７  入力部，  ４０８  通信部，  ４０９  ドライブ，  ４１０  入出力インタフェース，  ４１１  リムーバブル記録媒体
【図１】
2005051469.tif 000003
【図２】
2005051469.tif 000004
【図３】
2005051469.tif 000005
【図４】
2005051469.tif 000006
【図５】
2005051469.tif 000007
【図６】
2005051469.tif 000008
【図７】
2005051469.tif 000009
【図８】
2005051469.tif 000010
【図９】
2005051469.tif 000011
【図１０】
2005051469.tif 000012
【図１１】
2005051469.tif 000013
【図１２】
2005051469.tif 000014
【図１３】
2005051469.tif 000015