《信息论实习报告》由会员分享，可在线阅读，更多相关《信息论实习报告（6页珍藏版）》请在金锄头文库上搜索。
1、在此处键入 071141-柳耀城-信息论与编码实习部分报告-2016 年 12 月1 / 7指导老师签名本部分实习成绩实习一题目:写一个执行 lempel-ziv 算法的程序。该程序的输入可以是英文字母。它应该 将字母转化为他们的 ASC码然后进行压缩，他应该输出压缩结果。用这个程 序对下列的字符串所得到的压缩：（1） The Lempel Ziv algorituhm can compress the English text by about fifty five percent.（2）The cat cannot sit on zhe canopy of zhe car.目的:1熟悉 m
2、atlab 编程； 2通过实验进一步理解 Lempel-Ziv 编码算法。 基本原理:首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表 示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个 字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后 将串表丢弃。如“print“ 字符串，如果在压缩时用 266 表示，只要再次出现，均用 266 表 示，并将“print“字符串存入串表中，在图象解码时遇到数字 266，即可从串表中查出 266 所代表的字符串“print“，在解压缩时，串表可以根据压缩数据重新生成。 程序及
3、说明：1. 在“source.txt”输入一段文字： The Lempel Ziv algorituhm can compress the English text by about fifty five percent. 或 The cat cannot sit on zhe canopy of zhe car. 2求熵 function entropy=Entropy(seq)%the function that calculate the source entropy 3.创建词典 function dictionary codelength=LZcode(seq)%the functi
4、on that acquire the LZ dictionary 4.编码 function decode=LZdecode(dictionary)%the function that decodes the encode file在此处键入 071141-柳耀城-信息论与编码实习部分报告-2016 年 12 月2 / 75.解码 function encode=LZencode(dictionary)%the function that encodes the source file 6.程序运行说明 (1) The Lempel Ziv algorituhm can compress t
5、he English text by about fifty five percent.Entropy =4.3275 Code length =6 Average length =3.6429 Encoded Sequence : Look encode.txt. Decoded Sequence : Look decode.txt. 00000000000100001000001100010000010100011000011100100000100100 10100010110011000011010011100011110100000100010100100100110101 0001
6、0101010110010111011000011001011010011011011100011101011110 01111110000010000110001010001110010010010110011010011110100010 1001101010101011101100101101101110101111110000110001110010 （2）The cat cannot sit on zhe canopy of zhe car. Entropy =3.7141 Code length =5 Average length =3.2955 Encoded Sequence
7、: Look encode.txt. Decoded Sequence : Look decode.txt. 00000000010001000011001000010100110001110100001001010100101101 10001101011100111110000100011001010011101001010110110101111100 011001110101101111100 实验心得:Lempeil-Ziv 字典压缩的原理是构建一个字典，用索引来代替重复出现的字符或字符串。如果字符串相对长，那么对整个字符串构建字典，这个字典将会很大，并且随着字典的增大，匹配速度也会
8、快速下降。原始的 LZ 算法是利用了字符串中上下文的相关性特点，通过一个滑动窗口（一个查找缓冲区）来作为字典，对要压缩的字符串保留一个 look-aheadbuffer。压缩后的字符串采用三元组来表示：，在滑动窗口中从后往前找，如果在窗口中有曾经出现过的相同字符，看最多可以匹配多少字节，完了继续往前查找，查找完了取窗口中最长的匹配串（如果有多个相同长度的串可以匹配，取最后一个），将这个匹配串距当前位置的位移，长度，及下一个字符构成的三元组写出。在此处键入 071141-柳耀城-信息论与编码实习部分报告-2016 年 12 月3 / 7如果在滑动窗口找不到匹配串，那么位移=长度=0，加上不能压缩
9、的字符一起输出。滑动窗口可以通过循环队列实现。实验二题目：写一个程序，它在输入信道转移概率矩阵后计算信道容量。 目的：了解信道容量的定义和计算方法，能编写出正确的程序进行迭代计算得出信道 容量 要求：1）输入：输入信源个数、信宿个数和信道容量的精度，程序能任意生成随机的 信道转移概率率矩阵。2）输出：输出最佳信源分布和信道容量。实验原理：输入 iiiiij iijiij ijiaCaapCriabpapabpabpamaxln)(ln, 2 , 1)/()()/(ln)/(exp21）（)()() 0 (iiapap00001. 0|21CCiiiii iaapaapap)()()(i=1,2
10、,r)nnCC, 11是否终止在此处键入 071141-柳耀城-信息论与编码实习部分报告-2016 年 12 月4 / 7程序及其说明：function main()clc; p=1/3 1/3 0 1/30 1/2 1/2 01/6 0 1/3 1/21/8 1/8 1/4 1/2;channel_cap(p,0.001)function channel_cap(P, e)n=0;C=0;C_0=0;C_1=0;r,s=size(P);for i=1:r if(sum(P(i,:)=1). error return; end for j=1:s if(P(i,j)1) error retur
11、n; end end endX=ones(1,r)/r;A=zeros(1,r);B=zeros(r,s);while(1) n=n+1; for i=1:r for j=1:s B(i,j)=log(P(i,j)/(X*P(:,j)+eps); end A(1,i)=exp(P(i,:)*B(i,:); end C_0=log2(X*A); C_1=log2(max(A); if (abs(C_0-C_1)e) C=C_0; fprintf fprintf 在此处键入 071141-柳耀城-信息论与编码实习部分报告-2016 年 12 月5 / 7break; else X=(X.*A)/(
12、X*A); continue; end end运行结果:迭代次数: n=34 信道容量: C=0.644340 比特/符号 体会：1）结合实验的动手操作，我对信道容量的定义和计算有了更深刻的认识。信道容量是在关于信源分布和信道转移概率的函数，当信道转移概率固定时，信道容量是关于信源分布的上凸形函数。实验过程中固定了信道转移概率，将信道容量看作是信源分布和后验概率的函数。固定信源分布和后验概率其中一个，后进行迭代计算另一个，最后得到最大的信道容量。 2）在编程的实现方面，我学会了自动生成信道转移概率矩阵、迭代的算法设计，精度的控制和实现以及程序的中断调试等。 实验三题目：写一个程序,当给出 n,
13、q,t 和接收到的向量时他能进行 BCH 编码 目的：熟悉 bch 码编码，译码过程 能用 matlab 进行 bch 编码及码译码操作编程 基本原理BCH 码 1959 年由 Hocquenghem、1960 年由 Bo se 和 Chandhari 分别独立提出。BCH 码是 纠正多个随机错误的循环码，可以用生成多项式 g(x)的根描述。 给定任一有限域 GF(q)及 其扩域 GF(qm)， 其中 q 是素数或素数的幂， m 为某一正整数。 若码元取自 GF(q)上的一 循环码，它的生成多项式 g(x)的根集合 R 中含有以下 -1 个连续根： 时， 则 由 g(x)生成的循环码称为 q
14、进制 BCH 码。 设 mi(x)和 ei 分别是 (i=0， 1， ， -2)元素的最小多项式和级， 则 BCH 码的生成 多项式和码长分别是： g(x)=LCM(m0(x)， m1(x)， ， m-2 (x) n=LCM(e0， e1， ， e-2) 如果生成多项式 g(x)的根中， 有一个 GF(qm)中的本原域元素， 则 n=qm-1， 称这种码长 n=qm-1 的 BCH 码为本原 BCH 码；否则， 称为非本原 BCH 码。 GF(qm)中元素的级一定是在此处键入 071141-柳耀城-信息论与编码实习部分报告-2016 年 12 月6 / 7qm-1 的因子， 所以非本原 BCH
15、 码的码长也一定是 qm-1 的因子。 编码过程：编码过程举例（以码长为 15，能纠错 3 个错误的 BCH 码为例） (15, 5)BCH 码：码长 n=15, 信息码位 k=5, 纠错位 t=3, 阶数 m=4, 能纠错 3 位。 该码的既约多项式： 该码的生成多项式： 根据式： 其中：为信息码多项式，为商式，为余式 得到的系统 BCH 多项式为：，即为编码后的 BCH 组。 4、译码方法BCH 码的译码方法有时域译码盒频域译码两类。频域译码是把每个码组看成一个数字信 号，把接收到的信号进行离散傅氏变换，然后利用数字信号处理技术在频域内译码，最后 进行傅氏反变换得到译码后的码组。时域译码则是在时域上直接利用码的代数结构进行译 码。纠正多个错误的 BCH 码的译码算法很复杂。时域译码又有多种方式，这里仅以彼得森 译码方法。在彼得森一码中采用计算校正子，然后用校正子寻找错误图样的方法。以下以 BCH (15 ,5) 码为例说明： 由可知，纠正 t 个错误的 BCH 码的生成多项式由 t 个最小多项式相乘得到，其中第 1 个最 小
