Advanced

On Tailbiting Codes from Convolutional Codes

Ståhl, Per LU (2001)
Abstract (Swedish)
Popular Abstract in Swedish

Denna avhandling behandlar en speciell typ av felrättande koder som kallas tailbitingkoder. Syftet med en felrättande kod är att korrigera fel som kan uppkomma på grund av brus och störningar då digital information överförs från sändare till mottagare.
Abstract
Tailbiting is a method to terminate convolutional codes into block codes. We call these block codes tailbiting codes. This thesis focuses on the encoding of tailbiting codes. The tailbiting method is carefully investigated. Conditions for when the tailbiting method fails are given, and methods for the proper initialization of the encoder are presented. Furthermore, the minimum distances of the tailbiting codes are investigated.



A code search for good tailbiting codes is presented. The results show that by using tailbiting we can obtain powerful binary linear block codes. We have even found codes that are better than any previously known code with the same length and dimension.



For efficient decoding of... (More)
Tailbiting is a method to terminate convolutional codes into block codes. We call these block codes tailbiting codes. This thesis focuses on the encoding of tailbiting codes. The tailbiting method is carefully investigated. Conditions for when the tailbiting method fails are given, and methods for the proper initialization of the encoder are presented. Furthermore, the minimum distances of the tailbiting codes are investigated.



A code search for good tailbiting codes is presented. The results show that by using tailbiting we can obtain powerful binary linear block codes. We have even found codes that are better than any previously known code with the same length and dimension.



For efficient decoding of block codes powerful trellis representations of block codes are often useful. We investigate tailbiting trellises of binary linear block codes and focus on the state complexity of these trellises. We derive lower bounds on the maximal and product state complexities of linear tailbiting trellises for binary linear block codes. The lower bound on the maximal state complexity is compared with the maximal state complexity of the tailbiting trellises of tailbiting codes. Since the tailbiting codes are encoded by convolutional encoders, straight-forward tailbiting trellis representations of these codes are obtained. It is shown that these trellises are efficient in terms of state complexity.



The choice of the convolutional encoder to be used when encoding a tailbiting code in a given setting is investigated. We give an explanation for the fact that, at low signal-to-noise ratios, a tailbiting code encoded by a systematic encoder results in fewer decoding bit errors than a tailbiting code encoded by a nonsystematic encoder. It is shown that the number of taps in the encoder inverse is an important parameter for the performance at low signal-to-noise ratios. We also compare tailbiting codes encoded by systematic feedback encoders and nonsystematic feedforward encoders at high signal-to-noise ratios. A code search is presented which indicates that, at high signal-to-noise ratios, for certain tailbiting lengths, systematic feedback encoders result in fewer decoding bit errors than nonsystematic feedforward ones. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Professor Kötter, Ralf, University of Illinois at Urbana-Champaign, USA
organization
publishing date
type
Thesis
publication status
published
subject
keywords
computer technology, Systems engineering, Teknik, Technological sciences, encoder inverse, systematic feedback encoder, state complexity, trellis, tailbiting termination method, tailbiting code, channel coding, convolutional code, Data- och systemvetenskap, Informatics, systems theory, Informatik, systemteori
pages
167 pages
publisher
Department of Information Technology, Lund Univeristy
defense location
E:1406, LTH
defense date
2001-12-07 13:15
external identifiers
  • Other:ISRN: LUTEDX/TEIT-01/1018-SE
ISBN
91-7167-022-X
language
English
LU publication?
yes
id
3385bfb5-7d0c-43fe-93a2-4ac6fe87c790 (old id 20092)
date added to LUP
2007-05-28 08:23:57
date last changed
2016-09-19 08:45:09
@phdthesis{3385bfb5-7d0c-43fe-93a2-4ac6fe87c790,
  abstract     = {Tailbiting is a method to terminate convolutional codes into block codes. We call these block codes tailbiting codes. This thesis focuses on the encoding of tailbiting codes. The tailbiting method is carefully investigated. Conditions for when the tailbiting method fails are given, and methods for the proper initialization of the encoder are presented. Furthermore, the minimum distances of the tailbiting codes are investigated.<br/><br>
<br/><br>
A code search for good tailbiting codes is presented. The results show that by using tailbiting we can obtain powerful binary linear block codes. We have even found codes that are better than any previously known code with the same length and dimension.<br/><br>
<br/><br>
For efficient decoding of block codes powerful trellis representations of block codes are often useful. We investigate tailbiting trellises of binary linear block codes and focus on the state complexity of these trellises. We derive lower bounds on the maximal and product state complexities of linear tailbiting trellises for binary linear block codes. The lower bound on the maximal state complexity is compared with the maximal state complexity of the tailbiting trellises of tailbiting codes. Since the tailbiting codes are encoded by convolutional encoders, straight-forward tailbiting trellis representations of these codes are obtained. It is shown that these trellises are efficient in terms of state complexity.<br/><br>
<br/><br>
The choice of the convolutional encoder to be used when encoding a tailbiting code in a given setting is investigated. We give an explanation for the fact that, at low signal-to-noise ratios, a tailbiting code encoded by a systematic encoder results in fewer decoding bit errors than a tailbiting code encoded by a nonsystematic encoder. It is shown that the number of taps in the encoder inverse is an important parameter for the performance at low signal-to-noise ratios. We also compare tailbiting codes encoded by systematic feedback encoders and nonsystematic feedforward encoders at high signal-to-noise ratios. A code search is presented which indicates that, at high signal-to-noise ratios, for certain tailbiting lengths, systematic feedback encoders result in fewer decoding bit errors than nonsystematic feedforward ones.},
  author       = {Ståhl, Per},
  isbn         = {91-7167-022-X},
  keyword      = {computer technology,Systems engineering,Teknik,Technological sciences,encoder inverse,systematic feedback encoder,state complexity,trellis,tailbiting termination method,tailbiting code,channel coding,convolutional code,Data- och systemvetenskap,Informatics,systems theory,Informatik,systemteori},
  language     = {eng},
  pages        = {167},
  publisher    = {Department of Information Technology, Lund Univeristy},
  school       = {Lund University},
  title        = {On Tailbiting Codes from Convolutional Codes},
  year         = {2001},
}