海明编码实验报告
海明编码实验报告
学科专业：计算机科学与技术
姓名：
学号：
指导教师：
天津工业大学计算机科学与技术学院
二零一零年十二月
一．海明编码原理
海明码是一种可以纠正一位差错发现两位差错的编码。它是利用在信息位为k 位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：
２r>=n+1 或 2r>=k+r+1
海明码的编码效率为：
R=k/(k+r)
式中 k为信息位位数
r为增加冗余位位数
2.海明码的生成与接收
二．海明编码方法
1）海明码的生成（顺序生成法）。
例3.已知：信息码为：" 1 1 0 0 1 1 0 0 " (k=8)
求：海明码码字。
解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码
码字:" A B 1 C 1 0 0 D 1 1 0 0 "
码位: 1 2 3 4 5 6 7 8 9 10 11 12
其中A,B,C,D分别插于2k位(k=0,1,2,3)。码位分别为1,2,4,8。
2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)
A->1,3,5,7,9,11；
B->2,3,6,7,10,11；
C->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)
D->8,9,10,11,12。
3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：
A=∑(0,1,1,0,1,0)=1
B=∑(0,1,0,0,1,0)=0
C=∑(0,1,0,0,0)=1
D=∑(0,1,1,0,0)=0
4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"
2)海明码的接收。
例.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=8)
求：发送端的信息码。
解： 1)设错误累加器(err)初值=0
2)求出冗余码的偶校验和，并按码位累加到err中：
A=∑(1,0,1,0,1,0)=1 err=err+20=1
B=∑(0,0,0,0,1,0)=1err=err+21=3
C=∑(1,1,0,0,0)=0 err=err+0 =3
D=∑(0,1,1,0,0)=0 err=err+0 =3
由err≠0可知接收码字有错，
3)码字的错误位置就是错误累加器(err)的值3。
4)纠错--对码字的第3位值取反得正确码字：
"1 0 1 1 1 0 0 0 1 1 0 0"
5)把位于2k位的冗余码删除得信息码："1 1 0 0 1 1 0 0" 3）发现两位差错
P5=∑(1，2,3,4,5,6,7,8,9,10,11,12)
S5=∑(1，2,3,4,5,6,7,8,9,10,11,12，P5)
如果err≠0且S5=0是两位错。
三．程序
import java.applet.*;
import java.awt.*;
import java.awt.event.*;
public class Haiming extends Applet implements ActionListener{ Label fsxx;
Label xybm;
Label xdbm;
Label xdgr;
Label xdym;
Label cc;
Label xyym;
Label sdxx;
TextField tfxx;
TextField txybm;
TextField txdbm;
TextField txdgr;
TextField txdym;
TextField tcc;
TextField txyym;
TextField tsdxx;
public void init(){
fsxx = new Label("发送信息:");
xybm = new Label("信源编码:");
xdbm = new Label("信道编码:");
xdgr = new Label("信道干扰:");
xdym = new Label("信道译码:");
cc = new Label("一/二错:");
xyym = new Label("信源译码:");
sdxx = new Label("收到信息:");
tfxx = new TextField(30);
txybm = new TextField(30);
txdbm = new TextField(30);
txdgr = new TextField(30);
txdym = new TextField(30);
tcc = new TextField(30);
txyym = new TextField(30);
tsdxx = new TextField(30);
setLayout(new GridLayout(8,2));
add(fsxx);add(tfxx);
add(xybm);add(txybm);
add(xdbm);add(txdbm);
add(xdgr);add(txdgr);
add(xdym);add(txdym);
add(cc);add(tcc);
add(xyym);add(txyym);
add(sdxx);add(tsdxx);
tfxx.addActionListener(this);
txdgr.addActionListener(this);
}
public void actionPerformed(ActionEvent e){
String sfsxx,erjz,sxdbm,sxdgr,sxdym;
int sjs,i,count = 0,j = 0,m = 0,count1 = 0,count2 = 0,count3 = 0;
double err = 0,sum = 0;
char xx,a = '0',b = '0',c = '0',d = '0',s5 = '0';
char[] C = new char[12]; //放海明码
char[] C1 = new char[12]; //放信道干扰码
char[] S = new char[4]; //放s1到s4
char[] C2 = new char[8]; //放信源译码
char[] C3 = new char[1]; //放收到的信息
sfsxx = tfxx.getText(); //获得输入信息
xx = sfsxx.charAt(0);
sjs = xx - '0' + 48;
erjz = '0' + Integer.toBinaryString(sjs);//将其转换成二进制字符串
txybm.setText(erjz);
for(i = 0;i<12;i++){ //将p1,p2,p3,p4放在字符数组中，并赋初值'0'
if(i == 0||i == 1||i == 3||i == 7)
C[i] = '0';
else
C[i] = erjz.charAt(j++);
}
for(i = 0;i<12;i = i + 2){ //求出p1
if(C[i] == '1')count++;
if(count % 2 == 1)a = '1';
else a = '0';
}
count = 0;
for(i = 0;i<12;i++){ //求出p2,p3,p4
if(i == 1||i == 2||i == 5||i == 6||i == 9||i == 10)
if(C[i] == '1')count1++;
if(count1 % 2 == 1)b = '1';
else b = '0';
if(i == 3||i == 4||i == 5||i == 6||i == 11)
if(C[i] == '1')count2++;
if(count2 % 2 == 1)c = '1';
else c = '0';
if(i == 7||i == 8||i == 9||i == 10||i == 11)
if(C[i] == '1')count3++;
if(count3 % 2 == 1)d = '1';
else d = '0';
}
count = 0;
count1 = 0;
count2 = 0;
count3 = 0;
for(i = 0;i<12;i++){ //把p1,p2,p3,p4的新值放到字符数组中
if(i == 0)
C[i] = a;
if(i == 1)
C[i] = b;
if(i == 3)
C[i] = c;
if(i == 7)
C[i] = d;
}
sxdbm = String.copyValueOf(C); //把字符数组转换成字符串txdbm.setText(sxdbm); //把字符串输出到文本框中sxdgr = txdgr.getText();
for(i = 0;i<12;i++){
C1[i] = sxdgr.charAt(i);
}
for(i = 0;i<12;i = i + 2){ //求出s1
if(C1[i] == '1')count++;
if(count % 2 == 1)S[0] = '1';
else S[0] = '0';
}
count = 0;
for(i = 0;i<12;i++){ //求出s2,s3,s4 if(i == 1||i == 2||i == 5||i == 6||i == 9||i == 10) if(C1[i] == '1')count1++;
if(count1 % 2 == 1)S[1] = '1';
else S[1] = '0';
if(i == 3||i == 4||i == 5||i == 6||i == 11)
if(C1[i] == '1')count2++;
if(count2 % 2 == 1)S[2] = '1';
else S[2] = '0';
if(i == 7||i == 8||i == 9||i == 10||i == 11)
if(C1[i] == '1')count3++;
if(count3 % 2 == 1)S[3] = '1';
else S[3] = '0';
}
count = 0;
for(i = 0;i<12;i++){ //求s5
if(C[i] == '1')count++;
}
for(i = 0;i<12;i++){ //求s5
if(C1[i] == '1')count++;
}
if(count%2 == 0)s5 = '0';
else
s5 = '1';
for(i = 0;i<4;i++){ //判断是否出现错误，出现几位错误
if(S[i]!='0')
err = err + Math.pow(2, i);
}
if(err==0)tcc.setText("正确");
else
if(s5!='0')
tcc.setText("第"+(int)err+"位出错");
else tcc.setText("两位出错");
if(err!=0)if(C1[(int)(err-1)]=='0')C1[(int)(err-1)] = '1'; //将错误改过来，得到信道译码
else C1[(int)(err-1)] = '0';
sxdym = String.copyValueOf(C1);
txdym.setText(sxdym);
for(i = 0;i<12;i++){ //得到信源译码
if(i == 0||i == 1||i == 3||i == 7)continue;
else
C2[m++] = C1[i];
}
txyym.setText(String.copyValueOf(C2));
for(i = 0;i<8;i++){ //求得信源译码的十进制数if(C2[i]=='1')
sum = sum + Math.pow(2, 7 - i);
}
C3[0] = (char)(sum); //求出字符
if(err != 0&&s5 == '0' )
tsdxx.setText("");
else
tsdxx.setText(String.copyValueOf(C3));
}
}
四．程序执行结果
无干扰时：
一位出错时：
两位出错时：
参考文献
[1] 阳宪惠现场总线技术及其应用清华大学出版社
[2] 王行言java语言与面向对象程序设计清华大学出版社
[3] Thinking in Java
数据结构 哈夫曼编码实验报告
实验报告 实验课名称：数据结构实验 实验名称：文件压缩问题 班级：20132012 学号：姓名：时间：2015-6-9 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 二、数据结构设计 首先定义一个结构体： struct head { unsigned char b; //记录字符 long count; //权重 int parent,lch,rch; //定义双亲，左孩子，右孩子 char bits[256]; //存放哈夫曼编码的数组 } header[512],tmp; //头部一要定设置至少512个,因为结 点最多可达256,所有结点数最多可 达511 三、算法设计 输入要压缩的文件读文件并计算字符频率根据字符的频率，利用Huffman 编码思想创建Huffman树由创建的Huffman树来决定字符对应的编码，进行文件的压缩解码压缩即根据Huffman树进行译码 设计流程图如图1.1所示。
图1.1 设计流程图 (1)压缩文件 输入一个待压缩的文本文件名称(可带路径)如:D:\lu\lu.txt 统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进行编码,生成压缩文件。压缩文件名称=文本文件名.COD 如:D:\lu\lu.COD 压缩文件内容=哈夫曼树的核心内容+编码序列 for(int i=0;i<256;i++) { header[i].count=0; //初始化权重 header[i].b=(unsigned char)i; //初始化字符 } ifstream infile(infilename,ios::in|ios::binary); while(infile.peek()!=EOF) { infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符 header[temp].count++; //统计对应结点字符权重 flength++; //统计文件长度 } infile.close(); //关闭文件 for(i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面，编码时效率高 for(int j=0;j<256-1-i;j++) if(header[j].count 中南大学数据结构课程 姓名：刘阳 班级：信息0703 学号：0903070312 实验时间： 08.11.14 指导老师：赵颖 一、实验内容 根据输入的n 个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕。 二、实验说明 哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。 设二叉树具有n 个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL ，记作： WPL=k n k k L W *∑=1。在给定一组具有确定权值的叶结点，可以构造出不同的带权二 叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL 值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。 在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA ，电文中只含有A ，B ，C ，D 四种字符，若这四种字符采用下表所示的编码，则电文的代码为000010000100100111 000，长度为21。 在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。 采用哈夫曼树进行编码，也不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。 姓名关瀚文学号222012306022011专业应用心理学年级2012级课程实验心理学实验时间2013．11．6同组人姓名洪万里单宏宇成绩 短时记忆视觉编码实验 关瀚文 （西南大学心理学部，重庆，400715） 摘要本实验以西南大学心理学部2012级应用班的44名同学作为被试，每名被试运用PsyKey 心理教学系统 3.1，“短时记忆视觉编码”实验程序，进行以减数法探究短时记忆的视觉编码试验108次，本实验旨在重复posner等人的字母实验，验证短时记忆的视觉编码，并学习减法反应时方法。最后的结果显示，短时记忆的视觉编码确实存在，posner关于短时记忆的视觉编码理论得到验证。 关键词短时记忆减法反应时视觉编码 1引言减数法是一种用减法方法将反应时分解成各个成分，然后来分析信息加工过程的方法。减数法的反应时实验逻辑是如果一种作业包含另一种作业所没有的某个特定的心理过程，且除此过程之外二者在其他方面均相同，那么这两种反应时的差即为此心理过程所需的时间。 储存在短时记忆中的信息，传统的观点认为主要是语音听觉编码。这是根据短时记忆中产生的错误与正确信息之间存在着语音听觉上的联系而推测出来的。康拉德在记忆广度实验中观察到，回忆错误与正确反应之间有着语音上的联系。但是这个结论因为以拼音文字的英文字母做实验材料，因而其普遍性受到了质疑。但70年代波斯纳等人利用减法反应时基本范式，在其实验中清楚地表明，某些短时记忆信息可以有视觉编码和听觉编码两个连续的阶段，这是认知心理学史上的一个重大发现。莫雷的实验也表明，汉字的短时记忆以形状编码为主。对于绘画、脸和身体动作以及视觉观察事件所属范畴的短时记忆，倾向于用视觉编码的短时记忆，倾向于视觉编码和语义编码。现在一般认为，短时记忆信息存在感觉代码与语义代码，其中前者包括听觉代码与视觉编码；对于感觉编码的过程而言，视觉编码率先出现并保持一个短暂的瞬间，然后出现听觉编码。 实验二游程编码 一、实验目的 1、掌握游程编码原理； 2、理解数据编码压缩和译码输出编码的实现。 二、实验要求 实现游程编码和译码的生成算法。 三、实验内容 输入一幅二值图像，先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。 四、实验原理 1、xx 树的定义： 假设有n 个权值，试构造一颗有n 个叶子节点的二叉树，每个叶子带权值为wi ，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树； 2、xx 树的构造： weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性，即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node,将他们的data 相加，构造出新的HTNode作为他们的父节点，指针pare nt，leftchild，rightchild 赋相应值。在把这个新的节点插入最小堆。 按此步骤可以构造出一棵XX树。 通过已经构造出的哈夫曼树,自底向上,由频率节点开始向上寻找parent, 直到parent 为树的顶点为止。这样,根据每次向上搜索后,原节点为父节点的 左孩子还是右孩子，来记录 1 或0，这样，每个频率都会有一个01 编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。 五、实验程序 #include 实验二二叉树的遍历及霍夫曼编码 班级：计科1101班 学号：0909101605 姓名：杜茂鹏 2013年5月22日 一、实验目的 掌握二叉树的建立及遍历操作，霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1）初始化：从终端读入字符集大小n，以及n个字符和n个权值（或者读入字符集和频度数据文件），建立哈夫曼树，并将哈夫曼树存入到文件HfmTree 中。 2）编码：利用已建好的哈夫曼树（如果不在内存中，则从文件中读入），从文件ToBeTran中读入原文，对原文进行编码，将编码后的结果存入文件CodeFile 中。 3）译码：利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 4）打印：打印输出哈夫曼树，显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 四、概要设计 1）首先动态分配数组存储霍夫曼树及存储霍夫曼编码表，然后从终端或文件读入霍夫曼树的字符变量及其频度，初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2）从指定的文件succe.txt中读入原文，利用已经编好的霍夫曼树对其编码，将编码结果写入文件Coding.txt保存。 3）利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码，结果存入文件decoding.txt中。 五、测试数据： 2．原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树，对原文进行编码、译码 #include 哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 心理实验报告 1.题目 减法反应时－短时记忆的视觉编码 2.引言 R．Conrad(1964)的一项研究给被试视觉呈现字母，随后报告字母的实验结果表明，对于视觉呈现的字母，我们使用听觉编码而非视觉。而Posner等人（1969）的实验结果显示，被试对于不同字母对（Aa和AA）判断是否同一字母的反应时不同，这否定了对于视觉呈现的字母，我们只用听觉编码的观点。对于视觉编码和听觉编码的先后问题，现在普遍的观点是视觉编码在先。 根据R．Conrad的实验，研究者们还在探讨这样一个逻辑，如果一个作业包含另一个作业所没有的某个心理过程，而其它方面相同，则两个作业的反应时之差，即是这个心理过程所用的时间，也是这个心理过程存在的证据。 本实验研究作为一个验证性研究，为存在视觉编码提供证据之外，还将探讨在不同时间间隔下反应时差的差异的内部机理。 3.方法 3.1被试：心理系大三学生 3.2仪器材料：字母对AA、BB、Aa、Bb、AB、BA、Ab、Ba 3.3实验程序： 3.3.1：实验前被试阅读指导语，清楚不同判断的按键方式，尽量正确的判断，并尽快按键反应 3.3.2：第一次实验时，每对字母对随机出现6次，前12对时间间隔是0s,中间12对间隔0.5s,最后12对间隔2s。36次完毕后，被试休息30s。继续第二次实验，但这次时间间隔按0.5s-2s-0s进行；同样休息30s进行第三次实验，这次间隔按照2s-0s-5s进行。被试看到呈现的字母后，尽快正确判断字母是否相同，并尽快按相应的键。 4．结果 表a 各水平下被试平均正确反应时(ms) 间隔(ms) 音同形 同 音同形 异 音异 形异 0 561.59 707.00 777.95 500 519.05 681.79 734.54 2000 489.62 639.46 725.00 表b 各水平下被试平均正确率(%) 间隔 (ms) 音同形 同 音同形 异 音异 形异 0 97.86 91.88 90.38 500 98.08 92.95 89.53 2000 98.08 92.74 90.60 表a显示： 音同形同比音同形异、音异形异在各个间隔时间水平下的反应时均值都要小；（多因素方差分析） 每种音形水平在时间间隔上反应时存在显著差异（多因素方差分析） 表b显示： 音同形同比音同形异、音异形异在各个间隔水平下的正确率均值都要大。而同一音形水平下的各个时间间隔水平上正确率均值相差不大。 一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #define MAXBIT 10 姓名关瀚文学号222012306022011 专业应用心理学年级 2012级课程实验心理学实验时间2013．11．6 同组人姓名洪万里单宏宇成绩 短时记忆视觉编码实验 关瀚文 （西南大学心理学部，重庆，400715） 摘要本实验以西南大学心理学部2012级应用班的44名同学作为被试，每名被试运用PsyKey 心理教学系统 3.1，“短时记忆视觉编码”实验程序，进行以减数法探究短时记忆的视觉编码试 验108次，本实验旨在重复posner等人的字母实验，验证短时记忆的视觉编码，并学习减法反 应时方法。最后的结果显示，短时记忆的视觉编码确实存在，posner关于短时记忆的视觉编码 理论得到验证。 关键词短时记忆减法反应时视觉编码 1引言减数法是一种用减法方法将反应时分解成各个成分，然后来分析信息加工过程的方法。减数法的反应时实验逻辑是如果一种作业包含另一种作业所没有的某个特定的心理过程，且除此过程之外二者在其他方面均相同，那么这两种反应时的差即为此心理过程所需的时间。 储存在短时记忆中的信息，传统的观点认为主要是语音听觉编码。这是根据短时记忆中产生的错误与正确信息之间存在着语音听觉上的联系而推测出来的。康拉德在记忆广度实验中观察到，回忆错误与正确反应之间有着语音上的联系。但是这个结论因为以拼音文字的英文字母做实验材料，因而其普遍性受到了质疑。但70年代波斯纳等人利用减法反应时基本范式，在其实验中清楚地表明，某些短时记忆信息可以有视觉编码和听觉编码两个连续的阶段，这是认知心理学史上的一个重大发现。莫雷的实验也表明，汉字的短时记忆以形状编码为主。对于绘画、脸和身体动作以及视觉观察事件所属范畴的短时记忆，倾向于用视觉编码的短时记忆，倾向于视觉编码和语义编码。现在一般认为，短时记忆信息存在感觉代码与语义代码，其中前者包括听觉代码与视觉编码；对于感觉编码的过程而言，视觉编码率先出现并保持一个短暂的瞬间，然后出现听觉编码。 实验二十三 时分复用与解复用实验 实验项目一 256K 时分复用帧信号观测 （1）帧同步码观测：用示波器连接复用输出，观测帧头的巴克码。 （2）帧内PN 序列信号观测：用示波器接复用输出，利用储存功能观测3个周期 中的第一时隙的信号。 实验项目二 256K 时分复用及解复用 （1）帧内PCM 编码信号观测：将PCM 信号输入DIN2，观测PCM 数据。以帧同 思考题：PN15序列的数据是如何分配到复用信号中的？ 分析分时复用的实质，可知，在模拟传送时，一位用户的数据根据复用划分的时隙以一帧为周期，逐次将8位数据插入每个帧相同的时隙处。对于此次实验中的PN15序列，检测到帧同步信号的帧头时，便插入第一帧数据，在第二次检测到帧头时插入第二帧数据，以此类推，将信号分配到复用信号中，以达到提高信道利用率的目的。 对比观测实验出现的码元，发现为01110010，根据所学知识可知，这串码即为帧头的观测码。 步为触发分别观测PCM编码数据和复用输出的数据。 （2）解复用帧同步信号观测：PCM对正弦波进行编译码。观测复用输出与FSOUT， 观测帧同步上跳沿与帧同步信号的时序关系。 思考题：PCM数据是如何分配到复用信号中去的？ 时分多路复用以时间作为信号分割的参量，将各路输入变为变为并行数据，然后按照给端口数据所在的时隙进行帧的拼接，完成一个完整的数据帧。而在本实验中，PCM 的数据输入到DIN2，将其插入到复用信号的第2个时隙，与其它3个时隙拼接为一帧，从而实现了PCM信号分配到复用信号中。 上图分别为PCM编码输入和复用输出的波形。仔细观察可知，对比复用输入信号，复用输出有2帧的延时，且在复用输出的第0时隙为帧头的巴克码，第1时隙没有数据，第2时隙有了数据的存放，即PCM复用编码时被插在了一帧的第2时隙中，在解复用时先寻找巴克码，再按照每一帧的数据存放的相应的时隙进行解复用，之后拼接起来，便实现了PCM的数据恢复。 数据结构实验报告 实验名称：实验三哈夫曼树 学生姓名： 班级： 班内序号： 学号： 日期： 程序分析： 存储结构：二叉树 程序流程： template 2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链 表中字符的个数) 3.从字符串第2个字符开始，逐个取出字符串中的字符 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的 字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)） 算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其 下标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为 i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i 结点的双亲设置为空 4. 根据哈夫曼树创建编码表 减法反应时-短时记忆的视觉编码 记忆的加工水平 减法反应时实验 1、目的：检验短时记忆是否存在视觉编码 2、材料：4对字母：AA Aa BB Bb，装有Psykey心理教学系统的大学版的计算机，一号反应 键盘 3、过程： 给被试并排呈现两个字母，或同时呈现，或有一定间隔，让被试判断这两个字母是否相同并按键反应，记录反应时。 本实验所用字母对是AA（6次）、BB（6次）、Aa（6次）、Bb（6次）、AB（3次）、BA（3次）、Ab（3次）、Ba（3次），共出现36次，有三种呈现间隔：0s（即同时呈现）、50ms和100ms，采用如下拉丁方设计，即：第一次36张随机呈现，前12张间隔0s，中间12张间隔50s，最后12张间隔100ms；休息30s后再做36张，间隔时间按50ms→100ms→0s的顺序；第三次的36张则采用100ms→0s→50ms的顺序。 4、设计： 自变量：字母对的类型（AA BB Aa Bb）呈现时间的长短（0s 50ms 100ms） 因变量：判断的正确率以及辨别所需的时间 5、结果： ＝＝＝＝＝结果数据＝＝＝＝＝ ------------------------------------------------------------ 间隔音同形同音同形异音异形异 ------------------------------------------------------------ 0ms 650(100.00％) 716(100.00％) 768( 91.67％) 50ms 489(100.00％) 621(100.00％) 760(100.00％) 100ms 476(100.00％) 708(100.00％) 696( 91.67％) ------------------------------------------------------------ 本科生实验报告 实验课程信息论与编码 学院名称信息科学与技术学院 专业名称通信工程 学生姓名 学生学号 指导教师谢振东 实验地点6C601 实验成绩 二〇一五年十一月二〇一五年十一月 实验一：香农（Shannon ）编码 一、实验目的 掌握通过计算机实现香农编码的方法。 二、实验要求 对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。 三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、将信源消息符号按其出现的概率大小排列 )()()(21n x p x p x p ≥≥≥ 2、确定满足下列不等式的整数码长K i ； 1)(l o g )(l o g 22+-<≤-i i i x p K x p 3、为了编成唯一可译码，计算第i 个消息的累加概率 ∑ -== 1 1 )(i k k i x p p 4、将累加概率P i 变换成二进制数。 5、取P i 二进制数的小数点后K i 位即为该消息符号的二进制码。 四、源程序： #include int i,j; for(i=0;i 《短时记忆的视觉编码》实验报告 1 引言 实验逻辑 此次实验是根据短时记忆是以听觉编码为主的原理，该原理可以得出如果字母发音不同，被试的反应时会存在差异的推论。那么该实验就是要通过同时控制字母形状和发音形成的三个实验水平a1、a2、a3(其中a1：字母形状发音都相同，a2：字母形状不同但发音相同，a3：字母形状发音都不同)，实验旨在通过三个不同水平下的比较，探索视觉编码是否存在短时记忆中。 实验假设 我们假设视觉编码存在短时记忆中。若实验设计合理，实验进行正常。那么可以得到，短时记忆存在听觉编码。因此在字母形状不同发音相同、字母形状发音都不同的条件下。被试的反应时会存在差异。 实验预期 被试在不同刺激条件a1、a2、a3下（a1字母形状名称均相同、a2字母形状不同但名称相同、a3字母形状和名称都不同）的反应时存在差异。 2.方法 被试：五人一组，互为主被试，共85名被试。 实验材料：JGW—B型心理实验台的速示器单元，计时计数器单元，手键1个，练习卡片3张（DD、Dd、DG），实验卡片16张（见下表），注视点卡片1张。 实验设计：单因素重复测量设计 实验程序： 统计方法 单因素重复测量的方差分析 3 结果 不同条件下反应时的描述统计结果 在字母形状和发音都相同、字母形状不同但发音相同和字母形状和发音都不同三种条件下的反应时描述统计结果见表1。 表1 三种条件下的反应时的描述统计结果(N=3) 条件M(SD)min max 形状和发音都相 同（a1） 形状不同但发音 相同(a2) 形状和发音都不 同(a3) 不同条件下反应时的差异 通过单因素重复测量方差分析，得出的结果发现，不同条件下，被试反应时有统计学意义上的显着差异（F(2)=,P=0）;再通过多重比较结果分析发现：a1≠a2,a1≠a3,a2≠a3,见表2. 表2 不同条件下反应时差异检验的结果 4 讨论 通过实验结果分析、实验假设得到了验证。在a2（字母形状不同但名称相同）与（a3字母形状发音都不同）的条件下，被试反应时差异显着。这个结果表明，在字母形状条件相同的情况下，字母发音的不同会影响到被试反应时的结果，即短时记忆存在记忆的声音编码，这一分析结果表明本实验的设计是比较合理。a1（字母形状发音都相同）与a2（字母形状不同但名称相同）的条件下被试反应时差异显着，这表明，在字母发音条件相同的情况下，字母形状的不同也会影响被试反应时的结果，即短时记忆存在记忆的视觉编码。 5 结论 中南大学 《信息论与编码》实验报告 题目信源编码实验 指导教师 学院 专业班级 姓名 学号 日期 目录 一、香农编码 (3) 实验目的 (3) 实验要求 (3) 编码算法 (3) 调试过程 (3) 参考代码 (4) 调试验证 (7) 实验总结 (7) 二、哈夫曼编码 (8) 实验目的 (8) 实验原理 (8) 数据记录 (9) 实验心得 (10) 一、香农编码 1、实验目的 （1）进一步熟悉Shannon 编码算法； （2）掌握C 语言程序设计和调试过程中数值的进制转换、数值与字符串之间 的转换等技术。 2、实验要求 （1）输入：信源符号个数q 、信源的概率分布p ； （2）输出：每个信源符号对应的Shannon 编码的码字。 3、Shannon 编码算法 1：procedure SHANNON(q,｛Pi ｝) 2: 降序排列｛Pi ｝ 3: for i=1 q do 4: F(i s ) 5：i l 2 []log 1/()i p s 6：将累加概率F(i s )（十进制小数）变换成二进制小数。 7：取小数点后i l 个二进制数字作为第i 个消息的码字。 8：end for 9：end procedure ------------------------------------------------------------------------------------------------------------------ 4、调试过程 1、fatal error C1083: Cannot open include file: 'unistd.h': No such file or directory fatal error C1083: Cannot open include file: 'values.h': No such file or directory 原因：unistd.h 和values.h 是Unix 操作系统下所使用的头文件 纠错：删去即可 2、error C2144: syntax error : missing ')' before type 'int' error C2064: term does not evaluate to a function 原因：l_i(int *)calloc(n,sizeof(int)); l_i 后缺少赋值符号使之不能通过编译 纠错：添加上赋值符号 1 1 ()i k k p s -=∑ 图像压缩编码实验报告 一、实验目的 1.了解有关数字图像压缩的基本概念，了解几种常用的图像压缩编码方式； 2.进一步熟悉JPEG编码与离散余弦变换（DCT）变换的原理及含义； 3.掌握编程实现离散余弦变换（DCT）变换及JPEG编码的方法； 4.对重建图像的质量进行评价。 二、实验原理 1、图像压缩基本概念及原理 图像压缩主要目的是为了节省存储空间，增加传输速度。图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3类： （1）无损压缩编码种类 哈夫曼（Huffman）编码，算术编码，行程（RLE）编码，Lempel zev编码。（2）有损压缩编码种类 预测编码，DPCM，运动补偿； 频率域方法：正交变换编码(如DCT)，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码； 基于重要性：滤波，子采样，比特分配，向量量化； （3）混合编码 JBIG，，JPEG，MPEG等技术标准。 2、JPEG 压缩编码原理 JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。其中最常用的是基于DCT变换的顺序式模式，又称为基本系统。JPEG 的压缩编码大致 图 像 压 缩 编 码（实验报告） 一、实验目的 1．理解图像压缩目的及意义； 2．理解有损压缩和无损压缩的概念； 3．了解几种常用的图像压缩编码方法； 4．利用MATLAB程序进行图像压缩。 二、实验原理 图像压缩主要目的是为了节省存储空间，提高存储、处理、传输速度。虽然表示图像需要大量的数据，但数据是高度相关的，或者说存在冗余（Redundancy），去掉这些冗余信息可以有效地压缩图像，同时不会损坏图像的有效信息。信息的冗余量有许多种，如空间冗余，时间冗余，结构冗余，知识冗余，视觉冗余等，数据压缩实质上是减少这些冗余量。高效编码的主要方法是尽可能去除图像中的冗余成分，从而以最小的码元包含最大的图像信息。 图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。 编码压缩方法有许多种，从不同的角度出发有不同的分类方法，从信息论角度出发可分为两大类。 （1）冗余度压缩方法，也称无损压缩、信息保持编码或嫡编码。具体说就是解码图像和压缩编码前的图像严格相同，没有失真，从数学上讲是一种可逆运算。 （2）信息量压缩方法，也称有损压缩、失真度编码或烟压缩编码。也就是说解码图像和原始图像是有差别的，允许有一定的失真。 应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下几类： （1）熵编码。熵编码是纯粹基于信号统计特性的编码技术，是一种无损编码。熵编码的基本原理是给出现概率较大的符号赋予一个短码字，而给出现概率较小的符号赋予一个长码字，从而使得最终的平均码长很小。 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名：陈**浩学号：*************指导教师：钱** 实验地点：科研教学楼A508实验时间：一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—树 三、实验学时：4 四、实验原理： 霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。 可以证明霍夫曼树的WPL是最小的。哈夫曼编码实验报告
短时记忆视觉编码实验报告
游程编码实验报告
霍夫曼树实验报告
哈夫曼树实验报告
短时记忆的信息编码 实验报告
哈夫曼树的实验报告1
哈夫曼树 实验报告
短时记忆视觉编码实验报告
PCM编码 实验报告
哈夫曼树实验报告
减法反应时-短时记忆的视觉编码实验报告
信息论与编码实验报告.
《短时记忆的视觉编码实验报告》
香农编码实验报告
图像压缩编码实验报告
图像编码实验报告
哈夫曼树及其操作-数据结构实验报告(2)