(57)【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法であって、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を用意し、さらに、最終的に生成するパリティ検査行列において所定の最小ループを保証するための条件式を導出し、当該条件式および所定の重み分布に基づいて特定の巡回置換行列を０行列に変換するためのマスク行列を生成するマスク行列生成ステップと、
前記マスク行列を用いて前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則（行と列の重みが非一様）なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含むことを特徴とする検査行列生成方法。
【請求項２】
前記マスク行列生成ステップでは、
前記正則な擬似巡回行列として、行方向にＪ個および列方向にＬ個のｐ行×ｐ列の巡回置換行列が配置され、当該巡回置換行列を単位として表現された、ループ４を含まないＪ行×Ｌ列の擬似巡回行列を想定する場合、
当該Ｊ行×Ｌ列の擬似巡回行列に、ｊ行（０≦ｊ≦Ｊ−１）ｌ列（０≦ｌ≦Ｌ−１）目に配置された巡回置換行列の１行目の“１”の列番号が「（ｊ＋ｃ）・（ｌ＋ｄ）」（ｃ、ｄは０以上の任意の整数であり、「（ｊ＋ｃ）・（ｌ＋ｄ）＜ｐ」を満たす）となる特定の規則性を持たせることを特徴とする請求項１に記載の検査行列生成方法。
【請求項３】
前記マスク行列生成ステップでは、
前記正則な擬似巡回行列として、行方向にＪ個および列方向にＬ個のｐ行×ｐ列の巡回置換行列が配置され、当該巡回置換行列を単位として表現された、ループ４を含まないＪ行×Ｌ列の擬似巡回行列を想定する場合、
当該Ｊ行×Ｌ列の擬似巡回行列に、ｊ行（０≦ｊ≦Ｊ−１）ｌ列（０≦ｌ≦Ｌ−１）目に配置された巡回置換行列の１行目の“１”の列番号が「（ｊ＋ｃ）・（ｌ＋ｄ）ｍｏｄ  ｐ」（ｃ、ｄは０以上の任意の整数である）となる特定の規則性を持たせることを特徴とする請求項１に記載の検査行列生成方法。
【請求項４】
前記マスク行列生成ステップでは、
前記条件式として、前記正則な擬似巡回行列がループ６を含む条件式（ループ６の条件式）を導出し、当該条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項２に記載の検査行列生成方法。
【請求項５】
前記マスク行列生成ステップでは、
前記条件式として、前記正則な擬似巡回行列がループ６を含む条件式（ループ６の条件式）を導出し、当該条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項３に記載の検査行列生成方法。
【請求項６】
さらに、前記正則な擬似巡回行列と前記巡回置換行列を階段状に配置した行列との間で構成されるループ６の条件式を導出し、
前記２つの条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項４に記載の検査行列生成方法。
【請求項７】
さらに、前記正則な擬似巡回行列と前記巡回置換行列を階段状に配置した行列との間で構成されるループ６の条件式を導出し、
前記２つの条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項５に記載の検査行列生成方法。
【請求項８】
さらに、前記ループ６の条件式に加えて、必要に応じてループ８、ループ１０、…の条件式を導出し、前記ループ６の条件式を満たさないこと、前記ループ６および８の条件式を満たさないこと、前記ループ６、８および１０の条件式を満たさないこと、…を拘束条件として、適応的にマスク行列を構成することを特徴とする請求項６に記載の検査行列生成方法。
【請求項９】
さらに、前記ループ６の条件式に加えて、必要に応じてループ８、ループ１０、…の条件式を導出し、前記ループ６の条件式を満たさないこと、前記ループ６および８の条件式を満たさないこと、前記ループ６、８および１０の条件式を満たさないこと、…を拘束条件として、適応的にマスク行列を構成することを特徴とする請求項７に記載の検査行列生成方法。
【請求項１０】
前記マスク行列生成ステップでは、
前記正則な擬似巡回行列として、行方向にＪ個および列方向にＬ個のｐ行×ｐ列の巡回置換行列が配置され、当該巡回置換行列を単位として表現された、ループ４を含まないＪ行×Ｌ列の擬似巡回行列を想定する場合、
当該Ｊ行×Ｌ列の擬似巡回行列に、ｊ行（０≦ｊ≦Ｊ−１）ｌ列（０≦ｌ≦Ｌ−１）目に配置された巡回置換行列の１行目の“１”の列番号が「ｑ(j+c)・ｑ(l+d)」（ｃ、ｄは０以上の任意の整数であり、「ｑ(j+c)・ｑ(l+d)＜ｐ」を満たす）となる特定の規則性を持たせることを特徴とする請求項１に記載の検査行列生成方法。
【請求項１１】
前記マスク行列生成ステップでは、
前記正則な擬似巡回行列として、行方向にＪ個および列方向にＬ個のｐ行×ｐ列の巡回置換行列が配置され、当該巡回置換行列を単位として表現された、ループ４を含まないＪ行×Ｌ列の擬似巡回行列を想定する場合、
当該Ｊ行×Ｌ列の擬似巡回行列に、ｊ行（０≦ｊ≦Ｊ−１）ｌ列（０≦ｌ≦Ｌ−１）目に配置された巡回置換行列の１行目の“１”の列番号が「ｑ(j+c)・ｑ(l+d)ｍｏｄ  ｐ」（ｑは正の整数であり、ｃ、ｄは０以上の任意の整数である）となる特定の規則性を持たせることを特徴とする請求項１に記載の検査行列生成方法。
【請求項１２】
前記マスク行列生成ステップでは、
前記条件式として、前記正則な擬似巡回行列がループ６を含む条件式（ループ６の条件式）を導出し、当該条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項１０に記載の検査行列生成方法。
【請求項１３】
前記マスク行列生成ステップでは、
前記条件式として、前記正則な擬似巡回行列がループ６を含む条件式（ループ６の条件式）を導出し、当該条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項１１に記載の検査行列生成方法。
【請求項１４】
さらに、前記正則な擬似巡回行列と前記巡回置換行列を階段状に配置した行列との間で構成されるループ６の条件式を導出し、
前記２つの条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項１２に記載の検査行列生成方法。
【請求項１５】
さらに、前記正則な擬似巡回行列と前記巡回置換行列を階段状に配置した行列との間で構成されるループ６の条件式を導出し、
前記２つの条件式を満たさないことを拘束条件としてマスク行列を構成することを特徴とする請求項１３に記載の検査行列生成方法。
【請求項１６】
さらに、前記ループ６の条件式に加えて、必要に応じてループ８、ループ１０、…の条件式を導出し、前記ループ６の条件式を満たさないこと、前記ループ６および８の条件式を満たさないこと、前記ループ６、８および１０の条件式を満たさないこと、…を拘束条件として、適応的にマスク行列を構成することを特徴とする請求項１４に記載の検査行列生成方法。
【請求項１７】
さらに、前記ループ６の条件式に加えて、必要に応じてループ８、ループ１０、…の条件式を導出し、前記ループ６の条件式を満たさないこと、前記ループ６および８の条件式を満たさないこと、前記ループ６、８および１０の条件式を満たさないこと、…を拘束条件として、適応的にマスク行列を構成することを特徴とする請求項１５に記載の検査行列生成方法。
【請求項１８】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法であって、
前記請求項２に記載の特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を用意し、さらに、所定の重み分布に基づく有限幾何符号を用意し、当該有限幾何符号を所定の演算式に基づいて規則的に置換することにより、特定の巡回置換行列を０行列に変換するためのマスク行列を生成するマスク行列生成ステップと、
前記マスク行列を用いて前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則（行と列の重みが非一様）なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含むことを特徴とする検査行列生成方法。
【請求項１９】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法であって、
前記請求項３に記載の特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を用意し、さらに、所定の重み分布に基づく有限幾何符号を用意し、当該有限幾何符号を所定の演算式に基づいて規則的に置換することにより、特定の巡回置換行列を０行列に変換するためのマスク行列を生成するマスク行列生成ステップと、
前記マスク行列を用いて前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則（行と列の重みが非一様）なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含むことを特徴とする検査行列生成方法。
【請求項２０】
前記マスク行列生成ステップでは、前記マスク行列の重み分布を密度発展法により求めることを特徴とする請求項１に記載の検査行列生成方法。
【請求項２１】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する符号化方法であって、
前記請求項１〜２０のいずれか一つに記載の処理で生成された非正則なパリティ検査行列を用いて所定の情報ビットを符号化する符号化ステップ、
を含むことを特徴とする符号化方法。
【請求項２２】
前記符号化ステップでは、符号語長Ｎ（Ｎ＝情報長Ｋ＋パリティ長Ｍ）の符号を構成する場合、情報長Ｋのメッセージが与えられると、前記符号と前記非正則なパリティ検査行列との積が０となる条件の下で生成された所定の演算式に基づいて、Ｍビットのパリティを、Ｋ＋１ビット目から順にＮビット目まで１ビット単位に決定することを特徴とする請求項２１に記載の符号化方法。
【請求項２３】
複数の符号化率に対応したＬＤＰＣ符号を構成する場合、
特定の符号化率の符号語を基準とし、
前記特定の符号化率よりも低い符号化率の場合には、前記検査行列生成ステップにおいて生成された前記特定の符号化率に対応するＬＤＧＭ構造の非正則なパリティ検査行列の構成を維持した状態で、前記非正則なパリティ検査行列を拡張し、
前記特定の符号化率よりも高い符号化率の場合には、前記特定の符号化率の符号語のパリティを間引くことを特徴とする請求項２２に記載の符号化方法。
【請求項２４】
前記拡張後のパリティ検査行列がＬＤＧＭ構造を維持することを特徴とする請求項２３に記載の符号化方法。
【請求項２５】
前記特定の符号化率の符号語のパリティを間引く処理においては、可能な限りビット間隔を空けることを特徴とする請求項２４に記載の符号化方法。
【請求項２６】
所定の情報ビットを消失訂正符号化する符号化方法であって、
前記請求項１〜１９のいずれか一つに記載の処理で生成された非正則なマスク化擬似巡回行列を用いて消失訂正符号を生成することを特徴とする符号化方法。
【請求項２７】
前記請求項２１に記載の処理でＬＤＰＣ符号化された符号語を、前記請求項２１に記載の処理と同一の処理で生成したパリティ検査行列を用いて復号する復号方法であって、
前記パリティ検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値に基づいて、列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理ステップと、
前記行処理により演算された列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算し、さらに、行重みに対応した行処理用ＬＬＲの絶対値の最小ｋ値をメモリの特定領域に保持する列処理、を実行する列処理ステップと、
を行の最小ｋ値を更新しながら実行し、復号を行うことを特徴とする復号方法。
【請求項２８】
前記パリティ検査行列の列を所定数に分割し、分割後のグループ単位に並列に前記行処理および列処理を実行し、さらに、前記最小ｋ値を保持するメモリの領域を共有し、並列に実行される各列処理においてそれぞれ前記最小ｋ値を更新することを特徴とする請求項２７に記載の復号方法。
【請求項２９】
前記パリティ検査行列の特徴を利用して、前記並列処理の実施時に、前記グループを、G1=[0*p+1,1*p+1,2*p+1,…]，G2=[0*p+2,1*p+2,2*p+2,…]，G3=[0*p+3,1*p+3,2*p+3,…]，…に分割し、各グループの要素の最小値から順に全グループあるいは一部のグループの並列処理を実行することを特徴とする請求項２８に記載の復号方法。
【請求項３０】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する送信側および受信側の通信装置であって、
前記請求項１〜２０のいずれか一つに記載の処理で、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成することを特徴とする通信装置。
【請求項３１】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する送信側の通信装置であって、
前記請求項２１に記載の処理で、所定の情報ビットを符号化するＬＤＰＣ符号化器、
を備えることを特徴とする通信装置。
【請求項３２】
送信側でＬＤＰＣ符号化された符号語を、パリティ検査行列を用いて復号する受信側の通信装置であって、
前記請求項２７に記載の処理で、符号語を復号するＬＤＰＣ復号器、
を備えることを特徴とする通信装置。
【請求項３３】
誤り訂正技術として、ＬＤＰＣ（Low-Density  Parity  Check）符号を採用する通信システムであって、
前記請求項２１に記載の処理で、所定の情報ビットを符号化する送信装置と、
前記請求項２７に記載の処理で、符号語を復号する受信装置と、
を備えることを特徴とする通信システム。
【請求項３４】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する符号化器において、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列と、最終的に生成するパリティ検査行列において所定の最小ループを保証するための条件および所定の重み分布に基づいて生成された特定の巡回置換行列を０行列に変換するためのマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換して生成された非正則（行と列の重みが非一様）なマスク化擬似巡回行列と、巡回置換行列を階段状に配置した行列とを所定位置に配置して生成されたＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を用いて符号化する符号化手段、
を備えたことを特徴とする符号化器。
【請求項３５】
前記請求項３４に記載の符号化器で符号化された符号語を復号する復号器であって、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列と、最終的に生成するパリティ検査行列において所定の最小ループを保証するための条件および所定の重み分布に基づいて生成された特定の巡回置換行列を０行列に変換するためのマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換して生成された非正則（行と列の重みが非一様）なマスク化擬似巡回行列と、巡回置換行列を階段状に配置した行列とを所定位置に配置して生成されたＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を用いて復号する復号手段、
を備えたことを特徴とする復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル通信における符号化技術に関するものであり、特に、ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法、当該パリティ検査行列を用いて所定の情報ビットを符号化する符号化方法、および通信装置に関するものである。
【背景技術】
【０００２】
以下、符号化方式としてＬＤＰＣ符号を採用する従来の通信システムについて説明する。ここでは、ＬＤＰＣ符号の一例として擬似巡回（ＱＣ：Quasi-Cycilc）符号（非特許文献１参照）を採用する場合について説明する。【０００３】
まず、符号化方式としてＬＤＰＣ符号を採用する従来の通信システムにおける、符号化／復号処理の流れを簡単に説明する。【０００４】
送信側の通信装置（送信装置と呼ぶ）内のＬＤＰＣ符号化器では、後述する従来の方法でパリティ検査行列Ｈを生成する。さらに、ＬＤＰＣ符号化器では、たとえば、Ｋ行×Ｎ列の生成行列Ｇ（Ｋ：情報長，Ｎ：符号語長）を生成する。ただし、ＬＤＰＣ用のパリティ検査行列をＨ（Ｍ行×Ｎ列）とした場合、生成行列Ｇは、ＧＨT＝０（Ｔは転置行列）を満たす行列となる。【０００５】
その後、ＬＤＰＣ符号化器では、情報長Ｋのメッセージ（ｍ1，ｍ2，…，ｍK）を受け取り、このメッセージおよび上記生成行列Ｇを用いて、下記（１）式のように、符号語Ｃを生成する。ただし、Ｈ（ｃ1，ｃ2，…，ｃN）T＝０とする。
Ｃ＝（ｍ1，ｍ2，…，ｍK）Ｇ
＝（ｃ1，ｃ2，…，ｃN）                    …（１）【０００６】
そして、送信装置内の変調器では、ＬＤＰＣ符号化器で生成した符号語Ｃに対して、ＢＰＳＫ（Binary  Phase  Shift  Keying），ＱＰＳＫ（Quadrature  Phase  Shift  Keying），多値ＱＡＭ（Quadrature  Amplitude  Modulation）等の所定の変調方式によりディジタル変調を行い、その変調信号ｘ＝（ｘ1，ｘ2，…，ｘN）を受信装置に送信する。【０００７】
一方、受信側の通信装置（受信装置と呼ぶ）では、復調器が、受け取った変調信号ｙ＝（ｙ1，ｙ2，…，ｙN）に対して、上記ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭ等の変調方式に応じたディジタル復調を行い、さらに、受信装置内のＬＤＰＣ復号器が、復調結果に対して「ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム」による繰り返し復号を実施し、その復号結果（元のメッセージｍ1，ｍ2，…，ｍKに対応）を出力する。【０００８】
ここで、ＬＤＰＣ符号用の従来のパリティ検査行列生成方法を具体的に説明する。ＬＤＰＣ符号用のパリティ検査行列としては、たとえば、下記非特許文献１において、以下のＱＣ符号のパリティ検査行列が提案されている（図１７参照）。図１７に示すＱＣ符号のパリティ検査行列は、５行×５列の巡回置換行列（ｐ＝５）が縦方向（Ｊ＝３）と横方向（Ｌ＝５）に配置された行列となっている。【０００９】
一般的には、Ｍ（＝ｐＪ）行×Ｎ（＝ｐＬ）列の（Ｊ，Ｌ）ＱＣ符号のパリティ検査行列ＨQCは、下記（２）式のように定義することができる。なお、ｐは奇数（２以外）の素数であり、Ｌはパリティ検査行列ＨQCにおける巡回置換行列の横方向（列方向）の個数であり、Ｊはパリティ検査行列ＨQCにおける巡回置換行列の縦方向（行方向）の個数である。【００１０】
【数１】
0004563454.tif 000002
…（２）【００１１】
ただし、０≦ｊ≦Ｊ−１，０≦ｌ≦Ｌ−１において、Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１），列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列である。【００１２】
また、ＬＤＰＣ符号の設計の際には、一般的に、長さが短いループが多く存在するときに性能の劣化を引き起こすため、内径を大きくし、長さが短いループ（ループ４，ループ６等）の数を少なくする必要がある。【００１３】
なお、図１８は、検査行列の一例をタナーグラフで表現した場合を示す図であり、｛０，１｝の２元のＭ行×Ｎ列のパリティ検査行列Ｈにおいて、各列に対応するノードをビットノードｂn（１≦ｎ≦Ｎ）と呼び（図中の○に相当）、各行に対応するノードをチェックノードｃm（１≦ｍ≦Ｍ）と呼び（図中の□に相当）、さらに、検査行列の行と列の交点に“１”がある場合にそのビットノードとチェックノードを枝で接続する２部グラフをタナーグラフと呼ぶ。また、上記ループとは、図１８に示すように、特定のノード（図中の○や□に相当）から始まりそのノードで終わる閉路のことを表し、また、内径とは、その最小ループを意味する。また、ループの長さは、閉路を構成する枝の数で表現され、長さに応じて、簡易的にループ４，ループ６，ループ８…と表現する。【００１４】
また、下記非特許文献１においては、（Ｊ，Ｌ）ＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCにおける内径ｇの範囲が、「４≦ｇ≦１２（ｇは偶数）」とされている。ただし、ｇ＝４を回避することは容易であり、多くの場合、ｇ≧６である。【００１５】
【非特許文献１】M.Fossorier  “Quasi-Cyclic  Low  Density  Parity  Check  Code”  ISIT2003,  pp150,  Japan,  June  29-July  4,  2003.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記従来の技術によれば、規則的な構成ながらループ６以上となる符号を容易に構成できる一方で、レギュラー（行と列の重みが一様）なＬＤＰＣ符号用のパリティ検査行列を生成しており、一般に性能が良好とされているイレギュラー（行と列の重みが非一様）なパリティ検査行列については規定されていない、という問題があった。【００１７】
また、符号化の際には、生成行列Ｇを検査行列Ｈとは別に用意する必要があり、生成行列Ｇを計算するための追加回路が必要となる、という問題があった。また、複数の符号化率に対応する場合には、符号化率の数に相当する検査行列Ｈを用意する必要があり、さらに回路規模が大きくなる、という問題があった。【００１８】
本発明は、上記に鑑みてなされたものであって、イレギュラー（行と列の重みが非一様）なＬＤＰＣ符号用のパリティ検査行列に対応するとともに、さらに、従来技術と比較して回路規模を低減可能な通信装置を得ることを目的とする。
【課題を解決するための手段】
【００１９】
上述した課題を解決し、目的を達成するために、本発明にかかる検査行列生成方法は、ＬＤＰＣ符号用のパリティ検査行列を生成する検査行列生成方法であって、たとえば、巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則な擬似巡回行列を用意し、さらに、最終的に生成するパリティ検査行列において所定の最小ループを保証するための条件式を導出し、当該条件式および所定の重み分布に基づいて特定の巡回置換行列を０行列に変換するためのマスク行列を生成するマスク行列生成ステップと、前記マスク行列を用いて前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、を含むことを特徴とする。
【発明の効果】
【００２０】
この発明によれば、特定の規則性を持たせた正則な擬似巡回行列に対して、非正則な行列を生成するための所定のマスキングルールを適用することとしたので、容易にＬＤＧＭ構造の非正則なパリティ検査行列を生成することができる。また、従来のように、生成行列Ｇを生成する必要がないので、回路規模を大幅に削減することができる。
【図面の簡単な説明】
【００２１】
【図１】図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む本実施の形態の通信システムの構成例を示す図である。
【図２−１】図２−１は、符号生成における積和演算部の構成例を示す図である。
【図２−２】図２−２は、図２−１に示す積和演算部を用いた符号生成部の構成例を示す図である。
【図３】図３は、マスク行列生成処理の一例を示すフローチャートである。
【図４】図４は、マスク行列生成処理の一例を示すフローチャートである。
【図５】図５は、本発明にかかる消失訂正ＬＤＰＣ符号化／復号システムの構成例を示す図である。
【図６】図６は、符号構成法の一例を示す図である。
【図７】図７は、符号化率に応じてパリティ検査行列を拡張する場合の一例を示す図である。
【図８】図８は、複数の符号化率に対応した符号の特性を示す図である。
【図９−１】図９−１は、ＬＤＰＣ復号器の構成例を示す図である。
【図９−２】図９−２は、ＬＤＰＣ復号器の構成例を示す図である。
【図１０】図１０は、「巡回近似minアルゴリズム」において行処理を実行する行処理部の構成例を示す図である。
【図１１−１】図１１−１は、「巡回近似minアルゴリズム」において列処理を実行する列処理部の構成例を示す図である。
【図１１−２】図１１−２は、「巡回近似minアルゴリズム」において列処理を実行する列処理部の構成例を示す図である。
【図１２】図１２は、ｎ＝１５の列処理において、Ｍｉｎ２ＬＬＲにｎ＝１５の情報が保持されている場合の処理を示す図である。
【図１３】図１３は、「巡回近似minアルゴリズム」における処理の流れを示すフローチャートである。
【図１４】図１４は、列番号表記を示す図である。
【図１５】図１５は、ＬＤＰＣ復号器の構成例を示す図である。
【図１６】図１６は、移動体通信システムの構成例を示す図である。
【図１７】図１７は、ＱＣ符号のパリティ検査行列の一例を示す図である。
【図１８】図１８は、検査行列の一例をタナーグラフで表現した場合を示す図である。
【符号の説明】
【００２２】
１  ＬＤＰＣ符号化器
２  変調器
３  通信路
４  復調器
５  ＬＤＰＣ復号器
１１  受信ＬＬＲ算出部
１２，１２ａ  復号コア部
２１，２１ａ  途中結果保持部
２２，２２−１，２２−２，２２−Ｇ  行処理部
２３，２３−１，２３−２，２３−Ｇ  列処理部
２４  復号結果判定部
２５，２５ａ  制御部
３１  最小値選択部
３２  符号演算部
３３  ＬＬＲ算出部
４１  α加算部
４２  λ加算部
４３  最小ｋ値比較部
４４  符号演算部
５１  積和演算部
８１  情報Packet生成部
８２  消失ＬＤＰＣ符号化部
８３  送信部
８５  受信部
８６  消失ＬＤＰＣ復号部
８７  情報ビット再生部
１００  移動体端末
１０１  消失訂正ＬＤＰＣ符号化器
１０２  物理層ＬＤＰＣ符号化器
１０３  変調器
１０４  復調器
１０５  物理層ＬＤＰＣ復号器
１０６  消失訂正ＬＤＰＣ復号器
１０７，２０７  アンテナ
２００  基地局
２０１  消失訂正ＬＤＰＣ復号器
２０２  物理層ＬＤＰＣ復号器
２０３  復調器
２０４  変調器
２０５  物理層ＬＤＰＣ符号化器
２０６  消失訂正ＬＤＰＣ符号化器
【発明を実施するための最良の形態】
【００２３】
以下に、本発明にかかる通信装置の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。【００２４】
実施の形態１．
図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む本実施の形態の通信システムの構成例を示す図である。図１において、送信側の通信装置（送信装置と呼ぶ）は、ＬＤＰＣ符号化器１と変調器２を含む構成とし、受信側の通信装置（受信装置と呼ぶ）は、復調器４とＬＤＰＣ復号器５を含む構成とする。【００２５】
ここで、ＬＤＰＣ符号を採用する通信システムにおける符号化処理，復号処理の流れを簡単に説明する。【００２６】
送信装置内のＬＤＰＣ符号化器１では、本実施の形態の検査行列生成方法により生成されたパリティ検査行列、すなわち、後述する所定のマスキングルールに基づいてマスキング処理が行われたＭ行×Ｎ列のパリティ検査行列ＨMQCLを生成する。【００２７】
その後、ＬＤＰＣ符号化器１では、情報長Ｋのメッセージ（ｕ1，ｕ2，…，ｕK）を受け取り、このメッセージおよび上記パリティ検査行列ＨMQCLを用いて、下記（３）式のように、長さＮの符号語ｖを生成する。なお、本実施の形態においては、従来技術において計算していた生成行列Ｇ（Ｋ：情報長，Ｎ：符号語長）を用いずに、情報ビットの符号化処理を行う。
ｖ＝｛（ｖ1，ｖ2，…，ｖN）∈ＧＦ（２）｜（ｖ1，ｖ2，…，ｖN）ＨMQCLT＝０｝
…（３）【００２８】
そして、送信装置内の変調器２では、ＬＤＰＣ符号化器１で生成した符号語ｖに対して、ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭ等の所定の変調方式によりディジタル変調を行い、その変調信号ｘ＝（ｘ1，ｘ2，…，ｘN）を、通信路３を介して受信装置に送信する。【００２９】
一方、受信装置では、復調器４が、通信路３を介して受け取った変調信号ｙ＝（ｙ1，ｙ2，…，ｙN）に対して、上記ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭ等の変調方式に応じたディジタル復調を行い、さらに、受信装置内のＬＤＰＣ復号器５が、復調結果に対して後述する復号アルゴリズム（「巡回近似minアルゴリズム」）による繰り返し復号を実施し、その復号結果（元のメッセージｕ1，ｕ2，…，ｕKに対応）を出力する。なお、上記「巡回近似minアルゴリズム」は、巡回的に最小ｋ値（最小値から昇順にｋ番目まで）のＬＬＲの絶対値のみを更新していく方法であり、正確な最小値ではなく近似的な最小値を用いて繰り返し復号を行う復号法である。【００３０】
つづいて、本実施の形態における検査行列生成方法を詳細に説明する。なお、本実施の形態においては、イレギュラー（重み分布を非一様）なパリティ検査行列を生成することとし、その構造として、ＬＤＧＭ（Low  Density  Generation  Matrix）構造を採用することを前提とする。また、以下において説明する各実施の形態の検査行列生成処理については、通信装置内のＬＤＰＣ符号化器１で実行することとしてもよいし、または、通信装置の外部で予め実行しておくこととしてもよい。通信装置の外部で実行される場合には、生成済みの検査行列を内部メモリに記憶しておく。【００３１】
まず、本実施の形態の検査行列生成処理により生成されるマスキング処理後のイレギュラーなパリティ検査行列ＨMQCLの前提となる、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLを定義する。【００３２】
たとえば、Ｍ（＝ｐＪ）行×Ｎ（＝ｐＬ＋ｐＪ）列のＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCL（＝［ｈm,n］）は、下記（４）式のように定義することができる。【００３３】
【数２】
0004563454.tif 000003
…（４）【００３４】
なお、ｈm,nは、パリティ検査行列ＨQCLにおいて、行番号ｍ，列番号ｎの要素を表す。また、０≦ｊ≦Ｊ−１，０≦ｌ≦Ｌ−１において、Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１），列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列である。【００３５】
上記パリティ検査行列ＨQCLは、左側の行列（情報ビットに対応する部分）が、上記（２）式で示したＱＣ符号のパリティ検査行列と同一の擬似巡回行列ＨQCであり、右側の行列（パリティビットに対応する部分）が、下記（５）式に示すＩ（０）を階段状に配置した行列Ｔである。【００３６】
【数３】
0004563454.tif 000004
…（５）【００３７】
ただし、上記階段状の構造で用いている巡回置換行列は、Ｉ（０）に限定しているわけではなく、任意のＩ（ｓ｜ｓ∈［０，ｐ−１］）の組み合わせでもよい。【００３８】
また、上記ＬＤＧＭ構造とは、上記（４）に示す行列のように、パリティ検査行列の一部を下三角行列にした構造のことをいう。この構造を用いることにより、生成行列Ｇを用いずに符号化を容易に実現できる。たとえば、組織符号語ｖを下記（６）式のように表し、情報メッセージｕ＝（ｕ1，ｕ2，…，ｕK）が与えられた場合、パリティ要素ｐm＝（ｐ1，ｐ2，…，ｐM）は、「ＨQCL・ｖT＝０Ｋ，」を満たすように、すなわち、下記（７）式のように生成する。【００３９】
ｖ＝（ｖ1，ｖ2，…，ｖK，ｖK+1，ｖK+2，…，ｖN）
＝（ｕ1，ｕ2，…，ｕK，ｐ1，ｐ2，…，ｐM）                …（６）
ただし、Ｎ＝Ｋ＋Ｍである。【００４０】
【数４】
0004563454.tif 000005
…（７）【００４１】
さらに、本実施の形態においては、上記（４）のように定義されたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、特定の規則性を設けている。具体的には、パリティ検査行列ＨQCLの左側の擬似巡回行列部分において、行番号ｊ，列番号ｌに配置されたｐ行×ｐ列の巡回置換行列の１行目の列番号が「（ｊ＋ｃ）・（ｌ＋ｄ）」となる特定の規則性を設けている。なお、ｃ、ｄは０以上の任意の整数であり、「（ｊ＋ｃ）・（ｌ＋ｄ）＜ｐ」とする。また、特定の規則性を設けたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLの一例を、下記（８）式に示す。ただし、ｃ＝０，ｄ＝１としている。【００４２】
【数５】
0004563454.tif 000006
…（８）【００４３】
つづいて、本実施の形態の検査行列生成方法における特徴的な処理である、パリティ検査行列ＨQCLに対するマスク処理について説明する。【００４４】
たとえば、上記（８）式に示す左側の擬似巡回行列を、下記（９−１）式に示すように、Ｊ行×Ｌ列の行列ＨQCLLと表し、マスク行列Ｚ（＝［ｚj,l］）をＧＦ（２）上のＪ行×Ｌ列の行列とした場合、後述する所定のルールを適用すると、マスク処理後の行列ＨMQCLLは、下記（９−２）式のように表すことができる。【００４５】
【数６−１】
0004563454.tif 000007
…（９−１）【００４６】
【数６−２】
0004563454.tif 000008
…（９−２）【００４７】
なお、上記（９−２）式におけるｚj,lＩ（ｐj,l）は、下記（１０）式のように定義される。【００４８】
【数７】
0004563454.tif 000009
…（１０）【００４９】
また、上記０行列は、ｐ行×ｐ列の０行列である。また、行列ＨMQCLLは、擬似巡回行列ＨQCLLをマスク行列Ｚの０要素によりマスクし、重み分布を非一様（イレギュラー）にした行列である。ただし、重み分布を非一様にする場合のマスク行列Ｚの重み分布は、既知の密度発展法等で求めることとする。【００５０】
したがって、本実施の形態において、最終的に求めるイレギュラーなパリティ検査行列ＨMQCLは、下記（１１）式のように表すことができる。
ＨMQCL＝［Ｚ×ＨQCLL｜Ｔ］
＝［ＨMQCLL｜Ｔ］                              …（１１）【００５１】
つづいて、レギュラーなパリティ検査行列ＨMQCLを用いて、生成行列Ｇを用いずに符号化を実現する場合の実装例を以下に示し、その動作を説明する。なお、ここでは、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLを、下記（１２−１）式に示す行列とする。【００５２】
【数８−１】
0004563454.tif 000010
…（１２−１）【００５３】
また、上記（１２−１）式に示す行列をマスク化したイレギュラーなパリティ検査行列ＨMQCLを、下記（１２−２）式に示す行列とする。【００５４】
【数８−２】
0004563454.tif 000011
…（１２−２）【００５５】
また、情報メッセージをｕ＝（ｕp,1  ｕp,2）＝（０１１００  １１００１）とする。ただし、ｕp,lは、ｕをｐビット単位で区切り、ｌに対して昇順に番号を付したものである。【００５６】
ここで、生成行列Ｇを用いずに符号を生成する場合の処理として、ｐ行分のマスク処理後の行列ＨMQCLLと情報メッセージｕとの積和演算について説明する。【００５７】
図２−１は、符号生成における積和演算部５１の構成を示す図である。ここでは、基準クロックを１クロックとし、図中、遅延素子（Ｄ）６１は１クロック単位で動作し、遅延素子（Ｄ）６２はｐクロック単位で動作する（この例ではｐ＝５）。また、列カウンタ６３はｐクロック単位で動作し、行カウンタ６４はＬ・ｐクロック単位で動作する（この例ではＬ＝２）。【００５８】
図２−１において、擬似巡回行列ＨQCLLのｊ行ｌ列目の巡回置換行列は、Ｉ（ｊ・（ｌ＋１）），「０≦ｊ≦Ｊ−１」，「０≦ｌ≦Ｌ−１」であるため、行カウンタ６４にてｊを昇順にＬ・ｐクロック単位でカウントし、列カウンタ６３にて「ｌ＋１」を昇順にｐクロック単位でカウントし、乗算器６５にて「ｊ・（ｌ＋１）」を算出し、その値をセレクタ６６に入力し、長さｐのレジスタ６７の“１”の位置を決めることにより、ｊ行ｌ列目の巡回置換行列の１行目の“１”の位置をセットする。【００５９】
一方、情報メッセージｕについては、長さｐ毎に区切り、遅延素子６２を介してｐクロック単位でレジスタ６８，６９に順に入力する。そして、加算器７０にてレジスタ６９内の長さｐの情報メッセージｕとレジスタ６７内のビット列とのＥＸＯＲを計算し、加算器７２にてＥＸＯＲ演算結果の各ビットの総和を計算する。この処理により、Ｉ（ｊ・（ｌ＋１））の１行目と情報メッセージのｕp,lとの積和計算が実現できる。つぎに、レジスタ６７を、遅延素子６１を用いてシフトすることにより、Ｉ（ｊ・（ｌ＋１））の２行目が生成でき、同様に、Ｉ（ｊ・（ｌ＋１））の２行目と情報メッセージのup,lとの積和計算が実現できる。その後、この処理をｐ回にわたって繰り返し実行することにより、Ｉ（ｊ・（ｌ＋１））のｐ行分の積和計算結果ｐp,j´が得られる。なお、ｐp,j´はｊ行目の巡回置換行列全ての積和計算結果のｐビットを意味する。【００６０】
つぎに、ｌ＝０からｌ＝Ｌ−１まで、Ｉ（ｊ・（ｌ＋１））とｕp,lとの積和を計算するために、遅延素子６２と加算器７２により、Ｌ回にわたって繰り返しＥＸＯＲ演算を行う。この操作をｊ＝０からｊ＝Ｊ−１まで繰り返し実行し、マスク処理後の行列ＨMQCLLとｕとの積和計算結果ｐp,j´を得る。なお、セレクタ７３では、ｚj,l＝０のとき０を選択出力し、ｚj,l＝１のとき加算器７１出力を選択出力する。【００６１】
また、図２−２は、図２−１に示す積和演算部５１を用いた符号生成部の構成例を示す図である。ここでは、遅延素子（Ｄ）７４がＬ・ｐクロック単位で動作する。図２−２において、ｐビット単位に昇順にｊに番号を付した系列（パリティビット）をｐp,jとすると、系列ｐp,jは、遅延素子７４と加算器７５によるＥＸＯＲ演算で得られる。すなわち、「ｐp,j＝ｐp,j´＋ｐp,j-1´」を計算する。なお、ｐp,0´＝０である。【００６２】
つづいて、上記擬似巡回行列ＨQCLLをマスク行列Ｚの０要素によりマスクする場合のマスキングルールを具体的に説明する。ここでは、擬似巡回行列ＨQCLLを非正則（イレギュラー）にするためのマスク行列Ｚを、規則的なマスキングルールにより生成する。【００６３】
本実施の形態では、たとえば、マスク後の行列ＨMQCLLの最小ループを８とする場合、マスキングルールとして、上記（９−１）式に示す擬似巡回行列ＨQCLLがループ６を含む条件式を導出する。なお、上記（９−１）式の擬似巡回行列ＨQCLLは、すでに最小ループ（内径）が６であることが分かっている。【００６４】
たとえば、上記（２）式に示す６つの巡回置換行列Ｉ（ｐj1,l1），Ｉ（ｐj2,l1），Ｉ（ｐj2,l2），Ｉ（ｐj3,l2），Ｉ（ｐj3,l3），Ｉ（ｐj1,l3）が下記（１３）式を満たすとき、上記６つの巡回置換行列間では、ループ６が存在する。なお、「ｊ１，ｊ２，ｊ３∈［０，Ｊ−１］」であり、「ｌ１，ｌ２，ｌ３∈［０，Ｌ−１］」である。【００６５】
【数９】
0004563454.tif 000012
…（１３）【００６６】
ここで、上記（１３）式の条件式を、上記（９−１）式に示す擬似巡回行列ＨQCLLに適用した場合について説明する。【００６７】
たとえば、上記（９−１）式に示す擬似巡回行列ＨQCLLにおいて、行方向にａ番目，列方向にｂ番目の巡回置換行列をＩ（ａｂ）と表し、このＩ（ａｂ）から相対的に、行方向にｊｄ番目，列方向にｌｄ番目の位置にある巡回置換行列をＩ（（ａ＋ｊｄ）（ｂ＋ｌｄ））と表す。このとき、上記（２）式のＩ（ｐa+jd,b+ld）が上記（９−１）式のＩ（（ａ＋ｊｄ）（ｂ＋ｌｄ））に対応する。また、上記６つの巡回置換行列については、Ｉ（ａｂ），Ｉ（（ａ＋ｊｄ１）ｂ），Ｉ（（ａ＋ｊｄ１）（ｂ＋ｌｄ１）），Ｉ（（ａ＋ｊｄ２）（ｂ＋ｌｄ１）），Ｉ（（ａ＋ｊｄ２）（ｂ＋ｌｄ２）），Ｉ（ａ（ｂ＋ｌｄ２））と表す。【００６８】
したがって、上記（１３）式で表される条件式を、上記（９−１）式における６つの巡回置換行列に対して適用すると、マスキングルールとして、下記（１４−１）式を導出することができる。【００６９】
【数１０−１】
0004563454.tif 000013
…（１４−１）【００７０】
なお、「（ｊ＋ｃ）・（ｌ＋ｄ）≧ｐ」が存在した場合、擬似巡回符号ＨQCLLの行番号ｊ，列番号ｌに配置されたｐ行×ｐ列の巡回置換行列の１行目の“１”の列番号を「（ｊ＋ｃ）・（ｌ＋ｄ）ｍｏｄ  ｐ」とする。また、この場合、上記（１４−１）式は、下記（１４−２）式となる。【００７１】
【数１０−２】
0004563454.tif 000014
…（１４−２）【００７２】
そして、本実施の形態では、上記（１４−１）式または上記（１４−２）式を満たさないことを条件として、マスク行列Ｚを構成する。これにより、マスク後の行列ＨMQCLLの最小ループが８となることを保証することができる。また、上記（１４−１）式または上記（１４−２）を導出することにより、限られた小さいサイズの条件式によるループ６の検出処理が可能となるため、ループ６を検出が容易となる。なお、以下では、上記（１４−１）式または上記（１４−２）式を、単に（１４）式と表現する。【００７３】
つづいて、本実施の形態の通信装置において実行される、上記マスキングルールに基づくマスク行列生成処理を具体的に説明する。図３は、本実施の形態のマスク行列生成処理を示すフローチャートである。なお、ここでは、本実施の形態のマスク行列生成処理を、通信装置内のＬＤＰＣ符号化部１にて実行する場合の例を示す。【００７４】
まず、通信装置内のＬＤＰＣ符号化器１では、密度発展法により、マスク行列Ｚの行と列の重み分布を計算する（ステップＳ１）。一般の密度発展法では、検査行列Ｈ全体の行と列の重みの分布を求めるため、組み合わせが膨大で、その最適値算出には時間が掛かるが、本実施の形態の処理では、マスク行列のみを対象に密度発展法を行なうため、組み合わせ数も少なく、非常に短時間で重み分布を導出できる。また、ＬＤＰＣ符号化器１は、ループ４の含まない特定の規則性を設けた擬似巡回行列として、たとえば、上記（９−１）式に示す擬似巡回行列ＨQCLLを用意する（ステップＳ２）。【００７５】
つぎに、ＬＤＰＣ符号化器１では、上記擬似巡回行列ＨQCLLに対して上記（１３）式で表される条件式を適用し、上記（１４）式に示す、擬似巡回行列ＨQCLLがループ６を含む条件式を導出する（ステップＳ３）。【００７６】
つぎに、ＬＤＰＣ符号化器１では、マスク行列Ｚにおける行カウンタをｔ＝１とし（ステップＳ４）、上記ステップＳ１において計算しておいた重み分布に基づいて、行重み分の列番号を乱数にて発生させ、この列番号を行番号ｔ＝１における“１”の位置とする（ステップＳ５）。このとき、現在までに生成したマスク行列Ｚの各列重みが、上記ステップＳ１にて計算した列重み数以下かどうかを判定し（ステップＳ６）、規定の列重み数以下であれば（ステップＳ６，Ｙｅｓ）、次の処理に移行し、一方で、規定の列重み数を超える列がある場合には（ステップＳ６，Ｎｏ）、すべての列重みが規定の列重み数以下になるまで、ステップＳ５およびＳ６の処理を繰り返し実行する。【００７７】
その後、上記ステップＳ６の処理において、すべての列重みが規定の列重み以下となった場合、ＬＤＰＣ符号化器１は、現在までに生成されたマスク行列Ｚが上記ステップＳ３にて導出しておいた条件式を満たしているかどうかを判定し（ステップＳ７）、満たしていなければ（ステップＳ７，Ｎｏ）、次の処理に移行し、一方で、満たしている場合には（ステップＳ７，Ｙｅｓ）、すべての列重みが規定の列重み数以下になり、かつ条件式を満たさないようになるまで、ステップＳ５、Ｓ６およびＳ７の処理を繰り返し実行する。【００７８】
そして、上記ステップＳ７の処理において、条件式を満たさないようになった場合、ＬＤＰＣ符号化器１は、マスク行列Ｚにおける行カウンタｔをインクリメントし（ステップＳ８）、さらに、行カウンタｔがＪ＋１になるまで、ステップＳ５〜ステップＳ９の処理を繰り返し実行し（ステップＳ９）、最終的に、Ｊ行×Ｌ列のマスク行列Ｚを出力する。【００７９】
なお、本実施の形態においては、ステップＳ３の処理においてループ６の条件式を導出することとしたが、これに限らず、さらにループ８，ループ１０…の条件式を導出し、その条件式をステップＳ７における判定条件として追加することとしてもよい。また、特にマスク行列が小さい場合は、必ずしもループ６等の条件を全て回避できるマスク行列を検出できるとは限らないため、列重みの大きい順に、ループ６等を回避する条件を除外してもよい。列重みの大きいビットノードに部分的に接続されたチェックノードとの経路によって短いループが存在していても、他に接続されたチェックノードの経路が構成するループが大きければ、性能劣化を起こさない場合があるため、このような処置も有効である。【００８０】
このように、本実施の形態においては、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、擬似巡回行列ＨQC部分の行番号ｊ，列番号ｌに配置された巡回置換行列の１行目の列番号が「（ｊ＋ｃ）・（ｌ＋ｄ）」となる特定の規則性を設け、当該特定の規則性を設けた擬似巡回行列ＨQCLLに対して、イレギュラーな行列を生成するための所定のマスキングルールを適用することとした。具体的には、擬似巡回行列ＨQCLLがループ６を含む条件式を導出し、この条件式を満たさないことを条件としてマスク行列Ｚを構成することによって、マスク後の行列ＨMQCLLの最小ループを８とすることとした。これにより、ＬＤＧＭ構造のレギュラーなパリティ検査行列ＨQCLから、ＬＤＧＭ構造のイレギュラーなパリティ検査行列ＨMQCLを生成することができる。また、従来のように、パリティ検査行列の一部を階段状の構造にしたことにより、生成行列Ｇを用いずに符号化を容易に実現でき、生成行列Ｇを生成する必要がないので、回路規模を大幅に低減することができる。【００８１】
実施の形態２．
前述の実施の形態１においては、上記（４）式のように定義されたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに対して、パリティ検査行列ＨQCLの左側の擬似巡回行列ＨQC部分の行番号ｊ，列番号ｌに配置されたｐ行×ｐ列の巡回置換行列の１行目の“１”の列番号が「（ｊ＋ｃ）・（ｌ＋ｄ）」となる、既知である特定の規則性を設けていた（上記（８）式参照）。しかしながら、上記特定の規則性については、一定の符号化／復号性能が得られるのであれば、上記規則性に限定されるものではない。そこで、実施の形態２においては、前述した実施の形態１とは異なる規則性について提案する。なお、本実施の形態においては、前述した実施の形態１と異なる処理について説明する。【００８２】
本実施の形態においては、上記（４）式のように定義されたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、前述した実施の形態１とは異なる特定の規則性を設けている。具体的には、パリティ検査行列ＨQCLの左側の擬似巡回行列部分において、行番号ｊ，列番号ｌに配置されたｐ行×ｐ列の巡回置換行列の１行目の“１”の列番号が「ｑ(j+c)・ｑ(l+d)」となる規則性を設けた。なお、ｑは正の整数であり、ｃ、ｄは０以上の整数であり、「ｑ(j+c)・ｑ(l+d)＜ｐ」を満たすこととする。また、上記特定の規則性を設けた、本実施の形態のＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLの一例を、下記（１５）式に示す。ただし、ｑ＝２，ｃ＝１，ｄ＝０としている。【００８３】
【数１１】
0004563454.tif 000015
…（１５）【００８４】
つづいて、本実施の形態の検査行列生成方法における特徴的な処理である、パリティ検査行列ＨQCLに対するマスク処理について説明する。【００８５】
たとえば、上記（１５）式に示す左側の擬似巡回行列を、下記（１６）式に示すように、Ｊ行×Ｌ列の行列ＨQCLLと表し、マスク行列Ｚ（＝［ｚj,l］）をＧＦ（２）上のＪ行×Ｌ列の行列とした場合、後述する所定のルールを適用すると、マスク処理後の行列ＨMQCLLは、下記（１７）式，（１８）式のように表すことができる。【００８６】
【数１２】
0004563454.tif 000016
…（１６）【００８７】
【数１３】
0004563454.tif 000017
…（１７）【００８８】
【数１４】
0004563454.tif 000018
…（１８）【００８９】
なお、本実施の形態において、最終的に求めるイレギュラーなパリティ検査行列ＨMQCLは、前述同様、上記（１１）式のように表すことができる。【００９０】
つづいて、上記擬似巡回行列ＨQCLLをマスク行列Ｚの０要素によりマスクする場合のマスキングルールを具体的に説明する。ここでは、前述同様、マスク行列Ｚを規則的なマスキングルールにより生成する。【００９１】
本実施の形態では、たとえば、マスク後の行列ＨMQCLLの最小ループを８とする場合、マスキングルールとして、上記（１６）式に示す擬似巡回行列ＨQCLLがループ６を含む条件式、を導出する。なお、上記（１６）式の擬似巡回行列ＨQCLLは、すでに最小ループ（内径）が６であることが分かっている。また、本実施の形態においても、上記（２）式に示す６つの巡回置換行列Ｉ（ｐj1,l1），Ｉ（ｐj2,l1），Ｉ（ｐj2,l2），Ｉ（ｐj3,l2），Ｉ（ｐj3,l3），Ｉ（ｐj1,l3）が、前述した上記（１３）式を満たすとき、上記６つの巡回置換行列間では、ループ６が存在することになる。【００９２】
ここで、上記（１３）式の条件式を、上記（１６）式に示す擬似巡回行列ＨQCLLの６つの巡回置換行列に適用した場合について説明する。【００９３】
たとえば、上記（１６）式に示す擬似巡回行列ＨQCLLにおいて、行方向にａ番目，列方向にｂ番目の巡回置換行列をＩ（ｑab）と表し、このＩ（ｑab）から相対的に、行方向にｊｄ番目，列方向にｌｄ番目の位置にある巡回置換行列をＩ（ｑ(a+jd)(b+ld)）と表す。このとき、上記（２）式のＩ（ｐa+jd,b+ld）が上記（１６）式のＩ（ｑ(a+jd)(b+ld)）に対応する。また、上記６つの巡回置換行列については、Ｉ（ｑab），Ｉ（ｑ(a+jd1+b)），Ｉ（ｑ(a+jd1+b+ld1)），Ｉ（ｑ(a+jd2+b+ld1)），Ｉ（ｑ(a+jd2+b+ld2)），Ｉ（ｑ(a+b+ld2)）と表す。【００９４】
したがって、上記（１３）式で表される条件式を、上記（１６）式における６つの巡回置換行列に対して適用すると、マスキングルールとして、下記（１９−１）式を導出することができる。【００９５】
【数１５−１】
0004563454.tif 000019
…（１９−１）【００９６】
なお、「ｑ(j+c)・ｑ(l+d)≧ｐ」が存在した場合、擬似巡回符号ＨQCLLの行番号ｊ，列番号ｌに配置されたｐ行×ｐ列の巡回置換行列の１行目の“１”の列番号を「ｑ(j+c)・ｑ(l+d)ｍｏｄ  ｐ」とする。また、この場合、上記（１９−１）式は、下記（１９−２）式となる。【００９７】
【数１５−２】
0004563454.tif 000020
…（１９−２）【００９８】
そして、本実施の形態では、上記（１９−１）式または（１９−２）式を満たさないことを条件として、マスク行列Ｚを構成する。これにより、最小ループが８となることを保証することができる。また、上記（１９−１）式または（１９−２）式を導出することにより、限られた小さいサイズの条件式によるループ６の検出処理が可能となるため、ループ６の検出が容易となる。なお、以下では、上記（１９−１）式または上記（１９−２）式を、単に（１９）式と表現する。【００９９】
なお、本実施の形態のマスク行列生成処理は、図３に示す実施の形態１のフローチャートと基本的に同様であるが、ステップＳ２において用意する似巡回行列ＨQCLLが異なっている。【０１００】
このように、本実施の形態においては、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、擬似巡回行列ＨQC部分の行番号ｊ，列番号ｌに配置された巡回置換行列の１行目の列番号が「ｑ(j+c)・ｑ(l+d)ｍｏｄ  ｐ」となる特定の規則性を設け、当該特定の規則性を設けた擬似巡回行列ＨQCLLに対して、イレギュラーな行列を生成するための所定のマスキングルールを適用することとした。具体的には、擬似巡回行列ＨQCLLがループ６を含む条件式を導出し、この条件式を満たさないことを条件としてマスク行列Ｚを構成することによって、マスク後の行列ＨMQCLLの最小ループを８とすることとした。これにより、ＬＤＧＭ構造のレギュラーなパリティ検査行列ＨQCLから、ＬＤＧＭ構造のイレギュラーなパリティ検査行列ＨMQCLを生成することができる。また、従来のように、生成行列Ｇを生成する必要がないので、回路規模を大幅に低減することができる。【０１０１】
実施の形態３．
前述した実施の形態１においては、たとえば、マスク後の行列ＨMQCLL（上記（９−２）式参照）の最小ループを８とする場合（行列Ｔを含まない）のマスキングルールについて規定したが、一方で、上記（８）式に示した、特定の規則性を設けたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLは、擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、上記マスキングルールを適用して最終的に求めたイレギュラーなパリティ検査行列ＨMQCLは、ループ６を含む可能性がある。そこで、実施の形態３においては、行列Ｔ部分も考慮したマスキングルールを規定することによって、最終的に求めたイレギュラーなパリティ検査行列ＨMQCLからループ６を排除する。以下、前述した実施の形態１と異なる処理について説明する。【０１０２】
本実施の形態においては、上記（８）式に示すパリティ検査行列ＨQCLが擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、前述した実施の形態１で導出した条件に加えて、擬似巡回行列ＨQCLLと行列Ｔとの間で構成されるループ６の条件を導出する。【０１０３】
たとえば、行列Ｔと擬似巡回行列ＨQCLLとの間でループ６が発生する条件は、前述した６つの巡回置換行列において、行列Ｔの縦方向（行方向）に連続するＩ（０）が含まれている場合である。したがって、パリティ検査行列ＨQCLにおける６つの巡回置換行列を、Ｉ（０），Ｉ（０），Ｉ（ａｂ），Ｉ（（ａ±１）ｂ），Ｉ（（ａ＋１）（ｂ＋ｌｄ１）），Ｉ（（ａ＋ｊｄ２）（ｂ＋ｌｄ１））と表すことができる。なお、最初の２つのＩ（０）は、行方向にａ番目と（ａ＋１）番目、あるいは（ａ−１）番目とａ番目、に対応する。【０１０４】
したがって、上記（１３）式で表される条件式を、上記６つの巡回置換行列に対して適用すると、マスキングルールとして、下記（２０−１）式を導出することができる。【０１０５】
【数１６−１】
0004563454.tif 000021
…（２０−１）【０１０６】
なお、「（ｊ＋ｃ）・（ｌ＋ｄ）≧ｐ」が存在した場合、上記（２０−１）式は、下記（２０−２）式となる。【０１０７】
【数１６−２】
0004563454.tif 000022
…（２０−２）【０１０８】
そして、本実施の形態では、上記（１４）式および上記（２０−１）式または上記（２０−２）式を満たさないことを条件として、マスク行列Ｚを構成する。これにより、マスク後のパリティ検査行列ＨMQCLの最小ループが８となることを保証することができる。なお、以下では、上記（２０−１）式または上記（２０−２）式を、単に（２０）式と表現する。【０１０９】
なお、本実施の形態のマスク行列生成処理は、図３に示す実施の形態１のフローチャートと基本的に同様であるが、ステップＳ３において、マスク後のパリティ検査行列ＨMQCLがループ６を含む条件式（上記（１４）式および上記（２０）式）を導出する処理、が異なっている。【０１１０】
このように、本実施の形態においては、前述した実施の形態１の処理に加えて、さらに、パリティ検査行列ＨQCLが擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、擬似巡回行列ＨQCLLと行列Ｔとの間で構成されるループ６の条件を導出することとした。これにより、最終的に求めるパリティ検査行列ＨMQCLの最小ループが８となることを保証することができる。【０１１１】
実施の形態４．
前述した実施の形態１においては、たとえば、マスク後の行列ＨMQCLL（上記（９−２）式参照）の最小ループを８とする場合（行列Ｔを含まない）のマスキングルールについて規定した。また、前述した実施の形態３においては、たとえば、マスク後のパリティ検査行列ＨMQCLの最小ループを８とする場合（行列Ｔを含む）のマスキングルールについて規定した。しかしながら、マスク後の最小ループについては、上記ループ８に限らず、ループ１０，ループ１２，…であってもよい。そこで、実施の形態４においては、一例として、マスク後の行列ＨMQCLL（上記（９−２）式参照）の最小ループを１０とする場合のマスキングルールについて規定した。以下、前述した実施の形態１と異なる処理について説明する。【０１１２】
本実施の形態では、たとえば、行列ＨMQCLLの最小ループを１０とする場合、マスキングルールとして、前述した上記（９−１）式に示す擬似巡回行列ＨQCLLがループ６およびループ８を含む条件式、を導出する。なお、ループ６の条件式は、前述した（１３）式と同様であるため、以下では、ループ８の条件式について記載する。【０１１３】
たとえば、上記（２）式に示す８つの巡回置換行列Ｉ（ｐj1,l1），Ｉ（ｐj2,l1），Ｉ（ｐj2,l2），Ｉ（ｐj3,l2），Ｉ（ｐj3,l3），Ｉ（ｐj4,l3），Ｉ（ｐj4,l4），Ｉ（ｐj1,l4）が下記（２１）式を満たすとき、上記８つの巡回置換行列間では、ループ８が存在する。なお、「ｊ１，ｊ２，ｊ３，ｊ４∈［０，Ｊ−１］」であり、「ｌ１，ｌ２，ｌ３，ｌ４∈［０，Ｌ−１］」である。【０１１４】
【数１７】
0004563454.tif 000023
…（２１）【０１１５】
ここで、上記（２１）式の条件式を、上記（９−１）式に示す擬似巡回行列ＨQCLLに適用した場合について説明する。【０１１６】
たとえば、上記８つの巡回置換行列は、Ｉ（ａｂ），Ｉ（（ａ＋ｊｄ１）ｂ），Ｉ（（ａ＋ｊｄ１）（ｂ＋ｌｄ１）），Ｉ（（ａ＋ｊｄ２）（ｂ＋ｌｄ１）），Ｉ（（ａ＋ｊｄ２）（ｂ＋ｌｄ２）），Ｉ（（ａ＋ｊｄ３）（ｂ＋ｌｄ２）），Ｉ（（ａ＋ｊｄ３）（ｂ＋ｌｄ３）），Ｉ（ａ（ｂ＋ｌｄ３））と表すことができる。【０１１７】
したがって、上記（２１）式で表される条件式を、上記（９−１）式における８つの巡回置換行列に対して適用すると、マスキングルールとして、下記（２２−１）式を導出することができる。【０１１８】
【数１８−１】
0004563454.tif 000024
…（２２−１）【０１１９】
なお、「（ｊ＋ｃ）・（ｌ＋ｄ）≧ｐ」が存在した場合、擬似巡回符号ＨQCLLの行番号ｊ，列番号ｌに配置されたｐ行×ｐ列の巡回置換行列の１行目の“１”の列番号を「（ｊ＋ｃ）・（ｌ＋ｄ）ｍｏｄ  ｐ」とする。また、この場合、上記（２２−１）式は、下記（２２−２）式となる。【０１２０】
【数１８−２】
0004563454.tif 000025
…（２２−２）【０１２１】
そして、本実施の形態では、たとえば、上記（１４）式および上記（２２−１）式または（２２−２）式を満たさないことを条件として、マスク行列Ｚを構成する。これにより、マスク後の行列ＨMQCLLの最小ループが１０となることを保証することができる。なお、以下では、上記（２２−１）式または上記（２２−２）式を、単に（２２）式と表現する。また、本実施の形態においては、マスク後の行列ＨMQCLLの最小ループが１０となることを保証することとしたが、たとえば、上記（１４）式を満たさないことを条件とする場合と、上記（１４）式および上記（２２）式を満たさないことを条件とする場合とを、伝送路状態等に応じて適宜変更することによって、マスク後の行列ＨMQCLLの最小ループが８また１０となることを保証することとしてもよい。さらに、ループ１０，ループ１２，…の条件式を求めることによって、マスク後の行列ＨMQCLLの最小ループが８，１０，１２，…となることを保証することとしてもよい。【０１２２】
また、本実施の形態のマスク行列生成処理は、図３に示す実施の形態１のフローチャートと基本的に同様であるが、ステップＳ３において、マスク後の行列ＨMQCLLがループ６，ループ８，…を含む条件式を導出する処理、が異なっている。【０１２３】
このように、本実施の形態においては、伝送路状態等に応じて、適応的にマスク後の行列ＨMQCLLの最小ループを変更することとした。これにより、伝送路状態等に応じて最適な符号化／復号処理が可能となる。【０１２４】
実施の形態５．
前述した実施の形態４においては、たとえば、マスク後の行列ＨMQCLL（上記（９−２）式参照）に関するループ８の条件式を導出したが、一方で、上記（８）式に示した、特定の規則性を設けたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLは、擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、実施の形態４に示すマスキングルールを適用して最終的に求めたイレギュラーなパリティ検査行列ＨMQCLは、ループ８を含む可能性がある。そこで、実施の形態５では、たとえば、ループ８の条件式の導出において、行列Ｔ部分も考慮したマスキングルールを規定することによって、最終的に求めたイレギュラーなパリティ検査行列ＨMQCLからループ８を排除する。以下、前述した実施の形態４と異なる処理について説明する。【０１２５】
本実施の形態においては、上記（８）式に示すパリティ検査行列ＨQCLが擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、前述した実施の形態４で導出した条件（実施の形態１および実施の形態３で導出した条件を含む）に加えて、擬似巡回行列ＨQCLLと行列Ｔとの間で構成されるループ８の条件を導出する。【０１２６】
たとえば、行列Ｔと擬似巡回行列ＨQCLLとの間でループ８が発生する条件は、前述した８つの巡回置換行列において、行列Ｔの縦方向（行方向）に連続するＩ（０）が含まれている場合である。したがって、パリティ検査行列ＨQCLにおける８つの巡回置換行列を、Ｉ（０），Ｉ（０），Ｉ（ａｂ），Ｉ（（ａ＋ｊｄ１）ｂ），Ｉ（（ａ＋ｊｄ１）（ｂ＋ｌｄ１）），Ｉ（（ａ＋ｊｄ２）（ｂ＋ｌｄ１）），Ｉ（（ａ＋ｊｄ２）（ｂ＋ｌｄ２）），Ｉ（（ａ±１）（ｂ＋ｌｄ２））と表すことができる。なお、最初の２つのＩ（０）は、行方向にａ番目と（ａ＋１）番目、あるいは（ａ−１）番目とａ番目、に対応する。【０１２７】
したがって、上記（２１）式で表される条件式を、上記８つの巡回置換行列に対して適用すると、マスキングルールとして、下記（２３−１）式を導出することができる。【０１２８】
【数１９−１】
0004563454.tif 000026
…（２３−１）【０１２９】
なお、「（ｊ＋ｃ）・（ｌ＋ｄ）≧ｐ」が存在した場合、擬似巡回符号ＨQCLLの行番号ｊ，列番号ｌに配置されたｐ行×ｐ列の巡回置換行列の１行目の“１”の列番号を「（ｊ＋ｃ）・（ｌ＋ｄ）ｍｏｄ  ｐ」とする。また、この場合、上記（２３−１）式は、下記（２３−２）式となる。【０１３０】
【数１９−２】
0004563454.tif 000027
…（２３−２）【０１３１】
そして、本実施の形態では、上記（１４）式、（２０）式、（２２）式、および上記（２３−１）式または上記（２３−２）式を満たさないことを条件として、マスク行列Ｚを構成する。これにより、マスク後のパリティ検査行列ＨMQCLの最小ループが１０となることを保証することができる。以下では、上記（２３−１）式または上記（２３−２）式を、単に（２３）式と表現する。【０１３２】
なお、本実施の形態のマスク行列生成処理は、図３に示す実施の形態１のフローチャートと基本的に同様であるが、ステップＳ３において、マスク後のパリティ検査行列ＨMQCLがループ６およびループ８を含む条件式を導出する処理、が異なっている。【０１３３】
このように、本実施の形態においては、前述した実施の形態４の処理に加えて、さらに、擬似巡回行列ＨQCLLと行列Ｔとの間で構成されるループ８の条件を導出することとした。これにより、最終的に求めるパリティ検査行列ＨMQCLの最小ループが１０となることを保証することができる。【０１３４】
実施の形態６．
前述した実施の形態２においては、たとえば、マスク後の行列ＨMQCLL（上記（１７）式参照）の最小ループを８とする場合（行列Ｔを含まない）のマスキングルールについて規定したが、一方で、上記（１５）式に示した、特定の規則性を設けたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLは、擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、上記マスキングルールを適用して最終的に求めたイレギュラーなパリティ検査行列ＨMQCLは、ループ６を含む可能性がある。そこで、実施の形態６においては、行列Ｔ部分も考慮したマスキングルールを規定することによって、最終的に求めたイレギュラーなパリティ検査行列ＨMQCLからループ６を排除する。以下、前述した実施の形態２と異なる処理について説明する。【０１３５】
本実施の形態においては、上記（１５）式に示すパリティ検査行列ＨQCLが擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、前述した実施の形態２で導出した条件に加えて、擬似巡回行列ＨQCLLと行列Ｔとの間で構成されるループ６の条件を導出する。【０１３６】
たとえば、行列Ｔと擬似巡回行列ＨQCLLとの間でループ６が発生する条件は、前述した実施の形態２における６つの巡回置換行列において、行列Ｔの縦方向（行方向）に連続するＩ（０）が含まれている場合である。したがって、パリティ検査行列ＨQCLにおける６つの巡回置換行列を、Ｉ（０），Ｉ（０），Ｉ（ｑa+b），Ｉ（ｑ(a+jd1+b)），Ｉ（ｑ(a+jd1+b+ld1)），Ｉ（ｑ(a±1+b+ld1)）と表すことができる。なお、最初の２つのＩ（０）は、行方向にａ番目と（ａ＋１）番目、あるいは（ａ−１）番目とａ番目、に対応する。【０１３７】
したがって、上記（１３）式で表される条件式を、上記６つの巡回置換行列に対して適用すると、マスキングルールとして、下記（２４）式を導出することができる。【０１３８】
【数２０】
0004563454.tif 000028
…（２４）【０１３９】
そして、本実施の形態では、上記（１９）式および上記（２４）式を満たさないことを条件として、マスク行列Ｚを構成する。これにより、マスク後のパリティ検査行列ＨMQCLの最小ループが８となることを保証することができる。【０１４０】
なお、本実施の形態のマスク行列生成処理は、図３に示す実施の形態１のフローチャートと基本的に同様であるが、ステップＳ２において、用意する似巡回行列ＨQCLL（上記（１６）式）が異なり、さらに、ステップＳ３において、マスク後のパリティ検査行列ＨMQCLがループ６を含む条件式を導出する処理（上記（１９）式および上記（２４）式）が異なっている。【０１４１】
また、本実施の形態においては、さらに、ループ８，ループ１０，ループ１２，…の条件式を求めることによって、マスク後のパリティ検査行列ＨMQCLの最小ループが１０，１２，１４，…となることを保証することとしてもよい。【０１４２】
このように、本実施の形態においては、前述した実施の形態２の処理に加えて、さらに、パリティ検査行列ＨQCLが擬似巡回行列ＨQCLL部分と行列Ｔ部分で構成されていることから、擬似巡回行列ＨQCLLと行列Ｔとの間で構成されるループ６の条件を導出することとした。これにより、最終的に求めるパリティ検査行列ＨMQCLの最小ループが８となることを保証することができる。【０１４３】
実施の形態７．
前述した実施の形態１〜６においては、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLを用いた所定の探索処理を実行することによって、マスク行列Ｚを構成していたが、実施の形態７においては、上記（８）式に示すパリティ検査行列ＨQCLを用いる場合に限り、上記探索処理を実行することなく、最小ループがループ８となることを保証する。以下、前述した実施の形態１〜６と異なる処理について説明する。【０１４４】
本実施の形態においては、マスク行列Ｚの元となる行列として、たとえば、有限幾何符号の一種であるユークリッド幾何符号を利用する。上記マスク行列Ｚの元となるユークリッド幾何符号ＺEGBを下記（２５）式に示す。【０１４５】
【数２１】
0004563454.tif 000029
…（２５）【０１４６】
そして、本実施の形態においては、上記ユークリッド幾何符号ＺEGBを所定の規則で置換することにより、前述した探索処理を実行することなく、マスク行列ＺEGを生成する。具体的には、巡回行列で表現される２次元の（０，ｓ＝２）次ユークリッド幾何符号ＺEGBを、ＺEGB＝［ｈm,n］，１≦ｍ≦２2s−１，１≦ｎ≦２2s−１とし、さらに、２2s−１が３の倍数の場合、下記（２６）式により置換処理を行う。【０１４７】
【数２２】
0004563454.tif 000030
…（２６）【０１４８】
また、２次元の（０，ｓ＝２）次ユークリッド幾何符号ＺEGBを、ＺEGB＝［ｈm,n］，１≦ｍ≦２2s−１，１≦ｎ≦２2s−１とし、さらに、２2s−１が３の倍数以外の場合、下記（２７）式により置換処理を行う。【０１４９】
【数２３】
0004563454.tif 000031
…（２７）【０１５０】
したがって、上記（２５）式に示すユークリッド幾何符号ＺEGBを、上記（２６）式および（２７）式にしたがって置換した、本実施の形態のマスク行列ＺEGは、下記（２８）式のように表すことができる。【０１５１】
【数２４】
0004563454.tif 000032
…（２８）【０１５２】
なお、２次元の（０、ｓ）次ユークリッド幾何的符号のｓが２以上の整数の場合は、上記操作により、ループ８以上を保証可能なマスクパターンを生成することができる。【０１５３】
つづいて、本実施の形態の通信装置において実行されるマスク行列生成処理を具体的に説明する。図４は、本実施の形態のマスク行列生成処理を示すフローチャートである。【０１５４】
まず、通信装置内のＬＤＰＣ符号化器１では、密度発展法により、マスク行列ＺEGの行と列の重み分布を計算する（ステップＳ１１）。また、ＬＤＰＣ符号化器１は、上記（８）式に示すパリティ検査行列ＨQCLを用意し（ステップＳ１２）、さらに、上記ステップＳ１１において計算した行と列の重み分布に基づいて、所定のユークリッド幾何符号を用意する（ステップＳ１３）。【０１５５】
そして、ＬＤＰＣ符号化器１では、上記（２６）式および（２７）式の処理により、ステップＳ１３において用意したユークリッド幾何符号を置換し、その置換処理結果をマスク行列ＺEGとする（ステップＳ１４）。なお、この構造の場合、巡回置換行列のサイズを変更することにより、符号長を可変にできる。【０１５６】
このように、本実施の形態においては、上記（８）式に示すパリティ検査行列ＨQCLを用いる場合に限り、ユークリッド幾何符号を所定の規則で置換したマスク行列ＺEGを用いてマスク処理を実行し、イレギュラーなパリティ検査行列を生成することとした。これにより、前述したマスク行列の探索処理を実行する必要がなくなるので、計算量を大幅に削減することができる。【０１５７】
実施の形態８．
実施の形態８では、上記（８）式に示すパリティ検査行列ＨQCLに含まれる上記擬似巡回行列ＨQCLLと、上記ユークリッド幾何と、を用いて、消失誤り訂正に用いる符号を構成する。【０１５８】
以下、消失誤り訂正符号を構成する場合における、ＬＤＰＣ符号による通信システムについて説明する。図５は、本発明にかかる消失訂正ＬＤＰＣ符号化／復号システムの構成例を示す図であり、この消失訂正ＬＤＰＣ符号化／復号システムにおいて、送信側の通信装置は、情報Packet生成部８１と消失ＬＤＰＣ符号化部８２と送信部８３とを備え、一方、受信側の通信装置は、受信部８５と消失ＬＤＰＣ復号部８６と情報ビット再生部８７とを備えている。なお、消失訂正符号としてのＬＤＰＣ符号は、送信部８３に送る、あるいは受信部８５から受け取る、特定のサイズにパケット化されたデータに対する誤り訂正符号である。また、受信部８５から受け取るパケットは、受信が成功した場合は、そのパケット内のデータが１００％正しく、受信が失敗した場合には、そのパケット内のデータが消失してしまっているとみなされる。【０１５９】
図５において、情報Packet生成部８１は、情報ビット系列を用いて、予め決められたパケットサイズ長Ｌの単位でかつパケットの位置番号を伴った系列を生成し、その系列をパケット化する。このとき、全パケット数をｋとし、各パケットの系列をＩＰ（１），ＩＰ（２），…，ＩＰ（ｋ）と表し、各系列の引数を位置番号とする。つぎに、消失ＬＤＰＣ符号化部８２は、上記パケットを符号化する。このとき、符号化されたパケットの全パケット数をｋとし、符号化されたパケットの系列をＣ（１），Ｃ（２），…，Ｃ（ｋ）と表し、各系列の引数を位置番号とする。【０１６０】
その後、符号化されたパケットは送信部８３に送られ、ここでは、変調等の処理を施した後の信号を通信路８４に送信する。なお、通信路８４はノイズ等が存在する場合を想定する。【０１６１】
一方、通信路８４を経由した信号は受信部８５にて受信され、ここでは、受信に成功したパケットだけが消失ＬＤＰＣ復号部８６に送られる。すなわち、消失ＬＤＰＣ復号部８６では、成功したパケットのみを受け取るため、位置番号が欠落したパケットの系列、たとえば、Ｃ（１），Ｃ（３），Ｃ（７），…，Ｃ（ｋ）のパケットの系列を受け取り、このパケットからＩＰ（１），ＩＰ（２），…，ＩＰ（ｋ）を生成する。そして、情報ビット再生部８７では、受け取ったパケットから送信情報ビット系列を再生する。【０１６２】
つづいて、上記消失訂正ＬＤＰＣ符号化／復号システムにおける符号化処理／復号処理について詳しく説明する。【０１６３】
たとえば、簡単のためにパケットサイズ長Ｌ＝１と仮定する。この仮定の元で、Ｉ1＝ＩＰ（１），Ｉ2＝ＩＰ（２），Ｉ3＝ＩＰ（３），…，Ｉk＝ＩＰ（ｋ）、ｃ1＝Ｃ（１），ｃ2＝Ｃ（２），ｃ3＝Ｃ（３），…，ｃk＝Ｃ（ｋ）、のように置き換える。また、Ｉ＝（Ｉ1  Ｉ2  Ｉ3  …  Ｉk）とし、Ｃ＝（Ｃ1  Ｃ2  Ｃ3  …  Ｃk）とし、消失訂正用の検査行列をＨersとすると、下記（２９）式のように符号化することができる。なお、（・）Tは転置行列を意味する。【０１６４】
【数２５】
0004563454.tif 000033
…（２９）【０１６５】
消失ＬＤＰＣ符号化部８２は、このＣを送信部８３へ渡し、受信部８５は、通信路８４経由で、受信が成功したパケットのみを受け取る。以下、パケット長がＬ＝１なので、パケットをビットに置き換えて説明する。消失訂正符号は、｛０，１｝の２元消失通信路を仮定した場合、受信した情報長以上のビット数の受信ビットを使って復号する。たとえば、受信が成功したビットは、確率１で受信ビットを受けたと仮定し、受信が失敗したビットは、確率１／２で０か１を受信したと仮定する。一般に、受信が失敗したビットは無視し、受信が成功したビットのみで復号する。この際、たとえば、検査行列Ｈersを使って受信が成功したビットに対応する行のみを抽出し、行毎に連結し、復号用の行列を再構成する。このとき、この行列のランクが情報長と同じであれば、情報ビットを復号できる。この復号においては、ループ長が長い方が、検査行列の任意の行を抽出した際に線形従属の行が少なくなり、情報長以上の少ない受信成功ビット数でランクが情報長となる確率が高くなる。【０１６６】
そこで、この消失訂正用の検査行列Ｈersとして、ループ長を長くすることが可能な、前述の実施の形態１〜６に示すＴを含まない擬似巡回行列ＨQCLLやマスク化擬似巡回行列ＨMQCLLを用いることができる。【０１６７】
また、ユークリッド幾何符号における特定の列の“１”の位置を、多項式を使って表現し、巡回行列を生成すると、ループ４を含まない２２行×１５列の巡回行列ＺEGBEを構成できる。具体的には、上記（２５）式の一行目の“１”の列番号に対応した多項式を、ｙ＝ｘ0＋ｘ1＋ｘ3＋ｘ7と表現する。そして、この多項式を、１列目の“１”の行番号に対応した多項式表現とし、下記（３０）式に示すように、１列移動毎に１行ずつシフトした巡回行列を、ＺEGBEとする。この行列ＺEGBEもそれ自体ループ４を含まないのでＨersとして用いることができる。【０１６８】
【数２６】
0004563454.tif 000034
…（３０）【０１６９】
さらに、上記（３０）式に示す、２次元の（０，ｓ＝２）次ユークリッド幾何符号ＺEGBEを、ＺEGBE＝［ｈm,n］，１≦ｍ≦Ｍ，１≦ｎ≦Ｎとした場合、このユークリッド幾何符号ＺEGBEを用いて、上記（２８）式の作成時と同様な操作で、すなわち、下記（３１）式および（３２）式の処理により、下記（３３）式に示す行列ＺEGEを生成する。【０１７０】
(I)Ｍが３の倍数の場合：【０１７１】
【数２７】
0004563454.tif 000035
…（３１）【０１７２】
(II)Ｍが３の倍数以外の場合：【０１７３】
【数２８】
0004563454.tif 000036
…（３２）【０１７４】
【数２９】
0004563454.tif 000037
…（３３）【０１７５】
この場合、この行列ＺEGE，情報長１５ビット（長さＫ）の情報Ｉを用いて、非組織的符号長２２ビット（長さＮ）の消失訂正符号Ｃを、下記（３４）式にて生成する。また、（９−２）式を用いて行列ＨMQCLL（＝ＺEGE×ＨQCLL）を生成し、このイレギュラーな行列ＨMQCLL，情報長１５ビット（長さＫ）の情報Ｉを用いて、非組織的符号長２２ビット（長さＮ）の消失訂正符号Ｃを生成することとしてもよい。【０１７６】
【数３０】
0004563454.tif 000038
…（３４）【０１７７】
実施の形態９．
実施の形態９では、前述した実施の形態１〜７にて求めたイレギュラーなパリティ検査行列ＨMQCL、すなわち、上記（１１）式に示すマスク化擬似巡回符号のパリティ検査行列ＨMQCL（＝［Ｚ×ＨQCLL｜Ｔ］：実施の形態７の場合はＺをＺEGに置き換える）を用いて、複数の符号化率に対応したＬＤＰＣ符号を構成する。【０１７８】
本実施の形態においては、特定の符号化率の符号語を基準とし、基準符号語より高い符号化率に関してはパンクチャを行い（符号語のパリティを間引く）、低い符号化率に関してはパリティを増加させる。このとき、本実施の形態では、符号化率に応じて個別にパリティ検査行列を生成することなく、一つのパリティ検査行列ＨMQCLを用いて上記処理を実現する。図６は、本実施の形態の符号構成法を示す図であり、たとえば、符号化率０．５の符号を基準符号語とし、それよりも高い符号化率に関してはパリティのパンクチャを行い、低い符号化率に関してはパリティを追加している。【０１７９】
ここで、上記処理を具体的に説明する。本実施の形態においては、一つのパリティ検査行列ＨMQCLで複数の符号化率を実現するために、図７のように、符号化率０．５を基準にパリティ検査行列ＨMQCLを拡張して、低符号化率（図７の例では１／３）に対応したパリティ検査行列を生成する。上記パリティ検査行列拡張時の次数分布は、密度発展法にて計算する。【０１８０】
なお、図７において、Ｍ１行×Ｎ１列の検査行列は符号化率０．５に対応し、Ｍ２行×Ｎ２列の検査行列は、Ｍ１行×Ｎ１列の検査行列の構成を維持した状態で符号化率１／３に対応している。また、図中右側のＩは、単位行列を示し、拡張後のパリティ検査行列がＬＤＧＭ構造を維持するために配置される。また、図中左側のＩも単位行列を示しているが、この部分については、これに限定されるものではなく、良好な性能が得られる行列であればどのような行列を配置してもよい。【０１８１】
一方、高符号化率に関しては、パリティのパンクチャにより対応する。具体的には、Ｍ１行×Ｎ１列の検査行列（符号化率０．５用）を用いて符号語を作成し、作成した符号語から、Ｐの部分の列に対応するパリティビットを規則的または不規則なインターバルで削除し、符号化率０．５よりも大きい符号化率の符号を生成する。【０１８２】
たとえば、符号化率０．５の組織符号語ｖをｖ＝（ｕ1，ｕ2，…，ｕK，ｐ1，ｐ2，…，ｐM1）とし、パリティをｐ＝（ｐ1，ｐ2，…，ｐM1）とし、このパリティが符号化率０．５に対応している場合、符号化率０．６に対応する符号語は、上記ｐの要素の１／３をパンクチャすることにより生成する。その場合、パンクチャするパリティの位置ｐ´は、たとえば、ｐ´＝（ｐ1，ｐ4，ｐ7，ｐ10，…）とする。また、パンクチャのパターンについては、可能な限りビット間隔を空けることとする。これは、ＬＤＧＭ構造のパリティ検査行列により生成したパリティビットが連続して“１”あるいは“０”になるケースが多いためである。具体的な回路構成に基づいて説明すると、図２−２に示す符号化器の回路例では、ｐp,jがパリティに相当しており、ｐp,j＝（１  ０  １  ０  １  ０  １  １  ０  １  １  ０  ０  ０  １）がこの符号化器で生成されるが、たとえば、偶数番目のビットをパンクチャすることによりパンクチャ後のパリティｐp,jpuncは、ｐp,jpunc＝（１  １  １  １  ０  １  ０  １）となる。【０１８３】
図８は、上記処理により生成した複数の符号化率に対応した符号の特性を示す図である。本実施の形態の符号構成法では、たとえば、情報長１４００程度の場合、符号化率１／３，１／２，２／３，３／４，４／５，５／６，６／７，７／８，８／９の全てにおいて、ＢＥＲ＝１０-4点シャノン限界から１．５ｄＢ以内の性能を実現している。【０１８４】
このように、本実施の形態においては、特定の符号化率の符号語を基準とし、基準符号語より高い符号化率に関してはパリティのパンクチャを行い、低い符号化率に関してはパリティを増加させることとし、その際、符号化率に応じて個別にパリティ検査行列を生成することなく、一つのパリティ検査行列ＨMQCLを用いて、上記パンクチャ処理およびパリティ追加処理を実現することとした。これにより、容易に複数の符号化率に対応できるとともに、さらに、符号化率の数に相当するパリティ検査行列を用意する必要がなくなるので、従来と比較して回路規模を大幅に削減できる。【０１８５】
実施の形態１０．
つづいて、前述した実施の形態１〜９の処理で生成されたイレギュラーなパリティ検査行列ＨMQCLを用いた符号化処理、に対応する復号処理について説明する。【０１８６】
以下において説明する本実施の形態の「巡回近似minアルゴリズム」は、たとえば、一般的な「Sum-Productアルゴリズム」の近似復号法である「Min-Sumアルゴリズム」を改良した復号アルゴリズムであり、この「巡回近似minアルゴリズム」は、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新していく方法であり、正確な最小値ではなく近似的な最小値を用いて復号する方法である。なお、上記最小ｋ値とは、「最小値から昇順にｋ番目まで」を表す。【０１８７】
つづいて、本発明にかかる受信装置を構成するＬＤＰＣ復号器５の構成、およびＬＤＰＣ復号器５による復号方法を、図面にしたがって詳細に説明する。【０１８８】
図９−１は、本実施の形態のＬＤＰＣ復号器５の構成を示す図であり、このＬＤＰＣ復号器５は、受信情報から受信ＬＬＲ（対数尤度比）を算出する受信ＬＬＲ算出部１１と復号処理を行う復号コア部１２で構成されている。また、復号コア部１２は、復号の途中結果（中間値）を保持しておくためのメモリで構成された途中結果保持部２１と、行処理を実行する行処理部２２と、列処理を実行する列処理部２３と、復号処理の停止規範として、列処理における事後値の硬判定およびパリティ検査結果の正誤判定を行う復号結果判定部２４と、復号の繰り返し制御を行う制御部２５と、を備えている。【０１８９】
ここで、上記受信装置において実施される「巡回近似minアルゴリズム」を以下に示す。なお、通信路として２値入力ＡＷＧＮ通信路を仮定した場合、第ｎシンボルの対数尤度比λnは、下記（３５）式となる。【０１９０】
【数３１】
0004563454.tif 000039
…（３５）【０１９１】
ただし、ｘnは２元｛０，１｝の第ｎシンボルの値であり、送信側では、このｘnに対して、下記（３６）式の変調をかけて送信する。【０１９２】
【数３２】
0004563454.tif 000040
…（３６）【０１９３】
また、通信路では分散値σ2のノイズベクトルｅ＝（ｅ1，ｅ2，…，ｅn，…，ｅN）が付加され、受信側では、下記（３７）式に示す受信値ｙ＝（ｙ1，ｙ2，…，ｙn，…，ｙN）を受信する。【０１９４】
【数３３】
0004563454.tif 000041
…（３７）【０１９５】
また、前述した実施の形態８に示すパンクチャと検査行列の拡張を併用したＬＤＰＣ符号の検査行列を使用する場合、ＬＤＰＣ復号器５においてパンクチャするビットの対数尤度比λnは、下記（３８）式となる。【０１９６】
【数３４】
0004563454.tif 000042
…（３８）【０１９７】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定する。さらに、初期時におけるｍ行目の最小ｋ値のＬＬＲをβmn(i)(0)として、受信ＬＬＲ：λnを入力し、下記（３９）式に示すようにＢmn(i)を求める。また、初期時におけるｍ行目のＬＬＲ：βmn(0)の符号として、ｓｇｎ（λn）を入力し、下記（３９）式に示すようにＳmを求める。【０１９８】
【数３５】
0004563454.tif 000043
…（３９）【０１９９】
ただし、Ｂmn(i)は、ｍ行目の最小ｋ値のＬＬＲ：βmn(i)の絶対値であり、ｎ（ｉ）は、Ｂmn(i)の中で最小ｉ番目のＬＬＲの列番号であり、Ｓmは、ｍ行目のＬＬＲ：βmnの符号（＋または−）の積である。【０２００】
（行処理ステップ）
つぎに、行処理として、１≦ｎ≦Ｎおよび各ｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４０）式により更新する。なお、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０２０１】
【数３６】
0004563454.tif 000044
…（４０）【０２０２】
具体的には、現在の列番号がｎの場合、「ｎ´＜ｎ」を満たす列番号については、ｌ回目の列処理で更新されたＬＬＲ：βmn'(l)の符号の積をとり、また、「ｎ´＞ｎ」を満たす列番号については、（ｌ−１）回目の列処理で更新されたＬＬＲ：βmn'(l-1)の符号の積をとり、そして、それらの結果とｍ行目の最小ｋ値中の最小のＬＬＲ：ｍｉｎ［βmn'］との乗算結果を、列番号ｎの更新後のＬＬＲ：αmn(l)としている。なお、本実施の形態においては、さらに、上記βmn'(l)の符号の積と上記βmn'(l-1)の符号の積と乗算する項を、（ｌ−１）回目に更新されたＳmと（ｌ−１）回目に更新されたβmn'の符号とを乗算する項に、置き換えることとした。これにより、さらに、計算量およびメモリ量を削減できる。なお、上記（４０）式のＮk（ｍ）は、ｍ行目のｎ（ｉ）の集合であり、Ｎk（ｍ）＝｛ｎ（１），ｎ（２），…，ｎ（ｋ）｝と表す。【０２０３】
（列処理ステップ）
つぎに、列処理として、各ｍ，ｎについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（４１）式により更新する。【０２０４】
【数３７】
0004563454.tif 000045
…（４１）【０２０５】
具体的には、列番号ｎにおいて、受信ＬＬＲ：λnと、ｌ回目の行処理で更新されたｍ行目以外のＬＬＲ：αm'n(l)の合計値と、の加算結果を、更新後のＬＬＲ：βmn(l)としている。また、上記Ｓm´とｌ回目の列処理で更新されたβmn(l)の符号（＋または−）とを乗算することにより、行処理にて使用するＳmを更新している。なお、上記（４１）式における下の２つの式は、Ｂmn(1)の並べ替え処理（最小ｋ値）を規定したものである。【０２０６】
また、各ｎについて、硬判定のための、ビットｎの繰り返しｌ回目の事後値βn(l)を下記（４２）式により更新する。【０２０７】
【数３８】
0004563454.tif 000046
…（４２）【０２０８】
（停止規範）
その後、たとえば、ビットｎの繰り返しｌ回目の事後値βn(l)が「βn(l)＞０」の場合には、復号結果を「ｘn´＝１」とし（ｘ´は元の送信信号ｘに対応）、一方、「βn(l)≦０」の場合には、復号結果を「ｘn´＝０」とし、復号結果ｘ´＝（ｘ1´，ｘ2´，…，ｘN´）を得る。【０２０９】
そして、パリティ検査の結果が「Ｈｘ´＝０」または繰り返し回数が「ｌ＝ｌmax」の場合（いずれか１つの条件を満たしている場合）に、そのときの復号結果ｘ´を出力する。なお、上記２つの条件のどちらも満たしていない場合は、「ｌ＝ｌ＋１」とし、上記行処理に戻り、以降、順に演算を実行する。【０２１０】
つぎに、上記「巡回近似minアルゴリズム」を実行するＬＤＰＣ復号器５の特徴的な動作を、構成図を用いて具体的に説明する。【０２１１】
図１０は、上記「巡回近似minアルゴリズム」において行処理を実行する行処理部２２の構成例を示す図であり、この行処理部２２は、最小値選択部３１と符号演算部３２とＬＬＲ算出部３３から構成されている。なお、図示のＭｉｎ１ＬＬＲ（ｍ行目における最小のＬＬＲ）はＢmn(1)であり、Ｍｉｎ２ＬＬＲ（ｍ行目における最小２番目のＬＬＲ）はＢmn(2)であり、それぞれ途中結果保持部２１に保持された値である。また、図示のＳmおよび「（１−１）回目のｍ行ｎ列目のＬＬＲ：βmnの符号」についても、それぞれ途中結果保持部２１に保持された値である。【０２１２】
最小値選択部３１では、行処理の対象となっている列番号ｎとＭｉｎ１ＬＬＲ（Ｂmn(1)）の列番号ｎ（１）とが一致している場合は、Ｍｉｎ２ＬＬＲ（Ｂmn(2)）を選択し、それ以外の場合は、Ｍｉｎ１ＬＬＲ（Ｂmn(1)）を選択し、出力する。また、符号演算部３２は、「（ｌ−１）回目の列処理で更新されたＳm」および「（１−１）回目のｍ行ｎ列目のＬＬＲ：βmnの符号」を乗算し、その結果としてＳm´を出力する。このとき、Ｓm´は、途中結果保持部２１に保持される。また、ＬＬＲ算出部３３は、最小値選択部３１から得られる最小のＬＬＲと符号演算部３２から得られる符号の乗算結果Ｓm´（＋または−）とを乗算することによって、ＬＬＲ：αmn(l)を算出する。この構成により、「Min-Sumアルゴリズム」においては行重み分だけ必要であったメモリを、ｋ値分に縮小できる。【０２１３】
図１１−１は、上記「巡回近似minアルゴリズム」において列処理を実行する列処理部２３の構成例を示す図であり、この列処理部２３は、α加算部４１とλ加算部４２と最小ｋ値比較部４３と符号演算部４４から構成されている。なお、本実施の形態では、ｋ＝３の場合を一例として記載している。また、図示の列重み分のＬＬＲ，αmn，λn，Ｓm´，Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲ（ｍ行目における最小３番目のＬＬＲ）は、それぞれ途中結果保持部２１に保持された値である。【０２１４】
上記列処理部２３では、α加算部４１が、ｌ回目の行処理で更新されたｍ行目以外のすべてのＬＬＲ：αm'n(l)を加算し、さらに、λ加算部４２が、α加算部４１による加算結果に受信ＬＬＲ：λnを加算し、βmn(l)を出力する。そして、最小ｋ値比較部４３（ｋ＝３）は、｜βmn(l)｜を受け取る。ここで、図１１−１に図示はしていないが、たとえば、列処理の対象となるｎ列目のｎと、Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲにそれぞれ保持されているＢmn(1)，Ｂmn(2)，Ｂmn(3)に対応する列番号を示すｎ（１），ｎ（２），ｎ（３）のいずれかが一致した場合、ｎ＝ｎ（ｉ）となるＢmn(i)を間引きし、図１２に示すような操作を行う。具体的には、Ｍｉｎ２ＬＬＲに保持されている情報を削除し、Ｍｉｎ３ＬＬＲに保持されている情報をＭｉｎ２ＬＬＲに移動し、さらに、Ｍｉｎ３ＬＬＲには、たとえば（１６ビットの場合）、最大値“ＦＦＦＦ”を格納する。これにより、処理対象の列を除いた比較処理が可能となるとともに、少なくともＭｉｎ３ＬＬＲが列処理において必ず更新されることになる。この処理後、図１１−１に示すとおり、｜βmn(l)｜と、Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲと、をそれぞれ比較し、「｜βmn(l)｜＜Ｍｉｎ３ＬＬＲ」であれば、最小３値のＬＬＲを更新する。一方、λ加算部４２が出力するβmn(l)の符号を「ｌ回目のｍ行ｎ列目のＬＬＲ：βmn(l)の符号」として途中結果保持部２１に保持し、さらに、符号演算部４４が、ｌ回目の行処理で更新されたＳm´と上記βmn(l)の符号とを乗算し、その結果を用いて途中結果保持部２１に保持されたＳmを更新する。なお、｜βmn(l)｜とＭｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲとの比較の際に、｜βmn(l)｜をＢmn(i)の中心の値であるＭｉｎ２ＬＬＲと最初に比較し、それ以降、図示のように、ツリー状に比較するようにしたが、たとえば、最小値であるＭｉｎ１ＬＬＲから比較する場合に比べ、実行時間が｛（ｋ＋１）／２｝／ｋ（ｋが奇数の場合）となる効果がある。また、ｋが偶数の場合には、Ｂmn(i)の中心の値は２個になるが、最初に比較を開始する対象は、そのいずれであってもよい。ｋが偶数の場合は、最小値であるＭｉｎ１ＬＬＲから比較する場合に比べ、実行時間が｛ｋ／２＋１｝／ｋ（ｋが偶数の場合）となる効果がある。【０２１５】
また、上記と同じ処理を、図１１−２に示す構成でも実現することができ、その際、α加算部４１では、列重み分のすべてのＬＬＲの加算のみを行い、その後、λ加算部４２でλnの加算を行い、その結果を復号結果判定部２４に出力するとともに、ｍ行目のＬＬＲであるαmnの減算を行う。このような手順でも上記処理の手順と同一の結果を得ることができる。この際のＬＤＰＣ符号器の構成は図９−２のようになる。【０２１６】
つぎに、本実施の形態の「巡回近似minアルゴリズム」における処理の流れを、図１３のフローチャートを用いて説明する。【０２１７】
上記「巡回近似minアルゴリズム」においては、まず、受信ＬＬＲ計算部１１が、受信情報から受信ＬＬＲを算出し（ステップＳ３１，Ｓ３２）、その結果を初期値として途中結果保持部２１に設定し（ステップＳ３３）、さらに、制御部２５が、繰り返し回数をｌ＝１と初期化する（ステップＳ３３）。また、列処理部２３のうち、λ加算部４２，最小ｋ値比較部４３，符号演算部４４を用いて、ｎ＝１からｎ＝Ｎまで巡回的に、上記（３９）式の演算を行う（ステップＳ３３）。【０２１８】
つぎに、復号コア部１２は、制御部２５の制御により、ｌ回目（１回目〜最終回）の繰り返し復号演算を行う（ステップＳ３４）。具体的には、繰り返し復号の１回目として、行処理部２２が、１列目に“１”を持つ行に対して行処理（受信ＬＬＲを使用）を行い、その結果を列処理部２３へ受け渡す。その後、列処理部２３が、１列目の列処理を行い、その結果であるＢmn(i)とＳmを、途中結果保持部２１に保持する（更新する）。以降、２列目，３列目，…Ｎ列目の順に、上記と同様の処理を行い、それぞれＢmn(i)とＳmを、途中結果保持部２１に保持する（繰り返し復号１回目に相当）。その後、繰り返し復号の２回目以降は、１つ前の処理で更新されたＬＬＲおよびＳmを用いて行処理を行い、それ以外は、上記１回目と同様に復号処理を行う。【０２１９】
また、上記ｌ回目の繰り返し復号を実施後、復号結果判定部２４が、繰り返しｌ回目で算出した事後値を硬判定し、その判定値を復号結果ｘ´として決定し、さらにパリティ検査を行う（停止規範）。そして、この停止規範において、パリティ検査結果がＯＫ（「Ｈｘ´＝０」）となるか、または繰り返し回数がｌ＝ｌmaxとなった場合に、最終的にそのときの復号結果ｘ´を出力する（ステップＳ３５）。なお、上記２つの条件を満たしていない場合は、制御部２５がｌ＝ｌ＋１とし、復号コア部１２においては、（ｌ＋１）回目の繰り返し復号を実行する。【０２２０】
つぎに、列番号の表記方法によるメモリサイズの削減について説明する。図１４は、本実施の形態の列番号表記を示す図である。「巡回近似minアルゴリズム」では、たとえば、列番号をｎ＝０から昇順に表記することとした。また、従来、列番号ｎを、パリティ検査行列の列番号そのもの（絶対列番号）で表現していたが、本実施の形態においては、パリティ検査行列におけるｍ行目の“１”の最小の列番号をｎ＝０とし、ｍ行目の次の“１”の列番号をｎ=１とし、以降、“１”毎にｎ＝２，３，…とする相対的列番号で表現することとした。すなわち、従来は、パリティ検査行列の“１”の絶対列番号が、たとえば、“３２７６８”である場合、列番号を表現するために必要なビット数が１５ビットとなるが、一方、本実施の形態においては、たとえば、行重みが８個であれば０〜７を表現できる３ビットまで、行重みが１６個であれば０〜１５を表現できる４ビットまで、メモリサイズを縮小することができる。【０２２１】
以上にように、本実施の形態では、ＬＤＰＣ復号において、行処理のためのＬＬＲの絶対値｜βmn｜を、巡回構造により行単位に最小ｋ値に縮小することとしたので、それらを保持するためのメモリ量を大幅に削減することができる。たとえば、行重みが２０でｋ＝３の場合は、従来と比較してメモリ量を３／２０に削減することができる。また、列番号を、絶対列番号（1,3,10,15…）から相対的列番号（0,1,2,3…）に変更することにより、さらにメモリ量を削減することができる。【０２２２】
つづいて、前述した実施の形態８の処理により構成された符号に対する復号処理として、たとえば、一般的な「Sum-productアルゴリズム」または上記「巡回近似minアルゴリズム」を用いた場合の効果について説明する。【０２２３】
一般的な「Sum-productアルゴリズム」では、行毎に行重み分のＬＬＲを保存し、かつ列毎に行重み−１回分の関数計算を行う必要があったが、「巡回近似minアルゴリズム」では、行毎に最小値から昇順にｋ個の行重み分のＬＬＲを保存し、かつ列毎にｋ回分の関数計算を行なえばよい。たとえば、「巡回近似minアルゴリズム」では、行重み３０に対して、ｋが３〜５個程度でよいことがわかっているため、メモリ量は「Sum-productアルゴリズム」の３／３０〜５／３０に削減でき、計算量も「Sum-productアルゴリズム」の行処理と比較して３／３０〜５／３０に削減できる。【０２２４】
一方、ＬＤＰＣ符号の符号化率が高くなると、一般に行重みは増える。たとえば、列重みｃｗ＝４、行重みｒｗ＝８のレギュラーＬＤＰＣ符号の場合、符号化率ｒａｔｅと行重み列重みとの関係は、パリティ検査行列がフルランクの場合、「ｒａｔｅ＝（ｒｗ−ｃｗ）／ｒｗ」となる。上記の場合、「ｒａｔｅ＝（８−４）／８＝０．５」となる。したがって、列重みが一定で符号化率が高くなると、行重みは大きくなる。たとえば、列重みｃｗ＝４で符号化率ｒａｔｅ＝０．９の場合、「ｒａｔｅ＝（ｒｗ−ｃｗ）／ｒｗ」は、「０．９＝（ｒｗ−４）／ｒｗ」となり、ｒｗ＝４０となる。【０２２５】
このような高符号化率の行重みの大きい符号の場合は、一般の「Sum-productアルゴリズム」を実行すると、行処理の計算量が大きくなる。また、高符号化率の行重みの大きいＬＤＰＣ符号に対しては、「巡回近似minアルゴリズム」で用いる最小ｋ値のｋの値が大きくなる場合がある。たとえば、行重みが１０以下の符号化率０．６程度では、ｋ＝３で十分だったものが、行重みが３０以上になると、ｋが５以上必要な場合がある。【０２２６】
そこで、行重みが小さいことによりｋ＝３で十分な性能が得られる符号化率ｒａｔｅ＝０．５程度以下の符号は、パンクチャなしでパリティ検査行列の拡張により符号を構成する。そして、行重みが増えることによりｋ用のメモリが増える場合には、パンクチャを取り入れることとした（実施の形態８参照）。パンクチャを取り入れることにより、一般の「Sum-productアルゴリズム」を実行する場合の内部メモリを小さくできる。また、パンクチャを取り入れることで行重みを増やすことなく高い符号化率を実現できるので、「巡回近似minアルゴリズム」を採用する場合においては、行重みが増えないのでｋの数を増やさなくても復号特性を劣化させることがない。すなわち、ｋ用のメモリを増やすことなく、復号特性を劣化させずに全ての符号化率に対応できる。なお、本実施の形態では、行毎に最小値から昇順にｋ個の行重み分のＬＬＲを保存する場合について説明したが、最小値から昇順にｋ個のうちｊ個（ｊ≦ｋ）の行重み分のＬＬＲを保存するようにしてもよい。【０２２７】
実施の形態１１．
つづいて、前述した実施の形態１〜９の処理で生成されたイレギュラーなパリティ検査行列ＨMQCLを用いた符号化処理、に対応する復号処理（実施の形態９とは異なる復号処理）について説明する。【０２２８】
本実施の形態のＬＤＰＣ復号は、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を、１ビットずつまたは予め定めた複数ビットずつ行う場合に適用可能であり、たとえば、演算処理を並列化することにより、繰り返し回数の低減を図る。なお、本実施の形態においては、途中結果保持部のＢmn(i)およびＳmを、並列化の数にかかわらず１セットとし、並列化されたすべての処理部が同一のＢmnCおよびＳmを更新していく、いわゆる「Overlapped」されたＢmnCおよびＳmを用いた「巡回近似minアルゴリズム」を実行する。以降、本実施の形態の復号アルゴリズムを、「Overlapped巡回近似minアルゴリズム」と呼ぶ。【０２２９】
ここで、本実施の形態の受信装置において実施される「Overlapped巡回近似minアルゴリズム」を以下に示す。【０２３０】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定する。さらに、初期時におけるｍ行目の最小ｋ値のＬＬＲをβmn(i)(0)として、受信ＬＬＲ：λnを入力し、下記（４３）式に示すようにＢmn(i)Cを求める。また、初期時におけるｍ行目のＬＬＲ：βmn(0)の符号として、ｓｇｎ（λn）を入力し、下記（４３）式に示すようにＳmを求める。【０２３１】
【数３９】
0004563454.tif 000047
…（４３）【０２３２】
ただし、Ｂmn(i)Cは、ｍ行目の最小ｋ値のＬＬＲ：βmn(i)の絶対値であり、並列処理の際に共通に用いられる。また、ｎ（ｉ）は、Ｂmn(i)Cの中で最小ｉ番目のＬＬＲの列番号である。【０２３３】
（行処理ステップ）
つぎに、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４４）式により更新する。なお、Ｇは並列数であり、ＮGは並列化された各復号回路が処理する列数である。また、Ｇ・Ｎg＝Ｎである。また、本実施の形態においては、各行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０２３４】
【数４０】
0004563454.tif 000048
…（４４）【０２３５】
具体的には、たとえば、列数：ＮG毎にＧ個に分割された各列郡にそれぞれ割り当てられたＧ個の行処理部が、並列に行処理を実行する。なお、Ｇ個の行処理部が並列に処理を行い、すべての処理部が同一のＢmnCを用いる以外は、前述した「巡回近似minアルゴリズム」と同様に動作する。【０２３６】
（列処理ステップ）
つぎに、列処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（４５）式により更新する。すなわち、本実施の形態においては、上記のように並列に行処理が行われた後の各列について、並列に、下記（４５）式に示す列処理を実行する。【０２３７】
【数４１】
0004563454.tif 000049
…（４５）【０２３８】
また、各ｎについて、硬判定のための、ビットｎの繰り返しｌ回目の事後値βn(l)を下記（４６）式により更新する。【０２３９】
【数４２】
0004563454.tif 000050
…（４６）【０２４０】
なお、停止規範については、前述した「巡回近似minアルゴリズム」と同様である。【０２４１】
つづいて、上記「Overlapped巡回近似minアルゴリズム」を実現する実施の形態２のＬＤＰＣ復号器５の構成および動作について説明する。【０２４２】
図１５は、本実施の形態のＬＤＰＣ復号器５の構成例を示す図であり、受信情報から受信ＬＬＲを算出する受信ＬＬＲ算出部１１と復号処理を行う復号コア部１２ａで構成されている。また、復号コア部１２ａは、復号の途中結果（中間値）を保持しておくためのメモリで構成された途中結果保持部２１ａと、行処理（並列処理）を実行する行処理部２２−１〜２２−Ｇと、列処理（並列処理）を実行する列処理部２３−１〜２３−Ｇと、復号処理の停止規範として、列処理における事後値の硬判定およびパリティ検査結果の正誤判定を行う復号結果判定部２４と、復号の繰り返し制御を行う制御部２５ａと、を備えている。【０２４３】
図１５において、本実施の形態のＬＤＰＣ復号器５は、各行処理部および各列処理部が並列に処理を行う際、上記（４３）式，（４４）式，（４５）式に従って、途中結果保持部２１ａのＢmnCおよびＳmを共通に使用し、それぞれが更新する。この並列処理により、ＢmnCおよびＳmは、並列数に応じて急速に更新され、それに伴って、復号の繰り返し回数を大幅に削減することができる。【０２４４】
つづいて、前述した実施の形態１〜８の処理により構成された符号に対する復号処理として、たとえば、「Overlapped巡回近似minアルゴリズム」を用いた場合の効果について説明する。【０２４５】
たとえば、上記のような並列処理において、同一クロックで同一行の演算が発生し、同一バッファを参照するような問題が生じる場合、従来は、追加回路による対策が必要であった。これは「巡回近似minアルゴリズム」のみならず、如何なる復号法においても同様であった。【０２４６】
この問題の解決のために、本実施の形態においては、ｐ×ｐの巡回置換行列から成る擬似巡回行列をマスク化することにより生成されたパリティ検査行列の特徴を利用して、復号における並列処理の実施時に、行と列の重複が発生しないように並列処理の列グループを、G1=[0*p+1,1*p+1,2*p+1,…]，G2=[0*p+2,1*p+2,2*p+2,…]，G3=[0*p+3,1*p+3,2*p+3,…]，…に分割し、各グループの要素の最小値から順に全グループあるいは一部のグループを同時に実行する。【０２４７】
また、特定の列のグループの復号処理において、列に関連する行を並列に処理する。たとえば、前述した図１７に示す擬似巡回符号の場合、G1=[1,6,11,16,21]，G2=[2,7,12,17,22]，G3=[3,8,13,18,23]，G4=[4,9,14,19,24]，G5=[5,10,15,20,25]に分割する。この際、G1，G2，G3，G4，G5は並列に処理するが、同時にそれぞれ各グループの最初の要素1,2,3,4,5の列が実行され、次に6,7,8,9,10の列が実行されるため、列の重複は発生しない。また、G1の最初の要素の列番号は１であるが、これに関連する行番号は１，６，１１であり、この３つの行は並行に処理できる。同時に、G2の最初の要素の列番号は2であるが、これに関連する行番号は２，７，１２であり、この３つの行も並行に処理でき、かつG1にて処理する行番号との重複はない。同様に、全グループにおいて、行および列の重複はないため、特別の追加回路がなくても、上記グループ分けにより重複なく並列処理が実行できる。【０２４８】
なお、本実施の形態においては、「巡回近似minアルゴリズム」を並列処理する場合について記載したが、これに限らず、巡回置換行列から成る擬似巡回行列をマスク化することにより生成されたパリティ検査行列を利用して符合化が行われるシステムであれば、その他のＬＤＰＣ用復号法を並列処理する場合についても同様に適用可能である。【０２４９】
実施の形態１２．
つづいて、前述した実施の形態１〜１１の符号化処理／復号処理を適用するシステムについて説明する。たとえば、本発明にかかるＬＤＰＣ符号化処理および復号処理は、移動体通信（端末、基地局），無線ＬＡＮ，光通信，衛星通信，量子暗号装置等、通信機器全般に適用できるものであり、具体的には、図１に示すＬＤＰＣ符号化器１、ＬＤＰＣ復号器５や、図５に示す消失ＬＤＰＣ符号化部８２、消失ＬＤＰＣ復号部８６を、各通信機器に搭載し、誤り訂正を行う。【０２５０】
図１６は、本発明にかかる符号化処理／復号処理を、移動体端末１００およびその移動体端末１００と通信を行う基地局２００を備えた移動体通信システムに適用した場合の構成例を示す図であり、移動体端末１００は、消失訂正ＬＤＰＣ符号化器１０１と物理層ＬＤＰＣ符号化器１０２と変調器１０３と復調器１０４と物理層ＬＤＰＣ復号器１０５と消失訂正ＬＤＰＣ復号器１０６とアンテナ１０７とを備え、基地局２００は、消失訂正ＬＤＰＣ復号器２０１と物理層ＬＤＰＣ復号器２０２と復調器２０３と変調器２０４と物理層ＬＤＰＣ符号化器２０５と消失訂正ＬＤＰＣ符号化器２０６とアンテナ２０７とを備えている。【０２５１】
また、図１６に示す移動体端末１００および基地局２００には、物理層にフェージング通信路等に適用する物理層ＬＤＰＣ符号化器１０２および物理層ＬＤＰＣ復号器１０５が搭載されており、データリンク層等の上位層に消失訂正ＬＤＰＣ符号化器１０１および消失訂正ＬＤＰＣ復号器１０６が搭載されている。なお、移動体端末１００および基地局２００の物理層ＬＤＰＣ符号化器には、前述した実施の形態１〜７，９で説明したＬＰＤＣ符号化器のいずれかの構成を適用し、移動体端末１００および基地局２００の物理層ＬＤＰＣ復号器には、前述した実施の形態１０または１１で説明したＬＰＤＣ復号器の構成を適用する。また、移動体端末１００および基地局２００の消失訂正ＬＤＰＣ符号化器および消失訂正ＬＤＰＣ復号器には、実施の形態８の図５に記載の符号化部および復号部を適用する。【０２５２】
上記のように構成される移動体通信システムにおいて、移動体端末１００からデータを送信する場合は、まず、データとして、たとえば、音声，メール，WEB等の情報データをパケット化し、消失訂正ＬＤＰＣ符号化器１０１により符号化する。つぎに、物理層では、このパケットデータ単位に、フェージング通信路用の物理層ＬＤＰＣ符号化器１０２が符号化する。この符号化データを、変調器１０３とアンテナ１０７を介して無線通信路へ送出する。【０２５３】
一方、基地局２００では、無線通信路中で発生した誤りを含む受信信号を、アンテナ２０７と復調器２０３を介して受け取り、復調後の受信データを物理層用ＬＤＰＣ復号器２０２にて訂正する。そして、物理層では、パケット単位で誤り訂正が成功したかどうかを、上位層に通知する。上位層では、消失訂正ＬＤＰＣ復号器２０１が、誤り訂正が成功したパケットのみを用いて情報パケットを再生する。そして、この情報パケットを、ネットワークを介して通信先へ転送する。なお、ネットワークから移動体端末１００が各種データを受信する場合についても、上記と同様の処理で、基地局２００が移動体端末１００へ符号化データを送信し、移動体端末１００が各種データを再生する。基地局２００が移動体端末１００へ符号化データを送信する場合は、まず、データとして、たとえば、音声，メール，ＷＥＢ等の情報データをパケット化し、消失訂正ＬＤＰＣ符号化器２０６により符号化する。つぎに、物理層では、このパケットデータ単位に、フェージング通信路用の物理層ＬＤＰＣ符号化器２０５が符号化する。この符号化データを、変調器２０４とアンテナ２０７を介して無線通信路へ送出する。一方、移動体端末１００では、無線通信路中で発生した誤りを含む受信信号を、アンテナ１０７と復調器１０４を介して受け取り、復調後の受信データを物理層ＬＤＰＣ復号器１０５にて訂正する。そして、物理層では、パケット単位で誤り訂正が成功したかどうかを、上位層に通知する。上位層では、消失訂正ＬＤＰＣ復号器１０６が、誤り訂正が成功したパケットのみを用いて情報パケットを再生する。
【産業上の利用可能性】
【０２５４】
以上のように、本発明にかかる検査行列生成方法および符号化方法は、ディジタル通信における符号化技術として有用であり、特に、符号化方式としてＬＤＰＣ符号を採用する通信装置に適している。
【図１】
0004563454.tif 000051
【図２−１】
0004563454.tif 000052
【図２−２】
0004563454.tif 000053
【図３】
0004563454.tif 000054
【図４】
0004563454.tif 000055
【図５】
0004563454.tif 000056
【図６】
0004563454.tif 000057
【図７】
0004563454.tif 000058
【図８】
0004563454.tif 000059
【図９−１】
0004563454.tif 000060
【図９−２】
0004563454.tif 000061
【図１０】
0004563454.tif 000062
【図１１−１】
0004563454.tif 000063
【図１１−２】
0004563454.tif 000064
【図１２】
0004563454.tif 000065
【図１３】
0004563454.tif 000066
【図１４】
0004563454.tif 000067
【図１５】
0004563454.tif 000068
【図１６】
0004563454.tif 000069
【図１７】
0004563454.tif 000070
【図１８】
0004563454.tif 000071