錯誤檢測與糾正

在計算機科學和通訊的資訊理論和編碼理論應用中，錯誤檢測和糾正是在不可靠的通訊通道上可靠地傳送數字資料的技術。許多通訊通道會經受通道噪聲，因此可能在源至接收器的傳輸期間引入錯誤。錯誤檢測技術能夠檢測這樣的錯誤，而錯誤糾正能在不少情況下重建原始資料。定義.該術語的一般定義如下：歷史.錯誤糾正編碼的現代發展在1947年由理查德·衛斯里·漢明帶來。漢明碼的描述出現於克勞德·夏農的《通訊的數學理論》一書中，並由迅速推廣。引入.實現錯誤檢測和糾正的一般思路是新增一些資訊冗餘。如果僅需要錯誤檢測，則接收器可以簡單對接收到的資料位應用相同的演算法，並將其輸出與接收到的校驗位進行比較。如果值不匹配，則傳輸期間的某個點位發生錯誤。在非系統性的編碼系統中，原始訊息被變換與原始訊息相等或更長位元的被編碼訊息。良好的錯誤控制性能需要基於通訊通道的特性來選擇方案。常見的通道模型包括無記憶模型，其中錯誤以一定機率隨機發生，以及錯誤主要出現的動態模型。因此，錯誤檢測與糾正編碼通常可分為：隨機錯誤檢測/糾正與突發錯誤檢測/糾正。一些編碼是同時適用隨機錯誤與突發錯誤的混合體。如果通道容量不能被確定，或者高度可變，錯誤檢測方案可以與重傳出錯資料的系統組合。這也稱之為自動重傳請求，它是ARQ與錯誤糾正編碼的組合。實現.錯誤糾正通常可以用兩種方式實現：ARQ與FEC可以組合，使得不需重傳就糾正微小錯誤，並經由重傳請求校正大的錯誤，這被稱為混合式自動重送請求。錯誤檢測方案.錯誤檢測通常使用適合的雜湊函式實現。雜湊演算法新增定長的"標籤"到訊息，從而使接收者能透過計算標籤並與所提供的標籤比較來驗證傳遞的訊息。雜湊函式存在多種多樣的設計。其中一部分因其簡單性或適合檢測某些型別的錯誤而被廣泛使用。一個隨機前向錯誤更正 基於最小距離編碼的可以對可檢測誤差的數量提供嚴格保證，但它可能不能防禦原像攻擊。下面章節中描述的重複編碼就是糾錯碼的一種特殊案例。雖然相當低效，但由於其簡單性，重複編碼適合部分糾錯與檢測的應用。重複編碼.重複編碼是在通道上重複位元資訊以實現無差錯通訊的編碼方案。首先將要傳送的資料流劃分為位元塊，然後將每個傳輸預定的次數。例如，要傳送位元“1011”，四位元塊則再重複三次而產生“1011 1011 1011”。但是，如果此例中收到12位元資訊為“1010 1011 1011”，其中第一個塊不同於其他兩個，則可以確定已經發生錯誤。重複編碼非常低效，並且如果錯誤在每個組的完全相同的地方發生，則很容易出現問題。重複編碼的優點是它非常簡單，並實際上用於某些數字電臺的傳輸。奇偶校驗位.奇偶校驗位是一種非常簡單的方案，可以用於檢測任何奇數個錯誤的發生。但如果發生的錯誤數量為偶數，則奇偶效驗位看上去是正確的。對奇偶效驗位的擴充套件和改變有縱向冗餘校驗、，以及雙或對角奇偶。校驗和.訊息的校驗和是固定字長的位元組碼的模算數和。和可能在傳輸前用一補數以檢測全零訊息出現的錯誤。校驗和方案包括奇偶校驗位、校驗碼和縱向冗餘校驗。部分校驗和方案如、Luhn演算法和在設計上是專門用於檢測人類書寫或記錄數字時常出現的錯誤。迴圈冗餘校驗.迴圈冗餘校驗是一個非安全的雜湊函式，旨在檢測計算機網路中數字資料的意外變化。因此，它不適合檢測惡意引入的錯誤。迴圈碼有著非常適合檢測的有利特性。CRC尤其容易在硬體中實現，並且因此常用在數字網路和諸如硬碟等儲存裝置中。奇偶校驗是迴圈冗餘校驗的特殊案例，其中單位元CRC由除數x + 1生成。加密雜湊函式.加密雜湊函式的輸出也稱訊息摘要，它可以提供強力的資料完整性保證，無論資料改變是偶然。在不瞭解金鑰的情況下，攻擊者不可能計算出結果正確的含金鑰雜湊值。錯誤糾正碼.任何錯誤糾正碼都可用於錯誤檢測。最小漢明距離為d的編碼在碼字中最多可以檢測出d − 1個錯誤。如果對要檢測的最小錯誤數量有嚴格限制，使用基於最小距離的糾錯碼進行錯誤檢測則很合適。最小漢明距離d = 2的編碼是糾錯碼的退化情況，並可用於檢測單個錯誤。奇偶校驗位是單錯誤檢測的一個例子。錯誤糾正.自動重傳請求.自動重傳請求是透過錯誤檢測碼、確認或否決訊息，以及可靠訊息資料傳輸的訊息來完成資料傳輸的一種錯誤控制方法。確認訊息是由接收方傳送，以表明其已正確接收資料幀。通常來說，當傳送方沒有在超時發生前接收到確認，則它將重傳該幀，直到該幀被正確接收，或者該錯誤反覆存在而超過預定的重傳次數。ARQ協議的三種類型是、和選擇重傳ARQ。如果通訊通道具有變化或未知的容量，例如在網際網路，則ARQ適宜使用。但是，ARQ需要一個可用，這使重傳可能增加延遲，並且需要維護用於重傳的緩衝器和計時器，這在擁塞控制的情況下可對伺服器和整體網路容量造成壓力。舉例來說，ARQ在短波無線電資料鏈路中的應用為，結合複用為。糾錯碼.前向錯誤更正。因為接收方不必要求傳送方重傳資料，在前向糾錯中不需要，並因此適合諸如廣播等。糾錯碼經常用於底層通訊，以及用於諸如CD、DVD、硬碟和RAM等介質中的可靠儲存。糾錯碼經常區分為卷積碼與分組碼：夏農定理是前向糾錯的一個重要定理，並且描述了在具有特定錯誤機率或信噪比的通道上可進行可靠通訊的最大資訊速率。這個嚴格的上限以通道容量表示。所允許的實際最大位元速率取決於所使用的糾錯碼，並可能更低。這是因為夏農的證明只是存在性的，並沒有顯示如何構建程式碼是為最優並具有高效的編碼和解碼演算法。混合方案.混合式自動重送請求是ARQ與前向糾錯的組合。有兩種基本方法：後一種方法在上使用噴泉碼時尤為有吸引力。應用程式.需要低延遲的應用程式。在此類應用中，當ARQ系統發現錯誤及重新請求和完成傳送，重新發送的資料到達之時對於此類應用已然太遲以至沒有任何作用。傳送方在傳送後立即忘記資訊的應用。使用ARQ的應用程式必須有一個；沒有返回通道的應用程式不能使用ARQ。需要極低錯誤率的應用程式必須使用ARQ。可靠性和檢驗工程也利用了糾錯碼的理論。網際網路.在典型的TCP/IP棧中，錯誤控制在多個層級施行：深空通訊.由於訊號功率在星際距離上的極度稀釋，以及空間探測器上有限的可用功率，糾錯碼的開發與深空任務的歷史緊密相關。在早期任務中，傳送資料未被編碼，而從1968年開始，則以，並在1969年至1977年期間在水手航天器上執行任務。在自1977年開始的旅行者1號和旅行者2號任務中，設計包括在木星和土星的科學資訊中提供彩色成像。這使得編碼的要求增加，因此航天器得到了可以級聯外部的卷積碼的支援。旅行者2號探測器也添加了一種裡德-所羅門碼的支援：串聯的裡德-所羅門-維特比碼允許非常強效的錯誤糾正，並使航天器的旅程延長到天王星和海王星。兩個探測器在1989年ECC系統升級後使用V2 RSV編碼。目前建議至少使用效能類似於Voyager 2 RSV程式碼的糾錯碼。串聯碼日已失去了空間任務的青睞，並正被更強大的編碼所取代，例如Turbo碼或低密度奇偶檢查碼。不同種類的深空和軌道任務表明，試圖找到一個“萬能”的糾錯系統將是一段時間以來一個持續的問題。對於接近地球的任務，通道雜訊的性質與星際任務中的宇宙飛船經歷並不相同。此外，隨著航天器與地球距離的增加，校正噪聲的問題也日益嚴重。衛星廣播.受到提供電視節目速率決定。概述資料儲存.錯誤檢測和糾正碼經常被用於提供資料儲存介質的可靠性。#重定向現代的硬碟驅動器使用CRC程式碼來檢測和裡德-所羅門碼校正扇區讀取中的較小錯誤，以及從“損壞”的扇區恢復資料並將該資料儲存在備用扇區中。RAID系統使用各種糾錯技術來糾正硬碟驅動器出現完全故障時導致的錯誤。諸如ZFS或Btrfs等檔案系統以及部分RAID實現支援和彈性，這允許在使用之前檢測並希望恢復壞塊。恢復的資料可能被重寫到完全相同的物理位置，以備在同一硬體上的另一處壞塊，或者替換硬體。錯誤糾正記憶體.動態隨機存取儲存器就是一種面向高容錯應用提供的記憶體，它適合伺服器以及要經受宇宙線增加考驗的深空應用。錯誤糾正儲存器的控制器通常使用漢明碼，也有些使用三重冗餘模組。交織允許透過將相鄰位與不同的字相關聯來分散單個宇宙射線對多個物理相鄰位的潛在破壞。只要一次單粒子翻轉在特定期間內不超過錯誤閾值，並使儲存系統維持在無錯誤的狀態。除了透過ECC記憶體硬體提供此項特性外，作業系統通常也包含相關的報告措施，用以在軟錯誤被透明恢復時提供通知。軟錯誤的增加率可能預示著DIMM模組需要被更換，但在沒有相關手段的情況下，此類報告資訊不容易取得。例如，Linux核心的EDAC子系統會在啟用錯誤檢查的計算機系統內部收集資料；除了收集和報告與ECC記憶體相關的事件外，它還支援其他校驗和錯誤，包括在PCI總線上檢測到的錯誤。有幾個系統也支援記憶體刷洗。