（微电子学与固体电子学专业论文）基于epon系统的信道编译码技术研究与硬件实现.pdf

l 海大学硕j j 学化论文 摘要 在网络通信中潜在着不稳定的物理层，为了把不稳定的物理层转换为稳定 的连接，e p o n ( e t h e m e tp a s s i v eo p t i c a ln e t w o r k ) 依赖于链路和数据特性在发送 帧中加入足够的冗余信息，从而在接收端能够检测出错误并安排受损帧的重发， 这些工作都是由信道编码技术来完成的。c r c ( c y c l er e d u n d a n c yc h e c k l 码因其 强大的榆错能力在e p o n 系统数据链路层m a c ( m e d i a a c c e s sc o n t r 0 1 ) 部分的实 现中得到应用。 本文首先介绍了信道编码技术的基本理论和差错控制的基本方式，然后重 点分析了8 0 2 3 协议中c r c 码技术的要求，根据协议对c r c 码算法和硬件实现 进行了研究，提出了改进的并行c r c 算法，接着运用f p g a ( 现场可编程门阵列) 技术通过q u a r t u si i 、s o p cb u i l d e r 和n i o si is d k 等软件工具完成了n i o si i 用 户自定义指令的实现，不仅进行了功能仿真，而且实现了开发板上的验证，为 e p o n 系统平台的验证建立了基础，最后根据e p o n 帧校验的具体要求，在0 3 5 um 工艺下通过c a d e n c e 和s y n o p s y s 工具并基于流水线技术对c r c 编译码器进 行了重新设计及a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 实现，该 硬件电路与用通用算法实现的结果相比，控制单元更简单，数据处理速度更快。 我们设计的编译码器芯片面积为2 5 6 m m 2 ，数据吞吐量为1 2 5 m b i t s 。 本论文主要创新点： 通过对u n f o d i n g 算法以及基于矩阵的流水线法等算法的分析，提出了改 进的适合于高速光网络的并行c r c 码算法；通过n i o si i 自定义指令完成c r c 码 编码器，将一个复杂的标准指令序列简化为一个用硬件实现的单一指令，简化 了系统软件设计并加快了系统运行速度。 关键词：差错控制流水线c r c 码n i o si i a s i c v l 海大学坝| 学位论文 a b s t r a c t t h e r ei sf a l l i b i l i t yp h y s i c a li nn e t w o r kc o m m u n i c a t i o n i no r d e rt om a k et h e p o t e n t i a li n s e c u r ep h y s i c a ls t e a d y , e p o n ( e t h e m e tp a s s i v eo p t i c a ln e t w o r k ) a d dt h e r e d n n d a n c yi n f o r m a t i o ni nt r a n s m i tf r a m ea c c o r d i n gt o t h ed a t al i n ka n dd a t a c h a r a c t e r i s t i c s ow ec a l lc h e c kt h ee r r o ra n dr e q u i r ef o rs e n d i n gt h ef l a m ea g a i na t t h er e c e i v i n ge n d t h e s ep r o b l e mc a nb es o l v e db yt h ec h a n n e lc o d et e c h n o l o g y w e o f t e nc h o o s ec r c ( c y c l er e d u n d a n c yc h e c k ) t or e a l i z eb e c a u s eo fi t ss t r o n gc h e c k i n g a b i l i t y , f i r s t l y , t h i sp a p e ri n t r o d u c et h eb a s i ct h e o r yo ft h ec h a n n e lc o d ea n dt h eb a s i c m o d eo ft h ee r r o rc o n t r 0 1 s e c o n d l y , w em a i n l ya n a l y z et h er e q u i r e m e n tf o rt h ec r c i n8 0 2 ，3 a h a c c o r d i n gt ot h ep r o t o c o lw eg i v et h ei m p r o v e dp a r a l l e lc r ca l g o r i t h m a f t e rd i s c u s s i n gt h ec r cc o d i n gf u n d m e n t a l sa n dh a r d w a r ed e s i g n t h i r d l y , b yu s i n g f p g at e c h n o l o g yw ed e s i g nt h ec r cc o d ec u s t o mi n s t r u c t i o no f n i o si ic p ub yt h e e d at o o l ss u c ha sq u a r t u si i s o p cb u i l d e ra n dn i o si is d k t h e r ei st h ef u n c t i o n s i m u l a t o ra n de m l u a t o ri nd e v e l o p m e n tb o a r d ，w h i c hb u i l dt h eb a s eo ft h ee m u l a t i o n p l a t f o r mo fe p o n f i n a l l y , a c c o r d i n gt ot h er e q u i r e m e n to fe p o nf r a m ec h e c k ，w e c o m p l e t ea s i c ( a p p l i c a t i o ns p e c i f i ci n t e r g r a t e dc i r c u i t ) d e s i g no f c r cc o d e ru s i n g 0 3 5 p mc m o st e c h n o l o g yb yt h ee d a t o o l so fc a d e n c ea n ds y n o p s y s t h ec o d e r s c o n t r o lu n i ti sm o r es i m p l ea n di t sp r o c e s s i n gs p e e di sm o r er a p i dc o m p a r e dw i t h t h a tr e a l i z e db yt h ec o m m o na l g o r i t h m t h ea r e ao ft h ec o d e ri s2 5 6 r a m 2a n d p r o c e s s i n gt h r o u g h p u ti s1 2 5 m b i v s t h em a i nc r e a t i v ep o i n t so f t h i sp a p e ra r ea sf o l l o w ： a f t e ra n a l y z i n gt h eu n f o l d i n ga l g o r i t h ma n dt h em a t r i xp i p e l i n i n ga l g o r i t h mw e o b t a i nt h ei m p r o v e da n dp a r a l l e lc r c a l g o r i t h m ；w ed e s i g nt h ec r c c o d e rb yt h e n i o si ic u s t o mi n s t r u c t i o n ，w h i c hc a l lr e d u c et h ec o m p l e x i t yo f t h en o r m a li n s t r u c t i o n s e q u e n c et os i n g l ei n s t r u c t i o ni nh a r d w a r e ，s ow e c a ns i m p l i f yt h es o f t w a r ed e s i g ni n j 二海大学硕 一学位论文 s y s t e ma n dm a k et h es y s t e mm o r er a p i d k e y w o r d s ：e r r o r - c o n t r o lp i p e l i n i n g c r cn i o si ia s i c 海大学硕i ：学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：强童控日期：丝! ： 2 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：建壁垒! 导师签名： 2 ) ，每一个波形用来传输2 ”个可能的比特序列中的某一 个序列，这种调制方式称为m 元调制。 信道：信号传输的通道，是发送端到接收端之问信号传输所经过的物理媒 介。信道可以分为有线信道( 比如双绞线、同轴电缆、光缆等) 和无线信道( 比如 长波、短波、微波、红外线等1 。在信号传输的过程中不可避免地会引入干扰和 噪声( 比如热噪声、脉冲干扰与衰落等) 。不同的信道具有不同的特性，而信道 的固有特性和所引入干扰的特性会直接天系到发送端中变换方式的选取。 接收端：数字解调器对受到信道恶化影响的发送波形进行处理，并将该波 形还原成一个数字序列，此序列表示对发送数据符号的估计值( 二进制或m 元) 。 这个数字序列被送至信道译码器，信道译码器根据信道编码器所采用的编码方 法的有关知识以及接收数掘所含的冗余信息重构原始序列。当需要模拟输出的 时候，信源译码器接收到信道译码器的输出序列后，根据所采用的信源编码方 法的有关知识还原出由信源所发出的原始信号。信宿，信息的接收者，即为信 息最后到达的目的地。 由此可见，通信的基本任务是传送信息。通信系统中最重要的指标就是信 息传输的有效性和可靠性，而这两者往往是一对矛盾。如何合理地解决有效性 与可靠性这对矛盾，是正确设计一个通信系统的关键问题之一。通信系统本身 ( 包括纠错码) 就是在解决这对矛盾的过程中不断地发展起来的。下面介绍一些 衡量有效性与可靠性的主要技术参数： 1 、传输速率 ( 1 ) 码元传输速率波特率调制速率：每秒钟通过信道传输的码元数。单位 是波特。 ( 2 ) 比特率i l k 特传输速率：每秒钟通过信道传输的信息量。币化是比特秒。 2 、差错率 1 ) 定义 差错率是衡量传输质量的重要指标之一，它有以下几种不同的定义： 码元差错率：指在传输的码元总数中发生差错的码元数所占的比例( 平 均值) ，简称误码率。 上海大学硕士学位论文 比特差错率l l 特误码率：指在传输的比特总数中发生差错的比特数所 占的比例( 平均值) 。在二进制传输系统中，码元差错率就是比特差错率。 码组差错率：指在传输的码组总数中发生差错的码组数所占的比例( 平 均值) 。 2 ) 降低差错率的方法 在传输过程中产生不同差错的主要原因有：不同的传输系统有不同的性能： 在传输过程中干扰不同；不同的用户或不同的传输系统对差错率的要求不同。 有两种途径降低差错率以满足系统要求： 降低信道( 调制解调器i # 输媒介) 本身引起的误码率； 采用信道编码，在数字通信系统中增加差错控制设备。 本文正是从这一角度来设计c r c 码以降低差错率，从而提高通信系统的町 靠性的。 1 3f p g a 技术及n i o si i 用户自定义指令 f p g a 是一种用户可编程逻辑器件，具有高度灵活的用户现场可编程方式， 现场定义高容量电子数字系统的能力，可重复定义和反复改写。由于f p g a 设计 实现的产品具有集成度高、体积小、功耗低、可靠性高和开发周期短等特点， 因此，随着f p g a 器件在我国的逐步推广，其应用范围越来越广泛。 2 0 0 4 年，a 1 t e a 公司推出了n i o si i 处理器。n i o sl i 为3 2 位r i s c 嵌入式 处理器，具有i d e ( 集成开发环境) 和g u i ( 图形用户界面) 。它支持m i c r o c o s 儿、 灿c l i n u x 等多种实时操作系统，支持轻量级t c p i p 协议栈，支持 z i p 的文件 系统，具有超过2 0 0d m i p 的性能，而在f p g a 巾实现的成本最低只有3 5 美分。 n i o s l i 处理器采用软核，开发人员无需考虑系统层设计中的a s l c 可：蘸接挑选 系统配置实现性能及成本要求。更值得一提的是，n i o si i 处理器允许自定义 硬件加速单元和用户增加自定义指令。 使用n i o si i 的用户自定义指令，可以将一个复杂的标准指令序列简化为 一个用硬件实现的单一指令，从而简化系统软件设计并加快系统运行速度。n i o s i i 的用户自定义指令是与c p u 的数据通路中的a l u 相连的用户逻辑块。其基本 操作是，接收从d a t a a 或d a t a b 端口输入的数据，经过自定义指令逻辑的处理， 海，l ：= 学顿卜学位论文 将结果输出到r e s u l t 端口。在信道编码中，有时编码的处理数据运算量比较大， 循环数目多；而n i o si i 的定制指令个数己增加到2 5 6 个，可以使用用户自定 义指令完成许多循环内的数据处理，从而加速数据处理的速度。 本文正是考虑到f p g a 技术的灵活性，所以在f p g a 上对c r c 码编码器进 行验证，同时进行了n i o si i 用户自定义指令的尝试。 1 4 论文的主要工作 o a m 帧 o a m 帧 幽1 2e p o n 系统框图 图1 2 为e p o n 系统中主要模块框图。在e p o n 中，有r s ( r e c o n c i l i a t i o ns u b l a y e r ) 子层 d f e c ( f o r w a r de r r o rc o r r e c t i o n ) 子层需要使用信道编译码技术，因为f e c 子层的位置处在p c s ( p h y s i c a lc o d i n gs u b l a y e r ) 子层和p m a ( p h y s i c a lm e d i a a t t a c h m e n t ) 子层之间，是e p o n 物理层中的可选部分，所以本文主要是讨论r s 层 中l l i d ( l o g i c a ll i n ki d e n t i f i e ) 过滤和添加及f c s ( f r a m ec h e c ks e q u e n c e ) 帧校验模 块所用的c r c 编译码器的设计及其硬件a s i c 实现。 在设计可应用于e p o n 系统的c r c 码编译码器时，是采用了自顶向下口 的设 计方法，基于数字系统的不同层次来设计的。首先根据系统的需求分析，以信 道编码理论为基础，通过对多种编码算法的比较分析，确定了所采用的算法为 一种新改进的算法，并在系统级上通过仿真验证了c r c 码能够满足e p o n 的误码 性能要求。接着用v e r il o g 语言将整体算法进行了行为级和r t l 级描述，并在 f p g a 上验证了所采用的编码算法的正确性，从而为后面的a s i c 设计奠定了基 海人学f mi 。学位论文 础。另外，在配合e p o k 系统验证的同时，还基于n i o sit 进行了用户自定义指 令的实现。最后在r t l 级上对c r c 码编译码器完成逻辑综合和布局布线，并且 通过了静态时序分析和版图验证。 1 5 论文的创新点 本文的创新点主要有以下几点： 1 通过对u n f o l d i n g 算法以及基于矩阵的流水线法等算法的比较分析，提 出了一种简单且易实现的新改进的c r c 码编译码算法； 2 采用流水线技术，设计了一种可应用于e p o n 系统的并行度较高的c r c 码编译码器； 3 通过n i o si i 自定义指令设计了c r c 码编码器，这样在充分利用n i o s1 1 软核灵活性的同时，将一个复杂的标准指令序列简化为一个用硬件实现的单一 指令，从而简化系统软件设计并加快系统运行速度； 4 完成了c r c 码编码器的a s i c 实现，其硬件电路与用通用算法实现的 结果相比，控制单元更简单，数据处理速度更快。 1 6 论文的内容 本文分为六章： 第一章为绪论，概要介绍论文的背景、主要工作、创新点及内容安排。 第二章阐述了信道编码的基本理论，并对差错控制编码，汉明码距与编码 纠错能力做了分析，这是开展本文研究工作的基础。 第三章介绍了c r c 码的原理和特点，给出c r c 码的常用计算方法，并对几 种编译码算法实现方式进行比较分析，提出了改进的c r c 码并行算法。 第四章介绍了n i o si i 处理器的基本特征及内部结构和用户自定义的原理， 详细描述了c r c 码编码器在用户自定义指令中的创新设汁，最后基于n i o si i 对编码器进行了验证，并给出了仿真结果。 第五章介绍c r c 码编译码器芯片实现的设计流程，包括编译码器芯片的功 能仿真、逻辑综合、布局布线、静态时序分析及相关验证。 第六章对本文的研究工作作了一个简要的总结并对未来的工作进行了展 望。 海人学顺 。学位论义 第二章信道编码理论 本章的j i 要内容是介绍信道编码的基本理论4 】 9 】【10 1 ，它为后面章节要介绍 的c r c 码编译码器的设计及应用提供了理论基础。 2 1 信道编码定理 2 1 1 信道容量的定义 香农定义信道容量为： c = m a x ，( x ，y )( 2 1 1 ) p 0j 其中变量x 和y 分别代表信道的输入和输出，i ( x ，y ) 为x ，y 的互信息量， p ( x ) 是变量x 的概率密度函数( p d f ，p r o b a b a l i t yd e n s i t yf u n c t i o n ) 。i ( x ，y ) 的最 大值取决于信源x 的概率分布。信道容量c 的单位是信道上每传送一个符号( 每 使用一次信道1 所能携带的比特数，即比特符号。如果每符号传送周期是t 秒， 也可用“秒”为单位来计算信道容量，此时c s = c t ，以比特每秒( b i t s ) 为信 道容量单位。 2 1 2 信道编码的分类 纠错码的分类有很多种，主要有以下几类： 1 ) 按照对信息元处理方法的不同，分为分组码和卷积码两大类。 分组码是把信源输出的信息序列，以k 个码元划分为一段，通过编码器把 这k 个信息元按一定规则产生r 个校验元，输出长为n = k + r 的一个码组。因此 每一码组的校验元仅与本组的信息元有关，而与别组无关。而卷积码的校验元 不仅与本组的信息元有关，也与其前m 段的信息元有关。另外分组码又可分为 循环码和非循环码。 2 ) 根据校验元与信息元之问的关系分为线性码和非线性码。 若校验元与信息元之间的关系是线性关系( 满足线性叠加关系) ，则称为线 性码：否则称为非线性码。 海大学顺j 一学位论文 3 ) 按照纠f 错误的类型可分为纠一随机( 独立) 错误的码、纠正突发错误的 码和纠正同步错误的，以及既能纠f 随机错误又能纠正突发错误的码。 信道编码中用到的码类很多，为清楚起见，我们用图2 1 来说明。 2 1 3 纠错码的信道模型 图2 1 纠错码的分类 不同类型的信道加不同类型的噪声就构成了不同类型的信道模型。就噪声 引发差错的统计规律而言，分为随机差错信道( 一般由高斯白噪声引起) 和突发 差错( 由突发噪声引起的) 两大类。常见的差错编码信道模型有以下几种： ( 1 1 二进制对称信道 该信道模型有一个输入取值集合x = o ，1 和输出集合y = 0 ，1 ) ，以及一 组表示输入、输出关系的条件概率。如果a w g i n 导致统讨独立的差错且条件 概率对称，即 p ( y = o l x = 1 ) = p y = l | x = o ) = p ( 2 1 2 ) p ( y = 1 i x = 1 ) = p ( y ；o 【x = 0 ) = 1 一p( 2 ，1 _ 3 ) 则称这种对称二进制输入、二进制输出的编码信道为二进制对称信道，简写为 b s c ( b i n a r ys y m m e t r i c a lc h a n n e l ) ，其信道模型如图2 2 所示： 卜海人学硕j 学位论文 输入 0 输出 1 图2 2 一进制对称信道( b s c ) 根据式2 1 1 ，其信道容量可表示为： =霄=妄扣j)p(ytxj)l092c i ( x x j ) l 掣 = m “，y ) = p “兰掣等 p ri = 0 l = 0 p l ，fj ( 2 ) 离散无记忆信道 b s c 可视为一种更广义的离散输入、离散输出信道的特例。假设信道编码 器的输入是q 元符号，即输入符号集由q 个元素x = x o ，x 1 ，x 。一i ) 构成，而检测 器的输出是q 元符号即信道输出符号集由q 个元素y = y 0 ，y t ，y q 1 ) 构成，且 信道和调制过程是无记忆的，那么图2 3 所示信道模型的输入输出特性可用一 组共q q 个条件概率来描述 p ( y 2 y i x = x 0 2 p ( y i x i ) ( 2 1 5 ) 式中，i = o ，1 ，q 一1 。这样的信道称为离散无记忆信道( d m c ，d i s c r e t em e m o r y l e s s c h a n n e l ) 。 图2 3 离散无记忆信道( d m c ) 若已知该信道的转移概率，则可以求出相应的信道传输信息i ( x ，y ) ， p ( x ) p ( y j x ) t 0 9 2 掣(216i-0 ) y ) = 等 ( 2 ) p op 、j i i ：海人学砸l 学位论文 式中p ( y j ) = p ( y = y j 产芝p ( x ，) p ( y l 。 i = 0 其信道容量由定义可知cm a xi ( x ，y ) ，由式21 5 可知在信道转移概率 p ( y j x ) 已知的情况下，信道容量c 取决于x 的概率分布。 下面以对称d m c 信道为例来分析其信道容量。 1 ) 对称d m c 信道 如果转移概率矩阵p 的每一行都是第一行的置换( 包含同样的元素) ，称该 矩阵是输入对称的：如果转移概率矩阵p 的每一列都是第一列的置换( 包含同样 的元素) ，则称该矩阵是输出对称的；如果输入、输出都对称，则称陔矩阵为对 称的d m c 信道。 有扰的对称d m c 信道有如下性质： 信道的条件熵h ( y ) ( ) 与信道输入符号的概率分布无关，且有h ( y x ) 3 h ( y x i ) ，i = 0 ，1 ，q l ，推导如下： h ( y x ) = 一地) p ( y ，x ! ) l o g p ( y ，x ，) 一e ? p ( y ，7 一) l o g p ( y l x f )( 2 1 7 ) = h t y x 、 当信道输入符号等概分布时，信道输出符n 也等概分布 输出符号等概分布，信道输入符号必定也是等概分布。 当信道输入符号等概分布时，对称d m c 信道容量为： 口 c = l o g q h ( y x ，) = l o g q + p ( y , x ，) l o g p ( y , t ) j = l 反之，若信道 ( 2 1 8 ) 2 ) 准对称d m c 信道的容量 如果转移概率矩阵p 是输入对称而输出不对称，即转移概率矩阵p 的每 行都包含同样的元素而各列的元素可以不同，则称该矩阵是准对称d m c 信道。 可以证明，准对称d m c 信道容量为： 0 c s l o g q y p ( y ，x i ) o g p ( y , x i )( 2 1 9 ) 产l 当信道输入符号等概分布时，准对称d m c 信道达到其信道容量c 。 ( 3 ) 离散输入、连续输出信道 海大学硕f ：学位论文 若d m c 信道的输入字符集有限而输出字符集y = y 0 ，yj ，y q 一1 ) 中q m 时，信道就不再是离散信道而是离散输入、连续输出的离散时间无记忆信道。 离散h , j - i | j 无记忆信道的容量，【】丁视作d m c 信道软判决译码时的容量极限。这 类信道中最重要的一种是加性高斯白噪声( a w o n ) 信道，对它而占，离散输入 x = x 0 ，x 】 _ ”，b l 和模拟输出y = 一，* ) 之间的最大平均互信息即信道容量由 下式给出： ( = 一警q 毛- i p ( y 一删1 0 9 z _ p ( y i 万x 一) 咖 ( b 符号)( 2 1 _ 1 0 ) 式中p ( y ) = p ( y ，t ) p ( x b 。 当x 给定后，y 是一个均值为x 、方差为o2 的高斯随机变量 p ( y x 产1 岳p 巾1 一，”一 ( 2 1 1 1 ) 作为特例，对于一个二进制输入的a w g n 无记忆信道，若x = x 0 ，x i = a ，- a ) ， 输入概率矢量p ( x ) = ( o 5 ，0 5 ) 即等概输入时，平均互信息i ( x ；y ) 最大而达到信道 容量，以b 符号为单位是： c = m g z 号筹咖+ j i o p ( y _ a 腿：丛者咖 ( 2 1 1 2 ) ( 4 ) 波形信道 波形信道具有输入模拟波形，其输出也是模拟波形的特点，是一个受加性 高斯白噪声干扰的带限波形信道。其信道容量，已由香农( 1 9 4 8 年) 正式定义为： c = l i r am a x 圭，( x ；】，)( 2 1 1 3 ) 1 + ，( 工) 1 若把输入、输出和噪声波形x ( t ) 、y ( t ) 和n ( t ) 展开成为1 个f 交函数的完备 集，可得到与展开式对应的一组系数 x ) 、 y n n i ，然后利用展开式中的系 数来描述信道特征。令x n = x i ，x 2 ，x n 及y n = y l ，y 2 ，y n ，这早n = 2 w t ，y i 2 x ，+ n i ， 则a w g n 信道x 。和y n 之间的平均互信息是： i ( x w ：y n ) _ 萎e p ( y t x i ) p ( x , ) l o g ”暑等1 也出， ( 2 1 1 4 ) 式中驯_ ) 2 去8 一”饥 当f x 是统计独立、零均值的高斯随即变量时，即 海大学倾t 学位论文 p ( x i ) ：毒一e 一# 。； ( 2 1 1 5 ) 式中ox 2 是各x 的方差，则对于已知的输入p d f p ( x ) ，可求出i ( x ；y ) 的最大值。 由( 2 1 1 3 ) 式推出 瞄一扩吾n j il 0 9 2 ( i + 等，= i n l 0 9 2 ( i + 焉，= 胛 l 0 9 2 ( 1 + 鲁，( 2 1 1 6 ， 假如对x ( t ) 的平均功率加以限制，即 驴f e l x 2 ( t ) d t = 耋呐= 孚 ( 2 ，1 1 7 ) 于是有： 一= t p a v = 多 ( 2 1 1 8 ) 将上式代入( 2 1 1 6 ) 式，并将结果除以t ，就得到单位时白j 的信道容量为： c = w l o g ( i + p 。，( w n o ) ) = w l o g ( i + s n r ) b s ，这就是带限a w g n 波形信道 在平均功率受限条件下信道容量的基本公式，也就足有名的香农公式。 2 14 信道容量与带宽、s n r 间的关系 根据香农公式，带宽一定时，信道容量随s n r 的增加而单调增加，因此增 大信号功率、减小信道噪声可以增加信道容量；如果s n r 固定，信道容量随着 带宽的增加而增加，其极限为= 丽p 五；如果给定信道容量c ，带宽w 和信噪 比s n r 存在着互换的关系，即若减小带宽则必须发送较大的信号功率，若有较 大的传输带宽，则在同样信道容量的情况下能够用较小的信号功率来传送，这 表明宽带系统有较好的抗干扰性。扩频通信就是利用这个原理，将所需传送的 信号扩频，使之远远大于原始信号带宽，以增强抗干扰的能力。 2 1 5 信道编码定理 每个信道具有确定的信道容量c ，对任何小于c 的码率r ，存在有速率为 r 码长为n 的分组码及( n 0 ，k o ，m ) 卷积码，若用最大似然译码，则随着码长的增 加其译码错误概率p 可任意小。 该定理表明，以任意低的错误概率通过有噪声信道传送信息是可能的，但 并不是任意分组长度为n 速率为r 的编码都能达到该目的。实际上，错误概率 j 二海人学碗l j 学位论文 越低，如果r 以任意小的距离逼近c ，则编码长度n 将会越大。 2 2 信道编码的数学基础 1 群的概念 对一个非空集合g 在并在g 上定义一种代数运算，若满足条件： ( 1 ) 封闭性a * b g( 2 ) 结合律a 4 ( b + c ) = ( a 铀) + c ( 3 ) 存在唯一单位元a * e = e * a = a( 4 ) 有唯一逆元a + a = a 。1 + a = e ( a ，b ，c ，e ，a 1 g ) 目j j 称g 为一个群。 如果这个集合中的元素满足交换律：a * b = b * a ，则称此集合为“交换群”。 若群中的所有元素都可用其中某一元素的幂次方来表示，则称此群为“循环 群”。群中元素个数称为元素的“阶”，元素个数有限的“群”称为“有限 群”，群中的“单位元”是唯一的，群中的任一元素的“逆元”是唯一的。 2 有限域的基本概念 对一个非空元素集合f ，若在f 中定义了加和乘两种运算，且满足下述条 件： ( 1 ) f 关于加法构成交换群。其加法恒等元记为0 。 ( 2 ) f 中非零元素全体对乘法构成交换群。其乘法恒等冗( 单位元) 记为1 。 ( 3 ) 加法和乘法间有如下分配律： a ( b + c ) = a b + a c( b + c ) a = b a + c a 则称f 是一个域。包含有限个元素的“域”被称为“有限域”或叫作“伽罗华 ( g a l o i s ) 域”，记为g f ( q ) 。域中的元素个数称为域的“阶”，若在有限域 g f ( q ) 中，所有非零元素可以由一个元素a 的各次幂a o ，a i c a q 之生成，则称元素 a 为生成元或本原i 。 3 扩域的概念及性质 ( 1 ) 即约多项式 对于某数域上的多项式p ( x ) ，若除了常数c 以及c p ( x ) 外。不能被该数域 上的任何其它多项式整除，则称p ( x ) 为该数域上的即约多项式。 ( 2 1 本原多项式 对于有限域g f ( q ) 上的m 次多项式p ( x ) ，若能被它整除的最简首一多项式 海大学硕l 学位论文 ( x n 1 ) 的次数n q 1 ，则称该多项式为本原多项式。 ( 3 ) 扩域 若p ( x ) 足g f ( q ) 2 啪m 次即约多项式，则g f ( q ) 域上次数小于m 的多项式 的全体，在模q 加、模p ( x ) 乘运算下构成一个q 阶的有限域，称为g f ( q ) 域的 扩域( e x t e n s i o nf i e l d ) ，写作g f ( q ”) 。称g f ( q ) 是扩域g f ( q m ) 的基域。 ( 4 ) g f ( q ) 上的本原多项式p ( x ) 在扩域g f ( q ) 上的根q 一定是本原元。 ( 5 ) 若p ( x ) 是g f ( q ) 埔m 次本原多项式，则g f ( q “) 上次数小于m 的非零多项 式的全体( 共q m _ 1 个) ，在模p ( x ) 乘运算下构成一个多项式循环群。也就是说， 扩域g f m ) 罩至少存在一个本原元a ( a 代表一个次数小于1 t i 的多项式) ，它的 各次幂。o ，- ，。u 。2 构成了扩域的全部非零元素。 4 有关基的基本概念及定理m 1 ( 1 ) 自然基 g f ( p “) 中的p m - 1 个非零元素，均可以用本原域元素口的各次幂表示：口o - 1 口，口2 ，口，也可用本原多项式的根口多项式表示，此时 1 ，口，口2 ， t 2 严1 ) 就是域的一组自然基，如g f ( 2 3 ) 中的自然摹是 1 ，c t * ，口2 。 ( 2 ) i t 规基 定义 a ，a ，c g p 2 - i ，。，- ) 为g f ( ：p “) 域的正规基，其实就是以。为根的本 原多项式f 溆) 的其轭根系。 ( 3 ) 对偶基 迹的定义：。g f ( q ”) ，则它在g f ( q ) 上的迹定义为 耳( a ) ：“+ a q + g q 2 + + 。q ”1( 2 2 1 ) q 为素数或素数幂。 对偶基的定义 与g f ( p ”) 的基底b = ( o ， 1 ， ) 相对应，若 f 1 i 号 。帆n 卜1* 。 (2222)0其它 、 4 f 。海人学顺1 1 学位论文 满足，则称g f ( p “) 的基底b 、= ( yo ，y1 一，y 。一1 ) 是b 的对偶基。 如果将迹函数扩展到普通线性函数f 乞卅，基底b 、b 、存在下列关系： i i = j f ( f 1 2 i y , ) = ( 2 2 3 ) l0其它 则也称g f ( p “) 的基底b = ( yo ，yi ，ym _ 1 ) 是b 的对偶基。其中乞。代表g f ( p ”) 一g f ( p ) 的所有的线性函数的集合。 ( 4 ) 定理l 设 u j ) 为迦罗华扩展域g f ( p “) 的基， xk 为它的对偶基，则任一域元素z 可表示为： z ：宝：女4 ，其中z k = t r ( z u k ) ( 2 2 4 ) k = o 也可表示为： z = f ( z f l p ，n ( 2 2 5 ) i = 0 ( 5 ) 定理2 设 u i ) 为迦罗华扩展域g f ( p “) 的基， k ) 为它的对偶基，则两域元素z 、 g 的乘积w 可以对偶基的形式表示为： mim1 w = f ( w f l u k ) + = f ( z g u k ) 4 ( 2 2 6 ) k = ok = 0 ( 6 ) 定理3 如果a , b ，c g f ( p “) ，a _ b c ，则下列关系式成立： f ( b f l )f ( b f l a )f ( b f l a 、 ，( 妒口】f ( b f l c t 2 ) f ( b f l a ”) f ( b f l o t m1 ) f ( b f l a “) f ( b f l a2 m - 2 ) 设 xi ) 是自然基( a ) 的对偶基，对任何非零f e g f ( p ) 和非零b g f ( p ”) ，b 以对偶基表示为： m - i 6 = ( 2 2 8 ) i = 0 c 以自然基表示为： c = 叩， ( 2 2 9 ) d 2 q ， 卅 ，d d 叩啪 啪，一， 1 = 一 印q i | 。1 海人学硕j j 学位论文 出定理3 司得： a o = b o c o + b l c l + 。+ b l c i a 1 = b l c o + b 2 c l + + b m c m 1 a m f b m - i c o + b m c l + + b 2 m 一2 c ：m 一1 ( 2 2 1 0 ) 这罩b 。+ k = 窆p t b j + 。，其中p i 为g f ( p ) 的即约多项式p ( x ) 的系数，p ( x ) = m 王- i 即+ x 。 j = o 1 一” 2 3 差错控制编码 2 31 差错控制的基本方式 差错控制方式基本上分为两类，一类称为“前向纠错”，另一类称为“反 馈校验”。在这两类基础上又派生出一种称为“混合纠错”。 ( 1 ) 前向纠错 发送端对信息码元进行编码处理，是发送的码组具有纠错能力。接收端收到 这些码序列后，通过译码能自动发现并纠f 传输中出现的错误。这种方式不需要 反向信道，特别适合于只能提供单向信道的场合。由于接收端能自动纠错，不会 因发送端反复重发而延误时间，系统实时性好。这种差错控制方式的主要特点就 足设备较为复杂。 ( 2 1 反馈校验 接收端将收到的信息码元原封不动地转发回发送端，并与发送的码元相比 较。如果发现错误。发送端再进行重发。这种方法的原理和设备都比较简单，无 需检错和纠错编译系统，但要使用反向信道。由于每个信息码7 亡至少要被传送两 次，所以传输效率低，实时性差。 ( 3 ) 混合纠错 发送端经过编码后发出的码组不但能够检测错误，还具有一定的纠错能力。 如果接收端收到的码组错误较少，则自动进行纠错；如果错误太多，超出了码的 纠错能力但尚能检测时，接收端通过反向信道请求发送端重发一遍1 2 1 。 海人学颂i 二学位论文 2 3 2 汉明码距与编码纠错能力的关系 汉明码距指的是长度相同的两个符号序列( 码字) a l l b 之问对应位置上不同 码元的个数，用符号d ( a ，b ) 表示，如两个二元序列： a - 11 0 0 1 0 1b = 1 0 1 l1 0 l 则得d ( a ，b ) = 3 。 有了汉明码距的概念，我们就可以用汉明码距束描述码的纠错检测能力。如 果一组编码的码长为n ，如果将这些资源全部利用上，可以对2 “的符号进行编码， 但这样一来这个编码就没有任何的抗干扰能力，因为合法码字之间的最小汉明码 距为i ，任何一个符号的编码的任意一位发生错误，就变成了另外一个符号的编 码，它也是一个合法的码字。接收端不能判断是不是有错误发生。我们可以在2 “ 个可用的码字中问选择一些码字来对信源符号进行编码，把这些码字称为合法码 字，而其他的没有使用的码字称为非法的码字。这样合法码字之间的汉明距离就 会拉开，有些合法码字发生错误后有可能变成非法码字，接收端如果收到这些非 法码字后就可以判断出传输过程中出现了错误。码字之间的最小汉明距离越大， 编码的抗干扰能力就越强。如编码的最小汉明距离为2 ，任何合法码字发生一位 错误都会变成非法码字，但不能确定是由哪一个合法码字错误而来，因此这个编 码可以发现一位错误；如编码的最小汉明距离为3 ，任何合法码字发生一位错误 都会变成非法码字，而且距离原来的码字距离为1 ，而距离其他任何合法码字的 最小距离为2 ，因此可以确定这个非法码字是由哪一个合法码字发生错误而来， 因此这个编码用作纠错编码可以发现一位错误并且纠f 一位错误，但是如果发生 了两位错误，也可发现但是如果试图纠正这个错误就会产生新的错误；如果把这 种编码只当作检错编码，则可以发现两个错误。以此类推，可以总结出编码的最 小汉明码距与编码纠错检错能力之间的关系”】： 要检测e 个错码，则要求最小码距：d m i n c + l 要纠正t 个错码，则要求最小码距：d r a i n 2 t + l 要纠正t 个错码，同时能检测e ( e t ) 个错码，则要求最小码距： d m i n e + t + 1 ，e t 纠正t 个错误和p 个删除，则要求最小码距：d r a i n 2 t + p * l 海人学硕1 ：学位论文 如果一个分组码的数据位长度为k ，校验位长度为r ，总的编码长度为n ， n = k + r ，则总的可以编码的合法码字的个数为2 。，总的码字个数为2 “，可以看出 如果检验位的长度越长，合法码字所占的比例就越小，如果这些码字能够尽可能 在所有的码字中均匀分布的话，合法码字之间的最小汉明码距就可以越火，编码 的抗干扰能力也就越强，因此设计编码方法的最重要的任务就是尽量使得合法码 字能够尽可能的均匀分布。 2 4 常用的差错控制编码 2 4 1 奇偶校验码 奇