動機
最小距離定理告訴我們,附近的碼字是唯一的,但接收者仍需把它找出來。隨著碼變大,逐一比較所有訊息的代價可能很高。伴隨式則從方程中消去未知的被傳送字,只保留關於錯誤的資訊。對於二元長度十五的 BCH 碼,兩個擴域伴隨式確定一個二次多項式,其非零根標出被改動的位置。
關鍵的簡化恰恰是二元性。被改動的位元與被傳送的位元相差一,所以每個錯誤都以相同的係數貢獻其位置。我們可以用第一和第三冪和來表示至多兩個位置元素的和與積。這樣,二次式記錄了未知的位置,而無需在所有訊息上搜尋。
我們推導完整的算法,包括無錯分支、單個錯誤、被拒絕的伴隨式,以及對候選結果的驗證。它的保證只涉及至多兩個位元錯誤。即使所有代數檢驗都通過,解碼器在該半徑之外也可能輸出一個看似合理但不正確的訊息。理解這一局限是理解該算法的一部分。
定義
使用上一單元構造的域 與階為十五的元素 。座標編號為 ,字即其低次在前的多項式。該碼由
生成,參數為 。等價地,其碼字多項式在 處取值為零。假定每個接收到的係數都是位元。本單元處理的是錯誤,而不是符號缺失的刪除位置。
定義 15.2.1
(接收字的伴隨式)
對接收字 ,定義伴隨式
在特徵二中加法與減法相同。由於碼字 在這些點處為零,同樣的伴隨式就是 與 。若錯誤支撐集為 ,則
定義 15.2.2
(位置元)
座標 的位置元是 ,一個非零域元素。十五個非零域元素中的每一個恰好對應一個座標。這個解碼器使用的多項式,其根就是位置元本身。另一種常見約定使用位置元的倒數;其公式必須作相應一致的修改。
定理/命題
定理 15.2.3
(二次式識別一個或兩個錯誤)
若接收字與某個碼字至多有兩個位置不同,則要麼 且沒有錯誤,要麼 。在後一種情形,令
對於兩個錯誤, 的根恰是它們兩個互不相同的非零位置元。對於一個錯誤,根是零與它唯一的非零位置元。零根只是佔位符,並不標識任何座標。
定理 15.2.4
(經過驗證的有界距離解碼器)
計算伴隨式,並使用下面描述的二次式過程。只要存在距離不超過二的碼字,它就返回這個唯一的碼字;若不存在,則報告失敗。因此,若被傳送的碼字至多遭受兩個錯誤,它就會被恢復。超出這一傳輸承諾之外,返回的鄰近碼字不一定就是被傳送的那個。
證明思路或證明
冪和恆等式
證明
(位置元的冪和)
把可能的位置元記為 。對於一個錯誤,取其位置為 ,並僅在推導中令 。則 ,。在特徵二中展開得
因為二項式係數三在這個域中等於一。於是 。單個非零錯誤給出 。兩個互不相同的非零位置也給出 ,因為在特徵二中 會推出 。因此在非空且至多兩個錯誤的承諾下,除以 是合理的,並給出 。
現在展開 得 。在一個錯誤的情形,其根是零與 ;在兩個錯誤的情形,其根是兩個實際位置。 的導數是非零常數 ,所以根不會重複。這些陳述也解釋了為甚麼在承諾之外產生的任意二次式可能在 中沒有根。
為甚麼兩個伴隨式檢驗了整個碼
證明
(兩個伴隨式檢驗全部四個定義根)
對二元多項式 ,平方與取值可交換: 且 。因此 已經檢驗了根 ,而 檢驗第四個定義根 。它們的極小多項式因子恰是 的兩個因子。上一單元的取值為零刻畫證明了
在沒有錯誤數界的情況下,零伴隨式並不意味著被傳送的字未被改動:一個非零碼字本身就可以是錯誤。然而在至多兩個錯誤的承諾之下,一個兩個伴隨式都為零的非零錯誤,會是重量至多為二的非零碼字,與距離五矛盾。
從十五維二元字空間到 的伴隨式映射在 上是線性的。其核的維數為七,所以其秩為八。由於 的二元維數也是八,每個伴隨式對都會出現。因此這兩個域符號恰好提供了該碼所需的八個獨立校驗位元;它們並沒有丟掉接收者日後還需要的額外約束。
這一計算有有用的幾何解釋。所有具有相同伴隨式的接收字構成碼的一個陪集,因為它們的差的伴隨式為零。解碼就是為該陪集選一個小重量的代表並將其減去。選擇代表時不需要知道傳送的是哪個碼字。距離五表明,一個陪集至多含有一個重量至多為二的代表;並不表明每個陪集都含有這樣的代表。因此失敗訊息是關於錯誤半徑模型的有意義的資訊,而不是線性性或域運算出了問題的證據。最後的練習精確計數了有這類代表的陪集個數。
概念視角算法
把譯碼器看作即時計算的查找表
重量至多為二的不同錯誤圖樣有不同的伴隨式,所以在半徑二內譯碼,等同於查一張從伴隨式對到錯誤圖樣的表;表中沒有條目的伴隨式對就表示失敗。這張表可以預先算好並儲存。二次式的做法則是按需計算給定 的條目: 與 是定位多項式的係數,它的非零根直接讀出錯誤圖樣。由正確性定理,兩種程序定義了從接收字到輸出的同一個函數。
算法,包括失敗分支
先計算 。若二者都為零,返回 。若 而 ,報告失敗:前述恆等式排除了任何重量至多為二的錯誤模式具有這樣的伴隨式。
若 ,構造 與 。在全部十五個冪 處計算 。記錄每個零點的座標。若 ,則要求恰有一個這樣的非零根;若 ,則要求恰有兩個。否則報告失敗。非零導數排除了重根,但並不保證任意多項式在所給的域中分裂。
恰好翻轉所記錄的位元,得到 。最後驗證翻轉的個數至多為二,且 。只有兩項檢驗都通過才返回 。用 做多項式除法同樣可驗證成員關係。這些檢驗使算法的輸出約定變得明確,並能捕捉有誤的中間計算;它們不能替代前面的證明,即在承諾之下正確的根必定會出現。
證明
(每個分支的正確性)
若有任何碼字與接收字相距不超過二,就把它取作推導中的 。它的實際錯誤位置必須恰是上面所得的非零根,所以算法能找到它。反過來,任何被返回的候選者,經驗證,都是距離至多為二的碼字。若存在兩個這樣的候選者,它們的距離至多為四,與該碼的距離五矛盾。因此所有分支都滿足所述的有界距離約定。
證明透視
兩個承諾用在兩個不同位置
存在性一半用到的假設是:有某個碼字 與 相距不超過二。只有這樣,冪和推導才適用於一個重量至多為二的實際錯誤,從而保證 的非零根位於 中,並恰是錯誤位置。唯一性一半完全不需要關於傳送的承諾:驗證使每個返回的字都是距離至多為二的碼字,而兩個這樣的字相距至多為四,為距離五所不容。
關鍵一步是二次式背後的消元。在生成多項式的根處取值完全消去 ,二元錯誤值則只留下兩個未知位置,其初等對稱函數就是 與 。失敗分支使情況分析完整:、根的個數不對,或最後檢驗不通過,每一種都只會在沒有碼字與 相距不超過二時出現,所以報告失敗永不會丟掉正確答案。
例題詳解
例題 15.2.5
(位置零與位置一處的錯誤)
設錯誤出現在位置 ,即 。被傳送的碼字不影響伴隨式的計算。我們得到 與 。冪和恆等式給出 ,且
非零根對應於位置零與位置一,所以翻轉這兩個位元。兩個接收到的伴隨式隨之被抵消。注意,域元素一表示座標零,而域元素零表示根本沒有座標;混淆二者會使譯出的錯誤模式發生位移。
例題 15.2.6
(在確定位置之前先約化域中的冪)
取位置 處的錯誤。位置元為 與 ,所以 。又 ,因為 且 。因此
對於這個除法,把 乘以 並使用 ,即得 。二次式為 。查冪次表或對全部十五個候選者取值,即可定位到位置二與位置五。在約化這些表達式時,二元係數表是必要的:模十六的普通整數係數並不描述 中的算術。
例題 15.2.7
(一個錯誤,以及一個必須被拒絕的伴隨式)
對於位置四處的單個錯誤,,所以 ,。故 ,。捨去零根,翻轉座標四。相反,若沒有錯誤,則兩個伴隨式都為零,不會進入二次式分支,從而避免了除以零。
對於三個錯誤的多項式 ,第一個伴隨式為 ,但第三個為 。這裏 。解碼器拒絕這一對。該例子說明了一個在半徑之外但可被檢測的模式;並不意味著三個或更多錯誤的每種模式都可被檢測。
常見錯誤
反例模式
通過驗證的碼字仍可能是錯誤的被傳送字
設 。若發出的是零,則是三個錯誤產生了 。但 與 只相差兩個錯誤,所以解碼器返回 。它的答案是一個有效的、唯一鄰近的碼字,卻與被傳送的零字不同。在承諾的半徑之外,代數驗證無法重構究竟發生了哪種傳輸歷史。
常見錯誤
(二元冪和不能照搬到其他字母表或約定)
的公式也不能原封不動地照搬到非二元碼。在非二元碼中,錯誤係數可能有不同的非零值,所以伴隨式是加權冪和,而不是 與 。也不應把我們這種以位置元為根的多項式與倒數根約定混用:兩者都可用,但改變其中一個定義時,查找規則與公式必須一併更改。
對這個固定的碼,霍納(Horner)法取值與檢驗十五個可能的根,都是小規模的精確有限域計算。這並不證明對任意錯誤預算存在適用於一般 BCH 碼的快速解碼器。針對更長的碼與更大的設計距離的算法,需要更完整的錯誤位置多項式計算,以及另行的代價分析。
總結
兩個擴域伴隨式完整地表達了這個二元碼的奇偶校驗。在至多兩個錯誤之下,它們的第一和第三冪和恢復出位置元的和與積。一個二次式、明確的零伴隨式分支以及最後的成員檢驗,合起來構成完整的有界距離解碼器。它的保證在半徑二之內是精確的,在半徑之外則有意加以限制。
練習
快速檢查
(對兩個互不相同的錯誤位置,為甚麼分母 不會為零?為甚麼這一論證用到了特徵二?)
寫 ,並問兩個域元素之和何時為零。
解答
方程 給出 。在特徵二中,,與位置互不相同矛盾。在其他特徵中,互為相反數的非零元素可以不同,所以該推斷不成立;二元錯誤的冪和設定也需要修改。
快速檢查
(若 且 ,指出 的兩個根,並解釋翻轉哪個座標。)
當常數項為零時把 分解。
解答
該多項式分解為 。其根為零與 。只有後者是非零冪 ,從而是座標位置。找出那個唯一的指數 並翻轉其位元;零作為佔位符被捨去,而不被解釋為座標零。
快速檢查
(在 個伴隨式對中,有多少個對應於重量至多為二的可糾正錯誤?解釋為甚麼這些對互不相同。)
比較兩個具有相同伴隨式的錯誤模式。
解答
共有 個錯誤模式。若有兩個具有相同的伴隨式,它們的和就是重量至多為四的碼字,除非二者相同否則不可能。因此恰有 個伴隨式對是可糾正的,剩下 個對沒有重量至多為二的錯誤代表。解碼器在這些陪集上報告失敗。
快速檢查
(設發出的是零,但錯誤多項式等於 。解碼器返回甚麼?為甚麼這與它的定理並不矛盾?)
計算一個碼字的伴隨式。
解答
接收字為 ,它是碼字,所以其伴隨式為零。解碼器不作任何改動地返回 。五個位元被改動,所以這次傳輸違反了至多兩個錯誤的假設。其觀察到的字同樣與無錯誤地發出 相一致;僅從接收字,接收者無法區分這兩種歷史。