Reed Solomon Code

Question

Working in GF(32). Polynomial is $x^5+x^2+1$. $\alpha$ is primitive element. $t = 3$. RS code. $n = 31$, $k = 25$. I have obtained generator polynomial $x^6+\alpha^{10}x^5+\alpha^{30}x^4+\dots$ How do I obtain generator matrix? I believe I write down coefficients in increasing order of $x$ over $31$ columns and $25$ rows and keep shifting since it is cyclic. Is this correct?

Answer 1

Yes you're absolutely correct. If, say, $G(x) = g_0+g_1x^1+\dots+g_{n-k}x^{n-k}$, then the Generator matrix (a possible one; certainly not systematic. For a systematic generator matrix, please look at the other answer from Prof. Sarwate which is much better) is given as: $$G=\left[ \begin{array}{} g_0 & g_1 & g_2 & \dots & g_{n-k} & 0 & \dots & 0 & 0 & 0\\ 0 & g_0 & g_1 & \dots & g_{n-k-1} & g_{n-k} & 0 &\dots & 0 & 0 \\ 0 & 0 & g_0& \dots& g_{n-k-2}& g_{n-k-1}& g_{n-k}& 0& \dots& 0\\. & & & & & & & & & . \\ 0&0&0&\dots & g_0 & g_1 & g_2 &\dots & \dots & g_{n-k}\end{array}\right]$$

Answer 2

The answer given by Sudarsan is one possible generator matrix. If $${\bf d} = (d_0, d_1, \ldots , d_{k-1}) \longleftrightarrow d(x) = d_0 + d_1x + \cdots + d_{k-1}x^{k-1}$$ is the data polynomial, then the codeword polynomial corresponding to the codeword ${\bf c} = {\bf d}G$ (where $G$ is the generator matrix in Sudarsan's answer) is $d(x)g(x)$. Thus, using this generator matrix gives us a nonsystematic Reed-Solomon code meaning that $\bf d$ is not a subvector of ${\bf c}$.

The generator matrix $\hat{G}$ of a systematic cyclic code, in which the codewords are of the form $${\bf c} = {\bf d}\hat{G} = ({\bf r}, {\bf d}) = (r_0, r_1, \ldots, r_{n-k-1}, d_0, d_1, \ldots, d_{k-1}),$$ is obtained as follows. We use the fact that $g_{n-k} = 1$.

• The first row is the same as in Sudarsan's answer.

• The second row is obtained by first shifting the first row to the right by one place (as in Sudarsan's answer) but then subtracting $g_{n-k-1}$ times the first row from the shifted second row. What this does is modify the second row to put a $0$ below the $g_{n-k}$ in the first row. The first two rows thus look like $$\left[ \begin{array}{} g_0 & g_1 & \dots & g_{n-k-1} & 1 &0 & \dots & 0 & 0\\ -g_0g_{n-k-1} & g_0-g_1g_{n-k-1} & \dots & g_{n-k-2}-g_{n-k-1}^2& 0 & 1 &\dots & 0 & 0 \end{array}\right]\\ {\Large \Downarrow}\\ \left[ \begin{array}{} p_{0,0} & p_{0,1} & \dots & p_{0,n-k-1} & 1 &0 & \dots & 0 & 0\\ p_{1,0} & p_{1,1} & \dots & p_{1, n-k-1} & 0 & 1 &\dots & 0 & 0 \end{array}\right]$$

• The third row is obtained first shifting the newly constructed second row to the right by one place but then subtracting $p_{1,n-k-1}$ times the first row from so as to put a $0$ below the $1$ in the first row. Note that this forms a $3\times 3$ identity matrix on the right.

• Lather, rinse, repeat, till you get $\hat{G} = [P \mid I]$ where $I$ is the $k\times k$ identity matrix and $P$ is the $k\times (n-k)$ matrix formed on the left as the shifting and subtracting is done. The first row of $\hat{G}$ is, of course, the same as the first row of $G$ in Sudarsan's answer. The rows of $\hat{G}$ are, of course, codewords, and the corresponding codeword polynomials are $$g(x),\\x^{n-k+1} - \left(x^{n-k+1} \mod g(x)\right), \\ x^{n-k+2} - \left(x^{n-k+2} \mod g(x)\right),\\ \vdots \\x^{n-1} - \left(x^{n-1} \mod g(x)\right),$$

The codeword polynomial corresponding to ${\bf d}\hat{G}$ is $x^{n-k}d(x) - \left(x^{n-k}d(x) \mod g(x)\right)$ where the second term on the right is the residue of $x^{n-k}d(x)$, a polynomial of degree $n-1$, modulo the generator polynomial $g(x)$. This residue is of degree $n-k-1$ or less, while $x^{n-k}d(x)$ has no nonzero coefficients of degree smaller than $n-k$, reflecting the fact that the codeword polynomial $x^{n-k}d(x) - \left(x^{n-k}d(x) \mod g(x)\right)$ has all the data symbols "in the clear" in the high-order coefficients followed by the parity symbols; that is, we have a systematic code.