Characteristic generators and dualization for tail-biting trellises

Heide Gluesing-Luerssen; Elizabeth A. Weaver

doi:10.1109/TIT.2011.2161572

Characteristic generators and dualization for tail-biting trellises

Heide Gluesing-Luerssen, Elizabeth A. Weaver

Mathematics

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

9 Scopus citations

Abstract

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 language	English
Article number	5967911
Pages (from-to)	7418-7430
Number of pages	13
Journal	IEEE Transactions on Information Theory
Volume	57
Issue number	11
DOIs	https://doi.org/10.1109/TIT.2011.2161572
State	Published - 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: heide.gl@uky.edu; eaweaver1s@uky.edu). Communicated by N. Kashyap, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2011.2161572

Keywords

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

Access to Document

10.1109/TIT.2011.2161572

Cite this

@article{8ffa43bce6674feabfaf73920cc0bd95,

title = "Characteristic generators and dualization for tail-biting trellises",

abstract = "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.",

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

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

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: heide.gl@uky.edu; eaweaver1s@uky.edu). Communicated by N. Kashyap, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2011.2161572",

year = "2011",

month = nov,

doi = "10.1109/TIT.2011.2161572",

language = "English",

volume = "57",

pages = "7418--7430",

number = "11",

}

TY - JOUR

T1 - Characteristic generators and dualization for tail-biting trellises

AU - Gluesing-Luerssen, Heide

AU - Weaver, Elizabeth A.

N1 - 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: heide.gl@uky.edu; eaweaver1s@uky.edu). Communicated by N. Kashyap, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2011.2161572

PY - 2011/11

Y1 - 2011/11

N2 - 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.

AB - 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.

KW - Characteristic generators

KW - KV trellises

KW - dualization

KW - linear block codes

KW - tail-biting BCJR trellises

KW - tail-biting trellises

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

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

U2 - 10.1109/TIT.2011.2161572

DO - 10.1109/TIT.2011.2161572

M3 - Article

AN - SCOPUS:81255143073

VL - 57

SP - 7418

EP - 7430

IS - 11

M1 - 5967911

ER -

Characteristic generators and dualization for tail-biting trellises

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this