International Conference on Communications

Maximum Likelihood Decoding of Codes on the Z-channel

Ángela I. Barbero, Pål Gunnar Ellingsen, Susanna Spinsante, Øyvind Ytrehus

Published Jan 1, 2006• 5 citations

Abstract

The aim of this paper is to extend some basic concepts related to the Maximum Likelihood decoding of codes on the Z-channel, which is a particular, but very important, example of an asymmetric channel. We study distance properties of linear codes over the Z-channel, in order to define a suitable metric for the implementation of a Maximum Likelihood decoder on the channel. A combinatorial expression for an approximation on the probability of incorrect Maximum Likelihood decoding is also provided, and comparisons are given to evaluate the tightness of the estimation, when a Hamming code, a Turbo code and an LDPC code are used for communicating over the Z-channel.

DOI: 10.1109/icc.2006.254911

Related papers

Maximum Likelihood Decoding of Codes on the Asymmetric Z-channel

Susanna Spinsante, Ángela I. Barbero

AbstractThe aim of this paper is to extend some basic concepts related to the MaximumLikelihood decoding of codes on the Z-channel, which is a particular, but very important,example of an asymmetric channel. We study distance properties of linear codes overthe Z-channel, in order to de ne a suitable metric for the implementation of a MaximumLikelihood decoder on the channel. A combinatorial expression for an upper bound on theprobability of incorrect Maximum Likelihood decoding is also provided, and comparisonsare given to evaluate the tightness of the bound, when a Hamming code, a Turbo codeand an LDPC code are decoded on the asymmetric channel. 1 Introduction Errors induced by communications on a noisy channel or storage medium can be reduced to anydesired level by proper encoding of the information, as long as the information rate is less thanthe capacity of the channel. This fact was shown in a landmark paper by Shannon, in 1948 [1];since that time, much work has been devoted to the problem of devising ecient encoding anddecoding methods for error control in a noisy environment.In a block-coded system, the source output u represents a k-bit message, the encoder outputc represents an n-symbol codeword, the demodulator output r represents the correspondingbinary received n-tuple and the decoder output u^ represents the k-bit estimate of the encodedmessage. The decoder must produce an estimate u^ of the information sequence u based onthe received sequence r. Equivalently, since there is a one-to-one correspondence between theinformation sequence u and the codeword c, the decoder can produce an estimate ^c of thecodeword c. Obviously, u^ = u if and only if ^c = c. The strategy adopted for choosing an

Jan 1, 20053 citations

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information TheoryJan 1, 2001157 citations

Applications of linear programming to coding theory

Nathan Axvig

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.

Jan 1, 20103 citations

To the Question of Almost Maximum-Likelihood Decoding

Mikhail Afanasev, Andrei A. Ovchinnikov

Evseev’s lemma claims that if we use the decoding by a standard array and use coset leaders having the weight not greater than Gilbert-Varshamov distance then the probability of error decoding will become not greater than the probability of error decoding of maximum-likelihood multiplied by two. However, the estimation of tightness of this bound is an open problem. In this work we perform the estimation of the accuracy of Evseev’s lemma on the example of several linear random codes by simulating them in a binary-symmetric channel.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)Jun 1, 20201 citation

Matched Metrics and Channels

Marcelo Firer, Judy L. Walker

The most common decision criteria for decoding are maximum likelihood decoding and nearest neighbor decoding. It is well-known that maximum likelihood decoding coincides with nearest neighbor decoding with respect to the Hamming metric on the binary symmetric channel. In this work we study channels and metrics for which those two criteria do and do not coincide for general codes.

arXiv:1506.03782Jun 11, 20151 citation

Analytical Bounds on Maximum-Likelihood Decoded Linear Codes with Applications to Turbo-Like Codes: An Overview

Igal Sason, Shlomo Shitz Shamai

Upper and lower bounds on the error probability of linear codes under maximum-likelihood (ML) decoding are shortly surveyed and applied to ensembles of codes on graphs. For upper bounds, focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, sphere-packing bounds, and information-theoretic bounds on the bit error probability of codes defined on graphs. A comprehensive overview is provided in a monograph by the authors which is currently in preparation.

arXiv:cs/0512074Dec 18, 20051 citation