Characteristic generators and dualization for tail-biting trellises

Heide Gluesing-Luerssen, Elizabeth A. Weaver

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


This paper focuses on dualizing tail-biting trellises, particularly KV trellises. These trellises are based on characteristic generators, as introduced by Koetter-Vardy (2003), and may be regarded as a natural generalization of minimal conventional trellises, even though they are not necessarily minimal. Two dualization techniques will be investigated: the local dualization, introduced by Forney (2001) for general normal graphs, and a linear-algebra-based dualization tailored to the specific class of tail-biting Bahl-Cocke-Jelinek-Raviv (BCJR) trellises, introduced by Nori-Shankar (2006). It turns out that, in general, the BCJR dual is a subtrellis of the local dual, while for KV trellises these two coincide. Furthermore, making use of both the BCJR construction and the local dualization, it will be shown that for each complete set of characteristic generators of a code there exists a complete set of characteristic generators of the dual code such that their resulting KV trellises are dual to each other if paired suitably. This proves a stronger version of a conjecture formulated by Koetter-Vardy.

Original languageEnglish
Article number5967911
Pages (from-to)7418-7430
Number of pages13
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 2011

Bibliographical note

Funding Information:
Manuscript received January 18, 2011; revised June 11, 2011; accepted June 28, 2011. Date of current version November 11, 2011.The work of H. Gluesing-Luerssen was supported in part by the National Science Foundation under Grant DMS-0908379. This paper was presented in part at the 6th Workshop on Coding and Systems, Aveiro, Portugal, June 2011. The authors are with the Department of Mathematics, University of Kentucky, Lexington, KY 40506 USA (e-mail:; Communicated by N. Kashyap, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2011.2161572


  • Characteristic generators
  • KV trellises
  • dualization
  • linear block codes
  • tail-biting BCJR trellises
  • tail-biting trellises

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Characteristic generators and dualization for tail-biting trellises'. Together they form a unique fingerprint.

Cite this