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

IEICE ESS FUNDAMENTALS REVIEW

Low-Density Parity-Check Codes

Hironori Uchikawa

Published Dec 31, 2020• 7 citations
Publisher

Abstract

2020年の日本国際賞をマサチューセッツ工科大学名誉教授であるRobert G. Gallagerが受賞した．受賞の対象となった低密度パリティ検査符号（LDPC符号）は，Gallagerが1960年に彼の博士論文で提案した誤り訂正符号である．30年以上という長い歳月を経て評価されたLDPC符号は，またたく間に我々に身近な情報機器にも搭載されるようになり，現在では我々の生活に欠かせない技術となっている．本稿ではこのLDPC符号について解説する．特に確率推論の観点から最適な復号アルゴリズムがLDPC符号により実行可能な形で導かれることを紹介する．更に実用的なLDPC符号をどのようにして構成するのか，その構成方法を紹介する．

DOI
10.1587/essfr.14.3_217

Related papers

最適化手法に基づく誤り訂正符号の復号アルゴリズムについて

正 和田山

月 28 日；改訂 8 月 28 日；採択 9 月 5 日) 要 旨 近年，線形計画法などの連続最適化に基づく誤り訂正符号の復号法が登場し，符号理論研究 者の注目を集めている．本稿では，著者の提案する内点法に基づく LDPC 符号 (Low-Density Parity-Check 符号) の復号法の概要とその特徴を紹介する．この復号法 (内点復号法) は，LDPC 符号の復号問題を凸計画問題として定式化し，バリア関数に基づく主パス追跡内点法により近 似的にその凸計画問題を高速に解く，という考え方に基づいて構成されている．本復号アルゴ リズムは，線形ベクトル通信路の範疇に入る定常無記憶通信路，シンボル間干渉通信路，MIMO 通信路，マルチプルアクセス通信路など様々な通信路に適用が可能であり，幅広い応用が期待 されている． キーワード： 内点法，凸計画問題，低密度パリティ検査符号． 1. 緒言

•Jun 1, 2013•0 citations

Density Evolution Analysis of Generalized Low-density Parity-check Codes under a Posteriori Probability Decoder

Chang, Dongxu, Qingqing Peng, Ma, Zhiming +2 more

In this study, the performance of generalized low-density parity-check (GLDPC) codes under the a posteriori probability (APP) decoder is analyzed. We explore the concentration, symmetry, and monotonicity properties of GLDPC codes under the APP decoder, extending the applicability of density evolution to GLDPC codes. On the binary memoryless symmetric channels, using the BEC and BI-AWGN channels as two examples, we demonstrate that with an appropriate proportion of generalized constraint (GC) nodes, GLDPC codes can reduce the original gap to capacity compared to their original LDPC counterparts. Additionally, on the BI-AWGN channel, we apply and improve the Gaussian approximation algorithm in the density evolution of GLDPC codes. By adopting Gaussian mixture distributions to approximate the message distributions from variable nodes and Gaussian distributions for those from constraint nodes, the precision of the channel parameter threshold can be significantly enhanced while maintaining a low computational complexity similar to that of Gaussian approximations. Furthermore, we identify a class of subcodes that can greatly simplify the performance analysis and practical decoding of GLDPC codes, which we refer to as message-invariant subcodes. Using the aforementioned techniques, our simulation experiments provide empirical evidence that GLDPC codes, when decoded with the APP decoder and equipped with the right fraction of GC nodes, can achieve substantial performance improvements compared to low-density parity-check (LDPC) codes.

arXiv:2404.01136•Apr 1, 2024•0 citations

Generalized LDPC codes and generalized stopping sets

N. Miladinovic, M.P.C. Fossorier

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.

IEEE Transactions on Communications•Feb 1, 2008•52 citations

Full and shortened low-density parity-checked codes based on finite geometries and their decoding algorithms.

Назаров Лев Евгеньевич

ПОЛНЫЕ И УКОРОЧЕННЫЕ БЛОКОВЫЕ НИЗКОПЛОТНОСТНЫЕ КОДЫ НА ОСНОВЕ КОНЕЧНЫХ ГЕОМЕТРИЙ И АЛГОРИТМЫ ИХ ИТЕРАТИВНОГО ПРИЕМА Л. Е. Назаров Фрязинский филиал Института радиотехники и электроники им.В.А.Котельникова РАН, 141190, Московская область, г.Фрязино, пл.академика Введенского, д.1 Статья поступила в редакцию 25 октября 2018 г.Аннотация.Приведены описания методов формирования полных и укороченных помехоустойчивых низкоплотностных кодов на основе конечных геометрий (евклидово-геометрические коды, проективно-геометрические коды).Даны описания алгоритмов итеративного приема для данных кодов.Даны результаты моделирования для ряда рассматриваемых кодов с использованием программно-аппаратной реализации алгоритмов формирования и приема на основе программируемой логической интегральной схемы FPGA VIRTEX-5SX.

Journal of Radio Electronics•Nov 1, 2018•1 citation

量子誤り訂正符号を用いたエンタングルメント蒸留プロトコルの性能評価に関する検討(LDPC符号,一般)

雅一 吉田, 学 萩原, 隆之 宮寺 +1 more

Information technology newsletter•Sep 14, 2010•0 citations

Decoding of generalised low-density parity-check codes using weighted bit-flip voting

S. Hirst, B. Honary

A generalised low-density parity-check code (GLDPC) is a low-density parity-check code in which the constraint nodes of the code's graph are replaced with component or subcodes other than single parity checks. Gallager's bit-flipping algorithm for LDPCs is generalised to the class of GLDPCs with Hamming subcodes. The proposed weighted bit-flip voting (WBFV) method is iterative and uses only the hard decision decoder of the Hamming subcodes. Decoding of Hamming-based GLDPCs using WBFV has been simulated on the binary symmetric channel. Simulation results are presented showing the variation in performance with voting rule, graph construction and block length. In terms of the dependence of coding gains and complexity on the GLDPC block length, the proposed method is found to display a good performance to decoding complexity trade-off. Performance is found to compete well with other more conventional hard decision decoding schemes.

IEE Proceedings - Communications•Jan 1, 2002•19 citations
2020年の日本国際賞をマサチューセッツ工科大学名誉教授であるRobert G. Gallagerが受賞した．受賞の対象となった低密度パリティ検査符号（LDPC符号）は，Gallagerが1960年に彼の博士論文で提案した誤り訂正符号である．30年以上という長い歳月を経て評価されたLDPC符号は，またたく間に我々に身近な情報機器にも搭載されるようになり，現在では我々の生活に欠かせない技術となっている．本稿ではこのLDPC符号について解説する．特に確率推論の観点から最適な復号アルゴリズムがLDPC符号により実行可能な形で導かれることを紹介する．更に実用的なLDPC符号をどのようにして構成するのか，その構成方法を紹介する．
月 28 日；改訂 8 月 28 日；採択 9 月 5 日) 要 旨 近年，線形計画法などの連続最適化に基づく誤り訂正符号の復号法が登場し，符号理論研究 者の注目を集めている．本稿では，著者の提案する内点法に基づく LDPC 符号 (Low-Density Parity-Check 符号) の復号法の概要とその特徴を紹介する．この復号法 (内点復号法) は，LDPC 符号の復号問題を凸計画問題として定式化し，バリア関数に基づく主パス追跡内点法により近 似的にその凸計画問題を高速に解く，という考え方に基づいて構成されている．本復号アルゴ リズムは，線形ベクトル通信路の範疇に入る定常無記憶通信路，シンボル間干渉通信路，MIMO 通信路，マルチプルアクセス通信路など様々な通信路に適用が可能であり，幅広い応用が期待 されている． キーワード： 内点法，凸計画問題，低密度パリティ検査符号． 1. 緒言
In this study, the performance of generalized low-density parity-check (GLDPC) codes under the a posteriori probability (APP) decoder is analyzed. We explore the concentration, symmetry, and monotonicity properties of GLDPC codes under the APP decoder, extending the applicability of density evolution to GLDPC codes. On the binary memoryless symmetric channels, using the BEC and BI-AWGN channels as two examples, we demonstrate that with an appropriate proportion of generalized constraint (GC) nodes, GLDPC codes can reduce the original gap to capacity compared to their original LDPC counterparts. Additionally, on the BI-AWGN channel, we apply and improve the Gaussian approximation algorithm in the density evolution of GLDPC codes. By adopting Gaussian mixture distributions to approximate the message distributions from variable nodes and Gaussian distributions for those from constraint nodes, the precision of the channel parameter threshold can be significantly enhanced while maintaining a low computational complexity similar to that of Gaussian approximations. Furthermore, we identify a class of subcodes that can greatly simplify the performance analysis and practical decoding of GLDPC codes, which we refer to as message-invariant subcodes. Using the aforementioned techniques, our simulation experiments provide empirical evidence that GLDPC codes, when decoded with the APP decoder and equipped with the right fraction of GC nodes, can achieve substantial performance improvements compared to low-density parity-check (LDPC) codes.
A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.
ПОЛНЫЕ И УКОРОЧЕННЫЕ БЛОКОВЫЕ НИЗКОПЛОТНОСТНЫЕ КОДЫ НА ОСНОВЕ КОНЕЧНЫХ ГЕОМЕТРИЙ И АЛГОРИТМЫ ИХ ИТЕРАТИВНОГО ПРИЕМА Л. Е. Назаров Фрязинский филиал Института радиотехники и электроники им.В.А.Котельникова РАН, 141190, Московская область, г.Фрязино, пл.академика Введенского, д.1 Статья поступила в редакцию 25 октября 2018 г.Аннотация.Приведены описания методов формирования полных и укороченных помехоустойчивых низкоплотностных кодов на основе конечных геометрий (евклидово-геометрические коды, проективно-геометрические коды).Даны описания алгоритмов итеративного приема для данных кодов.Даны результаты моделирования для ряда рассматриваемых кодов с использованием программно-аппаратной реализации алгоритмов формирования и приема на основе программируемой логической интегральной схемы FPGA VIRTEX-5SX.
A generalised low-density parity-check code (GLDPC) is a low-density parity-check code in which the constraint nodes of the code's graph are replaced with component or subcodes other than single parity checks. Gallager's bit-flipping algorithm for LDPCs is generalised to the class of GLDPCs with Hamming subcodes. The proposed weighted bit-flip voting (WBFV) method is iterative and uses only the hard decision decoder of the Hamming subcodes. Decoding of Hamming-based GLDPCs using WBFV has been simulated on the binary symmetric channel. Simulation results are presented showing the variation in performance with voting rule, graph construction and block length. In terms of the dependence of coding gains and complexity on the GLDPC block length, the proposed method is found to display a good performance to decoding complexity trade-off. Performance is found to compete well with other more conventional hard decision decoding schemes.