Codes on graphs: Observability, controllability, and local reducibility

G. David Forney, Heide Gluesing-Luerssen

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


This paper investigates properties of realizations of linear or group codes on general graphs that lead to local reducibility. Trimness and properness are dual properties of constraint codes. A linear or group realization with a constraint code that is not both trim and proper is locally reducible. A linear or group realization on a finite cycle-free graph is minimal if and only if every local constraint code is trim and proper. A realization is called observable if there is a one-to-one correspondence between codewords and configurations, and controllable if it has independent constraints. A linear or group realization is observable if and only if its dual is controllable. A simple counting test for controllability is given. An unobservable or uncontrollable realization is locally reducible. Parity-check realizations are controllable if and only if they have independent parity checks. In an uncontrollable tail-biting trellis realization, the behavior partitions into disconnected sub-behaviors, but this property does not hold for nontrellis realizations. On a general graph, the support of an unobservable configuration is a generalized cycle.

Original languageEnglish
Article number6295660
Pages (from-to)223-237
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - 2013


  • Codes on graphs
  • controllability
  • duality
  • local reducibility
  • observability
  • realizations

ASJC Scopus subject areas

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


Dive into the research topics of 'Codes on graphs: Observability, controllability, and local reducibility'. Together they form a unique fingerprint.

Cite this