纠错码Lecture7-卷积码(II)

1、信道编码理论信道编码理论邢莉娟、李卓，西安电子科技大学邢莉娟、李卓，西安电子科技大学1Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论2状态转移图和网格图状态转移图和网格图Viterbi译码算法译码算法修正的修正的Viterbi译码算法译码算法Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论3右图为右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生卷积编码示意图，其生成多项式矩阵和生成矩阵分别为成矩阵分别为22( )1, 1DDDDG11 101111 101111 1011GLecture 7 Le

2、cture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论4(2, 1, 2)码的状态图如右图所示码的状态图如右图所示卷积码的自由距离等于编码卷积码的自由距离等于编码 器从器从s0出发，又回到该状态出发，又回到该状态 时，所有可能非全零路径重时，所有可能非全零路径重 量的最小值量的最小值重量最小的路径：重量最小的路径： s0s1s2s0； 相应的输出码字序列为：相应的输出码字序列为： 111011 因此，因此，df =5Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论5s0s1s2s3s0s1s2s3状态图状态图网格图网格图Lecture

3、7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论6若编码信息序列为若编码信息序列为 1011100，则编码过程即为在，则编码过程即为在Trellis图上寻找一条路径图上寻找一条路径Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论7译码过程即为在译码过程即为在Trellis图上寻找一条路径，该路图上寻找一条路径，该路径对应的编码序列径对应的编码序列与接收序列之间有最大概率度与接收序列之间有最大概率度量量0max(|( )maxlog(|( ) 1,2,2k LjjjjPPjR CSR CSLecture 7 Lecture

4、7 卷积码卷积码(II)(II)信道编码理论信道编码理论8从第从第1时刻的全零状态开始（零状态初始度量为时刻的全零状态开始（零状态初始度量为0，其它状，其它状态初始度量为态初始度量为负无穷负无穷）在任一时刻在任一时刻t，对每一个状态只记录到达路径中度量最大，对每一个状态只记录到达路径中度量最大的一个（残留路径，的一个（残留路径，硬判决为汉明距离，软判决为欧氏距硬判决为汉明距离，软判决为欧氏距离离）及其度量（状态度量）及其度量（状态度量）在向在向t+1时刻前进过程中，对时刻前进过程中，对t时刻的每个状态作延伸，即时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到在状态度量基础上加上分支度

5、量，得到|S|2k条路径条路径对所得到的对所得到的t+1时刻到达每一个状态的时刻到达每一个状态的2k条路径进行比较，条路径进行比较，找到一个度量最大的作为残留路径找到一个度量最大的作为残留路径直到码的终点，如果确定终点是一个确定状态，则最终保直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果留的路径就是译码结果Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论9在在BSC和和BIQO-DMC上，最大概率度量分别等效为最小上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量距离度量和最小欧氏距离度量 距离度量更新公式

6、距离度量更新公式 Theorem：在：在Viterbi译码算法中，留选路径是有最大似然译码算法中，留选路径是有最大似然函数的路径。函数的路径。111111111 min(, ()min(, (), min min(, (), tttttttttttttttttttsddd rc ssdd rc ssSSSRC SRC SRC SttttSSSS max(|( )maxlog(|( ) min, ( )PPdR C SR C SR C SLecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论10第1个时刻接收子码10汉明距离d11第2个时刻接收子码10汉明距

7、离dExample: M=(1011100)，初始状态为全0的编码器输出序列为C=(11, 10, 00, 01, 10, 01, 11), 通过有噪信道后，接收序列为R=(10, 10, 00, 01, 11, 01, 11)11Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论11第3个时刻接收子码00汉明距离d2132Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论12第4个时刻接收子码01汉明距离d3,43,43,31,5汉明距离d33312133Lecture 7 Lecture 7 卷积码卷积码(

8、II)(II)信道编码理论信道编码理论13第5个时刻接收子码11汉明距离d3,53,52,42,4汉明距离d33223313Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论14第6个时刻接收子码01汉明距离d3,42,5汉明距离d3233223,43,433Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论15第7个时刻接收子码11汉明距离d2,5323301/000/101/110/110/011/14,44,43,4Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理

9、论16保存的保存的幸存路径幸存路径为为：译码结果为：译码结果为：1011100Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论17最大似然序列译码要求序列有限，因此对卷积码来说，要最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。求能收尾。收尾的原则收尾的原则 在信息序列输入完成后，利用输入一些特定的比特，使在信息序列输入完成后，利用输入一些特定的比特，使|S|个状态个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成就变成只有一条残留路径只有一条残留路径，这就是最大似

10、然序列。，这就是最大似然序列。非递归卷积码非递归卷积码 约束长度为约束长度为m+1的卷积码，只要在信息序列输入完成后的卷积码，只要在信息序列输入完成后连续送入连续送入m个个0，即可使任一路径都到达最终的状态，即可使任一路径都到达最终的状态0。递归卷积码递归卷积码 可通过将输入值置成反馈值的负值，而使可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达个时钟后的状态到达0。Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论18DD非系统非递非系统非递归码归码递归系统码递归系统码Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编

11、码理论信道编码理论19第6个时刻接收子码01汉明距离d3,42,5汉明距离d323322Example (cont.): M=(10111); M=(1011100)Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论20第7个时刻接收子码11汉明距离d2,5Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论21保存的保存的幸存路径幸存路径为为：译码结果为：译码结果为：1011100Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论22基本思想基本思想为了充分利用信道输出

12、符号的信息，提高译码可靠性，为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行把信道输出的信号进行Q电平量化，然后在输入电平量化，然后在输入Viterbi译码器。能适应这种译码器。能适应这种Q进制输入的进制输入的Viterbi译码器称为译码器称为软软判决判决Viterbi译码器译码器。例子：例子：Q=4电平量化的信道比特度量电平量化的信道比特度量00102112111085005810Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论23对信息序列长度为对信息序列长度为L，信息符号取自，信息符号取自GF(p)，R=k/n，约束长度为，

13、约束长度为m+1的卷积码。状态数为的卷积码。状态数为pkm因此对每个时刻要做因此对每个时刻要做pkm次次加比选加比选得到得到pkm个状态的残留个状态的残留路径路径每次加比选包括每次加比选包括pk次加法和次加法和pk-1次比较次比较。因此总运算量。因此总运算量约为约为Lpkm次加比选次加比选同时要能保存同时要能保存pkm条残留路径，因此需要条残留路径，因此需要Lpkm个存贮单个存贮单元。元。Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论24维特比算法是最大似然的序列译码算法维特比算法是最大似然的序列译码算法译码复杂度与信道质量无关译码复杂度与信道质量

14、无关运算量与码长呈线性关系运算量与码长呈线性关系存贮量与码长呈线性关系存贮量与码长呈线性关系运算量和存贮量都与状态数呈线性关系运算量和存贮量都与状态数呈线性关系状态数随分组大小状态数随分组大小k及编码存贮及编码存贮m呈呈指数指数关系关系Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论25基本思想基本思想当状态数有限时，给定时刻的各状态残留路径在一定当状态数有限时，给定时刻的各状态残留路径在一定时间（时间（L）之前来自于同一状态的可能性随）之前来自于同一状态的可能性随L的增加而的增加而迅速趋近于迅速趋近于1。因此当前时刻各残留路径很可能来自于。因此当前

15、时刻各残留路径很可能来自于L时刻前的同一路径。时刻前的同一路径。Lecture 7 Lecture 7 卷积码卷积码(II)(II)信道编码理论信道编码理论26在第在第k时刻，可以将时刻，可以将t-L时刻前的路径结果直接输出，而在时刻前的路径结果直接输出，而在存贮空间中不再保存存贮空间中不再保存t-L时刻前的内容。因此存贮量控制时刻前的内容。因此存贮量控制在在Lpkm。这里的。这里的L就被称做就被称做译码深度译码深度，不再随码长的增加，不再随码长的增加而增加。因而特别适合信息流的卷积码编译码。在这种情而增加。因而特别适合信息流的卷积码编译码。在这种情况下甚至况下甚至不需要对流分段加尾比特不需要对流分段加尾比特。显然，滑动窗算法是一种准最优算法。但通常译码深度只显然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的要有编码约束长度的5到到10倍，其性能损失就可以忽略不倍，其性能损失就可以忽略不计了。计了。Lecture 7 Lecture 7 卷积码