Search

The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo $r$. [ABSTRACT FROM AUTHOR]

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

Boolean functions with high algebraic immunity are important cryptographic primitives in some stream ciphers. In this paper, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity. Via these general constructions, infinite families of minimal binary linear codes of dimension $m$ and length less than or equal to $m(m+1)/2$ are obtained. Besides, a lower bound on the minimum distance of the proposed minimal linear codes is established. Conjectures and open problems are also presented. The results of this paper show that Boolean functions with high algebraic immunity have nice applications in several fields additionally to symmetric cryptography, such as coding theory and secret sharing schemes. [ABSTRACT FROM AUTHOR]

The binary quadratic-residue codes and the punctured Reed-Muller codes ${\mathcal {R}}_{2}((m-1)/2, m))$ are two families of binary cyclic codes with parameters $[n, (n+1)/2, d \geq \sqrt {n}]$. These two families of binary cyclic codes are interesting partly due to the fact that their minimum distances have a square-root bound. The objective of this paper is to construct two families of binary cyclic codes of length $2^{m}-1$ and dimension near $2^{m-1}$ with good minimum distances. When $m \geq 3$ is odd, the codes become a family of duadic codes with parameters $[2^{m}-1, 2^{m-1}, d]$ , where $d \geq 2^{(m-1)/2}+1$ if $m \equiv 3 \pmod {4}$ and $d \geq 2^{(m-1)/2}+3$ if $m \equiv 1 \pmod {4}$. The two families of binary cyclic codes contain some optimal binary cyclic codes. [ABSTRACT FROM AUTHOR]

$\mathbb {Z}_{2^{s}}$ -additive codes are subgroups of $\mathbb {Z}^{n}_{2^{s}}$ , and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{2^{s}}$ -linear code is a binary code (not necessarily linear) which is the Gray map image of a $\mathbb {Z}_{2^{s}}$ -additive code. We consider $\mathbb {Z}_{2^{s}}$ -additive simplex codes of type $\alpha $ and $\beta $ , which are a generalization over $\mathbb {Z}_{2^{s}}$ of the binary simplex codes. These codes are related to the $\mathbb {Z}_{2^{s}}$ -additive Hadamard codes. In this paper, we use this relationship to find a linear subcode of the corresponding $\mathbb {Z}_{2^{s}}$ -linear codes, called kernel, and a representation of these codes as cosets of this kernel. In particular, this also gives the linearity of these codes. Similarly, $\mathbb {Z}_{2^{s}}$ -additive MacDonald codes are defined for $s>2$ , and equivalent results are obtained. [ABSTRACT FROM AUTHOR]

In this paper, we determine all dihedral subgroups in $PGL_{2}(\mathbb {F}_{q})$ , where $q=2^{l}$ and $l$ is a positive integer; and construct binary expurgated and extended Goppa codes with dihedral automorphism groups. Moreover, it is easy to obtain binary quasi-cyclic expurgated or extended Goppa codes. [ABSTRACT FROM AUTHOR]

In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code’s length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders. [ABSTRACT FROM AUTHOR]

Non-overlapping codes are a set of codewords in $\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$ , where $\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q > 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes. [ABSTRACT FROM AUTHOR]

The family of Goppa codes is one of the most interesting subclasses of linear codes. As the McEliece cryptosystem often chooses a random Goppa code as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evaluation of the security of such a cryptosystem. In this paper we present a new approach to give an upper bound on the number of inequivalent extended irreducible binary Goppa codes. To be more specific, let $n>3$ be an odd prime number and $q=2^{n}$ ; let $r\geq 3$ be a positive integer satisfying $\gcd (r,n)=1$ and $\gcd \big (r,q(q^{2}-1)\big)=1$. We obtain an upper bound for the number of inequivalent extended irreducible binary Goppa codes of length $q+1$ and degree $r$. [ABSTRACT FROM AUTHOR]

Linear codes over $\mathbb {Z}_{p^{s}}$ of length $n$ are subgroups of $\mathbb {Z}_{p^{s}}^{n}$. These codes are also called $\mathbb {Z}_{p^{s}}$ -additive codes and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{p^{s}}$ -linear code is a code over $\mathbb {Z}_{p}$ , not necessarily linear, which is the generalized Gray map image of a $\mathbb {Z}_{p^{s}}$ -additive code. In 2015, a systematic encoding was found for $\mathbb {Z}_{4}$ -linear codes. Moreover, an alternative permutation decoding method, which is suitable for any binary code (not necessarily linear) with a systematic encoding, was established. In this paper, we generalize these results by presenting a systematic encoding for any $\mathbb {Z}_{p^{s}}$ -linear code with $s\geq 2$ and $p$ prime. We also describe a permutation decoding method for any systematic code over $\mathbb {Z}_{p}$ , not necessarily linear, and show some examples of how to use this systematic encoding in this decoding method. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by ${t}$ -criss-cross deletions defined as any combination of ${t_{\mathrm {r}}}$ row and ${t_{\mathrm {c}}}$ column deletions such that ${t_{\mathrm {r}}}+ {t_{\mathrm {c}}}= {t}$ for a given $t$. We show an equivalence between correcting ${t}$ -criss-cross deletions and ${t}$ -criss-cross insertions and show that a code correcting ${t}$ -criss-cross insertions/deletions has redundancy at least ${t} n + {t}\log n - \log ({t}!)$. Then, we present an existential construction of a ${t}$ -criss-cross insertion/deletion correcting code with redundancy bounded from above by ${t} n + \mathcal {O}({t}^{2} \log ^{2} n)$. The main ingredients of the presented code construction are systematic binary ${t}$ -deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient. [ABSTRACT FROM AUTHOR]

In this paper, we mainly study quaternary linear codes and their binary subfield codes. First we obtain a general explicit relationship between quaternary linear codes and their binary subfield codes in terms of generator matrices and defining sets. Second, we construct quaternary linear codes via simplicial complexes and determine the weight distributions of these codes. Third, the weight distributions of the binary subfield codes of these quaternary codes are also computed by employing the general characterization. Furthermore, we present two infinite families of optimal linear codes with respect to the Griesmer Bound, and a class of binary almost optimal codes with respect to the Sphere Packing Bound. We also need to emphasize that we obtain at least 9 new quaternary linear codes. [ABSTRACT FROM AUTHOR]

Reed-Muller codes are error-correcting codes used in many areas related to coding theory, such as electrical engineering and computer science. The binary $r^{th}$ -order Reed-Muller code $RM(r,n)$ can be viewed as the set of all $n$ -variable Boolean functions of algebraic degree at most $r$. Despite the intense work on these codes, many problems are known to be hard (notably, determining their covering radius) and remain open to this day. Fourteen years ago, Carlet and Mesnager improved in [IEEE Transactions on Information Theory, “Improving the Upper Bounds on the Covering Radii of Binary Reed-Muller Codes”, 53(1), 2007] the upper bound on the covering radius of the Reed-Muller code of order 2, and they deduced improved upper bounds on the covering radii of the Reed-Muller codes of higher orders. Until 2021, these upper bounds remained the best ones in the literature. The Reed-Muller code $RM(n-3,n)$ , which corresponds to the dual of the Reed-Muller code $RM(2,n)$ , has attracted much attention. One of the main reasons is that it is precisely the code that has been considered to get the upper bounds derived by Carlet and Mesnager. Those upper bounds have been obtained thanks to the characterization of the codewords of the Reed-Muller code, whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ due to Kasami, Tokura, and Azumi. Despite their impressive work in the seventieth, a more refined study and profound description of those codewords of ${RM}({n-3},{n})$ whose Hamming weight equals 16, and especially 18, seem necessary, as it could help us significantly in improving the covering radius of Reed-Muller codes. In this paper, we push further the known results on the Reed-Muller codes by focusing on the Reed-Muller code ${RM}({n-3},{n})$. We provide a classification of the codewords of weights 16 and 18 of the Reed-Muller code $RM(n-3,n)$. Our algebraic descriptions allow us to count the number of such codewords and to enumerate all of them explicitly. [ABSTRACT FROM AUTHOR]

Diameter perfect codes form a natural generalization for perfect codes. They are based on the code-anticode bound which generalizes the sphere-packing bound. The code-anticode bound was proved by Delsarte for distance-regular graphs and it holds for some other metrics too. In this paper we prove the bound for non-binary constant-weight codes with the Hamming metric and characterize the diameter perfect codes and the maximum size anticodes for these codes. We distinguish between six families of non-binary diameter constant-weight codes and four families of maximum size non-binary constant-weight anticodes. Each one of these families of diameter perfect codes raises some different questions. We consider some of these questions and leave lot of ground for further research. Finally, as a consequence, some $t$ -intersecting families related to the well-known Erdös-Ko-Rado theorem, are constructed. [ABSTRACT FROM AUTHOR]

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed as accessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (called syndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064. [ABSTRACT FROM AUTHOR]

Let $n (>3)$ be a prime number and ${\mathbb {F}}_{2^{n}}$ a finite field of $2^{n}$ elements. Let $L ={\mathbb {F}}_{2^{n}}\cup \{\infty \}$ be the support set and $g(x)$ an irreducible polynomial of degree 6 over ${\mathbb {F}}_{2^{n}}$. In this paper, we obtain an upper bound on the number of extended irreducible binary Goppa codes $\Gamma (L, g)$ of degree 6 and length $2^{n}+1$. [ABSTRACT FROM AUTHOR]

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]