《数学卷积码》PPT课件.pptVIP

6.4 卷积码积码 卷积码积码 的产产生 分组码组码 以孤立码块为单码块为单 位编译码编译码 信息流割裂为为孤立块块后丧丧失了分组间组间 的相关信息 分组码长组码长 n越大越好，但译码译码 运算量随n指数上升 本节节内容 卷积码积码 的基本概念和描述方法 卷积码积码 的最大似然译码译码 维维特比算法 卷积码积码 的性能限与距离特点 * 1 (n,k,L)卷积编码示意 第i分组 第i-1分组 第i-2分组 第i-L分组 输入 卷积编码器（线性组合器） c0i c1i cn-2i cn-1i * 2 编码输出C i 6.4.1 卷积码积码 的基本概念和描述方法 将信息序列分隔成长度k的一个个分组 某一时刻的编码输出不仅取决于本时刻的 分组，而且取决于本时刻以前的L个分组。 称L1为约束长度 最重要的三个参数 (n,k,L) * 3 卷积编码器的一般结构 * 4 m0i-Lm0i-2m0i-1m0i m1i-Lm1i-2m1i-1m1i 串 并 变 换 线 性 组 合 器 并 串 变 换 mk-1i-L mk-1i-2mk-1i-1mk-1i c0i c1i Cn-2i Cn-1i . 信号mi 编码 输出ci 例10 二进制(3,2,1)卷积编码器 本时刻m0=(m00,m10)=(01),上一时刻m1=(m01,m11)= (10) glk,n表示记忆阵列第k行(k=0,1) 第l列(l =0,1)对第n个( n =0,1,2) 码元的影响,共NK(L+1)= 322个系数： g000 = 1, g001 = 1, g010 = 0, g011 = 1,g020 = 1, g021 = 1, g100 = 0, g101 = 1,g110 = 1, g111 = 0,g120 = 1, g121 = 0。 用矩阵表示 * 5 c0i 信号入 m c1i C i 编码输出 c2i m0i m0i-1 m1i m1i-1 本时刻编码输出： C0=(c00, c10, c20 )= m1G0+m0G1 =(10) + (01) = (101)+(100) =(001) * 6 卷积码名称的由来 设编码器的初始状态为零（记忆阵列全体清0），随着时 刻i的递推和k比特信息组(m0, m1, mL, mL+1,)源源不断 地输入，码字(C0, C1, CL, CL+1,)源源不断地输出。 在时刻i = 0 时，C0 = m0G0 i = 1 时，C1= m1G0 + m0G1 i = L 时，CL= mLG0 + mL-1G1+m0GL i=L+1时，CL+1= mL+1G0 + mLG1+m1GL 于是任何时刻i的输出码字：Ci = mi -l Gl * 7 *8 无限长矩阵序列mi与有限长矩阵序列Gl的卷积运算 * 9 例11:图示, 假设输入信息序列是101101011100, 求输出码字序列。 c0i 信号入 m c1i 输出C i c2i m0i m0i-1 m0i-2 c0i 信号入 m c1i 输出C i c2i m0i m0i-1 m0i-2 解： 由 g000 = 1, g001 = 0, g002 = 0, g010 = 1, g011 = 1, g012 = 0, g020 = 1, g021 = 1, g022 = 1。 * 10 得： *11 例:设GF(2)中（3，2，1）卷积码生成矩阵分别为： 求：卷积码的生成矩阵G 。 若输入信息序列为U=1011010100，求输出码字序列 。 解：码的基本生成矩阵g =g0 g1 0 ,则其生成矩阵为 C=101 110 010 011 001 树图表示 * 12 对对于图图示的(3,1,3)卷积码编码积码编码 器，假设设移位寄存器的初始状态为态为 (000)。 如果第1位输输入为为0，编码输编码输 出码码字为为(000)，如果输输入为为1，输输出为为 (111)；第2位输输入也有两种可能性，考虑虑到第1位输输入的两种可能，共有 4种可能，对应输对应输 出分别为别为 (00)(000) (01)(111) (10)(001) (11)(110) 树图表示 * 13 (00)(000) (01)(111) (10)(001) (11)(110) 依次类类推，可以将输输入序 列各种可能都加以考虑虑，用一个 树树将编码输编码输 入信息与编码输编码输 出 码码字之间间的关系表示出来，如右 图图所示。 通过过跟踪由输输入序列 确定的路径，即可以得到相应应的 输输出码码序列。 若输输入序列为为 1101 ，得到相应应的输输出码码序列为为111 110 010 100 。 路径为为加黑的虚线线。 多项式表示 G(D)= G0+ G1D+ GLDL = gkn(D)=gkn0+gkn1D+gkn2D2+gknLDL= gknl Dl 例6-10中 * 14 例12 二元(3,1,2)卷积码积码 的转转移函数矩阵阵G(D)=(1,1+D, 1+D+D2 )，画出编码编码 器结结构图图. 根据转转移函数矩阵阵， g00(D) = g000+ g001D + g002 D2 = 1 g01(D) = g010+ g011D + g012 D2 = 1D g02(D)= g020+g021D +g022 D2 = 1+D+D2 得 g000 = 1, g001 = 0, g002 = 0, g010 = 1, g011 = 1, g012 = 0, g020 = 1, g021 = 1, g022 = 1。 * 15 c0i 信号入 m c1i 输出C i c2i m0i m0i-1 m0i-2 卷积码的状态流图表示 * 16 例13:图示, 试分别用编码矩阵和状态流图来描述该码 .假设输入信息序列是101101011100,求输出码字. c0i 信号入 m c1i 输出C i c2i m0i m0i-1 m0i-2 *17 解:n=3，k=1，L=2,记忆阵记忆阵 列为为1行3列。 除本时时刻输输入信息m0i外,记忆记忆 的信息 的4种组组合状态态 决定了编码编码 器当前的状态态。 记忆记忆 位 加上m0i 共同决定了编码编码 器当前的状态态, 而编码编码 器的下一个状态态是由 两者决定的。 状态态 S000 S101 S210 S311 编码器状态的定义 输输入 状态态 S0000111 S1001110 S2011100 S3010101 输输入 状态态 S0S0S2 S1S0S2 S2S1S3 S3S1S3 不同状态与输入时 编出的码字 不同状态与输入 时的下一状态 S0 1/111 S2 0/011 S11/110 S2 1/100 S3 0/010 S1 * 18 S0 S1 S2 S3 假如输入信息序列 是10110， 0/000 S0 1/111 0/001 1/110 S2 S1 0/011 1/100 0/010 S3 1/101 (3,1,2)卷积码状态流图 编码矩阵 卷积码网格图 S0(00) 1/111 0/001 0/001 S1(01) 1/111 S2(10) 0/010 1/110 S3(11) t =0 T 2T 3T 4T 5T 6T * 19 1/110 0/011 0/010 1/101 0/000 1/100 0/0000/0000/0000/0000/0000/000 0/011 1/110 1/100 第一部分：网格图 第二部分：编码轨迹（路径）图 S0 1/111 S2 0/011 S11/110 S2 1/100 S3 0/010 S1 138 输入信息序列是10110，输出码字是111，011，110，100，010 6.4.2 卷积码积码 的最大似然译码译码 维维特比算法 *20 卷积码的性能取决于卷积码距离特性和译码算法。 描述距离特性的最好方法是利用网格图。 含义： 任意两序列间的距离等于将它们模2 加后所得序列的汉 明重量，又一定等于某一序列与全零序列的距离，等效地等 于该序列的重量。 通过研究序列重量来研究卷积码距离特性，序列间的最 小距离正好是最轻序列的重量。 6.4.2 卷积码积码 的最大似然译码译码 维维特比算法 * 21 序列距离与序列长度有关。 定义义：长长度l（码码字）的任意两序列的最小距离为为l 阶阶列距 离，记记作dc(l),即 由定义，自由距离在网格图上就是0时刻从0状态与全零路 径分叉（C0），经若干分支后又回到全零路径的所有路径 中，重量最轻的那条。 6.4.2 卷积码积码 的最大似然译码译码 维维特比算法 * 22 2 2 1 2 0 1 0 0/0000/0000/0000/0000/000 t =0 T 2T 3T 4T 5T 6T 3 1 3 3 1 2 6 6 9 9 66 1 1 1 例：二元(3,1,2)编码器结构如下图， 求该码的自由距离. S0 1/111 S2 0/011 S11/110 S2 1/100 S3 0/010 S1 135 S0(00) S1(01) S2(10) S3(11) 6.4.2 卷积码积码 的最大似然译码译码 维维特比算法 自由距离 df 的常用计计算方法是 用信号流图图化简简法来得到生成函数 T(D)，然后由到生成函数T(D)得出 自由距离df 。 例16：由(3，1，2)卷积码积码 ，其状态态 流图图如图图示，试试用信号流图图法计计 算生成函数T(D)及自由距离df 。 * 23 0/000 S0 1/111 0/001 1/110 S2 S1 0/011 1/100 0/010 S3 1/101 (3,1,2)(3,1,2)卷积码状态流图卷积码状态流图 卷积码积码 的纠错纠错 能力取决于码码字序列间间的距离。自由距 离df就成了卷积码积码 的主要性能指标标。 *24 0/000 S0 1/111 0/001 1/110 S2 S1 0/011 1/100 0/010 S3 1/101 (3,1,2)(3,1,2)卷积码状态流图卷积码状态流图 *25 *26 自由距离df=6 6.4.2 卷积码积码 的最大似然译码译码 维维特比算法 * 27 卷积码的译码就是搜遍网格图找出最可能的序列. 搜寻网格图时所用的相似性度量可以是汉明距离,也 可是欧氏距离,这种最小距离准则的译码算法叫卷积码的 最大似然译码. 以一个具体例子来说明维特比算法的执行过程。 6.4.2 卷积码积码 的最大似然译码译码 维维特比算法 * 28 例：二元(3,1,2)卷积码，其网格图如上图所示，设发送的 码字序列是C=(000,111,011,001,000,000,),接收的码字序 列是R=(110,111,011,001,000,000,),试用维特比算法译码 。 1 4 3 2 000 101 111 001 110 011 010 100 6.4.2 卷积码积码 的最大似然译码译码 维维特比算法 * 29 1 4 3 2 000 101 111 001 110 011 010 100 解（1）用数组描述网格图结构： p(1,1)=1，c(1,1)=000，p(1,2)=2，c(1,2)=001 p(3,1)=1，c(3,1)=111，p(3,2)=2，c(3,2)=110 p(2,1)=3，c(2,1)=011，p(2,2)=4，c(2,2)=010 p(4,1)=3，c(4,1)=100，p(4,2)=4，c(4,2)=101 6.4.2 卷积码积码 的最大似然译码译码 维维