码的界&MDS码&完备码

目录

• A q ( n , d ) A_q(n,d) Aq​(n,d)
• Singleton 界
• MDS码（极大距离可分码）
• Sphere-Packing 界
• 完备码
• Plotkin 界
• Gilbert-Varshamov 界（下界）

A q ( n , d ) A_q(n,d) Aq​(n,d)

以 A q ( n , d ) A_q(n,d) Aq​(n,d)表示码长为 n n n 、最小汉明距离为 d d d 的 GF( q q q)上码所含的码字的最大个数。

Singleton 界

A q ( n , d ) ⩽ q n − d + 1 A_q(n,d)\leqslant q^{n-d+1} Aq​(n,d)⩽qn−d+1
证明：设 C C C是( n , M , d n,M,d n,M,d)码，则当把这个码中的每个码字的后 d − 1 d-1 d−1个坐标去掉时得到的新的 M M M个码字仍然互不相同，但这些新的码字的长度已变更为 n − d + 1 n-d+1 n−d+1, 因而，

M ⩽ q n − d + 1 M\leqslant q^{n-d+1} M⩽qn−d+1

MDS码（极大距离可分码）

当 Singleton 界达到时，就称 C C C是极大距离可分码，简称 MDS 码。MDS 码对参数的限制很严格，所以，这样的码并不是太多，但无论是在可靠通信的纠错方面，还是在信息安全密码方面，MDS 码都有广泛且重要的应用。

Sphere-Packing 界

A q ( n , d ) ⩽ q n ∑ k = 0 ′ ( n k ) ( q − 1 ) k , t = ⌊ d − 1 2 ⌋ A_{q}\left(n,d\right)\leqslant\frac{q^{n}}{\sum\limits_{k=0}^{\prime}\binom{n}{k}\left(q-1\right)^{k}},\quad t=\left\lfloor\frac{d-1}{2}\right\rfloor Aq​(n,d)⩽k=0∑′​(kn​)(q−1)kqn​,t=⌊2d−1​⌋

证明 考虑以 C = ( n , M , d C=(n,M,d C=(n,M,d )中每个码字为中心、以

t = ⌊ d − 1 2   ⌋ t=\left\lfloor\frac{d-1}{2}\:\right\rfloor t=⌊2d−1​⌋

为半径的那些球之间应该互不相交。否则，假设存在以码字 c 1 c_{1} c1​ 和 c 2 c_{2} c2​ 为中心的两个球有交集，并假定 n n n长的向量 y 同时在这两个球中，则利用汉明距离满足三角不等式这个事实，可以得到：y 到 c 1 c_1 c1​ 和 c 2 c_2 c2​ 的距离之和应大于 c 1 c_1 c1​ 到 c 2 c_2 c2​ 的距离，如果我们用 d ( z 1 , z 2 ) d\left(z_{1},z_{2}\right) d(z1​,z2​)表示两个 n n n长向量 z 1 z_{1} z1​和 z 2 z_{2} z2​的汉明距离，则有

d ⩽ d ( c 1 , c 2 ) ⩽ d ( y , c 1 ) + d ( y , c 2 ) ⩽ 2 t ⩽ d − 1 d\leqslant d(c_1,c_2)\leqslant d(y,c_1)+d(y,c_2)\leqslant2t\leqslant d-1 d⩽d(c1​,c2​)⩽d(y,c1​)+d(y,c2​)⩽2t⩽d−1

这显然是不可能的。既然以 C = ( n , M , d C=(n,M,d C=(n,M,d)中每个码字为中心、以

t = ⌊ d − 1 2   ⌋ t=\left\lfloor\frac{d-1}{2}\:\right\rfloor t=⌊2d−1​⌋

为半径的这些球互不相交， n n n 长向量的总数是 q ′ ′ = ∣ G F ( q ) ′ ′ ∣ q^{\prime\prime}=|GF(q)^{\prime\prime}| q′′=∣GF(q)′′∣,而每个球所含的 n n n 长
向量的个数为

∑ k   =   0 t ( n k )   ( q − 1 ) k \sum\limits_{k\:=\:0}^{t}\binom{n}{k}\:(q-1)^{k} k=0∑t​(kn​)(q−1)k

完备码

达到 Sphere-Packing 界的码被称为完备码。应用极大似然译码方法和完备码传输信息的好处在于接收方无论收到哪一个向量，都可以唯一地译码。目前知道的完备码有以下这些：

( n , M , d ) = ( n , q n , 1 ) ( n, M , d )=( n , q^{n} ,1 ) (n,M,d)=(n,qn,1)
( n , M , d ) = ( n , 1 , 2 t + 1 ) , t 任意 ( n, M, d) = ( n, 1, 2t+ 1), t任意 (n,M,d)=(n,1,2t+1),t任意
( n , M , d ) = ( 2 m + 1 , 2 , 2 m + 1 ) (n,M,d)=(2m+1,2,2m+1) (n,M,d)=(2m+1,2,2m+1)
( n , M , d ) = ( q r − 1 q − 1 , q n − r , 3 ) , r ⩾ 2 (n,M,d)=\left(\frac{q^r-1}{q-1},q^{n-r},3\right),\quad r\geqslant2 (n,M,d)=(q−1qr−1​,qn−r,3),r⩾2

可以注意到，第一类和第二类码分别是全体 n n n长向量和一个 n n n长向量构成的平凡码，第三类码是编码理论中所谓的二元重复码，而第四类码即为著名的汉明(Hamming)线性码类。1967 年，编码学者林特(Lint)利用计算机搜寻了所有参数满足

n ⩽ 1000 , d ⩽ 2001 , q ⩽ 100 n\leqslant1000,\quad d\leqslant2001,\quad q\leqslant100 n⩽1000,d⩽2001,q⩽100

的完备码，除以上所列出的之外，还仅包含下列码：

( n , M , d ) = ( 23 , 2 11 , 7 ) ( n , M , d ) = ( 90 , 2 78 , 5 ) ( n , M , d ) = ( 11 , 3 6 , 5 ) (n,M,d)=(23,2^{11},7)\\(n,M,d)=(90,2^{78},5)\\(n,M,d)=(11,3^{6},5) (n,M,d)=(23,211,7)(n,M,d)=(90,278,5)(n,M,d)=(11,36,5)

由此可以看出，完备码很少，而寻找和构造完备码是编码理论中有意义的研究

课题。

Plotkin 界

设 θ = q − 1 q \theta=\frac{q-1}q θ=qq−1​,如果 d > θ n d>\theta n d>θn ,则

A q ( n , d ) ⩽ d d − θ n A_q(n,d)\leqslant\frac d{d-\theta n} Aq​(n,d)⩽d−θnd​

证明 一方面，令 C C C是( n , M , d n,M,d n,M,d )码，考虑码字之间距离的和，即
S = ∑ c ∈ C ∑ d ∈ C d ( c , d ) S=\sum_{c\in C}\sum_{d\in C}d(c,d) S=c∈C∑​d∈C∑​d(c,d)

于是有

S ⩾ M ( M − 1 ) d S\geqslant M(M-1)d S⩾M(M−1)d

另一方面，假设 C C C 中 所 有 码 字 第 i i i 个 坐 标 中 等 于 j ∈ j\in j∈GF ( q ) = { 0 , . . . , q − 1 } ( q) = \{ 0, . . . , q- 1\} (q)={0,...,q−1}的个数为 k i j k_{ij} kij​,于是，第 i i i 个坐标在S 中所占的份额为
∑ j = 0 q − 1 k i j ( M − k i j ) = M ∑ j = 0 q − 1 k i j − ∑ j = 0 q − 1 k i j 2 = M 2 − ∑ j = 0 q − 1 k i j 2 ⩽ M 2 − M 2 q ( 因为  k i j = M q  时, ∑ j = 0 q − 1 k i j 2  达到最小 ) = θ M 2 \begin{aligned}\sum_{j=0}^{q-1}k_{ij}\left(M-k_{ij}\right)&=M\sum_{j=0}^{q-1}k_{ij}-\sum_{j=0}^{q-1}k_{ij}^{2}=M^{2}-\sum_{j=0}^{q-1}k_{ij}^{2}\\&\leqslant M^2-\frac{M^2}q\quad\left(\text{因为 }k_{ij}=\frac Mq\text{ 时,}\sum_{j=0}^{q-1}k_{ij}^2\text{ 达到最小}\right)\\&=\theta M^2\end{aligned} j=0∑q−1​kij​(M−kij​)​=Mj=0∑q−1​kij​−j=0∑q−1​kij2​=M2−j=0∑q−1​kij2​⩽M2−qM2​(因为 kij​=qM​ 时,j=0∑q−1​kij2​ 达到最小)=θM2​

对 n n n个坐标累加便得：

M ( M − 1 ) d ⩽ S ⩽ θ M 2 n M(M-1)d\leqslant S\leqslant\theta M^2n M(M−1)d⩽S⩽θM2n

上式进一步整理并解出 M M M即得结论。

上面是 A q ( n . d ) A_q(n.d ) Aq​(n.d)的几个上界，下面再介绍 A q ( n . d ) A_q(n.d ) Aq​(n.d)的一个下界

Gilbert-Varshamov 界（下界）

A q ( n , d ) ⩾ q n ∑ i = 0 d − 1 ( n i ) ( q − 1 ) i A_q(n,d)\geqslant\frac{q^n}{\sum_{i=0}^{d-1}\binom{n}{i}\left(q-1\right)^i} Aq​(n,d)⩾∑i=0d−1​(in​)(q−1)iqn​

证明 设 M = A q ( n , d ) M=A_q(n,d) M=Aq​(n,d),则码 C = ( n , M , d ) C=(n,M,d) C=(n,M,d)应具备下列性质：任意一个 n n n 长向量 y ∈ y\in y∈GF ( q ) n \ C ( q) ^n\backslash C (q)n\C,必存在一个码字 c ∈ C c\in C c∈C,使得 c c c 与 y y y 的汉明距离 d ( c , y ) ⩽ d − 1 ; d(c,y)\leqslant d-1; d(c,y)⩽d−1;否则，就可把 y 添加到 C C C中得到一个含 M + 1 M+1 M+1个码字的码，其最小距离也是 d d d,这与 M M M 的最大性矛盾。这样，以 C C C中每个码字为中心、以 d − 1 d-1 d−1为半径的那些球的并集应该正好等于所有 n n n长向量的集合 GF( q q q)”。既然以每个码字为中心，以 d − 1 d-1 d−1为半径的球含有

∑ i   =   0 d − 1 ( n i )   ( q − 1 ) i \sum_{i\:=\:0}^{d-1}\binom{n}{i}\:(q-1)^i i=0∑d−1​(in​)(q−1)i

个 n n n长向量，则应有

A q ( n , d ) [ ∑ i = 0 d − 1 ( n i ) ( q − 1 ) i ] = M [ ∑ i = 0 d − 1 ( n i ) ( q − 1 ) i ] ⩾ q n A_q\left(n,d\right)\left[\sum_{i=0}^{d-1}\binom{n}{i}\left(q-1\right)^i\right]=M\left[\sum_{i=0}^{d-1}\binom{n}{i}\left(q-1\right)^i\right]\geqslant q^n Aq​(n,d)[i=0∑d−1​(in​)(q−1)i]=M[i=0∑d−1​(in​)(q−1)i]⩾qn

即结论成立。