Codes on Graphs: Observability, Controllability, and Local Reducibility
Original manuscript: August 30, 2012
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86145 |
| _version_ | 1811081084446703616 |
|---|---|
| author | Gluesing-Luerssen, Heide Forney, G. David, Jr. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gluesing-Luerssen, Heide Forney, G. David, Jr. |
| author_sort | Gluesing-Luerssen, Heide |
| collection | MIT |
| description | Original manuscript: August 30, 2012 |
| first_indexed | 2024-09-23T11:41:24Z |
| format | Article |
| id | mit-1721.1/86145 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:41:24Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/861452022-09-27T21:14:34Z Codes on Graphs: Observability, Controllability, and Local Reducibility Gluesing-Luerssen, Heide Forney, G. David, Jr. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Forney, G. David, Jr. Original manuscript: August 30, 2012 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. 2014-04-14T15:34:09Z 2014-04-14T15:34:09Z 2012-09 2012-08 Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 http://hdl.handle.net/1721.1/86145 Forney, Jr., G. David, and Heide Gluesing-Luerssen. “Codes on Graphs: Observability, Controllability, and Local Reducibility.” IEEE Trans. Inform. Theory 59, no. 1 (n.d.): 223–237. en_US http://dx.doi.org/10.1109/tit.2012.2217312 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Gluesing-Luerssen, Heide Forney, G. David, Jr. Codes on Graphs: Observability, Controllability, and Local Reducibility |
| title | Codes on Graphs: Observability, Controllability, and Local Reducibility |
| title_full | Codes on Graphs: Observability, Controllability, and Local Reducibility |
| title_fullStr | Codes on Graphs: Observability, Controllability, and Local Reducibility |
| title_full_unstemmed | Codes on Graphs: Observability, Controllability, and Local Reducibility |
| title_short | Codes on Graphs: Observability, Controllability, and Local Reducibility |
| title_sort | codes on graphs observability controllability and local reducibility |
| url | http://hdl.handle.net/1721.1/86145 |
| work_keys_str_mv | AT gluesingluerssenheide codesongraphsobservabilitycontrollabilityandlocalreducibility AT forneygdavidjr codesongraphsobservabilitycontrollabilityandlocalreducibility |