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

可编程器件实现卷积编码和译码的初步实现 0 目录目录 第一章 绪 论1 1.1 卷积码及卷积编码技术的应用.1 1.1.1 卷积码概述1 1.1.2 卷积码技术的应用2 1.2 可编程器件概述.2 1.2.1 FPGA 概述.3 1.2.2 FPGA 设计.5 1.2.3 FPGA 技术的发展趋势.5 第二章 卷积码的编码研究7 2.1 卷积编码的基本原理.7 2.2 卷积码的生成矩阵.8 2.3 卷积编码的 FPGA 实现.9 2.3.1 MAX+PLUSSII 应用简介.9 2.3.2 基于 MAX+PLUSSII 平台实现卷积码编码11 第三章 卷积码的译码研究17 3.1 卷积译码的基本方法.17 3.1.1 码树17 3.1.2 状态图18 3.1.3 网格图18 3.2 VITERBI译码算法.19 3.2.1 最大似然算法原理19 3.2.2 Viterbi 译码基本原理 .20 3.3 卷积码的 VITERBI译码 FPGA 实现22 .30 第四章 研究小结与心得体会.31 4.1 分析小结.31 4.2 收获体会.31 参 考 文 献32 上海理工大学毕业设计（论文） 1 第一章第一章 绪绪 论论 1.1 卷积码及卷积编码技术的应用 卷积码又称连环码，它是麻省理工学院的 P.Elias 于 1955 年发明的一种非分组码，它 和分组码有着明显的区别。在同等码率和相似的纠错能力下，卷积码的实现往往要比分组码 简单，但卷积码没有分组码那样严密的数学分析手段，目前大多是通过计算机进行好码的搜 索，卷积码主要应用于前向纠错 FEC 数据通信系统中。 1.1.11.1.1 卷积码概述卷积码概述 对输入的码元序列编成长度为 k 的段，每段附上 r (r = n-k ) 个监督位,此监督位仅与 本组的 k 个信息位有关，而与其他码组无关，也就是说各个码组间是没有约束关系的，即监 督码只监督本码组中的码元有没有错码，解码时也是分组进行解码，这样的码制我们称之为 分组码，n 在这里代表的是码组长度。 而卷积码不同，在任何一段规定时间内编码器产生的 n 个码元，不仅取决于这段时间中 的 k 个信息码元，而且还取决于前 N-1(m)段规定时间内的信息码元，所以监督位监督着这 N 段时间内的信息。换句话说，各个码内的监督元不仅对本子码有监督作用，而且对前面 m 个 子码内的信息元也是有监督作用的。 一般来说，卷积码的结构是：“信息元，监督元，信息元，监督元”。可以用 （n,k,m）表示卷积码，k，n 通常是比较小的整数，m 称为编码记忆（或编码存储），它反 映了输入的信息元在编码器中需要存储的时间长短；N 称为卷积码的约束度，它是相互约束 的子码的个数；N*n 称为约束长度，它表明约束的二进制码元的个数。 用下图 1-1-1 来说明卷积码编码器的一般结构: 图 1-1-1 卷积编码器结构 可编程器件实现卷积编码和译码的初步实现 2 它包括:一个由 N 段组成的输入移位寄存器，每段有 k 级，共 Nk 位寄存器;一组 n 个模 2 和加法器;一个由 n 级组成的输出移位寄存器。对应于每段 k 个比特的输入序列，输出 n 个 比特。由图可知，n 个输出比特不但与当前的 k 个输入比特有关，而且与以前的(N-1)k 个输 入比特有关。整个编码过程可以看成是输入信息序列与由移位寄存器模 2 和连接方式所决定 的另一个序列的卷积，故称为卷积码。 1.1.21.1.2 卷积码技术的应用卷积码技术的应用 在数字通信卫星中，卷积码的性能要优于分组码，因而能够得到广泛的应用，卷积码的 维特比译码在译码约束度较小，一般在 N10 的情况下计算速度快，效率高，译码器也较简 单，随着微电子技术的发展和 PLD 技术的普遍使用，在软件开发工具的帮助下，维特比译码 器由硬件来实现已成为可能。 同时在数字通信过程中，降低误码率，提高通信质量是很关键的问题，卫星通信是远距 离传送数据，需要很高的能量来降低各方面的干扰，而卫星体积是受限的，功率很难达到理 想的状况，采用卷积码维特比译码可以降低误码率，实现强大的纠错能力，突破卫星信道功 率受限的弱点，改善通信效率。 另外，卷积码在码分多址(CDMA)和数字蜂窝移动个人通信网(PCN)中也有广泛的应用。 在 PCN 中,IS95 标准1建议对信息传输的差错控制采用大约束度(K=9)卷积编码和最大似然 的 Viterbi 译码方案,而满足 IS95 标准的 Viterbi 译码器至今没有面市。研究用现场可编程 门阵列(FPGA)来实现 K=9 的差错控制器的问题是重中之重。因为,一旦用 FPGA 研制成功,就 可进行低功耗超大规模电路集成(VLSI)，制成高性能单片差错控制器，应用于 PCN；另一方 面，VLSI 方案具有高得多的处理速率，适用于更为广泛的数字通信场合。 基于 FPGA 的卷积码译码器是充分利用了 FPGA 的资源丰富的特点，设计特定的模块使的 幸存路径的选择更加快捷和有效。 1.2 可编程器件概述 可编程器件 PLD（Programable Logic Device)是 80 年代发展起来的新型器件，PLD 是 一种由用户根据自己的需要来设计逻辑功能并对此器件进行编程后实现的。 数字电路的集成电路通常是标准的小规模、中规模、大规模的器件，而这些器件的逻辑 功能是出厂时已经由厂商设计好了，用户只能根据其提供的功能及管脚进行设计其需要的电 路，由于这些通用器件考虑到其通用性，其在使用时有许多功能是多余的，并且由于管脚的 排布是固定的，在设计 PCB 时给电路的连线带来了极大不便，而 PLD 其内部具有大量组成数 字电路的最小单元门电路，而这些门电路并没有固定怎样连接，并且输入/输出脚的连 上海理工大学毕业设计（论文） 3 接可自己设置，而这些门电路的连接是通过编程的方法加以设计，故这种电路给我们带来了 极大的方便。 （1 1）提高了功能的集成度）提高了功能的集成度 PLD 器件较中小规模集成芯片具有更高的功能集成度，一般来说一片 PLD 器件可替代 420 片的中小规模集成芯片，而更大规模的 PLD（如 CPLD、FPGA)一般采用最新的集成电路 生产工艺及技术，可达到极大的规模，这些器件的出现降低了电子产品的成本和缩小了电子 产品的体积。 （2 2）加快了电子系统的设计速度）加快了电子系统的设计速度 一方面由于 PLD 器件集成度的提高，减小了电子产品设计中的布线时间及器件的安装时 间；另一方面由于 PLD 器件的设计是利用计算机进行辅助设计的，其可以通过计算机的辅助 设计软件对设计的电路进行仿真和模拟，减小了传统设计过程中的调试电路的时间，另外由 于 PLD 器件是可擦除和可编程的，故即使设计有问题修改也是很方便的。 （3 3）高的性能）高的性能 由于 PLD 器件在生产过程中采用了最新的生产工艺及技术，故通过 PLD 器件的性能优于 一般通用的器件，其速度一般比通用器件速度高一到两个数量级，另外由于器件数量的减少， 降低的电路的总功耗。 （4 4）高可靠性）高可靠性 系统的可靠性是数字系统的一项重要指标。根据可靠性理论可知器件的数量增加，系统 的可靠性将下降；反之将提高。采用了 PLD 器件可减少器件的数量，器件的减少还导致 PCB 的布线减少，同时也减少了器件之间的交叉干扰和可能产生的噪声源，使系统运行更可靠。 （5 5）成本低）成本低 由于 PLD 器件的上述优点将导致电子产品在设计、安装、调试、维修、器件品种库存等 方面的成本下降，从而使电子产品的总成本降低，提高了产品的竞争力。 1.2.11.2.1 FPGAFPGA 概述概述 FPGA 是 Field Programmable Gate Array（现场可编程门阵列）的缩写，代表的是一种 可编程逻辑器件，它可以在制造完成后由用户根据自己的需要定义其逻辑功能。FPGA 包含了 一个逻辑单元（可以是门，也可以是查找表 RAM）的阵列、触发器以及可编程的互连线。除 此之外，现在的一些大规模 FPGA 还包含了片内 RAM、嵌入式 CPU、高速收发器等资源。FPGA 的显著特点是有一个窄输入的逻辑单元，使用分布式互连方案，相对于传统的诸如 PAL 和 PLA 之类的可编程逻辑器件来说，FPGA 的设计更加灵活。 可编程器件实现卷积编码和译码的初步实现 4 FPGA 是 PAL、GAL、EPLD 等可编程器件的基础上进一步发展的产物。它是作为专用集成 电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有 可编程器件门电路数有限的缺点，是电子设计领域中最具活力和发展前途的一项技术，它的 影响丝毫不亚于 70 年代单片机的发明和使用。 FPGA 在现代数字电路设计中发挥着越来越重要的作用。从设计简单的接口电路到设计复 杂的状态机，甚至设计“System On Chip（片上系统）”，FPGA 所扮演的角色已经不容忽视。 FPGA 所具有的静态可重复编程和动态在系统重构的特性，使得硬件的功能可以像软件一样通 过编程来修改，这样就极大地提高了电子系统设计的灵活性和通用性，缩短了产品的上市时 间并降低了电子系统的开发成本。基于此，FPGA 设计技术受到了世界范围内广大电子工程师 的普遍欢迎，现已成为电子工程师必须掌握的一项基本技能之一。 FPGA 采用了逻辑单元阵列 LCA（Logic Cell Array）这样一个新概念，内部包括可配置 逻辑模块 CLB（Configurable Logic Block）、输出输入模块 IOB（Input Output Block） 和内部连线（Interconnect）三个部分。可配置逻辑模块 CLB 是实现各种逻辑功能的基本单 元，其中包括组合逻辑单元，时序逻辑，RAM 及各种运算功能。CLB 是以 n n 阵列形式分布 在 FPGA 中,同一系列中的不同 FPGA,其阵列规模也不同;输入输出模块 IOB 是芯片外部引脚数 据与内部数据进行交换的接口电路,通过编程可将 I/O 引脚设置成输入,输出和双向等不同的 功能;金属导线以纵横交错的格栅状结构分布在两个层面,有关的交叉点上连接着可编程开关 或可编程开关阵列,通过对可编程开关和可编程开关矩阵的编程实现 CLB 与 CLB 之间，CLB 与 IOB 之间,以及全局信号与 CLB 和 IOB 之间的连接。 FPGA 的基本特点主要有： 1.采用 FPGA 设计 ASIC 电路，用户不需要投片生产，就能得到合用的芯片。 2.FPGA 可做其它全定制或半定制 ASIC 电路的中试样片。 3.FPGA 内部有丰富的触发器和 IO 引脚。 4.FPGA 是 ASIC 电路设计周期最短、开发费用最低、风险最小的器件之一。 5.FPGA 采用高速 CHMOS 工艺，功耗低，可以与 CMOS、TTL 电平兼容。 可以说，FPGA 芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。 FPGA 是由存放在片内 RAM 中的程序来设置其工作状态的，因此，工作时需要对片内的 RAM 进行编程。用户可以根据不同的配置模式，采用不同的编程方式。加电时，FPGA 芯片将 EPROM 中数据读入片内编程 RAM 中，配置完成后，FPGA 进入工作状态。掉电后，FPGA 恢复成 白片，内部逻辑关系消失，因此，FPGA 能够反复使用。FPGA 的编程无须专用的 FPGA 编程器， 只须用通用的 EPROM、PROM 编程器即可。当需要修改 FPGA 功能时，只需换一片 EPROM 即可。 上海理工大学毕业设计（论文） 5 这样，同一片 FPGA，不同的编程数据，可以产生不同的电路功能。因此 FPGA 的使用非常灵 活。 FPGA 有多种配置模式：并行主模式为一片 FPGA 加一片 EPROM 的方式；主从模式可以支 持一片 PROM 编程多片 FPGA；串行模式可以采用串行 PROM 编程 FPGA；外设模式可以将 FPGA 作为微处理器的外设，由微处理器对其编程。 1.2.21.2.2 FPGAFPGA 设计设计 (1)(1)设计流程设计流程 设计输入：主要有原理图输入和 HDL 输入两种方式，一般开发软件都能够同时支持这两 种输入方式。还有的甚至提供更多的输入方式，如 Xilinx 公司的 ISE6.0 就提供四种输入方 式，包括 EDIF 网表输入。 设计仿真：包含功能仿真和时序仿真两项主要内容，功能仿真忽略了综合和布局布线导 致的时延等因素，仅仅从逻辑上进行仿真，这对设计思路的验证是有帮助的，但必须通过时 序仿真作进一步验证，发现并修正时序问题。 设计综合：将 HDL 语言生成用于布局布线的网表和相应的约束。综合效果直接导致设计 的性能和逻辑门的利用效率，因此，许多开发软件都支持第三方综合和仿真工具，著名的有： Synplicity、Synopsys 和 ModelSim 等。 布局布线：工具利用综合生成的网表，在 FPGA 内部进行布局布线，并生成可用于配置 的比特流文件（有了比特流文件就下载到板子里了)。布局布线工具与可编程逻辑器件工艺 及其布线资源密切相关，一般由可编程逻辑器件开发商直接提供。 (2)FPGA(2)FPGA 设计时注意的问题设计时注意的问题 本人在使用 Altera 公司开发的 MAX+PLUS II 软件进行电路图输入的设计过程中,体会到 有些问题是初学 FPGA 设计的同学要注意的: 1.异步逻辑主要用组合逻辑来实现控制,容易因时钟传递延时不一致而产生毛刺,建议尽 量改成同步逻辑,当输出信号用于 RESET,CLEAR,PRESET 时最好改成同步。 2.组合逻辑容易设计，但要注意处理好毛刺，最好分析出毛刺产生的原因，然后重新设 计新的电路。 3.选择模块可以节省设计时间，但不是必须所有的过程都使用。 1.2.31.2.3 FPGAFPGA 技术的发展趋势技术的发展趋势 随着微电子技术、EDA 技术、以及应用系统需求的发展，FPGA 正在逐渐成为数字系统开 发的平台，并朝着以下方面发展和提高： 1.高集成度、大容量、低成本、低电压、低功耗； 可编程器件实现卷积编码和译码的初步实现 6 2.资源多样化； 3.适用于片上系统：处理器、高速串行 I/O DSP 等等； 4.深亚微米工艺的使用，基于 90nm 工艺的 FPGA 已经商用，正在向 65nm 挺进； 5.各种软硬 IP 库的发展和完善； 6.动态可重构技术实用化； 新 FPGA 器件在复杂设计、增加总的逻辑资源、改进布线与软件以及在系统中对器件进 行编程的能力方面正在仿照 ASIC。深亚微米技术使可编程器件的逻辑单元更小。 另一个明显的发展趋势是一些产品采用部分存储器结构作为专用存储器而不仅作为逻辑 切换驱动器。此外，可编程密度已在传统上限制了性能和密度。这促使一些厂商考虑将 ASIC 和 FPGA 技术混合，以生产出能按用户编程定制的高性能、高密度的混合功能器件。 同时 FPGA 工具组也在升级,这种从逻辑级向以语言为基础的设计变迁，意味着综合技术 利用的增加。从这一点看，FPGA 工具与设计流程的通用性越多，从可编程器件向硬件连线 ASIC 转移就越容易。 FPGA 的发明和在全球范围内的广泛使用是电子设计领域的一场革命，目前正处于高速发 展阶段。每年都有高集成度的新产品投入市场，同时也有支持它们的强大的 EDA 工具的问世。 FPGA 不但使电子系统的性能得到了增强，更重要的是它使电子系统的设计发生了根本性变革， 使得一切设计仿真测试工作能够在个人电脑和开发平台(EDA 工具)的支持下通过模拟仿真的 形式通过。 FPGA 作为一个比较新的领域，在最近几年中有很大的发展和进步。各个厂家的 FPGA 不 断推陈出新，工艺越来越高、速度越来越快、功能越来越多，价格却越来越便宜。各种依靠 FPGA 技术设计的芯片已在信号纠错,总线接口,高速数据采集,通信领域编解码,嵌入式系统, 数字图象处理,数字信号处理得到了广泛的应用。 随着 FPGA 成本的进一步降低和规模的增加，在未来几年中 FPGA 应该有更加宽广的应用 领域。 上海理工大学毕业设计（论文） 7 第二章第二章 卷积码的编码研究卷积码的编码研究 2.1 卷积编码的基本原理 以下图 2-1-1 的（2，1，2）卷积编码器为例来分析卷积码的编码原理和编码方法。 （2，1，2）卷积编码器是由 2 个移位寄存器，2 个模 2 加法器和开关电路组成。在编码 前，对每一级的移位寄存器进行清零，每输入一个信息码元，将会输出 C1,C2各一次，即 1 比特的信息输入将有 2 比特的信息输出。其中输入与输出之间的编码关系可用下面的式子表 示出来： C1=S1S2S3 C2=S1S3 S1是当前的输入的信息位，S2, S3是移位存储器前两个信息位。输出信息的顺序是信息 位在前，监督位在后，即输出的码元以“信息位,监督位,信息位,监督位,监督位,信息位,监 督位， , 信息位,监督位,监督位”的形式表示。 本人在初始编码时，每一级的移位寄存器的状态全部清零，输入 1101000 此时编码器输 出状态如下表 2-1-1 表示： 图 2-1-1 原理框图 可编程器件实现卷积编码和译码的初步实现 8 经过(2,1,2)卷积编码器的编码后输出的信号码元将会是 “11，01，01，00，10，11，00” 2.2 卷积码的生成矩阵 卷积码是线性码，因此它完全可以由生成矩阵和校验矩阵来确定。以比较简单的 （2，1，2）卷积码编码器为例阐述生成矩阵的规律,见图 2-2-4。 输出码元可以用下面的表达式来表示： Cj1 = mjmj-1 mj-2 Cj2 = mjmj-2 输入信息位是(m0,m1,m2,mj)，输出位 C0,C1,C2,C3,C4可以用下面形式表示出 来 C C0 0： ： C01=m0 C C1:1: C11=m0 m1 C C2:2: C21 =m0 m1m2 C02=m0 C12 =m1 C22 =m0m2 输入(S1) 1101000 S20111000 S30010110 c11000110 c21110010 表 2-1-1 输入输出状态列表 mj mj- 1 mj-2 图 2-2-4 生成矩阵 上海理工大学毕业设计（论文） 9 C C3: 3: C31=m1 m2m3 C C4: 4: C41=m2 m3m4 C32=m1m3 C42=m2m4 输出码元(C01,C02,C11,C12,C21, C22,C31,C32,C41,C42, ) 用矩阵形式表示： C01,C02,C11,C12,C21,C22,C31,C32,C41,C42, =m0,m1,m2,m3,m4, 由卷积码生成矩阵定义可得(2,1,2)卷积码的生成矩阵是： 1110110000 0011101100 0000111011 0000001110 从生成矩阵可以找出以下规律： 1.第二行是由第一行右移 2 位（一个子码的长度）得到，第三行是由第二行右移 2 位得 到，依次类推。 2.除第一行前 6 个数字外，以后的数字全部是0，这前 6 个数字组成基本生成矩阵， 如果基本生成矩阵给定的话，就有可能得到整个编码序列。 2.3 卷积编码的 FPGA 实现 2.3.12.3.1 MAX+PLUSSIIMAX+PLUSSII 应用简介应用简介 (1)MAX+PLUSSII(1)MAX+PLUSSII 概述概述 Max+plus是 Altera 公司提供的 FPGA/CPLD 开发集成环境，Altera 是世界上最大可编 程逻辑器件的供应商之一。Max+plus界面友好，使用便捷，被誉为业界最易用易学的 EDA 软件。在 Max+plus上可以完成设计输入、元件适配、时序仿真和功能仿真、编程下载整个 流程，它提供了一种与结构无关的设计环境，是设计者能方便地进行设计输入、快速处理和 器件编程。 Max+plus开发系统的特点 开放的界面 1110110000. 0011101100 0000111011 0000001110 可编程器件实现卷积编码和译码的初步实现 10 Max+plus支持与 Cadence，Exemplarlogic，Mentor Graphics，Synplicty，Viewlogic 和其它公司所提供的 EDA 工具接口。 与结构无关 Max+plus系统的核心 Complier 支持 Altera 公司的 FLEX10K、FLEX8000、FLEX6000、MAX9000、MAX7000、MAX5000 和 Classic 可编程逻辑器件， 提供了世界上唯一真正与结构无关的可编程逻辑设计环境。 完全集成化 Max+plus的设计输入、处理与较验功能全部集成在统一的开发环境下，这样可以加快 动态调试、缩短开发周期。 丰富的设计库 Max+plus提供丰富的库单元供设计者调用，其中包括 74 系列的全部器件和多种特殊 的逻辑功能（Macro-Function）以及新型的参数化的兆功能（Mage-Function）。 模块化工具 设计人员可以从各种设计输入、处理和较验选项中进行选择从而使设计环境用户化。 硬件描述语言（HDL） Max+plus软件支持各种 HDL 设计输入选项，包括 VHDL、Verilog HDL 和 Altera 自己 的硬件描述语言 AHDL。 Opencore 特征 Max+plus软件具有开放核的特点，允许设计人员添加自己认为有价值的宏函数。 （2 2）设计流程：）设计流程： 使用 Max+plus软件设计流程由以下几部分组成。如图 2-3-1 所示。 1、设计输入：可以采用原理图输入、HDL 语言描述、EDIF 网表输入及波形输入等几种 方式。 2、编译： 先根据设计要求设定编译参数和编译策略，件的如器选择、逻辑综合方式的选择等。然 后根据设定的参数和策略对设计项目进行网表提取、逻辑综合和器件适配，并产生报告文件、 延时信息文件及编程文件，供分析仿真和编程使用。 3、仿真：仿真包括功能仿真、时序仿真和定时分析，可以利用软件的仿真功能来验证 设计项目的逻辑功能是否正确。 4、编程与验证：用经过仿真确认后的编程文件通过编程器（Programmer）将设计下载 到实际芯片中，最后测试芯片在系统中的实际运行性能。 上海理工大学毕业设计（论文） 11 在设计过程中，如果出现错误，则需重新回到设计输入阶段，改正错误或调整电路后重 复上述过程。 图 2-3-2 是 Max+plus编译设计主控界面，它显示了 Max+plus自动设计的各主要处 理环节和设计流程，包括设计输入编辑、编译网表提取、数据库建立、逻辑综合、逻辑分割、 适配、延时网表提取、编程文件汇编（装配）以及编程下载 9 个步骤。 图 2-3-2 编译主控界面 图 2-3-1 开发流程 可编程器件实现卷积编码和译码的初步实现 12 2.3.22.3.2 基于基于 MAX+PLUSSIIMAX+PLUSSII 平台实现卷积码编码平台实现卷积码编码 仍以（2，1，2）卷积码编码器为例来描述卷积码编码译码的 FPGA 实现。整个 FPGA 的 电路搭建和仿真模拟都是在 MAX+PLUSSII 的平台上来完成的。 （2，1，2）的卷积编码译码器实现起来较为简单和方便，同时它的应用也很广泛，在 查阅了很多的相关资料后发现（2，1，2）卷积码编码译码器在水下无线通信传输系统和卫 星通信领领域应用最为普遍。 （1 1） 编码器的编码器的 FPGAFPGA 实现过程分析实现过程分析 （2，1，2）卷积编码器是在一个码元输入后将会有两个码元输出，我们根据上面提到 的编码表示方法中的状态图可以把卷积码的编码器看作是一个简单的状态机。假设某个时刻 编码器的状态为 10，即状态 c,在输入端，如果输入的信息序列是 0，则下一时刻编码器的状 态是 a,对应的输出为 11；如果输入信息序列为 1，则下一时刻编码器状态为 b,对应的输出 为 00。根据各个状态之间的关系可以得出状态转移图，用寄存器保存对应的状态。 我们也可以根据输入与输出之间的简单模 2 加的关系来实现编码过程，这里提到的状态 机是对于输入输出较为复杂的情况时效率要高，本人采用的是根据输入输出之间的关系的方 法来实现编码的。 每位信息码元送入编码模块后，编码模块立即进行编码，编码结束后保存新的状态变量， 同时得到并行输出的码元，（2，1，2）卷积编码器的编码效率 R=1/2,表明如果仅仅用一个 时钟的话，编码的输入和输出不能同步起来，在设计的过程中，加上一个分频模块，达到编 码器的输出控制时钟是输入控制时钟频率的 2 倍的效果。考虑到现在得到的是并行输出的数 据，需要加入一个并串转换模块来保证码元串行输出，这个模块可以用移位寄存器来实现， 也可以根据具体的卷积码来选择合适的电路实现并串转换功能。 （2 2） 编码器的原理图编码器的原理图 一般卷积编码器原理框图见图 2-3-3 串 并 转 换 模 块 编 码 模 块 并 串 转 换 模 块 上海理工大学毕业设计（论文） 13 卷积码编码器主要由移位寄存器构成，输入数据经串并变换器后形成 k bit 一帧的并行 数据送到编码模块中去，这里的编码模块是线性逻辑单元和移位寄存器，每读入一个新的数 据帧，旧的数据帧就向右移一帧，编码模块根据当前输入的数据帧和存放在数据帧寄存器中 以前消息数据进行线性逻辑运算后得到 n （bit）的编码输出，再经过并串模块转换成串行 输出的数据。 串并转换模块是把串行输入的数据转换成并行输出的数据输入到编码模块中，由于我设 计的是（2，1，2）卷积编码器，这里 k=1，因此这一个串并转换的模块在整个编码器中就不 需要考虑，信息码元可以直接输入到编码模块中去。 编码模块是由 D 触发器组成的移位寄存器和异或门组成，D 触发器在上升沿到来时是有 效的，其他输入端的信息详见状态表 2-3-1 表 2-3-1 （Qo*： level of Q before Clock pulse） InputsOutput CLRNPRNENADCLKQ LHXXXL HLXXXH LLXXXIllegal HHLXXQo* HHHLL HHHHH HHXXLQo* 编码模块在 Max+plus中电路图见图 2-3-4 图 2-3-3 编码器原理框图 可编程器件实现卷积编码和译码的初步实现 14 图 2-3-4 编码模块 编码后的波形图见下图 2-3-5 图 2-3-5 编码后的波形图 从仿真的波形图上我们可以看出，当输入的信息是1101000时，得到的输出信号 C1 是1000110，输出信号 C2 是1110010。 由于这里的（2，1，2）卷积编码器的输出是两个码元，所以选择了 2 位数据选择器来 把输入到并串转换模块的信息码元以串行的形式把数据输出，这样在信息码元一个时钟周期 上海理工大学毕业设计（论文） 15 内将会有 C1，C2 两个码元数据输出，其中前半个时钟周期输出 C1，后半个时钟周期输出 C2，OUT 端输出的就是串行数据。 并串转换模块在 Max+plus中电路见图 2-3-6。 编码模块和并串转换模块连在一起的电路见图 2-3-7 图 2-3-6 并串转换模块 图 2-3-7 编码器 可编程器件实现卷积编码和译码的初步实现 16 输出码元的仿真波形图 2-3-8 见输出端 OUT，我们明显可以看到在一个时钟周期内有两 个码元输出，最后的输出结果是“11，01，01，00，10，11，00” 图 2-3-8 仿真波形图 上海理工大学毕业设计（论文） 17 第三章 卷积码的译码研究 3.1 卷积译码的基本方法 卷积译码分为代数译码和概率译码。 代数译码是根据卷积码的本身代数结构进行译码，译码时不考虑信道的统计特性，该方 法的硬件实现简单，但性能较差，主要方法是大树逻辑译码（门限译码）；概率译码在计算 时不仅利用了卷积码的代数结构，而且还要考虑信道的统计特性，这种译码是建立在最大似 然准则的基础上，提高了译码性能，但增加了硬件实现的复杂度，常用的译码方法有 Viterbi 和序列译码。 3.1.13.1.1 码树码树 码树描述的是在数据序列输入时，码字所有可能的输出对应于(2，1，2)卷积编码器， 码树图可用下图 2-2-1 来表示，在图中每一个节点对应于一个输入码元，当输入是0时， 走上分支；输入是1时，走下分支，编码器的输出码元 C1,C2标在每个分支的上面。图中 的 a,b,c,d 表示 S3,S2的状态，状态的编码规则如表 3-1-1： 00 11 a 10 01 b 11 00 c 01 10 d 00 11 a 10 01 b 11 00 c 01 10 d a b c d a b c d a b c d a b c d 00 11 10 01 11 00 01 10 00 11 10 01 11 a b c d a b a 0 1 00 11 a 图 3-1-1（2，1，2）卷积编码器码树图 （2，1，2）卷积码的码树图 状态S3,S2 a00 b01 c10 d11 表 3-1-1 状态编码规则 可编程器件实现卷积编码和译码的初步实现 18 a c b d 00 11 10 01 11 01 10 00 从码树图上可以看出：从第四条支路开始，码树的各节点从上面开始重复出现 a,b,c,d 四种状态，并且码树的上半部分和下半部分是完全相同的，这就是表明从第 4 位输入码元开 始，无论输入的第一位信息码元是0或1，编码输出是没有影响的，输出码元已和输 入的码元已经没有关系了，定义约束度 N=3 的含义也就在于此。 3.1.23.1.2 状态图状态图 卷积码的状态图给出的是编码器当前状态和下一个状态之间的关系，如下图 3-1-2 所示 (虚线表示输入码元是1的路径，实线表示输入码元是0的路径，圈内的字母表示此 时的编码器状态，路径上的数字是输出的码元) 3.1.33.1.3 网格图网格图 在码树图中，从同一个节点出发的分支都相同，可以把状态相同的节点合并在一起得到 更加紧凑的表示方法，这个图示的作用在卷积码的译码过程中可以得到充分的体现（图中每 一个节点表示的是 a,b,c,d 四种状态，对应于输入码元是0的情况，用实线表示；对 应于输入码元是1的情况，用虚线表示）见图 3-1-3 00 11 10 01 01 11 00 10 a b c d a b c d 图 3-1-2 （2，1，2）卷积编码器状态图 上海理工大学毕业设计（论文） 19 图 3-2-1 卷积编码译码的系统模型 图 2-4 网格图 Viterbi 译码在卷积码的约束长度较小时，比序列译码的方法效率更高，速度更快，译 码器的设计也较简单，目前已经广泛应用于各种数字通信系统中。 3.2 Viterbi 译码算法 Viterbi 译码是一种最大似然算法，最大似然算法的基本思路是,把接受码字与所有可能 的码字比较，选择码距最小的码字作为解码输出。Viterbi 译码同时也是在最大似然算法的 基础上对其进行了简化，它把接受码字分段累计处理，每接受一段码字，需要计算，比较一 次，保留码距小的路径，直到译码完所有的序列。 3.2.13.2.1 最大似然算法原理最大似然算法原理 下图 3-2-1 是一个卷积编码译码的系统模型，信息码元 M 经过卷积码编码器后成为发送 序列 C,发送序列 C 经过 DMC（离散无记忆信道）,在接受端，译码器接受经 DMC 后的序列 R, 译码输出序列 M 卷积码 编码器 卷积码 译码器 信息码元 M 离散无记 忆信道 发送序列 C 接受序列 R 译码序列 M 图 3-2-1 系统模型 00 00 00 00 00 11 11 11 11 11 10 01 10 10 01 00 00 10 10 10 01 01 01 01 10 11 00 11 10 11 a b c d 00 11 10 01 10 01 00 11 图 3-1-3 网格图 可编程器件实现卷积编码和译码的初步实现 20 输入码元序列为 C，输出为 R 的概率为：P(R/C)= 1 0 /) L m i P Ri Ci （ 1 0 (/) n i p ri ci 对上面的式子取对数得到：log P(R/C)= = 1 0 log(/) L m i p Ri Ci 1 0 log(/) n i p ri ci 是信道的转移概率，log P(R/C)是 C 序列的似然概率，由贝叶斯公式，(/)p ri ci log P(R/C)= 取对数后得到：log P(R/C)=logP(R)+logP(C/R)-logP(C) ( ) (/) ( ) P R P C R P C 式子中，P(R)是接受序列 R 的概率，P(C/R)是 C 的后验概率，P(C)是发送序列为 C 的概 率，在发送序列为等概率的情况下，最大似然译码就等于最大后验概率译码。 在二进制对称信道下，最大似然译码就是最小汉明距离译码，也就等于最大后验概率译 码。 3.2.23.2.2 ViterbiViterbi 译码基本原理译码基本原理 译码器接受到 R 序列后，按照最大似然法则寻找编码器在网格图上走过的路径，也就是 寻找最大度量的路径，对于二进制对称信道，就是寻找与 R 由最小汉明距离的路径。 最大似然译码只是一种译码准则，实现起来有一定困难，因为译码器每接受一个序列 R 就要计算很多的似然函数才可以做出译码判决，维特比针对这个实现的困难提出了一种算法， 后来称为维特比算法。维特比算法的基本思想是接受一段信息码元后就进行计算和比较，在 每个状态时选择最可能进入该状态的分支，这样可以留下与 R 距离最小的路径（幸存路径）， 而去掉其它可能的路径，同时把幸存路径按逐分支地存储起来，幸存路径的数目等于状态数。 归纳维特比算法的基本步骤如下： （1）在第 j（jm）时刻以前，译码器计算所有的长为 m 个分支的部分路径值，对进入 2km个状态的每一条路径进行保留； （2）第 m 个时刻开始，对进入每一个状态的部分路径值进行计算，这样的路径有 2k条， 挑选具有最大部分路径值的部分路径为留选路径，删除进入该状态的其它路径，然后，留选 路径向前前延长一个分支； （3）重复第（2）部的计算，比较和判决过程； （4）如果进入某个状态的部分路径中有两条相同的部分路径值，则可以选择其中一条 作为幸存路径。 本人仍以（2，1，2）码为例说明整个译码的基本思想： 设发送序列为全零序列，而接受序列为 R=01,00,00,10,00,00,假设译码器的初始 状态全为零，在第 0 个时刻时，接受序列的第 0 个分支 R001 进入译码器，从网格图可以看 上海理工大学毕业设计（论文） 21 出从 a 状态有 2 个分支，它们是 00 和 11，R0和这两个分支进行比较，比较的结果和到达的 状态如下表 3-2-1。 表 3-2-1 幸存路径第 0 个分支的 距离 第 1 个分支的 距离 001S0 111S1 第 1 个时刻态进入译码器的接受码组 R1=00 将和此时刻出发的四条分支进行比较，比较 结果和到达的状态如下表 3-2-2。 表 3-2-2 上次距离留选路径延长分支本分支距 离 累加距离到达状态 1000001a 1123b 1111012c 0112d 第 1 个时刻到第 2 个时刻共有 4 条路径，到达状态 a,b,c,d。在第二个状态以前译码器 不做任何的选择和判决，路径选择存储器存储此刻的留选路径：0000，0011，1110，1101， 并且路径存储器存储此时刻到达该状态的幸存路径累加值。 从第 2 个时刻起，第 2 个接受码组 R2=00 进入译码器，从网格图上看出，从第 2 个时刻 到第 3 个时刻，进入每个状态的分支有两个，译码器将接受码组 R2与进入每个状态的两个分 支进行比较和判决，选择一个累加距离最小的路径作为进入该状态的留选路径，比较和判决 的过程见表 3-2-3 。 表 3-2-3 上次距离留选路径延长分支本分支距离累加距离到达状态 100000001a 1123b 300111014c 0114d 211101124a 可编程器件实现卷积编码和译码的初步实现 22 0002b 211010113c 1013d 上面介绍的是以最小汉明距离为度量的译码器是硬判决译码器，适合于二进制对称信道， 在实际应用的过程中为了提高译码的可靠性，充分利用信道输出信号的有关信息，把输出的 信号进行 Q 电平的量化，然后再输到维特比译码器里进行译码，这样的译码器是软判决译码 器，适合于离散无记忆信道。软判决维特比译码算法和硬判决维特比译码算法的译码过程很 相似，唯一的差别是软判决不应用汉明距离，它使用的是欧氏距离。 维特比译码算法解码简单,计算快,已经得到了广泛应用,特别是在卫星通信和蜂窝网通 信系统中的应用。 3.3 卷积码的 Viterbi 译码 FPGA 实现 在 Viterbi 译码算法的 FPGA 实现设计中，译码器有 6 个模块组成，它们分别是支路度 量模块，加法比较选择模块，最大似然判决模块，回溯模块，路径度量存储器，幸存路径存 储器。其中加法比较选择模块是译玛器中的关键环节，它的设计好坏在一定程度上决定了卷 积码译码器的复杂程度和工作效率的高低。同时法比较选择是运算最多的环节，度量的保存 和路径的保存都会用到很大的 RAM 空间，需要选择合适的 FPGA 来完成。 Viterbi 译码 FPGA 实现的总体框图见图 3-3-1。 上海理工大学毕业设计（论文） 23 支路度量模块：对于每一时刻的输入码元，为每一个状态生成相应的支路度量，也就是 说它用于产生接受序列与状态转移分支上的编码输出数据之间的距离。由于分支度量运算过 程中没有平方运算，可以将状态转移分支上的编码输出数据（比特度量值）存储在查找表内， 这样只需要进行加减和查找表运算，可以降低计算的复杂度，软判决在 FPGA 中一般可以用 查找表来实现。在硬判决支路度量模块中，度量值的计算只需要一个判决门限，即对输出进 行判决。 加法比较选择模块：根据 Viterbi 译码算法原理，将支路度量和前一个时刻存储的路径 度量相加比较，得到这一时刻的路径度量和相应的判决。对于（2，1，2）卷积码来说有 4 个状态，也就是每一次转换中需要计算多个路径度量值，需要 4 个加法比较选择模块，每个 一个加法比较选择模块由 2 个加法器，1 个比较器和 1 个选择器组成，这样由 8 个加法器， 4 个比较器和 4 个选择器可以完成一次状态的转换。同时加法比较选择模块决定着译码速度， 并行性越好，译码速度就越高。 图 3-3-2 表示一个加法比较选择模块。 图 3-3-3 表示加法比较选择模块内部的加法器，比较器，选择器与路径度量存储器，幸 存路径存储器之间的具体连接示意图。 可编程器件实现卷积编码和译码的初步实现 24 最大似然模块：在所有状态的路径度量中找出最大值，具有最大路径度量的幸存路径便 是最大似然路径，在某一时刻，最大似然模块判决最大似然路径，将其末端节点状态送入回 溯模块存储起来。 回溯模块：回溯模块也是译码器中的一个关键模块，它结合最大似然模块挑出最大似然 路径。在控制信号的控制下根据地址信息到幸存路径寄存器中提取比特信息，在找出最大似 然路径的时候产生一个最小状态信号，最小状态信号和提取出的最小路径信号比特进行逻辑 组合后最后产生译码输出。 路径度量存储器：用于存储每一状态的路径度量值，取出的结果与前一个时刻的路径度 量值在加法比较选择模块中的加法器完成相加功能。 幸存路径存储器：设计完成幸存路径的选择，交换，存储等功能，在 FPGA 中用特定的 RAM 来作为存储器。 接口电路 1：连接加法比较选择模块与路径度量存储器之间的模块。 接口电路 2：连接最大似然模块与幸存路径存储器之间的模块。 本人重点以加法比较选择模块和最大似然模块为基础来阐述 Viterbi 译码算法的基本思 想。由于总体电路图比较复杂，分成 3 部分来描述： 第一部分（见图 3-3-4）是每一时刻每一状态的比较部分，通过模 2 加运算相同比特为 0，不同比特为 1 的原则，如果产生一个高电平，则完成一次计数，全部计数完成后得到这 一时刻每一个状态的汉明距离。在第一部分电路图中的 3add 表示的是 3 位同步加计数器， 它是由 3 个 JK 触发器组成（内部电路见图 3-3-5） 图 3-3-4 前 3 时刻状态的比较 上海理工大学毕业设计（论文） 25 第一部分可以看作是计算路径度量值的模块，相当于支路度量模块，这里计算出的是每 一个时刻每一个状态的汉明距离。本人以输出码元是“00，00，00”为例来描述这一部分的 功能。a 状态到达 b 状态这一状态转换的输出码元序列是“11”,与输出码元“00”比较后计 数器的输出应该是 2，即汉明距离是 2。验证的波形见图 3-3-6。 从波形图里可以看出计数器从 000 到 001 再到 010，表明计数器计数的结果是 2，意味 着汉明距离是 2。 第二部分是加法器部分，由于只考虑了 3 个时刻汉明距离的累加，累加和最大是 6，因 此选择多个 3 位加法器即可实现（一个 3 位的加法器见图 3-3-7） 图 3-3-7 3 位加法器 图 3-3-5 3 位同步加计数器 图 3-3-6 波形验证 可编程器件实现卷积编码和译码的初步实现 26 其中 hadd 是半加法器（图 3-3-8），fadd 是全加法器（图 3-3-9） 第二部分的完整电路图见图 3-3-10，它由 12 个 3 位加法器加法器组成，完成的输入码 元进入译码器后前 3 个时刻 8 条路径汉明距离的累加。 图 3-3-8 半加器图 3-3-9 全加器 图 3-3-10 汉明距离的累加 上海理工大学毕业设计（论文） 27 第一部分和第二部分电路图完成 8 条路径汉明距离的计算，两部分和在一起的电路图见 3-3-11。 图 3-3-11 解码器部分的实现 可编程器件实现卷积编码和译码的初步实现 28 在假定输出码元在前 3 个时钟周期是“00,00,00”的情况下，从 c20J20 的 8 条路径的汉明距离计算的结果见图 3-3-12。 从波形图中可以看出，在译码输出为“00，00，00”的情况下，8 条路径中的最小汉明 距离是 0(000)，最大汉明距离是 5(101)。汉明距离最小的路径有一条，它的状态转换过程 是 a-a-a-a；汉明距离最大的路径也只有一条，它的状态转换路径是 a-b-c-a。 最后的目标就是需要把最小汉明距离的那条路径选出并存储，并把相关信息提供给回溯 模块，最终把输入的