信息论基础与编码 (21)

卷积码的译码卷积码的译码卷积码的译码可分为两大类型卷积码的译码可分为两大类型:代数译码代数译码与与概率译码概率译码。(1)(1)代数译码代数译码：从码的代数结构出发，以一个约束度的接收：从码的代数结构出发，以一个约束度的接收序列为单位，对该接收序列的信息码组进行译码。大数序列为单位，对该接收序列的信息码组进行译码。大数逻辑译码是代数译码的主要方法。逻辑译码是代数译码的主要方法。代数译码中，用代数译码中，用矩阵矩阵描述比较方便。描述比较方便。(2)(2)概率译码概率译码：从信道的统计特性出发，以远大于约束度的：从信道的统计特性出发，以远大于约束度的接收序列为单位，对信息码组进行最大似然的判决。接收序列为单位，对信息码组进行最大似然的判决。维维特比译码特比译码和和序列译码序列译码是其最主要的方法。是其最主要的方法。在维特比译码中，用在维特比译码中，用网格图网格图来描述码的译码更为方便。来描述码的译码更为方便。卷积码的最大似然译码卷积码的最大似然译码维特比算法维特比算法 卷积码的译码就是搜遍网格图找出最可能的发码序列。搜寻网格图时所用的相似性度量可以是汉明距离,这种最小距离准则的译码算法叫卷积码的最大似然译码。以一个具体例子来说明维特比算法的执行过程。例例：某：某(2,1,2)卷积码，卷积码，其编码器结构如图其编码器结构如图所示，设发送的所示，设发送的码字序列是码字序列是C=(00,00,00,00,00,00,00,),接收的码字序列接收的码字序列是是R=（10,00,01,00,00,00,00,）,试用维特比算法译码。试用维特比算法译码。编码器状态的定义编码器状态的定义状态状态S000S110S201S311状态转移图状态转移图卷积码的状态转移图卷积码的状态转移图卷积码的网格图卷积码的网格图红实线红实线表示输入为表示输入为0 0时产生的转移分支；时产生的转移分支；黄虚线黄虚线表示输入为表示输入为1 1时产生的转移分支。时产生的转移分支。7 译码器接收到译码器接收到 R 序列后，按序列后，按最大似然法则最大似然法则力图力图寻找编码器在网格图上原来走过的路径，也就寻找编码器在网格图上原来走过的路径，也就是寻找具有是寻找具有最大度量的路径最大度量的路径；因此，译码器必须寻找因此，译码器必须寻找与与 R 有最小距离的路径有最小距离的路径，即计算和寻找即计算和寻找 mind(R,Cj)。最大似然译码最大似然译码/最小距离译码最小距离译码8在起始的第在起始的第0个到第个到第2个时刻内，编码器根据输入的信息元不个时刻内，编码器根据输入的信息元不同从同从S0状态向四个可能的状态之一行进；状态向四个可能的状态之一行进；本例假定信息序列长为本例假定信息序列长为L=5个信息组，最后个信息组，最后 m=2个个信息组是信息组是全全0，所以在篱笆图上的最后两个时刻向，所以在篱笆图上的最后两个时刻向 S0 状态返回；状态返回；篱笆图上各连续分支组成了可能的路径，它们代表了各种可篱笆图上各连续分支组成了可能的路径，它们代表了各种可能的码序列；能的码序列；由于可能的输入信息序列有由于可能的输入信息序列有 2kL=25=32 个，可能的路径有个，可能的路径有32条；条；每个分支上的数字表示输出的子码。每个分支上的数字表示输出的子码。维维特比译码的基本原理特比译码的基本原理9译码器译码器不是在篱笆图上一次就计算和比较不是在篱笆图上一次就计算和比较 2Lk 条路径，而是接收一段，就计算、比较一段，条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可能从而在每个状态时，选择进入该状态的最可能的分支。的分支。维特比译码的基本思想：将接收序列维特比译码的基本思想：将接收序列 R 与篱与篱笆图上的路径逐分支地比较笆图上的路径逐分支地比较，然后，然后留下与留下与 R 距离最小的路径，称为幸存路径，而去掉其余距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐分支地延长可能的路径，并将这些幸存路径逐分支地延长并存储起来。并存储起来。幸存路径的数目等于状态幸存路径的数目等于状态数。数。维特比译码工作原理维特比译码工作原理假设译码器的初始状态为全假设译码器的初始状态为全0；第一步第一步：接收序列的第接收序列的第0个分支个分支 R0=10 进入译码进入译码器。从器。从 S0 状态有两个分支，它们是状态有两个分支，它们是 00 和和 11，R0与这两个分支比较，比较的结果和到达的状态与这两个分支比较，比较的结果和到达的状态如图和表中所如图和表中所示：示：每个状态每个状态/节点都有两个存储器：节点都有两个存储器：路径存储器：存储该状态的部分路径存储器：存储该状态的部分路径；路径；路径值存储器：存储达到该状态路径值存储器：存储达到该状态的部分路径值的部分路径值(累加距离累加距离)。第二步第二步：进入：进入译码器的接收码组译码器的接收码组 R1=00 和此时刻出和此时刻出发的四条分支比较，比较结果和达到状态发的四条分支比较，比较结果和达到状态如图、表如图、表所所示：示：从第一步到第二步共有四条路径，到从第一步到第二步共有四条路径，到达达S0,S1,S2和和S3。在第二个时刻以前。在第二个时刻以前译码器不做任何选择和判决。译码器不做任何选择和判决。每个状每个状态的路径存储器态的路径存储器存储下此时刻的幸存存储下此时刻的幸存路径：路径：0000,0011,1110,1101；每个状态的路径值存储器每个状态的路径值存储器存储了此时存储了此时刻到达该状态的幸存路径累加值刻到达该状态的幸存路径累加值(累累加距离加距离)。12 第三步第三步：第二个接收码组第二个接收码组 R2=01 进入译码器，从篱笆图上可见，进入译码器，从篱笆图上可见，从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组 R2 与进入每个状态的两个分支进行比较和判决，选择一个累加距离与进入每个状态的两个分支进行比较和判决，选择一个累加距离（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸存路径共四条，比较和判决的过程如下：存路径共四条，比较和判决的过程如下：部分部分路径路径 00,00,00为到达为到达 S0 状态的幸存路径；状态的幸存路径；部分路径部分路径 00,00,11为到达为到达 S1 状态的幸存路径；状态的幸存路径；部分路径部分路径 11,01,01为到达为到达 S2 状态的幸存路径；状态的幸存路径；部分路径部分路径 00,11,01为到达为到达 S3 状态的幸存路径状态的幸存路径。按照上述方法，接收序列的诸码组依次进入按照上述方法，接收序列的诸码组依次进入译码器，每个时刻进入一个码组，沿着篱笆图对译码器，每个时刻进入一个码组，沿着篱笆图对每个状态按部分路径值（累加距离）的大小，选每个状态按部分路径值（累加距离）的大小，选择择一条幸存路径一条幸存路径。在每个状态上进行判决时，可。在每个状态上进行判决时，可能出现进入这一状态的能出现进入这一状态的两条路径两条路径的的距离值相同距离值相同，这时可以这时可以任选其一任选其一，因为对以后的判决而言，无，因为对以后的判决而言，无论选择那一条路径，累加距离是相同的。论选择那一条路径，累加距离是相同的。151819 对对本例而言，按上述算法进行到本例而言，按上述算法进行到第八步后第八步后，四，四条路径的前面分支都合并在一起。所以，只要译码深度条路径的前面分支都合并在一起。所以，只要译码深度足够，就可达到较低的错误概率足够，就可达到较低的错误概率。依此类推。依此类推，对接收序，对接收序列中的诸码组进行译码。列中的诸码组进行译码。维特比译码的一次运算：维特比译码的一次运算：计算每个输入分支的度量值（分支距离、累加距离）计算每个输入分支的度量值（分支距离、累加距离）；比较各部分路径的度量值，选择一条作为幸存路径比较各部分路径的度量值，选择一条作为幸存路径。20在在第第 j(j=L)个时刻以前，译码器计算所有的长个时刻以前，译码器计算所有的长为为L 个个分支的部分路径值，对进入分支的部分路径值，对进入 2kL 个状态的每一条部分路个状态的每一条部分路径都保留。径都保留。第第 L 个时刻开始，对进入每一个状态的部分路径进个时刻开始，对进入每一个状态的部分路径进行计算，这样的路径有行计算，这样的路径有 2k 条，挑选具有最大部分路径条，挑选具有最大部分路径值的部分路径为幸存路径，删去进入该状态的其它路径，值的部分路径为幸存路径，删去进入该状态的其它路径，然后，幸存路径向前延长一个分支。然后，幸存路径向前延长一个分支。重复重复第二步的计算、比较和判决过程。若输入接收序第二步的计算、比较和判决过程。若输入接收序列长为列长为 (l+L)k，其中，后，其中，后 L 段是人为加入的全段是人为加入的全0段，则段，则译码一直进行到译码一直进行到 (l+L)个时刻为止。个时刻为止。若进入某个状态的部分路径中，有两条的部分路径值相若进入某个状态的部分路径中，有两条的部分路径值相等，则可任选其一作为幸存路径。等，则可任选其一作为幸存路径。维特比算法的步骤维特比算法的步骤21维特比译码技术在目前已作为一个标准技术在宇航和卫维特比译码技术在目前已作为一个标准技术在宇航和卫星通信系统中获得广泛应用星通信系统中获得广泛应用。维特比译码算法是一种最大似然译码算法，由于译码的维特比译码算法是一种最大似然译码算法，由于译码的计算量与计算量与 L 成指数增长，所以适用于维特比算法的码，成指数增长，所以适用于维特比算法的码，编码存储编码存储 L 都不太大，从而码的自由距离不能很大，都不太大，从而码的自由距离不能很大，维特比译码器的输出误码率不能做的很低，一般只能维特比译码器的输出误码率不能做的很低，一般只能达到达到 10-510-6 的量级的量级。随着大规模集成技术的发展和计算机的应用，维特比译随着大规模集成技术的发展和计算机的应用，维特比译码在功率受限、误码率要求为中等的情况下，广泛被码在功率受限、误码率要求为中等的情况下，广泛被作为标准技术应用。作为标准技术应用。维特比译码的应用维特比译码的应用