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

한국통신학회논문지

Two Stage Early Stopping Belief Propagation Decoding Scheme for Polar Codes

Sungyeol Back, Chan-Soo Park, Young-Jun Ko, Wangrok Oh

Published Jun 30, 2025• 0 citations
Publisher

Abstract

극 부호 (polar code)의 반복 복호 기법인 조기 종료 신뢰 전파 (early stopping belief propagation, ESBP) 복호 기법은 신뢰 전파 (belief propagation, BP) 복호 기법의 높은 연산 복잡도와 긴 복호 지연 시간을 완화하기 위해 제안되었다. ESBP 복호 기법 중 하나인 G-matrix 기반 ESBP는 가장 적은 평균 반복 복호 횟수와 우수한 프레임 오율 (frame error rate) 성능을 보이나 조기 종료 판별에 요구되는 복잡도가 높은 단점이 있다. 본 논문에서는 G-matrix 조기 종료 판별 수행 여부를 판단하는 단계를 추가한 ESBP를 제안한다. 제안하는 기법은 G-matrix 기반 ESBP와 동일한 프레임 오율 성능을 달성하는 동시에 복호 및 조기 종료 판별에 요구되는 연산 복잡도를 크게 낮출 수 있다.

DOI
10.7840/kics.2025.50.6.924

Related papers

Low Complexity Early Stopping Belief Propagation Decoding Scheme for Polar Codes

Sungyeol Back, Young-Jun Ko, Seoyoung Kim +1 more

조기 종료 신뢰 전파 (early stopping belief propagation, ESBP) 복호 기법 중 생성 행렬 (generator matrix, G-matrix) 기반 ESBP는 가장 적은 반복 복호 횟수로 우수한 프레임 오율 (frame error rate, FER) 성능을 달성하지만 조기 종료 판별에 요구되는 복잡도가 크다. 해당 복잡도를 낮추기 위해 서브 팩터 그래프 (sub-factor graph, SFG) 동결 기반 ESBP가 제안되었으나 FER 성능 열화가 발생하고 동결된 SFG의 길이와 위치를 저장하기 위해 많은 레지스터 (register)를 필요로 한다. 본 논문에서는 조기 종료 판별에 가장 적합한 길이를 갖는 SFG를 선별하여 정해진 순서에 따라 SFG별 G-matrix 기반 조기 종료 판별을 수행하는 낮은 복잡도의 ESBP 복호 기법을 제안한다. 제안하는 기법은 조기 종료 판별 조건을 만족한 SFG 내에서는 메시지 업데이트를 생략할 수 있어 복호 복잡도를 낮출 수 있을 뿐만 아니라 조기 종료 판별에 필요한 계산 복잡도를 낮출 수 있으며 G-matrix 기반 ESBP와 유사한 성능을 달성할 수 있다.

한국통신학회논문지•Oct 19, 2026•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 Complexity Early Termination Detector for Polar Code Belief Propagation Decoding

Chungsu Lee, Sungyeol Back, Chansoo Park +1 more

극 부호 (polar codes) 복호 기법 중 하나로 신뢰 전파 복호 기법 (belief propagation decoding)이 제안되었으며 연속 제거 복호 기법 (successive cancellation decoding) 대비 지연시간이 짧은 장점이 있으나 계산 복잡도가 높은 단점이 있다. 이를 보완하기 위해 조기 종료 신뢰 전파 복호 기법이 제안되었으나 조기 종료 여부를 판별하는 데 추가적인 복잡도가 요구된다. 본 논문에서는 극 부호의 신뢰 전파 복호 시 임계 집합 (critical set)의 원소를 포함하는 하위 극 부호 (sub-polar code)의 복호 과정에서 계산되는 로그 우도 비들의 특징을 활용한 낮은 복잡도의 조기 종료 판별기들을 제안한다. 제안하는 조기 종료 판별기들은 기존의 조기 종료 판별기들과 동일한 복호 성능을 제공하며 구현 복잡도를 크게 낮출 수 있다.

한국통신학회논문지•Mar 25, 2024•0 citations

Performance of Successive-Cancellation List Decoding of Extended-Minimum Distance Polar Codes

Daehyeon Ryu, Jae Yoel Kim, Jong-Hwan Kim +1 more

극 부호(polar codes)는 광범위한 이진 입력 이산 무기억 채널(binary input discrete memoryless channel: BI-DMC)에서 채널 용량에 달성하는 것이 이론적으로 증명된 최초의 채널부호이다. 하지만 유한한 길이를 갖는 극 부호는 연속 제거 리스트(successive-cancellation list: SCL) 복호기에서 오류마루(error floor)가 발생하는 문제점이 있다. 선행 연구에 따르면 이 오류마루 현상은 극 부호에 오류 검출 코드(error detection codes) 중 하나인 CRC(Cyclic Redundancy Check) 부호를 연접했을 때 효과적으로 낮출 수 있는 것으로 알려져 있다. 본 논문에서는 외부 부호(outer codes)를 사용하지 않고 극 부호와 RM(Reed-Muller) 부호의 생성 행렬 연관성을 이용하여 기존 극 부호보다 확장된 최소거리를 갖는 극 부호를 제안한다. 그리고 제안된 극 부호와 CRC 부호를 연접한 극 부호의 성능을 비교한다. Polar codes are the first provable error correcting code achieving the symmetric channel capacity in a wide case of binary input discrete memoryless channel(BI-DMC). However, finite length polar codes have an error floor problem with successive-cancellation list(SCL) decoder. From previous works, we can solve this problem by concatenating CRC(Cyclic Redundancy Check) codes. In this paper we propose to make polar codes having extended-minimum distance from original polar codes without outer codes using correlation with generate matrix of polar codes and that of RM(Reed-Muller) codes. And we compare performance of proposed polar codes with that of polar codes concatenating CRC codes.

한국통신학회논문지•Jan 31, 2013•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

저밀도 양자 오류정정부호를 위한 반복 복호 알고리즘에 관한 연구

신정환, 허준

본 논문에서는 기존 오류정정부호의 복호 과정에 사용되는 Belief propagation (BP) 알고리즘을 이용한 저밀도 양자 오류정정 부호의 복호 기법에 대해 기술한다. Depolarizing 채널 가정하에 기존 오류정정부호와 다르게 양자 오류정정부호가 갖는 초기 채널 오류 확률에 의한 성능 열화를 개선하기 위해 초기 채널 오류 확률 정보를 개선하는 기법을 적용하였다. 테너 그래프를 바탕으로 각 체크 노드의 신드롬과 노드의 연결 상태를 고려하여 오류가 발생한 위치를 추적하고 BP 알고리즘에 입력되는 초기 채널 오류 확률 정보를 수정하여 반복 복호 시 발생할 수 있는 성능 열화를 개선하였다.

한국방송미디어공학회 학술발표대회 논문집•Nov 1, 2010•0 citations
극 부호 (polar code)의 반복 복호 기법인 조기 종료 신뢰 전파 (early stopping belief propagation, ESBP) 복호 기법은 신뢰 전파 (belief propagation, BP) 복호 기법의 높은 연산 복잡도와 긴 복호 지연 시간을 완화하기 위해 제안되었다. ESBP 복호 기법 중 하나인 G-matrix 기반 ESBP는 가장 적은 평균 반복 복호 횟수와 우수한 프레임 오율 (frame error rate) 성능을 보이나 조기 종료 판별에 요구되는 복잡도가 높은 단점이 있다. 본 논문에서는 G-matrix 조기 종료 판별 수행 여부를 판단하는 단계를 추가한 ESBP를 제안한다. 제안하는 기법은 G-matrix 기반 ESBP와 동일한 프레임 오율 성능을 달성하는 동시에 복호 및 조기 종료 판별에 요구되는 연산 복잡도를 크게 낮출 수 있다.
조기 종료 신뢰 전파 (early stopping belief propagation, ESBP) 복호 기법 중 생성 행렬 (generator matrix, G-matrix) 기반 ESBP는 가장 적은 반복 복호 횟수로 우수한 프레임 오율 (frame error rate, FER) 성능을 달성하지만 조기 종료 판별에 요구되는 복잡도가 크다. 해당 복잡도를 낮추기 위해 서브 팩터 그래프 (sub-factor graph, SFG) 동결 기반 ESBP가 제안되었으나 FER 성능 열화가 발생하고 동결된 SFG의 길이와 위치를 저장하기 위해 많은 레지스터 (register)를 필요로 한다. 본 논문에서는 조기 종료 판별에 가장 적합한 길이를 갖는 SFG를 선별하여 정해진 순서에 따라 SFG별 G-matrix 기반 조기 종료 판별을 수행하는 낮은 복잡도의 ESBP 복호 기법을 제안한다. 제안하는 기법은 조기 종료 판별 조건을 만족한 SFG 내에서는 메시지 업데이트를 생략할 수 있어 복호 복잡도를 낮출 수 있을 뿐만 아니라 조기 종료 판별에 필요한 계산 복잡도를 낮출 수 있으며 G-matrix 기반 ESBP와 유사한 성능을 달성할 수 있다.
조기 종료 신뢰 전파 (early stopping belief propagation, ESBP) 복호 기법은 반복 복호 과정 중 조기 종료 조건이 만족되면 반복 복호를 종료함으로써 복호 복잡도를 낮출 수 있으나 연속 제거 (successive cancellation) 복호기법 대비 여전히 높은 복호 복잡도를 가진다. 본 논문에서는 극 부호의 최소 해밍 무게를 활용하여 G-matrix 기반 ESBP 복호 기법의 복호 복잡도를 감소시키는 방안을 제안한다. 제안하는 기법은 매 반복 복호 종료 시 추정된 정보 비트를 재부호화한 결과와 추정된 부호어 사이의 해밍 거리가 미리 설정된 임계값보다 낮아질 경우 특정 정보 비트들을 경판정하고 나머지 정보 비트들에 대해서만 반복 복호를 수행함으로써 성능 열화 없이 복호 복잡도를 감소시킬 수 있다.
극 부호 (polar codes) 복호 기법 중 하나로 신뢰 전파 복호 기법 (belief propagation decoding)이 제안되었으며 연속 제거 복호 기법 (successive cancellation decoding) 대비 지연시간이 짧은 장점이 있으나 계산 복잡도가 높은 단점이 있다. 이를 보완하기 위해 조기 종료 신뢰 전파 복호 기법이 제안되었으나 조기 종료 여부를 판별하는 데 추가적인 복잡도가 요구된다. 본 논문에서는 극 부호의 신뢰 전파 복호 시 임계 집합 (critical set)의 원소를 포함하는 하위 극 부호 (sub-polar code)의 복호 과정에서 계산되는 로그 우도 비들의 특징을 활용한 낮은 복잡도의 조기 종료 판별기들을 제안한다. 제안하는 조기 종료 판별기들은 기존의 조기 종료 판별기들과 동일한 복호 성능을 제공하며 구현 복잡도를 크게 낮출 수 있다.
극 부호(polar codes)는 광범위한 이진 입력 이산 무기억 채널(binary input discrete memoryless channel: BI-DMC)에서 채널 용량에 달성하는 것이 이론적으로 증명된 최초의 채널부호이다. 하지만 유한한 길이를 갖는 극 부호는 연속 제거 리스트(successive-cancellation list: SCL) 복호기에서 오류마루(error floor)가 발생하는 문제점이 있다. 선행 연구에 따르면 이 오류마루 현상은 극 부호에 오류 검출 코드(error detection codes) 중 하나인 CRC(Cyclic Redundancy Check) 부호를 연접했을 때 효과적으로 낮출 수 있는 것으로 알려져 있다. 본 논문에서는 외부 부호(outer codes)를 사용하지 않고 극 부호와 RM(Reed-Muller) 부호의 생성 행렬 연관성을 이용하여 기존 극 부호보다 확장된 최소거리를 갖는 극 부호를 제안한다. 그리고 제안된 극 부호와 CRC 부호를 연접한 극 부호의 성능을 비교한다. Polar codes are the first provable error correcting code achieving the symmetric channel capacity in a wide case of binary input discrete memoryless channel(BI-DMC). However, finite length polar codes have an error floor problem with successive-cancellation list(SCL) decoder. From previous works, we can solve this problem by concatenating CRC(Cyclic Redundancy Check) codes. In this paper we propose to make polar codes having extended-minimum distance from original polar codes without outer codes using correlation with generate matrix of polar codes and that of RM(Reed-Muller) codes. And we compare performance of proposed polar codes with that of polar codes concatenating CRC codes.
본 논문에서는 기존 오류정정부호의 복호 과정에 사용되는 Belief propagation (BP) 알고리즘을 이용한 저밀도 양자 오류정정 부호의 복호 기법에 대해 기술한다. Depolarizing 채널 가정하에 기존 오류정정부호와 다르게 양자 오류정정부호가 갖는 초기 채널 오류 확률에 의한 성능 열화를 개선하기 위해 초기 채널 오류 확률 정보를 개선하는 기법을 적용하였다. 테너 그래프를 바탕으로 각 체크 노드의 신드롬과 노드의 연결 상태를 고려하여 오류가 발생한 위치를 추적하고 BP 알고리즘에 입력되는 초기 채널 오류 확률 정보를 수정하여 반복 복호 시 발생할 수 있는 성능 열화를 개선하였다.