온라인 코드

컴퓨터 과학에서 온라인 코드는 무비례 삭제 코드의 예다.이러한 코드는 메시지를 여러 기호로 인코딩할 수 있으며, 그 중 어떤 부분에 대한 지식이 있으면 원래의 메시지를 복구할 수 있다(높은 확률로).무임승차 코드는 임의로 많은 수의 기호를 생성하며 수신자가 충분한 기호를 가질 때까지 방송할 수 있다.

온라인 인코딩 알고리즘은 여러 단계로 구성된다.먼저 메시지는 n개의 고정 크기 메시지 블록으로 분할된다.그러면 외부 인코딩은 메시지 블록에 추가되어 복합 메시지를 형성하는 보조 블록을 생성하는 삭제 코드다.

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

상세토론

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

외부 인코딩

삭제 코드는 외부 인코딩으로 사용할 수 있지만 온라인 코드의 작성자는 다음과 같이 제안한다.

각 메시지 블록에 대해 의사 임의로 q 보조 블록(총 0.55qεn 보조 블록에서)을 선택하여 부착한다.각 보조 블록은 그 블록에 부착된 모든 메시지 블록의 XOR이다.

내부 인코딩

내부 인코딩은 복합 메시지를 받아 체크 블록 스트림을 생성한다.체크 블록은 이 블록이 연결된 복합 메시지에서 모든 블록의 XOR이다.

체크 블록의 정도는 그것이 부착된 블록의 수입니다.정도는 다음과 같이 정의되는 랜덤 분포 p를 표본으로 추출하여 결정한다.

$F=\왼쪽\lceil {\frac(\ln(\epsilon ^{2}/4)}{\ln(1-\epsilon /2)}{\ln(1-\epsilon /2)}\오른쪽\rceil$

$p_{1}=1-{\frac {1+1/F}{1+\엡실론}}}}$

$p_$$\mathrm{F<img\; alt="p\_\{i\}=\{\backslash frac\; \{(1-p\_\{1\})"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/2d99e60df64c4314362b932e0347ffc825dad144"\; style="vertical-align:\; -2.671ex;\; margin-left:\; -0.089ex;\; width:20.963ex;\; height:6.509ex;"\; papago-attr-id="32">}$$}{{(F-1)i(i-1$)}}{{{(F-1$)}}}$$$}} F $\leq$ i$\leq F$.

체크 블록의 정도가 알려지면, 해당 블록이 부착된 복합 메시지의 블록이 균일하게 선택된다.

디코딩

분명히 내부 단계의 디코더는 현재 해독할 수 없는 체크 블록을 보유해야 한다.체크 블록은 한 블록을 제외한 모든 블록이 알려진 경우에만 디코딩할 수 있다.왼쪽 그래프는 내부 디코더의 진행률을 보여준다.x축은 수신된 체크 블록 수를 표시하고, 점선은 현재 사용할 수 없는 체크 블록 수를 나타낸다.이것은 1도 이하의 많은 체크 블록이 수신되었지만 사용할 수 없기 때문에 처음에는 거의 선형적으로 상승한다.특정 시점에서 일부 체크 블록을 갑자기 사용할 수 있게 되어 더 많은 블록을 해결하면 더 많은 체크 블록을 사용할 수 있게 된다.매우 빠르게 전체 파일을 디코딩할 수 있다.

그래프는 또한 내부 디코더가 n개의 체크 블록을 받은 후 잠시 동안 모든 디코딩을 하는 것을 수줍어한다는 것을 보여준다.외부 인코딩을 통해 내부 디코더에서 몇 개의 찾기 어려운 블록이 문제가 되지 않도록 하는데, 이 블록이 없어도 파일을 복구할 수 있기 때문이다.

외부 링크

• 오리지널 페이퍼
• 무료 코드 및 대용량 다운로드(동일한 저자가 더 쉽게 액세스할 수 있는 종이)
• 페타르 메이문코프의 논문
• Ruby Forge에서 주최하는 Ruby 프로젝트. 온라인 코딩용 Ruby 라이브러리가 포함된 Ruby 프로젝트