Help Verifying/Completing Basic Cryptography Proofs
I'm not sure if there's a lot of different types of notation for this stuff, but just to be clear S(a) means the support of a, w(a) means the weight of a, h(a,b) is the hamming distance between a and b, is the minimum hamming distance between any two words in the group code C, and S(a;b) is a sphere where a is the center and b is the radius.
1. "Given and a nonnegative integer r, find a formula for |S( ;r)|. Use it to find |S(0110101;4)|"
For this one I said |S( ;r)| =
Substituting 7 for n and 4 for r, I got |S(0110101;4)| = = 99
2. "If C is a code contained in and a fixed word in , prove that where "
By adding to words , is unchanged since each coordinate position i in that gets changed is also changed in (with each coordinate position .
The hamming distance between any two elements of C are unchanged when is added to all of them, therefore the minimum hamming distance of C is equal to the minimum hamming distance of C + .
3. "For and any nonnegative real number r, define . Prove that if and p and q are nonnegative integers, then if and only if ."
Consider the following 3 possible Cases:
If , then
If , then
So I did the "if" part, but I'm not sure how to do the "only if" part or if that's necessary (I've seen proofs that said it's ok to omit it, but I don't know when that's true?)
4. "Let and be words of . Define to be (ie ). Let C be an (n,k) code (code of length n with n-k check digits) and define . This is the so-called dual of C.
(i) Prove is a subgroup of
(ii) Prove that if M is the generator matrix of C, then where is the transpose of M, i.e., the matrix obtained by interchanging rows and columns. Hence show that "
I know that I need to show that the elements of are closed, have an identity, an inverse, and are associative (all under addition), but I don't know how to do it though?
M is a matrix of the form . I need to show that , but I don't know how to show this or
Re: Help Verifying/Completing Basic Cryptography Proofs