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]

The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo $r$. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to construct pliable fractional repetition (FR) codes that are locally recoverable for distributed storage systems (DSSs). FR codes are integral in constructing a class of distributed storage codes with exact repair by transfer. Pliable FR codes are a new type of FR codes in which both the per-node storage and repetition degree can easily be adjusted simultaneously; thus, pliable FR codes are vital for DSSs in which parameters can dynamically change over time. However, the constructions of pliable FR codes with repair locality remain unknown. In addition, the tradeoffs between the code minimum distance of an FR code and its repair locality are not fully understood. To address these problems, this paper first presents general results regarding FR codes. Subsequently, this paper presents an improved Singleton-like bound for locally recoverable FR codes under an additional requirement that each node must be part of a local structure that, upon failure, allows it to be exactly recovered by a simple download process. Moreover, this paper proposes a construction of locally recoverable FR codes that can achieve the proposed Singleton-like bound; this construction is based on bipartite graphs with a given girth. In particular, this paper also proposes a general bipartite-graph-based approach to constructing optimal pliable FR codes with and without repair localities; in this approach, a new family of bipartite graphs, called matching-feasible graphs, is introduced. Finally, this paper proposes the explicit constructions of optimal pliable FR codes by using a family of matching-feasible graphs with arbitrary large girth. Notably, in addition to attaining a Singleton-like bound for FR codes, the explicit pliable FR codes are optimal locally recoverable FR codes from two perspectives of repair locality. The explicit pliable FR codes can also be used as FR batch codes to provide load balancing in DSSs. [ABSTRACT FROM AUTHOR]

The construction of a quasi-cyclic low density parity-check (QC-LDPC) matrix is usually carried out in two steps. In the first step, a prototype matrix is defined according to certain criteria (size, girth, check and variable node degrees, and so on). The second step involves the expansion of the prototype matrix. During this last phase, an integer value is assigned to each non-null position in the prototype matrix corresponding to the right-rotation of the identity matrix. The problem of determining these integer values is complex. The state-of-the-art solutions use either some mathematical constructions to guarantee a given girth of the final QC-LDPC code, or a random search of values until the target girth is satisfied. In this paper, we propose an alternative/complementary method that reduces the search space by defining large equivalence classes of topologically identical matrices through row and column permutations using additive, structural, and multiplicative transformations. Selecting only a single element per equivalence class can reduce the search space by a few orders of magnitude. Then, we use the formalism of constraint programming to list the exhaustive sets of solutions for a given girth and a given expansion factor. An example is presented in all sections of the paper to illustrate the methodology. [ABSTRACT FROM AUTHOR]

In this paper, we study two families of codes with availability, namely, private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter imposes this property for each multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_{P}(n,k)$ and $r_{B}(n,k)$ , for PIR codes and batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$ , $r_{P}(n,k) = \Theta (\sqrt {n})$ and $r_{B}(n,k)= {\mathcal{ O}}(\sqrt {n}\log (n))$. In this paper, we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=\Theta (n^\epsilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1 and show that for all $\epsilon < 1$ , $r_{P}(n,n^\epsilon) = o(n)$ and $r_{B}(n,n^\epsilon) = o(n)$. Furthermore, several more results are proved for the case of fixed $k$. [ABSTRACT FROM AUTHOR]

Due to the emergence of extremely high density memory along with the growing number of embedded memories, memory yield is an important issue. Memory self-repair using redundancies to increase the yield of memories is widely used. Because high density memories are vulnerable to soft errors, memory error correction code (ECC) plays an important role in memory design. In this paper, methods to exploit spare columns including replaced defective columns are proposed to improve memory ECC. To utilize replaced defective columns, the defect information needs to be stored. Two approaches to store defect information are proposed—one is to use a spare column and the other is to use a content-addressable-memory. Experimental results show that the proposed method can significantly enhance the ECC performance. [ABSTRACT FROM AUTHOR]

The Euclidean hull of a linear code $C$ is the intersection of $C$ with its Euclidean dual $C^\perp $. The hull with low dimensions gets much interest due to its crucial role in determining the complexity of algorithms for computing the automorphism group of a linear code and for checking permutation equivalence of two linear codes. The Euclidean hull of a linear code has been applied to the so-called entanglement-assisted quantum error-correcting codes (EAQECCs) via classical error-correcting codes. In this paper, we firstly consider linear codes with one-dimensional Euclidean hull from algebraic geometry codes, and then present a general method to construct linear codes with arbitrary dimensional Euclidean hull. Some new EAQECCs are presented. [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]

Cache vulnerability due to soft errors is one of the reliability concerns in embedded systems. Dynamic reconfiguration techniques are widely studied for improving cache energy without considering the implications of cache vulnerability. Maintaining a useful data longer in the cache can be beneficial for energy improvement due to reduction in miss rates, however, longer data retention negatively impacts the vulnerability due to soft errors. This paper studies the tradeoff between energy efficiency improvement and reduction in cache vulnerability during cache reconfiguration. We propose a heuristic approach for both intertask and intratask cache reconfiguration in multitasking systems. Experimental results demonstrate that our proposed approach can significantly improve both vulnerability (25% on average) and energy efficiency (21% on average) for data cache without violating real-time constraints. [ABSTRACT FROM AUTHOR]

This paper considers a low-complexity iterative linear minimum mean square error (LMMSE) multiuser detector for the multiple-input and multiple-output system with nonorthogonal multiple access (MIMO-NOMA), where multiple single-antenna users simultaneously communicate with a multiple-antenna base station (BS). While LMMSE being a linear detector has a low complexity, it has suboptimal performance in multiuser detection scenario due to the mismatch between LMMSE detection and multiuser decoding. Therefore, in this paper, we provide the matching conditions between the detector and decoders for MIMO-NOMA, which are then used to derive the achievable rate of the iterative detection. We prove that a matched iterative LMMSE detector can achieve the optimal capacity of symmetric MIMO-NOMA with any number of users, the optimal sum capacity of asymmetric MIMO-NOMA with any number of users, all the maximal extreme points in the capacity region of asymmetric MIMO-NOMA with any number of users, and all points in the capacity region of two-user and three-user asymmetric MIMO-NOMA systems. In addition, a kind of practical low-complexity error-correcting multiuser code, called irregular repeat-accumulate code, is designed to match the LMMSE detector. Numerical results shows that the bit error rate performance of the proposed iterative LMMSE detection outperforms the state-of-art methods and is within 0.8 dB from the associated capacity limit. [ABSTRACT FROM AUTHOR]

Multiple cell upsets (MCU) is an issue that has to be dealt with when designing electronics for working in a radiated environment. Furthermore, the constant evolution of ICs integration density causes an increment in the MCUs span. These issues are typical in aviation applications, where, additionally, fault-tolerant (FT) performance is required. FT systems are typically based on a redundancy concept for storing and retrieving healthy information, for example, with a triple modular redundancy (TMR) scheme. The main issue with redundancy is design oversizing. On the other hand, reconfiguration-based techniques allow error scrubbing with a limited overhead. The main drawback here is overhead vulnerability to radiation, which is invalid for FT requirements. This paper proposes a new hybrid architecture that takes advantage of the optimized performance of reconfiguration-based techniques supported on extremely compressed redundant information nonvulnerable to radiation, referred to in this paper as hardwired seed bits (HSB). It also includes different known techniques, such as interleaving, error detection and correction (EDAC) algorithms, etc., for optimizing the final architecture as much as possible. As a result, the proposed approach meets FT requirements thanks to nonvulnerable tiny redundant information combined with an optimized performance through EDAC-based implementation. [ABSTRACT FROM AUTHOR]

Maximum distance profile codes over finite non-binary fields have been introduced and thoroughly studied in the last decade. These codes have the property that their column distances are maximal among all codes of the same rate and degree. In this paper, we aim at studying this fundamental concept in the context of convolutional codes over a finite ring. We extensively use the concept of $p$ -encoder to establish the theoretical framework and derive several bounds on the column distances. In particular, a method for constructing (not necessarily free) maximum distance profile convolutional codes over ${\mathbb Z}_{p^{r}}$ is presented. [ABSTRACT FROM AUTHOR]

This paper deals with Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes, which are binary codes after a Gray map from a subgroup of direct products of \mathbb Z2 , \mathbb Z4 , and Q8 , where Q8 is the quaternionic group. In a previous work, these codes were classified in five shapes. In this paper, we analyze the allowable range of values for the rank and dimension of the kernel, which depends on the particular shape of the code. We show that all these codes can be represented in a standard form, from a set of generators, which can help in understanding the characteristics of each shape. The main results we present are the characterization of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes as a quotient of a semidirect product of \mathbb Z2 \mathbb Z4 -linear codes and the construction of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes with each allowable pair of values for the rank and dimension of the kernel. [ABSTRACT FROM AUTHOR]

Information retrieval in associative memories was studied in a recent paper by Yaakobi and Bruck (2012). Associations between memory entries give us the t -neighbourhood of an entry. In their model, an information unit is retrieved from the memory with the aid of input clues, which are chosen from a reference set. In this paper, we consider the situation where the information unit is found unambiguously using the associated t -neighbourhoods of the input clues. A varying number of input clues are allowed, but a limit mu on the maximum number of them is imposed. Of course, we would like mu to be as small as possible. We consider the problem over the binary Hamming space \mathbb F^n and focus on the minimum of mu , denoted by $\nu (n;t)$ . Using linear reference sets, we show that $\nu (n;2) \leq 5$ for any $n \geq 9$ . We also give infinite families of reference sets, which provide good bounds on $\nu (n;t)$ for $t=3$ . In addition, efficient methods are given to obtain bounds on $\nu (n;t)$ for any $t$ from known reference sets. We also discuss the applications of this model to the Levenshtein’s sequence reconstruction problem and the sensor network monitoring. [ABSTRACT FROM AUTHOR]

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. [ABSTRACT FROM AUTHOR]

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the $q^\ell $ -incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the $q^\ell $ -incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all $[n,k]$ linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all $[n,nR]$ linear codes. [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]

In this paper, we study the decoding of dual-containing codes from Hermitian tower and applications to quantum codes. The contribution of this paper is threefold. First, we construct the quantum stabilizer codes from the Hermitian tower. Second, we provide a deterministic decoding algorithm with decoding radius that almost achieves the optimal decoding radius, i.e., $(1-R)/4$ , where $R$ is the rate. Last and most importantly, we present a Monte Carlo algorithm with decoding radius roughly equal to $(1-R)/3$ , which is beyond the optimal decoding radius $(1-R)/4$ . There are several features in this paper. First of all, we employ a differential for the Hermitian tower. This differential plays a crucial role for decoding. We also extend our decoding by passing to the constant field extension. This constant field extension makes the decoding work perfectly. [ABSTRACT FROM PUBLISHER]

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]

Quantum error-correcting codes play the role of suppressing noise and decoherence in quantum systems by introducing redundancy. Some strategies can be used to improve the parameters of these codes. For example, entanglement can provide a way for quantum error-correcting codes to achieve higher rates than the one obtained by means of the traditional stabilizer formalism. Such codes are called entanglement-assisted quantum error-correcting (EAQEC) codes. In this paper, we utilize algebraic geometry codes to construct several families of EAQEC codes derived from the Euclidean and the Hermitian construction. Three families constructed here consist of codes whose quantum Singleton defect is equal to zero, one, or two. We also construct families of EAQEC codes with an encoding rate exceeding the quantum Gilbert-Varshamov bound. Additionally, asymptotically good towers of linear complementary dual codes are used to obtain asymptotically good families of EAQEC codes consuming maximal entanglement. Furthermore, a simple comparison with the quantum Gilbert-Varshamov bound demonstrates that, by utilizing the proposed construction, it is possible to generate an asymptotically family of EAQEC codes that exceeds this bound. [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]

In this paper, the basic function field of an asymptotically optimal tower of function fields by Garcia and Stichtenoth is studied, where bases of one-point linear systems can be explicitly constructed. A representation of finite GF(q^2) -rational points on the associated plane curve is derived in this paper. This representation is exploited to extend the use of Horner’s loops and the mechanism of Chien search in the decoding of Reed–Solomon codes for syndrome generation and error-location search, respectively, to algebraic-geometry codes built on the plane Garcia–Stichtenoth curve. [ABSTRACT FROM AUTHOR]

Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this paper, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible with missing connections, but we find suitably defined decoding thresholds for communication systems with binary erasure channels under peeling decoding, as well as binary symmetric channels under Gallager A and B decoding. We see that decoding is robust to missing wires, as decoding thresholds degrade smoothly. Moreover, there is a stochastic facilitation effect in Gallager B decoders with missing connections. We also conduct finite-length simulations, compare the decoding sensitivity to channel noise and to missing wiring, and perform preliminary error-tolerant manufacturing yield analysis. [ABSTRACT FROM PUBLISHER]

Efficient list decoding of rank-metric codes seems more difficult compared with classical block codes although list decodability of random rank-metric codes is completely determined by Ding. For example, it was shown by Raviv and Wachter-Zeh that the list decoding radius of Gabidulin codes is the same as the unique decoding radius, i.e., half the minimum distance for some instances of parameters. On the other hand, Guruswami and Xing give an explicit construction of subcodes of Gabidulin codes, which can be list decoded up to the Singleton bound. This implies that subcodes of Gabidulin codes are good candidates for list decoding. In this paper, we confirm that, with overwhelming probability, a random subcode of a Gabidulin code can be list decoded with decoding radius far beyond half of the minimum distance. [ABSTRACT FROM PUBLISHER]

Golay complementary sequences and complementary sets have been proposed to deal with the high peak-to-average power ratio (PAPR) problem in orthogonal frequency division multiplexing (OFDM) system. The existing constructions of complementary sets based on generalized Boolean functions are limited to lengths, which are powers of two. In this paper, we propose novel constructions of binary and nonbinary complementary sets of non-power-of-two length. Regardless of whether or not the length of the complementary set is a power of two, its PAPR is still upper bounded by the size of the complementary set. Therefore, the constructed complementary sets can be applied in practical OFDM systems where the number of used subcarriers is not a power of two. In addition, while the binary Golay complementary pairs exist only for limited lengths, the constructed binary complementary sets of size 4 exist for more lengths with PAPR at most 4. [ABSTRACT FROM PUBLISHER]

This paper proposes a soft input decoding algorithm and a decoder architecture for generalized concatenated (GC) codes. The GC codes are constructed from inner nested binary Bose–Chaudhuri–Hocquenghem (BCH) codes and outer Reed–Solomon codes. In order to enable soft input decoding for the inner BCH block codes, a sequential stack decoding algorithm is used. Ordinary stack decoding of binary block codes requires the complete trellis of the code. In this paper, a representation of the block codes based on the trellises of supercodes is proposed in order to reduce the memory requirements for the representation of the BCH codes. This enables an efficient hardware implementation. The results for the decoding performance of the overall GC code are presented. Furthermore, a hardware architecture of the GC decoder is proposed. The proposed decoder is well suited for applications that require very low residual error rates. [ABSTRACT FROM PUBLISHER]

In recent years, flash memory has been widely used in embedded systems, portable devices, and high-performance storage products due to its nonvolatility, shock resistance, low power consumption, and high performance natures. To reduce the product cost, multi-level-cell (MLC) flash memory has been proposed; compared with the traditional single-level-cell (SLC) flash memory that only stores one bit of data per cell, each MLC cell can store two or more bits of data. Thus MLC can achieve a larger capacity and reduce the cost per unit. However, MLC also suffers from the degradation in both performance and reliability. In this paper, we try to enhance the reliability and reduce the product cost of flash-memory-based solid-state drive (SSD) from a totally different perspective. We propose the half-level-cell (HLC) scheme to manage and reuse the worn-out space in SSD; through our management scheme, the system can treat two bad pages as a normal page without sacrificing performance and reliability. The proposed scheme is purely on software/firmware-level, thus there is no need to change the hardware. The experiment results show that the lifetime of SSD with our proposed HLC scheme can be extended to 50.56% under the Windows workload and up to 65.45% under the multimedia workload. When we apply the HLC scheme to flash-memory cache of hybrid storage systems, the response time can be improved up to 20.57%. [ABSTRACT FROM AUTHOR]

Spatially coupled turbo-like codes (SC-TCs) have been shown to have excellent decoding thresholds due to the threshold saturation effect. Furthermore, even for moderate block lengths, the simulation results demonstrate a very good bit error rate performance in the waterfall region. In this paper, we discuss the effect of spatial coupling on the performance of TCs in the finite block-length regime. We investigate the effect of coupling on the error floor performance of SC-TCs by establishing conditions under which the spatial coupling either preserves or improves the minimum distance of TCs. This allows us to investigate the error floor performance of SC-TCs by performing a weight enumerator function analysis of the corresponding uncoupled ensembles. Our results demonstrate that the spatial coupling changes the design trade-off between the waterfall and error floor performance. Instead of optimizing the belief propagation (BP) threshold of uncoupled TCs, which in turn leads to a higher error floor, we can take advantage of the threshold saturation property of the SC-TCs. Choosing strong ensembles, characterized by good maximum-a-posteriori (MAP) thresholds and low error floors, the corresponding SC-TCs are then able to simultaneously approach capacity and achieve very low error floor. [ABSTRACT FROM AUTHOR]

In this paper, we propose a performance analysis algorithm of low density parity check-bit interleaved coded modulation (LDPC-BICM) system. First, we introduce the Gaussian mixture approximation method of the LLR messages output from the demodulator over the AWGN channel. Then, we analyze the density evolution based on these Gaussian mixture approximation LLR messages. During the analysis, the Gaussian approximation is applied to simplify the calculation. Some LDPC-BICM systems (which are adopted by ATSC3.0 standard) are used to evaluate the proposed algorithm. We also employ the actual performances and the thresholds obtained by the multi-edge type (MET) discretized density evolution algorithm as the references. The simulation results prove that our proposed algorithm can work well in most cases. Furthermore, the proposed algorithm is simpler than the MET algorithm because of the Gaussian or Gaussian mixture approximations. [ABSTRACT FROM AUTHOR]

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against side-channel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with $\sigma $ complementary dual ($\sigma $ -LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, $\sigma $ -LCD codes can also be used to construct LCP of codes. We show that for $q > 2$ , all $q$ -ary linear codes are $\sigma $ -LCD, and for every binary linear code $\mathcal C$ , the code $\{0\}\times \mathcal C$ is $\sigma $ -LCD. Furthermore, we study deeply $\sigma $ -LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of $\sigma $ -LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good $\sigma $ -LCD GQC codes. Finally, we focus on $\sigma $ -LCD abelian codes and prove that all abelian codes in a semi-simple group algebra are $\sigma $ -LCD. The results derived in this paper extend those on the classical LCD codes and show that $\sigma $ -LCD codes allow the construction of LCP of codes more easily and with more flexibility. [ABSTRACT FROM AUTHOR]

Let $p$ be a prime, $s$ be a positive integer, and $\mathcal {R}$ be a finite commutative chain ring with the characteristic as a power of $p$. For a unit $\lambda \in \mathcal {R},~\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are ideals of the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $. In this paper, we derive necessary and sufficient conditions under which the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring. When $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring, all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are known. In this paper, we establish the algebraic structures of all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ when $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a non-chain ring. We also determine the number of codewords in each of these codes. Using their algebraic structures, we obtain symbol-pair distances, Rosenbloom–Tsfasman (RT) distances, and RT weight distributions of all constacyclic codes of length $p^{s}$ over $\mathcal {R}$. Apart from this, we derive necessary and sufficient conditions under which a constacyclic code of length $p^{s}$ over $\mathcal {R}$ is maximum-distance separable with respect to the: 1) Hamming metric; 2) symbol-pair metric; and 3) RT metric. We also provide an algorithm to decode the constacyclic codes of length $p^{s}$ over $\mathcal {R}$ using the known decoding algorithms of linear codes over finite fields with respect to the Hamming, symbol-pair, and RT metrics. [ABSTRACT FROM AUTHOR]

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed–Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size $q$. Recently, it was proved through the extension of construction by Tamo and Barg that the length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al. Surprisingly, Barg et al. presented a few examples of $q$ -ary optimal locally repairable codes of small distance and locality with code length achieving roughly $q^{2}$. Very recently, it was further shown in the work of Li et al. that there exist $q$ -ary optimal locally repairable codes with the length bigger than $q+1$ and the distance proportional to $n$. Thus, it becomes an interesting and challenging problem to construct new families of $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen. [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]

This manuscript proposes three classes of codes for error correction in a storage system in which the memory cells do not have the same number of levels, i.e., a multiscale storage. The proposed codes are single multiscale-symbol error correction (SMSEC) codes and are capable of correcting any errors occurring on a single memory cell, namely a column-deleted SMSEC code, an element-compacted SMSEC code and a product SMSEC code. In the proposed codes, the codewords are divided into two partitions, the elements on the first partition are over GF(2b 1), while those on the remaining partition are over GF(2b2). This paper also gives guidelines for selection among the three SMSEC codes to meet the desired hardware overhead in the parallel decoder for realistic parameters of the partition pair, such as (b1, b2) = (4,3), (4,2) and (3,2). Moreover it is shown that the best choice for a MSS system is the SMSEC code with the shortest check bit length; if the check bit lengths of at least two codes are equal, then the use of the element-compacted SMSEC code incurs in the smallest hardware overhead. [ABSTRACT FROM PUBLISHER]

When transmitting information over a noisy channel, two approaches, dating back to Shannon’s work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper, we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with the cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this paper. The first is proving closed-form bounds on the capacity, which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained $(0,k)$ -RLL tends to 1 as $k$ grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a model of a distributed storage system that is locally recoverable from any single server failure. Unlike the usual local recovery model of codes for distributed storage, this model accounts for the fact that each server or storage node in a network is connectable to only some, and not all other, nodes. This may happen for reasons such as physical separation, inhomogeneity in storage platforms, and so forth. We estimate the storage capacity of both undirected and directed networks under this model and propose some constructive schemes. From a coding theory point of view, we show that this model is approximately dual of the well-studied index coding problem. Furthermore, in this paper, we extend the above model to handle multiple server failures. Among other results, we provide an upper bound on the minimum pairwise distance of a set of words that can be stored in a graph with the local repair guarantee. The well-known impossibility bounds on the distance of locally recoverable codes follow from our result. [ABSTRACT FROM PUBLISHER]

Optical orthogonal codes (OOCs) have applications in optical code-division multiple-access communications systems and other wideband code-division multiple environments. They can also be used to construct protocol sequences for multiuser collision channel without feedback, and constant-weight codes for error detection and correction. We have given a cyclotomic construction of several classes of (2m - 1, w, 2) OOCs recently. The purpose of this paper is to present five classes of (q - 1, w, 2) OOCs, and thus five classes of binary constant-weight cyclic codes, where q is a power of an odd prime. [ABSTRACT FROM AUTHOR]

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]

Recognition of continuous foot motions is important in robot-assisted lower limb rehabilitation, especially in prosthesis and exoskeleton design. For instance, perceiving foot motion is essential feedback for the robot controller. However, few studies have focused on perceiving multiple-degree of freedom (DOF) foot movements. This paper proposes a novel human-machine interaction (HMI) recognition wearable system for continuous multiple-DOF ankle-foot movements. The proposed system uses solely kinematic signals from inertial measurement units and multiclass support vector machines by creating error-correcting output codes. We conducted a study with multiple participants to validate the performance of the system using two strategies, a general model and a subject-specific model. The experimental results demonstrated satisfactory performance. The subject-specific approach achieved 98.45% ± 1.17% (mean ± SD) overall accuracy within a prediction time of 10.9 ms ± 1.7 ms, and the general approach achieved 85.3% ± 7.89% overall accuracy within a prediction time of 14.1 ms ± 4.5 ms. The results prove that the proposed system can more effectively recognize multiple continuous DOF foot movements than existing strategies. It can be applied to ankle-foot rehabilitation and fills the HMI high-level control demand for multiple-DOF wearable lower-limb robotics. [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]

Since discovery of Goppa geometric codes, people have been asking the question: are there different constructions of block codes from algebraic curves that give the same parameters as Goppa geometric codes. Despite of great effort by researchers, no such constructions have been found so far. Although in literature, there are many constructions of block code from algebraic curves, most of them are quite different from the one by Goppa in nature and thus they have different parameters. Some of these constructions have the same parameters as Goppa geometric codes, however it was proved that these are essentially the same codes defined by Goppa. In this paper, we solve this question for the case where the characteristic of the ground field is 2, namely, we present a different construction of block codes from algebraic curves that give the same parameters as Goppa geometric codes for the characteristic 2 case. [ABSTRACT FROM PUBLISHER]

Polar codes are the first error-correcting codes to provably achieve channel capacity, asymptotically in code length, with an explicit construction. However, under successive-cancellation decoding, polar codes require very long code lengths to compete with existing modern codes. Nonetheless, the successive cancellation algorithm enables very-low-complexity implementations in hardware, due to the regular structure exhibited by polar codes. In this paper, we present an improved architecture for successive-cancellation decoding of polar codes, making use of a novel semi-parallel, encoder-based partial-sum computation module. We also provide quantization results for realistic code length N=2^15, and explore various optimization techniques such as a chained processing element and a variable quantization scheme. This design is shown to scale to code lengths of up to N=2^21, enabled by its low logic use, low register use and simple datapaths, limited almost exclusively by the amount of available SRAM. It also supports an overlapped loading of frames, allowing full-throughput decoding with a single set of input buffers. [ABSTRACT FROM PUBLISHER]

We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded $k$ data symbols using an $(n,k)$ code with code length $n$ and dimension $k$. During storage, some of the codeword coordinates might be corrupted by errors. We aim to recover the original data by reading the corrupted codeword with a limit on the transmission bandwidth, namely, we can only download an $\alpha $ proportion of the corrupted codeword. For a given $\alpha $ , our objective is to design a code and a decoding scheme such that we can recover the original data from the largest possible number of errors. A naive scheme is to read $\alpha n$ coordinates of the codeword. This method used in conjunction with MDS codes guarantees recovery from any $\lfloor (\alpha n-k)/2\rfloor $ errors. In this paper we show that we can instead download an $\alpha $ proportion from each of the codeword’s coordinates. For a well-designed MDS code, this method can guarantee recovery from $\lfloor (n-k/\alpha)/2 \rfloor $ errors, which is $1/\alpha $ times more than the naive method, and is also the maximum number of errors that an $(n,k)$ code can correct by downloading only an $\alpha $ proportion of the codeword. We present two families of such optimal constructions and decoding schemes of which one is based on Interleaved Reed-Solomon codes and the other on Folded Reed-Solomon codes. We further show that both code constructions attain asymptotically optimal list decoding radius when downloading only a part of the corrupted codeword. We also construct an ensemble of random codes that with high probability approaches the upper bound on the number of correctable errors when the decoder downloads an $\alpha $ proportion of the corrupted codeword. [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]

A common way to protect data stored in DRAM and related memory systems is through the use of an error-correcting code such as the extended Hamming code. Traditionally, these error-correcting codes provide equal protection guarantees to all messages. In this paper, we focus on unequal message protection (UMP), in which a subset of messages is deemed as special, and is afforded additional error-correction protection while maintaining the same number of redundancy bits as the baseline code. UMP is a powerful approach when the special messages are chosen based on the knowledge of data patterns in context. Our objective is to construct deterministic, algebraic codes with guaranteed UMP properties, derive their cardinality bounds using novel combinatorial techniques, and to demonstrate their efficacy for realistic memory benchmarks. We first introduce a UMP alternative to the single-bit parity-check code, and then we generalize to a broader UMP code family, including a UMP alternative to the extended Hamming code, offering full double-error correction protection to special messages. Our UMP constructions, applied to main memory in high-performance computing applications, could lead to significant system-level benefits such as less frequent checkpoints in supercomputers and decreased risk of catastrophic failure from erroneous special messages. [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]