etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2005/487

Title:  Computational Problems In Codes On Graphs 
Authors:  Krishnan, K Murali 
Advisors:  Shankar, Priti 
Keywords:  Coding Theory Graphs And Graphical Representation Tanner Graphs Tailbiting Trellises Decoding Tailbiting Trellis Decoding LDPC Codes Linear Codes Linear Block Codes Stopping Distance 
Submitted Date:  Jul2007 
Series/Report no.:  G21677 
Abstract:  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 tailbiting trellises is presented and analyzed. Experiments indicate that the algorithm performs close to the ideal maximum likelihood decoder. 
URI:  http://hdl.handle.net/2005/487 
Appears in Collections:  Computer Science and Automation (csa)

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.
