3. Bug fixes

The extra redundancy bits can not only detect transmission errors, they are also capable of correcting the detected errors.

There are many systems that can only transmit information once, they do not allow the correct data to be requested from the sender again (digital terrestrial television, satellite television, etc.). Physical media such as CD-ROM, USB flash drives or SSD Disks have the same problem; once the information is corrupted, it cannot be requested from the issuer again.

In all these cases it is not enough to detect errors, it is also necessary to be able to correct them based on the information received.

Bug fixes with parity bits

The simplest example of code that corrects errors is a system with double parity, horizontal and vertical. This example is not used in practice to correct errors, but it is much easier to visualize than other more capable and much more complex codes.

We start with a table with 16 bits of information (4x4):

16 bits of data.

To this table we add 4 horizontal parity bits and another 4 vertical parity bits:

16 data bits surrounded by 8 parity bits, no errors.

Once the table is formed we can transmit it and with the redundant information we can detect and correct any 1-bit error.

If an error occurs in one bit of the data, the parity information will not be correct in a row parity bit and will not be correct in a column parity bit:

16 bits of data with one bit error, surrounded by 8 parity bits of which 2 do not match the data.

This indicates that the bit corresponding to that row and that column has changed:

Parity bits indicating error in yellow, wrong bit in orange.

With that information we can correct the erroneous bit to return to the original table.

On the other hand, if what changes by mistake is a parity bit, only that bit will be the one that does not match the table. All other parity bits will be correct, indicating that it is the lone bit that has changed:

Bad parity bit in yellow. It's the only bit that doesn't match the others.

With that information we can correct the erroneous parity bit to return to the original table:

16 data bits surrounded by 8 parity bits, no errors.

Bug Fix Codes

The error correction codes used in practice are capable of correcting bursts of several error bits in the same block of information.

The most popular corrective codes are the following:

1. Reed-Solomon codes.

   They are the simplest to implement and the oldest. They have been used in CD, DVD, digital TV, ADSL, etc.

2. Convolutional Codes.

   Used in GSM mobile telephone networks, old WiFi networks or in space probes.

3. Turbo Codes.

   Employed in satellite communications and 3G mobile telephone networks. They have the disadvantage of being patented.

4. LDPC or Gallager codes.

   They are the most recent. They are used in the most modern WiFi networks, in 5G mobile telephony, in the highest speed wired Ethernet networks and in the latest versions of Digital TV.

Exercises

1. Write your name on a piece of paper.

   On the paper, draw and fill in the following 4x4-bit table with random binary data (zero or one), leaving a gap in one of the squares.

   Then fill in the parity bits for each row and each column, taking into account that there should be a one (1) in the space left free.

   Now write a zero (0) in the space left before. This will be the transmission error.

   Exchange the table with a classmate so that each one can solve where the error is in the other's table.

   

2. Draw and fill the following 4x4 bit table with random binary data.

   Then fill in the parity bits of each row and each column, taking into account that you must write one the opposite of what it actually counts (error in a parity bit).

   Exchange the table with a classmate so that each one can solve where the error is in the other's table.

   

3. Can the error correction codes used in practice only correct one erroneous bit in each data block?

4. Write the name of three error codes used in practice and write two applications of each of them.