Search

We propose a new type of ultimate-Shannon-limit-approaching codes called spatially coupled protograph-based low-density parity-check Hadamard convolutional codes (SC-PLDPCH-CCs), which are constructed by spatially coupling PLDPC-Hadamard block codes. We develop an efficient decoding algorithm that combines pipeline decoding and layered scheduling for the decoding of SC-PLDPCH-CCs, and analyze the latency and complexity of the decoder. To estimate the decoding thresholds of SC-PLDPCH-CCs, we first propose a layered protograph extrinsic information transfer (PEXIT) algorithm to evaluate the thresholds of spatially coupled PLDPC-Hadamard terminated codes (SC-PLDPCH-TDCs) with a moderate coupling length. With the use of the proposed layered PEXIT method, we develop a genetic algorithm to find good SC-PLDPCH-TDCs in a systematic way. Then we extend the coupling length of these SC-PLDPCH-TDCs to form good SC-PLDPCH-CCs. Results show that our constructed SC-PLDPCH-CCs can achieve comparable thresholds to the block code counterparts. Simulations illustrate the superiority of the SC-PLDPCH-CCs over the block code counterparts and other state-of-the-art low-rate codes in terms of error performance. For the rate-0.00295 SC-PLDPCH-CC, a bit error rate of 10−5 is achieved at $E_{b}/N_{0} = -1.465$ dB, which is only 0.125 dB from the ultimate Shannon limit. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes have recently regained some interest in the context of low latency communications and due to their relation to polar codes. RM codes can be constructed based on the Plotkin construction. In this work, we consider concatenated codes based on the Plotkin construction, where extended Bose-Chaudhuri-Hocquenghem (BCH) codes are used as component codes. This leads to improved code parameters compared to RM codes. Moreover, this construction is more flexible concerning the attainable code rates. Additionally, new soft-input decoding algorithms are proposed that exploit the recursive structure of the concatenation and the cyclic structure of the component codes. First, we consider the decoding of the cyclic component codes and propose a low complexity hybrid ordered statistics decoding algorithm. Next, this algorithm is applied to list decoding of the Plotkin construction. The proposed list decoding approach achieves near-maximum-likelihood performance for codes with medium lengths. The performance is comparable to state-of-the-art decoders, whereas the complexity is reduced. [ABSTRACT FROM AUTHOR]

The prefixed Varshamov-Tenengolts (VT) codes, which are subsets of VT codes with predetermined prefixes, can be used for error correction over segmented edit channels. In this paper, we investigate the construction and analysis of this class of codes. First, we derive upper bounds on the size of zero-error codes for segmented edit channels with segment-by-segment decoding. Second, we establish a one-to-one correspondence between prefixed VT codes and Levenshtein codes. Based on this relation, we can obtain explicit formulas on the size of prefixed VT codes via the existing results on the size of Levenshtein codes. Third, we construct a new zero-error prefixed VT code and show that the size of the constructed code is strictly larger than that of the existing prefixed VT code for the segmented deletion channel. Finally, an efficient systematic encoding method of prefixed VT codes is proposed for the segmented edit channels. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new method to design low-density parity-check Hadamard (LDPC-Hadamard) codes — a type of ultimate-Shannon-limit approaching channel codes. The technique is based on applying Hadamard constraints to the check nodes in a generalized protograph-based LDPC code, followed by lifting the generalized protograph. We name the codes formed protograph-based LDPC Hadamard (PLDPC-Hadamard) codes. We also propose a modified Protograph Extrinsic Information Transfer (PEXIT) algorithm for analyzing and optimizing PLDPC-Hadamard code designs. The proposed algorithm further allows the analysis of PLDPC-Hadamard codes with degree- 1 and/or punctured nodes. We find codes with decoding thresholds ranging from −1.53 dB to −1.42 dB. At a BER of 10−5, the gaps of our codes to the ultimate-Shannon-limit range from 0.40 dB (for rate = 0.0494) to 0.16 dB (for rate = 0.003). Moreover, the error performance of our codes is comparable to that of the traditional LDPC-Hadamard codes. Finally, the BER performances of our codes after puncturing are simulated and compared. [ABSTRACT FROM AUTHOR]

This work studies the design of MET-LDPC code ensembles at low code rates with good threshold performances and exponentially few small weight codewords. There was a notable study on the condition, so called the ‘t-value condition’, for exponentially few small weight codewords. Meanwhile, it was shown that by introducing degree-one variable nodes, the threshold performances of MET-LDPC code ensembles of low rates can be significantly improved. However, the degree-one variable nodes may result in small weight codewords and thus must be carefully introduced to MET-LDPC code ensembles. Despite the importance, the existing t-value condition was developed only for MET-LDPC code ensembles without degree-one variable nodes. This work extends the t-value condition to MET-LDPC code ensembles with degree-one variable nodes, which includes the existing work as a special case. The extended t-value condition provides useful insights into the contributions of degree-one variable nodes to the distribution of small weight codewords. Thus, the results of this work allow us to design MET-LDPC code ensembles of low rates with both good threshold performances and exponentially few small weight codewords. In addition, it will be demonstrated that MET-LDPC codes at finite lengths based on the designed code ensembles have good error-rate performances both in the waterfall and low-error-rate regions. [ABSTRACT FROM AUTHOR]

Linear nested codes, where two or more sub-codes are nested in a global code, have been proposed as candidates for reliable multi-terminal communication. In this article, we consider nested array-based spatially coupled low-density parity-check (SC-LDPC) codes and propose a line-counting based optimization scheme for minimizing the number of dominant absorbing sets in order to improve its performance in the high signal-to-noise ratio regime. Since the parity-check matrices of different nested sub-codes partially overlap, the optimization of one nested sub-code imposes constraints on the optimization of the other sub-codes. To tackle these constraints, a multi-step optimization process is applied first to one of the nested codes, then sequential optimization of the remaining nested codes is carried out based on the constraints imposed by the previously optimized sub-codes. Results show that the order of optimization has a significant impact on the number of dominant absorbing sets in the Tanner graph of the code, resulting in a trade-off between the performance of a nested code structure and its optimization sequence: the code which is optimized without constraints has fewer harmful structures than the code which is optimized with constraints. We also show that for certain code parameters, dominant absorbing sets in the Tanner graphs of all nested codes are completely removed using our proposed optimization strategy. [ABSTRACT FROM AUTHOR]

Resistive random-access memory (ReRAM) is a promising candidate for the next generation non-volatile memory technology due to its simple read/write operations and high storage density. However, its crossbar array structure causes a severe interference effect known as the “sneak path.” In this paper, we propose channel coding techniques that can mitigate both the sneak-path interference and the channel noise. The main challenge is that the sneak-path interference is data-dependent, and also correlated within a memory array, and hence the conventional error correction coding scheme will be inadequate. In this work, we propose an across-array coding strategy that assigns a codeword to multiple independent memory arrays, and exploit a real-time channel estimation scheme to estimate the instantaneous status of the ReRAM channel. Since the coded bits from different arrays experience independent channels, a “diversity” gain can be obtained during decoding, and when the codeword is adequately distributed over different memory arrays, the code actually performs as that over an uncorrelated channel. By performing decoding based on the scheme of treating-interference-as-noise (TIN), the ReRAM channel over different memory arrays is equivalent to a block varying channel we defined, for which we propose both the capacity bounds and a coding scheme. The proposed coding scheme consists of a serial concatenation of an optimized error correction code with a data shaper, which enables the ReRAM system to achieve a near capacity limit storage efficiency. [ABSTRACT FROM AUTHOR]

This work considers a layered coding approach for efficient transmission of data over a wireless block fading channel without transmitter channel state information (CSI), which is connected to a limited capacity reliable link, known as the bottleneck channel. Two main approaches are considered, the first is an oblivious approach, where the sampled noisy observations are compressed and transmitted over the bottleneck channel without having any knowledge of the original information codebook. The second approach is a non-oblivious decode-forward (DF) relay where the sampled noisy data is decoded, and whatever is successfully decoded is reliably transmitted over the bottleneck channel. The bottleneck channel from relay to destination has a fixed capacity $C$. We examine also the case where the channel capacity can dynamically change due to variable loads on the backhaul link. The broadcast approach is analyzed for cases that only the relay knows the available capacity for next block, and for the case that neither source nor relay know the capacity per block, only its capacity distribution. Fortunately, it is possible to analytically describe in closed form expressions, the optimal continuous layering power distribution which maximizes the average achievable rate. Numerical results demonstrate the achievable broadcast rates. [ABSTRACT FROM AUTHOR]

Iterative decoders used for decoding low-density parity-check (LDPC) and moderate-density parity-check (MDPC) codes are not characterized by a deterministic decoding radius and their error rate performance is usually assessed through intensive Monte Carlo simulations. However, several applications, like code-based cryptography, need guaranteed low values of the error rate, which are infeasible to assess through simulations, thus requiring the development of theoretical models for the error rate of these codes. Some models of this type already exist, but become computationally intractable for parameters of practical interest. Other approaches approximate the code ensemble behaviour through assumptions, which may not hold true for a specific code. We propose a theoretical analysis of the error correction capability of LDPC and MDPC codes that allows deriving tight bounds on the error rate at the output of parallel bit-flipping decoders. Special attention is devoted to the case of codes with small girth. Single-iteration decoding is investigated through a rigorous approach, which does not require any assumption and results in a guaranteed error correction capability for any single code. We show an example of application of the new bound to the context of code-based cryptography, where guaranteed error rates are needed to achieve strong security levels. [ABSTRACT FROM AUTHOR]

In this paper, a variant of the Reed–Muller code, termed symmetric Reed-Muller (SRM) code, is proposed. We show that the bivariate version of SRM code forms the best-known locally-correctable codes in certain parameter regimes. Then, the minimum distance of SRM codes is provided in certain cases. Finally, the multivariate version of SRM codes is introduced. [ABSTRACT FROM AUTHOR]

This paper proposes a novel deep learning-based error correction coding scheme for AWGN channels under the constraint of one-bit quantization in receivers. Specifically, it is first shown that the optimum error correction code that minimizes the probability of bit error can be obtained by perfectly training a special autoencoder, in which “perfectly” refers to converging the global minima. However, perfect training is not possible in most cases. To approach the performance of a perfectly trained autoencoder with a suboptimum training, we propose utilizing turbo codes as an implicit regularization, i.e., using a concatenation of a turbo code and an autoencoder. It is empirically shown that this design gives nearly the same performance as to the hypothetically perfectly trained autoencoder, and we also provide a theoretical proof of why that is so. The proposed coding method is as bandwidth efficient as the integrated (outer) turbo code, since the autoencoder exploits the excess bandwidth from pulse shaping and packs signals more intelligently thanks to sparsity in neural networks. Our results show that the proposed coding scheme at finite block lengths outperforms conventional turbo codes even for QPSK modulation. Furthermore, the proposed coding method can make one-bit quantization operational even for 16-QAM. [ABSTRACT FROM AUTHOR]

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

In this paper, we investigate an artificial-intelligence (AI) driven approach to design error correction codes (ECC). Classic error-correction code design based upon coding-theoretic principles typically strives to optimize some performance-related code property such as minimum Hamming distance, decoding threshold, or subchannel reliability ordering. In contrast, AI-driven approaches, such as reinforcement learning (RL) and genetic algorithms, rely primarily on optimization methods to learn the parameters of an optimal code within a certain code family. We employ a constructor-evaluator framework, in which the code constructor can be realized by various AI algorithms and the code evaluator provides code performance metric measurements. The code constructor keeps improving the code construction to maximize code performance that is evaluated by the code evaluator. As examples, we focus on RL and genetic algorithms to construct linear block codes and polar codes. The results show that comparable code performance can be achieved with respect to the existing codes. It is noteworthy that our method can provide superior performances to classic constructions in certain cases (e.g., list decoding for polar codes). [ABSTRACT FROM AUTHOR]

This paper analyzes and explicitly constructs quasi-cyclic (QC) codes for correcting multiple bursts via matrix transformations. Our analysis demonstrates that the multiple-burst-correction capability of QC codes is determined by sub-matrices in the diagonal of their transformed parity-check matrices. By well designing these sub-matrices, the proposed QC codes are able to achieve optimal or asymptotically optimal multiple-burst-correction capability. Moreover, it proves that these codes can be QC low-density parity-check (QC-LDPC) codes, if the diagonal sub-matrices of their transformed parity-check matrices are Hadamard powers of base matrices. Analysis and simulation results show that our QC-LDPC codes perform well over not only random symbol error/erasure channels, but also burst channels. [ABSTRACT FROM AUTHOR]

This paper presents a new construction of error correcting codes which achieves optimal recovery of a streaming source over a packet erasure channel. The channel model considered is the sliding-window erasure model, with burst and arbitrary losses, introduced by Badr et al. We present a simple construction, when the rate of the code is at least 1/2, which achieves optimal error correction in this setup. Our proposed construction is explicit and systematic. It uses off-the-shelf maximum distance separable (MDS) codes and maximum rank distance (MRD) Gabidulin block codes as constituent codes and combines them in a simple manner. This is in contrast to other recent works, where the construction involves a careful design of the generator or parity check matrix from first principles. The field size requirement which depends on the constituent MDS and MRD codes is also analyzed. [ABSTRACT FROM AUTHOR]

A linear network (LN) code can be described by either global encoding kernels (GEKs) or local encoding kernels (LEKs). In the literature, the multicast property of an LN code is described using GEKs, so the design algorithms for multicast LN codes employ GEKs to check this property. In this paper, a criterion is developed so that LEKs rather than GEKs can be used to check the multicast maximum distance separable (MDS) property of linear network error correction (LNEC) codes on erroneous networks. Further, it is used to develop a design algorithm for multicast MDS LNEC codes on erroneous cyclic networks. This algorithm is more efficient than the algorithm that uses GEKs when the number of edges is high and the interconnection of these edges is low. [ABSTRACT FROM AUTHOR]

In coded caching, a single server is connected to a set of users through a shared bottleneck link, which is assumed to be error free. During non-peak hours, all the users fill their local cache with portions of the files available. During the delivery phase, each user requests a file and the server delivers coded transmissions to meet the demands. In this paper, the links between the server and the users are assumed to be error prone. Prefetching errors are also considered. A new delivery scheme is required to meet the demands of each user even after receiving a finite number of transmissions in error in the presence of erroneous portions of files in the cache. The minimum average rate and minimum peak rate for this problem are characterized. Closed form expressions for average and peak rates for a particular caching scheme, namely, symmetric batch prefetching are established when there are no prefetching errors. An optimal linear error correcting delivery scheme is proposed for coded caching problems with symmetric batch prefetching in the absence of prefetching errors. In addition to this, lower bounds are established for the optimal rate required when there are prefetching errors in symmetric batch prefetching. [ABSTRACT FROM AUTHOR]

The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code. [ABSTRACT FROM AUTHOR]

This paper concerns the construction and hardware execution of (n, n(n-1), n-1) permutation group codes (PGCs) for communication systems. Cyclic shift techniques acting on a permutation, including cyclic shift operators and their compound functions (CFs), are defined and demonstrated, then compared to other tools such as cyclic subgroups and n-dimension cyclic shift registers. A generalized finite state machine is established that can enumerate n! permutations based on complete CFs. This is a hardware-oriented algorithm that is capable of being significantly faster than all existing algorithms which we can find up to now. After this, the ideal structural features for an ordered set of n! permutations are discussed and the multiset features of (n, n(n-1), n-1)-PGCs in this ordered set are pinpointed. A simpler way of generating (n, n(n-1), n-1)-PGCs is then developed using cyclic shift techniques, where the code length n is a prime. This outperforms existing approaches using composite operation and affine transform on module-n operation. The simulation experiments in AWGN channel show that the performance on codeword error rates (WER) and signal-noise ratio (SNR) becomes better as the code length increases and the best SNR performance achieves −0.8 dB at 10−5 WER for code length n=11. [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]

Locally decodable codes and locally correctable codes (LCCs) have several important applications, such as private information retrieval, secure multiparty computation, and circuit lower bounds. Three major parameters are considered in LCCs: query complexity, message length, and codeword length. The most familiar LCCs in the regime of low query complexity are the generalized Reed–Muller (GRM) codes. However, it has not previously been determined whether there exist codes that have shorter codeword lengths than GRM codes with the same query complexity and message length. In this paper, we show that the projective Reed–Muller (PRM) codes are such LCCs for some parameters. The GRM code is specified by the alphabet size $q$ , the number of variables $m$ , and the degree $d$ , where $d\le q-2$. When $d= q-2$ and $q-1$ is a power of a prime, we prove that there exists a PRM code with shorter codeword length than the GRM code with the same query complexity and message length. We also present for these PRM codes a perfectly smooth local decoder to recover a symbol in a codeword by accessing not more than $q$ symbols at the coordinates of the codeword. [ABSTRACT FROM AUTHOR]

In recent years, communicating information using molecules via diffusion has attracted significant interest in bio-medical applications. To date, most of the studies have concentrated on point-to-point molecular communication (MC), whereas in a realistic environment, multiple MC transmitters are likely to transmit molecular messages simultaneously sharing the same propagation medium, resulting in significant performance variation of the MC system. In this type of large-scale MC system, the collective signal strength at the desired receiver can be impaired by the interference caused by other MC transmitters, which may degrade the system reliability and efficiency. This paper presents the first tractable analytical framework for the collective signal strength at a partially absorbing receiver due to the desired transmitter under the impact of a swarm of interfering transmitters in a 3D large-scale MC system using stochastic geometry. To combat the multi-user interference and the intersymbol interference (ISI) in the multi-user environment, we propose Reed–Solomon (RS) error correction coding, due to its high effectiveness in combating burst and random errors, as well as the two types of information molecule modulating scheme, where the transmitted bits are encoded using two types of information molecules at consecutive bit intervals. We derive analytical expressions for the bit error probability (BEP) of the large-scale MC system with the proposed two schemes to show their effectiveness. The results obtained using Monte Carlo simulations, match exactly with the analytical results, justifying the accuracy of the derivations. Results reveal that both schemes improve the BEP by a factor of 3–4 compared with that of a conventional MC system without using any ISI mitigation techniques. Due to the implementation simplicity, the two-type molecule encoding scheme is better than the RS error correction coding scheme, as the RS error correction coding scheme involves additional encoding and decoding process at both the transmitter and receiver nodes. Furthermore, the proposed analytical framework can be generalized to the analysis of other types of receiver designs and performance characterization in multi-user large-scale MC systems. Also, the two types of information molecule modulating scheme can be extended to M-type of information molecule modulating scheme without loss of generality. [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]

We consider a unicast network with an adversary who is able to attack a proportion of edges, which is no more than $p$ for some 0 < p < 1 . Based on the knowledge of the adversary, three cases of attacks are considered: 1) the adversary knows nothing about the source message; 2) the adversary knows the source message but does not know the transmitted codeword; and 3) the adversary knows the transmitted codeword. Two classes of code schemes, deterministic code and stochastic code, are designed to assure reliable transmission against the adversarial attack. It is concluded that stochastic code does not provide any more benefit than the deterministic code does against the attacking cases 1 and 3. However, when the attacking case 2 is considered, stochastic code would achieve a higher capacity than the deterministic code does. [ABSTRACT FROM AUTHOR]

The index coding with side-information problem introduced by Birk and Kol has been generalized to the case, where the transmissions are subjected to errors by Dau et al.. Lower and upper bounds on the optimal number of transmissions required to correct a specified number $\delta $ of errors were established. In another generalization of index coding problem, namely, generalized index coding (GIC) problem introduced by Dai et al., linear combination of the messages can be demanded and held as side information by the receivers. Error correction for GIC problems was studied and the bounds for optimal number of transmissions required for $\delta $ -error correcting generalized index codes were established by Byrne and Calderini. In this paper, for a particular class of GIC problems construction of optimal scalar linear index codes are discussed. For this class of GIC problems, the optimal linear $\delta $ -error correcting index codes are also constructed. As special cases, optimal linear error correcting codes are obtained for two classes of original index coding problems, namely, single-prior index coding problems and single unicast index coding problems with symmetric neighboring consecutive side information. [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]

We design classes of quantum low-density parity-check (LDPC) codes, called quasi-cyclic stabilizer (QCS) codes, from conventional QC-LDPC codes. The proposed QCS codes belong to the family of non-Calderbank–Shor–Steane stabilizer codes. The QC-LDPC codes are self-orthogonal with respect to the symplectic inner product (SIP) and are constructed from submatrices of nonorthogonal Latin squares via array dispersion. The Latin squares are constructed using quadratic (non)-residue sets of prime modulus $p$ , where $p = 4n\pm 1$. For $p = 4n-1$ , two constructions, namely, Type-I-A and Type-I-B QCS codes, are proposed based on matrix superposition and matrix concatenation, respectively. For $p = 4n+1$ , Type-II QCS codes are proposed based on permutations of a base matrix. We show that the parity-check matrix for Type-I-B and Type-II QCS codes is self-orthogonal with respect to the SIP for all orders of circulant permutation matrix. This resulting in ensembles of QCS codes characterized by a single base matrix. We show that the minimum distance of Type-II QCS codes can be lower bounded by the minimum distance of the QC-LDPC codes. Simulation results show that the proposed QCS codes outperform some codes in the literature with a noteworthy low-error floor, below 10−7, over quantum depolarizing channels. [ABSTRACT FROM AUTHOR]

In this paper, the faulty successive cancellation decoding of polar codes for the binary erasure channel is studied. To this end, a simple erasure-based fault model is introduced to represent errors in the decoder, and it is shown that, under this model, polarization does not happen, meaning that fully reliable communication is not possible at any rate. Furthermore, a lower bound on the frame error rate of polar codes under faulty successive cancellation decoding is provided, which is then used, along with a well-known upper bound, in order to choose a blocklength that minimizes the erasure probability under faulty decoding. Finally, an unequal error protection scheme that can re-enable asymptotically erasure-free transmission at a small rate loss and by protecting only a constant fraction of the decoder is proposed. The same scheme is also shown to significantly improve the finite-length performance of the faulty successive cancellation decoder by protecting as little as 1.5% of the decoder. [ABSTRACT FROM AUTHOR]

This paper proposes a “quasi-synchronous” design approach for signal processing circuits, in which timing violations are permitted, but without the need for a hardware compensation mechanism. The case of a low-density parity-check (LDPC) decoder is studied, and a method for accurately modeling the effect of timing violations at a high level of abstraction is presented. The error-correction performance of code ensembles is then evaluated using density evolution, while taking into account the effect of timing faults. Following this, several quasi-synchronous LDPC decoder circuits based on the offset min-sum algorithm are optimized, providing a 23%–40% reduction in energy consumption or energy-delay product, while achieving the same performance and occupying the same area as conventional synchronous circuits. [ABSTRACT FROM PUBLISHER]

Inter-cell interference (ICI) is a significant cause of errors in flash memories. In single-level cell (SLC) flash memory, ICI arises when 1 0 1 patterns are programmed either in the horizontal or vertical directions. Since data pages are written sequentially in horizontal wordlines, one can mitigate the effects of horizontal ICI by applying conventional constrained codes that forbid the 1 0 1 pattern. This approach does not address the problem of vertical ICI, however. In this paper, a row-by-row coding technique that eliminates vertical 1 0 1 patterns while preserving the sequential wordline programming order is presented. This scheme, though efficient, necessarily suffers a rate loss of almost 20%. We therefore propose another coding scheme, combining a weak constraint on vertical 1 0 1 patterns with a systematic error-correcting code, that can mitigate vertical ICI errors while achieving a higher overall coding rate, provided that the vertical ICI error probability is sufficiently small. Some extensions for multi-level cell (MLC) flash memory are discussed as well. [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]

We propose binary discrete parametric channel models for multi-level cell (MLC) flash memories that provide accurate error-correcting code (ECC) performance estimation by modeling the empirically observed error characteristics under program/erase cycling stress. Through a detailed empirical error characterization of 1X-nm and 2Y-nm MLC flash memory chips from two different vendors, we observe and characterize the overdispersion phenomenon in the number of bit errors per ECC frame. A well-studied channel model, such as the binary asymmetric channel model, is unable to provide accurate ECC performance estimation. Hence, we propose a channel model based on the beta-binomial probability distribution [2-beta-binomial (2-BBM) channel model], which is a good fit for the overdispersed empirical error characteristics, and show through statistical tests and simulation results for BCH, low density parity check, and polar codes, that the 2-BBM channel model provides accurate ECC performance estimation in MLC flash memories. [ABSTRACT FROM AUTHOR]

Irregular joint source and channel coding (JSCC) scheme is proposed, which we refer to as the irregular unary error correction (IrUEC) code. This code operates on the basis of a single irregular trellis, instead of employing a set of separate regular trellises, as in previous irregular trellis-based codes. Our irregular trellis is designed with consideration of the UEC free distance, which we characterize for the first time in this paper. We conceive the serial concatenation of the proposed IrUEC code with an irregular unity rate code (IrURC) code and propose a new EXtrinsic Information Transfer (EXIT) chart matching algorithm for parametrizing these codes. This facilitates the creation of a narrow EXIT tunnel at a low E_\textb/N_0 value and provides near-capacity operation. Owing to this, our scheme is found to offer a low symbol error ratio (SER), which is within 0.4 dB of the discrete-input continuous-output memoryless channel (DCMC) capacity bound in a particular practical scenario, where gray-mapped quaternary phase shift keying (QPSK) modulation is employed for transmission over an uncorrelated narrowband Rayleigh-fading channel with an effective throughput of 0.508 \,\textbit\,\texts^-1\,\textHz^-1. Furthermore, the proposed IrUEC–IrURC scheme offers a SER performance gain of 0.8 dB, compared to the best of several regular and irregular separate source and channel coding (SSCC) benchmarkers, which is achieved without any increase in transmission energy, bandwidth, transmit duration, or decoding complexity. [ABSTRACT FROM AUTHOR]

Two-dimensional (2D) cyclic codes are presented which correct any single occurrence of known 2D error patterns within a 2D array of bits. Applications for this type of codes include storage and display devices. The code construction begins with a generation of distinct syndrome sets for all targeted 2D error patterns. A method to refine the syndrome sets is then presented for making each syndrome set to contain distinct members, thereby guaranteeing full correction capability for the given list of known error patterns. Using an example construction, the effectiveness of the proposed coding approach is demonstrated versus the maximum-distance-separable (MDS) random-error-correcting code and known 2D burst-correcting codes for a 2D intersymbol interference (ISI) channel that yields a few dominant, but relatively large error patterns. [ABSTRACT FROM PUBLISHER]

This paper studies the allocation of information flows in noiseless, memoryless communication networks in the presence of omniscient Byzantine adversary. In such networks, adversary may maliciously modify some edge-flows, and legitimate users should resort to network error correction strategies to transmit data reliably. Unlike prior papers, which focused on the capacities of the networks, we consider the expense of resources used by the flow. Hereby, this paper uses an optimization problem to define the concept of minimum cost network error correction flows. We provide a necessary and sufficient condition of feasibility of the allocation problem, and derive a cut-set outer bound on the feasible region. Using this cut-set bound, we can find the minimum cost network error correction flow in some instances. Moreover, we also consider the relationship between incoming edge-flows and outgoing edge-flows of a vertex. As for the directed acyclic graphs, we propose an algorithm to allocate the network error correction flow. This algorithm is with polynomial time complexity, and proves to be optimal when recoding at intermediate nodes is forbidden. Additionally, in order to justify the necessity of recoding at intermediate nodes, we analyze the benefit of intermediate recoding. On the one hand, we construct a series of instances to prove that intermediate recoding can bring enormous benefits in some networks. On the other hand, numerical analysis shows that the benefit is modest in small random graphs. [ABSTRACT FROM PUBLISHER]

Regenerating codes provide an efficient way to recover data at failed nodes in distributed storage systems. It has been shown that regenerating codes can be designed to minimize the per-node storage (called MSR) or minimize the communication overhead for regeneration (called MBR). In this work, we propose new encoding schemes for error-correcting MSR and MBR codes that generalize our earlier results on error-correcting regenerating codes. General encoding schemes for product-matrix MSR and MBR codes are derived such that the encoder based on Reed-Solomon (RS) codes is no longer limited to the Vandermonde matrix proposed earlier. Furthermore, MSR codes and MBR codes with the least update complexity can be found. A decoding scheme is proposed that utilizes RS codes to perform data reconstruction for MSR codes. The proposed decoding scheme has better error correction capability and incurs least number of node accesses when errors are present. A new decoding scheme is also proposed for MBR codes that is more capable and can correct more error-patterns. Simulation results are presented that exhibit the superior performance of the proposed schemes. [ABSTRACT FROM PUBLISHER]

This paper investigates polynomial remainder codes with non-pairwise coprime moduli. We first consider a robust reconstruction problem for polynomials from erroneous residues when the degrees of all residue errors are assumed small, namely, the robust Chinese Remainder Theorem (CRT) for polynomials. It basically says that a polynomial can be reconstructed from its erroneous residues such that the degree of the reconstruction error is upper bounded by $\tau$ whenever the degrees of all residue errors are upper bounded by $\tau$, where a sufficient condition for $\tau$ and a reconstruction algorithm are obtained. By relaxing the constraint that all residue errors have small degrees, another robust reconstruction is then presented when there are multiple unrestricted errors and an arbitrary number of errors with small degrees in the residues. We finally obtain a stronger residue error correction capability in the sense that apart from the number of errors that can be corrected in the previous existing result, some errors with small degrees can be also corrected in the residues. With this newly obtained result, improvements in uncorrected error probability and burst error correction capability in data transmission are illustrated. [ABSTRACT FROM PUBLISHER]

In this work, we consider high-rate error-control systems for storage devices using multi-level per cell (MLC) NAND flash memories. Aiming at achieving a strong error-correcting capability, we propose error-control systems using block-wise parallel/serial concatenations of short Bose-Chaudhuri-Hocquenghem (BCH) codes with two iterative decoding strategies, namely, iterative hard-decision decoding (IHDD) and iterative reliability based decoding (IRBD). It will be shown that a simple but very efficient IRBD is possible by taking advantage of a unique feature of the block-wise concatenation. For tractable performance analysis and design of IHDD and IRBD at very low error rates, we derive semi-analytic approaches. The proposed error-control systems are compared with various error-control systems with well-known coding schemes such as a product code, multiple BCH codes, a single long BCH code, and low-density parity-check codes in terms of page error rates, which confirms our claim: the proposed error-control systems achieve good tradeoffs between error-performance and complexity as compared to the traditional schemes and is also very favorable for implementation. [ABSTRACT FROM PUBLISHER]

A new class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding. [ABSTRACT FROM PUBLISHER]

In this paper we propose a novel low-complexity Joint Source and Channel Code (JSCC), which we refer to as the Elias Gamma Error Correction (EGEC) code. Like the recently-proposed Unary Error Correction (UEC) code, this facilitates the practical near-capacity transmission of symbol values that are randomly selected from a set having an infinite cardinality, such as the set of all positive integers. However, in contrast to the UEC code, our EGEC code is a universal code, facilitating the transmission of symbol values that are randomly selected using any monotonic probability distribution. When the source symbols obey a particular zeta probability distribution, our EGEC scheme is shown to offer a 3.4 dB gain over a UEC benchmarker, when Quaternary Phase Shift Keying (QPSK) modulation is employed for transmission over an uncorrelated narrowband Rayleigh fading channel. In the case of another zeta probability distribution, our EGEC scheme offers a 1.9 dB gain over a Separate Source and Channel Coding (SSCC) benchmarker. [ABSTRACT FROM PUBLISHER]

Recently, we introduced a new class of finite alphabet iterative decoders (FAIDs) for low-density parity-check (LDPC) codes. These decoders are capable of surpassing belief propagation (BP) in the error floor region on the binary symmetric channel (BSC) with much lower complexity. In this paper, we introduce a novel scheme with the objective of guaranteeing the correction of a given and potentially large number of errors on column-weight-three LDPC codes. The proposed scheme uses a plurality of FAIDs which collectively correct more error patterns than a single FAID on a given code. The collection of FAIDs utilized by the scheme is judiciously chosen to ensure that individual decoders have different decoding dynamics and correct different error patterns. Consequently, they can collectively correct a diverse set of error patterns, which is referred to as decoder diversity. We provide a systematic method to generate the set of FAIDs for decoder diversity on a given code based on the knowledge of the most harmful trapping sets present in the code. Using the well-known column-weight-three (155,64) Tanner code with dmin = 20 as an example, we describe the method in detail and show, by means of exhaustive simulation, that the guaranteed error correction capability on short length LDPC codes can be significantly increased with decoder diversity. [ABSTRACT FROM AUTHOR]

Low-rate non-binary low-density parity-check (LDPC) codes for coherent and blockwise non-coherent additive white Gaussian noise (AWGN) channels are developed. The proposed construction is based on the concatenation of non-binary outer LDPC codes with inner binary codes. In case the binary codes are chosen to be Hadamard or Reed-Muller (RM) codes, the complexity of the decoding scheme is considerably reduced. An asymptotic analysis of the concatenation with help of composite capacity considerations anddensity evolution (DE) is provided, from which guidelines on the choice of both inner and outer codes are devised. Finite length designs presented in this work confirm the excellent performance of the proposed codes. [ABSTRACT FROM AUTHOR]

A joint source-channel coding problem that combines the efficient compression of discrete memoryless sources with their reliable communication over memoryless channels via binary prefix-free variable-length error-correcting codes (VLECs) is considered. Under a fixed free distance constraint, a priority-first search algorithm is devised for finding an optimal VLEC with minimal average codeword length. Two variations of the priority-first-search-based code construction algorithm are also provided. The first one improves the resilience of the developed codes against channel noise by additionally considering a performance parameter B_dfree without sacrificing optimality in average codeword length. In the second variation, to accommodate a large free distance constraint as well as a large source alphabet such as the 26-symbol English data source, the VLEC construction algorithm is modified with the objective of significantly reducing its search complexity while still yielding near-optimal codes. A low-complexity sequence maximum a posteriori (MAP) decoder for all VLECs (including our constructed optimal code) is then proposed under the premise that the receiver knows the number of codewords being transmitted. Simulations show that the realized optimal and suboptimal VLECs compare favorably with existing codes in the literature in terms of coding efficiency, search complexity and error rate performance. [ABSTRACT FROM AUTHOR]

A novel Joint Source and Channel Code (JSCC)} is proposed, which we refer to as the Unary Error Correction (UEC) code. Unlike existing JSCCs, ourUEC facilitates the practical encoding of symbol values that are selected from a set having an infinite cardinality. Conventionally, these symbols are conveyed using Separate Source and Channel Codes (SSCCs), but we demonstrate that the residual redundancy that is retained following source coding results in capacity loss. This loss is found to have a value of 1.11 dB in a particular practical scenario, where Quaternary Phase Shift Keying (QPSK) modulation is employed for transmission over an uncorrelated narrowband Rayleigh fading channel. By contrast, the proposed UEC code can eliminate this capacity loss, or reduce it to an infinitesimally small value. Furthermore, the UEC code has only a moderate complexity, facilitating its employment in practical low-complexity applications. [ABSTRACT FROM AUTHOR]

In distributed rateless coding, multiple disjoint sources need to deliver their rateless coded symbols (where a symbol may contain a single bit or thousands of bits) to a common destination via a single relay. In this paper, we propose and design novel distributed rateless codes called DU-rateless codes that can provide Unequal Error Protection (UEP) for disjoint sources with unequal data lengths on erasure channels. To design DU-rateless codes, we tune the coding parameters at each source and propose to smartly combine the encoded symbols at the relay. We analyze DU-rateless codes employing And-Or tree analysis technique and leverage our analysis to design several sets of codes for various setups employing the-state-of-the-art multi-objective genetic algorithms. We evaluate the performance of the designed codes using numerical simulations and discuss their advantages. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm for joint carrier phase estimation and turbo decoding for the case of rapidly varying carrier phase during the transmitted block. The proposed algorithm shows improved performance over previously proposed communication schemes, both coherent and noncoherent, for channels with additive white Gaussian noise and high carrier phase noise. The novel algorithm utilizes a modified ‘two dimensional’ bit carrier phase a posteriori probability (BCAPP) decoder containing additional states representing the received carrier phase. The BCAPP decoder calculates two extrinsic metrics: one representing the bit soft value and the other representing the received carrier phase probability density function approximation. A modified structure of the turbo code iterations is suggested, implementing separate propagation of the two metrics between the BCAPP decoders. One additional attractive property of the suggested algorithm is its robustness against phase noise model mismatch. [ABSTRACT FROM AUTHOR]

This paper describes a concatenated code method where the outer decoder hypothesizes possible block symbol values for the inner code to make a likelihood retest from its original soft information. These hypotheses come from low density check sets where the probability is significant that there is only one error in the check set, whose value would be the syndrome for that check. The method has an advantage over pure verifications in converting errors into erasures. Also, it is shown that, if the inner decoder can supply a list of two decisions for each symbol, the decoding method, for large first choice symbol error probability p, allows reliable communication at rates substantially exceeding the (1-p) log 2Q QSC per symbol channel capacity with b-bit symbols. [ABSTRACT FROM AUTHOR]

In this paper, we provide the performance analysis of unequal error protection (UEP) random linear coding (RLC) strategies designed for transmission of source messages containing packets of different importance over lossy packet erasure links. By introducing the probabilistic encoding framework, we first derive the general performance limits for the packet-level UEP coding strategies that encode the packets of each importance class of the source message independently (non-overlapping windowing strategy) or jointly (expanding windowing strategy). Then, we demonstrate that the general performance limits of both strategies are achievable by the probabilistic encoding over non-overlapping and expanding windows based on RLC and the Gaussian Elimination (GE) decoding. Throughout the paper, we present a number of examples that investigate the performance and optimization of code design parameters of the expanding window RLC strategy and compare it with the non-overlapping RLC strategy selected as a reference. [ABSTRACT FROM AUTHOR]

A novel implicitly-exhaustive search algorithm for finding, in systematic form, rate R=\frac12 optimal-span Convolutional Self-Doubly Orthogonal (CDO) codes and Simplified Convolutional Self-Doubly Orthogonal (S-CDO) codes is presented. In order to build high-performance low-latency codecs with these codes, it is important to minimize their constraint length (or "span") for a given J number of generator connections. The proposed algorithm is exhaustive in nature and its improvements over the best previously published searching techniques allowed it to yield new optimal-span CDO/S-CDO codes (having order J ∈ 6,7,8 and J ∈ 9 respectively), as well as a span reduction for codes with a higher J value (J ∈ 10,11 and J ∈ 14,15 for CDO and S-CDO respectively). [ABSTRACT FROM AUTHOR]

When a telecommunication system is constrained in terms of delay and complexity, it is usually wise to allow some cross-layer cooperation between the source and channel layers. In this context, the success of joint source-channel turbo techniques has been attested several times in the literature, in particular to transmit variable length code (VLC) streams which are very sensitive to error propagation. Capitalizing on previously developed performance upper bounds, this paper investigates whether the VLC can contribute to the interleaving gain of concatenated codes just as a convolutional code with non-catastrophic encoder would. To this end, the important concept of bounded VLC spectrum is introduced and is proved to be a sufficient condition for the VLC to contribute indeed to the interleaving gain. This concept is also proved to be closely related to non-catastrophic VLCs and, under certain assumptions, to the well known concept of statistically synchronizable VLCs. [ABSTRACT FROM PUBLISHER]