中南大學
資訊理論與編碼
題目關於編碼的實驗
學生姓名
指導教師
學院資訊科學與工程學院
學號專業班級
2023年12月
目錄一、 實驗目的3
二、實驗原理3
三、實驗內容5
四、實驗要求5
五、**除錯結果6
六、實驗**8
一、實驗目的
1. 掌握夏農碼和 huffman 編碼原理和過程。
2. 熟悉 matlab 軟體的基本操作，練習使用matlab 實現夏農碼和huffman
編碼。3. 熟悉 c/c++語言，練習使用c/c++實現夏農碼和huffman 編碼。
4. 應用 huffman 編碼實現檔案的壓縮和解壓縮。
二、 實驗原理
夏農編碼：夏農第一定理指出了平均碼長與信源之間的關係，同時也指出了可以通過編碼使平均碼長達到極限值，這是乙個很重要的極限定理。如何構造這種碼？
夏農第一定理指出，選擇每個碼字的長度ki滿足下式
i(xi)≤k﹤i(xi)+1,
就可以得到這種碼。這種編碼方法就是夏農編碼。
夏農第一定理：
設離散無記憶信源為
s p=s1 s2sq p(s1) p(s2) .....p(sq)
熵為h(s)，其n 次擴充套件信源為
熵為h(sn)。碼符號集x=（x1,x2,…,xr）。先對信源s n 進行編碼，總可以
找到一種編碼方法，構成惟一可以碼，使s 中每個信源符號所需的平均碼長滿足：
當n→∞時
l 是平均碼長λ 是ai 對應的碼字長度
哈夫曼編碼：要完成哈夫曼的編碼和解碼需要首先建立哈夫曼樹，之後對所有字元根據權重進行編碼，最後再對檔案內容進行編碼和解碼。
首先定義適合哈夫曼樹的節點型別，需要定義的有當前節點的字元，當前節點的左子、右子和父親指標。在建立哈夫曼樹之前還需要對出現的字元和權重進行統計和記錄，並且定義乙個可以篩選出最小權重的函式。
初始化樹節點之後開始建立哈夫曼樹。先在所有可能出現的字元中篩選出當前權重最小的兩個字元，將這兩個字元分別作為新節點的左子和右子建立乙個小的二叉樹，並將兩個字元的權重之和賦值給新節點，將新二叉樹放入篩選字元中，再將篩選過的兩個字元從篩選列表中淘汰掉。依次對列表中剩下的字元進行權重最小的篩選，直到根節點（如果編碼表共有n個字元，則2*n-1就為最終根節點）為止，也就是當篩選列表為空的時候，哈夫曼樹即建立完成。
對於哈夫曼編碼樹來說，由於哈夫曼編碼是字首碼，所以所有要編碼的字元最終都將是這顆樹的葉子節點，而其它節點並沒有真正的字元意義。即當哈夫曼編碼樹建立之後，對樹的所有葉子節點進行列印可知道是否有字元遺漏或多餘。
建立哈夫曼編碼表。
建立編碼表時要根據每個出現的字元的權重對建立的哈夫曼樹的每個葉子節點進行編碼。編碼時要從葉子節點出發向根節點進行逆向編碼。判斷如果當前節點為左子則對其編碼『0』，如果當前節點為右子則對其編碼『1』。
以此類推進行編碼直到根節點為止。此時的編碼是逆向的，所以需要將碼值逆向儲存。依次對每乙個葉子節點進行編碼操作，即可得到當前哈夫曼樹的編碼表。
對於碼值的逆向儲存可以使用棧結構，先將乙個碼的每一步編碼存入棧，再在乙個碼結束後出棧至空。當然也可以定義乙個字元型陣列，將值從後向前存入陣列，再將陣列有值部分貼上到新的陣列中進行儲存。本次採用了後者，因為個人認為為此一步操作建立棧結構不划算，而且前乙個設計也已經熟練掌握了棧的方法，此處進行新的嘗試會更好。
對檔案進行編碼。
首先需要建立乙個原始檔案，在檔案中輸入需要編碼的內容。之後將檔案開啟，將其中的內容儲存到字串中以便程式編碼呼叫。開始對需要編碼的字元進行編碼，將字元逐一讀取與剛剛建立的編碼表中的每個葉子節點代表的字元進行比較，找出相同的物件，並將當前節點的編碼列印到螢幕，並將編碼存入到新建的密碼檔案當中。
對檔案進行解碼。
先開啟密碼檔案，將之前編碼後得到的密文內容儲存到字串中以便解碼呼叫。開始對密文的字串進行解碼，樹索引從根節點開始走，當密文中的當前字元是『0』的時候，則索引走向左子節點；當是『1』的時候，則走向右子節點。以此類推，一直走到葉子節點為止，則當前葉子節點所代表的字元即為前一段密文的解碼結果，。
再對下乙個字元依次從根節點開始解碼，如此迴圈對每一段密文進行解碼直到解碼結束。將解碼列印到螢幕，並將解碼結果存入到新的解碼檔案當中。
在解碼之前，還應該先確認之前是否建立了哈夫曼樹並且是否構建了編碼表。不過由於本次將『a』到『z』都進行了編碼，所以此步省略了，因為編碼表是唯一的。需要的時候可以在encoder 函式中先進行判定。
將編碼和解碼寫在了一起，可以在執行時進行選擇呼叫。
三、實驗內容
1.使用matlab 實現夏農碼和huffman 編碼，並自己設計測試案例。
2.使用c\c++實現夏農碼和huffman 編碼，並自己設計測試案例。
3.可以用任何開發工具和開發語言，嘗試實現huffman 編碼應用在資料文
件的壓縮和解壓縮中，並自己設計測試案例。
四、實驗要求
1. 提前預習實驗，認真閱讀實驗原理以及相應的參考書。
2. 認真高效的完成實驗，實驗中服從實驗室管理人員以及實驗指導老師的
管理。3. 認真撰寫實驗報告，內容可以自己編排，可以考慮包括以下一些方面：
原理概述、程式設計與演算法描述、源程式及注釋（程式太長可以只選取
重要部分）、執行輸出結果例項、除錯和執行程式過程中產生的問題及
採取的措施、對實驗的討論分析、總結。
五、**除錯結果
夏農編碼:
哈夫曼編碼：
c語言之夏農編碼：
c語言之哈夫曼編碼：
六、實驗**
matlab實現
夏農編碼：
clear;
a=input('please input a number:') %提示輸入介面
a=fliplr(sort(a));%降序排列
[m,n]=size(a);
for i=1:n
b(i,1)=a(i);%生成b的第1列
end%生成b第2列的元素
a=sum(b(:,1))/2;
for k=1:n-1
if abs(sum(b(1:k,1))-a)<=abs(sum(b(1:k+1,1))-a)
break;
endendfor i=1:n%生成b第2列的元素
if i<=k
b(i,2)=0;
else
b(i,2)=1;
endend%生成第一次編碼的結果
end=b(:,2)';
end=sym(end);
%生成第3列及以後幾列的各元素
j=3;
while (j~=0)
p=1;
while(p<=n)
x=b(p,j-1);
for q=p:n
if x==-1
break;
else
if b(q,j-1)==x
y=1;
continue;
else
y=0;
break;
endend
endif y==1
q=q+1;
endif q==p|q-p==1
b(p,j)=-1;
else
if q-p==2
b(p,j)=0;
end(p)=[char(end(p)),'0'];
b(q-1,j)=1;
end(q-1)=[char(end(q-1)),'1'];
else
a=sum(b(p:q-1,1))/2;
for k=p:q-2
if abs(sum(b(p:k,1))-a)<=abs(sum(b(p:k+1,1))-a);
break;
endend
for i=p:q-1
if i<=k
b(i,j)=0;
end(i)=[char(end(i)),'0'];
else
b(i,j)=1;
end(i)=[char(end(i)),'1'];
endend
end end
p=q;
endc=b(:,j);
d=find(c==-1);
河北工程大學資訊理論與編碼實驗指導書
實驗一 英文文字資訊量的計算 一實驗目的 1 通過本實驗熟悉matlab軟體程式設計環境2 編寫m檔案實現對英文文字資訊量的計算，掌握信源熵的計算方法二實驗要求 1 了解matlab中m檔案的編輯 除錯過程2 編寫程式實現英文文字資訊量的統計，掌握信源熵及資訊量的計算方法三實驗步驟 查詢各個英文本母...
資訊理論與編碼課程總結
08資訊 1 班 0807011039 趙傳來 資訊理論是人們在長期通訊工程的實踐中，由通訊技術與概率論 隨機過程和數理統計相結合而逐步發展起來的一門科學。緒論首先引出資訊的概念，進而討論資訊理論這一科學的研究物件 目的和內容，並簡述本學科的發展歷史 現狀和動向。經總結有以下知識點。資訊是指各個事物...
2019資訊理論與編碼試卷
考試時間120分鐘 班級學號姓名 1.15分 彩色電視顯象管的螢幕上有5 105 個象元，設每個象元有64種彩色度，每種彩度又有16種不同的亮度層次，如果所有的彩色品種和亮度層次的組合均以等概率出現並且各個組合之間相互獨立。1 計算每秒傳送25幀圖象所需要的通道容量 2 如果在加性高斯白雜訊通道上訊...