对于卷积码的解码方法中，Viterbi译码算法是被应用的广泛的译码算法。是一种似然译码算法(MLD，Maximu LikelihoodDecoding）。它接收输人的信息序列后，寻找任何可能的路径值，而后找一条路径值当作解码输出。为了描述Viterbi译码算法，常用网格图（Trellis Diagram，根 据时间的增加将网格图扩充所得到的图形，如图1所示）来表示演算过程。网格图中的节点，代表编码器中的各个状态， 而在其中的分支代表编码器的所有可能的状态转移情况。图1显示为（2，1，3）网格图。
图1 （2，1，3）网L=5时的网格图
此图是L＝5时，该（2，1，3）码的状态转移时间关系图，总共有L＋m＋1个时间单位（节点），以0至L＋m标号，其中m ＝k￣1为编码存储。若编码器从SO（00）状态开始，并且结束于SO状态，则的m＝2个节点（0，1），相应于编码器 由SO状态出发往各个状态行进，而m2个节点（6，7），相应于编码器由各状态返回到SO状态。因而，在开始和m 个时间单位，编码器不可能处于任意状态中，而只能处于某些特定状态（如SO，Sl）中之一，仅仅从第m（2）至第L（5 ）节点，编码器可以处于任何状态之中（即4个状态SO、S1、S2、S3中之任一个）。编码器从全0的SO状态出发，叉 回到SO状态时所输出的码序列，称为结尾卷积码序列。因此，当送完L段信息序列后，还必须向编码器再送入m段全0序列 ，以迫使编码器回到SO状态。
网格图中每一状态有两个输入和两个输出分支。在某一节点i，离开每一状态的虚线分支（下面分支），表示输人编码 器中的信息子组ml＝1；而实线分支（上面分支）表示此时刻输人至编码器的信息子组ml＝o；每一分支上的2（nO）个数 字，表示第i时刻编码器输出的子组01=（cl（1），cl（2）），因此网格图中的每一条路径都对应于不同输入的信息序 列。由于所有可能输人的信息序列共有2k1条不同的路径，相应于编码器输出的2k1个码序列。
Viterbi译码算法考虑的是如何去掉不可能成为似然选择对象的格形图上的路径，即如果有两条路径到达同一个状 态，则具有度量的路径被选中，称为幸存路径（survtvmgpath）。对所有状态都将进行这样的选路操作，译码器不 断在格形图上深人，通过去除可能性的路径实现判决。较早地抛弃不可能的路径从而降低了译码器上实现的复杂度 。Omura在1969年证明了Viterbi译码算法其实就是似然算法。也就是说，选择路径可以表述为选择具有似 然度量的码字，或者选择具有距离的码字。
Viterbi译码算法中硬判决Viterbi译码和软判决Viterbi译码的性能差异。由于对模拟信号的处理比较复杂，因此在软 判决译码之前，一般先要对接收序列进行量化。实际上，可以将硬判决译码看做软判决译码的特殊情况，即采用了1比特 量化。而软判决采用的是多比特量化。在理想的软判决情况下，信道接收值直接用于译码器。相应地，卷积码的Viterbi 译码也有硬判决Viterbi译码和软判决Viterbi译码两种译码方式。从仿真的结果来看，对于高斯信道来说，8级量化比2级量 化的信噪比提高了大约2dB，这说明了为了获得相同的比特差错性能，8级软判决需要的Ec/No比硬判决低2dB，模拟装置 比2级量化的性能提高2．2dB；因此，8级量化比无穷级量化的性能损失了仅0.2dB。由于这个原因，量化级超过8级只能 获得较少的性能提高。因此，软判决Viterbi译码算法一般采用3比特量化，它比硬判决Viterbi算法所要处理的数据量要 多3倍。可见，软判决译码的代价是译码器所需存储量的增大。
卷积码的编码码字序列c是输入信息序列m与编码器冲激响应g卷积的结果。码字序列c经过信号传输映射并送至有噪信道 传输，在接收端得到接收序列r。Viterbi译码算法就是利用接收序列r，根据似然估计准则来得到估计的码字序列y 。即寻找在接收序列r的条件下使条件概率p（r/y）取得值时所对应的码字序列y。序列y必须取自许用码字集合。
对于码率为R的（no，k0，m）卷积码，在每个时间单位并行输人k0个码元，同时并行输出no个码元。一般输人序列表示为：
其中下标中的m表示卷积码编码器中寄存单元的个数，L表示输入信息序列的长度。事实上，增加的m个码元为零码 元，目的是得到结尾码字，即使编码器在编码结束时的状态回到初始全零状态。相应的接收序列表示为：
类似地，接收序列r和估计序列y也有类似的表示形式：
对于似然译码，Viterbi算法选择使p（r/y）的y作为估计序列。如果假设信道是无记忆的，则噪声对每一位 发送码元的影响都是独立（不相关）的，从而条件概率p（r/y）就等于每个独立同分布接收码元条件概率的乘积，即
上式即为给定接收序列r的条件下序列y的似然函数。由于对数函数lg是一个单调递增函数，因此使p（r/y）化就等 价于化lg p（r/y）。为降低似然函数的计算复杂性， 常采用如下定义的对数似然函数：
为简化上式中的对数函数求和运算，可以定义如下码元度量：
其中常数a和b的选取原则是使码元度量值是或者尽可能接近于某个小的正整数。在BSC信道或者采用硬判决译码时可以 用不同的方式定义常数a和b：
在这种情况下，Viterbi算法就是在编码格图上选择与接收序列r之间汉明（Hamming）距离的码字序列作为译码输出。对于一般的信道，可以按照误差化的原则选择常数a和b的值来获得可接受的码 元度量。根据码元度量的定义可以定义格图路径度量：
这意味着在编码格图上译码估计码元序列y与接收码元序列r之间的总代价。对于BSC，即两个序列之间的汉明距离。
Vitervi算法就是利用卷积码编码器的格形图来计算路径度量。算法首先给格图中的每个状态（结点）指定一个部分路 径度量值。这个部分路径度量值由从起始时刻t＝0的So状态到当前各个时刻的So状态决定。在每个状态，选择达到该状 态的具有“”部分路径度量的分支。
的部分路径度量根据前述常数a和b的选择不同，可以是“”度量，也可以是“”度量。按照所采用的度 量，选择满足条件的部分路径作为幸存路径，而将其他达到该状态的分支从格图上删除。viterbi算法就是在格形图上选 择从起始时刻到终止时刻的惟一幸存路径作为似然路径。沿着似然路径，从终止时刻回溯到开始时刻，所走过 的路径｜对应的编码输出就是似然译码输出序列。
硬判决viterbi算法可以按照如下步骤实现。
（1）首先以Skj代表编码器格图中第t时刻的状态Sk。给格形图中的每个状态指定一个度量呈V（Skj）。
（2）初始化。在时刻t＝0，V（So,o）＝0，其他时刻V（Skj）为无穷大。
（3）t+1→t。计算在t时刻到达Sk状态的所有路径的部分路径度量，即首先找到时刻t的分支度量，这可以通过计算汉 明距离来完成。其次，计算t时刻的部分路径度量。
（4）将V（Skj）设置为t时刻到达Sk状态的“”部分路径度量。通常情况下，的部分路径度量是具有度 量值的部分路径度量；如果有多个的部分路径度量，可以选择其中任意一个。
（5）存储的部分路径度量及其相应的幸存路径和状态路径。
（6）若t＜L＋m－1，返回（3）。
viterbi算法得到的终幸存路径在格形图中是惟一的，也就是似然路径。
下面给出硬判决viterbi算法实现卷积码译码的一个简单例子。考察（2，1，3）卷积码。若输入序列为m＝（1011100 ）；相应的码字序列为c＝（11，10，00，01，10，01，11）。如果经过BSC信道传输后得到的接收硬判决序列为F（10， 10，00，01，11，01，11）。其中两位出现了错误，下面考察通过viterbi算法以汉明距离为准则实现译码，从而获 得估计信息序列m和码字序列c。
图2给出了在编码器格形图上根据接收序列进行Viterbi译码的过程。图中用粗线画出了在每一时刻进入每一个状态的 幸存路径。在t＝2时刻以前，进人每一个状态的分支只有一个，因此这些路径就是幸存路径；从t=2时刻开始，进入每一 个状态结点的路径有两条，按照距离准则，选择一条幸存路径。在t＝7时刻，只剩下惟一的一条幸存路径，即 似然路径，与这条似然路径相对应的码字就是译码输出，显然，根据前述该输人序列的编码码字，可知（II，10，00， 01，10，01，II）；相应的译码输出信息序列为（1011100）。
图2 译码过程流程
表1 进入每个状态节电的幸存路径的部分度量值
通常，实现软判决viterbi算法是利用欧几里德距离度量代替硬判决时的汉明距离度量，其中接收码元采用多比特量化 ；接收机并不是将每个接收码元简单地判决为0或者1，而是使用多比特量化或者直接使用未量化的模拟信号。理想情况 下，接收序列r直接用于软判决viterbi译码器。软判决viterbi译码器的工作过程与硬判决viterbi译码器的工作过程相 似，惟一的区别是在度量中以欧几里德距离的平方代替汉明距离。
从实现方法来看，硬判决viterbi译码算法和软判决viterbi译码算法区别主要在加比选部件（ACS，Addition Comparison Selection），路径计算部件（BMG；Bran。h Metric Generation）以及度量储存模块或者寄存器模块的不 同。
Viterbi译码流程主要有下面几个部分。
（1）量化。将接收机接收的模拟信号转化成数字信号。
（2）码同步。检测码元帧的边界以及码元标志。
（3）分支度量计算。计算各个状态的接收码元和本地码元的汉明距离。
（4）状态度量更新。用各个状态新的路径度量代替前一时刻的路径度量。
（5）幸存路径存储。将Viterbi译码所需的网格图上所走过的路径记录下来。
（6）输出判决。根据幸存路径存储的信｀崽，产生译码序列的输出。
图3显示了Viterbi译码算法的流程，它是根据上述的几个部分来进行的。
整个译码器按照功能主要分成7个模块。系统框图如图4所示，主要由路径计算模块（BMG，Branch Metric Generation ），加比选模块（ACS，Addition Comparison Selection），状态路径存储管理模块（MMU，Metric Memory Management Unit），路径回溯模块（TB，Traceback），路径存储模块（SMU，Survivor Memory Management Unit），输人输出模块 再加上一个控制电路模块组成。
图3 Viterbi译码算法流程
图4 Viterbi译码系统框图
输入输出模块：输入输出部分提供解码器与外部的接口。在无线通信中，接收端从信道中接收到信息序列，然后通过输 入端传入解码器。经过解码之后，得到的解码序列从输出端送出，在经过其他处理输出。
ACS模块：Add Compare Select模块，即“加比选”模块。它是Viterbi译码器中运算量的部分，大量的运算都是在 这个模块完成的。ACS接收原来的状态度量和当前的度量路径值，每一状态都有两条路径可以到达，对每一状态的两条路 径的对应值相加，将得到的两个结果进行比较，从中选取较小的一条，将它作为当前的状态度量。
BMG模块：Branch Metric Generator模块，即路径度量模块。这个模块计算每一时刻各个状态的路径度量的，在BSC信道 的硬判决Viterbi译码过程中，就是计算接收值与期望值之间的汉明距离。
TB模块：Traceback模块，路径回溯模块。这个模块当译码开始一段序列后，按照路径回溯算法，历经各个状态，得到 译码输出。
MMU模块：Metric Memory Management Unit，路径度量存储管理模块。这个模块主要负责对路径度量的存取进行管理， 为ACS模块提供所需的路径度量值以及按时更新路径度量。
SMU模块：Survivor Memory Management Unit，幸存路径存储管理模块。这个模块负责对幸存路径RAM进行管理，负责 幸存路径的存储和读取。
Control模块：控制电路模块，主要负责提供各种控制信号给各个模块，以保证时钟上同步，流水线不堵塞，提高系统 的并行能力。
由于在卷积码的译码过程中，Viterbi译码算法的复杂度和寄存器状态数成正比，与约束长度成指数增长关系。因此解 决计算复杂度大的问题是关键，所以整个译码器的重点在ACS模块、MMU模块、SMU模块和TB模块上。
基于DSP的Viterbi译码实现过程分为欧几里德距离计算、寻找短距离、计算累加距离、跟踪回溯路径、微分等步骤。
欢迎转载，信息来源维库电子市场网（www.dzsc.com）
免责声明: 凡注明来源本网的所有作品，均为本网合法拥有版权或有权使用的作品，欢迎转载，注明出处。非本网作品均来自互联网，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。
