实验三 信源编码实验
实验三信源编码实验
一、实验目的：
1、掌握哈夫曼编码的Matlab实现方法。
2、掌握VC++读取信源数据的方法。
3、运行编译好的霍夫曼编码、算术编码、游程编码编码程序，比较霍夫曼
编码、算术编码、游程编码编码的编码效果
二、实验内容与步骤
1、Huffman编码实验
1）编写计算信息熵的M文件
参考程序：
function h=entropy(p)
%H=ENTROPY(P)返回概率矢
% 量P的熵函数
if length (find(p<0))~=0
error('Not a prob.vector,negative component(s)')
end
if abs (sum(p)-1)>10e-10
error ('Not a prob.vector,components do not add up to 1') end
h=sum(-p.*log2(p));
求信源X=[x1,x2,…,x9]，其相应的概率为p=[0.2,0.15,0.13,0.12,0.1,0.09,0.08,0.07,0.06];利用编写的程序计算信息熵，并记录数值。
2）编写程序实现Huffman编码
编写实现Huffman编码的M文件，编译后运行，验证程序的正确性并记录编码结果。
参考程序：
function [h,l]=huffman(p);
%HUFFMAN 哈夫曼编码生成器
% [h,l]=huffman(p),返回哈夫曼编码矩阵H及码字长度
if length (find (p<0))~=0,
erro('Not a prob.vector,negative component(s)')
end
if abs(sum(p)-1)>10e-10,
error('Not a prob.vector,components do not add up to 1') end
n=length(p);
q=p;
m=zeros(n-1,n);
for i=1:n-1
[q,l]=sort(q);
m(i,:)=[l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
end
for i=1:n-1
c(i,:)=blanks(n*n);
end
c(n-1,n)='0';
c(n-1,2*n)='1';
for i=2:n-1
c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))-(n-2):n*(fi nd(m(n-i+1,:)==1)));
c(n-i,n)='0';
c(n-i,n+1:2*n-1)=c(n-i,1:n-1);
c(n-i,2*n)='1';
for j=1:i-1
c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(m(n-i+1,:)==j+1 )-1)+1:n*find(m(n-i+1,:)==j+1));
end
end
for i=1:n
h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n); ll(i)=length(find(abs(h(i,:))~=32));
end
l=sum(p.*ll);
在命令行后输入
》p=[0.1 0.3 0.05 0.09 0.21 0.25];
》[H,l]=huffman(p)
记录运行结果，并说明编码结果是否正确，计算编码效率。
2、VC++下图像的显示
双击实验程序文件夹下的openimagefile可执行文件，出现如下对话框后
选择相应的图片文件，则可显示图片。
双击实验程序文件夹下的MyYUViewer可执行文件，出现如下对话框，选择打开文件，则可显示第一帧图像，点击播放后可看到按设定的帧率播放的图像。
3、比较霍夫曼编码、算术编码、游程编码编码的编码效果
运行实验程序文件夹下的liftingscheme可执行文件，出现如下对话框，
分别选择各种编码方式完成编码及解码，并记录源文件，编码文件及解码文件的大小。下面以霍夫曼编解码为例说明使用的方法。点击霍夫曼编解码后出现以下界面：
选择好文件后，选打开，出现以下界面，选择编码，编码后的文件后缀为.huf。
若进行解码操作，要重新选择输入及输出文件，如下图所示：
点击解码，则生成解码后的文件lena_De.raw。比较源文件、编码文件及解码文件的大小，并记录。
4、运用photoshop软件打开原始图片和解码后图片，比较结果。
三、实验结果：
1、1）信息熵的结果：
2）M文件编码结果：
2、原始图片：
霍夫曼编码解码后的图片：
算术编码解码后的图片：与霍夫曼编码解码后的图片一样。游程编码解码后的图片：
霍夫曼编码的matlab实现(信源编码实验)
重庆交通大学信息科学与工程学院综合性设计性实验报告 专业班级：通信工程2012级1班 学号：631206040118 姓名：王松 实验所属课程：信息论与编码 实验室(中心)：软件与通信实验中心 指导教师：黄大荣 2015年4月
霍夫曼编码的matlab实现 一、实验目的和要求。 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。 本实验用Matlab语言编程实现霍夫曼（Huffman）编码。 二、实验原理。 霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。离散无记忆信源： 例如 U u 1u 2 u 3 u 4 u 5 P(U) = 0.4 0.2 0.2 0.1 0.1
通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。 三、实验步骤 分为两步，首先是码树形成过程：对信源概率进行合并形成编码码树。然后是码树回溯过程：在码树上分配编码码字并最终得到霍夫曼编码。 1、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。然后按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。在这一过程中每一次都把排序后的信源概率存入矩阵G中，位置索引存入矩阵Index中。这样，由排序之后的概率矩阵G以及索引矩阵Index就可以恢复原概率矩阵P了，从而保证了回溯过程能够进行下去。 2、码树回溯过程：在码树上分配编码码字并最终得到Huffman 编码。从索引矩阵M 的末行开始回溯。 (1) 在Index的末行2元素位置填入0和1。 (2) 根据该行索引1 位置指示，将索引1 位置的编码（‘1’）填入上一行的第一、第二元素位置，并在它们之后分别添加‘0’和‘1’。 (3) 将索引不为‘1’的位置的编码值（‘0’）填入上一行的相应位置（第 3 列）。 (4) 以Index的倒数第二行开始向上，重复步骤(1) ～(3)，直到计算至Index 的首行为止。 四、程序代码： %取得信源概率矩阵,并进行合法性判断 clear; P=input('请输入信源概率向量P='); N=length(P); for component=1:1:N
信源编码的基本原理及其应用..
信源编码的基本原理及其应用 课程名称通信原理Ⅱ 专业通信工程 班级******* 学号****** 学生姓名***** 论文成绩 指导教师***** ******
信源编码的基本原理及其应用 信息论的理论定义是由当代伟大的数学家美国贝尔实验室杰出的科学家香农在他1948 年的著名论文《通信的数学理论》所定义的，它为信息论奠定了理论基础。后来其他科学家，如哈特莱、维纳、朗格等人又对信息理论作出了更加深入的探讨。使得信息论到现在形成了一套比较完整的理论体系。 信息通过信道传输到信宿的过程即为通信，通信中的基本问题是如何快速、准确地传送信息。要做到既不失真又快速地通信，需要解决两个问题：一是不失真或允许一定的失真条件下，如何提高信息传输速度（如何用尽可能少的符号来传送信源信息）；二是在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大（如何尽可能地提高信息传输的可靠性）。这样就对信源的编码有了要求，如何通过对信源的编码来实现呢？ 通常对于一个数字通信系统而言，信源编码位于从信源到信宿的整个传输链路中的第一个环节，其基本目地就是压缩信源产生的冗余信息，降低传递这些不必要的信息的开销，从而提高整个传输链路的有效性。在这个过程中，对冗余信息的界定和处理是信源编码的核心问题，那么首先需要对这些冗余信息的来源进行分析，接下来才能够根据这些冗余信息的不同特点设计和采取相应的压缩处理技术进行高效的信源编码。简言之，信息的冗余来自两个主要的方面：首先是信源的相关性和记忆性。这类降低信源相关性和记忆性编码的典型例子有预测编码、变换编码等；其次是信宿对信源失真具有一定的容忍程度。这类编码的直接应用有很大一部分是在对模拟信源的量化上，或连续信源的限失真编码。可以把信源编码看成是在有效性和传递性的信息完整性（质量）之间的一种折中有段。 信源编码的基本原理： 信息论的创始人香农将信源输出的平均信息量定义为单消息（符号）离散信源的信息熵： 香农称信源输出的一个符号所含的平均信息量为 为信源的信息熵。 通信原理中对信源研究的内容包括3个方面： (1)信源的建模 信源输出信号的数学描述已有成熟的理论——随机过程，一般的随机过程理∑=-=L i i i x p x p x H 12) (log )()()(x H
数字通信中的信源编码和信道编码.(优选)
数字通信中的信源编码和信道编码 摘要：如今社会已经步入信息时代，在各种信息技术中，信息的传输及通信起着支撑作用。而对于信息的传输，数字通信已经成为重要的手段。本论文根据当今现代通信技术的发展，对信源编码和信道编码进行了概述性的介绍. 关键词：数字通信；通信系统；信源编码；信道编码 Abstract：Now it is an information society. In the all of information technologies, transmission and communication of information take an important effect. For the transmission of information, Digital communication has been an important means. In this thesis we will present an overview of source coding and channel coding depending on the development of today’s communica tion technologies. Key Words：digital communication; communication system; source coding; channel coding 1.前言 通常所谓的“编码”包括信源编码和信道编码。编码是数字通信的必要手段。使用数字信号进行传输有许多优点, 如不易受噪声干扰, 容易进行各种复杂处理, 便于存贮, 易集成化等。编码的目的就是为了优化通信系统。一般通信系统的性能指标主要是有效性和可靠性。所谓优化，就是使这些指标达到最佳。除了经济性外，这些指标正是信息论研究的对象。按照不同的编码目的，编码可主要分为信源编码和信道编码。在本文中对此做一个简单的介绍。 2.数字通信系统 通信的任务是由一整套技术设备和传输媒介所构成的总体——通信系统来完成的。电子通信根据信道上传输信号的种类可分为模拟通信和数字通信。最简单的数字通信系统模型由信源、信道和信宿三个基本部分组成。实际的数字通信系统模型要比简单的数字通信系统模型复杂得多。数字通信系统设备多种多样，综合各种数字通信系统，其构成如图2-l所示。 图2-1 数字通信系统模型 信源编码是以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。 信道，通俗地说是指以传输媒质为基础的信号通路。具体地说，信道是指由有线或无线电线路提供的信号通路。信道的作用是传输信号，它提供一段频带让信号通过，同时又给信号加以限制和损害。 信道编码是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率或带宽。与信源编码正好相反。在计算机科学领域，信道编
信源编码的基本原理及其应用讲课稿
信源编码的基本原理 及其应用
信源编码的基本原理及其应用 课程名称通信原理Ⅱ 专业通信工程 班级 ******* 学号 ****** 学生姓名 ***** 论文成绩 指导教师 ***** ******
信源编码的基本原理及其应用 信息论的理论定义是由当代伟大的数学家美国贝尔实验室杰出的科学家香农在他1948 年的著名论文《通信的数学理论》所定义的，它为信息论奠定了理论基础。后来其他科学家，如哈特莱、维纳、朗格等人又对信息理论作出了更加深入的探讨。使得信息论到现在形成了一套比较完整的理论体系。 信息通过信道传输到信宿的过程即为通信，通信中的基本问题是如何快速、准确地传送信息。要做到既不失真又快速地通信，需要解决两个问题：一是不失真或允许一定的失真条件下，如何提高信息传输速度（如何用尽可能少的符号来传送信源信息）；二是在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大（如何尽可能地提高信息传输的可靠性）。这样就对信源的编码有了要求，如何通过对信源的编码来实现呢？ 通常对于一个数字通信系统而言，信源编码位于从信源到信宿的整个传输链路中的第一个环节，其基本目地就是压缩信源产生的冗余信息，降低传递这些不必要的信息的开销，从而提高整个传输链路的有效性。在这个过程中，对冗余信息的界定和处理是信源编码的核心问题，那么首先需要对这些冗余信息的来源进行分析，接下来才能够根据这些冗余信息的不同特点设计和采取相应的压缩处理技术进行高效的信源编码。简言之，信息的冗余来自两个主要的方面：首先是信源的相关性和记忆性。这类降低信源相关性和记忆性编码的典型例子有预测编码、变换编码等；其次是信宿对信源失真具有一定的容忍程度。这类编码的直接应用有很大一部分是在对模拟信源的量化上，或连续信源的限失真编码。可以把信源编码看成是在有效性和传递性的信息完整性（质量）之间的一种折中有段。 信源编码的基本原理： 信息论的创始人香农将信源输出的平均信息量定义为单消息（符号）离散信源的信息熵： 香农称信源输出的一个符号所含的平均信息量为 为信源的信息熵。 通信原理中对信源研究的内容包括3个方面： ∑=-=L i i i x p x p x H 12) (log )()() (x H
霍夫曼信源编码实验报告
实验1：霍夫曼信源编码综合设计 【实验目的】 通过本专题设计，掌握霍夫曼编码的原理和实现方法，并熟悉利用C语言进行程序设计，对典型的文本数据和图像数据进行霍夫曼编解码。 【预备知识】 1、熵的概念，霍夫曼编码原则 2、数据结构和算法设计 3、C(或C++)编程语言 【实验环境】 1、设备：计算机一台 2、软件：C程序编译器 【设计要求】 根据霍夫曼编码原则，利用C语言设计并实现霍夫曼编码和解码程序，要求能够对给出的典型文本数据和图像数据进行霍夫曼编解码，并计算相应的熵和压缩比。 【实验原理】 Huffman编码属于熵编码的方法之一，是根据信源符号出现概率的分布特性而进行的压缩编码。 Huffman编码的主要思想是：出现概率大的符号用长的码字表示；反之，出现概率小的符号用短的码字表示。 Huffman编码过程描述： 1. 初始化: 将信源符号按出现频率进行递增顺序排列，输入集合L; 2. 重复如下操作直至L中只有1个节点: (a) 从L中取得两个具有最低频率的节点，为它们创建一个父节点； (b) 将它们的频率和赋给父结点，并将其插入L; 3. 进行编码： 从根节点开始，左子节点赋予1，右节点赋予0，直到叶子节点。 【基本定义】
1. 熵和平均编码符号长度 熵是信息量的度量方法，它表示某一事件出现的概率越小，则该事件包含的信息就越多。根据Shannon 理论，信源S 的熵定义为2()log (1/)i i i H s p p =∑,其中i p 是符号i S 在S 中出现的概率；2log (1/)i p 表示包含在i S 中的信息量，也就是编码i S 所需要的位数 假设符号i S 编码后长度为l i (i=1,…,n)，则平均编码符号长度L 为：i i i L p l =∑ 2. 压缩比 设原始字符串的总长度为L orig 位,编码后的总长度为L coded 位，则压缩比R 为 R = (L orig - L coded )/ L orig 【例子】 有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A 、B 、C 、D 和E 表示，40个象素中出现灰度A 的象素数有15个，出现灰度B 的象素数有7个，出现灰度C 的象素数有7个等等，如表1所示。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。 根据Shannon 理论，这幅图像的熵为 H (S ) = (15/40)?2log (40/15)+(7/40)?2log (40/7)+ +(5/40)?2log (40/5)=2.196 平均编码符号长度L 为(15/40)*1+(7/40)*3+(7/40)*3+(6/40)*3+(5/40)*3 ＝ 2.25 根据霍夫曼编码原则可以得到如下的霍夫曼编码表。 霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A ，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代
《信息论与信源编码》实验报告
《信息论与信源编码》实验报告 1、实验目的 (1) 理解信源编码的基本原理； (2) 熟练掌握Huffman编码的方法； (3) 理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。 2、实验设备与软件 (1) PC计算机系统 (2) VC++6.0语言编程环境 (3) 基于VC++6.0的图像处理实验基本程序框架imageprocessing_S (4) 常用图像浏览编辑软件Acdsee和数据压缩软件winrar。 (5) 实验所需要的bmp格式图像（灰度图象若干幅） 3、实验内容与步骤 (1) 针对“图像1.bmp”、“图像2.bmp”和“图像3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的编码效率和压缩比。 (2) 利用图像处理软件Acdsee将“图像1.bmp”、“图像2.bmp”和“图像 3.bmp”转换为质量因子为10、50、90的JPG格式图像（共生成9幅JPG图像），比较图像格式转换前后数据量的差异，比较不同品质因素对图像质量的影响； (3) 数据压缩软件winrar将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”分别生成压缩包文件，观察和分析压缩前后数据量的差异； (4) 针对任意一幅图像，比较原始BMP图像数据量、Huffman编码后的数据量（不含码表）、品质因素分别为10、50、90时的JPG文件数据量和rar压缩包的数据量，分析不同编码方案下图像数据量变化的原因。 4、实验结果及分析 (1)在VC环境下，添加代码构造Huffman编码表，对比试验结果如下： a.图像1.bmp：
无失真信源编码
第3章无失真信源编码 教学内容包括：信源编码概述、定长编码、变长编码常用的信源编码 3．1信源编码概述 讲课内容： 1、信源编码及分类 2、信源编码定义 3、信源编码基础 1、给出编码译码示意图 2、编码：信源编码、信道编码。 信源 = 信息 + 冗余 信源编码：针对信源的编码，能更加有效地传输、存储信息。编码后尽可能减少所需信息的损失，提高编码后携带信息的效率。 3、信源编码的主要任务 a、减少冗余 b、提高编码效率 4、信源编码的基本途径 a、解除相关性
b 、概率均匀化 4、信源编码的两个基本定理 a 、无失真编码定理（可逆编码的基础、只适用于离散信源） b 、限失真编码定理（连续信源） 5、信源编码的分类 a 、冗余度压缩编码，可逆压缩，经编译码后可以无失真地恢复。 统计特性：Huffman 编码，算术编码Arithmetic Coding b 、熵压缩编码，不可逆压缩 压缩超过一定限度，必然带来失真 允许的失真越大，压缩的比例越大 译码时能按一定的失真容许度恢复，保留尽可能多的信息 本章讨论离散信源无失真编码，包括定长、变长无失真编码定理和编码方法，以及几种实用的无失真信源编码，如香农编码、费诺编码、哈夫曼编码等。 6、信源编码的定义 首先给出信源编码的定义， 信源编码就是从信源符号到码符号的一种映射f ，它把信源输出的符号u i 变换成码元序列w i 。 f ：u i ——>w i ，i =1，2，…，q 译码是从码符号到信源符号的映射。若要实现无失真编码，这种映射必须是一一对应的、可逆的。 给出马元、码字、马块、二元编码的概念
结合P34例3.1.1给出编码的分类如下： 给出平均码长的定义和公式。 结合P34例3.1.1进行二进制信源的简单编码，并计算平均码长。 3．2克拉夫特（Kraft）不等式 讲课内容： 1、变长码的码字分离技术 2、即时码的引入和码树表示方法 3、即时码与克拉夫特不等式 1、变长码的码字分离技术 a、同步信号 b、可分离码字 2、即时码和码树表示法 即时码是一种实时的惟一可译码，这类码无需另加同步信息，就能在接收端被分离出来。在信源编码和数据压缩中，这类编码无论在理论还是在实际中都有很大意义，对较简单的信源，可以很方便地用码树法直接且直观地构造出可以分离码（异前缀码）。
实验三 无失真信源编码
实验三 无失真信源编码 一、[实验目的] 1、理解香农第一定理指出平均码长与信源之间的关系； 2、加深理解香农编码具有的重要的理论意义。 3、掌握霍夫曼编码的原理； 4、掌握霍夫曼编码的方法和步骤； 二、[实验环境] windows XP,MATLAB 7 三、[实验原理] 香农第一定理： 设离散无记忆信源为 12 (1) (2)....()S s s sq P p s p s p sq ????=???????? 熵为H(S)，其N 次扩展信源为 12 (1) (2)....()N q S p p p q P αααααα????=???????? 熵为H(S N )。码符号集X=（x1,x2,…,xr ）。先对信源N S 进行编码，总可以找 到一种编码方法，构成惟一可以码，使S 中每个信源符号所需的平均码长满足： 1N L H S H S N N +>≥（）（）logr logr 当N →∞时 lim ()N r N L H S N →∞= N L 是平均码长 1 ()N q N i i i L p αλ==∑ i λ是i α对应的码字长度 四、[实验内容] 1、在给定离散无记忆信源 S P s1 s2 s3 s4 1/8 5/16 7/16 1/8 =
条件下，实现二进制霍夫曼编码，求最后得到的码字并算出编码效率。 五、[实验过程] 每个实验项目包括：1)设计思路2)实验中出现的问题及解决方法； 某一离散信源概率分布：p=[1/2,1/4,1/8,1/16,1/16] 求信源的熵，并对该信源进行二元哈夫曼编码，得到码字和平均码长以及编码效率。 Matlab程序： function [h,l]=huffman(p) p=[1/2 1/4 1/8 1/16 1/16]; if length(find(p<0))~=0, error('Not a prob.vector,there is negative component') end if abs (sum(p)-1)>10e-10 error('Input is not a prob.vector,the sun of the components is not equal to 1') end n=length(p); q=p; m=zeros(n-1,n); for i=1:n-1 [q,l]=sort(q); m(i,:)=[l(1:n-i+1),zeros(1,i-1)]; q=[q(1)+q(2),q(3:n),1]; end for i=1:n-1 c(i,:)=blanks(n*n); end c(n-1,n)='0'; c(n-1,2*n)='1'; for i=2:n-1
信源编码-PCM非均匀量化与编码实验报告(完成版)
PCM非均匀量化与编码 实验报告
一、实验目的 (1). 了解模拟信号数字化的三个基本步骤：抽样、量化、编码。 (2). 抽样频率、量化级数对信号数字化的影响. (3). 加深对非均匀量化的理解。 (4). 理解信息速率与抽样量化编码的关系。 (5). 掌握MATLAB语言的函数调用，提高编程编程能力,，为之后的学习做准备。 二、实验内容： 对模拟信号进行抽样、量化并进行13折线PCM编码，运用Matlab软件实现PCM编码全过程。 三、实验步骤与结果 1、抽样： 产生一个周期的正弦波x(t)=1024cos(2πt)mv ，分别以4HZ和32Hz的频率进行采样用plot函数在绘出原信号和抽样后的信号序列(可用stem函数)。(4Hz保存为图1，32Hz保存为图2) function sample(f) t=0:1/f:1; y=1024*cos(2*pi*t); stem(t,y,'b','filled'); hold on; T=1:0.01:1; Y=1024*cos(2*pi*T); plot(T,Y,'r');
2、均匀量化： 对以32Hz的抽样频率进行抽样后的信号的绝对值分别进行8级和2048级均匀量化。在同一张图上绘出正弦波波形(用plot函数)、量化图(用stairs函数)。(保存为图3) function y=Even(n,m) t=0:1/m:1; x=1024*cos(2*pi*t); a=-1024:2048/n:1024; for i=1:m+1 for j=1:n if (x(i)>=a(j)&x(i)<=a(j+1)) y(i)=(a(j)+a(j+1))/2; end end end y=y/max(y); if(n==8) stairs(t,y,'b'); end if(n==2048) stairs(t,y,'k') end axis([0 1 -1.5 1.5]); hold on;
信源编码实验报告
电子科技大学 实验报告 课程名称信息论与编码 实验名称信源编码 任课教师 姓名学号 时间2018 年11月28 日 一、实验目的和要求 1.掌握对信源变长编码定理的理解； 2.掌握信源编码技术，如香农编码，费诺编码，哈夫曼编码或其他无失真信源 编码技术； 3.对英文小说“Game of Thrones”中出现的26个英文字母和空格符号（一共 27个符号）进行信源编码。 4.至少对前两章“Prologue”和“Bran”中出现的符号进行统计。 5.任意选择一种编程平台，C++，Java，Python，Matlab等等。 6.运行程序后，能够在屏幕上显示每一个符号对应的码字，原始信源的熵，平 均码字长度，码字长度的方差，以及编码效率。
二、 实验内容 1. 对英文小说“Game of Thrones ”中出现的26个英文字母和空格符号（一共27个符号）进行信源编码。 2. 在屏幕上显示每一个符号对应的码字，原始信源的熵，平均码字长度，码字长度的方差，以及编码效率。 三、 实验原理 1. 采用哈夫曼编码完成实验要求 2.哈夫曼（Haveman ）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。 离散无记忆信源： 例如 Uu 1u 2u 3u 4u 5 P (U ) = 0.4 0.2 0.2 0.1 0.1
第五章 信源编码(第十讲)
第五章 信源编码（第十讲） （2课时） 主要内容：（1）编码的定义（2）无失真信源编码 重点：定长编码定理、变长编码定理、最佳变长编码。 难点：定长编码定理、哈夫曼编码方法。 作业：5。2，5。4，5。6； 说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。 通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。 一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。 §3.1 编码的定义 编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。 讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图 3.1是一个信源编码器，它的输入是信源符号},,,{21q s s s S =，同时存在另一符号 },,,{21r x x x X =，一般来说，元素小姐xj 是适合信道传输的，称为码符号（或者码元）。 编码器的功能就是将信源符号集中的符号s i （或者长为N 的信源符号序列）变换成由x j (j=1,2,3,…r)组成的长度为l i 的一一对应的序列。 输出的码符号序列称为码字，长度l i 称为码字长度或简称码长。可见，编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。 码符号的分类： 下图是一个码分类图
2.10常用信源编码
2.10常用信源编码 信源编码也称为有效性编码，通过编码的方式，压缩信源的冗余度，从而提高了了通信的有效性。 2.10.1山农—费诺编码 山农—费诺编码是一种常见的信源编码，其编码的步骤如下： (1)将信源的符号按其概率从大到小排列。 (2)将这一列符号分成尽可能概率接近或相同的两组。 (3)上面一组符号编为0，下面一组符号编为1，或反之。 (4)已分的组再按（2）、（3）步骤重复做，直至不能再分组。 (5)自左至右写出各码字。 [例2.10.1]有一单符号离散无记忆信源X如下，要求进行山农—费诺编码
因为信源有8个符号，其理论最大熵为lb8=3比特/符号，而实际熵为2.55比特/符号，如采用三位二进制等长编码，则效率η=2.55/3 = 85%，或者说采用定长编码效率较低。如采用山农—费诺编码，则效率会提高不少。 2.10.2哈夫曼编码 哈夫曼编码是效率比较高的又一种无失真信源编码，二进制哈夫曼编码步骤如下： (1) 把信源符号按概率从大到小排成一列； (2) 把概率最小的两个分成一组，上面一个编为0，下面一个编为1，并将这两个符号的概率加起来，其结果再和尚未处理过的符号重新按大小排序； (3) 重复步骤2，直到所有信源符号都处理完。 (4) 从右向左依据编码路径返回，就得到各码字。 [例2.10.2]同前例,编码过程见下图2.10.2：（PPT 001第四章）
第五节香农编码 ? 设离散无记忆信源 ? 二进制香农码的编码步骤如下：?将信源符号按概率从大到小的顺序排列，为方便起见，令p (x 1)≥p (x 2)≥…≥p (x n )?令p (x 0)=0，用p a (x j )，j =i +1表示第i 个码字的累加概率，则： ?确定满足下列不等式的整数k i ，并令k i 为第i 个码字的长度?－log 2p (x n )≤k i <－log 2p (x n )+1 ? 将p a (x j ) 用二进制表示，并取小数点后k i 位作为符号x i 的编码。 1 ()(),1,2,,j a j i i p x p x j n -== =∑ 121 12,,,,,,()1 (), (), , (), , ()()n i n i i i n x x x x X p x p x p x p x p x P X =????==? ???????∑ 2.10.3冗余位编码 冗余的信息完全可以不全部传送（压缩掉），从而提高了传输效率。 1．L —D 编码 现在来讨论一种由林绪（Lynch ）和达维生（Davission ）分别独立提出的冗余位编码法，称为L —D 编码。 例如有一二元序列，其中的一串000100000001000共二进制15位，其余的也可分割成15位一串，称为一帧。现在研究压缩冗余的方法。显然对该帧可确切描述为： （1） 帧长为15。
实训二 信源编码和信道编码
实训二信源编码和信道编码 一、实验内容 1、对抽样信号进行均匀量化，改变量化级数和信号大小，根据MATLAB仿真获得量化误差和量化信噪比。 2、对抽样信号进行A律压缩、均匀量化，改变量化级数和信号大小，根据MATLAB仿真获得量化误差和量化信噪比。 3、限失真信源编码：采用Ａ律１３折线编码 二、程序和仿真图 1. close all; fs=1000; t=0:1/fs:1; x=0.99*sin(2*pi*t); plot(t,x); hold on; M=8; delta=2/M; y_level=floor(abs(x/delta)); signal=sign(x); for k=1:1000; for i=0:7; if x(1,k)>=-1+i*delta&x(1,k)<=-1+(i+1)*delta; Q=signal.*(y_level*delta+delta/2); end; end; end; plot(t,Q,'r'); grid on; title('原信号与均匀量化信号');
close all; fs=32; t=0:1/fs:1; x=sin(2*pi*t); subplot(2,1,1); plot(t,x);hold on; stem(t,x,'filled','r'); title('采样样值和8级均匀量化后的样值');grid on; M=8; deta=2/M; y_level=fix(abs(x/deta)); signal=sign(x); Q=signal.*(y_level*deta+deta/2); Q_error=x-Q; S=mean(x.^2); N=mean(Q_error.^2); stem(t,Q,'filled','b'); legend('输入信号','采样量值','量化后量值'); subplot(2,1,2); stem(t,Q_error,'filled','r'); title('量化误差图');grid on;
信源编码作业 答案
1 证明： 均匀分布，均匀量化器时 设[a,b]内量化电平数为m 则量化间隔Δ=(b ?a)M ? 分层电平x k =a +??k k =1,2,?M 量化器输出y k =(x k +x k?1)2?=a +??k ??2? 量化噪声N q =E [eq 2] = ∑∫(x ?y k )2 x k x k?1p(x)dx M k=1=?2 12 最佳量化器时，使量化噪声平均功率最小 必要条件为Lloyd-Max 条件 由上边计算均匀分布时，均匀量化的量化噪声N q =?2 12 计算得{eN q ex k =0 eN q ey k =0 , k =1,2,?M 满足Lloyd-Max 条件，使均方误差最小 且分层电平在相邻重建电平的中点 重建电平在量化间隔的概率质心上 满足最佳量化的条件。 故在均匀分布时，均匀量化即是最佳量化，两种量化方法的输出表达式一致。 2 解： 由题知，最小量化间隔1量化单位为1/2048 128为正值，则第一位为1 而128=16+16+32+64,，故在第五段的起始位置。 2-4位为100 又其在第五段起始，故5-8位为0000 综上，码组为11000000。
习题1、有一个一阶平稳马尔可夫链X 1，X 2，…,X r ,…,各X r 取值于集A={a 1，a 2，a 3}。已知起始概率p(a i )为：p 1=1/2, p 2= p 3=1/4, 转移概率如右下表所示，求： （1） X 1 X 2的联合熵和平均符号熵。 （2） 这个链的极限平均符号熵。 （3） 解： (1). H (X 1,X 2)=?∑∑P(a i ,a j )logP(a i ,a j ) 2 j=02i=0 =?(1 4log 1 4+2×1 8log 1 8+2×1 6log 1 6+2×1 12log 1 12)=2.71bit 平均符号熵H 2(X )=12H (X 1,X 2)=1.35bit . (2). 设信源稳态符号概率分布W =(w 1,w 2,w 3) 由{WP =W w 1+w 2+w 3=1 ，解得{w 1=4/7 w 2=3/14w 3=3/14。 H 3=4 7H (X |s 1)+3 14H (X |s 2)+3 14H (X |s 3)=1.25. (3). H 0=H max =log3=1.585bit . H 1=H (X 1)=1.5bit . H 2=1 2H (X 1,X 2)=1.355bit . 冗余度分别为： R 0=0. R 1=1?H 1 H 0?=0.054. R 2=1? H 2 H 0 ?=0.145.
《数据压缩与信源编码》实验指导书
《数据压缩与信源编码》实验指导书 适用专业:信息工程 课程代码: 6088619 总学时: 40 总学分: 2.5 编写单位:电气与电子信息学院 编写人:李斌 审核人: 审批人: 批准时间: 2015 年 11 月 10日
目录 实验一码书的设计和使用 (2) 实验二基于DCT变换的图像压缩技术 (8) 实验三基于小波变换的图像压缩技术 (15)
实验一 码书的设计和使用 一、实验目的 采用矢量量化算法（LBG ）获得图像压缩所需要的码书，通过码书实现图像压缩编码。 二、实验内容 对给定的一幅图像进行码书设计、编码和解码。 三、实验仪器、设备及材料 操作系统：Windowsxp ； 软件：MA TLAB 四、实验原理 要想得到好的性能编码，仅采用标量量化是不可能的。当把多个信源符号联合起来形成多维矢量，再对矢量进行标量量化时自由度将更大，同样的失真下，量化基数可进一步减少，码率可进一步压缩。这种量化叫矢量量化。 一种有效和直观的矢量量化码书设计算法——LBG 算法(也叫GLA 算法)是由Linde 、Buzo 和Gray 于1980年首先提出来的。该算法基于最佳矢量量化器设计的最佳划分和最佳码书这两个必要条件，且是Lloyd 算法在矢量空间的推广，其特点为物理概念清晰、算法理论严密及算法实现容易。 设训练矢量集为{}110,,,-=M x x x X ，待产生的码书为{}110,,,-=N y y y C ，其中{})1(10,,,-=k i i i i x x x x ，{})1(10,,,-=k j j j j y y y y ，10,10-≤≤-≤≤N j M i ，则码书设计过程就是需求把训练矢量集X 分成N 个子集)1,,1,0(-=N j S j 的一种最佳聚类方案，而子集j S 的质心矢量j y 作为码字。假设平方误差测度用来表征训练矢量i x 和码字j y 之间的失真，即： ∑-=-=1 02)(),(k l jl il j i y x y x d 则码书设计的准则可用下列数学形式表达： 最小化 ∑∑-=-==101 0),(),,(N j M i j i ij y x d w C X W f 约束条件 ∑-==101N j ij w ，10-≤≤M i 其中W 为N M ?矩阵，其元素满足：
信源编码实验
实验2 信源编码实验 一、实验目的 ● 掌握香农、霍夫曼编码的方法和手段。 ● 通过信源编译码，理解香农第一定理。 二、实验原理 设离散无记忆信源 121 1 2,,,,,,()1(),(), , (), , ()()=?? ??==???????? ∑n i n i i i n x x x x X p x p x p x p x p x P X 二进制香农码的编码步骤如下： ? 将信源符号按概率从大到小的顺序排列，为方便起见，令 p (x 1)≥ p (x 2)≥…≥ p (x n ) ? 令p (x 0)=0，用p a (x j )，j =i +1表示第i 个码字的累加概率，则： 1 0()(),1,2, ,-===∑j a j i i p x p x j n ? 确定满足下列不等式的整数k i ，并令k i 为第i 个码字的长度 －log 2 p (x n )≤k i <－ log 2 p (x n )+1 ? 将p a (x j ) 用二进制表示，并取小数点后k i 位作为符号x i 的编码。 霍夫曼编码步骤如下： ? 将信源符号按概率从大到小的顺序排列，令 p (x 1)≥ p (x 2)≥…≥ p (x n ) ? 给两个概率最小的信源符号p (x n -1)和p (x n )各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n －1)个信源符号的新信源。称为信源的第一次缩减信源，用S 1表示。 ? 将缩减信源S 1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n －2)个符号的缩减信源S 2。 ? 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
信息论与信源编码实验报告
《信息论与编码》实验报告 1 实验目的 (1) 理解信源编码的基本原理； (2) 熟练掌握Huffman编码的方法； (3) 理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。 2 实验设备与软件 (1) PC计算机系统 (2) VC++6.0语言编程环境 (3) 基于VC++6.0的图像处理实验基本程序框架imageprocessing (4) 常用图像浏览编辑软件Acdsee和数据压缩软件winrar。 (5) 实验所需要的bmp格式图像（灰度图像若干幅） 3 实验内容与步骤 (1) 针对“图像1.bmp”、“图像2.bmp”和“图像3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的编码效率和压缩比。 (2) 利用图像处理软件Acdsee将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”转换为质量因子为10、50、90的JPG格式图像（共生成9幅JPG图像），比较图像格式转换前后数据量的差异，比较不同品质因素对图像质量的影响； (3) 数据压缩软件winrar将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”分别生成压缩包文件，观察和分析压缩前后数据量的差异； (4) 针对任意一幅图像，比较原始BMP图像数据量、Huffman编码后的数据量（不含码表）、品质因素分别为10、50、90时的JPG文件数据量和rar压缩包的数据量，分析不同编码方案下图像数据量变化的原因。 4 实验总结分析
实验步骤（1）： 实验代码： void CImageProcessingDoc::OnImageHuffman() { // TODO: Add your command handler code here int m_Width, m_Height, m_SaveWidth; int i,j,k; int *b; double *a,acl=0,size=0,ratio=0,ce=0,e=0;//acl:average code length(平均码长);ce:code efficiency（编码效率）;e:entropy（信息熵）;size:图像大小；ratio：压缩比； long s=0; b=new int[256]; a=new double[256]; for (i=0; i<256; i++) { b[i]=0;a[i]=0; } m_Width = m_pDibInit->GetWidth(); m_Height = m_pDibInit->GetHeight(); m_SaveWidth = m_pDibInit->GetSaveWidth(); for(j=0;j 实验六 信源编码仿真实现 一、实验目的 理解信源编码的思想，掌握信源编码的编程实现原理及技术。 二、实验原理 信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 1 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，– 可做到无失真编码； 连续信源编码：独立信源编码，– 只能做到限失真信源 编码； 相关信源编码：非独立信源编码。 ()log l H S N r ε +≥ （等长信源编码定理） 一个熵为H(S)的离散无记忆信源，若对其N 次扩展信源进行等长r 元编码，码长为l ，对于任意 大于0，只要满足 当N 无穷大时，则可以实现几乎无失真编码，反之，若： ()2log l H S N r ε -≤ 则不可能实现无失真编码，当N 趋向于无穷大是，译码错误率接近于1。 log ()l r NH S > 若条件式可写成： 左边表示长为 的码符号所能载荷的最大信息量，而右边代表长为N 的序列平均携带的信息量。因此，只要码字传输的信息量大于信源序列携带的信息量，总可以实现无失真编码 。 log ()l r H S N ε≥+ 若条件式可写成： 'log l R r N = 为了衡量编码效果，引进 ' ()() log H S H S l R r N η= = 最佳编码效率为： 1() H S η εη -= '()()()H S H S R H S ηε= =+ 12,,...,q W W W 1 212...... q n a a a X p p p P ????=???????? 12,,...,q l l l 1 ()q i i i L P S l ==∑ 无失真变长信源编码定理（香农第一定理）实验六信源编码仿真实现