(57)【要約】【課題】線形符号の符号化の動作速度を変えることなく、符号化装置の回路規模を削減する。【解決手段】加算器１３は、サイクリックシフト回路１２から供給される６ビットの情報語D12と、その情報に対応する検査行列Hの情報部との積を、６行単位で行ごとに積算し、和D15としてRAM１４に供給する。RAM１４は、その和D15を記憶する。また、RAM１４は、既に記憶されている２ビットの和D15を読み出し、インターリーバ１５を介して、和D17としてアキュムレータ１６に供給する。アキュムレータ１６は、その和D17を積算し、その結果得られる和D１７を符号語ｃのパリティビットｐとして、セレクタ１７を介して出力する。本発明は、衛星放送を送信する放送局の装置に適用することができる。【選択図】図８
2006304132.tif 000002
【特許請求の範囲】
【請求項１】
所定の情報を線形符号に符号化する符号化装置であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記線形符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記線形符号の検査行列が、行や列の置換により、複数の前記構成行列の組み合わせで表される場合において、
前記情報と、その情報に対応する前記検査行列の情報部との積を、複数の行単位で行ごとに積算する第１の積算手段と、
前記第１の積算手段により積算された結果得られる第１の積算値を記憶する記憶手段と、
前記記憶手段から読み出された第１の積算値を積算し、その結果得られる第２の積算値を前記線形符号の一部として出力する第２の積算手段と
を備えることを特徴とする符号化装置。
【請求項２】
前記線形符号はLDPC(Low Density Parity Check)符号である
ことを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記第１の積算手段は、前記Pの約数個の行単位で行ごとに積算する
ことを特徴とする請求項１に記載の符号化装置。
【請求項４】
前記記憶手段は、前記Pの約数個の前記第１の積算値を同時に読み書き可能なメモリから構成される
ことを特徴とする請求項３に記載の符号化装置。
【請求項５】
前記記憶手段は、前記第１の積算値を前記線形符号の検査行列の１を列方向に詰めるように格納する
ことを特徴とする請求項４に記載の符号化装置。
【請求項６】
前記記憶手段は、RAM（Random Access Memory）であり、そのRAMのアドレスは前記検査行列の情報部の前記P個の行に対応する
ことを特徴とする請求項５に記載の符号化装置。
【請求項７】
前記情報と、その情報に対応する前記検査行列の情報部との積を、前記単位行列、準単位行列、またはシフト行列単位で演算する演算手段
をさらに備え、
前記記憶手段は、前記検査行列の情報部の前記和行列を、前記単位行列、準単位行列、またはシフト行列のうちの複数の行列の和に分解したときの、その複数の行列それぞれに対して得られる前記積を同一のアドレスに格納するように、前記演算手段により演算される積を記憶し、
前記第１の積算手段は、前記記憶手段から読み出される積と、前記演算手段により得られる積とを加算することにより、前記P個の行単位で行ごとに前記積を積算する
ことを特徴とする請求項６に記載の符号化装置。
【請求項８】
前記第１の積算手段は、順次入力される前記情報と、その情報に対応する前記検査行列の情報部とを積算し、その結果得られる第１の積算値を、前記記憶手段を介して前記第２の積算手段に順次出力し、
前記第２の積算手段は、前記第１の積算手段から前記記憶手段を介して順次入力される前記第１の積算値を積算し、その結果得られる第２の積算値を順次出力する
ことを特徴とする請求項３に記載の符号化装置。
【請求項９】
前記情報をサイクリックシフトすることにより前記積を算出する並べ替え手段
をさらに備える
ことを特徴とする請求項８に記載の符号化装置。
【請求項１０】
前記第１の積算手段は、
前記積を行ごとに積算する前記Pの約数個の第３の積算手段
を備え、
前記Pの約数個の第３の積算手段は、同時に前記積を行ごとに積算する
ことを特徴とする請求項８に記載の符号化装置。
【請求項１１】
前記第２の積算手段は、前記記憶手段から読み出される第１の積算値と、前回の加算の結果得られた前記第２の積算値とを加算し、その結果得られる加算値を前記第２の積算値として出力するとともに、次回の加算に用いる
ことを特徴とする請求項８に記載の符号化装置。
【請求項１２】
前記第１の積算手段により積算された結果得られる第１の積算値の順序を制御する順序制御手段
をさらに備え、
前記記憶手段は、前記順序制御手段により順序が制御された第１の積算値を記憶する
ことを特徴とする請求項８に記載の符号化装置。
【請求項１３】
前記順序制御手段は、前記第１の積算値の並び替えおよびサイクリックシフトを行うことにより、前記第１の積算値の順序を制御する
ことを特徴とする請求項１２に記載の符号化装置。
【請求項１４】
前記記憶手段は、前記Pの約数個の前記第１の積算値を同時に読み書き可能、かつ独立に制御可能な複数のメモリから構成される
ことを特徴とする請求項１２に記載の符号化装置。
【請求項１５】
前記記憶手段から読み出される第１の積算値の順序を制御する順序制御手段
をさらに備え、
前記第２の積算手段は、前記順序制御手段により順序が制御された第１の積算値を積算する
ことを特徴とする請求項８に記載の符号化装置。
【請求項１６】
前記順序制御手段は、インターリーバである
ことを特徴とする請求項１５に記載の符号化装置。
【請求項１７】
前記P個の情報をサイクリックシフトすることにより、前記積を算出する並べ替え手段
をさらに備える
ことを特徴とする請求項８に記載の符号化装置。
【請求項１８】
前記並べ替え手段は、バレルシフタで構成される
ことを特徴とする請求項１７に記載の符号化装置。
【請求項１９】
所定の値を記憶する記憶手段を備え、所定の情報を線形符号に符号化する符号化装置の符号化方法であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記線形符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記線形符号の検査行列が、行や列の置換により、複数の前記構成行列の組み合わせで表される場合において、
前記情報と、その情報に対応する前記検査行列の情報部との積を、複数の行単位で行ごとに積算する第１の積算ステップと、
前記第１の積算ステップの処理により積算された結果得られる第１の積算値を、前記記憶手段に記憶させる記憶制御ステップと、
前記記憶手段から読み出された第１の積算値を積算し、その結果得られる第２の積算値を前記線形符号の一部として出力する第２の積算ステップと
を含むことを特徴とする符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置および符号化方法に関し、特に、所定の情報を線形符号化する符号化装置および符号化方法に関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、LDPC符号という）が脚光を浴びつつある。
【０００４】
LDPC符号は、R. G. Gallagerによる非特許文献１において最初に提案されたものであり、その後、非特許文献２や、非特許文献３等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【０００６】
以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
【０００７】
LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列Hとしては、例えば、図１に示すように、各列のハミング重み（"1"の数）(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。
【０００８】
このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。
【０００９】
このようなLDPC符号への符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを２元の情報語ｉに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号に符号化する符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列（ｋ行ｎ列の行列）である場合には、検査行列Hは、n-k行ｎ列の行列である。
【００１０】
なお、例えば、nビットの符号語cが、kビットの情報語ｉに続けて、n-kビットのパリティビットｐを配置したビット列に一致する組織符号である場合に、n-k行n列の検査行列Hにおいて、nビットの符号語cのうちのkビットの情報語ｉに対応するn-k行k列の部分を情報部というとともに、n-kビットのパリティビットｐに対応するn-k行n-k列の部分をパリティ部ということとすると、パリティ部が、下三角行列または上三角行列になっていれば、情報語ｉのLDPC符号への符号化は、検査行列Hを用いて行うことができる。
【００１１】
即ち、例えば、検査行列Hが、図２に示すように、情報部と、下三角行列のパリティ部とで構成され、パリティ部の下三角の部分の要素が、すべて１であるとすると、符号語cのパリティビットｐの０番目のビットは、情報語ｉのうちの、検査行列Hの情報部の第０行において１になっている要素に対応するビットのEXOR（排他的論理和）を演算した値となる。
【００１２】
また、符号語cのパリティビットｐの１番目のビットは、情報語ｉのうちの、検査行列Hの情報部の第１行において１になっている要素に対応するビットと、パリティビットｐの０番目のビットのEXORを演算した値となる。
【００１３】
さらに、符号語cのパリティビットｐの２番目のビットは、情報語ｉのうちの、検査行列Hの情報部の第２行において１になっている要素に対応するビットと、パリティビットｐの０番目および１番目のビットのEXORを演算した値となる。
【００１４】
以下、同様にして、符号語cのパリティビットｐのｍ番目のビットは、情報語ｉのうちの、検査行列Hの情報部の第ｍ行において１になっている要素に対応するビットと、パリティビットｐの０乃至ｍ-1番目のビットのEXORを演算した値となる。
【００１５】
以上のようにして、n-kビットのパリティビットｐを求め、kビットの情報語ｉに続けて配置することにより、nビットの符号語cを得ることができる。
【００１６】
即ち、パリティ部が下三角行列の検査行列Hを図３に示すように一般化すると、情報語ｉのLDPC符号への符号化は、検査行列Hを用いて以下のように行われる。
【００１７】
図３では、検査行列Hの０行目(最上行)の成分は、０列目（左端列）から順に、情報部がｈ0,0，ｈ0,1，・・・・ｈ0,k-1となり、パリティ部が１，０，・・・０となっている。また、１行目の成分は、０列目から順に、情報部がｈ1,0，ｈ1,1，・・・・，ｈ1,k-1となり、パリティ部がｈ1,k，１，０，・・・０となっている。以下、同様にして、n-k-1行目(最下行)の成分は、０列目から順に、情報部がｈn-k-1,0，ｈn-k-1,1，・・・・，ｈn-k-1,k-1となり、パリティ部がｈn-k-1,k，・・・，ｈn-k-1,n-2，１となっている。
【００１８】
ここで、ｋビットの情報語ｉをｉ0，ｉ1，・・・，ｉk-1と表し、n-kビットのパリティビットｐをｐ0，ｐ1，・・・，ｐn-k-1と表すとする。即ち、符号語ｃは、ｉ0，ｉ1，・・・，ｉk-1，ｐ0，ｐ1，・・・，ｐn-k-1で表される。符号語ｃと検査行列Hの各行との積の排他的論理和は０であるので、符号語ｃと検査行列Hの０行目との積の演算は、以下の式（１）で表される。
【００１９】
【数１】
2006304132.tif 000003
・・・（１）
【００２０】
従って、パリティビットｐ0は、以下の式（２）で表される。
【００２１】
【数２】
2006304132.tif 000004
・・・（２）
【００２２】
また、符号語ｃと検査行列Hの１行目との積の演算は、以下の式（３）で表される。
【００２３】
【数３】
2006304132.tif 000005
・・・（３）
【００２４】
従って、パリティビットｐ1は、以下の式（４）で表される。
【００２５】
【数４】
2006304132.tif 000006
・・・（４）
【００２６】
同様に、符号語ｃと検査行列Hのn-k-1行目との積の演算は、以下の式（５）で表される。
【００２７】
【数５】
2006304132.tif 000007
・・・（５）
【００２８】
従って、パリティビットｐn-k-1は、以下の式（６）で表される。
【００２９】
【数６】
2006304132.tif 000008
・・・（６）
【００３０】
以上のようにして、n-kビットのパリティビットｐ0，ｐ1，・・・，ｐn-k-1を求め、kビットの情報語ｉであるｉ0，ｉ1，・・・，ｉk-1に続けて配置することにより、nビットの符号語cを得ることができる。
【００３１】
また、近年、LDPC符号の符号化装置の実装方法に関する研究も行われており、シフトレジスタで実装する方法やシフトレジスタの代わりにRAM（Random Access Memory）で実装する方法がある。
【００３２】
【非特許文献１】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", Proceedings of the 30th annual ACM Symposium on Theory of Computing(STOC),1998,pp. 249-258
【発明の開示】
【発明が解決しようとする課題】
【００３３】
しかしながら、シフトレジスタで実装されるLDPC符号の符号化装置では、情報語iのビット数（情報長）分のレジスタから構成されるシフトレジスタが実装されており、情報長が長い場合、レジスタ（フリップフロップ）のゲート数が膨大になる。例えば、フリップフロップの１個当たりのゲート数が９であり、情報長が60000である場合、符号化装置を構成するフリップフロップ全体のゲート数は、５４万（＝９×60000）となり、５０万を超える。その結果、符号化装置の回路規模が増大する。
【００３４】
一方、RAMで実装されるLDPC符号の符号化装置では、RAMから読み出すデータの数やアドレスがLDPC符号（の符号語ｃ）の符号長、符号化率などによって異なり、１つの符号化装置で符号長、符号化率などのパラメータの異なるLDPC符号（の符号語ｃ）を得ることは困難である。また、RAMの構造は、データのパラレル入力または出力に適していない。
【００３５】
本発明は、このような状況に鑑みてなされたものであり、LDPC符号の符号化の動作速度を変えることなく、符号化装置の回路規模を削減することができるようにするものである。
【課題を解決するための手段】
【００３６】
本発明の符号化装置は、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、線形符号の検査行列が、複数の構成行列の組み合わせで表される場合、または線形符号の検査行列が、行や列の置換により、複数の構成行列の組み合わせで表される場合において、情報と、その情報に対応する検査行列の情報部との積を、複数の行単位で行ごとに積算する第１の積算手段と、第１の積算手段により積算された結果得られる第１の積算値を記憶する記憶手段と、記憶手段から読み出された第１の積算値を積算し、その結果得られる第２の積算値を線形符号の一部として出力する第２の積算手段とを備えることを特徴とする。
【００３７】
本発明の符号化方法は、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、線形符号の検査行列が、複数の構成行列の組み合わせで表される場合、または線形符号の検査行列が、行や列の置換により、複数の構成行列の組み合わせで表される場合において、情報と、その情報に対応する検査行列の情報部との積を、複数の行単位で行ごとに積算する第１の積算ステップと、第１の積算ステップの処理により積算された結果得られる第１の積算値を、記憶手段に記憶させる記憶制御ステップと、記憶手段から読み出された第１の積算値を積算し、その結果得られる第２の積算値を線形符号の一部として出力する第２の積算ステップとを含むことを特徴とする。
【００３８】
本発明においては、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、線形符号の検査行列が、複数の構成行列の組み合わせで表される場合、または線形符号の検査行列が、行や列の置換により、複数の構成行列の組み合わせで表される場合において、情報と、その情報に対応する検査行列の情報部との積を、複数の行単位で行ごとに積算し、第１の積算ステップの処理により積算された結果得られる第１の積算値を、記憶手段に記憶させ、記憶手段から読み出された第１の積算値を積算し、その結果得られる第２の積算値を線形符号の一部として出力する。
【発明の効果】
【００３９】
本発明によれば、線形符号の符号化の動作速度を変えることなく、符号化装置の回路規模を削減することができる。
【発明を実施するための最良の形態】
【００４０】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００４１】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００４２】
請求項１に記載の符号化装置は、
所定の情報(例えば、情報語ｉ)を線形符号に符号化する符号化装置（例えば、図８の符号化装置１）であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記線形符号の検査行列（例えば、検査行列H）が、複数の前記構成行列の組み合わせで表される場合、または前記線形符号の検査行列が、行や列の置換により、複数の前記構成行列の組み合わせで表される場合において、
前記情報と、その情報に対応する前記検査行列の情報部との積を、複数の行(例えば、６行)単位で行ごとに積算する第１の積算手段(例えば、図８の加算器１３)と、
前記第１の積算手段により積算された結果得られる第１の積算値を記憶する記憶手段(例えば、図８のRAM１４)と、
前記記憶手段から読み出された第１の積算値を積算し、その結果得られる第２の積算値を前記線形符号の一部として出力する第２の積算手段(例えば、図８のアキュムレータ１６)と
を備えることを特徴とする。
【００４３】
請求項７に記載の符号化装置は、
前記情報と、その情報に対応する前記検査行列の情報部との積を、前記単位行列、準単位行列、またはシフト行列単位で演算する演算手段(例えば、図８のサイクリックシフト回路１２)
をさらに備え、
前記記憶手段は、前記検査行列の情報部の前記和行列を、前記単位行列、準単位行列、またはシフト行列のうちの複数の行列の和に分解したときの、その複数の行列それぞれに対して得られる前記積を同一のアドレスに格納するように、前記演算手段により演算される積を記憶し（例えば、図１７のステップＳ５の処理）、
前記第１の積算手段は、前記記憶手段から読み出される積と、前記演算手段により得られる積とを加算することにより、前記P個の行単位で行ごとに前記積を積算する(例えば、図１７のステップＳ４の処理)
ことを特徴とする。
【００４４】
請求項９に記載の符号化装置は、
前記情報をサイクリックシフトすることにより前記積を算出する並べ替え手段(例えば、図８のサイクリックシフト回路１２)
をさらに備える
ことを特徴とする。
【００４５】
請求項１１に記載の符号化装置は、
前記第２の積算手段は、前記記憶手段から読み出される第１の積算値と、前回の加算の結果得られた前記第２の積算値とを加算し、その結果得られる加算値を前記第２の積算値として出力するとともに、次回の加算に用いる（例えば、図１７のステップＳ９の処理）
ことを特徴とする。
【００４６】
請求項１２に記載の符号化装置は、
前記第１の積算手段により積算された結果得られる第１の積算値の順序を制御する順序制御手段(例えば、図１８の並べ替え回路１０１とサイクリックシフト回路１０２)
をさらに備え、
前記記憶手段は、前記順序制御手段により順序が制御された第１の積算値を記憶する（例えば、図２１のステップＳ２７の処理）
ことを特徴とする。
【００４７】
請求項１３に記載の符号化装置は、
前記順序制御手段は、前記第１の積算値の並び替えおよびサイクリックシフトを行うことにより、前記第１の積算値の順序を制御する（例えば、図２１のステップＳ２４とＳ２５の処理）
ことを特徴とする。
【００４８】
請求項１５に記載の符号化装置は、
前記記憶手段から読み出される第１の積算値の順序を制御する順序制御手段(例えば、図８のインターリーバ１５)
をさらに備え、
前記第２の積算手段は、前記順序制御手段により順序が制御された第１の積算値を積算する(例えば、図１７のステップＳ９)
ことを特徴とする。
【００４９】
請求項１７に記載の符号化装置は、
前記P個の情報をサイクリックシフトすることにより、前記積を算出する並べ替え手段（例えば、図８のサイクリックシフト回路１２）
をさらに備える
ことを特徴とする。
【００５０】
請求項１９に記載の符号化方法は、
所定の値を記憶する記憶手段(例えば、図８のRAM１４)を備え、所定の情報を線形符号に符号化する符号化装置(例えば、図８の符号化装置１)の符号化方法であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記線形符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記線形符号の検査行列が、行や列の置換により、複数の前記構成行列の組み合わせで表される場合において、
前記情報と、その情報に対応する前記検査行列の情報部との積を、複数の行単位で行ごとに積算する第１の積算ステップ(例えば、図１７のステップＳ４)と、
前記第１の積算ステップの処理により積算された結果得られる第１の積算値を、前記記憶手段に記憶させる記憶制御ステップ(例えば、図１７のステップＳ５)と、
前記記憶手段から読み出された第１の積算値を積算し、その結果得られる第２の積算値を前記線形符号の一部として出力する第２の積算ステップ（例えば、図１７のステップＳ９）と
を含むことを特徴とする。
【００５１】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００５２】
なお、情報語ｉとLDPC符号の符号語ｃにおいては、１ビットを｛０，・・・，ｑ｝（ｑ≧１）で表すことが可能であり、必ずしも２元である必要はないが、以下では、２元であるものとして説明する。
【００５３】
図４は、LDPC符号化に用いる検査行列Hの例を示している。
【００５４】
図４の検査行列Hは、n=108，k=72の符号語ｃ（符号化率2/3、符号長108）を得るための検査行列Hであり、３６(行)×１０８（列）の行列である。なお、図４の検査行列Hでは(後述する図５乃至７，２２、および２５の行列においても同様)、０を、"."で表現している。また、図４の検査行列Hは、６×６の行列の単位に間隔を空けて表したものである。
【００５５】
即ち、検査行列Hは、３６（=n-k）行７２（=k）列の情報部と、３６(=n-k)行３６（=n-k）列のパリティ部とから構成される。LDPC符号への符号化においては、情報部は、LDPC符号の符号語ｃの情報語ｉと乗算され、パリティ部は、符号語ｃのパリティビットｐと乗算される。
【００５６】
図４の検査行列Hでは、LDPC符号の情報語ｉに対応する情報部の各行は、７個の“１”と、１０１個の“０”から構成される。パリティ部は、下三角状の構造を有する行列（下三角行列）となっている。即ち、図４の検査行列Hのパリティ部は、行列の対角線の右上が全て“０”とされた行列となっており、下三角状の構造を有している。
【００５７】
図５と図６は、図４の検査行列Hを行置換または列置換した後の検査行列H´を示している。
【００５８】
図５の検査行列H´では、情報部を、P×P（図５の例の場合、P＝６）の単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、P×Pの０行列の組み合わせで表すことができる。なお、以下では、P×Pの単位行列、準単位行列、シフト行列、和行列、０行列を、以下、適宜、構成行列という。
【００５９】
図６の検査行列Hは、図５に示した検査行列Hを、６×６の構成行列の単位に間隔を空けて表したものである。検査行列Hを構成する横方向の構成行列の数をｎ0個とし、検査行列Hの情報部を構成する横方向の構成行列の数をｋ0個とすると、ｎ0（=n/P=108/6）は18となり、ｋ0（=k/P=72/6）は12となる。
【００６０】
即ち、図５や図６の検査行列Hでは、縦方向に６（=ｎ0-ｋ0=18-12）個の構成行列が、横方向にｎ0(=18)個の構成行列が並んでいる。
【００６１】
また、図４の検査行列Hの最上行（先頭行）を０行目とすると、検査行列Hの（n0-k0）×v＋w（0≦v≦P-1,0≦ｗ≦n0-k0-1）行目の行は、図５や図６の検査行列H´では、P×w+v行目の行となっている。
【００６２】
図５や図６の検査行列H´を用いてLDPC符号化を行うことにより、LDPC符号化に必要な演算である検査行列H´の情報部の各行と情報語ｉとの積算を、情報語ｉを６個単位でサイクリックシフトすることで行うことができる。即ち、構成行列であるP×Pの単位行列、準単位行列、またはシフト行列、もしくは構成行列の和行列を複数の行列に分解したときのP×Pの単位行列、準単位行列、またはシフト行列の各行の“１”の数は１個であるので、その構成行列に対応する６個の情報語ｉをサイクリックシフトすることで、検査行列H´の情報部の各行と情報語ｉとの積を算出することができる。
【００６３】
図７Ａ乃至図７Ｂは、図４の検査行列Hと図５や図６の検査行列H´のパリティ部を示している。
【００６４】
図７Ａに示すように、図４の検査行列Hのパリティ部は、行列の対角線の右上が全て“０”とされた行列となっており、下三角状の構造を有している。また、パリティ部は、下三角行列の対角成分とその成分の直下の成分が１であり、それ以外の成分が０となっている。これにより、LDPC符号化におけるパリティビットｐを求める演算を容易に行うことができる。
【００６５】
図７Ｂに示すように、図５や図６の検査行列H´のパリティ部では、図７Ａのパリティ部の（n0-k0）×ｖ＋ｗ行目の行が、P×ｗ＋ｖ行目の行となる。
【００６６】
図８は、本発明を適用した符号化装置１の第１実施の形態の構成例を示すブロック図である。
【００６７】
図８の符号化装置１は、図４の検査行列Hを用いて、情報語ｉをLDPC符号化し、その結果得られる符号語ｃを出力する。
【００６８】
符号化装置１は、ビット幅調整回路１１、サイクリックシフト回路１２、加算器１３、RAM１４、インターリーバ１５、アキュムレータ１６、セレクタ１７、および制御部１８から構成される。
【００６９】
ビット幅調整回路１１には、情報語D11（情報語ｉ）が２ビット単位で供給され、ビット幅調整回路１１は、２ビット単位で供給された情報語D11を３つ合わせて、６ビット単位で情報語D12としてサイクリックシフト回路１２に供給する。
【００７０】
サイクリックシフト回路１２には、制御部１８から、情報語D12に対応する検査行列H´の情報部の１が、検査行列H´において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報を表す制御信号D21が供給される。サイクリックシフト回路１２は、制御信号D21に基づいて、ビット幅調整回路１１から順次供給される１２（=k0)個の６ビットの情報語D12をサイクリックシフトすることにより、検査行列H´を構成する構成行列のうち０行列ではない構成行列の各行の値ｈと情報語D12との積（h×i）を求め、加算器１３に順次供給（出力）する。
【００７１】
なお、構成行列が和行列である場合、即ち構成行列のハミング重みが２以上である場合、サイクリックシフト回路１２は、和行列を単位行列、準単位行列、またはシフト行列のうちの複数の行列の和に分解したときの、その行列単位で、行列と情報語D12との積を求め、それらを対応する行ごとにEXOR演算（加算）した値を、情報語D13として加算器１３に供給する。また、サイクリックシフト回路１２は、６ビット単位で情報語D12のサイクリックシフトを行うようにしたが、６(=P)の約数個のビット単位でサイクリックシフトを行うようにしてもよい。
【００７２】
加算器１３は、６つの加算器（図示せず）から構成され、各加算器は、サイクリックシフト回路１２からの６ビットの積D13とRAM１４からの６ビットの和D14とのEXORをビット毎に求め、その結果得られる６ビットの値を和D15（第１の積算値）としてRAM１４に供給することにより、積D13を６行単位で行ごとに積算する。
【００７３】
RAM１４には、制御部１８から、データの読み出しまたは書き込みを行うアドレスを指定する制御信号D22が供給される。RAM１４は、その制御信号D22に基づいて、加算器１３からの和D15を６ビット単位で記憶したり、既に記憶している和D15を６ビットまたは２ビット単位で読み出す。
【００７４】
このように、RAM１４は、６ビットまたは２ビットの和D15を同時に記憶したり、読み出すことができるので、LDPC符号化における処理を６ビットまたは２ビット単位で行うことができる。その結果、符号化装置１では、適度な回路規模と動作周波数でLDPC符号化を行うことができる。
【００７５】
RAM１４は、６ビット単位で読み出した和D15を、和D14として加算器１３に供給したり、２ビット単位で読み出した和D15を、和D16としてインターリーバ１５に供給する。なお、RAM１４のビット数は６（=P）であり、ワード数は６（=n0-k0）である。
【００７６】
インターリーバ１５は、RAM１４から供給される和D16の順序を制御する。具体的には、インターリーバ１５は、和D16を検査行列Hに対応する順序に並べ替え、並べ替え後の和D17をアキュムレータ１６に供給する。
【００７７】
アキュムレータ１６には、制御部１８から、アキュムレータ１６のセレクタ６２（後述する図１４）における選択を表す選択信号D23が供給され、アキュムレータ１６は、その選択信号D23とインターリーバ１５から順次供給される和D17とに基づいて、所定の演算（例えば、式（２），（４），（６））を行い、その結果得られるパリティビットｐを２ビット単位でパリティビットD18としてセレクタ１７に順次供給(出力)する。即ち、アキュムレータ１６は、和D17を積算し、その結果得られるパリティビットｐを２ビット単位でパリティビットD18（第２の積算値）としてセレクタ１７に供給する。
【００７８】
セレクタ１７には、所定の時間遅延された情報語ｉが２ビット単位で情報語D19として供給される。セレクタ１７は、制御部１８からの、パリティビットD18と情報語D19のいずれか一方の選択を表す選択信号D24に基づいて、アキュムレータ１６からのパリティビットD18と情報語D19のうちのいずれか一方を選択し、２ビット単位で符号語D20（符号語ｃ）として出力する。具体的には、セレクタ１７は、kビットの情報語D19を２ビット単位で出力し、その後n-kビットのパリティビットD18を２ビット単位で出力することにより、符号語D20を出力する。
【００７９】
制御部１８は、制御信号D21をサイクリックシフト回路１２に、制御信号D22をRAM１４に、選択信号D23をアキュムレータ１６に、選択信号D24をセレクタ１７に供給する。
【００８０】
図９を参照して、図８のサイクリックシフト回路１２が行うサイクリックシフトの量について説明する。
【００８１】
なお、以下では、ビット幅調整回路１１から供給される情報語ｉの（6×s）乃至（6×(s+1)-1）ビット目（s=0,1,2,・・・，k0-1）の情報語D12をｓ番ベクトルという。
【００８２】
図９において、最上行の数字はベクトルの番号を表し、左端の数字は、検査行列H´の構成行列の上からの番号を表している。なお、構成行列の上からの番号は、０から順に付与するものとする。また、図９において、「−」はサイクリックシフト回路１２が情報語D13を出力しないことを表している。
【００８３】
例えば、第ｍ行第ｌ列を、(ｍ,ｌ)と表すこととすると、図６に示すように、検査行列H´の(0,0)から(5,5)の構成行列は単位行列、(6,0)から(11,5)の構成行列は和行列（６×６の単位行列を右方向に２つだけサイクリックシフトした第１のシフト行列と、右方向に４つだけサイクリックシフトした第２のシフト行列の和である和行列）、(12,0)から(17,5)の構成行列は０行列、(18,0)から(23,5)の構成行列はシフト行列（６×６の単位行列を右方向に３つだけサイクリックシフトしたシフト行列）、(24,0)から(29,5)の構成行列は０行列、(30,0)から(35,5)の構成行列はシフト行列（６×６の単位行列を右方向に５つだけサイクリックシフトしたシフト行列）となっている。
【００８４】
そこで、サイクリックシフト回路１２は、検査行列H´の左から０乃至５列目を構成する構成行列に応じて、まず最初に、サイクリックシフトを行わず、０番ベクトルと検査行列H´の(0,0)から(5,5)の構成行列との積として、０番ベクトルをそのまま積D13として出力する。即ち、図９に示すように、０番ベクトルと検査行列H´の上から０番目の構成行列との積を求める場合、サイクリックシフト回路１２のサイクリックシフト量は０回となる。
【００８５】
次に、サイクリックシフト回路１２は、０番ベクトルを右方向に２つだけサイクリックシフトするとともに、０番ベクトルを右方向に４つだけサイクリックシフトし、その結果得られる２つのサイクリックシフト後の６ビットの情報語D12をEXOR演算することにより、０番ベクトルと(6,0)から(11,5)の構成行列との積を求める。即ち、(6,0)から(11,5)の構成行列を第１のシフト行列と第２のシフト行列の和に分解したときの、第１のシフト行列と第２のシフト行列それぞれに対して得られる情報語D12が、加算器１３を介して、RAM14の同一のアドレスに格納されるように、サイクリックシフト回路１２は、第１と第２のシフト行列それぞれに対して得られる情報語D12をEXOR演算する。そして、サイクリックシフト回路１２は、その求めた積を、積D13として出力する。
【００８６】
即ち、図９に示すように、０番ベクトルと検査行列H´の上から１番目の構成行列との積を求める場合、サイクリックシフト回路１２のサイクリックシフト量は右方向に２回と４回である。
【００８７】
ここで、検査行列H´の上から２番目の(12,0)から(17,5)の構成行列は０行列であるので、その構成行列については、サイクリックシフト回路１２は何も処理を行わず、何も出力しない（図９の「−」）。
【００８８】
以下、同様にして、サイクリックシフト回路１２は、０番ベクトルを右方向に３回サイクリックシフトすることにより、０番ベクトルと検査行列H´の３番目の(18,0)から(23,5)の構成行列との積を求め、０番ベクトルを左方向に５回サイクリックシフトすることにより、０番ベクトルと(30,0)から(35,5)の構成行列との積を求める。そして、サイクリックシフト回路１２は、サイクリックシフト後の情報語D12を積D13として出力する。
【００８９】
以上のようにして、サイクリックシフト回路１２は、１回目にビット幅調整回路１１から供給される０番ベクトルと、検査行列H´の左から０乃至５（＝P-1）列目との積をそれぞれ求める。
【００９０】
以降も同様に、サイクリックシフト回路１２は、２乃至１２回目にビット幅調整回路１１から供給される１乃至１１番ベクトルと、検査行列H´の左から６乃至７１列目との積をそれぞれ求める。
【００９１】
次に、図１０と図１１を参照して、図８のRAM１４に記憶される和D15について説明する。
【００９２】
なお、以下の説明に用いるRAM１４のワード方向とは、図１０に示すように、図中横方向であり、左端から順に０番アドレス、１番アドレス、２番アドレス、・・・という。また、RAM１４のビット方向とは、図中縦方向であり、上から順に０ビット目、１ビット目、２ビット目、・・・という。
【００９３】
また、以下では、検査行列H´の上からv番目の構成行列の上からw行目（=P×v+w=6×v+w）と０乃至１１番ベクトルのそれぞれとの積の和D１５を、ｏw,vとも表す。即ち、ｏw,vは、以下の式（７）で表される。
【００９４】
【数７】
2006304132.tif 000009
・・・（７）
【００９５】
図１１に示すように、RAM１４のビット数はＰ(=6)であり、ワード数は、n0-k0（=6）である。まず最初に、RAM１４には、サイクリックシフト回路１２から加算器１３を介して、０番ベクトルと検査行列H´の上から０番目の構成行列との積が６ビットの和D15として供給され、RAM１４は、その和D15の各ビットを０番アドレスの０ビット目から順に記憶する。
【００９６】
次に、RAM１４には、サイクリックシフト回路１２から加算器１３を介して、１番ベクトルと検査行列H´の上から１番目の構成行列との積が６ビットの和D15として供給され、RAM１４は、その和D15の各ビットを１番アドレスの０ビット目から順に記憶する。以降、同様にして、RAM１４の２乃至５番アドレスにも、和D15が記憶される。
【００９７】
また、RAM１４は、０番アドレスの０乃至５ビット目に記憶されている０番ベクトルと検査行列H´の上から０番目の構成行列との積を読み出し、６ビットの和D14として加算器１３に供給する。以降、同様にして、RAM１４の１乃至５番アドレスに記憶されている６ビットの和D15をそれぞれ読み出し、和D14として加算器１３に供給する。
【００９８】
加算器１３は、RAM１４から６ビットの和D14として供給される０番ベクトルと検査行列H´の上から０番目の構成行列との積と、サイクリックシフト回路１２から供給される１番ベクトルと検査行列H´の上から０番目の構成行列との積とをEXOR演算し、その結果得られる和D15をRAM１４に供給する。RAM１４は、その和D15の各ビットを０番アドレスの０ビット目から順に記憶する。即ち、RAM１４は、０番アドレスを更新する。以降、同様にして、RAM１４は、１乃至５番アドレスも更新する。
【００９９】
そして、同様の処理が繰り返され、RAM１４の０番アドレスの０ビット目には、検査行列H´の上から０番目の構成行列の上から０行目と０乃至１１番ベクトルのそれぞれとの積の和D１５であるｏ0,0が記憶される。また、RAM１４の０番アドレスの１乃至５ビット目には、ｏ1,0,乃至ｏ5,0がそれぞれ記憶される。
【０１００】
同様に、RAM１４の１番アドレスの０乃至５ビット目には、それぞれｏ0,1,乃至ｏ5,1が、２番アドレスの０乃至５ビット目には、それぞれｏ0,2,乃至ｏ5,2が、RAM１４の３番アドレスの０乃至５ビット目には、それぞれｏ0,3,乃至ｏ5,3が、RAM１４の４番アドレスの０乃至５ビット目には、それぞれｏ0,4,乃至ｏ5,4が、５番アドレス０乃至５ビット目には、それぞれｏ0,5,乃至ｏ5,5が記憶される。
【０１０１】
以上のように、RAM１４のアドレスは、検査行列Hの情報部の６行に対応し、RAM１４は、図中左上から右下方向に向かって、和D15に対応する検査行列H´の上からの行数（6×v+w）が大きくなるように、和D15（ｏ0,0,乃至ｏ5,5）を記憶する。また、RAM１４は、ｏ0,0,乃至ｏ5,5を、検査行列H´の構成行列の１を列方向（横方向）に詰めるように記憶（格納）する。
【０１０２】
ここで、ビット方向（縦方向）での順番がP×x+y（x=0,1,・・・，5，y=0,1,・・・，5）番目の和D15は、ワード方向（横方向）での順番が（n0-k0）×y+x番目となる。なお、ビット方向の順番は、各番号アドレスの５ビット目の次が、右隣のアドレス（次の番号のアドレス）の０ビット目となるものとする。また、ワード方向の順番は、各ビットの５番アドレスの次が、直下のビット(次のビット)の０番アドレスとなるものとする。例えば、ビット方向での順番が６番目の和D15はｏ0,1となり、ワード方向での順番が６番目の和D15はｏ1,0となる。
【０１０３】
上述したように、検査行列Hの（n0-k0）×v＋w行目の行は、図５の検査行列H´では、P×w+v行目の行となる。即ち、検査行列H´のP×w+v行目の行は、検査行列Hの（n0-k0）×v＋w行目の行である。従って、RAM１４のビット方向に検査行列H´の０行目から順に和D15として記憶される、検査行列H´の情報部の各行と０乃至１１番ベクトルのそれぞれとの積の和であるｏw,vは、ワード方向の順番に見ると、検査行列Hの０行目から順に対応する積の和であるｏw,vとなる。
【０１０４】
しかしながら、RAM１４は、一般的に２つ以上のアドレスに同時にアクセスすることができないため、ワード方向に和D15を読み出すことはできない。従って、符号化装置１では、インターリーバ１５により、RAM１４がビット方向に読み出した和D15の順序を入れ替えている。インターリーバ１５の詳細については、後述する図１２と図１３を参照して説明する。
【０１０５】
図１２は、図８のインターリーバ１５の詳細構成例を示す図である。
【０１０６】
図１２のインターリーバ１５は、５つのレジスタ４１−１乃至４１−５および５つのレジスタ４２−１乃至４２−５、並びにセレクタ４３から供給される。
【０１０７】
インターリーバ１５には、RAM１４から２ビットの和D16が供給され、そのうちの１ビットが和D41としてレジスタ４１−１乃至４１−５に１ビット単位で順に記憶される。また、他の１ビットが和D42としてレジスタ４１−２乃至４１−５に１ビット単位で順に記憶される。レジスタ４１−１乃至４１−５とレジスタ４２−１乃至４２−５は、記憶している１ビットの和D41またはD42をそれぞれセレクタ４３に供給する。
【０１０８】
セレクタ４３は、レジスタ４１−１乃至４１−５とレジスタ４２−1乃至４２−５のそれぞれから供給される５つの和D41またはD42のうち、いずれか２つの和D41またはD42を選択し、和D43とD44として出力する。１ビットの和D43とD44は合わせられ、２ビットの和D17としてアキュムレータ１６に供給される。
【０１０９】
以上のように、インターリーバ１５では、レジスタ４１−１乃至４１−５およびレジスタ４２−１乃至４２−５が、入力された和D16（和D41またはD42）を記憶し、セレクタ４３が、そのレジスタ４１−１乃至４１−５およびレジスタ４２−１乃至４２−５に記憶されている和D16を選択して、和D17（和D43またはD44）として出力することにより、入力される和D16と出力される和D17の順序を入れ替える。
【０１１０】
次に、図１３を参照して、図１２のインターリーバ１５におけるデータの入出力を説明するタイミングチャートである。図１３において、横軸は時間を表している。
【０１１１】
図１３に示すように、まず最初に、RAM１４は、０番アドレスに記憶されているｏ0,0,とｏ1,0の２ビットを、和D16として読み出してインターリーバ１５に出力する。即ち、インターリーバ１５には、ｏ0,0,とｏ1,0が和D16として入力される。
【０１１２】
次に、RAM１４は、１番アドレスに記憶されているｏ0,1,とｏ1,1の２ビットを、和D16としてインターリーバ１５に出力する。以降、同様にして、RAM１４は、２乃至５番アドレスに記憶されているｏ0,2,とｏ1,2、ｏ0,3,とｏ1,3、ｏ0,4,とｏ1,4、またはｏ0,5,とｏ1,5を、和D16としてそれぞれインターリーバ１５に出力する。
【０１１３】
図１２のインターリーバ１５のレジスタ４１−１乃至４１−５には、例えば、インターリーバ１５に入力される和D16のうちの１ビットであるｏ0,0乃至ｏ0,5が順に供給され、記憶される。また、他の１ビットであるｏ1,0乃至ｏ5,0がレジスタ４２−１乃至４２−５に順に供給され、記憶される。そして、レジスタ４１−１乃至４１−５と４２−１乃至４２−５は、ｏ0,0乃至ｏ0,5とｏ1,0乃至ｏ5,0をそれぞれセレクタ４３に供給する。
【０１１４】
図１３に示すように、セレクタ４３は、まず最初にｏ0,0とｏ0,1を選択し、和D43とD44としてそれぞれ出力する。即ち、ｏ0,0とｏ0,1が和D17としてアキュムレータ１６に入力される。次に、セレクタ４３は、ｏ0,2とｏ0,3を選択し、それぞれ和D43とD44として出力する。その後、セレクタ４３は、ｏ0,4とｏ0,5、ｏ1,0とｏ1,1、ｏ1,2とｏ1,3、ｏ1,4とｏ1,5の順に選択して出力する。
【０１１５】
即ち、インターリーバ１５に入力される和D16のうちの１ビットであるRAM１４の０ビット目に記憶されるｏ0,0乃至ｏ0,5を系列＃１といい、他の１ビットであるRAM１４の１ビット目に記憶されるｏ1,0乃至ｏ5,0を系列＃２というと、セレクタ４３は、系列＃１をｏ0,0から順に２ビットずつ選択し、その後系列＃２をｏ1,0から順に２ビットずつ選択する。即ち、セレクタ４３は、入力される和D16を、その和D16が記憶されているRAM１４のワード方向の順番に２ビットずつ選択する。
【０１１６】
以上のように、インターリーバ１５は、RAM１４のビット方向の順番に読み出され、入力される２ビットの和D16を、その和D16が記憶されているRAM１４のワード方向の順番に２ビットずつ選択して出力するので、検査行列Hの情報部の各行と０乃至１１番ベクトルのそれぞれとの積の和であるｏw,vを、検査行列Hの情報部の０行目から順に、２ビット単位で和D17として出力することができる。
【０１１７】
図１４は、図８のアキュムレータ１６の詳細構成例を示している。
【０１１８】
図１４のアキュムレータ１６は、加算器６１と６３、並びにセレクタ６２から構成される。
【０１１９】
加算器６１には、インターリーバ１５から２ビットの和D17のうちの１ビットである和D61が供給されるとともに、加算器６３から前回の加算の結果得られたパリティビットD65が供給される。加算器６１は、和D61とパリティビットD65を加算し、その結果得られる値を和D63として、セレクタ６２に供給する。
【０１２０】
セレクタ６２には、和D61が供給されるとともに、制御部１８から選択信号D23が供給され、セレクタ６２は、選択信号D23に基づいて、和D61またはD63をパリティビットD64として、セレクタ１７と加算器６３に出力する。
【０１２１】
加算器D63には、インターリーバ１５から２ビットの和D17のうちの和D61以外の１ビットである和D62が供給される。加算器D63は、セレクタ６２から供給される前回の加算の結果得られたパリティビットD64と和D62とを加算し、その結果得られる値をパリティビットD65として、セレクタ１７と加算器６１に出力する。なお、セレクタ６２と加算器６３から出力されるパリティビットD64とD65は合わせられ、２ビットのパリティビットD18（パリティビットp）としてセレクタ１７に供給される。
【０１２２】
図１５と図１６を参照して、図１４のアキュムレータ１６で行われるパリティビットpの演算について説明する。
【０１２３】
図１５と図１６に示すように、上述した式（２）と式（７）により、パリティビットp0=ｏ0,0となる。また、上述した式（３）と式（７）により、図１５に示すように、ｏ0,1+h1,kp0+p1=0となり、検査行列Hではh1,kは１であるので、ｏ0,1+p0+p1=0（ｏ0,1=p0+p1）となる。即ち、図１６に示すように、パリティビットp1=ｏ0,0+p0である。
【０１２４】
具体的には、図１４のアキュムレータ１６に、インターリーバ１５からｏ0,0とｏ0,1の２ビットの和D17が供給され、加算器６１とセレクタ６２にｏ0,0が和D61として供給され、加算器６３にｏ0,1が和D62として供給される。このとき、まだ加算器６３による加算が行われていないので、加算器６１にはパリティビットD65が供給されておらず、加算器６３は、和D61をそのまま和D63としてセレクタ６２に供給する。
【０１２５】
セレクタ６２は、選択信号D23に基づいてインターリーバ１５からの和D61（いまの場合、ｏ0,0）を選択し、パリティビットD64（いまの場合、p0）としてセレクタ１７と加算器６３に出力する。加算器６３は、インターリーバ１５からの和D62（いまの場合、ｏ0,1）と、セレクタ６２からのパリティビットD64とを加算し、その結果得られる値（いまの場合、ｏ0,1+p0）をパリティビットD65(いまの場合、p1)として、セレクタ１７と加算器６１に出力する。その結果、パリティビットD64とD65が合わせられて、２ビットのパリティビットD18としてセレクタ１７と加算器６１に出力される。
【０１２６】
以降、同様にして、アキュムレータ１６は、図１５や図１６に示す式により、パリティビットp2乃至pn-k-1を２ビットずつ演算し、パリティビットD18として出力する。
【０１２７】
次に、図１７を参照して、図８の符号化装置１による符号化処理を説明する。この符号化処理は、例えば、情報語D11（情報語ｉ）が２ビット単位で入力されたとき、開始される。
【０１２８】
ステップＳ１において、ビット幅調整回路１１は、サイクリックシフト回路１２に出力する情報語D12のベクトルの番号ｓを０に設定し、ステップＳ２に進む。
【０１２９】
ステップＳ２において、ビット幅調整回路１１は、２ビット単位で入力される情報語D11を合わせて６ビットにし、ｓ番ベクトル（情報語D12）としてサイクリックシフト回路１２に供給する。
【０１３０】
ステップＳ２の処理後は、ステップＳ３に進み、サイクリックシフト回路１２は、制御部１８からの制御信号D21に基づいて、ｓ番ベクトルをサイクリックシフトすることにより、検査行列H´の情報部を構成する構成行列のうち、０行列ではない構成行列の各行の値ｈとｓ番ベクトルとの積（h×i）を求め、６ビットの積D13として、加算器１３に供給する。
【０１３１】
ステップＳ３の処理後は、ステップＳ４に進み、加算器１３は、サイクリックシフト回路１２からの６ビットの積D13と、後述するステップＳ５でRAM１４から供給される６ビットの和D14との排他的論理和をビット毎に求め、その結果得られる６ビットの値を和D15としてRAM１４に供給する。なお、最初のステップＳ３では、RAM１４から和D14が供給されないので、加算器１３は、積D13をそのまま和D15としてRAM１４に供給する。
【０１３２】
ステップＳ４の処理後は、ステップＳ５に進み、RAM１４は、制御部１８からの制御信号D22に基づいて、加算器１３からの和D15を６ビット単位で記憶する。また、RAM１４は、既に記憶している和D15を６ビットまたは２ビット単位で読み出す。RAM１４は、６ビット単位で読み出した和D15を、和D14として加算器１３に供給したり、２ビット単位で読み出した和D15を、和D16としてインターリーバ１５に供給する。
【０１３３】
ステップＳ５の処理後は、ステップＳ６に進み、ビット幅調整回路１１は、ベクトルの番号sが１１より小さいかどうかを判定し、１１より小さいと判定した場合、ステップＳ７に進む。
【０１３４】
ステップＳ７において、ビット幅調整回路１１は、ベクトルの番号ｓを１だけインクリメントし、ステップＳ２に戻り、上述した処理を繰り返す。
【０１３５】
一方、ステップＳ６において、ベクトルの番号ｓが１１より小さくはない（１１以上である）と判定された場合、ステップＳ８に進み、インターリーバ１５は、ステップＳ５でRAM１４から供給される和D16を、検査行列Hに対応する順序に並べ替え、並べ替え後の和D17をアキュムレータ１６に供給する。
【０１３６】
ステップＳ８の処理後は、ステップＳ９に進み、アキュムレータ１６は、インターリーバ１５からの和D17を用いて、所定の演算を行い、その結果得られるパリティビットｐを、２ビット単位でパリティビットD18としてセレクタ１７に供給し、ステップＳ１０に進む。
【０１３７】
ステップＳ１０において、セレクタ１７は、２ビット単位で遅延されて入力される情報語D19を符号語D20としてすべて出力した後、ステップＳ９でアキュムレータ１６から供給されるパリティビットD18を２ビット単位で符号語D20として出力することにより、符号語ｃを出力し、処理を終了する。
【０１３８】
図１８は、本発明を適用した符号化装置１の第２の実施の形態の構成例を示すブロック図である。
【０１３９】
図１８の符号化装置１は、ビット幅調整回路１１、サイクリックシフト回路１２、アキュムレータ１６、セレクタ１７、並べ替え回路１０１、サイクリックシフト回路１０２、加算器１０３、３つのRAM１０４−１乃至１０４−３から構成されるRAM１０４、並びに制御部１０５から構成される。なお、図８と同一のものには同一の符号を付してあり、説明は繰り返しになるので省略する。
【０１４０】
並べ替え回路１０１には、サイクリックシフト回路１２から６ビットの積D13が供給されるとともに、制御部１０５から並び替えを制御する制御信号D105が供給される。並び替え回路１０１は、制御信号D105に基づいて、積D13の並び替えを行い、並び替え後の積D13を、積D101としてサイクリックシフト回路１０２に供給する。なお、図１８の符号化装置１では、RAM１０４の数が３つであり、n0-k0（=6）がRAM１０４の数の倍数であるので、並べ替え回路１０１は並び替えを行わず、サイクリックシフト回路１０２に供給する。n0-k0の数がRAM１０４の数の倍数ではない場合については、後述する図２２乃至図２９を参照して説明する。
【０１４１】
サイクリックシフト回路１０２には、制御部１０５からサイクリックシフトの量を表す制御信号D106が供給され、サイクリックシフト回路１０２は、その制御信号D106に基づいて、並べ替え回路１０１からの積D101をサイクリックシフトし、サイクリックシフト後の６ビット単位の積D101を、積D102として加算器１０３に供給する。
【０１４２】
加算器１０３は、サイクリックシフト回路１０２からの６ビットの積D102とRAM１０４からの６ビットの和D103との排他的論理和をビット毎に求め、その結果得られる６ビットの値を和D104としてRAM１０４に供給する。
【０１４３】
RAM１０４のビット数は６（=P）であり、ワード数は６（=n0-k0）である。RAM１０４は、ビット数が２（=6/3）、ワード数が６（=n0-k0）の３つの独立に制御可能なRAM１０４−１乃至１０４−３から構成され、RAM１０４には、制御部１０５から、データの読み出しまたは書き込みを行うアドレスを指定する制御信号D107が供給される。RAM１０４は、その制御信号D107に基づいて、加算器１０３からの和D104を６ビット単位で記憶したり、既に記憶している和D104を６ビットまたは２ビット単位で読み出す。
【０１４４】
なお、RAM１０４は、３つのRAM１０４−１乃至１０４−３から構成されるため、RAM１０４−１乃至１０４−３の所定のアドレスから同時に（パラレルに）和D104を読み出したり、RAM１０４−１乃至１０４−３の所定のアドレスに同時に和D104を記憶させることができる。RAM１０４は、６ビット単位で読み出した和D104を、和D103として加算器１０３に供給したり、２ビット単位で読み出した和D104を、和D17としてアキュムレータ１６に供給する。
【０１４５】
また、RAM１０４が３つのRAM１０４−１乃至１０４−３から構成される場合の、１つのRAMで構成される場合と比べたRAM１０４の回路規模の増大は、無視できる程度に小さい。
【０１４６】
制御部１０５は、図８の制御部１８と同様に、制御信号D21をサイクリックシフト回路１２に、選択信号D23をアキュムレータD23に、選択信号D24をセレクタ１７に供給する。また、制御部１０５は、符号語ｃのn0-k0とRAM１０４を構成するRAM１０４−１乃至１０４−３の数とに応じて、並べ替えを制御する制御信号D105を生成し、並べ替え回路105に供給する。さらに、制御部１０５は、RAM１０４のビット数と、積D102を記憶させるRAM１０４のアドレス番号とに応じて、サイクリックシフト量を表す制御信号D106を生成し、サイクリックシフト回路１０２に供給する。
【０１４７】
図１９を参照して、図１８のサイクリックシフト回路１０２が行うサイクリックシフトの量について説明する。
【０１４８】
なお、以下では、積D13としてサイクリックシフト回路１２から出力される検査行列H´の上からv番目の構成行列の上からw行目と０番ベクトルのそれぞれとの積を、ｄw,vとも表す。
【０１４９】
制御部１０５は、各RAM１０４−１乃至１０４−３のビット数ｙ（いまの場合、２）と、積D102（D101）を記憶させるRAMのアドレス番号（0,1,・・・, n0-k0-1）とに基づいて、サイクリックシフトの量をy×0,y×1,y×2,・・・,y×（n0-k0-1）（mod P）の順に繰り返し設定し、そのサイクリックシフトの量を表す制御信号D106を生成して、サイクリックシフト回路１０２に供給する。いまの場合、ビット数ｙは２であるので、制御部１０５は、サイクリックシフトの量を0,2,4,0,2,4の順に繰り返し設定する。
【０１５０】
即ち、図１９に示すように、サイクリックシフト回路１０２は、サイクリックシフト回路１２から並べ替え回路１０１を介して供給される６ビットの積D101の、ｄ0,0乃至ｄ5,0をサイクリックシフトせずに、積D102として加算器１０３に出力する。即ち、ｄ0,0乃至ｄ5,0のサイクリックシフト量は０である。
【０１５１】
また、サイクリックシフト回路１０２は、サイクリックシフト回路１２から並べ替え回路１０１を介して供給される６ビットの積D101の、ｄ0,1乃至ｄ5,1を２つだけサイクリックシフトし、積D102として加算器１０３に出力する。即ち、加算器１０３から、ｄ4,1,ｄ5,1,ｄ0,1,ｄ1,1,ｄ2,1,ｄ3,1の順に並んだ６ビットの積D102が加算器１０３に供給される。
【０１５２】
さらに、サイクリックシフト回路１０２は、サイクリックシフト回路１２から並べ替え回路１０１を介して供給される６ビットの積D101の、ｄ0,2乃至ｄ5,2を４つだけサイクリックシフトし、積D102として加算器１０３に出力する。即ち、加算器１０３から、ｄ2,2,ｄ3,2,ｄ4,2,ｄ5,2,ｄ0,2,ｄ1,2の順に並んだ６ビットの積D102が加算器１０３に供給される。
【０１５３】
以降、同様にして、サイクリックシフトの量が0,2,4の順に設定され、ｄ0,2乃至ｄ5,2,ｄ0,2乃至ｄ5,2,ｄ0,2乃至ｄ5,2のサイクリックシフトが行われる。
【０１５４】
図１９では、検査行列H´の上からv番目の構成行列の上からw行目と０番ベクトルのそれぞれとの積であるｄw,vの場合について説明したが、検査行列H´の上からv番目の構成行列の上からw行目と１乃至１１番ベクトルのそれぞれとの積D101についても同様にサイクリックシフトが行われる。
【０１５５】
次に、図２０を参照して、図１８のRAM１０４に記憶される和D104について説明する。
【０１５６】
図１９に示したように、まず最初に、RAM１０４には、サイクリックシフト回路１０２から加算器１０３を介して、０番ベクトルと検査行列H´の上から０番目の構成行列とのｄ0,0乃至ｄ5,0が６ビットの和D104として供給される。RAM１０４は、図２０に示すように、制御信号D107に基づいて、その和D104の各ビットをRAM１０４−１乃至１０４−３の０番アドレスに順に記憶する。具体的には、RAM１０４−１の０ビット目にはｄ0,0、１ビット目にはｄ1,0が記憶され、RAM１０４−２の０ビット目にはｄ2,0、１ビット目にはｄ3,0が記憶される。また、RAM１０４−３の０ビット目にはｄ4,0、１ビット目にはｄ5,0が記憶される。以降、同様にして、RAM１０４は、制御信号D107に基づいて、その和D104をRAM１０４−１乃至１０４−３の１乃至５番アドレスに順に記憶する。
【０１５７】
また、RAM１０４は、RAM１０４−１乃至１０４−３の０番アドレスの０と１ビット目に記憶されているｄ0,0乃至ｄ5,0を読み出し、６ビットの和D103として加算器１０３に供給する。以降、同様にして、RAM１０４−１乃至１０４−３の１乃至５番アドレスに記憶されている６ビットの和D104をそれぞれ読み出し、和D103として加算器１０３に供給する。
【０１５８】
加算器１０３は、RAM１０４から６ビットの和D103として供給される０番ベクトルと検査行列H´の上から０番目の構成行列との積であるｄ0,0乃至ｄ5,0と、サイクリックシフト回路１０２から供給される１番ベクトルと検査行列H´の上から０番目の構成行列との積とをEXOR演算し、その結果得られる和D104をRAM１０４に供給する。RAM１０４のRAM１０４−１乃至１０４−３は、その和D104の各ビットを０番アドレスに順に記憶する。即ち、RAM１０４−１乃至１０４−３は、０番アドレスを更新する。以降、同様にして、RAM１０４−１乃至１０４−３は、１乃至５番アドレスも更新する。
【０１５９】
そして、同様の処理が繰り返され、RAM１０４−１の０番アドレスの０ビット目には、検査行列H´の上から０番目の構成行列の上から０行目と０乃至１１番ベクトルのそれぞれとの積であるｏ0,0が記憶される。また、RAM１０４−１の０番アドレスの１ビット目にｏ1,0が記憶され、RAM１０４−２の０番アドレスの０ビット目にｏ2,0、１ビット目にｏ3,0が記憶される。また、RAM１０４−３の０番アドレスの０ビット目にｏ4,0、１ビット目にｏ5,0が記憶される。
【０１６０】
また、同様に、RAM１０４−１乃至１０４−３の１番アドレスには、ｏ4,1,ｏ5,1,ｏ0,1,ｏ1,1,ｏ2,1,ｏ3,1が、２番アドレスには、ｏ2,2,ｏ3,2,ｏ4,2,ｏ5,2,ｏ0,2,ｏ1,2が、RAM１０４の３番アドレスには、ｏ0,3,ｏ1,3,ｏ2,3,ｏ3,3,ｏ4,3,ｏ5,3が、RAM１０４の４番アドレスには、ｏ4,4,ｏ5,4,ｏ0,4,ｏ1,4,ｏ2,4,ｏ3,4が、５番アドレスには、ｏ2,5,ｏ3,5,ｏ4,5,ｏ5,5,ｏ0,5,ｏ1,5が記憶される。
【０１６１】
また、RAM１０４は、制御信号D107に基づいて、既に記憶されているｏ0,0乃至ｏ5,5を、検査行列Hの１行目に対応するものから順に読み出す。具体的には、まず最初に、RAM１０４は、RAM１０４−１の０番アドレスの０ビット目に記憶されているｏ0,0とRAM１０４−２の１番アドレスの１ビット目に記憶されているｏ0,1とを読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１６２】
次に、RAM１０４は、RAM１０４−３の２番アドレスの０ビット目に記憶されているｏ0,2とRAM１０４−１の３番アドレスの０ビット目に記憶されているｏ0,3とを読み出し、２ビットの和D17としてアキュムレータ１６に供給する。そして、RAM１０４は、RAM１０４−２の４番アドレスの０ビット目に記憶されているｏ0,4とRAM１０４−３の５番アドレスの０ビット目に記憶されているｏ0,5とを読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１６３】
また、RAM１０４は、RAM１０４−１の０番アドレスの１ビット目に記憶されているｏ1,0、RAM１０４−２の１番アドレスの１ビット目に記憶されているｏ1,1、RAM１０４−３の２番アドレスの１ビット目に記憶されているｏ1,2、RAM１０４−１の３番アドレスの１ビット目に記憶されているｏ1,3、RAM１０４−２の４番アドレスの１ビット目に記憶されているｏ1,4、RAM１０４−３の５番アドレスの１ビット目に記憶されているｏ1,5を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１６４】
次に、RAM１０４は、RAM１０４−２の０番アドレスの０ビット目に記憶されているｏ2,0、RAM１０４−３の１番アドレスの０ビット目に記憶されているｏ2,1、RAM１０４−１の２番アドレスの０ビット目に記憶されているｏ2,2、RAM１０４−２の３番アドレスの０ビット目に記憶されているｏ2,3、RAM１０４−３の４番アドレスの０ビット目に記憶されているｏ2,4、RAM１０４−１の５番アドレスの０ビット目に記憶されているｏ2,5を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１６５】
また、RAM１０４は、RAM１０４−２の０番アドレスの１ビット目に記憶されているｏ3,0、RAM１０４−３の１番アドレスの１ビット目に記憶されているｏ3,1、RAM１０４−１の２番アドレスの１ビット目に記憶されているｏ3,2、RAM１０４−２の３番アドレスの１ビット目に記憶されているｏ3,3、RAM１０４−３の４番アドレスの１ビット目に記憶されているｏ3,4、RAM１０４−１の５番アドレスの１ビット目に記憶されているｏ3,5を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１６６】
次に、RAM１０４は、RAM１０４−３の０番アドレスの０ビット目に記憶されているｏ4,0、RAM１０４−１の１番アドレスの０ビット目に記憶されているｏ4,1、RAM１０４−２の２番アドレスの０ビット目に記憶されているｏ4,2、RAM１０４−３の３番アドレスの０ビット目に記憶されているｏ4,3、RAM１０４−１の４番アドレスの０ビット目に記憶されているｏ4,4、RAM１０４−２の５番アドレスの０ビット目に記憶されているｏ4,5を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１６７】
また、RAM１０４は、RAM１０４−３の０番アドレスの１ビット目に記憶されているｏ5,0、RAM１０４−１の１番アドレスの１ビット目に記憶されているｏ5,1、RAM１０４−２の２番アドレスの１ビット目に記憶されているｏ5,2、RAM１０４−３の３番アドレスの１ビット目に記憶されているｏ5,3、RAM１０４−１の４番アドレスの１ビット目に記憶されているｏ5,4、RAM１０４−２の５番アドレスの１ビット目に記憶されているｏ5,5を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１６８】
上述した図１９に示すように、サイクリックシフト回路１０２が、積D101をサイクリックシフトするので、RAM１０４が同時に読み出す２ビットの和D104を、異なるRAM１０４−１乃至１０４−３に記憶させることができる。これにより、ワード方向に読み出すことができないRAM１０４において、実質的にワード方向に読み出すことができる。例えば、２ビットの和D104として同時に読み出すｏ0,0とｏ0,1は、ワード方向に並べて記憶されるが、それぞれ異なるRAM１０４−１または１０４−２に記憶されているので、同時に読み出すことができる。
【０１６９】
その結果、RAM１０４のビット方向に検査行列H´の０行目から順に和D104として記憶される、検査行列H´の情報部の各行と情報語ｉの積を、検査行列Hの０行目に対応する積から順に読み出すことができる。
【０１７０】
次に、図２１を参照して、図１８の符号化装置１による符号化処理を説明する。この符号化処理は、例えば、情報語D11（情報語ｉ）が２ビット単位で入力されたとき、開始される。
【０１７１】
ステップＳ２１乃至Ｓ２３は、図１７のステップＳ１乃至Ｓ３と同様の処理であるので、説明は省略する。
【０１７２】
ステップＳ２３の処理後は、ステップＳ２４に進み、並べ替え回路１０１は、制御部１０５からの制御信号D105に基づいて、ステップＳ２３でサイクリックシフト回路１２から供給される６ビットの積D13の並び替えを行い、並び替え後の積D13を、積D101としてサイクリックシフト回路１０２に供給する。
【０１７３】
ステップＳ２４の処理後は、ステップＳ２５に進み、サイクリックシフト回路１０２は、制御部１０５からの制御信号D106に基づいて、並べ替え回路１０１からの積D101をサイクリックシフトし、サイクリックシフト後の６ビット単位の積D101を、積D102として加算器１０３に供給する。
【０１７４】
ステップＳ２５の処理後は、ステップＳ２６に進み、加算器１０３は、サイクリックシフト回路１０２からの６ビットの積D102と、後述するステップＳ２７でRAM１０４から供給される６ビットの和D103との排他的論理和をビット毎に求め、その結果得られる６ビットの値を和D104としてRAM１０４に供給し、ステップＳ２７に進む。
【０１７５】
ステップＳ２７において、RAM１０４は、制御部１０５からの制御信号D107に基づいて、加算器１０３からの和D104を６ビット単位で記憶したり、既に記憶している和D104を６ビットまたは２ビット単位で読み出す。RAM１０４は、６ビット単位で読み出した和D104を、和D103として加算器１０３に供給したり、２ビット単位で読み出した和D104を、和D17としてアキュムレータ１６に供給する。
【０１７６】
ステップＳ２８乃至Ｓ３１の処理は、ステップＳ６,Ｓ７，Ｓ９、およびＳ１０の処理と同様であるので、説明は省略する。
【０１７７】
次に、図２２は、LDPC符号化に用いる検査行列Hの他の例を示している。
【０１７８】
図２２の検査行列Hは、n=102，k=72の符号語ｃ（符号化率12/17、符号長102）を得るための検査行列Hであり、３０(行)×１０２（列）の行列である。即ち、検査行列Hは、３０（=n-k）行７２（=k）列の情報部と、３０(=n-k)行３０（=n-k）列のパリティ部とから構成される。図２２の検査行列Hを行置換または列置換すると、図２３に示す検査行列H´になる。図２３の検査行列H´では、情報部を、構成行列の組み合わせで表すことができる。
【０１７９】
次に、図２４と図２５を参照して、図２２の検査行列Hを用いて図１８の符号化装置１がLDPC符号化を行う場合の、並べ替え回路１０１、サイクリックシフト回路１０２、およびRAM１０４における処理について説明する。
【０１８０】
まず最初に、図２４を参照して、並べ替え回路１０１とサイクリックシフト回路１０２の処理について説明する。
【０１８１】
図２４に示すように、並び替え回路１０１には、まず最初に、サイクリックシフト回路１２から、６ビットの積であるｄ0,0乃至ｄ5,0，ｄ0,1乃至ｄ5,1，ｄ0,2乃至ｄ5,2，ｄ0,3乃至ｄ5,3，ｄ0,4乃至ｄ5,4，ｄ0,5乃至ｄ5,5が、それぞれ順に積D13として供給される。
【０１８２】
ここで、n0-k0（=(n-k)/P=30/6）は５であり、RAM１０４−１乃至１０４−３の数である３の倍数ではなく、３で除算した結果余りが２となる。このように、n0-k0が、RAM１０４−１乃至１０４−３の倍数ではなく、３で除算した結果余りが２である場合、RAM１０４において、検査行列H´の情報部の各行と情報語ｉの積を、検査行列Hの０行目に対応する積から順に読み出すために、並べ替え回路１０１は、次のように並び替えを行う。
【０１８３】
並び替え回路１０１は、積D13の０ビット目を積D101の０ビット目に、積D13の３ビット目を積D101の１ビット目に、積D13の２ビット目を積D101の２ビット目に、積D13の５ビット目を積D101の３ビット目に、積D13の１ビット目を積D101の４ビット目に、積D13の４ビット目を積D101の５ビット目に並び替え、６ビットの積D101をサイクリックシフト回路１０２に供給する。
【０１８４】
例えば、並び替え回路１０１は、図２４に示すように、６ビットのｄ0,0乃至ｄ5,0を、ｄ0,0，ｄ3,0，ｄ2,0，ｄ5,0，ｄ1,0，ｄ4,0の順に並び替え、積D101としてサイクリックシフト回路１０２に供給する。また、並び替え回路１０１は、図２４に示すように、６ビットのｄ0,1乃至ｄ5,1を、ｄ0,1，ｄ3,1，ｄ2,1，ｄ5,1，ｄ1,1，ｄ4,1の順に並び替え、積D101としてサイクリックシフト回路１０２に供給する。
【０１８５】
図２４に示すように、制御部１０５は、サイクリックシフトの量をy×0,y×1,y×2,・・・,y×（n0-k0-1）（mod P）の順、即ち0,2,4,0,2の順に繰り返し設定し、そのサイクリックシフトの量を表す制御信号D106を生成して、サイクリックシフト回路１０２に供給する。
【０１８６】
サイクリックシフト回路１０２は、制御部１０５からの制御信号D106に基づいて、例えば、並べ替え回路１０１から６ビットの積D101として供給される、ｄ0,0，ｄ3,0，ｄ2,0，ｄ5,0，ｄ1,0，ｄ4,0をサイクリックシフトせずに、積D102として加算器１０３に出力する。即ち、ｄ0,0乃至ｄ5,0のサイクリックシフト量は０である。
【０１８７】
なお、検査行列H´の上からv番目の構成行列の上からw行目と１乃至１１番ベクトルのそれぞれとの積D101についても同様に並べ替えとサイクリックシフトが行われる。
【０１８８】
次に、図２５を参照して、RAM１０４の処理について説明する。
【０１８９】
RAM１０４は、図２０の場合と同様に、制御信号D107に基づいて、加算器１０３から供給される６ビットの和D104の記憶（更新）と読み出しを繰り返し、最終的に、RAM１０４には、図２５に示すように、ｏ0,0乃至ｏ5,4が記憶される。
【０１９０】
例えば、RAM１０４−１の０番アドレスの０ビット目には、ｏ0,0が、RAM１０４−１の０番アドレスの１ビット目にｏ3,0が記憶される。また、RAM１０４−２の０番アドレスの０ビット目にｏ2,0、１ビット目にｏ5,0が記憶される。さらに、RAM１０４−３の０番アドレスの０ビット目にｏ1,0、１ビット目にｏ4,0が記憶される。
【０１９１】
また、RAM１０４は、図２０の場合と同様に、制御信号D107に基づいて、既に記憶されているｏ0,0乃至ｏ5,4を、検査行列Hの１行目に対応するものから順に読み出す。
【０１９２】
具体的には、まず最初に、RAM１０４は、RAM１０４−１の０番アドレスの０ビット目に記憶されているｏ0,0とRAM１０４−２の１番アドレスの１ビット目に記憶されているｏ0,1とを読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１９３】
次に、RAM１０４は、RAM１０４−３の２番アドレスの０ビット目に記憶されているｏ0,2とRAM１０４−１の３番アドレスの０ビット目に記憶されているｏ0,3とを読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１９４】
また、RAM１０４は、RAM１０４−２の４番アドレスの０ビット目に記憶されているｏ0,4、RAM１０４−３の０番アドレスの０ビット目に記憶されているｏ1,0、RAM１０４−１の１番アドレスの０ビット目に記憶されているｏ1,1、RAM１０４−２の２番アドレスの０ビット目に記憶されているｏ1,2、RAM１０４−３の３番アドレスの０ビット目に記憶されているｏ1,3、RAM１０４−１の４番アドレスの０ビット目に記憶されているｏ1,4を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１９５】
次に、RAM１０４は、RAM１０４−２の０番アドレスの０ビット目に記憶されているｏ2,0、RAM１０４−３の１番アドレスの０ビット目に記憶されているｏ2,1、RAM１０４−１の２番アドレスの０ビット目に記憶されているｏ2,2、RAM１０４−２の３番アドレスの０ビット目に記憶されているｏ2,3を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１９６】
また、RAM１０４は、RAM１０４−３の４番アドレスの０ビット目に記憶されているｏ2,4、RAM１０４−１の０番アドレスの１ビット目に記憶されているｏ3,0、RAM１０４−２の１番アドレスの１ビット目に記憶されているｏ3,1、RAM１０４−３の２番アドレスの１ビット目に記憶されているｏ3,2、RAM１０４−１の３番アドレスの１ビット目に記憶されているｏ3,3、RAM１０４−２の４番アドレスの１ビット目に記憶されているｏ3,4を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１９７】
次に、RAM１０４は、RAM１０４−３の０番アドレスの０ビット目に記憶されているｏ4,0、RAM１０４−１の１番アドレスの０ビット目に記憶されているｏ4,1、RAM１０４−２の２番アドレスの０ビット目に記憶されているｏ4,2、RAM１０４−３の３番アドレスの０ビット目に記憶されているｏ4,3を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１９８】
また、RAM１０４は、RAM１０４−１の４番アドレスの１ビット目に記憶されているｏ4,4、RAM１０４−２の０番アドレスの１ビット目に記憶されているｏ5,0、RAM１０４−３の１番アドレスの１ビット目に記憶されているｏ5,1、RAM１０４−１の２番アドレスの１ビット目に記憶されているｏ5,2、RAM１０４−２の３番アドレスの１ビット目に記憶されているｏ5,3、RAM１０４−３の４番アドレスの１ビット目に記憶されているｏ5,4を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０１９９】
上述した図２４に示すように、並び替え回路１０１が、積D13を並び替え、その並び替え後の積D101をサイクリックシフト回路１０２がサイクリックシフトするので、RAM１０４が同時に読み出す２ビットの和D104を、異なるRAM１０４−１乃至１０４−３に記憶させることができる。
【０２００】
次に、図２６は、LDPC符号化に用いる検査行列Hのさらに他の例を示している。
【０２０１】
図２６の検査行列Hは、n=96，k=72の符号語ｃ（符号化率3/4、符号長96）を得るための検査行列Hであり、２４(行)×９６（列）の行列である。即ち、検査行列Hは、２４（=n-k）行７２（=k）列の情報部と、２４(=n-k)行２４（=n-k）列のパリティ部とから構成される。図２６の検査行列Hを行置換または列置換すると、図２７に示す検査行列H´になる。図２７の検査行列H´では、情報部を、構成行列の組み合わせで表すことができる。次に、図２８と図２９を参照して、図２６の検査行列Hを用いて図１８の符号化装置１がLDPC符号化を行う場合の、並べ替え回路１０１、サイクリックシフト回路１０２、およびRAM１０４における処理について説明する。
【０２０２】
まず最初に、図２８を参照して、並べ替え回路１０１とサイクリックシフト回路１０２の処理について説明する。
【０２０３】
図２８に示すように、並び替え回路１０１には、サイクリックシフト回路１２から、６ビットのｄ0,0乃至ｄ5,0，ｄ0,1乃至ｄ5,1，ｄ0,2乃至ｄ5,2，ｄ0,3乃至ｄ5,3，ｄ0,4乃至ｄ5,4，ｄ0,5乃至ｄ5,5が、それぞれ順に積D13として供給される。
【０２０４】
ここで、n0-k0（=(n-k)/P=30/6）は４であり、RAM１０４−１乃至１０４−３の数である３の倍数ではなく、３で除算した結果余りが１となる。このように、n0-k0が、RAM１０４−１乃至１０４−３の倍数ではなく、３で除算した結果余りが１である場合、RAM１０４において、検査行列H´の情報部の各行と情報語ｉの積を、検査行列Hの０行目に対応する積から順に読み出すために、並べ替え回路１０１は、次のように並び替えを行う。
【０２０５】
並び替え回路１０１は、積D13の０ビット目を積D101の０ビット目に、積D13の３ビット目を積D101の１ビット目に、積D13の１ビット目を積D101の２ビット目に、積D13の４ビット目を積D101の３ビット目に、積D13の２ビット目を積D101の４ビット目に、積D13の５ビット目を積D101の５ビット目に並び替え、６ビットの積D101をサイクリックシフト回路１０２に供給する。
【０２０６】
例えば、並び替え回路１０１は、図２８に示すように、６ビットのｄ0,0乃至ｄ5,0を、ｄ0,0，ｄ3,0，ｄ1,0，ｄ4,0，ｄ2,0，ｄ5,0の順に並び替え、積D101としてサイクリックシフト回路１０２に供給する。また、並び替え回路１０１は、図２８に示すように、６ビットのｄ0,1乃至ｄ5,1を、ｄ0,1，ｄ3,1，ｄ1,1，ｄ4,1，ｄ2,1，ｄ5,1の順に並び替え、積D101としてサイクリックシフト回路１０２に供給する。
【０２０７】
図２８に示すように、制御部１０５は、サイクリックシフトの量をy×0,y×1,y×2,・・・,y×（n0-k0-1）（mod P）の順、即ち0,2,4,0の順に繰り返し設定し、そのサイクリックシフトの量を表す制御信号D106を生成して、サイクリックシフト回路１０２に供給する。
【０２０８】
例えば、図２８に示すように、サイクリックシフト回路１０２は、並べ替え回路１０１から６ビットの積D101として供給される、ｄ0,0，ｄ3,0，ｄ1,0，ｄ4,0，ｄ2,0，ｄ5,0をサイクリックシフトせずに、積D102として加算器１０３に出力する。即ち、ｄ0,0乃至ｄ5,0のサイクリックシフト量は０である。
【０２０９】
なお、検査行列H´の上からv番目の構成行列の上からw行目と１乃至１１番ベクトルのそれぞれとの積D101についても同様に並べ替えとサイクリックシフトが行われる。
【０２１０】
次に、図２９を参照して、RAM１０４の処理について説明する。
【０２１１】
RAM１０４は、図２０や図２５の場合と同様に、制御部１０５からの制御信号D107に基づいて、加算器１０３から供給される６ビットの和D104の記憶（更新）または読み出しを繰り返し、最終的に、RAM１０４には、図２９に示すように、ｏ0,0乃至ｏ5,3が記憶される。
【０２１２】
例えば、RAM１０４−１の０番アドレスの０ビット目にｏ0,0、１ビット目にｏ3,0が記憶される。また、RAM１０４−２の０番アドレスの０ビット目にｏ1,0、１ビット目にｏ4,0が記憶される。さらに、RAM１０４−３の０番アドレスの０ビット目にｏ2,0、１ビット目にｏ5,0が記憶される。
【０２１３】
また、RAM１０４は、図２０や図２５の場合と同様に、制御信号D107に基づいて、既に記憶されているｏ0,0乃至ｏ5,3を、検査行列Hの１行目に対応するものから順に読み出す。
【０２１４】
具体的には、まず最初に、RAM１０４は、RAM１０４−１の０番アドレスの０ビット目に記憶されているｏ0,0とRAM１０４−２の１番アドレスの０ビット目に記憶されているｏ0,1とを読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０２１５】
次に、RAM１０４は、RAM１０４−３の２番アドレスの０ビット目に記憶されているｏ0,2とRAM１０４−１の３番アドレスの０ビット目に記憶されているｏ0,3とを読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０２１６】
また、RAM１０４は、RAM１０４−２の０番アドレスの０ビット目に記憶されているｏ1,0、RAM１０４−３の１番アドレスの０ビット目に記憶されているｏ1,1、RAM１０４−１の２番アドレスの０ビット目に記憶されているｏ1,2、RAM１０４−２の３番アドレスの０ビット目に記憶されているｏ1,3を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０２１７】
次に、RAM１０４は、RAM１０４−３の０番アドレスの０ビット目に記憶されているｏ2,0、RAM１０４−１の１番アドレスの０ビット目に記憶されているｏ2,1、RAM１０４−２の２番アドレスの０ビット目に記憶されているｏ2,2、RAM１０４−３の３番アドレスの０ビット目に記憶されているｏ2,3を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０２１８】
また、RAM１０４は、RAM１０４−１の０番アドレスの１ビット目に記憶されているｏ3,0、RAM１０４−２の１番アドレスの１ビット目に記憶されているｏ3,1、RAM１０４−３の２番アドレスの１ビット目に記憶されているｏ3,2、RAM１０４−１の３番アドレスの１ビット目に記憶されているｏ3,3を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０２１９】
次に、RAM１０４は、RAM１０４−２の０番アドレスの１ビット目に記憶されているｏ4,0、RAM１０４−３の１番アドレスの１ビット目に記憶されているｏ4,1、RAM１０４−１の２番アドレスの１ビット目に記憶されているｏ4,2、RAM１０４−２の３番アドレスの１ビット目に記憶されているｏ4,3を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０２２０】
また、RAM１０４は、RAM１０４−３の０番アドレスの１ビット目に記憶されているｏ5,0、RAM１０４−１の１番アドレスの１ビット目に記憶されているｏ5,1、RAM１０４−２の２番アドレスの１ビット目に記憶されているｏ5,2、RAM１０４−３の３番アドレスの１ビット目に記憶されているｏ5,3を、この順に２個ずつ読み出し、２ビットの和D17としてアキュムレータ１６に供給する。
【０２２１】
上述した図２８に示すように、並び替え回路１０１が、積D13を並び替え、その並び替え後の積D101をサイクリックシフト回路１０２がサイクリックシフトするので、RAM１０４が同時に読み出す２ビットの和D104を、異なるRAM１０４−１乃至１０４−３に記憶させることができる。
【０２２２】
以上のようにしてRAM１０４から供給される和D17を用いて、アキュムレータ１６は、式（６）の演算を行い、その結果得られるパリティビットｐが、２ビット単位でパリティビットD18としてセレクタ１７を介して出力される。
【０２２３】
以上のように、符号化装置１によりLDPC符号化された結果得られる符号語ｃの復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、各列に対応するバリアブルノード(variable node（メッセージノード(message node)とも呼ばれる。）)と、各行に対応するチェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズム（サムプロダクトアルゴリズム（Sum Product Algorithm）によって行うことが可能である。
【０２２４】
このアルゴリズムでは、LDPC符号の符号語ｃが受信されると、チェックノードのメッセージ（値の"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値）が初期化され、その後、各行に対応するチェックノードの処理と、各列に対応するバリアブルノードの処理とが繰り返し行われることにより、復号が行われる。
【０２２５】
バリアブルノードの処理の結果得られる値のシンドロームが０である場合、または所定の回数チェックノードとバリアブルノードの処理が繰り返された場合、その時点でバリアブルノードの処理の結果得られた値が、復号結果として出力され、アルゴリズムが終了される。
【０２２６】
以上のように、図８の符号化装置１では、加算器１３が、６ビットの情報語D12と、その情報語D12に対応する検査行列Hの情報部との積を、６ビット単位で行ごとに積算し、その結果得られる和D15をRAM１４に記憶させ、アキュムレータ１６が、RAM１４から読み出された２ビットの和D16（D15）に対応する和D17を積算し、その結果得られる２ビットのパリティビットD18をLDPC符号の符号語ｃのパリティビットｐとして出力するので、線形符号の符号化の動作速度を変えることなく、符号化装置の回路規模を削減することができる。
【０２２７】
本実施の形態では、検査行列Hの情報部の列数kを102、構成行列の行数（または列数）Pを6としたが、情報部の列数kと構成行列の行数Pはこれに限定されない。例えば、符号化装置１は、情報語iの情報長が102より大きく、情報部の列数kが大きい検査行列Hにも適用可能であるし、6×6より大きい正方行列を構成行列として分割可能な検査行列Hにも適用可能である。
【０２２８】
また、本実施の形態では、RAM１０４のビット数を２、ワード数を６、個数を３としたが、ビット数、ワード数、および個数はこれに限定されず、自由度があるものとする。さらに、RAM１０４から同時に読み出し可能な和D104のビット数、または書き込み可能な和D104のビット数は、どのような値であってもよい。
【０２２９】
上述した説明では、LDPC符号が２元であるものとして説明したが、２元ではなく、１ビットを｛０，・・・，ｑ｝（ｑ＞１）で表す場合、アキュムレータ１６によるパリティビットｐの演算には、乗算と除算も必要となる。
【０２３０】
また、上述したサイクリックシフト回路１２と１０２として、バレルシフタを用いると回路規模を小さくすることができる。
【０２３１】
本発明は、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、線形符号の検査行列が、複数の構成行列の組み合わせで表される場合において適用することができる。
【０２３２】
また、本発明の効果は、情報語ｉの情報長が長い（大きい）場合に、より大きくなる。
【０２３３】
一般に、LDPC符号化に必要な計算量は少ないが、符号化装置１によるLDPC符号化においても、検査行列Hの要素に０が多い場合、計算量を著しく削減することができる。
【０２３４】
また、符号化装置１は、ベクトルと行列の積算を忠実に実装するものであるため、従来の符号化装置と異なる出力を出すことはない。
【０２３５】
本実施の形態では、LDPC符号への符号化について説明したが、本発明はLDPC符号だけでなく、その他の線形符号への符号化を行う符号化装置にも適用することができる。
【０２３６】
上述したLDPC符号を符号化する符号化装置１は、例えば、（ディジタル）衛星放送を送信する放送局の装置などに適用することができる。
【図面の簡単な説明】
【０２３７】
【図１】LDPC符号の検査行列Hを説明する図である。
【図２】パリティ部が下三角行列になっている検査行列Hを示す図である。
【図３】パリティ部が下三角行列になっている検査行列Hを示す図である。
【図４】LDPC符号化に用いる検査行列Hの例を示す図である。
【図５】図４の検査行列Hを行置換または列置換した後の検査行列H´を示す図である。
【図６】図４の検査行列Hを行置換または列置換した後の検査行列H´を示す図である。
【図７】図４の検査行列Hと図５や図６の検査行列H´のパリティ部を示す図である。
【図８】本発明を適用した符号化装置の第１実施の形態の構成例を示すブロック図である。
【図９】図８のサイクリックシフト回路が行うサイクリックシフトの量について説明する図である。
【図１０】図８のRAMに記憶される和について説明する図である。
【図１１】図８のRAMに記憶される和について説明する図である。
【図１２】図８のサイクリックシフト回路が行うサイクリックシフトの量について説明する図である。
【図１３】図１２のインターリーバにおけるデータの入出力を説明するタイミングチャートである。
【図１４】図８のアキュムレータの詳細構成例を示す図である。
【図１５】図１４のアキュムレータで行われるパリティビットpの演算について説明する図である。
【図１６】図１４のアキュムレータで行われるパリティビットpの演算について説明する図である。
【図１７】図８の符号化装置による符号化処理を説明するフローチャートである。
【図１８】本発明を適用した符号化装置１の第２の実施の形態の構成例を示すブロック図である。
【図１９】図１８のサイクリックシフト回路が行うサイクリックシフトの量について説明する図である。
【図２０】図１８のRAMに記憶される和について説明する図である。
【図２１】図１８の符号化装置による符号化処理を説明するフローチャートである。
【図２２】LDPC符号化に用いる検査行列Hの他の例を示す図である。
【図２３】図２２の検査行列Hを行置換または列置換した後の検査行列H´を示す図である。
【図２４】図２２の検査行列Hを用いてLDPC符号化を行う場合の処理について説明する図である。
【図２５】図２２の検査行列Hを用いてLDPC符号化を行う場合の処理について説明する図である。
【図２６】LDPC符号化に用いる検査行列Hのさらに他の例を示す図である。
【図２７】図２６の検査行列Hを行置換または列置換した後の検査行列H´を示す図である。
【図２８】図２６の検査行列Hを用いてLDPC符号化を行う場合の処理について説明する図である。
【図２９】図２６の検査行列Hを用いてLDPC符号化を行う場合の処理について説明する図である。
【符号の説明】
【０２３８】
１  符号化装置,  １１  ビット幅回路,  １２  サイクリックシフト回路,  １３  加算器,  １４  RAM,  １５  インターリーバ,  １６  アキュムレータ,  １７  セレクタ,  １８  制御部,  １０１  並べ替え回路,  １０２  サイクリックシフト回路,  １０３  加算器,  １０４  RAM,  １０５  制御部
【図１】
2006304132.tif 000010
【図２】
2006304132.tif 000011
【図３】
2006304132.tif 000012
【図４】
2006304132.tif 000013
【図５】
2006304132.tif 000014
【図６】
2006304132.tif 000015
【図７】
2006304132.tif 000016
【図８】
2006304132.tif 000017
【図９】
2006304132.tif 000018
【図１０】
2006304132.tif 000019
【図１１】
2006304132.tif 000020
【図１２】
2006304132.tif 000021
【図１３】
2006304132.tif 000022
【図１４】
2006304132.tif 000023
【図１５】
2006304132.tif 000024
【図１６】
2006304132.tif 000025
【図１７】
2006304132.tif 000026
【図１８】
2006304132.tif 000027
【図１９】
2006304132.tif 000028
【図２０】
2006304132.tif 000029
【図２１】
2006304132.tif 000030
【図２２】
2006304132.tif 000031
【図２３】
2006304132.tif 000032
【図２４】
2006304132.tif 000033
【図２５】
2006304132.tif 000034
【図２６】
2006304132.tif 000035
【図２７】
2006304132.tif 000036
【図２８】
2006304132.tif 000037
【図２９】
2006304132.tif 000038