리드 솔로몬 부호

3. 기본 원리

리드-솔로몬 부호는 데이터를 특정 크기의 덩어리로 묶어 처리하며, 이 덩어리를 심볼이라고 부른다. 하나의 심볼은 ''r'' 비트로 구성된다.
부호어: N개의 심볼로 구성되며, 전체 비트 수는 ''r'' × N이다. 부호어는 K개의 정보 심볼과 (N-K)개의 중복 심볼로 나뉜다.
유한체 (갈루아체): 리드-솔로몬 부호는 2^''r''개의 원소를 갖는 유한체(갈루아체)를 사용한다. 각 심볼은 이 유한체의 원소에 대응된다. 유한체 연산의 예로, 덧셈은 XOR 연산을 사용하고, 곱셈은 원시 다항식을 사용하여 구현한다.
다항식 표현: 부호어는 심볼을 계수로 하는 (N-1)차 다항식으로 표현할 수 있다. 예를 들어, 8비트 심볼 A, B, C, D로 구성된 비트 열은 다음과 같은 다항식으로 표현된다.

: $Ax^3\; \backslash oplus\; Bx^2\; \backslash oplus\; Cx\; \backslash oplus\; D$
심볼 변환: ''r'' 비트를 하나의 심볼로 묶고, 2^''r''개의 원소를 갖는 갈루아체를 정의한다. ''r''차 원시 다항식을 선택하고 (예: r=8, $x^8\; \backslash oplus\; x^4\; \backslash oplus\; x^3\; \backslash oplus\; x^2\; \backslash oplus\; 1\; =\; 0$), 이 방정식의 근을 α라고 하면, α의 거듭제곱을 이용하여 각 비트 열에 대응시킨다.
생성 다항식: (N-K)차 다항식으로, 부호어 다항식을 생성하는 데 사용된다. 생성 다항식 ''G(x)''는 다음과 같이 표현된다.

: $G(x)\; =\; \backslash prod\_\{i=b\}^\{2t-1+b\}(x-\backslash alpha^i)$ (b는 적당한 정수)
오류 정정 능력: (N-K)/2 = ''t''개의 심볼 오류를 정정할 수 있다. 즉, 최대 ''t''개의 심볼에 오류가 발생해도 원래 데이터를 복원할 수 있다.

4. 부호화 (Encoding)

부호화는 다음과 같은 절차로 수행된다.

먼저 보낼 정보 K × ''r'' 비트를 심볼화하여 K-1차 다항식을 생성하며, 이를 정보 다항식(''I(x)'')이라고 한다. 다음으로, 생성 다항식을 준비한다.

:$G(x)\; =\; \backslash prod\_\{i=b\}^\{2t-1+b\}(x-\backslash alpha^i)$

위 식에서 b는 적당한 정수이다.

예를 들어 b=0으로 2 심볼의 오류를 정정하는 부호를 생성하면, t=2가 되고, 생성 다항식은 다음과 같다.

:$G(x)\; =\; (x-1)(x-\backslash alpha)(x-\backslash alpha^2)(x-\backslash alpha^3)\; =\; x^4\; +\; \backslash alpha^\{75\}x^3\; +\; \backslash alpha^\{249\}x^2\; +\; \backslash alpha^\{78\}x\; +\; \backslash alpha^\{6\}$

정보 다항식과 생성 다항식을 사용하여 다음과 같은 연산을 수행한다.

:$C(x)\; =\; x^\{N-K\}\; \backslash times\; I(x)\; +\; P(x)$

단,

:$P(x)\; \backslash equiv\; x^\{N-K\}\; \backslash times\; I(x)\; \backslash mod\; G(x)$

여기서 생성되는 C(x)에 대응하는 비트열이 전송되는 부호이다.

5. 복호화 (Decoding)

리드-솔로몬 부호의 복호 과정은 다음과 같다.

1. 오류 검출 및 신드롬 계산: 수신된 데이터에 오류가 있는지 확인하고, 오류가 있다면 신드롬을 계산한다. 신드롬은 다음과 같이 표현되는 2t개의 숫자이다.

::$S\_i\; =\; Y(\backslash alpha^\{i-1+b\}),\; (i=1,\backslash dots,2t)$

2. 오류 심볼 수 검출: 신드롬을 이용하여 오류를 포함하는 심볼의 개수를 찾는다.

3. 오류 위치 검출: 오류 위치 다항식을 생성하여 오류가 있는 심볼의 위치를 찾는다. 오류 위치 다항식은 다음과 같다.

::$\backslash sigma(x)\; =\; 1\; +\; \backslash sigma\_1x\; +\; \backslash sigma\_2x^2\; +\; \backslash cdots\; +\; \backslash sigma\_kx^k$

4. 오류 값 검출: 오류 위치와 신드롬을 이용하여 오류 값을 계산하고, 연립 일차 방정식을 사용하여 오류 값을 구한다.

5. 오류 정정: 오류 위치와 값을 이용하여 원래 데이터를 복원한다.

리드-솔로몬 부호의 복호 방법에는 피터슨법이나 유클리드법 등이 있다. 피터슨법은 처리가 단순하지만, 수정하는 심볼 수가 많을 때는 계산량이 증가하는 단점이 있다.

6. 응용 분야

리드-솔로몬 부호는 데이터의 오류를 정정하는 데 널리 사용되는 기술이다. 특히, 연속적인 데이터 손상(버스트 오류)에 강한 특징을 가지고 있다.

• 데이터 저장:
• 콤팩트 디스크(CD), DVD, 블루레이 디스크(BD) 등의 광학 디스크에 데이터를 기록하고 읽을 때 발생할 수 있는 오류를 정정한다. CD에서는 교차 인터리브 리드-솔로몬 부호(CIRC)라는 방식을 사용한다.^[7]
• QR 코드와 같은 2차원 바코드의 일부가 손상되어도 정확하게 데이터를 읽을 수 있도록 한다.
• 하드 디스크 및 RAID와 같은 대용량 저장 시스템에서 매체 결함으로 인한 오류를 수정한다.
• USENET에서 멀티미디어 파일과 함께 게시되는 파카이브 파일의 오류 정정에 사용된다.
• 2015년에 중단된 분산 온라인 스토리지 서비스 왈라(Wuala)에서 파일을 분할할 때 사용되었다.
• PDF-417, MaxiCode, Datamatrix 등 2차원 바코드에도 사용된다.

• 데이터 전송:
• xDSL과 같은 통신 시스템에서 데이터 전송 중 발생하는 오류를 정정한다.
• 위성 통신(DVB-S, DVB-S2) 및 우주 통신 (\보이저 계획, 마스 패스파인더, 카시니 탐사선 등)에서 잡음과 신호 간섭으로 인한 오류를 정정한다.^[7]
• 지상파 디지털 방송 에서도 사용된다.

• 기타:
• 포스트바 기호 체계와 같은 1차원 바코드에도 사용된다.

7. 한국의 관점

리드-솔로몬 부호는 1960년에 개발되어 오류 정정 능력이 뛰어나 지상파 디지털 텔레비전 방송, 위성 통신 등 다양한 분야에 활용되고 있다. 특히 여러 비트를 하나의 덩어리로 처리하여 연속적인 비트 오류(버스트 오류)에 강한 특성을 보인다. 이러한 특징 덕분에 한국의 디지털 방송, 통신, 저장 매체 기술 발전에 중요한 역할을 해왔다.

유럽식 디지털 방송 표준인 DVB-S, DVB-S2 등에 리드-솔로몬 부호가 채택되어 한국에서도 널리 사용되고 있으며, 데이터의 안정성과 신뢰성이 중요해지는 4차 산업혁명 시대에 리드-솔로몬 부호의 활용은 더욱 확대될 것으로 예상된다.

8. 추가 설명

리드-솔로몬 부호는 1960년에 어빙 스토이 리드와 구스타브 솔로몬이 개발한 오류 정정 부호이다. 부호 생성과 복호화가 복잡하여 처리 속도가 요구되는 분야에서는 많이 사용되지 않지만, 오류 정정 능력이 높아 지상파 디지털 방송, 위성 통신, ADSL, DVTR, CD, DVD, BD, QR 코드의 오류 정정에 응용되고 있다.

부호 생성에는 갈루아체(유한체) 개념을 사용한다. 여러 비트를 하나의 덩어리(심볼 또는 워드)로 간주하고, 부호어를 심볼 집합으로 나타내어 각 심볼 단위로 오류를 검출하고 정정한다. 하나의 심볼 내 비트가 아무리 많은 오류를 포함하더라도 "1 심볼 오류"로 간주되므로, 연속적인 비트 오류(버스트 오류)에 강하다. 1 심볼의 비트 수는 보통 정해져 있지 않지만, 컴퓨터 사양상 8비트(1바이트)로 구현되는 시스템이 많다.

''r'' 비트 덩어리를 하나의 심볼로, N개 심볼( ''r'' × N 비트 배열)을 하나의 부호어로 한다. K개 심볼은 전송할 정보이고, (N-K)개 심볼은 부호화로 생성되는 중복 심볼이다. ''r'', N, K는 다음 조건을 만족한다.

(N-K)/2 = ''t'' 일 때, 리드-솔로몬 부호는 ''t''개까지의 심볼 오류를 정정할 수 있다.

리드-솔로몬 부호 복호화 방법에는 피터슨법이나 유클리드법 등이 있다.

8. 1. 최대 거리 분리 부호 (MDS 부호)

참조

_[1] 간행물 1960
_[2] 논문 A class of cyclic linear error-correcting codes in ''p^m'' symbols 1961-06
_[3] 서적 Error-Correcting Codes MIT Press 1961
_[4] 서적 Error Correcting Codes "{{GBurl|5kfwlFeklx0[...] MIT Press 1996
_[5] 논문 A method for solving key equation for decoding Goppa codes 1975
_[6] 간행물 New Algorithm For Decoding Reed-Solomon Codes http://www.math.clem[...] Clemson 2002-01
_[7] 간행물 Reed–Solomon Codes and Their Applications IEEE Press
_[8] 서적 Reed Solomon Codes and Their Applications IEEE Press 1994
_[9] 논문 The development of turbo and LDPC codes for deep-space applications. https://scholar.arch[...] 2007
_[10] 간행물 1983
_[11] 웹사이트 Analytical Expressions Used in bercoding and BERTool https://www.mathwork[...] 2019-02-01
_[12] 간행물 Kissing Numbers, Sphere Packings, and Some Unexpected Proofs https://www.ams.org/[...] 2004-09
_[13] 간행물 A class of cyclic linear error-correcting codes in p^m symbols 1961-06
_[14] 서적 Error Correcting Codes 1961
_[15] 간행물 Error Control Coding 1982
_[16] 간행물 Improved decoding of Reed–Solomon codes and algebraic geometry codes 1999-09
_[17] 서적 Proceedings of the 55th Annual ACM Symposium on Theory of Computing Association for Computing Machinery 2023-06-02
_[18] 서적 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) 2023
_[19] 간행물 Randomly punctured Reed--Solomon codes achieve list-decoding capacity over linear-sized fields 2023-08-18
_[20] 논문 Algebraic soft-decision decoding of Reed–Solomon codes
_[21] 논문 Open Source Soft-Decision Decoder for the JT65 (63,12) Reed–Solomon Code http://physics.princ[...] 2017-06-07