(57)【特許請求の範囲】
【請求項１】
符号長が等しく符号化率が異なる複数のＬＤＰＣ符号の符号化を行う誤り訂正符号化方法において、
前記複数のＬＤＰＣ符号のうち第１の符号化率に対応する第１のＬＤＰＣ符号とは異なる符号化率に対応するＬＤＰＣ符号の符号化を行う際に、前記第１のＬＤＰＣ符号の符号化を行うための第１の符号化行列または前記第１の符号化行列の部分行列に基づいて生成され、前記第１のＬＤＰＣ符号と符号長が等しく符号化率が異なるＬＤＰＣ符号の符号化を行うための符号化行列に基づいて、符号化を行う符号化工程を備え、
前記第１のＬＤＰＣ符号の符号化を行うための符号化行列は、下三角の構造を有し、
前記符号化工程は、前記第１のＬＤＰＣ符号と符号長が等しく、前記第１のＬＤＰＣ符号よりも符号化率が小さい第２のＬＤＰＣ符号の符号化を行うための第２の符号化行列を生成する符号化行列生成工程を含み、
前記符号化行列生成工程は、
前記第１のＬＤＰＣ符号の第１のパリティ検査行列を下三角化して前記第１の符号化行列を生成する第１の下三角化工程と、
前記第１の下三角化工程の際に行われた列交換を、前記第１のパリティ検査行列に施し、第２のパリティ検査行列を生成する第１の列交換工程と、
前記第１の列交換工程が行われた第２のパリティ検査行列の行数を増加し、前記第２のＬＤＰＣ符号の符号化率に対応した第３のパリティ検査行列を生成する行増加工程と、
前記行増加工程により増加した行を前記第１の符号化行列に付加する行付加工程と、
前記行付加工程により行が付加された第１の符号化行列に対し、付加された行以外が有する下三角構造を壊さずに行列全体を下三角化し、前記第２の符号化行列を生成する第２の下三角化工程と、を含む
ことを特徴とする誤り訂正符号化方法。
【請求項２】
前記符号化行列生成工程は、
前記第２の下三角化工程の際に行われた列交換を前記第２のパリティ検査行列に施して、第４のパリティ検査行列を生成するとともに、前記第２の下三角化工程の際に行われた列交換を前記第３のパリティ検査行列に施して第５のパリティ検査行列を生成する第２の列交換工程を含むことを特徴とする請求項１に記載の誤り訂正符号化方法。
【請求項３】
前記符号化行列生成工程は、
前記複数のＬＤＰＣ符号のうち最も符号化率が大きいＬＤＰＣ符号のパリティ検査行列から順に最も符号化率が小さいＬＤＰＣ符号のパリティ検査行列まで、前記第４のパリティ検査行列を第１のパリティ検査行列として、前記第１の下三角化工程、前記第１の列交換工程、前記行増加工程、前記行付加工程、前記第２の下三角化工程、および前記第２の列交換工程を繰り返し行う繰り返し工程を含むことを特徴とする請求項２に記載の誤り訂正符号化方法。
【請求項４】
前記第１のパリティ検査行列は、前記第１のＬＤＰＣ符号よりも符号化率が小さいパリティ検査行列の部分行列を抜き出して生成されたことを特徴とする請求項１に記載の誤り訂正符号化方法。
【請求項５】
前記行増加工程は、前記第１のＬＤＰＣ符号よりも符号化率が大きいパリティ検査行列の部分行列に新たな行を追加して行を増加することを特徴とする請求項１に記載の誤り訂正符号化方法。
【請求項６】
前記第１のパリティ検査行列は、複数のパリティ検査行列の行を結合して生成されたことを特徴とする請求項１に記載の誤り訂正符号化方法。
【請求項７】
前記行増加工程は、前記第２のパリティ検査行列の行を２つ以上の行に分割する行分割を施して行数を増加することを特徴とする請求項１に記載の誤り訂正符号化方法。
【請求項８】
符号長が等しく符号化率が異なる複数のＬＤＰＣ符号の符号化を行う誤り訂正符号化装置において、
前記複数のＬＤＰＣ符号のうち第１の符号化率に対応する第１のＬＤＰＣ符号とは異なる符号化率に対応するＬＤＰＣ符号の符号化を行う際に、前記第１のＬＤＰＣ符号の符号化を行うための第１の符号化行列または前記第１の符号化行列の部分行列に基づいて生成され、前記第１のＬＤＰＣ符号と符号長が等しく符号化率が異なるＬＤＰＣ符号の符号化を行うための符号化行列に基づいて、符号化を行う符号化手段を備え、
前記符号化手段は、
前記第１のＬＤＰＣ符号に対応した符号化行列に基づく第１の符号化手段と、
前記複数のＬＤＰＣ符号から１つを選択する符号化率選択手段と、
前記符号化行列から、前記符号化率選択手段で選択したＬＤＰＣ符号に対応する部分行列を選択する部分行列選択手段と、
前記部分行列選択手段で選択された部分行列に基づく部分のみを用いて符号化を行う部分行列符号化手段と、を含む
ことを特徴とする誤り訂正符号化装置。
【請求項９】
請求項８に記載の誤り訂正符号化装置を用いた通信システムであって、前記複数のＬＤＰＣ符号を切り換え可能に構成されたことを特徴とする通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、符号長が等しく符号化率が異なる複数のＬＤＰＣ符号を構成する工程または手段を備えた誤り訂正符号化方法および装置ならびにそれを用いた通信システムに関するものである。
【背景技術】
【０００２】
一般に、誤り訂正符号化方法および装置を用いた通信システムにおいては、符号化率が大きいほど通信効率は良いが誤り訂正能力が低く、逆に、符号化率が低いほど通信効率が悪くなるが誤り訂正能力は高くなるので、通信路の状況に合わせて符号化率を設定することが重要となる。なお、符号化率とは、誤り訂正符号の符号長ｎおよび情報系列長ｋを用いて表される値「ｋ／ｎ」（＝１−（行数／列数））である。
【０００３】
上記技術背景に鑑みて、従来から、一部の通信システムにおいては、異なる符号化率の誤り訂正符号を通信システムに搭載し、通信路の状況などに応じて符号化率の切り換え設定を可能にしている。【０００４】
また、従来から、の１つとして、低密度パリティ検査符号（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  ｃｏｄｅ：以下、「ＬＤＰＣ符号」という）が知られている。【０００５】
ＬＤＰＣ符号は、「１」の要素が疎（全要素数に対して少ない割合で存在）のパリティ検査行列で定義される符号であり、パリティ検査行列の列数ｎが符号長となり、行数ｍが検査ビット（パリティビット）数に対応する。【０００６】
パリティ検査行列の列が含む「１」の数をその列における「列重み」と呼び、各列の列重みの値の分布を「列重み分布」と呼ぶ。
列重み分布は、ＬＤＰＣ符号の誤り訂正能力に大きく影響するが、最適な列重み分布は密度発展法などから計算することが可能である。【０００７】
また、同様に、パリティ検査行列の行が含む「１」の数をその行における「行重み」とよぶ。
また、パリティ検査行列は、タナーグラフと呼ばれる２部グラフによって表現することが可能であるが、タナーグラフに含まれる最短ループの長さが大きいほど、ＬＤＰＣ符号のエラーフロアは軽減される。【０００８】
ＬＤＰＣ符号においては、符号化率が異なるとパリティ検査行列も異なり、符号化や復号で行う演算がパリティ検査行列に依存する。
したがって、複数の符号化率のＬＤＰＣ符号を１つの通信システムに搭載する場合には、符号化率ごとに異なる符号化器や復号器を用意しなければならない。【０００９】
このため、従来から、異なる符号化率の複数のＬＤＰＣ符号間で回路を共有して、効率よく通信システムを構成するＲａｔｅ−Ｃｏｍｐａｔｉｂｌｅ  ＬＤＰＣ符号（以下、「ＲＣ−ＬＤＰＣ符号」という）の開発が行われている。
ＲＣ−ＬＤＰＣ符号の設計においては、符号化率の高いＬＤＰＣ符号のパリティ検査行列が、符号化率の低いパリティ検査行列の部分行列と一致するように構成されることが多いが、２種の符号化率の双方で最適な列重み分布とすることは困難である。【００１０】
そこで、まず符号化率の低いパリティ検査行列を用意し、その一部の行を２つの行に分割することで行数を増やし、かつ列を追加することにより、行分割前のパリティ検査行列と行分割後のパリティ検査行列とで、異なる２種の符号化率を切り換え可能とする技術が提案されている（たとえば、特許文献１参照）。【００１１】
上記特許文献１に記載の従来技術においては、追加列を工夫することによって、階段行列の構造（後述する）をパリティ検査行列に持たせておき、可変する符号化率の切り換えに効率的に対応した符号化演算の構成を可能としている。
ただし、この手法では、行を１つ分割する（パリティビットを１ビット増やす）ごとに列重み「２」の列を１つ追加するので、可変する２種の符号化率の間で情報系列長ｋは等しく、符号長は、列を追加した分だけ増加してしまう。【００１２】
ここでは、符号化率切り換えについて説明したが、ＬＤＰＣ符号の別の問題として、パリティ検査行列の構成の難しさがある。
任意の符号長および符号化率で、タナーグラフの最短ループ長が大きいパリティ検査行列を構成することは困難である。【００１３】
したがって、従来では、所望の符号長および符号化率に近い値のＬＤＰＣ符号を構成してから、パディングやパンクチャといった手法を用いて符号化率を調整していた。
なお、パディングとは、送信時に情報ビットの一部を或る決まった値として、情報系列長ｋを小さくする技術である。また、パンクチャとは、送信時にパリティビットの一部を送信しないことにより、パリティビット長を小さくする技術である。【００１４】
しかし、上記手法を適用した場合には、符号長の変化や、誤り訂正能力の大きな劣化が生じることが問題となっている。
また、上記特許文献１による方法によって符号化率を調整することも可能であるが、この場合も符号長が変化してしまう。【００１５】
次に、ＬＤＰＣ符号の符号化法について説明する。
ＬＤＰＣ符号の符号化法はいくつか知られており、下三角行列や階段行列を用いる手法も提案されている（たとえば、非特許文献１参照）。
ここでは、上記非特許文献１に記載の下三角行列を用いた符号化について説明する。
下三角行列とは、ｍ×ｎ行列（ただし、ｍ＜ｎ）の最も右側にあるｍ×ｍ部分行列の対角成分がすべて「１」となり、かつ、対角成分よりも上の行の要素がすべて「０」となる行列である。【００１６】
パリティ検査行列が下三角行列である場合には、情報ビットに基づいて排他的論理和を行うのみでパリティビットを算出可能である。
たとえば、符号語における１番目のパリティビットは、パリティ検査行列の１行目で「１」となっている列に対応する情報ビットに対して、排他的論理和を行えば算出可能である。【００１７】
また、符号語におけるｊ（＞１）番目のパリティビットは、全情報ビットと、１番目からｊ−１番目のパリティビットとのうち、パリティ検査行列のｊ行目において「１」となっている列に対応する上記情報ビットおよびパリティビットに対して、排他的論理和を行えば算出可能である。つまり、１ビット目のパリティビットから１つずつ順番に計算していけば、すべてのパリティビットが算出でき、符号化を行うことが可能である。【００１８】
上記の符号化法を行うためには、パリティ検査行列が下三角行列である必要がある。
ただし、上記非特許文献１に記載されたように、パリティ検査行列の行をベクトルとしたときの行ベクトルが１次独立であれば（つまり、パリティ検査行列の階数と行数とが一致すれば）、パリティ検査行列は、基本行操作と列交換（ガウス消去法）によって下三角行列に変換することが可能である。【００１９】
なお、基本行操作とは、或る行に対して他の行を要素ごとに加算する（排他的論理和を行う）という操作と、２つの行を入れ替える行交換操作とのことであり、列交換とは、２つの列を入れ替える操作のことである。
基本行操作が行われても、ＬＤＰＣ符号の情報ビットと符号語との対応関係は変化しない。つまり、基本行操作によって変形したパリティ検査行列に基づき符号化しても、基本行操作を行う前のパリティ検査行列に基づいて符号化したのと同じ結果となる。一方、列交換が行われると、情報ビットと符号語との対応関係は崩れてしまう。【００２０】
多くの場合、基本行操作を行うとパリティ検査行列の「１」の疎性が失われるので、復号においては、「１」が疎である元のパリティ検査行列を用い、符号化には上記のように生成した下三角行列（以下、「符号化行列」という）を用いる手法がある。【００２１】
上記のように、パリティ検査行列を基本行操作および列交換により下三角化して符号化行列を生成した場合、列交換によって復号用のパリティ検査行列と符号化行列との間の対応関係が崩れてしまうが、この問題を解決するためには、符号化行列の生成過程で行われた列交換と同様の列交換を、復号用のパリティ検査行列に対しても行えばよい。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】ＷＯ２００７／０９１３２７号公報
【非特許文献】
【００２３】
【非特許文献１】和田山正著、「低密度パリティ検査符号とその復号法」トリケップス、２００２年６月５日発行
【発明の概要】
【発明が解決しようとする課題】
【００２４】
従来の可変符号化率に対応したＬＤＰＣ符号生成手段を用いた誤り訂正符号化方法および装置ならびにそれを用いた通信システムは、効率的な符号化方法を構成するために、パリティ検査行列に対して、行のみならず列を追加することにより符号化率を可変設定しているので、符号化率を切り換えた場合に符号長も変化するという課題があった。
また、上記手法を用いてＬＤＰＣ符号の符号化率を調整する際においても、符号長が変化するという課題があった。
【００２５】
この発明は、上記のような課題を解決するためになされたものであり、可変符号化率に対応した効率的な符号化方法または手段により、符号長が一定のまま符号化率を可変にしたＬＤＰＣ符号生成方法を実現して、符号長を変化させずにＬＤＰＣ符号の符号化率を調整可能な誤り訂正符号化方法および装置ならびにそれを用いた通信システムを得ることを目的とする。
【課題を解決するための手段】
【００２６】
この発明に係る誤り訂正符号化方法は、符号長が等しく符号化率が異なる複数のＬＤＰＣ符号の符号化を行う誤り訂正符号化方法において、複数のＬＤＰＣ符号のうち第１の符号化率に対応する第１のＬＤＰＣ符号とは異なる符号化率に対応するＬＤＰＣ符号の符号化を行う際に、第１のＬＤＰＣ符号の符号化を行うための第１の符号化行列または第１の符号化行列の部分行列に基づいて生成され、第１のＬＤＰＣ符号と符号長が等しく符号化率が異なるＬＤＰＣ符号の符号化を行うための符号化行列に基づいて、符号化を行う符号化工程を備え、第１のＬＤＰＣ符号の符号化を行うための符号化行列は、下三角の構造を有し、符号化工程は、第１のＬＤＰＣ符号と符号長が等しく、第１のＬＤＰＣ符号よりも符号化率が小さい第２のＬＤＰＣ符号の符号化を行うための第２の符号化行列を生成する符号化行列生成工程を含み、符号化行列生成工程は、第１のＬＤＰＣ符号の第１のパリティ検査行列を下三角化して第１の符号化行列を生成する第１の下三角化工程と、第１の下三角化工程の際に行われた列交換を、第１のパリティ検査行列に施し、第２のパリティ検査行列を生成する第１の列交換工程と、第１の列交換工程が行われた第２のパリティ検査行列の行数を増加し、第２のＬＤＰＣ符号の符号化率に対応した第３のパリティ検査行列を生成する行増加工程と、行増加工程により増加した行を第１の符号化行列に付加する行付加工程と、行付加工程により行が付加された第１の符号化行列に対し、付加された行以外が有する下三角構造を壊さずに行列全体を下三角化し、第２の符号化行列を生成する第２の下三角化工程と、を含むものである。
【発明の効果】
【００２７】
この発明によれば、可変符号化率に対応した効率的な符号化方法により、符号長が一定のまま符号化率を可変にしたＬＤＰＣ符号生成方法を実現して、符号長を変化させずにＬＤＰＣ符号の符号化率を調整可能にした誤り訂正符号化方法を得ることができる。
【図面の簡単な説明】
【００２８】
【図１】この発明の実施の形態１によるパリティ検査行列の行分割を示す説明図である。（実施例１）
【図２】この発明の実施の形態１による行分割前後のパリティ検査行列を示す説明図である。（実施例１）
【図３】この発明の実施の形態１による符号化行列の生成方法を示すフローチャートである。（実施例１）
【図４】図３内の各ステップで扱う行列を示す説明図である。（実施例１）
【図５】この発明の実施の形態３によりさらに行分割して生成されたパリティ検査行列を示す説明図である。（実施例３）
【図６】この発明の実施の形態３により生成された符号化行列を示す説明図である。（実施例３）
【図７】この発明の実施の形態３による符号化行列の生成方法を示すフローチャートである。（実施例３）
【図８】この発明の実施の形態４に係る通信システムを示すブロック構成図である。（実施例４）
【図９】この発明の実施の形態４による符号化器の内部構成の一例を示すブロック図である。（実施例４）
【図１０】この発明の実施の形態５による符号化器の内部構成の一例を示すブロック図である。（実施例５）
【図１１】この発明の実施の形態６による符号化行列の生成方法を示すフローチャートである。（実施例６）
【発明を実施するための形態】
【００２９】
（実施例１）
以下、図面を参照しながら、この発明の実施の形態１に係る誤り訂正符号化方法（または、装置）について説明する。
なお、この発明の実施の形態１においては、扱うＬＤＰＣ符号を組織符号とし、パリティ検査行列をｍ×ｎ行列としたときに、最も右側のｍ列がパリティビットに対応するものとする。ただし、このパリティビットの対応位置は、便宜的に設定したものであり、これに限らず、列の対応位置を適切に入れ替えても、この発明と同様の構成が適用可能であることは言うまでもない。
【００３０】
また、この発明の実施の形態１においては、パリティ検査行列を下三角化した符号化行列（符号化用検査行列）を用いてＬＤＰＣ符号の符号化を行うものとし、行分割という操作によって、パリティ検査行列の行数を可変して、ＬＤＰＣ符号の符号化率（行数）を可変するものとする。
【００３１】
図１はこの発明の実施の形態１によるパリティ検査行列の行分割を示す説明図である。
図１において、「行分割」とは、パリティ検査行列の１つの行（１点鎖線枠参照）が含む「１」を、新たな２つ以上の行（破線枠参照）に分割して配置し、行数を増加させることによって符号化率を下げる手法である。
【００３２】
図１のように、行分割を行う前と、分割後のパリティ検査行列とを、切り換えて用いることにより、符号化率を可変する。
このとき、行分割の前後において、（１）符号長（＝９）が同一であること、（２）各列の列重み（「１」の数）が同一であること、（３）パリティ検査行列のタナーグラフの内周（ｇｉｒｔｈ）が減少しないこと、が特徴である。特に、後者２つの特徴（２）、（３）は、行分割後においても誤り訂正能力が高いことを示している。
【００３３】
ただし、元のパリティ検査行列が効率的な符号化が可能な構造（下三角行列や階段行列）を有していたとしても、行分割によってその構造は崩れてしまうので、可変符号化率に対応した符号化手法を単純に構成することはできない。
そこで、たとえば前述の特許文献１においては、この問題に対処するために、図１の行分割後に、列を新たに追加していたが、列の追加によって符号化率ごとに異なる符号長となっていた。
【００３４】
これに対し、この発明の実施の形態１は、図１の行分割後であっても、新たな列を追加せずに、効率的に符号化可能な符号化法を実現したものである。
図２はこの発明の実施の形態１における行分割前後のパリティ検査行列を示す説明図である。
【００３５】
図２において、元のパリティ検査行列Ｈ１（上段側参照）は、行数ｍおよび符号長ｎからなる「ｍ×ｎ」行列であり、行分割によってｒ行だけ増やされた分割後のパリティ検査行列Ｈ２（下段側参照）は、行数「ｍ＋ｒ」および符号長ｎからなる「（ｍ＋ｒ）×ｎ」行列である。ここで、増加行数ｒは、増加パリティビット数に相当している。
図２で示すように、行分割の前後において、符号長ｎは同一であり、各列で列重みも同一である。
【００３６】
なお、この発明の実施の形態１においては、１行を何行に分割するかの制限は特にないので、行分割を行う行数のみでなく、１行を何行に分割するかによっても、増加させたい行数ｒ（増加させたいパリティビット数）を設定することが可能である。
【００３７】
また、この発明の実施の形態１に係る誤り訂正符号化方法は、通信システムに適用されるが、その場合、復号に用いるパリティ検査行列とは別に、符号化を行うための符号化行列（後述する）が通信システムに用意されることになる。
【００３８】
また、以下の方法によって符号化行列を生成すれば、１つの符号化行列で複数の符号化率のＬＤＰＣ符号の符号化が可能となる。
さらに、以下の符号化行列を用いた符号化法によれば、行分割によって行列の構造が崩れるという第１の問題と、可変する符号化率ごとに異なる符号長となるという第２の問題と、の両方を解決することができる。
【００３９】
次に、図１および図２とともに、図３および図４を参照しながら、この発明の実施の形態１に係る誤り訂正符号化方法（または、装置）における符号化行列の生成方法について説明する。
図３はこの発明の実施の形態１による符号化行列Ｇ２の生成方法を示すフローチャートであり、図４は図３内の各ステップＳ１〜Ｓ６で扱う行列を示す説明図である。なお、この発明の実施の形態１に係る誤り訂正符号化装置は、各ステップＳ１〜Ｓ６を、それぞれ手段に置き換えることにより実現可能である。
【００４０】
図３、図４において、まず、行分割前のパリティ検査行列Ｈ１に対して基本行操作および列交換を行い、下三角化して、図４のように、符号化行列Ｇ１を生成する（ステップＳ１）。
続いて、行分割前（下三角化の操作を行う前）のパリティ検査行列Ｈ１に対して、ステップＳ１の列交換を行い、パリティ検査行列Ｈ１の列の並び順を、符号化行列Ｇ１の列の並び順と一致させる（ステップＳ２）。
【００４１】
次に、パリティ検査行列Ｈ１を行分割し、パリティ検査行列Ｈ１の行数をｒ行だけ増加させたパリティ検査行列Ｈ２を生成する（ステップＳ３）。
ただし、ステップＳ３の行分割は、行分割後のパリティ検査行列Ｈ２の各行ベクトルが１次独立となるように行われる。この条件を満たせば、分割前のパリティ検査行列Ｈ１の行のうち、どの何行を分割するかに制限はなく、また、１つの行をいくつの行に分割してもよい。
【００４２】
行分割の一例として、分割前のパリティ検査行列Ｈ１の行重みの大きい行を分割し、行分割後におけるパリティ検査行列Ｈ２の行重みの偏りを小さくする方法がある。この方法によれば、多くの場合で、パリティ検査行列Ｈ２の行ベクトルは１次独立となる。
また、行分割の他の例として、行分割後の各行の行重みが、可能な限り「２の累乗」の数になるよう分割する方法もある。この方法によれば、誤り訂正回路のメモリ量や回路規模の削減を計ることが可能となる。
【００４３】
この発明の実施の形態１における行分割は、行分割後の複数の行に、元の行の「１」をどのように配分するかについても制限はなく、行分割後のパリティ検査行列Ｈ２の行ベクトルが１次独立となれば、どのように配分してもよい。
例として、ランダムに配分する方法や、行分割を施す行に属する「１」のうち最も列番号の小さいものから順に１つずつ行分割後の行に順番に配置していく配分の仕方がある。
【００４４】
次に、行分割（ステップＳ３）に続いて、ステップＳ１で生成した符号化行列Ｇ１に対して、ステップＳ３の行分割によって増加したｒ行を、図４のように、符号化行列Ｇ１の最も上の行に付加して、行列Ａを生成する（ステップＳ４）。
【００４５】
ただし、ステップＳ４で付加する行は、以下のように選択される。
たとえば、パリティ検査行列Ｈ１の１つの行のみに行分割を施して、ｑ行に分割した場合、ｑ行のうち任意の１行を除いた「ｑ−１」行を符号化行列Ｇ１に付加する。
また、パリティ検査行列Ｈ１の行のうち、２行以上を行分割した場合も同様に、各行分割で生じた行のうちの任意の１行を除いたすべての行を、それぞれ符号化行列Ｇ１に付加する。
【００４６】
次に、ステップＳ４で生成した行列Ａを下三角化し、行分割後のパリティ検査行列Ｈ２に対応した符号化行列Ｇ２を生成する（ステップＳ５）。
このとき、図４に示すように、行列Ａの下側ｍ行は、符号化行列Ｇ１であって既に下三角化されているので、ステップＳ４で付加した上側ｒ行のみに対して基本行操作を行い、また必要であれば、行列Ａの全体に対して列交換を行う。
【００４７】
上記ステップＳ５で行う行列Ａに対する操作においては、以下の制約を付加する。
まず、基本行操作を行う際、ステップＳ４で付加した行と下側ｍ行との間では、行交換を行わないものとする。つまり、行交換は、ステップＳ４で付加したｒ行の行同士のみで行われる。ただし、ステップＳ４で付加した行に対し、下側ｍ行に属す行を加算する（要素ごとの排他的論理和を行う）操作は、行うものとする。
【００４８】
また、列交換は、行列Ａの右側ｍ列（下側ｍ行が既に下三角化されている列）に対しては行わないものとする。
以上の制限を加えたとしても、パリティ検査行列Ｈ２の各行ベクトルが１次独立であるならば、行列Ａを下三角化することは可能である。
【００４９】
最後に、ステップＳ５の列交換を、パリティ検査行列Ｈ１、Ｈ２に対しても行い、符号化行列Ｇ１、Ｇ２との間で列の対応を合致させたパリティ検査行列Ｈ１’、Ｈ２’を生成し（ステップＳ６）、図３および図４に示した符号化行列Ｇ２の生成処理ルーチンを終了する。
【００５０】
以上の方法で生成された符号化行列Ｇ２の下ｍ行は、行分割前のパリティ検査行列Ｈ１に対応する符号化行列Ｇ１の列を並びかえた行列となっている。
また、符号化行列Ｇ２の各行は、行分割後のパリティ検査行列Ｈ２に対して、基本行操作および列交換して得られる行列なので、符号化行列Ｇ２は、列交換後のパリティ検査行列Ｈ２に対応した符号化行列である。
【００５１】
つまり、この発明の実施の形態１に係る誤り訂正符号化方法を用いた通信システムにおいて、行分割前のＬＤＰＣ符号を用いるのであれば、符号化行列Ｇ２の下ｍ行を用いて符号化を行い、ステップＳ６による列交換後のパリティ検査行列Ｈ１’を用いて復号すればよい。
一方、行分割後のＬＤＰＣ符号を用いる場合には、符号化行列Ｇ２のすべての行を用いて符号化を行い、復号においては、列交換後のパリティ検査行列Ｈ２’を用いれば可能である。
【００５２】
なお、復号演算部（または、復号器）においては、パリティ検査行列Ｈ１、Ｈ２の両方を必ず記憶する必要はなく、いずれか一方のパリティ検査行列と行分割についての情報とがあれば、他方のパリティ検査行列を生成することができる。
この場合、図３、図４内のステップＳ６の列交換は、パリティ検査行列Ｈ１、Ｈ２のいずれか一方（復号演算部で記憶する方）のみに対して行えばよい。
【００５３】
以上のように、この発明の実施の形態１（図１〜図４）に係る誤り訂正符号化方法は、１つのパリティ検査行列Ｈ１に基づいて、一部またはすべての行を２つ以上ごとの行に分割する行分割工程と、任意の符号化率（行数）の複数のＬＤＰＣ符号を構成する符号構成工程とを備えている。
行分割工程は、行分割後のパリティ検査行列Ｈ２の各行に含まれる非ゼロ要素の数が、行によって偏った数とならないように、行分割を行う。
【００５４】
また、行分割工程は、行分割後のパリティ検査行列Ｈ２において、可能な限り多くの行が２の累乗数個の非ゼロ要素を含むように、行分割を行う。
また、行分割工程は、行分割後のパリティ検査行列Ｈ２の各行をベクトルとしてみたときに、ベクトルが１次独立の関係となるように行分割を行う。
【００５５】
また、この発明の実施の形態１に係る誤り訂正符号化方法は、符号長ｎが等しく符号化率「ｋ／ｎ」が異なる複数のＬＤＰＣ符号のそれぞれを符号化する符号化工程（図３、図４）を備えている。
符号化工程は、複数のＬＤＰＣ符号のうち最も符号化率（行数）の大きい最大ＬＤＰＣ符号に対応する符号化行列Ｇ１のみを用意し、最大ＬＤＰＣ符号以外のＬＤＰＣ符号を符号化する際に、最大ＬＤＰＣ符号に対応する符号化行列Ｇ１の部分行列に基づいて符号化を行う。
最大ＬＤＰＣ符号に対応する符号化行列Ｇ１は、下三角の構造を有する。
【００５６】
具体的には、符号化工程は、最大ＬＤＰＣ符号に対応した符号化行列Ｇ１を生成する符号化行列生成工程を含む。
符号化行列生成工程は、複数のＬＤＰＣ符号のうち最も符号化率の小さい最小ＬＤＰＣ符号のパリティ検査行列を下三角化する第１の下三角化工程（ステップＳ１）と、第１の下三角化工程（ステップＳ１）の際に行われた列交換を、複数のＬＤＰＣ符号のパリティ検査行列Ｈ１に施す第１の列交換工程（ステップＳ２）と、を備えている。
【００５７】
また、符号化行列生成工程は、複数のＬＤＰＣ符号のうち既に第１の下三角化が行われた最小ＬＤＰＣ符号の次に符号化率が小さい準最小ＬＤＰＣ符号のパリティ検査行列の一部の行を、第１の下三角化が既に行われた行列の最も上の行から追加する行追加工程（ステップＳ３、Ｓ４）を備えている。
【００５８】
さらに、符号化行列生成工程は、行追加工程（ステップＳ３、Ｓ４）により行が追加された行列Ａに対し、追加された行以外が有する下三角構造を壊さずに行列全体を下三角化する第２の下三角化工程（ステップＳ５）と、第２の下三角化工程（ステップＳ５）の際に行われた列交換を、複数のＬＤＰＣ符号のパリティ検査行列Ｈ１に施す第２の列交換工程（ステップＳ６）と、を備えている。
【００５９】
また、この発明の実施の形態１による符号構成工程は、１つのパリティ検査行列Ｈ１の部分行列を抜き出して、新たなパリティ検査行列を生成することにより、１つのパリティ検査行列のＬＤＰＣ符号よりも符号化率の小さいＬＤＰＣ符号を構成する。
また、符号構成工程は、１つのパリティ検査行列Ｈ１に新たな行を追加して、新たなパリティ検査行列を生成することにより、１つのパリティ検査行列Ｈ１のＬＤＰＣ符号よりも符号化率の大きいＬＤＰＣ符号を構成する。
【００６０】
このように、可変符号化率に対応した効率的な符号化方法により、符号長ｎが一定のまま符号化率を可変にしたＬＤＰＣ符号生成方法を実現し、符号長ｎを変化させずにＬＤＰＣ符号の符号化率を調整可能にした誤り訂正符号化方法を得ることができる。
また、この発明の実施の形態１を通信システムに適用した場合、２種の符号化率のＬＤＰＣ符号に対応した通信システムにおいて、２種の符号化率における符号長を一定とすることができる。
【００６１】
また、２種の符号化率の間で符号化行列を共有することができ、符号化演算の一部を共通化できるので、符号化演算部（または、符号化器）の演算量や記憶領域を軽減し、回路規模を小さくすることができる。
さらに、列重み分布は、２種の符号化率で等しく、行分割前のパリティ検査行列Ｈ１の列重み分布が最適値であれば、２種の符号化率の双方で高い誤り訂正能力となる。
【００６２】
なお、この発明の実施の形態１において適用可能な行分割は、１行を２行に分割するという制限がなく、たとえば、１行を３行に分割してもよく、また、元のパリティ検査行列Ｈ１のすべての行を分割してもよく、一部のみを行分割してもよい。
これにより、自由度が高く、行分割によって増加行数を設定できるので、幅広い符号化率を可変にすることができる。
【００６３】
また、この発明の実施の形態１は、符号化率の可変化を目的した場合のみに限らず、ＬＤＰＣ符号の符号長ｎを一定にしたまま情報ビット長およびパリティビット長を調整し、任意の符号化率のＬＤＰＣ符号を構成することが目的である場合においても、適用可能である。
【００６４】
たとえば、通信システムのフレームフォーマットに合致するようにＬＤＰＣ符号を構成したい場合があるが、パリティ検査行列Ｈ１の列数および行数を、フレームフォーマットの要求通りに生成し、かつ高性能を実現することは難しい。
【００６５】
これを実現するためには、まず、パリティ検査行列Ｈ１の列数（ＬＤＰＣ符号の符号長ｎ）がフレームフォーマットと合致するように、パリティ検査行列Ｈ１を生成し、その後、行分割によってパリティ検査行列Ｈ１の行数を増やせばよい。
これにより、符号長ｎを変えずに、情報系列長ｋとパリティビット長とを１ビット単位で調整し、フレームフォーマットに合致させることが可能である。
【００６６】
また、この調整法は、ＬＤＰＣ符号の符号長ｎのみが定まっていて、符号化率「ｋ／ｎ」または情報系列長ｋが定まっていない場合に有効である。
たとえば、ＬＤＰＣ符号を用いて連接符号を構成する際に、フレームフォーマットの要求によって、連接符号全体で用いるパリティビット長が定まってはいるものの、連接符号を構成する各誤り訂正符号の符号化率が定まっていない場合に、上記手法によってＬＤＰＣ符号の符号化率を１ビット単位で調整することができる。
【００６７】
ところで、ＬＤＰＣ符号においては、符号語を形成するビットごとに、復号後の残留ビット誤りの発生のしやすさが異なる。
つまり、パリティ検査行列Ｈ１のどの列に対応するビットかによって、誤りやすさが異なっているので、上記のように行分割工程を行うと、パリティ検査行列が変化することから、残留ビット誤りの発生しやすい列（符号語におけるビット位置）が変化してしまう可能性がある。
【００６８】
したがって、この発明の実施の形態１に係る誤り訂正符号化方法を適用した通信システムにおいて、内符号をＬＤＰＣ符号とした連接符号を誤り訂正方式として採用している場合は、内符号であるＬＤＰＣ符号の切り換えによって誤りビットの発生位置が変化するので、外符号に影響を与える可能性がある。
【００６９】
しかし、この発明の実施の形態１により生成した符号化行列Ｇ２およびパリティ検査行列Ｈ２に対して、情報系列に対応する列を並び替えれば、上記問題による影響を抑制することが可能である。
たとえば、ランダムな順序で並び替えを行えば、上記問題による影響は小さくなる。ただし、このとき、パリティ検査行列Ｈ２と符号化行列Ｇ２とに対して同一の並び替えを行う必要がある。
【００７０】
同様に、この発明の実施の形態１に係る誤り訂正符号化装置においても、上述した各工程を実行する手段を備えることにより、上述した通りの作用効果を奏する。
【００７１】
（実施例２）
なお、上記実施の形態１（図１〜図４）では、パリティ検査行列Ｈ１を行分割してパリティ検査行列Ｈ２を生成したが、行分割に代えて行結合を用いてもよい。
この場合、前述の行分割工程に代えて、１つのパリティ検査行列に基づいて２つ以上の行を結合する行結合工程が用いられる。
【００７２】
行結合とは、行分割とは逆の操作であり、２つ以上の行を要素ごとに加算（結合）することで１つの行にし、行数を減らす操作である。
すなわち、パリティ検査行列Ｈ２に行結合を施し、パリティ検査行列Ｈ２の行数を減少させたパリティ検査行列Ｈ１を生成した場合においても、前述（図３）の符号化行列Ｇ２の生成方法により、符号化行列Ｇ２を生成することができる。
【００７３】
この場合、まず、あらかじめパリティ検査行列Ｈ２に行結合を施して、パリティ検査行列Ｈ１を生成しておく。ただし、パリティ検査行列Ｈ２を行結合する前に、各行結合で結合する行のうちの１つを除いたすべての行を、それぞれパリティ検査行列Ｈ２の一番上の行に配置しておく必要がある。
【００７４】
その後、図３内のステップＳ１を行い、次のステップＳ２においては、パリティ検査行列Ｈ１のみでなく、パリティ検査行列Ｈ２に対しても列交換を行う。
また、ステップＳ３においては、パリティ検査行列Ｈ１を生成する際の行結合とは全く逆の行分割を行うものと見なし、行の配置を上記の通りにしたパリティ検査行列Ｈ２を生成する。
その後のステップＳ４〜Ｓ６は、前述（図３）の通りに行えばよい。
【００７５】
上記構成によれば、２種の符号化率のＬＤＰＣ符号に対応した通信システムにおいて、２種の符号化率における符号長を一定とすることができる。また、２種の符号化率の間で符号化行列を共有化することができ、符号化演算の一部を共通化できるため、符号化演算または符号化器の演算量や記憶領域、回路規模を小さくすることができる。
【００７６】
また、前述のように、ＬＤＰＣ符号においては、符号語を形成するビットごとに、復号後の残留ビット誤りの発生のしやすさが異なり、パリティ検査行列Ｈ１のどの列に対応するビットかによって、誤りやすさが異なっているので、上記のように行結合工程を行うと、パリティ検査行列が変化することから、残留ビット誤りの発生しやすい列（符号語におけるビット位置）が変化してしまう可能性がある。
【００７７】
したがって、この発明の実施の形態２に係る誤り訂正符号化方法を適用した通信システムにおいて、内符号をＬＤＰＣ符号とした連接符号を誤り訂正方式として採用している場合は、内符号であるＬＤＰＣ符号の切り換えによって誤りビットの発生位置が変化するので、外符号に影響を与える可能性がある。
【００７８】
しかし、前述と同様に、この発明の実施の形態２により生成した符号化行列Ｇ２およびパリティ検査行列Ｈ２に対して、情報系列に対応する列を並び替えれば、上記問題による影響を抑制することが可能である。
たとえば、ランダムな順序で並び替えを行えば、上記問題による影響は小さくなる。ただし、このとき、パリティ検査行列Ｈ２と符号化行列Ｇ２とに対して同一の並び替えを行う必要がある。
【００７９】
（実施例３）
なお、上記実施の形態１（図１〜図４）では、パリティ検査行列Ｈ１と、パリティ検査行列Ｈ１を行分割したパリティ検査行列Ｈ２と、の２種類の符号化率に対応する符号化行列Ｇ２を生成したが、パリティ検査行列Ｈ２をさらに行分割して生成したパリティ検査行列Ｈ３（図５参照）に対して、符号化行列Ｇ３（図６参照）を生成し、さらに、図７のように、同様の操作を繰り返して、ｃ（≧３）種類の符号化率（ｃ−１回の行分割）に対応した符号化行列Ｇｃおよびパリティ検査行列Ｈｃを生成してもよい。
【００８０】
図５はこの発明の実施の形態３によりさらに行分割（２回目）して生成されたパリティ検査行列Ｈ３を示す説明図であり、図６はこの発明の実施の形態３により生成された符号化行列Ｇ３を示す説明図である。
また、図７はこの発明の実施の形態３による符号化行列Ｇ３の生成方法を示すフローチャートである。
【００８１】
以下、図５〜図７を参照しながら、この発明の実施の形態３に係る誤り訂正符号化方法における符号化行列Ｇ３の生成方法について説明する。
ただし、ここでは、前述（図３）の符号化行列Ｇ２の生成方法によって既に符号化行列Ｇ２が得られているものとし、さらに、符号化行列Ｇ２に対応した列交換が施されたパリティ検査行列Ｈ１、Ｈ２が得られているものとする。
【００８２】
図５において、パリティ検査行列Ｈ３は、１回行分割した行列Ｈ２に対して、さらに２回目の行分割を施されることにより、ｒｉの初期値（ｉ＝３）分だけ行数が増加している。
同様に、図６において、符号化行列Ｇ３（３種類の符号化率に対応）は、行分割１回目に対応した符号化行列Ｇ２に対して、さらにｒｉ（ｉ＝３）分だけ行数が増加している。
【００８３】
図７のフローチャートは、前述（図３）と基本的には同じであり、図３と大きく異なる点は、既に符号化行列Ｇ２が得られていることから、図３内のステップＳ１、Ｓ２に該当する処理が存在しない点と、図３内のステップＳ３〜Ｓ６に該当する処理（ステップＳ１１〜Ｓ１４）を、可変したい符号化率の数だけ繰り返し行う点と、の２点のみである。
【００８４】
図７において、まず、ループ繰り返し変数ｉを初期値（ｉ＝３）にセットし（ステップＳ１０）、ループ内部のステップＳ１１〜Ｓ１４を繰り返し行う。
最終のループ処理（ステップＳ１５）は、ステップＳ１１〜Ｓ１４の処理を繰り返し行うためのものであり、ステップＳ１４が終了するごとに、ステップＳ１０の処理に復帰させる。
【００８５】
ステップＳ１０においては、ステップＳ１４が終了するごとに、変数ｉの値を「１」だけ増やし、変数ｉが、可変したい符号化率の数ｃに対して「ｉ≦ｃ」の関係を満たせば、ループ内部のステップＳ１１〜Ｓ１４を再実行し、「ｉ＞ｃ」の関係となれば、図７の処理ルーチンを終了する。
なお、以下の説明において、行列Ｈ（ｉ−１）は、行列Ｈｓ（ｓ＝ｉ−１）を表すものとする。
【００８６】
初期化処理（ステップＳ１０）に続くステップＳ１１においては、パリティ検査行列Ｈ（ｉ−１）を行分割し、図５に示すように、ｒｉ行のパリティ検査行列Ｈｉを生成する。
ステップＳ１１の行分割は、前述の実施の形態１と同様に、パリティ検査行列Ｈｉに属する各行ベクトルが１次独立となるように行われる。
【００８７】
続いて、ステップＳ１１の行分割で増加したｒｉ行を、符号化行列Ｇ（ｉ−１）に付加する（ステップＳ１２）。
ステップＳ１２においては、前述の実施の形態１で述べたように、各行分割で生じた行のうち、１行を除いたすべての行をそれぞれ付加する。
次に、前述の実施の形態１の場合と同様の制限下で下三角化を行い、図６に示すように、符号化行列Ｇｉを生成する（ステップＳ１３）。
【００８８】
最後に、パリティ検査行列Ｈ１〜Ｈｉのすべてに対して、ステップＳ１３の列交換を行い（ステップＳ１４）、ループ処理（ステップＳ１５）に移行する。
以上のステップＳ１１〜Ｓ１４（前述のステップＳ３〜Ｓ６に対応）は、ステップＳ１３（前述のステップＳ５に対応）の処理が、最も符号化率（行数）の大きいＬＤＰＣ符号のパリティ検査行列に対して行われるまで、繰り返し行われる。
【００８９】
なお、前述の実施の形態１で述べたように、どの行をどのように行分割したかの情報を復号側で記憶しておけば、ステップＳ１４においてすべてのパリティ検査行列Ｈ１〜Ｈｉを列交換する必要はなく、行分割の情報に応じて、一部のパリティ検査行列のみを列交換すればよい。
【００９０】
たとえば、復号側において、パリティ検査行列Ｈｃのみを記憶して、どの行を加算すれば（要素ごとの排他的論理和を行えば）行分割前のパリティ検査行列Ｈ（ｃ−１）が得られるかの情報を有しておき、また、パリティ検査行列Ｈ（ｃ−１）のどの行を加算すればパリティ検査行列Ｈ（ｃ−２）となるかの情報を有しておき、さらに、以下同様にして、元のパリティ検査行列Ｈ１までのすべてのパリティ検査行列が復元可能な情報を有するように、復号方法（または、復号装置）を構成すれば、図７内のステップＳ１４は、パリティ検査行列Ｈｉに対してのみ列交換を行えばよい。
なぜなら、各ループにおいて、パリティ検査行列Ｈｉのみに対して列交換していけば、パリティ検査行列Ｈｃを得ることができるからである。
【００９１】
また、上記説明では、元のパリティ検査行列Ｈ１を、符号化率の異なる複数のＬＤＰＣ符号のうちの１つとして可変な構成としたが、必ずしもパリティ検査行列Ｈ１を可変なＬＤＰＣ符号の１つとして含める必要はない。
【００９２】
たとえば、パリティ検査行列Ｈ１に行分割を施して得られたパリティ検査行列Ｈ２を、上記処理によりパリティ検査行列Ｈ１と記したパリティ検査行列に改めて置きなおし、新たなパリティ検査行列Ｈ１に対して上記の符号化行列の生成方法を適用すれば、元のパリティ検査行列には対応していないものの、複数回にわたって行分割した複数のパリティ検査行列に対応した符号化行列を生成することができる。
【００９３】
以上のように、この発明の実施の形態３によれば、前述の実施の形態１と同等の作用効果が得られるうえ、符号化行列Ｇｃによって、ｃ種類のパリティ検査行列Ｈ１〜Ｈｃに対応した符号化を行うことができ、符号化演算の一部を異なる符号率間で共通化することができ、符号化演算や符号化器の演算量や、記憶領域および回路規模を軽減することができる。
【００９４】
また、可変する符号化率のすべてにおいて、符号長を一定とすることが可能である。
さらに、列重み分布は、可変設定される符号化率のすべてにおいて等しいので、パリティ検査行列Ｈ１の列重み分布が最適値であれば、可変される符号化率のすべてにおいて、高い誤り訂正能力を達成することができる。
【００９５】
さらに、前述の実施の形態２のように、行分割に代えて行結合を適用した場合であっても、この発明の実施の形態３と同様に構成することができる。この場合、元のパリティ検査行列をＨｃとし、行結合によって得られるパリティ検査行列を、行数の多いものから順に、Ｈ（ｃ−１）、Ｈ（ｃ−２）、・・・、Ｈ１と置き、その後、前述の行分割の場合と同様にして、符号化行列Ｇ１から順に符号化行列Ｇ２、Ｇ３、・・・、Ｇｃを生成すれば、パリティ検査行列Ｈ１〜Ｈｃに対応した符号化行列Ｇｃが得られる。
【００９６】
（実施例４）
なお、上記実施の形態１〜３（図１〜図７）では、誤り訂正符号化方法（または、装置）における符号化行列Ｇの生成方法（または、装置）を示したが、図８に示すように、誤り訂正符号化方法（または、装置）を用いて、通信システムを構成してもよい。
【００９７】
図８はこの発明の実施の形態４に係る通信システムを示すブロック構成図であり、前述の実施の形態１〜３に係る誤り訂正符号化方法（または、装置）を用いた通信システムを示している。この場合、特に、前述の実施の形態１（図３、図４）で生成した符号化行列Ｇ２を用いた効率的な符号化器１００を備えた構成例を示している。
【００９８】
図８において、通信システムは送信側装置および受信側装置からなり、送信側装置は、送信ビット列から誤り訂正符号の符号語を生成する符号化器１００と、符号化器１００からの符号語に基づいて変調信号を生成する変調器２００とを備えている。
【００９９】
変調器２００からの変調信号は、通信路３００を介して送信され、受信側装置により受信される。
受信側装置は、変調器２００から受信した変調信号を復調する復調器４００と、復調器４００からの復調信号に基づいて誤り訂正符号の復号を行う復号器５００とを備えている。
【０１００】
符号化器１００は、送信ビット列に基づいてパリティビットを生成し、符号語を計算する。
変調器２００は、符号語にしたがって変調を行い、通信方式に応じて、電波、光または電気信号を生成し、変調信号として送信する。
【０１０１】
変調器２００から送信された変調信号は、通信路３００を通って雑音が付加された後、受信側装置で受信される。
復調器４００は、受信した変調信号を復調し、復調信号を復号器５００に入力する。
復号器５００は、復号した結果を、送信情報となる推定ビット列として出力する。
【０１０２】
図９は図８内の符号化器１００の内部構成を示すブロック図であり、２種の符号化率に対応した符号化器１００の一例を示している。
図９において、符号化器１００は、ＬＤＰＣ符号の符号化率を切り換える符号化率切換器１０１と、送信ビット列が入力される入力回路１０２と、入力回路１０２を介した入力信号を符号化する符号化回路１０３と、入力信号を選択するセレクタ１０４と、セレクタ１０４を介した入力信号を符号化する符号化回路１０５と、符号化回路１０５の出力信号を制御して符号語を生成する出力回路１０６と、各種情報を記憶するメモリ１０７とを備えている。
【０１０３】
なお、図９に示した符号化器１００で用いるＬＤＰＣ符号の符号長は、ｎビットとしている。
また、符号化率切換器１０１は、２種の情報系列長（ｋビット、「ｋ−ｒ」ビット）に対応した２種の符号化率（「ｋ／ｎ」、「（ｋ−ｒ）／ｎ」）の切り換えが可能に構成されている。
【０１０４】
符号化率切換器１０１は、通信システムで用いる符号化率情報を切り換え設定して、入力回路１０２およびセレクタ１０４に入力する。
なお、通信システムで使用する符号化率は、あらかじめ設定されるか、受信側装置と同期しながら自動的に設定されるか、外部の切り換えスイッチ（図示せず）などにより手動で切り換えられるか、または、その他の任意手段によって決定される。
【０１０５】
入力回路１０２は、入力された送信ビット列の制御を行い、送信ビット列を一時的にメモリ１０７に記憶し、符号化率切換器１０１から入力された符号化率情報に基づくビット列を、符号化率情報（「ｋ−ｒ」またはｋ）に応じて、符号化回路１０３またはセレクタ１０４に入力する。
【０１０６】
すなわち、入力回路１０２は、情報系列長「ｋ−ｒ」ビットの符号化率「（ｋ−ｒ）／ｎ」を用いる場合には、符号化回路１０３に対して「ｋ−ｒ」ビットのビット列を入力し、情報系列長ｋビットの符号化率「ｋ／ｎ」を用いる場合には、セレクタ１０４に対してｋビットのビット列を入力する。
【０１０７】
符号化回路１０３は、入力された「ｋ−ｒ」ビットに基づいて、まず、ｒビットのパリティビットを生成する。
このとき、符号化回路１０３で生成されるのは、図４内の符号化行列Ｇ２の第１行から第ｒ行に基づいて計算されるパリティビットである。つまり、行分割によって増加されたｒ行と、入力された「ｋ−ｒ」ビットの送信ビット列とを用いて、ｒビットのパリティビット列を生成する。
【０１０８】
また、符号化回路１０３は、最終的に、「ｋ−ｒ」ビットの送信ビット列と、生成したｒビットのパリティビット列とを結合し、ｋビットのビット列をセレクタ１０４に入力する。
【０１０９】
セレクタ１０４は、符号化率切換器１０１で設定された符号化率情報に基づき、符号化率「（ｋ−ｒ）／ｎ」を用いる場合には、符号化回路１０３からのｋビットのビット列を選択し、符号化率「ｋ／ｎ」を用いる場合には、入力回路１０２から直接入力されたｋビットのビット列を選択して、符号化回路１０５に入力する。
【０１１０】
符号化回路１０５は、セレクタ１０４から入力されたｋビットのビット列を用いて符号化を行う。すなわち、図４内の符号化行列Ｇ２の下側「ｎ−ｋ」行を用いて、「ｎ−ｋ」ビットのパリティビットを生成する。
符号化行列Ｇ２の下側「ｎ−ｋ」行は、元のパリティ検査行列Ｈ１と行分割後のパリティ検査行列Ｈ２との双方に対応しているので、両方の符号化率で共有可能となる。
符号化回路１０５は、生成した「ｎ−ｋ」ビットを入力ビット列に結合し、最終的なｎビットのビット列を出力回路１０６に入力する。
【０１１１】
最後に、出力回路１０６は、変調器２００の構成に合わせて、メモリ１０７を用いて符号化後のビット列の出力制御を行い、符号化器１００の出力信号となる符号語を生成して変調器２００に入力する。
なお、上記説明では、入力回路１０２および出力回路１０６のみにおいてメモリ１０７を用いたが、通信システムの仕様に合わせて、それ以外の部分で用いてもよい。
【０１１２】
以上のように、この発明の実施の形態４（図８、図９）によれば、この発明の実施の形態１〜３の誤り訂正符号化方法（または、装置）を用いた通信システムにおいて、符号化器１００内に符号化率切換器１０１、セレクタ１０４および符号化回路１０３、１０５を設け、複数のＬＤＰＣ符号を切り換え可能に構成したので、符号化回路１０５を２種の符号化率のＬＤＰＣ符号で共有化することができ、回路規模を削減することができる。
【０１１３】
なお、図９においては、符号化器１００の一例を示したが、符号化器１００内の符号化回路１０５を２種の符号化率のＬＤＰＣ符号で共有するような構成であれば、同様の効果を奏することができる。
【０１１４】
同様に、この発明の実施の形態４に係る通信システムに適用される誤り訂正符号化装置は、１つのパリティ検査行列に基づいて、一部またはすべての行を２つ以上ごとの行に分割する行分割手段（図３、図４内のステップＳ３）と、任意の符号化率の複数のＬＤＰＣ符号を構成する符号構成手段（ステップＳ５）と、符号構成手段によって生成された符号長が等しく符号化率が異なる複数のＬＤＰＣ符号のそれぞれを符号化する符号化手段（符号化器１００）とを備えている。
【０１１５】
符号化器１００は、複数のＬＤＰＣ符号のうち最も符号化率の大きい最大ＬＤＰＣ符号に対応する符号化行列のみを有し、最大ＬＤＰＣ符号以外のＬＤＰＣ符号を符号化する際には、最大ＬＤＰＣ符号に対応する符号化行列の部分行列に基づいて、符号化を行う。
【０１１６】
また、符号化器１００は、最大ＬＤＰＣ符号に対応した符号化行列に基づく最大符号化手段と、複数のＬＤＰＣ符号から１つを選択する符号化率選択手段（符号化率切換器１０１）と、符号化行列から、符号化率選択手段で選択したＬＤＰＣ符号に対応する部分行列を選択する部分行列選択手段（セレクタ１０４）と、最大符号化手段のうち部分行列選択手段で選択された部分行列に基づく部分のみを用いて符号化を行う部分行列符号化手段（符号化回路１０５）とを備えている。
これにより、上述した通り、符号化器１００内の最も出力側の符号化回路１０５を２種の符号化率（「ｋ／ｎ」、「（ｋ−ｒ）／ｎ」）のＬＤＰＣ符号で共有化可能なので、回路規模を削減することができる。
【０１１７】
（実施例５）
なお、上記実施の形態４（図８、図９）では、２種の符号化率を可変設定する符号化器１００を用いたが、図１０に示すように、３種の符号化率を可変設定する符号化器１００Ａを用いてもよい。
【０１１８】
図１０はこの発明の実施の形態５に係る誤り訂正符号化方法（または、装置）を用いた通信システムの符号化器１００Ａの内部構成を示すブロック図であり、前述（図８、図９参照）と同様のものについては、前述と同一符号を付して詳述を省略する。
また、図１０内の符号化器１００Ａ、符号化率切換器１０１Ａおよび入力回路１０２Ａは、前述（図９）の符号化器１００、符号化率切換器１０１および入力回路１０２に対応している。
【０１１９】
図１０において、符号化器１００Ａは、前述の構成要素１０３〜１０７に加えて、入力回路１０２Ａに接続された符号化回路１０８およびセレクタ１０９を備えている。
セレクタ１０９は、入力回路１０２Ａと符号化回路１０３との間に挿入されており、符号化回路１０８は、入力回路１０２Ａとセレクタ１０９との間に挿入されている。
【０１２０】
符号化率切換器１０１Ａは、３種の情報系列長（ｋビット、「ｋ−ｒ」ビット、「ｋ−ｒ−ｒｉ」ビット）に対応した３種の符号化率（「ｋ／ｎ」、「（ｋ−ｒ）／ｎ」、「（ｋ−ｒ−ｒｉ）／ｎ」）の切り換えが可能に構成されている。
【０１２１】
符号化率切換器１０１Ａにおいて、行分割を２回行った後のパリティ検査行列Ｈ３（図５参照）を用いるものと設定された場合、入力回路１０２Ａは、符号化回路１０８に対して、「ｋ−ｒ−ｒｉ」ビットの情報ビットを入力する。
符号化回路１０８は、入力されたビット列にｒｉビットのパリティビットを追加して、ｒｉビットのビット列をセレクタ１０９に入力する。このとき、符号化回路１０８で追加されるパリティビットは、図６内の符号化行列Ｇ３の上側ｒｉ行に基づいて算出される。
【０１２２】
セレクタ１０９は、符号化率切換器１０１Ａで切り換えられた符号化率に応じて、入力ビット列を選択する。
すなわち、セレクタ１０９は、２回行分割したＬＤＰＣ符号を用いる場合には、符号化回路１０８からのビット列（ｋ−ｒビット）を選択して符号化回路１０３に入力し、１回行分割したＬＤＰＣ符号を用いる場合には、入力回路１０２Ａからのビット列（ｋ−ｒビット）を選択して符号化回路１０３に入力する。
以下、前述の実施の形態３（図９）と同様に、符号化回路１０３〜出力回路１０６により、符号化器１００Ａの出力信号（符号語）が生成されて変調器２００に入力される。
【０１２３】
以上のように、この発明の実施の形態５（図１０）に係る通信システムによれば、符号化器１００Ａ内の最も出力側の符号化回路１０５を、３種の符号化率（「ｋ／ｎ」、「（ｋ−ｒ）／ｎ」、「（ｋ−ｒ−ｒｉ）／ｎ」）のＬＤＰＣ符号で共有化することができ、符号化回路１０５の上段側の符号化回路１０３を、２種の符号化率（「ｋ／ｎ」、「（ｋ−ｒ）／ｎ」）のＬＤＰＣ符号で共有化可能なので、回路規模を削減することができる。
【０１２４】
なお、図１０においては、符号化器１００Ａの一例を示したが、符号化回路１０５、１０３を複数の符号化率のＬＤＰＣ符号で共有するような構成であれば、同等の作用効果を奏することができる。
【０１２５】
また、図１０においては、前述の実施の形態４（図９）と同様の構成に加えて、符号化回路１０３と入力回路１０２Ａとの間に、符号化回路１０８およびセレクタ１０９を挿入したが、さらに、符号化回路１０８と入力回路１０２Ａとの間に、新たな符号化回路およびセレクタ（図示せず）を追加挿入することにより、４種の符号化率を可変設定する符号化器を構成することも可能である。以下同様に、新たな符号化回路およびセレクタを順次追加挿入し、５種以上の符号化率を可変設定する符号化器を構成することも可能である。
【０１２６】
（実施例６）
なお、上記実施の形態１〜３（図１〜図７）では、基本となるパリティ検査行列と、行分割により生成したパリティ検査行列との間で、符号化行列を共通化する符号化行列生成方法を適用した誤り訂正符号化方法（または、装置）を示したが、他の場合においても、同様の符号化行列生成方法は構成可能である。
【０１２７】
以下、この発明の実施の形態６に係る誤り訂正符号化方法（または、装置）について説明する。
この発明の実施の形態６においては、列数の等しい２つのパリティ検査行列Ｈ１、Ｈ２の一方が、他方のパリティ検査行列の部分行列となっている場合に、前述と同様の符号化行列生成方法を適用するものとする。
【０１２８】
ここでは、パリティ検査行列Ｈ１がパリティ検査行列Ｈ２の部分行列であるものとし、パリティ検査行列Ｈ２の行ベクトルは１次独立であるものとする。このとき、パリティ検査行列Ｈ１の行ベクトルも必ず１次独立となる。
【０１２９】
上記関係の２つのパリティ検査行列Ｈ１、Ｈ２は、まず、パリティ検査行列Ｈ１を用意して、これに対して新たな行を追加してパリティ検査行列Ｈ２を生成するか、または、パリティ検査行列Ｈ２の一部の行を選び、それらの行からなる部分行列をパリティ検査行列Ｈ１とするなどにより構成される。
【０１３０】
このような関係にある２つのＬＤＰＣ符号は、復号演算部の一部を共有化可能なので、可変符号化率に対応する通信システムに有用であるが、前述の実施の形態１における行分割の場合と同様に、符号化法が問題となる。
この発明の実施の形態６においては、前述の実施の形態１のように、２つのＬＤＰＣ符号で共有化可能な符号化行列Ｇ２の生成方法を示す。
【０１３１】
図１１はこの発明の実施の形態６による処理手順を示すフローチャートであり、パリティ検査行列Ｈ１、Ｈ２の符号化が可能な符号化行列Ｇ２の生成方法を示している。
なお、図１１内のステップＳ２１〜Ｓ２５は、概して、前述（図３参照）のステップＳ１、Ｓ２、Ｓ４〜Ｓ６に対応している。
【０１３２】
まず、一方のパリティ検査行列Ｈ１に対して基本行操作および列交換を行い、符号化行列Ｇ１を生成する（ステップＳ２１）。
続いて、パリティ検査行列Ｈ２に対しても、ステップＳ２１の列交換を施す（ステップＳ２１）。
【０１３３】
次に、符号化行列Ｇ１の最も上の行に対して、パリティ検査行列Ｈ２の行を付加する（ステップＳ２３）。このとき、符号化行列Ｇ１の一番上の行に付加される行は、パリティ検査行列Ｈ１とパリティ検査行列Ｈ２との差分である。つまり、パリティ検査行列Ｈ２の行のうち、パリティ検査行列Ｈ１のどの行とも異なる行を、すべて付加することになる。
【０１３４】
次に、ステップＳ２３で付加した行に対する基本行操作と、行全体に対する列交換とを行い、下三角化することにより、符号化行列Ｇ２を生成する（ステップＳ２４）。
ここで行う基本行操作および列交換は、前述（図３、図４）のステップＳ５と同様の制限下で行われる。すなわち、行交換は、ステップＳ２４で付加した行と符号化行列Ｇ１との間で行わず、列交換は、既に下側ｍ行が下三角行列となっている部分（右側のｍ列）に対しては行わない、ものとする。
【０１３５】
最後に、パリティ検査行列Ｈ１、Ｈ２に対して、ステップＳ２４と同じ列交換を行い（ステップＳ２５）、図１１の処理ルーチンを終了する。
ただし、復号方法（および装置）において、パリティ検査行列Ｈ２のみを記憶し、パリティ検査行列Ｈ２のどの部分行列がパリティ検査行列Ｈ１となるかの情報を記憶するように構成すれば、ステップＳ２５の列交換処理は、パリティ検査行列Ｈ２のみに対して行えばよい。
【０１３６】
上記説明では、パリティ検査行列Ｈ２の部分行列が、そのままパリティ検査行列Ｈ１である場合について述べたが、２つのパリティ検査行列Ｈ１、Ｈ２の列や行の並びを任意に変更し、変更後の行列において、一方が他方の部分行列となっていれば、上記方法によって符号化行列を生成することは可能である。
すなわち、あらかじめ、列および行の並びを変更して２つのパリティ検査行列Ｈ１、Ｈ２が部分行列の関係となるようにしておき、上記方法で符号化行列を生成すればよい。なお、行や列の並びを変更しても、誤り訂正能力への影響はほとんど生じない。
【０１３７】
また、上記説明では、２つのパリティ検査行列Ｈ１、Ｈ２について述べたが、３つのパリティ検査行列Ｈ１、Ｈ２、Ｈ３に対しても、同様の方法で３つのパリティ検査行列Ｈ１〜Ｈ３に対応した符号化行列Ｇ３を構成することができる。
【０１３８】
この場合、パリティ検査行列Ｈ１がパリティ検査行列Ｈ２の部分行列となっており、パリティ検査行列Ｈ２がパリティ検査行列Ｈ３の部分行列となっているものとし、まず、図１１の符号化行列の生成方法によってパリティ検査行列Ｈ１、Ｈ２に対応した符号化行列Ｇ２を生成する。
【０１３９】
続いて、符号化行列Ｇ２の一番上の行に、パリティ検査行列Ｈ３とパリティ検査行列Ｈ２との差分の行を付加し、図１１内の下三角化処理（ステップＳ２４）と、列交換処理（ステップＳ２５）を行うことにより、３つのパリティ検査行列Ｈ１〜Ｈ３に対応した符号化行列Ｇ３を生成することができる。ただし、パリティ検査行列Ｈ３の行ベクトルは１次独立であるものとする。
【０１４０】
同様に、４つ以上のパリティ検査行列に対しても、上記の部分行列の関係があり、また最も行数の多いパリティ検査行列の行ベクトルが１次独立であれば、４つ以上のパリティ検査行列に対応した符号化行列を生成することができる。
【０１４１】
以上のように、この発明の実施の形態６（図１１）に係る誤り訂正符号化方法（または、装置）において適用する符号化行列生成方法によれば、生成された符号化行列Ｇ２は、１つの符号化行列で符号化率の異なる複数のＬＤＰＣ符号の符号化に用いることができる。
また、この発明の実施の形態６に係る誤り訂正符号化方法（または、装置）を可変符号化率の通信システムに適用すれば、前述と同様に、符号化演算または符号化器の記憶領域や演算量を小さくすることができる。
【０１４２】
なお、この発明の実施の形態６で生成する符号化行列Ｇ２に対しても、前述の実施の形態４、５（図９、図１０）における符号化器１００、１００Ａと同様の構成が適用可能であり、符号化回路１０５を符号化率の異なる複数のＬＤＰＣ符号で共有することにより回路規模を削減することができる。
さらに、この発明の実施の形態６によれば、可変する符号化率のＬＤＰＣ符号において、符号長をすべて同一とすることができる。
【符号の説明】
【０１４３】
１００、１００Ａ  符号化器、１０１、１０１Ａ  符号化率切換器、１０２、１０２Ａ  入力回路、１０３、１０５  符号化回路、１０４  セレクタ、１０６  出力回路、１０８  符号化回路、１０９  セレクタ、２００  変調器、３００  通信路、４００  復調器、５００  復号器、Ｇ、Ｇ１〜Ｇ３、Ｇｃ、Ｇｉ  符号化行列、Ｈ、Ｈ１〜Ｈ３、Ｈｃ、Ｈｉ  パリティ検査行列、ｋ  情報系列長、ｒ  増加行数。
【図１】
0005442024.tif 000002
【図２】
0005442024.tif 000003
【図３】
0005442024.tif 000004
【図４】
0005442024.tif 000005
【図５】
0005442024.tif 000006
【図６】
0005442024.tif 000007
【図７】
0005442024.tif 000008
【図８】
0005442024.tif 000009
【図９】
0005442024.tif 000010
【図１０】
0005442024.tif 000011
【図１１】
0005442024.tif 000012