比特翻转交织器在Turbo码中的应用研究.doc

XXXX 大学 毕 业 设 计 论 文 题 目比特翻转交织器在 Turbo 码中的应用研究 专 业 学生姓名 班级学号 指导教师 指导单位 日期 XXXX 年 XX 月 X 日至 XXXX 年 X 月 XX 日 毕业设计 论文 原创性声明 本人郑重声明 所提交的毕业设计 论文 是本人在导师指导下 独立进 行研究工作所取得的成果 除文中已注明引用的内容外 本毕业设计 论文 不 包含任何其他个人或集体已经发表或撰写过的作品成果 对本研究做出过重要贡 献的个人和集体 均已在文中以明确方式标明并表示了谢意 论文作者签名 日期 年 月 日 摘 要 Turbo 码从出现就具有了里程碑的意义 Turbo 码是由卷积码改进而成的 其巧妙的将卷积码和随机交织码结合在一起 充分利用了 Shannon 信道编码定理 的基本条件 因此得到了接近 Shannon 理论极限的性能 Turbo 码的好坏主要由 分量码和交织器设计的好坏来决定 本文简述了 Turbo 码的相关理论 介绍了交织器在 Turbo 码中的应用 并利 用 Matlab 工具 对比特翻转交织器在 Turbo 码中的应用进行研究 并对其具体的 编码译码进行了仿真以及各种译码方案和相关编码参数对 Turbo 码的影响 从而 验证了 Turbo 的优越性 为以后 Turbo 码的比特翻转交织器的设计和应用提供了 相应的参考资料 关键词 Turbo 码 比特翻转交织器 卷积码 误码比特率 Shannon 理论 ABSTRACT Turbo code is considered as the greatest achievements made in the field of channel coding Turbo code is developed from convolutional code and it combines convolutional codes with random interleaver code which take full advantage of the basic conditions in order that the performance approach the limit of Shannon channel coding theorem This indicates that performance of Turbo code is depend on the design of component code and interleaver design This thesis briefly introduce the theories of Turbo code and summarizes the application of interleaver in the turbo code Then we stimulate Turbo encoding and deconding by Matlab tools and take research in the application of bit flip interleaver in the turbo code It is easy to understand the influence of different kind of coding scheme and coding presentation which prove the distinguishing of the Turbo code and offer the reference data about the design and application of bit flip interleaver Key words Turbo code bit flip interleaver convolutional code bit error rate Shannon s theorem 目 录 第一章 绪论 1 1 1 数字通信 1 1 1 1 数字通信原理 1 1 1 2 数字通信特点 2 1 2 信道编码理论 2 1 2 1 信道编码的纠错方式 2 1 2 2 向前纠错编码类型的演变 2 第二章Turbo码简介 4 2 1 Turbo 码的提出 4 2 2 Turbo 码的编译原理 5 2 2 1 PCCC 类的编码与译码 5 2 2 2 SCCC 类的编码及说明 6 2 2 3 HCCC 类的编码及说明 6 2 2 4 Turbo 码的删余矩阵 7 2 2 5 Turbo 码的译码算法 8 2 3 Turbo 码的研究现状以及不足 9 2 4 Turbo 码的前景 10 第三章 交织器简介 11 3 1 交织器的设计准则 11 3 2 交织器类型 13 3 2 1 块交织器 13 3 2 2 均匀交织器 14 3 2 3 随机交织器与 S 交织器 14 第四章仿真结果及分析 17 4 1 Matlab 工具 17 4 2 比特翻转交织器 18 4 3 性能仿真 18 4 3 1 迭代次数不同对于 Turbo 码的影响 18 4 3 2 码率不同对于 Turbo 码的影响 19 4 3 3 交织长度不同对于 Turbo 码的影响 20 4 3 4 交织器不同对于 Turbo 码的影响 21 第五章 总结 23 结束语 24 致 谢 25 参考文献 26 南京邮电大学 2012 届本科生毕业设计 论文 1 第一章 绪论 随着移动通信技术和大规模集成技术以及万维网的迅猛发展 各种通信业务和信息 业务以及终端设备日新月异 伴随着这些科学技术的日益发展 走在更前列的是用户对 通信质量 高速数据传输和良好的用户体验的强烈需求 而要传输的数据信号在经过电 磁波信道传输到达用户接收端的过程中会受到不可避免的噪声干扰 为了降低这些干扰 通常需要采用差错控制码来检测和纠正由信道失真引起的信息传输错误 但与此同时降 低了数据的传输速率 属于用减低速度换取更高可靠性 1 1 数字通信 数字通信就是用数字形式 即比特 0 1 传输消息或用数字方法对载波进行调制后 再进行传输的通信方式 以前常规的老式的电话和电视都是模拟通信 通过电话和电视 模拟信号经过数字调制后 再进行调制和传输 即所谓的数字电话和数字电视 但是以 计算机等数字产品为终端机的相互数据通信 因信号本身就是数字形式 因而属于数字 通信 卫星通信中常用的多路通信也是数字通信 1 1 1 数字通信原理 在模拟通信中 直接用原始信号 像音频信号 视频信号等 对载波信号进行调制 而在数字通信中 原始信号须先经过模拟到数字的转换器 转换成数字信号 即 1 和 0 形式来表现 来代替原始信号 再对载波信号进行调制 在收信端 对接收到的载波 信号经解调后 得到的仍是数字信号序列 但数字信号序列还必须经过数字 模拟转换 器才能恢复原始模拟信号 对模拟信号进行数字化有多种方法 最基本的方法是脉码调 制 还有各种类型的增量调制 后者在电路实现上更为简单 为了减少传输话音所必需 的脉码率 声码器正逐步得到推广应用 声码器也是最可靠的数字电话保密终端 声码 技术中较有发展前途的是线性预测编码 如何以更高的精度 更低的脉码率使信号数字 化 仍然是数字通信技术的主要研究课题 用数字信号代替模拟信号后 模拟通信中的 载频供给系统亦应相应改变 将被时钟所代替 为了正确判别收发两端数字码元 收发 时钟之间必须同步 这要靠码元同步和帧同步技术达到 如果数字通信设备连成通信网 还必须用网同步技术 见同步技术 数字通信还有一系列特有的技术 为使各种传输信 道适应数字信号的传输 避免各种频率成分的振幅和时延特性上的不均匀性 避免码间 干扰 需要采用均衡技术 为了便于在收信端提取同步信号 通常采用双极性码 高密 度双极性码 HDB3 码 四比三进码 4B3T 码 和部分响应码等 为了发现和自动纠正 传输中出现的误码 需要采用差错控制技术 差错控制已发展成为一种独立的技术 南京邮电大学 2012 届本科生毕业设计 论文 2 1 1 2 数字通信特点 数字通信比模拟通信有明显的优点 首先 由于采用二进制数字信号 可在强干扰的 情况下传输 从而抗干扰能力大大加强 数字信号可以再生 能消除传输过程中的引入干 扰的积累 可使通信质量不受通信距离的影响 其次 由于大量使用数字电路而易于采 用大规模集成电路实现数字多路复用 数字振铃和其他数字信号处理技术 并且更有利 于实现数字交换 使数字系统能兼容电话 电报 电视 数据和其他通信业务 最后 作为数字通信特有的优点 就是便于实现高度保密的通信 数字通信的主要缺点是占用 频带较宽 并且需要较复杂的同步系统 1 2 信道编码理论 在通信系统中 信息的传输是有方向性的 提高数据传输效率 降低误码率是信道 编码的任务 信道编码的本质是增加通信的可靠性 但信道编码会使有用的信息数据传 输减少 信道编码的过程是在源数据码流中加插一些码元 从而达到在接收端进行判错 和纠错的目的 1 2 1 信道编码的纠错方式 信道编码的纠错方式主要有三种 前向纠错 和混合差错控制 FEC 前向纠错 是增加数据通讯可信度的方法 在单向通讯信道中 一旦错误被发 现 其接收器将无权再请求传输 FEC 是利用数据进行传输冗长信息的方法 当传输中 出现错误 将允许接收器再建数据 ARQ 反馈重传 是在接收端检测到错误后给发送端发送错误信息 发送端根据错误 信息后重新发送数据到接收端 在自动重发请求方式下相同冗余码字的检错能力要远高 于其纠错能力 但自动重发请求差错控制要求有反馈信道 控制电路比较复杂 而且译 码的实时性较差 HEC 是 FEC 和 ARQ 相结合的差错控制方式 发端发送的码不仅能检测出错误 而 且还有一定的纠错能力 收端收到后 首先检测错误情况 如果错误在码的纠错能力以 内 则自动进行纠错 如果错误很多 超过了码的纠错能力 但能检测出来 则收端通 过反馈信道要求发端重新发送有错的信息 1 2 2 向前纠错编码类型的演变 首先是汉明码 其是一个错误校验码码集 由 Bell 实验室的 R W Hamming 发明 因 此定名为汉明码 随后出现了格雷码 其在数字系统中只能识别 0 和 1 各种数据要转换 南京邮电大学 2012 届本科生毕业设计 论文 3 为二进制代码才能进行处理 格雷码是一种无权码 采用绝对编码方式 之后又提出了 循环码 为无权码 每位代码无固定权值 任何相邻的两个码组中 仅有一位代码不同 为了弥补循环码的缺点 人们发明了卷积码 卷积码是 1955 年由 Elias 等人提出的 是一种非常有前途的编码方法 分组码的实现是将编码信息分组单独进行编码 因此无 论是在编码还是译码的过程中不同码组之间的码元无关 卷积码和分组码的根本区别在 于 它不是把信息序列分组后再进行单独编码 而是由连续输入的信息序列得到连续输 出的已编码序列 即进行分组编码时 其本组中的 n k 个校验元仅与本组的 k 个信息元有 关 而与其它各组信息无关 但在卷积码中 其编码器将 k 个信息码元编为 n 个码元时 这 n 个码元不仅与当前段的 k 个信息有关 而且与前面的 m 1 段信息有关 m 为编 码的约束长度 而本论文讨论的中心 Turbo 码正是在卷积码的基础上发展起来的 虽然 软判决译码 编码调制技术 和级联码都对信道编码技术产生了深远的影响 但是不论 他们如何优秀都始终在增益方面与 Shannon 理论极限始终存在 2dB 以上的差距 因此在 Turbo 码出现之前 Shannon 极限仅仅是理论上的极限 是不可能达到的 南京邮电大学 2012 届本科生毕业设计 论文 4 第二章 Turbo 码简介 由于现代信息和编码理论的奠基人 C E Shannon 在 1948 年提出了著名的带噪信道编 码定理 在其定理中 Shannon 给出了数字通信系统中实现可靠通信方法以及特定信道上 实现了可靠通信信息的信息传输速率的上限 带噪信道编码定理不仅给出了信道编码领 域的研究方向和目标 证明了有效差错控制编码的存在证明 更是在编码研究领域掀起 了一股浪潮 从而促进了这个领域的快速发展 Turbo 正是在这一股浪潮中诞生的 它的出现被认为是在信息论提出以来最大的研究 进展 其是由两位任教于法国不列颠通信大学教授 C Berrou A Glavieux 和他们的缅甸籍 博士生 P Thitimajshima 在 1993 年的国际通信会议上提出的 其巧妙地将卷积码和随机交 织器结合在一起 在实现随机编码思想的同时 通过交织器实现了由短码构造长码的方 法 并采用软输出迭代译码来逼近最大似然译码 Turbo 码充分利用了 Shannon 信道编码 定理的基本条件 因此得到了接近 Shannon 极限的性能 2 1 Turbo 码的提出 在 Turbo 码提出以前 信道截止速率 R0 一直被认为是差错控制码性能的实际极限 Shannon 极限仅仅是理论上的极限 是不可能达到的 虽然软判决译码 级 联码和编码 调制技术都对信道码的设计产生了重大影响 但其增益与 Shannon 理 论极限始终存在 2 3dB 的差距 1993 年 两位任教于法国不列颠通信大学的教授 C Berrou A Glavieux 和他 们的 缅甸籍博士生 P Thitimajshima 在 ICC 国际会议上首次提出了一种采用重复迭 代 Turbo 译码方式的并行级联码 Berrou 在他介绍 Turbo 码的首篇论文里给出 了 Turbo 码的基本组成和迭代译码原理 但没有严格的理论解释和证明 Turbo 码 很好地 应用了 Shannon 信道编码理论中的随机性编 译码条件 从而获得了几乎接近 Shannon 理论极限的译码性能 仿真结果表明 Turbo 码达到了与 Shannon 极 限仅相差 0 7dB 的优异性能 Turbo 码的出现 在编码理论界引起了轰动 成为自信息论提出以来最重大的研究进 展 掀起了 Turbo 码的研究热潮 J Hagenauer 首先系统地阐明了迭代译码的原理 并推 导了二进制分组码与卷积码的软输入软输出译码算法 T M Duman I Sason 和 D Divsalar 等人在 Gallager 限等已有性能界技术的基础上进行改进 扩展了 Turbo 码性 能界的紧致范围 D Divsalar 等人还根据递归系统卷积码的特点提出了有效自由距离的概 念 并说明在设计 Turbo 码时应该使码字有效自有距离尽可 能大 J Seghers 系统地分 析了 Turbo 码的距离特性 考虑到 Turbo 码的延时问题 E K Hall 等人提出了面向流 的 Turbo 码 南京邮电大学 2012 届本科生毕业设计 论文 5 2 2 Turbo 码的编译原理 Turbo 码最大特点在于它通过了在编译码器中交织器和解交织器的使用 使得短码 的有效结合实现长码 达到了 Shannon 定理的 3 个基本假设条件 从而达到了接近 Shannon 理论极限的性能 Turbo 码常见的编码类型有三种 包括 PCCC SCCC 和 HCCC 2 2 1 PCCC 类的编码与译码 PCCC 类的编码如图 2 1 所示 复 接 输出码元 输入码元 删 余 矩 阵 分量编码器1 分量编码器2交织器 图 2 1 PCCC 类 Turbo 码编码器框图 PCCC 类的译码如图 2 2 所示 解交织器 码元输出 似 然 值 k2 译码器 2 交织器 交织器 解交织 器 译码器1 校验序 列y1 信息序 列x1 校验序列y2 似然值k1 图 2 2 PCCC 类 Turbo 译码器框图 Turbo 编码器主要由分量编码器 交织器以及删除矩阵和复接矩阵者组成 1 分量码一般选择为递归系统卷积 RSC 码 2 通过交织器出来的输送给分量编码器 2 的数据和分量编码器 1 里面的数据的唯一不 南京邮电大学 2012 届本科生毕业设计 论文 6 同是其顺序 其他完全相同 3 因为码字的最小距离是估计码字性能的首要参数 因此交织器设计的好坏在很大程 度上影响着 Turbo 码的性能 4 删余矩阵的作用是提高编码效率 2 2 2 SCCC 类的编码及说明 SCCC 的编码如图 2 3 所示 交织器内编码器外编码器 输入码元 输出码元 图 2 3 SCCC 类 Turbo 编码器框图 SCCC 编码的出现是为了解决在 AWGN 信道上 当误比特率随信噪比的增加下降到 一定程度以后 出现下降缓慢甚至不再降低的情况 其综合了 Formey 串行级联码 RS 码 卷积码 和 Turbo 码 PCCC 的特点 2 2 3 HCCC 类的编码及说明 HCCC 的编码如图 2 4 所示 交织器1 并行编 码器 交织器2 内编码 器 外编码 器 输入码元 输出码元 输出码元 图 2 4 HCCC 类 Turbo 编码器框图 HCCC 为混合级联卷积码 其是将 PCCC 和 HCCC 的编码方案综合起来 同时具备 了这两者的优点 这种码的编码方案有编码很多 图 4 为其中一种 2 2 4 Turbo 码的删余矩阵 Turbo 码的删余就是通过删除冗余的校验位来调节码率 Turbo 码采用两个成员编器 产生的冗余比特比一般情况多一倍 这在很多场合下并不需要 但又不能排斥任何一个 编码器 折衷的办法就是按一定规律轮流选用两个编码器的校验比特 例如 采用两个 南京邮电大学 2012 届本科生毕业设计 论文 7 1 2 成员编码器时 如果不删余 信息位加两个编码器的校验位将产生 1 3 的码流 但如 果令编码器 1 的校验流乘以一个删余矩阵 令编码器 2 的校验流乘以删余矩阵 P 及可 其中 1 代表传输此比特 0 表示不传输 这样就产生了在编码器 1 和 2 之间轮流取值的效 果 一般情况下 设两个编码器的校验位生成矩阵为 q 和 q m 和 m 为交织前后的 N 位信息位流 则 m 和 q 分别为 lxN 的校验位矢量 删余矩阵 P 为 Nx2 矩阵 其中 12 pp 和均为 Nxl 的列矢量 由 0 或 1 值组成 分别表示对两个编码器校验位的选择情况 1 p 2 p 1 表示该编码比特作为输出比特传输到对端 0 表示该编码比特不进行传输 借助删余可以用较简单的编译码器 如1 2卷积码 实现较高码率 如6 7码率 的编 译码 比如 在1 2卷积码的网格上 从每一状态出发或到达每一状态仅有两条路径 而 直接使用6 7卷积码从一个状态出发或到达一个状态存在2 二64条路径 通常 R kln的 卷积码译码时每一状态需要进行2k次路径比较 如果用1 2编码器产生6 12码 再通过删 余产生6 7码 译码时仍使用1 2的译码器 比直接使用6 7的译码器要容易实现 使用两个 RSC 分量码进行编码的 Turbo 码的码率为 1 3 信道的带宽通常是有限 的 提高有限带宽的利用率成为需要解决的重要问题 为了提高Turbo 码的码率 可以对 Turbo 码采用删余技术 Turbo 码的删余技术是指从两个RSC分量编码器生成的校验序列 中按照一定规则周期地删除一些校验位比特 然后将得到的校验序列与输入的信息序列 通过并串转换组成编码输出序列 经过Turbo 编码后得到的编码输出序列的长度为3N 其中包括由两个RSC 分量码编 码器输出的长度为2N 的校验比特序列 编码后的码率为1 3 通过删余可以将码率提高到1 2 删余矩阵p 为 式2 1 10 01 p 删余矩阵 p 意义为 横坐标表示由第几个分量编码器输出 纵坐标表示校验序列的 奇偶位 1 表示该位不删余 0 表示该位删余 该矩阵表示删余校验序列 Y1 y1k 的偶数位和校验 Y2 y2k 的奇数位 将得到的校验序列与信息序列 U k u 复接后 得到的输出序列为 式 2 2 0201111 kkk Xxuyuyuy 码率变为1 2 图2 5 是矩阵p的删余示意图 阴影的部分是经过打孔去掉的删余比 特 南京邮电大学 2012 届本科生毕业设计 论文 8 图 2 5 删余示意图 2 2 5 Turbo 码的译码算法 香农信息论告诉我们 最优的译码算法是概率译码算法 也就是最大后验概率算法 MAP 但在 Turbo 码出现之前 信道编码使用的概率译码算法是最大似然算法 ML ML 算法是 MAP 算法的简化 即假设信源符号等概率出现 因此是次优的译码算法 Turbo 码的译码算法采用了 MAP 算法 在译码的结构上又做了改进 再次引入反馈的概 念 取得了性能和复杂度之间的折衷 同时 Turbo 码的译码采用的是迭代译码 这与经 典的代数译码是完全不同的 Turbo 码的译码算法是在 BCJR 算法的基础上改进的 我们称为 MAP 算法 后来又 形成 Log MAP 算法 Max Log MAP 以及软输出维特比译码 SOVA 算法 译码时首先对接收信息进行处理 两个成员译码器之间外部信息的传递就形成了一 个循环迭代的结构 由于外部信息的作用 一定信噪比下的误比特率将随着循环次数的 增加而降低 同时外部信息与接收序列间的相关性也随着译码次数的增加而逐渐增加 外部信息所提供的纠错能力也随之减弱 在一定的循环次数之后 译码性能将不再提高 译码算法应该考虑到三方面的问题 外信息的引入 如何在迭代译码中充分利用各 类信息 防止简单正反馈的形成 确保算法收敛 充分利用码源的相关信息 2 3 Turbo 码的研究现状以及不足 1 编译码技术 编码编码方面主要包括对并行级联编码与串行级联编码的分析 以 及对混合级联方式的研究 译码方面主要包括迭代译码 译码算法 最大后验概率算法 MAP 修正的 MAP 算法 Max Log MAP 软输出 Viterbi 算法 SOVA 等 的研究 2 Turbo 码的设计和分析 主要包括交织器的设计 码的级联方式 译码算法 Turbo 码的性能分析等 在性能分析中 主要对码重分布及距离谱进行分析 但由于没有 相应的理论支持 这种分析只能是近似的 且仅局限于短码长 小码重的情况 3 Turbo 码在直扩 CDMA 系统中的研究及应用 Turbo 码不仅在信道信噪比很低 南京邮电大学 2012 届本科生毕业设计 论文 9 的高噪声环境下性能优越 而且还具有很强的抗衰落 抗干扰能力 因此它在信道条件 差的移动通信系统中有很大的应用潜力 在第三代移动通信系统 IMT 2000 中己经将 Turbo 码作为其传输高速数据的信道编码标准 在硬件实现方面 Turbo 码的实验芯片已经开发出来 法国 澳大利亚 美国的三家 公司己宣称开发出了相应的产品 但是从目前的研究情况来看 Turbo 码的技术还不成熟 主要存在以下几个问题 1 Turbo 码的编码机理 Turbo 码的产生是实践的结果 没有确定的设计准则 这对 Turbo 码的设计和优化产生了一定的困难 因此 有必要对 Turbo 码的机理进行研究 以 便为好码的构造提供指导 而要完成对 Turbo 码的编码机理的研究 有待于 Turbo 码的 正确建模 2 Turbo 码交织方法的选择 Turbo 码中的交织器对其性能有很大的影响 选择恰当 的交织器将使 Turbo 码的优异性能得到充分的发挥 什么是最佳的交织方法一直没有定论 这是 Turbo 码所要解决的一个重要问题 3 Turbo 码的译码算法 目前 Turbo 码的译码算法主要为 MAP 算法和 SOVA 算法 MAP 算法性能很好 但是复杂度太高 在实际通信系统中受到限制 SOVA 算法简单 但性能比 MAP 算法差 且译码性能不是很稳定 这两种算法都没有采用快速算法 能否 设计简单可行 性能较佳的译码算法也将决定 Turbo 码的应用前景 4 Turbo 码的延时 Turbo 码采用了级联译码和迭代译码 从而具有优越的译码性能 但这也造成了一个较大的缺点 那就是延时太大 妨碍它的实际应用 如何正确估量 Turbo 码中延时的影响 从而确定最佳的编码方法还有待于进一步的研究 2 4 Turbo 码的前景 目前 Turbo 码的研究尚缺少理论基础支持 但是在各种恶劣条件下 即低 SNR 情况 下 提供接近 Shannon 极限的通信能力已经通过模拟证明 但 Turbo 码也存在着一些急 待解决的问题 例如译码算法的改进 复杂性的降低 译码延时的减小 作为商用 3G 移 动通信系统的关键技术之一 Turbo 码也将逐渐获得较好的理论支持并且得到进一步开发 和完善 南京邮电大学 2012 届本科生毕业设计 论文 10 m d m d 第三章 交织器简介 交织器的作用是改变信息结构将传输过程中出现的突发错误进行的分散化和不规则 化 码字的重量分布决定了 Turbo 码的纠错译码性能 交织器可以改变 Turbo 码的重量 分布 因此 交织器对 Turbo 码性能的好坏有着重要作用 在 Turbo 码中 交织器使输 入码元符号的顺序尽可能随机分布 使码元符号之间的相关性减弱 从而使进入各个子 译码器的信息序列之间不相关 这使得各个子译码器彼此独立的工作 互相利用软判决 信息 判决结果也因此逐渐准确 但是 同样由于 Turbo 码是以帧的形式编码 交织器 的存在使得 Turbo 码存在时延 帧越长 时延越大 所以 只有允许较大时延的系统 才可以充分发挥 Turbo 码的作用 3 1 交织器的设计准则 较多的通信系统中都用到了交织器 其位置一般在信道编码器之后和调制之前 作 为一相对独立的模块 其作用主要是改变码重分布及为了分离传输中相关信道的衰落所 引起的连续突发错误 一般的信道纠错编码对于纠独立的随机错误是有效的 而对于突发的连续错误显得 没有效果 所以用了交织器之后 就可以把突发错误分离为近似的随机错误 有利于纠 错码的有效纠错 从分集的角度来说 交织器是一种隐性的时间分集方式 在 Turbo 码的最先提出中 Berrou 等人也使用了交织器 此时交织器是作为一个不 可分割的部分 同 RSC 成员编码器共同组成一有机整体一 Turbo 码的编码器 大量的研 究表明 交织器的结构和长度在 Turbo 码的纠错性能中扮演着重要的角色 事实证明 交织器在 Turbo 码中起着十分重要的关键作用 很大程度上影响着 Turbo 码的性能 所以 交织器的设计是 Turbo 码设计中的一个重要方面 交织器的设计应遵循以下几个重要准则 1 最大程度地置乱原数据排列顺序 避免置换前相距较近的数据在置换后仍相距较近 特别是避免置换前相邻数据在置换后再次相邻 2 尽可能避免与同一信息位直接相关的两个分量编码器中的校验位均被删余 3 对于不归零的编码器 交织器设计时要避免出现 尾效应 图案 4 在满足上述要求的交织器中再选择一个好的交织器 使码字之间的最小距离 或自 由距离 尽可能大 而重量为的码字数要尽可能少 以改善 Turbo 码在高信 噪比时的性能 以上原则也可概括为两个大的原则 1 汉明重原则 在 AWGN 信道下采用最大似然算法的线性纠错码的性能 和此种纠 错码的最小汉明距离或自由距离价有关 Turbo 码作为一种线性码 在 AWGN 信道下 误码比特率近似等于 南京邮电大学 2012 届本科生毕业设计 论文 11 式 3 1 由于 Turbo 码可被看作是一种线性分组码 就是其最小汉明重量 上式中是 min N 码重等于最小汉明重量的码字的数量 是交织器的长度 是产生最小汉明重量码字 的输入序列的平均汉明重量 是编码速率 是未编码前信息比特的平均能量 高 斯白噪声的单边带功率谱密度 由式 3 1 可知 对于 Turbo 码 当交织器长度固定时 要想获得更好的纠错性能 N 可以通过增加 或者减小 两种途径 当 Turbo 码中的 RSC 成员编码器固定时 交织 器的结构将极大地影响上述两个参数 式 3 1 只是一种近似描述 实际上 一种线性码的纠错性能不只和最小汉明重量的码 字有关系 和汉明重接近最小汉明重量的码字也有很大关系 也就是说 所有码字中 较低汉明重量的码字极大地影响了这个码的纠错性能 因此在设计具有更好纠错性能的 Turbo 码时 可以通过交织器结构的改变来改变这些低汉明重码字的数量和重量 下面可 以看到 Turbo 码中交织器在这些方面所起到的作用 当输入序列进入第一 RSC 编码器产生较低汉明重的校验码字时 可通过交织器来打 乱输入序列后 再送入第二 RSC 编码器 使其产生较高汉明重量的校验码字 这样对于 整个编码输出码字 就有比较高的汉明重量 从此种观点来看 交织器的设计就是尽量避免在两个 RSC 编码器同时产生低汉明重 的校验码字 尽量地提高码字的 尽量地减少低汉明重量码字的数量 这就是汉 明重原则 2 随机性原则 Shannon 在证明 Shannon 定理时 采用的就是随机编码方式 他从所 有种码字中随机挑选出了 个码字 他指出 当趋于无穷时 若信息传输速率 低 n q n 于信道容量 就可达到任意低的误码率 显然 趋于无穷 在运用中是不现实的 因 n 此目前的所有信道编码方法都是按照确定性的方法获得 但 Shannon 在证明中给了我们 一种启示还是不容忽略的 这就是具有随机性的编码方式会获得较好的结果 如前所述 Turbo 码在最先提出来时 在编码器中引入了随机的交织器 使得码具有 了一些随机的性质 G Battail 曾经从信息论的角度来理解 Turbo 码这种编码方式 并把 Turbo 码归类为一种弱随机性编码方式 Weakly random like codes Turbo 码的译码不是采用最优的最大似然译码算法 而是采用了次优的迭代译码算 法 采用最大似然译码算法时 影响码性能的关键是码的最小汉明距离或自由距离 而 在次优的迭代译码算法中 每次迭代输入的先验信息和从信道获得的比特信息的相关性 将极 大地影响译码的性能 因为先验信息是由另一成员译码器输出的外在信息经 交织或反交织获得的 由于成员译码器采用的是 MAP 或者 LOG MAP 等算法 每一个信 息比特的外在信息都会和其前 和后 个信息比特有关 若采用 SOVA 算法时 只和前 个信息比特有关 一般高达 5 6 倍的成员编码器的约束长度 若外在信息经交织或反交 0 NR b E min w N m d minmin 0 2 b bm R ENw PQd NN m d min N m d min N m N m N m N C k q R 南京邮电大学 2012 届本科生毕业设计 论文 12 织后 又当作为 个信息比特中的某一个比特的先验信息来进行译码 可想而知 译 码会因为它们的相关性而性能下降 从此种角度来讲 使外在信息和信道比特信息二者 越不相关越好 因此交织器应尽量的使二者不相关 我们称之为随机性原则 从随机性 原则来看 最好的交织器 是最随机的交织器 3 2 交织器类型 3 2 1 块交织器 块交织器 Block Interleaver 是一种常见的交织器 它沿用了通信系统交织过程中常见 的交织器结构 一般来说 交织器的长度是 交织过程如下 nm 把个输入数据放入一个行列的矩阵中 按列的顺序从上到下 从左到右地nm mn 填入 等全部个数据填满后 再开始按行的顺序从左到右 从上到下地读出 nm 块交织器是一种基于汉明重原则设计的交织器 它能比较有效的打乱码重为 2 的输 入序列 使其能产生较高码重的输出码字 但是块交织器有一个很大的缺点 就是它不 能打乱一些特殊的序列 如图 3 1 所示的序列块是无法被一个块交织器打乱的 而且即使 增加了块交织器的长度 这样的序列也是无法被打乱 类似不能被块交织器所打乱的序 列还有很多 这样就会使 Turbo 码产生许多低重量码字 从而影响了 Turbo 码的性能 1001 0000 0000 1001 图 3 1 无法被一个块交织器打乱的序列块 而且 交织器长度越长 不能被块交织器所打乱的序列就越多 所以在长数据帧的 情况下 不能采用块交织器来构造 Turbo 码 而在短数据帧的情况下 这一缺点表现得不 是很明显 所以块交织器一般只用于短数据帧的 Turbo 码 3 2 2 均匀交织器 均匀 Uniform 交织器是 Benedetto 等人提出的 在 Turbo 码刚提出的一段时间内 关 2 m N 南京邮电大学 2012 届本科生毕业设计 论文 13 于 Turbo 码的性能一般都是通过仿真方法来考察的 很少有人从理论上进行分析 这是因 为在理论上推导纠错码的性能上界时 需要计算码字的重量枚举函数 Weight Enumerating Function 而对于 Turbo 码 交织器的存在使得这种计算变得难以实现 Benedetto 等人 为克服这个难题 提出了均匀交织器 结果表明这种交织器对于从理论上分析 Turbo 码的 纠错性能是非常有效的 均匀交织器是这样定义的 设交织器长度为 输入待编码码字的汉明重量为 Nk 对于这个码字将存在种交织器 交织后分别得到不同的结果 而均匀交织器就是这些 k N C 交织器的综合体 也就是说 上述汉明重量的输入码字 经均匀交织器交织后 会有k 种结果 而每种结果的概率是 满足 k N C k N C1Nk 2 1 0 从定义中可看到 均匀交织并不是一种具有实质意义的交织器 是不可实现的交织 器 但这种交织器的提出仍具有非常重大的意义 一是其在 Turbo 码性能的理论推导中起 到了关键作用 二是由于均匀交织器是所有可能交织器的数学期望 因此对于一种 Turbo 码 用均匀交织器获得的性能肯定不会是最好的 但也不是最坏的 这个特点 为交织 器的设计提供了一个很好的参照物 3 2 3 随机交织器与 S 交织器 1 随机交织器 随机交织器被期望能够实现随机交织过程 但实际上采用的随机交织器都是伪随机 交织器 它反映的是一种映射关系 其映射原理如图 3 2 所示 其工作过程是 对于长为的信息序列 首先标记每个比特的位置 然后生成相应个随机数 按NN 产生的顺序排列成序列 每个随机数对应于信息序列中相应位置的信息比特 然后把X 中元素按一定的规则重新排列得到序列 并按中元素的顺序读出相应的信XYY 南京邮电大学 2012 届本科生毕业设计 论文 14 图 3 2 随机交织器交织过程 息比特 这样就完成了交织 Berrou 等人在最先提出的 Turbo 码中就是用的随机交织器 应该说 随机交织器能产生性能较好的交织器 尤其是在产生长度比较长的交织器时 性能一般都比较好 但因为是采用随机的方法 有时也会产生性能较差的交织器 正因为 没有什么特殊准则要遵守 使得随机交织器很容易产生 但是其性能是得不到保障的 在设计时 若需采用随机交织器 一般会产生很多个随机交织器 通过仿真从中选取性 能最好的那一个 2 S 交织器 S 交织器又叫半随机交织器 Semi random Interleaver 是一类特殊的随机交织器 它 把两种原则比较好的结合了起来 长为的 S 交织器的设计步骤如下 N 1 选取一个正整数 即扩展参数 应尽量大 最好是 若 ss2Ns 2Ns 以下步骤很难彻底完成 2 产生一个随机数 使得 iNi 1 3 把 与前面所产生的 个整数相比较 如果当前的选择与前面 个整数中的任何一iss 个相距都不在士 的范围之内 则保留之 否则 需要重新产生随机数 直到上述条件i 满足为止 4 重复步骤 2 3 直到交织器的全部个位置均被填满 N S 交织器是部分基于汉明重原则设计的交织器 一段时间以来 重量为 2 的输入序列 被认为是引起 Turbo 码低汉明重量码字输出的主要因素 设计 S 交织器的出发点就是要 打乱这些重量为 2 的输入序列 减少这些输入序列同时在两个 RSC 成员编码器上产生低 重量输出的机会 经过 S 交织器后 使得重量为 2 的输入序列交织前的距离和交织后 1 d 的距离 满足 确保了最小的值 而且随着的最大 这个最小 2 d1 21 sdd 21 dd N 南京邮电大学 2012 届本科生毕业设计 论文 15 值也会随之增大 可以看到重量为 2 的输入序列被比较有效的分开了 S 交织器的设计利用了上述地搜索算法来实现 该算法的一个缺点是不能确保对于每 一个的值 都可以找到一个 S 交织器 而且算法的搜索时间随着 的增加而增加 2Ns 当 N 比较大时 这一搜索算法会耗费大量时间 当 s 1 时 S 交织器就是随机交织器 南京邮电大学 2012 届本科生毕业设计 论文 16 第四章 仿真结果及分析 4 1Matlab 工具 1970 年代末到 80 年代初 时任美国新墨西哥大学 University of New Mexico 教 授的克里夫 莫勒尔 Cleve Moler 为了让学生更方便地使用 LINPACK 及 EISPACK 需要通过 FORTRAN 编程来实现 但当时学生们并无相关知识 独立编写了第 一个版本的 MATLAB 这个版本的 MATLAB 只能进行简单的矩阵运算 例如矩阵转置 计算 行列式和本征值 此版本软件分发出大约两三百份 1984 年 杰克 李特 Jack Little 克里夫 莫勒尔和斯蒂夫 班格尔特 Steve Bangert 合作成立了 MathWorks 公司 正式把 MATLAB 推向市场 MATLAB 最初是由 莫勒尔用 FORTRAN 编写的 李特和班格尔特花了约一年半的时间用 C 重新编写了 MATLAB 并增加了一些新功能 同时 李特还开发了第一个系统控制工具箱 其中一些 代码到现在仍然在使用 C 语言版的面向 MS DOS 系统的 MATLAB 1 0 在拉斯维加斯举 行的 IEEE 决策与控制会议 IEEE Conference on Decision and Control 正式推出 它的 第一份订单只售出了 10 份拷贝 而到了现在 根据 MathWorks 自己的数据 目前世界 上 100 多个国家的超过一百万工程师和科学家在使用 MATLAB 和 Simulink MATLAB 将数值分析 矩阵计算 科学数据可视化以及非线性动态系统的建模和仿 真等诸多强大功能集成在一个易于使用的视窗环境中 为科学研究 工程设计以及必须 进行有效数值计算的众多科学领域提供了一种全面的解决方案 并在很大程度上摆脱了 传统非交互式程序设计语言 如 C Fortran 的编辑模式 代表了当今国际科学计算软件 的先进水平 它在数学类科技应用软件中在数值计算方面首屈一指 MATLAB 可以进行 矩阵运算 绘制函数和数据 实现算法 创建用户界面 连接其他编程语言的程序等 主要应用于工程计算 控制设计 信号处理与通讯 图像处理 信号检测 金融建模设 计与分析等领域 MATLAB 的主要提供以下功能 可用于技术计算的高级语言 可对代码 文件和数据进行管理的开发环境 可以按迭代的方式探查 设计及求解问题的交互式工具 可用于线性代数 统计 傅立叶分析 筛选 优化以及数值积分等的数学函数 可用于可视化数据的二维和三维图形函数 可用于构建自定义的图形用户界面的各种工具 可将基于 MATLAB 的算法与外部应用程序和语言 如 C C Fortran Java COM 以 及 Microsoft Excel 集成的各种函数工具箱 南京邮电大学 2012 届本科生毕业设计 论文 17 4 2 比特翻转交织器 比特翻转交织器就是将输入数据依据 Turbo 码交织参数表进行比特翻转将原有的数 据顺序打乱并生成新的数据顺序输出 比特翻转交织器的工作原理 设 Turbo 码的输入帧长为 N 即交织长度为 N 比特 翻转交织器按如下步骤实现 确定长度满足 的最小整数 n 构造长度为 n 5 位的计数器并初始化 取计数器的高 n 位加 1 后保留低 n 位 用计数器的低 5 位作为索引查表 得到一个 n 位的数值 将 和 的结果相乘 保留结果的低 n 位 取计数器的低 5 位并比特顺序翻转 以 得到的结果为高 5 位 以 得到的结果为低 n 位 构成 n 5 位的地址 若 得到的地址大于交织长度 N 则放弃该地址 否则作为有效地址输出 计数器加 1 重复执行 直到生成所有 N 个交织器输出地址 4 3 性能仿真 本小节将通过计算机仿真 研究有关设计参数 如交织长度 码率 迭代次数大小 等 对 Turbo 码性能的影响 从而更好地把握设计参数的选择 仿真环境 MATALAB7 0 采用的生成矩阵为 23323 111 G DDDDDDDD 4 3 1 迭代次数不同对于 Turbo 码的影响 图 4 1 给出了不同迭代次数下 Turbo 码的误比特率与信噪比的关系曲线 采用 Log MAP 算法 以及比特翻转交织器 测试环境为 AWGN 码率为 1 3 帧长为 350 迭代 次数为 10 测试范围为 0 3dB 测试步长为 0 3dB 从图 4 1 所示的仿真结果可以看出 随着迭代次数的增加 Turbo 码的误比特率曲线 不断降低并趋于收敛 而且随着信噪比的增加 迭代对误比特率性能的影响越来越明显 这是 Turbo 码通过迭代译码充分利用冗余信息来提高编译码性能这一特点的反映 最初 迭代译码的增益较高 但随着迭代次数的增加 译码增益增长相对缓慢 虽然继续增加 迭代次数可以提高 Turbo 码的性能 但权衡迭代所需要的时间 性能改善的幅度 我们通 常都选取合适的迭代次数 5 2nN 南京邮电大学 2012 届本科生毕业设计 论文 18 00 511 522 53 10 5 10 4 10 3 10 2 10 1 10 0 交 交 交 交 1 交 交 交 交 2 交 交 交 交 3 交 交 交 交 4 交 交 交 交 10 图 4 1 不同迭代次数对Turbo码误码率的影响 4 3 2 码率不同对于 Turbo 码的影响 图 4 2 给出了 Turbo 码在不同的编码率下的仿真结果 码率分别为 1 2 1 3 采用 随比特翻转交织 交织长度为 378 比特 译码算法采用 Log MAP 最大迭代次数为 10 测试范围为 0 3dB 测试步长为 0 3dB 帧长为 350 帧 从图 4 2 的仿真结果可知 不同的码率明显影响了 Turbo 码的性能 图中 1 3 码率的 Turbo 码的误码率始终低于 1 2 码率的 Turbo 码 Turbo 码中存在一定的冗余 这些冗余 信息对迭代译码起重要作用 删余使冗余信息减小降低了校验信息的可靠性 因此 1 2 码率的