Show that there is precisely one cyclic code C of length 4 and dimension 2. Write down all the codewords in C.

Question

I have shown there is one cyclic code, put not sure how to calculate the codewords in C.

I think that the generator matrix is \begin{bmatrix}1&0&1&0\\0&1&0&1\end{bmatrix}

but am not sure, is that correct and if it is where do I go next?

Answer 1

The rigorous way is to exploit the algebraic structure of cyclic codes: a cyclic code of size $(n=4,k=2)$ must have a generator poylnomial $g(x)$ of degree $n-k=2$, which must have a non null independent coefficient, and must be a factor of $1+x^{n}=1+x^4$

Now $1+x^{n}$ factors (remember we are in $GF(2)$) as $$1+x^4=(1+x^2)^2=(1+x)^4$$

Hence there is a single possible generator polynomial $$g(x)=1+x^2$$

And the full code is

$$ \begin{array}{c c |c c} u & u(x) & v(x)=u(x)g(x) & v\\ \hline 00 & 0 & 0 & 0000\\ 10 & 1 & 1+x^2 & 1010\\ 01 & x & x+x^3 & 0101\\ 11 & 1+x & 1+x+x^2+x^3 & 1111\\ \end{array} $$ Hence your matrix $G$ is right.

Answer 2

Without using much algebra, note that the standard assumption that a cyclic code is also a linear code ensures that one of the codewords must be $0000$. Cyclic shifts of this codeword are also in the code. Now, only three remaining codewords need to be considered. Any length-$4$ vector such as $0001$ which has four distinct cyclic shifts $0001, 0010, 0100, 1000$ cannot be a codeword in our cyclic code. A little thought (or just brute-force writing out all $15$ possible codewords and discarding all that have $4$ distinct cyclic shifts) then gets us to having $1111$ as another codeword, and $0101$ and $1010$ as the other two: they are the only codewords with one distinct cyclic shift, and a cyclic shift of one is the other (or itself).