The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Codes on graphs: normal realizations
Abstract
A generalized state realization of the Wiberg (1996) type is called normal if symbol variables have degree 1 and state variables have degree 2. A natural graphical model of such a realization has leaf edges representing symbols, ordinary edges representing states, and vertices representing local constraints. Such a graph can be decoded by any version of the sum-product algorithm. Any state realization of a code can be put into normal form without essential change in the corresponding graph or in its decoding complexity. Group or linear codes are generated by group or linear state realizations. On a cycle-free graph, there exists a well-defined minimal canonical realization, and the sum-product algorithm is exact. However, the cut-set bound shows that graphs with cycles may have a superior performance-complexity tradeoff, although the sum-product algorithm is then inexact and iterative, and minimal realizations are not well-defined. Efficient cyclic and cycle-free realizations of Reed-Muller (RM) codes are given as examples. The dual of a normal group realization, appropriately defined, generates the dual group code. The dual realization has the same graph topology as the primal realization, replaces symbol and state variables by their character groups, and replaces primal local constraints by their duals. This fundamental result has many applications, including to dual state spaces, dual minimal trellises, duals to Tanner (1981) graphs, dual input/output (I/O) systems, and dual kernel and image representations. Finally a group code may be decoded using the dual graph, with appropriate Fourier transforms of the inputs and outputs; this can simplify decoding of high-rate codes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Low-density parity-check codes
Gallager, R. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057683 · Cited by 10,602
Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1
Berrou, C., Glavieux, A., & Thitimajshima, P. (2002) · Proceedings of ICC '93 - IEEE International Conference on Communications · doi:10.1109/icc.1993.397441 · Cited by 6,738
Factor graphs and the sum-product algorithm
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486
Low-Density Parity-Check Codes
Gallager, R. G. (1963) · The MIT Press eBooks · doi:10.7551/mitpress/4347.001.0001 · Cited by 4,401
Design of capacity-approaching irregular low-density parity-check codes
Richardson, T. J., Shokrollahi, M. A., & Urbanke, R. L. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910578 · Cited by 3,335
Probabilistic Reasoning in Intelligent Systems
(1988) · Elsevier eBooks · doi:10.1016/c2009-0-27609-4 · Cited by 3,321
A recursive approach to low complexity codes
Tanner, R. (1981) · IEEE Transactions on Information Theory · doi:10.1109/tit.1981.1056404 · Cited by 3,138
The capacity of low-density parity-check codes under message-passing decoding
Richardson, T. J., & Urbanke, R. L. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910577 · Cited by 3,065
Near Shannon limit performance of low density paritycheck codes
MacKay, D. J. C., & Neal, R. M. (1997) · Electronics Letters · doi:10.1049/el:19970362 · Cited by 2,678
Iterative decoding of binary block and convolutional codes
Hagenauer, J., Offer, E., & Papke, L. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.485714 · Cited by 2,303
Near Shannon limit performance of low density paritycheck codes
MacKay, D. J. C., & Neal, R. M. (1996) · Electronics Letters · doi:10.1049/el:19961141 · Cited by 1,923
(2006) · Spectral Interpretation of Decision Diagrams · doi:10.1007/0-387-21734-7_4 · Cited by 1,771
On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit
Chung, S.-Y., Forney, G. D., Richardson, T. J., & Urbanke, R. (2001) · IEEE Communications Letters · doi:10.1109/4234.905935 · Cited by 1,539
Self-citationLow-density parity check codes over GF(q)
Davey, M. C., & MacKay, D. (1998) · IEEE Communications Letters · doi:10.1109/4234.681360 · Cited by 1,199
Paradigms and puzzles in the theory of dynamical systems
Willems, J. C. (1991) · IEEE Transactions on Automatic Control · doi:10.1109/9.73561 · Cited by 1,176
Sipser, M., & Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556667 · Cited by 931
Turbo decoding as an instance of Pearl's "belief propagation" algorithm
McEliece, R. J., MacKay, D. J. C., & Cheng, J.-F. (1998) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.661103 · Cited by 904
Codes and Decoding on General Graphs
Wiberg, N. (1996) · Cited by 869
The generalized distributive law
Aji, S. M., & McEliece, R. J. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825794 · Cited by 735
On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
Weiss, Y., & Freeman, W. T. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910585 · Cited by 581
Coding theorems for 'turbo-like' codes
Divsalar, D. (1998) · Medical Entomology and Zoology · Cited by 524
Graphical models for machine learning and digital communication
(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)90253-5 · Cited by 454
Rudin, W. (1990) · Wiley eBooks · doi:10.1002/9781118165621 · Cited by 447
Willems, J. C. (1989) · Dynamics Reported · doi:10.1007/978-3-322-96657-5_5 · Cited by 421
Iterative decoding of compound codes by probability propagation in graphical models
Kschischang, F. R., & Frey, B. J. (1998) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.661110 · Cited by 388
Bennett, C. H., & Shor, P. W. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720553 · Cited by 370
Codes and iterative decoding on general graphs
Wiberg, N., Loeliger, H., & Kotter, R. (1995) · European Transactions on Telecommunications · doi:10.1002/ett.4460060507 · Cited by 314
Bennett, C. H. (2018) · Feynman and Computation · doi:10.1201/9780429500459-13 · Cited by 218
Minimal tail-biting trellises: the Golay code and more
Calderbank, A. R., Forney, G. D., & Vardy, A. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.771145 · Cited by 163
Self-citationBethe free energy, Kikuchi approximations, and belief propagation algorithms
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2001) · Cited by 162
Probability propagation and decoding in analog VLSI
Loeliger, H.-A., Lustenberger, F., Helfenstein, M., & Tarkoy, F. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910594 · Cited by 158
Which codes have cycle-free Tanner graphs?
Etzion, T., Trachtenberg, A., & Vardy, A. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.782170 · Cited by 158
Design of provably good low-density parity check codes
Richardson, T., Shokrollahi, A., & Urbanke, R. L. (2002) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2000.866497 · Cited by 137
Convolutional codes over groups
Loeliger, H., & Mittelholzer, T. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556664 · Cited by 121
Least Squares and Kalman Filtering on Forney Graphs
Loeliger, H.-A. (2002) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/978-1-4615-0895-3_7 · Cited by 52
Cited by
Factor graphs and the sum-product algorithm
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486
Arikan, E. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2021379 · Cited by 4,476
Information, Physics, and Computation
Mézard, M., & Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,913
Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850085 · Cited by 1,617
On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit
Chung, S.-Y., Forney, G. D., Richardson, T. J., & Urbanke, R. (2001) · IEEE Communications Letters · doi:10.1109/4234.905935 · Cited by 1,539
Self-citation
Metadata
- Authors
- Forney, G. D.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2001
- Volume
- 47
- Issue
- 2
- Pages
- 520-548
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2139584447
- Cited by
- 642
- References
- 35
- FWCI
- 42.49
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.