잡음 속에서 원본을 복원하는 기술
한 개발자가 러스트(Rust)로 작성한 비터비(Viterbi) 디코더를 공개했어요. SIMD 명령어를 활용해 성능을 끌어올린 FEC 라이브러리인데요. 용어가 낯설 수 있으니 하나씩 풀어볼게요.
무선 통신에서는 데이터가 전송 중에 깨지는 일이 일상이에요. 위성에서 지구로 신호를 보내면 우주 잡음 때문에 비트가 뒤집히곤 하거든요. FEC(순방향 오류 정정)가 뭐냐면, 보내는 쪽에서 미리 여분의 정보를 섞어 보내서, 받는 쪽이 일부가 깨진 신호를 받아도 원본을 복원할 수 있게 하는 기술이에요. '다시 보내주세요'라고 재전송을 요청할 수 없는 상황 — 위성 통신, 방송, 실시간 스트리밍 — 에서 필수적이죠. 그중 컨볼루션 코드(convolutional code)라는 부호화 방식이 있는데, 이걸 해독하는 대표적인 알고리즘이 바로 비터비 알고리즘이에요. 1967년에 나온 고전인데 위성 통신과 각종 무선 규격에서 아직도 현역이에요.
비터비 알고리즘, 쉽게 말하면
비유하자면 이래요. 친구가 보낸 문자가 얼룩져서 '안하세'라고 도착했다고 해봐요. 우리는 한국어의 문맥을 알기 때문에 '안녕하세요'였을 가능성이 가장 높다고 추측할 수 있죠. 비터비 알고리즘도 똑같은 일을 해요. 잡음 섞인 수신 신호를 보고, '송신 측이 보냈을 가능성이 가장 높은 원본 비트열'을 찾아내는 거예요. 인코더가 만들어낼 수 있는 모든 상태 변화를 격자(trellis) 형태로 펼쳐놓고, 동적 계획법(dynamic programming)으로 가장 그럴듯한 경로 하나를 골라내죠.
이 과정의 핵심 연산이 ACS(Add-Compare-Select)예요. 각 상태마다 '경로 점수를 더하고, 두 후보를 비교해서, 더 좋은 쪽을 선택'하는 걸 반복하는 건데요. 문제는 이걸 상태 수만큼, 그리고 복원할 비트 수만큼 해야 해서 연산량이 어마어마하다는 거예요. 예를 들어 널리 쓰이는 constraint length 7짜리 코드는 내부 상태가 64개라서, 비트 하나를 복원할 때마다 64개 상태 전부에 대해 ACS를 돌려야 하거든요.
여기서 SIMD가 등장해요. SIMD(Single Instruction, Multiple Data)가 뭐냐면, CPU가 명령 하나로 여러 개의 데이터를 동시에 처리하는 기능이에요. 일반 연산이 계산기 한 대로 하나씩 계산하는 거라면, SIMD는 계산기 16대를 나란히 놓고 버튼 하나로 한꺼번에 돌리는 셈이죠. 그런데 ACS 연산은 상태별로 서로 독립적이라서 SIMD와 궁합이 아주 좋아요. 64개 상태의 점수를 벡터 레지스터에 담아 한 번에 더하고 비교하면 순수 반복문 대비 수 배에서 수십 배까지 빨라지거든요. 이 프로젝트가 노린 게 바로 그 지점이에요.
libfec의 계보, 그리고 러스트
이 분야의 고전은 아마추어 무선계의 전설인 필 칸(Phil Karn)이 만든 C 라이브러리 libfec이에요. 20년 넘게 SDR(소프트웨어 정의 라디오, 하드웨어 회로 대신 소프트웨어로 무선 신호를 처리하는 기술) 커뮤니티의 사실상 표준처럼 쓰였고, SSE 명령어로 최적화된 비터비 구현이 들어 있죠. 이번 프로젝트는 그 계보를 러스트로 잇는 시도라고 볼 수 있어요. 러스트는 메모리 안전성을 컴파일 타임에 보장하면서도 C 수준의 성능을 내는 언어라서 이런 저수준 신호 처리 코드에 점점 많이 쓰이고 있고, 러스트의 SIMD 지원도 portable SIMD(std::simd) 작업이 진행되면서 예전보다 훨씬 다루기 좋아졌거든요. 안전한 언어로 극한의 성능을 뽑는 사례가 하나 더 쌓인 셈이에요.
한국 개발자에게는
'내가 위성 통신 할 일이 있을까?' 싶으실 수 있는데요, 의외로 접점이 많아요. 몇만 원짜리 RTL-SDR 수신기로 기상 위성 신호를 직접 잡아 디코딩하는 취미 분야가 있는데, 거기서 비터비 디코더가 핵심 부품이에요. 임베디드나 IoT에서 자체 무선 프로토콜을 다룰 때도 FEC 지식은 큰 무기가 되고요. 무엇보다 이 프로젝트는 '고전 알고리즘 + SIMD 최적화 + 러스트' 조합의 살아있는 교재예요. 코드 규모도 부담스럽지 않아서, 러스트로 성능 최적화를 공부하고 싶은 분에게 좋은 출발점이 될 거예요. 알고리즘 교과서에서 본 동적 계획법이 실제 하드웨어 명령어 수준에서 어떻게 최적화되는지 따라가 보는 재미가 쏠쏠하거든요.
정리하며
비터비 디코딩은 반세기 된 알고리즘이지만, 그걸 현대적인 언어와 벡터 명령어로 다시 구현하는 과정에는 배울 게 가득해요. 여러분은 고전 알고리즘을 밑바닥부터 직접 구현해보면서 실력이 확 늘었던 경험이 있으신가요? 있다면 어떤 알고리즘이었는지 궁금하네요.
🔗 출처: Hacker News