Matrix theory for minimal trellises

Research output: Contribution to journalArticle

Abstract

Trellises provide a graphical representation for the row space of a matrix. The product construction of Kschischang and Sorokine builds minimal conventional trellises from matrices in minimal span form. Koetter and Vardy showed that minimal tail-biting trellises can be obtained by applying the product construction to submatrices of a characteristic matrix. We introduce the unique reduced minimal span form of a matrix and we obtain an expression for the unique reduced characteristic matrix. Among new properties of characteristic matrices we prove that characteristic matrices are in duality if and only if they have orthogonal column spaces, and that the transpose of a characteristic matrix is again a characteristic matrix if and only if the characteristic matrix is reduced. These properties have clear interpretations for the unwrapped unit memory convolutional code of a tail-biting trellis, they explain the duality for the class of Koetter and Vardy trellises, and they give a natural relation between the characteristic matrix based Koetter–Vardy construction and the displacement matrix based Nori–Shankar construction. For a pair of reduced characteristic matrices in duality, one is lexicographically first in a forward direction and the other is lexicographically first in the reverse direction. This confirms a conjecture by Koetter and Vardy after taking into account the different directions for the lexicographical ordering.

Original languageEnglish (US)
Pages (from-to)2507-2536
Number of pages30
JournalDesigns, Codes, and Cryptography
Volume87
Issue number11
DOIs
StatePublished - Nov 1 2019

Fingerprint

Matrix Theory
Convolutional codes
Duality
Data storage equipment
Tail
Row space
Column space
If and only if
Convolutional Codes
Transpose
Graphical Representation
Reverse

Keywords

  • Characteristic generator
  • Koetter and Vardy conjecture
  • Linear block code
  • Minimal trellis
  • Tail-biting trellis

ASJC Scopus subject areas

  • Computer Science Applications
  • Applied Mathematics

Cite this

Matrix theory for minimal trellises. / Duursma, Iwan M.

In: Designs, Codes, and Cryptography, Vol. 87, No. 11, 01.11.2019, p. 2507-2536.

Research output: Contribution to journalArticle

@article{74358eb2a29b400d80f9fdc1980bb189,
title = "Matrix theory for minimal trellises",
abstract = "Trellises provide a graphical representation for the row space of a matrix. The product construction of Kschischang and Sorokine builds minimal conventional trellises from matrices in minimal span form. Koetter and Vardy showed that minimal tail-biting trellises can be obtained by applying the product construction to submatrices of a characteristic matrix. We introduce the unique reduced minimal span form of a matrix and we obtain an expression for the unique reduced characteristic matrix. Among new properties of characteristic matrices we prove that characteristic matrices are in duality if and only if they have orthogonal column spaces, and that the transpose of a characteristic matrix is again a characteristic matrix if and only if the characteristic matrix is reduced. These properties have clear interpretations for the unwrapped unit memory convolutional code of a tail-biting trellis, they explain the duality for the class of Koetter and Vardy trellises, and they give a natural relation between the characteristic matrix based Koetter–Vardy construction and the displacement matrix based Nori–Shankar construction. For a pair of reduced characteristic matrices in duality, one is lexicographically first in a forward direction and the other is lexicographically first in the reverse direction. This confirms a conjecture by Koetter and Vardy after taking into account the different directions for the lexicographical ordering.",
keywords = "Characteristic generator, Koetter and Vardy conjecture, Linear block code, Minimal trellis, Tail-biting trellis",
author = "Duursma, {Iwan M}",
year = "2019",
month = "11",
day = "1",
doi = "10.1007/s10623-019-00627-8",
language = "English (US)",
volume = "87",
pages = "2507--2536",
journal = "Designs, Codes, and Cryptography",
issn = "0925-1022",
publisher = "Springer Netherlands",
number = "11",

}

TY - JOUR

T1 - Matrix theory for minimal trellises

AU - Duursma, Iwan M

PY - 2019/11/1

Y1 - 2019/11/1

N2 - Trellises provide a graphical representation for the row space of a matrix. The product construction of Kschischang and Sorokine builds minimal conventional trellises from matrices in minimal span form. Koetter and Vardy showed that minimal tail-biting trellises can be obtained by applying the product construction to submatrices of a characteristic matrix. We introduce the unique reduced minimal span form of a matrix and we obtain an expression for the unique reduced characteristic matrix. Among new properties of characteristic matrices we prove that characteristic matrices are in duality if and only if they have orthogonal column spaces, and that the transpose of a characteristic matrix is again a characteristic matrix if and only if the characteristic matrix is reduced. These properties have clear interpretations for the unwrapped unit memory convolutional code of a tail-biting trellis, they explain the duality for the class of Koetter and Vardy trellises, and they give a natural relation between the characteristic matrix based Koetter–Vardy construction and the displacement matrix based Nori–Shankar construction. For a pair of reduced characteristic matrices in duality, one is lexicographically first in a forward direction and the other is lexicographically first in the reverse direction. This confirms a conjecture by Koetter and Vardy after taking into account the different directions for the lexicographical ordering.

AB - Trellises provide a graphical representation for the row space of a matrix. The product construction of Kschischang and Sorokine builds minimal conventional trellises from matrices in minimal span form. Koetter and Vardy showed that minimal tail-biting trellises can be obtained by applying the product construction to submatrices of a characteristic matrix. We introduce the unique reduced minimal span form of a matrix and we obtain an expression for the unique reduced characteristic matrix. Among new properties of characteristic matrices we prove that characteristic matrices are in duality if and only if they have orthogonal column spaces, and that the transpose of a characteristic matrix is again a characteristic matrix if and only if the characteristic matrix is reduced. These properties have clear interpretations for the unwrapped unit memory convolutional code of a tail-biting trellis, they explain the duality for the class of Koetter and Vardy trellises, and they give a natural relation between the characteristic matrix based Koetter–Vardy construction and the displacement matrix based Nori–Shankar construction. For a pair of reduced characteristic matrices in duality, one is lexicographically first in a forward direction and the other is lexicographically first in the reverse direction. This confirms a conjecture by Koetter and Vardy after taking into account the different directions for the lexicographical ordering.

KW - Characteristic generator

KW - Koetter and Vardy conjecture

KW - Linear block code

KW - Minimal trellis

KW - Tail-biting trellis

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

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

U2 - 10.1007/s10623-019-00627-8

DO - 10.1007/s10623-019-00627-8

M3 - Article

AN - SCOPUS:85064622501

VL - 87

SP - 2507

EP - 2536

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

SN - 0925-1022

IS - 11

ER -