信息论与编码原理第10章卷积码.ppt

第1页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,信息论与编码原理,（第十章） 卷积码,第2页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,第10章 卷积码,10.1 卷积码的基本概念 10.2 卷积码的编码 10.3 卷积码的矩阵描述 10.4 卷积码的译码 10.5 卷积码的状态转移图与栅格描述 10.6 维特比译码的基本原理 10.7 软判决维特比译码 10.8 维特比译码的性能 10.9 维特比译码的应用,第3页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,卷积码（连环码）首先由麻省理工学院于1955年提出。 卷积码与分组码的不同之处：在任意给定单元时刻，编码器输出的 n 个码元中，每一个码元不仅和此时刻输入的 k 个信息元有关，还与前连续 m 个时刻输入的信息元有关。卷积码常用(n,k,m)表示。 n子码，k信息位，m编码存储 在同样的编码效率 R 下，卷积码的性能优于分组码，至少不低于分组码。 卷积码的译码方法 代数译码：门限译码。译码延时是固定的。 概率译码： 序列译码：译码延时是随机的。 维特比译码：译码延时是固定的。,第4页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 (2) 系统码形式的卷积码,第5页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例9.1.1：(2,1,3)码,返回,第6页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.1：(2,1,3)码 待编码的信息序列 M：在对 M 进行编码之前，先将它每 k 个码元分成一组，在每单元时刻内，k 个码元串行输入到编码器； 移位寄存器组： (m+1) 个，每个移位寄存器组内有 k 级寄存器； 常数乘法器 g(i,j)：i=1,2,k；j=1,2,n，共有 (m+1)n 个，当 g(i,j) =1时，常数乘法器为一条直通的连接线；当 g(i,j) =0 时，连接线断开。每一个码元都是 k(m+1) 个数据组合，每一个码字需用 nk(m+1) 个系数才能描述； 开关 K 在每一节拍中移动 n 次，每一节拍输入 k 个信息元而输出 n 个码元。,参见图,第7页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.1：(2,1,3)码 信息序列 M=m0(1)m1(1)； ml(1)表示第 l 个时刻的第 k=1个信息元； 卷积码的生成序列 g(1,1)=g0(1,1) g1(1,1) g2(1,1) g3(1,1)=1011 g(1,2)=g0(1,2) g1(1,2) g2(1,2) g3(1,2)=1111 g(1,1)表明：任一时刻 l 时，输出端 1 的码元 Cl(1) 是由此时刻 l 输入的信息元 ml(1) 与前两个时刻输入的信息元 ml2(1) 以及前三个时刻 ml3(1) 输入的信息元模 2 加后的和； g(1,2)表明：Cl(2) 是由 ml(1)、ml1(1)、ml2(1)和ml3(1) 的模 2 和。,参见图,第8页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.1：(2,1,3)码 信息序列 M=m0(1)m1(1)； ml(1)表示第 l 个时刻的第 k=1个信息元； 卷积码的生成序列 生成序列：给定 g(i,j) 后，就可以生成编码器输出的码元。称g(1,1) 和 g(1,2) 为 (2,1,3) 卷积码的生成序列。 第 l 个时刻的编码器输出为：,第9页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.1：(2,1,3)码 信息序列 M=m0(1)m1(1)； ml(1)表示第 l 个时刻的第 k=1个信息元； 卷积码的生成序列 卷积码名称的由来：任一时刻编码器的输出可以由信息元与生成序列的离散卷积运算求出。,第10页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.1：(2,1,3)码 设 M =m0(1) m1(1) m2(1) m3(1)=1011，则编码器两个输出端的序列分别是： 子码：在任一单元时刻，送入编码器一个信息元（k=1），编码器输出由 2 个 (n=2) 码元组成的一个码组，称之为子码。,第11页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.1：(2,1,3)码 每个子码中的码元不仅与此时此刻的信息元有关，而且还与前 m 个 (m=3) 时刻的信息元有关。 编码存储：m（本例 m=3） 约束度：N=m+1，编码过程中相互约束的子码数。（本例 N=4） 编码约束长度：Nn，编码过程中相互约束的码元数。（本例Nn=8） 非系统码：在码序列 C 中的每个子码不是系统码字结构。（本例是非系统码）,第12页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.2：(3,2,1)码 n=3, k=2, m=1； 它的任一子码有 3 个码元。每个码元由此时此刻的 2 个信息元和前一个时刻进入编码器的 2 个信息元模 2 运算和求出。 这些信息元参加模 2 运算的规则由 nk=32=6 个生成序列 nk(m+1)=322=12个系数 所确定，每个生成序列含有 2 个元素。这 6 个输出序列是： g(1,1)=g0(1,1) g1(1,1)=11 g(1,2)=g0(1,2) g1(1,2)=01 g(1,3)=g0(1,3) g1(1,3)=11 g(2,1)=g0(2,1) g1(2,1)=01 g(2,2)=g0(2,2) g1(2,2)=10 g(2,3)=g0(2,3) g1(2,3)=10 (10.1.1),参见图,第13页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.2：(3,2,1)码 若待编码的信息序列：M=m0(1)m0(2) m1(1)m1(2) ml(1)ml(2) 则码序列 C 中的任一子码为：,第14页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.2：(3,2,1)码 g(1,1)=g0(1,1) g1(1,1)=11 g(2,1)=g0(2,1) g1(2,1)=01 g(1,2)=g0(1,2) g1(1,2)=01 g(2,2)=g0(2,2) g1(2,2)=10 g(1,3)=g0(1,3) g1(1,3)=11 g(2,3)=g0(2,3) g1(2,3)=10,返回,第15页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 例10.1.2：(3,2,1)码 每个时刻单元输入编码器 k=2个信息元，它们与前一个时刻进入编码器的 2 个信息元按式 (9.1.2) 所确定的卷积关系进行运算后，在输出端1，2，3分别得到该时刻子码中的 3 个码元。 编码器由 N=2 个移位寄存器组和模 2 加法器构成，每个移位寄存器组含有 k=2 级移位寄存器，每级移位寄存器的输出按式 (9.1.1) 的规则引出后进行模 2 加的运算。 本例也是非系统码形式的卷积码。,第16页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(1) 卷积码的生成序列、约束度和约束长度 推论：(n,k,m) 码完全由 (nk) 个生成序列所生成，每个生成序列中含有 (N =m+1) 个元素。 码序列：C=C0(1)C0(2)C0(n)C1(1)C1(2)C1(n)Cl(1)Cl(2)Cl(n) 待编码的信息序列：M=m0(1)m0(2)m0(k)m1(1)m1(2)m1(k)ml(1)ml(2)ml(k) 任一子码：可按如下卷积关系求出：,返回目录,第17页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(2) 系统码形式的卷积码 系统卷积码：是卷积码的一类。它的码序列中任一子码 Cl，也是有 n 个码元，其前 k 位与待编码信息序列中的第 l 信息组 ml(i) 相同，而后 (nk) 位监督元由生成序列生成； 每个码中的前 k 位就是此时刻待编码的 k 位信息元，所以在生成序列 g(i,j) 中有 (kk) 个生成序列是固定的，即：,第18页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(2) 系统码形式的 卷积码,只有 k(nk) 个生成序列需要给定，以便确定每个子码中 (nk) 个监督元。,返回,第19页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(2) 系统码形式的卷积码 任一子码由下式计算： 上式表明：在约束长度 N 内，每个子码中的 (nk) 个监督元与信息元的卷积关系。,第20页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(2) 系统码形式的卷积码 例10.1.3：(3,1,2)系统卷积码 g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=110 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101,第21页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.1 卷积码的基本概念,(2) 系统码形式的卷积码 例10.1.3：(3,1,2)系统卷积码 g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=110 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101 任一时刻子码为：,第22页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 系统码形式的卷积码 例10.1.4：(3,2,2)系统卷积码 g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=000 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101 g(2,1)=g0(2,1) g1(2,1) g2(2,1)=000 g(2,2)=g0(2,2) g1(2,2) g2(2,2)=100 g(2,3)=g0(2,3) g1(2,3) g2(2,3)=110 该码的任一子码 Cl 中前两位与 ml(1)、ml(2) 相同，后一位的监督元由式 (10.1.4) 确定，即：,10.1 卷积码的基本概念,第23页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 系统码形式的卷积码 例10.1.4：(3,2,2)系统卷积码 g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(2,1)=g0(2,1) g1(2,1) g2(2,1)=000 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=000 g(2,2)=g0(2,2) g1(2,2) g2(2,2)=100 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101 g(2,3)=g0(2,3) g1(2,3) g2(2,3)=110,10.1 卷积码的基本概念,返回目录,第24页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 串行输入、串行输出的编码电路 (2) (nk)m 级移位寄存器构成的并行编码电路 （型编码电路） (3) km级移位寄存器编码电路（型编码电路） (4) 结论,10.2 卷积码的编码,第25页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 串行输入、串行输出的编码电路 非系统码编码器：根据式(10.1.3)构造的是非系统编码器。 图9.2.1是(n,k,m)非系统卷积码串行编码电路。,10.2 卷积码的编码,第26页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 串行输入、串行输出的编码电路,10.2 卷积码的编码,第27页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 串行输入、串行输出的编码电路 系统码编码器：根据式(10.1.4)构造的是系统编码器； 图10.2.2是 (n,k,m) 系统卷积码串行编码电路。,10.2 卷积码的编码,第28页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 串行输入、串行输出的编码电路,10.2 卷积码的编码,返回目录,第29页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) (nk)m 级移位寄存器构成的并行编码电路（型编码电路） 这是系统码形式的一种编码电路，又称型编码电路；将式(10.1.4)展开后可以改写为式(10.2.1)。 式(10.2.1)表明：在并入并出方式下，为了获得第 l 个子码的 (nk) 个监督元，需要： (nk) 个移位寄存器组，每一组移位寄存器的数目为 m 级； 它们根据生成序列 g(i,j) 所确定的关系存储了第 l 个信息组相邻的前 m 个信息组。,10.2 卷积码的编码,第30页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) (nk)m 级移位寄存器构成的并行编码电路,10.2 卷积码的编码,第31页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) (nk)m 级移位寄存器构成的并行编码电路 例10.2.1：(3,2,2)码型编码电路 解：生成序列为： g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=000 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101 g(2,1)=g0(2,1) g1(2,1) g2(2,1)=000 g(2,2)=g0(2,2) g1(2,2) g2(2,2)=100 g(2,3)=g0(2,3) g1(2,3) g2(2,3)=110 根据式(10.2.1)，第 l 个子码的监督元为： Cl(3)=ml(1)g0(1,3)+ ml(2)g0(2,3) +ml1(1)g1(1,3)+ ml1(2)g1(2,3) + ml2(1)g2(1,3)+ ml2(2)g2(2,3),10.2 卷积码的编码,第32页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) (nk)m 级移位寄存器构成的并行编码电路 例10.2.1：(3,2,2)码型编码电路 解： 将生成序列诸元素带入后有： Cl(3)=ml(1)+ ml(2)+ ml1(2)+ ml2(1) (3,2,2)码的型编码电路如图10.2.3所示。 图10.2.4是(n,k,m)系统码型编码电路。,10.2 卷积码的编码,第33页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.2 卷积码的编码,返回目录,第34页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(3) km 级移位寄存器编码电路（型编码电路） 将式(10.1.4)展开后可以改写为式(10.2.2)。 式(10.2.2)表明：只需将第 l 时刻的 k 个信息元与前 m 个时刻的诸信息元按生成序列所确定的关系模 2 相加，就可以得到此时刻的 (nk) 个监督元。 型编码电路由 k 个移位寄存器组构成，每一组有 m 级移位寄存器。它们分别寄存了前 m 时刻进入编码器的第一个到第 k 个信息元.,10.2 卷积码的编码,第35页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(3) km 级移位寄存器编码电路（型编码电路） 例10.2.2：(3,1,2)码 g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=110 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101 由式(10.2.2)，该码任一子码的监督元为： Cl(2)=ml(1)g0(1,2)+ml1(1)g1(1,2)+ml2(1)g2(1,2)=ml(1)+ml1(1) Cl(3)=ml(1)g0(1,3)+ml1(1)g1(1,3)+ml2(1)g2(1,3)=ml(1)+ml2(1) 其编码电路如图10.2.5所示。,10.2 卷积码的编码,第36页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(3) km 级移位寄存器编码电路（型编码电路） 例10.2.3：(3,2,2)码，已知码的生成序列为： g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=000 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101 g(2,1)=g0(2,1) g1(2,1) g2(2,1)=000 g(2,2)=g0(2,2) g1(2,2) g2(2,2)=100 g(2,3)=g0(2,3) g1(2,3) g2(2,3)=110 由式(10.2.2)，该码任一子码的监督元为： Cl(3) =ml(1)g0(1,3)+ml1(1)g1(1,3)+ml2(1)g2(1,3) +ml(2)g0(2,3)+ml1(2)g1(2,3)+ml2(2)g2(2,3) Cl(3) =ml(1)+ml2(1)+ml(2)+ml1(2) 编码电路如图10.2.6所示。图10.2.7所示的是(n,k,m)码的型编码电路。,10.2 卷积码的编码,第37页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(3) km 级移位寄存器编码电路（型编码电路） 例10.2.3：(3,2,2)码 Cl(3)=ml(1)+ml2(1)+ml(2)+ml1(2),10.2 卷积码的编码,第38页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.2 卷积码的编码,返回目录,第39页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(4) 结论：以上三种形式电路各有不同的特点 在一般的串行通信方式下，用串行编码电路比较方便，虽然它所需的电路级数较多； 在并行通信时，若(nk)k，采用型编码电路较型更为简单； 否则，应采用型编码电路。,10.2 卷积码的编码,返回目录,第40页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,描述卷积码编译码的过程，可以用不同的描述方法：如矩阵法、码树法、状态图法、篱笆图法等。采用何种方法与卷积码的译码方法有很大关系。 代数译码时：用矩阵法 对译码原理的叙述和理解较方便。 概率译码时：借助码树和篱笆图能更清晰地分析和了解译码过程和码的性能。 (1) 卷积码的生成矩阵 (2) 卷积码的监督矩阵,10.3 卷积码的矩阵描述,第41页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.1：(2,1,3) 码的生成矩阵是如何得到的？ g(1,1)=g0(1,1) g1(1,1) g2(1,1) g3(1,1)=1011 g(1,2)=g0(1,2) g1(1,2) g2(1,2) g3(1,2)=1111,10.3 卷积码的矩阵描述,第42页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.1：(2,1,3) 码的生成矩阵是如何得到的？ g(1,1)=g0(1,1) g1(1,1) g2(1,1) g3(1,1)=1011 g(1,2)=g0(1,2) g1(1,2) g2(1,2) g3(1,2)=1111,10.3 卷积码的矩阵描述,第43页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.1：(2,1,3) 码的生成矩阵是如何得到的？ 将上式表示成矩阵方程，则有： 即：CT=GTMT=(MG) T,10.3 卷积码的矩阵描述,第44页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.1：(2,1,3) 码的生成矩阵是如何得到的？ 或者：C=MG,10.3 卷积码的矩阵描述,第45页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.1：(2,1,3) 码的生成矩阵是如何得到的？ 或者：C=MG 式中： 其中：,10.3 卷积码的矩阵描述,第46页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.1：(2,1,3) 码的生成矩阵是如何得到的？ 码的生成矩阵G：G 称为 (2,1,3) 码的生成矩阵。 当输入的信息序列是有头无尾的半无限序列时，生成矩阵也是半无限矩阵，G 的下标就是这个含义，这时码序列 C 亦为半无限序列。 生成矩阵 G中，只要第一行 G0G1G2G3确定以后，生成矩阵 G 也就确定了。 基本生成矩阵g：生成矩阵 G 的第一行为该码的基本生成矩阵. g 中的每一个元素完全由码的生成序列 g(i,j) 诸元素所确定。 (2,1,3)码g的参数：基本生成矩阵中的每个元素 G0,G1,G2,G3 都是 (12)阶矩阵 (kn, k=1,n=2)，元素的数目共4个 (m+1=N=4)。,10.3 卷积码的矩阵描述,第47页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.2：(3,2,2)非系统卷积码，它的6个生成序列为： g(1,1)=g0(1,1) g1(1,1) g2(1,1)=110 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=010 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=100 g(2,1)=g0(2,1) g1(2,1) g2(2,1)=001 g(2,2)=g0(2,2) g1(2,2) g2(2,2)=100 g(2,3)=g0(2,3) g1(2,3) g2(2,3)=111 设信息序列： M=m0(1)m0(2)m1(1)m1(2)m2(1)m2(2)m3(1)m3(2) 由式 (10.1.3)，编码器的输出 C 为：,10.3 卷积码的矩阵描述,第48页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.3 卷积码的矩阵描述,第49页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 例10.3.2：(3,2,2)非系统卷积码 写成矩阵方程，得到(3,2,2)码的生成矩阵和基本生成矩阵：,10.3 卷积码的矩阵描述,第50页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 (n,k,m) 码的基本生成矩阵和生成矩阵,10.3 卷积码的矩阵描述,第51页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 初始截断码组C：编码器初始状态全为 0，编码器输入N=m+1 个信息组，即 Nk 个信息元后，编码器输出的首 N=m+1 个子码，即 Nn 个码元，这首 N=m+1 个子码组成的码组称为卷积码的初始截断码组。 C=C0C1C2Cm 其中 Ci=Ci(1)Ci(2) Ci(n) i=0,1,2, m 根据初始截断码组的定义：C = MG 其中：M=m0m1m2mm mi=mi(1)mi(2) mi(k) i=0,1,2, m,10.3 卷积码的矩阵描述,第52页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 初始截断码组C：编码器初始状态全为 0，编码器输入N=m+1 个信息组，即 Nk 个信息元后，编码器输出的首 N=m+1 个子码，即 Nn 个码元，这首 N=m+1 个子码组成的码组称为卷积码的初始截断码组。 初始截断码组的生成矩阵：G 初始截断码组的基本生成矩阵：g =G0G1G2Gm,10.3 卷积码的矩阵描述,第53页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 系统卷积码的生成矩阵 (kk) 个生成序列是已知的，即当： i=j 时，g(i,j)=1；当 ij 时， g(i,j)=0，i=1,2,k；j=1,2,k。,10.3 卷积码的矩阵描述,每个子码中的前 k 个码元与相应的 k 个信息元相同；后(nk)个监督元由信息序列与生成序列的卷积运算得到。 系统卷积码的初始截断码组的生成矩阵为：,参见图,第54页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 系统卷积码的生成矩阵 其中 Ik 是 k 阶单位方阵 Pl 是 k(nk) 阶矩阵，l=0,1,2,m 系统卷积码初始截断码组的基本生成矩阵为： g =IkP0 0P1 0P2 0Pm,10.3 卷积码的矩阵描述,第55页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(1) 卷积码的生成矩阵 由于初始截断码组的基本生成矩阵和生成矩阵完全可以描述码的卷积关系，为简洁起见，就直接称它们为码的基本生成矩阵和生成矩阵。,10.3 卷积码的矩阵描述,返回目录,第56页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） 任一时刻单元的信息元不仅参与本时刻子码中 (nk) 个监督元的运算，而且还参与了相邻的后 m 个子码中的监督元的运算。这种约束关系用矩阵表示，就是卷积码的监督矩阵。,10.3 卷积码的矩阵描述,第57页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） 例10.3.3：(3,1,2)系统卷积码 g(1,1)=g0(1,1) g1(1,1) g2(1,1)=100 g(1,2)=g0(1,2) g1(1,2) g2(1,2)=110 g(1,3)=g0(1,3) g1(1,3) g2(1,3)=101,10.3 卷积码的矩阵描述,第58页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） 例10.3.3：(3,1,2)系统卷积码 初始截断码组的监督矩阵：设 l=0,1,2,10.3 卷积码的矩阵描述,第59页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） 例10.3.3：(3,1,2)系统卷积码 将上式中各子码的监督元表示式重写如下：,10.3 卷积码的矩阵描述,第60页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） 例10.3.3：(3,1,2)系统卷积码 系数用矩阵表示，得到如下矩阵方程：,10.3 卷积码的矩阵描述,第61页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） 例10.3.3：(3,1,2)系统卷积码 系数用矩阵表示，得到如下矩阵方程：,10.3 卷积码的矩阵描述,第62页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） 例10.3.3：(3,1,2)系统卷积码 在监督矩阵 H 中，I2 是 2 阶单位方阵，0 是 2 阶全 0 方阵： P0T，P1T ，P2T分别为: 基本监督矩阵 h：H 最后一行。 h29= P2T0 P1T 0 P0TI2,10.3 卷积码的矩阵描述,第63页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,(2) 卷积码的监督矩阵（系统卷积码的监督矩阵） (n,k,m)码的基本监督矩阵和监督矩阵,10.3 卷积码的矩阵描述,第64页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.4 卷积码的译码,(1) 卷积码译码的种类：卷积码的译码可分为代数译码和概率译码。 (2) 代数译码：从码的代数结构出发，以一个约束度的接收序列为单位，对该接收序列的信息码组进行译码。大数逻辑译码是代数译码的主要方法。代数译码中，用矩阵描述比较方便。 (3) 概率译码：从信道的统计特性出发，以远大于约束度的接收序列为单位，对信息码组进行最大似然的判决。维特比译码和序列译码是其最主要的方法。在维特比译码中，用栅格图来描述码的译码更为方便。,返回目录,第65页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(1) 卷积码的状态,(2) 卷积码的状态转移图,(3) 卷积码的栅格图,第66页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(1) 卷积码的状态 定义：卷积码编码器要存储 m 段消息，这些消息数据既要因新的输入而改变，又要影响当前的编码输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，简称状态。,第67页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(1) 卷积码的状态 有效存储单元 M：Mk m 状态向量(l)/：(l)=(M(l), M1(l), 2(l),1(l) 二元 (n,k,m) 卷积码共有 2M 个不同的状态，记为： 新的状态：(l+1)/ 转移分支：(l),(l+1)/(, ) 输入段：u(l)/u 输出段：v(l)/v 状态转移方程：=(,u) 输出方程： v =(,u),第68页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(1) 卷积码的状态 例10.5.1：(2,1,2)码的状态向量为=(21)，共有 4 种状态 S0,S1,S2,S3，如图所示。 g(1,1)=g0(1,1) g1(1,1) g2(1,1) =111 g(1,2)=g0(1,2) g1(1,2) g2(1,2) =101,第69页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(1) 卷积码的状态 例10.5.1： 其状态变化表如表所示。 该码的状态转移方程和输出方程分别为： 1=u 2=1 v1=u +1+2 v2=u +2,第70页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(1) 卷积码的状态 例10.5.1： 其状态转移图如图10.5.3和图10.5.4所示。,第71页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(1) 卷积码的状态 例10.5.1： 其状态转移图如图10.5.3和图10.5.4所示。,返回目录,第72页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(2) 卷积码的状态转移图 闭合型的状转移态图：直接地描述了卷积编码器在任一时刻的工作状况； 开放型的状态转移图：更适合去描述一个特定输入序列的编码过程。,第73页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(2) 卷积码的状态转移图 例10.5.2：(3,2,1)码的状态向量为=(21)，共有 4 种状态S0,S1,S2,S3，如图10.5.5所示。 g(1,1)=g0(1,1) g1(1,1)=11 g(1,2)=g0(1,2) g1(1,2)=01 g(1,3)=g0(1,3) g1(1,3)=11 g(2,1)=g0(2,1) g1(2,1)=01 g(2,2)=g0(2,2) g1(2,2)=10 g(2,3)=g0(2,3) g1(2,3)=10 其状态为： S=(21) S0=(00),S1 =(01),S2 =(10),S3 =(11) v=(v1v2v3) u=(u1u2),第74页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(2) 卷积码的状态转移图 例10.5.2： 状态方程和输出方程为： 1=u1 2= u2 v1=u1+1+2 v2=u2+1 v2=u1+u2+1,第75页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(2) 卷积码的状态转移图 例10.5.2：,返回目录,第76页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(3) 卷积码的栅格图（篱笆图） 状态图不能反映出状态转移与时间的关系 栅格图/篱笆图：将开放型的状态转移图按时间顺序级联形成一个栅格图。 编码路径：状态序列在栅格图中形成的一条有向路径。 当有向路径始于全“0”状态 S0，又终于 S0 时，表明此时编码器又回到全“0”状态，这条始于 S0 又首次终于 S0 的路径是一个卷积码码字。,第77页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(3) 卷积码的栅格图（篱笆图） 红实线表示 U=0 时输入产生的转移分支； 兰虚线表示 U=1 时输入产生的转移分支。,第78页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.5 卷积码的状态转移图与栅格描述,(3) 卷积码的栅格图（篱笆图）,返回目录,第79页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.6 维特比译码的基本原理,(1) 维特比译码的度量 (2) 维特比译码和篱笆图 (3) 码参数和篱笆图的关系 (4) 最大似然译码最小距离译码 (5) 举例说明维特比译码工作原理 (6) 总结维特比算法的步骤,第80页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.6 维特比译码的基本原理,(1) 维特比译码的度量 待编码的信息序列 M：M=M0, M1, ML1； 编码器输入序列的总长度：k(L+m)； 编码器输出的码序列 C：C=C0, C1,CL+m1，其中每个子码Ci 含有 n 个码元； 经离散无记忆信道（DMC）传输后，译码器接收的序列 R：R=R0, R1,RL+m1；,第81页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.6 维特比译码的基本原理,(1) 维特比译码的度量 对于 DMC 信道： 码序列 C 的路径度量 M(R/C)：计算第 l 时刻到达状态 i 的最大似然路径的相似度log p(R/C)； 子码 Ci的度量（分支度量）M(Ri/Ci) ：计算第 l 时刻接收子码 Ri 相对于各子码的相似度 log p(Ri/Ci)。,返回目录,第82页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.6 维特比译码的基本原理,(2) 维特比译码和篱笆图 在维特比译码中，用状态图和篱笆图描述码的译码比较方便。 例10.6.1：(2,1,2)码 g(1,1)=g0(1,1) g1(1,1) g2(1,1) =111 g(1,2)=g0(1,2) g1(1,2) g2(1,2) =101 图10.6.1是 (2.1.2) 码的篱笆图：它由结点和分支构成。 共有 8 个结点（单元时刻），在图中的上方以 0,1,2,7 标号，0 结点表示第 0 个时刻。,参见图,第83页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.6 维特比译码的基本原理,(2) 维特比译码和篱笆图 编码器的工作过程：,返回,第84页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.6 维特比译码的基本原理,(2) 维特比译码和篱笆图 编码器的工作过程： 在起始的第 0 个到第 2 个时刻内，编码器根据输入的信息元不同从 S0 状态向四个可能的状态之一行进； 本例假定信息序列长为 L=5 个信息组，最后 m 个信息组是全 0，所以在篱笆图上的最后两个时刻向 S0 状态返回； 篱笆图上各连续分支组成了可能的路径，它们代表了各种可能的码序列； 由于可能的输入信息序列有 2kL=25=32 个，可能的路径有 32 条； 每个分支上的数字表示输出的子码。,参见图,返回目录,第85页,2019/11/27,Department of Electronics and Information, NCUT Song Peng,10.6 维特比译码的基本原理,(3) 码参数和篱笆图的关系 对 (n,k,m) 码而言，编码器的可能状态数目为 2km个，进入每个状态的分支数为 2k 个，从每个状态输出的分支数 2k 个，若输入信息序列长为 k(L+m)（后 mk 个码元全为 0），则篱笆图上共有 2kL 条不同的路径，相应于编