Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
notes:fountain [2017/02/20] – gomida | notes:fountain [2022/11/17] (current) – removed gomida | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== 파운틴 코드 ====== | ||
- | ===== Fountain Codes ===== | ||
- | <sq> | ||
- | 필자의 경우 차세대 방송용 프로토콜 [[MMTP]]를 공부하면서 그 순방향에러정정(Forward Error Correction; FEC) 방법으로 RaptorQ(RFC-6330, | ||
- | </sq> | ||
- | <sq> | ||
- | ==== Random Binary Fountain Code ==== | ||
- | 파운틴코드를 다루는 논문들에서 비교 대상이 되곤 하는 이상적 파운틴코드이다. 랜덤 바이너리 파운틴코드는 완전히 랜덤한 분포를 가진 매트릭스를 사용하여 인코딩심볼을 생성하는 것을 가정한다. 이 경우 가우스 소거법(Gaussian-Elimination; | ||
- | </sq> | ||
- | <sq> | ||
- | ==== Luby Transform Code ==== | ||
- | 루비트랜스폼코드는 신뢰전파(Belief-Propagation; | ||
- | </sq> | ||
- | <sq> | ||
- | ==== Raptor Code, R10, RQ ==== | ||
- | LT Code의 경우 BP와 GE 알고리즘을 혼합하여 디코딩하였을 때 좋은 결과를 보이는데, | ||
- | </sq> | ||
- | |||
- | <sq> | ||
- | ==== 접근 순서 ==== | ||
- | 필자의 경우 수학에 익숙하지 않아 상당한 진입장벽을 경험하였는데, | ||
- | |||
- | 각 코드의 오리지널 논문은 인코딩 매트릭스 구성에 맞는 디코더를 함께 제안하고 있는데, 이를 파악하는 것이 최우선이라 생각된다. 만약 순수 가우스 소거법으로 디코딩하고 있다면, 각 코드의 핵심이 가려지면서 필자처럼 멀리 돌아오는 길을 걸을 수도 있다. :) | ||
- | </sq> | ||
- | |||
- | <sq> | ||
- | ==== 디코딩 알고리즘 ==== | ||
- | 디코더 구현을 위해 관련 알고리즘을 살펴보았을 때 익숙하지 않은 이름들이 혼용되고 있어 접근이 쉽지 않았다. 그나마 조금이라도 익숙한 것이라면 가우스 소거법 정도지만, | ||
- | \\ | ||
- | \\ | ||
- | ^ 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로 해결하는 방법은 어떨까. 이 접근방법의 대표적인 예가 인액티베이션 디코딩이며, | ||
- | |||
- | 프로그래머 입장에서는 R10과 RQ도 GE로 푸는 방법도 생각할 수 있지만, 저밀도 매트릭스에서 BP의 구현 용이성을 생각하면 BP를 통해 매트릭스 크기를 줄이고 최소한의 매트릭스만 GE로 푸는 것이 아무래도 합리적이다. | ||
- | </sq> | ||
- | |||
- | <sq> | ||
- | ==== 심볼 수 K에 대한 디코딩 알고리즘의 시간 복잡도 ==== | ||
- | {{ : | ||
- | RFC 5053의 인액티베이션 디코딩(표준 문서에는 이 명칭이 언급되어 있지 않다)을 실제 구현해 시간 복잡도를 비교해 보면 O(KlogK)로 유사선형을 나타내며 유효구간 K:4~8192 영역에서는 선형이라고 주장할 수 있을 만큼 효율이 좋다. 논문에 따라서는 Inactivation Decoding Gaussian Elimination IDGE로 부르기도 한다. 자료구조에 의해서도 많은 영향을 받기 때문에 어딘가 아직 핵심을 놓치고 있을 수도 있고 보완되면 완전한 선형 복잡도를 나타낼 수도 있을 것이다. 많은 응용논문에서 R10의 디코딩 복잡도가 심볼 수 K< | ||
- | |||
- | |||
- | RFC6330의 랩터Q에서 개선 된 인액티베이션 디코딩은 GF(256) 영역을 PI라고 하여 처음부터 비활성화 상태로 디코딩을 시작하는 점을 제외하면 RFC5053의 디코더와 동등하다. 실제 구현할 때에도 단순히 H 영역을 비활성화하는 코드를 몇 줄 추가하는 것으로 동작 가능했는데 다만 필자가 놓친 새로운 아이디어가 포함되어 있을 수 있다. 랩터Q에서는 LT degree 분포 자체가 PI를 상정하여 솔리톤분포에 GF(256) HDPC 영역에 대한 DEGREE를 추가하고 있어서 이를 비활성화하지 않으면 DEGREE 2 조차도 거의 없는 매트릭스가 되어 BP는 도저히 돌 수 없는 상태가 된다. | ||
- | </sq> | ||
- | |||
- | <sq> | ||
- | ==== 인코딩 알고리즘 ==== | ||
- | === Soliton Distribution === | ||
- | LT 인코딩 측면에서는 몇 개의 소스심볼과 XOR 되었는지를 나타내는 DEGREE 분포가 핵심이 된다. 여러가지 변형이 존재하지만 [[notes/ | ||
- | </sq> | ||
- | <sq> | ||
- | ==== Raptor Code의 인코딩 시간 복잡도 ==== | ||
- | 인코딩 부하가 거의 없는 순수 LT코드에 비해 R10과 RQ는 각 K값에 대해 역행렬을 최소 한 번은 연산해두어야 하는 부하를 가지고 있다. 랩터는 체계적 부호(Systematic Code)로서 K개의 소스심볼에서 K+N개의 인코딩 심볼을 생성할 때 심볼구분자(External Symbol Identifier; 이하 ESI) 0번부터 K-1번까지는 K개의 소스심볼로 구성되는데, | ||
- | |||
- | 역행렬을 가우스 소거법으로 구한다면 O(L< | ||
- | |||
- | 하지만 반전이 있으니 각 역행렬은 각 K 값에 대해 한 번만 연산해두면 계속 사용할 수 있는 것으로, 심볼 크기 T만큼의 XOR을 한 사이클에 처리하는 SIMD를 갖추고 있다면 사실상의 인코딩 복잡도는 O(k)로 표기 가능할 것이다. | ||
- | </sq> | ||
- | <sq> | ||
- | ==== 랩터 인코딩에서 역행렬을 구하는 과정이 단지 Systematic Code 특성만을 위한 것인가? ==== | ||
- | 아직 완전한 이해를 못 한 부분 가운데 하나이다. 하지만 Non-systematic LT 코드에서 제약심볼 생성을 가정하면 A< | ||
- | </sq> |
TypeError: Cannot access offset of type string on string
An unforeseen error has occured. This is most likely a bug somewhere.
More info has been written to the DokuWiki error log.