矩陣分析在漢明碼中的應用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上矩陣分析在漢明碼中的應用摘要：數(shù)字信號在傳輸過程中，由于受到干擾的影響，碼元波形將變壞。接收端收到后可能發(fā)生錯誤判決。由于乘性干擾引起的碼間串擾，可以采用均衡的辦法來糾正。而加性干擾的影響則需要用其他辦法解決。在設計數(shù)字通信系統(tǒng)時，應該首先從合理選擇調(diào)制制度，解調(diào)方法以及發(fā)送功率等方面考慮，使加性干擾不足以影響到誤碼率要求。在仍不能滿足要求時，就要考慮采用差錯控制措施了，本文在基于矩陣分析的基礎上對漢明編碼進行介紹，效率高，提高抗突發(fā)干擾的能力。關鍵詞：矩陣分析 漢明碼引言矩陣如今在各個領域都有廣泛的應用，例如在生活中，在經(jīng)濟中，在通信領域，數(shù)字圖像領域中等各個方面應

2、用很廣泛。在生活中的魔方也是根據(jù)矩陣分析，在excel表格中，我們可以根據(jù)矩陣很簡單的計算出各行各列的和，在數(shù)字圖像處理中，我們將圖像用矩陣表示，像素來表示，一個像素代表一點，有很多像素組成一幅數(shù)字圖像，再對矩陣進行各種變換從而實現(xiàn)數(shù)字圖像處理，在通信領域中我們也經(jīng)常用到矩陣，例如編碼，我們下面將對矩陣分析在漢明編碼中的應用進行具體分析1.漢明碼編碼Hamming碼中文稱作漢明碼。漢明碼是由漢明于1950年提出的，具有糾正一位錯誤能力的線性分組碼 它的突出特點是：編譯碼電路簡單，易于硬件實現(xiàn)；用軟件實現(xiàn)編譯碼算法時，軟件效率高；而且性能比較好.1.1 漢明碼的定義：若一致監(jiān)督矩陣H 的列是由不

3、全為0且互不相同的所有二進制m(m2的正整數(shù))重組成，則由此H矩陣得到的線性分組碼稱為2m-1,2m-1-m，3漢明碼。1.2 漢明碼的構(gòu)造特點：1)紿定一個m，我們由二進制m 重組成線性分組碼的監(jiān)督矩陣H，由二進制m重來標定一個發(fā)生錯誤的位置。由此可知，二進制m 重共有2 種位組合，去掉一個全為0的位組合，則余下共有2m-1種位組合。故漢明碼的最大碼長n=2m-1。2)由上面分析，我們可以知道：m 即是漢明碼監(jiān)督位的位數(shù)。故一個漢明碼中，信息位的位數(shù)k=nm=2m-1-m3)漢明碼的距離為3，因此可以糾正1位錯誤，檢出2位錯誤。1.3 漢明碼編碼的主要算法漢明碼的編碼就是如何根據(jù)信息位數(shù)k，

4、求出糾正一個錯誤的監(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)督矩陣H；4)用3步的H形成HCT =0，從而得出m個監(jiān)督方程；5)將已知的信息代入方程組，然后求出滿足上述方程組的監(jiān)督位c (i=0，1， ，m一1)。例如，用以上方法，很容易求出7，4，3漢明碼的監(jiān)督矩陣：1 1 1 0 1 0 0 H= 1 1

5、 0 1 0 1 0 1 0 1 1 0 0 1及編碼所對應的碼字為C=。對于碼組長度為n、信息碼元為k位、監(jiān)督碼元為rnk位的分組碼，常記作（n，k）碼，如果滿足2r1n，則有可能構(gòu)造出糾正一位或一位以上錯誤的線性碼。下面我們通過（7，4）漢明碼的例子來說明如何具體構(gòu)造這種碼。設分組碼（n，k）中，k = 4，為能糾正一位誤碼，要求r3。現(xiàn)取r3，則nkr7。我們用a0ala2a3a4a5a6表示這7個碼元，用S1、S2、S3表示由三個監(jiān)督方程式計算得到的校正子，并假設三位S1、S2、S3校正子碼組與誤碼位置的對應關系如表1所示。S1S2S3錯碼位置S1S2S3 錯碼位置 001 a0 10

6、1 a4 010 al 110 a5 100 a2 111 a6 011 a3 000 無錯碼 表1 校正子和錯碼位置關系由表可知，當誤碼位置在a2、a4、a5、a6時，校正子S11；否則S10。因此有S1a6a5a4a2，同理有S2a6a5a3a1和S3a6a4a3a0。在編碼時a6、a5、a4、a3為信息碼元，a2、a1、a0為監(jiān)督碼元。則監(jiān)督碼元可由以下監(jiān)督方程唯一確定 a6a5a4a2 = 0 a6a5a3a1 = 0 (1.1.1) a6a4a3a0 = 0 也即a2a6a5a4 a1a6a5a3 （ 1.1.2）a0 = a6a4a3由上面方程可得到表2所示的16個許用碼組。在接收

7、端收到每個碼組后，計算出S1、S2、S3，如果不全為0，則表示存在錯誤，可以由表1確定錯誤位置并予以糾正。舉個例子，假設收到碼組為，可算出S1S2S3=011,由表1可知在a3上有一誤碼。通過觀察可以看出，上述（7，4）碼的最小碼距為dmin3，糾正一個誤碼或檢測兩個誤碼。如果超出糾錯能力則反而會因“亂糾”出現(xiàn)新的誤碼. 信息位 監(jiān)督位 信息位 監(jiān)督位 a6a5a4a3 a2a1a0 a6a5a4a3 a2a1a000000001 0010 0011 0100 0101 01100111 000 011 101 110 110 101 011 0001000100110101011110011

8、0111101111 111100010001001010100111 表2 （7,4）漢明碼的許用碼組2.監(jiān)督矩陣 上面有提到過，線性碼是指信息位和監(jiān)督位滿足一組線性代數(shù)方程的碼，式(1.1.1)就是這樣的例子，現(xiàn)在將它改寫成 1*a61*a51*a40*a31*a20*a10*a0=0 1*a61*a50*a41*a30*a21*a10*a0=0 (1.1.3) 1*a60*a51*a41*a30*a20*a11*a0=0 我們可以將式（1.1.3）表示成如下的矩陣形式 a6 a5 1 1 1 0 1 0 0 a4 0 1 1 0 1 0 1 0 a3 = 0 （1.1.4） 1 0 1

9、1 0 0 1 a2 0 a1 a0 式（1.1.4）還可以簡記為 H*AT=0T 或 A*HT=0 （1.1.5） 其中1 1 1 0 1 0 0 H= 1 1 0 1 0 1 0 A= a6a5a4a3a2a1a0 0= 000 1 0 1 1 0 0 1上角“T”表示將矩陣轉(zhuǎn)置。例如HT是H的轉(zhuǎn)置，即HT的第一行為H的第一列，第二行為第二列。 我們將H稱為監(jiān)督矩陣(paritycheck matrix).只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關系就完全確定了。由（1.1.4）和(1.1.5)都可以看出，H的行數(shù)就是監(jiān)督關系式的數(shù)目r，H的每一行中的“1”的位置表示相應碼元之間存在的監(jiān)

10、督關系。式（1.1.4）中的H矩陣可以分為兩部分。 1 1 1 0 1 0 0 H= 1 1 0 1 0 1 0 = PIr (1.1.6) 1 0 1 1 0 0 1式中：P為r*k階矩陣；Ir為r*r階單位方陣。3. 生成矩陣 由代數(shù)理論可知，H矩陣的的各行應該是線性無關的，否則將得不到r個線性無關的監(jiān)督關系式，從而也得不到r個獨立的監(jiān)督位。若一矩陣可以寫成PIr的矩陣形式，則其各行一定是線性無關的。因為容易驗證Ir的各行是線性無關的，故PIr的各行也是線性無關的。 類似于（1.1.1）改成（1.1.4）那樣，（1.1.2）可以改寫成 a6a2 1 1 1 0 a5 a1 = 1 1 0

11、1 a4 （1.1.7） a0 1 0 1 1 a3或者 1 1 1 a2a1a0 = a6a5a4a3 1 1 0 = a6a5a4a3 Q (1.1.8) 1 0 10 1 1其中，Q為一個k*r階矩陣，它為P的轉(zhuǎn)置，即 Q=PT式（1.1.8）表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督位。我們將Q的左邊加上一個k*k階單位方陣，就構(gòu)成一個矩陣G 1 0 0 0 1 1 1 G= IKQ = 0 1 0 0 1 1 0 (1.1.9) 0 0 1 0 1 0 1 0 0 0 1 0 1 1G稱為生成矩陣（generator matrix），因為由它可產(chǎn)生整個碼組，即有 a6

12、a5a4a3a2a1a0 = a6a5a4a3 G= A (2.2.0)4.(7,4)漢明碼的編碼就是將輸入的四位信息碼編成七位的漢明碼，即加入三位監(jiān)督位。根據(jù)式(2.2.0）A = a6 a5 a4 a3 ·G可知，信息碼與生成矩陣G的乘積就是編好以后的(7,4)漢明碼，而生成矩陣G又是已知的，由式(1.1.9)得1 0 0 0 1 1 1 G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1所以，可以得出如下方程組     a6 = a6         

13、;   a5 = a5            a4 = a4            a3 = a3            (2.2.1)                    a2 = a6 + a5 + a4            a1 = a6 + a5 + a3