漢明碼編譯碼文檔

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

圖6編碼流程圖輸入信息碼a3a2a1a0，輸出(7,4)漢明碼b6b5b4b3b2首先，輸入信息碼a3a2port(a:instd_logic_vector(3downto0);然后，根據(jù)式()，就可以得到監(jiān)督位與信息碼之間的對(duì)應(yīng)關(guān)系，使用異或運(yù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)督位與原來(lái)輸入的信息一起輸出，就是編碼結(jié)束了。第四章編譯程序的調(diào)試與分析4.1(7,4)漢明碼的編碼程序的編譯在max+plusⅡ中采用原理圖輸入如下所示：步驟一:指定設(shè)計(jì)工程名字步驟二:建立一個(gè)新的圖形文件步驟三：輸入圖元和功能符號(hào)步驟四：命名引腳和鏈接邏輯符號(hào)編譯結(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Ⅱ采用波形編輯器：先建立一個(gè)仿真通道文件bm·scf，如下列圖示：編輯的wdf文件如下圖:編譯結(jié)果如下：4.3〔7,4)漢明碼的編碼程序的編譯和仿真分析

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