Error correction code: Difference between revisions

Revision as of 08:14, 26 June 2025

Revision as of 10:25, 28 June 2025

Line 78:

There are many types of block codes; [[Reed–Solomon error correction|Reed–Solomon coding]] is noteworthy for its widespread use in [[compact disc]]s, [[DVD]]s, and [[hard disk drive#Error rates and handling|hard disk drives]]. Other examples of classical block codes include [[Golay code (disambiguation)|Golay]], [[BCH code|BCH]], [[Multidimensional parity-check code|Multidimensional parity]], and [[Hamming code]]s.

Hamming ECC is commonly used to correct [[ECC memory]] and early SLC [[NAND flash]] memory errors.<ref>[http://www.eetasia.com/ART_8800575062_499486_AN_7549c493.HTM "Hamming codes for NAND flash memory devices"] {{Webarchive|url=https://web.archive.org/web/20160821122453/http://www.eetasia.com/ART_8800575062_499486_AN_7549c493.HTM |date=21 August 2016 }}. EE Times-Asia. Apparently based on [http://www.micron.com/~/media/Documents/Products/Technical%20Note/NAND%20Flash/tn2908_NAND_hamming_ECC_code.pdf "Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices"] {{Webarchive|url=https://web.archive.org/web/20170829073235/http://www.micron.com/~/media/Documents/Products/Technical%20Note/NAND%20Flash/tn2908_NAND_hamming_ECC_code.pdf |date=29 August 2017 }}. 2005. Both say: "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications."</ref>

This provides single-bit error correction and 2-bit error detection.

Hamming codes are only suitable for more reliable [[single-level cell]] (SLC) NAND.

Denser [[multi-level cell]] (MLC) NAND may use multi-bit correcting ECC such as BCH or Reed–Solomon.<ref name="spansion">{{cite web|url=http://www.spansion.com/Support/Application%20Notes/Types_of_ECC_Used_on_Flash_AN.pdf|title =What Types of ECC Should Be Used on Flash Memory?|publisher=Spansion|format=Application note|year=2011|quote=Both Reed–Solomon algorithm and BCH algorithm are common ECC choices for MLC NAND flash. ... Hamming based block codes are the most commonly used ECC for SLC.... both Reed–Solomon and BCH are able to handle multiple errors and are widely used on MLC flash.}}</ref><ref>{{cite web|author=Jim Cooke|url=https://cushychicken.github.io/assets/cooke_inconvenient_truths.pdf |title=The Inconvenient Truths of NAND Flash Memory|date=August 2007|page=28|quote=For SLC, a code with a correction threshold of 1 is sufficient. t=4 required ... for MLC.}}</ref> Later, the [[Multi-level cell|MLC]] NAND flash used more complex ECC such as [[BCH code|BCH]] and [[Low-density parity-check code|LDPC]]. NOR Flashflash typically does not use any error correction.<ref name="spansion"/>

Classical block codes are usually decoded using '''hard-decision''' algorithms,<ref>{{cite journal |author-last1=Baldi |author-first1=M. |author-last2=Chiaraluce |author-first2=F. |title=A Simple Scheme for Belief Propagation Decoding of BCH and RS Codes in Multimedia Transmissions |journal=[[International Journal of Digital Multimedia Broadcasting]] |volume=2008 |pages=1–12 |date=2008 |doi=10.1155/2008/957846 |doi-access=free }}</ref> which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, convolutional codes are typically decoded using '''soft-decision''' algorithms like the Viterbi, MAP or [[BCJR algorithm|BCJR]] algorithms, which process (discretized) analog signals, and which allow for much higher error-correction performance than hard-decision decoding.

Line 263:

* [[Cyclic redundancy check]]s (CRCs) can correct 1-bit errors for messages at most <math>2^{n-1}-1</math> bits long for optimal generator polynomials of degree <math>n</math>, see {{section link|Mathematics of cyclic redundancy checks|Bitfilters}}

* [[Locally Recoverable Codes]]

* [[Message authentication code]]

==See also==