Barrier-error channels have been suggested as a model for non-binary channels that are milder than symmetric-error channels. Such channels are motivated by practical applications in data storage and communications. The barrier-error model allows errors only to (downward) and from (upward) a specific symbol within the alphabet. We study a generalization of prior barrier-error models that considers different numbers of downward and upward errors. The results of this paper include a sufficient condition for error correction, code-size upper and lower bounds, a code construction decomposing to just two constituent symmetric-error codes (prior ones used many), and a decoding algorithm that decodes the two codes jointly. The decoder is shown empirically to achieve better block error rates when compared to previous algorithms.
Barrier-error channels have been suggested as a model for non-binary channels that are milder than symmetric-error channels. Such channels are motivated by practical applications in data storage and communications. The barrier-error model allows errors only to (downward) and from (upward) a specific symbol within the alphabet. We study a generalization of prior barrier-error models that considers different numbers of downward and upward errors. The results of this paper include a sufficient condition for error correction, code-size upper and lower bounds, a code construction decomposing to just two constituent symmetric-error codes (prior ones used many), and a decoding algorithm that decodes the two codes jointly. The decoder is shown empirically to achieve better block error rates when compared to previous algorithms.
A ternary barrier channel is a non-symmetric error model defined previously to address emerging applications. Conveniently, it admits a code-construction method comprising two binary constituent codes. In this paper we propose a decoding algorithm that decodes the two constituent codes jointly by message passing on a graph representing the two codes' parity-check constraints. The messages exchanged by the algorithm are likelihoods calculated from incoming messages, and they are derived in the paper based on the exact dependence between the binary values of the two codewords. Simulation results demonstrate that the proposed decoder has superior error-rate performance compared to prior decoding approaches.
Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.
A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.
We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive and doubly transitive codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.1. We give a tight bound on the weight distribution of every transitive linear code $ C \subseteq \mathbb{F}_2^N : \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \mathsf{dim}(C)}. $2. We give a criterion that certifies that a linear code $ C $ can be decoded on the binary symmetric channel. Let $ K_s(x) $ denote the Krawtchouk polynomial of degree $ s $, and let $ C^\perp $ denote the dual code of $ C $. We show that bounds on $ \mathbb{E}_{c \in C^{\perp}}[ K_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $ C^\perp $ is sufficiently close to the binomial distribution in some interval around $ \frac{N}{2} $, $ C $ is resilient to $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.
Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, we introduce parity-check matrices yielding parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. This allows for the separation of erasures from errors to facilitate decoding. The parity-check matrices typically have redundant rows. We give several constructions of such matrices and prove general bounds on their minimum sizes.
Low-density parity-check (LDPC) codes have been known for their outstanding error-correction capabilities. With low- complexity decoding algorithms and a near capacity performance, these codes are among the most promising forward error correction schemes. LDPC decoding algorithms are generally sub-optimal and their performance not only depends on the codes, but also on many other factors, such as the code representation. In particular, a given non- binary code can be associated with a number of different field or ring image codes. Additionally, each LDPC code can be described with many different Tanner graphs. Each of these different images and graphs can possibly lead to a different performance when used with iterative decoding algorithms. Consequently, in this dissertation we try to find better representations, i.e., graphs and images, for LDPC codes. We take the first step by analyzing LDPC codes over multiple-input single-output (MISO) channels. In an n_T by 1 MISO system with a modulation of alphabet size 2M̂, each group of n_T transmitted symbols are combined and produce one received symbol at the receiver. As a result, we consider the LDPC-coded MISO system as an LDPC code over a 2̂{M n_T}-ary alphabet. We introduce a modified Tanner graph to represent MISO-LDPC systems and merge the MISO symbol detection and binary LDPC decoding steps into a single message passing decoding algorithm. We present an efficient implementation for belief propagation decoding that significantly reduces the decoding complexity. With numerical simulations, we show that belief propagation decoding over modified graphs outperforms the conventional decoding algorithm for short length LDPC codes over unknown channels. Subsequently, we continue by studying images of non-binary LDPC codes. The high complexity of belief propagation decoding has been proven to be a detrimental factor for these codes. Thereby, we suggest employing lower complexity decoding algorithms over image codes instead. We introduce three classes of binary image codes for a given non-binary code, namely: basic, mixed, and extended binary image codes. We establish upper and lower bounds on the minimum distance of these binary image codes, and present two techniques to find binary image codes with better performance under belief propagation decoding algorithm. In particular, we present a greedy algorithm to find optimized binary image codes. We then proceed by investigation of the ring image codes. Specifically, we introduce matrix-ring-image codes for a given non-binary code. We derive a belief propagation decoding algorithm for these codes, and with numerical simulations, we demonstrate that the low-complexity belief propagation decoding of optimized image codes has a performance very close to the high complexity BP decoding of the original non-binary code. Finally, in a separate study, we investigate the performance of iterative decoders over binary erasure channels. In particular, we present a novel approach to evaluate the inherent unequal error protection properties of irregular LDPC codes over binary erasure channels. Exploiting the finite length scaling methodology, that has been used to study the average bit error rate of finite-length LDPC codes, we introduce a scaling approach to approximate the bit erasure rates in the waterfall region of variable nodes with different degrees. Comparing the bit erasure rates obtained from Monte Carlo simulation with the proposed scaling approximations, we demonstrate that the scaling approach provides a close approximation for a wide range of code lengths. In view of the complexity associated with the numerical evaluation of the scaling approximation, we also derive simpler upper and lower bounds and demonstrate through numerical simulations that these bounds are very close to the scaling approximation