動機
碼除了加法封閉,還可能有其他有用的代數結構。循環碼把合法字循環移位後仍得到合法字。用多項式表示字,可以把移位變為乘法,從而得到具體編碼規則和緊湊的校驗方法。這裏在有限域 F q \mathbb F_q F q 上工作,固定正整數長度 n n n 。
定義
把字 ( c 0 , … , c n − 1 ) (c_0,\ldots,c_{n-1}) ( c 0 , … , c n − 1 ) 與商環 R = F q [ x ] / ( x n − 1 ) R=\mathbb F_q[x]/(x^n-1) R = F q [ x ] / ( x n − 1 ) 中的剩餘類對應,其代表為
c ( x ) = c 0 + c 1 x + ⋯ + c n − 1 x n − 1 . c(x)=c_0+c_1x+\cdots+c_{n-1}x^{n-1}. c ( x ) = c 0 + c 1 x + ⋯ + c n − 1 x n − 1 .
由多項式除法,每個剩餘類有唯一的次數小於 n n n 的代表。在 R R R 中乘以 x x x 會把字變為 ( c n − 1 , c 0 , … , c n − 2 ) (c_{n-1},c_0,\ldots,c_{n-2}) ( c n − 1 , c 0 , … , c n − 2 ) :最高次項由於 x n = 1 x^n=1 x n = 1 而回到開頭。我們固定這一移位方向;反向約定會改變寫出的座標。
循環碼 是在線性子空間 C ≤ F q n C\le\mathbb F_q^n C ≤ F q n 中再要求對該移位封閉的碼。首項係數為一的多項式稱為首一多項式。選首一生成多項式,可避免相差非零純量的歧義。
定理/命題
有限域上長度為 n n n 的每個非零循環碼 C C C 都有唯一的首一最低次數碼字多項式 g g g 。它整除 x n − 1 x^n-1 x n − 1 ,而碼恰由 R R R 中 g g g 的倍數剩餘類組成。
若首一多項式 g g g 整除 x n − 1 x^n-1 x n − 1 且次數為 r r r ,則其循環碼維數為 n − r n-r n − r 。令 h = ( x n − 1 ) / g h=(x^n-1)/g h = ( x n − 1 ) / g ,則剩餘類 c c c 屬於碼當且僅當 c ( x ) h ( x ) ≡ 0 ( m o d x n − 1 ) c(x)h(x)\equiv0\pmod{x^n-1} c ( x ) h ( x ) ≡ 0 ( mod x n − 1 ) 。
概念視角 結構
循環碼構成模多項式的因子格 兩個定理給出長度為 n n n 的循環碼與 x n − 1 x^n-1 x n − 1 的首一因子之間的雙射,其中零碼對應 g = x n − 1 g=x^n-1 g = x n − 1 。這個對應把次序反轉:g g g 的碼包含 g ′ g' g ′ 的碼,當且僅當 g ∣ g ′ g\mid g' g ∣ g ′ 。因此數循環碼就是數因子。在 F 2 \mathbb F_2 F 2 上,
x 7 + 1 = ( x + 1 ) ( x 3 + x + 1 ) ( x 3 + x 2 + 1 ) x^7+1=(x+1)(x^3+x+1)(x^3+x^2+1) x 7 + 1 = ( x + 1 ) ( x 3 + x + 1 ) ( x 3 + x 2 + 1 ) 有三個互異的不可約因子,所以長度為七的二元循環碼恰有 2 3 = 8 2^3=8 2 3 = 8 個。
證明思路
對一次移位和線性組合封閉,說明 C C C 對任意多項式乘法封閉,因此是 R R R 的理想。選最低次數的非零代表 g g g ,乘以純量使它首一。任取碼字代表 c c c ,多項式除法給出 c = a g + b c=ag+b c = a g + b ,其中 deg b < deg g \deg b<\deg g deg b < deg g 。c , a g c,ag c , a g 都代表碼字,所以差 b b b 也代表碼字。最低次數迫使 b = 0 b=0 b = 0 ,因此每個碼字都由 g g g 的倍數表示;反過來所有倍數都屬於 C C C 。
用 g g g 除 x n − 1 x^n-1 x n − 1 :寫成 x n − 1 = a g + b x^n-1=ag+b x n − 1 = a g + b ,且 deg b < deg g \deg b<\deg g deg b < deg g 。在 R R R 中左側為零,故 b b b 代表碼字。它的次數小於 n n n ,所以它就是自己的唯一代表;最低次數迫使 b = 0 b=0 b = 0 ,即 g g g 整除 x n − 1 x^n-1 x n − 1 。若另有首一最低次數多項式生成同一碼,兩者互相整除,次數相同且都首一,因此相等。
證明透視
最低次數與域的假設在哪裏用到 deg g \deg g deg g 的最小性用了兩次,分別針對兩個不同的餘式。第一次除法中,餘式 b b b 是碼字,因為 c c c 與 a g ag a g 都是碼字;第二次中,它是碼字,因為 x n − 1 x^n-1 x n − 1 在 R R R 中為零。兩次都有 deg b < deg g \deg b\lt\deg g deg b < deg g ,所以非零的 b b b 會與 g g g 的選法矛盾。域的假設在兩次除法之前就已用到:要使 g g g 首一,其首項係數必須可逆;而用首一多項式做除法,餘式次數必然較小。理想性質把「對一次移位封閉」變成「對乘以 a a a 封閉」;沒有它,a g ag a g 根本不一定是碼字。排除零碼只因為零碼沒有可供選取 g g g 的非零元素。
設 deg g = r \deg g=r deg g = r 。g , x g , … , x n − r − 1 g g,xg,\ldots,x^{n-r-1}g g , xg , … , x n − r − 1 g 次數互不相同且小於 n n n ,故其剩餘類線性無關。每個碼字是 g g g 的倍數;把乘數模 h = ( x n − 1 ) / g h=(x^n-1)/g h = ( x n − 1 ) / g 約化,就能把它表示成這 n − r n-r n − r 個元素的線性組合。因此它們構成基底。對於校驗,g g g 的倍數與 h h h 相乘後模 x n − 1 x^n-1 x n − 1 為零。反之,若 x n − 1 = g h x^n-1=gh x n − 1 = g h 在多項式環中整除 c h ch c h ,消去非零多項式 h h h 得 g ∣ c g\mid c g ∣ c 。不需要假設 g , h g,h g , h 互質。
零碼是邊界情形:它不含次數小於 n n n 的非零代表。可另外用因子 g = x n − 1 g=x^n-1 g = x n − 1 描述,它在 R R R 中的剩餘類為零,維數為零。整個空間對應 g = 1 g=1 g = 1 。
例題詳解
在 F 2 \mathbb F_2 F 2 上,g = x 3 + x + 1 g=x^3+x+1 g = x 3 + x + 1 整除 x 7 − 1 = x 7 + 1 x^7-1=x^7+1 x 7 − 1 = x 7 + 1 。直接相乘得
( x 3 + x + 1 ) ( x 4 + x 2 + x + 1 ) = x 7 + 1. (x^3+x+1)(x^4+x^2+x+1)=x^7+1. ( x 3 + x + 1 ) ( x 4 + x 2 + x + 1 ) = x 7 + 1. 特徵二下出現兩次的項相消。碼的維數為 7 − 3 = 4 7-3=4 7 − 3 = 4 ,共有 16 個字;校驗多項式為 h = x 4 + x 2 + x + 1 h=x^4+x^2+x+1 h = x 4 + x 2 + x + 1 。
取訊息多項式 a ( x ) = 1 + x 2 a(x)=1+x^2 a ( x ) = 1 + x 2 ,則碼字為
a ( x ) g ( x ) = 1 + x + x 2 + x 5 , a(x)g(x)=1+x+x^2+x^5, a ( x ) g ( x ) = 1 + x + x 2 + x 5 , 座標字是 ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) (1,1,1,0,0,1,0) ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) 。其循環移位為 ( 0 , 1 , 1 , 1 , 0 , 0 , 1 ) (0,1,1,1,0,0,1) ( 0 , 1 , 1 , 1 , 0 , 0 , 1 ) ,由 x a ( x ) g ( x ) x a(x)g(x) x a ( x ) g ( x ) 模 x 7 − 1 x^7-1 x 7 − 1 表示;按構造它屬於碼。此例直到出現 x 7 x^7 x 7 的係數時才需約化。
字 ( 1 , 0 , 0 , 0 , 0 , 0 , 0 ) (1,0,0,0,0,0,0) ( 1 , 0 , 0 , 0 , 0 , 0 , 0 ) 表示 1 1 1 。次數為三的 g g g 不整除 1 1 1 ,所以它不是碼字。等價地,其校驗乘積為 h h h ;h h h 次數為四,小於七,故在 R R R 中非零。
常見錯誤
加法封閉的向量空間不一定對移位封閉:二元長度三的碼 { 000 , 100 } \{000,100\} { 000 , 100 } 是線性的,但移位 100 100 100 得到 010 010 010 ,不在碼中。它的多項式是 0 0 0 與 1 1 1 ,而 x ⋅ 1 = x x\cdot1=x x ⋅ 1 = x 不在其中,所以這個集合不是 R R R 的理想,也沒有生成多項式。
反例模式
不整除模多項式的生成多項式 人們可能以為每個 r r r 次首一多項式 g g g 都生成維數為 n − r n-r n − r 的碼。在 F 2 \mathbb F_2 F 2 上取 n = 3 n=3 n = 3 與 g = x 2 + 1 g=x^2+1 g = x 2 + 1 ,它不整除 x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) x^3+1=(x+1)(x^2+x+1) x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) 。在 R R R 中,它的倍式是 0 0 0 、g = 1 + x 2 g=1+x^2 g = 1 + x 2 、x g ≡ 1 + x xg\equiv1+x xg ≡ 1 + x 以及兩者之和 x + x 2 x+x^2 x + x 2 :共四個字,所以維數是二,而不是 3 − 2 = 1 3-2=1 3 − 2 = 1 。貝祖(Bézout)等式解釋了原因:若 d = gcd ( g , x n − 1 ) = u g + v ( x n − 1 ) d=\gcd(g,x^n-1)=ug+v(x^n-1) d = g cd( g , x n − 1 ) = ug + v ( x n − 1 ) ,則在 R R R 中 d ≡ u g d\equiv ug d ≡ ug ,所以 g g g 與 d d d 生成同一個理想;這裏 d = x + 1 d=x+1 d = x + 1 。修正就是定理的假設:維數公式適用於 x n − 1 x^n-1 x n − 1 的首一因子,而定理中的生成多項式必定是這樣的因子。
乘以 x x x 是在 R R R 中進行的,其中 x n = 1 x^n=1 x n = 1 。未經模 x n − 1 x^n-1 x n − 1 約化的普通乘積次數可能達到 n n n 或以上,便不是長度 n n n 的字。取 n = 7 n=7 n = 7 ,碼字 x 3 g = x 3 + x 4 + x 6 x^3g=x^3+x^4+x^6 x 3 g = x 3 + x 4 + x 6 移位後為 x 4 + x 5 + x 7 ≡ 1 + x 4 + x 5 x^4+x^5+x^7\equiv1+x^4+x^5 x 4 + x 5 + x 7 ≡ 1 + x 4 + x 5 ,寫作 ( 1 , 0 , 0 , 0 , 1 , 1 , 0 ) (1,0,0,0,1,1,0) ( 1 , 0 , 0 , 0 , 1 , 1 , 0 ) 。
校驗多項式不保證糾正任意錯誤,它只用於檢查是否屬於碼。要定位或糾正錯誤,還需要解碼算法和最小距離論證。
總結
商環記錄循環移位。多項式除法給出整除 x n − 1 x^n-1 x n − 1 的唯一首一生成元;它的次數決定維數,互補因子給出成員檢驗。零碼與整個空間按明確約定分別處理。
練習
快速檢查
(在 F 2 \mathbb F_2 F 2 上取 n = 3 n=3 n = 3 、g = x + 1 g=x+1 g = x + 1 。驗證 g ∣ x 3 − 1 g\mid x^3-1 g ∣ x 3 − 1 ,並求碼的維數。)
分解 x 3 + 1 x^3+1 x 3 + 1 ,並使用 dim C = n − deg g \dim C=n-\deg g dim C = n − deg g 。
解答 · 答案 特徵二下 x 3 − 1 = x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) x^3-1=x^3+1=(x+1)(x^2+x+1) x 3 − 1 = x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) 。生成元次數為一,維數為 3 − 1 = 2 3-1=2 3 − 1 = 2 。
快速檢查
(對此長度三的碼,1 + x 1+x 1 + x 和 1 1 1 分別是碼字嗎?)
解答 · 答案 1 + x = g 1+x=g 1 + x = g 是碼字;常數多項式 1 1 1 不被 g g g 整除,因此不是碼字。
用一組基編碼
維數證明給出直接編碼器。令 k = n − r k=n-r k = n − r ,把訊息寫成 a ( x ) = a 0 + ⋯ + a k − 1 x k − 1 a(x)=a_0+\cdots+a_{k-1}x^{k-1} a ( x ) = a 0 + ⋯ + a k − 1 x k − 1 ,輸出 a ( x ) g ( x ) a(x)g(x) a ( x ) g ( x ) 。它的次數至多為 ( k − 1 ) + r = n − 1 (k-1)+r=n-1 ( k − 1 ) + r = n − 1 ,故這個乘積已是長度 n n n 的代表,編碼這一步無需回繞。不同訊息給出不同碼字:若 a g = b g ag=bg a g = b g ,則 ( a − b ) g = 0 (a-b)g=0 ( a − b ) g = 0 ;多項式環沒有零因子,所以 a = b a=b a = b 。
g , x g , … , x k − 1 g g,xg,\ldots,x^{k-1}g g , xg , … , x k − 1 g 的係數向量構成生成矩陣的各行。七位例子按低次在前的約定得到
( 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 ) . \begin{pmatrix}
1&1&0&1&0&0&0\\
0&1&1&0&1&0&0\\
0&0&1&1&0&1&0\\
0&0&0&1&1&0&1
\end{pmatrix}. 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 .
訊息 ( 1 , 0 , 1 , 0 ) (1,0,1,0) ( 1 , 0 , 1 , 0 ) 選擇第一行和第三行,二元和為 ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) (1,1,1,0,0,1,0) ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) ,與多項式計算一致。若採用高次在前的座標,寫出的向量和移位方向會反過來;只要約定始終一致,底層的碼沒有改變。
此編碼器在這些座標中不是系統式的:訊息位沒有原封不動地佔據四個指定位置。下一節用多項式除法構造系統編碼。不同生成矩陣可以生成同一碼,所以看到不同矩陣本身不代表碼不同。
多項式除法與系統編碼
令 r = deg g r=\deg g r = deg g ,訊息 a a a 的次數小於 n − r n-r n − r 。用 g g g 除 x r a x^ra x r a :
x r a = q g + s , deg s < r . x^ra=qg+s,\qquad \deg s<r. x r a = q g + s , deg s < r .
於是 c = x r a − s = q g c=x^ra-s=qg c = x r a − s = q g 是碼字。它在 r , … , n − 1 r,\ldots,n-1 r , … , n − 1 次的係數恰為 a a a 的係數,而前 r r r 個係數來自 − s -s − s :餘式次數小於 r r r ,不會影響較高位置。特徵二下減法與加法相同;一般域上的負號不可省略。
七位二元例子取 a = 1 + x 2 a=1+x^2 a = 1 + x 2 ,則 x 3 a = x 3 + x 5 x^3a=x^3+x^5 x 3 a = x 3 + x 5 。由 x 3 ≡ x + 1 ( m o d g ) x^3\equiv x+1\pmod g x 3 ≡ x + 1 ( mod g ) ,有 x 5 ≡ x 2 ( x + 1 ) = x 3 + x 2 ≡ x 2 + x + 1 x^5\equiv x^2(x+1)=x^3+x^2\equiv x^2+x+1 x 5 ≡ x 2 ( x + 1 ) = x 3 + x 2 ≡ x 2 + x + 1 ,因此 x 3 + x 5 ≡ x 2 ( m o d g ) x^3+x^5\equiv x^2\pmod g x 3 + x 5 ≡ x 2 ( mod g ) 。系統碼字是 x 5 + x 3 + x 2 x^5+x^3+x^2 x 5 + x 3 + x 2 ,座標為 ( 0 , 0 , 1 , 1 , 0 , 1 , 0 ) (0,0,1,1,0,1,0) ( 0 , 0 , 1 , 1 , 0 , 1 , 0 ) ,最後四位 ( 1 , 0 , 1 , 0 ) (1,0,1,0) ( 1 , 0 , 1 , 0 ) 就是訊息。用 g g g 除該碼字恰得 x 2 x^2 x 2 ,獨立驗證它屬於碼。
系統編碼與直接編碼通常把相同訊息映為不同碼字:前者得到 x 2 + x 3 + x 5 x^2+x^3+x^5 x 2 + x 3 + x 5 ,後者得到 1 + x + x 2 + x 5 1+x+x^2+x^5 1 + x + x 2 + x 5 。兩者都屬於同一碼,因為它們都是 g g g 的倍數。因此訊息到碼字的例子必須說明編碼約定。
校驗乘積與伴隨式
記 M = x n − 1 = g h M=x^n-1=gh M = x n − 1 = g h 。收到的多項式 r r r 的校驗乘積為 r h m o d M rh\bmod M r h mod M ;若為零,r r r 是碼字,否則不是。若 r = c + e r=c+e r = c + e 且 c c c 是碼字,則 r h ≡ e h ( m o d M ) rh\equiv eh\pmod M r h ≡ e h ( mod M ) 。這與矩陣伴隨式類似:結果依賴錯誤而不依賴傳送碼字。
另一種常用伴隨式是 r r r 除以 g g g 的餘式。它也恰在碼字上為零,因為成員條件是 g ∣ r g\mid r g ∣ r 。兩種伴隨式的表示不同,不能作為多項式直接等同;它們對成員資格給出等價資訊,且加入碼字後均只依賴錯誤。要解碼,還須規定如何將伴隨式對應到候選錯誤圖樣。若多個錯誤有相同伴隨式,單憑它不能確定實際發生哪個。
對七位碼,單座標錯誤 e = x j e=x^j e = x j 的餘式為 x j m o d g x^j\bmod g x j mod g 。前三個餘式是 1 , x , x 2 1,x,x^2 1 , x , x 2 ;由 x 3 ≡ x + 1 x^3\equiv x+1 x 3 ≡ x + 1 ,第四個是 x + 1 x+1 x + 1 。它們非零且彼此不同。完整的單錯誤解碼表還須檢查七個位置,證明七個餘式均非零且不同;只列出四個不足以得出全部位置的結論。
可選 循環碼的對偶碼也是循環碼嗎? 是的,其生成多項式是倒序後的校驗多項式。
自然延伸的下一個問題
循環碼的對偶碼也是循環碼嗎? 是的,其生成多項式是倒序後的校驗多項式。
設 σ \sigma σ 為移位。若 d d d 與每個碼字正交,則 ⟨ c , σ d ⟩ = ⟨ σ − 1 c , d ⟩ = 0 \langle c,\sigma d\rangle=\langle\sigma^{-1}c,d\rangle=0 ⟨ c , σ d ⟩ = ⟨ σ − 1 c , d ⟩ = 0 ,因為 σ − 1 c ∈ C \sigma^{-1}c\in C σ − 1 c ∈ C ;所以對偶碼是循環碼,並有一個整除 x n − 1 x^n-1 x n − 1 的首一生成多項式。記 k = deg h k=\deg h k = deg h ,這個生成多項式就是倒序多項式 x k h ( x − 1 ) x^kh(x^{-1}) x k h ( x − 1 ) ,再縮放為首一。對長度為七的碼,h = 1 + x + x 2 + x 4 h=1+x+x^2+x^4 h = 1 + x + x 2 + x 4 給出 1 + x 2 + x 3 + x 4 1+x^2+x^3+x^4 1 + x 2 + x 3 + x 4 ,它的八個倍式都與全部十六個碼字正交。
關閉
快速檢查
(二元長度三的碼取 g = x + 1 g=x+1 g = x + 1 ,用 r = 1 r=1 r = 1 為訊息 a = 1 + x a=1+x a = 1 + x 構造系統碼字。)
解答 · 答案 用 x + 1 x+1 x + 1 除 x a = x + x 2 xa=x+x^2 x a = x + x 2 ,恰得 x ( x + 1 ) x(x+1) x ( x + 1 ) ,餘式為零,碼字為 x + x 2 x+x^2 x + x 2 ,座標 ( 0 , 1 , 1 ) (0,1,1) ( 0 , 1 , 1 ) 。最後兩位包含訊息係數 ( 1 , 1 ) (1,1) ( 1 , 1 ) 。
快速檢查
(同一碼收到 r = 1 + x + x 2 r=1+x+x^2 r = 1 + x + x 2 ,用模 g g g 的餘式檢驗。)
解答 · 答案 在二元域上模 x + 1 x+1 x + 1 有 x ≡ 1 x\equiv1 x ≡ 1 ,所以 r ≡ 1 + 1 + 1 = 1 r\equiv1+1+1=1 r ≡ 1 + 1 + 1 = 1 ,非零。接收字不是碼字;此檢驗本身不能指出哪個座標被改變,或是否只發生一次改變。
七位例子的最小距離
繼續使用 x 3 ≡ x + 1 ( m o d g ) x^3\equiv x+1\pmod g x 3 ≡ x + 1 ( mod g ) ,每步乘以 x x x 並約化,得到餘式表:
j 0 1 2 3 4 5 6 x j m o d g 1 x x 2 x + 1 x 2 + x x 2 + x + 1 x 2 + 1 \begin{array}{c|ccccccc}
j&0&1&2&3&4&5&6\\
\hline
x^j\bmod g&1&x&x^2&x+1&x^2+x&x^2+x+1&x^2+1
\end{array} j x j mod g 0 1 1 x 2 x 2 3 x + 1 4 x 2 + x 5 x 2 + x + 1 6 x 2 + 1
對線性碼,兩字的距離等於其差的重量;碼字之差仍為碼字,而每個碼字都可寫成它與零之差。因此最小距離等於非零碼字的最小重量。
它們恰好是次數小於三的七個非零多項式,各出現一次。重量一的碼字將是 x j x^j x j ,但它的餘式非零。重量二的碼字將是不同位置的 x i + x j x^i+x^j x i + x j ;其餘式為零只有在兩項表值相等時才可能,而表中沒有重複。另一方面,g = 1 + x + x 3 g=1+x+x^3 g = 1 + x + x 3 本身是重量為三的碼字,因此最小距離恰為三。
該表現在支持單錯誤糾正:收到多項式的餘式若非零,找到唯一具有相同餘式的 x j x^j x j ,並將它加到接收字上。在至多發生一個錯誤的假設下,這恢復傳送碼字;零餘式在此假設下對應沒有錯誤。若不作此假設,兩個或更多錯誤可能與單錯誤具有相同餘式,過程可能輸出另一合法碼字。
此碼有 16 個字,二元半徑一球各有 1 + 7 = 8 1+7=8 1 + 7 = 8 個字。最小距離三保證這些球互不相交,而 16 ⋅ 8 = 128 = 2 7 16\cdot8=128=2^7 16 ⋅ 8 = 128 = 2 7 ,所以它們恰好劃分整個空間。這是半徑一填充界達到等號的完美碼,並不意味著實際噪聲的重量一定至多為一。
快速檢查
(接收多項式模 g g g 的餘式為 x 2 + x x^2+x x 2 + x ,假設至多一個錯誤,如何解碼?)
解答 · 答案 表中該餘式對應 x 4 x^4 x 4 。把 x 4 x^4 x 4 加到接收多項式後,餘式為零;距離三說明所得碼字是在一次座標改變範圍內的唯一碼字。
快速檢查
(傳送零字時,為甚麼重量三的碼字可以是未被偵測的錯誤?)
解答 · 答案 零加上該碼字仍得到該碼字,它除以 g g g 的餘式為零。接收者看到合法碼字,單憑成員檢驗不會發現錯誤。最小距離定理保證偵測至多兩個錯誤,並不保證偵測每個更高重量錯誤。
檢查假設
係數為域,保證可以用非零多項式做除法,且多項式環沒有零因子。證明用到了這兩個事實:除法產生低次數餘式,消去律證明校驗條件。在一般係數環上這兩步可能失敗,不能直接照搬證明。正長度保證模數 x n − 1 x^n-1 x n − 1 和長度 n n n 的座標約定有意義。
循環移位只是置換座標,因而保持漢明(Hamming)重量。所有移位所得碼字具有相同重量,但這本身不能確定最小距離:還須考慮所有非零線性組合。七位例子用餘式表給出缺少的下界,再用重量三的生成元給出相配的上界。
一個重因子例子具體說明為何不要求 g , h g,h g , h 互質。在 F 2 \mathbb F_2 F 2 上取 n = 2 n=2 n = 2 ,則 x 2 − 1 = ( x + 1 ) 2 x^2-1=(x+1)^2 x 2 − 1 = ( x + 1 ) 2 。取 g = h = x + 1 g=h=x+1 g = h = x + 1 ,於是 gcd ( g , h ) = x + 1 \gcd(g,h)=x+1 g cd( g , h ) = x + 1 。g g g 生成的碼為 { 00 , 11 } \{00,11\} { 00 , 11 } 。校驗恆等式仍成立:在 F 2 [ x ] \mathbb F_2[x] F 2 [ x ] 中消去 h h h ,可知 g h gh g h 整除 c h ch c h 當且僅當 g g g 整除 c c c 。這是在取商之前的多項式環中消去;商環本身可以有零因子。