리드솔로몬 부호 (Reed-Solomon Code)
쉽게 풀면
리드솔로몬 부호는 문장을 한 글자씩이 아니라 단어 단위로 점검하는 맞춤법 검사기에 비유할 수 있습니다. 개별 비트 하나하나를 따지는 대신 몇 개의 비트를 묶은 "심볼" 단위로 오류를 검사하고 정정하기 때문에, 특정 구간이 통째로 손상되는 상황에서도 효과적으로 복구할 수 있습니다. 이런 특성 덕분에 스크래치나 먼지처럼 연속된 구간을 훼손시키는 오류에 특히 강합니다.
왜 중요한가
리드솔로몬 부호는 저장매체의 표면 손상이나 통신 채널에서의 순간적인 잡음처럼 오류가 한꺼번에 몰려 발생하는 상황에 강하다는 특성 때문에, 광디스크, QR코드, 디지털 방송, 우주통신 등 데이터 무결성이 중요한 여러 분야에서 오랫동안 다뤄져 온 대표적인 오류정정 부호입니다.
인터리빙과 함께 사용하면 원래 짧은 구간에 몰려 있던 버스트 오류를 여러 부호어에 걸쳐 분산시켜, 각 부호어 안에서는 정정 가능한 범위 안의 오류로 바꿀 수 있어 두 기법이 흔히 함께 적용됩니다.
디지털 방송이나 저장매체처럼 오류가 일정한 구간에 몰려 나타나는 환경에서 리드솔로몬 부호가 특히 선호되는 이유는, 심볼 단위 처리가 그런 몰림 현상과 구조적으로 잘 맞아떨어지기 때문입니다.
핵심 정리
- 리드솔로몬 부호는 비트가 아니라 m비트로 묶은 심볼을 단위로 하는 블록 부호입니다. 심볼은 유한체의 원소이며, 부호 길이는 보통 n = 2m − 1 심볼입니다(Reed & Solomon, 1960).
- k개의 정보 심볼에 n − k개의 패리티 심볼을 더해 (n, k) 부호를 만들며, 최소거리는 d = n − k + 1입니다. 이는 주어진 n, k에서 얻을 수 있는 최댓값이어서 이런 부호를 최대거리분리(MDS) 부호라 부릅니다.
- 정정 능력은 심볼 오류 ⌊(n − k)/2⌋개입니다. 오류 위치를 미리 알고 있는 소실(erasure)이라면 n − k개까지 복원할 수 있습니다.
- 한 심볼 안에서 몇 비트가 틀리든 심볼 하나의 오류로 세므로, 오류가 몰려서 생기는 버스트 오류에 유리합니다.
예시로 보기
대표적인 부호의 계산입니다(모두 계산한 값).
| 부호 (n, k) | 심볼 크기 m | 패리티 심볼 수 | 정정 가능 심볼 오류 수 t | 최소거리 d |
|---|---|---|---|---|
| (255, 223) | 8비트 | 32 | 16 | 33 |
| (255, 239) | 8비트 | 16 | 8 | 17 |
| (15, 9) | 4비트 | 6 | 3 | 7 |
(255, 223) 부호가 8비트 심볼로 최대 16개의 심볼 오류를 정정하므로, 연속된 b비트가 깨지는 버스트가 최대 몇 심볼에 걸치는지 따져 보면 정정 보장 길이를 알 수 있습니다. 가장 불리하게 버스트가 심볼 경계를 걸쳐 시작해도 길이 (t − 1)·m + 1 = 15 × 8 + 1 = 121비트까지는 16개 이하의 심볼에만 걸립니다. 122비트부터는 17개 심볼에 걸칠 수 있어 정정이 보장되지 않습니다. 이 부호가 여러 비트가 한꺼번에 깨지는 상황에 강하다는 말의 구체적인 의미입니다.
활용 예로 우주통신 표준의 (255, 223) 부호, 디지털 방송의 단축 부호(204, 188), 광디스크의 교차 인터리브 리드솔로몬 부호(CIRC), QR코드가 있습니다. 주로 인터리빙이나 다른 부호와의 연접으로 쓰입니다.
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| 패리티가 32개면 오류 32개를 고친다. | 위치를 모르는 오류는 절반인 16개, 위치를 아는 소실은 32개까지입니다. 오류 e개와 소실 s개가 섞이면 2e + s ≤ n − k 가 조건입니다. |
| 비트 오류를 고치는 부호다. | 단위는 심볼입니다. 비트 오류가 서로 다른 심볼에 흩어지면 비트 수만큼 심볼 오류로 세므로 효율이 떨어집니다. |
| 리드솔로몬 부호는 길쌈부호나 LDPC와 같은 종류다. | 리드솔로몬은 대수적 블록 부호이고, 길쌈부호는 연속 흐름 부호, LDPC는 성긴 패리티 검사 행렬 기반 부호입니다. |
| 복호기가 오류 개수를 항상 알려 준다. | 정정 능력을 넘으면 복호 실패를 알리거나 잘못된 부호어로 복호할 수 있어, 실제 시스템은 별도의 검출 장치를 함께 둡니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
전체 심볼 중 일부에 여분을 두어 정해진 개수만큼의 오류 심볼을 스스로 정정할 수 있게 했다는 뜻입니다.
서로 다른 두 오류정정 부호를 이어 붙여 각각의 장점을 함께 활용했다는 의미입니다.
조금 더 깊게 보면
리드솔로몬 부호는 유한체 위에서 정의된 다항식 연산을 기반으로 하며, 원본 데이터를 다항식의 계수로 보고 여러 지점에서의 값을 함께 전송해 여분의 정보를 만듭니다. 심볼 단위로 오류를 처리하기 때문에 한 심볼 안에 여러 비트 오류가 몰려 있어도 심볼 하나의 오류로 취급되어, 버스트 오류에 유리한 특성을 가집니다.
리드솔로몬 부호가 정정할 수 있는 심볼 오류 개수는 부호에 추가된 여분 심볼 수의 절반으로 정해지며, 이 관계는 부호의 최소거리라는 수학적 성질로부터 유도됩니다.
주의할 점
비트가 여기저기 흩어져 무작위로 발생하는 오류에는 상대적으로 비효율적일 수 있으며, 심볼 단위 처리 특성상 부호 설계 시 심볼 크기와 정정 가능한 오류 개수 사이의 관계를 고려해야 합니다.
헷갈리기 쉬운 용어
순방향 오류정정 부호의 대표 종류와 비교합니다.
| 부호 | 처리 단위·구조 | 특징 |
|---|---|---|
| 리드솔로몬 부호 | 심볼 단위의 블록 부호 | 버스트 오류에 강하고 MDS 성질 |
| 길쌈부호화 | 연속된 비트 흐름에서 현재와 이전 비트를 조합 | 블록 경계가 없음 |
| 터보 부호화 | 두 부호화기를 인터리버로 병렬 결합, 반복 복호 | 반복 복호로 성능 향상 |
| 저밀도 패리티검사 부호 | 성긴 패리티검사 행렬의 선형 블록 부호 | 효율적인 반복 복호 |
참고 문헌
- Reed, I. S., & Solomon, G. (1960). Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2).
- Berlekamp, E. R. (1968). Algebraic Coding Theory. McGraw-Hill.
- MacWilliams, F. J., & Sloane, N. J. A. (1977). The Theory of Error-Correcting Codes. North-Holland.
- Wicker, S. B., & Bhargava, V. K. (Eds.). (1994). Reed-Solomon Codes and Their Applications. IEEE Press.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.