TY - GEN

T1 - Observability, controllability and local reducibility of linear codes on graphs

AU - Forney, G. David

AU - Gluesing-Luerssen, Heide

PY - 2012

Y1 - 2012

N2 - This paper is concerned with the local reducibility properties of linear realizations of codes on finite graphs. Trimness and properness are dual properties of constraint codes. A linear realization is locally reducible if any constraint code is not both trim and proper. On a finite cycle-free graph, a linear realization is minimal if and only if every constraint code is both trim and proper. A linear realization is called observable if it is one-to-one, and controllable if all constraints are independent. Observability and controllability are dual properties. An unobservable or uncontrollable realization is locally reducible. A parity-check realization is uncontrollable if and only if it has redundant parity checks. A tail-biting trellis realization is uncontrollable if and only if its trajectories partition into disconnected subrealizations. General graphical realizations do not share this property.

AB - This paper is concerned with the local reducibility properties of linear realizations of codes on finite graphs. Trimness and properness are dual properties of constraint codes. A linear realization is locally reducible if any constraint code is not both trim and proper. On a finite cycle-free graph, a linear realization is minimal if and only if every constraint code is both trim and proper. A linear realization is called observable if it is one-to-one, and controllable if all constraints are independent. Observability and controllability are dual properties. An unobservable or uncontrollable realization is locally reducible. A parity-check realization is uncontrollable if and only if it has redundant parity checks. A tail-biting trellis realization is uncontrollable if and only if its trajectories partition into disconnected subrealizations. General graphical realizations do not share this property.

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

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

U2 - 10.1109/ISIT.2012.6284277

DO - 10.1109/ISIT.2012.6284277

M3 - Conference contribution

AN - SCOPUS:84867512664

SN - 9781467325790

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 641

EP - 645

BT - 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012

Y2 - 1 July 2012 through 6 July 2012

ER -