Error Correction Coding: Mathematical Methods and Algorithms

Chapter01 - Home
Exercises: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19 - 20 - 21 - 22 - 23 - 24 - 25 - 26 - 27 - 28 - 29 - 30 - 31 - 32 - 33 - 34 - 35

Exercise. This is the solution to exercise 1.1 in the book.

Solution. a. We do proof by induction. For n = 1 we have:

W = w1 w1 = t1 t1 = s1

hence

W = s1

For n = 2 we also have:

W = w2 w2 = t1 + t2 t1 = s1 t1 = s1 + s2

hence

W = 2s1 + s2

Now assume n holds and prove n + 1

Wn+1 = wn+1 = t1 + t2 + + tn+1

but

Wn = t1 + t2 + + tn

or

Wn+1 = Wn + tn+1

. But

Wn = ns1 + (n 1)s2 + + 2sn1 + sn

and

tn+1 = s1 + s2 + + sn + sn+1

hence

Wn+1 = ns1 + (n 1)s2 + + 2sn1 + sn + s1 + s2 + + sn + sn+1

or

Wn+1 = (n + 1)s1 + ns2 + + 3sn1 + 2sn + sn+1

b. The two digits indicated contribute:

W = + (n k + 1)sk + (n k)sk+1 +

W = + (n k + 1)s k+1 + (n k)sk+1 +

Re-arranging we get:

W = W + s k+1 sk

If sk+1 sk is positive (cannot be zero as digits are different) then:

W = (s k+1 sk)(modp)

If sk+1 sk is negative then we can substract p from W to make p + sk+1 sk a positive value. The same holds:

W0(modp)

c. We have:

W = + (n k + 1)sk +

W = + (n k + 1)s k +

then

W = W + (n k + 1)(s k s k)

Since n < p then

n k + 1 < p,1 k n

Since sk,sk are digits they’re in range 09. Since the digits are different, then potentially sk sk = 0(modp) if p 9 (i.e., p = 2,3,5,7).

Assuming p 10 then

(n k + 1)(sk s k)0(modp)

Hence if W = 0(modp) then it must be that:

W0(modp)

If n > p then there exists a value of k such that n k + 1 = 0(modp) hence

(n k + 1)(sk s k) = 0(modp)

and

W = 0(modp)

Thus the length of the sequence must be restricted to n < p.

d. This ISBN is valid.

digitcumul. sumcumul. sum



0 0 0
1 1 1
3 4 5
1 5 9
3 8 17
9 17 34
0 17 51
7 24 76
2 26 102
4 30 132

e. As determined in b. this ISBN cannot be valid because digits 3 and 9 (in ISBN from d. which is valid) are interchanged.