動機
插值能修復缺失的值,是因為它們的位置已知。面對未知錯誤時,任意選取一組插值點,可能選中被破壞的值,從而恢復出錯誤的多項式。逐一嘗試所有可能的錯誤位置集合雖然是有限的,但所需的嘗試次數可能多得無法承受。有用的觀察是:一個多項式可以在每個被破壞的位置處取零,使這些位置上的方程變得無害,而無需事先知道這些位置。
乍看之下這引入了一個非線性問題:未知的訊息多項式必須與未知的錯誤定位多項式相乘。我們改為把它們的乘積引入為一個新的獨立未知量。接收到的值本來就是已知純量,因此所得方程是線性的。我們將證明,在解碼假設成立時,它們的解為何能恢復出多項式商;以及在沒有該假設時,為甚麼必須檢驗整除性。
我們使用求值碼一章中域上根的界與距離的計算。這裏的論證只計數域運算;實際的位元複雜度還取決於有限域及其運算如何表示。
定義
固定域 、互異點 ,以及滿足 的整數 ,。碼字是次數小於 的多項式的取值。設 為接收字。若一個候選訊息多項式與 至多在 個座標上不同,則稱其在預算之內。在涉及次數界的陳述中,零多項式的次數為 。
尋求滿足下式的多項式
使得
多項式 稱為錯誤定位多項式,取為次數恰為 的首一多項式。當 時,它是固定的多項式 1。這些方程對 的 個低次係數與 的 個係數而言是線性的:因子 是數據,而不是未知量。共有 個未知係數和 個方程。
首一性排除了平凡的一對 ,它對每個接收字都滿足方程,卻不傳達任何訊息。把首項係數固定為 1 也消除了純量的不確定性。若發生的錯誤少於 個, 不必恰好是以這些錯誤位置為單根的多項式;允許存在額外的因子。
寫出實際的係數行
記 。把未知的定位多項式低次項移到左邊,每個接收座標對應一行:
一旦求值點和接收值已知,這個係數矩陣的每個元素都是已知的。不出現兩個未知係數的乘積。未知的乘積 已被 的獨立係數列表所取代;之後用整除性來檢驗這種替換確實來自某個訊息多項式。正是這一步使普通線性代數得以適用。
概念視角代數
把方程組看成一個多項式同餘式
令 ,並設 是滿足 、次數小於 的插值多項式。方程 恰好表示 在全部 個點上為零,即
由於 ,多項式 就是 除以 的餘式。解碼就是要找一個次數為 的首一 ,使這個餘式的次數小於 。
求值點為零不造成困難。當 時,其對應的行化為 。我們從不除以求值點。當 時,第二個和為空,該行就是 ,因為常數單項式 的值為 1,在零處也是如此。這些約定使邊界情形成為同一方程組的普通實例,而不是特殊的數值例外。
該方程組可能方程多於未知數,也可能方程相關。因此高斯(Gauss)消去法必須處理不相容與自由變量,而不能僅僅對一個假定非奇異的方陣求逆。後面的正確性證明有意允許所有這些可能。未用完錯誤預算的接收碼字,自然會產生自由的定位係數;不應僅僅因為矩陣秩虧就拒絕這樣的輸入,把它當作例外。
定理/命題
定理 16.2.1
(在假設下每個解都有相同的訊息商)
設次數小於 的多項式 與 至多在 個位置上不同。則該線性方程組有一個滿足首一的、次數為 的 的解。每個這樣的解都滿足 。因此,即使線性方程組有多個解,其商也都是同一個 。
定理 16.2.2
(帶有被檢驗輸出的多項式時間唯一解碼器)
求解該線性方程組。若它不相容,則報告在預算內沒有碼字。否則取任意一個解,用 除 ,僅當餘式為零、商的次數小於 ,且其取值與 至多在 個位置上不同時,才接受該商。若任一檢驗失敗,則報告在預算內沒有碼字。當 時,該過程對每個接收字都是正確的,並且僅使用多項式數量的域運算。
證明思路或證明
證明
(填充後的真實定位多項式與根的計數)
被保證的訊息提供一個解。 設 為 的不正確位置的集合,記 。定義
填充因子使 成為次數恰為 的首一多項式。它可能引入重根,或在正確位置處取零,這些都是允許的。乘積的次數小於 。在正確位置,。在不正確位置,由於 ,兩邊均為零。因此這是一個解。這裏並未使用接收方不經解碼就能構造它的說法;這只證明了只要被保證的訊息存在,線性方程組就是相容的。
任意解都有正確的商。 任取一個具有指定次數和首一性的解 ,並與真實的 比較。多項式 的次數至多為 。在每個正確位置,
這樣的互異點至少有 個。因此根的界迫使 。由於 ,精確的多項式除法給出商 和零餘式。這個論證既不要求定位係數唯一,也不要求接收值非零,也不要求知道被破壞的位置。
證明透視
方程個數並不等於正確性證明
方程的個數至少與未知數一樣多,但僅憑這一觀察,既不能證明相容性,也不能證明商正確。相容性來自填充後的真實定位多項式。正確性來自 在所有正確位置處的根。不等式 出現在那個根的計數中,在那裏它具有超出矩陣維數的數學意義。
第二個定理的解碼器在此論證之上再加上拒絕規則與代價上界。
證明
(半徑內的唯一性與計算代價)
拒絕是合理的。 求值碼的距離為 ,所以兩個不同的訊息多項式不可能同時處於預算之內。若存在一個,則第一個定理表明方程組是相容的,並且每個解都通過商與距離檢驗,得到該訊息。因此,不相容或檢驗失敗說明不存在這樣的候選。反之,被接受的商已被顯式驗證為一個在預算之內的、滿足次數界的有效多項式,所以接受不會憑空捏造一個無效的候選。
這說明了為甚麼「取任意一個解」是合理的。我們不必在解空間中搜尋一個碰巧合適的定位多項式。若數據在預算之內可解碼,則所有解給出同一個商;若不可解碼,則沒有任何解能通過最後的候選檢驗。非零餘式是有意義的拒絕結果,而不是解碼定理的失敗。
代價。 用基本實現,高斯消去法可在 次域運算內求解含 個方程、至多 個未知數的方程組。寫出冪、對次數為 的多項式做除法、對商求值,以及統計不一致的位置,同樣只需多項式數量的運算。矩陣奇異時可以直接選取一個含自由變量的解;未知係數向量的唯一性是不必要的。這些界不包含對一次域運算的代價的未加說明的估計。在有明確高效的域表示時,這些運算還須以位元為單位實現並計數;代數證明本身並不保證某個特定的軟件實現。
例題詳解
例題 16.2.3
(在七元域上解碼出一個被破壞的取值)
取點 ,維數 ,預算 。收到 。記 ,。方程具有如下形式
行化簡得 以及 。直接檢驗該解: 在五個點處的值為 , 的值為 ;乘積 給出同樣的列表。
用 除 。商的第一項 留下餘式 ;下一項 留下 ;最後一項 留下零。商為 。其字為 ,僅在第三個座標上不同。定位多項式的根是求值點 ,而不是序數標籤「第二個座標」。
例題 16.2.4
(較小的預算是另一種假設)
在 上,取點 且 。 的字是 。若接收字為 而預算為零,則 ,方程組要求一個線性多項式在全部四個位置上一致。在 0 和 2 處的值已迫使 ,其在 1 處的值是 3,所以方程組不相容。這與糾一個錯誤並不矛盾:那一次運行要求的是零個錯誤。
預算為 1 時,,一個有效解是 ,(模 5)。精確除法恢復出訊息。所選的預算決定了線性方程組,以及它的失敗所能確立的結論。
例題 16.2.5
(多餘的定位因子不會產生多餘的訊息)
使用 的全部七個點,,預算為 2。設接收字沒有錯誤,等於 的取值。 配 ,以及 配 ,都是該方程組的解。它們的係數向量不同,但商都是同一個 。第一個定位多項式甚至在一個正確的點處取零。當錯誤預算有餘量時,不能把它的根解釋為實際錯誤的準確列表。
常見錯誤
(從定位多項式讀出錯誤值)
恢復出訊息之後,位置 處的實際錯誤值為 。定位多項式的係數並不直接編碼這些值。在第一個例子中,被破壞的位置是域點 ,錯誤值為 ;定位多項式的常數項係數為 。若混淆這三個數,就會把座標標籤、錯誤大小與多項式係數混為一談。線性方程組把接收符號用作數據,而定位多項式記錄的是乘法應在何處壓制某個方程。
常見錯誤
反例模式
有理擬合不一定是多項式訊息
在 上,取點 ,,接收值為 。一對 , 滿足每個方程:每個 都是 的逆元。但 不整除 。
在一個錯誤之內不存在二次訊息。若某個二次訊息在四個點處一致,則 的次數至多為 並有四個互異的根,所以它為零。在 處對該恆等式求值得 ,這在域中不可能。因此線性方程組在不可解碼的數據上也可能是相容的;除法是必不可少的檢驗。
常見錯誤
(把預算提高到唯一解碼半徑以外)
半徑條件不能隨意去掉。對五點、維數為 的碼,多項式 的字是 。接收字 與零字相差一個錯誤,與該非零字相差兩個錯誤。預算為 時兩個訊息都被允許,所以沒有任何解碼器能統一地判斷發送的是哪一個。這是資訊本身的局限,而不是高斯消去法的缺陷。
含有擦除時,刪去被擦除的座標,並在其餘互異的求值點上運行同一算法。若有 個符號被擦除,其餘值中至多有 個錯誤,則條件為 ,即 。必須在倖存的位置中計數錯誤;按此約定,被擦除的位置不會同時被算作未知錯誤。
總結
定位多項式使有問題的求值方程變為零,而乘積變量把問題化為線性代數。根的計數論證證明,在唯一解碼半徑之內,每個解都有正確的商。精確除法與候選檢驗把真正的訊息多項式與偽造的有理擬合區分開來,在違反錯誤假設的輸入上也是如此。
練習
快速檢查
(對 、,在沒有擦除時被涵蓋的最大整數錯誤預算是多少?若有兩個位置被擦除呢?)
使用 ,再使用 。
解答 · 答案
沒有擦除時, 允許 。有兩個擦除時,剩下十個取值,所以 至多允許兩個未知錯誤。混合不等式給出同樣的答案,。
快速檢查
(為甚麼選取 、 是不可接受的,儘管它滿足插值方程?)
想想這對多項式對接收字說明了甚麼。
解答
它會使每個接收向量看起來都滿足方程,而用 作除法沒有定義。首一的首項係數固定了一個非零的、次數為 的定位多項式,並使其餘方程成為非齊次線性約束。
快速檢查
(在第一個例題中,透過計算模 下的 、 與 ,驗證點 處的方程組方程。)
解答 · 答案
模 下 。 的整數值為 ,故 。又 。這檢驗了方程組的一行成立;一個解需要所有行都成立。
快速檢查
(設在假設下兩個首一的定位多項式解有不同的額外因子。在不假定線性方程組滿秩的前提下,證明它們的商仍然一致。)
對每個解分別把根的計數用於 。
解答
每一對解都按同樣的正確位置根的計數滿足 。因此其非零的 整除 ,商為 。該論證確定的是商,而不是自由的定位因子,所以係數方程組秩虧不會對訊息造成歧義。