基于VHDL的循环码编译码器的设计毕业论文.doc

北华航天工业学院毕业论文 I 基于基于 VHDLVHDL 的循环码编译码器的设计毕业论文的循环码编译码器的设计毕业论文 目 录 摘 要 I 第第 1 1 章章 绪论绪论 1 1 1 1设计目的和要求 1 1 2背景及国内外研究概况 1 1 3本次设计完成的主要工作 2 第第 2 2 章章 EDAEDA 技术技术 3 3 2 1EDA 概述 3 2 2VHDL 语言介绍 3 2 3VHDL 语言的特点 4 2 4可编程逻辑器件 5 2 5QUARTUS II 概述 6 2 6QUARTUS II 数字系统开发流程 7 2 7小结 8 第第 3 3 章章 常用循环码简介常用循环码简介 9 9 3 1循环码 9 3 2R S 码 10 3 3非本原 BCH 码 10 3 4小结 11 第第 4 4 章章 基于基于 BCHBCH 码设计原理码设计原理 1212 4 1编码器设计原理 12 北华航天工业学院毕业论文 II 4 2译码器设计原理 13 4 2 1由接收多项式 r x 求伴随式 s 13 4 2 2由伴随式求出错误位置 15 4 2 3搜索法译码原理 17 4 3主模块电路设计方框图 18 4 3 1编码器电路 18 4 3 2综合计算电路 18 4 3 3迭代译码算法电路 19 4 3 4钱氏搜索译码电路 19 4 3 5差错定位电路 20 4 3 6译码器电路 双纠错码 20 4 4小结 21 第第 5 5 章章 程序设计实现程序设计实现 2222 5 1程序设计总流程图 22 5 2编码器顶层文件主程序 23 5 3译码器顶层文件主程序 24 5 4编码器顶层文件生成模块 27 5 5译码器顶层文件生成模块 28 5 6编码器仿真图 28 5 7译码器仿真图 29 5 8小结 30 第第 6 6 章章 结论结论 3131 致致 谢谢 3232 参考文献参考文献 3333 附附 录录 3434 附录 1 34 附录 2 43 北华航天工业学院毕业论文 1 基于 VHDL 的循环码编译码器的设计 第 1 章 绪论 1 1 设计目的和要求 BCH 码是一种重要而有效的纠正多个随机错误的循环码 它的纠错能力很强 在短和 中等码长下 其性能很接近于理论值 并且构造方便 编码简单 因此 在通信领域中 BCH 码的应用极为广泛 本设计中将一组循环码输入 并且能编码 再纠错 再到解码输出的一个过程 15 7 码是距离 d 5 的本原 BCH 码 它能有效的纠正 2 位随机错误 对不同的设计方法 进行分析和比较 选择优化的设计方法 利用 VHDL 分别设计 15 7 BCH 码的编码器 和译码器 并能够对两部分进行单独仿真调试 实现其相应的功能 作为通信工程专业的学生 通过这次循环码编译码方面的毕业设计 可以提高本人 对编码领域及通信电路设计领域的认识 有利于培养我在通信编码方面的设计能力 一 人一题特别有利于锻炼我独立分析问题和解决问题的能力 设计过程的复杂加老师的严 格要求有益于培养本人严谨的工作作风 1 2 背景及国内外研究概况 提高信息传输的可靠性和有效性 始终是通信工作所追求的目标 纠错码是提高信 息传输可靠性的一种重要手段 1948 年香农 Shannon 在他的开创性论文 通信的数 学理论 中 首次阐明了在有扰信道中实现可靠通信的方法 提出了著名的有扰信道编 码定理 奠定了纠错码的基石 根据香农的思想 研究者先后给出了一系列设计好码和 有效译码的方法 以后 纠错码受到了越来越多的通信和数学工作者 特别是代数学家 的重视 使纠错码无论在理论上还是在实际中都得到了飞速发展 比如 BCH 卷积码 Turbo 码 LDPC 码等 北华航天工业学院毕业论文 2 BCH 码译码算法的研究一直是编解码领域的主要研究课题 至今已经提出了多种译码 算法 但是这些传统的译码算法用硬件实现较为复杂 而且延时比较严重 而一种码在实 际中能否得到广泛的应用 往往取决于译码器是否精简 快速 文中将讨论一种简单 快 速的 BCH 译码器的 VHDL 设计方法 现代数据传输通信中 常常因传输差错造成误码错码 尤其在无线通信中 空中的突发 或随机干扰噪声会造成编码差错 为了提高传输的正确率 往往采用一些校验方法 以检 验纠正传输差错 通信中校验的方法很多 如 BCH 卷积码 Turbo 码 LDPC 码等 其中 的 BCH 编码有其独特的优点 它的纠错能力很强 特别在短和中等码长下 其性能很接近 于理论值 构造方便 编码简单 不仅可以检纠突发性错误 还能检纠随机差错 因此 在通信系统中得到广泛应用 如在我国地面数字电视广播标准中就选用了 BCH 762 752 码 循环码是在严密的代数理论基础上建立起来的 是线性分组码的一种 这种码的编 码和解码设备都不太复杂 而且纠错的能力较强 顾名思义 循环码除具有线性码的一 般性质之外 还有循环性 即任一码组循环移位以后 仍为该码中的一个码组 从信道编码定理的公式出发 不强调物理意义 只是从数学角度分析如何使不等式 左边的减小 是负指数函数 从数值看欲减小可走增大码长 N 或增大可靠性函数 e P e P e P E R 两条路 而想增大 E R 又有加大信道容量 C 或减小码率 R 两条路 对于同样的码率 R 信道容量大的 其可靠性函数 E R 也大 若信道容量 C 不变 码率减小时其可靠性函数 E R 增大 1 3 本次设计完成的主要工作 本文设计中主要包括以下内容 方案论证 画出组成方框图 画出系统工作的时序图 设计组成系统的各单元电路 完成整个系统的设计 进行部分电路的时序仿真 并对仿真结果进行分析 完成整个系统的仿真调试和性能分析 撰写毕业设计论文 北华航天工业学院毕业论文 3 第 2 章 EDA 技术 2 1 EDA 概述 EDA 是电子设计自动化 Electronic Design Automation 的缩写 在 20 世纪 90 年代 初从计算机辅助设计 CAD 计算机辅助制造 CAM 计算机辅助测试 CAT 和计算机辅助 工程 CAE 的概念发展而来 EDA 技术是在电子 CAD 技术基础上发展起来的计算机软件系 统 是指以计算机为工作平台 融合了应用电子技术 计算机技术 信息处理及智能化 技术的最新成果 进行电子产品的自动设计 EDA 技术就是以计算机为工具 设计者在 EDA 软件平台上 用硬件描述语言 HDL 完 成设计文件 然后由计算机自动地完成逻辑编译 化简 分割 综合 优化 布局 布 线和仿真 直至对于特定目标芯片的适配编译 逻辑映射和编程下载等工作 典型的 EDA 工具中必须包含两个特殊的软件包 即综合器和适配器 综合器的功能就是将设计 者在 EDA 平台上完成的针对某个系统项目的 HDL 原理图或状态图形描述 针对给定的 硬件系统组件 进行编译 优化 转换和综合 最终获得欲实现功能的描述文件 综合 器在工作前 必须给定所要实现的硬件结构参数 它的功能就是将软件描述与给定的硬 件结构用一定的方式联系起来 也就是说 综合器是软件描述与硬件实现的一座桥梁 综合过程就是将电路的高级语言描述转换低级的 可与目标器件 FPGA CPLD 相映射的网 表文件 电子设计自动化的重要特征就是要求采用形式化语言来描述硬件电子电路的功能 即使用硬件描述语言来描述硬件电子电路 目前 作为硬件描述语言之一的 VHDL Very High Speed Integrated Circuit Hardware Description Language 已经成为各家 EDA 工具和集成电路厂商所普遍认同和共同推广的标准化硬件描述语言 2 2 VHDL 语言介绍 VHDL 的英文全名是 Very High Speed Integrated Circuit Hardware Description 北华航天工业学院毕业论文 4 Language 诞生于 1982 年 1987 年底 VHDL 被 IEEE 和美国国防部确认为标准硬件描述 语言 VHDL 主要用于描述数字系统 的结构 行为 功能和接口 除了含有许多具有硬 件特征的语句外 VHDL 的语言形式和描述风格与句法是十分类似于一般的 计算机 高级语言 VHDL 的程序结构特点是将一项工程设计 或称设计实体 可以是一个元 件 一个电路模块或一个系统 分成外部 或称可视部分即端口 和内部 或称不 可视部分 即涉及实体的内部功能和算法完成部分 在对一个设计实体定义了外 部界面后 一旦其内部开发完成后 其他的设计就可以直接调用这个实体 这种将设 计实体分成内外部分的概念是 VHDL 系统设计的基本点 随着信息技术的不断发展 电子技术面临着严峻的挑战 为了跟上快速变化的步 伐 电子产品的设计不得不非常快 模拟设计依然 是很特殊的职业 数字设计已变 得非常依赖于计算机辅助设计 设计自动化 DA 或电子设计自动化 EDA 2 3 VHDL 语言的特点 VHDL 语言能够成为标准化的硬件描述语言并获得广泛应用 它自身必然具有很 多其他硬件描述语言所不具备的优点 归纳起来 VHDL 语言主要具有以下优点 1 VHDL 语言功能强大 设计方式多样 VHDL 语言具有强大的语言结构 只需采用简单明确的 VHDL 语言程序就可以描述 十分复杂的硬件电路 同时 它还具有多层次的电路设计描述功能 此外 VHDL 语 言能够同时支持同步电路 异步电路和随机电路的设计实现 这是其他硬件描述语 言所不能比拟的 VHDL 语言设计方法灵活多样 既支持自顶向下的设计方式 也支 持自底向上的设计方法 既支持模块化设计方法 也支持层次化设计方法 2 VHDL 语言具有强大的硬件描述能力 VHDL 语言具有多层次的电路设计描述功能 既可描述系统级电路 也可以描述 门级电路 描述方式既可以采用行为描述 寄存器传输描述或者结构描述 也可以采 用三者的混合描述方式 同时 VHDL 语言也支持惯性延迟和传输延迟 这样可以准 确地建立硬件电路的模型 VHDL 语言的强大描述能力还体现在它具有丰富的数据类 型 VHDL 语言既支持标准定义的数据类型 也支持用户定义的数据类型 这样便会 给硬件描述带来较大的自由度 北华航天工业学院毕业论文 5 3 VHDL 语言具有很强的移植能力 VHDL 语言很强的移植能力主要体现在 对于同一个硬件电路的 VHDL 语言描述 它可以从一个模拟器移植到另一个模拟器上 从一个综合器移植到另一个综合器上或 者从一个工作平台移植到另一个工作平台上去执行 4 VHDL 语言的设计描述与器件无关 采用 VHDL 语言描述硬件电路时 设计人员并不需要首先考虑选择进行设计的器 件 这样做的好处是可以使设计人员集中精力进行电路设计的优化 而不需要考虑 其他的问题 当硬件电路的设计描述完成以后 VHDL 语言允许采用多种不同的器件 结构来实现 5 VHDL 语言程序易于共享和复用 VHDL 语言采用基于库 library 的设计方法 在设计过程中 设计人员可以建立 各种可再次利用的模块 一个大规模的硬件电路的设计不可能从门级电路开始一步步 地进行设计 而是一些模块的累加 这些模块可以预先设计或者使用以前设计中的存 档模块 将这些模块存放在库中 就可以在以后的设计中进行复用 由于 VHDL 语言是一种描述 模拟 综合 优化和布线的标准硬件描述语言 因 此它可以使设计成果在设计人员之间方便地进行交流和共享 从而减小硬件电路设 计的工作量 缩短开发周期 2 4 可编程逻辑器件 可编程逻辑器件英文全称为 programmable logic device 即 PLD PLD 是由 一种通用集成电路产生的 它的逻辑功能按照用户对器件编程来确定 一般的PLD 的集成度很高 足以满足设计一般的 数字系统的需要 这样就可以由设计人员自行 编程而把一个数字系统 集成 在一片 PLD 上 而不必去请芯片制造厂商设计和制 作专用的集成电路芯片了 可编程逻辑器件的两种主要类型是现场可编程门阵列 FPGA 和复杂可编程逻 辑器件 CPLD 这两类可编程逻辑器件中 FPGA 提供了最高的逻辑密度 最丰富 的特性和最高的性能 现在最新的FPGA 器件 如 Xilinx Virtex 系列中的部分器 件 可提供八百万 系统门 相对逻辑密度 这些先进的器件还提供诸如内建的 硬连线处理器 如 IBM Power PC 大容量存储器 时钟管理系统等特性 并支持 北华航天工业学院毕业论文 6 多种最新的超快速器件至器件 device to device 信号技术 FPGA 被应用于范围 广泛的应用中 从数据处理和存储 以及到仪器仪表 电信和数字信号处理等 与此相比 CPLD 提供的逻辑资源少得多 最高约 1 万门 但是 CPLD 提供了 非常好的可预测性 因此对于关键的控制应用非常理想 PLD 与一般数字芯片不同的是 PLD 内部的数字电路可以在出厂后才规划决定 有些类型的 PLD 也允许在规划决定后再次进行变更 改变 而一般数字芯片在出厂前 就已经决定其内部电路 无法在出厂后再次改变 事实上一般的模拟芯片 混讯芯片 也都一样 都是在出厂后就无法再对其内部电路进行调修 2 5 Quartus II 概述 Quartus II 是 Altera 公司在 21 世纪初推出的 CPLD FPGA 集成开发环境 是该公司 前一代 CPLD FPGA 集成开发环境 MAX PUS II 的更新换代产品 Quartus II 提供了一种 与结构无关的设计环境 其界面使设计者能方便地进行设计输入 快速处理和器件编程 Quartus II 还包含许多十分有用的参数化的模块库 它们是复杂或高级系统构建的重要 组成部分 Quartus II 加强了网络功能 它具有最新的 Internet 技术 设计人员可以 直接通过 Internet 获得 Altera 的技术支持 Quartus II 软件包是 Altera 公司专有知识产权的开发软件 适用于大规模逻辑电 路设计 其界面友好 集成化程度高 易学 易用 深受业界人士好评 Quartus II 软件的设计流程概括为设计输入 设计编译 设计仿真和设计下载等过程 该软件支持 多种编辑输入法 包括图形编辑输入法 VHDL Verilog HDL 和 AHDL 的文本编辑输入 法 符号编辑输入法 以及内存编辑输入法 与 MAX PLUS II 相比 Quartus II 设计软件增加了网络编辑功能 提升了调试能 力 解决了潜在的设计延迟 同时其直观易用的接口 深受数字系统设计者的青睐 Quartus II 开发系统具有以下主要特点 1 Quartus II 可以产生并识别 EDIF 网络表文件 VHDL 网络表文件和 Verilog HDL 网络表文件 为第三方 EDA 工具提供了方便的接口 2 Quartus II 支持一个工作组环境下的设计要求 包括支持基于 Internet 的协 作设计 与 Cadence Exemplar Logic Mentor Graphics Synopsys 和 Synplicity 等 EDA 供应商的开发工具相兼容 北华航天工业学院毕业论文 7 3 Quartus II 作为一种设计环境 除支持 Altera 的 APEX20KE APEX20KC APEX II ARM based Excalibur 嵌入处理方案 Mercury Stratix FLEX10KE 和 ACEX1K 外 还支持 MAX3000A 和 MAX7000 系列乘积项器件 4 Quartus II 增加了一个新的快速适配器编译选项 可保留最佳性能的设置 加 快了编译过程 可缩短 50 的编译时间 对设计性能的影响最小 2 6 Quartus II 数字系统开发流程 用 Quartus II 软件进行数字系统开发的流程如 包括以下步骤 如图 2 1 所示 图 2 1 Quartus II 设计开发流程 1 设计输入 包括原理图输入 HDL 文本输入 EDIF 网表输入 波形输入等 几种方式 2 编译 先根据设计要求设定编译方式和编译策略 如器件的选择 逻辑综 合方式的选择等 然后根据设定的参数和策略对设计项目进行网表提取 逻辑综合 器件适配 并产生报告文件 延时信息文件及编程文件 供分析 仿真和编程使用 3 仿真与定时分析 仿真和定时分析均属于设计校验 其作用是测试设计的 逻辑功能和延时特性 仿真包括功能仿真和时序仿真 定时分析器可通过三种不同的 分析模式分别对传播延时 时序逻辑性能和建立 保持时间进行分析 4 编程与验证 用得到的编程文件通过编程电缆配置PLD 加入实际激励 北华航天工业学院毕业论文 8 进行在线测试 在设计过程中 如果出现错误 则需重新回到设计输入阶段 改正错误或调整电 路后重新测试 2 7 小结 本章介绍了 VHDL 语言的特点及仿真软件工具 Quartus II 的简单介绍及 其数字 系统开发流程 VHDL 语言具有众多的优点 受到业内人士 尤其是通信领域 的喜爱 应用广泛 Quartus II 软件可理解为是 MAX PLUS II 的加强版 具有更强更直观的 仿真能力和效果 有兼容性强等更 完善的特点 本次设计也主要使用VHDL 语言进 行代码编写 QuartusII 软件进行模拟仿真 北华航天工业学院毕业论文 9 第 3 章 常用循环码简介 3 1 循环码 循环码是在严密的代数学理论基础上建立起来的 是线性分组码的一种 这种码的 编码和解码设备都不太复杂 而且纠错的能力较强 顾名思义 循环码除具有线性码的 一般性质之外 还具有循环性 即任一码组循环移位以后 仍为该码中的一个码组 在代数编码理论中 为了便于计算 经常将循环码表示成码多项式的形式 设码组 为 则码多项式定义如下 0121 aaaaa nn 0121 axaxaxaXT nn 在循环码除全 0 码组外 再没有连续 k 位均为 0 的码组 即连 0 的长度最 多只有位 否则 在经过若干次循环移位后将得到一个 k 位信息位全为 0 但 1 k 监督位不全为 0 的一个码组 因此 必须是一个常数项不为 0 的次多 xg kn 项式 而且这个还是这种码中次数为的唯一一个多项式 称这唯一的 xg kn 次多项式为码的生成多项式 一旦确定了 则整个循环码就被确 kn xg xg kn 定了 由此 可以写出循环码的生成矩阵 G 通常这时得到的循环码的生成矩阵不是典型矩阵 可通过线性变换转为典型矩阵 则循环码组可写成 21 XGaaaXT knnn 1 21 xgaxaxaxaXG knnn 所有的码组多项式都可被整除 而且任意一个次数不大于的多项式 xT xg 1 k 乘都是码多项式 该条性质用于编码 还可用于验证接收码组是否出错 xg 由于任一循环码多项式都是的倍式 故可写成 而 xT xg xgxhXT 本身也是一个码组 即有 由于是一个次多项式 故 xg xgXT X T kn 是一个 n 次多项式 在模运算下 也是该编码中的一个许用码组 可以写成 XTxk 1 n x 又由于等式左端分子和分母都是 n 次多项式 故 因此 xTxQxTx 1 xQ 上式可化成 最后 可得到 由此说明 1 xTxxTx n 1 xhxxgx kn 北华航天工业学院毕业论文 10 应该是的一个因子 xg 1 n x 3 2 R S 码 R S 码以它的发现者理得 Reed 和索罗蒙 Solomon 的姓氏开头字母命名 是 BCH 码最重要的一种子类 q 进制 BCH 码 R S 码的每个码元取值于 q 元符号集 使用时通常选取 q 为 2 的幂次 使 q 元符号集的所有非 0 210 q 2 m q 零元素 是基于某个 m 次本原多项式扩域的元素 编码时 每 m 210 q 2 m GF 个信息比特映射为一个 q 进制码元 便于与具有 4 8 16 32 点数的 PSK 或 2 m q QAM 调制信号集相匹配 近年来采用最多的是 m 8 即进制的 R S 码 以便25628 q 将整个 8bit 字节变为 R S 码的一个码元 本原 R S 码具有如下参数 码长 校验位 n k 2t 最小距离 生成多项式1 qn1 min knd 01 1 1 22 axaxaxaaxaxaxxg kn kn kn kn t 式中 的各次系数对照可知 RS xg 22 1 0 0 q i kni 1 min knd 码是极大最小距离码 从这种码的 n k 值立即可断定其纠错能力 2 int 21int min kndt R S 码的重量分布是已知的 在码重多项式第 i 次项的系数是 min 0 1 1 1 min min diqqA Di j Dji j i i i n i 3 3 非本原 BCH 码 非本原 BCH 码与本原 BCH 码的主要区别在于采用的根是否是本原元 本原多项式的 根的阶 因此给定 n 后即可知道本原多项式的次数 m 从而得到扩域 12 m n 而非本原多项式的根的阶 n 是的因式 给定 n 后还需要计算 m 2 m GF 12 m 若码长 但 n 是的因子 是域中的一个 n 阶元素但不是12 m n12 m 2 m GF 本原元 设是以为根的最低次多项式 则用生成的循环码称为非 xg t22 xg 本原 BCH 码 北华航天工业学院毕业论文 11 给定码长 n 和纠错能力 t 后 二进制非本原 BCH 码的构造方法如下 1 找出满足 n 是的因子的最小 m 值 12 m 2 找出一个 m 阶本原多项式 生成二元扩域 xp 2 m GF 3 求出的根 找出一个 n 阶的非本原元 xp n m 12 4 计算对应的最小多项式 并计算生成 1253 t 221 xxx t 多项式 1231 xxxLCMxg t BCH 码的基本特点是其生成多项式包含 2t 个连续幂次的根 若生成多项式含有 xg 2t 个连续幂次的根 则该码的最小距离 也就是说该码纠错能力是12 tdm BCH 的出现为通信系统设计者们在纠错能力 码长和码率的选择和控 tdm 2 1 int 制上提供了很大的灵活性 一旦要求的纠错能力 t 给定 只要算出 2t 个连续幂次的根所 对应的多项式作为生成多项式 就可以得到纠错能力符合要求的码 3 4 小结 本章主要对循环码 R S 码 非本原 BCH 码做了简单介绍 同时也做了简单的分析 比较 对本次设计优化方法选择起到关键作用 有关本原 BCH 码的介绍在下一章中有详 细的内容 本原 BCH 码也是循环码中最具特殊性的码类之一 主要考虑本原 BCH 码的计 算量小的特点 本次设计中应用的是本原 BCH 码 下面讨论的就是 15 7 本原 BCH 码编 译码器的 VHDL 设计 北华航天工业学院毕业论文 12 第 4 章 基于 BCH 码设计原理 4 1 编码器设计原理 BCH bose chaudhuri hocquenghem 码是循环码中的一大子类 它可以是二进制 码 也可以是非二进制码 本次设计中主要讨论二进制本原 BCH 码 二进制本原 BCH 码具有下列参数 式中 和纠错能力 12 12 min td mtkn n m 3 mm 是任意正整数 BCH 码的基本特点是其生成多项式包含个连续幂次的 2 1 m tt xgt 2 根 若生成多项式含有个连续幂次的根 则该码的最小距离 也就是说该t 212 min td 码纠错能力是 BCH 码的出现为通信系统设计者们在纠错能力 码长和 td 21int min 码率的选择和控制上提供了很大的灵活性 一旦要求的纠错能力 t 给定 只要算出个t 2 连续幂次的根所对应的多项式作为生成多项式 就可能得到纠错能力符合要求的码 已知码长 n 及纠错能力 t 二元本原 BCH 码具体的设计步骤如下 1 由关系算出 m 表查找 m 次本原多项式 用它产生一个扩12 m n xP 2 m GF 域 2 以本原多项式的根为本原元 分别计算 2t 个连续幂次根所 xP t22 对应的二元域上的最小多项式 221 xmxmxm t 3 计算这些最小多项式的最小公倍式 得到生成多项式为 221 xmxmxmLCMxg t 4 用关系式 导出系统码字 也可利用 xg xmx xr kn xrxmxC 编出 BCH 码字 xgxmxC 根据课题要求利用 VHDL 分别设计BCH 码的编码器和译码器 代入上式 得 7 15 计算出 即 111010001 导出5 2 7 4 15 dtkmn1 4678 xxxxxg 系统码字 将从 0000000 到 1111111 分别代入 得部份 xrxmxC 01233456 mmmmmmmm 北华航天工业学院毕业论文 13 系统码字为 4 2 译码器设计原理 BCH 码是一种循环码 因此线性分组码和循环码的译码方法对 BCH 码同样适用 其 中伴随式译码仍是最为通用的译码方法 译码的具体步骤与循环码一样 包括 1 由接收多项式计算出伴随式 s xr 2 由伴随式找出错误图样 xe 3 由得到发送码字的估值 完成译码 如果是非系统码 还须由 xexrxC 计算出信息多项式 xgxmxC xm 但鉴于 BCH 码自身的结构特点 BCH 码的译码方法也具有一些特殊性 4 2 1 由接收多项式 r x 求伴随式 s 设 BCH 码的码多项式为由 01 2 2 2 2 1 1 cxcxcxcxcxC n n n n 111111111111111 011101111110001 011101111101100 011000001001110 110110001100111 010100001101001 110010001111010 010000001110100 101110000101001 001100000100111 101010000110100 001000000111010 000100000011101 100110000010011 100010000001110 000000000000000 xC 北华航天工业学院毕业论文 14 知 若是生成多项式的根 则必是的根 因此 xgxhxC 21 ti i xg xC 4 0 01 2 2 2 2 1 1 cccccC iini n ni n i 1 写成矩阵形式为 0 1 12 110 T niii n ccc 4 2 设 代入式 4 2 得到ti21 4 3 即 cA 0 将上式与0 1111 1213121 2223222 232 110 ntnnn t t n ccccA 相比较可以看出 式 4 3 中的矩阵 A 等效为校验矩阵0 TTT GHmHGmcH 的转置 即 BCH 码的校验矩阵为 4 4 12222 12233 12222 12 1 1 1 1 nttt nt n n H 如果是的共轭元 则当且仅当时 有 也就是说 如果码 j i 0 i c 0 j c 字序列 c 和 H 矩阵第 i 行的内积为零 则 c 和 H 的第 j 行的内积也为零 因此可消去 H 的第 j 行 于是 BCH 码的校验矩阵 H 可以改写成为 11221212 12233 12 1 1 1 nttt nt n H 4 5 设接收多项式 4 01 2 2 1 1 xexcrxrxrxrxr n n n n 6 该接收多项式的伴随式为 将式 4 5 和式 4 6 代入 T t rHssss 221 s 得 tirrrrrrs n j ji j iiin n in ni 21 1 0 01 2 2 1 1 4 7 由此求出伴随式的各个分量 考虑码长 n 为 15 纠 2 个错误的 BCH 码 令为的本原元 则该码的奇偶 2 4 GF 北华航天工业学院毕业论文 15 校验矩阵为 利用的四维向量 4239363330272421181512963 141312111098765432 1 1 H 2 4 GF 表示法和等式 将 H 的每个元素都表示为它所对应的四维向量 得到该码的二进1 15 制奇偶校验矩阵如下 011110111101111 001010010100101 000110001100011 100011000110001 011110001001101 111100010011010 111000100110101 101111000100110 H 接收多项式 接收多项式的伴随式 01 13 13 14 14 xexcrxrxrxrxr T rHsssss 4321 41 01 13 13 14 14 irrrrrs iiii i 4 2 2 由伴随式求出错误位置 由于错误图样和伴随式一一对应 求出伴随式理论上就知道了错误位置 如前所述 与线性分组码中介绍的查表法译码原理一样 利用标准阵的陪集首与伴随式的关系 将 其制成表格 在求得了伴随式后 通过查表就可以得到所对应的错误图样 标准阵中的陪集首通常按照错误的个数从小到大排列 对于循环码 产生 1 个 kn 传输错误的错误样图个数为 产生 i 个的个数为 等等 当码长 n 比较小且纠错 1 n C i n C 能力 t 较小时 查表法简单有效 但是随着 n 和 t 的增大 查表法将变得复杂 这时可 以采用通过求解错误位置多项式的方法来确定错误位置 从而避免复杂的查表过程 BCH 码伴随式的各个分量可以表示为 4 i s iiii i eecrs 8 假设已由式 4 7 求出 设在位置上出错 即 i s xe v jjj xxx 21 4 v jjj jjjxxxxe v 21 0 21 北华航天工业学院毕业论文 16 9 将 4 9 代入式 4 8 得 为方便起见 令 tjtjtj t jjj jjj v v v s s s 222 2 222 2 1 21 21 21 则上式可化简得 4 vl lj l 1 ttt t v v v s s s 222 2 222 2 211 21 21 10 式 4 10 中列出了个方程 其中是个已知数 是 vt 2 t sss 221 t 2 v 21 个未知数 需要求解这个非线性方程 从而得到错误位置数 而实际上任何 v 21 一种解方程的方法就是一种译码算法 下面用迭代算法解答 4 10 式 首先定义一个错误位置多项式 它的根是错误位置的倒数 即 x 11 2 1 1 v 4 v vv xxxxxxx 2 21021 1 1 1 11 将式 4 10 的乘积展开 比较等式两边同幂次的系数 有 vv vv v 21 132212 211 0 1 4 12 式 4 10 给出了与的关系 式 4 11 给出了与的关系 将两者结合起来并 i s l l l 利用式 4 10 式 4 12 可以得到与的关系 i s l 0 03 02 0 12111 312213 2112 11 ssss sss ss s vvvv 4 13 称为牛顿恒等式 如果和错误个数 v 已知 则利用上述 v 个方程组即可求出 v 个未知 i s 数 如果 v 未知 假设 v t 根据自回归建模技术 可以由伴随式构造出一个矩阵 利 北华航天工业学院毕业论文 17 用前 t 个伴随式来得到下一个伴随式 经过数学运算 可得到有 t 个未知数的 t 个方程 构成的一个线性方程组 用矩阵表示为 t t t t t ttt t t s s s sss sss sss 2 2 1 1 1 121 132 21 4 14 该方程组有解的充要条件是系数矩阵满秩 在求得了伴随式后 利用上式即可 求得 l 根据本此设计要求 代入数据整理得 再根据牛顿恒等公式得 4 3 1 2 32 21 s s ss ss 32 2 2 2 3422 3 2 2 3 2 2 3421231 ssssss sssssssss 4 2 3 搜索法译码原理 设接收多项式 判断第一位是否有错误 即 01 2 2 1 1 rxrxrxrxr n n n n 1 n r 确定是否对应着错误位置 这等效于检验是否是的根 若是 1 n 1 n x 1 n 的根 则即 x 01 1 1 1 1 t t t t n 1 1 1 1 t t t t 也就是说 在得到错误位置多项式后 为判断 译码器先计算 x 1 n r 然后计算他们的和是否为 1 若是 则对应着错误位置 即 1 1 1 t t t t 1 n 码元出错 否则无错 类似地 为判断 译码器先计算 1 n r 2 n r llt t tl t 1 1 1 然后计算它们的和 若 则有错 1 1 1 1 llt t tl t 2 n r 则无错 1 1 1 1 llt t tl t 2 n r 以此类推 逐次判断每个即得到的所有根 从而得到错误位置 2 1 nlr ln x 这个方法将的各次方代入中计算其结果是否为 1 相当于错误位置多项式对 x 域元素的全体搜索了一遍 因此称为搜索法 也称钱氏搜索法 搜索法避开了因式分解 或其他求解高次方程方法在实现上的困难 而且每一步骤的方法都一样 特别适用于计 北华航天工业学院毕业论文 18 算机编程或数字电路实现 是一种普通应用的译码方法 北华航天工业学院毕业论文 19 4 3 主模块电路设计方框图 4 3 1 编码器电路 此编码器电路主要利用线性反馈移位寄存器 LFSR 实现了式 xrxmxC 如图 4 1 编码器电路所示 图 4 1 编码器电路 4 3 2 综合计算电路综合计算电路 此综合计算电路主要实现输入求出伴随多项式即在该电路的执行 xr i s 4321 ssss 过程中 寄存器初试时为空 每次移位 将向量逐步移入该电路 在第一次 1410 rrr 移位之后 寄存器中含有 第二次 含有的向量表示式 第三次含有 0 0 0 14 r 1314 rr 最后一个移入电路时 寄存器中含有向量表示式 如图 4 2 综 121314 rrr 0 r r 合计算电路所示 图 4 2 综合计算电路 b0 b1 b2 bn k 1 g1 g2 gn k 1 xn k i x c x S1 S2 1 2 S1 S2 S3 S4 r x 北华航天工业学院毕业论文 20 4 3 3 迭代译码算法电路迭代译码算法电路 此电路实现伯利坎普迭代算法 BMA 当错误位置多项式经过 t 1 次迭代后在 x C 中得到确认 如图 4 3 迭代译码算法电路所示 图 4 3 迭代译码算法电路 4 3 4 钱氏搜索译码电路钱氏搜索译码电路 此电路以一种简单 直接的方式实现错误位置校验过程 初始态 t 个寄存器中 存储着译码第二步得到的 在从缓冲区中读出之前 t 个乘法器工作一 t 21 1 n r 次 乘法运算被执行 且被存储在寄存器中 如图 4 4 钱氏搜索译 v v 2 21 码算法电路所示 B2 B3 B4 Bt C1 C2 C3 C4 Ct Sj 1 Sj 2 Sj 3 Sj 4 Sj t 1 Sj 2 Sj 1 Sj inv dr reg 0 0 1 buffer 0 1 2 t 2 t t i il i 1 input output 北华航天工业学院毕业论文 21 图 4 4 钱氏搜索译码算法电路 4 3 5 差错定位电路差错定位电路 寄存器和分别发起被和使用 如果没有错 则 1 s 3 s 1 S 3 S0 0 21 0 0 31 ss 如果有一个错 则 如果有两个错 则0 0 21 3 131 0sss 0 0 21 如果 则有多于 2 个错误 因此错误不能纠正 如图 4 5 差 3 131 0sss 3 131 0sss 错定位电路所示 s1 s3 3 s1 3 s1 0 s1 3 s3 S1 S3 h1 h3 p1 p3 error decision circuit b u f f e r r x output 图 4 5 差错定位电路 4 3 6 译码器电路 双纠错码 译码器电路 双纠错码 此电路将实现双错误码的纠正 dsyn1 dsyn2 为计算电路 dch1 dch3 为钱氏搜索 电路 deq 为比较纠错电路 ffce 为 D 触发器序列产生电路 dcount 为 n 计数器模块 dbuf 为缓冲器寄存器 如图 4 6 双纠错电路所示 b1 dbuf s1 dsyn1 s3 dsyn3 c1 dcount h3 dch3 e1 deq f2 ffce f1 ffce h1 dch1 din dout syn1 syn3 ch1 ch3 neq 北华航天工业学院毕业论文 22 图 4 6 双纠错电路 4 4 小结 本章主要介绍了基于 BCH 码的编译码原理 理论分析 数学推论 主模块电路设计 样图 编码器运用反馈移位寄存器实现了系统码字的编码 译码器电路中应用到了迭代 译码算法 牛顿恒等式 钱氏搜索译码 双纠错电路等经典模拟电路分析及应用 北华航天工业学院毕业论文 23 din Y NN 第 5 章 程序设计实现 5 1 程序设计总流程图 图 5 1 程序设计总流程图 图 5 2 程序流程图 Y N 代码下载到模块电路 逻辑综合 软件模版与仿真 用 VHDL 语言描述电 路 功能设计 结果满意 完成 输出信息码 译码 纠错 编码 初始化并且输入七位信息码 开始 判断检查 结束 北华航天工业学院毕业论文 24 5 2 编码器顶层文件主程序 ENCODER LIBRARY IEEE 调用库函数 USE IEEE STD LOGIC 1164 ALL USE IEEE STD LOGIC UNSIGNED ALL ENTITY enc IS PORT clk reset din IN BIT vdin dout OUT BIT output serial data 串行数据输出 END enc vdin valid data in 有效数据 to enable external data shifting 转移外部数据 ARCHITECTURE enca OF enc IS SIGNAL vdin1 rin rout rll BIT rll ring loop lock 锁环 pe parallel enable din 并行 din COMPONENT ecount counter encoder 计数器编码 PORT clk reset IN BIT vdin OUT BIT END COMPONENT COMPONENT ering ring for encoder 循环编码 PORT clk rll din IN BIT dout OUT BIT END COMPONENT BEGIN c1 ecount PORT MAP clk reset vdin1 r1 ering 北华航天工业学院毕业论文 25 PORT MAP clk rll rin rout rin din AND NOT reset rll vdin1 AND NOT reset vdin vdin1 PROCESS BEGIN WAIT UNTIL clk EVENT AND clk 1 doutsc 并行 er correct error 纠错 vdout valid data out remenber data register SIGNAL ff1 ff3 err err1 err2 errcheck ce neq BIT SIGNAL syn1 syn3 BIT VECTOR 0 TO 3 北华航天工业学院毕业论文 26 syndroms 综合计算 SIGNAL ch1 ch3 BIT VECTOR 0 TO 3 Chien output 检错 SIGNAL ch1 or BIT VECTOR 0 TO 3 COMPONENT deq dout syn1 3 syn3 PORT syn1 syn3 IN BIT VECTOR 0 TO 3 dout OUT BIT END COMPONENT COMPONENT ffce PORT clk ce din IN BIT dout OUT BIT END COMPONENT COMPONENT dcount counter decoder 计数器解码器 PORT clk reset IN BIT cef pe vdout vdout1 OUT BIT END COMPONENT COMPONENT dbuf buffer shift registers 缓冲寄存器 PORT clk err vdout din IN BIT dout OUT BIT END COMPONENT COMPONENT dsyn1 syndrom calculation 综合计算电路 1 PORT clk pe din IN BIT dout1 OUT BIT VECTOR 0 TO 3 END COMPONENT COMPONENT dsyn3 syndrom calculation 综合计算电路 3 PORT clk pe din IN BIT dout3 OUT BIT VECTOR 0 TO 3 END COMPONENT COMPONENT dch1 Chein search circuit 检错电路 1 PORT clk err errcheck pe IN BIT 北华航天工业学院毕业论文 27 din IN BIT VECTOR 0 TO 3 dout OUT BIT VECTOR 0 TO 3 END COMPONENT COMPONENT dch3 Chein search circuit 检错电路 3 PORT clk err errcheck pe IN BIT din IN BIT VECTOR 0 TO 3 dout OUT BIT VECTOR 0 TO 3 END COMPONENT BEGIN c1 dcount PORT MAP clk reset cef pe vdout vdout1 b1 dbuf PORT MAP clk err vdout1 din reset dout e1 deq PORT MAP ch1 ch3 neq f1 ffce PORT MAP clk cefa ch1 or 3 ff1 f2 ffce PORT MAP clk cefa neq ff3 s1 dsyn1 PORT MAP clk pe din reset syn1 s3 dsyn3 PORT MAP clk pe din reset syn3 h1 dch1 PORT MAP clk err errcheck pe syn1 ch1 h3 dch3 PORT MAP clk err errcheck pe syn3 ch3 din reset din AND NOT reset ch1 or eq or gates 北华航天工业学院毕业论文 28 ch1 or 0 ch1 0 gen FOR i IN 1 TO 3 GENERATE ch1 or i ch1 or i 1 OR ch1 i END GENERATE cefa clock enable p1 p3 cepa 1 if start of a new word or err cefa cef OR e