Record Details

Computational Problems In Codes On Graphs

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Computational Problems In Codes On Graphs
 
Creator Krishnan, K Murali
 
Subject Coding Theory
Graphs And Graphical Representation
Tanner Graphs
Tail-biting Trellises
Decoding
Tail-biting Trellis Decoding
LDPC Codes
Linear Codes
Linear Block Codes
Stopping Distance
Computer Science
 
Description Two standard graph representations for linear codes are the Tanner graph and the tailbiting trellis. Such graph representations allow the decoding problem for a code to be phrased as a computational problem on the corresponding graph and yield graph theoretic criteria for good codes. When a Tanner graph for a code is used for communication across a binary erasure channel (BEC) and decoding is performed using the standard iterative decoding algorithm, the maximum number of correctable erasures is determined by the stopping distance of the Tanner graph. Hence the computational problem of determining the stopping distance of a Tanner graph is of interest.
In this thesis it is shown that computing stopping distance of a Tanner graph is NP hard. It is also shown that there can be no (1 + є ) approximation algorithm for the problem for any є > 0 unless P = NP and that approximation ratio of 2(log n)1- є for any є > 0 is impossible unless NPCDTIME(npoly(log n)).
One way to construct Tanner graphs of large stopping distance is to ensure that the graph has large girth. It is known that stopping distance increases exponentially with the girth of the Tanner graph. A new elementary combinatorial construction algorithm for an almost regular LDPC code family with provable Ώ(log n) girth and O(n2) construction complexity is presented. The bound on the girth is close within a factor of two to the best known upper bound on girth.
The problem of linear time exact maximum likelihood decoding of tailbiting trellis has remained open for several years. An O(n) complexity approximate maximum likelihood decoding algorithm for tail-biting trellises is presented and analyzed. Experiments indicate that the algorithm performs close to the ideal maximum likelihood decoder.
 
Contributor Shankar, Priti
 
Date 2009-05-11T10:08:22Z
2009-05-11T10:08:22Z
2009-05-11T10:08:22Z
2007-07
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/487
 
Language en_US
 
Relation G21677