動機
重複一個符號,是透過多份相同的資訊來保護它。多項式求值則以另一種方式分散資訊:若干訊息符號成為係數,而傳輸的符號是多項式在互異點處的取值。只要倖存的取值足夠多,就能確定整個多項式。這使得該構造在擦除情形下尤為清晰,因為接收方知道哪些位置遺失了。
關鍵事實是:兩個低次多項式若不相等,就不可能在太多互異點上取值相同。由此可得距離的證明、針對擦除的插值解碼器,以及冗餘度的精確刻畫。我們還將導出校驗矩陣,把這一求值觀點與前面線性碼各章聯繫起來。未知錯誤需要另外的論證,後續解碼單元將會給出。
我們假定讀者已掌握有限域運算、多項式除法,以及線性碼及其距離的定義。
定義
設 為有限域,取整數 以及互異點 。對次數小於 的多項式 ,定義其求值字
這些字構成的集合稱為 Reed–Solomon 求值碼 。係數訊息 表示 。所有運算都在該域中進行。當 是非質數的質數冪時,域運算並不是整數模 的運算。
擦除是明確缺失的座標。錯誤是指收到的域元素與所發送的不同,而其位置不一定已知。我們設有 個擦除位置,並在其餘位置中有 個錯誤;這兩個座標集合互不相交。最小距離在這些計數的界限下給出唯一性,而算法則需另行找出所發送的字。
對線性 碼,下面證明的 Singleton 界斷言 。達到該界的碼稱為極大距離可分碼(MDS)。這是關於固定長度與維數下距離的陳述,不同於完美性,後者問的是互不相交的解碼球是否填滿整個環境空間。
定理/命題
定理 16.1.1
(Singleton 界)
每個線性 碼都滿足 。
求值構造達到這個界,而插值同時提供它的擦除解碼器與校驗關係。
定理 16.1.2
(求值碼的參數與擦除恢復)
碼 是線性碼,參數為 。它的任意 個座標即可確定整個碼字。特別地,至多 個擦除可被唯一恢復。更一般地,當 時,含有 個未知錯誤和 個擦除的接收字,在該錯誤界內至多與一個碼字相容。
定理 16.1.3
(插值權重給出校驗關係)
假設 ,並令
以 ()為元素的 矩陣的秩為 ,並且 。這裏在方程 中把字視為列向量;若採用行向量的約定,則取轉置。
證明思路或證明
根的個數決定碼的參數
證明
(根的界、單射性與一個最小重量的字)
求值是線性的,因為對和與純量倍數求值與這些運算可交換。次數至多為 的非零多項式在域中至多有 個互異的根。回憶其證明:根 透過除法給出因子 ;由於域中沒有零因子,每個不同的根也是剩餘因子的根。對次數歸納即證得該界。
若一個次數小於 的多項式在全部 個點上的取值皆為零,則根的界與 迫使該多項式為零。因此求值映射是單射,維數為 。對任意非零碼字,至多有 個座標為零,所以其重量至少為 。這個下界是可以達到的:多項式 在這 個點處為零,而在所選點集的其他點處不為零。當 時,取空積 1。故最小距離恰為 。
證明
(刪去 個座標)
下面給出 Singleton 界的一個不依賴求值構造的直接證明。對最小距離為 的碼,從每個字中刪去任意 個座標。兩個不同的碼字不會因此變得相同:否則它們原本至多在這 個位置上不同。因此刪除映射是單射。對於維數為 的線性碼,這給出 ,從而得到該界。求值碼由根的計數而達到這個界。
由取值恢復多項式
證明
(Lagrange 插值與一次距離計數)
任取 個互異的倖存點 ,其取值為 。定義 Lagrange 多項式
由互異性,每個分母都不為零。每個 的次數至多為 ,在 處等於 1,在其他選定點處等於 0。因此 具有所給的取值。若另一個次數小於 的多項式也具有這些取值,則它們的差有 個根,必為零。把重構出的 在缺失的座標處求值,即可恢復所有擦除。
對於錯誤與擦除並存的情形,設兩個候選碼字在未被擦除的接收位置上,各自至多有 處與接收字不同。它們在未被擦除的位置上至多有 處互不相同,在被擦除的位置上至多有 處不同。它們之間的距離至多為 ,這是矛盾。由此證明了唯一性。但這並未告訴我們哪些未擦除位置是錯的,因此在任意 個接收位置上做普通插值尚不是糾錯算法。
選擇訊息符號的含義
係數編碼器便於證明線性性,但訊息不必是係數列表。可任選 個座標位置作為資訊位置。把訊息解釋為這些位置上期望的取值,插值出取這些值的唯一的次數小於 的多項式,再輸出它在每個點的取值。於是訊息原封不動地出現在指定座標上:這是一個系統編碼器。插值的單射性表明每個舊碼字仍然出現,所以碼及其距離都沒有改變,改變的只是訊息與碼字之間的對應關係。
對於擦除恢復,資訊位置不必在倖存位置之中。任意 個互異的倖存點就足夠了。這種靈活性正是 MDS 性質在擦除模型中的操作含義:沒有任何特定的 個位置享有特權。若倖存的符號多於 個,可以由任意 個重構,再與其餘觀測值比較。在僅有擦除的假設下它們一致。若沒有這一假設,不一致說明僅有擦除的模型是錯誤的,但這本身並不能指出所有不正確的符號。
擦除的上限是尖銳的。取一個重量最小的非零碼字,其支撐有 個位置,並恰好擦除這個支撐。所有倖存座標都是零,與零碼字的情形一樣。接收方無法由倖存數據分辨這兩個所發送的字。因此沒有任何該碼的解碼器能恢復所有 個擦除的模式。前面的恢復定理與這個歧義例子給出了互相匹配的正反兩方面的陳述,而不只是一個充分條件。
增大 會提高符號率 ,但同時降低所保證的擦除容忍度與最小距離。對於固定的求值構造,這種權衡是精確的。它並不比較所有字母表上所有可能的碼,並且要有足夠多互異的域點,仍是該構造的一部分要求。
插值也解釋了校驗矩陣
證明
(缺失的最高次係數,以及對各行的根計數)
對多項式 ()在全部 個點上做 Lagrange 插值。它的 係數為零。第 個 Lagrange 基多項式的 係數是 ,所以比較係數得
對於訊息單項式 ()與行指標 ,有 。因此該恆等式表明 。由線性性,每個碼字都在 中。
各行是線性無關的。若某個行組合為零,則一個次數至多為 的多項式 在全部 個點上滿足 。每個 非零,所以 有 個根,必為零。於是秩為 ,核的維數為 ,與 的維數相等。當 時,該碼是整個空間,空的校驗矩陣可單獨處理;此時不需要非零的校驗方程。
證明透視
校驗矩陣證明中各假設在哪裏起作用
證明分為兩半,各用不同的事實。包含關係 純粹是次數的計算:次數 的訊息單項式乘以次數 的行單項式,次數至多為 ,因此最高次 Lagrange 係數為零的恆等式適用。行的範圍止於 的原因只在這裏;多一行就會達到次數 ,恆等式便不再成立。各行線性無關則再次用到根的界,並用到 ,而這由各點互異保證。兩半在維數計算中會合: 的維數為 ,所以包含關係變成相等,無需直接描述核。假設 只是保證 至少有一行。
例題詳解
例題 16.1.4
(由三個係數編碼出五個符號)
在 上,取點 且 。係數訊息 表示 。它的取值為
因為未約化的值是 。該碼為 :它能唯一糾正一個未知錯誤,或恢復兩個擦除。若以前三個取值作為訊息,則訊息為 。係數編碼與系統取值編碼是同一個碼的兩種不同的訊息約定。
例題 16.1.5
(恢復兩個缺失的取值)
設點 處倖存的取值為 。記 。第一個給出 。另外兩個給出模 7 下的 與 。用第二個方程減去第一個方程的兩倍,得 ;於是 。重構出的多項式為 ,在 處被擦除的值是 。這三個點的互異性與次數的界,證明了唯一性,而不僅僅是這一次計算成功。
例題 16.1.6
(用兩個校驗方程檢驗同一個字)
對上面的五個點,權重為 。例如在點 0 處,分母為 (在該域中),其逆元為 5。矩陣為
對字 ,兩個整數點積分別為 與 ,模 7 後均為零。若第四個座標增加 1,則伴隨式增加第四列 。這檢驗了成員資格,並分離出該指定錯誤對伴隨式的影響;識別未知錯誤仍然需要解碼規則。
概念視角結構
對偶碼仍是一個求值碼
的各行生成 ,因為 的秩為 且 。以次數小於 的多項式 為係數的行組合,就是字 。所以 先對次數小於 的多項式求值,再把第 個座標乘以 。根的界使每個非零對偶字的重量至少為 :對偶碼同樣是 MDS 碼。在例題中,兩行的重量分別為五和四。
常見錯誤
常見錯誤
(MDS 不等於完美)
在 的例子中,半徑為 1 的球含有 個字。該碼有 個字,所以其互不相交的半徑為 1 的球共含 個字,少於環境空間的 個。它達到了 Singleton 界,卻仍使許多接收字落在這些球之外。不同的最優性陳述比較的是不同的資源。
反例模式
剩餘類環不能代替域
在 上,非零的一次多項式 在 0 和 2 處都為零。在 處求值得到 ,重量為 2,而對長度為 4、維數參數為 2 的情形,域上的公式會預測距離為 3。失效的一步是根的界:2 是零因子,消去律不可用。四階域是存在的,但它與這個剩餘類環是不同的代數對象。
常見錯誤
(重複使用同一個求值點)
求值點必須互異。重複同一個點,只是把同一個方程再加一份,而不是一個獨立的插值條件。在 上取點 與 ,多項式 的取值為 ,是重量為 的非零碼字,低於根的計數所給出的 。對於長度大於 的情形,需要不同的或擴展的構造;本章的定義無法提供這麼多互異的域元素。
總結
域上根的界給出精確的距離與單射的編碼。Lagrange 插值恢復擦除,Singleton 論證解釋了所達到的距離界,而對最高次係數的比較則產生顯式的校驗關係。這些結果把可恢復的缺失位置與未知錯誤區分開來,並為配套單元中的多項式時間錯誤解碼器作好準備。
練習
快速檢查
(在 上,在 處對 求值,並在 時寫出碼的參數。)
把每個值模 約化,再使用 。
解答 · 答案
該字為 ,碼為 。在 處的整數值是 ,在該域中為零。
快速檢查
(在該碼中,只有取值 與 倖存。恢復 。)
記 ,把兩個方程相減。
解答 · 答案
記 。相減得到模 下 ,所以 ,。兩個互異點唯一地確定一個次數小於 的多項式。
快速檢查
(對 求值碼,解釋當 時,為甚麼 、 被唯一性定理所涵蓋,而 、 不被涵蓋。)
比較 與 。
解答
第一組給出 ,所以兩個相互競爭的碼字會違反距離條件。第二組給出 ,超出了已證明的保證。保證失效並不是說每個這樣的模式都有歧義;它的意思是該定理無法統一地證明唯一性。
快速檢查
(直接證明一維求值碼的距離為 。若所選的某個求值點為零,為甚麼該結論仍然成立?)
次數小於一的多項式是常數。
解答
次數小於 意味著常數多項式。每個非零常數給出所有 個分量都非零的字,所以其重量與最小距離為 。在 處對非零常數求值並不改變它; 是合法的求值點,不應與零碼元混淆。
關於代數碼族的更廣泛視角,可參見 Guruswami 的關於 Reed–Solomon 及相關碼的編碼理論講義。