(57)【要約】【課題】  オーダの小さいサイズのブロックの誤り訂正を効果的に行う。【解決手段】  所定の要素符号の少なくとも２つの異なるセクションを使用し、符号語を定義するブランチ・ラベルのベクトル（ｂ0，ｂ1，ｂ2，ｂ3）に従って到達ベクトル（ｓ2，ｓ3）を開始状態ベクトル（ｓ0，ｓ1）に関連付け、該ブランチ・ラベルのベクトルの要素の順序および／または機能が変化すると前記要素符号の２つのセクションが異なることを特徴とする誤り訂正符号化方法を提供する。【選択図】        図２
2004304807.tif 000002
【特許請求の範囲】
【請求項１】
所定の要素符号の少なくとも２つの異なるセクションを使用し、符号語を定義するブランチ・ラベルのベクトル（ｂ0，ｂ1，ｂ2，ｂ3）に従って到達ベクトル（ｓ2，ｓ3）を開始状態ベクトル（ｓ0，ｓ1）に関連付け、該ブランチ・ラベルのベクトルの要素の順序および／または機能が変化するときには前記要素符号の２つのセクションが異なることを特徴とする誤り訂正符号化方法。
【請求項２】
（ｓ0，ｓ1）と（ｓ2，ｓ3）と（ｂ0，ｂ1）と（ｂ2，ｂ3）の４つのパケットへと前記要素符号の符号語を分割しておくことにより、ゼロ符号語以外の各符号語は４つのうち少なくとも３つの軽量化パケットを含むようにし、パケットが値１のビットを少なくとも含む場合には、該パケットは軽量化されているといわれるものであることを特徴とする請求項１に記載の符号化方法。
【請求項３】
少なくとも１つの符号化トレリスを形成するように、前記要素符号セクションを順次結合することを特徴とする請求項１または２に記載の符号化方法。
【請求項４】
前記トレリスが巡回性のものであることを特徴とする請求項３に記載の符号化方法。
【請求項５】
２つのトレリスを含み、符号化されるソース・データが異なる順序で入力されることを特徴とする請求項３または４に記載の符号化方法。
【請求項６】
保持される符号化結果が、開始セクションとして選択され、前記要素符号セクションの１つに対するすべての可能な開始状態にある、開始状態に等しい到達状態を有する符号化結果であることを特徴とする請求項４または５に記載の符号化方法。
【請求項７】
前記符号化結果が、前記トレリスにより与えられる情報と冗長要素との集合であることを特徴とする請求項６に記載の符号化方法。
【請求項８】
前記要素を分解して符号化結果を形成することを特徴とする請求項７に記載の符号化方法。
【請求項９】
前記セクションの少なくとも１つが分解されることを特徴とする請求項１または８に記載の符号化方法。
【請求項１０】
少なくとも１つの左に分解されたセクションと少なくとも１つの右に分解されたセクションとが使用されることを特徴とする請求項９に記載の符号化方法。
【請求項１１】
前記トレリスを少なくとも１回複写することによって、置換手段によって連接される少なくとも２つの符号化集合を有することを特徴とする請求項３から１０のいずれかに記載の符号化方法。
【請求項１２】
符号化されるデータが、前記符号化集合のそれぞれにシフトにより伝送されることを特徴とする請求項１１に記載の符号化方法。
【請求項１３】
前記ベクトルが２進要素から成ることを特徴とする請求項１または１２に記載の符号化方法。
【請求項１４】
前記要素符号は、ハミング［８，４，４］符号であることを特徴とする請求項１３に記載の符号化方法。
【請求項１５】
Ｈ；（ｙ0，ｙ1，ｘ0，ｘ1）（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈ；（ｘ0，ｘ1，ｙ0，ｙ1）（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈ；（ｘ0，ｙ0，ｙ1，ｘ1）（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈ；（ｙ0，ｘ0，ｘ1，ｙ1）（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈ；（ｙ0，ｘ0，ｙ1，ｘ1）（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈ；（ｘ0，ｙ0，ｘ1，ｙ1）（ｂ0，ｂ1，ｂ2，ｂ3）
のセクションを適用することを特徴とする請求項１４に記載の符号化方法。
【請求項１６】
Ｈg；（*，*，ｘ0，ｘ1）（*、*、ｂ2、ｂ3）
Ｈd；（ｘ0，ｘ1，*，*）（ｂ0、ｂ1、*、*）
の分解セクションを適用することを特徴とする請求項１４と請求項１５と請求項１０とのいずれかに記載の符号化方法。
【請求項１７】
識別順列と４ビット巡回シフト順列と８ビット巡回シフト順列とによって、１２符号化ビットを受け取る３つの符号化集合をそれぞれ含むことを特徴とする請求項１４と請求項１６と請求項１１とのいずれかに記載の符号化方法。
【請求項１８】
前記符号化セットが、Ｇｏｌａｙ［２４，１２，８］符号を生成するように構成されることを特徴とする請求項１７に記載の符号化方法。
【請求項１９】
前記ベクトルが４つの値を仮定できる基本語から成ることを特徴とする請求項１および１２のいずれかに記載の符号化方法。
【請求項２０】
前記要素符号が、パラメータ［８，４，６］を有するＮｏｒｄｓｔｒｏｍ  Ｒｏｂｉｎｓｏｎ符号であることを特徴とする請求項１９に記載の符号化方法。
【請求項２１】
前記ベクトルが８つの値を仮定できる基本語から成ることを特徴とする請求項１または１２に記載の符号化方法。
【請求項２２】
前記要素符号がＭ［８，４］符号であることを特徴とする請求項２１に記載の符号化方法。
【請求項２３】
符号化が「ターボコード」タイプであることを特徴とする請求項１または２２に記載の符号化方法。
【請求項２４】
所定の要素符号の少なくとも２つの異なるセクションに対応する少なくとも２つの符号化モジュールを含み、ブランチ・ラベルのベクトル（ｂ0，ｂ1，ｂ2，ｂ3）に従って到達ベクトル（ｓ2，ｓ3）を開始状態ベクトル（ｓ0，ｓ1）に関連付けし、
該ブランチ・ラベルのベクトルの要素の順序および／または機能が変化すると前記要素符号の２つのセクションが異なることを特徴とする誤り訂正符号化装置。
【請求項２５】
所定の要素符号の少なくとも２つの異なるセクションを使用して、ブランチ・ラベルのベクトル（ｂ0，ｂ1，ｂ2，ｂ3）に従って到達ベクトル（ｓ2，ｓ3）を開始状態ベクトル（ｓ0，ｓ1）に関連付けし、
該ブランチ・ラベルのベクトルの要素の順序および／または機能が変化するときには前記要素符号の２つのセクションが異なることを特徴とする、請求項１から２３のいずれかに記載の符号化方法により符号化データを復号する方法。
【請求項２６】
繰返し的であることを特徴とする請求項２５に記載の復号化方法。
【請求項２７】
各繰返しにおいて、前記要素符号セクションにより定義される少なくとも１つのトレリスに関連する基準について事後確率を計算し、
前記繰返しは、安定結果が得られたときに、および／または、所定の繰返し回数の後に中止されることを特徴とする請求項２６に記載の復号化方法。
【請求項２８】
所定の要素符号の少なくとも２つの異なるセクションに対応する少なくとも２つの復号化モジュールを含み、ブランチ・ラベルのベクトル（ｂ0，ｂ1，ｂ2，ｂ3）に従って到達ベクトル（ｓ2，ｓ3）を開始状態ベクトル（ｓ0，ｓ1）に関連付けし、
該ブランチ・ラベルのベクトルの要素の順序および／または機能が変化するときには、前記要素符号の２つのセクションが異なることを特徴とする、請求項１から２３のいずれかに記載の符号化方法により符号化されたデータを復号する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は、デジタル通信分野である。より詳細には、本発明は誤り訂正符号に関する。特に、本発明は、これに限定されないが、「ターボコード（turbo-codes）」としてよく知られた符号に関する。
【０００２】
本発明は、誤り訂正符号の利用を必要とするかまたは少なくとも望ましい場合の、あらゆる分野への応用を見出すことができる。したがって、本発明は、例えば、以下の場合である、
物理的伝送通信路に固有の雑音および干渉に起因する誤りに対する保護（多重アンテナ・システムに対する従来の誤り訂正符号化および時空符号）と、
情報源（イメージ、サウンド、信号、およびデータ）からの信号の圧縮と、
コンピュータ・ディスクまたはマイクロプロセッサなどのデータ・マス・メモリの格納に対する保護と
に適用できる。
【背景技術】
【０００３】
誤り訂正のための多くの符号化手法がよく知られている。この問題に関する最初の研究は１９４０年代に遡る。それは、Shannonが現在においても用いられている情報理論を発表した時である。その後、多くの符号化手法が提案されている。
【０００４】
このように、（特に、ビタビ（Viterbi）アルゴリズムに従って、トレリス符号化（trellis coding）に適用できる）畳み込み符号はよく知られており、または、現在でも「ターボコード」と呼ばれる符号化方法としてよく知られており、この「ターボコード」は、c.BerrouおよびA.Glavieuxにより、例えば、論文「Near Shannon Limit Error Correting Coding and  Decoding:Turbo-Codes」（proofreading of ICC’９３、１９９３年５月、１０６４〜１０７０）において１９９３年に提案されたものである。
【０００５】
この手法は、多くの研究および改良の主題である。
【０００６】
ＬＤＰＣ符号と呼ばれる符号系もよく知られている。
【０００７】
ターボコードとＬＤＰＣ符号とさらに一般的なすべての連接符号とは、大きいブロック・サイズに対して、特に、少なくとも数千または数万の情報ビットのブロックに対しては優れた訂正性能を提供する。
【０００８】
不利な点は、このような情報ビットのブロックの処理が復号化の際に計算の複雑性を大きくすることであり、実際、高性能計算能力のマイクロプレセッサによってのみ可能であることが立証されているため、相対的に高いコストになることが証明されている。
【０００９】
さらに、一方では、これらの構造は、例えば、百ビットまたは千ビットのオーダの小さいサイズのブロックの誤り訂正にはあまり効果的ではない。
【００１０】
しかし、短い符号の利用を想定する、デジタル通信分野における小さいパケットによる通信に対する極めて強い要求が現在も存在する。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、特に、前記の要求に対する解決策を提供し、従来の手法の欠点を克服することである。
【００１２】
さらに詳細には、本発明の目的は、復号化の複雑性を低減するために、特に「ターボコード」タイプの誤り訂正符号化手法を提供することである。
【００１３】
言い換えると、本発明の目的は、単純な復号器を低コストで製作し、誤り訂正品質の劣化のない符号化手法を提供することである。
【００１４】
本発明の別の目的は、小さいサイズのブロックに対する誤り訂正に適する符号化手法を提供することである。
【００１５】
言い換えると、本発明の別の目的は、小さいブロック・サイズであっても適正な最少距離を備える符号化手法を提供することである。
【００１６】
本発明のさらに別の目的は、簡単な方法により符号化および復号化を実現することにより、容易に適用できる符号化手法を提供することである。
【課題を解決するための手段】
【００１７】
後に詳細に示すように、これらの目的および他の目的は、誤り訂正符号化方法により達成される。この方法は、所定の要素符号の少なくとも２つの異なるセクションを使用することによって、符号語を定義するブランチ・ラベルのベクトル（ｂ0，ｂ1，ｂ2，ｂ3）に従って到達ベクトル（ｓ2，ｓ3）を開始状態ベクトル（ｓ0，ｓ1）に関連付けるものであり、前記ブランチ・ラベルのベクトルの要素の順序および／または機能が変化するときには前記要素符号の２つのセクションが異なるものである。
【００１８】
したがって、形成される符号は、複雑性の極めて小さいものであり、（任意選択的には、配線式アナログ回路で生成できる）小サイズであり、さらに効率的な基本ブリックから形成されるため、極めて簡単になる。後に説明するように、それ自体が知られている符号は、極めて簡単な形により特に再生できる。
【００１９】
さらに詳細には、本発明によれば、関連する既存の技術分野に対して、少なくとも２の比率まで（特に少数の状態である場合は、後に説明する２進符号に対して最低４つの状態を有するトレリスを使用することにより）、同一訂正能力に対して複雑性の低減が得られる。
【００２０】
さらに、これらのトレリスを用いて生成される長さの短いこれらの２進符号は、極めて小さい距離を有するので、小さいブロック・サイズと２進の場合のわずか４つの状態を持つトレリスとであっても、現在の「ターボコード」に比べて優れた誤り訂正能力を有することができる。
【００２１】
好ましくは、４つのパケット（ｓ0，ｓ1）と（ｓ2，ｓ3）と（ｂ0，ｂ1）と（ｂ2，ｂ3）とに前記要素符号の符号語を分割することにより、ゼロ符号語を除く各符号語が４つのうちの少なくとも３つの軽量化パケットを含むようにし、パケットは、少なくとも値１のビットを含むときに軽量化されたといわれる。
【００２２】
これにより、「１」を伝送できるので、符号距離（code distance）を増加できる。
【００２３】
有利には、前記要素符号セクションをシーケンスに結合して、少なくとも１つの符号化トレリスを形成する。誤り訂正能力は、このトレリスを形成するステージ・シーケンス（またはセクション）の適正な選択により最適化できる。
【００２４】
有利な実施形態によれば、前記トレリスまたは複数のトレリスは、巡回性（cyclic）のものである。
【００２５】
このことは、訂正能力の最適化と情報ビット間の保護レベルの均一化とを可能にする。
【００２６】
この場合、有利に保持される符号化結果は、開始セクションとして選択され、前記要素符号セクションの１つに対する可能なすべての開始状態にある、そのセクションの開始状態に一致する到達状態を有する符号化結果である。
【００２７】
有利には、本発明の符号化方法は２つのトレリスを含み、符号化されるソース・データは異なる順で入力される。
【００２８】
好ましい実施形態によれば、前記符号化結果は、前記トレリスまたは複数トレリスにより提供された情報および冗長要素の全体である。
【００２９】
有利には、分解は符号化結果を形成する前記要素に対して適用できる。
【００３０】
また、少なくとも前記セクションの分解は、本発明の特定の態様に従って実現できる。好ましくは、少なくとも１つの左に分解されたセクションと、少なくとも１つの右に分解されたセクションとが用いられる。
【００３１】
本発明の好ましい実施形態によれば、前記トレリスまたは複数トレリスを少なくとも１回複写して、置換方法により相互に関連する少なくとも２つの符号化集合を得るようにする。
【００３２】
この場合、有利には、符号化されるデータは、好ましくはシフトすることによって前記符号化集合のそれぞれに伝送できる。
【００３３】
本発明の第１方法によれば、前記ベクトルは２進要素から成る。この場合、前記要素符号は、有利には、［８，４，４］ハミング符号（Hamming code）である。
【００３４】
この場合、符号化方法は、以下のセクションを適用できる。
Ｈα；（ｙ0，ｙ1，ｘ0，ｘ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈβ；（ｘ0，ｘ1，ｙ0，ｙ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈγ；（ｘ0，ｙ0，ｙ1，ｘ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈδ；（ｙ0，ｘ0，ｘ1，ｙ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈδ；（ｙ0，ｘ0，ｙ1，ｘ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈφ；（ｘ0，ｙ0，ｘ1，ｙ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
有利には、以下の分解セクションを追加して使用できる。
Ｈg；（*，*，ｘ0，ｘ1）→（*、*、ｂ2、ｂ3）
Ｈd；（ｘ0，ｘ1，*，*）→（ｂ0、ｂ1、*、*）
【００３５】
特定の実施形態によれば、符号化は３つの符号化集合を含み、その各々は、識別順列（identity permutation）と４ビットの巡回シフト順列(cyclic shift permutation)と８ビットの巡回シフト順列とを介して、１２の符号化ビットをそれぞれ受け取る。
【００３６】
この場合、前記符号化テストは、有利には、［２４，１２，８］Ｇｏｌａｙ符号を生成するように構成される。
【００３７】
別の有利な方法によれば、前記ベクトルは、４つの値および予測できる基本ワードから成る。この場合、前記要素符号は、有利には、パラメータ［８，４，６］を有するＮｏｒｄｓｒｏｍ  Ｒｏｂｉｎｓｏｎ符号である。
【００３８】
本発明のさらに別の有利な方法によれば、前記ベクトルは、８つの値を仮定できる基本ワードから成る。このとき、前記要素符号は、特に、Ｍ［８，４］符号にできる。
【００３９】
本発明の好ましい態様によれば、得られる符号は「ターボコード」タイプである。
【００４０】
また、本発明は、このような符号化方法に適合する誤り訂正符号化装置に関する。
【００４１】
さらに、本発明は、対応する復号化装置および復号化方法に関する。
【００４２】
このような方法は、符号化に適用される方法に対称的なステップを適用する。このように、所定の要素符号の少なくとも２つの異なるセクションを使用して、ブランチ・ラベル・ベクトル（ｂ0、ｂ1、ｂ2、ｂ3）に従って到達ベクトル（ｓ2，ｓ3）を開始状態ベクトル（ｓ0，ｓ1）に関連付けるものであり、前記ブランチ・ラベルのベクトルの要素の順序および／または機能が変化すると前記要素符号の２つのセクションが異なる。
【００４３】
好ましくは、前記符号化方法は、繰返し的（iterative）である。
【００４４】
有利には、各繰返しにおいて、事後確率が前記要素符号セクションにより定義される少なくとも１つのトレリスに関連する基準について計算され、前記繰返しは安定結果が得られるときに、および／または、所定数の繰返し後に停止される。
【００４５】
本発明の他の特徴および利点は、平易な説明と非限定的な例および添付の図面とにより与えられる、本発明の実施形態の以下の説明を理解することにより明らかになるであろう。
【発明を実施するための最良の形態】
【００４６】
[本発明の一般原理]
前述のように、本発明の目的は、よく知られた手法に比較して復号化の複雑性の少ない符号、特に「ターボコード」を提供し、小さいブロック・サイズに対しても優れた誤り訂正能力を保証することである。
【００４７】
後に説明するように、少なくとも２の比率までの複雑性の低減は、同一訂正能力に対して、よく知られた手法に比較して、特に、小さい数の状態（この場合、２進符号に対して最少４の状態）を有するトレリスを使用することにより、本発明により達成できる。
【００４８】
さらに、これらトレリスを用いて生成される短い長さの符号は、極めて短い距離を有するので、小さいサイズのブロックおよびトレリスであっても、現在の「ターボコード」に比べて優れた誤り訂正能力を有する。
【００４９】
２進符号の場合には、本発明の重要な技術要素は、基本セクションから得られる４状態のトレリス・ステージを使用することである。後の（パラグラフ２）に説明する実施形態では、このセクションは「Ｈ」と呼ばれ、パラメータ［８，４，４］を有する拡張ハミング符号を表わす。
【００５０】
本発明により得られるターボコードの平易さおよび性能は、この小さい符号が固有であり、４ビットの有効な情報に対して８ビットの長さを有し、符号語間の最少距離が４に等しいという事実から得られる。
【００５１】
トレリス・セクションまたはステージは、ブランチ・ラベル・ビットの順序および機能（入力または出力）を変更することにより、基本セクションから得られる。
【００５２】
別の重要な態様は、基本ステージを生成するのに用いられる小さい基本符号が、特殊な方法に従ってビットの４パケットへと分割されることであり、この分割は、すべての非ゼロ・符号語が４つのうち少なくとも３つの非ゼロ・パケットを常に有する、すなわち、それらがパケット当たり少なくとも１つの非ゼロ・ビットを有するようになされることである。後に述べるが、４つのうち少なくとも３つの「軽量化」パケットが常に存在し、パケットは少なくとも１ビットが非ゼロであるときに軽量化される。
【００５３】
｛８，４，４｝ハミング符号の前述の場合には、４つのパケットは２ビットから成る。
【００５４】
したがって、本発明によれば、各トレリスは、基本セクションから得られる、異なる（または同一の）ステージのシーケンスと見なされる。これらシーケンスの望ましい選択は、誤り訂正能力の最適化を実現する。
【００５５】
好ましくは、この結果として得られたトレリスは、巡回的（または「ｔａｉｌ  ｂｉｔｉｎｇ」）であり、誤り訂正能力の最適化と情報ビット間の保護レベルの均一性とを実現する。
【００５６】
（モジュロ４の加算および乗算により提供される集合｛０，１，２，３｝である）リングＺ４上の符号については、等価符号またはパラメータ｛８，４，６｝を有するＮｏｒｄｓｔｒｏｍ  Ｒｏｂｉｎｓｏｎ符号がＬｅｅ距離と共に使用できる（パラグラフ３を参照）。
【００５７】
次に、１６の状態トレリスが得られる。
【００５８】
また、符号は、２つの別の小さい実行符号を使用して６４および２５６状態をそれぞれ有するステージを得る（パラグラフ４参照）ことにより、Ｚ８およびＺ１６上で生成できる。
【００５９】
このＺ４（およびＺ８のそれぞれに）上の符号を用いて、（ＭＤＰ８、ＭＤＰ１６、またはＭＡＱ１６（１６ポイント直交振幅変調）のそれぞれに））極めて高機能のＭＤＰ４（４ポイント位相変調）符号化変調を特に実現できる。
【００６０】
Ｚ４に関しては、これにより、符号は、複雑性が減少し、ＭＤＰ１６またはＭＡＱ１６符号化変調に展開される。同様に、Ｚ８の集合では、符号はＭＡＱ６４変調に展開できる。
【００６１】
実際、ＭＤＰ４変調は、２つのＭＤＰ２変調へと分解でき、ＭＡＱ１６変調は２つのＭＤＰ４変調へと分解でき、ＭＡＱ３２変調はＭＡＱ８変調とＭＤＰ４変調の積へと分解でき、ＭＡＱ６４変調は２つのＭＤＰ８変調へと分解でき、さらにＭＡＱ２５６変調は２つのＭＤＰ１６変調へと、というふうに分解できる。
【００６２】
したがって、Ｚ４またはＺ８上で生成されるトレリスは、複雑性の少ない適正な基本ブリック（basic brick）であり、高性能な低コストの符号化器／変調器を構成し、容易に復号化される。
【００６３】
２）２進「ターボコード」に対する状態基本セクション
ａ）２進「ターボコード」に対する状態非分解基本トレリス・セクション
基本トレリス「Ｈ」セクションは、以下の式の生成行列を有する［８，４，４］ハミング符号語を表わす。
【数１】
2004304807.tif 000003
【００６４】
セクションＨは、図１に示すように、ラベル・ブランチ（ｂ0，ｂ1，ｂ2，ｂ3）を経由する開始状態（ｓ0，ｓ1）から到達状態（ｓ2，ｓ3）へのパスの集合として、［８，４，４］ハミング符号の符号語の集合を表わす。
【００６５】
状態およびラベル・ベクトルは、行列式により関連付けされる。
（ｓ0，ｓ1，ｓ2，ｓ3）＝（ｂ0，ｂ1，ｂ2，ｂ3）Ｐ
【００６６】
ラベルは、標準的方法すなわち各開始状態と反対方向に、関連する到達状態の００，０１，１０，１１の順に記載される。このセクションのＴａｎｎｅｒグラフがセクションの右に示される。
【００６７】
［８，４，４］ハミング符号は、以下の分散により、２ビット「軽量化」パケットを有する４つのパケット（ｓ0，ｓ1）と（ｓ2，ｓ3）と（ｂ0，ｂ1）と（ｂ2，ｂ3）とに分割される。
４つのうち、０の軽量化パケットを有する１語（ゼロ語）、
４つのうち、３つの軽量化パケットを有する１２語（すなわち、符号語７５％）、
４つのうち、４つの軽量化パケットを有する３語（すなわち、符号語の１８．７５％）。
【００６８】
「４つのうち、（少なくとも）３つの軽量化パケット」のこの部分的特性を用いて、一般に、連接符号のTannerグラフが過小サイズの非ゼロ状態のサブ・グラフを含まないようにすることができるので、適正な最少距離を得ることができる。
【００６９】
セクションＨから得られる６つの非分解セクションは、Ｈα、Ｈβ、Ｈγ、Ｈδ、Ｈε、Ｈφであり、これらの情報ビット（ｘ0，ｘ1）と冗長ビット（ｙ0，ｙ1）とは、以下のようにビット（ｂ0，ｂ1，ｂ2，ｂ3）にそれぞれ対応する。
Ｈα；（ｙ0，ｙ1，ｘ0，ｘ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈβ；（ｘ0，ｘ1，ｙ0，ｙ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈγ；（ｘ0，ｙ0，ｙ1，ｘ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈδ；（ｙ0，ｘ0，ｘ1，ｙ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈε；（ｙ0，ｘ0，ｙ1，ｘ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
Ｈφ；（ｘ0，ｙ0，ｘ1，ｙ1）→（ｂ0，ｂ1，ｂ2，ｂ3）
【００７０】
セクションＨの入力（情報ビット）または出力（冗長ビット）のどちらかとしてラベル・ビットを用いることにより、ブール関数が完全に変更される。これにより、トレリス選択（つまり、符号）の多様性が得られ、トレリスは、図２に示すようなセクションのシーケンスに一致する。
【００７１】
図２は、前に記載したセクションを用いて構成された２つの「ｔｒａｉｌ  ｂｉｔｉｎｇ」巡回トレリスを含む１つの順列を備えた代表的な並列「ターボコード」を示す。
【００７２】
２進「ターボコード」の対する４つの状態分解基本トレリス・セクション
分解基本セクション（Punctured basic section）を使用できる。
【００７３】
分解基本セクションはまた、前の非分解セクションのすべてに関し、例えば、左または右の２ビットを分解して、基本セクションＨを有する開始状態によって構成されるものであり、それらは基本セクションに対して、ＨgおよびＨdで表わされる。
Ｈg；（*，*，ｘ0，ｘ1）→（*、*、ｂ2、ｂ3）
Ｈd；（ｘ0，ｘ1，*，*）→（ｂ0、ｂ1、*、*）
【００７４】
分解された（除去された）ビットは、スター*で表わされる。前述のその他の取り出されて分解されたセクションは、ａ∈｛α，β，γ，δ，ε，φ｝を備えたＨgaおよびＨdaとして表わされる。
【００７５】
図３は、このようなセクションを使用して、パラメータＣ［１６，１２，２］を有する符号に対応する代表的な巡回トレリスを示す。この巡回トレリスは、シーケンス（Ｈg，Ｈ，Ｈg，Ｈd，Ｈ，Ｈd）から成り、このシーケンスでは、１２の情報ビットＸi（ｉ＝０，１，．．．１１）が、パラメータＣ［１６，１２，２］を有する符号の４つの冗長ビットＲj（ｊ＝０，１，．．．，３）に適合する。
【００７６】
図４は、図３のトレリスを使用する（３つの）例、つまり、図３の前の符号Ｃ［１６，１２，２］の３つのトレリスを並列に用いる例を示しており、それぞれは、スターの中心に置かれた１２情報ビットを受け取る。
【００７７】
ブロックＲは、１２ビット情報ベクトルの３重に繰り返される符合を表わす。
【００７８】
この特定の場合の順列は極めて簡単である。これは、シーケンス（Ｘ５，Ｘ９，Ｘ４，Ｘ１１，Ｘ６，Ｘ８，Ｘ１０，Ｘ０，Ｘ１，Ｘ２，Ｘ３，Ｘ７）に相当するＩｄとして示される識別順列と、Ｄ4およびＤ8として示され、識別順列に対して４位置および８位置まで巡回的にシフトされたシーケンスを提供する、それぞれ４ビットおよび８ビットの巡回シフト順列とである。
【００７９】
このようなシーケンスおよび構成要素トレリスから構成できる「ターボコード」は、多様であり、直列「ターボコード」や、並列「ターボコード」や、複合直並列「ターボコード」や、「繰返し−積算」符号となる。
【００８０】
ｃ）これらの「ターボコード」の符号化の説明
図２の例についての符号化を実行するためのデータ入力は、情報ビット（ｘ0，ｘ1，．．．ｘ15）であり、この情報ビットから冗長ビット（ｙ0，ｙ1，．．．ｙ15）および（ｚ0，ｚ1，．．．ｚ15）が計算される。この場合、構造の中心に配置された情報ビットは、トレリスの１つの上に自然順に入力され、別の１つ内に入れ替えて置かれる。
【００８１】
各巡回トレリスに対して少数の開始状態（４、８、または１６）しか存在しないため、単純符号化方法は、開始セクションとして１つのセクションを任意に選択し、ラベル・ビットｘおよび各可能な開始状態（ｓ０，ｓ１）に対して、冗長ビットｙおよび到達状態（ｓ２，ｓ３）を計算して格納する。
【００８２】
例として、４つの開始状態｛００，０１，１０，１１｝の各々および開始セクションの２つの情報ビット（ｘ0，ｘ1）に対して、論理表としてトレリス・セクションを用いて次の状態が計算（読取り）される。
【００８３】
トレリスが巡回（「ｔａｉｌ  ｂｉｔｉｎｇ」）するとき、開始セクションの入力に戻るまで、再度次のセクションを用いてトレリスが開始される。すなわち、符号語は、トレリスの各セクションのブランチから成る単純な回路であるため、同一の開始状態および到達状態を有する。
【００８４】
これにより、保有される１つだけの符号化結果は、それの開始状態に等しい到達状態を有する符号化結果である。符号化の結果は、情報および冗長ビットの集合であり、１つは伝送のために選択でき、伝送前に分解できない。
【００８５】
したがって、前述のアルゴリズムを用いて、符号生成行列を１度にすべてに対して計算でき、ベクトル行列乗算により符合を生成できるが、これは、計算量の点でコストが高くなる。
【００８６】
ｄ）これらの「ターボコード」の繰返し復号の説明
繰返し「ソフト（soft）」復号は、復調器の出力における受信時の情報および冗長ビットの優先利用可能な情報から、「ターボコード」の現在の標準符号化により実現できる。
【００８７】
これらのビットは、図２の１つとしてTannerグラフの黒点で示される。各トレリスについて、基準（ＳＩＳＯ、ＳＯＶＡ、ＳＵＢＭＡＰなど）を用いて、ＢＣＪＲアルゴリズムに従って利用可能な優先確率またはその変形形態の１つから事後確率を計算し、トレリスまたは他のトレリス中へと挿入する情報のいわゆる「付帯的な（extrinsic）」部分を抽出する。このプロセスは、安定するまで、または一定の繰返し回数後まで繰り返される。
【００８８】
図５ａ〜図７は、ガウス通信路において１／２および１／３にシミュレートされた長さおよび量と、２状態位相変調である「ＭＤＰ２」とを備えたいくつかの符号に対して、このアルゴリズムから得られるいくつかの２進誤り率曲線（ＴＥＢに対する有効な信号／雑音比Ｅｂ／Ｎ０）を示す。
【００８９】
図８は、従来技術による、１６の状態トレリス（または、等価な複雑性）を用いる有効情報の２００ビットを符号化する長さ４００の符号のＴＥＢと、これらの長さに対する本発明による（まだ最適化されていない）第１の結果のＴＥＢとに関する比較曲線である。
【００９０】
約２倍以下の複雑性であるにもかかわらず、順列および構造を最適化することなく、同等性能が得られている。
【００９１】
ＣＴ（３，１）およびＴＣ（２１，３７）によりそれぞれ示される曲線は、３つのツリー符号（tree code）により構成される従来のＬｉ−Ｐｉｎｇの「ターボコード」と１６の状態２進トレリスを用いるＢｅｒｒｏｕの「ターボコード」とにそれぞれ対応する。
【００９２】
本発明による４状態の「ターボコード」は、信号対雑音比Ｅｂ／Ｎ０を３．５ｄＢ以上（曲線の外側方向に）大幅に改善する。
【００９３】
しかし、これらの新規の「ターボコード」は、それらの順列および構造に応じてまだ最適化されていないのに対し、従来技術の「ターボコード」は大きな長さ(great length)において最適化されている。
【００９４】
図の例においては、使用された新しいトレリスの構造は、実際に最適化されておらず、セクションＨだけから成るため、不変である。各トレリスのさまざまなタイプのセクションは、訂正能力の増加、つまりＴＥＢ曲線の改良が可能である。
【００９５】
３）Ｚ4上の「ターボコード」に対する１６の状態基本トレリス・セクション
「Ｚ4」上の基本トレリス・セクション「Ｎ」は、以下の式の生成行列ＧMを有するパラメータＮ［８，４，６］を備えたＲｏｂｉｎｓｏｎ−Ｎｏｒｄｓｔｒｏｍ符号と等価であり、整数モジュロ４のリングであるＺ4＝｛０，１，２，３｝内で取られる記号を備えた符号語の集合を表わす。
【数２】
2004304807.tif 000004
【００９６】
Ｚ4の４つの記号｛０，１，２，３｝は、以下の２ビットＧｒａｙマッピングに相当する。
【数３】
2004304807.tif 000005
【００９７】
図９にTannerグラフにより単純化して示すセクションＮは、ラベル・ブランチ（ｂ0，ｂ1，ｂ2，ｂ3）を経由して開始状態（ｓ0，ｓ1）から到達状態（ｓ2，ｓ3）までのパスのセットにより、Ｎ［８，４，６］符合の符号語のセットを表わす。ラベルおよび状態ベクトルは行列式で関連付けされる。
（ｓ0，ｓ1，ｓ2，ｓ3）＝（ｂ0，ｂ1，ｂ2，ｂ3）ＰN
【００９８】
Ｚ4上の２つの記号の４つのパケット（ｓ0，ｓ1）と（ｓ2，ｓ3）と（ｂ0，ｂ1）と（ｂ2，ｂ3）とに分割されるＮ［８，４，６］符号は、２つの「軽量化」記号パケットの以下の分散である、
４つのうち、０の軽量化パケットを有する１語（ゼロ語）と、
４つのうち、３つの軽量化パケットを有する６０語、つまり、符号語の約２３％と、
４つのうち、４つの軽量化パケットを有する１９５語（すなわち、符号語の７６％）と
を有する。
【００９９】
なお、特性「４つのうち、少なくとも３つ」は、ハミング［８，４，４］２進符号に対して、Ｚ4上のＮ［８，４，６］符号により強調されている。したがって、Ｚ4上の２つの状態記号がそれぞれ２ビットで符号化されているため、この１６の状態基本セクションにより構成されるトレリスを使用することが重要である。
【０１００】
基本ブロックのラベル上の記号を分解して配列するための同一パターンを使用して、前述のＨから引き出されるセクションと同様に、引き出されるすべてのセクションを得ることができる。
【０１０１】
４）Ｚ8上の「ターボコード」に対する６４の状態基本セクション
「Ｚ8上の」基本トレリスのセクション「Ｍ」は、以下の式の生成行列ＧMを有する、整数モジュロ８のリングであるＺ8＝｛０，１，．．．，７｝内で取られる記号を有する符号語の集合を表わす。
【数４】
2004304807.tif 000006
Ｚ8の記号｛０，１，．．．，７｝は３ビットの整数の標準２進符号化に相当する。
【数５】
2004304807.tif 000007
【０１０２】
図１０にＴａｎｎｅｒグラフにより単純化して示すセクションＭは、ラベル・ブランチ（ｂ0，ｂ1，ｂ2，ｂ3）を経由して開始状態（ｓ0，ｓ1）から到達状態（ｓ2，ｓ3）までのパスの集合により、Ｍ［８，４］符合の符号語の集合を表わす。状態およびラベル・ベクトルは、以下の行列式により関連付けされる。
（ｓ0，ｓ1，ｓ2，ｓ3）＝（ｂ0，ｂ1，ｂ2，ｂ3）ＰM
【０１０３】
Ｚ8上の２つの記号の４つのパケット（ｓ0，ｓ1）と（ｓ2，ｓ3）と（ｂ0，ｂ1）と（ｂ2，ｂ3）とに分割されるＭ［８，４］符号は、２つの「軽量化」記号パケットの以下の分散である、
４つのうち、０の軽量化パケットを有する１語（ゼロ語）と、
４つのうち、３つの軽量化パケットを有する２５２語、すなわち、符号語の約６％と、
４つのうち、４つの軽量化パケットを有する３４４３語、すなわち、符号語の９４％と
を有する。
【０１０４】
なお、特性「４つのうち、少なくとも３つ」は、４要素Ｎ［８，４，６］符号およびハミング［８，４，４］２進符号に対して、Ｚ8上のこのＭ［８，４］符号により強調されている。
【０１０５】
トレリス・ステージを連接してトレリスを用いて大きい符号を効率的に構成する間に重要である、同一特性「４つのうち、少なくとも３つ」を有する他の符号［８，４］を見出すこともできる。
【０１０６】
したがって、Ｚ8上の２つの状態記号がそれぞれ３ビットで符号化されているため、この６４状態基本セクションにより構成されるトレリスを使用することは重要である。
【０１０７】
基本ブロックのラベル上の記号を分解して配列するための同一パターンを使用して、前述のセクションＮおよびＨから引き出されるセクションと同様に、引き出されるすべてのセクションを得ることができる。
【図面の簡単な説明】
【０１０８】
【図１】本発明の第１実施形態により用いられる、要素符号の基本セクションおよび対応するＴａｎｎｅｒグラフを示す概略図である。
【図２】図１によるセクションによって生成される並列ターボコードの例を示す概略図である。
【図３】図１のセクションにより生成される別のトレリス例を示す概略図である。
【図４】図３のトレリスによる符号を用いる、３つの順列を有する並列ターボコードを示す概略図である。
【図５】ａおよびｂは、異なるタイプの符号および異なる繰返し回数についての２進誤り率曲線を示すグラフである。
【図６】ｃおよびｄは、異なるタイプの符号および異なる繰返し回数についての２進誤り率曲線を示すグラフである。
【図７】異なるタイプの符号および異なる繰返し回数についての２進誤り率曲線を示すグラフである。
【図８】本発明の手法からの復号化結果と従来技術からの３つの他の手法との比較を示すグラフである。
【図９】１６の状態基本セクション符号に対するＴａｎｎｅｒグラフを示す概略図である。
【図１０】６４の状態基本セクション符号に対するＴａｎｎｅｒグラフを示す概略図である。
【図１】
2004304807.tif 000008
【図２】
2004304807.tif 000009
【図３】
2004304807.tif 000010
【図４】
2004304807.tif 000011
【図５】
2004304807.tif 000012
【図６】
2004304807.tif 000013
【図７】
2004304807.tif 000014
【図８】
2004304807.tif 000015
【図９】
2004304807.tif 000016
【図１０】
2004304807.tif 000017
【外国語明細書】
2004304807.tif 000018
2004304807.tif 000019
2004304807.tif 000020
2004304807.tif 000021
2004304807.tif 000022
2004304807.tif 000023
2004304807.tif 000024
2004304807.tif 000025
2004304807.tif 000026
2004304807.tif 000027
2004304807.tif 000028
2004304807.tif 000029
2004304807.tif 000030
2004304807.tif 000031
2004304807.tif 000032
2004304807.tif 000033
2004304807.tif 000034
2004304807.tif 000035
2004304807.tif 000036
2004304807.tif 000037
2004304807.tif 000038
2004304807.tif 000039
2004304807.tif 000040
2004304807.tif 000041
2004304807.tif 000042