（计算机科学与技术专业论文）dvbs2中bch编译码的研究与实现.pdf

国防科技大学研究生院学位论文 摘要 本文针对d v b s 2 中使用的b c h 码主要进行了编译码算法、硬件实现和纠错 性能三个方面的研究。在编译码算法研究的基础上设计了符合d v b s 2 应用的可 配置串行和并行编译码器电路结构，并对所设计的电路进行了f p g a 实现。最后 对d v b s 2 中b c h 和l d p c 级联码的纠错性能进行了实验分析和研究。本文在以 上三个方面所完成的主要工作和取得的主要研究成果有： 1 对传统的基于b m 迭代的b c h 译码算法的改进。在传统的b c h 迭代译码 算法中根据迭代过程需要计算的伴随式个数为2 t ，本文在对二进制b c h 码的b m 迭代过程进行深入分析后，发现在其迭代过程中对迭代结果有用的伴随式只有2 t 1 个，最后一个伴随式是不需要的。据此，改进后的译码算法只需要计算2 t 1 个伴 随式，从而实现了对算法的简化。 2 根据b c h 的编码算法分别设计了符合d v b s 2 标准的串行和并行编码电 路。串行编码电路采用移位寄存器实现，并行电路由一个组合逻辑网络和余数寄 存器构成。在此基础上对编码器的动态可配置方案进行了研究，提出了编码器的 串行和并行配置结构。对所设计的两种编码器分别进行了f p g a 实现，8 位并行编 码器的编码速率可达到2 2 4 4 m b p s 。 3 根据改进的译码算法分别设计了可灵活配置多种参数的串行和并行流水译 码器体系结构。该结构对码字参数之间相差较大而造成的流水和配置问题进行了 充分考虑，从而使得译码器的可配置参数范围得到了很大提高。在译码器设计中， 通过对不同有限域上乘法器设计共同点的发掘，设计了支持不同有限域的重构乘 法器电路，比单独设计不同的有限域乘法器节省了硬件资源。对设计好的两种译 码器分别进行了实现和正确性仿真，8 位并行译码器译码速率可达到1 5 2 8 m b p s 。 4 分析了在d v b s 2 中采用b c h 和l d p c 进行级联的原因。首先，对d v b s 2 中使用l d p c 码和b c h + l d p c 级联码进行了性能仿真和对比，仿真结果表明，采 用级联码要比单独使用l d p c 多出o 5 d b 的编码增益；其次，采用与b c h 码具有 相同码长和码率的r s 码与l d p c 进行级联，通过级联的结果来看，采用 b c h + l d p c 级联比r s + l d p c 可获得0 1 d b 的编码增益。 主题词：d v b 8 2 ，b c h 编码器，b c h 译码器，可配置，并行，纠错性能 第i 页 国防科技大学研究生院学位论文 a b s t r a c t st h e s i sf o c u s e so nt h es t u d yo fe n c o d i n ga n dd e c o d i n ga l g o r i t h m s h a r d w a r e i m p l e m e n t a n de r r o r c o r r e c t i n gc a p a b i l i t y o fb c hc o d e ，w h i c hi su s e di n d v b s 2 ( d i g i t a lv i d e ob r o a d c a s t i n g s a t e l l i t e2 ) t h ec o n f i g u r a b l es e r i a la n dp a r a l l e l e n c o d e r d e c o d e ru s e di nd v b s 2h a sd e s i g n e da n di m p l e m e n t e db a s e do nt h es t u d yo f e n c o d i n ga n dd e c o d i n ga l g o r i t h m s f i n a l l y ，w em a k ea ne x p e r i m e n t a la n a l y s i sa n d s t u d yo ft h ee r r o rc o r r e c t i n gc a p a b i l i t yo fb c ha n dl d p cc o n c a t e n a t e dc o d eu s e di n d v b s 2 t h ec o m p l e t e dw o r ka n dp r o d u c t i o no nt h o s et h r e ea s p e c t sa sf o l l o w s 1 、 i m p r o v e d t h et r a d i t i o n a lb c h d e c o d i n ga l g o f i t h m b a s e do n b e r l e k a m p - m a s s e yi t e r a t i o n t h en u m b e ro fs y n d r o m en e e d st oc o m p u t ei s 2 t i n t r a d i t i o n a li t e r a t i v ed e c o d i n ga l g o r i t h m ，w eh a sp a i dm o r ea t t e n t i o nt ot h eb i n a r yb c h i t e r a t i v ep r o c e d u r ea n dd i s c o v e r e do n l y2 t 1s y n d r o m e sa r eu s e di nt h ei t e r a t i o n t h el a s t s y n d r o m ei sn o tn e e d e d a c c o r d i n gt ot h i s ，t h ei m p r o v e dd e c o d i n ga l g o r i t h mo n l yn e e d t oc o m p u t e2 t - 1s y n d r o m e s ，s os i m p l i f i e dt h ed e c o d i n ga l g o r i t h m 2 w ed e s i g n e dt h es e r i a la n dp a r a l l e le n c o d e r so fd v b s 2b a s e do nt h eb c h e n c o d i n ga l g o r i t h m t h es e r i a le n c o d e ri sd e s i g n e dw i t hs h i f tr e g i s t e r s ，t h ep a r a l l e l e n c o d e ri sc o n s i s t e do fac o m b i n a t i o n a ll o g i cn e t w o r ka n dr e m a i n d e rr e g i s t e r s o nt h e b a s i so ft h i s ，w eh a v eas t u d yo nt h ed y n a m i cc o n f i g u r a b l ep l a no fe n c o d e ra n dp u t f o r w a r dt h ec o n f i g u r a b l ea r c h i t e c t u r eo fs e r i a la n dp a r a l l e le n c o d e r t h e s et w ok i n d so f e n c o d e rh a v ei m p l e m e n t e do nf p g a t h et h r o u g h p u to f8b i t sp a r a l l e le n c o d e rc a n a c h i e v e2 2 4 4 m b p s 3 w ed e s i g n e dt h ec o n f i g u r a b l e p i p e l i n ea r c h i t e c t u r e so fs e r i a la n dp a r a l l e l d e c o d e rb a s e do nt h ei m p r o v e dd e c o d i n ga l g o r i t h m t h e s ea r c h i t e c t u r e st a k ead e e p c o n s i d e r a t i o no fp i p e l i n ea n dc o n f g u r a t i o np r o b l e m sc a u s e db ym o r ed i f f e r e n c e s b e t w e e nd i f f e r e n tc o d e sp a r a m e t e r s ，t h i se n l a r g e dt h er a n g eo fc o n f i g u r a b l ec o d e s p a r a m e t e r s w ed e s i g n e dac o n f i g u r a b l em u l t i p l i e ra r c h i t e c t u r e w h i c hc a nb eu s e di n d i f f e r e n tg a l o i a sf i e l d s ，t h i ss a v em o r eh a r d w a r er e s o u r c e st h a ns e p a r a t e l yd e s i g n m u l t i p l i e ri nd i f f e r e n tg a l o i a sf i e l d s t w ok i n d so fd e c o d e rh a v ei m p l e m e n t e da n d s i m u l a t e d t h et h r o u g h p u to f8b i t sp a r a l l e ld e c o d e rc a na c h i e v el5 2 8 m b p s 4 w ea n a l y s e dt h er e s e a o no fu s i n gb c ht oc o n c a t e n a t ew i t hl d p ci i ld v b s 2 a tf i r s t ，w es i m u l a t e da n dc o m p a r e dt h ee r r o r c o r r e c t i n gc a p a b i l i t yo fl d p ca n d b c h + l d p ci nd v b - s 2 ：t h ec o n c a t e n a t e dc o d ec a nd e p r i v e0 5 d bc o d i n gg a i nt h a nu s e l d p cl o n e l yf r o mt h er e s u l to fc o m p a r i s o n t h e n w ec h o o s ear sc o d ew h i c hh a st h e s a m el e n g t ha n dr a t ea sb c ht oc o n c a t e n a t ew i t hl d p c t h ec o n c a t e n a t e dc o d eo f b c h + l d p cc a nd e p r i v e0 1d bc o d i n gg a i nt h a nr s + l d p cf r o ms i m u l a t i o n k e yw o r d s ：d v b s 2 ，b c he n c o d e r ，b c hd e c o d e r ，c o n f i g u r a b l e ，p a r a l l e l ， e r r o rc o r r e c t i n gc a p a b i l i t y 第i i 页 国防科技大学研究生院学位论文 表 目录 表3 1 普通帧中的编码参数1 7 表3 2 短帧中的编码参数18 表3 3 普通帧中的1 6 次最小多项式。1 9 表3 4 短帧中的1 4 次最小多项式1 9 表3 5 码率与m o d c o d 值对照表2 0 表3 6 串行编码器综合结果31 表3 7 并行编码器综合结果3 2 表4 1 通用乘法器和固定因子乘法器综合结果：3 6 表4 2d v b s 2 中最小多项式与其对应的根4 1 表4 3 串行译码器综合结果5 2 表4 4 并行译码器综合结果5 3 表5 一l 普通帧格式下b c h 码的码率5 6 第1 v 页 国防科技大学研究生院学位论文 图1 1 图2 1 图2 2 图3 1 图3 2 图3 3 图3 4 图3 5 图3 - 6 图3 7 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 图4 图4 图4 图4 1 4 图4 1 5 图5 1 图5 2 图5 3 图5 - 4 图5 5 图目录 d v b s 2 中上行链路系统结构图。1 e ( r ) 与足的关系6 系统码的一种结构形式1l 编码器外部接口图2 1 b c h 码的编码器电路2 2 并行b c h 编码器简化结构图2 5 可配置串行编码电路2 8 可配置并行编码电路结构。 2 9 串行编码器仿真波形图3 0 并行编码器仿真波形图3 1 m 维二元矢量的模2 乘法3 4 不同有限域上的乘法器重构3 7 d v b s 2 中b c h 译码器体系结构3 9 基于有限域乘法的伴随式计算电路4 0 基于最小多项式除法的伴随式计算电路4 2 b m 迭代算法流程图4 3 无逆b m 迭代算法的硬件实现结构4 3 钱搜索电路结构4 4 串行译码器流水拍数4 7 p 位并行伴随式计算单元4 8 简化后的p 位并行伴随式计算电路4 9 p 位并行钱搜索电路结构5 0 译码器正确性仿真系统结构5 0 串行译码器仿真波形图51 并行译码器仿真波形图5 2 a w g n 信道下b p s k 调制方式的误码率5 6 d v b s 2 中b c h 码的误比特率性能5 7 d v b s 2 中l d p c 码的误比特率性能5 9 b c h + l d p c 的误比特率性能6 0 r s + l d p c 的误比特率性能6 1 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：业垒二2 主墼旦编竖璺的丛究生塞丑 学位论文作者签名：互痃缝 日期：讥嘲年位月上l 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：型垦= 2 主墼旦编逢璺的珏壅量塞翌 学位论文作者签名： 玺宏缝 日期：砌年2 户j 上2 日 储指捌雠：半丝一吼m 年嗍l 咱 国防科技大学研究牛院学位论文 第一章绪论弟一早珀t 匕 1 1 课题背景 d v b s 2 是由欧洲电信标准协会( e t s i ) 于2 0 0 5 年3 月颁布的第二代数字视频 广播标准。该标准是在d v b s 的基础上发展起来的，它融合了d v b s 提出以来 近1 0 年中通信技术发展的最新成果，是面向各种宽带卫星应用的第二代标准。 d v b s 2 应用的主要领域有： ( 1 ) 标准清晰度和高清晰度广播业务； ( 2 ) 面向消费者的交互业务应用，包括i n t e m e t 接入； ( 3 ) 专业应用，如数字电视节目素材投送和新闻采集，对地面v h f u h f 发射 机的节目分配，数据内容分配等【l j 。 所有的这些d v b s 2 应用，都得益于信道编码和调制技术的最新发展。在 d v b s 2 中采用了新的信道编码方案和高阶调制组合，比d v b s 在同样的传输条 件下增加了3 0 的容量，并能在同样的谱效率下提供更强劲的接收能力。d v b s 2 的前向纠错系统( f e c ) 采用了功能强大的b c h 和l d p c 级联的信道编码方式，有 效地降低了系统解调门限，距离理论的香农极限只有0 7 l d b 的差距1 2 j 。 级联码中的b c h 码于1 9 5 9 年由霍昆格姆( h o c q u e n g h e m ) ，1 9 6 0 年由博斯( b o s e ) 和雷查德胡- 罩( r a y c h a u d h u r i ) 分别提出。b c h 码是迄今为止所发现的一类很好的 线性纠错码类。它的纠错能力很强，特别在短和中等码长下，其性能很接近于理 论值，并且构造方便，编码简单。特别是它具有严格的代数结构，因此它在编码 理论中起着重要作用【3 】。在d v b s 2 的上行链路中所使用的b c h 编码模块在整个 系统中所处的位置如图1 1 所示。译码用在下行链路的接收端，数据流按图l l 中 相反的方向进行传输。 图1 1d v b s 2 中上行链路系统结构图f 4 】 在符合d v b s 2 标准的数字卫星接收机和发射机中分别需要能够完成纠错功 能的b c h 译码器和编码器。为了满足多种不同的宽带卫星应用和卫星信道中的抗 噪声性能，在d v b s 2 中根据帧格式和内码( l d p c ) 码率的不同，一共给出了码字 第1 页 国防科技大学研究生院学位论文 参数不同的2 l 组b c h 码，并且这些b c h 码的码长较长，其中最长的为5 8 3 2 0 。 这是目前已知的对b c h 实现要求最为复杂的一次应用，相当于要在一个独立的编 码器和译码器中实现参数不同的2 1 种b c h 码的编译码，动态可配置是这样的编 码器和译码器实现的一个难点。对于超长码字的编译码应用，降低编译码的时间 延迟是实现过程中必须解决的又一个难点问题。像一般芯片设计所追求的目标一 样，对于采用硬件实现的编译码器，在保证功能正确的前提下如何提高芯片的数 据处理速度和降低芯片面积是为芯片赢得市场从而在实际应用中派上用场所必须 考虑的一个问题。 d v b s 2 标准自提出以来很快引起了多方面关注，世界上主要的直播卫星系统 运营商一致认为d v b s 2 代表了直播卫星系统的发展趋势和方向，都计划将目前 的d v b s 升级为d v b s 2 【5 j 。在我国今年启动的直播卫星系统中虽然没有采用 d v b s 2 标准( 采用自主研发的a b s s 标准) ，但随着d v b 标准逐渐在全球的广泛 应用和通信全球化的发展，我国直播卫星系统以后的发展还难以确定。解决 d v b s 2 芯片实现的技术问题对世界其他国家和我国以后的直播卫星系统建设有 重要意义。 1 2 国内外研究现状 自2 0 0 4 年e - t s i 的d v b s 2 标准草案提出以来，国内外工业界和学术界纷纷 出现了很多关于d v b s 2 标准的产品和技术研究性文章。美国的b r o a d t o m 公司于 2 0 0 6 年1 月4 日在美国拉斯维加斯举办的2 0 0 6 国际消费电子展( c e s ) 上发布了 工业界第一款集成双高频头和解调器的d v b s 2 接收芯片b c m 4 5 0 1 。b c m 4 5 0 1 为制造厂商开发具备d v b s 2 能力的机顶盒( s t b ) 、个人录像机( p v r ) 、卫星接收 机和集成多功能家庭媒体中心产品提供了能够显著降低成本的解决方案【6 】【。7 1 。文献 【8 】提出了一个用于上行链路中测试卫星接收器的d v b s 2 信号发生器，文中的信 号发生器具有灵活的可编程性。文献【9 】研究了卫星通信中网络层到d v b s 2 物理 层的接口问题，其中将i p 数据包像m p e g 2 传输流一样通过d v b s 2 标准中规定 的格式进行传输。 法国n a v t e ls y s t e m s 公司已经开发出针对d v b s 2 的b c h 译码器i p 核， 并给出了该i p 核性能特征。该串行实现的译码器在x i l i n xv i r t e x2p r o 系列f p g a 中占用5 8 0 0 个s l i c e s 和5 个b r a m s ，综合频率达到1 4 0 m h z 1 0 】。x i l i n x 公司开发 了实现整个d v b s 2 中f e c 编码模块的i p 核，其中包括b c h 编码、l d p c 编码 和位交织三部分。该编码器有串行和并行两种选择输入模式，其中的并行模式为4 位并行，编码器在v i r t e x 5 系列f p g a 中综合后，4 位并行的最大频率为2 4 3 m h z ， 在普通帧和l d p c 码率为1 2 的条件下数据吞吐率可达到9 0 0 m b i t s 】。文献 1 2 】 第2 页 国防科技大学研究生院学何论文 讨论了通过c 语言实现d v b s 2 中b c h 码软件编译码的关键问题和解决方法，给 出了其在加性高斯白噪声信道中的性能仿真结果。文献 5 】和 1 3 】针对d v b s 2 中 b c h 码的特殊性提出了实现该译码器的f p g a 硬件结构，但对于译码器中关键的 可配置解决方法和并行结构设计讲解的不是很清楚，也没有给出所设计译码器达 到的性能。 b c h 码自提出以来由于其具有严格的代数结构，到目前已经研究的比较透彻， 是取得研究成果最多的码类之一。b c h 码的纠错能力完全由它的最小汉明距离d 。 决定，而d 。又完全由生成多项式g ( x ) 的根决定，研究叱和g ( x ) 的根的关系目前 仍然是一个非常引人注目的研究课题，到目前为止有4 个限：b c h 限、h t 限、鲁 斯( r o s s ) 限和l w 限，论述了这种关系【3 】。基于这种关系研究的超b c h 限频域译 码方法取得了很多成果。文献 1 4 通过对循环码生成多项式g ( x ) 的研究，得到了设 计距离为万的g 元b c h 码的周期分布的精确公式，进而利用周期分布求出了g 元 b c h 码的非循环等价类的数目。文献 1 5 1 在介绍了基于频域采样的超b c h 限的纠 错码译码算法基础上，针对采样序列问题，重点研究了循环码共轭根系问题，给 出了基于频域采样超b c h 限的循环码译码算法。在有关b c h 编码器和译码器的 硬件实现方面创新性比较强的文章不多。文献 1 6 1 针对码长较长的b c h 码提出了 一种高速的并行编码器体系结构，文中提出的结构消除了并行编码器中的扇出瓶 颈降低了编码器的时钟周期。文献 1 7 】针对码长较短的b c h 码利用生成矩阵和校 验矩阵编译码的代数方法设计了频率很高数据处理速度很快的编码器和译码器， 当码长较长时生成矩阵和校验矩阵所占的面积会很大，不适合使用这种方法。 1 3 课题研究内容 本课题的主要任务是设计并实现符合d v b s 2 各种应用需求的b c h 编码器和 译码器。d v b s 2 标准为了支持多种不同的宽带卫星应用需求和提高卫星信道的抗 噪声性能，在f e c 系统中根据帧格式和内码( l d p c ) 码率的不同，一共给出了码字 参数不同的2 1 组b c h 码，并且这些b c h 码的码长较长，其中最长的为5 8 3 2 0 。 这就要求所实现的编码器和译码器能够对这2 1 种码字参数进行动态配置，以随时 满足不同应用的需求。另外码字的码长太长会给编码和译码的数据传输带来较大 的时间延迟，不利于系统的实时应用，采用并行编译码方法来实现相应的编译码 器对提高系统性能有重要意义。 本课题以设计出准确、高效、低功耗的编码器和译码器为目标，主要对以下5 个方面的内容进行了深入研究： b c h 码纠错的基本原理和它的编译码算法。 串行的编码器和译码器的实现方法。 第3 页 国防科技大学研究生院学位论文 并行的编码器和译码器的实现方法。 对编码器和译码器进行多种参数配置的实现方法。 d v b s 2 系统中b c h + l d p c 级联码的纠错性能。 通过对以上5 个方面内容的深入研究，本课题在设计完成符合应用需求的编 码器和译码器的基础上在以下3 个方面取得一定的研究进展： 提出了有效地适用于码长较长且可配置参数多的并行流水译码器体系结 构( 见4 2 1 ) 。 对b c h 的译码算法进行了改进，改进后的译码算法在伴随式计算部分只 需要计算2 f 1 个伴随式( ，为纠错个数) ，比改进前的计算数量2 f 少了一个 ( 见4 2 2 ) 。 对不同有限域g f ( 2 ”) 上独立的通用乘法器分两步实现后进行重构，重构 后的乘法器能够完成重构前各独立乘法器的功能，但其所占的面积比各独 立乘法器面积总和节约近1 2 ( 见4 1 3 ) 。 取得的这些进展对以后设计实现其它多应用条件下的b c h 译码器有一定的指 导意义。 。 1 4 文章的组织结构 本文的主体内容共分六章。 第一章为绪论部分，主要介绍了课题研究的背景和意义、国内外主要的研究 状况和本课题的主要研究内容。 第二章根据信道编码定理分析了b c h 码纠错的基本原理，然后从数论中的有 限域理论出发给出了b c h 码的严格代数定义，在此基础上研究了b c h 码的编码 算法和基于b e r l e k a m p m a s s e y 迭代的译码算法( 简称b m 算法) 。 第三章根据b c h 码的编码算法给出了可配置参数的串行和并行b c h 编码器 的设计结构，分析了编码器的参数配置原理。最后给出了所实现的编码器的仿真 测试结果和综合性能。 第四章基于b m 迭代译码算法设计了可配置参数的串行和并行译码器体系结 构，并对体系结构中各模块的具体电路设计进行了详细研究。根据研究和设计结 果对译码器进行了实现，最后给出了所实现译码器的测试结果和综合性能。 第五章对d v b s 2 中的b c h 码和l d p c 码在a w g n 信道下的纠错性能分别 进行了实验研究，根据实验结果对b c h 码在d v b s 2 的f e c 系统中所起的作用进 行了定量分析。 第六章为结束语，对课题中所作的工作做了一定的总结，阐明了进一步工作 的方向。 第4 页 国防科技大学研究生院学位论文 第二章b c h 编译码原理和算法研究 信息论和编码理论是现代数字通信两个基本的理论基础，前者是由s h a n n o n 以他的不朽名著“通信的数学理论”【硌】为标志建立起来的，而后者则以h a m m i n g 的经典著作“纠错和检错编码 【1 9 】为代表。s h a n n o n 信息论主要讨论信息的度量， 以及对于信息表示和信息传输的基本限制。其中的信道编码定理告诉我们，只要 信息传输速率小于信道容量，则信息传输可以以任何小的错误概率进行。但是， s h a n n o n 信息论并没有告诉我们如何去实现这一点。h a m m i n g 提出的纠错编码理 论正是为了解决这个问题1 2 。 自1 9 5 0 年h a m m i n g 发表了纠正单个随机错误的码以来，几乎过了近1 0 年时 间，才于1 9 5 9 年由霍昆格姆( h o c q u e n g h e m ) ，1 9 6 0 年由博斯( b o s s ) 和雷查德胡里 ( r a y c h a u d h u r i ) 分别提出了纠正多个随机错误的循环码b c h 码的构造方法 f 2 1 】【2 2 】。b c h 码是迄今为止所发现的一类很好的线性纠错码类【3 】o 2 1b c h 码的纠错原理 b c h 码的纠错能力很强，特别在短和中等码长下，其性能很接近于理论值， 并且构造方便，编码简单。特别是它具有严格的代数结构，因此它在编码理论中 起着重要作用【3 1 。本节首先从s h a n n o n 的信道编码定理出发来简单说明b c h 码的 纠错原理，然后介绍b c h 码所基于的代数基础有限域理论，最后在有限域的 基础上给出b c h 码的严格代数定义。 2 1 1 信道编码定理 由信息论的基本知识可知，在高斯白噪声信道时，信道容量 p 良刖0 9 2 【1 + 蒜1 ( b i t l s ) ( 2 - 1 ) 式中，是信道所能提供的带宽，只= e t 是信号功率，e ，是信号能量，丁是分 组码信号的持续时间即信号宽度，只w 是单位频带的信号功率，。是单位频带 的噪声功率，只( w t v o ) 是信噪比。 信道编码定理：每个信道具有确定的信道容量c ，对任何小于c 的码率r ， 存在有速率为尺码长为n 的分组码及( ，k o ，m ) 卷积码，若用最大似然译码，则随 着码长的增加其译码错误概率p 可任意小，即 p a 6 e n e # 鄹 ( 2 - 2 ) 和 第5 页 国防科技大学研究生院学位论文 p a c e 一”+ 1 ”。t r = a c e 一t r ( 2 - 3 ) 式中，a 。和a 。为大于0 的系数，e 。( r ) 和e c ( r ) 为正实函数，称为误差指数，它 与r 、c 的关系如图2 - 1 所示。图中，c 1 、c 2 为信道容量，_ kc 1 c 2 。 ( 尺) d c 2c i r 图2 - l e ( j 6 c ) 与r 的关系 由式( 2 3 ) 和图2 1 可看出，信道容量c 、码长疗和错误概率p 之间的转换关系。 为了满足一定误码率p 的要求，可以用以下两类方法实现。 一是增加信道容量c ，从而使e ( r ) 增加。由c 的表示式( 2 1 ) 可知，增加c 的 方法可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、调 相等宽带调制方法；增加发射机的功率；应用高增益天线；采用分集接收及低噪 声器件等方法。这些措施是从根本上改善信道、增加信道容量、减少误码率的方 法，是通信设计工作者经常采用的传统方法。 另一种方法是在r 一定下，增加分组码长珂( 也就是增加分组信号持续时间丁) ， 可使p 随n 的增加呈指数下降。但由于码长n 的增加，当尺保持一定时，可能发送 的码字数随2 呈指数增加，从而增加了译码设备的复杂性。这种方法就是信道编 码定理所指出减少误码率的另一方向，它为通信设计工作者提供了一条新的途径。 在b c h 码中有3 个重要的参数( 刀，k ，f ) ，其中n 为码长，k 为信息位长度，r 为 码字的最大纠错个数。b c h 码的码率r = k n ，由上面对信道编码定理的分析可 知，在r 一定下，增加码长玎可使译码错误概率p 随门的增加呈指数下降。另一方 面，在保持码长挖不变的情况下，降低信息位长度k 从而使码率尺降低，由式( 2 3 ) 和图2 1 可得译码错误概率p 随k 的降低也会下降。对于所有用于纠错的纠错码而 言，都是同样的道理。在d v b s 2 中针对不同的应用对f e c 系统中的内码( l d p c ) 一共分了1 1 种不同的码率。 应用纠错码后，若仍要求传输信息的速率不变，则必然使信道的带宽形增加。 设原来的信息传输速率为6 0 0b i t s ，如用r = 1 2 码，则要求信道传输速率为1 2 0 0 b i t s ，一般要求信道带宽增加一倍( 通常增加一k ) k 倍) 。因此，纠错码主要应用 于功率受限而带宽不太受限的信道中【3 l 。 第6 页 国防科技大学研究生院学位论文 2 1 2 有限域理论 分组码是建立在码的代数结构基础上的。本节介绍代数中有限域的基本知识， 有限域也称为伽逻华( g a l o i s ) 域，在编码理论中起着非常重要的作用。 2 1 2 1 有限域的定义 定义2 1 ：设f 是一个由元素组成的集合，在这个集合上定义两种运算，即加 法“+ ”和乘法“ 。对f 中的任意三个元素口，厂，如果集合f 满足以下条件： 1 具有封闭性。即 ( 口+ ) f ( 2 4 ) 口f 2 满足交换律。即 口+ = + 口 ( 2 5 ) a p = p a 3 满足结合律。即 口+ ( + 厂) = ( 口+ ) + 厂 ( 2 6 ) 口( y ) = ( 口) 厂 、7 4 满足分配律。即 口( + 厂) = 口+ 口厂( 2 7 ) 并且对于加法“+ ，存在唯一的零元素“0 ”，使口+ 0 = 口；对于乘法“一， 存在唯一单位元“1 ，使口1 = 口；对每一个元口f ，存在唯一的加法逆元，即 存在唯一的( 一口) f 使得口+ 0 = 口；对每个非零元口，存在唯一的乘法逆元 口1 f ，使口口= 1 ，则称集合f 为域。 如果一个域f 仅具有有限多个元素，比如说仅有留个元素，这样的域称为有限 域，或称之为伽逻华( g a l o i s ) 域，记为g f ( q ) 。 对任何质数p ，可以构成具有p 个元素的伽逻华域g f ( p ) = 0 ，1 ，2 ，p 一1 ) ， 在g f ( p ) 上的加法和乘法分别为模p 加法和模p 乘法。 仅当g 等于质数幂时，即q = p ”，才存在有限域g f ( q ) 。称g f ( p ) 为基域， g f ( p ”) 为g f ( p ) 的扩域，可以从g f ( p ) 出发来构造g f ( p ”) 。 2 1 2 2 g f ( 2 ”) 的构成 对于系数取自g f ( 2 ) 上的( m 1 ) 次多项式： a ( a ) = 口o + a 1 口+ + a m - i 口”q ( 2 - 8 ) 其中口。g f ( 2 ) ，j = 0 ，l ，所一1 。这些多项式的总和等于2 肘。可以把它们作为 g f ( 2 ”) 上的元素。这些元素可以用两种方式表示，一种用多项式，另一种用m 维 第7 页 国防科技大学研究生院学位论文 二元矢量。对于g f ( 2 ”) 中两个元素的加法和乘法，采用普通多项式的加法和乘法， 系数之间的运算采用模2 运算。 定义2 2 ：设厂( x ) 是次数大于零的多项式，若除了常数和常数与本身的乘积以 外，再不能被域g f ( p ) 上的其它多项式除尽，则称厂( x ) 为域凹( p ) 上的既约多项 式。 当口是凹( p ) 上某历次既约多项式的根时，口的所有次数小于所的多项式构 成一个有限域卯( 2 ”) 。一般地，设p 是一个质数，口是卯( p ) 上某历次既约多项 式的根时，口的所有次数小于m 的多项式构成一个有限域g f ( p ”) 。 2 1 2 3 有限域的特征和元素的级数 对于有g 个元素的有限域舒( g ) 。可以构成口( g ) 中单位元素“1 ”的连续和 序列 i2 k y 1 ：1 ，y l ：1 + 1 ，y 1 = 1 + 1 + + l j 二j j 二- j 一、，o z = li = li = 1血 由于g f ( q ) 是有限域，所以随着k 的增加，总可能出现重复，比如说存在m 和 n ( m ，z ) ，使 1 = l 1 = 1l = l 所以 y l = 0 j - 一 t = l 令五为使1 = o 成立的最小整数，这个允称为有限域舒( g ) 的特征。g f ( 2 ) 的特 t = l 征为2 。有限域凹( g ) 的特征见一定是质数。 特征为p 的有限域中，任何元素连加p 次就得到“o ”元素。g f ( p ”) 的特征 为p 。 对于有限域中的任何非零元，构造如下的幂序列： p 、= p ，p 2 = p p ， | b 3 = p p p ， 由于凹( g ) 是有限的，则必定有整数所和n ( m 力) ，使 p m = 9 “ 或”= 1 所以对每个非零元，存在最小正整数k 使得。= 1 ，称为k 级元素。 如果g f ( q ) 的一个元素口的级数为g - 1 ，则口被称为是本原域元素。可以证 第8 页 国防科技大学研究生院学位论文 明，每个有限域g f ( q ) 至少有一个本原域元素口，它的逐次幂构成g f ( q ) 的全部非 零元，即口1 ，口2 ，g q 一= l = 口。是g f ( q ) 的全部非零元。i 抒g f ( q ) 的每个非零元 是本原域元素的幂，所以形式上可以对每个非零元取以口为底的对数，用对数来 标记此非零元。同时如果我们把零元素“0 的对数记为一0 0 ，则g f ( q ) 中元素可 用它们的对数标记，即一o o ，1 ，2 ，g 一1 。 定义2 3 ：g f ( 2 ) 上的一个m 次多项式x ( x ) ，如果它的所有根均是g f ( 2 啊) 中 的本原域元素，则万( x ) 称为是m 次本原多项式。 m 次既约多项式不一定是本原多项式，但是本原多项式却一定是既约的。 由于g f ( 2 ”) 中每个非零元的级数是2 ”一l 的因子，所以g f ( 2 ”) 中的每个非零 元满足2 。一+ 1 = 0 ，或者说g f ( 2 ”) 中每个非零元都是方程x 2 - 1 + l = 0 的根。 于是g f ( 2 脚) 中的全部元素构成了方程x 2 ”+ x = 0 的全部根。因为任何m 次本原多 项式的根是g f ( 2 ”) 中的本原域元素，所以每个聊次本原多项式x ( x ) 都能够除尽 x 2 ”一+ l ，但x ( x ) 不能除尽任何其他x ”+ 1 ，其中n 2 ”一l 。 2 1 2 4 最小多项式 设为g f ( 2 ”) 中任一元素，m ( x ) 是g f ( 2 ) 上使m ( , f 1 ) = 0 的最低次多项式，则 称m ( x ) 为的最小多项式。例如，在g f ( 2 ”) 中“o 的最小多项式为x ，“1 ”的 最小多项式是l + x 。显然，最小多项式m ( x ) 必定是既约的。 在特征为p 的有限域g f ( p ”) 中，若是系数在g f ( p ) 上的多项式f ( x ) 的根， 则p 也是f ( x ) 的根。因为：如果 n 。 f ( f 1 ) = q = 0 l = 0 其中a 。g f ( p ) ( 江o ，1 ，2 ，胛) ，则 广h1 ，n 【厂( ) r - i q i = 口，p ( 甲 l t = oj i = o 因为a ，g f ( p ) ，a ，p = a j ，所以 l 厂( ) r = q ( p ) t = o 即f ( 3 p ) = l 厂( ) 】p = 0 。 在特征为2 的g f ( 2 “) 中，2 ，4 ，具有相同的最小多项式，这些元 素构成共轭根系，就像实系数多项式的根总是共轭成对出现一样。同样，3 ，6