Codes on Graphs: Duality and MacWilliams Identities
A conceptual framework involving partition functions of normal factor graphs is introduced, paralleling a similar recent development by Al-Bashabsheh and Mao. The partition functions of dual normal factor graphs are shown to be a Fourier transform pair, whether or not the graphs have cycles. The ori...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72571 |
| _version_ | 1826194950335758336 |
|---|---|
| author | 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 Forney, G. David, Jr. |
| author_sort | Forney, G. David, Jr. |
| collection | MIT |
| description | A conceptual framework involving partition functions of normal factor graphs is introduced, paralleling a similar recent development by Al-Bashabsheh and Mao. The partition functions of dual normal factor graphs are shown to be a Fourier transform pair, whether or not the graphs have cycles. The original normal graph duality theorem follows as a corollary. Within this framework, MacWilliams identities are found for various local and global weight generating functions of general group or linear codes on graphs; this generalizes and provides a concise proof of the MacWilliams identity for linear time-invariant convolutional codes that was recently found by Gluesing-Luerssen and Schneider. Further MacWilliams identities are developed for terminated convolutional codes, particularly for tail-biting codes, similar to those studied recently by Bocharova, Hug, Johannesson, and Kudryashov. |
| first_indexed | 2024-09-23T10:04:41Z |
| format | Article |
| id | mit-1721.1/72571 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:04:41Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/725712022-09-30T18:45:04Z Codes on Graphs: Duality and MacWilliams Identities Forney, G. David, Jr. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Forney, G. David, Jr. Forney, G. David, Jr. A conceptual framework involving partition functions of normal factor graphs is introduced, paralleling a similar recent development by Al-Bashabsheh and Mao. The partition functions of dual normal factor graphs are shown to be a Fourier transform pair, whether or not the graphs have cycles. The original normal graph duality theorem follows as a corollary. Within this framework, MacWilliams identities are found for various local and global weight generating functions of general group or linear codes on graphs; this generalizes and provides a concise proof of the MacWilliams identity for linear time-invariant convolutional codes that was recently found by Gluesing-Luerssen and Schneider. Further MacWilliams identities are developed for terminated convolutional codes, particularly for tail-biting codes, similar to those studied recently by Bocharova, Hug, Johannesson, and Kudryashov. 2012-09-07T17:46:08Z 2012-09-07T17:46:08Z 2011-02 2010-11 Article http://purl.org/eprint/type/JournalArticle 0018-9448 http://hdl.handle.net/1721.1/72571 Forney, G. David. “Codes on Graphs: Duality and MacWilliams Identities.” IEEE Transactions on Information Theory 57.3 (2011): 1382–1397. en_US http://dx.doi.org/10.1109/tit.2011.2104994 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Forney, G. David, Jr. Codes on Graphs: Duality and MacWilliams Identities |
| title | Codes on Graphs: Duality and MacWilliams Identities |
| title_full | Codes on Graphs: Duality and MacWilliams Identities |
| title_fullStr | Codes on Graphs: Duality and MacWilliams Identities |
| title_full_unstemmed | Codes on Graphs: Duality and MacWilliams Identities |
| title_short | Codes on Graphs: Duality and MacWilliams Identities |
| title_sort | codes on graphs duality and macwilliams identities |
| url | http://hdl.handle.net/1721.1/72571 |
| work_keys_str_mv | AT forneygdavidjr codesongraphsdualityandmacwilliamsidentities |