（光学工程专业论文）前向纠错技术在高速光纤通信系统中的应用研究.pdf

华中科技大学硕士学位论文 摘要 光纤通信自问世以来，一直向着两个目标不断发展。一是延长中继距离，二是提 高传输速率( 容量) 。光纤的吸收和散射会导致光信号的衰减，光纤的色散将使光脉 冲发生畸变，导致误码率增高，信号传输质量降低，限制通信距离。为了满足长距离 正确传输的需要，人们必须克服许多物理限制因素。这些物理限制因素包括辐射噪声 积累、色度色散、非线性效应和偏振模色散等。面对这些因数的挑战，为了增大传输 容量和延长无电中继距离，科研人员开发出了多种新技术，包括新型光纤、分布式拉 曼放大技术、前向纠错( f e c ) 技术、新型编码调制技术、光孤子传输技术、色散补 偿和非线性控制技术等。 本论文针对光纤技术的发展，主要讨论前向纠错( f e c ) 技术。r r u t 标准中规 定用于高速光纤通信系统中的前向纠错码主要是b c h 码和r s 码。而b c h 码和r s 码的应用有多种形式，为了找到适合的应用方法，本论文中，首先对信道编码和前向 纠错的基本原理作了简单的综述。通过对编码理论的一些分析，解释了b c h 码和r s 码的应用范围和基本方法。接着对各种f e c 技术进行了详尽的分析和总结，在对几种 f e c 技术分析和现有的些实现方法的基础上，提出了增强的f e c 设想。有了设想 后，分析了其在系统中可获得的增益，并由实验验证了这些分析结果，其结果与理论 分析是一致的。通过分析和实验得出增强的f e c 技术优于其他前向纠错( f e c ) 技术。 同时，在以往大多基于软件实现f e c 的基础上，提出了基于硬件的实现方法，设计出 了该实现方法的硬件逻辑电路。 关键词：前向纠错编码b c h 码r s 码增强f e c 高速光纤通信系统 华中科技大学硕士学位论文 a b s t r a c t s i n c et h ef m e rc o m m u n i c a t i o nw a si v e n t e d ，i th a sb e e ne v o l v i n gi n t ot w o g o a l s f 地呜 e x t e n dt h er e l a yd i s t a i l c e s e c o n d ，i c r c a s et h et r a i l s m i s s i o ns p e e do fm t e p a c i t y ) f i b e r o p t i c a la b s o i p t j o na n ds c a t t e i i gw o u l dl e a dt o 山ed e g r a d a t i o no ft h es i 印a l ，t h cd i s p c s i v e o fo p t i c a lr a yb u r s t sw o u l do c c u rt od i s t o n i o n s ，w h i c hr e s u l ti nt l l ei n c r c a s ee d r r a t e sa n d r e d u c t i o o fs i g a lt r a i l s m i s s j o nq u a l i t y ，a n dt h i sl i m i t st h ec o m m u i c a t i o nd i s t a n c e i n o r d e rt of l l l f i nt h en e e do f 也el o n 争d i s t a n c et 删1 s m i s s i o nc o m 斌l y w em u s t0 v e r 咖e m a n yp h y s j c a l j i 】n i t e df a c c 0 i s t h c s c p h y s i c a jf a c t o r s i n d u d et h e r a d i a l i o nn o i a c c u m u l a t i o n ，c h r o m a t i cd i s p e r s i o n ，n o n l i n e a re f f - c c t 锄dp o l a r i z a t i o nm o d ed i s p e r s i o na l i d s oo n i nt h ef a c eo ft h e s ec h a l l e n g e s ，i no r d e rt oi n c r c a s et h et m i l s m i s s i o nc a p a c i t y 趾d e x t e n dt h ed i s t a l l c e ，t h er e s e a r c h e r sh a v ed w e l o p e dav 蕊e yo fn e wt e c h n o l o 酉e s ， 砌u d j n gn e wt y p e so f 龇o p t j c a l 纳e r ，舶e rd i s t 曲u t e dr 砌a na m p 埘e rt e c h n o l o g y ， f o n v 盯de r f o rc 0 e c t i o n ( f e c ) t e d m o l o g y ，an e wc o d em o d u l a t i o nt e c h n o l o g y ，t h co p t i c a i t r a n s m i s s i o nt e d m o l o g y d i r o i n a t i cd i s p e r s i o nc o m p e n s a t i o na j l dt h en o n i i n e a rc o n t r o l t e c h n o l o g 弘 t h ep a p e rf o c u s c so nt h ed e v e l o p m e n to fo p t i c a l 矗b e rt e c h n 0 1 0 9 ya dm 嘲l yd i s c u s s e s t l l ef o 州a r de r m rc o e c t i o n ( f e c ) t e c h n o l o g y - n eb 髂i cf e cc o d e ss e tb ym j - ts 胁d a r d s f o r i nt h eh i g h - s p e e dn b e fc o m m u n i c a t i o ns y s t e ma r cb c hc 0 d ea i l dr sc 0 dc n e r e 盯c m a l l yf o 瑚s d fb c hc o d e 柚dr sc o d e 1 no r d 盯t o 丘n ds u i t 曲l ea p p l i c a t i o n s ，t h ep a p e rn r s t l y g i v e sas u e yt om cb a s i cp r i n c i p j e so ft h ec o d i n ga n df e ct e c h n o l o g y t u 曲a n a i y z i n g t h e d i i l gt l l e o 珊i te x p l a i n st h cm 萨o fa p p l i c a t i o na i l db 鹪i cm c t h o d so fb c hc o d e 砸l d r sc o d e i ta n a l y s e sa dc o n c l u d e sa l lk i n d so ff e ct e c h n o l o gy 0 nt h ef o u d a t i 0 o ft h e a i l a l y s i sa n ds o m ep r a c t i c a lm e t h c h d sa v a j l a b l e ，i tp m p o s e st h ec o n c e p t i o no fs u p e rf e c w 沛 t h ec o n c e p t i o n ，i ta n a l y z e si h ep o s s i b l eb e n e f i t so b t a i n e d 丘d mm es y s t e m ，a 1 1 dp m v e st l l e r c s u l t so ft h ee x p e r i i i l e m t st ow l l i c hi st h es a m et ot h et l l e o r c t i c a la n a l y s i s a n di tf i n a l l y d r a w sac o n c l u s i o nm a ts u p c rf e c t e c h n o l o g yo b t a i c d 舶ma n a l y s i sa n de x p e d m e n t si s s u p e r i o r t oo t h e rf o 九v a r de r i d fc o r r e c t i o n ( f e c ) t e c 王l i l o l o g y a tt h es 姗et i m e ，o n f o u n d a t i o no ft h ew j d e l y - u s e ds o 脚a r e b a s e df e c ，“p r o p o s e st h ch a r d w a r e - b a s e dm a t h o d a i l dd e s i g n si t sh a r d w a r el o 西cc i r c u i t s k e yw o r d s ：f b 聊a r de h o rc o 玎c c 主o n c o d j n gb o s e - 曲a u d h u r i 一 1 0 c g e n h ec o 如 r e e d - s o l 加o nc o d e s u p e rf e c h i 曲一s p e e df i b e rc b 瑚l m j c a t i o s y s f e m 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：夕妻跣 日期：孙巧年尹月c 阳 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于， 不保密时。 ( 请在以上方框内打“”) 学位论文作者签名：夕磬吕欠 日期：细6 年乎月，扩日 指剥嗽：啭七剜仍 日期彻5 年毕月跖日 华中科技大学硕士学位论文 1 1 纠错编码研究的意义 l 概论 随着数字通信、数据处理和计算机通信网的飞速发展，用户对数据传输和存贮的 可靠性提出了更高的要求。过去通过改进加工技术、线路技术、机械技术和提高元件 的可靠性等方法，来提高系统的可靠性。实践证明，它虽然是提高可靠性的一种途径， 但是，利用这种方法来提高可靠性是很困难的，原因是它不仅要花费很高的代价，而 且也很难获得极为理想的效益。为此，如何提高整个系统的可靠性，已成为一个迫切 需要解决的问题。 目前，提高系统可靠性最盛行的一种方法是采用纠错编码技术。由于采用纠错码 能有效地提高通信系统的可靠性，故日益受到人们的重视。自6 0 年代以来，在这方 面发表了很多有价值的论文。最近几年来，由于代数理论的应用，为纠错编码提供了 坚实的理论基础：大规模集成电路的发展，为纠错编码提供了重要的物资基础；尤其 是编、译码器可用计算机由软件来进行模拟，更促进了纠错编码技术的应用和发展。 香农证明，在噪声信道上如果信源用固定速度r 发送信息，而信道容量为c ，当 r k ) 使a h = 铲，于是有：a “= a k a - k - e 。 从而群g ( a ) 中的元素只有e ，a ，a 2 ，a h * 1 总共h - k 个有限元素。此地我们称该群为有限 循环群，并称满足a “= e 的最小正整数n 为有限循环群元素a 的级。 对于一个n 阶有限循环群，群中的每一个元素的级必是群的阶数n 的因子，在此 不再证明。n 阶有限循环群中的每一个n 级元素称为该有限循环群的n 次单位原根。 2 ) 域多项式的定义和有关概念 定义：含有一个未知数x 的域f p ( g 啦) ) 上的多项式定义为： ，o ) = ，+ 一一”1 + + 矗x + ，0 正t i = 0 ，1 ，2 ，l 。 多项式次数：称系数不为零的x 的最高次数为多项式f ( x ) 的次数。 首一多项式：称最高次数的系数为1 的多项式为首一多项式。 既约多项式：设f ( x ) 是次数大于零的多项式，若除了常数和常数与其本身的乘法 以外，再不能被域f p 上的其他多项式除尽，则称f 伍) 为域耳上的既约多项式。 最大公因式：若多项式h ( x ) 是能除尽f ( x ) 且能除尽窖( x ) 的所有多项式中次数最高 的首一多项式，则称h ( x ) 为f ( x ) 和甙x ) 的最大公因式。 最小公倍式：若多项式h ( x ) 是能被f ( x ) 除尽且能被g ( x ) 除尽的所有多项 式中次数最低的首一多项式，则称h ( x ) 为f ( x ) 和g ( x ) 的最小公倍式。 多项式剩余类环：以一个k 上的多项式f ( x ) = 岛+ x + 一为模的剩余类全体构成 一个环，则此环为多项式f ( x ) 的多项式剩余类环。 定理：若n ( n o ) 次首一多项式f ( x ) 在域g f ( p ) 上既约，则由x ) 为模所组成的多项 式剩余类环是一个有p n 个元素的有限域g f ( p n ) 。( 在此不再证明) 例如：g f ( 2 ) 上既约多项式“x ) = x 2 + x + 1 ，以它为模可产生一个有2 2 个元素的g f ( 2 2 ) 有限域，该域的4 个元素为：o ，1 ，x ，x + 1 ，它们之问的加法乘法运算如表2 1 所示。 华中科技大学硕士学位论文 表2 1 以f ( x ) = x 2 + x + 1 为模的元素及其相互运算 +0 1xx + l 0 o1xx + 1 l10 x + 11 xxx + 101 x + 1x + 1x10 x 01xx + 1 o 000o l01xx + 1 x0 x x + 11 x + 10 x + 1 11 3 ) 有限域的乘法结构 定义：域中非o 元素所构成的乘法群的阶数称为域中该元素的级。 定义：若a 为域g f ( q ) 中的n 级元素，则称a 为n 次单位原根。如果a 的级为q 一1 ， 则称a 为原域元素。 多项式的分解：设a 是g f ( q ) 的n 级元素，则g ( a ) = 1 ，a ，a 2 ，a 且。1 ) 是一个由a 生成 的循环群，且此循环群中n 个元素都是x “1 的根，这样x o 一1 可以分解为： 一1 x “一1 2 兀。一口) 。 4 ) 有限域的加法结构 在域g f ( p ) 中必有一个单位元e ，满足n e = o 的最小整数n 称为域的特征。可以证 明：域g f b ) 的特征为p ，且域中的每一个元素a ( a ，o ) ，满足n a = o 的最小正整数n 为 域的特征p ，我们把n 称为元素a 的周期，可见域中每个非零元素的周期都相同为p 。 基域、扩域：以p 为特征的域是g f 口。) ，m = 1 ，2 ，称g ) 为域g f ( p “) 的基域， g f ( p m ) 为g f 0 ) 的扩域。 费尔马定理：对g f ( p ) 中的任何元素，恒有珊，= 珊 最小多项式和本原多项式：设， ) 一善舡i ，z g f ( p ) a 若p 特征域的元素是 方程f ( x ) 的根，则对于一切自然数n ，m 矿也必是f ( x ) 的根。但多项式f ( x ) 的次数k 是 华中科技大学硕士学位论文 有限的，因此方程在某一有限域上的根必有限，这表明在下述根序列：，m 一，r ， ，中必有重复。由费尔马定理可知，若g f ( p m ) ，则有，z 珊，因此，p ， r ，”1 ，。= 共m 个，必是g f ( p “) 的共轭根系。系数取自g f 上，且 以为根的所有首一多项式中次数最低的那个多项式我们称之为的最小多项。如果 是g f ( p m ) 的本原域元素，则m 的最小多项式又称为本原多项式。可以推导出共轭根 系m ，mp ，r ，m ，“中每个元素的最小多项式均相同。我们在这里介绍一下方 次数的概念，满足p “t 1 ( m o dn ) 的最小正整数m 称为p 对模n 的方次数。 设珊是p 特征有限域g f ( p m ) 中的n 级元素，而m 是p 关于模n 的方次数，则甜的 m 一1 最小多项式m ( x ) 是m 次多项式，且：坍o ) = 丌o w 一) ，即的最小多项式m ( x ) ， t 矿 在g f ( p m ) 中可完全分解成一次因式的乘积，我们称为m ( x ) 的分解域。 如果是g f 口4 ) 的本原域元素，则g f ( p 4 ) 中的任何一个元素可以由1 ，2 ， 。”1 这m 个元素线性表示，我们称集合 1 ，2 ，“) 为g f ( p m ) 的自然基 底。 华中科技大学硕士学位论文 3 线性分组码 3 1 线性分组码的生成矩阵、校验矩阵及系统码 一个【n ，k 】线性分组码，就是将信息元以k 个码元为单元进行划分，按照一定的编 码方式( 即按照一定的线性关系) 将这k 个码元变为n ( n ，k ) 个码元。这n 个码元作为 一个信息组，称为此【n ，k 】线性分组码的一个码字。若每个码元可取q 个不同的值，则 共有q 。个码字，n 个码元共有q 。种取值方式。显然q n 个n 重组成了g f ( q ) 上的n 维线 性空间，q k 个码字组成了g f 上的k 维n 重空间，它是q “个n 重所组成g f ( q ) 上的 n 维线性空间的一个子空间。 1 ) 线性分组码的生成矩阵 将k 个信息码元组表示为：m = ( 1 ，m 2 ，m k 1 ，m k ) ，将其编码成n 个信息码元的码 字表示为：c = ( c 1 ，c 2 ，c 3 ，c k - l ，c k ，c 。- l ，c 1 1 ) 。它们满足固定的线性关系，设这种固定 的线性关系可表示为： t k l 畦 e - i e 一善肌函e 。；善乳。，c lz 善帆g 二( 岛g f ( q ) 1 s f s 七，1 sj5 n ) ( 3 _ 1 ) 写成矩阵的形式为： c = 【c 1 ，c 1 ，c l ，c c i i 】 = 【魄m 2 ，。】 占1 1 9 2 1 ： 巩一1 1 巩l ( 3 2 ) 可见当k 位信息码元确定后，可用式3 2 的矩阵关系来生成其相应的码字。等式 右边的k n 阶矩阵我们称之为生成矩阵g 。 即：g = g l j 9 2 j ： g _ 1 j g f j 9 1 2 占2 2 ： 一1 z 如2 ( 3 3 ) 1 4 跏跏； 炒踟 胁鼬； 彬鼬 肌踟； 彬舯 跏跏 一跏 趾胁； 舭趾 华中科技大学硕士学位论文 2 ) 系统码及码的校验矩阵 若每个码字的前k 位为信息位，后n 1 【位为校验位，则该线性分组码称为系统码。 根据系统码的这种性质可以得出，系统码具有以下形式： c j2 小，1 s ，e 七；c 2 著岛，七+ 1 s ，l 。故其生成矩阵具有以下特点： 1 oo t_ o 9 1 ，i + 1 _ 9 1 m 一1g l m l o 1oo 9 2 ，t + l 9 2 m l9 2 ，。 g 昔l ； ；i l o - o 1o g - l “1 g i 1 ，i | 一1 g i 一功 l o o o 1 g t ，h l g t ，1g ， 熙：竺 i k 是k k 阶的单位矩阵，p = i ；。； j 苌：髦：1 ( 3 4 ) 对于系统码，由于当1 ，七时c i = m ，所以式3 1 可以改写为： c 2 善c i + 1 9 ，s ，l 。即c ，一善q 乳j2 0 ，七+ 1 e ，h 。写成矩阵的形式为： 一占1 i + 1一9 2 + 1 一吼+ 1 一占l j + 2一9 2 ，i + 2+ 。一颤+ 2 一占1 j l9 2 ， 一1 一g t ，n 一1 一9 1 一9 2 ，。 一9 1 月 ( 注：酗表示踟的加法逆元， lo o0 01o 0 0 o10 o0 o1 c 1 c 2 ： q - 1 c 一 = 0 如果是二进制码，则其加法逆元为其本身。) 等式 左边的o 一 ) 厅阶矩阵称为系统码的校验矩阵h 。 即：h = 一9 1 女+ 1 一9 1 j + 2 一9 1 n - 1 一9 1 。 一9 2 j + 1 一9 2 i + 2 ： 一占2 一1 一9 2 故对任一码字c ：( c 1 c 2 ，c 。) 一颤j + 1 1ooo 一吼j + 2 o1oo = 【一，一。】 ( 3 5 ) 1 7 训 一反。 ooo1l 恒有：h c t ：0 或c h t o ( 3 6 ) 华中科技大学硕士学位论文 3 2 线性分组码的译码 f n ，k 】线性分组码的译码由以下三个步骤来完成： ( 1 ) 由接收的码字r ，计算伴随式s 。 ( 2 ) 若s = 0 ，表示无误。若s - 0 ，则由s 找出错误图样e 。 ( 3 ) 由e 和r 得出码字的估计值：c = r e ，从而完成译码。 若接收的码字为r ，则定义伴随式s 为： s ：兄h 7 ：化+ e ) h 7 ：c 日+ 删7 。e h 7 。可见伴随式s 完全由错误e 确定，而与发 送的码字无关。现在的任务是如何由伴随式s 得出最接近的错误图样e 。 【n ，k 】分组码的校验矩阵h 是一个o 一七) n 的矩阵： 日= 啊。啊： 也，也，： k 。| 1 1 1 。 2 “如。 吃4 ，1七2吃一i 。一1 吃七。 = 陬 ：吃一，玩】 吃为h 矩阵中第i 列所组成的一个( n k ) 重的列向量。设码字c 中有t 位错误， e 号门，e 2 ，巳州巳) 昌( o ，t l ，o ，q 2 ，0 一，o ，q 。，o ，( ) x 1 董，q 2 ，e ) 贝0 ：s = e 日= 【o ，弓l ，o ，一，q 2 ，o ，0 ，q ，o ，一，0 】 硭 酵 ； 磉。 碟 = q ：+ q ： 三+ - - + 磁 若要求该分组码能纠证t 个错误，则必须满足下述条件：t 个错误的所有错误 图样应该有互不相同的伴随式与之相对应，否则就不能正确地纠错。 也就是，当( 0 ，q 1 ，0 ，弓2 ，0 ，o ，白，0 ，o ) ( 0 ，8 卅o ，勺2 ，o ，o ，8 ，0 ，o ) 时， 有q ，瑶+ q ：壤+ + 珥一e ，1 二+ e ，加五+ + ；，即q ，磋+ q ：日五+ + 联 一巳， j e ，： 五一e j o 。这要求h 矩阵中任意2 t 个列向量线性无关。 1 6 华中科技大学硕士学位论文 当h 矩阵中任意2 t 个列向量线性无关时，则t 个错误的所有错误图样都有各自 不同的伴随式，不同的伴随式与不同的错误图样相对应，从而由伴随式可以找出错误 图样e ，并由c = r e 完成最终的译码。显然这要建立一个伴随式与错误图样相对应的 关系表。 标准阵译码法： 对分组码而言，如何由伴随式s 求出错误图样e 其实比较复杂。当分组码码字长 度很大，错误位数又很多时，就显得更加复杂。这是因为在译码端要建立一个庞大的 伴随式与错误图样相对应的关系表。可以推导出：对一个长度为n 的二进制码，如果 要想其能纠正t 个错误，则要建立含有q + + + q 。1 + 对这种对应关系的译码 表。为此，1 9 5 6 年斯勒宾提出了标准阵译码法，它是一种译码错误概率最小的译码方 法。 【n ，k 】分组码的2 k 个码字组成了n 维线性空间的一个k 维子空间，它可以看成一个 子群。如果以此予群为基础，把整个n 维空间的2 “个元素划分为陪集。首先将2 k 个 码字作为第一个陪集放在第一行，全0 码字放在最左边。然后在禁用码组中挑出一个 n 重e 2 ，将e 2 ，e 2 + c 2 ，e 2 + c 2 。作为第二个陪集放在第二行。再挑出一个在上 述二行中均未出现的n 重e 3 ，e 3 + q ，e 3 + c 2 。作为第三个陪集放在第三行。以 此类推，一共构成2 + o 个陪集，把所有2 “个矢量划分完毕，如表3 1 。我们称c 1 ，e 2 ， e 3 ，e 2 以为陪集首。收到的n 重落到某一列中，则译码器就译成相应于该列最上 面的码字。若发送的码字为c i ，收到的r = c j + e i ，则能正确译码；收到的码字为r = q + e j ， 则产生了错误译码。由于在误码率较低的信道中产生1 个错误的概率比产生2 个错误 的概率大，产生2 个错误的概率比产生3 个错误的概率大，即重量越轻的错误图样 产生的可能性越大。译码器必须首先保证能正确纠正出现可能性最大的错误图样，也 就是重量最轻的错误图样。因此要求挑选重量最轻的n 重作为陪集首，这样就能得到 最小的译码错误概率。 表3 1 标准阵译码表 码字 c ，陪集首 c 2 c 3c 产 禁 e 2c 2 + e 2c 3 + e 2时+ e 2 + 。 用 e 3q + e 3c 3 + e 3c 2 k + e 2 + 。 码 字 f c 2 + e 2 “c 3 + e 2 “g 。+ e 2 + 。 华中科技大学硕士学位论文 4b c h 码和r s 码 b c h 码是循环码的一个大类，是迄今发现的一类能纠多个错误的线性纠错码。它 的纠错能力很强，特别在短的和中等码长情况下，其性能很接近理论值。r s 码是一 类有很强纠错能力的多进制b c h 码。 4 1 系统循环码的生成 1 ) 系统码的生成 系统码的g 矩阵形式为：g 一阪叫。是| 七阶单位方阵，只有这样才能保证 码字多项式的第n 1 次至n k 的系数是信息位，而其余的系数为校验位，即： c o ) _ _ i ，l o 扛”以+ ，0 ) i0 ( m o d 9 0 ) ) ，式中州o ) = 小i - 1 x 卜1 + m m 石卜2 + + 胁一+ 珊。是信 息多项式，( + 魄- 2 ，竹，m 。) 是信息位，而r o ) = + ，4 。1 + 4 2 工“。2 + + x + 是校验位多项式，( 。，。：，r 0 ) 是校验位。故有： ，o ) ；c 0 ) 一m o p ”一小0 p ”( m o d 9 0 ) ) ( 4 _ 1 ) 由上面分析可知系统循环码的构造步骤为： ( 1 ) 首先将信息多项式m ( x ) 乘以x ”得出r 小o ) 。 ( 2 ) 用g ( x ) 除一x ”m o ) ，得到余式f ( x ) ，其各项系数就是所要求的校验位。 任意k 位信息组。，。，惕，肌。) 可由k 个基底矢量( 1 0 0 o ) ，( 0 1 0 0 0 ) ， ( 0 0 0 1 ) 线性表示，这k 个基底矢量相应的信息多项式分别为： ，0 ) = 工“1 ，历：0 ) = 石“2 ，m 。0 ) 一1 。则与这些信息多项式相应的校验多项式分别为 乇o ) = 蔗4 。z “2s 一一。2 ( m o d g o ) ) ，o ) = j ”1 - 一，4 ( m o d g o ) ) 。则相应的码字 多项式为：c 1 0 ) = r - 1 + o ) c 2 0 ) 一_ x j i 。2 + ，2 0 ) ，q 0 ) - 1 + 0 ) 。由它们的系数作 为行向量，便构成了系统循环码的生成矩阵g 。即： g ； 1o oo o ) o1 o o 吒o ) oo 一0 1 吒0 ) ：”o ) 1 lj ( 4 2 ) 华中科技大学硕士学位论文 0 ) 为r i ( x ) 的系数。因而，校验矩阵h 可写成： 日l 暖。r ，i o ，i o ，l t 】= 。【； ，以一t ( 4 3 ) 日z k 0 ) 7 ，r 2 0 ) 7 ，o ) 7 ，l 一。】= ： r ，以一。l ( 4 3 ) 例4 1 ：二进制【7 ，4 】码的生成多项式g ) 一矿+ 工+ 1 ，求系统码的生成矩阵g 和 校验矩阵h 。 o ) = 工6 - z 2 + 1 ( m o d g o ) ) ，2 0 ) 昌z 5 - z 2 + z + 1 ( m o d g o ) ) ， ，3 0 ) 一z 4 - 工2 + x ( i n o d g o ) ) ，4 0 ) 一工3 - x + 1 ( i n o d g ( x ) ) 。故有 g 昌 10 0 0101 01o0l11 0 01o11o 0 o o1o11 f 1 11o1o 0 1 h 。i o 111o1 o l 1 1 1o1o o 1 l 2 ) 由生成多项式的根来分析循环码 设生成多项式g ( x ) 在g f ( q ) 的扩域g f ( q “) 上完全分解为： g ) 一g n 。) o 一：) o 一4 ，) ，且当i ，j 时，口。一4 ，f ，= 1 2 ，( 这里只讨论无重 根的情况) 。由于g ( x ) 产生的循环码的每一码字多项式必是g ( x ) 的倍式，所以每一个码 字多项式必以口。，口：，口， 为根。设码字多项式为 c 0 ) = e 一，。1 + e 一一”2 + + c ，+ c 0 ，则有： c ( 口f ) = c 。一1 口? 。1 + c ：一2 4 7 2 + + c j n i + c o - o ，f 1 2 ，。 即： 4 ：一14 ：一2 口： 口1 1 口；- 14 ；口；口2 1 口；一1口；一2 口；口， 1 c 一一l 巳一2 ： c 2 c 1 c 0 _ o 故循环码的校验矩阵h 又可以写成根的形式 华中科技大学硕士学位论文 日t 硝。1 4 ；1 ； 口；- 1 口1 l n 2 1 ： 口， 1 ( 4 4 ) 由有限域的知识可知：如果a 是g f ( q ”) 中的元素，且a 是g f 上多项式f ( x ) 的 根，则a a ，n r ，n - + 1 也是f g ) 的根。这样式“中的h 矩阵中由口，- ，n r ，口- “所组 成的行可以缩为仅由a 所组成的行即可。因此在g f ( 2 “) 中，h 矩阵可简化为： 日= 口：4 硝一；口1 1 4 ；_ 1口；一2 - 4 ；3 1 4 ；- 1口；一2 口；， 1 ( 4 5 ) 去掉了n l 项 例4 2 ：求g f ( 2 4 ) 上以a ，a 3 为根的二进制循环码。 在g f ( 2 4 ) 上a ，a 2 ，a 4 ，a 8 是同一共轭根系，其最小多项式为珊。0 ) 一茗4 + x + 1 。 口3 ，口6 ，口9 ，1 2 是同一共轭根系，其最小多项式为m ，g ) 一工4 + x 3 + z 2 + x + 1 。故码的生成 多项式为暑0 ) 。c m 唧， ) ，鸭o ) ) ；朋， ) ( x ) = 工8 + z 7 + + 工4 + 1 ， 码长 一三c m ( 1 5 ，5 ) ；1 5 。故编出的码字为【1 5 ，7 】循环码。它的校验矩阵为： 叫嚣。 口1 3 ( 3 ) 1 3 - 砰； t 也 矿园， o o o 1 o o o 1 o o l o 1 o o o o 1 o o 1 1 0 o 1 o o o l o 1 0 o o 1 1 1 1 1 l o 1 1 o 0 0 o l 1 1 o o 1 o o o 1 o 1 l 1 1 o o o 1 o 1 1 o l o 1 o 1 0 1 1 1 1 o 1 1 1 o o o 1 1 1 1 o 1 o o o 1 1 1 1 1 1 o 0 1 1 0 1 1 0 1 0 1 o o 1 1 1 1 1 华中科技大学硕士学位论文 4 2b c h 码的定义及性质 b c h 码的定义：对于任一有限域g f ( q ) 及其扩域g f ( q m ) ，若码元是取自g f ( q ) 上 的一循环码，它的生成多项式g ( x ) 的根集合中含有以下t - 1 个连续根： 如“，口“，4 m “2 ，则此循环码称为q 进制b c h 码，其中，口g f ( 鼋“) 是域中的n 级元素，a “g | f ( 矿) ，0 fs f 一2 ，i i l 0 是任意整数，通常m o = 1 。 一个码的纠错能力，完全由它的最小汉明距离d 曲决定，而b c h 码的d m i n 完全 由其生成多项式g ( x ) 的根决定，因此b c h 码的根与d 劬有密切关系。可以证明，b c h 码的最小码间距离d 。i 。至少为t 。具有t 个误码纠错能力的( n ，k ) b c h 码的最基本 特性可以描述如下： 长度：n = 2 卅一1 ：最小的t 值：h l 】 t m f 。 在实际应用中使用得最多的是码元取自g f ( 2 ) 中的二进制b c h 码。如果取m o = 1 。 f = 2 ，+ 1 ，a 为g f ( 2 “) 上的本原域元素，则以口，口2 ，口2 7 为根的二进制b c h 码的生 成多项式为：占o ) 一三c m ( o ) ，m ：o ) ，聊：， ) ) 。由于在二迸制中，口1 与口“有相同 的最小多项式，所以生成多项式又为：g ( d 一幔o ) 鸭0 ) 。扛) 。码的校验矩阵为： 好一 口“一1日“一2 4 z ( 口3 y 。1 0 3 ) ( 口3 ) 2 1； 0 2 7j 1 ) 肛1( 口2 _ 1 ) 一2 0 2 7 _ 1 ) 2 ( 4 6 ) 例4 3 ：a 是g f ( 2 4 ) 上的本原域元素，它是x 4 + 石+ 1 的根。求码长为1 5 ，且能纠 正3 位错误的二进制的b c h 码。 要想纠正3 位错误，则码的生成多项式必以。，n 3 ，矿为根，所以 g o ) 一竹0 砌，o 砌，o ) ；0 4 + x + 1 z 4 + x 3 + 上2 + x + 1 ) ( ，2 + 工+ 1 ) 1 1 ；1 。矿；押 华中科技大学硕士学位论文 o ) 一o ”一1 ) g ) 一g 一口7 x 一口“) o 一口”) 0 4 “x 工一1 ) ；x 5 + 工3 + z + 1 依式4 2 得出生成矩阵为： g l 校验矩阵h ； 由此可生成一个【1 5 ，5 ，7 】b c h 码。其编码可用图4 1 的1 0 级除法电路或用图 4 2 的5 级编码电路完成。 毛占a 占田矗口占口叩占，孟 殴 输入m ( x ) 图4 - 1 【1 5 ，5 ，7 】b c h 码的除法编码电路 图4 1 电路工作过程如下： ( 1 ) 开始时所有的移存器清为o ，门1 开，门2 关，然后进行移位，送入信息组 m ( x ) 的系数，高次项首先送入电路。它一方面经或门直接输出，另一方面自动乘以x 1 0 1引|川l圳刮o o 0 0 o o o 0 o 1 1 1 1 l 1 0 o o o 0 o o o 1 o o 1 o 1 1 o o o 0 o o o 1 0 o 1 o 1 1 0 o o o 0 0 0 1 o o 0 1 1 o 0 1 o o o o o 1 o 0 o 0 o 0 1 1 1 0 o o 0 1 0 o 0 o o o 1 l 1 o 0 o o l o o o o o o 1 1 1 0 0 0 o 1 0 o o o o o o 1 l 1 0 1 o 1 o o o o o 0 o o 1 1 0 1 0 1 o o 0 0 o o o o o 0 0 o 0 1 0 1 0 l 1 1 0 1 1 l o o o 1 o 1 0 1 1 1 o 1 1 1 o 0 o 1 o o o l 1 1 1 o 1 o 1 1 o 1 o 0 o 1 1 1 o o 1 o 1 l o 1 o 0 0 o 1 o o 0 0 1 l o 1 1 华中科技大学硕士学位论文 后进入除法电路。 ( 2 ) 5 次移位后m ( x ) 的系数全部送入电路，完成了除法作用。此时移存器的内 容就是余式“k ) 的系数，即校验位。 ( 3 ) 此时门1 关，门2 开，再经过1 0 次移位后，把移存器的校验元全部输出， 与原先的5 位信息元一起组成了一个1 5 位的码字。 ( 4 ) 门1 开，门2 关，送入第二组信息组重复上述过程。 图4 2f 1 5 ，5 ，7 1 b c h 码的编码电路 图4 2 电路工作过程如下： ( 1 ) 开始工作时，5 级移存器全清o ，门关闭。接着移位5 次，5 个信息元一方 面直接输出，另一方面进入移存器。 ( 2 ) 移位5 次后，门打开。信息元己送完，停止送入。再移位1 0 次，则1 0 位 校验元全部输出，并与原来的5 位信息元一起组成一个1 5 位的码字。 ( 3 ) 1 5 次移位完后，门打开，再送入第二个信息组，并重复上述的步骤。 4 - 3r s 码的定义及性质 r s 码是一种特殊类型的q 元b c h 码。r s 码是码元取自g f ( q ) 上，其生成多项式 的根也在g f ( q ) 上b c h 码，即码元的符号域和根域一致的一种特殊的b c h 码。它的 生成多项式g ( 力一o 一口“) o 一口“) 0 一口“2 ) ，通常取一1 ，此时它的生成多项 式9 0 ) 一o 一口1 ) o 一口2 ) o n “1 ) 。由此生成一个q 进制的f q - 1 ，q t 1 r s 码，有最小码 间距离d d 。= f 。 例4 4 ：设码的符号取自g f ( 2 4 ) 中的元素，口g f ( 2 4 ) 是本原域元素，它是x 4 + 茗+ 1 的根，构造d 。= 7 的r s 码。g f ( 2 4 ) 中的元素见表4 - 1 。 华中科技大学硕士学位论文 表4 1 以x 4 + z + 1 为模的g f ) 的元素特性表 本原域元素剩余类表示a 多项式表示四维矢量表示 0000 0 0 0 1110 0 0 1 ax0 0 1 0 a 2x 2 a 2 0 1 0 0 a 3， a 3】0 0 0 a 41 + xl + a0 0 1 1 a 5 x + x 2a + a 20 1 1 0 a 6x 2 + x 3a 2 + a 31 1 0 0 a 71 + x + x j1 + a + a 31 0 1 1 a s 1 + x 2 1 + a 20 1 0 1 a 9x + x 3a + a 31 0 1 0 a 1 0 1 + x + f1 + a + a 20 1 1 1 a 儿x + x 2 + fa + a 2 + a 31 1 1 0 a l z1 + x + x 2 + x 31 + a + a 2 + a 31 1 1 1 a 1 3 x + x 2 + x 3 a + a 2 + a 31 1 0 1 a 1 41 + x 31 + a 31 0 0 1 由于d 。一7 ，则码必以口，2 ，n 3 ，口4 ，口5 ，6 为根，则码的生成多项式 g ( x ) = ( x 一口) ( x 一口2 ) ( 工一口3 ) 一口4 ) o 一口5 ) o 一口6 ) 5 算6 + n 1 5 + n “工4 + n 4 2 3 + 6 工2 + 口+ 口6 ，由此生成一个g f ( 2 4 ) 上的1 6 进制 1 5 ，9 ，7 】r s 码。它的系统码的生成矩阵由式4 2 得出： g ； 矿p扣种水矿矿。驴 驴矿驴以冰以北矿水一旷驴驴铲扣卵驴铲扣鹕妒矿矿驴酽酽，矿。矿矿矿水以矿水矿酽驴驴。北水 o o o o 0 o o o 1 0 o o o o o 0 1 o o o o 0 o o 1 0 0 o o o o o l o 0 o o 0 o o 1 o 0 o o 0 o o 1 o 0 o o o o o 1 0 o o o o 0 0 1 o o 0 0 o o o 1 0 0 0 0 o d d 0 华中科技大学硕士学位论文 校验矩阵为： h = g f