动机
最小距离告诉我们线性码中最小的非零重量,却丢弃了分布的其余部分。在误差分析和结构性问题中,我们往往需要知道每种重量各有多少个码字。令人惊讶的是,线性码的完整重量分布决定了其正交对偶码的重量分布。因此,可以转而枚举一个小得多的对偶码并作一次多项式代换,从而研究一个很大的码。
其机制是一个有限傅里叶(Fourier)计算。对群上的非平凡特征标求和会产生抵消;对平凡特征标求和则得到群的阶。我们将显式地构造所需的特征标,并证明它的零化子正是通常取值于域的对偶。最后这一点依赖于在整个域上的线性性,而不仅仅是对加法封闭。
思想史
分布决定其对偶分布 MacWilliams 1963 年 1 月的论文 指出,有限域线性码的重量分布决定其正交对偶码的分布。
定义
设 C ≤ F q n C\le F_q^n C ≤ F q n 为 F q F_q F q -线性码。它的 Euclid 对偶为
C ⊥ = { y ∈ F q n : c ⋅ y = 0 对每个 c ∈ C } , c ⋅ y = ∑ j = 1 n c j y j . C^\perp=\{y\in F_q^n:c\cdot y=0\text{ 对每个 }c\in C\},\qquad
c\cdot y=\sum_{j=1}^n c_jy_j. C ⊥ = { y ∈ F q n : c ⋅ y = 0 对每个 c ∈ C } , c ⋅ y = j = 1 ∑ n c j y j . 设 A i A_i A i 为汉明(Hamming)重量等于 i i i 的码字个数。齐次重量枚举多项式为
W C ( X , Y ) = ∑ c ∈ C X n − wt ( c ) Y wt ( c ) = ∑ i = 0 n A i X n − i Y i . W_C(X,Y)=\sum_{c\in C}X^{n-\operatorname{wt}(c)}Y^{\operatorname{wt}(c)}
=\sum_{i=0}^n A_iX^{n-i}Y^i. W C ( X , Y ) = c ∈ C ∑ X n − wt ( c ) Y wt ( c ) = i = 0 ∑ n A i X n − i Y i . 因此 A 0 = 1 A_0=1 A 0 = 1 ,每个 A i A_i A i 都是非负整数,且 W C ( 1 , 1 ) = ∣ C ∣ W_C(1,1)=|C| W C ( 1 , 1 ) = ∣ C ∣ 。把对偶码的计数记为 B j B_j B j 。重量枚举多项式不记录任何坐标位置;它所含的信息少于码本身,也少于支撑集的完整列表。
定义 1.4.2
(F q F_q F q 的加法特征标)
记 q = p s q=p^s q = p s 。利用给定的多项式基 1 , θ , … , θ s − 1 1,\theta,\ldots,\theta^{s-1} 1 , θ , … , θ s − 1 ,令 λ : F q → F p \lambda:F_q\to F_p λ : F q → F p 取 1 1 1 的系数。定义取复值的加法特征标
χ ( a ) = exp ( 2 π i λ ( a ) / p ) . \chi(a)=\exp(2\pi i\lambda(a)/p). χ ( a ) = exp ( 2 π iλ ( a ) / p ) . 这里 λ ( a ) \lambda(a) λ ( a ) 用其整数剩余类代表元表示。由可加性得 χ ( a + b ) = χ ( a ) χ ( b ) \chi(a+b)=\chi(a)\chi(b) χ ( a + b ) = χ ( a ) χ ( b ) ,并且 χ ( 1 ) ≠ 1 \chi(1)\ne1 χ ( 1 ) = 1 。复数只是证明的工具;最终的系数公式是精确的整数计算。
定理/命题
定理 1.4.3
(MacWilliams 恒等式)
对每个 F q F_q F q -线性码,
W C ⊥ ( X , Y ) = 1 ∣ C ∣ W C ( X + ( q − 1 ) Y , X − Y ) . W_{C^\perp}(X,Y)=\frac1{|C|}W_C\bigl(X+(q-1)Y,X-Y\bigr). W C ⊥ ( X , Y ) = ∣ C ∣ 1 W C ( X + ( q − 1 ) Y , X − Y ) . 特别地,∣ C ⊥ ∣ = q n / ∣ C ∣ |C^\perp|=q^n/|C| ∣ C ⊥ ∣ = q n /∣ C ∣ 。再施行一次该变换即恢复 W C W_C W C 。
约定二项式系数超出通常范围时取为零,定义
K j ( i ) = ∑ r = 0 j ( − 1 ) r ( q − 1 ) j − r ( i r ) ( n − i j − r ) . K_j(i)=\sum_{r=0}^j(-1)^r(q-1)^{j-r}
\binom ir\binom{n-i}{j-r}. K j ( i ) = r = 0 ∑ j ( − 1 ) r ( q − 1 ) j − r ( r i ) ( j − r n − i ) . 则 B j = ∣ C ∣ − 1 ∑ i = 0 n A i K j ( i ) B_j=|C|^{-1}\sum\limits_{i=0}^n A_iK_j(i) B j = ∣ C ∣ − 1 i = 0 ∑ n A i K j ( i ) 。任何被提出的线性码重量分布都必须使这些值全为非负整数。这些条件是必要的;本章并未证明它们对码的存在也是充分的。
概念视角 代数
这一变换在相差一个倍数下是对合 记 T ( X , Y ) = ( X + ( q − 1 ) Y , X − Y ) T(X,Y)=(X+(q-1)Y,\;X-Y) T ( X , Y ) = ( X + ( q − 1 ) Y , X − Y ) 。则 T ( T ( X , Y ) ) = ( q X , q Y ) T(T(X,Y))=(qX,qY) T ( T ( X , Y )) = ( q X , q Y ) ,因此对 n n n 次齐次多项式连续用 T T T 代换两次,相当于乘以 q n q^n q n 。用系数表示,T T T 把 X n − i Y i X^{n-i}Y^i X n − i Y i 映到 ∑ j K j ( i ) X n − j Y j \sum\limits_jK_j(i)X^{n-j}Y^j j ∑ K j ( i ) X n − j Y j ,而矩阵 K = ( K j ( i ) ) K=(K_j(i)) K = ( K j ( i )) 满足 K 2 = q n I K^2=q^nI K 2 = q n I 。由于 ∣ C ∣ ∣ C ⊥ ∣ = q n |C|\,|C^\perp|=q^n ∣ C ∣ ∣ C ⊥ ∣ = q n ,归一化后的变换作用两次就回到 W C W_C W C :取对偶码对应重量分布上一个固定的线性映射,而它在相差因子 q n q^n q n 下是自身的逆。
若 C ⊥ C^\perp C ⊥ 不含重量为一的字,则
∑ i i A i = ∣ C ∣ n ( q − 1 ) q . \sum_i iA_i=|C|\frac{n(q-1)}q. i ∑ i A i = ∣ C ∣ q n ( q − 1 ) . 若它不含重量为一或二的非零字,则还有
∑ i i ( i − 1 ) A i = ∣ C ∣ n ( n − 1 ) ( q − 1 ) 2 q 2 . \sum_i i(i-1)A_i=|C|\frac{n(n-1)(q-1)^2}{q^2}. i ∑ i ( i − 1 ) A i = ∣ C ∣ q 2 n ( n − 1 ) ( q − 1 ) 2 . 第二个断言说的是成对坐标的分布,并不是说随机码字的各个坐标是联合独立的。
证明思路
建立有限正交性
当 z = 0 z=0 z = 0 时,和 ∑ a ∈ F q χ ( a z ) \sum\limits_{a\in F_q}\chi(az) a ∈ F q ∑ χ ( a z ) 等于 q q q 。当 z ≠ 0 z\ne0 z = 0 时,乘以 z z z 是域的一个置换,所以该和等于 S = ∑ a χ ( a ) S=\sum\limits_a\chi(a) S = a ∑ χ ( a ) 。加上 1 1 1 的平移同样是域的置换,由此得 S = χ ( 1 ) S S=\chi(1)S S = χ ( 1 ) S 。由于 χ ( 1 ) ≠ 1 \chi(1)\ne1 χ ( 1 ) = 1 ,必有 S = 0 S=0 S = 0 。
现在固定 y ∈ F q n y\in F_q^n y ∈ F q n ,对 c ∈ C c\in C c ∈ C 求 χ ( c ⋅ y ) \chi(c\cdot y) χ ( c ⋅ y ) 之和。若 y ∈ C ⊥ y\in C^\perp y ∈ C ⊥ ,结果为 ∣ C ∣ |C| ∣ C ∣ 。否则取 c 0 ∈ C c_0\in C c 0 ∈ C 使 z = c 0 ⋅ y ≠ 0 z=c_0\cdot y\ne0 z = c 0 ⋅ y = 0 。因为 C C C 对域线性,所以 z − 1 c 0 ∈ C z^{-1}c_0\in C z − 1 c 0 ∈ C ,且它与 y y y 的点积为一。把和按这个码字平移,和被乘以 χ ( 1 ) ≠ 1 \chi(1)\ne1 χ ( 1 ) = 1 ,所以和为零。这就证明了指示函数恒等式
1 C ⊥ ( y ) = 1 ∣ C ∣ ∑ c ∈ C χ ( c ⋅ y ) . \mathbf1_{C^\perp}(y)=\frac1{|C|}\sum_{c\in C}\chi(c\cdot y). 1 C ⊥ ( y ) = ∣ C ∣ 1 c ∈ C ∑ χ ( c ⋅ y ) .
这个证明也解释了为什么仅仅找到一个非零点积本身并不够:非平凡特征标仍可能在某些非零的扩域元素上取值为一。把该点积缩放为一,用到了线性码的全部假设。
将整体和逐坐标分解
把指示函数恒等式乘以 y y y 的重量单项式,再对所有 y ∈ F q n y\in F_q^n y ∈ F q n 求和。交换有限和是精确的。对固定的 c c c ,各坐标的和是相互独立的乘积。在第 j j j 个坐标处,贡献为
X + Y ∑ a ≠ 0 χ ( c j a ) . X+Y\sum_{a\ne0}\chi(c_ja). X + Y a = 0 ∑ χ ( c j a ) . 若 c j = 0 c_j=0 c j = 0 ,它等于 X + ( q − 1 ) Y X+(q-1)Y X + ( q − 1 ) Y 。若 c j ≠ 0 c_j\ne0 c j = 0 ,由正交性得 ∑ a ≠ 0 χ ( c j a ) = − 1 \sum\limits_{a\ne0}\chi(c_ja)=-1 a = 0 ∑ χ ( c j a ) = − 1 ,所以它等于 X − Y X-Y X − Y 。对各坐标相乘,再对 c c c 求和,即证明了重量变换。
证明透视
抵消完成对偶成员检验 外层的和遍历每个环境空间中的字,但特征标平均在对偶码之外恰好为零,在对偶码之内恰好为一。坐标分解之后,只需知道码字的每个坐标是否为零。因此,尽管忘记了全部支撑位置,只保留重量的多项式仍然含有足以决定对偶重量的信息。
在恒等式中令 X = Y = 1 X=Y=1 X = Y = 1 。只有零码字对 W C ( q , 0 ) W_C(q,0) W C ( q , 0 ) 有贡献,所以结果是 q n / ∣ C ∣ q^n/|C| q n /∣ C ∣ 。对于逆变换,线性代换 T ( X , Y ) = ( X + ( q − 1 ) Y , X − Y ) T(X,Y)=(X+(q-1)Y,X-Y) T ( X , Y ) = ( X + ( q − 1 ) Y , X − Y ) 满足 T 2 ( X , Y ) = ( q X , q Y ) T^2(X,Y)=(qX,qY) T 2 ( X , Y ) = ( q X , q Y ) 。连续施行两次时,齐次性给出因子 q n q^n q n ,它恰好与乘积 ∣ C ∣ ∣ C ⊥ ∣ |C||C^\perp| ∣ C ∣∣ C ⊥ ∣ 相消。这也与初等的向量空间事实 C ⊥ ⊥ = C C^{\perp\perp}=C C ⊥⊥ = C 一致。
提取系数与矩
在 ( X + ( q − 1 ) Y ) n − i ( X − Y ) i (X+(q-1)Y)^{n-i}(X-Y)^i ( X + ( q − 1 ) Y ) n − i ( X − Y ) i 中,要得到 Y j Y^j Y j ,从第二个因子中取 r r r 份、从第一个因子中取 j − r j-r j − r 份。二项式定理恰好给出 K j ( i ) K_j(i) K j ( i ) 。这样无需数值计算特征标就证明了系数公式。当 j = 1 j=1 j = 1 时,它为 K 1 ( i ) = ( q − 1 ) n − q i K_1(i)=(q-1)n-qi K 1 ( i ) = ( q − 1 ) n − q i 。令 B 1 = 0 B_1=0 B 1 = 0 立即得到第一矩。
矩公式也有一个结构性的证明。若 C C C 在某个坐标上的投影为零,则存在支撑在该坐标上的对偶字。否则该投影是到 F q F_q F q 的满线性映射,各纤维大小相等。于是均匀随机选取的码字在该坐标上非零的概率为 ( q − 1 ) / q (q-1)/q ( q − 1 ) / q 。对这些指示函数的期望求和即得第一矩。
若 C C C 在两个不同坐标上的投影是 F q 2 F_q^2 F q 2 的真子空间,则 F q 2 F_q^2 F q 2 上存在非零线性泛函将它零化。该泛函的两个系数给出一个支撑在这一对坐标上的非零对偶字。因此,不存在重量为一和二的对偶字,就使每个成对投影都是满的,同样各纤维大小相等。两个坐标同时非零的概率是 ( q − 1 ) 2 / q 2 (q-1)^2/q^2 ( q − 1 ) 2 / q 2 。由于 wt ( c ) ( wt ( c ) − 1 ) \operatorname{wt}(c)(\operatorname{wt}(c)-1) wt ( c ) ( wt ( c ) − 1 ) 数的是非零坐标的有序相异对,求和即得第二矩。证明中没有用到三元或更高元的投影。
明确该计算能节省什么、不能节省什么
如果输入已经包含 n + 1 n+1 n + 1 个整数计数 A i A_i A i ,那么所有变换后的计数都可以通过有限的二项式和,在关于 n n n 与 log q \log q log q 的多项式时间内算出。这些计数至多有 O ( n log q ) O(n\log q) O ( n log q ) 比特,相关的二项式系数与幂的贡献在相差可比较的多项式因子的意义下也是如此。只需精确的整数加法、乘法与除法。出现负数或非整数的结果,就推翻了被提出的重量谱。
这并不是一个由生成矩阵求出 A i A_i A i 的一般多项式时间方法。用直接方法枚举维数为 k k k 的码仍需遍历 q k q^k q k 个码字。好处在于:当对偶码的维数小得多时,可以改为枚举对偶码,再变换其分布。重量枚举多项式也不能重构码的坐标排布,不能给出高效的译码器,也不能保证每个数值上可行的重量谱都可以实现。
为非零伴随式类保留相位
对给定向量 a a a ,把 y y y 处的对偶指示函数换成 y − a y-a y − a 处的指示函数。同样的证明给出陪集公式
W a + C ⊥ ( X , Y ) = 1 ∣ C ∣ ∑ c ∈ C χ ( − c ⋅ a ) ( X + ( q − 1 ) Y ) n − wt ( c ) ( X − Y ) wt ( c ) . W_{a+C^\perp}(X,Y)=\frac1{|C|}\sum_{c\in C}\chi(-c\cdot a)
\bigl(X+(q-1)Y\bigr)^{n-\operatorname{wt}(c)}(X-Y)^{\operatorname{wt}(c)}. W a + C ⊥ ( X , Y ) = ∣ C ∣ 1 c ∈ C ∑ χ ( − c ⋅ a ) ( X + ( q − 1 ) Y ) n − wt ( c ) ( X − Y ) wt ( c ) .
相位取决于具体码字 c c c 和向量 a a a ,而不只取决于 c c c 的重量。因此我们通常不能把这个表达式换成普通枚举多项式的代换。这一差别对伴随式译码很重要:非零伴随式描述的是可能误差向量的仿射类,而不是线性的零伴随式类。特征标计算仍然有效,但需要这些依赖于坐标的相位。取 a = 0 a=0 a = 0 就去掉了它们,并恢复 MacWilliams 对偶。通过枚举 C C C 来计算全部相位,仍要付出枚举的代价;封闭的代数表达式本身并不提供快速的最大似然译码器。
陪集枚举多项式并不是对 W C W_C W C 作普通代换。取二元重复码 C = { 000 , 111 } C=\{000,111\} C = { 000 , 111 } ,则 C ⊥ C^\perp C ⊥ 是偶重量码;再取 a = 100 a=100 a = 100 。陪集 a + C ⊥ a+C^\perp a + C ⊥ 由奇重量字 100 , 010 , 001 , 111 100,010,001,111 100 , 010 , 001 , 111 组成,枚举多项式为 3 X 2 Y + Y 3 3X^2Y+Y^3 3 X 2 Y + Y 3 。公式确实给出这个结果,因为 111 ⋅ a = 1 111\cdot a=1 111 ⋅ a = 1 带来相位 − 1 -1 − 1 :1 2 ( ( X + Y ) 3 − ( X − Y ) 3 ) = 3 X 2 Y + Y 3 \tfrac12\bigl((X+Y)^3-(X-Y)^3\bigr)=3X^2Y+Y^3 2 1 ( ( X + Y ) 3 − ( X − Y ) 3 ) = 3 X 2 Y + Y 3 。若忽略相位,得到的是 X 3 + 3 X Y 2 X^3+3XY^2 X 3 + 3 X Y 2 ,即 C ⊥ C^\perp C ⊥ 本身的枚举多项式。
来看一个具体的概率应用。设加性误差独立地改变每个坐标:以概率 1 − ε 1-\varepsilon 1 − ε 取零,并以概率 ε / ( q − 1 ) \varepsilon/(q-1) ε / ( q − 1 ) 取每个非零域值,其中 0 ≤ ε ≤ 1 0\le\varepsilon\le1 0 ≤ ε ≤ 1 。发送的码字加上误差仍在 C C C 中,当且仅当误差属于 C C C 。因此,出现非零不可检出误差的概率为
W C ( 1 − ε , ε q − 1 ) − ( 1 − ε ) n . W_C\left(1-\varepsilon,\frac{\varepsilon}{q-1}\right)-(1-\varepsilon)^n. W C ( 1 − ε , q − 1 ε ) − ( 1 − ε ) n .
减去的一项去掉了零误差,它通过每个校验,但不是误差事件。该公式显式地使用了独立对称误差律。对于相关信道或各符号误差概率不等的情形,仅凭重量未必能决定误差概率;支撑集和实际的非零符号都可能起作用。
例题详解
对二元长度为三的重复码,W C = X 3 + Y 3 W_C=X^3+Y^3 W C = X 3 + Y 3 且 ∣ C ∣ = 2 |C|=2 ∣ C ∣ = 2 。变换给出 ( ( X + Y ) 3 + ( X − Y ) 3 ) / 2 = X 3 + 3 X Y 2 ((X+Y)^3+(X-Y)^3)/2=X^3+3XY^2 (( X + Y ) 3 + ( X − Y ) 3 ) /2 = X 3 + 3 X Y 2 。这就是偶校验对偶码:零字加上三个重量为二的字。它的第一矩为六,与 4 ⋅ 3 / 2 4\cdot3/2 4 ⋅ 3/2 一致。它的对偶码是重复码,其非零重量为三,所以成对公式也给出第二阶乘矩 4 ⋅ 3 ⋅ 2 / 4 = 6 4\cdot3\cdot2/4=6 4 ⋅ 3 ⋅ 2/4 = 6 。
例题 1.4.7
(由小的对偶码恢复 Hamming 码的分布)
长度为七的 Hamming 码的二元单纯形对偶码的枚举多项式为 X 7 + 7 X 3 Y 4 X^7+7X^3Y^4 X 7 + 7 X 3 Y 4 :单纯形码的每个非零字重量都是四。对这个含八个字的码作变换,得
1 8 ( ( X + Y ) 7 + 7 ( X + Y ) 3 ( X − Y ) 4 ) = X 7 + 7 X 4 Y 3 + 7 X 3 Y 4 + Y 7 . \frac18\bigl((X+Y)^7+7(X+Y)^3(X-Y)^4\bigr)
=X^7+7X^4Y^3+7X^3Y^4+Y^7. 8 1 ( ( X + Y ) 7 + 7 ( X + Y ) 3 ( X − Y ) 4 ) = X 7 + 7 X 4 Y 3 + 7 X 3 Y 4 + Y 7 . 因此含十六个字的 Hamming 码,除零字外,有七个重量为三的字、七个重量为四的字和一个重量为七的字。最小的非零重量为三,第一重量和为 21 + 28 + 7 = 56 = 16 ⋅ 7 / 2 21+28+7=56=16\cdot7/2 21 + 28 + 7 = 56 = 16 ⋅ 7/2 。
对 C = { ( a , a ) : a ∈ F q } C=\{(a,a):a\in F_q\} C = {( a , a ) : a ∈ F q } ,其对偶码为 { ( b , − b ) : b ∈ F q } \{(b,-b):b\in F_q\} {( b , − b ) : b ∈ F q } 。两者的枚举多项式都是 X 2 + ( q − 1 ) Y 2 X^2+(q-1)Y^2 X 2 + ( q − 1 ) Y 2 。确实有
1 q ( ( X + ( q − 1 ) Y ) 2 + ( q − 1 ) ( X − Y ) 2 ) = X 2 + ( q − 1 ) Y 2 . \frac1q\bigl((X+(q-1)Y)^2+(q-1)(X-Y)^2\bigr)=X^2+(q-1)Y^2. q 1 ( ( X + ( q − 1 ) Y ) 2 + ( q − 1 ) ( X − Y ) 2 ) = X 2 + ( q − 1 ) Y 2 . 交叉项相消。这个计算使用的是 Euclid 对偶,在特征为二的情形同样成立,此时两种坐标描述恰好重合。
例如,在上述对称二元误差律下,长度为三的重复码的非零不可检出误差概率为 ε 3 \varepsilon^3 ε 3 ,而它的偶校验对偶码的概率为 3 ε 2 ( 1 − ε ) 3\varepsilon^2(1-\varepsilon) 3 ε 2 ( 1 − ε ) 。这说明了为什么了解整个重量谱比只了解最小距离能支持更精细的误差计算。
常见错误
反例模式
加法子群并不足够 设 F 4 = F 2 ( θ ) F_4=F_2(\theta) F 4 = F 2 ( θ ) ,θ 2 = θ + 1 \theta^2=\theta+1 θ 2 = θ + 1 ,并取长度为一的加法子群 C = { 0 , 1 } C=\{0,1\} C = { 0 , 1 } 。它不是 F 4 F_4 F 4 -线性的。它取值于域的 Euclid 零化子只有零。但对上面取常数项系数的特征标,χ ( θ ) = 1 \chi(\theta)=1 χ ( θ ) = 1 ,所以在 y = θ y=\theta y = θ 处对 C C C 取平均得到的是一而不是零。指示函数的证明恰好在此失效,因为把码字乘以 θ − 1 \theta^{-1} θ − 1 后不一定仍在 C C C 中。一般的加性码对偶需要相应的特征标配对,不能悄悄地使用本文的域线性定理。
一个看似合理的整数重量谱也可能通不过变换。对一个假设的二元长度为六、维数为三的码,试取 A 0 = 1 , A 2 = 7 A_0=1,A_2=7 A 0 = 1 , A 2 = 7 ,其余计数全为零。这些是总和为八的非负整数,且环境空间中重量为二的字也足够多。然而预测的对偶重量为一的字的个数是 ( 6 + 7 ⋅ 2 ) / 8 = 5 / 2 (6+7\cdot2)/8=5/2 ( 6 + 7 ⋅ 2 ) /8 = 5/2 ,这是不可能的。基本的基数与重量范围检查没有发现这一矛盾。
练习
快速检查
(计算零码和整个空间 F q n F_q^n F q n 的变换。)
解答 · 答案 零码的 W = X n W=X^n W = X n ,其变换为 ( X + ( q − 1 ) Y ) n (X+(q-1)Y)^n ( X + ( q − 1 ) Y ) n ,即整个空间的枚举多项式。整个空间的大小为 q n q^n q n ,其枚举多项式即后者;对其作线性代换后,所得的线性式为 q X qX q X ,于是 q − n ( q X ) n = X n q^{-n}(qX)^n=X^n q − n ( q X ) n = X n ,符合要求。
快速检查
(直接由系数公式推导 K 1 ( i ) K_1(i) K 1 ( i ) ,并在 B 1 = 0 B_1=0 B 1 = 0 时恢复第一矩。)
解答 · 答案 r = 0 r=0 r = 0 项为 ( q − 1 ) ( n − i ) (q-1)(n-i) ( q − 1 ) ( n − i ) ,r = 1 r=1 r = 1 项为 − i -i − i ,相加得 ( q − 1 ) n − q i (q-1)n-qi ( q − 1 ) n − q i 。由于 ∑ i A i = ∣ C ∣ \sum\limits_iA_i=|C| i ∑ A i = ∣ C ∣ ,等式 0 = B 1 0=B_1 0 = B 1 整理后即为所述的第一矩。
快速检查
(证明自对偶的域线性码长度必为偶数,维数为 n / 2 n/2 n /2 。写出由此得到的枚举多项式恒等式。)
解答 · 答案 大小恒等式给出 ∣ C ∣ 2 = q n |C|^2=q^n ∣ C ∣ 2 = q n 。记 ∣ C ∣ = q k |C|=q^k ∣ C ∣ = q k ,得 2 k = n 2k=n 2 k = n 。枚举多项式必须满足 W C ( X , Y ) = q − n / 2 W C ( X + ( q − 1 ) Y , X − Y ) W_C(X,Y)=q^{-n/2}W_C(X+(q-1)Y,X-Y) W C ( X , Y ) = q − n /2 W C ( X + ( q − 1 ) Y , X − Y ) 。这是必要条件,并未对自对偶码分类,也没有证明它们对每个偶数长度和每个域都存在。
快速检查
(对二元长度为三的偶校验码,显式说明两两独立的坐标不必是联合独立的。)
解答 · 答案 四个字是 000 , 011 , 101 , 110 000,011,101,110 000 , 011 , 101 , 110 。任取一对坐标,四个二元取值各出现一次,所以是均匀的。但第三个坐标是前两个坐标之和,111 111 111 的概率为零而不是 1 / 8 1/8 1/8 。因此两两均匀并不蕴含各坐标是完全独立均匀的。
快速检查
(不展开完整的变换,独立地检查为什么那个假设的长度为六的重量谱不满足第一矩的解释。)
解答 · 答案 二元线性码的非零坐标投影是满射,对所有码字的总重量贡献 ∣ C ∣ / 2 = 4 |C|/2=4 ∣ C ∣/2 = 4 。零坐标贡献为零。因此总重量必须等于有效坐标个数的四倍。所提出的总重量是 7 ⋅ 2 = 14 7\cdot2=14 7 ⋅ 2 = 14 ,不能被四整除。它不可能来自二元线性码。