Although Low-density parity-check (LDPC) codes have superb error correcting ability, in order to be a viable solution in practical systems such as a Hybrid Automatic Repeat reQuest (HARQ), besides the performance, there are a few additional issues such as decoding complexity and decoding latency. In this thesis, we focus on the considerations of LDPC codes to be adequate for HARQ system.
For the first approach, we propose a $\It{stopping criterion}$ for the decoding failure. Actually, LDPC codes have an inherent stopping criterion, the parity-check constraints (equations). By testing the parity-check constraints, LDPC decoders can detect successful decoding and stop their decoding, which is, however, not possible with Turbo codes. In the first part, we propose a stopping criterion to predict decoding failure of LDPC codes, instead of detecting successful decoding. If the decoder predicts the decoding failure in advance, the receiver can more rapidly response to the transmitter and request for additional parity bits with HARQ system, which reduces overall system latency. The receiver can also save power consumption by avoiding the unnecessary decoder iterations. The proposed stopping criterion makes use of the variations of the number of satisfied parity-check constraints in the Belief-Propagation (BP) decoding which is always tested by the conventional BP decoder to detect successful decoding. Thus, the proposed stopping criterion does not require any additional complexity. Besides the stopping criterion, the counting the number of satisfied parity-check constraints shows behaviors of the BP decoding, which comes, otherwise, from the observations of the changes of log-likelihood ratio (LLR) values in multi-bit resolution with additional complexity.
Secondly, we deal with novel HARQ scheme called a $\It{partial chase combining}$, which retransmits partial bits among whole codeword for the retransmission requests. Of existing HARQ scheme, the type-I HARQ system has a problem of low throughput while the type-II HARQ system has a problem of high design complexity. Since the partial chase combining scheme is based on the type-I HARQ scheme, however, its implementation is simple as like the type-I HARQ scheme. In addition, its throughput is much more improved than the type-I HARQ scheme by retransmitting only highly effective bits. In the second part, we analyze the partial chase combining and derive the recursive equations for mean values of messages at the check nodes and the variable nodes with Gaussian approximation. Using these derived equations and a linear programming, we propose the optimization algorithm selecting the retransmission portions.
저밀도 패리티 (LDPC) 부호는 에러정정능력이 우수한 부호로 잘 알려져있다. 하지만 LDPC 부호가 Hybrid Automatic Repeat reQuest(HARQ)와 같은 실제 시스템에서 실용가능한 부호가 되기 위해서는 복호 지연이나 복호 복잡도같은 문제들을 해결하는 것이 필요하다. 본 연구에서는 LDPC 부호가 HARQ 시스템에 적합한 부호가 되기위하여 고려해야할 사항들에 대하여 다룬다.
첫번째 고려사항으로 우리는 복호 실패에 대한 멈춤기준 (stopping criterion) 알고리즘을 제안한다. 실제 LDPC 부호는 패리티체크 제약 (parity-check constraint)이라는 내재적인 멈춤기준을 갖고 있다. 즉, LDPC 부호는 패리티체크 제약 테스트를 통해 복호 성공을 인지하고 테스트 만족시 복호를 멈추게 한다. 하지만 복호 실패시에는 내부적인 멈춤기준이 없어서 최대 반복횟수까지 복호가 진행되어야한다. 따라서 우리는 LDPC 부호에서 복호실패가 발생하는 경우에 대한 멈춤 기준을 제시한다. 만약에 복호기가 미리 복호 실패를 예상할 수 있게 되고 추가적인 패리티 비트를 빨리 받을 수 있게 된다. 이는 HARQ 시스템의 전체적인 시스템 지연을 줄이는 효과를 가져오게된다. 더군다나 수신기에서는 불필요한 반복을 피함에 의해 전력소모를 줄일수 있게된다. 제안된 멈춤기준은 BP 복호기가 성공적인 복호를 인지하기 위하여 항상 테스트하는 패리티체크를 만족하는 제약의 개수를 이용한다. 따라서 제안된 멈춤기준은 어떤 추가적인 복잡도를 요구하지 않게 된다. 또한 기존에는 BP 복호기의 움직을 관찰하는데 추가적인 복잡도를 요구하는 부동 소수점으로 구성된 Log-Likelihood Ratio(LLR) 값의 변화를 사용하였지만, 본 연구에서는 추가적인 복잡도가 없는 패리티체크를 만족하는 제약의 개수가 이를 완벽하게 똑같이 표현할 수 있음을 보여준다.
두번째로 재전송 요구시 전체부호중 일부분만 재전송하는 부분 체이스 결합법 (partial chase combining) 이라고 불리는 새로운 HARQ 시스템에 대하여 다루었다. 기존의 HARQ 시스템중 type-I HARQ 시스템은 throughput이 낮다는 문제점을 갖고있고, type-II HARQ 시스템은 적절한 부호 디자인이 복잡하다는 문제점을 갖고있다. 반면 부분 체이스 결합법은 type-I HARQ 시스템처럼 기존에 전송된 비트를 재전송하기때문에 시스템 구현이 간단하고, 전체 비트를 모두 재전송하는 type-I HARQ 시스템과 달리 효과적인 비트만을 재전송하기 때문에 전체적인 시스템 throughput을 높일 수 있다느 장점이 있다. 본 연구에서 우리는 부분 체이스 결합법에서 효과적인 재전송 비트를 선택하기 위한 방법을 Gaussian 어림법 (Gaussian approximation)을 이용하여 분석한다. 또한 분석을 통하여 얻은 수식들과 선형 프로그래밍 (linear programming) 방법을 이용하여 효과적인 재전송 비트를 선택하는 최적 알고리즘을 제시한다.
