《信息论课程设计(香农、费诺编码)(共35页).doc》由会员分享，可在线阅读，更多相关《信息论课程设计(香农、费诺编码)(共35页).doc（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上华 北 科 技 学 院信息论基础课程设计说明书班级: 计算B092 姓名: 李 宁 (7) 设计题目: 信源编码软件 设计时间: 2012.7.4 至 2012.7.8 指导教师: 李 慧 评 语: _评阅成绩: 评阅教师: 目 录专心-专注-专业设计总说明早期的数据压缩起源于人们对概率的认识。当对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，平均编码长度就能缩短不少。印象中的著名的Morse电码就是一个范例。信息论之父C.E.Shannon曾指出，任何信息都存在冗余，冗余大小与信息中每个符号的出现概率（不确定性）有关
2、。他所提出的无失真信源编码定理奠定了数据压缩的理论基础。数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。 本文主要采用香农编码和费诺编码方法来描述信源的编码过程。香农编码采用信源符号与概率由用户输入。通过一定的校验代码确保离散信源的正确性。例如单个符号的概率不能大于1，概率和不能大于1，信源概率和不为1时无法编码等校验。由于香农编码是将信源概率由大到小排序的，所以，本软件也实现了这一点，输入时不必考虑信源概率顺序问题，软件会自动按概率排序编码。最后将结果显示在MFC列表控件上。用户可以将最终结果保存成文件。费诺编码通过输入字符串来自动计算单个
3、信源符号的概率。当然，为了方便起见，本软件对费诺编码还提供了打开文件完成信源输入，从而可以更快的输入字符串。进行编码时同样按概率从大到小排序，同样可以将结果保存到文件中。本软件界面友好，方便可靠，用户可根据自己的爱好选择不同的界面风格。在首页加入了好看的Flash，使软件更为美观。同样反映除了本软件的功能特性。根据实验要求和日常压缩数据的习惯，本软件最终完成了以下目标：1、 界面设计友好，美观，数据存储安全，可靠。2、 操作简便、适用，无冗余操作。3、 编码效率较高，编码时间短。关键词: 离散信源；香农编码；费诺编码；信源熵 前 言本课程设计是在学习了信息论与编码和相关开发的软件课程后，让学生
4、通过实际的操作来熟悉信源编码微机实现，培养学生能够独立的完成对相关课题或者项目的分析能力、设计能力和调试能力。本课程设计是衔接在大一时C课程设计之后的，同样是运用MFC程序来设计，联系本学期所学内容，要求有独立的操作界面。由于在以前有过类似的练习，故在这次的课程设计相对以前来说不是太难。在这次的课程设计中，着重培养的是学生的自学能力，以及独立分析互联网上和图书馆里的各种资料，来丰富自己的知识并且提高对数学公式的计算机实现、VC+等软件的实际操作能力。通过这次的课程设计，能够使学生对已经学习过的信息论与编码课程的进一步的掌握，能够对知识进行最大程度的消化融汇。因此这次的课程设计对我们有着非常重要
5、的意义。 本课程设计中用VC+编写出基于MFC界面的简单软件以实现压缩信源的目的。软件应用香农编码的相关理论，经过比较系统合理的编程操作，实现可视化的窗口以方便用户使用。通过简单校验确保信源正确性，保证软件的可靠性。最终将结果保存为文档方便记录编码结果。 通过让完成具体编码算法的程序设计和调试工作，达到提高编程能力和深刻理解编码理论的目的。培养我们使用计算机和查阅参考资料的能力，提高我们的基本设计能力。培养了理论联系实际和独立思考的能力。并激发我们的实际开发创造的意识和能力。培养和提高我们的自学能力以及综合运用所学理论知识去分析解决实际问题的能力。第1章 总体设计方案1.1 软件结构设计香农编
6、码帮助费诺编码编码选择信源编码费诺编码香农编码编码理论菜单皮肤切换图1.1.1 软件功能结构图输入信源符号和概率码长累加概率码字进行编码检验信息平均码长显示结果正确错误信源熵信息率信源符号概率编码效率图1.1.2 香农编码流程图输入字符串序列码长概率码字进行编码打开文件字符串长度显示结果字符个数信源熵信源符号编码效率直接输入概率计算及排序出现次数平均码长图1.1.3 费诺编码流程图第2章 算法思想及设计2.1香农编码2.1.1香农编码思想:设有离散无记忆信源：1按信源符号的概率从大到小的顺序排列，为方便起见，可令23确定满足下列不等式的整数，并令为第个码字的长度4把用二进制表示，用小数点后的位
7、作为的码字例：有一单符号离散无记忆信源对该信源编二进制香农码编码过程 ：2.1.2香农编码算法设计:通过文本框输入信源符号及相应概率。用冒泡法将信源符号及概率依概率由大到小排序，计算其累加概率，用数学公式计算每个信源符号的。最后把结果写入列表控件中，以可视化方式显示编码结果。2.2费诺编码2.2.1费诺编码思想设有离散无记忆信源1.按信源符号的概率从大到小的顺序排队不妨设2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。 3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1
8、”。 4.如此重复，直至每个组只剩下一个信源符号为止。 5.信源符号所对应的码字即为费诺码。例：有一单符号离散无记忆信源对该信源编二进制费诺码2.2.2费诺编码算法设计通过输入字符串或打开相关文件获取字符串，用字符串处理方法统计每个字符的数量及运算其概率。然后按照每个字符的概率用冒泡法进行排序。然后用递归的思想进行费诺编码，求得了每个字符的二进制码字。并且对编码后的平均码长，以及编码的传输效率进行了求解。第3章 软件详细设计3.1主界面设计编码软件主界面如图3.1.1所示，基本功能在菜单中进行选择。用Falsh CS5软件设计一个简单的Flash插入到主界面，使界面更美观而且形象。 图3.1.
9、1 主界面3.2功能设计3.2.1香农编码的实现香农编码是通过编辑框依次输入信源符号和概率的，输入时同时完成校验工作。即单个信源符号概率不能大于1，信源概率和不能大于1，概率和不为1时不能进行编码。正确输入信源符号及其概率后便可计算出该离散信源的码长、码字等信息。可以讲编码结果保存为txt文本等文件。图3.2.1 香农编码界面图3.2.2保存编码结果(1) 添加信源代码：void CShannonCode:OnAdd() / TODO: Add your control notification handler code hereUpdateData(true); CString tempf1
10、,tempf2;/添加之前、之后列表控件值float sum=0.0, sum2=0.0, tempa1, tempa2;if(m_prob = 1.0)/单个信源符号概率不能大于1MessageBox(概率小于1！,提示);return;for(int i = 0;i = 1.0)/如果和大于等于1，则不再添加MessageBox(信源概率和已等于1！无法添加！,提示);return;CString s1,s2;m_list1.InsertItem(r,);s1.Format(%s,m_single);m_list1.SetItemText(r,0,s1);s2.Format(%.6f,m_
11、prob);m_list1.SetItemText(r,1,s2);r+;count+;for(int j = 0;j 1.0)/如果添加后概率和大于1，则最后添加的信源不做计算MessageBox(当前信源添加后信源概率和大于1！,提示);s1.Format(%s,);m_list1.SetItemText(r-1,0,s1);s2.Format(%s,);m_list1.SetItemText(r-1,1,s2);r-;count-;return;m_single = ;m_prob = 0.0;UpdateData(false); (2) 算法实现代码：void CShannonCode
12、:Count() CString singe,temp,s;char binN=;CString singleN;/信源符号数组float pN;/信源概率数组int i,j,c3;float btemp,vtemp;double c1,c2;/读取输入的信源符号和概率for(i = 0; i count; i+)singlei =m_list1.GetItemText(i,0); temp=m_list1.GetItemText(i,1); pi = (float)(atof(temp);/信源符号和概率按概率大小排序for(i = 1;i count;i+) for(j = 0;j cou
13、nt-i;j+)if(pj pj+1)ExChangeChar(single,j,j+1);ExChangePsingle(p,j,j+1);for(i = 0; i count; i+)m_list2.InsertItem(i,);temp.Format( %s ,singlei);m_list2.SetItemText(i,0,temp);/信源符号temp.Format(%.6f,pi);m_list2.SetItemText(i,1,temp);/概率/计算累加概率;for(i = 0; i count; i+)temp = m_list2.GetItemText(i,1); sing
14、i.pa = (float)(atof(temp); sing0.paa = 0;for(i = 0; i count; i+) singi.paa =singi-1.pa+singi-1.paa; for(i = 0; i count; i+)s.Format(%.6f,singi.paa); m_list2.SetItemText(i,2,s);/累加概率/计算码字长度; for(i = 0;i count;i+) for(j = 0;j =-log(singi.pa)/log(2)&j1-log(singi.pa)/log(2)singi.k=j;c1 = -log(singi.pa)/
15、log(2);c2 = 1-log(singi.pa)/log(2);c3 = int(c1);if(c3-c1) = 0)singi.k = c3;elsesingi.k = c3+1;for(i = 0; i count; i+)s.Format(%d,singi.k); m_list2.SetItemText(i,3,s);/码字长度 /计算二进制数; for(i = 0;i count;i+)singi.binary0 =0;singi.binary1 =.;btemp = singi.paa;for(j=0;j= 1)binj = 1;btemp = btemp*2-1;elsebi
16、nj = 0;btemp = btemp*2;singi.binaryj+2 = binj; singi.binaryj+2 =0; for(i = 0; i count; i+)s.Format(%s,singi.binary); m_list2.SetItemText(i,4,s);/二进制数/计算码字; for(i = 0;i count;i+)vtemp = singi.paa;for(j = 0;j =1)singi.codej=1;vtemp=vtemp*2-1;elsesingi.codej=0;vtemp=vtemp*2; singi.codej=0;for(i = 0; i
17、count; i+)s.Format(%s,singi.code); m_list2.SetItemText(i,5,s);/码字for(i = 0;i count ; i+)for(int j = 0;j 6; j+)Result1 = Result1 + m_list2.GetItemText(i,j)+t;Result1 = Result1 + n;void CShannonCode:CodeEfficiency()/计算并显示编码效率CString temp,s;int i;double K,Hx,R,A; for(i = 0; i count; i+)temp = m_list2.G
18、etItemText(i,1); singi.pa =(float)(atof(temp); K = sing0.pa*sing0.k;Hx = -sing0.pa*log(sing0.pa)/log(2); for(i = 0; i count; i+)K = K+singi.pa*singi.k;Hx = Hx+(-singi.pa*log(singi.pa)/log(2); R = (K*log(2)/log(2)/1; A = Hx/R; /A代表编码效率,转化为百分比; s.Format(%.6f,K); m_list3.InsertItem(0,s,0); s.Format(%.6
19、f,Hx); m_list3.SetItemText(0,1,s); s.Format(%.6f,R); m_list3.SetItemText(0,2,s); s.Format(%.6f,A); m_list3.SetItemText(0,3,s);/显示结果void CShannonCode:OnResult() / TODO: Add your control notification handler code herem_list2.DeleteAllItems();/清空已有数据m_list3.DeleteAllItems();CString temp;float sum=0.0,t
20、emp2;for(int i=0;icount;i+)/计算信源概率和 temp=m_list1.GetItemText(i,1);temp2=(float)(atof(temp);sum = sum +temp2;if(sum != 1.0)/信源概率和不为1时不进行编码MessageBox(信源概率之和不为1！请检查！,提示);return;Count();/编码结果CodeEfficiency();/编码效率(3) 保存代码：void CShannonCode:OnBUTTONSave() / TODO: Add your control notification handler cod
21、e hereUpdateData(true); CFileDialog dlgSave(false,NULL,NULL,OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,Txt Files(*.txt)|*.txt|Dat Files(*.dat)|*.dat|All Files (*.*)|*.*|,AfxGetMainWnd();/构造文件打开对话框CString strPath; /声明变量if(dlgSave.DoModal() = IDOK)/判断是否按下打开按钮strPath=dlgSave.GetPathName();/获得文件路径和文件名 if(strP
22、ath!=)FILE *pFile=fopen(strPath,w);if (pFile)fprintf(pFile,%s,Result1);fclose(pFile);UpdateData(false);3.2.2费诺编码的实现费诺编码可由用户打开文本获取信源序列，也可直接输入序列。输入内容为空时会有提示信息弹出。正确读到文本域内容后点击编码按钮即可用算法实现各字符概率的计算并按概率排序，进而对其进行编码。列表框内容也可以进行保存。图3.2.3 费诺编码界面图3.2.4 打开文件读取文本(1) 主要代码BOOL CFanoCode:OnInitDialog() CDialog:OnInitD
23、ialog();/ TODO: Add extra initialization here/编码结果栏初始化; m_list1.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_HEADERDRAGDROP|LVS_EX_ONECLICKACTIVATE|LVS_EX_GRIDLINES);m_list1.InsertColumn(0,_T(信源符号), LVCFMT_CENTER, 60);m_list1.InsertColumn(1,_T(出现次数), LVCFMT_CENTER, 70);m_list1.InsertColumn(2,_T(概率),
24、 LVCFMT_CENTER, 80); m_list1.InsertColumn(3,_T(码字长度), LVCFMT_CENTER, 60);m_list1.InsertColumn(4,_T(码字), LVCFMT_CENTER, 80); /信源信息级编码效率栏初始化; m_list2.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_HEADERDRAGDROP|LVS_EX_ONECLICKACTIVATE|LVS_EX_GRIDLINES);m_list2.InsertColumn(0,_T(字符串长度), LVCFMT_CENTER, 8
25、0);m_list2.InsertColumn(1,_T(字符个数), LVCFMT_CENTER, 80);m_list2.InsertColumn(2,_T(平均码长), LVCFMT_CENTER, 80);m_list2.InsertColumn(3,_T(信源熵), LVCFMT_CENTER, 80);m_list2.InsertColumn(4,_T(编码效率), LVCFMT_CENTER, 80);return TRUE; / return TRUE unless you set the focus to a control / EXCEPTION: OCX Property
26、 Pages should return FALSEint Group(CodeType FanoNode,int low,int high) /*一次分组(一分为二)并编码*/float MinSum=FanoNodelow.data,MaxSum=FanoNodehigh.data;FanoNodelow.bitFanoNodelow.length+=1;FanoNodehigh.bitFanoNodehigh.length+=0;while(low+1 MaxSum)MaxSum+= FanoNode-high.data;FanoNodehigh.bitFanoNodehigh.leng
27、th+ = 0; /*编码加0*/elseMinSum+=FanoNode+low.data;FanoNodelow.bitFanoNodelow.length+ = 1; /*编码加1*/return low; /*返回分组的第一部分的上界*/void FanoEncoding(CodeType FanoNode,int s,int t)/*递归进行费诺编码*/if(s t)int pivotloc = Group(FanoNode,s,t);if(s t-1)FanoEncoding(FanoNode,s,pivotloc);FanoEncoding(FanoNode,pivotloc+1
28、,t);int IsnotIn(char a,char t,int n,int count) /*检查字符a是否在数组t中*/for(int k = 0;k 200)MessageBox(字符串长度超过200！,提示);return;t0 = str0;count0+;for(int i = 1;i SLength;i+)/*去除重复的字符，并计算个数*/if(IsnotIn(stri,t,m,count)tm = stri;countm+;for(int j = 0;j m;j+)pj=float(countj)/float(SLength);for(i = 1;i m;i+) /*冒泡排序
29、*/ for(j = 0;j m-i;j+)if(pj pj+1)ExChangeFloat(p,j,j+1);ExChangeChar(t,j,j+1);/*相应的计数器数值也交换 */int temp;temp = countj;countj = countj+1;countj+1 = temp;for(i = 0;i m;i+)/*将值赋给结构体数组 */FanoNodei.data = pi;FanoNodei.length =0;FanoNodei.Character = ti;FanoEncoding(FanoNode,0,m-1);for( i=0;im;i+)K+=FanoNo
30、dei.data*FanoNodei.length; /*求平均码长*/H+=-FanoNodei.data*log(FanoNodei.data); /*求信源熵H(X)的大小*/R = H/K;CString s1,s2,s3;for(i = 0;i m;i+)m_list1.InsertItem(i,);s1.Format( %ct,FanoNodei.Character);m_list1.SetItemText(i,0,s1);s1.Format(%d ,counti);m_list1.SetItemText(i,1,s1);s1.Format(%.6f,FanoNodei.data)
31、;m_list1.SetItemText(i,2,s1);s1.Format( %d ,FanoNodei.length);m_list1.SetItemText(i,3,s1);s3=;for(int j=0;jFanoNodei.length;j+)s2.Format(%d,FanoNodei.bitj);s3=s3+s2;m_list1.SetItemText(i,4,s3);m_list2.InsertItem(0,);s2.Format(%d,SLength);m_list2.SetItemText(0,0,s2);s2.Format(%d,m);m_list2.SetItemTex
32、t(0,1,s2);s2.Format(%.6f,K);m_list2.SetItemText(0,2,s2);s2.Format(%.6f,H);m_list2.SetItemText(0,3,s2);s2.Format(%.6f,R);m_list2.SetItemText(0,4,s2);/遍历列表，获取相应值，用于保存for(i = 0;i 5 ; i+)for(j = 0;j m; j+)Result = Result + m_list1.GetItemText(i,j)+t;Result = Result + n;(2) 读文件代码：void CFanoCode:OnOpenFil
33、e() / TODO: Add your control notification handler code hereUpdateData(true); CFileDialog dlgOpen(true,NULL,NULL,OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,Txt Files(*.txt)|*.txt|Dat Files(*.dat)|*.dat|All Files (*.*)|*.*|,AfxGetMainWnd();/构造文件打开对话框CString strPath; /声明变量if(dlgOpen.DoModal() = IDOK)/判断是否按下打
34、开按钮strPath = dlgOpen.GetPathName();/获得文件路径m_FilePath.Format(%s,strPath);/显示文件路径FILE *pFile = fopen(strPath,r);/以读形式打开文件if (pFile)/判断文件是否被正确打开char pchData1000 = 0;/定义数据缓冲区 fread(pchData,sizeof(char),1000,pFile); /读取数据到缓冲区中fclose(pFile);/关闭文件m_text.Format(%s,pchData);UpdateData(false);3.2.3有关文档的链接编码软件自然不能缺少对编码的理论介绍，这一点可通过网页形式展现出来。通过单击触发打开制作好的简单网页。可分别对每种编码进行简单介绍。图3.2.5 编码理论介绍(1) 主要代码void CMyDlg:OnMENUITEMSourcecoding() / TODO: Add your command handler code hereShellExecute(NULL, _T(open),webSourcecoding.html, NULL,NULL, SW_SHOW);软件设计离不开软件说明书，本软件的说明书也是通过网页完成的，这样可以保证说明书不被修改，保持原版特性。图3.2.6