纠错码理论

​ 纠错码一开始应用于数字通信系统，目的是使消息可以在信道中可靠的传输而不产生错误，其通过在消息中增加冗余的方法，排除噪声信道下带来的干扰，从而使接收方能够正确的检测或纠正错误

image-20240407195159132

分类：

  • 线性分组码
  • 线性卷积码
  • 非线性卷积码等

密码学中常用线性分组码

定义1（线性分组码）：

二进制(n, k)线性分组码 C 是 GF(2)上的 n 维线性空间的一个 k 维子空间。n 表示码字的长度，k 表示消息位的长度。

定义2 （生成矩阵，校验矩阵）:

对于(n, k)线性分组码 C，对于(n, k)线性分组码 C，若矩阵G∈F2k×nG \in F_2^{k \times n}满足

C={mG∣m∈F2k}C = \{mG|m \in F_2^k\}

称矩阵G为码C的生成矩阵。

可见，码字空间是矩阵G的行的线性组合张成的子空间，对G做初等变换有G=[IkP]G=[I_kP],IkI_k是k阶的单位阵，P是大小为k×(n−k)k\times (n-k)的矩阵，由该G生成的码称为系统码，且系统码的前k位是信息位，后(n−k)(n-k)位是校验位。

若矩阵H∈F2(n−k)×nH \in F_2^{(n-k)\times n}满足

C={c∈F2n∣HcT=0}C= \{c\in F_2^n|Hc^T=0\}

称矩阵H为码C的校验矩阵

定义3 （校验子）：

设向量c∈F2nc\in F_2^n,校验矩阵H∈F2(n−k)×nH\in F_2^{(n-k)\times n}。若向量s∈F2n−ks\in F_2^{n-k}有

sT=HcT∈F2n−ks^T = Hc^T\in F_2^{n-k}

称s为向量c的校验子。当码字正确是，校验子为0向量。

定义4 （汉明重量）：

设向量c∈F2nc\in F_2^{n},汉明重量指向量中非0元素的个数，记作w(c)w(c)

定义5 （汉明距离）：

设向量a,b∈F2na,b \in F_2^n,汉明距离指对应位置不同元素的个数，记作d(a,b)=w(a−b)d(a,b)=w(a-b)

定义6 （最小距离）：

设线性分段码C，∀c1,c2∈C\forall c_1,c_2\in C且c1≠c2c_1 \neq c_2，最小距离记作dmin=min d(c1,c2)d_{min}= min\ d(c_1,c_2)。其等价于线性分组码C中非零码字的最小汉明重量，即c∈C,c≠0,dmin=min w(c)c\in C,c\neq0,d_{min} = min\ w(c)。

若一个(n,k)线性分组码的最小距离为dmind_{min}，则

  1. 检测出e个随机错误，需满足dmin≥e+1d_{min}\ge e+1

  2. 纠正出t个随机错误，需满足dmin≥2t+1d_{min} \ge 2t +1

  3. 纠正出t个随机错误，且检测出e个随机错误，其中e≥te \ge t，需满足dmin≥e+t+1d_{min} \ge e+t+1

下文将以(n,k,d)表示线性分组码，其中d表示dmind_{min}

定义7 （等价类）：

设(n,k,d)线性分组码C1C_1和C2C_2，置换C1C_1中的n个码元位置并加一个不变的n维向量a后能够得到C2C_2，称C1C_1与C2C_2属于一个等价类。即

C2∈{π(u)+a,u∈C1}C_2 \in \{ \pi(u)+a,u\in C_1\}

对C1C_1和C2C_2而言，判断二者是否为同一等价类等价于寻找k阶满秩方阵S和n阶置换矩阵P，使得C1C_1的生成矩阵G1G_1和C2C_2的生成矩阵G2G_2满足

G1=SG2PG_1 = SG_2P

若满足上式，则代表C1C_1与C2C_2等价。