MATH1005/MATH6005 Written Assignment 2: Error detecting codes

Most communication channels are subject to noise that creates errors.  We say the channel is unreliable. If you have played the game of “telephone”, also known as  “whis- pers”, you have seen an extreme example of the errors that are brought into communi- cation via unreliable channels.  One needs to realize that almost all of the channels of communication we use are unreliable.

Why are channels unreliable?  Communication channels are subject to interference. Even when communication takes place using highly engineered equipment such as satellite and microwave transmission, signals fade, while weather and other disturbances occur between the transmitter and receiver.  For example, here is a website that discusses the effects that heavy rain and snow, ice and water accumulation can have on a satellite TV

reception: http://dish-cable. com/rain_fade. htm

Unreliable channels  are  a problem because we need  communication to be reliable! One way to create reliable communication over unreliable channels is to add redundant

information to the message in a clever way so that one can say either:

(1) this message has definitely been corrupted and should not be acted upon; or

(2) there is no evidence that this message has been corrupted so it is probably an accurate record of what was sent.

What we are describing is an error detecting code.

1    Error Detecting Codes

Most error detecting codes work as follows.  Let A denote the set of all possible messages. Let C denote another nonempty set.  Let h : A 一 C denote a function called a hash function. When a sender wishes to transmit a message m e A, they instead transmit a pair (m,c), and element of A X C, with h(m) = c.  So the sender sends the message and something else which is computed from the message. The recipient receives a transmission (m( , c( ).  If the transmission went well, then m = m(  and c(  = h(m);  but the recipient cannot know mto check this.  The recipient can only compute h(m( ) and check it against c( .   If  h(m( )   c( ,  then the recipient knows that something definitely went wrong in the transmission; in this case, the recipient should not act upon the message (they may instead ask for a retransmission—an  automatic  repeat request  might be built into the communications protocol).  In the case that h(m( ) = c( , no error is detected.  This does not necessarily mean that m  =  m( .   Instead  it  means  that  one  of the following has

occurred:

1. m = m(  and c = c(

2. m  m(  and c = c(  and h(m) = h(m( )

3. m  m(  and c  c(  and h(m( ) = c(

The first case is the desirable scenario that the message was transmitted accurately and sender has no reason to doubt its accuracy.  The second and third cases are scenarios in which the message contains errors, but the recipient has no reason to suspect this. These are dangerous, so we would like to minimize the occurrences of the second and third cases.  The likelihood of the second case depends on how many different messages map to the same “hash code”. The likelihood of the the third case also depends on how many different message maps to the same hash-code, and how random-like the function h is.  An excellent choice of h makes the second and third possibilities unlikely, while keeping C small so that h(m) is small for every message, and so that the transmissions are not much longer than the messages.

2    ISBN-10

Notational Convention:  In what follows, for any positive integer d and any integers

a,b, we shall write a 三 b as alternate notation for a 三 b   ( mod d).  Thus a 三 b means d                                                                                                                               d

that b — a is divisible by d (equivalently, a and b leave the same remainder upon division

by d).

An ISBN-10 is a  10-digit  code  assigned to a publication  (books  etc).   Its  use  was standard in the publishing industry between 1970 and 2007. The first 9 characters of an ISBN-10 code are digits that uniquely identify the publication (the title, author, edition etc).  The tenth character, which is either a digit or the letter X, is a check character

used to detect errors in transmission or recording.

More formally, let X = 10 and

D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},

C = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X},

A =  X D X · · ·  .

9 times

We define a function h : A 一 C by the rule

A(a1 ,..., a9 ) e A    h((a1 ,... a9 ))

 iai.

When the ISBN-10 is written, no parentheses or commas are included.  Often hyphens are used (for reasons we may ignore).

For example, the paperback third edition of Herstein’s “Abstract Algebra” was assigned the ISBN-10 code 0471368792. In this case we have

a1  = 0, a2  = 4, a3  = 7, a4  = 1, a5 = 3, a6 = 6, a7 = 8, a8 = 7, a9 = 9.

Then

iai = 1(0) + 2(4) + 3(7) + 4(1) + 5(3) + 6(6) + 7(8) + 8(7) + 9(9)

= 277 = 25(11) + 2.

It follows that that the message (9 digits that uniquely identify the publication)is m = (0, 4, 7, 1, 3, 6, 8, 7, 9), the hash-code (something computed from the message) is h(m) = 2 and the transmission (the ISBN-10) is the concatenation of these with the parentheses

omitted.

Definition 1. An element (a1 ,..., a9 , c) ∈ D × ... D × C is a valid ISBN-10 if

c ≡

11

 iai.

Lemma 2. An element (a1 ,..., a9 , a10 ) ∈ D × ... D × C is a valid ISBN-10 if and only

if

 iai  0.

Proof. Let (a1 ,..., a9 , a10 ) e D X ...D X C. Then

(a1 ,..., a9 , a10 )                                          (is a valid ISBN-10)

今      a10  11(三)  iai                                                    (using the definition above)

今      0 11(三)（  iai）- (a10 )

今      011(三)（ iai）+ (-1)a10

今      0 11(三) iai）+ 10a10                                                    (because 10 11(三) -1)

今      0 11(三)  iai.

Theorem 3 (The ISBN-10 detects any transmission error in which exactly one character

is changed). Let m = (a1 ,... a9 , a10 ) and m\  = (a,..., a, a) be elements of DX ... DX

C.  If m is  a valid ISBN-10, and m and m\  differ in exactly one component, then m\  is

not a valid ISBN-10.

Proof. Suppose that misa valid ISBN-10, and m and m\  differ in exactly one component.

Then there exists an integer j such that 1 三 j  三 10 and a  aj  and a = ak  for all

integers k such that 1 三 k 三 10 and k  j.

By Lemma 2, to show that m\  is not a valid ISBN-10 it suffices to show that 0 三1\1  ia .

Since a d(三) b if and only if d divides b - a, it suffices to show that  ia is not divisible

by 11. Now

 ia 11(三)  ia — 0

11(三) ia — iai               (by Lemma 2, because m is a valid ISBN-10)

11(三) i(a — ai )                    (using algebraic properties of summation)

11(三)j(a — aj )                                         (because ak  = a when k j).

Since 1  三 j  三 10,  11 does not divide j.  Since 0  三 aj  三  10  and  0  三  a  三  10,  — 10  三 aj  — a 三 10. Since aj   a , aj  — a  0. Hence

aj  — a e {— 10, . . . , — 1} n {1, . . . 10},

and 11 does not divide aj  — a. By the Prime Divisibility Property, 11 does not divide

j(aj  — a). Hence m\  is not a valid ISBN-10.                                                                    

Theorem 4. If any two distinct digits in a valid ISBN-10 are transposed, then the re-

sulting string is not a valid ISBN-10.

Proof. Let (a1 ,..., a10 ), (b1 ,..., b10 ) e D X ··· X D X C.  Suppose that (a1 ,..., a10 ) is a

valid ISBN-10 and (a,..., a) is obtained from (a1 ,..., a10 ) by transposing two distinct

digits. Then there exist integers j,k such that 1 三 j < k 三 10 and a = ak  and a = aj

and a = ai  for all integers i such that 1 三 i 三 10 and i  j,k.  The fact that the digits

transposed are distinct means that aj   ak .

By Lemma 2, to show that (a,..., a) is not a valid ISBN-10 it suffices to show that

10                                                                                                                                                                          10

0 三1\1   ia .  Since a d(三) b if and only if d divides b — a, it suffices to show that  ia is

not divisible by 11. Now

 ia — 0

 ia —  iai

 i(a — ai )

j(a — aj ) + k(a

j(ak — aj ) + k(aj

(k — j)(aj  — ak )

— ak )

— ak )

(by Lemma 2, because m is a valid ISBN-10)

(using algebraic properties of summation)

(because ai = a when i  j, k).

(because a = ak  and a = aj ).

Since 1 三 j < k 三 10, we have that 1 三 k — j 三 9; it follows that 11 does not divide k — j. Since  1 三 aj , ak  三 10 and aj   ak , we have that — 10 三 aj  — ak  三 10 and aj  — ak   0; it follows that 11 does not divide aj  — ak . By the Prime Divisibility Property, 11 does not

divide (k — j)(aj  — ak ). HenceΣi(1)1 ia is not divisible by 11.                                       II

3    ISBN-13

An ISBN-13 is a 13-digit code assigned to a publication  (books etc).  It replaced the ISBN-10 on January 1, 2007. The first 12 characters of an ISBN-13 code are digits that uniquely identify the publication (the title, author, edition etc). The thirteenth character is a check digit used to detect errors in transmission or recording.  More formally, let D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. An element (a1 ,..., a13 ) e D X ··· X D is a valid ISBN-13

if

a1 + 3a2 + a3 + 3a4 + ··· + a11 + 3a12 + a13 三 0.

10

We usually write an ISBN-13 as a string of digits, rather than a 13-tuple of digits.

Theorem 5. If one digit in a valid ISBN-13 is changed, then the resulting string of 13

digits is not a valid ISBN-13.

Proof. Let m = (a1 ,..., a13 ) and m（ = (a,..., a) be 13-tuples of digits.  Suppose that

m is a valid ISBN-13 and m（  is obtained from m by changing one entry.   Then there

exists j e {1, . . . , 13} such that a  aj  and a = ak  for all k  j.

To show that m（ is not a valid ISBN-13 we must show that

0 =1\0 a + 3a + a + 3a + ... 3a + a .

Since a d(=) b if and only if d divides b - a, it suffices to show that

a + 3a + a + 3a + ... 3a + a

is not divisible by 10. Now

a + 3a + a + 3a + ... 3a + a - 0

 a + 3a + a + 3a + ... 3a + a - (a1 + 3a2 + a3 + 3a4 + ... 3a12 + a13 )

(because m is a valid ISBN-13)

 (a - a1 ) + 3(a - a2 ) + ... 3(a - a12 ) + (a - a13 )

 3  - a(aj)j )   if(if)j(j) is(is) eve(od)n(d)

(because ak  = a when k  j).

Consider first the case that j is odd.  Since 0 三 aj   三 9 and 0 三 a 三 9, -9 三 a - aj  三 9. Since aj   a , a - aj   0.  Hence

a - aj  e {-9, . . . , -1} n {1, . . . 9},

and 10 does not divide a - aj . Thus we have that a + 3a + a + 3a + ... 3a + a is

not divisible by 10.

Now consider the case that j is even.  Since 0 三 aj  三 9 and 0 三 a 三 9, -9 三 a -aj  三

9.  Since aj   a , a 一 aj   0. Hence

a 一 aj  e {一9）. . . ）一1} n {1）. . . 9}.

It follows that

3(a 一 aj ) e {一27）一24 . . . ）一3} n {3）6）. . . 27}）

and 10 does not divide 3(a 一 aj ). Thus we have that a + 3a + a + 3a + ... 3a + a

is not divisible by 10.                                                                                                      

Unfortunately, the ISBN-13 error detecting code does not always detect the transpo- sition of distinct digits. We note that both 1020000000007 and 2010000000007 are valid ISBN-13’s; perhaps more alarmingly, we note that both 160000000001 and 610000000001

are valid ISBN-13’s.