Search

We introduce a new class of rate one-half binary codes: complementary information set codes. A binary linear code of length 2n and dimension n is called a complementary information set code (CIS code for short) if it has two disjoint information sets. This class of codes contains self-dual codes as a subclass. It is connected to graph correlation immune vectorial Boolean functions of use in the security of hardware implementations of cryptographic primitives. Such codes permit to improve the cost of masking cryptographic algorithms against side channel attacks. In this paper, we investigate this new class of codes: we give optimal or best known CIS codes of length < 132. We derive general constructions based on cyclic codes and on double circulant codes. We derive a Varshamov–Gilbert bound for long CIS codes, and show that they can all be classified in small lengths \leq 12 by the building up construction. Some nonlinear permutations are constructed by using \BBZ4-codes, based on the notion of dual distance of a possibly nonlinear code. [ABSTRACT FROM AUTHOR]

Binary linear [n,k] codes that are proper for error detection are known for many combinations of n and k. For the remaining combinations, existence of proper codes is conjectured. In this paper, a particular class of [n,k] codes is studied in detail. In particular, it is shown that these codes are proper for many combinations of n and k which were previously unsettled. [ABSTRACT FROM PUBLISHER]

Although there are many different approaches used in cryptanalysis of nonlinear filter generators, the selection of tap positions has not received enough attention yet. In this paper we examine the security of nonlinear filter generators that output several bits at the time against a variant of a guess and determine attack that takes into account the tap positions of the generator. In difference to the filter state guessing attack (FSGA) introduced by Pasalic (2009), our approach further reduces the input preimage space by using a given placement of the tap positions. The new attack, though a simple generalization of the FSGA, in many cases outperforms both classical algebraic attacks and the FSGA. In particular, the new attack is much more efficiently applied against filter generators that use a vectorial Maiorana–McFarland than classical algebraic attacks or the FSGA. As a proof of the concept we apply our attack to the stream cipher SOBER-t32 without stuttering and show that our attack performs slightly better than a guess and determine attack proposed by Babbage [ABSTRACT FROM AUTHOR]

A polynomial matrix is said to be locally invertible if it has an invertible subsequence map of equal size between its input and output sequence spaces. This paper examines the use of these matrices, which we call locally invertible encoders, for generating multidimensional convolutional codes. We discuss a novel method of encoding and inverting multidimensional sequences using the subsequence map. We also show that the overlapping symbols between consecutive input subsequences obtained during the sequence inversion can be used to determine if the received sequence is the same as the transmitted codeword. [ABSTRACT FROM AUTHOR]

Motivated by iterative decoding techniques for the binary erasure channel Hollmann and Tolhuizen introduced and studied the notion of generic erasure correcting sets for linear codes. A generic (r,s)–erasure correcting set generates for all codes of codimension r a parity check matrix that allows iterative decoding of all correctable erasure patterns of size s or less. The problem is to derive bounds on the minimum size F(r,s) of generic erasure correcting sets and to find constructions for such sets. In this paper, we continue the study of these sets. We derive better lower and upper bounds. Hollmann and Tolhuizen also introduced the stronger notion of (r,s)–sets and derived bounds for their minimum size G(r,s). Here also we improve these bounds. We observe that these two conceps are closely related to so called s–wise intersecting codes, an area, in which G(r,s) has been studied primarily with respect to ratewise performance. We derive connections. Finally, we observed that hypergraph covering can be used for both problems to derive good upper bounds. [ABSTRACT FROM AUTHOR]

In this paper the decoding capabilities of convolutional codes over the erasure channel are studied. Of special interest will be maximum distance profile (MDP) convolutional codes. These are codes which have a maximum possible column distance increase. It is shown how this strong minimum distance condition of MDP convolutional codes help us to solve error situations that maximum distance separable (MDS) block codes fail to solve. Towards this goal, two subclasses of MDP codes are defined: reverse-MDP convolutional codes and complete-MDP convolutional codes. Reverse-MDP codes have the capability to recover a maximum number of erasures using an algorithm which runs backward in time. Complete-MDP convolutional codes are both MDP and reverse-MDP codes. They are capable to recover the state of the decoder under the mildest condition. It is shown that complete-MDP convolutional codes perform in many cases better than comparable MDS block codes of the same rate over the erasure channel. [ABSTRACT FROM PUBLISHER]

We exhibit explicit bases for BCH codes of designed distance 5. While BCH codes are some of the most studied families of codes, only recently Kaufman and Litsyn (FOCS, 2005) showed that they admit bases of small weight codewords. Furthermore, Grigorescu, Kaufman, and Sudan (RANDOM, 2009) and Kaufman and Lovett (FOCS, 2011) proved that, in fact, BCH codes can admit very structured bases of small weight codewords (i.e., bases that can be fully specified by a single codeword and its orbit under the affine group). The existence of such structured bases has applications in property testing, and motivates our search for a fully explicit description of low weight codewords and, in particular, of codewords that generate a basis for BCH codes. In this paper, we describe the support of basis-generating codewords under affine transformations of the domain for the very specific case of binary (extended) BCH(2, n). We believe that extending these findings to general BCH codes merits further investigation. [ABSTRACT FROM PUBLISHER]

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]

Linear finite state machines (LFSMs) are particular primitives widely used in information theory, coding theory and cryptography. Among those linear automata, a particular case of study is linear feedback shift registers (LFSRs) used in many cryptographic applications such as design of stream ciphers or pseudo-random generation. LFSRs could be seen as particular LFSMs without inputs. In this paper, we first recall the description of LFSMs using traditional matrices representation. Then, we introduce a new matrices representation with polynomial fractional coefficients. This new representation leads to sparse representations and implementations. As direct applications, we focus our work on the Windmill generators case, used for example in the E0 stream cipher and on other general applications that use this new representation. In a second part, a new design criterion called diffusion delay for LFSRs is introduced and well compared with existing related notions. This criterion represents the diffusion capacity of an LFSR. Thus, using the matrices representation, we present a new algorithm to randomly pick LFSRs with good properties (including the new one) and sparse descriptions dedicated to hardware and software designs. We present some examples of LFSRs generated using our algorithm to show the relevance of our approach. [ABSTRACT FROM AUTHOR]

Kloosterman sums have recently become the focus of much research, most notably due to their applications in cryptography and coding theory. In this paper, we extensively investigate the link between the semibentness property of functions in univariate forms obtained via Dillon and Niho functions and Kloosterman sums. In particular, we show that zeros and the value four of binary Kloosterman sums give rise to semibent functions in even dimension with maximum degree. Moreover, we study the semibentness property of functions in polynomial forms with multiple trace terms and exhibit criteria involving Dickson polynomials. [ABSTRACT FROM AUTHOR]

In this paper, a new but simple construction of stabilizer codes and related entanglement-assisted quantum error-correcting codes is proposed based on syndrome assignment by classical parity-check matrices. This method turns the construction of quantum stabilizer codes to the construction of classical parity-check matrices satisfying a specific commutative condition. The designed minimum distance 2t^*+1 of the constructed quantum stabilizer codes can be achieved by a commutative classical parity-check matrix with classical minimum distance 4t^*-m, where the parameter m, 0\leq m\leq 2t^*, depends on a property of the parity-check matrix. As m decreases, there is an increasing set of additional correctable error operators beyond the designed error correcting capability t^*. The (asymptotic) coding efficiency is at least comparable to that of CSS codes. A class of quantum Reed–Muller codes is constructed and codes in this class have a larger set of correctable error operators than that of the quantum Reed–Muller codes previously developed in the literature. Quantum circulant codes are also constructed and many of them are optimal in terms of their coding parameters. [ABSTRACT FROM AUTHOR]

At Crypto'07, Goyal introduced the concept of Accountable Authority Identity-Based Encryption (A-IBE) as a convenient tool to reduce the amount of trust in authorities in Identity-Based Encryption. In this model, if the Private Key Generator (PKG) maliciously re-distributes users' decryption keys, it runs the risk of being caught and prosecuted. Goyal proposed two constructions: the first one is efficient but can only trace well-formed decryption keys to their source; the second one allows tracing obfuscated decryption boxes in a model (called weak black-box model) where cheating authorities have no decryption oracle. The latter scheme is unfortunately far less efficient in terms of decryption cost and ciphertext size. The contribution of this paper is to describe a new construction that combines the efficiency of Goyal's first proposal with a simple weak black-box tracing mechanism. The proposed scheme is the first A-IBE that meets all security properties (although traceability is only guaranteed in the weak black-box model) in the adaptive-ID sense. [ABSTRACT FROM AUTHOR]

The problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of memoryless subsources is revisited. Berger's 1971 paper “The Source Coding Game” solves this problem when the adversary is allowed only strictly causal access to the subsource realizations. The case when the adversary has access to the subsource realizations non-causally is considered. This new rate-distortion function is determined to be the maximum of the rate-distortion function over a set of independent and identically distributed (IID) random variables that can be simulated by the adversary. The results are extended to allow for partial or noisy observations of subsource realizations. The model is further explored by attempting to find the rate-distortion function when the ‘adversary’ is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a desired accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID source. [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]

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

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]

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

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]

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

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]

A family of quantum codes of increasing block length with positive rate is asymptotically good if the ratio of its distance to its block length approaches a positive constant. The asymptotic quantum Gilbert–Varshamov (GV) bound states that there exist q -ary quantum codes of sufficiently long block length N having fixed rate R with distance at least , where H_{q^{2}} is the q^{2}$ -ary entropy function. For $q<7$ , only random quantum codes are known to asymptotically attain the quantum GV bound. However, random codes have little structure. In this paper, we generalize the classical result of Thommesen to the quantum case, thereby demonstrating the existence of concatenated quantum codes that can asymptotically attain the quantum GV bound. The outer codes are quantum generalized Reed–Solomon codes, and the inner codes are random independently chosen stabilizer codes, where the rates of the inner and outer codes lie in a specified feasible region. [ABSTRACT FROM PUBLISHER]

The subclass of cyclic Goppa codes is proposed. It is proved that this subclass contains all cyclic codes of length n\vert q^m\pm 1 with generator polynomial g(x), g(\alpha ^i)=g(\alpha ^-j)=0, i=0,1,\ldots, s1, \;j=1,\ldots, s2, \alpha ^n=1, \; \alpha \in GF(q^2m). [ABSTRACT FROM AUTHOR]

We study (symbol-pair) codes for symbol-pair read channels introduced recently by Cassuto and Blaum (2010). A Singleton-type bound on symbol-pair codes is established and infinite families of optimal symbol-pair codes are constructed. These codes are maximum distance separable (MDS) in the sense that they meet the Singleton-type bound. In contrast to classical codes, where all known q-ary MDS codes have length O(q), we show that q-ary MDS symbol-pair codes can have length \Omega (q^2). In addition, we completely determine the existence of MDS symbol-pair codes for certain parameters. [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]

A method for constructing n-stage Galois NLFSRs with period 2^n-1 from n-stage maximum length LFSRs is presented. Nonlinearity is introduced into state cycles by adding a nonlinear Boolean function to the feedback polynomial of the LFSR. Each assignment of variables for which this function evaluates to 1 acts as a crossing point for the LFSR state cycle. The effect of nonlinearity is cancelled and state cycles are joined back by adding a copy of the same function to a later stage of the register. The presented method requires no extra time steps and it has a smaller area overhead compared to the previous approaches based on cross-join pairs. It is feasible for large n. [ABSTRACT FROM AUTHOR]

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary k of n nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary d nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. [ABSTRACT FROM AUTHOR]

Let C be a binary extremal self-dual code of length 96. We prove that an automorphism of C of order 3 has 6 or no fixed points and an automorphism of order 5 has 6 fixed points. Moreover, if all automorphisms of order 3 are fixed point free then Aut(C) is solvable and its order divides 2^53 or 2^55 or Aut(C) is the alternating group A5 which is the only possible group of order 60. Furthermore, \vert Aut(C)\vert = 20 or 40 cannot occur. [ABSTRACT FROM AUTHOR]