(57)【要約】【課題】パリティ演算に関わる回路の規模を小さくし、演算量を低減させる。【解決手段】パリティ演算部３１には、排他的論理和演算回路が含まれる。パリティ検査行列を、単位行列を含む行列に基本変形し、その変形後の行列のうち、単位行列以外の行列に含まれる非零要素の数に関する表を作成する。その表には、パリティを割り当てる位置に依存した行列毎にデータが書き込まれている。例えば、所定の行に含まれる非零要素の数は、排他的論理和演算回路に入力されるデータ数に関係しているため、作成された表から、所定の行に含まれる非零要素の数が少ない行列を適用したパリティ演算回路が設計される。本発明は、所定の記録媒体にデータを符号化して記録する記録装置に適用できる。【選択図】図１０
2008259051.tif 000002
【特許請求の範囲】
【請求項１】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化方法において、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列に含まれる非零の要素数が最小となるように（n-k）箇所をパリティに割り当てる
符号化方法。
【請求項２】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を行う符号化装置において、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列に含まれる非零の要素数が最小となるように（n-k）箇所をパリティに割り当てる
符号化装置。
【請求項３】
前記割り当てられるパリティをｋ段シフトレジスタで求める
請求項２に記載の符号化装置。
【請求項４】
前記割り当てられるパリティをｋ0個のｍ段シフトレジスタで求める
請求項２に記載の符号化装置。
【請求項５】
前記割り当てられるパリティを（ｎ0―ｋ0）個のｍ段シフトレジスタで求める
請求項２に記載の符号化装置。
【請求項６】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を制御するコンピュータが読み取り可能なプログラムであって、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列に含まれる非零の要素数が最小となるように（n-k）箇所をパリティに割り当てる
プログラム。
【請求項７】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化方法において、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列の各行に含まれる非零の要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる
符号化方法。
【請求項８】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を行う符号化装置において、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列の各行に含まれる非零の要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる
符号化装置。
【請求項９】
前記割り当てられるパリティをｋ段シフトレジスタで求める
請求項８に記載の符号化装置。
【請求項１０】
前記割り当てられるパリティをｋ0個のｍ段シフトレジスタで求める
請求項８に記載の符号化装置。
【請求項１１】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を制御するコンピュータが読み取り可能なプログラムであって、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列の各行に含まれる非零の要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる
プログラム。
【請求項１２】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化方法において、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列の各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる
符号化方法。
【請求項１３】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を行う符号化装置において、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列の各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる
符号化装置。
【請求項１４】
前記割り当てられるパリティを（ｎ0−ｋ0）個のｍ段シフトレジスタで求める
請求項１３に記載の符号化装置。
【請求項１５】
符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を制御するコンピュータが読み取り可能なプログラムであって、
情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、
前記第２の行列の各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は符号化方法および符号化装置、並びにプログラムに関し、特に、符号化に関わる回路の規模を小さくし、かつ演算量を少なくするようにした符号化方法および符号化装置、並びにプログラムに関する。
【背景技術】
【０００２】
近年、例えば、移動体通信などの通信分野、及び地上波又は衛星デジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、LDPC符号という）が脚光を浴びつつある。
【０００４】
LDPC符号は、R. G. Gallagerによる「R. G. Gallager, "Low Density Parity Check Codes", Cambridge, Massachusetts: M. I. T. Press, 1963」において最初に提案されたものであり、その後、「D. J. C. MacKay, "Good error correcting codes based on very sparse matrices", Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999」や、「M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくに従って、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【０００６】
【非特許文献１】Y. Kou, S. Lin, M. P. C. Fossorier, “Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 2711-2736, Nov. 2001.
【非特許文献２】R. L. Townsend, E. J. Weldon, “Self-Orthogonal Quasi-Cyclic Codes,” IEEE Transactions on Information Theory, vol. IT-13, no. 2, Apr. 1967.
【特許文献１】Dieter Roth et al, “SYSTEM FOR BINARY DATA TRANSMISSION,” US Patent, No. 4,453,249, Jun. 1984.
【特許文献２】Shin et al, “METHOD OF CONSTRUCTING QC-LDPC CODES USING QTH-ORDER POWER RESIDUE,” US Patent Application Publication, Pub. No. US2005/0149845 A1, Jul. 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
線形符号は生成行列が与えられれば、情報語から符号語への変換が一意に求められる。LDPC符号の誤り復号性能は、パリティ検査行列の構造により決定付けられるが、パリティ検査行列が与えられただけでは、情報語から符号語への変換には自由度がある。準巡回符号をLDPC符号として用いる場合において、n0ビット単位でみた特定の位置のビットをパリティとする組織符号の符号化を行うとき、k段シフトレジスタによる符号化が行えるため、行列の演算に比べると回路は簡略化される。しかしながら、n0ビット単位でみた、どの特定の位置のビットをパリティとするかという自由度に対しては、さらに検討がなされる必要性がある。
【０００８】
本発明は、このような状況に鑑みてなされたものであり、符号化に関わる回路の規模を小さくすることができるようにするものである。
【課題を解決するための手段】
【０００９】
本発明の一側面の第１の符号化方法は、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化方法において、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列に含まれる非零の要素数が最小となるように（n-k）箇所をパリティに割り当てる。
【００１０】
本発明の一側面の第１の符号化装置は、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を行う符号化装置において、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列に含まれる非零の要素数が最小となるように（n-k）箇所をパリティに割り当てる。
【００１１】
前記割り当てられるパリティをｋ段シフトレジスタで求めるようにすることができる。
【００１２】
前記割り当てられるパリティをｋ0個のｍ段シフトレジスタで求めるようにすることができる。
【００１３】
前記割り当てられるパリティを（ｎ0―ｋ0）個のｍ段シフトレジスタで求めるようにすることができる。
【００１４】
本発明の一側面の第１のプログラムは、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を制御するコンピュータが読み取り可能なプログラムであって、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列に含まれる非零の要素数が最小となるように（n-k）箇所をパリティに割り当てる。
【００１５】
本発明の一側面の第１の符号化方法および装置、並びにプログラムにおいては、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化が行われ、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述され、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形が施され、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、第２の行列に含まれる非零の要素数が最小となるように（n-k）箇所がパリティに割り当てられる。
【００１６】
本発明の一側面の第２の符号化方法は、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化方法において、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列の各行に含まれる非零の要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる。
【００１７】
本発明の一側面の第２の符号化装置は、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を行う符号化装置において、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列の各行に含まれる非零の要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる。
【００１８】
前記割り当てられるパリティをｋ段シフトレジスタで求めるようにすることができる。
【００１９】
前記割り当てられるパリティをｋ0個のｍ段シフトレジスタで求めるようにすることができる。
【００２０】
本発明の一側面の第２のプログラムは、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を制御するコンピュータが読み取り可能なプログラムであって、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列の各行に含まれる非零の要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる。
【００２１】
本発明の一側面の第２の符号化方法および装置、並びにプログラムにおいては、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化が行われ、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化される場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述され、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形が施され、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、第２の行列の各行に含まれる非零の要素数の最大値が最小となるように（n-k）箇所がパリティに割り当てられる。
【００２２】
本発明の一側面の第３の符号化方法は、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化方法において、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列の各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる。
【００２３】
本発明の一側面の第３の符号化装置は、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を行う符号化装置において、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列の各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる。
【００２４】
前記割り当てられるパリティを（ｎ0-ｋ0）個のｍ段シフトレジスタで求めるようにすることができる。
【００２５】
本発明の一側面の第３のプログラムは、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化を制御するコンピュータが読み取り可能なプログラムであって、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形を施し、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、前記第２の行列の各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（n-k）箇所をパリティに割り当てる。
【００２６】
本発明の一側面の第３の符号化方法および装置、並びにプログラムにおいては、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号を用いる符号化が行われ、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化される場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述され、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするように行の基本変形が施され、その基本変形を施した第１の行列から単位行列を除いた残りを第２の行列とするとき、第２の行列の各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（n-k）箇所がパリティに割り当てられる。
【発明の効果】
【００２７】
本発明の一側面によれば、パリティ演算回路における演算量を低減させることができる。
【００２８】
本発明の一側面によれば、パリティ演算回路の回路規模を縮小させることができる。
【発明を実施するための最良の形態】
【００２９】
以下に、本発明の実施の形態について図面を参照して説明する。図１は、本発明を適用した記録再生システム一実施の形態の構成を示す図である。チャネル符号化部１１は、入力されたデータを、チャネルの周波数特性や再生時の等化方式、タイミング検出などに適した制約の符号に変換する。チャネル符号は、例えば、ランレングス制約 (run-length-limited) 符号などである。
【００３０】
誤り訂正符号化部１２は、チャネルにおける雑音や歪みなどの影響により起こる誤りを再生時に訂正するために冗長度を持たせ、チャネル符号化された情報語dを符号語cに変換する。誤り訂正符号化部１２は、例えば、リード・ソロモン (Reed-Solomon) 符号やLDPC (low-density parity-check) 符号などの符号化方式に基づいて符号化を行う。
【００３１】
記録再生チャネル部１３は、例えば、記録ヘッド、磁気メディア、再生ヘッド、あるいは光ピックアップ、光ディスクなどにより構成される。記録再生チャネル部１３は、テレビジョン放送に適用された場合、その放送の通信方式にあった送信や受信を行う。また、記録再生チャネル部１３は、記録媒体にデータを記録し、その記録媒体に記録されたデータを再生するような場合、その記録媒体に適した構成とされる。
【００３２】
等化・タイミング検出・チャネル復号部１４は、再生信号から記録データを復元するのに適した等化やタイミング検出を行い、記録データの推定値やその確率を計算する。誤り訂正・復号部１５は、記録時に付加した冗長性を用いて再生信号に生じた誤りを訂正し、情報語の推定値を出力する。チャネル復号部１６は、誤り訂正された情報語の推定値からチャネル符号化の逆の操作によりデータを復元する。
【００３３】
誤り訂正符号化部１２における誤り訂正符号化は、チャネル符号化部１１によりチャネル符号化された情報語ｄにおけるチャネル符号の制約の性質をなるべく損なわないようにする必要がある。誤り訂正符号を符号長ｎの線形ブロック符号とすれば、符号語をｋ個の情報部とｎ-ｋ個のパリティ部とで構成する組織符号とすることにより、符号化の際には情報部はそのまま符号語の一部となり、パリティ部を追加するだけでよい。また、復号時においてはパリティ部を除去するだけでよい。
【００３４】
図２Ａと図２Ｂは、それぞれ組織符号における情報部とパリティ部の割り当ての例を示している。図２Ａおよび図２Ｂにおいて、白四角は情報ビット、黒四角はパリティビットをそれぞれ表している。図２Ａは、符号語の前半に情報部、後半にパリティ部がまとまって割り当てられている例を示し、図２Ｂは、符号語中にパリティビットが周期的に挿入されて割り当てられている例を示している。
【００３５】
図２Ａに示したように、情報部とパリティ部をそれぞれまとめて割り当てると、情報部はチャネル符号の制約を満たすが、パリティ部はチャネル符号の制約を満たさないという問題がある。一方、図２Ｂのように、周期的にパリティ部を割り当てると、チャネル符号制約を満たさないパリティ部が局所的に集中することがないため、チャネル符号制約の乱れを少なくすることができる。従って、図１に示したシステムのように誤り訂正符号化部１２の前段にチャネル符号化部１１が設けられ、誤り訂正符号化の前にチャネル符号化が行われるようにした場合、図２Ｂに示したようにパリティ部が周期的に情報部に挿入された組織符号の割り当てが好ましい。
【００３６】
誤り訂正符号化方式として、LDPC（Low Density Parity Check codes)符号化方式を適用した場合を例に挙げて説明を続ける。LDPC符号化は、非零の要素が疎なパリティ検査行列で表される誤り訂正符号化方式であり、パリティ検査行列に対応したタナーグラフ (Tanner graph) を用いて軟判定繰り返し復号を行うことでシャノン（Shannon）の理論限界に近い符号化利得を与えることが知られている。
【００３７】
パリティ検査行列Ｈは、任意の符号語を符号語c = [c0 c1 c2 … cn-1]Tとしたとき、常に
Ｈc＝０
を満たす。図３に示した行列Ｈは、符号長n=26、情報ビット数k=13の２元LDPC符号のパリティ検査行列の一例である。
【００３８】
パリティ検査行列Ｈに対応するタナーグラフを図４に示す。図４に示したタナーグラフの例においては、黒丸で表したのがバリアブルノード (variable node) であり、四角で表したのがチェックノード (check node) である。バリアブルノードは、パリティ検査行列Ｈの列に対応し、チェックノードはパリティ検査行列Ｈの行に対応する。チェックノードとバリアブルノードの間の結線は、枝 (edge) であり、パリティ検査行列の非零元に相当する。
【００３９】
確率伝播アルゴリズムによるLDPC符号の復号では、タナーグラフ上におけるバリアブルノードとチェックノード間で信頼度を表す数値のやりとりを繰り返すことで各バリアブルノードに対応するビットの事後確率を更新する。そのため、各ノードは複数の枝と接続されていることが望ましい。すなわち、LDPC符号の復号に用いるパリティ検査行列の列重みは２以上が望ましい。
【００４０】
例えば、文献１には、LDPC符号のパリティ検査行列に規則的な構造をもたせた場合の例が示されている。文献１で提案されたLDPC符号は、パリティ検査行列の規則的な構造により、準巡回 (quasi-cyclic) 符号の性質を持つものである。
文献１：Y. Kou, S. Lin, M. P. C. Fossorier, “Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 2711-2736, Nov. 2001.
【００４１】
準巡回符号とは、任意の符号語をn0回巡回シフトさせたものが、また符号語となる線形符号である。準巡回符号の符号長nはmを整数としてn = m n0で表せる。
【００４２】
図３に示したパリティ検査行列で表される符号は、n0=2の準巡回符号となっている。図５は、図３に示したパリティ検査行列の列を、n0=2列ごとに取って並べ替えて記述したものである。図５のように、準巡回符号のパリティ検査行列は、n0列ごとに取って並べ替えることによって複数のm×m巡回正方行列からなる行列とすることができる。図６は準巡回符号のパリティ検査行列をn0列ごとに取って並べ替えた場合の一般的な表現を表している。ここでHi,jはそれぞれm×m巡回正方行列である。
【００４３】
図７は、文献２で例として示されている、符号長n=39、n0=3の準巡回符号のパリティ検査行列を示している。
文献２：R. L. Townsend, E. J. Weldon, “Self-Orthogonal Quasi-Cyclic Codes,” IEEE Transactions on Information Theory, vol. IT-13, no. 2, Apr. 1967.
【００４４】
図８は、図７に示したパリティ検査行列を３列おきに取って並べ替えることにより３個の巡回正方行列で表現した行列である。図８に示した行列Ｈ’は、最も右側の正方行列（図８中、点線で囲んだ部分）が、１３×１３の単位行列となっている。この１３列に対応する符号語の位置をパリティビットとする生成行列Ｇ’は、パリティ検査行列の残りの列を転置することにより求めることができる。
【００４５】
すなわち、
Ｈ’＝［Ｐ Ｉ］
としたとき、
Ｇ’＝［Ｉ ＰT］
とすることができる。
【００４６】
生成行列Ｇ’の列の並び順を、行列Ｈと同じように戻した生成行列を行列Ｇとすると、
情報語d=[d0 d1 d2 … dk-1]T
から符号語ｃへの符号化は、次式に基づいて演算される。
ｃ＝ＧT ｄ
【００４７】
図９は、このような演算により求められた生成行列Ｇにより情報語ｄが符号語ｃに符号化される様子を模式的に示した図である。符号語中に情報語ｋ0=２ビットに対してパリティがｎ0-ｋ0＝１ビットずつ挿入された形となっている。このような形は、図１のようにチャネル符号化がなされた情報語を、符号化する際に適した情報語とパリティの配置となっている。
【００４８】
準巡回符号において、図７に示したようなパリティ検査行列のn0列単位でみた特定の位置の列からなる行列が、単位行列となる場合、対応するビットの位置をパリティとする符号化を行うｋ＝ｍ ｋ0段シフトレジスタによる符号化回路が文献２により提案されている。
【００４９】
組織符号の場合、誤り訂正符号化部１２は、図１０に示すような構成とすることができる。即ち、図１０に示した誤り訂正符号化部１２は、情報語ｄを入力としてパリティを演算するパリティ演算部３１、情報語ｄを遅延させるバッファメモリ３２、情報語とパリティを適切な順に並べ替えるセレクタ３３を含む構成とされる。なお、図１０には図示していないが、誤り訂正符号化部１２の各部を制御する制御部も含まれる。
【００５０】
図１１は、図７のパリティ検査行列による準巡回符号のｋ段シフトレジスタによるパリティ演算回路３１のブロック図である。パリティ演算回路３１は、スイッチ５１、レジスタ５２-１乃至５２-２６、および、排他的論理和(EXOR)回路５３を含む構成とされている。
【００５１】
図１１に示したパリティ演算回路３１のスイッチ５１が、データを入力する位置にセットされ、情報語d0，d1，d2，…，d25が順にレジスタ５２-１乃至５２-２６にそれぞれ保持される。入力が終わるとスイッチ５１が、パリティ側に切り換えられ、レジスタ５２-１乃至５２-２６の中身が巡回シフトするようにされる。最初の出力としてパリティc2が出力される。その後、２サイクルおきにパリティが順次出力される。
【００５２】
排他的論理和演算回路５３の入力側と接続されるレジスタ５２-１乃至５２-２６の数と位置は、例えば、行列Ｐの最初の行における“１”の場所と関連付けられる。行列Ｐとは、ここでは、例えば図８に示した行列のうち、単位行例を除いた部分の行列のことである。
【００５３】
図１２は、パリティ演算回路３１のブロック図であり、図７のパリティ検査行列による準巡回符号のk/2段シフトレジスタによるパリティ演算回路３１のブロック図である。図１２に示したパリティ演算回路３１は、スイッチ７１-１，７１-２、レジスタ７２-１乃至７２-１３、および排他的論理和演算回路７３-１乃至７３-６を含む構成とされている。
【００５４】
図１２に示したパリティ演算回路３１は、符号化を開始する前の時点で、レジスタ７２-１乃至７２-１３の値を全て０（ゼロ）にセットする。次に、スイッチ７１-１とスイッチ７１-２をそれぞれ、Data0とData1を入力する位置にし、情報語d0，d1，d2，…，d25を２ビットずつ順に入力する。入力が終了されると、レジスタ７２-１乃至７２-１３のそれぞれでパリティc2，c5，c8，…，c35が求められる。
【００５５】
スイッチ７１-１とスイッチ７１-２を、それぞれパリティの位置にし、レジスタ７２-１乃至７２-１３の中身を巡回させることにより、左端から１ビットずつパリティが出力される。排他的論理和演算回路７３-１乃至７３-６のそれぞれの入力と接続されるレジスタ７２-１乃至７２-１３の数と位置は、例えば、行列Ｐに含まれる各巡回行列の最初の列における“１”の場所と関連付けられる。
【００５６】
ところで、図３に示したパリティ検査行列で示されるLDPC符号は、準巡回符号ではあるが、図４に示したタナーグラフにおける各ノードは、複数の枝と接続されているという条件から、図７の行列とは異なり、列を抜き出しても単位行列とはならない。パリティ検査行列Ｈの中から選んだ(ｎ-ｋ)列で構成される行列の階数 (rank) が、パリティ検査行列Ｈの階数に一致すれば、例えば、ガウス消去法によって生成行列を求めることができるが、このような行列の変形は、元々のパリティ検査行列Ｈにおける非零の要素が疎であるという性質が保てなくなるため、符号化が複雑になってしまう可能性があった。
【００５７】
また線形符号は、生成行列が与えられれば情報語から符号語への変換が一意に求められる。LDPC符号の誤り復号性能は、パリティ検査行列の構造により決定付けられるが、パリティ検査行列が与えられただけでは、情報語から符号語への変換には自由度がある。準巡回符号を、LDPC符号として用いる場合において、n0ビット単位でみた特定の位置のビットをパリティとする組織符号の符号化を行うときには、ｋ段シフトレジスタによる符号化が行えるため、行列の演算に比べると回路は簡略化される。
【００５８】
しかしながら、n0ビット単位でみた、どの位置のビットをパリティとするかという自由度に対しても、さらに検討を加えることで、より符号化に関わる回路規模を小さくしたり、演算量を少なくしたりすることができる。そこで、以下の説明においては、n0ビット単位でみた、どの位置のビットをパリティとするかという自由度に対して検討を加え、より符号化に関わる回路規模を小さくし、演算量を少なくする実施の形態について説明を加える。
【００５９】
図３に示したパリティ検査行列を用いるLDPC符号を例としてあげ、以下の説明を続ける。また、情報語の１ビット単位にパリティを１ビットずつ挿入された形の組織符号として符号化する場合を例に挙げて説明する。
【００６０】
図３に示したパリティ検査行列の列の順を並び替え、２個の１３×１３巡回行列で記述すると、図５に示したような行列となる。図５に示したように、また、上記したように、図３に示したパリティ検査行列で示されるLDPC符号は、準巡回符号ではあるが、列を抜き出しても単位行列とはならない。よってこのような場合、元々のパリティ検査行列Ｈにおける非零の要素が疎であるという性質が保てなくなるため、以下に説明することを考慮せずに符号化を行うと、符号化が複雑になってしまう可能性がある。
【００６１】
図５に示したパリティ検査行列に含まれる２個の巡回行列は、いずれも階数が１３であるので、符号語２６ビットにおける情報ビットとパリティビットは、図１３Ａまたは図１３Ｂに示した、いずれの割り当てでも可能である。図１３Ａ、図１３Ｂ中、白四角は情報ビットを表し、黒四角はパリティビットを表している。
【００６２】
図１３Ａに示したような割り当て、すなわち、パリティビットのあとに情報ビットが割り当てられるような行の基本変形を施すと、図１４に示したような行列Ｈ”となる。図１３Ｂに示したような割り当て、すなわち、情報ビットのあとにパリティビットが割り当てられるような行の基本変形を施すと、図１５に示したような行列Ｈ”となる。
【００６３】
図１４に示した行列Ｈ”の左側の１３×１３行例は、単位行列となり、図１５に示した行列Ｈ”の右側の１３×１３行列は、単位行列となっている。すなわちこの場合、図５（または図３）に示したパリティ検査行列が、単位行列を含む行列に基本変形される。
【００６４】
図１４に示した行列Ｈ”を元に、ｋ段シフトレジスタによるパリティ演算回路を構成すると、図１６に示した構成となる。図１５に示した行列Ｈ”を元に、ｋ段シフトレジスタによるパリティ演算回路を構成すると、図１７に示した構成となる。
【００６５】
図１６に示したパリティ演算回路は、スイッチ１１１、レジスタ１１２-１乃至１１２―１３、および、排他的論理和演算回路１１３を含む構成とされている。排他的論理和演算回路１１３には、レジスタ１１２-１、レジスタ１１２-５、レジスタ１１２-６、レジスタ１１２-７、レジスタ１１２-９、レジスタ１１２-１１、およびレジスタ１１２-１２からのそれぞれの出力が入力されるように構成されている。
【００６６】
図１７に示したパリティ演算回路は、スイッチ１３１、レジスタ１３２-１乃至１３２―１３、および、排他的論理和演算回路１３３を含む構成とされている。排他的論理和演算回路１３３には、レジスタ１３２-１、レジスタ１３２―３、およびレジスタ１３２-８からのそれぞれの出力が入力されるように構成されている。
【００６７】
図１６に示したパリティ演算回路と図１７に示したパリティ演算回路を比較するに、図１６に示したパリティ演算回路の排他的論理和演算回路１１３へのレジスタ１１２からの入力は、７入力であるのに対し、図１７に示したパリティ演算回路の排他的論理和演算回路１３３へのレジスタ１３２からの入力は、３入力である点が異なる。
【００６８】
排他的論理和演算回路１１３（１３３）に入力されるデータ数が少ない方が、排他的論理和演算回路１１３（１３３）の演算量を少なくすることができることを意味している。また、排他的論理和演算回路１１３（１３３）に入力されるデータ数が少ない方が、パリティ演算回路の回路規模をより小さくできることを意味している。
【００６９】
よって、図１６に示したパリティ演算回路と図１７に示したパリティ演算回路を比較したとき、図１７に示したパリティ演算回路の排他的論理和演算回路１３３の方が、図１６に示したパリティ演算回路の排他的論理和演算回路１１３よりも入力数が少ないため、図１７に示したパリティ演算回路の方が、回路規模を小さくすることができ、早い符号化動作をすることができる。
【００７０】
従って、図３に示したパリティ検査行列を用いるLDPC符号を、情報語１ビット単位にパリティ１ビットが挿入された形の組織符号として符号化する場合、情報ビットとパリティビットの割り当てとして図１３Ｂで示した方を適用した方が、図１３Ａで示した方を適用する場合と比べて、より高速に動作し且つ回路規模の小さな符号化回路が実現できる。
【００７１】
ところで、排他的論理和演算回路１１３（１３３）に接続されるレジスタ１１２（１３２）の数と位置は、例えば、行列の最初の行における“１”の場所と関連付けられる。このことについて、再度、図１４乃至図１７を参照して説明する。
【００７２】
図１４に示したパリティ検査行列Ｈ”のうちの点線を付した部分の行が、図１６の排他的論理和演算回路１１３の入力の数と位置に関わっている。すなわち、図１４に示したパリティ検査行列Ｈ”のうちの点線を付した部分の行は、
１０００１１１０１０１１０
であるが、この“１”の位置（非零の要素）の位置が、排他的論理和演算回路１１３の入力の数と位置に関わっている。
【００７３】
この行には非零の要素が、７個含まれている。よって、排他的論理和演算回路１１３への入力は、７個となる。また、この行の非零の要素の位置は、排他的論理和演算回路１１３への入力の位置、すなわち、どのレジスタ１１２からの入力を受けるかに関係している。この場合、非零の要素は、左側から数えると、１番目、５番目、６番目、７番目、９番目、１１番目、および１２番目に存在している。よって、この非零の要素の位置に対応する位置に設けられているレジスタ１１２-１、レジスタ１１２-５、レジスタ１１２-６、レジスタ１１２-７、レジスタ１１２-９、レジスタ１１２-１１、およびレジスタ１１２-１２からの出力が、排他的論理和演算回路１１３に入力されるように接続される。
【００７４】
図１５に示したパリティ検査行列Ｈ”と図１７に示したパリティ演算回路との間にも、同様な関係が成り立っている。すなわち、図１５に示したパリティ検査行列Ｈ”のうちの点線を付した部分の行が、図１７の排他的論理和演算回路１３３の入力の数と位置に関わっている。すなわち、図１５に示したパリティ検査行列Ｈ”のうちの点線を付した部分の行は、
１０１００００１０００００
であるが、この“１”の位置（非零の要素）の位置が、排他的論理和演算回路１３３の入力の数と位置に関わっている。
【００７５】
この行には非零の要素が、３個含まれている。よって、排他的論理和演算回路１３３への入力は、３個となる。また、この行の非零の要素の位置は、排他的論理和演算回路１３３への入力の位置、すなわち、どのレジスタ１３２からの入力を受けるかに関係している。この場合、非零の要素は、左側から数えると、１番目、２番目、および８番目に存在している。よって、この非零の要素の位置に対応する位置に設けられているレジスタ１３２-１、レジスタ１３２-２、およびレジスタ１３２-８からの出力が、排他的論理和演算回路１３３に入力されるように接続される。
【００７６】
このように、排他的論理和演算回路に接続されるレジスタの数と位置は、基本変換された行列の最初の行における“１”の場所（非零の要素の場所）と関連付けられる。よって、この非零の要素が少なければ、排他的論理和演算回路への入力数が少なくなり、演算量の低減や回路規模の縮小をはかることが可能となる。
【００７７】
同様なことが、ｋ段シフトレジスタによるパリティ演算回路でも言える。次に、ｋ段シフトレジスタによるパリティ演算回路について説明を加える。
【００７８】
ｋ段シフトレジスタによるパリティ演算回路では、n0-k0個の排他的論理和演算回路を必要とする。例えば、i番目の排他的論理和演算回路への入力数は、パリティ検査行列を図１８に示したような形で記述したときの巡回行列Pi,jを要素とする行列Ｐのi行目からなる行列 (Pi,0 Pi,1 … Pi,k0-1) における１行あたりの非零要素数ｗとなる。
【００７９】
排他的論理和演算回路への入力数が多いほど演算時間がかかるため、非零要素数ｗの最大値が最小となるようにパリティの位置を選ぶことで、速い符号化動作が可能となる。
【００８０】
非零要素数ｗの入力の排他的論理和演算回路は、ｗ-１個の２入力排他的論理和演算回路でも記述できる。従って、非零要素数ｗの和を最小とすれば、符号化回路全体の回路規模を小さくすることが可能となる。
【００８１】
ｋ0が２以上の場合、ｋ個のレジスタを使う別のパリティ演算回路として、ｋ段シフトレジスタによるパリティ演算回路のシフト動作をｋ0クロックサイクル分一度に行うようにすることができる。このように構成した場合の回路構成は、ｋ0個のｍ段シフトレジスタとなるが、排他的論理和演算回路の数や各排他的論理和演算回路への入力数は、ｋ段シフトレジスタによる構成と同じである。従って、非零要素数ｗの最大値が最小となるようにパリティの位置を選べば、速い符号化動作が可能となる。また、非零要素数ｗの和を最小とすれば、符号化回路全体の回路規模を小さくすることが可能である。
【００８２】
ここで再度、図３のパリティ検査行列Ｈで表される、符号長ｎ＝２４、情報ビット数ｋ＝１２、パリティビット数ｎ-ｋ＝１２のLDPC符号に対応する符号化回路について説明する。
【００８３】
図１４Ａに対応するｎ0―ｋ0個のｍ段シフトレジスタによるパリティ演算回路を構成すると、図１９に示すような構成となる。また、図１４Ｂに対応するｎ0―ｋ0個のｍ段シフトレジスタによるパリティ演算回路を構成すると、図２０に示すような構成となる。
【００８４】
図１９に示したパリティ演算回路は、スイッチ２１１、レジスタ２１２-１乃至２１２-１３、および、排他的論理和演算回路２１３-１乃至２１３-７を含む構成とされている。図２０に示したパリティ演算回路は、スイッチ２３１、レジスタ２３２-１乃至２３２-１３、および、排他的論理和演算回路２３３-１乃至２３３-３を含む構成とされている。
【００８５】
図１９に示したパリティ演算回路と図２０に示したパリティ演算回路を比較するに、パリティを計算する２入力の排他的論理和演算回路の数が、図１９に示した構成では、排他的論理和演算回路２１３-１乃至２１３-７の７個であるのに対し、図２０に示した構成では、排他的論理和演算回路２３３-１乃至２３３-３の３個である。よって、図２０に示したパリティ演算回路の方が、排他的論理和演算回路が少ない構成とすることができ、回路規模を小さくすることが可能となる。
【００８６】
従って、図３に示したパリティ検査行列Ｈを用いるLDPC符号を、情報語１ビット単位にパリティ１ビットが挿入された形の組織符号として符号化するｎ0-ｋ0個のｍ段シフトレジスタによる符号化回路を構成する場合、情報ビットとパリティビットの割り当てとして図１４Ｂに示した割り当て方法を適用した方が、図１４Ａに示した割り当て方法を適用するよりも、回路規模の小さな符号化回路が実現できる。
【００８７】
上述してきたように、ｎ0―ｋ0個のｍ段シフトレジスタによるパリティ演算回路で必要な排他的論理和演算回路の数は、パリティ検査行列を図１８の形で記述したときの行列Ｐによって求めることができる。排他的論理和演算回路が挿入されるパリティ演算回路内の候補となる位置は、各レジスタの出力であり、それぞれのレジスタは、行列Ｐの各行と対応する位置とすることができる。
【００８８】
行列Ｐのｍi+r行目に対応するレジスタの出力は、各巡回行列Pi,0 ，Pi,1 ，… ，Pi,k0-1のそれぞれr行目０列目成分(Pi,j)r,0が全て０の場合、排他的論理和演算回路を介さず行列Ｐのmi+{(r+1) mod m}に対応するレジスタに接続される。
【００８９】
また、ｗ＞０個の非零要素があれば非零要素の箇所それぞれに対応したｗ個の入力との排他的論理和が演算され、行列Ｐのmi+{(r+1) mod m}に対応するレジスタに接続される。ｗ＞０の場合、排他的論理和演算回路にｗ＋１個の入力がなされる。よって、入力数が多いほど演算時間がかかるため、ｗの最大値が最小となるようにパリティの位置を選べば、よりｗの最大値が大きい割り当てに比べて速い符号化動作が可能となる。
【００９０】
ｗ＋１個の入力の排他的論理和演算回路は、ｗ個の２入力の排他的論理和演算回路でも記述できる。従って、ｗの和を最小とすれば、符号化回路全体の回路規模が小さくできる。
【００９１】
上述した実施の形態においては、符号語が２６ビットなどの比較的小さなビット数のときを例に挙げて説明したため、例えば、図１６や図１７に示したパリティ演算回路における排他的論理和演算回路１１３や排他的論理和演算回路１３３に入力されるデータ数が、３や７といった比較的小さな差となるが、扱うビット数が増すことで、排他的論理和演算回路に入力される数や、排他的論理和演算回路の数に大きな違いが生じる。そこで、さらに、比較的大きなビット数を扱う場合を例に挙げて説明を続ける。
【００９２】
次に、パリティ検査行列をn0列おきに取って並べ替えたものが、
Ｈ’=[Ｈ0,0 Ｈ0,1 … Ｈ0,17]
で表されるn0=18、k0=17、m=148の準巡回符号によるLDPC符号の例を示す。このような表記だが、例えば、図５に示したパリティ検査行列Ｈ’を、このような表記で行うと、
Ｈ’=[Ｈ0,0 Ｈ0,1]
となる。すなわち、図５において、左側の行列が、Ｈ0,0であり、右側の行列が、Ｈ0,1である。
【００９３】
ここで、Ｈ’=[Ｈ0,0 Ｈ0,1 … Ｈ0,17]における、各Ｈ0,jは１４８×１４８巡回正方行列である。よって、１４８×１４８の巡回正方行列が１８個並ぶような行列を図示するのは困難であるので、図２１に示したような形で図示する。
【００９４】
図２１に示したのは、各巡回正方行列のうちの０列目に注目し、その０列目に含まれる非零要素が存在する行番号である。例えば、巡回正方行列Ｈ0,0の０列目の１１１行目、１３６行目、１４７行目は“１”であり、その他の行番号の要素は“０”である。
【００９５】
参考とし、図５に示したパリティ検査行列Ｈ’を、図２１に示したような形で図示すると、図２２に示したようになる。図５と図２２を参照するに、図５に示したパリティ検査行列Ｈ’のうちの左側の巡回行列Ｈ0,0の０列目には、図２２に示すように、０行目、９行目、１２行目に“１”がある。同様に、図５に示したパリティ検査行列Ｈ’のうちの右側の巡回行列Ｈ0,1の０列目には、図２２に示すように、０行目、６行目、１１行目に“１”がある。
【００９６】
図２１に示した行列の説明に戻り、上記したように、各Ｈ0,jの０列目の要素は図２１に示した行番号を除き“０”である。また、各Ｈ0,jの０列目以外の各列は、ひとつ左の列を下方向に１段巡回シフトしたものである。
【００９７】
各巡回行列の階数は、全て１４８であるため、１８ビットおきにパリティを１ビット挿入するような割り当ては、１８通り可能である。
【００９８】
パリティ演算回路は、ｋ＝２５１６段シフトレジスタ、あるいはｋ0＝１７個のｍ＝１４８段シフトレジスタによる構成が可能である。ここではレジスタ数の少ないｎ0―ｋ0＝１個のｍ＝１４８段シフトレジスタによる構成で実現する場合を例に挙げて説明する。レジスタ数が少ない方が、小さな回路規模を実現できるため、ここでは、レジスタ数が少ない方を例に挙げて説明する。
【００９９】
ｋ段シフトレジスタによるパリティ演算回路を設計するか、または、ｎ0-ｋ0個のｍ段シフトレジスタによるパリティ演算回路を設計するかを決定する１つの判断要因としては、最終的なパリティ演算回路に含まれるレジスタの個数が少なくなる方を選択することが考えられる。そして、レジスタの個数が少なくなる方はどちらであるかを判断する１つの判断要因としては、符号化率が１／２以下である場合には、ｋ段シフトレジスタによるパリティ演算回路を設計し、符号化率が１／２以上である場合には、ｎ0-ｋ0個のｍ段シフトレジスタによるパリティ演算回路を設計することが考えられる。
【０１００】
取り扱うビット数が多いときなど、上記したことを考慮し、予めどのようなパリティ演算回路を設計するかを決定した後に、その決定したパリティ演算回路に関わる、図２３に示したような表を生成する。
【０１０１】
図２３に示した表は、パリティの候補となる１８通りのビット位置の組を選び、各候補に対して、対応する巡回行列を単位行列とするように、パリティ検査行列Ｈ’に行の基本変形を施して、パリティ位置に対応する列を除いた残りを行列Ｐとするときに、その行列Ｐに含まれる非零要素の数ｗの和と最大値を示した表である。
【０１０２】
図５を参照して説明した行列を再度例に挙げて説明するならば、図３に示したような行列を、図５に示したような行列に変換し、さらにパリティを割り当てる位置に対応し、図１５又は図１６に示した単位行列を含む行列に変換する。このように、パリティの割り当てる位置毎に、異なる行列が作成されるので、その作成された行列、この場合図２１に示した行列の特徴を示したのが、図２３である。
【０１０３】
即ちこの場合、パリティの割り当てる位置は、１８通りあるので、図１５や図１６に示したような単位行列を含む行列が、１８個作成される。ここでは、パリティの位置に対応する巡回行列をそれぞれＨ0,0，Ｈ0,1，・・・，Ｈ0,17とし、行の基本変形によって得られた行列から単位行列を除いた部分の行列Ｐに含まれるｗの和と最大値を表したのが図２３である。
【０１０４】
参考とし、図５に示したパリティ検査行列Ｈ’から生成された図１４に示した行列Ｈ”と図１５に示した行列Ｈ”を、図２３に示したような形で図示すると、図２４に示したようになる。図１４と図２４を参照するに、図１４の行列Ｈ”の右側の行列（単位行列でない側）の１行に含まれる非零要素の数は、“７”であるため、ｗの和は、“７”となり、ｗの最大値は１となる。同様に、図１５と図２４を参照するに、図１５の行列Ｈ”の左側の行列（単位行列でない側）の１行に含まれる非零要素の数は、“３”であるため、ｗの和は、“３”となり、ｗの最大値は１となる。
【０１０５】
図２４は、ｎ0-ｋ0個のｍ段シフトレジスタによるパリティ演算回路を生成するときの表である。図１４または図１５に示した行列Ｈ”は、ｋ0＝１のときの行列であるので、ｗの最大値として取り得る範囲は１である。よって、図２４に示したように、ｗの最大値は、それぞれ“１”となっている。
【０１０６】
これに対して、図２３に示した表を再度参照するに、図２３に示した表は、ｎ0-ｋ0個のｍ段シフトレジスタによるパリティ演算回路を生成するときの表であり、ｋ0＝１７のときの表である。よって、ｗの最大値として取り得る範囲は、１乃至１７となる。図２３に示したように、ｗの最大値としては、最小値が“６”であり、最大値が“１６”であるので、この１乃至１７という範囲内であることがわかる。
【０１０７】
ｗの和は、上記してきたように、各排他的論理和演算回路に入力されるデータ数の総和に関わる数値であり、ｗの最大値は、１つの排他的論理和演算回路に入力されるデータ数の最大値に関わる数値である。ｗの和の値も、ｗの最大値も、共に、小さい値を選択することで、回路規模の縮小と演算処理の低減をはかることが可能となる。
【０１０８】
すなわち、図２３に示した例によれば、ｗの和とｗの最大値のいずれも行列Ｈ0,4に対応する位置を、パリティとしたときに最小となることがわかる。従って、Ｈ0,4に対応するビットの位置をパリティに割り当てる符号化方法とすることで、n0=18、k0=17、m=148の準巡回符号によるLDPC符号のときには、最も小さな回路規模、速い動作速度が達成できる符号化回路を構成することが可能となる。
【０１０９】
図２３に示した例を参照するに、例えば、巡回行列Ｈ0,0のｗの和と巡回行列Ｈ0,4のｗの和は、それぞれ、“１２６３”と“４２７”である。この数値から、巡回行列Ｈ0,0のｗの和は、巡回行列Ｈ0,4のｗの和の約３倍であることがわかる。すなわちこの場合、巡回行列Ｈ0,0を適用してパリティ演算回路を作成すると、各排他的論理和演算回路に入力されるデータ数の総和が、巡回行列Ｈ0,4を適用してパリティ演算回路を作成した場合に比べて約３倍であることを意味する。
【０１１０】
このように、扱うビット数が大きくなると、どの巡回行列を適用するかにより、排他的論理和演算回路に入力されるデータ数が大きく異なってくるので、演算量や回路規模に大きな差が生じてくると考えられる。よって、扱うビット数が大きい場合、本発明を適用することで、回路規模を縮小したり、演算量を少なくしたりするといった効果を、より期待することが可能である。また、上記してきたように、適切な巡回行列を選択するまでの処理、換言すれば、図２３に示したような表を作成するまでの処理は、比較的簡便であるので、表を作成するまでの処理で、従来の処理よりも負担が増加するといったようなことはない。
【０１１１】
なお、図２３を参照して説明した例の場合、行列Ｈ0,4がｗの和とｗの最大値ともに、最小となったが、ｗの和の最小値をとる行列と、ｗの最大値が最小値となる行列が別々の場合、どちらを優先するか、換言すれば、各排他的論理和演算回路に入力されるデータ数の総和を少なくする方を優先するか、１つの排他的論理和演算回路に入力されるデータ数の最大値を少なくする方を優先するかは、適宜、設計の段階などで検討されればよい。
【０１１２】
また、上記してきたように、ｗの和が最小となる行列や、ｗの最大値が最小となる行列を選択し、その選択した行列にあったパリティ演算回路を設計することで、回路規模を小さくでき、演算処理の低減をはかることができるが、例えば、図２３に示したような表を作成することで、パリティの候補とした位置に対応する巡回行列のうち、どの巡回行列を用いると、どのような回路規模になるかなどを予測することが可能となる。よって、必ずしも、ｗの和が最小となる行列や、ｗの最大値が最小となる行列を選択しなくても、目的にあった回路を設計するための１つの資料としても、図２３に示したような表を作成することは意義がある。
【０１１３】
上述してきた処理であるが、図２３に示したような表を作成するまでの処理について、再度、図２５のフローチャートを参照し、簡便な説明を加える。
【０１１４】
ステップＳ２１において、処理対象となるパリティ検査行列が決定される。ステップＳ２１において、例えば、図３に示したようなパリティ検査行列が処理対象の行列として決定される。
【０１１５】
ステップＳ２２において、処理対象とされたパリティ検査行列に対して、基本変形が施される。基本変形とは、処理対象とされているパリティ検査行列を、単位行列を含む行列に変形することを意味する。ステップＳ２２の処理が実行されることにより、例えば、図３に示したようなパリティ検査行列が処理対象の行列とされているときには、例えば、図１４や図１５に示した行列に変形される。なお、基本変形を行う前の段階として、例えば、図５に示したような行列に変形するなどの処理が、適宜行われるようにしても勿論良い。
【０１１６】
ステップＳ２２における処理対象とされた行列に対して基本変形を行う処理は、人により行われても良いし、プログラムを組み、そのプログラムを実行することで行われるようにしても良い。また、ステップＳ２２の処理も含め、図２５に示したフローチャートの各処理は、人により行われても良いし、プログラムが実行されることにより行われるようにしても良い。
【０１１７】
ステップＳ２３において、設計したいパリティ演算回路を適用する符号化の符号化率は、１／２以上であるか否かが判断される。この判断は、上記したように、パリティ演算回路に含まれるレジスタの数が少なくなる回路を判断するための処理である。ステップＳ２３において、符号化率が１／２以上であると判断された場合、ステップＳ２４に処理が進められる。
【０１１８】
ステップＳ２４において、ｎ0―ｋ0個のｍ段シフトレジスタによるパリティ演算回路のための表が作成される。例えば、図３に示したパリティ検査行列が処理対象の行列とされていた場合には、図１９または図２０に示したパリティ演算回路が作成されるような、図２４に示したような表が作成される。また例えば、図２１に示したようなパリティ検査行列が処理対象の行列とされていた場合には、図２３に示したような表が作成される。
【０１１９】
一方、ステップＳ２３において、符号化率が１／２以上ではないと判断された場合、ステップＳ２５に処理が進められる。
【０１２０】
ステップＳ２５において、ｋ段シフトレジスタによるパリティ演算回路のための表が作成される。例えば、図３に示したパリティ検査行列が処理対象の行列とされていた場合には、図１６または図１７に示したパリティ演算回路が作成されるような、図２６に示したような表が作成される。
【０１２１】
図２６に示した表は、図３に示したパリティ検査行列が処理対象の行列とされていた場合であり、ｋ段シフトレジスタによるパリティ演算回路を設計するときの表であるため、ｗの和に関する値は、図２４に示した場合と同じ値となるが、ｗの最大値に関する値は、図２４に示した場合とは異なる値となる。すなわちこの場合、ｎ0-ｋ0＝１であるので、設計されるｋ段シフトレジスタによるパリティ演算回路に設けられる排他的論理和演算回路の数は、１つとなる。
【０１２２】
よって、ｗの最大値は、１つの排他的論理和演算回路に入力されるデータ数の最大値に関わる数値であるので、その排他的論理和演算回路が１つの場合、その排他的論理和演算回路に入力されるデータ数の最大値は、各排他的論理和演算回路に入力されるデータ数の総和に関わる数値である、ｗの和と同一の値となる。よって、図２６に示したような表が作成される。  
【０１２３】
このようにして作成された表から、ｗの和が最小となる巡回行列を判断し、その判断結果に基づくパリティ演算回路が設計されたり、ｗの最大値が最小となる巡回行列を判断し、その判断結果に基づくパリティ演算回路が設計されたりする。
【０１２４】
このように、符号長ｎ＝ｍ ｎ0、情報語長ｋ＝ｍ ｋ0の準巡回符号をLDPC符号として用いる通信システムや記録再生システムにおいて、情報語ｋ0単位に(ｎ0―ｋ0)個のパリティが挿入された形の組織符号として符号化する場合、ｎ0単位でみたときに取り得るパリティ位置(ｎ0―ｋ0)箇所の全組み合わせのうち、パリティ検査行列の列の順を並び替えて複数のｍ×ｍ巡回行列で記述し、パリティの位置に対応する列からなる(n-k)×(n-k)行列を単位行列とするようにパリティ検査行列に行の基本変形を施し、そこから単位行列を除いた残りを行列Ｐとするとき、
１、行列Ｐの中に含まれる非零の要素数が最小となるように（ｎ-ｋ）箇所をパリティに割り当てる
または／および
２、行列Ｐの各行における非零の要素数の最大値が最小となるように（ｎ-ｋ）箇所をパリティに割り当てる
または／および
３、行列Ｐの各行におけるｍ列単位でみたｋ0個の要素のうちの非零要素数の最大値が最小となるように（ｎ-ｋ）箇所をパリティに割り当てる
ようにすることで、以下のような効果がある。
【０１２５】
k段シフトレジスタによるパリティ演算回路において、排他的論理和演算回路への入力数が少なくなり、速い動作速度を得られる回路が実現可能となる。また、(ｎ0―ｋ0)個からなる排他的論理和演算回路の回路規模を小さくすることが可能となる。
【０１２６】
また、ｋ0個のｍ段シフトレジスタを用いても、同じ効果を得ることが可能となる。
【０１２７】
さらに、(ｎ0―ｋ0)個のｍ段シフトレジスタによるパリティ演算回路において、排他的論理和演算回路への入力数が少なくなり、速い動作速度を得られる回路が実現可能となる。また、排他的論理和演算回路の回路規模を小さくことが可能となる。
【０１２８】
なお、上述した実施の形態においては、LDPC符号を例に挙げて説明したが、LDPC符号以外の符号化についても、本発明を適用できる。
【０１２９】
［記録媒体について］
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【０１３０】
図２７は、上述した一連の処理をプログラムにより実行するパーソナルコンピュータのハードウェアの構成の例を示すブロック図である。
【０１３１】
コンピュータにおいて、CPU（Central Processing Unit）４０１、ROM（Read Only Memory）４０２、RAM（Random Access Memory）４０３は、バス４０４により相互に接続されている。
【０１３２】
バス４０４には、さらに、入出力インターフェース４０５が接続されている。入出力インターフェース４０５には、キーボード、マウス、マイクロホンなどよりなる入力部４０６、ディスプレイ、スピーカなどよりなる出力部４０７、ハードディスクや不揮発性のメモリなどよりなる記憶部４０８、ネットワークインタフェースなどよりなる通信部４０９、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア４１１を駆動するドライブ４１０が接続されている。
【０１３３】
以上のように構成されるコンピュータでは、CPU４０１が、例えば、記憶部４０８に記憶されているプログラムを、入出力インターフェース４０５及びバス４０４を介して、RAM４０３にロードして実行することにより、上述した一連の処理が行われる。
【０１３４】
コンピュータ（CPU４０１）が実行するプログラムは、例えば、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)等）、光磁気ディスク、もしくは半導体メモリなどよりなるパッケージメディアであるリムーバブルメディア４１１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供される。
【０１３５】
そして、プログラムは、リムーバブルメディア４１１をドライブ４１０に装着することにより、入出力インターフェース４０５を介して、記憶部４０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部４０９で受信し、記憶部４０８にインストールすることができる。その他、プログラムは、ROM４０２や記憶部４０８に、あらかじめインストールしておくことができる。
【０１３６】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１３７】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１３８】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１３９】
【図１】本発明を適用したシステムの一実施の形態の構成を示す図である。
【図２】パリティの割り当てについて説明する図である。
【図３】パリティ検査行列を示す図である。
【図４】タナーグラフについて説明する図である。
【図５】パリティ検査行列を示す図である。
【図６】パリティ検査行列を一般的に表現した図である。
【図７】パリティ検査行列を示す図である。
【図８】パリティ検査行列を示す図である。
【図９】パリティが挿入される様子を示す図である。
【図１０】符号化回路の構成例を示す図である。
【図１１】パリティ演算回路の構成例を示す図である。
【図１２】パリティ演算回路の構成例を示す図である。
【図１３】パリティの割り当てについて説明する図である。
【図１４】変形されたパリティ検査行列を示す図である。
【図１５】変形されたパリティ検査行列を示す図である。
【図１６】パリティ演算回路の構成例を示す図である。
【図１７】パリティ演算回路の構成例を示す図である。
【図１８】変形されたパリティ検査行列の一般的に表現した図である。
【図１９】パリティ演算回路の構成例を示す図である。
【図２０】パリティ演算回路の構成例を示す図である。
【図２１】パリティ検査行列を示す図である。
【図２２】パリティ検査行列を示す図である。
【図２３】パリティ検査行列の特徴を示す数値が記載された表である。
【図２４】パリティ検査行列の特徴を示す数値が記載された表である。
【図２５】表の作成処理について説明するフローチャートである。
【図２６】パリティ検査行列の特徴を示す数値が記載された表である。
【図２７】記録媒体を説明する図である。
【符号の説明】
【０１４０】
１１  チャネル符号化部，  １２  誤り訂正符号化部，  １３  記録再生チャネル部，  １４  等化タイミング検出チャネル部，  １５  誤り訂正復号部，  １６  チャネル復号部，  ３１  パリティ演算部，  ３２  バッファメモリ，  ３３  セレクタ
【図１】
2008259051.tif 000003
【図２】
2008259051.tif 000004
【図３】
2008259051.tif 000005
【図４】
2008259051.tif 000006
【図５】
2008259051.tif 000007
【図６】
2008259051.tif 000008
【図７】
2008259051.tif 000009
【図８】
2008259051.tif 000010
【図９】
2008259051.tif 000011
【図１０】
2008259051.tif 000012
【図１１】
2008259051.tif 000013
【図１２】
2008259051.tif 000014
【図１３】
2008259051.tif 000015
【図１４】
2008259051.tif 000016
【図１５】
2008259051.tif 000017
【図１６】
2008259051.tif 000018
【図１７】
2008259051.tif 000019
【図１８】
2008259051.tif 000020
【図１９】
2008259051.tif 000021
【図２０】
2008259051.tif 000022
【図２１】
2008259051.tif 000023
【図２２】
2008259051.tif 000024
【図２３】
2008259051.tif 000025
【図２４】
2008259051.tif 000026
【図２５】
2008259051.tif 000027
【図２６】
2008259051.tif 000028
【図２７】
2008259051.tif 000029