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

한국통신학회논문지

MIN-SUM 복호화 알고리즘을 이용한 LDPC 오류정정부호의 성능분석

허준

Published Oct 1, 2003• 0 citations
OpenAlex

Abstract

최근에 소개된 Density evolution 기법은 sum-product 알고리즘에서 LDPC부호가 갖는 성능의 한계를 분석하였다.[1] 또한. Iterative decoding 알고리즘에서 전달되는 정보가 Gaussian확률 분포를 갖는 점을 이용하여 기존의 Density evolution 기법을 단순화 시킨 연구결과가 소개되었다 [2]. 한편, LDPC 부호의 한계 성능을 sum-product 가 아닌 min-sum 알고리즘에서 분석한 결과가 최근에 발표되었다. [3] 본 논문에서는 이러한 일련의 연구 결과를 바탕으로 min-sum 알고리즘을 이용하면서 Gaussian 확률 분포 특성을 이용한 Density evolution 기법을 소개한다. 제안된 Density evolution 기법은 기존의 방법보다 적은 계산으로 정확한 threshold를 구할 수 있으며, 그 결과가 numerical simulation 결과와 잘 일치함을 나타내었다.

Related papers

Min-Sum 반복 복호 알고리즘을 사용한 Tree-LDPC의 성능과 수렴 분석

노광석, 허준, 정규혁

본 논문에서는 Tree-LDPC 코드의 성능을 scaling 인자를 이용한 min-sum 알고리즘을 사용하여 나타내고, 그 때의 water fall 영역에서의 점근 성능은 density evolution 기법을 사용하여 나타낸다. Density evolution 기법을 통하여 얻어진 최적의 scaling 인자를 사용하게 되면 min-sum 알고리즘을 사용하는 Tree-LDPC 코드는 sum- product 알고리즘을 사용했을 때와 비슷한 성능을 나타낼 정도로 상당한 성능 이득을 갖게 되는 반면 sum- product 알고리즘을 사용했을 때보다 복호 복잡도가 훨씬 줄어들게 된다. 작은 인터리버 크기를 갖는 Tree-LDPC 복호기를 FPGA(Field Programmable Gate Array)로 구현하였다.

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

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

LDPC 부호의 복호를 위한 양자화 성능과 반복 횟수 통계

서영동, 공민한, 송문규

LDPC 복호기의 성능과 하드웨어 복잡도는 양자화 과정의 설계 변수인 클리핑 임계치(clipping threshold) c th 와 양자화 비트 수 q, 그리고 복호과정의 최대 반복 횟수에 의존한다. 본 논문에서는 이상적인 Min-Sum 알고리즘과 양자화된 Min-Sum 알고리즘을 비교하기 위해서 시뮬레이션을 통해 클리핑 임계치 c th 와 양자화 비트 수 q에 따른 LDPC 부호의 비트 오율 성능을 평가하였다. 시뮬레이션 결과 클리핑 임계치 c th = 2.5, 양자화 비트 수 q = 6일 경우에 이상적인 Min-Sum 알고리즘에 가장 근접한 비트 오율이 나타남을 확인할 수 있었다. 또한 반복 횟수의 통계적 분석을 통한 반복 횟수의 확률 밀도 함수를 이용하여 q와 반복 횟수에 따른 복호 복잡도를 계산하고, 부호어 에러율(word error rate; WER) 성능을 추정하였다. 이상의 결과는 LDPC 복호기 설계에서 부호의 성능과 복호 복잡도 사이의 절충을 위해 사용될 수 있다.

IEEE Transactions on Computers•Feb 1, 2008•0 citations

LDPC 부호 적용을 위한 Tanner의 최소 거리 바운드의 일반화

신민호, 김준성, 송홍엽

LDPC 부호의 검사행렬은 비트노드와 검사노드간의 이분 그래프로 표현된다. Tanner는 그래프상의 인접 행렬 (adjacency matrix) 고유 값을 이용하여, 균일 LDPC 부호의 최소 거리 하 한식 (minimum distance bound)을 유도하였다. 본 논문에서는 Tanner의 결과를 일반화하여, 균일 및 블록 구조를 갖는 비 균일 LDPC 부호에 적용 가능한 두개의 최소 거리 하한식을 유도한다. 첫 번째는 최소 거리 부호 어에 연접한 비트노드들의 관계를 통하여 유도되는 비트노드 기반 하한식이고, 두 번째는 최소 거리 부호 어와 연접한 검사노드들의 관계에서 얻어지는 검사노드 기반 하한식이다 본 논문에서 유도한 하한 식을 통하여 블록 구조를 갖는 비 균일 LDPC 부호의 거리 특성을 그래프의 고유 값들과의 관계로 나타낼 수 있다.

한국통신학회논문지•Oct 1, 2004•0 citations

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

윤태현, 박진태, 주언경

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

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

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

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

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

한국통신학회논문지•Apr 1, 2006•0 citations
최근에 소개된 Density evolution 기법은 sum-product 알고리즘에서 LDPC부호가 갖는 성능의 한계를 분석하였다.[1] 또한. Iterative decoding 알고리즘에서 전달되는 정보가 Gaussian확률 분포를 갖는 점을 이용하여 기존의 Density evolution 기법을 단순화 시킨 연구결과가 소개되었다 [2]. 한편, LDPC 부호의 한계 성능을 sum-product 가 아닌 min-sum 알고리즘에서 분석한 결과가 최근에 발표되었다. [3] 본 논문에서는 이러한 일련의 연구 결과를 바탕으로 min-sum 알고리즘을 이용하면서 Gaussian 확률 분포 특성을 이용한 Density evolution 기법을 소개한다. 제안된 Density evolution 기법은 기존의 방법보다 적은 계산으로 정확한 threshold를 구할 수 있으며, 그 결과가 numerical simulation 결과와 잘 일치함을 나타내었다.
본 논문에서는 Tree-LDPC 코드의 성능을 scaling 인자를 이용한 min-sum 알고리즘을 사용하여 나타내고, 그 때의 water fall 영역에서의 점근 성능은 density evolution 기법을 사용하여 나타낸다. Density evolution 기법을 통하여 얻어진 최적의 scaling 인자를 사용하게 되면 min-sum 알고리즘을 사용하는 Tree-LDPC 코드는 sum- product 알고리즘을 사용했을 때와 비슷한 성능을 나타낼 정도로 상당한 성능 이득을 갖게 되는 반면 sum- product 알고리즘을 사용했을 때보다 복호 복잡도가 훨씬 줄어들게 된다. 작은 인터리버 크기를 갖는 Tree-LDPC 복호기를 FPGA(Field Programmable Gate Array)로 구현하였다.
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.
LDPC 복호기의 성능과 하드웨어 복잡도는 양자화 과정의 설계 변수인 클리핑 임계치(clipping threshold) c th 와 양자화 비트 수 q, 그리고 복호과정의 최대 반복 횟수에 의존한다. 본 논문에서는 이상적인 Min-Sum 알고리즘과 양자화된 Min-Sum 알고리즘을 비교하기 위해서 시뮬레이션을 통해 클리핑 임계치 c th 와 양자화 비트 수 q에 따른 LDPC 부호의 비트 오율 성능을 평가하였다. 시뮬레이션 결과 클리핑 임계치 c th = 2.5, 양자화 비트 수 q = 6일 경우에 이상적인 Min-Sum 알고리즘에 가장 근접한 비트 오율이 나타남을 확인할 수 있었다. 또한 반복 횟수의 통계적 분석을 통한 반복 횟수의 확률 밀도 함수를 이용하여 q와 반복 횟수에 따른 복호 복잡도를 계산하고, 부호어 에러율(word error rate; WER) 성능을 추정하였다. 이상의 결과는 LDPC 복호기 설계에서 부호의 성능과 복호 복잡도 사이의 절충을 위해 사용될 수 있다.
LDPC 부호의 검사행렬은 비트노드와 검사노드간의 이분 그래프로 표현된다. Tanner는 그래프상의 인접 행렬 (adjacency matrix) 고유 값을 이용하여, 균일 LDPC 부호의 최소 거리 하 한식 (minimum distance bound)을 유도하였다. 본 논문에서는 Tanner의 결과를 일반화하여, 균일 및 블록 구조를 갖는 비 균일 LDPC 부호에 적용 가능한 두개의 최소 거리 하한식을 유도한다. 첫 번째는 최소 거리 부호 어에 연접한 비트노드들의 관계를 통하여 유도되는 비트노드 기반 하한식이고, 두 번째는 최소 거리 부호 어와 연접한 검사노드들의 관계에서 얻어지는 검사노드 기반 하한식이다 본 논문에서 유도한 하한 식을 통하여 블록 구조를 갖는 비 균일 LDPC 부호의 거리 특성을 그래프의 고유 값들과의 관계로 나타낼 수 있다.
LDPC(low density parity check)부호는 합-곱 알고리즘 기반의 반복복호를 통해 Shannon 한계에 근접하는 성능을 보인다. 합곱 알고리즘에서 체크노드와 비트노드의 확률 및 부가정보의 갱신 순서는 스케쥴링 방법에 따라 달라지며 그에 따라 오류정정능력이나 반복복호의 횟수가 달라진다. 기존에 제안된 순차 BP 알고리즘을 사용한 LDPC의 복호는 표준 BP 알고리즘을 바탕으로 복호를 수행했을 경우에 비해 적은 평균반복복호 횟수에도 불구하고 좋은 성능을 가진다고 알려져 있다. 하지만 기존의 연구들에서는 이러한 성능 차이의 원인에 대한 연구는 미비하다. 따라서 본 논문에서는 두 알고리즘의 적용에 따른 LDPC 복호의 성공 여부에 따라 4가지 경우로 분류하고 각 경우를 비교한다. 이를 통해 두 알고리즘의 성능 차이의 원인을 분석하고 그 결과로 성능 차이의 원인이 패리티 검사행렬 내부의 사이클을 구성하는 비트노드들의 확률 값을 갱신할 때 알고리즘에 따른 갱신 과정의 차이에 있음을 보인다.
본 논문에서는 체크 노드 분할에 의한 low-density parity-check(LDPC) 부호의 새로운 직렬 메시지 전달 복호알고리즘을 제안한다. 이 새로운 복호 알고리즘은 특히 적은 반복 횟수에 대하여 기존의 메시지 전달 복호 알고리즘 [3],[7] 의 비트 오율(BER) 성능보다 더 우수한 성능을 보인다. 체크 노드의 분할된 부분 집합의 개수가 증가함에 따라 비트 오율 성능이 보다 좋아진다는 사실을 분석적 결과로 확인할 수 있다. 또한 가우시안 근사화를 이용한 밀도 진화를 이용하여 변수 노드에서 메시지들의 평균값에 대한 재귀 방정식을 유도하고, 모의 실험을 이용하여 분석적인 결과를 검증하였다.