Search

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. In addition, it is shown that this property extends to Poltyrev’s random-coding exponent for a random ensemble of lattices. [ABSTRACT FROM PUBLISHER]

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed–Solomon (GRS) codes is proved to be co-NP-complete by Guruswami and Vardy. For the extended Reed–Solomon codes RSq( \mathbb {F}q,k) , a conjecture was made to classify deep holes by Cheng and Murray. Since then efforts have been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for GRS codes RSp (D,k) , where $p$ is a prime, |D| > k \geqslant ({p-1})/{2} . Our techniques are built on the idea of deep hole trees, and several results concerning the Erdös–Heilbronn conjecture. [ABSTRACT FROM PUBLISHER]

A q -ary code of length n , size M , and minimum distance d code. An (n,q^{k},n-k+1)_{q} code is called a maximum distance separable (MDS) code. In this paper, some MDS codes over small alphabets are classified. It is shown that every (k+d-1,q^{k},d)_{q} code with k\geq 3 , d \geq 3 , is equivalent to a linear code with the same parameters. This implies that the (6,5^4,3)5 code and the (n,7^{n-2},3)7 MDS codes for n\in \6,7,8\ are unique. The classification of one-error-correcting 8-ary MDS codes is also finished; there are 14, 8, 4, and 4 equivalence classes of (n,8^n-2,3)8 codes for $n=6,7,8$ , and 9, respectively. One of the equivalence classes of perfect (9,8^{7},3)_{8} codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction. [ABSTRACT FROM PUBLISHER]

Recently, symbol-pair codes are proposed to protect against pair errors in symbol-pair read channels. One main task in symbol-pair coding theory is to design codes with large minimum pair distance. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense they attain maximal minimum pair distance. In this paper, based on constacyclic codes, we construct some new MDS symbol-pair codes with minimum pair-distance five and six. Compared with classical $q$ -ary MDS codes, the constructed MDS symbol-pair codes have length up to q^{2}+q+1 . [ABSTRACT FROM PUBLISHER]

In a locally recoverable or repairable code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage nodes as possible. In this paper, we bound the minimum distance of a code in terms of its length, size, and locality. Unlike the previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence, the Simplex codes are the first example of an optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds. [ABSTRACT FROM PUBLISHER]

In this paper, a class of two-weight and three-weight linear codes over \mathrm GF(p) is constructed, and their application in secret sharing is investigated. Some of the linear codes obtained are optimal in the sense that they meet certain bounds on linear codes. These codes have applications also in authentication codes, association schemes, and strongly regular graphs, in addition to their applications in consumer electronics, communication and data storage systems. [ABSTRACT FROM PUBLISHER]

Polar codes are constructed based on kernels with polarizing properties. The performance of a polar code is characterized asymptotically in terms of the exponent of its kernel. The pioneering work of Arıkan on polar codes is based on a linear kernel of dimension two and exponent 0.5. In this paper, constructions of linear and nonlinear binary kernels of dimensions up to 16 are presented. The kernels are obtained using computer search or by shortening longer kernels obtained by computer search and a computer program is used to determine their exponents. It is proved that the constructed kernels have maximum exponents except in the case of nonlinear kernels of dimension 12 where it is demonstrated that the maximum exponent either equals that of the presented construction or assumes another specified value. The results show that the minimum dimension for which there exists a linear kernel with exponent greater than 0.5, i.e., exceeds the exponent of the linear kernel proposed by Arıkan, is 15, while this minimum dimension is 14 for nonlinear kernels. Furthermore, it is shown that there is a linear kernel with maximum exponent up to dimension 11. For dimensions 13, 14, 15, and 16, there are nonlinear kernels with exponents larger than any of that of a linear kernel. The kernels of these dimensions that have maximum exponent, although nonlinear over \textrm GF(2) , are \mathbb Z4 -linear or \mathbb Z2\mathbb Z4 -linear. [ABSTRACT FROM PUBLISHER]

We consider the coded cooperative data exchange problem for general graphs, both undirected and directed. In this problem, given a graph $G=(V,E)$ representing clients in a broadcast network, each of which initially hold a (not necessarily disjoint) set of information packets; one wishes to design a communication scheme in which eventually all clients will hold all the packets of the network. Communication is performed in rounds, where in each round a single client broadcasts a single (possibly encoded) information packet to its neighbors in G$ . The objective is to design a broadcast scheme that satisfies all clients with the minimum number of broadcast rounds. The coded cooperative data exchange problem has seen significant research over the last few years; mostly when the graph G$ is the complete broadcast graph in which each client is adjacent to all other clients in the network, but also on general topologies, both in the fractional and integral setting. In this paper, we focus on the integral setting in general topologies G$ , both undirected and directed. For undirected graphs, we tie the coded cooperative data exchange problem on G is intractable (i.e., NP-hard). We then turn to study efficient data exchange schemes for undirected topologies yielding a number of communication rounds comparable with our intractability result. Last, we tie the coded cooperative data exchange problem for directed topologies to the directed Steiner tree problem, yielding efficient data exchange approximation schemes. Our communication schemes do not involve encoding, and in such yield bounds on the coding advantage in the setting at hand. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a class of exponential sums from some half quadratic binomials. The exponential sums are proven to be eleven-valued with maximal magnitude (1/2(q-\sqrt q)) except for the trivial value $q$ . As applications, first, we investigate the autocorrelation and cross-correlation distribution among the sequences in a sequence family. Second, we determine the weight distributions of several classes of linear codes. Some of the dual codes have minimum distance four, which are optimal with respect to the Hamming bound. Our results extend the result by Choi et al. and show that some correlation values in it do not occur. [ABSTRACT FROM PUBLISHER]

Quantum maximum-distance-separable (MDS) codes form an important family of quantum codes. In this paper, using Hermitian construction and classical constacyclic codes, we construct six classes of quantum MDS codes. Two of these six classes of quantum MDS codes have larger minimum distance than the ones available in the literature. Most of these quantum MDS codes are new in the sense that their parameters are not covered by the codes available in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we extend two earlier works further in two directions and compute the weight distribution of these cyclic codes under more relaxed conditions. It is interesting to note that many cyclic codes in the family are optimal and have only a few non-zero weights. Besides using similar ideas, we carry out some subtle manipulation of certain exponential sums. [ABSTRACT FROM AUTHOR]

In this paper, we address the computational hardness of optimally decoding a quantum stabilizer code. Much like classical linear codes, errors are detected by measuring certain check operators which yield an error syndrome, and the decoding problem consists of determining the most likely recovery given the syndrome. The corresponding classical problem is known to be NP-complete, and are appropriate a similar decoding problem for quantum codes is also known to be NP-complete. However, this decoding strategy is not optimal in the quantum setting as it does not consider error degeneracy, which causes distinct errors to have the same effect on the code. Here, we show that optimal decoding of stabilizer codes (previously known to be NP-hard) is in fact computationally much harder than optimal decoding of classical linear codes, it is #P-complete. [ABSTRACT FROM AUTHOR]

The set of all subspaces of \mathbb Fq^{n} is denoted by \mathbb Pq(n) . The subspace distance dS(X,Y) = \dim (X)+ \dim (Y)\, - 2\dim (X \cap Y) defined on \mathbb Pq(n) turns it into a natural coding space for error correction in random network coding. A subset of \mathbb P\vphantom {RRRq}(n) is called a code and the subspaces that belong to the code are called codewords. Motivated by classical coding theory, a linear coding structure can be imposed on a subset of \mathbb Pq(n) . Braun et al. conjectured that the largest cardinality of a linear code, that contains \mathbb Fq^{n} , is 2^n . In this paper, we prove this conjecture and characterize the maximal linear codes that contain \mathbb Fq^{n} . [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]

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]

Since discovery of Goppa geometric codes, people have been asking the question: are there different constructions of block codes from algebraic curves that give the same parameters as Goppa geometric codes. Despite of great effort by researchers, no such constructions have been found so far. Although in literature, there are many constructions of block code from algebraic curves, most of them are quite different from the one by Goppa in nature and thus they have different parameters. Some of these constructions have the same parameters as Goppa geometric codes, however it was proved that these are essentially the same codes defined by Goppa. In this paper, we solve this question for the case where the characteristic of the ground field is 2, namely, we present a different construction of block codes from algebraic curves that give the same parameters as Goppa geometric codes for the characteristic 2 case. [ABSTRACT FROM PUBLISHER]

By extending the notion of minimum rank distance, this paper introduces two new relative code parameters of a linear code \mathcal C1 of length n over a field extension \mathbb {F}_{q^{m}} and its subcode \mathcal {C}_{2} \subsetneqq \mathcal {C} _{1}$ . One is called the relative dimension/intersection profile (RDIP), and the other is called the relative generalized rank weight (RGRW). We clarify their basic properties and the relation between the RGRW and the minimum rank distance. As applications of the RDIP and the RGRW, the security performance and the error correction capability of secure network coding, guaranteed independently of the underlying network code, are analyzed and clarified. We propose a construction of secure network coding scheme, and analyze its security performance and error correction capability as an example of applications of the RDIP and the RGRW. Silva and Kschischang showed the existence of a secure network coding in which no part of the secret message is revealed to the adversary even if any \dim \mathcal {C} _{1} -1 links are wiretapped, which is guaranteed over any underlying network code. However, the explicit construction of such a scheme remained an open problem. Our new construction is just one instance of secure network coding that solves this open problem. [ABSTRACT FROM PUBLISHER]

Feldman et al. [11] asked whether the performance of the linear programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for low-density parity-check codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the binary symmetric channel under certain conditions on the base Tanner graph. First, we show that if the Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense. For each constant $\delta >0$ , there is a constant $k>0$ such that the threshold of the LP decoder containing all redundant checks of degree at most $k$ improves by at most $\delta $ upon adding to the LP all redundant checks of degree larger than $k$ . We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [9] and its recent improvement by Viderman [24], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs. [ABSTRACT FROM PUBLISHER]

Cyclic codes are an interesting class of linear codes due to their efficient encoding and decoding algorithms. Bose-Ray-Chaudhuri-Hocquenghem (BCH) codes form a subclass of cyclic codes and are very important in both theory and practice as they have good error-correcting capability and are widely used in communication systems, storage devices, and consumer electronics. However, the dimension and minimum distance of BCH codes are not known in general. The objective of this paper is to determine the Bose and minimum distances of a class of narrow-sense primitive BCH codes. [ABSTRACT FROM AUTHOR]

In this paper, we study the asymptotic performance of Abelian group codes for the channel coding problem for arbitrary discrete (finite alphabet) memoryless channels as well as the lossy source coding problem for arbitrary discrete (finite alphabet) memoryless sources. For the channel coding problem, we find the capacity characterized in a single-letter information-theoretic form. This simplifies to the symmetric capacity of the channel when the underlying group is a field. For the source coding problem, we derive the achievable rate-distortion function that is characterized in a single-letter information-theoretic form. When the underlying group is a field, it simplifies to the symmetric rate-distortion function. We give several illustrative examples. Due to the nonsymmetric nature of the sources and channels considered, our analysis uses a synergy of information-theoretic and group-theoretic tools. [ABSTRACT FROM AUTHOR]

Tail-biting trellises are important graphical representations of codes, which can be simpler to decode than conventional trellises. While conventional trellises are well understood, the general theory of (tail-biting) trellises is still under development. In this paper we first develop a new algebraic framework for a systematic analysis of linear trellises which enables us to address open foundational questions. In particular, we present a useful and powerful characterization of linear trellis isomorphy. We also obtain a new proof of the linear factorization theorem of Koetter/Vardy, and point out unnoticed problems for the group case. Next, we apply our framework to: 1) describe all the factorizations of linear trellises; 2) determine and classify all the minimal linear trellises for a given linear code; and 3) prove that nonmergeable, one-to-one, linear trellises are determined by the edge-label sequences of certain closed paths. We also provide new insight into mergeability and state how results on reduced linear trellises can be extended to nonreduced ones. Our classification results are relevant to iterative/linear programming decoding, as we show that minimal linear trellises can yield different pseudocodewords even if they have the same graph structure. [ABSTRACT FROM AUTHOR]

Quantum error correction is an important building block for reliable quantum information processing. A challenging hurdle in the theory of quantum error correction is that it is significantly more difficult to design error-correcting codes with desirable properties for quantum information processing than for traditional digital communications and computation. A typical obstacle to constructing a variety of strong quantum error-correcting codes is the complicated restrictions imposed on the structure of a code. Recently, promising solutions to this problem have been proposed in quantum information science, where in principle any binary linear code can be turned into a quantum error-correcting code by assuming a small number of reliable quantum bits. This paper studies how best to take advantage of these latest ideas to construct desirable quantum error-correcting codes of very high information rate. Our methods exploit structured high-rate low-density parity-check codes available in the classical domain and provide quantum analogues that inherit their characteristic low decoding complexity and high error correction performance even at moderate code lengths. Our approach to designing high-rate quantum error-correcting codes also allows for making direct use of other major syndrome decoding methods for linear codes, making it possible to deal with a situation where promising quantum analogues of low-density parity-check codes are difficult to find. [ABSTRACT FROM AUTHOR]

A Z2Z4 -linear Hadamard code of length \alpha +2\beta =2^t is a binary Hadamard code, which is the Gray map image of a Z2Z4 -additive code with \alpha binary coordinates and \beta quaternary coordinates. It is known that there are exactly \lfloor \frac t-12 \rfloor and \lfloor \frac t2 \rfloor nonequivalent Z2Z4 -linear Hadamard codes of length 2^t , with $\alpha =0$ and \alpha \not =0$ , respectively, for all t\geq 3$ . In this paper, it is shown that each \alpha =0$ is equivalent to a Z2Z4 -linear Hadamard code with \alpha \not =0 nonequivalent Z2Z4 -linear Hadamard codes of length 2^t . Moreover, the order of the monomial automorphism group for the Z2Z4 -additive Hadamard codes and the permutation automorphism group of the corresponding Z2Z4 -linear Hadamard codes are given. [ABSTRACT FROM AUTHOR]

Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert–Varshamov bound. In particular, we show that, for any fixed finite field \mathbb Fq , error fraction \delta \in (0,1-1/q) satisfying 1-H_{q}(\delta )\le 1/2 , and small \epsilon >0 , with high probability a random Euclidean self-orthogonal code over 1-Hq(\delta )-\epsilon is (\delta ,O(1/\epsilon )) -list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert–Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert–Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result. [ABSTRACT FROM AUTHOR]

Function computation over Gaussian networks with orthogonal components is studied for arbitrarily correlated discrete memoryless sources. Two classes of functions are considered: 1) the arithmetic sum function and 2) the type function. The arithmetic sum function in this paper is defined as a set of multiple weighted arithmetic sums, which includes averaging of the sources and estimating each of the sources as special cases. The type or frequency histogram function counts the number of occurrences of each argument, which yields various fundamental statistics, such as mean, variance, maximum, minimum, median, and so on. The proposed computation coding first abstracts Gaussian networks into the corresponding modulo sum multiple-access channels via nested lattice codes and linear network coding and then computes the desired function using linear Slepian–Wolf source coding. For orthogonal Gaussian networks (with no broadcast and multiple-access components), the computation capacity is characterized for a class of networks. For Gaussian networks with multiple-access components (but no broadcast), an approximate computation capacity is characterized for a class of networks. [ABSTRACT FROM AUTHOR]

Quantum synchronizable error-correcting codes are special quantum error-correcting codes that are designed to correct both the effect of quantum noise on qubits and misalignment in block synchronization. It is known that, in principle, such a code can be constructed through a combination of a classical linear code and its subcode if the two are both cyclic and dual-containing. However, finding such classical codes that lead to promising quantum synchronizable error-correcting codes is not a trivial task. In fact, although there are two families of classical codes that are proved to produce quantum synchronizable codes with good minimum distances and highest possible tolerance against misalignment, their code lengths have been restricted to primes and Mersenne numbers. In this paper, examining the incidence vectors of projective spaces over the finite fields of characteristic 2, we give quantum synchronizable codes from cyclic codes whose lengths are not primes or Mersenne numbers. These projective geometric codes achieve good performance in quantum error correction and possess the best possible ability to recover synchronization, thereby enriching the variety of good quantum synchronizable codes. We also extend the current knowledge of cyclic codes in classical coding theory by explicitly giving generator polynomials of the finite geometric codes and completely characterizing the minimum weight nonzero codewords. In addition to the codes based on projective spaces, we carry out a similar analysis on the well-known cyclic codes from Euclidean spaces that are known to be majority logic decodable and determine their exact minimum distances. [ABSTRACT FROM PUBLISHER]

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on \(q\) levels. Each cell is initially in level 0 and can only increase its level. A \(t\) -write WOM code is a coding scheme, which allows one to store \(t\) messages to the WOM such that on consecutive writes every cell’s level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the \(t\) writes and number of memory cells, is bounded by \(\log (t+1)\) . Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates. [ABSTRACT FROM PUBLISHER]

This paper develops a fundamental theory of realizations of linear and group codes on general graphs using elementary group theory, including basic group duality theory. Principal new and extended results include: normal realization duality; analysis of systems-theoretic properties of fragments of realizations and their connections; minimal \(\Leftrightarrow \) trim and proper theorem for cycle-free codes; results showing that all constraint codes except interface nodes may be assumed to be trim and proper, and that the interesting part of a cyclic realization is its 2-core; notions of observability and controllability for fragments, and related tests; and relations between state-trimness and controllability, and dual state-trimness and observability. [ABSTRACT FROM AUTHOR]

Linear encoders with good joint spectra are suitable candidates for optimal lossless joint source-channel coding (JSCC), where the joint spectrum is a variant of the input–output complete weight distribution and is considered good if it is close to the average joint spectrum of all linear encoders (of the same coding rate). In spite of their existence, little is known on how to construct such encoders in practice. This paper is devoted to their construction. In particular, two families of linear encoders are presented and proved to have good joint spectra. The first family is derived from Gabidulin codes, a class of maximum-rank-distance codes. The second family is constructed using a serial concatenation of an encoder of a low-density parity-check code (as outer encoder) with a low-density generator matrix encoder (as inner encoder). In addition, criteria for good linear encoders are defined for three coding applications: 1) lossless source coding; 2) channel coding; and 3) lossless JSCC. In the framework of the code-spectrum approach, these three scenarios correspond to the problems of constructing linear encoders with good kernel spectra, good image spectra, and good joint spectra, respectively. Good joint spectra imply both good kernel spectra and good image spectra, and for every linear encoder having a good kernel (respectively, image) spectrum, it is proved that there exists a linear encoder not only with the same kernel (respectively, image) but also with a good joint spectrum. Thus, a good joint spectrum is the most important feature of a linear encoder. [ABSTRACT FROM AUTHOR]

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, whereas other (heavy) parity symbols may depend on all data symbols. Such codes have been studied recently in the context of erasure coding for data storage, where the local parities facilitate fast recovery of any single symbol when it is erased, whereas the heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally recoverable, if it corrects all erasure patterns, which are information theoretically correctable given the prescribed dependence relations between data symbols and parity symbols. In this paper, we present explicit families of maximally recoverable codes with locality. We also initiate the general study of the tradeoff between maximal recoverability and alphabet size. [ABSTRACT FROM AUTHOR]

We introduce complementary information set codes of higher order. A binary linear code of length \(tk\) and dimension \(k\) is called a complementary information set code of order \(t\) ( \(t\) -CIS code for short) if it has \(t\) pairwise disjoint information sets. The duals of such codes permit to reduce the cost of masking cryptographic algorithms against side-channel attacks. As in the case of codes for error correction, given the length and the dimension of a \(t\) -CIS code, we look for the highest possible minimum distance. In this paper, this new class of codes is investigated. The existence of good long CIS codes of order 3 is derived by a counting argument. General constructions based on cyclic and quasi-cyclic codes and on the building up construction are given. A formula similar to a mass formula is given. A classification of 3-CIS codes of length \(\le 12\) is given. Nonlinear codes better than linear codes are derived by taking binary images of \( {\mathbb Z}_{4}\) -codes. A general algorithm based on Edmonds’ basis packing algorithm from matroid theory is developed with the following property: given a binary linear code of rate \(1/t\) , it either provides \(t\) disjoint information sets or proves that the code is not \(t\) -CIS. Using this algorithm, all optimal or best known \([tk, k]\) codes, where \(t=3, 4, {\dots }, 256\) and \(1 \le k \le \lfloor 256/t \rfloor \) are shown to be \(t\) -CIS for all such \(k\) and \(t\) , except for \(t=3\) with \(k=44\) and \(t=4\) with \(k=37\) . [ABSTRACT FROM AUTHOR]

Recently, there has been intensive research on the weight distributions of cyclic codes. In this paper, we compute the weight distributions of three classes of cyclic codes with Niho exponents. More specifically, we obtain two classes of binary three-weight and four-weight cyclic codes and a class of nonbinary four-weight cyclic codes. The weight distributions follow from the determination of value distributions of certain exponential sums. Several examples are presented to show that some of our codes are optimal and some have the best known parameters. [ABSTRACT FROM AUTHOR]

Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems due to their efficient encoding and decoding algorithms. In this paper, let \(\Bbb F_r\) be a finite field with \(r=q^m\) . Suppose that \(g_1, g_2 \in \Bbb F_r^*\) are not conjugates over \(\Bbb F_q\) , \( \operatorname {ord}(g_1)=n_1\) , \( \operatorname {ord}(g_2)=n_2\) , \(d=\gcd (n_1, n_2)\) , and \(n={n_1n_2}/ d\) . Let \(\Bbb F_q(g_1)=\Bbb F_{q^{m_1}}, \Bbb F_q(g_2)=\Bbb F_{q^{m_2}}\) , and \(\text{T}_i\) denote the trace function from \(\Bbb F_{q^{m_i}}\) to \(\Bbb F_q\) for \(i=1, 2\) . We define a cyclic code \(\mathcal C_{(q, m, n_1, n_2)}=\{c(a,b) : a \in \Bbb F_{q^{m_1}}, b \in \Bbb F_{q^{m_2}}\},\) where \(c(a,b)=(\text {T}_1(ag_1^0)+\text {T}_2(bg_2^0), \text {T}_1(ag_1^1)+\text {T}_2(bg_2^1), \ldots , \text {T}_1(ag_1^{n-1})+\text {T}_2(bg_2^{n-1})).\) We mainly use Gauss periods to present the weight distribution of the cyclic code \(\mathcal C_{(q, m, n_1, n_2)}\) . As applications, we determine the weight distribution of cyclic code \(\mathcal C_{(q, m,q^{m_1}-1,q^{m_2}-1)}\) with \(\gcd (m_1,m_2)=1\) ; in particular, it is a three-weight cyclic code if \(\gcd (q-1,m_1-m_2)=1\) . We also explicitly determine the weight distributions of some classes of cyclic codes including several classes of four-weight cyclic codes. [ABSTRACT FROM AUTHOR]