(57)【要約】【課題】  回路規模を増加することなく、低密度パリティ検査符号の検査行列の復号処理時間を短縮する。【解決手段】  検査行列を行方向及び列方向に均等な複数の部分行列に分割する。各部分行列は、その四隅のいずれか一の隅部に位置する要素を基準とし、行方向及び列方向にそれぞれ所定数離れた各要素を結ぶ略三角形の領域内の全ての要素を零とする。行処理演算部１７は、各部分行列の基準となる隅部と同列の隅部に位置する要素を起算点として、所定の行処理を列方向に隣接する行毎に順次実行し、結果をデュアルポートメモリ部３に順次記憶する。列処理演算部２４は、行処理の実行終了が検知された列に対する行処理結果をデュアルポートメモリ部３から読み出し、所定の列処理を順次実行する。行処理と列処理とをオーバーラップさせることで処理時間を短縮する。【選択図】  図７
2007043635.tif 000002
【特許請求の範囲】
【請求項１】
検査行列により定義される低密度パリティ検査符号を復号する復号装置において、
前記検査行列を行方向及び列方向にそれぞれ均等な複数の部分行列に分割した後、当該各部分行列を、当該各部分行列の四隅のうちいずれか一の隅部に位置する要素を基準として、行方向及び列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ略三角形の領域内の全ての要素が零となるように構成しておき、
各前記部分行列の四隅のうち前記領域の基準となる隅部と同じ列の隅部に位置する要素を起算点として、所定の行処理を列方向に隣接する行ごとに順次実行する行処理手段と、
前記行処理手段による各行の行処理結果を順次記憶するメモリ手段と、
各前記部分行列の各列ごとに、前記領域外の全ての要素に対する前記行処理手段による行処理の実行終了時点を検知する行処理終了時点検知手段と、
各前記部分行列について、前記行処理終了時点検知手段により前記実行終了時点が検知された列ごとに、当該実行終了時点の検知タイミングに同期して前記メモリ手段から前記領域外の全ての行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する列処理手段と
を備えることを特徴とする復号装置。
【請求項２】
各前記部分行列を、当該各部分行列の四隅のうち同一部位の隅部に位置する要素を基準として、全ての要素が零となる前記領域を構成するようにした
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
各前記部分行列を、当該各部分行列の四隅のうち行方向及び列方向にそれぞれ同じ側の隅部に位置する要素を基準として、全ての要素が零となる前記領域を構成するようにした
ことを特徴とする請求項１に記載の復号装置。
【請求項４】
前記行処理終了時点検知手段は、前記領域内の階段状の単調変化に基づいて、当該領域外の全ての要素に対する行処理の実行終了時点を検知する
ことを特徴とする請求項１乃至請求項３のいずれか１項に記載の復号装置。
【請求項５】
前記メモリ手段は、前記行処理結果を順次記憶すると同時に、既に記憶されている前記行処理結果を順次読み出すデュアルポートメモリでなる
ことを特徴とする請求項１乃至請求項４のいずれか１項に記載の復号装置。
【請求項６】
前記検査行列は、基準とした前記いずれか一つの隅と対角に位置する隅を基準として、行方向および列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ第２の略三角形の領域内の全ての要素が零となるように構成されており、
前記列処理手段による各列の列処理演算結果を順次記憶する第２のメモリ手段と、
各前記部分行列の各行ごとに、前記第２の略三角形の領域以外の全ての要素に対する前記列処理手段による列処理の実行終了時点を検知する列処理終了時点検知手段とを備え、
前記行処理手段は、更に、
各前記部分行列について、前記列処理終了時点検知手段により前記列処理実行終了時点が検知された行ごとに、当該列処理の実行終了時点の検知タイミングに同期して前記第２のメモリ手段から前記第２の略三角形の領域以外の全ての列に対する列処理演算結果を読み出して、当該各列処理演算結果に基づく所定の行処理を順次実行する
ことを特徴とする請求項１に記載の復号装置。
【請求項７】
前記検査行列に含まれる前記略三角形および前記第２の略三角形の位置を、全ての部分行列において、同一となるように構成したことを特徴とする請求項６に記載の復号装置。
【請求項８】
前記検査行列に含まれる前記略三角形の基準となる隅部の位置を、行方向に同じ行および列方向に同じ列の隅部に位置する要素を基準として構成したことを特徴とする請求項６に記載の復号装置。
【請求項９】
前記行処理終了時点検知手段は、
前記略三角形の領域内の階段状の単調変化に基づいて、列ごとに、当該領域外の全ての要素に対する行処理の実行終了時点を検知し、
前記列処理終了時点検知手段は、
前記第２の略三角形の領域内の階段状の単調変化に基づいて、行ごとに、当該領域外の全ての要素に対する列処理の実行終了時点を検知することを特徴とする請求項６乃至請求項８のいずれか１項に記載の復号装置。
【請求項１０】
前記メモリ手段は、前記行処理結果を順次記憶すると同時に、既に記憶されている前記行処理結果を順次読み出すデュアルポートメモリでなり、
前記第２のメモリ手段は、
前記列処理演算結果を順次記憶すると同時に、既に記憶されている前記列処理演算結果を順次読み出すデュアルポートメモリでなる
ことを特徴とする請求項６乃至請求項９のいずれか１項に記載の復号装置。
【請求項１１】
検査行列により定義される低密度パリティ検査符号を復号する復号装置において、
前記検査行列を列方向に均等な複数の部分行列に分割した後、当該各部分行列を、各列ごとに列重みが１以下となるように構成しておき、
各前記部分行列の最端の列から行方向に隣接する列ごとに、当該部分行列の行数と同じ数の列数について、当該各列に零以外の要素が含まれるか否かを判断する要素判断手段と、
各前記部分行列ごとに、前記要素判断手段により列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて所定の行処理を順次実行する行処理手段と、
前記行処理手段による各行の行処理結果を順次記憶するメモリ手段と、
各前記部分行列の各列ごとに、前記要素判断手段により判断された零要素以外の要素に対する前記行処理手段による行処理の実行終了時点を検知する行処理終了時点検知手段と、
各前記部分行列について、前記行処理終了時点検知手段により前記実行終了時点の検知タイミングに同期して前記メモリ手段から前記要素判断手段により判断された零要素以外の要素を含む行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する列処理手段と
を備えることを特徴とする復号装置。
【請求項１２】
検査行列により定義される低密度パリティ検査符号を復号する復号方法において、
前記検査行列を行方向及び列方向にそれぞれ均等な複数の部分行列に分割した後、当該各部分行列を、当該各部分行列の四隅のうちいずれか一の隅部に位置する要素を基準として、行方向及び列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ略三角形の領域内の全ての要素が零となるように構成しておく第１のステップと、
各前記部分行列の四隅のうち前記領域の基準となる隅部と同じ列の隅部に位置する要素を起算点として、所定の行処理を列方向に隣接する行ごとに順次実行しながら、当該各行の行処理結果をメモリ手段に順次記憶する第２のステップと、
各前記部分行列の各列ごとに、前記領域外の全ての要素に対する前記行処理の実行終了時点を検知する第３のステップと、
各前記部分行列について、前記実行終了時点が検知された列ごとに、当該実行終了時点の検知タイミングに同期して前記メモリ手段から前記領域外の全ての行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する第４のステップと
を備えることを特徴とする復号方法。
【請求項１３】
各前記部分行列を、当該各部分行列の四隅のうち同一部位の隅部に位置する要素を基準として、全ての要素が零となる前記領域を構成するようにした
ことを特徴とする請求項１２に記載の復号方法。
【請求項１４】
各前記部分行列を、当該各部分行列の四隅のうち行方向及び列方向にそれぞれ同じ側の隅部に位置する要素を基準として、全ての要素が零となる前記領域を構成するようにした
ことを特徴とする請求項１２に記載の復号方法。
【請求項１５】
前記第３のステップでは、前記領域内の階段状の単調変化に基づいて、当該領域外の全ての要素に対する行処理の実行終了時点を検知する
ことを特徴とする請求項１２乃至請求項１４のいずれか１項に記載の復号方法。
【請求項１６】
前記第１のステップは、基準とした前記いずれか一つの隅と対角に位置する隅を基準として、行方向および列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ第２の略三角形の領域内の全ての要素が零となるように前記検査行列を構成する復号方法であって、
前記列処理手段による各列の列処理演算結果を順次第２のメモリ手段に記憶する第５のステップと、
各前記部分行列の各行ごとに、前記第２の略三角形の領域以外の全ての要素に対する前記列処理手段による列処理の実行終了時点を検知する第６のステップと、を含み、
前記第２のステップは、更に、
各前記部分行列について、前記列処理終了時点検知手段により前記列処理実行終了時点が検知された行ごとに、当該列処理の実行終了時点の検知タイミングに同期して前記第２のメモリ手段から前記第２の略三角形の領域以外の全ての列に対する列処理演算結果を読み出して、当該各列処理演算結果に基づく所定の行処理を順次実行する
ことを特徴とする請求項１２に記載の復号方法。
【請求項１７】
前記検査行列に含まれる前記略三角形および前記第２の略三角形の位置を、全ての部分行列において、同一となるように構成した
ことを特徴とする請求項１６に記載の復号方法。
【請求項１８】
前記検査行列に含まれる前記第１の三角形の基準となる隅部の位置を、行方向に同じ行および列方向に同じ列の隅部に位置する要素を基準として構成した
ことを特徴とする請求項１６に記載の復号方法。
【請求項１９】
前記第３のステップは、
前記略三角形の領域内の階段状の単調変化に基づいて、列ごとに、当該領域外の全ての要素に対する行処理の実行終了時点を検知し、
前記第６のステップは、
前記第２の略三角形の領域内の階段状の単調変化に基づいて、行ごとに、当該領域外の全ての要素に対する列処理の実行終了時点を検知することを特徴とする請求項１６乃至請求項１８のいずれか１項に記載の復号方法。
【請求項２０】
検査行列により定義される低密度パリティ検査符号を復号する復号方法において、
前記検査行列を列方向に均等な複数の部分行列に分割した後、当該各部分行列を、各列ごとに列重みが１以下となるように構成しておき、
各前記部分行列の最端の列から行方向に隣接する列ごとに、当該部分行列の行数と同じ数の列数について、当該各列に零以外の要素が含まれるか否かを判断する第１のステップと、
各前記部分行列ごとに、列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて所定の行処理を順次実行しながら、当該各行の行処理結果をメモリ手段に順次記憶する第２のステップと、
各前記部分行列の各列ごとに、前記判断された零要素以外の要素に対する行処理の実行終了時点を検知する第３のステップと、
各前記部分行列について、前記実行終了時点の検知タイミングに同期して前記メモリ手段から前記判断された零要素以外の要素を含む行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する第４のステップと
を備えることを特徴とする復号方法。
【請求項２１】
低密度パリティ検査符号を定義する検査行列を行方向及び列方向にそれぞれ均等な複数の部分行列に分割した後、当該各部分行列を、当該各部分行列の四隅のうちいずれか一の隅部に位置する要素を基準として、行方向及び列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ略三角形の領域内の全ての要素が零となるように構成しておく第１のステップと、
各前記部分行列の四隅のうち前記領域の基準となる隅部と同じ列の隅部に位置する要素を起算点として、所定の行処理を列方向に隣接する行ごとに順次実行しながら、当該各行の行処理結果をメモリ手段に順次記憶する第２のステップと、
各前記部分行列の各列ごとに、前記領域外の全ての要素に対する前記行処理の実行終了時点を検知する第３のステップと、
各前記部分行列について、前記実行終了時点が検知された列ごとに、当該実行終了時点の検知タイミングに同期して前記メモリ手段から前記領域外の全ての行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する第４のステップと
を実行させるための復号プログラム。
【請求項２２】
各前記部分行列を、当該各部分行列の四隅のうち同一部位の隅部に位置する要素を基準として、全ての要素が零となる前記領域を構成するようにした
ことを特徴とする請求項２１に記載の復号プログラム。
【請求項２３】
各前記部分行列を、当該各部分行列の四隅のうち行方向及び列方向にそれぞれ同じ側の隅部に位置する要素を基準として、全ての要素が零となる前記領域を構成するようにした
ことを特徴とする請求項２１に記載の復号プログラム。
【請求項２４】
前記第３のステップでは、前記領域内の階段状の単調変化に基づいて、当該領域外の全ての要素に対する行処理の実行終了時点を検知する
ことを特徴とする請求項２１乃至請求項２３のいずれか１項に記載の復号プログラム。
【請求項２５】
前記第１のステップは、基準とした前記いずれか一つの隅と対角に位置する隅を基準として、行方向および列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ第２の略三角形の領域内の全ての要素が零となるように前記検査行列を構成する復号プログラムであって、
前記列処理手段による各列の列処理演算結果を順次第２のメモリ手段に記憶する第５のステップと、
各前記部分行列の各行ごとに、前記第２の略三角形の領域以外の全ての要素に対する前記列処理手段による列処理の実行終了時点を検知する第６のステップと、を含み、
前記第２のステップは、更に、
各前記部分行列について、前記列処理終了時点検知手段により前記列処理実行終了時点が検知された行ごとに、当該列処理の実行終了時点の検知タイミングに同期して前記第２のメモリ手段から前記第２の略三角形の領域以外の全ての列に対する列処理演算結果を読み出して、当該各列処理演算結果に基づく所定の行処理を順次実行する
ことを特徴とする請求項２１に記載の復号プログラム。
【請求項２６】
前記検査行列に含まれる前記略三角形および前記第２の略三角形の位置を、全ての部分行列において、同一となるように構成した
ことを特徴とする請求項２５に記載の復号プログラム。
【請求項２７】
前記検査行列に含まれる前記第１の三角形の基準となる隅部の位置を、行方向に同じ行および列方向に同じ列の隅部に位置する要素を基準として構成した
ことを特徴とする請求項２５に記載の復号プログラム。
【請求項２８】
前記第３のステップは、
前記略三角形の領域内の階段状の単調変化に基づいて、列ごとに、当該領域外の全ての要素に対する行処理の実行終了時点を検知し、
前記第６のステップは、
前記第２の略三角形の領域内の階段状の単調変化に基づいて、行ごとに、当該領域外の全ての要素に対する列処理の実行終了時点を検知することを特徴とする請求項２５乃至請求項２７のいずれか１項に記載の復号プログラム。
【請求項２９】
低密度パリティ検査符号を定義する検査行列を列方向に均等な複数の部分行列に分割した後、当該各部分行列を、各列ごとに列重みが１以下となるように構成しておき、
各前記部分行列の最端の列から行方向に隣接する列ごとに、当該部分行列の行数と同じ数の列数について、当該各列に零以外の要素が含まれるか否かを判断する第１のステップと、
各前記部分行列ごとに、列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて所定の行処理を順次実行しながら、当該各行の行処理結果をメモリ手段に順次記憶する第２のステップと、
各前記部分行列の各列ごとに、前記判断された零要素以外の要素に対する行処理の実行終了時点を検知する第３のステップと、
各前記部分行列について、前記実行終了時点の検知タイミングに同期して前記メモリ手段から前記判断された零要素以外の要素を含む行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する第４のステップと
を実行させるための復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査符号の復号装置、復号方法および復号プログラムに関し、特に、データの高速伝送を行う伝送路において生ずるエラー訂正を行うのに好適な低密度パリティ検査符号の復号装置および復号方法に関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や無線ＬＡＮなどの通信分野の研究が急速に進められており、これに伴って、低密度パリティ検査符号などの誤り訂正技術の研究も盛んに行われている。
【０００３】
ここで、低密度パリティ検査（ＬＤＰＣ）符号（ＬＤＰＣ：Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅｓ）とは、行列内の「１」の要素の数が非常に少ない検査行列によって定義される線形符号をいう。また、ＬＤＰＣ符号は２元とは限らないが、以下においては、説明を簡略化するために２元のＬＤＰＣ符号について言及する。
【０００４】
ＬＤＰＣ符号の復号について、タナーグラフを用いて説明する。図２５に示すＭ行Ｎ列の検査行列Ｈに対するタナーグラフは、図２６に示すようにＮ個のビットノードとＭ個のチェックノードからなる。そして、検査行列Ｈにおいて「１」の要素の行、列に対応するノード間を線で結ぶ。ＬＤＰＣ符号の復号は、このようなタナーグラフにおけるビットノード、チェックノード間のメッセージのやり取りを繰り返すことで復号を行う。
【０００５】
次に、タナーグラフにおけるビットノード、チェックノード間のメッセージのやり取りについて説明する。検査行列Ｈのｍ行目、ｎ列目の要素をＨｍｎとする。また、ｍ行目において「１」となっている要素の列番号の集合Ｎ（ｍ）、およびｎ列目において「１」となっている要素の行番号の集合Ｍ（ｎ）を次式（１）ように定義する。
【０００６】
【数１】
2007043635.tif 000003
【０００７】
さらに、ビットノードｎからチェックノードｍへ送られるメッセージをＺｍｎ、チェックノードｍからビットノードへ送られるメッセージをＬｍｎと定義する。また、受信語からのメッセージをｙｎと定義する。
【０００８】
図２７に示すように、チェックノードｍからビットノードｎ１へ送られるメッセージＬｍｎ１は、当該チェックノードに結びついているビットノードのうち、当該メッセージが送られるビットノードを除く他のビットノードからのメッセージ（Ｚｍｎ２、Ｚｍｎ３）に基づいて演算される。このときの演算は次式（２）が適用される。
【０００９】
【数２】
2007043635.tif 000004
【００１０】
図２８に示すように、ビットノードｎからチェックノードｍ１へ送られるメッセージＺｍ１ｎは、当該ビットノードに結びついているチェックノードのうち、当該メッセージが送られるチェックノードを除く他のチェックノードからのメッセージ（Ｌｍ２ｎ、Ｌｍ３ｎ）に基づいて演算される。このときの演算は、次式（３）が適用される。
【００１１】
【数３】
2007043635.tif 000005
【００１２】
ＬＤＰＣ符号の復号処理では、これら全てのビットノードおよびチェックノードについて処理を繰り返し行う。
【００１３】
次に、復号処理の流れを、図２９を用いて説明する。
【００１４】
＜ステップ１＞（初期化）
反復回数をカウントするカウンタＴをＴ＝１に初期化する。また、Ｈｍｎ＝１である全ての要素に対して、Ｚｍｎ＝ｙｎで初期化する。
【００１５】
＜ステップ２＞（行処理）
このステップでは、チェックノードからビットノードへ送られるメッセージの演算を式（２）を用いて、全てのｍ、ｎについて行う。
【００１６】
＜ステップ３＞（列処理）
このステップでは、ビットノードからチェックノードへ送られるメッセージの演算を、式（３）を用いて、全てのｍ、ｎについて行う。また、一時推定語Ｃｎの演算を、次式（４）を用いて、全てのｍ、ｎについて行う。
【００１７】
【数４】
2007043635.tif 000006
【００１８】
＜ステップ４＞（反復回数判定）
このステップでは、カウンタＴ＜ｉｔであれば、カウンタＴをインクリメント＜ステップ４−１＞して、ステップ２の行処理に戻る。一方、カウンタＴ＝ｉｔであれば、復号処理を終了する。このようにステップ２の行処理からステップ３の列処理を複数回反復して行うことにより、受信した符号語に含まれるエラーを訂正する。
ここで、行処理および列処理の合計処理回数は、（Ｍ＋Ｎ）×ｉｔとなる。これを復号計算処理時間としてみると、図３０のようになる（例えば、非特許文献１参照）。
【非特許文献１】「低密度パリティ検査符号とその復号法  ＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｙ  Ｃｈｅｃｋ）符号／ｓｕｍ−ｐｒｏｄｕｃｔ復号法」」Ｐ２３〜Ｐ８２、トリケップス社発行、和田山  正著、２００２年６月５日発行
【発明の開示】
【発明が解決しようとする課題】
【００１９】
上記のように、従来の復号方法においては、例えば、検査行列Ｈの構成が図３１に示すようにＭ行Ｎ列に「１」をランダムに配列した場合、図中の○で囲った１行Ｎ列目の列処理が終わらないと、１行目の行処理を実行することができない。つまり、全ての列処理を行った後に、行処理を開始するために、復号処理に多大な時間を要するという問題があった。
【００２０】
また、列処理についても、図中の□で囲ったＭ行１列目の行処理が終わらないと、１列目の列処理を実行することができない、つまり、すべての行処理を行った後に、列処理を開始するために、列処理の観点においても、復号処理に多大な時間を要するという問題があった。
【００２１】
また、復号処理時間を短縮する方法として、図３２（ａ）のような非並列処理を図３２（ｂ）に示すように、検査行列Ｈをいくつかの部分行列に分割し、縦方向および横方向の分割数に対応した演算器を設けて行処理および列処理の並列処理を行うことにより処理時間の短縮を図る技術も提案されている。しかし、図３３に示すように、検査行列Ｈの分割数を増やせば増やすほど、処理時間の短縮は可能であるが、その分、演算器が増加することにより回路規模が大きくなるという問題がある。
【００２２】
そこで、本発明は、上述の問題点に鑑みてなされたものであり、回路規模を増加することなく、復号処理時間を短縮する低密度パリティ検査符号の復号装置および復号方法を提供することを目的とする。
【課題を解決するための手段】
【００２３】
上記課題を解決するために、本発明は以下の事項を提案している。
検査行列により定義される低密度パリティ検査符号を復号する復号装置において、検査行列を行方向及び列方向にそれぞれ均等な複数の部分行列に分割した後、当該各部分行列を、当該各部分行列の四隅のうちいずれか一の隅部に位置する要素を基準として、行方向及び列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ略三角形の領域内の全ての要素が零となるように構成しておき、各部分行列の四隅のうち領域の基準となる隅部と同じ列の隅部に位置する要素を起算点として、所定の行処理を列方向に隣接する行ごとに順次実行する行処理手段と、行処理手段による各行の行処理結果を順次記憶するメモリ手段と、各部分行列の各列ごとに、領域外の全ての要素に対する行処理手段による行処理の実行終了時点を検知する行処理終了時点検知手段と、各部分行列について、行処理終了時点検知手段により実行終了時点が検知された列ごとに、当該実行終了時点の検知タイミングに同期してメモリ手段から領域外の全ての行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する列処理手段とを備えることを特徴とする復号装置を提案する。
【００２４】
この復号装置においては、検査行列を構成する各部分行列ごとに、当該部分行列の各行について行処理を順次実行しながら、当該行処理結果を順次メモリ手段に記憶し、各部分行列内の各列ごとに、略三角形の領域外の全ての要素に対する行処理の実行終了時点の検知タイミングに同期して当該領域外の全ての行に対応する行処理結果をメモリ手段から読み出して、列処理を順次実行することにより、各部分行列ごとにメモリ手段への読み書きを同時に行う時間分だけ行処理と列処理とを並行させて実行することができる。
【００２５】
また検査行列により定義される低密度パリティ検査符号を復号する復号装置において、検査行列を列方向に均等な複数の部分行列に分割した後、当該各部分行列を、各列ごとに列重みが１以下となるように構成しておき、各部分行列の最端の列から行方向に隣接する列ごとに、当該部分行列の行数と同じ数の列数について、当該各列に零以外の要素が含まれるか否かを判断する要素判断手段と、各部分行列ごとに、要素判断手段により列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて所定の行処理を順次実行する行処理手段と、行処理手段による各行の行処理結果を順次記憶するメモリ手段と、各部分行列の各列ごとに、要素判断手段により判断された零要素以外の要素に対する行処理手段による行処理の実行終了時点を検知する行処理終了時点検知手段と、各部分行列について、行処理終了時点検知手段により実行終了時点の検知タイミングに同期してメモリ手段から要素判断手段により判断された零要素以外の要素を含む行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する列処理手段とを備えることを特徴とする復号装置を提案する。
【００２６】
この復号装置においては、検査行列を構成する各部分行列ごとに、要素判断手段により列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて行処理を順次実行しながら、当該行処理結果を順次メモリ手段に記憶し、各部分行列内の各列ごとに、要素判断手段により判断された零要素以外の要素を含む行に対する行処理の実行終了時点の検知タイミングに同期して当該零要素以外の要素を含む行に対応する行処理結果をメモリ手段から読み出して、列処理を順次実行することにより、各部分行列ごとにメモリ手段への読み書きを同時に行う時間分だけ行処理と列処理とを並行させて実行することができる。さらに検査行列を構成する要素が予めランダムに配置されて構成されている場合でも、行処理の実行順序を変えることにより、上述と同様に並列処理を行うことができると共に、検査行列に自由度を持たせることができる。
【００２７】
さらに検査行列により定義される低密度パリティ検査符号を復号する復号方法及び復号プログラムにおいて、検査行列を行方向及び列方向にそれぞれ均等な複数の部分行列に分割した後、当該各部分行列を、当該各部分行列の四隅のうちいずれか一の隅部に位置する要素を基準として、行方向及び列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶ略三角形の領域内の全ての要素が零となるように構成しておく第１のステップと、各部分行列の四隅のうち領域の基準となる隅部と同じ列の隅部に位置する要素を起算点として、所定の行処理を列方向に隣接する行ごとに順次実行しながら、当該各行の行処理結果をメモリ手段に順次記憶する第２のステップと、各部分行列の各列ごとに、領域外の全ての要素に対する行処理の実行終了時点を検知する第３のステップと、各部分行列について、実行終了時点が検知された列ごとに、当該実行終了時点の検知タイミングに同期してメモリ手段から領域外の全ての行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する第４のステップとを備えることを特徴とする復号方法及び復号プログラムを提案する。
【００２８】
この復号方法及び復号プログラムにおいては、検査行列を構成する各部分行列ごとに、当該部分行列の各行について行処理を順次実行しながら、当該行処理結果を順次メモリ手段に記憶し、各部分行列内の各列ごとに、略三角形の領域外の全ての要素に対する行処理の実行終了時点の検知タイミングに同期して当該領域外の全ての行に対応する行処理結果をメモリ手段から読み出して、列処理を順次実行することにより、各部分行列ごとにメモリ手段への読み書きを同時に行う時間分だけ行処理と列処理とを並行させて実行することができる。
【００２９】
検査行列により定義される低密度パリティ検査符号を復号する復号方法及び復号プログラムにおいて、検査行列を列方向に均等な複数の部分行列に分割した後、当該各部分行列を、各列ごとに列重みが１以下となるように構成しておき、各部分行列の最端の列から行方向に隣接する列ごとに、当該部分行列の行数と同じ数の列数について、当該各列に零以外の要素が含まれるか否かを判断する第１のステップと、各部分行列ごとに、列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて所定の行処理を順次実行しながら、当該各行の行処理結果をメモリ手段に順次記憶する第２のステップと、各部分行列の各列ごとに、判断された零要素以外の要素に対する行処理の実行終了時点を検知する第３のステップと、各部分行列について、実行終了時点の検知タイミングに同期してメモリ手段から判断された零要素以外の要素を含む行に対応する行処理結果を読み出して、当該各行処理結果に基づく所定の列処理を順次実行する第４のステップとを備えることを特徴とする復号方法及び復号プログラムを提案する。
【００３０】
この復号方法及び復号プログラムにおいては、検査行列を構成する各部分行列ごとに、列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて行処理を順次実行しながら、当該行処理結果を順次メモリ手段に記憶し、各部分行列内の各列ごとに、上記判断された零要素以外の要素を含む行に対する行処理の実行終了時点の検知タイミングに同期して当該零要素以外の要素を含む行に対応する行処理結果をメモリ手段から読み出して、列処理を順次実行することにより、各部分行列ごとにメモリ手段への読み書きを同時に行う時間分だけ行処理と列処理とを並行させて実行することができる。さらに検査行列を構成する要素が予めランダムに配置されて構成されている場合でも、行処理の実行順序を変えることにより、上述と同様に並列処理を行うことができると共に、検査行列に自由度を持たせることができる。
【発明の効果】
【００３１】
本発明によれば、検査行列を構成する各部分行列ごとに、当該部分行列の各行について行処理を順次実行しながら、当該行処理結果を順次メモリ手段に記憶し、各部分行列内の各列ごとに、略三角形の領域外の全ての要素に対する行処理の実行終了時点の検知タイミングに同期して当該領域外の全ての行に対応する行処理結果をメモリ手段から読み出して、列処理を順次実行するようにしたことにより、各部分行列ごとにメモリ手段への読み書きを同時に行う時間分だけ行処理と列処理とを並行させて実行することができ、かくして回路規模を増加することなく、低密度パリティ検査符号の復号処理時間を短縮することができる。
【００３２】
また本発明によれば、検査行列を構成する各部分行列ごとに、列単位で判断された零要素以外の要素が起算点となるように当該要素を含む行を優先させて行処理を順次実行しながら、当該行処理結果を順次メモリ手段に記憶し、各部分行列内の各列ごとに、上記判断された零要素以外の要素を含む行に対する行処理の実行終了時点の検知タイミングに同期して当該零要素以外の要素を含む行に対応する行処理結果をメモリ手段から読み出して、列処理を順次実行することにより、各部分行列ごとにメモリ手段への読み書きを同時に行う時間分だけ行処理と列処理とを並行させて実行するようにしたことにより、検査行列を構成する要素が予めランダムに配置されて構成されている場合でも、各部分行列ごとにメモリ手段への読み書きを同時に行う時間分だけ行処理と列処理とを並行させて実行することができると共に、検査行列に自由度を持たせることができ、かくして回路規模を増加することなく、低密度パリティ検査符号の復号処理時間を短縮することができる。
【発明を実施するための最良の形態】
【００３３】
以下、図面を用いて、本発明の実施形態に係る低密度パリティ検査符号の復号装置および復号方法について詳細に説明する。
＜第１実施形態＞
【００３４】
図１は、第１実施形態に係る低密度パリティ検査符号の検査行列Ｈの構成を示している。図１に示すように、第１実施形態に係る低密度パリティ検査符号の検査行列Ｈ（Ｍ行×Ｎ列）は、これを列方向にＰｍ分割、行方向にＰｎ分割した大きさＭ／Ｐｍ行、Ｎ／Ｐｎ列の部分行列（図中、Ｈｓｕｂ１１、Ｈｓｕｂ１２、・・・、ＨｓｕｂＰｍＰｎと示す。）により構成されている。ここで、Ｐｍは行処理の処理分割値と同じ値であり、Ｐｎは列処理の処理分割値と同じ値である。
【００３５】
図２は、第１実施形態に係る低密度パリティ検査符号の検査行列Ｈの構成の一例をより詳細に示したものである。図２に示される分割された部分行列は、図３（ａ）に示されるように、部分行列の４隅の要素のうち左下隅の要素と、この要素から行方向および列方向に同じ行数および列数（図３においては、Ｍｐと示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成をしている（以下、タイプ１と呼ぶ）。なお、図２に示す部分行列は一例であり、図３（ｂ）に示すように、部分行列の４隅の要素のうち左上隅の要素と、この要素から行方向および列方向に同じ行数および列数Ｍｐ離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成（以下、タイプ２と呼ぶ）、図３（ｃ）に示すように、部分行列の４隅の要素のうち右上隅の要素と、この要素から行方向および列方向に同じ行数および列数Ｍｐ離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成（以下、タイプ３と呼ぶ）図３（ｄ）に示すように、部分行列の４隅の要素のうち右下隅の要素と、この要素から行方向および列方向に同じ行数および列数Ｍｐ離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成（以下、タイプ４と呼ぶ）である部分行列を用いてもよい。また、図中、Ｍｐは、上記三角部の１辺の「０」が並ぶ行数を示し、Ｍｓは、部分行列の行数からＭｐを減じた行数であり、１以上の整数である。
【００３６】
図４は、図２に示す低密度パリティ検査符号の検査行列Ｈの復号処理演算に関するものである。なお、図４においては、説明を簡単にするために、各部分行列のＭｓを１行としている。図２に示す低密度パリティ検査符号の検査行列Ｈの場合、１ステップ目の演算処理では、図中斜線で示された各部分行列の先頭の行を同時並行的に計算する。この計算によって、各部分行列の先頭の行のビットノードがすべて計算されたことになる。ここで、各部分行列の１列目に着目すると、１行１列の要素を除いて、他の要素はすべて「０」である。したがって、１ステップ目の演算が終了すれば、１列目の列処理を行うための要素はすべて確定するため、１列目の演算を開始することができる。すなわち、２ステップ目の演算では、２行目（図中、黒塗りの部分）の演算と１列目の演算とをオーバーラップして処理できる。そして、２ステップ目以降の処理についても、行処理と列処理とを同時並行的にオーバーラップして処理することができる。そのため、復号処理計算に要する時間を図５のように短縮することができる。
【００３７】
以下、この復号装置の詳細を図６から図８を用いて、詳細に説明する。
第１実施形態における復号装置は、例えば、携帯電話機やＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ（Ｄａｔａ）Ａｓｓｉｓｔａｎｔｓ）のような受信装置に用いられるものであり、一般的に、図６に示すように、受信信号を復調する復調回路１０１と、第１実施形態の復号装置に相当する復調された信号を復号する復号回路１０２と、受信装置全体を制御するＣＰＵ１０３と、復号された映像信号あるいは音声信号を処理する映像／音声信号処理回路１０４と、信号処理された音声信号を外部に発音するスピーカ１０５と、信号処理された映像信号を表示するモニタ１０６等から構成されている。
【００３８】
第１実施形態の復号装置に相当する復号回路１０２は、図７に示すように、行計算統括処理部１と、列計算統括処理部２と、デュアルポートメモリ部（メモリ手段、デュアルポートメモリ）３と、行タイミング遅延部１４と、行処理演算部（行処理手段）１７と、出力バッファ１８と、Ｐ／Ｓ回路１９と、列処理演算部（列処理手段）２４と、列タイミング遅延部２５と、Ｓ／Ｐ回路２６、一時推定語演算部２７とから構成されており、行計算統括処理部１は、さらに、行計算制御部１１と、行番号カウンタ部１２と、行番号選択部１３とから、列計算統括処理部２は、列計算制御部（行処理終了時点検知手段）２１と、列番号カウンタ部２２と、列番号選択部２３とから、デュアルポートメモリ部（メモリ手段、デュアルポートメモリ）３は、行処理演算結果格納メモリ部１５と、列処理演算結果格納メモリ部１６とから構成されている。
【００３９】
ビットノード演算ブロック２８は、行タイミング遅延部１４と、行処理演算部１７とを備えている。ビットノード演算ブロック２８は、検査行列の行処理の分割数分（１〜Ｐｍ）存在する。また、チェックノード演算ブロック２９は、列タイミング遅延部２５と、列処理演算部２４と、一時推定語演算部２７とを備えている。チェックノード演算ブロック２９は、検査行列の列処理の分割数分（１〜Ｐｎ）存在する。
【００４０】
行計算制御部１１は、行番号カウンタ部１２に対する制御信号を生成する回路であり、行番号カウンタ部１２は、行計算制御部１１からの行カウント指示により、行番号アップカウンタまたは行番号ダウンカウンタを動作させ、カウント値をアップまたはダウンし、行カウンタクリア指示により、行カウンタを初期値にクリアする。
【００４１】
行番号選択部１３は、行番号カウンタ部１２からの出力に応じて、アップカウント値を使用するか、ダウンカウント値を使用するかを選択する。選択後、このカウント値を列処理演算結果格納メモリ部１６のリードアドレスおよび行処理演算結果格納メモリ部１５のライトアドレスとして使用する。また、行番号選択部１３は、使用している検査行列Ｈの部分行列のタイプに応じて選択するカウンタを決定する。例えば、図２に示す部分行列の場合には、アップカウンタを選択する。
【００４２】
行タイミング遅延部１４は、行処理にかかる処理時間に応じて、アドレスを遅延させる回路である。行処理演算結果格納メモリ部１５、列処理演算結果格納メモリ部１６は、行処理、列処理のオーバーラップ処理を実現するために、デュアルポートメモリにより構成されている。行処理演算部１７は、列処理演算結果格納メモリ部１６からリードした値に基づいて、新たなビットノードを計算し、その計算結果を行処理演算結果格納メモリ部１５へライトする。
【００４３】
行計算制御部１１は、列処理が開始可能となった時点で、列計算制御部２１へ列処理開始の指示を出す。列計算制御部２１は、行計算制御部１１からの上記列処理開始の指示を受けて、列番号カウンタ部２２に対する制御信号を生成する回路である。列番号カウンタ部２２は、列計算制御部２１からの列カウント指示により、列番号アップカウンタまたは列番号ダウンカウンタを動作させ、カウント値をアップまたはダウンし、列カウンタクリア指示により、列カウンタを初期値にクリアする。
【００４４】
列番号選択部２３は、列番号カウンタ部２２からの出力に応じて、アップカウント値を使用するか、ダウンカウント値を使用するかを選択する。選択後、このカウント値を列処理演算結果格納メモリ部１６のライトアドレスおよび行処理演算結果格納メモリ部１５のリードアドレスとして使用する。また、列番号選択部２３は、使用している検査行列Ｈの部分行列のタイプに応じて選択するカウンタを決定する。例えば、図２に示す部分行列の場合には、アップカウンタを選択する。
【００４５】
列タイミング遅延部２５は、列処理にかかる処理時間に応じて、アドレスを遅延させる回路である。列処理演算部２４は、行処理演算結果格納メモリ部１５からリードした値に基づいて、新たなチェックノードを計算し、その計算結果を列処理演算結果格納メモリ部１６へライトする。そして、列計算制御部２１は、すべての列処理が終了すると、行計算制御部１１に対して列処理終了信号を出す。一時推定語演算部２７は、行処理演算結果格納メモリ部１５から計算結果を読み出して、一時推定語を演算するとともに、一時推定語を出力バッファ１８を介して、Ｐ／Ｓ回路１９に出力する。
【００４６】
また、出力バッファ１８は、ＬＤＰＣによるエラー訂正後のデータを図６の映像／音声信号処理回路１０４に送信するための一時的な記憶手段である。これにより、行計算制御部１１の内部に設けられた反復回数カウンタを用いて行処理の反復回数をカウントしながら、確率精度が十分に高まった所定回数（例えば１０回）になったとき、制御信号を出力バッファ１８に送信することによって、出力バッファ１８から最終的な更新結果である復号後データを出力させる。Ｐ／Ｓ回路１９は、出力バッファ１８から入力したパラレルデータをシリアルデータに変換し、映像／音声信号処理回路１０４に出力する回路であり、Ｓ／Ｐ回路２６は、図６の復調回路１０１から入力したシリアルデータをパラレルデータに変換して列処理演算部２４等に供給する回路である。
【００４７】
次に、図８を用いて、第１実施形態に係る復号装置の復号方法について説明する。  行計算制御部１１は、符号語を受信すると処理を開始する（ステップ１０１）。行計算制御部１１は、まず、行番号カウンタ部１２に行カウント指示を出す（ステップ１０２）。行カウント指示を受け取った行番号カウンタ部１２は、行カウンタのアップダウンを開始する（ステップ１０３）。行計算制御部１１は、次に、ビットノードを計算するために、受信した符号語が初期値として格納されている列処理演算結果格納メモリ部１６をリードする。なお、このときのリードアドレスは、行番号カウンタ部１２から出力される（ステップ１０４）。
【００４８】
リードされたデータに基づいて、行処理演算部１７が新たなビットノードの計算処理を実行すると、行計算制御部１１が、その結果を行処理演算結果格納メモリ部１５へライトする。このときのライトアドレスは、行番号カウンタ部１２から出力されているカウンタ値を行タイミング遅延部１４において処理される計算時間に応じて遅延させた値を用いる（ステップ１０５）。
【００４９】
行計算制御部１１は、処理済行数カウンタのカウンタ値が予め設定されているＭｓ行数設定値と一致すると、列計算制御部２１に列処理の開始を指示する（ステップ１０６）。行計算制御部１１は、引き続き行処理を続行し、すべての行に対する計算を終了させる（ステップ１０７）。したがって、列計算制御部２１からの列処理の開始指示が出た後は、行処理と列処理の処理はオーバーラップするように実行される。その後、行計算制御部１１は、列計算制御部２１から列処理の計算終了信号を受信するまで処理を停止する（ステップ１０８）。
【００５０】
一方、列計算制御部２１は、行計算制御部１１からの列処理開始指示を受けて処理を開始する（ステップ１０９）。行計算制御部１１からの列処理開始指示を受けると、列計算制御部２１は、列番号カウンタ部２２に対して列カウント指示を出す（ステップ１１０）。列カウント指示を受け取った列番号カウンタ部２２は、列カウンタのアップダウンを開始する（ステップ１１１）。列計算制御部２１は、次に、チェックノードを計算するために、行処理演算結果格納メモリ部１５をリードする。なお、このときのリードアドレスは、列番号カウンタ部２２から計算に必要なデータが格納されているアドレスへ変更した後、出力される（ステップ１１２）。
【００５１】
リードされたデータに基づいて、列処理演算部２４が新たなチェックノードの計算処理を実行すると、列計算制御部２１が、その結果を列処理演算結果格納メモリ部１６へライトする。このときのライトアドレスは、列番号カウンタ部２２から出力されているリードアドレス値を列タイミング遅延部２５において処理される計算時間に応じて遅延させた値を用いる（ステップ１１３）。
【００５２】
列計算制御部２１は、繰り返し列処理を行い、すべての列に対する計算処理が終了すると、行計算制御部１１に列処理の終了信号を出力する（ステップ１１４）。列計算制御部２１は、列番号カウンタ部２２に列カウンタのクリア指示を出力する（ステップ１１５）。そして、列番号カウンタ部２２は、列カウンタのクリア指示を受けて、列カウンタを初期値にクリアする（ステップ１１６）。
【００５３】
ここまでの一連の処理で、１回目の復号処理が終了するため、行計算制御部１１は、行番号カウンタ部１２に行カウンタのクリア指示を出力する（ステップ１１７）。行番号カウンタ部１２は、行カウンタクリア指示を受けて、行カウンタを初期値にクリアする（ステップ１１８）。行計算制御部１１は、反復回数カウンタのカウンタ値が予め定められたカウンタ値ｉｔに達するまで、上記ステップ１０２からステップ１１８までの処理を繰り返し実行する（ステップ１１９）。そして、上記ステップ１０２からステップ１１８までの処理がｉｔ回実行されたところで、すべての処理を完了する（ステップ１２０）。
【００５４】
図９は、図８を用いて説明を行ったように、行処理と列処理とのオーバーラップ処理を実現するための行処理演算結果格納メモリ部１５および列処理演算結果格納メモリ部１６に対するアクセスタイミングを示すものである。図９から、列処理演算結果格納メモリ部１６のポートＡは、リードアクセス用に、列処理演算結果格納メモリ部１６のポートＢは、ライトアクセス用に使用される。また、行処理演算結果格納メモリ部１５のポートＡは、ライトアクセス用に、行処理演算結果格納メモリ部１５のポートＢは、リードアクセス用に使用される。
【００５５】
行処理実行時には、列処理演算結果格納メモリ部１６のポートＡからリードしたデータは、行処理を行ったのち、行処理演算結果格納メモリ部１５のポートＡを通してライトされる。一方、列処理実行時には、行処理演算結果格納メモリ部１５のポートＢからリードしたデータは、列処理を行ったのち、列処理演算結果格納メモリ部１６のポートＢを通してライトされる。このように、行処理演算結果格納メモリ部１５および列処理演算結果格納メモリ部１６としてデュアルポートメモリを使用することで行処理、列処理のオーバーラップ処理が実現できる。
【００５６】
なお、第１実施形態においては、検査行列Ｈを構成する部分行列として、図３（ａ）（タイプ１）の部分行列を用いる場合についてその処理等を説明したが、部分行列として、図３（ｂ）（タイプ２）の部分行列を用いる場合には、行番号選択部１３は、ダウンカウンタを選択し、列番号選択部２３は、アップカウンタを選択する。また、図３（ｃ）（タイプ３）の部分行列を用いる場合には、行番号選択部１３は、ダウンカウンタを選択し、列番号選択部２３は、ダウンカウンタを選択し、図３（ｄ）（タイプ４）の部分行列を用いる場合には、行番号選択部１３は、アップカウンタを選択し、列番号選択部２３は、ダウンカウンタを選択する。
【００５７】
第１実施形態においては、図２に示すように、検査行列を構成する各部分行列を、当該各部分行列の四隅のうち同一部位の隅部に位置する要素を基準として、全ての要素が零となる略三角形の領域を構成するようにしたことにより、当該各部分行列の行番号及び列番号のアドレスが共通にすることができることから、図７の復号回路１０２において、行番号カウンタ部１２（行番号アップカウンタを除く。）、行番号選択部１３、列番号カウンタ部２２（列番号アップカウンタを除く。）及び列番号選択部２３を削除しても上述と同様に行処理及び列処理の並列処理を実行することができる。
【００５８】
＜第２実施形態＞
図１０は、第２実施形態に係る低密度パリティ検査符号の検査行列Ｈの構成を示している。図１０に示すように、第２実施形態に係る低密度パリティ検査符号の検査行列Ｈ（Ｍ行×Ｎ列）は、これを行方向に４分割、列方向に４分割した大きさＭ／４行、Ｎ／４列の部分行列により構成されている。部分行列は、第１実施形態で説明したタイプ１からタイプ４であり、図１０の検査行列Ｈは、列方向にタイプ１とタイプ２およびタイプ３とタイプ４とを組み合わせ、行方向にタイプ１とタイプ４およびタイプ２とタイプ３とを組み合わせた構成になっている。
【００５９】
次に、図１０に示した第２実施形態に係る低密度パリティ検査符号の検査行列Ｈの復号処理演算について説明する。なお、第２実施形態においては、説明を簡単にするために、各部分行列のＭｓを１行とする。
ここで、タイプ１の部分行列については、行方向の演算、列方向の演算をともに行番号、列番号の小さい方から大きい方（行方向については、左から右に、列方向については、上から下）に計算を行う。また、タイプ２の部分行列については、行方向の演算は、行番号の大きい方から小さい方に、列方向の演算は、列番号の小さい方から大きい方に演算し、タイプ３の部分行列については、行方向の演算、列方向の演算をともに行番号、列番号の大きい方から小さい方行方向の演算し、タイプ４の部分行列については、行方向の演算は、行番号の小さい方から大きい方に、列方向の演算は、列番号の大きい方から小さい方に演算する。これは、検査行列Ｈの復号処理演算を短縮するためである。
【００６０】
検査行列Ｈの復号処理演算は以下のように行われる。つまり、１ステップ目の演算処理では、１行目、（Ｍ／４）＋１）行目、３Ｍ／４行目、（（３Ｍ／４）＋１）行目の行処理が同時並行的に行われる。この計算によって、１列目、２Ｎ／４列目、（（２Ｎ／４）＋１）列目、（（３Ｎ／４）＋１）列目の要素が確定するため、２ステップ目では、確定した前記列について列処理を同時並行的に行うとともに、２行目、（（Ｍ／４）＋２）行目、（（３Ｍ／４）−１）行目、（（３Ｍ／４）＋２）行目の行処理が同時並行的に行われる。以降、上述した各部分行列の演算順序にしたがって、行処理および列処理が同時並行的に行われる。
【００６１】
具体的な回路処理としては、図７に示す処理回路において、部分行列のタイプに応じて、行番号選択部１３及び列番号選択部２３は、それぞれアップカウンタを選択するか、ダウンカウンタを選択するか予め決定しておく。
【００６２】
したがって、第２実施形態に係る復号方法によれば、第１実施形態と同様に、２ステップ目以降、行処理と列処理とを同時並行して処理（オーバーラップ処理）することができるため、復号処理計算に要する時間を短縮することができる。
【００６３】
第２実施形態においては、図１０に示すように、検査行列を構成する各部分行列を、当該各部分行列の四隅のうち行方向及び列方向にそれぞれ同じ側の隅部に位置する要素を基準として、全ての要素が零となる略三角形の領域を構成するようにしたことにより、各部分行列に含まれる略三角形の領域の設定位置に応じて、当該各部分行列ごとに行方向及び列方向の向きをそれぞれ設定するようにすれば、第１実施形態の場合と同様に、行処理及び列処理の並列処理を実行することができる。
【００６４】
また、第２実施形態においては、各部分行列の四隅のうちいずれか一の隅部に位置する要素を基準として、行方向及び列方向にそれぞれ所定数離れた各要素を直線的に結ぶ略三角形の領域内の全ての要素が零となるように構成した場合について述べたが、本発明はこれに限らず、上記行方向及び列方向にそれぞれ所定数離れた各要素を階段状に単調変化させて結ぶようにして略三角形の領域を形成するようにしても良い。この場合、階段状の単調変化として、単に１行１列のみならず、２行１列や１行２列など行数及び列数をそれぞれ自由に設定することができ、行処理及び列処理の並列処理を当該設定された行数及び列数に合わせて実行することができる。
【００６５】
また、第２実施形態においては、行処理終了時点検知手段としての列計算制御部２１（図７）は、全ての要素が零となる略三角形の領域内の階段状の単調変化に基づいて、当該領域外の全ての要素に対する行処理の実行終了時点を検知するようにしたことにより、実際の行処理の終了タイミングを認識しなくても、各列ごとに列処理の開始タイミングを認識することができる。なお本発明はこれに限らず、各部分行列の各列ごとに、略三角形の領域外の全ての要素に対する行処理の実行終了時点を実際に検知するようにしても良い。
【００６６】
さらに本実施形態においては、メモリ手段として、行処理演算結果格納メモリ部１５及び列処理演算結果格納メモリ部１６からなるデュアルポートメモリ部３を適用した場合について述べたが、本発明はこれに限らず、要は、行処理結果を順次記憶すると同時に、既に記憶されている行処理結果を順次読み出すことができれば、その他種々の構成からなるメモリ手段に広く適用することができる。
【００６７】
＜第３実施形態＞
図１１は、第３実施形態に係る低密度パリティ検査符号の検査行列Ｈとその計算順序を例示している。第３実施形態においては、検査行列Ｈ全体の構成自体には特徴がなく、行処理時間および列処理時間の短縮化のために、検査行列Ｈを行方向に３つに分割し、行処理および列処理を同時並行的に処理するためにその計算順序を規定している。なお、分割数は任意であって、３に限るものではない。
【００６８】
第３実施形態における処理は、まず、列処理に必要な要素を含む行を抽出（図１１では、１列目に着目し、1列目の列処理に必要な要素を含む行として、図中、「１回目」と記載された行を抽出）し（要素判断手段）、１ステップ目でこの抽出した複数の行の行処理を同時並行的に処理する。１ステップ目の処理が終了すると、図１１の一列目の要素が確定する。一方、図１１において、２列目に着目すると、その列処理に必要な要素を含む行は、図中、「２回目」と記載された行であるため、２ステップ目では、これらの行を抽出して複数の行について行処理を同時並行的に行うとともに、さらに、1列目の列処理をオーバーラップして処理する。以降、こうした並行処理が順次行われる。
【００６９】
具体的な回路処理としては、図７に示す処理回路において、計算に必要なデータが格納されているメモリのアドレスを図１１に示す行処理の順番に並び替えて順番変更用メモリに格納し、行処理時に、順番変更用メモリから行処理に必要なデータが格納されているメモリのアドレスを適宜読み出すことにより、計算順序の変更を行う。
【００７０】
したがって、第３実施形態に係る復号方法によれば、検査行列の構成が特殊なものでなくとも、行処理と列処理とを同時並行的に処理することができるため、復号処理計算に要する時間を短縮することができる。
【００７１】
＜第４の実施形態＞
次に、本発明の第４の実施形態に係る低密度パリティ検査符号の復号装置および復号方法について詳細に説明する。
図１２は、第４実施形態に係る低密度パリティ検査符号の検査行列Ｈの構成を示している。図１２に示すように、第４実施形態に係る低密度パリティ検査符号の検査行列Ｈ（Ｍ行ＸＮ列）は、これを縦にＰｍ分割、横にＰｎ分割した大きさＭ／Ｐｍ行、Ｎ／Ｐｎ列の部分行列（図中、Hｓｕｂ１１、・・・、ＨｓｕｂＰｍＰｎと示す。）により構成されている。
【００７２】
ここで、Ｐｍは行処理の処理分割値と同じ値であり、Ｐｎは列処理の処理分割値と同じ値である。
【００７３】
図１３は、第４実施形態に係る低密度パリティ検査符号の検査行列Ｈの構成の一例をより詳細に示したものである。図１３に示される分割された部分行列は、図１４（ａ）に示されるように、部分行列の４隅の要素のうち左下隅の要素と、この要素から行方向および列方向に同じ行数および同じ列数（図１４（ａ）においては、Ｍｐ１と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、かつ、右上隅の要素と、この要素から行方向および列方向に同じ行数および同じ列数（図１４（ａ）においては、Ｍｐ２と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成をしている（以下、タイプ１と呼ぶ）。
【００７４】
なお、図１３示す部分行列は一例であり、以下、図１４（ｂ）（ｃ）（ｄ）に示す部分行列を用いてもよい。
【００７５】
図１４（ｂ）に示す部分行列は、部分行列の４隅の要素のうち左上隅の要素と、この要素から行方向および列方向に同じ行数および同じ列数（図１４（ｂ）においては、Ｍｐ１と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、かつ、右下隅の要素と、この要素から行方向および列方向に同じ行数および同じ列数（図１４（ｂ）においては、Ｍｐ２と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成（以下、タイプ２と呼ぶ）を有している。
【００７６】
図１４（ｃ）に示す部分行列は、部分行列の４隅の要素のうち右上隅の要素と、この要素から行方向および列方向に同じ-行数および同じ列数（図１４（ｃ）においては、Ｍｐ１と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、かつ、左下隅の要素と、この要素から行方向および列方向に同じ行数および同じ列数（図１４（ｃ）においては、Ｍｐ２と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成（以下、タイプ３と呼ぶ）を有している。
【００７７】
図１４（ｄ）に示す部分行列は、部分行列の４隅の要素のうち右下隅の要素と、この要素から行方向および列方向に同じ行数および同じ列数(図１４（ｄ）においては、Ｍｐ１と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、かつ、左上隅の要素と、この要素から行方向および列方向に同じ行数および同じ列数（図１４（ｄ）においては、Ｍｐ２と示す。）離れた要素とを互いに結んだ三角形内部のすべての要素が「０」であり、他の要素が「１」または「０」となる構成（以下、タイプ４と呼ぶ）を有している。
【００７８】
また、図１４（ａ）〜（ｄ）に示す部分行列において、Ｍｐ１およびＭｐ２は、上記三角部の１辺の「０」が並ぶ行数を示し、Ｍｓ１は、部分行列の行数からMｐ１を減じた行数であり、１以上の整数である。
【００７９】
次に、図１５及び図１６は、図１３に示す低密度パリティ検査符号の検査行列Ｈを用いた復号処理順序に関するものである。なお、図１５においては、説明を簡単にするために、各部分行列のＭｓ１を１行としている。
【００８０】
図１３に示す低密度パリティ検査符号の検査行列Ｈの場合、１ステップ目の演算処理では、図１５において斜線で示された各部分行列の先頭の行を同時並列的に処理する。この処理によって、各部分行列の先頭の行の要素がすべて計算されたことになる。ここで、各部分行列の１列目に着目すると、各部分行列の１行１列の要素を除いて、他の要素はすべて「０」である。
【００８１】
したがって、１ステップ目の行処理が終了すれば、各部分行列の１列目の列処理を行うための要素はすべて確定するため、各部分行列の１列目の列処理を開始することができる。すなわち、２ステップ目の演算では、各部分行列の２行目（図１５中、黒塗りの部分）の行処理と各部分行列の１列目の列処理とをオーバーラップして処理できる。そして、２ステップ目以降の処理についても、行処理と列処理を同時並列的にオーバーラップして処理することができる。
【００８２】
次に、検査行列Ｈの列処理についても、図１６において斜線で示された各部分行列のＭｓ２列目を同時並列的に処理する。１列目からＭｓ２列目までの列処理によって、各部分行列の先頭の行の要素がすべて計算されたことになる。
【００８３】
したがって、（Ｍｓ２＋１）ステップ目の列処理が終了すれば、各部分行列の１行目の行処理を行うための要素はすべて確定するため、各部分行列の１行目の行処理を開始することができる。すなわち、（Mｓ２＋２）ステップ目の演算では、各部分行列の１行目(図１６中、黒塗りの部分）の行処理と各部分行列の（Mｓ２＋１）列目の列処理とをオーバーラップして処理できる。そして、（Ｍｓ２＋２）ステップ目以降の処理についても、行処理と列処理を同時並列的にオーバーラップして処理することができる。そのため、復号計算処理に要する時間を図１７のように短縮することができる。
【００８４】
以下、この復号装置の詳細を説明する。
第４実施形態における復号装置も第１実施形態における復号装置と同じく、例えば、携帯電話機やＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ（Ｄａｔａ）Ａｓｓｉｓｔａｎｔｓ）のような受信装置に用いられるものである。その構成は、第１実施形態において説明した図６に示す内部構成と同じであり、第４実施形態の復号装置は、復調回路１０１ａ、復号回路１０２ａ、ＣＰＵ１０３ａ、映像／音声信号処理回路１０４ａ、スピーカ１０５ａ、モニタ１０６ａを備えている。
【００８５】
第４実施形態の復号装置に相当する復号回路１０２ａの内部構成を図１９、図２０、図２１に示す。第４実施形態の復号装置に相当する復号回路１０２ａは、図１９に示すように、主制御部４０と、行処理制御部（列処理終了時点検知手段）４１と、列処理制御部（行処理終了時点検知手段）４２と、行処理アドレス生成部５０と、列処理アドレス生成部６０と、列処理演算結果格納メモリ部（第２のメモリ手段）４６と、行処理演算部（行処理手段）４７と、行処理演算結果格納メモリ部（メモリ手段）４５と、列処理演算部（列処理手段）４４と、入力バッファ４３と、一時推定語演算部４９と、出力バッファ４８とを備えている。
【００８６】
図１９において、入力バッファ４３は受信語データを蓄えるメモリである。主制御部４０は、受信語有効信号により、復号すべき受信語データを受信したことを検知して、復号処理を開始するため、初期化指示を列処理制御部４２へ出力する。
【００８７】
行処理制御部４１は、行処理アドレス生成部５０、列処理制御部４２、および主制御部４０に対する制御信号を生成する回路であり、列処理制御部４２からの行処理開始の指示を受けて行処理を開始する。行処理中は、行処理アドレス生成部５０に制御信号を出す。そして、列処理が開始可能となった時点で、列処理制御部４２へ列処理開始の指示を出す。列処理が開始可能かどうかは、設定されているＭｓ１行数と処理済み行数カウンタ値を比較することで判断する。また、全ての行について、設定されている処理反復回数分の行処理が終了した時点で、主制御部４０へ行処理終了信号を出す。
【００８８】
行処理アドレス生成部５０は、行処理制御部４１からの行カウント指示により、図２０に示す行番号アップカウンタ５１または行番号ダウンカウンタ５２を動作させ、カウント値をアップまたはダウンし、行カウンタクリア指示により、行番号アップカウンタおよび行番号ダウンカウンタを初期値にクリアする。また、行処理アドレス生成部５０は、行番号選択回路５３にて、行番号アップカウンタ５１の出力をリードアドレスおよびライトアドレスとして出力するか、行番号ダウンカウンタ５２の出力をリードアドレスおよびライトアドレスとして出力するかを、行カウンタ選択信号によって選択する。当該選択信号は、使用している検査行列の部分行列のタイプに応じて決定する。
【００８９】
例えば、図１３に示す部分行列の場合には、行番号アップカウンタ５１を選択する。また、当該行処理アドレス生成部５０から出力するライトアドレスは、リードアドレスを遅延回路５４で遅延させることで生成する。遅延量は、行処理演算部４７の処理レイテンシや行処理演算結果格納メモリ部４５および列処理演算結果格納メモリ部４６のタイミング仕様に合わせて、遅延量を調整する。
【００９０】
行処理演算結果格納メモリ部４５および列処理演算結果格納メモリ部４６は、行処理および列処理のオーバーラップ処理を実現するために、デュアルポートメモリにより構成されている。
【００９１】
行処理演算部４７は、列処理演算結果格納メモリ部４６から読み出した値に基づいて、ビットノードへ送るメッセージを演算し、その演算結果を行処理演算結果格納メモリ部４５へライトする。
【００９２】
列処理制御部４２は、列処理アドレス生成部６０、行処理制御部４１、および主制御部４０に対する制御信号を生成する回路であり、主制御部４０からの初期化指示を受けて、列処理演算結果格納メモリ部４６の初期化を行う。また、列処理制御部４２は、行処理制御部４１からの列処理開始の指示を受けて列処理を開始する。列処理中は、列処理アドレス生成部６０に制御信号を出す。そして、行処理が開始可能となった時点で、行処理制御部４１へ行処理開始の指示を出す。行処理が開始可能かどうかは、設定されているＭｓ２列数と処理済み列数カウンタ値を比較することで判断する。
また、全ての列について、設定されている処理反復回数分の列処理が終了した時点で、主制御部へ列処理終了信号を出す。
【００９３】
列処理アドレス生成部６０は、列処理制御部４２からの列カウント指示により、図２１列番号アップカウンタ６１または列番号ダウンカウンタ６２を動作させ、カウント値をアップまたはダウンし、列カウンタクリア指示により、列番号アップカウンタ６１および列番号ダウンカウンタ６２を初期値にクリアする。また、列処理アドレス生成部６０は、列番号選択回路６３にて、列番号アップカウンタ６１の出力をアドレス変換部６４へ出力するか、列番号ダウンカウンタ６２の出力をアドレス変換部６４へ出力するかを、列カウンタ選択信号によって選択する。
【００９４】
当該選択信号は、使用している検査行列の部分行列のタイプに応じて決定する。例えば、図１３に示す部分行列の場合には、列番号アップカウンタ６１を選択する。アドレス変換部６４では、使用している検査行列に対応するように、選択後列番号から列処理対象データが格納されている行処理演算結果格納メモリ部４５および列処理対象データを格納する列処理演算結果格納メモリ部４６のアドレスへ変換する。また、当該列処理アドレス生成部６０から出力するライトアドレスは、リードアドレスを遅延回路６５で遅延させることで生成する。遅延量は、列処理演算部４４の処理レイテンシや行処理演算結果格納メモリ部４５および列処理演算結果格納メモリ部４６のタイミング仕様に合わせて、遅延量を調整する。
【００９５】
列処理演算部４４は、行処理演算結果格納メモリ部４５から読み出した値と入力バッファ４３から読み出した受信語に基づいて、チェックノードへ送るメッセージを演算し、その演算結果を列処理演算結果格納メモリ部４６へライトする。
【００９６】
一時推定語演算部４９は、行処理演算結果格納メモリ部４５から読み出した値と入カバッファから読み出した受信語に基づいて、一時推定語を求める演算回路である。そして、求めた一時推定語を出力バッファ４８へ出力する。出力バッファ４８は、一時推定語演算結果を蓄えるメモリであり、主制御部４０からの出力制御信号に従い、蓄えた一時推定語演算結果を復号後データとして外部へ出力する。主制御部４０は、行処理制御部４１からの行処理終了信号および列処理制御部４２からの列処理終了信号の両方を受け取ることで、１受信語の復号処理を終了する。また、出力バッファ４８から復号後データを出力するように、出力バッファ４８へ出力制御信号を出す。
【００９７】
なお、図１９の構成は、検査行列Ｈが分割されない場合の構成であり、行処理アドレス生成部５０、列処理アドレス生成部６０、行処理演算部４７、列処理演算部４４を１つずつ備えているが、検査行列が分割される場合には、行処理アドレス生成部５０及び行処理演算部４７は、Ｐｍ個分備え、列処理アドレス生成部６０及び列処理演算部４４は、Ｐｎ個分備えることになる。
【００９８】
次に、具体的な処理の流れを図２２に示すフローに沿って説明する。主制御部４０は、符号語を受信すると処理を開始する（ステップ２０１）。主制御部４０は、まず、列処理制御部４２および列処理演算部４４に初期化指示を出す（ステップ２０２）。初期化指示を受け取った列処理演算部４４は、受信語データのみを列処理演算結果格納メモリ部４６に出力する。また、初期化指示を受け取った列処理制御部４２は、初期化のための列処理を開始する（ステップ２０３）。列処理制御部４２は、列処理アドレス生成部６０に列カウント指示を出す（ステップ２０４）。列カウント指示を受け取った列処理アドレス生成部６０は、列カウンタのアップおよびダウンを開始する（ステップ２０５）。
【００９９】
列処理制御部４２は、次に、列処理演算を行うために、行処理演算結果格納メモリ部４５をリードする（ステップ２０６）。なお、このときのリードアドレスは、列処理アドレス生成部６０から出力される。初期化のときは、当該リードデータは必要ないが、初期化以外の列処理と動作を共通にするため、ここではステップ２０６の処理を行う。
【０１００】
列処理制御部４２は、次に、列処理演算結果格納メモリ部４６を受信語で初期化するため、列処理演算部４４の出力データを列処理演算結果格納メモリ部４６へライトする（ステップ２０７）。なお、このときのライトアドレスは、列処理アドレス生成部６０から出力される。列処理制御部４２は、処理済列数カウンタのカウント値が予め設定されているＭｓ２列数設定値と一致すると、行処理制御部４１に行処理の開始を指示する（ステップ２０８）。列処理制御部４２は、列処理を繰り返し、全ての列に対する列処理を終了させる（ステップ２０９）。
【０１０１】
列処理制御部４２は、全ての列に対する列処理を終了すると、列処理アドレス生成部６０に列カウンタクリア指示を出力する（ステップ２１０）。列カウンタクリア指示を受け取った列処理アドレス生成部６０は、列カウンタを初期値にクリアする（ステップ２１１）。列処理制御部４２は、次に、全ての列処理をｉｔ回繰り返したかどうかの判定を行うが、初期化時は、常に、「Ｎｏ」の判定とする（ステップ２１２）。
【０１０２】
一方、行処理制御部４１は、列処理制御部４２からの行処理開始指示を受けて処理を開始する（ステップ２２０）。行処理制御部４１は、行処理アドレス生成部５０に行カウント指示を出す（ステップ２２１）。行カウント指示を受け取った行処理アドレス生成部５０は、行カウンタのアップおよびダウンを開始する（ステップＳ２２２）。行処理制御部４１は、次に、行処理演算を行うために、列処理演算結果格納メモリ部４６をリードする（ステップＳ２２３）。なお、このときのリードアドレスは、行処理アドレス生成部５０から出力される。
【０１０３】
行処理制御部４１は、次に、行処理演算部４７の出力データを行処理演算結果格納メモリ部４５へライトする（ステップ２２４）。なお、このときのライトアドレスは、行処理アドレス生成部５０から出力される。行処理制御部４１は、処理済行数カウンタのカウント値が予め設定されているＭｓ１行数設定値と一致すると、列処理制御部４２に列処理の開始を指示する（ステップ２２５）。行処理制御部４１は、行処理を繰り返し、全ての行に対する行処理を終了させる（ステップ２２６）。行処理制御部４１は、全ての行に対する行処理を終了すると、行処理アドレス生成部５０に行カウンタクリア指示を出力する（ステップ２２７）。行カウンタクリア指示を受け取った行処理アドレス生成部５０は、行カウンタを初期値にクリアする（ステップ２２８）。
【０１０４】
行処理制御部４１は、次に、全ての行処理をｉｔ回繰り返したかどうかの判定を行う（ステップ２２９）。まだｉｔ回繰り返していなければ、再び、列処理制御部４２からの行処理開始指示を待ち、ｉｔ回繰り返していれば、行処理制御部４１は、主制御部に行処理終了信号を出力して（ステップ２３０）、行処理を終了する（ステップ２３１）。
【０１０５】
列処理制御部４２は、行処理制御部４１からの列処理開始指示を受け取って、列処理を開始する。このときは、初期化のための列処理ではないので、ステップ２１２のｉｔ回繰り返し判定を行う。まだｉｔ回繰り返していなければ、再び、行処理制御部４１からの列処理開始指示を待ち、ｉｔ回繰り返していれば、列処理制御部４２は、主制御部４０に列処理終了信号を出力して（ステップ２１３）、列処理を終了する（ステップ２１４）。
【０１０６】
主制御部４０は、行処理制御部４１からの行処理終了信号および列処理制御部４２からの列処理終了信号の両方を受け取ることで復号処理終了と判断し、最後に出力制御信号を出力バッファ４８に出力して、１受信語に対する復号処理を終了する（ステップ２３２、２３３、２３４）
【０１０７】
図２３は、図２２を用いて説明を行った行処理と列処理とのオーバーラップ処理を実現するための行処理演算結果格納メモリ部４５および列処理演算結果格納メモリ部４６に対するアクセスタイミングを示すものである。図２３から、列処理演算結果格納メモリ部４６のポートＡは、リードアクセス用に、列処理演算結果格納メモリ部４６のポートＢは、ライトアクセス用に使用される。また、行処理演算結果格納メモリ部４５のポートＡは、ライトアクセス用に、行処理演算結果格納メモリ部４５のポートＢは、リードアクセス用に使用される。
【０１０８】
行処理実行時には、列処理演算結果格納メモリ部４６のポートＡからリードしたデータは、行処理の演算を行ったのち、行処理演算結果格納メモリ部４５のポートＡを通してライトされる。一方、列処理実行時には、行処理演算結果格納メモリ部４５のポートＢからリードしたデータは、列処理の演算を行ったのち、列処理演算結果格納メモリ部４６のポートＢを通してライトされる。このように、行処理演算結果格納メモリ部４５および列処理演算結果格納メモリ部４６としてデュアルポートメモリを使用することで行処理、列処理のオーバーラップ処理を実現できる。
【０１０９】
＜第５実施形態＞
次に、本発明の第５実施形態について説明する。
図２４は、第５実施形態に係る低密度パリティ検査符号の検査行列Ｈの構成を示している。図２４に示すように、第５実施形態に係る低密度パリティ検査符号の検査行列Ｈ（Ｍ行ＸＮ列）は、これを縦に４分割、横に４分割した大きさＭ／４行、Ｎ／４列の部分行列により構成されている。部分行列は、第４実施形態で説明したタイプ１からタイプ４であり、図２４の検査行列Ｈは、縦方向にタイプ１とタイプ２およびタイプ３とタイプ４とを組み合わせ、横方向にタイプ１とタイプ４およびタイプ２とタイプ３とを組み合わせた構成になっている。
【０１１０】
次に、図２４に示した第５実施形態の係る低密度パリティ検査符号の検査行列Ｈを用いた復号処理について説明する。
なお、第５実施形態においては、説明を簡単にするために、各部分行列のＭｓ１を１行とする。
【０１１１】
ここで、タイプ１の部分行列については、行番号、列番号ともに小さいほうから大きいほうに行処理および列処理を行う。また、タイプ２の部分行列については、行番号の大きいほうから小さいほうに、列番号の小さいほうから大きいほうに行処理および列処理を行う。タイプ３の部分行列については、行番号、列番号ともに大きいほうから小さいほうに行処理および列処理を行う。タイプ４の部分行列については、行番号の小さいほうから大きいほうに、列番号の大きいほうから小さいほうに行処理および列処理を行う。このような処理を行うのは、図２４で示した検査行列Ｈを用いた復号処理時間を短縮するためである。
【０１１２】
検査行列Ｈの復号処理は以下のように行われる。１ステップ目の演算処理では、１行目、（Ｍ／４＋１）行目、（３Ｍ／４）行目、（３Ｍ／４＋１）行目の行処理が同時並列的に行われる。この処理によって、１列目、２Ｎ／４列目、（２Ｎ／４＋１）列目、（３Ｎ／４＋１）列の要素が確定するため、２ステップ目では、確定した前記列について列処理を同時並列的に行うとともに、２行目、（Ｍ／４＋２）行目、（３Ｍ／４−１）行目、（３Ｍ／４＋２）行目の行処理が同時並列的に行われる。以降、上述した各部分行列の処理順序にしたがって、行処理および列処理が同時並列的に行われる。
【０１１３】
したがって、第５実施形態に係る復号方法によれば、第４実施形態と同様に、２ステップ目以降、行処理と列処理とを同時並行して処理（オーバーラップ処理）することができるため、復号処理に要する時間を短縮することができる。
【０１１４】
また、上述した第１、第２、第４及び第５実施形態においては、各部分行列の零三角部は直角二等辺三角形の場合について述べたが、本発明は、これに限らず、上記零三角部は直角二等辺三角形以外の直角三角形でもよい。この場合、階段状の単調変化として、単に１行１列のみならず、２行１列や１行２列など行数および列数をそれぞれ自由に設定することができ、行処理および列処理の並列処理を当該設定された行数および列数に合わせて実行することができる。
【０１１５】
さらに、上述した第１及び第４実施形態においては、メモリ手段として、行処理演算結果格納メモリ部１５および列処理演算結果格納メモリ部１６、並びに行処理演算結果格納メモリ部４５および列処理演算結果格納メモリ部４６からなるデュアルポートメモリを適用した場合について述べたが、本発明はこれに限らず、要は、行処理演算結果を順次記憶すると同時に、既に記憶されている行処理演算結果を順次読み出すことができ、かつ、列処理演算結果を順次記憶すると同時に、既に記憶されている列処理演算結果を順次読み出すことができれば、その他種々の構成からなるメモリ手段に広く適用することができる。
【０１１６】
以上、図面を参照して本発明の実施例について詳述してきたが、具体的な構成はこれらの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。例えば、第１および第２、並びに第４および第５実施形態においては、部分行列内に形成される「０」のみの要素からなる三角部を行方向、列方向の要素数が等しい、直角二等辺三角形として説明したが、これに限るものではない。また、本発明の復号装置の構成として、図７では、行計算統括処理部および列計算統括処理部を示したが、これらの機能は、受信装置のＣＰＵにおける部分的な機能として実現することも可能である。また、図１８では、主制御部、行処理制御部、列処理制御部、行処理アドレス生成部、列処理アドレス生成部を示したが、これらの機能は、受信装置のＣＰＵにおける部分的な機能として実現することも可能である。
【図面の簡単な説明】
【０１１７】
【図１】本発明の第１実施形態に係る検査行列の基本構成を示す図である。
【図２】第１実施形態に係る検査行列の構成を示す図である。
【図３】第１実施形態に係る部分行列の構成例を示した図である。
【図４】第１実施形態に係る復号計算順序を示す図である。
【図５】第１実施形態に係る復号処理時間を示した図である。
【図６】第１実施形態に係る受信装置の構成を示した図である。
【図７】第１実施形態に係る復号回路の構成図である。
【図８】第１実施形態に係る復号処理のフローである。
【図９】第１実施形態に係るメモリのアクセスタイミングを示した図である。
【図１０】第２実施形態に係る検査行列の構成を示す図である。
【図１１】第３実施形態に係る検査行列の構成および復号処理順序を示す図である。
【図１２】第４実施形態に係る検査行列の基本構成を示す図である。
【図１３】第４実施形態に係る検査行列の構成を示す図である。
【図１４】第４実施形態に係る部分行列の構成例を示した図である。
【図１５】第４実施形態に係る復号計算順序（行処理）を示す図である。
【図１６】第４実施形態に係る復号計算順序（列処理）を示す図である。
【図１７】第４実施形態に係る復号処理時間を示した図である。
【図１８】第４実施形態に係る受信装置の構成を示した図である。
【図１９】第４実施形態に係る復号回路の構成図である。
【図２０】第４実施形態に係る行処理アドレス生成部の構成図である。
【図２１】第４実施形態に係る列処理アドレス生成部の構成図である。
【図２２】第４実施形態に係る復号処理のフローである。
【図２３】第４実施形態に係るメモリのアクセスタイミングを示した図である。
【図２４】第５実施形態に係る検査行列の構成および復号処理順序を示す図である。
【図２５】一般的な検査行列を示した図である。
【図２６】タナーグラフを示した図である。
【図２７】行処理の計算方法を例示した図である。
【図２８】列処理の計算方法を例示した図である。
【図２９】従来の復号処理に関する処理フローである。
【図３０】従来の復号処理に関する復号処理時間を示す図である。
【図３１】従来の検査行列における復号処理手順を示した図である。
【図３２】並行処理を行う場合の従来の回路構成を示す図である。
【図３３】並行処理を行った場合の従来の復号処理時間を示す図である。
【符号の説明】
【０１１８】
１・・・行計算統括処理部、２・・・列計算統括処理部、３・・・デュアルポートメモリ部（メモリ手段、デュアルポートメモリ）、１１・・・行計算制御部、１２・・・行番号カウンタ部、１３・・・行番号選択部、１４・・・行タイミング遅延部、１５・・・行処理演算結果格納メモリ部、１６・・・列処理演算結果格納メモリ部、１７・・・行処理演算部（行処理手段）、１８・・・出力バッファ、１９・・・Ｐ／Ｓ回路、２１・・・列計算制御部（行処理終了時点検知手段）、２２・・・列番号カウンタ部、２３・・・列番号選択部、２４・・・列処理演算部（列処理手段）、２５・・・列タイミング遅延部、２６・・・Ｓ／Ｐ回路、２７・・・一時推定語演算部、２８・・・ビットノード演算ブロック、２９・・・チェックノード演算ブロック
【図１】
2007043635.tif 000007
【図２】
2007043635.tif 000008
【図３】
2007043635.tif 000009
【図４】
2007043635.tif 000010
【図５】
2007043635.tif 000011
【図６】
2007043635.tif 000012
【図７】
2007043635.tif 000013
【図８】
2007043635.tif 000014
【図９】
2007043635.tif 000015
【図１０】
2007043635.tif 000016
【図１１】
2007043635.tif 000017
【図１２】
2007043635.tif 000018
【図１３】
2007043635.tif 000019
【図１４】
2007043635.tif 000020
【図１５】
2007043635.tif 000021
【図１６】
2007043635.tif 000022
【図１７】
2007043635.tif 000023
【図１８】
2007043635.tif 000024
【図１９】
2007043635.tif 000025
【図２０】
2007043635.tif 000026
【図２１】
2007043635.tif 000027
【図２２】
2007043635.tif 000028
【図２３】
2007043635.tif 000029
【図２４】
2007043635.tif 000030
【図２５】
2007043635.tif 000031
【図２６】
2007043635.tif 000032
【図２７】
2007043635.tif 000033
【図２８】
2007043635.tif 000034
【図２９】
2007043635.tif 000035
【図３０】
2007043635.tif 000036
【図３１】
2007043635.tif 000037
【図３２】
2007043635.tif 000038
【図３３】
2007043635.tif 000039