Exercises

Contents

Exercises#

ECFF 1992 Pretzel, Oliver. Error-Correcting Codes and Finite Fields. Oxford University Press Applied Mathematics and Computing Science Series.

1#

1.1

A spelling checker is a kind of error processor for typewritten English. Consider what strategies a spelling checker should adopt. Why is the symmetric channel model which is used for binary codes not adequate for a spelling checker?

1.2

Extend the definition of the \((8, 7)\) parity check code to define an \((n + 1, n)\) parity check code, adding a parity check bit to every block of \(n\) message bits. What are the advantages and disadvantages of taking \(n\) large in this definition?

Advantages

The code is economical. If the original message has length \(n\) then the encoded message has length \(n + 1\) for any \(n\). For large \(n\), there is hardly an increase in the length.

Disadvantages

The code is not reliable. The larger the \(n\) the more errors the code is susceptible to, but it cannot handle more than just one error.

1.3

Extend the definition of the triple repetition code to define an \(n\)-fold repetition code. What are the advantages and disadvantages of taking \(n\) large in this definition?

Advantages

The code is reliable. The larger the \(n\) the more robust the code is to undetected or uncorrected errors. For large \(n\), the code is near immune to failing to detect or correct error.

Disadvantages

The code is uneconomical. The encoded message is \(n\) times as long as the original. For large \(n\), there is an unwieldy increase in the length.

1.4

There is one pattern of incorrect equations that the triple check code does not exploit to correct an error. Try to modify the definition of the triple check code to produce a code which adds three check bits to every block of four message bits and can still correct any single error.

\( \begin{aligned} a + b + d + x &= 2k \\ a + c + d + y &= 2k \\ b + c + d + z &= 2k \\ \end {aligned} \)

\( \begin{array}{rrr} \text{message } abcd & \text{encoded message } abcdxyz \\ \hline 0000 & 0000000 \\ 0001 & 0001111 \\ 0010 & 0010011 \\ 0011 & 0011100 \\ 0100 & 0100101 \\ 0101 & 0101010 \\ 0110 & 0110110 \\ 0111 & 0111001 \\ 1000 & 1000110 \\ 1001 & 1001001 \\ 1010 & 1010101 \\ 1011 & 1011010 \\ 1100 & 1100011 \\ 1101 & 1101100 \\ 1110 & 1110000 \\ 1111 & 1111111 \\ \end {array} \)

This modified triple check code works the same way as the original triple check code with the addition that if the fourth message bit \(d\) is incorrect then all three conditions fail.

1.5

Show that it is not possible to devise a code adding three check bits to every block of five message bits in such a way that the code can correct every single error.

Since there are five message bits but only three check bits there is no unique set of failed conditions to check the fifth bit.

1.6

The standard ASCII code used to represent printable and non-printable characters in computers contains 128 7-bit symbols: for instance (in the usual descending order) ‘0’ is 0110000, a space ‘ ‘ is 0100000, ‘A’ is 1000001, and ‘a’ is 1100001. Devise a single error-correcting code for transmitting ASCII, using as few check bits as possible. Give encoding and error-correcting rules.

Contents