從多項式到距離保證
循環碼的意義不止於碼字可以輪轉:我們還要知道碼字相距多遠,並利用接收字定位錯誤。本單元證明連續根下界,並完整構造一個小型解碼表。內容以先前距離和伴隨式單元為基礎。
令 為有限域、,以 表示 。座標按常數項在前的次序書寫。 在模 下乘 ,會把最後一個座標移至第一個。對這種位移封閉的線性碼是循環碼:反覆位移及線性組合顯示它是 的理想。
定理 2.1.1
(循環碼的生成多項式與維數)
長度為 、定義在 上的每個循環碼 都有唯一首一生成多項式 ,且 。反過來, 的每個首一因子都生成一個循環碼。若 ,則碼字恰為乘積 (),且每個碼字只有一種寫法,故 。
證明
(最小次數與多項式除法)
考慮 在 的原像,它是包含 的理想。在原像中選次數最小的非零首一多項式 ;多項式除法的餘式若非零,便會屬於該理想且次數更小,故原像每個元素都被 整除,特別地 。若 是另一個同次數的首一元素,則 屬於該理想而次數更小,故 。反過來每個首一因子都生成商環的一個理想。 給出零碼;以下討論距離時假設碼含非零字。
每個 的乘積 次數小於 ,本身就是約簡代表元。反過來,每個碼字都由某個 代表。把 除以次數為 的 :若 且 ,則 。若 ,域上多項式環沒有零因子,故 。因此 構成一組基底。
連續根下界
假設擴域 含有乘法階恰為 的 。因 ,在其各次冪代值與商環代表元無關。我們假設此 存在;特別地,其階與域的特徵互質。令 為整數且 。
定理 2.1.2
(連續根距離下界)
若每個碼字均滿足 ,則每個非零碼字的 Hamming 重量至少為 ,故 。
證明
(位置太少的 Vandermonde 方程組)
若非零碼字只有 個非零係數,位置為互異的 ,令 。因 且 的階為 ,這些值互異且非零。頭 個根方程給出
係數矩陣為 Vandermonde 矩陣,行列式 。故每個 均為零,與非零係數的選擇矛盾。所得只是下界,不自動保證等號;要得確切距離,還須展示達到下界的碼字。
證明透視
重量上界、連續指數與階分別在哪裏起作用
三個假設分別在三處起作用。條件 保證所用的 個方程都在已知的 個根之內,於是方程數與未知數一樣多。指數 連續,才使得把公因子 併入未知數後,係數矩陣成為 Vandermonde 矩陣;根的指數若分散,得到的是廣義 Vandermonde 矩陣,其行列式可以為零。 的階恰為 使各 互異,故行列式非零;而 讓我們由 推出 。論證中沒有構造任何重量為 的碼字,所以結論只是下界。
七個位置的完整伴隨式表
在 中令 。它在 沒有根,故此三次多項式不可約。令 、,則 。反覆相乘得到
表中七個元素互異且非零,而 ,故 的階是七。直接相乘得
由 生成的循環碼維數為四,有 16 個碼字。由 及 ,定理在 時給出距離至少三。生成多項式本身的重量為三,故距離恰為三。依指定座標次序,它的向量是 :這是碼字,不是單一位元錯誤。
常見錯誤
(把所有根都當作連續根來數)
生成多項式 在 的冪中有三個根:、 與 。若把它們當作三個連續根,會得到 ,可是 本身的重量只有三。下界要求指數連續:,所以最長的連續段是 ,給出 ,而這裏三正好達到。
對次數小於七的接收多項式 ,定義伴隨式為除以 的餘式,亦即 。碼字餘式為零,所以若 ,伴隨式是 。查表可辨認每一個單一位元錯誤位置:伴隨式為零便原樣輸出 ;否則翻轉表中唯一對應的座標。這可糾正所有重量至多一的錯誤,並不保證修正任意損壞。
概念視角結構
這個碼就是長度為七的二元漢明(Hamming)碼
把每個 寫成基底 下的座標向量,並以這些向量為列,組成 的二元矩陣 。於是 就是 的座標向量,所以該碼是 的核。由上表,這些列恰好是 的七個非零向量,各出現一次:這正是漢明(Hamming)碼的定義校驗矩陣。十六個半徑為一的球共含 個字,所以每個接收字都恰好在一個碼字的距離一以內,沒有任何伴隨式能提示兩位錯誤。
常見錯誤
(把向量當作最高次項在前來讀)
字串 表示 ,因為座標按常數項在前書寫。若反過來讀,便成了 ,其伴隨式為 。採用相反慣例的解碼器會把生成多項式當成受損的字並翻轉一個座標。計算伴隨式之前,必須先固定座標慣例。
例題 2.1.3
(追蹤一個接收字)
令 ,寫作 。模 有 ,故伴隨式為 。表中對應座標 ;翻轉它得到 ,寫作 。由於碼距為三,它是距離 至多一的唯一碼字。
例題 2.1.4
(最後一個座標出錯)
傳送碼字 ,寫作 ,並設座標 被翻轉,於是 ,寫作 。利用上表,
伴隨式指向座標 ,翻轉它便還原 。計算中從沒用到傳送的是哪個碼字:碼字部分對伴隨式的貢獻是 。
例題 2.1.5
(兩個錯誤會被錯誤糾正)
傳送零字,並設座標 與 被翻轉,於是 ,寫作 。其伴隨式為 ,所以單錯誤規則翻轉座標 ,輸出 ,寫作 。輸出是碼字,但與傳送的字相距三。錯誤重量為二時,解碼器仍然返回一個碼字,只是返回了錯的那個,而伴隨式完全沒有顯示失敗。
反例模式
零伴隨式不等於沒有錯誤
若傳送零字而發生重量三錯誤 ,接收字是非零碼字 ,伴隨式仍為零,解碼器會原樣輸出。零伴隨式只證明接收字屬於碼,不證明通道沒有出錯。
練習
快速檢查
(為何特徵二中 會推出 ?)
把等式 兩邊平方。
解答 · 答案
特徵二中平方是域同態,而 的係數在 ,故 。
快速檢查
(若伴隨式為 ,單錯誤規則翻轉哪個座標?)
在冪表中找出這個元素。
解答 · 答案
表中 ,故翻轉從零起算的座標 。
快速檢查
(解釋為何距離至少三排除兩個碼字同時距同一接收字至多一。)
使用 Hamming 距離的三角不等式。
解答 · 答案
三角不等式會使兩碼字距離至多二,與距離下界三矛盾。
快速檢查
( 生成的碼維數是多少? 呢?)
使用 ,並留意 在商環中代表甚麼。
解答
生成整個 維空間; 在商環中代表零,生成維數零的零碼。本節對非零碼的最小距離慣例不為零碼定義距離。
延伸閱讀
MIT 多項式碼講義 講解多項式編碼及利用餘式定位錯誤;CMU 編碼理論講義 討論 BCH 碼及連續根距離論證。