Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

Codes and Algorithms Based on Graphs

Richard E. Blahut

Published Feb 6, 2003• 0 citations
Publisher
DOI
10.1017/cbo9780511800467.013

Related papers

Codes defined on graphs

Frank R. Kschischang

Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.

IEEE Communications Magazine•Aug 1, 2003•64 citations

Codes on graphs: recent progress

G. David Forney

Physica A Statistical Mechanics and its Applications•Dec 1, 2001•4 citations

Codes and Graphs

Mohammad Amin Shokrollahi

Lecture notes in computer science•Jan 1, 2000•7 citations

Quantum Computing from Graphs

Andrey Boris Khesin

While stabilizer tableaus have proven exceptionally useful as a descriptive tool for additive quantum codes, they offer little guidance for concrete constructions or coding algorithm analysis. We introduce a representation of stabilizer codes as graphs with certain structures. Specifically, the graphs take a semi-bipartite form where input nodes map to output nodes, such that output nodes may connect to each other but input nodes may not. Intuitively, the graph's input-output edges represent information propagation of the encoder, while output-output edges represent the code's entanglement. We prove that this graph representation is in bijection with tableaus and give an efficient compilation algorithm that transforms tableaus into graphs. We show that this map is efficiently invertible, which gives a universal recipe for code construction by finding graphs with nice properties. The graph representation gives insight into both code construction and algorithms. To the former, we argue that graphs provide a flexible platform for building codes. We construct several constant-size codes and several infinite code families. We also use graphs to extend the quantum Gilbert-Varshamov bound to a three-way distance-rate-weight trade-off. To the latter, we show that key coding algorithms, distance approximation, weight reduction, and decoding, are unified as instances of a single optimization game on a graph. Moreover, key code properties such as distance, weight, and encoding circuit depth, are all controlled by the graph degree. We give efficient algorithms for producing encoding circuits whose depths scale with the degree and for implementing certain logical diagonal and Clifford gates with reduced depth. Finally, we find an efficient decoding algorithm for certain classes of graphs. These results give evidence that graphs are useful for the study of quantum computing and its implementations.

arXiv:2501.17959•Jan 29, 2025•6 citations

Codes on Graphs: A Survey for Algebraists

G. David Forney

Lecture notes in computer science•Jan 1, 1999•1 citation

Improved Trellis-Based Algorithm for Locating and Breaking Cycles in Bipartite Graphs with Applications to LDPC Codes

Juane Li, Shu Lin, Khaled Abdel-Ghaffar

LDPC codes are typically decoded using belief propagation decoding algorithms applied to their Tanner graphs. Cycles of short lengths in these graphs, which are bipartite graphs representing parity-check equations of the codes, can negatively impact the performance of the decoder. In this paper, a trellis-based algorithm is presented to locate cycles in bipartite graphs. This algorithm is an improvement in complexity and run-time over the one developed by Lan et al. in 2004. When applied to Tanner graphs of quasi-cyclic LDPC codes, the newly proposed algorithm can exploit the structure of their parity-check matrices to cut the complexity further. Locating cycles in the Tanner graphs of codes allows for eliminating them to increase the girth and thus improve performance.

Information Theory and Applications Workshop (ITA)•Feb 1, 2018•0 citations
Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.
While stabilizer tableaus have proven exceptionally useful as a descriptive tool for additive quantum codes, they offer little guidance for concrete constructions or coding algorithm analysis. We introduce a representation of stabilizer codes as graphs with certain structures. Specifically, the graphs take a semi-bipartite form where input nodes map to output nodes, such that output nodes may connect to each other but input nodes may not. Intuitively, the graph's input-output edges represent information propagation of the encoder, while output-output edges represent the code's entanglement. We prove that this graph representation is in bijection with tableaus and give an efficient compilation algorithm that transforms tableaus into graphs. We show that this map is efficiently invertible, which gives a universal recipe for code construction by finding graphs with nice properties. The graph representation gives insight into both code construction and algorithms. To the former, we argue that graphs provide a flexible platform for building codes. We construct several constant-size codes and several infinite code families. We also use graphs to extend the quantum Gilbert-Varshamov bound to a three-way distance-rate-weight trade-off. To the latter, we show that key coding algorithms, distance approximation, weight reduction, and decoding, are unified as instances of a single optimization game on a graph. Moreover, key code properties such as distance, weight, and encoding circuit depth, are all controlled by the graph degree. We give efficient algorithms for producing encoding circuits whose depths scale with the degree and for implementing certain logical diagonal and Clifford gates with reduced depth. Finally, we find an efficient decoding algorithm for certain classes of graphs. These results give evidence that graphs are useful for the study of quantum computing and its implementations.
LDPC codes are typically decoded using belief propagation decoding algorithms applied to their Tanner graphs. Cycles of short lengths in these graphs, which are bipartite graphs representing parity-check equations of the codes, can negatively impact the performance of the decoder. In this paper, a trellis-based algorithm is presented to locate cycles in bipartite graphs. This algorithm is an improvement in complexity and run-time over the one developed by Lan et al. in 2004. When applied to Tanner graphs of quasi-cyclic LDPC codes, the newly proposed algorithm can exploit the structure of their parity-check matrices to cut the complexity further. Locating cycles in the Tanner graphs of codes allows for eliminating them to increase the girth and thus improve performance.