Abstract
This paper considers generalized quasi-cyclic (GQC) codes with no restriction on their block lengths. By relaxing the condition on its block lengths, we find some new optimal codes of small length. Also, we generalize the decomposition of codes and dimension formula given by Güneri et al, Séguin, and Siap et al. We use two different approaches to describe GQC codes: first, by torsion module structure, and second, by injection into classes of QC codes. Using the first approach, we can determine the dimension and give a formula for the minimum distance of the corresponding GQC code. In the second approach, we use structural properties of QC codes with one specific length. This approach gives us a way to construct GQC codes, dual code for a given GQC code, and a criterion for a GQC code to be a Euclidean self-dual code. Moreover, we also consider GQC codes over a family of finite rings, called the ring \(B_k,\) and its relation to GQC codes over finite fields using a collection of Gray maps.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Quasi-cyclic (QC) codes are an important type of code. One of the main reasons is QC codes can be used as public and private keys in the McEliece cryptosystem, see [1, 2, 12]. Compared to the cyclic codes, the QC codes have a more complicated algebraic structure. Although more complex than the cyclic one, QC codes satisfy Gilbert-Varshamov’s lower bound on minimum distance, as Kasami showed [9]. One practical way to study the algebraic structure of QC codes is by decomposing QC code into shorter length codes over larger alphabets using the Chinese remainder theorem (CRT) as has been done by Ling and Solé [10, 11].
Any QC code is equivalent to a linear code with a block circulant generator matrix. This corresponding generator matrix has circulant blocks with the same size, say m, which is then called the co-index of the related QC code. From this point of view, one way to generalize QC codes is by allowing generator matrices to have circulant blocks of different sizes. Codes with this property are called generalized quasi-cyclic (GQC)codes with co-indices \((m_1,m_2,\dots ,m_k),\) where \(m_1,\dots ,m_k\) are the sizes of circulant blocks in corresponding generator matrices. The study of GQC codes over \({\mathbb {F}}_q\) has been done by Séguin [14] under different term. In [14], the author called this type of codes \(\sigma \)-codes, where \(\sigma \) is a permutation with cycle structures equal co-indices of GQC codes. The author showed that GQC code could be expressed as the sum of primary GQC codes, equivalent to the decomposition of a cyclic code as the sum of minimal cyclic codes. Moreover, one can obtain GQC codes via the trace function, and this formulation can be applied to describe the dual of a QC code. However, one got these results assuming that the order of \(\sigma \) (consequently, the block circulant sizes) coprime to q.
Siap and Kulhan [15] first introduced the term generalized quasi-cyclic (GQC) codes. In [15], under the same assumption for co-indices as in [14], the authors determined the generator for 1-generator GQC codes and proved a BCH type bound for GQC codes. In 2009, Esmaeili and Yari [4] improved the results obtained in [15]. In the latter study, the authors determined the dimension and parity check polynomial of a given 1-generator GQC code over \({\mathbb {F}}_q\) with no restriction on the co-indices of corresponding GQC code. Moreover, with the same assumption on the co-indices as in [14] and [15], the authors characterized \(\rho \)-generator GQC codes using CRT. By using this characterization, they obtained a lower bound on the minimum distance of 1-generator GQC codes. Also, the authors gave some GQC code construction algorithms and lists of optimal and sub-optimal GQC codes obtained using the algorithm.
Most recently, Güneri et al. [8] have studied GQC codes over \({\mathbb {F}}_q\) under the assumption that its co-indices are coprime to q. In particular, the authors extend the CRT approach and trace formulation for QC codes in [10, 11] to describe the structural properties of GQC codes. By using this point of view, the authors obtained generalized concatenated description for GQC codes. The latter description gave Jensen’s type bound for GQC codes, which generalized the bound given in [4]. Moreover, the authors presented a criterion for a GQC code to be Euclidean self-dual and studied the asymptotic performance of GQC codes.
This paper describes the algebraic structure of GQC codes over \({\mathbb {F}}_q\) and a family of finite rings with no restriction on its co-indices. By relaxing the restriction on co-indices, we can construct GQC codes of any length and any co-indices. For instance, most of optimal codes in Tables 1,2, and 3 are GQC codes where their co-indices are not coprime to q. We use two approaches on describing GQC codes, first, by torsion module structure, and second, by injection into classes of QC codes. In the first approach, we give a more detailed decomposition for GQC based on torsion module decomposition. By using this decomposition, we can express a given GQC code as a direct sum of primary GQC codes.
Consequently, we can determine the dimension and give a formula for minimum distance of the corresponding GQC code. The second approach is done by injecting a GQC code to the set of QC codes with longer length. This approach is different compared to [4, 8, 14, 15]. Using structural properties of QC codes in [10, 11], we obtain a way to construct GQC codes, dual code for a given GQC code, and a criterion for a GQC code to be a Euclidean self-dual code. Moreover, we also consider GQC codes over a family of finite rings and its relation to GQC codes over finite fields.
This paper is organized as follows. Section 2 collects background on QC codes, GQC codes, and torsion modules. Section 3 describes GQC codes as submodules of a torsion module and related properties. In Sect. 4, we inject GQC codes into a set of QC codes, decompose GQC codes using CRT and describe the dual code of a GQC code. Section 5 gives algorithms to construct GQC codes and some optimal GQC codes of small lengths. In Sect. 6, we describe GQC codes over a family of finite rings and its relation to the construction of GQC codes over finite fields using Gray maps.
2 Background on QC Codes, GQC Codes, and Torsion Modules
2.1 QC and GQC Codes
Let \({\mathbb {F}}_q\) be the finite field of order q, where q is a prime power. A linear code C of length n over \({\mathbb {F}}_q\) is an \({\mathbb {F}}_q\)-subspace of \({\mathbb {F}}_q^n.\) For any \({\mathbf {c}}=(c_1,\dots ,c_n)\) in C, define
Also, for any code \(C\subseteq {\mathbb {F}}_q^n,\) define the Hamming distance of C as follows:
Let T be a shift operator such that for any \({\mathbf {c}} =\left( c_0,c_1,\dots ,c_{n-1}\right) \in {\mathbb {F}}_q^n,\) we have \(T({\mathbf {c}})=\left( c_{n-1},c_0,\dots ,c_{n-2}\right) ,\) and let \(T^j(C)=\left\{ T^j({\mathbf {c}})\;\mid \;{\mathbf {c}}\in C\right\} .\) A linear code C of length mk over \({\mathbb {F}}_q\) is called a quasi-cyclic (QC) code of index k if \(T^k(C)\subseteq C\) and k is the smallest number with this property.
Let \(\displaystyle {R=\frac{{\mathbb {F}}_q[x]}{\langle x^m-1\rangle }}\) and define a map \(\phi : {\mathbb {F}}_q^{mk}\rightarrow R^k,\) where for any
we have
with \(c_i(x)=\sum _{j=0}^{m-1}c_{j,i}x^j,\) for all \(i=0,1,\dots ,k-1.\) We can check that, \(\phi \) is a one-to-one correspondence between the set of QC codes of index k and length mk over \({\mathbb {F}}_q\) and the set of linear codes of length k over R.
Let \(\sigma \) be a permutation in the symmetric group \(S_{mk},\) and \(T_\sigma \) be a shift operator induced by \(\sigma \) such that for any \({\mathbf {x}}=\left( x_1,\dots ,x_{mk}\right) \in {\mathbb {F}}_q^{mk},\) we have
Let \(T_\sigma (C)=\left\{ T_\sigma ({\mathbf {c}})\;\mid \;{\mathbf {c}}\in C\right\} .\) A linear code C of length mk over \({\mathbb {F}}_q\) is called \(\sigma \)-code if \(T_\sigma (C)\subseteq C.\) We have to note that any \(\sigma \)-code is permutation equivalent to a QC code. For this reason, we can say that a QC code is a \(\sigma \)-code. Using this point of view, we can generalize QC codes as follows.
Definition 1
Let \(m_1,m_2,\dots ,m_k\) be positive integers and \(\sigma =\sigma _1\cdots \sigma _k,\) where \(\sigma _1,\dots ,\sigma _k\) are disjoint cycles and
for all \(i=1,\dots ,k\) with \(s_0=0\) and \(s_j=\sum _{t=1}^jm_t,\) for all \(j=1,\dots ,k.\) A linear code C of length \(\sum _{i=1}^km_i\) over \({\mathbb {F}}_q\) is called a generalized quasi-cyclic (GQC) code of co-indices \((m_1,\dots ,m_k)\) if \(T_\sigma (C)\subseteq C.\)
Let \(\displaystyle {R_i=\frac{{\mathbb {F}}_q[x]}{\langle x^{m_i}-1\rangle }},\) for all \(i=1,2,\dots ,k,\) and \(R=R_1\times \cdots \times R_k.\) Define a map \(\varphi \) as follows.
where \({\mathbf {c}}_i(x)=\sum _{j=0}^{m_i-1}c_{\sigma ^{j}(s_{i-1})}x^j,\) for all \(i=1,2,\dots ,k.\) Let \(\varphi (C)\) be the image of C under the map \(\varphi .\) We have the following proposition.
Proposition 2
The map \(\varphi \) induces a one-to-one correspondence between \(\sigma \)-codes of length n over \({\mathbb {F}}_q\) and submodules of R over \({\mathbb {F}}_q[x].\)
Proof
Let C be a \(\sigma \)-code of length n over \({\mathbb {F}}_q.\) Then \(\varphi (C)\) is closed under multiplication by elements of \({\mathbb {F}}_q\) because C is a linear code. Since \(x^{m_i}=1\) in \(R_i,\) for all \(i=1,2,\dots ,k,\) consider
The above equation implies, for any \({\mathbf {c}}=(c_1,\dots ,c_n)\) in \({\mathbb {F}}_q^n,\)
So, \(\varphi (C)\) is also closed under the multiplication by x, and the action \(T_{\sigma }\) in C corresponds to the multiplication by x in R. Therefore, \(\varphi (C)\) is a submodule of R over \({\mathbb {F}}_q[x].\) \(\square \)
We have to note that, by Proposition 2, Definition 1 is equivalent to the definition of a GQC code in [4, 8, 15]. Also, when \(m_1=m_2=\cdots =m_k=m,\) a GQC code is a QC code of index m. Since a GQC code is a linear code invariant under a permutation \(\sigma ,\) for the rest of the paper, we will call a GQC code a \(\sigma \)-code. Seguin [14] introduced this term for the first time.
2.2 Torsion Modules
Let M be a module over a principal ideal domain \(R'.\) A nonzero element v in M for which \(rv=0\) for some nonzero element r in \(R',\) is called a torsion element. If all elements of M are torsion elements, then M is called a torsion module. Given an element u in M, the annihilator of u is
Moreover, the annihilator of a submodule N of M is
where \(rN=\{rw\;\mid \;w\in N\}.\) Any generator of \({{\,\mathrm{ann}\,}}(N)\) is called an order of N and denoted by o(N), and an order of an element u of M is an order of the submodule generated by u. The following theorem gives a cyclic decomposition of a finitely generated torsion module over \(R'.\)
Theorem 3
[13, Theorem 6.13] If M is a finitely generated torsion module over \(R'\) and \(o(M)=p_1^{e_1}\cdots p_n^{e_n},\) where \(p_i\)’s are distinct non-associate irreducible elements in \(R',\) then M can be uniquely decomposed into direct sum
where \(o(v_{i,j})=p_i^{e_{i,j}}\) and \(e_i=e_{i,1}\ge e_{i,2}\ge \cdots \ge e_{i,k_i},\) for all \(i=1,2,\dots ,n.\)
3 GQC Codes as Submodules of a Torsion Module
Let \(\sigma = \sigma _1\sigma _2\cdots \sigma _k\) in \(S_n,\) where \(\sigma _i\) is a cycle of length \(m_i,\) for all \(i=1,2,\dots ,k.\) In Sect. 2, we proved that a \(\sigma \)-code can be considered as a submodule of \(R=R_1\times R_2\times \cdots \times R_k\) over \({\mathbb {F}}_q[x],\) where \(R_i={\mathbb {F}}_q[x]/\langle x^{m_i}-1\rangle ,\) for all \(i=1,2,\dots ,k.\) The following proposition shows that R is a torsion module over \({\mathbb {F}}_q[x].\)
Proposition 4
The module R is a torsion module over \({\mathbb {F}}_q[x].\) Moreover, the order of R, o(R), is equal to \({{\,\mathrm{lcm}\,}}\left( x^{m_1}-1,\dots ,x^{m_k}-1\right) .\)
Proof
If \(r(x)={{\,\mathrm{lcm}\,}}\left( x^{m_1}-1,\dots ,x^{m_k}-1\right) ,\) then \(ra=0,\) for all a in R. So, R is a torsion module over \({\mathbb {F}}_q[x].\) Moreover, if \(S = {{\,\mathrm{ann}\,}}(R),\) then \(r(x)\in S.\) Since \({\mathbb {F}}_q[x]\) is a principal ideal domain, assume that \(S=\langle g(x)\rangle ,\) for some g(x) in \({\mathbb {F}}_q[x].\) Suppose that \(\deg (g)<\deg (r),\) then there exists \(i\in \{1,2,\dots ,k\}\) such that \(g\not \equiv 0 \mod (x^{m_i}-1).\) Consequently, if we choose \(a=(0,\dots ,0,1,0,\dots ,0)\in M,\) then \(ga\not =0,\) a contradiction. So, \(r=bg,\) for some \(b\in {\mathbb {F}}_q^\times .\) Therefore, \(S=\langle r(x)\rangle ,\) or \(o(M)=r(x)={{\,\mathrm{lcm}\,}}\left( x^{m_1}-1,\dots ,x^{m_k}-1\right) .\) \(\square \)
As a consequence of Proposition 4, we can decompose the module R using the primary decomposition theorem of the torsion module (see Theorem 3). First, we shall define the following notion.
Definition 5
For any \(a=(a_1,\dots ,a_k)\) in R, for some \(a_i\in R_i,\) \(i=1,2,\dots ,k,\) define the support of a as follows.
Moreover, if \(N\subseteq R\) is a submodule of R, then define
Let \(o(R)={{\,\mathrm{lcm}\,}}(x^{m_1}-1,\dots ,x^{m_k}-1)=f_1^{e_1}\cdots f_r^{e_r},\) where \(f_i\)’s are distinct non-associate irreducible polynomials over \({\mathbb {F}}_q\) and \({\mathbf {0}}=(0,0,\dots ,0).\) Also, let \(\omega _{ij}\) be an element of R such that
for all \(i=1,2,\dots ,r\) and \(j=1,2,\dots ,k,\) where \(e_{ij}\) is the algebraic multiplicity of \(f_i\) as an irreducible factor of \(x^{m_j}-1.\) As we can see, if \(\omega _{ij}\not ={\mathbf {0}},\) then \({{\,\mathrm{supp}\,}}(\omega _{ij})=\{j\}.\) We have the following result.
Theorem 6
Let \(o(R)={{\,\mathrm{lcm}\,}}(x^{m_1}-1,\dots ,x^{m_k}-1)=f_1^{e_1}\cdots f_r^{e_r},\) where \(f_i\)’s are distinct non-associate irreducible polynomials over \({\mathbb {F}}_q.\) Then,
-
(a)
we have the following decomposition of R,
$$\begin{aligned}R=\bigoplus _{i=1}^r\left( \bigoplus _{j=1}^{k}\langle \omega _{i,j}\rangle \right) ,\end{aligned}$$ -
(b)
if C is a \(\sigma \)-code of length \(\sum _{i=1}^km_i\) over \({\mathbb {F}}_q,\) then \(C=\bigoplus _{i=1}^r N_i,\) where \(N_i\) is a submodule of \(\bigoplus _{j=1}^{k}\langle \omega _{i,j}\rangle ,\) for all \(i=1,\dots ,r.\)
Proof
(a) If \(\omega _{ij}\not ={\mathbf {0}},\) then \(o(\omega _{ij})=f_i^{e_{ij}}.\) Since \(o(R)=f_1^{e_1}\cdots f_r^{e_r},\) by Theorem 3, we have the desired decomposition.
(b) Follows from part (a). \(\square \)
Let \(N_i=\sum _{j=1}^{\alpha _i}W_{i,j},\) where \(W_{i,1},\dots ,\) and \(W_{i,\alpha _i}\) are submodules of \(N_i\) with pairwise disjoint supports. Also, let \({\mathcal {P}}_1,{\mathcal {P}}_2,\dots ,{\mathcal {P}}_t\) be partitions of the set
such that \(W_{i_1,j_1},W_{i_2,j_2}\in {\mathcal {P}}_l\) if \({{\,\mathrm{supp}\,}}(W_{i_1,j_1})\cap {{\,\mathrm{supp}\,}}(W_{i_2,j_2})\not =\varnothing .\) We have the following consequence of Theorem 6.
Corollary 7
If C is a \(\sigma \)-code over \({\mathbb {F}}_q\) of length \(\sum _{i=1}^km_k,\) and \(C_i=\bigoplus _{W_{l,j}\in {\mathcal {P}}_i}N_{l_j},\) for \(1\le i\le t,\) then
-
(a)
\(\dim _{{\mathbb {F}}_q}(C)=\sum _{i=1}^t\dim _{{\mathbb {F}}_q}(C_i),\) where \(\dim _{{\mathbb {F}}_q}(C_i)=\deg (o(C_i)),\) and
-
(b)
\(d_H(C)=\min _{1\le j\le t}d_H(C_j).\)
Proof
We can see that \(C=\bigoplus _{j=1}^tC_j.\) Since \(C_1,\dots ,C_t\) have pairwise disjoint supports, we have
and
\(\square \)
Example 8
Let \(q=2, k=2, m_1=2,\) and \(m_2=3.\) Then, \(R=\displaystyle {\frac{{\mathbb {F}}_2[x]}{\langle x^2+1\rangle }\times \frac{{\mathbb {F}}_2[x]}{\langle x^3+1\rangle }}.\) Let \(f_1=x+1\) and \(f_2=x^2+x+1.\) We can check that
and
So, we have
and
Take \(N_1=\langle (f_1,0)\rangle \oplus \langle \omega _{1,2}\rangle .\) Let \(C=N_1,\) then we have
So, we have \(C_1=\langle (f_1,0)\rangle \) and \(C_2=\langle \omega _{1,2}\rangle .\) Since \(o((f_1,0))=f_1\) and \(o(\omega _{1,2})=f_1,\) we have \(\dim _{{\mathbb {F}}_2}(C_1)=\dim _{{\mathbb {F}}_2}(C_1)=1.\) These imply \(\dim _{{\mathbb {F}}_2}(C)=2.\) Moreover, we can see that \(d_H(C_1)=2\) and \(d_H(C_2)=3.\) Therefore, \(d_H(C)=2.\)
4 Dual Codes of GQC Codes and CRT Description of GQC Codes
This part will describe a way to find the dual code for a GQC code with arbitrary co-indices. This description differs from [8, Section 5], at least in two ways. First, our description does not restrict the block lengths (co-indices) to be coprime with q. In [8], the block lengths required to be coprime with q. Second, we do the description by injecting GQC codes into a set of QC codes with a longer length. Then, we only work on QC codes with one specific length (block lengths) and apply the known results for QC codes directly. In [8], the authors consider the “direct sum" of several QC codes, which could be of different lengths, for the description. Also, we describe a characterization for Euclidean self-dual GQC codes.
4.1 Dual Code of a GQC Code
Let \(l(x)={{\,\mathrm{lcm}\,}}\left( x^{m_1}-1,\dots ,x^{m_k}-1\right) ,\) \(\deg (l)=m,\) and \(m'={{\,\mathrm{lcm}\,}}(m_1,\dots ,m_k).\)
Lemma 9
A polynomial p(x) is a common multiple of \(x^{m_1}-1,x^{m_2}-1,\dots ,\) and \(x^{m_k}-1\) if and only if \(p(x)b(x)=0,\) for all \(b(x)\in R.\)
Proof
(\(\Rightarrow \)) When p(x) is a common multiple of \(x^{m_1}-1,x^{m_2}-1,\dots ,\) and \(x^{m_k}-1,\) we have that \(p(x)\equiv 0 \mod (x^{m_i}-1),\) for all \(i=1,\dots ,k.\)
(\(\Leftarrow \)) If \(p(x)b(x)=0\) for all \(b(x)\in R,\) then \(p(x)(1,1,\dots ,1)=0.\) So, we have \(p\equiv 0 \mod (x^{m_i}-1),\) for all \(i=1,\dots ,k.\) Therefore, \(x^{m_i}-1\mid p(x),\) for all \(i=1,\dots ,k.\)
\(\square \)
Proposition 10
Let \(\langle l(x)\rangle \) be the ideal generated by l(x) in \({\mathbb {F}}_q[x].\) Then, \(\langle x^{m'}-1\rangle \subseteq \langle l(x)\rangle .\)
Proof
Since \(\sigma =\sigma _1\sigma _2\cdots \sigma _k,\) where \(\sigma _i\) is a cycle of length \(m_i,\) for all \(i=1,2,\dots ,k,\) we have \(order(\sigma )=m'\) and \(T^{m'}_\sigma ({\mathbf {a}})={\mathbf {a}}.\) Recall that \(T^j_\sigma ({\mathbf {a}})\) corresponds to \(x^j(\varphi ({\mathbf {a}})).\) So, we have \(x^{m'}(\varphi ({\mathbf {a}}))=\varphi ({\mathbf {a}})\) or \((x^{m'}-1)\varphi ({\mathbf {a}})=0.\) By Lemma 9, \(x^{m'}-1\) is a common multiple of \(x^{m_1}-1,x^{m_2}-1,\dots ,\) and \(x^{m_k}-1.\) Therefore, \(l(x)\mid x^{m'}-1.\) \(\square \)
Based on Proposition 10, it is natural to define an injective map from \({\mathbb {F}}_q^n\) to \(R'=\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }\times \cdots \times \frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}.\) Any \({\mathbf {a}}\) in \({\mathbb {F}}_q^n\) can be written as
where \({\mathbf {a}}_i\in {\mathbb {F}}_q^{m_i},\) for all \(i=1,2,\dots ,k.\) Define a map from \({\mathbb {F}}_q^n,\) where \(n=m_1+m_2+\cdots +m_k,\) to \({\mathbb {F}}_q^{m'k}\) as follows.
with
where \(n_i=\displaystyle {\frac{m'}{m_i}}.\)
Let \({\mathbf {a}}^{(i)}=\left( a_{i1},a_{i2},\dots ,a_{im'}\right) ,\) and define a map from \(\lambda _1\left( {\mathbb {F}}_q^{n}\right) \) to \({\mathbb {F}}_q^{m'k}\) as follows.
where \({\mathbf {a}}_{(j)}=(a_{1j},a_{2j},\dots ,a_{kj}),\) for all \(j=1,2,\dots ,m'.\) Now, we shall define a map from \({\mathbb {F}}_q^n\) to \({\mathbb {F}}_q^{m'k}\) as follows.
We have the following result related to the map \(\lambda .\)
Theorem 11
If C is a \(\sigma \)-code of length n, then \(\lambda (C)\) is a quasi-cyclic code of length \(m'k\) with index k.
Proof
We can check that \(\lambda \left( T_\sigma ({\mathbf {a}})\right) =T^k(\lambda ({\mathbf {a}})).\) Therefore, if \(T_\sigma ({\mathbf {a}})\in C,\) then \(T^k(\lambda ({\mathbf {a}}))\in \lambda (C).\) \(\square \)
Example 12
Let \(q=2, k=2, m_1=2,\) and \(m_2=3.\) So, \(\sigma = (1\;2)(3\;4\;5), n=5,\) and \(m'=6.\) Let \({\mathbf {a}}= \left( 1,0,0,0,0\right) ,{\mathbf {b}}=\left( 0,1,0,0,0\right) ,\) and \(C=\langle {\mathbf {a}},{\mathbf {b}}\rangle .\) We can check that C is a binary \(\sigma \)-code of length 5. Also,
where \(a^{(1)}=(1,0,1,0,1,0), a^{(2)}=b^{(2)}=(0,0,0,0,0,0), b^{(1)}=(0,1,0,1,0,1).\) So, we have
and
We can see that \(T^2\left( \lambda ({\mathbf {a}})\right) =\lambda ({\mathbf {b}})\) and \(T^2\left( \lambda ({\mathbf {b}})\right) =\lambda ({\mathbf {a}}).\) Therefore,
is a binary quasi-cyclic code of index 2 and length 12.
Any \({\mathbf {b}}\in {\mathbb {F}}_q^{m'k}\) can be written as
Now, define a map from \({\mathbb {F}}_q^{m'k}\) to \(R'=\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }\times \cdots \times \frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\) as follows
where \(b_i(x)=\sum _{j=0}^{m'-1}b_{(j+1)i}x^j,\) for all \(i=1,2,\dots ,k.\)
The map \(\phi \) is a one-to-one correspondence between quasi-cyclic codes of length \(m'k\) and \(\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\)-submodules of \(R',\) see [10, 11] for more details. By composing \(\lambda \) and \(\phi ,\) we have the following map.
For our convenience, we shall define the following notion.
Definition 13
A vector \({\mathbf {a}}=(a_1,\dots ,a_t)\) in \({\mathbb {F}}_q^t\) is said to be the coefficients vector for a polynomial f(x) if \(f(x)=\sum _{i=0}^{t-1}a_{i+1}x^i.\)
We have the following properties related to the image of \(\mu .\)
Proposition 14
If \(\mu ({\mathbf {a}})=\left( a_1(x),\dots ,a_k(x)\right) ,\) then \(a_i(x)=f_i(x)\sum _{j=0}^{n_i-1}x^{jm_i},\) for some \(f_i(x)\in \displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\) with coefficients vector \({\mathbf {a}}_i,\) where \(n_i=\displaystyle {\frac{m'}{m_i}},\) for all \(i=1,2,\dots ,k.\)
Proof
We can check that the coefficients vector for \(a_i(x)\) is \({\mathbf {a}}^{(i)}.\) By Eq. 5, we have that
for some \(f_i(x)\in \displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\) with coefficients vector \({\mathbf {a}}_i,\) where \(n_i=\displaystyle {\frac{m'}{m_i}}.\) \(\square \)
Theorem 15
A code C is a \(\sigma \)-code of length n over \({\mathbb {F}}_q\) if and only if \(\mu (C)\) is a \(\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\)-submodule of \(R',\) where for any \({\mathbf {c}} =(c_1(x),\dots ,c_{k}(x)) \in \mu (C)\) we have
for some \(f_i(x)\in \displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\) with coefficients vector \({\mathbf {c}}_i\in {\mathbb {F}}_q^{m_i}\) for all \(i=1,2,\dots ,k.\)
Proof
Apply Proposition 14 and the fact that \(\phi (C)\) is an \(\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\)-submodule of \(R'.\)
\(\square \)
Example 16
Consider the \(\sigma \)-code C in Example 12. We can check that,
As we can see,
and \(\mu (C)\) is a \(\displaystyle {\frac{{\mathbb {F}}_2[x]}{\langle x^{6}-1\rangle }}\)-submodule of \(R'=\left( \displaystyle {\frac{{\mathbb {F}}_2[x]}{\langle x^{6}-1\rangle }}\right) ^2\) generated by \(\mu ({\mathbf {a}})\) and \(\mu ({\mathbf {b}}).\)
Conversely, take a submodule \(C'\!=\!\langle {\mathbf {c}}\rangle \) of \(R',\) where \({\mathbf {c}}\!=\!\left( 0,(1+x+x^2)\sum _{i=0}^1x^{3i}\right) .\) We can see that,
Therefore, the code \(\mu ^{-1}(C')=\langle \mu ^{-1}({\mathbf {c}})\rangle \) is a binary \(\sigma \)-code of length 5.
The following lemma shows that the map \(\lambda \) preserves duality.
Lemma 17
If \({\mathbf {c}}\cdot {\mathbf {c}}'=0\) in \({\mathbb {F}}_q^n,\) then \(\lambda ({\mathbf {c}})\cdot \lambda ({\mathbf {c}}')=0\) in \({\mathbb {F}}_q^{m'k}.\)
Proof
It is clear that
\(\square \)
Before we describe duality in \(R',\) we need to show the following property.
Theorem 18
Let C be a code of length n over \({\mathbb {F}}_q\) and \(C^\bot \) be its Euclidean dual. If \(C_1=\lambda \left( C\right) ^\bot \cap \lambda \left( {\mathbb {F}}_q^n\right) ,\) then \(C_1=\lambda (C^\bot ).\)
Proof
By Lemma 17, we have \(\lambda (C^\bot )\subseteq C_1.\) Also, we have \(dim(C_1)=n-dim(\lambda (C))=n-dim(C)=dim(C^\bot ).\) Therefore, \(C_1=\lambda (C^\bot ).\) \(\square \)
Theorem 18 shows that for any \({\mathbf {c}}'\) in \(\lambda ({\mathbb {F}}_q^n),\) which satisfies \({\mathbf {c}}'\cdot \lambda ({\mathbf {c}})=0\) for all \({\mathbf {c}}\) in C, we have \({\mathbf {c}}'\in \lambda (C^\bot ).\)
Now, define a conjugation map, denoted by \(^-,\) on \(\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }},\) where \({\overline{\alpha }}=\alpha ,\) for all \(\alpha \) in \({\mathbb {F}}_q,\) and \({\overline{x}}=x^{m'-1}.\) Also, define Hermitian inner product on \(R'\) as follows: for \({\mathbf {a}}=(a_1,\dots ,a_k)\) and \({\mathbf {b}}=(b_1,\dots ,b_k)\) in \(R',\)
For any submodule C in of \(R',\) define \(C^H=\left\{ {\mathbf {c}}'\in R' \mid \langle {\mathbf {c}},{\mathbf {c}}'\rangle =0,\forall {\mathbf {c}}\in C\right\} .\)
Proposition 19
Let \({\mathbf {a}},{\mathbf {b}}\in {\mathbb {F}}_q^n.\) Then, \(T_{\sigma }^{j}({\mathbf {a}})\cdot {\mathbf {b}}=0,\) for all \(0\le j\le \omega -1,\) if and only if \(\langle \mu ({\mathbf {a}}),\mu ({\mathbf {b}}) \rangle =0.\)
Proof
We can see that \(T^{\alpha k}(\lambda ({\mathbf {a}}))\cdot \lambda ({\mathbf {b}})=0,\) for all \(0\le \alpha \le m'-1\) if and only if \(T_\sigma ^j({\mathbf {a}})\cdot {\mathbf {b}}=0,\) for all \(0\le j\le m'-1.\) By [11, Proposition 3.2], \(T^{\alpha k}(\lambda ({\mathbf {a}}))\cdot \lambda ({\mathbf {b}})=0,\) for all \(0\le \alpha \le m'-1\) if and only if \(\langle \mu ({\mathbf {a}}),\mu ({\mathbf {b}})\rangle =0,\) as we hope. \(\square \)
As a consequence, we have the following result.
Theorem 20
If C is a \(\sigma \)-code of length n over \({\mathbb {F}}_q,\) \(\mu (C)\) is its image under the map \(\mu ,\) and \(C_2=\mu (C)^H\cap \mu ({\mathbb {F}}_q^n),\) then
-
(i)
the equation \(\mu \left( C^\bot \right) =C_2\) holds, and
-
(ii)
the code C is Euclidean self-dual over \({\mathbb {F}}_q\) if and only if the code \(\mu (C)\) is Hermitian self-dual over \({\mathbb {F}}_q[x]\) in \(\mu ({\mathbb {F}}_q^n).\)
Proof
Apply Theorem 18, Proposition 19, and [11, Corollary 3.3]. \(\square \)
We have to note that, by Proposition 15, a \(\sigma \)-code C is Euclidean self-dual if and only if \(\mu (C)\) is Hermitian self-dual over \({\mathbb {F}}_q[x]\) in \(\mu ({\mathbb {F}}_q^n),\) where for any \({\mathbf {c}} =(c_1(x),\dots ,c_{k}(x)) \in \mu (C),\)
for some \(f_i(x)\in \displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\) with coefficients vector \({\mathbf {c}}_i\in {\mathbb {F}}_q^{m_i},\) for all \(i=1,2,\dots ,k.\)
4.2 CRT Description of GQC Codes and Their Duals
Let \(q=p^r,\) for some prime number p and positive integer \(r\ge 1.\) Also, let \(m'=p^a{\dot{m}},\) where \(gcd(p,{\dot{m}})=1.\) The polynomial \(x^{{\dot{m}}}-1\) factors completely into distinct irreducible factors in \({\mathbb {F}}_q[x]\) as follows.
where \(\delta \in {\mathbb {F}}_q^\times ,\) \(g_1,\dots ,g_s\) are self-reciprocal factors, and \(h_j,h_j^*\) are reciprocal pairs for all \(j=1,2,\dots ,t.\) Now, we have
As a consequence, by [10] we have
where \(G_i=\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle g_i^{p^a}\rangle }},\) for all \(i=1,2,\dots ,s,\) \(H_j=\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle h_j^{p^a}\rangle }}\) and \(H_j'=\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle (h_j^*)^{p^a}\rangle }},\) for all \(j=1,2,\dots ,t.\) So, from (12), we have
Therefore, any submodule C of \(\left( \displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\right) ^k\) over \(\displaystyle {\frac{{\mathbb {F}}_q[x]}{\langle x^{m'}-1\rangle }}\) can be decomposed as
where \(C_i\) is a submodule of \(G_i^k\) over \(G_i,\) for all \(i=1,2,\dots ,s,\) \(C_j'\) and \(C_j''\) are submodules of \(H_j^k\) over \(H_j\) and \((H_j')^k\) over \(H_j',\) respectively, for all \(j=1,2,\dots ,t.\)
Now, let \({\mathbf {b}}_i=\sum _{j=0}^{n_i-1}x^{jm_i},\) where \(n_i=\displaystyle {\frac{m'}{m_i}},\) and \({\mathbf {b}}_{if}={\mathbf {b}}_i\mod f(x).\) We have the following results.
Theorem 21
A code C is a \(\sigma \)-code of length n over \({\mathbb {F}}_q\) if and only if
where
-
(i)
for any \({\mathbf {c}}_i = (c_{i1},\dots ,c_{ik}) \in C_i\le G_i^k,\) we have \(c_{il}=f_l{\mathbf {b}}_{lg_i},\) for some \(f_l\in G_i,\) for all \(l=1,2,\dots ,k\) and \(i=1,2,\dots ,s,\) and
-
(ii)
for any \({\mathbf {c}}_j' = (c_{j1}',\dots ,c_{jk}') \in C_j'\le H_j^k\) and \({\mathbf {c}}_j'' = (c_{j1}'',\dots ,c_{jk}''),\in C_j''\le (H_j')^k,\) we have \(c_{jl}'=f_l'{\mathbf {b}}_{lh_j}\) and \(c_{jl}''=f_l''{\mathbf {b}}_{lh_j'},\) for some \(f_l'\in H_j\) and \(f_l''\in H_j',\) for all \(l=1,2,\dots ,k\) and \(j=1,2,\dots ,t.\)
Proof
Apply Theorem 15, Eq. 14, and Chinese remainder algorithm (see [6, Algorithm 5.4]). \(\square \)
Theorem 22
A code C is a Euclidean self-dual \(\sigma \)-code of length n over \({\mathbb {F}}_q\) if and only if
where
-
(i)
for any \({\mathbf {c}}_i = {\mathbf {c}}_i=(c_{i1},\dots ,c_{ik}) \in C_i\le G_i^k,\) we have \(c_{il}=f_l{\mathbf {b}}_{lg_i},\) for some \(f_l\in G_i,\) for all \(l=1,2,\dots ,k\) and \(i=1,2,\dots ,s,\)
-
(ii)
for any \({\mathbf {c}}_j' = (c_{j1}',\dots ,c_{jk}'),\in C_j'\le H_j^k,\) we have \(c_{jl}'=f_l'{\mathbf {b}}_{lh_j},\) for some \(f_l'\in H_j,\) for all \(l=1,2,\dots ,k\) and \(j=1,2,\dots ,t.\)
-
(iii)
submodule \(C_i\) is Hermitian self-dual over \(G_i,\) for all \(i=1,2,\dots ,s,\) and
-
(iv)
submodule \((C_j')^\bot \) is the Euclidean dual of \(C_j',\) for all \(j=1,2,\dots ,t,\)
Proof
Apply Theorem 21 and [11, Theorem 4.2]. \(\square \)
Example 23
Let \(q=2, k=2, m_1=2,\) and \(m_2=3.\) So, \(m'=6\) and
where \(g_1(x)=x+1\) and \(g_2(x)=x^2+x+1.\) Moreover,
where \(G_1=\displaystyle {\frac{{\mathbb {F}}_2[x]}{\langle g_1^2\rangle }}\) and \(G_2=\displaystyle {\frac{{\mathbb {F}}_2[x]}{\langle g_2^2\rangle }}.\) Also, let \({\mathbf {b}}_1=1+x^2+x^4\) and \({\mathbf {b}}_2=1+x^3.\) Then,
and
Now, if we take \(M_1=\langle (1\cdot {\mathbf {b}}_{1,g_1^2},0\cdot {\mathbf {b}}_{1,g_2^2})\rangle \subseteq G_1^2\) and \(M_2=\langle (0\cdot {\mathbf {b}}_{2,g_1^2},0\cdot {\mathbf {b}}_{2,g_2^2})\rangle \subseteq G_2^2,\) then \(M=M_1\oplus M_2\) is a \(\sigma \)-code of length 5 over \({\mathbb {F}}_2.\) Moreover, \(\mu ^{-1}(M)=C,\) where C is the \(\sigma \)-code in Example 12.
Now, we want to find the dual code of the code C from Example 12. We can check that, \(M_1^H=\langle (0,1)\rangle , M_2^H=G_2^2,\) and \(M^H=M_1^H\oplus M_2^H.\) Now, take \(M_1'=\langle (0,1\cdot {\mathbf {b}}_{2,g_1^2})\rangle \subseteq M_1^H\) and \(M_2'=\langle (0,1\cdot {\mathbf {b}}_{2,g_2^2})\rangle \subseteq M_2^H.\) If \(M'=M_1'\oplus M_2',\) then \(C^\bot =\mu ^{-1}(M').\)
5 General Construction Algorithm for GQC Codes and Some Examples
The results in two previous sections, especially Theorem 6 and Theorem 21, give us the following systematic ways to construct GQC codes.
Algorithm 24
Given \(m_1,m_2,\dots ,m_k\) and \({\mathbb {F}}_q.\)
-
(1)
Calculate the polynomial \(l(x)={{\,\mathrm{lcm}\,}}(x^{m_1}-1,\dots ,x^{m_k}-1).\)
-
(2)
Find polynomials \(f_1(x),\dots ,f_r(x),\) all non-reducible factors of l(x).
-
(3)
Calculate \(\omega _{ij},\) for all \(i=1,\dots ,r\) and \(j=1,\dots ,k.\)
-
(4)
Choose \(N_i,\) for all \(i=1,\dots ,r,\) as stated in Theorem 6(b).
-
(5)
Code \(C=\bigoplus _{i=1}^rN_i\) is a GQC code with co-indices \((m_1,\dots ,m_k).\)
Algorithm 25
Given \(m_1,m_2,\dots ,m_k\) and \({\mathbb {F}}_q.\)
-
(1)
Calculate \(m'={{\,\mathrm{lcm}\,}}(m_1,\dots ,m_k)\) and \(m'={\dot{m}}p^a,\) where \(\gcd ({\dot{m}},p)=1.\)
-
(2)
Find all factors of \(x^{{\dot{m}}}-1\) over \({\mathbb {F}}_q\) as expressed in equation 10
-
(3)
Derive the decomposition of \(x^{m'}-1\) using equation 11
-
(4)
Determine polynomials \({\mathbf {b}}_1,\dots ,{\mathbf {b}}_k.\)
-
(5)
Calculate \({\mathbf {b}}_{i,w}={\mathbf {b}}_i\mod w(x),\) for all \(i=1,2,\dots ,k,\) where \(w(x)=f(x)^{p^a}\) and f(x) is an irreducible factor of \(x^{{\dot{m}}}-1\) in step (2).
-
(6)
Construct GQC code C using Theorem 21.
See Example 12 (for Algorithm 24) and Example 23 (for Algorithm 25). The above algorithms, especially Algorithm 24, enable us to search for new GQC codes with the best known parameters using Octave. The results compared to the best known linear codes tables in [7] and the best known linear codes database from magma. Due to memory limitation in Octave, we only search for optimal GQC codes of small length and dimension. Here is an example of an optimal binary GQC code of length 5.
Example 26
Let \(q=2, m_1=2\) and \(m_2=3.\) Using the information from Example 8, choose \(C=\langle (1+x)\omega _{1,1}\rangle \oplus \langle \omega _{2,2}\rangle .\) We can see that, by Corollary 7, C is a \(\sigma \) binary code with dimension 3 and Hamming distance 2. As a binary code, C has the following generator matrix
Denote by \(C'\) the best known [5, 3, 2] binary linear code from the magma database. We have the following comparison of weights distribution between C and \(C'.\)
Weight | C | \(C'\) |
---|---|---|
0 | 1 | 1 |
2 | 4 | 6 |
4 | 3 | 1 |
We can see that C and \(C'\) are not equivalent. Also, note that one of the co-indices of C, i.e., \(m_2=2,\) is not co-prime to \(q=2.\)
Using a similar way as in Example 26 and Algorithm 24, we construct new binary, ternary, and 5-ary \(\sigma \)-codes with best known parameters as shown in Tables 1,2, and 3. Note that the generator given in the table is for the corresponding submodule. The letters k and d stand for dimension and Hamming distance of the corresponding binary/ternary/5-ary code, respectively.
6 Generalized Quasi-Cyclic Codes Over the Ring \(B_k\)
Let \({\mathbb {F}}_q\) be the finite field of order q, where \(q=p^r,\) for prime p and positive integer r. In this section, we will study generalized quasi-cyclic codes (GQC) over the ring \(B_k.\) The ring \(B_{k}\) is defined as \(B_{k}:={\mathbb {F}}_{q}[v_1,v_2,\dots ,v_k]/\langle v_i^2-v_i,v_iv_j-v_jv_i \rangle \) for all \(i,j=1,\dots ,k.\) This ring essentially differs from the one considered by Gao et al. in [5]. In [5], the authors described the structural properties of GQC codes over the ring \({\mathbb {F}}_q+u{\mathbb {F}}_q,\) where \(u^2=0,\) using the Chinese remainder theorem. The ring \({\mathbb {F}}_q+u{\mathbb {F}}_q,\) where \(u^2=0,\) is a chain ring. Meanwhile, the ring \(B_k\) is not a chain ring. Also, similar studies have been done before in [3] for GQC codes over Galois rings under the assumption that the code’s block lengths are coprime with the characteristic of the corresponding Galois ring. The main tool in [3] is also the Chinese remainder theorem. The main focus of this part is to describe a connection between GQC codes over \(B_k\) and GQC codes over the corresponding finite field using two types of Gray maps. This connection gives a way to construct GQC codes over finite fields from a GQC code over \(B_k.\)
6.1 Gray Maps
Let \(B_j={\mathbb {F}}_q[v_1,\dots ,v_j]/(v_i^2-v_i, \forall i=1,2,\dots ,j).\) For any a in \(B_j,\) we can write a as \(a=\alpha +\beta v_{j},\) for some \(\alpha \) and \(\beta \) are elements in \(B_{j-1}.\) We define a map \(\varphi _{j}\) as follows.
where \(\beta _i,\beta _i'\) are elements in \(B_{j-1},\) for all \(1\le i\le l_j,\) and \(\beta _{l_{j}-1}'\) is a unit in \(B_{j-1}.\) We can check that the map \(\varphi _j\) is an injective map because \(\beta _{l_{j-1}}'\) is a unit.
Example 27
Let \(q=2\) and \(B_1={\mathbb {F}}_2+v{\mathbb {F}}_2,\) where \(v^2=v\) and \(B_0={\mathbb {F}}_2.\) Define a map
We can see that
This means, the map \(\varphi _1\) is injective.
We can extend the map \(\varphi _j\) as follows.
Example 28
Let \(\varphi _1\) be the map in Example 27. Then, we have an extension of \(\varphi _1\) as follows.
Now, we define another map. For any \(\alpha \) in \(B_k,\) we can write \(\alpha \) as \(\alpha = \sum _{i=1}^{2^k}\alpha _{S_i}v_{S_i},\) for some \(\alpha _{S_i}\) in \({\mathbb {F}}_q,\) where \(S_i\subseteq \{1,2,\dots ,k\}\) and \(v_{S_i}=\prod _{t\in S_i}v_t,\) for all \(1\le i\le 2^k.\) Note that, if \(S=\varnothing ,\) then \(v_S=1.\) Define a map \(\Psi \) as follows.
Note that the map \(\Psi \) is a bijective map, and we can extend the map \(\Psi \) as follows.
where \(\Psi (a_i)\) is written as a column vector in the image for all \(1\le i\le n.\)
Example 29
Let \(q=2,\) and \(B_1={\mathbb {F}}_2+v{\mathbb {F}}_2=\left\{ 0,1,2,v,1+v\right\} .\) We have
Moreover, for \(n=3,\) the extension of \(\Psi \) will be as follows.
where
6.2 Generalized Quasi-Cyclic Codes
The following definition of GQC codes is similar to Definition 1.
Definition 30
Let \({\mathbf {c}}\in B_k^n,\) with \({\mathbf {c}}=\left( {\mathbf {c}}^{(1)}\mid {\mathbf {c}}^{(2)}\mid \cdots \mid {\mathbf {c}}^{(d)}\right) ,\) where \({\mathbf {c}}^{(i)}\in B_k^{t_i},\) for some \(t_i\in {\mathbb {N}},\) for all \(i=1,2,\dots ,d.\) Let \(\sigma \) be a map from \(B_k^n\) to \(B_k^n\) such that \(\sigma ({\mathbf {c}})=\left( \sigma _{t_1}\left( {\mathbf {c}}^{(1)}\right) \mid \sigma _{t_2}\left( {\mathbf {c}}^{(2)}\right) \mid \cdots \mid \sigma _{t_d}\left( {\mathbf {c}}^{(d)}\right) \right) ,\) where \(\sigma _{t_i}\) is a cyclic shift from \(B_k^{t_i}\) to \(B_k^{t_i}.\) A code C of length n over ring \(B_k\) is said to be a generalized quasi-cyclic code with co-indices \((t_1,t_2,\dots ,t_d)\) or a \(\sigma \)-code if \(\sigma (C)=C.\)
Example 31
Let \(q=2\) and \(C=\langle (v_1,v_1,v_1,1+v_2,1+v_2) \rangle \) be a code of length 5 over \(B_2.\) Any \({\mathbf {c}}\) in C can be rewritten as \({\mathbf {c}}=({\mathbf {c}}^{(1)}\mid {\mathbf {c}}^{(2)}),\) where \({\mathbf {c}}^{(1)}\subseteq B_2^3\) and \({\mathbf {c}}^{(2)}\subseteq B_2^2.\) Based on this arrangement, we have for any \({\mathbf {c}}\) in C,
Therefore, C is a GQC code with co-indices (3, 2) over \(B_2.\)
The following property describes the image of a GQC code under the map \({\overline{\varphi }}_j.\)
Theorem 32
If C is a GQC code of length n with co-indices \(\left( t_1,\dots , t_d\right) \) over \(B_j,\) then \({\overline{\varphi }}_j(C)\) is a GQC code of length \(nl_j\) with co-indices \(\left( t_1,\dots ,t_d,\dots ,t_1,\dots ,t_d\right) \) over \(B_{j-1}.\)
Proof
Any \({\mathbf {c}}\) in C can be written as
for some \({\mathbf {c}}_s^{(r)}\subseteq B_{j-1}^{t_r},\) for all \(1\le r\le d\) and for all \(1\le s\le 2.\) Then, we have
Moreover, we have
Since C is a GQC code with co-indices \(\left( t_1,\dots ,t_d\right) ,\) we can see that \(\sigma \left( {\overline{\varphi }}_j({\mathbf {c}})\right) \) is also in \({\overline{\varphi }}_j(C)\). Therefore, by injectivity of \({\overline{\varphi }}_j\) we conclude that \({\overline{\varphi }}_j(C)\) is a GQC code of length \(nl_j\) with co-indices \(\left( t_1,\dots ,t_d,\dots ,t_1,\dots ,t_d\right) \) over \(B_{j-1}.\) \(\square \)
The following result is a direct consequence of Proposition 32.
Theorem 33
If C is a GQC code of length n with co-indices \(\left( t_1\,\dots ,t_d\right) \) over \(B_k,\) then \({\overline{\varphi }}_1\circ \cdots \circ {\overline{\varphi }}_k(C)\) is a GQC code of length \(n\prod _{j=1}^kl_j\) with co-indices \(\left( t_1,\dots ,t_d,\dots ,t_1,\dots ,t_d\right) \) over \({\mathbb {F}}_q.\)
Proof
Apply Proposition 32k times. \(\square \)
Here are examples on how to get GQC codes over a finite field from a GQC code over \(B_k\) using the map \({\overline{\varphi }}_i.\)
Example 34
Let \(\pi = (1\;4)(2\;3)\) and \(C=\langle (1,1,v,1),(1,v,1,1)\rangle .\) We can see that C is a \(\pi \)-code of length 4 over \(B_1.\) Moreover,
Define a map \(\varphi _1\) such that \(\varphi _1(\alpha +\beta v)=(\alpha ,\beta )\) and its extension
We have
Therefore, \({\overline{\varphi }}_1(C)\) is a [8, 3, 4] \(\pi ^{(2)}\)-code over \({\mathbb {F}}_2,\) where \(\pi ^{(2)}=(1\; 4)(2\; 3)(5\; 8)(6\; 7).\) Also, C is the best known linear [8, 3, 4] code over \({\mathbb {F}}_2\) according to the best known linear codes in magma.
Example 35
Let \(B_3=\sum _{S\subseteq \{1,2,3\}}v_S{\mathbb {F}}_2\) and \(C=\left\{ \left( 0,0,0\right) ,\left( v_1+v_2,v_1+v_2,0\right) \right\} .\) We can see that C is a GQC code of length 3 with co-indices (2, 1) over \(B_3.\) Take
and
Then, we have
We can check that \(C'\) is a binary GQC code of length 24 with co-indices
\((2,1,2,1,2,1,\dots ,2,1,2,1).\)
By a similar way as in Example 34, we can find some other examples of best known binary linear codes according to the database in magma as presented in Table 4. There are no new optimal codes in Table 4. The data in Table 4 are provided only to show that we can derive some best known linear codes from GQC codes over \(B_k\) with shorter length.
For any code C of length n over \(B_k,\) there exist q-ary codes, \(C_1,C_2,\dots ,C_{2^k},\) of length n such that \(C={\overline{\Psi }}^{-1}(C_1,\dots ,C_{2^k}).\) The following proposition gives a characterization of a GQC code.
Theorem 36
Let \(C={\overline{\Psi }}^{-1}(C_1,\dots ,C_{2^k}),\) for some q-ary codes \(C_1,\dots , C_{2^k}.\) The code C is a GQC code of length n with co-indices \(\left( t_1,\dots ,t_d\right) \) over \(B_k\) if and only if \(C_1,C_2,\dots ,C_{2^k}\) are GQC codes of length n with co-indices \(\left( t_1,\dots ,t_d\right) \) over \({\mathbb {F}}_q.\)
Proof
(\(\Longrightarrow \)) Take any \({\mathbf {c}}_i\) in \(C_i,\) for all \(1\le i\le 2^k.\) We want to show that \(\sigma ({\mathbf {c}}_i)\) is also in \(C_i\) for all \(1\le i\le 2^k.\)
There exists \({\mathbf {c}}\) in C such that \({\overline{\Psi }}({\mathbf {c}})=({\mathbf {c}}_1,\dots ,{\mathbf {c}}_{2^k}).\) Since \(\sigma (C)=C,\) we have \({\overline{\Psi }}(\sigma ({\mathbf {c}}))=(\sigma ({\mathbf {c}}_1),\dots ,\sigma ({\mathbf {c}}_{2^k}))\) is also in \({\overline{\Psi }}(C).\) So, \(\sigma ({\mathbf {c}}_i)\in C_i\) for all \(1\le i\le 2^k.\) By bijectivity of \({\overline{\Psi }},\) we have \(C_i\) is a generalized quasi-cyclic code with co-indices \(\left( t_1,\dots , t_d\right) ,\) for all \(1\le i\le 2^k.\)
(\(\Longleftarrow \)) For any \({\mathbf {c}}\) in C, there exist codewords \({\mathbf {c}}_1,\dots , {\mathbf {c}}_{2^k},\) where \({\mathbf {c}}_i\in C_i\) for all \(1\le i\le 2^k,\) such that \({\overline{\Psi }}({\mathbf {c}})=({\mathbf {c}}_1,\dots ,{\mathbf {c}}_{2^k}).\) Then, we have \({\overline{\Psi }}(\sigma ({\mathbf {c}}))=(\sigma ({\mathbf {c}}_1),\dots ,\sigma ({\mathbf {c}}_{2^k})).\) Since \(\sigma (C_i)=C_i\) for all \(1\le i\le 2^k,\) we have that \((\sigma ({\mathbf {c}}_1),\dots ,\sigma ({\mathbf {c}}_{2^k}))\) is also in \((C_1,\dots ,C_{2^k}).\) Therefore, \(\sigma ({\mathbf {c}})\) is in C. \(\square \)
Here is an example of getting GQC codes over a finite field from a GQC code over \(B_k\) using the map \({\overline{\Psi }}.\)
Example 37
Let \(q=2\) and \(C=\langle (v,v,1+v,1+v,1+v)\rangle \) be a code of length 5 over \(B_1={\mathbb {F}}_2+v{\mathbb {F}}_2,\) where \(v^2=v.\) We can check that
So, C is a GQC code with co-indices (2, 3). Also, since
we have that \(C={\overline{\Psi }}(C_1,C_2),\) where
and
As we can see, \(C_1\) and \(C_2\) are generalized quasi-cyclic codes of length 5 with co-indices (2, 3) over \({\mathbb {F}}_2.\)
Here is an example of how to get a GQC code over \(B_k\) from GQC codes over a finite field using the map \({\overline{\Psi }}.\)
Example 38
Let \(C_1=C_2=\{(1,1,0), (0,0,0)\}\) and \(C_3=C_4=\{(0,0,0)\}\) are binary codes of length 3. We can see that \(C_i\) is a GQC code with co-indices (2, 1). Let \(S_1=\varnothing , S_2=\{1\}, S_3=\{2\},\) and \(S_4=\{1,2\}.\) Then, we have
and
So, we have
We can see that C is a GQC code with co-indices (2, 1) over \(B_2={\mathbb {F}}_2+v_1{\mathbb {F}}_2+v_2{\mathbb {F}}_2+v_1v_2{\mathbb {F}}_2.\)
References
Baldi, M.: QC-LDPC Code Based Cryptography. Springer, Berlin (2014)
Berger, T.P.: Goppa and related codes invariant under a prescribed permutation. IEEE Trans. Inf. Theory 46(7), 2628–2633 (2000)
Cao, Y.: Generalized quasi-cyclic codes over Galois rings: structural properties and enumeration. Appl. Alg. Eng. Comm. Comput 22, 219 (2011). https://doi.org/10.1007/s00200-011-0145-5
Esmaeili, M., Yari, S.: Generalized quasi-cyclic codes: structural properties and code construction. Appl. Alg. Eng. Comm. Comput. 20, 159–173 (2009)
Gao, J., Shen, L., Fu, F.W.: Generalized quasi-cyclic codes over \({\mathbb{F}}_q+u{\mathbb{F}}_q\), https://arxiv.org/abs/1307.1746v1
von sur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013)
Grassl, M., Bounds on the minimum distance of linear codes and quantum codes, online available at http://www.codetables.de, Accessed on 2021-09-01
Güneri, C., Özbudak, F., Özkaya, B., Saçikara, E., Sepasdar, Z., Solé, P.: Structure and performance of generalized quasi-cyclic codes. Finite Field and Their App. 47, 183–202 (2017)
Kasami, T.: A Gilbert-Varshamov bound for quasi cyclic codes of rate 1/2. IEEE Trans. Inf. Theory 20, 679 (1974)
Ling, S., Solé, P.: On the algebraic structures of quasi-cyclic codes I: finite fields. IEEE Trans. Inf. Theory 47(7), 2751–2760 (2001)
Ling, S., Solé, P.: On the algebraic structures of quasi-cyclic codes II: chain rings. Des. Codes. Crypt. 30, 113–130 (2003)
Misoczki, R., Tillich, J.P., Sendrier, N., Baretto, P.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes, Proceedings of 2013 IEEE ISIT 2069–2073 (2013)
Roman, S.: Advanced Linear Algebra. Springer, Berlin (2008)
Séguin, G.E.: The algebraic structure of codes invariant under a permutation. In: Chouinard JY., Fortier P., Gulliver T.A. (Eds) Information Theory and Applications II. CWIT 1995. Lecture Notes in Computer Science, vol 1133 pp. 1–18 (1995)
Siap, I., Kulhan, N.: The structure of generalized quasi-cyclic codes. Appl. Math. E-Notes 5, 24–30 (2005)
Acknowledgements
This research is funded by Hibah P3MI ITB 2018.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by See Keong Lee.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Muchtadi-Alamsyah, I., Irwansyah & Barra, A. Generalized Quasi-Cyclic Codes with Arbitrary Block Lengths. Bull. Malays. Math. Sci. Soc. 45, 1383–1407 (2022). https://doi.org/10.1007/s40840-022-01251-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40840-022-01251-x