（微电子学与固体电子学专业论文）一种低误码率efec算法设计与实现.pdf

摘要 摘要 随着当代通信传输中数据量的激增，传输误码率也随之增加。f e c 即前向纠 错算法已经得到越来越高的重视。f e c 算法在数字电视等很多领域都有应用，尤 其广泛应用于电通信系统和光通信系统，在很多通信产品中都是采用这项技术来 改善通信系统的性能。在光传输系统中采用前向纠错技术能够降低光链路中线性 及非线性因素对系统性能的影响，达到延长传输距离的目的。现行的增强型f e c 算法，更进一步极大的提高算法纠错能力。本文从工程应用角度，基于实际高速 光通信光传送网系统中数据传输可靠性需求，构造出一种新的增强型f e c 算法， 并将算法硬件实现在o t n 的网络中。 论文分成三个阶段：建模仿真阶段，电路实现阶段和上板测试阶段。 根据对上板测试的数据分析可知，本算法纠错能力很强，能够很好的满足 0 1 n 的实际需求。对于其它通信领域，也可以通过使用本算法的结构和演变算法 的码型来完成传输中的纠错功能。 关键词：r s 码增强型前向纠错信噪比光传送网 a b s t r a c t 3 a b s t r a c t n o w a d a y s , 、析mt h et r a n s m i s s i o nd a t ac a p a c i t ys h a r p l yi n c r e a s e s , 5 0i st h ee r r o r r a t e n l ef o r w a r de r r o rc o r r e c t i o ng e t sm o r e ：a n dm o r ea t t e n t i o n 。珏ef e ct e c h n i q u e h a sa p p l i e dm a n ya r e a s ，s u c ha sd i g i t a l 代e s p e c i a l l yw i d e l yu s e di nt h ee l e c t r i c t e l e c o m m u n i c a t i o na n do p t i c a lc o m m u n i c a t i o n m a n yp r o d u c t s a d o p tt h ef e c t e c h n i q u et oi m p r o v et h es y s t e mp e r f o r m a n c e 1 f l l ef e cc o u l dr e d u c ei n f l u e n c e s c a u s e db yt h el i n e a ra n dn o n l i n e a rf a c t o r si nt h eo p t i c a lc h a n n e l ，s oi nt h i sw a yt h e t r a n s m i s s i o nd i s t a n c ew i l lb eg r e a t l yl e n g t h e n e d n o w , t h ee n h a n c e df o r w a r de r r o r c o r r e c t i o nm e t h o dh a sb e t t e rc o r r e c t i o np e r f o r m a n c e f r o mt h ep o i mo fv i e wo f e n g i n e e r i n ga p p l i c a t i o n , b a s e do nt h eh i g hs p e e do p t i c a lt e l e c o m m u n i c a t i o no t n s y s t e md a t at r a n s m i tr e l i a b i l i t ya p p l i c a t i o nr e q u e s lm yp a p e ri n t r o d u c e san e w k i n do f e f e ct e c h n i q u e a n di m p l e m e n t si to no t nn e t w o r k t h e r ea r et h r e ep h a s e si n t h i sp a p e r , t h e ya l es i m u l a t i o n , c i r c u i ti m p l e m e n t a t i o n a n do nb o a r dt e s t a f t e ra n a l y z i n gt h eo nb o a r dt e s tr e s u l t , t h ee f e cd e s i g ni m p l e m e n tm e t h o dh a s b e t t e rc o r r e c t i o na b i l i t ya n dc o u l ds a t i s 匆t h ec u r r e n to t n r e q u i r e m e n tv e r yw e l l o t h e r t c l e c o m m u m e m i o na l e a sc o u l da l s ou s et h i se f e cd e s i g ns t r u c t u r ea n d j u s te v o l v et h ec o d ep a t t e r n t 0s a t i s f yt h ec o r r e c t i o nf u n c t i o n k e y w o r d ： r sc o d ee f e cs n ro t n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包括其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：l 彳竖霉日期：) m 1 1 z 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或者使用论文工作成果时署名单位仍然为西安电子科技大 学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文 的全部或部分内容，以允许采用影印、缩印或其它复制手段保存论文。 本人签名：鲤茎日期：塑2 ：! ：幺 导师签名：扭逊日期：卫号叫 第一章绪论 第一章绪论 本章首先介绍了通信系统组成以及信道编码发展历程，然后介绍了前向 纠错码在下一代光传输系统o t n 中的应用，论文选题的实际意义，最后说明 本文的主要内容和取得的成果。 1 1 通信系统组成与香农理论 通信是人与人之间、人与机器之间的信息传输、处理或再现信息的过程。 它涉及信息的发送者、接收者和传输媒体。通信的目的是要把对方不知道的 消息及时可靠地( 有时还需秘密地) 传送给对方，因此，要求一个通信系统 传输消息必须可靠且有尽可能高的传输速率。在数字通信系统中可靠性与有 效性往往是一对矛盾：若要求很高的有效性，则必然使得每个数据码元所占 的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增 加，传送消息的可靠性减低；若要求可靠，则使得传送消息的速率变慢。因 此，如何较合理地解决可靠性与有效性这一对矛盾，是正确设计一个通信系 统的关键问题之一【l 】。通信理论本身也正是在解决这一对矛盾中不断发展起 来的。通信的目的在于消除传输信息的不确定性，通俗的讲，就是实现信息 传递。按照传递信息形式的不同，通信系统可以分为模拟通信系统和数字通 信系统。由于数字通信具有模拟通信不可比拟的优点，如抗干扰能力强、便 于差错控制、便于使用现代数字信号处理、易于加密等等，因此数字通信更 能适用于现代通信的要求，这里仅讨论与数字通信有关的信道编码问题【1 1 。 通信系统的质量评估有很多指标：有效性、可靠性、安全性、经济性、 标准性、可维护性等【1 2 j 。其中有效性是信息传输的速率问题，即单位时间能 够传输多少信息；而可靠性是指信息传输的质量问题，即信息是否无误的从 接收端得到。早期，人们普遍认为有效性与可靠性是一对不可调和的矛盾， 因而在有扰信道上实现可靠传输的唯一方法就是将传输速率降为零，然而事 实并非如此i i 。 1 9 4 8 年s h a n n o n 在他的开创性论文通信的数学理论0 4 】中，首次阐明 了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，否 定了上述观点，为在有扰信道实现可靠通信指明了方向。信道编码奠定了纠 错码的基石，s h a n n o n 也因此被称为“信息论之父”。 2 一种低误码率e f e c 算法设计与实现 s h a n n o n 信道编码定理【1 哪： 任意离散输入无记忆平稳有噪声信道都有一个被称为是信道容量的值 c ，它标志着信道传输能力的上限，只要信息传输速率r c ，就存在一种编码 方式，当平均码长足够大时，译码错误概率可以做到任意小；反之，则无论 采用何种编码方式都不能保证错误概率任意小。s h a n n o n 证明码长n 大时， 随机选择的码以很高概率为好码。信道编码定理表明，信道容量正好等于信 息传输速率的上界。 s h a n n o n 在文中将通信系统分成五个部分：信源、编码器、信道、译码器 和信宿【1 4 1 。把任何一个数字通信系统抽象为图1 1 的基本框图，成功地定义 了信息量的概念，启发式地证明了几个编码定理。图1 1 中的信源( i n f o r m a t i o n s o i l r c 七) 随机地产生消息( m e s s a g e ) ，一般用消息的统计特性来刻画信源，不 同的信源构成不同形式的通信系统；发射机( t r a n s m i t t e r ) 完成由消息变换为 信号( s i g n a l ) 的功能，是一个广义的编码器，对于不同的需求，有把非电信 号转换成电信号、模数转换、调制等；由于有噪声源( n o i s es o u r c e ) 的存在， 接收信号( r e c e i v e ds i g n a l ) 会有不同程度上的畸变，这种畸变是由信道的物 理特性和噪声源的统计特性确定的，一般用条件概率转移矩阵或条件概率密 度来描述；接收机( r e c e i v e r ) 是从接收信号恢复正确的消息，是一个广义的 译码器；这个估计的消息最终送给了信宿( d e s t i n a t i o n ) ，也就是信息接收者， 它可能从信源、变换器、传输信道或接收器中引入。 图1 i 通信系统模型 信道容量定义为信道输入与信道输出的信息，它表征了信道可靠传输的 最大速率。最常见的信道容量计算公式就是带宽、功率受限下的加性高斯白 噪声信道容量计算式。设a w g n 信道带宽受限【w ，w ，噪声双边功率谱密度 为n 0 2 ，信号功率是p 其中c 是信道容量，r 是码率，高斯白噪声信道的信道 第一章绪论 容量c 的计算方法如式： c - w l o g ：( 1 + 南埘 式中，w 是信道所提供的带宽，p 。= e s t 是信号功率，e s 是信号能量，t 是 分组信号的持续时间即信号宽度，p s w 是单位频带的信号功率，n o 是单位频 带的噪声功率，p , ( w n o ) 是信噪比。这里以加性白高斯噪声( a w g n ，a d d i f i v e w h i t eg a u s s i a nn o i s e ) 信道为例来说明信道编码定理。 设信息传输速率r 比特信道符号，则单位比特所用能量为e = p r 。记 高斯噪声的单边功率谱密度为“，则o = 2 盯2 ，呱u s n r = 躲风e _ l 。容量曲线 如图1 2 所示。 g a u s s ii n m o u t s b p s k l ? f ， ， 图1 2 理想a w g n 信道的容量曲线 从图1 2 可以看出，日n o 0 0 d b 时，信道容量c 0 5 。s h a n n o n 信道 编码定理指出，存在速率r = 0 5 的编码方案，只要e n o = 0 0 就可以达到“可 靠”通信。所谓“可靠”，一般是用误比特率( b i t - e r r o r - r a t e ) b e r 来度量的。 尽管实际的通信系统对b e r 的要求有差别，理论的“可靠”通信一般以 b e r 1 0 6 一1 0 4 来衡量。从图1 2 还可以看出，与不编码( r = 1 0 ) 的b p s k 4 一种低误码率e f e c 算法设计与实现 调制相比较，s h a n n o n 信道编码定理指出了编码可以节省能量达9 6 d b 。如果 采用1 2 的编码，利用b p s k 信号在理论上可以达到o 2 d b 。由于b p s k 在工 程实现上简单，因而当信息速率较低，例如( rs0 5 比特信道符号) ，采用 b p s k 调制就足够了。 s h a n n o n 编码定理以后h a m m i n g 、s l e p i a n 、p r a n g e 等人在5 0 年代初，根 据s h a n a o n 的思想，给出了一系列有效译码的方法。纠错码越来越受到大家 的重视，同时无论在理论还是实际中都得到了飞速发展。 纠错码的主要发展过程大致分以下几个阶段【1 5 】：5 0 年代至6 0 年代初， 主要研究各种有效的编、译码方法，奠定了线性分组码的理论基础：提出了 b c h 编码、译码方法以及卷积码的序列译码；给出了纠错码的基本码限；还 出版了纠错码的第一本专著。 6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。提出了 如门限译码、迭代译码、软判决译码和卷积码的v i t e r b i 译码等有效的编译码 方法；同时注意到了纠错码实用化的问题，讨论了如码重量分布、译码错误 概率和不可检错误概率的计算、信道的模型化等与实用化有关的各种问题。 7 0 年代以来，纠错码在实际应用中得到了更大的发展。大规模集成电路 和微机的迅速发展，为纠错码的实用打下了坚实的物质基础。 7 0 年代末、8 0 年代初( 2 0 世纪) ，gu n g e r b o e c k 把编码与调制相结合提 出的网格编码调制( t c m ，仃e i l i s - c o d e dm o d u l a f i o n ) 技术【16 】是编码理论的又一 重要里程碑。 1 2 0 烈介绍 o t n 的全称是o p t i c a l 仃a n s m k n e t w o r k ，中文名称是光传送网。它是在s d h 的基础上在为了满足爆炸性的带宽需求下发展起来下一代光传送网络，是一 种全新的光传送网络机制。 目前，全球因特网业务已经在骨干网络层面上远远超过话音业务，成为 全球的主导业务。大量迅速发展的因特网业务不仅对标准传送网的容量形成 了巨大的压力，而且也对传送网的结构形成了新的挑战。另外，随着技术的 不断进步，每比特传送成本已经降低了几百倍。带宽成本的持续下降不仅刺 激了大量业务量和宽带业务的产生，而且也迫使网络规划者重新考虑建网的 基本假设和前提。s d h 网络在标准电信网络中扮演着很重要的角色，而且在 可以预见的未来仍然是不断改进以适应电信网转型的大趋势。然而必须看到， 随着数据业务逐渐成为全网的主要业务，作为客户层的核心网络路由器设备 的端口速率越来越高，目前起码是2 5 g b w s ，并在向1 0 g b i f f s 乃至4 0 g b i t s 速 第一章绪论 率发展。作为支持电路交换方式的s d h 复杂的t d m 时分复用结构已经不再 需要，额外的t d m 复用结构不仅增加了很多路径的丌销，减低了效率，而且 增加了设备的复杂性和成本，所以需要探索新的技术核心的更有效的网络结 构【6 1 。 采用w d m 波分技术后可以使容量迅速扩大几倍至几十倍；典型的电再 生中继距离也从标准的6 0 1 0 0 k m 增加到4 0 0 6 0 0 k m ，从而节约了大量光 纤和电再生设备，大大降低了传输的成本；目前w d m 的发展十分迅猛，很 多w d m 系统已经大量投入应用。可以看出，采用w d m 试验系统容量的世 界记录已经突破，容量瓶颈转移到传送节点上， 光传送网可以从垂直方向划分三个独立的层网络，即从上往下为o c h 、 光复用段层o m s 和光传输段层o t s ，相邻两个层之间构成客户，服务层关系， 目前所支持的客户层信号主要是数字信号( p d h 、s d h 、a t m 、i p ) 。o t n 一个重要的特点就是提供带外f e c 功能，能够有效的保证光传输的可靠性。 图1 3 是o t n 的结构关联图，从上到下分成两个层次：上层是电层，下 层是光层。客户信号经过加入开销字节包封成o p u k 结构，在到下一级包封 成o d u k 信号，加入f e c 的开销字节后包封成标准的o t u k 信号，这样就到 光层的载体o c c 中传输。 o c hp a y l o a du n i t o p u k ) o c hd a t au n i ti o d u k ) o c ht r a n s p o r tu n i t ( o t u k ) o p t i c a lc h a n n e l ( o c h ) o p t i c a lc h a n n e lc a r r i e r o c c ) o p t i c a lm u l t i p l e xs e c t i o n o p t i c a t r a n s m i s s i o ns e c t i o n o t mo v e r h e a ds i g n a l o p a c a ls u p e r v l s o r yc h a n n e l 图1 3o t n 的结构层次 o p t i c a lp h y s i c a ls e c t i o n 图1 4 是o t h 帧的结构框图，可以看到带外f e c 的地址空间。每个o t u 6 一种低误码率e f e c 算法设计与实现 帧的行是3 8 2 4 个字节的数据，和2 5 6 字节的e f e c 区域。6 7 的编码冗余， 实际上如果传送的数据带宽大于o t u 的带宽，还可以占用e f e c 的区域传输， 但这样纠错数据量会变少，e f e c 算法的纠错性能也会降低。 图1 4o t n 的l 帧结构 1 3o t n 系统中f e c 应用和论文选题意义 随着光通信向超光速、超大容量方向发展，以及s d h 体系结构、d w d m 系统、全光网以及光交叉连接等技术在光纤通信系统中不断应用，加之器件 性能不断改善，信道速率得到了跳跃式的提升，系统容量得到了成倍的扩大。 但传输的有效性和可靠性是一对矛盾，在速率大幅提高的同时，色散、非线 性效应、接收机性能等也成为限制系统性能的主要因素。容量的扩大也会引 起一系列诸如各路光信号之间的串扰，信号的同步、定时、恢复的问题，这 一切都会引起在通信中误码的产生，从而降低通信的可靠性。通信可靠性的 降低最终又制约了通信质量的提高，通信距离的延长，多路复用的大规模应 用，以及通信设备成本的降低，因此大大阻碍了光通信的进一步发展。 市场的需求决定了技术的发展：因此业界开始致力于改善器件的性能， 加大信号发射端功率等措施的研究，以降低这些不利因素。但是由于器件性 能的提高已经没有多少潜力可挖，加大发射功率又会大大增加成本，增加系 统器件负担，造成非线性效应的严重增大，因此这些都不是理想的方案。所 以在第一代光通信系统中并没有得到应用的f e c 技术也开始广泛的被应用到 目前的光通信系统中，特别是随着光传输速度的逐步提高，f e c 技术在光通 第一章绪论 7 信中也是越来越重要。 从香农定理可知，当信息发送率小于信道容量时，就存在某种f e c 编码， 用来纠正信道传输中发生的错误，提高系统的可靠性。总的来说，f e c 技术 就是编码端在数据发送之前根据一定的编码规则增加一定的冗余码，使得原 来不具有相关往的数据产生相关性，在译码端根据译码规则，利用冗余所产 生的数据线来纠正信道中发生的错误，恢复发送的码序列。f e c 技术总是力 求用最少的冗余纠正尽可能多的错误，在速率和可靠性之间找到一个最佳的 平衡点。它的主要优点是：不需要反馈信道，适用于一点发送多点接收的广 播系统，译码延时固定，较适合于实时传输系统。但是这种方式要求预先确 定信道差错的统计特性，以便选择合适的纠错码，否则难于满足纠错性能的 要求。 在光通信系统中应用f e c ，具有能够延长光信号传输距离，增加光通道 复用光信号路数，降低光发射机发射功率等优点，最早应用在超长距离的海 底光缆系统中。最早f e c 采用的是带内方式，把f e c 的校检b i t 和相关的状 态指示b i t 用s d h 预留的开销字节来传送，不用开辟新的空间专门分配给 f e c ，因而增加了f e c 功能后传输的速率不改变。带内f e c 的优点是不影响 传输速率，但是它能提供的误码性能改善有限，一般达到2 个d b 左右，而且 对突发性的差错改善不明显。 随着陆地光通信系统的发展，单信道速率提高，多通道复用的应用，f e c 应用将成为降低设备要求容限和系统组网成本优选方案之一，因此也开始考 虑采用性能更优越的带外f e c 方式，专门为f e c 的校检b “分配了一个空间， 一般是在有效载荷的后面加上一段，专门用来传输f e c 的校检b i t o 通过牺牲 传输速率为代价，来达到提高误码的纠正能力。现在不少公司开发的s d h 系 统均采用了带外f e c 。到目前为止，删一t 一直在研究何种纠错码最适合用 于陆上系统的带外f e c ，各个厂家都按照自己的方式进行a s i c 和系统设计， 在互通方面也是存在着极大的障碍。 最近，很多国外的公司正在数字包封的基础上开发所谓的s u p e r f e c 系 统，目的是更好的提高系统性能，延长传输的距离，增加传输的波长数，以 及补偿色散、损耗和极化的损失阎。一般是通过应用纠错能力更强的码型结 构，增加冗余字节，提高传输的速率，来获得更大的系统收益，提高系统的 可靠性，具体来说，比原来的f e c 系统要多出3 5 d b 。很多公司的增强型 f e c 系统得到了很好的效果，提高了系统的性能，可见f e c 技术在国内也已 经作为光通信中的一个新的热点被广泛的应用开来，只是关于f e c 在高速光 传输中的理论研究目前国内还很少，因此有必要针对f e c 在光通信应用中的 理论分析、特别是更高的光传输中应用新的性能更好的f e c 方案的问题进行 一种低误码率e f e c 算法设计与实现 探索。 f e c 分为带内f e c ( i nb a n df e c ) 和带外f e c ( o u to f b a n df e c ) 。所 谓带内f e c ，是指利用信道本身未使用的开销字节，作为f e c 纠错编码字节， 实施f e c 编码后，信道码元速率不变。所谓带外f e c ，是指把f e c 纠错校检 信息字节插入到传输信道，实施f e c 编码后，信道码元速率增加。这些附加 的校检信息被用在接收端以确认并纠正在传输中产生的错误。o t n 帧的结构 中含有f e c 校检字节的位置，所以是带外f e c 的处理方式。 图1 5 含有f e c 功能的光传输系统模型 本文应用的背景是在o t no v e rs d h 系统中应用f e c 技术，降低远距离 光传输中的误码率。 1 2 3 4 综上可以看出f e c 的必要性主要有以下几点： 物理信道本身存在缺陷； 信号速率提高对信道影响较大，对系统的可靠性要求提高； 很多系统要求信号的实时纠错； 很多场合都要求系统能够实时纠错，随着理论和i c 的发展，其缺点被不 断弱化。 f e c 编码是信道编码技术，可以有效地降低误码率。f e c 编码可以允许 系统工作在较高的误码率的情况下，也就是说，即使系统工作在较高的误码 率信道中，也能够通过f e c 技术达到一个较低的误码率水平。这无疑放宽了 高速光通信系统对各个器件性能的要求，从而降低了系统的造价。同时也提 高了系统对色散、非线性效应、q 值和o s n r 的容忍度，有利于信号高速率、 第一章绪论 9 长距离的传输阴。 从上面的论述中，可以看到f e c 技术在当今的很多领域有着广泛的应用， 而且对改善光通信中传输的可靠性效果明显。但是应用标准的b c h 码、r s 码到高速光传输系统中，在数据量不大的情况下，标准的f e c 算法能够满足 实际需要，一般增益在6 7 d b 。但现阶段数据量剧增，使得通信中引入的误 码数也在上升，就存在编码增益不够的问题，纠错能力有限。如果采用卷积 码等方法，在硬件电路实现上十分复杂，而且占用大量逻辑资源。本文根据 实际应用中的需求，在满足纠错指标的前提下，构造出种增强型f e c 算法。 当输入的误码率是3 3 0 1 0 q 时，输出的误码率在1 0 x1 0 1 2 左右；这样编码 增益能够达到8 d b 。因此，本文具有很强的应用性。本文另一个创新是在节约 硬件实现资源使用方面。众所周知，当今阶段芯片的规模越来越大。很多芯 片已经在千万门的层次上。e f e c 算法需要很多的逻辑，如果算法实现方式不 合理，势必增加很多的逻辑量，这就使得芯片成本上升。在满足性能的基础 上，本文注重考虑e f e c 算法中逻辑资源的使用，减少逻辑规模。编码上复 用组合逻辑减少逻辑使用量。本文实现时利用解码b m 迭代时间较短的特点， 多个码字的解码器共用一个b m 模块，这使得逻辑资源大大降低。 1 4 本文的主要工作及内容安排 本文主要是结合通信光网络项目中的“高速光通信系统可靠性研究”和 一个o t n 网络实际应用项目，对增强型f e c 算法不同实现方式进行研究， 分析了不同e f e c 实现方式的纠错性能和硬件电路实现逻辑量等性能，主要内 容安排如下： 1 第二章，详细论述了r s 码的编译码原理及算法，重点讨论了代数译码 算法的流程及一些关键问题，并且比较了各种算法的复杂度。 2 第三章，利用m a t l a b 的s i m u l i n k 对通信系统中不同e f e c 实现方 式进行建模，得到性能指标。 3 第四章，选择一种满足需求的e f e c 实现方式，并利用硬件描述语言 v e r i l o g 对改进的算法进行硬件电路实现，仿真和综合，最后布局布线到 f p g a 中。 4 第五章，主要是在通信单板上进行验证，得到e f e c 的编码增益性能 指标，并给出结论。 5 第六章，本文的总结。 第二二章数学理论和r s 码原理 第二章数学理论和r s 码原理 本章首先介绍纠错码算法相关的数学知识，然后详细讨论r s 编解码算法。 讨论了关于r s 码的一些基本概念，编译码原理，详细论述了r s 码的各种代数译 码算法，并对几种译码算法的复杂度做了分析比较。 2 1 基础理论 2 1 1 有限域理论 有限域的理论是来自于近代代数，要掌握有限域的知识首先要了解近代代数 中的基本概念一一群。这一节从群开始介绍，一直到有限域的相关知识。 群：设g 是一个非空的集合，若在g 上定一个二元运算，满足： & 封闭型c = a b ： b 结合律a - ( b c ) = ( a b ) c ； c 单位元a e = e a = a ； d 逆元 a a 。= a - 1 a = e ( a ，b ，c ，e g ) ； ( 2 1 ) 则称( g ，) 为一个群。如果群还适合交换律：即对任何a ，b g 有a b = b a ， 称群g 是可换群或称为阿贝尔群。 2 1 2 纠镨码的编码理论 信道纠错码主要分成分组码和卷积码两大类。本文设计的r s 码是线性分组 码的一种，理论部分从线性分组码开始介绍，这样有一个连贯的概念。 ( 1 )线性分组码 分组码是一种代数编码，它的基本单位称作码字，每个码字包含k 个信息 位和n - - k 个监督位，其监督位和信息位之间是一种代数关系，如果这种代数关 系是线性的，则称为线性分组码。如果在( n ，k ) 码中信息位没有变化，与原 信息码排列相同，并且与监督位分开，则称为系统码，否则称为非系统码。下 面是线性分组码的两个重要参数： 码率：r = k n ，码率实际上就是编码效率或传输效率。 最小码距：在一个码字集合中，两个长度均为n 的码字之间，对应位取值不 同的数目，则称为两个码字的码距。在( n ，k ) 线性分组码中，任意两个码字之 间码距的最小值，称为该线性分组码的最小距离d 。最小码距d 决定了该线性分 组码的纠错能力，具体关系如下： 若能发现。个错误，要求d 耋e + 1 ； 1 2 一种低误码率e f e c 算法设计与实现 若能纠正t 个错误要求d 耋2 t + 1 ； 若能发现e 个错误的同时纠正t 个错误，要求d 至t + e + 1 t e 。 ( 2 ) 循环码 设一个( n ，k ) 线性分组码c ，如果码组中的任何一个码字的循环移位也是 这个码组中的一个码字，则称c 为循环码。 循环码的表示一般用多项式的形式，即把码字c 的各个分量看作多项式的各 次项系数，如一个( n ，k ) 循环码c 可以表示成c ( x ) = 厶扩+ c n _ 1 x ”1 + e e e + c l x + c o ， 且把这个多项式称为( n ，k ) 循环码的码字。循环码的生成多项式在一个( n ，k ) 循环码中，存在且仅存在一个次数为n k 的码字多项式： g ) = x 柑+ g m l x “+ e e + 9 1 x + g o ，它能生成循环码集合中的所有码字，并且 每个阶小于n 一1 的g ( x ) 的倍式都是一个码字多项式，则称为g ( x ) 是循环码 的生成多项式。 2 2 r s 码的概念 如果一个b c h 码的码元和其生成多项式g ( x ) 的根均在g f ( q ”) ( q ”2 ) 上，则称此b c h 码为r s 码。r s 码是一种非二进制形式的b c h 码，在( n ，k ) r s 码中，输入的信息分成k * m 比特一组，每组包含k 个符号，每个符号由m 比 特组成。r s 码的最小汉明距离d = 2 t + 1 ，因此它是最大距离可分码( m d s 码) ， 也就是说：在所有的线性分组码中，r s 码有最大的最小汉明距离。所以它是纠错 能力最强的，且纠错能力t = ( n k ) 2 。 定义2 2 1 给定任一有限域g f ( q ) 及其扩域o f ( q ) ，其中q 是素数或素数 的幂，m 为某一正整数。若码元取自g f ( q ) 上的一循环码，它的生成多项式g ( x ) 的根集合r 中含有以下8 - 1 个连续根：r 2 口“，口“，口“” 时，则由 g ( x ) 生成的循环码称为q 进制b c h 码。 设m i ( x ) 和e i ( x ) 分别为口蛳“( 踟，1 2 ，8 - 2 ) 元素的最小多项式和级，根 据循环码的生成多项式的性质，可知b c h 码的生成多项式和码长分别为： g ( x ) = l c m ( m o ( 功，码( 功，一2 ) ) ( 2 2 ) r l = l c m ( e o p l ，e 8 _ 2 ) 如果生成多项式g ( x ) 的根中，有一个g f ( q 。) 中的本原域元素，则n = q m 1 ，称 这种码长为n = q m 1 的b c h 码为本原b c h 码，否则称非本原b c h 码。 在q 进制无记忆离散对称信道中，若信道的转移概率p 1 q ，则信道产生错 误个数少的可能性最大，也就是错误位置多项式的次数最低。 下面从b c h 码的角度定义r s 码的概念。 由定义可知，r s 码最主要特点之一是码元取自g f ( c o 上，而它的生成多项式 第二章数学理论和r s 码原理 的根也在o f ( q ) 上，所以r s 码是码元的符号域和根域一致的b c h 码。 设o 【是有限域g f ( q ) 的一个n 阶元素，其中q = p m , p 是该域的特征。因为： x 纠一1 = 兀 一) ，0 【5 的最小多项式m i ( x ) ：- x 仪，所以长为n = q - i ，设计距 一三b f ( 目) 离为8 的r s 码，其生成多项式为： g = o 一扩) 一扩“) 章一矿枷) ( 2 3 ) 通常情况下取m o = l ，此时 2 t g ( x ) = ( x - a ) ( x - a 2 ) ( x - a 2 。) = g ，x ( 2 4 ) ，1 0 但取不同的m o 值，可以有不同的生成多项式，可以形成不同结构的编码器，其复 杂度也不一样。详细讨论可以参照下节的编码器实现。 由该生成多项式可以构造出一个q 进制的r s 码，有最小距离为6 。由于线性 码的最大可能的最小距离是校验元的个数加l ，而r s 码恰好做到了这一点，因此， 称r s 码为极大最小距离可分码，简称m d s 码。显然，r s 码的设计距离8 与实 际距离d 是一致的 一个码的纠错能力，完全由它的最小汉明距离“决定，而r s 码的“则完 全由生成多项式的根所决定的。根据b c h 限可知，r s 码的最小距离矽。就是6 。 对于参数为 n , k ，d 】的本原r s 码，其符号域为g f ( p ) ，p = 2 。在该域上，码长n = 2 m 1 即每个码字有n 个符号，每个符号用m 个比特表示。信息位为k 个符号，校验位 是n - k 个符号，该码最多可以纠正b t ) 2 j 个符号错误。 2 3r s 码的编码原理 r s 码的编码原理及编码器的实现比较简单，而译码则相对复杂一些。编码方 式有三种，时域编码、频域编码和利用c a u e h y 矩阵进行编码，实际应用中前面 两种编码方式比较常用，下面分别讨论一下时域和频域两种编码方式。 1 r s 码的时域编码 1 ) 定义：o f ( q ) ( q = 2 “) 上，码长n = q - 1 的本原b c h 码称为r s 码。它的码元和 生成多项式的根都在o f ( q ) 上，即它是符号域和根域致的b c h 码。若口是g f ( q ) 上的本原元素，因为： x g 一一1 = 丌( x 一口) ( 2 - - 5 ) a j c g f ( g ) o 【的最小多项式m i ( x ) = - x d ，所以长为n = q 1 ，设计距离为8 的r s 码，由b c h 码 一种低误码率e f e c 算法设计与实现 的定义可知，其生成多项式为： g ( = ( 工一口“) ( x a - m o + 1 ) ( x o e , m o + 5 2 ) ( 2 - - 6 ) 其中n 】0 是整常数，m o 不同时可构成不同的生成多项式，合理地选择m o 的值，可 以降低编译码电路的复杂度。通常情况下这里选m o = 1 ，此时 g ( j ) = o a ) o - - o r 2 ) ( x - - 。) = g ，x 7 ( 2 - - 7 ) i = 0 设g f ( 2 ”) 上的k 个数据符号为d = d o ，d t ，d k - i 】表示成多项式为： d ( x ) = d o + d tx+dblxk-1(2-8) 最简单的编码是利用乘法电路，直接与生成多项式相乘，得到码多项式 “x ) ：d ( x ) g ( x ) ，但这样编出的码是非系统码，因此在解码时，要先将信息码从接 收码中选出。非系统码的编译码效率明显低于系统码，实际的应用中都是采用系 统码。 2 ) 基于多项式除法的编码器 同样对于g f ( 2 “) 上的k 个数据符号( 矢量表示) ：e = e o ，e l ，e k q ，设校验 位矢量q - 【q o ，q l ，q 操 】，则码矢量( 系统码) f = f o ，f i ，矗1 】= q o ，q l ，q t ，q 2 t qe e ，e l ，_ e k 1 】 表示成多项式： c ( x ) = q ( x ) + x “e ( x ) ( 2 9 ) 其中q ( x ) = ( x ) i x “止e ( x ) 】，即g ( x ) 除妒ke ( x ) 后的余式，记为： g ( 功= ：g 。一 ( 2 1 0 ) 它是g f ( 2 “) 上的多项式，阶数 - - - 2 t - 1 ，可知p ，就是校验位。 这样编码过程分为三步： a 预乘：x n “e ( x ) b 由除法电路求q ( x ) c 得至0f ( x ) = q ( x ) + x r , “e ( x ) 其中步骤2 ) 需要k ( n k ) 个g f ( 2 ”) 上的乘法运算。 编码结构的复杂性取决于所用的乘法器，对于并行乘法器，电路复杂度为 o ( m 2 t ) ，若采用b e r l e k a m p s 比特串行对偶基乘法器，电路复杂度可降为0 ( r o t ) ， 利用三角基得到的电路，复杂度与此相当。 2 r s 码的频域编码 如同在数字信号处理中，既可以用时域表示信号f ( t ) ，也可以使用频域来表 示，在纠错码理论中。一个码字也可以使用频域来表示。 设a 是g f ( q ) 上的本原域元素，n k 1 , n k - 2 ，, n i , n o 是信息元，n i g f ( q ) ， 0 = i = k - 1 做信息多项式： 第二章数学理论和r s 码原理 1 5 ，( 力= l z q + m 一2 x 一2 + + 工+ n o ( 2 1 1 ) 把o f ( q ) 中的q 1 个非0 元素分别代入上式， 这里定义下列g f 上的q - l 重：( f 9 2 ) ，f 一) ，f ) ，( 1 ) ) 是r s 码的频域上的一个码字，与其相应的码多项式是： c ( x ) = f 9 _ 2 n 一+ f 7 。一+ + f ( 0 。工+ f ( i ) = q x 。+ c 。一善r 3 + + c - x + c o ( 2 1 2 ) 显然，它就是信息多项式f ( x ) 的m s 多项式。码字c ( x ) p a a ，f ，( x q - k 1 为根， 但得到的r s 码是非系统码。 为了将频域上的信息符号进行编码，将前面( n k ) 个符号置为零： a = 0 ，扣0 , 1 2 ， 一最一1 ，后面k 个符号作为信息符号，进行以下的f t 运算： c f = 罗c ，0 - f = o ，1 ，尼一l ( 2 - - 1 3 ) 捌可得到时域的r s 码。 在上式中付氏变换中所需的乘法运算和多项式除法编码器中的乘法运算量相 同，不过当信息位个数k 变化时，这里只需改变c i 中寅0 的个数即可，不需对 硬件加以改变，此时这种变换编码器会更方便些。 将方程重写为： d i = ( ( d n 1c 1 + d n - 2 ) 盯+ + d i ) i x 。+ d o ( 2 1 4 ) 这样重复利用一个乘一的常系数乘法器和一个加法器，就可得到时域的码 字d i ，图2 - 1 所示为编码结构，其中用到了三角基乘法器。这一电路的优点是 它不依赖于纠错能力t 这个参数，很适合编不同速率的码。 2 4r s 码的译码原理 译码问题一直是编码理论研究中最感兴趣的课题之一。一个码能否在实际中 应用，往往取决于译码器是否简单、快速、经济和译码错误率小。 接收端收到一个码字后，如果在一个码字内发生的误码不大于t 个码元，则 可以在接收端恢复原始信息的内容。而在一个码元中，有一个或多个比特发生错 误都算一个码元错误。因此r s 码能够纠正随机错误和纠正突发错误。 r s 码的解码基本思想就是：从接收端r ( x ) 找到错误的位置和错误值，即 求得错误多项式e ( x ) ，从r ( x ) 中减去e ( x ) 就得到解码后的正确码字c ( x ) = r ( x ) e ( x ) 。r s 解码算法分为时域解码，变换域解码以及软解码。变换域解码和 软解码如果用硬件来实现过于复杂，耗费的硬件资源很大，适合软件实现。时域 解码算法具有快速，耗费资源少，控制电路小等优点。下面详细介绍本文涉及到 的时域解码算法。 1 6 一种低误码率e f e c 算法设计与实现 r s 码的译码与其它的线性分组码的译码步骤相同，基本上分为三步：第一步 是由接收到的r ( x ) 计算出伴随式s ；第二步由伴随式找出错误图样反，) ；第三步 由尺o ) 一反z ) 得到最可能发送的码字e ( ，) ，完成译码。而根据k s 码的特点，有几种 译码效率更高的专门译r s 码的译码算法出现。下面就简要介绍这几种算法。 1 欧几里得算法 从上面的讨论可以看出，r s 码的译码问题可以表述为： v 定义错误位置多项式人( 力= 丌( 1 一五x ) 和伴随式多项式 岫一i 1 + s ( x ) = 1 + s ，译码的关键是求解方程： t - i a (