Codes on Graphs: Observability, Controllability and Local Reducibility. (arXiv:1203.3115v1 [cs.IT])

from cs.IT updates on

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.

The dual property to observability is the property of having independent
constraints, which is called controllability. 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 trajectories partition into disconnected subrealizations, but
this property does not hold for non-trellis realizations. On a general graph,
the support of an unobservable trajectory is a generalized cycle.



Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s