JPH07254861A - ヴィタビ復号方法及び畳み込み符号化伝送方法 - Google Patents
ヴィタビ復号方法及び畳み込み符号化伝送方法Info
- Publication number
- JPH07254861A JPH07254861A JP4578694A JP4578694A JPH07254861A JP H07254861 A JPH07254861 A JP H07254861A JP 4578694 A JP4578694 A JP 4578694A JP 4578694 A JP4578694 A JP 4578694A JP H07254861 A JPH07254861 A JP H07254861A
- Authority
- JP
- Japan
- Prior art keywords
- path
- information
- code
- reliability information
- paths
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Error Detection And Correction (AREA)
- Digital Transmission Methods That Use Modulated Carrier Waves (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】
【目的】 各復号シンボルについて正しく信頼度情報を
得る。 【構成】 送信側で情報系列２１を分割し、固定パター
ンのダミービット２２を挿入して送出し、受信側で各フ
レームの終りのダミービット２２（この例ではすべて−
１）によって符号トレリスを終端し、その上でヴィタビ
アルゴリズムを実行し、唯一の生き残りパス２３を決定
する。そのパス２３上の各時点ｋでマージする対向パス
２４の両パスメトリックの差Δｋを計算し、パス２４が
パス２３からダイバージしてからマージするまでの間で
互いの情報シンボルが異なる時点でのパス２３上の情報
シンボルに対応した信頼度情報を更新していく。
得る。 【構成】 送信側で情報系列２１を分割し、固定パター
ンのダミービット２２を挿入して送出し、受信側で各フ
レームの終りのダミービット２２（この例ではすべて−
１）によって符号トレリスを終端し、その上でヴィタビ
アルゴリズムを実行し、唯一の生き残りパス２３を決定
する。そのパス２３上の各時点ｋでマージする対向パス
２４の両パスメトリックの差Δｋを計算し、パス２４が
パス２３からダイバージしてからマージするまでの間で
互いの情報シンボルが異なる時点でのパス２３上の情報
シンボルに対応した信頼度情報を更新していく。
Description
【０００１】
【産業上の利用分野】この発明は、誤り訂正符号をヴィ
タビアルゴリズムを用いて復号する際に、ビット毎の復
号結果とともにそれに対応した信頼度情報を同時に出力
する復号方法に関するものである。具体的応用として
は、連接符号（Ｃｏｎｃａｔｅｎａｔｅｄ Ｃｏｄｅ）
による誤り訂正において、内符号の復号過程で出力され
る信頼度情報を用いて外符号を軟判定復号することによ
る誤り率特性の改善、あるいは、選択ダイバーシティに
おける選択制御を信頼度情報を参照して行う、などが挙
げられる。
タビアルゴリズムを用いて復号する際に、ビット毎の復
号結果とともにそれに対応した信頼度情報を同時に出力
する復号方法に関するものである。具体的応用として
は、連接符号（Ｃｏｎｃａｔｅｎａｔｅｄ Ｃｏｄｅ）
による誤り訂正において、内符号の復号過程で出力され
る信頼度情報を用いて外符号を軟判定復号することによ
る誤り率特性の改善、あるいは、選択ダイバーシティに
おける選択制御を信頼度情報を参照して行う、などが挙
げられる。
【０００２】
【従来の技術】例えば図５Ａに示すシステム構成におい
て、送信側１で送信すべき情報系列２を１次誤り訂正符
号器３で符号化（たたみ込み符号化）し、その符号化系
列４（外符号）を、２次誤り訂正符号器５で再度符号化
（たたみ込み符号化）してその符号化系列６（内符号）
を送信し、受信側７で内符号６のヴィタビ復号器８によ
る復号を行い、その後復号された外符号と、外符号９の
ヴィタビ復号器１０による復号を行い、復号結果１１を
出力する。このような連接符号の復号化を考える。説明
の簡単のために、符号化系列は２値系列とする。一般
に、ヴィタビアルゴリズムによる復号を行う場合には、
受信シンボルと符号シンボルとのユークリッド距離によ
りブランチメトリックを計算して最尤復号を行う方法
（軟判定復号）のほうが、受信系列を識別判定してから
復号を行う方法（硬判定復号）よりも、誤り率特性が２
ｄＢから３ｄＢ程良くなることが知られている〔Ｓ．Ｌ
ｉｎ ａｎｄ Ｄ．Ｊ．Ｃｏｓｔｅｌｌｏ，Ｊｒ．，
“Ｅｒｒｏｒ Ｃｏｎｔｒｏｌ Ｃｏｄｉｎｇ：Ｆｕｎ
ｄａｍｅｎｔａｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ
ｓ”（Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，ｐｐ．３２２〜３
２８，１９８３）参照〕。しかし図５Ａの受信側７で
は、内符号６のヴィタビ復号器８は２値の復号系列のみ
を出力する。このため、これを入力とする外符号９のヴ
ィタビ復号器１０は硬判定復号を行うことになり、軟判
定復号による利得が得られないことになる。
て、送信側１で送信すべき情報系列２を１次誤り訂正符
号器３で符号化（たたみ込み符号化）し、その符号化系
列４（外符号）を、２次誤り訂正符号器５で再度符号化
（たたみ込み符号化）してその符号化系列６（内符号）
を送信し、受信側７で内符号６のヴィタビ復号器８によ
る復号を行い、その後復号された外符号と、外符号９の
ヴィタビ復号器１０による復号を行い、復号結果１１を
出力する。このような連接符号の復号化を考える。説明
の簡単のために、符号化系列は２値系列とする。一般
に、ヴィタビアルゴリズムによる復号を行う場合には、
受信シンボルと符号シンボルとのユークリッド距離によ
りブランチメトリックを計算して最尤復号を行う方法
（軟判定復号）のほうが、受信系列を識別判定してから
復号を行う方法（硬判定復号）よりも、誤り率特性が２
ｄＢから３ｄＢ程良くなることが知られている〔Ｓ．Ｌ
ｉｎ ａｎｄ Ｄ．Ｊ．Ｃｏｓｔｅｌｌｏ，Ｊｒ．，
“Ｅｒｒｏｒ Ｃｏｎｔｒｏｌ Ｃｏｄｉｎｇ：Ｆｕｎ
ｄａｍｅｎｔａｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ
ｓ”（Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，ｐｐ．３２２〜３
２８，１９８３）参照〕。しかし図５Ａの受信側７で
は、内符号６のヴィタビ復号器８は２値の復号系列のみ
を出力する。このため、これを入力とする外符号９のヴ
ィタビ復号器１０は硬判定復号を行うことになり、軟判
定復号による利得が得られないことになる。
【０００３】これに対してＪ．Ｈａｇｅｎａｕｅｒと
Ｐ．Ｈｏｅｈｅｒは、内符号の復号を行う際に、受信シ
ンボルの事後確率を用いて復号系列に対応したシンボル
毎の信頼度情報を算出し、これと復号系列を用いて外符
号の軟判定復号を行うことを提案している〔Ｊ．Ｈａｇ
ｅｎａｕｅｒ ａｎｄ Ｐ．Ｈｏｅｈｅｒ，“Ａ Ｖｉ
ｔｅｒｂｉ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈ Ｓｏｆｔ
−Ｄｅｃｉｓｉｏｎ Ｏｕｔｐｕｔｓ ａｎｄ ｉｔｓ
Ａｐｐｌｉｃａｔｉｏｎｓ”，ＩＥＥＥ ＧＣＯＭ，
Ｎｏ．４７．１．１，１９８９（文献１）〕。その復号
装置構成は図５Ｂに示すように、内符号６を復号するヴ
ィタビ復号器１２から、２値の復号系列９に加えてそれ
に対応した信頼度情報１３を出力する。従来のヴィタビ
復号を行うアルゴリズムに加えて、信頼度情報１３は次
の反復アルゴリズムにより生成される。
Ｐ．Ｈｏｅｈｅｒは、内符号の復号を行う際に、受信シ
ンボルの事後確率を用いて復号系列に対応したシンボル
毎の信頼度情報を算出し、これと復号系列を用いて外符
号の軟判定復号を行うことを提案している〔Ｊ．Ｈａｇ
ｅｎａｕｅｒ ａｎｄ Ｐ．Ｈｏｅｈｅｒ，“Ａ Ｖｉ
ｔｅｒｂｉ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈ Ｓｏｆｔ
−Ｄｅｃｉｓｉｏｎ Ｏｕｔｐｕｔｓ ａｎｄ ｉｔｓ
Ａｐｐｌｉｃａｔｉｏｎｓ”，ＩＥＥＥ ＧＣＯＭ，
Ｎｏ．４７．１．１，１９８９（文献１）〕。その復号
装置構成は図５Ｂに示すように、内符号６を復号するヴ
ィタビ復号器１２から、２値の復号系列９に加えてそれ
に対応した信頼度情報１３を出力する。従来のヴィタビ
復号を行うアルゴリズムに加えて、信頼度情報１３は次
の反復アルゴリズムにより生成される。
【０００４】符号トレリス上の時点ｋでの状態Ｓｋ（０
≦Ｓｋ≦２p −１，ｐ：符号の拘束長）において、 ｉ）Ｓｋにマージする２つのパスの両パスメトリックの
差Δを記憶 ii）信頼度情報Ｌｋ（Ｓｋ）に十分大きな値の初期値を
代入 iii)ｊ＝ｋ−ｐからｊ＝ｋ−δ（δ：パスメモリ長）の
間で、Ｓｋでマージする２つのパス（生き残りパスと対
抗パス）の時点ｊｅ（ｅ＝１，２，…）での情報シンボ
ルが互いに異なる場合、生き残りパス上のその情報シン
ボルに対応する信頼度情報Ｌｊを Ｌｊ＝ｍｉｎ（Ｌｊ，αΔ），α：定数（符号間の最大
距離と伝送路のＳ／Ｎとで決る） （Ｃ＝ｍｉｎ（ａ，ｂ）はａとｂのうち小さい方をＣと
する）で更新 iv）パスメモリから、復号系列とそれに対応した信頼度
情報Ｌｊを出力 符号トレリスの例を図５Ｃに示す。図５Ｂにおいて、外
符号のヴィタビ復号器１４では、復号系列９とそれに対
応した信頼度情報１３との積に符号トレリス上の符号シ
ンボルをかけることでシンボルメトリック（ブランチメ
トリック）を計算し、通常のヴィタビアルゴリズムによ
る復号を行い復号結果１５を出力する。例えば図５Ｃに
おいて状態Ｓｋに実線のパス１６と１７がマージし、こ
の両パス１６と１７は時点ｋ−５の状態Ｓｋ−５でダイ
バージしたものであって、これらパス１６，１７の時点
ｋ−５，ｋ−３で情報シンボルが互いに異なっており、
これらの時点ｋ−５，ｋ−３で生き残りパス（この例で
はパス１６とする）上の情報シンボルに対応する信頼度
情報Ｌｊの更新を前述のように行う。なお各パスに沿っ
て付けた「＋１」と「−１」はその時点での情報シンボ
ルを示す。
≦Ｓｋ≦２p −１，ｐ：符号の拘束長）において、 ｉ）Ｓｋにマージする２つのパスの両パスメトリックの
差Δを記憶 ii）信頼度情報Ｌｋ（Ｓｋ）に十分大きな値の初期値を
代入 iii)ｊ＝ｋ−ｐからｊ＝ｋ−δ（δ：パスメモリ長）の
間で、Ｓｋでマージする２つのパス（生き残りパスと対
抗パス）の時点ｊｅ（ｅ＝１，２，…）での情報シンボ
ルが互いに異なる場合、生き残りパス上のその情報シン
ボルに対応する信頼度情報Ｌｊを Ｌｊ＝ｍｉｎ（Ｌｊ，αΔ），α：定数（符号間の最大
距離と伝送路のＳ／Ｎとで決る） （Ｃ＝ｍｉｎ（ａ，ｂ）はａとｂのうち小さい方をＣと
する）で更新 iv）パスメモリから、復号系列とそれに対応した信頼度
情報Ｌｊを出力 符号トレリスの例を図５Ｃに示す。図５Ｂにおいて、外
符号のヴィタビ復号器１４では、復号系列９とそれに対
応した信頼度情報１３との積に符号トレリス上の符号シ
ンボルをかけることでシンボルメトリック（ブランチメ
トリック）を計算し、通常のヴィタビアルゴリズムによ
る復号を行い復号結果１５を出力する。例えば図５Ｃに
おいて状態Ｓｋに実線のパス１６と１７がマージし、こ
の両パス１６と１７は時点ｋ−５の状態Ｓｋ−５でダイ
バージしたものであって、これらパス１６，１７の時点
ｋ−５，ｋ−３で情報シンボルが互いに異なっており、
これらの時点ｋ−５，ｋ−３で生き残りパス（この例で
はパス１６とする）上の情報シンボルに対応する信頼度
情報Ｌｊの更新を前述のように行う。なお各パスに沿っ
て付けた「＋１」と「−１」はその時点での情報シンボ
ルを示す。
【０００５】
【発明が解決しようとする課題】しかしながら、上記の
アルゴリズムでは、各状態ＳｋでΔを計算して信頼度情
報Ｌｊを更新していくため、例えば図５Ｃで、状態Ｓ′
ｋにマージする点線で示す２つのパス１８，１９の各パ
スメトリックが、同じ時点ｋの他の状態Ｓ′ｋでマージ
するパス１６，１７の各パスメトリックと比べてともに
小さく（パスメトリックが小さいということは、そのパ
スが符号トレリス上の正しいパスである可能性が低いこ
とを意味する）、しかもその差Δ′が小さい場合、パス
メトリックの高いパス上（図５Ｃのパス１６上）にあ
り、本来は確からしいはずの情報シンボル（下線）に対
応した信頼度情報が、確からしさが悪いΔ′によって更
新されてしまい、実際の信頼度を反映しない可能性がで
てくるという欠点がある。
アルゴリズムでは、各状態ＳｋでΔを計算して信頼度情
報Ｌｊを更新していくため、例えば図５Ｃで、状態Ｓ′
ｋにマージする点線で示す２つのパス１８，１９の各パ
スメトリックが、同じ時点ｋの他の状態Ｓ′ｋでマージ
するパス１６，１７の各パスメトリックと比べてともに
小さく（パスメトリックが小さいということは、そのパ
スが符号トレリス上の正しいパスである可能性が低いこ
とを意味する）、しかもその差Δ′が小さい場合、パス
メトリックの高いパス上（図５Ｃのパス１６上）にあ
り、本来は確からしいはずの情報シンボル（下線）に対
応した信頼度情報が、確からしさが悪いΔ′によって更
新されてしまい、実際の信頼度を反映しない可能性がで
てくるという欠点がある。
【０００６】以上は、連接符号を例に説明してきたが、
内符号の復号過程で得られる信頼度情報の利用には、外
符号の復号に限らない。例えば、移動通信において、選
択ダイバーシティ受信を行う際に、その複数の伝搬経路
についてのそれぞれの受信復号の選択制御のために信頼
度情報Ｌｊを参照するなどの利用形態も考えられる。こ
の場合、信頼度情報が復号結果の信頼度を正しく反映し
ているかが重要となる。上述したように、従来の手法で
は、復号結果の信頼度を正しく反映しない可能性がでて
くるという欠点がある。
内符号の復号過程で得られる信頼度情報の利用には、外
符号の復号に限らない。例えば、移動通信において、選
択ダイバーシティ受信を行う際に、その複数の伝搬経路
についてのそれぞれの受信復号の選択制御のために信頼
度情報Ｌｊを参照するなどの利用形態も考えられる。こ
の場合、信頼度情報が復号結果の信頼度を正しく反映し
ているかが重要となる。上述したように、従来の手法で
は、復号結果の信頼度を正しく反映しない可能性がでて
くるという欠点がある。
【０００７】この発明の目的は、たたみ込み符号のヴィ
タビアルゴリズムによる復号過程において、復号結果に
対応した信頼度情報を求める際に、符号トレリス上のあ
る状態にマージする２つのパスで、パスメトリックがそ
れぞれ低くその差が小さいパス同志によって計算された
Δによって情報シンボルに対応した信頼度情報を更新し
てしまうといった問題を解決し、復号系列とその信頼度
を正しく反映した信頼度情報を出力する復号方法を提供
する。
タビアルゴリズムによる復号過程において、復号結果に
対応した信頼度情報を求める際に、符号トレリス上のあ
る状態にマージする２つのパスで、パスメトリックがそ
れぞれ低くその差が小さいパス同志によって計算された
Δによって情報シンボルに対応した信頼度情報を更新し
てしまうといった問題を解決し、復号系列とその信頼度
を正しく反映した信頼度情報を出力する復号方法を提供
する。
【０００８】
【課題を解決するための手段】請求項１の発明によれ
ば、符号トレリスを終端した唯一の生き残りパスのみに
ついて、信頼度情報の更新と、情報シンボルとその信頼
度情報を出力することを実行する。請求項２の発明によ
れば、各時点で各生き残りパス中のパスメトリックの最
も大きい生き残りパスについてのみ、信頼度情報の更新
と、情報シンボルとその信頼度情報を出力することを実
行する。
ば、符号トレリスを終端した唯一の生き残りパスのみに
ついて、信頼度情報の更新と、情報シンボルとその信頼
度情報を出力することを実行する。請求項２の発明によ
れば、各時点で各生き残りパス中のパスメトリックの最
も大きい生き残りパスについてのみ、信頼度情報の更新
と、情報シンボルとその信頼度情報を出力することを実
行する。
【０００９】請求項３の発明によれば送信側で情報系列
をｎビットごとに分別して、ｍビット（ｍ＜ｎ，ｍ：受
信側のパスメモリ長以上）の固定パターンのダミービッ
トを挿入し、そのダミービットが挿入された情報系列を
畳み込み符号化して送信し、受信側で請求項１の発明に
より復号する。
をｎビットごとに分別して、ｍビット（ｍ＜ｎ，ｍ：受
信側のパスメモリ長以上）の固定パターンのダミービッ
トを挿入し、そのダミービットが挿入された情報系列を
畳み込み符号化して送信し、受信側で請求項１の発明に
より復号する。
【００１０】
【実施例】請求項１の発明の実施例を図１を参照して説
明する。この発明では符号トレリスを終端した唯一の生
き残りパスのみについて信頼度情報の更新を行う。この
ように終端した唯一の生き残りパスを間違いなく得るた
めに、図１Ａに示すように送信側の送信情報系列２１に
対し適当な間隔で長さｍの固定パターン（例えばすべて
−１）のダミービット２２を挿入する。ダミービット２
２の符号長ｍは受信側の復号器におけるパスメモリの長
さと等しいか、これより長くする。隣接ダミービット２
２の間の情報系列２１の長さｎは、ｍより大とするが、
ｍ＋ｎだけ復号が遅れるのであまり大とすると問題とな
ることがある、一方、ｎを小にすると伝送効率が悪くな
る。
明する。この発明では符号トレリスを終端した唯一の生
き残りパスのみについて信頼度情報の更新を行う。この
ように終端した唯一の生き残りパスを間違いなく得るた
めに、図１Ａに示すように送信側の送信情報系列２１に
対し適当な間隔で長さｍの固定パターン（例えばすべて
−１）のダミービット２２を挿入する。ダミービット２
２の符号長ｍは受信側の復号器におけるパスメモリの長
さと等しいか、これより長くする。隣接ダミービット２
２の間の情報系列２１の長さｎは、ｍより大とするが、
ｍ＋ｎだけ復号が遅れるのであまり大とすると問題とな
ることがある、一方、ｎを小にすると伝送効率が悪くな
る。
【００１１】受信側でダミービット２２により符号トレ
リスが終端した生き残りパスを利用するが、伝送誤りが
多く、仮りに、終端した状態がダミービット２２のそれ
と異っている場合でも、終端すべき状態が予めわかって
いるから、その状態に到達したパスのパスメトリックの
大きい方を、唯一の生き残りパスとして用い、そのパス
について信頼度情報の更新を行う。
リスが終端した生き残りパスを利用するが、伝送誤りが
多く、仮りに、終端した状態がダミービット２２のそれ
と異っている場合でも、終端すべき状態が予めわかって
いるから、その状態に到達したパスのパスメトリックの
大きい方を、唯一の生き残りパスとして用い、そのパス
について信頼度情報の更新を行う。
【００１２】例えば符号トレリス上において、図１Ｂに
示すように、各ｎビットの情報ビット２１とその前後の
ダミービット２２とからなる各フレームごとに、その後
端部のダミービット２２によって符号トレリスを終端
し、この上でヴィタビアルゴリズムを実行することによ
り、唯一の生き残りパスを決定する。つぎにこの生き残
りパス２３上の各時点ｋでマージする対抗パス２４のパ
スメトリックと、時点ｋでのパス２３のパスメトリック
との差Δｋを計算する。そしてパス２４がパス２３から
ダイバージしてからマージするまでの間で、パスブラン
チ上の互いの情報シンボルが異なる時点ｊｅ（ｅ＝１，
２，…）でのパス２３上の情報シンボルに対応した信頼
度情報Ｌｊを適当な初期値Ｌｊから Ｌｊ＝ｍｉｎ（Ｌｊ，αΔｋ）， α：定数 により更新していく。この反復をフレーム内のすべての
ｋについて行い、最終的なＬｊをそれに対応した情報シ
ンボルの信頼度情報として出力する。例えば、連接符号
の外符号の復号を行う場合には、復号結果とそれに対応
した信頼度情報を用いて軟判定復号を行うことができ
る。
示すように、各ｎビットの情報ビット２１とその前後の
ダミービット２２とからなる各フレームごとに、その後
端部のダミービット２２によって符号トレリスを終端
し、この上でヴィタビアルゴリズムを実行することによ
り、唯一の生き残りパスを決定する。つぎにこの生き残
りパス２３上の各時点ｋでマージする対抗パス２４のパ
スメトリックと、時点ｋでのパス２３のパスメトリック
との差Δｋを計算する。そしてパス２４がパス２３から
ダイバージしてからマージするまでの間で、パスブラン
チ上の互いの情報シンボルが異なる時点ｊｅ（ｅ＝１，
２，…）でのパス２３上の情報シンボルに対応した信頼
度情報Ｌｊを適当な初期値Ｌｊから Ｌｊ＝ｍｉｎ（Ｌｊ，αΔｋ）， α：定数 により更新していく。この反復をフレーム内のすべての
ｋについて行い、最終的なＬｊをそれに対応した情報シ
ンボルの信頼度情報として出力する。例えば、連接符号
の外符号の復号を行う場合には、復号結果とそれに対応
した信頼度情報を用いて軟判定復号を行うことができ
る。
【００１３】即ち図２に示すように通常のヴィタビ復号
器におけるメトリックコンピュータ２６で、符号トレリ
ス上のブランチメトリック２７を計算し、出力する。こ
のブランチメトリック２７と、パスメモリ２８に記憶さ
れているパスメトリック２９とを用いて各状態での生き
残りパスの選択、情報シンボル３１の出力がＡＣＳ（Ａ
ｄｄ−Ｃｏｍｐａｒｅ−Ｓｅｌｅｃｔ）回路３２で行
う。この出力された情報シンボル２９はパスメモリ（符
号トレリスを終端して用いるので、パスメモリ長は内符
号のフレーム長）２８に入り、各状態の生き残りパス、
情報シンボル、マージするパス、それぞれのパスメトリ
ックを記憶する。そして、符号系列のフレームの終わり
まできた時点で、唯一の生き残りパス上の各時点での対
抗パスとのパスメトリックの差Δを算出し、信頼度情報
を更新、記憶する。この反復を終えた時点で、１フレー
ム分の復号系列３３とそれに対応した信頼度情報３４を
出力する。外符号用メトリックコンピュータ３５で、そ
の復号系列３３とそれに対応した信頼度情報３４及び符
号トレリス上の符号シンボルをもちいてブランチメトリ
ックを計算し、ＡＣＳ回路３６、パスメモリ３７によっ
てヴィタビアルゴリズムによる復号を行う。
器におけるメトリックコンピュータ２６で、符号トレリ
ス上のブランチメトリック２７を計算し、出力する。こ
のブランチメトリック２７と、パスメモリ２８に記憶さ
れているパスメトリック２９とを用いて各状態での生き
残りパスの選択、情報シンボル３１の出力がＡＣＳ（Ａ
ｄｄ−Ｃｏｍｐａｒｅ−Ｓｅｌｅｃｔ）回路３２で行
う。この出力された情報シンボル２９はパスメモリ（符
号トレリスを終端して用いるので、パスメモリ長は内符
号のフレーム長）２８に入り、各状態の生き残りパス、
情報シンボル、マージするパス、それぞれのパスメトリ
ックを記憶する。そして、符号系列のフレームの終わり
まできた時点で、唯一の生き残りパス上の各時点での対
抗パスとのパスメトリックの差Δを算出し、信頼度情報
を更新、記憶する。この反復を終えた時点で、１フレー
ム分の復号系列３３とそれに対応した信頼度情報３４を
出力する。外符号用メトリックコンピュータ３５で、そ
の復号系列３３とそれに対応した信頼度情報３４及び符
号トレリス上の符号シンボルをもちいてブランチメトリ
ックを計算し、ＡＣＳ回路３６、パスメモリ３７によっ
てヴィタビアルゴリズムによる復号を行う。
【００１４】次に請求項２の発明の実施例を説明する。
請求項２の発明では終端した符号トレリスを利用するも
のではなく、従ってダミービット２２の送信は必要とし
ない。この発明では、パスメモリ内の各生き残りパスの
うち、パスメトリックの最も大きい生き残りパスを選
ぶ。例えば図３Ａに示すように、時点ｋで状態Ｓｋにパ
ス４１と４２がマージし、状態Ｓ′ｋにパス４３と４４
がマージしているが、その各生き残りパス４１と４４と
では対応するパスメトリックがパス４１の方が大きいか
ら、このパス４１だけを選ぶ。つぎにこの生き残りパス
４１上の各時点ｋでマージする対抗パス４２のパスメト
リックと、時点ｋでのパス４１のパスメトリックとの差
Δ′ｋを計算する。そしてパス４２が４１からダイバー
ジしてからマージするまでの間で、パスブランチ上の互
いの情報シンボルが異なる時点ｊｅ（ｅ＝１，２，…）
でのパス４１上の情報シンボルに対応した信頼度情報
Ｌ′ｊを適当な初期値Ｌ′ｊから Ｌ′ｊ＝ｍｉｎ（Ｌ′ｊ，αΔ′ｋ）， α：定数 により更新していく。この反復をパスメモリ内のすべて
のｋについて行い、パスメモリより出力される情報シン
ボルに対応したＬ′ｊを情報シンボルに対応した信頼度
情報として出力する。例えば、連接符号の外符号の復号
を行う場合には、復号結果とそれに対応した信頼度情報
を用いて軟判定復号を行うことができる。
請求項２の発明では終端した符号トレリスを利用するも
のではなく、従ってダミービット２２の送信は必要とし
ない。この発明では、パスメモリ内の各生き残りパスの
うち、パスメトリックの最も大きい生き残りパスを選
ぶ。例えば図３Ａに示すように、時点ｋで状態Ｓｋにパ
ス４１と４２がマージし、状態Ｓ′ｋにパス４３と４４
がマージしているが、その各生き残りパス４１と４４と
では対応するパスメトリックがパス４１の方が大きいか
ら、このパス４１だけを選ぶ。つぎにこの生き残りパス
４１上の各時点ｋでマージする対抗パス４２のパスメト
リックと、時点ｋでのパス４１のパスメトリックとの差
Δ′ｋを計算する。そしてパス４２が４１からダイバー
ジしてからマージするまでの間で、パスブランチ上の互
いの情報シンボルが異なる時点ｊｅ（ｅ＝１，２，…）
でのパス４１上の情報シンボルに対応した信頼度情報
Ｌ′ｊを適当な初期値Ｌ′ｊから Ｌ′ｊ＝ｍｉｎ（Ｌ′ｊ，αΔ′ｋ）， α：定数 により更新していく。この反復をパスメモリ内のすべて
のｋについて行い、パスメモリより出力される情報シン
ボルに対応したＬ′ｊを情報シンボルに対応した信頼度
情報として出力する。例えば、連接符号の外符号の復号
を行う場合には、復号結果とそれに対応した信頼度情報
を用いて軟判定復号を行うことができる。
【００１５】即ち、例えば図３Ｂに図２と対応する部分
に同一符号を付けて示すように、ＡＣＳ回路４５におい
て、メトリックコンピュータ２６で計算されたブランチ
メトリック２７と、パスメモリ４０からのパスメトリッ
ク２９とを用いて各状態での生き残りパスの選択、最大
パスメトリックを持つ生き残りパスとそれにマージする
対抗パスとのパスメトリックの差Δの算出を行い、情報
シンボル３１、Δ４６及び最大パスメトリックを持つ状
態番号４７をパスメモリ４０に出力する。パスメモリ
（パスメモリ長は、各状態の生き残りパスが時間的に古
い方向へさかのぼったときに、すべてのパスがマージす
るのに十分な長さで、通常は拘束長の５〜６倍程度が用
いられる）４０では、各状態の生き残りパス、情報シン
ボル、パスメトリックを記憶し、Δを用いて信頼度情報
を更新、記憶する。そして、復号系列３３とそれに対応
した信頼度情報３４を出力する。外符号用メトリックコ
ンピュータ３５で復号系列３３とそれに対応した信頼度
情報３４及び符号トレリス上の符号シンボルをもちいて
ブランチメトリックを計算し、ＡＣＳ回路３６、パスメ
モリ３７によってヴィタビアルゴリズムによる復号を行
う。
に同一符号を付けて示すように、ＡＣＳ回路４５におい
て、メトリックコンピュータ２６で計算されたブランチ
メトリック２７と、パスメモリ４０からのパスメトリッ
ク２９とを用いて各状態での生き残りパスの選択、最大
パスメトリックを持つ生き残りパスとそれにマージする
対抗パスとのパスメトリックの差Δの算出を行い、情報
シンボル３１、Δ４６及び最大パスメトリックを持つ状
態番号４７をパスメモリ４０に出力する。パスメモリ
（パスメモリ長は、各状態の生き残りパスが時間的に古
い方向へさかのぼったときに、すべてのパスがマージす
るのに十分な長さで、通常は拘束長の５〜６倍程度が用
いられる）４０では、各状態の生き残りパス、情報シン
ボル、パスメトリックを記憶し、Δを用いて信頼度情報
を更新、記憶する。そして、復号系列３３とそれに対応
した信頼度情報３４を出力する。外符号用メトリックコ
ンピュータ３５で復号系列３３とそれに対応した信頼度
情報３４及び符号トレリス上の符号シンボルをもちいて
ブランチメトリックを計算し、ＡＣＳ回路３６、パスメ
モリ３７によってヴィタビアルゴリズムによる復号を行
う。
【００１６】
【発明の効果】以上述べたように請求項１の発明によれ
ば、符号トレリス上で終端した唯一の生き残りパス（し
かも既知の状態にマージする）についてのみ、Δの演算
をし、かつ信頼度情報の更新を行っているため、パスメ
トリックの低い、つまり正しいパスである可能性が低
い、パス同士で計算されたΔによって信頼度情報が更新
されるおそれはない。
ば、符号トレリス上で終端した唯一の生き残りパス（し
かも既知の状態にマージする）についてのみ、Δの演算
をし、かつ信頼度情報の更新を行っているため、パスメ
トリックの低い、つまり正しいパスである可能性が低
い、パス同士で計算されたΔによって信頼度情報が更新
されるおそれはない。
【００１７】同様に請求項２の発明によれば、各時点で
マージするパス中のパスメトリックが最大の生き残りパ
スのみについて信頼度情報の更新を行うため、パスメト
リックの低いパス同士で計算されたΔによって信頼度情
報が更新されるおそれはない。請求項１，２の各発明方
法を用いてシミュレーションによって連接符号の復号を
行った後の誤り率特性を図４の曲線５１，５２にそれぞ
れ示す。また硬判定復号後の誤り率特性、前記文献１に
示す手法による復号後の誤り率特性をそれぞれ参照とし
て曲線５３，５４を示す。横軸、縦軸はそれぞれ内符号
復号後の誤り率、外符号復号後の誤り率であり、内符
号、外符号の符号化レートはともに１／２、拘束長はと
もに７とした。内符号復号器出力系列における誤りをラ
ンダム化するためにインタリーブを用いた。そのサイズ
は４０×３２とした。このシミュレーション結果から、
請求項１，２の発明による復号を行うことによって、硬
判定復号を行ったときと比べて誤り率特性が大きく改善
（誤り率が、請求項１の復号で２桁程度、請求項２の復
号で１桁程度）しているのがわかる。それに対して、ハ
ーゲナウアらの手法による復号を行っても、硬判定復号
に対する改善はごくわずかである。
マージするパス中のパスメトリックが最大の生き残りパ
スのみについて信頼度情報の更新を行うため、パスメト
リックの低いパス同士で計算されたΔによって信頼度情
報が更新されるおそれはない。請求項１，２の各発明方
法を用いてシミュレーションによって連接符号の復号を
行った後の誤り率特性を図４の曲線５１，５２にそれぞ
れ示す。また硬判定復号後の誤り率特性、前記文献１に
示す手法による復号後の誤り率特性をそれぞれ参照とし
て曲線５３，５４を示す。横軸、縦軸はそれぞれ内符号
復号後の誤り率、外符号復号後の誤り率であり、内符
号、外符号の符号化レートはともに１／２、拘束長はと
もに７とした。内符号復号器出力系列における誤りをラ
ンダム化するためにインタリーブを用いた。そのサイズ
は４０×３２とした。このシミュレーション結果から、
請求項１，２の発明による復号を行うことによって、硬
判定復号を行ったときと比べて誤り率特性が大きく改善
（誤り率が、請求項１の復号で２桁程度、請求項２の復
号で１桁程度）しているのがわかる。それに対して、ハ
ーゲナウアらの手法による復号を行っても、硬判定復号
に対する改善はごくわずかである。
【００１８】この発明は連接符号による誤り訂正におけ
る内符号の復号過程で出力される信頼度情報を用いて外
符号を軟判定復号する場合のみならず、複数の伝搬経路
の受信復号を誤り訂正復号し、その復号結果を信頼度情
報を用いて選択するダイバーシティ受信、その他にも適
用できる。図１Ａでは情報系列を分割したが、送信情報
系列の最後にのみダミービットを付加してもよい。
る内符号の復号過程で出力される信頼度情報を用いて外
符号を軟判定復号する場合のみならず、複数の伝搬経路
の受信復号を誤り訂正復号し、その復号結果を信頼度情
報を用いて選択するダイバーシティ受信、その他にも適
用できる。図１Ａでは情報系列を分割したが、送信情報
系列の最後にのみダミービットを付加してもよい。
【図１】Ａは請求項１の発明に復号方法に適する送信フ
レームの例を示す図、Ｂは請求項１の発明による復号を
行うときの符号トレリスの例を示す図である。
レームの例を示す図、Ｂは請求項１の発明による復号を
行うときの符号トレリスの例を示す図である。
【図２】請求項１の発明を適用した復号装置を示すブロ
ック図。
ック図。
【図３】Ａは請求項２の発明による復号を行うときの符
号トレリスの例を示す図、Ｂは請求項２の発明を適用し
た復号装置を示すブロック図である。
号トレリスの例を示す図、Ｂは請求項２の発明を適用し
た復号装置を示すブロック図である。
【図４】この発明の方法、従来の方法をそれぞれ用いた
連接符号復号後の誤り率特性のシミュレーション結果を
示す図。
連接符号復号後の誤り率特性のシミュレーション結果を
示す図。
【図５】Ａは連接符号による符号化送信と、その受信復
号とを示すブロック図、Ｂは連接符号の復号において、
ヴィタビ復号と結果とともに信頼度情報とを出力して外
符号を軟判定復号する装置を示すブロック図、Ｃは従来
法により復号を行うときの符号トレリスの例を示す図で
ある。
号とを示すブロック図、Ｂは連接符号の復号において、
ヴィタビ復号と結果とともに信頼度情報とを出力して外
符号を軟判定復号する装置を示すブロック図、Ｃは従来
法により復号を行うときの符号トレリスの例を示す図で
ある。
Claims (3)
- 【請求項１】 入力符号系列を、符号トレリス上でヴィ
タビアルゴリズムにより復号し、 上記符号トレリス上のある時点における各状態から生き
残りパス上の各時点ｋでマージする一対のパスのパスメ
トリックの差Δｋを計算し、 上記一対のパスがそれぞれダイバージしてからマージす
るまでの間でパスブランチ上の互いの情報シンボルが異
なる時点ｊでの、上記一対のパスのパスメトリック中の
大きい（確からしい）方のパス上の上記情報シンボルに
対応した信頼度情報Ｌｊを、初期値Ｌｊから、 Ｌｊ＝ｍｉｎ（Ｌｊ，αΔｋ）， α：定数 により更新して、最終的なＬｊをその情報シンボルに対
応した上記信頼度情報としてその情報シンボルとともに
出力するヴィタビ復号方法において、 上記符号トレリスを終端した唯一の生き残りパスのみに
ついて、上記信頼度情報Ｌｊの更新、上記情報シンボル
とその信頼度情報の出力を実行することを特徴とするヴ
ィタビ復号方法。 - 【請求項２】 入力符号系列を、符号トレリス上でヴィ
タビアルゴリズムにより復号し、 上記符号トレリス上のある時点における各状態から生き
残りパス上の各時点ｋでマージする一対のパスのパスメ
トリックの差Δｋを計算し、 上記一対のパスがそれぞれダイバージしてからマージす
るまでの間でパスブランチ上の互いの情報シンボルが異
なる時点ｊでの、上記一対のパスのパスメトリック中の
大きい（確からしい）方のパス上の上記情報シンボルに
対応した信頼度情報Ｌｊを、初期値Ｌｊから、 Ｌｊ＝ｍｉｎ（Ｌｊ，αΔｋ）， α：定数 により更新して、最終的なＬｊをその情報シンボルに対
応した上記信頼度情報としてその情報シンボルとともに
出力するヴィタビ復号方法において、 上記各時点ｋで各生き残りパスのうちパスメトリックの
最も大きい生き残りパスについてのみ、上記信頼度情報
Ｌｊの更新、上記情報シンボルとその信頼度情報の出力
を実行することを特徴とするヴィタビ復号方法。 - 【請求項３】 送信側で情報系列をｎビットごとに分割
して、ｍビット（ｍ＜ｎ，ｍ：受信側のパスメモリ長以
上）の固定パターンのダミービットを挿入し、 そのダミービットが挿入された情報系列を畳み込み符号
化して送信し、 受信側で受信系列を、符号トレリスを終端したトレリス
上でヴィタビアルゴリズムにより復号し、 その復号の際に、上記符号トレリス上の唯一の生き残り
パスの各時点ｋでマージする対抗パスとのパスメトリッ
クの差Δｋを計算し、 上記生き残りパスと上記その対抗パスがそれぞれダイバ
ージしてからマージするまでの間で、パスブランチ上の
互いの情報シンボルが異なる時点ｊでのその生き残りパ
ス上のその情報シンボルに対応した信頼度情報Ｌｊを初
期値Ｌｊから、 Ｌｊ＝ｍｉｎ（Ｌｊ，αΔｋ）， α：定数 により更新していき、最終的なＬｊをその情報シンボル
に対応した信頼度情報として、その情報シンボルととも
に出力することを特徴とする畳み込み符号化伝送方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4578694A JPH07254861A (ja) | 1994-03-16 | 1994-03-16 | ヴィタビ復号方法及び畳み込み符号化伝送方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4578694A JPH07254861A (ja) | 1994-03-16 | 1994-03-16 | ヴィタビ復号方法及び畳み込み符号化伝送方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH07254861A true JPH07254861A (ja) | 1995-10-03 |
Family
ID=12728971
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4578694A Pending JPH07254861A (ja) | 1994-03-16 | 1994-03-16 | ヴィタビ復号方法及び畳み込み符号化伝送方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH07254861A (ja) |
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1999008412A1 (en) * | 1997-08-11 | 1999-02-18 | Sony Corporation | Device and method for transmitting digital data, device and method for demodulating digital data, and transmission medium |
| WO2000033529A1 (en) * | 1998-11-27 | 2000-06-08 | Kabushiki Kaisha Kenwood | Demodulator |
| WO2000036756A1 (en) * | 1998-12-14 | 2000-06-22 | Sony Corporation | Decoder and decoding method |
| US6118825A (en) * | 1997-08-11 | 2000-09-12 | Sony Corporation | Digital data transmission device and method, digital data demodulation device and method, and transmission medium |
| US6332208B1 (en) | 1997-12-12 | 2001-12-18 | Matsushita Electric Industrial Co., Ltd. | Data transmitting apparatus and data transmitting method |
| US6445755B1 (en) | 1999-09-14 | 2002-09-03 | Samsung Electronics Co, Ltd. | Two-step soft output viterbi algorithm decoder using modified trace back |
| US6668351B1 (en) | 1999-12-14 | 2003-12-23 | Sony Corporation | Decoder and decoding method |
| US6973610B1 (en) * | 1999-07-22 | 2005-12-06 | Siemens Aktiengesellschaft | Method of providing error protection for a data bit flow |
| US7576935B2 (en) | 2000-06-27 | 2009-08-18 | Fujitsu Limited | Apparatus for recording and regenerating data |
-
1994
- 1994-03-16 JP JP4578694A patent/JPH07254861A/ja active Pending
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1999008412A1 (en) * | 1997-08-11 | 1999-02-18 | Sony Corporation | Device and method for transmitting digital data, device and method for demodulating digital data, and transmission medium |
| US6118825A (en) * | 1997-08-11 | 2000-09-12 | Sony Corporation | Digital data transmission device and method, digital data demodulation device and method, and transmission medium |
| US6332208B1 (en) | 1997-12-12 | 2001-12-18 | Matsushita Electric Industrial Co., Ltd. | Data transmitting apparatus and data transmitting method |
| WO2000033529A1 (en) * | 1998-11-27 | 2000-06-08 | Kabushiki Kaisha Kenwood | Demodulator |
| US7058118B1 (en) | 1998-11-27 | 2006-06-06 | Kabushiki Kaisha Kenwood | Demodulator |
| WO2000036756A1 (en) * | 1998-12-14 | 2000-06-22 | Sony Corporation | Decoder and decoding method |
| US6973610B1 (en) * | 1999-07-22 | 2005-12-06 | Siemens Aktiengesellschaft | Method of providing error protection for a data bit flow |
| US6445755B1 (en) | 1999-09-14 | 2002-09-03 | Samsung Electronics Co, Ltd. | Two-step soft output viterbi algorithm decoder using modified trace back |
| US6668351B1 (en) | 1999-12-14 | 2003-12-23 | Sony Corporation | Decoder and decoding method |
| US7576935B2 (en) | 2000-06-27 | 2009-08-18 | Fujitsu Limited | Apparatus for recording and regenerating data |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CA2020899C (en) | Generalized viterbi decoding algorithms | |
| US6484285B1 (en) | Tailbiting decoder and method | |
| US7246294B2 (en) | Method for iterative hard-decision forward error correction decoding | |
| US20050091568A1 (en) | Iterative decoding process | |
| CN100517984C (zh) | 用于移动通信系统的维特比/涡轮联合译码器 | |
| EP2418796B1 (en) | Bitwise reliability indicators from survivor bits in Viterbi decoders | |
| US7480852B2 (en) | Method and system for improving decoding efficiency in wireless receivers | |
| JPH1070471A (ja) | 大きな制約長を持つ場合に有効なソフト判定ビテルビ復号 | |
| US20030188248A1 (en) | Apparatus for iterative hard-decision forward error correction decoding | |
| JPH07254861A (ja) | ヴィタビ復号方法及び畳み込み符号化伝送方法 | |
| US9419656B2 (en) | Decoder and method for decoding an encoded sequence of bits | |
| US8009773B1 (en) | Low complexity implementation of a Viterbi decoder with near optimal performance | |
| EP3996285B1 (en) | Parallel backtracking in viterbi decoder | |
| US8489972B2 (en) | Decoding method and decoding device | |
| CN101228699B (zh) | 用于对尾比特卷积码译码的方法 | |
| Lou | Viterbi decoder design for the IS-95 CDMA forward link | |
| JPH06284018A (ja) | ビタビ復号方法および誤り訂正復号化装置 | |
| US7975212B2 (en) | Sequential decoding method and apparatus thereof | |
| JPWO1995001008A1 (ja) | 誤り検出方法、装置ならびに識別方法 | |
| JP2008118327A (ja) | ビタビ復号方法 | |
| JP7835619B2 (ja) | 誤り訂正装置、誤り訂正方法、及び、誤り訂正プログラム | |
| JP5370487B2 (ja) | 復号方法および復号装置 | |
| JP3337950B2 (ja) | 誤り訂正復号化方法及び誤り訂正復号化装置 | |
| JP2004260391A (ja) | 畳み込み符号の最尤復号器および最尤復号方法 | |
| US7032165B2 (en) | ACS unit in a decoder |