线性分组码
线性分组码,有两个特点,一个是线性,一个是分组。线性是指校验位和数据位成线性关系,可以通过线性方程直接求得。分组是指校验位由当前码组的数据位唯一确定。比如(n,k)线性分组码,指码长为n,数据位为k的编码方案。汉明码是线性分组码中的一种。
- 发送方生成码组
- 接收方破译码组
- 生成矩阵和校验矩阵
- 码组形式:k bit数据位+r bit校验位,这样的码被称为系统码。
- 重点在第三部分生成矩阵和校验矩阵。
- 我这里说的数据位,也被称为信息位。
(1)发送方生成码组
n=k+r。数据位为k位,冗余的校验位为r位。满足 2 r ≥ k + r + 1 \Large 2^r \ge k+r+1 2r≥k+r+1。
用k bit数据组成的行向量矩阵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和校验矩阵H相乘,如果得到0向量,则说明收到的是正确的。
或者,将所有错误情况列举出来查表。
(3)生成矩阵和校验矩阵
一般教科书里面会先讲校验矩阵,再讲生成矩阵,我也准备这样写,但为什么这样写呢?
这要从信道编码出现的原因讲起。信源编码是降冗余,是想要传输速率一定的情况下,发出去更多的符号;信道编码是加冗余,是想要在信道干扰条件一定的情况下,送出去更多的可靠的符号。比如信息位是4位,添加了3位的冗余,那么携带信息的码字有16种,而7比特总共有128种码字。这多出来的的就是112种,就是被禁用的。
而在这128种情况里面,一定有和16种携带信息的向量正交的。我们选出三种线性无关的禁用码字,用来当作校验矩阵。从定义都可以知道,校验矩阵和许用码字的矩阵相乘的结果是一个零向量。那么我们就可以用这个来进行校验。
由线性代数的知识,我们对校验矩阵进行行初等变换,其校验结果是不变的。那么我们就可以把校验矩阵变换成特殊形式,然后就可以轻松降校验矩阵转换为生成矩阵。用生成矩阵生成的码字就可以用校验矩阵进行校验了。
上面的理论显然是非常抽象且枯燥的,现在我举一个例子,(7,4)汉明码。
-
校验矩阵:它的特点是,从左到右分别是1~7的二进制表示。
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=⎣⎡001010011100101110111⎦⎤
-
对上述校验矩阵进行行初等变换,将靠右的部分变为单位阵。
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=⎣⎡011101110111100010001⎦⎤=[P,Ir×r]
-
然后得到生成矩阵,生成系统码形式的汉明码的生成矩阵
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]=⎣⎢⎢⎡1000010000100001011110111101⎦⎥⎥⎤
- 生成汉明码: 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]
- 校验:$s = Hc^T = [0;0;0] $
s被称为伴随式。
变换前后的最小汉明距离不变。文章来源:https://www.toymoban.com/news/detail-478994.html
贴一段我用来测试上述过程的代码。文章来源地址https://www.toymoban.com/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))
到了这里,关于【通信原理】信道编码——线性分组码的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!