Linear tail-biting trellises: Characteristic generators and the BCJR-construction

Heide Gluesing-Luerssen; Elizabeth A. Weaver

doi:10.1109/TIT.2010.2094850

Linear tail-biting trellises: Characteristic generators and the BCJR-construction

Heide Gluesing-Luerssen, Elizabeth A. Weaver

Mathematics

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

This paper investigates the constructions of tail-biting trellises for linear block codes as introduced by Koetter and Vardy (2003) and Nori and Shankar (2006). For a given code, the sets of characteristic generators are defined slightly more generally than by Koetter and Vardy. In particular, they are not uniquely determined by the code. The effect of the choice of characteristic generators on the resulting product trellises, called KV-trellises, is discussed in detail. It is shown that each KV-trellis is a span-based BCJR-trellis and that the latter are always nonmergeable. Finally, a duality conjecture posed by Koetter and Vardy is addressed by making use of a dualization technique of BCJR-trellises. The conjecture is proven for minimal trellises.

Original language	English
Article number	5695113
Pages (from-to)	738-751
Number of pages	14
Journal	IEEE Transactions on Information Theory
Volume	57
Issue number	2
DOIs	https://doi.org/10.1109/TIT.2010.2094850
State	Published - Feb 2011

Bibliographical note

Funding Information:
Manuscript received April 01, 2010; revised September 10, 2010; accepted September 20, 2010. Date of current version January 19, 2011. The work of H. Gluesing-Luerssen was supported in part by the National Science Foundation Grant DMS-0908379. The material in this paper was presented at the IEEE Information Theory Workshop (ITW 2010), Dublin, Ireland, August 2010.

Funding

Manuscript received April 01, 2010; revised September 10, 2010; accepted September 20, 2010. Date of current version January 19, 2011. The work of H. Gluesing-Luerssen was supported in part by the National Science Foundation Grant DMS-0908379. The material in this paper was presented at the IEEE Information Theory Workshop (ITW 2010), Dublin, Ireland, August 2010.

Funders	Funder number
National Science Foundation (NSF)	DMS-0908379
Directorate for Mathematical and Physical Sciences	0908379

Keywords

Characteristic generators
linear block codes
minimal trellises
tail-biting BCJR-trellises
tail-biting trellises

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2010.2094850

Cite this

@article{4239d5ccebb14cdc913832dab512e0e3,

title = "Linear tail-biting trellises: Characteristic generators and the BCJR-construction",

abstract = "This paper investigates the constructions of tail-biting trellises for linear block codes as introduced by Koetter and Vardy (2003) and Nori and Shankar (2006). For a given code, the sets of characteristic generators are defined slightly more generally than by Koetter and Vardy. In particular, they are not uniquely determined by the code. The effect of the choice of characteristic generators on the resulting product trellises, called KV-trellises, is discussed in detail. It is shown that each KV-trellis is a span-based BCJR-trellis and that the latter are always nonmergeable. Finally, a duality conjecture posed by Koetter and Vardy is addressed by making use of a dualization technique of BCJR-trellises. The conjecture is proven for minimal trellises.",

keywords = "Characteristic generators, linear block codes, minimal trellises, tail-biting BCJR-trellises, tail-biting trellises",

author = "Heide Gluesing-Luerssen and Weaver, {Elizabeth A.}",

note = "Funding Information: Manuscript received April 01, 2010; revised September 10, 2010; accepted September 20, 2010. Date of current version January 19, 2011. The work of H. Gluesing-Luerssen was supported in part by the National Science Foundation Grant DMS-0908379. The material in this paper was presented at the IEEE Information Theory Workshop (ITW 2010), Dublin, Ireland, August 2010.",

year = "2011",

month = feb,

doi = "10.1109/TIT.2010.2094850",

language = "English",

volume = "57",

pages = "738--751",

number = "2",

}

TY - JOUR

T1 - Linear tail-biting trellises

T2 - Characteristic generators and the BCJR-construction

AU - Gluesing-Luerssen, Heide

AU - Weaver, Elizabeth A.

N1 - Funding Information: Manuscript received April 01, 2010; revised September 10, 2010; accepted September 20, 2010. Date of current version January 19, 2011. The work of H. Gluesing-Luerssen was supported in part by the National Science Foundation Grant DMS-0908379. The material in this paper was presented at the IEEE Information Theory Workshop (ITW 2010), Dublin, Ireland, August 2010.

PY - 2011/2

Y1 - 2011/2

N2 - This paper investigates the constructions of tail-biting trellises for linear block codes as introduced by Koetter and Vardy (2003) and Nori and Shankar (2006). For a given code, the sets of characteristic generators are defined slightly more generally than by Koetter and Vardy. In particular, they are not uniquely determined by the code. The effect of the choice of characteristic generators on the resulting product trellises, called KV-trellises, is discussed in detail. It is shown that each KV-trellis is a span-based BCJR-trellis and that the latter are always nonmergeable. Finally, a duality conjecture posed by Koetter and Vardy is addressed by making use of a dualization technique of BCJR-trellises. The conjecture is proven for minimal trellises.

AB - This paper investigates the constructions of tail-biting trellises for linear block codes as introduced by Koetter and Vardy (2003) and Nori and Shankar (2006). For a given code, the sets of characteristic generators are defined slightly more generally than by Koetter and Vardy. In particular, they are not uniquely determined by the code. The effect of the choice of characteristic generators on the resulting product trellises, called KV-trellises, is discussed in detail. It is shown that each KV-trellis is a span-based BCJR-trellis and that the latter are always nonmergeable. Finally, a duality conjecture posed by Koetter and Vardy is addressed by making use of a dualization technique of BCJR-trellises. The conjecture is proven for minimal trellises.

KW - Characteristic generators

KW - linear block codes

KW - minimal trellises

KW - tail-biting BCJR-trellises

KW - tail-biting trellises

UR - http://www.scopus.com/inward/record.url?scp=79251492670&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79251492670&partnerID=8YFLogxK

U2 - 10.1109/TIT.2010.2094850

DO - 10.1109/TIT.2010.2094850

M3 - Article

AN - SCOPUS:79251492670

SN - 0018-9448

VL - 57

SP - 738

EP - 751

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 2

M1 - 5695113

ER -

Linear tail-biting trellises: Characteristic generators and the BCJR-construction

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this