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

한국통신학회논문지

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

Myungin Kim, Jeongseok Ha

Published May 27, 2021• 0 citations
Publisher

Abstract

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

DOI
10.7840/kics.2021.46.5.810

Related papers

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

조준호, 성원용

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.

•May 1, 2009•0 citations

가중치가 부과된 Bit-flipping 기법을 이용한 LDPC 코딩

조경현, 나극환

본 논문에서는 통신 시스템에서 채널 전송에 의한 데이터의 오류 체크와 정정문제에 대해서 제안하였다. 제안된 LDPC 코드는 VDSL 시스템에서의 AWGN 채널 모델링에 의해 최소화된 채널 에러를 위해 사용된다. LDPC 코드는 낮은 밀도 패리티 비트를 사용하기 때문에, 수학적인 복잡도가 낮고 처리 시간이 짧다. 또한 LDPC 코드의 성능은 반복 복호 알고리즘에서 긴 코드 워드에 대해 터보 코드보다 더 나은 성능을 가지고 있다 제안된 시스템의 송신기에서 발생 행렬에 의해서 부호어가 발생되고, 수신기에서 사용된 에러 정정 알고리즘은 가중치를 갖는 Bit-flipping 방식이다. 이 방식은 기존의 Bit-flipping 방식과 달리 더 정확한 에러를 검출하고, 정정하기 위해 발생된 패리티 비트에 대해서 가중치를 주어 에러 정정을 하는 방식이다. 제안된 가중치를 갖는 Bit-flipping 알고리즘은 기존의 Bit-flipping 알고리즘에 비해서 1 ㏈ 이상의 이득 개선을 확인할 수 있었다.

전자공학회논문지-IE•Dec 1, 2006•0 citations

New Message-Passing Decoding Algorithm of LDPC Codes by Partitioning Check Nodes

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

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

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

이차원 코드를 위한 개선된 LDPC 코드

김현경, 정철호, 한탁돈

디지털 신호 및 전송부호의 오류검출에는 예전부터 패리티 체크가 사용되어 왔다. 그러나 패리티 체크기법은 구현 및 알고리즘이 단순, 간결한 우수성이 있지만 특정 데이터 비트의 경우 오류 검출이 불가능하다는 문제점을 가지고 있다. 이후 패리티 체크 기법은 해밍 코드 및 채널 오류 정정을 위한 LDPC 코드와 같은 다양한 오류검출 및 정정 알고리즘에 적용되어 발전되어 왔으며, 그 중 LDPC 코드의 bit-flipping 알고리즘에서는 패리티 기법을 반복적으로 적용하는 방식을 택하고 있다. 본 논문에서는 이러한 채널 오류 정정을 위한 LDPC의 bit-flipping 알고리즘을 이차원 코드에 적용하고, 이 때 bit-flipping 알고리즘이 가지고 있는 문제점을 보완할 수 있는 개선된 LDPC 코드를 제안한다.

한국정보과학회 학술발표논문집•Nov 1, 2005•0 citations

Improved Successive Cancellation Flip Decoding of Polar Codes Based on Bit Interleaver

Haseong Kim, Hyunjee Lee, Hosung Park

본 논문에서는 기존 연속적 제거 반전 복호보다 계산 복잡도를 감소시키기 위해서 비트 인터리버 기반 연속적 제거 반전 복호를 제안한다. 또한, 반전될 비트를 선택하는데 밀도 진화 확률을 사용한다. 높은 Eb/N0에 대하여, 제안하는 복호는 기존 복호와 유사한 오류 정정 성능을 가지면서, 오류가 발생한 프레임에 대해서 기존 복호보다 최소 35% 감소한 계산 복잡도를 가진다.

한국통신학회논문지•Jan 31, 2019•0 citations

Partial Early Stopping Scheme for Polar Codes

Chan-Soo Park, Sungyeol Back, Young-Jun Ko +1 more

조기 종료 신뢰 전파 (early stopping belief propagation, ESBP) 복호 기법은 반복 복호 과정 중 조기 종료 조건이 만족되면 반복 복호를 종료함으로써 복호 복잡도를 낮출 수 있으나 연속 제거 (successive cancellation) 복호기법 대비 여전히 높은 복호 복잡도를 가진다. 본 논문에서는 극 부호의 최소 해밍 무게를 활용하여 G-matrix 기반 ESBP 복호 기법의 복호 복잡도를 감소시키는 방안을 제안한다. 제안하는 기법은 매 반복 복호 종료 시 추정된 정보 비트를 재부호화한 결과와 추정된 부호어 사이의 해밍 거리가 미리 설정된 임계값보다 낮아질 경우 특정 정보 비트들을 경판정하고 나머지 정보 비트들에 대해서만 반복 복호를 수행함으로써 성능 열화 없이 복호 복잡도를 감소시킬 수 있다.

한국통신학회논문지•Jan 31, 2025•0 citations
본 논문은 저밀도 패리티 검사 (low-density parity-check, LDPC) 부호의 비트 반전 알고리즘(bit-flipping algorithm, BFA)의 부호 오류율 (Word Error Rate, WER) 및 복호 속도 개선에 관한 연구이다. 비트 반전 알고리즘은 비트의 신뢰도를 측정하는 측도인 반전 함수 (flipping function) 값의 임계값을 초과하는 비트를 반전시켜 오류를 정정하는 방식으로 동작한다. 본 논문에서는 반전 함수의 국소 최댓값을 이용해 반전 함수의 임계값을 매 반복마다 적응적으로 설정하여 반복 복호 횟수와 임계값을 찾는데 필요한 정렬 복잡도를 감소시키고, 복호 실패의 주 원인 중 하나인 trapping set 문제를 해결하기 위해 확률적으로 비트를 반전시켜 부호 오류율을 개선하였다.
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 코드는 VDSL 시스템에서의 AWGN 채널 모델링에 의해 최소화된 채널 에러를 위해 사용된다. LDPC 코드는 낮은 밀도 패리티 비트를 사용하기 때문에, 수학적인 복잡도가 낮고 처리 시간이 짧다. 또한 LDPC 코드의 성능은 반복 복호 알고리즘에서 긴 코드 워드에 대해 터보 코드보다 더 나은 성능을 가지고 있다 제안된 시스템의 송신기에서 발생 행렬에 의해서 부호어가 발생되고, 수신기에서 사용된 에러 정정 알고리즘은 가중치를 갖는 Bit-flipping 방식이다. 이 방식은 기존의 Bit-flipping 방식과 달리 더 정확한 에러를 검출하고, 정정하기 위해 발생된 패리티 비트에 대해서 가중치를 주어 에러 정정을 하는 방식이다. 제안된 가중치를 갖는 Bit-flipping 알고리즘은 기존의 Bit-flipping 알고리즘에 비해서 1 ㏈ 이상의 이득 개선을 확인할 수 있었다.
본 논문에서는 체크 노드 분할에 의한 low-density parity-check(LDPC) 부호의 새로운 직렬 메시지 전달 복호알고리즘을 제안한다. 이 새로운 복호 알고리즘은 특히 적은 반복 횟수에 대하여 기존의 메시지 전달 복호 알고리즘 [3],[7] 의 비트 오율(BER) 성능보다 더 우수한 성능을 보인다. 체크 노드의 분할된 부분 집합의 개수가 증가함에 따라 비트 오율 성능이 보다 좋아진다는 사실을 분석적 결과로 확인할 수 있다. 또한 가우시안 근사화를 이용한 밀도 진화를 이용하여 변수 노드에서 메시지들의 평균값에 대한 재귀 방정식을 유도하고, 모의 실험을 이용하여 분석적인 결과를 검증하였다.
디지털 신호 및 전송부호의 오류검출에는 예전부터 패리티 체크가 사용되어 왔다. 그러나 패리티 체크기법은 구현 및 알고리즘이 단순, 간결한 우수성이 있지만 특정 데이터 비트의 경우 오류 검출이 불가능하다는 문제점을 가지고 있다. 이후 패리티 체크 기법은 해밍 코드 및 채널 오류 정정을 위한 LDPC 코드와 같은 다양한 오류검출 및 정정 알고리즘에 적용되어 발전되어 왔으며, 그 중 LDPC 코드의 bit-flipping 알고리즘에서는 패리티 기법을 반복적으로 적용하는 방식을 택하고 있다. 본 논문에서는 이러한 채널 오류 정정을 위한 LDPC의 bit-flipping 알고리즘을 이차원 코드에 적용하고, 이 때 bit-flipping 알고리즘이 가지고 있는 문제점을 보완할 수 있는 개선된 LDPC 코드를 제안한다.
조기 종료 신뢰 전파 (early stopping belief propagation, ESBP) 복호 기법은 반복 복호 과정 중 조기 종료 조건이 만족되면 반복 복호를 종료함으로써 복호 복잡도를 낮출 수 있으나 연속 제거 (successive cancellation) 복호기법 대비 여전히 높은 복호 복잡도를 가진다. 본 논문에서는 극 부호의 최소 해밍 무게를 활용하여 G-matrix 기반 ESBP 복호 기법의 복호 복잡도를 감소시키는 방안을 제안한다. 제안하는 기법은 매 반복 복호 종료 시 추정된 정보 비트를 재부호화한 결과와 추정된 부호어 사이의 해밍 거리가 미리 설정된 임계값보다 낮아질 경우 특정 정보 비트들을 경판정하고 나머지 정보 비트들에 대해서만 반복 복호를 수행함으로써 성능 열화 없이 복호 복잡도를 감소시킬 수 있다.