0

Say I have a Reed-Solomon generator matrix (working in $\mathbb{Z}_{11}$)

$G=\left(\begin{array}{cccc} 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4\\ 1 & 4 & 9 & 5\\\end{array}\right)$

How do I find the parity check matrix $H$ of the form

$H=\left(\begin{array}{cccc} 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4\\ 1 & 4 & 9 & 5\\ 1 & 8 & 5 & 9 \end{array}\right)\cdot\left(\begin{array}{cccc} v_1 & 0 & 0 & 0\\ 0 & v_2 & 0 & 0\\ 0 & 0 & v_3 & 0\\ 0 & 0 & 0 & v_4 \end{array}\right)$ for non-zero values $v_1\dots v_n$ such that $GH^T=0$.

Note: I am trying to work out a simple example of the material presented in this paper towards the bottom of page 40 so that I can better understand it.

mikeazo
  • 412

1 Answers1

3

The parameters don't add up. Your $G$ generates a code of length 4 and rank 3, so its parity check matrix will have a single row ($4-3=1$).

The paper that you link to prescribes the use of a code of length $n=3t+1$ and rank $k=t+1$, so this won't fit into that scheme. If you intended $t=2$, then the code must have length $n=3t+1=7$.

Anyway, your $G$ is row equivalent to the reduced row echelon form $$ \left(\begin{array}{cccc} 1&0&0&1\\ 0&1&0&8\\ 0&0&1&3 \end{array}\right), $$ which gives us the check matrix $$ H=\left(\begin{array}{cccc} -1&-8&-3&1 \end{array}\right)=\left(\begin{array}{cccc} -1&3&-3&1 \end{array}\right). $$

Here I used a general recipe that a code generated by $G=(I|A)$ has check matrix $H=(-A^T|I)$. For Reed-Solomon codes there are useful duality results that allow us to write a check matrix in many a form.

Jyrki Lahtonen
  • 133,153