Search

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction $\tau \ge 1/4$ vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with $n$ transmissions that achieves a positive rate for any fraction of errors $\tau < 1$ and $n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes. [ABSTRACT FROM AUTHOR]

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

The paper presents a novel efficient encoding and decoding method for self‐correction and anti‐interference used in big data product tracing system based on the cyclic code theory. The principle of constructing code set is first illustrated. Then the specific encoding and decoding methods suitable for the algebra rules are invented in sequence for efficiency. At last, to test the new coding system, the paper accelerates the decoding time by OpenMP more than 36 times. The error‐correcting code presents its perfect recovery property with a recovery rate of more than 95% under 60% damage rate. In analyzing its efficiency, the encoding process only costs 0.0045 second in average while the time of decoding method will increase with the damage rate's ascending, but it can be controlled within 16 seconds. In comparison to other coding patterns in the references, the newly error‐correcting and anti‐interference coding method achieves a balance in complexity, encoding rate, and decoding time with its priority in recovering rate under the damage rate of 60%. [ABSTRACT FROM AUTHOR]

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

For the recently developed quasi-reversible BCH codes with long lengths and high error-correcting capability, this paper is aimed at proposing a new and faster decoding procedure. It consists of four steps: 1) compute the consecutive syndromes; 2) calculate the syndrome functions by the forward and backward recursions; 3) solve a linear subsystem together with one matrix multiplication in order to find an error-locator polynomial; 4) determine the errors from the obtained polynomial by using the root-finding algorithm. This procedure, especially in Steps 2 and 3, differs greatly from the conventional procedures, which determine an error-locator polynomial directly from solving a linear system with the aid of the consecutive syndromes. The key idea behind this decoding technique is that the computational complexity of such a small subsystem instead of an originally large linear system can be significantly reduced, although there are additional forward and backward syndrome calculations with low complexity increasing. Finally, the illustrative examples and numerical simulations can be helpful to demonstrate the accuracy and efficacy of the presented decoding technique at different error-correcting capabilities. [ABSTRACT FROM AUTHOR]

In the last three decades, several constructions of quantum error-correcting codes were presented in the literature. Among these codes, there are the asymmetric ones, i.e., quantum codes whose Z-distance d z is different from its X-distance d x . The topological quantum codes form an important class of quantum codes, where the toric code, introduced by Kitaev, was the first family of this type. After Kitaev's toric code, several authors focused attention on investigating its structure and the constructions of new families of topological quantum codes over Euclidean and hyperbolic surfaces. As a consequence of establishing the existence and the construction of asymmetric topological quantum codes in Theorem 5.1, the main result of this paper, we introduce the class of hyperbolic asymmetric codes. Hence, families of Euclidean and hyperbolic asymmetric topological quantum codes are presented. An analysis regarding the asymptotic behavior of their distances d x and d z and encoding rates k/n versus the compact orientable surface's genus is provided due to the significant difference between the asymmetric distances d x and d z when compared with the corresponding parameters of topological codes generated by other tessellations. This inherent unequal error protection is associated with the nontrivial homological cycle of the { r , s } tessellation and its dual, which may be appropriately explored depending on the application, where r ≠ s and (r - 2) (s - 2) ≥ 4 . Three families of codes derived from the { 7 , 3 } , { 5 , 4 } , and { 10 , 5 } tessellations are highlighted. [ABSTRACT FROM AUTHOR]

Let $q=p^{e}$ be a prime power and $\ell $ be an integer with $0\leq \ell \leq e-1$. The $\ell $ -Galois hull of classical linear codes is a generalization of the Euclidean hull and Hermitian hull. We provide a necessary and sufficient condition under which a codeword of a GRS code or an extended GRS code belongs to its $\ell $ -Galois dual code, generalizing both the Euclidean case and Hermitian case in the literature. By using four different tools: 1) the norm mapping from $\mathbb {F}_{q}^{\ast }$ to $\mathbb {F}_{p^{\ell }}^{\ast }$ ; 2) the direct product of two cyclic subgroups; 3) the coset decomposition of a cyclic group; 4) an additive subgroup of $\mathbb {F}_{q}$ and its cosets, we construct eleven families of $q$ -ary MDS codes with $\ell $ -Galois hulls of arbitrary dimensions, and give the related eleven families of $[[n,k,d;c]]_{q}$ entanglement-assisted quantum error-correcting codes (EAQECCs) with relatively large minimum distance in the sense that $2d=n-k+2+c$. We show that developing the theory on $\ell $ -Galois hulls of $q$ -ary MDS codes in this paper enables us to obtain new $q$ -ary EAQECCs with different kinds of length sets via different $\ell $ , where $2\ell \mid e$. [ABSTRACT FROM AUTHOR]

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

The study of constant-weight codes in $\ell _{1}$ -metric was motivated by the duplication-correcting problem for data storage in live DNA. It is interesting to determine the maximum size of a code given the length ${n}$ , weight ${w}$ , minimum distance ${d}$ and the alphabet size ${q}$. In this paper, based on graph decompositions, we determine the maximum size of ternary codes with constant weight w and distance $2{w}-2$ for all sufficiently large length ${n}$. Previously, this was known only for a very sparse family ${n}$ of density $4/{w}({w}-1)$. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with m > 2 strings (where a previous paper considered m = 2) in asymptotic terms, where code-words are taken from an error-correcting code. Thus, we find the trade-off between the design minimum distance, the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease coding redundancy, or the required number of reads, or both. [ABSTRACT FROM AUTHOR]

This paper proposes multilevel Reed–Solomon (MRS) codes and their iterative multistage soft decoding (IMSD) for visible light communication (VLC), realizing both high decoding performance and transmission spectrum efficiency. The proposed IMSD algorithm decodes the MRS codes level-by-level through iterating either hard decisions or extrinsic information of RS coded bits. Each level RS decoding is realized by cascading the adaptive belief propagation (ABP) algorithm that produces the extrinsic information and the Berlekamp–Massey (BM) algorithm that estimates the codeword. The earlier level decoding provides better a priori information for the later ones. A complexity reducing IMSD (CR-IMSD) algorithm is also proposed to facilitate the decoding. This paper further investigates a joint design of color-shift keying (CSK) constellation and the MRS code, optimizing the decoding performance. The CSK constellation is designed by considering both the set partitioning (SP) criterion and the harmonic mean of constellation’s minimum squared Euclidean distance (MSED). The MRS codes are further designed using the capacity and the equal error probability rules. Our simulation results show that the IMSD algorithm achieves significant iterative decoding gains. The performance of the designed MRS code is 0.3 dB away from the capacity limit at the bit error rate (BER) of 10−9. [ABSTRACT FROM AUTHOR]

This paper introduces a high rate error-correcting coding scheme called symmetric block-wise concatenated Bose–Chaudhuri–Hocquenghem (symmetric BC-BCH) codes tailored for storage devices with hard-decision outputs, e.g., storage devices based on NAND flash memory. It will be shown that a careful integration of the symmetry and 2-D block-wise concatenation is especially beneficial to achieve improvements of error-rate performance when an iterative hard-decision-based decoding (IHDD) is assumed. The claim is substantiated by proving that the proposed symmetric concatenation is optimal in terms of error-rate performance in the low error-rate regime over other 2-D block-wise concatenations. Besides, this paper proposes a novel way to design constituent codes, which enables us to enjoy advantages of primitive BCH codes and to efficiently break stopping sets associated with the IHDD in the low error-rate regime. We consider error-control systems made up of a symmetric BC-BCH code, the IHDD, and simple auxiliary decoders specifically targeting to break stopping sets caused in the IHDD. It will be shown that the auxiliary decoders significantly improve error-rate performance at a negligible amount of extra complexity. Performance comparisons are also carried out between error-control systems with the proposed and other coding schemes such as BCH codes, quasi-primitive BC-BCH codes, and low-density parity-check codes. [ABSTRACT FROM AUTHOR]

Compute-and-forward (CAF) relaying is an effective way to increase bandwidth efficiency of wireless two-way relay channels. Design of error-correcting codes and their decoding algorithms suitable for CAF relaying schemes remains an important issue to be studied. In this paper, we will analyze an asymptotic behavior of LDPC codes over two-way relay channels based on density evolution (DE). Because of the asymmetric characteristics of the channel, we use the population dynamics DE combined with DE formulas for asymmetric channels to obtain the belief propagation (BP) thresholds. Additionally, we also evaluate the asymptotic performance of spatially coupled LDPC codes for two-way relay channels. The results indicate that the spatially coupled codes yield improvements in the BP threshold compared with corresponding uncoupled codes for two-way relay channels. [ABSTRACT FROM AUTHOR]

In combinatorial group testing, the primary objective is to fully identify the set of at most d defective items from a pool of n items using as few tests as possible. The celebrated result for the combinatorial group testing problem is that the number of tests, denoted by $t$ , can be made logarithmic in n when ${d} = {O}(\text {poly}(\log {n}))$. However, state-of-the-art group testing codes require the items to be tested ${w} = \Omega \left ({\frac {{d} \log {n}}{\log {d} + \log \log {n}} }\right)$ times and tests to include $\rho = \Omega \left ({\frac {{n}}{{d} \log _{{d}} {n}}}\right)$ items. In many emerging applications, items can only participate in a limited number of tests and tests are constrained to include a limited number of items. In this paper, we study the “sparse” regime for the group testing problem where we restrict the number of tests each item can participate in by ${w}_{\max }$ or the number of items each test can include by $\rho _{\max }$ in both noiseless and noisy settings. These constraints lead to a largely unexplored regime where t is a fractional power of n, rather than logarithmic in n as in the classical setting. Our results characterize the number of tests t needed in this regime as a function of ${w}_{\max }$ or $\rho _{\max }$ and show, for example, that t decreases drastically when ${w}_{\max }$ is increased beyond a bare minimum. In particular, in the noiseless case it can be shown that if ${w}_{\max } \leq {d}$ , then we must have ${t}={n}$ , i.e., testing every item individually is optimal. We show that if ${w}_{\max }={d}+1$ , the number of tests decreases suddenly from ${t}={n}$ to ${t} = \Theta ({d} \sqrt {{n}})$. The order-optimal construction is obtained via a modification of the classical Kautz-Singleton construction, which is known to be suboptimal for the classical group testing problem. For the more general case, when ${w}_{\max }={{ ld}}+1$ for integer ${l}>1$ , the modified Kautz-Singleton construction requires ${t} = \Theta \left ({{d} {n}^{\frac {1}{{l}+1}}}\right)$ tests, which we prove to be near order-optimal. We also show that our constructions have a favorable encoding and decoding complexity, i.e. they can be decoded in $({poly}({d}) + {O}({t}))$ -time and each entry in any codeword can be computed in ${poly}(\log {n})$ memory space. We finally discuss an application of our results to the construction of energy-limited random access schemes for Internet of Things networks, which provided the initial motivation for our work. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size. [ABSTRACT FROM AUTHOR]

With technology scaling, burst errors or clustered errors are becoming increasingly common in different types of memories. Multiple bit upsets due to particle strikes, write disturbance errors, and magnetic field coupling are a few of the mechanisms which cause clustered errors. In this article, a new class of single burst error correcting codes are presented which correct a single burst of any size b within a codeword. A code construction methodology is presented which enables us to construct the proposed scheme from existing codes, e.g., Hamming codes. A new single step decoding methodology for the proposed class of codes is also presented which enables faster decoding. Different code constructions using Hamming codes, and BCH codes have been presented in this paper and a comparison is made with existing schemes in terms of decoding complexity and data redundancy. The proposed scheme in all cases reduces the decoder complexity for little to no increase in data redundancy, specifically for higher burst error sizes. [ABSTRACT FROM AUTHOR]

Transmissions across asynchronous communication channels are subject to delay injection attacks, which can cause an arbitrary number of skews. That is, such attacks can cause an arbitrary number of transmitted signals to arrive after the first signal of the next transmission has arrived. The (common) assumption that despite the delays, all signals from the $i$ th transmission arrive at the decoder before any signal from the (i+2){\text{nd}} transmission arrives is called a no switch assumption. This paper presents a self-synchronizing, zero-latency, zero-error coding scheme that requires no acknowledge and can decode transmissions distorted by an arbitrary number of skews that obey this no switch assumption. The rate associated with the coding scheme provides a lower bound of 0.6942 for the (zero-error) capacity of such a channel. It is further shown that zero-error channel capacity of the channel is upper bounded by 0.7248. Finally, this paper presents bounds on the (zero-error) capacity of a channel for which the number of transmissions that can mix with one another is large. [ABSTRACT FROM AUTHOR]

The rank-modulation scheme has been recently proposed to write and store data in flash memories efficiently. In this paper, a new construction of systematic error-correcting codes for permutations is presented under the Chebyshev distance. By constructing a subgroup code and using its coset codes to partition the set of information permutations, the proposed code construction can achieve much larger code cardinality and hence higher code rates. To facilitate the encoding and decoding of the constructed codes, we also investigate the concepts of ranking and unranking for permutations, and generalize them to $M$ -ranking and $M$ -unranking for multi-permutations. Examples are provided to demonstrate the relevant concepts and the encoding/decoding algorithms. [ABSTRACT FROM AUTHOR]

Gaussian thermal loss channels are of particular importance to quantum communication theory since they model realistic optical communication channels. Except for special cases, the quantum capacity of Gaussian thermal loss channels is not yet quantified completely. In this paper, we provide improved upper bounds of the Gaussian thermal loss channel capacity, both in energy-constrained and unconstrained scenarios. We briefly review Gottesman-Kitaev-Preskill (GKP) codes and discuss their experimental implementation. We then prove, in the energy-unconstrained case, that a family of GKP codes achieves the quantum capacity of Gaussian thermal loss channels up to at most a constant gap from the improved upper bound. In the energy-constrained case, we formulate a biconvex encoding and decoding optimization problem to maximize entanglement fidelity. Then, we solve the biconvex optimization heuristically by an alternating semi-definite programming method and report that, starting from Haar random initial codes, our numerical optimization yields a hexagonal GKP code as an optimal encoding in a practically relevant regime. [ABSTRACT FROM AUTHOR]

In this paper, we present linear systematic error-correcting codes Lk and L+k which are the results of our research on the sub-exceeding functions. Given an integer k such that k ≥ 3, these two codes are re-spectively [2k, k] and [3k, k] linear codes. The minimum distance of L3 is 3 and for k ≥ 4 the minimum distance of Lk is 4. The code L+k, the minimum distances are respectively 5 and 6 for k = 4 and k ≥ 5. By calculating the complexity of the algorithms, our codes have fast and efficient decoding. Then, for a short and medium distance data transmission (wifi network, bluetooth, cable, ...), we see that the codes mentioned above present many advantages. [ABSTRACT FROM AUTHOR]

The interest in polar codes has been increasing significantly since their adoption for use in the 5th generation wireless systems standard. Successive cancellation (SC) decoding algorithm has low implementation complexity, but yields mediocre error-correction performance at the code lengths of interest. SC-Flip algorithm improves the error-correction performance of SC by identifying possibly erroneous decisions made by SC and re-iterates after flipping one bit. It was recently shown that only a portion of bit-channels are most likely to be in error. In this paper, we investigate the average log-likelihood ratio (LLR) values and their distribution related to the erroneous bit-channels, and develop the Thresholded SC-Flip (TSCF) decoding algorithm. We also replace the LLR selection and sorting of SC-Flip with a comparator to reduce the implementation complexity. Simulation results demonstrate that for practical code lengths and a wide range of rates, TSCF shows negligible loss compared with the error-correction performance obtained when all single-errors are corrected. At matching maximum iterations, TSCF has an error-correction performance gain of up to 0.45 dB compared with SC-Flip decoding. At matching error-correction performance, the computational complexity of TSCF is reduced by up to 40% on average and requires up to $5\times $ lower maximum number of iterations. [ABSTRACT FROM AUTHOR]

Adaptive network coded cooperation (ANCC) provides a general coded cooperation framework to map the communication connections of a wireless network into the coding constraint. However, random selection policy is assumed at each node to select its retrieval subset, which cannot avoid illness in code graph at the sink. In this paper, the concept of indicator matrix is proposed to regulate the retrieval subset selection to derive the enhanced ANCC (EANCC) scheme. It is unveiled that the indicator matrix based retrieval subset selection policy can effectively tailor the girth and degree characteristics of the resultant code graph. Since the most harmful short cycles in the network coded cooperation can be completely eliminated, the proposed EANCC approach promises better error performance than the existing ANCC scheme. Numerical results show that it performs 13 dB better than the ANCC scheme at the bit error rate performance of $10^{-5}$ in seven-user network over the Rayleigh block fading channel. [ABSTRACT FROM AUTHOR]

Error Correcting Output Codes (ECOC) is a successful technique in multi-class classification, which is a core problem in Pattern Recognition and Machine Learning. A major advantage of ECOC over other methods is that the multi-class problem is decoupled into a set of binary problems that are solved independently. However, literature defines a general error-correcting capability for ECOCs without analyzing how it distributes among classes, hindering a deeper analysis of pair-wise error-correction. To address these limitations this paper proposes an Error-Correcting Factorization (ECF) method. Our contribution is three fold: (I) We propose a novel representation of the error-correction capability, called the design matrix, that enables us to build an ECOC on the basis of allocating correction to pairs of classes. (II) We derive the optimal code length of an ECOC using rank properties of the design matrix. (III) ECF is formulated as a discrete optimization problem, and a relaxed solution is found using an efficient constrained block coordinate descent approach. (IV) Enabled by the flexibility introduced with the design matrix we propose to allocate the error-correction on classes that are prone to confusion. Experimental results in several databases show that when allocating the error-correction to confusable classes ECF outperforms state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

This paper presents and analyzes a novel concatenated coding scheme for enabling error resilience in two distributed storage settings: one being storage using existing regenerating codes and the second being storage using locally repairable codes. The concatenated coding scheme brings together a maximum rank distance code as an outer code and either a globally regenerating or a locally repairable code as an inner code. In addition, error resilience for combination of locally repairable codes with regenerating codes is considered. This concatenated coding system is designed to handle two different types of adversarial errors: the first type includes an adversary that can replace the content of an affected node only once; while the second type studies an adversary that is capable of polluting data an unbounded number of times. The paper establishes an upper bound on the resilience capacity for a locally repairable code. This paper also proves that the proposed concatenated coding approach attains the upper bound on the resilience capacity in the presence of the first type of adversary for both minimum storage regenerating codes and locally repairable codes. Further, this paper presents mechanisms that combine the presented concatenated coding scheme with subspace signatures to achieve error resilience for the second type of errors. [ABSTRACT FROM PUBLISHER]

This paper proposes a new concatenated error correction coding scheme for 2-D magnetic recording (TDMR). The designed concatenated coding scheme consists of outer codes as binary polar codes and an inner code as non-binary low-density parity-check (LDPC) code. These error-correcting codes (ECCs) are considered to achieve large coding gains with small bandwidth expansion in the presence of intersymbol interference and inter-track interference. Polar codes have attracted much attention as one of the ECCs that provably achieve the optimal symmetric capacity of memoryless channels with an explicit construction and are decoded by the successive-cancellation decoding algorithm, whose computational complexity is comparatively low. Using systematic polar codes, we are able to design proper low-complexity ECCs with run-length-limited constraints for any TDMR schemes based on the selection criterion (which is called channel polarization) for choosing parity and information symbols by the magnitude of the approximately calculated mutual information amount regarding each recorded symbol in a codeword. Concretely, the concatenated coding schemes are designed for four-track and three-track recording, and the block error rate (BER) performances of 2-D partial response equalized signal processing schemes with proposed concatenated ECCs for bit-patterned media recording are evaluated. As a result, it shows that the BER performances of the proposed schemes are superior to that of the conventional scheme using a 1-D high rate binary LDPC code. [ABSTRACT FROM PUBLISHER]

In this paper, new index coding problems are studied, where each receiver has erroneous side information. Although side information is a crucial part of index coding, the existence of erroneous side information has not been considered yet. We study an index code with receivers that have erroneous side information symbols in the error-free broadcast channel, which is called an index code with side information errors (ICSIE). The encoding and decoding procedures of the ICSIE are proposed, based on the syndrome decoding. Then, we derive the bounds on the optimal codelength of the proposed index code with erroneous side information. Furthermore, we introduce a special graph for the proposed index coding problem, called a \delta s -cycle whose properties are similar to those of the cycle in the conventional index coding problem. Properties of the ICSIE are also discussed in the \delta s -cycle and clique. Finally, the proposed ICSIE is generalized to an index code for the scenario having both additive channel errors and side information errors, called a generalized error correcting index code. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the concept of spatially coupled turbo-like codes (SC-TCs) as the spatial coupling of a number of turbo-like code ensembles. In particular, we consider the spatial coupling of parallel concatenated codes, introduced by Berrou et al., and that of serially concatenated codes (SCCs), introduced by Benedetto et al. Furthermore, we propose two extensions of braided convolutional codes (BCCs), and a class of turbo-like codes which have an inherent spatially coupled structure, to higher coupling memories, and show that these yield improved belief propagation (BP) thresholds as compared with the original BCC ensemble. We derive the exact density evolution (DE) equations for SC-TCs and analyze their asymptotic behavior on the binary erasure channel. We also consider the construction of families of rate-compatible SC-TC ensembles. Our numerical results show that the threshold saturation of the BP decoding threshold to the maximum a posteriori threshold of the underlying uncoupled ensembles occurs for large enough coupling memory. The improvement of the BP threshold is especially significant for SCCs and BCCs, whose uncoupled ensembles suffer from a poor BP threshold. For a wide range of code rates, SC-TCs show close-to-capacity performance as the coupling memory increases. We further give a proof of threshold saturation for SC-TC ensembles with identical component encoders. In particular, we show that the DE of SC-TC ensembles with identical component encoders can be properly rewritten as a scalar recursion. This allows us to define potential functions and prove threshold saturation using the proof technique recently introduced by Yedla et al. [ABSTRACT FROM PUBLISHER]

The ability to store data in the DNA of a living organism has applications in a variety of areas including synthetic biology and watermarking of patented genetically modified organisms. Data stored in this medium are subject to errors arising from various mutations, such as point mutations, indels, and tandem duplication, which need to be corrected to maintain data integrity. In this paper, we provide error-correcting codes for errors caused by tandem duplications, which create a copy of a block of the sequence and insert it in a tandem manner, i.e., next to the original. In particular, we present two families of codes for correcting errors due to tandem duplications of a fixed length: the first family can correct any number of errors, while the second corrects a bounded number of errors. We also study codes for correcting tandem duplications of length up to a given constant $k$ , where we are primarily focused on the cases of $k=2,3$ . Finally, we provide a full classification of the sets of lengths allowed in tandem duplication that result in a unique root for all sequences. [ABSTRACT FROM AUTHOR]

In this paper, a multiple-input–multiple-output (MIMO) system with finite-bit feedback first proposed by Love–Heath is considered, where a transmitted signal consists of a precode followed by an orthogonal space–time block code (OSTBC), such as Alamouti code. A new design criterion and a corresponding design method of precoders are proposed. Simulations show that the precoders obtained by our proposed criterion and method perform better than the existing ones. Furthermore, since our proposed precoders have a layered structure, their designs can be implemented in the simplest Grassmannian manifold. Moreover, a fast encoding algorithm can be applied, which can greatly reduce the complexity of codeword selection. In this paper, we also propose non-unitary precoders and their design criterion and method based on the performance analysis and the special property of an OSTBC. Interestingly, non-unitary precoders can significantly improve performance over unitary precoders. [ABSTRACT FROM PUBLISHER]

This paper considers the relationship between code-rate selection and queueing performance for communication systems subject to time-varying channel conditions. While error-correcting codes offer protection against channel uncertainties, there exists a natural tradeoff between the enhanced protection of low-rate codes and the rate penalty imposed by additional redundancy. In the limiting regime where codewords are asymptotically long, this tradeoff is well understood and characterized by the Shannon capacity. However, for delay-sensitive communication systems and finite block lengths, a complete characterization of this tradeoff is not fully developed. This paper offers a new perspective on the queueing performance of communication systems with finite block lengths operating over correlated erasure channels. A rigorous framework that links code rate to overall system performance for random codes is presented. Guidelines for code-rate selection in delay-sensitive systems are identified. These findings are supported by a numerical study. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an MDS code with $k$ information nodes and r=n-k$ parity nodes is used to encode data in a distributed storage system. It is known that if h$ out of the n$ nodes are inaccessible and d$ surviving (helper) nodes are used to recover the lost data, then we need to download at least h/(d+h-k)$ fraction of the data stored in each of the helper nodes (Dimakis et al., 2010 and Cadambe et al., 2013). If this lower bound is achieved for the repair of any h$ erased nodes from any d$ helper nodes, we say that the MDS code has the (h,d)$ -optimal repair property. We study high-rate MDS array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any r$ and n$ , we present two explicit constructions of MDS array codes with the (h,d) . The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field $F$ as long as $|F|\ge n+1$ . Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property. [ABSTRACT FROM PUBLISHER]

In this paper, two multifault diagnosis methods based on improved support vector machine (SVM) are proposed for sensor fault detection and identification respectively. First, online sparse least squares support vector machine (OS-LSSVM) is utilized to detect and predict sensor faults. Then, a method which combines the SVM and error-correcting output codes (ECOC) called ECOC-SVM is proposed to solve the sensor fault feature extraction and online identification problem. We regard nonlinear transformation as the input of classifiers to enhance the separability of initial characteristics. ECOC-SVM is utilized to classify the fault states. Some typical faults are investigated and the experimental results indicate that ECOC-SVM has high identification accuracy and can be implemented in real-time to meet the requirements of online fault identification. This method can also be extended to solve other related problems. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with $r$ redundancy nodes can correct any $r$ node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, $e$ erasures are a more likely failure event, for some $1 \le e < r$ . Hence, a natural question is how much information do we need to access in order to rebuild $e$ storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of $e$ erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of $1/r$ for the rebuilding of any systematic node when $e=1$ ; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any $r$ erasures can be corrected by accessing some of the remaining information, and any $e=1$ erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of $e/r$ for systematic nodes of MDS codes, for any $1 \le e \le r$ ; 2) we construct systematic codes that achieve optimal rebuilding ratio of $1/r$ , for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances. [ABSTRACT FROM AUTHOR]

Generalized integrated interleaved codes refer to two-level Reed-Solomon codes, such that each code of the nested layer belongs to different subcode of the first-layer code. In this paper, we first devise an efficient decoding algorithm by ignoring first-layer miscorrection and by intelligently reusing preceding results during each iteration of a decoding attempt. Neglecting first-layer miscorrection also enables to explicitly and neatly formulate the decoding failure probability. We next derive an erasure correcting algorithm for redundant arrays of independent disks systems. We further construct an algebraic systematic encoding algorithm, which had been open. Analogously, we propose a novel generalized integrated interleaving scheme over binary Bose-Chaudhuri–Hocquenghem codes, reveal a lower bound on the minimum distance, and derive a similar encoding and decoding algorithm as those of Reed-Solomon codes. [ABSTRACT FROM AUTHOR]

Inductive coupling is a technique wherein one device (the reader) induces an electrical current in another device (the tag), thereby providing not only power for the tag, but also a communication channel. In this paper, we focus exclusively on the reader-to-tag channel. The first part of this paper presents modulation codes that possess a high minimum and a high average power. This is important, since the tag gets its entire power from the received signal, and the information should be modulated in a way that maximizes the power transferred to the tag. The presented modulation codes compare favorably to codes used in radio frequency identification applications today. The second part of the paper describes modulation codes with some error-correcting capabilities. In fact, most errors in the reader-to-tag channel are due to incorrect timing. Here, we propose to model the timing errors in the reader-to-tag communication channel by a simple bit-shift channel, and we will present optimal (in the sense of maximizing the code rate for a given block length) single bit-shift error-correcting codes for this simple bit-shift channel that also have large average power. [ABSTRACT FROM PUBLISHER]

Error-correcting output coding (ECOC) is one of the most widely used strategies for dealing with multi-class problems by decomposing the original multi-class problem into a series of binary sub-problems. In traditional ECOC-based methods, binary classifiers corresponding to those sub-problems are usually trained separately without considering the relationships among these classifiers. However, as these classifiers are established on the same training data, there may be some inherent relationships among them. Exploiting such relationships can potentially improve the generalization performances of individual classifiers, and, thus, boost ECOC learning algorithms. In this paper, we explore to mine and utilize such relationship through a joint classifier learning method, by integrating the training of binary classifiers and the learning of the relationship among them into a unified objective function. We also develop an efficient alternating optimization algorithm to solve the objective function. To evaluate the proposed method, we perform a series of experiments on eleven datasets from the UCI machine learning repository as well as two datasets from real-world image recognition tasks. The experimental results demonstrate the efficacy of the proposed method, compared with state-of-the-art methods for ECOC-based multi-class classification. [ABSTRACT FROM PUBLISHER]

High-frame rate (HFR) video streaming is emerging as a new paradigm in popular multimedia applications (e.g., mobile cloud gaming) to achieve smooth viewing experience perceived by end users. However, it is severely challenging to guarantee the delivery quality of HFR video over wireless platforms with regard to the high transmission rate and limited network resources. Multihoming capability enables mobile devices to concurrently receive video data with different radio interfaces (e.g., cellular and Wi-Fi). To effectively deliver mobile HFR video over multiple wireless access networks, this paper develops an application-layer transmission scheme dubbed joint FRAme Scheduling and Error Resilience (FRASER). First, we propose an unequal frame scheduling approach by taking advantage of interlaced forward error correction coding and reliability-aware data allocation to minimize the total distortion. Second, we introduce an error resilience scheme at the receiver side to proactively leverage the out-of-order and overdue video packets to mitigate the error propagations. The proposed FRASER is able to substantially reduce the probability of I (Intra) frame loss and consecutive P (Predicted) frame drops. We conduct the performance evaluation through extensive emulations in Exata involving HFR video streaming encoded with H.264 codec. Evaluation results show that FRASER outperforms the reference transmission schemes in terms of video peak signal-to-noise ratio, end-to-end delay, and received frame rate. Thus, FRASER is recommended for delivering HFR video streaming to multihomed mobile devices in heterogeneous wireless networks. [ABSTRACT FROM PUBLISHER]

In this paper, we propose and analyze an unequal error protection (UEP) rateless spinal code, which can provide UEP and unequal recovery time properties. The proposed UEP spinal codes achieve UEP by the permutation of different priority levels and the setup of different segment sizes for different priority levels. In addition, an unequal length transmission scheme to improve the transmission rate is proposed, where the number of transmitted symbols in each pass varies. Moreover, we analyze the finite-length performance of the proposed UEP spinal code, which enables us to provide the upper bound of average error probability for each priority level under maximum likelihood decoding. Based on this finite-length result, we discuss the design of UEP spinal code, which is flexible and efficient. Furthermore, the asymptotic performance analysis shows that the proposed UEP spinal code with a practical decoder can achieve the capacities of both binary symmetric channel and additive white Gaussian noise channel. Simulation results verify our analysis. [ABSTRACT FROM PUBLISHER]

This paper studies the capacity of single-source single-sink noiseless networks under adversarial or arbitrary errors on no more than z edges. Unlike prior papers, which assume equal capacities on all links, arbitrary link capacities are considered. Results include new upper bounds, network error-correction coding strategies, and examples of network families where our bounds are tight. An example is provided of a network where the capacity is 50% greater than the best rate that can be achieved with linear coding. While coding at the source and sink suffices in networks with equal link capacities, in networks with unequal link capacities, it is shown that intermediate nodes may have to do coding, nonlinear error detection, or error correction in order to achieve the network error-correction capacity. [ABSTRACT FROM AUTHOR]

Recent technological advancements in wireless infrastructures and handheld devices enable mobile users to concurrently receive multimedia contents with different radio interfaces (e.g., cellular and Wi-Fi). However, multipath video transport over the resource-limited and error-prone wireless networks is challenged with key technical issues: 1) conventional multipath protocols are throughput-oriented, and video data are scheduled in a content-agnostic fashion and 2) high-quality real-time video is bandwidth-intensive and delay-sensitive. To address these critical problems, this paper proposes a bandwidth-efficient multipath streaming (BEMA) protocol featured by the priority-aware data scheduling and forward error correction-based reliable transmission. First, we present a mathematical framework to formulate the delay-constrained distortion minimization problem for concurrent video transmission over multiple wireless access networks. Second, we develop a joint Raptor coding and data distribution framework to achieve target video quality with minimum bandwidth consumption. The proposed BEMA is able to effectively mitigate packet reordering and path asymmetry to improve network utilization. We conduct performance evaluation through extensive emulations in Exata involving real-time H.264 video streaming. Compared with the existing multipath protocols, BEMA achieves appreciable improvements in terms of video peak signal-to-noise ratio, end-to-end delay, bandwidth utilization, and goodput. Therefore, BEMA is recommended for streaming high-quality real-time video to multihomed terminals in heterogeneous wireless networks. [ABSTRACT FROM AUTHOR]

This paper studies secure communication based on incremental redundancy (INR) secure hybrid automatic retransmission request (HARQ) protocol over block-fading wiretap channels. The transmitter has no instantaneous channel state information (CSI) available from either main channel or the eavesdropper channel, hence the coding rates cannot be adapted to instantaneous channel conditions. We investigate the outage performance for two schemes of INR secure HARQ protocols: case 1) when there exists two reliable multibit feedback channels from both legitimate receiver and eavesdropper to the transmitter carrying a function of outdated CSI, and case 2) when there is a multibit feedback channel only from legitimate receiver. In both cases, we demonstrate that using the information carried via multibit feedback channels, the transmitter can adapt the coding rates in order to achieve a better secrecy throughput using a smaller number of transmissions comparing to the ACK/NACK feedback channel model. For some parameters, our rate adaptation protocol achieves a strictly positive secrecy throughput whereas it is equal to zero for the protocol with ACK/NACK feedback. We show that for some set of parameters, the loss of secrecy throughput between case 1 and case 2 is very small compared to the gain provided by both protocols. [ABSTRACT FROM PUBLISHER]

To avoid data corruption, error correction codes (ECCs) are widely used to protect memories. ECCs introduce a delay penalty in accessing the data as encoding or decoding has to be performed. This limits the use of ECCs in high-speed memories. This has led to the use of simple codes such as single error correction double error detection (SEC-DED) codes. However, as technology scales multiple cell upsets (MCUs) become more common and limit the use of SEC-DED codes unless they are combined with interleaving. A similar issue occurs in some types of memories like DRAM that are typically grouped in modules composed of several devices. In those modules, the protection against a device failure rather than isolated bit errors is also desirable. In those cases, one option is to use more advanced ECCs that can correct multiple bit errors. The main challenge is that those codes should minimize the delay and area penalty. Among the codes that have been considered for memory protection are Reed-Solomon (RS) codes. These codes are based on non-binary symbols and therefore can correct multiple bit errors. In this paper, single symbol error correction codes based on Reed-Solomon codes that can be implemented with low delay are proposed and evaluated. The results show that they can be implemented with a substantially lower delay than traditional single error correction RS codes. [ABSTRACT FROM PUBLISHER]

We consider the task of communicating a data stream—a long, possibly infinite message not known in advance to the sender—over a channel with adversarial noise. For any given noise rate $c<1$ , we show an efficient, constant-rate scheme that correctly decodes a $(1-c)$ fraction of the stream sent so far with high probability, or aborts if the noise rate exceeds $c$ . In addition, we prove that no constant-rate scheme can recover more than a $(1-c)$ fraction of the stream sent so far with non-negligible probability, which makes our scheme optimal in that aspect. The parties are assumed to preshare a random string unknown to the channel. Our techniques can also be applied to the task of interactive communication (two-way communication) over a noisy channel. In a recent paper (Braverman and Rao, STOC11), the possibility of two-party interactive communication as long as the noise level is $< 1/4$ was shown. By allowing the parties to preshare some private random string, we extend this result and construct a (nonefficient) constant-rate interactive protocol that succeeds with overwhelming probability against noise rates up to $1/2$ . We complete this result by proving that no constant-rate protocol can withstand noise rates $> 1/2$ . [ABSTRACT FROM PUBLISHER]

As technology scales, the protection of Finite State Machines' (FSMs) states against single event upset (SEU) and multiple bit upsets (MBUs) becomes more difficult. In this paper, a self-checking approach to enhance the SEU/MBUs immunity of FSMs' states by replicating One-Hot code M times for state encoding is presented. This approach can correct less than M bit-flip faults in the state register per cycle. Bit-flips are treated as random events and modeled by applying Poisson distribution. Two characteristics of this approach are obtained through probability analysis: first, this approach performs better with the increase of M, whereas worse when an FSM contains more states; second, this approach can offer more enhanced reliability than Binary or One-Hot state encoding with Triple Modular Redundancy (TMR). The former characteristic leads to the further improvement of this approach which is called state-reforming. The reliabilities of this proposed approach and its state-reformed solutions, as well as One \mathchar"702D Hot +TMR are all evaluated through simulations of fault injections. [ABSTRACT FROM PUBLISHER]

This paper proposes for single carrier signaling a simple structure that combines turbo equalization and decoding of correlated sources in multipath-rich multiuser Rayleigh fading multiple access channels (MAC), where the correlation between the sources is exploited by vertical iterations (VI) between the decoders. The bit-flipping model with a flipping probability pe is used to express the correlation ρ between the sources as ρ = 1-2pe. The proposed simple structure, spatially concatenated codes (SpCC), can achieve turbo-like performance over MAC channels suffering from severe inter-symbol interference (ISI), even though it uses short memory convolutional codes. First of all, to achieve turbo-like performance we introduce VIs to exploit the knowledge about the source correlation by exchanging extrinsic log-likelihood ratio (LLR) between the two decoders. We then add a rate-1 doped accumulator (D-ACC) to flexibly adapt for the variation of correlations between the sources. The results of computer simulations and extrinsic information transfer (EXIT) analysis confirm that in multipath-rich environments the proposed structure can achieve excellent performances, 1.02-1.28 dB away from the Slepian-Wolf-Shannon limit, at 1% outage probability for 0 <; ρ ≤ 1. [ABSTRACT FROM PUBLISHER]

The corruption of compressed video bitstreams during their transmission over error-prone communication channels leads to degradation in the visual quality at the decoder. In order to effectively conceal the corrupted video data an exact error detection scheme is of utmost importance. In this paper, we present a new error detection scheme for the H.264/AVC using the RD optimized motion vector constraints to improve the error detection rate. The simulation results show that the detection rate of the proposed algorithm is about 86%, although the proposed scheme brings about a small amount of bitrate increment and causes a slight decrement in the PSNR during the encoding. [ABSTRACT FROM PUBLISHER]

The original design of standard digital fountain codes assumes that the coded information symbols are equally important. In many applications, some source symbols are more important than others, and they must be recovered prior to the rest. Unequal error protection (UEP) designs are attractive solutions for such source transmissions. In this paper, we introduce a more generalized design for the first universal fountain code design, Luby transform (LT) codes, that make it particularly suited for progressive bit stream transmissions. We apply the generalized LT codes to a progressive source and show that it has better UEP properties than other published results in the literature. For example, using the proposed generalization, we obtained up to 1.7-dB peak signal to noise ratio gain in a progressive image transmission scenario over the two major UEP fountain code designs. [ABSTRACT FROM AUTHOR]