錯誤檢測與更正
 | 此條目翻譯自其他語言維基百科，需要相關領域的編者協助校對翻譯。 |
在電腦科學和通訊的資訊理論和編碼理論應用中，錯誤檢測和更正（英語：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 （頁面存檔備份，存於互聯網檔案館）