维特⽐译码器（ViterbiDecoder）硬件架构（⼆）--卷积码解码算法
1.⽹格图(Trellis Diagram)
⽹格图(Trellis Diagram)是卷积解码⽤到的概念，是理解解码过程的基础。⽹格图是由按时间顺序排列的状态结点矩阵， 每⼀列代表当前时刻的所有状态，最左侧第⼀列代表初始状态(t=0)，第⼆列代表第⼀个输⼊进⼊编码器后的转移状态。红⾊路径表⽰输⼊是0时的转移路径，蓝⾊表⽰输⼊为1时的转移路径。如下图所⽰，
t=1时刻，只有两个从初始状态过来的转移路径，只存在2个可能的状态；
t=2时刻，从t=1向t=2转移存在四个路径，此刻存在四种可能状态。
t=3时刻，从t=2过来的转移路径有8条。
以此类推形成整个⽹格图(Trellis Diagram)
2.⽤⽹格图表⽰编码过程
如下图所⽰，编码器初始状态为 state=‘00’,
t=1，输⼊bit为1，⾛蓝⾊加粗线段所⽰的转移路径，转移后的状态为state= ‘10’， 编码输出为 ‘11’。t=2，输⼊bit为1，转移路径在上图中⽤蓝⾊加粗线段表⽰，转移后的状态为state= ‘11’ ， 编码输出为 ‘
01’。t=3，输⼊bit为1，转移路径在上图中⽤红⾊粗线表⽰，转移后的状态为state=‘11’ ， 编码输出为 ‘01’。t=4，输⼊bit为0，转移路径在上图中⽤蓝⾊粗线表⽰，转移后的状态为state= ‘11’ ， 编码输出为 ‘00’。
以此类推，可以形成编码过程的状态转移路径，也称幸存路径。
3. 解码过程
3.1 理想状态下的解码
卷积码的编码过程与⽹格图中的⼀条路径对应，即接收端接收到的序列的编码过程与⽹格图中的路径⼀⼀对应。当序列长度为L时，⽹格中有2条不同的路径和编码器的2种输⼊序列对应。在⽹格图中，每个状态转移的过程中都会输出编码码字。译码器建⽴和编码器相同的⽹格图， 据此查询可得到解码码流。
理想状况下，假设在传输过程中没有错误发⽣，在接收端，根据已经存在的⽹格图很容易解码得到原始⽐特流。
以tail-bits卷积码为例，假如接收端收到的⽐特流为’1101010001’, 先按2 bit宽度分组：11 01 01 00 01，解码过程如下：L L
1. 从t=0的初始状态开始，tail-bits编码器的初始状态为’00’
2. 查询输出为11时的转移路径，如下图粗线标志，此时编码器输⼊bit为1才能⾛该转移路径，因此可得到解码的第⼀bit:1
3. t=1时，状态为‘10’，根据接收到的第⼆组‘01’，查询从该状态出发的两条转移路径
4. 只有输⼊为0时，才能得到‘01’的输出，因此可得到此刻的转移路径，把其他⽆关路径删除。因此解码得到第⼆⽐特为0.
5. 以此类推，可在⽹格图上得到完整的状态转移路径及所有解码数据：11011.
现实中不会存在这种理想状态，信号经过复杂信道后均会引⼊不同程度错误，因此在接收端不会真正使⽤这种解码算法。
3.2 Viterbi 译码算法原理
Viterbi算法 是CDMA之⽗，⾼通公司的创始⼈之⼀Andrew J. Viterbi在1967年提出的，它是基于卷积码⽹格图的最⼤似然译码算法。最⼤似然译码 的⼀种基本想法是：把已接收序列与所有可能的发送序列做⽐较，选择其中码距最⼩的⼀个序列做为发送序列。如果发送L组信息⽐特对于(n，k) 卷积码来说，⽹格图上可能发送的序列有2 个，译码器需存储这些序列并进⾏⽐较，以到码距最⼩的那个序列。当传信率和信息组数L 较⼤时，使得译码器难以实现。Viterbi算法则对上述最⼤似然解码做了简化，成为了⼀种实⽤化的最⼤似然译码算法。它不是在⽹格图上⼀次性⽐较所有可能的2 条路径（序列），⽽是接收⼀段，计算和⽐较⼀段，选择⼀段有最⼤似然可能的码段，从⽽达到整个码序列是⼀个有最⼤似然值的序列。译码过程类似于动态规划的过程。
3.3 Viterbi 译码中的⼏个概念
kL kL
分⽀度量（BM, Branch Metric），对于⽹格中每个路径，分⽀度量表⽰其对应的输出码字与接收到的码字之间的差距。
路径度量（PM，Path Metric） ⽹格中每个状态节点⽽⾔，对应所有到达该节点所⾛过的最有可能路径的分⽀度量值的累计结果。Viterbi译码过程的关键是，译码器可以使⽤分⽀度量和先前计算的状态路径度量递推地计算当前状态的路径度量.
硬判决(Hard decision) 是指接收端根据其判决门限对接收到的信号波形直接进⾏判决后输出0或1，也就供给译码器作为译码⽤的每个码元只取0或1两个值，以序列之间的汉明距离作为度量进⾏译码。适⽤于⼆进制对称信道（BSC）.decoder
软判决(Soft decision) 是指接受端对采样点直接输出模拟量，进⾏多电平量化（不是简单的0、1两电平量化）形成多⽐特的数字量，然后送往译码器，即编码信道的输出是没有经过判决的“软信息”。软判决译码器以欧⼏⾥德距离作为度量进⾏译码，软判决译码算法的路径度量采⽤“软距离”⽽不是汉明距离，最常采⽤的是欧⼏⾥德距离，也就是接收波形与可能的发送波形之间的⼏何距离，是⼀种适合于离散⽆记忆信道(DMC)的译码⽅法。⽬前，通⽤的量化电平为8电平（3 bit量化）和16电平（4 bit量化），再⾼的话，只能增加译码器复杂度，⼏乎没有性能的提⾼。除了度量的计算以外，软判决算法与硬判决算法在结构和过程上完全相同。⼀般⽽⾔，由于硬判决译码的判决过程损失了信道信息，软判决译码⽐硬判决译码性能上要好约2 dB。
3.4 Viterbi 译码过程
在当前时间t，对每个状态进⾏：
1. 计算分⽀度量BM：即计算进⼊该状态的两个路径的分⽀度量(BM)，即接收到的码元与两个路径对应的输出码元之间的汉明距离(硬判
决)或欧⼏⾥得距离(软判决)。
2. 计算路径度量PM：把两个路径的BM同各⾃对应的t-1时刻状态所存储的状态度量进⾏求和，得到t时刻的两个路径度量PM。
3. 选取幸存路径： ⽐较两个路径度量PM，选取并保留最⼩的作为t时刻的状态度量，同时保留与之对应的路径作为形成路径。如两个相
等，则任选其⼀作为幸存路径。
4. 回溯(Traceback): 从各个状态的形成路径中选取出状态度量最⼩的⼀条，顺次向前进⾏回溯，并输出译码结果。
第2步第3步简称加⽐选(ACS), 是译码的核⼼步骤。
3.4 Viterbi 译码所需的存储
每个状态需要记录当前累计的路径度量PM(可成状态度量)，所以(n, k, L) 卷积码的译码需要2 个寄存器记录状态度量。
如果回溯深度为N， 则每个时刻需要记录每个状态的幸存路径，
则需要深度为N，宽度为2bit的存储器存储幸存路径。
参考⽂献
1.
2.
3.
本博客所有⽂章均同步发表于L L

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。