動機
最小距離告訴我們線性碼中最小的非零重量,卻捨棄了分佈的其餘部分。在誤差分析和結構性問題中,我們往往需要知道每種重量各有多少個碼字。令人驚訝的是,線性碼的完整重量分佈決定了其正交對偶碼的重量分佈。因此,可以轉而枚舉一個小得多的對偶碼並作一次多項式代換,從而研究一個很大的碼。
其機制是一個有限傅立葉(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 ,不能被四整除。它不可能來自二元線性碼。