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