1
$\begingroup$

I'm looking at creating sparse generator matrices for cyclic codes of a given length and dimension. A generator matrix of an [n,k] cyclic code can be expressed as

$G = \begin{bmatrix}g_0 & g_1 & \cdots& g_{n-k-1}& 1 & 0 & \cdots & 0\\ 0 &g_0 & g_1 & \cdots& g_{n-k-1}& 1 & 0 & 0\\ \vdots & & \ddots & & & \ddots & \ddots &&\\0 & \cdots & 0& g_0 & g_1 & \cdots& g_{n-k-1}& 1\end{bmatrix}$

Where the generator polynomial of the code is $g(x) = g_0 + g_1 x + \cdots + g_{n-k-1}x^{n-k-1} + x^{n-k}$

To get some guarantees on what sparsities are possible for a given n and k, I'm looking for bounds (lower and upper) on the number of non-zero generator polynomial coefficients in the lowest weight generator polynomial for n and k.

Or relating to my original problem, are there bounds on the sparsity of $G$'s of the above form?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Considering only primitive polynomials over $\mathbb{F}_2$ as your generating polynomial candidate, there is a conjecture that there are infinitely many primitive trinomials.

So, it may well be the case that there is an infinite sequence $d_i\geq 1,$ and generating polynomials $g_i(x)=(1+x^{a_i}+x^{d_i})$ for which there is (at least) a corresponding set of lengths $n_{i}$, where $g_i(x)|(x^{n_i}+1)$, (due to existence of splitting fields) and the sparsity of each row of $G$ is 3.

By the way, it is conjectured but as far as I know unknown [as stated by Golomb as recently as in 2007] whether infinitely many binary primitive $m-$nomimals (where $m$ must be odd) exist or not, for any finite odd $m$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Do you have some reference(s) for the conjecture, especially the 2007 article(?) by Golomb? $\endgroup$
    – Yuichiro Fujiwara
    Commented Mar 12, 2015 at 23:50
  • 1
    $\begingroup$ Hi, it's in the LNCS volume 4893, Sequences, Subsequences and Consequences. The first article, authored by Golomb, is the reference. $\endgroup$
    – kodlu
    Commented Mar 12, 2015 at 23:58
  • $\begingroup$ By the way, clearly $(x+1)$ divides any $x^n+1$ but I considered that a degenerate case and did not mention above since it generates the two word repetition code. One thing that's unclear to me, whether taking appropriate products of irreducible polynomials can result in constant low weight product polynomials infinitely often, due to cancellation. That's likely to be even harder to prove, in my opinion. $\endgroup$
    – kodlu
    Commented Mar 13, 2015 at 0:02
  • $\begingroup$ I'll definitely look into it! I have worries about these polynomials being divisors of $x^n - 1$. I don't think adding the condition that my generator be primitive gives any bonus and it restricts my search space. Trinomials would make good sparse generators though! Thanks for the help! $\endgroup$
    – mitch
    Commented Mar 16, 2015 at 15:18
  • $\begingroup$ @mitch:post a comment here if you find anything interesting. $\endgroup$
    – kodlu
    Commented Mar 16, 2015 at 21:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .