码-综述（MDS码及Singleton Bound的证明）-526互联

我的研究方向是通信编码理论，上层建筑是分布式存储中的编码方案，所以对于各类码要非常的熟悉，接下来会将一些手记记录下来。

（前置知识：有限域）

（研究的细分领域：信道编码 -》差错控制编码 -》分组码/卷积码 -》分组码 -》 线性分组码 ）

1.码的定义

Fq是一个有限域，F_qⁿ是F_q上的长为n的向量空间，F_qⁿ的一个非空向量子集C称为一个码，C中任意元素称为码字。码C中都是长度为n的向量，码C的码长是n，|C|=K（码字个数是K，在有限域中，绝对值符号代表其域中的元素个数）。

2.码字之间的距离：汉明距离（小写粗体代表向量）

a=(a₁,a₂,...,a_n)，b=(b₁,b₂,...,b_n) ∈ C　　（向量a，向量b，是C中的两个码字）

他们的汉明距离定义为：d_H（a , b）= # {1 ≤ i ≤ n | a_i≠ b_i}　　（a_i与b_i各自分量不同的个数）（满足3条性质：非负性，对称性，三角不等式性）

3.定义：汉明重量

a ∈ F_qⁿ，W_t(a) = d_H（a , 0） = # {1 ≤ i ≤ n | a_i≠ 0}　　（非零分量的个数）

举例：F₃⁴，取a=(1,2,1,0)，W_t(a) = 3　　（因为F的下标是3，意味着其向量的取值为0，1，2）

4.码C的最小距

d(C) = min d_H（x , y） (x ≠ y) (x , y ∈C)

举例：F₃⁴

      { α1= (1,2,1,0) }
C =   { α2= (0,0,1,0) }
      { α3= (1,0,0,2) }

d_H（α₁ , α₂）= 2 ，d_H（α₁ , α₃）= 3 ，d_H（α₂ , α₃）= 3

∴d(C) = 2

5.码C的参数：（n，k，d），性质

（1）可检查 ≤d - 1位错误

（2）可纠正 ≤⌊(d-1)/2⌋位错误

具体说明：

（1）码字a ∈ C ， a出错小于(d-1)位变为a'

　　则有d_H（a , a'）≤ d-1，同时一定有∀b∈C且b≠a，d_H（a , b）≥ d 　　（这块要好好的想一想，因为C内d_min=d，现在存在比d_min还小的码距，说明a'一定发生了错误！！）

　　说明a'不是码字，即a'发生错误。

（2）可以通过“三角不等式”性质证明

6.Singleton Bound（辛格尔顿界）

C ∈ F_qⁿ，C的参数为（n，K，d），将C中的码字写成矩阵形式：

    a11  a12  a13  ...  a1n
    a21  a22  a23  ...  a2n
    a31  a32  a33  ...  a3n
(   ...  ...  ...  ...  ...    )
    ...  ...  ...  ...  ...
    aK1  aK2  aK3  ...  aKn

删去最后（d-1）列，即删去最后（d-1）个分量，得到新的长为（n-d+1）的向量两两不同！

证明（反证法）：

假设a发生错误变为a'，b发生错误变为b'　　（他们都删去d-1个分量）
若dH（a' , b'）= 0　　　　　　　　　　（他们两者的汉明距离一样，即他们两两相同，与定义中的“两两不同”相反）
这时，可以得到dH（a , b）≤ d-1，与dH（a , b）≥ d 相矛盾！！！　　　　（为什么这么说呢，前半句：他们都加上d-1个分量后，理论上最多也就只有d-1个不同的元素，即最小码距=d-1；后半句：最小码距的定义dmin，a与b的码距一定 ≥ C的最小码距）

证毕。

删去最后（d-1）列后得到的新的码字集合定义为C'，|C'| = K，C' ∈ F_q^n-d+1

∴ K ≤ q^n-d+1，即是Singleton Bound

达到Singleton Bound的码称为MDS码。