Design of Irregular SC-LDPC Codes Based on Various Optimization Techniques

Abstract

이 학위 논문에서는, i) 선형 계획법을 이용하여 비균일 차수 분포를 갖는 spatially-coupled low-density parity check (SC-LDPC) 부호의 설계 방법 및 ii) 차동 진화 알고리즘을 이용하여 SC-LDPC 부호의 부호율 손실 완화 방법들이 연구되었다.

먼저, 선형 계획법을 이용하여 비균일 차수 분포를 갖는 SC-LDPC 부호 설계 방법을 제안한다. 일반적으로, SC-LDPC 부호의 밀도 진화 수식이 다 차원적이기 때문에 비균일 차수 분포를 갖는 SC-LDPC 부호를 낮은 복잡도로 설계하는 것은 어렵다. 제안 하는 방법은 차수 분포의 지역별 설계, 입출력 메세지 관계의 계산, 적절한 목적함수 선정과 같은 세가지 방법론에 기반하여 위와 같은 문제를 해결하고 있다. 이러한 방법들을 이용하여 이진 소실 채널에서 비균일 SC-LDPC 부호의 차수 분포들을 낮은 복잡도의 선형 계획법으로 설계할 수 있다. 제안하는 비균일 SC-LDPC 부호는 점근적 그리고 유한한 길이에서 모두 균일 SC-LDPC 부호에 보다 더 좋은 성능을 보인다. 또한 제안하는 비균일 SC-LDPC 부호가 동일 길이를 갖는 최적화된 비균일 블록 LDPC 부호보다 성능이 더 좋음을 확인하였다. 이는 제안하는 설계 알고리즘이 임계값에 다가가는 블록 LDPC 부호 설계하는 새로운 종류의 방법을 제공한다는 것을 의미한다.

두 번째로, 유한한 길이에서 성능 열화가 없는 SC-LDPC 부호의 부호율 손실 완화 방법이 제안된다. SC-LDPC 부호의 부호율 손실은 해결되어야 할 중요한 문제로써 부호율 손실을 완화하기 위한 한가지 방법으로 경계 확인 노드에 비균일 차수 분포를 갖는 추가적인 변수 노드를 연결 하는 것이 제안되었다. 이전 연구에서는 비균일 차수 분포를 BP 임계값이 손실되지 않는 제한 조건을 갖는 선형 계획법으로 최적화 되었다. 하지만 그러한 방법으로 얻은 비균일 차수 분포는 유한한 길이에서의 성능열화를 야기시킨다. 이러한 문제를 해결하기 위해서 평균 그래프 진화를 이용하여 새로운 제한 조건을 제안하고 이 제한 조건을 차동 진화 알고리즘에 기반한 제안하는 설계 알고리즘에 반영하였다. 이를 통해서 SC-LDPC 부호의 부호율 손실은 54% 완화되면서 유한한 길이의 손해가 없는 차수 분포를 얻었다. 또한, 설계된 부호와 기존 부호를 동일 부호율에서 비교한 다면 부호율 손실 완화는 성능 개선으로 이어진다는 것을 보여주었다.

In this dissertation, two main contributions are given as i) design methods of irregular spatially-coupled low-density parity-check (SC-LDPC) codes with non-uniform degree distributions by linear programming (LP) and ii) rate-loss mitigation methods of SC-LDPC codes without degradation of the finite-length code performance using differential evolution algorithms.

First, new design algorithms of irregular SC-LDPC codes with non-uniform degree distributions are proposed using LP optimization techniques. In general, irregular SC-LDPC codes with non-uniform degree distributions are difficult to design with low complexity because their density evolution equations are multi-dimensional.

To overcome the problem, proposed design algorithms are based on three main ideas

a local design of degree distributions, pre-computation of the input/output message relationship, and selection of a proper objective function. These ideas make it possible to design degree distributions of irregular SC-LDPC codes by solving low complexity LP problems over the binary erasure channel (BEC). It is shown that the proposed irregular SC-LDPC codes designed by the proposed algorithms are superior to regular SC-LDPC codes in terms of both asymptotic and finite-length performances over the BEC. It is also confirmed that the proposed irregular SC-LDPC code achieves better performance compared to an optimized irregular block LDPC code in the same blocklength, which implies that the proposed design algorithms also provide a new way to construct capacity-approaching block LDPC codes.

Second, new optimization methods are provided to mitigate the rate-loss of SC-LDPC codes without finite-length performance degradation over the binary erasure channel. In the SC-LDPC codes, the rate-loss of SC-LDPC codes is one of the main issues to be addressed. One way to mitigate the rate-loss is attaching additional variable nodes with an irregular degree distribution to the boundary check nodes, where the degree distribution of additional variable nodes is optimized with a constraint that the BP threshold should not be degraded by attaching them. However, it is observed that the degree distribution obtained with the BP threshold constraint degrades the finite-length performance. In order to maintain the finite-length performance, a proper design constraint is given using the expected graph evolution and then the constraint is imposed on the proposed optimization method, which is based on differential evolution algorithms. From the well-designed degree distribution, the rate-loss of SC-LDPC codes is mitigated by 54% without sacrificing the finite-length performance. It is also shown that the rate-loss mitigation can be translated into a performance improvement if the conventional SC-LDPC codes and the proposed SC-LDPC codes are compared for the same code-rate.