Galois域的信道编码.doc

淮 海 工 学 院 毕业设计 论文 说明书 题 目 Galois 域的信道编码 作 者 学 号 学 院 专业班级 指导者 评阅者 淮海工学院二 八届毕业设计 论文 第 1 页 共 38 页 毕业设计 论文 中文摘要 Galois 域的信道编码 摘 要 域和 Galois 理论的产生确是为了应用于解决用根式解方程问题 但它并不局限 于此 它不仅对方程的可解性问题提供了全面透彻的解答 还解决了困扰数学家们长达数 百年之久的问题 给出了能否用直尺和圆规作图的一般判别法 圆满解决了三等分任意角 倍立方等问题 Galois 理论的创立 对现代数学的形成和发展起了巨大的推动作用 它使 抽象代数学迅速发展成一门崭新的数学分支 并对近现代数学的形成和发展产生了举足轻 重的影响 同时 这种理论对物理学 化学等自然科学 甚至对于 20 世纪结构主义哲学的 产生和发展都产生了影响 近年来 随着计算机数字技术的快速发展 提出了一系列需要解决的 3 与信息安全息 息相关的编译码等问题 其中的许多问题都涉及域和 Galois 理论 目前 域和 Galois 理 论已经成为数字信息技术研究 发展中不可或缺的工具 关键词 毕业设计 论文 外文摘要 淮海工学院二 八届毕业设计 论文 第 2 页 共 38 页 The Proposal s Research And Design For Modern Integrated Laboratory Network Abstract This proposal constructs a private integrated laboratory network for teaching researching and experiment It provides students a chance to study theoretical knowledge and to know to understand to master the feature function and the way to use it The proposal also carries on the essential network design organization and the experiment s application It is very practical for raising student s ability of independent scientific the network to set up with the network application experiment this regarding raising student s independent networks equipment structure and training the high quality person Base the demand of the computer network technology teaching the computer network s actuality and development the design of the computer network laboratory was made of eight function module IPv6 module wide area network routing communication module wireless services module user authentication module voice over IP module wide area network of digital date network communication module two core redundancy module the existent computer network laboratory module Among the design base on the function demand of the eight modules designed the computer network laboratory in a single network and designed every module in detailed The eight modules not only can offer computer network technology experiment but also satisfied scientific research s demand Keywords network laboratory wide area route communication WAN DDN communications Two core redundancy IPv6 VOIP user authentication wireless service 目 录 淮海工学院二 八届毕业设计 论文 第 3 页 共 38 页 目 录 第一章 绪论 1 1 数字通信系统的结构 1 2 信道编码技术的发展史 1 3 QPSK 调制的研究现状 1 4 RS 调制的研究现状 1 5 BPSK 二进制移相键控 调制的研究现状 第二章 信道编码基础 2 1 线性分组码的概念 2 2 生成矩阵和校验矩阵 2 3 线性分组码的最小距离 2 4 系统码 2 5 循环码和准循环码 第三章 LDPC 码概述 3 1 图的定义 3 2 双向图 3 3 图的矩阵表示 3 4 LDPC 码的描述赫图模型表达 第四章 LDPC 码译码 4 1 软判决译码基本原理 4 2 LDPC 码的位翻转译码 4 3 硬判决位翻转译码 4 4 软判决翻转译码 4 5 两种翻转译码算法的性能比较 结 论 24 致 谢 25 参 考 文 献 26 附录 1 27 附录 2 30 附录 3 30 淮海工学院二 八届毕业设计 论文 第 4 页 共 38 页 1 信道编码基础 数字通信基础 框图 出现的问题 出现误码 必须采用信道编码技术 信道编码 发展上 2 有限与介绍 3 RS 码 原理 编码方法 姨妈方法 与 4方针实现 1 方针框图 2 BPSK 3 AWGN 4 4 方针结果 5 结论 附录 淮海工学院二 八届毕业设计 论文 第 5 页 共 38 页 1 引言 本章介绍信道编码在数字通信系统中所处的地位 信道编码技术的发展历史及 LDPC 码目前的研究现状 1 1 数字通信系统的结构 通信的目的是把对方不知道的消息及时可靠地传送给对方 随着对高效 高可靠性数字通信系统需求的迅猛增长 大规模高速宽带网络的发展使语音 图像和其他多媒体信息的传输成为可能 通信系统设计人员最关心的是如何在 数据源功率和带宽有限 系统复杂性和设备造价尽可能小的条件下实现尽可能 准确的信息传输 即使信息传输的误码率最小化 信道编码是消除或降低信息 错误概率的有效手段之一 为更好的理解信道编码在数字通信系统中的地位和 作用 下面首先介绍通用数字通信系统的基本组成结构 所有数字通信系统如通信 雷达 遥控遥测 数字计算机存储系统的内部 运算以及数字计算机之间的数据传输等 都可归纳成如图 1 1 所示的模型 图中 信源是产生需要传输的信息 信息可以是模拟信号 也可以是数字 信号 如果信源是模拟信号 则在送入数字系统传输之前需要进行采样和数字 化处理 如果是数字信号则可以是字 码字等符号 一般将这些称为码元 信源 的输出根据给定的码表转化成符号序列 一般情况下常用的是二元符号序列 码字符号中的码元取自集合 0 1 这时码元又称为比特 如果信源编码器的 输出信号为 称为数据传输速率 简称为数据率 r bbit s rb 信源编码器的任务是将信源发出的消息如语言 图像 文字等转换成为能 够抵抗信道噪声和失真以及有利于在传输媒质上进行的传输形式 信源输出经 过信源编码器编码后得到的数字序列称为信息序列 信道编码是在发送器和接收器之间实现信号可靠传输的必要手段之一 传 输信道存在一定的噪声和衰落 必然会对其上传输的信息引入失真和信号判决 错误 因此需要采用差错控制码来检测和纠正这些比特错误 信道编码器的作 用是在信息序列中嵌入冗余码元 提高其纠错能力 信道编码的冗余码元的作 用是减小传输中发生的信号和码元错误 提高系统的可靠性 下面主要考虑二元有限域上的信道编码 因此不再区分码元和比特的概念 信道编码的基本思想是将每 k 个连续的信息比特分为一组 经过适当的编码后 得到 n 个比特的输出 这 n 个比特组成的序列称为一个码字 好的差错控制码 所生成的码字应该是在码字集合中 所有码字之间的区别尽可能大 从而使通 信系统中的无法纠正或检测的信道错误尽可能少 k 个信息比特与 n 个码字比 淮海工学院二 八届毕业设计 论文 第 6 页 共 38 页 特的比值称为编码速率 简称码率 R 即 k R n 从而经过信道编码后的数据率为 bb c rr n rbit s Rk 差错控制码的基本目标是在有限的信号功率 系统带宽和硬件复杂性要求 下使通信的可靠性最大 这个目标是通过在信息序列中引入冗余比特来实现的 与未编码系统相比 信道编码会导致数据传输率的降低或者对信道带宽的要求 增加 数字调制器的作用是使信息变成能够适应信道传输的信号 如比特形式的 信息是不适合在物理信道上传输的 因此需要利用数字调制器将这些编码比特 转化成适合于在信道上传输的连续波形信号 通过相应方式调制可以在相同的 物理信道上同时传输多个信息比特 数目与具体的调制方式有关 如 8PSK 调制下 可同时传输 3 比特信息 16QAM 调制下可同时传输 4 比特信息 从而提高信息 传输速率 调制器的基本思想是将编码的数字序列映射成适合在信道上传输的 模拟连续信号 具体地说 M 维调制器可以将 l 个二元数字符号映射成一个有 M 种不同波形的模拟连续信号 2lM 如果调制器输出的每个信号的持续时间为 T 则称 T 为信号间隔 而称 1 T 为符号速率 如果定义信号带宽的最小值为 r Hz 则可以表示为 rr bb s n rHz Rlkl 信号经过调制器后送入物理信道进行传输 典型的传输信道包括有线信道 光纤信道 无线信道 卫星信道 磁记录信道以及水下声音信道等 无论是哪 一种传输媒体 都会引入一定的传输噪声 使传输信号发生一定的失真 而且 由于信道带宽资源有限 通常需要为不同的通信业务分配不同的传输频率和带 宽 因此 在实际的信道中存在的两个主要问题就是信道固有的嗓声和有限的 带宽限制 此外 移动信道会受到多径传播的影响 卫星信道会受到信号功率 衰减的影响等 这些在系统设计过程中都应该考虑 信号到达接收端 在接收机中 数字解调器的作用是通过对接收到的调制 信号序列或传输码字进行最优估计 然后输出数字编码序列到信道译码器 信 道译码器对传输消息进行估计和判决 估计准则是根据编码准则和信道特性而 确定的 目的是使信道噪声所造成的信号判决错误最小化 最后 信源译码器根据信源编码准则将得到的信道译码器输出的编码信息 序列经过相应的信源译码后 得到对原始信源序列的估计并传递给用户 因此 我们首先关心的是图中的信道编 译码器两个方框 为了便于研究 淮海工学院二 八届毕业设计 论文 第 7 页 共 38 页 将模型简化成如图 1 1 所示的模型 在此模型中 信源是指原来的信源和信源 编码器 其输出是二 多 进制信息序列 信道是包括发射机 实际信道和接收 机在内的广义信道 又称编码信道 它输入二 多 进制数字序列 输出一般也 是二 多 进制数字序列 图 1 1 数字通信系统简化系统 1 2 信道编码技术的发展史 伴随着通信技术的飞速发展以及各种传输方式对可靠性要求的不断提高 差错控制编码技术作为抗干扰技术的一种重要手段 在数字通信领域和数字传 输系统中显示出越来越重要的作用 由于通信信道固有的噪声和衰落特性 信 号在经过信道传输到达通信接收端的过程中不可进免的会受到干扰而导致信号 失真 通常需要采用差错控制码来检测和纠正有信道失真引起的信息传愉错误 最早的纠错码主要是用于深空通信和卫星通信 随着数字蜂窝电话 数字电视 以及高分辨率数字存储设备的出现 编码技术的应用己经不仅仅局限于科研和 军事领域 而是逐渐在各种实现信息交流和存储的设备中得到成功应用 1948 年 C E Shannon 发表的著名的 通信的数学理论 一文 为信道编 码技术的发展指明了方向 Shannon 在著名的有噪信道编码定理中 给出了在 数字通信系统中实现可靠通信的方法以及在特定信道上实现可靠通信的信息传 输速率上限 Shannon 在他的证明中引用了三个基本条件 1 采用随机的编译码方法 2 构造码长的渐进好码或 Shannon 码 3 译码采用最佳的最大似然译码算法 50 多年来构造好码的思想基本上是按照 Shannon 所引用的基本条件的后两 条为主线进行研究的 经过 50 年的不懈努力 各种差错控制编码方案不断涌现 在 20 世纪 40 年代 R Harmming 和 M Golay 提出了第一个实用的差错控制 编码方案 使编码理论这个应用数学分支的发展俱到了极大的推动 Hamming 所采用的方法就是将输入数据每 4 个比特分为一组 然后通过计算将这些信息比 特的线性组合得到 3 个校验比特 然后将得到的 7 个比特送入计算机 计算机 按照一定的原则来读取这些码字 通过采用一定的算法 不仅能够检测到是否 淮海工学院二 八届毕业设计 论文 第 8 页 共 38 页 有错误发生 同时还可以找到发生单个比特错误的比特的位置 该码可以纠正 7 个比特中所发生的单个比特错误 这个编码方法就是分组码的基本思想 Hamrning 提出的编码方案后来被命名为汉明码 虽然汉明码的思想是比较先进的 但是它也存在许多难以接受的缺点 首 先 汉明码的编码效率比较低 它每 4 个比特编码就需要 3 个比特的冗余校验 比特 另外 在一个码组中只能纠正单个的比特错误 M Gaoiay 研究了汉明码 的这些缺点 并提出了两个以他自己的名字命名的高性能码字 一个是二元 Golay 码 在这个码字中 Golay 将信息比特每 12 个分为一组 编码生成 11 个 冗余校验比特 相应的译码算法可以纠正 3 个错误 另外一个是三元 Golay 码 它的操作对象是三元而非二元数字 三元 Golay 码将每 6 个三元符号分为一组 编码生成 5 个冗余校验三元符号 这样由 11 个三元符号组成的三元 Golay 码码 字可以纠正 2 个错误 1954 年 Reed 在 Muller 提出的分组码的基础上得到了一种新的分组码 称 为 Reed Muller 码 简记为 RM 码 RM 码在汉明码和 Golay 码的基础上前进了 一大步 在码字长度和纠错能力方面具有更强的适应性 RM 码是一类参数选择 范围很广的分组码 1969 年到 1977 年之间 RM 码在火星探测方面得到了极为 广泛的应用 即使在今天 IBM 码也具有很高的研究价值 其快速的译码算法 非常适合于光纤通信系统 在 RM 码提出之后人们又提出了循环码的概念 循环码实际上也是一类分组 码 但它的码字具有循环移位特性 即码字比特经过循环移位后仍然是码字集 合中的码字 这种循环结构使码字的设计范围大大增加 同时大大简化了编译 码结构 循环码的另外一个特点就是它可以用一个幕次为 n k 的多项式来表示 循环码也称为循环冗余校验 CRC Cyclic Redundancy Check 码 并且可以用 Meggitt 译码器来实现译码 Hocquenghem 在 1959 年 Base 和 Ray Chaudhuri 研究组在 1960 年几乎同 时提出了 BCH 码 BCH Bose Chaudhuri Hocquenghem BCH 码是循环码的一个非 常重要的子集 BCH 码的码字长度为 n r 1 其中 m 为一个整数 二元 BCH 码的 纠错能力限为 1960 年 Reed 和 solomon 将 BCH 码扩展到了非二元 21 2 m t 的情况 得到了 RS Reed Solomon 码 RS 码的最大优点是其非二元特性可以 纠正突发错误 但直到 1967 年 Berlekamp 给出了一个非常有效的译码算法之后 RS 码才得到了广泛的应用 此后 RS 码在 CD 播放器 DVD 播放器以及 CDPD Cellular Digital Packet Dara 标准中都得到了很好的应用 1955 年 Elias 等人提出了卷积码 卷积码与分组码的不同在于分组码在编 码之前先将信息序列按照一定的数据块长度分组 然后对每一组信息进行独立 编码 即对于 n k 分组码来说 码字中的 n k 个检验元仅与本码字的 k 个信息 淮海工学院二 八届毕业设计 论文 第 9 页 共 38 页 元有关 而与其他码字的信息元无关 卷积码中的 n k 个校验码不仅与本码字 的 k 个信息元有关 还与之前码字的信息元有关 Fomey 在 1966 年提出的两个短码构造长的串行级联的思想 其基本思想是 将编制长码的过程分级完成 从而通过用短码级联构造长码的方法来提高纠错 码的纠错能力 级联码的目标是构造具有较大等效分组长度的纠错码 并且允 许将最大似然译码分为几个较简单的译码步骤 这样便得到一个次最优但实际 可行的译码策略 其纠错能力强 译码也不复杂 展现了构造 Shannon 码美好的 前景 20 世纪 70 年代期间 在构造 Shannon 码中一个重要成果是 1972 年由 Justeson 用级联构造的 justeson 码 另一个重要成果是前苏联学者 Goppa 在 用有理分式表示码字基础上所构造的 Goppa 码 其渐进性很好 但 n 很长时 真正构造出这种好码仍然很困难 构造 Shannon 码的一个重要突破是 80 年代初 由 Goppa 提出的代数几何码 他将代数几何的理论和方法系统地应用于编码理 论中 使得原来线性码中的重要参数如码长 距离 维数等具有全新的几何意 义 代数几何码的研究成为 80 年代和 90 年代编码领域中研究热点之一 在传统通信系统的最佳接收机中 解调器和译码器是独立的两个部分 在 处理接收信号的过程中 解调器首先对调制器输入符号做最佳判决 然后将硬 判决结果送给译码器 译码器再对编码器输入消息做最佳判决 纠正解调器可以 发生的错误判决 这是硬判决译码的思想 事实上 经过解调器对符号的硬判 决 丢失了很多有利于译码的信息 为了提高编码通信系统的性能 人们从信 息论的角度对接收机中解调器与信道译码器的功能划分和接口重新进行了审视 提出了软判决译码方法 即解调器对输出不进行判决 送到译码器的是判决符 号可能的概率值或未量化输出 而非硬判决值 则译码器就可以利用这些信息 与编码信息综合做出判决 从而提高系统性能 这就是软判决译码的基本思想 研究表明 在接收机中解调器采用软输出可以得到比硬输出高 2dB 左右的附加 编码增益 软判决译码算法主要分为两大类 一类是使符号错误概率最小的逐位软判决 译码算法 如 1974 年有 Bahl Cocke Jelinek 和 Raviv 共同提出的前向后向最 大后验概率 MAP 译码算法 也称为 BCJR 算法 和 Lee 提出的前向 MAP 算法 1976 年 Hartman 和 Rudolph 提出的逐位译码算法 HR 算法 以 1971 年 Weldon 提 出的重量删除译码算法 WED 算法 等 另一类是使码字错误概率最小的逐组软 判决译码方法 如 I966 年 Forney 提出的广义最小距离译码 GMD 算法 1972 年 Chase 提出的 Chase 算法以及 1967 年 Viterbi 提出的 Viterbi 译码算法等 1974 年 J Massey 提出了将编码与调制作为一个整体看待可能会提高系统 性能的设想 此后 许多学者研究了将此设想付诸于实践的途径 其中 1982 淮海工学院二 八届毕业设计 论文 第 10 页 共 38 页 年 Ungerboeck 提出的 TCM 概念是解决带宽和纠错这对矛盾的一个理想方案 它 将纠错编码技术与调制技术有机结合 在不增加系统带宽要求的条件下通过扩 展符号空间来达到提高编码增益的目的 TCM 技术奠定了限带信道上编码调制 技术的研究基础 被认为是信道编码发展中的一个里程碑 另外 几乎在同一 时期日本学者 Imai 提出了一种采用分组码的编码调制技术 称为 BCM Block Coding Modulation 技术 它在衰落信道中的性能比较突出 虽然软判决译码 级联码和编码调制技术都对信道码的设计和发展产生了 重大影响 但是其增益与 Shannan 理论极限始终都存在 2 3dB 的差距 因此 在 Turb 码提出以前 信道截止速率 RO 一直被认为是差错控制码性能的实际 极限 Shannon 极限仅仅是理论上的极限 是不可能达到的 直到 1993 年 Turbo 码的提出以及 1996 年又发现的低密度校验 Low Density Parity Check LDPC 码 才让人们看到了逼近 Shannon 限的可能 1 3 QPSK 码的研究现状 QPSK 是英文 Quadrature Phase Shift Keying 的缩略语简称 意为正交相 移键控 是一种数字调制方式 四相相移键控信号简称 QPSK 它分为绝对相 移和相对相移两种 由于绝对移相方式存在相位模糊问题 所以在实际中主要 采用相对移相方式 QDPSK 它具有一系列独特的优点 目前已经广泛应用于无 线通信中 成为现代通信中一种十分重要的调制解调方式 在数字信号的调制 方式中 QPSK 四相移键控是目前最常用的一种卫星数字信号调制方式 它具有较 高的频谱利用率 较强的抗干扰性 在电路上实现也较为简单 偏移四相相移键控信号简称 O QPSK 全称为 offset QPSK 也就是相对移相 方式 OQPSK 它具有一系列独特的优点 已经广泛应用于无线通信中 成为现 代通信中一种十分重要的调制解调方式 在数字信号的调制方式中 QPSK 四相移键控是最常用的一种卫星数字信号调 制方式 它具有较高的频谱利用率 较强的抗干扰性 在电路上实现也较为简单 QPSK 数字解调包括 模数转换 抽取或插值 匹配滤波 时钟和载波恢复等 在实际的调谐解调电路中 采用的是非相干载波解调 本振信号与发射端 的载波信号存在频率偏差和相位抖动 因而解调出来的模拟工 Q 基带信号是 带有载波误差的信号 这样的模拟基带信号即使采用定时准确的时钟进行取样 判决 得到的数字信号也不是原来发射端的调制信号 误差的积累将导致抽样 判决后的误码率增大 因此数字 QPSK 解调电路要对载波误差进行补偿 减少非 相干载波解调带来的影响 此外 ADC 的取样时钟也不是从信号中提取的 当 取样时钟与输入的数据不同步时 取样将不在最佳取样时刻进行所得到的取样 值的统计信噪比就不是最高 误码率就高 因此 在电路中还需要恢复出一个 与输入符号率同步的时钟 来校正固定取样带来的样点误差 并且准确的位定 时信息可为数字解调后的信道纠错解码提供正确的时钟 校正办法是由定时恢 复和载波恢复模块通过某种算法产生定时和载波误差 插值或抽取器在定时和 载波误差信号的控制下 对 A D 转换后的取样值进行抽取或插值滤波 得到信 淮海工学院二 八届毕业设计 论文 第 11 页 共 38 页 号在最佳取样点的值 不同芯片采用的算法不尽相同 例如可以采用据辅助法 DA 载波相位和定时相位联合估计的最大似然算法 四相相移调制是利用载波的四种不同相位差来表征输入的数字信息 是四进制 移相键控 QPSK 是在 M 4时的调相技术 它规定了四种载波相位 分别为45 135 225 275 调制器输入的数据是二进制数字序列 为了能和四进制 的载波相位配合起来 则需要把二进制数据变换为四进制数据 这就是说需要 把二进制数字序列中每两个比特分成一组 共有四种组合 即 00 01 10 11 其中每一组称为双比特码元 每一个双比特码元是由两位二 进制信息比特组成 它们分别代表四进制四个符号中的一个符号 QPSK 中每次 调制可传输2个信息比特 这些信息比特是通过载波的四种相位来传递的 解调 器根据星座图及接收到的载波信号的相位来判断发送端发送的信息比特 数字调制用 星座图 来描述 星座图中定义了一种调制技术的两个基本 参数 1 信号分布 2 与调制数字比特之间的映射关系 星座图中规定 了星座点与传输比特间的对应关系 这种关系称为 映射 一种调制技术的特 性可由信号分布和映射完全定义 即可由星座图来完全定义 首先将输入的串行二进制信息序列经串 并变换 变成 m log2M 个并行数 据流 每一路的数据率是 R m R 是串行输入码的数据率 I Q 信号发生器将每 一个 m 比特的字节转换成一对 pn qn 数字 分成两路速率减半的序列 电 平发生器分别产生双极性二电平信号 I t 和 Q t 然后对 coswct 和 sinwct 进 行调制 相加后即得到 QPSK 信号 QPSK 是一种频谱利用率高 抗干扰性强的数调制方式 它被广泛应用于各 种通信系统中 适合卫星广播 例如 数字卫星电视 DVB2S 标准中 信道噪声 门限低至4 5 dB 传输码率达到45M bs 采用 QPSK 调制方式 同时保 证了信号传输的效率和误码性能 调制的作用是将基带信号转变为适合卫星信道传输的信号形式 由于卫星 上的能源有限 为了提高能源的利用率 卫星转发器的功率放大器通常工作于 非线性状态以提高效率 因此 卫星信道通常是非线性信道 这就要求卫星电 视应采用恒定包络的数字调制方式 四相移相键控 QPSK 是目前微波或卫星数字通信中最常用的一种数字调 制方式 它既是一种恒定包络的数字调制方式 而且占用较少射频带宽 频带 利用率高 抗干扰能力强 其原理框图如图1 2所示 图 1 2 QPSK 调制框图 QPSK 调制有4种不同的输出相位 对应于相继两种码元的4个组合 淮海工学院二 八届毕业设计 论文 第 12 页 共 38 页 00 01 10 11 可见 每输入两个比特后 输出相位才产生一次变化 可 见 在相同带宽下 传输码率可提高一倍 图2 56为 QPSK 调制的星座图 图 1 3 QPSK 调制的星座图 1 4 RS 码的研究现状 R S 码是一种循环码 它属于线性分组码 为了更好的理解 R S 码的检纠错 原理 我们先用一个简单的循环码为例进行说明 该循环码的生成电路图2 48 所示 该循环码的生成电路可以用多项式 f x x 1 来表示 设该电路的原 始状态为010 我们可以用 Galois 域中的运算关系进行分析 在伽罗华域中 每个元素 a 与移位寄存器的状态一一对应 并且都应满足上述的多项式关系 即 f a a 1 0 根据这一关系 我们可以看到 a 的幂次方能产生 Galois 域中的所有元素 如 a 010 100 当 a 的幂次方超过2 就应根据以 上的约束多项式来求解 图 1 4 循环码的生成电路 由此可见 从 a 到所对应的值就是原始状态为010的电路中 移位寄存器 在每个时钟作用下的移位寄存器的状态 在循环码中 检查是否有错码的方法 淮海工学院二 八届毕业设计 论文 第 13 页 共 38 页 是 用输入码字除以多项式 从检查余数是否为零来判断传输中是否出错 以上例子是对单个比特的处理 实际上还可以以符号为单位来处理 通常 选用8比特构成的符号 DVB S 系统采用的 R S 码就是以符号作为处理的单位 也就是说 分组是以符号为单位的 而不是以比特为单位的 在 R S 编码中 每个符号要先乘以某个基本元素的幂次方后才进行模2加 这里的乘法也是指 Galois 域中的乘法 它要受到某个约束多项式的约束 该多项式就是域多项式 图2 49是 R S 码编码器的原理框图 图 1 5 R S 码编码器的原理框图 如果每个符号有3比特 如基本元素 a 为010 输入为5个符号 与图中相应 的元素相乘后进行模2加输出 由于图中有两种系数 所以得到2个校验码 例 如 若输入为 A B C D E 则两个校验位 P Q 分别为 在接收端通过计算校验式 并根据校验式是否为零 来判断传输过程是否 有错 在以上的编码电路中 对应的校验式有两个 通过分析和推导可知 用来纠错 而则是用来确定错误的位置 更一般的结论是 要纠 t 个错误需要2t 个检验符 这时要计算2t 个等式 用来确定 t 个错误位置和纠 t 个错误 根据分组码理论可知 能纠 t 个符号错误的 R S 码生成多项式为 此外 还有一个截短码的概念 它是为了适应不同的码组长度而设计的 DVB S 采用 R S 208 188 10 编码 即分组码符号长度为208个字节 信息 符号长度为188个字节 可纠10个符号的错 该码就是由 R S 255 235 10 码的截短而得到的 实际上 可以把它看成235个符号中 除了188个符号外 其它的47个字符都用零来填充 因此 可用 R S 255 235 10 的编码电路 来完成编码 编码完成后 再把零字节去除就可以得到 R S 208 188 10 截短码了 外编码使用截短的 R S 码对扰码后的每个数据包进行编码 包括翻转和未 翻转的同步字节 其生成多项式和域多项式分别为 淮海工学院二 八届毕业设计 论文 第 14 页 共 38 页 1 1 其中 生成多项式 g x 是用来决定编码器的电路结构 域多项式 P x 则 是用来约束 Galois 域乘法规则的约束多项式 RS 208 188 10 编码包结构 如图2 50所示 图 1 6 RS 208 188 10 编码包结构 1 5 BPSK Binary Phase Shift Keying 二相相移键控 是把模拟信号转换成数据 值的转换方式之一 是利用偏离相位的复数波浪组合来表现信息键控移相方式 的一种 BPSK 使用了基准的正弦波和相位反转的波浪 使一方为 0 另一方为 1 从而可以同时传送接受 2 值 1 比特 的信息 由于最单纯的键控移相方式虽抗 噪音较强但传送效率差 所以常常使用利用 4 个相位的 QPSK 和利用 8 个相位的 8PSK 移相键控分为绝对移相和相对移相两种 以未调载波的相位作为基准的相 位调制叫作绝对移相 以二进制调相为例 取码元为 1 时 调制后载波与未 调载波同相 取码元为 0 时 调制后载波与未调载波反相 1 和 0 时 调制后载波相位差 1800 绝对移相的波形如下图所示 图 1 7 绝对移相的波形 2 1 线性分组码的概念2 信道编码基础 淮海工学院二 八届毕业设计 论文 第 15 页 共 38 页 不论那种编码方法 都需要遵循一些基本的定义和定理 都要使用一些 恰当的表达方法 不同编码方法的性能差异因信号传愉信道的不同而有所区别 因此需要考虑不同信道条件下的信道模型 不同的信道 其容量也不同 LDPC 码是一类分组码 本章首先简单介绍分组码的概念 编码方法以及译码 方法 接着对几类典型信道模型的信道容量进行简单的介绍 分组码是纠错码中最基本的一类编码方法 这里仅限讨论分组码类中最常用 的一个子类 线性分组码 同时由于本文只讨论二元码 即码元取值为 0 或 1 因此下面只涉及符号取自二元有限域 GF 2 的线性分组码 即二元线性分组码 线性分组码是把信息划成 k 个码元为一段 称为信息组 通过编码器变成 长为 n 个码元的一组 这 n 个码元的一组称为码字 码组 在二进制情况下信 息组共有个 因此通过编码器后 相应的码字也有个 称这个码字集合 k 2 k 2 k 2 为线性分组码 用 n k 表示 n 表示码长 k 表示信息位 码率 R k n 二元 线性分组码必须满足如下两个条件 1 码字集合中的任意两个码字经过模 2 加之后得到的结果仍然是码字集合 中的一个码字 2 码字集合中包含有全零码字 从数学角度讲 可以把一个 n k 线性分 组码看成二元 n 维线性空间上的 k 维子空间 因此 n k 线性分组码可以通过 由 k 个线性无关的二元 n 维矢量集合 来得到 得到的码字实 0 g 1 g 1k g 际上是这些 n 维矢量根据信息序列分组中各个比特的取值而得到的线性组合 2 2 生成矩阵和校验矩阵 线性分组码的编码过程可以描述为一个信息矢量 m 和一个矩阵相乘的结果 C m G 2 1 其中 C 是由 k 个 n 维矢量 构成的矩阵 m 是信息序列分 0 g 1 g 1k g 组 C 是编码得到的 n 维编码输出 其中矢量与矩阵的乘法 0 m 1 m 1k m 是在二元域 GF 2 上进行的 根据式 2 1 码字 C 可以表示为 C 2 2 0 m 0 g 1 m 1 g 1k m 1k g 而矩阵 G 称为编码生成矩阵 形式为 淮海工学院二 八届毕业设计 论文 第 16 页 共 38 页 G 2 3 0 1 1 k g g g 0 00 10 1 1 01 11 1 1 01 11 1 n n kkkn ggg ggg ggg 例如 对于一个二元 7 3 线性分组码 其生成矩阵可以为 G 1001110 0100111 0011101 如果编码信息分组为 m 01 1 C mG 01 1 1001110 0100111 0011101 01 1 1010 表 2 1 给出了 7 3 线性分组码的所有信息分组和生成码字 表 2 1 7 3 线性分组码的信息分组和码字 信息序列分组 m码字 c 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 和每个线性分组码相联系的还有另一种有用的矩阵 对于任意有 k 个线性 独立行的 k n 矩阵 G 存在有一个具有 n 一 k 行线性独立的 n k n 阶矩阵 H 它使得 G 的行空间中的任意向量都和 H 的行正交 且与 H 的行正交的任意向 量都在 G 的行空间中 因此我们用另一种方法来描述由 G 生成的 n k 线性码 一个 n 维向量 C 是 G 生成的码字中的码字 其充要条件为 2 4 TT C HO 此时 H 称为一致校验矩阵 一般情况下 一个 n k 码的 H 矩阵可表示为 H 2 5 1 11 21 0 2 12 22 0 1 1 0 h nn nn n k nn k nn k hh hhh hhh 则式 2 5 表示成 淮海工学院二 八届毕业设计 论文 第 17 页 共 38 页 0 2 6 0 c 1 c 1n c 1 11 1 1 2 22 2 2 1 02 0 0 h nnn k n nnn k n n k hh hhh hhh 因 G 中的每一行及其线性组合均为 n k 码的一个码字 所以由式 2 4 可知 2 7 0 T G H 例如 对于一个二元 7 3 线性分组码 其相应的校验矩阵可以为 1011000 1110100 1100010 0110001 H 显然满足0 T G H 2 3线性分组码的最小距离 好的编码方式应该使得到的码字之间的区别尽可舱大 对于二元码而言 码字集合中任何两个码字之间的区别就表现在它们相应位置上比特取值的区别 为衡量码字之间的区别 该里宁望码字距离与重叠的概念 定义 1 两个 n 重 x y 之间 对应位取值不同的个数 称为它们之间的 汉明距离 用 d x y 表示 例如 若 x 10101 y 01111 则 d x y 3 定义 2 n 维向最 x 中非零码元的个数 称为它的汉明重童 简称重级 用 w x 表示 例如 若 x 10101 则 w x 3 若 y 01111 则 w y 4 等等 定义 3 n k 分组码中 任何两个码字之间距离的最小值 称为该分组码 的最小汉明距离 简称最小距离 0 d 0 min x yn k dd x y 例如 3 2 码 n 3 k 2 共有 4 个码字 000 011 101 110 显然 2 2 2 0 d 是线性分组码的另一个重要参数 它表明了分组码抗干扰能力的大小 0 d 因此有时线性分组码也用 n k 表示 下面给出线性分组码和校验矩阵之间的 关系 定理 1 n k 线性分组码有最小距离等于的充要条件是 矩阵中 0 d 0 d 淮海工学院二 八届毕业设计 论文 第 18 页 共 38 页 任意式 1 列线性无关 0 d 2 4 系统码 对于线性分组码的码字 我们希望它具有如图 2 1 所示的系统结构 其码 字划分成两部分 即消息部分和冗余校验部分 信息部分由 k 个未变化的信息 数字组成 冗余校验部分由 n k 位一致校验数字组成 它们是信息数字的线性 组合 有这种结构的线性分组码称为线性系统分组码 K 位信息位n k 位校验位 图 2 1 码字的系统形式 因此 系统的生成矩阵为 2 8 K GIP 其中 P 是 k n k 阶矩阵 是 k 阶单位阵 如果信息位不在码字的前 k 位 K I 而在码字的后 k 位 则 G 矩阵的单位阵在 P 矩阵的右边 K I 若 n k 线性码生成矩阵为式 2 8 的系统形式 则一致校验矩阵 H 可取 如下形式 2 r n k HPI 9 式中 是一个 n 一 k k 阶矩阵 它是 P 矩阵的转置 一 号表示矩 r P T P 阵中的每一元素是 P 矩阵中对应元素的逆元 在二进制情况下 仍是该元素自 己 显然由此得到的 H 矩阵满足 0 T K K P G HIP I 2 5 循环码和准循环码 一个线性分组码 若它的任一码字左移或右移一位后 得到的仍是该码