第十三章 信道编码理论.ppt

第十二章 卷积码的概率译码 （I） 卷积码的网格图表示 卷积码的概率译码：Viterbi译码算法 修正的Viterbi译码算法 滑窗 状态缩减 卷积码的Trellis图表示 右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生成矩阵分别为: 卷积码的Trellis图表示 Viterbi译码 Viterbi译码 Viterbi译码 从第1时刻的全零状态开始（零状态初始度量为0，其它状态初始度量为负无穷）； 在任一时刻t，对每一个状态只记录到达路径中度量最小的一个（残留路径，硬判决为汉明距离，软判决为欧氏距离）及其度量（状态度量）； 在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到|S|×2k条路径； 对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径； 直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果。 Viterbi译码 在BSC和BIQO-DMC上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量 。 距离度量更新公式 ： Theorem：在Viterbi译码算法中，留选路径是有最大似然函数的路径。 Viterbi译码 Viterbi译码 Viterbi译码 Viterbi译码 Viterbi译码 Viterbi译码 Viterbi译码 Viterbi译码——收尾 最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。 收尾的原则 在信息序列输入完成后，利用输入一些特定的比特，使|S|个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成只有一条残留路径，这就是最大似然序列。 非递归卷积码 约束长度为m+1的卷积码，只要在信息序列输入完成后连续送入m个0，即可使任一路径都到达最终的状态0。 递归卷积码 可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达0。 Viterbi译码——收尾 Viterbi译码 Viterbi译码 Viterbi译码 软判决Viterbi译码 基本思想： 为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行Q电平量化，然后在输入Viterbi译码器。能适应这种Q进制输入的Viterbi译码器称为软判决Viterbi译码器。 例子：Q=4电平量化的信道比特度量： Viterbi译码的复杂度 对信息序列长度为L，信息符号取自GF(p)，R=k/n，约束长度为m+1的卷积码。状态数为pkm 因此对每个时刻要做pkm次加比选得到pkm个状态的残留路径； 每次加比选包括pk次加法和pk-1次比较。因此总运算量约为Lpkm次加比选； 同时要能保存pkm条残留路径，因此需要Lpkm个存贮单元。 Viterbi译码的特点 维特比算法是最大似然的序列译码算法； 译码复杂度与信道质量无关； 运算量与码长呈线性关系； 存贮量与码长呈线性关系； 运算量和存贮量都与状态数呈线性关系； 状态数随分组大小k及编码存贮m呈指数关系。 滑窗Viterbi译码算法 基本思想： 当状态数有限时，给定时刻的各状态残留路径在一定时间（L）之前来自于同一状态的可能性随L的增加而迅速趋近于1。因此当前时刻各残留路径很可能来自于L时刻前的同一路径。 滑窗Viterbi算法实现 在第t时刻，可以将t-L时刻前的路径结果直接输出，而在存贮空间中不再保存t-L时刻前的内容。因此存贮量控制在Lpkm。这里的L就被称做译码深度，不再随码长的增加而增加。因而特别适合信息流的卷积码编译码。在这种情况下甚至不需要对流分段加尾比特。 显然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的5到10倍，其性能损失就可以忽略不计了。 缩减状态的Viterbi译码 由于运算量与k和m呈指数关系，因此维特比译码算法一般只适合于k和m较小的场合。大多数情况下k=1，m10。 对状态数很大的卷积码，维特比算法要经一定的修正后才可能实用，常用的算法是缩减状态的维特比译码，即在每一时刻，只处理部分的状态。 第十二章 卷积码的概率译码 （II） 序列译码 Fano译码算法 ST译码算法 调制与编码的结合(TCM技术) 序列译码 Viterbi译码算法存在的问题: 对m值很大的情况不适用——误码率很难做的很低; 译每一个分支的计算量不变; Viterbi译码中路径度量计算方法不适用于比较不同长度的路径，如: R =(10,10,00,01,11,01,00) C5=(11,10,00,01,10,01) C0=(11)