基于MATLAB的卷积码的分析与应用.doc

基于 MATLAB 的卷积码的分析与应用 东北大学本科毕业设计 论文 毕业设计 论文 任务 书 I 毕业设计 论文 任务书毕业设计 论文 任务书 毕业设计 论文 题目 毕业设计 论文 题目 基于基于 MATLAB 的卷积码的分析与应用的卷积码的分析与应用 设计设计 论文论文 的基本内容 的基本内容 1 介绍纠错控制编码的相关理论 重点分析卷积码的相关编码和解码理 论 2 在 MATLAB 中编写卷积码的编码和解码程序 模拟通信系统 针对 TD SCDMA 系统中的卷积码进行仿真 3 进行纠错译码验证 纠错比较及误码率相关因素分析 毕业设计 论文 专题部分 毕业设计 论文 专题部分 题目 题目 设计或论文专题的基本内容 设计或论文专题的基本内容 学生接受毕业设计 论文 题目日期学生接受毕业设计 论文 题目日期 第第 2 周周 指导教师签字 指导教师签字 2010 年年 3 月月 8 日日 东北大学本科毕业设计 论文 摘 要 II 基于 MATLAB 的卷积码的分析与应用 摘 要 随着现代通信的发展 特别是在未来 4G 通信网络中 高速信息传输和高 可靠性传输成为信息传输的两个主要方面 而可靠性尤其重要 因为信道状况 的恶劣 信号不可避免会受到干扰而出错 为实现可靠性通信 主要有两种途 径 一种是增加发送信号的功率 提高接收端的信号噪声比 另一种是采用编 码的方法对信道差错进行控制 前者常常受条件限制 不是所有情况都能采用 因此差错控制编码得到了广泛应用 介绍了多种信道编码方式 着重介绍了卷积码的编码方法和解码方式 介 绍了 MATLAB 的使用方法 编程方法 语句 变量 函数 矩阵等 介绍了 TD SCDMA 通信系统和该系统下的卷积码 搭建了系统通信模型 编写卷积码 的编码和解码程序 用 MATLAB 仿真软件对 TD SCDMA 系统的卷积码编解码 进行仿真 对其纠正错码性能进行验证 并且对误码率进行仿真和分析 卷积 码的编码解码方式有很多 重点仿真 Viterbi 算法 Viterbi 算法就是利用卷积码 编码器的格图来计算路径度量 选择从起始时刻到终止时刻的惟一幸存路径作 为最大似然路径 沿着最大似然路径回溯到开始时刻 所走过的路径对应的编 码输出就是最大似然译码输出序列 它是一种最大似然译码方法 当编码约束 长度不大 或者误码率要求不是很高的情况下 Viterbi 译码器设备比较简单 计算速度快 因而 Viterbi 译码器被广泛应用于各种领域 关键词 卷积码 信道编码 TD SCDMA MATLAB 东北大学本科毕业设计 论文 目 录 III 目 录 毕业设计 论文 任务书毕业设计 论文 任务书 I 摘摘 要要 II Abstract III 第第 1 章章 绪绪 论论 1 1 1 课题研究的背景和来源 1 1 2 主要内容 2 第第 2 章章 相关理论介绍相关理论介绍 3 2 1 信道编码 3 2 1 1 信道编码的分类 3 2 1 2 编码效率 3 2 2 线性分组码 3 2 3 循环码 5 2 4 卷积码 6 2 4 1 卷积码简介 7 2 4 2 卷积码的编码 7 2 4 3 卷积码的解码 13 第第 3 章章 MATLAB 应用应用 21 3 1 数和算术的表示方法 21 3 2 向量与矩阵运算 21 3 2 1 通过语句和函数产生 21 3 2 2 矩阵操作 22 3 3 矩阵的基本运算 22 3 3 1 矩阵乘法 22 3 3 2 矩阵除法 23 3 4 MATLAB 编程 23 3 4 1 关系运算 23 3 4 2 控制流 25 第第 4 章章 卷积码的设计与仿真卷积码的设计与仿真 27 4 1 TD SCDMA 系统 27 4 1 1 系统简介 27 4 1 2 仿真通信系统模型 27 东北大学本科毕业设计 论文 目 录 IV 4 2 卷积编码设计 28 4 3 编解码程序实现 29 4 3 1 卷积码编解码设计 29 4 3 2 卷积码编解码程序设计 32 4 4 卷积码实现 34 4 4 1 2 1 卷积码的仿真研究 34 4 4 2 3 1 卷积码的仿真研究 36 4 5 卷积码误码率 38 第第 5 章章 结结 论论 41 5 1 总结 41 5 2 展望 41 参考文献参考文献 43 致致 谢谢 45 东北大学本科毕业设计 论文 第 1 章 绪 论 1 第 1 章 绪 论 1 1 课题研究的背景和来源 纠错编码己有五十几年历史 早在 1948 年 香农 Shannon 在他的开创性 论文 通信的数学理论 中 首次阐明了在有扰信道中实现可靠通信的方法 提 出了著名的有扰信道编码定理 奠定了纠错码的基石 以后 纠错码受到了越 来越多的通信和数学工作者 特别是数学家的重视 使纠错码无论在理论上还 是在实际中都得到了飞速发展 1 随着现代通信的发展 特别是在未来 4G 通信网络中 高速信息传输和高 可靠性传输成为信息传输的两个主要方面 而可靠性尤其重要 因为信道状况 的恶劣 信号不可避免会受到干扰而出错 为实现可靠性通信 主要有两种途 径 一种是增加发送信号的功率 提高接收端的信号噪声比 另一种是采用编 码的方法对信道差错进行控制 前者常常受条件限制 不是所有情况都能采用 例如卫星通信系统以很远的距离传送数据 由于衰落 噪声和干扰等的影响 信号在传输过程中将产生严重的畸变 如果要求信号具有尽可能大的能量 卫 星体积和载重就会大大增加 使成本相对于原来大大增加 所以不可能给信号 提供太大的能量 而建立在香农基础上的编码理论正可以解决这个问题 使得 成本降低 实用性增强 前向纠错技术 FEC 特别是卷积编码是当今无线数字通 信系统的一个十分重要的组成部分 它是一种有效的信道编码方法 在实际中 广泛应用 目前无线数字通信系统都采用某一形式的卷积编码如在 W CDMA DVB S DVB T IEE802 11 系统中都使用了卷积编码 由于其出色的 纠错性能 一般在级联码中作为内码使用 从而保证外码有效地工作 大大提 高了整个系统的纠错能力 而 Viterbi 译码器正是针对卷积码的一种最佳译码方 法 2 CDMA 系统以其容量大 抗干扰能力强的特点成为第三代移动通信系统的 标准 CDMA 系统的信道编码大多采用卷积编码 这是因为卷积码的纠错能力 强 不仅能纠随机差错 还可以纠突发差错 在 CDMA 系统中 对卷积码的译 码采用 Viterbi 算法 它是一种最大似然译码方法 当编码约束长度不大 或者 误码率要求不是很高的情况下 Viterbi 译码器设备比较简单 计算速度快 因 而 Viterbi 译码器被广泛应用于各种领域 现代通信中 随着信号序列的传输速率的不断提高 要求卷积码译码的速 度也要不断提高 Viterbi 译码由于充分利用信号序列统计概率的特性而具有最 东北大学本科毕业设计 论文 第 1 章 绪 论 2 佳性能 信道编码的应用领域主要包括深空通信 卫星通信 数据传输 移动 通信 文件传输和数字音频 视频传输等 卷积编码作为信道编码方式中最重要 一种 被广泛使用于卫星通信 无人机测控 深空通信 移动通信 水声通信 等数字通信系统 甚至被采纳到某些无线通信的标准之中 如 GSM IS 95 和 CDMA2000 的标准 在卫星通信中 码率为 1 2 和 1 3 的卷积码己经成为商业 卫星通信系统中的标准编码方法 在无人机测控中 与传统的信道改善控制指 令传输误码的方式比较 利用卷积码对无人机遥控信道进行编码 在一定信道 条件下 其控制指令传输误码有明显下降 在码速率不增加的条件下 无人机 系统控制指令传输可靠性得到明显改善 3 随着数字通信系统业务的不断拓展 随着卷积编码理论的不断发展和完善 卷积码的应用必将越来越广泛 卷积码在现在通信系统中的作用必将越来越大 1 2 主要内容 论文框架 第一章介绍了卷积码的研究背景 第二章介绍了卷积码的相关 理论 信道编码 线性分组码 循环码及卷积码的表示方式 编码方式 解码 方式 第三章介绍了实现卷积码仿真所需要的软件方式 第四章进行卷积码设 计与仿真 介绍了 TD SCDMA 系统下的卷积码 对卷积码性能进行了研究 主要内容 介绍了信道编码方式 着重研究列举了卷积码的编码方法和解 码方式 介绍了 MATLAB 的使用方法和 TD SCDMA 系统 编写卷积码的编码 和解码程序 并且用 MATLAB 仿真软件对 TD SCDMA 系统的卷积码编解码进 行仿真 Viterbi 算法就是利用卷积码编码器的格图来计算路径度量 选择从起 始时刻到终止时刻的惟一幸存路径作为最大似然路径 沿着最大似然路径回溯 到开始时刻 所走过的路径对应的编码输出就是最大似然译码输出序列 它是 一种最大似然译码方法 当编码约束长度不大 或者误码率要求不是很高的情 况下 Viterbi 译码器设备比较简单 计算速度快 因而 Viterbi 译码器被广泛应 用于各种领域 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 3 第 2 章 相关理论介绍 2 1 信道编码 在数字通信中 根据不同的目的 编码可分为信源编码和信道编码 信源 编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码 信道编码是为了降低误码率 提高数字通信的可靠性而采取的编码 信道编码 现在已经得到广泛的应用 2 1 1 信道编码的分类 信道编码有多种分类方式 主要有按照关系 范围及用途三种 1 根据纠错码各码组信息元和监督元的函数关系 可分为线性码和非线性 码 如果函数关系是线性的 即满足一组线性方程式 则称为线性码 否则为 非线性码 2 根据上述关系涉及的范围 可分为分组码和卷积码 分组码的各码元仅 与本组的信息元有关 卷积码中的码元不仅与本组的信息元有关 而且还与前 面若干组的信息元有关 3 根据码的用途 可分为检错码和纠错码 检错码以检错为目的 不一定 能纠错 而纠错码以纠错为目的 一定能检错 4 5 2 1 2 编码效率 用差错控制编码提高通信系统的可靠性 是以降低有效性为代价换来的 定义编码效率尺来衡量有效性 R k n 其中 k 是信息元的个数 n 为码长 对纠错码的基本要求是 检错和纠错能力尽量强 编码效率尽量高 编码规律 尽量简单 2 2 线性分组码 线性分组码中的线性是指码组中码元间的约束关系是线性的 而分组则是 对编码方法而言 即编码时将每 k 个信息位分为一组进行独立处理 变换成长 度为 n n k 的二进制码组 线性分组码的编码过程可以简单描述成一个矢量和一个矩阵相乘的结果 即 C mG 其中 C 是经过编码后得到的 n 维编码输出 c0 c1 cn 1 m 是信息序 列分组 m0 m1 mk 1 G 是由 k 个 n 维矢量 g0 g1 gk 1 构成的矩阵 线性分组码编码问题的核心就是如何在 n 维线性空间 Vn中找出满足一定要 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 4 求的 由 2k个矢量组成的 k 维线性子空间 也就是说 在满足给定码字最小距 离或编码速率的前提下 如何根据已知的 k 个信息比特求得 r n k 个校验比特 通过对码字生成矩阵 G 的初等变换 可以得到惟一的行简化梯形矩阵 再 经过列交换可以得到如下形式的生成矩阵 2 1 I p ppp ppp ppp ggg ggg ggg g g g kk knk knkkk kn kn nkkk n n k G 1 11 10 1 1 11 10 1 1 01 00 0 1 11 10 1 1 11 10 1 1 01 00 0 1 1 0 100 010 001 其中 P 是 k n k 的矩阵 这种形式的生成矩阵 G 称为标准生成矩阵 按照标准矩阵生成的码字为 2 2 mmm ppp k kn IPmmGc 110 110 其中前 n k 1 个比特为校验比特 其值为 2 3 10 1 1 1 1 0 0 kni p m p m p m p ik k iii 后面 k 个比特就是信息比特 这种在生成码字中包含信息序列的编码码字 称为线性系统分组码 简称为系统码 系统码的编码结构相当简单 以系统 7 4 为例 其生成矩阵为 2 4 1000110 0100011 0010111 0001101 G 系统码的编码结构非常简单 比如对系统 7 4 码 根据上面的生成矩阵 G 只要在输入编码器的每组 k 个数字的后面 附加上 n k 个监督码元就可得到 所编出的 n 个码字 系统 7 4 码对应的监督矩阵为 2 5 1011100 1110010 0111001 H 假如发送的码字为 c 1001011 而接收到的码字为 Y 1001001 信道传 输中产生的错误为 e 0000010 由 S y HT可求出 S 1 1 1 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 5 2 3 循环码 循环码是线性分组码中最重要的一类 循环码是指码集合中的任一码字经 过循环移位后得到的码字仍然是码集合中的码字 循环码的码字可以用矢量的 形式表示 即 2 6 110cccn c 也可用码多项式表示 即 2 7 xccc n n xxc 1 110 循环码 c 向右移一位的码字可由下式得出 2 8 1mod 1 2 2 1011 2 10 xxcxcxccxcxcxc nn nn n n xxc 循环码可由它的生成多项式 2 9 x g x gg kn kn xg 10 唯一确定 信息序列也可以表示成多项式 2 10 xmxmm k k xm 1 110 那么生成码字可表示成 2 11 1mod x n xgxmxc 由于多项式乘法等价于多项式系数的卷积 故 2 12 g mc j kn j jii 0 循环码编码则可以通过移位寄存器组成的乘法电路结构实现 由数论知识可知 n k 循环码的生成多项式 g x 一定是 xn 1 的 n k 次因式 2 13 1 10 10 xhxhhxgxggx k k kn kn n xhxg 反之 若 g x 为 n k 次多项式 且 xn 1 能被 g x 整除 则 g x 一定能生成一个 n k 循环码 以 g x 为生成多项式所构成的 n k 循环码中 g x x g x xk 1 g x 2 14 等七个多项式必定是线性无关 则循环码的生成矩阵 G 为 2 15 ggg ggg ggg kn kn kn G 0 0 0 0 0 0 00 10 10 10 循环码的编码也可以通过移位寄存器组成的除法电路结构实现 以 7 4 循 环码为例 选 7 4 码生成矩阵 g x g3 x 1 x x3 2 16 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 6 它除尽 1 x7 若输入信息码元为 m x 1 x3 则由 2 17 1mod 1 3263347 xxxxxxx xxxm kn 因此 码多项式为 2 18 xxxxxxx xxxmxrxc kn6323472 1 对应的码字为 C 0 1 1 1 0 0 1 其中最右边的 4 位是信息元 详细的编码过程 如下 1 三级移位寄存器初始状态为 000 此时门打开 信息组以 2 19 xxxxx xm kn63347 1 即 1001 次序分两路进入编码器 一路直接输出 另一路送入 g x 除法电路 2 经 4 次移位后 信息组 1001 全部输出 它就是系统码的 4 个信息元 另一路则将全部信息元送入 g x 除法电路 并完成除法运算 这时移位寄存器 中的状态就是余式 r x 系数 即为码的监督元 c0 c1 c2 3 输出开关倒向上面 2 经 3 次移位 移位器由监督元 c0 c1 c2 跟在信息 元 c3 c4 c5 c6 后面依次输出为 C c0 c1 c2 c3 c4 c5 c6 0111001 4 送入第二组信息元 重复上述过程 该码最小距离为 3 它能纠正 7 个码元一组中任何单个错误 这 7 种错误 图样和全零矢量一起组成译码表的陪集首 它组成了所有可能纠正的图样 现 假设接收的多项式为 2 20 x y x y x y x yy xy 6 6 3 3 2 210 即 Y 1 1 1 1 0 0 1 译码器工作步骤如下 1 将移位寄存器清零 2 输入 Y 分两路进入译码器 一路进入缓存器 另一路经门 1 进入伴随 式计算电路与寄存器 并分别计算 S0 S1 S2值 3 在输出 Y 的同时 S0 S1 S2依次循环移位 无错误时 错误检测电路 无输出 最后输出的码字 C 的码元与 Y 相对应码元一致 有错误时 S0 S2 1 S1 0 错误检测电路输出为 1 它正好与 Y 中错误位在输出端的模 2 加 中相遇 并予以纠正后再输出 2 4 卷积码 相对于分组码而言 分组码的编码和译码都是各分组独立的进行 彼此不 相关联 而卷积码的每一组不仅与本组的 k 位信息位有关 还和这以前各组的 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 7 信息位有关 卷积码的结构比较复杂 但 n 和 k 的值相对于分组码来说比较小 译码也相对比较容易些 2 4 1 卷积码简介 非分组码的卷积码的编码器是在任一段规定时间内产生 n 个码元 但它不 仅取决于这段时间中的 k 个信息位 还取决于前 K 1 段规定时间内的信息位 这 K 段时间内的码元数目为 K k 称参数 K 为卷积码的约束长度 每 k 个比特 输入 得到 n 比特输出 编码效率为 k n 约束长度为 K 在 k 1 的条件下 移 位寄存器级数 m K 1 卷积码一般可用 n k K 来表示 其中 k 为输入码元数 n 为输出码元数 而 K 则为编码器的约束长度 典型的卷积码一般选 n 和 k k n 值较小 但约 束长度 K 可取较大值 K 10 以获得既简单又高性能的信道编码 6 卷积码是 1955 年 Elias 最早提出 1957 年 Wozencraft 提出了序列译码 1963 年 Massey 提出了一种性能稍差 但比较实用的门限译码方法 1967 年维 特比 Viterbi 提出了最大似然译码 它对存储器级数较小的卷积码的译码很容易 实现 称为维特比算法或维特比译码 2 4 2 卷积码的编码 卷积码的编码器是由一个有 k 个输入位 端 n 个输出位 端 且具有 m 级 移位寄存器所构成的有限状态的有记忆系统 通常称它为时序网络 2 4 2 1 卷积码的解析表示法 一个二元 2 1 4 卷积码的编码器 它是由 k 1 即一个输入位 端 n 2 即两个输出位 端 K 4 m 3 即三级移位寄存器所组成的有限状态的有记忆系 统 1 离散卷积 若输入信息序列为 这里的卷积码是 u0首先输入 2 21 210uuuu 则对应输出为两个码字序列 2 22 2 1 0 2 1 0 cccc cccc 其相应编码方程可写为 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 8 2 23 ccc g uc g uc 其中 表示卷积运算 g g 表示编码器的两个脉冲冲击响应 即编码可由 输入信息序列 u 和编码器的两个冲击响应的卷积得到 故称为卷积码 7 这里 的脉冲冲击响应是指 当输入信息为 u 100 时 所观察到的两个输出序列值 由于编码器有 m 3 级寄存器 故冲激响应至多可持续到 K m 1 3 1 4 位 且 可写成 2 24 1111 1011 g g 在一般情况下有 2 25 m 1 0 m 1 0 gggg gggg 经编码器后 两个输出序列合并为一个输出码字序列为 2 26 1 1 0 0 ccccc 若输入信息序列为 2 27 10111 u 则有 2 28 10000001 1011 10111 c 2 29 11011101 1111 10111 c 最后输出的码字为 2 30 0100111101000101 c 2 生成矩阵 上述冲激响应 g g 又称为生成序列 若将该生成序列 g g 按如下方法 排列 构成如下生成矩阵 当 K 4 m 3 时 2 31 3 3 2 2 1 1 0 0 3 3 2 2 1 1 0 0 3 3 2 2 1 1 0 0 gggggggg gggggggg gggggggg G 上述矩阵中 其中空白部分均为 0 则上述编码方程可改为矩阵形式 2 32 G uc 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 9 G 为卷积码的生成矩阵 若输入信息序列为一无限序列时 即 u 10111 生 成矩阵则为一个半无限矩阵 即有起点无终点 因此称它为半无限 若 2 33 1111 1011 10111 ggu 则 2 34 1100010101000111 11110111 11110111 11110111 11110111 11110111 10111 Guc 3 码多项式 若将生成序列表达成多项式形式 有 2 35 xxx g xx g 32 32 11111 11011 输入信息序列也可表达为多项式形式 2 36 xxxu 432 110111 则卷积码可以用下列码多项式形式表达 2 37 10000001 1 1 1 11 7 765432 76536542432 32432 22222 x xxxxxx xxxxxxxxxxx xxxxxc 2 38 11011101 1 1 1 11 7 7543 76536542543432 32432 x xxxxx xxxxxxxxxxxxxxx xxxxxxc 2 4 2 2 卷积码的图形表示法 卷积码的图形表示法有很多种 在此介绍最常用的三种 状态图表示法 树图表示法 网格图表示法 1 状态图表示法 卷积编码器在下一时刻的输出取决于编码器当前的状态及下一时刻的输入 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 10 当前状态取决于编码器在当时各移位寄存器所存储的内容 称编码器的各移位 寄存器在任一时刻的存数 0 或 1 为编码器在该时刻的一个状态 编码器的总可 能状态数是 2mk个 对于 n 2 k 1 K 3 m 2 的 2 1 3 卷积编码器 则其 总的可能状态数是 4 个 设以 Si表示某状态 i 0 1 2 3 在某 tj时刻 此 2 1 3 卷积编码器的输出表述为 2 39 uuc uuuc 2 jj j 2 j1 jj j 它取决于 uj uj 1及 uj 2三个值 其中 uj是当前的输入值 uj 1及 uj 2是以前输 入的两个值 若要求出下一个 tj 1时刻的输出值 则要知道当前的 uj及 uj 1值 当输入下一时刻的 uj 1值时 就可以求出下一个 tj 1时刻的 c j 1及 c j 1值 所 以 为决定下一个 tj 1时刻编码器的输出 此 2 1 3 卷积编码器在当前 tj时 刻的状态用 Si uj uj 1 i 0 1 2 3 表示即可 如表 2 1 所示 表 2 1 状态转移表 ujuj 1Si 00S0 a 10S0 b 01S0 c 11S0 d 设输入信息序列为 2 40 1011100 210 uuuuu i 1 首先 对移位寄存器清洗 复 0 移存器状态为 00 2 输入 u0 1 输出 故 移位寄 1001 0 c 101 0 c 11 0 00 ccc 存器状态改为 10 3 输入 u1 0 则根据 010 可算出 故 移位寄存 0 1 1 1 cc 10 1 c 器状态改为 01 4 输入 u2 1 则根据 101 可算出 故 移位寄存 0 0 2 2 cc 00 2 c 器状态改为 10 5 输入 u3 1 则根据 110 可算出 故 移位寄存 1 0 3 3 cc 01 3 c 器状态改为 11 6 输入 u4 1 则根据 111 可算出 故 移位寄存 0 1 4 4 cc 10 4 c 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 11 器状态改为 11 7 输入 u5 0 则根据 011 可算出 故 移位寄存 1 0 5 5 cc 01 5 c 器状态改为 01 8 输入 u6 0 则根据 001 可算出 故 移位寄存 1 1 6 6 cc 11 6 c 器状态改为 00 9 输入 u7 0 则根据 000 可算出 故 移位寄存 0 0 7 7 cc 00 7 c 器状态改为 00 按照上述步骤 可画出状态图如图 2 1 所示 图 2 1 2 1 3 卷积码状态图 图 2 1 中 4 个圆圈中的数字表示状态 状态之间的连线与箭头表示转移方 向 称作分支 分支上的数字表示由一个状态到另一个状态转移时的输出码字 而括号中数字表示相应的输入信息数字 例如若当前状态为 11 即 S3 11 则 当下一时刻的输入信息位为 u1 0 时 输出码字 c1 01 下一刻的状态为 S2 01 若输入信息位 u1 1 则输出码字为 c1 10 下一时刻的状态仍为 S3 11 2 树图表示法 如果要展示出编码器的输入 输出所有可能情况 则可采用树图来描述 它是 将上述编码器的状态图按时间展开而成的 如图 2 2 所示 由图 2 2 可见 若设初始状态 S0 00 作为树根 对每个时刻可能的输入进 行分支 若分支的节点级数用 表示 则当时 有两个可能分支 若l0 l u0 0 则向上 即 0 分支向上 若 u0 1 则向下 即 1 分支向下 它们都达到下 一个一级节点 当时 对每个一级节点根据 u1的取值也将产生上 1 l1 l 下两个分支 并推进到相应的二级节点 依此类推 就可以得到一个无2 l 限延伸的树状结构图 图 2 2 中各分支上的数字表示相应输出的码字 字段 表示编码器所处的状态 dcba a 00 0 00 S0 d 11 10 1 S3 11 1 01 1 b 10 S1 c S2 01 00 1 10 0 11 0 01 0 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 12 对于特定输入信息序列 u 10111000 2 41 相应的输出 c 11 10 00 01 10 01 11 00 2 42 图 2 2 2 1 3 卷积码树图表示 3 网格图表示法 网格图的纵坐标表示所有状态 横坐标表示时间 这类网格图描述法在卷 积码的概率译码中 特别在维特比译码中特别有用 它综合了状态图与树图的 优点 即网格图既具有状态图结构简单 又具有树图的时序关系清晰特点 以 2 1 3 卷积码为例 当节点级数大于时 状态3121 ml 呈现重复 利用这种重复 即如果将图 2 2 中以后 码树上处dcba 3 l 于同一状态的同一节点折叠起来加以合并 就可以得到纵深宽度 或称高度 为 2km 22 4 的网格图 如图 2 3 所示 图 2 3 中实线表示输入为 0 时所走的分支 虚线表示输入为 1 时所走的分 支 由图 2 3 可见这个图实质上是将图 2 2 的树图重复部分合并而成的 它自 即第二级节点开始 从同一状态出发所延伸的树结构完全一样 因此网格2 l 00 11 10 01 11 00 01 10 a b c d 00 a 11 10 b 01 11 c 00 01 d 10 1 00 a 11 00 a 11 0 分支 树根 1 分支 00 11 10 01 11 00 01 10 a b c d 10 b 01 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 13 图能更为简洁地表示卷积码 8 如果任意给定一个输入信息序列 则它在网格图中就必将存在一条特定的 路径 比如 u 1011100 其输出编码为 c 11 10 00 01 10 01 11 即为上述网 格图 2 3 中粗黑线所表示的路径 网格图是研究卷积码最大似然译码维特比算 法的重要工具 图 2 3 2 1 3 卷积码网格图表示法 2 4 3 卷积码的解码 卷积码的解码方式可以分为两类 代数解码和概率解码 代数解码是利用 编码本身的代数结构进行解码 不考虑信道的统计特性 大数逻辑解码 又称 门限解码 是卷积码代数解码的最主要一种方法 也可以应用于循环码的解码 大数逻辑解码对于约束长度较短的卷积码最为有效 而且设备较简单 概率解 码 又称最大似然解码 则是基于信道的统计特性和卷积码的特点进行计算 首 先由沃曾克拉夫特针对无记忆信道提出的序贯解码就是概率解码方法之一 另 一种概率解码方法是维特比 Viterbi 算法 当码的约束长度较短时 它比序贯解 码算法的效率更高 速度更快 目前得到广泛的应用 9 10 2 4 3 1 大数逻辑解码 卷积码的大数逻辑解码是基于卷积码的代数表述运算的 其一般工作原理 如图 2 4 所示 首先将接受信息位暂存于移存器中 并从接收码元的信息位和监督位计算 校正子 然后 将计算得出的校正子暂存 并用它来检测错码的位置 在信息 a 00 00 00 00 00 00 00 00 11 11 11 11 11 11 11 b 10 10 11 00 11 00 11 00 10 10 10 c 01 01 01 01 01 01 01 01 01 d 11 10 10 10 l 0 l 1 l 2 l 3 l 4 l 5 l 6 l 7 l 0 1 2 3 4 5 6 7 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 14 位移存器输出端 接有一个模 2 加电路 当检测到输出的信息位有错时 在输 出的信息为上加 1 从而纠正之 11 在图 2 5 中画出了一个 2 1 6 卷积码编码器 图 2 4 大数逻辑解码一般工作原理 图 2 5 2 1 6 卷积码编码器原理方框图 图 2 5 中编码器的监督位和信息位的关系如下 当输入序列为 b1b2b3b4时 监督位为 2 43 63216 5215 414 33 22 11 bbbbc bbbc bbc bc bc bc 其监督关系式如下 b1b2b3b4b5b6 ci 输出 bi bici 输入 输入 输出 监督位 信息位 错码检测 校正子移存器 校正子计算 信息位移存器 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 15 2 44 bbbbcs bbbcs bbcs bcs bcs bcs 632166 52155 4144 333 222 111 Si i 1 6 称为校正子 经过简单线性变换 可以得出如下正交校验方程组 2 45 bbbccss bbbcs bbcs bcs 6316262 52155 4144 111 只有信息位 b1出现在每个方程中 监督位和其他信息位均最多只出现一次 因此 在接收端解码时 考察 b1 c1至 b6 c6等 12 个码元 仅当 b1出错时 才可 能有 3 个或 3 个以上方程等于 1 从而能够纠正 b1的错误 按照这一原理画 出的此 2 1 6 卷积码解码器原理方框图示于图 2 6 中 由图 2 6 可见 当信息位出现一个错码时 仅当它位于信息位移存器的第 6 3 2 和 1 级时 才使校正子等于 1 因此 这时的校正子序列为 100111 反之 当监督位出现一个错码时 校正子序列将为 100000 由此可见 当校正 子序列中出现第一个 1 时 表示已经检出一个错码 后面的几位校正子则指出 是信息位错了 还是监督位错了 门限电路将这 4 个电压 非模 2 相加 当相加 结果大 于或等于 3 时 门限电路输出 1 它除了送到输出端的模 2 加法器纠正输出码 元 b1的错码外 还送到校正子移存器纠正其中错误 19 21 b1b2b3b4b5b6 输出 输入 s6 s2s1s3s4s5 门限电路 1 的个数大于等于 3 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 16 图 2 6 2 1 6 卷积码解码器原理方框图 此卷积码除了能够纠正两位在约束长度中的随机错误外 还能纠正部分多 于两位的错误 为了克服突发错误 可以采用更长的约束长度和在约束长度中 能纠正更多错误的码 2 4 3 2 维特比解码算法 维特比解码算法是维特比于 1967 年提出的 这种算法的基本原理是将接收 到的信号序列和所有可能的发送信号序列比较 选择其中汉明距离最小的序列 认为是当前发送信号序列 若发送一个 k 位序列 则有 2k种可能的发送序列 当 K 较大时 存储量太大 使实用受到限制 维特比算法对此作了简化 使之 能够实用 一种 3 1 3 卷积码编码器方框图如图 2 7 图 2 7 一种 3 1 3 卷积码编码器方框图 该 3 1 3 卷积码的状态图如图 2 8 图 2 8 3 1 3 卷积码状态图 111 1 110 1 b 001 0 d 000 0 a 100 1 101 1 010 0 011 0 c 输入 bi M2 M3M1 bi 2 bi 1bi 编码输出 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 17 设发送信息位为 1101 为了使图 2 7 中移存器的信息位全部移出 需要 在信息位后面加入三个 0 故经过编码后的发送序列为 111 110 010 100 001 011 000 并且假设接收序列为 111 010 010 110 001 011 000 其中第 4 和第 11 个码元为错码 由于这是一个 n k N 3 1 3 卷积码 发送序列的约束度 N 3 所以首先需要考察 nN 9 该 3 1 3 卷积码网格图如图 2 9 图 2 9 3 1 3 卷积码网格图 该 3 1 3 卷积码编码举例如图 2 10 图 2 10 3 1 3 卷积码编码路径举例 第一步考察接收序列前 9 位 111 010 010 由此码的网格图 2 10 可见 沿 111 111 111 111 111 000 000 000 000 000 a a 011 011 100 100 100 011 b b 001 001 001 001 c c 010 010 010 110 110 110 110 d d 101 101 101 a 111 001 100 b 110 c 010 d 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 18 路径每一级有 4 种状态 a b c d 每种状态只有两条路径可以到达 故 4 种状态 有 8 条到达路径 现在比较网格图中的这 8 条路径和接收序列之间的汉明距离 例如 由出发点状态 a 经过三级路径后到达状态 a 的两条路径中上面一条 为 000 000 000 它和接收序列 111 010 010 的汉明距离等于 5 下面一条为 111 001 011 它和接收序列的汉明距离等于 3 同样 由出发点状态 a 经过 三级路径后到达状态 b c d 的路径分别都有两条 故总共有 8 条路径 在表 2 2 中列出了这 8 条路径和汉明距离 表 2 2 维特比算法解码第一步计算结果 该 3 1 3 卷积码的树图如图 2 11 所示 序号路径对应序列汉明距离幸存否 1aaaa000 000 0005否 2abca111 001 0113是 3aaab000 000 1116否 4abcb111 001 1004是 5aabc000 111 0017否 6abdc111 110 0101是 7aabd000 111 1106否 8abdd111 110 1014是 000 111 001 110 011 100 010 101 a b c d 000 a 111 001 b 110 011 c 100 010 d 101 1 000 a 111 000 a 111 0 分支 树根 1 分支 000 111 001 110 011 100 010 101 a b c d 001 b 110 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 19 图 2 11 3 1 3 卷积码编码树图 现在将到达每个状态的两条路径的汉明距离作比较 将距离小的一条路径 保留 称为幸存路径 若两条路径的汉明距离相同 则可以任意保存一条 这 样就剩下 4 条路径了 即表中第 2 4 6 和 8 条路径 第二步将继续考察接收序列中的后继 3 位 110 现在计算 4 条幸存路径上 增加一级后的 8 条可能路径的汉明距离 计算结果列于表 2 3 中 表 2 3 维特比算法解码第二步计算结果 序 号 路径原幸存路 径的距离 新增路 径段 新增距 离 总距离幸存否 1abca a3aa25否 2abdc a1ca23是 3abca b3ab14否 4abdc b1cb12是 5abcb c4bc37否 6abdd c4dc15是 7abcb d4bd04是 8abdd d4dd26否 表 2 3 中最小的总距离等于 2 其路径是 abdc b 相应序列为 111 110 010 100 它和发送序列相同 故对应发送信息位 1101 按照表 2 3 中的幸存路径画 出的网格图示于图 2 12 中 图中粗线路径是汉明距离最小 等于 2 的路径 图 2 12 对应信息位 1101 的幸存路径网格图 a 111 b 100 011 100 001 c 110 010 110 d 010 101 010 东北大学本科毕业设计 论文 第 2 章 相关理论介 绍 20 为了使输入的信息位全部通过编码器的移存器 使移存器回到初始状态 在信息位 1101 后面加了三个 0 若把这三个 0 仍看作是信息位 则可以按照 上述算法继续解码 这样得到的幸存路径网格图示于图 2 13 中 图中的粗线仍 然是汉明距离最小的路径 但是 若已知这三个码元是 为结尾而补充的 0 则在解码计算时就预先知道在接收这三个 0 码元后 路径必然应该回到状态 a 而由图可见 只有两条路径可以回到 a 状态 所以 这时图 2 13 可以简化 成图 2 14 图 2 13 对应信息位 1101000 的幸存路径网格图 图 2 14 对应信息位 1101 及以 000 结束的幸存路径网格图 b c 000 000 111 011 011 011 001 100 100 001 001 110 010 010 101 101 101 d a 000 000 111 011 011 011 001 100 100 001 001 110 010 010 101 101 a b c d 东北大学本科毕业设计 论文 第 3 章 卷积码实 现 21 第 3 章 MATLAB 应用 3 1 数和算术的表示方法 Matlab 中数的表示方法和一般的编程语言没有区别 如 3 990 0001 9 639721 6021E 206 02252e23 数学运算符有 加 减 乘 右除 左除 幂 这里 1 4 和 4 1 有相同的值都等于 0 25 注意比较 1 4 4 只有在矩阵的除 法时左除和右除才有区别 3 2 向量与矩阵运算 3 2 1 通过语句和函数产生 1 向量的产生 除了直接列出向量元素 即所谓的 穷举法 外 最常用的用来产生相同增量 的向量的方法是利用 算符 即所谓的 描述法 在 Matlab 中 它是一个很重 要的字符 如 z 1 5 z 1 2 3 4 5 即产生一个 1 5 的单位增量是 1 的行向量 此为默认情况 用 号也可以产生单位增量不等于 1 的行向量 语法是把增量放在起始量 和结尾量的中间 如 x 0 pi 4 pi 即产生一个由 0 pi 的行向量 单位增量是 pi 4 3 1416 4 0 7854 x 00 78541 57082 35623 1416 也可以产生单位增量为负数的行向量 如 东北大学本科毕业设计 论文 第 3 章 卷积码实 现 22 y 6 1 1 y 6 5 4 3 2 1 2 矩阵的产生 Matlab 提供了一批产生矩阵的函数 如表 3 1 所示 表 3 1 矩阵函数 函数名 功能 函数名 功能 zeros 产生一个零矩阵diag产生一个对角矩阵 ones生成全 1 矩阵tril取一个矩阵的下三角 eye生成单位矩阵triu取一个矩阵的上三角 magic生成魔术方阵pascal生成 PASCAL 矩阵 除了以上产生标准矩阵的函数外 Matlab 还提供了产生随机 向量 矩阵的 函数 rand 和 randn 及产生均匀级数的函数 linspace 产生对数级数的函数 logspace 和产生网格的函数 meshgrid 等等 详细使用请查阅随机文档 冒号 可以用来产生简易的表格 为了产生纵向表格形式 首先用冒号 产生行向 量 再进行转置 计算函数值的列 然后形成有二列的矩阵 3 2 2 矩阵操作 在 Matlab 中可以对矩阵进行任意操作 包括改变它的形式 取出子矩阵 扩充矩阵 旋转矩阵等 其中最重要的操作符为 它的作用是取出选定的 行与列 例如 A 代表 A 的所有元素 A J 代表 A 的第 J 列 A J K 代表 A J A J 1 A K 如同 A 的第 J 到第 K 个元素 A J K 代表 A J A J 1 A K Matlab 中有内部函数 fliplr Flip matrix in the left right direction 它对矩阵 进行左右旋转 3 3 矩阵的基本运算 3 3 1 矩阵乘法 矩阵乘法用 符号表示 当 A 矩阵列数与 B 矩阵的行数相等时 二者可 以进行乘法运算 否则是错误的 计算方法和线性代数中所介绍的完全相同 如 A 1 2 3 4 B 5 6 7 8 C A B 东北大学本科毕业设计 论文 第 3 章 卷积码实 现 23 结果为 C 43 21 87 65 84637453 82617251 5043 2219 即 Matlab 返回 C 19 22 43 50 如果 A 或 B 是标量 则 A B 返回标量 A 或 B 乘上矩阵 B 或 A 的每一个 元素所得的矩阵 3 3 2 矩阵除法 在 Matlab 中有两种矩阵除法符号 即左除和 即右除 如果 A 矩阵 是非奇异方阵 则 A B 是 A 的逆矩阵乘 B 即 inv A B 而 B A 是 B 乘 A 的 逆矩阵 即 B inv A 具体计算时可不用逆矩阵而直接计算 x A B 就是 A x B 的解 x B A 就是 x A B 的解 当 B 与 A 矩阵行数相等可进行左除 如果 A 是方阵 用高斯消元法分解因 数 解方程 A x j B j 式中的 j 表示 B 矩阵的第 j 列 返回的结果 x 具有与 B 矩阵相同的阶数 如果 A 是奇异矩阵将给出警告信息 右除 B A 可由 B A A B 左除来实现 3 4 Matlab 编程 3 4 1 关系运算 3 4 1 1 比较运算 比较两个同阶矩阵有下面六种相关操作符 如表 3 2 所示 表 3 2 比较运算符 符号功能符号功能 大于 大于等于 等于 不等于 比较两个元素的大小 结果是 1 表明为真 结果是 0 表明为假 例如 2 2 4 结果是 0 表明为假 例如一个 6 阶魔术方阵 矩阵元素计算满足各种条件 A magic 6 东北大学本科毕业设计 论文 第 3 章 卷积码实 现 24 ans 35 1 6 26 19 24 3 32 7 21 23 25 31 9 2 22 27 20 8 28 33 17 10 15 30 5 34 12 14 16 4 36 29 13 18