Viterbi译码的Matlab实现
2010年12月（上）
Viterbi 译码的Matlab 实现
张慧
（盐城卫生职业技术学院，江苏盐城
224006）
［摘要］本文主要介绍了Viterbi 译码是一种最大似然译码算法，是卷积编码的最佳译码算法。本文主要是以（2，1，2）卷积码为例，介
绍了Viterbi 译码的原理和过程，并用Matlab 进行仿真。［关键词］卷积码；Viterbi 译码
1卷积码的类型
卷积码的译码基本上可划分为两大类型：代数译码和概率译码，其中概率译码是实际中最常采用的卷积码译码方法。
2Viterbi 译码
Viterbi 译码是由Viterbi 在1967年提出的一种概率译码，其实质是最大似然译码，是卷积码的最佳译码算法。它利用编码网格图的特殊结构，降低了计算的复杂性。该算法考虑的是，去除不可能成为最大似然选择对象的网格图上的路径，即，如果有两条路径到达同一状态，则具有最佳量度的路径被选中，称为幸存路径（
surviving path ）。对所有状态都将进行这样的选路操作，译码器不断在网格图上深入，通过去除可能性最小的路径实现判决。较早地抛弃不可能的路径降低了译码器的复杂性。
为了更具体的理解Viterbi 译码的过程，我们以（2，1，2）卷积码为例，为简化讨论，假设信道为BSC 信道。译码过程的前几步如下：假定输入数据序列m ，码字U ，接收序列Z ，如图1所示，并假设译码器确知网格图的初始状态。
图１
时刻t 1接收到的码元是11，从状态00出发只有两种状态转移方向，00和10，如图a 所示。状态转换的分支量度是2；状态转换的分支径量度是0。时刻t 2从每个状态出发都有两种可能的分支，如图b 所示。这些分支的累积量度标识为状态量度┎a ，┎b ，┎c ，┎d ，与各自的结束状态相对应。同样地，图c 中时刻t 3从每个状态出发都有两个分支，因此，时刻时到达每个状态的路径都有两条，这两条路径中，累积路径量度较大的将被舍弃。如果这两条路径的路径量度恰好相等，则任意舍弃其中一条路径。到各个状态的幸存路径如图d 所示。译码过程进行到此时，时刻t 1和t 2之间仅有一条幸存路径，称为公共支（com-mon stem ）。因此这时译码器可以判决时刻t 1和t 2之间的状态转移是00→10；因为这个状态转移是由输入比特1产生的，所以译码器输出1作为第一位译码比特。由此可以看出，用实线表示输入比特0，虚线表示输入比特1，可以为幸存路径译码带来很大的便利。注意，只有当路径量度计算进行到网格图较深处时，才产生第一位译码比特。在典型的译码器实现中，这代表了大约是约束长度5倍的译码延迟。
图２幸存路径选择
在译码过程的每—步，到达每个状态的可能路径总有两条，通过比较路径量度舍弃其中一条。图e 给出了译码过程的下一步：在时刻t 5到达各个状态的路径都有两条，其中一条被舍弃；图f 是时刻t 5的幸存路径。注意，此例中尚不能对第二位输入数据比特做出判决，因为在时刻t 2离开状态10的路径仍为两条。图g 中的时刻t 6同样有路径合并，图h 是时刻t 6的幸存路径，可见编码器输出的第二位译码比特是1，对应了时刻t 2和t 3之间的幸存路径。译码器在网格图上继续上述过程，通过不断舍弃路径直至仅剩一条，来对输入数据比特做出判决。
网格图的删减（通过路径的合并）确保了路径数不会超过状态数。对于此例的情况，可证明在图b 、d 、f 、h 中，每次删减后都只有4条路径。而对于未使用维特比算法的最大似然序列彻底比较法，其可能路径数（代表可能序列数）是序列长度的指数函数。对于分支字长为L 的二进制码字序列，共有2L 种可能的序列。下面我们用Matlab 函数viterbi （G,k,channel_output ）来产生输入序列经Viterbi 译码器得到的输出序列，并将结果与输入卷积码编码器的信息序列进行比较。在这里，G ＝g ，k=k0，channel_output=output 。用Matlab 函数得到的译码输出为10011100110000111，这与我们经过理论分析得出的结果是一致的。
我们用subplot 函数将译码器最终的输出结果与（下转第261页）
250
TECHNOLOGY TREND
（上接第250页）
编码器的输入信息序列画出来，其仿真图如下：
图５－４
从仿真图上可以看出，在无任何干扰的理想状态或纠错范围内（随机干扰数），经过译码后，其输出的结果与输入编码器的信息序列是一致的。这说明设计的卷积编译码器是符合要求的。但是当有一连串的
突发差错出现时，译码器的输出就会出错，这时，我们就得考虑对信道进行改造，以降低误码率。
3结语
Viterbi 译码是一种最大似然译码算法，是卷积编码的最佳译码算法。本文主要是以（
2，1，2）卷积码为例，介绍了Viterbi 译码的原理和过程。同时指出，尽管差错概率随着约束长度按指数级减小，但是编码状态数以及相应的译码复杂性，都随约束长度呈指数增长，因此要选择合适的约束长度。
［参考文献］
[1]徐超颖,杨国安,石永光,郑南宁.卷积码及其维特比译码算法的软件实现.
西安交通大学学报,2003.
[2]John G.Proakis.数字通信(第三版)(Digital Communications,Third Edition).电子工业出版社,1998.
[3]王新梅,肖国镇.纠错码———原理与方法.西安电子科技大学出版社,2001.[4]徐元欣,王匡,仇佩亮.实现卷积交织的几种实用方法.电路与系统学报.2001.
在的0.94左右。
电流变化显示：
对东曲选煤厂8个低压配电室，配电12台变压器装设了补偿后，平均每台变压器的二次侧总电流比原来降低25%左右。
变压器的二次测电压变化情况：
补偿前，开车时，线电压降为370V~375V 左右；补偿后，开车时，线电压升为380V~385V 左右。2）从经济效益方面看：
a.装设无功补偿设备后，减少了线路和变配电设备传输的无功功率和视在功率，提高了功率因数，减少了功率损耗和电能损耗。
降低了线路损耗.功率因数由0.78提高到0.94后，线损降低的百分率为31.2%，生产开车时，全厂供电系统需传输功率约为700KW ，在补偿前，线损百分率为5%，补偿后，线损比原来降低31.2%，则线损比原来降低109.2KW ，按每天开时间为20小时计算，则每月节约电能为65520Kwh ，年节约电费为27万元。
b.减少了功率因数调整电费支出
根据有关功率因数调整电费的办法，用户的功率因数低于0.9时要加收电费，高于该值时减收电费。
补偿前，因功率因数低于0.9，受罚多支出电费平均每月为4.5万元，每年多支出电为54万元。
补偿后，功率因数达0.94，按照奖励办法将奖励0.6%，与补偿前相比较，年减少电费支出61.1万元，综上，每年直接创造经济效益87.8万元.
c.减少了供电系统的无功损耗
无功补偿运行以来，大大降低了无功电量。如广场高压配电室Ⅰ回路，补偿前每月无功电量为558000，补偿后，该回路每月份无功电量为212400，比原来降低了62%。
d.减少了供电设备投资
补偿后，减少了供电设备的负载，因而在一定范围内解决了过载问题，可不办理变配电设备增容手续和更换供电设备，减少了增容改造的费用，从而节省了投资。
5提高功率因素的意义
东曲选煤厂通过低压配电系统集中无功补偿改造，在6KV 侧的功率因数由低于0.8提高到现在的0.94左右，变压器二次侧运行电流降低了25%，使变压器的备用容量得到增加，能够再充分利用。同时减少了变压器配电线路的功率损失和配电线路的电压损失，有利于异步电动机的运行和安全起动，既满足了上级电业管理部门的安全要求，又节约了电费支出。实践证明，低压配电系统集中无功补偿改造能够很好地提高电力系统功率因数，是节约电能，保证供电质量和安全运行的有效方法之一。
作者简介：王超，男，1971年5月14日出生于河南省柘城县，本科学历，山西西山煤电（集团）有限责任公司东曲矿选煤厂工程师，研究方向为电器安全运行。
［参考文献］
[1]最新实用电工手册,化学工业出版社,2000.
[2]煤矿电工手册,煤炭工业出版社,1981.[3]矿山供电,山西焦煤编印,2003.
应用科技
261
哈夫曼树编码译码实验报告(DOC)
数据结构课程设计设计题目：哈夫曼树编码译码
目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12)
在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。
DSP卷积码的维特比译码的分析与实现
编号： 《DSP技术与应用》课程论文卷积码的维特比译码的分析与实现 论文作者姓名：______ ______ 作者学号：___ ______ 所在学院： 所学专业：_____ ___ 导师姓名职称：__ _ 论文完成时间： _
目录 摘要： (1) 0 前言 (2) 1 理论基础 (2) 1.1信道理论基础 (2) 1.2差错控制技术 (3) 1.3纠错编码 (4) 1.4线性分组码 (5) 2 卷积码编码 (7) 2.1 卷积码概要 (7) 2.2 卷积码编码器 (8) 2.3卷积码的图解表示 (8) 2.4 卷积码的解析表示 (11) 3 卷积码的译码 (14) 3.1 维特比译码 (15) 3.2 代数译码 (17) 3.3 门限译码 (18) 4 维特比译码器实现 (18) 4.1 TMS320C54 系列DSP概述 (18) 4.2 Viterbi译码器的DSP实现 (19) 4.3 实现结果 (21) 5 结论 (21) 参考文献 (22) II
卷积码的维特比译码的分析与实现 摘要： 针对数据传输过程中的误码问题，本文论述了提高数据传输质量的一些编码及译码的实现问题。自P.Elias 首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。在与分组码同样的码率R 和设备复杂性的条件下，无论从理论上还是从实际上均己证明卷积码的性能至少不比分组码差，且实现最佳和准最佳译码也较分组码容易。目前，卷积码已广泛应用在无线通信标准中，其维特比译码则利用码树的重复性结构，对最大似然译码算法进行了简化。本文所做的主要工作： 首先对信道编码技术进行了研究，根据信道中可能出现的噪声等问题对卷积码编码方法进行了主要阐释。 其次，对卷积码维特比译码器的实现算法进行了研究，完成了译码器的软件设计。 最后，结合实例，采用DSP芯片实现卷积码的维特比译码算法的仿真和运行。 关键词： 卷积码维特比译码DSP Convolutional codes and Viterbi decoding analysis and realization Zhang Yi-Fei (School of Physics and Electronics, Henan University, Henan Kaifeng 475004, China) Abstract: Considering the error bit problem during data transmission,this thesis discussed some codings and decoders,aiming at enhancing transmission performance. From P.Elias first gave the concept of convolutional code, it has show its’ great advantage. Under the same condition and the same rate of block code, the performance of convolutional code is better than block code, and it’s easier to implement the best decoding.Convolutional codes have been widely used in wireless communication standards, the V iterbi decoding using the repetitive structure of the code tree, the maximum likelihood decoding algorithm has been simplified. Major work done in this article: First, the channel coding techniques have been studied, the main interpretation of the convolutional code encoding method according to the channel may be noise and other issues. Secondly, the convolutional code V iterbi decoder algorithm has been studied, the software design of the decoder. Finally, with examples, simulation and operation of the DSP chip convolutional codes, Viterbi decoding algorithm. 1
哈夫曼编码与译码的实现
数据结构课程设计评阅书
2011—2012学年第一学期 专业：信息管理与信息系统学号： 1021024016 姓名：万永馨 课程设计名称：数据结构课程设计 设计题目：哈夫曼编码与译码的实现 完成期限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计依据、要求及主要内容（可另加附页）： 该设计题目将按以下要求完成： 哈夫曼编码与译码是信息传输中应用的经典算法，运用C或VC++结合数据结构等基础知识，按 以下要求编程实现各种进制的转换。 任务要求：1）阐述设计思想,画出流程图;2）需要对哈夫曼编码/译码的相关原理有所了解，设计数 据结构，建立必要的信息数据文件（最好存储成外部文件），并分析完成用户所需的基本操作功能；3）实现给定信息的编码和译码功能；4）应有较好的界面设计，说明程序测试方法；5）按照格式要 求完成课程设计说明书。 设计要求: 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的 原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定 义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调 用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统 功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基 本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精， 写出数据存储结构的类型定义，写出函数形式的算法框架； 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言， 使程序中逻辑概念清楚； 5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正 确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算 法的时间、空间复杂性分析； 7）编写课程设计报告； 以上要求前三个阶段的任务完成后，将设计说明书的草稿交指导老师面审，审查合格方可进入 后续阶段的工作。设计工作结束，经指导老师验收合格后将设计说明书装订，并答辩。
Viterbi译码的Matlab实现
2010年12月（上） Viterbi 译码的Matlab 实现 张慧 （盐城卫生职业技术学院，江苏盐城 224006） ［摘要］本文主要介绍了Viterbi 译码是一种最大似然译码算法，是卷积编码的最佳译码算法。本文主要是以（2，1，2）卷积码为例，介 绍了Viterbi 译码的原理和过程，并用Matlab 进行仿真。［关键词］卷积码；Viterbi 译码 1卷积码的类型 卷积码的译码基本上可划分为两大类型：代数译码和概率译码，其中概率译码是实际中最常采用的卷积码译码方法。 2Viterbi 译码 Viterbi 译码是由Viterbi 在1967年提出的一种概率译码，其实质是最大似然译码，是卷积码的最佳译码算法。它利用编码网格图的特殊结构，降低了计算的复杂性。该算法考虑的是，去除不可能成为最大似然选择对象的网格图上的路径，即，如果有两条路径到达同一状态，则具有最佳量度的路径被选中，称为幸存路径（ surviving path ）。对所有状态都将进行这样的选路操作，译码器不断在网格图上深入，通过去除可能性最小的路径实现判决。较早地抛弃不可能的路径降低了译码器的复杂性。 为了更具体的理解Viterbi 译码的过程，我们以（2，1，2）卷积码为例，为简化讨论，假设信道为BSC 信道。译码过程的前几步如下：假定输入数据序列m ，码字U ，接收序列Z ，如图1所示，并假设译码器确知网格图的初始状态。 图１ 时刻t 1接收到的码元是11，从状态00出发只有两种状态转移方向，00和10，如图a 所示。状态转换的分支量度是2；状态转换的分支径量度是0。时刻t 2从每个状态出发都有两种可能的分支，如图b 所示。这些分支的累积量度标识为状态量度┎a ，┎b ，┎c ，┎d ，与各自的结束状态相对应。同样地，图c 中时刻t 3从每个状态出发都有两个分支，因此，时刻时到达每个状态的路径都有两条，这两条路径中，累积路径量度较大的将被舍弃。如果这两条路径的路径量度恰好相等，则任意舍弃其中一条路径。到各个状态的幸存路径如图d 所示。译码过程进行到此时，时刻t 1和t 2之间仅有一条幸存路径，称为公共支（com-mon stem ）。因此这时译码器可以判决时刻t 1和t 2之间的状态转移是00→10；因为这个状态转移是由输入比特1产生的，所以译码器输出1作为第一位译码比特。由此可以看出，用实线表示输入比特0，虚线表示输入比特1，可以为幸存路径译码带来很大的便利。注意，只有当路径量度计算进行到网格图较深处时，才产生第一位译码比特。在典型的译码器实现中，这代表了大约是约束长度5倍的译码延迟。 图２幸存路径选择 在译码过程的每—步，到达每个状态的可能路径总有两条，通过比较路径量度舍弃其中一条。图e 给出了译码过程的下一步：在时刻t 5到达各个状态的路径都有两条，其中一条被舍弃；图f 是时刻t 5的幸存路径。注意，此例中尚不能对第二位输入数据比特做出判决，因为在时刻t 2离开状态10的路径仍为两条。图g 中的时刻t 6同样有路径合并，图h 是时刻t 6的幸存路径，可见编码器输出的第二位译码比特是1，对应了时刻t 2和t 3之间的幸存路径。译码器在网格图上继续上述过程，通过不断舍弃路径直至仅剩一条，来对输入数据比特做出判决。 网格图的删减（通过路径的合并）确保了路径数不会超过状态数。对于此例的情况，可证明在图b 、d 、f 、h 中，每次删减后都只有4条路径。而对于未使用维特比算法的最大似然序列彻底比较法，其可能路径数（代表可能序列数）是序列长度的指数函数。对于分支字长为L 的二进制码字序列，共有2L 种可能的序列。下面我们用Matlab 函数viterbi （G,k,channel_output ）来产生输入序列经Viterbi 译码器得到的输出序列，并将结果与输入卷积码编码器的信息序列进行比较。在这里，G ＝g ，k=k0，channel_output=output 。用Matlab 函数得到的译码输出为10011100110000111，这与我们经过理论分析得出的结果是一致的。 我们用subplot 函数将译码器最终的输出结果与（下转第261页） 250
Matlab的卷积码译码器的仿真要点
基于Matlab的卷积码译码器的 设计与仿真 学生姓名：指导老师：** 摘要本课程设计主要解决对一个卷积码序列进行维特比(Viterbi)译码输出, 并通过Matlab软件进行设计与仿真，并进行误码率分析。在课程设计中，系统开发平台为Windows Vista Ultimate，程序设计与仿真均采用Matlab R2007a(7.4)，最后仿真详单与理论分析一致。 关键词课程设计；卷积码译码器；Matlab；Simulink；设计与仿真 1引言 本课程设计主要解决对一个卷积码序列进行维特比(Viterbi)译码输出,并通 过Matlab软件进行设计与仿真。卷积码的译码有两种方法——软判决和硬判决，此课程设计采用硬判决的维特比译码。 1.1课程设计目的 卷积码是一种向前纠错控制编码。它将连续的信息比特序列映射为连续的编码器输出符号。这种映射是高度结构化的，使得卷积码的译码方法与分组码译码所采用的方法完全不同。可以验证的是在同样复杂度情况下，卷积码的编码增益要大于分组码的编码增益。对于某个特定的应用，采用分组编码还是采用卷积编码哪一种更好则取决于这一应用的具体情况和进行比较时可用的技术[1]。 本课程设计便是通过Matlab设计一个硬判决维特比译码输出的完整电路，并进行误码率分析。
1.2 课程设计的原理 卷积码，又称连环码，是由伊莱亚斯(P.elias)于1955年提出来的一种非分组码。 卷积编码的最佳译码准则为：在给定已知编码结构、信道特性和接收序列的情况下，译码器将把与已经发送的序列最相似的序列作为传送的码字序列的估值。对于二进制对称信道，最相似传送序列就是在汉明距离上与接收序列最近的序列。 卷积码的译码方法有两大类：一类是大数逻辑译码，又称门限译码(硬判决，编者注)；另一种是概率译码(软判决，编者注)，概率译码又分为维特比译码和序列译码两种。门限译码方法是以分组码理论为基础的，其译码设备简单，速度快，但其误码性能要比概率译码法差[2]。 当卷积码的约束长度不太大时，与序列译码相比，维特比译码器比较简单，计算速度快。维特比译码算法是1967年由Viterbi提出，近年来有大的发展。目前在数字通信的前向纠错系统中用的较多，而且在卫星深空通信中应用更多，该算法在卫星通信中已被采用作为标准技术。 2维特比译码原理 采用概率译码的基本思想是：把已接收序列与所有可能的发送序列做比较，选择其中码距最小的一个序列作为发送序列。如果发送L组信息比特，那么对于(n,k)卷积码来说，可能发送的序列有2kL个，计算机或译码器需存储这些序列并进行比较，以找到码距最小的那个序列。当传信率和信息组数L较大时，使得译码器难以实现。维特比算法则对上述概率译码做了简化，以至成为了一种实用化的概率算法。它并不是在网格图上一次比较所有可能的2kL条路径(序列)，而是接收一段，计算和比较一段，选择一段最大似然可能的码段，从而达到整个码序列是一个最大似然值得序列。 下面以图2.1的(2，1，3)卷积码编码器所编出的码为例，来说明维特比解码的方法和运作过程。为了能说明解码过程，这里给出该码的状态图，如图2.2所
卷积码编码和维特比译码
卷积码编码维特比译码实验设计报告 SUN 一、实验目的 掌握卷积码编码和维特比译码的基本原理，利用了卷积码的特性, 运用网格图和回溯以得到译码输出。 二、实验原理 1.卷积码是由连续输入的信息序列得到连续输出的已编码序列。其编码器将k个信息码元编为n个码元时，这n个码元不仅与当前段的k个信息有关，而且与前面的（m-1）段信息有关（m为编码的约束长度）。 2.一般地，最小距离d表明了卷积码在连续m段以内的距离特性，该码可以在m个连续码流内纠正(d-1)/2个错误。卷积码的纠错能力不仅与约束长度有关，还与采用的译码方式有关。 3. 维特比译码算法基本原理是将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送序列。卷积码的Viterbi 译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程,找到最佳路径即完成了译码过程,并可以纠正接收码字中的错误比特。 4.所谓“最佳”, 是指最大后验条件概率:P( C/ R) = max [ P ( Cj/ R) ] , 一般来说, 信道模型并不使用后验条件概率,因此利用Beyes 公式、根据信道特性出结论:max[ P ( Cj/ R) ]与max[ P ( R/ Cj) ]等价。考虑到在系统实现中往往采用对数形式的运算,以求降低运算量,并且为求运算值为整数加入了修正因子a1 、a2 。令M ( R/ Cj) = log[ P ( R/ Cj) ] =Σa1 (log[ P( Rm/ Cmj ) ] + a2) 。其中, M 是组成序列的码字的个数。因此寻找最佳路径, 就变成寻找最大M( R/ Cj) , M( R/ Cj) 称为Cj 的分支路径量度,含义为发送Cj 而接收码元为R的似然度。 5.卷积码的viterbi译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程，找到最佳路径即完成了译码过程并可以纠正接收码字中的错误比特。 三、实验代码 #include<> #include "" #define N 7 #include "" #include <> #include<> #define randomize() srand((unsigned)time(NULL)) encode( unsigned int *symbols, /*编码输出*/ unsigned int *data, /*编码输入*/ unsigned int nbytes, /*nbytes=n/16,n为实际输入码字的数目*/ unsigned int startstate /*定义初始化状态*/
哈夫曼树的编码和译码
#include"stdafx.h" #include"stdio.h" #include"conio.h" #include
Viterbi译码的MATLAB仿真研究
BUPT 卷积码编码及Viterbi译码 班级：07114 学号：070422 姓名：吴希龙 指导老师：彭岳星 邮箱：FusionBupt@https://www.wendangku.net/doc/188512174.html,
1. 序言 卷积码最早于1955年由Elias 提出，稍后，1957年Wozencraft 提出了一种有效地译码方法即序列译码。1963年Massey 提出了一种性能稍差但是比较实用的门限译码方法，使得卷积码开始走向实用化。而后1967年Viterbi 提出了最大似然译码算法，它对存储级数较小的卷积码很容易实现，被称作Viterbi 译码算法，广泛的应用于现代通信中。 2. 卷积码编码及译码原理 2.1 卷积码编码原理 卷积码是一种性能优越的信道编码，它的编码器和解码器都比较易于实现，同时还具有较强的纠错能力，这使得它的使用越来越广泛。卷积码一般表示为(n,k,K)的形式，即将k 各信息比特编码为n 个比特的码组，K 为编码约束长度，说明编码过程中相互约束的码段个数。卷积码编码后的n 各码元不经与当前组的k 个信息比特有关，还与前K-1个输入组的信息比特有关。编码过程中相互关联的码元有K*n 个。R=k/n 是编码效率。编码效率和约束长度是衡量卷积码的两个重要参数。典型的卷积码一般选n,k 较小，但K 值可取较大(>10)，以获得简单而高性能的卷积码。 卷积码的编码描述方式有很多种：冲激响应描述法、生成矩阵描述法、多项式乘积描述法、状态图描述，树图描述，网格图描述等。 2.1.1 卷积码解析表示法 卷积码的解析表示发大致可以分为离散卷积法，生成矩阵法，码多项式法。下面以离散卷积为例进行说明。 卷积码的编码器一般比较简单，为一个具有k 个输入端，n 个输出端，m 级移位寄存器的有限状态有记忆系统。下图所示为(2,1,7)卷积码的编码器。 若输入序列为u =(u 0u 1u 2u 3……), 则对应两个码字序列c ①=(c 0①c 1①c 2①c 3①……)和c ②=(c 0②c 1②c 2②c 3② ……) 相应的编码方程可写为c ①=u ?g ①，c ②=u ?g ②，c=(c ①,c ②)。 “?” 符号表示卷积运算，g ①，g ②表示编码器的两个冲激响应，即编码器的输出可以由输入序列和编码器的两个冲击响应卷积而得到，故称为卷积码。这里的冲激响应指：当输入为[1 0 0 0 0 … … ]序列时，所观察到的两个输出序列值。由于上图K 值为7，故冲激响应至
213卷积码编码和译码
No.15 (2,1,3)卷积码的编码及译码 摘要： 本报告对于（2,1,3）卷积码原理部分的论述主要参照啜刚教材和课件，编程仿真部分绝对原创，所有的程序都是在Codeblocks 8.02环境下用C语言编写的，编译运行都正常。完成了卷积码的编码程序，译码程序，因为对于短于3组的卷积码，即2 bit或4 bit纠错是没有意义的，所以对正确的短序列直接译码，对长序列纠错后译码，都能得到正确的译码结果。含仿真结果和程序源代码。 如果您不使用Codeblocks运行程序，则可能不支持中文输出显示，但是所有的数码输出都是正确的。
一、 卷积码编码原理 卷积码编码器对输入的数据流每次1bit 或k bit 进行编码，输出n bit 编码符号。但是输出的分支码字的每个码元不仅于此时可输入的k 个嘻嘻有关，业余前m 个连续式可输入的信息有关，因此编码器应包含m 级寄存器以记录这些信息。 通常卷积码表示为 (n,k,m). 编码率 k r n = 当k=1时，卷积码编码器的结构包括一个由m 个串接的寄存器构成的移位寄存器（成为m 级移位寄存器、n 个连接到指定寄存器的模二加法器以及把模二加法器的输出转化为穿行的转换开关。 本报告所讲的（2,1,3）卷积码是最简单的卷积码。就是2n =，1k =，3m =的卷积码。每次输入1 bit 输入信息，经过3级移位寄存器，2个连接到指定寄存器的模二加法器，并把加法器输出转化为串行输出。 编码器如题所示。 二、卷积码编码器程序仿真 C 语言编写的仿真程序。 为了简单起见，这里仅仅提供数组长度30 bit 的仿真程序，当然如果需要可以修改数组大小。为了更精练的实现算法，程序输入模块没有提供非法字符处理过程，如果需要也可以增加相应的功能。 进入程序后，先提示输入数据的长度，请用户输入int （整型数）程序默认用户输入的数据小于30，然后提示输入01数码，读入数码存储与input 数组中，然后运算输出卷积码。经过实验仿真，编码完全正确。 以下是举例： a.课件上的输入101 输出11 10 00 的实验
哈夫曼编码与译码器_数据结构课程设计报告
沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：实现哈夫曼编码和译码器 院（系）：计算机学院 专业：计算机科学与技术 班级：24010102 学号：2012040101082 姓名：尹伟和 指导教师：徐蕾
此页为任务书
目录 1.题目分析 (1) 1.1.题目重述 (1) 1.1.1.系统功能需求分析 (1) 2.程序设计 (2) 2.1.系统功能模块说明 (2) 2.1.1.系统功能模块结构 (2) 2.1.2.系统模块功能说明 (3) 2.2.数据结构说明 (3) 2.2.1.结构体定义说明 (3) 2.2.2.哈夫曼树 (4) 2.2.3.字符-哈夫曼编码对照表 (4) 2.3.函数说明 (4) 3.算法描述 (6) 3.1.哈夫曼树的构建 (6) 3.2.字符-哈夫曼编码对照表 (6) 3.3.编码 (6) 3.4.译码 (7) 4.程序测试 (9) 4.1.字符集输入 (9) 4.2.编码测试 (10) 4.3.译码测试 (11) 参考文献 (13) 附录（程序清单） (14)
沈阳航空航天大学课程设计报告 1.题目分析 1.1.题目重述 本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码，使二进制密文变为字符明文。 1.1.1.系统功能需求分析 通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需求如下： 1)读取用户输入的字符集和相应字符出现的频率； 2)根据用户输入构建哈夫曼树； 3)根据哈夫曼树构建字符-哈夫曼编码对照表； 4)根据字符-哈夫曼编码对照表对明文字符串进行编码； 5)根据哈夫曼树对二进制密文进行译码。
Viterbi译码器研究目的意义及现状
Viterbi译码器研究目的意义及现状Viterbi译码器研究目的意义及现状 1研究的目的和意义 由于卷积码的优良性能，被广泛的应用于深空通信，卫星通信和2G及3G移动通信中，卷积码有三种译码方法:门限译码，门限译码,概率译码和Viterbi 算法,其中Viterbi算法是一种基于网格图的最大似然译码算法,是卷积码的最佳译码方式,具有效率高、速度快等优点。Viterbi译码充分发挥了卷积码的特点，使译码错误概率达到最小，在码的约束度较小时，它具有译码算法效率高，速度快，译码器也简单的特点。 FPGA(Field,Programmable Gate Array)，即现场可编程门阵列，它是在PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路(ASIC)领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。 同时在FPGA的基础上实现Viterbi译码器，迎合了当前FPGA迅猛发展的趋势。把相对成熟的技术应用到某些特定领域如通讯，视频，信息处理等等开发出满足行业需要并能被行业客户接受的产品这方面主要是FPGA技术和专业技术的结合问题，另外还有就是与专业客户的界面问题产品设计还包括专业工具类产品及民用产品，前者重点在性能，后者对价格敏感产品设计以实现产品功能为主要目的，FPGA技术是一个实现手段在这个领域，FPGA因为具备接口，控制，功能IP，内嵌CPU等特点有条件实现一个构造简单，固化程度高，功能全面的系统产品设计将是FPGA技术应用最广大的市场，具有极大的爆发性的需求空间产品设计对技术人员的要求比较高，路途也比较漫长不过现在整个行业正处在组建“首发团队”的状态，只要加入，前途光明产品设计是一种职业发展方向定位，不是简单的爱好就能
huffman编码译码实现文件的压缩与解压.
数据结构 课程设计 题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组长： 小组成员： 指导教师： 二〇一二年十二月二十六日
目录 一、目标任务与问题分析 (2) 1.1目标任务 (2) 1.2问题分析 (2) 二、算法分析 (2) 2.1构造huffman树 (2) 2.1.1 字符的统计 (2) 2.1.2 huffman树节点的设计 (2) 2.2构造huffman编码 (3) 2.2.1 huffman编码的设计 (3) 2.3 压缩文件与解压文件的实现 (3) 三、执行效果 (4) 3.1界面 (4) 3.2每个字符的编码 (4) 3.3操作部分 (5) 3.4文件效果 (6) 四、源程序 (7) 五、参考文献 (16)
huffman编码与解码实现文件的压缩与解压 一、目标任务与问题分析 1.1目标任务 采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 字符的统计 用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。 struct huffchar{ //存放读入字符的类； int Count;//字符出现的个数； char data;//字符； }; 函数实现： bool char_judge(char c)//判断字符出现的函数； void char_add(char c)//添加新出现的字符； void read_file_count() //文件的读取 2.1.2 huffman树节点的设计 用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。
Viterbi译码程序代码
译码主要部分 #include"stdafx.h" //#define DEBUG void deci2bin(int d, int size, int *b); int bin2deci(int *b, int size); int nxt_stat(int current_state, int input, int *memory_contents); void init_quantizer(void); void init_adaptive_quant(float es_ovr_n0); int soft_quant(float channel_symbol); int soft_metric(int data, int guess); int quantizer_table[256]; void sdvd(int g[2][K], float es_ovr_n0, long channel_length, float*channel_output_vector, int *decoder_output_matrix) { int i, j, l, ll; //循环控制变量 long t; //时间 int memory_contents[K]; //记录输入内容 int input[TWOTOTHEM][TWOTOTHEM]; //对当前状态以及下一个状态映射 int output[TWOTOTHEM][2]; //卷积码编码输出矩阵 int nextstate[TWOTOTHEM][2]; //下一个状态矩阵 int accum_err_metric[TWOTOTHEM][2]; //误差累计矩阵 int state_history[TWOTOTHEM][K * 5 + 1]; //历史状态表 int state_sequence[K * 5 + 1]; //状态序列 int *channel_output_matrix; //信道输出序列 int binary_output[2]; int branch_output[2]; //0或者1的输出分支 int m, n, number_of_states, depth_of_trellis, step, branch_metric, sh_ptr, sh_col, x, xx, h, hh, next_state, last_stop; n = 2; //1/2为卷积码传输数据的码率 m = K - 1;//寄存器个数 number_of_states = (int)pow(2.0, m);//状态个数number of states = 2^(K - 1) = 2^m depth_of_trellis = K * 5; for (i = 0; i < number_of_states; i++)
MATLAB实现卷积码编译码-
本科生毕业论文（设计） 题目：MATLAB实现卷积码编译码 专业代码： 作者姓名： 学号： 单位： 指导教师： 年月日
目录 前言----------------------------------------------------- 1 1. 纠错码基本理论---------------------------------------- 2 1.1纠错码基本理论 ----------------------------------------------- 2 1.1.1纠错码概念 ------------------------------------------------- 2 1.1.2基本原理和性能参数 ----------------------------------------- 2 1.2几种常用的纠错码 --------------------------------------------- 6 2. 卷积码的基本理论-------------------------------------- 8 2.1卷积码介绍 --------------------------------------------------- 8 2.1.1卷积码的差错控制原理----------------------------------- 8 2.2卷积码编码原理 ---------------------------------------------- 10 2.2.1卷积码解析表示法-------------------------------------- 10 2.2.2卷积码图形表示法-------------------------------------- 11 2.3卷积码译码原理---------------------------------------------- 15 2.3.1卷积码三种译码方式------------------------------------ 15 2.3.2V ITERBI译码原理---------------------------------------- 16 3. 卷积码编译码及MATLAB仿真---------------------------- 18 3.1M ATLAB概述-------------------------------------------------- 18 3.1.1M ATLAB的特点------------------------------------------ 19 3.1.2M ATLAB工具箱和内容------------------------------------ 19 3.2卷积码编码及仿真 -------------------------------------------- 20 3.2.1编码程序 ---------------------------------------------- 20 3.3信道传输过程仿真-------------------------------------------- 21 3.4维特比译码程序及仿真 ---------------------------------------- 22 3.4.1维特比译码算法解析------------------------------------ 23 3.4.2V ITERBI译码程序--------------------------------------- 25 3.4.3 VITERBI译码MATLAB仿真----------------------------------- 28 3.4.4信噪比对卷积码译码性能的影响 -------------------------- 28
哈夫曼编码与译码报告
一、设计思想 程序要求： 利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。 实现方法： 输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算权值的函数（jsquanzhi()）进行字符统计，统计出现的字符种数以及每种字符出现的次数，将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT（节点）权值的大小建立哈夫曼树，首先用选择函数select（）函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两个叶节点的父节点，被选中的节点给他的HT[i].parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择（被选过的不再被使用），直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为‘0’，右子为‘1’，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins[]数组。 重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd[]，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[]中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。
动态规划：卷积码的Viterbi译码算法
动态规划:卷积码的Vitｅrｂi译码算法 学院:网研院?姓名:ｘxx 学号：xxｘ一、动态规划原理 动态规划（dynamｉc programminｇ)是运筹学的一个分支,是求解决策过程(decｉsioｎ procｅsｓ）最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。 二、卷积码的Ｖｉterbi译码算法简介 在介绍维特比译码算法之前，首先了解一下卷积码编码，它常常与维特比译码结合使用。(2,１，3)卷积码编码器是最常见的卷积码编码器,在本次实验中也使用了(2,1，３)卷积码编码器,下面介绍它的原理。 （2,１,３)卷积码是把信源输出的信息序列，以1个码元为一段,通过编码器输出长为2的一段码段。该码段的值不仅与当前输入码元有关，而且也与其之前的２个输入码元有关。如下图所示,输出out1是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，输出ouｔ２是输入和第二个编码器存储的值逻辑加操作的结果。 （２,1,３)卷积码编码器