(57)【特許請求の範囲】
【請求項１】
情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することにより前記情報系列を符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列にＬＤＰＣ（Low Density Parity Check）符号を用いて符号化する符号器であって、
逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の生成行列に係る情報を取得する情報取得手段と、
前記情報取得手段により取得された情報に基づいて所定の情報系列を符号系列に符号化する符号化手段と、
を備え、
前記第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列である
ことを特徴とする符号器。
【請求項２】
前記第１の行列は、１行目の１列目、ａ＋１列目およびｂ＋１列目（０＜ａ，ｂ＜Ｍかつａ＜ｂ）の要素が１であり、１行目の他の要素が０である列重み３の巡回置換行列であることを特徴とする請求項１に記載の符号器。
【請求項３】
前記第１の行列の逆行列は、列重みが３の行列であることを特徴とする請求項１または２に記載の符号器。
【請求項４】
前記第１の行列は、M=b-a、b-a=M-b、M-b=a、b=M-b、M-a=a又はM-b+a=b-aのいずれかを満足する行列が排除された行列であることを特徴とする請求項２に記載の符号器。
【請求項５】
前記第１の行列の逆行列は、列重みが５の行列であることを特徴とする請求項４に記載の符号器。
【請求項６】
前記符号化手段は、前記情報系列を第２の行列を用いて符号化した後、さらに第１の行列の逆行列を用いて符号化することによりパリティ系列を生成し、生成したパリティ系列を前記情報系列に付加することにより所定の情報系列を符号系列に符号化することを特徴とする請求項１〜５のいずれか１つに記載の符号器。
【請求項７】
情報系列をアレイ符号により符号化する符号器であって、
前記アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列と前記巡回置換行列との積を算出することにより得られる検査行列により定義された生成行列に係る情報を生成する情報生成手段と、
前記情報生成手段により生成された前記生成行列に係る情報を取得する情報取得手段と、
前記情報取得手段により取得された情報に基づいて前記情報系列を符号系列に符号化する符号化手段と
を備えることを特徴とする符号器。
【請求項８】
情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することによりＬＤＰＣ（Low Density Parity Check）符号を用いて符号化された符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列を復号する復号器であって、
逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により前記ＬＤＰＣ符号が定義される場合に、当該検査行列に係る情報を取得する情報取得手段と、
前記情報取得手段により取得された情報に基づいて符号系列を復号する復号手段と、
を備え
前記第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列である
ことを特徴とする復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することにより前記情報系列をＬＤＰＣ（Low Density Parity Check）符号を用いて符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列に符号化する符号器、情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することによりＬＤＰＣ符号を用いて符号化された符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列を復号する復号器、および、情報系列をアレイ符号により符号化する符号器に関し、特に、検査行列を構造化し、誤り特性の劣化を抑制し、符号化に係る計算量を低減させるとともに、回路規模を縮小することができる符号器および当該符号器により符号化された情報系列を復号する復号器に関する。
【背景技術】
【０００２】
近年、次世代の誤り訂正技術としてＬＤＰＣ（Low-Density Parity-Check：低密度パリティ検査）符号が注目されている。ＬＤＰＣ符号とは、検査行列に含まれる「１」の数が少なくなるよう制限された線形符号である。
【０００３】
ＬＤＰＣ符号は、符号長を大きくし、かつランダム性を持たせることで、従来の符号を大きく上回る誤り訂正能力を実現している。また、ＬＤＰＣ符号では、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法と呼ばれる反復復号法を用いて符号系列を効率的に復号することができる。
【０００４】
このＬＤＰＣ符号は、磁気ディスク装置への適用が検討されている。磁気ディスク用のＬＤＰＣ符号に要求される条件として、ウォーターフォール特性が良好であること、エラーフロアが低いこと、パリティ長が短く、高符号化率であること、符号長が短いこと、組織符号であること、符号器および復号器の回路規模が小さいことなどが挙げられる。そして、これらの条件をすべて満足させるＬＤＰＣ符号は未だ存在していない。
【０００５】
ここで、組織符号とは、情報系列からパリティ系列を生成し、そのパリティ系列を情報系列に付加することにより生成される符号である。図６は、組織符号について説明する図である。
【０００６】
図６に示すように、この組織符号は、情報長がＫである情報系列にパリティ長がＭであるパリティ系列を付加することにより符号系列を生成するものであり、符号系列の符号長はＮ（Ｎ＝Ｋ＋Ｍ）となる。
【０００７】
また、図７は、従来のＬＤＰＣ符号方式を用いた磁気ディスク装置の符号／復号部の機能構成を示す図である。図７に示すように、この符号／復号部は、ＬＤＰＣ符号器１、ＰＲ（Partial Response）チャネル２、チャネルＡＰＰ（A Posteriori Probability）復号器３、ＬＤＰＣ復号器４、しきい値判定部５を有する。
【０００８】
ＬＤＰＣ符号器１は、入力された情報系列ｕkをＬＤＰＣ符号系列ｘkに符号化する符号器である。ＰＲチャネル２は、ＬＤＰＣ符号器１により符号化されたＬＤＰＣ符号系列ｘkをパーシャルレスポンス方式により磁気ディスクに記録するとともに、磁気ディスクに記録された情報ｙkを再生して、再生した情報ｙkをチャネルＡＰＰ復号器３に出力するチャネルである。
【０００９】
チャネルＡＰＰ復号器３は、ＰＲチャネル２から受信した情報ｙkに対してＭＬ（Maximum Likelihood）復号をおこなうとともに、ＬＤＰＣ符号系列ｘkに対する外部情報Λe（ｘk’）を対数尤度比でＬＤＰＣ復号器４に出力する復号器である。
【００１０】
ＬＤＰＣ復号器４は、外部情報Λe（ｘk’）を事前尤度として信頼度伝播演算をおこない、ＬＤＰＣ符号系列ｘkに対する外部情報Λe（ｘk’）を更新するとともに、情報系列ｕkに対する推定値ｕk’の事後確率Λ（ｕk’）を外部情報Λe（ｘk’）に基づいて算出する復号器である。
【００１１】
このＬＤＰＣ復号器４は、更新した外部情報Λa（ｘk’）を事前情報として用いるようチャネルＡＰＰ復号器３に出力する。また、ＬＤＰＣ復号器４は、上記処理を所定回数反復した後、事後確率Λ（ｕk’）の情報をしきい値判定部５に出力する。
【００１２】
しきい値判定部５は、ＬＤＰＣ復号器４から事後確率Λ（ｕk’）の情報を取得し、事後確率Λ（ｕk’）のしきい値判定をおこなうことにより、情報系列ｕkに対する推定値ｕk’を得ることができる。
【００１３】
ここで、ＬＤＰＣ符号とは線形ブロック符号であり、検査行列Ｈで定義される。図８は、検査行列Ｈの一例を示す図である。図８に示すように、符号長をＮ、パリティ長をＭとすると、検査行列Ｈは、Ｍ行Ｎ列の行列となる。
【００１４】
このとき、検査行列Ｈは、符号系列ｘと以下のような関係を有する。
ＨｘT＝０
ここで、ｘはＮ次元ベクトルであり、０はＮ次元ゼロベクトルであり、Ｔはｘの転置を表す。
【００１５】
また、符号系列ｘを情報系列ｕから生成する場合には以下のような生成行列Ｇが用いられる。
ｘ＝ｕＧ
ここで、情報系列ｕはＫ次元ベクトルであり、生成行列ＧはＫ行Ｎ列の行列である。
【００１６】
この生成行列Ｇは、情報系列ｕ、符号系列ｘおよび検査行列Ｈと以下のような関係を有する。
ＨＧT＝０
ここで、０はＭ行Ｋ列のゼロ行列である。
【００１７】
この検査行列Ｈと生成行列Ｇとをすべてハードディスク装置が有するＬＳＩ（Large Scale Integration）内のメモリに保持することとすると、ＬＳＩの回路規模が非常に大きくなってしまうという問題がある。そのため、これらの行列の構造をＬＳＩ内に容易に保持できるものとしたり、あるいは、これらの行列を容易に生成できるものとする検討がおこなわれている。
【００１８】
たとえば、検査行列Ｈの構造化手法として、アレイ符号を用いる手法がある。アレイ符号をＬＤＰＣ符号に適用したアレイ−ＬＤＰＣ符号は、巡回置換行列を用いて検査行列Ｈを構造化している（たとえば、非特許文献１を参照）。
【００１９】
以下に、アレイ−ＬＤＰＣ符号の検査行列Ｈの一例を示す。
【数１】
0004558638.tif 000002
ここで、Ｉはｐ行ｐ列（ｐは素数：ｐ＝１，３，５，７，１１，・・・）の単位行列である。ｊおよびｋはそれぞれ検査行列Ｈの列重みおよび行重みであり、ｊ，ｋ≦ｐの関係を満たす。
【００２０】
また、σは単位行列Ｉの「１」を行または列方向に移動したｐ行ｐ列の巡回置換行列である。以下にσの一例を示す。
【数２】
0004558638.tif 000003
【００２１】
アレイ−ＬＤＰＣ符号には、タナーグラフにおける長さが４のサイクルが無く、復号性能の劣化を防止するとともに、検査行列Ｈを構造化できるという特徴があるものの、生成行列Ｇは一般に特定の構造を持たないという欠点がある。
【００２２】
そのため、構造化された検査行列を用いて再帰的に情報系列の符号化をおこなう手法も提案されているが、符号化時の計算量が多くなるという問題がある（たとえば、特許文献１を参照）。
【００２３】
また、符号化時の計算量を抑えるとともに、低いエラーフロアを実現するＩＲＡ（Irregular Repeat-Accumulate）−ＬＤＰＣ符号も提案されている（たとえば、非特許文献２を参照）。
【００２４】
このＩＲＡ−ＬＤＰＣ符号では、Ｍ行Ｎ列の検査行列Ｈを、Ｍ行Ｍ列の正方行列Ｈ2と、残りのＭ行Ｋ列（Ｋ＝Ｎ−Ｍ）の行列Ｈ1とに分ける。
Ｈ＝［Ｈ1 Ｈ2］
【００２５】
この場合、生成行列Ｇは、
Ｇ＝［Ｉ （Ｈ2-1 Ｈ1）T］
となる。
【００２６】
ＩＲＡ−ＬＤＰＣ符号では、検査行列Ｈ1はランダムに生成された行列（ランダムインターリーバ）であり、検査行列Ｈ2は
【数３】
0004558638.tif 000004
のような１＋Ｄ（Ｄは１遅延）の構成を有する。ここで、「＋」は排他的論理和演算子である。
【００２７】
図９は、従来のＩＲＡ−ＬＤＰＣ符号化をおこなう符号器について説明する図である。図９に示すように、この符号器では、情報系列ｕに検査行列Ｈ1Tを掛け、その出力に対して１／（１＋Ｄ）という伝達関数を適用することにより、情報系列ｕからパリティ系列ｐを生成する。
【００２８】
【特許文献１】米国特許第６８９５５４７号明細書
【非特許文献１】John L. Fan, "Array Codes as Low-Density Parity-Check Codes", in Proc. 2nd. Int. Symp. Turbo Codes, Brest, France, Sept. 2000,. pp. 543-546.
【非特許文献２】M. Yang, W. E. Ryan, and Y. Li, "Design of efficiently encodable moderate-length high-rate irregular LDPC codes," IEEE Trans. Comm., Vol. 52, No. 4, pp. 564-571, April 2004.
【発明の開示】
【発明が解決しようとする課題】
【００２９】
しかしながら、上述したＩＲＡ−ＬＤＰＣ符号を用いる従来技術は、パーシャルレスポンス方式を用いた磁気ディスク装置のような符号間干渉を許す装置に適用された場合、検査行列Ｈに「１」が連続する部分があると、誤り率特性が良好にならないという問題があった。
【００３０】
具体的には、ＩＲＡ−ＬＤＰＣ符号における検査行列Ｈ2の列重みは２となっているが、符号間干渉がある場合にはビット間での誤り伝播が発生しやすく、誤り訂正能力の低下を免れないという問題があった。また、列重みが２であるＬＤＰＣ符号はエラーフロア特性が悪いことが一般に知られている。
【００３１】
そのため、検査行列の構造化をしつつも、誤り率特性の劣化を抑制し、符号化・復号化に係る計算量を低減させるとともに、符号回路および復号回路の回路規模を小さくすることのできる技術の開発が重要な課題となっている。
【００３２】
本発明は、上述した従来技術による問題点を解消するためになされたものであり、検査行列を構造化し、誤り特性の劣化を抑制し、符号化に係る計算量を低減させるとともに、回路規模を縮小することができる符号器および符号化方法、また、その符号器により符号化された情報系列を復号する復号器を提供することを目的とする。
【課題を解決するための手段】
【００３３】
上述した課題を解決し、目的を達成するため、本発明は、情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することにより前記情報系列を符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列にＬＤＰＣ（Low Density Parity Check）符号を用いて符号化する符号器であって、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の生成行列に係る情報を取得する情報取得手段と、前記情報取得手段により取得された情報に基づいて所定の情報系列を符号系列に符号化する符号化手段と、を備え、前記第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列であることを特徴とする。
【００３４】
また、本発明は、情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することによりＬＤＰＣ（Low Density Parity Check）符号を用いて符号化された符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列を復号する復号器であって、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の当該検査行列に係る情報を取得する情報取得手段と、前記情報取得手段により取得された情報に基づいて符号系列を復号する復号手段と、を備え、前記第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列であることを特徴とする。
【００３５】
また、本発明は、上記発明において、前記第１の行列は、１行目の１列目、ａ＋１列目およびｂ＋１列目（０＜ａ，ｂ＜Ｍかつａ＜ｂ）の要素が１であり、１行目の他の要素が０である列重み３の巡回置換行列であることを特徴とする。
【００３６】
また、本発明は、上記発明において、前記第１の行列の逆行列は、列重みが３の行列であることを特徴とする。
【００３７】
また、本発明は、上記発明において、前記第１の行列は、M=b-a、b-a=M-b、M-b=a、b=M-b、M-a=a又はM-b+a=b-aのいずれかを満足する行列が排除された行列であることを特徴とする。
【００３８】
また、本発明は、上記発明において、前記長さが４のサイクルが発生する条件は、ａ＝ｂ−ａ、ｂ−ａ＝Ｍ−ｂ、Ｍ−ｂ＝ａ、ｂ＝Ｍ−ｂ、Ｍ−ａ＝ａ、Ｍ−ｂ＋ａ＝ｂ−ａのいずれかの式を満足することであることを特徴とする。
【００３９】
また、本発明は、上記発明において、前記第１の行列が、タナーグラフにおいて長さが４のサイクルが発生する条件を満足しないように構成された行列である場合に、前記第１の行列の逆行列は、列重みが５の行列であることを特徴とする。
【００４０】
また、本発明は、上記発明において、前記符号化手段は、前記情報系列を第２の行列を用いて符号化した後、さらに第１の行列の逆行列を用いて符号化することによりパリティ系列を生成し、生成したパリティ系列を前記情報系列に付加することにより所定の情報系列を符号系列に符号化することを特徴とする。
【００４１】
また、本発明は、上記発明において、前記第２の行列は、アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列により構成されることを特徴とする。
【００４２】
また、本発明は、上記発明において、前記第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列であることを特徴とする。
【００４３】
また、本発明は、情報系列をアレイ符号により符号化する符号器であって、前記アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列と前記巡回置換行列との積を算出することにより得られる検査行列で定義された生成行列に係る情報を生成する情報生成手段と、前記情報生成手段により生成された前記生成行列に係る情報を取得する情報取得手段と、前記情報取得手段により取得された情報に基づいて前記情報系列を符号系列に符号化する符号化手段と、を備えたことを特徴とする。
【００４５】
また、本発明は、情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することにより前記情報系列を符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列にＬＤＰＣ（Low Density Parity Check）符号を用いて符号化する符号化方法であって、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の生成行列に係る情報を取得する情報取得工程と、前記情報取得工程により取得された情報に基づいて所定の情報系列を符号系列に符号化する符号化工程と、を含んだことを特徴とする。
【００４６】
また、本発明は、情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することによりＬＤＰＣ（Low Density Parity Check）符号を用いて符号化された符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列を復号する復号方法であって、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の当該検査行列に係る情報を取得する情報取得工程と、前記情報取得工程により取得された情報に基づいて符号系列を復号する復号工程と、を含んだことを特徴とする。
【発明の効果】
【００４７】
本発明によれば、符号器が、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の生成行列に係る情報を取得し、取得した情報に基づいて所定の情報系列を符号系列に符号化することとしたので、列重みを３とすることにより符号間干渉がある場合でもビット間での誤り伝播を抑制し、また、エラーフロア特性を改善して誤り訂正能力の低下を防止し、さらに、第１の行列を構造化することにより符号化に係る計算量を低減させるとともに、回路規模を縮小することができるという効果を奏する。
【００４８】
また、本発明によれば、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の当該検査行列に係る情報を取得し、取得した情報に基づいて符号系列を復号することとしたので、列重みを３とすることにより符号間干渉がある場合でもビット間での誤り伝播を抑制し、また、エラーフロア特性を改善して誤り訂正能力の低下を防止し、さらに、第１の行列を構造化することにより復号に係る計算量を低減させるとともに、回路規模を縮小することができるという効果を奏する。
【００４９】
また、本発明によれば、第１の行列の逆行列は、列重みが３の行列であることとしたので、逆行列を疎な行列とすることができ、符号化に係る計算量を低減させることができるという効果を奏する。
【００５０】
また、本発明によれば、第１の行列は、１行目の１列目、ａ＋１列目およびｂ＋１列目（０＜ａ，ｂ＜Ｍかつａ＜ｂ）の要素が１であり、１行目の他の要素が０である列重み３の巡回置換行列であることとしたので、１行目の１の要素の位置を記憶しておくだけで第１の行列を生成することができ、第１の行列の要素すべてを記憶しておく必要がないため、回路規模を縮小することができるという効果を奏する。
【００５１】
また、本発明によれば、第１の行列は、タナーグラフにおいて長さが４のサイクルが発生する条件を満足しないように構成された行列であることとしたので、復号性能の劣化を防止することができるという効果を奏する。
【００５２】
また、本発明によれば、長さが４のサイクルが発生する条件は、ａ＝ｂ−ａ、ｂ−ａ＝Ｍ−ｂ、Ｍ−ｂ＝ａ、ｂ＝Ｍ−ｂ、Ｍ−ａ＝ａ、Ｍ−ｂ＋ａ＝ｂ−ａのいずれかの式を満足することであることとしたので、この条件を満足しないように第１の行列を生成することにより復号性能の劣化を効率的に防止することができるという効果を奏する。
【００５３】
また、本発明によれば、第１の行列が、タナーグラフにおいて長さが４のサイクルが発生する条件を満足しないように構成された行列である場合に、第１の行列の逆行列は、列重みが５の行列であることとしたので、逆行列を疎な行列とすることができ、符号化に係る計算量を低減させることができるという効果を奏する。
【００５４】
また、本発明によれば、情報系列を第２の行列を用いて符号化した後、さらに第１の行列の逆行列を用いて符号化することによりパリティ系列を生成し、生成したパリティ系列を情報系列に付加することにより所定の情報系列を符号系列に符号化することとしたので、Ｍ行Ｎ列の検査行列を構成する第１の行列と第２の行列とを用いて効率的に情報系列の符号化をおこなうことができるという効果を奏する。
【００５５】
また、本発明によれば、第２の行列は、アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列により構成されることとしたので、ランダムインターリーバを模倣することができ、符号間干渉がある場合でもビット間での誤り伝播を抑制することにより誤り訂正能力の低下を防止することができるという効果を奏する。
【００５６】
また、本発明によれば、第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列であることとしたので、第２の行列を列重み、行重みが一様でない非正則ＬＤＰＣ符号とすることができるという効果を奏する。
【００５７】
また、本発明によれば、アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列により構成される検査行列により定義された生成行列に係る情報を取得し、取得した情報に基づいて情報系列を符号系列に符号化することとしたので、ランダムインターリーバを模倣することができ、符号間干渉がある場合でもビット間での誤り伝播を抑制することにより誤り訂正能力の低下を防止することができるとともに、行列を構造化することにより符号化に係る計算量を低減させ、回路規模を縮小することができるという効果を奏する。
【００５８】
また、本発明によれば、アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列と巡回置換行列との積を算出することにより生成行列に係る情報を生成し、生成した情報を取得することとしたので、生成行列に係る情報をあらかじめ記憶させる記憶装置を不要とすることができるという効果を奏する。
【発明を実施するための最良の形態】
【００５９】
以下に添付図面を参照して、本発明に係る符号器および復号器の好適な実施例を詳細に説明する。
【実施例１】
【００６０】
まず、本発明の特徴について説明する。本発明に係るＬＤＰＣ符号では、Ｍ行Ｎ列の検査行列Ｈは、Ｍ行Ｍ列の正方行列である検査行列Ｈ2と残りのＭ行Ｋ列（Ｋ＝Ｎ−Ｍ）の検査行列Ｈ1との２つの行列から構成される。
Ｈ＝［Ｈ1 Ｈ2］
【００６１】
この場合、生成行列Ｇは、
Ｇ＝［Ｉ （Ｈ2-1 Ｈ1）T］
と表すことができる。
【００６２】
ここで、
ＨＧT＝［Ｈ1 Ｈ2］［Ｉ （Ｈ2-1 Ｈ1）T］T
＝Ｈ1Ｉ＋Ｈ2（Ｈ2-1 Ｈ1）
＝Ｈ1＋Ｈ1
＝０
となる。なお、「＋」は排他的論理和演算子である。
【００６３】
検査行列Ｈ1には、アレイ符号を用いる。この場合、検査行列Ｈ1は、
【数４】
0004558638.tif 000005
と表される。
【００６４】
ここで、Ｉはｐ行ｐ列（ｐは素数：ｐ＝１，３，５，７，１１，・・・）の単位行列である。ｊおよびｋはそれぞれ検査行列Ｈ1の列重みおよび行重みであり、ｊ，ｋ≦ｐの関係を満たす。
【００６５】
また、σは単位行列Ｉの「１」を行または列方向に移動したｐ行ｐ列の巡回置換行列である。次式
【数５】
0004558638.tif 000006
は、「１」を行方向に移動した場合の例であり、次式
【数６】
0004558638.tif 000007
は、「１」を行方向に移動した場合の例である。
【００６６】
なお、上記検査行列Ｈ1では、左上隅の要素をＩ（＝σ0）としているが、検査行列Ｈ1の左上隅の要素を任意の要素σn（ただし、ｎ≦（ｊ−１）（ｋ−１））に設定し、残りの要素を行または列方向に巡回させた行列を検査行列Ｈ1として用いることとしてもよい。
【００６７】
たとえば、σ（＝σ1）を左上隅の要素とした場合には、残りの要素を
【数７】
0004558638.tif 000008
のように巡回させて、検査行列Ｈ1を生成する。
【００６８】
また、ここでは、ｐは素数であることとしているが、これはｐが素数でない場合には検査行列Ｈ1における巡回置換行列の巡回長が短くなり、それを用いて検査行列Ｈ1を作成すると検査行列Ｈ1が４サイクルを有するようになるためである。
【００６９】
しかし、ｐが素数であって、巡回置換行列の巡回長が検査行列Ｈ1の行列数よりも大きい場合には、４サイクルは発生しない。ここで、この条件は、ｊ，ｋ≦ｐ（ｐは素数）で表される。図１は、４サイクルの発生原因について説明する図である。
【００７０】
図１に示すように、ｐが素数５である場合には、行列Ｈ1に４サイクルが発生していないのに対し、ｐが非素数６である場合には、巡回置換行列の巡回長が短くなり、巡回行列Ｉによる４サイクルが生じていることがわかる。
【００７１】
このような、列重みｊ、行重みｋとなる（ｊ×ｐ）行（ｋ×ｐ）列の検査行列Ｈ1により定義されるアレイ符号は、正則ＬＤＰＣ符号であり、行列数に制約がある。そこで、上記検査行列Ｈ1の一部を切り出して用いることにより、行列数の制約を取り除き、列重み、行重みが一様でない非正則ＬＤＰＣ符号を生成する。
【００７２】
図２は、検査行列Ｈ1の生成方法を説明する図である。図２には、ｐ＝７、ｊ＝３、ｋ＝４であり、１６行２４列の検査行列Ｈ1を生成する例が示されている。検査行列Ｈ1を生成する場合には、まず、７行７列の巡回置換行列を用いて２１行２８列のアレイ符号の検査行列Ｈarrayを生成する。そして、検査行列Ｈarrayから１６行２４列の行列を切り出して検査行列Ｈ1とする。
【００７３】
一方、検査行列Ｈ2は列重み３の巡回置換行列とする。ただし、「１」のビット位置は、４サイクルがなく、かつ、逆行列が疎となるように決定される。疎な行列とは、「１」の数が非常に少なく、「０」の数が多い行列のことである。ここでは、列重みが５となる逆行列を疎な逆行列として選択する。
【００７４】
以下に示す検査行列Ｈ2は、パリティ長を１６、初期値列を｛０，２，６｝とした場合の例である。
【数８】
0004558638.tif 000009
【００７５】
初期値列｛０，a，ｂ｝（ただし、０＜ａ，ｂ＜Ｍかつａ＜ｂ）とは、列重みが３の巡回置換行列の１行目において、３つの「１」のビットが位置する列を特定する情報である。具体的には、初期値列｛０，a，ｂ｝とは、検査行列Ｈ2の１行目の１列目、ａ＋１列目およびｂ＋１列目の要素が「１」であり、他の要素が「０」であることを示している。
【００７６】
検査行列Ｈ2は、巡回置換行列であるため、初期値列が決定されると初期値列に基づいて検査行列Ｈ2の要素すべてを決定することができる。そのため、符号器は検査行列Ｈ2のすべての要素の値を保持する必要が無く、初期値列の情報を保持するだけでよいので、回路規模の縮小を実現することができる。
【００７７】
また、上記検査行列Ｈ2の逆行列Ｈ2-1は、以下のようになる。
【数９】
0004558638.tif 000010
【００７８】
このように、検査行列Ｈ2を初期値列｛０，２，６｝の行列とした場合には、逆行列Ｈ2-1の列重みは５となり、検査行列Ｈ2と同様に逆行列Ｈ2-1も巡回置換行列となる。そのため、符号器は逆行列Ｈ2-1を生成するために初期値列の情報を保持するだけでよいので、回路規模の縮小および演算の高速化を実現することができる。
【００７９】
なお、４サイクルがなく、逆行列が存在し、その逆行列の列重みが５となる列重みが３の巡回置換行列Ｈ2の初期値列はパリティ長によって異なるものとなる。上記条件を満足するパリティ長と初期値列との間の関係は、コンピュータによる探索で容易に調べることができる。
【００８０】
また、４サイクルを許容する場合には、逆行列の列重みを５未満にすることができる。具体的には、逆行列の列重みを３にまで減らすことができる。このように逆行列の列重みが３となる巡回置換行列Ｈ2をコンピュータによる探索で調べて用いることにより、逆行列を疎とすることができ、符号化に係る計算量を低減させるとともに、回路規模を縮小することができる。
【００８１】
以下に、コンピュータによりなされた初期値列の探索結果について示すこととする。図３−１、図３−２、図３−３および図３−４は、各パリティ長Ｍに対応する初期値列｛０，ａ，ｂ｝を示す図（１）、（２）、（３）および（４）である。なお、図３−１、図３−２、図３−３および図３−４においては、初期値列｛０，a，ｂ｝の数字を区切るカンマ「，」は省略されている。
【００８２】
ここで、パリティ長Ｍ、初期値列｛０，ａ，ｂ｝である列重み３の巡回置換行列Ｈ2が、４サイクルとなるのは、
（１）ａ＝ｂ−ａ，
（２）ｂ−ａ＝Ｍ−ｂ，
（３）Ｍ−ｂ＝ａ，
（４）ｂ＝Ｍ−ｂ，
（５）Ｍ−ａ＝ａ，
（６）Ｍ−ｂ＋ａ＝ｂ−ａ，
のいずれかの条件を満足する場合である。そのため、初期値列の探索時には、そのような条件を満足する初期値列は排除される。
【００８３】
つぎに、ＬＤＰＣ符号を生成する符号器の機能構成について説明する。図４は、ＬＤＰＣ符号を生成する符号器の機能構成を示す図である。この符号器は、図７に示したＬＤＰＣ符号器１に対応するものである。図４に示すように、この符号器は、情報系列受信部１０、記憶部１１、行列生成部１２、第１行列演算部１３、第２行列演算部１４、符号生成部１５を有する。
【００８４】
情報系列受信部１０は、情報系列を受信して、受信した情報系列を第１行列演算部１３と符号生成部１５とにそれぞれ出力する。記憶部１１は、メモリなどの記憶デバイスであり、検査行列Ｈ1の生成に用いられる巡回置換行列σの「１」の位置に係る情報や、検査行列Ｈ2の逆行列Ｈ2-1の初期値列の情報、検査行列Ｈ1および逆行列Ｈ2-1の行列数の情報などを記憶する。
【００８５】
行列生成部１２は、記憶部１１から巡回置換行列σにおける「１」の位置に係る情報や検査行列Ｈ1の行列数の情報を取得して、検査行列Ｈ1を図２で説明したような方法にしたがって生成し、生成した検査行列Ｈ1の転置行列Ｈ1Tを第１行列演算部１３に出力する。
【００８６】
また、行列生成部１２は、記憶部１１から逆行列Ｈ2-1の初期値列の情報や逆行列Ｈ2-1の行列数の情報を取得して、検査行列Ｈ2の逆行列Ｈ2-1を初期値列から生成し、生成した逆行列Ｈ2-1の転置行列（Ｈ2-1）Tを第２行列演算部１４に出力する。
【００８７】
第１行列演算部１３は、情報系列受信部１０から取得した情報系列と、行列生成部１２から取得した転置行列Ｈ1Tとの間の積を算出し、その積の情報を第２行列演算部１４に出力する。
【００８８】
第２行列演算部１４は、第１行列演算部１３から積の情報を取得し、取得した積と、行列生成部１２から取得した転置行列（Ｈ2-1）Tとの間の積を算出する。この積がパリティ系列となる。そして、第２行列演算部１４は、パリティ系列を符号生成部１５に出力する。
【００８９】
符号生成部１５は、情報系列受信部１０から取得した情報系列に、第２行列演算部１４から取得したパリティ系列を付加することにより符号系列を生成し、生成した符号系列を出力する。
【００９０】
つぎに、ＬＤＰＣ符号を復号する復号器の機能構成について説明する。図５は、ＬＤＰＣ符号を復号する復号器の機能構成を示す図である。この復号器は、図７に示したＬＤＰＣ復号器４に対応するものである。図５に示すように、この復号器は、外部情報受信部２０、記憶部２１、行列生成部２２、復号処理部２３を有する。
【００９１】
外部情報受信部２０は、図７に示したチャネルＡＰＰ復号器３から外部情報を受信する。記憶部２１は、メモリなどの記憶デバイスであり、検査行列Ｈ1の生成に用いられる巡回置換行列σの「１」の位置に係る情報や、検査行列Ｈ2の初期値列の情報、検査行列Ｈ1および検査行列Ｈ2の行列数の情報などを記憶する。
【００９２】
行列生成部２２は、記憶部２１から読み出した巡回置換行列σの「１」の位置に係る情報や検査行列Ｈ2の初期値列の情報、検査行列Ｈ1および検査行列Ｈ2の行列数の情報を基にして検査行列Ｈを生成し、生成した検査行列Ｈを復号処理部２３に出力する。
【００９３】
復号処理部２３は、一般に用いられるＳｕｍ−Ｐｒｏｄｕｃｔ復号法によりＬＤＰＣ符号を復号する。具体的には、復号処理部２３は、行列生成部２２から取得した検査行列Ｈを用い、外部情報受信部２０から取得した外部情報を事前尤度として信頼度伝播演算をおこない、ＬＤＰＣ符号系列ｘkに対する外部情報を更新する。
【００９４】
また、復号処理部２３は、情報系列に対する推定値の事後確率を外部情報に基づいて算出する。さらに、復号処理部２３は、更新した外部情報を事前確率情報として用いるようチャネルＡＰＰ復号器３に出力する。
【００９５】
また、復号処理部２３は、上記処理を所定回数反復した後、事後確率の情報を図７に示したしきい値判定部５に出力する。この情報を取得したしきい値判定部５では、事後確率のしきい値判定をおこなうことにより、情報系列に対する推定値を得ることができ、ＬＤＰＣ符号の復号がなされる。
【００９６】
上述してきたように、実施例１では、符号器の第１行列演算部１３および第２行列演算部１４が、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の検査行列Ｈ2と、Ｍ行Ｋ列の検査行列Ｈ1とにより構成されるＭ行Ｎ列の検査行列Ｈにより定義されたＬＤＰＣ符号の生成行列に係る情報を取得し、取得した情報に基づいて所定の情報系列を符号系列に符号化することとしたので、列重みを３とすることにより符号間干渉がある場合でもビット間での誤り伝播を抑制し、また、エラーフロア特性を改善して誤り訂正能力の低下を防止し、さらに、第１の行列を構造化することにより符号化に係る計算量を低減させるとともに、回路規模を縮小することができる。
【００９７】
また、実施例１では、復号器の復号処理部２３が、逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の検査行列Ｈ2とＭ行Ｋ列の検査行列Ｈ1とにより構成されるＭ行Ｎ列の検査行列Ｈにより定義されたＬＤＰＣ符号の当該検査行列Ｈに係る情報を取得し、取得した情報に基づいて符号系列を復号することとしたので、列重みを３とすることにより符号間干渉がある場合でもビット間での誤り伝播を抑制し、また、エラーフロア特性を改善して誤り訂正能力の低下を防止し、さらに、第１の行列を構造化することにより復号に係る計算量を低減させるとともに、回路規模を縮小することができる。
【００９８】
また、実施例１では、検査行列Ｈ2の逆行列は、タナーグラフにおいて長さが４のサイクルが発生するのを許容する場合に、列重みが３の行列であることとしたので、逆行列を疎な行列とすることができ、符号化に係る計算量を低減させることができる。
【００９９】
また、実施例１では、検査行列Ｈ2は、１行目の１列目、ａ＋１列目およびｂ＋１列目（０＜ａ，ｂ＜Ｍかつａ＜ｂ）の要素が１であり、１行目の他の要素が０である列重み３の巡回置換行列であることとしたので、１行目の１の要素の位置を記憶しておくだけで第１の行列を生成することができ、第１の行列の要素すべてを記憶しておく必要がないため、回路規模を縮小することができる。
【０１００】
また、実施例１では、検査行列Ｈ2は、タナーグラフにおいて長さが４のサイクルが発生する条件を満足しないように構成された行列であることとしたので、復号性能の劣化を防止することができる。
【０１０１】
また、実施例１では、長さが４のサイクルが発生する条件は、ａ＝ｂ−ａ、ｂ−ａ＝Ｍ−ｂ、Ｍ−ｂ＝ａ、ｂ＝Ｍ−ｂ、Ｍ−ａ＝ａ、Ｍ−ｂ＋ａ＝ｂ−ａのいずれかの式を満足することであることとしたので、この条件を満足しないように第１の行列を生成することにより復号性能の劣化を効率的に防止することができる。
【０１０２】
また、実施例１では、検査行列Ｈ2が、タナーグラフにおいて長さが４のサイクルが発生する条件を満足しないように構成された行列である場合に、検査行列Ｈ2の逆行列は、列重みが５の行列であることとしたので、逆行列を疎な行列とすることができ、符号化に係る計算量を低減させることができる。
【０１０３】
また、実施例１では、第１行列演算部１３が、情報系列を検査行列Ｈ1を用いて符号化した後、第２行列演算部１４が、さらに検査行列Ｈ2の逆行列を用いて符号化することによりパリティ系列を生成し、符号生成部１５が、生成したパリティ系列を情報系列に付加することにより所定の情報系列を符号系列に符号化することとしたので、Ｍ行Ｎ列の検査行列を構成する検査行列Ｈ2と検査行列Ｈ1とを用いて効率的に情報系列の符号化をおこなうことができる。
【０１０４】
また、実施例１では、検査行列Ｈ1は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列ＨarrayからＭ行Ｋ列の行列を切り出すことにより生成される行列であることとしたので、検査行列Ｈ1を列重み、行重みが一様でない非正則ＬＤＰＣ符号とすることができる。
【実施例２】
【０１０５】
ところで、実施例１では検査行列Ｈを構造化することとしているが、単純に構造化をおこなうだけであると検査行列のランダム性が低下し、誤り訂正能力を向上させることが難しくなる場合がある。
【０１０６】
検査行列のランダム性を高める技術としては、ランダムインターリーバがあるが、符号系列を記憶するメモリを複数用意する必要があり、回路規模が大きくなってしまう。そのため、本実施例２では、回路規模が大きくなることなく、検査行列のランダム性を高める場合について説明する。なお、符号器および復号器の機能構成は、図４および図５に示したものと同様であり、以下では、実施例１と異なる部分について詳細に説明することとする。
【０１０７】
まず、実施例２に係る検査行列Ｈについて説明する。ここでも、実施例１と同様、Ｍ行Ｎ列の検査行列Ｈを、Ｍ行Ｍ列の正方行列である検査行列Ｈ2と、残りのＭ行Ｋ列（Ｋ＝Ｎ−Ｍ）の検査行列Ｈ1とに分ける。
Ｈ＝［Ｈ1 Ｈ2］
【０１０８】
ここで、検査行列Ｈ2は、実施例１における検査行列Ｈ2と同様の行列を用いる。検査行列Ｈ1は、アレイ符号における検査行列Ｈarrayの各列ブロックと、後に説明する巡回置換行列ωにより構成されるωm（０≦ｍ≦ｋ−１）との積により、以下のようにして構成される。
【数１０】
0004558638.tif 000011
【０１０９】
ここで、Ｉはｐ行ｐ列（ｐは素数：ｐ＝１，３，５，７，１１，・・・）の単位行列である。ｊおよびｋはそれぞれ検査行列Ｈ1の列重みおよび行重みであり、ｊ，ｋ≦ｐの関係を満たす。
【０１１０】
また、σは、以下に例を示すように、アレイ符号を構成する実施例１と同様のｐ行ｐ列の巡回置換行列である。
【数１１】
0004558638.tif 000012
【０１１１】
また、巡回置換行列ωは、ｐ行ｐ列の行列であり、巡回置換行列σにおいて隣接する行の２つの「１」を所定の列だけ間をあけて行あるいは列置換配置した行列である。たとえば、隣接する行の２つの「１」を１列だけ間をあけて行あるいは列置換配置した巡回置換行列ωは、
【数１２】
0004558638.tif 000013
となる。
【０１１２】
実施例１の巡回置換行列σでは、「１」が対角線上に並んでしまうが、このような擬似ランダムな巡回置換行列ωを用いることにより対角線上に並ぶ「１」を分散し、ランダムインターリーバを模倣することができるので、磁気ディスク装置における符号のように符号間干渉がある場合において誤り訂正能力の向上に有効となる。また、ここでも、図２で説明したように、検査行列Ｈ1の任意の部分を切り出して検査行列Ｈ1として用いることができる。
【０１１３】
図４および図５に示した符号器および復号器は、このようにして構成された検査行列Ｈに対応する生成行列Ｇ、および、検査行列Ｈを用いて、情報系列の符号化、および、符号系列の復号をおこなう。
【０１１４】
上述してきたように、本実施例２では、符号器の第１行列演算部１３および第２行列演算部１４が、アレイ符号の検査行列Ｈarrayを構成する巡回置換行列σにおける隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列ωにより構成される検査行列Ｈにより定義された生成行列に係る情報を取得し、取得した情報に基づいて情報系列を符号系列に符号化することとしたので、ランダムインターリーバを模倣することができ、符号間干渉がある場合でもビット間での誤り伝播を抑制することにより誤り訂正能力の低下を防止することができるとともに、行列を構造化することにより符号化に係る計算量を低減させ、回路規模を縮小することができる。
【０１１５】
また、本実施例２では、符号器の行列生成部１２は、アレイ符号の検査行列Ｈarrayを構成する巡回置換行列σにおける隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列ωと巡回置換行列σとの積を算出することにより生成行列に係る情報を生成し、第１行列演算部１３および第２行列演算部１４が、生成された情報を取得することとしたので、生成行列に係る情報をあらかじめ記憶させる記憶装置を不要とすることができる。
【０１１６】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施例にて実施されてもよいものである。たとえば、本発明は磁気ディスク装置用の誤り訂正に適用されるだけでなく、光ディスク記憶装置や通信用の誤り訂正に適用することとしてもよい。
【０１１７】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。
【０１１８】
この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１１９】
また、図示した符号器および復号器の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、符号器および復号器の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１２０】
さらに、符号器および復号器にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１２１】
（付記１）情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することにより前記情報系列を符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列にＬＤＰＣ（Low Density Parity Check）符号を用いて符号化する符号器であって、
逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の生成行列に係る情報を取得する情報取得手段と、
前記情報取得手段により取得された情報に基づいて所定の情報系列を符号系列に符号化する符号化手段と、
を備えたことを特徴とする符号器。
【０１２２】
（付記２）前記第１の行列は、１行目の１列目、ａ＋１列目およびｂ＋１列目（０＜ａ，ｂ＜Ｍかつａ＜ｂ）の要素が１であり、１行目の他の要素が０である列重み３の巡回置換行列であることを特徴とする付記１に記載の符号器。
【０１２３】
（付記３）前記第１の行列の逆行列は、列重みが３の行列であることを特徴とする付記１または２に記載の符号器。
【０１２４】
（付記４）前記第１の行列は、タナーグラフにおいて長さが４のサイクルが発生する条件を満足しないように構成された行列であることを特徴とする付記１または２に記載の符号器。
【０１２５】
（付記５）前記長さが４のサイクルが発生する条件は、ａ＝ｂ−ａ、ｂ−ａ＝Ｍ−ｂ、Ｍ−ｂ＝ａ、ｂ＝Ｍ−ｂ、Ｍ−ａ＝ａ、Ｍ−ｂ＋ａ＝ｂ−ａのいずれかの式を満足することであることを特徴とする付記４に記載の符号器。
【０１２６】
（付記６）前記第１の行列の逆行列は、列重みが５の行列であることを特徴とする付記４または５に記載の符号器。
【０１２７】
（付記７）前記符号化手段は、前記情報系列を第２の行列を用いて符号化した後、さらに第１の行列の逆行列を用いて符号化することによりパリティ系列を生成し、生成したパリティ系列を前記情報系列に付加することにより所定の情報系列をＬＤＰＣ符号に符号化することを特徴とする付記１〜６のいずれか１つに記載の符号器。
【０１２８】
（付記８）前記第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列であることを特徴とする付記１〜７のいずれか１つに記載の符号器。
【０１２９】
（付記９）情報系列をアレイ符号により符号化する符号器であって、
前記アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列により構成される検査行列により定義された生成行列に係る情報を取得する情報取得手段と、
前記情報取得手段により取得された情報に基づいて前記情報系列を符号系列に符号化する符号化手段と、
を備えたことを特徴とする符号器。
【０１３０】
（付記１０）前記アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列と前記巡回置換行列との積を算出することにより前記生成行列に係る情報を生成する情報生成手段をさらに備え、前記情報取得手段は、前記情報生成手段により生成された情報を取得することを特徴とする付記９に記載の符号器。
【０１３１】
（付記１１）情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することによりＬＤＰＣ（Low Density Parity Check）符号を用いて符号化された符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列を復号する復号器であって、
逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の当該検査行列に係る情報を取得する情報取得手段と、
前記情報取得手段により取得された情報に基づいて符号系列を復号する復号手段と、
を備えたことを特徴とする復号器。
【０１３２】
（付記１２）前記第１の行列は、１行目の１列目、ａ＋１列目およびｂ＋１列目（０＜ａ，ｂ＜Ｍかつａ＜ｂ）の要素が１であり、１行目の他の要素が０である列重み３の巡回置換行列であることを特徴とする付記１１に記載の復号器。
【０１３３】
（付記１３）前記第１の行列の逆行列は、列重みが３の行列であることを特徴とする付記１１または１２に記載の復号器。
【０１３４】
（付記１４）前記第１の行列は、タナーグラフにおいて長さが４のサイクルが発生する条件を満足しないように構成された行列であることを特徴とする付記１１または１２に記載の復号器。
【０１３５】
（付記１５）前記長さが４のサイクルが発生する条件は、ａ＝ｂ−ａ、ｂ−ａ＝Ｍ−ｂ、Ｍ−ｂ＝ａ、ｂ＝Ｍ−ｂ、Ｍ−ａ＝ａ、Ｍ−ｂ＋ａ＝ｂ−ａのいずれかの式を満足することであることを特徴とする付記１４に記載の復号器。
【０１３６】
（付記１６）前記第１の行列の逆行列は、列重みが５の行列であることを特徴とする付記１４または１５に記載の復号器。
【０１３７】
（付記１７）前記第２の行列は、アレイ符号の検査行列を構成する巡回置換行列における隣接する行の２つの１を所定の列だけ間をあけて行あるいは列置換配置した行列により構成されることを特徴とする付記１１〜１６のいずれか１つに記載の復号器。
【０１３８】
（付記１８）前記第２の行列は、アレイ符号のＰ行Ｑ列（Ｍ＜ＰかつＫ＜Ｑ）の検査行列からＭ行Ｋ列の行列を切り出すことにより生成される行列であることを特徴とする付記１１〜１７のいずれか１つに記載の復号器。
【０１３９】
（付記１９）情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することにより前記情報系列を符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列にＬＤＰＣ（Low Density Parity Check）符号を用いて符号化する符号化方法であって、
逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の生成行列に係る情報を取得する情報取得工程と、
前記情報取得工程により取得された情報に基づいて所定の情報系列を符号系列に符号化する符号化工程と、
を含んだことを特徴とする符号化方法。
【０１４０】
（付記２０）情報長がＫである所定の情報系列にパリティ長がＭであるパリティ系列を付加することによりＬＤＰＣ（Low Density Parity Check）符号を用いて符号化された符号長がＮ（Ｎ＝Ｋ＋Ｍ）である符号系列を復号する復号方法であって、
逆行列が存在し、列重みが３の巡回置換行列であるＭ行Ｍ列の第１の行列とＭ行Ｋ列の第２の行列とにより構成されるＭ行Ｎ列の検査行列により定義されたＬＤＰＣ符号の当該検査行列に係る情報を取得する情報取得工程と、
前記情報取得工程により取得された情報に基づいて符号系列を復号する復号工程と、
を含んだことを特徴とする復号方法。
【産業上の利用可能性】
【０１４１】
以上のように、本発明に係る符号器および復号器は、検査行列を構造化し、誤り特性の劣化を抑制し、符号化に係る計算量を低減させるとともに、回路規模を縮小することが必要な符号化システム、また、その符号化システムにより符号化された情報系列を復号する復号システムに対して有用である。
【図面の簡単な説明】
【０１４２】
【図１】４サイクルの発生原因について説明する図である。
【図２】検査行列Ｈ1の生成方法を説明する図である。
【図３−１】各パリティ長に対応する初期値列を示す図（１）である。
【図３−２】各パリティ長に対応する初期値列を示す図（２）である。
【図３−３】各パリティ長に対応する初期値列を示す図（３）である。
【図３−４】各パリティ長に対応する初期値列を示す図（４）である。
【図４】ＬＤＰＣ符号を生成する符号器の機能構成を示す図である。
【図５】ＬＤＰＣ符号を復号する復号器の機能構成を示す図である。
【図６】組織符号について説明する図である。
【図７】従来のＬＤＰＣ符号方式を用いた磁気ディスク装置の符号／復号部の機能構成を示す図である。
【図８】検査行列Ｈの一例を示す図である。
【図９】従来のＩＲＡ−ＬＤＰＣ符号化をおこなう符号器について説明する図である。
【符号の説明】
【０１４３】
１０    情報系列受信部
１１    記憶部
１２    行列生成部
１３    第１行列演算部
１４    第２行列演算部
１５    符号生成部
２０    外部情報受信部
２１    記憶部
２２    行列生成部
２３    復号処理部
【図１】
0004558638.tif 000014
【図２】
0004558638.tif 000015
【図３−１】
0004558638.tif 000016
【図３−２】
0004558638.tif 000017
【図３−３】
0004558638.tif 000018
【図３−４】
0004558638.tif 000019
【図４】
0004558638.tif 000020
【図５】
0004558638.tif 000021
【図６】
0004558638.tif 000022
【図７】
0004558638.tif 000023
【図８】
0004558638.tif 000024
【図９】
0004558638.tif 000025