(57)【特許請求の範囲】
【請求項１】
パリティ検査行列が１つあるいは複数の巡回行列によって表される自己直交ＱＣ符号の符号化方法において、
各巡回行列の列重みｗが３以上であり、かつ符号の最小ハミング距離がｗ＋２以上となるように設計された検査行列を満足する符号系列を生成し、
上記検査行列は、
上記ＱＣ符号の周期をｐ、上記検査行列の行数をｍとし、上記検査行列を構成するｐ個の巡回行列の構造を表す、要素数ｗのｐ個のアドレス集合から、重複を許して抽出されたｗ＋１個のアドレス集合におけるｊ(０≦ｊ≦ｗ）番目のアドレス集合の、各要素の１つの並べ替えをｂ0,jｂ1,j…ｂw-1,jとした時、２≦ｊ≦ｗ、１≦ｉ＜ｊの範囲内にある１つの［ｉｊ］について、ｂj-1,0−ｂi-1,0＋ｂ0,i−ｂj-1,i＋ｂi,j−ｂ0,j≠０（mod  m)が、全てのｂ0,jｂ1,j…ｂw-1,jについて成り立つ
ことを特徴とする符号化方法。
【請求項２】
ｐ≧２である
ことを特徴とする請求項１に記載の符号化方法。
【請求項３】
ｗ＝３で、かつ符号の最小ハミング距離が６以上となる
ことを特徴とする請求項２に記載の符号化方法。
【請求項４】
ｗ≧４である
ことを特徴とする請求項２に記載の符号化方法。
【請求項５】
パリティ検査行列を構成する各巡回行列における６サイクルの数が最小となる、
ことを特徴とする請求項１に記載の符号化方法。
【請求項６】
ｐ個のアドレス集合の１つを｛ａ0，ａ1，…，ａw-1｝（ａ0＝０）とした時、
【数１】
0004591371.tif 000020
の範囲内にある全ての整数ｉ0，ｉ1，ｉ2，ｉ3，ｉ4，ｉ5について、ａi0−ａi1＋ａi2−ａi3＋ａi4−ａi5≠０（mod  m)が、ｐ個のアドレス集合全てについて成り立つ
ことを特徴とする請求項５に記載の符号化方法。
【請求項７】
パリティ検査行列を構成する複数の巡回行列の中から任意に抽出された２つあるいは３つの巡回行列の間で６サイクルが存在しない、もしくは与えられたｗ，ｍ，ｐにおいて最小となる
ことを特徴とする請求項６に記載の符号化方法。
【請求項８】
ｐ個のアドレス集合から２個までの重複を許して抽出された３個のアドレス集合におけるｊ（０≦ｊ≦２）番目のアドレス集合の、各要素の並べ替えの１つをｂ0,jｂ1,j…ｂw-1,jとした時、ｂ1,0−ｂ0,0＋ｂ0,1−ｂ1,1＋ｂ1,2−ｂ0,2≠０（mod  m)を、全てのｂ0,jｂ1,j…ｂw-1,jについて評価した際に、それに違反する数が最小となる
ことを特徴とする請求項７に記載の符号化方法。
【請求項９】
ｂ1,0−ｂ0,0＋ｂ0,1−ｂ1,1＋ｂ1,2−ｂ0,2≠０（mod  m)に違反する数が０となる
ことを特徴とする請求項８に記載の符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、磁気ディスク記録再生装置、磁気テープ記録再生装置等の各種磁気記録再生装置、並びに、光磁気ディスク記録再生装置、相変化光ディスク記録再生装置、再生専用光ディスク再生装置等の各種光ディスク装置、およびテレビ放送、携帯型電話、Local Area Network (ＬＡＮ) 等の各種通信装置に使用される符号の符号化器において、伝送情報のビット誤り率 (ＢＥＲ: bit-error rate) や未検出誤り確率を低減するために用いて好適な符号化方法に関する。
【背景技術】
【０００２】
一般的に、多くの記録再生装置や通信装置においては、入力情報系列を符号化した符号系列を伝送する事により、デジタル伝送情報のＢＥＲの低減が図られている。
【０００３】
図１は、一般的な記録再生装置もしくは通信装置におけるデジタル信号処理のためのブロック図の一例である。
【０００４】
図１において、まずユーザー側の情報系列は符号化部１に入力され、ｋ／ｎの比で符号化されて符号系列となる。ただしここで、ｋは情報語長、ｎは符号語長、そしてｋ／ｎは符号率あるいは符号化率と呼ばれる。符号化は、暗号化、誤り訂正符号化、run-length limited 符号化等、複数の符号化が組み合わされる事が多い。
【０００５】
符号系列は、記録部２（もしくは送信部２）に入力され、たとえば記録再生システムにおける記録装置ならば、記録部２において光ピックアップあるいは磁気ヘッド等を用いて図示しない記録媒体上に記録され、たとえば無線通信システムにおける送信装置ならば、送信部２において送信アンテナによって信号が空間に送信される。
【０００６】
記録信号もしくは送信信号は、再生部３（もしくは受信部３）に入力され、たとえば記録再生システムにおける再生装置ならば、再生部３においてアナログ光ピックアップあるいは磁気ヘッドによって図示しない記録媒体からアナログ再生信号に変換され、たとえば無線通信システムにおける受信装置ならば、受信部３において受信アンテナによって空間中の信号からアナログ受信信号に変換される。
【０００７】
これらのアナログ信号は、図示しないアナログ等化器を用いて所定の目標等化特性に等化された後、Ａ／Ｄ変換部４においてデジタル受信信号に毎時刻変換される。ここで、Ａ／Ｄ変換部４には図示しない位相同期回路が含まれる。デジタル受信信号は、符号検出部５において検出符号系列もしくは、その事後確率情報系列に変換された後、復号部６に入力され、ｎ／ｋ の比で検出情報語に復号され、検出情報系列となる。
【０００８】
ただし、アナログ等化器による等化が十分でない場合には、Ａ／Ｄ変換部４と符号検出部５との間にデジタル等化器が設けられる場合もある。また近年、符号検出部５においては、ビタビ検出器等の軟判定検出器を用いるのが一般的である。復号部６において繰り返し復号法を用いる場合には、符号検出部５において事後確率検出器が用いられる場合がある。
【０００９】
図１において、符号化部１および復号部６に用いられる符号として様々な符号が検討され、Reed-Solomon (ＲＳ) 符号等、その内の一部が実用化されている。近年、図１の符号化部１および復号部６に用いられる、伝送情報のＢＥＲの低減に有効な誤り訂正符号の一つとして、低密度パリティ検査 (ＬＤＰＣ：low-density parity-check) 符号の研究が盛んに行なわれている。ＬＤＰＣ符号は、Gallagerによって、１９６１年に提案された古くから知られていた符号であったが、最近になって非常に優れた復号性能を有している事が明らかとなってきた。ＬＤＰＣ符号の詳細は、非特許文献１に開示されてなる。
【００１０】
ＬＤＰＣ符号とは、そのパリティ検査行列（以下、単に、「検査行列」と呼ぶ）において１の数が疎 (sparse) となるパリティ検査符号の事である。従って、ＬＤＰＣ符号とは、検査行列における１の数がある程度曖昧に定義されただけの非常に広い範囲の符号に対して適用される名前であり、たとえば一般的によく知られているＲＳ符号の様に、ある特定の符号生成規則に従った符号を指すものではない。つまり、ＬＤＰＣ符号と呼べる符号は符号語長やパリティ長が同じでも非常に多く存在する事に注意する必要がある。ＬＤＰＣ符号の復号には一般的に、Sum-Product 復号法、あるいは Belief-Propagation (ＢＰ）復号法と呼ばれる繰り返し復号法の一つが適用される。
【００１１】
ＬＤＰＣ符号に対してＢＰ復号法を適用した際に良好なＢＥＲを得るためには、その検査行列において、短いサイクル (short cycle) ができるだけ少ない事が望ましい。行列における最も短いサイクルは４サイクルであり、ＬＤＰＣ符号において復号後のＢＥＲを低減させるためには、その検査行列において４サイクルが含まれない方が望ましい事が知られている。ここで、｛０，１｝を要素とするある２値行列が４サイクルを含むとは、その行列の任意の２列を選んだとき、その両方の列に１が存在する行が２つ以上ある事である。
【００１２】
検査行列に４サイクルが含まれないとき、その符号は自己直交 (self-orthogonal) 符号と呼ばれる。自己直交符号は多くの場合、その検査行列における１の数が結果的に疎となり、ＬＤＰＣ符号として利用する事ができる。また、自己直交符号は１段多数決論理復号可能 (one-step majority-logic decodable) である事が知られている。検査行列における最小の列重み (column weight) をｗとした時、自己直交符号の最小ハミング距離（以下、「最小距離」と呼ぶ）ｄminは、（１）式となる事が知られている。ここで列重みとは、２値行列の場合、列における１の総数である。
【００１３】
ｄmin ≧ｗ＋１          ・・・（１）
また、列重み一定の検査行列を有する自己直交符号の符号語長ｎの上限は、Steiner 限界として知られており、ｗおよび検査行列の行数ｍを用いて、次式で与えられる。
【００１４】
【数１】
0004591371.tif 000002
ＬＤＰＣ符号において、一般的に、復号後のＢＥＲを低減させるためには符号の最小距離ができるだけ大きい方が望ましく、復号器の回路規模を小さくするためには列重みができるだけ小さい方が望ましい。ところが多くの場合は、最小距離を大きくしようとすると列重みの増大につながり、復号器が複雑となる。すなわち、ＬＤＰＣ符号においては、復号後のＢＥＲを改善しようとすると、その符号化および復号器の回路規模が大きくなり易い事が一つの問題点として挙げられる。
【００１５】
近年、この問題を解決する方法の１つとして、古くから知られている準巡回 (ＱＣ： quasi-cyclic) 符号をＬＤＰＣ符号として用いる方法が注目されている。ＱＣ符号は検査行列の規則性が非常に高く、その規則性を利用する事により、ＬＤＰＣ 符号として用いたとき、その符号化および復号器の回路規模の低減を図る事ができる事が期待される。ここでＱＣ符号とは、任意の符号語を、符号語長と異なるある周期ｐだけ巡回シフトした系列が、元の符号語以外の符号語となる符号の事である。ＱＣ符号において、特にｐ＝１となる符号は巡回符号と呼ばれる。ＱＣ符号を自己直交とする事も可能であり、自己直交ＱＣ符号の詳細は非特許文献２に開示されてなる。
【００１６】
ＱＣ符号の検査行列は、ｐの整数倍個の巡回行列 (circulant matrix) を用いて表す事ができる。一般的に、ｍ行ｍ列 (ｍ×ｍ) 巡回行列は、全ての列がある任意の列、たとえば最初の列の巡回シフトである行列として定義される。すなわち、ｍ×ｍ巡回行列Ｃの左端最初の列ベクトルを[ｘ0，ｘ1，…，ｘm-1]T (Ｔは転置操作を表す) と定義すれば、Ｃは、次の様に表される。
【００１７】
【数２】
0004591371.tif 000003
ただし、（３）式においては、巡回行列Ｃの各列を行列の下方向へ巡回させているが、これを上方向へ巡回させて定義しても良い。巡回行列の逆行列、および２つの巡回行列の積は、各々巡回行列となる。
【００１８】
このとき、ｍ×ｐ行列Ｄi（０≦ｉ＜ｍ）を、その第ｊ列目（０≦ｊ＜ｐ）が、ｐ個のｍ×ｍ巡回行列Ｃjの第ｉ列目からなる行列と定義すれば、周期ｐを有するＱＣ符号の検査行列Ｈpの１つは、次の様に表すことができる。
【００１９】
Ｈp＝（Ｄ0 Ｄ1 … Ｄm-1）          ・・・（４）
ＱＣ符号は、ごく簡単なシフトレジスタ回路を用いて符号化する事ができる。その方法は、例えば、上述した非特許文献２や、特許文献１および特許文献２に開示されている。
【００２０】
これまでに、ＬＤＰＣ符号として利用可能なＱＣ符号を設計するための幾つかの理論が知られているが、その1つとして、有限幾何 (finite geometry) がある。有限幾何とは、主にユークリッド幾何 (ＥＧ：Euclidean geometry) 及び射影幾何 (ＰＧ：projective geometry) の各理論の事である。有限幾何に従って設計された符号は、有限幾何符号と呼ばれる。
【００２１】
有限幾何符号においては、その検査行列が空間内の線 (lines) 上に存在する点 (points) に基づいて構成され、点が存在するとき１、点が存在しないとき０と各々定義される。ガロア体ＧＦ(２s) を部分空間とするＧＦ(２qs) を考えたとき、１つの線上に２s個の点を有するＧＦ(２s)上のｍ次元ユークリッド幾何はＥＧ(q,２s) と表現される。また、ガロア体ＧＦ(２s) を部分空間とするＧＦ(２(q+1)s） を考えたとき、１つの線上に２s＋１ 個の点を有するq 次元射影幾何はＰＧ(q,２s) と表現される。
【００２２】
有限幾何符号は、多数決論理復号可能な巡回符号として古くから知られており、例えば射影幾何ＰＧ(２,２4) に基づいた、(２７３，１９１) 差集合 (difference set) 巡回符号を１ビット短縮化 (shortened) した (２７２, １９０) 短縮化差集合巡回符号は、日本におけるテレビの文字多重放送用の誤り訂正符号として実用化されている。ここで、(ｎ, ｋ) 符号のｎは符号語長、ｋは情報語長である。ただし、有限幾何符号には２段以上で多数決論理復号可能な符号も含まれるが、その様な符号は自己直交ではない。自己直交な有限幾何符号をＬＤＰＣ符号として用いる方法は、非特許文献３に開示されてなる。
【００２３】
非特許文献３によれば、有限幾何符号の検査行列の転置行列を検査行列とする符号を有限幾何符号のtype-II符号と呼び、この様なtype-II符号にもＬＤＰＣ符号として有用な符号が幾つか存在する事が指摘されている。ここで、有限幾何符号は巡回符号、そのtypeII符号はＱＣ符号となり、かつ自己直交な有限幾何符号のtypeII符号は自己直交である。以下、有限幾何符号およびそのtype-II符号の事を、有限幾何に基づいた符号と呼ぶ。
【００２４】
有限幾何に基づいた自己直交ＱＣ符号においては、ｐ≧２の時、一般的にｄmin＝ｗ＋１となる。ただしここで、ある２値符号が与えられた時、その最小距離があるハミング距離ｄH以下であるかどうかは、たとえば次の様にして調べる事ができる。すなわち、検査行列からｄH個の列を抜き出した時、各行における１の総和のmodulo2が、全ての行において０となる様な組み合わせの例を、唯一つ示せば良い。またその際、ｄH＝ｗ＋１でかつその符号が自己直交であるならば、（１） 式より、その最小距離はｗ＋１であると確定できる。
【００２５】
ＱＣ符号の設計に利用可能なその他の理論としては、たとえば非常に古くから知られている balanced incomplete block design (ＢＩＢＤ) と呼ばれる組み合わせ論 (combinatorics) に基づいた手法がある。ＢＩＢＤに従ったＬＤＰＣ符号の構成方法は、非特許文献４に開示されている。ただし、infinite family に分類される射影幾何は、ＢＩＢＤの１つである。
【００２６】
ＢＩＢＤに従って構成される符号は、その１部にＱＣ符号が含まれるが、必ずしもＱＣ符号ではない。
【００２７】
ＢＩＢＤに従って構成されるＱＣ符号に限定しない自己直交符号の最小距離をｗ＋１よりも大きくするための検討は、これまでにｗ＝３の場合について、多く行なわれている。検査行列の列重みが全て同じで、かつｗ＝３の時、自己直交符号からハミング距離４を形成する符号語を全て取り除くと、その最小距離は６以上となる事が知られており、その様な符号の検査行列の構造は、anti-Pasch configurationと呼ばれる。
【００２８】
組み合わせ論においてPasch configurationとは、quadrilateralとも呼ばれ、Steiner triple system (ＳＴＳ) の４つの3点 (points) の和集合 (union) が、６点の集合から成る事を指す。Pasch configuration とは、言い換えれば、４つの3点が各々、{x0, x1, x2}, {x0, x4, x5}, {x1, x3, x5}, {x2, x3, x4} の形式となっている事である。Pasch configuration を含まないＳＴＳが、anti-Pasch configurationもしくはquadrilateral freeと呼ばれる。Anti-Pasch configuration の詳細は、たとえば非特許文献５に開示されてなる。
【００２９】
ただし、これまでにＱＣ符号となる、（４）式の検査行列においてｗ＝３のanti-Pasch configurationを有する符号は報告されていない様である。また、有限幾何やＢＩＢＤに基づいた自己直交ＱＣ符号においては、設計できる符号の符号語長やパリティ数は限定的である。
【００３０】
自己直交なＱＣ符号を、有限幾何やＢＩＢＤを用いずに任意の符号語長やパリティ数で設計し、かつその最小距離がｗ＋１よりも大きくなる符号、すなわち、
ｄmin≧ｗ＋２        ・・・（５）
が成り立つ符号については、たとえば、これまでｗが２の場合について、その報告がある。その詳細は、特許文献３に記載されている。
【００３１】
ＱＣ符号は、ｗ≧３の時、必ず６サイクルを含む事が知られているが、ｗ＝２の時だけは６サイクルを取り除く事ができる。そして、ｗ＝２のＱＣ符号から４サイクルおよび６サイクルを取り除くと、その最小距離は４以上となる。特許文献３の方法は、ＱＣ符号において、唯一 ｗ＝２の時に６サイクルを取り除けるという、特殊性を利用して、上述の（５）式を満たす符号を設計したものである。
【００３２】
【特許文献１】R. Townsend and E. Weldon, Jr., “Error Control System,” United States Patent, US3475724, Oct. 1969.
【特許文献２】H. Yamagishi and Y. Shimpuku, “Encoding Method and Encoder,” United States Patent，US6928602 B2, Aug. 2005.
【特許文献３】H. Song, V. Bhagavatula and J. Liu, “Encoding Method using a Low Density Parity Check Code with a Column Weight of Two”, United States Patent Application Publication, US2004/0093549 A1, May. 2004.
【非特許文献１】R.G. Gallager, "Low Density Parity Check Codes," MIT Press, Cambridge, Mass., 1963.
【非特許文献２】R. Townsend and E. Weldon, Jr., "Self-Orthogonal Quasi-Cyclic Codes," IEEE Trans. Info. Theory, vol. IT-13, no.2, pp.183-195, Apr. 1967.
【非特許文献３】Y. Kou, S. Lin and M. Fossorier, "Low Density Parity Check Codes on Finite Geometries: A Rediscovery and New Results," IEEE Trans. Info. Theory, vol. 47, no.7, pp.2711-2735, Nov. 2001.
【非特許文献４】B. Ammar, B. Honary, Y. Kou, J. Xu and S. Lin, "Construction of Low-Density Pariry-Check Codes Based on Balanced Incomplete Block Designs," IEEE Trans. on Info. Theory, vol. 50, no. 6, pp. 1257-1268, June 2004.
【非特許文献５】T.S. Griggs, J. Murphy and J.S. Phelan, “Anti-Pashe Steiner Triple Systems,” J. of Combinatorics, Information & System Sciences, vol. 15, pp. 79-84, 1990.
【発明の開示】
【発明が解決しようとする課題】
【００３３】
以上述べた様に、これまでＬＤＰＣ符号において、その符号化・復号回路の簡略化を図る方法の１つとして、自己直交ＱＣ符号を用いる事が有効であり、自己直交ＱＣ符号を設計するための代表的な理論として、有限幾何やＢＩＢＤが知られている。
【００３４】
しかしながら、有限幾何やＢＩＢＤに基づいた符号は、上述した様に、その符号語長やパリティ数がごく少数の値に限定されている。このため、この符号を実際のシステムに応用しようとした場合、取り扱うデータの符号語長やパリティ数が限定されてしまい、応用しづらいという問題があった。
【００３５】
また、復号後のＢＥＲ向上のためには、符号の最小距離ｄminの向上が有効な手法の１つと考えられるが、これまでに知られている自己直交ＱＣ符号は、多くの場合、ｄmin＝ｗ＋１である。任意の符号語長やパリティ数で、ｄmin≧ｗ＋２となる自己直交ＱＣ符号については、ｗ＝２の場合については、検査行列から６サイクルを取り除く事による符号構成法が知られていたが、ｗ≧３の場合については知られていないという問題があった。その構造上、原理的に６サイクルが含まれるｗ≧３のＱＣ符号について、ｄmin≧ｗ＋２、すなわち上述した（５） 式を成立させる汎用的な手法を見出す事は容易ではなかった。
【００３６】
本発明の目的は、伝送情報のビット誤り率（ＢＥＲ）や未検出誤り確率を低減することにある。
【課題を解決するための手段】
【００３７】
本発明に係るＱＣ符号の符号化方法は、パリティ検査行列が１つあるいは複数の巡回行列によって表される自己直交ＱＣ符号の符号化方法及び復号方法において、列重みｗが３以上であり、かつ符号系列の最小距離がｗ＋２以上となる様に設計された検査行列を満足する符号系列を生成し、検査行列は、ＱＣ符号の周期をｐ、検査行列の行数をｍとし、検査行列を構成するｐ個の巡回行列の構造を表す、要素数ｗのｐ個のアドレス集合から、重複を許して抽出されたｗ＋１個のアドレス集合におけるｊ(０≦ｊ≦ｗ）番目のアドレス集合の、各要素の１つの並べ替えをｂ0,jｂ1,j…ｂw-1,jとした時、２≦ｊ≦ｗ、１≦ｉ＜ｊの範囲内にある１つの［ｉｊ］について、ｂj-1,0−ｂi-1,0＋ｂ0,i−ｂj-1,i＋ｂi,j−ｂ0,j≠０（mod  m)が、全てのｂ0,jｂ1,j…ｂw-1,jについて成り立つものである。
【００３９】
本発明による符号化方法はｗが３以上のＬＤＰＣ符号において、符号化・復号器の回路規模の低減に結びつく符号規則性の付与と、最小距離の拡大による復号性能の向上とを、両立させる事を可能とする。
【発明の効果】
【００４０】
本発明によれば、符号変換を行なう事ができる。特に、その検査行列がｐ個の巡回行列からなる自己直交ＱＣ符号の符号化方法において、任意のｐ、任意の列重み、任意の検査行列の列数において、最小距離の拡張された符号を用いる事ができ、これをＬＤＰＣ符号として用いる事により、復号後のビット誤り率および未検出誤り率を改善する事ができる。従って、本発明の符号化方法を通信システムあるいはストレージシステムに用いる事により、それらシステムの信頼性向上を図る事が可能となり、その工業的価値は大きい。
【発明を実施するための最良の形態】
【００４１】
以下、本発明の実施の形態について説明する。
【００４２】
まず、ＱＣ行列を構成する巡回行列の、本実施例における表現方法について述べる。
【００４３】
今、全ての列重みがｗのｍ×ｍ２値巡回行列において、ｊ番目（０≦ｊ＜ｍ）の列において、ビット１となるｗ個の行アドレスの集合を、Ａjとする。たとえば、Ａ0｛２，３，５｝とすれば、対応するｍ＝７の巡回行列Ｃは、次の様になる。
【００４４】
【数３】
0004591371.tif 000004
このＡjの定義は、ＢＩＢＤにおけるblockの定義と同じである。
【００４５】
この時、４サイクルの無い２値巡回行列において、Ａjの全要素を小さい順に並べた系列ａ0ａ1…ａw-1を考えた時、次の２条件を満たすＡjが必ず只１つ存在する。
【００４６】
ａ0＝０              ・・・（７）
ａ1＜ａi−ａi-1        ・・・（８）
ここで、２≦ｊ≦ｗ，ａw≡ｍであり、（８）式はこの範囲にある全てのｉについて成り立つものとする。たとえば、（６）式の例では、Ａ5＝｛０，１，３｝のみが、（７）式、（８）式を満たす。ただし 、（８）式には、巡回行列が４サイクルを含まないための条件の一部であるａ1≠ａi−ａi-1の条件が含まれている。
【００４７】
本実施の形態においては、（７）式、（８）式を満たすＡjを起点行アドレス集合ＢＡＳ(base address set) と呼び、巡回行列において行や列を巡回シフトさせた巡回行列は元の巡回行列と等価な巡回行列と見なす事にする。この時、１つのＢＡＳによって、独立した１つの巡回行列、すなわちｍ個の等価な巡回行列を代表させる事ができる。また同様に、相異なるｐ個のＢＡＳによって、独立したｐ個の巡回行列から構成されるｍ×（ｍ・ｐ）ＱＣ行列を代表させる事ができる。本発明に用いられるＱＣ行列は、（４）式に従って表現できるものとする。
【００４８】
次に、本実施の形態に用いられるＱＣ符号を自己直交符号とする、すなわち検査行列から４サイクルを取り除くための、ｐ個のＢＡＳの条件について述べる。
【００４９】
ＱＣ符号の検査行列に限らない任意のｍ×ｎ検査行列から、任意の２個の列を抽出した ｍ×２部分行列 (sub matrix) を考える。そして、そのｍ×２部分行列から更に任意の２列を抽出した２×２部分行列を考える。ｍ×ｎ検査行列が４サイクルを含むのは、全ての要素が１となる２×２部分行列が少なくとも１つ存在する時である。従って、４サイクルの無い検査行列を得るには、ｍ×ｎ検査行列から任意に抽出された全ての２×２部分行列において、全ての要素が１となるものが１つも存在しない検査行列を設計すれば良い。
【００５０】
本発明者の検討によれば、検査行列のＱＣ構造を利用すれば、その様な検査行列を、以下の様に任意のｗについて効率的に設計する事ができる。
【００５１】
今、ＱＣ符号の検査行列を定義するｐ個のＢＡＳ Ｓ0，Ｓ1，…，Ｓp-1から、重複を許して抽出された任意のｒ（１≦ｒ）個のＢＡＳを、Ｔ0，Ｔ1，…，Ｔr-1とする。ここで、Ｔj≡｛ａ0,j，ａ1,j，…，ａw-1,j｝（ａ0,j＝０、０≦ｊ＜ｒ）とする。
【００５２】
この時、ＱＣ符号の検査行列において４サイクルが発生しない条件は、Ｓ0，Ｓ1，…，Ｓp-1から重複を許して抽出された任意の２個のＢＡＳ Ｔ0，Ｔ1について、次式が成立する事である。
【００５３】
ａi0,0−ａi1,0＋ａi2,1−ａi3,1≠０  （mod m)        ・・・（９）
ここで、Ｔ0≠Ｔ1の時は、１≦ｉ0＜ｗ、０≦ｉ1＜ｉ0、０≦ｉ2＜ｗ、０≦ｉ3＜ｗ（ｉ3≠ｉ2）、Ｔ0＝Ｔ1の時は、２≦ｉ0＜ｗ、０≦ｉ1＜ｉ0、ｉ0≦ｉ2＜ｗ、（ｉ1≦ｉ3＜ｉ0）＆（ｉ2＜ｉ3＜ｗ）であり、（９）式はこれらの範囲内にある全ての整数ｉ0，ｉ1，ｉ2，ｉ3について成り立つ必要がある。
【００５４】
Ｔ0≠Ｔ1の時、あるＴ0，Ｔ1において、（９）式の総評価回数の最大値は、次のｎ0回となる。
【００５５】
【数４】
0004591371.tif 000005
たとえば、ｗ＝２の時ｎ0＝２、ｗ＝３の時ｎ0＝１８、ｗ＝４の時ｎ0＝７２である。
【００５６】
Ｔ0＝Ｔ1の時、すなわちＴ0，Ｔ1が１つのＢＡＳから構成される場合、（９）式の総評価回数の最大値は、次のｎ1回となる。
【００５７】
【数５】
0004591371.tif 000006
たとえば、ｗ＝２の時ｎ1＝０、ｗ＝３の時ｎ1＝３、ｗ＝４の時ｎ1＝１４である。ただしここで、あるＴ0，Ｔ1において、（９）式をｎ0あるいはｎ1通りの全てについて調べなければならないのは、そのＴ0，Ｔ1が（９）式を満たす時だけである。
【００５８】
（９）式を満たさないＴ0，Ｔ1が１つでもあれば、そのＴ0，Ｔ1を発生するＢＡＳの組み合わせは、本発明の検査行列を表すｐ個のＢＡＳには用いない。Ｔ0，Ｔ1が（９）式を満たす限り、（９）式は、ｐ個のＢＡＳから抽出できる全てのＴ0，Ｔ1について、順次評価される必要がある。ｐ個のＢＡＳから重複を許して２個のＢＡＳ Ｔ0，Ｔ1を抽出する組み合わせの数ｎ2は、次式で計算できる。
【００５９】
【数６】
0004591371.tif 000007
たとえば、ｐ＝２１の場合、ｎ2＝２３１である。ただし、（９）式をこのｎ2通り全てについて調べなければならないのは、ｐ個のＢＡＳから重複を許して抽出された、全てのＴ0，Ｔ1が（９）式を満たす時だけである。
【００６０】
以下、本発明に用いられるｐ個のＢＡＳは（９）式を満たす、すなわち本発明に用いられるＱＣ符号は自己直交符号であるものとする。
【００６１】
次に、本発明に用いられる自己直交ＱＣ符号の最小距離を、ｗ＋２以上とするためのｐ個のＢＡＳの条件について述べる。
【００６２】
今、ＱＣ符号の検査行列に限らないｍ×ｎ検査行列から、任意のｗ＋１個の列を抽出したｍ×（ｗ＋１）部分行列を考える。この部分行列を検査行列の一部とする符号の最小距離がｗ＋１となるのは、ｍ×（ｗ＋１）部分行列の各行における１の総和のmodulo2 が全て０となる時である。ただし、ｍ×（ｗ＋１）部分行列の各行における１の総和のmodulo2が全て０である時に、各行における１の総和が１行でも４以上となる場合は、この部分行列における４サイクルの発生、すなわちその符号が自己直交でない事を意味する。従って、自己直交符号の最小距離がｗ＋１となる時には、その検査行列の１部である、あるｍ×（ｗ＋１）部分行列において全０の行を取り除いた際、各行における１の総和が全て２となるｕ×（ｗ＋１）部分行列が存在する。ここで、ｕは、次式で表される。
【００６３】
【数７】
0004591371.tif 000008
たとえば、ｗ＝２の時ｕ＝３、ｗ＝３の時ｕ＝６、ｗ＝４の時ｕ＝１０である。
【００６４】
図２は、この様な、各行における１の総和が全て２となるｕ×（ｗ＋１）部分行列の、ｗ≦４の場合における一例である。
【００６５】
図２においては、ｕ×（ｗ＋１）部分行列の各行における１の総和が全て２、すなわち各行における１の総和のmodulo2 が全て０となっており、この様な部分行列を検査行列の一部とする自己直交符号の最小距離はｗ＋１となる。
【００６６】
従って、最小距離がｗ＋２以上となる自己直交符号を得るためには、ｍ×ｎ検査行列から抽出できる全てのｕ×（ｗ＋１）部分行列において、各行における１の総和が全て２となるものが１つも存在しない検査行列を設計すれば良い。本発明者の検討によれば、検査行列のＱＣ構造を利用すれば、その様な検査行列を、以下の様に任意のｗについて効率的に設計する事ができる。
【００６７】
ｐ個のＢＡＳ Ｓ0，Ｓ1，…，Ｓp-1から、重複を許して任意に抽出されたｗ＋１個のＢＡＳをＴ0，Ｔ1，…，Ｔwとする。また、Ｔ0，Ｔ1，…，Ｔwの任意の並べ替えをＵ0Ｕ1…Ｕwとおき、Ｕj（０≦ｊ≦ｗ）における各要素の並べ替えをｂ0,jｂ1,j…ｂw-1,jとおく。ただし、Ｕx＝Ｕy（１≦ｘ≦ｗ、０≦ｙ＜ｘ）の時は、ｂx,y≠ｂx-1,yである。
【００６８】
この時、Ｓ0，Ｓ1，…，Ｓp-1から求められる全てのＵ0Ｕ1…Ｕwの、各要素の全ての並べ替えが、（１４）式を満たせば、そのＱＣ符号の最小距離はｗ＋２以上となる。
【００６９】
ｂj-1,0−ｂi-1,0＋ｂ0,i−ｂj-1,i＋ｂi,j−ｂ0,j≠０（mod m）    ・・・（１４）
ここで、２≦ｊ≦ｗ、１≦ｉ＜ｊであり、（１４）式は各Ｕ0Ｕ1…Ｕwの、各要素のある１つの並べ替えにおいて、ある１つの［ｉｊ］について満たされれば良い。ただしここで、Ｔ0，Ｔ1，…，Ｔwの内のいずれか１つのＢＡＳは、ＢＡＳ同士の並べ替えおよびその要素の並べ替えを、共に考慮しなくても良い。たとえば（１４）式の計算において、Ｔ0のみはこれら並べ替えの内、任意の１つだけを用いれば良く、他のＴ1，Ｔ2，…，Ｔwについては、これら全ての並べ替えについて調べる必要がある。ただしここで、仮に、Ｔ0，Ｔ1，…，Ｔwの全ての並べ変えについて、（１４）式を評価したとしても、それは重複した評価が生じて計算時間が長くなるだけで、本発明に用いられる符号の性能には何ら影響を与えない。ここでは、以下、Ｔ0のみ並べ替えを考慮しない事とする。ただしここで、仮にＢＡＳ同士の並べ替えを考慮しないで、たとえば常にＵ0＝Ｔ0，Ｕ1＝Ｔ1，…，Ｕw＝Ｔwとしておいて、全てのＢＡＳについて、各要素の並べ替えを考慮する手法は、本実施の形態の手法と本質的に同じである。
【００７０】
（１４）式の総評価回数の最大値は、ある１つの並べ替えＵ0Ｕ1…Ｕwの、各要素のある１つの並べ替えについて、次のｎ3回となる。
【００７１】
【数８】
0004591371.tif 000009
たとえば、ｗ＝２の時ｎ3＝１、ｗ＝３の時ｎ3＝３、ｗ＝４の時ｎ3＝６である。ただし （１４）式を、ある１つの並べ替えＵ0Ｕ1…Ｕwの、各要素のある１つの並べ替えについて、ｎ3通りの全てを調べなければならないのは、その並べ替えが （１４） 式を満たさない時だけである。
【００７２】
（１４）式を満たさないＵ0Ｕ1…Ｕwが１つでもあれば、その並べ替えを発生するＢＡＳの組み合わせは、本発明の検査行列を表すｐ個のＢＡＳには用いない。Ｕ0Ｕ1…Ｕwが（１４）式を満たす限り、（１４）式は、Ｕ0Ｕ1…Ｕwの各要素の所定の並べ替え（最大(ｗ！)w通り）、およびＴ1，Ｔ2，…，Ｔwの全ての並べ替え（最大ｗ！通り）について、順次評価される必要がある。すなわち、ある１つの組み合わせＴ1，Ｔ2，…，Ｔwについて、（１４）式の総評価回数の最大値は、次のｎ4回となる。
【００７３】
ｎ4＝(ｗ！)w+1            ・・・（１６）
たとえば、ｗ＝２の時ｎ4＝８、ｗ＝３の時ｎ4＝１２９６、ｗ＝４の時ｎ4＝７９６２６２４である。ただし、（１４）式をｎ4通り全てについて調べなければならないのは、Ｔ0，Ｔ1，…，Ｔwが全て異なり、かつその全ての並べ替えＵ0Ｕ1…Ｕwが（１４）式を満たす時だけである。
【００７４】
また、ｐ個のＢＡＳからｗ＋１個までの重複を許してｗ＋１個のＢＡＳ Ｔ1，Ｔ2，…，Ｔwを抽出する組み合わせの数ｎ5は、次式で計算できる。
【００７５】
【数９】
0004591371.tif 000010
たとえば、ｐ＝２１の場合、ｗ＝２の時ｎ5＝１７７１、ｗ＝３の時ｎ5＝１０６２６、ｗ＝４の時ｎ5＝５３１３０である。ただし、（１４） 式をｎ5通り全てについて調べなければならないのは、ｐ個のＢＡＳから重複を許して抽出された、全てのＴ0，Ｔ1，…，Ｔwが（１４）式を満たす時だけである。
【００７６】
ここで、抽出されたｗ＋１個のＢＡＳが全て同じ場合、すなわち、Ｔw＝…＝Ｔ1＝Ｔ0＝｛ａ0，ａ1，…，ａw-1｝（ａ0＝０）の場合には、（１４）式を満たすＢＡＳには、より簡略化された必要十分条件が存在する。その条件は、ｍが２w−１の倍数の時に、次の２式が各々、あるｘについて成立する事である。
【００７７】
【数１０】
0004591371.tif 000011
ここで、０≦ｘ＜ｗである。ただし、ｍが２w−１の倍数でない時には（18.1），（18.2）式は常に成り立つので、これを評価する必要はない。上述したｎ5通りの内のｐ通りは、（１４）式の代わりに（18.1），（18.2）式を用いてＢＡＳを評価する事ができる。
【００７８】
（18.1），（18.2）式を満たすＢＡＳの条件式の総数ｎ6は、ｗ＝２の時ｎ6＝１、ｗ≧３の時ｎ6＝２である。
【００７９】
（18.1），（18.2）式を満足する一例として、たとえば、ｗ＝２の時にＢＡＳ ｛０，ａ1｝が満たすべき条件は、ｍが３の倍数の時に、次式が成り立つ事である。
【００８０】
ａ1≠ｍ／３          ・・・（２０）
同様に、ｗ＝３の時にＢＡＳ｛０，ａ1，ａ2｝が満たすべき条件は、ｍが７の倍数のときに、次の２式が同時に成り立つ事である。
【００８１】
【数１１】
0004591371.tif 000012
同様に、ｗ＝４の時にＢＡＳ｛０，ａ1，ａ2，ａ3｝が満たすべき条件は、ｍが１５の倍数のときに、次の２式が同時に成り立つ事である。
【００８２】
【数１２】
0004591371.tif 000013
次に、重複を許したｗ＋１個のＢＡＳ Ｔ0，Ｔ1，…，Ｔwが、（１４）式を満たさない例を２つ述べる。
【００８３】
まず、ｗ＝３の場合に、Ｔ0，Ｔ1，Ｔ2，Ｔ3が全て重複している時に (21.1) 式に違反する、次の例について考える。
【００８４】
Ｔ3＝Ｔ2＝Ｔ1＝Ｔ0＝｛０，m/7，3m/7｝      ・・・（２３）
ここで、Ｔ0，Ｔ1，Ｔ2，Ｔ3は全て同じなので、その並べ替えＵ0Ｕ1Ｕ2Ｕ3の各要素は全て同じである。Ｕ0Ｕ1Ｕ2Ｕ3の各要素の並べ替えの中には、上述した各ＢＡＳが重複した場合の条件ｂy,x≠ｂx-1,y、すなわちｂ0,1≠ｂ0,0、ｂ0,2≠ｂ1,0、ｂ1,2≠ｂ1,1、ｂ0,3≠ｂ2,0、ｂ1,3≠ｂ2,1、ｂ2,3≠ｂ2,2の６条件を全て満たす組み合わせの1つとして、次のものが存在する。
【００８５】
【数１３】
0004591371.tif 000014
（24.1）〜（24.4）式を（１４）式の左辺に代入して、［ｉｊ］が［１２］、［１３］、［２３］の３通りの場合について順次評価すると、次の様に全て０となる。
【００８６】
【数１４】
0004591371.tif 000015
すなわち、（２３）式のＢＡＳは（１４）式に違反する。これは、（２３）式のＢＡＳによって代表される巡回行列を検査行列の１部とする、ｗ＝３のＱＣ符号の最小距離がｗ＝１である事を示している。
【００８７】
次に、ｗ＝３、ｍ＝２５の場合にＴ0，Ｔ1，Ｔ2，Ｔ3が全て異なる、次の例について考える。
【００８８】
Ｔ0＝｛０，１，３｝              ・・・（26.1)
Ｔ1＝｛０，６，１５｝            ・・・（26.2)
Ｔ2＝｛０，５，１７｝            ・・・（26.3）
Ｔ3＝｛０，４，１１｝            ・・・（26.4）
（26.1)〜(26.4) 式において、Ｕ0＝Ｔ0とした時のＵ0Ｕ1Ｕ2Ｕ3の１つとして、次のものがある。
【００８９】
Ｕ0＝｛０，１，３｝              ・・・（27.1)
Ｕ1＝｛０，４，１１｝            ・・・（27.2)
Ｕ2＝｛０，５，１７｝            ・・・（27.3）
Ｕ3＝｛０，６，１５｝            ・・・（27.4）
また、(27.1)〜 (27.4)式において、Ｕ0Ｕ1Ｕ2Ｕ3の各要素の並べ替えの１つとして、次のものが存在する。
【００９０】
［ｂ0,0ｂ1,0ｂ2,0］＝［0 1 3］        ・・・(28.1)
［ｂ0,1ｂ1,1ｂ2,1］＝［11 0 4］       ・・・(28.2)
［ｂ0,2ｂ1,2ｂ2,2］＝［17 5 0］       ・・・(28.3)
［ｂ0,3ｂ1,3ｂ2,3］＝［0 15 6］       ・・・(28.4)
(28.1)〜 (28.4)式を（１４）式の左辺に代入して、［ｉｊ］が［１２］、［１３］、［２３］の３通りの場合について順次評価すると、次の様に全て０となる。
【００９１】
ｂ1,0-ｂ0,0+ｂ0,1-ｂ1,1+ｂ1,2-ｂ0,2＝1-0+11-0+5-17＝0           ・・・(29.1)
ｂ2,0-ｂ0,0+ｂ0,1-ｂ2,1+ｂ1,3-ｂ0,3＝3-0+11-4+15-0＝0 (mod 25)  ・・・(29.2)
ｂ2,0-ｂ1,0+ｂ0,2-ｂ2,2+ｂ2,3-ｂ0,3＝3-1+17-0+6-0＝0  (mod 25)  ・・・(29.3)
すなわち、(26.1)〜(26.4) 式のＢＡＳの組み合わせは（１４）式に違反する。これは、(26.1)〜(26.4) 式のＢＡＳによって代表される５つの巡回行列を検査行列の１部もしくは全てとする、ｗ＝３、ｍ＝２５のＱＣ符号の最小距離がｗ＋１である事を示している。
【００９２】
以下、本発明の符号化方法に用いられるＱＣ符号の検査行列を表すｐ個のＢＡＳは（９）式、（１４）式を満たす、すなわち本発明に用いられるＱＣ符号は最小距離がｗ＋２以上の自己直交符号であるものとする。
【００９３】
ここで、（４）式によって表されるｗ≧３であるＱＣ行列には必ず６サイクルが含まれる事が一般的に知られているが、本発明者の検討によれば、ＱＣ行列における６サイクルの数を最小化する事ができる。本発明に用いられる最小距離がｗ＋２以上の自己直交ＱＣ符号は、復号時のＢＥＲをできるだけ低下させるために、その検査行列における６サイクルの数ができるだけ少なくなっている事が望ましい。本発明者の検討によれば、検査行列のＱＣ構造を利用すれば、その様な検査行列を、以下の様に任意のｗについて効率的に設計する事ができる。
【００９４】
ｐ個のＢＡＳ Ｓ0，Ｓ1，…，Ｓp-1から、重複を許して任意に抽出された３個のＢＡＳをＴ0，Ｔ1，Ｔ2とする。Ｔ0，Ｔ1，Ｔ2の任意の並べ替えをＵ0Ｕ1Ｕ2とおき、Ｕj（０≦ｊ≦２）のｗ個の要素から抽出された２要素の並べ替えをｂ0,jｂ1,jとおく。ただし、Ｕ1＝Ｕ0の時ｂ0,1≠ｂ0,0、Ｕ2＝Ｕ0の時ｂ0,2≠ｂ1,0、Ｕ2＝Ｕ1の時ｂ1,2≠ｂ1,1、かつｂ1,0＞ｂ0,0である。
【００９５】
この時、ＱＣ符号の検査行列に含まれる６サイクルの数を低減させるためには、（１４）式について、ｉ＝１、ｊ＝２の場合のみ評価すれば良い。すなわち、あるＵ0Ｕ1Ｕ2について次の１式を、できるだけ満たす様にすれば良い。
【００９６】
ｂ1,0−ｂ0,0＋ｂ0,1−ｂ1,1＋ｂ1,2−ｂ0,2≠０  （mod m)      ・・・（３０）
ただしここで、Ｔ2＝Ｔ1＝Ｔ0の時には、必ず（３０）式に違反するＵ0Ｕ1Ｕ2が存在する事に注意しなければならない。また、ｗ＝２の時には、（３０）式は（１４）式と同じなので、これを重複して調べる必要はない。（３０）式の評価にあたっては、（１４）式の場合と同様に、重複した評価を避けるために、Ｕ0Ｕ1Ｕ2の内の１つ、たとえばＵ0については、ｗ個の要素の中から２要素を抽出した際、その並べ替えについては考慮しなくても良い。
【００９７】
ただしここで、仮にＢＡＳ同士の並べ替えを考慮しないで、たとえば常にＵ0＝Ｔ0，Ｕ1＝Ｔ1，Ｕ2＝Ｔ2としておいて、全てのＢＡＳについて、各要素の並べ替えを考慮する手法は、本実施の形態の手法と本質的に同じである。
【００９８】
ある１つの組み合わせＴ0，Ｔ1，Ｔ2について、（３０）式の総評価回数の最大値は、次のｎ7回となる。
【００９９】
【数１５】
0004591371.tif 000016
たとえば、ｗ＝３の時ｎ7＝１０８、ｗ＝４の時ｎ7＝８６４である。ただし、（３０）式をｎ7通り全てについて調べなければならないのは、Ｔ0，Ｔ1，Ｔ2が全て異なる時だけである。
【０１００】
ここで、上述した様に、Ｔ2＝Ｔ1＝Ｔ0＝｛ａ0，ａ1，ａ2｝の時、すなわちＴ0，Ｔ1，Ｔ2が１つのＢＡＳから構成される場合には、必ず（３０）式に違反するｂ0,jｂ1,jの組み合わせが複数存在する。たとえば、その１つが、ｂ0,1≠ｂ0,0、ｂ0,2≠ｂ1,0、ｂ1,2≠ｂ1,1を満たす次の条件である。
【０１０１】
［ｂ0,0ｂ1,0］＝［ａ0ａ1］        ・・・(32.1)
［ｂ0,1ｂ1,1］＝［ａ2ａ1］        ・・・(32.2)
［ｂ0,2ｂ1,2］＝［ａ2ａ0］        ・・・(32.3)
（３２）式を（３０）式の左辺に代入すると、次の様に０となる。
【０１０２】
ｂ1,0−ｂ0,0＋ｂ0,1−ｂ1,1＋ｂ1,2−ｂ0,2
＝ａ1−ａ0−ａ2−ａ1＋ａ0−ａ2＝０      ・・・（３３）
この様に、任意の｛ａ0，ａ1，ａ2｝が（３０）式に違反する事は、ｗ≧３の時に、任意の巡回行列に６サイクルが含まれる事を表している。この様なケースを除外して、Ｔ2＝Ｔ1＝Ｔ0＝｛ａ0，ａ1，…，ａw-1｝（ａ0＝０）の時に、（３０）式をＵ0Ｕ1Ｕ2について全て評価するためには、次式を用いる事ができる。
【０１０３】
ａi0−ａi1＋ａi2−ａi3＋ａi4−ａi5≠０（mod m)      ・・・（３４）
ここで、
【０１０４】
【数１６】
0004591371.tif 000017
であり、（３４）式はこの範囲内にある全ての整数ｉ0，ｉ1，ｉ2，ｉ3，ｉ4，ｉ5について満足される必要がある。ただし、ｗ＝２の時には、（３４）式は（２０）式と同じなので、これを重複して調べる必要はない。
【０１０５】
（３４）式の総評価回数の最大値は、次のｎ8回となる。
【０１０６】
【数１７】
0004591371.tif 000018
たとえば、ｗ＝３の時ｎ8＝９、ｗ＝４の時ｎ8＝４６である。ただし、（３４）式をｎ8通り全てについて調べなければならないのは、そのＢＡＳが（３４）式を満たす時だけである。
【０１０７】
本発明の符号化方法に用いられるｐ個のＢＡＳは、（３０）式や（３４）式を必ず満たさなければならないものではなく、それができるだけ満たされていれば良い。本発明者の検討によれば、ｐ個のＢＡＳを、Ｔ2＝Ｔ1＝Ｔ0の場合に（３４）式を、それ以外の場合に（３０）式を、各々必ず満たす様に設計すると、達成できるｐの最大値が、（３０）式、（３４）式を満たさない場合と比べて小さくなる。一方で、ｐ個のＢＡＳを、Ｔ2＝Ｔ1＝Ｔ0の場合にのみ（３４）式を満たす様に設計すると、ｍの値がある程度大きければ、達成できるｐの最大値を劣化させる事は少ない。従って本発明の符号化方法に用いられるｐ個のＢＡＳの各々は、特に（３４）式を満たしている事が望ましい。
【０１０８】
ただしここで、本発明者の検討によれば、ｗ＝４の時には、（９）式、（１８）式、（３４）式を満たすＢＡＳから構成され、かつ（９）式を満たすｐ個のＢＡＳは、必ず （１４）式を満たす。この事を利用すれば、ｗ＝４の時には、（１４）式の評価を実質的に省略する事もできる。
【０１０９】
以上の様なｐ個のＢＡＳは、（９）式、（１４）式を満たす限り、どの様な手順を用いて設計されても良いが、以下にその１つの方法について述べる。
【０１１０】
図３は、本発明の符号化方法に用いられるｐ個の巡回行列によって表されるＱＣ符号の検査行列を設計するための手順を表す、フローチャートの一例である。図３では、まず、ステップ１において、（９）式、（１８）式を満たす全てのＢＡＳを求める。ステップ１においては、（３４）式を同時に満たす様にしても良い。次に、ステップ２において、ステップ１で求められたＢＡＳの中から、（９）式、（１４）式を満たすｐ個のＢＡＳを選択する。このステップ２においては、Ｔ2＝Ｔ1＝Ｔ0の場合を除いて（３０）式を同時に満たす様にしても良い。
【０１１１】
ここで Steiner 限界式を表す（２）式において、ｎ＝ｍ・ｐと置くと、ｍ≠０より次式が得られる。
【０１１２】
【数１８】
0004591371.tif 000019
図３のアルゴリズムにおいてｐ個のＢＡＳが求められる可能性があるかどうかは、設定されたｗ，ｍ，ｐが（３６）式を満たすかどうかによって判断する事ができる。ただし、ＱＣ符号においてｐ＝１の時、すなわちＢＡＳによって定義される単一の巡回行列を検査行列とする巡回符号が構成できるのは、符号のパリティ数がｍよりも小さい場合だけである。符号のパリティ数は、検査行列に対してごく一般的なガウス消去法 (Gaussian elimination) を適用した際の、検査行列のrankとして求める事ができる。
【０１１３】
（３６）式が満たされている場合、図３のアルゴリズムに従って求められるｐ個のＢＡＳの組み合わせは、与えられたｗ，ｍにおいて、通常、複数存在する。ｗ，ｍ，ｐの各値がある程度小さい時、これらｐ個のＢＡＳの組み合わせの全てを全検索法によって求める事が可能である。
【０１１４】
図４は、図３のアルゴリズムに従って、ｗ＝３、ｐ≦６の場合において、ｍ、ｐ、符号語長 ｎ、（９）式、（１８）式を満たすＢＡＳの数Ｎc、（９）式、（１８）式のみを満たすｐ個のＢＡＳの組み合わせの数Ｎo、（９）式、（１４）式を満たすｐ個のＢＡＳの組み合わせの数Ｎeを、各々全検索法によって調べた結果を表す表である。ここで、Ｎoは最小距離ｗ＋１以上の自己直交ＱＣ符号の数と等しく、Ｎeは本発明に用いられる最小距離ｗ＋２以上の自己直交ＱＣ符号の数と等しい。
【０１１５】
図５は、図３のアルゴリズムに従って、ｗ＝４、ｐ≦４の場合において、図４と同様に ｍ，ｐ,ｎ,Ｎc,Ｎo,Ｎeを、各々全検索法によって調べた結果を表す表である。
【０１１６】
図４及び図５の計算においては、まず与えられたｗ，ｐについて（３６）式が成り立つ最小のｍ、すなわちｗ＝３の時にはｍ＝６ｐ＋１、ｗ＝４の時にはｍ＝１２ｐ＋１となるｍについて各々調べ、Ｎe＞０となった場合にはｐを、Ｎe＝０となった場合にはｍを、各々インクリメントした。
【０１１７】
図３、図４及び図５を見ても分かる様に、本発明の実施例において述べられたＱＣ符号の検査行列設計方法は、従来の有限幾何符号やＢＩＢＤに基づいた符号の場合と異なり、任意のｗ，ｍ，ｐに適用する事ができる。
【０１１８】
ただし、図４及び図５の様に、所望のＢＡＳの組み合わせの全てを全検索によって求める事は、ｗ，ｍ，ｐの各値がある程度大きくなると所要計算時間が非常に長くなり、非現実的となる。しかしながら、実用上は、所望の検査行列を只１つ求めれば良いので、検査行列の設計に際しては、必ずしも全検索法を行なう必要は無く、部分検索法を用いれば十分である。実用的な部分検索方法としては、たとえば、木検索法とランダムな検索法とを組み合わせた方法などが考えられる。
【０１１９】
次に、従来から知られている自己直交ＱＣ符号である、type-II 有限幾何符号と、図３のアルゴリズムに従って設計された検査行列を用いた、本発明の符号化方法に用いられる符号との性能を比較してみる事にする。
【０１２０】
比較例１として、上述した非特許文献３に従って射影幾何ＰＧ(6, 21) に基づいて設計された、ｗ＝３、ｍ＝１２７の(2667, 2547) 符号を用いた。また、比較例２として、同様に非特許文献３に従ってユークリッド幾何ＥＧ(4, 22) に基づいて設計された、ｗ＝４,ｍ＝２５５の (5355, 5121) 符号を用いた。比較例１、２共に、非特許文献３において、type-II 有限幾何符号に分類されているｐ＝２１の自己直交ＱＣ符号である。
【０１２１】
ここで、有限幾何を基に設計された符号の検査行列は、一般的にincidence vectorと呼ばれるベクトルを用いて表現されるが、本発明の実施例において定義されたＢＡＳを用いても、本発明の実施例の場合と同様に表現される事が可能である。
【０１２２】
図６は、２つの比較例に用いられた、２１個のＢＡＳである。この図６の各ＢＡＳの組み合わせは、（９）式を満たしているが、（１４）式は満たしていない。
【０１２３】
実施例１および実施例２として、比較例１および比較例２の各々と全く同じｗ，ｍ，ｐを有する符号を、図３のアルゴリズムに従って設計した。これら実施例はいずれも、図３のステップ１において、各ＢＡＳが（９）式、（１８）式、（３４）式を満足する様に、かつ図３のステップ２において、２１個のＢＡＳが（９）式、（１４）式を満足する様に、部分検索法を用いて求めた。この場合、本発明の符号化方法に用いる事のできる符号は、各ｗについて複数存在するが、本実施例では、それらの中の１つを適当に選んだ。
【０１２４】
図７は、本発明の２つの実施例に用いられた、２１個のＢＡＳである。  
これら実施例および比較例の各符号はいずれも、符号長も現実的で、かつ与えられたｗ，ｍにおいて（３６）式を満たす最大のｐを有した、符号化率の非常に高いＱＣ符号であり、実用上の有用性が高いと言って良い符号の一部である。
【０１２５】
本発明の実施例の様に、（３６）式を満たす最大のｐを有する様にｐ個のＢＡＳが選ばれている場合、たとえば現実のシステムにおいて符号化率が低くても良い場合には、単純に、選択されたｐ個のＢＡＳの一部を検査行列に用いなければ良い。
【０１２６】
図８は、本発明の実施例及び比較例に用いられたｐ＝２１の各ＱＣ符号について、それらの符号パラメータ、すなわちｗ，ｍ，ｎ、パリティ数 (= rank)、および符号化率Ｒの各値をまとめた表である。
【０１２７】
本発明者が検討した限りでは、図３のアルゴリズムに従って設計されたＱＣ符号のパリティ数は、ｐ≧２の場合、ｗ＝３の時ｍと、ｗ＝４の時ｍ−１と、各々等しく、図８の実施例もこれに順じている。
【０１２８】
ここで、本発明の実施例および比較例について、ＢＥＲの評価を行なった。図６及び図７に示された各ＱＣ符号の符号化器を用い、ランダムデータを符号化して、{−1, 1} を要素とする信号系列に変換し、分散値σ2の白色ガウス雑音 (additive white Gaussian noise) を加えた後、ごく一般的なSum-Product復号法を用いた繰り返し復号を行ない、ＢＥＲを計測した。ここで、繰り返し復号回数は最大２０回とし、全ての計測点において１００個の誤り符号語を発生させた。信号エネルギー対雑音比は、符号化率Ｒを用いてＥb／Ｎo≡−１０log10（２Ｒ・σ2）と定義した。
【０１２９】
図９は、本発明の実施例および比較例における、ＢＥＲのＥb／Ｎo依存性である。図９を見て分かる様に、本発明の実施例は、比較例と比較して、特に高いＥb／Ｎoにおいて、ＢＥＲの低下、すなわちエラーフロアの改善が見られる。たとえば、図９において、Ｅb／Ｎo＝５．４９ｄＢにおけるＢＥＲは、比較例１が３．２×１０-5、実施例１が１．４×１０-5、比較例２が２．４×１０-6、実施例２が １．６×１０-7という結果であった。
【０１３０】
図１０は、図９のシミュレーション時に誤りを起こした１００符号語の内、未検出誤りを起こした符号語の数の、Ｅb／Ｎo依存性である。ここで未検出誤りとは、誤りを起こした符号語が他の符号語となってしまい、検査行列を満たしてしまう符号語誤りの事である。
【０１３１】
図１０を見て分かる様に、本発明の実施例は、比較例と比較して、特に高いＥb／Ｎoにおいて、未検出誤り率の大幅な改善が見られる。ここでの未検出誤り率は、図１０の縦軸である未検出誤り個数を、誤り符号語数１００で割った値とする。たとえば、図１０において、Ｅb／Ｎo＝５．４９ｄＢにおける未検出誤り率は、比較例１が９９％、実施例１が２％、比較例２が８８％、実施例２が０％という結果であった。
【０１３２】
未検出誤り率が改善されると、復号後に、その符号語が誤りであったかどうかを判定できるため、実システムにおいて再生信号の再送信要求を行なうなどの手法により、その信頼度を向上させる事ができる。
【０１３３】
本発明の実施例における、図９のＢＥＲ改善および図１０の未検出誤り率の改善は、符号の最小距離が改善された事に起因するものである。
【０１３４】
本発明者の検討によれば、本発明の符号化方法に用いられる自己直交ＱＣ符号の最小距離は、ｗ＋２以上であるが、ｗが奇数の時はｗ＋３以上となる。
【０１３５】
そこで、実施例および比較例に用いた各符号の最小距離を以下見積もってみる。図９のシミュレーションにおいて、未検出誤りが起こった時に１符号語内で発生したビット誤りの数は、比較例１が４以上２２以下、比較例２が５以上１６以下、そして実施例１が６以上１０以下という結果であった。この結果より、符号の最小距離は、比較例１が４以下、比較例２が５以下、そして実施例１が６以下という事が分かる。
【０１３６】
ただしここで、自己直交符号の最小距離は必ずｗ＋１以上である事、および本発明の実施例１についてはｗが奇数である事を考慮すれば、符号の最小距離は、比較例１が４、比較例２が５、そして実施例１が６と確定できる。実施例２については、シミュレーション中に未検出誤りが１度も発生しなかったので、最小距離の確定はできなかった。実施例２の符号の最小距離は、小さくとも６である。
【０１３７】
実施例１及び実施例２については、（３０）式は満たしていないが、ここで本発明の実施例として、Ｔ2＝Ｔ1＝Ｔ0の場合を除いて（３０）式も満たす例を１つ挙げておく。
【０１３８】
すなわち、本発明の実施例３は、ｗ＝３、ｍ＝１２８，ｐ＝４の時、（９）式、（１４）式、（３０）式、（３４）式を全て満たす４つのＢＡＳ Ｓ0Ｓ1Ｓ2Ｓ3の１つの、次式である。
【０１３９】
Ｓ0＝｛０，５，２９｝            ・・・(37.1)
Ｓ1＝｛０，１１，６１｝          ・・・(37.2)
Ｓ2＝｛０，２０，７７｝          ・・・(37.3)
Ｓ3＝｛０，２３，５９｝          ・・・(37.4)
ここで、本発明の符号化方法が任意のｍについて実行できる事を示すために、ｍの値は実施例１及び２の場合のｍ＝１２７と異なる、ｍ＝１２８を用いた。ｍ＝１２８の符号は、有限幾何を用いて構成する事は不可能である。
【０１４０】
以上の説明より明らかな様に、本発明の符号化方法に用いられる自己直交ＱＣ符号の検査行列設計方法は、任意のｗ，ｍ，ｐに対して適用する事ができ、しかもこの検査行列を満足する符号は、従来の自己直交ＱＣ符号よりも、そのＢＥＲと未検出誤り率とを同時に改善する事ができる。
【産業上の利用可能性】
【０１４１】
本発明は、ＢＥＲおよび未検出誤り率を同時に改善できるものであり、各種通信装置に使用される符号の符号化器に適用できる。
【図面の簡単な説明】
【０１４２】
【図１】一般的な記録再生装置もしくは通信装置を示すブロック図である。
【図２】各行における１の総和が全て２となるｕ×（ｗ＋１）部分行列の、ｗ≦４ の場合における一例を示す図である。
【図３】本発明の符号化方法に用いられるｐ個の巡回行列によって表されるＱＣ符号の検査行列を設計するための手順の一例を示すフローチャートである。
【図４】図３のアルゴリズムに従って、ｗ＝３、ｐ≦６の場合において、ｍ，ｐ、符号語長ｎ、（９）式、（１８）式を満たすＢＡＳの数Ｎc、（９）式、（１８）式のみを満たすｐ個のＢＡＳの組み合わせの数Ｎo、（９）式、（１４）式を満たすｐ個のＢＡＳの組み合わせの数Ｎeを、各々全検索法によって調べた結果を示す図である。
【図５】図３のアルゴリズムに従って、ｗ＝４、ｐ≦４の場合において、図４と同様にｍ,ｐ,ｎ,Ｎc,Ｎo,Ｎeを、各々全検索法によって調べた結果を示す図である。
【図６】２つの比較例に用いられた、２１個のＢＡＳを示す図である。
【図７】本発明の２つの実施例である、部分探索法によって求められた２１個のＢＡＳを示す図である。
【図８】本発明の実施例及び比較例に用いられたｐ＝２１のＱＣ符号について、それらの符号パラメータ、すなわちｗ，ｍ，ｎ、パリティ数 (= rank)、および符号化率Ｒの各値をまとめて示した図である。
【図９】本発明の実施例および比較例における、ＢＥＲのＥb／Ｎo依存性を説明するための図である。
【図１０】本発明の実施例および比較例において、誤りを起こした１００符号語の内、未検出誤りを起こした符号語の数のＥb／Ｎo依存性を説明するための図である。
【符号の説明】
【０１４３】
１・・・符号化部、２・・・記録部、送信部、３・・・再生部、受信部、４・・・Ａ／Ｄ変換部、５・・・符号検出部、６・・・復号部
【図１】
0004591371.tif 000021
【図２】
0004591371.tif 000022
【図３】
0004591371.tif 000023
【図４】
0004591371.tif 000024
【図５】
0004591371.tif 000025
【図６】
0004591371.tif 000026
【図７】
0004591371.tif 000027
【図８】
0004591371.tif 000028
【図９】
0004591371.tif 000029
【図１０】
0004591371.tif 000030