Content deleted Content added
Joefromrandb (talk | contribs) →Principles: ce |
ClueBot NG (talk | contribs) m Reverting possible vandalism by 50.175.213.202 to version by Bender the Bot. Report False Positive? Thanks, ClueBot NG. (4410618) (Bot) |
||
| (19 intermediate revisions by 17 users not shown) | |||
Line 4:
{{More citations needed|article|date=August 2008}}
[[File:Reed–Solomon error correction Mona Lisa LroLrLasercomFig4.jpg|thumb|To clean up transmission errors introduced by Earth's atmosphere (left), Goddard scientists applied [[Reed–Solomon error correction]] (right), which is commonly used in CDs and DVDs. Typical errors include missing pixels (white) and false signals (black). The white stripe indicates a brief period when transmission was interrupted.]]
In [[information theory]] and [[coding theory]] with applications in [[computer science]] and [[telecommunications]], '''error detection and correction''' ('''EDAC''') or '''error control''' are techniques that enable [[reliable delivery]] of [[digital data]] over unreliable [[communication channel]]s. Many communication channels are subject to [[channel noise]], and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.
Line 37:
Three types of ARQ protocols are [[Stop-and-wait ARQ]], [[Go-Back-N ARQ]], and [[Selective Repeat ARQ]].
ARQ is appropriate if the communication channel has varying or unknown [[channel capacity|capacity]], such as is the case on the Internet. However, ARQ requires the availability of a [[Backward channel|back channel]], results in possibly increased [[
For example, ARQ is used on shortwave radio data links in the form of [[ARQ-E]], or combined with multiplexing as [[ARQ-M]].
=== Forward
[[Forward error correction]] (FEC) is a process of adding [[redundancy (information theory)|redundant data]] such as an [[error-correcting code]] (ECC) to a message so that it can be recovered by a receiver even when a number of errors (up to the capability of the code being used) are introduced, either during the process of transmission or on storage. Since the receiver does not have to ask the sender for retransmission of the data, a [[backchannel]] is not required in forward error correction. Error-correcting codes are used in [[Physical layer|lower-layer]] communication such as [[cellular network]], high-speed [[fiber-optic communication]] and [[Wi-Fi]],<ref>{{cite book |last1=Shah |first1=Pradeep M. |last2=Vyavahare |first2=Prakash D. |last3=Jain |first3=Anjana |title=2015 Radio and Antenna Days of the Indian Ocean (RADIO) |chapter=Modern error correcting codes for 4G and beyond: Turbo codes and LDPC codes |date=September 2015 |pages=1–2 |doi=10.1109/RADIO.2015.7323369 |isbn=978-9-9903-7339-4 |s2cid=28885076 |chapter-url=https://www.researchgate.net/publication/301611980 |access-date=22 May 2022}}</ref><ref>{{cite journal |title=IEEE SA - IEEE 802.11ac-2013 |journal=IEEE Standards Association |url=https://standards.ieee.org/ieee/802.11ac/4473/ |language=en |access-date=2022-05-22 |archive-date=2022-05-22 |archive-url=https://web.archive.org/web/20220522205452/https://standards.ieee.org/ieee/802.11ac/4473/ |url-status=dead }}</ref> as well as for reliable storage in media such as [[flash memory]], [[hard disk]] and [[ECC memory|RAM]].<ref>{{cite web |title=Transition to Advanced Format 4K Sector Hard Drives {{!}} Seagate US |url=https://www.seagate.com/sg/en/tech-insights/advanced-format-4k-sector-hard-drives-master-ti/ |website=Seagate.com |access-date=22 May 2022 |language=en-us}}</ref>
Line 123:
{{Main|Cryptographic hash function}}
The output of a ''cryptographic hash function'', also known as a ''message digest'', can provide strong assurances about [[data integrity]], whether changes of the data are accidental (e.g., due to transmission errors) or maliciously introduced. Any modification to the data will likely be detected through a mismatching hash value. Furthermore, given some hash value, it is typically infeasible to find some input data (other than the one given) that will yield the same hash value. If an attacker can change not only the message but also the hash value, then a ''keyed hash'' or [[message authentication code]] (MAC) can be used for additional security. Without knowing the key, it is not possible for the attacker to easily or conveniently calculate the correct keyed hash value for a modified message.
=== Digital signature ===
{{ main | Digital signature }}
Digital signatures can provide strong assurances about data integrity, whether the changes of the data are accidental or maliciously introduced.
Digital signatures are perhaps most notable for being part of the HTTPS protocol for securely browsing the web.
=== Error correction code ===
Line 135 ⟶ 140:
Applications where the transmitter immediately forgets the information as soon as it is sent (such as most television cameras) cannot use ARQ; they must use FEC because when an error occurs, the original data is no longer available.
Applications that use ARQ must have a [[return channel]]; applications having no return channel cannot use ARQ. Applications that require extremely low error rates (such as digital money transfers) must use ARQ due to the possibility of uncorrectable errors with FEC.
Reliability and inspection engineering also make use of the theory of error-correcting codes
{{cite journal
| author = Yvo Meeres, Tommi A. Pirinen
| authorlink =
| year = 2021
| title = Vowel Harmony Viewed as Error-Correcting Code
| journal = Proceedings of the Society for Computation in Linguistics
| volume = 4
| issue = 1
| pages = 313–322
| doi = 10.7275/bjvb-2n37
| pmid =
}}
</ref>
=== Internet ===
In a typical [[TCP/IP]] stack, error control is performed at multiple levels:
* Each [[Ethernet frame]] uses [[
* The [[IPv4]] header contains a [[IPv4 header checksum|checksum]] protecting the contents of the header. [[Network packet|Packets]] with incorrect checksums are dropped within the network or at the receiver.
* The checksum was omitted from the [[IPv6]] header in order to minimize processing costs in [[network routing]] and because current [[link layer]] technology is assumed to provide sufficient error detection (see also RFC 3819).
Line 162 ⟶ 178:
=== Data storage ===
Error detection and correction codes are often used to improve the reliability of data storage media.<ref>{{Cite book|last1=Kurtas|first1=Erozan M.|url=https://books.google.com/books?id=Vx_NBQAAQBAJ&q=Error+detection+and+correction+codes+are+often+used+to+improve+the+reliability+of+data+storage+media&pg=PR5|title=Advanced Error Control Techniques for Data Storage Systems|last2=Vasic|first2=Bane|date=2018-10-03|publisher=CRC Press|isbn=978-1-4200-3649-7|language=en}}{{Dead link|date=March 2020 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> A parity track capable of detecting single-bit errors was present on the first [[magnetic tape data storage]] in 1951. The [[optimal rectangular code]] used in [[group coded recording]] tapes not only detects but also corrects single-bit errors. Some [[file format]]s, particularly [[archive formats]], include a checksum (most often
Modern hard drives use Reed–Solomon codes to detect and correct minor errors in sector reads, and to recover corrupted data from failing sectors and store that data in the spare sectors.<ref>{{cite web |archive-url=https://web.archive.org/web/20080202143103/http://www.myharddrivedied.com/presentations_whitepaper.html |archive-date=2008-02-02 |url=http://www.myharddrivedied.com/presentations_whitepaper.html |title=My Hard Drive Died |author=Scott A. Moulton}}</ref> [[RAID]] systems use a variety of error correction techniques to recover data when a hard drive completely fails. Filesystems such as [[ZFS]] or [[Btrfs]], as well as some [[RAID]] implementations, support [[data scrubbing]] and resilvering, which allows bad blocks to be detected and (hopefully) recovered before they are used.<ref>{{Cite book|last1=Qiao|first1=Zhi|last2=Fu|first2=Song|last3=Chen|first3=Hsing-Bung|last4=Settlemyer|first4=Bradley|title=2019 IEEE International Conference on Cluster Computing (CLUSTER) |chapter=Building Reliable High-Performance Storage Systems: An Empirical and Analytical Study |date=2019|pages=1–10|doi=10.1109/CLUSTER.2019.8891006|isbn=978-1-7281-4734-5|s2cid=207951690}}</ref> The recovered data may be re-written to exactly the same physical ___location, to spare blocks elsewhere on the same piece of hardware, or the data may be rewritten onto replacement hardware.
Line 187 ⟶ 203:
| author = Jeff Layton | magazine = [[Linux Magazine]]
}}</ref><ref>{{cite web
| url =
| title = EDAC Project
| access-date = 2014-08-12
Line 217 ⟶ 233:
* {{cite book|author1=Shu Lin |author2=Daniel J. Costello, Jr. | title = Error Control Coding: Fundamentals and Applications| year = 1983| publisher = [[Prentice Hall]]| isbn = 0-13-283796-X }}
* [http://pdos.csail.mit.edu/papers/softecc:ddopson-meng/softecc_ddopson-meng.pdf SoftECC: A System for Software Memory Integrity Checking]
* [http://www.fiala.me/pubs/papers/libsdc11.pdf A Tunable, Software-based DRAM Error Detection and Correction Library for HPC] {{Webarchive|url=https://web.archive.org/web/20141107074502/http://www.fiala.me/pubs/papers/libsdc11.pdf |date=2014-11-07 }}
* [http://www.fiala.me/pubs/papers/sc12-redmpi.pdf Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing] {{Webarchive|url=https://web.archive.org/web/20141107074511/http://www.fiala.me/pubs/papers/sc12-redmpi.pdf |date=2014-11-07 }}
== External links ==
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms], by [[David J.C. MacKay]], contains chapters on elementary error-correcting codes; on the theoretical limits of error-correction; and on the latest state-of-the-art error-correcting codes, including [[low-density parity-check code]]s, [[turbo code]]s, and [[fountain codes]].
* [http://www.eccpage.com/ ECC Page]
[[Category:Error detection and correction| ]]
| |||