© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

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

正和田山

Published Jun 1, 2013• 0 citations

Abstract

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

Related papers

Low-Density Parity-Check Codes

Hironori Uchikawa

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

IEICE ESS FUNDAMENTALS REVIEW•Dec 31, 2020•7 citations

低密度パリティ検査符号とその復号法 : LDPC(Low density parity check)符号/sum-product復号法

正和田山, トリケップス企画部

トリケップス eBooks•Jan 1, 2002•0 citations

Low-complexity iterative detection and decoding in finite geometry LDPC-coded MIMO systems

Nuwan Balasuriya, Pradeepa Yahampath, Telex M. N. Ngatched +1 more

This paper presents a low-complexity iterative joint detection and decoding algorithm for finite geometry-low density parity check (FG-LDPC) coded multiple-input multiple-output (MIMO) systems, in which the MIMO channel detector and the FG-LDPC decoder iteratively exchange soft information. The key to the simplicity of the algorithm is the use of a bit flipping-based decoder for FG-LDPC code. An important issue addressed here is the generation of soft information from the binary outputs of the bit-flipping decoder to be fed back to the MIMO detector. Simulation results show that the proposed joint detection and decoding algorithm achieves a substantial reduction in decoding error probability compared to a cascaded detector and a decoder. We also compare the performance with belief-propagation (BP) based detector-decoders which are significantly more complex. The new algorithm provides a practical approach to joint detection and decoding of popular FG-LDPC codes in a MIMO system, a task which is computationally unmanageable with a BP algorithm.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2009•2 citations

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

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

Information technology newsletter•Sep 14, 2010•0 citations

체크 노드 분할에 의한 LDPC 부호의 새로운 메시지 전달 복호 알고리즘

김성환, 장민호, 노종선 +2 more

본 논문에서는 체크 노드 분할에 의한 low-density parity-check(LDPC) 부호의 새로운 직렬 메시지 전달 복호알고리즘을 제안한다. 이 새로운 복호 알고리즘은 특히 적은 반복 횟수에 대하여 기존의 메시지 전달 복호 알고리즘 [3],[7] 의 비트 오율(BER) 성능보다 더 우수한 성능을 보인다. 체크 노드의 분할된 부분 집합의 개수가 증가함에 따라 비트 오율 성능이 보다 좋아진다는 사실을 분석적 결과로 확인할 수 있다. 또한 가우시안 근사화를 이용한 밀도 진화를 이용하여 변수 노드에서 메시지들의 평균값에 대한 재귀 방정식을 유도하고, 모의 실험을 이용하여 분석적인 결과를 검증하였다.

한국통신학회논문지•Apr 1, 2006•0 citations

Symbol-based BP detection for MIMO systems associated with non-binary LDPC codes

Ali Haroun, Charbel Abdel Nour, Matthieu Arzel +1 more

In this paper, an efficient iterative receiver for digital communication systems is investigated. It combines a Non-Binary Low-Density Parity-Check (NB-LDPC) decoder with a high-order constellation demapper and a Multiple-Input Multiple-Output (MIMO) detector. A suboptimal MIMO detector based on the Belief Propagation (BP) algorithm is investigated as an alternative to a Maximum Likelihood (ML) detector. Extrinsic information is exchanged between the detector and the decoder thanks to an iterative process. EXtrinsic Information Transfer (EXIT) charts enable to analyze the convergence behaviour of the proposed MIMO-BP detector. A suitable schedule for the different types of iterations is finally proposed to reduce the receiver latency and improve its error correction performance.

IEEE Wireless Communications and Networking Conference•Apr 1, 2014•13 citations

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

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

This paper presents a low-complexity iterative joint detection and decoding algorithm for finite geometry-low density parity check (FG-LDPC) coded multiple-input multiple-output (MIMO) systems, in which the MIMO channel detector and the FG-LDPC decoder iteratively exchange soft information. The key to the simplicity of the algorithm is the use of a bit flipping-based decoder for FG-LDPC code. An important issue addressed here is the generation of soft information from the binary outputs of the bit-flipping decoder to be fed back to the MIMO detector. Simulation results show that the proposed joint detection and decoding algorithm achieves a substantial reduction in decoding error probability compared to a cascaded detector and a decoder. We also compare the performance with belief-propagation (BP) based detector-decoders which are significantly more complex. The new algorithm provides a practical approach to joint detection and decoding of popular FG-LDPC codes in a MIMO system, a task which is computationally unmanageable with a BP algorithm.

본 논문에서는 체크 노드 분할에 의한 low-density parity-check(LDPC) 부호의 새로운 직렬 메시지 전달 복호알고리즘을 제안한다. 이 새로운 복호 알고리즘은 특히 적은 반복 횟수에 대하여 기존의 메시지 전달 복호 알고리즘 [3],[7] 의 비트 오율(BER) 성능보다 더 우수한 성능을 보인다. 체크 노드의 분할된 부분 집합의 개수가 증가함에 따라 비트 오율 성능이 보다 좋아진다는 사실을 분석적 결과로 확인할 수 있다. 또한 가우시안 근사화를 이용한 밀도 진화를 이용하여 변수 노드에서 메시지들의 평균값에 대한 재귀 방정식을 유도하고, 모의 실험을 이용하여 분석적인 결과를 검증하였다.

In this paper, an efficient iterative receiver for digital communication systems is investigated. It combines a Non-Binary Low-Density Parity-Check (NB-LDPC) decoder with a high-order constellation demapper and a Multiple-Input Multiple-Output (MIMO) detector. A suboptimal MIMO detector based on the Belief Propagation (BP) algorithm is investigated as an alternative to a Maximum Likelihood (ML) detector. Extrinsic information is exchanged between the detector and the decoder thanks to an iterative process. EXtrinsic Information Transfer (EXIT) charts enable to analyze the convergence behaviour of the proposed MIMO-BP detector. A suitable schedule for the different types of iterations is finally proposed to reduce the receiver latency and improve its error correction performance.