Advanced

On the Construction and Analysis of Iteratively Decodable Codes

Truhachev, Dmitri LU (2004)
Abstract
Iterative decoding methods allow efficient decoding of long codes that are composed of smaller component codes. As a result reliable communication can be achieved with low decoding complexity even for rates close to Shannon capacity. This makes iteratively decodable codes a very attractive object of study in modern coding theory.



This thesis focuses on different kinds of cycles which appear in the matrices specifying the interconnection between the component codes. It is shown that the possibility to manipulate the cycle structure of these matrices is a key to the construction of good codes. A method to construct low-density parity-check matrices and permutation matrices without undesired cycles is developed. It is... (More)
Iterative decoding methods allow efficient decoding of long codes that are composed of smaller component codes. As a result reliable communication can be achieved with low decoding complexity even for rates close to Shannon capacity. This makes iteratively decodable codes a very attractive object of study in modern coding theory.



This thesis focuses on different kinds of cycles which appear in the matrices specifying the interconnection between the component codes. It is shown that the possibility to manipulate the cycle structure of these matrices is a key to the construction of good codes. A method to construct low-density parity-check matrices and permutation matrices without undesired cycles is developed. It is inspired by Gallager's construction of low-density parity-check matrices without short cycles. The construction method is applied to obtain low-density parity-check codes and turbo codes for which a given number of correct decoding iterations can be performed. Such codes are used for deriving bounds on the asymptotic performance of iterative decoding.



Moreover, the construction of matrices without undesired cycles is used to obtain iteratively decodable codes with good distance properties. Turbo codes with minimum distance logarithmically increasing with the block length are constructed. This growth rate is asymptotically optimal for this code family. Additionally, a strategy for the design of turbo codes with practical block lengths is proposed. Furthermore, serially concatenated convolutional codes with good tradeoff between length and minimum distance are constructed where the minimum distance can be flexibly attuned to the length.



In addition to the component code interconnection the performance of the component codes themselves is also investigated. Time-invariant convolutional codes are studied for transmission over the binary symmetric channel. New upper bounds on the burst and bit error probabilities for maximum-likelihood decoding are proposed. For memory two encoders, closed form expressions for the exact bit error probability are derived.



Finally, a new class of iteratively decodable codes operating on continuous data streams, braided block codes, is introduced. For the proposed codes, bounds on the free distance are derived and decoding performance is analyzed. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Professor Fuja, Thomas E., USA.
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Computer science, minimum distance, cycles, asymptotic performance, turbo codes, iterative decoding, low-density parity-check codes, numerical analysis, systems, control, Datalogi, numerisk analys, system, kontroll
pages
177 pages
publisher
Department of Information Technology, Lund Univeristy
defense location
Room E:1406, E-building, Lund Institute of Technology.
defense date
2004-06-10 10:15
external identifiers
  • other:ISRN: LUTEDX/TEIT-04/1027-SE
ISBN
91-7167-030-0
language
English
LU publication?
yes
id
fbd4e973-e464-4f45-ac78-b8825a03a4ff (old id 27620)
date added to LUP
2007-06-08 10:39:10
date last changed
2016-09-19 08:45:06
@phdthesis{fbd4e973-e464-4f45-ac78-b8825a03a4ff,
  abstract     = {Iterative decoding methods allow efficient decoding of long codes that are composed of smaller component codes. As a result reliable communication can be achieved with low decoding complexity even for rates close to Shannon capacity. This makes iteratively decodable codes a very attractive object of study in modern coding theory.<br/><br>
<br/><br>
This thesis focuses on different kinds of cycles which appear in the matrices specifying the interconnection between the component codes. It is shown that the possibility to manipulate the cycle structure of these matrices is a key to the construction of good codes. A method to construct low-density parity-check matrices and permutation matrices without undesired cycles is developed. It is inspired by Gallager's construction of low-density parity-check matrices without short cycles. The construction method is applied to obtain low-density parity-check codes and turbo codes for which a given number of correct decoding iterations can be performed. Such codes are used for deriving bounds on the asymptotic performance of iterative decoding.<br/><br>
<br/><br>
Moreover, the construction of matrices without undesired cycles is used to obtain iteratively decodable codes with good distance properties. Turbo codes with minimum distance logarithmically increasing with the block length are constructed. This growth rate is asymptotically optimal for this code family. Additionally, a strategy for the design of turbo codes with practical block lengths is proposed. Furthermore, serially concatenated convolutional codes with good tradeoff between length and minimum distance are constructed where the minimum distance can be flexibly attuned to the length.<br/><br>
<br/><br>
In addition to the component code interconnection the performance of the component codes themselves is also investigated. Time-invariant convolutional codes are studied for transmission over the binary symmetric channel. New upper bounds on the burst and bit error probabilities for maximum-likelihood decoding are proposed. For memory two encoders, closed form expressions for the exact bit error probability are derived.<br/><br>
<br/><br>
Finally, a new class of iteratively decodable codes operating on continuous data streams, braided block codes, is introduced. For the proposed codes, bounds on the free distance are derived and decoding performance is analyzed.},
  author       = {Truhachev, Dmitri},
  isbn         = {91-7167-030-0},
  keyword      = {Computer science,minimum distance,cycles,asymptotic performance,turbo codes,iterative decoding,low-density parity-check codes,numerical analysis,systems,control,Datalogi,numerisk analys,system,kontroll},
  language     = {eng},
  pages        = {177},
  publisher    = {Department of Information Technology, Lund Univeristy},
  school       = {Lund University},
  title        = {On the Construction and Analysis of Iteratively Decodable Codes},
  year         = {2004},
}