矩陣分析在漢明碼中的應(yīng)用

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

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

3、全為0且互不相同的所有二進(jìn)制m(m2的正整數(shù))重組成，則由此H矩陣得到的線性分組碼稱為2m-1,2m-1-m，3漢明碼。1.2 漢明碼的構(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=2m-1。2)由上面分析，我們可以知道：m 即是漢明碼監(jiān)督位的位數(shù)。故一個(gè)漢明碼中，信息位的位數(shù)k=nm=2m-1-m3)漢明碼的距離為3，因此可以糾正1位錯(cuò)誤，檢出2位錯(cuò)誤。1.3 漢明碼編碼的主要算法漢明碼的編碼就是如何根據(jù)信息位數(shù)k，

4、求出糾正一個(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)督矩陣H；4)用3步的H形成HCT =0，從而得出m個(gè)監(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及編碼所對(duì)應(yīng)的碼字為C=。對(duì)于碼組長(zhǎng)度為n、信息碼元為k位、監(jiān)督碼元為rnk位的分組碼，常記作（n，k）碼，如果滿足2r1n，則有可能構(gòu)造出糾正一位或一位以上錯(cuò)誤的線性碼。下面我們通過(guò)（7，4）漢明碼的例子來(lái)說(shuō)明如何具體構(gòu)造這種碼。設(shè)分組碼（n，k）中，k = 4，為能糾正一位誤碼，要求r3?，F(xiàn)取r3，則nkr7。我們用a0ala2a3a4a5a6表示這7個(gè)碼元，用S1、S2、S3表示由三個(gè)監(jiān)督方程式計(jì)算得到的校正子，并假設(shè)三位S1、S2、S3校正子碼組與誤碼位置的對(duì)應(yīng)關(guān)系如表1所示。S1S2S3錯(cuò)碼位置S1S2S3 錯(cuò)碼位置 001 a0 10

6、1 a4 010 al 110 a5 100 a2 111 a6 011 a3 000 無(wú)錯(cuò)碼 表1 校正子和錯(cuò)碼位置關(guān)系由表可知，當(dāng)誤碼位置在a2、a4、a5、a6時(shí)，校正子S11；否則S10。因此有S1a6a5a4a2，同理有S2a6a5a3a1和S3a6a4a3a0。在編碼時(shí)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個(gè)許用碼組。在接收

7、端收到每個(gè)碼組后，計(jì)算出S1、S2、S3，如果不全為0，則表示存在錯(cuò)誤，可以由表1確定錯(cuò)誤位置并予以糾正。舉個(gè)例子，假設(shè)收到碼組為，可算出S1S2S3=011,由表1可知在a3上有一誤碼。通過(guò)觀察可以看出，上述（7，4）碼的最小碼距為dmin3，糾正一個(gè)誤碼或檢測(cè)兩個(gè)誤碼。如果超出糾錯(cuò)能力則反而會(huì)因“亂糾”出現(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)督矩陣 上面有提到過(guò)，線性碼是指信息位和監(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）還可以簡(jiǎn)記為 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給定，編碼時(shí)監(jiān)督位和信息位的關(guān)系就完全確定了。由（1.1.4）和(1.1.5)都可以看出，H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目r，H的每一行中的“1”的位置表示相應(yīng)碼元之間存在的監(jiān)

10、督關(guān)系。式（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矩陣的的各行應(yīng)該是線性無(wú)關(guān)的，否則將得不到r個(gè)線性無(wú)關(guān)的監(jiān)督關(guān)系式，從而也得不到r個(gè)獨(dú)立的監(jiān)督位。若一矩陣可以寫成PIr的矩陣形式，則其各行一定是線性無(wú)關(guān)的。因?yàn)槿菀昨?yàn)證Ir的各行是線性無(wú)關(guān)的，故PIr的各行也是線性無(wú)關(guān)的。 類似于（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為一個(gè)k*r階矩陣，它為P的轉(zhuǎn)置，即 Q=PT式（1.1.8）表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督位。我們將Q的左邊加上一個(gè)k*k階單位方陣，就構(gòu)成一個(gè)矩陣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），因?yàn)橛伤僧a(chǎn)生整個(gè)碼組，即有 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