Channel Coding/Objective of Channel Coding

1. Channel Coding
2. Binary Block Codes for Channel Coding
3. Objective of Channel Coding

• [[Channel Coding/{{{Vorherige Seite}}} | Previous page]]
• Next page

• [[Channel Coding/{{{Vorherige Seite}}} | Previous page]]
• Next page

# Overview on The First Main Chapter #

The first chapter deals with  block codes for error detection and error correction  and provides the basics for describing more effective codes such as

• the  »Reed-Solomon codes«  (see Chapter 2),
• the  »convolutional codes«  (see Chapter 3),  and
• the  »iteratively decodable product codes«  ("turbo codes") and the  »low-density parity-check codes«  (see Chapter 4).

This specific field of coding is called  Channel Coding  in contrast to

•   »Source Coding«  (redundancy reduction for reasons of data compression),  and
•   »Line Coding«  (additional redundancy to adapt the digital signal to the spectral characteristics of the transmission medium).

We restrict ourselves here to  »binary codes«.  In detail,  this book covers:

1. Definitions and introductory examples of  »error detection and error correction«,
2. a brief review of appropriate  »channel models«  and  »decision device structures«,
3. known binary block codes such as  »single parity-check code«,  »repetition code«  and  »Hamming code«,
4. the general description of linear codes using  »generator matrix«  and  »check matrix«,
5. the decoding possibilities for block codes, including  »syndrome decoding« ,
6. simple approximations and upper bounds for the  »block error probability«,  and
7. an  »information-theoretic bound«  on channel coding.

Error Detection and Error Correction

Transmission errors occur in every digital transmission system.  It is possible to keep the probability  $p_{\rm S}$  of such a symbol error very small,  for example by using a very large signal energy.  However, the symbol error probability  $p_{\rm S} = 0$  is never achievable because of the Gaussian PDF of the thermal noise that is always present.

Particularly in the case of heavily disturbed channels and also for safety-critical applications,  it is therefore essential to provide special protection for the data to be transmitted,  adapted to the application and channel.  For this purpose,  redundancy is added at the transmitter and this redundancy is used at the receiver to reduce the number of decoding errors.

$\text{Definitions:}$

1.  Error Detection:   The decoder checks the integrity of the received blocks and marks any errors found.  If necessary,  the receiver informs the transmitter about erroneous blocks via the return channel,  so that the transmitter sends the corresponding block again.
   
   
2.  Error Correction:   The decoder detects one  (or more)  bit errors and provides further information for them,  for example their positions in the transmitted block.  In this way,  it may be possible to completely correct the errors that have occurred.
   
   
3.  Channel Coding  includes procedures for  error detection  as well as those for  error correction.
   

All  $\rm ARQ$  ("Automatic Repeat Request")  procedures use error detection only. 

• Less redundancy is required for error detection than for error correction. 

• One disadvantage of ARQ is its low throughput when channel quality is poor,  i.e. when entire blocks of data must be frequently re-requested by the receiver.
  

In this book we mostly deal with  $\rm FEC$  ("Forward Error Correction")  which leads to very small error rates if the channel is sufficiently good when  (large SNR). 

• With worse channel conditions,  nothing changes in the throughput,  i.e. the same amount of information is transmitted. 

• However,  the symbol error rate can then assume very large values.
  

Often FEC and ARQ methods are combined,  and the redundancy is divided between them in such a way,

• so that a small number of errors can still be corrected,  but
• when there are too much errors,  a repeat of the block is requested.

Some Introductory Examples of Error Detection

$\text{Example 1:   Single Parity–Check Code (SPC)}$
If one adds  $k = 4$  bit by a so-called check bit (English:   Parity Bit ) in such a way that the sum of all ones is even, for example (with bold check bits)

$$0000\boldsymbol{0}, 0001\boldsymbol{1}, \text{...} , 1111\boldsymbol{0}, \text{...}\ ,$$

it is very easy to recognise a single error. Two errors within a code word, on the other hand, remain undetected.

$\text{Example 2:   International Standard Book Number (ISBN)}$
Since the 1960s, all books have been given 10-digit codes (ISBN–10 ). Since 2007, the specification according to ISBN–13  is additionally obligatory. For example, these are for the reference book [Söd93]:

• $\boldsymbol{3–540–57215–5}$  (for ISBN–10), bzw.
• $\boldsymbol{978–3–54057215–2}$  (for ISBN–13).

The last digit  $z_{10}$  for ISBN–10 results from the previous digits  $z_1 = 3$,  $z_2 = 5$, ... ,  $z_9 = 5$  according to the following calculation rule:

\[z_{10} = \left ( \sum_{i=1}^{9} \hspace{0.2cm} i \cdot z_i \right ) \hspace{-0.3cm} \mod 11 = (1 \cdot 3 + 2 \cdot 5 + ... + 9 \cdot 5 ) \hspace{-0.2cm} \mod 11 = 5 \hspace{0.05cm}. \]

Note that  $z_{10} = 10$  must be written as  $z_{10} = \rm X$  (Roman numeral representation of "10"), since the number  $10$  cannot be represented as a digit in the decimal system.

The same applies to the check digit for ISBN–13:

\[z_{13}= 10 - \left ( \sum_{i=1}^{12} \hspace{0.2cm} z_i \cdot 3^{(i+1) \hspace{-0.2cm} \mod 2} \right ) \hspace{-0.3cm} \mod 10 = 10 \hspace{-0.05cm}- \hspace{-0.05cm} \big [(9\hspace{-0.05cm}+\hspace{-0.05cm}8\hspace{-0.05cm}+\hspace{-0.05cm}5\hspace{-0.05cm}+\hspace{-0.05cm}0\hspace{-0.05cm}+\hspace{-0.05cm}7\hspace{-0.05cm}+\hspace{-0.05cm}1) \cdot 1 + (7\hspace{-0.05cm}+\hspace{-0.05cm}3\hspace{-0.05cm}+\hspace{-0.05cm}4\hspace{-0.05cm}+\hspace{-0.05cm}5\hspace{-0.05cm}+\hspace{-0.05cm}2\hspace{-0.05cm}+\hspace{-0.05cm}5) \cdot 3\big ] \hspace{-0.2cm} \mod 10 \]

\[\Rightarrow \hspace{0.3cm} z_{13}= 10 - (108 \hspace{-0.2cm} \mod 10) = 10 - 8 = 2 \hspace{0.05cm}. \]

With both variants, in contrast to the above parity check code (SPC), number twists such as  $57 \, \leftrightarrow 75$  are also recognised, since different positions are weighted differently here

.

$\text{Example 3:   Barcode (one-dimensional)}$
The most widely used error-detecting code worldwide is the bar code or bar code (English:   Bar Code) for marking products, for example according to  EAN–13  (European Article Number ) with 13 digits.

One-dimensional bar code

• These are represented by bars and gaps of different widths and can be easily decoded with an opto–cial reader.
• The first three digits indicate the country (for example Germany:   between 400 and 440), the next four or five digits the manufacturer and the product.
• The last digit is the check digit  $z_{13}$, which is calculated exactly as for ISBN–13.

Some Introductory Examples of Error Correction

$\text{Example 4:   2D–Barcodes For Online–Tickets}$
If you book a Deutsche Bahn ticket online and print it out, you will find an example of a two-dimensional barcode, namely the  Aztec–Code developed in 1995 by Andy Longacre at the Welch Allyn company in the USA, with which amounts of data up to  $3000$  characters can be encoded. Due to the  Reed–Solomon–error correction    reconstruction of the data content is still possible even if up to  $40\%$  of the code has been destroyed, for example by bending the ticket or by coffee stains.

2D–Barcodes: Aztec– And QR–Code

On the right is a $\rm QR–Code$  (Quick Response) with associated content. The QR–code was developed in 1994 for the automotive industry in Japan to mark components and also allows error correction. In the meantime, the use of the QR–code has become very diverse. In Japan, it can be found on almost every advertising poster and on every business card. It is also becoming more and more popular in Germany.

All 2D–barcodes have square markings to calibrate the reader. You can find details on this in [KM+09].

$\text{Example 5:   Codes For Satellites– And Space Communications}$
One of the first areas of application of error correction methods was communication from/to satellites and space shuttles, i.e. transmission routes characterised by low transmission powers and large path losses. As early as 1977, channel coding was used in the  space–mission Voyager 1  to Neptune and Uranus, in the form of serial concatenation of a  Reed–Solomon–Code  and a  convolutional code.

Thus, the power parameter  $10 · \lg \; E_{\rm B}/N_0 \approx 2 \, \rm dB$ was already sufficient to achieve the required error rate  $5 · 10^{-5}$  (related to the compressed data after source coding). Without channel coding, on the other hand, almost  $9 \, \rm dB$  are required for the same error rate, i.e. a factor  $10^{0.7} ≈ 5$  greater transmission power.

The planned Mars project (data transmission from Mars to Earth with  $\rm 5W$–lasers) will also only be successful with a sophisticated coding scheme

.

$\text{Example 6:   Channel Codes For Mobile Communikations}$
A further and particularly high-turnover application area that would not function without channel coding is mobile communication. Here, unfavourable conditions without coding would result in error rates in the percentage range and, due to shadowing and multipath propagation (echoes), the errors often occur in bundles. The error bundle length is sometimes several hundred bits.

• For voice transmission in the GSM–system, the  $182$  most important (class 1a and 1b) of the total  260  bits of a voice frame  $(20 \, \rm ms)$  together with a few parity– and tailbits are convolutionally coded $($with memory  $m = 4$  and rate $R = 1/2)$  and scrambled. Together with the  $78$  less important and therefore uncoded bits of class 2, this results in the bit rate increasing from  $13 \, \rm kbit/s$  to  $22.4 \, \rm kbit/s$ .
  

• One uses the (relative) redundancy of $r = (22.4 - 13)/22.4 ≈ 0.42$  for error correction. It should be noted that  $r = 0.42$  because of the definition used here, $42\%$  of the encoded bits are redundant. With the reference value "bit rate of the uncoded sequence" we would get  $r = 9.4/13 \approx 0.72$  with the statement:   To the information bits are added  $72\%$  check bits.
  

• For  UMTS  (Universal Mobile Telecommunications System),  Convolutional Codes  with the rates  $R = 1/2$  or  $R = 1/3$  are used. In the UMTS–modes for higher data rates and correspondingly lower spreading factors, on the other hand, one uses  Turbo–Codes  of the rate  $R = 1/3$  and iterative decoding. Depending on the number of iterations, gains of up to  $3 \, \rm dB$ can be achieved compared to convolutional coding.

$\text{Example 7:   Error Protection of the Compact Disc}$
For a CD (Compact Disc), one uses cross–interleaved  Reed–Solomon–Codes  (RS) and then a so-called   Eight–to–Fourteen–Modulation. Redundancy is used for error detection and correction. This coding scheme shows the following characteristics:

• The common code rate of the two RS–component codes is  $R_{\rm RS} = 24/28 · 28/32 = 3/4$. Through the 8–to–14–modulation and some control bits, one arrives at the total code rate  $R ≈ 1/3$.
  

• In the case of statistically independent errors according to the  BSC–model  (Binary Symmetric Channel ),a complete correction is possible as long as the bit error rate does not exceed the value  $10^{-3}$ .
  

• The CD–specific  Cross Interleaver  scrambles  $108$  blocks together so that the  $588$  bits of a block  $($each bit corresponds to approx.   $0.28 \, \rm {µ m})$  are distributed over approximately  $1.75\, \rm cm$.
  

• With the code rate  $R ≈ 1/3$  one can correct approx.  $10\%$  "Erasures". The lost values can be reconstructed (approximately) by interpolation   ⇒  Error concealment.
  
  

In summary, if a CD has a scratch of  $1. 75\, \rm mm$  in length in the direction of play (i.e. more than  $6000$  consecutive erasures), still  $90\%$  of all the bits in a block are error-free, so that even the missing  $10\%$  can be reconstructed, or at least the erasures can be disguised so that they are not audible.
.

A demonstration of the CD's ability to correct follows on the next page

.

The "Slit CD" - A Demonstration By The LNT of TUM

At the end of the 1990s, staff of the  Chair of Communications Engineering of the Technical University of Munich  led by professor  Joachim Hagenauer  eliberately damaged a music–CD by cutting a total of three slits, each more than one millimetre wide. Thus, almost  $4000$  consecutive bits of audio coding are missing with each defect.

„A Slit CD” of The  $\rm LNT/TUM$

The diagram shows the "slit CD":

• Both track 3 and track 14 have two such defective areas on each revolution.
• You can visualise the music quality with the help of the two audio players (playback time approx. 15 seconds each).
• The theory of this audio–demo can be found in the  $\text{Example 7}$  on the previous page.
  

Track 14:

Track 3:

Summary of this audio demo:

• The CD's error correction is based on two serial–concatenated  Reed–Solomon–Codes  and one  Eight–to–Fourteen–Modulation.The total code rate for RS–error correction is  $R = 3/4$.
  

• As important for the functioning of the CD as the codes is the interposed interleaver, which distributes the erased bits ("Erasures") over a length of almost  $2 \, \rm cm$ .
  

• In  Track 14  the two defective areas are sufficiently far apart. Therefore, the Reed–Solomon–decoder is able to reconstruct the missing data.
  

• In  Track 3  the two error blocks follow each other in a very short distance, so that the correction algorithm fails. The result is an almost periodic clacking noise.
  
  

We would like to thank Rainer Bauer,  Thomas Hindelang  and  Manfred Jürgensfor the permission to use this audio–demo.

Interplay Between Source and Channel Coding

Message transmission of natural sources such as speech, music, images, videos, etc. is usually done according to the discrete-time model outlined below.

Image Transmission With Source and Channel Coding

From [Liv10] the following should be noted:

• Source and sink are digitised and represented by (approximately equal numbers of ) zeros and ones.
  

• The source encoder compresses the binary data – in the example a digital photo – and thus reduces the redundancy of the source.
  

• The channel encoder adds redundancy again, and specifically so that some of the errors that occurred on the channel can be corrected in the channel decoder.
  

• A discrete-time model with binary input and output is used here for the channel, which should also suitably take into account the components of the technical transmit– and receive equipment (modulator, decision maker, clock recovery).
  
  

With correct dimensioning of sources– and channel coding, the quality of the received photo is sufficiently good, even if the sink symbol sequence will not exactly match the source symbol sequence due to error patterns that cannot be corrected. One can detect a (red marked) bit error within the sink symbol sequence.

$\text{Example 8:}$  For the above graph, it was assumed, as an example and for the sake of simplicity, that

• the source symbol sequence has only the length  $40$ ,
• the source encoder compresses the data by a factor of  $40/16 = 2.5$  and
• the channel encoder  $50\%$  adds redundancy.

Thus, only  $24$  encoder symbols have to be transmitted instead of  $40$  source symbols, which reduces the overall transmission rate by  $40\%$ .

If one were to dispense with source encoding by transmitting the original photo in BMP–format rather than the compressed JPG–image, the quality would be comparable, but a bit rate higher by a factor  $2.5$  and thus much more effort would be required.

$\text{Example 9:}$  If one were to dispense with both source– and channel coding, i.e. transmit the BMP–data directly without error protection, the result would be extremely poor despite  $($by a factor  $40/24)$  greater bit rate.

Image Transmission Without Source and Channel Coding

$\text{Example 10:}$  Now let's consider the case of directly transferring the compressed data (for example JPG) without error-proofing measures.

• Since the compressed source has little redundancy left, any single transmission error will cause entire blocks of images to be decoded incorrectly.
  
• This coding scheme (source coding but no channel coding) should be avoided at all costs

.

Block Diagram and Requirements

In the further sections, we will start from the sketched block diagram with channel encoder, digital channel and channel decoder.

Block Diagram Describing Channel Coding

Dabei gelten folgende Voraussetzungen: The following conditions apply:

• The vector  $\underline{u} = (u_1, u_2, \text{...} \hspace{0.05cm}, u_k)$  denotes an  information block  with  $k$  symbols.
• Mostly we restrict ourselves to binary symbols (bits)   ⇒   $u_i \in \{0, \, 1\}$ for $i = 1, 2, \text{...} \hspace{0.05cm}, k$  with equal occurrence probabilities for zeros and ones.
  

• Each information block  $\underline{u}$  is represented by a  codeword  (or a  codeblock)  $\underline{x} = (x_1, x_2, \text{. ..} \hspace{0.05cm}, x_n)$  with  $n \ge k$, $x_i \in \{0, \, 1\}$  represented. One then speaks of a binary  $(n, k)$–block code  $C$. We denote the assignment by  $\underline{x} = {\rm enc}(\underline{u})$, where "enc" stands for "encoder–function".
  

• The  receive word $\underline{y}$  results from the codeword  $\underline{x}$  by  Modulo–2–Addition with the likewise binary error vector  $\underline{e} = (e_1, e_2, \text{. ..} \hspace{0.05cm}, e_n)$, where "$e= 1$" represents a transmission error and "$e= 0$" indicates that the  $i$–th bit of the codeword was transmitted correctly. The following therefore applies:

\[\underline{y} = \underline{x} \oplus \underline{e} \hspace{0.05cm}, \hspace{0.5cm} y_i = x_i \oplus e_i \hspace{0.05cm}, \hspace{0.2cm} i = 1, \text{...} \hspace{0.05cm} , n\hspace{0.05cm}, x_i \hspace{-0.05cm} \in \hspace{-0.05cm} \{ 0, 1 \}\hspace{0.05cm}, \hspace{0.5cm}e_i \in \{ 0, 1 \}\hspace{0.5cm} \Rightarrow \hspace{0.5cm}y_i \in \{ 0, 1 \}\hspace{0.05cm}.\]

The description by the  Digital Channel Model  – i.e. with binary input and output – is, however, only applicable if the transmission system makes hard decisions – see  AWGN–Channel at Binary Input. Systems with  soft decision  cannot be modelled with this simple model.

• The vector  $\underline{v}$  after  channel decoding  has the same length  $k$  as the information block  $\underline{u}$. We describe the decoding process with the "decoder–function" as  $\underline{v} = {\rm enc}^{-1}(\underline{y}) = {\rm dec}(\underline{y})$. In the error-free case, analogous to  $\underline{x} = {\rm enc}(\underline{u})$  also  $\underline{v} = {\rm enc}^{-1}(\underline{y})$.
  

• If the error vector  $\underline{e} \ne \underline{0}$, then  $\underline{y}$  is usually not a valid element of the block code used, and the decoding is then not a pure mapping  $\underline{y} \rightarrow \underline{v}$, but an estimate of  $\underline{v}$ based on maximum match (mimimum error probability).
  

Important Definitions for Block Coding

We now consider the exemplary binary block code

\[\mathcal{C} = \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm} (0, 1, 0, 1, 0) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 0, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 1, 1) \}\hspace{0.05cm}.\]

This code would be unsuitable for the purpose of error detection or –correction. But it is constructed in such a way that it clearly illustrates the calculation of important descriptive variables:

• Each individual codeword  $\underline{u}$  is described by five bits. Throughout the book, we express this fact by the  codeword length  (English:  Code Length )  $n = 5$.

• The above code contains four elements. Thus the  code size  (English:   Size )  $|C| = 4$. Accordingly, there are also four unique mappings (English:  Mappings ) between  $\underline{u}$  and  $\underline{x}$.

• The length of an information block  $\underline{u}$   ⇒   Information block length  is denoted by  $k$ . Since for all binary codes  $|C| = 2^k$  holds, it follows from  $|C| = 4$  that  $k = 2$. The assignments between  $\underline{u}$  and  $\underline{x}$  in the above code are  $C$:

\[\underline{u_0} = (0, 0) \hspace{0.2cm}\leftrightarrow \hspace{0.2cm}(0, 0, 0, 0, 0) = \underline{x_0}\hspace{0.05cm}, \hspace{0.8cm} \underline{u_1} = (0, 1) \hspace{0.2cm}\leftrightarrow \hspace{0.2cm}(0, 1, 0, 1, 0) = \underline{x_1}\hspace{0.05cm}, \]

\[\underline{u_2} = (1, 0)\hspace{0.2cm} \leftrightarrow \hspace{0.2cm}(1, 0, 1, 0, 1) = \underline{x_2}\hspace{0.05cm}, \hspace{0.8cm} \underline{u_3} = (1, 1) \hspace{0.2cm} \leftrightarrow \hspace{0.2cm}(1, 1, 1, 1, 1) = \underline{x_3}\hspace{0.05cm}.\]

• The code has the  code rate  $R = k/n = 2/5$ . Accordingly, its redundancy is  $1-R$, that is  $60\%$. Without error protection $($so for the case  $n = k)$  the code rate  $R = 1$.
  

• A small code rate indicates that of the  $n$  bits of a codeword, very few actually carry information. For example, a repetition code  $(k = 1)$  with  $n = 10$  has a code rate  $R = 0.1$.
  

• The  Hamming–weight  $w_{\rm H}(\underline{x})$  of the codeword  $\underline{x}$  indicates the number of codeword elements  $x_i \ne 0$ . For a binary code  ⇒   $x_i \ne 0$  $w_{\rm H}(\underline{x})$  is equal to the sum  $x_1 + x_2 + \hspace{0.05cm}\text{...} \hspace{0.05cm}+ x_n$. In the example:

\[w_{\rm H}(\underline{x}_0) = 0\hspace{0.05cm}, \hspace{0.4cm}w_{\rm H}(\underline{x}_1) = 2\hspace{0.05cm}, \hspace{0.4cm} w_{\rm H}(\underline{x}_2) = 3\hspace{0.05cm}, \hspace{0.4cm}w_{\rm H}(\underline{x}_3) = 5\hspace{0.05cm}. \]

• The  Hamming–distance  $d_{\rm H}(\underline{x}, \ \underline{x}\hspace{0.03cm}')$  between the codewords  $\underline{x}$  and  $\underline{x}\hspace{0.03cm}'$  denotes the number of bit positions in which the two codewords differ:

\[d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_1) = 2\hspace{0.05cm}, \hspace{0.4cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_2) = 3\hspace{0.05cm}, \hspace{0.4cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_3) = 5\hspace{0.05cm},\hspace{0.4cm} d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_2) = 5\hspace{0.05cm}, \hspace{0.4cm} d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_3) = 3\hspace{0.05cm}, \hspace{0.4cm} d_{\rm H}(\underline{x}_2, \hspace{0.05cm}\underline{x}_3) = 2\hspace{0.05cm}.\]

• An important property of a code $C$ that significantly affects its ability to be corrected is the  minimum distance  between any two code words:

\[d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')\hspace{0.05cm}.\]

$\text{Definition:}$  A  $(n, \hspace{0.05cm}k, \hspace{0.05cm}d_{\rm min})\text{ – block code}$  has the codeword length  $n$, the information block length  $k$  and the minimum distance  $d_{\rm min}$.

• According to this nomenclature, the example considered here is a  $(5, \hspace{0.05cm}2,\hspace{0.05cm} 2)$ – block code.
• Sometimes one omits the specification of  $d_{\rm min}$  and then speaks of a  $(n,\hspace{0.05cm} k)$ – block code.

Examples of Error Detection and Correction

The variables just defined are now to be illustrated by two examples.

{{GraueBox|TEXT= $\text{Example 11:}$     $\text{(4, 2, 2)–block code}$

In the graphic, the arrows pointing to the right or left illustrate the coding process or decoding:

$$\underline{u_0} = (0, 0) \leftrightarrow (0, 0, 0, 0) = \underline{x_0}\hspace{0.05cm},\hspace{0.5cm} \underline{u_1} = (0, 1) \leftrightarrow (0, 1, 0, 1) = \underline{x_1}\hspace{0.05cm},$$

$$\underline{u_2} = (1, 0) \leftrightarrow (1, 0, 1, 0) = \underline{x_2}\hspace{0.05cm},\hspace{0.5cm} \underline{u_3} = (1, 1) \leftrightarrow (1, 1, 1, 1) = \underline{x_3}\hspace{0.05cm}.$$

(4, 2, 2)–Block Code For Error Detection

On the right, all  $2^4 = 16$  possible receive words  $\underline{y}$  are shown:

• Of these,  $2^n - 2^k = 12$  can only be due to bit errors.
• If the decoder receives such a "white" code word, it detects an error, but it cannot correct it because  $d_{\rm min} = 2$ .
• For example, if it receives  $\underline{y} = (0, 0, 0, 1)$, then with equal probability  $\underline{x_0} = (0, 0, 0, 0)$  or  $\underline{x_1} = (0, 1, 0, 1)$ may have been sent}
  .

(5, 2, 3)–Block Code For Error Correction

$\text{Example 11:}$     $\text{(5, 2, 3)–Block Code}$

Here, because of $k=2$, there are four valid code words :

$$\underline{x_0} = (0, 0, 0, 0, 0)\hspace{0.05cm},\hspace{0.5cm} \underline{x_1} =(0, 1, 0, 1, 1)\hspace{0.05cm},$$

$$\underline{x_2} =(1, 0, 1, 1, 0)\hspace{0.05cm},\hspace{0.5cm}\underline{x_3} =(1, 1, 1, 0, 1).$$

The graphic shows the receiver side, where you can recognise falsified bits by the italics.

• Of the  $2^n - 2^k = 28$  invalid codewords, now  $20$  can be assigned to a valid codeword (fill colour:   red, green, blue or ochre), assuming that a single bit error is more likely than their two or more.
• For each valid codeword, there are five invalid codewords, each with only one corruption   ⇒   Hamming–Distance  $d_{\rm H} =1$. These are indicated in the respective square with red, green, blue or ochre background colour.
• Error correction is possible for these due to the minimum distance  $d_{\rm min} = 3$  between the codewords.
• Eight receive words are not decodable. For example, the receive word  $\underline{y} = (0, 0, 1, 0, 1)$  could have arisen from the codeword  $\underline{x}_0 = (0, 0, 0, 0)$  but also from the codeword  $\underline{x}_3 = (1, 1, 1, 0, 1)$. In both cases, two bit errors would have occurred.

On the Nomenclature in This Book

One of the objectives of our learning tutorial $\rm LNTww$  was to describe the entire field of communications engineering and the associated basic subjects with uniform nomenclature. In this most recently tackled book " Channel Coding" some changes have to be made with regard to the nomenclature after all. The reasons for this are:

• Coding theory is a largely self-contained subject and few authors of relevant reference books on the subject attempt to relate it to other aspects of digital signal transmission.
  

• The authors of the most important books on channel coding – English-language and German – largely use a uniform nomenclature. We therefore do not take the liberty of squeezing the designations for channel coding into our communication technology–scheme.
  
  

Some nomenclature changes compared to the other  $\rm LNTww$–books shall be mentioned here:

• All signals are represented by sequences of symbols in vector notation. For example  $\underline{u} = (u_1, u_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, u_k)$  the   Quellensymbolfolge  and  $\underline{v} = (v_1, v_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, v_k)$  the sink symbol sequence. Previously, these symbol sequences were designated  $\langle q_\nu \rangle$  and  $\langle v_\nu \rangle$  respectively.
  

• The vector $\underline{x} = (x_1, x_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, x_n)$   now denotes the discrete-time equivalent to the transmit signal  $s(t)$, while the receive signal  $r(t)$ is described by the vector  $\underline{y} = (y_1, y_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, y_n)$ . The code rate is the quotient   $R=k/n$   with   $0 \le R \le 1$ and the number of check bits is given by  $m = n-k$.

• In the first main chapter the elements  $u_i$  and  $v_i$   $($each with index  $i = 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, k)$  of the vectors  $\underline{u}$  and  $\underline{v}$  always binary  $(0$  or  $1)$, as are the  $n$  elements  $x_i$  of the codeword  $\underline{x}$. For digital channel model  (BSC,  BEC,  BSEC) also applies to the  $n$  received values  $y_i \in \{0, 1\}$.

• The   AWGN–Channel  is characterised by real-valued output values  $y_i$ . The code word estimator in this case extracts from the vector $\underline{y} = (y_1, y_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, y_n)$   the binary vector  $\underline{z} = (z_1, z_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, z_n)$ to be compared with the codeword  $\underline{x}$ .

• The transition from  $\underline{y}$  to  $\underline{z}$  is done by threshold decision   ⇒   Hard Decision or according to the MAP–criterion   ⇒   Soft Decision. For equally likely input symbols, the "Maximum Likelihood"–estimation also leads to the minimum error rate.

• In the context of the AWGN–model, it makes sense to represent binary code symbols $x_i$ bipolar (i.e. $\pm1$). This does not change the statistical properties. In the following, we mark the bipolar signalling with a tilde. Then applies:

\[\tilde{x}_i = 1 - 2 x_i = \left\{ \begin{array}{c} +1\\ -1 \end{array} \right.\quad \begin{array}{*{1}c} {\rm if} \hspace{0.15cm} x_i = 0\hspace{0.05cm},\\ {\rm if} \hspace{0.15cm}x_i = 1\hspace{0.05cm}.\\ \end{array}\]

Exercises For The Chapter

Aufgabe 1.1: Zur Kennzeichnung aller Bücher

Aufgabe 1.2: Einfacher binärer Kanalcode

Aufgabe 1.2Z: 3D–Darstellung von Codes