Block code

Systematic block code consisting of separate information and test symbols

Block codes are a type of channel coding in the family of (error-detecting and) error-correcting codes . They are characterized by a fixed block size of symbols from a fixed alphabet (for binary codes ). In contrast to convolutional codes, individual blocks are encoded and decoded independently of one another. ${\ displaystyle n}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma = \ {0.1 \}}$

Important properties of a block code are the information rate (the ratio of the amount of information contained to the total amount of data ) and its correction rate (i.e. the ability to recognize and / or correct errors). Both properties influence each other and create a common, insurmountable barrier. The barrier can be approached through optimization, but the codes are long and laborious to decode. Cascading codes has proven to be a more practical solution here. ${\ displaystyle k}$ ${\ displaystyle n}$

Although block codes are often not optimal in terms of a minimum mean code word length, one often restricts oneself to block codes. Linear codes and systematic codes are another specialization .

construction

Possible words result from the alphabet and the block size , a subset of which represents the valid code words . The thickness of the alphabet is denoted by, it is in the case of binary codes . The thickness of the code can be used as many codes (always with linear codes) with be written. Given a block size of symbols, these codes can carry a payload . ${\ displaystyle \ Sigma}$ ${\ displaystyle n}$ ${\ displaystyle \ Sigma ^ {n}}$ ${\ displaystyle {\ mathcal {C}} \ subseteq \ Sigma ^ {n}}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle q = | \ Sigma |}$ ${\ displaystyle q = | \ Sigma | = 2}$ ${\ displaystyle | {\ mathcal {C}} |}$ ${\ displaystyle | {\ mathcal {C}} | = q ^ {k}}$ ${\ displaystyle k \ in \ mathbb {N} ^ {+}}$ ${\ displaystyle n}$ ${\ displaystyle k \ leq n}$

The information rate is , the correction rate is limited by the (minimal) Hamming distance of the code . The Hamming distance between two code words and is the number of different symbols of these code words , the (minimum) Hamming distance of a (whole) code is the minimum Hamming distance of all (disjoint) code word pairs, i.e. H. . The latter limits the maximum (reliable) correction performance on symbol errors . In the case of cascaded correction procedures, in addition to error correction, error detection also plays a role. For a non-detect perfect codes a certain amount of multi-bit errors with which they themselves can not be corrected, on the other hand can be error correction capabilities against further (guaranteed) error detection capabilities to exchange and following corrective steps help: . ${\ displaystyle k / n \ leq 1}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle c_ {i}}$ ${\ displaystyle c_ {j}}$ ${\ displaystyle \ Delta (c_ {i}, c_ {j})}$ ${\ displaystyle d}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle d = \ Delta ({\ mathcal {C}}) \, \, {\ overset {\ underset {\ mathrm {def}} {}} {=}} \, \ min _ {i \ neq j } \, \ Delta (c_ {i}, c_ {j})}$ ${\ displaystyle t}$ ${\ displaystyle t = \ left \ lfloor (d-1) / 2 \ right \ rfloor}$ ${\ displaystyle t _ {\ mathrm {Mehrbit}}> t}$ ${\ displaystyle r}$ ${\ displaystyle r = d-1-t _ {\ mathrm {uses}}}$

Different notations have been established for codes in the literature:

${\ displaystyle [n, k; d, q]}$ or , the semicolon is often replaced by a comma and the square brackets by round brackets. is often left out, the same applies to the classic Hamming codes. ${\ displaystyle [n, k; d] _ {q}}$ ${\ displaystyle q = 2}$ ${\ displaystyle d = 3}$
Often, instead of (the number of useful symbols), the code strength , i. H. or the code specified itself , this information is partly hidden in the type of brackets used. ${\ displaystyle k}$ ${\ displaystyle q ^ {k} = | {\ mathcal {C}} |}$ ${\ displaystyle (n, q ^ {k}, d) _ {q}}$ ${\ displaystyle (n, {\ mathcal {C}}, d) _ {q}}$

Furthermore, an attempt is made to keep this as well as the use of variable names consistent in this article as well as in related articles.

It is commonly referred to as a code if ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle (n, {\ mathcal {C}}; d, q)}$

${\ displaystyle \ Sigma}$ an alphabet with is, ${\ displaystyle | \ Sigma | = q}$
the code is and ${\ displaystyle {\ mathcal {C}} \ subseteq \ Sigma ^ {n}}$
is the (minimum) Hamming distance . ${\ displaystyle d = \ Delta ({\ mathcal {C}})}$

If one looks at linear codes , one speaks of codes or codes, whereby here the dimension is from above the body . and have the same meaning as for the general block codes. ${\ displaystyle [n, k; d, q]}$ ${\ displaystyle [n, k; d] _ {q}}$ ${\ displaystyle k}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle n}$ ${\ displaystyle d}$

While there are theoretical limits (like the Hamming limit), another question is what codes can actually be constructed. It's like packing spheres in a square box ... This diagram shows the codes that can be constructed, which are linear and binary. The x-axis shows the number of protected symbols k and the y-axis shows the number of test symbols nk required. The limits for different Hamming distances are shown: From 1 (unprotected) to 34.
Perfect codes are marked with dots:

light orange on the x-axis: trivially unprotected codes
orange, on the y-axis: trivial repetition codes
dark orange, on the line for d = 3: classic, perfect Hamming codes
dark red and large: the only perfect binary Golay code

One is interested in the given , and in maximizing the power of the code, i. H. for , as this achieves an optimal information rate for these parameters. However, there are favorable parameters that lead to more efficient codes than their neighboring parameters. A code requires 11 protection bits, but a code requires 14. A code , like a code, requires 17 protection bits. ${\ displaystyle n}$ ${\ displaystyle d}$ ${\ displaystyle q}$ ${\ displaystyle \ max \ {| {\ mathcal {C}} |: {\ mathcal {C}} \, \, {\ mathrm {with}} \, \, \ Delta ({\ mathcal {C}}) \ geq d \}}$ ${\ displaystyle [23.12; 7.2]}$ ${\ displaystyle [27.13; 7.2]}$ ${\ displaystyle [41.24; 7.2]}$ ${\ displaystyle [55.38; 7.2]}$

There are estimates of whether codes might be possible or violate certain principles:

Singleton barrier ( MDS code )
Hamming barrier ( perfect code )
Plotkin bound
Gilbert limit , Varshamov limit , Johnson limit , Griesmer limit , Bassalygo-Elias limit
Optimal code

Boundaries indicate whether codes can exist, not whether they can be constructed and really exist.

Types of block codes

Formally, the code is called block code, where it is called the alphabet and is the length of each code word . ${\ displaystyle {\ mathcal {C}} \ subseteq \ Sigma ^ {n}}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle n}$ ${\ displaystyle c \ in {\ mathcal {C}}}$

Trivial block codes are codes

only one word as the code include: . All transmission errors can be recognized, but no information can be transmitted or ${\ displaystyle | {\ mathcal {C}} | = 1}$
the all possible words as the code include: . No transmission errors can be detected, but the information transmitted is maximum. ${\ displaystyle | {\ mathcal {C}} | = | \ Sigma | ^ {n}}$

Remarks:

The first code can be written as code. In the classic sense, it has no Hamming distance, since there are no code pairs. Up to a maximum of symbol errors in the transmitted word can be corrected (the transmitted code word is known), which is a typical property for codes with . The same applies to the number of codes that can be clearly decoded. The equation gives the correct result. ${\ displaystyle [n, 0; 2n + 1, q]}$ ${\ displaystyle t = n}$ ${\ displaystyle w}$ ${\ displaystyle d = 2t + 1 = 2n + 1}$ ${\ displaystyle q ^ {n} = {\ sum _ {i = 0} ^ {\ lfloor (d-1) / 2 \ rfloor} (q-1) ^ {i} {\ binom {n} {i} }}}$ ${\ displaystyle d \ geq 2n + 1}$
The second code can be written as code. He has a Hamming distance of 1. ${\ displaystyle [n, n; 1,2]}$

Linear block codes are codes
if there is a -dimensional subspace of . There is then a basis of . If you combine this basis into a matrix ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle k}$ ${\ displaystyle \ Sigma ^ {n}}$ ${\ displaystyle g_ {1}, \ dots, g_ {k}}$ ${\ displaystyle {\ mathcal {C}}}$

{\ displaystyle G = {\ begin {pmatrix} g_ {1} \\ g_ {2} \\\ vdots \\ g_ {k-1} \\ g_ {k} \ end {pmatrix}}}

together, one obtains a generator matrix of this linear block code. The code words are obtained by multiplying the input signal by the generator matrix ${\ displaystyle x}$

{\ displaystyle c (x) = x \ cdot G}

The main advantage of linear codes is that they can be easily coded and decoded.

Remarks:
To encode a code with code words one only has to keep code words in stock. The same applies to decoding with vs. . ${\ displaystyle q ^ {k}}$ ${\ displaystyle k}$ ${\ displaystyle q ^ {n}}$ ${\ displaystyle n}$

Parity
codes are linear, systematic and binary codes with the check symbol generator matrix

{\ displaystyle G_ {p} = {\ begin {pmatrix} 1 \\ 1 \\\ vdots \\ 1 \\ 1 \ end {pmatrix}}}

and the overall generator matrix

{\ displaystyle G = {\ begin {pmatrix} 10 \ dots 00 \, \, 1 \\ 01 \ dots 00 \, \, 1 \\\, \, \, \, \ vdots \ ddots \ vdots \, \ , \, \, \, \, \ vdots \\ 00 \ dots 10 \, \, 1 \\ 00 \ dots 01 \, \, 1 \\\ end {pmatrix}}}

They have a Hamming distance of 2 and represent block codes. They can recognize an error, but not correct an error. Linear binary block codes with an uneven Hamming distance can be expanded to form a code with an additional parity code. ${\ displaystyle [n, n-1; 2.2]}$ ${\ displaystyle [n, k; 2m + 1,2]}$ ${\ displaystyle [n + 1, k; 2m + 2.2]}$

Systematic block codes are codes that
consist of information symbols at the beginning of the block and check symbols at the end of the block (see illustration at the beginning of the article). They can be linear block codes at the same time, but do not have to be. They are linear block codes if, in addition to the information symbols (which are always linear), the check symbols are also linear. ${\ displaystyle k}$ ${\ displaystyle nk}$

Perfect block codes are codes
in which each word has the smallest Hamming distance to exactly one code word (and not to several) . Each word can thus be uniquely decoded. ${\ displaystyle w \ in \ Sigma ^ {n}}$ ${\ displaystyle c \ in {\ mathcal {C}}}$ ${\ displaystyle d_ {w}}$

Hadamard codes
are linear, non-systematic block codes . The generator matrix has a very striking shape ${\ displaystyle [2 ^ {k}, k + 1; 2 ^ {k-1}]}$

{\ displaystyle G = {\ begin {pmatrix} 01010101 \ cdots 10 \ cdots 01010101 \\ 00110011 \ cdots 10 \ cdots 00110011 \\ 00001111 \ cdots 10 \ cdots 00001111 \\\ vdots \\ 00000000 \ cdots 01 \ cdots 11111111 \ \ 11111111 \ cdots 10 \ cdots 00000000 \\\ end {pmatrix}}}

They have a low information rate, but can still decode data from very faulty signals.

Information rate for block codes

Be a block code and assume that the alphabet has different elements. Then the definition of the information rate reads : ${\ displaystyle {\ mathcal {C}} \ subseteq \ Sigma ^ {n}}$ ${\ displaystyle q = | \ Sigma |}$ ${\ displaystyle q}$ ${\ displaystyle {\ mathcal {C}}}$

{\ displaystyle {\ frac {\ log _ {q} (| {\ mathcal {C}} |)} {\ log _ {q} (| \ Sigma | ^ {n})}} = {\ frac {\ log _ {q} (| {\ mathcal {C}} |)} {n}}}

.

Is z. B. a binary code with different elements, bits are needed to distinguish between different code words. The information rate sets the lowest possible number of symbols in relation to the actually transmitted number of symbols. ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle s}$ ${\ displaystyle \ lceil \ log _ {2} s \ rceil}$ ${\ displaystyle s}$

If the first bits of a binary -bit code word are information bits that exist in all possible code words, then the information rate is: ${\ displaystyle k}$ ${\ displaystyle n}$

{\ displaystyle {\ frac {\ log _ {2} (2 ^ {k})} {n}} = {\ frac {k} {n}}}

.

Examples of block codes

example 1

{\ displaystyle (9, \ {0,31,227,364,437,474 \}; 5.2)}

The code words are in the binary representation: ${\ displaystyle | {\ mathcal {C}} | = 6}$ ${\ displaystyle c}$

.........
....#####
.###...##
#.##.##..
##.##.#.#
###.##.#.

There is no linear code of this power. On the one hand, the largest linear codes of this type are one and one code. The code cannot be converted into a linear code. ${\ displaystyle {\ text {log}} _ {q} 6 \ not \ in \ mathbb {N} ^ {+}}$ ${\ displaystyle [8.2; 5.2]}$ ${\ displaystyle [10.3; 5.2]}$

Example 2

{\ displaystyle (11, \ {0,143,307,444,597,730,870,1001,1130,1253,1369,1494,1599,1712,1804,1923 \}; 5.2)}

The code words are in the binary representation (MSB left): ${\ displaystyle | {\ mathcal {C}} | = 16}$ ${\ displaystyle c}$

...........
...#...####
..#..##..##
..##.####..
.#..#.#.#.#
.#.##.##.#.
.##.##..##.
.#####.#..#
#...##.#.#.
#..###..#.#
#.#.#.##..#
#.###.#.##.
##...######
##.#.##....
###....##..
####.....##

It is a linear systematic code with the base

...#...####
..#..##..##
.#..#.#.#.#
#...##.#.#.

The 16 code words can be generated by XORing the basic vectors whose information bits are set (therefore linear code). The information bits represent the left 4 bits (bits 10 to 7), the protection bits the right 7 bits (bits 6 to 0) (hence the systematic code).

Example 3

{\ displaystyle (8, \ {0,7,25,30,42,53,75,84,97,108,114,127,140,147,166,169,176,194,197,216 \}; 3.2)}

The code words are in the binary representation: ${\ displaystyle | {\ mathcal {C}} | = 20}$ ${\ displaystyle c}$

........
.....###
...##..#
...####.
..#.#.#.
..##.#.#
.#..#.##
.#.#.#..
.##....#
.##.##..
.###..#.
.#######
#...##..
#..#..##
#.#..##.
#.#.#..#
#.##....
##....#.
##...#.#
##.##...

There is no linear code of this power. Again, on the one hand , on the other hand, the largest linear codes of this type are one and one code. The code cannot be converted into a linear code. ${\ displaystyle {\ text {log}} _ {q} 20 \ not \ in \ mathbb {N} ^ {+}}$ ${\ displaystyle [7.4; 3.2]}$ ${\ displaystyle [9.5; 3.2]}$

Bug fix

Block codes can be used for error detection and error correction when transmitting data over faulty channels . The transmitter assigns a length code word to the information word to be transmitted , whereby . The addition of the additional symbols creates redundancy and decreases the information rate; however, the receiver can now use the redundant information to identify and correct transmission errors. ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ displaystyle n> k}$ ${\ displaystyle nk}$

For example, if you use the assignment in the case of binary coding

Information word	code word
0	000
1	111

received code words with exactly one bit error can be corrected by reversing the deviating bit with the help of a majority function :

Incorrect code word	Corrected code word	Associated information word
00 1	00 0	0
0 1 0	0 0 0	0
0 11	1 11	1
1 00	0 00	0
1 0 1	1 1 1	1
11 0	11 1	1

However, if two bits are incorrect in this case, an error is recognized, but incorrectly corrected. If three bits are wrong, an error cannot even be recognized.

literature

Rudolf Nocker: Digital Communication Systems 1. Basics of Baseband Transmission, 1. Edition, Friedrich Vieweg & Sohn Verlag, Wiesbaden 2004, ISBN 978-3-528-03976-9 .
Markus Hufschmid: Information and communication . Basics of information transfer, Vieweg and Teubner, Wiesbaden 2006, ISBN 3-8351-0122-6 .
Bernd Friedrichs: Channel coding. Basics and applications in modern communication systems. Springer Verlag, Berlin / Heidelberg 1995, ISBN 3-540-59353-5 .

Web links

Channel coding and block codes (accessed April 6, 2018)
Linear Error Correcting Codes (accessed April 6, 2018)
Proinformatik - Functional Programming (accessed April 6, 2018)
Channel Coding Formula Collection (accessed April 6, 2018)
Theory and Practice of Error Control Codes Block Code Performance (accessed April 6, 2018)