卷积码-第六章信道编码.ppt

2020 4 16 1 记住该记住的 忘记该忘记的 改变能改变的 接受不能改变的 2020 4 16 2 6 4 1卷积码的基本概念6 4 2卷积码的编码6 4 3卷积码的矩阵描述6 4 4卷积码的译码6 4 5卷积码的状态转移图与栅格描述6 4 6维特比译码的基本原理6 4 7软判决维特比译码6 4 8维特比译码的性能6 4 9维特比译码的应用 6 4卷积码 2020 4 16 3 回顾 信道编码的本质 通过增加冗余度 即将信息空间映射到更大的信道空间 在信道空间中绝大多数不是许用码字 以提高不同码字之间的差异程度 从而获得编码增益 回顾 编码与译码 一种编码方案就是从信息空间映射到更大的信道空间的一个映射可选的编码方案种类数极其巨大 其平均性能在码长趋于无穷时可以达到信道容量译码就是要根据接收的符号序列以最小的代价判断原发送码字 常用的有最小信息损失 最小差错概率 最大后验概率 最大似然 最小汉明距离等 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 4 回顾 线性分组码 由于编码方案数量巨大 完全的最优编码设计及任意编码的有限运算量译码都是很难做到的 因此引入了一系列的约束线性分组就是要引入的一个约束 原因是人们对线性系统的研究比较充分但仅有线性分组的约束还不够 编码设计和译码的规则性还是不够强利用域分析和生成多项式设计循环码回顾 线性分组码的译码 伴随式译码大数逻辑译码循环码的捕错译码 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 5 输入输出符号可以不同 可以用矢量表示 最常见的是取自同一域上的不同维数的矢量 例如信息符号流 Ai 映射到编码符号流 Bi 其中Ai为k维矢量 Bi为n维矢量 这样就是一个效率为k n的编码通常 输入符号流是经过信源编码的结果 已经变成二进制流或较小的域符号 因此k维输入矢量和n维输出矢量往往是人为地一种分割 6 4 1卷积码的基本概念 对信息流编码的模型 2020 4 16 6 利用分组码对信息流编码对信息序列按一定长度分段 对每一段分别进行分组编码 Bi fi Ai 当采用线性分组码时有 Bi GiAi当采用非时变线性分组码时 Bi GAi分组码编码中第i个输出编码码段只与第i个输入信息段有关 即编码在段间没有记忆性 6 4 1卷积码的基本概念 2020 4 16 7 从一般的角度讲 当前的编码符号完全可以不仅受当前的信息符号控制 而且还可受控于其它时刻的输入信息符号从因果的角度出发 可以只考虑受控于当前及历史上的输入符号流 换句话说 就是编码器可以是有记忆的因此输出的编码符号流也就具有了一定的相关性 6 4 1卷积码的基本概念 有记忆的编码方法 2020 4 16 8 这种相关性是广义的 一种典型的相关性就是马氏链过程编码器的记忆可以是有限的 也可以是无限的 有限记忆系统的输出总可模型化为马氏过程 可以用状态转移图来描述 无限记忆系统中可用状态转移图描述的也是马氏过程 对于线性系统而言 有限记忆和无限记忆就分别对应于FIR和IIR滤波器 当从滤波器角度看时 输入输出要用同一域中的元素 这样输入符号流应为GF p 上的k维矢量 输出符号流为GF p 上的n维矢量 6 4 1卷积码的基本概念 编码器的记忆性 2020 4 16 9 卷积码 又称连环码 首先由埃里亚斯 Elias 于1955年提出 1957年伍成克拉夫 Wozencraft 提出了一种有效译码算法 即序列译码 1963年梅西 Massey 提出了一种性能稍差 但比较实用的门限译码方法 由于这一实用性进展使卷积码从理论走向实用化 1967年维特比 Viterbi 提出了最大似然译码法 它对存储器级数较小的卷积码的译码很容易实现 人们后来称它为维特比算法或维特比译码 并被广泛地应用于现代通信中 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 10 分组码是把k个信息比特的序列编成n个比特的码组 每个码组的n k个校验位仅与本码组的k个信息位有关 而与其他码组无关 为了达到一定的纠错能力和编码效率 分组码的码组长度一般都比较大 编译码时必须把整个信息码组存储起来 由此产生的译码延时随n的增加而增加 卷积码是另外一种编码方法 它也是将k个信息比特编成n个比特 但k和n通常很小 特别适合以串行形式进行传输 时延小 与分组码不同 卷积码编码后的n个码元不仅与当前段的k个信息有关 还与前面的N 1段信息有关 编码过程中互相关联的码元个数为nN 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 11 卷积码与分组码的不同之处 在任意给定单元时刻 编码器输出的n个码元中 每一个码元不仅和此时刻输入的k个信息元有关 还与此前连续m个时刻输入的信息元有关 在同样的编码效率R下 卷积码的性能优于分组码 至少不低于分组码 卷积码的纠错性能随N的增加而增大 而差错率随N的增加而指数下降 在编码器复杂性相同的情况下 卷积码的性能优于分组码 但卷积码没有分组码那样严密的数学分析手段 目前大多是通过计算机进行好码的搜索 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 12 卷积码的译码方法代数译码 门限译码 译码延时是固定的 概率译码 序列译码 译码延时是随机的 维特比译码 译码延时是固定的 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 13 1 卷积码的生成序列 约束度和约束长度 例6 4 1 2 1 3 码该码的编码原理图示于图6 4 1 设待编码的信息序列为M 在对信息序列M进行编码之前 先将它每k个码元分成一组 在每单元时刻内 k个码元串行输入到编码器 编码器由 m 1 个移位寄存器组构成 每个移位寄存器组内有k级寄存器 g i j 表示常数乘法器 i 1 2 k j 1 2 n 共有n k个序列 当g i j 1时 常数乘法器为一条直通的连接线 当g i j 0时 连接线断开 每一个码元都是k m 1 个数据组合 每一个码字需用n k m 1 个系数才能描述 开关K在每一节拍中移动n次 每一节拍输入k个信息元而输出n个码元 6 4 1卷积码的基本概念 6 4卷积码 n 2 k 1 m 3 2020 4 16 14 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 15 信息序列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 与前两个时刻输入的信息元ml 2 1 以及前三个时刻ml 3 1 输入的信息元模2加后的和 g 1 2 表明 Cl 2 是由ml 1 ml 1 1 ml 2 1 和ml 3 1 的模2和 只要给定g i j 以后 就可以生成编码器输出的码元 称g 1 1 和g 1 2 为 2 1 3 卷积码的生成序列 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 16 第l个时刻的编码器输出为 上式表明 任一时刻编码器的输出可以由信息元与生成序列的离散卷积运算求出 这就是卷积码名称的由来 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 17 设M m0 1 m1 1 m2 1 m3 1 1011 则编码器两个输出端的序列分别是子码 在任一时刻单元 送入编码器一个信息元 k 1 编码器输出由2个 n 2 码元组成的一个码组 称之为子码 每个子码中的码元不仅与此时此刻的信息元有关 而且还与前m个 m 3 时刻的信息元有关 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 18 m 编码存储 本例m 3 N m 1 为编码的约束度 表明编码过程中相互约束的子码数 本例N 4 N n 编码约束长度 表明编码过程中相互约束的码元数 本例N n 8 本例是非系统码 在码序列C中的每个子码不是系统码字结构 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 19 例6 4 2 3 2 1 码n 3 k 2 m 1 它的任一子码有3个码元 每个码元由此时此刻的2个信息元和前一个时刻进入编码器的2个信息元模2运算和求出 这些信息元参加模2运算的规则由 n k 3 2 6个生成序列 n k m 1 3 2 2 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 6 4 1 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 20 若待编码的信息序列M m0 1 m0 2 m1 1 m1 2 ml 1 ml 2 则码序列C中的任一子码为 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 21 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 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 22 每个时刻单元输入编码器k 2个信息元 它们与前一个时刻进入编码器的2个信息元按式 6 4 1 所确定的卷积关系进行运算后 在输出端1 2 3分别得到该时刻子码中的3个码元 编码器由N 2个移位寄存器组和模2加法器构成 每个移位寄存器组含有k 2级移位寄存器 每级移位寄存器的输出按式 6 4 2 的规则引出后进行模2加的运算 本例也是非系统码形式的卷积码 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 23 推论 n k m 码完全由 n k 个生成序列所生成 每个生成序列中含有 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 按如下卷积关系求出 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 24 2 系统码形式的卷积码系统卷积码 是卷积码的一类 它的码序列中任一子码Cl 也是有n个码元 其前k位与待编码信息序列中的第l信息组ml i 相同 而后 n k 位监督元由生成序列生成 每个码中的前k位就是此时刻待编码的k位信息元 所以在生成序列g i j 中有 k k 个生成序列是固定的 即 6 4 1卷积码的基本概念 6 4卷积码 g i j 表示生成序列 i 1 2 k j 1 2 n 2020 4 16 25 只有k n k 个生成序列需要给定 以便确定每个子码中 n k 个监督元 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 26 任一子码由下式计算上式表明 在约束长度N内 每个子码中的 n k 个监督元与信息元的卷积关系 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 27 例6 4 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 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 28 任一时刻子码为 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 29 例6 4 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 相同 后一位的监督元由式 6 4 4 确定 即 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 30 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 6 4 1卷积码的基本概念 6 4卷积码 2020 4 16 31 1 串行输入 串行输出的编码电路 2 n k m级移位寄存器构成的并行编码电路 型编码电路 3 k m级移位寄存器编码电路 型编码电路 4 结论 6 4 2卷积码的编码 6 4卷积码 Here 2020 4 16 32 1 串行输入 串行输出的编码电路非系统码编码器 根据式 6 4 3 构造的是非系统编码器 图6 4 5是 n k m 非系统卷积码串行编码电路 6 4 2卷积码的编码 6 4卷积码 2020 4 16 33 6 4卷积码 6 4 2卷积码的编码 2020 4 16 34 系统码编码器 根据式 6 4 4 构造的是系统编码器 图6 4 6是 n k m 系统卷积码串行编码电路 6 4 2卷积码的编码 6 4卷积码 2020 4 16 35 6 4卷积码 6 4 2卷积码的编码 2020 4 16 36 2 n k m级移位寄存器构成的并行编码电路 型编码电路 这是系统码形式的一种编码电路 又称 型编码电路 将式 6 4 4 展开后可以改写为式 6 4 5 6 4 2卷积码的编码 6 4卷积码 2020 4 16 37 6 4 2卷积码的编码 2020 4 16 38 2 n k m级移位寄存器构成的并行编码电路 型编码电路 式 6 4 5 表明 在并入并出方式下 为了获得第l个子码的 n k 个监督元 需要 n k 个移位寄存器组 每一组移位寄存器的数目为m级 它们根据生成序列g i j 所确定的关系存储了第l个信息组相邻的前m个信息组 6 4 2卷积码的编码 6 4卷积码 2020 4 16 39 例6 4 5 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 根据式 6 4 5 第l个子码的监督元为Cl 3 ml 1 g0 1 3 ml 2 g0 2 3 ml 1 1 g1 1 3 ml 1 2 g1 2 3 ml 2 1 g2 1 3 ml 2 2 g2 2 3 6 4 2卷积码的编码 6 4卷积码 2020 4 16 40 将生成序列诸元素带入后有Cl 3 ml 1 ml 2 ml 1 2 ml 2 1 3 2 2 码的 型编码电路如图6 4 7所示 图6 4 8是 n k m 系统码 型编码电路 6 4 2卷积码的编码 6 4卷积码 2020 4 16 41 6 4卷积码 6 4 2卷积码的编码 2020 4 16 42 3 k m级移位寄存器编码电路 型编码电路 将式 6 4 4 展开后可以改写为式 6 4 6 式 6 4 6 表明 只需将第l时刻的k个信息元与前m个时刻的诸信息元按生成序列所确定的关系模2相加 就可以得到此时刻的 n k 个监督元 型编码电路由k个移位寄存器组构成 每一组有m级移位寄存器 它们分别寄存了前m时刻进入编码器的第一个到第k个信息元 6 4 2卷积码的编码 6 4卷积码 2020 4 16 43 例6 4 6 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 000 g 1 3 g0 1 3 g1 1 3 g2 1 3 101 由式 6 4 6 该码任一子码的监督元为Cl 2 ml 1 g0 1 2 ml 1 1 g1 1 2 ml 2 1 g2 1 2 ml 1 ml 1 1 Cl 3 ml 1 g0 1 3 ml 1 1 g1 1 3 ml 2 1 g2 1 3 ml 1 ml 2 1 其编码电路如图6 4 9所示 6 4 2卷积码的编码 6 4卷积码 2020 4 16 44 例6 4 7 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 由式 6 4 6 该码任一子码的监督元为Cl 3 ml 1 g0 1 3 ml 1 1 g1 1 3 ml 2 1 g2 1 3 ml 2 g0 2 3 ml 1 2 g1 2 3 ml 2 2 g2 2 3 ml 1 ml 2 1 ml 2 ml 1 2 其编码电路如图6 4 10所示 图6 4 11所示的是 n k m 码的 型编码电路 6 4 2卷积码的编码 6 4卷积码 2020 4 16 45 Cl 3 ml 1 ml 2 1 ml 2 ml 1 2 6 4 2卷积码的编码 6 4卷积码 2020 4 16 46 6 4卷积码 6 4 2卷积码的编码 2020 4 16 47 4 结论以上三种形式电路各有不同的特点 在一般的串行通信方式下 用串行编码电路比较方便 虽然它所需的电路级数较多 在并行通信时 若 n k k 采用 型编码电路较 型更为简单 否则 应采用 型编码电路 6 4 2卷积码的编码 6 4卷积码 2020 4 16 48 描述卷积码编译码的过程 可以用不同的描述方法 如矩阵法 码树法 状态图法 篱笆图 或称栅格图 法等 采用何种方法与卷积码的译码方法有很大关系 代数译码时 用矩阵法对译码原理的叙述和理解较方便 概率译码时 借助码树和篱笆图能更清晰地分析和了解译码过程和码的性能 1 卷积码的生成矩阵 2 卷积码的监督矩阵 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 49 1 卷积码的生成矩阵 例6 4 8 以 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 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 50 其中 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 51 将上式表示成矩阵方程 则有 即C T G TM T M G T或者C M G 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 52 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 53 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 54 码的生成矩阵G G 称为 2 1 3 码的生成矩阵 当输入的信息序列是有头无尾的半无限序列时 生成矩阵也是半无限矩阵 G 的下标就是这个含义 这时码序列C 亦为半无限序列 由式 6 4 7 可以看出 生成矩阵G 中 只要第一行G0G1G2G3确定以后 生成矩阵G 也就确定了 基本生成矩阵g 生成矩阵G 的第一行为该码的基本生成矩阵 2 1 3 码的基本生成矩阵g 为 g G0G1G2G300 g 中的每一个元素完全由码的生成序列g i j 诸元素所确定 编码器的输出码序列C 可根据生成矩阵得到 2 1 3 码 基本生成矩阵中的每个元素G0 G1 G2 G3都是 1 2 阶矩阵 k n k 1 n 2 元素的数目共4个 m 1 N 4 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 55 例6 4 9 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 由式 6 4 3 编码器的输出C为 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 56 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 57 写成矩阵方程 可得到 3 2 2 码的生成矩阵和基本生成矩阵 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 58 n k m 码的基本生成矩阵和生成矩阵 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 59 初始截断码组C 编码器初始状态全为0 编码器输入N m 1个信息组 即N k个信息元后 编码器输出的首N m 1个子码 即N n个码元 这首N m 1个子码组成的码组称为卷积码的初始截断码组 C C0C1C2 Cm 其中Ci Ci 1 Ci 2 Ci n i 0 1 2 m根据初始截断码组的定义C MG其中M m0m1m2 mm mi mi 1 mi 2 mi k i 0 1 2 m 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 60 初始截断码组的生成矩阵G基本生成矩阵gg G0G1G2 Gm 6 4 3卷积码的矩阵描述 6 4卷积码 2020 4 16 61 系统卷积码的生成矩阵 k k 个生成序列是已知的 即当i j时 g i j 1 当i j时 g i j 0 i 1 2 k j 1 2 k 6 4 3卷积码的矩阵描述 6 4卷积码 每个子码中的前k个码元与相应的k个信息元相同 后 n k 个监督元由信息序列与生成序列的卷积运算得到 系统卷积码的初始截断码组的生成矩阵为 2020 4 16 62 其中Ik是k阶单位方阵Pl是k n k 阶阵 l 0 1 2 m系统卷积码初始截断码组的基本生成矩阵为g