错误检测与纠正

歷史

錯誤糾正編碼的現代發展在1947年由理察·衛斯里·漢明帶來。漢明碼的描述出現於克勞德·夏農的《通訊的數學理論》一書中，並由Marcel J. E. Golay迅速推廣。

引入

實現錯誤檢測和糾正的一般思路是添加一些資訊冗餘（例如一些額外資料）到訊息，從而使接收器可以用它來檢查訊息的一致性，並恢復被確定為損壞的資料。錯誤檢測和糾正的方案可以是系統性或非系統性：在系統性方案中，發射機傳送原始資料，並且附加其通過一些確定性演算法從資料位元匯出的固定數量的校驗位（或奇偶校驗資料）。如果僅需要錯誤檢測，則接收器可以簡單對接收到的資料位應用相同的演算法，並將其輸出與接收到的校驗位進行比較。如果值不符合，則傳輸期間的某個點位發生錯誤。在非系統性的編碼系統中，原始訊息被變換與原始訊息相等或更長位元的被編碼訊息。
良好的錯誤控制效能需要基於通訊通道的特性來選擇方案。常見的通道模型包括無記憶模型，其中錯誤以一定概率隨機發生，以及錯誤主要突發出現的動態模型。因此，錯誤檢測與糾正編碼通常可分為：隨機錯誤檢測/糾正與突發錯誤檢測/糾正。一些編碼是同時適用隨機錯誤與突發錯誤的混合體。
如果通道容量不能被確定，或者高度可變，錯誤檢測方案可以與重傳出錯資料的系統組合。這也稱之為自動重傳請求（ARQ），它在網際網路中極為常用。用於替代錯誤控制的一種方案是混合式自動重送請求（HARQ），它是ARQ與錯誤糾正編碼的組合。

錯誤檢測方案

錯誤檢測通常使用適合的雜湊函式（或校驗和 演算法）實現。雜湊演算法添加定長的標籤到訊息，從而使接收者能通過計算標籤並與所提供的標籤比較來驗證傳遞的訊息。
雜湊函式存在多種多樣的設計。其中一部分因其簡單性或適合檢測某些類型的錯誤（例如循環冗餘校驗的效能優勢  為檢測突發錯誤而使用）而被廣泛使用。
一個隨機前向錯誤更正  基於最小距離編碼的可以對可檢測誤差的數量提供嚴格保證，但它可能不能防禦原像攻擊。下面章節中描述的重複編碼就是錯誤更正碼的一種特殊案例。雖然相當低效，但由於其簡單性，重複編碼適合部分糾錯與檢測的應用。

重複編碼

重複編碼是在通道上重複位元資訊以實現無差錯通訊的編碼方案。首先將要傳送的資料流劃分為位元塊，然後將每個傳輸預定的次數。例如，要傳送位元「1011」，四位元塊{{what}}則再重複三次而產生「1011 1011 1011」。但是，如果此例中收到12位元資訊為「1010 1011 1011」，其中第一個塊不同於其他兩個，則可以確定已經發生錯誤。
重複編碼非常低效，並且如果錯誤在每個組的完全相同的地方發生，則很容易出現問題（例如上例中正巧錯誤為「1010 1010 1010」，將被檢測為傳輸無誤）。重複編碼的優點是它非常簡單，並實際上用於某些數位電台的傳輸。

奇偶校驗位

奇偶校驗位（parity bit）是一種非常簡單的方案，可以用於檢測任何奇數個錯誤的發生。但如果發生的錯誤數量為偶數，則奇偶效驗位看上去是正確的。
對奇偶效驗位的擴充和改變有縱向冗餘校驗、垂直冗餘檢查，以及雙或對角奇偶（在RAID-DP中使用）。

校驗和

訊息的校驗和是固定字長（例如位元組值）的位元組碼的模算數和。和可能在傳輸前用一補數以檢測全零訊息出現的錯誤。
校驗和方案包括奇偶校驗位、校驗碼和縱向冗餘校驗。部分校驗和方案如Damm演算法、Luhn演算法和Verhoeff演算法在設計上是專門用於檢測人類書寫或記錄數位時常出現的錯誤。

迴圈冗餘校驗（CRC）

迴圈冗餘校驗（CRC）是一個非安全的雜湊函式，旨在檢測電腦網路中數位資料的意外變化。因此，它不適合檢測惡意引入的錯誤。
迴圈碼有著非常適合檢測突發錯誤的有利特性。CRC尤其容易在硬體中實現，並且因此常用在數位網路和諸如硬碟等儲存裝置中。
奇偶校驗是迴圈冗餘校驗的特殊案例，其中單位元CRC由除數x + 1生成。

加密雜湊函式

加密雜湊函式的輸出也稱訊息摘要，它可以提供強力的資料完整性保證，無論資料改變是偶然（例如由於傳輸錯誤）還是被惡意引入。對資料的任何修改都可用檢測雜湊值是否符合判斷。此外，指出某些雜湊值並找到產生相同雜湊值的另一組輸入資料（原輸入資料除外）一般是不可行的。如果攻擊者不僅能改變訊息，還可以改變雜湊值，那麼含金鑰雜湊或或訊息鑑別碼（MAC）可用於提供額外的安全性（即金鑰雜湊訊息鑑別碼）。在不了解金鑰的情況下，攻擊者不可能計算出結果正確的含金鑰雜湊值。

錯誤糾正碼

任何錯誤糾正碼都可用於錯誤檢測。最小漢明距離為d的編碼在碼字中最多可以檢測出d − 1個錯誤。如果對要檢測的最小錯誤數量有嚴格限制，使用基於最小距離的錯誤更正碼進行錯誤檢測則很合適。
最小漢明距離d = 2的編碼是錯誤更正碼的退化情況，並可用於檢測單個錯誤。奇偶校驗位是單錯誤檢測的一個例子。

自動重傳請求（ARQ）

自動重傳請求（ARQ）是通過錯誤檢測碼、確認或否決訊息，以及可靠訊息資料傳輸的訊息超時來完成資料傳輸的一種錯誤控制方法。確認訊息是由接收方傳送，以表明其已正確接收資料框。
通常來說，當傳送方沒有在超時發生前（即傳送資料框之後的合理時間內）接收到確認，則它將重傳該影格，直到該影格被正確接收，或者該錯誤反覆存在而超過預定的重傳次數。
ARQ協定的三種類型是停止並等待ARQ、後退N影格ARQ和選擇重傳ARQ。
如果通訊通道具有變化或未知的容量，例如在網際網路，則ARQ適宜使用。但是，ARQ需要一個反向通道可用，這使重傳可能增加延遲，並且需要維護用於重傳的緩衝區和計時器，這在擁塞控制的情況下可對伺服器和整體網路容量造成壓力。
舉例來說，ARQ在短波無線電資料鏈路中的應用為ARQ-E，結合復用為ARQ-M。

應用程式

需要低延遲的應用程式（如電話通話）不能使用ARQ；它們必須使用前向錯誤更正（FEC）。在此類應用中，當ARQ系統發現錯誤及重新請求和完成傳送，重新傳送的資料到達之時對於此類應用已然太遲以至沒有任何作用。
傳送方在傳送後立即忘記資訊的應用（例如大多數網路攝影機）不能使用ARQ；它們必須使用FEC，因為當發現錯誤時，原始資料已不再可用。（這也是為什麼FEC被用於RAID、分散式檔案系統等資料儲存系統）。
使用ARQ的應用程式必須有一個返回通道；沒有返回通道的應用程式不能使用ARQ。需要極低錯誤率的應用程式（如數位貨幣轉移）必須使用ARQ。可靠性和檢驗工程也利用了錯誤更正碼的理論。

深空通訊

由於訊號功率在星際距離上的極度稀釋，以及太空探測器上有限的可用功率，錯誤更正碼的開發與深空任務的歷史緊密相關。在早期任務中，傳送資料未被編碼，而從1968年開始，則以（子最佳解碼）卷積碼和里德-穆勒碼的形式實現數位糾錯。里德-穆勒碼非常適合於太空飛行器所受雜訊（大致符合鐘形曲線），並在1969年至1977年期間在水手太空飛行器上執行任務。
在自1977年開始的旅行者1號和旅行者2號任務中，設計包括在木星和土星的科學資訊中提供彩色成像。這使得編碼的要求增加，因此太空飛行器得到了可以級聯外部Golay (24,12,8)碼的卷積碼（最佳Viterbi解碼器）的支援。
旅行者2號探測器也添加了一種里德-所羅門碼的支援：串聯的里德-所羅門-維特比（RSV）碼允許非常強效的錯誤糾正，並使太空飛行器的旅程延長到天王星和海王星。兩個探測器在1989年ECC系統更新後使用V2 RSV編碼。
CCSDS目前建議至少使用效能類似於Voyager 2 RSV程式碼的錯誤更正碼。串聯碼日已失去了空間任務的青睞，並正被更強大的編碼所取代，例如Turbo碼或低密度奇偶檢查碼。
不同種類的深空和軌道任務表明，試圖找到一個「萬能」的糾錯系統將是一段時間以來一個持續的問題。對於接近地球的任務，通道雜訊的性質與星際任務中的宇宙飛船經歷並不相同。此外，隨著太空飛行器與地球距離的增加，校正雜訊的問題也日益嚴重。

資料儲存

錯誤檢測和糾正碼經常被用於提供資料儲存媒介的可靠性。第一例是1951年在磁帶資料儲存上的「奇數軌道」。用於封包程式碼記錄磁帶的「最佳矩形程式碼」不僅能檢測，還能校正單位元錯誤。部分檔案格式，尤其是歸檔格式，包含一個校驗和（通常以CRC32提供）以檢測損壞與截斷，並可以採用冗餘和/或奇偶效驗檔案來恢復損壞部分的資料。里德-所羅門碼就被用於光碟中，以糾正由劃痕引起的錯誤。
現代的硬碟機使用CRC程式碼來檢測和里德-所羅門碼校正磁區讀取中的較小錯誤，以及從「損壞」的磁區恢復資料並將該資料儲存在備用磁區中。RAID系統使用各種糾錯技術來糾正硬碟機出現完全故障時導致的錯誤。諸如ZFS或Btrfs等檔案系統以及部分RAID實現支援資料擦洗和彈性，這允許在使用之前檢測並希望恢復壞塊。恢復的資料可能被重寫到完全相同的物理位置，以備在同一硬體上的另一處壞塊，或者替換硬體。

錯誤糾正記憶體

動態隨機存取記憶體（DRAM）記憶體可以採用錯誤更正碼提供對軟性錯誤的增強保護。諸如糾錯記憶體（也稱ECC或'EDAC保護記憶體）就是一種面向高容錯應用提供的記憶體，它適合伺服器以及要經受宇宙線增加考驗的深空應用。
錯誤糾正記憶體的控制器通常使用漢明碼，也有些使用三重冗餘模組。
交織允許通過將相鄰位與不同的字相關聯來分散單個宇宙射線對多個物理相鄰位的潛在破壞。只要一次單粒子翻轉在特定期間內不超過錯誤閾值（例如：單位元錯誤），它就可以被糾正（例如通過單位元錯誤更正碼），並使儲存系統維持在無錯誤的狀態。
除了通過ECC記憶體硬體提供此項特性外，作業系統通常也包含相關的報告措施，用以在軟錯誤被透明恢復時提供通知。軟錯誤的增加率可能預示著DIMM模組需要被更換，但在沒有相關手段的情況下，此類報告資訊不容易取得。例如，Linux核心的EDAC子系統（以前稱為bluesmoke）會在啟用錯誤檢查的電腦系統內部收集資料；除了收集和報告與ECC記憶體相關的事件外，它還支援其他校驗和錯誤，包括在PCI匯流排上檢測到的錯誤。
有幾個系統也支援記憶體刷洗。