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

High-Performance and Low-Complexity Decoding of High-Weight LDPC Codes

조준호, 성원용

Published May 1, 2009• 0 citations
OpenAlex

Abstract

Low-density parity-check (LDPC) 부호의 복호에는 성능이 좋은 합곱 알고리즘(sum-product algorithm; SPA)과 하드웨어가 간단한 비트 반전(bit-flipping; BF) 알고리즘이 많이 쓰이고 있다. 본 논문은 이들 두 가지 방법의 장점을 가지는 저복잡도 고성능 복호 알고리즘을 제안한다. 본 제안된 유연 비트 반전(soft bit-flipping) 알고리즘은 비트와 체크 노드 사이에 전달되는 메시지를 계산하는 데 단순한 비교와 덧셈 연산만을 필요로 하며 연산량이 적다는 장점이 있다. 또한 연산이 완료된 메시지의 활용률을 높이고 비균등 양자화(non-uniform quantization)를 채용하여 1000 내외의 부호 길이에서 SPA 에 0.4dB 근접하는 신호대 잡음비(signal-to-noise ratio)를 달성하였다. 본 논문에서 제안된 알고리즘을 이용하면, 행 무게(row weight)와 열 무게(column weight)가 높아서 종래의 SPA로 구현하기 어려웠던 부호를 비교적 좋은 오율 성능을 유지하면서 실용적으로 구현할 수 있다. ; A high-performance low-complexity decoding algorithm for LDPC codes is proposed in this paper, which has the advantages of both bit-flipping (BF) algorithm and sum-product algorithm (SPA). The proposed soft bit-flipping algorithm requires only simple comparison and addition operations for computing the messages between bit and check nodes, and the amount of those operations is also small. By increasing the utilization ratio of the computed messages and by adopting nonuniform quantization, the signal-to-noise ratio (SNR) gap to the SPA is reduced to 0.4dB at the frame error rate of 10-4 with only 5-bit assignment for quantization. LDPC codes with high column or row weights, which are not suitable for the SPA decoding due to the complexity, can be practically implemented without much worsening the error performance.

Related papers

Analysis of Performance according to LDPC Decoding Algorithms

Tae Hyun Yoon, Jin Tae Park, Eon Kyeong Joo

LDPC(low density parity check)부호는 합-곱 알고리즘 기반의 반복복호를 통해 Shannon 한계에 근접하는 성능을 보인다. 합곱 알고리즘에서 체크노드와 비트노드의 확률 및 부가정보의 갱신 순서는 스케쥴링 방법에 따라 달라지며 그에 따라 오류정정능력이나 반복복호의 횟수가 달라진다. 기존에 제안된 순차 BP 알고리즘을 사용한 LDPC의 복호는 표준 BP 알고리즘을 바탕으로 복호를 수행했을 경우에 비해 적은 평균반복복호 횟수에도 불구하고 좋은 성능을 가진다고 알려져 있다. 하지만 기존의 연구들에서는 이러한 성능 차이의 원인에 대한 연구는 미비하다. 따라서 본 논문에서는 두 알고리즘의 적용에 따른 LDPC 복호의 성공 여부에 따라 4가지 경우로 분류하고 각 경우를 비교한다. 이를 통해 두 알고리즘의 성능 차이의 원인을 분석하고 그 결과로 성능 차이의 원인이 패리티 검사행렬 내부의 사이클을 구성하는 비트노드들의 확률 값을 갱신할 때 알고리즘에 따른 갱신 과정의 차이에 있음을 보인다. LDPC (low density parity check) code shows near Shannon limit performance by iterative decoding based on sum-product algorithm (SPA). Message updating procedure between variable and check nodes in SPA is done by a scheduling method. LDPC code shows different performance according to scheduling schemes. The conventional researches have been shown that the shuffled BP (belief propagation) algorithm shows better performance than the standard BP algorithm although it needs less number of iterations. However the reason is not analyzed clearly. Therefore the reason of difference in performance according to LDPC decoding algorithms is analyzed in this paper. 4 cases according to satisfaction of parity check condition are considered and compared. As results, the difference in the updating procedure in a cycle in the parity check matrix is considered to be the main reason of performance difference.

한국통신학회논문지•Nov 30, 2012•2 citations

Tabu-List Probabilistic Sequential Adaptive Threshold Gradient Descent Bit-Flipping Algorithm

Myungin Kim, Jeongseok Ha

본 논문은 저밀도 패리티 검사 (low-density parity-check, LDPC) 부호의 비트 반전 알고리즘(bit-flipping algorithm, BFA)의 부호 오류율 (Word Error Rate, WER) 및 복호 속도 개선에 관한 연구이다. 비트 반전 알고리즘은 비트의 신뢰도를 측정하는 측도인 반전 함수 (flipping function) 값의 임계값을 초과하는 비트를 반전시켜 오류를 정정하는 방식으로 동작한다. 본 논문에서는 반전 함수의 국소 최댓값을 이용해 반전 함수의 임계값을 매 반복마다 적응적으로 설정하여 반복 복호 횟수와 임계값을 찾는데 필요한 정렬 복잡도를 감소시키고, 복호 실패의 주 원인 중 하나인 trapping set 문제를 해결하기 위해 확률적으로 비트를 반전시켜 부호 오류율을 개선하였다.

한국통신학회논문지•May 27, 2021•0 citations

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

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

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

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

높은 무게 LDPC 부호의 저복잡도 고성능 복호 알고리즘

Jun-Ho Cho, 성원용

A high-performance low-complexity decoding algorithm for LDPC codes is proposed in this paper, which has the advantages of both bit-flipping (BF) algorithm and sum-product algorithm (SPA). The proposed soft bit-flipping algorithm requires only simple comparison and addition operations for computing the messages between bit and check nodes, and the amount of those operations is also small. By increasing the utilization ratio of the computed messages and by adopting nonuniform quantization, the signal-to-noise ratio (SNR) gap to the SPA is reduced to 0.4dB at the frame error rate of 10-4 with only 5-bit assignment for quantization. LDPC codes with high column or row weights, which are not suitable for the SPA decoding due to the complexity, can be practically implemented without much worsening the error performance.

한국통신학회논문지•Jan 1, 2009•0 citations

저밀도 패리티 검사부호의 복호 알고리즘에 따른 성능 비교 분석

윤태현, 박진태, 주언경

LDPC(low density parity check)부호는 합-곱 알고리즘 기반의 반복복호를 통해 Shannon 한계에 근접하는 성능을 보인다. 합곱 알고리즘에서 체크노드와 비트노드의 확률 및 부가정보의 갱신 순서는 스케쥴링 방법에 따라 달라지며 그에 따라 오류정정능력이나 반복복호의 횟수가 달라진다. 기존에 제안된 순차 BP 알고리즘을 사용한 LDPC의 복호는 표준 BP 알고리즘을 바탕으로 복호를 수행했을 경우에 비해 적은 평균반복복호 횟수에도 불구하고 좋은 성능을 가진다고 알려져 있다. 하지만 기존의 연구들에서는 이러한 성능 차이의 원인에 대한 연구는 미비하다. 따라서 본 논문에서는 두 알고리즘의 적용에 따른 LDPC 복호의 성공 여부에 따라 4가지 경우로 분류하고 각 경우를 비교한다. 이를 통해 두 알고리즘의 성능 차이의 원인을 분석하고 그 결과로 성능 차이의 원인이 패리티 검사행렬 내부의 사이클을 구성하는 비트노드들의 확률 값을 갱신할 때 알고리즘에 따른 갱신 과정의 차이에 있음을 보인다.

한국통신학회논문지•Nov 1, 2012•6 citations

오류 마루 현상이 완화된 비이진 LDPC 부호의 설계 및 성능 분석 연구

안석기, 임승찬, 양영오 +1 more

본 논문은 오류 마루 영역에서 우수한 성능을 가지는 비이진 LDPC (low-density parity-check) 부호의 설계 방법을 제안하고 성능을 검증한다. 제안된 설계 방법은 비이진 LDPC 부호의 이진 최소 거리(binary minimum distance)를 최대화하도록 패리티 검사 행렬의 비이진 원소 값들을 결정한다. BPSK (binary phase-shift keying) 변조 방식 하에서 제안된 방법으로 설계된 비이진 LDPC 부호가 오류 마루(error floor) 영역에서 우수한 성능을 가지는 것을 Monte Carlo 시뮬레이션과 중요도 표본 추출(importance sampling) 기법을 사용하여 검증한다.

한국통신학회논문지•Oct 1, 2013•0 citations
Low-density parity-check (LDPC) 부호의 복호에는 성능이 좋은 합곱 알고리즘(sum-product algorithm; SPA)과 하드웨어가 간단한 비트 반전(bit-flipping; BF) 알고리즘이 많이 쓰이고 있다. 본 논문은 이들 두 가지 방법의 장점을 가지는 저복잡도 고성능 복호 알고리즘을 제안한다. 본 제안된 유연 비트 반전(soft bit-flipping) 알고리즘은 비트와 체크 노드 사이에 전달되는 메시지를 계산하는 데 단순한 비교와 덧셈 연산만을 필요로 하며 연산량이 적다는 장점이 있다. 또한 연산이 완료된 메시지의 활용률을 높이고 비균등 양자화(non-uniform quantization)를 채용하여 1000 내외의 부호 길이에서 SPA 에 0.4dB 근접하는 신호대 잡음비(signal-to-noise ratio)를 달성하였다. 본 논문에서 제안된 알고리즘을 이용하면, 행 무게(row weight)와 열 무게(column weight)가 높아서 종래의 SPA로 구현하기 어려웠던 부호를 비교적 좋은 오율 성능을 유지하면서 실용적으로 구현할 수 있다. ; A high-performance low-complexity decoding algorithm for LDPC codes is proposed in this paper, which has the advantages of both bit-flipping (BF) algorithm and sum-product algorithm (SPA). The proposed soft bit-flipping algorithm requires only simple comparison and addition operations for computing the messages between bit and check nodes, and the amount of those operations is also small. By increasing the utilization ratio of the computed messages and by adopting nonuniform quantization, the signal-to-noise ratio (SNR) gap to the SPA is reduced to 0.4dB at the frame error rate of 10-4 with only 5-bit assignment for quantization. LDPC codes with high column or row weights, which are not suitable for the SPA decoding due to the complexity, can be practically implemented without much worsening the error performance.
LDPC(low density parity check)부호는 합-곱 알고리즘 기반의 반복복호를 통해 Shannon 한계에 근접하는 성능을 보인다. 합곱 알고리즘에서 체크노드와 비트노드의 확률 및 부가정보의 갱신 순서는 스케쥴링 방법에 따라 달라지며 그에 따라 오류정정능력이나 반복복호의 횟수가 달라진다. 기존에 제안된 순차 BP 알고리즘을 사용한 LDPC의 복호는 표준 BP 알고리즘을 바탕으로 복호를 수행했을 경우에 비해 적은 평균반복복호 횟수에도 불구하고 좋은 성능을 가진다고 알려져 있다. 하지만 기존의 연구들에서는 이러한 성능 차이의 원인에 대한 연구는 미비하다. 따라서 본 논문에서는 두 알고리즘의 적용에 따른 LDPC 복호의 성공 여부에 따라 4가지 경우로 분류하고 각 경우를 비교한다. 이를 통해 두 알고리즘의 성능 차이의 원인을 분석하고 그 결과로 성능 차이의 원인이 패리티 검사행렬 내부의 사이클을 구성하는 비트노드들의 확률 값을 갱신할 때 알고리즘에 따른 갱신 과정의 차이에 있음을 보인다. LDPC (low density parity check) code shows near Shannon limit performance by iterative decoding based on sum-product algorithm (SPA). Message updating procedure between variable and check nodes in SPA is done by a scheduling method. LDPC code shows different performance according to scheduling schemes. The conventional researches have been shown that the shuffled BP (belief propagation) algorithm shows better performance than the standard BP algorithm although it needs less number of iterations. However the reason is not analyzed clearly. Therefore the reason of difference in performance according to LDPC decoding algorithms is analyzed in this paper. 4 cases according to satisfaction of parity check condition are considered and compared. As results, the difference in the updating procedure in a cycle in the parity check matrix is considered to be the main reason of performance difference.
본 논문은 저밀도 패리티 검사 (low-density parity-check, LDPC) 부호의 비트 반전 알고리즘(bit-flipping algorithm, BFA)의 부호 오류율 (Word Error Rate, WER) 및 복호 속도 개선에 관한 연구이다. 비트 반전 알고리즘은 비트의 신뢰도를 측정하는 측도인 반전 함수 (flipping function) 값의 임계값을 초과하는 비트를 반전시켜 오류를 정정하는 방식으로 동작한다. 본 논문에서는 반전 함수의 국소 최댓값을 이용해 반전 함수의 임계값을 매 반복마다 적응적으로 설정하여 반복 복호 횟수와 임계값을 찾는데 필요한 정렬 복잡도를 감소시키고, 복호 실패의 주 원인 중 하나인 trapping set 문제를 해결하기 위해 확률적으로 비트를 반전시켜 부호 오류율을 개선하였다.
본 논문에서는 체크 노드 분할에 의한 low-density parity-check(LDPC) 부호의 새로운 직렬 메시지 전달 복호알고리즘을 제안한다. 이 새로운 복호 알고리즘은 특히 적은 반복 횟수에 대하여 기존의 메시지 전달 복호 알고리즘 [3],[7] 의 비트 오율(BER) 성능보다 더 우수한 성능을 보인다. 체크 노드의 분할된 부분 집합의 개수가 증가함에 따라 비트 오율 성능이 보다 좋아진다는 사실을 분석적 결과로 확인할 수 있다. 또한 가우시안 근사화를 이용한 밀도 진화를 이용하여 변수 노드에서 메시지들의 평균값에 대한 재귀 방정식을 유도하고, 모의 실험을 이용하여 분석적인 결과를 검증하였다.
A high-performance low-complexity decoding algorithm for LDPC codes is proposed in this paper, which has the advantages of both bit-flipping (BF) algorithm and sum-product algorithm (SPA). The proposed soft bit-flipping algorithm requires only simple comparison and addition operations for computing the messages between bit and check nodes, and the amount of those operations is also small. By increasing the utilization ratio of the computed messages and by adopting nonuniform quantization, the signal-to-noise ratio (SNR) gap to the SPA is reduced to 0.4dB at the frame error rate of 10-4 with only 5-bit assignment for quantization. LDPC codes with high column or row weights, which are not suitable for the SPA decoding due to the complexity, can be practically implemented without much worsening the error performance.
LDPC(low density parity check)부호는 합-곱 알고리즘 기반의 반복복호를 통해 Shannon 한계에 근접하는 성능을 보인다. 합곱 알고리즘에서 체크노드와 비트노드의 확률 및 부가정보의 갱신 순서는 스케쥴링 방법에 따라 달라지며 그에 따라 오류정정능력이나 반복복호의 횟수가 달라진다. 기존에 제안된 순차 BP 알고리즘을 사용한 LDPC의 복호는 표준 BP 알고리즘을 바탕으로 복호를 수행했을 경우에 비해 적은 평균반복복호 횟수에도 불구하고 좋은 성능을 가진다고 알려져 있다. 하지만 기존의 연구들에서는 이러한 성능 차이의 원인에 대한 연구는 미비하다. 따라서 본 논문에서는 두 알고리즘의 적용에 따른 LDPC 복호의 성공 여부에 따라 4가지 경우로 분류하고 각 경우를 비교한다. 이를 통해 두 알고리즘의 성능 차이의 원인을 분석하고 그 결과로 성능 차이의 원인이 패리티 검사행렬 내부의 사이클을 구성하는 비트노드들의 확률 값을 갱신할 때 알고리즘에 따른 갱신 과정의 차이에 있음을 보인다.
본 논문은 오류 마루 영역에서 우수한 성능을 가지는 비이진 LDPC (low-density parity-check) 부호의 설계 방법을 제안하고 성능을 검증한다. 제안된 설계 방법은 비이진 LDPC 부호의 이진 최소 거리(binary minimum distance)를 최대화하도록 패리티 검사 행렬의 비이진 원소 값들을 결정한다. BPSK (binary phase-shift keying) 변조 방식 하에서 제안된 방법으로 설계된 비이진 LDPC 부호가 오류 마루(error floor) 영역에서 우수한 성능을 가지는 것을 Monte Carlo 시뮬레이션과 중요도 표본 추출(importance sampling) 기법을 사용하여 검증한다.