（微电子学与固体电子学专业论文）基于dvb的rs（255239）码译码器的asic设计.pdf

上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的 s i c 设计 摘要 r e e ds o l o m o n ( 简称r s 码) 是一种具有很强的纠正突发和随机错误的信道编 码方式，在深空通信、移动通信、d v d 纠错以及数字视频广播( d v b ) 等系统中 具有广泛的应用。本论文主要介绍一种应用于d v b 系统的r s ( 2 5 5 ，2 3 9 ) 信道 编、解码电路的设计，其中重点是在译码电路的a s i c 设计上。 r s 译码器的设计，采用了新改进的欧几里德( 简称欧式) 算法，利用并行 方式来解关键方程，可以同时求出错误位置多项式和错误值多项式而不用执行多 项式除法运算和域元素求逆运算。该算法的控制单元较简单，而且具有规则的模 块化结构。本文还采用3 级流水线( p i p e - l i n e ) 的处理结构，并利用有限域对偶基 乘法器的特性对译码电路进行优化。此外，使用比较规整的电路结构，对关键方 程求解模块实现了模块复用。这些技术的采用大大的提高了译码器的效率，节省 了译码器电路面积。 f p g a 仿真结果表明本文所设计的r s 译码器，解码速度可达到7 0 m h z 。 使用上华o 6 u m c m o s 工艺库的综合及布局布线结果表明电路规模为3 8 万门 ( 不包含r o m 及f i f o ) ，芯片面积为2 4 5 r a m 2 关键词：r s 码、d v b 、改进e u c l i d 算法、关键方程、a s i c v i 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 2 3 9 ) 码译码器的a s i c 设计 a b s t r a c t r e e d s o l o m o nc o d e ，ap o w e r f u le r r o rc o r r e c t i n gc o d ef o rb u r s ta n dr a n d o me r r o r s ， i sw i d e l ya p p l i e dt od e e ps p a c ec o m m u n i c a t i o n s ，m o b i l ec o m m u n i c a t i o n s ，d v d c o r r e c t i n gr e e de r r o r s ，d i g i t a lv i d e ob r o a d c a s t i n gs y s t e m ，a n ds oo n t h i sp a p e r m a i n l yi n t r o d u c e sar s ( 2 5 5 ，2 3 9 ) c h a n n e lc o d i n ga n dd e c o d i n gc i r c u i t si nd v b s y s t e m s ，b e i n ge m p h a s i z e di nt h e a s i cd e s i g no ff f sd e c o d i n gc i r c u i t s ， t h i sn e wm o d i f i e de u c l i d e a n a l g o r i t h m ，b e i n gi m p l e m e n t e dt o s o l v et h e k e y - e q u a t i o nw i t hp a r e l l e lm o d ei nt h ed e s i g no fr sd e c o d e r , c a ns o l v et h ee r r o r l o c a t o ra n de v a l u a t o rp o l y n o m i a l ss i m u l t a n e o u s l yw i t h o u tp e r f o r m i n gt h eo p e r a t i o n s o fp o l y n o m i a ld i v i s i o na n df i e l de l e m e n ti n v e r s i o n t h ep r o p o s e da l g o r i t h mh a sv e r y s i m p l ec o n t r o l l i n gu n i t s ，a n dp r o v i d e sr e g u l a rm o d u l ea r c h i t e c t u r e f u r t h e r m o r e ，t h e 3 - l e v e lp i p e l i n ep r o c e s s i n ga r c h i t e c t u r ei nr sd e c o d e ri so p t i m i z e db yu s i n gt h e c l m m c t e r i s t i c so ft h ef i n i t e f i e l dm u l t i # i e rb a s e do nd u a lb a s i s f u r t h e r m o r e ，m e t h o d s f o rm o d u l e sr e u s ea r eu s e di nt h es o l v i n gt h ek e y - e q u a t i o nm o d u l ew i t l lt h er e g u l a r a r c h i t e c t u r e 。a l lt h e s et e c h n i q u e si m p r o v e dm u c he f f i c i e n c yo ft h er sd e c o d e ra n d r e d u c et h ec h i pa r e ao f r sd e c o d e r t h es i m u l a t i o nr e s u l t so fr sd e c o d e rc i r c u i t si m p l e m e n t e di nf p g ad e m o n s t r a t e t h a ti t sd e c o d i n gs p e e di s7 0m h z t h er e s u l t so f s y n t h e s i sa n dp & ri n d i c a t e st h a t t h i sd e s i g nu s i n gao 6 u mc s m cc m o st e c h n o l o g yc o n s t r u c t sar s ( 2 5 5 ，2 3 9 ) d e c o d e rw i t ht h ec h i pa r e ao f2 4 5m m ：a tt h es c a l e so f3 8 kg a t e s ( n o ti n c l u d i n g r o m a n df i f o ) k e y w o r d ：r s ，d v b ，m o d i f i e de u c l i d e a na l g o r i t h m ，t h ek e ye q u a t i o n ， a s i c v l i 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：。鸳e l 期丝：! ： 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送 交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：玉型 导师签名：兰查! 母日期：! ：兰：_ i i i 上海大学硕士学位论文基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 第一章绪论 d v b 是d i g i t a lv i d e ob r o a d c a s t i n g 的简称。它是数字视频广播的标准。为了在 d v b 中增强数据传输的功能，提高数据传输的可靠性，采用信道编码技术是一 种有效的方法。本文主要讨论r s 码在d v b 系统中的应用i l l 。在本章中，主要介 绍论文的相关背景，包括d v b 、数字通信系统纠错码和a s i c 技术，然后说明本 文的研究工作、创新点和论文内容。 1 1 背景 1 1 1d v b 的发展状况 从九十年代开始，数字电视技术在世界范围内飞速发展，除了欧洲之外，美 国、日本等技术先进国家也都认识到数字电视技术对本国经济发展的重要性，因 此也加入到数字电视技术的研究的行列，并制定了现代数字视频压缩技术的一系 列主要标准m p e g x s 中国也准备在m p e g 的基础上制订出自己的数字电视标准 系列。 随着各数字电视的标准出台，多个国家或联合或独立实施数字电视广播项 目。欧洲成立了由三十多个国家2 3 0 多个成员组成的国际机构：数字电视广播 ( d v b ) 联盟，d v b 联盟共同制定t d v b 数字卫星电视( d v b s ，q p s k 调制) 、 d v b 数字有线电视( d v b c ，q a m 调制) 、d v b 数字地面广播电视( d v b t ， c o f d m 调制) 标准。这些标准现在已经作为世界统一标准被大多数国家接受， 世界上许多国家已经以d v b 技术进行商业广播。我国目前已开办了d v b 广播系 统，并于1 9 9 8 年9 月成功进行了数字h d t v 试播，还制定了我国数字电视广播三 步走计划，将于2 0 0 8 年正式试播h d t v - t ，计划2 0 1 5 年将全面实现数字电视广播， 同时停止模拟电视广播。数字电视的时代即将到来，模拟电视终将被数字电视所 取代。 d v b 数字电视广播系统，包括了卫星、电线电视和地面广播的普通电视和 高清晰度电视的广播与传输，它的目标是要找到一种对所有传输媒体都适用的数 字电视技术和系统，它的主要特点有： 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 。2 3 9 ) 码译码器的a s i c 设计 1 系统能灵活传送m p e g 2 视频，音频和其他数据信号； 2 系统使用统一的m p e g 2 传送比特流复用； 3 系统使用统一的服务信息系统提供广播节目的细节等信息； 4 系统使用统一的一级里德一索罗f ( r e e d s o l o m o n ) 前向纠错系统； 5 使用统一的加扰系统，但可有不同的加密： 6 选择适于不同传输媒体的调制方法和通道编码方法以及任何必须的附加 纠错方法： 本文主要是讨论d v b 中前向纠错编码系统的r e e d s o l o m o n 编码的设计及其 硬件a s i c 实现。 1 1 2 数字通信系统 通信的目的是要把对方不知道的消息及时可靠地传送给对方。要在 d v b 系统中实现数据传输，进行数字通信，就必须保证所传输信息的可靠性。 在数字通信系统中通常采用纠错码技术来进行差错控制，从而达到提高数据传输 可靠性的目的。本小节介绍数字通信的基本原理口i ，图1 1 给出了数字通信系统 的模型，下面对组成数字通信系统的各个部分分别进行描述。 图1 1 数字通信系统的模型 发送端：信源( 信息源) 是信息的产生之地，其信号可能是模拟的，也可能是数 字的。信源编码器，负责把信源发出的信息转换成数字形式的信息序列，主要包 括模拟数字( a d ) 变换和压缩处理，然后再进行一定形式的编码处理；有时为了保 密，还会进行加密处理。信道编码器，其目的是在数字序列中以受控的方式加入 一些冗余信息，以便在接收端克服信号在信道传输时所遭受到的噪声和干扰的影 2 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 据的可靠性以及改善接收信号的逼真度的，这种技术就是纠错码技术。数字调制 器，是通信信道的接口，其主要目的是把数字信息序列映射成信号波形，假定已 编码的信息序列以均匀速率rb i f f s 每次一比特进行传输，数字调制器可以简单 地将二进制数字“0 ”映射成波形s o ( t ) ，而将二进制数字“1 ”映射成波形s l ( t ) ， 在这种方式中，信道编码器所输出的每比特是分别进行传输的，这种调制方式称 为二进制调制；在另外一种调制方式中，调制器一次传输m 个已编码的信息比特， 其方法是采用m = 2 “个不同的信号波形s i ( t ) ，i = o ，1 ，2 ，m ( m 2 ) ，每一个波形用 来传输2 “个可能的比特序列中的某一个序列，这种调制方式称为m 元调制。 信道：信号传输的通道，是发送端到接收端之间信号传输所经过的物理媒介。 信道可以分为有线信道( 比如双绞线、同轴电缆、光缆等) 和无线信道( 比如长波、 短线、微波、红外线等) 。在信号传输的过程中不可避免地会引入干扰和噪声( 比 如热噪声、脉冲干扰与衰落等) 。不同的信道具有不同的特性，而信道的固有特 性和所引入的干扰的特性会直接关系到发送端中的变换方式的选取。 接收端：数字解调器对受到信道恶化影响的发送波形进行处理，并将该波形 还原成一个数字序列，此序列表示对发送数据符号的估计值( - - 进制或m 元) 。这 个数字序列被送至信道译码器，信道译码器根据信道编码器所采用的编码方法的 有关知识以及接收数据所含的冗余信息重构原始序列。当需要模拟输出的时候， 信源译码器接收到信道译码器的输出序列后，根据所采用的信源编码方法的有关 知识还原出由信源所发出的原始信号。信宿，信息的接收者，即为信息最后到达 的目的地。 由此可见：通信的基本任务是传送信息。通信系统中最重要的指标就是信息 传输的有效性和可靠性，而这两者往往是一对矛盾。如何合理地解决有效性与可 靠性这对矛盾，是正确设计一个通信系统的关键问题之一。通信系统本身( 包括 纠错码) 就是在解决这对矛盾的过程中不断地发展起来的。下面介绍一些衡量有 效性与可靠性的主要技术参数 l 、传输速率 ( 1 ) 码元传输速率波特率调制速率：每秒钟通过信道传输的码元数。单位是泼 敞聊。 ( 2 ) 比特率，比特传输速率：每秒钟通过信道传输的信息量。单位是选挂壁( 6 i 以) 。 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s t c 设计 2 、差错率 1 ) 定义 差错率是衡量传输质量的重要指标之一，它有以下几种不同的定义： 码元差错率：指在传输的码元总数中发生差错的码元数所占的比例( 平 均值) ，简称误码率。 比特差错率，比特误码率：指在传输的比特总数中发生差错的比特数所占 的比例( 平均值) 。在= 进制传输系统中。码元差错率就是比特差错率。 码组差错率：指在传输的码组总数中发生差错的码组数所占的比例( 平 均值) 。 2 ) 降低差错率的方法 在传输过程中产生不同差错的主要原因有：不同的传输系统有不同的性能： 在传输过程中干扰不同；不同的用户或不同的传输系统对差错率的要求不同。有 两种途径降低差错率以满足系统要求： 降低信道( 调制解调器传输媒介) 本身引起的误码率； 采用信道编码，在数字通信系统中增加差错控制设备。本文正是从速一角度 来设计一种纠错码r s 码以降低差错率，从而提高通信系统的可靠性的。 1 1 3 信道编码的分类 图1 - 2 纠错码的分类 从上节介绍中可以看出纠错码技术在数字通信系统中的位置和作用。下面将 介绍它的分类。 纠错码的分类有很多种，主要有以下几类 3 1 6 1 ： 介绍它的分类。 纠错码的分类有很多种，主要有以下几类 3 1 1 6 1 ： 4 上海大学硕士学位论文基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 l 、按照对信息元处理方法的不同，分为分组码和卷积码两大类。 分组码是把信源输出的信息序列，以k 个码元划分为一段，通过编 码器把这k 个信息元按一定规则产生r 个校验元，输出长为n = k + r 的一个 码组。因此每一码组的校验元仅与本组的信息元有关，而与别组无关。 而分组码的校验元不仅与本组的信息元有关，也与其前m 段的信息元有 关。另外分组码又可分为循环码和非循环码。 2 、根据校验元与信息元之间的关系分为线性码和非线性码。 若校验元与信息元之间的关系是线性关系( 满足线性叠加关系) ，则称 为线性码；否则称为非线性码。 3 、按照纠正错误的类型可分为纠正随机( 独立) 错误的码、纠正突发错误的码 和纠正同步错误的，以及既能纠正随机错误又能纠正突发错误的码。 信道编码中用到的码类很多，为简便起见，我们用图1 2 来说明。 1 1 4a s i c 简介 a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ，专用集成电路) 是相对于通用集 成电路而言的，a s i c 主要是指某一专门用途的集成电路元器件。a s i c 分类大致 可分为数字a s i c 、模拟a s i c 和数模混合，本文主要论述数字电路的a s i c 设计。 数字a s i c 设计方法1 1 有多种，按版图结构及制造方法分类，有半定制 ( s e m i - c u s t o m ) 和全定制两种实现方法( 图1 - 3 ) 图1 - 3a s i c 设计方法分类 全定制方法是一种基于晶体管级的，手工设计版图的制造方法。设计者需要 使用全定制版图设计工具来完成，设计者必须考虑晶体管版图的尺寸、位置、互 蚤 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 连线等技术细节，并据此确定整个电路的布局布线，以使设计的芯片的性能、面 积、功耗、成本达到最优。显然，全定制设计中，人工参与的工作量大，设计周 期长，而且容易出错。然而利用全定制方法设计的电路，面积利用率最高，性能 较好，有利于降低设计成本，提高芯片的集成度和工作速度，以及降低功耗。在 通用中小规模集成电路设计、模拟集成电路，包括射频级集成电路的设计，以及 有特殊性能要求和功耗要求的电路或处理器中的特殊功能模块电路的设计中被 广泛采用。 半定制法是一种约束性设计方式，约束的目的是简化设计，缩短设计周期， 降低设计成本，提高设计正确率。半定制法按逻辑实现的方式的不同，可再分为 门阵列法、标准单元法和可编程逻辑器件法。 门阵n ( g a t ea r m y ) 是较早使用的一种a s i c 设计方法。它预先设计和制造 好各种规模的母片，其内部排行成列，并等间距地排列着基本单元的阵列。除金 属连线及引线孔以外的各层版图图形均固定不变，只剩下一层或两层金属铝连线 及孔的掩模需要根据用户电路的不同而订制。i c 厂家根据用户设计的网表所描 述的电路连接关系，完成母片上电路单元的布局及单元间的连线然后对这部分 金属线及引线孔的图形进行制版、流片。 标准单元( s t a n d a r dc e l l ) 法必须预建完善的版图单元库，库中包括以物理版图 级表达的各种电路元件和电路模块“标准单元”，可供用户调用以设计不同的芯 片。这些单元的逻辑功能、电性能及几何设计规则等都已经过分析和验证。与门 阵列单元不同的是，标准单元的物理版图将从最低层至最高层的各种版图设计图 形都包括在内。在设计布图时，从单元库中调出标准单元进行排列，行与行之间 留有布线通道，同行或相邻行的单元相连可通过单元行的上下通道完成。各行单 元之间的垂直方向互连则必须借用实现预留在“标准单元”内部的走线道 ( f e e d - t h r o u g h ) 或在两单元间设置的“走线道单元”或“空单元”来完成连接。 门阵列或标准单元设计a s i c 共存的缺点是无法避免冗杂繁复的i c 制造后 向流程，而且与i c 设计工艺紧密相关，最终的设计也需要集成电路制造厂家来 完成，一旦设计有误，将导致巨大的损失。另外还有设计周期长、基础投入大、 更新换代难等方面的缺陷。 可编程逻辑器件法是用可编程逻辑器件设计用户定制的数字电路系统。可编 6 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码嚣的a s i c 设计 程逻辑器件芯片实质上是门阵列及标准单元设计技术的延伸和发展。可编程逻辑 器件是一种半定制的逻辑芯片，但与门阵列法、标准单元法不同，芯片内的硬件 资源和连线资源是由厂家预先制定好的，可以方便地通过变成下载获得重新配 置。这样，用户就可以借助e d a 软件和编程器在实验室或车间中自行进行设计、 编程或电路更新。 1 2 论文的主要工作 作者在设计可应用于d v b 系统的r s 编译码器时，是采用了自顶向下1 4 i 的 设计方法，基于数字系统的不同层次f s l 来设计的。首先根据系统的需求分析，以 信道编码理论为基础，通过对多种译码算法的比较分析，确定了所采用的算法为 一种新改进的欧式算法，并在系统级上通过m a t l a b 仿真从理论上验证了r s ( 2 5 5 ，2 3 9 ) 码能够满足d v b 的误码性能要求。接着在整体算法的行为级上通 过c 语言步步验证了所采用的译码算法的正确性，从而为后面的a s i c 设计奠定 了基础。然后在r t l 、逻辑门级上，设计了r s 编、译码器，其中重点是译码器 的乘法器、关键方程求解、钱搜索等模块的设计及实现。最后在版图级上对r s 码译码器电路布局布线成功。 1 3 论文的创新点 本文的创新点主要有以下几点： 1 、采用流水线技术，设计了一种可应用于d v b 系统的基于对偶基乘法 器的r s 译码器 2 、通过对多种译码算法的比较分析，选择了一种简单且易实现的新改 进的r s 译码算法，该算法用硬件描述语言v e r i l o gh d l 实现后，映 射的硬件电路与通用算法相比，控制单元更简单：数据处理单元模 块更规则。 3 、采用分时复用技术及一种较特殊的硬件结构，对译码硬件电路的解 关键方程模块进行了优化，节省了硬件资源。 7 上海大学硕士学位论文 基于d v 8 的r s ( 2 5 5 2 3 9 ) 码译码器的a s i c 设计 1 4 论文的内容 本文分为七章：第一章为绪论，概要介绍论文的背景、主要工作、创新点及 内容安排。第二章介绍纠错编码的基本理论，这是开展本文研究工作的基础。第 三章给出r s 码编译码的软件算法，并对几种译码算法进行比较分析。第四章以 d v b s 为例，给出其采用纠错码的总体方案设计，并对r s 码的性能进行分析。 第五章介绍了所用的f p g a 器件，详细描述了r s 编译码器的硬件设计与实现， 最后也给出了f p g a 的仿真结果。第六章介绍r s 译码器芯片实现的设计流程， 包括译码器芯片的综合、及布局布线。第七章对本文的研究工作给出了一个简要 的总结。 海大学硕士学位论文 基于i ) v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 第二章信道编码理论 本章的主要内容是介绍信道编码的基本理论和数学知识【3 】1 6 1 1 7 1 1 8 i ，它为 后面章节要介绍的r s 纠错码的设计及应用提供了理论基础。 2 1 信道编码定理 2 1 1 信道容量的定义 香农定义信道容量为 c 。攀1 ( x ，y ) ( 2 _ 1 1 ) 其中变量x 和y 分别代表信道的输入和输出，i ( x ，y ) 为x ，y 的互信息量， p ( x ) 是变量x 的概率密度函数( p d f ，p r o b a b a l i t yd e n s i t yf u n c t i o n ) 。i ( x ，y ) 的最 大值取决于信源x 的概率分布。信道容量c 的单位是信道上每传送一个符号( 每 使用一次信道) 所能携带的比特数，即比特符号。如果已知符号传送周期是t 秒，也可以“秒“为单位来计算信道容量，此时c 。= c ts ，以比特秒o i t s ) 为信道容量单位。 2 1 2 纠错码的信道模型 不同类型的信道加不同类型的噪声就构成了不同类型的信道模型。就噪声引 发差错的统计规律而言，分为随机差错信道( 一般由高斯噪声引起) 和突发差错 ( 由突发噪声引起的) 两大类。常见的差错编码信道模型有一下几种： ( 1 ) 、二进制对称信道 该信道模型有一个输入取值集合x = o ，1 ) 和输出集合y = o ，1 ，以及一组 表示输入、输出关系得条件概率。如果a w g i n 导致统计独立的差错且条件概率 对称，即 p ( y 2 0 i x = 1 ) - p ( y _ 1 i x = o ) = p( 2 - 1 - 2 ) p ( y 2 l l x 2 1 ) 2 p ( y = o i x = o ) = i p( 2 - l 一3 ) 则称这种对称二进制输入、二进制输出的编码信道为二进制对称信道，简写为： b s c ，其信道模型如图2 1 所示： 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 o f l 0 p 、 输入输出 夕7 1 。1 矿j 1 圈2 - i 二进制对称信道( b s c ) 根据式2 1 1 ，其信道容量可表示为 c 2 蛩1 ( 础产圭圭p ( x j ) p ( y ix j ) l 0 9 2 j = o i = o掣p#p、，l = l + p l 0 9 2 p + ( 1 一p ) i 0 9 2 ( i p ) ( 2 一l - 4 ) ( 2 ) 、离散无记忆信道 b s c 可视为一种更广义的离散输入、离散输出的一个特例。假设信道编码 器的输入是q 元符号即输入符号集由q 个元素x = x o ，x 1 ，x q 1 ) 构成，而检测器 的输出是q 元符号即信道输出符号集由q 个元素y = ( y o ，y l ，, y q - 1 ) 构成，且 信道和调制构成是无记忆的，那么图2 2 所示信道模型的输入输出特性可用 组共q 个条件概率来描述 p ( y = y i x = x i ) - - - p ( y i x i ) 式中，i = o ，1 ，q - 1a 这样的信道称为离散无记忆信道( d m c ) 。 ) 【0 x 1 ： ! ： x r l 图2 - 2 离散无记忆信i 萱( d m c ) 若已知该信道的转移概率，则可以求出相应的信道传输信息i o ( ，y ) 酗，y ) = 篆- i 盘- t 一州w ：i p ( y j f x , ) ( 2 - 1 - 5 ) i t o ，卸，、，f ， 式中p ( y j ) = p ( y = y j 产呈p ( x j 扫( 巧，而) i = 0 其信道容量由定义可知c = m a xi ( x ，y ) 由式2 - 1 5 可知在信道转移概率 p ( y j x i ) 已知的情况下，信道容量c 取决于x 的概率分布。 l o l 海大学硕士学位论文基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 下面以对称d m c 信道为例来分析其信道容量。 1 1 、对称d m c 信道 如果转移概率矩阵p 的每一行都包含同样的元素( 是第一行的置 换) ，则称该矩阵是输入对称的；如果转移概率矩阵p 的每一列都包含 同样的元素( 是第一列的置换) ，则称该矩阵是输出对称的：如果输入、 输出都对称，则称该d m c 为对称的d m c 新道。d m c 信道有如下性 质： 对称信道的条件熵h ( y x ) 与信道输入符号的概率分布无关，且有 h ( y x ) = h ( y x i ) ，i = 0 ，l ，1 “q - 1 ，推导如下 h o x ) = 一p ( 而) p ( 以7 0 ) 1 0 9 p ( y ，7 0 ) = 一；p ( y ，7 x , ) l o g p ( y j x d( 2 1 6 ) ；h ( y = d 当信道输入符号等概分布时，信道输出符号也等概分布；反之，若信 道输出符号等概分布，信道输入符号必定也是等概分布。 当信道输入符号等概分布时，对称d m c 信道达到其信道容量，为 o c = l o g q h ( y x i ) = l o g q + p ( 乃，而) l o g p ( 卟，t ) ( 2 - l 7 ) j = i 2 ) 、准对称d m c 信道的容量 如果转移概率矩阵p 是输入对称而输出不对称，即转移概率矩阵p 的 每一行都包含同样的元素而各列的元素可以不同，则称该矩阵是准对 称d m c 信道可以证明准对称d m c 信道的容量 o c s l o g 口一声p ( y j x i ) l o g p ( ) , i x i ) ( 2 - 1 - 8 ) = l 当信道输入符号等概分布时，准对称d m c 信道达到其信道容量c ( 3 ) 、离散时间无记忆信道的容量 若d m c 信道的输入字符集有限而输出字符集y = y o ，y l ，”y q 1 中q 一* 时， 信道就不再是离散信道而是离散输入、连续输出的离散时间无记忆信道。离散时 间无记忆信道的容量，可视作d m c 信道软判决译码时的容量极限。这类信道中 最重要的一种是加性高斯白噪声( a w g n ) 信道，对它而言，离散输入x = x o ，x j ，” 上海大学预士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 x q 1 和模拟输出y = 一o 。，。) 之间的最大平均互信息即信道容量由下式给出 c = 嘴q 丕- l p ( y x i ) p ( x i ) l 0 9 2 号铲咖 ( 比特符号) ( 2 - l _ 9 ) 式中 口一l p ( y ) = p ( y j ，) p ( x a i = 0 当x 给定后，y 是一个均值为x i 、 舭。产击e 七呻丹2 一 ( 2 - 1 1 0 ) 方差为02 的高额随机变量 f 2 1 1 1 ) 作为特例，对于一个二进制输入的a w g n 无记忆信道，若x = x o ，x 1 ) 2 a ，。a ) ， 输入概率矢量p x = ( o 5 ，0 ，5 ) 即等概输入时，平均互信息i ( x ；y ) 最大而达到信道容 量，以比特符号为单位是 c = ；一【，i 0 9 2 号署方畦一( ，圳o s ：丛爱咖( 2 - 1 - 1 2 ) ( 4 ) 、波形信道 波形信道是这样一种信道模型：其输入是模拟波形，其输出也是模拟波形。 一个受加性高斯白噪声干扰的带限波形信道的容量，已由香农( 1 9 4 8 ) 1 e 式定义为 1 c = l i mm 砖- l ( x ；y ) ( 2 - i 一1 3 ) t - o o p c x , ) 若把输入、输出和噪声波形x ( t ) 、y ( t ) 和n ( t ) n 开成为一个正交函数的完备集， 可得到与展开式对应的一组系数 x i ) 、 y i ) 、 n i ) ，然后利用展开式中的系数来描 述信道特征。令两f 【x l x 2 ，p 【n 】及y n = y l ，y 2 ，y n 】，这里n _ 2 w t ，y i 味i + r l i ，则 a w g n 信道x h 和y n 之间的平均互信息是 i ( x w ；y n ) = 茧e p ( y , x i ) p ( x i ) l o g 号铲幽幽， ( 2 1 - 1 4 ) 式中p ( y i i x i ) = 丽1 p 一27 帕 当 x i 是统计独立、零均值的高斯随即变量时，即 盹) = 击e 枷2 ( 2 - 1 - 1 5 ) 式中ox 2 是各x i 的方差，则对于已知的输入p d f 值p ( x i ) ，可求出i ( x ；y ) 的最大值。 由( 2 - 1 - 1 4 ) 式 蛩，t 粕；，= 善”弘1 鲋+ 鲁曩1 胁卅鲁，= 盯，删+ 等，( 2 - 1 - 1 6 ) 假如对x ( t ) 的平均功率加以限制，即 1 2 上海大学硕士学位论文基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 耻；肛2 = ；薹耐) = 孚( 2 - 1 - 1 7 ) 于是有 一：t p a v ：生 (2118)n2 w 、。， 将上式代入( 2 1 1 6 ) 式，并将结果除以t ，就得到单位时间的信道容量 c = w l o g ( i + p w i ( w n o ) ) 2 w l o g ( i + s n r ) b s 这就是带限a w g n 波形信道在平均功率受限条件下信道容量的基本公式 也就是有名的香农公式。 2 1 3 信道容量与带宽、s n r 间的关系 根据香农公式，带宽定时，信道容量随s n r 的增加而单调增加，因此增 大信号功率、减小信道噪声可以增加信道容量；如果s n r 固定，信道容量随着 带宽的增加而增加，其极限为c 曲= i 去；如果给定信道容量c 。带宽w 和信噪 v 0 l i i 比s n 存在着互换的关系，即若减小带宽则必须发送较大的信号功率，若有较大 的传输带宽，则在同样信道容量的情况下能够用较小的信号功率来传送，这表明 宽带系统有较好的抗干扰性。扩频通信就是利用这个原理，将所需传送的信号扩 频，使之远远大于原始信号带宽，以增强抗干扰的能力。 2 1 4 信道编码定理 每个信道具有确定的信道容量c ，对任何小于c 的码率r ，存在有速率为r 码长为n 的分组码及( n o ，k o 皿) 卷积码，若用最大似然译码，则随着码长的增加其 译码错误概率p 可任意小。 该定理表明，以任意低的错误概率通过有噪声信道传送信息是可能的，但并 不是任意分组长度为n 速率为r 的编码都能达到该目的。实际上，错误概率越 低，如果r 以任意小的距离逼近c ，则编码长度n 将会越大。 2 2 纠错码的数学基础 1 、群的概念 如果一个元素集合g 在其中定义一种运算“，并满足条件 1 3 e 海大学硕+ 学位论文基于d v b 的r s ( 2 5 5 2 3 9 ) 码译码器的a s i c 设计 ( 1 ) 自闭性c = a + b( 2 ) 结合律a + ( b t c ) = ( a 吣) + c ( 3 ) 单位元a + e = e + a _ a( 4 ) 逆元a + a - 1 = a - 1 + a _ e 则称这个元素集合为一个“群”( a ，b ，c ，e ，a - 1 g ) 。如果这个集合中的元素满 足交换律：a 岫= b + a ，则称此集合为“交换群”。若群中的所有元素都可用其中某 一元素的幂次方来表示，则称此群为“循环群”。群中元素个数称为元素的“阶”， 元素个数有限的“群”称为“有限群”，群中的“单位元”是唯一的，群中的任 一元素的“逆元”是唯一的。 2 、有限域的基本概念 如果存在一个非空元素集合f ，若在f 中定义了加和乘两种运算，且满足 下述条件： ( 1 ) f 关于加法构成交换群。其加法恒等元记为0 ， ( 2 ) f 中非零元素全体对乘法构成交换群。其乘法恒等元( 单位元) 记为1 ( 3 ) 加法和乘法间有如下分配律： a ( b + c ) = a b + a c ( b + c ) a = b a + c a 则称f 是一个域。包含有限个元素的“域”被称为“有限域”或叫作“伽罗华 ( g a l o i s ) 域，记为g f ( q ) 。域中的元素个数称为域的“阶”，若在有限域g f ( q ) 中，所有非零元素可以由一个元素a 的各次幂ao ，a1 ，aq 2 生成，则称元素a 为生成元或本原元。 3 、扩域的概念及性质 ( 1 ) 即约多项式 对于某数域上的多项式p ( x ) ，若除了常数c 以及c p ( x ) 外。不能被该数域上 的任何其它多项式整除，则称p ( x ) 为该数域上的即约多项式。 ( 2 ) 本原多项式 对于有限域g f ( q ) 上的m 次多项式p ( x ) ，若能被它整除的最简首一多项式 ( x n = 1 ) 的次数n 毫q m - 1 ，则称该多项式为本原多项式 ( 3 ) 扩域 若p ( x ) 是g f ( q ) 上的m 次即约多项式，则g f ( q ) 域上次数小于i r l 的多项式的 全体，在模q 加、模p ( x ) 乘运算下构成一个q m 阶的有限域，称为( 拒( q ) 域的扩域 4 上海大学硕士学位论文 基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 ( e x t e n s i o nf i e l d ) ，写作g f ( q “) 。称g f ( q ) 是扩域g f ( q m ) 的基域。 ( 4 ) g f ( q ) 上的本原多项式p ( x ) 在扩域g f ( q m ) 上的根q 一定是本原元。 ( 5 ) 若p ( x ) 是g f ( q ) p 的m 次本原多项式，则g f ( q m ) j 2 次数小于m 的非零多项式的 全体( 共q m - 1 个) ，在模p ( x ) 乘运算下构成一个多项式循环群。也就是说，扩域 o f ( q ) 里至少存在一个本原元n ( c i 代表一个次数小于m 的多项式) ，它的各次幂 qo ，d1 ，qq 2 构成了扩域的全部非零元素。 4 、有关基的基本概念及定理i ”i ( 1 ) 自然基 g f ( p m ) 中的p m 1 个非零元素，均可以用本原域元素的各次幂表示： o = 1 ，2 a ，也可用本原多项式的根多项式表示，i l i a 1 ，q2 ， 6 t p ”1 ) 就是域的一组自然基，如g f ( 2 3 ) 中的自然基是( 1 ，n ，n2 ) 。 ( 2 ) 正规基 定义 。，。，2 ，。，2 - 1 ”a ，q 为g f ( p m ) 域的正规基，其实就是以a 为 根的本原多项式f i x ) 的共轭根系 ( 3 ) 对偶基 迹的定义：a g f ( q “) ，则它在g f ( q ) 上的迹定义为 耳扭) ：口+ a q + 口q 2 + + 仃口一1 ( 2 - 2 一1 ) q 为素数或素数幂 对偶基的定义 与g f ( p ”) 的基底b = ( x0 1 ， 。1 ) 相对应，若 1 i = j o 栅卜1* 。 (2-2-12)0i其它 、 满足，则称o f ( p “) 的基底b 1 = ( ，”。，) 是b 的对偶基。 如果将迹函数扩展到普通线性函数f 0 ，基底b 、b 、存在下列关系 f 1 i = j ，( 觑n ) = ( 2 - 2 2 ) 0其它 上海大学硕士学位论文基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 则也称g f ( p “) 的基底b 、= ( 朋，。) 是b 的对偶基。其中乞m 代表g f ( p ) 一g f ( p ) 的所有的线性函数的集合。 4 ) 定理1 设 q 为迦罗华扩展域g f ( p ) 的基， 九k ) 为它的对偶基，则任一域元素z 可表示为： z ：m - l ： 丑，其中z k = t r ( z u k )( 2 2 3 ) k = 0 也可表示为： m - i z = ，( z m 埔( 2 - 2 - 4 ) s = 0 5 ) 定理2 设 u j 为迦罗华扩展域g f ( p m ) 的基， k ) 为它的对偶基，则两域元素z 、g 的乘积w 可以对偶基的形式表示为： m - i m - i w = ，( 矿卢) 厶= ，( z g ) 厶( 2 - 2 5 ) k = o k = 0 6 ) 定理3 如果a , b ，c g f ( p m ) ，a _ b c ，则下列关系式成立： 黧f(bpa1 f篓型刚cl=臣：(apafcbpaf ( b p af ( b p a 2 m - 2f ( a p = 一p 撕， )( 枷2 ) ，( 6 触“) 0 1) 1，1 。 ”1 ) “) ) i h l jl”。) j 设 九i 是自然基( a1 ) 的对偶基，对任何非零f e g f ( p “) 和非零bg f ( p “) ，b 以 对偶基表示为 b = 刍j f ；o c 以自然基表示为 m - i c = c 产 = 0 由定理3 可得： ( 2 - 2 - 7 ) ( 2 - 2 - 8 ) a o = b o c o + b l c i + 十b m 1 c m 1 8 - i = n c o + b 2 e l + + b m c m - l a m 1 2b m i c 0 + b m c i + + b 2 m - 2 c m - 1 ( 2 - 2 9 ) 1 6 上海大学硕士学位论文基于d v b 的r s ( 2 5 5 ，2 3 9 ) 码译码器的a s i c 设计 这里b i n + k _ r t l - in 屯+ 女 2 = 0 其中p i 为g f ( p m ) 的即约多项式p ( x ) 的系数 p