卷积码

卷积码编译码方案张宁•卷积码的基本概念•码的几种描述•编码方式•译码准则（Viterbi）要求掌握的内容•卷积码的编码：会由生成矩阵画编码电路；会由编码电路写生成矩阵，生成多项式矩阵•理解卷积码的Trellis描述方法，掌握卷积码的Viterbi译码算法第1节卷积码基本概念ConvolutionalCode区别于线性分组码的一个重要特性是有记忆。以此卷积码的编码器需要有存储m组信息元的记忆部件。即移位寄存器。卷积码的提出•Encoding：1955，Elias•Decoding：ThresholdDecoding——Massey(1963)ListDecoding——Wozencraft(1961)ViterbiDecoding——Viterbi(1967)卷积码的描述•卷积码是与分组码相对应的另一类纠错编码。•卷积码编码器输出的n个码元中，每一个码元不仅与此单元时间输入的k个信息元相关，还与之前的输入信息相关。•一般表示为（n，k，m）几个基本概念•输入信息k•输出信息n•码字c(信息位校验位校验位)•寄存器的个数m•编码约束度编码过程中互相约束的子码个数m+1•码率k/n卷积码与分组码的区别：本组的码元不仅与本组的k个信息元有关，而且还与以前若干时刻输入至编码器的信息元有关。译码时，不仅从此时刻收到的n个码元中提取译码信息，而且还利用以后若干时刻收到的码组提取有关译码信息。卷积码各码组之间不再是相互独立。卷积码的编码器可以看作是一个由k个输入端和n个输出端组成的时序网络。设第i时刻输入编码器的k个信息为：mi＝（mi(1)，mi(2)，‥，mi(k)）相应输出是由n0个码元组成的子码：ci＝（ci(1)，ci(2)，‥，ci(n)）若输入的信息序列：m＝（m0,m1,m2,‥）则输出由子码C＝（c0,c1,c2,‥），定义：如果n位长的子码中，前k位是原输入的信息元，则称该卷积码为系统码，否则称为非系统码。如图二进制卷积码编码器：第i时刻输入信息元mi，此时刻的子码：ci＝（mi，pi,1，pi,2）,pi,1，pi,2为校验元且满足：ci(1)＝mici(2)＝pi,1＝mi＋mi-1ci(3)＝pi,2＝mi＋mi-2mipi2pi1描述卷积码的参数mipi2pi1(n0,k0,m)mipi1pi2称为卷积码的一个子码，mi(或pi1或pi2)为卷积码的一个码元，子码中的一个比特称为一个码元(3,1,2)卷积码的编码及描述方式mipi2pi1(3,1,2)卷积编码器生成多项式矩阵2111DDDG子生成元1001,1g1102,1g1013,1gG(D)描述的卷积码码字中，每一段子码的n0个码元与k0个信息位之间的关系0nk0生成矩阵和生成多项式矩阵mipi2pi1(3,1,2)卷积编码器编码电路子生成元DGg假设移位寄存器的原始状态为（00），输入序列为m为（1010），那么编码输出如下：（1）当输入x0=1时，寄存器的状态为（100），所以1001100001gc1001001110001gc2101001101001gc320于是编码输出码字c0=（111）（2）当第2位信息x1=0输入时，移位寄存器内容为（010），编码输出分别为：0010100010gc1010010110010gc2111010101010gc321此时编码输出码字c1=（001）,...,,210bbb....)(332210bDbDbbDM)()()(11DgDMDC)()()(22DgDMDC则输入信息的多项式为那么我们可以得到输出Example1已知(2,1,3)码的子生成元为11011,1g11112,1g1求出该码的G(D)2画出该码的编码器3求出相应于信息序列M=(11001)的码序列4判断此码是否是系统码第2节卷积码的几种描述依据状态的转化来作图即s0（00），s1（10），s2（01），s3（11）卷积码的树图表示(2,1,2)卷积编码示意图将码树分成上下相等的两部分，就是把码序列划分成大小相等的两个子集s0和s1•（2，1，2）码码树图：•对一般的二进制（n0,k0,m）编码器，每次输入的是k0个信息元，有2ko个可能的信息组，这相应于从码树每一节点上分出的分支数有2ko条，相应于2ko种不同信息组的输入，且每条都有n0个码元，作为与此相应的输出子码。•因此，码数上所有可能的路径，就是该卷积码编码器所有可能输出的码序列。码树中子集的划分二、卷积码的状态图编码器寄存器中任一时刻的存数称为编码器的一个状态，以si表示，每个状态都对应一个不同的输入组。如图为（2，1，2）卷积码编码器状态图。编码器由两级移存器组成，其存数只有4种可能，即4个状态。实线表示0输入、虚线表示1输入时的状态转移例：信息组M＝（1100），M(D)＝1＋D，则，输出的码序列：C(D)＝M(D)G(D)＝(1+D)[1+D+D2,1+D2]相应地C＝（11，01，01，11）状态图中编码器的状态变化为：s0→s1→s3→s2→s0从s0开始再回到s0，所得码序列称为结尾码字。这要求输完信息序列后，还应再输入mk0个全0信息元，使编码器回到全0状态。S110S201S000S3110010010111100011卷积码的距离度量最小汉明距离：初始截段码字子集之间的最小汉明距离，用于衡量代数译码的性能——第0子组为非零的初始截短码字的最小重量在实际计算自由距离时，不需要计算所有半无限长码序列之间的汉明距离，只要在有限段上的截段码树上计算。卷积码的Trellis图表示(1)00/011/110/001/110/101/000/111/0(2,1,2)卷积编码示意图卷积码的Trellis图表示(2)00/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/0若编码信息序列为1011100，则编码过程即为在Trellis图上寻找一条路径第4节卷积码的Viterbi译码Viterbi译码基本原理硬判决Viterbi译码软判决Viterbi译码Viterbi译码基本原理Viterbi译码算法，给出通过Trellis图找到具有最大度量的路径，即最大似然路径或最大似然码字。即将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送的序列。在每个时间单元，Viterbi译码算法把2k个分支度量，加到每一个前面存储的路径度量上(加操作)，比较进入每一个状态的所有2k个路径的度量(比较操作)，选择具有最大度量的路径，这样的路径称为幸存路径(选择操作)。硬判决Viterbi译码(1)00/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/000/011/110/001/110/101/000/111/0译码过程即为在Trellis图上寻找一条路径，该路径对应的编码序列与接收序列之间有最小汉明距离硬判决Viterbi译码(2)•从第1时刻的全零状态开始（零状态初始度量为0，其它状态初始度量为负无穷）•在任一时刻t，对每一个状态只记录到达路径中度量最小的一个（残留路径，硬判决为汉明距离，软判决为欧氏距离）及其度量（状态度量）•在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到M*2k条路径•对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径•直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果硬判决Viterbi译码(3)00/011/1Example:M为1011100，编码器输出为：11,10,00,01,10,01,11,接收序列为10,10,00,01,11,01,11第1个时刻接收子码10汉明距离d11第2个时刻接收子码1000/011/1汉明距离d2201/100/011/110/011/013硬判决Viterbi译码(4)第3个时刻接收子码00汉明距离d2,34,13,43,400/011/101/100/011/110/011/001/100/011/110/010/101/000/111/000/011/1汉明距离d2101/100/011/110/011/03301/100/010/001/000/1硬判决Viterbi译码(5)00/011/110/001/110/101/000/111/000/011/101/100/011/110/011/001/100/011/110/001/000/111/0第4个时刻接收子码01汉明距离d3,43,43,31,500/011/110/001/100/011/101/100/011/110/001/100/010/000/1汉明距离d3331硬判决Viterbi译码(6)00/011/110/001/100/011/100/010/000/000/101/100/011/110/010/101/000/111/0第5个时刻接收子码11汉明距离d3,53,52,42,4汉明距离d332200/011/110/001/100/011/100/010/000/000/111/110/101/011/0硬判决Viterbi译码(7)00/010/001/100/011/100/010/000/000/111/110/101/011/010/111/000/011/110/001/101/000/1第6个时刻接收子码01汉明距离d3,42,500/010/001/100/011/100/010/000/000/110/101/011/011/001/0汉明距离d32硬判决Viterbi译码(8)00/010/001/100/011/100/010/000/000/110/101/011/011/001/0第7个时刻接收子码11汉明距离d2,500/011/0硬判决Viterbi译码(9)01/111/110/000/110/101/011/0保存的幸存路径为：译码结果为：1011100Viterbi译码算法的问题对m值很大的情况不适用——误码率很难做的很低译每一个分支的计算量不变要求误码率很低，且译码器计算量可随信道情况变化时，需采用序列译码课后习题•1给定生成元为g1=（110），g2=（101），g3=（111）的（3,1,2）二元卷积码，试画出它的编码电路及当输入为（11001100）时的码字输出。•二元（2,1,2）码。发送的码字为序列c=（11100001100111），通过BSC传送，接受序列R=（10100101100111）。用Viterbi译码译出相应的信息序列。uˆ