信道编码理论

《信道编码理论》由会员分享，可在线阅读，更多相关《信道编码理论（52页珍藏版）》请在装配图网上搜索。

1、1第十二章第十二章 卷积码的概率译码卷积码的概率译码 （I）v卷积码的网格图表示卷积码的网格图表示v卷积码的概率译码：卷积码的概率译码：Viterbi译码算法译码算法v修正的修正的Viterbi译码算法译码算法滑窗滑窗状态缩减状态缩减2卷积码的卷积码的Trellis图表示图表示v 右图为右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生卷积编码示意图，其生成多项式矩阵和生成矩阵分别为成矩阵分别为:22( )1, 1DDDDG11 101111 101111 1011G3卷积码的卷积码的Trellis图表示图表示s0s1s2s3s0s1s2s3v状态图状态图Trellis图图4Viterb

2、i译码译码v若编码信息序列为若编码信息序列为 1011100，则编码过程即为在，则编码过程即为在Trellis图上寻找一条路径。图上寻找一条路径。5Viterbi译码译码v译码过程即为在译码过程即为在Trellis图上寻找一条路径，该路图上寻找一条路径，该路径对应的编码序列径对应的编码序列与接收序列之间有最大概率度与接收序列之间有最大概率度量：量：0max(|( )maxlog(|( ) 1,2,2k LjjjjPPjR CSR CS6Viterbi译码译码v 从第从第1时刻的全零状态开始（零状态初始度量为时刻的全零状态开始（零状态初始度量为0，其它状，其它状态初始度量为态初始度量为负无穷负无

3、穷）；）；v 在任一时刻在任一时刻t，对每一个状态只记录到达路径中度量最小，对每一个状态只记录到达路径中度量最小的一个（残留路径，的一个（残留路径，硬判决为汉明距离，软判决为欧氏距硬判决为汉明距离，软判决为欧氏距离离）及其度量（状态度量）；）及其度量（状态度量）；v 在向在向t+1时刻前进过程中，对时刻前进过程中，对t时刻的每个状态作延伸，即时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到在状态度量基础上加上分支度量，得到|S|2k条路径；条路径；v 对所得到的对所得到的t+1时刻到达每一个状态的时刻到达每一个状态的2k条路径进行比较，条路径进行比较，找到一个度量最大的作为残留路径；

4、找到一个度量最大的作为残留路径；v 直到码的终点，如果确定终点是一个确定状态，则最终保直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果。留的路径就是译码结果。7Viterbi译码译码v 在在BSC和和BIQO-DMC上，最大概率度量分别等效为最小上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量距离度量和最小欧氏距离度量 。v 距离度量更新公式距离度量更新公式 ：v Theorem：在：在Viterbi译码算法中，留选路径是有最大似然译码算法中，留选路径是有最大似然函数的路径。函数的路径。111111111 min(, ()min(, (), min

5、min(, (), tttttttttttttttttttsddd rc ssdd rc ssSSSRC SRC SRC SttttSSSS max(|( )maxlog(|( ) min, ( )PPdR C SR C SR C S8Viterbi译码译码第1个时刻接收子码10汉明距离d11第2个时刻接收子码10汉明距离dv Example: M=(1011100)，初始状态为全0的编码器输出序列为C=(11, 10, 00, 01, 10, 01, 11), 通过有噪信道后，接收序列为R=(10, 10, 00, 01, 11, 01, 11)119Viterbi译码译码第3个时刻接收子码

6、00汉明距离d213210Viterbi译码译码第4个时刻接收子码01汉明距离d3,43,43,31,5汉明距离d3331213311Viterbi译码译码第5个时刻接收子码11汉明距离d3,53,52,42,4汉明距离d3322331312Viterbi译码译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d3233223,43,43313Viterbi译码译码第7个时刻接收子码11汉明距离d2,5323301/000/101/110/110/011/14,44,43,414Viterbi译码译码保存的保存的幸存路径幸存路径为为：译码结果为：译码结果为：101110015Viterbi

7、译码译码收尾收尾v 最大似然序列译码要求序列有限，因此对卷积码来说，要最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。求能收尾。v 收尾的原则收尾的原则 在信息序列输入完成后，利用输入一些特定的比特，使在信息序列输入完成后，利用输入一些特定的比特，使|S|个状态个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成就变成只有一条残留路径只有一条残留路径，这就是最大似然序列。，这就是最大似然序列。v 非递归卷积码非递归卷积码 约束长度为约束长度为m+1的卷积码，只要在信息序列输入完成后的卷积码，只要在信息序列输入完

8、成后连续送入连续送入m个个0，即可使任一路径都到达最终的状态，即可使任一路径都到达最终的状态0。v 递归卷积码递归卷积码 可通过将输入值置成反馈值的负值，而使可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达个时钟后的状态到达0。16DDViterbi译码译码收尾收尾非系统非递非系统非递归码归码递归系统码递归系统码17Viterbi译码译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d323322Example (cont.): M=(10111); M=(1011100)18Viterbi译码译码第7个时刻接收子码11汉明距离d2,519Viterbi译码译码保存的保存的幸存路

9、径幸存路径为为：译码结果为：译码结果为：101110020软判决软判决Viterbi译码译码v基本思想：基本思想：为了充分利用信道输出符号的信息，提高译码可靠性，为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行把信道输出的信号进行Q电平量化，然后在输入电平量化，然后在输入Viterbi译码器。能适应这种译码器。能适应这种Q进制输入的进制输入的Viterbi译码器称为译码器称为软软判决判决Viterbi译码器译码器。v例子：例子：Q=4电平量化的信道比特度量：电平量化的信道比特度量：001021121121Viterbi译码的复杂度译码的复杂度v对信息序列长度为对信息序列长度

10、为L，信息符号取自，信息符号取自GF(p)，R=k/n，约束长度为，约束长度为m+1的卷积码。状态数为的卷积码。状态数为pkm因此对每个时刻要做因此对每个时刻要做pkm次次加比选加比选得到得到pkm个状态的残留个状态的残留路径；路径；每次加比选包括每次加比选包括pk次加法和次加法和pk-1次比较次比较。因此总运算量。因此总运算量约为约为Lpkm次加比选；次加比选；同时要能保存同时要能保存pkm条残留路径，因此需要条残留路径，因此需要Lpkm个存贮单个存贮单元。元。22Viterbi译码的特点译码的特点v 维特比算法是最大似然的序列译码算法；维特比算法是最大似然的序列译码算法；v 译码复杂度与信

11、道质量无关；译码复杂度与信道质量无关；v 运算量与码长呈线性关系；运算量与码长呈线性关系；v 存贮量与码长呈线性关系；存贮量与码长呈线性关系；v 运算量和存贮量都与状态数呈线性关系；运算量和存贮量都与状态数呈线性关系；v 状态数随分组大小状态数随分组大小k及编码存贮及编码存贮m呈呈指数指数关系。关系。23滑窗滑窗Viterbi译码算法译码算法v基本思想：基本思想：当状态数有限时，给定时刻的各状态残留路径在一定当状态数有限时，给定时刻的各状态残留路径在一定时间（时间（L）之前来自于同一状态的可能性随）之前来自于同一状态的可能性随L的增加而的增加而迅速趋近于迅速趋近于1。因此当前时刻各残留路径很可

12、能来自于。因此当前时刻各残留路径很可能来自于L时刻前的同一路径。时刻前的同一路径。24滑窗滑窗Viterbi算法实现算法实现v 在第在第t时刻，可以将时刻，可以将t-L时刻前的路径结果直接输出，而在时刻前的路径结果直接输出，而在存贮空间中不再保存存贮空间中不再保存t-L时刻前的内容。因此存贮量控制时刻前的内容。因此存贮量控制在在Lpkm。这里的。这里的L就被称做就被称做译码深度译码深度，不再随码长的增加，不再随码长的增加而增加。因而特别适合信息流的卷积码编译码。在这种情而增加。因而特别适合信息流的卷积码编译码。在这种情况下甚至况下甚至不需要对流分段加尾比特不需要对流分段加尾比特。v 显然，滑动

13、窗算法是一种准最优算法。但通常译码深度只显然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的要有编码约束长度的5到到10倍，其性能损失就可以忽略不倍，其性能损失就可以忽略不计了。计了。25缩减状态的缩减状态的Viterbi译码译码v由于运算量与由于运算量与k和和m呈指数关系，因此维特比译码呈指数关系，因此维特比译码算法一般只适合于算法一般只适合于k和和m较小的场合。大多数情况较小的场合。大多数情况下下k=1，m门限门限前向试探节前向试探节点，因此应考虑从反向试探节点另一个方向衍点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，生一个试探节点，因此要

14、回到反向试探节点，以便向前观察下一个最佳节点。以便向前观察下一个最佳节点。41Fano算法算法v先找一个最佳节点，大于门限，则前进并提高门先找一个最佳节点，大于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限。并提高门限，再向前找一个最佳节点，小于门限。42 Fano算法算法43堆栈堆栈(ST)算法算法v核心：存贮一组可能的路径，但每次只对当时认为核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。的最佳路径进行延伸，然后再重新排序。从码树图起始节点开始；从码树图起始节

15、点开始；将堆栈第一行中路径向各分支延伸，计算新度量；将堆栈第一行中路径向各分支延伸，计算新度量；删去第一行原存贮内容；删去第一行原存贮内容；将延伸后的各路径在堆栈中重新排序，找出度量量大的将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行；路径放在第一行；若第一行中的路径已达码树终点，则结束，否则回到步若第一行中的路径已达码树终点，则结束，否则回到步骤骤2。44ST算法的本质算法的本质v存贮一组可能路径；存贮一组可能路径；v每次只有最可能的（度量最大的）路径可以繁衍，每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径；同时删去父路径；v繁衍出的子路径与其它未繁衍的路径一起排

16、序；繁衍出的子路径与其它未繁衍的路径一起排序；v堆栈满时最坏路径被丢弃。堆栈满时最坏路径被丢弃。45序列译码的特点序列译码的特点v运算量与信道质量有关；运算量与信道质量有关；v需要输入缓冲器，其长度也与信道质量有关，有需要输入缓冲器，其长度也与信道质量有关，有溢出现象；溢出现象；v计算量与约束长度无关。计算量与约束长度无关。46TCM encoderRate k/(k+r)ConvolutionalencoderSelect one of2k+r subsetsSelect one of2m-k signals insubset S(ci)m+r bitsSignal mapperm bits

17、 persymbolSubset labelsequence ci(1)ia( )kia(1)kia()mia(1)ic( )kic()k ric(1)k ric S(ci)()m ric()(1)(.)m riiixf ccSignalsequencexi47TCMv For a trellis code C (of length n), the minimum squared Euclidean distance between two different sequences of signal points is referred to as its free squared Eucli

18、dean distance; i.e.,v The asymptotic coding gain (including shaping gain) is defined to be v where denote the minimum squared Euclidean distance between signal points in the uncoded scheme, and E and E(u) denote the average signal energies of the coded and uncoded schemes, respectively.22( )min, , (

19、or )nnfreemmmmm mdxxxxRCCC2free102( )( )min( )/10log/uudEdEC dB2( )minud 48TCM examplev The 4-state TCM encoder for 8-PSK TT8-PSKSignalSet(1)ic(2)ic(3)ic(1)ia(2)iaxi(3)(2)(1)iiicccc49Set partition of 8PSKA: 8-PSK(1)0ic(2)0ic(3)0ic11111110000(1)()iB c(2)(1)()iiC cc(000)(100)(010)(110)(001)(101)(011)(

20、111)(3)(2)(1)()iiiccc012sE50Trellis diagram40062625104371573102C(00)=0, 4C(10)=2, 6C(01)=1, 5C(11)=3, 7S0S1S2S3The error event corresponding to 2free()dS S51Coding gainv The intra-subset minimum squared Euclidean distance is given by v In this example, the parallel transitions are associated with si

21、gnals from one of the four subsets, C(00), C(01), C(10), C(11), with minimum squared Euclidean distance v In this example, the minimum squared Euclidean distance between any two different sequences of subsets 2222free()(0,2)(0,1)(0,2)4.586EEEsddddES S22min, ( )minmin( , )Es sdds sSSS 224sE 52Coding

22、gainv Thus, the free squared Euclidean distance of this TCM code isv Compared with an uncoded QPSK scheme with the minimum squared Euclidean distance 2Es between signal points, this TCM scheme can provide an asymptotic coding gain of222freefree2( )min(),=4sddECS S 410log32(dB)22SE SEQPSK constellation