# 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:

$\begin{array}{rcll}W& =& {w}_{1}& \text{}\\ {w}_{1}& =& {t}_{1}& \text{}\\ {t}_{1}& =& {s}_{1}& \text{}\end{array}$

hence

$W={s}_{1}$

For $n=2$ we also have:

$\begin{array}{rcll}W& =& {w}_{2}& \text{}\\ {w}_{2}& =& {t}_{1}+{t}_{2}& \text{}\\ {t}_{1}& =& {s}_{1}& \text{}\\ {t}_{1}& =& {s}_{1}+{s}_{2}& \text{}\\ & & & \text{}\end{array}$

hence

$W=2{s}_{1}+{s}_{2}$

Now assume $n$ holds and prove $n+1$

${W}_{n+1}={w}_{n+1}={t}_{1}+{t}_{2}+\dots +{t}_{n+1}$

but

${W}_{n}={t}_{1}+{t}_{2}+\dots +{t}_{n}$

or

${W}_{n+1}={W}_{n}+{t}_{n+1}$

. But

${W}_{n}=n{s}_{1}+\left(n-1\right){s}_{2}+\dots +2{s}_{n-1}+{s}_{n}$

and

${t}_{n+1}={s}_{1}+{s}_{2}+\dots +{s}_{n}+{s}_{n+1}$

hence

${W}_{n+1}=n{s}_{1}+\left(n-1\right){s}_{2}+\dots +2{s}_{n-1}+{s}_{n}+{s}_{1}+{s}_{2}+\dots +{s}_{n}+{s}_{n+1}$

or

${W}_{n+1}=\left(n+1\right){s}_{1}+n{s}_{2}+\dots +3{s}_{n-1}+2{s}_{n}+{s}_{n+1}$

b. The two digits indicated contribute:

$W=\dots +\left(n-k+1\right){s}_{k}+\left(n-k\right){s}_{k+1}+\dots$

${W}^{\prime }=\dots +\left(n-k+1\right){s}_{k+1}+\left(n-k\right){s}_{k+1}+\dots$

Re-arranging we get:

${W}^{\prime }=W+{s}_{k+1}-{s}_{k}$

If ${s}_{k+1}-{s}_{k}$ is positive (cannot be zero as digits are different) then:

${W}^{\prime }=\left({s}_{k+1}-{s}_{k}\right)\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$

If ${s}_{k+1}-{s}_{k}$ is negative then we can substract $p$ from $W$ to make $p+{s}_{k+1}-{s}_{k}$ a positive value. The same holds:

${W}^{\prime }\ne 0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$

c. We have:

$W=\dots +\left(n-k+1\right){s}_{k}+\dots$

${W}^{\prime }=\dots +\left(n-k+1\right){s}_{k}^{\prime }+\dots$

then

${W}^{\prime }=W+\left(n-k+1\right)\left({s}_{k}^{\prime }-{s}_{k}\right)$

Since $n then

$n-k+1

Since ${s}_{k}^{\prime },{s}_{k}$ are digits they’re in range $0\dots 9$. Since the digits are different, then potentially ${s}_{k}^{\prime }-{s}_{k}=0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$ if $p\le 9$ (i.e., $p=2,3,5,7$).

Assuming $p\ge 10$ then

$\left(n-k+1\right)\left({s}_{k}^{\prime }-{s}_{k}\right)\ne 0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$

Hence if $W=0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$ then it must be that:

${W}^{\prime }\ne 0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$

If $n>p$ then there exists a value of $k$ such that $n-k+1=0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$ hence

$\left(n-k+1\right)\left({s}_{k}^{\prime }-{s}_{k}\right)=0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$

and

${W}^{\prime }=0\phantom{\rule{1em}{0ex}}\left(mod\phantom{\rule{1em}{0ex}}p\right)$

Thus the length of the sequence must be restricted to $n.

d. This ISBN is valid.

 digit cumul. sum cumul. 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.