루비 변환 코드

컴퓨터 과학에서 LT 코드(Luby transform code, LT code)는 실용 분수 코드의 첫 번째 등급으로, 삭제 코드의 최적화에 가깝다.그것들은 1998년에 마이클 루비에 의해 발명되었고 2002년에 출판되었다.^[1]다른 분수 코드와 마찬가지로 LT 코드는 인코딩 및 디코딩 속도를 위해 수신 오버헤드를 교환하기 위해 희박한 초당적 그래프에 의존한다.LT 코드의 구별되는 특징은 메시지를 인코딩하고 디코딩하기 위해 배타적 또는 조작([\$displaystyle \oplus }$${\displaystyle }$에 기초한 특별히 단순한 알고리즘을 채용하는 것이다.^[2]

인코딩 알고리즘은 원칙적으로 무한대의 메시지 패킷(즉, 메시지를 해독하기 위해 수신해야 하는 패킷의 백분율이 임의로 작을 수 있음)을 생성할 수 있기 때문에 LT 코드는 무급이다.삭제 채널에서 디지털 데이터를 안정적으로 전송하는 데 사용할 수 있기 때문에 삭제 코드를 수정하는 것이다.

LT 코드 이외의 다음 세대는 Raptor 코드(예를 들어 IETF RFC 5053 또는 IETF RFC 6330 참조)로, 선형 시간 인코딩 및 디코딩이 가능하다.랩터 코드는 기본적으로 LT 코드에 기반을 두고 있다. 즉, 랩터 코드의 인코딩은 두 개의 인코딩 단계를 사용하며, 여기서 두 번째 단계는 LT 인코딩이다.마찬가지로, Raptor 코드로 디코딩하는 것은 주로 LT 디코딩에 의존하지만, LT 디코딩은 보다 진보된 디코딩 기법과 혼합되어 있다.가장 발전된 분수 코드인 IETF RFC 6330에 명시된 RaptorQ 코드는 LT 코드만 사용하는 것에 비해 디코딩 확률과 성능이 월등히 우수하다.

LT 코드를 사용하는 이유

삭제 채널을 통해 데이터를 전송하는 전통적인 계획은 지속적인 양방향 통신에 의존한다.

• 송신자는 정보의 패킷을 암호화하고 송신한다.
• 수신자는 수신된 패킷을 해독하려고 한다.디코딩이 가능한 경우, 수신기는 송신기로 수신확인을 다시 전송한다.그렇지 않으면, 수신자는 송신자에게 패킷을 다시 보내라고 요구한다.
• 이 양방향 프로세스는 메시지의 모든 패킷이 성공적으로 전송될 때까지 계속된다.

휴대 무선 방송에 사용되는 네트워크와 같은 특정 네트워크에는 피드백 채널이 없다.이러한 네트워크의 애플리케이션은 여전히 신뢰성을 필요로 한다.일반적으로 분수 코드, 특히 LT 코드는 본질적으로 단방향 통신 프로토콜을 채택하여 이 문제를 해결한다.

• 송신자는 정보 패킷을 인코딩하고 패킷을 전송한다.
• 수신자는 각 패킷이 수신되는 대로 평가한다.오류가 발생하면 잘못된 패킷은 폐기된다.그렇지 않으면 패킷은 메시지의 일부로 저장된다.
• 결국 수신자는 전체 메시지를 재구성하기에 충분한 유효 패킷을 가지고 있다.전체 메시지가 성공적으로 수신되면 수신기는 전송이 완료되었음을 신호한다.

위에서 언급했듯이, IETF RFC 6330에 명시된 RaptorQ 코드는 실제로 LT 코드를 능가한다.

LT 인코딩

인코딩 프로세스는 코드화되지 않은 메시지를 대략 같은 길이의 n개의 블록으로 나누는 것으로 시작한다.암호화된 패킷은 유사 숫자 생성기의 도움을 받아 생성된다.

• 다음 패킷의 도 d, 1 ≤ d ≤ n을 임의로 선택한다.
• 메시지에서 정확히 d블록은 무작위로 선택된다.
• M이_i 메시지의 ith 블록인 경우, 다음 패킷의 데이터 부분은 다음과 같이 계산된다.

${\displaystyle M_{i_{1}}\oplus M_{2}}\oplus \cdots \oplus M_{d}},}$

여기서 {i₁, i₂, …, i_d}은(는) 이 패킷에 포함된 d 블록에 대해 무작위로 선택한 인덱스다.

• 인코딩된 패킷에 접두사가 추가되어 메시지에서 n개 블록의 수, 이 패킷의 데이터 부분에 배타적으로 적용된 블록의 수, 그리고 {i₁₂, i, …, i_d} 인덱스 목록이 정의된다.
• 마지막으로, 어떤 형태의 오류 감지 코드(아마도 주기적 중복성 검사처럼 간단할 것이다)가 패킷에 적용되어 패킷이 전송된다.

이 과정은 수신자가 메시지가 수신되어 성공적으로 디코딩되었다는 신호를 보낼 때까지 계속된다.

LT 디코딩

디코딩 프로세스는 인코딩된 메시지를 검색하기 위해 "독점적 또는" 작업을 사용한다.

• 현재 패킷이 깨끗하지 않거나 이미 처리된 패킷을 복제하는 경우 현재 패킷은 폐기된다.
• 현재 깨끗하게 수신된 패킷이 도 d > 1인 경우, 먼저 메시지 큐 영역에 있는 모든 완전 디코딩된 블록에 대해 처리된 후(다음 단계에서 더 자세히 설명됨), 감소된 도수가 1보다 클 경우 버퍼 영역에 저장된다.
• d = 1(블록 M_i)의 새롭고 깨끗한 패킷이 수신되면(또는 이전 단계에서 현재 패킷의 정도가 1로 감소하면 메시지 대기열 영역으로 이동한 다음 버퍼에 있는 d > 1의 모든 패킷과 일치한다.그것은 M을_i 사용하여 인코딩된 버퍼링된 패킷의 데이터 부분에 독점적으로 포함되며, 일치하는 패킷의 정도가 감소하며, 그 패킷의 지수 목록은 M의_i 적용을 반영하도록 조정된다.
• 이 프로세스가 버퍼에서 d = 2의 블록을 잠금 해제하면 해당 블록은 °1로 감소하고 그 다음 메시지 대기열 영역으로 이동한 다음 버퍼에 남아 있는 패킷에 대해 처리된다.
• 메시지의 모든 n개의 블록이 메시지 대기열 영역으로 이동되면, 수신기는 송신기에 메시지가 성공적으로 디코딩되었다는 신호를 보낸다.

이 디코딩 절차는 모든 비트 문자열 A에 대해 A $\oplus {\displaystyle }$ ${\displaystyle \oplus }$ = 0이기 때문에 작동한다.d - 1개의 고유 블록을 d의 패킷으로 독점화한 후, 일치하지 않는 블록의 원래 인코딩되지 않은 콘텐츠만 남게 된다.우리가 가진 상징적으로

${\displaystyle{\begin{정렬}&,{}\qquad(M_{i_{1}}\oplus \dots\oplus M_{i_{d}})\oplus(M_{i_{1}}\oplus \dots\oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots\oplus M_{i_{d}})\\&amp을 말한다.=M_{i_{1}}\oplus M_{i_{1}}\oplus \dots\oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1}}\oplus M_{i_{k+1}}\oplus \dots\oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_{k}\oplus 0\oplus \&=}\oplus \oplus \dots \oplus \&=\oplus \oplus \oplus 0\&M_{i_{k}}\,\end{aigned}}}$

변형

위에서 설명한 인코딩 및 디코딩 프로세스의 몇 가지 변형이 가능하다.예를 들어, 실제 메시지 블록 지수 {i, i₁₂, …, i}의 목록으로_d 각 패킷에 접두사를 붙이는 대신, 인코더는 단순히 PRNG(Parentorandom Number Generator) 또는 인덱스 리스트를 구성하는 데 사용된 인덱스 테이블의 시드 역할을 하는 짧은 "키"를 보낼 수 있다.동일한 RNG 또는 인덱스 테이블을 장착한 수신기가 이 시드로부터 "랜덤" 인덱스 목록을 안정적으로 재생성할 수 있기 때문에 디코딩 프로세스를 성공적으로 완료할 수 있다.또는 낮은 평균 수준의 단순한 LT 코드와 강력한 오류 수정 코드를 결합하여 실제적으로 최적화된 LT 코드를 능가하는 랩터 코드를 구성할 수 있다.^[3]

LT 코드의 최적화

직선 LT 코드를 최적화하는 데 사용할 수 있는 파라미터는 단 하나, 즉 도 분포 함수(위의 LT 인코딩 섹션에서는 도 d에 대한 유사andom 번호 생성기로 설명됨)이다.실제로 다른 "랜덤" 숫자(지수 목록 {i₁₂, i, …, i } )는 항상 [0, n_d]에 대한 균일한 분포에서 추출된다. 여기서 n은 메시지가 분할된 블록 수입니다.^[4]

루비 자신이^[1] 정의한 "이상적인 솔리톤 분배"에 대해 논의했다.

${\displaystyle {\begin{aigned}\mathrm {P} \{d=1\}\{n1}\{npt]\mathrm {P} \{d=k\}}={d=k-1}}}}}}}{1}{k(k-1)\qquad(k=2,3,dots\n}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}{parglined}}}}.$

이 정도 분포는 이론적으로 디코딩 프로세스가 완료되기 전에 전송될 예상 중복 코드 워드의 수를 최소화한다.그러나 이상적인 솔리톤 분포는 실제적으로 잘 작동하지 않는데, 이는 예상된 행동을 둘러싼 어떤 변동은 디코딩 프로세스의 어느 단계에서 (축소된) 정도 1의 패킷이 없기 때문에 디코딩이 실패할 가능성이 높기 때문이다.게다가, 원래의 블록들 중 일부는 어떤 전송 패킷에도 xor-ed되지 않을 것이다.따라서, 실제로, 변형된 분포인 "로봇 솔리톤 분포"가 이상적인 분포로 대체된다.수정의 효과는 일반적으로 모든 원본 블록이 일부 패킷에 포함되도록 하기 위해 선택한 상당히 많은 양의 패킷 스파이크를 제외하고 매우 작은 정도(약 1)의 패킷과 1 이상의 패킷보다 적은 패킷을 생성하는 것이다.^[4]

참고 항목

• 온라인 코드
• 랩터 코드
• 토네이도 코드

참고 및 참조

외부 링크

• "C#에 Luby 변환 코드 구현"
• "분수대 코드 소개: 파이썬이 있는 LT 코드"