（通信与信息系统专业论文）reedsolomon码在部分响应信道上的系统性能研究.pdf

重庆邮电大学硕士论文 摘要 摘要 r e e d s o l o m o n 码是2 0 世纪以来应用晟广泛的码型之一，它由麻省理工学院 ( m i t ) 林肯实验室的i s r e e d 和g s o l o m o n 于1 9 6 0 年提出。r e e d s o l o m o n 码具有优 越的纠错能力，特别是纠正突发差错的能力，因此被广泛应用于工程实践中，如卫 星通信系统、磁盘存储系统等。2 l 世纪以来，人们对存储容量的需求急剧增加，对 磁盘面密度的要求也随之大幅提高，由此带来了严重的码间干扰，降低了磁记录系 统的误码率性能。这就要求寻找一种更先进的信号处理机制以同时满足磁盘存储系 统高存储密度及极低误码率的要求。目前商业磁盘中通常采用部分响应最大似然检 测( p i m l ) 信道检测技术和基于硬判决译码算法的r s 码。近几年的研究表明r s 码 的软判决译码算法能带来更大的系统增益，这使得磁记录领域的部分研究者们将目 光转移到r s 码代数软判决译码算法上。 本文先对比分析了r s 码的硬判决译码与软判决译码的性能。硬判决译码方式 采用的是经典译码算法( b e r l e k a m p m a s s e y 算法) ，而软判决使用的是代数软判决算 法叫o e t t e r - v a r d y ( k - v ) 算法。仿真结果表明：在a w g n 信道下，f e r 为9 1 0 5 时，软判决译码较硬判决有1 ( 1 b 的性能增益。且随着码长增长，二者的性能均有所 提升。 随后，本文简单介绍了p r 信道( p a r t i a lr e s p o n s ec h a n n e l ) 特性及其检测算法， 重点研究r s 码在部分响应信道上的应用。对于两种常用的简单p r 信道，分别构建 r s 硬判决系统与软判决系统，并详细介绍了系统中各模块的功能原理及应用过程， 重点阐述各部件之间的接口处理。计算机仿真结果表明：对于p r 4 信道，在f e r 达到1 0 5 时，r s 码的代数软判决译码算法较硬判决译码算法有2 3 d b 的性能增益， 两者在p r 4 信道下均能获得优于e p r 4 信道的译码性能。此外，不论是软判决系统 还是硬判决系统，在低信噪比区域码率起主导地位，即码率越低性能越好；随着信 噪比逐渐增大，码长的影响变得更为重要，码长越长性能越好。 关键词：r e e d s o l o m o n 码，b e r l e k a m p m a s s e y 算法，k o e t t e r - v a r d y 算法，部分响应 信道 重庆邮电大学硕士论文 a b s t r a c t r e e d - s o l o m o nc o d eh a sb e e no n eo ft h em o s tw i d e l yu s e dc o d e ss i n c e2 0 t hc e n t u r y , i tw a sp r o p o s e da t19 6 0b yi s r e 。da n dg s o l o m o n , c o m i n gf r o mm i t d u et oi t s s u p e r i o re r r o r - c o r r e c t i n gc a p a b i l i t y , e s p e c i a l l yi nc o r r e c t i n gb u r s te r r o r s ，r e e d - s o l o m o n c o d eh a sb e e nw i d e l yu s e d ，s u c ha ss a t e l l i t ec o m m u n i c a t i o ns y s t e m , m a g n e t i cr e c o r d i n g s y s t e m sa n ds oo i lt h ed e m a n do fs t o r a g ec a p a c i t yi n c r e a s e sr a p i d l ya sw e l la st h e d e n s i t yo fc u r r e n tm a g n e t i cr e c o r d i n gs y s t e mi n 21s t c e n t u r y ,b r i n g i n g s e r i o u s i n t e r s y m b o li n t e r f e r e n c e , w h i c hm a d et h ep e r f o r m a n c eo f b i te r r o rr a t eb e c o m ew o r s ei n t h em a g n e t i cr e c o r d i n gs y s t e m i nt h a tc a s e ，i tr e q u i r e sam o r ea d v a n c e ds i g n a lp r o c e s s i n g m e c h n i s i u mt om e e tt h ed e m a n do fh i g hd e n s i t ya n dl o we r r o rr a t ei nm a g n e t i cr e c o r d i n g s y s t e m t h ec o m m e r c i a ld i s ks y s t e mu s e sp a r t i a lr e s p o n s em a x i m u m l i k e l i h o o dd e t e c t i o n t e c h n o l o g ya n dr sc o d e s 谢mh a r d - d e c i s i o nd e c o d i n g r e s e a r c h sh a v es h o w e dt h a tt h e s o f t - d e c i s i o nd e c o d i n ga l g o r i t h mo fr sc o d e 咖b r i n gl a r g es y s t e mg a i n , w h i c ha t t r a c t s m u c ha t t e n t i o nf r o mr e s e a r c h e r si nt h ef i e l do f m a g n e t i cr e c o r d i n gr e c e n t l y h lt h i sp a p e r , w ef i r s ta n a l y z et h ed e c o d i n gp e r f o r m a n c eo fr sc o d e sw i t ht h e c l a s s i c a lh a r d d e c i s i o nd e c o d i n gb e r l e k a m p - m a s s e ya l g o r i t h ma n dt h ek o e t t e r - v a r d y s o f t - d e c i s i o na l g o r i t h mr e s p e c t i v e l y t h es i m u l a t i o nr e s u l ts h o w st h es o f t - d e c i s i o n d e c o d i n go fr sg r e a t l yo u t p e r f o r r n a n c e st h eh a r d d e c i s i o nd e c o d i n g o v e ra w g nc h a n n e l s p e c i f i c a l l y , t h es o f t - d e c i s i o nd e c o d i n g h a sld bg a i na tf e ro f9 10 。f u r t h e r m o r e , t h e l o n g e rc o d el e n g t ht h eb e t t e rp e r f o r m a n c eo f b o t ha l g o r i t h m t h e n , t h ec h a r a c t e r i s t i c so fp a r t i a lr e s p o n s ec h a n n e l sa n di t sd e t e c t i o na l g o r i t h m si s b r i e f l yd e s c r i b e di nt h i sp a p e r , w ee m p h a s i z e so nt h ea p p l i c a t i o no f r sc o d e so v e rt h e p a r t i a lr e s p o n s ec h a n n e l s ，b u l i d i n gu pt h ec o n s t r u c to f b o t hr sc o d ed e c o d i n gw i t hh a r d d e c i s i o na n ds o f t - d e c i s i o ns y s t e mo v e rt w os i m p l ep rc h a n n e l s t h i sp a p e ri n t r o d u c e st h e d e t a i lf u n c t i o na n da p p l i c a t i o np r o c e s so fe v e r ym o d u l e , f o c u s i n go nt h ei n t e r f a c e b e t w e e nt h e m r e s u l t ss h o wt h a tt h ea l g e b r a i cs o f t - d e c i s i o nd e c o d i n ga l g o r i t h mh a s 2 3 d bo fp e r f o r m a n c eg a i no v e rh a r dd e c i s i o nd e c o d i n ga l g o r i t h mo v e rp r 4c h a n n e la t f e ro f1 0 - 5 ；b o t ho f t w od e c o d i n ga l g o r i t h mo v e rp r 4c h a n n e lo u t p 刑r ) n n a n c 髓t h a to v e r e p r 4c h a n n e l ；w h a t sm o r e , t h er a t et a k e st h ed o m i n a t ea tl o wb e r , w h i l ea th i d e rb e r t h ec o d el e n g t hp l a y sal e a d i n gr o l ei nb o t hs o f t - d e c i s i o ns y s t e ma n dh a r d d e c i s i o no n e k e y w o r d s ：r sc o d e s ，b ma l g o r i t h m , k - va l g o r i t h m , p a r t i a lr e s p o n s ec h a n n e l 重庆邮电大学硕士论文 第一章绪论 1 1 纠错编码的简史 第一章绪论 近年来，对高效可靠的数字传输和存储系统的需求日益增长，系统设计者所关 心的一个主要问题就是如何尽量减少差错以使得数据能够可靠重现。1 9 4 8 年，香农 在其具有里程碑意义的论文【l 】中曾经证明，只有信息传输速率低于信道容量，通过 对信息适当进行编码，可以在不牺牲信息传输或存储速率的情况下，将有噪信道或 存储媒介引入的差错减到任意低的程度。根据香农的思想，给出了一系列设计好码 和有效译码的方法。此后，许许多多的研究者们都致力于寻求能够逼近香农容量限 的码型，使纠错码无论在理论上还是在实际中都得到飞速的发展。 迄今，纠错码已近6 0 年的历史，其发展过程大致分为以下几个阶段e e l 2 0 世纪5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠定了线性分 组码的理论基础；提出了著名的b c h 码的编译码方法以及卷积码的序列译码；给出 了纠错码的基本码限；这是纠错码从无到有得到迅速发展的时代。 f 16 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。不仅提出许多 有效的编译码方法，如门限译码、迭代译码、软判决译码和卷积码的维特比译码等。 而且注意到纠错码的实用化问题，讨论了与实用有关的各种问题，如码的重量分布、 译码错误概率和不可检错误概率的计算、信道的模型化等。 7 0 年代初至8 0 年代，这是纠错码发展史具有极其重要意义的时期。在理论上以 戈帕为首的一批学者，构造了一类g o p p a 码，其中一类子码能达到香农在信道编码 定理中所提出的码一香农码，所能达到的性能，这在纠错码历史上具有划时代的 意义。在这期间大规模集成电路与微机的发展，为纠错码的使用打下了坚实的基础， 因而与实用相关的技术及有关问题得到了极大的关注，并在实用中取得了巨大的成 功。 二十世纪8 0 年代，戈帕等研究者从几何观点讨论分析码，利用代数曲线构造了 一类代数几何码。在这些码中，某些码的性能达到了香农码所能达到的性能。由于 代数几何码是一类范围非常广的码，在理论上已证明她具有优越的性能，因而一开 始就受到了编码理论工作者，特别是代数几何学家的重视，使代数几何码的研究得 到了非常迅速的进展，取得了许多成果。 2 0 世纪九十年代，纠错码理论日趋完善。在卷积码和级联码的基础上，提出了 t u r b o 码【3 】，其拥有独特的编码结构和新的译码方式。它在编码器中使用了反馈型的 系统卷积码，且在子编码器间引入交织器，在译码器中采用软输入和软输出的迭代 重庆邮电大学硕士论文第一章绪论 译码。该码的出现，引起了人们对迭代译码的热情关注，使得各种现代的纠错码理 论相继出现，完善了s h a n n o n 编码理论。 目前，利用纠错码降低各类数字通信系统以及计算机存储和运算系统的误码率， 提高通信质量，延长计算机无故障运行时间等。可以预料，随着科学的进步和实际 的需要，纠错码理论必将进一步的发展，它的应用范围必将进一步扩大。 1 2r e e d s o l o m o n 码的历史与发展状况 r e e d s o l o m o n ( r s ) 码是一种有很强纠错能力的代数几何码，它首先由里德( r e e d ) 和所罗f 1 ( s o l o m o n ) 于1 9 6 0 年提t 4 1 。r s 码的发展的过程如下： 二十世纪六十年代，二进制b c h 码的第一种译码算法由彼得逊( p c t e r s o n ) 于 1 9 6 0 年提出，从理论上解决了二元b c h 码的译码问题，奠定了b c h 码译码的理论 基础。稍后戈雷( g o r e ) 和齐勒儿( z i e d 神把此译码推广到多进制的b c h 码。r s 码是 多进制b c h 码的一个子类，从而在r s 码中使用彼得逊的算法。所以在r s 码中这 种算法称为p g z ( p e t e r s o n - g o r e z i 耐神算法。这种算法在理论上理解容易，但在实 际运用中，由于使用大量的矩阵的运算，复杂度很高。伯利坎普( b c r l c k a m p ) 于1 9 6 6 年提出了一种有效地降低b c h 和r s 码复杂度的解码方法【5 】，该方法实现比较简单， 且易用计算机完成译码。他与彼得逊在该算法中使用迭代方式，提高r s 码的纠错 能力，使r s 码可以同时纠正多个字节的错误。梅西( m a s s e y ) 贝j j 在1 9 6 9 年指出伯利 坎普的迭代译码算法【6 】等同于找到一个能生成给定序列的最短的线性移位寄存器， 从而对此算法进行了简化。此算法被称为b e r l e k a m p - m a s s e y 算法，简称b m 算法， 该算法进一步提高了译码的效率。 二十世纪七十年代，s u g i y a m a ，k a s a h a r a ，h i r a s a w a 和n a m e k a w a i t t 明，用于寻 找两个多项式的最大公因式的提出了欧几里德( e u c l i d ) 算法，且证明欧几里德算法能 有效地对b c h 码、r s 码和g o r n ， 7 , 8 】进行译码。 二十世纪八十年代，i 扫w e l d 痢b e r l e k a m p 提出了一个算法，此算法中的关键方 程不用计算伴随式，只依赖于余式和生成多项式，从而在很大程度上降低了算法的 复杂度。此算法被称为余式译码算法也称为w e l d 卜b d e k 距l p 算法【9 】，简称w b 算法。 二十世纪末，g u r u s w a m i 和s u d a n 提出了一种代数列表译码算法，该算法引进了 曲线拟合的方法，改善了r s 码的硬判决译码，被称为g s 算法【l o 】。此算法能够超越 r s 码硬译码半径，提高了译码的性能。该算法的提出为r s 码的软译码出现创造了条 件。 二十一世纪初，在g s 算法的基础上k b e 位e f 和v a r d y 提出了一种代数软判决译码 2 重庆邮电大学硕士论文第一章绪论 算法，被称为k - v 算法【l l 】。此算法在性能上比硬判决算法有着明显的系统增益，从 此r s 码的研究进入了软判决译码算法。此后，g a u s s 算法【1 2 】，w a t e r f i l l i n g l i k e - 算法【1 3 】， c h e m o f t 算法【1 4 1 ，a b p 算法【1 5 】，分解译码【1 司以及各种级联型的r s 码软判决译码算法 不断出现。这些r s 码的软判决译码算法在性能上都越来越好，但复杂度也越来越高， 在实际运用中软判决都由于其复杂度过高，没有被采用。 由于其优越的纠错能力，特别是纠突发差错的能力，r e e d s o l o m o n 码被广泛应 用于工程实践中。如数据存储系统( 硬磁盘驱动器、c d 、d v d 等) ，消费电子系统( 数 字电视、数字音频、数字图像等) ，数字通信系统( 卫星通信、深空探测、a t s c 、d a b 、 d w 3 ) 等。不同码字形式的i 峪码在实际应用的具体情况如下：在硬盘驱动器主要使 用的是r s ( 3 2 ，2 8 ，5 ) 码；在c d 中使用是交叉交织i 峪码；在d v d 中使用r s ( 2 0 8 ，1 9 2 ，1 7 ) 码和r s ( 1 8 2 ，1 7 2 ，1 1 ) 码乘积码；在d a b 与d v b 系统中使用外码为r s ( 2 0 4 ，1 8 8 ，1 7 ) 码，内码为卷积码的级联码：在a t s c 中使用内码为卷积码，外码为r s ( 2 0 7 ，1 8 7 ，2 1 ) 码的级联码；在深空通信中使用内码为卷积码、外码为r s ( 2 5 5 ，2 2 3 ，3 3 ) 码的级联码； 在光纤通信中使用r s ( 2 5 5 ，2 3 9 ，17 ) 码。 r e e d s o l o m o n 码优秀的性能，严谨的代数结构，使得人们一直对它进行研究。 i 峪码被提出不久，b e r l e k a m p 和m a s s e y 提出了b m 算法，它是一种基于快速查找 错误位置多项式的r s 硬判决译码方式，它易于实现但译码性能较差。然而，近十 年来，随着通信技术的进步，越来越多的通信系统设计者开始摒弃r s 硬判决译码。 原因很简单，软判决译码相对于硬判决译码能够提供更大的译码增益。然而r s 码 缺乏简单有效地软译码算法，无法提供软判决增益的r s 码在a w g n 信道下的性能 完全不如卷积码，更不要说当今的宠儿t u r b o 码和l d p c 码。更让人失望的是， g u m s w a m i 和v a r d y 证明r s 码的最大似然译码( m a x i m u ml i k e l i h o o d ) 是一个n p - h a r d 问题。 在实际中r s 码仍然有着广泛应用，人们通过理论分析隐约看到r s 码软判决译 码的巨大潜力，它也许是不逊于任何纠错码的。因此，研究者们开始致力于挖掘这 种码的内在潜力，目的在于为它设计较有效的软译码算法。由此提出了利用软信息 译码的软判决译码算法，可以获得较大的系统增益。 1 3 论文研究的目的、方法与意义 在现今信息时代，呈爆炸式增长的数据量使得对磁盘存储系统的容量需求越来 越大。在相同的盘片尺寸下，更大的容量就对应着更高的存储密度，由此带来的严 重码间干扰降低了系统性能。r s 码作为现有磁盘存储系统中纠错码的工业标准，已 3 重庆邮电火学硕士论文第一章绪论 经渐渐不能适应未来磁盘存储系统对纠错码更高编码增益的要求。本论文对r s 码 代数软判决译码展开研究，以期能进一步挖掘r s 码的性能增益，增强其生命力。 磁盘存储系统首先要保证数据读取的可靠性，之后才去追求高存储容量与快速 存取，以及价格便宜和使用简易等方面。目前，磁记录中常采用p r m l 技术【l s 】对信 道进行检测以减轻或消除码间干扰带来的影响，其实质是将均衡器输出的具有较短 i s i 的p r 信号送入v i t e r b i 检测器，并将维特比检测器输出的硬判决信息直接馈入到 硬判决r s 码译码器以构成级联系统。该方案译码性能好、运算复杂度低且易于硬 件实现，广泛应用于当前的磁盘存储工业标准中。近几年出现的一些研究表明软判 决译码算法能带来更大的系统增益，使得磁记录研究者将目光转移到r s 码代数软 判决译码上【1 蛆1 1 。信道检测器则采用具有软信息输出的b c j r 算法或其改进算法来 获得r s 码软判决译码器所需要的输入软信息，并将译码器输出外信息反馈到信道 检测器以构成t u r b o 均衡，从而进一步提高系统性能。 本文研究了r s 码在部分响应信道上的应用。分别构建了维特比检测与r s 硬判 决译码算法的硬判决系统和由b c j r 检测算法与k - v 软判决r s 译码算法构成的软 判决系统。通过对比研究，以期从性能以及复杂度两个层面寻求到相比现有磁盘系 统中的检测与纠错机制更具竞争力的解决方案，以进一步增强r s 码在磁盘存储系 统中的生命力。 1 4 论文的结构 本文重点研究了r s 码在部分响应信道中的应用。在p r 信道下分别构造基于 r s 码的硬判决系统和软判决系统，对比分析两种系统的特点与性质。 第一章简述纠错码发展历史及其背景，重点介绍r s 码由其诞生到目前发展现 状，最后阐述磁盘中r s 码的研究背景及其意义并给出全文的具体安排。 第二章详细介绍了研究纠错码的数学基础，主要是代数中的某些有关基本知识， 涉及近世代数一些概念与性质，它是研究码字的生成、编译码方法及其性能特点的 基础。后续介绍纠错码的基本理论、概念及其性质，最后着重介绍了几种典型的纠 错码编译码方式。 第三章首先简述b c h 码的基本原理，从而引出作为其重要子类的r s 码。继而 从r s 码时域编码与频域编码两个角度详述其编码原理，然后重点介绍r s 码经典硬 判决译码算法- b m 算法，仿真分析其性能并给出相应的结论。 第四章着重介绍了r s 码的代数软判决译码典型算法- k v 算法。首先阐述 软信息的概念，然后介绍k - v 算法的基础g 。s 译码算法原理，详述并分析g - s 4 重庆邮电大学硕士论文 第一章绪论 算法中的插值运算与因式分解运算的过程，在此基础上分析k - v 算法。 第五章简单介绍了部分响应编码信道的原理及其对应的检测方案。针对r s 码 两种译码方式分别介绍了部分响应信道的维特比算法与b c j r 算法检测。 第六章，构造了r s 码在p r 信道中两个模型。分别是p r 信道下的硬判决系统 与软判决系统，分析每个系统构造过程，以及作用。 第七章是本文结论以及展望。 5 重庆邮电大学硕士论文第二章近世代数与纠错码基本原理 第二章近世代数与纠错码基本原理 纠错码其数学基础是近世代数，它是研究纠错码编译码方法及其性能的基础。 本章首先介绍一下近世代数的一些概念与性质 2 2 1 ，然后对多项式进行分析，主要分 析伽罗华域的扩域构造的方法。而后对纠错码的概念、性质及其基本理论做简要阐 述，最后分别介绍分组码与卷积码的相关概念与性质。 2 1 近世代数基本概念与性质 2 1 1 群、环、域 令g 为一组元素的集合。二元运算宰定义为一种规则( 这里的宰泛指任一种代数 运算，如+ ，模m 加，模m 乘等) ，若满足： 1 有封闭性，即v a ，b g ，3 ( a 宰6 ) = c g 。 2 宰满足结合律，即v a ，b g ，了口奉( 6 宰c ) = ( 口宰6 ) 枣c 。 3 g 中包合e ，使得g 中任意元素a ，有矿e ：e 幸a _ a ； 4 存在另一个元素a ，满足a * a = e 。 则称这样的代数系统为群，记做( g 宰) 【2 2 1 。 如果群满足交换律，则称为交换群或者阿贝尔群。如果群( g 毒) 中包含无数个元 素，则乘该群为无限群。如果群( g 宰) 中包含有限个元素，则乘该群为有限群。构成 有限群的元素的个数称为该群的阶。 群的定理阎如下： 定理2 1 群g 的单位元是唯一的。 定理2 2 群中每个元素的逆元是唯一的。 定理2 3 令g 为二元运算幸下的一个群，h 为g 的一个非空子集。那么如果满 足下面条件，则h 是g 的一个子群：h 在二元运算木下是封闭的；h 中的任一元素 a ，a 的逆元也在h 中。 定理2 - 4 令h 为群g 在二元运算毒下的一个子群，则h 的陪集中任意两个元素 互不相同。 定理2 5 对群g 的子群h ，其任意两个不同的陪集之间没有相同的元素。 定理2 - 6 设g 为一个n 阶群，h 为一个m 阶子群。则m 可以整除1 1 ，且划分 g h 由n m 个h 的陪集构成。 6 重庆邮电大学硕士论文 第二章近世代数与纠错码基本原理 对于非空元素的集合r 以及定义在r 上的乘、加两种运算，如满足以下3 个条 件： 1 集合r 在加运算下可构成加群( r + ) 。 2 集合r 在乘法运算下满足群的前三个条件，即封闭性、结合性及单位元存 在性( 这里由于少了乘法交换律而不构成乘群。因为既然是加群( k + ) ，r 中必然含有 零元素，而0 不存在乘法运算下的逆元) 。 3 分配律，即v a ，b ，c r ，3 a ( 6 + c ) = a - 6 + a c ( 6 + c ) 口= 6 口+ 6 c 。 则该代数系统为环，记做( 凡+ ，) ，简称为环r 。 一种具有很强聚合力的子环叫做理想子环。理想子环的充要条件是：若r 是交 换环，i 是r 的非空子集，如满足v a ，b i ，b a b ，；v a ，r ， j 口，= ，a i 则i 是r 的理想子环，简称理想。 若理想子环的所有元素可由一个元素口的各次幂的线性组生成，则称该理想子 环为主理想子环，简称主理想，元素口称作生成元。 令f 为一组元素的集合。其上定义“+ ”，“妒。若： 1 f 关于加法构成阿贝尔群，存在加法单位元记为0 。对f 中存在任意元素b ， 有a + b - - 0 ，则a 为b 的负元素。 2 f 中非零元素全体对乘法满足交换群，存在单位元记为1 。对f 中存在着任 意非零元素b ，有a b = 1 ，则a 为b 的逆元素。 3 满足分配律：x ( y + z ) = - x y + x z 、z ) x = y x + 及 则该代数系统称为域【2 2 1 。域与环的关系如下：对于至少含有一个非零元素的交 换环f ，若每个非零元素都存在乘运算下的逆元，则称该交换环为域，记做但+ ，) ， 简称域f 。 域的性质如下：对域中任一个元素x ，有x 0 = o - x = 0 ；对域中任意两个非零元素 x 和y ，有x y 0 ；x y = 0 且x 4 - o ，则b - - = o ；对域中任意两个元素x 和y ，有 一 y ) = ( _ 功y - - x ( 一y ) ；当x 0 且x y - - - - x z ，则y 吃。 2 1 2 多项式剩余环 含有一个未定元数x 的域f p ( g f q ) ) 上的多项式定义为： ( 功= z x 4 + z _ 1 x 4 - 1 + + 石x + f o ，1 、 其慨c i = 0 , 1 ，2 ，刀 p v 且用f p x 】( 或g f o ) 【x 】) 表示系数取自域f 止的一切多项式集合。 多项式次数是系数不为零的x 的最高次数为多项式蕾【x ) 的次数，记为 a 。厂( 功( a 。力或d e g f ( x ) ( d e g j r ) 。最高次数系数为1 的多项式称为首一多项式。当埘 7 重庆邮电大学硕士论文第二章近世代数与纠错码基本原理 是次数大于零的多项式，若除了常数与本身的乘积以外，再不能被域f p 上的其它多 项式除尽，则称妇& ) 为域f 。上的既约多项式。 每一个首一多项式取) 必可分解为首一既约多项式之积，并且当不考虑因式的 顺序时，这种分解是唯一的，即 厂( x ) = a ( x 严a ( 矿p a x ) q( 2 2 ) 式中，p i ( x ) 为首一既约多项式，是某一正整数，i = l ，2 ， s 。 2 1 3 伽罗华域及其扩域 域中的元素个数为有限个则称为有限域，也叫g a l o i s 域。对于由一个素数p 构 成的域称为素域，记作g f ( p ) 。可以将g f ( p ) 构造成g f q m ) 的扩展域，其中的m 为 非零整数。当p = 2 时，就是二元域g f ( 2 ) ，则g f ( 2 m ) 为其扩域。有限域中的定理如 下： 定理2 - 7 有限域的特征值a 是一个素数。 定理2 8 设防为有限域g f ( q ) q b 的一个非零元素，则口g - 1 = 1 。 定理2 - 9 设口为有限域g f ( q ) 中的一个非零元素，n 为口的阶，则n 必能整除 q - 1 。 定理2 1 0g f ( 2 ) 上的任意m 次不可约多项式整除x 2 舟1 + 1 。 下面举例构造g f ( 2 ) 的扩域： 由g f ( 2 ) 构造g f ( 2 m ) ，除了含有元素0 和l ，引进元素t ；t 。得到一个由( 0 ，l ， 口) 作乘法运算的的非空集合： f = ( o ，1 ，口，口2 ，aj ，) ，其中口咆l 为了使其成为有限域，施加条件使其要满足乘法的封闭。关键的问题是f 中的 元素变为2 m 个，除去一个0 元素，那么从而我们可知最大项为口2 一，根据乘法的 性质，如果口2 一= 1 ，即满足条件。则集合f 变为有限集合可以改写为： g f ( 2 ”) = o ，( ；t o ，t t c l ，口2 ，口2 。2 根据口2 一= 1 ，可得： g f ( 2 ”) = o ，口o ，口1 ，口2 ，口2 。2 从而可知在g f ( q ) 中，每一个非零元素都满足方程x q - 1 = 1 ，都是x q - t 1 = 0 方程的 根，可知在乘法上是封闭的。下一步要定义一个f 上的加法运算“+ ，使得f + 在 “+ 下构成一个交换群。 在有限域g f ( 2 m ) 中的任一个元素都可以由一个多项式表示，多项数的阶数不大 于m - 1 次。阶数为多项式的最高幂指数。例如将g f ( 2 m ) 中非0 元素口。( 功用多项式 来表示： 8 重庆邮电大学硕士论文第二章近世代数与纠错码基本原理 口= 口，( 功= q ，o + q ，l x - 4 - a f ，2 x + 4 - a i ，。一x ”- 1 ，其中i = o ，l ，2 ，2 m - 2 从式中x 用o r 代换，可以看出f 中的2 1 1 个非零元素口。口1 口2 。_ 2 可用g f ( 2 ) 上的2 m - 1 个饼的m 1 次或更低次的互异非零多项式表示。现在定义f 上的加法“+ 如式2 3 所示： 口+ 口7 = ( 口印+ a j ，o ) + ( q ，l + 口”) 货+ + ( q 。m l + a j ，。4 ) 口”_ 1 ( 2 3 ) 集合f 在公式2 1 9 定义的“+ 下是封闭的。因此f 名( o ，1 ，口，口2 ，口2 i - 1 ) 是一个含有2 m 个元素的伽罗华域g f ( 2 m ) 。注意伽罗华域是模2 加法与乘法。 设m = 4 ，多项式p 0 0 = l + 删是g f ( 2 4 ) 能j - 个本原多项式。本原多项式定义 是m 次不可约多项式p c p 满足p ( x 3 整除) p i + 1 的最少正整数1 1 为n - 2 m 1 。则 p ( a ) = 1 + 口+ 口4 = o ，即口4 = 1 + 口( 模2 加) ，用这个关系式可以构造g f ( 2 4 ) 。 比如： 口5 = 口口t 口( 1 + 口) = 口+ 口2 口6 = 口口5 = 口( 口+ 口2 户口2 + 口3 口7 = a t 口6 ：= 口( 口2 + 口3 ) = 口3 + 口4 = l + a + t t 3 口8 = 口口7 = 口( 1 + 口+ 口3 ) = l + a 2 口1 5 _ 岱7 仿8 = ( 1 + 口+ 口3 ) 木( 1 + 口2 ) = l = c t 即域中只有1 6 个元素为( o ，1 ，口，口2 口1 4 口1 5 ) ，域中也可以用 q ，。+ 口m o r + a ，2 口2 + + 口枷一l 口”_ 1 为一个元素p 多项式表示，或者我们可以用p 表示为m 个元素的有序序列，称之为m 维向量。 由p 0 0 = 1 + ) ( + x 4 生成的g f ( 幻的元素有三种表示方法如表2 1 ： 表2 1g f ( 2 4 ) 的元素表示方法 幂表示多项式表示4 维向量表示 oo0 0 0 0 ll1 0 0 0 口口o l o o 本 口2口2o o l o 原 口3口30 0 0 l 多 口4l + 口1 1 0 0 项 口5口+ 口20 1 1 0 式 口6口2 + 口30 0 1 1 p ( ) ( ) 口7l + 口+ 口3 1 1 0 1 的 口8l + t z 2 l o l o 9 重庆邮电大学硕士论文第二章近世代数与纠错码基本原理 域口9口+ 口30 1 0 l 元 口l o1 + 口+ 口21 1 1 0 素口“口+ 口2 + 口30 ll l 口1 2 l + a + 口2 + 口3 1 1 1 1 口1 31 + 口2 + 口3 1 0 11 口1 4 l + a 3 1 0 0 1 g f ( 2 m ) 算术的简单举例如下： 在g f ( 2 4 ) q b 解下面的线性方程组： fx + 口7 y = 口2 i 口1 2 r + 口8 y ：口4 利用克莱姆法则来解方程组： f 口2 口7 l 肛陶=筹|g+919=了a,141 甜 l口7 l 及口5 i 口1 2口8 i l1口2 l 咋1 矧= 筹= 等纠 l口7 l 口8 + 口碍口5 l 口1 2口8 i 2 1 4 矢量空间 令v 是一个定义了二元运算加法“+ 的集合，f 是一个域。在f 中的元素和 v 中的元素之间定义一个乘法运算，记为。若： 1 v 对于加法是一个交换群； 2 对f 中的任意元素a 和v 中任意元素v ，a - v 是v 中的元素； 3 对v 中的任意元素u 和v 及f 中的任意元素a 和b ，a 0 + 1 ，) = a u + a 1 ， ( 口+ 6 ) v = a v + b ，； 4 对任何v v 和任意a ，b e f ，0 6 ) 1 ，= a ( 6 d ； 5 设1 为f 的幺元，则对任意v v ，1 v = v 。 满足上面的五个条件，则称集合v 为域f 上的一个向量空问。 向量空间的性质如下： 性质l 设o 为域f 的零元，则对v 中的任意向量v ，0 v = o 。 1 0 重庆邮电大学硕士论文第二章近世代数与纠错码基本原理 性质2 对f 中的任意标量c ，v - 0 = 0 。 性质3 对f 中的任意标量c 和v 中的任意向量v ，且( - c ) v - c 卜，) = 一( c d 。 2 2 纠错码的基本理论 只有码率少于信道容量，信息就可以通过信道可靠的传播。根据香农的第二定 理我们可以得到信道编码定理：对于离散无记忆的信道，小于信道容量c 的所有码 率都是可达的。具体的说，对任意码率r ，j = o ，1 ，l 一1 ， j = 1 ，n - k 。 2 ) 找出各根对应的既约多项式r l m 1 ( 】【) ，r 2 _ m 2 ( x ) ，r nk n l n 1 舡) 。 3 ) 求出这些既约多项式的最少公倍式：g ( x ) = l c m m l ( x ) ，m 2 ( x ) ，咄) 】。 循环码的译码与线性分组码一样可以分为三个步骤： 1 ) 计算r ( x ) 的伴随式s ( x ) ； 2 ) 根据伴随式s ( x ) 找出估计错误图样应( x ) ； 3 ) e = 尺( 功一雪( 功得到译码器输出的估值码e ，并送出译码器给用户。若e ， 则译码正确，否则译码错误。 2 3 2 卷积码 卷积码是1 9 5 5 年由爱里斯提出的【2 7 】，由3 个整数n ，k ，k 描述，这里的k n 也表示分组码的编码效率；但1 1 和分组码时不一样，不再表示分组码时不一样，不 再表示分组或码字长度，k 为约束长度，表示在编码移位寄存器中k 元组的级数。 卷积码不同于分组码的一个重要特征就是编码器的记忆性，即卷积编码过程产生的 n 元组，不仅是输入k 元组的函数，而且还是前面k - 1 个输入k 元组的函数。 卷积码与分组码不同的是，卷积码编码中，本组的校验元不仅与本组的信息元 有关，而且与以前各时刻输入至编码器的信息组有关。同样，译码提取译码信息也 要利用以前或者以后各时刻收到的码组中提取的信息。此为每组码元的信息位长度 和码长通常都要比分组码的要小。因此在相同的码率和设备复杂性条件下可以获得 比线性分组码更高的编码增益，但是这种相关性同时也增加了分析和设计卷积码的 复杂性。因此至今仍未找到像分组码那样有效的数学工具，而且往往要借助计算机 来搜索好码。但卷积码有三种比较好的译码方法：梅西提出的门限译码：w o z c n c r a i t 提出由f a n o 改进的序列译码；维特比算法译码【2 s 】。 1 5 重庆邮电大学硕士论文第二章近世代数与纠错码基本原理 卷积码的差错分布有其特点：分组码的一个差错只影响一个码组，卷积码的一 个差错却要影响一个序列。对于分组码而言，可以从码字的差错开始讨论码元的差 错、比特的差错；而对于卷积码，必须从序列的差错开始才能进行讨论码字、码元 和比特的差错。一旦译码错误，分组码只错一个码字而卷积码错一个序列。 卷积码译码的基本思想是：以断续的接收码流为基础，逐个计算它与其他所有 可能出现的、联系的网格图路径的距离，选出其中可能性( 概率) 最大的一条作为译 码估值输出。概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的 正是最大似然的准则。 2 3 3t u r b o 码 t u r b o 码，又称并行级联卷积码，是由c b e r r o u 等在i c c 9 3 会议上提出的。它 巧妙地将卷积码和随机交织器结合在一起，实现了随机编码的思想；同时，采用软 输出迭代译码来逼近最大似然译码。t u r b o 码的编码器是由两个反馈的系统卷积码 编码器通过一个随机的交织器并行连接而成的，编码后的校验位经过删余阵，从而 产生不同码率的码字。 图2 1t u b r o 码编码器结构框图 t u r b o 码译码器采用反馈结构，以迭代方式译码。译码器包含两个独立的子译 码器，分别为d e c l 和d e c 2 。均采用软输入软输出的迭代译码算法。根据d e c l 和d e c 2 连接方式不同，可以分为并行译码与串行译码。子译码器d e c l 先对分量 码编码器进行译码，把译出的比特似然比信息当做外信息，经过交织，送给予译码 器d e c 2 当作先验信息，进行最佳译码。该译码器得到的没比特的似然比信息，经 过借交织，当作子译码器d e c l 的先验信息，进行译码。重复这个过程，经过多次 迭代，使两个子译码器的外信息都趋于稳定。对此外信息进行硬判决，得到的就是 译码信息。 t u r b o 译码的基本原理【2 9 】：使用m a p 算法对信息符号进行迭代估计，其输入包 括从前次译码迭代之后所有统计独立的信息中获得的逐次更新的先验l 值。 1 6 重庆邮电大学硕士论文第二章近世代数与纠错码基本原理 2 4 本章小结 本章主要介绍两部分概念，第一部分分析了纠错码的数学理论基础包括群、环 和域的基本概念与性质。着重介绍了伽罗华域的相关概念与性质，及其扩域的构造 过程。第二部分阐述了纠错码的原理及其性质，从纠错码的定义到纠错码的性能， 分析其主要码字的特点。简单介绍包括线性码、卷