Cryptography Reference
In-Depth Information
11.24. Prove that an MDS code, defined on page 445, possesses the largest
possible value of d for a given M and n .
11.25. Verify that the cardinality of the Hamming sphere displayed on page
443 is indeed valid.
( Hint: Calculate
|{
v
S ( u,r ): d ( u,v )= m
}|
for each m
N
. )
11.26. Prove that the Hamming bound displayed on page 445 holds.
( Hint: Place a Hamming sphere around each codeword so that it has radius
t . Then count the number of vectors in these spheres and multiply by the
number of codewords. )
11.27. Establish that the Gilbert-Varshamov bound given on page 446 holds.
Conclude that this is also a lower bound for A q ( n,d ).
( Hint: Use an iterative process where you begin with some fixed vector
and remove all vectors within a Hamming sphere radius of d
1 from
it. Then from the remaining vectors choose another and do the same
thing, continuing in this fashion until no vectors remain. Then employ
the cardinality of the Hamming sphere established in Exercise 11.25 to
conclude that ultimately the bound is achieved. )
( Alternative hint: There is an alternative proof for those who are comfort-
able with the notion of cosets, at this juncture, and have solved Exercise
11.22. In this case, assume that the code has fewer than the number of el-
ements in the bound. Then there is a coset where all the words have weight
at least d . However, the union of a linear code with one of its cosets can
be shown to be a linear code. Once confirmed this establishes the result. )
= 0
11.28. Prove that d ( C ) = min
{
w ( c ): c
C where c
}
for a linear code C .
(See Exercise 11.22 and the discussion on page 446.)
11.29. Prove that two matrices generate equivalent linear [ n,k ]-codes if one
matrix can be obtained from the other by operations R1-R3 and C1-C2
described on page 447.
( Hint: The rows of a generator matrix are linearly independent. Show
that the row operations preserve this independence and that the column
operations create a generator matrix for an equivalent code. )
11.30 Prove that if G is the generator matrix for a linear [ n,k ]-code, then op-
erations R1-R3, and C1-C2 transform G into standard form [ I k |
M k,n k ],
as described on page 447.
11.31. Prove that the matrix P defined on page 447 satisfies that cP t = 0 for
all c
C .
Prove that C defined on page 448 is indeed a linear [ n,n
11.32.
k ]-code
M k,n k |
with generating matrix P =[
I n k ], and that G is a parity check
matrix for C as claimed on the aforementioned page.
Search WWH ::




Custom Search