Cryptography Reference
In-Depth Information
If an incorrect ISBN number has been transmitted, what is the best way
to correct it?
11.16. Prove that the Hamming distance defined on page 443 is indeed a
function as asserted. Then establish that the properties, displayed on
page 443, of the Hamming function hold.
11.17. Establish the two conditions 1 and 2, for the Hamming function's ability
to detect/correct codes, given on page 444.
11.18. Verify the statement made on page 444 to the effect that nearest neigh-
bour decoding may be used to either detect up to
d
−
1 errors or to correct
up to (
d
−
1)
/
2 errors.
11.19. Prove the facts, stated on page 445, that
A
q
(
n,
1) =
q
n
and
A
q
(
n,n
)=
q
.
(
Hint: To show the latter it su
7
ces to show that you can always find
at least one
(
n,M,d
)
-code. To do this, let
C
be a collection of vectors
(
a,a,a,...,a,a
0
,...,a
0
)
where there are
d
repetitions of
a
, and
n
−
d
repetitions of
a
0
, where
a
0
∈
M
arbitrary. Conclude that
there are
q
such vectors, with distance
d
(
c,c
)=
d
for
c
fixed and
a
∈
M
=
c
.
)
11.20. Prove that any (
n,M,d
)-code over
F
q
is equivalent to an (
n,M,d
)-code
which has a row of zeros in some matrix representation of it (see page
444).
11.21. Prove that the Singleton bound given on page 445 holds. Conclude that
the code rate for such a code is at most (
n
−
d
+1)
/n
. See Footnote 11.6
on page 442.
11.22. Let
w
(
c
) denote the number of 1s appearing in a binary code
c
, called its
weight
(see page 446). Show that if
c,c
∈
F
2
, then
d
(
c,c
)=
w
(
c
+
c
)
≤
w
(
c
)+
w
(
c
). Indeed, show that
d
(
c,c
)=
w
(
c
)+
w
(
c
)
c
), where
−
w
(
c
∩
c
c
∩
is the codeword consisting of 1s in precisely the places
j
where
c
and
c
both have a 1 in position
j
.
11.23. Show that if
d
is even, then there exists a binary (
n
−
1
,M,d
−
1)-code
if and only if a binary (
n,M,d
)-code exists.
(
Hint: Use Exercise 11.22. In particular, when you assume that
C
is
a binary
(
n
−
1
,M,d
−
1)
-code, proceed as follows. For each codeword
C
, define
c
=(
c
1
,c
2
,...,c
n
−
1
,c
n
)
, where
c
=(
c
1
,...,c
n
−
1
)
∈
n
−
1
c
n
=
c
j
(mod 2)
.
j
=1
The set
C
of new codewords can be shown to be an
(
n,M,d
)
-code. This
construction of
C
from
C
is often called
adding an overall parity check
to
C
.
)
Search WWH ::
Custom Search