Content deleted Content added
No edit summary Tags: Reverted Mobile edit Mobile web edit |
m unpiped links using script |
||
(18 intermediate revisions by 12 users not shown) | |||
Line 1:
{{Short description|Family of error-correcting codes that encode data in blocks}}
{{More footnotes needed|date=February 2025}}
In [[coding theory]], '''block codes''' are a large and important family of [[Channel coding|error-correcting codes]] that encode data in blocks.
There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, [[mathematician]]s, and [[computer
Such limitations often take the form of ''bounds'' that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.
Examples of block codes are [[Reed–Solomon code]]s, [[Hamming code]]s, [[Hadamard code]]s, [[Expander code]]s, [[Golay code (disambiguation)|Golay code]]s, [[Reed–Muller code]]s and [[
Algebraic block codes are typically [[Soft-decision decoder|hard-decoded]] using algebraic decoders.{{Technical statement|date=May 2015}}
Line 24 ⟶ 26:
=== The alphabet Σ ===
The data stream to be encoded is modeled as a [[string (computer science)|string]] over some '''alphabet''' <math>\Sigma</math>. The size <math>|\Sigma|</math> of the alphabet is often written as <math>q</math>. If <math>q=2</math>, then the block code is called a ''binary'' block code. In many applications it is useful to consider <math>q</math> to be a [[prime power]], and to identify <math>\Sigma</math> with the [[finite field]] <math>\mathbb F_q</math>.
=== The message length ''k'' ===
Messages are elements <math>m</math> of <math>\Sigma^k</math>, that is, strings of length <math>k</math>.
Hence the number <math>k</math> is called the '''message length''' or '''dimension''' of a block code.
=== The block length ''n'' ===
The '''block length''' <math>n</math> of a block code is the number of symbols in a block. Hence, the elements <math>c</math> of <math>\Sigma^n</math> are strings of length <math>n</math> and correspond to blocks that may be received by the receiver. Hence they are also called received words.
If <math>c=C(m)</math> for some message <math>m</math>, then <math>c</math> is called the codeword of <math>m</math>.
=== The rate ''R'' ===
The '''rate''' of a block code is defined as the ratio between its message length and its block length:
:<math>R=k/n</math>.
A large rate means that the amount of actual message per transmitted block is high. In this sense, the rate measures the transmission speed and the quantity <math>1-R</math> measures the overhead that occurs due to the encoding with the block code.
It is a simple [[information theory|information theoretical]] fact that the rate cannot exceed <math>1</math> since data cannot in general be losslessly compressed. Formally, this follows from the fact that the code <math>C</math> is an injective map.
=== {{anchor|Minimum distance}}The distance ''d'' ===
Line 34 ⟶ 46:
Then the minimum distance <math>d</math> of the code <math>C</math> is defined as
:<math>d := \min_{m_1,m_2\in\Sigma^k\atop m_1\neq m_2} \Delta[C(m_1),C(m_2)]</math>.
Since any code has to be [[injective]], any two codewords will disagree in at least one position, so the distance of any code is at least <math>1</math>. Besides, the '''distance''' equals the '''[[Hamming weight#Minimum weight|minimum weight]]''' for linear block codes because:{{cn|date=December 2024}}
:<math>\min_{m_1,m_2\in\Sigma^k\atop m_1\neq m_2} \Delta[C(m_1),C(m_2)] = \min_{m_1,m_2\in\Sigma^k\atop m_1\neq m_2} \Delta[\mathbf{0},C(
A larger distance allows for more error correction and detection.
Line 58 ⟶ 70:
== Error detection and correction properties ==
A codeword <math>c \in \Sigma^n</math>could be considered as a point in the <math>n</math>-dimension space <math>\Sigma^n</math> and the code <math>\mathcal{C}</math> is the subset of <math>\Sigma^n</math>. A code <math>\mathcal{C}</math> has distance <math>d</math> means that <math>\forall c\in \mathcal{C}</math>, there is no other codeword in the
* <math> \mathcal{C}</math> can detect <math>d-1</math> errors : Because a codeword <math>c</math> is the only codeword in the Hamming ball centered at itself with radius <math>d-1</math>, no error pattern of <math>d-1</math> or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of <math> \mathcal{C}</math>, the errors are detected (but no guarantee to correct).
* <math> \mathcal{C}</math> can correct <math>\textstyle\left\lfloor {{d-1} \over 2}\right\rfloor</math> errors. Because a codeword <math>c</math> is the only codeword in the Hamming ball centered at itself with radius <math>d-1</math>, the two Hamming balls centered at two different codewords respectively with both radius <math>\textstyle\left \lfloor {{d-1} \over 2}\right \rfloor</math> do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word <math>y</math>, as long as the number of errors is no more than <math>\textstyle\left \lfloor {{d-1} \over 2}\right \rfloor</math>, there is only one codeword in the hamming ball centered at <math>y</math> with radius <math>\textstyle\left \lfloor {{d-1} \over 2}\right \rfloor</math>, therefore all errors could be corrected.
Line 159 ⟶ 171:
{{reflist}}
{{refbegin}}
* {{cite book | author=J.H. van Lint | authorlink=Jack van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | year=1992 | isbn=3-540-54894-7 | page=[https://archive.org/details/introductiontoco0000lint/page/31 31] | url=https://archive.org/details/introductiontoco0000lint/page/31 }}
* {{cite book | author=F.J. MacWilliams | authorlink=Jessie MacWilliams |author2=N.J.A. Sloane |authorlink2=Neil Sloane | title=The Theory of Error-Correcting Codes | url=https://archive.org/details/theoryoferrorcor0000macw | url-access=registration | publisher=North-Holland | year=1977 | isbn=0-444-85193-3 | page=[https://archive.org/details/theoryoferrorcor0000macw/page/35 35]}}
* {{cite book | author=W. Huffman |author2=V.Pless | authorlink2=Vera Pless | title= Fundamentals of error-correcting codes | url=https://archive.org/details/fundamentalsofer0000huff | url-access=registration | publisher=Cambridge University Press | year=2003 | isbn=978-0-521-78280-7}}
* {{cite book | author=S. Lin |author2=D. J. Jr. Costello | title= Error Control Coding: Fundamentals and Applications | publisher=Prentice-Hall | year=1983 | isbn=0-13-283796-X}}
{{refend}}
== External links ==
|