[PonsWarp 개념 교실 13] Reed-Solomon — GF(2^8) 이레이저 코딩
쉽게 말하면, **Reed-Solomon은 "데이터 10조각을 보낼 때 패리티 4조각을 더 보내서, 아무 4조각이 사라져도 나머지 10조각으로 원본을 복원하는 기법"**이다.
전송에서 패킷이 손실되면 보통 재전송을 요청한다. 그런데 왕복 지연이 크거나 손실이 잦은 환경에서는 재전송을 기다리는 것보다 "처음부터 여분을 보내는" 편이 낫다. 그게 FEC(Forward Error Correction, 전방 오류 정정)다. 이 글에서는 Reed-Solomon의 수학과 PonsWarp의 구현, 그리고 왜 전송에 안 썼는지를 본다.
이게 왜 필요한가 — 재전송이 비싼 순간
WebRTC DataChannel(SCTP)은 손실 패킷을 자동 재전송한다. 그런데 재전송은 왕복 시간(RTT)만큼 기다려야 한다.
- LAN: RTT 1ms — 재전송이 거의 공짜
- TURN 릴레이 경유: RTT 수백 ms — 재전송이 비싸짐
- 손실률이 높은 무선: 재전송이 계속 반복됨
FEC의 아이디어는 "잃을 것을 예상하고 여분을 보낸다"다. 재전송을 기다리는 대신, 이미 받은 조각들로 즉시 복구한다. 지연이 높고 손실이 있는 경로에서 재전송보다 유리하다.
Reed-Solomon의 원리 — 방정식 풀기
핵심 아이디어는 놀랍도록 단순하다. n개의 데이터 조각이 n개의 방정식을 만족한다고 보고, 방정식이 풀리도록 여분의 정보(패리티)를 붙이는 것이다.
데이터: d1 d2 d3 ... d10
패리티: p1 p2 p3 p4 ← 데이터들의 선형 조합
p1 = a1·d1 + a2·d2 + ... + a10·d10 (GF(2^8) 연산)
p2 = b1·d1 + b2·d2 + ... + b10·d10
...
10개의 데이터 + 4개의 패리티 = 14개의 값. 이 중 아무 10개만 있으면 10개의 미지수(d1~d10)를 풀 수 있는 10개의 방정식이 만들어진다. 4개가 사라져도 나머지 10개로 복원 가능하다. 이게 "최대 4개 손실 복구"의 의미다.
GF(2^8) — 왜 갈루아 체인가
Reed-Solomon의 덧셈·곱셈은 일반 수학이 아니라 GF(2^8)이라는 유한체에서 한다. 이유는 두 가지다.
- 바이트 단위 연산: GF(2^8)은 256개의 값(0~255)으로 이루어져, 바이트 하나가 체의 원소 하나가 된다. 데이터가 바이트라서 자연스럽게 맞는다.
- 손실 없는 역연산: 유한체에서는 모든 0이 아닌 값에 역수가 존재해서 "방정식을 푸는" 연산(나눗셈, 역행렬)이 항상 가능하다.
덧셈은 XOR(같은 값 두 번 더하면 0)이고, 곱셈은 지수·로그 테이블로 구현한다.
rust// pons-core-wasm/src/fec/reed_solomon.rs /// GF(2^8) 원시 다항식: x^8 + x^4 + x^3 + x^2 + 1 const GF_PRIMITIVE: u16 = 0x11d; #[inline] fn gf_mul(a: u8, b: u8) -> u8 { if a == 0 || b == 0 { 0 } else { GF_EXP[(GF_LOG[a as usize] as usize) + (GF_LOG[b as usize] as usize)] } }
곱셈은 "로그를 더해서 지수 테이블에서 찾는" 방식 — 일반 정수 곱셈과 완전히 다르다. 이 체의 성질 덕분에 **패리티는 항상 데이터의 "올바른 선형 조합"**이 된다.
Vandermonde 행렬 — 패리티를 만드는 공식
패리티 계수(위의 a1a10, b1b10...)는 Vandermonde 행렬로 생성한다. 이 행렬은 구조가 단순하면서도 어떤 부분 행렬이든 역행렬이 존재한다는 보장이 있어서, 손실 복구에 이상적이다.
rust// pons-core-wasm/src/fec/reed_solomon.rs fn build_vandermonde_matrix(rows: usize, cols: usize) -> Vec<Vec<u8>> { // 단위행렬(데이터) + Vandermonde(패리티) 결합 }
복구 — 가우스-조던 역행렬
손실이 발생하면 복구는 이렇게 동작한다.
받은 10개 샤드 → 서브행렬 구성 → 역행렬 계산(가우스-조던) → 원본 복원
rust// pons-core-wasm/src/fec/reed_solomon.rs let inv_matrix = self.invert_matrix(&mut sub_matrix)?; // 가우스-조던
받은 샤드들에 대응하는 행렬의 역행렬을 구해 원본을 재구성한다. 손실된 위치에 따라 서브행렬이 달라지므로, 매번 다른 역행렬을 계산한다. GF(2^8)에서는 이 연산이 항상 가능하다.
그런데 PonsWarp는 왜 전송에 안 썼나
정직하게 말하면, Reed-Solomon은 완전히 구현·export되어 있지만 프론트엔드 전송 경로에서 호출하는 증거를 찾지 못했다. LZ4·Merkle과 같은 운명이다.
추정 가능한 이유가 두 가지 있다. [INFERENCE] — 코드에는 사용 근거가 없고 설계만 보인다.
첫째, SCTP가 이미 신뢰성을 보장한다. DataChannel은 ordered 채널이 손실을 재전송으로 처리한다. FEC의 "재전송이 비싼" 전제가 SCTP에서는 약해진다. 애플리케이션 레벨 FEC는 SCTP 위에서 중복 보호가 될 수 있다.
둘째, 40% 오버헤드가 크다. 10+4 구성은 패리티 4개를 항상 보낸다. 손실이 없는 LAN에서는 이 40%가 순수 낭비다. 적응형 FEC(AdaptiveFec)가 손실률에 따라 2~6개로 조절하는 기능도 구현되어 있지만, 기본값 40%의 비용이 전송 전체에 붙는 걸 피한 것으로 보인다.
FEC가 정말 유리한 시나리오(고지연·고손실·비신뢰 채널)는 SCTP 기반 P2P 경로와 맞지 않았고, 그래서 구현만 남은 것이다.
PonsWarp 적용 지점
| 항목 | 값 | 증거 |
|---|---|---|
| 데이터 샤드 | 10 (기본) | reed_solomon.rs:11 |
| 패리티 샤드 | 4 (40% 오버헤드) | reed_solomon.rs:13 |
| 유한체 | GF(2^8), 원시다항식 0x11d | reed_solomon.rs:16 |
| 곱셈 | 지수·로그 테이블 (GF_EXP/GF_LOG) | reed_solomon.rs:19-70 |
| 행렬 | Vandermonde (단위+패리티) | reed_solomon.rs:92-110 |
| 인코더 | encode / encode_block (4B 길이+패딩+패리티) | reed_solomon.rs:154-224 |
| 복구 | 서브행렬 역행렬(가우스-조던) | reed_solomon.rs:338-418 |
| 적응형 | AdaptiveFec 2~6 패리티 (손실률 기반) | reed_solomon.rs:425-534 |
| 전송 경로 | 프론트 호출 없음 (미사용) | 프론트 grep 무결과 |
지금 돌아보는 판단
세 가지를 정리한다.
첫째, FEC는 "재전송 대체재"가 아니라 "재전송이 비싼 채널 전용"이다. SCTP가 재전송을 이미 싸게 해주는 환경에서는 FEC의 여분이 낭비가 된다. 도구의 가치는 채널 특성에 달려 있다. PonsWarp가 FEC를 안 쓴 것은 기술 부족이 아니라 채널 분석의 결과로 보인다.
둘째, GF(2^8)의 수학은 "바이트 단위 + 항상 역연산 가능"이라는 두 요구의 정답이다. 이 설계가 없으면 Reed-Solomon의 복구(역행렬)가 바이트 단위로 동작하지 않는다. 유한체 선택이 곧 구현의 토대다.
셋째, "구현했지만 안 쓴" 패턴이 반복되고 있다. LZ4, Merkle, Reed-Solomon — 셋 다 구현·export됐지만 전송 경로에 안 쓰인다. 세 가지가 같은 운명이라는 것은 우연이 아니라 "검증 비용보다 기능 추가가 쉬웠던" 개발 문화의 증거일 수 있다. 이 패턴은 "구현했지만 쓰지 않은 것들" 편에서 종합한다.
한 문장 정리
Reed-Solomon은 GF(2^8)에서 Vandermonde 행렬로 패리티를 만들어 10+4 샤드 구성에서 최대 4개 손실을 복구하는 FEC이고, PonsWarp는 완전히 구현했지만 SCTP의 재전송 신뢰성과 40% 오버헤드 때문에 전송 경로에는 쓰지 않는다.
관련 개념: [개념 12 — LZ4] (같은 "미사용" 운명) · [구현 12 — 구현했지만 쓰지 않은 것들] (종합 예정)
다음 글: [개념 14 — WebRTC DataChannel: SCTP 신뢰성과 bufferedAmount]