Cryptography Reference
In-Depth Information
11.33. Prove that if G is a generator matrix for an [ n,.k ]-code, then it can
be reduced to standard form [ I k |
M k,n k ]employing only row operations
R1-R3 if and only if the first k columns of G are linearly independent.
11.34. A linear code C is self-dual if C = C (see page 448). Prove that if C
is a self-dual linear [ n,k,d ]-code, then n is even.
11.35. With reference to Exercise 11.34, prove that ( C ) = C for any linear
[ n,k ]-code C .
Exercises 11.36-11.40 pertain to the discussion on page 450 concerning
cosets of linear codes.
11.36. Establish that two vectors are in the same coset if and only if they have
the same syndrome. Conclude that there is a one-to-one correspondence
between cosets and syndromes.
11.37. Prove that if e + C is a coset of C and f
e + C , then e + C = f + C .
11.38. Prove that every coset C + e has exactly q k vectors.
q is in some coset of C .
11.40. Show that two cosets are either identical or are disjoint.
( Hint: Use Exercise 11.37. )
11.39. Verify that every vector of
F
11.41. Prove that if C is a linear [ n,k ]-code over
F q with parity check matrix
P , then the minimum distance of C is d if and only if d
1 columns of P
are linearly independent, but d columns are linearly dependent.
11.42. If q is a prime power and N =( q n
1) / ( q
1) for a given n
N
, prove
that there exists a [ N,N
n, 3]-code.
( Hint: Consider the sets
S v =
{
λv : λ
F q
=0
}
for each nonzero
n
v
1 for each such v and there are N such sets.
Select one vector from each
F
q . Then
| S v |
= q
S v , no two of which are linearly dependent.
Now use Exercise 11.41 to conclude. )
11.43. The codes constructed in Exercise 11.42 are called q -ary Hamming
codes . Prove that these codes are perfect single-error-correcting codes.
(See page 445.)
11.44. Show that the repeating [ n, 1]linear code with generator matrix G =
[1 , 1 ,..., 1]with n odd is a perfect code where the Hamming spheres of
radius ( n
n
q without overlapping.
11.45. Prove the allegation stated in Footnote 11.8 on page 447.
1) / 2 completely fill
F
11.46. In the Example on page 454 of the [7 , 4 , 3]Hamming code, construct
the 8
16 Slepian array. Then extract the syndrome lookup table from it,
and use syndrome decoding to find the original message from the following
received vectors.
×
Search WWH ::




Custom Search