Instructions: You may type up or handwrite your work, but it must be neat, professional, and organized and it must be saved as a PDF file and uploaded to the appropriate Gradescope assignment. Use a scanner or scanning app to convert handwritten work on paper to PDF. I encourage you to type your work using the provided template.
All tasks below must have a complete solution that represents a good-faith attempt at being right to receive engagement credits. If your submission is complete and turned in on time, you will receive full engagement credits for the assignment. All other submissions will receive zero engagement credit. Read the guidelines at Grading Specifications carefully.
To abide by the class’ academic honesty policy, your work should represent your own understanding in your own words. If you work with other students, you must clearly indicate who you worked with in your submission. The same is true for using tools like generative AI although I strongly discourage you from using such tools since you need to build your own understanding here to do well on exams.
where \(\alpha_1,\alpha_2,\dots,\alpha_{n-1}\) are distinct elements of \(F\) and \(v_1,v_2,\dots,v_n\) are nonzero elements of \(F\text{.}\) The code \(C\) is called a doubly-extended GRS code, and the last column in \(H\) is said to correspond to the code locator \(\infty\text{,}\) i.e., the “infinity” element or “point at infinity”.
Assuming that \(k\lt n\text{,}\) show that the dual code \(C^{\perp}\) is an \([n,n-k]\) doubly-extended GRS code that can be defined through the same code locators as \(C\text{.}\)
Fix \(\mu, \nu,\) and \(\eta\) to be elements of \(F\) with \(\mu,\eta\neq 0\text{.}\) Show that \(C\) is identical to the \([n,k]\) GRS code \(C'\) over \(F\) defined by the code locators
(Note: Given \(\mu\text{,}\) there are certain choice of \(\nu\) for which \(C'\) will in fact be singly-extended; still, if \(n\lt|F|\text{,}\) one can select \(\nu\) so that each \(\alpha_j'\) is nonzero, even when \(C\) is singly-extended.)
Show that each row in a canonical patrity check matrix of \(C'\) can be written as a linear combination of some rows in a canonical parity check matrix of \(C\text{.}\)
Show that \(C\) is identical to an \([n,k]\) GRS code over \(F\) with code locators \(\alpha_1^{-1},\alpha_2^{-1},\dots,\alpha_n^{-1}\) (and with propertly selected column multipliers). Verify that this holds also when \(C\) is singly-extended or doubly-extended, i.e., when the code locators of \(C\) include the zero element or the “infinity” element, regarding one to be the multiplicative inverse of the other.
[Optional]. Let \(\mu,\nu,\sigma\text{,}\) and \(\tau\) be elements of \(F\) such that \(\mu\tau \neq \sigma\nu\text{.}\) Based on parts 1 and 2, show that \(C\) is identical to an \([n,k]\) GRS code over \(F\) with code locators
and with properly selected column multipliers. Verify that this holds also when \(C\) is singly-extended or doubly-extended (with \(\alpha_j=\infty\) being mapped to \(\alpha_j'=\mu/\sigma\) and \(\alpha_j=-\tau/\sigma\) to \(\alpha_j'=\infty\)).
Give a construction of a concatenated code \(C_{\mathrm{cont}}\) which is a \([765,248,\geq 63]_2\) code. This means identifying explicitly the inner code \(C_{\mathrm{in}}\text{,}\) the outer code \(C_{\mathrm{out}}\text{,}\) and the mapping from symbols of \(C_{\mathrm{out}}\) to codewords of \(C_{\mathrm{in}}\text{.}\) Justify that your construction indeed achieves the desired parameters. How many errors can your code correct?
Find an appropriate RS code to use as the outer code and an appropriate binary code to use as the inner code, noticing that \(765=51\cdot 15, 248=31\cdot 8\) and \(63=21\cdot 3\text{.}\)
Let \(C_{\RS}\) be a \([21,17]\) normalized RS code over an extension field \(E\) of \(F=\GF(2)\) and let \(C_{\mathrm{BCH}}\) be the BCH code \(C_{\RS}\cap F^{21}\) over \(F\text{.}\)
5.Generator Matrix for a Concatenated Code [Optional].
Let \(C_{\mathrm{out}}\) be an \([N,K]\) code over an extension field \(E=\GF(q^k)\) of \(F=\GF(q)\text{,}\) and let \(C_{\mathrm{in}}\) be an \([n,k]\) code over \(F\text{.}\) Let \(\{\beta_1,\beta_2,\dots,\beta_k\}\) be a basis for \(E\) over \(F\text{.}\) Let \(C_{\mathrm{cont}}\) be the concatenated code with these outer and inner codes and with the mapping from symbols of \(C_{\mathrm{out}}\) to codewords of \(C_{\mathrm{in}}\) defined by writing each symbol in \(E\) as a linear combination of the basis elements with coefficients in \(F\) and replacing it with the corresponding linear combination of codewords of \(C_{\mathrm{in}}\text{.}\)
Let \(G_{\mathrm{out}}\) be a generator matrix for \(C_{\mathrm{out}}\text{.}\) Argue that the \(kK\times N\) matrix \(G_{\mathrm{out}}'\) obtained by replacing each row \(\br_i\) of \(G_{\mathrm{out}}\) with the \(k\times N\) matrix
Each symbol \(g_{ij}\) of \(G_{\mathrm{out}}'\) is an element of \(E\) and therefore can be written as a linear combination of the basis elements \(\beta_1,\beta_2,\dots,\beta_k\) with coefficient vector \(\vec{g_{ij}}\) in \(F\text{.}\) By replacing each symbol in \(G_{\mathrm{out}}'\) with the vector \(\vec{g_{ij}}G_{\mathrm{in}}\text{,}\) we can obtain a \(kK\times nN\) matrix \(\tilde{G}\) with entries in \(F\text{.}\) Show that \(\tilde{G}\) is a generator matrix for the concatenated code \(C_{\mathrm{cont}}\text{.}\)
