Search

We study the classical expander codes, introduced by Sipser and Spielman [M. Sipser and D. A. Spielman, 1996]. Given any constants 0 < ��, �� < 1/2, and an arbitrary bipartite graph with N vertices on the left, M < N vertices on the right, and left degree D such that any left subset S of size at most �� N has at least (1-��)|S|D neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly {�� N}/{2 ��}. This is strictly better than the best known previous result of 2(1-��) �� N [Madhu Sudan, 2000; Viderman, 2013] whenever �� < 1/2, and improves the previous result significantly when �� is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever �� < 1/4. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests., LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 43:1-43:3

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code ${\mathcal {C}}_{0}$ of length $d$ , and a $d$ -regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the code ${\mathcal {C}}= {\mathcal {C}}(G, {\mathcal {C}}_{0})$ of length $nd$ from approximately $\delta \delta _{r} nd$ erasures in time $n \cdot \mathrm {poly} (d2^{r} / \delta)$ , where $\delta $ and $\delta _{r}$ are the relative distance and the $r$ ’th generalized relative distance of ${\mathcal {C}}_{0}$ , respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately $\delta ^{2}~nd$ . To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation , 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on $r$ and $\delta $ ; then we show how to improve the dependence of the running time on these parameters.

Research on the expander code shows that for a regular low-density parity-check (LDPC) code, the Tanner graph’s spectrum determines its properties, such as the minimum distance and the size of stopping sets. In this study, we demonstrate theoretically and experimentally that the performance of irregular LDPC codes is related to the graph spectrum. Our observations may provide an efficient metric to search for good irregular LDPC codes.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes, group divisible codes, and multiply constant-weight codes. We achieve this via an application of the theory of decomposition of edge-colored digraphs. MOE (Min. of Education, S’pore) Published version

In this paper, we construct new families of classical convolutional codes (CCC's) and new families of quantum convolutional codes (QCC's). The CCC's are derived from (block) algebraic geometry (AG) codes. Furthermore, new families of CCC's are constructed by applying the techniques of puncturing, extending, expanding, and by the direct product code construction applied to AG codes. In addition, utilizing the new CCC's constructed here, we obtain new families of QCC's. The parameters of these new codes are good. More precisely, in the classical case, a family of almost near maximum distance separable (MDS) codes is presented; in the quantum case, we construct a family of MDS (optimal) quantum convolutional codes.

Combinatorics, Coding and Security Group (CCSG) A binary nonlinear code can be represented as a union of cosets of a binary linear subcode. In this paper, the complexity of some algorithms to obtain this representation is analyzed. Moreover, some properties and constructions of new codes from given ones in terms of this representation are described. Algorithms to compute the minimum distance of binary nonlinear codes, based on known algorithms for linear codes, are also established, along with an algorithm to decode such codes. All results are written in such a way that they can be easily transformed into algorithms, and the performance of these algorithms is evaluated.

We give an algebraic structure for a large family of binary quasi-cyclic codes. We construct a family of commutative rings and a canonical Gray map such that cyclic codes over this family of rings produce quasi-cyclic codes of arbitrary index in the Hamming space via the Gray map. We use the Gray map to produce optimal linear codes that are quasi-cyclic.

The threshold theorem is a seminal result in the field of quantum computing asserting that arbitrarily long quantum computations can be performed on a faulty quantum computer provided that the noise level is below some constant threshold. This remarkable result comes at the price of increasing the number of qubits (quantum bits) by a large factor that scales polylogarithmically with the size of the quantum computation we wish to realize. Minimizing the space overhead for fault-tolerant quantum computation is a pressing challenge that is crucial to benefit from the computational potential of quantum devices. In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation. We show that the polylogarithmic factor in the standard threshold theorem is in fact not needed and that there is a fault-tolerant construction that uses a number of qubits that is only a constant factor more than the number of qubits of the ideal computation. This result was conjectured by Gottesman who suggested to replace the concatenated codes from the standard threshold theorem by quantum error-correcting codes with a constant encoding rate. The main challenge was then to find an appropriate family of quantum codes together with an efficient classical decoding algorithm working even with a noisy syndrome. The efficiency constraint is crucial here: bear in mind that qubits are inherently noisy and that faults keep accumulating during the decoding process. The role of the decoder is therefore to keep the number of errors under control during the whole computation. On a technical level, our main contribution is the analysis of the SMALL-SET-FLIP decoding algorithm applied to the family of quantum expander codes . We show that it can be parallelized to run in constant time while correcting sufficiently many errors on both the qubits and the syndrome to keep the error under control. These tools can be seen as a quantum generalization of the BIT-FLIP algorithm applied to the (classical) expander codes of Sipser and Spielman.

In this paper we define and study a family of codes which are coming close to MRD codes. Thus we call them AMRD codes (almost MRD). An AMRD code is a code with rank defect equal to 1. These codes can be viewed as q-analogs of classical AMDS codes as considered in [3] , [7] , [9] . AMRD codes whose duals are AMRD as well are called dually AMRD. These codes have important symmetry properties. For instance, the number of codewords of minimum rank in C and C ⊥ are equal if the size of the matrices divides the dimension of C [4] . Necessary and sufficient conditions are given for codes to be dually AMRD and we give a construction of such codes of minimal dimension. We also construct self-dual AMRD codes. Furthermore, we show that dually AMRD codes coincide with codes of rank defect one and maximum 2-generalized weight if the size of the matrices divides the dimension. The results may be seen as q-analogs of results established in classical coding theory [7] , [9] .

Linear complementary-dual (LCD for short) codes are linear codes that intersect with their duals trivially. LCD codes have been used in certain communication systems. It is recently found that LCD codes can be applied in cryptography. This application of LCD codes renewed the interest in the construction of LCD codes having a large minimum distance. MDS codes are optimal in the sense that the minimum distance cannot be improved for given length and code size. Constructing LCD MDS codes is thus of significance in theory and practice. Recently, Jin (\cite{Jin}, IEEE Trans. Inf. Theory, 2016) constructed several classes of LCD MDS codes through generalized Reed-Solomon codes. In this paper, a different approach is proposed to obtain new LCD MDS codes from generalized Reed-Solomon codes. Consequently, new code constructions are provided and certain previously known results in \cite{Jin} are extended.

We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have been useful recently in constructing efficiently list-decodable codes, as well as explicit constructions of matrices for compressive sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most 1/2; in contrast, our codes can have rate $1 - \epsilon$ for any $\epsilon > 0$. We can plug our high-rate codes into a construction of Meir (2014) to obtain linear-time list recoverable codes of arbitrary rates, which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code. While list-recovery is interesting on its own, our primary motivation is applications to list-decoding. A slight strengthening of our result would implies linear-time and optimally list-decodable codes for all rates, and our work is a step in the direction of solving this important problem.

We present constructions of codes obtained from maximal orders over number fields. Particular cases include codes from algebraic number fields by Lenstra and Guruswami, codes from units of the ring of integers of number fields, and codes from both additive and multiplicative structures of maximal orders in central simple division algebras. The parameters of interest are the code rate and the minimum Hamming distance. An asymptotic study reveals several families of asymptotically good codes. Accepted version

Recently, linear codes constructed from defining sets have been investigated extensively and they have many applications. For an odd prime $p$ , we determine the complete weight enumerator and weight enumerator of a class of $p$ -ary linear codes by choosing a proper defining set. The results show that they have at most two weights and are suitable for applications in secret sharing schemes.

In this paper, a new method to construct parity check matrix of QC-LDPC codes based on shortening RS codes for wireless sensor networks (WSNs) is proposed. The proposed method constructs a basic matrix based on shortening RS codes with two information symbols, then expands the basic matrix optimally utilizing cyclic permutation matrix, so as to obtain the check matrix of quasi-cyclic regular LDPC codes in which the girth is 8 at least, and constructed LDPC codes have good minimum distances. Especially, the basic matrix and its expansion are both fully structured, so it is convenient for hardware implementation. The simulation results show that the QC-LDPC codes constructed by the proposed method have good BER performance and convenient for the hardware design and implementation. Moreover, the simulation results show that WSNs using the constructed QC-LDPC codes have good energy efficiency.

Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length n ≥ 3 , the semiautomorphisms are exactly the bijections that preserve the set of r -balls for each radius r . Switching of optimal codes of size at most 7 and of codes attaining K ( 8 , 1 ) = 32 is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes.

We consider computational problems concerning algebras over finite fields. In particular, we propose an algorithm for finding a small generating set for the multiplicative group of F q [ x ] / F , where q = p n is a prime power and F ∈ F q [ x ] is a polynomial not necessarily irreducible. Based on this result, a new set of expander graphs can be explicitly constructed. In addition, we present algorithms for basis construction and decomposition of a given element with respect to the basis.

Generalizing the quasi-cyclic codes of index 1 1 3 introduced by Fan et al., we study a more general class of quasi-cyclic codes of fractional index generated by pairs of polynomials. The parity check polynomial and encoder of these codes are obtained. The asymptotic behaviours of the rates and relative distances of this class of codes are studied by using a probabilistic method. We prove that, for any positive real number δ such that the asymptotic GV-bound at k + l 2 δ is greater than 1 2 , the relative distance of the code is convergent to δ , while the rate is convergent to 1 k + l . As a result, quasi-cyclic codes of fractional index are asymptotically good.

We construct an infinite family of two-Lee-weight and three-Lee-weight codes over the non-chain ring F p + u F p + v F p + u v F p , where u 2 = 0 , v 2 = 0 , u v = v u . These codes are defined as trace codes. They have the algebraic structure of abelian codes. Their Lee weight distribution is computed by using Gauss sums. With a linear Gray map, we obtain a class of abelian three-weight codes and two-weight codes over F p . In particular, the two-weight codes we describe are shown to be optimal by application of the Griesmer bound. We also discuss their dual Lee distance. Finally, an application to secret sharing schemes is given.

Recently, Yaakobi et al. introduced codes for b-symbol read channels, where the read operation is performed as a consecutive sequence of b2 symbols. In this paper, we establish a Singleton-type bound for b-symbol codes. Codes meeting the Singleton-type bound are called maximum distance separable (MDS) codes, and they are optimal in the sense they attain the maximal minimum b-distance. We introduce a construction method using projective geometry, and then construct several infinite families of linear MDS b-symbol codes over finite fields. The lengths of these codes have a large range. And in some sense, we completely determine the existence of linear MDS b-symbol codes over finite fields for certain parameters.

The graph approach of circular codes recently developed (Fimmel et al., 2016) allows here a detailed study of diletter circular codes over finite alphabets. A new class of circular codes is identified, strong comma-free codes. New theorems are proved with the diletter circular codes of maximal length in relation to (i) a characterisation of their graphs as acyclic tournaments; (ii) their explicit description; and (iii) the non-existence of other maximal diletter circular codes. The maximal lengths of paths in the graphs of the comma-free and strong comma-free codes are determined. Furthermore, for the first time, diletter circular codes are enumerated over finite alphabets. Biological consequences of dinucleotide circular codes are analysed with respect to their embedding in the trinucleotide circular code X identified in genes and to the periodicity modulo 2 observed in introns. An evolutionary hypothesis of circular codes is also proposed according to their combinatorial properties.

Recently some special type of mixed alphabet codes that generalize the standard codes has attracted much attention. Besides Z 2 Z 4 -additive codes, Z 2 Z 2 [ u ] -linear codes are introduced as a new member of such families. In this paper, we are interested in a new family of such mixed alphabet codes, i.e., codes over Z 2 Z 2 [ u 3 ] where Z 2 [ u 3 ] = { 0 , 1 , u , 1 + u , u 2 , 1 + u 2 , u + u 2 , 1 + u + u 2 } is an 8-element ring with u 3 = 0 . We study and determine the algebraic structures of linear and cyclic codes defined over this family. First, we introduce Z 2 Z 2 [ u 3 ] -linear codes and give standard forms of generator and parity-check matrices and later we present generators of both cyclic codes and their duals over Z 2 Z 2 [ u 3 ] . Further, we present some examples of optimal binary codes which are obtained through Gray images of Z 2 Z 2 [ u 3 ] -cyclic codes.

The objective of this letter is to construct two classes of cyclic codes over $F_{p}$ with few weights, where $p$ is an odd prime. The weight distributions of these codes are determined. Some of the cyclic codes are optimal, which refers to meeting a certain bound on linear codes. The number of nonzero weights of these codes is not more than five and these codes can be employed to obtain secret sharing schemes.

Binary linear codes with good parameters have wide applications in data storage, communications, and information security. Inspired by the idea proposed by Ding recently and based on the Boolean functions with bivariate polynomial representation in even number of variables, we construct a class of two-weight binary linear codes with length $(2^{k}-1)e$ , dimension $2k$ , and minimum distance $2^{k-1}(e-1)$ , where $k\ge 2$ and $e$ is an arbitrary integer with $2^{k}-k . The variable $e$ provides flexible tradeoff between the code length and minimal distance. We determine the weight distributions of all the generated binary linear codes and, most notably, mathematically prove that all these codes are distance-optimal with respect to the Griesmer bound.

Linear codes with few weights have applications in secret sharing, authentication codes, association schemes, data storage systems, strongly regular graphs and some other fields. Two-weight linear codes are particularly interesting since they are closely related to finite geometry, combinatorial designs, graph theory. In this paper, we present a new approach to constructing linear codes with two or three weights from q -polynomials and study their weight distributions. As an application of two-weight linear codes, we obtain three families of strongly regular graphs. Some of the presented strongly regular graphs are new.

This letter presents a new method for constructing the multi-rate non-binary quasi-cyclic low-density parity-check codes by expurgating a high-rate mother code. A matrix-theoretic approach is applied to design the parity-check matrices of the proposed codes. The resulting codes possess a quasi-cyclic structure, which is desirable for hardware implementations of the encoder and decoder. The codes can also be encoded directly with parity-check matrices due to the block dual-diagonal structure. Simulation results show that the codes can achieve good performance within a wide range of code rates both in the waterfall region and in the error-floor region.

Binary constant weight codes have important applications in various topics and have been studied for many years. Optimal or near-optimal binary constant weight codes of small lengths have been determined. In this paper we propose an improvement of the Ericson–Zinoviev construction of binary constant weight codes from q-ary codes. By applying this improvement to Reed–Solomon codes, some new or optimal binary constant weight codes are presented. In particular new binary constant weight codes A ( 64 , 10 , 8 ) ≥ 4112 and A ( 64 , 12 , 8 ) ≥ 522 are constructed. We also give explicitly constructed binary constant weight codes which improve the Gilbert and the Graham–Sloane lower bounds asymptotically in a small range of parameters. Some new binary constant weight codes constructed from algebraic-geometric codes by applying our this improvement are also presented.

Recently, Karadeniz and Yildiz introduced an efficient method to search for self-dual codes. It is called lifting method and can be applied to some alphabets. In this work, by considering R 2 -lifts of binary self-dual codes of length 16 new extremal binary self-dual codes of lengths 64 are constructed as Gray images. More precisely, we construct 15 new codes of length 64. Moreover, 10 new codes of length 66 were obtained by applying a building-up construction to the binary codes. Codes with these weight enumerators are constructed for the first time in the literature. The results are tabulated.

In this work we introduce a novel approach to find reversible codes over different alphabets, using so-called coterm polynomials and a module-construction. We obtain many optimal reversible codes with these constructions. In an attempt to apply the constructions to the DNA, we identify k-bases of DNA with elements in the ring R 2 k = F 2 [ u ] / ( u 2 k − 1 ) , and by using a form of coterm polynomials, we are able to solve the reversibility and complement problems in DNA codes over this ring. With a freedom on the choice of k we are able to embed any DNA code in a suitable ring, giving an algebraic structure to the DNA codes. We are also able to find reversible and reversible-complement codes that are not necessarily linear cyclic codes.

In this paper, we propose a novel extending algorithm to design rate compatible (RC) QC-IRA-d codes through Tanner Graph extension. The structure of QC-IRA-d codes provides high efficiency and low complexity for graph extension. Thus, in the proposed method, there are three features: (1) close relation between the extended parts and original parity check matrix; (2) larger length of introduced cycles; (3) balanced check node degree. All of them guarantee good performance of the designed RC family codes. Simulation results show that the graph extension method outperforms existed algorithms from 0.05 to 0.47 dB for different rate codes.

Recently, some attentions have been focused on a class of low-density parity-check codes from affine permutation matrices , called APM-LDPC codes, which have some advantages rather than quasi-cyclic low-density parity-check (QC-LDPC) codes in the minimum-distance, cycle distribution and error-rate performance. In this letter, first, some novel explicit constructions for exponent matrices of conventional APM-LDPC codes with girths 6, 8, and 10 are investigated, and for each given exponent matrix $E$ corresponding to an APM-LDPC code with girth $2g$ , $3\leq g\leq 5$ , a lower bound $Q=Q(E,g)$ is obtained, such that APM-LDPC codes with exponent matrix $E$ have girth at least $2g$ , for each (prime) APM size $m\geq Q$ . Then, regarding to reduce the lower bound, an improved bound $IQ$ is obtained, which is significantly better than some lower bounds reported for QC-LDPC codes with explicit constructions. Simulation results show that the constructed APM-LDPC codes outperform QC-LDPC codes with the same girth.

The use of error-correcting codes is a common strategy to protect memories from errors. Single-error correction, double-error detection linear block codes have been traditionally utilized. However, there are applications where multiple errors are frequent and more complex codes are needed. Orthogonal Latin square codes are one type of codes with multiple-error-correction capability. They are of interest for memory protection because they can be decoded with low complexity and delay. This paper presents a modification to orthogonal Latin square codes that reduces the number of parity check bits to be stored in memory therefore lowering the memory overhead needed to implement the codes. The proposed codes can also be decoded with low delay and complexity. This paper also presents an evaluation of the encoder and decoder implementations for various word sizes and compares them with the standard orthogonal Latin square implementations. The results show that they are similar in terms of circuit area and introduce only a small penalty in delay.

Explicit construction of linear codes with best possible parameters is one of the major problems in coding theory. Among all alphabets of interest, the binary alphabet is the most important one. In this work we use a comprehensive search strategy to find new binary linear codes in the well-known and intensively studied class of quasi-cyclic (QC) codes. We also introduce a generalization of an augmentation algorithm to obtain further new codes from those QC codes. Also applying the standard methods of obtaining new codes from existing codes, such as puncturing, extending and shortening, we have found a total of 62 new binary linear codes.

In this paper we present a class of integer codes that are suitable for use in optical networks without optical amplifiers. The presented codes can correct all single errors and all burst asymmetric errors within a b-bit byte. Compared to other classes of integer codes, these codes have two advantages: first, they are less demanding in terms of memory needs, and second, they have higher code rates. Thanks to these features, the proposed codes are faster to decode, and thus simpler to implement.

We construct a family of nonlinear q-ary codes obtained from the corresponding families of modified complex Butson–Hadamard matrices. Parameters of the codes are quite close to the Plotkin bound and in a number of cases attain this bound. Furthermore, these codes admit rather simple encoding and decoding procedures.

A novel technique for construction of minimum storage regenerating (MSR) codes is presented. Based on this technique, three explicit constructions of MSR codes are given. The first two constructions provide access-optimal MSR codes, with two and three parities, respectively, which attain the sub-packetization bound for access-optimal codes. The third construction provides longer MSR codes with three parities (i.e., codes with larger number of systematic nodes). This improvement is achieved at the expense of the access-optimality and the field size. In addition to a minimum storage in a node, all three constructions allow the entire data to be recovered from a minimal number of storage nodes. That is, given storage $\ell $ in each node, the entire stored data can be recovered from any $2\log _{2} \ell $ for two parity nodes, and either $3\log _{3}\ell $ or $4\log _{3}\ell $ for three parities. Second, in the first two constructions, a helper node accesses the minimum number of its symbols for repair of a failed node (access-optimality). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, in the first construction a field size of at least $6\log _{3} \ell +1$ (or $3\log _{3} \ell +1$ for fields with characteristic 2) is sufficient, and in the second construction the field size is larger, yet linear in $\log _{3}\ell $ . Both constructions with three parities provide a significant improvement over previous works due to either decreased field size or lower subpacketization.

We present a new design approach to construct generalized concatenated codes (GCCs) based on polar codes (PCs). It is already known that PCs can be considered as a special class of the GCCs with polar outer and inner codes. We show how density evolution (DE) can be used to develop a channel-specific method to design outer codes of length $L$ under maximum-likelihood (ML) decoding. Once a bank of outer codes of length $L$ and different rates have been designed, we develop a rate-allocation algorithm to allocate rates to the outer codes of the GCC with the goal of minimizing the overall block error rate for a given overall rate of $K/N$ . To maintain the low complexity of the SC decoder, we only design very short outer codes $(L\le\text{8})$ . We show that, at this outer code length, it is possible to design GCC-PCs that can result in up to 0.5-dB coding gain while reducing decoding complexity.

We design a non-commutative version of the Peterson–Gorenstein–Zierler decoding algorithm for a class of codes that we call skew RS codes. These codes are left ideals of a quotient of a skew polynomial ring, which endow them of a sort of non-commutative cyclic structure. Since we work over an arbitrary field, our techniques may be applied both to linear block codes and convolutional codes. In particular, our decoding algorithm applies for block codes beyond the classical cyclic case.

Linear codes with few weights have applications in secret sharing, authentication codes, association schemes, date storage systems, strongly regular graphs and some other fields. In this paper, we present several classes of binary linear codes with two or three weights and study their weight distributions. Two classes of strongly regular graphs are constructed from binary linear codes with two weights. Numerical results show that some of the obtained codes are either optimal or near optimal with respect to certain bounds on linear codes.

Linear codes with few weights have applications in data storage systems, secret sharing schemes, and authentication codes. In this paper, a class of p-ary two-weight linear codes is constructed using a generic construction developed by Ding et al. recently, where p is a prime. Their length and weight distribution are closed-form expressions of Kloosterman sums over prime finite fields, and are completely determined when p = 2 and p = 3. The dual of this class of linear codes is also studied and is shown to be optimal or almost optimal in the binary case.

It has been known for a long time that t-designs can be employed to construct both linear and nonlinear codes and that the codewords of a fixed weight in a code may hold a t-design. While a lot of progress in the direction of constructing codes from t-designs has been made, only a small amount of work on the construction of t-designs from codes has been done. The objective of this paper is to construct infinite families of 2-designs and 3-designs from a type of binary linear codes with five weights. The total number of 2-designs and 3-designs obtained in this paper are exponential in any odd m and the block size of the designs varies in a huge range.

A conflict-avoiding code is used to guarantee that each transmitting user can send at least one packet successfully within a fixed period of time, provided that at most k out of M potential users are active simultaneously in a multiple-access collision channel. The number of codewords in a conflict-avoiding code determines the number M of potential users that can be supported in a system. That is why codes of the maximum cardinality for given parameters (optimal codes) are of interest. In this paper we determine the values of the maximum cardinality and classify up to multiplier equivalence optimal conflict-avoiding codes for 6 and 7 active users and given small lengths.

Both Maximum Distance Separable and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining the existence of $q$ -ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where $q$ is even. This paper focuses on the case where $q$ is odd. We construct a few classes of new MDS self-dual codes through generalized Reed–Solomon codes. More precisely, we show that for any given even length $n$ , we have a $q$ -ary MDS code as long as $q\equiv 1\bmod {4}$ and $q$ is sufficiently large (say $q\ge 4^{n}\times n^{2})$ . Furthermore, we prove that there exists a $q$ -ary MDS self-dual code of length $n$ if $q=r^{2}$ and $n$ satisfies one of the three conditions: 1) $n\le r$ and $n$ is even; 2) $q$ is odd and $n-1$ is an odd divisor of $q-1$ ; and 3) $r\equiv 3\mod {4}$ and $n=2tr$ for any $t\le (r-1)/2$ .

We construct an infinite family of two-Lee-weight codes over the ring F2+uF2+vF2+uvF2. These codes are defined as trace codes and have the algebraic structure of abelian codes. Their Lee weight distribution is computed by using character sums. Then, taking Gray mapping, we obtain an infinite family of abelian binary two-weight codes which are shown to be optimal by application of the Griesmer bound. Moreover, an application to secret sharing schemes is given.

We propose a new ensemble of binary low-density parity-check codes with paritycheck matrices based on repetition codes and permutation matrices. The proposed class of codes is a subensemble of quasi-cyclic codes. For the constructed ensemble, we obtain minimum distance estimates. We present simulation results for the proposed code constructions under the (Sum-Product) iterative decoding algorithm for transmission over an additive white Gaussian noise channel using binary phase-shift keying.

Codes over the chain ring are obtained by writing special matrices. Gray images of these codes are binary codes. It is shown that first repeat code, second repeat code, even code and odd code are either equivalent or equal to these codes. The definitions of direct sum and direct product of these codes were given. Moreover dual codes were classed. Self dual codes and self orthogonal codes were established.