Show simple item record

dc.contributor.advisorShankar, Priti
dc.contributor.authorKrishnan, K Murali
dc.date.accessioned2009-05-11T10:08:22Z
dc.date.accessioned2018-07-31T04:39:45Z
dc.date.available2009-05-11T10:08:22Z
dc.date.available2018-07-31T04:39:45Z
dc.date.issued2009-05-11T10:08:22Z
dc.date.submitted2007
dc.identifier.urihttps://etd.iisc.ac.in/handle/2005/487
dc.description.abstractTwo 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.en
dc.language.isoen_USen
dc.relation.ispartofseriesG21677en
dc.subjectCoding Theoryen
dc.subjectGraphs And Graphical Representationen
dc.subjectTanner Graphsen
dc.subjectTail-biting Trellisesen
dc.subjectDecodingen
dc.subjectTail-biting Trellis Decodingen
dc.subjectLDPC Codesen
dc.subjectLinear Codesen
dc.subjectLinear Block Codesen
dc.subjectStopping Distanceen
dc.subject.classificationComputer Scienceen
dc.titleComputational Problems In Codes On Graphsen
dc.typeThesisen
dc.degree.namePhDen
dc.degree.levelDoctoralen
dc.degree.disciplineFaculty of Engineeringen


Files in this item

This item appears in the following Collection(s)

Show simple item record