온라인 부호

온라인 부호 사용의 개략적인 모습

컴퓨터 과학에서 온라인 부호(영어: Online codes)는 소거 부호의 한 예이다. 이 부호는 메시지를 여러 기호로 인코딩하여 그중 일부만으로도 원래 메시지를 (높은 확률로) 복구할 수 있게 한다. 레이트리스 부호는 수신자가 충분한 기호를 받을 때까지 임의로 많은 수의 기호를 생성하여 전송할 수 있다.

온라인 인코딩 알고리즘은 여러 단계로 구성된다. 먼저 메시지는 n개의 고정 크기 메시지 블록으로 분할된다. 그런 다음 외부 인코딩은 소거 부호이며, 이는 보조 블록을 생성하여 메시지 블록에 추가하여 복합 메시지를 형성한다.

여기서 내부 인코딩은 검사 블록을 생성한다. 일정 수의 검사 블록을 수신하면 복합 메시지의 일부를 복구할 수 있다. 충분히 복구되면 외부 디코딩을 사용하여 원래 메시지를 복구할 수 있다.

자세한 설명

온라인 부호는 블록 크기와 두 개의 스칼라인 q와 ε로 매개변수화된다. 저자들은 q=3, ε=0.01을 제안한다. 이 매개변수들은 인코딩의 복잡성과 성능 간의 균형을 설정한다. n개의 블록으로 구성된 메시지는 (1+3ε)n개의 검사 블록으로부터 높은 확률로 복구될 수 있다. 실패 확률은 (ε/2)^q+1이다.

외부 인코딩

어떤 소거 부호든 외부 인코딩으로 사용될 수 있지만, 온라인 부호의 저자는 다음을 제안한다.

각 메시지 블록에 대해 (총 0.55qεn개의 보조 블록 중에서) q개의 보조 블록을 의사 난수적으로 선택하여 연결한다. 각 보조 블록은 연결된 모든 메시지 블록의 XOR이다.

내부 인코딩

10000 블록 메시지에 대해 수신된 검사 블록 수와 고정된 메시지 블록 수를 나타내는 그래프.

내부 인코딩은 복합 메시지를 취하여 검사 블록 스트림을 생성한다. 검사 블록은 연결된 복합 메시지의 모든 블록의 XOR이다.

검사 블록의 차수는 연결된 블록의 수이다. 차수는 다음과 같이 정의된 무작위 분포 p를 샘플링하여 결정된다.

$F=\left\lceil {\frac {\ln(\epsilon ^{2}/4)}{\ln(1-\epsilon /2)}}\right\rceil$

$p_{1}=1-{\frac {1+1/F}{1+\epsilon }}$

$p_{i}={\frac {(1-p_{1})F}{(F-1)i(i-1)}}$ for $2\leq i\leq F$

검사 블록의 차수가 알려지면, 연결될 복합 메시지의 블록이 균일하게 선택된다.

디코딩

당연히 내부 단계의 디코더는 현재 디코딩할 수 없는 검사 블록을 보유해야 한다. 검사 블록은 연결된 블록 중 하나를 제외한 모든 블록이 알려진 경우에만 디코딩할 수 있다. 왼쪽 그래프는 내부 디코더의 진행 상황을 보여준다. x축은 수신된 검사 블록 수를 나타내고, 점선은 현재 사용할 수 없는 검사 블록 수를 보여준다. 처음에는 차수 > 1인 많은 검사 블록이 수신되지만 사용할 수 없으므로 거의 선형적으로 증가한다. 특정 시점에서 일부 검사 블록이 갑자기 사용 가능해지면서 더 많은 블록이 해결되고, 이는 더 많은 검사 블록을 사용 가능하게 한다. 매우 빠르게 전체 파일을 디코딩할 수 있다.

그래프에서 볼 수 있듯이 내부 디코더는 n개의 검사 블록을 수신한 후 잠시 동안 모든 것을 디코딩하지 못한다. 외부 인코딩은 내부 디코더에서 몇 개의 찾기 힘든 블록이 문제가 되지 않도록 보장하며, 파일은 이들 없이도 복구될 수 있다.

외부 링크

• Original paper
• Rateless Codes and Big Downloads (A more accessible paper by the same author)
• Papers by Petar Maymounkov
• A Ruby project hosted at RubyForge containing a Ruby library for Online Coding