Search

Bicyclic codes are a generalization of the one-dimensional (1D) cyclic codes to two dimensions (2D). Similar to the 1D case, in some cases, 2D cyclic codes can also be constructed to guarantee a specified minimum distance. Many aspects of these codes are yet unexplored. Motivated by the problem of constructing quantum codes, we study some structural properties of certain bicyclic codes. We show that a primitive narrow-sense bicyclic hyperbolic code of length n 2 contains its dual if and only if its design distance is lower than n - O (n) . We extend the sufficiency condition to the non-primitive case as well. We also show that over quadratic extension fields, a primitive bicyclic hyperbolic code of length n 2 contains Hermitian dual if and only if its design distance is lower than n - O (n) . Our results are analogous to some structural results known for BCH and Reed–Solomon codes. They further our understanding of bicyclic codes. We also give an application of these results by showing that we can construct two classes of quantum bicyclic codes based on our results. [ABSTRACT FROM AUTHOR]

Input devices such as motor-imagery brain-computer interfaces (BCIs) are often unreliable. In theory, channel coding can be used in the human-machine loop to robustly encapsulate intention through noisy input devices but standard feedforward error correction codes cannot be practically applied. We present a practical and general probabilistic user interface for binary input devices with very high noise levels. Our approach allows any level of robustness to be achieved, regardless of noise level, where reliable feedback such as a visual display is available. In particular, we show efficient zooming interfaces based on feedback channel codes for two-class binary problems with noise levels characteristic of modalities such as motor-imagery based BCI, with accuracy <75%. We outline general principles based on separating channel, line and source coding in human-machine loop design. We develop a novel selection mechanism which can achieve arbitrarily reliable selection with a noisy two-state button. We show automatic online adaptation to changing channel statistics, and operation without precise calibration of error rates. A range of visualisations are used to construct user interfaces which implicitly code for these channels in a way that it is transparent to users. We validate our approach with a set of Monte Carlo simulations, and empirical results from a human-in-the-loop experiment showing the approach operates effectively at 50-70% of the theoretical optimum across a range of channel conditions. [ABSTRACT FROM AUTHOR]

In this paper, we present a deliberate bit flipping (DBF) coding scheme for binary two-dimensional (2-D) channels, where specific patterns in channel inputs are the significant cause of errors. The idea is to eliminate a constrained encoder and, instead, embed a constraint into an error correction codeword that is arranged into a 2-D array by deliberately flipping the bits that violate the constraint. The DBF method relies on the error correction capability of the code being used so that it should be able to correct both deliberate errors and channel errors. Therefore, it is crucial to flip minimum number of bits in order not to overburden the error correction decoder. We devise a constrained combinatorial formulation for minimizing the number of flipped bits for a given set of harmful patterns. The generalized belief propagation algorithm is used to find an approximate solution for the problem. We evaluate the performance gain of our proposed approach on a data-dependent 2-D channel, where 2-D isolated-bits patterns are the harmful patterns for the channel. Furthermore, the performance of the DBF method is compared with classical 2-D constrained coding schemes for the 2-D no isolated-bits constraint on a memoryless binary symmetric channel. [ABSTRACT FROM AUTHOR]

The Z2s-additive codes are subgroups of Zn2s, and can be seen as a generalization of linear codes over Z2 and Z4. A Z2s-linear Hadamard code is a binary Hadamard code which is the Gray map image of a Z2s-additive code. It is known that either the rank or the dimension of the kernel can be used to give a complete classification for the Z4-linear Hadamard codes. However, when s > 2, the dimension of the kernel of Z2s-linear Hadamard codes of length 2t only provides a complete classification for some values of t and s. In this paper, the rank of these codes is computed for s = 3. Moreover, it is proved that this invariant, along with the dimension of the kernel, provides a complete classification, once t ≥ 3 is fixed. In this case, the number of nonequivalent such codes is also established. [ABSTRACT FROM AUTHOR]

We provide polylog sparse quantum codes for correcting the Erasure channel arbitrarily close to the capacity. Specifically, we provide the $[[n, k, d]]$ quantum stabilizer codes that correct for the erasure channel arbitrarily close to the capacity if the erasure probability is at least 0.33 and with a generating set $\langle S_{1}, S_{2}, \cdots {} S_{n-k} \rangle $ such that $|S_{i}|\leq {\mathrm{ log}} ^{2+\zeta }(n)$ for all $i$ and for any $\zeta > 0$ with high probability. In this paper, we show that the result of Delfosse et al. is tight: one can construct capacity approaching codes with weight almost $O(1)$. [ABSTRACT FROM AUTHOR]

We construct error-correcting write-once memory (WOM) codes that guarantee correction of any specified number of errors in $q$ -level memories. The constructions use suitably designed short $q$ -ary WOM codes and concatenate them with outer error-correcting codes over different alphabets using suitably designed mappings. With a new storage-efficiency measure, we call EC-rate and show that for common error types the codes save redundancy and implementation complexity over straightforward concatenation. In addition to constructions for guaranteed error correction, we extend the error-correcting WOM scheme to binary multi-level coding for random errors, and toward soft-decision decoding provide an efficient way to extract reliability information without using higher-precision readout. [ABSTRACT FROM AUTHOR]

This paper generalizes the method proposed by Poulliat et al. for the determination of the optimal Galois field coefficients of a non-binary LDPC parity check constraint based on the binary image of the code. Optimal, or almost-optimal, parity check coefficients are given for check degree varying from 4 to 20 and Galois field varying from GF (64) up to GF (1024). For all given sets of coefficients, no codeword of Hamming weight two exists. A reduced complexity algorithm to compute the binary Hamming weight 3 of a parity check is proposed. When the number of sets of coefficients is too high for an exhaustive search and evaluation, a local greedy search is performed. Explicit tables of coefficients are given. The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction. [ABSTRACT FROM AUTHOR]

In the random deletion channel, each bit is deleted independently with probability $p$. For the random deletion channel, the existence of codes of rate $(1-p)/9$ , and thus bounded away from 0 for any $p < 1$ , has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate $c_{0} (1-p)$ for an absolute constant $c_{0} > 0$. [ABSTRACT FROM AUTHOR]

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory. [ABSTRACT FROM AUTHOR]

Neil Sloane showed that the problem of determining the maximum size of a binary code of constant weight 2 that can correct a single adjacent transposition is equivalent to finding the packing number of a certain graph. In this paper we solve this open problem by finding the packing number of the double vertex graph of the path graph. This double vertex graph is isomorphic to Sloane’s graph. Our solution implies a conjecture of Rob Pratt about the ordinary generating function of sequence A085680. [ABSTRACT FROM AUTHOR]

We propose a new structure of a self-checking combinational device where, based on the properties of parity and Berger codes, as well as a code with the detection of all double errors in information vectors, the problem of detecting all single faults of logical elements can be solved without transforming the structure of the source device. The properties of binary codes with the detection of all double errors that can be used in constructing the proposed structure are considered. We give an example of constructing a new structure. [ABSTRACT FROM AUTHOR]

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate $R$ and minimum distance $\delta $ of a binary code. The best known tradeoff is the Gilbert–Varshamov bound, and says that for every $\delta \in (0, 1/2)$ , there are codes with minimum distance $\delta $ and rate $R = {R_{\mathsf {GV}}}(\delta) > 0$ (for a certain simple function ${R_{\mathsf {GV}}}(\cdot)$ ). In this paper, we show that the Gilbert–Varshamov bound can be achieved by codes, which support local error-detection and error-correction algorithms. Specifically, we show the following results. 1) Local testing: for all $\delta \in (0,1/2)$ and all $R < {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally testable with $\mathsf {quasipolylog}(n)$ query complexity. 2) Local correction: for all $\epsilon > 0$ , for all $\delta < 1/2$ sufficiently large, and all $R < (1-\epsilon) {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally correctable from $({\delta }/{2}) - o(1)$ fraction errors with $O(n^{\epsilon })$ query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen’s random concatenation technique and the best known locally testable codes by Kopparty et al. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami–Sudan–Indyk list decoding strategy for concatenated codes, Alon–Edmonds–Luby distance amplification, and the local list-decodability, local list-recoverability, and local testability of Reed–Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code. [ABSTRACT FROM AUTHOR]

Multiply constant-weight codes (MCWCs) have been recently studied to improve the reliability of certain physically unclonable function response. In this paper, we give combinatorial constructions for the MCWCs, which yield several new infinite families of optimal MCWCs. Furthermore, we demonstrate that the Johnson-type upper bounds of the MCWCs are asymptotically tight for fixed Hamming weights and distances. Finally, we provide bounds and constructions of the 2-D MCWCs. [ABSTRACT FROM AUTHOR]

The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of worst case deletions, with a focus on constructing efficiently decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following tradeoffs (for any \varepsilon > 0 ): 1) codes that can correct a fraction 1- \varepsilon of deletions with rate \mathop \mathrm poly\nolimits ( \varepsilon ) over an alphabet of size \mathop \mathrm poly\nolimits (1/ \varepsilon ) ; 2) binary codes of rate 1-\tilde O(\sqrt \varepsilon ) that can correct a fraction $ \varepsilon $ of deletions; and 3) Binary codes that can be list-decoded from a fraction (1/2- \varepsilon )$ of deletions with rate \mathop {\mathrm {poly}}\nolimits ( \varepsilon ) . This paper gives the first efficient constructions which meet the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate approaching 1 over a fixed alphabet. The above-mentioned results bring our understanding of deletion code constructions in these regimes to a similar level as worst case errors. [ABSTRACT FROM PUBLISHER]

We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k \ge 2 , we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1-(2/(k+\sqrt k)) . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(\sqrt 2 +1)=\sqrt 2-1 \approx 0.414 . Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1-\Theta (1/\sqrt k) , and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for $k$ -ary codes as 1-\Theta (1/k)$ , since 1-1/k$ is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question. [ABSTRACT FROM PUBLISHER]

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size $q$ , i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this paper, we present an upper bound on the minimum distance $d$ of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length $n$ , dimension $k$ , locality $r$ , availability $t$ , and field size $q$ . Then, we study the binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed–Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared with other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, the availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code. [ABSTRACT FROM PUBLISHER]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert–Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval [0,0.0668] . One of the two newly presented upper bounds improves on the best known upper bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval \tau \in (0,{1}/{8}] and meets the lower bound of {1}/{2} for \tau \geq 1/8 . Moreover, in a nonasymptotic regime, both upper bounds improve on the previously best known results on the largest size of t -grain-correcting codes of length $n$ , for certain values of n$ and t$ . Constructions of 1-grain-correcting codes based on a partitioning technique are presented for lengths up to 18. Finally, a lower bound of on the minimum redundancy of $\infty $ -grain-detecting codes of length $n$ is presented. [ABSTRACT FROM PUBLISHER]

It is shown that for some location sets and some integral multiple power Galois fields that some new general subclasses of Goppa codes may be defined which have improved lower bounds to code dimension and minimum distance compared with ordinary Goppa codes. Some previously published results are shown to be particular cases of these general subclasses of codes. A new subclass of reversible Goppa codes is also presented. Examples of code construction for these subclasses, demonstrating the improved code parameters, are presented for both non binary and binary codes. [ABSTRACT FROM AUTHOR]

We present new constructions of codes for asymmetric channels for both binary and nonbinary alphabets, based on methods of generalized code concatenation. For the binary asymmetric channel, our methods construct nonlinear single-error-correcting codes from ternary outer codes. We show that some of the Varshamov–Tenengol’ts–Constantin–Rao codes, a class of binary nonlinear codes for this channel, have a nice structure when viewed as ternary codes. In many cases, our ternary construction yields even better codes. For the nonbinary asymmetric channel, our methods construct linear codes for many lengths and distances which are superior to the linear codes of the same length capable of correcting the same number of symmetric errors. [ABSTRACT FROM AUTHOR]

We study certain combinatorial aspects of list-decoding, motivated by the exponential gap between the known upper bound (of \(O(1/\gamma )\) ) and lower bound (of \(\Omega _{p} (\log (1/\gamma ))\) ) for the list size needed to list decode up to error fraction \(p\) with rate \(\gamma \) away from capacity, i.e., \(1- h(p)-\gamma \) [here \(p\in (0, {1}/{2})\) and \(\gamma > 0\) ]. Our main result is that we prove that in any binary code \(C \subseteq \{ 0, 1 \} ^{n}\) of rate \(1- h(p) - \gamma \) , there must exist a set \( \mathcal {L}\subset C\) of \(\Omega _{p} (1/\sqrt {\gamma })\) codewords such that the average distance of the points in \( \mathcal {L}\) from their centroid is at most \(pn\) . In other words, there must exist \(\Omega _{p}(1/\sqrt {\gamma })\) codewords with low average radius. The standard notion of list decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average radius form is in itself quite natural; for instance, the classical Johnson bound in fact implies average-radius list-decodability. The remaining results concern the standard notion of list-decoding, and help clarify the current state of affairs regarding combinatorial bounds for list-decoding as follows. First, we give a short simple proof, over all fixed alphabets, of the above-mentioned \(\Omega _{p}(\log (1/\gamma ))\) lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. Second, we show that one cannot improve the \(\Omega _{p}(\log (1/\gamma ))\) lower bound via techniques based on identifying the zero-rate regime for list-decoding of constant-weight codes [this is a typical approach for negative results in coding theory, including the \(\Omega _{p} (\log (1/\gamma ))\) list-size lower bound]. On a positive note, our \(\Omega _{p}(1/\sqrt {\gamma })\) lower bound for average-radius list-decoding circumvents this barrier. Third, we exhibit a reverse connection between the existence of constant-weight and general codes for list-decoding, showing that the best possible list-size, as a function of the gap \(\gamma \) of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes (with weight bounded away from \(p\) ) and general codes. Fourth, we give simple second moment-based proofs that w.h.p. a list-size of \(\Omega _{p} (1/\gamma )\) is needed for list-decoding random codes from errors as well as erasures. For random linear codes, the corresponding list-size bounds are \(\Omega _{p} (1/\gamma )\) for errors and \(\exp (\Omega _{p}(1/\gamma ))\) for erasures. [ABSTRACT FROM AUTHOR]

A stepped-up tree encoder (SUTE) has been designed to deal with the issue of non-thermometer-to-binary (NTH2B) encoding for a 10-ps wave union FPGA TDC. The encoder is made up of two pipeline stages: pre-encoding and parallel encoding, and is capable of bubble error correction (BEC) as well. With this encoding algorithm applied in a Xilinx Virtex-4 FPGA, we achieved a NTH2B conversion rate of up to 100 MHz for more than 200-bit non-thermometer codes. [ABSTRACT FROM AUTHOR]

Recent work by Divsalar has shown that properly designed protograph-based low-density parity-check codes typically have minimum (Hamming) distance linearly increasing with block length. This fact rests on ensemble arguments over all possible expansions of the base protograph. However, when implementation complexity is considered, the expansions are frequently selected from a smaller class of structured expansions. For example, protograph expansion by cyclically shifting connections generates a quasi-cyclic (QC) code. Other recent work by Smarandache and Vontobel has provided upper bounds on the minimum distance of QC codes. In this paper, we generalize these bounds to punctured QC codes and then show how to tighten these for certain classes of codes. We then evaluate these upper bounds for the family of protograph codes known as AR4JA codes that have been recommended for use in deep space communications in a standard established by the Consultative Committee for Space Data Systems. At block lengths larger than 4400 bits, these upper bounds fall well below the ensemble lower bounds. [ABSTRACT FROM AUTHOR]

It is an important issue to search for self-orthogonal codes for construction of quantum codes by CSS construction (Calderbank-Sho-Steane codes); in quantum error correction, CSS codes are a special type of stabilizer codes constructed from classical codes with some special properties, and the CSS construction of quantum codes is a well-known construction. First, we employ hierarchical posets with two levels for construction of binary linear codes. Second, we find some necessary and sufficient conditions for these linear codes constructed using posets to be self-orthogonal, and we use these self-orthogonal codes for obtaining binary quantum codes. Finally, we obtain four infinite families of binary quantum codes for which the minimum distances are three or four by CSS construction, which include binary quantum Hamming codes with length n ≥ 7 . We also find some (almost) "optimal" quantum codes according to the current database of Grassl. Furthermore, we explicitly determine the weight distributions of these linear codes constructed using posets, and we present two infinite families of some optimal binary linear codes with respect to the Griesmer bound and a class of binary Hamming codes. [ABSTRACT FROM AUTHOR]

Noise in quantum computing is countered with quantum error correction. Achieving optimal performance will require tailoring codes and decoding algorithms to account for features of realistic noise, such as the common situation where the noise is biased towards dephasing. Here we introduce an efficient high-threshold decoder for a noise-tailored surface code based on minimum-weight perfect matching. The decoder exploits the symmetries of its syndrome under the action of biased noise and generalizes to the fault-tolerant regime where measurements are unreliable. Using this decoder, we obtain fault-tolerant thresholds in excess of 6% for a phenomenological noise model in the limit where dephasing dominates. These gains persist even for modest noise biases: we find a threshold of ~5% in an experimentally relevant regime where dephasing errors occur at a rate 100 times greater than bit-flip errors. [ABSTRACT FROM AUTHOR]