動機
奇偶校驗是每個被傳送的碼字都必須滿足的一個方程。對循環碼而言,把碼字多項式在生成多項式的某個根處取值,就得到這樣一個方程。有用的問題是:如何選取若干個根,使得少數幾個被改動的座標無法同時滿足所有校驗。一個域元素的連續冪給出了答案:只要所設想的錯誤的支撐集足夠小,所得方程就構成一個可逆的范德蒙(Vandermonde)方程組。
這一構造區分了字母表的兩種角色。被傳送的符號可以保持為二元的,即使我們是在更大的域中對它們的多項式取值。擴域提供了足夠多互不相同的校驗點,但它並不會把每個二元座標變成可獨立選取的擴域符號。這一區別既解釋了構造的威力,也解釋了下面維數的計算。
我們假定讀者已知域上的多項式除法,以及先前把循環碼描述為模 的理想的內容。我們將證明這裏用到的根界,包括使其行列式非零的各項假設。最後的二元例子是一個完全確定的碼;一般的設計距離只是下界,並不保證對每種參數選擇都取等號。
定義
設 為質數冪。在一個給定的、包含 的擴域 中工作。取正整數 ,以及乘法階恰為 的元素 。於是 互不相同且非零。 上的一個字 對應於
座標零是常數項係數。在模 下乘以 會旋轉各座標,原來的最後一個座標移到位置零。
定義 15.1.1
(極小多項式)
對 ,它在 上的極小多項式是以 為根的、次數最小的正次首一多項式。多項式除法表明,它整除每個以 為根的 上的多項式:除以極小多項式,再對次數更小的餘式取值。由極小性,餘式必須恆等於零。
定義 15.1.2
(BCH 碼與設計距離)
固定一個整數 與一個整數 。設 為
的各極小多項式的首一最小公倍式。指數按模 理解。由 生成的循環碼稱為具有這些連續定義根、設計距離為 的 BCH 碼。常見的狹義選擇是 。不同的設計參數可以產生同一個生成多項式,從而產生同一個碼。
定理/命題
定理 15.1.3
(生成多項式存在於被傳送的字母表上)
多項式 屬於 ,並且整除 。它在模 下的倍式構成一個維數為 的線性循環碼。等價地,該碼的碼字恰是次數小於 、且在每個所選定義根處取值為零的多項式。
定理 15.1.4
(連續根距離界)
若該碼非零,則每個非零碼字的重量至少為 。因此其最小距離至少為 ,並且它能唯一地糾正至多 個符號錯誤的每一種模式。僅憑這一距離結論並不能提供解碼算法。
概念視角代數
把碼看作擴域核在基域上的部分
設 為 上的 矩陣,第 行第 列的元素為 。於是 列出各值 ,所以該碼就是 。從第 列提出因子 後,任意 列都成為可逆的范德蒙矩陣,因此任意 列在 上線性無關,這正等價於距離至少為 。在 上這個核的維數是 ;只保留分量屬於 的向量,距離界仍然成立,維數卻變成 ,可能更小。
證明思路或證明
極小多項式把共軛校驗打包在一起
證明
(弗羅貝尼烏斯(Frobenius)軌道與 g 生成的理想)
若 上的多項式 在 處為零,則 。因此一個根會帶來它的整個弗羅貝尼烏斯(Frobenius)軌道。反過來,對 的軌道中互不相同的元素 ,構造所有 的乘積。弗羅貝尼烏斯映射置換這些因子,所以它固定每個係數。被弗羅貝尼烏斯固定的係數滿足 。這個多項式在域中至多有 個根,而它已在 的全部 個元素處為零,所以被固定的元素恰好構成該子域。因此軌道乘積屬於 。
每個以 為根的多項式在整個軌道上為零,從而在 中被這個互異線性因子的乘積整除。除以首一的軌道乘積同樣在 中進行,這證明它就是極小多項式。這給出了計算生成多項式的實用方法:把指數按模 乘以 的作用分成軌道,然後對每個所需的軌道取一個極小多項式。同一軌道的重複出現不會引入新的獨立因子。
每個定義根都是 的根。它的極小多項式整除該多項式,因此它們的最小公倍式也整除它。寫 。模 下 的每個倍式都有唯一的代表 ,其中 :把乘子除以 即可。唯一性成立,因為這樣的非零乘積次數小於 ,不可能在模 下為零。這些乘子給出大小為 的一組基。乘以 保持該理想,從而證明了循環性。
在所選根處取值為零,等價於被它們的極小多項式整除,從而被 整除。這證明了另一種校驗描述。通過選取 在 上的一組基,擴域方程可以展開為若干個基域方程;若不考慮共軛性而直接數所列出的擴域方程,就會高估其秩。
生成多項式也給出了具體的編碼器,無需為每條訊息重新解方程組。把訊息係數列為次數小於維數的多項式 ,再乘以固定的 。乘積的次數小於 ,所以此時無需約化。不同的訊息給出不同的乘積,因為域上的多項式環沒有零因子。在接收端,除以 可檢驗候選字。這些運算說明,即使尚未推導出任何高效的糾錯過程,稱其為一種構造也是恰當的。它們也揭示了碼率的代價:加入一個真正新的共軛類會增大生成多項式的次數,並減少自由訊息係數的個數。而加入一個來自已被要求的類的根則沒有這種代價。
短支撐集迫使范德蒙矛盾
證明
(短支撐集無法滿足全部校驗)
假設某個非零碼字的重量為 ,支撐位置互不相同,為 。令 。前 個連續根方程對 給出
第 行第 列為 的矩陣,其行列式為 。理解這一恆等式的一種方法,是把行列式看作交錯多項式:每個差都整除它,總次數一致,比較首項單項式可得係數為一。這些因子非零,因為 的階恰為 ,且支撐位置模 互不相同。
因此該方程組在 上可逆。它迫使對每個 都有 。但每個 都非零,即使 為負也是如此,並且每個支撐係數也非零。這一矛盾證明了重量界。線性性把最小非零重量化為最小距離。若兩個碼字都與同一個接收字相差不超過 處改動,則它們彼此相距不超過 ,這證明了所述半徑內的唯一性。
證明透視
為甚麼連續根是特殊的
證明用了三個假設,各自在一個可辨認的位置。連續指數 使列因子 可以提出,留下范德蒙矩陣的各行 ;任意選取的 個根沒有這種分解。 的階恰為 ,使各 互不相同,所以行列式 非零。最後,每個 非零,才能由 推出 。
關鍵一步是只保留假設中的 個支撐座標,並只用 個可用方程中的 個,使問題變成一個方陣線性方程組。論證以與支撐集的選取相矛盾而收結。它從不計算 的根數,而 的次數可能接近 ,所以任何根數界都不能代替這個行列式。
例題詳解
例題 15.1.5
(構造域並辨認兩個共軛類)
取 ,以 記 的剩餘類。該多項式在 中沒有根。一個沒有線性因子的可約四次式必是不可約二次式之積;而 上唯一的首一不可約二次式是 。該四次式模這個二次式餘一,所以它不可約,商環確實是一個有十六個元素的域。
關係式為 。其非零乘法群有十五個元素,所以 的階整除十五。它不是一或三,因為這兩種可能都會給出次數低於四的非零多項式關係。又 ,因為若相等就會給出二次關係。所以它的階為十五。
指數一和三模十五的弗羅貝尼烏斯軌道分別是 與 。第一個極小多項式是 。由於 的階為五,它是 的根;其軌道有四個元素,所以這個四次式就是它的極小多項式。兩組根互不相交。
例題 15.1.6
(參數恰為 [15,7,5] 的二元碼)
取 與 。定義根為 。它們的兩個共軛類給出
生成多項式的次數為八,所以二元維數為七。連續根定理給出距離至少為五。多項式 本身是重量為五的非零碼字,所以距離也至多為五。因此精確參數為 ,並且每一對位元錯誤都能被唯一糾正。等號是由一個具體的碼字確立的,而不是把設計距離解釋為一個等式定理。
例題 15.1.7
(編碼並旋轉而不改變碼)
採用係數訊息的約定,把 乘以 來編碼。八次與六次項各出現兩次,在特徵二中相消,留下
其六個非零座標位於位置 。七個訊息係數一般並不原樣出現在七個指定的座標上;我們並沒有聲稱這個編碼器是系統碼。
對於越過端點的旋轉,把 乘以 。由於在商環中 ,結果是 。它仍是一個碼字。把旋轉後的字在某個定義根處取值,相當於把其原來的值零乘以該根,這給出了校驗得以保持的另一個直接解釋。
常見錯誤
常見錯誤
(擴域校驗不會改變訊息字母表)
剛才構造的碼有 個碼字,而不是 個。每個座標和每個乘子係數都屬於 。在 中取值只是用來表達二元線性約束的一種手段。把所列出的每個域方程當作十六個獨立的選擇,會徹底改變這個構造。
常見錯誤
(一個共軛類只貢獻一個因子)
把每個連續根都算作一個新的極小多項式因子會重複計算。根 、 與 已經屬於同一個二元共軛類。把同一個極小多項式乘上多次會引入重複因子;由於 是奇數, 在特徵二中沒有重根,所以這樣的乘積根本不整除 。對根 ,樸素乘積的次數是 ,而最小公倍式 的次數是 。
反例模式
階太小的元素
也許有人以為任何滿足 的非零 都可以用。取 、例題中的域 ,以及 ;它滿足 ,但階只是五。取 、,定義根 組成一個共軛類,所以 。於是
是重量為二的碼字,低於設計值五。直接驗證:每個定義根 都是 的冪,所以 ,。在證明中,位置 與 給出 與 ,范德蒙行列式為零。修正就是所述假設: 的階必須恰為 ,使模 不同的位置給出不同的 。
距離證明是在錯誤數量的承諾之下給出唯一答案;要確定被改動的位置,需要用到配套單元中發展的伴隨式算法。
總結
BCH 構造在保持基域字母表的同時選取擴域中的根。弗羅貝尼烏斯軌道決定生成多項式及其維數。連續的根的冪迫使每個短支撐集都滿足一個可逆的范德蒙方程組,從而證明設計距離的下界。長度為十五的二元例子達到了該界,因為它的生成多項式本身的重量已是五。
練習
快速檢查
(解釋為甚麼由 可推出 ,以及為甚麼此時 沒有重根。)
考慮 的質因數與 的導數。
解答
整除 的質數不可能整除 ,所以它不可能整除 。導數為 ,在該域中非零。它與 的公共根只能是零,但零不是後者的根。因此這兩個多項式互質,沒有重根。
快速檢查
(證明這一構造的維數估計 ,允許右端為負。)
用弗羅貝尼烏斯軌道的大小來界定每個極小多項式的次數。
解答
每個極小多項式的次數至多為 ,因為弗羅貝尼烏斯軌道至多經過 步就閉合。最小公倍式的次數至多等於其各因子次數之和,故 ,即得所述維數界。共享的軌道可能使這一估計非常寬鬆。
快速檢查
(在 上,設 的階為七,並選取根 ,於是設計距離為四。求生成多項式與實際最小距離。)
列出模七的二元分圓軌道。
解答
二元指數軌道是 與 。所選的根遇到了這兩個軌道,所以 。該碼維數為一,由零字與全一字組成。其距離為七,嚴格大於設計值四。
快速檢查
(解釋為甚麼長度為十五的碼雖然距離等於其設計距離,卻不是完美的二錯糾正碼。)
把互不相交的半徑二球的總大小與 比較。
解答
長度為十五的二元半徑二的球含有 個字。 個碼字的這類球互不相交,但它們合起來只含有 個字。因此有些接收字位於所有半徑二的球之外。達到設計距離界,與用解碼球填滿整個環境空間,是兩回事。