(57)【特許請求の範囲】
【請求項１】
伝送チャネルから受信された、次元ｋと長さｎのブロック線形符号の語（ｓ）のソフト入力ソフト出力式復号化方法であって、
最尤推定値のｋ項組のリストを符号化することによって、受信された符号語（ｓ）に近い符号のファーム語（ｕb）のリストを生成するステップと、
最も近い生成された符号語の距離とｊ番目の反対の正負符号の構成要素を有する最も近い生成された符号語の距離との差によって出力ソフト語のｊ番目の構成要素を計算するステップと、
を含む方法。
【請求項２】
最尤推定値のｋ項組が、受信された語の構成要素のファーム近似を行うことによって、および最も信頼性の低い構成要素を変えることによって得られることを特徴とする請求の範囲第１項に記載の方法。
【請求項３】
ｋ項組のリストのｋ項組の各々が、
受信された符号語の構成要素を、置換（Ｔ）に従って信頼性順に分類し、
このようにして得られた語のｋ個の最も信頼性の高い構成要素が他のｎ−ｋ個の構成要素の生成を可能にすることを検査し、
前記ｋ個の構成要素のうちのｍ個の最も信頼性の低い構成要素についてファーム値を選択し（ｍはｋより小さい整数である）、
他のｋ−ｍ個の構成要素のファーム近似を行い、
このようにして得られたファーム語を、前記置換の逆置換による、前記符号の構成に等しい符号によって符号化する、
ことによって得られる請求の範囲第１項または第２項に記載の方法。
【請求項４】
検査が、
符号のパリティ行列の列に置換を適用し、
このようにして置換されたパリティ行列の最後のｎ−ｋ個の列で形成された行列の階数を検査する、
ことによって行われる請求の範囲第３項に記載の方法。
【請求項５】
検査ステップがネガティブであるときは、検査ステップの後に置換の変更ステップが続く請求の範囲第３項または第４項に記載の方法。
【請求項６】
ｋ項組のリストのｋ項組の各々が、
受信された符号語の最初のｋ個の構成要素を置換（Ｔ）によって信頼性順に分類し、
ｍ個の最も信頼性の低い構成要素についてファーム値を選択し（ｍはｋより小さい整数である）、
他のｋ−ｍ個の構成要素のファーム近似を行い、
このようにして得られたファーム語を、前記置換の逆置換による、前記符号の構成に等しい符号によって符号化する、
ことによって得られる請求の範囲第１項または第２項に記載の方法。
【請求項７】
出力ソフト語のｊ番目の構成要素の計算が、ｊ番目の反対の正負符号の構成要素を有する最も近い生成された符号語が存在していないときは、最も近い生成された符号語の距離と最も遠い生成された符号語の距離との差によって行われる請求の範囲第１項から第６項のいずれか一項に記載の方法。
【請求項８】
出力ソフト語のｊ番目の構成要素の計算が、ｊ番目の反対の正負符号の構成要素を有している最も近い生成された符号語が存在していないときは、受信された語のｊ番目の構成要素に、受信された語に最も近い符号語のｊ番目の構成要素のファームデシジョンの正負符号が割り当てられた係数を加えることによって行われることを特徴とする請求の範囲第１項から第６項のいずれか一項に記載の方法。
【請求項９】
受信された語が、ガウス型白色雑音によって影響を受けていることを特徴とする請求の範囲第１項から第８項のいずれか一項に記載の方法。
【請求項１０】
伝送チャネルから受信された、次元ｋと長さｎのブロック線形符号の語（ｓ）のソフト入力ソフト出力式復号化方法であって、
受信された符号語（ｓ）に近い符号のファーム語（ｕｂ）であって、最尤推定値のｋ項組のリストを符号化することによって生成されたファーム語（ｕｂ）のリストから、受信された語に最も近い符号語を選択するステップと、
受信された語のｊ次の各構成要素について（ｊは１からｎまで変化する）、
最も近い前記符号語のｊ番目の構成要素を逆にして、受信された語のｊ番目の構成要素を置き換えるステップと、
置き換えステップで得られた語に最も近い符号語を、置き換えステップで得られた符号語に近い符号のファーム語であって、最尤推定値のｋ項組のリストを符号化することによって生成されたファーム語のリストから、選択するステップと、
出力ソフト語のｊ番目の構成要素を、受信された語に最も近い符号語の距離と置き換えステップで得られた語に最も近い符号語の距離との差によって計算するステップと、
を含む方法。
【請求項１１】
受信された語に最も近い符号語を選択するステップにおいて、最尤推定値のｋ項組が、受信された語の最も信頼性の高い構成要素のファーム近似を行うことによって、および最も信頼性の低い構成要素を変えることによって得られることを特徴とする請求の範囲第１０項に記載の方法。
【請求項１２】
置き換えステップで得られた語に最も近い符号語を選択するステップにおいて、最尤推定値のｋ項組が、置き換えステップで得られた語の最も信頼性の高い構成要素のファーム近似を行うことによって、および最も信頼性の低い構成要素を変えることによって得られることを特徴とする請求の範囲第１０項または第１１項に記載の方法。
【請求項１３】
受信された語が、ガウス型白色雑音によって影響を受けていることを特徴とする請求の範囲第１０項から第１２項のいずれか一項に記載の方法。
【請求項１４】
伝送チャネルから受信された積符号の語（Ｒ）の反復復号化方法であって、請求の範囲第１項から第１３項のいずれか一項の方法による、少なくとも１回反復する、積符号の前記語の行または列のソフト入力ソフト出力式復号化とを含む方法。
【発明の詳細な説明】
本発明は、積符号の反復復号化（デコーディング）方法を目的とする。また、本発明は、伝送方法、ならびにこのような復号化方法を用いた伝送システムに関する。
本発明は、ブロック線形符号の積符号の復号化に関する。本発明は、チャネル符号化（コーディング）について、伝送分野に適用される。典型的な伝送チャネルは、バイナリ情報源、符号器、チャネル内で送信する変調器、チャネルの出力側に位置する復調器、およびバイナリ信号を提供する復号器を含む。チャネル符号化は、所与のビット誤り率に達するのに必要なパワーを減らすことを目的としている。「特にＡＴＭセルに適用可能な積符号によるブロック符号化方法」という題名のもとで１９９７年１０月９日に提出されたフランス特許出願第９７１２５９４号は、伝送とチャネル符号化の基本概念について記載している。さらなる詳細については、この特許出願を参照することができるであろう。本発明が、チャネル復号化に関する限りにおいて、伝送システムのその他の要素（情報源の符号化や、伝送媒体に応じて使用される変復調等）は、さらなる説明の対象にならない。
符号化については、冗長符号や積符号を使用することが普通である。一般に、Ｃ1符号は、３項組（ｎ1、ｋ1、ｄ1）によって特徴づけられる。ここに、ｋ1は符号の入力時のビット数であり、ｎ1は符号の出力時のビット数であり、ｄ1は符号の最小ハミング距離である。このような符号をｋ項組（ｘ1、．．．、ｘk）に適用することによって、ｎ−ｋ個の冗長ビットをもつｎ項組（ｘ１、．．．、ｘk、ｘk+1、．．．、ｘn）が提供される。
Ｃ1符号とＣ2符号の２つを次のような方法で連続的に適用することを積符号と呼んでいる。各々がｋ1個のビットで構成されたｋ2個の語の形でｋ1．ｋ2個のビットを考える。ｋ1個のビットで構成されたｋ2個の語にＣ1（ｎ1、ｋ1、ｄ1）符号を適用して、ｎ1個のビットで構成されたｋ2個の語を得る。ｎ1個のビットで構成されたこれらのｋ2個の語は、行列（マトリックス）の形で並べられ、ｎ1個の列を形成する。ｊ番目の列は各ｋ2個の語のｊ番目のビットで形成される。ｋ2個のビットで構成されたこれらのｎ1個の列の各々にＣ2（ｎ2、ｋ2、ｄ2）符号を適用して、ｎ2個のビットで構成されたｎ1個の語を得る。このような積符号を適用することによって、ｋ1．ｋ2個のビットを、ｎ1．ｎ2−ｋ1．ｋ2個の冗長ビットをもつｎ1．ｎ2個のビットにすることができる。もし符号が線形であるならば、したがってＣ1符号のｎ2個の語の行かＣ2符号のｎ1個の語の列が得られる。積符号はパラメータ（ｎ1．ｎ2；ｋ1．ｋ2；ｄ1．ｄ2）を有する符号である。符号化順序は重要でなく、上述のように、最初に行を符号化しようとも最初に列を符号化しようとも同じ結果が得られる。このような積符号は、チャネル符号化についての文献の中に記載されている。上記フランス特許出願あるいはＦＲ−Ａ−２７１２７６０の第２図は、このような積符号による符号化原理について詳細に説明している。
このような積符号での問題は、復調器の出力部における復号化である。復調器の出力部において（一般に±１の形で変調された）ビット値の集合が得られるが、これらのビット値には雑音が伴う。雑音を伴って受信された値を「ソフト値」と呼んでいる。この値は実数である。値±１を、すなわち受信された値についての閾値による決定によって得られた、対応するバイナリ値を「ファーム値」と呼んでいる。以下においては、バイナリの語を「ファーム語」と呼び、実際に受信された語であって、実数で形成された語を「ソフト語」と呼ぶ。
積符号による符号化を用いた伝送の際に、復調器の出力部においてｎ1．ｎ2個の実数（ソフト値）の集合Ｒ＝｛ｒi，j｝が得られる。復号化は、Ｃ1．Ｃ2積符号のどの語に、これらのソフト値が対応しているかを、ある性能基準に従って決定することからなる。もし雑音がガウス型白色雑音による影響であるならば、最適な解決法は受信されたソフト語Ｒまでのユークリッド距離を最小化する積符号の語を探索することからなる。この最尤推定の基準は、事実上不可能である。なぜならば、積ｋ1．ｋ2は一般に数百個を超えるからである。
したがって、積符号の復号化を確保するために様々な解決法が提案された。最も即時的な解決法は、列についてＣ2符号の復号器を、次に行についてＣ1符号の復号器を適用することによって、行を、次に列を、ファーム決定（ファームデシジョン）で順次復号化することからなるが、この解決法は最適であるにはほど遠く、伝送チャネルから受信された全情報を使用しないので、積符号の理論上の結果を達成することができない。
ＦＲ−Ａ−２７１２７６０は、Ｃ1．Ｃ2積符号の反復復号化アルゴリズムを提供している。このアルゴリズムでは、受信された積符号語から形成された行列の様々な列または行の復号化が連続かつ反復してなされる。各列または行について、すなわち雑音を伴い受信されたＣ2またはＣ1符号の各語（受信されたソフト語）について、この文献は、変更されたＣｈａｓｅアルゴリズムを用いて復号化を行うことを提案している。より正確には、
−  受信されたソフト語に一見したところ近いＣ2符号またはＣ1符号のファーム語の集合を対応する行または列上において生成し、
−  これらの様々なファーム語と受信されたソフト語とのユークリッド距離を計算し、
−  これらの様々なファーム語のうちから、実際に受信されたソフト語までの最小距離を有するファーム語を、受信された符号語として選択することを提案している。
受信されたソフト語に一見したところ近いＣ2（またはＣ1）符号のファーム語の集合を生成するには、この文献は、
−  受信されたソフト語の最も信頼性の低いｐ個の構成要素をマークし、
−  これらｐ個の最も信頼性の低い構成要素からｑ個のテストバイナリシーケンスを構築し、
−  これらのテストバイナリシーケンスと復号化された語の現在のバイナリ値から、復号化すべきｑ個のバイナリ語を構築し（この現在のバイナリ値は、受信された各ビットのバイナリ近似によってスタート時に初期化される）、
−  Ｂｅｒｋｅｌａｍｐ復号器（代数復号器）を用いて、ｑ個のバイナリ語を復号化して、ｑ’個の符号語を得ることを、そして必要があれば、得られたｑ’個の語がＣ2（またはＣ1）符号語であることを検査することを提案している。
ｑ個のバイナリ語の構築と上記アルゴリズムによるそれらの復号化は、あまり効果的な作業ではない。つまり、ｑ個の生成された語は、Ｃ2（またはＣ1）符号の語ではあるが、必ずしも別個のものであるわけではない。復号器の出力部において、ｑ個の生成された語より少ないｑ’個の別個の符号語が得られる。
それに、この方法は、代数復号器が存在する符号についてしか機能しない。代数復号器の実行は、ガロア（Ｇａｌｌｏｉｓ）体における計算や複雑なアーキテクチャを必要とする。
Ｊｕｉｎｇ  Ｆａｎｇは、１９８６年に国立パリ高等電信学校（ＥＮＳＴ）のエンジニア博士論文「ブロック線形符号の重み付き復号化」の中で、ブロック線形符号のソフト入力式復号化アルゴリズムについて記載している。このアルゴリズムは、最尤推定という意味において最適であり、符号の代数的構造を明白に関与させない。このアルゴリズムは、最尤推定値を有するファーム符号語を出力部において提供することを可能にするものであり、多くのソフト入力ファーム出力式復号化アルゴリズムの１つであるが、ソフト出力を生成するのにリストの使用を示唆していない。
本発明は、より迅速であり、かつより効果的である復号化を可能にする、また代数復号器が存在する符号のみならず、あらゆるタイプの符号に適用される積符号の反復復号化に解決方法を提供する。
積符号の復号化は、数学的問題ではなく、伝送分野における重要な技術的問題である。この復号化は、伝送チャネルの復調器の出力部で受信された積符号のビットまたは語の値の復号化に直接適用される。
より正確には、本発明は伝送チャネルから受信された、次元ｋと長さｎのブロック線形符号の語（ｓ）のソフト入力ソフト出力式復号化方法であって、
−  最尤推定値ｋ項組のリストを符号化することによって、受信された符号語（ｓ）に近い符号のファーム語（ｕb）のリストを生成するステップと、
−  最も近い生成された符号語の距離と、ｊ番目の反対の正負符号の構成要素を有する最も近い生成された符号語の距離との差によって出力ソフト語のｊ番目の構成要素を計算するステップとを含む方法を提供する。
一実施形態では、最尤推定値ｋ項組は、受信された語の構成要素のファーム近似を行うことによって、および最も信頼性の低い構成要素を変えることによって得られる。
有利には、ｋ項組のリストのｋ項組の各々は、
−  受信された符号語の構成要素を、置換（Ｔ）に従って、信頼性順に分類し、
−  このようにして得られた語のｋ個の最も信頼性の高い構成要素が、他のｎ−ｋ個の構成要素の生成を可能にすることを検査し、
−  前記ｋ個の構成要素のうちのｍ個の最も信頼性の低い構成要素について、ファーム値を選択し（ｍはｋより小さい整数である）、
−  他のｋ−ｍ個の構成要素のファーム近似を行い、
−  前記置換の逆置換による前記符号の構成に等しい符号によって、こうして得られたファーム語を、符号化する。
また、検査は、
−  符号のパリティ行列の列に置換を適用し、
−  このようにして置換されたパリティ行列の最後のｎ−ｋ個の列で形成された行列の階数を検査することによって行われるようにすることもできる。
検査ステップが、ネガティブであるときは、検査ステップの後に置換の変更ステップが続く。
別の実施形態では、ｋ項組のリストのｋ項組の各々は、
−  受信された符号語の最初のｋ個の構成要素を置換（Ｔ）によって信頼性順に分類し、
−  ｍ個の最も信頼性の低い構成要素についてファーム値を選択し（ｍはｋより小さい整数である）、
−  他のｋ−ｍ個の構成要素のファーム近似を行い、
−  このようにして得られたファーム語を、前記置換の逆置換による前記符号の構成に等しい符号によって符号化する、ことによって得られる。
好ましくは、出力ソフト語のｊ番目の構成要素の計算は、ｊ番目の反対の正負符号の構成要素を有する最も近い生成された符号語が存在していないときは、最も近い生成された符号語の距離と最も遠い生成された符号語の距離との差によって行われる。
また、出力ソフト語のｊ番目の構成要素の計算は、ｊ番目の反対の正負符号の構成要素を有している最も近い生成された符号語が存在していないときは、受信された語のｊ番目の構成要素に、受信された語に最も近い符号語のｊ番目の構成要素の正負符号が割り当てられた係数を加えることによって行われるようにすることもできる。
有利には、受信された語はガウス型白色雑音によって影響を受けている。
本発明は、伝送チャネルから受信された、次元ｋと長さｎのブロック線形符号の語（ｓ）のソフト入力ソフト出力式復号化方法であって、
−  受信された符号語（ｓ）に近い符号のファーム語（ｕｂ）であって、最尤推定値のｋ項組のリストを符号化することによって生成されたファーム語（ｕｂ）のリストから、受信された語に最も近い符号語を選択するステップと、
−  受信された語のｊ次の各構成要素について（ｊは１からｎまで変化する）、
＊より近い前記符号語のｊ番目の構成要素を逆にして、受信された語のｊ番目の構成要素を置き換えるステップと、
＊置き換えステップで得られた語に最も近い符号語を、置き換えステップで得られた符号語に近い符号のファーム語であって、最尤推定値のｋ項組のリストを符号化することによって生成されたファーム語のリストから選択するステップと、
＊出力ソフト語のｊ番目の構成要素を、受信された語に最も近い符号語の距離と置き換えステップで得られた語に最も近い符号語の距離との差によって計算するステップを含む方法も目的とする。
一実施形態では、受信された語に最も近い符号語を選択するステップにおいて、最尤推定値のｋ項組は、受信された語の最も信頼性の高い構成要素のファーム近似を行うことによって、および最も信頼性の低い構成要素を変えることによって得られる。
好ましくは、置き換えステップで得られた語に最も近い符号語を選択するステップにおいて、最尤推定値のｋ項組は、置き換えステップで得られた語の最も信頼性の高い構成要素のファーム近似を行うことによって、および最も信頼性の低い構成要素を変えることによって得られる。
一実施形態では、受信された語はガウス型白色雑音によって影響を受けている。
また、本発明は伝送チャネルから受信された積符号の語（Ｒ）の反復復号化方法であって、このような方法による、少なくとも１回反復する前記積符号語の行または列のソフト入力ソフト出力式復号化を含む方法も目的とする。
本発明のその他の特徴および利点は、添付の下記図を参照しながら、例として示されている、本発明の実施形態についての以下の説明を読むことによって明らかになるであろう。
−  第１図は、本発明において実施されたソフト入力ソフト出力式復号化方法の第１の実施形態のフローチャートである。
−  第２図は、本発明において実施されたソフト入力ソフト出力式復号化方法の第２の実施形態のフローチャートである。
−  第３図は、本発明において実施されたソフト入力ソフト出力式復号化方法の第３の実施形態のフローチャートである。
−  第４図は、本発明による反復復号化アルゴリズムのフローチャートである。
−  第５図は、４回の反復回数についての本発明の復号器の動作図である。
−  第６図および第７図は、本発明の様々な方法の結果をグラフで表した図である。
ソフト入力ソフト出力式復号化アルゴリズムにおいて、受信されたソフト符号語に一見したところ近い符号語の集合を決定するには、本発明は復号化を使用するのではなく、符号化を使用することを提案する。
第１図は、本発明において実施されたソフト入力ソフト出力式復号化方法の第１の実施形態のフローチャートを示している。つまり、第１図には、受信された積符号語の行または列における受信されたソフト語のソフト出力式復号化に必要なステップを図示した。
以下の説明では、伝送チャネルから受信された積符号のソフト語をＲ＝｛ｒi，j｝と表す。ここに、ｉおよびｊは、１≦ｉ≦ｎ1、１≦ｊ≦ｎ2である。このソフト語は、雑音を有するチャネルの復号器に到達するＣ2．Ｃ1積符号のバイナリまたはファーム語のチャネル上の伝送に対応している。実数の集合内のソフト値の表示を考える。なお、ファーム値は±１に対応している。このような表示では、受信されたソフト値のモジュロは値の信頼性を示しており、その正負符号は受信されたファーム値を与える。
第１図を参照しながら、この符号語の行の復号化について説明する。同方法は、必要な変更を加えた上で、この積符号語の列の復号化にも適用される。したがって、所与の行に対応したソフト語ｓ＝｛ｓi，１≦ｉ≦ｎ1｝を考える。ここに、所与のｊについてｓi＝ｒi，jである。この語は、Ｃ1（ｎ1、ｋ1、ｄ1）符号の語についての誤りを有しているバージョンである。この語は、情報源符号器によって提供されるｋ1個のビットと、Ｃ1符号によって生成されるｎ1−ｋ1個の冗長ビットとを含む。説明をより簡単にするため、入力のｋ1個の構成要素が、出力符号語の中にそのまま再び出現する系統的な形式を考えた。
第１ステップ１において、受信された構成要素セットｓiを、モジュロ｜ｓi｜の小さい順に、すなわち信頼性に従ってソーティングする。対応する置換は、Ｔと表される。
第２ステップ２において、置換におけるｓiの像Ｔ（ｓi）の最後のｋ1個の構成要素が、残りのｎ1−ｋ1個の構成要素の再生を可能にすることを検査する。このことは、置換Ｔを、Ｃ1符号のパリティ行列の列に適用することによって、および置換され得られた行列の最後のｎ1−ｋ1個の列が独立していることを検査することによって行われることができる。もしこれらの最後のｎ1−ｋ1個の列が独立していないならば、置換をパリティ行列の列に適用したときに、独立した最後のｎ1−ｋ1個の列が得られるように、置換Ｔを変更する。このことは、ｊ番目の列（ｊ≦［ｎ1−ｋ1＋１，ｎ1］）を変えることによって、すなわち置換（ｐ，ｎ1−ｋ1＋ｊ）でＴを構成することによって行われることができる。ここに、ｐはｋ1以下の整数である。ステップ８までの以下の方法では、置換された符号語について、この置換空間内で作業する。
第３ステップ３では、受信された語であって、置換された語の対応する最後のｋ1個の構成要素のうちのｍ（ｍ＜ｋ1）個を、たとえば最も信頼性の低いｍ個の構成要素を考える。そして、それらをバイナリ値に割り当て、対応するｍ項組を生成する。この方法で、２m個のバイナリのｍ項組を生成することができるが、これらの２m個のｍ項組のうちのいくつかだけを、たとえば最も小さな距離を有するものだけを生成する方がより有利になりうる。
第４ステップ４では、最後のｋ1個の構成要素のうちの残りのｋ1−ｍ個の構成要素を考える。これらの構成要素の各々について、ファームデシジョンを行う。すなわち、各ソフト構成要素にファーム値またはバイナリ値を割り当てる。たとえば、各構成要素にその正負符号を単に付与することができる。
第５ステップ５において、第３ステップと第４ステップの結果からバイナリの語の集合ｔb＝｛ｔi，１≦ｉ≦ｋ1｝bを再構築する。ここに、ｂ≦２mである。換言するならば、ステップ５で得られた語の各々は、ステップ３で生成されたｍ個の構成要素とステップ４で得られたｋ1−ｍ個の構成要素との集合または連結である。置換された語の空間内においてＣ1符号に対応している符号化をそれらに適用する。
この符号化を行う方法は、Ｃ1符号のパリティ行列Ｈを使用することである。構成要素のソーティングに関連付けられた置換Ｔが、符号のパリティ行列Ｈに適用される。次に、リストＴによって置換された行列Ｈの右端の（ｎ1−ｋ1）列にガウス変換（ｒｅｄｕｃｔｉｏｎ：リダクション）を適用して、この行列を系統的な形式にする。留意すべきことであるが、一般に、置換された行列Ｈの最後の（ｎ1−ｋ1）個の列は独立していない。この場合には、これらの列を独立させるために、またしたがって置換された行列Ｈを系統化できるようにするために、置換Ｔを変更することができる。ステップ２で提案されている検査は、置換された行列の系統化と同時になされることができる。次に、有利には、置換空間内の符号化のために、この系統化されたパリティ行列が使用される。
したがって、対応する符号の置換されたファーム語ｕb＝｛ｕi，１≦ｉ≦ｎ1｝bが直接得られる。これらのファーム語は、伝送チャネル上で送られた語の置換されたバージョンに一見したところ近い。
次に、第６ステップ６において、得られた各符号語ｕbについて、受信されたソフト符号語ｓiまでのユークリッド距離を計算することができる。このステップにおいて、これらの符号語のうちから最も信頼性の高い語だけを保持することができる。なお、信頼性の測定は、計算されたばかりのユークリッド距離を考えることによってのみ行われる。つまり、符号語を保持するのに使用される閾値、あるいは当該符号語の数は、前の諸ステップで生成した符号語の合計数に依存している。換言するならば、より多くの符号語を生成すればするほど、保持できる符号語の数は多くなる。保持される符号語の数は、多くの符号語の生成によってもたらされる複雑性と、生成される符号語の合計数が増えれば非常に信頼性の高い符号語を見つけだす確率が高くなるという利点との妥協の産物である。
ステップ７において、次の方法でソフト復号化を行う。所与のｊ次の受信された所与の構成要素ｓjについて、得られた符号語集合ｕbの中で、ｊ次の構成要素としてビット１を有する最も近い符号語ｕj+と、ｊ次の構成要素ビット−１を有する最も近い符号語ｕj-とを考える。つまり、復号化されるソフト語のｊ番目の構成要素の値を、ｊ番目のポジションにおいてビット−１を有する最も近い符号語ｕj-の距離ｃj-＝｜ｕj-−ｓ｜と、ｊ番目のポジションにおいてビット＋１を有する最も近い符号語ｕj+の距離ｃj+＝｜ｕj+−ｓ｜との正規化係数１／４を乗じた差として計算する。換言するならば、ｊの各値について、復号器によって提供されるソフト符号語｛ｖi，１≦ｉ≦ｎ1｝のｊ次の構成要素ｖjを次式のように計算する。
0004185167.tif 000002
ステップ５において生成され、ステップ６において保持された語の数によっては、ｊ番目のポジションにおいて反対の正負符号のビット値を有する２つの符号語が生成された符号語集合内に見つからない場合がありうる。たとえば、ｊ次の構成要素が高い信頼性を備えて受信されるケースが挙げられる。また、生成された、あるいは保持された符号語数が少なかったケースも挙げちれる。このようなケースでは、最も小さな距離（受信された符号語に最も近いリストの語の距離）と最も大きな距離（受信された符号語から最も遠いリストの語の距離）との差をｊ番目の構成要素のソフト値として取ることができる。この場合には、正確な値が２つの距離のうちの一方に見つかる。つまり、他方の距離は近似されるか、少なくとも、最も遠いリストの符号語の距離を取ることによって、その下限を考える。
同様にこの場合には、受信された語のｊ番目の構成要素と、最も近い符号語のｊ番目の構成要素のファームデシジョンの正負符号を割り当てられた係数ｂとの和を、ｊ番目の構成要素のソフト値として取ることもできる。換言するならば、最も近い符号語のｊ番目の構成要素が、正であるならば、係数ｂを加え、最も近い符号語のｊ番目の構成要素が、負であるならば、−ｂを加える。つまり、この係数の値は反復に応じて変化しうる。
次に、ステップ２の置換の逆の置換を適用することによって、受信された語の空間内に戻ることができる。これによって、受信された語に最も近い符号語と、各シンボルのすべての信頼性の係数とが、すなわち重み付け出力が見つかる。
では、ステップ７の計算について説明する。構成要素ｂjが平均値ゼロ及び同じ分散ｓ2を有するガウス型白色雑音ｂが付加されたケースを考える。この場合、次のように表すことができる。
0004185167.tif 000003
ここに、ｓは先に説明したように受信された語であり、ｅは、ｅi＝±１で送信された符号語であり、ｅ＝（ｅi，１≦ｉ≦ｎ1）である。また、ｂ＝（ｂi，１≦ｉ≦ｎ1）である。この場合、復号化される語の各シンボルｃiに関連付けられた信頼性測定は、次式によって規定される尤度比の対数から決定されることができる。
0004185167.tif 000004
この場合、Ｂａｙｅｓの法則を用いて、および雑音がガウス型白色雑音であることを考慮して、シンボルｃiに関連付けられた尤度比が次式に等しいことを示す。
0004185167.tif 000005
ここに、Ｓ1，jおよびＳ-1，jは、ｊ番目のシンボルがそれぞれ＋１または−１である２つの符号の語の集合である。Ｍ（ｓ，ｕ）は、アルゴリズムによって見つけだされた符号語ｕと受信された語ｓとの距離である。なお、距離は、われわれのケースでは、受信された語ｓと符号語ｕとのユークリッド距離である。ユークリッド距離は、有限の精度によるものであることができる。この距離は、必要ならば、フェージングのあるチャネルのケースに適応されることができる。
符号語の数は一般に多いので、尤度比の計算は比較的複雑である。信号対雑音比が十分に大きいときは、分子と分母に最も大きな項だけを代入することによってこの式を簡略化することができる。したがって、尤度比の対数の式は、次のようになる。
0004185167.tif 000006
尤度比の対数を係数
0004185167.tif 000007
によって正規化することによって、ｊ番目のシンボルｖjの重み付け出力は次のように表される。
0004185167.tif 000008
ここに、Ｓijは、ポジションｊにおけるｉ（ｉ＝±１）に等しいシンボルをもつ符号の語の集合である。ｃj-とｃj+について先の記号表記を踏襲すれば、結局第１図のステップ７の式が得られる。
0004185167.tif 000009
第１図を参照して説明した諸ステップは、伝送チャネル上で受信されたソフト語に近い符号語の生成を可能にする。第１図の方法を用いれば、符号の語のリストを見つけることによって、そこから、受信された符号語の各構成要素のソフト値を導き出すことができる。方法の複雑さは、ステップ４において生成された符号語の数に、つまり生成された近い符号語の数に依存している。この数が多ければ多いほど、方法はより高性能になるが、実施するのがより複雑になる。この数が少なければ、方法は高性能ではあるが、さほど効果的ではなくなる。選択された符号語の数は、方法の性能と複雑性のバランスを決定づけるので、様々な状況に応じて適応される。実際には、満足のいく結果は、拡張されたＢＣＨ（３１、２１）符号については、５０個の生成された語のうちから１９個の最良の符号語を保持することによって得られる。
ステップ２の変形形態として、最も信頼性の低い構成要素を変えるのではなく、組み合わせ上において最も信頼性の低い構成要素を変えることができる。たとえば、対応するモジュロをもつ下記構成要素を考えるならば、
0004185167.tif 000010
たとえば、Ｉ1を変え、次にＩ2を変え、次にＩ3を変え、次にＩ1とＩ2を変え、次にＩ4を変え、次にＩ1とＩ3を変え、次にＩ5を変え、以下同様に変える。こうすることにより、最も信頼性の高い構成要素を保持することになる。
第２図は、本発明で実施されたソフト入力ソフト出力式復号化方法の第２の実施形態のフローチャートを示している。やはり、第２図においても、行の例だけを考えた。やはり、符号の系統的な形式を参照して説明する。所与の行に対応するソフト語｛ｓi，１≦ｉ≦ｎ1｝を考える。ここに、所与のｊについてｓi＝ｒi，jである。この語は、Ｃ1（ｎ1、ｋ1、ｄ1）符号の語の誤りを有しているバージョンである。この語は、情報源符号器によって提供されるｋ1個のビットと、Ｃ1符号によって生成されるｎ1−ｋ1個の冗長ビットとを含む。
第１ステップ１１において、受信された最初のｋ1個の構成要素ｓiを、モジュロ｜ｓi｜の小さい順に、すなわち信頼性に従ってソーティングする。対応する置換をＴと表す。
第２ステップ１２において、Ｃｈａｓｅアルゴリズムの場合のように行い、最も信頼性の低いｍ個（ｍ＜ｋ1）の構成要素についてファームベクトルを生成する。この方法で２m個のｍ項組を生成することができるが、これら２m個のｍ項組のうちのいくつかだけを、たとえば最も小さなユークリッド距離を有するものだけを生成する方がより有利になりうる。ｋ1＝４、ｍ＝２である場合には、生成されるベクトルはたとえば００、１０、０１、１１である。
第３ステップ１３において、残りのｋ1−ｍ個の構成要素を考える。これらの構成要素の各々について、ファームデシジョンを行う。すなわち、各ソフト構成要素にファーム値またはバイナリ値を割り当てる。たとえば、ｉ次の構成要素ｓiに正負符号の値（ｓi）を単に割り当てることができる。
ステップ１４において、ステップ１２とステップ１３の結果から、ステップ１２で得られたｍ個の構成要素と、ステップ１３で得られたｋ1−ｍ個の構成要素との連結によって
バイナリの語の集合ｔb＝｛ｔi，１≦ｉ≦ｋ1｝bを再構築する。ここに、ｂ≦２mである。これらのファーム語に符号化Ｃ1．Ｔ-1を適用する。ここに、Ｔ-1はステップ１の置換Ｔの逆置換である。このようにして、伝送チャネル上に送られた語に一見すると近い、Ｃ1符号のファーム語ｕb＝｛ｕi，１≦ｉ≦ｎ1｝ｂが直接得られる。
次に、ステップ１５において、得られた符号語ｕbの各々について、受信されたソフト符号語ｓiまでのユークリッド距離を、あるいは受信された符号語ｓに対する各符号語ｕbの距離を計算することができる。このステップにおいて、第１図のステップ６を参照して先に説明したように、これらの符号語のうちから最も信頼性の高い語だけを保持することができる。
ステップ１６において、第１図のステップ７と同じ方法でソフト復号化を行う。
第１図の方法と比較して第２図の方法は、パリティ行列の最後の列の独立性を検査するステップを省くことができるが、第１図のこの同じ方法に比べ、符号語の構成要素の全てのうちからではなく、最初のｋ1個の構成要素のうちからしか構成要素を変更しないという欠点を有している。換言するならば、第１図の方法は、送られた情報のうちからだけでなく、冗長値のうちからも選択される低信頼性の構成要素の変更を可能にする。したがって、送られた語の最初のｋ1個の構成要素のうちだけではなく、全体の中における符号語のより信頼性の高いｋ1個の構成要素のうちの最も信頼性の低い構成要素を変更することになる。
第３図は、本発明において実施されたソフト入力ソフト出力式復号化方法の第３の実施形態のフローチャートを示している。この実施形態では、第１図の最初の５つのステップの場合と同様に行って、符号語のリストとそれらの距離を得る。このことは、第３図において、ステップ２０によって記号化されている。ステップ２１において、最も近い符号語ｃ*を、すなわち最も小さな距離を有する符号語を考えるとともに、現在の値ｊを１に初期化する。
ステップ２２において、受信された符号語ｓのｊ番目の構成要素ｓjに、ステップ２１で決定された、非常に大きな信頼性をもつ符号語ｃ*のｊ番目の構成要素の値と反対の値を与えるために、前者の構成要素の値を変える。
ステップ２３において、第１図の最初の５つのステップと同様に、受信された語であって、そのｊ番目の構成要素において変更された語に近い符号語のリストを探索し、それらの距離を計算する。
ステップ２４において、最も小さな距離を有する符号語ｃI*を考える。ｃI*のｊ次の構成要素は、ステップ２１で決定された符号語ｃ*の反対である。次に、出力ソフト語ｖのｊ次の構成要素ｖjを、ステップ２１および２４の語ｃ*とｃI*との距離の正規化係数１／４を乗じた差として計算する。
ステップ２５において、ｊとｎを比較する。もしｊ＝ｎであるならば、復号化を終了する（ステップ２６）。そうでなければ、ステップ２７において、ｊに１を増分し、ステップ２２に戻る。
第１図および第２図の方法に比べ、第３図の方法は、各構成要素ごとに、この構成要素について反対の正負符号のビット値を有する２つの符号語が見つかる限りにおいて、より良い結果を与える。しかしながら、この方法は、近い語のリストを１回だけではなくｎ1＋１回計算しなければならない限りにおいてより複雑である。
第１図から第３図の方法は、したがって、伝送チャネルから受信された積符号語の各行または各列ごとにソフト出力を提供する。本発明の復号化方法は、反復復号化の一実施形態を示している第４図を参照して説明するように、このような反復復号化にこのソフト復号化を使用する。反復においては、現在の行列の行と列それぞれから、次の反復のための行と列をそれぞれ得るために、第１図から第３図のいずれかの図の方法か、これらの方法の組み合わせを使用する。
第１ステップ３０において、現在の行列Ｒiをチャネルから受信された値Ｒに初期化する。符号ｉの値はゼロに初期化される。次に、ステップ３２に移る。
ステップ３２において、ｉの各値について係数ａiを決定する。当該係数は、増加する実数の系列（ａi）を形成する。これらの係数の値は、拡張されたＢＣＨ（３１、２１）積符号について第６図に例として示されている。
次にステップ３４に移る。
第１図から第３図のソフト入力ソフト出力式復号化アルゴリズムのうちのどれか１つを使用して、行列Ｒiの行を復号化する最初のステップによって、各行がＣ1符号の語である新しい行列Ｌｉを決定することができる。次にステップ３６に移る。
ステップ３６において、ｉに１を増分する。行列Ｌi-1から、（Ｌi-1−Ｒi-1）に等しい外因性の情報を抽出し、この情報に係数ａiによって重み付けし、受信された行列Ｒに加える。この新しい行列Ｒi＝Ｒ＋ａi（Ｌi-1−Ｒi-1）を計算して、ステップ３８に移る。
ステップ３８において、引き続き第１図から第３図のソフト入力ソフト出力式復号化アルゴリズムのうちのどれか１つを使用して行列Ｒiの列を復号化する。この復号化によって、各行がＣ2符号の語である行列Ｌiを得ることができる。このステップ３８は、列に関して、ステップ３４に対応している。次にステップ４０に移る。
ステップ４０は、ステップ３６に対応している。つまり、ｉに１を増分し、新しい行列Ｒi＝Ｒ＋ａi（Ｌi-1−Ｒi-1）を形成することからなる。
ステップ４２において、ｉ／２に等しい反復回数を所望の反復回数と比較する。指摘しておくべきことであるが、行の復号化と列の復号化を含む組み合わせを「反復」と呼ぶ。更なる反復を行わなければならないならば、ステップ３４に移る。そうでなければ、ステップ４６に移る。
ステップ４６において、ステップ３８で列の復号化によって得られた行列Ｌi-1について、バイナリデジションを行う。このようにして得られた行列は、送信された符号語に対応していると仮定されるので、情報ビットを見つけだすには情報のサブマトリクスを抽出すればよい。
第５図は、４に等しい反復回数について復号器の動作を示している。
本発明の方法は、代数復号器やＧａｌｌｏｉｓ有限体の複雑な計算を使用することなく、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ、Ｒｅｅｄ−Ｍｕｌｌｅｒ、ＱＲ、サイクリック符号等の符号を含むＢＣＨ符号のような線形ブロック符号からなるあらゆるタイプの符号に適用される。
第６図および第７図は、本発明による復号化結果を示している。第６図は、第４図および第１図を参照して説明した方法による拡張ＢＣＨ（３１、２１）積符号の復号化結果を示している。図の縦座標にビット誤り率を、横座標に信号対雑音比Ｅｂ／Ｎ０（単位：ｄＢ）を示した。図には、制約長７の１／２合成符号について得られた結果と、本発明による復号化の１回、２回、３回または４回の反復後に得られた結果を示した。
第６図のシミュレーションについては、Ｊ＝５０個の符号語を計算し（第１図のステップ５）、そのうちからＱ＝１９個の最良の符号語を各回に採用した。行および列に使用した係数（ａiは次表に示されている。
0004185167.tif 000011
同時に発生する符号語が見つからなかった場合には、下記係数（ｂi）が使用される。
0004185167.tif 000012
図は、１０-6のビット誤り率（ＢＥＲ）について、１／２符号に比べて約２ｄＢの符号化利得を示している。
第７図は、ＢＣＨ（３０，１９）ｘＢＣＨ（３０，２４）積符号について、対応する結果を示している。ＢＣＨ（３０，１９）符号は、拡張ＢＣＨ（３１，２１）符号から得られた、２つ短縮された符号である。ＢＣＨ（３０，２４）符号は、拡張ＢＣＨ（３１，２６）符号から得られた、２つ短縮された符号である。同じ参照符号に比べ、２ｄＢを超える符号化利得が認められる。
本発明による積符号の反復復号化は、そのすべての実施形態において、ＦＲ−Ａ−２７１２７６０で提案されたアルゴリズムと同じ反復回数のもとで、より良い性能を提供している。
もちろん、本発明は、説明、図示した例および実施形態に限定されず、専門家であれば分かる多数の変形形態の対象となりうる。したがって、本発明は、Ｃ1．Ｃ2積符号を参照して説明したが、たとえばブロックからなる３つの符号あるいはそれ以上の符号の積符号のような、異なる形の符号にも適用される。また、本発明は本出願人の上記特許出願Ｎｏ．９７１２５９４で説明した積符号タイプの積符号にも適応される。これらの積符号は、非同期転送モード（ＡＴＭ）による伝送パケットの符号化に特に応用される。つまり、パケットのボディに使用されるＣ2符号と異なるＣ1符号をヘッダの符号化に使用する。次に、行がＣ1とＣ2符号の語で形成される行列の列にＣ3符号を適用する。
同様に、第４図のアルゴリズム以外の反復復号化アルゴリズムに第１図から第３図の方法を使用することができる。
また明白なことであるが、受信された積符号語の「行」および「列」という用語は、表現上の便利性のためにだけ用いられており、チャネル上で受信された値は行列の形をしていない。「行」から復号化を始めても、「列」から復号化を始めてもどちらでもよい。したがって、「伝送チャネルの出力部で受信された積符号語」という表現は、伝送チャネルの出力部で受信される、連続した値であると、あるいは雑音を有する一連のバイナリ値であると解釈されなければならない。
さらに、本発明は、系統的なブロック符号を参照して説明された。本発明は、第１および第３の実施形態の方法に関しては、系統的な形にないＣ（ｎ、ｋ、ｄ）符号に適用される。ただし、Ｃ（ｎ、ｋ、ｄ）符号が、階数ｋの行列による積によって系統的な形の符号に容易に変換されることができる限りにおいてである。本発明は、バイナリ符号の例を参照して説明されたが、本発明は、ｑエリア符号（ｑ≠２）にも適用される。
【図１】
0004185167.tif 000013
【図２】
0004185167.tif 000014
【図３】
0004185167.tif 000015
【図４】
0004185167.tif 000016
【図５】
0004185167.tif 000017
【図６】
0004185167.tif 000018
【図７】
0004185167.tif 000019