（信号与信息处理专业论文）gb206002006数字电视中bch编译码的研究及dsp器件的实现.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 地面数字电视广播系统是广播电视体系中的重要组成部分，它与卫星数字电视广播系 统和有线数字电视广播系统以及其它辅助系统一起相互协同提供全面的受众覆盖，是我国 广播电视综合覆盖网的重要环节。经过长达7 年的艰苦攻关，在经历多次的实验室测试、 场地测试后，相关管理部门于2 0 0 6 年8 月1 8 日颁布了g b 2 0 6 0 0 2 0 0 6 数字电视地面广播 传输系统帧结构、信道编码和调制国家强制标准( 下称国标) 。考虑到提高数据传输效率 并尽量降低信道的误码率，我国数字电视地面广播系统的前向纠错( f e c ) 由b c h 码和 l d p c 码级联而成。因此，本课题的研究很有现实意义。 本文较为系统的介绍了b c h 码的编译码算法，重点是其在中国数字电视地面广播传 输标准中的应用及d s p 器件的实现。本文首先介绍数字电视的基本内容、全球数字电视标 准的区别和差错控制编码的基本理论。然后在第二章对b c h 码的编码和译码进行详细的 理论分析研究，提出b c h 译码器的基本实现方法。接着第三章介绍中国数字电视地面广 播传输标准的基本内容、无线衰落信道的特性以及符合该标准的b c h 编译码器的设计， 并给出仿真性能结果。而第四章介绍t m s 3 2 0 v c 5 4 0 2d s p 硬件的结构以及基于d s p 器件 的b c h 编码器的实现。最后对本次设计作总结和展望。 关键词：数字电视，前向纠错，b c h 码，错位多项式，d s p 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t d i g i t a lt e l e v i s i o nt e r r e s t r i a lb r o a d c a s t i n gs y s t e mi so n eo ft h em o s ti m p o r t a n tp a r t so f b r o a d c a s t i n gs y s t e m 。d v b t ，a sw e l la sd i g i t a lv i d e os a t e l l i t eb r o a d c a s t i n gs y s t e ma n dc a b l e t e l e v i s i o nb r o a d c a s t i n gs y s t e m ，h a v ep r o v i d e da nw h o l ec o v e r a g ef o rt e l e v i s i o na u d i e n c e sa l l o v e rt h ec o u n t r y a f t e r7y e a r sh a r dw o r k i n g 。t h en a t i o n a ls t a n d a r dg b 2 0 6 0 0 - 2 0 0 6 一( ( f r a m i n g s t r u c t u r ec h a n n e lc o d i n ga n dm o d u l a t i o nf o rd i g i t a lt e l e v i s i o nt e r r e s t r i a lb r o a d c a s t i n gs y s t e m ) ) w a sp r o m u l g a t e da ta u g u s t18 m , 2 0 0 6 ，w h i c hh a sp a s s e dan u m b e ro fe x p e f i m e n t si nl a b o r a t o r i e s a n do n s i t e i no r d e rt oe n h a n c et h ee f f i c i e n c yo fd a t at r a n s m i s s i o na n dl o w e rt h ee r r o rc o r r e c t i n g p r o p e r t yp r o b a b l y ，t h ed i g i t a lt v t e r r e s t r i a lb r o a d c a s t i n gs y s t e m sf e cs y s t e mu s e di nc h i n ai s b a s e do nl d p cc o d e sc o n c a t e n a t e dw i t hb c hc o d e s s o ，t h eb c he r r o r - c o r r e c t i n gc o d e t e c h n o l o g yi so n eo ft h em o s ti m p o r t a n tt e c h n o l o g i e su s e di nt h en a t i o n a ls t a n d a r d t h i st h e s i sp r e s e n t sas y s t e m a t i ci n v e s t i g a t i o no fb c hc o d e s ，a n df o c u so nt h ea p p l i c a t i o n o fb c hc o d e si nt h en a t i o n a ls t a n d a r do fd i g i t a lt vt e r r e s t r i a lb r o a d c a s t i n gs y s t e m t h ef i r s t c h a p t e ri n t r o d u c e st h eb a s i cc o n c e p to fd i g i t a lt v 、t h ed i f f e r e n ts c h e m e so fg l o b a ld i g i t a lt v s t a n d a r d s ，a n dt h ef u n d a m e n t a lp r i n c i p l e so fe r r o rc o n t r o lc o d i n g c h a p t e r2c o n c e n t r a t e so nt h e d e c o d i n ga l g o r i t h mo fb c h c o d e sa n di ta l s og i v e st h eb a s i cm e t h o dw h i c ht e l l su sh o wt om a k e ab c hd e c o d e r i nc h a p t e r3 ，t h en a t i o n a ls t a n d a r di n c l u d i n gm a i nt e c h n o l o g i e sa n dt h e c h a r a c t e r so fw i r e l e s sf a d i n gc h a n n e la r ei n t r o d u c e d t h e nad e s i g no fb c he n c o d e ra n d d e c o d e rw h i c hm a t c ht h en a t i o n a ls t a n d a r d ，a sw e l la st h er e s u l t so fc o m p u t e rs i m u l a t i o na r e g i v e n i nc h a p t e r4 t h es t r u c t u r eo ft m s 3 2 0 v c 5 4 0 2a n dt h ee n c o d e ro ft h eb c h c o d e sb a s e d o nt m s 3 2 0 v c 5 4 0 2a r ep r e s e n t e d a tl a s t ，c h a p t e r5m a k e sas u m m a r yo ft h ew h o l et h e s i s k e y w o r d s ：d i g i t a lt v ，f e c ，b c hc o d e s ，e r r o rl o c a t o rp o l y n o m i a l s ，d s p h 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 氇蝠日期：趟：绘! c 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究叠签名：监导师签名：多逸垫! 堑日期：迦墨；丝f 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 数字化是一场世界范围的新技术革命，是全球广播电视的发展趋势，发达国家纷纷开 发推广数字电视。经过长达7 年的艰苦攻关，在经历多次的实验室测试，场地测试后，相 关管理部门于2 0 0 6 年8 月1 8 日颁布了g b 2 0 6 0 0 2 0 0 6 数字电视地面广播传输系统帧结构信 道编码和调制国家强制标准【l 】。 目前国际上关于数字电视地面传输有三个标准，分别是美国的a t s c 、欧洲的d v b 和 日本的i s d n 。各数字电视地面广播标准采用的技术不同，而各有优点。a t s c 标准强调高清 晰度电视接收，在相同的发射功率和覆盖率下，a t s c 标准可达到较高的资料传输速率。d v b - t 标准则强调适应不同的应用要求，因而提供各种参数设定，以适应各种要求。我国拥有巨 大的数字电视潜在市场，国外公司的专家也承认：中国的市场规模足以支撑形成一个新的 数字电视标准。国标的提出体现了自主创新的特点，并能提高系统性能。 对于前向纠错编码技术，a t s c 和d v b 的编码器都是r s 编码器外加一级编码，其实现 简单，成熟度高，成本低，但缺点也很明显：在一个特定的传输信道中，例如编码效率低， 即在相同的载噪匕l ( c n ) 时，每个符号传输的比特数很低，而且离理论上的香农信道容量有 较大的差距。国标的信道编码方案是b c h p b 码和l d p c 内码，与b c h 码的串连，可以使l d p c 码的性能更好，而且在以后相当长的时间里该方案无须改进，可以更好的保护有关国标的 可能的巨大投资，因此对于国标b c h 码的应用研究具有很大的理论和现实意义。 1 1 数字电视介绍 数字电视是从电视节目的采集、制作到电视节目的传输、用户终端的接收及播放全部 实现数字化。数字电视分为高清晰度电视( h d t v ) 、增强清晰度电视( e d t v ) 和标准清 晰度电视( s d t v ) 三大类，用户通过高清晰度电视机，看到的画面质量可以达到演播室 的水平。 在传统的模拟电视中，模拟电视信号通过调制在无线电射频载波上发送出去。广播信 道可以是地面广播、有线电视网或卫星广播。数字电视则是将电视信号进行数字化采样， 其信号的数据率是很高的，演播室质量的数字化电视信号的数据率在2 0 0 m b p s 。要在原模 拟电视频道带宽内直接传输如此高速率的数字信号是不可能的，因此，必须采取两方面的 措施：一是在信源编码过程中进行压缩，利用人类听觉视觉效应去除信号中的多余成分， 1 南京邮电大学硕士研究生学位论文第一章绪论 在不影响收听收看效果的前提下尽量压缩数据率：二是改进信道编码，发展新的数字调制 技术，提高单位频宽数据传送速率。信源编码方面，i e e e 的m p e g 专家组已发展制订了 i s o i e c l l l 7 2 ( m p e g 1 ) 和i s o i e c l 3 8 1 8 ( m p e g 2 ) 两项国际标准。m p e g 1 的输入视频格 式为c i f 3 5 2 x 2 8 8 ，主要用于c d r o m ，v c d 或t i ( e i ) 线路传输，码率为固定的1 5 m b p s ； m p e g 2 供数字电视使用，它支持标准分辨率的1 6 ：9 宽屏及高清晰度电视等多种格式， 其码率可变，为3 - 4 0 m b p s 。 信源编码是把节目源的模拟声像信号变为数字信号，再经过m p e g 2 压缩编码，形成 数字信号源，并根据多个节目传输的要求，编为复用码流。m p e g 2 是广播电视数字压缩 的国际标准，采用不同的层和级组合即可满足从家庭质量到广播级质量不同的要求，其应 用面很广。从进入家庭的d v d 到卫星电视、广播电视微波传输都采用了这一标准。 1 2 数字电视地面广播标准 目前国际上关于数字电视地面传输有三个标准，分别是美国的高级电视系统委员会 ( a d v a n c e dt e l e v i s i o ns y s t e m sc o m m i t t e e ，a t s c ) 、欧洲的数字视频地面广播( d i g i t a lv i d e o b r o a d c a s t i n g - t e r r e s t r i a l ，d v b ) 和日本的地面综合业务数字广播( i n t e g r a t e ds e r v i c ed i g i t a l b r o a d c a s t i n g t e r r e s t r i a l ，i s d n ) 。 1 2 1 欧洲d v b - t d v b t 系统是欧洲数字视频广播组织开发的一系列标准中的一个，此系列标准考虑了 数字视频和音频的传输，以及将来的多媒体节目。此系统工作在现己分配给模拟电视传输 的u h f 频谱内，根据信道编码参数、调制类型和保护间隔的选择，在8 m h z 信道内传输 的有效净比特码速率在4 9 8 3 1 6 7 m b i t s 范围内不等。d v b t 采用编码的正交频分复用 ( c o f d m ) 多载波调制技术。系统具有很多可选择的参数，以适应大范围的载噪比和信道特 性，不仅能处理高斯信道，而且也能适应r i c i a n 和r a y l e i g h 信道。此系统抗干扰性能优 异，不仅能抵抗高电平( o d b ) 、长时延的多径失真，也能克服地势或建筑物反射的回波。系 统支持固定、便携和移动接收。 1 2 2 美国a t s c a t s c 是一套单载波方案。此系统使用单载波调制方案，即八电平残留边带( 8 v s b ) 调 2 南京邮电大学硕士研究生学位论文 第一荦绪论 制，用于单发射机( 多频网m v n ) 实现。它为了在单个6 m h z 频道中传输高质量视频和音频 ( r r d t v ) 以及辅助数据而设计的，用于地面广播和有线分配系统。它能够可靠地在6 m h z 地面信道中传输1 9 4 m b i t s 的数据速率，在有线电视信道中数据速率为3 8 8 m b i t s 。有两 种有效的操作模式：8 - v s b “地面同播模式”便于更好地抵抗n t s c 干扰：1 6 - v s b “高码率模 式”主要用于更干净的有线信道。此系统可以抵抗许多类型的干扰：现存的模拟电视节目、 白噪声、脉冲噪声、相位噪声、连续波和无源反射( 多径) 。系统提供固定的接收，不支持 移动接收。虽然此系统是为6 m h z 频道开发和测试的，但它能应用于任何信道带宽( 6 、7 、 8 m h z ) ，只是相应地改变数据速率。 1 2 3 日本is d n 采用频带分段传输正交频分复用( b a n d w i d t hs e g m e n t e dt r a n s m i s s i o no f d m ， b s t - o f d m ) 。它系统地综合了各种类型的数字内容，每一种可包括从s d t v 到h d t v 的 多节目视频、多节目音频、图形和文本等。系统提供了可选择的调制和误码保护方案，以 适应综合业务的各种需求。系统采用的调制方法称为频带分段传输( b s t ) i o f d m ，由一组共 同的称为b s t 段的基本频率块组成。每段的带宽为b w 1 4 m h z ，这罩b m 指的是地面电 视信道带宽( 6 、7 或8 m h z ，依赖于所处地区) 。例如，对于6 m h z 信道，每段占据 6 1 4 m h z = 4 2 8 6 k h z 频谱，7 段等于6 7 1 4 m h z ：3 m h z 。在o f d m 特性之外，b s t o o f d m 对不同的b s t 段采用不同的载波调制方案和内码编码码率，依此提供了分级传输特性。每 个数据段有其自己的误码保护方案( 内码编码码率、时间交织深度) 和调制类型( q p s k 、 d q p s k 、1 6 q a m 或者6 4 q a m ) ，那么每段能满足不同的业务需求。许多段可以灵活地组 合到一起，提供宽带业务( 例如h d t v ) 。通过传输不同传输参数的o f d m 段群，可以达到 分级传输。 1 2 4 中国d t m b 国标d t m b ( 数字电视多媒体广播) 提供的地面数字多媒体业务包括h d t v 、音频、 视频、数据广播和交互多媒体等，支持多个传送网路协议，例如m p e g 2 和i p 协议集，易 于与其他的广播和通信系统连接。系统通过选择不同的调制方式和地址信息，系统能够支 持固定、便携、步行或高速移动接收，使用单频网和同频道覆盖扩展器缝隙填充器的概念。 系统通过选择不同保护间隔的工作模式可构建1 6 公里和3 6 公里覆盖范围的单频网。系统 采用了创新的时域同步正交频分复用( v d s o f d m ) 单多载波调制方式。这种调制方式，主 3 南京邮电大学硕士研究生学位论文 第一章绪论 要针对地面数字多媒体电视广播传输信道线性时变的宽带传输信道特性( 频域选择性与时 域选择性同时存在的传输信道) 所设计。由于t d s o f d m 适用于具有多径干扰和多普勒频 移的传输信道，因此其同样适用于地面数字多媒体电视广播以外的其他宽带传输系统。 1 3 差错控制编码 1 3 1 差错控制方式 从差错控制的角度来看，根据加性干扰引起的差错分布规律不同，信道可以分为三类， 即随机差错信道、突发差错信道和混合信道。当信道中的加性干扰主要是高斯白噪声时， 错码是随机分布的，而且各错码之间相互独立，称这种信道为随机差错信道。当信道中存 在脉冲干扰或者衰落现象时，错码是集中成串出现的，即大量的错误集中在很短的一段时 间内，不过这种成串错码出现的频率很低，因此成为突发错码。也称这种信道为突发差错 信道。把既存在随机错码又存在突发错码，且哪一种都不能忽略不计的信道称为混合信道。 对于不同类型的信道，应采用不同的差错控制技术。 常用的差错控制方法主要有四种： ( 1 ) 检错重发( a r q ) 接收端在收到的码元中检测出错码时，就立刻经过反向信道通知发送端重发该信息码 元，直到接收端确认收到正确信息为止。所谓检测出错码，是指在若干接收码元中知道有 一个或一些是错误的，但不一定知道该错码的准确位置。这种方式需要反向信道，故其传 输效率和实时性都要差一些。 ( 2 ) 前向纠错( f e c ) 接收端不仅能在收到的码元中发现有错码，还能够自动纠正错码。对于二进制系统， 如果能够确定错码的位置，就能够纠正它。这种方法不需要反向信道( 传递重发指令) ，也 不存在由于反复重发而延误时间，传输效率高、实时性好。但是随着纠错能力的提高，编 解码设备的复杂程度也随之增加，而且纠错设备要比检错设备更为复杂。 ( 3 ) 反馈检验( i r q ) 接收端将收到的码元原封不动地转发回发送端，并与原发送码元相比较。如果发现错 误，则发送端再进行重发。这种方法原理和设备都较简单，但需要有双向信道。因为每一 码元都相当于至少传送了两次，所以传输效率和实时性都最差。 ( 4 ) 混合纠错( h e c ) 4 南京邮电大学硕上研究生学位论文第一章绪论 是前向纠错方式和检测重发方式的结合。如果接收端接收到的码组的错误较少，则自 动进行纠错；如果错误太多超出了码的纠错能力但尚能检测时，接收端就通过反向信道请 求发送端再重发一遍。 1 3 2 差错控制编码的基本原理 差错控制编码的基本思路是，在发送端给被传输的信息附加一些冗余的监督码元，这 些监督码元与信息码元之间以某种确定的规则相互关联。接收端按照这种既定的规则检验 信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就遭 到破坏，从而接收端可以发现错误乃至纠正错误。 1 3 3 差错控制编码的分类 ( 1 ) 按照对信息元处理方法的不同，可以把纠错码分为分组码和卷积码两大类。分组码 是把信源输出的信息序列，以k 个码元分为一段，通过编码器把这段k 个信息元按一定的 规则产生，个校验元，输出长度刀= k + ，的一个码组。分组码用( 以，k ) 表示。每一码组的 校验元仅与本组的信息元有关，而与别组无关。卷积码是把信源输出的信息序列，以( 通常小于k ) 个码元分为一组，通过编码器输出长为( k o ) 的码组。但是该码组的一个 校验元不仅与本组的信息元有关，而且也与其前m 组的信息元有关，称m 为记忆长度，因 此卷积码用( ，k o ，m ) 表示。 ( 2 ) 根据校验元与信息元的关系可以把纠错码分为线性码与非线性码。若校验元与信息 的之间的关系是线性关系( 满足线性叠加原理) ，则称为线性码，否则为非线性码。 ( 3 ) 按照纠正错误的类型可以把纠错码分为纠随机错误码、纠突发错误码，以及既能纠 随机错误又能纠突发错误的码。 ( 4 ) 按照每个码元的取值来分，可分为二进制码与q 进制码。 此外，在分组码中按照码的结构特点，又可分为循环码和非循环码。 若信息组以不变的形式在码组的任意k 位( 通常在最前面) 中出现的码称为系统码，否 则为非系统码。 南京邮电大学硕士研究生学位论文 第一章绪论 1 4 本课题研究的主要内容 本课题研究的主要内容是中国数字电视地面广播传输标准中b c h 编码的应用以及在 d s p 器件上的实现。本文首先介绍数字电视的基本内容全球数字电视标准的区别和差错控 制编码的基本理论。然后在第二章对b c h 码的编码和译码进行详细的理论分析研究，给 出b c h 译码器的基本实现方法。接着第三章介绍中国数字电视地面广播传输标准的基本 内容以及符合该标准的b c h 译码器的设计，并给出仿真性能结果。而第四章介绍 t m s 3 2 0 v c 5 4 0 2d s p 硬件的结构以及基于d s p 器件的b c h 编码器的实现。最后对本次设 计作总结和展望。 6 第二章b c h 编译码原理和算法的研究 b c h 码【2 1 【3 l 是能纠正多个错误的线性分组码，是通过预定的码长和纠错能力来设计的， 有相对来说比较简单成熟的实现编码和译码的方法。 b c h 编码理论是基于有限域代数理论之上的。对于码长( 刀= 9 ”一1 ) 、纠错能力为f 的 本原b c h 编码，设计生成多项式的基本步骤如下： 1 找出一个m 次数多项式并构造g f ( q ”) 2 对于f - 1 ，2 t ，求出相应的极小多项式z o ) 3 g 似2 l c m f l ( x ) ，五( x ) ，石( x ) ，五，( x ) 】为生成多项式( l c m 是最小公倍式的缩写) 本章将对b c h 编译码原理和算法进行分析，结合信道编码理论对各种典型的译码算 法加以比较，提出适合数字电视国标的译码实现方案。 2 1b c h 编码原理 b c h 码的编码和一般的循环码的编码方法相同。设待编码的信息组为： 而= ( m k - i ，m l ，m o )( 2 一1 ) 相应的信息多项式为： 肌( x ) = m 一l z 。一1 + + 强x + ( 2 - 2 ) 每一码多项式c 俐都是生成多项式g 的倍式，且每一个小于等于向砂次的g 例倍式 一定是码字多项式。设生成矩阵为： 召= 瓦f ( 2 3 ) 左边是k k 阶单位方阵。即码字多项式的第胛一，次至，2 一k 次的系数是信息位，而其余 的为校验位，这相当于码字满足： c ( x ) = 一l x ”一1 + + ，z ”一。+ 一t l x ”一一1 + + t o = m ( x ) x 加。+ ，- ( 力- 0 ( m o d g ( x ) )( 2 4 ) 式中 m ( 工) = ，缸一l x 一1 + ，仇一2 z 一2 + + x + ， ( 2 - 5 ) 是信息多项式，( 小，) 是信息位，而 7 直塞唑盥太堂亟班蕉生堂僮论塞箜三童旦h 绳递塑丝堡塑篡选数婴宜 ，( x ) = ，：，一一l x ”一1 + ，：，一t 一2 x ”一一2 + + z + ( 2 - 6 ) 是校验位多项式，相应的系数( ，：，小。，小：，) 就是信息组( 小，惕，m o ) 的校验 位。于是可得 - r ( x ) = - c ( x ) + 所( x ) 扩一暑m ( x ) x ”( m o dg ( x ) )( 2 7 ) 因此，系统b c h 码的编码方法就归结为以下三个步骤： 1 先用x 肛乘以信息多项式m ( x ) ，变成m ( x ) x ”； 2 用生成多项式g ( x ) 除m ( x ) x ”得到余式r ( x ) ，再将其各项系数取加法逆元，就得 到了所要求的校验位： 3 联合m ( x ) x ”和r ( x ) 即得到编码后的码字多项式m ( x ) x ”。+ r ( x ) 。 并不是对于所有的n 和k 都存在相应的b c h 码。如果希望能比较灵活地选择b c h 码 的参数，就要用到所谓的缩短的b c h 码。其基本思路是：使码组前面的若干个码元符号 为0 ，从而可以不发送这些符号。对于一个伽，砂系统循环码，只要令前面的，个信息数字 为0 ，且满足j k ，就可以将伽，砂系统循环码缩短为( n - j ，锄的循环码，称之为缩短码。 缩短之后的循环码往往不再具有循环特性，但是缩短码的纠错能力并没有降低。 2 2b c h 译码原理和算法 b c h 译码算法和过程比编码要复杂得多。设发送码字多项式是 c ( x ) = q l x ”1 + + c i x + c o ，通过信道后，译码器输入端得到的是 r ( x ) = c ( x ) + e ( x ) = ，；，一l x ”1 + + 石+ ，：= q + q ( 2 - 8 ) 式( 2 8 ) 中e ( x ) = 一l x ”1 + + q x + e o 是信道产生的错误图样。译码器的主要任务就是如 何从r 似中得到正确的估计错误图样p 4 x ) = e ( x ) ，然后得到c 俐，由此得到信息组m 俐。 b c h 译码可以分为时域译码和频域译码两种主要方案，对于一般b c h 译码流程中的 各个步骤，可以分别采用不同的方案，而单独就时域译码来说，同时就有很多种方法，这 将在后文中作重点阐述。 一般b c h 码译码过程分为以下几步【4 】： 1 由接收到的r 俐计算校正子s ( x ) ； 8 2 根据校正子s ( z ) 找出错误图样后( x ) ； 3 计算天( x ) 一豆( 石) = e ( x ) ，得到译码器的估值码字0 ，如果e = e ，则译码正确，否 则译码错误。 2 2 1 计算校正子s ( x ) 根据编码理论【2 】【5 1 可知印，k ，明码的每一码字c 都必须满足以下关系： 疗伊= 0 7 或者e 77 = 0 式( 2 9 ) 中疗是码字的一致校验矩阵。 因此收到豆后用该两式中的任一式进行检验 夏。厅7 = ( 弓+ 露) 百7 = 否。7 7 + 豆厅r = 雷7 r ( 2 9 ) ( 2 - 1 0 ) 若雷= o ，则页厅r = 0 ，若霄0 ，则瓦疗r 0 。说明豆厅“仅与错误图样有关，而与 发送的是什么码字无关。因此豆厅7 可用作检测码字出错与否的标志。 令 季= 豆厅r = 五厅7 或i 7 = 豆豆7 = 疗豆r( 2 1 1 ) 称为接收矢量豆的校正子。因此校正子完全由豆决定，它充分反映了信道的干扰情况。 可以看出，若码字受到信道干扰发生错误，校正子的计算结果必为非零。若校正子值为零， 则可认定码字没有发生错误。 在b c h 译码中，校j 下子计算是非常耗费时间和硬件的。其复杂度与编码长度成比 例关系。这些都是由校正子计算的特殊的迭代过程所决定的。 对于g f ( g ) 上的b c h ( n ，盂) 码，码字长度为规，信息字长为k ，最多可纠错个数t ，校 正子多项式的长度为2 f ，接收到的信息多项式为 n - - l r ( x ) = r , x = 名一1 x 舯1 + + r _ i x + r o 设b c h ( n ，动生成多项式以1 ，口，口2 ，口2 卜。为根，则一致校验矩阵为 9 ( 2 1 2 ) r 1 口”1 2 l ： f 【g z , ( 2 t - i x n - i ) 则根据 i 口”一2 ： ( ，岛。，是h ) 7 = j r = 疗豆7 l 口 口( 2 1 - 1 】 1 1 口”一l口” 口 ； ； 2 。一l x n - i ) 口( 2 一l x ”一2 ， 口( 2 t i ) i + r n 2 + + 与+ r o i n 1 口”一。+ k t 2 口”一2 + + q 口+ 珞 口2 卜1 1 ( ”一1 ) + 2 口2 卜x ”一2 ) + + l ；口 n 1 r j c a o ) 7 j = o n 1 l ：i ( 口1 ) 7 j = o 毛 薹n - 1 弓c 口。，7 2 萎c j c 口，。+ 芸e 。c 口7 ，7 = 善8 ，c 口， ，= 。，2 ，一 可知校正子多项式为 ( 2 - 1 3 ) ( 2 - 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 故根据接收到的码字多项式就可求得校正子。 如果从频域角度来观察校正子f 6 】 nn a 为一玎阶元素，式( 2 1 6 ) 可以看作对于接收信 息进行频域变换以后在2 ，个连续位置上的分量。所以求校正子的另外一个方法也得到了， 即通过对接收信息进行频域变换得到厂例， 取出所需要的2 t - 卜n ，丢弃不需要的值。 对于缩短b c h 码，由于被截位置上均为零数据，所以根据接收码字求得的校正子多 l o l， 0 k ；r，。，。l r_，j l 一 一 ， 嘛 = = 、j 一 但 口 l l 二1 一 x s 棚 = 、， x l s f 2 一 f 一 o口 ，l 气 一 i i 口 0 纠脚 = 0 中 其 壶塞塑立太堂亟迎究生堂僮诠塞笙三童旦堡珏绳递理逐理塑篡擅丝塑红 项式与未截短码是一致的，并不影响对后续的错位多项式的求取。 2 2 2 错位多项式和错值多项式的求取 在求出了校正子后，要对式( 2 一1 6 ) 进行求解。若信道产生7 ( 0 7 ，) 个错误，令 巧= 气( o ，7 ) 表示错误值( 气是错误图样e ( x ) 中不为0 的系数) ，为= 口 ( o ，y ) 表示 第，个错误的发生在r ( x ) 中的第六( p 的系数算第一位) 位上，称为错误位置数，则式( 2 - 1 6 ) 可表示为： ， = i + e + + = 巧 ，= i ， 焉= 巧五+ e 而+ + 一= 巧而 ，= i ， h = x 而2 卜1 + k 吻2 卜1 + + _ 2 卜= 巧而2 卜 ，互l ( 2 - 1 7 ) 我们的目的是要由式( 2 1 7 ) q b 的2 f 个方程求出2 厂个未知数，髟( ，= 1 ，2 ，7 ) ，但这 是一个非线性方程组，且0 y t ，可能存在多余项，直接求解很困难，为此引入错位多 项式【3 】 人( z ) = ( 1 - x l x ) ( 1 - x 2 x ) ( 1 - x r x ) = 人o + 人l x + a 2 x 2 + + 人y x 7 ( 2 1 8 ) 若第z 个错误位置x = 而一，则八( 而一) = 0 ，即a ( x ) 的根是错误位置的倒数 x l - i 而，通过求解a ( x ) 的根可确定错误的位置。将人( x ) 展开得到 人o = 1 人l = 一( 五+ 而+ + ) a 2 = 而而+ x j x a + + 一i 人，= ( 一1 ) 7 而而 若而为错误位置，则 ( 2 1 9 ) 人( 西一1 ) = l + 人i 而一1 + 人2 而一2 + + 人，西一7 两边乘以而，则 而，+ 人l 西7 1 + 人2 而7 2 + + a ，= 0 上式两边再乘以z 而7 ，= 0 , 1 ，y - 1 ，则 巧而+ 7 + 人l 髟西p 7 1 + a 2 巧而+ 7 2 + + 人，巧西7 = 0 ， 对，求和得到 壹巧而肿+ 人l 圭 ，皇l ，= l ( 2 2 0 ) ( 2 - 2 1 ) = o ，1 ，7 - 1 ( 2 2 2 ) 巧x + r - i + 人：壹巧习p ，一z + + 人，圭髟而7 ：0 ，：0 ，1 ，7 1 = l，= l ( 2 2 3 ) 由式( 2 1 7 ) 可知，式( 2 2 3 ) q b 的每一和式都是校正子分量，所以式( 2 - 2 3 ) 又可以写成： + ，+ 人l + ，一l + + 人，s i = 0 ，一，= o ，l ，厂一1 或者 人l + ，一l + 人2 一+ ，一2 + + 人，已 按7 展开，则 = 一一+ ， = 0 ，l ，厂一1 a i s r i + 人2 s ，一2 + + 人，8 02 一j ， 人l s + 人2 s ，一l + + 人，& = 一j ，“ a i s 2 ，一2 + a 2 s 2 ，一3 + + 人，j ，一l2 一s 2 y - l 写成矩阵形式为 s l s 2 s ， 或厨天= 一百 s y - i s ， ： s 2 p 2 h 一。 ( 2 - 2 4 ) ( 2 2 5 ) ( 2 - 2 6 ) ( 2 2 7 ) 式( 2 2 6 ) 是一组线性方程，有厂个方程和y 个未知数，该方程有解的充要条件是式( 2 2 7 ) 中的露矩阵满秩。若实际产生的错误个数为，则可以证明系数矩阵庸为满秩。 1 2 ， ， 1 ；a p。l郎囟；咿p。r。l 虚塞鲤鱼太堂亟班蕴生堂僮诠塞筮三童垦h 缠竖亟厘堡塑篡选的鲤塞 结论2 1 如果一u = 1 ，2 ，7 ) 由厂不同的非零数对( 一，髟) 成，则矩阵 s 0 s l ： s y - i s l s 2 s ， 证明：将_ 代入厨 m = yz z 一 p 1 而 ! 五7 。 而 吒7 1 s r - l s ， ： s 2 ，一2 满秩，否则为非满秩。 巧而1 巧西2 骗， x y i x r 巧而卜1 7 巧_ 2 卜2 写0 0 艺 ： 0o 0 0 ： e i 五 i 而 ： ： 1 哆 ( 2 - 2 8 ) ( 2 2 9 ) = 【x 】吲h r 式( 2 - 2 9 ) 中，【x 】和i x 7 1 是范德蒙矩阵，只要每个元素不为0 且不同，则它们的行列式 不为0 ，而【z 】矩阵仅只有所有数z 不为0 时，行列式不为0 。若发生厂个错误，则只有7 个 不同且不为0 的薯和z ，因而厨矩阵满秩，否则不满秩。 证毕。 据结论2 1 可以从式( 2 2 6 ) 的y 个方程中求解出7 个根，从而得到错位多项式a ( x ) 。当 实际发生，个错误时，由所有的校正子墨，是，s ：，组成的，f 阶厨矩阵即为满秩，可求得式 ( 2 - 2 6 ) 1 拘，个根，当实际发生的错误数7 ，时，由所有的校正子，岛，组成的，阶厨矩 阵为非满秩的，只有由部分校正子s is 2 ，s ：，组成的y xy 阶露矩阵为满秩，而求得 人l ，人2 ，人，。 可设错位多项式为： ， 人( x ) = l + a l x + a 2 x 2 + + a ，x 7 = 兀( 1 - x j x ) ( 2 - 3 0 ) 2 t - 12 t l， 并设s ( x ) = s o + s l x + s 2 x 2 + + s 2 ，- l z 2 卜= s i x = ( 艺弓) ( 2 3 1 ) 1 = 0 t = 0 j = o 定义错值多项式 c o ( x ) = s ( x ) a ( x ) ( m o dx 2 7 ) 得到求a ( x ) 的关键方程s ( x ) a ( x ) = o ( x ) ( m o dx 2 7 ) 将式( 2 - 3 0 ) 和式( 2 - 31 ) 代入式( 2 3 2 ) 并展开 c o ( x ) - - - - - s 0 + ( 蜀+ a l s o ) x + ( s 2 + a l _ + 人2 s o ) x 2 + + ( _ 一l + 人l s ，2 + 人，一1 s o ) x 7 1 + ( 5 ，+ 人i s ，一i + 人，) x 7 + + ( 屯，- i + 人i s 2 ，一2 + 人z s 2 t - r - i ) x 2 h 5 c o o + c o a x + c 0 2 x 2 + + 哆一l x 厂一1 + 哆x 7 + + 叻，一i x 2 卜1 由式( 2 - 2 4 ) n - 礅l l - + 人1 0 1 + 人2 一2 + + 人，s o = 0 鼽i + a i s r + a z s r i + + a ，q = 0 ，一i + a l s 2 卜2 + a 2 8 2 ，一3 + + 人，s 2 ，- l 一，= 0 ( 2 3 2 ) ( 2 3 3 ) ( 2 - 3 4 ) ( 2 - 3 5 ) 所以式( 2 3 4 ) 中大于x 川的系数均为0 ，所以d e g ( c o ( x ) ) 7 ，因为d e g ( a ( x ) ) = 7 ，有 d e g ( c o ( x ) ) d e g r l ，对于七= 0 , 1 ，定义- q , + l 为r k 除以r k + l 得到的商 多项式，定义+ 2 为得到的余式，有d e g r , + 2 d e g r , + i ，有关系式 r k = q k + l + l + r k + 2 ( 2 _ 4 5 ) 定义多项式“和咋如下 ( = 仁4 6 ， 廿川训 可以得到以下结论【1 7 1 【18 1 。 结论2 2 d e g r k + d e g t k + i = d e g r o ( 2 - 4 7 ) 证明：据式( 2 - 4 5 ) 可以得到 d e g r k = d e g q 女“+ d e g r k + l ( 2 - 4 8 ) d e g t , + l = d e g q k + d e g t 所以得到 d e g r k = d e g r o - d e g q k - d e g q i l 一d e g q o ( 2 _ 4 9 ) d e g t k = d e g q , 一l + d e g q k 一2 + + d e g q l + d e g t l ( 2 - 5 0 ) 证毕。 结论2 3 吆= + l + v , r o ( 2 5 1 ) 直盛竖电态堂亟主婴红生堂焦坠窑 蔓三重旦垡旦显堕丝丛丝型昱鲨幽! 芝 丛 证明：定义丑和，( 七= l ，2 ，) 如下 最= 匕咋- r , 。) 巩= 三) p 5 2 ， 所以有 最+ 。= 巩只 ( 2 - 5 3 ) 且 巩。u = v k + ) 进一步得到 最+ 。= - 1 一u 名 = 滢跏三= ：) 所以 = - 。，异+ 。( ? ) = 气1 + 咋 c 2 - 5 6 ， 证毕。 根据结论2 2 和结论2 3 可以得到： 嗽) = ( 嚣描煅) p 5 7 ， 有( x ) = ( x ) 气+ i ( x ) ( m o dr o ( x ) ) ( 2 - 5 8 ) 令( x ) = s ( x ) ，( x ) = x 甜，形式与缈( x ) = s ( x ) a ( x )