Contents

Block code: Difference between revisions

Revision as of 08:44, 9 March 2011

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Formulas with little or no explanation, symbols not defined, content fork issues with more specific articles. Material given in outline rather than prose style. Please help improve this article if you can. (May 2010) (Learn how and when to remove this message)

Incoding theory, block codes are one of the two common types of channel codes (the other one being convolutional codes), which enable reliable transmission of digital data over unreliable communication channels subject to channel noise.

A block code transforms a message m consisting of a sequence of information symbols over an alphabet Σ into a fixed-length sequence cofn encoding symbols, called a code word. In a linear block code, each input message has a fixed length of k < n input symbols. The redundancy added to a message by transforming it into a larger code word enables a receiver to detect and correct errors in a transmitted code word, and – using a suitable decoding algorithm – to recover the original message. The redundancy is described in terms of its information rate, or more simply – for a linear block code – in terms of its code rate, k/n.

The error correction performance of a block code is described by the minimum Hamming distance d between each pair of code words, and is called the distance of the code.

Definitions

The encoder for a block code divides the information sequence into message blocks, each message block contains ${\displaystyle k}$ information symbols over an alphabet set ${\displaystyle \Sigma }$, i.e. a message could be represented as a ${\displaystyle k}$-tuple ${\displaystyle m=\left(m_{1},m_{2},\dots ,m_{k}\right)\in \Sigma ^{k}}$. The total number of possible different message is therefore ${\displaystyle |\Sigma |^{k}}$. The encoder transforms message ${\displaystyle m}$ independently onto an ${\displaystyle n}$-tuple codeword ${\displaystyle c=\left(c_{1},c_{2},\dots ,c_{n}\right)\in \Sigma ^{n}}$. The code of block length ${\displaystyle n}$ over ${\displaystyle \Sigma }$ is a subset of ${\displaystyle \Sigma ^{n}}$ : the total number of possible different codewords is the same as the total number of messages ${\displaystyle |\Sigma |^{k}}$ and ${\displaystyle k}$ is called dimension. Rate of the block code is defined as ${\displaystyle R={k \over n}}$.

The Hamming weight ${\displaystyle wt($c)} of a codeword ${\displaystyle {\boldsymbol {c}}}$ is defined as the number of non-zero positions in ${\displaystyle {\boldsymbol {c}}}$. The Hamming distance ${\displaystyle \Delta (c_{1},c_{2})}$ between two codewords ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ is defined as the number of different positions between the codewords. The (minimum) distance ${\displaystyle d}$ of a block code ${\displaystyle C\subseteq \Sigma ^{n}}$ is defined as the minimum distance between any two different codewords: ${\displaystyle d=\min _{c_{1}\neq c_{2}\in C}\Delta (c_{1},c_{2})}$. The notation ${\displaystyle (n,k,d)_{\Sigma }}$ is used to represent a block code of dimension ${\displaystyle k}$, block length ${\displaystyle n}$ over alphabet set ${\displaystyle \Sigma }$, with distance ${\displaystyle d}$. In particular, if alphabet set ${\displaystyle \Sigma }$ has size ${\displaystyle q}$, the block code is denoted as ${\displaystyle (n,k,d)_{q}}$.

Properties

A codeword ${\displaystyle c\in \Sigma ^{n}}$could be considered as a point in the ${\displaystyle n}$-dimension space ${\displaystyle \Sigma ^{n}}$ and the code ${\displaystyle {\mathcal {C}}}$ is the subset of ${\displaystyle \Sigma ^{n}}$. A code ${\displaystyle {\mathcal {C}}}$ has distance ${\displaystyle d}$ means that ${\displaystyle \forall c\in {\mathcal {C}}}$, there is no other codeword in the Hamming ball centered at ${\displaystyle c}$ with radius ${\displaystyle d-1}$, which is defined as the collection of ${\displaystyle n}$-dimension words whose Hamming distanceto${\displaystyle c}$ is no more than ${\displaystyle d-1}$. Similarly, ${\displaystyle {\mathcal {C}}}$ with (minimum) distance ${\displaystyle d}$ has the following properties:

• ${\displaystyle {\mathcal {C}}}$ can detect ${\displaystyle d-1}$ errors : Because a codeword ${\displaystyle c}$ is the only codeword in the Hamming ball centered at itself with radius ${\displaystyle d-1}$, no error pattern of ${\displaystyle d-1}$ or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of ${\displaystyle {\mathcal {C}}}$, the errors are detected (but no guarantee to correct).
• ${\displaystyle {\mathcal {C}}}$ can correct ${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$ errors. Because a codeword ${\displaystyle c}$ is the only codeword in the Hamming ball centered at itself with radius ${\displaystyle d-1}$, the two Hamming balls centered at two different codewords respectively with both radius ${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$ do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word ${\displaystyle y}$, as long as the number of errors is no more than ${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$, there is only one codeword in the hamming ball centered at ${\displaystyle y}$ with radius ${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$, therefore all errors could be corrected.
• ${\displaystyle {\mathcal {C}}}$ can correct ${\displaystyle d-1}$ erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by ${\displaystyle q}$-passing decoding : In ${\displaystyle i^{th}}$ passing the erased position is filled with the ${\displaystyle i^{th}}$ symbol and error correcting is carried out. There must be one passing that the number of errors is no more than ${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$ and therefore the erasures could be corrected.

Maximum likelihood decoding (MLD) could be used to decode: it outputs the codeword ${\displaystyle c}$ closest to the received word ${\displaystyle y}$ in Hamming distance means: ${\displaystyle {\mathcal {D}}_{MLD}($y)=\arg \min _{c\in C}\Delta (c,y)} .

Example

Consider a simple repetition code ${\displaystyle [$2]^{2}\to [2]^{6}} : ${\displaystyle C_{3,rep}(x_{1},x_{2})=(x_{1},x_{1},x_{1},x_{2},x_{2},x_{2})}$. The distance of ${\displaystyle C_{3,rep}}$ is 3 because any different valid codewords have at least 3 different symbols. Therefore, if there is only up to 1 error in the received word, e.g. ${\displaystyle y=(x_{1},x_{1},x_{3},x_{2},x_{2},x_{2})}$, the error could be recovered. However if there are more than 1 possible errors, the decoder could not tell what is the correct codeword. For example, ${\displaystyle y=(x_{1},x_{3},x_{3},x_{2},x_{2},x_{2})}$ could be the received word for either ${\displaystyle (x_{3},x_{3},x_{3},x_{3},x_{2},x_{2})}$or${\displaystyle (x_{1},x_{1},x_{2},x_{2},x_{2},x_{2})}$.

Lower and upper bound of block codes

Family of codes

${\displaystyle C=\{C_{i}\}_{i\geq 1}}$ is called family of codes, where ${\displaystyle C_{i}}$ is an ${\displaystyle (n_{i},k_{i},d_{i})_{q}}$ code with monotonic increasing ${\displaystyle n_{i}}$.

Rate of family of codes ${\displaystyle C}$ is defined as ${\displaystyle R($C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}

Relative distance of family of codes ${\displaystyle C}$ is defined as ${\displaystyle \delta ($C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}

To explore the relationship between ${\displaystyle R($C)} and ${\displaystyle \delta ($C)} , a set of lower and upper bounds of block codes are known.

Hamming bound

${\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\lfloor {{\delta \cdot n-1} \over 2}\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}$

Singleton bound

${\displaystyle \forall (n,k,d)_{q}\ code\ C,k+d\leq n+1}$, i.e. ${\displaystyle R\leq \delta +o($1)}

Plotkin bound

For ${\displaystyle q=2}$, ${\displaystyle R+2\delta \leq 1}$

For the general case, the following Plotkin bounds holds for any ${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$ with distance ${\displaystyle d}$:

1. If ${\displaystyle d=(1-{1 \over q})n,|C|\leq 2qn}$

2. If ${\displaystyle d}$ > ${\displaystyle (1-{1 \over q})n,|C|\leq {qd \over {qd-(q-1)n}}}$

For any ${\displaystyle q}$-ary code with distance ${\displaystyle \delta }$, ${\displaystyle R\leq 1-({q \over {q-1}})\delta +o($1)}

Gilbert–Varshamov bound

${\displaystyle R\geq 1-H_{q}(\delta )-\epsilon }$ , where ${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}(\delta )}$, ${\displaystyle H_{q}($x)\equiv _{def}-x\cdot \log _{q}{x \over {q-1}}-(1-x)\cdot \log _{q}{(1-x)}} is the ${\displaystyle q}$-ary entropy function.

Johnson bound

Define ${\displaystyle J_{q}(\delta )\equiv _{def}(1-{1 \over q})(1-{\sqrt {1-{q\delta \over {q-1}}}})}$.
Let ${\displaystyle J_{q}(n,d,e)}$ be the maximum number of codewords in a Hamming ball of radius ${\displaystyle e}$ for any code ${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$ of distance ${\displaystyle d}$.

Then we have the Johnson Bound : ${\displaystyle J_{q}(n,d,e)\leq qnd}$, if ${\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}({d \over n})}$

Elias–Bassalygo bound

${\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}(J_{q}(\delta ))+o($1)}

Sphere packings and lattices

Block codes are tied to the sphere packing problem which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful Golay code used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is), the dimensions refer to the length of the codeword as defined above.

The theory of coding uses the N-dimensional sphere model. For example, how many pennies can be packed into a circle on a tabletop or in 3 dimensions, how many marbles can be packed into a globe. Other considerations enter the choice of a code. For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners. As the dimensions get larger, the percentage of empty space grows smaller. But at certain dimensions, the packing uses all the space and these codes are the so called perfect codes. There are very few of these codes.

Another property is the number of neighbors a single codeword may have.^[1] Again, consider pennies as an example. First we pack the pennies in a rectangular grid. Each penny will have 4 near neighbors (and 4 at the corners which are farther away). In a hexagon, each penny will have 6 near neighbors. Respectively, in three and four dimensions, the maximum packing is given by the 12-face and 24-cell with 12 and 24 neighbors, respectively. When we increase the dimensions, the number of near neighbors increases very rapidly. In general, the value is given by the kissing numbers.

The result is the number of ways for noise to make the receiver choose a neighbor (hence an error) grows as well. This is a fundamental limitation of block codes, and indeed all codes. It may be harder to cause an error to a single neighbor, but the number of neighbors can be large enough so the total error probability actually suffers.^[1]

See also

• Channel Capacity
• Shannon–Hartley theorem
• Noisy channel
• List decoding
• Sphere packing

Notes

• Atri Rudra, CSE545 Error Correcting Codes: Combinatorics, Algorithms and Applications, State University of New York at Buffalo, http://www.cse.buffalo.edu/~atri/courses/coding-theory/

References

This article needs additional citations for verification. Please help improve this articlebyadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Block code" – news · newspapers · books · scholar · JSTOR (September 2008) (Learn how and when to remove this message)

• J.H. van Lint (1992). Introduction to Coding Theory. GTM. Vol. 86 (2nd ed ed.). Springer-Verlag. p. 31. ISBN 3-540-54894-7. {{cite book}}: |edition= has extra text (help)
• F.J. MacWilliams (1977). The Theory of Error-Correcting Codes. North-Holland. p. 35. ISBN 0-444-85193-3. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• W. Huffman (2003). Fundamentals of error-correcting codes. Cambridge University Press. ISBN 13: 9780521782807. {{cite book}}: Check |isbn= value: invalid character (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)

• S. Lin (1983). Error Control Coding: Fundamentals and Applications. Prentice-Hall. ISBN 0-13-283796-X. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

• Coding Concepts and Block Coding