Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
notes:fountain [2017/02/09] – gomida | notes:fountain [2022/11/17] (current) – removed gomida | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== 파운틴 코드 ====== | ||
- | ===== Fountain Codes ===== | ||
- | <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 : | ||
- | RFC 5053의 인액티베이션 디코딩을 실제 구현해 비교해 보면 거의 선형임을 볼 수 있지만 논문에서의 주장처럼 진짜 선형은 아직 달성해보지 못했다. 자료구조에 의해서도 많은 영향을 받기 때문에 어딘가 아직 핵심을 놓치고 있을 수도 있는 부분이라고 생각된다. 많은 응용논문에서 R10의 디코딩 복잡도가 심볼 수 K< | ||
- | </sq> | ||
- | |||
- | <sq> | ||
- | ==== 인코딩 알고리즘 ==== | ||
- | === Soliton Distribution === | ||
- | LT 인코딩 측면에서는 몇 개의 소스심볼과 XOR 되었는지를 나타내는 DEGREE 분포가 핵심이 된다. 여러가지 변형이 존재하지만 [[notes/ | ||
- | </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.