漢明碼編譯碼文檔

第一章緒論過失控制編碼1.1概述數(shù)字信號在傳輸過程中，由于受到干擾的影響，碼元波形將變壞。接收端收到后可能發(fā)生錯誤判決。由于乘性干擾引起的碼間串擾，可以采用均衡的方法來糾正。而加性干擾的影響那么需要用其他方法解決。在設(shè)計數(shù)字通信系統(tǒng)時，應該首先從合理選擇調(diào)制制度，解調(diào)方法以及發(fā)送功率等方面考慮，使加性干擾缺乏以影響到誤碼率要求。在仍不能滿足要求時，就要考慮采用過失控制措施了。從過失控制角度看，按加性干擾引起的錯碼分布規(guī)律不同，信道可以分為3類，即隨機信道，突發(fā)信道和混合信道。在隨機信道中，錯碼的出現(xiàn)是隨機的，而且錯碼之間是統(tǒng)計獨立的。在突發(fā)信道中，錯碼是成串集中出現(xiàn)的，而且在短促的時間段之間存在較長的無錯碼區(qū)間。把既存在隨機錯碼又存在突發(fā)錯碼的的信道稱為混合信道。對于不同類型的信道，應該采用不同的過失控制技術(shù)。1.2糾錯編碼原理我們把信息碼分組，為每組信息碼附加假設(shè)干監(jiān)督碼的編碼稱為分組碼(blockcode).在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。分組碼一般用符號〔n，k〕表示，其中n是碼組的總位數(shù)，又稱為碼組的長度〔碼長〕，k是碼組中信息碼元的數(shù)目，n-k=r為碼組中的監(jiān)督碼元的數(shù)目，或者稱為監(jiān)督位數(shù)目，分組碼的結(jié)構(gòu)如圖2示，圖中前k位為信息位，后面附加r個監(jiān)督位。其中an-1到ar為k個信息位，ar-1到a0為r個監(jiān)督位。an-1an-2………arar-1………ao圖4分組碼的結(jié)構(gòu)在分組碼中，把碼組中“1”的個數(shù)稱為碼組的重量，簡稱碼重。把兩個碼組中對應位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱為碼距，碼距又稱為漢明距離。我們把某種編碼中各個碼組之間距離的最小值稱為最小碼距〔d0一種編碼的最小距離的大小直接關(guān)系著這種編碼的檢錯與糾錯能力：〔1〕為檢測e個錯碼，要求最小碼距d0大于等于e+1;(2)為了糾正t個錯碼，要求最小碼距d0大于等于2t+1；(3)為糾正t個錯碼同時檢測e個錯碼，要求最小碼距d0大于等于e+t+1〔e>t〕.1.3漢明碼編碼Hamming碼中文稱作漢明碼。漢明碼是由漢明于1950年提出的，具有糾正一位錯誤能力的線性分組碼它的突出特點是：編譯碼電路簡單，易于硬件實現(xiàn)；用軟件實現(xiàn)編譯碼算法時，軟件效率高；而且性能比擬好..1漢明碼的定義：假設(shè)一致監(jiān)督矩陣H的列是由不全為0且互不相同的所有二進制m(m≥2的正整數(shù))重組成，那么由此H矩陣得到的線性分組碼稱為[2m-1,2m-1-m，漢明碼的構(gòu)造特點：1)．紿定一個m，我們由二進制m重組成線性分組碼的監(jiān)督矩陣H，由二進制m重來標定一個發(fā)生錯誤的位置。由此可知，二進制m重共有2種位組合，去掉一個全為0的位組合，那么余下共有2m-1種位組合。故漢明碼的最大碼長n=22)．由上面分析，我們可以知道：m即是漢明碼監(jiān)督位的位數(shù)。故一個漢明碼中，信息位的位數(shù)k=n—m=2m3)．漢明碼的距離為3，因此可以糾正1位錯誤，檢出2位錯誤。漢明碼編碼的主要算法漢明碼的編碼就是如何根據(jù)信息位數(shù)k，求出糾正一個錯誤的監(jiān)督矩陣H，然后根據(jù)H求出信息位所對應的碼字。構(gòu)造漢明碼監(jiān)督矩陣H的方法很多，這里僅介紹一種。1)根據(jù)的信息位數(shù)k，從漢明不等式中求出校驗位數(shù)m=n-k；2)在每個碼字C：(C1，C2，?，C2m-1)中，用c02，c12，cn-12作為監(jiān)督位，剩下的位作為信息位；3)用二進制數(shù)字表示2m-1列，得到2m-1列和m行監(jiān)督矩陣4)用3步的H形成HCT=0，從而得出m個監(jiān)督方程；5)將的信息代入方程組，然后求出滿足上述方程組的監(jiān)督位c(i=0，1，?，m一1)。例如，用以上方法，很容易求出[7，4，3]漢明碼的監(jiān)督矩陣：1110100H=11010101011001及編碼所對應的碼字為C=011001。1.4.主要應用領(lǐng)域1.4.1隨著現(xiàn)代通信技術(shù)和計算機技術(shù)的高速開展，無線數(shù)字通信的應用越來越廣泛.鋼絲繩張力檢測系統(tǒng)將數(shù)字無線通信、測量和計算機技術(shù)結(jié)合在一起，其功能是將電梯、纜車或提升機鋼絲繩張力檢測信息轉(zhuǎn)換成數(shù)字信號，通過無線方式傳送給控制中心，由控制中心對原始數(shù)據(jù)進行處理、分析和計算，輸出人們想要的結(jié)果，做出相應的判斷與控制。因此，鋼絲繩張力的檢測系統(tǒng)對使用鋼絲繩的提升設(shè)備的平安運行起著至關(guān)重要的作用。數(shù)字存儲系統(tǒng)隨著PC機的日益普及，存儲對象的日漸多元化，用戶對存儲需求不斷升級，如何保證數(shù)據(jù)穩(wěn)定、高速傳輸?RAID(”RedundantArrayofIndependentDisk”)獨立冗余磁盤陣列解決了這個難題，并且成為目前存儲的主流技術(shù)。RAID之所以實現(xiàn)數(shù)據(jù)高速、可靠的傳輸，一個關(guān)鍵的核心技術(shù)就是應用了一定的過失控制編碼技術(shù)。在RAID眾多系列中最復雜的RAID2中就采用了”漢明碼(HammingCode)過失控制編碼技術(shù)”，它在數(shù)據(jù)存儲及移動過程中進行過失控制，對傳輸過程中出現(xiàn)的過失自動進行糾正，保證了數(shù)據(jù)傳輸?shù)钠桨部煽啃浴１Ｃ芡ㄐ偶夹g(shù)隨著計算機網(wǎng)絡(luò)的開展及應用的普及，特別是在軍事指揮，情報系統(tǒng)，銀行系統(tǒng)的應用，通信的可靠性及保密性要求越來越高，這就要求研制新的高可靠性及保密性通信技術(shù)。接收端不僅能從接收到的信息中檢測出傳輸過程中的錯誤而且能糾正之。針對IBM-PC微計算機之間通信過程中的糾錯技術(shù)提出了一種在通信計算機之間不增加任何硬件設(shè)備的情況下，僅用編寫一段糾錯編碼(發(fā)送端)和糾錯譯碼(接收端)的軟件方法到達計算機通信糾錯和保密的目的，即利用漢明碼編碼實現(xiàn)檢錯、糾錯的具體方案，這樣做的優(yōu)點是：在保持一定功能和相應速度的前提下，采用軟件方法，不僅可以提高通信過程的可靠性，而且還可以提高通信系統(tǒng)本身的可靠性。第二章(7,4)漢明碼的編碼原理2.1根本構(gòu)造對于碼組長度為n、信息碼元為k位、監(jiān)督碼元為r＝n－k位的分組碼，常記作〔n，k〕碼，如果滿足2r－1≥n，那么有可能構(gòu)造出糾正一位或一位以上錯誤的線性碼。下面我們通過〔7，4〕漢明碼的例子來說明如何具體構(gòu)造這種碼。設(shè)分組碼〔n，k〕中，k=4，為能糾正一位誤碼，要求r≥3?，F(xiàn)取r＝3，那么n＝k＋r＝7。我們用a0ala2a3a4a5a6表示這7個碼元，用S1、S2、S3表示由三個監(jiān)督方程式計算得到的校正子，并假設(shè)三位S1S1S2S3錯碼位置S1S2S3錯碼位置001a0101a4010al110a5100a2111a6011a3000無錯碼表1校正子和錯碼位置關(guān)系由表可知，當誤碼位置在a2、a4、a5、a6時，校正子S1＝1；否那么S1＝0。因此有S1＝a6⊕a5⊕a4⊕a2，同理有S2＝a6⊕a5⊕a3⊕a1和S3＝a6⊕a4⊕a3⊕a0。在編碼時a6、a5、a4、a3為信息碼元，a2、a1、a0為監(jiān)督碼元。那么監(jiān)督碼元可由以下監(jiān)督方程唯一確定a6⊕a5⊕a4⊕a2=0a6⊕a5⊕a3⊕a1=0()a6⊕a4⊕a3⊕a0=0也即a2＝a6⊕a5⊕a4a1＝a6⊕a5⊕a3〔〕a0=a6⊕a4⊕a3由上面方程可得到表2所示的16個許用碼組。在接收端收到每個碼組后，計算出S1、S2、S3，如果不全為0，那么表示存在錯誤，可以由表1確定錯誤位置并予以糾正。舉個例子，假設(shè)收到碼組為0000011，可算出S1S2S3=011,由表1可知在a3上有一誤碼。通過觀察可以看出，上述〔7，4〕碼的最小碼距為dmin＝3，糾正一個誤碼或檢測兩個誤碼。如果超出糾錯能力那么反而會因“亂糾”出現(xiàn)新的誤碼.信息位監(jiān)督位信息位監(jiān)督位a6aa2a1a6aa2a0000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111表2〔7,4〕漢明碼的許用碼組2.2監(jiān)督矩陣上面有提到過，線性碼是指信息位和監(jiān)督位滿足一組線性代數(shù)方程的碼，式()就是這樣的例子，現(xiàn)在將它改寫成1*a6⊕1*a5⊕1*a4⊕0*a3⊕1*a2⊕0*a1⊕0*a0=01*a6⊕1*a5⊕0*a4⊕1*a3⊕0*a2⊕1*a1⊕0*a0=0()1*a6⊕0*a5⊕1*a4⊕1*a3⊕0*a2⊕0*a1⊕1*a0=0我們可以將式〔〕表示成如下的矩陣形式a6a51110100a401101010a3=0〔〕1011001a20a1a0式〔〕還可以簡記為H*AT=0T或A*HT=0〔〕其中1110100H=1101010A=a6a5a41011001上角“T”表示將矩陣轉(zhuǎn)置。例如HT是H的轉(zhuǎn)置，即HT的第一行為H的第一列，第二行為第二列。我們將H稱為監(jiān)督矩陣(parity—checkmatrix).只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關(guān)系就完全確定了。由〔〕和(1.1.5)都可以看出，H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目r，H的每一行中的“1”的位置表示相應碼元之間存在的監(jiān)督關(guān)系。式〔1.1.4〕中的H矩陣可以分為兩局部。1110100H=1101010=PIr()1011001式中：P為r*k階矩陣；Ir為r*r階單位方陣。2.3生成矩陣由代數(shù)理論可知，H矩陣的的各行應該是線性無關(guān)的，否那么將得不到r個線性無關(guān)的監(jiān)督關(guān)系式，從而也得不到r個獨立的監(jiān)督位。假設(shè)一矩陣可以寫成PIr的矩陣形式，那么其各行一定是線性無關(guān)的。因為容易驗證Ir的各行是線性無關(guān)的，故PIr的各行也是線性無關(guān)的。類似于〔〕那樣，〔1.1.2〕可以改寫成a6a21110a5a1=1101a4〔〕a01011a3或者111a2a1a0=a6a5a4a3110=a6101011其中，Q為一個k*r階矩陣，它為P的轉(zhuǎn)置，即Q=PT式〔〕表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督位。我們將Q的左邊加上一個k*k階單位方陣，就構(gòu)成一個矩陣G1000111G=IKQ=0100110()00101010001011G稱為生成矩陣〔generatormatrix〕，因為由它可產(chǎn)生整個碼組，即有a6a5a4a3a2a第三章(7,4)漢明碼編碼的設(shè)計3.1(7,4)漢明碼的編碼思路(7,4)漢明碼的編碼就是將輸入的四位信息碼編成七位的漢明碼，即參加三位監(jiān)督位。根據(jù)式(〕A=[a6a5a4a3]·G可知，信息碼與生成矩陣G1000111G=010011000101010001011所以，可以得出如下方程組a6=a6

a5=a5

a4=a4

a3=a3()

a2=a6+a5+a4

a1=a6+a5+a3

a0=a6+a4+a3

根據(jù)式()就可以編出編碼程序了。

3.2(7,4)漢明碼的編碼程序設(shè)計根據(jù)(7,4)漢明碼的編碼原理，首先畫出程序設(shè)計的流程圖：

圖6編碼流程圖輸入信息碼a3a2a1a0，輸出(7,4)漢明碼b6b5b4b3b2首先，輸入信息碼a3a2port(a:instd_logic_vector(3downto0);然后，根據(jù)式()，就可以得到監(jiān)督位與信息碼之間的對應關(guān)系，使用異或運算，即：b(6)<=a(3);

b(5)<=a(2);

b(4)<=a(1);

b(3)<=a(0);b(2)<=a(3)xora(2)xora(1);b(1)<=a(3)xora(2)xora(0);b(0)<=a(3)xora(1)xora(0);最后，將算好的監(jiān)督位與原來輸入的信息一起輸出，就是編碼結(jié)束了。第四章編譯程序的調(diào)試與分析4.1(7,4)漢明碼的編碼程序的編譯在max+plusⅡ中采用原理圖輸入如下所示：步驟一:指定設(shè)計工程名字步驟二:建立一個新的圖形文件步驟三：輸入圖元和功能符號步驟四：命名引腳和鏈接邏輯符號編譯結(jié)果如下：在在max+plusⅡ采用文本輸入法：(7,4)漢明碼的編碼程序如下

libraryieee;

useieee.std_logic_1164.all;

entitybmis

port(a:instd_logic_vector(3downto0);

b:outstd_logic_vector(6downto0));

endbm;

architecturestrcofbmis

begin

b(6)<=a(3);

b(5)<=a(2);

b(4)<=a(1);

b(3)<=a(0);b(2)<=a(3)xora(2)xora(1);

b(1)<=a(3)xora(2)xora(0);

b(0)<=a(3)xora(1)xora(0);

endstrc;文本編輯如下:編譯結(jié)果:4.2(7,4)漢明碼的編碼程序的仿真在max+plusⅡ采用波形編輯器：先建立一個仿真通道文件bm·scf，如下列圖示：編輯的wdf文件如下圖:編譯結(jié)果如下：4.3〔7,4)漢明碼的編碼程序的編譯和仿真分析

按照上述編碼程序的編寫思路，編寫好程序，點擊，進行編譯，出現(xiàn)一些錯誤，列舉如下：Error1