下载文档原格式
1. 在无失真的信源中，信源输出由 H (X ) 来度量；在有失真的信源中，信源输出由 R (D ) 来度量。
2. 要使通信系统做到传输信息有效、可靠和保密，必须首先 信源 编码， 然后_____加密____编码，再______信道_____编码，最后送入信道。
3. 带限AWGN 波形信道在平均功率受限条件下信道容量的基本公式，也就是有名的香农公式是log(1)C W SNR =+；当归一化信道容量C/W 趋近于零时，也即信道完全丧失了通信能力，此时E b /N 0为 -1.6 dB ，我们将它称作香农限，是一切编码方式所能达到的理论极限。
4. 保密系统的密钥量越小，密钥熵H (K )就越 小 ，其密文中含有的关于明文的信息量I (M ；C )就越 大 。
5. 已知n ＝7的循环码42()1g x x x x =+++，则信息位长度k 为 3 ，校验多项式 h(x)= 31x x ++ 。
6. 设输入符号表为X ＝{0，1}，输出符号表为Y ＝{0，1}。
输入信号的概率分布为p ＝(1/2，1/2)，失真函数为d (0，0) = d (1，1) = 0，d (0，1) =2，d (1，0) = 1，则D min ＝ 0 ，R (D min )＝ 1bit/symbol ，相应的编码器转移概率矩阵[p(y/x )]＝1001⎡⎤⎢⎥⎣⎦；D max ＝ 0.5 ，R (D max )＝ 0 ，相应的编码器转移概率矩阵[p(y/x )]＝1010⎡⎤⎢⎥⎣⎦。
7. 已知用户A 的RSA 公开密钥(e,n )=(3,55)，5,11p q ==,则()φn = 40 ，他的秘密密钥(d,n )＝(27,55) 。
若用户B 向用户A 发送m =2的加密消息，则该加密后的消息为 8 。
二、判断题1. 可以用克劳夫特不等式作为唯一可译码存在的判据。
（√ ）2. 线性码一定包含全零码。
（√ ）3. 算术编码是一种无失真的分组信源编码，其基本思想是将一定精度数值作为序列的 编码，是以另外一种形式实现的最佳统计匹配编码。
Xx大学yy学院综合性设计性实验报告专业班级：学号：姓名：实验所属课程：信息论与编码技术实验室(中心)：信息科学与工程学院软件中心指导教师：实验完成时间： 2012 年 12 月 9 日一、设计题目：Huffman编码及译码二、实验内容及要求：<一>实验内容：对所给的字符串进行huffman的编译码；译码对应原始序列，在将编码进行移位操作时，再进行译码输出，得出误码率。
<二>实验要求：自己设计一段信源序列，利用Huffman编码对其进行编码，然后利用相应的译方法进行译码，同时考察译码错误对后续序列带来的影响。
三、实验过程(详细设计)：<一> huffman编码原理：Huffman编码是一种紧致编码，但编码序列的码并非是唯一的。
它是根据源数据各信号发生的概率进行编码，在源数据中出现的概率越大的信号，分配的码字越短；出现概率越小的信号，其码字越长，从而达到用尽可能少的码字表示源数据的目的。
Huffman编码的步骤如下：设信源X有m个符号（消息），信源概率分布如下：X = ⎧ x1, x2 ,..., x m ⎫⎩ p1 2 ,..., p m ⎭（1）把信源X 中的消息按概率从大到小的顺序排列；（2）把最后两个出现概率最小的消息合并成一个消息，从而使信源的消息数减少，并同时再按信源符号（消息）出现的概率从大到小排列；（3）重复上述2 个步骤，直到信源最后为一个序列只有一个1；（4）将被整合的消息分别赋予1 和0，并对最后的两个消息也相应地赋予1 和0.（5）通过以上步骤即可完成编码操作。
<二> huffman译码原理：通过在刚开始生成的随机编码序列，得到列出的0 1 序列与源字符串一一对应，就完成了译码。
而对错位后的编码序列，我只是只错位了前两个进行译码，效果不是很明显。
<三>算法设计：1、编码部分：（1）主函数主要用于调用前面所编写的各个函数模块，按照主函数（主函数代码如下）所列出来的调用顺序，进行一一叙述。
5-10 设有离散无记忆信源}03.0,07.0,10.0,18.0,25.0,37.0{)(=X P 。
（1）求该信源符号熵H(X)。
（2）用哈夫曼编码编成二元变长码，计算其编码效率。
（3）要求译码错误小于310-，采用定长二元码达到（2）中的哈夫曼编码效率，问需要多少个信源符号连在一起编？ 解：（1）信源符号熵为symbolbit x p x p X H i ii /23.203.0log 03.007.0log 07.010.0log 10.018.0log 18.025.0log 25.037.0log 37.0)(log )()(222222=------=-=∑ （2）1x 3x 2x 6x 5x 4x 0.370.250.180.100.070.030111110.100.200.380.621.0000011110110001001符号概率编码该哈夫曼码的平均码长为符号码元/3.2403.0407.0310.0218.0225.0237.0)(=⨯+⨯+⨯+⨯+⨯+⨯==∑iii K x p K 编码效率为9696.03.223.2)(===KX H η (3)信源序列的自信息方差为2222)(792.0)]([)]()[log ()(bit X H x p x p X i ii =-=∑σ7.00696.90)()(==+=εεη得，由X H X H53222102.6110)7.00(92.70)(⨯=⨯=≥-δεσX L 由切比雪夫不等式可得所以，至少需要1.62×105个信源符号一起编码才能满足要求。
5-12 已知一信源包含8个消息符号，其出现的概率}04.0,07.0,1.0,06.0,05.0,4.0,18.0,1.0{)(=X P ，则求：（1）该信源在每秒内发出1个符号，求该信源的熵及信息传输速率。
（2）对这8个符号作哈夫曼编码，写出相应码字，并求出编码效率。
信息论大作业信息论大作业电子工程学院班号编码1．Huffman 编码原理：①将信源符号按概率从大到小的顺序排列，令p(x1)≥ p(x2)≥?≥ p(xn) ②给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。
称为信源的第一次缩减信源，用S1表示。
③将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n －2)个符号的缩减信源S2。
④重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。
然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
2. 霍夫曼编码优缺点：1) 编出来的码都是异字头码，保证了码的唯一可译性。
2) 于编码长度可变。
因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
3) 编码长度不统一，硬件实现有难度。
4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
5) 于0与1的指定是任意的，故上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
3.编码流程：读入一幅图像的灰度值; 1. 将矩阵的不同数统计在数组c的第一列中; 2. 将相同的数占站整个数组总数的比例统计在数组p中; 3. 找到最小的概率,相加直到等于1,把最小概率的序号存在tree第一列中,次小放在第二列,和放在p像素比例之后; 4. C数组第一维表示值,第二维表示代码数值大小,第三维表示代码的位数； 5. 把概率小的值为1标识，概率大的值为0标识； 6. 计算信源的熵；7. 计算平均码长；8. 计算编码效率’；9. 计算冗余度。
源程序：p=input(‘请输入数据:’); n=length(p); for i=1:n if p(i) fprintf(‘\\n 提示：概率值不能小于0!\\n’); p=input(‘请重新输入数据:’);end end if abs(sum(p))>1 fprintf(‘\\n 哈弗曼码中概率总和不能大于1!\\n’); p=input(‘请重新输入数据:’);end q=p; a=zeros(n-1,n); %生成一个n-1 行n 列的数组for i=1:n-1[q,l]=sort(q); a(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,1:n*n)=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(a(n-i+1,:)==1 ))-(n-2):n*(find(a(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-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find( a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j +1)); end end%完成huffman 码字的分配for i=1:n h(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a (1,:)==i)*n);ll(i)=length(find(abs(h(i,:))~=32)); %计算每一个huffman 编码的长度end l=sum(p.*ll);%计算平均码长fprintf(‘\\n Huffman编码结果为:\\n’);h fprintf(‘\\n 编码的平均码长为:\\n’); l hh=sum(p.*(-log2(p))); %计算信源熵fprintf(‘\\n 信源熵为:\\n’);hh fprintf(‘\\n 编码效率为:\\n’); t=hh/l%计算编码效率运行结果为：请输入数据:[,,,,,,,] Huffman编码结果为: h = 1100 1101010111011 00010001 编码的平均码长为: l = 3 信源熵为: hh = 编码效率为: t = 编码：Fano 码: 费诺编码属于概率匹配编码，但它不是最佳的编码方法。
信息论与编码课程作业_huffman编码的matlab_实现信息论与编码课程作业——霍夫曼编码求信源熵和存储前后的信息量的变化一：设计目的：1、学习离散信源平均信息量的计算方法。
2、理解和掌握huffman 编码的基本原理，实现对信源符号的huffman 编码3、熟悉 Matlab 编程；二：设计原理和思路1.信源熵的计算：公式： 21()log a I a p = Matlab 实现：I=log2(1/p) 或I=-log2(p) 熵（平均自信息）的计算公式22111()log log qq i i i i i i H x p p p p ====-∑∑Matlab 实现：HX=sum(-x.*log2(x))；或者h=h-x(i)*log2(x(i));2.霍夫曼编码原理;分为两步，首先是码树形成过程：对信源概率进行合并形成编码码树。
然后是码树回溯过程：在码树上分配编码码字并最终得到Huffman 编码。
1、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。
然后按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。
在这一过程中每一次都把排序后的信源概率存入矩阵p 中，位置索引存入矩阵m 中。
这样，由排序之后的概率矩阵 p 以及索引矩阵m 就可以恢复原概率矩阵P 了，从而保证了回溯过程能够进行下去。
2、码树回溯过程：在码树上分配编码码字并最终得到Huffman 编码。
从索引矩阵M 的末行开始回溯。
(1) 在p 的末行2元素位置填入0和1。
(2) 根据该行索引1位置指示，将索引1位置的编码（‘1’）填入上一行的第一、第二元素位置，并在它们之后分别添加‘0’和‘1’。
(3) 将索引不为‘1’的位置的编码值（‘0’）填入上一行的相应位置（第3 列）。
(4) 以m的倒数第二行开始向上，重复步骤(1) ～(3)，直到计算至m的首行为止。
三：设计代码：>> clear all;format longdisp(strcat('信息论与编码课程作业——霍夫曼编码求信源熵和存储前后的信息量的变化',13));histgram=zeros(1,255);[c,map]=imread('C:\Documents and Settings\Administrator\桌面\infomation\lenna.bmp');x=rgb2gray(c);[a,b]=size(x);for i=1:afor j=1:bk=x(i,j);histgram(k)=histgram(k)+1;endendf=histgram/a/b;symbols=find(f~=0); %灰度值p=f(symbols); %概率L=length(p);pp=p;%霍夫曼编码m=zeros(L-1,L);for i=1:L-1[p,mark]=sort(p);m(L-i,1:L-i+1)=mark(1:L-i+1);p=[p(1)+p(2),p(3:L),1];endc=cell(L-1,L);c(1,1)={'0'};c(1,2)={'1'};for i=2:L-1;ind=find(m(i-1,:)==1);temp=char(c(i-1,ind));c(i,1)={[temp,'0']};c(i,2)={[temp,'1']};snc=find(m(i-1,:)~=1);for j=3:i+1;con=snc(j-2);c(i,j)=c(i-1,con);endendcodeL=[];averge_long=0;H1=0;disp(strcat('灰度值',32,32,32,'概率',32,32,32,32,32,32,32,32,32,'霍夫曼编码:'));for i=1:L;ind=find(m(L-1,:)==i);code=char(c(L-1,ind));codeLength(i)=length(code);averge_long=averge_long+pp(i)*codeLength(i);H1=H1+pp(i)*log2(1/pp(i));disp(strcat(32,num2str(symbols(i)),32,32,32,num2str(pp(i)),3 2,32, code));enddisp(strcat('信源熵=',num2str(H1),32,32,32,32,'平均码字长度=',num2str(averge_long),32,32,32,32,32,'压缩比=',num2str(8/averge_long)));四：设计运行结果：信息论与编码课程作业——霍夫曼编码求信源熵和存储前后的信息量的变化灰度值概率霍夫曼编码:30 1.5259e-005 101000111100001031 1.5259e-005 101000111100001136 1.5259e-005 101000111100000037 1.5259e-005 101000111100000139 6.1035e-005 1010001111000140 7.6294e-005 1110010101001041 6.1035e-005 0111010111011042 6.1035e-005 0111010111011143 9.1553e-005 1110010101001144 0.00018311 111011101010145 0.00021362 00111101101146 0.00022888 01110101111047 0.00024414 01110101111148 0.00039673 0011110110049 0.00048828 1010001110050 0.00065613 1110010101151 0.00090027 011101011052 0.00086975 001111011153 0.0013123 111001011054 0.0013733 111011101156 0.0018005 01110101057 0.0025177 11010001158 0.0036621 0111111059 0.0033722 0101111060 0.0046539 1100110161 0.0055847 1111010162 0.0061188 001001063 0.0080261 100111064 0.0075226 100001165 0.0083466 101010166 0.0088806 101111167 0.0092773 110011168 0.0095367 110101069 0.0086517 101101070 0.0084229 101011071 0.0075378 100010172 0.0071564 011011173 0.0061493 001001174 0.0056 1111011075 0.0053864 1110110076 0.0045319 1100011177 0.0043488 1011000178 0.0042114 1010111079 0.0039063 1000111180 0.0041199 1010100181 0.0035706 0110101182 0.0039368 1001011083 0.0037537 1000010084 0.003479 0110101086 0.0033417 0101101087 0.0032501 0100110088 0.0034027 0110000189 0.0031128 0011010090 0.0031433 0011110091 0.0036774 0111111192 0.0041046 1010011094 0.0038452 1000111095 0.004364 1011100096 0.0037842 1000110097 0.0037079 1000001198 0.0033722 0101111199 0.0040741 10100001 100 0.0040741 10100010 101 0.0038147 10001101 102 0.0040588 10011111 103 0.0041046 10100111 104 0.004364 10111001 105 0.0048218 11010111 106 0.0052185 11100100 107 0.0049591 11011010 108 0.005188 11100001 109 0.0047455 11010110 110 0.0052032 11100011 111 0.0054474 11110100 112 0.0057526 11111011 113 0.0065308 0100111 114 0.0079346 1001100 115 0.010223 1101111116 0.0095825 1101100 117 0.0089417 1100000 118 0.0086975 1011011 119 0.0081787 1010010 120 0.007782 1001001121 0.0066376 0101011 122 0.0059357 11111111 123 0.0056458 11110111 124 0.0051575 11100000 125 0.0052948 11101001 126 0.005188 11100010 127 0.0059814 0000001 128 0.0058594 11111101 129 0.0065613 0101010 130 0.0062561 0011011 131 0.006897 0110100132 0.0072479 0111011 133 0.0073242 0111110 134135 0.0075226 1000100 136 0.0077515 1001000138 0.008606 1011001139 0.0091095 1100100 140 0.012115 000010141 0.012115 000011142 0.012741 001110143 0.012329 001100144 0.010941 1111001145 0.010147 1101110146 0.0089417 1100001 147 0.0088043 1011101 148 0.0091095 1100101 149 0.010712 1110101150 0.011337 1111100151 0.010513 1110011152 0.012878 010000153 0.012268 001010154 0.013138 010100155 0.012238 001000156 0.012939 010001157 0.012115 000100158 0.012955 010010159 0.012207 000111160 0.011993 000001161 0.013916 011001162 0.012177 000110163 0.012299 001011164 0.0094604 1101001 165 0.0089874 1100010 166 0.0088501 1011110 167 0.0056915 11111010 168 0.0059357 0000000 169 0.0071716 0111001 170 0.0057678 11111100 171 0.0054016 11101111 172 0.0054169 11110001 173 0.0058746 11111110 174 0.0072937 0111100 175 0.0070953 0110110 176177 0.0061035 0001011 178 0.0054016 11110000 179 0.0053864 11101101 180 0.0046692 11010000182 0.0036774 10000000183 0.0033875 01100000184 0.0033264 01011000185 0.0031281 00110101186 0.0035706 01110000187 0.0033264 01011001188 0.0033569 01011011189 0.0036011 01110100190 0.0040436 10011110191 0.0034485 01100010192 0.0036774 10000001193 0.0032654 01001101194 0.0034485 01100011195 0.003006 00010100196 0.0033722 01011100197 0.0036774 10000010198 0.0042419 10110000199 0.0045166 11000110200 0.0041046 10101000201 0.0052643 11101000202 0.0050354 11011011203 0.0045319 11001100204 0.0039825 10011010205 0.0040588 10100000206 0.0039673 10010111207 0.0037537 10000101208 0.0033722 01011101209 0.0026703 111011100210 0.0022125 110100010211 0.0018768 101000110212 0.0015259 000101010213 0.0013428 1110010111214 0.0012665 1110010100215 0.0007782 0011110100216 0.00079346 0011110101217 0.00061035 10100011111218 0.00054932 10100011101219 0.00065613 11101110100220 0.00035095 111011101011 221 0.00033569 111001010101 222 0.00030518 101000111101 223 0.00021362 011101011100 224 0.00016785 1110111010100225 0.00019836 001111011010226 0.00015259 1110010101000227 0.00010681 0111010111010228 6.1035e-005 10100011110010230 3.0518e-005 101000111100110231 1.5259e-005 10100011110011110232 1.5259e-005 10100011110011111233 1.5259e-005 1010001111001110信源熵=7.2193 平均码字长度=7.2492 压缩比=1.1036五：设计新得体会：通过这学期对信息论和编码的学习，以及这次的设计，使我了解了很多东西，也使以前所学的知识得以巩固！，通过这次的设计，进一步学习了离散信源平均信息量、平均码长和压缩比的计算方法。
信息论与编码课程大作业
一、信源与信源编码
1、若信源包含N 个符号，在什么情况下熵最大？（10分）
最大的熵值是多少？（10分）
2、简述信源编码的两个作用。
（10分）
3、已知离散无记忆信源中各符号的概率空间为
X = 符号u1 u2 u3 u4
概率：1/2 1/4 1/8 1/8
(1)求信源的熵(10分)；
(2)对其进行哈夫曼编码(要求码方差较小)，写出过程(10分)；
(3)求出平均码长和编码效率(10分)。
4、举出学过的无失真与限失真编码方法，各1种。
（10分）
并选择一种，阐述其在实际中的应用（不少于200字）。
（10分）
5、编程题（20分）
二、信道与信道编码
1、 对称信道容量公式？（10分）
在信源如何分布时达到信道容量？（10分）
2、信道编码的基本原理是什么？（10分）
3、对一个（4，2）码，其生成矩阵为
(1)写出伴随式译码表(10分)；
(2)接收序列R=1100，估算发码(10分)；
(3)判断码的检错能力(10分)。
4、举出两种常用的纠错码，（10分）
并选择一种，阐述其在实际中的应用（不少于200字）。
（10分）
5、编程题（20分）
说明：（1）按学号排列前30名同学完成信源与信源编码方面的作业，其余同学
完成信道与信道编码方面的作业。
（2）第5题编程题另付题目与具体要求，可在20道编程题中任选一道；
自己编写课程相关的其他程序也可以。
（3）第4题和第5题，任意两个同学不能雷同，否则均不能通过。
10010111G ⎡⎤=⎢⎥⎣⎦。
哈夫曼编码1.前言:H affman算法是个简单而高效的贪心算法，主要用来创建最优二叉树.可以在通讯时，对于出现频率较高的字符，用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。
该算法在各类数据结构, 算法,组合数学，离散数学，图论等主题的书籍中都有所涉及。
故本文不再赘述，本文致力于用Haffman算法实现压缩与解压缩,采用的语言为C语言，编译环境VC++6.0.下面给出[1]中实现的Haffman树的结构及创建算法，有两点说明:a) 这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。
b) 由于对于最后生成的Haffman树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为m个时，内部结点数为m-1.整个Haffman树的需要的结点数为2m-1. 2压缩过程的实现:压缩过程的流程是清晰而简单的:1创建Haffman树à2打开需压缩文件à3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出à4文件压缩结束。
其中，步骤1和步骤3是压缩过程的关键。
a) 步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创建. 统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率;或者是创建前即做好统计.本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。
当前，也可以根据被压缩文件的特性有针对性的进行统计，如要压缩C语言的源文件，则可事先对多篇C语言源文件中出现的字符进行统计,这样，会创建出高度相对较“矮”的Haffman树，从而提高压缩效果。
创建Haffman树的算法前文已有陈述，这里就不再重复了。
b) 步骤3: 将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出.这是本压缩程序中最关键的部分:这里涉及“转换”和“输出”两个关键步骤:“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码，可以将每个Haffman码值及其对应的ascii码存放于如下所示的结构体中：2.算术编码(1)算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。
哈夫曼编码1.前言:H affman算法是个简单而高效的贪心算法，主要用来创建最优二叉树.可以在通讯时，对于出现频率较高的字符，用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。
该算法在各类数据结构, 算法,组合数学，离散数学，图论等主题的书籍中都有所涉及。
故本文不再赘述，本文致力于用Haffman算法实现压缩与解压缩,采用的语言为C语言，编译环境VC++6.0.下面给出[1]中实现的Haffman树的结构及创建算法，有两点说明:a) 这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。
b) 由于对于最后生成的Haffman树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为m个时，内部结点数为m-1.整个Haffman树的需要的结点数为2m-1. 2压缩过程的实现:压缩过程的流程是清晰而简单的:1创建Haffman树à2打开需压缩文件à3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出à4文件压缩结束。
其中，步骤1和步骤3是压缩过程的关键。
a) 步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创建. 统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率;或者是创建前即做好统计.本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。
当前，也可以根据被压缩文件的特性有针对性的进行统计，如要压缩C语言的源文件，则可事先对多篇C语言源文件中出现的字符进行统计,这样，会创建出高度相对较“矮”的Haffman树，从而提高压缩效果。
创建Haffman树的算法前文已有陈述，这里就不再重复了。
b) 步骤3: 将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出.这是本压缩程序中最关键的部分:这里涉及“转换”和“输出”两个关键步骤:“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码，可以将每个Haffman码值及其对应的ascii码存放于如下所示的结构体中：2.算术编码(1)算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。
(2)设计思想:其算法的主要算法基本思想：首先就是构造一个结构体用于存储信源的相关信息（包括信源符号，信源概率，编码的上下限）；接着就是初始化信源的相关信息，如初始化编码间隔；利用算术编码的原理构造编码方法，最后实现编码。
(3)调试分析：此算法主要就是算术编码方法的构造，利用算法中Initial_message()函数初始化以后，根据初始化间隔完成编码序列的编码。
在调试的过程中经常遇到一些小问题，通过一步步的调试以及修改，问题一个的解决了。
同时也遇到比较大的问题，就是编码方法过程的实现，最大的体会就是必须深入理解次编码方法的原理。
(4)流程图(5)测试结果：(6)源程序清单：#include<stdio.h>#include<string.h>#include <conio.h>#define N 4 //信源符号的个数#define n 7 //要编码的序列长度struct ARC{char m[N];float P[N];float Low[N];float High[N];float low;float high;}code;Initial_message() //初始化编码间隔{float F=0;int i=0,j;printf("请输入%d个信源符号及其概率!\n",N);for(i=0;i<N;i++){scanf("%c %f",&code.m[i],&code.P[i]);getchar();}for(j=0;j<N;j++){code.Low[j]=F;F=F+code.P[j];code.High[j]=F;}printf("信源符号概率初始编码间隔\n");for(j=0;j<N;j++){printf("%c %f [%f,%f)\n",code.m[j],code.P[j],code.Low[j],code.High[j]);}}main(){int i=0;int Bcode[10];char c[n];char *p=NULL;char *q=NULL;float s,mid;Initial_message();printf("请输入长度为%d要编码的序列:",n);scanf("%s",c);p=c;q=code.m;while(q!=NULL)//判定第一个需要编码序列的第一符号所在的间隔{if(*p==*q){code.low =code.Low [i];code.high =code.High [i];printf("%c\n[%f,%f)\n",code.m[i],code.low ,code.high );goto ss;}else{q++;i++;}}ss:p++;while(*p!='\0')//利用算术编码的方法，求出编码的十进制结果{int k=0;float t;float pt=0;int k1;q=code.m;while(*q!='\0'){if(*p==*q){if(k==0){t=code.high -code.low ;code.low =code.low +t*pt;code.high =code.low +t*code.P [k];printf("%c\n[%f,%f)\n",code.m [k],code.low ,code.high );goto xx;}else{k1=k;while(k1){t=code.high -code.low ;pt=pt+code.P[k1-1];k1--;}code.low =code.low +t*pt;code.high =code.low +t*code.P [k];printf("%c\n[%f,%f)\n",code.m [k],code.low ,code.high );goto xx;}}elseq++;k++;}xx:p++;}mid=(code.high-code.low )/2+code.low ;s=2*mid;for(i=0;i<10;i++) //编码结果{if(s>1){ Bcode[i]=1;s=s-1;}else{Bcode[i]=0;}s=2*s;printf("%d",Bcode[i]);}printf("\n");}3. Huffman编码对英文文本的压缩和解压缩(1) 根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。
要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。
(2) 设计思想：首先构造一个结构体用于统计字符频率，然后把统计后的结果当作信源；接着用Haffman编码的方法对其编码，编码后对输入的英语文本进行编码的转换，即用Haffman编码的每一个字符的编码代替输入的英语文本每一字符，输入的英语文本就变成了01代码流，最后利用这01代码流每八位压缩成相对应的字符。
压缩流程：解压缩流程：(3)调试分析：本算法可以分成四个部分即统计字符概率，Huffman 编码，压缩文件和解压文件四部分，也就是次算法中函数stati() ,函数HCode() 和函数compress()的构建，用于压缩后的字符出现了乱码，所以对解压文件这部分难以实现，这也是此算法失败的地方。
经过不断的调试和修改还是只完成统计字符概率，Huffman 编码和压缩文件这三部分。
(4)流程图(5)测试结果：(6)源程序清单：#include<stdio.h>#include<stdlib.h>#define MaxValue 1000 //设定权值最大值#define MaxBit 10 //设定的最大编码位数#define MaxN 1000 //设定的最大结点个数#include"Huffman.h"float ComNum=0;//用于计算压缩后的字符个数struct statistics //统计字符频率{char a[100]; //出现的字符double p[100]; //字符出现的概率int tag[100];//每一个字符出现次数int num; //总计出现的字符种类个数float n; //总计字符出现的次数}TJ;char cc[100];void raplace(myHaffCode);stati()//统计字符{FILE *fp;FILE *fp1;char ch,filename[10];int i=0,k;printf("请输入用于保存字符文本的文件名，如file.txt\n");scanf("%s",filename);getchar();printf("请输入英语文本:");gets(cc);fp=fopen(filename,"w+");fprintf(fp,"%s",cc);fclose(fp);TJ.num=1;TJ.n=0;if((fp1=fopen(filename,"r"))==NULL){printf("文件无法打开！");exit(0);}ch=fgetc(fp1);TJ.a[i]=ch;while(ch!=EOF)//统计字符出现的次数，并计算起概率。
{int j;for(j=i;j>=0;j--){if(TJ.a[j]==ch){TJ.tag [j]+=1;goto xx;}}i++;TJ.a[i]=ch;TJ.tag[i]+=1;TJ.num++;xx:ch=fgetc(fp1);TJ.n++;}fclose(fp1);for(k=0;k<=i;k++){TJ.p[k]=TJ.tag[k]/TJ.n;}printf("\t字符统计\n");printf("字符出现的次数概率\n");for(k=0;k<=i;k++){printf(" %c %d %1.10f\n",TJ.a[k],TJ.tag[k],TJ.p[k]);}}HCode()//haffman编码{int i,j,n=TJ.num;HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n+1));Code *myHaffCode=(Code *)malloc(sizeof(Code)*TJ.num);for(i=0;i<n;i++)//排序--按字符出现的次数从小到大排{int t=TJ.tag[i];char t1=TJ.a[i];for(j=i+1;j<n;j++){if(t>TJ.tag[j]){t=TJ.tag[j];TJ.tag[j]=TJ.tag[i];TJ.tag[i]=t;t1=TJ.a[j];TJ.a[j]=TJ.a[i];TJ.a[i]=t1;}}}Haffman(TJ.tag,n,myHaffTree);//建立叶结点个数为n权值数组为J.tag的哈夫曼树HaffmanCode(myHaffTree,n,myHaffCode);//由n个结点的夫曼树myHaffTree构造哈夫曼编码myHaffCodeprintf("\t Haffman编码\n");printf("信源符号权值编码结果\n");for(i=0;i<n;i++){printf(" %c Weight=%d Code=",TJ.a[i],myHaffCode[i].weight);for(j=myHaffCode[i].start;j<n;j++)printf("%d",myHaffCode[i].bit[j]);printf("\n");}raplace(myHaffCode);}void raplace(Code myHaffCode[])//把英语文本的字母包（括标点符号）用已经用Haffman编码完成的编码结果代替成01代码并存于文件code.txt中{char ch;int i,n,j;FILE *fp1;if((fp1=fopen("code.txt","w+"))==NULL){printf("文件无法打开！");exit(0);}n=0;ch=cc[n];while(ch!='\0'){for(j=0;j<TJ.num;j++){if(ch==TJ.a[j]){for(i=myHaffCode[j].start;i<TJ.num;i++)fprintf(fp1,"%d",myHaffCode[j].bit[i]);j=TJ.num;}}n++;ch=cc[n];}fclose(fp1);}void compress()//根据保存于code.txt的01代码每八位压缩一次{FILE *fp1,*fp2;int ch;char c;int i=0;int value;int a[8]={0};fp1=fopen("code.txt","r");fp2=fopen("yasuo.txt","w+");//yasu.txt用于存储压缩后的结果while(!feof(fp1)){fscanf(fp1,"%1d",&ch);a[i]=ch;i++;if(i==8){value=a[0]*128+a[1]*64+a[2]*32+a[3]*16+a[4]*8+a[5]*4+a[6]*2+a[7];c=value;fprintf(fp2,"%c",c);ComNum++;i=0;}}if(i!=0){while(i==8){a[i]=0;i++;}value=a[0]*128+a[1]*64+a[2]*32+a[3]*16+a[4]*8+a[5]*4+a[6]*2+a[7];c=value;fprintf(fp2,"%c",c);ComNum++;}fclose(fp2);fclose(fp1);}main(){float p;//用于计算压缩率printf("\tHuffman编码的对英文文本压缩和解压缩\n");stati();//统计HCode();//编码compress();//压缩p=((TJ.n-ComNum)/TJ.n);printf("压缩后的结果保存于文件yasuo.txt\n其压缩率为%f\n",p);}总结：本次课程设计能够完满的结束，关键在于组员之间有效的分工合作。
