IEEE Transactions on Information Theory

Decoding by local optimization (Corresp.)

K. Farrell, L. Rudolph, Carlos R. P. Hartmann, L. Nielsen

Published Sep 1, 1983• 19 citations

Abstract

The maximum likelihood decoding problem for linear binary(n,k)codes is reformulated as a continuous optimization problem in ak-dimensional solid cube. We obtain a near optimum solution of this problem by use of a simple gradient local optimization algorithm. Computer simulation results are presented for the(21,11)projective geometry code and the(47,23)quadratic-residue code.

DOI: 10.1109/tit.1983.1056724

Related papers

Design of optimization techniques for soft-decision decoding of linear block codes

Ching-Cheng Shih

This dissertation deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. We present three new decoding algorithms: $MA\sp*D,\ H\sp*,$ and Directed Search. The first algorithm, $MA\sp*D,$ is an instance of Algorithm $A\sp*$ that conducts heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search through a code tree. $MA\sp*D$ takes into consideration more properties of the code and is considerably more efficient than the original $A\sp*$ decoding algorithm presented by Han, Hartmann, and Chen in 1993. The second algorithm, $H\sp*,$ is a new decoding algorithm that determines the value of every component of a minimum-cost codeword by estimating the cost of the minimum-cost codeword, which has a fixed value at one of the k most reliable, linearly independent bit positions. The suboptimal version of this algorithm is combined with other decoding algorithms to reduce the search space during the decoding process. The third algorithm, Directed Search, is designed to enhance the performance of soft-decision decoding by searching in continuous space. This approach explores the search space between a given vector and the received vector and finds the codeword closest to the received vector in the space explored. We also present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. It hybridizes $MA\sp*D,\ H\sp*,$ and Directed Search algorithms, utilizing their strengths to make the decoding more efficient. Simulation results for this hybrid algorithm are presented for the (104,52) binary-extended quadratic residue code and for the (128,64), the (256, 131), and the (256, 139) binary-extended BCH codes. This hybrid algorithm can efficiently decode the (104,52) binary extended quadratic residue code and the (128,64) code for any signal-to-noise ratio and has near-optimal to optimal performance. Previously, no practical decoder could decode these two codes with such a performance for all signal-to-noise ratio ranges.

Jan 1, 19960 citations

Performance Evaluation of Integer Optimization Decoding

柿沼, 美希, 祐一高野

This paper explores a mathematical optimization approach to error correction. Tanatmis et al. [2010] proposed an integer optimization formulation for the maximum likelihood decoding of binary linear codes. They developed a cutting plane algorithm in which valid inequalities for cutting off non-integral solutions are iteratively added to the continuous relaxation problem. By contrast, we focus on the integer optimization decoding; that is, we solve the integer optimization problem directly by using mathematical optimization software. We evaluate the computational performance of the integer optimization decoding and suggest its potential for practical use. The computational results demonstrate that in a lownoise condition, the integer optimization decoding achieved higher bit error rate performance than did the common sum-product decoding for low-density parity-check codes.

Mar 1, 20180 citations

Monotonic Optimization Based Decoding for Linear Codes

Pham Thanh Anh Khoa, T. T. SON, Hoang Duong Tuan +1 more

A new efficient method is developed for optimal maximum likelihood (ML) decoding of an arbitrary binary linear code based on data received from a Gaussian channel. The decoding algorithm is based on minimization of a difference of two monotonic objective functions subject to the 0-1 constraint of bit variables. The iterative process converges to the global optimal ML solution after a finite number of steps. The proposed algorithm's computational complexity depends on the input sequence length k which is much less than the codeword length n, especially for codes with small code rates. The viability of the developed method is verified through simulations on different coding schemes

IEEE International Conference on Acoustics Speech and Signal ProcessingAug 3, 20063 citations

On iterative soft-decision decoding of linear binary block codes and product codes

R. Lucas, Martin Bossert, Markus Breitbach

Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.

IEEE Journal on Selected Areas in CommunicationsJan 1, 1998100 citations

Mathematical Programming Approaches for Decoding of Binary Linear Codes

Akın Tanatmis

In this thesis, we aim at finding appropriate integer programming models and associated solution approaches for the maximum likelihood decoding problem of several binary linear code classes.

Jan 1, 20112 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