JP3720251B2 - Viterbi decoder - Google Patents

Description

で計算される。但し、式（１）における加算は排他論理和で行う。また、ｘ^Tはｘの転置ベクトルを示す。従って、図３の（ｃ）の状態遷移に伴って出力される符号g₀、g₁は、式（１）に、図３の（ｃ）のｘ₃ｍ、ｍｘ₀（ｍ＝ｘ₂ｘ₁）を代入して、
【００１０】
【数２】

となる。但し、式（２）においてｘ’はｘの論理反転を示す。
【００１１】
以上述べたように、畳み込み符号のトレリス構造（遷移前後の状態番号、および出力される符号）は状態番号ｍ＝０〜２^K-2−１を与えると、一意的に決定される。
【００１２】
したがって、受信側の最尤復号器においては、時点ｔ_nの全ての状態に至る遷移パス（図３の（ｂ）の例では８本）を候補パスとして保持しておき、受信した符号ｒ₀、ｒ₁を手がかりとして送信側の符号器の状態遷移として最も確からしい遷移パスを選択（最尤選択）することで符号器の状態遷移を推定しながら復号を行う。ここで確からしさを具体的に表す量として尤度を用いる。状態番号ｍからｍ’への状態遷移に伴って出力される符号ｇ₀、ｇ₁と、実際に受信した符号ｒ₀、ｒ₁とのハミング距離（幾何学的距離）を、その遷移枝の枝尤度（ブランチメトリック）とする。受信符号ｒ₀、ｒ₁は受信信号ｙ₀、ｙ₁を識別して、ｙ＞０のときはｒ＝０、ｙ＜０のときはｒ＝１とする。このような０、１判定した復号値で求める尤度を硬判定尤度という。
【００１３】
なお、枝尤度には状態遷移に伴う符号（ｇ₀，ｇ₁）＝（０，０）、（０，１）、（１，０）、（１，１） を直交信号点座標（Ｉ，Ｑ）＝（１，１）、（−１，１）、（１，−１）、（−１，−１） に割り当て、直交信号点（Ｉ，Ｑ）と受信信号点（ｙ₀，ｙ₁）とのユークリッド距離、または直交、同相成分の差の絶対値和を尤度として与える軟判定尤度という計算方法もある。
【００１４】
以上で、送信側の説明を終え、次に、受信側の復号について、説明する。
【００１５】
図２は、従来のヴィタビ復号器の構成図であり、枝尤度計算部１で、受信符号が入力される毎に全ての遷移枝の枝尤度を計算して求める。そして求めた枝尤度を用いて、ＡＣＳ部３で状態尤度を計算する。状態尤度は各状態に至る遷移パスの枝尤度を全て加算したものである。実際には図３の（ｂ）のトレリス線図で図示されているように、各状態には２本ずつ遷移枝が入っているので、それぞれの遷移枝の枝尤度を１時点前の状態尤度に加算（Add）して新しい状態尤度を求め、現時点に至る２つの状態遷移の状態尤度を比較（Compare）し、確からしい方の遷移枝を遷移パスとして選択（Select）する。また実際には枝尤度をハミング距離で表しているので、状態尤度も小さい方が確からしい（尤度が高い）ことになる。
【００１６】
ＡＣＳ部３が計算した状態尤度を状態尤度メモリ４に格納するとともに、ＡＣＳ演算（ＡＣＳ：Add Compare Select、加算比較選択演算）処理によって選択した遷移パスの遷移情報をパスメモリ５に送る。パスメモリ５では選択した遷移情報を逐次全て記憶する。データの入力が終了した時点で、状態尤度の最も高い（数値としては最も小さい）状態に至る遷移パスを符号器の遷移パスとして推定し、推定した遷移パスの遷移情報を、最尤復号部６で最尤復号して出力する。
【００１７】
以上述べたように、最尤復号による最尤復号法では、受信データを直ちに復号しないで、情報の確からしさを、パスメモリ５に状態尤度の形で保持しておき、複数の送信シンボルにわたる遷移パスについて復号するようにしているので、受信信号の１シンボル毎に混入する雑音成分の影響を軽減して、誤りを少なくすることが出来る。
【００１８】
なお、この種のヴィタビ復号器として関連するものに、例えば特開平５−３１５９７６号公報等が挙げられる。
【００１９】
【発明が解決しようとする課題】
ヴィタビ復号器においては、畳み込み符号の拘束長Ｋが大きくなるほど、誤り訂正能力が大きくなり、符号誤り率が改善される。そこで、特にＩＣ化技術の進歩とともに、拘束長の大きい符号が用いられるようになっている。しかしながら、ヴィタビ復号器における一連の演算（枝尤度計算、状態尤度計算、ＡＣＳ演算、状態尤度メモリ容量、パスメモリ容量）の処理量は、状態数２^K-1に比例する。従って、拘束長Ｋが小さい時には比較的容易に実行できるが、拘束長Ｋが大きくなると、演算処理量が指数関数的に増加し、処理時間が長くなって実現が困難になる課題がある。
【００２０】
本発明の目的は、ACS処理即ち状態尤度演算処理を、従来よりも少ない演算処理量で実現し且つ性能劣化の少ないヴィタビ復号器を提供することにある。
【００２１】
【課題を解決するための手段】
本発明は、上記の目的を達成するため、ヴィタビ復号器のＡＣＳ演算処理過程に入る前に、状態尤度を判定し、状態尤度がある設定値より小さい状態を含む状態遷移についてのみ通常のＡＣＳ演算処理を行うようにしたことにある。このような処理が可能である理由について、図４を用いて説明する。
【００２２】
図４は、トレリス遷移と生き残りパスを示す図である。図４の（ａ）は、符号化率ｒ＝１／２、拘束長Ｋの畳み込み符号のトレリスの基本トレリスであり、状態番号ｍ、２^K-2＋ｍを始点とし、２ｍ、２ｍ＋１の状態を終点とする基本トレリスである。符号化率ｒ＝１／２、拘束長Ｋの畳み込み符号のトレリスは、この基本トレリスが２^K-2個（ｍ＝０〜２^K-2−１）集まったものである。
【００２３】
図４の（ａ）の基本トレリスの状態でＡＣＳ演算処理が行われると、（ｂ）〜（ｅ）に示すようなトレリス遷移が結果として得られる。すなわち、（ｂ）、（ｃ）は始点の２状態からのパスが各々生残り、パスを一時点延ばした場合であり、（ｄ）、（ｅ）は片方のパスが生残って、終点の２状態に枝分かれした場合である。後者の場合、生残らなかったパスは生き残りパスにmerge（マージ、合流）されたという。トレリス線図の時点をさらに一時点延ばすと、（ｆ）に示すような4状態間のトレリス線図が得られる。４状態トレリスの始点は（ｍ、２^K-3＋ｍ、２^k-2＋ｍ、３・２^K-3＋ｍ）の４状態、終点は（４ｍ、４ｍ＋１、４ｍ＋２、４ｍ＋３）の４状態（ｍ＝０〜２^K-3−１）である。
この４状態トレリスでＡＣＳ演算処理が行われた場合のトレリス線図の一例を（g）に示す。（g）では一例として、拘束長Ｋ＝１０（状態数２^K-1＝５１２）、状態番号ｍ＝１４の場合について示している。トレリス線図のノードに付した数字は、その時点の状態番号を示す。状態（１４、２７０）から状態（２８、２９）への遷移（すなわち、状態番号１４のノードと状態番号２７０から状態番号２８のノードと状態番号２７０のノードへの遷移）では（ｂ）の形の遷移が、状態（２９、２８５）から状態（５８、５９）への遷移では（ｃ）の形の遷移が生じ、状態（１４２、３９８）から状態（２８４、２８５）への遷移および状態（２８、２８４）から状態（５６、５７）への遷移では、夫々（ｄ）、（ｅ）の形の遷移が生じたとすると、（ｇ）から分かるように、始点１４２からのパスは終点５６、５７、５８の３状態に分岐し、始点２７０からのパスは終点５９まで生残り、始点１４、３９８からのパスは途中で、他のパスにマージされている。
【００２４】
ＡＣＳ演算の動作原理から、ｔ_nの時点で始点１４が状態尤度が最も小さいと考えられる。さらにトレリスの時点を延ばしてｔ_n+K以上にすると、全ての状態（２^K-1個）がｔ_n時点の最尤状態から枝分かれしたパスの終点となる。すなわち、ｔ_n時点の最尤状態以外の状態では途中のＡＣＳ処理によって全てパスが途絶えてしまう結果となり、ＡＣＳ演算は不要であったことになる。
【００２５】
以上の検討は理想状態すなわち、伝送路で雑音の混入が無い場合であるが、雑音のある実際の伝送系であっても、トレリスの時点をさらに延ばしていけば（拘束長の５〜６倍の長さで実用上十分であると言われている）、最尤パスは一本にマージすることが知られている。すなわち、生残りパスは状態尤度の小さい状態から枝分かれしており、状態尤度の（ある程度以上）大きい状態から伸びるパスは途中で途絶えてしまう。このことから、状態尤度がある設定値より小さい状態を含む状態遷移についてのみ通常のＡＣＳ演算処理を行えば良いことが分かる。状態尤度が設定値より大きい状態間での状態遷移については、通常のＡＣＳ演算処理を行わず、（いずれ他のパスにマージしてしまうので）終点状態の状態尤度を設定値（より若干大きい値）にしておく事で、ＡＣＳ演算処理の大幅な縮減が可能であり、且つ性能劣化も少ない。以上を基に、本発明は下記の通りである。
【００２６】
本発明は、Ｋビットの情報をｎビット（ｎ＞ｋ）の符号に符号化した符号化率ｒ＝ｋ／ｎで拘束長ｋの畳み込み符号を入力し、該入力した畳込み符号を最尤復号するヴィタビ復号器において、該ヴィタビ復号器の状態尤度演算処理を２^K-1個の状態の中から予め定めた値Ｍｓ０より小さい状態尤度を持つ状態を始点に含む状態遷移について、状態尤度演算処理をし、Ｍｓ０より小さい状態尤度を持つ状態を始点に含まない状態遷移については、予め定めた値Ｍｓ１を遷移後の状態尤度として与えるようにすることを特徴とするヴィタビ復号器である。
【００２７】
本発明は、ｋビットの情報をｎビット（ｎ＞ｋ）の符号に符号化した符号化率ｒ＝ｋ／ｎで拘束長ｋの畳み込み符号を入力し、該入力した畳込み符号を最尤復号するヴィタビ復号器において、該ヴィタビ復号器の状態尤度演算処理を２^K-1個の状態の中から状態尤度の小さい順にみて予め定めたＭ２番目（Ｍ２は２^K-1より小さい正整数）の状態尤度Ｍｓ２より小さい状態尤度をもつ状態を始点に含む状態遷移について、状態尤度演算処理をし、Ｍｓ２より小さい状態尤度を持つ状態を始点に含まない状態遷移については、予め定めた値Ｍｓ３を遷移後の状態尤度として与えるようにすることを特徴とするヴィタビ復号器である。
【００２８】
本発明は、ｋビットの情報をｎビット（ｎ＞ｋ）の符号に符号化した符号化率ｒ＝ｋ／ｎで拘束長ｋの畳み込み符号を入力し、該入力した畳込み符号を最尤復号するヴィタビ復号器において、該ヴィタビ復号器の状態尤度演算処理を２^K-1個の状態の中から予め定めた値Ｍｓ０より小さい状態尤度を持つＭ０個の状態と、２^K-1の状態の中から状態尤度の小さい順にみて予め定めたＭ２番目（Ｍ２は２^K-1より小さい正整数）の状態尤度Ｍｓ２より小さい状態尤度を持つＭ２個の状態との、いずれか少ない方の個数の状態を始点に含む状態遷移について、状態尤度演算処理をし、前記Ｍ０個あるいはＭ２個のいずれか個数の少ないほうの状態を始点に含まない状態遷移については、予め定めた値Ｍｓ４を遷移後の状態尤度として与えるようにすることを特徴とするヴィタビ復号器である。
【００２９】
【発明の実施の形態】
図１は、本発明によるヴィタビ復号器の第１の実施の形態の構成を示す図である。図１において、１は枝尤度計算部、２は状態尤度判定部、３はＡＣＳ部（ＡＣＳ：Add Compare Select、加算比較選択演算部）、４は状態尤度メモリ、５はパスメモリ、６は最尤復号部である。
【００３０】
図１においては、状態尤度判定部２を備え、図２の従来のヴィタビ復号器の状態尤度メモリ４の読出しデータバス側に状態尤度判定部２を挿入したもので、状態尤度判定部２以外の構成要素については、動作も従来のヴィタビ復号器とほぼ同様である。図１の第１の実施の形態では、状態尤度メモリ４から状態尤度を読出し、状態尤度判定部２で読み出した状態尤度の大きさによってＡＣＳ部３での演算処理の方法を変えることによって、ＡＣＳ演算処理の演算量を削減する。
【００３１】
図５は図１の動作を説明する図である。図５において、４は図１の符号４と同じ状態尤度メモリ、２は図１の符号２と同じ状態尤度判定部である。図１のヴィタビ復号器のＡＣＳ演算部３では、図４の（ａ）で示す基本トレリスにおけるＡＣＳ演算処理を行うため、基本トレリスの番号ｍ＝０〜２^K-2-１（図５ではＢ＝２^K-2と置く）をアドレスとして、状態尤度メモリ４から、状態ｍおよびＢ＋ｍの状態尤度Ｍｓ（ｍ）、Ｍｓ（Ｂ＋Ｍ）を読み出す。
【００３２】
次に読み出した状態尤度を、状態尤度判定部2に入力し、予め定めた尤度判定値Ｍｓ０と比較し、状態尤度Ｍｓ（ｍ）、Ｍｓ（Ｂ＋ｍ）の何れか一方が予め定めたＭｓ０より小さいかどうかを判定し、ＡＣＳ部３では、予め定めたＭｓ０より小さい状態尤度を持つ状態を始点に含む状態遷移について、状態尤度演算処理すなわち通常のACS演算処理を行う。これは基本トレリスの始点の状態尤度が小さいので、生残る可能性が高いからである。
【００３３】
それに対して、Ｍｓ０より小さい状態尤度を持つ状態を始点に含まない状態遷移については、予め定めた値ＭＳ１（＞Ｍｓ０）を遷移後の状態尤度として与えるよう状態尤度演算処理をする。
【００３４】
このように処理を行なうことにより、生き残る可能性の低い（尤度の大きい状態）に対するＡＣＳ演算処理を大幅に簡略化でき、ヴィタビ復号器の演算処理量を小さく且つ性能劣化も少なくすることが出来る。従って、拘束長Ｋの大きい符号に対するヴィタビ復号器も実現が可能となる。
【００３５】
第１の実施の形態では、ＡＣＳ演算処理を行う状態尤度の値を決めているので、伝送路の状況により復号器の受信系列に混入する符号誤りの割合が変動するような場合には、ＡＣＳ演算処理を行う状態の数が時間的に変動する。このような場合には復号結果の得られる時間（復号処理遅延時間）が変動することになり、復号器の適用分野によっては、好ましくない場合がある。
【００３６】
そこで、伝送路の符号誤り状況が変動しても復号処理遅延時間が変動しないようにした、本発明による第２の実施の形態を次に説明する。
【００３７】
図６は、本発明によるヴィタビ復号器の第２の実施の形態の構成図である。図６において、１は枝尤度計算部、２は状態尤度判定部、３はＡＣＳ部、４は状態尤度メモリ、５はパスメモリ、６は最尤復号部、６０は状態尤度カウンタである。
【００３８】
図６においては、図１の本発明によるヴィタビ復号器の第１の実施の形態に、状態尤度カウンタ６０を設けたものであり、状態尤度カウンタ６０以外の構成は、図１の本発明の第１の実施の形態と同様である。状態尤度カウンタ６０は、ＡＣＳ部３が基本トレリスの終点状態の状態尤度を求める度に、その状態尤度の状態の個数をカウントする。ＡＣＳ演算処理が終わった時点で、状態尤度の小さい順にカウント値を積算し、予め定めた既定の状態数Ｍ２になる状態尤度値Ｍｓ２より小さい状態尤度を持つ状態を始点に含む状態遷移について、状態尤度演算処理をし、Ｍｓ２より小さい状態尤度を持つ状態を始点を含まない状態遷移については、あらかじめ定めた値Ｍｓ３を遷移後の状態尤度として与えるよう状態尤度演算処理をする。
【００３９】
第２の実施の形態では、ＡＣＳ演算処理を行なう状態の数が既定状態数Ｍ２により制限されるので、伝送路での符号誤りの状況によらずＡＣＳ演算に要する処理時間は一定値以下となり、復号時間も一定値以下に保たれる。
【００４０】
次に、本発明によるヴィタビ復号器の第３の実施の形態について、説明する。本発明によるヴィタビ復号器の第３の実施の形態の構成自体は、図６の第２の実施の形態と同じであり、動作を異にしている。
【００４１】
この第３の実施の形態では、図１で説明した予め定めた値Ｍｓ０より小さい状態尤度を持つＭ０個の状態と、図５で説明した状態尤度の小さい順にみて予め定めたＭ２番目の状態尤度Ｍｓ２より小さい状態尤度を持つＭ２個の状態との、いずれか個数の少ないほうの状態を選択し、選択した状態を始点に含む状態遷移について状態尤度演算処理をし、選択した状態を含まない状態遷移については、予め定めた値Ｍｓ４を遷移後の状態尤度として与えるよう状態尤度演算処理をする。
【００４２】
第３の実施の形態では、更に優れたヴィタビ復号器を提供することが出来る。
【００４３】
以上説明したように、本発明のヴィタビ復号器は、状態尤度が大きく生残る可能性の低い状態に対するＡＣＳ演算処理を省略し、ヴィタビ復号器を構成する上で最も処理量の大きいＡＣＳ演算時間を短縮するので、ヴィタビ復号器の高速化が可能であり、拘束長の大きい畳み込み符号に対するヴィタビ復号器も実現が容易になる。
【００４４】
【発明の効果】
本発明によれば、ＡＣＳ演算処理すなわち状態尤度演算処理を、従来よりも少ない処理量で実現し且つ性能劣化の少ないヴィタビ復号器を提供することが出来る。
【図面の簡単な説明】
【図１】本発明によるヴィタビ復号器の第１の実施の形態の構成図である。
【図２】従来のヴィタビ復号器の構成図である。
【図３】畳み込み符号器の構成と、符号器の状態遷移の状況を図に表したトレリス線図である。
【図４】トレリス遷移と生残りパスを示す図である。
【図５】図１の動作を説明する図である。
【図６】本発明によるヴィタビ復号器の第２の実施の形態、第３の実施の形態に共通の構成図である。
【符号の説明】
１…枝尤度計算部、２…状態尤度判定部、３…ＡＣＳ部、４…状態尤度メモリ、５…パスメモリ、６…最尤復号部、３１、３２、３３、３４、３５…排他論理和ゲート、３６、３７、３８…１ビット遅延素子、６０…状態尤度カウンタ。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an error correction code decoder, and more particularly to a Viterbi decoder that performs maximum likelihood decoding of a convolutional code.
[0002]
[Prior art]
In order to improve the reliability of data transmission, an error correction technique for correcting a code error of transmission data generated during transmission on the receiving side is used in various fields. Among them, a Viterbi decoder capable of maximum likelihood decoding a convolutional code is known for its large error correction capability.
[0003]
FIG. 2 is a configuration diagram of a conventional Viterbi decoder. In FIG. 2, 1 is a branch likelihood calculation unit, 3 is an ACS unit (ACS: Add Compare Select), 4 is a state likelihood memory, 5 is a path memory, and 6 is a maximum likelihood decoding unit. .
[0004]
Prior to the description of the operation of the conventional Viterbi decoder shown in FIG. 2, a convolutional encoder serving as an encoder on the transmission side that plays an important role in maximum likelihood decoding will be described.
[0005]
FIG. 3 is a trellis diagram illustrating the configuration of the convolutional encoder and the state transition state of the encoder. FIG. 3A shows the configuration of a convolutional encoder, which includes a shift register including exclusive OR gates 31, 32, 33, 34, and 35 and 1-bit delay elements 36, 37, and 38. Input data x ₀ is inputted to the 1-bit delay element 36, 37 and 38 to obtain a delayed data _{x 1, x 2, x 3} . Also, the exclusive OR gates 31, 32, 33, 34, and 35 take the exclusive OR of the data x ₀ , x ₁ , x ₂ , and x ₃ to generate encoded outputs g ₀ and g ₁ , and encode them. Outputs g ₀ and g ₁ are transmitted.
[0006]
Here, since the convolutional encoder shown in FIG. 3A outputs 2 bits for 1 bit of input data, the coding rate r = 1/2, and 1 is set for the number 3 of delay elements. Since the code is generated with the added 4 bits of input data, it is called a convolutional encoder with a constraint length K = 4. Further, the state x ₃ x ₂ x ₁ of the 3-bit data held in the shift registers 36, 37, and 38 of the convolutional encoder is referred to as an encoder state. Since there are 3 bits here, there are 8 states from 000 to 111, and encoding is performed while the 8 states transition each time input data is input. A diagram representing the state of this state transition is called a trellis diagram.
[0007]
FIG. 3B is an 8-state trellis diagram showing a transition state from time t _{n −1} to time t _n . In the state of state number x ₃ x ₂ x ₁ at time t _n−1 , x ₀ is input to the convolutional encoder, and at the same time, x ₃ is extracted from the convolutional encoder and output, and state number x ₂ x at time t _n is output. It moves to the state of ₁ x _0. Here, if m = x ₂ x ₁ (= 0 to 3), 2m (x ₀ = 0) and 2m + 1 (x ₀ = x) from the state of m (x ₃ = 0) and m + 4 (x ₃ = 1). Transition to the state of 1) having a transition branch. That is, considering two time points, time point t _n-1 and time point t _n , (b) 8-state trellis is a combination of four (c) basic unit trellises (m = 0-3). It is.
[0008]
The encoded outputs g ₀ and g ₁ shown in FIGS. 3A and 3C are code generator polynomials.
[Expression 1]

Calculated by However, the addition in equation (1) is performed by exclusive OR. Further, x ^T denotes the transposed vector of x. Therefore, the codes g ₀ and g ₁ output in accordance with the state transition of (c) in FIG. 3 are expressed as x ₃ m and mx ₀ (m = x ₂ x in (c) of FIG. ₁ )
[0010]
[Expression 2]

It becomes. However, in the formula (2), x ′ represents logical inversion of x.
[0011]
As described above, the trellis structure of the convolutional code (the state number before and after the transition and the code to be output) is uniquely determined when the state number m = 0 to 2 ^K−2 −1 is given.
[0012]
Therefore, in the maximum likelihood decoder on the receiving side, transition paths (eight in the example of FIG. 3B) reaching all the states at time t _n are held as candidate paths, and the received code r _{0 is} stored. , R ₁ is used as a clue to select the most probable transition path as the state transition of the encoder on the transmission side (maximum likelihood selection), and decoding is performed while estimating the state transition of the encoder. Here, the likelihood is used as a quantity that specifically represents the certainty. The Hamming distance (geometric distance) between the codes g ₀ and g ₁ output along with the state transition from the state number m to m ′ and the actually received codes r ₀ and r ₁ is expressed as the transition branch. Let branch likelihood (branch metric). The received codes r ₀ and r ₁ identify the received signals y ₀ and y _1, and r = 0 when y> 0 and r = 1 when y <0. The likelihood obtained from such a decoded value determined as 0 or 1 is referred to as a hard decision likelihood.
[0013]
For the branch likelihood, the codes (g ₀ , g ₁ ) = (0, 0), (0, 1), (1, 0), (1, 1) associated with the state transition are represented by orthogonal signal point coordinates (I , Q) = (1,1), (−1,1), (1, −1), (−1, −1), the orthogonal signal point (I, Q) and the received signal point (y ₀ , There is also a calculation method called soft decision likelihood that gives the Euclidean distance to y ₁ ) or the absolute value sum of the difference between the quadrature and in-phase components as the likelihood.
[0014]
The description on the transmission side is finished, and then the decoding on the reception side will be described.
[0015]
FIG. 2 is a configuration diagram of a conventional Viterbi decoder. The branch likelihood calculation unit 1 calculates and obtains branch likelihoods of all transition branches every time a received code is input. Then, the state likelihood is calculated by the ACS unit 3 using the obtained branch likelihood. The state likelihood is the sum of all branch likelihoods of transition paths leading to each state. Actually, as shown in the trellis diagram of FIG. 3B, there are two transition branches in each state, so the branch likelihood of each transition branch is the state one point before the point in time. A new state likelihood is obtained by adding to the likelihood (Add), the state likelihoods of the two state transitions up to the present time are compared (Compare), and the most probable transition branch is selected as the transition path (Select). Moreover, since the branch likelihood is actually represented by the Hamming distance, it is likely that the state likelihood is smaller (the likelihood is higher).
[0016]
The state likelihood calculated by the ACS unit 3 is stored in the state likelihood memory 4, and the transition information of the transition path selected by the ACS operation (ACS: Add Compare Select) is sent to the path memory 5. The path memory 5 stores all the selected transition information sequentially. When the data input is completed, the transition path that reaches the state with the highest state likelihood (the smallest numerical value) is estimated as the transition path of the encoder, and the transition information of the estimated transition path is the maximum likelihood decoding unit. 6 performs maximum likelihood decoding and outputs.
[0017]
As described above, in the maximum likelihood decoding method using the maximum likelihood decoding, the received data is not immediately decoded, but the accuracy of information is held in the path memory 5 in the form of state likelihood, and a plurality of transmission symbols are covered. Since the decoding is performed for the transition path, it is possible to reduce the error by reducing the influence of the noise component mixed for each symbol of the received signal.
[0018]
An example of this type of Viterbi decoder is disclosed in JP-A-5-315976.
[0019]
[Problems to be solved by the invention]
In the Viterbi decoder, the error correction capability increases and the code error rate improves as the constrained code constraint length K increases. Therefore, especially with the advancement of IC technology, codes with a large constraint length are used. However, the processing amount of a series of operations (branch likelihood calculation, state likelihood calculation, ACS operation, state likelihood memory capacity, path memory capacity) in the Viterbi decoder is proportional to the number of states 2 ^K−1 . Therefore, it can be executed relatively easily when the constraint length K is small. However, when the constraint length K is large, there is a problem that the amount of calculation processing increases exponentially and the processing time becomes long and difficult to realize.
[0020]
An object of the present invention is to provide a Viterbi decoder that realizes ACS processing, that is, state likelihood calculation processing with a smaller calculation processing amount than the conventional one, and has less performance degradation.
[0021]
[Means for Solving the Problems]
In order to achieve the above object, the present invention determines the state likelihood before entering the ACS operation process of the Viterbi decoder, and performs normal operations only for state transitions including states where the state likelihood is smaller than a set value. This is because ACS operation processing is performed. The reason why such processing is possible will be described with reference to FIG.
[0022]
FIG. 4 is a diagram illustrating trellis transitions and survival paths. FIG. 4 (a) is a trellis basic trellis of a convolutional code trellis with a coding rate r = 1/2 and a constraint length K. The state numbers m, 2 ^K−2 + m are the starting points, and the states 2m, 2m + 1 are shown. The basic trellis that is the end point. Coding rate r = 1/2, the trellis of convolutional code with a constraint length K is for this basic trellis gathered 2 ^K-2 pieces ^{(m = 0~2 K-2 -1} ).
[0023]
When the ACS calculation process is performed in the basic trellis state of FIG. 4A, trellis transitions as shown in FIGS. 4B to 4E are obtained as a result. That is, (b) and (c) are the cases where the paths from the two states at the starting point are both survived and the paths are temporarily extended, and (d) and (e) are the cases where one of the paths remains and the end point This is a case of branching into two states. In the latter case, the path that did not survive was merged into the surviving path. When the time point of the trellis diagram is further extended, a trellis diagram between four states as shown in (f) is obtained. The starting point of the 4-state trellis is (m, 2 ^K−3 + m, 2 ^k−2 + m, 3 · 2 ^K−3 + m) 4 states, and the end point is (4m, 4m + 1, 4m + 2, 4m + 3) 4 states (m = 0-2K ^- 3-1).
An example of a trellis diagram in the case where ACS calculation processing is performed in the four-state trellis is shown in (g). In (g), as an example, a case where the constraint length K = 10 (number of states 2 ^K−1 = 512) and the state number m = 14 is shown. The numbers attached to the nodes of the trellis diagram indicate the state numbers at that time. In the transition from the state (14, 270) to the state (28, 29) (that is, the transition from the node of the state number 14 and the state number 270 to the node of the state number 28 and the node of the state number 270), the form (b) In the transition from state (29, 285) to state (58, 59), a transition of the form (c) occurs, and the transition from state (142, 398) to state (284, 285) and state ( 28, 284) to the state (56, 57), if transitions of the form (d) and (e) occur, the path from the start point 142 is the end point 56, as can be seen from (g). Branching into three states 57 and 58, the path from the start point 270 survives to the end point 59, and the paths from the start points 14 and 398 are merged with other paths on the way.
[0024]
From the principle of operation of the ACS calculation, it is considered that the starting point 14 has the smallest state likelihood at the time point t _n . If the trellis time is further extended to t _{n + K} or more, all states (2 ^K-1 ) become the end points of the paths branched from the maximum likelihood state at the time t _n . That is, in a state other than the maximum likelihood state at the time point t _n , all the paths are interrupted by the intermediate ACS process, and the ACS calculation is unnecessary.
[0025]
The above examination is an ideal state, that is, a case where no noise is mixed in the transmission line, but even in an actual transmission system with noise, if the time of the trellis is further extended (5 to 6 times the constraint length). It is known that the maximum likelihood paths are merged into one. In other words, the surviving path branches off from a state with a small state likelihood, and a path extending from a state with a large state likelihood (a certain degree or more) is interrupted on the way. From this, it can be seen that the normal ACS calculation process should be performed only for the state transition including the state likelihood having a state smaller than a certain set value. For state transitions between states whose state likelihood is larger than the set value, the normal ACS calculation processing is not performed, and the state likelihood of the end point state is set to the set value (slightly more). By setting it to a large value, it is possible to greatly reduce the ACS arithmetic processing and there is little performance degradation. Based on the above, the present invention is as follows.
[0026]
The present invention inputs a convolutional code having a constraint length k at a coding rate r = k / n obtained by encoding K-bit information into an n-bit (n> k) code, and the input convolutional code is the maximum likelihood. In the Viterbi decoder for decoding, the state likelihood calculation process of the Viterbi decoder is performed for a state transition including a state having a state likelihood smaller than a predetermined value Ms0 from 2 ^K−1 states as a starting point. Viterbi decoding characterized by performing likelihood calculation processing and giving a predetermined value Ms1 as a state likelihood after the transition for a state transition that does not include a state having a state likelihood smaller than Ms0 as a starting point It is a vessel.
[0027]
The present invention inputs a convolutional code having a constraint length k at a coding rate r = k / n obtained by encoding k-bit information into an n-bit (n> k) code, and the inputted convolutional code is the maximum likelihood. In the Viterbi decoder for decoding, the state likelihood calculation processing of the Viterbi decoder is determined in advance from the 2 ^K−1 states in ascending order of the state likelihood (M2 is a positive value smaller than 2 ^K−1). (Integer) for state transitions having a state likelihood smaller than state likelihood Ms2 at the start point, state likelihood calculation processing is performed, and for state transitions that do not include a state having state likelihood smaller than Ms2 at the start point, The Viterbi decoder is characterized in that a predetermined value Ms3 is given as a state likelihood after transition.
[0028]
The present invention inputs a convolutional code having a constraint length k at a coding rate r = k / n obtained by encoding k-bit information into an n-bit (n> k) code, and the inputted convolutional code is the maximum likelihood. in the decoding to Viterbi decoder, and M0 or condition with a predetermined value Ms0 smaller state likelihoods from the state likelihood computation processing 2 ^K-1 pieces of state of the Viterbi decoder, 2 ^K-1 Any of the M2 states having a state likelihood smaller than the M2 (M2 is a positive integer smaller than 2 ^K-1 ) state likelihood Ms2 determined in the order of decreasing state likelihood. State likelihood calculation processing is performed for state transitions that include the smaller number of states at the start point, and state transitions that do not include the smaller number of M0 or M2 states at the start point are determined in advance. Give value Ms4 as state likelihood after transition A Viterbi decoder characterized and.
[0029]
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 is a diagram showing a configuration of a first embodiment of a Viterbi decoder according to the present invention. In FIG. 1, 1 is a branch likelihood calculating unit, 2 is a state likelihood determining unit, 3 is an ACS unit (ACS: Add Compare Select), 4 is a state likelihood memory, 5 is a path memory, Reference numeral 6 denotes a maximum likelihood decoding unit.
[0030]
In FIG. 1, a state likelihood determining unit 2 is provided, and the state likelihood determining unit 2 is inserted on the read data bus side of the state likelihood memory 4 of the conventional Viterbi decoder of FIG. Regarding the components other than the unit 2, the operation is almost the same as that of the conventional Viterbi decoder. In the first embodiment of FIG. 1, the state likelihood is read from the state likelihood memory 4, and the calculation processing method in the ACS unit 3 is changed depending on the state likelihood read by the state likelihood determining unit 2. As a result, the calculation amount of the ACS calculation process is reduced.
[0031]
FIG. 5 is a diagram for explaining the operation of FIG. In FIG. 5, 4 is the same state likelihood memory as reference numeral 4 in FIG. 1, and 2 is the same state likelihood determination unit as reference numeral 2 in FIG. The ACS operation unit 3 of the Viterbi decoder of FIG. 1 performs the ACS operation process in the basic trellis shown in FIG. 4A, so that the basic trellis number m = 0 to 2 ^K− 2−1 (B in FIG. 5). = 2 place the ^K-2) as addresses, from the state likelihood memory 4, state m and B + m state likelihood Ms (m), reads the Ms (B + M).
[0032]
Next, the read state likelihood is input to the state likelihood determination unit 2 and compared with a predetermined likelihood determination value Ms0, and one of the state likelihoods Ms (m) and Ms (B + m) is determined in advance. The ACS unit 3 performs state likelihood calculation processing, that is, normal ACS calculation processing for a state transition including a state having a state likelihood smaller than Ms0 as a starting point. This is because the state likelihood at the starting point of the basic trellis is small, and the possibility of survival is high.
[0033]
On the other hand, for state transitions that do not include a state having a state likelihood smaller than Ms0 as a starting point, state likelihood calculation processing is performed to give a predetermined value MS1 (> Ms0) as the state likelihood after the transition.
[0034]
By performing the processing in this way, it is possible to greatly simplify the ACS arithmetic processing for a low possibility of survival (high likelihood state), and to reduce the arithmetic processing amount of the Viterbi decoder and reduce performance degradation. . Therefore, a Viterbi decoder for a code having a large constraint length K can also be realized.
[0035]
In the first embodiment, the state likelihood value for performing the ACS calculation process is determined. Therefore, when the ratio of code errors mixed in the received sequence of the decoder varies depending on the state of the transmission path, The number of states in which the ACS calculation process is performed varies with time. In such a case, the time for which the decoding result is obtained (decoding processing delay time) fluctuates, which may not be preferable depending on the application field of the decoder.
[0036]
Therefore, a second embodiment according to the present invention in which the decoding processing delay time does not vary even when the code error situation of the transmission path varies will be described below.
[0037]
FIG. 6 is a block diagram of a second embodiment of the Viterbi decoder according to the present invention. In FIG. 6, 1 is a branch likelihood calculating unit, 2 is a state likelihood determining unit, 3 is an ACS unit, 4 is a state likelihood memory, 5 is a path memory, 6 is a maximum likelihood decoding unit, and 60 is a state likelihood counter. It is.
[0038]
In FIG. 6, a state likelihood counter 60 is provided in the first embodiment of the Viterbi decoder according to the present invention of FIG. 1, and the configuration other than the state likelihood counter 60 is the same as that of the present invention of FIG. This is the same as the first embodiment. The state likelihood counter 60 counts the number of states of the state likelihood each time the ACS unit 3 calculates the state likelihood of the end state of the basic trellis. State transition including a state having a state likelihood smaller than the state likelihood value Ms2 at which the count value is accumulated in order of increasing state likelihood and having a predetermined state number M2 at the start point when the ACS calculation process is completed For state transitions that do not include a starting point, a state likelihood calculation process is performed so that a predetermined value Ms3 is given as a state likelihood after the transition. To do.
[0039]
In the second embodiment, since the number of states in which the ACS calculation process is performed is limited by the predetermined number of states M2, the processing time required for the ACS calculation is equal to or less than a predetermined value regardless of the state of the code error in the transmission path. The decoding time is also kept below a certain value.
[0040]
Next, a third embodiment of the Viterbi decoder according to the present invention will be described. The configuration itself of the third embodiment of the Viterbi decoder according to the present invention is the same as that of the second embodiment of FIG. 6, and the operation is different.
[0041]
In the third embodiment, M0th states having a state likelihood smaller than the predetermined value Ms0 described with reference to FIG. 1 and the M2th state determined in advance in ascending order of the state likelihood described with reference to FIG. The state with the state likelihood smaller than the state likelihood Ms2 is selected, and the state with the smaller number is selected, and state likelihood calculation processing is performed on the state transition including the selected state as the start point. For state transitions that do not include a state, state likelihood calculation processing is performed to give a predetermined value Ms4 as the state likelihood after the transition.
[0042]
In the third embodiment, a more excellent Viterbi decoder can be provided.
[0043]
As described above, the Viterbi decoder of the present invention omits the ACS calculation processing for a state with a large state likelihood and is unlikely to survive, and has the ACS processing time with the largest processing amount in configuring the Viterbi decoder. Therefore, the Viterbi decoder can be speeded up, and the Viterbi decoder for a convolutional code having a large constraint length can be easily realized.
[0044]
【The invention's effect】
According to the present invention, it is possible to provide a Viterbi decoder that realizes ACS calculation processing, that is, state likelihood calculation processing, with a smaller processing amount than that of the prior art and with less performance degradation.
[Brief description of the drawings]
FIG. 1 is a configuration diagram of a first embodiment of a Viterbi decoder according to the present invention;
FIG. 2 is a configuration diagram of a conventional Viterbi decoder.
FIG. 3 is a trellis diagram illustrating the configuration of a convolutional encoder and the state transition state of the encoder.
FIG. 4 is a diagram showing trellis transitions and surviving paths.
FIG. 5 is a diagram for explaining the operation of FIG. 1;
FIG. 6 is a configuration diagram common to the second and third embodiments of a Viterbi decoder according to the present invention.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 ... Branch likelihood calculation part, 2 ... State likelihood determination part, 3 ... ACS part, 4 ... State likelihood memory, 5 ... Path memory, 6 ... Maximum likelihood decoding part, 31, 32, 33, 34, 35 ... Exclusive OR gate, 36, 37, 38... 1 bit delay element, 60... State likelihood counter.

Claims (3)

A Viterbi decoder that inputs a convolutional code having a constraint length k at a coding rate r = k / n obtained by encoding K-bit information into an n-bit (n> k) code, and performs maximum likelihood decoding on the input convolutional code In the state likelihood calculation process of the Viterbi decoder, the state likelihood calculation process is performed for a state transition including a state having a state likelihood smaller than a predetermined value MsO as a starting point from 2 ^K-1 states. A Viterbi decoder characterized by giving a predetermined value Ms1 as a state likelihood after the transition for a state transition that does not include a state having a state likelihood smaller than the predetermined value MsO as a starting point. . A Viterbi decoder for inputting a convolutional code having a constraint length k at a coding rate r = k / n obtained by encoding k-bit information into an n-bit (n> k) code, and performing maximum likelihood decoding on the input convolutional code , The state likelihood calculation process of the Viterbi decoder is preliminarily determined from the 2 ^K-1 states in ascending order of the state likelihood (M2 is a positive integer smaller than 2 ^K-1 ). The state likelihood calculation process is performed for a state transition including a state having a state likelihood smaller than the degree Ms2, and the state transition not including a state having a state likelihood smaller than the state likelihood Ms2 is determined in advance. A Viterbi decoder characterized in that a predetermined value Ms3 is given as a state likelihood after transition. A Viterbi decoder for inputting a convolutional code having a constraint length k at a coding rate r = k / n obtained by encoding k-bit information into an n-bit (n> k) code, and performing maximum likelihood decoding on the input convolutional code in the M0 amino state having a predetermined value Ms0 smaller state likelihoods from the state likelihood computation processing 2 ^K-1 pieces of state of the Viterbi decoder, from among the 2 ^K-1 states The smaller of the number M2, which has a state likelihood smaller than the M2 (M2 is a positive integer smaller than 2 ^K-1 ) state likelihood Ms2, which is determined in order of increasing state likelihood. The state likelihood calculation process is performed on the state transition including the state at the starting point, and the state transition not including the smaller number of the M0 or M2 state at the starting point is changed to a predetermined value Ms4. Is given as the state likelihood of Viterbi decoder to.

Images