（通信与信息系统专业论文）基于fpga技术的纠错码研究.pdf

基于f p g a 技术的纠错码研究 中文摘要 基于f p g a 技术的纠错码研究 中文摘要 纠错码理论的中心任务是设计出编码效率高、抗干扰性能好而编译码设备又较简 单的纠错码。本文主要关注纠错码中的线性分组码，因为线性分组码是分组码中最重 要的一类码，是讨论各类码的基础，文中重点研究的循环纠错码和l d p c 码就属于线 性分组码。 鉴于采用硬件描述语言v h d l 进行设计输入的优点，首先给出了基于v h d l 的 一种系统循环码编码器、译码器，以及m 序列发生器的实现办法，并进行性能仿真 与分析。接下来对l d p c 码的译码算法和硬件实现方案进行了较深入的研究，针对其 译码算法的特点，提出了采用基于c 语言的f p g a 编程设计方法进行相应的结构模 型设计的方案。给出了译码器的c 语言设计和i m p u l s ec 编程模型，最后在f p g a 协处理器混合平台目标上实现该译码器，证实了l d p c 码具有良好的纠错性能，为软 件工程师开发基于f p g a 的嵌入式系统提供了新的思路。 关键诃：纠错码，循环纠错码，l d p c 码，现场可编程门阵列，i m p u l s ec 编程 作者：张培 导 师：汪一鸣 t h es t u d yo fc o r r e c tc o d e sb a s e do nf p g aa b s t r a c t t h es t u d yo fc o r r e c tc o d e s b a s e do nf i e l dp r o g r a m m a b l eg a t ea n 阏_ p g a a b s t r a c t h o wt o d e s i g nt h ec o r r e c tc o d e s w it h h i g he f f i c i e n c y ，g o o d a n t i l 。i n t e r f e r e n c ea n de a s yi m p l e m e n t a t i o ne q u i p m e n ti st h et a s ko fc o r r e c t c o d e st h e o r y t h eli n e rb l o c kc o r r e c tc o d e sa r et h em o s ti m p o r t a n tb l o c k c o r r e c tc o d e s ，s ot h e ya r ed i s c u s s e di nt h et h e s i s c y c l i c a lc o d e sa n dl d p c c o d e sb o t hb e l o n gt ot h e1i n e rb l o c kc o r r e c tc o d e s f i r s t l y ，u s i n gv h d la st h ei n p u t t e dl a n g u a g e ，t h i st h e s i sg i v e st h e i m p le m e n t a tio no ft h ec o d e r ，d e c o d e ro fac y c lic a lc o d ea n dam _ s e q u e n c e g e n e r a t o rb a s e do nv h d l t h es i m u l a t i o na n da n a l y s e so ft h ep e r f o r m a n c ea r e g i v e nt o o s e c o n d l y ，t h ed e c o d i n ga l g o r i t h ma n di m p l e m e n t a t i o ns c h e m eo f l d p c c o d e sa r es t u d i e d w i t hr e g a r dt ot h ec h a r a c t e r i s t i co fl d p cc o d e s ，t h et h e s i s p r o p o s e sam e t h o dt od e s i g nt h ed e c o d e ru s i n gf p g ap r o g r a m m i n gi ncl a n g u a g e t h ep r o g r a m m i n gm o d e lo fl d p cd e c o d e ri nca n di m p u l s eca r ed e s i g n e d f i n a l l y ， t h ed e c o d e ri si m p l e m e n t e do nh y b r i df p g a j o i n tp r o c e s s o r ，a n dt h ee x c e l l e n t p e r f o r m a n c eo fl d p cc o d e si sp r o v e d an e wi d e ai sp r o v i d e df o rs o f te n g i n e e r s t od e v e l o pe m b e d d e ds y s t e m sb a s e do i lf p g a k e yw o r d s ：c o r r e c tc o d e s ，c y c l i c a lc o d e s ，l d p cc o d e s ， f i e l dp r o g r a m m a b l eg a t ea r r a y ，i m p u l s ecp r o g r a m m i n g w r i t t e nb y s u p e r v i s e db y p e i z h a n g y h n i n gw a n g 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创，| 生声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：i 磁 日 期：b 盘：皇：2 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： i 堑童 e t 期： 导师签名：2 圭二堕 e t 期： p 。j f o 卯8 f 、，五 基于f p g a 技术的纠错码研究 第一章引言 第一章引言昂一早ji 函 1 1 课题的意义 作为信息论的核心内容之一，纠错码理论在通信技术中具有重要意义。在现代通 信系统中，纠错码被用来提高信道传输的可靠性和功率利用率，因为它可以检测并纠 正信号传输过程中引入的错误，抗干扰能力强，所以纠错码的设计是保证数据可靠传 输的一个重要组成部分。 在许多实际差错控制系统中所使用的大部分线性分组码，几乎都与循环码有着密 切关系，都是循环纠错码的子类。目前，循环纠错码被广泛应用于帧校验中。 l d p c 码( l o w - d e n s i t yp a r i t y - c h e c kc o d e s ) 是一种新的高性能纠错码，纠错能 力极强，是目前最逼近香农限的一类纠错码，已成为第四代移动通信编码技术中的首 选。l d p c 码易实现，并且系统复杂度低。相比传统的纠错码，它具有很优异的特点， 在许多情况下有取代t u r b o 码的趋势，具有良好的应用前景，几乎适用于所有信道， 因此成为近年来编码界研究的热点。 因此研究纠错码具有十分重要的学术意义和实际应用价值，对现代通信技术发展 的影响是巨大的。近年来j 国内外对纠错码的理论研究方面已经取得了重要进展，在 工程应用方面的研究也在循序渐进的开展。 f p g a 是f i e l dp r o g r a m m a b l eg a t ea r r a y 的缩写，即现场可编程逻辑阵列，是在 c p l d 的基础上发展起来的新型高性能可编程逻辑器件。利用f p g a 技术来实现数字 信号处理可以很好地解决并行性、可配置性和速度问题。由于f p g a 的开发周期短、 投资风险小、产品上市速度快、市场适应能力强和硬件升级的回旋余地大，所以设计 人员利用它可以在办公室或实验室里设计出所需的专用集成电路，从而大大缩短了产 品上市时间，降低了开发成本。 由于过去割裂了硬件和软件开发工具和开发方法之间的关系，在面向软件应用中 的f p g a ，比传统处理器和d s p 的优势并没有体现出来。本课题提出采用最新一代 基于c 语言的硬件软件协同设计工具，从而可以加速开发过程。 本课题拟在广泛查阅相关资料的基础上，利用信道编码技术的相关理论和f p g a 基于f p g a 技术的纠错码研究 第一章引言 技术，以用c 语言编制的l d p c 码译码器软件为原型，采用q u a r t u si i 、c o d e v e l o p e r 等相关软件分别针对循环纠错码和l d p c 码的算法进行软硬件设计，依次完成循环纠 错码编解码器的设计、l d p c 码译码器的软硬件设计，并进行软件仿真和性能分析。 本课题针对当前通信领域的热点问题，基于f p g a 技术分别对循环纠错码和 l d p c 码进行研究和设计，具有很好的学术理论价值和非常广阔的工程应用前景。通 过本课题的研究，我们可以熟悉循环纠错码、l d p c 码的编译码机制，可以在l d p c 码的算法性能研究上做些探索。另一方面，f p g a 作为当今应用最广泛的可编程专用 集成电路，其在理论和实现方法上目前都比较成熟。因此利用f p g a 技术来开发循环 码和l d p c 码编译码器的设计方案是可行的，也使得本课题具有良好的工程应用能 力，为下一步的实际系统开发奠定了良好的基础。 1 2 国内外研究现状 尽管纠错码理论的提出迄今只有5 0 多年的历史，但随着编码理论和超大规模集 成电路v l s i ( v e r yl a r g es c a l ei n t e g r a t i o n ) 技术的发展，其应用范围越来越广泛。特 别是近年来，国内外在寻求用于各类噪声信道上有效与实用的编码方案方面，以及在 编解码的实现和实际应用上进行了大量研究。 早期r s 译码、卷积译码由于电路实现的复杂性限制其应用，以致被认为只有学 术价值。随着大规模集成电路微处理器技术的发展，使电路复杂性和设计费用大大降 低，设计者可选择不同的手段来实现这些复杂的算法。 近年来，对纠错码研究主要集中于译码算法的结构以及算法的变通上。八十年代 初，国外开始注重开发译码器专业v l s i 产品。换句话说，随着微处理器和超大规模 集成电路的飞速发展，译码专业芯片功能越来越强大，而且其数据吞吐率也越来越大， 为纠错码的广泛应用提供了有利条件，使得系统设计者可以采用性能好的码来改善传 输的可靠性。 如今，在卫星通信、深空通信、行星探测、移动通信、广播电视系统、磁盘、光 盘等众多通信系统中，处处可见纠错码的成功应用。同时随着纠错码技术的日益完善 以及专业芯片的支持，现在许多标准都采用或推荐使用纠错码技术，如欧洲的数字视 频传送d v b ，美国的h d t v 等等均采用了纠错码技术，美国航天局和欧洲空间战在 深空通信中均推荐采用纠错码技术。特别在一些卫星通讯、军用通讯领域中，纠错码 2 基于f p g a 技术的纠错码研究第一章引言 技术的应用更为广泛。 在近十年，国内对纠错码的研究也越来越重视，许多行业都根据自身的特点把纠 错码应用到实际场合中，以此来改善其行业系统性能。而且在v l s i 研究领域成果也 颇多，例如【l 】，f l a f i o n 公司正在研制一种可编程的l d p c 解码器芯片，支持广泛的 l d p c 码设计；a g e r e 公司也在光纤网络上进行全并行的l d p c 码的运行试验。 循环码是线性分组纠错码的一个子集，它具有防止突发错误的保护功能，是目前 研究得比较成熟的一类码。由于循环码具有代数结构清晰、性能较好、编译码简单和 易于实现的特点，因此在目前的计算机纠错系统中所使用的线性分组码几乎都是循环 码。 低密度校验码( l d p c ) 是近几年通信技术领域研究较热的一种新的高性能纠错 码。g a l l a g e r 于1 9 6 2 年提出l d p c 码，并给出了高效的迭代译码算法s p a ( s u m p r o d u c ta l g o r i t h m ) 后，由于该算法计算复杂度高等原因，一直到2 0 世纪9 0 年代中期都极少受到编码界的重视。1 9 9 5 年，m a c k a y 和n e a l 等人重新发现了l d p c 码及其译码算法，并证明了迭代译码算法对于实际系统接近信道容量的重要性，使得 l d p c 码重新得到编码界的重视。此后，在l d p c 码编码算法和译码算法上，不断有 新的高效的算法提出，国外对于l d p c 码的研究也逐步趋于实用化。 前几年国内关于l d p c 码的研究很多都只是停留在理论上的，真正对具体实现的 比较少。国内的高校研究机构也先后提出过一些l d p c 码的改进优化的算法，如西安 电子科技大学的贺玉成等提出量化的b p 算法。国内对l d p c 码的硬件实现与通信系 统的实际应用研究还处于起步阶段。 国外关于l d p c 的研究进展主要分为两方面：一是侧重在理论上研究其性能，包 括如何构造好码，快速译码算法的研究等；另一方面侧重实际应用，包括其在通信系 统、磁记录系统等的应用和硬件实现。诸多报道均表明，为了快速推进l d p c 码的应 用，多种硬件实现方案正在研制过程中。 实际上对于l d p c 码译码器硬件实现的研究主要是从2 0 0 1 年开始的。我们看到的 现在有具体参数的芯片主要有以下3 个：文献 2 】给出的一个吞吐量可达1 6 g b i t s 的码 长为2 0 4 8 的可变码率的l d p c 码译码器芯片；文献 3 】给出的一个吞吐量可达1 g b i t s 的 码长为1 0 2 4 的1 2 码率的l d p c 码译码器芯片；文献 4 】给出的一个吞吐量为5 4 m b i t s 的 码长为9 2 1 6 的1 2 码率的l d p c 码译码器f p g a 芯片。 基于f p g a 技术的纠错码研究第一章引言 其中文献 2 给出的芯片的吞吐量是按1 次迭代计算的，文献 3 采用了3 2 次迭代， 文献 4 用了1 8 次迭代，因此实际上文献 3 介绍的芯片的吞吐量最高，这是因为它采 用了全并行的译码结构，当然这也是以增加芯片复杂度为代价的。 f p g a ( 现场可编程门阵列) 技术是在p a l 、g a l 、p l d 等可编程器件的基础上 进一步发展的产物，在近几年得到了快速发展。这种基于e d a 技术的芯片正在成为 电子系统设计的主流，大规模可编程逻辑器件f p g a 是当今应用最广泛的可编程专用 集成电路a s i c ( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u i t ) ，但在面向软件应用中的f p g a 比传统处理器和d s p 的优势并没有体现出来，f p g a 在设计和工具经验上需要相对 高的投入，在硬件设计语言作为主要的设计输入方式时尤其如此。 使用最新一代基于c 的硬件软件协同设计工具可以加速开发过程。因为大部分 的设计中可以采用熟悉的标准c 语言，尤其在那些本身就是实现算法的硬件电路。 因为设计直接从c 代码编译成最初的f p g a 实现，硬件工程师要参与性能转换的时 间会进一步提早至设计阶段，系统可以用更高效率的软件设计模式来进行设计。 1 。3 课题研究内容 纠错码的研究是现代数字通信技术中的一个非常重要的研究领域。 本课题在广泛查阅相关资料的基础上，首先对纠错码的一般原理进行了研究，重 点讨论了循环纠错码和l d p c 纠错码的编译码原理，此外对所采用的各种开发工具的 基本性能也做了阐述。接下来利用信道编码技术的相关理论和f p g a 技术，采用 q u a r t u si i 、c o d e v e l o p e r 、x i l i n xi s e 等相关软件对循环纠错码和l d p c 码的算法进行 软硬件设计，依次完成了循环纠错码编解码器的设计、l d p c 码译码器的软硬件设计， 并进行软件仿真和性能分析。 由于过去割裂了硬件和软件开发工具和开发方法之间的关系，在面向软件应用中 的f p g a ，比传统处理器和d s p 的优势并没有体现出来。本课题以用c 语言编制的 l d p c 码译码器软件为原型，提出采用最新一代基于c 语言的硬件软件协同设计工 具，从而可以加速开发过程。 1 4 论文结构 本论文的各章节内容概述安排如下： 第章一引言。介绍本课题提出的背景和意义、国内外研究现状，以及本论文 4 基于f p g a 技术的纠错码研究第一章引言 的主要内容和结构安排。 第二章纠错编码原理。简述了纠错码理论基础、循环纠错码原理以及l d p c 码原理。 第三章开发工具的选择。主要介绍了f p g a 设计方法与流程，所使用的开发 环境，并对v h d l 硬件描述语言和基于c 语言的f p g a 设计方法的基本情况做了介 绍。 第四章循环纠错码编、译码器的设计。采用v h d l 语言进行了m 序列发生 器模块的设计，循环纠错码编码器模块和译码器模块的设计，详细描述了设计过程， 并进行性能仿真与分析。 第五章一d p c 码译码器的设计。详细讨论了译码器结构模型与设计方案，译 码器的i m p u l s ec 语言设计，以及利用f p g a 实现译码器设计方案的过程，并分别进 行了桌面仿真与初步硬件分析。 第六章结束语。总结本论文的工作，并对本课题的后续工作提出了进一步研 究的方向。 基于f p g a 技术的纠错码研究第二章纠错编码原理 第二章纠错编码原理 2 1 纠错码理论基础晦1 在实际通信中，由于信道传输特性的不理想和加性噪声的影响，数据在传输过程 中不可避免地会发生错误，当误码率达到一定程度时会导致通信失败。为了保证通信 成功就必须尽量减少信道干扰对信息估值的影响，通常有两个方法来解决这个问题： 一是增加信噪比，另一个是采用信道编码技术，即增加差错控制功能。单纯以第一种 方法来提高信息传输的可靠性，代价比较大。随着编码理论和v l s i 技术的发展，编 译码设备做得越来越简单、成本越来越低，因而纠错码技术在实际的数字通信中逐渐 得到更广泛的应用。 随着对信息传输的可靠性和有效性要求越来越高，差错控制技术在通信中的作用 显得越发重要。对于具体的纠错码可按不同的角度进行分类，具体分类可参考文献 5 ，在此我们仅介绍本文涉及到的内容：循环纠错码和l d p c 码。 分组码是把信源输出的信息序列，以k 个码元划分为一段，通过编码器把这段k 个信息元按一定规则产生尹个校验元，输出长为刀= k + 广的一个码组。因此每一个码 组的校验元仅与本组的信息元有关，而与别组无关，通常用( 九，k ) 表示，其中 表示 码字长度，k 表示信息位长度。 本课题研究的循环码和l d p c 码都可以认为是分组码。循环码的编译码结构相对 简单，但是l d p c 码的译码器设计相对要复杂得多。 2 2 循环纠错码嘲忉 循环码是一类最重要的线性码。它具有严谨的代数结构，且性能易于分析。这种 码的编码和译码设备不太复杂，且检( 纠) 错的能力较强，目前在理论和实践上都有了 较大的发展。 循环码是1 9 5 7 年由普兰奇( p r a n g e ) 提出的，在此后几十年中得到了充分的研 究和发展。起初，人们认识到并感兴趣的是循环码的外在特点，即循环码码字的循环 移位仍然是码字，这个特点给循环码的编译码实现带来了便利。在以后的实践中，人 们从循环群的角度，在代数结构、纠错性能控制等方面找到了循环码更加吸引人的优 6 基于f p g a 技术的纠镨码研究第二章纠错编码原理 越之处。目前，实用差错控制系统中所使用的线性分组码几乎都是循环码或循环码的 子类。 循环码具有许多特殊的代数性质，这些性质有助于按照要求的纠错能力系统地构 造这类码，并且简化译码算法。循环码还有易于实现的特点，很容易用带反馈的移位 寄存器实现其硬件。 2 2 1 循环纠错码的描述 循环码是线性分组码中重要的一个子类。对于一个( 疗，七) 线性分组码，若将其任 意一个码字( c 川，c ，c 。) 的码元向右或向左循环移一位，所得的，c ，c ：，c 。) 或 ( c n - 2 c 。，c o ，已一。) 仍然是码字，则称该码为循环码。一个0 ，砷循环码必有2 上个不同 码组，其中行为码长，k 为信息位数。因此，如果c o = ( _ l , - - c l ，) 是码矢，则左 循环一位后，c l = ( c n 一2 ，q ，c o ，c n 一1 ) 也是码矢。它们各自对应的码多项式是 q ( x ) - c n l z ”一+ c n 一2 x 一一2 + c z x + c o ( 2 一1 ) c j ( 力= c 。一2 工”_ 1 + c 一3 x ”一2 + c o x + c n _ 1 ( 2 2 ) 比较两者可得g ( x ) = x c o ( x ) m o d ( x ”+ 1 ) 。依次类推，循环码循环移2 位、3 位、 ( n - 1 ) 位后仍然应是码字，于是得到一系列等式 c 2 ( x ) = x c l ( x ) = x 2 c o ( x ) m o d ( x 刀+ 1 ) ( 2 3 ) g ( z ) = 工c 2 ( 工) = z 了c o ( x ) m o d ( x 刀+ 1 ) ( 2 4 ) ， c 乙一l ( 功= x c _ 一2 ( z ) = x n - i c o ( x ) m o d ( x ”+ 1 ) ( 2 5 ) 由码空间的封闭性可知，它们的线性组合仍应是码多项式c ( x ) ， c ( x ) = a n i x ”c o ( x ) + 口 一2 x “一2 c o ( x ) + + 口l xc o ( x ) + 口o c o ( z ) 一 = ( 口。一l z ”一1 + 口月一2 x “。2 + + 口l x + a o ) c o ( x ) ( 2 6 ) 式中，m o d ( x ”+ 1 ) 运算仅适用于g f ( 2 ) 。在一个g f ( 2 ) 域上的( 行，k ) 循环码 中，一定存在唯一的次数最低的 一七) 次首一码多项式g ( x ) ，称为( 玎，七) 循环码的生 成多项式。 g ( j c ) = x ”一毒+ g n - k - i x ”一七- 1 + + g l x + l ( 2 7 ) 7 基于f p g a 技术的纠错码研究第二章纠错编码原理 使所有码多项式都是g ( x ) 的倍式，即所有码字都可以写成如下形式 c ( 砂= m 0 ) g ( 力 ( 2 - 8 ) 其中，r e ( x ) 是( 七一1 ) 次信息码组多项式，m ( x ) = 腰“石扣1 + + 班l x + m o ，与七重 信息矢量相对应。 2 2 2 循环纠错码的系统编码 上述循环码的构成方法并不是最方便的方法，因为所生成的码没有采用系统形 式，所以在译码时提取信息会很困难。而系统形式的循环码基于对序列进行模2 长除 法，使用带反馈的移位寄存器可以很容易的实现这种方法。本课题针对的循环码是系 统循环码，要求码字的前七位原封不动地照搬到信息位，而后面的0 一七) 位为校验位。 也就是说一个( 聆，七) 系统循环码的码多项式c ( x ) 可用下式表示， c ) = x - k m ( x ) + ，( x ) ( 2 9 ) c ( 力对应的码字c 即是系统码。式中，( 功是与码字中积一个校验元相对应 的即一七一1 ) 次监督位多项式，它由p ”朋( 列m o d ( g ( 砌后所得到的余式确定。 综上所述，产生系统循环码的具体步骤为：将信息多项式聊( 功预乘x 卜，即右 移( 刀一的位。将x ”聊( 功除以g ( x ) ，得余式r ( x ) 。系统循环码的码多项式写成 c ( x ) = x n - k m ( 功+ ，( x ) 的形式。 循环冗余校验码( c r c ) 是一种系统缩短循环码，被广泛应用于帧校验中，是一 种数字通信中的信道编码技术。经过c r c 方式编码的串行发送序列码，可称为c r c 码，共由两部分构成：k 位有效信息数据和，位c r c 校验码，= 刀一k 。其结构如图 2 - i 所示， 二二五西叵二二二工五团 、， c ( x ) ：n 位 图2 1 循环冗余校验码结构 其中m ( x ) 的k 个系数对应k 位信息，r ( x ) 的( n - k ) 个系数对应积一k ) 个校验位， 从信道编码角度来看，整个, 位帧( 或称分组、信元、单元、包等) 就是一个码字， 习惯上仅把( 一后) 校验位部分称为c r c 码。，位c r c 校验码是通过七位有效信息序列 基于f p g a 技术的纠错码研究 第二章纠错编码原理 被一个事先选择的p + 1 ) 位生成多项式模2 相除后得到的，位余数就是c r c 校验码。 2 2 3 循环纠错码译码原理 设七位信息编成n 位码字c = ( 一l ，c 1 ，c o ) 后送a 信道，在传输过程中受到各 种干扰，接收端的接收码r = ( 一l ，1 ，r o ) 不一定等于发送码c 。显然，收、发码 之间的差异是由信道干扰引起的，定义差错图案e 为 e = ( 一1 ，e l ，e 0 ) = ( r n 一1 一一1 ，1 一q ，场一c o ) = r c ( 2 1 0 ) 差错图案是信道干扰图案的反映。对于二进制码，模- ) o n 与模二减等同，即 e = r + c 等同于r = c + e 。因此可以通过下列运算来判断接收码r 是否有错， l m t = ( c + e ) h t ：c h t + e h t = 0 + e h t = e h t( 2 1 1 ) h 为校验矩阵，如果接收码无误，必有r = c ，即e = 0 及e h l = 0 ，此时上 式满足r h t = 0 。如果信道产生差错而使e 0 ，必有r h t = e h t 0 ，保持h t 不变，则r h l 仅与差错图案e 有关，而与发送什么码无关。为此定义伴随式s 为 s = 0 n - k - l , j 1 , s o - - r h t = e h l ( 2 1 2 ) 译码最重要的任务是由伴随式s 找出c 的估值c ，具体方法是：先算出s ，再由 s 算出e ，最后令c = r + e 而求出c r h t = s e 仑= r + e( 2 1 3 ) 最关键的是从s 找出e ，只要e 正确，译出的码也就是正确的。上述译码过程的 框图如图2 2 所示。 囹南i i 二网呻网上 划l i ：划。 输出r 图2 - 2 译码过程框图 迄今为止，已有从不同角度提出的多种循环码的译码方法，如m e g g i t 译码， p r a n g e 译码、m a s s e y 译码等。最常用的译码方法有捕错译码和大数逻辑译码。其中 9 基于f p g a 技术的纠错码研究第二章纠错编码原理 大数逻辑译码方法是1 9 5 4 年r e e d 提出的，可分成四步进行t 由监督多项式得到校 验矩阵h 。由除法电路计算伴随式s 和正交一致校验矩阵，其中s t = h e t 。 由正交一致校验矩阵判断可纠正的误码个数并构成大数逻辑电路。纠正相应误码， 得到正确的译码输出。 我们已经知道c r c 校验码一般在有效消息发送时产生，拼接在有效信息后被发 送。实际上在进行译码时，在接收端，c r c 码要用同样的生成多项式相除，若除尽表 示无误，弃掉，i 位c r c 校验码，接收有效信息：反之，则表示传输出错，进行纠错或 请求重发。 假设接收码用多项式r o ) 表示，若接收码流无误码，则应有接收码r ) 等于发 送码c ) ，即 r ( 工) = c ( x ) = x n - k 掰( x + ，( 力 ( 2 1 4 ) 此时，接收码尺( 力应能被生成多项式g ( x ) 整除，( 力= 0 。反之，如果不能整 除，r ( x ) 0 ，说明传输中一定出现了误码。 2 3l d p c 码 2 3 1l d p c 码原理嘲 早在2 0 世纪中期，香农( s h a n n o n ) 就提出并证明了著名的“抗干扰信道编码定 理”，它表明平均错误译码概率趋向于零、信道信息传输率无限接近于信道容量的 抗干扰信道编码是存在的。虽然香农并没有给出相应的实现方法，但在这一定理的 指引下，纠错码已发展成信息论的一个专门分支学科。几十年来，随着通信技术的发 展和实际应用的不断增加，人们一直在努力寻找能够更加逼近香农限的高性能的编译 码方法。从早期的分组码、代数码、卷积码，到今天的t u r b o 码、l d p c 码，系统性 能与香农限之间的差距越来越小。表2 - 1 是几种重要编码的指标比较。 表2 - 1 几种重要编码的指标比较 年份码型 误差 1 0 一5 1 9 4 8 s h a n n o n 限 0 d b 1 9 6 7 ( 2 5 5 ，1 2 5 ) b c h 码 5 4 d b 1 9 7 7 卷积码 4 5d b 1 9 9 3 t u r b o 码 0 7d b 2 0 0 1 l d p c 码0 0 0 4 5d b 1 0 基于f p g a 技术的纠错码研究 第二章纠错编码原理 表中第二列为码率等于i 2 的码型。第三列为不同类型码在1 2 码率时，为实现 通信错误译码概率小于1 0 - 5 所需要增加的信噪比。可见l d p c 码是目前最逼近香农限 的一类纠错码。 l d p c 码易实现，并且系统复杂度低，应用于采用正交频分复用技术的无线局域网 及高速光纤通信方面取得了良好的性能。相比传统的纠错码有很优异的特点，具有良 好的应用前景，几乎适用于所有信道，因此成为近年来编码界研究的热点，迭代信号 处理技术也渗透到通信链路的各个环节中。图2 - 3 是一种采用b p s k 调制方式，利用 l d p c 码实现编码、解码的信道模型。 图2 - 3l d p c 编码、调制和解码框图。 2 3 2l d p c 码的构造嘲d 州1 l d p c 码是一种可以用非常稀疏的校验矩阵来定义的线性分组纠错码，它是一种基 于正则的稀疏二分图的编码，因此也称为正则低密度码。l d p c 的编码主要是寻找一种 合适的方法产生稀疏校验矩阵h ，它与其它分组码的校验矩阵的区别在于它的矩阵 中含有大量的o ，仅含有少量的1 。这也就是l d p c 码性能优异的原因所在。该矩阵可以 采用最大长度线性同余序列( m a x i m a ll e n g t hl i n e a rc o n g r u e n t i a ls e q u e n c e ) 产生。 如上所述，一个 ，k ) 的正则l d p c 码由它的校验矩阵h 来定义，其中_ ， k ， k n 。校验矩阵有刀列，即码长为万，每列包含1 的个数为列重，每行包含1 的个 数为行重k 。行数= 冰，) 后，码率为k n 。其它元素均为o 。各行的行重相等，各 列的列重也相等。行重或者列重不一致就称为非正则l d p c 码。 例如，一个( 1 2 ，3 ，6 ) 的h 矩阵可以表示如下： 基于f p g a 技术的纠锗码研究第二章纠错编码原理 m = 在l d p c 码的研究过程中，t a n n e r 提出二分图( b i p a r t i t eg r a p h ) 模型对l d p c 码进 行分析。用二分图表示l d p c 码的优点是便于译码和进行性能分析。二分图和校验矩阵 是直接对应的，由比特节点、校验节点和连接它们的边构成。每个校验节点f ；对应于 h 矩阵的一行，每个比特节点x 。对应于h 矩阵的一列。当码字中某一比特包含在某 校验方程中，即校验矩阵中相应的位为1 时，图2 - 4 中的校验节点和比特节点之间存 在连线。二分图也n q t a n n e r 图。对于每个节点，与之相连的边数称为这个节点的次数 ( d e g r e e ) 。根据二分图中消息节点和校验节点次数分布的不同，l d p c 码可以分为正 则码和非正则码。正则码每个消息节点的次数都相同，每个校验节点的次数也相同； 非正则码消息节点的次数不都相同，校验节点的次数不都相同。 f of 1f 2f 3f 图2 4 奇偶校验矩阵的二分图 文献 1 2 提出用有限几何中的点线来构造l d p c 码，并使其编码时间与长度门成 线性的关系。平时使用的有限几何有两种：欧氏几何和射影几何。这些编码方法都大 大降低了编码复杂度。 2 3 3l d p c 码译码算法的选择n 3 1 们 信道编码的译码算法是决定编码性能和应用前景的一个重要因素。尤其是在长码 的条件下，译码算法的复杂度决定了编码的前途。通常分组码的译码复杂度与码长成 指数关系，导致码长增大到一定程度后无法实际应用。而l d p c 码的译码复杂度与码长 成线性关系，克服了上述分组码在长码长时所面临的巨大译码计算复杂度问题，使得 长编码分组的应用成为可能。 l d p c 码的译码算法有多种，主要是基于t a n n e r 图的消息传递算法m p ( m e s s a g e p a s s i n g ) ，其中最为常用的是置信传播算法b p ( b e l i e fp r o p a g a t i o n ) ，又称为和积 1 2 基于f p g a 技术的纠错码研究第二章纠错编码原理 译码算法s p a 。和积译码算法是一种迭代概率译码算法，每一轮迭代都需要对码字中 各个比特关于接收码字和信道参数的后验概率进行估算，因此准确地说和积译码算法 是一种逐比特最大后验概率( m a p ) 算法。l o g 域的m p 算法，是一种基于对数似然比测 度的和积译码算法，该算法的关键是迭代运算部分的迭代计算后验概率步骤。对数似 然比测度下的和积译码算法的复杂度为码长的线性函数，由于引入了对数似然比，乘 法运算转化为加法运算，降低了每轮迭代的计算复杂度和硬件实现难度，在硬件中的 并行实现能够极大地提高译码速度，因此对数似然比和积译码算法得到广泛认可。该 算法是完全并行的，因此译码速度极高，译码算法的复杂度适中，性能较好，其运算 量不会因为码长增加而急剧增加，这是卷积码及其他线性码所不能比拟的。 关于置信传播算法的研究，美国夏威夷大学的m a r cp c f o s s o r i e r 研究小组做 了很多工作，提出了两种b p 算法的简化算法，可以快速进行迭代译码，只有实数的 加法运算，不需要信道的先验信息，软件和硬件实现都可以获得好的性能和复杂度的 平衡m 1 。国内有学者提出用一个预先计算的表来简化计算的b p 算法，结果接近甚至 超过连续译码算法n 钉。为了提高译码的速度，y o n g y im a o 等提出基于概率的译码算 法n 叮。x i a oy uh u 等提出了不同的减低复杂度的方法，而且给出了并行和串行的实 现方案n 刀。 为了在译码性能和复杂度之间达到更好的平衡，文献 1 4 中提出了一种l o g b p 算法的简化近似算法，称为最小和算法m s a ( m i ns u ma l g o r i t h m ) 。它的性能比l o g b p 算法略有损失，但在复杂度上有大幅度的下降。所以基于硬件实现方面的考虑，本设 计选择采用m s a 算法，计算简洁，避免了进行复杂的计算和查表，复杂度得到了明显 降低，而且译码性能也较好，适合硬件实现。 首先令l 胁q u 1 。g 鬻州俨i o g 器，贝| j m s a 算法步骤女日下： 1 初始化：对于高斯加性白噪声信道，初始化每一比特节点的l ( q u ) ： l ( q o ) = l ( c i ) = 2 m c r z ( 2 1 5 ) 2 迭代： 1 ) 更新每一校验节点的三( “) 校验点更新 基于f p g a 技术的纠错码研究第二章纠错编码原理 三 j i ) = ，r a u i n 川f 三( g ，。- ) f 木，1 - u 川s i g n 三( 9 ，_ ，) ( 2 一1 6 ) 2 ) 更新每一比特节点的工( g f ) 二一比特点更新 三( 旦萝) = l ( q ) + 三( 0 - f ) ( 2 - 1 7 ) j i u 3 判决：计算厶国) = 已嘛) + 芝z 心f ) ， 1 固t 且箍盛嬲等终止条件为饵r = 。 或达到最大迭代次数。 其中锄( 尼) 表示除第歹个校验节点外其他校验节点提供消息的情况下第f 个比 特节点c f = k 的概率；( 后) 表示第f 个比特c f = 露，码字中其它比特满足相互独立 的概率分布时第歹个校验方程成立的条件概率；r ：i ( k ) 和鲂 ) 即为校验节点与信息 节点之间传递的外部信息；u j 表示与第_ ，个校验节点相连的比特节点的集合，u ，f 表示该集合为不包括第f 个比特节点的其它比特节点的集合；u i 表示与第f 个比特节 点相连的校验节点的集合，表示该集合为不包括第，个校验节点的其它校验节 点的集合；q f ( 尼) 表示码字中第f 个比特q = k 的概率。 2 4 本章小结 本章首先简述- j - 幺q 错码理论基础，然后详细讨论了循环纠错码的基本原理和编译 码算法，以及l d p c 码的概念、构造及编码方法、简化的基于置信传播算法的译码算 法的选择。 1 4 基于f p g a 技术的纠错码研究 第三章开发工具的选择 第三章开发工具的选择 3 1f p g a 简介n 州坞1 f p g a 技术是二十年前出现，而在近几年快速发展的可编程逻辑器件技术，随着 f p g a 的规模超过百万门级，它已经成为s o c ( s y s t e mo nc h i p ) 系统集成的重要载 体。与专用集成电路a s i c 相比，二者的设计技术大部分相同，但是f p g a 具有许多 a s i c 所无法比拟的灵活性与快速性。f p g a 基于在线可重构性和可配置计算能力，继 承了a s i c 的大规模、高集成度、高可靠性的优点，又克服了普通a s i c 设计周期长、 投资大、灵活性差的缺点。因此对于a s i c 设计来说，使用f p g a 在实现了小型化、集 成化和高可靠性的同时，减少了风险，降低了成本，缩短了设计周期，避免了昂贵的 重新设计过程。 f p g a 的集成度很高，其器件密度从数万系统门到数千万系统门不等，可以完成 极其复杂的时序与组合逻辑电路功能，适用于高速、高密度的高端数字逻辑电路设计 领域。可以说，f p g a 芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。 f p g a 采用了逻辑单元阵列l c a ( l o g i cc e l la r r a y ) 这样一个新概念，简化的 f p g a 基本由六个部分组成，分别为可编程输入输出模块l o b ( i n p u to u t p u tb l o c k ) 、 可配置逻辑模块c l b ( c o n f i g u r a b l el o g i cb l o c k ) 、嵌入式r a m 模块、丰富的布线 资源、底层嵌入功能单元和内嵌专用硬核等，用户可对f p g a 内部的c l b 和1 0 b 重新 配置。 3 1 1f p f i a 的设计流程 一般来说，完整的f p g a 设计流程大体分为设计输入、功能仿真( 前仿真) 、综合 优化与仿真、布局布线、时序仿真( 后仿真) 、板级仿真验证和配置下载等步骤。 ( 1 ) 电路设计与输入：常用的设计输入方法有硬件描述语言( h d l ，h 鲫蛔a r e d e s c r i p t i o nl a n g u a g e ) 和原理图设计输入方式等。原理图输入法是在图形编辑界面上 绘制出完成特定功能的电路原理图，该方法直观、便于理解、元器件库资源丰富，但 灵活性较差。h d l 的文本输入方法克服了其弊端，具有很好的移植性。其中影响最 为广泛的h d l 语言是v h d l 和v e r i l o gh d l 。本课题采用v h d l 输入方法。 基于f p g a 技术的纠错码研究第三章开发工具的选择 ( 2 ) 功能仿真：电路设计完成后，要用专用的仿真工具对设计进行功能仿真， 验证电路功能是否符合设计要求。 ( 3 ) 综合优化：综合优化( s y n t h e s i z e ) 是将h d l 语言、原理图等设计输入转 换成由与、非、或门、r a m 、触发器等基本逻辑单元组成的逻辑连接( 网表) ，并根 据目标与要求( 约束条件)