Dual of generalized Reed-Solomon code

386 Views Asked by At

I need to show that $GRS_{n,k}(\alpha,\mathbb{1})^{\perp}=GRS_{n,n-k}(\alpha,\alpha)$, where $\alpha=(1,a,\ldots,a^{n-1})$, $a$ is a primitive $n$-th root of unity, $\mathbb{1}=(1,1,\ldots,1)$.

So, to show this, I think It suffices to show that $c\cdot c'=0$ for all $c\in GRS_{n,k}(\alpha,\mathbb{1})$ and for all $c'\in GRS_{n,n-k}(\alpha,\alpha)$. I am kinda stuck how to approach this, should I go with the generating matrix or something else?

1

There are 1 best solutions below

1
On BEST ANSWER

Clearly

$$c=(1\cdot f(1),1 \cdot f(a),1\cdot f(a^2),\cdots,1\cdot f(a^{n-1}))=(f(1),f(a),f(a^2),\cdots, f(a^{n-1})),$$ and $$c'=(1\cdot g(1),a \cdot g(a),a^2\cdot g(a^2),\cdots,a^{n-1}\cdot g(a^{n-1}))=(g(1),ag(a),a^2g(a^2),\cdots, a^{n-1}g(a^{n-1})).$$ Where $f$ has degree at most $k-1$ and $g$ has degree at most $n-k-1.$

So the product has degree at most $n-2.$ One then needs to show that the product is actually the zero polynomial, using Lagrange interpolation. You can refer to John Hall's very useful Coding Theory notes (Chapter 5) at Michigan State, if you need more details.