可编程器件实现卷积编码和译码的初步实现论文

1、目录第一章绪论11.1卷积码及卷积编码技术的应用1卷积码概述1卷积码技术的应用21.2可编程器件概述21.2.1 FPGA概述31.2.2 FPGA设计51.2.3 FPGA技术的发展趋势5第二章卷积码的编码研究72.1卷积编码的基本原理72.2卷积码的生成矩阵82.3卷积编码的FPGA实现92.3.1 MAX+PLUSSII应用简介92.3.2 基于MAX+PLUSSII平台实现卷积码编码11第三章卷积码的译码研究173.1卷积译码的基本方法173.1.1 码树173.1.2 状态图18网格图183.2 Viterbi译码算法193.2.1 最大似然算法原理193.2.2 Viterbi译码

2、基本原理203.3卷积码的Viterbi译码FPGA实现2230第四章研究小结与心得体会314.1分析小结314.2收获体会31参考文献32第一章 绪 论1.1卷积码及卷积编码技术的应用卷积码又称连环码，它是麻省理工学院的P.Elias于1955年发明的一种非分组码，它和分组码有着明显的区别。在同等码率和相似的纠错能力下，卷积码的实现往往要比分组码简单，但卷积码没有分组码那样严密的数学分析手段，目前大多是通过计算机进行好码的搜索，卷积码主要应用于前向纠错FEC数据通信系统中。1.1.1卷积码概述对输入的码元序列编成长度为k的段，每段附上r (r=n-k) 个监督位,此监督位仅与本组的k个信息位

3、有关，而与其他码组无关，也就是说各个码组间是没有约束关系的，即监督码只监督本码组中的码元有没有错码，解码时也是分组进行解码，这样的码制我们称之为分组码，n在这里代表的是码组长度。而卷积码不同，在任何一段规定时间内编码器产生的n个码元，不仅取决于这段时间中的k个信息码元，而且还取决于前N-1(m)段规定时间内的信息码元，所以监督位监督着这N段时间内的信息。换句话说，各个码内的监督元不仅对本子码有监督作用，而且对前面m个子码内的信息元也是有监督作用的。一般来说，卷积码的结构是：“信息元，监督元，信息元，监督元”。可以用（n,k,m）表示卷积码，k，n通常是比较小的整数，m称为编码记忆（或编码存储）

4、，它反映了输入的信息元在编码器中需要存储的时间长短；N称为卷积码的约束度，它是相互约束的子码的个数；N*n称为约束长度，它表明约束的二进制码元的个数。用下图1-1-1来说明卷积码编码器的一般结构:图1-1-1 卷积编码器结构它包括:一个由N段组成的输入移位寄存器，每段有k级，共Nk位寄存器;一组n个模2和加法器;一个由n级组成的输出移位寄存器。对应于每段k个比特的输入序列，输出n个比特。由图可知，n个输出比特不但与当前的k个输入比特有关，而且与以前的(N-1)k个输入比特有关。整个编码过程可以看成是输入信息序列与由移位寄存器模2和连接方式所决定的另一个序列的卷积，故称为卷积码。卷积码技术的应用

5、在数字通信卫星中，卷积码的性能要优于分组码，因而能够得到广泛的应用，卷积码的维特比译码在译码约束度较小，一般在N<10的情况下计算速度快，效率高，译码器也较简单，随着微电子技术的发展和PLD技术的普遍使用，在软件开发工具的帮助下，维特比译码器由硬件来实现已成为可能。同时在数字通信过程中，降低误码率，提高通信质量是很关键的问题，卫星通信是远距离传送数据，需要很高的能量来降低各方面的干扰，而卫星体积是受限的，功率很难达到理想的状况，采用卷积码维特比译码可以降低误码率，实现强大的纠错能力，突破卫星信道功率受限的弱点，改善通信效率。另外，卷积码在码分多址(CDMA)和数字蜂窝移动个人通信网(PC

6、N)中也有广泛的应用。在PCN中,IS95标准1建议对信息传输的差错控制采用大约束度(K=9)卷积编码和最大似然的Viterbi译码方案,而满足IS95标准的Viterbi译码器至今没有面市。研究用现场可编程门阵列(FPGA)来实现K=9的差错控制器的问题是重中之重。因为,一旦用FPGA研制成功,就可进行低功耗超大规模电路集成(VLSI)，制成高性能单片差错控制器，应用于PCN；另一方面，VLSI方案具有高得多的处理速率，适用于更为广泛的数字通信场合。基于FPGA的卷积码译码器是充分利用了FPGA的资源丰富的特点，设计特定的模块使的幸存路径的选择更加快捷和有效。1.2可编程器件概述可编程器件P

7、LD（Programable Logic Device)是80年代发展起来的新型器件，PLD是一种由用户根据自己的需要来设计逻辑功能并对此器件进行编程后实现的。数字电路的集成电路通常是标准的小规模、中规模、大规模的器件，而这些器件的逻辑功能是出厂时已经由厂商设计好了，用户只能根据其提供的功能及管脚进行设计其需要的电路，由于这些通用器件考虑到其通用性，其在使用时有许多功能是多余的，并且由于管脚的排布是固定的，在设计PCB时给电路的连线带来了极大不便，而PLD其内部具有大量组成数字电路的最小单元门电路，而这些门电路并没有固定怎样连接，并且输入/输出脚的连接可自己设置，而这些门电路的连接是通过编程的

8、方法加以设计，故这种电路给我们带来了极大的方便。（1）提高了功能的集成度PLD器件较中小规模集成芯片具有更高的功能集成度，一般来说一片PLD器件可替代420片的中小规模集成芯片，而更大规模的PLD（如CPLD、FPGA)一般采用最新的集成电路生产工艺及技术，可达到极大的规模，这些器件的出现降低了电子产品的成本和缩小了电子产品的体积。（2）加快了电子系统的设计速度一方面由于PLD器件集成度的提高，减小了电子产品设计中的布线时间及器件的安装时间；另一方面由于PLD器件的设计是利用计算机进行辅助设计的，其可以通过计算机的辅助设计软件对设计的电路进行仿真和模拟，减小了传统设计过程中的调试电路的时间，另

9、外由于PLD器件是可擦除和可编程的，故即使设计有问题修改也是很方便的。（3）高的性能由于PLD器件在生产过程中采用了最新的生产工艺及技术，故通过PLD器件的性能优于一般通用的器件，其速度一般比通用器件速度高一到两个数量级，另外由于器件数量的减少，降低的电路的总功耗。（4）高可靠性系统的可靠性是数字系统的一项重要指标。根据可靠性理论可知器件的数量增加，系统的可靠性将下降；反之将提高。采用了PLD器件可减少器件的数量，器件的减少还导致PCB的布线减少，同时也减少了器件之间的交叉干扰和可能产生的噪声源，使系统运行更可靠。（5）成本低由于PLD器件的上述优点将导致电子产品在设计、安装、调试、维修、器件

10、品种库存等方面的成本下降，从而使电子产品的总成本降低，提高了产品的竞争力。1.2.1 FPGA概述FPGA是Field Programmable Gate Array（现场可编程门阵列）的缩写，代表的是一种可编程逻辑器件，它可以在制造完成后由用户根据自己的需要定义其逻辑功能。FPGA包含了一个逻辑单元（可以是门，也可以是查找表RAM）的阵列、触发器以及可编程的互连线。除此之外，现在的一些大规模FPGA还包含了片内RAM、嵌入式CPU、高速收发器等资源。FPGA 的显著特点是有一个窄输入的逻辑单元，使用分布式互连方案，相对于传统的诸如PAL和PLA之类的可编程逻辑器件来说，FPGA的设计更加灵活

11、。FPGA是PAL、GAL、EPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点，是电子设计领域中最具活力和发展前途的一项技术，它的影响丝毫不亚于70年代单片机的发明和使用。FPGA在现代数字电路设计中发挥着越来越重要的作用。从设计简单的接口电路到设计复杂的状态机，甚至设计“System On Chip（片上系统）”，FPGA所扮演的角色已经不容忽视。FPGA所具有的静态可重复编程和动态在系统重构的特性，使得硬件的功能可以像软件一样通过编程来修改，这样就极大地提高了电子系统

12、设计的灵活性和通用性，缩短了产品的上市时间并降低了电子系统的开发成本。基于此，FPGA设计技术受到了世界范围内广大电子工程师的普遍欢迎，现已成为电子工程师必须掌握的一项基本技能之一。FPGA采用了逻辑单元阵列LCA（Logic Cell Array）这样一个新概念，内部包括可配置逻辑模块CLB（Configurable Logic Block）、输出输入模块IOB（Input Output Block）和内部连线（Interconnect）三个部分。可配置逻辑模块CLB是实现各种逻辑功能的基本单元，其中包括组合逻辑单元，时序逻辑，RAM及各种运算功能。CLB是以nn阵列形式分布在FPGA中,同

13、一系列中的不同FPGA,其阵列规模也不同;输入输出模块IOB是芯片外部引脚数据与内部数据进行交换的接口电路,通过编程可将I/O引脚设置成输入,输出和双向等不同的功能;金属导线以纵横交错的格栅状结构分布在两个层面,有关的交叉点上连接着可编程开关或可编程开关阵列,通过对可编程开关和可编程开关矩阵的编程实现CLB与CLB之间，CLB与IOB之间,以及全局信号与CLB和IOB之间的连接。FPGA的基本特点主要有：1.采用FPGA设计ASIC电路，用户不需要投片生产，就能得到合用的芯片。2.FPGA可做其它全定制或半定制ASIC电路的中试样片。3.FPGA内部有丰富的触发器和IO引脚。4.FPGA是AS

14、IC电路设计周期最短、开发费用最低、风险最小的器件之一。5.FPGA采用高速CHMOS工艺，功耗低，可以与CMOS、TTL电平兼容。可以说，FPGA芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。FPGA是由存放在片内RAM中的程序来设置其工作状态的，因此，工作时需要对片内的RAM进行编程。用户可以根据不同的配置模式，采用不同的编程方式。加电时，FPGA芯片将EPROM中数据读入片内编程RAM中，配置完成后，FPGA进入工作状态。掉电后，FPGA恢复成白片，内部逻辑关系消失，因此，FPGA能够反复使用。FPGA的编程无须专用的FPGA编程器，只须用通用的EPROM、PROM编程器即可。当

15、需要修改FPGA功能时，只需换一片EPROM即可。这样，同一片FPGA，不同的编程数据，可以产生不同的电路功能。因此FPGA的使用非常灵活。FPGA有多种配置模式：并行主模式为一片FPGA加一片EPROM的方式；主从模式可以支持一片PROM编程多片FPGA；串行模式可以采用串行PROM编程FPGA；外设模式可以将FPGA作为微处理器的外设，由微处理器对其编程。FPGA设计(1)设计流程设计输入：主要有原理图输入和HDL输入两种方式，一般开发软件都能够同时支持这两种输入方式。还有的甚至提供更多的输入方式，如Xilinx公司的ISE6.0就提供四种输入方式，包括EDIF网表输入。 设计仿真：包含功

16、能仿真和时序仿真两项主要内容，功能仿真忽略了综合和布局布线导致的时延等因素，仅仅从逻辑上进行仿真，这对设计思路的验证是有帮助的，但必须通过时序仿真作进一步验证，发现并修正时序问题。 设计综合：将HDL语言生成用于布局布线的网表和相应的约束。综合效果直接导致设计的性能和逻辑门的利用效率，因此，许多开发软件都支持第三方综合和仿真工具，著名的有：Synplicity、Synopsys和ModelSim等。 布局布线：工具利用综合生成的网表，在FPGA内部进行布局布线，并生成可用于配置的比特流文件（有了比特流文件就下载到板子里了)。布局布线工具与可编程逻辑器件工艺及其布线资源密切相关，一般由可编程逻辑

17、器件开发商直接提供。 (2)FPGA设计时注意的问题本人在使用Altera公司开发的MAX+PLUS II软件进行电路图输入的设计过程中,体会到有些问题是初学FPGA设计的同学要注意的:1.异步逻辑主要用组合逻辑来实现控制,容易因时钟传递延时不一致而产生毛刺,建议尽量改成同步逻辑,当输出信号用于RESET,CLEAR,PRESET时最好改成同步。2.组合逻辑容易设计，但要注意处理好毛刺，最好分析出毛刺产生的原因，然后重新设计新的电路。3.选择模块可以节省设计时间，但不是必须所有的过程都使用。FPGA技术的发展趋势随着微电子技术、EDA技术、以及应用系统需求的发展，FPGA正在逐渐成为数字系统开

18、发的平台，并朝着以下方面发展和提高：1.高集成度、大容量、低成本、低电压、低功耗；2.资源多样化；3.适用于片上系统：处理器、高速串行I/O DSP等等；4.深亚微米工艺的使用，基于90nm工艺的FPGA已经商用，正在向65nm挺进；5.各种软硬IP库的发展和完善；6.动态可重构技术实用化；新FPGA器件在复杂设计、增加总的逻辑资源、改进布线与软件以及在系统中对器件进行编程的能力方面正在仿照ASIC。深亚微米技术使可编程器件的逻辑单元更小。另一个明显的发展趋势是一些产品采用部分存储器结构作为专用存储器而不仅作为逻辑切换驱动器。此外，可编程密度已在传统上限制了性能和密度。这促使一些厂商考虑将AS

19、IC和FPGA技术混合，以生产出能按用户编程定制的高性能、高密度的混合功能器件。 同时FPGA工具组也在升级,这种从逻辑级向以语言为基础的设计变迁，意味着综合技术利用的增加。从这一点看，FPGA工具与设计流程的通用性越多，从可编程器件向硬件连线ASIC转移就越容易。FPGA的发明和在全球范围内的广泛使用是电子设计领域的一场革命，目前正处于高速发展阶段。每年都有高集成度的新产品投入市场，同时也有支持它们的强大的EDA工具的问世。FPGA不但使电子系统的性能得到了增强，更重要的是它使电子系统的设计发生了根本性变革，使得一切设计仿真测试工作能够在个人电脑和开发平台(EDA工具)的支持下通过模拟仿真的

20、形式通过。FPGA作为一个比较新的领域，在最近几年中有很大的发展和进步。各个厂家的FPGA不断推陈出新，工艺越来越高、速度越来越快、功能越来越多，价格却越来越便宜。各种依靠FPGA技术设计的芯片已在信号纠错,总线接口,高速数据采集,通信领域编解码,嵌入式系统,数字图象处理,数字信号处理得到了广泛的应用。随着FPGA成本的进一步降低和规模的增加，在未来几年中FPGA应该有更加宽广的应用领域。第二章卷积码的编码研究2.1卷积编码的基本原理以下图2-1-1的（2，1，2）卷积编码器为例来分析卷积码的编码原理和编码方法。图2-1-1 原理框图（2，1，2）卷积编码器是由2个移位寄存器，2个模2加法器和

21、开关电路组成。在编码前，对每一级的移位寄存器进行清零，每输入一个信息码元，将会输出C1,C2各一次，即1比特的信息输入将有2比特的信息输出。其中输入与输出之间的编码关系可用下面的式子表示出来：C1=S1S2S3C2=S1S3S1是当前的输入的信息位，S2, S3是移位存储器前两个信息位。输出信息的顺序是信息位在前，监督位在后，即输出的码元以“信息位,监督位,信息位,监督位,监督位,信息位,监督位， , 信息位,监督位,监督位”的形式表示。本人在初始编码时，每一级的移位寄存器的状态全部清零，输入1101000此时编码器输出状态如下表2-1-1表示：表2-1-1 输入输出状态列表输入(S1)110

22、1000S20111000S30010110c11000110c21110010经过(2,1,2)卷积编码器的编码后输出的信号码元将会是“11，01，01，00，10，11，00”2.2卷积码的生成矩阵卷积码是线性码，因此它完全可以由生成矩阵和校验矩阵来确定。以比较简单的（2，1，2）卷积码编码器为例阐述生成矩阵的规律,见图2-2-4。mjmj-2mj-1图2-2-4 生成矩阵输出码元可以用下面的表达式来表示： Cj1 = mjmj-1 mj-2Cj2 = mjmj-2输入信息位是(m0,m1,m2,mj)，输出位C0,C1,C2,C3,C4可以用下面形式表示出来 C0：C01=m0 C1:

23、C11=m0m1 C2: C21 =m0m1m2C02=m0C12 =m1 C22 =m0m2C3:C31=m1m2m3 C4: C41=m2m3m4C32=m1m3 C42=m2m4输出码元(C01,C02,C11,C12,C21,C22,C31,C32,C41,C42, ) 用矩阵形式表示： C01,C02,C11,C12,C21,C22,C31,C32,C41,C42, 1110110000.001110110000001110110000001110=m0,m1,m2,m3,m4, 由卷积码生成矩阵定义可得(2,1,2)卷积码的生成矩阵是：11101100000011101100000

24、01110110000001110从生成矩阵可以找出以下规律：1.第二行是由第一行右移2位（一个子码的长度）得到，第三行是由第二行右移2位得到，依次类推。2.除第一行前6个数字外，以后的数字全部是0，这前6个数字组成基本生成矩阵，如果基本生成矩阵给定的话，就有可能得到整个编码序列。2.3卷积编码的FPGA实现 MAX+PLUSSII应用简介(1)MAX+PLUSSII概述Max+plus是Altera公司提供的FPGA/CPLD开发集成环境，Altera是世界上最大可编程逻辑器件的供应商之一。Max+plus界面友好，使用便捷，被誉为业界最易用易学的EDA软件。在Max+plus上可以完成设计

25、输入、元件适配、时序仿真和功能仿真、编程下载整个流程，它提供了一种与结构无关的设计环境，是设计者能方便地进行设计输入、快速处理和器件编程。Max+plus开发系统的特点开放的界面Max+plus支持与Cadence，Exemplarlogic，Mentor Graphics，Synplicty，Viewlogic和其它公司所提供的EDA工具接口。与结构无关Max+plus系统的核心Complier支持Altera公司的FLEX10K、FLEX8000、FLEX6000、MAX9000、MAX7000、MAX5000和Classic可编程逻辑器件，提供了世界上唯一真正与结构无关的可编程逻辑设计环

26、境。完全集成化Max+plus的设计输入、处理与较验功能全部集成在统一的开发环境下，这样可以加快动态调试、缩短开发周期。丰富的设计库Max+plus提供丰富的库单元供设计者调用，其中包括74系列的全部器件和多种特殊的逻辑功能（Macro-Function）以及新型的参数化的兆功能（Mage-Function）。模块化工具设计人员可以从各种设计输入、处理和较验选项中进行选择从而使设计环境用户化。硬件描述语言（HDL）Max+plus软件支持各种HDL设计输入选项，包括VHDL、Verilog HDL和Altera自己的硬件描述语言AHDL。Opencore特征Max+plus软件具有开放核的特点

27、，允许设计人员添加自己认为有价值的宏函数。（2）设计流程：使用Max+plus软件设计流程由以下几部分组成。如图2-3-1所示。1、设计输入：可以采用原理图输入、HDL语言描述、EDIF网表输入及波形输入等几种方式。2、编译：先根据设计要求设定编译参数和编译策略，件的如器选择、逻辑综合方式的选择等。然后根据设定的参数和策略对设计项目进行网表提取、逻辑综合和器件适配，并产生报告文件、延时信息文件及编程文件，供分析仿真和编程使用。3、仿真：仿真包括功能仿真、时序仿真和定时分析，可以利用软件的仿真功能来验证设计项目的逻辑功能是否正确。4、编程与验证：用经过仿真确认后的编程文件通过编程器（Progra

28、mmer）将设计下载到实际芯片中，最后测试芯片在系统中的实际运行性能。在设计过程中，如果出现错误，则需重新回到设计输入阶段，改正错误或调整电路后重复上述过程。图2-3-2是Max+plus编译设计主控界面，它显示了Max+plus自动设计的各主要处理环节和设计流程，包括设计输入编辑、编译网表提取、数据库建立、逻辑综合、逻辑分割、适配、延时网表提取、编程文件汇编（装配）以及编程下载9个步骤。图2-3-1 开发流程图2-3-2 编译主控界面 基于MAX+PLUSSII平台实现卷积码编码仍以（2，1，2）卷积码编码器为例来描述卷积码编码译码的FPGA 实现。整个FPGA的电路搭建和仿真模拟都是在MA

29、X+PLUSSII的平台上来完成的。（2，1，2）的卷积编码译码器实现起来较为简单和方便，同时它的应用也很广泛，在查阅了很多的相关资料后发现（2，1，2）卷积码编码译码器在水下无线通信传输系统和卫星通信领领域应用最为普遍。（1） 编码器的FPGA实现过程分析（2，1，2）卷积编码器是在一个码元输入后将会有两个码元输出，我们根据上面提到的编码表示方法中的状态图可以把卷积码的编码器看作是一个简单的状态机。假设某个时刻编码器的状态为10，即状态c,在输入端，如果输入的信息序列是0，则下一时刻编码器的状态是a,对应的输出为11；如果输入信息序列为1，则下一时刻编码器状态为b,对应的输出为00。根据各个

30、状态之间的关系可以得出状态转移图，用寄存器保存对应的状态。我们也可以根据输入与输出之间的简单模2加的关系来实现编码过程，这里提到的状态机是对于输入输出较为复杂的情况时效率要高，本人采用的是根据输入输出之间的关系的方法来实现编码的。每位信息码元送入编码模块后，编码模块立即进行编码，编码结束后保存新的状态变量，同时得到并行输出的码元，（2，1，2）卷积编码器的编码效率R=1/2,表明如果仅仅用一个时钟的话，编码的输入和输出不能同步起来，在设计的过程中，加上一个分频模块，达到编码器的输出控制时钟是输入控制时钟频率的2倍的效果。考虑到现在得到的是并行输出的数据，需要加入一个并串转换模块来保证码元串行输

31、出，这个模块可以用移位寄存器来实现，也可以根据具体的卷积码来选择合适的电路实现并串转换功能。（2） 编码器的原理图一般卷积编码器原理框图见图2-3-3并串转换模块编码模块串并转换模块图2-3-3 编码器原理框图卷积码编码器主要由移位寄存器构成，输入数据经串并变换器后形成k bit一帧的并行数据送到编码模块中去，这里的编码模块是线性逻辑单元和移位寄存器，每读入一个新的数据帧，旧的数据帧就向右移一帧，编码模块根据当前输入的数据帧和存放在数据帧寄存器中以前消息数据进行线性逻辑运算后得到n （bit）的编码输出，再经过并串模块转换成串行输出的数据。串并转换模块是把串行输入的数据转换成并行输出的数据输入

32、到编码模块中，由于我设计的是（2，1，2）卷积编码器，这里k=1，因此这一个串并转换的模块在整个编码器中就不需要考虑，信息码元可以直接输入到编码模块中去。编码模块是由D触发器组成的移位寄存器和异或门组成，D触发器在上升沿到来时是有效的，其他输入端的信息详见状态表2-3-1表2-3-1 （Qo*： level of Q before Clock pulse）InputsOutputCLRNPRNENADCLKQLHXXXLHLXXXHLLXXXIllegalHHLXXQo*HHHLLHHHHHHHXXLQo*编码模块在Max+plus中电路图见图2-3-4图2-3-4 编码模块编码后的波形图见下

33、图2-3-5图2-3-5 编码后的波形图从仿真的波形图上我们可以看出，当输入的信息是1101000时，得到的输出信号C1是1000110，输出信号C2是1110010。由于这里的（2，1，2）卷积编码器的输出是两个码元，所以选择了2位数据选择器来把输入到并串转换模块的信息码元以串行的形式把数据输出，这样在信息码元一个时钟周期内将会有C1，C2两个码元数据输出，其中前半个时钟周期输出C1，后半个时钟周期输出C2，OUT端输出的就是串行数据。并串转换模块在Max+plus中电路见图2-3-6。图2-3-6 并串转换模块编码模块和并串转换模块连在一起的电路见图2-3-7图2-3-7编码器输出码元的仿

34、真波形图2-3-8见输出端OUT，我们明显可以看到在一个时钟周期内有两个码元输出，最后的输出结果是“11，01，01，00，10，11，00”图2-3-8仿真波形图第三章 卷积码的译码研究3.1卷积译码的基本方法卷积译码分为代数译码和概率译码。代数译码是根据卷积码的本身代数结构进行译码，译码时不考虑信道的统计特性，该方法的硬件实现简单，但性能较差，主要方法是大树逻辑译码（门限译码）；概率译码在计算时不仅利用了卷积码的代数结构，而且还要考虑信道的统计特性，这种译码是建立在最大似然准则的基础上，提高了译码性能，但增加了硬件实现的复杂度，常用的译码方法有Viterbi和序列译码。3.1.1 码树码树

35、描述的是在数据序列输入时，码字所有可能的输出对应于(2，1，2)卷积编码器，码树图可用下图2-2-1来表示，在图中每一个节点对应于一个输入码元，当输入是0时，走上分支；输入是1时，走下分支，编码器的输出码元C1,C2标在每个分支的上面。图中的a,b,c,d表示S3,S2的状态，状态的编码规则如表3-1-1：表3-1-1 状态编码规则 图3-1-1（2，1，2）卷积编码器码树图（2，1，2）卷积码的码树图状态S3,S2a00b01c10d11从码树图上可以看出：从第四条支路开始，码树的各节点从上面开始重复出现a,b,c,d四种状态，并且码树的上半部分和下半部分是完全相同的，这就是表明从第4位输入

36、码元开始，无论输入的第一位信息码元是0或1，编码输出是没有影响的，输出码元已和输入的码元已经没有关系了，定义约束度N=3的含义也就在于此。 状态图卷积码的状态图给出的是编码器当前状态和下一个状态之间的关系，如下图3-1-2所示(虚线表示输入码元是1的路径，实线表示输入码元是0的路径，圈内的字母表示此时的编码器状态，路径上的数字是输出的码元)图3-1-2 （2，1，2）卷积编码器状态图网格图在码树图中，从同一个节点出发的分支都相同，可以把状态相同的节点合并在一起得到更加紧凑的表示方法，这个图示的作用在卷积码的译码过程中可以得到充分的体现（图中每一个节点表示的是a,b,c,d四种状态，对应于输入码

37、元是0的情况，用实线表示；对应于输入码元是1的情况，用虚线表示）见图3-1-3图3-1-3 网格图图2-4 网格图Viterbi译码在卷积码的约束长度较小时，比序列译码的方法效率更高，速度更快，译码器的设计也较简单，目前已经广泛应用于各种数字通信系统中。3.2 Viterbi译码算法Viterbi译码是一种最大似然算法，最大似然算法的基本思路是,把接受码字与所有可能的码字比较，选择码距最小的码字作为解码输出。Viterbi译码同时也是在最大似然算法的基础上对其进行了简化，它把接受码字分段累计处理，每接受一段码字，需要计算，比较一次，保留码距小的路径，直到译码完所有的序列。 最大似然算法原理下图

38、3-2-1是一个卷积编码译码的系统模型，信息码元M经过卷积码编码器后成为发送序列C,发送序列C经过DMC（离散无记忆信道）,在接受端，译码器接受经DMC后的序列R,译码输出序列M图 3-2-1 系统模型图3-2-1 卷积编码译码的系统模型输入码元序列为C，输出为R的概率为：P(R/C)=对上面的式子取对数得到：log P(R/C)=是信道的转移概率，log P(R/C)是C序列的似然概率，由贝叶斯公式，log P(R/C)= 取对数后得到：log P(R/C)=logP(R)+logP(C/R)-logP(C)式子中，P(R)是接受序列R的概率，P(C/R)是C的后验概率，P(C)是发送序列为

39、C的概率，在发送序列为等概率的情况下，最大似然译码就等于最大后验概率译码。在二进制对称信道下，最大似然译码就是最小汉明距离译码，也就等于最大后验概率译码。 Viterbi译码基本原理译码器接受到R序列后，按照最大似然法则寻找编码器在网格图上走过的路径，也就是寻找最大度量的路径，对于二进制对称信道，就是寻找与R由最小汉明距离的路径。最大似然译码只是一种译码准则，实现起来有一定困难，因为译码器每接受一个序列R就要计算很多的似然函数才可以做出译码判决，维特比针对这个实现的困难提出了一种算法，后来称为维特比算法。维特比算法的基本思想是接受一段信息码元后就进行计算和比较，在每个状态时选择最可能进入该状态

40、的分支，这样可以留下与R距离最小的路径（幸存路径），而去掉其它可能的路径，同时把幸存路径按逐分支地存储起来，幸存路径的数目等于状态数。归纳维特比算法的基本步骤如下：（1）在第j（jm）时刻以前，译码器计算所有的长为m个分支的部分路径值，对进入2km个状态的每一条路径进行保留；（2）第m个时刻开始，对进入每一个状态的部分路径值进行计算，这样的路径有2k条，挑选具有最大部分路径值的部分路径为留选路径，删除进入该状态的其它路径，然后，留选路径向前前延长一个分支；（3）重复第（2）部的计算，比较和判决过程；（4）如果进入某个状态的部分路径中有两条相同的部分路径值，则可以选择其中一条作为幸存路径。本人仍

41、以（2，1，2）码为例说明整个译码的基本思想：设发送序列为全零序列，而接受序列为R=01,00,00,10,00,00,假设译码器的初始状态全为零，在第0个时刻时，接受序列的第0个分支R001进入译码器，从网格图可以看出从a状态有2个分支，它们是00和11，R0和这两个分支进行比较，比较的结果和到达的状态如下表3-2-1。表3-2-1幸存路径第0个分支的距离第1个分支的距离001S0111S1第1个时刻态进入译码器的接受码组R1=00将和此时刻出发的四条分支进行比较，比较结果和到达的状态如下表3-2-2。表 3-2-2上次距离留选路径延长分支本分支距离累加距离到达状态1000001a1123b

42、1111012c0112d第1个时刻到第2个时刻共有4条路径，到达状态a,b,c,d。在第二个状态以前译码器不做任何的选择和判决，路径选择存储器存储此刻的留选路径：0000，0011，1110，1101，并且路径存储器存储此时刻到达该状态的幸存路径累加值。从第2个时刻起，第2个接受码组R2=00进入译码器，从网格图上看出，从第2个时刻到第3个时刻，进入每个状态的分支有两个，译码器将接受码组R2与进入每个状态的两个分支进行比较和判决，选择一个累加距离最小的路径作为进入该状态的留选路径，比较和判决的过程见表3-2-3。表 3-2-3上次距离留选路径延长分支本分支距离累加距离到达状态10000000

43、1a1123b300111014c0114d211101124a0002b211010113c1013d上面介绍的是以最小汉明距离为度量的译码器是硬判决译码器，适合于二进制对称信道，在实际应用的过程中为了提高译码的可靠性，充分利用信道输出信号的有关信息，把输出的信号进行Q电平的量化，然后再输到维特比译码器里进行译码，这样的译码器是软判决译码器，适合于离散无记忆信道。软判决维特比译码算法和硬判决维特比译码算法的译码过程很相似，唯一的差别是软判决不应用汉明距离，它使用的是欧氏距离。维特比译码算法解码简单,计算快,已经得到了广泛应用,特别是在卫星通信和蜂窝网通信系统中的应用。3.3卷积码的Viter

44、bi译码FPGA实现在Viterbi译码算法的FPGA实现设计中，译码器有6个模块组成，它们分别是支路度量模块，加法比较选择模块，最大似然判决模块，回溯模块，路径度量存储器，幸存路径存储器。其中加法比较选择模块是译玛器中的关键环节，它的设计好坏在一定程度上决定了卷积码译码器的复杂程度和工作效率的高低。同时法比较选择是运算最多的环节，度量的保存和路径的保存都会用到很大的RAM空间，需要选择合适的FPGA来完成。Viterbi译码FPGA实现的总体框图见图3-3-1。支路度量模块：对于每一时刻的输入码元，为每一个状态生成相应的支路度量，也就是说它用于产生接受序列与状态转移分支上的编码输出数据之间的

45、距离。由于分支度量运算过程中没有平方运算，可以将状态转移分支上的编码输出数据（比特度量值）存储在查找表内，这样只需要进行加减和查找表运算，可以降低计算的复杂度，软判决在FPGA中一般可以用查找表来实现。在硬判决支路度量模块中，度量值的计算只需要一个判决门限，即对输出进行判决。 加法比较选择模块：根据Viterbi译码算法原理，将支路度量和前一个时刻存储的路径度量相加比较，得到这一时刻的路径度量和相应的判决。对于（2，1，2）卷积码来说有4个状态，也就是每一次转换中需要计算多个路径度量值，需要4个加法比较选择模块，每个一个加法比较选择模块由2个加法器，1个比较器和1个选择器组成，这样由8个加法器

46、，4个比较器和4个选择器可以完成一次状态的转换。同时加法比较选择模块决定着译码速度，并行性越好，译码速度就越高。图3-3-2表示一个加法比较选择模块。图3-3-3表示加法比较选择模块内部的加法器，比较器，选择器与路径度量存储器，幸存路径存储器之间的具体连接示意图。最大似然模块：在所有状态的路径度量中找出最大值，具有最大路径度量的幸存路径便是最大似然路径，在某一时刻，最大似然模块判决最大似然路径，将其末端节点状态送入回溯模块存储起来。回溯模块：回溯模块也是译码器中的一个关键模块，它结合最大似然模块挑出最大似然路径。在控制信号的控制下根据地址信息到幸存路径寄存器中提取比特信息，在找出最大似然路径的

47、时候产生一个最小状态信号，最小状态信号和提取出的最小路径信号比特进行逻辑组合后最后产生译码输出。路径度量存储器：用于存储每一状态的路径度量值，取出的结果与前一个时刻的路径度量值在加法比较选择模块中的加法器完成相加功能。幸存路径存储器：设计完成幸存路径的选择，交换，存储等功能，在FPGA中用特定的RAM来作为存储器。接口电路1：连接加法比较选择模块与路径度量存储器之间的模块。接口电路2：连接最大似然模块与幸存路径存储器之间的模块。本人重点以加法比较选择模块和最大似然模块为基础来阐述Viterbi译码算法的基本思想。由于总体电路图比较复杂，分成3部分来描述：第一部分（见图3-3-4）是每一时刻每一

48、状态的比较部分，通过模2加运算相同比特为0，不同比特为1的原则，如果产生一个高电平，则完成一次计数，全部计数完成后得到这一时刻每一个状态的汉明距离。在第一部分电路图中的3add表示的是3位同步加计数器，它是由3个JK触发器组成（内部电路见图3-3-5）图3-3-4 前3时刻状态的比较图 3-3-5 3位同步加计数器第一部分可以看作是计算路径度量值的模块，相当于支路度量模块，这里计算出的是每一个时刻每一个状态的汉明距离。本人以输出码元是“00，00，00”为例来描述这一部分的功能。a状态到达b状态这一状态转换的输出码元序列是“11”,与输出码元“00”比较后计数器的输出应该是2，即汉明距离是2。

49、验证的波形见图3-3-6。图3-3-6 波形验证从波形图里可以看出计数器从000到001再到010，表明计数器计数的结果是2，意味着汉明距离是2。第二部分是加法器部分，由于只考虑了3个时刻汉明距离的累加，累加和最大是6，因此选择多个3位加法器即可实现（一个3位的加法器见图3-3-7）图3-3-7 3位加法器其中hadd是半加法器（图3-3-8），fadd是全加法器（图3-3-9） 图3-3-8 半加器图3-3-9 全加器第二部分的完整电路图见图3-3-10，它由12个3位加法器加法器组成，完成的输入码元进入译码器后前3个时刻8条路径汉明距离的累加。图 3-3-10 汉明距离的累加第一部分和第二

50、部分电路图完成8条路径汉明距离的计算，两部分和在一起的电路图见3-3-11。图3-3-11 解码器部分的实现在假定输出码元在前3个时钟周期是“00,00,00”的情况下，从c2.0J2.0的8条路径的汉明距离计算的结果见图3-3-12。图 3-3-12 汉明距离从波形图中可以看出，在译码输出为“00，00，00”的情况下，8条路径中的最小汉明距离是0(000)，最大汉明距离是5(101)。汉明距离最小的路径有一条，它的状态转换过程是a-a-a-a；汉明距离最大的路径也只有一条，它的状态转换路径是a-b-c-a。最后的目标就是需要把最小汉明距离的那条路径选出并存储，并把相关信息提供给回溯模块，最终把输入的码元译出。第三部分是8位比较器74684作为比较器部分，第二部分中的加法器输出接4864，可以比较出输入数据的大小，产生信息位把汉明距离最小的那条路径存储在幸存路径存储器中。74684和其状态表见图3-3-13图3-3-13 74684从状态表中可以看出假如输入的数据P比数据Q小，输出信号P_GR_QN有高电平信号产生，此高电平信号输入到幸存路径寄存器中用于指示汉明距离小的路径。所有汉明距离小的路径在最大似然模块中