Editing Error detection and correction (section)

== Types of error correction ==
There are three major types of error correction:<ref>{{cite journal  |title=Error Detection and Correction: An Introduction  |date=November 2012 |last1= Gupta |first1= Vikas |last2= Verma |first2= Chanderkant
 |s2cid=17499858 |journal=International Journal of Advanced Research in Computer Science and Software Engineering |volume=2 |issue=11 
 }}</ref>

=== Automatic repeat request ===
[[Automatic repeat request]] (ARQ) is an error control method for data transmission that makes use of error-detection codes, acknowledgment and/or negative acknowledgment messages, and [[Timeout (computing)|timeouts]] to achieve reliable data transmission. An ''acknowledgment'' is a message sent by the receiver to indicate that it has correctly received a [[data frame]].

Usually, when the transmitter does not receive the acknowledgment before the timeout occurs (i.e., within a reasonable amount of time after sending the data frame), it retransmits the frame until it is either correctly received or the error persists beyond a predetermined number of retransmissions.

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 [[Network latency|latency]] due to retransmissions, and requires the maintenance of buffers and timers for retransmissions, which in the case of [[network congestion]] can put a strain on the server and overall network capacity.<ref name="reliable-erasure-code">A. J. McAuley, ''Reliable Broadband Communication Using a Burst Erasure Correcting Code'', ACM SIGCOMM, 1990.</ref>

For example, ARQ is used on shortwave radio data links in the form of [[ARQ-E]], or combined with multiplexing as [[ARQ-M]].

=== Forward error correction ===
[[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>

Error-correcting codes are usually distinguished between [[convolutional code]]s and [[block code]]s:
* ''Convolutional codes'' are processed on a bit-by-bit basis. They are particularly suitable for implementation in hardware, and the [[Viterbi decoder]] allows [[maximum likelihood decoding|optimal decoding]].
* ''Block codes'' are processed on a [[Block (telecommunications)|block-by-block]] basis. Early examples of block codes are [[repetition code]]s, [[Hamming code]]s and [[multidimensional parity-check code]]s. They were followed by a number of efficient codes, [[Reed–Solomon code]]s being the most notable due to their current widespread use. [[Turbo code]]s and [[low-density parity-check code]]s (LDPC) are relatively new constructions that can provide almost [[:Category:Capacity-approaching codes|optimal efficiency]].

[[Shannon's theorem]] is an important theorem in forward error correction, and describes the maximum [[information rate]] at which reliable communication is possible over a channel that has a certain error probability or [[signal-to-noise ratio]] (SNR). This strict upper limit is expressed in terms of the [[channel capacity]]. More specifically, the theorem says that there exist codes such that with increasing encoding length the probability of error on a [[channel model|discrete memoryless channel]] can be made arbitrarily small, provided that the [[code rate]] is smaller than the channel capacity. The code rate is defined as the fraction ''k/n'' of ''k'' source symbols and ''n'' encoded symbols.

The actual maximum code rate allowed depends on the error-correcting code used, and may be lower. This is because Shannon's proof was only of existential nature, and did not show how to construct codes that are both optimal and have [[polynomial time|efficient]] encoding and decoding algorithms.

=== Hybrid schemes ===
{{Main|Hybrid ARQ}}
[[Hybrid ARQ]] is a combination of ARQ and forward error correction. There are two basic approaches:<ref name="reliable-erasure-code" />
* Messages are always transmitted with FEC parity data (and error-detection redundancy). A receiver decodes a message using the parity information and requests retransmission using ARQ only if the parity data was not sufficient for successful decoding (identified through a failed integrity check).
* Messages are transmitted without parity data (only with error-detection information). If a receiver detects an error, it requests FEC information from the transmitter using ARQ and uses it to reconstruct the original message.

The latter approach is particularly attractive on an [[erasure channel]] when using a [[rateless erasure code]].
<!-- Combined two somewhat redundant sections
== Types ==
Error correction may generally be realized in two different ways:
* ''[[Automatic repeat request]] (ARQ)'' (sometimes also referred to as ''backward error correction''): This is an error control technique whereby an error detection scheme is combined with requests for retransmission of corrupted data. Every block of data received is checked using the error detection code used, and if the check fails, retransmission of the data is requested – this may be done repeatedly, until the data can be verified.
* ''[[Forward error correction]] (FEC)'': The sender encodes the data using an ''error-correcting code (ECC)'' prior to transmission. The additional information (redundancy) added by the code is used by the receiver to recover the original data in the case of corruption.
ARQ and FEC may be combined such that minor errors are corrected without retransmission, and major errors are corrected via a request for retransmission: this is called ''[[hybrid automatic repeat request]] (HARQ)''.
-->