Coding Theory – Winter 2022 361-2-6251 ECE, BGU
Coding Theory – Winter 2022 361-2-6251 ECE, BGU
Due date: 20/12/2021 at 23:59 You should answer all questions. You can use the claims of previous questions to prove later ones (even if you do not know the answer to the previous questions). All claims should be proved. All calculations should be explained. The homework is to be solved alone without consulting with other people. Other sources are allowed, but should be clearly cited.
Homework #2
1. Let F = Fq be a finite field.
(a) (10%) Let α1 , α2 , . . . , αq be the elements of F = Fq, assuming now that q > 3, and let r be an integer, 1 6 r < q − 1. Show that
q
∑ i=1
αri = 0.
Hint: Represent the elements as powers of a primitive element.
(b) (10%) Let Φ = Fqm be an extension of F = Fq. Let β ∈ Φ be any element. Prove that β ∈ F if and only if βq = β.
2. Let C be an [n, k, d] code over Fq. Denote by supp(C) the set of coordinates of C that are not always 0, namely,
supp(C) = {1 6 i 6 n : there exists c = (c1 , . . . , cn) ∈ C such that ci 6= 0} .
We also define for all 1 6 ` 6 k the following quantity:
d`(C) = min C′ linear subcode of C
dim(C′)=`
∣∣supp(C′)∣∣ . (a) (10%) Prove d1(C) = d.
(b) (15%) Prove that if C′ is an [n, k′] subcode of C with k′ > 1, there exists a code C′′ which is an [n, k′ − 1] subcode of C′ such that |supp(C′′)| < |supp(C′)|.
(c) (15%) Prove for all 1 6 ` 6 k − 1 that d`(C) < d`+1(C).
3. Let C be an [n, k, d] MDS code over Fq.
(a) (10%) Let G be any generating matrix for C. Prove that any subset of k columns of G forms a k × k invertible matrix.
(b) (10%) Prove C⊥ is also MDS. Hint: Use question 3a.
4. (20%) Let C be an [n, k] code over Fq, and let H be an (n − k) × n parity-check matrix for the code, whose columns are denoted h
ᵀ 1 , . . . , h
ᵀ n. Let r(C) be defined as in Question 3 of Homework 1. Assume ` is the smallest
integer such that for any column vector vᵀ of length n − k there exist ` columns of H, hᵀi1 , . . . , h ᵀ i` , and ` scalars
α1 , . . . , α` ∈ Fq such that vᵀ = ∑`j=1 αj h ᵀ i j . Prove r(C) = `.
1
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
