(57)【特許請求の範囲】
【請求項１】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列Ｈを生成するための検査行列生成方法であって、
前記検査行列Ｈを、ｍ行ｋ列（ｋ＝ｎ−ｍ）の部分行列Ｈ１とｍ行ｍ列の部分行列Ｈ２とで構成し、
前記部分行列Ｈ１に含まれるいずれの２つの行を選んだ場合であっても、２つの行の周期が素となるか、または２つの行の周期が同一で位相が異なるという条件を満たすように、前記部分行列Ｈ１の各行の行列要素「１」の位置を決定する検査行列生成方法。
【請求項２】
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を定め、
前記周期リストＰの要素ｐ（ｊ）ごとに、周期がｐ（ｊ）であり位相が異なる最大ｐ（ｊ）個の部分行列Ｈ１の行を生成する請求項１記載の検査行列生成方法。
【請求項３】
先頭の要素ｐ（１）にもとづいて要素ｐ（２）から要素ｐ（ＰＬ）までを生成する請求項２記載の検査行列生成方法。
【請求項４】
周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小の値となるように生成する請求項３記載の検査行列生成方法。
【請求項５】
周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成する請求項３記載の検査行列生成方法。
【請求項６】
部分行列Ｈ２として単位行列を生成する請求項１から請求項５のうちのいずれか１項に記載の検査行列生成方法。
【請求項７】
部分行列Ｈ２として、部分行列Ｈ２に含まれるいずれの２つの行を選んだ場合であっても、２つの行の周期が素となるか、または２つの行の周期が同一で位相が異なるという条件を満たすように下三角内の行列要素「１」の位置を決定することによって、下三角行列を生成する請求項１記載の検査行列生成方法。
【請求項８】
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を定め、
前記周期リストＰの要素ｐ（ｊ）ごとに、周期がｐ（ｊ）であり位相が異なる最大ｐ（ｊ）個の部分行列Ｈ２の行を生成する請求項７記載の検査行列生成方法。
【請求項９】
先頭の要素ｐ（１）にもとづいて要素ｐ（２）から要素ｐ（ＰＬ）までを生成する請求項８記載の検査行列生成方法。
【請求項１０】
周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成する請求項９記載の検査行列生成方法。
【請求項１１】
周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成する請求項９記載の検査行列生成方法。
【請求項１２】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成するための検査行列生成方法であって、
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を前記周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、ｃ＝ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、前記いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する検査行列生成方法。
【請求項１３】
Ｆ（ｊ）＝−Ｎ（ｊ−１）とする請求項１２記載の検査行列生成方法。
【請求項１４】
Ｆ（ｊ）＝ｎ−ｍとする請求項１２記載の検査行列生成方法。
【請求項１５】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成するための検査行列生成方法であって、
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を前記周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉを用いて１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｐ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、前記条件を満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する検査行列生成方法。
【請求項１６】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成するための検査行列生成方法であって、
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）と、周期リストＱ＝｛ｑ（１），ｑ（２），・・・，ｑ（ＱＬ）｝（ｑ（１）〜ｑ（ＱＬ）は互いに素）とを用いて、Ｎ（ｊ）を前記周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し、Ｎ（０）を０であると定義し、Ｍ（ｊ）を前記周期リストＱの要素ｑ（１）から要素ｑ（ｊ）までの値の合計であると定義し、且つＭ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、Ｍ（ｊ−１）＋１≦ｒ≦Ｍ（ｊ）であれば、整数ｉを用いてｎ−ｍ＋１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｑ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、前記いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する検査行列生成方法。
【請求項１７】
Ｆ（ｊ）＝−Ｎ（ｊ−１）とする請求項１６記載の検査行列生成方法。
【請求項１８】
Ｆ（ｊ）＝ｎ−ｍとする請求項１６記載の検査行列生成方法。
【請求項１９】
先頭の要素ｐ（１）にもとづいて要素ｐ（２）から要素ｐ（ＰＬ）までを生成することによって、周期リストＰを定める請求項１２、請求項１５または請求項１６記載の検査行列生成方法。
【請求項２０】
周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成する請求項１９記載の検査行列生成方法。
【請求項２１】
周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成する請求項１９記載の検査行列生成方法。
【請求項２２】
データを符号化する符号化装置と、符号化されたデータを復号する復号装置とを含むデータ伝送システムであって、
前記符号化装置は、
所定のパラメータにもとづいて、請求項１、請求項１２、請求項１５または請求項１６のうちのいずれか１項に記載の検査行列生成方法を用いて検査行列を生成し、
生成した検査行列を用いてデータを低密度パリティ符号化して符号語に変換し、
変換した符号語を、伝送路を介して前記復号装置に送信し、
前記復号装置は、
前記符号化装置が用いるパラメータと同一のパラメータにもとづいて、前記検査行列生成方法を用いて検査行列を生成し、
前記符号化装置から受信した符号語を、生成した検査行列を用いて復号し符号化前のデータに変換するデータ伝送システム。
【請求項２３】
符号化装置は、パラメータとしての所定の周期リストＰにもとづいて検査行列を生成し、
復号装置は、前記符号化装置が用いる周期リストＰと同一の周期リストＰにもとづいて検査行列を生成する請求項２２記載のデータ伝送システム。
【請求項２４】
符号化装置は、
パラメータとしての周期リストＰの先頭の要素ｐ（１）にもとづいて、要素ｐ（２）から要素ｐ（ＰＬ）までを生成することによって、周期リストＰを定め、
定めた周期リストにもとづいて検査行列を生成し、
復号装置は、
前記符号化装置が用いる要素ｐ（１）と同一の要素ｐ（１）にもとづいて、要素ｐ（２）から要素ｐ（ＰＬ）までを生成することによって、周期リストＰを定め、
定めた周期リストにもとづいて検査行列を生成する請求項２２記載のデータ伝送システム。
【請求項２５】
符号化装置は、周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成し、
復号装置は、周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成する請求項２４記載のデータ伝送システム。
【請求項２６】
符号化装置は、周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成し、
復号装置は、周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成する請求項２４記載のデータ伝送システム。
【請求項２７】
符号化装置は、伝送路を介してパラメータを復号装置に送信し、
前記復号装置は、前記符号化装置から受信したパラメータを用いることによって、前記符号化装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成する請求項２２記載のデータ伝送システム。
【請求項２８】
復号装置は、伝送路を介してパラメータを符号化装置に送信し、
前記符号化装置は、前記復号装置から受信したパラメータを用いることによって、前記復号装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成する請求項２２記載のデータ伝送システム。
【請求項２９】
符号化装置は、所定時間ごとにパラメータを伝送路を介して復号装置に送信し、
前記復号装置は、前記符号化装置から受信したパラメータを用いることによって、前記符号化装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成する請求項２２記載のデータ伝送システム。
【請求項３０】
復号装置は、所定時間ごとにパラメータを伝送路を介して符号化装置に送信し、
前記符号化装置は、前記復号装置から受信したパラメータを用いることによって、前記復号装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成する請求項２２記載のデータ伝送システム。
【請求項３１】
符号化装置は、パラメータの内容が更新された場合に、前記パラメータを伝送路を介して復号装置に送信し、
前記復号装置は、前記符号化装置から受信したパラメータを用いることによって、前記符号化装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成する請求項２２から請求項記載のデータ伝送システム。
【請求項３２】
復号装置は、パラメータの内容が更新された場合に、前記パラメータを伝送路を介して符号化装置に送信し、
前記符号化装置は、前記復号装置から受信したパラメータを用いることによって、前記復号装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成する請求項２２記載のデータ伝送システム。
【請求項３３】
所定のパラメータにもとづいて、請求項１、請求項１２、請求項１５または請求項１６のうちのいずれか１項に記載の検査行列生成方法を用いて検査行列を生成し、
生成した検査行列を用いてデータを低密度パリティ符号化して符号語に変換し、
変換した符号語を、伝送路を介して復号装置に送信する符号化装置。
【請求項３４】
符号化装置から、伝送路を介して符号語を受信し、
所定のパラメータにもとづいて、請求項１、請求項１２、請求項１５または請求項１６のうちのいずれか１項に記載の検査行列生成方法を用いて検査行列を生成し、
前記受信した符号語を、生成した検査行列を用いて復号し符号化前のデータに変換する復号装置。
【請求項３５】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列Ｈを生成させるための検査行列生成プログラムであって、
コンピュータに、
前記検査行列Ｈを、ｍ行ｋ列の部分行列Ｈ１とｍ行ｍ列の部分行列Ｈ２とで構成する処理と（ｍ＝ｎ−ｋ）、
前記部分行列Ｈ１に含まれるいずれの２つの行を選んだ場合であっても、２つの行の周期が素となるか、または２つの行の周期が同一で位相が異なるという条件を満たすように、前記部分行列Ｈ１の各行の行列要素「１」の位置を決定する処理とを実行させる検査行列生成プログラム。
【請求項３６】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成させるための検査行列生成プログラムであって、
コンピュータに、
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を前記周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、ｃ＝ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、前記いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する処理を実行させる検査行列生成プログラム。
【請求項３７】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成させるための検査行列生成プログラムであって、
コンピュータに、
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を前記周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉを用いて１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｐ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、前記条件を満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する処理を実行させる検査行列生成プログラム。
【請求項３８】
低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成させるための検査行列生成プログラムであって、
コンピュータに、
周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）と、周期リストＱ＝｛ｑ（１），ｑ（２），・・・，ｑ（ＱＬ）｝（ｑ（１）〜ｑ（ＱＬ）は互いに素）とを用いて、Ｎ（ｊ）を前記周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し、Ｎ（０）を０であると定義し、Ｍ（ｊ）を前記周期リストＱの要素ｑ（１）から要素ｑ（ｊ）までの値の合計であると定義し且つＭ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、Ｍ（ｊ−１）＋１≦ｒ≦Ｍ（ｊ）であれば、整数ｉを用いてｎ−ｍ＋１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｑ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、前記いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する処理を実行させる検査行列生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り訂正符号としてＬＤＰＣ（低密度パリティ検査）符号を用いる符号化器（符号化装置）および復号器（復号装置）が検査行列を生成するための検査行列生成方法および検査行列生成プログラムに関し、検査行列生成方法や検査行列生成プログラムを適用したデータ伝送システム、符号化装置および復号装置に関する。
【背景技術】
【０００２】
伝送エラーが生じうる伝送路を介してデータの伝送を行う場合、一般に誤り訂正符号を用いる。図１は、伝送路を介してデータを伝送するデータ伝送システムの構成の一例を示すブロック図である。例えば、図１に示すデータ伝送システムでは、伝送路１２を介して送信側の伝送路符号化器１１および受信側の伝送路復号器１３を備えている。そして、伝送路符号化器１１および伝送路復号器１３を用いてエラー訂正を行うことによって、データ発生器１０からデータ消費器１４に送られるデータに伝送エラーが影響しないようにしている。【０００３】
誤り訂正符号として、Reed Solomon（リードソロモン）符号や Turbo（ターボ）符号などが知られている。また、近年、理論限界（シャノン限界）に近い性能を出せるＬＤＰＣ符号が誤り訂正符号として注目されている。【０００４】
ＬＤＰＣ符号化されるメッセージ（データ）のメッセージ長をｋとし符号化後の符号語長をｎとすると、ＬＤＰＣ符号の検査行列Ｈは、（ｎ−ｋ）行ｎ列の行列として表される。メッセージをＳ＝（ｓ１，ｓ２，・・・，ｓｋ）とし符号語をＣ＝（ｃ１，ｃ２，・・・，ｃｎ）とすると、符号語Ｃは、ｋ行ｎ列の生成行列ＧをメッセージＳに乗ずることによって得られる。すなわち、符号語Ｃは、Ｃ＝ＳＧを求めることによって得られる。全ての符号語ＣはＨＣｔ＝０の条件を満たすので、ＧＨｔ＝０である。なお、Ｃｔは符号語Ｃの転置ベクトルを示し、Ｈｔは検査行列Ｈの転置行列を示す。【０００５】
ＬＤＰＣ符号の応用例として、例えば、非特許文献１には、パケット列に対してＬＤＰＣ符号化を行い、パケット交換網で発生するパケットロス対策にＬＤＰＣ符号を応用する例が記載されている。【０００６】
ＬＤＰＣ符号のエラー訂正特性は検査行列によって決まる。非特許文献２では、ＬＤＰＣ符号のエラー訂正特性の理論解析を開示している。非特許文献２によれば、ＬＤＰＣ符号のエラー訂正特性を決定しているのは、主として検査行列の重み分布である。検査行列は、ほとんど要素「０」によって構成されており、まばらに要素「１」を含む。なお、重みとは、検査行列において各行や各列に含まれる要素「１」の数を示す。【０００７】
ＬＤＰＣ符号の発明者であるRobert  G.  Gallagerが提案した検査行列は、行や列の重みが均一な行列である。Robert  G.  Gallagerが提案した検査行列によるＬＤＰＣ符号は、Regular  （レギュラ）ＬＤＰＣ符号と呼ばれている。図２は、レギュラＬＤＰＣ符号の検査行列の一例を示す説明図である。図２に示す検査行列では、各行の重みはそれぞれ要素「１」の数がＷＲ個で一定（均一）であり、各列の重みはそれぞれ要素「１」の数がＷＣ個で一定（均一）である。【０００８】
これに対し、非特許文献２では、重みが不均一で特定の分布をもつ検査行列によるＬＤＰＣ符号のほうが、レギュラＬＤＰＣ符号に比べて、エラー訂正特性がよいことを明らかにしている。なお、重みが不均一で特定の分布をもつ検査行列によるＬＤＰＣ符号は、 Irregular（イレギュラ）ＬＤＰＣ符号と呼ばれている。【０００９】
最適な重み分布をもつ検査行列を生成する方法として、特許文献１には、符号化率にもとづいて検査行列を生成するＬＤＰＣ符号用検査行列生成方法が記載されている。特許文献１に記載されたＬＤＰＣ符号用検査行列生成方法では、重み分布の決定に線形計画法を利用する。そして、行や列あたりの要素「１」の数を決定した後に、疑似乱数を用いて要素「１」の位置を入れ替えることによって検査行列を生成する。【００１０】
また、検査行列のエラー訂正特性は、行や列の重み分布だけで決まるわけではない。検査行列の行や列の重み分布が最適であったとしても、検査行列を二部グラフ（タナーグラフ）を用いて表した場合に二部グラフ上に長さ４などの短いループが存在すれば、エラー訂正特性が大幅に劣化することが知られている。【００１１】
図３Ａ及び３Ｂは、検査行列に対応する二部グラフの例を示す説明図である。図３Ａは、検査行列の一例を示す。また、図３Ｂは、図３Ａに示す検査行列を表した二部グラフである。図３Ｂにおいて、変数ノードは符号語の各ビットに対応し、チェックノードは検査行列の各行に対応する。また、ノード間を結ぶエッジは、検査行列中の要素「１」を表している。図３Ａ及び３Ｂに示すように、二部グラフ上において、長さ４のループは、検査行列中のいずれか２つの行の間で共通に要素「１」をもつ列（共有列）が２以上存在する場合に発生する。【００１２】
ＬＤＰＣ符号の復号は、一般にsum-product 復号法を用いてエラーが重畳された符号語から元のメッセージを推定することによって行われる。検査行列にループが存在しなければ、sum-product 復号法は、最大事後確率（ＭＡＰ）推定となる。検査行列にループが存在すると、sum-product 復号法は、最大事後確率推定より劣化し最大事後確率推定の近似にすぎなくなる。そのため、検査行列にループが発生するのを防止する検査行列生成方法がいくつか提案されている。【００１３】
また、検査行列は、エラー訂正特性を決定するだけでなく、符号化における演算コスト（演算回数）や生成行列算出のための演算コストも決定する。一般に符号化を行うにはＯ（ｎ２）回の演算が必要であり、生成行列を算出するためにはＯ（ｎ３）回の演算が必要である。【００１４】
生成行列算出の演算コストや符号化の際の演算コストを削減するために、検査行列の一部を単位行列や三角行列にして、生成行列算出や符号化の際の演算回数をＯ（ｎ）回に抑える方法が提案されている。【００１５】
例えば、特許文献２には、サイクリックシフトを表す正方行列の累乗を部分行列として用い、これらの部分行列を組み合わせて検査行列を構成することによって、短いループの発生を防止する低密度パリティ検査符号化方法が記載されている。特許文献２に記載された低密度パリティ検査符号化方法では、ループの発生を防止すると同時に検査行列の三角化を行っている。そして、生成行列と検査行列とを等価にすることによって、符号化の際の演算回数をＯ（ｎ）回に抑えている。また、特許文献２に記載された低密度パリティ検査符号化方法では、検査行列を規則的なシフトを用いるだけで生成できるので、検査行列の生成コストも小さい。【００１６】
【非特許文献１】Michael  G.  Luby,  Michael  Mitzenmacher,  M.  Amin  Shokrollahi,  Daniel  A.  Spielman,  Efficient  Erasure  Correcting  Codes,  "IEEE  Transactions  on  Information  Theory",  February  2001,  Vol.  47,  No.2,  p.569-584.
【非特許文献２】Thomas  J.  Richardson,  M.  Amin  Shokrollahi,  Design  of  Capacity-Approaching  Irregular  Low-Density  Parity-Check  Codes,  "IEEE  Transactions  on  Information  Theory",  February  2001,  Vol.  47,  No.2,  p.619-637.
【特許文献１】特開２００３−１９８３８３号公報（第４−１０頁、第１−１８図）
【特許文献２】特開２００２−１１５７６８号公報（第６−１０頁、第１−９図）
【発明の開示】
【００１７】
特許文献１に記載されたＬＤＰＣ符号用検査行列生成方法によれば、検査行列の生成コストを削減することができる。しかし、検査行列から生成行列を算出する演算コストや、算出した生成行列を用いて符号化を行う際の演算コストの削減はできない。また、検査行列を生成するために線形計画法や疑似乱数を用いた複雑な演算を行わなければならない。
【００１８】
また、特許文献２に記載された低密度パリティ検査符号化方法では、三角化を行う前の行列の行重みと列重みが一定であり、生成する検査行列がレギュラＬＤＰＣ符号の検査行列に近くなる。従って、必ずしもエラー訂正特性がよくなるように検査行列を生成することはできない。
【００１９】
そこで、本発明は、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成できる検査行列生成方法、データ伝送システム、符号化装置、復号装置および検査行列生成プログラムを提供することを目的とする。
また、本発明は、生成行列の生成の際や符号化の際の演算コストを抑えることができる検査行列生成方法、データ伝送システム、符号化装置、復号装置および検査行列生成プログラムを提供することを目的とする。
【００２０】
本発明による検査行列生成方法は、低密度パリティ検査符号におけるｍ行ｎ列の検査行列Ｈを生成するための検査行列生成方法であって、検査行列Ｈを、ｍ行ｋ列（ｋ＝ｎ−ｍ）の部分行列Ｈ１とｍ行ｍ列の部分行列Ｈ２とで構成し、部分行列Ｈ１に含まれるいずれの２つの行を選んだ場合であっても、２つの行の周期が素となるか、または２つの行の周期が同一で位相が異なるという条件を満たすように、部分行列Ｈ１の各行の行列要素「１」の位置を決定することを特徴とする。
【００２１】
また、検査行列生成方法は、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を定め、周期リストＰの要素ｐ（ｊ）ごとに、周期がｐ（ｊ）であり位相が異なる最大ｐ（ｊ）個の部分行列Ｈ１の行を生成するように構成されていてもよい。そのような構成によれば、周期リストＰさえ入力すれば、容易に部分行列Ｈ１を生成することができる。
【００２２】
また、検査行列生成方法は、先頭の要素ｐ（１）にもとづいて要素ｐ（２）から要素ｐ（ＰＬ）までを生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に部分行列Ｈ１を生成することができる。
【００２３】
また、検査行列生成方法は、周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小の値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００２４】
また、検査行列生成方法は、周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００２５】
また、検査行列生成方法は、部分行列Ｈ２として単位行列を生成するように構成されていてもよい。そのような構成によれば、検査行列が単位行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。
【００２６】
また、検査行列生成方法は、部分行列Ｈ２として、部分行列Ｈ２に含まれるいずれの２つの行を選んだ場合であっても、２つの行の周期が素となるか、または２つの行の周期が同一で位相が異なるという条件を満たすように下三角内の行列要素「１」の位置を決定することによって、下三角行列を生成するように構成されていてもよい。そのような構成によれば、検査行列が下三角行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。
【００２７】
また、検査行列生成方法は、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を定め、周期リストＰの要素ｐ（ｊ）ごとに、周期がｐ（ｊ）であり位相が異なる最大ｐ（ｊ）個の部分行列Ｈ２の行を生成するように構成されていてもよい。そのような構成によれば、周期リストＰさえ入力すれば、容易に部分行列Ｈ２を生成することができる。
【００２８】
また、検査行列生成方法は、先頭の要素ｐ（１）にもとづいて要素ｐ（２）から要素ｐ（ＰＬ）までを生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に部分行列Ｈ２を生成することができる。
【００２９】
また、検査行列生成方法は、周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に部分行列Ｈ２を生成することができる。
【００３０】
また、検査行列生成方法は、周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に部分行列Ｈ２を生成することができる。
【００３１】
また、検査行列生成方法は、低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成するための検査行列生成方法であって、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、ｃ＝ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成するように構成されていてもよい。そのような構成によれば、部分行列ごとに生成することなく、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように、ｍ行ｎ列の検査行列を一括して生成することができる。また、部分行列ごとに生成することなく、単位行列を含むように検査行列を一括して生成することができる。
従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成することができる。また、検査行列Ｈが単位行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。
【００３２】
また、検査行列生成方法は、Ｆ（ｊ）＝−Ｎ（ｊ−１）とするように構成されていてもよい。
【００３３】
また、検査行列生成方法は、Ｆ（ｊ）＝ｎ−ｍとするように構成されていてもよい。
【００３４】
また、検査行列生成方法は、低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成するための検査行列生成方法であって、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉを用いて１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｐ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、条件を満たさない行列要素を「０」とすることによって検査行列の行ｒを生成するように構成されていてもよい。そのような構成によれば、部分行列ごとに生成することなく、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように、ｍ行ｎ列の検査行列を一括して生成することができる。また、部分行列ごとに生成することなく、下三角行列を含むように検査行列を一括して生成することができる。従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成することができる。また、検査行列が下三角行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。
【００３５】
また、検査行列生成方法は、低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成するための検査行列生成方法であって、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）と、周期リストＱ＝｛ｑ（１），ｑ（２），・・・，ｑ（ＱＬ）｝（ｑ（１）〜ｑ（ＱＬ）は互いに素）とを用いて、Ｎ（ｊ）を周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し、Ｎ（０）を０であると定義し、Ｍ（ｊ）を周期リストＱの要素ｑ（１）から要素ｑ（ｊ）までの値の合計であると定義し、且つＭ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、Ｍ（ｊ−１）＋１≦ｒ≦Ｍ（ｊ）であれば、整数ｉを用いてｎ−ｍ＋１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｑ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成するように構成されていてもよい。そのような構成によれば、２種類の周期リストにもとづいて、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように、ｍ行ｎ列の検査行列を一括して生成することができる。また、下三角行列を含むように検査行列を一括して生成することができる。
【００３６】
また、検査行列生成方法は、Ｆ（ｊ）＝−Ｎ（ｊ−１）とするように構成されていてもよい。
【００３７】
また、検査行列生成方法は、Ｆ（ｊ）＝ｎ−ｍとするように構成されていてもよい。
【００３８】
また、検査行列生成方法は、先頭の要素ｐ（１）にもとづいて要素ｐ（２）から要素ｐ（ＰＬ）までを生成することによって、周期リストＰを定めるように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００３９】
また、検査行列生成方法は、周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００４０】
また、検査行列生成方法は、周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ入力すれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００４１】
本発明によるデータ伝送システムは、データを符号化する符号化装置と、符号化されたデータを復号する復号装置とを含むデータ伝送システムであって、符号化装置は、所定のパラメータにもとづいて、検査行列生成方法を用いて検査行列を生成し、生成した検査行列を用いてデータを低密度パリティ符号化して符号語に変換し、変換した符号語を、伝送路を介して復号装置に送信し、復号装置は、符号化装置が用いるパラメータと同一のパラメータにもとづいて、検査行列生成方法を用いて検査行列を生成し、符号化装置から受信した符号語を、生成した検査行列を用いて復号し符号化前のデータに変換することを特徴とする。
【００４２】
また、符号化装置は、パラメータとしての所定の周期リストＰにもとづいて検査行列を生成し、復号装置は、符号化装置が用いる周期リストＰと同一の周期リストＰにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、周期リストＰさえ定めれば、容易に検査行列を生成することができる。
【００４３】
また、符号化装置は、パラメータとしての周期リストＰの先頭の要素ｐ（１）にもとづいて、要素ｐ（２）から要素ｐ（ＰＬ）までを生成することによって、周期リストＰを定め、定めた周期リストにもとづいて検査行列を生成し、復号装置は、符号化装置が用いる要素ｐ（１）と同一の要素ｐ（１）にもとづいて、要素ｐ（２）から要素ｐ（ＰＬ）までを生成することによって、周期リストＰを定め、定めた周期リストにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ定めれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００４４】
また、符号化装置は、周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成し、復号装置は、周期リストＰの要素ｐ（ｊ）を、先行する要素ｐ（１）から要素ｐ（ｊ−１）までの全ての要素と互いに素であるという条件を満たす値のうちの最小値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ定めれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００４５】
また、符号化装置は、周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成し、復号装置は、周期リストＰの要素ｐ（ｊ）を、１つ前の要素ｐ（ｊ−１）より大きい素数であるという条件を満たす値のうちの最小の値となるように生成するように構成されていてもよい。そのような構成によれば、周期リストＰの先頭要素さえ定めれば、周期リストＰが自動的に決定され、容易に検査行列を生成することができる。
【００４６】
また、符号化装置は、伝送路を介してパラメータを復号装置に送信し、復号装置は、符号化装置から受信したパラメータを用いることによって、符号化装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、符号化装置が用いる周期リストと、復号装置が用いる周期リストとの同一性を容易に保つことができる。
【００４７】
また、復号装置は、伝送路を介してパラメータを符号化装置に送信し、符号化装置は、復号装置から受信したパラメータを用いることによって、復号装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、符号化装置が用いる周期リストと、復号装置が用いる周期リストとの同一性を容易に保つことができる。
【００４８】
また、符号化装置は、所定時間ごとにパラメータを伝送路を介して復号装置に送信し、復号装置は、符号化装置から受信したパラメータを用いることによって、符号化装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、符号化装置が用いる周期リストと、復号装置が用いる周期リストとの同一性を容易に保つことができる。
【００４９】
また、復号装置は、所定時間ごとにパラメータを伝送路を介して符号化装置に送信し、符号化装置は、復号装置から受信したパラメータを用いることによって、復号装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、符号化装置が用いる周期リストと、復号装置が用いる周期リストとの同一性を容易に保つことができる。
【００５０】
また、符号化装置は、パラメータの内容が更新された場合に、パラメータを伝送路を介して復号装置に送信し、復号装置は、符号化装置から受信したパラメータを用いることによって、符号化装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、符号化装置が用いる周期リストと、復号装置が用いる周期リストとの同一性をリアルタイムに維持することができる。
【００５１】
また、復号装置は、パラメータの内容が更新された場合に、パラメータを伝送路を介して符号化装置に送信し、符号化装置は、復号装置から受信したパラメータを用いることによって、復号装置が用いるパラメータと同一のパラメータにもとづいて検査行列を生成するように構成されていてもよい。そのような構成によれば、符号化装置が用いる周期リストと、復号装置が用いる周期リストとの同一性をリアルタイムに維持することができる。
【００５２】
本発明による符号化装置は、所定のパラメータにもとづいて、検査行列生成方法を用いて検査行列を生成し、生成した検査行列を用いてデータを低密度パリティ符号化して符号語に変換し、変換した符号語を、伝送路を介して復号装置に送信することを特徴とする。
【００５３】
本発明による復号装置は、符号化装置から、伝送路を介して符号語を受信し、所定のパラメータにもとづいて、検査行列生成方法を用いて検査行列を生成し、受信した符号語を、生成した検査行列を用いて復号し符号化前のデータに変換することを特徴とする。
【００５４】
本発明による検査行列生成プログラムは、低密度パリティ検査符号におけるｍ行ｎ列の検査行列Ｈを生成させるための検査行列生成プログラムであって、コンピュータに、検査行列Ｈを、ｍ行ｋ列の部分行列Ｈ１とｍ行ｍ列の部分行列Ｈ２とで構成する処理と（ｍ＝ｎ−ｋ）、部分行列Ｈ１に含まれるいずれの２つの行を選んだ場合であっても、２つの行の周期が素となるか、または２つの行の周期が同一で位相が異なるという条件を満たすように、部分行列Ｈ１の各行の行列要素「１」の位置を決定する処理とを実行させることを特徴とする。
【００５５】
また、検査行列生成プログラムは、低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成させるための検査行列生成プログラムであって、コンピュータに、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、ｃ＝ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する処理を実行させるように構成されていてもよい。そのような構成によれば、部分行列ごとに生成することなく、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように、ｍ行ｎ列の検査行列を一括して生成することができる。また、部分行列ごとに生成することなく、単位行列を含むように検査行列を一括して生成することができる。従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成することができる。また、検査行列Ｈが単位行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。
【００５６】
また、検査行列生成プログラムは、低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成させるための検査行列生成プログラムであって、コンピュータに、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）を用いて、Ｎ（ｊ）を周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し且つＮ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉを用いて１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｐ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、条件を満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する処理を実行させるように構成されていてもよい。
そのような構成によれば、部分行列ごとに生成することなく、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように、ｍ行ｎ列の検査行列を一括して生成することができる。また、部分行列ごとに生成することなく、下三角行列を含むように検査行列を一括して生成することができる。従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成することができる。
また、検査行列が下三角行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。
【００５７】
また、検査行列生成プログラムは、低密度パリティ検査符号におけるｍ行ｎ列の検査行列を生成させるための検査行列生成プログラムであって、コンピュータに、周期リストＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝（ｐ（１）〜ｐ（ＰＬ）は互いに素）と、周期リストＱ＝｛ｑ（１），ｑ（２），・・・，ｑ（ＱＬ）｝（ｑ（１）〜ｑ（ＱＬ）は互いに素）とを用いて、Ｎ（ｊ）を周期リストＰの要素ｐ（１）から要素ｐ（ｊ）までの値の合計であると定義し、Ｎ（０）を０であると定義し、Ｍ（ｊ）を周期リストＱの要素ｑ（１）から要素ｑ（ｊ）までの値の合計であると定義し且つＭ（０）を０であると定義した場合に、Ｎ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）であれば、整数ｉおよび所定の値Ｆ（ｊ）を用いて１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）の条件を満たす列ｃに対応する行列要素を「１」とし、Ｍ（ｊ−１）＋１≦ｒ≦Ｍ（ｊ）であれば、整数ｉを用いてｎ−ｍ＋１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｑ（ｊ）・ｉ＋ｎ−ｍ＋ｒの条件を満たす列ｃに対応する行列要素を「１」とし、いずれの条件をも満たさない行列要素を「０」とすることによって検査行列の行ｒを生成する処理を実行させるように構成されていてもよい。そのような構成によれば、２種類の周期リストにもとづいて、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように、ｍ行ｎ列の検査行列を一括して生成することができる。また、下三角行列を含むように検査行列を一括して生成することができる。
【００５８】
本発明によれば、検査行列Ｈの部分行列Ｈ１を、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように生成する。２つの行が互いに素となる周期をもつようにした場合には、２つの行に共有列が存在しないようにできる。また、周期が同一である場合に互いに異なる位相をもつようにした場合には、２つの行に共有列が最大でも１つしか存在しないようにできる。よって、二部グラフ上での短いループによるエラー訂正の性能劣化を防止できる。また、互いに素である複数の周期を用いて行を生成するので、行重みの均一化によるエラー訂正の性能劣化を防止することができる。さらに、周期と位相が定まれば、簡易に部分行列Ｈ１を生成することができる。従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成することができる。
【図面の簡単な説明】
【００５９】
【図１】データ伝送システムの構成の一例を示すブロック図である。
【図２】レギュラＬＤＰＣ符号の検査行列の一例を示す説明図である。
【図３Ａ】検査行列の一例を示す図である。
【図３Ｂ】検査行列に対応する二部グラフの例を示す説明図である。
【図４】本発明による検査行列作成方法を適用した伝送路符号化器の構成の一例を示すブロック図である。
【図５】処理部５０が部分行列Ｈ１を生成する処理経過の一例を示す流れ図である。
【図６】処理部５０が生成する検査行列Ｈの一例を示す説明図である。
【図７】処理部５０が部分行列Ｈ２を生成する処理経過の一例を示す流れ図である。
【図８】処理部５０が生成する検査行列Ｈの他の例を示す説明図である。
【図９】処理部５０が検査行列Ｈを生成する処理経過の一例を示す流れ図である。
【図１０】処理部５０が生成する検査行列Ｈのさらに他の例を示す説明図である。
【符号の説明】
【００６０】
５０    処理部
５１    メモリ
５２    入出力部
【発明を実施するための最良の形態】
【００６１】
実施の形態１．
以下、本発明の第１の実施の形態を図面を参照して説明する。図４は、本発明による検査行列生成方法を適用した伝送路符号化器の構成の一例を示すブロック図である。図４に示すように、伝送路符号化器は、処理部５０、メモリ５１および入出力部５２を含む。【００６２】
図４において、処理部５０は、ＬＤＰＣ符号の検査行列を生成し、生成した検査行列をメモリ５１に書き込む。また、処理部５０は、メモリ５１からデータ列（メッセージ）を読み出し、読み出したデータ列をＬＤＰＣ符号化して符号語を生成する。そして、処理部５０は、生成した符号語を入出力部５２に出力する。【００６３】
メモリ５１は、検査行列およびデータ列などを記憶する。入出力部５２は、処理部５０からの符号語を外部に出力する。例えば、入出力部５２は、伝送路を介して符号語を伝送路復号器に送信する。入出力部５２は、データ列が外部から入力された場合には、入力されたデータ列をメモリ５１に書き込む。【００６４】
また、伝送路符号化器は、処理部５０に検査行列の生成処理やデータ列の符号化処理を実行させるための各種プログラムを記憶する記憶部（図示せず）を備える。例えば、伝送路符号化器の記憶部は、コンピュータに、検査行列Ｈを、ｍ行ｋ列の部分行列Ｈ１とｍ行ｍ列の部分行列Ｈ２とで構成する処理と（ｍ＝ｎ−ｋ）、部分行列Ｈ１に含まれるいずれの２つの行を選んだ場合であっても、２つの行の周期が素となるか、または２つの行の周期が同一で位相が異なるという条件を満たすように、部分行列Ｈ１の各行の行列要素「１」の位置を決定する処理とを実行させるための検査行列生成プログラムを記憶する。【００６５】
本実施の形態では、メッセージ長がｋであり符号語長がｎである場合に、処理部５０がＬＤＰＣ符号の符号化に用いるｍ行ｎ列の検査行列Ｈを生成する場合を説明する。ここで、ｍ＝ｎ−ｋである。本実施の形態において、処理部５０は、検査行列Ｈを、左側のｍ行ｋ列の部分行列Ｈ１と右側のｍ行ｍ列の部分行列Ｈ２とから構成する。【００６６】
本実施の形態では、処理部５０は、部分行列Ｈ２を単位行列として生成する。また、処理部５０は、部分行列Ｈ１を所定の条件に従って行列要素「１」または「０」をもつ行列として生成する。そして、処理部５０は、部分行列Ｈ１と部分行列Ｈ２とを結合することによって検査行列Ｈを生成する。以下、部分行列Ｈ１の生成処理を説明する。【００６７】
処理部５０は、各行において、所定の周期と所定の位相とによって定まる位置の行列要素が「１」となるようにし、他の行列要素が「０」となるように部分行列Ｈ１を生成する。ここで、周期とは、行の中に含まれる要素「１」と要素「１」との距離を示す。本実施の形態では、行の中に要素「１」が周期ごとに配置される。また、位相とは、行の中にある要素「１」のうち最も左側にある要素の列の位置である。位相は、１から周期までの値をとる。周期と位相とが定まれば、行の中の要素「１」の位置および要素「１」の個数が決定される。【００６８】
本実施の形態では、処理部５０は、部分行列Ｈ１に含まれる任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように部分行列Ｈ１を生成する。処理部５０は、部分行列Ｈ１の各行を順に生成する際に、次の行の生成に用いる周期および位相を、それまでに生成した全ての行の周期および位相に対して、２つの条件のうちのいずれかを満たすように選択する。【００６９】
図５は、処理部５０が部分行列Ｈ１を生成する処理経過の一例を示す流れ図である。処理部５０は、周期リストＰ＝｛ｐ１，ｐ２，・・・，ｐｊ｝を設定する（ステップＳ１１０）。例えば、ユーザによって周期リストＰの各要素が入力されると、処理部５０は、入力された各要素を含む周期リストＰを設定する。また、例えば、上位のアプリケーションに従って各要素が入力されると、処理部５０は、入力された各要素を含む周期リストＰを設定する。ステップＳ１１０において、周期リストＰの各要素は互いに素となるように設定され、周期リストＰの要素の値の合計がｍ以上となるように設定される。【００７０】
処理部５０は、部分行列Ｈ１の各行の生成に用いる各変数を初期化する（ステップＳ１２０）。本実施の形態では、周期を示す周期変数ａ、変数ｂ、および部分行列Ｈ１の各行のうちの生成対象の行を示す生成対象行番号ｒが変数として用いられる。なお、本実施の形態では、変数ｂの値が各行の要素「１」のうち最も左側にある要素の位置と一致する。
従って、本実施の形態では、変数ｂが位相を示す位相変数としての役割を果たす。【００７１】
ステップＳ１２０において、処理部５０は、周期リストＰの先頭要素ｐ１を周期変数ａの初期値として設定し、変数ｂの初期値を１に設定する。また、処理部５０は、生成対象行番号ｒの初期値を１に設定する。【００７２】
処理部５０は、生成対象行番号ｒに対応する行を生成する（ステップＳ１２１）。ステップＳ１２１において、処理部５０は、生成式ｃ＝ａ・ｉ＋ｂを用いて部分行列Ｈ１の行ｒを生成する。処理部５０は、生成式ｃ＝ａ・ｉ＋ｂで表される列ｃに位置する行列要素を「１」とし、それ以外の行列要素を「０」として行ｒを生成する。ここで、ｉは、整数である。【００７３】
処理部５０は、生成した行ｒが部分行列Ｈ１の最終行であるか否かを判断する（ステップＳ１２２）。最終行であると判断した場合には、処理部５０は、部分行列Ｈ１の生成の処理を終了する。最終行でないと判断した場合には、処理部５０は、変数ｂおよび生成対象行番号ｒを更新する（ステップＳ１２３）。ステップＳ１２３において、処理部５０は、生成対象行番号ｒに１を加算する。また、処理部５０は、変数ｂに１を加算する。【００７４】
変数ｂを更新すると、処理部５０は、変数ｂが周期変数ａの値以下であるか否かを判断する（ステップＳ１２４）。ｂ≦ａであると判断した場合には、処理部５０は、ステップＳ１２１の処理に戻り、ステップＳ１２１以降の処理を繰り返し実行する。【００７５】
ｂ≦ａでないと判断した場合には、処理部５０は、周期変数ａを更新する（ステップＳ１２５）。ステップＳ１２５において、処理部５０は、周期リストＰから次の要素の値を読み込んで周期変数ａの値に設定する。また、処理部５０は、変数ｂの値を１に設定する。そして、処理部５０は、ステップＳ１２１の処理に戻り、ステップＳ１２１以降の処理を繰り返し実行する。【００７６】
図６は、処理部５０が生成する検査行列Ｈの一例を示す説明図である。図６に示す検査行列Ｈは、メッセージ長がｋ＝１２であり符号語長がｎ＝２０であるとして生成された行列である。従って、図６に示すように、検査行列Ｈの行数は、ｍ＝ｎ−ｋ＝８である。また、図６に示すように、処理部５０は、検査行列Ｈのうちの部分行列Ｈ２を単位行列として生成している。また、検査行列Ｈのうちの部分行列Ｈ１は、ステップＳ１１０において周期リストＰ＝｛３，４，５｝と設定されて、図２に示す処理に従って生成されたものである。【００７７】
例えば、ステップＳ１２０において、処理部５０は、周期リストＰの先頭要素３を周期変数ａの初期値として設定し、変数ｂおよび生成処理対象番号ｒの初期値をそれぞれ１に設定する。ステップＳ１２１において、処理部５０は、これらの変数ａ，ｂを用いて、ｉ＝０，１，２，３の場合にそれぞれｃ＝１，４，７，１０と求める。そして、図６に示すように、処理部５０は、部分行列Ｈ１の１行目の要素のうち、１，４，７，１０列目の要素を「１」とし、それ以外の要素を「０」として行を生成する。【００７８】
次に、ステップＳ１２３において、変数ｂおよび生成処理対象番号ｒをそれぞれ２に更新すると、処理部５０は、周期変数ａ＝３および変数ｂ＝２を用いて、ｉ＝０，１，２，３の場合にそれぞれｃ＝２，５，８，１１と求める。そして、図３に示すように、処理部５０は、部分行列Ｈ１の２行目の要素のうち、２，５，８，１１列目の要素を「１」とし、それ以外の要素を「０」として行を生成する。【００７９】
部分行列Ｈ１の３行目を生成し変数ｂを４に更新すると、ステップＳ１２４において、処理部５０は、変数ｂ＝４が周期変数ａ＝３以下でないと判断し、周波数変数ａを４に更新する。そして、処理部５０は、図６に示すように、周波数変数ａ＝４を用いて部分行列Ｈ１の４行目から７行目までを生成する。【００８０】
部分行列Ｈ１の８行目を生成すると、処理部５０は、生成した行ｒ＝８が最終行であると判断して処理を終了する。以上の手順によって、部分行列Ｈ１が生成される。そして、処理部５０は、部分行列Ｈ１と部分行列Ｈ２とを結合して、図６に示す検査行列Ｈを生成する。【００８１】
図６に示すように、本例では、部分行列Ｈ１において、周期３および周期４についてはそれぞれ全ての位相（１から周期の値までの位相）に対応する行が存在し、周期５については位相１に対応する行だけが存在する。【００８２】
図６に示すように、部分行列Ｈ１の１行目から３行目までのいずれかの行と、４行目から７行目までのいずれかの行と、８行目の行とは、互いに周期が素となっており、共有列が最大でも１つしか存在しない。また、１行目から３行目までのいずれか２つの行を選んだ場合、周期は３で同一であるが位相が互いに異なっており共有列は存在しない。同様に、４行目から７行までのいずれか２つの行を選んだ場合、周期は４で同一であるが位相が互いに異なっており共有列は存在しない。【００８３】
なお、ステップＳ１２１において、生成式としてｃ＝ａ・ｉ＋ｂという条件を用いるのでなく、生成式としてｃ＝ａ・ｉ＋ｋ＋ｒを用いてもよい。そのようにすれば、検査行列Ｈ全体を見た場合の部分行列Ｈ１およびＨ２の位相を合わせることができる。【００８４】
また、周期リストＰは複数の要素を含むものであるが、これら複数の要素は、１つのパラメータから生成するようにすることもできる。例えば、周期リストＰの要素は、互いに素であるという条件だけでなく、並びが昇順であるという条件を満たすものとする。そして、周期リストＰの要素は２つの条件を満たす値のうちの最小値であると定義すると、パラメータとして先頭要素ｐ１だけを定めれば周期リストＰ全体の各要素を決定できる。【００８５】
また、先頭要素ｐ１以外の要素ｐｉは１つ前の要素ｐ（ｉ−１）より大きい素数のうちの最小の素数であると定義しても、先頭要素ｐ１だけを定めれば周期リストＰ全体を決定できる。【００８６】
本実施の形態ではステップＳ１１０において周期リストＰ全体を設定する場合を説明したが、周期リストＰの各要素を１つのパラメータから生成するための定義を取り入れることによって各要素を決定的に導出できるようにしてもよい。この場合、ステップＳ１２５において、処理部５０は、周期変数ａを更新する度に周期リストＰの要素を生成してもよい。例えば、処理部５０は、ステップＳ１１０において要素ｐ１のみを設定し、定義された条件を満たす次の値をステップＳ１２５で求めるようにしてもよい。そのようにすれば、ステップＳ１１０において周期リストＰ全体を設定するのと実質的に等価な動作を実現することができる。【００８７】
また、本実施の形態では、伝送路符号化器がＬＤＰＣ符号化に用いるために検査行列Ｈを生成する場合を説明したが、検査行列生成方法は、伝送路復号器が符号語の復号に用いるために検査行列Ｈを生成する場合にも適用できる。【００８８】
以上のように、本実施の形態によれば、低密度パリティ検査符号に用いるｍ行ｎ列の検査行列Ｈは、左側のｍ行ｋ列の部分行列Ｈ１と右側のｍ行ｍ列の部分行列Ｈ２とから構成される。また、処理部５０は、部分行列Ｈ１に含まれるいずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ（条件ａ）、または周期が同一である場合には互いに異なる位相をもつ（条件ｂ）という条件を満たすように部分行列Ｈ１を生成する。
また、本実施の形態によれば、処理部５０は、部分行列Ｈ２を単位行列として生成する。【００８９】
条件ｂに従って生成された部分行列Ｈ１の行を含む検査行列Ｈの行のいずれの２つの行にも、共有列は常に存在しない。よって、長さ４の短いループが発生しないようにでき、二部グラフ上での短いループによるエラー訂正の性能劣化を防止することができる。【００９０】
また、条件ａに従って生成された部分行列Ｈ１の行を含む検査行列Ｈの行のいずれの２つの行にも、周期の最小公倍数ごとに共有列が存在する。この場合、２つの行の周期は互いに素であるので最小公倍数は周期の積である。周期の積がｋ以上になるように周期を選択すれば、２つの行に共有列は最大でも１つしか存在しないようにできる。よって、長さ４の短いループが発生しないようにでき、二部グラフ上での短いループによるエラー訂正の性能劣化を防止することができる。【００９１】
また、互いに素である複数の周期を用いて行を生成するので、行重みを不均一にすることができる。よって、行重みの均一化によるエラー訂正の性能劣化を防止することができる。【００９２】
さらに、周期と位相が定まれば、簡易な生成式を用いて容易に部分行列Ｈ１を生成することができる。従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列Ｈを生成することができる。また、簡易な方法で部分行列Ｈ１を生成できるので、検査行列の生成コストを低減することができる。【００９３】
また、本実施の形態によれば、部分行列Ｈ２を単位行列として生成するので、入力メッセージがそのまま符号語の一部となる。そのため、処理部５０は、ＬＤＰＣ符号化を行う際に、入力メッセージに追加される冗長部のみの算出すればよく、検査行列Ｈが単位行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。【００９４】
実施の形態２．
次に、本発明の第２の実施の形態を図面を参照して説明する。本実施の形態において、伝送路符号化器の構成は、第１の実施の形態で示したものと同様である。本実施の形態では、伝送路符号化器の処理部５０は、第１の実施の形態と同様の処理に従って部分行列Ｈ１を生成する。また、本実施の形態では、処理部５０は、部分行列Ｈ２を下三角行列として生成する。【００９５】
図７は、処理部５０が部分行列Ｈ２を生成する処理経過の一例を示す流れ図である。本実施の形態では、図７に示すステップＳ２２１において、処理部５０は、第１の実施の形態のステップＳ１２１とは異なる生成式を用いて各行を生成する。なお、ステップＳ２２１以外の処理は、第１の実施の形態で示した処理と同様である。【００９６】
ステップＳ２２１において、処理部５０は、生成式ｃ＝ａ・ｉ＋ｒを用いて部分行列Ｈ２の行ｒを生成する。処理部５０は、生成式ｃ＝ａ・ｉ＋ｒで表される列ｃに位置する行列要素を「１」とし、それ以外の行列要素を「０」として行ｒを生成する。ここで、ｉは、０または負の整数である。なお、周期リストＰは、部分行列Ｈ１を生成する場合と部分行列Ｈ２を生成する場合とで同一であってもよいし、異なっていてもよい。【００９７】
図８は、処理部５０が生成する検査行列Ｈの他の例を示す説明図である。図８に示す検査行列Ｈは、図６に示す検査行列Ｈと同様に、メッセージ長をｋ＝１２、符号語長をｎ＝２０および検査行列Ｈの行数をｍ＝８として生成されたものである。また、図８に示す部分行列Ｈ１およびＨ２は、ともに周期リストＰ＝｛４，５｝として生成されたものである。図８に示すように、処理部５０は、図７に示す手順に従って、部分行列Ｈ２を下三角行列として生成する。【００９８】
図８に示すように、部分行列Ｈ１を生成する場合と同様に、部分行列Ｈ２に含まれるいずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように各行を生成することによって、容易に部分行列Ｈ２を下三角行列として生成することができる。【００９９】
なお、本実施の形態では、部分行列Ｈ２が下三角行列である場合を説明したが、検査行列Ｈの行や列を任意に入れ替えてもエラー訂正特性は同じである。例えば、検査行列Ｈに含まれる要素の上下を反転して部分行列Ｈ２が上三角形行列となるようにしてもよく、ＬＤＰＣ符号化の意味合いは変わらない。また、検査行列Ｈに含まれる要素の左右を反転して、検査行列Ｈの左側のｍ行ｍ列の部分を三角行列としてもよく、ＬＤＰＣ符号化の意味合いは変わらない。【０１００】
また、周期リストＰの複数の要素を、１つのパラメータから生成するようにしてもよい。例えば、周期リストＰの要素は、互いに素であるという条件だけでなく、並びが昇順であるという２つの条件を満たす値のうちの最小値であると定義してもよい。そのようにすれば、パラメータとして先頭要素ｐ１だけを定めれば周期リストＰ全体の各要素を決定できる。また、先頭要素ｐ１以外の要素ｐｉは１つ前の要素ｐ（ｉ−１）より大きい素数のうちの最小の素数であると定義することによって、先頭要素ｐ１だけを定めれば周期リストＰ全体を決定できるようにしてもよい。【０１０１】
また、部分行列Ｈ２を生成する際に、周期リストＰが１つの要素だけを含むようにＰ＝｛ｐ｝と設定し、要素ｐがｍ以上の値となるように設定すると、処理部５０は、部分行列Ｈ２を単位行列として生成する。従って、周期リストＰ＝｛ｐ｝且つｐをｍ以上に設定すると、第１の実施の形態と同様の検査行列Ｈを生成することができる。【０１０２】
また、本実施の形態では、伝送路符号化器がＬＤＰＣ符号化に用いるために検査行列Ｈを生成する場合を説明したが、検査行列生成方法は、伝送路復号器が符号語の復号に用いるために検査行列Ｈを生成する場合にも適用できる。【０１０３】
以上のように、本実施の形態によれば、処理部５０は、部分行列Ｈ２を下三角行列または単位行列として生成する。部分行列Ｈ２を下三角行列として生成した場合、条件ｂに従って生成された検査行列Ｈのいずれの２つの行にも、共有列は常に存在しない。よって、長さ４の短いループが発生しないようにでき、二部グラフ上での短いループによるエラー訂正の性能劣化を防止することができる。【０１０４】
また、部分行列Ｈ２を下三角行列として生成した場合、条件ａに従って生成された検査行列Ｈのいずれか２つの行には、周期の最小公倍数ごとに共有列が存在する。この場合、２つの行の周期は互いに素であるので最小公倍数は周期の積である。周期の積がｎ以上になるように周期を選択すれば、部分行列Ｈ１の２つの行に共有列が最大でも１つしか存在しないようにできるとともに、部分行列Ｈ２の２つの行に共有列が最大でも１つしか存在しないようにできる。よって、長さ４の短いループが発生しないようにでき、二部グラフ上での短いループによるエラー訂正の性能劣化を防止することができる。【０１０５】
また、部分行列Ｈ２を単位行列として生成した場合、条件ｂに従って生成された検査行列Ｈのいずれの２つの行にも、共有列は常に存在しない。よって、長さ４の短いループが発生しないようにでき、二部グラフ上での短いループによるエラー訂正の性能劣化を防止することができる。【０１０６】
また、部分行列Ｈ２を単位行列として生成した場合、条件ａに従って生成された検査行列Ｈのいずれか２つの行には、周期の最小公倍数ごとに共有列が存在する。この場合、２つの行の周期は互いに素であるので最小公倍数は周期の積である。周期の積がｋ以上になるように周期を選択すれば、検査行列Ｈの２つの行に共有列が最大でも１つしか存在しないようにできる。よって、長さ４の短いループが発生しないようにでき、二部グラフ上での短いループによるエラー訂正の性能劣化を防止することができる。【０１０７】
また、本実施の形態によれば、部分行列Ｈ２を下三角行列または単位行列として生成するので、入力メッセージがそのまま符号語の一部となる。そのため、処理部５０は、ＬＤＰＣ符号化を行う際に、入力メッセージに追加される冗長部のみの算出すればよく、検査行列Ｈが単位行列または下三角行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。【０１０８】
実施の形態３．
次に、本発明の第３の実施の形態を図面を参照して説明する。本実施の形態において、伝送路符号化器の構成は、第１の実施の形態および第２の実施の形態で示したものと同様である。本実施の形態では、伝送路符号化器の処理部５０は、部分行列Ｈ１および部分行列Ｈ２を別々に生成するのでなく、部分行列Ｈ１および部分行列Ｈ２を同時に生成する。【０１０９】
図９は、処理部５０が検査行列Ｈを生成する処理経過の一例を示す流れ図である。本実施の形態では、図９に示すステップＳ３２１において、処理部５０は、第１の実施の形態および第２の実施の形態とは異なる生成式を用いて各行を生成する。なお、ステップＳ３２１以外の処理は、第１の実施の形態および第２の実施の形態と同様である。【０１１０】
ステップＳ３２１において、処理部５０は、生成式ｃ＝ａ・ｉ＋ｋ＋ｒを用いて検査行列Ｈを生成する。処理部５０は、生成式ｃ＝ａ・ｉ＋ｋ＋ｒで表される列ｃに位置する行列要素を「１」とし、それ以外の行列要素を「０」として行ｒを生成する。ここで、ｉは、０または負の整数である。【０１１１】
図１０は、処理部５０が生成する検査行列Ｈのさらに他の例を示す説明図である。図１０に示す検査行列Ｈは、図６および図８に示す検査行列Ｈと同様に、メッセージ長をｋ＝１２、符号語長をｎ＝２０および検査行列Ｈの行数をｍ＝８として生成されたものである。また、図１０に示す検査行列Ｈは、ステップＳ１１０において周期リストＰ＝｛４，５｝と設定されて生成されたものである。【０１１２】
図１０に示すように、処理部５０は、図９に示す手順に従って、検査行列Ｈに含まれるいずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように各行を生成する。
従って、いずれか任意の２行に共有列が存在しないか、または最大でも１つしか存在しないようにできる。また、図１０に示すように、処理部５０は、図９に示す手順に従って、検査行列Ｈのうち部分行列Ｈ２を下三角行列として生成する。【０１１３】
なお、本実施の形態では、検査行列Ｈのうち部分行列Ｈ２が下三角行列である場合を説明したが、検査行列Ｈの行や列を任意に入れ替えてもエラー訂正特性は同じである。例えば、検査行列Ｈに含まれる要素の上下を反転して部分行列Ｈ２が上三角形行列となるようにしてもよく、ＬＤＰＣ符号化の意味合いは変わらない。また、検査行列Ｈに含まれる要素の左右を反転して、検査行列Ｈの左側のｍ行ｍ列の部分を三角行列としてもよく、ＬＤＰＣ符号化の意味合いは変わらない。【０１１４】
また、本実施の形態では、図９に示す手順に従って処理を実行することにより、処理部５０は、以下の条件に従って検査行列Ｈを生成する。ステップＳ１１０において設定される周期リストＰをＰ＝｛ｐ（１），ｐ（２），・・・，ｐ（ＰＬ）｝とし、Ｎ（ｊ）を周期リストＰの１番目からｊ番目までの要素の値の合計とする。また、Ｎ（０）＝０と定義する。生成対象行番号ｒがＮ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）を満たす場合には、処理部５０は、周期変数ａ＝ｐ（ｊ）を用いて、１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｐ（ｊ）・ｉ＋ｎ−ｍ＋ｒを満たす列ｃの行列要素を「１」とし、それ以外の行列要素を「０」として行ｒを生成する。ここで、ｉは、整数である。【０１１５】
また、本実施の形態ではステップＳ３２１において１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｐ（ｊ）・ｉ＋ｎ−ｍ＋ｒを満たす列ｃの要素を「１」とする場合を説明したが、要素を「１」とする条件は、本実施の形態で示したものに限られない。例えば、生成対象行番号ｒがＮ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）を満たす場合に、処理部５０は、周期リストＰの要素番号ｊを用いて定まる所定の値Ｆ（ｊ）を用いて、「１」とする要素を定めてもよい。この場合、処理部５０は、ステップＳ３２１において、１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）を満たす列ｃ、およびｃ＝ｎ−ｍ＋ｒを満たす列ｃに位置する行列要素を「１」とし、それ以外の行列要素を「０」として行ｒを生成する。そのようにすれば、検査行列ＨのうちＨ２に相当する部分を単位行列として生成することができる。【０１１６】
要素番号ｊを用いて定まる値Ｆ（ｊ）として、例えば、Ｆ（ｊ）＝−Ｎ（ｊ−１）を用いてもよい。また、例えば、Ｆ（ｊ）＝ｎ−ｍを用いてもよい。【０１１７】
また、本実施の形態では、ステップＳ１１０において周期リストが１つだけ設定される場合を説明したが、設定される周期リストは１つに限られない。例えば、周期リストＰに加えて、ステップＳ１１０において周期リストＱ＝｛ｑ（１），ｑ（２），・・・ｑ（ＱＬ）｝を設定してもよい。この場合に、Ｍ（ｊ）をリストＱの１番目からｊ番目までの要素の値の合計とし、Ｍ（０）＝０と定義する。そして、処理部５０は、２つの条件を用いて「１」とする要素を定めてもよい。【０１１８】
例えば、生成対象行番号ｒがＮ（ｊ−１）＋１≦ｒ≦Ｎ（ｊ）を満たす場合には、処理部５０は、ステップＳ３２１において、１≦ｃ≦ｎ−ｍ且つｃ＝ｐ（ｊ）・ｉ＋ｒ＋Ｆ（ｊ）を満たす列ｃに位置する行列要素を「１」とする。更に、生成対象行番号ｒがＭ（ｊ−１）＋１≦ｒ≦Ｍ（ｊ）を満たす場合には、処理部５０は、ｎ−ｍ＋１≦ｃ≦ｎ−ｍ＋ｒ且つｃ＝ｑ（ｊ）・ｉ＋ｎ−ｍ＋ｒを満たす列ｃに位置する行列要素を「１」とし、それ以外の行列要素を「０」として行ｒを生成する。なお、Ｆ（ｊ）として、例えば、Ｆ（ｊ）＝−Ｎ（ｊ−１）を用いてもよく、Ｆ（ｊ）＝ｎ−ｍを用いてもよい。【０１１９】
また、周期リストＰの複数の要素を、１つのパラメータから生成するようにしてもよい。例えば、周期リストＰの要素は、互いに素であるという条件だけでなく、並びが昇順であるという２つの条件を満たす値のうちの最小値であると定義してもよい。そのようにすれば、パラメータとして先頭要素ｐ１だけを定めれば周期リストＰ全体の各要素を決定できる。また、先頭要素ｐ１以外の要素ｐ（ｊ）は１つ前の要素ｐ（ｊ−１）より大きい素数のうちの最小の素数であると定義することによって、先頭要素ｐ１だけを定めれば周期リストＰ全体を決定できるようにしてもよい。【０１２０】
また、本実施の形態では、伝送路符号化器がＬＤＰＣ符号化に用いるための検査行列Ｈを生成する場合を説明したが、検査行列生成方法は、伝送路復号器が符号語の復号に用いるための検査行列Ｈを生成する場合にも適用できる。【０１２１】
以上のように、本実施の形態によれば、部分行列ごとに生成することなく、いずれか任意の２行を選んだ場合に、２つの行が互いに素となる周期をもつ、または周期が同一である場合には互いに異なる位相をもつという条件を満たすように、検査行列を一括して生成することができる。また、部分行列ごとに生成することなく、下三角行列または単位行列を含むように検査行列を一括して生成することができる。従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成することができる。また、検査行列が下三角行列や単位行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。【０１２２】
実施の形態４．
さらに、本発明の第４の実施の形態を図面を参照して説明する。本実施の形態では、第１の実施の形態から第３の実施の形態までに示した伝送路符号化器および伝送路復号器のうちのいずれかを適用したデータ伝送システムを説明する。本発明によるデータ伝送システムの構成は、図１に示すものと同様である。データ発生器１０は、伝送すべきデータ列を生成すると、生成したデータ列を伝送路符号化器１１に出力する。すなわち、データ発生器１０は、発生したデータ列を伝送路符号化器１１に供給する。【０１２３】
伝送路符号化器１１は、第１の実施の形態から第３の実施の形態までに示した検査行列生成方法を実現する構成のいずれかを実装している。例えば、伝送路符号化器１１は、検査行列を生成するための検査行列生成プログラムがインストールされている。伝送路符号化器１１は、周期リストＰにもとづいて検査行列Ｈを生成する。また、伝送路符号化器１１は、データ発生器１０から供給されたデータ列を、生成した検査行列Ｈを用いて符号語に変換する。そして、伝送路符号化器１１は、伝送路１２を介して符号語を伝送路復号器１３に送信する。【０１２４】
伝送路復号器１３は、検査行列生成方法を実現する構成を実装している。例えば、伝送路復号器１３は、検査行列を生成するための検査行列生成プログラムがインストールされている。伝送路復号器１３は、周期リストＰにもとづいて検査行列Ｈを生成する。また、伝送路復号器１３は、受信した符号語から、生成した検査行列Ｈを用いて、sum-product 復号法に従って元のデータ列を復元する。そして、伝送路復号器１３は、復元したデータ列をデータ消費器１４に出力する。すなわち、伝送路復号器１３は、復元したデータ列をデータ消費器１４に供給する。【０１２５】
データ消費器１４は、伝送路復号器１３から供給されたデータ列を消費する。すなわち、データ消費器１４は、供給されたデータ列を処理して表示や出力を行う。【０１２６】
例えば、データ伝送システムがビデオデータ伝送用のシステムである場合には、データ発生器１０はビデオ符号化器であり、データ発生器１０が発生するデータ列はビットストリームである。また、データ消費器１４はビデオ復号器である。【０１２７】
伝送路符号化器１１および伝送路復号器１３は、それぞれ同じ周期リストＰを用いる。周期リストＰの同一性を保つ方法として、伝送路符号化器１１および伝送路復号器１３それぞれに同じ周期リストＰを初期値として与えておく方法を用いてもよい。また、外部入力によって周期リストＰが与えられる場合には、外部入力された周期リストＰを伝送路符号化器１１および伝送路復号器１３それぞれに通知するようにしてもよく、伝送路符号化器１１および伝送路復号器１３は、それぞれ通知された周期リストＰを用いるようにしてもよい。【０１２８】
また、伝送路符号化器１１が周期リストＰを設定し、設定した周期リストＰを伝送路符号化器１１が伝送路１２を介して伝送路復号器１３に送信（通知）する方法を用いてもよい。この場合、伝送路１２のエラー発生モデルによって周期リストＰの最適値が異なる。伝送路符号化器１１は、周期リストＰを、符号語を送信するごとに送信（通知）してもよいし、周期リストＰを更新した時のみ送信（通知）するようにしてもよい。また、周期リストＰの変更を予め定めた所定の期間ごとに行う場合には、伝送路符号化器１１は、所定の期間ごとに変更後の周期リストＰを伝送路復号器１３に送信（通知）してもよい。【０１２９】
また、伝送路１２のエラー発生状況を最初に知るのは伝送路復号器１３である。そのため、周期リストＰの設定を伝送路復号器１３が行ってもよい。この場合、伝送路符号化器１１が周期リストＰを伝送路復号器１３に送信するのでなく、伝送路復号器１３が伝送路１２を介して周期リストＰを伝送路符号化器１１に送信（通知）する。【０１３０】
また、周期リストＰの各要素を１つのパラメータから生成するための定義を取り入れて、周期リストＰの先頭要素にもとづいて先頭要素以降の各要素を決定できる場合には、伝送路符号化器１１または伝送路復号器１３は、先頭要素のみを送信（通知）するようにしてもよい。例えば、周期リストＰの要素は、互いに素であるという条件だけでなく、並びが昇順であるという２つの条件を満たす値のうちの最小値であると定義することによって、先頭要素ｐ１だけを定めれば周期リストＰ全体の各要素を決定できるようにしてもよい。また、先頭要素ｐ１以外の要素ｐ（ｊ）は１つ前の要素ｐ（ｊ−１）より大きい素数のうちの最小の素数であると定義することによって、先頭要素ｐ１だけを定めれば周期リストＰ全体を決定できるようにしてもよい。【０１３１】
また、検査行列のサイズを変更したい場合には、伝送路符号化器１１は、変更後の検査行列の行数や列数を、伝送路１２を介して伝送路復号器１３に送信（通知）するようにしてもよい。また、検査行列のサイズを変更したい場合には、伝送路復号器１３は、変更後の検査行列の行数や列数を、伝送路１２を介して伝送路符号化器１１に送信（通知）するようにしてもよい。【０１３２】
以上のように、本実施の形態によれば、データ伝送システムにおいて、伝送路符号化器１１および伝送路復号器１３は、第１の実施の形態から第３の実施の形態までに示した検査行列生成方法のうちのいずれかを用いて検査行列を生成する。従って、低密度パリティ検査符号において、優れたエラー訂正特性を実現することができ、簡素な方法で検査行列を生成することができる。また、検査行列が下三角行列や単位行列を含まない場合と比較して生成行列の生成コストや符号化コストを低減することができる。【０１３３】
また、本実施の形態によれば、周期リストＰまたは周期リストＰの先頭要素がわかれば検査行列を決定できる。そのため、伝送路符号化器１１または伝送路復号器１３のうちのいずれか一方が周期リストＰまたは先頭要素を他方に通知すれば、伝送路符号化器１１および伝送路復号器１３は、同じ検査行列を共有することができる。【０１３４】
また、検査行列のサイズを変更する場合には、伝送路符号化器１１または伝送路復号器１３のうちのいずれか一方が行列サイズを他方に通知すれば、検査行列のサイズを容易に変更することができる。従って、伝送路１２の特性やパケット交換網の輻輳状況が変化する場合であっても、データ伝送の時点で伝送に最適な検査行列を容易に利用することができる。
【産業上の利用可能性】
【０１３５】
本発明による検査行列生成方法は、データ列をＬＤＰＣ符号化するために用いる検査行列を、データ伝送システムに含まれる伝送路符号化器が生成する場合に適用できる。また、検査行列生成方法は、受信した符号語を復号するために用いる検査行列を、データ伝送システムに含まれる伝送路復号器が生成する場合に適用できる。
【図１】
0004386198.tif 000002
【図２】
0004386198.tif 000003
【図３Ａ】
0004386198.tif 000004
【図３Ｂ】
0004386198.tif 000005
【図４】
0004386198.tif 000006
【図５】
0004386198.tif 000007
【図６】
0004386198.tif 000008
【図７】
0004386198.tif 000009
【図８】
0004386198.tif 000010
【図９】
0004386198.tif 000011
【図１０】
0004386198.tif 000012