(57)【要約】 【課題】  低コストで、演算処理時間が短いＬＤＰＣ符号の符号化器および復号器を備えた信号処理装置を提供することを目的とする。  【解決手段】  Ｌ行Ｌ列の正方行列ＦおよびＫ行Ｍ列の行列Ｐを用いて、Ｋ行Ｎ列の生成行列ＧおよびＭ行Ｎ列のパリティ検査行列Ｈを定義することにより、Ｋビットの情報ビットにＭビットの検査ビットを付加してＮビットの符号語を生成する低密度パリティ検査符号の符号化器と、Ｎビットの符号語に基づいてＫビットの情報ビットを復元する低密度パリティ検査符号の復号器とを簡単に構成できる信号処理装置を提供する。【選択図】  図９          
2005340920.tif 000002
【特許請求の範囲】
【請求項１】
Ｋビットの情報ビットにＭビットの検査ビットを付加してＮビットの符号語を生成する低密度パリティ検査符号の符号化器と、
Ｎビットの符号語に基づいてＫビットの情報ビットを復元する低密度パリティ検査符号の復号器とを有し、
数１に示すＬ行Ｌ列の正方行列Ｆを用いて、数２のＫ行Ｍ列の行列Ｐを構成したときに、前記符号化器におけるＫ行Ｎ列の生成行列Ｇが数３で与えられ、前記復号器におけるＭ行Ｎ列のパリティ検査行列Ｈが数４で与えられることを特徴とする信号処理装置。
ただし、数２において、記号^は行列のべき乗を、n11〜nabは整数を表し、数３においてIKはＫ行Ｋ列の単位行列を表し、数４において記号T は行列の転置、IMはＭ行Ｍ列の単位行列を表す。
【数１】
2005340920.tif 000030
【数２】
2005340920.tif 000031
【数３】
2005340920.tif 000032
【数４】
2005340920.tif 000033
【請求項２】
前記数２の行列Ｐにおいて、列方向の指数n1j , n2j , n3j ,・・・, naj は等差級数であり、各列の等差級数の公差が相異なることを特徴とする請求項１に記載された信号処理装置。
【請求項３】
前記数２の行列Ｐにおいて、一列の指数n1k , n2k , n3k ,・・・, nakが全て同一であり、その他の列の指数n1j , n2j , n3j ,・・・, najが等差級数であり、各列の等差級数の公差が相異なることを特徴とする請求項１に記載された信号処理装置。
【請求項４】
前記数２の行列Ｐにおいて、指数nij のLに関する剰余nij mod Lは、任意に選んだ長方形の４つの頂点で数５に示す配列にならないことを特徴とする請求項１に記載された信号処理装置。ただし、数５のｕ、ｖは整数である。
【数５】
2005340920.tif 000034
【請求項５】
前記数２の行列Ｐにおいて、指数nij のLに関する剰余nij mod Lは、任意に選んだ長方形の４つの頂点で数６に示す配列にならないことを特徴とする請求項１に記載された信号処理装置。ただし、数６のｕ、ｖは整数である。
【数６】
2005340920.tif 000035
【請求項６】
Ｋｃビットの情報ビットにＭｃビットの検査ビットを付加してＮｃビットの符号語を生成する低密度パリティ検査符号の符号化器と、
Ｎｃビットの符号語に基づいてＫｃビットの情報ビットを復元する低密度パリティ検査符号の復号器とを有し、
前記数２の行列Ｐから少なくとも一つの行を削除して、あるいは少なくとも一つの列を削除して、あるいは少なくとも一つの行と少なくとも一つの列を削除して、Ｋｃ行Ｍｃ列の行列Ｐｃを構成したときに、前記符号化器におけるＫｃ行Ｎｃ列の生成行列Ｇｃが数７で与えられ、前記復号器におけるＭｃ行Ｎｃ列のパリティ検査行列Ｈｃが数８で与えられることを特徴とする信号処理装置。
ただし、数７においてIKc はＫｃ行Ｋｃ列の単位行列を表し、数８においてIMc はＭｃ行Ｍｃ列の単位行列を表す。
【数７】
2005340920.tif 000036
【数８】
2005340920.tif 000037
【請求項７】
低密度パリティ検査符号のパラメータを決定するステップと、
正方行列を定義するステップと、
該正方行列のべき乗で構成される部分行列を定義するステップと、
該部分行列と単位行列とで構成される生成行列を定義するステップと、
該定義された生成行列と情報ビットとを乗じて低密度パリティ検査符号を生成するステップとを有することを特徴とする低密度パリティ検査符号の符号化方法。
【請求項８】
低密度パリティ検査符号のパラメータを決定するステップと、
正方行列を定義するステップと、
該正方行列のべき乗で構成される部分行列を定義するステップと、
該部分行列と単位行列とで構成されるパリティ検査行列を定義するステップと、
該定義されたパリティ検査行列に基づいて、繰返し演算処理を実行して低密度パリティ検査符号を復号するステップとを有することを特徴とする低密度パリティ検査符号の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル情報を伝送路に送信して、これを受信する通信装置における信号処理装置、あるいはディジタル情報を記録媒体に記録して再生する記録再生装置における信号処理装置、あるいは信号処理装置における符号化方法および復号方法に関する。
【背景技術】
【０００２】
従来より、誤り訂正符号の一種として、低密度パリティ検査（ＬＤＰＣ）符号が知られている。このＬＤＰＣ符号の符号化器は、ハミング符号などの誤り訂正符号と同様に、Ｋビットの情報ビットにＭビットの検査ビットを付加してＮ＝Ｋ＋Ｍビットの符号語を生成する。このとき、従来のハミング符号などと同様に、Ｋビットの情報ビットにＫ行Ｎ列の生成行列を乗じればＮビットの符号語を生成できる。
【０００３】
一方、ＬＤＰＣ符号の復号器は、Ｎ＝Ｋ＋Ｍ ビットの符号語に基づいて、Ｋビットの情報ビットを復元する。このとき、Ｍ行Ｎ列のパリティ検査行列に基づいてＳｕｍ−ｐｒｏｄｕｃｔ復号法と呼ばれる繰返し演算処理を行なうと、強力な誤り訂正が可能となり、高い復号性能を得ることができる。
【０００４】
ＬＤＰＣ符号は、一般に、Ｍ行Ｎ列のパリティ検査行列によって定義される。このパリティ検査行列の要素は大半が０であり、１は稀にしか存在しない。このようにパリティ検査行列においては、要素１の密度が低いため、特に、低密度パリティ検査符号と呼ばれている。また、このパリティ検査行列の構成法としては、非特許文献１および２あるいは特許文献１に記載された方法が知られている。
【非特許文献１】Ｒ．Ｇ．Ｇａｌｌａｇｅｒ、 “Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ Ｃｏｄｅｓ、“ Ｃａｍｂｒｉｄｇｅ、 ＭＡ：ＭＩＴ Ｐｒｅｓｓ、 １９６３．
【非特許文献２】Ｄ．Ｊ．Ｃ．ＭａｃＫａｙ、 “Ｇｏｏｄ Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅｓ Ｂａｓｅｄ ｏｎ Ｖｅｒｙ Ｓｐａｒｓｅ Ｍａｔｒｉｃｅｓ、“ ＩＥＥＥ Ｔｒａｎｓ． Ｉｎｆｏｒｍ． Ｔｈｅｏｒｙ、 ｖｏｌ．４５、 Ｎｏ．２、 ｐｐ．３９９−４３１、 Ｍａｒ． １９９９．
【特許文献１】特開２００３−１１５７６８号公報
【０００５】
ここで、非特許文献１に記載された方法は、規則的な要素配列を有する部分行列を複数個並べた後、コンピュータで発生した乱数に基づいて、行列の列配置を入れ替えてパリティ検査行列を生成するものである。そして、こうして得られたパリティ検査行列に対して、ガウス消去法をはじめとする複数ステップの行列演算処理を施すことにより、生成行列を算出できるというものである。
【０００６】
図１０に、非特許文献１に記載された方法で生成したパリティ検査行列の例を示す。ここで、図１０の行列の１行目から５行目は、要素１が規則的に並んでいる。また、５行目から１０行目は、一定の規則に従って1行目から５行目の列配置を入れ替えたものであり、１１行目から１５行目は、乱数を用いて1行目から５行目の列配置をランダムに入れ替えたものである。
【０００７】
非特許文献２に記載された方法は、コンピュータで発生した乱数に基づいて、パリティ検査行列の要素が１となる位置を決めるが、その位置がＬＤＰＣ符号の性能上望ましくない場合には修正を施すという試行錯誤を必要とする。こうして得られたパリティ検査行列に対して、複数ステップの行列演算処理を施すことにより、生成行列を算出できる。
【０００８】
特許文献１に記載された方法は、規則的な要素配列を有する部分行列を一定の規則に従って複数個並べることにより、演繹的にパリティ検査行列を生成するものである。そして、こうして得られたパリティ検査行列に対して、複数ステップの行列演算処理を施すことにより、生成行列を算出できる。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記の従来技術においては、ＤＳＰ（ＤＳＰ：Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）等を用いたソフトウェア演算で符号化器を実現する場合、符号語を生成するために複数ステップにわたる煩雑な行列演算を行なう必要があった。このため符号化に要する演算処理時間が長くなるという問題点があった。
【００１０】
また、ＬＳＩ（ＬＳＩ：Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｅｄ ｃｉｒｃｕｉｔ）等を用いたハードウェア回路で符号化器を実現する場合、予めパリティ検査行列に行列演算処理を施して生成行列を算出しておけばよいが、こうして得られた生成行列は、パリティ検査行列とは違って要素１の密度が高い。一般に、符号化器の回路規模は、生成行列における要素１の密度にほぼ比例するため、従来技術においては、符号化器が複雑となるという問題点があった。
【００１１】
さらに、ＬＳＩ等を用いたハードウェア回路で復号器を実現する場合、非特許文献１および２に記載された方法では、パリティ検査行列における要素１の配置が不規則であるため、復号器のメモリ制御回路が複雑になり、この結果復号器が複雑となるという問題点があった。
【００１２】
そこで、本発明は、上記の問題点に鑑みてなされたものであり、ソフトウェア演算で実現された演算処理時間が短いＬＤＰＣ符号の符号化器を有する信号処理装置を提供することを目的としている。
また、ハードウェア回路で実現された簡単で低コストのＬＤＰＣ符号の符号化器および復号器を備えた信号処理装置を提供することを目的としている。
【課題を解決するための手段】
【００１３】
請求項１に係る発明は、Ｋビットの情報ビットにＭビットの検査ビットを付加してＮビットの符号語を生成する低密度パリティ検査符号の符号化器と、Ｎビットの符号語に基づいてＫビットの情報ビットを復元する低密度パリティ検査符号の復号器とを有し、数１に示すＬ行Ｌ列の正方行列Ｆを用いて、数２のＫ行Ｍ列の行列Ｐを構成したときに、前記符号化器におけるＫ行Ｎ列の生成行列Ｇが数３で与えられ、前記復号器におけるＭ行Ｎ列のパリティ検査行列Ｈが数４で与えられることを特徴とする信号処理装置を提案している。
【００１４】
この発明によれば、要素１の密度が低い正方行列Ｆのべき乗を用いて生成行列を定義したので、ソフトウエア演算で符号化器を構成する場合、演算処理を高速化できる。また、ハードウエア回路で符号化器を実現する場合には、構成を簡素化することができる。さらに、正方行列Ｆのべき乗を用いてパリティ検査行列を定義したので、ハードウエア回路で復号器を実現する場合、メモリ制御の簡素化が可能であるため、復号器全体の構成を簡素化することができる。
【００１５】
請求項２に係る発明は、請求項１に記載された信号処理装置について、前記数２の行列Ｐにおいて、列方向の指数n1j , n2j , n3j ,・・・, naj は等差級数であり、各列の等差級数の公差が相異なることを特徴とする信号処理装置を提案している。
【００１６】
この発明によれば、数２の行列Ｐにおいて、列方向の指数n1j , n2j , n3j ,・・・, naj は等差級数であり、各列の等差級数の公差は相異なるようにしたので、任意に選んだ長方形の頂点がすべて１となるようなパリティ検査行列を生成することがない。
【００１７】
請求項３に係る発明は、請求項１に記載された信号処理装置について、前記数２の行列Ｐにおいて、一列の指数n1k , n2k , n3k ,・・・, nakが全て同一であり、その他の列の指数n1j , n2j , n3j ,・・・, najが等差級数であり、各列の等差級数の公差が相異なることを特徴とする信号処理装置を提案している。
【００１８】
この発明によれば、前記数２の行列Ｐにおいて、一列の指数n1k , n2k , n3k ,・・・, nakが全て同一であり、その他の列の指数n1j , n2j , n3j ,・・・, najは等差級数であり、各列の等差級数の公差は相異なるようにしたので、任意に選んだ長方形の頂点がすべて１となるようなパリティ検査行列を生成することがない。
【００１９】
請求項４に係る発明は、請求項１に記載された信号処理装置について、前記数２の行列Ｐにおいて、指数nij のLに関する剰余nij mod Lは、任意に選んだ長方形の４つの頂点で数５に示す配列にならないことを特徴とする信号処理装置を提案している。
【００２０】
この発明によれば、数２の行列Ｐにおいて、指数nij のLに関する剰余nij mod Lは、任意に選んだ長方形の４つの頂点で数５のように一致しないように構成したため、任意に選んだ長方形の頂点がすべて１となるようなパリティ検査行列を生成することがない。
【００２１】
請求項５に係る発明は、請求項１に記載された信号処理装置について、前記数２の行列Ｐにおいて、指数nij のLに関する剰余nij mod Lは、任意に選んだ長方形の４つの頂点で数６のように一致しないことを特徴とする信号処理装置を提案している。
【００２２】
この発明によれば、数２の行列Ｐにおいて、指数nij のLに関する剰余nij mod Lは、任意に選んだ長方形の４つの頂点で数６のように一致しないように構成したため、任意に選んだ長方形の頂点がすべて１となるようなパリティ検査行列を生成することがない。
【００２３】
請求項６に係る発明は、Ｋｃビットの情報ビットにＭｃビットの検査ビットを付加してＮｃビットの符号語を生成する低密度パリティ検査符号の符号化器と、Ｎｃビットの符号語に基づいてＫｃビットの情報ビットを復元する低密度パリティ検査符号の復号器とを有し、前記数２の行列Ｐから少なくとも一つの行を削除して、あるいは少なくとも一つの列を削除して、あるいは少なくとも一つの行と少なくとも一つの列を削除して、Ｋｃ行Ｍｃ列の行列Ｐｃを構成したときに、前記符号化器におけるＫｃ行Ｎｃ列の生成行列Ｇｃが数７で与えられ、前記復号器におけるＭｃ行Ｎｃ列のパリティ検査行列Ｈｃが数８で与えられることを特徴とする信号処理装置を提案している。
【００２４】
この発明によれば、生成行列Ｇｃおよびパリティ検査行列Ｈｃを数７および数８のように定義することにより、任意の情報ビット数Ｋｃ、検査ビット数Ｍｃ、符号ビット数Ｎｃを有する低密度パリティ検査符号を用途に応じて自由に設計することができる。
【００２５】
請求項７に係る発明は、低密度パリティ検査符号のパラメータを決定するステップと、  正方行列を定義するステップと、該正方行列のべき乗で構成される部分行列を定義するステップと、該部分行列と単位行列とで構成される生成行列を定義するステップと、該定義された生成行列と情報ビットとを乗じて低密度パリティ検査符号を生成するステップとを有することを特徴とする低密度パリティ検査符号の符号化方法を提案している。
【００２６】
請求項８に係る発明は、低密度パリティ検査符号のパラメータを決定するステップと、  正方行列を定義するステップと、該正方行列のべき乗で構成される部分行列を定義するステップと、該部分行列と単位行列とで構成されるパリティ検査行列を定義するステップと、  該定義されたパリティ検査行列に基づいて、繰返し演算処理を実行して低密度パリティ検査符号を復号するステップとを有することを特徴とする低密度パリティ検査符号の復号方法を提案している。
【発明の効果】
【００２７】
本発明のＬＤＰＣ符号は、正方行列の行数Ｌ、情報ビット数Ｋ、検査ビット数Ｍ、符号語長Ｎを任意に選択することができるため、応用事例に適合した符号設計が可能である。また、符号化器、復号器も、ソフトウェア演算量あるいはハードウェア回路量と復号性能とに応じて自由度の高い設計が可能である。
【００２８】
また、本発明のＬＤＰＣ符号の符号化器をＤＳＰ等のソフトウェア演算で実現する場合、符号語を生成するために複数ステップにわたる煩雑な行列演算を行なう必要がなく、このため符号化に要する演算処理時間を短縮できるという効果がある。また、本発明のＬＤＰＣ符号の符号化器をＬＳＩ等のハードウェア回路で実現する場合、生成行列における要素１の密度が低いため検査ビットを生成する回路が簡単になり、この結果符号化器が簡単となる効果がある。
【００２９】
さらに、本発明のＬＤＰＣ符号の復号器をＬＳＩ等のハードウェア回路で実現する場合、パリティ検査行列における要素１の配置が規則的であるため、復号器のメモリ制御回路が簡単になり、この結果復号器が簡単となる効果がある。したがって、本発明のＬＤＰＣ符号化器と復号器は、ソフトウェア実現する場合には演算処理時間が短く、ハードウェア実現する場合には簡単で低コストであり、特に、符号語長Ｎが長い場合や複数のＬＤＰＣ符号を併用する場合に、その効果は顕著である。
【発明を実施するための最良の形態】
【００３０】
以下、図１から図９を参照して、本発明の実施例について詳細に説明する。
【実施例】
【００３１】
本発明の信号処理装置におけるＬＤＰＣ符号を用いた符号化処理は、図９(ａ)に示すような処理過程により実現される。すなわち、まず最初に、ＬＤＰＣ符号のパラメータを決定する（ステップ１０１）。ＬＤＰＣ符号のパラメータが決定すると、次に、正方行列Ｆ、部分行列Ｐ、生成行列Ｇをそれぞれ順に定義する（ステップ１０２から１０４）。ＬＤＰＣ符号のパラメータが決定され、正方行列Ｆ、部分行列Ｐ、生成行列Ｇがそれぞれ定義されると、情報ビット列に対して、定義された生成行列Ｇを乗ずることによりＬＤＰＣ符号が生成される（ステップ１０５）。
これを、具体例に基づいて、説明すると以下のようになる。
【００３２】
すなわち、本発明のＬＤＰＣ符号は、Ｌ行Ｌ列の正方行列を構成要素として、生成行列とパリティ検査行列を定義する。例えばＬ＝６とし、数１のような正方行列Ｆを定義する。ここで、行列のべき乗を記号＾で表記し、正方行列Ｆのべき乗Ｆ＾２, Ｆ＾３、・・・、Ｆ＾５、 Ｆ＾６を計算すると、数２から数５のようになる。
【００３３】
【数１】
2005340920.tif 000003
【００３４】
【数２】
2005340920.tif 000004
【００３５】
【数３】
2005340920.tif 000005
【００３６】
【数４】
2005340920.tif 000006
【００３７】
【数５】
2005340920.tif 000007
【００３８】
すなわち、Ｆ＾６が単位行列となるため、正方行列Ｆの任意のべき乗Ｆ＾ｎはＦ＾（ｎｍｏｄ ６）で表現できる。なお、本発明の一実施例においては、数１の正方行列Ｆを用いて数６に示す行列Ｐを構成し、生成行列Ｇを数７でパリティ検査行列Ｈを数８で定義する。
【００３９】
【数６】
2005340920.tif 000008
【００４０】
【数７】
2005340920.tif 000009
【００４１】
【数８】
2005340920.tif 000010
【００４２】
ここで、生成行列Ｇの行数は情報ビット数Ｋを表し、パリティ検査行列の行数は検査ビット数Ｍを表し、両行列の列数は符号語長Ｎを表す。よって、上記例の場合、Ｋ＝２４、Ｍ＝１８、Ｎ＝Ｋ＋Ｍ＝４２である。数７の生成行列を図１に、数８のパリティ検査行列を図２に示す。図中、行列Oは全要素が０である零行列を示す。
【００４３】
このように本発明においては、図１の生成行列Ｇも図２のパリティ検査行列Hも要素０が大半を占めており、要素１の密度が低くなっている。また、従来のようにパリティ検査行列から生成行列を算出する必要は無く、パリティ検査行列Hと同時に生成行列Ｇを定義できる。したがって、本実施例の符号化器においては、容易に符号語を生成することができる。
【００４４】
符号化器は、数９のように情報ビット列ｓに生成行列Ｇを乗じて符号語ｃを生成する。ここで、情報ビット列ｓはＫ行１列の列ベクトル、符号語ｃはＮ行１列の列ベクトルである。
【００４５】
【数９】
2005340920.tif 000011
【００４６】
復号器は、後述するＳｕｍ−ｐｒｏｄｕｃｔ復号法を用いて符号語ｃを復元するが、符号語ｃにパリティ検査行列Ｈを乗じると、数１０のように全要素がゼロであるＭ行1列の列ベクトルｏが得られるので、復号結果の正誤を簡単に確認できる。
【００４７】
【数１０】
2005340920.tif 000012
【００４８】
一般に、ＬＤＰＣ符号のパリティ検査行列の中で任意に選んだ長方形の４つの頂点全てに要素１が存在する、すなわち、数１１に示すようなパターンが存在すると、復号性能が悪化することが知られている。
【００４９】
【数１１】
2005340920.tif 000013
【００５０】
数６の行列Ｐにおいて正方行列Ｆの指数に着目すると、各列の指数は（１、２、３、４）、（５、４、３、２）、（１、３、５、７）となっており、各々公差が１、−１、２と異なる等差級数になっている。このように、等差級数の公差が互いに異なるように行列Ｐを構成するとともに、数１２あるいは数１３というパターンが存在しないように行列Ｐを構成することにより、パリティ検査行列Ｈにおいて数１１に示すようなパターンが発生しなくなる。
【００５１】
【数１２】
2005340920.tif 000014
【００５２】
【数１３】
2005340920.tif 000015
【００５３】
前述のように、図１の生成行列と図２のパリティ検査行列で定義されるＬＤＰＣ符号は、情報ビット数Ｋ＝２４、検査ビット数Ｍ＝１８、符号語長Ｎ＝Ｋ＋Ｍ＝４２であった。これに対し図３のように、図２のパリティ検査行列Ｈから左端の４列を削除したパリティ検査行列Ｈｃを用いて、情報ビット数Ｋｃ＝２０、検査ビット数Ｍｃ＝１８、符号語調Ｎｃ＝Ｋｃ＋Ｍｃ＝３８の符号を構成することができる。また、図４のように、図２のパリティ検査行列Hから下端の３行と右端の３列を削除したパリティ検査行列Ｈｄを用いて、情報ビット数Ｋｄ＝２４、検査ビット数Ｍｄ＝１５、符号語長Ｎｄ＝Ｋｄ＋Ｍｄ＝３９の符号を構成することができる。
【００５４】
次に、図９（ｂ）を用いて、本実施例の復号器におけるＬＤＰＣ符号の復号処理について説明する。
本実施例の復号器におけるＬＤＰＣ符号の復号処理は、まず最初に、ＬＤＰＣ符号のパラメータを決定する（ステップ２０１）。ＬＤＰＣ符号のパラメータが決定すると、次に、正方行列Ｆ、部分行列Ｐ、パリティ検査行列Ｈをそれぞれ順に定義する（ステップ２０２から２０４）。ＬＤＰＣ符号のパラメータが決定され、正方行列Ｆ、部分行列Ｐ、パリティ検査行列Ｈがそれぞれ定義されると、パリティ検査行列Ｈに基づく、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法を実行することにより、ＬＤＰＣ符号が復号される（ステップ２０５）。
【００５５】
これを、具体例、特に、Ｓｕｍ−ｐｒｏｄｕｃｔ復号法と呼ばれるアルゴリズムを中心に、以下において説明する。
[ステップ１  初期化]
パリティ検査行列の(ｍ、ｎ)成分が１である、すなわちＨｍｎ＝１である全ての組(ｍ、ｎ)に対して対数事前値比βｍｎ＝０とする。
【００５６】
[ステップ２  行処理]
ｍ＝１、 ２、 …、 Ｍの各行において、Ｈｍｎ＝１である全ての組(ｍ、ｎ)に対して、数１４により、対数外部値比αｍｎを計算する。数１４において、ｓｉｇｎは極性を表す関数であり、数１５で定義される。
【００５７】
【数１４】
2005340920.tif 000016
【００５８】
【数１５】
2005340920.tif 000017
【００５９】
また、関数ｆ(ｘ)はＧａｌｌａｇｅｒ関数と呼ばれ、数１６で定義される。また、尤度情報ｑｎは、記録ＬＤＰＣ符号ｃの第ｎ列成分Ｃｎが0である場合、あるいは1である場合に、再生信号のレベルがpとなる条件付確率の対数比であり、数１７で与えられる。
【００６０】
【数１６】
2005340920.tif 000018
【００６１】
【数１７】
2005340920.tif 000019
【００６２】
さらに、数１４において、数１８は、列位置を表す変数ｎ´を用いて第n列成分を除いた第m行の積あるいは和を求める演算を意味する。
【００６３】
【数１８】
2005340920.tif 000020
【００６４】
[ステップ３  列処理]
n＝１、 ２、 …、 nの各列において、Hmn＝１である全ての組(ｍ、n)に対して、数１９を用いて、対数事前値比βmnを計算する。
【００６５】
【数１９】
2005340920.tif 000021
【００６６】
数１９において、数２０は、行位置を表す変数ｍ´を用いて第m行成分を除いた第n列の和を求める演算を意味する。このようなステップ２の行処理とステップ３の列処理を所定回数繰り返した後、ステップ４に移行する。
【００６７】
【数２０】
2005340920.tif 000022
【００６８】
[ステップ４  符号語の復号]
n＝１、 ２、 …、 Ｎについて、数２１を用いて再生符号ｒの第n列成分rｎを復号し、アルゴリズムを終了する。数２１において、数２２は行位置を表す変数ｍ´を用いて、第n列の和を求める演算を意味する。
【００６９】
【数２１】
2005340920.tif 000023
【００７０】
【数２２】
2005340920.tif 000024
【００７１】
以上のＳｕｍ−ｐｒｏｄｕｃｔ復号法を実行する復号器は、尤度情報ｑｎを記憶するメモリＭｑ、対数外部値比αｍｎを記憶するメモリＭα、対数事前値比βｍｎを記憶するメモリＭβを有し、メモリＭαとメモリＭβは、パリティ検査行列の要素１の数だけメモリアドレス(ｍ、ｎ)を有する。復号器はステップ２の行処理を行なう際、メモリＭβのアドレス(ｍ、ｎ‘)に記憶されている対数事前値比βｍｎ’を読み出して、数１４の演算を行ない、演算の結果得られた対数外部値比αｍｎをメモリMαのアドレス(ｍ、ｎ)に書き込む。
【００７２】
また、復号器はステップ３の列処理を行なう際、メモリＭαのアドレス(ｍ‘、ｎ)に記憶されている対数外部値比αｍ’ｎを読み出して数１９の演算を行ない、演算の結果得られた対数事前値比βｍｎをメモリＭβのアドレス(ｍ、ｎ)に書き込む。
【００７３】
本発明においては、パリティ検査行列における要素１の配置が規則的なので、メモリＭαとメモリＭβの読み出しと書き込みにおけるアドレス制御が容易である。例えば、図２のパリティ検査行列の場合、行列ＰTを構成する６行６列の正方行列の各行に一つずつ要素１が存在するとともに、各列に一つずつ要素１が存在する。このため復号器のメモリＭαとメモリＭβの読み出し回路は、６行６列の正方行列毎に６入力１出力のセレクタとセレクタ制御用のロジック回路を設けることにより簡単に実現できる。
【００７４】
以上の実施例では、数６から数８で生成行列とパリティ検査行列を定義したが、本発明はこれに限定されない。例えば、下記の数２３から数２５で生成行列とパリティ検査行列を定義してもよい。
【００７５】
【数２３】
2005340920.tif 000025
【００７６】
【数２４】
2005340920.tif 000026
【００７７】
【数２５】
2005340920.tif 000027
【００７８】
数２３の行列Pにおいては、正方行列Ｆの列方向の指数が(０、０、０、０)、(１、２、３、４)、(５、４、３、２)となっている。すなわち第１列の指数は全て同一であり、これは公差が０の等差数列とみなすことができる。数２４の生成行列を図５に、数２５のパリティ検査行列を図６に示す。
【００７９】
数２３と数２５とで定義されるパリティ検査行列は、６行６列の単位行列を多く含んでいる。単位行列に関しては、メモリＭαとメモリＭβの読み出し回路におけるセレクタ制御用のロジック回路が不要であり、復号器の回路規模をさらに削減することができる。
【００８０】
また、数６では、正方行列Ｆの指数が列方向に(１、２、３、４)、(５、４、３、２)、(１、３、５、７)と並んでおり、各々公差が１、−１、２の等差数列になっていた。しかし、本発明はこれに限定されず、行列Pにおいて数１１のパターンが発生しなければ、正方行列Ｆの指数は等差数列でなくてもよい。
【００８１】
また、数２６、数２７のように、生成行列とパリティ検査行列において行列Pと単位行列の位置を左右で入れ替えてもよい。
【００８２】
【数２６】
2005340920.tif 000028
【００８３】
【数２７】
2005340920.tif 000029
【００８４】
さらに、行列Pを左右反転したり上下反転したりしてもよく、数１１のパターンが発生しなければ、行列Pの列配置を入れ替えたり行配置を入れ替えたりしてもよい。
【００８５】
以上の実施例では、簡単のため符号語長Ｎが例えばＮ＝４２の場合について述べたが、実際のＬＤＰＣ符号の符号語長は数百から数万と長いのが普通である。この場合でも本発明によれば、正方行列Ｆの行数Ｌ（列数Ｌ）を数十から数千と大きく設定することにより、符号語長Ｎが長いＬＤＰＣ符号の生成行列Ｇとパリティ検査行列Ｈを容易に構成できる。
【００８６】
符号長Ｎが長い場合の具体例として、図７にＬ＝３５、Ｋ＝１１２０、Ｎ＝１２６０のＬＤＰＣ符号の生成例を示す。また、図８にＬ＝９０、Ｋ＝２１６０、Ｎ＝２４３０のＬＤＰＣ符号の生成行列を示す。このように本発明は、ＬＤＰＣ符号の生成行列とパリティ検査行列とを容易に定義することができ、設計の自由度が高いという長所がある。
【００８７】
また、本発明の符号化器および復号器は、ＤＳＰ等を用いたソフトウェア演算でもＬＳＩ等を用いたハードウェア回路でも実現が容易であり、いずれの場合にも、高い復号性能が期待できる。よって、無線通信、有線通信、磁気記録、光記録のいずれも分野にも応用が可能である。
【００８８】
例えば、無線通信の場合、送信装置はＬＤＰＣ符号の符号化を行なってから無線通信路に送信し、受信装置は無線通信路で雑音が重畳された受信信号に対してＬＤＰＣ符号の復号を行ない、雑音によるデータ誤りを訂正することができる。また、例えば磁気記録の場合、記録装置はＬＤＰＣ符号の符号化を行なってから磁気記録媒体に記録し、再生装置は磁気記録媒体で雑音が重畳された再生信号に対してＬＤＰＣ符号の復号を行ない、雑音によるデータ誤りを訂正することができる。
【図面の簡単な説明】
【００８９】
【図１】本実施例の生成行列を示す図である。
【図２】本実施例のパリティ検査行列を示す図である。
【図３】本発明の他の実施例に係るパリティ検査行列を示す図である。
【図４】本発明の他の実施例に係るパリティ検査行列を示す図である。
【図５】本発明の他の実施例に係る生成行列を示す図である。
【図６】本発明の他の実施例に係るパリティ検査行列を示す図である。
【図７】本発明の他の実施例に係る生成行列を示す図である。
【図８】本発明の他の実施例に係る生成行列を示す図である。
【図９】本実施例における符号化処理、復号処理を示すフロー図である。
【図１０】従来例のパリティ検査行列を示す図である。
【図１】
2005340920.tif 000038
【図２】
2005340920.tif 000039
【図３】
2005340920.tif 000040
【図４】
2005340920.tif 000041
【図５】
2005340920.tif 000042
【図６】
2005340920.tif 000043
【図７】
2005340920.tif 000044
【図８】
2005340920.tif 000045
【図９】
2005340920.tif 000046
【図１０】
2005340920.tif 000047