Abstract
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 language | English |
---|---|
Article number | 6295660 |
Pages (from-to) | 223-237 |
Number of pages | 15 |
Journal | IEEE Transactions on Information Theory |
Volume | 59 |
Issue number | 1 |
DOIs | |
State | Published - 2013 |
Keywords
- Codes on graphs
- controllability
- duality
- local reducibility
- observability
- realizations
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Library and Information Sciences