In this thesis, we analyze tradeoffs of rateless codes between performance and complexity in general noisy channels. While for erasure channels a decoder only needs to use unerased received symbols, for noisy channel the decoder needs to take all received symbols into account because each of them contains some information about the trasmitted message. This, however, increases complexity since more processing is needed. To reduce the complexity, the decoder can discard some unreliable symbols. This results in a performance-complexity tradeoff.
In addition, we consider a scenario where a rateless code operates over a fixed-rate error correcting code with reliable error checking such that the rateless code sees an erasure channel, which is typically used in practice for wireless applications, e.g., in 3GPP MBMS and DVB-H. At the receiver, only succesfully decoded blocks by the fixed-rate code are forwarded to the rateless code decoder. If some soft information of decoded blocks having errors is also forwarded, it can help decode message blocks better. Then the receiver can decode the message blocks with less received blocks. However, this has a drawback since more processing is inevitable and complexity will be higher. This results in another type of performance-complexity tradeoff.
We study the performance-complexity tradeoffs of rateless codes for the two cases. We consider AWGN and fading channels with binary input. We show the optimal tradeoff, and further demonstrate usefulness of the tradeoff by analyzing codes approaching the optimal one closely. We also design good LDPC codes which is suitable as the underlying fixed-rate code in the second scenario by using iterative linear programming and density evolution.
본 논문은 채널 코딩의 일종인 레이트리스 코드에 관한 연구이다. 레이트리스 코드는 코드 길이가 정해진 일반적인 코드와는 달리 코드의 길이가 정해지지 않아서 주어진 메시지를 전송하기 위해 무한하게 코드를 생성시키면서 동시에 전송한다. 코드의 생성 및 전송은 수신단에서 완벽히 정보를 수신하였다는 신호가 올 때까지 계속된다.
Erasure 채널에서는 수신 심볼 상에서 전송되는 메시지에 대한 정보가 완전히 지워지기만 하므로 그러한 심볼들을 복호 과정에서 사용하지 않으면 된다. 그러나 가우시안 채널을 비롯한 잡음이 섞이는 채널은 모든 수신 심볼들이 약간의 정보를 가지고 있기 때문에 일반적으로 모두 복호 과정에서 사용된다. 이 때, 더 적은 신뢰도를 갖는 심볼들을 폐기하고 복호 과정에서 사용하지 않음으로써 복호 복잡도를 줄일 수 있지만, 완벽히 메시지를 수신하기 위해서 심볼을 더 받아야 한다. 따라서 성능은 저하된다고 볼 수 있다. 본 논문에서는 수신 심볼의 폐기 비율을 조절함으로써 얻을 수 있는 성능-복잡도 교환에 대해 알아본다.
본 논문에서는 레이트리스 코드가 또다른 내부 채널 코드와 연계되었을 경우도 고려한다. 이러한 경우는 실제로도 이용되고 있다. 일반적으로 내부 채널 코드에 대해서만 복호를 수행하여 완벽히 복호된 정보만을 레이트리스 코드 복호기로 올려보낸다. 여기서 완벽히 복호되지 않았지만 레이트리스 코드 복호기에서 쓰일 수 있는 추가 정보를 더 올려보낼 경우, 더 적은 수신량으로 복호가 가능해지므로 성능이 개선된다. 그러나 완벽하지 못한 정보를 이용하여 복호하기 때문에 더 많은 계산이 필요하게 된다. 본 논문에서는 추가 정보의 전달 비율을 조절함으로써 얻을 수 있는 성능-복잡도 교환에 대해서도 알아본다.
마지막으로, 내부 채널 코드로서 가장 적합한 LDPC 코드를 설계한다. 전송률이 채널 용량 이하일 때에는 0에 가까운 에러율을 얻을 수 있는 LDPC 코드가 적합하지만, 그렇지 않은 경우 최소의 에러율을 얻을 수 있는 LDPC 코드가 필요하다. 본 논문에서는 그러한 LDPC 코드를 찾도록 한다.
