線性分組碼
線性分組碼，有兩個(gè)特點(diǎn)，一個(gè)是線性，一個(gè)是分組。線性是指校驗(yàn)位和數(shù)據(jù)位成線性關(guān)系，可以通過線性方程直接求得。分組是指校驗(yàn)位由當(dāng)前碼組的數(shù)據(jù)位唯一確定。比如（n，k）線性分組碼，指碼長為n，數(shù)據(jù)位為k的編碼方案。漢明碼是線性分組碼中的一種。
- 發(fā)送方生成碼組
- 接收方破譯碼組
- 生成矩陣和校驗(yàn)矩陣
- 碼組形式：k bit數(shù)據(jù)位+r bit校驗(yàn)位，這樣的碼被稱為系統(tǒng)碼。
- 重點(diǎn)在第三部分生成矩陣和校驗(yàn)矩陣。
- 我這里說的數(shù)據(jù)位，也被稱為信息位。
（1）發(fā)送方生成碼組
n=k+r。數(shù)據(jù)位為k位，冗余的校驗(yàn)位為r位。滿足 2 r ≥ k + r + 1 \Large 2^r \ge k+r+1 2r≥k+r+1。
用k bit數(shù)據(jù)組成的行向量矩陣m乘以生成矩陣G，即得碼組c。 c 1 × n = m 1 × k × G k × n c_{1\times n} = m_{1\times k}\times G_{k\times n} c1×n?=m1×k?×Gk×n?
（2）接收方破譯碼組
將接受到的碼組c和校驗(yàn)矩陣H相乘，如果得到0向量，則說明收到的是正確的。
或者，將所有錯(cuò)誤情況列舉出來查表。
（3）生成矩陣和校驗(yàn)矩陣
一般教科書里面會(huì)先講校驗(yàn)矩陣，再講生成矩陣，我也準(zhǔn)備這樣寫，但為什么這樣寫呢？
這要從信道編碼出現(xiàn)的原因講起。信源編碼是降冗余，是想要傳輸速率一定的情況下，發(fā)出去更多的符號(hào)；信道編碼是加冗余，是想要在信道干擾條件一定的情況下，送出去更多的可靠的符號(hào)。比如信息位是4位，添加了3位的冗余，那么攜帶信息的碼字有16種，而7比特總共有128種碼字。這多出來的的就是112種，就是被禁用的。
而在這128種情況里面，一定有和16種攜帶信息的向量正交的。我們選出三種線性無關(guān)的禁用碼字，用來當(dāng)作校驗(yàn)矩陣。從定義都可以知道，校驗(yàn)矩陣和許用碼字的矩陣相乘的結(jié)果是一個(gè)零向量。那么我們就可以用這個(gè)來進(jìn)行校驗(yàn)。
由線性代數(shù)的知識(shí)，我們對(duì)校驗(yàn)矩陣進(jìn)行行初等變換，其校驗(yàn)結(jié)果是不變的。那么我們就可以把校驗(yàn)矩陣變換成特殊形式，然后就可以輕松降校驗(yàn)矩陣轉(zhuǎn)換為生成矩陣。用生成矩陣生成的碼字就可以用校驗(yàn)矩陣進(jìn)行校驗(yàn)了。
上面的理論顯然是非常抽象且枯燥的，現(xiàn)在我舉一個(gè)例子，（7，4）漢明碼。
-
校驗(yàn)矩陣：它的特點(diǎn)是，從左到右分別是1～7的二進(jìn)制表示。
H = [ 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 ] H = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix} H=???001?010?011?100?101?110?111????
-
對(duì)上述校驗(yàn)矩陣進(jìn)行行初等變換，將靠右的部分變?yōu)閱挝魂嚒?/p>
H = [ 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 ] = [ P , I r × r ] H = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1\end{bmatrix} = [P,I_{r\times r}] H=???011?101?110?111?100?010?001????=[P,Ir×r?]
-
然后得到生成矩陣，生成系統(tǒng)碼形式的漢明碼的生成矩陣
G = [ I k × k ; P T ] = [ 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 ] G = [I_{k\times k};P^T] = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{bmatrix} G=[Ik×k?;PT]=?????1000?0100?0010?0001?0111?1011?1101??????
- 生成漢明碼： m = [ 1 , 0 , 1 , 0 ] ; c = m G = [ 1 , 0 , 1 , 0 , 1 , 0 , 1 ] m = [1,0,1,0] ;c = mG = [1,0,1,0,1,0,1] m=[1,0,1,0];c=mG=[1,0,1,0,1,0,1]
- 校驗(yàn)：$s = Hc^T = [0;0;0] $
s被稱為伴隨式。
變換前后的最小漢明距離不變。文章來源：http://www.zghlxwxcb.cn/news/detail-478994.html
貼一段我用來測試上述過程的代碼。文章來源地址http://www.zghlxwxcb.cn/news/detail-478994.html
import numpy as np
import itertools as it
G = np.array([[1,0,0,0,0,1,1],
[0,1,0,0,1,0,1],
[0,0,1,0,1,1,0],
[0,0,0,1,1,1,1]])
H = np.array([[0,1,1,1,1,0,0],
[1,0,1,1,0,1,0],
[1,1,0,1,0,0,1]])
s = list(it.product(range(2), repeat=4))
M = np.array(s)
C = np.matmul(M,G)%2
D = []
for c in C:
tmp = []
for other_c in C:
if (c!=other_c).any():
tmp.append(sum((c+other_c)%2))
D.append(np.min(tmp))
print("最小漢明距離:",np.min(D))
到了這里，關(guān)于【通信原理】信道編碼——線性分組碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
