Search

An $[{n}, {k}, {n}-{k}+1]$ linear code is called an MDS code. An $[{n}, {k}, {n}-{k}]$ linear code is said to be almost maximum distance separable (almost MDS or AMDS for short). A code is said to be near maximum distance separable (near MDS or NMDS for short) if the code and its dual code both are almost maximum distance separable. The first near MDS code was the [11, 6, 5] ternary Golay code discovered in 1949 by Golay. This ternary code holds 4-designs, and its extended code holds a Steiner system ${S}(5, 6, 12)$ with the largest strength known. In the past 70 years, sporadic near MDS codes holding t-designs were discovered and a lot of infinite families of near MDS codes over finite fields were constructed. However, the question as to whether there is an infinite family of near MDS codes holding an infinite family of t-designs for $ {t}\geq 2$ remains open for 70 years. This paper settles this long-standing problem by presenting an infinite family of near MDS codes over $ {GF}(3^{ {s}})$ holding an infinite family of 3-designs and an infinite family of near MDS codes over $ {GF}(2^{2 {s}})$ holding an infinite family of 2-designs. The subfield subcodes of these two families of codes are also studied, and are shown to be dimension-optimal or distance-optimal. [ABSTRACT FROM AUTHOR]

Let $p$ be a prime, $s$ be a positive integer, and let $b$ be an integer satisfying $2 \leq b < p^{s}$. In this paper, we obtain $b$ -symbol distances of all repeated-root constacyclic codes of length $p^{s}$ over finite fields. Using this result, we determine $b$ -symbol distances of all repeated-root constacyclic codes of length $p^{s}$ over finite commutative chain rings. We also list all MDS $b$ -symbol repeated-root constacyclic codes of length $p^{s}$ over finite fields, and all MDS $b$ -symbol repeated-root constacyclic codes of length $p^{s}$ over finite commutative chain rings in general. [ABSTRACT FROM AUTHOR]

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros. [ABSTRACT FROM PUBLISHER]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH , the corresponding minimum pair distance is at least dH+3 . In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance dH , the minimum pair distance is at least dH +\left \lceil{ {dH/{2}}}\right \rceil . We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, $b \geqslant 3$ , of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting. [ABSTRACT FROM AUTHOR]

A ${\mathbb {Z}}_{2}{\mathbb {Z}}_{4}$ -additive code ${\mathcal{ C}}\subseteq {\mathbb {Z}}_{2}^\alpha \times {\mathbb {Z}}_{4}^\beta $ is called cyclic if the set of coordinates can be partitioned into two subsets, the set of ${\mathbb {Z}}_{2}$ coordinates and the set of ${\mathbb {Z}}_{4}$ coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. Let $\Phi ({\mathcal{ C}})$ be the binary Gray map image of ${\mathcal{ C}}$. We study the rank and the dimension of the kernel of a ${\mathbb {Z}}_{2} {\mathbb {Z}}_{4} $ -additive cyclic code ${\mathcal{ C}}$ , that is, the dimensions of the binary linear codes $\langle \Phi ({\mathcal{ C}}) \rangle $ and $\ker (\Phi ({\mathcal{ C}}))$. We give upper and lower bounds for these parameters. It is known that the codes $\langle \Phi ({\mathcal{ C}}) \rangle $ and $\ker (\Phi ({\mathcal{ C}}))$ are binary images of ${\mathbb {Z}}_{2} {\mathbb {Z}}_{4}$ -additive codes that we denote by ${\mathcal{ R}}({\mathcal{ C}})$ and ${\mathcal{ K}}({\mathcal{ C}})$ , respectively. Moreover, we show that ${\mathcal{ R}}({\mathcal{ C}})$ and ${\mathcal{ K}}({\mathcal{ C}})$ are also cyclic and determine the generator polynomials of these codes in terms of the generator polynomials of the code ${\mathcal{ C}}$. [ABSTRACT FROM AUTHOR]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

The projective special linear group ${\mathrm {PSL}}_{2}(n)$ is 2-transitive for all primes $n$ and 3-homogeneous for $n \equiv 3 \pmod {4}$ on the set $\{0,1, \ldots, n-1, \infty \}$. It is known that the extended odd-like quadratic residue codes are invariant under ${\mathrm {PSL}}_{2}(n)$. Hence, the extended quadratic residue codes hold an infinite family of 2-designs for primes $n \equiv 1 \pmod {4}$ , an infinite family of 3-designs for primes $n \equiv 3 \pmod {4}$. To construct more $t$ -designs with $t \in \{2, 3\}$ , one would search for other extended cyclic codes over finite fields that are invariant under the action of ${\mathrm {PSL}}_{2}(n)$. The objective of this paper is to prove that the extended quadratic residue binary codes are the only nontrivial extended binary cyclic codes that are invariant under ${\mathrm {PSL}}_{2}(n)$. [ABSTRACT FROM AUTHOR]

In this paper, we construct a new family of quantum synchronizable codes from repeated-root cyclic codes of lengths p^s and lp^s over \mathbb Fq , where $s\geq 1~and l\geq 2$ are integers, and $p\geq 3$ is the odd characteristic. Within some loose limitations, these synchronizable codes can possess the best possible capability in synchronization recovery, and therefore, enriches the variety of good quantum synchronizable codes. Furthermore, by using known techniques in classical coding theory which convert the computation of the minimum distance of a repeated-root cyclic code to that of a shorter simple-root cyclic code, we prove that the repeated-root cyclic codes of lengths p^s and lp^s are in general better than narrow-sense BCH codes of close lengths in terms of minimum distances, and thereby enable the obtained synchronizable codes to correct more Pauli errors. [ABSTRACT FROM PUBLISHER]

Linear network coding over finite fields is a well-studied problem. We consider the more general setting of linear coding for directed acyclic networks with finite commutative ring alphabets. Our results imply that for scalar linear network coding over commutative rings, fields can always be used when the alphabet size is flexible, but other rings may be needed when the alphabet size is fixed. We prove that if a network has a scalar linear solution over some finite commutative ring, then the (unique) smallest such commutative ring is a field. We also show that fixed-size commutative rings are quasi-ordered, such that all the scalar linearly solvable networks over any given ring are also scalar linearly solvable over any higher-ordered ring. We study commutative rings that are maximal with respect to this quasi-order, as they may be considered the best commutative rings of a given size. We prove that a commutative ring is maximal if and only if some network is scalar linearly solvable over the ring, but not over any other commutative ring of the same size. Furthermore, we show that maximal commutative rings are direct products of certain fields specified by the integer partitions of the prime factor multiplicities of the ring’s size. Finally, we prove that there is a unique maximal commutative ring of size $m$ if and only if each prime factor of m$ has multiplicity in {1, 2, 3, 4, 6}. As consequences, 1) every finite field is such a maximal ring and 2) for each prime p$ , some network is scalar linearly solvable over a commutative ring of size but not over the field of the same size if and only if k \not \in \{1,2,3,4,6\} . [ABSTRACT FROM PUBLISHER]

Symbol-pair codes introduced by Cassuto and Blaum (2010) are designed to protect against pair errors in symbol-pair read channels. The higher the minimum pair distance, the more pair errors the code can correct. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense that pair distance cannot be improved for given length and code size. The contribution of this paper is twofold. First, we present three lower bounds for the minimum pair distance of constacyclic codes, the first two of which generalize the previously known results due to Cassuto and Blaum (2011) and Kai et al. (2015). The third one exhibits a lower bound for the minimum pair distance of repeated-root cyclic codes. Second, we obtain new MDS symbol-pair codes with minimum pair distance seven and eight through repeated-root cyclic codes. [ABSTRACT FROM AUTHOR]

Cyclic codes with a few weights are very useful in the design of frequency hopping sequences and the development of secret sharing schemes. In this paper, we mainly use Gauss sums to represent the Hamming weights of cyclic codes whose duals have two zeroes. A lower bound of the minimum Hamming distance is determined. In some cases, we give the Hamming weight distributions of the cyclic codes. In particular, we obtain a class of three-weight optimal cyclic codes achieving the Griesmer bound, which generalizes a Vega’s result, and several classes of cyclic codes with a few weights, which solve an open problem proposed by Vega. [ABSTRACT FROM AUTHOR]

The generalized Hamming weights dr(C) of a linear code C are a natural generalization of the minimum Hamming distance d(C)[=d_{1}(C)] and have become an important research object in coding theory since Wei’s originary work in 1991. In this paper, two general formulas on dr(C) for irreducible cyclic codes are presented using Gauss sums and the weight hierarchy \{d_{1}(C), d_{2}(C), \ldots , d_{k}(C)\}~(k=\dim C)$ is completely determined for several cases. [ABSTRACT FROM AUTHOR]

We propose three private information retrieval (PIR) protocols for distributed storage systems (DSSs), where data is stored using an arbitrary linear code. The first two protocols, named Protocol 1 and Protocol 2, achieve privacy for the scenario with noncolluding nodes. Protocol 1 requires a file size that is exponential in the number of files in the system, while Protocol 2 requires a file size that is independent of the number of files and is hence simpler. We prove that, for certain linear codes, Protocol 1 achieves the maximum distance separable (MDS) PIR capacity, i.e., the maximum PIR rate (the ratio of the amount of retrieved stored data per unit of downloaded data) for a DSS that uses an MDS code to store any given (finite and infinite) number of files, and Protocol 2 achieves the asymptotic MDS-PIR capacity (with infinitely large number of files in the DSS). In particular, we provide a necessary and a sufficient condition for a code to achieve the MDS-PIR capacity with Protocols 1 and 2 and prove that cyclic codes, Reed–Muller (RM) codes, and a class of distance-optimal local reconstruction codes achieve both the finite MDS-PIR capacity (i.e., with any given number of files) and the asymptotic MDS-PIR capacity with Protocols 1 and 2, respectively. Furthermore, we present a third protocol, Protocol 3, for the scenario with multiple colluding nodes, which can be seen as an improvement of a protocol recently introduced by Freij-Hollanti et al.. Similar to the noncolluding case, we provide a necessary and a sufficient condition to achieve the maximum possible PIR rate of Protocol 3. Moreover, we provide a particular class of codes that is suitable for this protocol and show that RM codes achieve the maximum possible PIR rate for the protocol. For all three protocols, we present an algorithm to optimize their PIR rates. [ABSTRACT FROM AUTHOR]

A ${\mathbb {Z}}_{2}{\mathbb {Z}}_{4}$ -additive code ${\mathcal{ C}}\subseteq {\mathbb {Z}}_{2}^\alpha \times {\mathbb {Z}}_{4}^\beta $ is called cyclic if the set of coordinates can be partitioned into two subsets, the set of ${\mathbb {Z}}_{2}$ and the set of ${\mathbb {Z}}_{4}$ coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. We study the binary images of $\mathbb {Z}_{2} \mathbb {Z}_{4} $ -additive cyclic codes. We determine all ${\mathbb {Z}_{2}\mathbb {Z}_{4}}$ -additive cyclic codes with odd $\beta $ whose Gray images are linear binary codes. In this case, it is shown that such binary codes are permutation equivalent (by the Nechaev permutation) to $\mathbb {Z}_{2}$ -double cyclic codes. Finally, the generator polynomials of these binary codes are given. [ABSTRACT FROM AUTHOR]

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and synchronization between communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized, and cyclic codes. [ABSTRACT FROM AUTHOR]

We present algorithms for initializing a convolutional network coding (CNC) scheme in networks that may contain cycles. An initialization process for finding global encoding kernels (GEK) is needed if the network is unknown or if local encoding kernels are chosen randomly. During the initialization process every source node transmits basis vectors and every sink node gets the impulse response of the network. The impulse response is then used to find the GEK, which are needed for a decoding algorithm and to find the set of all achievable rates. We present two initialization algorithms that find the GEK and one algorithm that finds achievable rates from the GEK. In the first initialization algorithm it is assumed that we can perform a reset operation on the network at some fixed times, while the second algorithm does not operate under this assumption. Unlike acyclic networks, for which it is sufficient to transmit basis vectors one after another, the initialization of cyclic networks is more involved, as test symbols from different times interfere with each other and the impulse response is of infinite duration. Our algorithms use only a finite number of the initial values of the impulse response to find the full GEK. This is possible because a CNC scheme can be described by a state space representation and, using the Cayley-Hamilton theorem, it is possible to find its full impulse response from its initial values. [ABSTRACT FROM AUTHOR]

For almost-cyclostationary processes, sufficient conditions are derived, such that estimates of the second-order cyclic probabilistic functions with estimated cycle frequencies are mean-square consistent and asymptotically complex normal. Cyclic (conjugate) autocorrelation functions and cyclic (conjugate) spectra are considered. Under the derived conditions, asymptotically, as the data-record length approaches infinity, the estimates of cyclic statistics with estimated cycle frequencies have the same complex normal distribution as the case of exactly known cycle frequencies. The results are applied to the detection of a moving cyclostationary source in the presence of strong Doppler effect and for low values of SNR. [ABSTRACT FROM PUBLISHER]

A \mathbb Z2\mathbb Z4 -additive code \mathcal C\subseteq \mathbb Z2^\alpha \times \mathbb Z4^\beta is called cyclic if the set of coordinates can be partitioned into two subsets, the set of \mathbb Z2 and the set of \mathbb Z4 coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. These codes can be identified as submodules of the \mathbb Z4[x] -module \mathbb Z2[x]/(x^\alpha -1)\times \mathbb Z4[x]/(x^\beta -1) . The parameters of a \mathbb Z2\mathbb Z4 -additive cyclic code are stated in terms of the degrees of the generator polynomials of the code. The generator polynomials of the dual code of a \mathbb Z2\mathbb Z4 -additive cyclic code are determined in terms of the generator polynomials of the code \mathcal C . [ABSTRACT FROM PUBLISHER]

We give a construction of quantum LDPC codes of dimension $\Theta (\log N)$ and distance $\Theta (N/\log N)$ as the code length $N\to \infty $. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance $\Omega (N^{1-\alpha /2}/\log N)$ and dimension $\Omega (N^\alpha \log N)$ , where $0 \le \alpha < 1$. We also introduce and study a new operation called lifted product, which naturally generalizes the product operations for quantum codes and chain complexes. Moreover, as a simple byproduct of our results on quantum codes, we obtain a new result on classical codes. We show that for any fixed $R < 1$ there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least $R$ with, in some sense, optimal circulant size $\Omega (N/\log N)$ as the code length $N\to \infty $. [ABSTRACT FROM AUTHOR]

We study the codes of the title by the CRT method, that decomposes such codes into constituent codes, which are shorter codes over larger alphabets. Criteria on these constituent codes for self-duality and linear complementary duality of the decomposed codes are derived. The special class of the one-generator codes is given a polynomial representation and exactly enumerated. In particular, we present some illustrative examples of binary optimal linear codes with respect to the Griesmer bound derived from the $\mathbb {Z}_{2} \mathbb {Z}_{4}$ -additive quasi-cyclic codes. [ABSTRACT FROM AUTHOR]

A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length $2^{2m}-1$ with relative decimation $d=2^{m+2}-3$ , where $m$ is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation $f(x)=x^{d}$ over a finite field of order $2^{2m}$ and at most five distinct nonzero weights in the cyclic code of length $2^{2m}-1$ with two primitive nonzeros $\alpha $ and $\alpha ^{d}$. The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when $m$ is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values. [ABSTRACT FROM AUTHOR]

In this work, cyclic-skew-cyclic codes and sum-rank BCH codes are introduced. Cyclic-skew-cyclic codes are characterized as left ideals of a suitable non-commutative finite ring, constructed using skew polynomials on top of polynomials (or vice versa). Single generators of such left ideals are found, and they are used to construct generator matrices of the corresponding codes. The notion of defining set is introduced, using pairs of roots of skew polynomials on top of poynomials. A lower bound (called sum-rank BCH bound) on the minimum sum-rank distance is given for cyclic-skew-cyclic codes whose defining set contains certain consecutive pairs. Sum-rank BCH codes, with prescribed minimum sum-rank distance, are then defined as the largest cyclic-skew-cyclic codes whose defining set contains such consecutive pairs. The defining set of a sum-rank BCH code is described, and a lower bound on its dimension is obtained. Thanks to it, tables are provided showing that sum-rank BCH codes beat previously known codes for the sum-rank metric for binary $2 \times 2 $ matrices (i.e., codes whose codewords are lists of $2 \times 2 $ binary matrices, for a wide range of list lengths that correspond to the code length). Finally, a decoder for sum-rank BCH codes up to half their prescribed distance is obtained. [ABSTRACT FROM AUTHOR]

We investigate the largest number of nonzero weights of quasi-cyclic codes. In particular, we focus on the function $\Gamma _{Q}(n,\ell,k,q)$ , that is defined to be the largest number of nonzero weights a quasi-cyclic code of index $\gcd (\ell,n)$ , length $n$ and dimension $k$ over $\mathbb F_{q}$ can have, and connect it to similar functions related to linear and cyclic codes. We provide several upper and lower bounds on this function, using different techniques and studying its asymptotic behavior. Moreover, we determine the smallest index for which a $q$ -ary Reed-Muller code is quasi-cyclic, a result of independent interest. [ABSTRACT FROM AUTHOR]

The non-linear binary Kerdock codes are known to be Gray images of certain extended cyclic codes of length $N = 2^{m}$ over $\mathbb {Z}_{4}$. We show that exponentiating these $\mathbb {Z}_{4}$ -valued codewords by $i \triangleq \sqrt {-1}$ produces stabilizer states, that are quantum states obtained using only Clifford unitaries. These states are also the common eigenvectors of commuting Hermitian matrices forming maximal commutative subgroups (MCS) of the Pauli group. We use this quantum description to simplify the derivation of the classical weight distribution of Kerdock codes. Next, we organize the stabilizer states to form $N+1$ mutually unbiased bases and prove that automorphisms of the Kerdock code permute their corresponding MCS, thereby forming a subgroup of the Clifford group. When represented as symplectic matrices, this subgroup is isomorphic to the projective special linear group PSL($2,N$). We show that this automorphism group acts transitively on the Pauli matrices, which implies that the ensemble is Pauli mixing and hence forms a unitary 2-design. The Kerdock design described here was originally discovered by Cleve et al. (2016), but the connection to classical codes is new which simplifies its description and translation to circuits significantly. Sampling from the design is straightforward, the translation to circuits uses only Clifford gates, and the process does not require ancillary qubits. Finally, we also develop algorithms for optimizing the synthesis of unitary 2-designs on encoded qubits, i.e., to construct logical unitary 2-designs. Software implementations are available at https://github.com/nrenga/symplectic-arxiv18a , which we use to provide empirical gate complexities for up to 16 qubits. [ABSTRACT FROM AUTHOR]

A novel scheme is presented for encoding and iterative soft-decision decoding of cyclic codes of prime lengths. The encoding of a cyclic code of a prime length is performed on a collection of codewords which are mapped through Galois Fourier transform into a codeword in a low-density parity-check code with a binary parity-check matrix for transmission. Using this matrix, binary iterative soft-decision decoding algorithm is applied to jointly decode a collection of codewords from the cyclic code. The joint-decoding allows for information sharing among the received vectors corresponding to the codewords in the collection during the iterative decoding process. For decoding Reed-Solomon and BCH codes of prime lengths, the proposed decoding scheme not only requires much lower decoding complexity than other soft-decision decoding algorithms for these codes, but also yields superior performance. The proposed decoding scheme can also achieve a joint-decoding gain over the maximum likelihood decoding of individual codewords. The decoding scheme is also applied to quadratic residue codes. [ABSTRACT FROM AUTHOR]

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length $n$ , minimum distance $d$ with $(d+1) \log _{4}\,\,n +O(1)$ redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth’s balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes and codes for DNA computing. [ABSTRACT FROM AUTHOR]

The dual of the Kasami code of length $q^{2}-1$ , with $q$ a power of 2, is constructed by concatenating a cyclic MDS code of length $q+1$ over $F_{q}$ with a Simplex code of length $q-1$. This yields a new derivation of the weight distribution of the Kasami code, a new description of its coset graph, and a new proof that the Kasami code is completely regular. The automorphism groups of the Kasami code and the related $q$ -ary MDS code are determined. New cyclic completely regular codes over finite fields a power of 2, generalized Kasami codes, are constructed; they have coset graphs isomorphic to that of the Kasami codes. Another wide class of completely regular codes, including additive codes, as well as unrestricted codes, is obtained by combining cosets of the Kasami or generalized Kasami code. [ABSTRACT FROM AUTHOR]

Upper and lower bounds on the largest number of weights in a cyclic code of given length, dimension and alphabet are given. An application to irreducible cyclic codes is considered. Sharper upper bounds are given for the special cyclic codes (called here strongly cyclic), whose nonzero codewords have period equal to the length of the code. Asymptotics are derived on the function $\Gamma (k,q)$ , that is defined as the largest number of nonzero weights a cyclic code of dimension $k$ over $\mathbb {F}_{q}$ can have, and an algorithm to compute it is sketched. The nonzero weights in some infinite families of Reed-Muller codes, either binary or $q$ -ary, as well as in the $q$ -ary Hamming code are determined, two difficult results of independent interest. [ABSTRACT FROM AUTHOR]

Families of codes, such as group codes, constacyclic, and skew cyclic codes, which were independently suggested, turn out to be special instances of the general family of crossed product codes. Under this framework, the ambient code spaces are classified here with respect to Hamming-isometry in cohomological terms. This classification is demonstrated by two families of examples. We also determine when crossed products belonging to these families are semisimple and, in particular, when they admit only trivial codes. [ABSTRACT FROM AUTHOR]

A general criterion to obtain $s$ -PD-sets of minimum size $s+1$ for partial permutation decoding, which enable correction up to $s$ errors, for systematic codes over a finite field ${ {F}}_{q}$ and ${ {Z}}_{4}$ -linear codes is provided. We show how this technique can be easily applied to linear cyclic codes over ${ {F}}_{q}$ , ${ {Z}}_{4}$ -linear codes which are the Gray map image of a quaternary linear cyclic code, and some related codes such as quasi-cyclic codes. Furthermore, specific results for some linear and nonlinear binary codes, including simplex, Kerdock, Delsarte-Goethals, and extended dualized Kerdock codes are given. Finally, applying this technique, new $s$ -PD-sets of size $s+1$ for ${ {Z}}_{4}$ -linear Hadamard codes of type $2^\gamma 4^\delta $ , for all $\delta \geq 4$ and $1< s\leq 2^\delta -3$ ; and for ${ {Z}}_{4}$ -linear simplex codes of type $4^{m}$ , for all $m\geq 2$ and $1< s\leq 2^{m+1}-3$ , are also provided. [ABSTRACT FROM AUTHOR]

We study linear complementary pairs (LCP) of codes $(C, D)$ , where both codes belong to the same algebraic code family. We especially investigate constacyclic and quasi-cyclic LCP of codes. We obtain characterizations for LCP of constacyclic codes and LCP of quasi-cyclic codes. Our result for the constacyclic complementary pairs extends the characterization of linear complementary dual (LCD) cyclic codes given by Yang and Massey. We observe that when $C$ and $D$ are complementary and constacyclic, the codes $C$ and $D^\bot $ are equivalent to each other. Hence, the security parameter $\min (d(C),d(D^\bot))$ for LCP of codes is simply determined by one of the codes in this case. The same holds for a special class of quasi-cyclic codes, namely 2D cyclic codes, but not in general for all quasi-cyclic codes, since we have examples of LCP of double circulant codes not satisfying this conclusion for the security parameter. We present examples of binary LCP of quasi-cyclic codes and obtain several codes with better parameters than known binary LCD codes. Finally, a linear programming bound is obtained for binary LCP of codes and a table of values from this bound is presented in the case $d(C)=d(D^\bot)$. This extends the linear programming bound for LCD codes. [ABSTRACT FROM AUTHOR]

We propose a framework for constructing efficient code-based encryption schemes that do not hide any structure in their public matrix. The framework is in the spirit of the schemes first proposed by Alekhnovich in 2003 and based on the difficulty of decoding random linear codes from random errors of low weight. We depart somewhat from Alekhnovich’s approach and propose an encryption scheme based on the difficulty of decoding random quasi-cyclic codes. We propose two new cryptosystems instantiated within our framework: the hamming quasi-cyclic cryptosystem (HQC), based on the hamming metric, and the rank quasi-cyclic cryptosystem (RQC), based on the rank metric. We give a security proof, which reduces the indistinguishability under chosen plaintext attack security of our systems to a decision version of the well-known problem of decoding random families of quasi-cyclic codes for the hamming and rank metrics (the respective \mathsf QCSD and \mathsf RQCSD problems). We also provide an analysis of the decryption failure probability of our scheme in the Hamming metric case: for the rank metric there is no decryption failure. Our schemes benefit from a very fast decryption algorithm together with small key sizes of only a few thousand bits. The cryptosystems are very efficient for low encryption rates and are very well suited to key exchange and authentication. Asymptotically, for \lambda the security parameter, the public key sizes are respectively in \mathcal {O}({\lambda }^{2}) for HQC and in \mathcal {O}\left({\lambda ^{\frac {4}{3}}}\right)$ for RQC. Practical parameter compares well to the systems based on ring-learning parity with noise or the recent moderate density parity check codes system. [ABSTRACT FROM PUBLISHER]

An explicit construction of an infinite family of cyclic codes is presented which, over GF(4) (resp., GF(8)), have approximately 8/9 (resp., 48/49) the redundancy of BCH codes of the same minimum distance and length. As such, the new codes are the best codes currently known in a regime where the minimum distance is fixed and the code length goes to infinity. [ABSTRACT FROM PUBLISHER]

Using a method for constructing self-dual codes having an automorphism of odd prime order, we classify up to equivalence all binary self-dual codes with an automorphism of order 11 with 6 cycles and minimum distance 12. This classification gives new [72, 36, 12] codes with weight enumerator that was previously not obtained as well as many [66, 33, 12], [68, 34, 12], and [70, 35, 12] codes with new values of the parameters in their respective weight enumerators. [ABSTRACT FROM PUBLISHER]