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

한국통신학회논문지

Low Complexity Early Stopping Belief Propagation Decoding Scheme for Polar Codes

Sungyeol Back, Young-Jun Ko, Seoyoung Kim, Wangrok Oh

Published Oct 19, 2026• 0 citations
Publisher

Abstract

조기 종료 신뢰 전파 (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와 유사한 성능을 달성할 수 있다.

DOI
10.7840/kics.2026.51.10.1942

Related papers

Two Stage Early Stopping Belief Propagation Decoding Scheme for Polar Codes

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

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

한국통신학회논문지•Jun 30, 2025•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

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

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

An Iterative Soft-Decision Decoding Algorithm of Block Codes Using Reliability Values

Yong-Geol Shim

본 논문에서는 블록 부호의 반복적 연판정 복호 알고리즘을 제안하였다. 최초의 경판정 복호 결과에 대한 분석을 바탕으로 후보 부호어들을 효율적으로 탐색할 수 있는 방법을 개발하였다. 복호의 복잡도를 줄이고 에러 확률을 감소시키기 위하여 적은 갯수의 후보 부호어들을 선택한다. 이 때, 수신 신호로부터 가까운 거리에 존재하는 부호어가 포함되어 있을 확률이 크도록 후보 부호어들을 선택한다. 선택된 후보 부호어까지의 거리를 계산하여 가장 가까운 후보 부호어를 복호 결과로 선정한다. 제안된 방법에 의하여 신뢰도 값이 작은 비트들을 에러 패턴에 포함시키게 하는 후보 부호어를 탐색할 수 있으며, 이미 탐색된 후보 부호어가 다시 선정되는 경우를 방지할 수 있다. (23, 12) Golay 부호에 대하여 시뮬레이션을 수행하고 그 결과를 제시하였다. 복호의 복잡도가 현저히 감소되었고, 블록 에러 확률이 저하된 사실을 시뮬레이션 견과에서 확인한 수 있었다. An iterative soft-decision decoding algorithm of block codes is proposed. With careful examinations of the first hard-decision decoding result, the candidate codewords are efficiently searched for. An approach to reducing decoding complexity and lowering error probability is to select a small number of candidate codewords. With high probability, we include the codewords which are at the short distance from the received signal. The decoder then computes the distance to each of the candidate codewords and selects the codeword which is the closest. We can search for the candidate codewords which make the error patterns contain the bits with small reliability values. Also, we can reduce the cases that we select the same candidate codeword already searched for. Computer simulation results are presented for (23,12) Golay code. They show that decoding complexity is considerably reduced and the block error probability is lowered.

The KIPS Transactions PartC•Feb 1, 2004•0 citations
조기 종료 신뢰 전파 (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와 유사한 성능을 달성할 수 있다.
극 부호 (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) 복호 기법은 반복 복호 과정 중 조기 종료 조건이 만족되면 반복 복호를 종료함으로써 복호 복잡도를 낮출 수 있으나 연속 제거 (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.
본 논문에서는 블록 부호의 반복적 연판정 복호 알고리즘을 제안하였다. 최초의 경판정 복호 결과에 대한 분석을 바탕으로 후보 부호어들을 효율적으로 탐색할 수 있는 방법을 개발하였다. 복호의 복잡도를 줄이고 에러 확률을 감소시키기 위하여 적은 갯수의 후보 부호어들을 선택한다. 이 때, 수신 신호로부터 가까운 거리에 존재하는 부호어가 포함되어 있을 확률이 크도록 후보 부호어들을 선택한다. 선택된 후보 부호어까지의 거리를 계산하여 가장 가까운 후보 부호어를 복호 결과로 선정한다. 제안된 방법에 의하여 신뢰도 값이 작은 비트들을 에러 패턴에 포함시키게 하는 후보 부호어를 탐색할 수 있으며, 이미 탐색된 후보 부호어가 다시 선정되는 경우를 방지할 수 있다. (23, 12) Golay 부호에 대하여 시뮬레이션을 수행하고 그 결과를 제시하였다. 복호의 복잡도가 현저히 감소되었고, 블록 에러 확률이 저하된 사실을 시뮬레이션 견과에서 확인한 수 있었다. An iterative soft-decision decoding algorithm of block codes is proposed. With careful examinations of the first hard-decision decoding result, the candidate codewords are efficiently searched for. An approach to reducing decoding complexity and lowering error probability is to select a small number of candidate codewords. With high probability, we include the codewords which are at the short distance from the received signal. The decoder then computes the distance to each of the candidate codewords and selects the codeword which is the closest. We can search for the candidate codewords which make the error patterns contain the bits with small reliability values. Also, we can reduce the cases that we select the same candidate codeword already searched for. Computer simulation results are presented for (23,12) Golay code. They show that decoding complexity is considerably reduced and the block error probability is lowered.