錯誤檢測與糾正
 | 此條目翻譯自其他語言維基百科，需要相關領域的編者協助校對翻譯。 |
在計算機科學和通信的信息論和編碼理論應用中，錯誤檢測和糾正（英語：error detection and correction）或錯誤控制（error control）是在不可靠的通信信道上可靠地傳送數字數據的技術。許多通信信道會經受信道噪聲，因此可能在源至接收器的傳輸期間引入錯誤。錯誤檢測技術能夠檢測這樣的錯誤，而錯誤糾正能在不少情況下重建原始數據。
定義
[編輯]該術語的一般定義如下：
- 錯誤檢測是檢測發射機到接收機的傳輸期間由噪聲或其他原因所致的錯誤。
- 錯誤糾正是檢測錯誤並重建無錯誤的原樣數據。
歷史
[編輯]錯誤糾正編碼的現代發展在1947年由理查德·衛斯里·漢明帶來。[1]漢明碼的描述出現於克勞德·香農的《通信的數學理論》一書中[2]，並由Marcel J. E. Golay迅速推廣。[3]
引入
[編輯]實現錯誤檢測和糾正的一般思路是添加一些信息冗餘（例如一些額外數據）到消息，從而使接收器可以用它來檢查消息的一致性，並恢復被確定為損壞的數據。錯誤檢測和糾正的方案可以是系統性或非系統性：在系統性方案中，發射機發送原始數據，並且附加其通過一些確定性算法從數據位元導出的固定數量的校驗位（或奇偶校驗數據）。如果僅需要錯誤檢測，則接收器可以簡單對接收到的數據位應用相同的算法，並將其輸出與接收到的校驗位進行比較。如果值不匹配，則傳輸期間的某個點位發生錯誤。在非系統性的編碼系統中，原始消息被變換與原始消息相等或更長位元的被編碼消息。
良好的錯誤控制性能需要基於通信信道的特性來選擇方案。常見的信道模型包括無記憶模型，其中錯誤以一定概率隨機發生，以及錯誤主要突發出現的動態模型。因此，錯誤檢測與糾正編碼通常可分為：隨機錯誤檢測/糾正與突發錯誤檢測/糾正。一些編碼是同時適用隨機錯誤與突發錯誤的混合體。
如果信道容量不能被確定，或者高度可變，錯誤檢測方案可以與重傳出錯數據的系統組合。這也稱之為自動重傳請求（ARQ），它在互聯網中極為常用。用於替代錯誤控制的一種方案是混合式自動重送請求（HARQ），它是ARQ與錯誤糾正編碼的組合。
實現
[編輯]錯誤糾正通常可以用兩種方式實現：
- 自動重傳請求（ARQ），有時也稱後向糾錯：這是一種錯誤控制技術，其中將錯誤檢測方案與重傳錯誤數據的請求組合。其中使用錯誤檢測代碼檢查接收的每個數據塊，如果檢查失敗則請求重傳數據——這可以被重複進行，直至數據可通過驗證。
- 前向錯誤更正（FEC）：發送者在傳輸前使用糾錯碼（ECC）對數據進行編碼。額外信息（信息冗餘）由代碼添加以供接收者用來恢復原始數據。一般來說，重建的數據被認為是「最有可能」的原始數據。
ARQ與FEC可以組合，使得不需重傳就糾正微小錯誤，並經由重傳請求校正大的錯誤，這被稱為混合式自動重送請求（HARQ）。
錯誤檢測方案
[編輯]錯誤檢測通常使用適合的散列函數（或校驗和 算法）實現。散列算法添加定長的標籤到消息，從而使接收者能通過計算標籤並與所提供的標籤比較來驗證傳遞的消息。
散列函數存在多種多樣的設計。其中一部分因其簡單性或適合檢測某些類型的錯誤（例如循環冗餘校驗的性能優勢 為檢測突發錯誤而使用）而被廣泛使用。
一個隨機前向錯誤更正 基於最小距離編碼的可以對可檢測誤差的數量提供嚴格保證，但它可能不能防禦原像攻擊。下面章節中描述的重複編碼就是糾錯碼的一種特殊案例。雖然相當低效，但由於其簡單性，重複編碼適合部分糾錯與檢測的應用。
重複編碼
[編輯]重複編碼是在信道上重複比特信息以實現無差錯通信的編碼方案。首先將要發送的數據流劃分為比特塊，然後將每個傳輸預定的次數。例如，要發送位元「1011」，四位元塊{{what}}則再重複三次而產生「1011 1011 1011」。但是，如果此例中收到12位元信息為「1010 1011 1011」，其中第一個塊不同於其他兩個，則可以確定已經發生錯誤。
重複編碼非常低效，並且如果錯誤在每個組的完全相同的地方發生，則很容易出現問題（例如上例中正巧錯誤為「1010 1010 1010」，將被檢測為傳輸無誤）。重複編碼的優點是它非常簡單，並實際上用於某些數字電台的傳輸。[4][5]
奇偶校驗位
[編輯]奇偶校驗位（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需要一個反向信道可用，這使重傳可能增加延遲，並且需要維護用於重傳的緩衝器和計時器，這在擁塞控制的情況下可對服務器和整體網絡容量造成壓力。[6]
舉例來說，ARQ在短波無線電數據鏈路中的應用為ARQ-E，結合復用為ARQ-M。
糾錯碼（ECC）
[編輯]前向錯誤更正（ECC）或前向糾錯（FEC）碼是一種添加信息冗餘數據或奇偶校驗數據到消息的過程，使得即使在傳輸或存儲中發生多個錯誤，接收方也可以用它恢復（不能超過編碼本身的能力限制）。因為接收方不必要求發送方重傳數據，在前向糾錯中不需要反向信道，並因此適合諸如廣播等單邊通信。糾錯碼經常用於底層通信，以及用於諸如CD、DVD、硬盤和RAM等媒介中的可靠存儲。
- 卷積碼是逐位元處理。它特別適合於硬件，並且Viterbi解碼器允許譯碼方法。
- 分組碼是以逐塊為基礎。分組碼的早期例子有重複碼、漢明碼和多維奇偶校驗碼。在它們之後是一些更有效的代碼，里德-所羅門碼因為其最顯着所以目前被廣泛使用。Turbo碼和低密度奇偶檢查碼（LDPC）相對較新的方法，可以提供幾乎最佳的效率。
香農定理是前向糾錯的一個重要定理，並且描述了在具有特定錯誤概率或信噪比（SNR）的信道上可進行可靠通信的最大信息速率。這個嚴格的上限以信道容量表示。
所允許的實際最大碼率取決於所使用的糾錯碼，並可能更低。這是因為香農的證明只是存在性的，並沒有顯示如何構建代碼是為最優並具有高效的編碼和解碼算法。
混合方案
[編輯]混合式自動重送請求是ARQ與前向糾錯的組合。有兩種基本方法：[6]
- 消息始終與FEC奇偶校驗數據（和錯誤檢測冗餘）一起發送。接收機使用奇偶校驗信息解碼消息，並僅在奇偶校驗數據不足以成功解碼（通過失敗的完整性校驗來識別）時才使用ARQ請求重傳。
- 消息在沒有奇偶校驗數據的情況下傳輸（僅具有錯誤檢測信息）。如果接收方檢測到錯誤，則其使用ARQ向發送方請求FEC信息，然後用它來重建原始消息。
應用程序
[編輯]需要低延遲的應用程序（如電話通話）不能使用ARQ；它們必須使用前向錯誤更正（FEC）。在此類應用中，當ARQ系統發現錯誤及重新請求和完成發送，重新發送的數據到達之時對於此類應用已然太遲以至沒有任何作用。
發送方在發送後立即忘記信息的應用（例如大多數攝像頭）不能使用ARQ；它們必須使用FEC，因為當發現錯誤時，原始數據已不再可用。（這也是為什麼FEC被用於RAID、分散式檔案系統等數據存儲系統）。
使用ARQ的應用程序必須有一個返回信道；沒有返回信道的應用程序不能使用ARQ。需要極低錯誤率的應用程序（如數字貨幣轉移）必須使用ARQ。可靠性和檢驗工程也利用了糾錯碼的理論。[7]
互聯網
[編輯]在典型的TCP/IP棧中，錯誤控制在多個層級施行：
- 每個以太網幀攜帶一個CRC-32校驗和。接收到校驗和不正確的幀將由接收器硬件丟棄。
- IPv4報頭包含保護頭內容的校驗和。不正確校驗和的網路封包將在網絡或接收處丟棄。
- IPv6報頭中省略了校驗和，以最小化網絡路由的處理成本，並也假設當前的鏈路層技術足以提供足夠的錯誤檢測（另見RFC 3819）。
- UDP具有覆蓋有效載荷和來自UDP和IP報頭尋址信息的可選校驗和。有不正確校驗和的數據包將被操作系統協議棧丟棄。校驗和僅在IPv4下可選，因為數據鏈路層的校驗和可能已提供了所期望的錯誤保護。
- TCP提供用於保護有效載荷和來自TCP和IP報頭尋址信息的校驗和。有不正確校驗和的數據包將在網絡堆棧中被丟棄，並最終使用ARQ進行重傳，可能顯式（例如通過三重ack）或因超時而隱含。
深空通信
[編輯]由於信號功率在星際距離上的極度稀釋，以及空間探測器上有限的可用功率，糾錯碼的開發與深空任務的歷史緊密相關。在早期任務中，發送數據未被編碼，而從1968年開始，則以（子最優解碼）卷積碼和里德-穆勒碼的形式實現數字糾錯。[8]里德-穆勒碼非常適合於航天器所受噪聲（大致匹配鐘形曲線），並在1969年至1977年期間在水手航天器上執行任務。
在自1977年開始的旅行者1號和旅行者2號任務中，設計包括在木星和土星的科學信息中提供彩色成像。[9]這使得編碼的要求增加，因此航天器得到了可以級聯外部Golay (24,12,8)碼的卷積碼（最優Viterbi解碼器）的支持。
旅行者2號探測器也添加了一種里德-所羅門碼的支持：串聯的里德-所羅門-維特比（RSV）碼允許非常強效的錯誤糾正，並使航天器的旅程延長到天王星和海王星。兩個探測器在1989年ECC系統升級後使用V2 RSV編碼。
CCSDS目前建議至少使用性能類似於Voyager 2 RSV代碼的糾錯碼。串聯碼日已失去了空間任務的青睞，並正被更強大的編碼所取代，例如Turbo碼或低密度奇偶檢查碼。
不同種類的深空和軌道任務表明，試圖找到一個「萬能」的糾錯系統將是一段時間以來一個持續的問題。對於接近地球的任務，信道雜訊的性質與星際任務中的宇宙飛船經歷並不相同。此外，隨着航天器與地球距離的增加，校正噪聲的問題也日益嚴重。
衛星廣播（DVB）
[編輯]受到提供電視節目（包括提供新頻道和高清晰度電視）和IP數據需求的推動，衛星轉發器帶寬需求持續增長。轉發器的可用性和帶寬限制限制了這種增長，因為轉發器的容量是由所選擇的調變模式和前向錯誤更正（FEC）速率決定。
概述
- QPSK加上傳統的里德·所羅門和維特比碼已經為提供數字衛星電視使用了近20年。
- 高階調製方案如8PSK、16QAM和32QAM已使衛星工業將轉發器效率提高了幾個數量級。
- 這種應答器中信息速率的增加以犧牲載波功率的代碼以滿足現有天線的閾值要求。[需要解釋]
- 使用最新芯片組進行的測試表明，使用Turbo碼實現的性能可能甚至低於早期設計中假定的0.8 dB。
數據存儲
[編輯]錯誤檢測和糾正碼經常被用於提供數據存儲媒介的可靠性。[來源請求]第一例是1951年在磁帶數據存儲上的「奇數軌道」。用於分組代碼記錄磁帶的「最佳矩形代碼」不僅能檢測，還能校正單位元錯誤。部分檔案格式，尤其是歸檔格式，包含一個校驗和（通常以CRC32提供）以檢測損壞與截斷，並可以採用冗餘和/或奇偶效驗文件來恢復損壞部分的數據。里德-所羅門碼就被用於光盤中，以糾正由劃痕引起的錯誤。
現代的硬盤驅動器使用CRC代碼來檢測和里德-所羅門碼校正扇區讀取中的較小錯誤，以及從「損壞」的扇區恢復數據並將該數據存儲在備用扇區中。[10]RAID系統使用各種糾錯技術來糾正硬盤驅動器出現完全故障時導致的錯誤。諸如ZFS或Btrfs等文件系統以及部分RAID實現支持數據擦洗和彈性，這允許在使用之前檢測並希望恢復壞塊。恢復的數據可能被重寫到完全相同的物理位置，以備在同一硬件上的另一處壞塊，或者替換硬件。
錯誤糾正內存
[編輯]動態隨機存取存儲器（DRAM）內存可以採用糾錯碼提供對軟性錯誤的增強保護。諸如糾錯內存（也稱ECC或'EDAC保護內存）就是一種面向高容錯應用提供的內存，它適合服務器以及要經受宇宙線增加考驗的深空應用。
錯誤糾正存儲器的控制器通常使用漢明碼，也有些使用三重冗餘模塊。
交織允許通過將相鄰位與不同的字相關聯來分散單個宇宙射線對多個物理相鄰位的潛在破壞。只要一次單粒子翻轉在特定期間內不超過錯誤閾值（例如：單比特錯誤），它就可以被糾正（例如通過單比特糾錯碼），並使存儲系統維持在無錯誤的狀態。[11]
除了通過ECC內存硬件提供此項特性外，操作系統通常也包含相關的報告措施，用以在軟錯誤被透明恢復時提供通知。軟錯誤的增加率可能預示着DIMM模塊需要被更換，但在沒有相關手段的情況下，此類報告信息不容易取得。例如，Linux內核的EDAC子系統（以前稱為bluesmoke）會在啟用錯誤檢查的計算機系統內部收集數據；除了收集和報告與ECC內存相關的事件外，它還支持其他校驗和錯誤，包括在PCI總線上檢測到的錯誤。[12][13][14]
有幾個系統也支持內存刷洗。
參見
[編輯]參考資料
[編輯]- ^ Thompson, Thomas M., From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America: vii, 1983, ISBN 0-88385-023-0
- ^ Shannon, C.E., A Mathematical Theory of Communication, Bell System Tech. Journal (p. 418), 1948, 27
- ^ Golay, Marcel J. E., Notes on Digital Coding, Proc.I.R.E. (I.E.E.E.) (p. 657), 1949, 37
- ^ Frank van Gerwen. Numbers (and other mysterious) stations. [12 March 2012]. （原始內容存檔於2017-07-12）.
- ^ Gary Cutlack. Mysterious Russian ‘Numbers Station’ Changes Broadcast After 20 Years. Gizmodo. 2010-08-25 [12 March 2012]. （原始內容存檔於2017-07-05）.
- ^ 6.0 6.1 A. J. McAuley, Reliable Broadband Communication Using a Burst Erasure Correcting Code, ACM SIGCOMM, 1990.
- ^ Ben-Gal I.; Herer Y.; Raz T. Self-correcting inspection procedure under inspection errors (PDF). IIE Transactions on Quality and Reliability, 34(6), pp. 529-540. 2003 [2017-03-16]. （原始內容 (PDF)存檔於2013-10-13）.
- ^ K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.
- ^ Huffman, William Cary; Pless, Vera S. Fundamentals of Error-Correcting Codes. Cambridge University Press. 2003. ISBN 978-0-521-78280-7.
- ^ My Hard Drive Died.
- ^ Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite. 北京清華大學清華空間中心. [2009-02-16]. （原始內容存檔於2011-10-02）.
- ^ Jeff Layton. Error Detection and Correction. Linux Magazine. [2014-08-12]. （原始內容存檔於2020-11-11）.
- ^ EDAC Project. [2014-08-12]. （原始內容存檔於2014-09-25）.
- ^ Documentation/edac.txt. Linux kernel documentation. kernel.org. 2014-06-16 [2014-08-12]. （原始內容存檔於2009-09-05）.
拓展閱讀
[編輯]- Shu Lin; Daniel J. Costello, Jr. Error Control Coding: Fundamentals and Applications. Prentice Hall. 1983. ISBN 0-13-283796-X.
外部連結
[編輯]- The on-line textbook: Information Theory, Inference, and Learning Algorithms （頁面存檔備份，存於網際網路檔案館），作者戴維·J·C·麥凱。章節包括有關基本糾錯碼，關於誤差校正的理論極限，以及最新、最前沿的錯誤糾正碼，例如低密度奇偶檢查碼、turbo codes和噴泉碼。
- Compute parameters of linear codes （頁面存檔備份，存於網際網路檔案館） – 用於生成和計算參數的在線接口（例如線性誤差校正碼的最小距離、覆蓋半徑）。
- ECC Page（頁面存檔備份，存於網際網路檔案館）
- SoftECC: A System for Software Memory Integrity Checking （頁面存檔備份，存於網際網路檔案館）
- A Tunable, Software-based DRAM Error Detection and Correction Library for HPC （頁面存檔備份，存於網際網路檔案館）
- Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing （頁面存檔備份，存於網際網路檔案館）