海明碼計(jì)算方法

1、海明碼的計(jì)算方法海明碼是一種具有糾錯(cuò)功能的校驗(yàn)碼。本文簡(jiǎn)單地介紹海明碼的計(jì)算方法。 海明碼的目的是能夠糾正一位誤碼。假設(shè)信息碼共有 n 位，海明碼共有 h 位，那么總共的碼長(zhǎng)為 n + h 位。為能檢測(cè)出 n + h 位編碼中其中一位的錯(cuò)誤，海明碼必須能夠表示至少 n + h + 1 種狀態(tài)，其中 n + h 種表示 n + h 位編碼中有一位錯(cuò)誤，另外還需要一種來(lái)表示整個(gè)編碼正確無(wú)誤。則海明碼的長(zhǎng)度需要滿(mǎn)足下列關(guān)系：2 h = n + h + 1于是根據(jù)這個(gè)式子我們可以得出以下的關(guān)系表：h2345678n1245111226275758120121247以 4 位信息位為例，由上表可以看出需

2、要的海明碼長(zhǎng)度為 3。設(shè)信息位為 x4x3x2x1，添加的 3 位海明碼為 a3a2a1，信息碼和海明碼組合之后得到的碼為 H7H6H5H4H3H2H1。錯(cuò)誤無(wú)H1H2H3H4H5H6H7C101010101C1 = H1 + H3 + H5 + H7 = 0C200110011C2 = H2 + H3 + H6 + H7 = 0C300001111C3 = H4 + H5 + H6 + H7 = 0如上表，在H1H7中添加的 3 位海明碼使得 C1C3 的值為零。其中C1C3為校驗(yàn)和。這樣當(dāng) Hn 傳輸出錯(cuò)時(shí)，有 (C3C2C1)2 = n。令 H1 = a1, H2 = a2, H4 =

3、a3, 則得出H7H6H5H4H3H2H1 = x4x3x2a3x1a2a1將上面的關(guān)系代入C1C3的計(jì)算公式，得到C1 = H1 + H3 + H5 + H7 = a1 + x1 + x2 + x4 = 0 C2 = H2 + H3 + H6 + H7 = a2 + x1 + x3 + x4 = 0 C3 = H4 + H5 + H6 + H7 = a3 + x2 + x3 + x4 = 0 即a1 + x1 + x2 + x4 = 0 a2 + x1 + x3 + x4 = 0 a3 + x2 + x3 + x4 = 0 即a3 = x4 + x3 + x2a2 = x4 + x3 + x

4、1a1 = x4 + x2 + x1海明碼1.海明碼的概念海明碼是一種可以糾正一位差錯(cuò)的編碼。它是利用在信息位為k位，增加r位冗余位，構(gòu)成一個(gè)n=k+r位的碼字，然后用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來(lái)區(qū)分無(wú)錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò)。它必需滿(mǎn)足以下關(guān)系式：2r=n+1或2r=k+r+1海明碼的編碼效率為：R=k/(k+r)式中 k為信息位位數(shù)r為增加冗余位位數(shù) 2.海明碼的生成與接收方法一：1)海明碼的生成。例1.已知：信息碼為：0010。海明碼的監(jiān)督關(guān)系式為：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6求：海明碼碼字。解：1)由監(jiān)督關(guān)系式知冗

5、余碼為a2a1a0。2)冗余碼與信息碼合成的海明碼是：0010a2a1a0。設(shè)S2=S1=S0=0,由監(jiān)督關(guān)系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此，海明碼碼字為：00101012)海明碼的接收。例2.已知：海明碼的監(jiān)督關(guān)系式為：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6接收碼字為：0011101(n=7)求：發(fā)送端的信息碼。解：1)由海明碼的監(jiān)督關(guān)系式計(jì)算得S2S1S0=011。2)由監(jiān)督關(guān)系式可構(gòu)造出下面錯(cuò)碼位置關(guān)系表： S2S1S0000001010100011101110111錯(cuò)碼位置無(wú)錯(cuò)a0a1a2a3a4a5a63)由S2S