信息论与编码技术之实验
前两个是别人的,后两个是自己的,学术交流,抛砖引玉。
信息论与编码 实验报告样板 实验室名称:S1-306
实验一 二维随机变量信息熵的计算 教学实验报告
[实验目的]
掌握二变量多种信息量的计算方法。 [实验要求]
1.熟悉二变量多种信息量的计算方法,设计实验的数据结构和算法; 2.编写计算二维随机变量信息量的书面程序代码。 [实验内容]
离散二维随机变换熵的计算 说明:
(1)利用random 函数和归一化方法构造一个二维离散随机变量(X ,Y );
(2)分别计算X 与Y 的熵、联合熵、条件熵:H (X )、H (Y )、H (X,Y )H (X|Y)、I (X|Y);
(3)对测试通过的程序进行规范和优化; (4)编写本次实验的实验报告。 [实验步骤]
实验过程中涉及的各种熵的主要公式(或定义式): 1、离散信源熵(平均不确定度/平均信息量/平均自信息量) H (X ) =
∑p (x i ) I (x i ) =-∑p (x i ) log p (x i ) H (X /y j ) =
i
2、在给定某个y j 条件下,x i i 的条件自信息量为I(xi /yj ) ,X 集合的条件熵H (X/yj )为
∑
i
p (x i /y j ) I (x i /y j )
在给定Y 条件下,X 集合的条件熵H (X/Y) 为: H(X/Y)=∑p (y j ) H (X /y j ) =
j
∑
i , j
p (y j ) p (x i /y j ) I (x i /y j )
=
∑
i , j
p (x i y j ) I (x i /y j )
相应地,在给定X (即各个x i )的条件下,Y 集合的条件熵H(Y/X)定义为:
H (Y /X ) =
∑
i , j
p (x i y j ) I (y j /x i ) =-∑p (x i y j ) log p (y j /x i )
i , j
3、联合熵是联合符号集合 XY 上的每个元素对x i y j 的自信息量的概率加权统计平均值,表示X 和Y 同时发生的不确定度。
H (X Y ) =
∑
i , j
p (x i y j ) I (x i y j ) =-∑p (x i y j ) log p (x i y j )
i , j
[实验体会]
通过本次实验,掌握了离散信源熵、条件熵、联合熵的概念和它们与信源统计分布或条件分布、联合分布之间的关系,并能进行计算。进一步加深了对各种信息熵的物理意义的理解。
附:计算信源熵、联合熵和条件熵的程序代码清单:(可写入实验报告也可不写入)
#include #include #include #include #include using namespace std; void main() {
int k,n,t=0;
double a[4][4],b=0,c=0; srand((unsigned )time(NULL));
for (k=0;k
{ }
cout
cout
for (n=0;n
cout
coutcout
couta[k][n]=rand()%100; t+=a[k][n];
int e=1;
for (k=0;k
cout
int r,u,h=0; for (k=0;k
cout
else cout
for (k=0;k
double i=0; for (n=0;n
if (a[k][n]!=0) { }
else { }
r=k,u=n; h=1; break ;
b-=((a[k][n]/t)*log(a[k][n]/t)/log(2.0));
double i=0,g=0; for (n=0;n
cout
b-=(i*log(i)/log(2.0)); c-=(g*log(g)/log(2.0));
i+=(a[k][n]/t); g+=(a[n][k]/t);
}
}
}
for (n=0;n
if (a[k][n]!=0) { }
else {h=1;break ;}
b-=((a[k][n]/t)*log((a[k][n]/t)/i)/log(2.0)); if (h==0){cout
if (h==0)cout
else cout
实验二 简单信源编码方法实现 教学实验报告
[实验目的]
掌握Huffman 编码方法。 [实验要求]
1.熟悉离散信源的编码方法,重点是Huffman 编码方法,设计Huffman 编码的数据结构和算法;
2.编写Huffman 编码的书面程序代码。 [实验内容]
离散信源的Huffman 编、译码方法 说明:
(1)利用random 函数构造一个一维离散随机变量分布P (X ); (2)构造离散随机变量的概率压缩表;
(3)根据概率压缩表构造Huffman 编码表,并实现Huffman 编码; (4)完成Huffman 译码; (4)编写本次实验的实验报告。
[实验体会]
通过本次实验,掌握了离散信源最佳不等长编码的概念,掌握了哈夫曼编码的基本方法和过
程及平均码长和编码效率的计算。
哈夫曼编码的计算例子: 给定离散信源概率分布如下:
u 2u 3u 4u 5u 6u 7⎤⎡U ⎤⎡u 1
=⎢⎥⎢⎥
⎣p (u ) ⎦⎣0. 200. 190. 180. 170. 150. 100. 01⎦
H (U ) =-0.2log 0.2-0.19log 0.19-0.18log 0.18-0.17log 0.17
-0.15log 0.15-0.10log 0.10-0.01log 0.01
=2.61
平均码长:
7
K =
∑
i =1
p (u i ) K i =0.2⨯2+0.19⨯2+0.18⨯3+0.17⨯3+0.15⨯3+0.10⨯4+0.01⨯4=2.72
编码效率
η=
H (U ) K
=
2. 612. 72
=95. 96%
对本信源进行了哈夫曼编码,可以得到如下的一种可能编码:
附:哈夫曼编码过程的程序代码清单:(可写入实验报告也可不写入)
#include #include #include #include #include #include #include using namespace std; double *a; string *c; struct elem {
double a2;
class stack {
int size; int top; elem *list;
public : };
void aa(int n) {
double w=0; a=new double [n];
srand((unsigned )time(NULL));
cout
for (int i=0;i
double p;
for (int i=0;i
cout
for (int j=n-2;j>=i;j--) { }
if (a[j]
p=a[j+1]; a[j+1]=a[j]; a[j]=p;
a[i]=a[i]/w; a[i]=rand()%50; w+=a[i];
stack(const int sz=0){size=sz;top=0;list=new elem[sz];} ~stack(){delete []list;} void clear(){top=0;}
void push(const elem& item){assert(top
elem topValue() const {assert(!isEmpty());return list[top-1];} bool isEmpty() const {return top==0;}
}
}
coutvoid huffman(double *a,string *c,int n) {
elem mp;stack s(n);
double *b;b=new double [n];for (int i=0;i
for (int m=n;m>=2;m--) { }
while (!s.isEmpty())
{
mp=s.pop();
for (int i=0;i
if (mp.a2==e[i]) { }
t=c[i];
b[m-2]+=b[m-1];
mp.a2=d[m-2];mp.a3=d[m-1]; s.push(mp); double mp,mp1;
for (int i=0;i
cout
cout.precision(3); cout=i;j--) { }
if (b[j]
mp=b[j+1]; mp1=d[j+1]; b[j+1]=b[j]; d[j+1]=d[j]; b[j]=mp;d[j]=mp1;
}
}
{ }
if (mp.a2==e[i]) { }
else if (mp.a3==e[i]) { }
c[i]=t; c[i]+="1" ; c[i]=t; c[i]+="0" ;
void main() { }
int n;
cout>n;
c=new string[n]; aa(n);
huffman(a,c,n); cout
cout
cout.precision(3); cout
项目三:算术编码
1. 实验内容
对信源概率进行算术编码。
2. 数据结构与算法分析
累积概率的递推公式为:
→
→
→
G (αr ) =G (α) +p (α) P (r ) 。
3. 实验数据与实验结果
本实验采用二元序列为:11111100,p (0)=实验结果:
14
,p (1)=
34
。
图3 算术编码实验结果
4. 程序代码清单:
→
myLength 用于计算码长,myProbability 用于计算p (α) P (r ) 的累积概率,myY ouC 用于计算
→
二元序列的G (α) 并累加,myY ouChengR 用于输出编码结果。
(1) YCAgain
//.h
#ifndef YCAGAIN_H_INCLUDED #define YCAGAIN_H_INCLUDED
extern int myLength(double p);
extern double myProbability(double *a,double p,int n); extern double myYouC(double *a,double p,int n); extern void myYouChengR(double p, int n);
#endif // YCAGAIN_H_INCLUDED //.cpp
#include #include
int myLength(double p) {
int length; double result;
if(p
length = 1;
result = log(1/p)/log(2); length = (int)result; if(result - length > 0) length += 1; return length; }
double myProbability(double *a,double p,int n) {
int i;
double sum =1; for(i=0; i
if(*(a+i)==1) {
sum *=p; //puts("1\t"); }
if(*(a+i)==0) {
sum *=(1-p); //puts("0\t"); } }
return sum; }
double myYouC(double *a, double p, int n) {
double sum=0; // all sum double myA[n]; int i;
int j;
for(i=0; i
{
// my array
if(i>0)
{
for(j=0; j
{
myA[j] = *(a+j);
//printf("myA[%d]: %lf ", j, myA[j]);
}
}
if(*(a+i)==1)
{
myA[i] = 0;
sum += myProbability(myA, p, i+1);
//printf("myA[%d]: %lf\t", i, myA[i]);
}
//puts("\n");
}
return sum;
}
void myYouChengR(double p, int n)
{
int i=0;
do
{
p = 2*p;
if(p>=1)
{
printf("1");
p = p-1;
}
else
{
printf("0");
}
i++;
}while(i
}
(2) main
#include
#include "YCAgain.h"
#define N 8
int main()
{
double a[N] = {1,1,1,1,1,1,0,0};
double p= 0.75;
double myP;
double myL;
double myYCP;
myP = myProbability(a,p,N);
printf("P: %lf\n",myP);
myL = myLength(myP);
printf("L: %lf\n",myL);
myYCP = myYouC(a, p, N);
printf("YCP: %lf\n",myYCP);
printf("Code: ");
myY ouChengR(myYCP, myL);
}
项目四:香农编码
1. 实验内容
香农编码
2. 数据结构与算法分析
(1) 将q 个信源符号按概率递减的方式进行排列:
p 1≥p 2≥... ≥p q
(2) 按上式计算出每个信源符号的码长l i 。
(3) 为了编成唯一可译码,计算第 i 个信源符号的累加概率:
i -1
G
(4) 将累加概率G i 用二进制表示。
(5) 取G i 对应二进制的小数点后 i =∑p k =1k l i 位构成该信源符号的二进制码字。
3. 实验数据与实验结果
(1) 信源概率是随机产生的。
(2) 实验结果如图:
图2 香农编码实验结果
4. 程序代码清单:
myRand 产生信源随机概率,myLength 计算码长,myQuickSort 对信源概率排序,主函数调用。
(1). myRand
// .h
#ifndef MYRAND_H_INCLUDED
#define MYRAND_H_INCLUDED
extern void myRand(double*, int);
#endif // MYRAND_H_INCLUDED
//.cpp
#include
#include
void myRand(double *p, int n)
{
int i=0;
double sum =0;
srand(time(NULL));
for(i=0; i
{
*(p+i) = rand() % 100 + 1;
sum += *(p+i);
}
for(i=0; i
{
*(p+i) /= sum;
}
}
(2)myLength
//.h
#ifndef MYLENGTH_H_INCLUDED
#define MYLENGTH_H_INCLUDED
extern int myLength(double);
#endif // MYLENGTH_H_INCLUDED
//.cpp
#include
int myLength(double p)
{
int length;
double result;
if(p
length = 1;
result = log(1/p)/log(2);
length = (int)result;
if(result - length > 0)
length += 1;
return length;
}
(3)myQuickSort
//.h
#ifndef MYQUICKSORT_H_INCLUDED
#define MYQUICKSORT_H_INCLUDED
extern void myQuickSort(double *, int, int);
#endif // MYQUICKSORT_H_INCLUDED
//.cpp
int mySortBase(double *p, int left, int right)
{
double m_flag;
double tmp;
m_flag = *(p + left);
while(left
{
while( m_flag > *(p+right) )
{
right--;
}
if(m_flag > *(p+right) );
{
tmp = *(p+right);
*(p+right) = *(p+left);
*(p+left) = tmp;
}
while( m_flag
{
left++;
}
if(m_flag
{
tmp = *(p+right);
*(p+right) = *(p+left);
*(p+left) = tmp;
}
}
*(p+left) = m_flag;
return left;
}
void myQuickSort(double *p, int left, int right)
{
int mid;
if(left
{
mid = mySortBase(p,left,right);
myQuickSort(p,left,mid-1);
myQuickSort(p,mid+1,right);
}
}
(4) main
#include
#include "myQuickSort.h"
#include "myRand.h"
#include "myLength.h"
#define N 7
int main()
{
double p[N] = {0.20, 0.19, 0.18, 0.17, 0.15, 0.10, 0.01}; double q[N];
int i,j;
int k; //编码 长度
double b_c; // 二 进制 数
// 生成 随机数
puts("Rand:\n");
myRand(p, N);
for(i=0; i
{
printf("%4.2lf\t", p[i]);
}
puts("\n");
// 排序
puts("Sort:\n");
myQuickSort(p, 0, N-1);
for(i=0; i
{
printf("%4.2lf\t", p[i]);
}
puts("\n");
//累加 概率
puts("Q:");
q[0] = 0;
for(i=1; i
{
q[i] = q[i-1] + p[i-1];
}
for(i=0; i
{
printf("%4.2lf\t", q[i]);
}
puts("\n");
//输出 编码
for(i=0; i
{
printf("P[%d]: %4.2lf\t", i+1, p[i]); printf("Q[%d]: %4.2lf\t", i+1, q[i]); k = myLength(p[i]);
b_c = 2*q[i];
for(j=0; j
{
if(b_c >= 1)
{
putchar('1');
b_c -= 1;
}
else
{
putchar('0');
}
b_c *= 2;
}
puts("\n");
}
return 0;
}