如果您曾經發送過簡訊、播放過 CD 或在雲端儲存文件，那麼您就會從糾錯中受益。這個革命性的想法可以追溯到 1940 世紀 XNUMX 年代，當時研究人員首次意識到可以以某種形式重寫任何訊息，以便以後的損壞可以輕鬆逆轉。

多年來，研究人員開發了許多巧妙的方案，稱為糾錯碼，它們以不同的方式對資料進行編碼，並使用不同的程序來修復錯誤。但對於理論計算機科學家來說，很少有比所謂的本地可修正程式碼更引人注目的了。這些代碼具有兩個聽起來幾乎矛盾的同時屬性：任何錯誤都可以透過讀取少數位置的編碼資料來修正，但沒有攻擊者可以透過選擇性地篡改程式碼來挫敗此修正過程。就好像你只需看一眼其他幾頁就可以恢復從書中撕下的任何一頁。

“這是一個非常神奇的現象，” 湯姆古爾，劍橋大學計算機科學家。 “先驗地，這樣的數學對像是否存在根本不明顯。”

但這種魔法的代價是高昂的。唯一已知的本地可修正程式碼的例子效率極低——對任何訊息進行編碼也會使其長度呈指數級增長。以這種方式編碼的整本書太笨重了。

計算機科學家長期以來一直想知道是否可能有更好的本地可校正程式碼。他們特別關注僅使用三個查詢來糾正任何錯誤的程式碼，希望這種嚴格的限制可以使這些程式碼更容易理解。但即使是這個簡單的案例也困擾了研究人員 20 多年。

現在是電腦科學家 普拉韋什·科塔里 卡內基美隆大學教授和他的研究生 彼得·馬諾哈爾 終於有 證明 不可能建立一個三查詢本地可校正程式碼來避免指數成本。這可能是一個負面的結果，但任何澄清糾錯限制的事情都會讓研究人員感到興奮，特別是因為本地可修正程式碼的數學出現在遠離通訊的地區。

“這個結果令人驚訝，” 舒邦吉·薩拉夫，多倫多大學計算機科學家。 “這是一個巨大的突破。”

人多力量大

要了解糾錯，請將您想要保護的資料想像為一系列位元或 0 和 1。在此模型中，錯誤可能是任何不必要的 0 翻轉為 1，反之亦然，無論是由於隨機波動還是故意篡改。

假設您想向朋友發送訊息，但您擔心錯誤可能會改變訊息的含義。一個簡單的策略是將訊息中的每個0 替換為000，將每個1 替換為111。如果您的朋友看到​​訊息的一部分不包含連續的三個相同位，他們就會知道發生了錯誤。如果錯誤是隨機的且相對罕見，那麼任何 110 字串都更有可能是損壞的 111，而不是損壞的 000。每個三元組內的簡單多數投票足以糾正大多數錯誤。

這種方案稱為重複碼，具有簡單的優點，但沒有什麼值得推薦的。一方面，它需要將每個訊息的長度增加兩倍，只是為了處理相對不常見的錯誤，如果很可能出現兩個相鄰的錯誤，我們將需要更多的冗餘。更糟的是，如果錯誤不是隨機的，例如當攻擊者積極嘗試破壞程式碼時，它很快就會變得毫無用處。在重複碼中，修正給定位所需的所有資訊僅儲存在其他幾個位元中，使其容易受到有針對性的攻擊。

幸運的是，許多糾錯碼的表現更好。一個著名的例子叫做 里德-所羅門碼，透過將訊息轉換為多項式來工作——數學表達式，例如 x² + 3x + 2 由不同的項加在一起組成，每個項都有一個變數（例如 x) 提升到不同的冪。使用里德-所羅門碼對訊息進行編碼涉及為訊息中的每個字元建立一個多項式，然後將多項式繪製為圖形上的曲線並儲存位於曲線上的點的座標（至少再取一個）點比字元數）。錯誤可能會將其中一些點推離曲線，但如果錯誤不多，則只有一條多項式曲線會通過大多數點。這條曲線幾乎肯定對應於真實的資訊。

里德-所羅門碼非常有效率——您只需要儲存一些額外的點來糾正錯誤，因此任何編碼的訊息只比原始訊息稍長一些。它們也不太容易受到那種會給重複代碼帶來災難的有針對性的破壞，因為用於糾正任何地方的錯誤的資訊分佈在整個編碼訊息中。

在全球範圍內思考，本地行動

里德-所羅門碼的力量源自於互連性。但正是由於這種相互關聯性，如果不閱讀整個內容，就無法修復編碼訊息中的單一錯誤。在通訊環境中，這聽起來可能不是問題：如果您要發送訊息，您可能希望收件人閱讀全部內容。但這可能是資料儲存中的負擔——這是糾錯的另一個主要應用。

考慮一家將用戶電子郵件儲存在雲端（即儲存在大量伺服器上）的公司。您可以將整個電子郵件集合視為一條長訊息。現在假設一台伺服器崩潰了。使用里德-所羅門程式碼，您需要執行涉及所有編碼資料的大量計算，才能從一台遺失的伺服器還原您的電子郵件。 「你必須審視一切，」他說。 澤夫·德維爾，普林斯頓大學計算機科學家。 “這可能是數十億封電子郵件——可能需要很長時間。”

研究人員使用術語“本地”來描述僅使用編碼訊息的一小部分來實現的代碼。 發現錯誤 或糾正它們。簡單的重複程式碼具有某種本地特徵，但這正是它如此容易被篡改的原因。相較之下，本地可修正的程式碼則兩全其美——它只需幾次查詢即可糾正任何位元的錯誤，而且不會失去使里德-所羅門程式碼具有如此彈性的互連性。

「這是一個非常嚴格的概念，」科塔里說。

局部可修正程式碼最著名的例子是數學家於 1954 年發明的古老糾錯碼的版本 大衛穆勒 和 歐文·里德 （他還幫助開發了里德-所羅門碼）。與 Reed-Solomon 碼一樣，Reed-Muller 碼使用將許多項相加的多項式來對長訊息進行編碼。

里德-所羅門碼中使用的多項式涉及單一變量， x，所以增加更多項目的唯一方法是使用更高的冪 x。這會導致曲線出現許多波動，只能透過查看多個點來確定。相反，Reed-Muller 碼使用多項式，其中每一項可以包含相乘的多個變數。更多的變數意味著更多的組合它們的方法，這反過來又提供了一種增加多項式項數的方法，而無需將任何單一變數提高到如此高的冪。

Reed-Muller 碼非常靈活。您可以透過增加多項式中出現的最高冪、增加變數數量或同時增加兩者來編碼更長的訊息。為了讓 Reed-Muller 碼可在本地修正，您只需將每個變數的最大功率限制為一個小的常數值，並透過僅增加變數的數量來處理更長的訊息。

特別是對於三查詢本地可校正程式碼，最大功率設定為 2。然後就每個單獨的變數而言，編碼訊息的多項式描繪出一條簡單的拋物線。要確定拋物線的確切形狀，您只需檢查曲線的三個點。更重要的是，對於許多變數來說，有許多這樣的拋物線，任何一個都可以用來修正錯誤。這就是 Reed-Muller 碼如此具有彈性的原因。

不幸的是，Reed-Muller 碼有一個嚴重的缺點：編碼訊息所需的位數隨著變數數量呈指數增長。如果您想要一個高度本地化的程式碼，只需少量查詢即可糾正錯誤，那麼您將需要大量變數來儲存長訊息，並且 Reed-Muller 程式碼在實踐中很快就會變得毫無用處。

「在這種情況下，指數非常糟糕，」德維爾說。但這是不可避免的嗎？

可修正或可解碼？

由於電腦科學家試圖找到更有效的本地可修正程式碼但未能成功，他們開始懷疑這種程式碼根本不可能。 2003年，兩位研究人員 證明 只使用兩個查詢是無法擊敗 Reed-Muller 程式碼的。但這只是任何人所能得到的。

「一旦你達到了三個，我們的知識就變得非常粗略，」科塔里說。

下一個突破只會讓事情變得更複雜。在發表於的兩篇論文中 2008 和 2009中，電腦科學家 Sergey Yekhanin 和 Klim Efremenko 展示瞭如何構造比 Reed-Muller 代碼更有效率的三查詢代碼，但這些代碼並不完全可以進行局部修正。相反，它們有一個略有不同的屬性，稱為本地可解碼性。

為了理解其中的差異，讓我們再次想像一個雲端儲存提供者將使用者的資料組合成一條長訊息並使用糾錯程式碼對其進行保護。本地可修正程式碼和本機可解碼程式碼都可以透過幾次查詢來修正原始訊息的任何位元中的錯誤。

但每個糾錯碼還需要原始訊息中沒有的額外位元——這就是為什麼對訊息進行編碼會使其更長。這兩種類型的程式碼在處理這些附加位元的方式上有所不同。本地可解碼代碼不承諾糾正這些位元中的錯誤所需的查詢數量。但在本地可修正的程式碼中，任何額外位元中的錯誤都可以透過與原始訊息中任何位元中的錯誤完全相同的方式進行修復。

“你存儲的所有內容，無論是用戶的原始數據還是冗餘和校驗信息——所有這些都可以在本地進行糾正。” 馬杜蘇丹，哈佛大學電腦科學家。

儘管原則上不同，但本地可糾正性和本地可解碼性在 2008 年之前的實踐中似乎總是可以互換的——每個已知的本地可解碼代碼也都是可本地糾正的。葉哈寧和埃夫雷門科的發現提出了這兩種情況之間存在根本差異的可能性。或者也許可以修改 Yekhanin 和 Efremenko 的程式碼，使其可以在本地修正。這將使這兩個條件再次處於平等地位，但這也意味著研究人員錯誤地認為三查詢本地可修正程式碼的效率有多高。不管怎樣，傳統觀念都必須改變。

借用邏輯

科塔里和馬諾哈爾最終透過採用電腦科學不同領域的一項技術解決了這種緊張局勢：即所謂的約束滿足問題的研究。試圖與一群朋友協調晚餐計劃是一種約束滿足問題。每個人都有他們會接受的選擇和他們會否決的選擇。你的工作是要么找到一個讓每個人都滿意的計劃，要么，如果沒有這樣的計劃，盡快弄清楚。

這兩種可能的結果之間存在著固有的不對稱性。一個可接受的解決方案可能不容易找到，但一旦找到，就很容易說服其他人它會起作用。但即使你知道這個問題確實是“不可滿足的”，也可能沒有一個例子可以提供證明。

2021 年，Kothari 和 Manohar 與加州大學柏克萊分校的 Venkatesan Guruswami 一起做了一項研究 重大突破 在約束滿足問題的研究中，使用新的理論技術來識別那些棘手的不可滿足的情況。他們懷疑新方法也將成為解決其他問題的強大工具，Guruswami 的研究生 Omar Alrabiah 建議他們研究三查詢本地可解碼程式碼。

「可以說，我們手裡拿著的是釘子和錘子，」科塔里說。

Yekhanin 和 Efremenko 的令人驚訝的結果表明，三查詢本地可解碼代碼可能比 Reed-Muller 代碼更有效。但他們的程式碼是否是最好的，或者三查詢本地可解碼程式碼是否可以變得更有效率？ Kothari、Manohar、Guruswami 和 Alrabiah 認為他們的新技術或許能夠證明此類程式碼效率的限制。他們的計劃是建立一個邏輯公式，包含給定大小的所有可能的三查詢本地可解碼代碼的結構，並證明它是不可滿足的，從而表明不存在這樣的代碼。

四位研究人員在 2022 年朝這個方向邁出了第一步，設定了 新限制 關於三查詢本地可解碼程式碼的最大效率。結果遠遠超出了研究人員使用其他技術所能達到的水平，但它並不排除所有比葉哈寧和埃夫雷門科的代碼更有效的代碼。

科塔里和馬諾哈爾懷疑他們可以走得更遠。但進展陷入停滯，直到馬諾哈記下了一個快速的粗略計算，表明該技術對於本地可糾正的程式碼可能比本地可解碼的程式碼更有效。

幾個月後，在經歷了更多的錯誤開始後，他們擔心自己過於樂觀，這項技術終於兌現了它的承諾。 Kothari 和 Manohar 證明，正如研究人員所懷疑的那樣，任何三查詢本地可校正代碼都不可能比 Reed-Muller 代碼表現得更好。指數縮放是一個基本限制。他們的結果也戲劇性地證明了局部可校正性和局部可解碼性雖然表面上相似，但在根本層面上確實存在差異：後者顯然比前者更容易實現。

Kothari 和 Manohar 現在希望擴展他們的技術來研究允許三個以上查詢的程式碼，因為現在人們對它們知之甚少。糾錯理論的進展往往會對其他看似不相關的領域產生影響。特別是，本地可修正的程式碼隨處可見，因為以下問題 私人資料庫搜尋 在密碼學中的證明 組合數學定理。現在說科塔里和馬諾哈爾的技術將如何影響這些不同領域還為時過早，但研究人員感到樂觀。

「這裡有一個非常漂亮的新想法，」德維爾說。 “我認為有很大的潛力。”