Advanced

Tailbiting codes: Bounds and search results

Bocharova, Irina LU ; Johannesson, Rolf LU ; Kudryashov, Boris LU and Ståhl, Per LU (2002) In IEEE Transactions on Information Theory 48(1). p.137-148
Abstract
Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are... (More)
Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
asymptotic complexity bounds, state complexity, tailbiting codes, trellis, quasi-cyclic codes
in
IEEE Transactions on Information Theory
volume
48
issue
1
pages
137 - 148
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000172727300009
  • scopus:0036158357
ISSN
0018-9448
DOI
10.1109/18.971744
language
English
LU publication?
yes
id
14dc6bbd-fab6-4a14-8971-cc7d4917d933 (old id 347737)
date added to LUP
2007-08-10 11:51:01
date last changed
2017-12-10 04:31:30
@article{14dc6bbd-fab6-4a14-8971-cc7d4917d933,
  abstract     = {Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes.},
  author       = {Bocharova, Irina and Johannesson, Rolf and Kudryashov, Boris and Ståhl, Per},
  issn         = {0018-9448},
  keyword      = {asymptotic complexity bounds,state complexity,tailbiting codes,trellis,quasi-cyclic codes},
  language     = {eng},
  number       = {1},
  pages        = {137--148},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Information Theory},
  title        = {Tailbiting codes: Bounds and search results},
  url          = {http://dx.doi.org/10.1109/18.971744},
  volume       = {48},
  year         = {2002},
}