HOME
RECENT CHANGES

파운틴 코드

Fountain Codes

필자의 경우 차세대 방송용 프로토콜 MMTP를 공부하면서 그 순방향에러정정(Forward Error Correction; FEC) 방법으로 RaptorQ(RFC-6330, RQ)를 처음 접하게 되었다. 최초에는 FEC 자체에 큰 관심은 없었기 때문에 오픈소스를 사용해 구현하였는데 문제는 여기서부터 시작되었던 것 같다. 대부분의 RaptorQ 오픈소스 구현은 디코딩 복잡도가 심볼 수 K에 대하여 K2 또는 심지어 K3을 나타내는데, 현재의 머신에서는 도저히 사용하기 어려울 것 처럼 보였기 때문이다. 그런데 오리지널 논문을 보면 최대 유사선형복잡도 KlogK로 디코딩 가능하다 하니 어떤 마법을 사용하는지 궁금해졌던 것이다. 비슷한 고민을 가진 프로그래머를 위해 공부하면서 이해한 것을 정리해 본다.

Random Binary Fountain Code

파운틴코드를 다루는 논문들에서 비교 대상이 되곤 하는 이상적 파운틴코드이다. 랜덤 바이너리 파운틴코드는 완전히 랜덤한 분포를 가진 매트릭스를 사용하여 인코딩심볼을 생성하는 것을 가정한다. 이 경우 가우스 소거법(Gaussian-Elimination; 이하 GE)을 사용하면 섀넌리밋에 근접하는 적은 전송 오버헤드로 디코딩 할 수 있지만 매트릭스의 밀도가 1/2에 달하여 GE 연산 오버헤드 측면에서 실용적이지 못한 문제가 있다.

Luby Transform Code

루비트랜스폼코드는 신뢰전파(Belief-Propagation; 이하 BP) 알고리즘을 사용한 디코딩이 가능하도록 인코딩 단계에서 솔리톤분포(Soliton-Distribution)를 사용하여 매트릭스 밀도를 낮춤으로써 최초의 실용적인 파운틴코드로 인정받을 수 있었다. BP는 심볼 수 K에 대해 유사선형복잡도에 해당하는 O(nlogn)으로 디코딩 가능하며, 솔리톤분포에 의해 생성되는 매트릭스의 밀도가 낮아 GE로 디코딩하는 경우에도 랜덤 바이너리 파운틴코드에 비해 빠르게 연산할 수 있다. 그러나 LT에서의 BP 디코딩은 충분한 K 값을 가져야 논문에서 제시하는 성능을 보이며, GE 디코딩의 경우 매트릭스 밀도가 너무 낮은 나머지 RANK 부족을 자주 겪는다. 솔리톤분포의 파라메터를 조절하여 매트릭스의 밀도를 상향하는 것이 가능하지만, 이 경우 끊임 없이 Degree 1 ( 무게 1 ) 심볼을 생성해야만 하는 BP 디코딩 알고리즘의 동작을 방해하게 되고, 이는 디코딩 성공확률의 편차를 크게 하여 전송 오버헤드의 예측이 어려워진다.

Raptor Code, R10, RQ

LT Code의 경우 BP와 GE 알고리즘을 혼합하여 디코딩하였을 때 좋은 결과를 보이는데, 이 하이브리드 디코딩 알고리즘의 최종 보스격인 것이 Raptor Code(이하 R10)논문에서 제시 된 Inactivation Decoding이다. 또한 랩터코드에서는 제약심볼이라 지칭하는 가상의 중간심볼을 생성하여 솔리톤분포를 크게 손상하지 않고 매트릭스의 밀도를 상향하였기에 충분한 RANK를 확보한다. RaptorQ(이하 RQ)의 경우 R10의 고밀도 매트릭스 영역을 0과 1의 바이너리가 아닌 0~255의 GF(28)로 대체하여 RANK 부족을 극적으로 억제하며 Permanent Inactivation Decoding이라 지칭하는 방법으로 BP 디코딩 동작에 영향을 주지 않도록 고밀도 매트릭스 영역을 숨긴다.

접근 순서

필자의 경우 수학에 익숙하지 않아 상당한 진입장벽을 경험하였는데, Raptor를 먼저 접하고 공부하다가 근간이 되는 Luby-Transform을 파고 들었고, 여기서 Belief-Propagation 알고리즘에 대한 이해를 얻어 LT코드에서의 BP-GE hybrid decoder를 연구하게 되었다. 이후 BP-GE hybrid decoder 연구를 완성시킬 즈음에서야 RFC-5053이 설명하고 있는 Inactivation-Decoding의 핵심을 이해하게 되면서 Raptor로 멀리 돌아온 케이스이다.

각 코드의 오리지널 논문은 인코딩 매트릭스 구성에 맞는 디코더를 함께 제안하고 있는데, 이를 파악하는 것이 최우선이라 생각된다. 만약 순수 가우스 소거법으로 디코딩하고 있다면, 각 코드의 핵심이 가려지면서 필자처럼 멀리 돌아오는 길을 걸을 수도 있다. :)

디코딩 알고리즘

디코더 구현을 위해 관련 알고리즘을 살펴보았을 때 익숙하지 않은 이름들이 혼용되고 있어 접근이 쉽지 않았다. 그나마 조금이라도 익숙한 것이라면 가우스 소거법 정도지만, 아련한 선형대수의 기억만 가지고 있던 필자로서는 이마저도 부담이었다. 그 이름들을 나열해보면 다음과 같다.

Belief Propagation(BP) Hybrid Maximum Likelihood(ML)
Sum Product, Greedy, Peeling Inactivation Decoding(IDGE) Gaussian Elimination(GE)
Luby Transform(LT) code Raptor, RaptorQ code


다양한 이름에서 알 수 있는 것 처럼 논문에 따라, 서술하는 사람에 따라 다르게 불리우고 있지만 큰 맥락을 보면 신뢰성전파와 최대유사도 알고리즘으로 나눌 수 있을 것이다. 그리고 두 가지를 조합하여 디코딩 하는 알고리즘들이 있고 인액티베이션 디코더가 대표적이다.

루비트랜스폼 코드(이하 LT)가 최초의 실용적인 파운틴코드라 일컬어지는 것은 솔리톤분포에 의한 저밀도 매트릭스와 신뢰성전파(이하 BP) 디코딩 알고리즘의 조합에 그 핵심이 있다. 그럼 LT 코드를 가우스소거법(이하 GE)으로는 풀면 어떻게 될까. BP에 비해 더 적은 오버헤드만으로 복구할 수 있지만, 디코딩 복잡도가 크게 증가하게 된다.

그럼 BP로 풀 수 있는데까지 풀고 나머지를 GE로 해결하는 방법은 어떨까. 이 접근방법의 대표적인 예가 인액티베이션 디코딩이며, LT코드 매트릭스를 통째로 GE로 푸는 것에 비해 개선된 성능을 보이는 랩터(이하 R10)와 랩터Q(이하 RQ) 코드의 핵심이기도 하다.

프로그래머 입장에서는 R10과 RQ도 GE로 푸는 방법도 생각할 수 있지만, 저밀도 매트릭스에서 BP의 구현 용이성을 생각하면 BP를 통해 매트릭스 크기를 줄이고 최소한의 매트릭스만 GE로 푸는 것이 아무래도 합리적이다.

심볼 수 K에 대한 디코딩 알고리즘의 시간 복잡도

RFC 5053의 인액티베이션 디코딩(표준 문서에는 이 명칭이 언급되어 있지 않다)을 실제 구현해 시간 복잡도를 비교해 보면 O(KlogK)로 유사선형을 나타내며 유효구간 K:4~8192 영역에서는 선형이라고 주장할 수 있을 만큼 효율이 좋다. 논문에 따라서는 Inactivation Decoding Gaussian Elimination IDGE로 부르기도 한다. 자료구조에 의해서도 많은 영향을 받기 때문에 어딘가 아직 핵심을 놓치고 있을 수도 있고 보완되면 완전한 선형 복잡도를 나타낼 수도 있을 것이다. 많은 응용논문에서 R10의 디코딩 복잡도가 심볼 수 K2에 비례하는 그래프를 보이고 있는데 이는 가우스 소거법을 사용하여 디코딩하는 경우로 판단된다.

RFC6330의 랩터Q에서 개선 된 인액티베이션 디코딩은 GF(256) 영역을 PI라고 하여 처음부터 비활성화 상태로 디코딩을 시작하는 점을 제외하면 RFC5053의 디코더와 동등하다. 실제 구현할 때에도 단순히 H 영역을 비활성화하는 코드를 몇 줄 추가하는 것으로 동작 가능했는데 다만 필자가 놓친 새로운 아이디어가 포함되어 있을 수 있다. 랩터Q에서는 LT degree 분포 자체가 PI를 상정하여 솔리톤분포에 GF(256) HDPC 영역에 대한 DEGREE를 추가하고 있어서 이를 비활성화하지 않으면 DEGREE 2 조차도 거의 없는 매트릭스가 되어 BP는 도저히 돌 수 없는 상태가 된다.

인코딩 알고리즘

Soliton Distribution

LT 인코딩 측면에서는 몇 개의 소스심볼과 XOR 되었는지를 나타내는 DEGREE 분포가 핵심이 된다. 여러가지 변형이 존재하지만 솔리톤 분포가 그 중심에 있다.

Raptor Code의 인코딩 시간 복잡도

인코딩 부하가 거의 없는 순수 LT코드에 비해 R10과 RQ는 각 K값에 대해 역행렬을 최소 한 번은 연산해두어야 하는 부하를 가지고 있다. 랩터는 체계적 부호(Systematic Code)로서 K개의 소스심볼에서 K+N개의 인코딩 심볼을 생성할 때 심볼구분자(External Symbol Identifier; 이하 ESI) 0번부터 K-1번까지는 K개의 소스심볼로 구성되는데, 이 특성을 부여하는 과정에서 역행렬을 구하는 단계가 포함된다.

역행렬을 가우스 소거법으로 구한다면 O(L2)의 성능을 보이는 구현이 될 것이다. 여기서 L은 중간심볼의 수를 나타내며 소스심볼 수 K와 제약심볼 수 S, H의 합이다. 약간의 최적화 방법으로 제약심볼을 KxK 영역에 미리 풀어놓고 역행렬을 구하는 구현도 생각해 볼 수 있지만 복잡도를 크게 줄이지는 못할 것이다. 랩터코드의 인코딩에 있어서 역행렬을 구하는 과정은 Inactivation Decoding 알고리즘을 활용여 중간심볼 수 L에 대해 O(LlogL)로 구현하는 것이 이상적이며 설계방향에 부합한다고 생각된다.

하지만 반전이 있으니 각 역행렬은 각 K 값에 대해 한 번만 연산해두면 계속 사용할 수 있는 것으로, 심볼 크기 T만큼의 XOR을 한 사이클에 처리하는 SIMD를 갖추고 있다면 사실상의 인코딩 복잡도는 O(k)로 표기 가능할 것이다.

랩터 인코딩에서 역행렬을 구하는 과정이 단지 Systematic Code 특성만을 위한 것인가?

아직 완전한 이해를 못 한 부분 가운데 하나이다. 하지만 Non-systematic LT 코드에서 제약심볼 생성을 가정하면 A-1를 사용하지 않아도 될 것이기에 Systematic 속성을 위한 것이라 잠정 이해하고 있다.