An Efficient Implementation of LT Codes Based on Its Optimized Degree Distribution Function

Abstract

본 논문은 네트워크를 통한 대량의 데이터 전송 시 발생할 수 있는 문제점을 채널 코딩의 관점에서 검토한다. 채널 코딩은 통신 채널 상 데이터 전송 시 발생할 수 있는 통신에러를 줄이기 때문에 통신 채널에서 하나의 패러다임으로 제기 되고 있다. 최근에는 새로운 채널 코딩 방식이 소실 채널 상에서도 사용되어 지고 있다. 본 논문에서는 LDPC 코드와 파운틴 코드를 포함하고, 그 중 보다 더 정확한 파운틴 코드에 초점을 맞추고 있다. 이전 연구에는 정확한 파운틴 코드의 개념을 내포하는 코드로 Reed Solomon 과 LDPC 코드 등의 방법이 있었다. 몇 년 전에는 새로운 코딩 방식으로 LT 코드가 제안되었다. LT 코드는 정확한 파운틴 코드이고, 이득이 높고 효율이 좋은 엔코더와 디코더 알고리즘이다. 또한 LT 코드는 첫 번째의 Rateless 코딩 방식이며, 그 중요성은 통신 표준들의 도입시 중요하게 여겨진다. 이에 본 논문을 통해 정도 분호 함수로 알려진 이러한 코드를 이용하여, 성능 지향적인 부분 중에 가장 중요한 한 부분을 최적화하였다. 우리는 정도 분포 함수의 최적화를 위한 새로운 분석을 제시하고, 이전에 정의된 학위 분포함수 또한 우리의 분석을 따르는 것을 보여준다. 분석을 바탕으로, 스케일이 없는 LT 코드와 랜덤 LT 코드로 총 두가지의 카테고리로 LT 코드를 분류한다. 두 카테고리 코드는 모두 Power Law 로 연결된다. 그리고 본 논문에서 스케일이 없는 LT 코드를 위한 두 가지 새로운 정도 분포를 제안했고, 그것은 이러한 코드의 성능을 대폭 향상시킬 수 있다. 그리고 우리는 또한 패이딩 채널을 통한 LT 코드의 성능평가를 위한 작업을 제시하였다. 또한 CFC(Concatenated Fountain Code)로 알려진 LT 코드의 향상된 버전을 제안하고 평가한다. 또한 기존의 LT 코드와 CFC 의 성능을 비교한다. 마지막으로, LT 코드를 위한 하드웨어 구조를 제안하는데, 그것은 정도 분포 함수를 사용하지 않고, 직접적으로 하드웨어에 매핑하는 노드와 에지 사이의 연결 정보를 포함하고 있다. 이러한 접근 방식은 LT 코드에 대해 서로 다른 최적의 정도 분포 함수 활용에 도움이 된다. 그리고 하드웨어를 통한 최적의 정도분포 함수를 구현하고 그 함수에 대한 영향을 확인하였다.|This thesis examines the problems associated to transfer of bulk amount of data in the networks from the perspective of channel coding. As channel coding is one paradigm in the communication channels, which help in reducing errors when information symbols are transmitted over communication channels. Recently, some new channel coding schemes are employed for erasure channels, these includes: LDPC codes and Fountain codes. The focus of this thesis is the codes that approximate the fountain codes. Previously, there were some schemes that approximate the Fountain codes concept, the famous among which includes: Reed Solomon and LDPC codes. Few years back a new coding scheme is proposed known as LT codes that approximates the fountain codes and have the benefit of robust and efficient encoding and decoding algorithms. Also these are the first rateless coding scheme and its importance is evident from their adoption in the communication standards. In this thesis work, we optimized one of the crucial and performance oriented part of these codes known as degree distribution functions. A well defined degree distribution function in the LT codes increases itsperformance to many folds. We have presented a new analysis for optimization of the degree distribution function, and shown that the previously defined degree distribution functions also follow our analysis. Based on the analysis, we have categorized the LT codes in to two categories that include: Free Scale LT codes and Random LT codes. Both the categories of the codes are associated with Power Law. We have proposed two new degree distributions for Free Scale LT codes that significantly enhance the performance of these codes. We have also presented an evaluation work that evaluates the performance of the LT codes over fading channels. An enhance version of the LT codes also known as Concatenated Fountain Codes (CFC) are proposed and evaluated. The performance of the conventional LT codes and CFC are also compared. Finally, hardware architecture for LT Codec is proposed in which the connection information between the nodes and edges are directly mapped on the hardware instead using the degree distribution function in hardware. This approach helps in utilizing the different optimal degree distribution functions for LT codes. The impacts of optimal degree distribution function on different features of the hardware are considered.