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]

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]

Two general constructions of linear codes with functions over finite fields have been extensively studied in the literature. The first one is given by C(ƒ) = {Tr(aƒ(x) + bx)x∈Fqm*: a, b ∈ Fqm}, where q is a prime power, Fqm* = Fqm \ {0}, Tr is the trace function from Fqm to Fq, and ƒ(x) is a function from Fqm to Fqm with ƒ(0) = 0. Almost bent functions, quadratic functions and some monomials on F2m were used in the first construction, and many families of binary linear codes with few weights were obtained in the literature. This paper studies some punctured codes of these binary codes. Several families of binary linear codes with few weights and new parameters are obtained in this paper. Several families of distance-optimal binary linear codes with new parameters are also produced in this paper. [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 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]

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]

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]

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]

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]

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]

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes. [ABSTRACT FROM AUTHOR]

Bazzi and Mitter showed that binary dihedral group codes are asymptotically good. In this paper we prove that the dihedral group codes over any finite field with strong duality property are asymptotically good. If the characteristic of the field is even, self-dual dihedral group codes are asymptotically good. If the characteristic of the field is odd, maximal self-orthogonal dihedral group codes and LCD dihedral group codes are asymptotically good. [ABSTRACT FROM AUTHOR]

The parameters of a q-ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further study on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed. [ABSTRACT FROM AUTHOR]

We introduce two notions of discrepancy between binary vectors, which are not metric functions in general but nonetheless capture the mathematical structure of the binary asymmetric channel. These lead to two new fundamental parameters of binary error-correcting codes, both of which measure the probability that the maximum likelihood decoder fails. We then derive various bounds for the cardinality and weight distribution of a binary code in terms of these new parameters, giving examples of codes meeting the bounds with equality. [ABSTRACT FROM AUTHOR]

Given a computable probability measure $P$ over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample such that none of its members are outliers of $P$. In addition, given a binary predicate $\gamma $ , the length of the smallest program that computes a complete extension of $\gamma $ is less than the size of the domain of $\gamma $ plus the amount of information that $\gamma $ has with the halting sequence. [ABSTRACT FROM AUTHOR]

We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε > 0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ = 2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2 × 2 kernel) on the BEC is μ = 3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist ℓ × ℓ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ (ℓ) that tends to the optimal value of 2 as ℓ grows. We furthermore characterize precisely how large ℓ needs to be as a function of the gap between μ (ℓ) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(n log n). [ABSTRACT FROM AUTHOR]

Consider an assignment of bits to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length $|V|$ on $G$. The storage code problem can be equivalently formulated as maximizing the probability of success in a guessing game on graphs, or constructing index codes of small rate. If $G$ contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate $> 1/2$ is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one. We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph. Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems. [ABSTRACT FROM AUTHOR]

Kim et al. (2021) gave a method to embed a given binary $[n,k]$ code $\mathcal {C}\,\,(k = 3, 4)$ into a self-orthogonal code of the shortest length which has the same dimension $k$ and minimum distance $d' \ge d(\mathcal {C})$. We extend this result by proposing a new method related to a special matrix, called the self-orthogonality matrix $SO_{k}$ , obtained by shortening a Reed-Muller code ${\mathcal R}(2,k)$. Using this approach, we can extend binary linear codes to many optimal self-orthogonal codes of dimensions 5 and 6. Furthermore, we partially disprove the conjecture (Kim et al. (2021)) by showing that if $31 \le n \le 256$ and $n\equiv 14,22,29 \pmod {31}$ , then there exist optimal $[n], [5]$ codes which are self-orthogonal. We also construct optimal self-orthogonal $[n], [6]$ codes when $41 \le n \le 256$ satisfies $n \ne 46, 54, 61$ and $n \equiv \!\!\!\!\!/~7, 14, 22, 29, 38, 45, 53, 60 \pmod {63}$. [ABSTRACT FROM AUTHOR]

We study codes with parameters of $q$ -ary shortened Hamming codes, i.e., $(n=(q^{m}-q)/(q-1), q^{n-m}, 3)_{q}$. Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such codes are optimal, generalizing it to a bound for multifold packings of radius-1 balls, with a corollary for multiple coverings. In particular, we show that the punctured Hamming code is an optimal $q$ -fold packing with minimum distance 2. Secondly, for every admissible length starting from $n=20$ , we show the existence of 4-ary codes with parameters of shortened 1-perfect codes that cannot be obtained by shortening a 1-perfect code. [ABSTRACT FROM AUTHOR]

The aim of this work is to study the structure and properties of the binary LCD codes having an automorphism of odd prime order and to present a method for their construction. [ABSTRACT FROM AUTHOR]

Additive codes have become an increasingly important topic in algebraic coding theory due to their applications in quantum error-correction and quantum computing. Linear Complementary Dual (LCD) codes play an important role for improving the security of information against certain attacks. Motivated by these facts, we define additive complementary dual codes (ACD for short) over a finite abelian group in terms of an arbitrary duality on the ambient space and examine their properties. We show that the best minimum weight of ACD codes is always greater than or equal to the best minimum weight of LCD codes of the same size and that this inequality is often strict. We give some matrix constructions for quaternary ACD codes from a given quaternary ACD code and also from a given binary self-orthogonal code. Moreover, we construct an algorithm to determine if a given quaternary additive code is an ACD code with respect to all possible symmetric dualities. We also determine the largest minimum distance of quaternary ACD codes for lengths $n \leq 10$. The obtained codes are either optimal or near optimal according to Bierbrauer et al +. (2009). [ABSTRACT FROM AUTHOR]

In this work, we present a family of vector quantization schemes vqSGD (Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic reduction in the communication cost with convergence guarantees in first-order distributed optimization. In the process we derive the following fundamental information theoretic fact: $\Theta \left({\frac {d}{R^{2}}}\right)$ bits are necessary and sufficient (up to an additive $O(\log d)$ term) to describe an unbiased estimator $\hat{\boldsymbol {g}}(\boldsymbol {g})$ for any $\boldsymbol {g}$ in the $d$ -dimensional unit sphere, under the constraint that $\| \hat{\boldsymbol {g}}(\boldsymbol {g})\|_{2}\le R$ almost surely, $R > 1$. In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a $d$ -dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require $o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using well-known families of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that vqSGD also offers automatic privacy guarantees. [ABSTRACT FROM AUTHOR]

We show that the problem of code construction for multiple access channel (MAC) resolvability can be reduced to the simpler problem of code construction for source resolvability. Specifically, we propose a MAC resolvability code construction that relies on a combination of multiple source resolvability codes, used in a black-box manner, and leverages randomness recycling implemented via distributed hashing and block-Markov coding. Since explicit source resolvability codes are known, our results also yield the first explicit coding schemes that achieve the entire MAC resolvability region for any discrete memoryless multiple-access channel with binary input alphabets. [ABSTRACT FROM AUTHOR]

This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel with parameter $p$ (${\mathrm {BDC}}_{p}$) every bit is deleted independently with probability $p$. A lower bound of $(1-p)/9$ is known on the capacity of the ${\mathrm {BDC}}_{p}$ , yet no explicit construction is known to achieve this rate. We give an explicit family of codes of rate $(1-p)/16$ , for every $p$. This improves upon the work of Guruswami and Li (2018) that gave a construction of rate $(1-p)/120$. The codes in our family have polynomial time encoding and decoding algorithms. Another channel considered in this work is the Poisson repeat channel with parameter $\lambda $ (PRC $_{\lambda }$) in which every bit is replaced with a discrete Poisson number of copies of that bit, where the number of copies has mean $\lambda $. We show that our construction works for this channel as well. As far as we know, this is the first explicit construction of an error correcting code for PRC $_{\lambda }$. [ABSTRACT FROM AUTHOR]

Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $\alpha > 0$. We construct, for any sufficiently small $\delta > 0$ , binary linear codes of block length $O(1/\delta ^{2+\alpha })$ and rate $I(W)-\delta $ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length $O(1/\delta ^{2})$. This quadratic dependence on the gap $\delta $ to capacity is known to be best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity. [ABSTRACT FROM AUTHOR]

In this article, we propose an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code. Using these algorithms, we demonstrate—both with a heuristic analysis and in practice—a small polynomial speed-up over the Information-Set Decoding algorithm of Lee and Brickell (1988) for random binary codes. This appears to be the first such speed-up that is not based on a time-memory trade-off. The above speed-up should be read as a very preliminary example of the potential of a reduction theory for codes, for example in cryptanalysis. [ABSTRACT FROM AUTHOR]

We determine the exact value of the optimal symmetric rate point $(r, r)$ in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity $r = h(1/2-\delta) \approx 0.78974$ , where $h(\cdot)$ is the binary entropy function and $\delta = 1/(2\log _{2}(2 + \sqrt {3}))$. Our motivation is a problem in quantitative group testing. Given a set of $n$ elements two of which are defective, the quantitative group testing problem asks for the identification of these two defectives through a series of tests. Each test gives the number of defectives contained in the tested subset, and the outcomes of previous tests are assumed known at the time of designing the current test. We establish that the minimum number of tests is asymptotic to $(\log _{2} n) / r$ as $n \to \infty $. [ABSTRACT FROM AUTHOR]

A family of error-correcting codes is list-decodable from error fraction $p$ if, for every code in the family, the number of codewords in any Hamming ball of fractional radius $p$ is less than some integer $L$. It is said to be list-recoverable for input list size $\ell $ if for every sufficiently large subset of at least $L$ codewords, there is a coordinate where the codewords take more than $\ell $ values. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below $q$ is the alphabet size, and $ \varepsilon > 0$ is the gap to capacity). (1) A random linear code of rate $1 - \log _{q}(\ell) - \varepsilon $ requires list size $L \ge \ell ^{\Omega (1/ \varepsilon)}$ for list-recovery from input list size $\ell $. (2) A random linear code of rate $1 - h_{q}(p) - \varepsilon $ requires list size $L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $ for list-decoding from error fraction $p$. (3) A random binary linear code of rate $1 - h_{2}(p) - \varepsilon $ is list-decodable from average error fraction $p$ with list size with $L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018). [ABSTRACT FROM AUTHOR]

We give a complete answer to the following basic question: “What is the maximal fraction of deletions or insertions tolerable by $q$ -ary list-decodable codes with non-vanishing information rate?” This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best-known result was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family. For any desired $\varepsilon > 0$ , we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma $ fraction of insertions and $\delta $ fraction of deletions as long as $\gamma + 2\delta \leq 1 - \varepsilon $. On the other hand, for any $\gamma, \delta $ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions. We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is not the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$ -piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve. The main technical work in our results is proving the existence of code families of sufficiently large size with good list-decoding properties for any combination of $\delta,\gamma $ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh and Ma, 2014]. Finally, we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate. [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]

The bee identification problem is a problem of properly recognizing a massive amount of data (a numerous amount of bees in a beehive, for example) which have been mixed and corrupted by noise. We derive various error exponents in the bee identification problem under two different decoding rules. Under naïve decoding, which decodes each bee independently of the others, we analyze a general discrete memoryless channel and a relatively wide family of stochastic decoders. Upper and lower bounds to the random coding error exponent are derived and proved to be equal at relatively high coding rates. Then, we propose a lower bound on the error exponent of the typical random code, which improves upon the random coding exponent at low coding rates. We also derive a third bound, which is related to expurgated codes, which turns out to be strictly higher than the other bounds, also at relatively low rates. We show that the universal maximum mutual information decoder is optimal with respect to the typical random code and the expurgated code. Moving further, we derive error exponents under optimal decoding, the relatively wide family of symmetric channels, and the maximum likelihood decoder. We first propose a random coding lower bound, and then, an improved bound which stems from an expurgation process. We show numerically that our second bound strictly improves upon the random coding bound at an intermediate range of coding rates, where a bound derived in a previous work no longer holds. [ABSTRACT FROM AUTHOR]

We give an explicit construction of length- $n$ binary codes capable of correcting the deletion of two bits that have size $2^{n}/n^{4+o(1)}$. This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size $\Omega (2^{n}/n^{4})$. Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size $\Omega (2^{n}/n^{3+o(1)})$ that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear. [ABSTRACT FROM AUTHOR]

The Byzantine distributed quickest change detection (BDQCD) is studied, where a fusion center monitors the occurrence of an abrupt event through a bunch of distributed sensors that may be compromised. We first consider the binary hypothesis case where there is only one post-change hypothesis and prove a novel converse to the first-order asymptotic detection delay in the large mean time to a false alarm regime. This converse is tight in that it coincides with the currently best achievability shown by Fellouris et al.; hence, the optimal asymptotic performance of binary BDQCD is characterized. An important implication of this result is that, even with compromised sensors, a 1-bit link between each sensor and the fusion center suffices to achieve asymptotic optimality. To accommodate multiple post-change hypotheses, we then formulate the multi-hypothesis BDQCD problem and again investigate the optimal first-order performance under different bandwidth constraints. A converse is first obtained by extending our converse from binary to multi-hypothesis BDQCD. Two families of stopping rules, namely the simultaneous d-th alarm and the multi-shot d-th alarm, are then proposed. Under sufficient link bandwidth, the simultaneous d-th alarm, with d being set to the number of honest sensors, can achieve the asymptotic performance that coincides with the derived converse bound; hence, the asymptotically optimal performance of multi-hypothesis BDQCD is again characterized. Moreover, although being shown to be asymptotically optimal only for some special cases, the multi-shot d-th alarm is much more bandwidth-efficient and energy-efficient than the simultaneous d-th alarm. Built upon the above success in characterizing the asymptotic optimality of the BDQCD, a corresponding leader-follower Stackelberg game is formulated and its solution is found. [ABSTRACT FROM AUTHOR]