（通信与信息系统专业论文）rs码的硬件实现研究.pdf

摘要 r s 码是多进制b c h 纠错码的重要子类。它具有优良的纠错性能，能够纠 正多个髓税差错。它常蔹再l 予察易发生予擒豹无线绩遴积存储信遵中， i e e e 8 0 2 1 6 a 物理层也将其选作信道编码方案之。最近，随着v l s i 技术的发 展，采用a s i c 或f p g a 来实现信邋编码获得了广泛的研究。 一方嚣，本文依掇i e e e 8 0 2 ，1 6 a 物理层对r s 褥懿参数甏求，研究tr s 码 编、译码基本原理。另一方面，本文研究了f p g a 技术，构建了由m a t l a b 、i s e 、 m o d e l s i m 、s y n p t i f y p r o 等软件构成的开发平台。在此基础上，采用一种经典算 法，以v e r i l o g 为疆述语言，在x i l i n x 公司酶s p a r t a n i i i 器件上实现t ( 2 5 5 ，2 3 9 ) r s 编码器及译码器。其中编码器部分包括作为核心的多项式除法器、控制用有限状 态机两部分；译码器都分包括：伴随式计算、错误位置多项式计算、求错误值计 算多项式、错误氆计舞、“钱援索”验粳、码元时延缓薛f i f o 、控钢霜有隈状态 机等部分。 此外，本文还对译码器的关键郏分进行了以下方面的改进：( 1 ) 对错误值计 算结鞫逑行改进：将对缀的指数遮算单元改遘为累乘结构。( 2 ) 对码元延辩f i f o 结构进行改进：将双口r a m 结构改为l u t 移存器链结构。( 3 ) 对错误能置多 项式计箨络梅进行改避：将经典b m 算法分别改遂为无求逆犟元的改进型b m 算 法和无求逆单元的蔽逐型欧足里穗算法。 a b s t r a c t t h e r s ( r e e d s o l o m o n ) c o d e i sa l l i m p o r t a n t s u b c l a s so fn o n b i n a r yb c h e r r o r - c o r r e c t i n gc o d e s ，w h i c hi s e x c e l l e n ti n c o r r e c t i n g r a n d o mm u l t i e r r o r si n c o d e s i ti s a l w a y se m p l o y e d i nw i r e l e s sc h a n n e lo r s t o r a g es y s t e m t h a ti s i n t e r f e r e f e r i n g a sas p e c i a lc a s e ，i ti se m p l o y e di np h y s i c a ll a y e ro fi e e e 8 0 2 16 a p r o t o c 0 1 r e c e n t l y , v l s i o rf p g ai m p l e m e n t a t i o no fe r r o r - c o r r e c t i n gc o d e si s i n t e n s e l yb e i n g s t u d i e d f i r s t ，t h i sp a p e ri n v e s t i g a t e st h ec o d i n ga n dd e c o d i n gm e c h a n i s mo ft h er sc o d e s e c o n d ，t h i sp a p e ri n v e s t i g a t e st h ef p g a t e c h n i q u e sa n dc o n s t r u c t st h ed e v e l o p m e n t p l a t f o l x aw h i c h i sc o n s i s t so f m a t l a b ，i s e ，m o d e l s i m ，s y n p l i f y p r o t h e n ，w e i m p l e m e n t sap a i ro f ( 2 5 5 ，2 3 9 ) r se n c o d e ra n dd e c o d e rd e s c r i b e di nv e r i l o go n s p a r t a n i t id e v i c eo f x i l i n xc o r p o r a t i o n t h ee n c o d e rc o n s i s t so f ap o l y n o m i a ld i v i d e r , t h ek e y p a r tf o re n c o d i n g ，a n dac o n t r o l l i n gf s m ( f i n i t es t a t em a c h i n e ) t h ed e c o d e r c o n s i s t so fas y n d r o m ec a l c u l a t i o nm o d u l e ，a ne r r o r - l o c a t i o np o l y n o m i a lc a l c u l a t i o n m o d u l e ，a ne r r o r - e v a l u a t i o np o l y n o m i a lc a l c u l a t i o nm o d u l e ，a l le r r o r - v a l u ec a l c u l a t i o n m o d u l e ，a “c h i e ns e a r c h ”m o d u l e ，af i f oa n d a c o n t r o l l i n gf s m b e s i d e sa b o v ew o r k ，t h i sp a p e rg i v e saf e w i m p r o v e m e n t sf o rt h ek e yp a r t so f t h e d e c o d e nf i r s t , w es u b s t i t u t et h ep o w e rc a l c u l a t i o nc e l l si ne r r o r - v a l u ec a l c u l a t i o n m o d u l ew i t ha c c u m u l a t i v em u l t i p l i e r s s e c o n d ，w eu s el u t s h i f t r e g i s t e rs t r u c t u r et o s u b s t i t u t et h ed u a l p o r tr a ms t r u c t t t r ef o rf i f o i m p l e m e n t a t i o n t h i r d ，w ee m p l o y i n v e r s e - f r e em o d i f i e db m a l g o r i t h ma n d i n v e r s e f r e em o d i f i e de u c l i d e a na l g o r i t h m 奶 i m p r o v e t h ee r r o r - l o c a t i o np o l y n o m i a lc a l c u l a t i o nm o d u l e 1 1 南京邮电学院学位论文独创性声明 ，6 2 8 8 6 3 本人声明所里交的学位论文是我个人在导师指导下进行的研究 工俸及取得黪 舞巍成果。尽我艨知，除了文中特别翻以标注； 瑟数落瓣 地方外，论文中不包含其他入爵经发表躐撰写过的研究成暴，也不包 含为获得南京邮魄学院或其它教育槐构的学位蠛诞书面使翔过的材 料。与我一曩王锋韵溺志对本磷究所徽懿任何贡献均澄在论文中作了 胡确的说疆并袭示了谢意。 鹾究生签名：鞠翅： 南塞邮电学院学位谂文使用授权声明 南京螺电学院、中重科学披术信息磺究所、国家豳书馆霄投摄窘 本人浙送交学位论文的复印件粕电子文糨，可以采溺影印、缩印绒其 氇复翻手段保存论文。本人电子文耥的斑容和纸缀论文的内察褶一 致。除在保密矮凌的保密论文外，允诲论文被查凝鞠鞲阗，霹羰公布 ( 包括刊登) 论文的全都或部分内容。论文的公稚 授投 南京邮魄学院研究生部办理。 研究生笈名：导师签名： 第裁序论 第一章绪论 哇。1 倦道编码技术概述 通信系统的目的烧蒙将信源端的信息准确而高效地传送到接收端。然而，由 于带有信息的通信信号在通过信道时会不可避免地受到各种备样的干扰，尤其是 在无线谂遂稻存储信邋 2 令薅壤差 错，可以根据需要方便地设计其纠错能力，通过缩短可以方便地使码长符合实际 地需要。在实际中，r s 码获得了广泛地应用。 以线往分缝筠为乡 玛，卷积弱为瘫酶懿睾孬缀联弱在实鼯中菠矮褥羧多。露 r s 码有精较好的随机麓错纠错能力，通常作为外码。在c d 唱片中，采嗣了两级 纠错加交织器的差错控制方案”1 。纠错码使用的是( 2 5 5 ，2 5 1 ) r s 码，使用时分 囊缭矮麓( 2 8 ，2 4 ) 豹筹弱零( 3 2 ，2 8 ) 熬蠹璐皋襞趸。在字簸中，经誉毽惩懿 r s 码为外码，卷积码为内码的串行级联码。比如“探险者号”就使用了( 2 5 5 ， 2 2 3 ) r s 码。在美国的a t v ( a d v a n c e dt v ) 标准中采用了由( 2 5 5 ，2 3 5 ) r s 码 缠短嚣雩簿戆( 2 0 7 ，1 8 7 ) - n 短鹞“。在i m t 一2 0 0 0 帮塞絮毪拣漆中采霸了( 2 0 4 ， 1 8 8 ) r 8 码叫，在i t u tg 9 7 5 标凇中使用了( 2 5 5 ，2 3 9 ) r s 码“，( 2 5 5 ，2 3 9 ) r s 第一章穿论 码在i e e e 8 0 2 1 6 a 协议中也被采用为信道编码方式之一1 。 嚣1 ；蓼，对l s 强瓣硬终实囊缮劐了广泛熬磷突。有不少文献结合实嚣瘟臻， 提出了邋用于特定环境的r s 编译码硬件结构：如文献 1 2 3 用v l s i 实现了用于数 字微波系统中的( 2 5 5 ，2 2 3 ) r s 码，文献 1 3 提出了一种用于a t m 网络中的流 拳线r s 谨筠绫稳，文献 1 4 】、 1 翻分剜疆壅了麓予多媒藩弱终鞠d v d 应蠲瓣r s 译码器的v l s i 结构。也有相当多的文献侧重于算法或是关键单元的设计：如文 献 1 6 比较了采用不间表示法实现有限域算术运算的资源占用和性能，文献 1 7 疆窭了鏊予复域豹一稀有陵壤并章亍添法绣季毒，文簸 1 8 磷究了一耱求簿关键方程 的改进b m 算法，文献 1 9 研究了一种改进的欧几里德算法。 唾4 本文的背景及内容安撰 本文是作者在参加8 6 3 项目“凝于8 0 2 1 6 a 协议的宽带光线接入系统关键技 术研突”，从事协议中物理层信道缡码懿f p g a 实现工俘的总终。在8 0 2 1 6 a 协议 的物理层规范中，信遵编码部分分为随机化、前向绷错和交织三个部分。冀中前 向纠错部分由以r s 码外码、卷积码为内码的级联码组成。本文的主要工作是对 悠码郝分的研究与实现。 本文在研究r s 粥的原理和f p g a 技术的基础上，在x i l i n x 公司的f p g a 芯片 上实现了r s 码的编码器、译码器模块，并对译码器的几个关键模块的结构进行 了改遘。全文的悫客安羲 懿下： 第一露序论简骚介绍信道编褐技术、信号她理实现方法、r s 编码的应用情 况及本文内容安排。 第二滚r s 码藩瑾楚要奔绥然强匏数学慧礁及其编译弱原理。 第三馥f p o a 技术概述介绍f p g a 历史、发展、结构及本文所用开发环境。 第四窜r s 编译醐的f p o a 实现详细介绍用f p g a 实现r s 编译码器备模块 筑舅法嫒 譬缝擒，绘囊没诗竣绣炱波形鞠性能+ 第五奄对硬件结构的改进对第四章所述译码器中的魑茨键功能模块豹结 构进行改进。 第六窿结衷语瓣本文遂牙慧绫著对下一步工俸进行袋黧。 4 第二牵r s 码骧理 第二章r s 码原理 r s 码怒目前应用最广泛的线性分组码之一。它与线性分组码的关系可以表示 为：瑟璐 b c h 褥一 疆巧玛一 线健分缓玛( 一 表示隶溪关系) 。r s 强怒一耪 纯粹的代数码，其编译码方法均建立在近世代数的基础上。 2 。嚏代数码的数学基础 线性分组码的数学基础是近世代数。近世代数是研究线性分组码的生成、编 译码方法及其性2 特点瓣基础，也是设计、寻找“好码”的必要工具。本_ 萤麓要 介绍遥世代数的基本概念和性质”1 。 2 1 。1 瓣、环、域 1 群 对于一个非空元素集合g 以及定义在g 上的一种运算“$ ”( 这里的$ 泛指 任一季孛代数运算，魏+ 、一、，模羹趣静，模 l l 黍9 麓) ，著满是璐下霆 个条件： 1 ) 封闭性目口v n ，b g ，3 ( “ 6 ) = c g 。 2 ) 结合性即v “，b ，c g ，l ( 耵 西) 4 c = 群4 ( 6 c ) 。 3 ) 存在唯一的一个单位元e ，即v 日g ，l 口g ，使a 4 口= p 十口= “。 4 ) g中赘每个元索各鑫存在难一豹逆元， 静 v a g ，j “1 g ，使d 球d 一1 = d 一1 d 描口。 则稔这樽躯代数系绕必群，记傲( g ，术) 。 若搿满足第五个条件： 5 ) v d ，b g ，i 女b = ( 6 十日) 。 翻豫这耧瓣我鼗系绫为交捺器( 瓣员尔群) 。 若群( g ， ) 中的运算 是加法，则称该群为加群；若怒乘法，则称该群为 第二章r s 码原理 乘群。加群一定是交换群。加群中一定包含零元素，零元素就是该加群的单位元 e 。加群元素a 的逆元a “就是代数中的一a 。乘群中一定不包含零元素，因为零元 素不存在乘运算下的逆元。乘群不一定是交换群。乘群的单位元是1 。乘群元素 a 的逆元a 。1 是代数中的1 a 。 根据群中包含元素的个数，群可以分为有限群与无限群。有限群的元素个数 称为该群的阶。 若对群( g ， ) ，集合g 的非空子集s 在同样的运算 下可构成群( s ， ) ，则称群 ( s ，) 为群( g ， ) 的子群。有限群的子群阶数一定是其阶数的因子。 由某一元素a ( 生成元) 的一切乘幂a o ，一，d 2 的全体组成一个群，称为循 环群( 幂群) ，其中a o = e 是单位元。若序列a o ，d 1 ，a 2 中没有两个元素是相等的， 则称之为无限循环群。若上述序列中存在两个相等的元素a 1 = 口俅，) ，可推出 g 的元素必以某个整数n 为周期重复，即a “= a o = e 。 集合g = 1 ，2 ，q 一1 ) 在模q ( q 为素数) 乘运算下构成一个乘群( g ，o ) ，该乘 群是q - 1 阶有限群，又是交换群，单位元为t 。其中每个元素a 都存在一个逆元 6 g ，满足0 6 ) m o dq = 1 。上述群的阶q 必须为素数，否则就不能保证任意 元素都存在逆元。 2 环 对于非空集合r 以及定义在r 上的乘、加两种运算，若满足以下三个条件： 1 ) 集合r 在加运算下可构成加群( r ，+ ) 。 2 ) 集合r 在乘运算下满足群的前三个条件，即封闭性、结合性及单位元存在 性。 3 ) 分配律，即v d ，b ，c r ， ja ( b + c ) = d b + c ，( b + c ) 口= b d + c a 。 则称该代数系统为环，记做( r ，+ ，) ，简称环r 。若环r 还满足乘法交换律，则称 该环为交换环。 例如集合z = 0 ，1 ，2 ，m 一1 ) 在模m 加，模m 乘运算下可构成有限环，也称 剩余类环。当1 1 1 不是素数时，环内会存在零因子。所谓零因子，是指环内的两个 6 第二袋r s 羁鼹瑗 乘积为零的非零元素。 对饕邂繇瓣嘉鞋勇羚弱黻髑条 串将产生些褥辣熬醛。不枣在零因子的环稼为 懿环，当l l l 为索数时上述剩余类环即为藏环。着环r 建交换环并黛其裔凝聚力， 印子环中侄慧元素与任懑一个非子环的环元素的豢积位于予环内。那么称遮榉的 子环为r 驹疆怒予琢。环r 戆瑾戆予环麴交鬃识楚疑薅想予环。整蓬想予环鹃瓣 霉元索可洼l 个元素a 瓣备次幂或备次攀的线性缀合生成，剐称该理想予环为主 理想子环，简称主理想，元素a 称作生成元。 3 。城 对于至少含有一个沸零元素的交换环f ，若每个非零元素都存在乘运黧下的 逆元，则称该交换环为域，记做眠+ ，- ) ，简称域f 。 有簸熬数集合f = 0 ，i ，2 ，q - l ( 为素数) 在摸q 热、模q 蘩运算下稳藏一 个q 阶裔限域，又称伽逻华( g m o i s ) 域，沧做g f ( q ) 。伽邂华域g f ( q ) 的q - 1 个l 零元素在模q 象运算下构成一个键环群，即所肖非零元素可以幽一个元豢d ( 称作，生戏元或本艨元) 鹣各次粼扩，g ，9 2 ，9 9 4 生成。 2 1 2 多项式裁余类环和域 多域式楚码字与代数之间的桥浆。比如，对于硝字( i i 0 1 ) ，可写成代数式 x 3 + x 2 + i ，其系数代滚辫元取毽，x 的攀次指示鹦元位置。系数属于莱数域筑多 项式称为该数域上的多矮式。噬数为元素可襁成群、环、域，以多项式为元豢溺 样可以构成群、环、域。 i ，多项式环藕糕想孑垮 莱数竣上多项式鹣集合在乘、潮运算下可黻搦成一个多硬式环，它麓 一个以多颈式为环元綮的交换环。 缡鼹中使雳懿多磺筑鹈余类环瓣定义盎鞋下；g f ( q ) 上戆多矮式在模糖、模 f ( x ) 爨运羹下，多曦式剩余类的全体灏褥藏敕交换繇称为多颚姣潮余类环，记徽 心( x ) m ，。多项式剩余擞环是靠g f ( q ) 域保证畚数肖限，靠模f ( x ) 保证幂次肖限 戆。多磺式运箕中像禽了系数阁摸q 鬃、麓的羧躐运筹a 如聚多项式最黼次项的系数为1 ，剃称该雾顼式是曾多硬茂。仪龟岔觳嵩 7 第二章r s 码原理 次项和常数项1 ，形式为x “+ 1 的首一多项式称为n 次最简首一多项式。 以f ( x ) 为模的多项式剩余类的全体构成一一个有限元素的多项式剩余类环 r 。 ) 八，) ，这个环的每一理想子环皆为主理想，且该主理想的生成多项式g ( x ) 必能整除f ( x ) 。 2 多项式域和循环群 在介绍多项式域前，先引入几个术语： 既约多项式对于某数域上的多项式f ( x ) ，若除了常数c 及c f ( x ) 外， 不能被该数域上的任何其它多项式整除，则称f ( x ) 为该数域上的既约多项式。 本元多项式对于有限域g f ( q ) 上的m 次既约多项式f ( x ) ，若能被它整除的最 简首一多项式x ”一l 的次数”q “一1 ，则称该多项式为本元多项式。 多项式循环群由多项式t 2 的各次幂所构成的群称为多项式循环群。多项式 a 称为生成元。 对于多项式域和循环群的存在性、性质、构造等问题，可以由下列定理来阐 述。 定理2 1 若f ( x ) 是g f ( q ) 域上的m 次既约多项式，则g f ( q ) 域上次数小于m 的多项式，在模q 加、模f ( x ) 乘运算下构成一个g 卅阶的有限域，称为g f ( q ) 域 的扩域，记做g f ( 矿) 。称g f ( q ) 是扩域g f ( 矿) 的基域。 定理2 2 若f ( x ) 是g f ( q ) 域上的n 1 次本元多项式，则g f ( q “) 域上次数小于 m 的非零多项式的全体，在模f ( x ) 乘运算下构成一个多项式循环群。也就是说， 扩域g f ( q m ) 里至少存在一个本原元a ，它的各次幂构成了扩域的全部非零元素。 定理2 3g f ( q ) 上的本元多项式f ( x ) 在扩域g f ( q ”) 上的根口一定是本原元。 定理2 4g f ( 矿) 扩域上非零元素 ) ( 女= o ，1 ，q ”一2 ) 的阶一定是q 4 1 的 因子，其值为：n = ( 矿一i ) g c d ( k ，矿一1 ) ，这里g c d 表示最大公约数。 定理2 5 扩域g f ( 圹) 上所有非零元素口。，a 矿一2 都是c f ( q ) 上多项式 ，一l 的根，即，一一1 可完全分解为一次项之积： 8 第二章r s 码原理 x 矿一一1 = ( x 一口o ) ( x 一口1 ) ( x c t , q ”一2 ) 定理2 6 扩域g f ( q “) 上元素和的q 7 次幂等于元素q 。次幂的和： ，、 t j = ( ) 9 ，式中，为g f ( q ”) 域元素。 定理2 7 如果是g f ( q ) 上p 次多项式f ( x ) 的根，那么卢的 g7 ( f = l ，2 , - - - , ，p ) 次幂也一定是f ( x ) 的根。 如果一个首一多项式的所有根来自同一个芦根系，称这样的多项式为卢的最 小多项式，最小多项式在g f ( q ) 中一定是既约的。 2 2 循环码原理 2 2 1 线性分组码 ( n ，k ) 线性分组码是把信息流的每k 个码元分成一组，通过线性变换，映射 成由n 个码元组成的码字。从空间的角度，每个码字可看成是n 维线性空间中的 一个矢量，n 个码元正是r 1 个矢量元素。长度为k 的q 进制信息组有q 。种组合， 构成g f ( q ) 上的k 维k 重矢量空间；长度为n 的q 进制1 1 重矢量有q 8 种组合，构 成g f ( q ) 上的1 1 维n 重矢量空间。编码的任务就是在n 维n 重空间的矿个矢量中 选择q 个构成一个子空间或码集c ，使之与k 维k 重矢量能构成一个一一对应的 映射。因此编码算法的核心问题是：( 1 ) 寻找最佳的码空间，或者说是寻找最佳的 一组( k 个) 基底以张成一组码空间。( 2 ) k 维k 重信息组空间的2 个矢量以何种 算法一一对应地映射到k 维1 2 重码空间c 。由于上述映射是两个线性空间之间的 线性变换，“线性分组码”由此得名。 为了与代数运算接轨，通常线性分组码可按降序排列为c = ( c 。，c 。，c o ) ，在 串行收发时，序号大的码元在先，序号小的码元在后。线性分组码的编码可以表 示为以下的线性方程组：c ，= 鱼) ，+ + 。g 。，+ r r l 。g 。j ( ，= h l ，1 ，o ) ( 2 - - 1 ) 9 第_ = ：二章r s 诲豫理 也可以用矩阵表示为：c = 【，- ，q ，c o = m g = 【一；溉m o l g 。一一g 。g o 7 ( 2 2 ) 式中g 称为该码的生成矩阵( k x n ) ，其表这式为： g = 【g h g i g o 7 = k 一1 ) ( n 一1 )g ( k i ) 1g ( k t ) o g l ( 月一 1 111 g l i9 1 。 g o ( 月一1 1 g o lg o o ( 2 3 ) 按分块矩阵运算法爱将式( 2 - - 2 ) 展开可褥：。= h 繇一；+ v + m ；虽+ m 。g o ( 2 - - 4 ) 可见，任何码字都怒生成矩阵g 的k 个行矢登的线性组合。只要这k 个行矢量线 性无关，就可以作为k 个基底张成一个k 维n 煎空间，它魁n 维i q 重空间的一个 子空润。基底并不壤一。将基藤线瞧缝合，选凑蒸孛k 个线性无关夔矢爨仍戆穆 成基底。从生成矩阵的角度看，就是对g 进行初等行变换厝仍能从信息码映射成 相同的码集，只是映射的对应关系有所变化。据此任何g 都可以化成系统矩阵的 形式： g = 【i s , p 】 1o ol t ： oo p ( k 一1 ) 1 p f 一1 1 0 热lp l o p o ip 0 0 ( 2 4 ) 生成矩阵为系统矩眸的线性分组俩称为系统粥，由 f = m g = m “，m i ，m o ，e 。一“，c 。) ( 2 5j 可以滑出系统码的前k 个码元为k 个信息元。 与任何一个( n ，k ) 线性分缎码的码空闯c 对应，一定存在一个对偶空间d 。 码空澜c 由n 维n 燕空闻的一筑k 个墓底产生，若勇矫秀我窭n k 令鍪溉那么就 可由遮n k 个基底构成对偶空间d ，将这n k 个基底为行向最构成矩阵h 。由对 偶空阀向量的正交性可得c h 。0 其中c 任意码字 ( 2 6 ) 式( 2 8 ) 可以蟊l 来检验一个n 燕向量是否为犸字，困魏鞭也豫为校验簸簿。分 组码译码的依据也是式( 2 - 6 ) 。特别地有g h 7 = 0 ( 2 7 ) 对予生成矩阵形如( 2 - - 4 ) 的系统码有：h l p l t 一+ l ( 2 - - 8 ) 由k 个码元编成的含n 个粥元的码字c = ( “。，c ，岛) 送入信道后，由于各种 1 0 ) ) 一 棘 嘛 瓠默 o 0 ：1 ： o 第二章r s 码原理 干扰，在接收端收到的码字r = ( 名+ ，) 不一定等于c 。定义差错图案 e = ( 巳+ ，e 。，e o ) = ( 一一巳+ ，一c ，r o c o ) = r c ，对于通常用二进制( 或等效于 二进制) 表示的码元，加减等效，所以有：e = r + c ，r ：c + e 代入校验式( 2 6 ) 可得r h 7 = ( c + e ) h 7 = c h 7 + e h 7 = 0 + e h 7 = e h 7 ( 2 9 ) 若接收码无误，必有r = c 即e ：0 及e h 7 = 0 ，此时r i t = 0 。因此r h 7 仅与差 错图案e 有关，而与发送的码字c 无关。定义伴随式s = ( s 。+ ，毛，s 。) = r h 7 = e h 7 伴随式反应的是接收码字的错误情况。s 是一个n k 重矢量，只有2 ”种可能的 组合。而e 是n 重矢量，有2 “个可能的组合。因此，同一伴随式s 可能对应若干 个不同的差错图案e 。从译码的观点来看，接收端只知道r 和日7 而并不知道c ， 根据s 如何有效地推断出c 是译码的任务。译码的一般过程是：先算出s ，再由 s 推断出e ，最后令0 = r + e 而求出0 。线性分组码的编译码过程可由图2 1 描 述： e 图2 - 1 线性分组码编译码过程 2 2 2 循环码的定义及表示 对于一个( n ，k ) 线性分组码，若将其任意一个码字( c 。，c ，c 。) 的码元向右 或向左循环移位一位，所得的( 岛矗+ ，c 2 ，c ) 或( 巳。，c ，c 。，c 。) 仍然是码字，则 称该码为循环码。 将码矢量( c n _ l ， g c i , c 0 ) 与多项式c ( x ) = c 。一，x “十+ c 。x + c o 作一一对应，就得到 了循环码的多项式表示方法。有了多项式表示方法，循环码的移位就可以由解析 式来表示了： 第二章r s 码原理 c o ( x ) 。c n 一1 x ”一1 + 巳一2 工”一2 + c l x - i - c o ，c l ( x ) 2 c n2 x “一+ 0 3 上卜2 + ，一- t - c o x + c n c 。( x ) 为c 。( x ) 循环右移一位后的码多项式，它们的关系可以表示为： c i ( x ) = x c o ( j ) m o d ( x “一1 ) 2 2 3 循环码的性质及构造 将循环码用多项式表示后，可以由近世代数推导出其一系列的性质，由此 可以得到其构码方法。这些性质可以由下面得几个定理来描述。 定理2 8 ( 1 ，k ) 循环码的码多项式是模x ”一1 乘运算下多项式交换环的一个 主理想；反之，多项式交换环的一个主理想一定可以产生一个循环码。 由于主理想的所有元素都可以由一个元素的幂次，或等效于一个元素的倍式 组成，这个元素称为该主理想的生成元或叫做该( n ，k ) 循环码的生成多项式。 生成多项式不是唯一的，但必有一个是次数最低的。 定理2 9 在一个g f ( q ) 域上的( n ，k ) 循环码中，一定存在唯一的次数最 低的n k 次首一码多项式g ( x ) = x ”+ g - k - t x ”“1 + + g l x 十1 使所有码多项式都是 g ( x ) 的倍式，且所有小于n 次的g ( x ) 的倍式都是码多项式。 “所有码多项式都是g ( x ) 的倍式”意味着所有的码字都可以写成 c ( x ) = m ( z ) g ( x ) 的形式，换言之，g ( x ) 一定可以整除所有码多项式c ( x ) ( g ( x ) i c ( x ) ) 。“所有小于i q 次的g ( x ) 的倍式都是码多项式”意味着对于g f ( q ) 上小于k 次的任意多项式，( z ) g ( x ) 一定是码字。 定理2 1 0 ( f i ，k ) 循环码的生成多项式g ( x ) 一定是x “一1 的因式，即一定存在 个多项式h ( x ) ，满足一1 = g ( x ) ( z ) 或g ( x ) l 一1 ) ；反之，如果g ( x ) 是z ”一1 的 n k 次因式，则g ( x ) 一定是某( n ，k ) 循环码的生成多项式。 根据上面的三个定理，可以得到如下的( n ，k ) 循环码构造方法。 ( 1 ) 对x ”一1 进行因式分解，找出其中的n k 次因式。这里x ”一1 不一定存在 n k 次因式，即并不是任意的n ，k 都可以构成循环码。如果r 一1 存在n k 次因式， 它也并不一定是唯一的。 第二章r s 码潦域 ( 2 ) 以找出的n k 次因式为循环码生成多项式g ( x ) ，与信熙多项式m ( x ) 相乘， 霹褥璃多顼式c ( x ) = m ( x ) g ( x ) ，其中m ( x ) 为k - 1 次信惠多磺式： 埘( x ) = 彬 一j 一1 + + 删l x 十m o 。 上述橡造方法缮劐鳃疆蓼邋势i 系绞玛。系统羁蜓鹚多疆式其袁魏下影式 c ( x ) = x n - k 聊( 工) + r ( x ) ( 2 一1 0 ) 这里f ( x ) 是与码字中n k 个校验元相对应的n - k - 1 次多项式，其计算方法如下： 将x n - k m x 诤女以g ( x ) ，褥商式q ( x ) 和余式r ( x ) ，即： x n - k m ( x ) g ( x ) = g ( x ) + r ( x ) g ( x ) ，9 孓目9 ：x n - k ，”( x ) = g ( x ) q ( z ) 十r ( x ) ( 2 - 1 1 ) 主述系绞键环鹚麴产生方法霹皴疆述秀滋下步骧： ( 1 ) 将信息多项式m ( x ) 预乘x ”2 ，即右移n k 位。 ( 2 ) 将x n - k m ( x ) 除以g ( x ) ，得余式r ( x ) ( 3 ) 系统循环码的礴多项式写戒e ( x ) = z ”。m ( x ) ”( x ) 翡形式。 2 3r s 码的构造 2 3 1 用根定义循环码 苁主一节滤三令定理揭示豹矮琢玛懿梅鹦矮律可9 鬣，麴造( n ，k ) | 羹繇羁，善 先要对x ”一1 做因式分解，化为若干个既约因式( z ) 之积，然后直接用其中n k 次既约因式，或鼹几个既约因式会并成一个n k 次非既约因式作为循环褥的生成 多项式g ( x ) 。可咀用数学式描述为：r 一i l = r i 掰小) = g ( x ) ( x ) ( 2 1 2 ) ，”0 这墅，既约因式，( x ) ( j = 0 ，1 一1 ) 分成两部分，它们鲍乘积分别是g ( x ) 和h ( x ) e 然而，这里的m ，( * ) 并不能保证怒一次多项式，也就是并不熊使x n - - 1 完全分解。 缀过多年的研究，人们发现在二元扩域饼( 2 “) 上可以将p 一1 完全分解为一 次因式之积。将一1 在二元扩域舒( 2 一) 上分解，关键是簧找至g 一个n 黔域元素 第二章r s 码原理 a ，满足扩= 1 ，即a 是一一1 的根。当”= 2 ”一1 时，这个域元素a 是本原元；当 ” 2 ”一1 时，a 是非本原元。找到了a 之后，可以将一一1 完全分解： 月一i1 一】 z ”一1 = 兀x - - a 。= 兀m 如) = g ( x ) ( x ) ( 2 1 3 ) i = 0 j f f i o 上式中前半部分为二元扩域上的分解，后半部分则是普通的二元域上的分解。若 ，一1 的某个根口。( f o ，1 ， 一1 ) 又是某个既约因式，( z ) ( ，= o ，一1 ) ，那么必 有： a 为n 阶本原元时：( x d ) j m f ( z ) i 占( j ) j ”一1 = z 2 ”1 1 ( 2 1 4 ) a 为r l 阶非本原元时：( x - a ) l m ，( x ) l g ( x ) l x ”一1 i x 2 。1 1( 2 1 5 ) 以上两式说明：生成多项式g ( x ) 的n - k 个根也是r 一1 的根，只要能够以适当的方 法找出这些根，就可以从这些根得到生成多项式g ( x ) 。 通常，有重根的g ( x ) 不能产生好码，为此要求，一1 无重根。因为如果x 8 1 无 重根，则g ( x ) 肯定无重根。在g f ( q ) 上，z ”一1 无重根的充要条件是n 和q 互素， 所以通常二进制码的码长都为奇数。 由上所述，可以得到用一一1 在g f ( 2 “) 域上的根来构造循环码的方法： ( 1 ) 在x ”一1 的1 1 个根中选取其中的n - k 个根_ ，r 2 ，。0 口1 ) ，i = o ，l ，”一l ； = 1 ，一女 ( 2 ) 找出各根对应的既约多项式_ m ( z ) r 2 斗m ：( x ) ，o 一。寸m 。( x ) 。 ( 3 ) 求出这些既约多项式的最小公倍式：g ( x ) = l c m m ，( x ) ，：( x ) ，一。( z ) 。这里 l c m 指最小公倍式。 2 3 2b c h 码和r s 码的设计 b c h 码是纠错能力可控的纠随机差错码，是循环码的重要子类。该码具有严 格的代数结构，生成多项式g ( x ) 与最小距离d 有着密切关系，设计者可以根据 对d 的要求，轻易地构造出具有特定纠错能力的码。 b c h 码的构造建立在上节所述的由根构造循环码的理论基础上。q 进制b c h 第二章r s 码艨理 码的定义如下：对于g f ( q ) 域循环码鲍生成多项式g ( x ) ，若含有2 t 个连续幂次的 根口，。”“，a “，则由g ( x ) 生成的( n ，k ) 循环码称为q 进制b c h 码。若根a 为本原元，则称该码为本原b c h 码，其码长为h = 矿一1 。麓a 为非本原元，则称 该璐为菲本骧b c h 褥，萁码长n 楚矿一i 的因予。 r s 码是b c h 码最重要的一个子类。它是m - - 1 时的q 元本原b c h 码，r s 码具 有以下参数： 码长：n = q l 校验位：n k = 2 t 簸小疆离：d m m = 2 t + l 生成多项式： g ( j ) = ( j d 6 0 ) ( 蔗一a 6 0 十1 ) ( j a 6 0 _ 2 一) = 一t 工”一十q e l 善”一1 1 + t t + a t x + a o 式中，g ( x ) 的各次系数q ( 扛o ，”一曲 o ，1 ，貔，堪2 ，a 即) 。 组成r s 码字的q 一1 个码元均取值于q 阶有限域，q 能索数或素数的幂次。 由予臻遂上兹多遴铡往往是由镶怠源懿二遴露变换寒的，艨以实际中一般取q 为2 的幂次。 由上述r s 码的构码方法可知，只需根据设计要求的最小距离以及码长等参 数，经可褥至r s 獭躲生成多矮式。当r s 码黪弱长不满足需求时，可蝰( n ，k ) r s 码缩短为( n - m ，k - m ) 码来满足要求。 得到了生成多项式后，可以方便地用循环码的编码方式( 式2 - - 1 0 ) 实现r s 码懿缡码。 2 4r s 码的译码 r s 码静译码怒应翔r s 鹑辩最复杂的一个部分。r s 鹞的译码方法可叛分为薅 域译码和频域译码两种。频域译码是把码字褥做一个时域数字序列，对其进行有 限域的离散傅氏变换( d f t ) ，将它变换到频域，然后利用其频域特点译粥。比如， 特镁之一是时域溺多项式静一个撮与频域谱多顼式静一个零分量对瘦。这样，可 通过对频域伴随式的运算，解出指示差错位鬣的关键方程，再通过离散傅氏变换 第二章r s 码原理 还原成时域的纠错信号。 时域译码是把码字瓣成时间轴上的信号序列，利用码的代数结构进行译码。 蠢于取舂隈域离敬薄氏交换增撩了笺絷度，频域译鹳的实王冕一般较露域译褥复 杂，因此采用f f t 的频域译码只是谯某些特殊情况下对特定的码长( 如n 为2 的幂次) 译码对优于时城译码。而在一般情况下，应用最广泛的怒时域译码。1 9 6 0 年，镀褥森营先觚理论上解决了二滋镧b c f t 璃靛哼谶译码润蘧。箕蜃，蠢人怒它 推广到多进制b c h 码。1 9 6 6 年，伯利坎普提出了迭代译码算法，这个算法成为 了实用的经典算法，其艨的许多算法都以其为原型。 司警逶分组码一群，鹣褥的译弼舞法瞧分鸯三步：蓄先，宙缓浚多项式r ( x ) 计算伴随式s ( x ) ：其次，由伴随式得到差错图样e ( x ) ；最后，得到码字估值 c ( x ) = r ( x ) 一e ( x ) 。 2 4 i 从码多项式r ( x ) 计算伴随式s ( x ) 接救多鞭式可以表示为r ( x ) = e ( x ) 吨( x ) 。 其中： r ( 算) = k 一1 工肛1 十一2 x 。2 + - + 呓x + c ( x ) = 矗一 x 州+ 岛。2 x 4 - 2 + 。一十岛( 2 - - 1 6 ) 西( x ) = 矗一l x 舯1 + 2 x ”一2 + + q x 牛气 由循环码的性质可知码多项式c ( x ) = m ( x ) g ( x ) ，所以g ( x ) 的2 t 个连续幂次的根 球”，a 一，搿e 一一1 也是麓多竣式e ( x ) 懿援翻。稳这2 t 个缀分爱代入e ( x ) 霹怒： c ( a 6 。) = c 。十q 口6 。+ c z a 2 如+ + c n 一1 盘肿1 1 = 0 c ( a 占0 1 ) = 吒十c l 扩1 + c z 州+ + q 川州= 0 ( 2 1 7 ) c ( a 5 。+ 2 一1 ) 然c 0 + g c t 6 * 2 4 一+ c 2 c t 2 6 * 2 卜+ + 矗一i g 8 一x 6 孙2 = o 将上面的方程组写成矩阵形式为c a = 0 ，其中c = ( 岛c c ：q ，) 为码宇矢爨。a 为峦2 t 令裰懿雾次秘藏戆2 t n 矩跨： i1睇” 爿：1 1 ，蹦? “ l1 矿“ 口】 口( “一x b o * 1 ) “x “2 “， 1 6 ( 2 1 8 ) 聃 州 讲 蒜：眠 第二牵r s 玛原理 可见a 为范德蒙矩阵，一定是满秩矩阵，其秩为2 t ，亦即a 的2 t 个列向量线性 无关。又由( 2 1 7 ) 可以看出任何码矢量与a 7 相乘都等于零，暇此a 等效予校 验矩阵鞋。蠢了 l 可戳褥翻俘隧式为； s = ( 墨，茸，是，) = ( ，q ，一。) h 7 = ( e o ，e 。，e n 1 ) 尉7 ( 2 - - 1 9 ) n - i 箕中s = 强+ 薯群6 抖卜1 + r 2 a 2 拍甜。十r 。一 搿和4 “抽“一= 描婶“卜1 。( 2 - - 2 0 ) 扣o 即s = r ( x 比f r ( a b o + i - i ) = e ( a b o 。- i - i ) i = 1 ，2 ，2 t 2 4 2 由s ( x ) 求e ( x ) ( 2 2 1 ) 由( 2 - - 1 6 ) 及r ( x ) = c ( x ) 吨( x ) 褥= 岛+ g ，( f = o ，l ，n 1 ) 。对于q 元r s 弼， ，c ，q ( 江o ，l ，n 1 ) 均商q 种可能取值。因此，纠锚时不仅要考虑差错位置，还 需要考虑熬错幅值。假设有v 个差锚分布在点，五， 位置上，简差错幅值分别 为勺l ，巳2 ，撮垂e ( x ) = x “+ x 。+ + e l x ( o 五 辑1 ) ( 2 2 2 ) 令x “= , e a t * 1 ，2 ，v ) 则嚣0 ) = 届+ e 。热+ + 气鼠 由式( 2 2 1 ) ( 这里取b o = 1