（通信与信息系统专业论文）rs码软判译码技术的研究.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学、通信与信息系统 研究方向：移动通信与无线技术 作者：2 0 0 7 级硕士研究生吴祖义 指导教师：酆广增教授 题目：r s 码软判译码技术的研究 英文题目：t h er 懿o e a r e ho i ls o f td e c i s i o nd e 啦t e c h n i q u e so fr e e d - s o l o m o n c o d e s 关键词：r s 码；软判决译码；球型译码；自适应置信度传播；级联译码 算法 k e yw o r d s ：r e e d - s o l o m o nc o d e s ；s o t td e c i s i o nd e c o d i n g ；s p h e r ed e c o d i n g ； a d a p t i v eb e l i e fp r o p a g a t i o n ；c o n c a t e n a t i o nd e c o d i n ga l g o r i t h m s 摘要 r s ( r e e d s o l o m o n ) 码是一种优秀的码，广泛应用于移动通信、卫星通信、磁记录设 备以及数字音频和视频传输等领域。r s 码不仅能够纠随机错误，而且以它较强的纠突发错 误的能力而著称。正因此，r s 码的译码成为关注的焦点。目前实际应用中使用的译码方法 一般为硬判译码，r s 码的硬判译码及编码算法被视为代数理论与工程实现的完美结合。 尽管如此，硬判译码由于没有充分利用信道输出的软信息而损失一定的译码增益。因 此能否提出译码性能较好同时也便于工程实现的软判译码算法对r s 码的未来更加广泛的 应用是一个考验。所幸的是，已经有很多关于r s 码的软判译码算法被相继提出。 正是在此背景下，本文着力于r s 码软判译码算法的研究。本文首先阐述并讨论了目 前主流的r s 码非级联的软判译码算法。如k o e t t e r 和v a r d y 提出的代数软判决( a l g e b r a i c s o f td e c e s i o n ) 译码算法，j i n gj i a n g 和n a r a y a n a n 提出的自适应置信度传播译码( a d a p t i v e b e l i e fp r o p a g a t i o n ) 算法等与此同时，在非级联软判译码算法中，我们详细讨论了一种最 新提出的称为球型( s p h e r ed e c o d i n g ) 译码的译码算法 本文在讨论了非级联软判译码算法之后，也简要讨论了目前几种主流的r s 码级联软 判译码算法这些级联译码算法能够提供更好的译码性能。正是受这些级联译码算法的启 发，本文最后详细讨论了本人合作提出及独立提出的两种级联译码算法：a b p - c h a s e 及 a b p s d 。其中，a b p c h a s e 译码算法是软判算法a b p 与c h a s e 算法的级联算法。a b p - s d 算法是由a b p 与s d 的级联译码算法。 经过在统一的仿真平台上仿真并与目前主流的各种软判译码算法进行比较，我们发 现，a b p c h a s e 、a b p s d 均能够提供较好的译码性能，取得译码性能和复杂度之间更好 的折中。 a bs t r a c t r s ( r e e d - s o l o m o n ) c o d ei sak i n do fp e r f e c tc o d e ，w h i c hi sw i d e l yu s e di nm o b i l e c o m m u n i c a t i o n , s a t e l l i t ec o m m u n i c a t i o n , m a g n e t i cr e c o r d i n gm e d i a , d i g i t a la u d i oa n dv i d e o t r a n s m i s s i o ne t c r sc o d ec a nc o r r e c tn o to n l yr a n d o me r r o r s ，b u ta l s ot h eb u r s t 睨姗w i t h s t r o n gc a p a b i l i t y h e n c e ，t h ed e c o d i n go fr sc o d eb e c o m e so n eo ft h eh o tt o p i c so f r e s e a r c h i n a c t u a la p p l i c a t i o n ，t h eh d df f l a r dd e c i s i o nd e c o d i n g ) a l g o r i t h mi su s u a l l yt h em a i nd e c o d i n g m e t h o df o rt h er sc o d e s t h eh d d a l g o r i t h ma n dt h ec o d i n gm e t h o do fr sc o d ea r ec o n s i d e r e d a sp e r f e c tc o m b i n a t i o no ft h ea l g e b r a i ct h e o r ya n dt h ee n g i n e e r i n gr e a l i z a t i o n n e v e r t h e l e s s ，t h e r ei sal o to fd e c o d i n gg a i nl o s sb e c a u s et h eh d d d o e s n tf u l l yu s et h es o f t i n f o r m a t i o n s d d ( s o f td e c i s i o nd e c o d i n g ) s h o u l db eap r o m i s i n gd e c o d i n ga l g o r i t h mf o rr s c o d e sw i t hb e t t e rp e r f o r m a n c e sc o m p a r i n gt oh d d i ti sf o r t u n a t e l yt h a ti nr e c e n ty e a r sm a n y s d dm e t h o d sa r ep u tf o r w a r d u n d e ra b o v eb k g r o u n d , t b i st h e s i si n v e s t i g a t e st h es d d a l g o r i t h m so f r s c o d e a tf i r s t t h em a i nn o n 口吼n c a k m 撕o ns d da l g o r i t h m so fr sc o d ea r ei n t r o d m 湖i nt h i s t h e s i s , s u c ha st h ea s d ( a l g e b r a i cs o ri ) e c i s i o n ) a l g o r i t h mi n v e n t e db yk o e t t e ra n d 呐；f i l e a b p ( m a p t i v eb e l i e fp r o l m g a f i o n ) a l g o r i t h mi n v e n t e db yy m gj i a n ga n dn a r a y a n a n , 哟c i nt h e n o n - c o n c a t e n a t i o nd e c o d i n ga g o r i t h m s ，w em a i n l yd i s c u s st h es d ( s p h e r ed e c o d i n g ) a l g o r i t h m w h i c hi sn e w l ys u b m i t t e d a f t e rt h i s ，w ew i l ls w i t c ho u rr e s e a r c ht oc o n c a t e n a t i o ns d dd e c o d i n ga l g o r i t h m so fr s c o d ew h i c hc a np r o v i d eb e t t e r 曲r f o r m a n c et h a nn o n - c o n c a t e n a t e ds d d e n l i g h t e n e db yt h o s e e x i s t e da l g o r i t h m s ，a tt h el a s tc h a p t e ro ft h i st h e s i s ，w ep r o p o s et w on e wc o n c a t e n a t i o na l g o r i t h m ： a b p - - c h a s ew h i c hi st h ec o n c a t e n a t i o no fa b pa l g o r i t h ma n dc h a s ea l g o r i t h ma n da b p - s d w h i c hi st h ec o n c a t e n a t i o no fa b pa n ds d s i m u l a t i o nr e s u l t ss h o wt h a tt h ep e r f o r m a n c e so f t h e s et w on e wc o n c a t e n a t e ds d da l g o r i t h m sa r es u p e r i o rt h a nc o n v e n t i o n a la l g o r i t h m s t h e y c a ng a i nb e t t e rt r a d e o f fb e t w e e nt h ed e c o d i n gp e r f o r m a n c ea n dt h ed e c o d i n gc o m p l e x i t y k e yw o r d s ：r e e d s o l o m o nc o d e s ；s o f td e c i s i o nd e c o d i n g ；s p h e r ed e c o d i n g ； a d a p t i v eb e l i e fp r o p a g a t i o n ；c o n c a t e n a t i o nd e c o d i n ga l g o r i t h m a b p a l l r a s d k n g 憾 b c h b d d b e r b m b m a b p c b c g a f e r g f g d g s h d d k v l r b m l d m r b o s d s d d r s s d 缩略语词汇 l l s i o fa b b r e v i a ：i l o n s a d a p t i v eb e l i e fp r o p a g a t i o n 自适应置信度传播 a c c u m u l a t e dl o g l i k e l i h o o dr a t i o累积对数似然比 a l g e b r a i cs o f td e c i s i o nd e c o d i n g 代数软判决译码 a d d e dw h i t eg a u s s i a nn o i s ec h a n n e l加性高斯白噪声信道 b o s e ，c h a u d h u r i & h o e q u e n g h e mt y p eo f 博斯一乔赫里- 霍克文黑姆 c o d e码 b o u n d e dd i s t a n c ed e c o d i n g限定距离译码 b i te r r o rr a t i o误比特率 b e r l e k a m p - m a s s e yb m 译码算法 b o xa n dm a t c h d e c o d i n g 盒匹配译码算法 b e l i e fp r o l m g a t i o n置信度传播 c o n t r o lb a n d控制带 c h a s e - l lg m d 测o n a l g o r i t l m ac h a s e - i i 与g m d 的级联 算法 f r a m ee r r o rr a t e误帧率 g a l o i sf i e l d g e n e r a lm i n i m u md i s t a n c ed e c o d i n g o u m s w a m i s u d a n h a r dd e c i s i o nd e c o d i n g k o e t t e r - v a r d y l e a s tr e l i a b l eb i t s m a x i m a ll i k e l i h o o dd e c o d i n g m o s tr e l i a b l eb i t s o r d e r e ds t a t i s t i c sd e c o d i n g s o rd e c i s i o nd e c o d i n g r e e d s o l o m o n s p h e r ed e c o d i n g i 伽罗华域 广义最小距离译码 g s 译码算法 硬判决译码 k v 译码算法 最不可靠比特信息集 最大似然译码 最可靠比特信息集 分阶统计译码 软判决译码 里德所罗门 球型译码 s e r s m o s i s ；0 帆 、e r s y m b o le r r o rr a t e s o i l - i n p u th a r d - o u t p u t s o f t i n p u ts o f t - o u t p u t s i g n a ln o i s er a t i o w b r de r r o rr a t e i v 误符率 软输入硬输出 软输入软输出 信噪比 码字错误概率 目录 摘i l 兽i a b s t r a c t i i 缩略语词汇i 目录v 第一章绪论1 1 1 纠错码的发展概况。1 1 2r s 码的发展与现状j 2 1 3 本课题意义3 1 4 本文工作及章节安排一4 第二章r s 码基本知识5 2 1 、伽罗华域代数基础5 2 1 1 群、域简介 2 1 2 有限域基本概念 2 13 扩展域g f ( 矿) 中的加法和乘法 2 1 4 有限域的本原多项式 5 6 7 7 2 2r s 码基础8 2 2 1 概述8 2 2 2 多元b c h 码与r s 码9 2 2 3r s 码的码重分布l0 2 2 4r s 码的译码性能1 1 2 3 本章小结1 3 第三章r s 码硬判译码算法1 4 3 1r s 码的硬判决译码算法发展历史1 4 3 2r s 码的伴随式译码算法。1 5 3 2 1r s 码的伴随式译码的译码原理：1 5 3 2 2 计算伴随式1 7 3 2 3 求解关键方程1 7 3 2 4 求错误位置1 9 v 3 2 5 求错误值2 0 3 3r s 码的列表译码算法。2 0 3 4 本章小结2 2 第四章r s 码非级联软判译码算法2 3 4 1 概述2 3 4 2 各种非级联软判译码2 4 4 2 1 纠错纠删译码2 4 4 2 2g m d 算法2 5 4 2 3c h a s e i i 算法2 5 4 2 4 分阶统计译码算法( o s d ) 2 6 4 2 5 盒匹配译码算法( b m a ) 2 7 4 2 6 代数软判决译码算法。2 8 4 2 7 自适应置信度传播算法( a b p ) 3 1 4 2 8 球型译玛( s d ) 算法 4 3 仿真结果及分析 4 4 本章小结。 二。3 4 一3 5 4 0 第五章r s 码级联软判译码算法研究。 5 1 级联算法4 l 5 1 1c g a 算法一4 1 5 1 2a b p o s d 级联译码算法4 2 5 1 3a b p b i a s b m a 译码算法k 4 3 5 1 4c h a s e a s d 算法4 5 5 2r s 码级联译码算法仿真结果及分析4 7 5 3a b p c h a s e 译码算法5 0 5 3 1 算法思想。5 0 5 3 2 算法步骤5 0 5 3 3 性能仿真及分析。5 1 5 4a b p s d 译码算法5 3 5 4 1 算法思想5 3 5 4 2a b p s d 译码算法5 3 5 4 3 能仿真及分析5 4 v i 5 4 4 算法复杂度分析5 7 5 5 本章小结5 9 第六章工作总结与展望6 0 附录i 程序清单61 附录硕士期间撰写的论文6 2 1 1 1 9 ：谢6 ：； 参考文献6 4 i 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 当今时代，通信特别是移动通信在人们生活中发挥着越来越重要的作用。正因此，许 多科技工作者对其进行了不懈的研究。其中，通信的有效性和可靠性始终是一个永恒的话 题。当信号经过各种数字传输系统，由于信道中噪声的恶化，在接收端信号会不可避免地 产生畸变。为了抑制这种畸变，达到信号的可靠传输，差错控制编解码成为当今通信工作 者研究的一个热点。 1 1 纠错码的发展概况 1 9 4 8 年，s n 【l 】提出的信道编码定理给出了有噪信道通信的最大速率，证明了好 码的存在性，但该定理证明的是非构造性的，它没有告诉我们怎么构造好码。如何通过不 可靠信道进行可靠的通信，是编码理论所要研究的问题。半个多世纪以来，众多的学者为 构造逼近容量限的纠错码做了大量的研究 众所周知，纠错码1 2 1 1 3 1 从构造方法上可以分为分组码( b l o c kc o d e s ) 和卷积码 ( c o n v o l u t i o n a lc o d e s ) 两大部分。在分组码方面，第一个分组码是1 9 5 0 年发现的能纠正 单个错误的h a m m i n g 码；在整个5 0 年代，基于代数理论又发现了多个短码长的分组码， 如1 9 5 4 年g o l a y 发现的g o l a y 码网以及r e e d 和m u l l e r 发现的r m 码【6 】忉，p r a n g e 在1 9 5 7 年发现的循环码等。b o s e 和r a y - c h a u d h u r i 在1 9 6 0 年及h o c u c n g h e m 在1 9 5 9 年分别独立 发现的能纠正多个错误的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 mt y p eo fc o d e ) h t s 9 ，以及 r e e d 和s o l o m o n 在1 9 6 0 年发现的非二进制r s 码【l o l 。其后发现的分组码主要有1 9 7 0 年的 g o p p a 码和1 9 8 2 年发现的代数几何码。在所有这些分组码中，除了g o p p a 码和代数几何 码中存在个别是渐进好码外，其它均不是好码。卷积码【1 1 】最早由e l i a s 在1 9 5 5 年提出，早 期被称为树码( t r e ec o d e s ) ，现在称为格图码( t r e l l i sc o d e s ) 或卷积码。 卷积码具有动态格图结构，可用有限状态机来描述其状态。在上世纪的五十年代末， 卷积码已可以通过序列译码算法得到成功的译码。在1 9 6 7 年，由v i t e r b i 提出的v i t e r b i 算 法成为了卷积码的译码工作中至今为止最常用的译码算法。 f o m e y 于1 9 6 6 年基于分级编码的概念提出了级联码( c o n c a t e n a t e dc o d e s ) ，构成码以顺 序方式进行编码和译码 4 1 。一个短长度信道编码的译码错误概率可能比较高，但是它不仅 能改变错误分布，而且能有效增加信号的接收信噪比( s i g n a ln o i s er a t i o ) ，它事实上提供了 南京邮电大学硕士研究生学位论文 第一章绪论 一个信道容量较大的等效信道。在此基础上再进行一级编码，则期望能实现有效而可靠的 通信。 1 9 9 3 年t u r b o 1 2 】【1 3 1 码的提出被看作是信道编码理论研究的重要里程碑。b e r r o u 等人将 卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近最大似然译码，取得了超乎 寻常的优异性能，并一举超越了截止码率，直接逼近s h a n n o n 提出的信道容量限。t u r b o 码是一种信道编码理论界梦寐以求的可实用非常好码，它的出现标志着信道编码理论研究 进入了一个崭新的阶段。t u r b o 码成功的根本原因在于其实现方案中长码构造的伪随机性， 它通过随机交织器对信息序列的伪随机置换实现了随机编码的思想，从而为s h a n n o n 随机 编码理论的应用研究奠定了基础。 随着t u r b o 码的深入研究，m a c k a y 和s p i e l m a n 几乎同时发现g a l l a g e r 早在19 6 2 年提 出的低密度校验码【1 4 l ( l o wd e n s i t yp a r i t y c h e c kc o d e s ，简称l d p c 码) 也是一种具有渐进特 性的好码，具有更低的线性译码复杂度，它的译码性能同样可以逼近s h a n n o n 信道容量限。 由于l d p c 码具有在中长码长时超过t u r b o 码的性能，并且具有译码复杂度更低，能够并 行译码及译码错误可检测等特点，成为目前信道编码理论的研究热点。人们在基于图模型 研究l d p c 码时，发现t u r b o 码也可看作一种图模型上的l d p c 码，译码算法具有等价性， 从而使两者在基于图模型的编译码研究中得到了统一 到目前为止，纠错码技术已经在实际应用中取得了越来越不可忽视的作用，我们有理 由相信，随着科学的进步和实际的需要，纠错码理论必将进一步发展，同时，随着超大规 模集成器件成本的进一步下降，它的应用范围必将进一步扩大。r s 码就是这种纠错码中不 可忽视的重要一员。 1 2r s 码的发展与现状 r s 码是一类有很强纠错能力的多进制b c h 码，也是一类典型的代数几何码。它首先 由里德( r e e d ) 和索罗蒙( s o l o m o n ) 于1 9 6 0 年构造出来的，在此后较长时间，没有比较 好的解码算法，直到1 9 6 5 年，e b e r l e k a m p 2 q 提出了一种可以有效地实现b c h 和r s 码解 码的方法，它首次使得可以纠正多个字节错误的r s 码的解码成为可能。1 9 6 9 年，m a s s e y t 2 r l 提出了一种等效于线性反馈移位寄存器( l f s r ) 综合方法的b c h 译码方法，该方法与 b e r l e k a m p 的方法是类似的，因而该算法现在常称为b e r l e k a m p m a s s e ) ( b m ) 算法。1 9 7 5 年，s u g i y a m a e t a l 提出了一种解关键方程的e u c l i d e a n 算法，可以有效对r s 码、b c h 码和 g o p p a 码解码。b m 算法及e u c l i d e a n 算法均为硬判译码算法。硬判译码有没有充分利用信 2 南京邮电大学硕士研究生学位论文 第一章绪论 道软信息的固有缺陷。 1 9 9 6 年，f o r n e y 首次提出了广义最小距离译码算法( g m d ) 。g m d 译码算法是一种迭 代纠错译码，算法需要i 眈1 次硬判决译码，得到i ( 抛1 个候选码字，然后挑出一个最好的 作为译码输出。g m d 算法开创了r s 码软判译码的先河。受到g m d 算法的启发，c h a s e 提出了c h a s e 算法。c h a s e 算法是一种伴随式译码，利用可信信息寻找最可能的错误图样， 根据试探错误图样数目的不同，分为c h a s e i 、c h a s e i i 和c h a s e i i i 三种算法，其中c h a s e - i i 由于的复杂性适中且译码性能很接近m l d 在实际中应用最多。之后大量学者围绕试探门 限标准和试探集合两个问题对c h a s e 算法进行改进，在缩短译码时间、提高译码性能等方 面取得进展。 f o s s o r i e r 等 4 4 1 1 4 5 1 于1 9 9 5 年提出了一种使用于线性分组码的分阶统计译码( o r d e r e d s t a t i s t i c sd e c o d i n g ) 算法。h u 等 4 6 1 于2 0 0 1 年将这种算法引入到r s 码的译码并在译码过 程中引入最优性测试，降低了译码复杂度。 1 9 9 9 年g u r u s w a m i 和s u a a n ( g s ) 【3 3 1 提出了一种能够超越r s 码硬判译码半径的代数列 表译码算法。2 0 0 4 年k o e t t 廿和郴牌在g s 算法的基础上提出了一种基于多项式 的低复杂度代数软判决译码( a s d 算法，该算法与硬判决算法( h d d ) 有着明显的增益 与此同时，有许多其他r s 码软判译码算法被相继提出。此外，r s 码的级联软判译码 算法也如雨后春笋。我们将在第四章及第五章详细介绍这些算法。 1 3 本课题意义 r s 码因为拥有独特的纠错性能而被广泛应用，如硬磁盘驱动器、c d - r o m 、c d 机、 数字音频、d v d 机、数字电视、数字图像系统、大容量存储系统、远距离通信和数据广播 协议、无线通信、单信息包数字数据、无线个人数字处理器、可容错r a i d 控制器、深空 探测任务、星际侦察、x d s l ( a d s l ，v d s l ，h d s l ，s d s l ) 以及移动系统的地面同步卫星 通信对接等。同时，r s 码在许多不同的国际标准中得到了相应规定，如c c s d s 、 i e e e 8 0 2 1 4 a 、i e e e 8 0 2 1 4 b 、w - c d m a 、v s b 、i m t 2 0 0 0 、d v b 以及d v d 等。而在国 内外的航天工作中，同样r s 码在许多不同的任务中发挥着重要的作用，如在国内则有实 践5 号、神舟3 号、神舟4 号以及探测l 号等任务，在国外则有m a r i n e r 9 、v o y a g e d 、v o y a g e r 2 、 g i o t t o 、g a l i l e o 、c a s s i n i 、s m a r t - i 、m a r s p a t h f i n d e r 、m a r sl a n d e r 和m a r se x p l o r a t i o nr o v e r 等任务。 正是因为r s 码有如此广泛的应用，对r s 码的深入研究尤为重要，其中，对r s 码的 3 南京邮电大学硕士研究生学位论文 第一章绪论 译码算法的研究非常关键。能否提出r s 码的具有优异性能的译码算法对r s 码的更加广泛 的应用有至关重要的作用。而r s 码的硬判译码算法因为没有充分利用信道输出的软信息 而损失一定的译码增益，为了取得更好的译码性能，r s 码的软判译码算法被提上了议事日 程。在此背景下，本文着力于对r s 码软判译码算法的研究。 1 4 本文工作及章节安排 本文主要研究了r s 码的级联软判译码算法。首先我们总结了目前主流的r s 码的硬判 译码算法及非级联软判译码算法。在非级联软判译码算法中，我们详细介绍了自适应置信 度传播( a d a p t i v eb e l i e fp r o p a g a t i o n ) 算法，球型译码( s p h e r ed e c o d i n g ) 等算法。此外我 们研究和总结了目前比较流行的r s 码的级联软判译码算法。在此基础上，我们提出了两 种级联译码算法：a b p c h a s e 算法及a b p s d 算法。 我们知道，a b p 是一种性能较好的译码算法，但是a b p 也有译码失败的时候。为了减 少这种译码失败，我们将c h a s e 算法级联于a b p 算法之后。仿真表明这种算法达到了预期 的效果，相对于a b p 算法，提高了译码性能； s d 算法是将b m 算法的译码输出与信道输出的欧氏距离作为译码半径，为了减小这种 译码算法的搜索半径，我们将a b p 算法级联于s d 算法之前，减小了搜索半径，译码性能 也相应的取得提升。 本文的章节安排如下： 第一章为绪论，简要介绍了纠错码的发展概况、r s 码的发展与现状和本文的主要工作。 第二章给出了r s 码的基本知识，包括有限域的基本知识以及r s 码的定义、码重分布 等。 第三章简要介绍了r s 码的硬判译码算法。 第四章我们研究了目前比较流行的r s 码的各非级联软判译码算法。我们详细介绍了 各种非级联软判译码算法的译码思路，译码步骤等。其中我们详细介绍了a b p 算法及s d 算法。在这些非级联软判译码算法中我们选择典型的译码算法进行了仿真。 第五章着力于r s 码的级联软判译码算法的研究。首先，我们分析和研究了目前比较 流行的级联软判译码算法，如c g a 、a b p o s d 等。受到这些级联软判译码算法的启发， 我们在级联软判译码领域进行了尝试，提出了两种卓有成效的级联软判译码算法： a b p c h a s e 算法及a b p s d 算法。 第六章对全文进行了总结，对下一步的工作进行了展望。 4 南京邮电大学硕士研究生学位论文 第二章r s 码基本知识 第二章r s 码基本知识 r s 码全称为r e e d - s o l o m o n 码，它是基于伽罗华域代数理论基础上的多进制完备分组 码。正因此，r s 码具有优良的纠错性能，它既能纠正随机差错也能纠正突发差错。在介绍 r s 码软判译码算法之前，有必要介绍下r s 码的基本知识，如，有限域代数基础，r s 码 的定义及码重分布及译码性能等。 2 1 、伽罗华域代数基础 2 1 1 群、域简介 群：若t 是非空集合，在t 内定义一种代数运算( 用表示) ，符合以下要求： l 、满足封闭性。对任意口，t ，恒有础e t ； 2 、满足结合律对任意口，声r ，有( a a p ) a r - a a ( p r ) ； 3 、集合t 中有恒等元万存在，对任意窿t ，有艿t ，使得必万= 融口= 口； 4 、对任意口t ，存在口的逆元口以e t ，使以口1 = 矿1 a a = 艿； 则称此集合t 构成一个群。 阿贝尔群：若群t 中，对任何口，t ，有鲥够= 肚口，则称t 为阿贝尔群。 域：非空元素集合q ，若在q 中定义了加和乘两种运算且满足下述公理： 1 、q 关于加法构成阿贝尔群，其加法恒等元记为0 ； 2 、q 中非零元素全体对乘法构成阿贝尔群。其乘法恒等元( 单位元) 记为l ； 3 、加法和乘法间有如下分配律： a ( p + 7 ) = q p + 町( 2 1 ) ( + r ) a = 触+ 胆 ( 2 2 ) 则称q 是一个域。域中元素的个数为域的阶。 元素个数有限的域称有限域即伽罗华域，厨g f 表示p 阶有限域。伽罗华域在编码 理论中起着非常重要的作用。 5 南京邮电大学硕士研究生学位论文 第二章r s 码基本知识 2 1 2 有限域基本概念 因为r s 纠错编码是在有限域内进行运算的，所以有限域理论在其编码理论研究中起 着特别重要的作用。有限域( g a l o i sf i e l d ) 是指元素个数有限的域，域中元素的个数称为域 的阶。通常用g 积p ) 表示p 阶有限域。有限域的一个重要性质是每个有限域g f ( p ) 至少要包 含一个叫做o f 的本原元素，它能生成该域中的每个非零元素。 为了理解r s 码的编码和译码，有必要深入到称为伽罗华域的有限域中。对于任何质 数p ，存在一个有限域，表示为g f ( p ) ，其中包含p 个元素。可以将g f ( p ) 延伸为一个含有 p ”个元素的域，这称为g fo ) 的扩展域，表示为g f ( p “) ，r n 是一个非零正整数。注意， g f 是g f ( p “) 的子集。扩展域g f ( p 研) 中的码元用于构造r s 码。 二进制域g f ( 2 ) 是g f ( 2 ”) 的一个子域，类似于实数是复数的一个子域一样。除了数字 0 和l ，在扩展域中还有特殊的元素，用一个新的符号o f 表示。g f ( 2 ”) 中任何非零元素都 可以由口的幂次表示。元素的无限集g ，就是根据元素 o ，1 ，o f 而形成的，后_ 个元素通过 前一项乘以口而得： g = q 1 ，矿，) = 0 ，口o ，t i l l 口2 ，一，口7 ，毒c 3 ) 为了从g 中得到有限元素的集合删) ，必须对g 域施加一个条件，使它只能含有2 一 个元素，并且对乘法封闭。域元素对乘法封闭的条件可由下面的不可约多项式表示： 口2 。一1 + l = 0 ( 2 4 ) 即： 口2 。一= 1 ( 2 5 ) 根据这个多项式限制条件，任何幂次等于或超过2 肺一l 的域元素都可降阶为如下表示 的幂次小于2 ”一1 的元素： 口2 。+ ”- - o f 2 m - i o f ( m ) = 口( 1 + 一 ( 2 6 ) 因此可以得到有限域g f ( 2 槐) 的元素由下面序列构成： g f ( 2 卅) = o , o f o , o f io f 2 ，口矿一2 ) 6 ( 2 7 ) 南京邮电大学硕士研究生学位论文 第二章i t s 码基本知识 2 i 3 扩展域g f ( 2 ”) 中的加法和乘法 为了找到一种遵守有限域内全部乘法性质的多项式乘法，用来构成一个元素数为p _ 的 有限域，首先，我们要求在一个集合内的任何两个多项式之积是本集合中的另一个多项式， 以满足封闭性。只要该乘积是一个次数等于或低于脚一l 的多项式，就可以满足这一要求。 对于次数等于或大于m 的乘积多项式，可以取它相对于一个m 次固定多项式的余项多项 式。这里所需要的m 次固定多项式就是本原多项式p ( x ) 。它的最高次幂为m ，而系数在 g f 上，它是不可约多项式。一般地说，系数取自g f ( p ) 的不可约多项式在g f 中无根， 但在扩张域g f ( p 肿) 内有根。具体说，m 次p ( x ) 在扩张域g f ( p 胛) 内必有m 个根。 在有限域g f ( 2 ”) 中，2 。个元素中的任意一个都可由阶数小于或等于m 一1 的不同多项 式来表示。多项式的阶数是它的最高幂指数。将g f ( 2 。) 中每个非零元素用多项式口j ( 力表 示，其系数至少有一个不为0 。对于f = 0 j , 2 , 2 2 ， 2 2 - - 2 ，有：， q ( 力= q + a l , t x + a j j ，口j _ 一i x 。一1 当m = 3 时，有限域表示为g f ( 2 s ) 由于式矿= 矿，所以在该域中有7 个非零元素， 或者说总共有8 个元素。6 f ( 2 3 ) 是o f ( 2 ) 的扩展域，g f ( 2 3 ) 中8 个元素都可以用6 v ( 2 ) 中 的两个元素0 ，l 组合来表示，例如1 0 0 ，1 1 0 ，0 1 1 等等。扩展域元素代替二进制元素的一 个好处就是表达的紧密性，使得非二进制编码和译码过程的数学表示变得简单。有限域中 两个元素的加法定义为两个多项式中同幂次项系数进行模2 加，即： 口+ 口7 = ( q o + 乃，o ) + ( q ，o + a j , o ) 工+ ( q ，l + 巳。1 ) x 2 + + ( 岛，辫一l + a j 。_ 一1 ) x 用- 1 ( 2 8 ) 有限域中的乘法运算规则是把两个元素表示化成指数形式，将指数直接相加，取模2 用一l ， 如下式所示： 口口j = 口( “j ) m o d ( 2 - 1 ) ( 2 9 ) 2 1 4 有限域的本原多项式 有限域g f ( 2 所) 可用一组本原多项式来定义，有限域是定义r s 码所必需的，所以研究 r s 码需研究本原多项式。本原多项式可定义为：一个m 阶的不可约多项式职) 如果f ( x ) 7 南京邮电大学硕士研究生学位论文 第二章i 峪码基本知识 能整除r + l 的最小整数为n ，其中疗= 2 ”一1 ，则该多项式是本原多项式。不可约多项式是 指一个多项式不能因式分解为更低幂次的多项式。表2 1 中列举了一些常用的本原多项式。 2 2r s 码基础 m本原多项式 2 1 + x + x 2 3i + x + x 3 4 1 + x + x 4 51 + x 2 + x 5 6 1 4 - x