（通信与信息系统专业论文）数字通信系统调制解调器的设计.pdf

硕上论文数字通信系统调制解调器的设计 摘要 本文在d s p 平台上实现了某数字通信系统调制解调器的设计 首先 介绍了系 统设计的总体方案 然后 介绍了信道编译码的原理及实现 数字信号在信道传输时 由于噪声 衰落以及人为干扰等 将会引起差错 为了减少差错 采用纠错编码技术 来保证系统信息传输的可靠性 本文中采用了r s 编译码与卷积编码和v i t e r b i 译码级 联的方法来实现信道编译码的 即外码采用r s 编译码 内码采用卷积编码和v i t e r b i 译码 接着 介绍了交织 去交织的原理及实现 纠错编码一般是用来纠正随机错误 的 而实际通信系统中经常会遇到突发干扰 差错是突发性的 即造成多个码元的连 续错误 使突发错误的数目超过了纠错码的纠错能力 为了使纠错码能抵抗这些突发 错误 在实际应用中纠错编码往往要结合数据交织技术 在发送端加上交织器 在接 收端加入去交织器 使信道的突发错误在时间上被扩散开来 把突发差错信道改造成 独立的随机差错信道 从而达到纠错的目的 最后 介绍了定时同步技术 由于信道 传输延时以及收发两地时钟偏差 将使采样无法在最佳时刻进行 这样采集到的数据 与真实数据之间会存在较大误差 为了避免或减少符号间的干扰 接收机时钟必须与 输入信号同步 以便在最佳抽样时刻抽样 使误码率最小化 本文采用了基于g a r n d e r 算法的定时同步技术 关键词 r s 码 卷积码 交织 v i t e r b i 译码 g a m d e r a b s t r a c t硕士论文 a b s t r a c t t h i st h e s i sc o n t a i n st h e d e s i g n o fam o d u l a t o r d e m o d u l a t o ri na d i g i t a l c o m m u n i c a t i o ns y s t e mo nt h ed s pp l a t f o r m f i r s t l y t h eo v e r a l ls y s t e md e s i g ni s i n t r o d u c e d a n ds e c o n d l yt h ep r i n c i p l ea n di m p l e m e n t a t i o no fc h a n n e lc o d i n ga n dd e c o d i n g i sa d d r e s s e d t h e r ew i l lb ee r r o r sf o rd i g i t a ls i g n a lt r a n s m i t t e di nt h ec h a n n e ld u et o t h e r m a ln o i s e f a d i n g i n t e r f e r e n c ef r o mh u m a n b e i n g sa n ds oo n e r r o rc o r r e c t i o n t e c h n o l o g yi se m p l o y e dt od e c r e a s et h ee r r o r st h u se n s u r i n gt h er e l i a b i l i t yo fi n f o r m a t i o n t r a n s m i s s i o n t h ec a s c a d eo fr se n c o d i n ga n dd e c o d i n ga n dc o n v o l u t i o nc o d i n ga n d v i t e r b id e c o d i n gi su s e dt or e a l i z et h ec h a n n e lc o d i n ga n dd e c o d i n gi nt h i st h e s i s t h a ti s t h eo u t e rc o d i n gi sr se n c o d i n ga n dd e c o d i n ga n dt h ei n n e rc o d i n gi sc o n v o l u t i o n e n c o d i n ga n dv i t e r b id e c o d i n g t h i r d l y t h ep r i n c i p l ea n dr e a l i z a t i o no fi n t e r l e a v i n ga n d d e i n t e r l e a v i n gi si n t r o d u c e d e r r o rc o r r e c t i n gc o d ei sc o m m o n l yu s e dt oc o r r e c tr a n d o m e r r o r s h o w e v e r b u r s ti n t e r f e r ei so f t e ne n c o u n t e r e di np r a c t i c a lc o m m u n i c a t i o ns y s t e m t h en u m b e ro fb u r s te r r o r se x c e e d st h ec o r r e c t i o nc a p a b i l i t yo ft h ee r r o rc o r r e c t i n gc o d e b e c a u s eo ft h eu n e x p e c t a t i o no ft h ee r r o r sa sar e s u l to fac o n t i n u o u sm u l t i p l ee r r o r s i n o r d e rt oc o m b a tt h e s eb u r s te r r o r su s i n ge r r o rc o r r e c t i n gc o d e e r r o rc o r r e c t i n gc o d ei s o f t e nu s e dt o g e t h e rw i t l li n t e r l e a v i n gt e c h n o l o g y i n t e r l e a v e ra d d e dt ot h et r a n s m i t t e ra n d d e i n t e r l e a v e ra d d e dt ot h er e c e i v e lt od e s p r e a dt h eb u r s te r r o r so fc h a n n e li nt h et i m e d i m e n s i o n a n dc h a n g et h eb u r s te r r o rc h a n n e li n t oi n d e p e n d e n tr a n d o me r r o rc h a n n e lt h u s a c h i e v et h e g o a lo fc o r r e c t i o ne r r o r s f i n a l l y t i m i n gs y n c h r o n i z a t i o ni s i n t r o d u c e d s a m p l i n gc a nn o tb ea c h i e v e da to p t i m a lt i m ei n s t a n tb e c a u s eo ft h ec h a n n e lp r o p a g a t i o n d e l a ya n dt h ec l o c ks k e wb e t w e e ns e n d i n ga n dr e c e i v i n g s ot h e r ee x i s t sl a r g ed i f f e r e n c e b e t w e e nt h ec o l l e c t e dd a t aa n dr e a ld a t a t h er e c e i v e rc l o c km u s tb es y n c h r o n i z e dw i t ht h e i n p u ts i g n a lt os a m p l ea tt h eo p t i m a ls a m p l i n gt i m et om i n i m i z et h eb i te r r o rr a t ea n dt h e t i m es y n c h r o n i z a t i o nm e t h o du s e di nt h i st h e s i si sb a s e do ng a m d e ra l g o r i t h m k e y w o r d r sc o d e c o n v o l u t i o n a lc o d e i n t e r l e a v i n g v i t e r b id e c o d i n g g a m d e r 声明 本学位论文是我在导师的指导下取得的研究成果 尽我所知 在 本学位论文中 除了加以标注和致谢的部分外 不包含其他人已经发 表或公布过的研究成果 也不包含我为获得任何教育机构的学位或学 历而使用过的材料 与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明 研究生签名 杨盘 堑主2 0 l o 年6 月2 1 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档 可以借阅 或上网公布本学位论文的部分或全部内容 可以向有关部门或机构送 交并授权其保存 借阅或上网公布本学位论文的部分或全部内容 对 于保密论文 按保密的有关规定和程序处理 研究生签名 艴塑塑12 0 l o 年6 月2 1 日 硕士论文数字通信系统调制解调器的设计 1 绪论 1 1 数字通信系统 根据信号方式的不同 通信可分为模拟通信和数字通信 数字通信是指用数字信 号作为载体来传输信息 或者用数字信号对载波进行数字调制后再进行传输的通信方 式 数字通信系统的基本组成部分如图1 1 所示 1 图1 1 数字通信系统的基本组成部分 信源是产生消息的源 消息可以有多种表现形式 如文字 图像 语音等 信源 输出可以是模拟信号 也可以是数字信号 信宿是消息的接收者 信源编码的作用之一是设法减少码元数目和降低码元速率 即通常所说的数据压 缩 码元速率将直接影响传输所占的带宽 而传输带宽又反映了通信的有效性 作用 之二是 当信息源是模拟信号时 信源编码器将其转换成数字信号 以实现模拟信号 的数字化传输 1 数字信号在信道传输时 由于噪声 衰落以及人为干扰等 将会引起差错 为了 减少差错 信道编码器对传输的信息码元按一定的规则加入保护成分即监督码元 并 在译码过程中发现错误或纠正错误 从而提高通信系统的抗干扰能力 实现系统的可 靠通信 3 1 信道编码输出的二进制序列送至数字调制器 它是通信信道的接口 因为在实际 中几乎所有的通信信道都能够传输电信号 所以数字调制的主要目的是将二进制信息 序列映射成信号波形 信道是用来将发送机的信号发送给接收机的物理媒介 目前 无论是模拟通信还是数字通信 在不同的通信业务中都得到了广泛的应用 但是 数字通信的发展速度已经超过模拟通信 成为当今通信发展的主流 与模拟通 信相比 数字通信具有以下优点 4 1 1 绪论 硕上论文 1 抗干扰能力强 且不存在噪声积累 2 传输差错可控 可以改善通信质量 3 便于用现代数字信号处理技术对数字信息进行处理 交换和存储 4 易于集成化和微型化 5 易于加密处理 保密性好 6 可以综合传递各种消息 1 2 信道编码及差错控制 1 9 4 8 年 香农 c e s h n n o n 提出了著名的有噪信道编码定理 1 该定理为提高 数据传输的可靠性指明了一个方向 纠错编码就是后人沿着香农指明的可行方向为寻 求有效而可靠的编码方法发展起来的一门学科 经过了半个多世纪的努力 已有了许 多有效的编译码方法 形成了系统的信道编码理论 也就是纠错编码理论 目前纠错 码可分为以下几个种类 6 1 如图1 2 所示 图1 2 纠错码的分类 在实际通信系统中 信息经过信道传输发生错误 通常要对信息进行纠正 纠正 的过程叫做差错控制 差错控制的方式基本上有两类 一类是接收端检测到传输的码 字有错以后 接收端译码器能自动地纠j 下错误 另一类是接收端检测到码字有错以后 通过反馈信道发送一个应答信号 要求发送端重新发送接收端认为有错的消息 从而 达到纠正错误的目的 在通信系统中 利用信道编码可提高系统传输的可靠性 差错 控制的方式主要有四种 前向纠错 f e c 反馈重传 a r q 信息反馈 i r q 2 硕士论文数j 通信系统调制解调器的设计 混合纠错 h e c n 一1 如图1 3 所示 可以纠错的码 发送端接收端 能够发现错误的码 发送端接收端 一 应答信号 信息信号 发送端接收端 一 信息信号 可以发现和纠正错误的码一 发送端接收端 一 应答信号 图1 3 差错控制的基本方式 a r q i r q h e c 1 前向纠错 f o r w a r de r r o rc o r r e c t i o n f e c 这种方式是信息在发送端先经过纠错编码 然后送入发送信道 接收端收到这些 码字后 由纠错译码器自动纠正传输中出现的差错 所谓前向纠错 是指差错控制过 程是单向的 无需差错信息的反馈 因此 不需要反馈信道 延时小 实时性能好 既适用于点与点之间的通信 又适用于一点对多点的同时通信或广播式通信 2 反馈重传 a u t o m a t i cr e p e a tr e q u e s t a r q 反馈重传方式是发送端发送能够检测错误的码字 接收端收到码字后 由译码器 根据该码的编码规则 判决其中是否有错误产生 并向发送端发送应答信号作为反馈 发送端根据译码器的判决结果 把接收端认为有错的码字重新再发送 直到接收端认 为正确为止 3 信息反馈 i n f o r m a t i o nr e p e a tr e q u e s t i r q 此方式也称回程校验方式 接收端把收到的码字全部由反馈信道送回发送端 发 送端将原码与反馈过来的码字进行比较 如果发现错误 则把出错的码再次重发 直 到接收端没有发现错误为止 4 混合纠错 h y b r i de r r o rc o n t r o l h e c 这种方式是f e c 和h r q 方式的组合 发送端发送同时具有检错和纠错能力的码 字 接收端收到码字后 首先检查差错情况 如果差错在码的纠错能力以内 则自动 进行纠正 如果信道干扰严重 错误很多 超出了码的纠错能力 则接收端通过反馈 信道请求重发 1 绪论硕上论文 1 3 课题研究主要内容 本课题围绕数字通信系统调制解调器的设计方法而展开 对纠错编码原理 定时 同步技术进行理论分析 并给出硬件实现方法 本课题主要完成以下工作 1 阐述本系统设计的总体方案 2 r s 编译码的原理以及在d s p 硬件平台上的实现方案 3 卷积编码原理以及 t e r b i 译码的实现 4 数字通信系统中定时同步技术的实现 1 4 论文组织结构 第二章对系统设计方案进行了介绍 首先介绍了信道编码的实现方案 然后介绍 了接收机模块中采用的定时同步技术 最后介绍了系统实现的硬件平台 第三章对r s 码的编译码原理以及硬件实现方案进行了阐述 重点介绍了r s 译 码原理及其硬件实现方案 最后给出了验证仿真结果 第四章对卷积编码和v i t e r b i 译码原理进行了介绍 首先讨论了卷积编码 译码原 理 然后简单介绍了在d s p 平台上利用维特比协处理器 v c p 实现v i t e r b i 译码 最后给出了卷积码编译码的验证仿真结果 第五章对系统中交织原理进行了阐述 首先讨论了交织 去交织原理 然后在此 基础上介绍了硬件实现方案 最后给出了验证仿真结果 第六章对定时同步技术进行了阐述 首先介绍了g a m d e r 定时同步算法 然后介 绍了硬件实现方案 最后给出了验证仿真结果 4 硕士论文数字通信系统调制解调器的设计 2 系统方案设计 本课题是实现某数字通信系统调制解调器的设计 在信道编码模块中采用前向纠 错 f e c 技术 以此来保证系统信息传输的可靠性 编码方案使用外码与内码级联 的方法 即外码采用r s 码 内码采用卷积码 再加上交织器 保证系统在各种环境 下都能实现业务的可靠传输 由于信道传输延时以及收发两地时钟偏差 将使采样无 法在最佳时刻进行 这样采集到的数据与真实数据之间会存在较大的误差 为了避免 或减少符号间干扰 接收机时钟必须与输入信号同步 以便在最佳抽样时刻抽样 使 误码率最小化1 4 5 1 本课题接收机模块中采用了基于g a m d e r 算法的定时同步技术 整 个系统方案的设计如图2 1 所示 调制部分 2 1 系统信道编码方案 解调部分 图2 1 系统方案设计 2 1 1 分组码 分组码是一组固定长度的码组 用符号 刀 k 来表示 通常它用于前向纠错 分组码的结构如图2 2 所示 信息位校验位 图2 2 分组码 2 系统方案设计硕1 论文 在分组码中 监督位被加到信息位之后 形成新的码 在编码时 k 个信息位被 编为 位码组长度 刀一k 个监督位的作用就是实现检错与纠错 当分组码的信息码元 与监督码元之间的关系为线性关系时 这种分组码就称为线性分组码 常见的分组码 有汉明 h a m m i n g 码 哈达马 h a d a m a r d 码 高莱 g o l a y 码 b c h b o s e c h a u d h u r i h o c q u e n g h e m 码 r s r e e d s o l o m o n 码 本课题中采用的r s 码是一类具有很强纠错能力的多进制b c h 码 它是由r e e d 和s o l o m o n 于1 9 6 0 年构造出来的 r s 码不但可以纠正随机错误 而且可以纠正突发 错误 具有很强的纠错能力 编码效率高 构造简单 易于实现 近年来 随着软件 无线电技术的发展 r s 编译码在通用平台上得以实现 在现代通信系统中广泛应用 2 1 2 卷积码 卷积码 又称连环码 首先由美国麻省理工学院的埃里亚斯 e l i a s 于1 9 5 5 年 提出的 在结构上与分组码完全不同的一种纠错码 分组码的刀一k 个校验元仅与本 组的k 个信息元有关 译码时也仅从本码组的码元中提取译码信息 而与其他码组无 关 卷积码虽然也将信息元分组 但本组的刀一k 个校验元不仅与本组的k 个信息元有 关 而且还与前面连续的m 一1 个信息元有关 卷积码一般可采用 f k m 来表 示 其中豫表示输出码元数 k 表示输入码元数 z 表示约束长度 卷积码既可以用于检错也可以用于纠错 其纠错能力随着约束长度m 的增加 而增大 译码性能不比分组码差 广泛应用于各种数据传输系统 特别是卫星通信 系统 卷积码的译码方法可分为代数译码和概率译码两大类 代数译码方法完全 基于它的代数结构 也就是利用生成矩阵和监督矩阵来译码 在代数译码中最 主要的方法就是大数逻辑译码 概率译码比较常用的有两种 一种叫序列译码 另一种叫维特比 v i t e r b i 译码 虽然代数译码所要求的设备简单 运算量小 但其译码性能要比概率译码方法差许多 因此 目前在数字通信中广泛使用的 是概率译码的方法 2 1 3 级联码 信道编码定理指出 在信息传输速率r 小于信道容量c 的条件下 当码长即jo o 译码错误概率p j 0 因此 为了可靠通信就必须增加码的长度 但是随着码长的 增加 在一个码组中要求纠错的数目相应增加 译码器的计算量和复杂度也相应增加 以致难以在实际通信系统中应用 为了解决纠错性能与设备复杂性的矛盾 福尼 f o m e y 于1 9 6 6 年提出了级联码的概念 把编制长码的过程分几级完成 每一级 中的子码取自不同的域串接而成 以此来减少各级译码器的复杂度 并且具有极强的 纠正突发错误和随机错误的能力 6 硕士论文数 通信系统调制解调器的设计 级联码设备的复杂性主要取决于译码器 可以证明其复杂性并不随码长的增长指 数增加 而是随码长以小的幂次增加 因此从译码复杂度的角度来讲 级联码比一级 码要好得多邸1 通常级联码分两级 其结构图如图2 3 所示 图2 3 级联码结码 鉴于此 本课题采用r s 编译码与卷积编码和v i t e r b i 译码级联的方法来实现信道 编译码的 外码采用r s 编译码 内码采用卷积编码和v i t e r b i 译码 在硬件平台上实 现了 8 7 5 9 的r s 编译码以及 2 1 7 的卷积编码和v i t e r b i 译码 2 2 系统定时同步方案 在数字接收系统中 为了正确恢复出发送端的符号信息 必须做到定时同步 定 时同步方法很多 常见的有插入导频法 锁相环法以及g a r d n e r 定时法 插入导频法是在被传送的信号频谱中额外插入一个位定时导频信号 在接收端使 用窄带滤波器提取该信号获得同步 经过适当的处理形成接收端的相干载波 实现这 种方法的关键在于很好地解决了位同步导频与传送信号之间的相互干扰问题1 1 0 1 为 减小数字信号对位同步的干扰 希望位同步导频处于数字信号的功率谱密度为零的位 置 锁相环法是利用锁相环来获得定时同步的方法 它的基本原理是采用高度稳定的 频率振荡器 在接收端通过鉴相器输出的误差信号去控制位同步输出脉冲序列 即通 过插入或扣除一个或几个脉冲来调整鉴相器输入位同步脉冲序列的相位 从而达到同 步的目的 g a r d n e r 定时算法是e m g a r d n e r 于1 9 8 6 年提出的一种适合高速信号的反馈式算 法 它只需要每符号两个采样点 且载波相位误差不影响算法的定时性能汹棚 盯 鉴于以上优点 该算法在数字通信系统中应用广泛 本课题就是采用的g a r d n e r 定时 算法来实现定时同步的 7 2 系统方案设计硕士论文 2 3 硬件实现平台 2 3 1 硬件平台 盯 在第三代移动通信系统w c d m a 和c d m a 2 0 0 0 中 为了能提供大容量和高质量 的语音 变速率数据 图像等业务 无线空中接口的传输速率在室内环境最高要达到 2 m b i t s 在室外移动环境最高要达到3 8 4 k b i t s 因此需要无线基站提供强大的处理能 力 t i 公司推出了t m s 3 2 0 c 6 4 1 6 数字信号处理芯片 本课题就是在t m s 3 2 0 c 6 4 1 6 数字信号处理芯片上完成的 t m s 3 2 0 c 6 4 1 6 内部包括一个d s p 内核 一级数据c a c h e 一级程序c a c h e 二 级存储器 增强型d m a 控制器 e d m a v t e r b i 译码协处理器 v c p t u r b o 译码协处理器 t c p 对外接口包括e m i f 接口 g p i o 接口 m c b s p 接口 p c i 接口 h p i 接口 u t o p i a 接口 t m s 3 2 0 c 6 4 1 6 内核采用超长指令字 v l i w 体系结构 有8 个功能单元 6 4 个3 2 b i t 通用寄存器 一个时钟周期同时执行8 条指令 运算能力可达到4 8 0 0 m i p s 每秒百万条指令 支持8 1 6 3 2 6 4 b i t 的数据类型 两个乘法累加单元一个时钟周 期可同时执行4 组1 6 1 6 b i t 乘法或8 组8 8 b i t 乘法 每个功能单元在硬件上都增加 了附加功能 增强了指令集的正交性 为使数据能保持对超快速d s p 内核的供给 t m s 3 2 0 c 6 4 1 6 采用了两级超高速缓存器 即1 6 k b y t e 的一级数据c a c h e 1 6 k b e 的 一级程序c a c h e 和1 0 2 4 k b y t e 的数据和程序统一内存 在内存和外设之间所有的数据传输都由e d m a 来处理的 t m s 3 2 0 c 6 4 1 6 的 e d m a 共有6 4 个通道 每个通道的优先级都可编程设置 每个通道都对应一个专用 同步触发事件 使得e d m a 可以被外设来的中断 外部硬件中断 其它e d m a 传输 完成的中断等事件触发 进行数据的搬移 e d m a 完成一个完整的数据搬移后 可 从通道传输参数记录指定的链接地址处重新加载该通道传输参数 e d m a 传输完成 后 e d m a 控制器可以产生一个到d s p 内核的中断 也可以产生一个中断触发另一 个e d m a 通道开始传输 t m s 3 2 0 c 6 4 1 6 的e m i f 提供了到s d r a m s b s r a m 等存储器的无缝连接 同 时e m i f 也可以与外部i o 器件实现无缝连接 如f p g a 其中e m i f a 接口有6 4 b i t 的数据总线 可连接8 1 6 3 2 6 4 b i t 的器件 e m i f b 接口有1 6 b i t 的数据总线 可连接 8 1 6 b i t 的器件 2 3 2 设计和验证平台 本课题从前期的设计 调试到后期的验证都是c c s c o d ec o m p o s e rs t u d i o 和 m a t l a b m a t r i xl a b o r a t o r y 平台下完成的 8 硕上论文数字通信系统调制解调器的设计 c c s 提供了基本的代码生成工具 它具有一系列的调试 分析能力 c c s 支持 如图2 4 所示的开发周期的所有阶段 图2 4c c s 开发周期 c c s 提供了配置 建立 调试 跟踪和分析程序的工具 它便于实时 嵌入式 信号处理程序的编制和测试 它能够加速开发进程 提高工作效率 m a t l a b 提供了大量的数字信号处理函数 d s p 处理的结果可以保存为一个t x t 文 件或b i n 文件 然后导入到m a t l a b 中 与m a t l a b 提供的函数处理的结果进行比较 验证设计的正确性 2 4 小结 本章首先介绍了信道编码的实现方案 然后介绍了接收机模块中采用的定时同步 技术 最后介绍了系统实现的硬件平台 9 3r s 码的编译原理及实现 硕上论文 3r s 码的编译原理及实现 r s r e e d s o l o m o n 码是纠错码中一类重要的线性分组循环码 它同时也是一 种多进制b c h b o s e c h a u d h u r i h o c q u e n g h e m 码 r s 码具有很强的纠错能力 不 但可以纠j 下随机错误 而且可以纠正突发错误 与同类纠错码相比 在同样的编码冗 余量下 它具有最强的纠错能力 而且编码效率高 构造简单 易于实现 近年来 随着软件无线电技术的发展 广泛应用于现代通信系统领域 3 1r s 码理论基础 3 1 1 伽罗华域 g a l o i sf i e l d 域在r s 编译码理论中起着至关重要的作用 r s 码的编译码算法是在伽罗华 g a l o i s 域的数学概念基础上发展起来的 因此有必要先阐述一下伽罗华域的基本 概念 由有限个元素的集合所构成的域称为伽罗华域 g a l o i sf i e l d 或有限域 表示为 g f 它要求满足加法和乘法两种运算的封闭性 加法封闭性 如果a b f 必有a 6 f 乘法封闭性 如果a b f 必有a b f 由0 1 两个元素所组成的域称为二元有限域 记为g f 2 如果有限域中有g 个元素 则表示为g f q 若g 是素数 g f q 可由元素 o 1 g 一1 构成 在域g f q 中的加法 乘法运算定义为模q 运算 写作 m o dq 从而满足加法 运算封闭性和乘法运算封闭性的要求 下面举两个例子来加以说明 g f 2 是由元素 0 l 构成的集合 其加法和乘法的运算如图3 1 所示 不o 1 0 o1 00l ll0 0 l 0 0 0 l01 图3 1g f 2 域运算 g f 5 是由元素 0 1 2 3 4 构成的集合 其加法和乘法的运算如图3 2 所 硕士论文数字通信系统调制解调器的设计 o123 4 0o1234 1l234o 22 3 4o1 3340l2 44o123 木 0 l23 4 o000oo 1o1234 2024 13 3031 4 2 404321 图3 2g f 5 1 域运算 如果将g f q 的元素按幂次扩展则可以表示为g f q 册 并称其为g f q 的m 次扩 域 r s 纠错码中的运算正是在扩域g f 2 上进行的 域g f 2 中2 肘个元素由 0 o r o 仅1 0 l 2 2 构成 并且具有以下性质 域中每个 元素都可以用0 o 仅l 0 t 2 0 1 的和来表示 其中仅为本原多项式p x 的根 为了更好的理解有限域 我们以扩域g f 2 4 为例来说明 g f 2 4 中共有1 6 个元 素 除o 之外 其余1 5 个元素均可以由其本原多项式p z x 4 x 1 推导出来 因 为o 是本原多项式p x 的根 得到仅4 0 c 1 0 或仅4 一q 一1 0 模2 运算中加法和 减法是一样的 从而得到0 4 0 t 1 由此可以得到g f 2 4 中所有元素 如表3 1 所 示 由有限域的定义可知 域中的加法和乘法运算与普通自然数中的加法和乘法运算 不同 对于二元域 伽罗华域内的加法运算就是异或运算 乘法运算就是普通自然数 的乘法运算 对于g f 2 其加法运算是域中元素对应的二进制数按位异或 例如 加法 仅 0 t m 0 0 1 0 0 1 11 0 1 0 1 0 8 减法 a 一0 加 0 0 1 0 0 11 l 0 1 0 1 0 1 8 乘法运算就是指数相加的过程 从表3 1 可知0 0 o l 即当域中元素的指数 超过2 一1 时 指数要模2 埘一1 例如 乘法 仅 珀 0 t 8 1 0 m o d 0 1 3 除法 仅8 o r l o 0 2 0 2 1 5 仅 倒数 1 仅8 仅ol o t 8 s a 8 1 5 0 7 3r s 码的编译原理及实现 硕士论文 表3 1g f 2 4 1 域元素 元素多项式表示二进制对应值十进制对应值 0 00 0 0 00 a o10 0 0 1l 仪l仅l0 0 1 02 仅20 1 0 0 4 仪一 仅3 戗31 0 0 08 仅4仅 10 0 1 13 仅5仅 1 仅2 仅o l l 06 仅6仅 仅2 0 仪3 0 c 21 1 0 0 1 2 o 7仅叙3 仅2 a 3 o r 1 1 0 1 11 l 仅8 0 l3 0 1 仅2 10 1 0 15 仅9仅 仅2 1 仅3 a1 0 1 01 0 仅1 0 仅3 q a2 仅 10 1 1 l7 仪l la 2 0 1 仅3 仅2 仅 1 1 1 01 4 a 1 2仅缸3 0 2 a 仅3 a2 a 11 1 1 11 5 仅1 3仅 仅3 a 2 仅 1 o r 3 a2 1 1 1 0 11 3 仅1 4仅 仅3 仅2 1 q 3 11 0 0 19 0 1 5o l o l3 1 1 1 0 0 0 1 1 3 1 2 本元多项式 若有限域g f q 中存在q 一1 阶元素仅 称0 为g f q 的本原元素 简称本原元 利用本原元素能生成域中所有的非零元素 即其它非零元素均可以用 的多项式来表 示 由本原元素a 推导出其它非零元素的公式就是本原多项式 表3 1 采用g f 2 4 中 的一个本原多项式p x x 4 x l 推出了域中所有元素 如需要的产生该本原多项式 对应域中的所有元素 既可以使用前面所述多项式依次推导的方法 也可以用图3 3 所示的线性反馈移位寄存器来得到域中的所有元素 1 2 图3 3 生成g f 5 中元素的逻辑电路结构 硕士论文 数字通信系统调制解调器的设计 电路的初始状态设置为z 4 z3 2 2 x 1 0 0 0 1 即o o 的二迸制表示 然后电路逐次 移位 每次移位仅的次数加一 寄存器更新后的数值即为该域的下一个元素 由此可 以依次得到o 1 仅2 o a 1 4 的二进制表示 在实际应用中 只需根据需要查出相应的本原多项式即可 表3 2 给出了m 1 6 时 对应不同m 本原多项式的个数 表3 3 给出了m 确定时一个本原多项式的八进制表 示 表3 2m 1 6 时所有本原多项式的个数 历个数m个数 2194 8 3 21 06 0 4 2 1 l 1 7 6 561 21 4 4 661 36 3 0 7 1 81 47 6 0 81 61 51 8 0 0 表3 3m r t g e c t p o l y 2 5 5 2 2 7 柚o g f 2 8 t o d a y p r l t i t i r ep o l y n 啪且 d 啪 4 d m 2 l 2 8 5d e c u 毫1 r r e z m u r a t s2 c o l t b a 1t h r 口t l 咖1 7 12 2 93 62 2 42 0 81 2 24 41 2 41 6 51 4 72 88 31 1 5t 32 1 21 3 11 5 5 c o l u b m s1 8t h r o u 曲2 9 1 4 81 1 l5 81 0 41 6 t1 5 52 3 58 哇2 0 51 6 13 了1 7 0 图3 i im a t l a b 产生生成多项式 最后根据r s 编码原理结合图3 1 0 完成编码 编码程序的流程图如图3 1 2 所示 1 9 3r s 码的编译原理及实现硕士论文 2 0 图3 1 2r s 编码流程图 硕士论文数字通信系统调制解调器的设计 编码的主程序如下 v o i dr s e n c o d e 0 i 1 1 ti j c o d e f o r i 0 i 8 7 i c i o f o r i 0 i 5 9 i c 嘲 m i f o r i 0 i 5 9 i c o d e c i f o r j o j 2 9 j t j g m p y 4 c o d e 鲥 域乘法 c i j t j c 州 域加法 f o r i 0 i 5 9 i c i m i 3 4r s 编码结果验证 根据图3 1 2 在d s p 中实现r s 8 7 5 9 编码 c c s 软件中m e m o r y 窗口可以 观察中间变量值 图3 1 3 给出了待编码的5 9 个信息值 保存在变量数组m 中 图 3 1 4 给出了r s 编码结果 保存在变量数组c 中 从两张图中可以看出检验信息为2 3 4 3 1 1 3 8 7 7 8 1 8 6 1 8 8 6 0 8 3 1 2 6 7 5 1 2 0 1 4 1 1 3 9 2 0 8 5 9 2 1 0 1 5 8 1 6 1 1 4 3 2 2 6 2 2 3 8 2 1 3 2 2 5 2 0 6 1 0 7 1 7 2 2 l 3r s 码的编译原理及实现 硕士论文 c 2 4 3 2 1 0 2 3 9 3 5 1 1 3 2 1 4 7 7 9 6 1 8 6 1 3 9 2 2 3 5 9 1 1 3 2 3 4 5 1 2 3 8 5 4 b 2 2 0 1 8 b 2 0 8 8 2 1 5 5 1 5 7 1 0 5 5 0 1 1 9 1 7 4 4 9 2 1 8 6 0 5 9 i 3 1 2 4 2 0 2 2 2 b 1 5 4 1 0 7 9 7 1 7 4 2 3 4 8 3 2 1 0 2 2 5 z 2 8 2 3 5 1 4 6 9 2 1 6 2 1 2 7 7 3 1 2 6 1 5 8 2 0 6 图3 1 4r s 编码结果 1 9 5 1 8 8 9 0 5 0 1 3 4 1 2 8 1 3 8 1 1 3 7 5 1 6 1 1 0 7 1 1 6 4 5 2 0 b 3 s l 1 8 l 3 8 8 7 1 2 0 1 4 3 i 7 2 4 1 0 3 2 1 9 1 1 7 2 l d 9 i 7 8 7 8 1 4 1 2 2 6 0 m a t l a b 内部提供了r s 编码函数 我们可以借助m a t l a b 来验证上述编码结果的 正确性 m a t l a b 的验证程序如下所示 其输出结果与图3 1 4 显示的结果一样 m r a i l d i n t 1 5 9 o 2 5 5 0 r s m 2 8 r s n 2 8 7 r s k 5 9 m s g g f m r s m c r s e n c m s g r s n r s k 3 5r s 译码原理 3 5 1r s 译码基本理论 1 由于本工程中生成多项式中的偏移量m 1 根据式3 1 生成多项式g 可以表 示成 g x x 一仪1 x 一0 2 x 一仅2 系统码c z 是生成多项式g x 的倍式 即c x q x g x 那么 c x q x g x g x x 一仅1 x 一0 2 x 一0 2 3 1 7 3 1 8 所以c 石 必以仅1 仅2 0 2 7 为根 若码字c z 巳一1 一1 巳一2 x 脚 q x c o 则 c a 巳一l 做 一1 c 一2 一2 c l c o i 1 2 2 t 由此可得r s 码的校验矩阵 3 1 9 硕十论文数字通信系统调制解调器的设计 h 仅 一1o a1 2 川 2 a 2 i 2 一 2 7 2 仅2 1 3 2 0 发送码字c c n 1 c 州 q c o 结合式3 1 9 可知 c h 7 0 或们7 0 3 2 1 满足校验矩阵的定义 设c x 为发送码字 r x 为接收码字 则r x 可以表示为 r x c e x 3 2 2 其中e x 为错误图样 表示为 e x e l x 1 一2 x 2 q x e o 3 2 3 若信道产生f 个错误 则 e x r x r l x 一1 x x r x 3 2 4 t l 式中 r g f q x 称为错误位置 说明在接受码字r x 中在位置 的地方发生了 错误 错误值为z 由伴随式的定义可知 s 7 h r r a 0 1 2 2 伐2 1 缸2 q 2 1 一l 一2 i 将式3 2 1 代入上式可得 s r h r 7 日 c e 7 h c r 砸丁 h e 7 1 仪 一l 2 1 缸2 川 0 l1 0 21 0 2 71 墨 r s 2 r a 2 1 s 2 r 2 3 2 5 l 弘 刀 矿誊 o 之 幢 广 厂 妒岭 心 3r s 码的编译原理及实现硕七论文 r 0 z l a 一 i 仅 r a 2 z l 仅2 x a 2 r 仅2 r l 仅2 k 旺2 7 岛 r 0 t e 是 r a2 e 2 r a2 e 0 l 2 式中 r 哕 j 1 2 2 t i 1 若令 打 x 即a 则上式可写成 一 纠 j l 2 2 t i l 或 3 2 6 3 2 7 3 2 8 而 x 薯 y 2 x 2 r 一 k 七 l 是2 i 砰 艺 r 2 善k 3 2 9 s 2 k x 7 k x r 匕 7 k l 我们的目的是要由式3 2 9 中的2 个方程求出2 个未知数 r f l 2 t 要直 接解上述方程比较困难 所以分两步进行 先求解出错误位置薯 再求出错误值r 为此引入错误位置多项式 o x 1 x x 1 x 2 x 1 一薯z 3 3 0 若第k 个错误位置为x 1 则6 巧1 0 因此 求错误位置首先求解错误位置多 项式o x 的根 根的倒数就是错误位置 把o x 展开 o x 1 x x 1 x 2 x 1 一五x 兀 1 x x i l 1 一 五 而 薯 x 一恐 x l x 3 薯一1 薯 x 2 一1 x l x 2 x x 3 3 1 2 4 硕士论文数字通信系统调制解调器的设计 令 则式3 3 1 可写成 若巧1 为错误位置 两边乘以 t 则 o l 五 薯 a 2 五 五恐 一l i o 一1 而恐 x x o x 1 0 1 x a 2 x 2 o f 一 兀 1 x x 3 3 2 l 则 6 巧1 l c y l 巧1 6 2 巧2 o 巧 0 o l 1 6 2 尊2 or 0 k 1 2 f 上式两边在乘以k 1 2 t 则 k 州 6 1 k 州一 c y 2 k 卅 2 c y k o k 1 2 f 对k 求和 得 k 矿 6 k 卅1 o k 州 2 c r k o k 1 2 f k lk lk lk l 由式3 2 8 的定义可知 e 式成为 s j f o l 一1 o r r s j 0 1 2 把上式展开 则 l 0 1 薯 a 2 一l 仃r s l 0 2 c y l i 1 a 2 o s 22 0 s 2 6 1 s 2 l 0 2 s 2 卜2 or s t 0 或 墨 s t i s 2 r i i s s 2 一2 g l y 2 o s t i s t 2 s 2 f 3 3 3 3 3 4 3 3 5 或 m 6 一 s 式3 3 4 是一组线性方程 有f 个方程 个未知数 该方程组有解的充要条件是式3 3 5 中的矩阵m 满秩 可以证明如果s j j 1 2 t 是由 个不同的非零对 r 组成 则矩阵m 满秩 2 5 五 墨 3r s 码的编译原理及实现 硕士论文 将式3 2 9 中的 代入m m 五恐 1 而i 1 x t 1 k 七 l x 五 k x 2 z 薯 1 五 1 j c 2 1 爿 1 l m 溉弘 7 式中 x 和 x 是范德蒙矩阵 只要每个元素不为 且不同 则它们的行列式不为o 而 投 为对角阵 只要i t 不为o 行列式不为o 若发生r 个错误 则有 个不同且不 为o 的t 和r 因而矩阵m 满秩 求得了o x 解出它的根得到错误位置j c l x 2 薯以后 把它们的值代入式3 2 9 得 而x 2 石 k k r 毛 s 2 s t 3 3 6 或 y i s 上式的 x 的矩阵是范德蒙矩阵 只