I would like to show that for an cyclic code $C\subset F_q[x]/(x^n -1)$ with check polynomial $p(x)=p_0+p_1x+...+p_k x^k$ there exists this check matrix:

$$ \begin{pmatrix} p_k & \cdots & p_1 & p_0 & 0 & \cdots & 0 \\ 0 & p_k & \cdots & p_1 & p_0 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots &\ddots & \ddots & 0 \\ 0 & \cdots & 0 & p_k & \cdots & p_1 & p_0 \\ \end{pmatrix} $$

Here's my approach: Lets call that Matrix $P$. $P$ is a check matrix of $C$, when $v\in C \Leftrightarrow P\cdot v^T=0$.

Let $v\in F_q^n, v=(v_0,...,v_{n-1})\\ H\cdot v^T=0 \Leftrightarrow 0=\sum_{i=0}^{k}p_{k-i}\cdot v_{i+h} \forall h \in \{0,...,n-k-1\}\\ \Leftrightarrow 0=\sum_{j+l=k+h}p_j\cdot v_l \forall h\\ \Leftrightarrow \text{all coefficients of }x^k,...,x^{n-1} \in p(x)\cdot v(x) \text{ are zero mod }x^n-1 $

Here im stuck. I want to follow, that $p(x)\cdot v(x) \equiv 0 \text{ mod } x^n-1$. But i don't know how to show that.

Because then i can follow that $P$ is check matrix if and only if $v \in C \Leftrightarrow P\cdot v^T =0 \Leftrightarrow p(x)\cdot v(x)\equiv 0$.

  • 1
    $\begingroup$ The idea is that the check polynomial $p(x)$ is actually a factor of $x^n-1$. This implies that those cyclic shifts of the rows of your check matrix that "wrap around" are actually linear combinations of the listed ones. $\endgroup$ – Jyrki Lahtonen Jul 3 at 21:08
  • $\begingroup$ @JyrkiLahtonen what do you mean with "..of the listed ones"? $\endgroup$ – George Devore Jul 3 at 21:33
  • $\begingroup$ I mean that for example the vector $(p_0,0,\ldots,0,p_k,p_{k-1},\ldots,p_1)$ is a linear combination of the rows of the matrix you gave. $\endgroup$ – Jyrki Lahtonen Jul 5 at 4:55

If the check polynomial for you is the polynomial p(x) whose product with every c(x) in the code is zero, then the statement is wrong. The dual is generated by the reciprocal of h(x). For instance the scalar product of p and c as vectors is the constant term of $p^*(x)c(x).$

  • $\begingroup$ What you wrote is, of course, correct. Hence the upvote. I do think that the OP is using the reciprocal because they reverted the order of the coefficients of $p(x)$ when forming the check matrix. $\endgroup$ – Jyrki Lahtonen Jul 11 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.