（电路与系统专业论文）rs编译码的fpga实现.pdf

b ei n g an 如portan t l in 已 叮bl ock 以 xl e inthe . rr o r c o n 七 o l field， the rs cod e h asv e 口 引 比 。 ngco ry ec t l o n abil i t y soit is 幼d e lyu ， 对inv 面ous m ed em c o n u n u n l c at ion sy s t e m s as to， 鱿 1 吻 the re li abil ityofd a t a tr 田 ” 而ssionc h a n n el. 仆j s p a pe r m ai n l y di s c u se s 奴 环 访 d p l esan d the ai g e b r a l c co而g u r at 1 o n m e th edof r e ed一 solo m onc 团e and its如p l e m e nt ati onb as edonfpg a . t 七 e pe rformance ofthe cod e r 阴d d 以 刀 d e r h a s h ” n s h o 从 .妙 5 加u 】 at l on， andthe c o n e c in已 弧b asbee nv e n fi ed 勿 t e sl ai tbe e n d of而s p a per， t h e softdeci si on ofrs dsc ode r has b 沈 n di c us， 月t entati v e ly. mai n workin面s p al ” r fon o w s . fi rs u y ， 丁 七 e rs e n 以 对 era n d d 即ed e r are r e al l 欢 月衍也fpg a . 5 郎 。 ndly，byus i ngthe 几b m al gori t 加 m ， 1 o gi cuni t s are use dl ess and阮 s p e ed isai so l n c r e a s e d . 仆对 d 】 y，面5 p a p err e a l 泳s the g al oi asm u l t i p l ieran d d i v i d e r ， 5 抑d r o m e c ircu i t and the 肥 so l utionofthe k ey e q u a t i on c i r c u i t etc via v h d ll ang 坦 g e . fou rt h l y，the c h i an se arc h p rogre s s b 韶b een i m p ro v e d l n 面s p a p e r at l ast， the c h 1 p epl c 4 0 q 3 2 4 c 8 o f a l t e r a 1s c yc l o neh a s b e e n use d for the i m p 1 e m e n tatin nofthe proj e ct. k e y w o r d s :r s c ode ， 瓦b ma lgori t h m ， f ie l d p r o g ra n u n abl e g ate a rr ay 声明 本学位论文是我在导师的指导下取得的 研究成果， 尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人己经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 己 在论文中作了明确的说明。 研 究 生 签 “ : 斗 嶙 一 ) 坷年分感 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电 子和纸质文档， 可以 借阅 或上网公布本学位论文的部分或全部内容， 可以向有关部门 或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按 保密的有关规定和程序处理。 研究生签名:， 月 业 半 - 可 钊 月 日 硕士论文rs 编译码的fpg a实现 引言 .1 课题背景及意义 在现代通信系统中， 由 于信道的固 有噪 声以 及衰落 特性， 信号在经过信道 传输过 程中， 不可避免的 会受到千扰而出现信号失 真， 当 误码率达到 一定程度时会导 致通信 失 败。 因 此， 为了 保证通 信成功 就必须尽量减少 信道干扰对 信息估值的影响。 通常有 两个 方法来解决这个问 题: 一是增加信噪比: 另 一个即 采用纠 错编码ll 。 而在实际的 通信系统中如单纯以第一种方法来提高信息传输可靠性的代价比较大， 特别在卫星通 信中 轨道每瓦功率的费 用比较昂贵。 随 着编码理论和大 规模集成电 路技术的 发展， 编 译码设 备变得比 较容易实 现， 成本也比 单纯的 提高信噪比 节省很多， 因 此纠错 编码技 术 在实际的 数字通信中 逐渐得 到更广泛应用。 本课题来源于某通信系统中 车载站接收机的 实现方法， 该系统采用卫星通信方 式， 在接收机中采用了r s 编码与卷积码级联的编码技术， 以提高信息传输的可靠性。 加入本译 码模块对于整 个系统的 误码率有了 显 著的 提高， 使得该 系统在恶劣的 环境下 各种业务 仍然可以 可靠 传输。 本工程中 需要实 现高速 r s ( 1 26， 1 12 ) 硬件译 码器， 并且 需要 拥有 这种硬件译码 器的核 心实现技术来为 进一步的研究 任务奠定基础。 本文首先 对r s 编译码方案进 行总 体分析， 分析其数学公 式和各种算法， 给出其编译 码的 硬件 实现方 法， 同 时在q 崔 犷 tu s h平台 上对fpg a实 现方案进 行了 仿真验证， 并 最终在满 足工程标准的电路板上调试成功。 在硬件设计中充分考虑到设备的可靠性、 功耗、体 积、 重量和以 及高 速率的 应用， 同时也为以 后通信设备的 升级留 下了很大的 余地。 .2 国内外发展情况 现代信息和编码理 论的 奠基人c e s h annon在 1 9 48 年提出了 著名的 有噪信 道编 码定 理， 在定理中s h a n n o n 给出了 在数字 通信系统中实 现可靠通 信的方 法以 及在 特定 信道 上实现可靠通信的 信息传输速率上限。 同时， 该定理还给出了 有效差错控制 编码 的 存在性证明， 从而促进了信道 编码领域研究的 快速发展。 随着编 码理论 和v l sl技 术的发展，其应用范围越来越广泛。 特别近年来，国内外在寻求用于各类噪声信道上 有 效与实用的编 码方案方面以 及 在编解码的实 现和实际应用方 面进行了 大量 研究。 r s码是由reed和s o l omon在 1 9 6 0 年通过 论文 “ p o l 犯 lo m i alc o de o ver c e rt a i n f l n i t e fi el ds” 所提出的 12 。 在提出 的 初期， 当时的 数字电 子技 术却未能够根据 rs 码 的 有关内 容做出 相应的 实际应用。 为什么在 这漫长的五年时间 里却没法 获得有关的实 际 应用， 而对于同样的 r s码纠 错码理论又能够在 现代的 数字电 子技术领域里 发挥 硕士论文rs 编译码的fpg a实现 如此重要的作用 呢? 其中的 主要原因 在于把rs 码有效 地推向实际应 用的关 键技术 有效的rs 码 译码 算法， 未能 得到实际性的 突破。 尽管在 1961 年已 经 存在了 可 行的rs 码译码 算法， 即p g z 算法， 但是无论是当时 还是现在， 该算 法的复 杂性却不 适合通过数字电 子技术的实 现来开展有效的 应用。 然而， 到了1 9 65年， 由e berlek a m p 以 及j. m as sey 提出 的 有 效 译 码 算 法 13 ，4 最 终 为r s 码 的 实 际 应 用 解 决 了 最 后 的 障 碍 。 从提出到现在，r s码已 经在许多不同的领域中得到了应用， 如硬磁盘驱动器 ( h ard d is k driv e s) 、 c d 一 劝m 、 c n机 、 数 字 音 频 、 o v o 机 、 数 字电 视 、 数 字图 像 系 统、 大容量存储系统、远距离通信和数据广播协议、无线通信、单信息包数字数据 (c ellul ardi g ital p 二 k etd at a ) 、无 线个人数字处理 器、 可容错r a i d控制器、 深空探测 任务、 星际侦察( 访 记 印 l an e t 田 丁re co l 川 ai s sanc e ) 、xds l( a d s l ， v d s l ， h d s l ， s d s l ) 以 及移动系统的 地面同步卫星 通信对接(mobile sy s te m s g eo 一sync hr on o us sate lli te co nunamc a t i ons h n k s ) 等。 同 时， rs 码 在许多不同 的国 际标准中 得到了 相应 规定， 如c c s d s 、 正 e e 8 0 2. 1 4 一 a 、 ieee 8 0 2 . 1 4 一 b 、w- c d ma 、v s b 、i m，20 0 0 、d v b 以及 d v d 等。 而在国内外的航 天工作中，同 样r s 码在许多不同的 任务中 发挥 着重 要的 作用， 如在国内 则有实践5 号、 神舟 3 号、 神舟 4 号以 及探测 1 号等任务， 在国 外则有 m 州n e rg 、 物y a g e r l 、 玩y a g erz 、 伍o tto、 g 目 i l eo、 c as s 面、s m a rt . 1 、m axsp a t h fi n d e r 、m ar s l 田 l d e r 和m ars e 即 lo rat i o n r o v e r 等 任务 . 在近十年， 国内 对纠 错码的 研究也越来越 重视， 许多 行业都根据自 身的 特点把纠 错码应用到实际场合中以此来改善其行业系统性能。 ， .3 课题研究主要内容 本课 题围 绕某新型通信接收机的r s 译码实 现方法而展开， 对编码译码原理、 实 现方法进 行理 论分析， 并 给出 硬件实现方 法。 课 题主要工作就是分析便携通信 终端的 纠错码原理， 在此 基础上用f p g a予以 实 现并 满足工程标准提出的测 试性能， 最终用 于实际系统中。 本文主要完成以下 工作: 1 .阐 述本译码器设计的总 体方案。 2 .分 析纠错码的编 码及译 码的 原理， 详细分析rs 译码的 各种算 法。 3 .在 理解编译 码的 工作原 理基础上， 提出 基于f p g a硬件实现方案， 并给出 其 具体实现方法。 4 . 在满足工 程标准性能 基础上， 提出 改进结构。 5 . 在译码器实 现成功的 基础上对rs 软判决 译码器的 实现进行探讨。 硕士论文 rs 编译码的f p g a实现 ， . 4 论文组织结构 第二章简单介绍了系统实现硬件实现平台以及所采用的芯片。 第三章讲述了 纠错码的概 念， rs 码编码原 理以 及其 硬件实 现进行阐述。 重点 介 绍了r s 编码的原理，并分析其算法，给出了硬件实现方案，最后给验证仿真结果。 第四 章是对rs 码译码原理 进行阐述， 并分 析了 现今流行的多种译码 算法， 从中 做出了选择。 第五章是对rs 码译码器的 硬件实现 进行阐 述。 详细给出了 译码器各个模块的 硬 件实 现结构， 并附以仿真图， 最后对于译码器的 性能进行了 分 析。 第六章是对rs 码的软判决译码的原理以及实现方法进行阐述， 分析了流行的多 种软判决译码算法，最后给出了软判决译码器的性能仿真图。 第七章是本文的结论篇。 首先列出 纠错码模块 在各种测试环境下的误码率， 然后 根 据测试结果判定设计是否达到 预期的性能， 最后对本课 题的 后续工作指出 几个改进 方向。 硕 士论 文 rs 编译码的f p g a实现 2硬件实现平台 可编程逻辑器件不仅使设计的电子产品达到小型化， 集成化和高可靠度， 而且器 件具有用户可编程 性， 大大缩短了设计周期， 减少了设 计费用，降 低了 设计风险， 因 而 成为现代数字系 统设计的主要 手段， 为电 子电 路和系统的设计 提供了一 个新的 发展 方向。 fpg a (f i el d p r o g r an l m ab leg at e a rr a y ) 的 优点在于集成 度高， 体积小， 功耗低， 电 路简化，可靠性高。目 前主流的f p g a器 件主要分以 下三种: 1 . 基 于e e p r o m ( 或fl as h) 工 艺 的f p ga( 如a c tel 公 司 的a p a 系 列 )o 2 . 基于s r a m工艺的f p g a ( 如a li 王 r a公司的 所有f l e x ， a c e x ， apex 系 列， x l l inx公司的s p artan， v i rt e x 系列 ) ， 由 于s r a m工艺的 特点， 掉电后数 据会消 失，因 此调试期间可以 用下载电缆配置p l d器 件， 调试 完成后， 需要将数据固 化在 一 个专用的 e e p ro m 中 ( 用通用编程器烧写 ) ，上电时，由 这片配置 eep r o m 先对 p ld 加载数据， 十几个毫秒后， p l d即 可正 常工 作( 也可由c p u配置p ld) 。 但s ram 工艺的p l d一般不可以加密。 3 . 基 于 反 熔丝 (劫 fu se ) 技 术的f p 以， 如a c te l ， q ul cklog ic 及l u c e n t 公 司 的 部分产品就采用这种工艺. 用法与e e p o m的p l d一样， 但这种 p l d不能重复擦写， 所以 初期开发过 程比较麻烦， 费 用也比 较昂 贵。 但反熔丝 技术也 有许多 优点: 布线能 力 更强， 系 统速度更快， 功 耗更低，同 时抗 辐射能力强， 耐高 低温， 可以加密， 所以 在一些有特殊要求的领域中运用较多，如军事及航空航天。 2. ， 硬件芯片 选用 本课题主 要任务就是 对rs 编码译码器 算法进 行硬件优化实现并验 证， 不可 避免 的存在芯片不断被烧写， 所以首先 f p g a的选择否定了价格昂贵， 不能重复擦写的反 熔丝技术的f p g a 。 课题中需要实 现复 杂的 译 码算法， 在f p g a逻辑时序资源和 存储 资 源上使用 较多， 速度要 求很高。 结合上述要 求， 经过调研后决定采用 alte ra公司 c yclo ne系列的f p g a器件。 a lt e r a 公 司日 前推出 业界目 前 成本 最 低 的fpga 器 件 系列 产 品 c y cl o ne l5i. c yclo ne器件容量从2， 9 10到20，0 60个逻 辑单元 (2 40， 0 00个逻辑门 或一百 多万个系统 门 ) 和多 达2 88 kb 的嵌 入存储 器。 每个 c yc fo ne器件 都集成了 单数据率s d r a m以 及 双数据率 ( d d r)s d r a m和f c r a m器件的专 用接口 电路， 支持多种单端阳 标 准， 包括l v 下 几、 lvc o m s 、 p c i 、 s s t l . 2 和s s t l . 3 。 并具有多 达 1 2 9 个低电 压差分 信 号 (l v d s) 兼 容 通 道， 每 个通 道 性 能 可 高 达 3l l n 几 p s 。 其中 嵌 入 存 储 器 有 不 少 优 点 ， 不但支持 各种存储模式， 而且还支持字节 使能操作、 基于奇 偶校验的 纠错功能以 及不 硕 士论 文rs 编译码的fpg a实现 等 位宽的 端口 存 储器设计。根 据前端数据处理对逻辑资 源需求量，我 们选择c y c l one epic20 作为硬件设计平台。该芯 片包含 2 。 。 60 个 l e ( l o gi c el e m e n t ) ， 64 个 m 4 k r a m ( 即4kb its 的r a m ) ， 2 个锁相 环，最 大用户f o管脚为3 01。 2. 2 设计和验证平台 fpg a设计大体分为设计输入、功能 仿真、综合、布 局布线、 时序仿真( 后仿真) 和 配 置 下 载 等 六 个 步 骤 161 。 而a lt e r a 公 司 提 供 的q u 田 九 ”n 软 件 包 括 上 述f p ga 设 计 的 完整开发环境， 其中有原理图 和基于文本的设计输 入、 h d l综合、 布线、验证 和 配置下载。当然如果有需要并且有条件可以嵌入第三方专业的e d a工具。 在 本 课 题的 设 计中 使 用v h d l 语 言 作 为 设 计 输 入 端 工 具 门 ， m anto r g ra p h ic : 公 司 的m o de ls 如 s e 6 .if用 于 精 确 仿 真 ， s y n p lic ity公 司 的s y n p li 斤pro s .6. 2 用 来 做 高 层 次 的综合， 并最终 与a l t e r a 公司 的q u axtusll 7 .0综合的结 果进行比 较， 从中选择 较优 者。使用 m at l ab7. o 和 c c s作为调试和验证平台。在设计内容配置到电路板 epi c 20 后，通过d sp和 fpg a的 接口 将需观察的变量 读入计算机， 然后通过m a t l ab处理阁 和其编译码函数结果进行比较，验证设计的正确性。 2.3 小结 在本章主要介绍了系统实现的硬件平台和设计工具. 硕 士 论 文rs 编译码的fpg a实现 3r s 码编码器的实现 3. 1 纠错码 纠错码的 产生源于1948年 cla u d e s b a n n on的 著名论文 “ a m at h e n l a t i c ai theo ryof co mmumc ation”的发表叨 。而 s h ann o n 提出 的信道编 码定 理正 是为纠错码的发 展奠定 了理 论基础。 众所周知， 在深空通 信中 需要不断地从 卫星上往下传输各种各 样的 科学 数 据和工程数据。 而为了 更加有效地对这些数 据进行传输， 往往会对传输数据的 通信 系统提出以下的五项需求: 1 . 数据传输的 速率最大 化; 2 . 传输数据得到最大的可靠性; 3 . 数据传输所要求的能量最小化; 4数据传输所要求的 带宽 最小化; 5 . 数据传输系统的复 杂性或资源使用最小化。 在努力完成以 上五种需求的同 时， 通 信系 统还需要克服存在于传输 媒介中不同噪 声所带来的影响。而这些噪声一般是以各种各样的气象效应、 千涉现象、 障碍物或者 其他现象等不同形式而存在的.从s hanno n 的噪声信道编码定理可知，为了克服由噪 声所带来的影响同时又满足上述五项需求，只要在传输数据中加入适当的保护冗余， 就可以达到上述所提出的目 标。 这就是说， 采取纠错码保护传输数据的通信系统可以 对上述的五项需求做出满意的折衷. 为什么纠错码能够对在深空中传输的数据起着如 此重要的作 用呢? 其主要原因在于: 从影响 传输数据的角 度来 看， 可以 把 深空传输信 道描述为一条无记忆高斯信道;而该信道正是s h a n n o n 的噪声信道编码定理所描述的 信道。 因 此， 所有依据该信道而 得到的理论结果 和仿真结果都可以对实际的 应用 起到 可靠的指导 作用。 同时， 从资 源使用的角 度来看， 纠错码可以 对影响数 据传输的 不同 因 素加以 折衷， 从而使得 传输数 据可以 在一定 程度上满足人们的要求。 随 着对信息传输的可 靠性和有效性 要求越来越高， 差 错控制技术就在通信中的 作 用显得 越发重要。 而在数字通信系 统中， 利用纠错码进 行差错控制的 方式通常可 分为 三种: 重 传反馈方式(ar q ) 、 前向 纠 错方式(f e c)和混合纠错方式( h e c)101 。 不同 的差 错控制方式有不同的优缺点， 要根据实际情况选择差错控制方式， 在本系统标准中规 定采 用前向 纠错方 式， 因 为卫星系统 存在着较大的 传输延迟， 所以 f e c 技 术比 要求 信 息重 传的 ar q 设 计更为适用. 前向纠 错方式是指发 送端发送能够被纠错的 数据即 经过 编码的 数据， 接收端接收到 这些数据后， 通过纠 错译码器自 动地发现 错误并且自 动纠 正 在传输过程中因 干扰而产生的 错误， 最终实现传输 信息 恢复， 达到可 靠通信的目 的. f e c 技术有 着坚实的理论基 础，经过多年的 发展己 相 对成熟。 香农的 信息理论告 诉我 6 硕士论文r s编译码的fpg a实现 们，当信息发送率小于 信道容量时 ，就存在 某种f e c 编 码， 用以 纠正信道中发生的 某 些错误， 从而提高系统的 可靠 性。 fec 技术总 是力求用最少的冗余来纠正尽可能多 的 错误， 在速率和可靠性 之间 找到一个最佳的 平衡点 。它的主要优点是: 不需要反 馈信 道，适 用于一点发送多点 接收的 广播系统， 译码延时固定 ， 较适合于实时 传输系 统。 但 是这种方式要求预先 确定信道的 差错统计 特性，以 便选 择合适的 纠错码，否则 难于 达到误 码率的要求， 而且误码率的降 低是以 牺牲信息 传输率为 代价的 ( 增加冗余 度)o 3. 2 系统信道编码方案 一 般来说， 信道编码多采 用若干种编码方 法结 合的方法， 以 求最大程度的的 提高 信息 传输的 可靠性。 在本工程中 是 采用rs 编 解码与 卷积编码和vi te rb i 译码级联的 方 法来实 现信道编译码的。 即外码采用r s 编译 码，内 码采用卷积编码与vi t erbi 译 码。 采用以 上编译码方案的可行性 在于， . 在硬件中r s 码中的 码字是以 二进制形式 表 示的，卷积编码只需对送入的二进制数据进行编码即可，而不用去关心 r s码字的长 度。以上编码方案的优点在于rs 码的突出的纠正突发错误的能力可以将信息序列中 的 突发错误纠正， 再通过卷积 编码与vi t e r b i 译码充分利 用信道中的软信息，可以 进 一步提高信息传输的可靠性。 3.3 r s编码原理 本部分主要论述以下三点: rs 码的性质、 rs 码编码算法的介绍以及在编码设计 中 的有限域运算。 为了 在论述的 过程中 更有效的 结合实际编码 器的设 计， 在论文中 所 谈到的r s 码的符号 都被认为是gf(2 鸣中 的元素( 其中m为 整数 ) ， 同时对所论述的 基 本运算方法是结合着硬件设计来阐述的。 3. 3. i r s码理论基础 r s码是纠错码中一类很重要的线性分组码。它是一种多进制 b c h (bos e 一c h a u d h u ri h o c q u e n gh e m)码 ， 也 是 一 种 最 大 距 离 可 分 码 ， 即 在 给 定 每 个 码 字 所 具 有 多 少 冗余量的 情况下， r s 码具有极 大的 最小 距离. 换句话说， r s 码的 最小距离么 信 息长 度k 以 及码字长度n 满足d = n 一 k 十 1 . 除此以 外， rs 码是一种具有纠正多 个错 误的 能力的非二元码。 那么， 对于 突发性的错 误， rs 码可以在使用相 对较少的 符号 数目 下发现连续的比 特错误。 rs 码的另外 一个性质是， 码字所使用的 符号和译码过 程中 所使 用的符号是 一致的， 从而使得在译 码过程中所进 行的 运算就是码符号之间的 运算。 在rs 译码器的 设计 过程中 数学 基础起着相当 重要的 作用， r s 码的 编译码算法111 1 硕士论文rs 编译码的fpg a实现 就是在g ai oi s( 伽罗华) 域的数学概念基 础上发展 起来的. 下面是 r s 码的 一些基本数 学概念: (l ) 由 有限 个 元素 的 集 合 所构 成 的 域 称 为 伽罗 华 域(galoi s) 或 有 限 域， 表示 为 g f ，伽罗华域是指按域的 构成规 则构成的有限个 元素的 集合， 同时要求满足 加 法 和乘 法两种运算的封闭性; (2 ) r s 码属于循环 码，即 码字经 任意 循环移位后 得到的 仍然是属于该g f 域上 的码字元素: (3 ) r s码属于线 形分组码， 码长为n的 码块中 前k 个码符号为信息位， 后面 n 一 k 个码符号为校验位; (4 ) 码的重量分布是完全确定的， 即码字空间中 重量为山的 码字个数是可预知 的: (5 )最 小 距离d=n 一k+1 ， 所 以rs 码 是 最 大 距 离 可 分 码 哪d s 码 ) ， 也 就 是 在 给 定n ， k 后， 纠错能力最强的(n，k) 码; (6 ) 由 。 ，1 两个 元素所组 成的 域称为 二元有限域，记为gf( 2) ; (7)设q阶有限 域 gf (q)中 非零 元素“ 满足 = 吞 ，a ， a ， 。 ，一 ， 的 最小整数n 称为a 的 阶。 n阶 元素a 生成一个n 阶 循环群，即 x 口 一 1 一 1 = 0 q 阶有限 域g f (q ) 中的 任意非 零元素都 满足方程 x ， 一 x =0: (8) 若 在q 阶 有 限 域 gf(a)中 存 在q 一 1 阶 元 素“ 时 ， 称“ 为gf(q) 的 本 原 域 元 素，简称本原元: (9 )若q 阶 有限 域gf( 的 中 存 在 本 原 元a 则gf(q ) 的 全 体 非 零 元 素 构 成 一 个 由a 生 成 的q- 1 阶 循 环 群 gf伪 ) 的 全 体 元素 可明 确 表 示 为 : 二(q ) 二 扣 ，1， a ， * ，a ， ” ; ( 10 )q 阶有限域gf (q ) 中 一定含 有本原元。 如果有限域中 有q 个元素， 则 表示为g f (q ) ， 如果将元素个数按幂次 扩展则表示 为gf(广 ) 并 称 其 为gf(q) 的m 次 扩 域。 r s 纠 错 码 正 是 蒸 于 扩 域gf( 尸) 的 。 为 了 更 好的 理 解 有限 域， 我 们以 扩 域g f (2 3 ) 例 子 来 说 明 。 gf( 2 3 ) 中 共 有8 个 元 素 (或 符 号 ) ， 除。 之 外 ， 其 余7 个 元 素 均 是由 其 本 原 多 项 式p (x ) = 扩+ x +l推 导 出 来 的 . 由 扩十 x + 1 = 0 得 到 扩= x + 1 ， 这 样 就 可 以 推 导出 gf(2 3 ) 的 元 素 如 表3 :3 1 .1 所 示。 例 如 对a 4 = a a = (a+ 1 卜= a ， 十 。 ， 用 二 进 制 串 表 示 该 多 项 式 就 是1 10。 硕士论文r s编译码的fpg a实现 gf ( 2 ， ) 多项式表示 二进制表示 几几几 推导过程 00 00 0 a o a 0 0 0 1 ala i0 1 0 a 2 a 21 0 0 a 3al +10 1 1p 伍 ) 一 a ， + a + 1 a 嘴a z + “ 1 1 0。 ， a = 伍+ 1 ) 。 = a ， + a “ 5a z + a+ 11 1 1a a 一 (a ， + aa=a 3 + a z =a z + a+ 1 a 6a z + 11 01a ， a 一 (a ， + a + 1 ) a 一 a ， + a ， + a 一 a ， 十 1 由 有限域定义 可知， 其定义了 加法和 乘法运算。 对于二元域， 伽罗华 域内的 加法 和乘 法运算就是普 通自 然 数的 加法乘法。 对于g 月 2 勺 ， 加法和乘法就不同于 普通自 然 数的 加法乘法了 . 其加法就是比 特串 逐位进行异 或运算， 得到的结果是二 进制 序列即 多项式表示。比如: a o + a s + a . + a 30= a o + a 30 = 0 0 0 0 0 0 0 1 e 0 l l 0 0 0 0 0 = 0 1 1 0 0 0 0 1 = “ “ 所以 加法就是元素多 项式表示的比 特串的 异或 运算。 如从逻辑电 路实 现上考虑， 就是多 个异或门 并联， 输出 端就是结果， 但没有进 位概念。 而乘法 运算 就是指数相加 的过程， 即指数相加超过2 55就要对结果取模2 55运算。 在此需要说明一下我们把多项 式 表示为“ 0 0 0 0 0 0 00” 元素的指数定 义为负无穷， 所以 在相 乘的操 作数中 如果出 现多 项 式表示为 “ 0 0 0 0 0 0 00” 的元素 那么 结果为 “ 0 0 0 0 0 0 00” ，因为负 无穷和任何常数相 加 仍然是负无穷。 如从 硬件实 现上考 虑， 乘法可以 通过查 表也可以 通过逻辑电 路运算， 具 体方法在下文中 将详述。同时 gf( z m ) 对上述运算 构成封闭性， 任意 gf(2 勺 中的 元素 进行加法运算和乘 法运算所得的结 果都仍是gf(2 勺 中 的一 个元素( 或 符号) 。 标准的 r s 码型， 其 码字 个数” 满 足n = 2 加 一 1 ， 纠错个数t = n 一 m ，而对于截断 的 纠错r s 码来说， 其码长并不固 定，即 可以 任意定义 码字长度，但是 其实际 码长仍 是n = 2 加 一 1 ，只 是其中 若干约定的 码字 位置被 删除， 在对截短r s 码 编码译码时 可在 删除的位置上 任意填上一 个二 进制数字。 简单起见， 使被删掉的位置全部为 0 ，即 可 看作是标准的 r s 码来译 码。 对于其它 b c h 码而言， 截 短码字的 译码很简单， 只需 将 输入或接收到的 截短码字 在其被删除的 位置全填上 。 再送入编码译码 器即 可， 而r s 码 不同 于其他 b c h 码， r s 码截 短码的 编译 码与rs码 标准码的编译 码方 法没有什么区别， 但其编码译 码器的 结构不 仅受到码长的影响， 而且每 种码型的译码能力( 即 纠错个数t) 都将对其产生影响。 硕士论文r s编译码的fpg a实现 3. 3 .2生成多项式 生成多项式 玲 ) 是模砂 一 ， 剩余类代数中 一个理 想的幕次最低的非零首一多 项式 1121， 它 是 理 想 或 循 环 码 的 生 成 元。 因 此 对 于 在gf(2 加 )上的rs 码 来 说 ， 当 要 求 其 纠 错 能 力为t 时 即其最小码距为zt+l，g( x)是以gf( 2 勺 上zt 个相 邻元素为根的多 项式， 即 式( 3 1 ) 所示: ， + 、 一 1 9 (x ) = ( x 一 a 材 x x 一 a “ + ，) (x 一 a “ ， 卜 ，) =艺( x 一 a )( 3 1 ) 其中，m称作偏移量，通常取m= 0或m=1 ，通过表达式可以看出偏移量的选 择会导致生成多项式系数的不同。 如果偏移量满 足式(3，2) 则生成多 项式的 系数就具 有 对称性113 1 ， 系数对称会使rs 编码器中的乘法 器减少一半， 这不 但节省了 逻辑资 源而 且 不会增加译码器的复杂度。 m= 2( 从 一 t ( 其 中m 为 符 号 宽 度， t 为 纠 错 能 力 )(3. 2) 偏移量 m将影响到编码译码器实际结构，而且对于使用特定偏移量进行的r s编 码，在实现其译码时也必须使用该偏移量，否则将得不到正确的输出码字。 3. 3. 3 本原多项式 在有限域中有一个重要的性质就是每个有限域至少包含一个表示为 a的本原元 素， 它能生成域中 所有非 零元素， 即其它 所有非 零元素均可以 用a 表示。 由 本原元 素 a 推导出 其它非零元素的公式就是 本原多项式。 例 如本工程采用 标准为r s ( 1 26， 1 1 2) 其 中 本 原多 项 式 为p( x)= 产+ 犷+ 扩十 x + 1 114 1 。 如 需 产 生 该 本 原 多 项 式 对 应 域 中 所 有元素既可以 使用 前面所 述多 项式依次 推导， 也可以 用图 3 .3.3 . 1 所示的线性反 馈移 位寄存器来得到域中的所有元素. 图3 一3 3 . 1 生 成gf (2 5) 中 元 素的 逻 辑电 路 结 构 电 路的初始 状态设置为x s x 7 x z x ， =00 0 0 0 0 01， 即矿的 二 进制比 特串 表示， 然 后电 路逐次移 位， 每次寄存 器更新后的值即为该 域的下一个元素， 由此可以 依次 得到 al 、 矿 、 矿 ” 、 矿 “ 的 二 进 制 比 特串 表 示 。 另外还可以 根据其自 身的规 律， 用高 级语言 编程来计算出 有限 域中的元素。 如 用 m atlab则可以 非常方便的产生。 通过上 述的 分析， 我们可以 看出 有限 域内 的 元素可用两种形 式表示， 第一种: 有 限 域内 所有非 零元素均可以 用本 原元素的幂次表示: 第二 种: 用多 项式系数对应的 二 进制比 特串 表示。 从硬件实现角 度上来说二进制比 特串 表示更为 适合。 l 0 硕士论文rs 编译码的fpg a实现 3. 4 r s编码硬件实现 对于rs 编码来说， 它存在时 域和频域两种算法 1 习 ， 其中时 域编码只 需要一 次多 项式除法， 频域编 码只需 要一次if ft. 不同 的是， 用时 域编码编出的码字 是系统 码、 可用于截短编 码， 而频域编码编出的码 字是非 系统码， 不能 用于截短编码 16。 因 此， 对于本标准所 采用的r s(12 6 ， 1 1 2) 码， 它属于截短 码， 因 此只能使 用时域编 码的 算 法， 所以下面介绍方法就以时域算法来说明。 对 于 纠 错 能 力 为t 的r s (n ， k) 码 的 每 一 个码 c = (c_ .， _ 2 ， 一 ，cl ， co ) 来 说， 它 都 可以 用c( x)= 一 1了 一， + 一2 扩 一 ， +.二 + cl x + co 多 项 式表 示， 且每 一 个码字 多项 式c( x)都 是 9 (x ) 的 倍式即 c ( x ) mo dg ( x ) 二 0一(3 3 ) 如将 信息m ( x)用多项式表示 m ( x ) = mk-，x 一 + 乓 _ zx k 一 + + 叭 x + 气(3 件 ) 则 对于系 统码的 码字可以 用多项 式(3 . 4) 表示 c (x)= 、 _ ，砂 一 + + 气 x 月 一 + rn _卜 1砂 一 一 + + ro = 从 (x ) x 月一 k + r (x )(3 .5 ) 式 (3 . 5) 码字多 项式的 第n- 1 次至第n 一 k 次的 系数是信息 位， 其余的 是校验位. 将 式( 3. 5 ) 带入式 (3 . 3) 中 可得: m ( x )砂 一 + r (x ) mod g (x ) 二 0(3 石 ) 由 式( 3 . 6) 可以 推导出 : r (x ) 二 m (x )扩 一 k modg ( x)(3 .7 ) 由 式 (3. 刀 可以 看出 : 系 统rs 码 的 编 码 器 就 是 信息 位 多 项 式m ( x) 乘以 工 卜 正 ， 再 用 9 (x ) 求 余 式叹 x)的 电 路 。 对于截短的rs( 1 2 6， 1 1 2)码，由 于附 加的1 29个0 字节 位于m ( x)的高 位， 在 做除 法时可不予考 虑， 就用 1 12 个信息字 节组成信息多 项式作为m ( x)即 可。 因此再 根据 多 项 式 乘 除 法 结 构 叨 可以 很容 易 给出r s ( 1 2 6， 1 1 2) 码 的 编 码 器 结 构图( 如图3 4 . 1 所 不 ) 0 硕士论文rs 编译码的fpg a实现 码输出 mo ， 码， “ ， 伙_ 1 图3. 4 . irs0 2 6， l l 2)编码器结构图 该 电 路的 工 作 过 程 如 下 (其中n “ 1 26， k 二 1 12 ) : 1)开 始编码时n 一 k 级 移位寄 存器的初 始状态均为零， 数据选择器 1 选择经过异 或运算的 数据支路， 数据选 择器 2选择输入 信息字m ( x)的支路。 此时输入端按照 ( 伙 戒 mk 一 2: 、 码 ， mo ) 先 后 次 序 将 信 息 字 送 入 编 码 电 路。 信 息 组 一 方 面 经 数 据选 择 器 2 输出，一 方面送入9 卜 ) 的 除法电 路右端， 这相当 于完成m (x) 乘犷 一 运算; 2)首 先 输 入 的伙 一 信 息 和夙 _ k一 ， ( 由 于 生 成 多 项 式为 首 一多 项式 ， 所以 系 _ 。 等 于 1 ) 相乘得 te mp ， te mp 反 馈到后面 参与有限 域乘 法运算，当下一 个时 刻到 来时各 级移 位 寄 存 器内 容 就 为 原 内 容 加 上te mp馆 沉 1=0，1， ，n 一 k- l): 3)依次 类推， 在经过k 次移 位后， 信息组 全部通过数据选择器输出，它就 是系 统 码 字 的 前k 位 信 息 元 ， 并 且 它 也 全 部 进 入创 卑 ) 的 除 法电 路 ， 完 成 除 法 运 算。 此时 移 位寄存器中内 容就是余式: (x ) 的系 数即 码字的校 验字; 4)此时 把数据 选择器1 送入零值即 关断 编码 器中 所有乘法器， 数据选择器2 将 移位寄存器中的 余式系 数输出 ， 这样再 经过， k 次移 位后， 移 位寄 存器中的 校验元就 跟在信息组的后 面输出， 从而形成一 个完整的 码字。 5)从步骤1 ) 重新开始，即 送入下一组 信息 码字。 3. 4. 1 有限域中乘法运算 由 r s编 码器的结 构框图可知 在编码过程中 涉及到较多的有限域乘法运算 ( 以 本 工 程 标 准rs 码 型 来说 需 要14个 有 限 域 乘 法 器 ) ， 而 乘 法 器 设 计 不 但消 耗 大量 的 逻 辑 资源而且处理延迟时间也 较长， 所以 编码器中的 有限 域乘法结构 得变通以 提高 系统速 度和资源利用率。 一般有限域乘法运 算可 通过查表 法或函 数法实 现。 函数 法用于实现伽罗 华域上任 意 两 个 数 相 乘 ，占 用 资 源 较 多 而 且 其 速 度 较 慢 ， 以 下 详细 介 绍 查 表 法。 即 先查 表 ( 自 然 域 到 有 限 域 的 对 应 表 ) 将 符 号 转 换 成 有 限 域中 的 幕 形 式 ( 指 数 形 式 ) ， 这 时 符号 间 的 乘 硕士论文rs 编译码的即c a实现 法就可以 简化为幂 之间的 加法运算， 加法运算 后的 结果在模2 55 处理后再查 表 有限 域到自 然域的 对应表) 得到符号。这种方法在软 件实现时可以 采用，比 较简洁易懂， 在本工程中使 用该 方法( m at l ab实现) 来验证即 将介绍的用组 合电 路设计的 有限 域 乘法 器的设计正确性。 由图3 . 41 所示编码器的结构可知，所有反馈支路乘法器都是并行处理的，如仍 采用查表法， 要么每一个支路均使用一个固 化表， 要么串 行处理 乘法运算即 每一 个输 入信息需要n 一 k 个时钟周期 才能处 理完毕。 无 疑硬件实现如仍 采用查表 法会大大降 低 整个系统的处理 速度， 所以 硬件实 现一般不采 用查表法.从图3 :41 所示编码器的结 构图 可以 看 出 编 码 器中 所 使 用的 乘 法 器 其中 一 个 操 作 数 都 是 固 定 数 ( 常 值91 ) ， 而 且 由 第一小 节对有限 域中 元素介绍 可知 gf(2 b 中 任一 个元素 。均可用其自 然 基 底 1 、 a、 “ 2 、 a 、 夕 的 线性组合来表示: e = 鸟 a ， + 瓦 a + + 八 a+ bo(3 .8 ) 所以有限域乘法运算就演变成 自 然基底的线性组合相乘。 如以 乙 二 矿 41 ， 本 原 多 项 式p (x)=x， + x ， + x ， 十 x +1为 例 ， 则 。 = 。 、 a 241= 八 a 24s + b6 a 247+. 叶八 a 摊+ bo 矿 41(3 9) 同 样 这 些 操 作 数 均 可 以 用自 然 基 底 线 性 组 合 表 示 ( 通 过3 .3. 3 小 节 的 图3. 3 :3 1 可 以 直 接得出 ) ， 所以 式(3 . 9) 可以 进一 步简化: c = e x a 24 ， = (氏 + 乓 + 拐 ) a ， + (b，+ 久 + 瓦 + 气 + 八 + bo )“ 6 + + ( 瓦 + 久 ) (3 .1 0 ) 即 乘 法的 结 果同 样由 自 然 基 底 线 性 组 合 表 示 . 通 过 式 (3 . 10 ) 可以 发 现 有 限 域 中 常 数 乘 法器可以 通过简单的 组合逻辑电 路实现， 如固 定操作数为“ 241，