Dimension of cyclic codes

Question

According to most texts, this is a trivial matter. If $g(x)$ is a generator polynomial of degree $n-k$ of a length $n$ cyclic code $C$, then $(a_0+ \ldots +a_{k-1}X^{k-1})g(x) \mod X^n - 1$ will give all possible values of $(b_0+ \ldots +b_{n-1}X^{n-1})g(x) \mod X^n - 1$. I really don't see how this is trivial at all. Any thoughts?

Answer 1

Let $c \in C$. Then $c=bg$ where $b \in (GF(q))^n$. This means $c(X)=b(X)g(X) \mod X^n-1$, where, if $l=(l_0, \ldots,l_{n-1})$, then $l(X)=l_0+ \ldots + l_{n-1}X^{n-1}$. So, we have, $$c(X)=b(X)g(X) + q(X)(X^n-1)$$ We know that $g(X)$ divides $X^n -1$, say $g(X)h(X)=X^n-1$, hence $$c(X)=b(X)g(X) + q(X)h(X)g(X)$$ Therefore $c(X)=(b(X) +q(X)h(X))g(X)$. This means that $\deg(b(X) +q(X)h(X))$ is at most $k-1$, hence the $b(X) +q(X)h(X)$ is the sought after $a_0 + \ldots + a_{k-1}X^{k-1}$