Search

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

This paper provides new constructions and lower bounds for subspace codes, using Ferrers diagram rank-metric codes from matchings of the complete graph and pending blocks. We present different constructions for constant dimension codes with minimum injection distance 2 or $k-1$ , where $k$ is the constant dimension. Furthermore, we present a construction of new codes from old codes for any minimum distance. Then, we construct nonconstant dimension codes from these codes. Some examples of codes obtained by these constructions are the largest known codes for the given parameters. [ABSTRACT FROM PUBLISHER]

Random network coding recently attracts attention as a technique to disseminate information in a network. This paper considers a noncoherent multishot network, where the unknown and time-variant network is used several times. In order to create dependence between the different shots, particular convolutional codes in rank metric are used. These codes are so-called (partial) unit memory ((P)UM) codes, i.e., convolutional codes with memory one. First, distance measures for convolutional codes in rank metric are shown and two constructions of (P)UM codes in rank metric based on the generator matrices of maximum rank distance codes are presented. Second, an efficient error-erasure decoding algorithm for these codes is presented. Its guaranteed decoding radius is derived and its complexity is bounded. Finally, it is shown how to apply these codes for error correction in random linear and affine network coding. [ABSTRACT FROM AUTHOR]

Encoding and indexing of lattice codes is generalized from self-similar lattice codes to a broader class of lattices. If coding lattice $\Lambda_{\mathrm c}$ and shaping lattice $\Lambda_{\mathrm s}$ satisfy $\Lambda _{\mathrm s}\subseteq \Lambda _{\mathrm c}$ , then $\Lambda _{\mathrm c}/ \Lambda _{\mathrm s}$ is a quotient group that can be used to form a (nested) lattice code $\mathcal C$. Conway and Sloane’s method of encoding and indexing does not apply when the lattices are not self-similar. Results are provided for two classes of lattices. 1) If $\Lambda _{\mathrm c}$ and $\Lambda _{\mathrm s}$ both have generator matrices in a triangular form that satisfies $\Lambda _{\mathrm s}\subseteq \Lambda _{\mathrm c}$ , then encoding is always possible. 2) When $\Lambda _{\mathrm c}$ and $\Lambda _{\mathrm s}$ are described by full generator matrices, if a solution to a linear diophantine equation exists, then encoding is possible. In addition, special cases where $\mathcal C$ is a cyclic code are considered. A condition for the existence of a group isomorphism between the information and $\mathcal C$ is given. The results are applicable to a variety of coding lattices, including Construction A, Construction D, and low-density lattice codes. A variety of shaping lattices may be used as well, including convolutional code lattices and the direct sum of important lattices such as $D_{4}$ , $E_{8}$ , etc. Thus, a lattice code $\mathcal C$ can be designed by selecting $\Lambda _{\mathrm c}$ and $\Lambda _{\mathrm s}$ separately, avoiding the competing design requirements of self-similar lattice codes. [ABSTRACT FROM AUTHOR]

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

Baranyai’s theorem is well known in the theory of hypergraphs. A corollary of this theorem says that one can partition the family of all \(u\) -subsets of an \(n\) -element set into \({n-1\choose u-1}\) subfamilies such that each subfamily forms a partition of the \(n\) -element set, where \(n\) is divisible by \(u\) . In this paper, we present a coding-theoretic application of Baranyai’s theorem. More precisely, we propose a combinatorial construction of locally decodable codes. Locally decodable codes are error-correcting codes that allow the recovery of any message symbol by looking at only a few symbols of the codeword. The number of looked codeword symbols is called query complexity. Such codes have attracted a lot of attention in recent years. The Walsh–Hadamard code is a well-known binary two-query locally decodable code of exponential length that can recover any message bit using 2 bits of the codeword. Our construction can give locally decodable codes over small finite fields for any constant query complexities. In particular, it gives a ternary two-query locally decodable code of length asymptotically shorter than the Walsh–Hadamard code. [ABSTRACT FROM PUBLISHER]

In this paper, we extend the concept of maximum-distance separable (MDS) array codes to a larger class of codes, where the array columns contain a variable number of data and parity symbols and the codewords cannot be arranged, in general, in a regular array structure with equal column length. These new codes, named irregular MDS array codes, find applications in problems of distributed data storage with multiple sources of information generating data at unequal rates. We solve the problem of finding optimal parity symbol allocations that achieve minimum redundancy for a given level of protection against block erasures. We provide a classification of irregular MDS array codes according to the parameters of their parity symbol allocation and we show how regular MDS array codes are a special case of this wider class. We derive necessary and sufficient conditions for such irregular array codes to be MDS and extend the concept of the lowest density generator matrix. Finally, we show how a simple constructive method allows to design irregular lowest density MDS array codes with alphabet size independent of the size of the array columns. [ABSTRACT FROM AUTHOR]

Network coding can significantly improve the transmission rate of communication networks with packet loss compared with routing. However, using network coding usually incurs high computational and storage costs in the network devices and terminals. For example, some network coding schemes require the computational and/or storage capacities of an intermediate network node to increase linearly with the number of packets for transmission, making such schemes difficult to be implemented in a router-like device that has only constant computational and storage capacities. In this paper, we introduce batched sparse code (BATS code), which enables a digital fountain approach to resolve the above issue. BATS code is a coding scheme that consists of an outer code and inner code. The outer code is a matrix generation of a fountain code. It works with the inner code that comprises random linear coding at the intermediate network nodes. BATS codes preserve such desirable properties of fountain codes as ratelessness and low encoding/decoding complexity. The computational and storage capacities of the intermediate network nodes required for applying BATS codes are independent of the number of packets for transmission. Almost capacity-achieving BATS code schemes are devised for unicast networks and certain multicast networks. For general multicast networks, under different optimization criteria, guaranteed decoding rates for the destination nodes can be obtained. [ABSTRACT FROM AUTHOR]

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

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

We consider the Gaussian wiretap channel, where two legitimate players Alice and Bob communicate over an additive white Gaussian noise (AWGN) channel, while Eve is eavesdropping, also through an AWGN channel. We propose a coding strategy based on lattice coset encoding. We define the secrecy gain as a design criterion for wiretap lattice codes, expressed in terms of the lattice theta series, which characterizes Eve’s confusion as a function of the channel parameters. The secrecy gain is studied for even unimodular lattices, and an asymptotic analysis shows that it grows exponentially in the dimension of the lattice. Examples of wiretap lattice codes are given. [ABSTRACT FROM AUTHOR]

An efficient isomorph-free generation algorithm for classification of binary self-dual codes with the minimum distance $d = 4$ is presented. It is combined with another isomorph-free generation algorithm for classification of self-dual codes with the minimum distance $d \ge 6$ . A complete classification of all binary self-dual codes of length 40 is given as a result. [ABSTRACT FROM PUBLISHER]

For some extremal (optimal) odd unimodular lattice L in dimensions 12, 16, 20, 28, 32, 36, 40, and 44, we determine all integers k such that L contains a k -code of lengths 12, 16, 20, 32, 36, 40, and 44, and a near-extremal Type I \mathbb {Z}_{k} -code of length 28 for positive integers k$ with only a few exceptions. [ABSTRACT FROM PUBLISHER]

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

A construction of a channel code by using a source code with decoder side information is introduced. The encoder and decoder pair of any source code can be used for the construction. Constrained-random-number generators, which generate random numbers satisfying a condition specified by a function and its value, are used to construct stochastic encoders and decoders. The result suggests that we can divide the channel coding problem into the problems of channel encoding and source decoding with side information. [ABSTRACT FROM AUTHOR]

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

Let p be a prime, and \lambda be a nonzero element of the finite field \mathbb Fp^{m} . The \lambda -constacyclic codes of length p^s over \mathbb Fp^{m} are linearly ordered under set-theoretic inclusion, i.e., they are the ideals \langle (x-\lambda 0)^{i} \rangle , 0 \leq i \leq p^s of the chain ring [(\mathbb Fp^{m[x]})/({\langle x^{p^{s}}-\lambda \rangle })] . This structure is used to establish the symbol-pair distances of all such $\lambda$ -constacyclic codes. Among others, all maximum distance separable symbol-pair constacyclic codes of length p^s are obtained. [ABSTRACT FROM AUTHOR]

We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C=(1+K/N+K^2/N^2+\cdots +K^M-1/N^M-1)^-1=(1+Rc+Rc^2+\cdots +Rc^M-1)^-1=({1-Rc})/({1-Rc^{M}}) , where Rc is the rate of the $(N,K)$ MDS code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost when the storage code is restricted to the class of MDS codes. The result generalizes the achievability and converse results for the classical PIR with replicated databases to the case of MDS-coded databases. [ABSTRACT FROM PUBLISHER]

A method of constructing rate-compatible polar codes that are capacity achieving at multiple code rates with low-complexity sequential decoders is presented. The underlying idea of the construction exploits certain common characteristics of polar codes that are optimized for a sequence of successively degraded channels. The proposed code consists of parallel concatenation of multiple polar codes with information-bit divider at the input of each polar encoder. Thus, it is referred to as parallel concatenated polar (PCP) codes. A lower-rate PCP code is simply constructed by adding more constituent polar codes, which enables incremental retransmissions at different rates in order to adapt to channel conditions. Due to the length limitation of polar codes, the PCP code can only support a restricted set of rates that is characterized by the size of the kernel when conventional polar codes are used. To overcome this limitation, punctured polar codes, which provide more flexibility on blocklength by controlling a puncturing fraction, are considered as constituent codes. The existence of capacity-achieving punctured polar codes for any given puncturing fraction is proven. Using such punctured polar codes as constituent codes, it is shown that the proposed PCP code is capacity achieving for an arbitrary sequence of rates and for any class of degraded channels. [ABSTRACT FROM AUTHOR]

One of the main problems of the research area of network coding is to compute good lower and upper bounds of the achievable cardinality of so-called subspace codes in \mathcal Pq(n) , i.e., the set of subspaces of \mathbb Fq^{n} , for a given minimal distance. Here we generalize a construction of Etzion and Silberstein to a wide range of parameters. This construction, named coset construction, improves or attains several of the previously best-known subspace code sizes and attains the maximum-rank distance bound for an infinite family of parameters. [ABSTRACT FROM AUTHOR]

In this paper, we consider metrics determined by hierarchical posets and give explicit formulas for the main parameters of a linear code: the minimum distance and the packing, covering, and Chebyshev radii of a code. We also present ten characterizations of hierarchical poset metrics, including new characterizations and simple new proofs to the known ones. [ABSTRACT FROM AUTHOR]

A normal rational curve of the (k-1) -dimensional projective space over {\mathbb F}_{q} is an arc of size q+1$ , since any k$ points of the curve span the whole space. In this paper, we will prove that if q$ is odd, then a subset of size 3k-6$ of a normal rational curve cannot be extended to an arc of size q+2$ . In fact, we prove something slightly stronger. Suppose that q$ is odd and E$ is a (2k-3)$ -subset of an arc G$ of size 3k-6$ . If G$ projects to a subset of a conic from every (k-3)$ -subset of E of odd characteristic, which can be extended to a Reed–Solomon code of length $q+1$ , cannot be extended to a linear maximum distance separable code of length $q+2$ . [ABSTRACT FROM AUTHOR]

We describe a general method for turning quantum circuits into sparse quantum subsystem codes. The idea is to turn each circuit element into a set of low-weight gauge generators that enforce the input–output relations of that circuit element. Using this prescription, we can map an arbitrary stabilizer code into a new subsystem code with the same distance and number of encoded qubits but where all the generators have constant weight, at the cost of adding some ancilla qubits. With an additional overhead of ancilla qubits, the new code can also be made spatially local. Applying our construction to certain concatenated stabilizer codes yields families of subsystem codes with constant-weight generators and with minimum distance d = n^1- \epsilon , where \epsilon = O(1/\sqrt \log n) . For spatially local codes in D dimensions, we nearly saturate a bound due to Bravyi and Terhal and achieve d = n^{1- \epsilon -1/D} . Previously the best code distance achievable with constant-weight generators in any dimension, due to Freedman, Meyer, and Luo, was O(\sqrt {n\log n})$ for a stabilizer code. [ABSTRACT FROM PUBLISHER]

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

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]

Deep generative models have emerged as a powerful class of priors for signals in various inverse problems such as compressed sensing, phase retrieval and super-resolution. In this work, we consider the compressed sensing problem and assume the unknown signal to lie in the range of some pre-trained generative model. A popular approach for signal recovery is via gradient descent in the low-dimensional latent space. While gradient descent has achieved good empirical performance, its theoretical behavior is not well understood. We introduce the use of stochastic gradient Langevin dynamics (SGLD) for compressed sensing with a generative prior. Under mild assumptions on the generative model, we prove the convergence of SGLD to the true signal. We also demonstrate competitive empirical performance to standard gradient descent. [ABSTRACT FROM AUTHOR]

We introduce quantum pin codes: a class of quantum CSS codes. Quantum pin codes are a generalization of quantum color codes and Reed-Muller codes and share a lot of their structure and properties. Pin codes have gauge operators, an unfolding procedure and their stabilizers form so-called $\ell $ -orthogonal spaces meaning that the joint overlap between any $\ell $ stabilizer elements is always even. This last feature makes them interesting for devising magic-state distillation protocols, for instance by using puncturing techniques. We study examples of these codes and their properties. [ABSTRACT FROM AUTHOR]

We explicitly construct random hash functions for privacy amplification (extractors) that require smaller random seed lengths than the previous literature, and still allow efficient implementations with complexity $O(n\log n)$ for input length $n$ . The key idea is the concept of dual universal2 hash function introduced recently. We also use a new method for constructing extractors by concatenating $\delta $ -almost dual universal2 hash functions with other extractors. Besides minimizing seed lengths, we also introduce methods that allow one to use non-uniform random seeds for extractors. These methods can be applied to a wide class of extractors, including dual universal2 hash function, as well as to the conventional universal2 hash functions. [ABSTRACT FROM AUTHOR]

We show that a p -ary polyphase sequence of period p^{2} from the Fermat quotients is perfect. That is, its periodic autocorrelation is zero for all non-trivial phase shifts. We call this Fermat-quotient sequence. We propose a collection of optimal families of perfect polyphase sequences using the Fermat-quotient sequences in the sense of the Sarwate bound. That is, the cross correlation of two members in a family is upper bounded by p . To investigate some relation between Fermat-quotient sequences and Frank-Zadoff sequences and to construct optimal families including these sequences, we introduce generators of p -ary polyphase sequences of period p^{2} using their p\times p$ array structures. We call an optimal generator to be the generator of some $p$ -ary polyphase sequences which are perfect and which gives an optimal family by the proposed construction. Finally, we propose an algebraic construction for optimal generators as another main result. A lot of optimal families of size $p-1$ can be constructed from these optimal generators, some of which are known to be from the Fermat-quotient sequences or from the Frank-Zadoff sequences, but some families are new for $p\geq 11$ . The relation between the Fermat-quotient sequences and the Frank-Zadoff sequences is determined as a by-product. [ABSTRACT FROM AUTHOR]

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

We characterize product-maximum distance separable (PMDS) pairs of linear codes, i.e., pairs of codes $C$ and $D$ whose product under coordinatewise multiplication has maximum possible minimum distance as a function of the code length and the dimensions $\dim C$ and $\dim D$ . We prove in particular, for $C=D$ , that if the square of the code $C$ has minimum distance at least 2, and $(C,C)$ is a PMDS pair, then either $C$ is a generalized Reed–Solomon code, or $C$ is a direct sum of self-dual codes. In passing we establish coding-theory analogues of classical theorems of additive combinatorics. [ABSTRACT FROM AUTHOR]

We construct a family of $(n,k)$ convolutional codes with degree $\delta \in \{k,n-k\}$ that have a maximum distance profile. The field size required for our construction is $\Theta (n^{2\delta })$ , which improves upon the known constructions of convolutional codes with a maximum distance profile. Our construction is based on the theory of skew polynomials. [ABSTRACT FROM AUTHOR]

We study the Singleton-type bound that provides an upper limit on the minimum distance of locally repairable codes. We present an improved bound by carefully analyzing the combinatorial structure of the repair sets. Thus, we show the previous bound is unachievable for certain parameters. We then also provide explicit constructions of optimal codes which show that for certain parameters the new bound is sharp. Additionally, as a byproduct, some previously known codes are shown to attain the new bound and are thus proved to be optimal. [ABSTRACT FROM AUTHOR]

We study generalized covering radii, a fundamental property of linear codes that characterizes the trade-off between storage, latency, and access in linear data-query protocols such as PIR. We prove lower and upper bounds on the generalized covering radii of Reed-Muller codes, as well as finding their exact value in certain extreme cases. With the application to linear data-query protocols in mind, we also construct a covering algorithm that gets as input a set of points in space, and find a corresponding set of codewords from the Reed-Muller code that are jointly not farther away from the input than the upper bound on the generalized covering radius of the code. We prove that the algorithm runs in time that is polynomial in the code parameters. [ABSTRACT FROM AUTHOR]

A construction of big convolutional codes from short codes called block Markov superposition transmission (BMST) is proposed. The BMST is very similar to superposition block Markov encoding (SBME), which has been widely used to prove multiuser coding theorems. The BMST codes can also be viewed as a class of spatially coupled codes, where the generator matrices of the involved short codes (referred to as basic codes) are coupled. The encoding process of BMST can be as fast as that of the basic code, while the decoding process can be implemented as an iterative sliding-window decoding algorithm with a tunable delay. More importantly, the performance of BMST can be simply lower bounded in terms of the transmission memory given that the performance of the short code is available. Numerical results show that: 1) the lower bounds can be matched with a moderate decoding delay in the low bit-error-rate (BER) region, implying that the iterative sliding-window decoding algorithm is near optimal; 2) BMST with repetition codes and single parity-check codes can approach the Shannon limit within 0.5 dB at the BER of 10^-5 for a wide range of code rates; and 3) BMST can also be applied to nonlinear codes. [ABSTRACT FROM AUTHOR]

We propose a lattice construction from totally real and complex multiplication fields, which naturally generalizes Construction A of lattices from p -ary codes obtained from the cyclotomic field \mathbb {Q}(\zeta _{p}) , p a prime, which in turn contains the so-called Construction A of lattices from binary codes as a particular case. We focus on the maximal totally real subfield \mathbb Q(\zeta p^{r}\,+\,\zeta p^{-r}) of the cyclotomic field \mathbb Q(\zeta p^{r}) , $r\geq 1$ . Our construction has applications to coset encoding of algebraic lattice codes for block fading channels, and in particular for block fading wiretap channels. [ABSTRACT FROM AUTHOR]

Given a linear code $C$ , one can define the d$ th power of C$ as the span of all componentwise products of d$ elements of C$ . A power of C or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2-n$ is at least linear in $k$ . The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros. [ABSTRACT FROM PUBLISHER]

We consider partially connected $K$ -user interference networks, where the transmitters have no knowledge about the channel gain values, but they are aware of network topology. We introduce several linear algebraic and graph theoretic concepts to derive new topology-based outer bounds and inner bounds on the symmetric degrees-of-freedom of these networks. We evaluate our bounds for two classes of networks to demonstrate their tightness for most networks in these classes, quantify the gain of our inner bounds over benchmark interference management strategies, and illustrate the effect of network topology on these gains. [ABSTRACT FROM AUTHOR]

In distributed storage systems, erasure codes with locality \(r\) are preferred because a coordinate can be locally repaired by accessing at most \(r\) other coordinates which in turn greatly reduces the disk I/O complexity for small \(r\) . However, the local repair may not be performed when some of the \(r\) coordinates are also erased. To overcome this problem, we propose the \((r,\delta )_{c}\) -locality providing \(\delta -1\) nonoverlapping local repair groups of size no more than \(r\) for a coordinate. Consequently, the repair locality \(r\) can tolerate \(\delta -1\) erasures in total. We derive an upper bound on the minimum distance for any linear \([n,k]\) code with information \((r,\delta )_{c}\) -locality. Then, we prove existence of the codes that attain this bound when \(n\geq k(r(\delta -1)+1)\) . Although the locality \((r,\delta )\) defined by Prakash et al. provides the same level of locality and local repair tolerance as our definition, codes with \((r,\delta )_{c}\) -locality attaining the bound are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol \((r,\delta )_{c}\) -locality where the gain in minimum distance is \(\Omega (\sqrt {r})\) and the information rate is close to 1. [ABSTRACT FROM PUBLISHER]

We improve lower bounds on the \(k\) th-order nonlinear complexity of pseudorandom sequences over finite fields, including explicit inversive sequences and sequences obtained from Hermitian function fields, and we establish a probabilistic result on the behavior of the \(k\) th-order nonlinear complexity of random sequences over finite fields. [ABSTRACT FROM AUTHOR]

This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed–Solomon codes, i.e. subcodes of Reed–Solomon codes over ${\mathbb {F}_{q^{m}}}$ whose entries lie in a fixed collection of ${\mathbb {F}_{q}}$ –subspaces of ${\mathbb {F}_{q^{m}}}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called the twisted product which yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen ${\mathbb {F}_{q}}$ –subspaces have dimension larger than $m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger. [ABSTRACT FROM AUTHOR]

Two algorithms for the classification of linear codes over finite fields are presented. One of the algorithms is based on canonical augmentation and the other one on lattice point enumeration. New classification results over fields with 2, 3 and 4 elements are obtained. [ABSTRACT FROM AUTHOR]

We investigate fat projective linear codes over ${\mathbb Z}_{p^{m}}$ , $m\geqslant 2$ , with two nonzero homogeneous weights (“two-weight codes”), building on the graph theory approach developed by Delsarte for codes over fields. Our main result is the classification of such codes under the additional assumption that the columns of a generator matrix of the code determine a cap in the projective Hjelmslev geometry $\mathop {\mathrm {PHG}}\nolimits (k-1, {\mathbb Z}_{p^{m}})$. This generalizes a result on projective two weight codes with dual distance at least four (Calderbank, 1982). The proof relies on a careful analysis of a certain strongly regular graph built on the cosets of the dual code, and on an interpretation of its parameters in terms of projective Hjelmslev geometry. [ABSTRACT FROM AUTHOR]

We consider a generalized construction of stream ciphers with forward security. The design framework is modular: it is built from a so-called layer function that updates the key and (optionally) the nonce and generates a new pseudorandom output stream. We analyze the generalized construction for four different instantiations: two possible layer functions that are in turn instantiated with either a block cipher or a pseudorandom function. We prove that each of these instantiations gives a stream cipher that is pseudorandom and forward secure in the multi-user setting with a very tight bound. A comprehensive analysis shows that the two block cipher based instantiations achieve very similar bounds. For the pseudorandom function based instantiations there is no clear winner: either layer can be beneficial over the other one, depending on the choice of parameters. By instantiating the pseudorandom function with a generic construction such as the sum of permutations, we obtain a highly efficient and competitive stream cipher based on an n-bit block cipher that is secure beyond the $2^{\text {n}/2}$ birthday bound. [ABSTRACT FROM AUTHOR]

As an important coding scheme in modern distributed storage systems, locally repairable codes (LRCs) have attracted a lot of attentions from perspectives of both practical applications and theoretical research. As a major topic in the research of LRCs, bounds and constructions of the corresponding optimal codes are of particular concerns. In this work, codes with $(r,\delta)$ -locality which have optimal minimal distance w.r.t. the bound given by Prakash et al. are considered. Through parity-check matrix approach, constructions of both optimal $(r,\delta)$ -LRCs with all symbol locality ($(r,\delta)_{a}$ -LRCs) and optimal $(r,\delta)$ -LRCs with information locality ($(r,\delta)_{i}$ -LRCs) are provided. As a generalization of a work of Xing and Yuan, these constructions are built on a connection between sparse hypergraphs and optimal $(r,\delta)$ -LRCs. With the help of constructions of large sparse hypergraphs, the lengths of codes obtained from our construction can be super-linear in the alphabet size. This improves upon previous constructions when the minimal distance of the code is at least $3\delta +1$. As two applications, optimal H-LRCs with super-linear lengths and GSD codes with unbounded lengths are also constructed. [ABSTRACT FROM AUTHOR]

We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector ${\mathbf{X}}\in \mathbb {R}^{n}$ in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of $\boldsymbol {X}$ are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for $\boldsymbol {X}$ are considered—uniform and Gaussian. For the uniform model, in dimensions two and three, the error probability is seen to grow with the packing density, and we demonstrate that the densest lattice in dimension two presents the worst error probability. For higher dimensions, we develop probabilistic concentration bounds as well as bounds based on geometric arguments for the error probability. The probabilistic bounds lead to the conclusion that for lattices which generate suitably thin coverings of $\mathbb {R}^{n}$ (which includes lattices that meet Rogers’ bound on the covering radius), the error probability goes to unity as $n$ grows. Probabilistic and geometric bounds are also used to estimate the error probability under the uniform model for various lattices including the $A_{n}$ family and the Leech lattice, $\Lambda _{24}$. On the other hand, for the Gaussian model, the error probability goes to zero as the lattice dimension tends to infinity, provided the noise variance is sufficiently small. [ABSTRACT FROM AUTHOR]

Spectral bounds on the minimum distance of quasi-twisted codes over finite fields are proposed, based on eigenvalues of polynomial matrices and the corresponding eigenspaces. They generalize the Semenov-Trifonov and Zeh-Ling bounds in a way similar to how the Roos and shift bounds extend the BCH and HT bounds for cyclic codes. The eigencodes of a quasi-twisted code in the spectral theory and the outer codes in its concatenated structure are related. A comparison based on this relation verifies that the Jensen bound always outperforms the spectral bound under special conditions, which yields a similar relation between the Lally and the spectral bounds. The performances of the Lally, Jensen and spectral bounds are presented in comparison with each other. [ABSTRACT FROM AUTHOR]

Based on the applications to the wire-tap channel and bounds on the relative generalized Hamming weight, we will introduce optimal codes of type $\mathcal {I}$ and type $\mathcal {II}$. We will give some necessary conditions and the explicit construction for a linear code $\mathcal {C}$ to be optimal of type $\mathcal {I}$ and $\mathcal {II}$ with respect to a subcode $\mathcal {C}_{1}$. We will also present a new bound on two different parameters of the relative generalized Hamming weight. [ABSTRACT FROM AUTHOR]

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

Given a collection of probability distributions p1, . . . , pm, the minimum entropy coupling is the coupling X1, . . . , Xm (Xi ∼ pi) with the smallest entropy H(X1, . . . , Xm). While this problem is known to be NP-hard, we present an efficient algorithm for computing a coupling with entropy within 2 bits from the optimal value. More precisely, we construct a coupling with entropy within 2 bits from the entropy of the greatest lower bound of p1, . . . , pm with respect to majorization. This construction is also valid when the collection of distributions is infinite, and when the supports of the distributions are infinite. Potential applications of our results include random number generation, entropic causal inference, and functional representation of random variables. [ABSTRACT FROM AUTHOR]