列表 Viterbi 译码算法及其应用

中国科技论文在线

http://www.paper.edu.cn

列表 Viterbi 译码算法及其应用

郝芳芳，牛凯**

5 （北京邮电大学信息与通信工程学院，北京 100876） 摘要：Viterbi 译码算法（VA）是卷积码的最大似然(ML)译码算法。列表 Viterbi 译码算法 (LVA)产生 L 个有序的最佳译码序列。 相对于 VA 算法性能有很大提高。 列表 Viterbi 译码算 法主要有两种：同时产生 L 个最佳序列的并行列表 Viterbi 译码算法(PLVA)和根据前 L-1 个最佳序列产生第 L 个最佳序列的串行列表 Viterbi 译码算法(SLVA)。本文采用外码为 CRC 检验， 内码为卷积码的级联结构对传统 Viterbi 译码算法和列表 Viterbi 译码算法进行仿真 并在相同条件下对比其误帧率。 关键词：VA；ML；LVA; 串行；并行 中图分类号：TN92

10

List Viterbi Decoding Algorithm and Its Application

15

HAO Fangfang, NIU Kai

(Beijing University of Posts and Telecommunications, College of Information and Telecommunication Engineering, Beijing 100876) Abstract: The Viterbi Algorithm(VA) is the maximum likelihood decoding algorighm for convolutional code. List Viterbi Alogrithm(LVA) produces L best decoding sequences and considerable improvement in performance can be obtained through LVA. There are two List Viterbi Algorithms. They are respectively, a Parallel Viterbi Algorithm(PLVA) that simultaneously produces L best sequences, and a Serial Viterbi Algorithm(SLVA)that produces the L best sequences using the previously found L-1 best sequences. In this paper, the concatenated system that uses Cyclical Redundancy Check(CRC) as the outer encoder and convolutional code as the inner encoder is considered. The system's performances using VA and LVA respectively are compared. Keywords: VA; ML; LVA; Parallel; Serial

20

25

0 引言

30 Viterbi 译码算法通过在卷积码的格图结构中搜索最佳路径来译码。通常采用级联码的 结构，在假设进入内编码器的数据是独立、服从同一分布的前提下先进行内编码译码，然后 进行外编码译码。在得知该格图结构的 L(L>1)条最佳路径后，Viterbi 译码算法的性能可以 得到很大提高。 近年来发现了很多种 VA 算法。 Forney 给出一个可得到两条最佳译码序列的最大似然译 35 码器[1]，以分析序列译码。Yamamoto 和 Itoh 提出将 LVA 算法与自动重传算法(ARQ)相结 合

[2]

，该算法指出当进入每一状态的最佳路径与进入该状态的第二条最佳路径“太近”时

就发出重传该帧的请求。 但是他们都没有利用第二条最佳路径、 第三条最佳路径等的信息来 进行译码。Hashimoto 提出列表型的约束长度 Viterbi 算法[3]，该算法的目的是保证译码复杂 度不高于传统 Viterbi 算法并避免由译码状态的减少产生的错误传递。但是他也只是利用了 40 第一条最佳路径的信息，因此不能算是列表译码算法。 本论文考虑可以产生任意条最佳路径的 LVA 算法。主要有两种 LVA 算法[4]，即同时产 生 L 条最佳路径的并行 LVA，以及根据前 l 条最佳路径的信息找到第 l + 1 条最佳路径的串

作者简介：郝芳芳，（1987-）， 女， 研二， 主要研究方向：信号与信息处理 通信联系人：牛凯，（1976-）， 男，副教授，主要研究方向：迭代信道编译码、MIMO 信号处理与空时 编码、无线资源管理. E-mail: [email protected]

-1-

中国科技论文在线

http://www.paper.edu.cn

行 LVA。LVA 作为接收机可提高级联系统的性能。总体系统框架如图 1 所示。内码产生基 于 LVA 的最佳估计数据，外码通过 CRC 对译码结果进行校验。如果校验位正确，则该帧数 45 据可以接受；否则外译码器要求内译码器传输下一个最佳译码结果，再进行校验。直到外码 校验正确，否则超过最佳路径数量 L 时报错。很明显这样误帧率就会降低很多。 本论文的结构如下： 第一章介绍列表 Viterbi 译码算法， 第二章对并行 LVA 和串行 LVA 的算法复杂度进行分析和比较，第三章结合 CRC 校验给出级联码仿真结果并对结果进行相 应分析，第四章对论文进行总结。

50

图 1 级联码系统框架

1 列表 Viterbi 译码算法

本章主要介绍并行 LVA 和串行 LVA。 并行 LVA 要一次求出 L 条最佳路径； 而串行 LVA 55 利用前面所求到的所有最佳路径信息得到下一个最佳路径。下面先介绍下最基本的 Viterbi 译码算法。

1.1 传统 Viterbi 译码算法

N 状态卷积码格图如图 2 所示（如果不是全联结的，其中有些联结是不存在的）。设

序列长度为 M ，从状态 j ( t − 1 时刻)到状态 i ( t 时刻)的度量增量为 λt ( j, i )（如果格图上 60

j 到 i 没有连接则 λt ( j, i ) = ∞ ），从已知初始状态到状态 j （ t 时刻）的最小累积度量为

α t ( j ) 。Viterbi 算法的主要思想是在格图中找到最佳状态序列。设在 t 时刻到达状态 j 的最

佳状态序列的前一状态（ t − 1 时刻）为 σ t ( j ) ，Viterbi 算法可表述如下：

λt ( 0,0 )

αt (0)

λM ( 0,0 )

λt ( N − 1, N − 1)

图2

α t ( N − 1)

N 状态全联结的卷积码格图

65 A. 初始化(t=1，设初始状态为 0)

α1 ( j ) = λ1 (1, j ) ， σ1 ( j ) = 0 ，

0 ≤ j ≤ N −1

70 B. 循环（ 2 ≤ t ≤ M ，采用相关度量） 公式（1）

α t ( i ) = max ⎡ ⎣α t −1 ( j ) + λt ( j, i ) ⎤ ⎦，

0≤ j ≤ N −1

-2-

中国科技论文在线

σ t ( i ) = arg max ⎡ ⎣α t −1 ( j ) + λt ( j , i ) ⎤ ⎦，

0≤ j ≤ N −1

http://www.paper.edu.cn

0 ≤ i ≤ N −1

回溯： 75 最佳状态序列为 ( 0, S1 , S2 ,L S M −1 ,0 ) ，其中

公式（2）

St = σ t +1 ( St +1 ) ，

1 ≤ t ≤ M −1

公式（3）

1.2 并行列表 Viterbi 译码算法

并行 LVA 算法与传统 VA 算法基本相同， 只不过传统 Viterbi 算法是找一条最佳的路径， 80 而并行 LVA 是同时找前 L 条最佳的路径，如果采用相关度量，即在格图中寻找在任一时刻 到达任一状态的前 L 个度量最大的路径。然后采用回溯法得到 L 个最佳译码序列。该算法 需要保存的值为： L 个最佳度量（每个大小 N × M ）， L 个度量增量（每个大小 N × M ），

85

L 个最佳状态序列 （每个大小 1 × M ） 以及用于记录 L 个最佳序列次序的变量 （大小 1 × M ） 。 在每一时刻需要比较 2 × L 个相关度量的大小。因此可以看出，并行 LVA 需要的存储与计 下面介绍的串行 LVA 相对来说在存储与计算量方面要小许多。 算量是普通 VA 算法的 L 倍。

1.3 串行列表 Viterbi 译码算法

串行 LVA 最大的好处是只有在前面 l 个最佳序列都出错的情况下才需要计算第 l + 1 个 最佳序列。而且利用前面 l 个最佳状态序列的信息来计算第 l + 1 个最佳序列。这就避免了 PLVA 中很多不必要的计算。本论文采用通过求两个序列度量差来确定最佳序列的方法[5]。 90 该算法的主要思想是第二条最佳路径肯定是与第一条最佳路径在某些时刻离开， 然后又在后 面某一时刻汇入最佳路径。如图 3 所示。在 t 0 时刻可能次佳路径离开最佳路径，又在 t1 时 刻汇合，之后再也没有离开过。不可能出现次佳路径与最佳路径再次重合两次的情况。因此 我们可以求汇合于最佳路径每一状态的两条路径 （二进制情况下到达每一状态的前一状态只 有两个）的度量差值。差值最小的那个状态即为次佳路径与最佳路径汇合的状态。由此利用 95 前面得到的最佳路径的相关信息即可得到次佳路径。 求第三条最佳路径时如图 4 所示， 共有 两个候选路径， 一条是相对于第二条最佳路径的次佳路径 （即距离第二条最佳路径最近的路 径）；一条是扣除次佳路径后最佳路径的次佳路径。其次比较这两条路径到最终状态的累积 度量，较大的为第三条最佳路径。依次类推，求第 l + 1 条最佳路径时有 l 个候选路径，分别 由前 l 个最佳路径产生，选择这 l 个候选路径中累积度量最大的为第 l + 1 条最佳路径。 100 串行 LVA 可总结如下： 初始化： a. 已找到的最佳路径数 l = 1 。 b. 用 VA 算法得到最佳路径状态序列 BestPathState(大小 1 × M )，到每一时刻每一状态 的最佳路径度量 BestMetricCost( 大小 N × M ) ，以及到每一时刻每一状态的最佳路径 105 PastStateMatrix(大小 N × M ，Sij 表示从初始状态到状态 j ，时刻 i 的最佳路径的前一状态)。 c. 构造最佳路径状态矩阵 BestPathMatrix(大小 L × M 用于记录 L 个最佳路径)，与下一 候选路径的汇合点向量 MergeTime(大小 1× L ，初始为最后时刻 M )，用于记录沿 L 个最佳

-3-

中国科技论文在线

径度量值的矩阵 PathMetricMatrix(大小 L × M )。 110 循环(假设寻找第 l + 1 条最佳路径)：

http://www.paper.edu.cn

路径的路径度量差的 AbsoluteDiff(大小 L × M ，初始为无穷大)，以及用于记录每个最佳路

a. 计算沿第 l 条最佳路径的度量差值并存储在 AbsoluteDiff 的相应位置。 并分别计 b. 在 AbsoluteDiff 分别找前 l 行的最小的值并将其时刻存储在 MergeTime 中， 算穿过该时刻的候选路径的累积路径度量。 c. 在 b 中所求的 l 个候选路径的累积路径度量中选择度量最大的路径即为第 l + 1 个最 115 佳路径，设该路径为 l ′ ，在 MergeTime( l ′ )和 MergeTime( l )中存储汇合时刻。 d. 将相应候选路径的相应汇入点扣除（即设相应 AbsoluteDiff 为无穷大）。

t0

t1

图 3 第二条最佳路径的产生

120

图 4 第三条最佳路径的产生

2 算法复杂度分析

PLVA 算法的存储量如 1.2 所述。 因为 PLVA 算法要求在每一时刻都寻找前 L 个最佳路 125 径，故显然其算法复杂度存储量是普通 VA 算法的 L 倍。而利用 1.3 中所述的 SLVA 算法需 要存储所有中间计算，即为了找到第 l + 1 条最佳路径，需要计算沿第 l 条最佳路径的度量差 值，即 M 个减法。然后还需分别找出这 l 个度量差值中的最小差值，即 l × M 个比较大小。 即进行 l 次比较。 即在 SLVA 算法中为了寻找第 l + 1 再比较这 l 个最小差值中度量最大的值， 条最佳路径，共需要进行 M + l × M + l 次减法与比较。而在 VA 算法中，找到每一时刻的 130 最佳路径时只需进行两次加法与比较(输入为二进制情况下)。 具体计算 SLVA 算法的复杂度 是很困难的，因为 SLVA 只有在外编码器要求的情况下才会产生相应数量的路径。因此 卷积码寄存器个数以及信噪比等。 当帧长 M SLVA 的复杂度取决于外编码器类型、 帧长 M 、

-4-

中国科技论文在线

的 SLVA 提供的最佳路径数也相应增加。 135

http://www.paper.edu.cn

增加时，为了检测错误，需要的最佳路径数也会增加；信噪比降低时，找到正确路径所需要

3 仿真结果

本论文采用外码为 CRC 校验，内码为卷积码的级联结构。CRC 校验的基本原理为在发 送端根据信息比特与相应的 CRC 生成矩阵计算出 CRC 校验位， 置于信息比特的后面进行内 编码、传输、译码；在接收端根据收到的信息序列重新计算出 CRC 校验序列，与接收到的 CRC 校验序列进行比较，如果两个 CRC 校验序列不同，则说明该帧数据传输出现错误。

140

本节的仿真结果条件为：卷积码生成矩阵为[27；15] (八进制表示)，CRC 生成矩阵为 [0x8005]。 输入序列帧长为 512(包括 4 个尾比特和 CRC 检验的 16 比特)。 下面分别仿真 PLVA 与 SLVA 算法并将其与传统 VA 算法性能进行比较。

3.1 并行 LVA 误帧率

10

0

10 Frame Error Rate

-1

VA PLVA L = 2 PLVA L = 4 PLVA L = 8 PLVA L = 16

10

-2

10

-3

10

-4

10

145

-5

4

4.5

5

5.5 6 Eb/N0(dB)

6.5

7

7.5

图 5 外码为 CRC 检验，AWGN 信道，PLVA 的误帧率

3.2 串行 LVA 误帧率

-5-

中国科技论文在线

10 10 Frame Error Rate 10 10 10 10 10

150

0

http://www.paper.edu.cn

-1

-2

VA SLVA L = 2 SLVA L = 4 SLVA L = 8 SLVA L = 16

-3

-4

-5

-6

4

4.5

5

5.5 6 Eb/N0(dB)

6.5

7

7.5

图 6 外码为 CRC 检验，AWGN 信道，SLVA 的误帧率

3.3 结果分析

由图 5 和图 6 可以看出，PLVA 和 SLVA 在性能上是几乎相同的，并且 L>1 的 LVA 算 法性能要明显优于传统 Viterbi 算法。在误帧率为10−4 时，L=16 的列表 Viterbi 算法相对于 155 传统 Viterbi 算法可取得 1.3dB 的增益，信噪比越高，这种增益也越明显。由于仿真的帧长 比较长(512)，故搜索的最佳路径数不同时，性能差异是很明显的。例如在误帧率为10−4 时， L=16 的列表 Viterbi 算法相对于 L=2 的列表 Viterbi 算法可取得 0.7dB 的增益。 下面从信号距离方便分析 LVA 算法性能优于普通 VA 算法的原因。 VA 算法的性能主要是由最容易混淆的两个信号(输出序列)决定的。 在 AWGN 信道中相 160 当于两个信号(码字)的最小欧氏距离。设 x , y 为两个码字序列，该编码相应星座图的最小欧 氏距离可表示为

r r

r r Dmin = min r r x− y

x≠ y

公式(4)

L=2 的 LVA 有 3 个候选序列 x , y, z ，这三个码字组成一个三角形，每边长度至少为

r r r

r Dmin 。 如图所示， 误码率主要是由从 x 到 Ο 的距离 Deq Ο 为该三角形重心(三条中线的交点)，

165 来决定的。LVA(L=2) 相对于 VA(L=1)的编码增益如公式(5)所示

⎛ D eq ⎞ 10 log10 ( G ) = 10 log10 ⎜ ⎟ , ⎝ Dmin 2 ⎠ D eq > Dxy 2 > Dmin 2 , 10 log10 ( G ) > 0

2

公式(5)

-6-

中国科技论文在线

r y

http://www.paper.edu.cn

Ο

r x

170 的几何运算得到 Deq = 2 Dmin

图7

D eq

r z

L=2 的 LVA 的信号星座图

最坏的结果是三个信号点之间的距离都相等并且等于 Dmin ，此时 Deq 最小，可由简单

3 。依次类推, LVA 的性能要优于传统 VA 算法。Seshadri

已推出一般情况下的性能增益[4]。

4 结论

175 本文讲述了产生多个有序的最佳译码序列的并行与串行两种列表 Viterbi 算法。并给出 了与 CRC 校验相结合的级联编码系统在 AWGN 信道下分别用 PLVA 和 SLVA 进行译码的 性能仿真。根据仿真结果可以知道，在误帧率为10−4 时，L=16 的列表 Viterbi 算法可取得 1.3dB 的增益。 本文只讲述了与 CRC 校验相结合的级联码系统， LVA 算法还可与 RS 码、 FEC/ARQ 算 180 法相结合，下一步的工作是将 LVA 算法与其他的编码方式相结合，来研究其译码性能。 列表译码算法还可应用于信道估计[6]，语音识别[7]，以及语音与信道联合译码[8]。

[参考文献] (References) 185

[1] Christiane Nill and Carl-Erik W.Sundberg, List and Soft Symbol Output Viterbi Algorithm: Extensions and Comparisons IEEE Trans. Inf. Theory, 1995, 277-286 [2] G.D.Forney,Jr.,Convolutional Codes: Maximum Likelihood Decoding, Information Control, 1974, 25:222-266 [3] H.Yamamoto and K.Itoh, Viterbi Decoding Algorithm for Convolutional Codes with Repeat Request, IEEE Trans. Inf. Theory, 1980, IT-26 [4] Nambirajan Seshadri, Carl-Erik W.Sundberg, List Viterbi Decoding Algorithm with Application, IEEE Trans, 1994, 42():313-323 [5] T.Hashimoto, A List-Type Reduced-Constraint Generalization of the Viterbi Algorithm, IEEE Trans. Inf. Theory, 1987, IT-33 [6] N.Seshadri, Joint Data and Channel Estimation Using Fast Blind Trellis Search Techniques, IEEE Trans, 1994, 1659-1663 [7] C.H.Lee and L.R.Rabiner, A Network-Based Frame Synchronous Level Building Algorithm for Connnected Word Recognition,IEEE Int. Conf. Acoustics, Speech and Signal Processing, 1988, 410-413 [8] W.C.Wong, N.Seshadri, C-E.W.Sundberg, Estimation of Unreliable Packets in Sub-band Coding of Speech, Proceedings of the IEEE, 1991, 138(1):43-49

190

195

-7-