(57)【要約】【課題】  Sum-Productアルゴリズムを用いた畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できる畳み込み符号及びターボ符号の復号器を提供する。【解決手段】  Sum-Productアルゴリズムを用いた畳み込み符号、ターボ符号の復号器において、拘束長の長い（ＨＣＬ）パリティ検査を用いて復号を行い、また、複数のＨＣＬパリティ検査を用いて復号（マルチパリティ復号）を行うものであり、オリジナルのパリティ検査多項式に対して畳み込み符号では拘束長が２倍程度の長さ、ターボ符号では拘束長が５倍程度の長さがあり、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善する畳み込み符号及びターボ符号の復号器である。【選択図】        図１３
2008271516.tif 000002
【特許請求の範囲】
【請求項１】
Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、
パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して前記集合に追加する処理を繰り返して得られた集合からタナーグラフにおいて長さ４のループが少なく、拘束長が大きい多項式を選択してパリティ検査式として復号することを特徴とする復号器。
【請求項２】
パリティ検査多項式の初回の集合の要素は、オリジナルのパリティ検査多項式と遅延演算子を掛けたパリティ検査多項式で構成されることを特徴とする請求項１記載の復号器。
【請求項３】
畳み込み符号の復号器にあっては、
オリジナルのパリティ検査多項式に対して拘束長が２倍程度の長さがあることを特徴とする請求項１又は２記載の復号器。
【請求項４】
ターボ符号の復号器にあっては、
オリジナルのパリティ検査多項式に対して拘束長が５倍程度の長さがあることを特徴とする請求項１又は２記載の復号器。
【請求項５】
Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、
パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して前記集合に追加する処理を繰り返して得られた集合からパリティ検査多項式の複数をパリティ検査式として復号することを特徴とする復号器。
【請求項６】
Sum-Productアルゴリズムを用いたターボ符号の復号器であって、
符号系列を元に戻すよう並び替えるディインタリーバと、
前記ディインタリーバからの出力を分割して入力すると共に通信路値を入力して、Sum-Product復号を行う複数の第１の復号器と、
前記第１の復号器からの出力を加算する第１の加算器と、
前記第１の加算器からの出力をスケーリングする第１の乗算器と、
前記第１の乗算器からの出力について符号系列の並び替えを行うインタリーバと、
前記インタリーバからの出力を分割して入力すると共に通信路値を入力して、Sum-Product復号を行う複数の第２の復号器と、
前記第２の復号器からの出力を加算する第２の加算器と、
前記第２の加算器からの出力をスケーリングして前記ディインタリーバに出力する第２の乗算器と、
前記第２の加算器からの出力に通信路値を加算して出力する第３の加算器とを有し、
前記複数の第１の復号器と前記複数の第２の復号器には、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して前記集合に追加する処理を繰り返して得られた集合から各々選択されたパリティ検査式が予め設定されていることを特徴とする復号器。
【請求項７】
パリティ検査式として、オリジナルのパリティ検査多項式、若しくは、線形演算により得られた新しいパリティ検査多項式の中で、拘束長の短いパリティ検査多項式が最低１つは含まれることを特徴とする請求項５又は６記載の復号器。
【請求項８】
畳み込み符号を要素符号とするターボ符号の復号器にあっては、
選択されたパリティ検査多項式の複数が、パリティ検査式で関係する共通のビットが少ない組み合わせを選択することを特徴とする請求項５又は６記載の復号器。
【請求項９】
Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)に情報ビットＸ，パリティビットＰを含まない非零の多項式である変数Ａ(Ｄ)を乗算し、前記オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)よりも長い拘束長を持ち、前記オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)と等価となる変形したパリティ検査多項式Ｈ'(Ｐ，Ｘ)を生成し、当該パリティ検査多項式Ｈ'(Ｐ，Ｘ)の拘束長を変化させて、Sum-Productアルゴリズムを用いた復号特性の良い多項式を選択してパリティ検査式として復号することを特徴とする復号器。
【請求項１０】
パリティ検査多項式Ｈ'(Ｐ，Ｘ)の拘束長を変化させて、Sum-Productアルゴリズムを用いた復号特性の良い多項式を選択する際に、タナーグラフにおける長さ４のループの数が最小のものを選択することを特徴とする請求項９記載の復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、畳み込み符号及びターボ符号を復号する復号器に係り、特に、Sum-Product復号特性を改善できる畳み込み符号及びターボ符号の復号器に関する。
【背景技術】
【０００２】
［はじめに］
ＡＤＳＬ（Asymmetric Digital Subscriber Line）、第三世代携帯電話、地上ディジタルテレビ等の分野において、誤り訂正符号として、畳み込み符号、ターボ符号が用いられている。
特に、理論限界に近い特性を示す誤り訂正符号としてターボ符号が提案されている。
しかし、復号の処理量は、ＬＤＰＣ（Low-Density Parity Check）符号に比べて高い。もし、ターボ符号がＬＤＰＣ符号のように、Sum-Productアルゴリズム（ＳＰＡ）を用いた復号（Sum-Product復号）が可能であるならば、ターボ符号の復号の処理量は少なくなると期待される。
【０００３】
ＳＰＡは、符号のタナーグラフに短いループがない場合には、その符号で良好の復号特性を実現する。
以下の非特許文献では、Sum-Product復号で良い特性を得るには、タナーグラフに短いループが存在しない必要があるとして、タナーグラフに短いループを持たない畳み込み符号を使ってターボ符号を構成することを提案している。
【０００４】
尚、関連する先行技術として、特開２００５−１４１８８７号公報（特許文献１）がある。
特許文献１には、ビタビ復号アルゴリズム、ＢＣＪＲ（Bahl-Cocke-Jeinek-Raviv）復号アルゴリズム、更にターボ復号処理に関する記載がある。
【０００５】
また、畳み込み符号にSum-Product復号を適用した先行技術が以下の非特許文献１，２に記載され、ターボ符号にSum-Product復号を適用した先行技術が以下の非特許文献３に記載されている。
【０００６】
【特許文献１】特開２００５−１４１８８７号公報
【非特許文献１】Alberto Jimenez Flstrom, Kamil Sh. Zigangirov, Time-variying periodic convolutional codes with low-density parity-check matrix, IEEE Trans. Inform. Theory, vol. 45, no.6, pp.2181-2191,1999
【非特許文献２】Zhengang Chen, Stephen Bates, Construction of low-density parity-check convolutional codes through progressive edge-growth,IEEE Commum. Letters, vol.9, no.12, 2005
【非特許文献３】ZHU Lianxiang, FENG Wenjiang, YANG Shizhong, Iterative decoding of turbo codes based on factor graphs, IEEE Region 10 Annual International Conference, vol.2, pp.1077-1081, 2002.
【非特許文献４】G. Colavolpe, Design and performance of turbo gallager codes, IEEE Trans. Commum., vol.52, no.11, pp.1901-1908, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記非特許文献１，２では、畳み込み符号にSum-Product復号を適用したときに良い特性が得られるような符号の構成方法を提案しているものであって、当該方法によって構成された特定の符号に限り良いSum-Product復号特性を得ることが可能となるが、一般の符号に対するSum-Product復号特性を改善できるものではないという問題点があった。
【０００８】
また、上記非特許文献３では、ターボ符号にSum-Product復号を適用することが記載されているが、ターボ符号のSum-Product復号特性が悪いという問題点があった。
【０００９】
そして、上記非特許文献４では、ターボ符号においてタナーグラフが短いループを持たないような符号の中から特性の良い符号を探索し、探索された符号のSum-Product復号特性が良いことが記載されているが、Sum-Product復号特性が良好なのは、特定の符号に限られており、一般の符号に対するSum-Product復号特性を改善できないという問題点があった。
【００１０】
また、上記特許文献１では、ターボ符号をSum-Product復号することについては記載されていない。
【００１１】
本発明は上記実情に鑑みて為されたもので、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できる畳み込み符号及びターボ符号のSum-Productアルゴリズムを用いた復号器を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記従来例の問題点を解決するための本発明は、Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して集合に追加する処理を繰り返して得られた集合からタナーグラフにおいて長さ４のループが少なく、拘束長が大きい多項式を選択してパリティ検査式として復号することを特徴とする。
【００１３】
本発明は、上記復号器において、パリティ検査多項式の初回の集合の要素は、オリジナルのパリティ検査多項式と遅延演算子を掛けたパリティ検査多項式で構成されることを特徴とする。
【００１４】
本発明は、上記復号器において、畳み込み符号の復号器にあっては、オリジナルのパリティ検査多項式に対して拘束長が２倍程度の長さがあることを特徴とする。
【００１５】
本発明は、上記復号器において、ターボ符号の復号器にあっては、オリジナルのパリティ検査多項式に対して拘束長が５倍程度の長さがあることを特徴とする。
【００１６】
本発明は、Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して集合に追加する処理を繰り返して得られた集合からパリティ検査多項式の複数をパリティ検査式として復号することを特徴とする。
【００１７】
本発明は、Sum-Productアルゴリズムを用いたターボ符号の復号器であって、符号系列を元に戻すよう並び替えるディインタリーバと、ディインタリーバからの出力を分割して入力すると共に通信路値を入力して、Sum-Product復号を行う複数の第１の復号器と、第１の復号器からの出力を加算する第１の加算器と、第１の加算器からの出力をスケーリングする第１の乗算器と、第１の乗算器からの出力について符号系列の並び替えを行うインタリーバと、インタリーバからの出力を分割して入力すると共に通信路値を入力して、Sum-Product復号を行う複数の第２の復号器と、第２の復号器からの出力を加算する第２の加算器と、第２の加算器からの出力をスケーリングしてディインタリーバに出力する第２の乗算器と、第２の加算器からの出力に通信路値を加算して出力する第３の加算器とを有し、前記複数の第１の復号器と前記複数の第２の復号器は、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して集合に追加する処理を繰り返して得られた集合から各々選択されたパリティ検査式が予め設定されていることを特徴とする。
【００１８】
本発明は、上記復号器において、パリティ検査式として、オリジナルのパリティ検査多項式、若しくは、線形演算により得られた新しいパリティ検査多項式の中で、拘束長の短いパリティ検査多項式が最低１つは含まれることを特徴とする。
【００１９】
本発明は、上記復号器において、畳み込み符号を要素符号とするターボ符号の復号器にあっては、選択されたパリティ検査多項式の複数が、パリティ検査式で関係する共通のビットが少ない組み合わせを選択することを特徴とする。
【００２０】
本発明は、Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)に情報ビットＸ，パリティビットＰを含まない非零の多項式である変数Ａ(Ｄ)を乗算し、オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)よりも長い拘束長を持ち、オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)と等価となる変形したパリティ検査多項式Ｈ(Ｐ，Ｘ)を生成し、当該パリティ検査多項式Ｈ(Ｐ，Ｘ)の拘束長を変化させて、Sum-Productアルゴリズムを用いた復号特性の良い多項式を選択してパリティ検査式として復号することを特徴とする。
【００２１】
本発明は、上記復号器において、パリティ検査多項式Ｈ(Ｐ，Ｘ)の拘束長を変化させて、Sum-Productアルゴリズムを用いた復号特性の良い多項式を選択する際に、タナーグラフにおける長さ４のループの数が最小のものを選択することを特徴とする。
【発明の効果】
【００２２】
本発明によれば、Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して集合に追加する処理を繰り返して得られた集合からタナーグラフにおいて長さ４のループが少なく、拘束長が大きい多項式を選択してパリティ検査式として復号する復号器としているので、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できる効果がある。
【００２３】
本発明によれば、Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して集合に追加する処理を繰り返して得られた集合からパリティ検査多項式の複数をパリティ検査式として復号する復号器としているので、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できる効果がある。
【００２４】
本発明によれば、Sum-Productアルゴリズムを用いた畳み込み符号又はターボ符号の復号器であって、オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)に情報ビットＸ，パリティビットＰを含まない非零の多項式である変数Ａ(Ｄ)を乗算し、オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)よりも長い拘束長を持ち、オリジナルのパリティ検査多項式Ｈ(Ｐ，Ｘ)と等価となる変形したパリティ検査多項式Ｈ(Ｐ，Ｘ)を生成し、当該パリティ検査多項式Ｈ(Ｐ，Ｘ)の拘束長を変化させて、Sum-Productアルゴリズムを用いた復号特性の良い多項式を選択してパリティ検査式として復号する復号器としているので、簡潔かつ実用的にパリティ検査式を求めることができ、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できる効果がある。
【発明を実施するための最良の形態】
【００２５】
本発明の実施の形態について図面を参照しながら説明する。
［実施の形態の概要］
本発明の実施の形態に係る復号器は、Sum-Productアルゴリズムを用いた畳み込み符号、ターボ符号の復号器において拘束長の長い（ＨＣＬ）パリティ検査を用いて復号を行い、また、複数のＨＣＬパリティ検査を用いて復号（マルチパリティ復号）を行うものであり、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できるものである。
ここで、パリティ検査式の拘束長とは、パリティ検査多項式の最大次数に１を加えた値をいう。また、畳み符号のパリティ検査式については後述する。
【００２６】
本発明の実施の形態を説明する前に、畳み込み符号、ターボ符号におけるSum-Product復号特性の劣化原因を説明し、その対策についても説明する。
尚、本発明の実施の形態における畳み込み符号及びターボ符号では、直列連接符号を含むものである。
【００２７】
［復号特性劣化の原因］
畳み込み符号、ターボ符号における各復号法の復号に影響する情報ビット長について考える。
畳み込み符号では、ビタビ復号における復号に影響する情報ビットの長さは、拘束長の４倍とされている。
【００２８】
また、ターボ符号では、Soft Output Viterbi Algorithm（ＳＯＶＡ）における復号に影響する情報ビットの長さは、拘束長の１０倍とされている。Sum-Product復号に関しては、復号に影響する情報ビット長という考えはこれまでなかった。
【００２９】
ここで、Sum-Product復号では、遠く離れたビットの信頼度ががどのように復号に影響するかについて図１を参照しながら考えてみる。図１は、（ａ）がオリジナルのタナーグラフを示す図であり、（ｂ）がＨＣＬパリティ検査式を用いたタナーグラフを示す図である。
【００３０】
図１（ａ）に示すように、１回の処理でｉ時点のビットに関する外部値は、拘束長をＫとすると、ｉ−Ｋからｉ＋Ｋの範囲におけるビットの情報から求められる。
つまり、拘束長の２倍範囲のビットのみが外部値の計算に関係している。そのため、１回の処理では、従来の復号法に比べて復号に影響する情報が少ないといえる。Sum-Product復号では、このような局所的な信頼度伝搬を繰り返すことで、離れた時点のビットの信頼度を伝搬している。
【００３１】
しかし、途中のあるビットの信頼度が低いときには、信頼度伝搬がその時点で弱まり、離れた時点のビットへの信頼度が伝搬し難くなる。
【００３２】
そこで、１回の処理で遠くまで信頼度を伝搬する方法を考案した。影響する情報を多くするには、図１（ｂ）に示すように、拘束長の長い（High Constraint Length：ＨＣＬ）パリティ検査を用いることで可能となるので、ＨＣＬパリティ検査を用いることで復号特性の改善が期待される。
【００３３】
特に、上述のことから拘束長Ｋの２倍程度のＨＣＬパリティ検査を考えると、畳み込み符号におけるｉ時点の外部値はｉ−２Ｋ〜ｉ＋２Ｋのビットの信頼度から求まる。すなわち、拘束長の４倍の範囲のビットがビタビ復号と同様影響する。
【００３４】
そのため、畳み込み復号では、拘束長の２倍程度のＨＣＬパリティ検査を用いることで十分な特性の改善が得られると推測される。
同様に、ターボ復号を考えると、拘束長の５倍程度のＨＣＬパリティ検査を用いることで、ＳＯＶＡと同様の範囲のビットが影響するため、十分な特性の改善が得られると推測される。
ここで、ＨＣＬパリティ検査はオリジナルのパリティ検査と等価であることが重要であり、そのようなＨＣＬパリティ検査の導出を以下説明する。
【００３５】
［ＨＣＬパリティ検査の導出］
ここでは、パリティ検査式を多項式表現で考える。この多項式を使って遠くのビットまで関係したパリティ検査式を導出する。そうすれば、Sum-product復号の１回の処理で遠くまで信頼度を伝搬させることが可能になると考えた。その方法として、オリジナルのパリティ検査多項式に遅延演算子Ｄl （ｌ＝１，２，…）を掛けたパリティ検査多項式を考える。
【００３６】
そしてこれらの多項式の線形演算で得られた多項式は、Ｋ＋ｌの範囲のビットが関係した多項式となる。従って、オリジナルよりも拘束長の長いパリティ検査式となる。実際の計算手順を以下に示す。
【００３７】
［Ｓｔｅｐ１．初期設定］
まず、ステップ１（初期設定）として、ＨＣＬパリティ検査多項式の導出で得られるパリティ検査多項式の集合を、ＳH(i)，（ｉ＝０，１，…）で表す。
初回ｉ＝０の集合ＳH(0)の要素は、オリジナルのパリティ検査多項式Ｈorg（Ｄ）と遅延演算子Ｄl（ｌ＝１，…，Ｌ  Ｌ：任意）をかけたパリティ検査多項式で与えられ、以下の式（１）のように表される。
ＳH(0)＝｛Ｈ｜Ｈ＝ＤlＨorg（Ｄ），ｌ＝０，１，…，Ｌ｝  （１）
【００３８】
［Ｓｔｅｐ２．ＨＣＬパリティ検査の導出］
次に、ステップ２として、ＨＣＬパリティ検査多項式は、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式の線形演算で得られ、パリティ検査多項式の集合に追加される。ｉ回目のパリティ検査多項式の集合は以下の式（２）のように表される。
ＳH(i+l)＝｛Ｈ｜Ｈ＝Ｈj1＋Ｈj2｝  （２）
但し、Ｈj1∈ＳH(i)，Ｈj2∈ＳH(i)
Ｈj1≠Ｈj2
【００３９】
集合に含まれるパリティ検査多項式から新しいＨＣＬパリティ検査多項式が得られなくなるまでｉ←ｉ＋１としてＳｔｅｐ２を繰り返す。新しいパリティ検査多項式が得られなくなった時点でＨＣＬパリティ検査の導出を終了する。
【００４０】
また、最終的にＨＣＬパリティ検査多項式は、現時点の情報ビットとパリティビットが関係する。すなわち多項式に情報ビット：Ｘ（Ｄ）とパリティビット：Ｐ（Ｄ）が含まれる多項式のみを選ぶ。
【００４１】
例として、遅延器数２で、（７，５）8畳み込み符号器を用いて考える。過去のパリティ検査多項式として２時点過去までを考える。このとき初回の多項式集合の要素は、式（３）〜（５）となる。
（Ｄ2＋１）Ｘ（Ｄ）＋（Ｄ2＋Ｄ＋１）Ｐ（Ｄ）＝０  （３）
（Ｄ3＋Ｄ）Ｘ（Ｄ）＋（Ｄ3＋Ｄ2＋Ｄ）Ｐ（Ｄ）＝０  （４）
（Ｄ4＋Ｄ2）Ｘ（Ｄ）＋（Ｄ4＋Ｄ3＋Ｄ2）Ｐ（Ｄ）＝０  （５）
【００４２】
式（３）〜（５）の２つのパリティ検査多項式の左辺、右辺をそれぞれ足し合わせることで式（６）〜（８）が得られる。また、式（５）と式（６）を足し合わせることで式（９）を得る。
（３）＋（４）：（Ｄ3＋Ｄ2＋Ｄ＋１）Ｘ（Ｄ）
＋（Ｄ3＋１）Ｐ（Ｄ）＝０  （６）
（３）＋（５）：（Ｄ4＋１）Ｘ（Ｄ）
＋（Ｄ4＋Ｄ3＋Ｄ＋１）Ｐ（Ｄ）＝０  （７）
（４）＋（５）：（Ｄ4＋Ｄ3＋Ｄ2＋Ｄ）Ｘ（Ｄ）
＋（Ｄ4＋Ｄ）Ｐ（Ｄ）＝０  （８）
（５）＋（６）：（Ｄ4＋Ｄ3＋Ｄ＋１）Ｘ（Ｄ）
＋（Ｄ4＋Ｄ2＋１）Ｐ（Ｄ）＝０  （９）
【００４３】
式（６）と式（８）を見て分かるように、同じ多項式を遅延した多項式が得られるため、最終的には現時点の情報とパリティが関係している多項式のみをＨＣＬパリティ検査多項式として選択する。式（６）と式（８）の場合、ＨＣＬパリティ検査多項式には式（６）を選ぶ。
【００４４】
このような操作によって得られるパリティ検査多項式は、膨大な数になる。その中から、Sum-Product復号でよい特性が得られるものを求める必要があり、その評価基準は検討する必要がある。
ここでは、ＦＣ（Four Cycle：長さ４のループ）の数ｎFCと拘束長νを評価基準としており、ｎFCが少なく、νが大きいものを選択する。
【００４５】
上記方法により求めた（７，５）8，（４５，７３）8畳み込み符号のそれぞれのパリティ検査多項式に対応するＨＣＬパリティ検査多項式の８及び１０進表現を図２，図３に示す。図２は、（７，５）8畳み込み符号のＨＣＬパリティ検査多項式の特性を示す図であり、図３は、（４５，７３）8畳み込み符号のＨＣＬパリティ検査多項式の特性を示す図である。
【００４６】
ここで、ｎFCはＦＣの数、νは拘束長、ｄcはチェックノード次数、ｄv,iは情報ビットに対応する変数ノード次数、ｄv,pはパリティビットに対応する変数ノード次数を表している。どちらの符号においても、オリジナルのパリティ検査式に比べて最大で４倍の拘束長の長いＨＣＬパリティ検査式が得られた。また、（４５，７３）8畳み込み符号では、オリジナルのパリティ検査式よりも、少ないＦＣの数を持つＨＣＬパリティが得られた。
【００４７】
［シミュレーション結果］
ここでは、畳み込み符号及びターボ符号において、オリジナルのパリティ検査に対応するタナーグラフの代わりに、ＨＣＬパリティ検査の導出で求めたＨＣＬパリティ検査式に対応するタナーグラフを用いた場合のSum-Product復号の復号特性を示す。
尚、ＨＣＬパリティ検査多項式の評価は、ＦＣの数ｎFCと拘束長νで行い、（ｎFC，ν）の表記で特性を示す。
【００４８】
［畳み込み符号の復号特性］
ＨＣＬパリティ検査式に対応するタナーグラフにおける畳み込み符号のSum-Product復号の復号特性を図４に示す。図４は、畳み込み符号のＢＥＲ特性を示す図である。
ＨＣＬパリティ検査の検査基準として（７，５）8畳み込み符号においては、各ＦＣの数ｎFCで最大の拘束長νを持つ４種類のＨＣＬパリティ検査式を選択した。
【００４９】
また、（４５，７３）8畳み込み符号では、オリジナルの拘束長νの２及び３倍で、ＦＣの数ｎFCが少ない場合と大きい場合の４種類のＨＣＬパリティ検査式を選択した。
ＢＥＲ（Bit Error Rate）特性を比較すると、ＨＣＬパリティ検査を用いることで、通常のSum-Product復号と比べて特性が改善することが分かった。特に、オリジナルのパリティ検査式に対して、拘束長が２倍程度の長さがあり、ＦＣの数が少ないことで良い特性が得られることが分かった。
【００５０】
（７，５）8，（４５，７３）8畳み込み符号において、ｎFCが少ない上位１９種類のＨＣＬパリティ検査式を用いて検討した。それぞれのＨＣＬパリティ検査における、Ｅb／Ｎo＝４．５，５．０［ｄＢ］でのＢＥＲ特性を図２，図３に示す。表からも、拘束長が長く、ＦＣの数が少ないことで復号特性が良くなることが分かった。
【００５１】
これまでの結果及びＢＥＲ特性から最適なＨＣＬパリティ検査を、（７，５）8畳み込み符号では、（１４１３，１１４１）8畳み込み符号相当のパリティ検査式、（４５，７３）8畳み込み符号では、（３１０１，２００７）8畳み込み符号相当のパリティ検査式とした。
【００５２】
［ターボ符号の復号特性］
次に、上記畳み込み符号の復号特性と同様のＨＣＬパリティ検査式を用いて、ターボ符号のSum-Product復号を行う。
ターボ符号のSum-Product復号におけるoverall，turbo-like復号の復号特性をそれぞれ図５、図６に示す。図５は、ターボ符号のＢＥＲ特性（overall復号）を示す図であり、図６は、ターボ符号のＢＥＲ特性（turbo-like復号）を示す図である。
ここで、turbo-like復号の内部繰り返しは１０回とした。また、チェックノードから変数ノードへの信頼度情報に対して、最適化したスケーリング値０．７を掛け合わせている。
【００５３】
ＨＣＬパリティ検査式を用いることで、オリジナルのパリティ検査式と比べてＢＥＲ特性が劣化することが分かった。
また、overall復号とturbo-like復号の復号特性を比較すると、ＢＥＲ特性から、turbo-like復号が優れていることが分かった。turbo-like復号では、要素符号器毎にＦＣが影響するのに対し、overall復号では２つの要素符号器を合わせたタナーグラフのＦＣが影響する。
従って、overall復号の方が特性の影響するＦＣの数が多くなっているのではないかと考えられる。
【００５４】
用いるＨＣＬパリティの拘束長がオリジナルのパリティの拘束長の５倍とすれば、復号特性の改善が可能であると期待される。遅延器数５，（４５，７３）8畳み込み符号の場合、拘束長ν＝６×５＝３０のＨＣＬパリティが必要であるが、このようなＨＣＬパリティ検査式の導出は図７に示すように時間的に困難である。図７は、拘束長νのＨＣＬパリティ検査式導出の所要時間を示す図である。
そこで、次に、拘束長を長くすることとは別の視点で、復号特性の改善策を説明する。
【００５５】
［複数のＨＣＬパリティ検査多項式を用いた復号（マルチパリティ復号）］
上記畳み込み符号の復号特性では、ターボ符号の復号に用いるＨＣＬパリティ検査式の拘束長の５倍に満たないため、特性が改善しないことを説明した。拘束長の５倍となるＨＣＬパリティの導出は困難であり、ここでは別の方法を説明する。
【００５６】
ここで、復号特性劣化の原因を再度思い起こすと、信頼度伝搬において、低い信頼度のビットの存在により、離れた時点のビットへの信頼度伝搬がしにくくなることが特性劣化の影響と考えていた。
そこで、このようなビットの信頼度を高めることができるなら、特性が改善すると考えた。ビットの信頼度を高めるには、他のビットからの信頼度が多く伝搬されることで可能であると考えられる。
【００５７】
図８（ａ）で、例えば、｜Ｌ（ｘ2）｜が小さい時には、Ｕc1,x1は小さい値となる。もし、図８（ｂ）のように別のパリティ検査ｃ2があれば、Ｕc1,x1が小さい値であったとしても、Ｕc2,x1によって、｜Ｌe（ｘ1）｜＝｜Ｕc1,x1＋Ｕc2,x1｜が小さな値をとる確率を減らすことができる。図８は、用いるパリティに対する信頼度伝搬の影響を示す図である。
【００５８】
そのため、パリティ検査を複数用いた復号（マルチパリティ復号）により、信頼度を高めることができると考えられる。また、これにより、ビットの信頼度が離れたビットまで伝搬し、復号特性が改善するのではないかと考えた。
ここで、用いるパリティはオリジナルのパリティ検査と等価である必要があるため、既に求めているＨＣＬパリティ検査式を用いることにした。
【００５９】
図９のように、ｃ2がｃ1と共通な変数ノードを含んでいる場合には、外部値Ｌe（ｘ1）が小さな値をとる確率は、図８（ｂ）の場合より高くなる。図９は、マルチパリティのビットの重なりを示す図である。
例えば、図９の場合、｜Ｌ（ｘ3）｜が小さい時には、Ｕc1,x1，Ｕc2,x1ともに小さい値となり、｜Ｌe（ｘ1）｜も小さな値となってしまう。
【００６０】
そこで、用いるＨＣＬパリティ検査には、それぞれのパリティ検査で共通するビットの数が少ないＨＣＬパリティ検査を選択することにした。
また、共通するビットの数はＦＣの数ｎFCに対応があるが、ここで用いるｎFCの導出法では、複数のパリティ検査多項式を用いる場合のタナーグラフにおけるｎFCを求めることはできない。そのため、それぞれのパリティ検査で共通するビットの数で評価する。
【００６１】
［復号器構成］
次に、本発明の実施の形態に係る復号器について図１０〜図１３を参照しながら説明する。図１０は、ＨＣＬパリティ検査式を用いた畳み込み符号の復号器の構成図であり、図１１は、マルチパリティ復号を用いた畳み込み符号の復号器の構成図であり、図１２は、ＨＣＬパリティ検査式を用いたターボ符号の復号器の構成図であり、図１３は、マルチパリティ復号を用いたターボ符号の復号器の構成図である。
【００６２】
図１０〜図１３において、ＤＥＣは要素復号器であり、ＨＣＬパリティ検査式を用いた復号を行う。また、図１１、図１３においては、分割した要素復号器で並列処理を行っている。尚、Πは、符号系列を並び替えるインタリーバであり、Π-1は、符号系列を元に戻すよう並び替えるディインタリーバである。
【００６３】
復号器は、畳み込み符号の場合、上述したＨＣＬパリティ検査によって選択された多項式が予め設定され、また、ターボ符号の場合、マルチパリティ復号によって選択された複数の多項式の各々が予め設定されている。
また、復号器は、例えば、ＬＳＩ（Large Scale Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）、ＤＳＰ（Digital Signal Processor）等で実現されるものである。
【００６４】
尚、復号器は、以下の文献に示されているように実現されるものである。
Optimizing iterative decoding of low-density 
parity check codes on programmable pipelined 
parallel architectures Al-Rawi, G. ; Cioffi, J. ;Motwani, R. ; Horowitz, M. ; Global Telecommunications Conference, 2001. GLOBECOM 01. IEEE Volume 5, 25-29 Nov. 2001 Page(s): 3012-3018 vol.5
【００６５】
ここで、図１３におけるマルチパリティ復号を用いたターボ符号の復号器の構成について具体的に説明する。
復号器の構成として、要素復号器を用いるＨＣＬパリティ検査のそれぞれに対応する復号器に分割する。復号では、この分割した復号器を直列又は並列で処理を行う。ここでは、並列処理の方が、復号特性が良かったため、図１３では並列処理を採用している。
【００６６】
図１３に示す復号器は、復号器（ＤＥＣ１）１１′と、復号器（ＤＥＣ２）１２′と、インタリーバ（Π）１３と、ディンタリーバ（Π-1）１４と、ηを乗算する乗算器１５，１６と、Ｌc2を加算する加算器１７とを備え、復号器１１′、１２′内には分割された複数の要素復号器１１-1〜１１-M，１２-1〜１２-Mとそれらの出力を加算する加算器１１０，１２０が設けられている。
【００６７】
尚、Ｍは用いるＨＣＬパリティ検査数、ＤＥＣ１(・)、ＤＥＣ２(・)は分割した復号器、Ｌe1(・)，Ｌe2(・)は分割した復号器で出力される外部値を表している。
要素復号器には、事前値Ｌa，通信路値Ｌcが入力される。また、復号器では、分割したそれぞれの復号器でSum-Product復号が一斉に行われる。
【００６８】
復号器で得られたそれぞれの外部値Ｌe(・)は、各ビットに対して足し合わせられ、要素復号器の外部値Ｌeとして出力される。
また、要素復号器２では、得られた外部値から情報ビットｄnに対する事後値Λ2(ｄn)を
Λ2(ｄn)＝Ｌa2(ｄn)＋Ｌc2(ｄn)＋Ｌe2(ｄn)  （１０）
で求め、得られた事後値の正／負で硬判定する。
【００６９】
ここで、Ｋ種類のＨＣＬパリティ検査を用いる場合を考えると、得られた要素復号の外部値は、それぞれの分割した復号で得られる外部値に対して、最大でＭ倍程度の大きさになると考えられる。
十分な復号が行われていない場合、このような外部値は誤った情報である可能性があり、この値を次段の事前値とすることで、特性の劣化を引き起こすと考えられる。
そこで、要素復号器の外部値に対してη≒１／Ｍ程度のスケーリングをかけ、次段の要素復号器の事前値とすることにした。
【００７０】
［ターボ符号の復号特性］
ターボ符号のマルチパリティ復号の復号特性を示す。用いるパリティ検査としては、オリジナルのパリティ検査多項式とＦＣの数が少ない上位１０種類のＨＣＬパリティ検査多項式を候補とする。この候補の中から、３種類のパリティ検査多項式を選択して復号を行う。
【００７１】
はじめに、Ｅb／Ｎoを固定して、候補の中から３種類のパリティ検査多項式を選択する全ての組み合わせに対してマルチパリティ復号を行った。
（７，５）8畳み込み符号を要素符号とするターボ符号では、Ｅb／Ｎo＝３．０［ｄＢ］で、（４５，７３）8畳み込み符号を要素復号とするターボ符号では、Ｅb／Ｎo＝２．５［ｄＢ］で復号を行った結果、良いＢＥＲ特性が得られた上位５種類の組み合わせを図１４に示す。図１４は、マルチパリティ復号に用いるパリティ検査の組み合わせを示す図である。
ここで、それぞれのターボ符号で、チェックノードから変数ノードへの信頼度情報に対して最適化したスケーリング値０．７，０．９を掛け合わせている。
【００７２】
全ての組み合わせに対して復号を行った結果、用いられるパリティ検査式として、オリジナルのパリティ検査、若しくは、求めたＨＣＬパリティ検査のなかで拘束長の短いパリティ検査が最低１つ含まれる組み合わせを選ぶ必要があることが分かった。
【００７３】
ここで、各組み合わせにおいて、用いるパリティ検査式の関係する共通のビットの数に対するＢＥＲの関係を図１５に示す。図１５は、共通のビットの数に対するＢＥＲの関係を示す図である。図１５の→で指しているプロット点は、図１４の組み合わせに対応している。
【００７４】
この特性から、（７，５）8畳み込み符号を要素符号とするターボ符号において、最も良い特性となる組み合わせは、共通のビットが少ない組み合わせで得られていることが分かる。また、（４５，７３）8畳み込み符号を要素符号とするターボ符号において、最も良い特性となる組み合わせは、共通のビットが少ない組み合わせとはならなかったが、ビットの重なりが少ない組み合わせでも同等の特性が得られていることが分かる。
【００７５】
そのため、マルチパリティ復号に用いるパリティ検査では、それぞれのパリティ検査多項式で関係する共通のビットが少ない組み合わせを選ぶ必要があることが分かった。
【００７６】
次に、図１４で示した、最も良い特性が得られる組み合わせを用いたマルチパリティ復号の復号特性を図１６に示す。図１６は、ターボ符号のＢＥＲ特性を示す図である。得られた特性を通常のSum-Product復号と比較すると、マルチパリティ復号により、（７，５）8畳み込み符号を要素符号とするターボ符号において、ＢＥＲ＝１０-3のＥb／Ｎoが０．５［ｄＢ］の改善が得られ、（４５，７３）8畳み込み符号を要素符号とするターボ符号において、ＢＥＲ＝１０-4のＥb／Ｎoが０．４［ｄＢ］の改善が得られた。
【００７７】
特に、マルチパリティ復号は、error floor領域の特性改善に効果があることが分かった。また、マルチパリティ復号に用いるパリティ検査式数を増やすことで、復号特性が更に改善することが分かっている。
増やしたパリティ検査数の分だけ処理量は倍増するが、特性が良くなり、その分だけ早く復号が終了すると考えられるため、ＢＥＲ特性の兼ね合いで用いるパリティ検査式数を増やしていけば良いと考えられる。
【００７８】
本発明の実施の形態に係る復号器によれば、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できる効果がある。
【００７９】
［畳み符号のパリティ検査式］
次に、補足として、畳み符号のパリティ検査式について説明する。
符号化率１／２，生成行列Ｇの畳み符号を考える。
Ｇ＝［１  Ｇ1(Ｄ)／Ｇ0(Ｄ)］    （１１）
ここで、Ｇ1はフィードフォーワード多項式、Ｇ0はフィードバック多項式を表している。情報系列の多項式表現を、Ｘ(Ｄ)＝ｘ0＋ｘ1Ｄ＋ｘ2Ｄ2＋・・・、パリティ系列の多項式表現をＰ(Ｄ)＝ｐ0＋ｐ1Ｄ＋ｐ2Ｄ2＋・・・とする。また、簡単のために、Ｘ，Ｐと表す場合もある。
【００８０】
パリティ検査式Ｈ(Ｘ，Ｐ)は、
Ｈ(Ｘ，Ｐ)＝Ｇ1(Ｄ)Ｘ(Ｄ)＋Ｇ0(Ｄ)Ｐ(Ｄ)    （１２）
で表される。Ｈ(Ｘ，Ｐ)＝０ならば、(Ｘ，Ｐ)は符号語であり、それ以外の場合、(Ｘ，Ｐ)は符号語ではない。
【００８１】
また、Ｈ(Ｘ，Ｐ)に基づいてタナーグラフを得ることができる。また、Ｇ1(Ｄ)，Ｇ0(Ｄ)の最大次数に１を加えた値をパリティ検査式の拘束長νと呼ぶことにする。
【００８２】
［拘束長の長いパリティ検査式］
上記実施の形態では、パリティ検査多項式の集合に含まれる任意の２つのパリティ検査多項式を線形演算して、新たに得られたパリティ検査多項式を前記集合に追加し、当該集合に含まれるパリティ検査多項式から線形演算により新しいパリティ検査多項式が得られなくなるまで、任意の２つのパリティ検査多項式を線形演算して集合に追加する処理を繰り返して得られた集合からタナーグラフにおいて長さ４のループが少なく、拘束長が大きい多項式を選択してパリティ検査式として復号するようになっているが、このように選択されるパリティ検査式と等価であり、簡潔かつ実用的なパリティ検査式の求め方について説明する。
【００８３】
タナーグラフは、パリティ検査式Ｈ(Ｘ，Ｐ)をグラフ表現したものであるから、Ｈ(Ｘ，Ｐ)と等価なパリティ検査式を求めればよい。等価なパリティ検査式Ｈ'(Ｘ，Ｐ)を求める方法として、次の方法を提案する。
【００８４】
Ｈ'(Ｘ，Ｐ)＝Ａ(Ｄ)Ｈ(Ｘ，Ｐ)    （１３）
＝Ａ(Ｄ)Ｇ1(Ｄ)Ｘ(Ｄ)＋Ａ(Ｄ)Ｇ0(Ｄ)Ｐ(Ｄ)    （１４）
＝Ｇ'1(Ｄ)Ｘ(Ｄ)＋Ｇ'0(Ｄ)Ｐ(Ｄ)    （１５）
ここで、
Ｇ'0(Ｄ)＝Ａ(Ｄ)Ｇ0(Ｄ)    （１６）
Ｇ'1(Ｄ)＝Ａ(Ｄ)Ｇ1(Ｄ)    （１７）
【００８５】
Ａ(Ｄ)は、変数ノード列であり、Ｘ，Ｐを含まない非零の多項式である。ここで、Ｈ(Ｘ，Ｐ)をオリジナルのパリティ検査式と呼ぶことにすると、上記のようにして得られたＨ'(Ｘ，Ｐ)はオリジナルのパリティ検査式Ｈ(Ｘ，Ｐ)と等価であるといえる。何故なら、次式が成立するからである。
【００８６】
Ｈ'(Ｘ，Ｐ)＝Ａ(Ｄ)Ｈ(Ｘ，Ｐ)＝０
iff  Ｈ(Ｘ，Ｐ)＝０    （１８）
Ｈ'(Ｘ，Ｐ)＝Ａ(Ｄ)Ｈ(Ｘ，Ｐ)≠０
iff  Ｈ(Ｘ，Ｐ)≠０
この式が成立することは、Ａ(Ｄ)がＸ，Ｐを含まない非零の多項式であることから明らかである。
【００８７】
式（１５）〜（１７）から、Ｈ'(Ｘ，Ｐ)は、オリジナルのパリティ検査式Ｈ(Ｘ，Ｐ)よりも長い拘束長を持つことが分かる。そこで、Ｈ'(Ｘ，Ｐ)を拘束長の長いパリティ検査式（ＨＣＬ−ＰＣＥ）と呼ぶことにする。
また、式（１５）〜（１７）から、Ｈ'(Ｘ，Ｐ)の拘束長νはＡ(Ｄ)の最大次数でコントロールできることが分かる。
【００８８】
どのようなＨ'(Ｘ，Ｐ)がＳＰＡに適しているのかについて、制御可能な拘束長νを変化させてヒューリスティックにＳＰＡ復号特性が改善するものを求める。その方法は次の通りである。
Ａ(Ｄ)の最大次数を設定したとき、可能な全てのＡ(Ｄ)を用いてＨ'(Ｘ，Ｐ)を求める。そうすると、設定した拘束長を持つＨ'(Ｘ，Ｐ)が多数得られる。この全てに対してシミュレーションを行うのは現実的ではないので、この中から１つのＨＣＬ−ＰＣＥを選択してシミュレーションを行う。その選択には、チェックノード当たりのＦＣ数ｎFCを用い、上記提案法で得られたＨ'(Ｘ，Ｐ)はＦＣを含んでおり、ｎFCが最小のものを選択することは妥当である。尚、拘束長νとＦＣ数ｎFCのどちらも同じＨＣＬ−ＰＣＥが複数存在した場合には、任意にその中の一つを選択する。
【００８９】
上記のように、パリティ検査式の拘束長を延ばす等価な変形により得られるパリティ検査の中からヒューリスティックに良いＳＰＡ復号特性が得られるパリティ検査式を求め、それを用いてＳＰＡ復号を行うようにすれば、復号特性の改善が期待できる。
また、この方法を適用したターボ符号のSum-Product復号では、ＢＥＲ特性の改善が期待できる。
【産業上の利用可能性】
【００９０】
本発明は、畳み込み符号、ターボ符号におけるSum-Product復号特性を改善できる畳み込み符号及びターボ符号の復号器に好適である。
【図面の簡単な説明】
【００９１】
【図１】（ａ）がオリジナルのタナーグラフを示す図であり、（ｂ）がＨＣＬパリティ検査式を用いたタナーグラフを示す図である。
【図２】（７，５）8畳み込み符号のＨＣＬパリティ検査多項式の特性を示す図である。
【図３】（４５，７３）8畳み込み符号のＨＣＬパリティ検査多項式の特性を示す図である。
【図４】畳み込み符号のＢＥＲ特性を示す図である。
【図５】ターボ符号のＢＥＲ特性（overall復号）を示す図である。
【図６】ターボ符号のＢＥＲ特性（turbo-like復号）を示す図である。
【図７】拘束長νのＨＣＬパリティ検査式導出の所要時間を示す図である。
【図８】用いるパリティに対する信頼度伝搬の影響を示す図である。
【図９】マルチパリティのビットの重なりを示す図である。
【図１０】ＨＣＬパリティ検査式を用いた畳み込み符号の復号器の構成図である。
【図１１】マルチパリティ復号を用いた畳み込み符号の復号器の構成図である。
【図１２】ＨＣＬパリティ検査式を用いたターボ符号の復号器の構成図である。
【図１３】マルチパリティ復号を用いたターボ符号の復号器の構成図である。
【図１４】マルチパリティ復号に用いるパリティ検査の組み合わせを示す図である。
【図１５】共通のビットの数に対するＢＥＲの関係を示す図である。
【図１６】ターボ符号のＢＥＲ特性を示す図である。
【符号の説明】
【００９２】
１…復号器（要素復号器）、  １１，１１′…復号器、  １２，１２′…復号器、  １３…インタリーバ、  １４…ディインタリーバ、  １５，１６…乗算器、  １７…加算器、  １１０，１２０…加算器
【図１】
2008271516.tif 000003
【図２】
2008271516.tif 000004
【図３】
2008271516.tif 000005
【図４】
2008271516.tif 000006
【図５】
2008271516.tif 000007
【図６】
2008271516.tif 000008
【図７】
2008271516.tif 000009
【図８】
2008271516.tif 000010
【図９】
2008271516.tif 000011
【図１０】
2008271516.tif 000012
【図１１】
2008271516.tif 000013
【図１２】
2008271516.tif 000014
【図１３】
2008271516.tif 000015
【図１４】
2008271516.tif 000016
【図１５】
2008271516.tif 000017
【図１６】
2008271516.tif 000018