A simple way to detect errors is the use of a check digit. When using a check

digit, the original data is appended by extra data that is calculated from the code.

Let us consider the International Standard Book Number $($ISBN$),$ which is used

to identify books. In particular, we will consider the ISBN$-10$ check digit.

Using ISBN$-10,$ books are identified by strings of the form

x$1$x$2$x$3$ x$9$x$10,$

where x$1,,$ x$9$ are digits from $09($inclusive$)$ and x$10$ can be either $09$ or X

$($which is used to represent $10)$ so that

$10$

$$

i$=1$

$(11$ i$)$xi

is divisible by $11.$

For example, $0-306-40615-2$ is a valid IBSN$-10$ code, because

$(0\backslash$times $10)+(3\backslash$times $9)+(0\backslash$times $8)+(6\backslash$times $7)+(4\backslash$times $6)+(0\backslash$times $5)$

$+(6\backslash$times $4)+(1\backslash$times $3)+(5\backslash$times $2)+(2\backslash$times $1)=132$

and $132=11\backslash$times $12,$ which is clearly divisible by $11.$

$($a$)$ Show that $0-205-08005-7$ is a valid ISBN$-10.$

ISBN$-10$ has the ability to detect two common types of error:

$$ When a single digit is changed, the check digit sum fails.

$$ When two $($distinct$)$ neighbouring digits are swapped, the check digit sum

fails.

It will fail when other types of error are made.

$($b$)$ Demonstrate and explain an error that is not detected by ISBN$-10.$

Various types of check digits exist and they often take advantage of some math$-$

ematical structure that allows one to prove the error detection$/$correction abilities.

Often, the mathematical structures are quite complicated and many are beyond

the scope of this module.

MATH$4004$

$($c$)$ Cyclic redundancy check $($CRC$)$ codes are codes commonly used in net$-$

works to detect errors. CRC codes are based on polynomials where the

coefficients are $0$s and $1$s$,$ because data itself is binary. For example, the

CRC based on x$3+$ x $+1$ is used in some mobile phone networks. Rather

than work with the polynomial itself, the expression is converted into the bit

string of coefficients. For example,

x$3+$ x $+1=$ x$3+0$x$2+$ x $+17->1011.$

Note: it is important to include the $$missing$$ x$2$ term to encode the polynomial

correctly.

We will not cover all of the details here, but it can be useful to use a polyno$-$

mial that does not factorise in a CRC code $($such polynomials are said to be

irreducible$).$

i$.$ Using real numbers, factorise the polynomial

x$2+6$x $16.$

$1$ mark

ii$.$ Explain why x$2+1$ is irreducible using real numbers.

$2$ marks

$($d$)$ Consider codes of the form abcd, where a$,$ b$,$ c$,$ d are positive integers such

that

ad$2$ bd $+$ c $=0.$

Note: this code is not a particularly good one and it is not used in practice.

i$.$ If a $=1,$ b $=4,$ c $=4,$ what must d be$?$

ii$.$ If a $=2,$ c $=4,$ d $=2,$ what must b be$?$