JPH0951278A - ビタビ復号器 - Google Patents
ビタビ復号器Info
- Publication number
- JPH0951278A JPH0951278A JP20241895A JP20241895A JPH0951278A JP H0951278 A JPH0951278 A JP H0951278A JP 20241895 A JP20241895 A JP 20241895A JP 20241895 A JP20241895 A JP 20241895A JP H0951278 A JPH0951278 A JP H0951278A
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- path
- traceback
- memory
- output
- 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)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】
【課題】 高速復号性能を保持しつつ、パスメモリの回
路規模を縮小し、半導体集積回路化が容易なビタビ復号
器を提供する。 【解決手段】 パス選択信号を複数ステップ分保持する
メモリ回路２１ａ〜ｄと、最尤パス選択信号に基づいて
前記メモリ回路の記憶内容をトレースバックするトレー
スバック回路２２ａ〜ｄと、トレースバック回路の出力
を所定の順序に並べ替える出力バッファ回路２４ａ〜ｄ
と、トレースバック制御回路２５とによりビタビ復号器
のパスメモリ回路を構成する。トレースバック制御回路
２５は、メモリ回路２１とトレースバック回路２２と出
力バッファ回路２４とからなる互いに独立に動作可能な
複数組ａ〜ｄを、パスメモリ更新動作と、トレースバッ
ク動作と、出力動作とを各組ａ〜ｄ間で位相をずらして
交互に動作せしめる。
路規模を縮小し、半導体集積回路化が容易なビタビ復号
器を提供する。 【解決手段】 パス選択信号を複数ステップ分保持する
メモリ回路２１ａ〜ｄと、最尤パス選択信号に基づいて
前記メモリ回路の記憶内容をトレースバックするトレー
スバック回路２２ａ〜ｄと、トレースバック回路の出力
を所定の順序に並べ替える出力バッファ回路２４ａ〜ｄ
と、トレースバック制御回路２５とによりビタビ復号器
のパスメモリ回路を構成する。トレースバック制御回路
２５は、メモリ回路２１とトレースバック回路２２と出
力バッファ回路２４とからなる互いに独立に動作可能な
複数組ａ〜ｄを、パスメモリ更新動作と、トレースバッ
ク動作と、出力動作とを各組ａ〜ｄ間で位相をずらして
交互に動作せしめる。
Description
【０００１】
【発明の属する技術分野】本発明は、たたみ込み符号の
最尤復号を効率的に実現するビタビ復号器に係り、さら
に詳しくは、そのパスメモリの回路規模を大幅に削減し
集積回路化に有利なビタビ復号器に関する。
最尤復号を効率的に実現するビタビ復号器に係り、さら
に詳しくは、そのパスメモリの回路規模を大幅に削減し
集積回路化に有利なビタビ復号器に関する。
【０００２】
【従来の技術】ビタビ復号法は、訂正能力の高い誤り訂
正法として、ディジタル伝送やディジタル記録の分野で
さかんに採用されている。そのアルゴリズムは、文献
[1] G.D.Forney,Jr.著、“The Viterbi Algorithm ”，
Proceedings of IEEE, Vol.61, No.3, pp.268-278, Ma
r.1973.に詳しく説明されている。
正法として、ディジタル伝送やディジタル記録の分野で
さかんに採用されている。そのアルゴリズムは、文献
[1] G.D.Forney,Jr.著、“The Viterbi Algorithm ”，
Proceedings of IEEE, Vol.61, No.3, pp.268-278, Ma
r.1973.に詳しく説明されている。
【０００３】パスメモリの構成を示す前に、たたみ込み
符号を復号するビタビ復号法の動作原理を要約してお
く。図３は、たたみ込み符号の符号器の構成例を示す。
説明の都合で入力側を右側にして示してある。右側の入
力端子から直列に入力される入力信号Ｓi は、順次６bi
t のシフトレジスタに取り込まれるとともに、排他的論
理和回路の出力Ｙ1，Ｙ2 がたたみ込み符号として左側
の出力端子へ出力される。この符号器の拘束長はＫ＝
７、符号化率はＲ＝１／２、状態数はＮs ＝６４であ
る。ビタビ復号の操作は、受信された符号に基づいて、
この符号器のレジスタの内容で決まる状態Ｓ＝｛Ｓ5 ，
Ｓ4 ，Ｓ3 ，Ｓ2 ，Ｓ1 ，Ｓ0 ｝の遷移を推定すること
と等価である。状態Ｓは、時刻ｔ−１で図３の状態であ
るとすると、次の時刻ｔには｛Ｓ4，Ｓ3 ，Ｓ2 ，
Ｓ1 ，Ｓ0 ，Ｓ-1｝になる。
符号を復号するビタビ復号法の動作原理を要約してお
く。図３は、たたみ込み符号の符号器の構成例を示す。
説明の都合で入力側を右側にして示してある。右側の入
力端子から直列に入力される入力信号Ｓi は、順次６bi
t のシフトレジスタに取り込まれるとともに、排他的論
理和回路の出力Ｙ1，Ｙ2 がたたみ込み符号として左側
の出力端子へ出力される。この符号器の拘束長はＫ＝
７、符号化率はＲ＝１／２、状態数はＮs ＝６４であ
る。ビタビ復号の操作は、受信された符号に基づいて、
この符号器のレジスタの内容で決まる状態Ｓ＝｛Ｓ5 ，
Ｓ4 ，Ｓ3 ，Ｓ2 ，Ｓ1 ，Ｓ0 ｝の遷移を推定すること
と等価である。状態Ｓは、時刻ｔ−１で図３の状態であ
るとすると、次の時刻ｔには｛Ｓ4，Ｓ3 ，Ｓ2 ，
Ｓ1 ，Ｓ0 ，Ｓ-1｝になる。
【０００４】図３の構成の符号器の場合、レジスタのシ
フトアウトビットとシフトインビットとに着目すれば、
レジスタの状態遷移はある状態の組と別の状態の組との
間で起こる。これを図４に示す。遷移先の状態の組を中
心に考えると、それぞれ６bit からなる６４通りの状態
Ｓを１０進数で表現し、奇数（ｍ）で現される状態と偶
数（ｎ）で現される状態で場合分けして、図４のように
遷移元（ｉあるいはｊ）と遷移先（ｍあるいはｎ）を関
係づけることができる。なお、以下の説明において、
“ｘ>>１”は、ｘをＬＳＢ側へ１bit シフトした数を示
し、“ｘ＾ｙ”は、ｘとｙとのビット毎の排他的論理和
演算の結果の数を示すものとする。
フトアウトビットとシフトインビットとに着目すれば、
レジスタの状態遷移はある状態の組と別の状態の組との
間で起こる。これを図４に示す。遷移先の状態の組を中
心に考えると、それぞれ６bit からなる６４通りの状態
Ｓを１０進数で表現し、奇数（ｍ）で現される状態と偶
数（ｎ）で現される状態で場合分けして、図４のように
遷移元（ｉあるいはｊ）と遷移先（ｍあるいはｎ）を関
係づけることができる。なお、以下の説明において、
“ｘ>>１”は、ｘをＬＳＢ側へ１bit シフトした数を示
し、“ｘ＾ｙ”は、ｘとｙとのビット毎の排他的論理和
演算の結果の数を示すものとする。
【０００５】ビタビ復号は復号パスの候補を、各状態に
対応したパスメトリックに基づいて逐次的に切り捨てて
いくことで、常に状態数（Ｎs ）分の復号パス（生き残
りパス）しか残さないようにする。こうすることで、効
率的な最尤復号を実現できるわけである。図５のように
各生き残りパスは、ある適当な長さ（Ｍs ）より過去に
相当するパスについて１本に合流する確率が高い。生き
残りパスのうち対応するパスメトリックが最小のパス
（最尤パス）を、Ｍs 段分さかのぼった遷移に対応する
情報ビットδ（ｔ−Ｍs ）がビタビ復号出力になる。
対応したパスメトリックに基づいて逐次的に切り捨てて
いくことで、常に状態数（Ｎs ）分の復号パス（生き残
りパス）しか残さないようにする。こうすることで、効
率的な最尤復号を実現できるわけである。図５のように
各生き残りパスは、ある適当な長さ（Ｍs ）より過去に
相当するパスについて１本に合流する確率が高い。生き
残りパスのうち対応するパスメトリックが最小のパス
（最尤パス）を、Ｍs 段分さかのぼった遷移に対応する
情報ビットδ（ｔ−Ｍs ）がビタビ復号出力になる。
【０００６】時刻がｔ−１からｔに移るときの遷移先の
状態ｎ，ｍのパスメトリックΓt (n ) ，Γt (m) の更新
は、図４の状態遷移の組で以下の式（１）及び（２）の
ようにして行われる。
状態ｎ，ｍのパスメトリックΓt (n ) ，Γt (m) の更新
は、図４の状態遷移の組で以下の式（１）及び（２）の
ようにして行われる。
【０００７】
【数１】 Γt (n) ＝min{Γt-1 (i) ＋λt （ν），Γt-1 (j) ＋λt （ν')｝…(1) Γt (m) ＝min{Γt-1 (i) ＋λt （ν')，Γt-1 (j) ＋λt （ν）｝…(2) ここでνとν’はブランチコードと呼び、状態（ｉ），
（ｊ）から（ｍ），（ｎ）へ遷移するときのそれぞれの
符号化ビット（Ｙ1 Ｙ0 ）に相当し、ν’＝ν＾(11)で
ある。ブランチメトリックλ（ν）及びλ（ν’）は、
各ブランチコードに対応した（デパンクチャ後の）復調
データの誤差（距離）に相当し、各復号ステップごとに
４つ発生される。例えば３bit で表現する場合は０〜７
の値をとる。各状態遷移の組（Ｎs ／２＝３２組ある）
では、λ(00)とλ(11)か、あるいはλ(01)とλ(10)のい
ずれかの組を用いてパスメトリックを計算する。
（ｊ）から（ｍ），（ｎ）へ遷移するときのそれぞれの
符号化ビット（Ｙ1 Ｙ0 ）に相当し、ν’＝ν＾(11)で
ある。ブランチメトリックλ（ν）及びλ（ν’）は、
各ブランチコードに対応した（デパンクチャ後の）復調
データの誤差（距離）に相当し、各復号ステップごとに
４つ発生される。例えば３bit で表現する場合は０〜７
の値をとる。各状態遷移の組（Ｎs ／２＝３２組ある）
では、λ(00)とλ(11)か、あるいはλ(01)とλ(10)のい
ずれかの組を用いてパスメトリックを計算する。
【０００８】また、パスメトリックの計算と同時に、い
ずれの状態から状態ｎ，ｍへ遷移したかを示す選択フラ
グβt (n) ，βt (m) を例えば以下の式（３）及び
（４）に示す条件で発生する。
ずれの状態から状態ｎ，ｍへ遷移したかを示す選択フラ
グβt (n) ，βt (m) を例えば以下の式（３）及び
（４）に示す条件で発生する。
【０００９】
【数２】 Γt-1 (i) ＋λt （ν）＜Γt-1 (j) ＋λt （ν’）のとき βt (n) ＝０， Γt-1 (i) ＋λt （ν）≧Γt-1 (j) ＋λt （ν’）のとき βt (n) ＝１ …(3) Γt-1 (i) ＋λt （ν’）＜Γt-1 (j) ＋λt （ν）のとき βt (m) ＝０， Γt-1 (i) ＋λt （ν’）≧Γt-1 (j) ＋λt （ν）のとき βt (m) ＝１ …(4) これらは、後述の生き残りパスの更新等で用いる。式
(1) 〜(4) までの演算は、加算比較選択ユニット（以
下、ＡＣＳＵと省略する）で実行される。その回路構成
を図６に示す。
(1) 〜(4) までの演算は、加算比較選択ユニット（以
下、ＡＣＳＵと省略する）で実行される。その回路構成
を図６に示す。
【００１０】各選択フラグに基づき、それぞれの状態で
残す復号パスの候補（生き残りパス）を以下に示す式
（５）及び（６）のようにして更新する（情報ビットを
残す場合である、以下直接的な実現と称す）。
残す復号パスの候補（生き残りパス）を以下に示す式
（５）及び（６）のようにして更新する（情報ビットを
残す場合である、以下直接的な実現と称す）。
【００１１】
【数３】 βt (n) ＝０のとき Ｖt (n) ＝｛０，ｖt-1 (i,0) ，ｖt-1 (i,1) ，…，ｖt-1 (i,Ms-1)｝， βt (n) ＝１のとき Ｖt (n) ＝｛０，ｖt-1 (j,0) ，ｖt-1 (j,1) ，…，ｖt-1 (j,Ms-1)｝ …(5) βt (m) ＝０のとき Ｖt (m) ＝｛１，ｖt-1 (i,0) ，ｖt-1 (i,1) ，…，ｖt-1 (i,Ms-1)｝， βt (m) ＝１のとき Ｖt (m) ＝｛１，ｖt-1 (j,0) ，ｖt-1 (j,1) ，…，ｖt-1 (j,Ms-1)｝ …(6) ここで、ｖt (S,k) は、時刻ｔで状態Ｓに対応する生き
残りパスの、現在からｋステップさかのぼった（時刻ｔ
−ｋに対応する）情報ビットである。また、状態ＳのＭ
ｓ段の生き残りパスは、次に示す式（７）となる。
残りパスの、現在からｋステップさかのぼった（時刻ｔ
−ｋに対応する）情報ビットである。また、状態ＳのＭ
ｓ段の生き残りパスは、次に示す式（７）となる。
【００１２】
【数４】 Ｖt (S) ＝｛ｖt (S,0) ，ｖt (S,1) ，ｖt (S,2) ，…，ｖt (S,Ms)｝ ただし、Ｓが偶数のときｖt (S,0) ＝０、Ｓが奇数のときｖt (S,0) ＝１ …(7) なお、各生き残りパスの右側（ｖ(S,Ms)）が最過去の情
報ビットに相当する。
報ビットに相当する。
【００１３】各生き残りパスのうち、それぞれに対応す
るパスメトリックが最小の生き残りパスが最尤パスであ
り、ビタビ復号出力Δt は、以下に示す式（８）のよう
にして決定される。
るパスメトリックが最小の生き残りパスが最尤パスであ
り、ビタビ復号出力Δt は、以下に示す式（８）のよう
にして決定される。
【００１４】
【数５】 Δt ＝δ（ｔ−Ｍs ）＝ｖt (SL,Ms) …(8) ここで、
【数６】 Γt (SL)＝min{Γt (0) ，Γt (1) ，Γt (2) ，…，Γt (Ns-1)｝ …(9) であり、状態ＳL は最尤パスに対応する状態（最尤パス
情報）を表す。
情報）を表す。
【００１５】前記式(5) 〜(8) に対応した操作を実現す
る従来のパスメモリ回路は、図７のような構成をとる。
各レジスタ（フリップフロップ）の入力側の信号が時刻
ｔに対応した生き残りパスの情報ビットであり、出力側
の信号が時刻ｔ−１に対応した生き残りパスの情報ビッ
トである。ビタビ復号出力は、最尤パス情報ＳL,t によ
りｖt (0,Ms)〜ｖt (Ns,Ms) のいずれかを選択して得ら
れるので、図８の構成のセレクタにより実現できる。
る従来のパスメモリ回路は、図７のような構成をとる。
各レジスタ（フリップフロップ）の入力側の信号が時刻
ｔに対応した生き残りパスの情報ビットであり、出力側
の信号が時刻ｔ−１に対応した生き残りパスの情報ビッ
トである。ビタビ復号出力は、最尤パス情報ＳL,t によ
りｖt (0,Ms)〜ｖt (Ns,Ms) のいずれかを選択して得ら
れるので、図８の構成のセレクタにより実現できる。
【００１６】高速な（例えば、数＋Mbps以上の）ビタビ
復号を情報ビットを残す手法で実現するには、Ｎｓ／２
＝３２の状態遷移の組について、式（５）及び（６）に
示すように１ステップ＝１クロックで一気にパスメモリ
（＝生き残りパス）の更新を行う必要がある。このた
め、パスメモリをＲＡＭで構成することは不可能で、図
７のパスメモリを構成する場合、Ｍs ×６４個のセレク
タと（Ｍs −１）×６４個のレジスタ（フリップフロッ
プ）が必要となる。
復号を情報ビットを残す手法で実現するには、Ｎｓ／２
＝３２の状態遷移の組について、式（５）及び（６）に
示すように１ステップ＝１クロックで一気にパスメモリ
（＝生き残りパス）の更新を行う必要がある。このた
め、パスメモリをＲＡＭで構成することは不可能で、図
７のパスメモリを構成する場合、Ｍs ×６４個のセレク
タと（Ｍs −１）×６４個のレジスタ（フリップフロッ
プ）が必要となる。
【００１７】
【発明が解決しようとする課題】状態数６４のたたみ込
み符号をマザーコードとした、符号化率Ｒ＝７／８のパ
ンクチャド符号に対応したビタビ復号を実現するために
は、そのパスメモリの段数Ｍs を１００程度とする必要
がある（文献[2] 安田、平田、小川著、“ヴィタビ復号
の容易な高符号化率たたみ込み符号とその諸特性”，信
学論(B),Vol.J64-B, No7, pp.573-580, Jul.1981. を参
照）。
み符号をマザーコードとした、符号化率Ｒ＝７／８のパ
ンクチャド符号に対応したビタビ復号を実現するために
は、そのパスメモリの段数Ｍs を１００程度とする必要
がある（文献[2] 安田、平田、小川著、“ヴィタビ復号
の容易な高符号化率たたみ込み符号とその諸特性”，信
学論(B),Vol.J64-B, No7, pp.573-580, Jul.1981. を参
照）。
【００１８】図７の構成によれば、そのパスメモリを構
成するのに、例えば１００×６４個のセレクタと９９×
６４個のレジスタが必要となり、セレクタ当たりのゲー
ト数を３ゲート、レジスタ（フリップフロップ）当たり
のゲート数を５ゲートとすると、合計約５０ｋゲートに
もなり、回路規模が大きくＩＣ化が困難であった。
成するのに、例えば１００×６４個のセレクタと９９×
６４個のレジスタが必要となり、セレクタ当たりのゲー
ト数を３ゲート、レジスタ（フリップフロップ）当たり
のゲート数を５ゲートとすると、合計約５０ｋゲートに
もなり、回路規模が大きくＩＣ化が困難であった。
【００１９】このパスメモリを縮小する有効な方法は、
レジスタをより集積度の高いＲＡＭで構成することであ
る。しかしながら、前記に示した手法でパスメモリの内
容を更新するにはデータバスがレジスタの数だけ必要で
現実的でない。ＩＣ化したときには配線の数が膨大とな
り、結局チップサイズは小さくならない。
レジスタをより集積度の高いＲＡＭで構成することであ
る。しかしながら、前記に示した手法でパスメモリの内
容を更新するにはデータバスがレジスタの数だけ必要で
現実的でない。ＩＣ化したときには配線の数が膨大とな
り、結局チップサイズは小さくならない。
【００２０】パスメモリとしてＲＡＭが使える手法に、
トレースバック法がある。これは文献[3]C.M,Rader著、
“Management in a Viterbi Decoder ”，IEEE Trans.
on Commun., Vol.COM-29, No.9, pp.1399-1401, Sep.19
81. に詳しい。トレースバック法は、パスメモリに復号
ステップ（時刻）ごとの選択フラグを記憶しておき、時
刻ｔにおける最尤パスに対応する状態ＳL,t からＭs 段
分の状態遷移をトレースバックしてビタビ復号出力δ
（ｔ−Ｍs ）を得る手法である。トレースバックは図９
の回路構成で実現できる。ただし、単純に各復号ステッ
プごとにこのトレースバックを行っていたのでは、高速
（数＋Mbps）の復号レートを実現することはできない。
トレースバック法がある。これは文献[3]C.M,Rader著、
“Management in a Viterbi Decoder ”，IEEE Trans.
on Commun., Vol.COM-29, No.9, pp.1399-1401, Sep.19
81. に詳しい。トレースバック法は、パスメモリに復号
ステップ（時刻）ごとの選択フラグを記憶しておき、時
刻ｔにおける最尤パスに対応する状態ＳL,t からＭs 段
分の状態遷移をトレースバックしてビタビ復号出力δ
（ｔ−Ｍs ）を得る手法である。トレースバックは図９
の回路構成で実現できる。ただし、単純に各復号ステッ
プごとにこのトレースバックを行っていたのでは、高速
（数＋Mbps）の復号レートを実現することはできない。
【００２１】以上の問題に鑑み本発明の課題は、高速復
号性能を保持しつつ、前記パスメモリの回路規模を縮小
した半導体集積回路化が容易なビタビ復号器を提供する
ことである。
号性能を保持しつつ、前記パスメモリの回路規模を縮小
した半導体集積回路化が容易なビタビ復号器を提供する
ことである。
【００２２】
【課題を解決するための手段】前記課題を解決するため
の本願第１の発明は、状態遷移のブランチの確かさを示
す量であるブランチメトリックを計算するブランチメト
リック演算回路と、各状態毎にパスメトリックを演算す
るとともにいずれのパスを選択したかを示すパス選択信
号を出力する加算比較選択回路と、各状態毎のパスメト
リックから最尤パスを選択して最尤パス選択信号を出力
する最尤判定回路と、復号の候補であるパスを記憶保持
するパスメモリ回路とを備えて構成されるビタビ復号器
において、前記パスメモリ回路は、前記パス選択信号を
複数ステップ分保持するメモリ回路と、前記最尤パス選
択信号に基づいて前記メモリ回路の記憶内容をトレース
バックするトレースバック回路と、前記トレースバック
回路の出力を所定の順序に並べ替える出力バッファ回路
と、トレースバック制御回路とからなり、前記メモリ回
路、前記トレースバック回路及び前記出力バッファ回路
からなる互いに独立に動作可能な複数組を具備し、前記
トレースバック制御回路は、前記各組のパスメモリ更新
動作と、トレースバック動作と、出力動作とを各組間で
位相をずらして交互に動作せしめることを要旨とする。
の本願第１の発明は、状態遷移のブランチの確かさを示
す量であるブランチメトリックを計算するブランチメト
リック演算回路と、各状態毎にパスメトリックを演算す
るとともにいずれのパスを選択したかを示すパス選択信
号を出力する加算比較選択回路と、各状態毎のパスメト
リックから最尤パスを選択して最尤パス選択信号を出力
する最尤判定回路と、復号の候補であるパスを記憶保持
するパスメモリ回路とを備えて構成されるビタビ復号器
において、前記パスメモリ回路は、前記パス選択信号を
複数ステップ分保持するメモリ回路と、前記最尤パス選
択信号に基づいて前記メモリ回路の記憶内容をトレース
バックするトレースバック回路と、前記トレースバック
回路の出力を所定の順序に並べ替える出力バッファ回路
と、トレースバック制御回路とからなり、前記メモリ回
路、前記トレースバック回路及び前記出力バッファ回路
からなる互いに独立に動作可能な複数組を具備し、前記
トレースバック制御回路は、前記各組のパスメモリ更新
動作と、トレースバック動作と、出力動作とを各組間で
位相をずらして交互に動作せしめることを要旨とする。
【００２３】本願第１の発明は、それぞれメモリ回路と
トレースバック回路と出力バッファ回路とからなる組を
複数組備えることにより、パスメモリの更新動作と、ト
レースバック動作と、トレースバックしながら復号デー
タを所定の順序に並べ替えて出力する出力動作とをそれ
ぞれ複数の組に交互に動作させることができる。これに
よりパスメモリをＲＡＭで構成可能として回路規模を縮
小するとともに、一つの組がパスメモリの更新動作中に
他の組がトレースバック及び出力動作を同時並列的に行
うので、連続的で高速なビタビ復号を実現することが可
能となる。
トレースバック回路と出力バッファ回路とからなる組を
複数組備えることにより、パスメモリの更新動作と、ト
レースバック動作と、トレースバックしながら復号デー
タを所定の順序に並べ替えて出力する出力動作とをそれ
ぞれ複数の組に交互に動作させることができる。これに
よりパスメモリをＲＡＭで構成可能として回路規模を縮
小するとともに、一つの組がパスメモリの更新動作中に
他の組がトレースバック及び出力動作を同時並列的に行
うので、連続的で高速なビタビ復号を実現することが可
能となる。
【００２４】また、本願第２の発明は、状態遷移のブラ
ンチの確かさを示す量であるブランチメトリックを計算
するブランチメトリック演算回路と、各状態毎にパスメ
トリックを演算するとともにいずれのパスを選択したか
を示すパス選択信号を出力する加算比較選択回路と、各
状態毎のパスメトリックから最尤パスを選択して最尤パ
ス選択信号を出力する最尤判定回路と、復号の候補であ
るパスを記憶保持するパスメモリ回路とを備えて構成さ
れるビタビ復号器において、前記パスメモリ回路は、前
記パス選択信号を複数ステップ分保持するメモリ回路
と、前記最尤パス選択信号に基づいて前記メモリ回路の
記憶内容をトレースバックするトレースバック回路と、
前記トレースバック回路の出力を所定の順序に並べ替え
る出力バッファ回路と、トレースバック制御回路とから
なり、前記メモリ回路及び前記トレースバック回路から
なる互いに独立に動作可能な複数組を具備し、前記トレ
ースバック制御回路は、前記各組のパスメモリ更新動作
と、トレースバック動作と、出力動作とを各組間で位相
をずらして交互に動作せしめ、前記出力バッファ回路
は、各トレースバック回路の出力を多重して所定の順序
に並べ替えることを要旨とする。
ンチの確かさを示す量であるブランチメトリックを計算
するブランチメトリック演算回路と、各状態毎にパスメ
トリックを演算するとともにいずれのパスを選択したか
を示すパス選択信号を出力する加算比較選択回路と、各
状態毎のパスメトリックから最尤パスを選択して最尤パ
ス選択信号を出力する最尤判定回路と、復号の候補であ
るパスを記憶保持するパスメモリ回路とを備えて構成さ
れるビタビ復号器において、前記パスメモリ回路は、前
記パス選択信号を複数ステップ分保持するメモリ回路
と、前記最尤パス選択信号に基づいて前記メモリ回路の
記憶内容をトレースバックするトレースバック回路と、
前記トレースバック回路の出力を所定の順序に並べ替え
る出力バッファ回路と、トレースバック制御回路とから
なり、前記メモリ回路及び前記トレースバック回路から
なる互いに独立に動作可能な複数組を具備し、前記トレ
ースバック制御回路は、前記各組のパスメモリ更新動作
と、トレースバック動作と、出力動作とを各組間で位相
をずらして交互に動作せしめ、前記出力バッファ回路
は、各トレースバック回路の出力を多重して所定の順序
に並べ替えることを要旨とする。
【００２５】本願第２の発明は、パスメモリの更新動作
と、トレースバック動作と、トレースバックしながら復
号データを出力する出力動作とをそれぞれ複数の組に交
互に動作させ、出力バッファは各復号データ出力を切り
かえながら入力して所定の順序に並べ替えて出力するこ
とができる。これによりパスメモリをＲＡＭで構成可能
として回路規模を縮小するとともに、一つの組がパスメ
モリの更新動作中に他の組がトレースバック及び出力動
作を同時並列的に行うので、連続的で高速なビタビ復号
を実現することが可能となる。
と、トレースバック動作と、トレースバックしながら復
号データを出力する出力動作とをそれぞれ複数の組に交
互に動作させ、出力バッファは各復号データ出力を切り
かえながら入力して所定の順序に並べ替えて出力するこ
とができる。これによりパスメモリをＲＡＭで構成可能
として回路規模を縮小するとともに、一つの組がパスメ
モリの更新動作中に他の組がトレースバック及び出力動
作を同時並列的に行うので、連続的で高速なビタビ復号
を実現することが可能となる。
【００２６】また、本願発明においては、前記メモリ回
路を４組具備することができる。また、本願発明におい
ては、リードモディファイライト動作可能な前記メモリ
回路を２組具備することができる。また、本願発明にお
いては、前記メモリ回路を３組具備することができる。
また、本願発明においては、前記トレースバック回路を
複数組の間で時分割共有化することができる。
路を４組具備することができる。また、本願発明におい
ては、リードモディファイライト動作可能な前記メモリ
回路を２組具備することができる。また、本願発明にお
いては、前記メモリ回路を３組具備することができる。
また、本願発明においては、前記トレースバック回路を
複数組の間で時分割共有化することができる。
【００２７】
【発明の実施の形態】次に、図面を参照して本発明の実
施の形態を詳細に説明する。図１は、本発明に係るビタ
ビ復号器の第１の実施の形態を示すブロック図である。
同図において、ビタビ復号器は、位相同期回路１０と、
デパンクチャ回路１１と、ＢＭＵ（Branch Metric Uni
t）１２と、正規化回路１３と、ＡＣＳＵ１４と、最尤
判定部１５と、Ｍs 段パスメモリ２０とを備えて構成さ
れている。
施の形態を詳細に説明する。図１は、本発明に係るビタ
ビ復号器の第１の実施の形態を示すブロック図である。
同図において、ビタビ復号器は、位相同期回路１０と、
デパンクチャ回路１１と、ＢＭＵ（Branch Metric Uni
t）１２と、正規化回路１３と、ＡＣＳＵ１４と、最尤
判定部１５と、Ｍs 段パスメモリ２０とを備えて構成さ
れている。
【００２８】Ｍs 段パスメモリ２０は、それぞれ６４ビ
ット×（２×Ｍs ）段の４組のＲＡＭ２１ａ〜２１ｄ
と、４つのトレースバック回路２２ａ〜２２ｄと、トレ
ースバック回路２２ａ及びトレースバック回路２２ｃの
出力を選択するセレクタ２３ａと、トレースバック回路
２２ｂ及びトレースバック回路２２ｄの出力を選択する
セレクタ２３ｂと、セレクタ２３ａで選択されたトレー
スバック回路の出力をラストイン・ファーストアウト
（以下、ＬＩＦＯと略記する）の順序で並べ変えるバッ
ファＡ（２４ａ）と、セレクタ２３ｂで選択されたトレ
ースバック回路の出力をＬＩＦＯの順序で並べ変えるバ
ッファＢ（２４ｂ）と、バッファＡまたはバッファＢの
出力を選択してビタビ復号出力とするセレクタ２６と、
トレースバック制御回路２５とから構成されている。
ット×（２×Ｍs ）段の４組のＲＡＭ２１ａ〜２１ｄ
と、４つのトレースバック回路２２ａ〜２２ｄと、トレ
ースバック回路２２ａ及びトレースバック回路２２ｃの
出力を選択するセレクタ２３ａと、トレースバック回路
２２ｂ及びトレースバック回路２２ｄの出力を選択する
セレクタ２３ｂと、セレクタ２３ａで選択されたトレー
スバック回路の出力をラストイン・ファーストアウト
（以下、ＬＩＦＯと略記する）の順序で並べ変えるバッ
ファＡ（２４ａ）と、セレクタ２３ｂで選択されたトレ
ースバック回路の出力をＬＩＦＯの順序で並べ変えるバ
ッファＢ（２４ｂ）と、バッファＡまたはバッファＢの
出力を選択してビタビ復号出力とするセレクタ２６と、
トレースバック制御回路２５とから構成されている。
【００２９】次に、本実施の形態の動作を説明する。軟
判定されたデータ（復調データＩd，Ｑd ）は、位相同
期回路１０により位相同期確定後、デパンクチャ回路１
１により送信側のパンクチャ処理に対応してデパンクチ
ャ処理が施され、ＢＭＵ１２によりブランチメトリック
が算出される。次いで、正規化回路１３によるパスメト
リックのオーバフローを防ぐための正規化処理の後、各
状態に対応したＡＣＳＵ１４（図６に示した構成を３２
組備える）にてパスメトリックの更新が行われる。各パ
スメトリックのうち最尤パスに対応した最尤パスメトリ
ックΓL （通常最小値）が最尤判定部１５にて判定さ
れ、これが前記正規化に用いられる。
判定されたデータ（復調データＩd，Ｑd ）は、位相同
期回路１０により位相同期確定後、デパンクチャ回路１
１により送信側のパンクチャ処理に対応してデパンクチ
ャ処理が施され、ＢＭＵ１２によりブランチメトリック
が算出される。次いで、正規化回路１３によるパスメト
リックのオーバフローを防ぐための正規化処理の後、各
状態に対応したＡＣＳＵ１４（図６に示した構成を３２
組備える）にてパスメトリックの更新が行われる。各パ
スメトリックのうち最尤パスに対応した最尤パスメトリ
ックΓL （通常最小値）が最尤判定部１５にて判定さ
れ、これが前記正規化に用いられる。
【００３０】またこの最尤パスメトリックΓL は、位相
同期とパンクチャのレートが整合していないとき、値が
増大する傾向にあるため、この同期判定を行い、適当な
位相とデパンクチャ処理が選択される。
同期とパンクチャのレートが整合していないとき、値が
増大する傾向にあるため、この同期判定を行い、適当な
位相とデパンクチャ処理が選択される。
【００３１】ビタビ復号の候補を必要段数（Ｍs 段）記
憶・保持するのが、Ｍs 段パスメモリ回路２０である。
この内容の更新には各状態に対応した選択フラグβ(0)
〜β(63)と、最尤パスに対応した最尤パス情報を用い
る。なお、必要段数よりも十分大なる段数分記憶保持す
ることが可能ならば、必ずしも最尤パス情報を必要とし
ない。
憶・保持するのが、Ｍs 段パスメモリ回路２０である。
この内容の更新には各状態に対応した選択フラグβ(0)
〜β(63)と、最尤パスに対応した最尤パス情報を用い
る。なお、必要段数よりも十分大なる段数分記憶保持す
ることが可能ならば、必ずしも最尤パス情報を必要とし
ない。
【００３２】トレースバック法を用いて数十Mbpsの復号
レートを実現する要点は、生き残りパスをいったんＭs
段さかのぼったときに、すべての生き残りが１本に合流
している場合には、さらにその先も１本に合流している
（図５の破線部分）という、きわめて明快で単純な原理
を利用することである。
レートを実現する要点は、生き残りパスをいったんＭs
段さかのぼったときに、すべての生き残りが１本に合流
している場合には、さらにその先も１本に合流している
（図５の破線部分）という、きわめて明快で単純な原理
を利用することである。
【００３３】例えば、メモリ回路として２×Ｍs 段分用
意しておき、トレースバックの１周期を２×Ｍs ステッ
プとする。上記の原理から、いったんＭs 段トレースバ
ックするとそこから先のトレースバックは、（ビタビ復
号の訂正能力の範囲内で正しい）復号出力を次々と得る
ことができる。ｋステップのトレースバック後のレジス
タの内容Ｓr,k を、
意しておき、トレースバックの１周期を２×Ｍs ステッ
プとする。上記の原理から、いったんＭs 段トレースバ
ックするとそこから先のトレースバックは、（ビタビ復
号の訂正能力の範囲内で正しい）復号出力を次々と得る
ことができる。ｋステップのトレースバック後のレジス
タの内容Ｓr,k を、
【数７】 Ｓr,k ＝βt-k (Sr,k-1)＾（Ｓr,k-1 >>１） …(10) とする。ここで、Ｓr,0 ＝ＳL,t である。すると、ビタ
ビ復号出力はＭs ≦ｋ≦２×Ｍs の範囲で有効となり、
ビ復号出力はＭs ≦ｋ≦２×Ｍs の範囲で有効となり、
【数８】 δ（ｔ−ｋ）＝Ｓr,k ＾１ …(11) となる。ただし、時間的に逆の順番で再生されるので、
ＬＩＦＯ機能を有する出力バッファを設けて正しい順に
出力する。出力バッファには、例えば１ビット×Ｍs ワ
ードのメモリまたは左右シフト可能なシフトレジスタを
用いても良い。このように、１回のトレースバックでビ
タビ復号出力がＭs ビット得られる。
ＬＩＦＯ機能を有する出力バッファを設けて正しい順に
出力する。出力バッファには、例えば１ビット×Ｍs ワ
ードのメモリまたは左右シフト可能なシフトレジスタを
用いても良い。このように、１回のトレースバックでビ
タビ復号出力がＭs ビット得られる。
【００３４】連続的にビタビ復号を行うには、２×Ｍs
段のメモリ回路２１と図９のトレースバック回路２２を
それぞれａ〜ｄの４組用意し、時間差を与えて動作さ
せ、それぞれの復号出力をセレクタ２３ａ，２３ｂで切
り替えて用いる。その動作を説明するタイミング図を図
１０に示す。２組でなくて４組用意するのは、ＲＡＭの
読み出し１周期のうち出力に直接寄与するのがその半分
の時間だからである。
段のメモリ回路２１と図９のトレースバック回路２２を
それぞれａ〜ｄの４組用意し、時間差を与えて動作さ
せ、それぞれの復号出力をセレクタ２３ａ，２３ｂで切
り替えて用いる。その動作を説明するタイミング図を図
１０に示す。２組でなくて４組用意するのは、ＲＡＭの
読み出し１周期のうち出力に直接寄与するのがその半分
の時間だからである。
【００３５】図１０のタイミング図において、十分に長
い符号系列のビタビ復号が行われるものとし、それぞれ
６４ビットで構成されたパス選択フラグβがＡＣＳＵよ
りクロック毎に出力されるとする。これによりパス選択
フラグβｔはクロック毎に状態が変化するが、時系列上
でＭs 個ずつのパス選択フラグβｔにより、本実施の形
態の動作の区切り（位相）がつけられている。
い符号系列のビタビ復号が行われるものとし、それぞれ
６４ビットで構成されたパス選択フラグβがＡＣＳＵよ
りクロック毎に出力されるとする。これによりパス選択
フラグβｔはクロック毎に状態が変化するが、時系列上
でＭs 個ずつのパス選択フラグβｔにより、本実施の形
態の動作の区切り（位相）がつけられている。
【００３６】まず、ＲＡＭａ及びトレースバック回路ａ
からなるａ組の動作について説明する。ＲＡＭａは最初
の２Ｍs クロックの期間に、２Ｍs 個のパス選択フラグ
β0〜β2Ms-1 を順次アドレス昇順で各記憶番地に記憶
する。そして、次のＭs クロックの期間に、ＲＡＭａか
らパス選択フラグβ2Ms-1 〜βMsがアドレス降順で読み
出され、トレースバック回路ａによりトレースバックさ
れる（ＴＢａ）。このトレースバック回路の“ＴＢ”と
は、トレースバック動作のみでは出力しない（有効でな
い）サイクルを示す。
からなるａ組の動作について説明する。ＲＡＭａは最初
の２Ｍs クロックの期間に、２Ｍs 個のパス選択フラグ
β0〜β2Ms-1 を順次アドレス昇順で各記憶番地に記憶
する。そして、次のＭs クロックの期間に、ＲＡＭａか
らパス選択フラグβ2Ms-1 〜βMsがアドレス降順で読み
出され、トレースバック回路ａによりトレースバックさ
れる（ＴＢａ）。このトレースバック回路の“ＴＢ”と
は、トレースバック動作のみでは出力しない（有効でな
い）サイクルを示す。
【００３７】次いで、次のＭs クロックの期間に、ＲＡ
Ｍａからパス選択フラグβMs-1〜β0 がアドレス降順で
読み出され、トレースバック回路ａによりトレースバッ
クされ、有効なＭs 個のトレースバック出力が出力され
る（ＯＵＴａ）とともに、セレクタ２３ａを介して順次
バッファＡに書き込まれる。
Ｍａからパス選択フラグβMs-1〜β0 がアドレス降順で
読み出され、トレースバック回路ａによりトレースバッ
クされ、有効なＭs 個のトレースバック出力が出力され
る（ＯＵＴａ）とともに、セレクタ２３ａを介して順次
バッファＡに書き込まれる。
【００３８】次いで、次のＭs クロックの期間に、バッ
ファＡから書き込まれた順序と逆の順序（ＬＩＦＯ）で
トレースバックデータを読み出し、セレクタ２６を介し
てビタビ復号出力として出力される。
ファＡから書き込まれた順序と逆の順序（ＬＩＦＯ）で
トレースバックデータを読み出し、セレクタ２６を介し
てビタビ復号出力として出力される。
【００３９】次に、ＲＡＭｂ及びトレースバック回路ｂ
からなるｂ組の動作について説明する。ｂ組の動作は、
ａ組の動作からＭs クロックだけ位相が遅れている。す
なわち、ＲＡＭａの書き込み開始からＭs クロック遅れ
てＲＡＭｂの書き込みが始まり、２Ｍs クロックの期間
に、２Ｍs 個のパス選択フラグβMs〜β3Ms-1 を順次ア
ドレス昇順で各記憶番地に記憶する。そして、次のＭs
クロックの期間に、ＲＡＭｂからパス選択フラグβ
3Ms-1 〜β2Ms がアドレス降順で読み出され、トレース
バック回路ｂによりトレースバックされる（ＴＢｂ）。
からなるｂ組の動作について説明する。ｂ組の動作は、
ａ組の動作からＭs クロックだけ位相が遅れている。す
なわち、ＲＡＭａの書き込み開始からＭs クロック遅れ
てＲＡＭｂの書き込みが始まり、２Ｍs クロックの期間
に、２Ｍs 個のパス選択フラグβMs〜β3Ms-1 を順次ア
ドレス昇順で各記憶番地に記憶する。そして、次のＭs
クロックの期間に、ＲＡＭｂからパス選択フラグβ
3Ms-1 〜β2Ms がアドレス降順で読み出され、トレース
バック回路ｂによりトレースバックされる（ＴＢｂ）。
【００４０】次いで、次のＭs クロックの期間に、ＲＡ
Ｍｂからパス選択フラグβ2Ms-1 〜βMsがアドレス降順
で読み出され、トレースバック回路ｂによりトレースバ
ックされ、有効なＭs 個のトレースバック出力が出力さ
れる（ＯＵＴｂ）とともに、セレクタ２３ｂを介して順
次バッファＢに書き込まれる。
Ｍｂからパス選択フラグβ2Ms-1 〜βMsがアドレス降順
で読み出され、トレースバック回路ｂによりトレースバ
ックされ、有効なＭs 個のトレースバック出力が出力さ
れる（ＯＵＴｂ）とともに、セレクタ２３ｂを介して順
次バッファＢに書き込まれる。
【００４１】次いで、次のＭs クロックの期間に、バッ
ファＢから書き込まれた順序と逆の順序（ＬＩＦＯ）で
トレースバックデータを読み出し、セレクタ２６を介し
てビタビ復号出力として出力される。
ファＢから書き込まれた順序と逆の順序（ＬＩＦＯ）で
トレースバックデータを読み出し、セレクタ２６を介し
てビタビ復号出力として出力される。
【００４２】同様に、ＲＡＭｃ及びトレースバック回路
ｃからなるｃ組の動作は、ｂ組の動作からＭs クロック
だけ位相が遅れているが、使用するバッファは、バッフ
ァＡである。同様に、ＲＡＭｄ及びトレースバック回路
ｄからなるｄ組の動作は、ｃ組の動作からＭs クロック
だけ位相が遅れているが、使用するバッファは、バッフ
ァＢである。
ｃからなるｃ組の動作は、ｂ組の動作からＭs クロック
だけ位相が遅れているが、使用するバッファは、バッフ
ァＡである。同様に、ＲＡＭｄ及びトレースバック回路
ｄからなるｄ組の動作は、ｃ組の動作からＭs クロック
だけ位相が遅れているが、使用するバッファは、バッフ
ァＢである。
【００４３】このように、ａ組とｃ組とでバッファＡ、
ｂ組とｄ組とでバッファＢをそれぞれ共用して並べ変え
を行うことにより、セレクタ２６からは切れ目のないビ
タビ復号出力、ＯＵＴａ，ＯＵＴｂ，ＯＵＴｃ，ＯＵＴ
ｄが得られる。
ｂ組とｄ組とでバッファＢをそれぞれ共用して並べ変え
を行うことにより、セレクタ２６からは切れ目のないビ
タビ復号出力、ＯＵＴａ，ＯＵＴｂ，ＯＵＴｃ，ＯＵＴ
ｄが得られる。
【００４４】この構成でビタビ復号が連続的に可能であ
ることを計算機による回路動作シミュレーションでも確
認した。このシミュレーション結果と前記文献［２］に
よるビタビ復号器のビット誤り率（ＢＥＲ）の理論的上
界特性を図１１に示す。出力バッファは、図１に示すよ
うに、複数のＲＡＭ間で共有して時分割動作させても良
いし、図２に示す第２の実施の形態のように、出力バッ
ファ２４ａ〜２４ｄとして各組毎に設けて、並べ替えた
後の出力をセレクタ２６で選択する構成としても良い。
ることを計算機による回路動作シミュレーションでも確
認した。このシミュレーション結果と前記文献［２］に
よるビタビ復号器のビット誤り率（ＢＥＲ）の理論的上
界特性を図１１に示す。出力バッファは、図１に示すよ
うに、複数のＲＡＭ間で共有して時分割動作させても良
いし、図２に示す第２の実施の形態のように、出力バッ
ファ２４ａ〜２４ｄとして各組毎に設けて、並べ替えた
後の出力をセレクタ２６で選択する構成としても良い。
【００４５】なお、ＲＡＭのアクセススピードに余裕が
あって、リードモディファイライトの倍レートアクセス
が可能なときは、トレースバックのための読み出しとパ
スメモリの更新のための書き込みとがリードモディファ
イライトにより行えるので、ＲＡＭａとＲＡＭｃ，ＲＡ
ＭｂとＲＡＭｄはそれぞれ共通として、２組のＲＡＭ回
路により実現することができる。
あって、リードモディファイライトの倍レートアクセス
が可能なときは、トレースバックのための読み出しとパ
スメモリの更新のための書き込みとがリードモディファ
イライトにより行えるので、ＲＡＭａとＲＡＭｃ，ＲＡ
ＭｂとＲＡＭｄはそれぞれ共通として、２組のＲＡＭ回
路により実現することができる。
【００４６】４組のメモリ回路によるパスメモリの回路
規模は、同期型のＲＡＭの採用を前提とすると約０．２
ゲート／ビットより、（６４bit ×（２×Ｍs ）word）
×４＝４９ｋ bitで約９．８ｋゲート相当となる。ビタ
ビ復号全体で約３５ｋゲート実現できる（Ｍs ＝９６，
Ｒ＝７／８までのパンクチャド符号に対応）。パスメモ
リの実際の構成は、例えば１６bit ×１９２wordのＲＡ
Ｍ・ＩＣを１６個使用する構成となる。
規模は、同期型のＲＡＭの採用を前提とすると約０．２
ゲート／ビットより、（６４bit ×（２×Ｍs ）word）
×４＝４９ｋ bitで約９．８ｋゲート相当となる。ビタ
ビ復号全体で約３５ｋゲート実現できる（Ｍs ＝９６，
Ｒ＝７／８までのパンクチャド符号に対応）。パスメモ
リの実際の構成は、例えば１６bit ×１９２wordのＲＡ
Ｍ・ＩＣを１６個使用する構成となる。
【００４７】次に本発明の第３の実施の形態を説明す
る。回路規模の縮小化において、ＩＣのチップサイズは
ゲート数もさることながら、配線数ないし配線を収容す
るためのチップ面積の比重が大きい。ＲＡＭのビット数
を最小とするよりも、個数（あるいはデータ数）を減ら
す方が配線数及び配線の総延長を減少し、回路の小形化
に有利な場合がある。
る。回路規模の縮小化において、ＩＣのチップサイズは
ゲート数もさることながら、配線数ないし配線を収容す
るためのチップ面積の比重が大きい。ＲＡＭのビット数
を最小とするよりも、個数（あるいはデータ数）を減ら
す方が配線数及び配線の総延長を減少し、回路の小形化
に有利な場合がある。
【００４８】この点を考慮して、本発明の第３の実施の
形態として、パスメモリを３組のメモリ回路で構成する
場合のブロック図を図１２に、その動作タイミングを図
１３に示す。
形態として、パスメモリを３組のメモリ回路で構成する
場合のブロック図を図１２に、その動作タイミングを図
１３に示す。
【００４９】図１２において、Ｍs 段パスメモリ４０
は、それぞれ６４ビット×（３×Ｍs）段の３組のメモ
リ回路ＲＡＭ２１ａ〜２１ｃと、３つのトレースバック
回路２２ａ〜２２ｃと、それぞれトレースバック回路２
２ａ〜２２ｃの出力を選択するセレクタ２３ａ、２３ｂ
と、セレクタ２３ａ，２３ｂで選択されたトレースバッ
ク回路の出力をＬＩＦＯの順序で並べ変えるバッファＡ
（２４ａ），バッファＢ（２４ｂ）と、バッファＡ（２
４ａ）またはバッファＢ（２４ｂ）の出力を選択してビ
タビ復号出力とするセレクタ２６と、トレースバック制
御回路２５と、から構成されている。
は、それぞれ６４ビット×（３×Ｍs）段の３組のメモ
リ回路ＲＡＭ２１ａ〜２１ｃと、３つのトレースバック
回路２２ａ〜２２ｃと、それぞれトレースバック回路２
２ａ〜２２ｃの出力を選択するセレクタ２３ａ、２３ｂ
と、セレクタ２３ａ，２３ｂで選択されたトレースバッ
ク回路の出力をＬＩＦＯの順序で並べ変えるバッファＡ
（２４ａ），バッファＢ（２４ｂ）と、バッファＡ（２
４ａ）またはバッファＢ（２４ｂ）の出力を選択してビ
タビ復号出力とするセレクタ２６と、トレースバック制
御回路２５と、から構成されている。
【００５０】各メモリ回路ＲＡＭ２１ａ〜２１ｃは、３
×Ｍs 段として１回のトレースバックで２×Ｍs ビット
の復号出力を得る。ＲＡＭの総ビット数は３組合計で５
５ｋビット（１１ｋゲート相当）であるが、配線数は３
／４になる（例えば１６bit×２８８wordのＲＡＭ・Ｉ
Ｃを１２個（４×３に配列）使用して構成できる）。復
調データが入力されてからビタビ復号出力が得られるま
での遅延量は、４×Ｍs （ビットタイム）から６×Ｍs
（ビットタイム）に増加するが、復号レートが速い場合
にはさほど問題にならない。
×Ｍs 段として１回のトレースバックで２×Ｍs ビット
の復号出力を得る。ＲＡＭの総ビット数は３組合計で５
５ｋビット（１１ｋゲート相当）であるが、配線数は３
／４になる（例えば１６bit×２８８wordのＲＡＭ・Ｉ
Ｃを１２個（４×３に配列）使用して構成できる）。復
調データが入力されてからビタビ復号出力が得られるま
での遅延量は、４×Ｍs （ビットタイム）から６×Ｍs
（ビットタイム）に増加するが、復号レートが速い場合
にはさほど問題にならない。
【００５１】さらに、本実施の形態の変形例として、ト
レースバック回路も時分割共有化可能である。例えば図
１０のタイミング図によれば、トレースバック回路２２
ａと２２ｃとは同時にトレースバック処理は行わないの
で共有化できる。同様に２２ｂと２２ｄとを共有化する
ことができる。
レースバック回路も時分割共有化可能である。例えば図
１０のタイミング図によれば、トレースバック回路２２
ａと２２ｃとは同時にトレースバック処理は行わないの
で共有化できる。同様に２２ｂと２２ｄとを共有化する
ことができる。
【００５２】以上の実施の形態の説明において、トレー
スバックの初期値Ｓr,0 は最尤パスに対応する状態Ｓ
L,t としたが、前記トレースバックの段数Ｍs を十分に
大とするとＳr,0 は任意（例えば状態(0))とすることが
可能である。
スバックの初期値Ｓr,0 は最尤パスに対応する状態Ｓ
L,t としたが、前記トレースバックの段数Ｍs を十分に
大とするとＳr,0 は任意（例えば状態(0))とすることが
可能である。
【００５３】また、上記の実施の形態では、図３に示す
非組織符号であるたたみ込み符号化を例に、そのビタビ
復号の構成を示したきたが、組織符号を含めた任意のた
たみ込み符号化に対するビタビ復号器について本発明が
有効であることは明白である。
非組織符号であるたたみ込み符号化を例に、そのビタビ
復号の構成を示したきたが、組織符号を含めた任意のた
たみ込み符号化に対するビタビ復号器について本発明が
有効であることは明白である。
【００５４】
【発明の効果】以上説明したように本発明によれば、高
速動作を可能としつつ、パスメモリをＲＡＭで構成可能
なので、高速動作のビタビ復号器の回路規模を縮小でき
るという効果がある。
速動作を可能としつつ、パスメモリをＲＡＭで構成可能
なので、高速動作のビタビ復号器の回路規模を縮小でき
るという効果がある。
【図１】本発明に係るビタビ復号器の第１の実施の形態
の構成を示すブロック図である。
の構成を示すブロック図である。
【図２】本発明に係るビタビ復号器の第２の実施の形態
の構成を示すブロック図である。
の構成を示すブロック図である。
【図３】たたみ込み符号の符号器の構成例を示す回路図
である。
である。
【図４】状態遷移の組を示す状態遷移図である。
【図５】生き残りパスの説明図である。
【図６】加算比較選択ユニット（ＡＣＳＵ）の構成を示
すブロック図である。
すブロック図である。
【図７】従来のパスメモリの直接的な実現を示すブロッ
ク図である。
ク図である。
【図８】最尤パス選択による復号出力を示すブロック図
である。
である。
【図９】トレースバック回路の構成を示すブロック図で
ある。
ある。
【図１０】トレースバックによる復号動作を示す第１の
タイミング図である。
タイミング図である。
【図１１】トレースバックによる復号ＢＥＲ特性を示す
グラフである。
グラフである。
【図１２】本発明に係るビタビ復号器の第３の実施の形
態の構成を示すブロック図である。
態の構成を示すブロック図である。
【図１３】トレースバックによる復号動作を示す第２の
タイミング図である。
タイミング図である。
１０ 位相同期回路 １１ デパンクチャ回路 １
２ ＢＭＵ １３正規化回路 １４ ＡＣＳＵ
１５ 最尤判定回路 １６ 同期判定回路 ２１ａ，２１ｂ，２１ｃ，２１ｄ ＲＡＭ ２２ａ，
２２ｂ，２２ｃ，２２ｄ トレースバック回路 ２４
ａ，２４ｂ，２４ｃ，２４ｄ バッファ ２５ トレースバック制御回路 ２６ セレクタ
３０ Ｍｓ段パスメモリ
２ ＢＭＵ １３正規化回路 １４ ＡＣＳＵ
１５ 最尤判定回路 １６ 同期判定回路 ２１ａ，２１ｂ，２１ｃ，２１ｄ ＲＡＭ ２２ａ，
２２ｂ，２２ｃ，２２ｄ トレースバック回路 ２４
ａ，２４ｂ，２４ｃ，２４ｄ バッファ ２５ トレースバック制御回路 ２６ セレクタ
３０ Ｍｓ段パスメモリ
Claims (6)
- 【請求項１】 状態遷移のブランチの確かさを示す量で
あるブランチメトリックを計算するブランチメトリック
演算回路と、各状態毎にパスメトリックを演算するとと
もにいずれのパスを選択したかを示すパス選択信号を出
力する加算比較選択回路と、各状態毎のパスメトリック
から最尤パスを選択して最尤パス選択信号を出力する最
尤判定回路と、復号の候補であるパスを記憶保持するパ
スメモリ回路とを備えて構成されるビタビ復号器におい
て、 前記パスメモリ回路は、前記パス選択信号を複数ステッ
プ分保持するメモリ回路と、前記最尤パス選択信号に基
づいて前記メモリ回路の記憶内容をトレースバックする
トレースバック回路と、前記トレースバック回路の出力
を所定の順序に並べ替える出力バッファ回路と、トレー
スバック制御回路とからなり、 前記メモリ回路、前記トレースバック回路及び前記出力
バッファ回路からなる互いに独立に動作可能な複数組を
具備し、 前記トレースバック制御回路は、前記各組のパスメモリ
更新動作と、トレースバック動作と、出力動作とを各組
間で位相をずらして交互に動作せしめることを特徴とす
るビタビ復号器。 - 【請求項２】 状態遷移のブランチの確かさを示す量で
あるブランチメトリックを計算するブランチメトリック
演算回路と、各状態毎にパスメトリックを演算するとと
もにいずれのパスを選択したかを示すパス選択信号を出
力する加算比較選択回路と、各状態毎のパスメトリック
から最尤パスを選択して最尤パス選択信号を出力する最
尤判定回路と、復号の候補であるパスを記憶保持するパ
スメモリ回路とを備えて構成されるビタビ復号器におい
て、 前記パスメモリ回路は、前記パス選択信号を複数ステッ
プ分保持するメモリ回路と、前記最尤パス選択信号に基
づいて前記メモリ回路の記憶内容をトレースバックする
トレースバック回路と、前記トレースバック回路の出力
を所定の順序に並べ替える出力バッファ回路と、トレー
スバック制御回路とからなり、 前記メモリ回路及び前記トレースバック回路からなる互
いに独立に動作可能な複数組を具備し、 前記トレースバック制御回路は、前記各組のパスメモリ
更新動作と、トレースバック動作と、出力動作とを各組
間で位相をずらして交互に動作せしめ、前記出力バッフ
ァ回路は、各トレースバック回路の出力を多重して所定
の順序に並べ替えることを特徴とするビタビ復号器。 - 【請求項３】 前記メモリ回路を４組具備したことを特
徴とする請求項１または請求項２記載のビタビ復号器。 - 【請求項４】 リードモディファイライト動作可能な前
記メモリ回路を２組具備したことを特徴とする請求項１
または請求項２記載のビタビ復号器。 - 【請求項５】 前記メモリ回路を３組具備したことを特
徴とする請求項１または請求項２記載のビタビ復号器。 - 【請求項６】 前記トレースバック回路を複数組の間で
時分割共有化したことを特徴とする請求項１または請求
項２記載のビタビ復号器。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20241895A JPH0951278A (ja) | 1995-08-08 | 1995-08-08 | ビタビ復号器 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20241895A JPH0951278A (ja) | 1995-08-08 | 1995-08-08 | ビタビ復号器 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0951278A true JPH0951278A (ja) | 1997-02-18 |
Family
ID=16457186
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP20241895A Pending JPH0951278A (ja) | 1995-08-08 | 1995-08-08 | ビタビ復号器 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0951278A (ja) |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0918292A3 (en) * | 1997-11-24 | 2000-03-01 | Lucent Technologies Inc. | Minimum and maximum value searching method |
| US6041433A (en) * | 1996-01-08 | 2000-03-21 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder and viterbi decoding method |
| US6263473B1 (en) | 1997-04-07 | 2001-07-17 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder and Viterbi decoding method |
| US6728926B1 (en) | 1999-06-29 | 2004-04-27 | Matsushita Electric Industrial Co., Ltd. | Encoding rate detection method and encoding rate detection device |
| JP2006229376A (ja) * | 2005-02-16 | 2006-08-31 | Nec Corp | ビタビ復号器及びそれを用いる移動体通信装置、基地局装置、移動体通信端末 |
| KR100752659B1 (ko) * | 2006-03-09 | 2007-08-29 | 삼성전자주식회사 | 데이터 검출 방법 및 장치와 이를 이용한 디스크 드라이브 |
| JP2010135918A (ja) * | 2008-12-02 | 2010-06-17 | Nec Corp | 演算装置、復号化装置およびメモリ制御方法ならびにプログラム |
| JP2010206570A (ja) * | 2009-03-04 | 2010-09-16 | Sony Corp | 復号装置、復号方法 |
-
1995
- 1995-08-08 JP JP20241895A patent/JPH0951278A/ja active Pending
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6041433A (en) * | 1996-01-08 | 2000-03-21 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder and viterbi decoding method |
| US6263473B1 (en) | 1997-04-07 | 2001-07-17 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder and Viterbi decoding method |
| EP0918292A3 (en) * | 1997-11-24 | 2000-03-01 | Lucent Technologies Inc. | Minimum and maximum value searching method |
| US6728926B1 (en) | 1999-06-29 | 2004-04-27 | Matsushita Electric Industrial Co., Ltd. | Encoding rate detection method and encoding rate detection device |
| JP2006229376A (ja) * | 2005-02-16 | 2006-08-31 | Nec Corp | ビタビ復号器及びそれを用いる移動体通信装置、基地局装置、移動体通信端末 |
| KR100752659B1 (ko) * | 2006-03-09 | 2007-08-29 | 삼성전자주식회사 | 데이터 검출 방법 및 장치와 이를 이용한 디스크 드라이브 |
| JP2010135918A (ja) * | 2008-12-02 | 2010-06-17 | Nec Corp | 演算装置、復号化装置およびメモリ制御方法ならびにプログラム |
| JP2010206570A (ja) * | 2009-03-04 | 2010-09-16 | Sony Corp | 復号装置、復号方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3515720B2 (ja) | ビタビ復号器 | |
| JP3747604B2 (ja) | ビタビ復号装置 | |
| US7246298B2 (en) | Unified viterbi/turbo decoder for mobile communication systems | |
| JP2000209106A (ja) | 高速ビタビ復号器の最小量のメモリによる実現 | |
| JPH0951278A (ja) | ビタビ復号器 | |
| US20050010854A1 (en) | Unified serial/parallel concatenated convolutional code decoder architecture and method | |
| EP2339757A1 (en) | Power-reduced preliminary decoded bits in viterbi decoder | |
| JP3259725B2 (ja) | ビタビ復号装置 | |
| CN114448562A (zh) | 维特比解码器中的并行回溯 | |
| CN118631265A (zh) | 一种新颖高效的全并行维特比译码设计方法及系统 | |
| JPH1155130A (ja) | ビタビ復号器 | |
| JP3753822B2 (ja) | ビタビ復号方法および装置 | |
| US7590928B2 (en) | Apparatus and method for Viterbi decoding | |
| JP4047697B2 (ja) | ビタビ復号装置 | |
| JPH05335973A (ja) | ビタビ復号器及び畳み込み符号の復号器 | |
| JP2002534902A (ja) | 復号装置におけるエム・エル状態選択装置及び方法 | |
| CN101826879A (zh) | 解码装置和解码方法 | |
| JP3260714B2 (ja) | ビタビ復号化装置およびビタビ復号化方法 | |
| JP2575853B2 (ja) | ビタビ復号回路 | |
| JP3288328B2 (ja) | ビタビ復号器のトレースバック処理の高速化装置およびその高速化方法 | |
| JP4702721B2 (ja) | ビタビ・メトリック計算のためのアドレッシング方法 | |
| JP2002198827A (ja) | 最尤復号方法及び最尤復号器 | |
| KR100410995B1 (ko) | 즉시역추적 알고리즘을 이용한 비터비 복호기용 생존경로메모리 관리 방법 및 그 장치 | |
| JP2003258650A (ja) | 最尤復号器 | |
| JP2004120791A (ja) | ビタビ復号器 |