信息论课程设计(香农、费诺编码)

华北科技学院课程设计说明书华 北 科 技 学 院信息论基础课程设计说明书班级: 计算B092 姓名: 李 宁 (7) 设计题目: 信源编码软件 设计时间: 2012.7.4 至 2012.7.8 指导教师: 李 慧 评 语: _评阅成绩: 评阅教师: 目 录设计总说明1前 言2第1章 总体设计方案31.1 软件结构设计3第2章 算法思想及设计52.1香农编码52.1.1香农编码思想:52.1.2香农编码算法设计:62.2费诺编码62.2.1费诺编码思想62.2.2费诺编码算法设计7第3章 软件详细设计83.1主界面设计83.2功能设计83.2.1香农编码的实现83.2.2费诺编码的实现153.2.3有关文档的链接223.2.4皮肤切换的设计23第4章 软件测试264.1香农编码的测试264.1.1 软件运行及结果测试264.2费诺编码的测试274.2.1 软件运行及结果测试274.3测试结果29第5章 总结30参 考 文 献31附 录32-35-设计总说明早期的数据压缩起源于人们对概率的认识。当对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，平均编码长度就能缩短不少。印象中的著名的Morse电码就是一个范例。信息论之父C.E.Shannon曾指出，任何信息都存在冗余，冗余大小与信息中每个符号的出现概率（不确定性）有关。他所提出的无失真信源编码定理奠定了数据压缩的理论基础。数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。 本文主要采用香农编码和费诺编码方法来描述信源的编码过程。香农编码采用信源符号与概率由用户输入。通过一定的校验代码确保离散信源的正确性。例如单个符号的概率不能大于1，概率和不能大于1，信源概率和不为1时无法编码等校验。由于香农编码是将信源概率由大到小排序的，所以，本软件也实现了这一点，输入时不必考虑信源概率顺序问题，软件会自动按概率排序编码。最后将结果显示在MFC列表控件上。用户可以将最终结果保存成文件。费诺编码通过输入字符串来自动计算单个信源符号的概率。当然，为了方便起见，本软件对费诺编码还提供了打开文件完成信源输入，从而可以更快的输入字符串。进行编码时同样按概率从大到小排序，同样可以将结果保存到文件中。本软件界面友好，方便可靠，用户可根据自己的爱好选择不同的界面风格。在首页加入了好看的Flash，使软件更为美观。同样反映除了本软件的功能特性。根据实验要求和日常压缩数据的习惯，本软件最终完成了以下目标：1、 界面设计友好，美观，数据存储安全，可靠。2、 操作简便、适用，无冗余操作。3、 编码效率较高，编码时间短。关键词: 离散信源；香农编码；费诺编码；信源熵 前 言本课程设计是在学习了信息论与编码和相关开发的软件课程后，让学生通过实际的操作来熟悉信源编码微机实现，培养学生能够独立的完成对相关课题或者项目的分析能力、设计能力和调试能力。本课程设计是衔接在大一时C课程设计之后的，同样是运用MFC程序来设计，联系本学期所学内容，要求有独立的操作界面。由于在以前有过类似的练习，故在这次的课程设计相对以前来说不是太难。在这次的课程设计中，着重培养的是学生的自学能力，以及独立分析互联网上和图书馆里的各种资料，来丰富自己的知识并且提高对数学公式的计算机实现、VC+等软件的实际操作能力。通过这次的课程设计，能够使学生对已经学习过的信息论与编码课程的进一步的掌握，能够对知识进行最大程度的消化融汇。因此这次的课程设计对我们有着非常重要的意义。 本课程设计中用VC+编写出基于MFC界面的简单软件以实现压缩信源的目的。软件应用香农编码的相关理论，经过比较系统合理的编程操作，实现可视化的窗口以方便用户使用。通过简单校验确保信源正确性，保证软件的可靠性。最终将结果保存为文档方便记录编码结果。 通过让完成具体编码算法的程序设计和调试工作，达到提高编程能力和深刻理解编码理论的目的。培养我们使用计算机和查阅参考资料的能力，提高我们的基本设计能力。培养了理论联系实际和独立思考的能力。并激发我们的实际开发创造的意识和能力。培养和提高我们的自学能力以及综合运用所学理论知识去分析解决实际问题的能力。第1章 总体设计方案1.1 软件结构设计香农编码帮助费诺编码编码选择信源编码费诺编码香农编码编码理论菜单皮肤切换图1.1.1 软件功能结构图输入信源符号和概率码长累加概率码字进行编码检验信息平均码长显示结果正确错误信源熵信息率信源符号概率编码效率图1.1.2 香农编码流程图输入字符串序列码长概率码字进行编码打开文件字符串长度显示结果字符个数信源熵信源符号编码效率直接输入概率计算及排序出现次数平均码长图1.1.3 费诺编码流程图第2章 算法思想及设计2.1香农编码2.1.1香农编码思想:设有离散无记忆信源：1按信源符号的概率从大到小的顺序排列，为方便起见，可令23确定满足下列不等式的整数，并令为第个码字的长度4把用二进制表示，用小数点后的位作为的码字例：有一单符号离散无记忆信源对该信源编二进制香农码编码过程 ：2.1.2香农编码算法设计:通过文本框输入信源符号及相应概率。用冒泡法将信源符号及概率依概率由大到小排序，计算其累加概率，用数学公式计算每个信源符号的。最后把结果写入列表控件中，以可视化方式显示编码结果。2.2费诺编码2.2.1费诺编码思想设有离散无记忆信源1.按信源符号的概率从大到小的顺序排队不妨设2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。 3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。 4.如此重复，直至每个组只剩下一个信源符号为止。 5.信源符号所对应的码字即为费诺码。例：有一单符号离散无记忆信源对该信源编二进制费诺码2.2.2费诺编码算法设计通过输入字符串或打开相关文件获取字符串，用字符串处理方法统计每个字符的数量及运算其概率。然后按照每个字符的概率用冒泡法进行排序。然后用递归的思想进行费诺编码，求得了每个字符的二进制码字。并且对编码后的平均码长，以及编码的传输效率进行了求解。第3章 软件详细设计3.1主界面设计编码软件主界面如图3.1.1所示，基本功能在菜单中进行选择。用Falsh CS5软件设计一个简单的Flash插入到主界面，使界面更美观而且形象。 图3.1.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,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_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: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 count-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); singi.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)/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;elsebinj = 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 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.GetItemText(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(%.6f,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,temp2;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 code 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(strPath!=)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:OnInitDialog();/ 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(概率), 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, 80);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 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.length+ = 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,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+) /*冒泡排序*/ 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+=FanoNodei.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);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.SetItemText(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:OnOpenFile() / 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)/判断是否按下打开按钮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软件说明3.2.4皮肤切换的设计以往的软件制作都以系统默认的样式为主，在不断的学习过程中要走向更专业化的道路，简单的皮肤添加可使整个程序样式不再单一，更为人性化。图3.2.7 皮肤切换实例1图3.2.8皮肤切换实例2(1) 皮肤代码：BOOL CMyApp:InitInstance()AfxEnableControlContainer();SkinStart(_T(skinbelv.urf),WINDOW_TYPE_VC,GTP_LOAD_FILE,NULL,NULL);第4章 软件测试4.1香农编码的测试4.1.1 软件运行及结果测试图4.1.1 香农编码结果显示图4.1.2 香农编码错误提示图4.1.3 香农编码结果保存文件测试时发现软件能够较好的完成预期目标，能够保证阻止各类错误信源的输入，以及能够正确按照概率排序并计算正确的码字。最终还可以正确的保存文件。4.2费诺编码的测试4.2.1 软件运行及结果测试文本内容为空时无法进行编码，会有错误提示。图4.2.1 空文本无法操作正确打开文件或输入字符串后，软件能够正确完成编码任务。结果如下图：图4.2.2 费诺编码结果显示图4.2.3 费诺编码保存结果4.3测试结果通过对各个模块功能的测试，最终可以确定本软件的数据计算正确性及可靠性。各个附加功能也能够无误的实现。第5章 总结 通过一周的时间终于完成了香农、费诺编码软件的设计开发，时间的紧迫导致软件依然存在不少问题，以费诺编码不能识别汉子的问题为首。在参考众多的资料后还是没能及时将这个问题解决，不过时间短促，短时间内这个问题也不好解决。在以后的学习生活中我会尝试着完成这个BUG。在课程设计的过程中困难不时的出现，很多时候觉得无可入手，想尽办法也不知道该怎么解决。在这个过程中我深深感受到编程人员经验是多么的宝贵。由于之前已经有过几次关于MFC的课程设计，所以在软件模块设计方面比较容易解决。算法方面，自己尝试着去做了但总是不如意，由于时间关系，还是参考了相关文档。在实践中感觉到了学数学将数学算法转换成计算机算法不是一件容易的事。信源编码软件的设计同样具有一定的挑战性，以往的程序大多是在“黑窗口”下完成的，写一个算法也是一件比较难的事，但路就是这样走过来的，没有今天的一小步就没有明天的一大步。不断地设计，不断的思索，慢慢的就发现自己学会很多。有些问题自然就边的简单了。本次课程设计比较有突破性的是引入了皮肤文件，以往的MFC编程都是在系统默认的背景下运行的，这样的软件总感觉不是很舒服。之前学会了给对话框添加背景图片等一些简单的美化，但还是感觉不够好。于是自己花了一段时间学习了一下皮肤美化程序，功夫不负有心人，这回在这方面感觉小有成就了。不过这也不算什么真真的提高，学好编程的思想更为重要。当然，软件的开发离不开好的资料和同学的交流。在这次课程设计中深深感受到了同学之间交流合作的重要性。交流不但可以发现新的问题，提高解决问题的效率，而且可以快速的学习到新的知识。最后，感谢同学在课程设计中给予我的帮助。让我从中感受到了软件开发时团队的力量以及重要性。参 考 文 献1 陈运. 信息论与编码 M. 北京：电子工业出版社，2011.2 姚领田.精通MFC程序设计 M. 北京：人民邮电出版社，2006.附 录源程序清单1 首页Flash效果代码：BOOL CMyDlg:OnInitDialog()CDialog:OnInitDialog();/ Add About. menu item to system menu./ IDM_ABOUTBOX must be in the system command range.ASSERT(IDM_ABOUTBOX & 0xFFF0) = IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX AppendMenu(MF_SEPARATOR);pSysMenu-AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);/ Set the icon for this dialog. The framework does this automatically/ when the applications main window is not a dialogSetIcon(m_hIcon, TRUE);/ Set big iconSetIcon(m_hIcon, FALSE);/ Set small icon/ TODO: Add extra initialization hereCRect layoutRect; GetClientRect(&layoutRect); char buf1200,buf2200;:GetCur