Polar codes achieve channel capacity of binary-input discrete memoryless symmetric (B-DMS) channels. Unlike random codes, polar codes have explicit structure. Because of this structure, polar codes can be encoded and decoded recursively. However, there have been no recursive construction algorithms for polar codes other than binary erasure channel. This thesis proposes algorithm that can construct code recursively on any binary symmetric discrete memoryless channels. The proposed algorithm calculates maximum likelihood error probability as well as Bhattacharyya parameter. Using these two parameters, extreme cases of channels were defined. Also it is shown that binary erasure channel (BEC) and binary symmetric channel (BSC) are extreme cases of B-DMS channels. The proposed algorithm measures distance between a given channel and BSC/BEC to estimate unknown channel parameters. The proposed algorithm works in low complexity while there is no significant performance degradation compared to previous works. Also it is shown that the concept of extremal channel can provide further insights on the channel polarization effect.
극 부호는 이산 무기억 채널에서 채널 용량을 달성한다고 알려진 이후 많은 주목을 받았다. 극 부호는 재귀적인 구조로 인해 낮은 복잡도로 부호화 및 복호화가 가능하다. 하지만 극 부호 설계 알고리즘의 경우 이산 소거 채널 이외의 채널에서는 저 복잡도의 재귀적 알고리즘이 알려져 있지 않다. 본 논문에서는 채널의 신뢰도를 나타내기 위해 기존에 사용되던 바타차리야 파라미터에 추가적으로 최대 우도 판별 오류율을 도입하였다. 이 두 파라미터를 활용해 극단 채널이라는 것을 정의하고 이산 소거 채널과 이산 대칭 채널이 이산 무기억 채널의 극단 채널이라는 것을 밝혔다. 주어진 채널이 두 극단 사이 중 어디에 위치 하는지를 추정함으로써 재귀적으로 채널의 파라미터들을 계산하는 알고리즘을 제시하였다. 제안된 알고리즘이 기존에 알려진 방식과 비교하여 낮은 복잡도로 동작하면서 성능 열화가 없음을 보였으며 실시간으로 변하는 채널 환경에서 최적화된 극 부호를 설계할 수 있음을 보였다. 또한 채널의 집합과 극단 채널의 개념을 도입하여 채널 분극화 현상에 대한 심화된 이론적 이해가 가능함을 보였다.
