当前位置: 首页 > >

Viterbi译码算法的研究与实现

发布时间:

国防科学技术大学 硕士学位论文 Viterbi译码算法的研究与实现 姓名:张普珩 申请学位级别:硕士 专业:计算机科学与技术 指导教师:李宗伯 20081101

国防科技大学研究生院硕十学位论文





本文在研究分析前人工作的基础上,对Viterbi译码算法的若干实现技术进行 了优化处理,提出了一种用寄存器交换法实现Viterbi译码的完整方案。首先借助
Matlab 7.0软件搭建完整测试系统,包括编译码、调*獾饕约靶藕旁谛诺乐械拇

输过程。根据Matlab生成的性能曲线又对软判决位数、交织深度和度量值计算方 式等参数的变化对译码性能的影响进行了研究。用Verilog硬件描述语言具体实现 了编译码过程,确定了译码器主要模块的体系结构,分析和均衡了面积与误码率 相互制约的矛盾。软判决位数、交织深度等参数均为编译前可配置。采用了一系 列方法如截短法、用等效的思想简化启动过程、加比选计算并行化等,进一步改 进了Viterbi译码算法的性能。在用ModelSim 6.0进行波形仿真时,要有数万译码 数据输出到文件,人工几乎不可能完成其与原始数据文件的比较以获知其译码正 确性,于是利用MFC编写了直观具有图形界面的误码率统计程序。之后又利用
Xilinx ISE9.1 i软件基于Virtex5芯片进行综合,最大输出频率可达*200Mbps。将 IP

Core下载到HAPS.54开发板中,并在真实系统中进行了BER性能测试,发现 为了使我们的研究具有更强的实用性,仿照DVB.S系统,我们将卷积编码作

自研IP Core,在信噪比高于5.0时优于Altera公司的同类产品和CDM.600。 为内码与RS编码进行级联,又融进了块交织技术,确定了交织矩阵和交织方案,
这样就进一步提高了编译码的性能和抗突发错误的能力。

主题词:无线通信,卷积编码,维特比译码,寄存器交换法,可配置

第i页

国防科技人学研究生院硕十学位论文

ABSTRACT
Based
on

the analysis of the previous research work,we proposed

one

way to fully

realize the Viterbi decoder with the method of register

improvements in details.At first,with the help of the

exchange and we made some software Matlab 7.0,we built a

complete testament system,including coding&decoding,modulming&de—modulming, and the process of transmission in channel with noise.Furthermore,by software simulmion we also did some comparisons and analysis
and computing methods
on on

soft—decision bits,delay depth

metrics.We

then realized it in Verilog HDL,identified the

main architecture of the decoder,and balanced the contradiction between the synthesis
area

and bit

error

rate.Some parameters,such

as

soft.decision bits and the delay depth
to further

are adjustable before compiling.A series of methods
decoding

enhance

the Viterbi

performance

are adopted,such as path-cured,equivalent startup process and
it with

parallelized ACS

computing.We simulated

ModelSim

6.0.In this procedure,

since tens of thousands of decoded data will be exported into text files,it iS impossible
to

compare and know if the data were right.Therefore,we made



more intuitionistic
on

program with MFC.With the software Xilinx ISE9.1 i,we then synthesized the code
Virtex 5 environment.the

equipment named XC5VLX330.Results show that the data speed iS close
the BER tests

maximal frequency of the
it into HAPS.54

output

board.and made

200Mbps.Then we downloaded in the actual system.It comes to the
to

conclusion that the IPCore of our own surpasses that of Altera and SNR is higher

CMD一600,when

the

than

5.0.

To be more practical,following the DVB—S System,we cascaded the convolution code as inner code with RS code.At the technology in
our

same time,we adopted

the block—interweaving and

design and ascertained the

interweaving Matrix

design

blue print.

On these improvements,the ability of decoding

and anti-bursting—error

ability Was

further

enhanced.

Key

Words:Wireless

communication,Convolution

code,Viterbi decoding,

Register exchange,Configurable

第ii页

国防科技大学研究生院硕十学位论文







表3.1 Viterbi反凿孔模块输入输出引脚…………………………………………….22

表3.2标准码率Viterbi译码模块输入输出引脚……………………………………22 表3.3状态转移与分支度量值输出列表……………………………………………28 表3.4三种软比特定义对照表……………………………………………………….29 表4.1延迟深度为36时硬件资源占用列表………………………………………..43 表4.2延迟深度为54时硬件资源占用列表………………………………………..43
表4.3延迟深度为36时综合后的速率结果………………………………………..43

表4.4延迟深度为54时综合后的速率结果………………………………………..44 表4.5三个IPCore译码性能对照表…………………………………………………45

第1V页

围防科技大学研究生院硕一卜学位论文


图1.1





本文整体结构框图…………………………………………………………….5

图2.1卷积编码的状态流图…………………………………………………………7 图2.2卷积编码的树状图……………………………………………………………8 图2.3卷积编码网格图表示法………………………………………………………8
图2.4 Viterbi算法流程图……………………………………………………………11

图2.5软判决区间量化图…………………………………………………………一14
图2.6

Matlab译码算法流程总图…………………………………………………..1 5

图2.7加比选(ACS)单元流程图…………………………………………………….1 7

图2.8软硬判决性能比较…………………………………………………………..1 8 图2.9多种情况模拟比较图………………………………………………………..19
图3.1

整体输入输出引脚…………………………………………………………..21

图3.2模块内部连线图……………………………………………………………一21 图3.3文件包含调用关系树图………………………………………………………23 图3.4凿孔恢复模块总示意图………………………………………………………24
图3.5 rCurrentState状态转移图……………………………………………………25

图3.6使能表中步进步数状态机变化流程图……………………………………..25
图3.7

Viterbi译码模块框图………………………………………………………..27

图3.8加比选单元具体电路设计框图……………………………………………。30 图3.9蝶形单元示意图……………………………………………………………..3 1 图3.10截短法实现示意图………………………………………………………….33
图3.1


误码率模块内部模块示意图………………………………………………34
ModelSim仿真波形图……………………………………………………..34

图3.12

图3.13仿真模拟时序图……………………………………………………………35 图3.14误码率统计比较程序界面…………………………………………………36 图3.15卷积编码(2,1,7)硬件实现框架图…………………………………………一37
图3.16(2,1,7)卷积编码模块引脚框图…………………………………………….37

图3.17编码部分仿真波形图………………………………………………………38
图4.1 图4.2 图4.3 图4.4 FPGA设计流程图【3l】………………………………………………………~39

HAPS.54开发板母板实物图及其接口简介t34】…………………………….42
真实系统测试框图…………………………………………………………一44

HAPS.54模拟ChipScope软件截图(起始时)………………………………44
第V页

同防科技大学研究乍院硕十学位论文

图5.1 图5.2 图5.3

级联码没计整体测试框图…………………………………………………..47 R=l/2时三种纠错编码误码率比较图………………………………………47

R=3/4时三种纠错编码误码率比较图………………………………………48

图5.4块交织示意图………………………………………………………………..49

图5.5块交织帧组成方案模块图…………………………………………………..49

第VI页

独创性声明

本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已 经发表和撰写过的研究成果,也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。
学位论文题目:

!i!曼!曼i逢塑篡洼鲍盟塞生塞理

学位论文作者签名:墨埴堑

日期:娜多年/≯月J7日

学位论文版权使用授权书

本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档,允 许论文被查阅和借阅;可以将学位论文的全部或部分内容编入有关数据库进行检索, 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 (保密学位论文在解密后适用本授权书。)

学位论文作者签名: 作者指导教师签名:

主量圭煎
坌鏖鱼

日期:弘啊宕年J≯月/7日
日期:

如。g年,z月’7日

国防科技大学研究生院硕十学位论文

第一章

绪论

1.1课题背景
纠错编码己有五十几年历史,早在1948年,香农(Shannon)在他的开创性论文 “通信的数学理论”中,首次阐明了在有扰信道中实现可靠通信的方法,提出了 著名的有扰信道编码定理,奠定了纠错码的基石【1J。以后,纠错码受到了越来越多
的通信和数学工作者,特别是数学家的重视,使纠错码无论在理论上还是在实际 中都得到了飞速发展。

随着现代通信的发展,特别是在未来4G通信网络中,高速信息传输和高可靠 性传输成为信息传输的两个主要方面,而可靠性尤其重要。因为信道状况的恶劣, 信号不可避免会受到干扰而出错。为实现可靠性通信,主要有两种途径:一种是 增加发送信号的功率,提高接收端的信号噪声比;另一种是采用编码的方法对信 道差错进行控制。前者常常受条件限制,不是所有情况都能采用。例如卫星通信 系统以很远的距离传送数据,由于衰落、噪声和干扰等的影响,信号在传输过程 中将产生严重的畸变。如果要求信号具有尽可能大的能量,卫星体积和载重就会 大大增加,使成本相对于原来大大增加,所以不可能给信号提供太大的能量,而 建立在香农基础上的编码理论正可以解决这个问题,使得成本降低,实用性增强【2】。 前向纠错技术(FEC)特别是卷积编码是当今无线数字通信系统的一个十分重
要的组成部分。它是一种有效的信道编码方法,在实际中广泛应用。目前无线数

字通信系统都采用某一形式的卷积编码,如在W.CDMA,DVB—S,DVB—T,IEEE
802.11系统中都使用了卷积编码。由于其出色的纠错性能,一般在级联码中作为

内码使用,从而保证外码有效地工作,大大提高了整个系统的纠错能力。而Viterbi
译码器正是针对卷积码的一种最佳译码方法。

CDMA系统以其容量大、抗干扰能力强的特点成为第三代移动通信系统的标 准。CDMA系统的信道编码大多采用卷积编码,这是因为卷积码的纠错能力强, 不仅能纠随机差错,还可以纠突发差错[31。在CDMA系统中,对卷积码的译码采 用Viterbi算法【4J,它是一种最大似然译码方法,当编码约束长度不大、或者误码
率要求不是很高的情况下,Viterbi译码器设备比较简单,计算速度快,因而Viterbi

译码器被广泛应用于各种领域。 现代通信中,随着信号序列的传输速率的不断提高,要求卷积码译码的速度 也要不断提高,Viterbi译码由于充分利用信号序列统计概率的特性而具有最佳性 能。一个实时高速通讯系统,软件实现Viterbi译码几乎不可能。译码速率在很多 情况下是不能够满足要求的。Viterbi译码专用的ASIC,又由于其生成式固定不变,
第1页

国防科技大学研究生院硕士学位论文

所以使州场合非常有限。通信卫星发展的趋势足卫星小型化和集成化,为了达到 此目标,需要鲁棒、灵巧的通信系统。使用现代强大的EDA工具和FPGA技术,

设计一个硬件Viterbi译码器可以极大提高译码速率,而且生成式可以自由改变,

扩大了它的使用范卧¨。
20世纪90年代以来,随着VLSI(VeryLargeScalelC,超大规模集成电路)-1-艺

的不断提高,单一芯片内部可以容纳*偻蚋鼍骞埽殖】杀喑堂耪罅
FPGA(Field Programmable
Gate

Array)和复杂可编程逻辑器件CPLD(Complex

Programmable Logic Device)芯片规模也越来越大,它能实现的功能也越来越强。由

于FPGA/CPLD具有编程方便、集成度高、速度快、可在线重新配置等优点,因而 用其实现各种信号处理的算法己经成为电子设计人员解决实际问题的一种方法。 FPGA最初的设计初衷是代替分离逻辑芯片,提供一个整体的解决方案。传统 上的FPGA与ASIC更像,FPGA可以仿真任何ASIC芯片的逻辑功能,但是时钟 频率低,功耗高。然而FPGA的优势是在系统内可以编程,设计周期短,一次性 成本小,因此在对低功耗要求比较低的场合完全可以代替ASIC。FPGA技术的发 展使得在FPGA芯片上实现信号处理、网络功能成为可能,该技术为可重构卫星 通信系统的实现提供了坚实的基础。在对未来卫星通信发展需求的基础上,提出 了用于设计可重构卫星通信系统的通用架构。FPGA的基本体系结构由数百上千个 基本逻辑模块组成,模块之间的互联网络是可配置的,因此逻辑模块之间可以任
意连接【51。现有Xilinx公司的Virtex.5的FPGA可以提供每秒高达4万亿次的16

比特的定点加法,或每秒12.5亿次单精度浮点乘法。之所以有这样高的性能,是 因为在同一片FPGA上可以实现大量简单的处理单元,而每一个处理单元的运行 速度是数百兆Hz,具有很好的空间并行性。因为基本的FPGA体系结构直接利用 了随技术进步不断增加的逻辑密度,所以每当新一代工艺产生的时候,FPGA的吞 吐性能都可以成倍的提高。实际上,现在的IC厂商很多利用FPGA来试验开发新 的工艺流程,因为FPGA的结构很规则,很容易在新工艺上实现。这样做的结果 就是FPGA芯片总是能够率先采用新工艺,实现更高的性能。 当今芯片产业发展依然遵循摩尔定律,工艺节点不断减小,复杂程度不断增 加,设计周期不断缩短,同时市场竞争也进一步加剧。为了占领市场,实现商业 价值,芯片设计就必须尽可能地提高性能,降低成本。RTL(寄存器传输级)设* 段属于芯片设计的前端设*锥危敲偶逗透撞愫蠖松杓频幕 S朊偶渡杓 相比,RTL设计更专注于系统结构和功能实现,而且由于其设计环境简单,相应 的EDA软件运行速度更快,因此在RTL设*锥谓杏呕芑竦酶玫男 果【3】。现在,各种通讯系统由于自身的特点而应用于不同场合。在欧洲(主要是北 欧、西欧)有许多不同的通讯体制,这些体制互不兼容,无论给用户还是给经营者
第2页

国防科技大学研究生院硕:卜学位论文

都带来了极大的彳i便。囚此,为了增加硬件器件的兼容性,使用范围与运行时间, “可重构计算’’已经在越来越多的领域得到应用,并且得到了越来越多人的青睐 与关注,关于此方面的研究也正在如火如荼的进行【6J。 卫星通讯在环境、安全性、可靠性/可用性、有效性等方面的需求与地面应用 完全不同,随着应用的发展,卫星运营商提出了能够通过更新可再生载荷的配置 方式,动态对卫星进行升级,基于软件无线电(SDR)的可重构技术,使得这一需求
成为可能。

随着时代的发展,对译码性能以及传输的准确性有了更高的要求,为了构成 更加强有力的纠错控制编码,常常把两个或多个简单纠错编码联合起来,构成乘 积编码或级联编码。现在应用非常广泛的广播卫星通讯标准DVB.S便是利用卷积 编码和RS编码进行级联。同时,由于在数据传输的过程中,常常会在有记忆信道 中传输,也就是说会遇到成片的突发错误,那么卷积编码与RS编码的性能将远不 如我们理论上预计的那样,于是我们考虑在两个编码之问加入块交织操作,把成 片的突发错误分散开,增加译码的准确性。 基于以上的相关技术背景,本项目重点研究了Viterbi译码器,用Matlab、 ModelSim等软件进行仿真,并最终用FPGA实现。采取了一系列措施,尽可能地 提高了其译码速率和性能,很多参数编译前可配置。同时根据实际的需要,又对 级联编码以及交织技术作了一定的模拟和研究。

1.2国内外研究现状
目前国内对于Viterbi译码器尚处在基本研发阶段,不同的学校与机构都针对 此项技术作了相关的研究,但是,大都停留在模拟与仿真阶段,没有进行综合与 投片,而且,译码往往只针对单一码率,特定约束长度,不具备可重构性。但是, 他们提出了许多相关的改进思路和实施方案。 比如北京理工大学张健博士曾提出一种模型,整个译码器采用由上至下的设 计方法,设计和仿真工具分别为Xilinx公司的ISE6.1和ModelSim5.7,并基于Xilinx 公司生产的Virtex2系列芯片中的xc2v1000—5b9575进行时序仿真和布线。通过进 行时序仿真和布线,最后译码器的最高运行频率可达90MHz,整个解码器耗用系 统资源为2604个slices,译码延时为45个时钟周期。 目前国外己有*僬椎牡バ酒弑嗦肼实模郑椋簦澹颍猓橐肼肫鳌W觯郑椋簦澹颍猓樗惴ǖ墓
司主要有两家,Xilinx和Altera公司。

1)Altera公司:在01年12月10号,已经做成了初步的可配置Viterbi译码器。 其中,约束长度的可选范围为3到9,软判决位数为2到16。这个全并行化的Viterbi
译码器是当时唯一~款与IEEE 802.16标准兼容的吞吐率超过185Mbps的译码器。
第3页

同防科技大学研究!F院硕士学位论文

2)Xilinx公司:随后,也发布了一款与IEEE 802.16标准兼容的Viterbi译码器。 内核超过了155Mbps的吞吐量。此外,它有一个用两个时钟来实现全同步的版本, 此外,低延迟,低功耗,小体积都是它的突出优势。内核采用基二的高速紧凑体
系结构。它支持可调判决位数的软判决译码。内核采用工业标准的约束长度k=7,

Go=171和Gl=133。两时钟同步版本的回溯长度可为48或96,仅用一个时钟同步
可以使回溯长度达到126。

1.3主要研究内容
对卷积编码,Viterbi译码的基本原理、性能作了研究与探讨,并在算法实现 和具体实现细节上做了一些优化和改进,进一步提高了译码速率,缩小了综合后 面积。本文主要从以下几个角度展开: ●在卷积码、Viterbi译码理论研究的基础上,对Viterbi译码算法做了进一步 深入的研究。主要探讨了提高译码速率、减小硬件复杂度的若干方法,并利用 Matlab软件对一些改进进行模拟和论证。 ?借鉴国外己采用的,将低速率的编译码器并行处理以得到高速率的编译码 器的思想,利用Verilog HDL实现(2,1,7)卷积编码的Viterbi译码IPCore,其中, 软判决位数、交织深度等参数编译前可配置。 ?为了保证设计的正确性以及对其性能进行评估,又进行了仿真和在真实系 统下的FPGA验证。通过一系列实验数据的比较,证明了本译码器的良好性能, 并与国外先进Viterbi译码IPCore进行比较,发现自研IPCore更适合于深空卫星 通讯。 最后,为了让Viterbi译码器的设计更具有实用性,我们仿照广播电视通信系 统(DVB.S)标准,将卷积编码和RS编码级联起来,又在之间加入块交织操作,做 了综合编译码性能评估及分析。

1.4文章的组织结构
其整体结构框图如图1.1所示。 第一章为绪论部分,主要介绍了研究的课题背景、国内外研究现状和主要研
究内容等。

中间章节根据FPGA设计实现的流程,关于Viterbi的译码IPCore设计按照下 面的三层设计。 第一层为文章中第二章,即为算法描述,又称行为级描述,它是对整个系统 数学模型的描述。这种描述的目的是试图在系统设计的初始阶段,通过对系统行
第4页

国防科技大学研究牛院硕士学位论文

为描述的仿真来发现系统设计中存在的问题。这时候更多的是考虑系统结构及其
工作流程是否能够达到系统设计规格书的要求,而与器件工艺无关。我们采用
Matlab

7.0编写代码对整个译码过程进行模拟并对算法的性能进行测试。

图1.1本文整体结构框图

第二层为文章中第三章,即为寄存器传输级(RTL)描述。用第一层次的系统结 构是很难直接映射到具体逻辑元件结构的,为了得到硬件的具体实现,我们用硬
件描述语言Verilog HDL实现编译码过程,再用仿真工具ModelSim 6.0对其进行 仿真(称之为前仿真)。

第三层为文章中第四章,即为逻辑综合和实际测试。利用Xilinx ISE9.0逻辑 综合工具,将RTL方式描述的程序转化为用基本逻辑元件表示的文件(门级网络 表)。此后再对逻辑综合结果在门级电路上进行仿真(称之为后仿真)。如果一切正 常,则说明系统的硬件设计基本结束。得到网表文件后,可以由自动布线程序将
网格表转换成相应的ASIC芯片;我们则是将网格表转换成相应的FPGA编程码点, 利用HAPS一54 FPGA开发板完成硬件电路设计,又在此基础上搭建了真实实验环

境,把自研IPCore的性能与其它公司IPCore做了对比。 至此,单个Viterbi译码算法IPCore的FPGA设计已经完成。 第五章为级联编码部分,为卷积编码与Viterbi译码的拓展性研究。在对Viterbi 译码算法进行研究的基础上,结合DVB.S系统,利用Matlab软件,研究了卷积编 码Viterbi译码与RS编译码级联码的性能,又结合了块交织技术的研究。 第六章对所做的工作进行了归纳总结,并阐明了下一步研究工作方向。

第5页

国防科技人学研究生院硕十学位论文

第二章Viterbi译码算法的实现与改进
2.1卷积编码
2.1.1总体介绍

卷积码是1955年由爱里斯(Elias)提出的。它把k个信息比特编成n个比特, 但一般来说,k和n通常很小,延时小,特别适宜于以串行形式传输信息。与分组 码不同,卷积编码器有记忆性,且在任意给定时间单元处,编码器的n个输出不 仅与此时间单元的k个输入信息有关,而且也与前M(M=K.1)个输入组有关,编码 过程中相互关联的码元为K*n个。所以,卷积码可用参数组(n,k,K)来描述,其中 K=M+I称为编码的约束长度,它说明了编码过程中互相约束码段的个数。M代表 移位寄存器的存储深度,每读入一个新的数据帧,老的数据帧就向右移一位。编 码速率R=k/n,它也是卷积码的重要衡量参数。
卷积码的纠错能力随着M的增加而增大,而差错率随着M的增加而呈指数下

降。在分组码中95%以上的码率是常见的,但在卷积码中码率一般低于90%。由 于码率比较低,所以卷积码的冗余度高,纠错能力也较强。并且,在同样的码率 和设备复杂性条件下,无论从理论还是实际上均己证明卷积码的性能优于分组码,
实现最佳和准最佳译码也比分组码容易。所以,从信道编码定理看,卷积码是一

种非常有前途,能达到信道编码定理要求的码类。 若输入的信息序列%,嘲…m一.是一个半无限长序列,则由卷积码编码器输出的 序列,也是一个由各子码Co,c1…e…,组成的半无限长序列,称此序列为卷积码的 一个码序列或一个码字。用这种卷积码编码器输出的每一子码中的校验元,是此 时刻输入的信息元与前M个子码中相关信息元的模2和,它们是线性关系。
2.1.2三种表述方法

除了用(n,m,K)表示之外,卷积码还有三种表示方法,它们分别是:状态图、树 状图、网格图,下面分别进行介绍(以下三种表示方法,均针对(2,1,3)卷积编码)‘71。 2.1.2.1状态图法 实际上,卷积编码器是一个有限状态机,因此可以用状态转移图来描述。卷积 码的状态图表示给出了编码器当前状态与下一个状态之间的相互关系。如图2.1所

示。图中虚线表示输入码元为…1’时的路径,实线表示输入码元为…0’时的路径,圆
圈内的字母表示编码器的状态,路经上的数字表示编码输出,比如0/01,表示输
第6页

【司防科技大学研究生院硕十学位论文

入信息0时的输出码字为0l。每个状态都有两个箭头发出,对应输入分别是0、l 两种情况下的转移路径。假如输入分别是0、l两种情况下的转移路径,输入序列 是101011010…从状态图可以轻易地找到输入/输出和状态转移关系,可从So状态 出发,根据输入找到相应的箭头,随箭头在状态流图上移动,得到以下的输出结
果:1l
lO OO 10 00 0l 01 00 10…

so地s严sl坦s2呲Sl巡s2……




1/10

I’.../

图2.1卷积编码的状态流图 2.1.2.2树状图法

若一个(n,k,K)卷积码编码器的输入序列是半无限长序列,它的输出序列也是半 无限长序列。这种半无限的输入、输出编码过程,可以用图2.2半无限树图来表示。 图中每个节点对应于一个输入码元。规定,当输入为”0”时,走上分支;输入为”1” 时,走下分支,每个分支的上面的标数,为编码器的输出。根据这个规则,对于 一个给定的码元输入序列,在树状图中,都有唯一的路径与之对应。由于是(2,1,3)
卷积码,即约束长度的值为3,也就是说当前输出译码值不仅与当前位,同时还与

先前两位输入状态有关,我们把先前两个状态值存入移位寄存器,其可能的取值 有四种:00,01,10和11,分别用So,Sl,S2和S3表示,并将其分别标注在码树 的各节点上。例如,针对下图,如果输入的信息序列为1101000…,输出编码序列
为11
0l Ol 00 10 11

oo…其所走路径见图2.2中加粗的支路。

第7页

国防科技大学研究生院硕:}:学位论文

。f


T:
———_一●●S
c“



J‘I


-S



▲ L

Tso


———__—●S



i. ▲

0‘



_¨1_=:。下 o——●S
———◆
ro Ll

————●S

I 2

———_—●S

————●■S

3 0





t 1‘ 0

l————●S
o———_—●s

1 2




———◆

r1
Lo

1———●S













弋¨.?。。 l—1
r1

l—’s






fo ———◆
Ll



o————●s



图2.2卷积编码的树状图
2.1.2.3

网格图法

为表示编码过程中状态转移与时间的关系,首先引入网格(Trellis)图的概念。 以(2,1,3)卷积编码为例,其网格图如图2-3所示【10】。 从上面的树状图可以看出,同类节点(也就是从同一状态生长出的子树)结构完 全相同,因此可以把树的每一层上同类节点归并压缩,压缩后,便得到了图2.3所 示的网格图,它是描述卷积编码的重要工具。2步之后,只保留了四个状态,每个 状态根据输入数据为”0”或”1”,转移到新的状态,同时有2比特输出码字。我们用

实线和虚线分别表示相应输入数据为…0’和”1”,在状态转移分之上所标的2比特数
据为相应的输出码字比特。

图2.3卷积编码网格图表示法

三种表述方各有利弊,网格图上在时间上完全是重复的,把网格图在时间上
第8页

同防科技大学研究生院硕十学位论文

进行归并和压缩,使得到了状态转移图。第二种表述方法很为直观,但是,随着 卷积编码时间的加长,这棵树也过于复杂;状态转移图表述方式非常简洁,提供 了一个比较直观的编码系统描述,但在必要的时候不能显示出系统状态转移随着 时间变化的轨迹。一般在进行Viterbi译码的描述过程中,我们通常要根据具体的 情况来选定描述方式。
2.1.3卷积编码的应用

从信道编码定理看,卷积码是一种很有前途的能达到信道编码定理所提出的 码型,广泛应用于各种领域如:数字卫星通信系统、遥测外测系统、GSM(Group
Special

Mobile)、3G(第三代移动通信)、各种数字电视标准等等。例如:GSM采用

(2,1,5)卷积码;绝大多数卫星通信采用的是(2,1,7)卷积码;CDMA的IS一95标准采 用的是(2,l,9)卷积码;3GPP(第三代移动通信伙伴关系)WCDMA正向信道采用的是 (2,1,9)卷积码,反向信道采用的是(3,1,9)卷积码;CCSDS(空间数据系统咨询委员 会)也把卷积码作为实时要求较高业务的信息纠错编码。此外卷积码还可以和RS
码级联使用。RS码做为外码,卷积码作为内码可应用于DVB.S(欧洲数字视频广

播)标准和ATSC(美国先进电视)标准等等【9】。 本文便采用其中的一种应用最广泛的(2,l,7)卷积码进行了深入的研究,Viterbi 译码也是针对此种卷积码。
2.2

Viterbi译码

2.2.1

卷积码的三种译码方式

针对上面的卷积编码,常用的译码方式有三种:1)门限译码,1963年由梅西 (Massey)提出,它类似于分组码中的大数逻辑译码,是一种码代数结构的代数译码。 2)序列译码,1961年由沃曾克拉夫特(Wozencraft)提出,1963年由费诺(Fano)改进 的,这是基于码树图结构上的一种准最佳的概率译码。3)Viterbi算法,1967年由 维特Lg(Viterbi)提出,这是基于码的网(Trellis)图基础上的一种最大似然译码算法, 是一种最佳的概率译码方法。其中,门限译码性能最差,但硬件实现相对简单; Viterbi译码具有最佳性能,但硬件实现相对要复杂;序列译码在性能和硬件实现
复杂度介于Viterbi译码和门限译码之间。

但是,在码的约束度较小的时候,Viterbi译码比序列译码算法效率高、速度 更快,译码器也较简单。因而自Viterbi算法提出以来,无论在理论上还是在实践 中都得到了极其迅速的发展,并广泛地应用于各种数字通信系统,特别是卫星通
信系统中…。
第9页

囝防科技大学研究生院硕十学位论文
2.2.2

Viterbi译码的基本原理

对于卷积码的最大似然译码,译码的任务是在树状图或网格图中选择一条路 径,使相应的译码序列与接收到的序列之间的距离最小,通常把可能的译码序列 与接收序列之间的距离称为量度。Viterbi译码便是一种最大距离译码,由贝叶斯 公式和欧式距离的定义可推导出,最大似然译码也就等价于最小欧氏距离译码。 基于网格图搜索的译码便是实现最大似然软判决的重要方法和途径。最大似 然译码要求在网格图上所有可能的路径中选一条具有最大度量的路径,当消息序
列长度为L时,可能的路径数目有2L条,于是随着路径长度L的增加,可能的路 径数以指数型增加。若对每条可能路径计算相应的路径度量,然后比较它们的大 小,选取其中最大者,显然是不实用的。用网格图描述时,由于路径的汇聚消除

了树状图中的冗余度,译码过程中只需考虑整个路径集合中那些使似然函数最大 的路径。如果在某一点上发现某条路径己不可能获得最大对数似然函数,就及时 放弃这条路径,然后在剩下的“幸存”路径中重新选择路径,这样一直进行到发 送序列发送完毕。由于这种方法较早地丢弃了那些不可能的路径,从而减轻了译
码的工作量【111。

Viterbi译码正是基于这种想法。对于(n,k,K)卷积码,每个节点(flO每个状态) 有2k条支路引入也有2k条支路引出,所以其网格图中共有2k(K-1)种状态。在我们
的Viterbi译码中,k=l,从全0状态为起始点开始讨论。由于网格图的前M.1条

连续支路构成的路径互不相交,即最初2M。1条路径各不相同,当接收到第M条支 路时,每条路径都有2条支路延伸到第M级上,而第M级上的每两条支路又都汇 聚在一个节点上。在Viterbi译码算法中,把汇聚在每个节点上的两条路径的对数 似然函数累加值进行比较,然后把具有较大对数似然函数累加值的路径保存下来,
而丢弃另一条路径,因而在任何时刻,对进入每一状态的所有路径只需要保留其

一条具有最大部分路径度量的路径,这条被保留的路径被称作幸存路径。由于卷 积码的状态数为2胁1,所以在任何时刻,译码器最多仅需保存2肼1条幸存路径,
和这2¨1条幸存路径所对应的路径度量值。由于每个节点引出两条支路,因此以

后各级中路径的延伸都增大一倍,但比较它们的似然函数累加值后,丢弃一半, 结果留存下来的路径总数保持常数。上述译码过程中的基本操作是“加.比.选" (Add.Compare.Select,ACS),即每级求出两条路径的对数似然函数的累加值,然后 两两比较并作出选择。有时会出现对数似然函数累加值相等的情形,这时,可以 任意选择其中一条作为“幸存”路径。 对于离散无记忆信道来说,在接收到序列r时,发送序列v的似然函数为:

第10页

国防科技人学研究牛院硕十学位论文
L+M—l

P(r/v)=1-I尸(‘/M)其中,三为信息序列的长度,M为移位寄存器长度。相应的
,=O 工+^,一l

对数似然函数为:lgP(r/v)=∑lgP(rj/V)。采用最大似然译码算法,要求在所
面 有可能的码字序列中选取一条使似然函数式极大的码字序列作为发送码字序列的 估计,如果记这最大似然估计码字序列为移,则移=argmaxlg P(r/v)。其中u表示
V∈U

从So出发、长度为L+M、最终回到So状态的码字序列集合。
标准的卷积编码器,要从网格图中的全零状态出发,最后再回到全零状态。

因此,当序列发送完毕后,要在网格图的终结处加上M.1个己知的信息(即M—1个 己知支路)作为结束信息。在结束信息到来时,由于每一状态中只有与己知发送信 息相符的那条支路被延伸,因而在每级比较后,幸存路径减少一半。因此,在接 收到M.1个己知信息后,在整个网格图中就只有唯一的一条幸存路径保留下来, 这就是译码所得的路径。在己知接收到的序列的情况下,这条译码路径和发送序
列是最相似的【l 21。同时,最后的译码结果也要删去这后补充的M一1个信息。

Viterbi译码器结构由以下几个模块组成:BMU(支路度量单元),ACSU(]JH比 选单元),PMU(路径更新存储单元),SMU(幸存路径存储和管理单元),Comrol(控
制模块)。在后面会进行详细介绍。

2.3利用Matlab7.0构建模拟环境
2.3.1总体设计流程

为了对Viterbi算法的性能进行评估,首先用用Matlab编写代码,搭建一个模 拟系统的实验*台。该系统包括编译码、调*獾鳌⑿诺涝谟性肷诺老碌拇 以及结果比较【13】。整体设计流程如图2.4所示。

图2.4

Viterbi算法流程图 第1l页

国防科技大学研究生院硕士学何论文

在Viterbi译码模块中,每个状态的度量值与幸存路径在卜^一时刻的值分别与 它们上一时刻的值相关。因此,对每个状态的度量值和幸存路径,我们都分别用 两个数组进行存储,采用“乒乓交换法’’(即轮流作为输入与输出),交替更新。寄
存器交换法也由此得名。

2.3.2各模块功能与实现 2.3.2.1数据生成模块 功能:本模块随机产生,个随机数,值分别为0或l。 实现:先利用rand函数随机生成一个长度为,的一维向量,其值全部为O,l 之间的小数。让这,个小数依次与0.5比较,大于0.5则对应生成元输出位为1, 小于O.5则相应输出位为O。 2.3.2.2卷积编码模块 功能:把上面生成的,个数进行卷积编码。 实现:设约束长度为K,首先在输入数组,的两边各添加K.1个0,设补零后 向量为moutput。设立个大矩阵U,每--N行数为K,第--YU值分别为向量moutput 的第1到第K位,第--y0的值分别为向量moutput的第2位到第K+1位……以此 类推,直至遍历整个向量moutput,然后,让这个矩阵U转置后乘以生成矩阵G, 便可得到输入矩阵的卷积编码向量。 由于Matlab是基于向量运算,所以,在实现移位操作时,我们可以创立个大 矩阵,整体利用一次矩阵乘法,这样,就不用一步步地用移位寄存器频繁的存取 移位,提高了效率。但是,却占用了较大的存储面积,是一种较为典型的“用空 间换时间"的方法。 2.3.2.3凿孔模块 功能:把生成的卷积码按照一定的规则进行凿孔,以便于增加数据传输率。 实现:根据规则,可以把1/2码率的卷积码,通过凿孔凿成2/3和3/4码率。 当要把卷积编码凿成2/3码率时,按照规定,每隔四位凿掉最后一位。具体实 现方法是把输入的卷积编码数组分成每四位一组。输出凿孔卷积码数组每三个分 成一组,每个值分别等于输入的卷积编码数组的前三位。卷积编码数组最后不足 四个的直接补在凿孔卷积码数组后面。 当要把卷积编码凿成3/4码率时,按照规定,每隔六位凿掉第4、5位。具体 实现方法是把输入的卷积编码数组分成每六位一组。输出凿孔卷积码数组中每四 位分成一组,每个值分别等于卷积编码数组的第1、2、3、6位。卷积编码最后不 足六位的直接补在凿孔卷积码数组后面。
第12页

国防科技大学研究生院硕士学位论文
2.3.2.4

BPSK调制模块

简介:数字调制是把数字符号转换成适合于信道特征的波形。例如在无线通 讯中,为了有效地发射无线信号,要求天线尺寸与无线电波长相当。所以要对原 始信号进行调制,将低频信号变为高频。本文中采用二元正弦波数字相位调制 (BPSK),其中数据”0”和”1”控制相位”0”和”7r”的切换。这是一种对映信号,与M=2
的对称双极性幅度调制一样。

功能:将原始凿孔卷积码数据流进行调制【141,以便于传播与接收。 实现:BPSK调制是一种最简单的PSK调制,对应星座图的两个点全部在实
轴上,其相位角分别为0。和180‘。这样,O被调制成.1,l调制后仍为1。

2.3.2.5高斯白噪声信道传输模块
简介:白噪声(White noise),是一种功率谱密度为常数的随机信号或随机过程,

即此种信号在各个频段上的功率是一样的。由于白光是由各种频率(颜色)的单色光 混合而成,因而此信号的这种具有*坦功率谱的性质被称作是“白色的”,此信 号也因此被称作白噪声。相对的,其他不具有这一性质的噪声信号被称为有色噪
声。 理想的白噪声具有无限带宽,因而其能量是无限大,这在现实世界是不可能

存在的。实际上,我们常常将有限带宽的*整信号视为白噪声,以方便进行数学
分析。符合高斯分布的白噪声称为高斯白噪声。为了使模型更加典型化,本文中 所加的噪声即高斯白噪声。

功能:并且为了保证信道传播模拟的真实性,在信道传输过程中加入高斯白
噪声干扰。

实现:利用Matlab软件中自带的AWGN函数,对原始数据进行干扰处理,
原始的两种码值一1和l被扰动成区间(.1,1)之间的数。

2.3.2.6解调模块 功能:在接收端对经过调制且在有干扰信道中传输后的数据进行解调,即为
调制的逆过程,以便于后面的译码。

实现:具体解调方式有两种,硬判决与软判决。 当采用硬判决时,对于接收到的码元数据,小于零时,对应位检测数据定为O;
大于零的,对应位检测数据定为1。

为了使译码器能以更大的正确概率判决,就把解调器输出的抽样电压进行分 层或量化,称作软判决。本文中,采用量化级数为3,即8个量化值,分别为:
ooo(强0),001,……11 1(强1)。由于接收到的每个模拟量为区间(一l,1)之间的小数,

所以,在量化时,首先把区间(.1,1)均分成7段,共8个截点,分别代表8个量化
第13页

国防科技大学研究牛院硕+学位论文

值。具体分划方法示意如图2.5所示。
一1—0.8571 Ooo

i一一一一一————二~…:一一.j……r一…J…一『一——j一一一T一——…L—了———一。—一
00l 010 011 100 101 110

-0.5714

—0.2857



0.2857

0.5714

0.8571



111

图2.5软判决区间量化图

根据量化理论,以各段中点为界,靠*哪一端则量化成哪个值。这样,我们 就把接收到的数据按照级数为3,量化成8个值,参与后面的Viterbi译码过程中。 2.3.2.7反凿子L模块
功能:为凿孔模的逆运算,根据一定的规则把原来在凿孔模块中凿掉的位填补 上0。

实现: 当要实现把收到的码流由2/3码率恢复成1/2码率时,首先要把补零后的数组
data

insert0分成四个一组,把接收检测到的数组data dec分成三个一组。data

insert0

数组每组中的前三个值分别等于数组data dec对应组中的三个值,data insert0数组 的第四个值等于3,即(弱零)。然后,再创立标志位数组flag,其长度等于data_insert0
数组,也和data insert0数组一样,分成四个一组,前三个分别等于O,第四个为1, 以表明data insert0中该位并非接收到的真实值,而是通过反凿孔补的零。最后,把
data

dec数组中不足三个,多的元素补在data insert0数组的后面。这样,data

insert0

数组便是经过反凿孔之后得到的数组。 当要实现把接收到的码流由3/4码率恢复成1/2码率时,首先要把补零后的数
组data insert0分成六个一组,把接收检测到的数组data dec分成四个一组。
data

insert0数组每组中的第1、2、3、6个值分别等于数组data dec对应组中的四
也和data insert0数组一样,分成六个

个个值,data insert0数组的第4、5个值等于3,即(弱零)。然后,再创立标志位
数组flag,其长度等于data insert0数组,

一组,第1、2、3、6个值分别等于O,第4、5个值为1,以表明data insert0中该 位并非接收到的真实值,而是通过反凿孔补的零。最后,把data dec数组中不足
四个,多的元素补在data insert0数组的后面。这样,data insert0数组便是经过反 凿孔之后得到的数组。
2.3.2.8

Viterbi译码模块

功能:对接收到的数据进行Viterbi译码 实现:算法流程描述如图2.6所示。说明:整体网格图的遍历分成两大部分, 第一为非尾部部分遍历,第二部分为尾部部分遍历。所谓尾部部分遍历,即在网 格图的最后阶段,接收补上的约束长度个零,使得所有状态全部归零。即使采用 截短法,不用每隔几个数据就补约束长度个零,但是,在译码的最后阶段,仍然
第14页

国防科技大学研究牛院硕七学位论文

要补充一定数量的零。下面具体说明各个模块的含义。

图2.6

Matlab译码算法流程总图

●网格图的建立以及相关参数初始化模块:

包括约束长度、状态数目、度量值截断上限、幸存路径度量值的初始化以及 网格图的建立、输入输出序列的确定,等等。
?分支度量计算模块:
第15页

国防科技人学研究牛院硕十学何论文

该模块按照Viterbi译码输出的位数来计算该输出译码序列与接收到的序列之

间的距离,在本文中,采用欧式距离或者改进的欧式距离。由于前面进行了凿孔 和反凿孔操作,所以,要根据反凿孔模块当前接收数据位的标识来判断该位是真 实数据还是经过反凿孔操作填补的弱零,进而判断该位是否要计入后面的度量值
累加计算。

?加比选单元:
该模块负责从到达后一状态的两条路径中选择一条度量值较小的。其流程图

如图2.7所示,其中:
state

metric代表状态累加度量值;
metric为分支度量值;

branch

i代表在主流程图里网格图中的步骤数;

flag为状态标志位,代表对应的状态寄存器是否被修改过,初始值为O;
path_regl与path_re92为两条路径寄存器。

2.4算法级改进及论证
在性能评估模块中,我们针对Viterbi译码作了一些实验,并对一些具体算法 的改进进行了可行性分析。 我们模拟分析了不同的信噪比、凿孔码率、软判决位数对误码率的影响以及 约束长度对译码复杂度的影响等等。又重点讨论了在不同信噪比下,采用软硬判 决方式、改进的度量值计算方法和截短法,分别对译码性能(误码率)的影响。
2.4.1

软硬判决性能比对实验
软硬判决它们之间不同之处在于量化电*数量以及支路量度的计算方法。硬

判决译码采用二电*量化(即量化电*Q:2),也就是硬判决,当接收信号大于0时, 判为”0”,否则判为”l”。这种量化虽然很为简洁,但太粗糙,将丢失许多有用的信

息。此外硬判决是以序列之间的汉明距离作为量度,适用于二进制对称信道(BSC)。
为了充分利用接收信号波形中的信息,使译码器能够以更大的正确概率判决所

发的码字,就把解调器输出的抽样电压进行量化。因而由解调器输出的供给译码 器的值就不止两个,而有Q(通常Q=2m)个。另一方面若译码器直接利用解调器的 未量化的模拟电压进行译码,称为模拟译码。无论译码器利用Q进制量化值进行 Viterbi译码,还是利用模拟量的模拟译码,统称为软判决译码。这样充分利用了 信道输出信号的信息,提高了译码的可靠性,是一种适用于离散无记忆信道(DMC) 的译码方法。通常,译码器利用附加的软判决信息进行软判决Viterbi译码时比硬判
第16页

国防科技大学珥f究牛院硕士学位论文

决Viterbi译码能得到额外的2.3dB软判决增益,向软判决Viterbi译码器的结构并不

比硬判决的复杂很多。当然,Q越大,性能越好,但实现无限电*量化相对困难,
而采用8电*软判决译码较无限电*软判决译码,编码增益损失只有0.2dBll5】。所

以,本文也采用8电*均匀量化,其性能也基本上可达到最大似然译码的性能。

图2.7加比选(ACS)单元流程图

究竟软硬判决对于Viterbi译码来说,能够提高多少性能呢,我们利用Matlab 进行了软件模拟,软判决位数为8,选取不同延迟深度,模拟结果如图2.8所示。 其中,横坐标为不同的信噪比,纵坐标为误码率。浅色X号虚连线代表软判决情 况时,深色+号实连线代表硬判决情况。从图2.8可以看出,采用软判决Viterbi
第17页

国防科技大学研究生院硕士学位论文

译码方式的确使得译码性能得剑提高,增加*3db的增益。

~ '


皇下:目说匹应*97来H
' ’

t l



l ‘






/}
拓正狼澡庸_j}f36时 旺迟深度为54时

, l

『『、、影 缪。
4:5 § 5:5



/, ∥{ …殇

凑瑟量l~.:




7 5

爱岷擂 图2.8软硬判决性能比较

2.4.2简化欧式距离与截短法应用实验

Viterbi译码算法在软判决时要采用欧式距离,假设软判决位数为3,支路输出 码为(口,,a2,a3),接收到的码字为(6,,b2,63)(十进制值为b)。则标准欧式距离计算公式

应为:√(q一61)2+(吃-b2)2+(吧一63)2。如果这个操作用硬件来实现,会很复杂。
考虑到码子中每个元素只是0或l,可以建立查找表,但不具备通用性,且随着软 判决位数的增加,查找表会迅速增加。于是考虑对欧式距离进行简化,考虑能否 将它优化成:l al一6l I+I口,一改l+I a3一以|116J[281。 此外,在标准Viterbi译码算法中,要求在译码之后回到网格图中的零状态。

这样,传输中就要在每三个数据后,添加嗽移位寄存器深度)个O,以判决出最优
路径。但显然实际传输速率损失了M/(M+L)。对于很大的三,会减小这种损失,但 会使幸存路径存储器随着变得很大,同时使译码延时增长,所以考虑采用截短法。 所谓截短法,即让每条幸存路径只存储其最*的,(,<<L)个消息数据,其中,定义 为交织深度。存满后进行强制性判决,确定第一个消息的数据比特,并作为译码 器的最终判决输出,然后从存储器中删除第一个消息数据比特,腾出空间可以暂 存新来到的幸存数据比特。如此过程重复进行【lⅢ。最后在2M条幸存路径中,本文 选择第1路作为输出。截短法是一种对标准算法的*似【l¨。 两种优化是否可行,是否适合于寄存器交换法呢?利用Matlab软件,用数据
生成器生成10万数据,之后进行模拟。结果比较如图2.9所示。

第18页

国防科技人学研究生院硕士学位论文



SIqR/dB

图2.9多种情况模拟比较图

其中,+点深色连线代表欧式距离情况,X点浅色连线代表改进度量值计算方
法情况。粗虚线代表正规Viterbi译码算法情况。 根据图2.9得出结论:

1)欧式距离优化成绝对值距离和的形式,性能上两者相差无几,但优化后硬 件实现大大简化,方案可行。 2)采用截短法不用每隔几十个数据就补约束长度个零,特别是在码流较长的 情况下,大大提高了效率。同时,改进后误码率基本上和原来处于同一数量级,
信噪比越高,相差越小。故该方案也可行。

3)随着信噪比的增大,误码率呈指数型递减。

2.5本章小结
本章首先做了关于卷积编码和Viterbi译码的研究和探讨。重点介绍了卷积编 码的编码过程、表述方式以及Viterbi译码算法的原理和过程,提出了实现Viterbi 译码算法的具体模块设计方案。重点是想在算法级上论证对Viterbi译码算法所作 一些改进的可行性,比如简化欧式距离和截短法是否适合于寄存器交换法以及这 两种简化会对Viterbi译码性能产生多大的影响等等。还用模拟实验证明了在 Viterbi译码算法中,软判决比硬判决的确在性能上好2。3db。为了完成这些实验,
我们首先设计了整体测试流程,用Matlab编写代码,搭建了实验*台。所以,本 章中也包含对系统中各模块具体设计思路的介绍。

第19页

国防科技大学研究生院硕士学位论文

第三章Viterbi译码器RTL级优化与实现
3.1自研IPCore改进及特点
3.1.1具体改进 基于以上算法级研究的基础,我们可以得出结论,即欧式距离的改进以及截 短法依然适用于寄存器交换法的Viterbi译码算法。在本章中,又做了用等效的思 想简化启动过程、度量值预溢出位设计、加比选计算并行化等一系列优化,进一 步改进了Viterbi译码算法的性能提高了译码速率。借助凿孔恢复模块和Viterbi译
码模块配置文件(RegExViterbi .v与noe.位决判软,)v. gif ViterbiDePunctured.eonfig

数、交织深度等参数在FPGA实现时均为编译前可配置。具体改进细节穿插于各
模块的设计中。 3.1.2总体特点

本IPCore译码速度较快,应用广泛,其基本特点如下所示。 ?Viterbi译码模块速度比较快,达到*200Mbps。
●适用于Virtex.II Pro,ViIrtex.4,Virtex-5,SpartanTM一3,Spartan-3A/3AN/3A
and Spartan.3E DSP

FPGAs等工具。

?单一时钟全同步设计。

?支持数据信息无间隙连续输入与带使能的间歇输入。 ?输入信号宽度为3比特。
?将用于DVB.S系统,作为纠错码内码。 3.1.3功能描述

本IPCore译码误码率较低,性能较好,其功能如下所示。 ?我们这次所作的Viterbi译码器,能够接收多种比率的凿孔卷积码,并采用 寄存器交换法,经大量数据测试,误码率很低,也尽可能作了优化,缩小了面积。
?主要针对(2,1,7)卷积码,该卷积码生成多项式为(171,133),这种类型的卷

积码应用非常广泛,所以这种译码器也很有应用价值。 ?输入为凿孔后卷积码,三位串行输入,接收到进程开始信号后,先根据不 同的凿孔比率进行反凿孔恢复,将恢复后数据进行标准码率Viterbi译码,输出译 码后数据,一位串行输出。 ?在译码的过程中,就同时进行误码率统计。
第20页

国防科技大学研究生院硕+学位论文

3.2译码器整体设计方案
3.2.1

整体框图

整体译码模块,数据输入为一路凿孔卷积码,并设有输入使能,数据输出为 路译码数据,并设输出使能信号,如图3.1所示。
DPREV—.RST..N DPREV—B Seri81DatBI

n(2:0) DPREV—B—BERCOUnter(15:0)

DPREV



ProStart DPREV■BERD0ne

DPREV一-一ProSt0P DPREV DPREV—T—S0ftRe
8et



N0r-ali zed

DPREV—B—Decod eD8ta DPREV B Seri81 DataIn DPREV一■一Decod eDataEnabl DPREV T S erialDataEn8ble


图3.1整体输入输出引脚

RegExViterbi_W_ProStart

2egExViterbij堂astop
RegExViterbi_CLK RegBⅨViterbi_B

BERCounter(15:0)

2egExViterbi—.RST—.N

Re皿xViterbi,豳m∞e
Re蠲xViterbi_W_SoftReset

-—+

Re出ViterbiJ
VDP_C1J【

Normalized

VDP_B_I)amOutl71[2:O]
VDP..RST..N Vl】P

l_◆ RegExViterbi_B_EncodeDatal71[2:O】
RegEIViterbi_B

DecodeData[2:0:

B_DataOutl33[2:0]

—◆ RegExViterbi_B_EncodeDatal3312:0】
Reg既Viterbi,Decode踟taE∞b1E

"妮I£国ftRest
VDP_W_MetricEnablel71

l-_● RegExViterbij里etricEnablel71

V-坤_B SetialDataIn[2:o]
V1)P_W_MetricFJmblel33

_-?●

RegExViterbl3坠tric眈曲lel33
|le虚Iviterbj I踟∞de阮taE∞ble 标准码目EViterbi译码模块

V坤LserialDBtaEnable
V卯,0I|t叫tElIBble 凿孔恢复模块

图3.2模块内部连线图

如图3.2所示,译码器内部含两大模块,一个负责凿孔码恢复,一个负责标准 码率下(即R=l/2)Viterbi译码。凿孔恢复模块主要负责把不同码率的凿孔卷积码恢 复成l/2码率的符合(2,1,7)标准的卷积码,然后再对恢复后码进行Viterbi译码。下
面我们针对两个模块分别作下说明。
第21页

国防科技大学研究生院硕.}:学位论文

3.2.2输入输出接口列表

两个模块的输入输出引脚图如表3.1,表3.2所示。
表3.1 Viterbi反凿孔模块输入输出引脚 引脚名
VDP——CLK

方向 输入 输入 输入

信号引脚说明 外来输入的时钟频率 主复位信号,当整个系统都要复位时,此信号置零 软复位信号,当只希望本模块发生复位时,此信号将被 置零

VDP卫S忑奠

VD芝嵫SoftReset
VDP——B——SerialDataIn

输入 输入 输出 输出 输出

凿孔后的Viterbi输入数据,为0或7 外部数据输入使能,指外部输入数据是否有效 经过反凿孔操作后的171路输出数据暂存器 经过反凿孔操作后的133路输出数据暂存器

VD£必SerialDataEnable
VDP——B——DataOutl 7 1 VDP——B——DataOutl 33

VD峰N

MetricEnable 1 7 1
1 33

用来判别上面输出的171路数据是反凿孔后的补零数据
还是真实数据

VD峄奠MetricEnable

输出

用米判别上面输出的133路数据是反凿孔后的补零数据 还是真实数据

VDP——W——OutputEnable

输出

对外输出信号,用来标识输出的数据是否有效

表3.2标准码率Viterbi译码模块输入输出引脚 引脚名
RegExViterbi_CLK

方向 输入 输入

信号引脚说明 外在时钟输入信号 外在输入复位信号 开始Viterbi译码信号 结束Viterbi译码信号 Viterbi软复位输入信号,当只想对这一个模块 进行复位时,使用该信号

RegExViterbi_RST--N

RegExViterbiN jroStart RegExViterb凡N,roStop RegExViterbi N—SoftReset
RegExViterbi——B——EncodeDatal 71 RegExViterbi B EncodeDatal 33

输入
输入 输入

输入 输入 输入 输入

译码器171路的输入,用来进行译码 译码器133路的输入,用来进行译码 输入信号是否有效 用来判另U171路输入是有效数据位,还是反凿 孔后的补零位

RegExViterbi——W——EncodeDataEnable
RegExViterbi

N MetricEnable

17 1

RegExViterb氏N MetricEnable 1 33
RegExViterbi B BERCounter

输入
输出 输出 输出 输出 输出

用来判别133路输入是有效数据位,还是反凿 孔后的补零位 误码率计数器

RegExViterbi——W——BERDone
RegExViterbi

指示已经检测到了指定数目的错误 (可选位)度量值是否超出过最人值
译码数据输出 译码输出使能信号

N奠ormalized

RegExViterbi B DecodeData

RegExViterbi翼pecodeDataEnable

第22页

国防科技大学研究生院硕士学何论文

3.2.3各文件之间调用关系 各文件的包含关系树图如图3.3所示。

testbench.v


DepuncturedRegExViterbi.V

Re2ExViterbi.v

ⅥterbiDePunctured.v

FIFO.V

RegExViterbiConfig.V

./。
RAMB4_S8-S8.V

ViterbiDePuncturedConfig.v

图3.3文件包含调用关系树图

3.3凿孔恢复模块
3.3.1总体设计思路 根据Viterbi译码算法,我们可以看出,其复杂度随着卷积编码码率的提高迅 速变大,高码率卷积码的Viterbi译码器实现起来过于复杂,这就使得目前大多数 Viterbi译码器仅限于低码率卷积码的译码。为解决在某些信道利用率高的场合中 能够使用高编码率译码器的问题,可以考虑对卷积编码进行凿孔来进一步提高码
率。

凿孔的目的,即对于一组固定输入输出位数的卷积编码,将之凿成不同的码 率以提高效率,主要用来实现多码率译码。凿孔码的Viterbi译码与原始的低编码
率的译码很相似,只是在分支量度的计算上需要作些修改,所以与相同码率的原

始高码率译码相比,凿孔码的译码复杂度就大为降低了。 如图3.2所示,该模块有一路凿孔卷积码输入,通过在相应位填补数据,输出 为两路凿孔恢复数据,作为标准码率Viterbi译码模块的输入。 由112凿成2/3码率时,规定对于编码后的卷积码流,每隔4个凿掉最后一个, 由于(1/2)*(4/3)=2/3,就得到了2/3的码率。同样,每隔6个凿掉2个数据(第4、 第5个),由于(1/2)*(6/4)=3/4,就得到了3/4的码率。在ViterbiDepunctured


第23页

国防科技大学研究生院硕士学位论文

中,针对每种凿孔方式,对译码输出的133和171路都建立了凿孔使能表,表中1 代表该位在进行凿孔时未被凿掉,0代表该位在凿孔时就已经被凿掉了,现在要补 回。2/3码率的两路凿孔使能表分别为2-b11和2'b10;3/4码率的两路凿孔使能表 分别为3lbllO和Ybl01。具体采用哪种码率的凿孔恢复方式,可根据的得到的输 入码流对自研IPCore进行编译前的配置【18J【1圳。 在进行凿孔操作时,由于凿掉了相应位上的数据,凿孔恢复操作所作的工作 也就是在被凿掉的相应位上补回数据。若某位在凿孔表中对应位为O,说明后填补 的数据非真实接收到的数据,并对填补的数据加以标识,让该位在后面标准码率 Viterbi译码模块的加比选单元(ACSU)中不参与度量值的计算。所以,所填补的数 据值O或1均可。 3.3.2具体设计方案 在具体实现时,采用“并行位步进"法。即以两行凿孔表组成一个整体为依 据,一路凿孔卷积编码输入,输出到两路输出暂存寄存器,根据输入位和凿孔表 中相对应的两位的值,在凿孔表中两对应位一组进行整体步进。给输出暂存器赋 值的同时给输出添加使能信号,以标识输出值在该时刻是否有效和标识该输出位 是真实码还是凿孔后恢复码。以3/4码率的凿孔表为例,参见图3.4。

rVDP rVDP

图3.4凿孔恢复模块总示意图

?wMetricCutted代表在凿孔表中相对应位异或运算的结果。 ?wStepMetricTable为在凿孔表中能否步进的标识位,当rCurrentState=l或
wMetricCutted=l时,wStepMetricTable信号为高有效。

?wMetricTableCycleRestart为凿孔表中重新开始的标志位,当使能表步进数 减到零且有输入和步进信号时,wMetricTableCycleRestart信号为高有效。
第24页

国防科技大学研究生院硕士学位论文

按照图中箭头的标识,如此往复对凿孔数据进行恢复,具体分成四个模块。 1)主状态机l,rCurrentState状态转移图如图3.5所示。
输 入 数 据 有

图3.5

输入数据有效

输入数据有效且
WMetricCutted=O rCurrentState状态转移图

?rCurrentState初始值为零,为零表示在凿孔表中仅有一路输入有效。 ?当wMetricCutted=l时,表示在凿孔表中的两个对应位异或为1,即在凿 孔表中,此时对应的两位不一致,分别为O或1,代表此时刻两路只需要接受一个 有效数据,凿孔表便可步进。把接收到的数据同时传给两路输出数据暂存器 rVDPDatal71和rYDPDatal33,最后在数据输出时,根据凿孔表确定输出有效信 号,用来区分该数据属于哪个暂存器。这样,rCurrentState始终处在0状态。 ?当wMetricCutted=0时,表示在凿孔表中的两个对应位相同,在设计凿孔 表时,不会出现两位同时为O的情况,只可能两位同时为l,这样,需要接收两位 有效输入数据后凿孔表方可步进。当接收一个输入有效数据时,把这路输入数据 送给1 33路输出数据暂存器,rCurrentState进入状态l,再接收一个有效数据时, 把数据赋给171路输出数据暂存器,然后rCurrentState重新进入状态0。 2)主状态机2,使能表中步进步数状态机,其状态转移示意图如图3.6所示。

图3.6使能表中步进步数状态机变化流程图

?rVDPMetricEnableState初始值为凿孔码深度减1(由于它从O开始计数), 没有接收到wMetricTableCycleRestart信号时,说明rVDPMetricEnableState还没有 减少到0,该值减l;若wMetricTableCycleRestart信号高有效,则rVDPMetric. EnableState重新初始化为凿孔码深度减1。如此反复进行循环直至译码结束。 3)根据rCurrentState寄存器和输入数据的情况来给输出暂存寄存器赋值。
第25页

罔防科技大学研究生院硕十学位论文

?当没有数据输入时,两路输出暂存器(rVDPDatal71和rVDPDatal33)全部
保持原值不变。

?当有数据输入且rCurrentState=O时,将输入值打入到两个寄存器中,利用 该时刻的输出使能有效信号来区分该输入数据究竟归属于哪一路。 ?当有数据输入且rCurrentState=l时,第一路rVDPDatal33保持原值不变,
rVDPDatal 71寄存器接收新到来的数据。因为当rCurrentState=0时,当时的输入数

据已经输入到rVDPDatal33中,该寄存器只消保持原值不变即可。

4)根据凿孔表来确定输出使能,在本设计中使能信号有三个。
?rVDPOutputEnable,表示VDP 输出信号是否有效。 ●rVDPMetricEnablel33和rVDPMetricEnablel71,分别表示对应输出位
VDP B B

DataOutl33和VDP

B DataOutl 71两个

DataOutl33和rVDPMetricEnablel71的有效输出是凿孔恢复位还是真实数

据,如果是真实数据,该位就记入后面的标准码率Viterbi译码模块中度量值的计 算,如果是通过凿孔恢复后的补零位则不记入度量值的计算。
3.3.3断流功能的支持

由于上述两个状态机的转动全部要用输入有效位进行驱动,所以,断流时, 即较长的一段时间内,数据输入使能信号为低电*,输入无效。这时状态机就会 停止状态转换,寄存器的值保持不变,即保留现场。所以,上述模块在有断流的 情况下的依然可以正确的进行凿孔恢复操作。

3.4标准码率Viterbi译码模块
3.4.1总体设计与等效启动过程

该模块由具体以下几个子模块组成:分支度量单元(BMU),加比选单元 (ACSU),幸存路径管理单元(SMU)和路径更新单元(PMU),根据需要,还补充 了BERU(误码率计算单元)【201。具体框图如图3.7所示。
各部分具体功能如下:

BMU:负责生成所有可能的路径,并计算进入加比选译码单元各分支的欧式 距离,为后继的ACS单元提供输入。 ACSU:负责对生成的分支路径欧式距离进行累加、比较、选择并输出路径度
量较小的节点。

PMU:负责存储每一级所有节点的路径度量值,并在时钟控制下不断进行更
新。
第26页

同防科技大学研究生院硕士学位论文

SMU:负责存储幸存路径信息并输出译码序列。 OUTPUT:输出经过Viterbi译码后的结果,设置输出使能信号,并且,把译 码结果送给BERU进行误码率的统计。 BERU:负责统计传输信道上的误码率,是指示Viterbi译码是否正确的重要
评估参数。

图3.7标准码率Viterbi译码模块框图

此外,Viterbi译码算法要求网格图从第零状态开始,然后通过启动过程,到 达中间过程,即每个状态都是可到达的。但是,启动过程代码编写比较繁琐。如 果假想预先进入约束长度个0,那么,所有状态均为可达且状态度量值初始全部变 为O,这样就直接进入了中间状态,开始正式译码,只不过,在译码输出时,开始 要输出约束长度个0,只要让输出有效信号延迟几拍,得到的输出数据即为有效数
据。这是一种“等效”的思想,却简化了代码,增强了其可读性。 3.4.2分支度量单元与简化欧式距离

第一个子模块是分支度量单元(BMU)。所谓分支度量,即Viterbi译码器接收
到来自信道的经过量化后的判决信息,并利用该判决信息来计算网各中各个分支

的度量。根据判别的位数不同又分成硬判决和软判决。硬判决采用l位判别位和 汉明距离作为量度;软判决采用多位判别位和欧几里德距离。(欧氏距离公式为:
local

distance(n,f)=∑【s,(甩)一G,(,z)】2)软判决会增大芯片面积,但与硬判决相比能 刃。


够提供差不多3db的增益。在对编码进行凿孔时,不能使用硬判决,而在卫星通

讯中,为了进一步提高通讯效率,往往采用1/2j3/4的凿孔方式,所以,本设计 采用软判决并且码间距计算方法采用欧式距离。在用Verilog HDL进行实现时,软 判决的位数为3、4、5可选。
根据上面利用Matlab软件进行的模拟,当随机产生上万个原始数据时,进行
第27页

国防科技大学研究生院硕}:学位论文

卷积编码,再分别用两种码fuJ/眶计算方式进行Viterbi泽码模拟,发现分别得到的

误码率相差得很少,所以在进行硬件实现时,仍将欧式距离原始计算方法,

√心一岛)2+(呸一岛)2+电一63)2改进成绝对值和I al一6l

I+l口2一也I+I口3—63 I的形式。

由于支路输出码字“十进制的值)要么为强1即(1,1,1),要么为强0即(O,0,O)。当 a=0时,修改后计算式的值为b;当a=7时,修改后计算式值的值为7-b,即为石。 这样优化,就大大减化了硬件实现的复杂度,由复杂的数学运算转变为简单的逻
辑运算。 在用硬件实现的过程中,如果像在用软件模拟时那样,采用矩阵的乘法操作

来计算输出度量值的话,那么势必会大大增加硬件代价,可以考虑用ROM读取操 作来实现,但是,这样必然又会有读取的时间延迟。由于我们所针对的是(2,1,7) 卷积码,状态一共只有64个,那么在网格图的中间过程,每个状态都有前一个时 刻的两个状态到达,所以,只需对应64x2=128种分支度量输出情况,只需要在编 程时,逐一写出这些状态转移语句即可。具体参见表3.3。
表3.3状态转移与分支度量值输出列表
输入为0时 初始 状态
0 l 2 3 4 5 6 7 8 9 10 1 1 12 13 14 15 16 17

输入为1时
分支 到达 状态
16 16 17 17 18 18 19 19 20 20 21 2l 22 22 23 23 24 24

分支 输出
00 ll 01 10 00 11 01 10 11 oo 10 01 11 00 lO 01 11 00

到达 状态
O O l 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8

初始 状态
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

初始 状态
O 1 2 3 4 5 6 7 8 9 10 1 1 12 13 14 15 16 17

分支 输出
1 1 00 10 Ol 1l 00 10 0l 00 l l 01 10 00 1 1 0l 10 00 ll

到达
状态
32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40

初始 状态
32 33 34 35 36 37 38 39 40 4l 42 43 44 45 46 47 48 49

分支 输出
0l 10 00 ll Ol 10 00 11 10 Ol 11 00 10 0l ll 00 lO 01

到达 状态
48 48 49 49 50 50 5l 5l 52 52 53 53 54 54 55 55 56 56

输出
10 Ol 1 1 00 10 0l l l 00 Ol 10 00 ll Ol 10 00 l1 0l 10

第28页

国防科技大学研究生院硕十学位论文 续表3.3 输入为0时 初始 状态
19 20 21 22 23 24 25 26 27 28 29 30 3l

输入为l时 分支 输出
1 l 01 10 00 11 10 01 ll 00 10 01 l l 00

分支 输出
01 ll 00 10 01 00 1l 0l 10 00 1 l 01 10

到达 状态
9 10 lO l 1 1l 12 12 13 13 14 14 15 15

初始 状态
5l 52 53 54 55 56 57 58 59 60 61 62 63

到达 状态
25 26 26 27 27 28 28 29 29 30 30 3l 31

初始 状态
19 20 21 22 23 24 25 26 27 28 29 30 3l

分支 输出
10 00 1 1 Ol 10 1l 00 lO 0l l l 00 lO 01

到达 状态
41 42 42 43 43 44 44 45 45 46 46 47 47

初始

分支

到达 状态
57 58 58 59 59 60 60 6l 6l 62 62 63 63

状态
5l 52 53 54 55 56 57 58 59 60 61 62 63

输出
00 10 0l l 1 00 01 10 00 1l 0l 10 00 1 1

根据这个表和初始到达状态,我们就可以查到分支输出比特,根据输出比特, 就可以确定优化欧式距离绝对值和的形式。然后通过做简单的加操作,就可确定 出在该时刻,某一分支输出码与接收到的相应码字之间的欧式距离了。通过以上 简化,我们省去了矩阵乘法,浮点乘除开根等复杂的浮点运算,大大简化了硬件 实现代价,提高了效率。简化后的硬件实现框图如图3.7所示。 有的时候根据需要,强1,强0需要做一些修改,现在常用的关于软比特定义 有如下三种类型,如表3.4。究竟使用哪种软比特定义方式可跟据具体的应用,用 户可以进行自行配置。修改后,建立一张映射表,把表中后两种形式映射成偏移
二进制形式,这样,码间距计算式就不需要进行调整。 表3.4三种软比特定义对照表
偏移二进制[2】[1】[0】 强l
11l 110 10l

符号能量型【2】[1】【0】
1ll 110 101 lOO 000 OOl 010 01l

二进制补码[2】【l】[O】
100 10l 110 111 000 001 010 0ll

弱1 弱0

100 0ll 010 00l

强0

000

第29页

国防科技大学研究生院硕十学位论文
3.4.3

加比选单元与并行化算法的研究 加比选蝶形单元组把分支度量、路径度量、幸存路径的选择和判决比特的生

成等功能集中到一起。本文中加比选单元是按基二网格图组织的,即由四个加法 器和两个比较器组成。加比选单元的两个加数一个来自路径状态度量单元,另一 个来自度量存储器中存储的当前状态的度量值,他们相加的结果经过比较器的判 决选出较小的存入另一块度量存储器中。加比选单元同时还为路径存储和输出模 块存储的路径信息提供依据【l引。其具体的硬件实现框图如3.8所示。

图3.8加比选单元具体电路设计框图
第30页

国防科技大学研究生院硕十学位论文

图3.9给出了蝶形单元的示意图。其中,实线表示下一输入位为1,虚线表示 下一输入位为0。当下一位输入0时,转移到下一状态,状态位全部右移一位,最 低位舍弃,最左端高位补零,所以,新状态为上一状态的1/2;同理当下一位输入 l时,状态位全部右移一位,最低位舍弃,最左端高位补1,故新状态为上一状态 的1/2+N/2(其中N为所有的状态数)。到达后一个状态有两条路径,加比选模快的 功能便是先分别计算两条路径前一状态度量值与该路径输出度量值的加和,然后 选择度量值和较小的,并选定那条路径为到达该状态的最优路径保存下来。

一代表输入o_———+
……一?f℃表输入1……+
图3.9蝶形单元示意图

对于本(2,l,7)译码器,每次运算有64条幸存路径,因此会生成64条路径信息 比特。由于ACS单元采用单蝶形Viterbi算法,所以需要32个ACS单元,每个 ACS单元产生2个判决比特。所以,运算一次会产生64个度量值和64个判决比
特【2l】。


常用的实现方法有串行实现、并行实现和串并结合实现。串行实现中可以仅 利用一个ACS单元串行实现各个状态的路径度量值的更新,大大节省了硬件资源, 但是这种方法也有比较明显的缺点,比如译码器吞吐量低和时序较为复杂。若实 现本文中约束长度K=7的译码器,需要有2K-l=64个状态,由于是串行实现,仅 有一个ACS单元,这样每接收一个码字至少需要64/2=32个主时钟周期才能完成 处理过程。在具体实现的过程中,各个内部功能单元还需要流水处理,这样32个
处理时钟周期都不够了,并且如此实现将会使内部时序相当复杂,需要作精密的 控制,就大大增加了硬件设计的工作量。

在吞吐量和硬件规模上进行折中考虑,可以考虑用串并结合的算法来实现 Viterbi译码器。比如,对于本译码器,我们还可以采用4个ACS单元来实现这64 个状态的路径度量的更新操作,这样译码器每接收一组码字,需要至少64/4/2=8 个处理时钟周期来完成路径度量值的更新。根据具体情况,我们就可以综合考虑
选择ACS单元的数量。

最后一种方法,即用全并行的算法来实现Viterbi译码器,需要有相同状态数 的ACS单元在一个码率时钟周期内完成所有状态的路径度量值的更新,就大大提 高了Viterbi译码器的译码吞吐量。由于整个系统只需一个码率时钟就可以工作,
第31页

l司防科技大学研究牛院硕士学位论文

时序也大大简化【2 2|。唯一的缺点是资源耗费较人。

但是随着VLSI工艺的不断提高,FPGA制造技术的飞速发展,芯片规模问题 已经不是系统实现的瓶颈问题,这样就解决了并行算法硬件资源耗费大的问题。 同时,本IPCore,K=7的值也不是很大,这样,在具体设计过程中,我们采用全
并行。

本应各采用两组寄存器乒乓交换法来实现(即两组寄存器分别先后作为输入和 输出),由于采用全并行方式,让所有状态并行同时比较,那么,一拍之后,就能 比较出全部的结果,这样所有状态度量值寄存器可以同时更新,大大提高了效率, 而且也仅仅只须用一组状态寄存器【2引。
3.4.4路径更新单元与度量值正常化

在加比选单元处理完毕的同时,调用PMU模块对每个状态的度量值和路径信 息比特及时进行更新。由于在加比选单元中,度量值要进行累加,很有可能出现 累加值超过一个固定的阀值过大溢出的情况,所以在状态度量值更新的过程中, 如果有上述情况发生,那么就要在适当的时候同时对所有状态的度量值减去一个 统一的量值,这个操作便称之为度量值正常化。
具体Verilog HDL实现过程中,我们采用一位预溢出标志位(为所有状态度量

值最高位的与),初始为0。每个状态度量值设为9位,最高位(第9位)初始时均为 O。当在状态值累加过程中所有状态的度量值全部超过255时(即第9位为1)那么就 规定该状态的度量值发生了预溢出,当所有状态度量值都发生预溢出时,那么预 溢出标志位为1,进行度量值正常化,所有状态度量值寄存器最高第9位均被翻转, 变成0,其它位不变,修改后继续参与到后续的运算。 如果在译码过程中,有很高的正常化比率,那么很有可能由于非同步而造成
了失真。因此,正常化信号可以用来检测Viterbi译码器的同步问题。

ACSU(力W比选单元)和PMU(路径更新单元)在一起就完成了幸存路径选择的功
能。

3.4.5幸存路径管理单元与截短法 前面介绍的ACSU模块在选择好最优路径后,都会有路径转移标志位,SMU 模块便是主要存储这些标志位,经过一定的延迟,按照先前所存储的幸存路径信 息,搜索出一条可能性最大的译码路径,并以正常顺序输出译码结果。 关于幸存路径管理的传统方法有两种:路径回溯法和寄存器交换法。 路径回溯法是用RAM来保存针对每个状态的幸存路径的信息,当到达译码深
度时再从当前最佳状态回溯出一条幸存路径并得到译码。这种方法硬件结构相对
第32页

同防科技入学珂f究牛院硕士学何论文

简单,易于管理和控制,但是每到译码深度就要进行回溯操作,故译码时延较长。 所以,关于回溯法,人们还提出了一些改进方案,比如单指针回溯法、k指针回溯
法和混合回溯法等等。

寄存器交换法在概念理解上较好理解,实现起来也相对容易,主要是采用专 用寄存器作为存储主体,利用大面积寄存器矩阵和复用器与ACS单元连接,将针 对每个状态的幸存路径都保留下来,等到达译码深度时再顺序由当前最佳状态输 出译码,这种算法利用数据在寄存器中的不断交换,通过更新幸存路径实现信息 译码【241,所以速度快,译码时延小,但是由于在更新幸存路径时需要对每个状态 的内容进行读取和写入,会带来较大功耗而且占用的面积也较大【2引。 根据卫星通讯的需求和特点,自研IPCore采用的是寄存器交换法。根据上文 的Matlab模拟结论,截短法切实可行,所以,这里仍采用截短法。那么首先为每 个状态设置长度为∥o】的幸存路径寄存器和当前操作位计数器rViterbiCounter,具 体操作流程如下: 1)rViterbiCounter初始值为0。 2)当rViterbiCounter小于l时,Viterbi译码每步进一步,幸存路径寄存器在 rViterbiCounter位置存进一个路径标志位,并且rViterbiCounter递加1。若接收到
译码结束信息,过程结束。

3)当rViterbiCounter等于l时,即当幸存路径寄存器组存满l时,Viterbi译码 再步进一步,rViterbiCounter则复位成0,且新一步的路径标志位存储到寄存器组 的第0个位置,强制把在该位置先前存储的幸存路径标志位输出,并且译码输出 使能位为高有效。若接收到译码结束信息,过程结束;没有,则跳至过程(2)。 上面过程示意图如图3.10所示。
幸存路径寄存器

[[[口]]]一一一一一一一一口
rViterbiCounter 1 2 l

(~
图3.10截短法实现示意图



经验和分析表明,在,为M(卷积码约数长度)的5倍以上时,在k时刻的所有 2M条幸存路径,实际上在缸,时刻,就已经合成一条了‘101。因此,当为某个状态寄 存了,个以上路径值时,可以强制把第一个输出,以此类推。在2M条幸存路径中,
可以选择第1路作为输出。

在自研IPCore中,比延迟深度)的值可取36,54,72,90,108,用户可以自 行配置。,值越大,所有幸存路径在k时刻重合成一条的概率就越大,误码率就越 低,但是综合后所用到的寄存器就越多,面积也就相应变大。
第33页

里堕型彗查茎至垒竺些矍圭茎竺篁奎
3.4

6误码率计算单元与译码正确性评估 误码率计算模块能够监控传输通道上的误码率如图3 ll所示。Viterbi译码器

译出的数据首先通过卷积编码器重新编码,即获得经过Viterbi译码纠正后的数据 的卷积编码,拿这组数据和经延迟后的输入数据进行比较,如果相对应的两位数 据不一样,那么就报错,同时误码计数嚣加1 p9l。如果Viterbi译码器没有正确的 进行译码就会报错。并且,由于Viterbi泽码错误所引起的误码率要比由于信道不 好产生的误码率的可能性太的多,因此,BER输出是指示VitcrN译码是否正确的 一个重要评估参数。但是,最终的正确性测试,还要等测试完成后拿译码结果和 原始数据进行比较【“I

谩码

L1…码卜 —L叫匕兰
图3
II

个数 输}I;

误码率模块内部模块示意图

我们把误码个数输出定为16位,所以最大错误数也就是216.1,如果更多的错
误发生了,超过了该上限,那么规定I]ER的所有位被置为全1。

3.5功能仿真测试


51整体测试波形 用ModelSim 6.0进行仿真测试时,译码IPCore采用文件输入,译码结果也输

出到文件,再与原始数据进行比对。 先将卷积码凿成3/4码率,然后输入到自研IPCore进行Viterbi泽码,敬交织 深度为36,用ModelSim6 0进行仿真。开始阶段的波形图如图3.12所示。每个引 脚的功能及功能参见表31、表3 2的模块输入输出引脚图。

幽3

12

ModelSim仿真波形图 第34页

国防科技大学研究生院硕士学位论文

我们可以看出:

1)ProStart在刚开始不久有一个跳变的高电*使能信号,指示Viterbi译码进 程开始。 2)Normalized信号一直为0,说明暂时没有累加值过大溢出的情况。 3)再过一定时间后DecodeData和DecodeDataEnable信号开始有规律的变化,
说明译码已经开始逐步译出结果。

由于输入数据比较多,仿真时间比较长,为了直观方便,又整体抽象出来的
模拟时序示意图如图3.13所示。
饼’REv cIX

_]厂]几r]厂]厂]厂]厂]厂]r]!门厂]r]r]r]n几r]厂l n几r

OPRE'V_RST_N

—]I

DPREV_B_SeflalD越aln

■■[叵X五X哑X
厂]


111

X嘲Iilll




000




111



000

X:

髀戆V疆ser}alD越旧ble
DPREV W_ProStat

。……



II
1)0000000000000000

DPREV_B

B强Countef

DPRE'V B_Oeco(:leDala

II厂]厂]厂]——
II厂] 图3.13仿真模拟时序图



呼艇V

B_De∞如O豳£∞№

L—厂

说明: 1)当DPREV 据,之前为无效。
2)DPREV B BERCounter始终为0,可以间接判断译码基本正确。
B RST



N下降延触发时,DPREV



SerialDataln开始接收数

3)过一段时间后,DPREV



DecoderData和DPREV

B DecodeDataEnable

有规律的变化,说明已经开始译码。
3.5.2利用MFC编写直观数据比较程序

由于在上面的仿真过程中,译码结果要输出到记事本文件,上万数据人工比 较起来几乎不可能,于是考虑用Visual C抖语言编写比较程序,并且为了直观,编 写图形界面,以验证译码的正确性并统计误码率。其用户界面如图3.14所示。 该程序可以支持两个tXt文本中不同字符的比较,统计出比较数目、误码数和 误码率。首先选中两个要比较的文件,确定路径后,点击显示文件,就会在中间 两个对话框中分别显示。在第一个文本框中选中一串字符后,可以自动在第二个 文本框中自动匹配到相应位置的字符串,并也加亮显示。同时,在文本框上部的 说明框中可显示统*峁ㄑ≈凶址谧茏址械奈恢茫≈凶址母 数。在最下面的波形框中,也可绘出相应的波形。把鼠标放到波形框中,在说明
第35页

国防科技大学研究生院硕十学位论文

框中还能显示所点的波形在选中字符串中的位置。点击比*磁ィ谟疑辖堑慕
果窗¨中会显示两文本全部数据的比较结果。

露蕊哥型叫 毫嚣篡o, 藤蔼画』叫
i}#mI

ii女#l旧嚣目:“∞咖]

塑堂



0∞0】i’0】00looo…1

㈦㈦㈦幽豳阑㈣㈣
10】oooI001t1000010…iiL…000∞101…1110000i00.口011l L010111111[10000…11 1∞…1 10…1㈣1 l…01110 L000…1 00101100i011±010001111【100}0…ii
1 101 0110。010010


…㈨M111110110111011…1110㈣1110”001011”111100110101011001000…1110001j

图3 14误码率统计比较程序界面

对f万原始数据进行卷积编码,然后进行凿孔,凿成3/4码率,通过自研IPCore 译码,升运用该程序将译码结果与原始数据进行比较,在统计处可以看出,在没 有噪声的情况下,译码完全正确,即误码率为O%。

3.6卷积编码器
3.6

1卷积编码的选择 为配合研究Viterbi译码的性能测试,又编写了基于Verilog HDI,的卷积编码

器。根据卷积编码的定义,它可以表示成(n,k,K)的形式。一般来说,衡量参数有两 个,一个是码率R-n&;一个是约束长度K。随着R取值的增大,译码性能会逐渐 变好,但是同时也要考虑信道容量与传输效率,所以R的值也不能无限制的增大。 同时,随着K值的长度增加,译码的误码率会越来越低,但是通过理论分析可以
第36页

同防科技大学研究生院硕士学位论文

测算出,译码器的复杂性随K呈指数增长。所以无论是R还足K都需要考虑众多

因素作出均衡,才能得出结论。在具体选择卷积码的同时,除了考虑上述因素外, 还应该考虑如何减小恶性误差的传播。在这方面,可以借助计算机来搜索具有良 好性质的好码。本文正是利用计算机当辅助工具,确定了采用(2,1,7)卷积编码。同 时(2,l,7)卷积编码也是CSSDS的一种推荐标准,已被各国广泛应用于卫星遥测信
道。

这种码的码率为R=l/2(且p--路输入,两路编码输出),约束长度为K=7,生成
多项式为:G1=1718,G2=133s。将Gl,G2写成多项式形式即为:

G,=,+D+∥+J矿+D6;G2=I+DZ+D3+DJ+D6
3.6.2编码器的硬件设计与仿真实验 编码器硬件实现图如图3.15所示。
二I =I

XOR

——砰—虹} …哑*…岖蛩—{固一一咽…一
I........_J

引XOR l
=l

图3.15卷积编码(2,1,7)硬件实现框架图

可以看出,OUTl为从左数(包括输入位)第l、2、3、4、7位的异或,用1表 示相应位,则生成多项式可以表示成(1111001)2;同理,OUT2的生成多项式为
(10i
101

1)2。通常合起来,用8进制表示为(171s,1338)即为上节中的两个生成多项

式Gl,G2。 用Verilog HDL语言实现该编码器的设计,总输入输出框图如图3.16所示。

(2,1,7)卷积码 编码器模块

le———◆
【1:0卜◆

图3.16(2,1,7)卷积编码模块引脚框图

编码模块仿真图如图3.17所示。
第37页

国防科技大学研究生院硕士学位论文

图3.17编码部分仿真波形图

说明:

clk为时钟信号,可以看出,其随着时间的推移,有规律的做锯齿变化。

reset为移位寄存器Shi虬Reg的复用信号,当reset被置成1时,寄存器Shifl_Reg
被置成全零。 en为输入使能信号,高电甲时代表输入数据有效,在波形巾,可以看出其一 直为高电?F,说明这段时间输入数据一直有效。 data为待输八编码器的原始数据,将要根据接收到的数据进行卷积编码,上面 波形为从原始数据文件中读出的数据。 enable为卷积编码输出使能信号,当为高电*H、J,表示输出的译码数据有效。
data

ell为卷积编码后的输出数掘,两位,分别为1 33路和17l路的输出。

3.7本章小结
本章主要介绍了在用Verilog硬件描述语言实现Viterbi译码时,在细节上所做 的系列改进,从而进一步提高译码速率,减小了面积。并分节对并模块的实现 和改进过程作了比较详尽的介绍。义利用ModelSim60,对该IPCore进行了模拟 仿真实验(又叫做前仿真1,来验证电路功能是否符合设汁要求,其中发现了设计中 的许多错误,并逐改正,系统的设计可靠性也随之大大提高了。同叫,为了配 合译码模块的测试,又编写了卷积编码模块,并作了仿真测试。

第38页

国防科技大学研究牛院硕士学位论文

第四章Viterbi译码器真实系统下的测试
无论是Matlab还是Verilog HDL对Viterbi译码的实现,都只是停留在模拟和

仿真阶段。设计出来的IPCore是否可行最终都要利用FPGA经过实际系统的测试 与检验。而算法级描述以及RTL级描述是为了顺利进行实际系统测试的两个必要
的步骤。
4.1

FPGA一般设计流程

首先,我们来看看FPGA设计的一般流程,如图4.1所示【3l】。

图4.1

FPGA设计流程副311

各模块具体说明: 1)电路设计与输入:
第39页

同防科技大’≯研究牛院硕士学位论文

电路没计与输入时通过某些规范的描述方式,将电路构思输入到EDA工具。 为了提高开发效率,增加对己有开发成果的可继承性,我们采用Verilog HDL。它 是硬件描述语言的一种,用于数字电子系统设计。设计者可用它进行各种级别的
逻辑设计,可用它进行数字逻辑系统的仿真验证、时序分析、逻辑综合。它是目

前应用最广泛的一种硬件描述语言。 采用Verilog硬件描述语言最大的优点是其与工艺无关性。这使得工程师在功 能设计、逻辑验证阶段,可以不必过多考虑门级及工艺实现的具体细节,只需要
根据系统设计时对芯片的要求,施加不同的约束条件,即可设计出时序电路[321。

实际上这是利用了计算机的巨大能力并在EDA工具的帮助下,把逻辑验证与具体 工艺库匹配、布线及时延计算分成不同的阶段来实现,从而减轻了人们繁琐的劳
动。

本文采用自顶向下的设计方式。现代集成电路制造工艺技术的改进,使得在 一个芯片上集成数十万乃至数千万个器件成为可能,为保证设计一个如此大规模 的电路而不出现错误,往往采用层次化、结构化的思想。一个完整的硬件设计任 务首先由总设计师划分成若干个可能的操作模块,编织出相应的模型(行为的或结 构的),通过仿真加以验证后,再把这些模块分配给下一层的设计师。这种设计模

式称为自项向-Fi毋,t(Top.Down)t33J。
本文中首先从系统级设计开始,做了很多模拟和有价值的实验,然后将总系 统分成卷积编码模块,调*獾髂?橐约耙肼肽?椋渲幸肼肽?橹杏趾淇谆 复模块和标准码率Viterbi译码模块,后者又分成分支度量模块,加比选模块,误 码率统计模块,幸存路径管理模块等。
2)功能仿真:

功能仿真也被称为前仿真,我们通过专用的仿真工具ModelSim6.0来验证电 路功能是否符合设计要求,以此发现设计中的错误,加快设*龋岣呱杓瓶
靠性。 3)综合优化:

我们将已经编好的Verilog代码用ISE9.1i进行综合,并进行优化,将设计输 入翻译成由与、或、非门,RAM和触发器等基本逻辑单元组成逻辑连接,并生成 网表文件供FPGA器件布局布线器进行实现。
4)综合后仿真:

检查综合器的综合结果是否与原设计输入一致,综合后仿真比功能仿真精确
一些,但由于只能估计门延时,不能估计线延时,因此仿真结果与布线后的实际 情况还有一定的差距。 5)实现与布局布线:
第40页

国防科技人学研究生院硕十学位论文

将综合输出的逻辑网表适配到具体器件上的过程称为实现,其最主要的过程 就是布局布线,布局是指将逻辑网表中的硬件原语适配至IJFPGA内部的固有硬件结 构上,布线则是利用FPGA内部的各种连线资源,合理正确的连接各个元件。


6)真实系统测试:

:将IPCore下载到HAPS.54开发板上进行*偻蚴菡媸迪低车模拢牛倚阅懿馐浴 其中,自研IPCore交织深度选108,3/4码率,测试信号为QPSK调制,信号速率768K。 并与Altera公司的同类产品和CMD600进行比较。其中,Altera公司的IPCore交织深
度为128,比我们稍大。

7)调试与加载:
设计开发的最后步骤就是在线调试或者将生成配置文件写入芯片中进行测

试,示波器和逻辑分析仪是逻辑设计的主要调试工具,对于相对简单的设计,可 以使用EDA工具中自带的在线逻辑分析程序进行调试【3¨。 由于Top.Down的设计方法是首先从系统级设计入手的,因而从顶层进行功能 划分和结构设计。系统的总体仿真是项层进行功能划分的重要环节,这时的设计 是与工艺无关的。由于设计的主要仿真和调试过程是在高层完成的,所以,如果 能够早期发现结构设计上的错误,就能避免设计工作的浪费,同时也减少了逻辑 仿真的工作量。自顶向下的设计方法很方便地从系统级划分和管理整个项目,使 得几十万门甚至几千万门规模的复杂数字电路设计成为可能,并可减少设计人员i’
避免不必要的重复设计,提高设计的一次性成功率。
4.2

HAPS.54开发板

我们所做的FPGA实验便是基于HAPS.54板,它是一款多功能FPGA开发板, 可以用来硬件/软件联合设计。它适合所有ASIC原型设计的需要,包括硬件/软件 设计联合开发等。由于其灵活设计,只要更换子板和I/O用户子系统就能够使同一 块板子在几个工程中重用。考虑信号完整性、速度和其他关键因素,在设计时母 板采用26层电路板压制技术,最大限度地能够兀显了其性能。其实物图及其接口
简介如图4.2所示1341。

HAPS一54母板配备了4个Virtex 5的FPGA开发板,并在板的正面配有24个
HapsTrak

II终端连接器,背面配有24个接插件连接器。HAPS.54板子需要一个+5V

的信号驱动,所有其它信号驱动,均由板内生成。 一个HAPS系统至少要由一个母板组成,所谓母板即一个装配有几个性能最 好FPGA的容器。高质量的I/O和内部FPGA连接器被封装在一个70x50的矩阵 中,每一个FPGA芯片都连接一组这样的连接器。每一个连接器都有特定的电源 和时钟信号引脚。FPGA板子上特定的时钟引脚连在总时钟信号上。时钟信号既可
第4l页

国防科技大学研究生院硕士学位论文

以被外部信号叉可以被FPOA内部时钟信号驱动。固定的总线把几个FPGA连在 了一起,更宽的总线通过低代价的内联模板也很容易实现。普通的子板,像内存 板和接口板子,很容易连接在任何一个连接器上,子板的规格也是严格限定的, 母板上也没有多余的连接器。母板连接接LJ跟子扳一样,这意味着母板之间也可 以通过标准的内联板子相互连接。由于所有的母板在背面都有配对的连接器,它 们就可以像搭积木一样堆在一起。所有接口符合HapsTrak标准。

蠡;;

看蔫嚣囊黜



图4.2



臻璞|
4.3综合结果



HAPS.54开发板母板实物图及其接口简介㈣

4.3l资源占用 译码模块DepuncturedRegExViterbi在使用Xilinx
ISE 9

li软件进行综合,选用

Viaex5进行模拟,选用器件为:5vlx330ffl760一l,综合结果如下。
第42页

国防科技大学研究生院硕士学位论文

1)当延迟深度为36时,综合后具体资源占用表如表4.1所示。
表4.1延迟深度为36时硬件资源占用列表
Slice Logic Utilization Number of Slice Registers Number of Slice LUTs Number used
as

3000 4952 4952 4955 1955 3

out out out

of of of

207360 207360 207360

1% 2% 2%

Logic

Number of Bit Slices used Number with Number with
an an

unused Fl ip Flop unused LUT

outof

4955

39% 0% 60%

out of

4955 4955

Number of fully used Bit Slices Number of lOs Number of bonded IOBs Number of Block RAM帆ⅧFo Number using Block RAM only Number of BUFG/BUFGCTRLs

2997 29 29 1 1 2

outof

outof Out of

1200 288

2% 0%

out of

32

6%

2)当延迟深度为54时,综合后具体资源占用表如表4.2所示。
表4.2延迟深度为54时硬件资源占用列表
Slice Logic Utilization Number of Slice Registers Number of Slice LUTs Number used as Logic Number of Bit Slices used Number with Number with
an an

4152 6208 6208 6214 2062 6
out

out out

of of

207360 207360 207360

2% 2% 2%

out of

unused Flip Flop unused LUT

outof of

6214

2% 0% 66%

6214 6214

Number of fully used Bit Slices Number of IOs Number of bonded lOBs Number of Block RAM/FIFO Number using Block RAM only Number of BUFG/_BUFGCTRLs

4146 29 29 1 1 2

Outof

outof out of

1200 288

2% 0%

out of

32

6%

4.3.2译码速率

同样使用上述环境和器件,译码速率的相关结果如下。 1)当延迟深度为36时,模块综合后的速率结果如表4.3所示。
表4.3延迟深度为36时综合后的速率结果
Minimum pedod Minimum input arrival time before clock Maximum output required time after clock
5.168ns 4.282ns 5.121ns

Maximum Frequency:

1 93.5 1 5MHz

第43页

国防科技大学研究生院硕十学位论文

2)当延迟深度为54时,模块综合后的速率结果如表4.4所示。
表4.4延迟深度为54时综合后的速率结果
Minimum period Minimum input arrival time before clock Maximum output required time after clock
5.722ns 4.282ns 5.121ns

Maximum

Frequency:

1 74.777MHz

4.4具体测试
首先,我们利用信号发生器产生M序列或固定序列作为数据源,之后将之进

行卷积编码,采用QPSK调制,然后进入模拟信道,并加入高斯白噪声。之后,
采用两种不同的解调方式,一种为CDM一600(自带Viterbi译码功能),一种用QPSK

解调器。在QPSK解调之后,分别用两个IPCore进行译码,一个是Altera公司的
(V4.2),一个是我们自研的待测IPCore,并对译码结果进行比较分析。由于比较的

是三个IPCore的译码性能,非译码速率和占用面积,所以是否在相同工艺和器件
上比较不影响结果。具体流程如图4.3。

图4.3真实系统测试框图

利用FPGA开发板HAPS.54对自研IPCore进行验证,其Chipscope截图如图 4.4所示。可以看出一定时间后译码数据和译码使能信号有规律的变化,说明译码
已开始。

圜}Waueform.DEV:3 Mpl)e、dce3(XCS~q_X330)UNIT:O MplLAO(ILA)豢善誊蓦鬃誊囊善豢善誊!豢善誊蓦囊攀;
Bus_fsignal
…CLK RST瑶inv X 0

130

440

150

160

170

180

190

200

210

220

.I.。..1.。..I.。.。I....I.。..I。...1.。..I。...1....I..

0 0

0 0

o一日既屺。吼ter
BERDone ,DecodeData DecodeDataEnab.

000 000 0 0 0 0 0 0



n_ n n『1 n f1 n_

山H『I舢n
HAPS一54模拟ChipScope软件截图(起始时) 第44页

图4.4

国防科技大学研究生院硕十学位论文

三个模块测试结果误码率比较如表4.5所示,得出结论: 1)当Eb/No大于4.5dB,小于5.0dB时,自研的Viterbi模块性能接*CDM.600 和Altera公司提供的Viterbi
公司提供的Ⅵterbi IPCore。
IPCore。

2)当Eb/No大于5.0dB时,自研的Viterbi模块性能优于CDM一600和Altera 3)在卫星通信中,信噪比通常比较高,所以自研IPCore更适合于深空卫星通
信。
表4.5三个IPCore译码性能对照表
Eb/No(dB)
7.O 6.O 5.5 5.O 4.5

CDM.600
8.0E一7 1.4E一5 1-3E一4 4.9E一4 1.5E.3

AlteraViterbi IP 2.4E.7 1.3E一5 7.73E.5 4.27E一4 1.79E.3

自研模块
2.4E.7 1.24E一5 7.7lE一5 4.45E.4 1.88E一3

4.5本章小结
本章首先介绍了FPGA的实现流程,在上两章的系统级模拟,RTL级仿真的基
础上,又利用Xilinx ISE9.1i软件对已编好的IPCore进行综合,生成逻辑网表,综

合分析了其性能与占用的面积。之后利用HAPS.54板子进行FPGA实验,搭建了 完整的真实测试环境,从编码、调*獾鞯叫诺来洌ü庖惶淄暾牟馐粤 程,将自研IPCore的测试结果与目前其它公司同类产品进行性能比对。

第45页

同防科技大学研究生院硕十学位沦文

第五章级联编码的研究
为了进一步增强卷积编码的纠错能力,通常采用将卷积编码作为内码与RS编 码进行级联,DVB.S标准便采用了这种级联技术。同时为了增大纠成片突发错误
的能力,又可以在两个级联编码之间加入交织技术。所以,为了进一步增加卷积 编码与Viterbi译码的实用性,本章又做了级联编码以及交织技术的模拟和研究。

5.1级联编码
为了构成更强有力的差错控制编码系统,通常把两个或多个简单纠错编码联
合起来,一般有两种方法,乘积编码和级联编码。

级联编码与乘积码具有极大相似性,但与乘积码的主要区别在于,级联码的 两个组成码通常是在不同的域上进行编码的。一般离信道较远的编码/译码器称为 外码;而离信道较*的编码/译码器称为内码。一般外码是GF(qk)上的一个(N,K) 码,每个外码的输出码元都是GF(q。)中的一个元素,它可以用GF(q)上的k维矢量 表示。外码输出的k维码元符号作为信息位再用GF(q)上的(n,k)码进行内码编码, 内码的码子符号是与调制器和信道相容的。内码一般是二进制的,外码常取GF(2k) 上的RS码。从外码系统来看,可以把内码编码,信道及内码译码看成是一个GF(qk) 域上的一个超信道。如果我们把外码看成一种列码,则内码扮演行码的角色,反 过来也可以。这样级联码与乘积码的相似性就更强了【41J。 级联码的译码过程是按照从内到外的顺序进行的,即每个内码字先分别进行 译码,而每个内码字的估计值(即内码译码值)再看作外码字的一个符号(GF(q)上的 k维矢量)。值得注意的是,当内码译码发生错误时,这个错误是k维矢量中的一 位分量发生错误,还是所有分量都发生错误并不重要,因为它们都是被认为外码
的一个码元错误。因此,外码被认为具有纠突发性错误的功能。 典型级联码的内码被设计成低速率、具有强纠错能力的码;而外码则是高速

率的码,通常是RS码。

5.2级联码的模拟
DVB—S标准便是应用Viterbi作内码,RS作外码的级联编码。DVB.S起初是 由ETSI(欧洲电信标准委员会)制订的数字视频广播卫星传输标准。目前,应用这 一标准传送视频节目的国家和地区己远远超出欧洲的范围,并且还在不断增加。 DVB.S以MPEG2传输流(TS)为传输格式,经过信道编码(包括基带整形)和D/A 转换,再经由QPSK调制和上变频送入卫星信道。DVB—S信道编码系统包括信号
第46页

国防科技人学研究牛院硕士学位论文

随机化(能量扩散)、RS编码、卷积交织、卷积编码及删余(多删余码率)和基带整形 等功能模块13引。
RS编码是一种非二进制的BCH编码,具有极强的纠错能力,随机错误和突

发错误都能够进行纠正。根据Singleton限界,线性编码的最可能的最小距离等于 校验位数数目加l,于是RS码便达到了Singleton限界。在这个意义上RS码是最
佳、最有效的。

仿照DVB.S系统,我们设计的整体级联框架图如图5.1所示。

图5.1级联码设计整体测试框图

在不加交织的情况下,同一组原始码经过卷积与RS级联编码后,再进行Viterbi
译码和RS译码,误码率明显降低。

1)当卷积编码中码率R_1/2时,其模拟参数对比如图5.2所示。

………。。:…。……:

.i兰沁蠹…。
q≮

……。熏蕊k!
。委


乳;;迨…。
.朱!!≮一
……,…,:i………;。 ……■………-……-

&i巍
;;;;i:≥ 童i}li¨IlIl

“十一Vaerbi

———●一RS+VtlaCai
—o—Rs+交织+v醅fbi

国防科技大学研究生院硕+学位论文

2)当卷积编码中码率R=3/4时,其模拟参数对比如图5.3所示。

~,



一、上



‘夸.~。 ~’~~。


V ’-?‘j

啭。..

‘i


…~、 ≮



象’、











、亭


X一.

:N : :
. ●







…’弦…气一








, j

r…21壤一

.、卅。小

一扣一RS+Viterbi

-0-一RS饺织+Viterbi

图5.3

R=3/4时三种纠错编码误码率比较图

5.3块交织技术的引进
在许多实际应用中,信道往往是有记忆的,这就是说,假设x=(Xo,五,…,Xn一,)
n-I

和,=(ro,‘,…,,:l一,)分别表示信道输入、输出矢量,如果P(r

x)≠几l"(rj
j=o

Xj)则我

们说信道是有记忆的,这时信道上传输的符号序列不是相互独立的随机事件。有 记忆信道的一个重要特征是差错突发产生,也就是要么信道不出现错误,要么错 一片。物理信道的这种记忆性,可能是由许多不同的原因造成。例如,无线信道 上的衰落、突发噪声或故意人为干扰,都能造成信道的突发错误;还有,信道时 间扩散所导致的码间干扰和磁盘或光盘表面上的瑕疵等,也是造成信道有记忆性
的原因lloJ。

卷积编码和RS编码都主要针对无记忆信道,在这种信道上差错是分散、随机 出现的。当把这些编码技术应用于有记忆信道时,由于有记忆信道偶尔发生的成 片突发错误将导致这些码译码崩溃,这时编码的性能将远不像我们在基于无记忆 信道下所预计的那样,所以,我们考虑采用交织技术。交织是一种非常简单的操 作,它只不过是在进入信道传输之前,对编码输出的符号序列进行有规律的重新 排列、置换而已。在接收端解调器输出的符号流必须再进行解交织,恢复原来编 码输出的符号流顺序。交织的目的是使到达译码器的同一分组码字中的各个码元 符号在信道上独立传输。
第48页

国防科技人’学研究牛院硕士。≯位论文

在这里我们采用块交织技术。所谓块交织,像通常的分组码一样,假设我们

有一个(n,k)的编码器。将连续的Dxn个码字Xi(江l,2,…,D)写入一个有D行、11
列的矩阵块。按行方向写入D个这样的码字,但信息序列的传输是按照列的顺序 进行的,即先传输第--N,然后第二列……直到整个矩阵传输完毕。经过突发差 错信道的传输,在接收端把解调器输出,不管是软判决的实数值还是硬判决的码 元符号,都按照传输的顺序,一列一列地写入另外一个矩阵,直到矩阵填满。解 交织时则是按照一行一行的顺序进行的。块交织示意图如图5.4所示。
J1

"--'-'11"

x: x;

X; x:

x:一l x:一l

工2—叫卜

D×n的矩阵

x:

x?

xol
图5.4块交织示意图

由上图我们可以清楚地看出,信道上任何长度不超过D的突发错误都被分散 在不同的码字中。参数D被称作交织深度,当D足够大时,信道就被改造成独立、 同分布的无记忆信道了。 设计的帧组成方案要求如图5.5所示。

图5.5块交织帧组成方案模块图

首先随机生成的十进制数212个分成一组,然后将之进行(244,212)的RS编码, 得到244字节的RS码流,组成一个编码块。为了增加交织的效果,将4组这样的
第49页

国防科技大学研究牛院硕十学位论文

(212,244)RS编码块组合成一大组,共976字节(7808比特)一起进行交织。 在这里,我们取D=128,n=61。即我们把7808比特的数据填到128x61矩阵 当中去,然后进行交织。 再次利用Matlab软件,模拟有记忆物理信道上的片状错误,并使用交织前后 的结果进行比较。 1)当不采用交织时。 实验: 先随机生成四组0到255之间的数据,每组有212个数。分别经RS编码后, 将四组数据合并成一组转成二进制数后进行Viterbi译码。假设在信道传输过程中, 没有发生错误,这样,在Viterbi译码之后得到的数据,应该与RS编码后Viterbi 译码前的数据完全一致。设这时的码流串数据存储数组为data 假设在传输过程中产生了突发错误,即data
decoded

viterbi。由

于不采用交织,将该数组直接进行RS译码。为具代表性,更好的说明问题,我们
decoded

viterbi数组出现了连续的错

误,采用这样的模拟方案,就要对这个待传输的长度为7808的数组,从第一个比 特开始,每隔8位手动制造一个错误,即将该位取反。如此对Viterbi的译码结果 进行手动修改,表示由于信道传输产生突发错误,在一开始就产生,个错误位数的 情况。其手动修改程序如下:
forh--1:8-(8母D data—decoded—viterbi(h)=mod((data_decoded_viterbi(h)+1),2);
end

结论:

当,取小于等于16时,级联码的译码结果错误数为O。由于每组(212,244)RS 编码最多能够纠正16个字的错误。也就是说,当不采用交织时,级联码所能够处 理的片状错误最大值为16个码元。当,取16以上的数时,第一个RS译码块的实 际产生的错误字节数已经超过16了,那么在最后的级联码译码结果就会报错。 2)当采用交织时。 实验: 数据生成和RS编码的操作与不采用交织时一样,也分别对四组数进行RS编 码后合并成一个数组,然后将之转成二进制数组存入data rs中。之后要进按如下 操作,把它按行存入128x61的矩阵data
data
rs rs

matrix,然后按列读出后存入

converse中,再进行Viterbi编码、信道传输和Vimrbi译码,之后存在数组
viterbi中。然后对data
decoded

data decoded

viterbi数组进行解交织操作,得到

数组viterbi

result。

由于一组(212,244)RS码最多能够纠正16个字的错误,所以4组最多能够纠正
第50页

同防科技大学研究生院硕十学位论文

16×4--64字节,但这必须保证这64个错误字节均匀地分在4个块中,即每个块的 错误数不能超过16个。能纠正的最大错误比特数为64×8=512比特的错误。但这 必须保证这512个比特的错误仅来自出错的64个字节,即这64个字节中每个字 的8个比特位全部出现错误。仍然采用同样的方案,从第一个比特开始,每隔8 个位手动制造一个错误,即将该位取反。如此对Viterbi译码结果,RS的输入进行 手动修改。同样,,为错误的位数。
forh--1:8-(8木D data—decoded—viterbi(h)=mod((data_decoded_viterbi(h)+1),2);
end

结论:

?当,取512时,即交织后RS编码错误字数为512,但采用了交织的方法, 把这512个错误比*骄值搅耍锤霾煌目橹校⑶遥扛隹榈模保玻父龃砦蟊 特恰好连成了16个字节,即每个块有少于16个的错误,那么RS外码可以将之纠
正,故最后级联码的误码率为零。 ●当,小于512时,误码率仍为O。 ●当,取513、514、515时,级联码误码率分别为:0.02,0.212和0.0236

所以,通过模拟,我们可以得出结论,采用交织技术,可以有效地纠正在有
记忆信道的突发错误。

5.4本章小结
本章主要介绍了用Matlab7.0软件实现卷积编码Viterbi译码与RS编译码级联 的全过程模拟,并在其间加入了块交织操作,通过比较分析我们选择了最优的 128x61交织矩阵。通过模拟出来的性能曲线图,我们可以将Viterbi译码,级联编 译码,以及级联后加块交织操作的编译码性能曲线做对比,级联编码及块交织后
的性能优势一目了然。

第5l页

国防科技大学研究生院硕十学位论文

第六章结束语
Viterbi译码算法是卷积编码的最优译码,是一种最大似然译码。其硬件实现 结构简单,与卷积码共同组成一种有效的前向纠错,广泛地应用于深空通信、卫
星通信和移动通信领域中。

本文介绍了用寄存器交换法实现Viterbi译码算法的完整过程包括软件模拟和 硬件实现。在细节方面做了优化和改进,大大提高了译码速率和性能,并做了一 系列的研究和实验。又在真实系统中做了详尽的测试,通过分析比较得出了结论。 根据数字视频广播卫星传输标准DVB.S,研究了卷积编码与RS码的级联,又实 现了两个编码之间的块交织操作,并作了性能评估。主要贡献在于: 1)目前国内的相关研究,译码速率普遍偏低,只有几十兆。本文则采用了一 系列方法如截短法、用等效的思想简化启动过程、加比选计算并行化等,进一步 改进了Viterbi译码算法的性能,确定了译码器主要模块的体系结构,并比较和均
衡了芯片面积和误码率相互制约的矛盾。基于Virtex5芯片进行综合,最大输出频 率可达*200Mbps。

2)此外,目前国内的很多论文大都只针对特定的参数,不可配置【3711381,随着 现代通信的发展,对卷积码的译码速率和纠错能力提出了更高的要求,同时为了 增加硬件器件的兼容性、卫星的使用范围与运行时间,可重构计算也越来越受到 人们的青睐。本文利用Matlab软件实现了卷积编码Viterbi译码算法的全过程模拟 时,码长、延迟深度、输入输出位数包括生成矩阵等一系列参数都可以根据用户 需要做选择合适的参数。在用VerilogHDL实现时,软判决位数、交织深度等参数
在编译前可配置。 3)用Verilog HDL实现Viterbi译码后,接着用ModelSim6.0软件进行了仿真, 仿真正确后利用ISE 9.1i进行综合,并烧到HAPS一54开发板做FPGA实验。在此

基础上搭建了真实环境,进行BER性能测试。通过和Altera公司的同类产品以及 CDM一600的比较,我们发现,自研IPCore,在信噪比高于5.O时误码率更低,性 能更好,更适合于深空卫星通信。 4)在实际应用中,比如DVB—S系统中往往采用卷积编码与RS码的级联操作, 我们也对级联编码和交织技术作了较为深入的研究和并对模拟实验结果进行了分
析。

5)基本上可以说本文对基于寄存器交换法的Viterbi译码算法有了比较完整和
深入的研究与分析。

由于时间有限,在以上研究内容的基础上,后续研究过程可以考虑从以下几个
方面着手:
第52页

国防科技大学研究生院硕十学位论文

1)在对可配置性要求不是特别高的地方,可以采用ASIC投片的方式,对后 端的研究与开发本文还没有涉及。 2)同时我们在FPGA的设计中,可配置的参数还不是很多,比如Altra公司 通过团队合作历经三四年,推出了三个版本的Viterbi译码器IPCore,基本上大多 的参数可以调配,具有很好的通用性。同时,他们做的IPCore有个很好的应用模 块接口界面,大大方便了用户。这些都很值得我们学*。 3)本文所做的硬件上的优化,大都集中在细节方面,以后可以考虑在体系结 构层次上做整体的优化和处理。 4)在低功耗的设计上,还没有具体涉及,在设计完成后,可以考虑选择功耗 较小的器件来实现。对译码器的其它功能单元也可进行算法和逻辑结构上的优化,
进一步降低功耗。

5)在幸存路径管理中,仅限于了寄存器交换法的研究,对于回溯法还有待于 进一步深入的研究。

第53页

国防科技人学研究生院硕士学位论文





衷心感谢我的导师李宗伯老师,李老师严谨的治学态度、渊博的学识崇高的 师德和丰富的实践经验、以及诲人不倦的教学精神使学生深受启迪,并成为本人 克服各种困难、完成学业的不竭动力。在他的悉心指导下,我的学术水*以及独 立科研能力得到了明显提高。而且李老师勤勉的敬业精神和一丝不苟的工作态度 不仅使我在本课题的研究中受益匪浅,也使我对做人治学的许多道理有了更深刻
的理解。其广阔的胸怀、宽容的态度和*易*人的作风将永远是我为人处事的楷

模在论文的完成之际,衷心地感谢李老师两年多在学业上、生活上的对我的关心。 感谢刘衡竹教授,韩明华老师和徐邦建老师。在我们课题的研究过程中。从 一开始对我们通讯基础知识的补*,课题总体规划与设计到后来的研究方向与目 标的明确,都给予了我们很多的帮助与指导。当我遇到困难时给了我诸多建设性 意见和帮助,正是由于他们的指导,使我得以顺利地完成研究任务。 感谢张波涛师兄。他严谨务实的工作态度,一丝不苟的工作作风,责任心和 乐于助人的精神,都给我留下了很深的印象。并且,我课题的顺利完成与张师兄 的悉心指导与鼎立相助是分不开的。感谢赵恒和胡文敏师兄,你们在具体细节上 给了我很大的帮助。感谢教研室的巩绪明同学,特别是在作和RS码的级联过程中,
我们相互配合,使得工作进展得非常顺利。感谢课题组的刘冬培和马宏强同学,

我们一起学*,一起探讨,共同进步,相互的交流与启发都让我很为受益。 感谢计算机学员五队的队干部,我们的成长离不开你们的悉心关怀与培养教 育,并感谢计算机学院的领导为我们营造了良好的学*和生活环境,让我们安心 学*,认真搞科研。 感谢寝室中的同学所给予的关怀。 感谢我的父母和家人,无时无刻都在给予我默默无闻的支持。 最后,借此机会对所有为我提供指导、关心和帮助的老师、同学表示衷心的
感谢!

第54页

围防科技大学研究生院硕十学位论文

参考文献
Ⅱ 1J

陈测库.高效Viterbi译码器的结构与实现[D】.西安电子科技大学硕士学位
论文,2005.1.


1J

郑芳,徐明星.信号处理原理[M】.清华大学出版社,2003.8.

口p 1J

喻希.Viterbi解码器RTL级设计优化[J】,现代电子技术,2006.29(23):
137.140

H1J

张传达,李小文.一种实现3G卷积码Viterbi译码的优化算法[J】.广东通信
技术,2006(3):71—75.



孙晓岩.Viterbi译码器的FPGA实现技术研究[D】.哈尔滨工程大学硕士学位
论文,2003.

陋 1】1J

杨小牛,楼才义,徐建良.软件无线电原理与应用[M】.电子工业出版社,
2006.9.

p1J

周强.维特比译码器在FPGA中的低功耗研究【D].西南石油大学硕士学位论
文,2006.
Ranpara S.A low-power Viterbi decoder design for wireless communications

哆 1J

applications[J】.20th
377—381.

ann.IEEE International ASIC/SOC

Conference【C],1 999:

张荣兵.参数化Viterbi译码器的FPGA实现【D】.哈尔滨工程大学硕士学位
论文,2005.1. 【lO】 [1 1】

仇佩亮,陈慧芳,谢磊.数字通信基础【M】.电子工业出版社,2006:365-378.
Muhammad
Irfan,Syed

Muslim Shah,Ahmad

Khalil

Khan.Design
on

and

Implementation of Viterbi Encoding 2005: 234.239.

and

Decoding Algorithm

FPGA[J].ieee,



刘会红,高速Viterbi译码器的研究与实现【D】,哈尔滨工程大学硕士学位论
文,2004. WEI
CHEN.RTL of Viterbi

*

implementation

decoder[D].Master’S

thesis

performed in Computer Engineerin Linkopings University,2006.
r_L,-_L,_L

曹志刚,钱亚生.现代通信原理[M】.清华大学出版社,1992.
钾靶

林茂生,朱义胜.基于Matlab的纠错码性能测试仿真[J】.现代电子技术,
2003(23):1-4.
Viterbi A.J.Error Bounds

p_ L,_ L



for Convolutional Codes and an Asymptotically

Optimum Decoding Algorithm.IEEE,1 967.1 2:260—269.
r__L
● 1●-■●l■,_■●_■●l■



刘国芳,程乃*.一种维特比译码改进算法的研究[J】.遥测遥控,2006,27(1):
30—32

第55页

国防科技大学研究生院硕十学位论文

[18】

朱胜,杨华中,董在望.一种高性能uJ.重用Viterbi译码器的设计[J】.微电 子学,2005,35(2):217-220.

【19】 【20】

张英全,侯方勇.数字电子技术[M】.机械工业出版社,2001.4.
Jae Sun Han,Tae Jin Kim,Chanho Lee.High Performance Viterbi Decoder Using

Modified

Register
on

Exchange

Methods[J].Proceedings

of

the

2004

International Symposium

Circuits and Systems,2004.3:23—26.

【2l】

Michael

Hosemann,Rene Habendoff,Gerhard Fettweis P.Hardware—Software

Codesign of A 1 4.4 Digital Signal

MBIT一64

State-Viterbi Decoder for

an

Application—Specific

Processor[J].IEEE,2003:45—50.

【22】 【23】

蔡雄飞,林争辉,杨浩.高速Viterbi译码器[J】.电子测量技术,2005.3:14.16. 罗义军,李劲,章东*.一种Viterbi译码的改进算法[J],电路与系统学报
2003,8(6):122—125. P.Pribylov,Member,Alexander
Using Viterbi Algorithm I.Plyasun,A Convolutional with Register Code

[24】

Vasily

Decoder Design

Exchange

History

Unit[J].IEEE,2006.4:13-1 8. [25】
Boutillon E.Demassieux N.High Speed Low Power Architecture for

Memory

Management 【26】

in



Viterbi

Decoder[J].Proc.Of

IEEE ISCAS,1 996.04-283—288.

张绍军,王新志.用Verilog硬件描述语言实现Viterbi译码[J].空军雷达学
院学报,2002,16(4):61.64.

【27]

于贵智.全并行Viterbi译码器的FPGA实现[D].南京理工大学硕士论文,
2005.

【28]

张健,刘小林,匡镜明等.高Viterbi译码器的FPGA实现【J】.电讯技术,
2006.3:37.42.

[29】

熊磊,姚冬苹.基于FPGA的删除卷积码Viterbi软判决译码器的研究【J】.北
京交通大学学报,2004,28(5):36。40.
Xilinx Company.Viterbi Decoder

【30] [31】 [32】

v6.1【S】.Usr manual,2006.5.

王冰.高速Viterbi译码器的FPGA实现[D】.兰州大学硕士学位论文,2007. 牛晨曦,张辉.一种基于FPGA的Viterbi译码器[J】.现代电子技术,
2005,28(3):56-57.

[33】 【34】 【35】

夏宇闻.Verilog数字系统设*坛獭荆汀浚本┖娇蘸教齑笱С霭嫔纾玻埃埃常
Xilinx

Company.HAPS一54一DRAFT[S],2007.

陈丽苹.数字卫星电视接收定时同步的设计与实现【D】.浙江大学硕士学位
论文,2005.

【36]

沈南,王华.基于FPGA的高性能Viterbi译码器的设计与实现【J].中国有线
电视,2006(02):163—167.
第56页

国防科技大学研究生院硕十学位论文

【37】

章宇,马彬.DRM系统中卷秘编码及Viterbi译码的实现[J】.信号与信息 处理,2006,36(1 1):25—28. 高志斌,黄联芬.无线通信系统维特比译码的FPGA仿真验iiE[J].现代电子
技术,2006,29(13):20-23.
selective Viterbi

【38]

【39】Sudhakar

R.Low-complexity

error

decoder[J].Electronics

Letters,2000,36(2):147-149.

[40】张俊.卷积码维特比译码算法最佳反馈深度研究【J】.现代电子技术,
2006,29(3),145—146. 【41】

王新梅,肖国镇,纠错码.原理与方法[M】.西安电子科技大学出版社,2001:
443.503.

[42]

赵崇辉,赵旦峰,齐金月.基于FPGA的多约束长度Viterbi译码器[J】.应用
科技,2004,3l(5):28.31.

第57页

国防科技大学研究生院硕十学位论文

作者在学期间取得的学术成果
[1】

张普珩,李宗伯,张波涛.一种可配置Viterbi译码器的FPGA实现,第十二 届计算机工程与工艺全国学术年会,内蒙古?呼和浩特,2008.8:41.45. 李宗伯,张普珩,张波涛等.一种Viterbi译码算法的改进,北京交通大学学
报(正刊),北京,2009.2(已录用).

[2】

第58页

Viterbi译码算法的研究与实现
作者: 学位授予单位: 张普珩 国防科学技术大学

本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1522620.aspx




友情链接: