리드-솔로몬 오류 수정

리드-솔로몬 코드
리드-솔로몬 코드
이름은 다음과 같습니다.	어빙 S. 리드와 구스타브 솔로몬
분류
계층	선형블록코드; 다항식 부호; 리드-솔로몬 코드
블록길이	n
메시지 길이	k
거리	n − k + 1
알파벳크기	q = pm ≥ n (p prime); 종종 n = q - 1.
표기법	[n, k, n - k + 1]-q코드
알고리즘
	베를레캄프-매시; 유클리드의; 기타의
특성.
	최대 거리 분리 가능 코드
	v; t;

리드-솔로몬 코드는 어빙 S에 의해 도입된 오류 수정 코드 그룹입니다. 리드와 구스타브 솔로몬은 ^[1]1960년에 그들은 많은 응용 프로그램을 가지고 있는데, 그 중 가장 두드러진 것은 MiniDisk, CD, DVD, Blu-ray 디스크, QR코드, DSL 및 WiMAX와 같은 데이터 전송 기술, 위성 통신, DVB 및 ATSC와 같은 방송 시스템, RAID 6와 같은 저장 시스템 등입니다.

리드-솔로몬 코드는 기호라는 유한장 요소 집합으로 취급되는 데이터 블록에서 작동합니다. 리드-솔로몬 코드는 여러 개의 심볼 오류를 감지하고 수정할 수 있습니다. 데이터에 $t$ = $n$ - k 체크 기호를 추가하면 리드-솔로몬 코드는 최대 $t개$ 의 잘못된 기호 조합을 감지하거나(정확하지는 않지만) 알 수 없는 위치에서 $최대$ ⌊t/2개의 ⌋ 잘못된 기호를 찾아 수정할 수 있습니다. 소거 코드로서 알고리즘에 알려진 위치에서 $최대$ 소거를 수정하거나 오류와 소거의 조합을 감지하고 수정할 수 있습니다. 리드-솔로몬 코드는 $b +1개$ 의 연속적인 비트 오류가 최대 $두$ 개의 크기 b 기호에 영향을 미칠 수 있기 때문에 다중 버스트 비트 오류 수정 코드로도 적합합니다. $t$ 의 선택은 코드의 설계자에게 달려 있으며 넓은 범위 내에서 선택할 수 있습니다.

리드-솔로몬 코드에는 두 가지 기본 유형(오리지널 뷰와 BCH 뷰)이 있습니다. BCH 뷰 디코더는 오리지널 뷰 디코더보다 더 빠르고 작업 스토리지가 덜 필요하기 때문에 BCH 뷰가 가장 일반적입니다.

역사

리드-솔로몬 코드는 1960년 어빙 S에 의해 개발되었습니다. 리드와 구스타브 솔로몬은 당시 MIT 링컨 연구소의 직원이었습니다. 그들의 중요한 기사 제목은 "특정 유한장에 대한 다항식 코드" (리드 & 솔로몬 1960)였습니다. Reed & Solomon 기사에 설명된 원래 인코딩 방식은 인코딩할 값(평가 포인트)의 고정 집합만 인코더와 디코더에 알려진 경우 인코딩할 메시지에 기반한 가변 다항식을 사용했습니다. 원래의 이론적 디코더는 수신된 메시지의 n(부호화된 메시지 길이) 값 중 k(부호화되지 않은 메시지 길이)의 하위 집합을 기반으로 잠재적 다항식을 생성하여 가장 일반적인 다항식을 올바른 다항식으로 선택했는데, 이는 가장 간단한 경우를 제외한 모든 경우에 비현실적이었습니다. 이는 처음에는 인코더와 디코더 모두에게 알려진 고정 다항식을 기반으로 한 BCH 코드와 같은 방식으로 원래 방식을 변경하여 해결했지만 나중에는 BCH 방식보다 느리지만 원래 방식을 기반으로 한 실용적인 디코더가 개발되었습니다. 그 결과 리드 솔로몬 코드는 크게 두 가지 종류가 있는데, 하나는 원래 인코딩 방식을 사용하는 것이고, 하나는 BCH 인코딩 방식을 사용하는 것입니다.

또한 1960년 Daniel Gorenstein과 Neal Zierler에 의해 개발된 BCH 코드에 대한 실용적인 고정 다항식 디코더가 1960년 1월 Zierler에 의해 MIT Lincoln Laboratory 보고서에 기술되었고 이후 1961년 6월 논문에 기술되었습니다.^[2] Gorenstein-Zierler 디코더 및 BCH 코드에 대한 관련 작업은 W에 의한 오류 수정 코드 책에 설명되어 있습니다. 웨슬리 피터슨 (1961).^[3] 1963년 J. J. Stone(또는 그 이전의 것)은 리드 솔로몬 코드가 고정 생성기 다항식을 사용하는 BCH 방식을 사용할 수 있다는 것을 인식하고 그러한 코드를 BCH 코드의 특별한 클래스로 만들었지만,^[4] 원래 인코딩 방식에 기반한 리드 솔로몬 코드는 BCH 코드의 클래스가 아니며 평가 포인트 세트에 따라 순환 코드도 아닙니다.

1969년, 개선된 BCH 방식 디코더가 Elwyn Berlekamp와 James Massey에 의해 개발되었고, 그 이후로 Berlekamp-Massey 디코딩 알고리즘으로 알려져 있습니다.

1975년, 또 다른 개선된 BCH 방식 디코더가 확장된 유클리드 알고리즘을 기반으로 스기야마 야스오에 의해 개발되었습니다.^[5]

1977년, Reed-Solomon 코드는 연결된 에러 정정 코드의 형태로 Voyager 프로그램에 구현되었습니다. 대량 생산된 소비자 제품에서 최초의 상업적 응용은 1982년에 콤팩트 디스크와 함께 등장했으며, 여기서 두 개의 인터리브된 리드-솔로몬 코드가 사용됩니다. 오늘날 리드-솔로몬 코드는 디지털 저장 장치와 디지털 통신 표준에서 널리 구현되고 있지만, 서서히 BCH(Bose-Chaudhuri-Hocquenghem) 코드로 대체되고 있습니다. 예를 들어, 리드-솔로몬 코드는 DVB(Digital Video Broadcasting) 표준 DVB-S에서 컨볼루션 내부 코드와 함께 사용되지만 BCH 코드는 후속 코드인 DVB-S2에서 LDPC와 함께 사용됩니다.

1986년 베를레캄프로 알려진 독창적인 방식의 디코더가웰치 알고리즘이 개발되었습니다.

1996년, 목록 디코더 또는 소프트 디코더라고 불리는 원래 방식 디코더의 변형이 Madhu Sudan 등에 의해 개발되었으며, 이러한 유형의 디코더에 대한 작업이 계속되고 있습니다 – Guruswami-Sudan 목록 디코딩 알고리즘 참조.

2002년에 슈홍 가오(Shuhong Gao)가 확장된 유클리드 알고리즘을 기반으로 또 다른 독창적인 방식 디코더를 개발했습니다.^[6]

적용들

데이터 저장

리드-솔로몬 코딩은 대용량 저장 시스템에서 미디어 결함과 관련된 버스트 오류를 수정하기 위해 매우 광범위하게 사용됩니다.

리드-솔로몬 코딩은 콤팩트 디스크의 핵심 구성 요소입니다. 이것은 대량 생산된 소비자 제품에 강력한 오류 정정 코딩을 처음으로 사용한 것이며, DAT와 DVD는 비슷한 방식을 사용합니다. CD에서는 28방향 컨볼루션 인터리버에 의해 분리된 리드-솔로몬 코딩의 두 계층이 교차 인터리브 리드-솔로몬 코딩(CIRC)이라는 방식을 산출합니다. CIRC 디코더의 첫 번째 요소는 상대적으로 약한 내부(32,28) 리드-솔로몬 코드이며, 8비트 심볼을 가진 (255,251) 코드에서 단축됩니다. 이 코드는 32바이트 블록당 최대 2바이트 오류를 수정할 수 있습니다. 더 중요한 것은 수정할 수 없는 블록, 즉 2바이트 이상의 오류가 있는 블록을 지우는 것으로 플래그를 지정합니다. 소거 표시가 있는 디코딩된 28-바이트 블록들은 그 후 디인터리버에 의해 (28,24) 외부 코드의 다른 블록들로 퍼집니다. 디인터리빙 덕분에 내부 코드에서 삭제된 28바이트 블록은 28개의 외부 코드 블록 각각에서 하나의 삭제된 바이트가 됩니다. 외부 코드는 블록당 최대 4개의 삭제를 처리할 수 있기 때문에 이를 쉽게 수정합니다.

결과적으로 디스크 표면에서 4000비트, 즉 약 2.5mm까지 오류 버스트를 완전히 수정할 수 있는 CIRC입니다. 이 코드는 매우 강력하기 때문에 대부분의 CD 재생 오류는 수정할 수 없는 오류 버스트가 아니라 레이저가 트랙을 점프하게 하는 추적 오류로 인해 발생합니다.^[7]

DVD는 비슷한 방식을 사용하지만 훨씬 큰 블록, (208,192) 내부 코드 및 (182,172) 외부 코드를 사용합니다.

리드-솔로몬 오류 수정은 일반적으로 USENET의 멀티미디어 파일과 함께 게시되는 양피지 파일에도 사용됩니다. 분산형 온라인 스토리지 서비스인 Wuala(2015년 중단)도 파일을 분해할 때 Reed-Solomon을 사용했습니다.

바코드

PDF-417, 맥시코드, 데이터매트릭스, QR코드, 아즈텍코드 등 거의 모든 2차원 바코드는 리드-솔로몬 오류 수정을 사용하여 바코드 일부가 손상되어도 올바른 판독이 가능합니다. 바코드 스캐너가 바코드 기호를 인식할 수 없으면 삭제로 처리합니다.

리드-솔로몬 코딩은 1차원 바코드에서는 덜 일반적이지만 PostBar 심볼릭에서 사용됩니다.

데이터전송

특수 형태의 리드-솔로몬 코드, 특히 Cauchy-RS 및 Vandermonde-RS는 삭제 채널을 통한 데이터 전송의 신뢰할 수 없는 특성을 극복하는 데 사용될 수 있습니다. 인코딩 프로세스는 데이터의 K개 심볼을 저장하는 길이 N개 심볼의 N개 코드워드가 생성된 후 소거 채널을 통해 전송되는 RS(N, K) 코드를 가정합니다.

다른 쪽 끝에 수신된 K개의 코드워드들의 어떤 조합도 N개의 코드워드들을 모두 재구성하기에 충분합니다. 채널의 삭제 가능성을 적절하게 모델링할 수 있고 더 적게 볼 수 있는 경우가 아니라면 코드 레이트는 일반적으로 1/2로 설정됩니다. 결론적으로 N은 일반적으로 2K입니다. 즉, 전송된 모든 코드워드를 재구성하려면 전송된 모든 코드워드의 절반 이상을 수신해야 합니다.

리드-솔로몬 코드는 xDSL 시스템과 CCSDS의 우주 통신 프로토콜 사양에서도 순방향 오류 수정의 형태로 사용됩니다.

우주전송

심층 공간 연결 코딩 시스템입니다.^[8] 표기: RS(255, 223) + CC(" constraint 길이" = 7, 코드 레이트 = 1/2).

Reed-Solomon 코딩의 중요한 응용 중 하나는 Voyager 프로그램에 의해 전송된 디지털 사진을 인코딩하는 것이었습니다.

보이저는 컨벌루션 코드와 연결된 리드-솔로몬 코딩을 도입했으며, 이는 이후 심해 공간 및 위성(예: 직접 디지털 방송) 통신에서 매우 널리 보급되었습니다.

비터비 디코더는 짧은 버스트에서 오류를 발생시키는 경향이 있습니다. 이러한 버스트 오류를 수정하는 작업은 짧거나 단순화된 리드-솔로몬 코드로 수행하는 것이 가장 좋습니다.

연결된 리드-솔로몬/비터비 디코딩 컨볼루션 코딩의 현대 버전은 Mars Pathfinder, Galileo, Mars Exploration Rover 및 Cassini 미션에 사용되었으며, 샤넌 용량의 최종 한계에서 약 1~1.5dB 이내의 성능을 발휘합니다.

이러한 연결 코드는 이제 보다 강력한 터보 코드로 대체되고 있습니다.

NASA 임무에^[9] 사용되는 채널 코딩 방식

몇 해	코드	미션
1958년 ~ 현재	코드화되지 않음	탐험가, 매리너 등 많은 사람들이
1968–1978	컨벌루션 코드 (CC) (25, 1/2)	개척자, 금성
1969–1975	리드-뮬러 코드 (32, 6)	매리너, 바이킹
1977년 ~ 현재	이진 골레이 코드	보이저
1977년 ~ 현재	RS(255, 223) + CC(7, 1/2)	보이저, 갈릴레오, 그 외 많은 사람들이
1989–2003	RS(255, 223) + CC(7, 1/3)	보이저
1989–2003	RS(255,223) + CC(14,1/4)	갈릴레오
1996~현재	RS + CC (15, 1/6)	카시니, 마스 패스파인더 등
2004년 ~ 현재	터보코드^{[nb 1]}	메신저, 스테레오, MRO, 기타
est. 2009	LDPC 코드	별자리, MSL

작도(부호화)

리드-솔로몬 코드는 실제로 코드 계열이며, 모든 $q$ 는알파벳크기 q {\ $displaystyle$ $n$ 블록 $길이$ n ${\$ displaystyle n} $및$ $메시지$ $길이$ k ${\displaystyle$ k}의 세 가지 매개 변수로 특징지어지며 $k$ $k<n\leq q$ < n $k<n\leq q$ $q {\displaystyle$ k< n $\leq q}$ 입니다 $k<n\leq q$ 알파벳 기호 집합은 순서 $q$ $q$ 의 $F$ 유한 $필드$ F $F$ 로 해석되므로 $q$ $q$ $q$ 는 프라임 전력이어야 $q$ 합니다. 리드-솔로몬 코드의 가장 유용한 파라미터화에서, 블록 길이는 일반적으로 메시지 길이의 일부 일정한 배수, 즉 $R={\frac {k}{n}}$ $R={\frac {k}{n}}$ = ${\display$ R = {\frac {k}{n}}는 일부 일정하며, 더 나아가 블록 길이는 알파벳 크기와 동일하거나 1보다 작습니다. $n=q$ = $n=q$ $displaysty$ $n=q$ $e$ n $=$ q} 또 $n=q$ n = q - 1 {\displaysty $n=q$ e n=q-1}입니다.

리드 & 솔로몬의 원래 견해: 값들의 시퀀스로서 코드워드

리드-솔로몬 코드의 인코딩 절차가 다르므로 모든 코드워드 집합을 설명하는 방법도 다릅니다. 리드 & 솔로몬의 원래 견해(1960)에서 리드-솔로몬 부호의 모든 부호어는 $k$ $k$ 보다 작은 다항식의 함수 값의 수열입니다 $k$ 리드-솔로몬 부호어를 구하기 위해서, 메시지 기호(각각 q 크기 알파벳 내)는 $q$ $q$ 요소가 $q$ 있는 $F$ 유한 필드 $F$ ${\displaystyle$ $F$ $}$ 에 대해 k보다 작은 차수의 $p$ $다항식$ p ${\displaystyle$ p $}$ 의 계수로 처리됩니다. 차례로, 다항식 p는 필드 $a_{1},\dots ,a_{n}$ 의 $a_{1},\dots ,a_{n}$ $a_{1},\dots ,a_{n}$ ≤ q 개의 구별점 a $a_{1},\dots ,a_{n}$ ${\$ 에서 평가되며, 값의 순서는 해당 코드워드입니다. 평가 점 집합에 대한 일반적인 선택은 {0, 1, 2, ..., n - 1}, {0, 1, α, α², ..., αⁿ⁻²} 또는 n < q, {1, α, α², ..., α는ⁿ⁻¹ F의 원시 요소입니다.

형식적으로 리드-솔로몬 코드의 코드워드 $\mathbf {C}$ 집합 $\mathbf {C}$ ${\$ 는 다음과 같이 정의됩니다.

{\displaystyle \mathbf {C} ={\Bigl \{}\;{\bigl(}p(a_{1}),p(a_{2}),\dots,p(a_{n}){\bigr}}\;{\bigr}\;p{\text{는}F{\text{ of degree}}<k\;{\Bigr \}\,}에 대한 다항식입니다.

k

k

보다 차수가 작은 두 개의 고유 다항식은

k-1

k-1

- 1

k-1

지점에서 일치하므로 리드-솔로몬 코드의 두 코드워드가

n-(k-1)=n-k+1

n

n-(k-1)=n-k+1

-

n-(k-1)=n-k+1

(

n-(k-1)=n-k+1

-

n-(k-1)=n-k+1

=

n-(k-1)=n-k+1

-

n-(k-1)=n-k+1

+

n-(k-1)=n-k+1

1 {\displaystyle n - (k-1) = n - k + 1} 위치에서 일치하지 않음을 의미합니다.

k-1

k

k-1

-

k-1

k-1

점에서 일치하지만 같지 않은 두 개의 다항식이 있으므로 리드-솔로몬 코드의 거리는

d=n-k+1

d=n-k+1

=

d=n-k+1

-

d=n-k+1

k + 1 {\displaystyle d = n-k + 1}입니다. 그러면 상대 거리는 δ = d /

n

= 1 -

R=k/n

/ n + 1 / n = 1 - R + 1 / n ~ 1 - R {\displaystyle \ delta = d/n = 1-k/n+1/n = 1-R+1/n\sim 1-R}이며, 여기서 R = k / n {\display R= k/n}은 속도입니다. 싱글턴 경계에 의해 모든 코드가

\delta +R\leq 1+1/n

δ

\delta +R\leq 1+1/n

+ R ≤ 1

\delta +R\leq 1+1/n

+

\delta +R\leq 1+1/n

/ n

{\displaystyle \delta

+

R\leq

1+ 1/n}을 만족하기 때문에 상대 거리와 속도 사이의 이러한 균형은 점근적으로 최적입니다. 리드-솔로몬 코드는 이러한 최적의 균형을 달성하는 코드로 최대 거리 분리 가능 코드 클래스에 속합니다.

k보다 작은 차수의 다른 다항식의 수와 다른 메시지의 수는 모두 $q^{k}$ ${\$ 와 $q^{k}$ 같으므로 모든 메시지가 이러한 다항식에 고유하게 매핑될 수 있지만 이 인코딩을 수행하는 다른 방법이 있습니다. 리드 & 솔로몬의 원래 구성(1960)은 메시지 x를 다항식 p의 계수로 해석하는 반면, 후속 구성은 메시지를 첫 번째 k 지점 $a_{1},\dots ,a_{k}$ $a_{1},\dots ,a_{k}$ $a_{1},\dots ,a_{k}$ ${\$ $a_{k}}$ 이 $a_{1},\dots ,a_{k}$ 값들을 k보다 작은 다항식으로 보간하여 다항식 p를 구합니다. 후자의 인코딩 절차는 약간 덜 효율적이지만 체계적인 코드를 생성한다는 장점이 있습니다. 즉, 원본 메시지는 항상 코드워드의 하위 시퀀스로서 포함됩니다.

간단한 인코딩 절차: 계수 시퀀스로서의 메시지

Reed & Solomon(1960)의 원래 구성에서 $m=(m_{0},\dots ,m_{k-1})\in F^{k}$ m = $m=(m_{0},\dots ,m_{k-1})\in F^{k}$ $…, m$ k - 1) ∈ $Fk$ {\displaystyle m = (m_{0},\ dots,m_{k-1})\in F^{k}는 다항식 pm {\displaystyle p_{m}}에 매핑됩니다.

p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}\,.

The codeword of

m

is obtained by evaluating

p_{m}

at

n

different points

a_{0},\dots ,a_{n-1}

of the field

F

. 따라서 고전 부호화 함수

C:F^{k}\to F^{n}

:

C:F^{k}\to F^{n}

C:F^{k}\to F^{n}

→ F {\

displaystyle

C

:

리드-솔로몬 코드에 대한

C:F^{k}\to F^{n}

F^{k}\to F^{n}}

는 다음과 같이 정의됩니다.

C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}

This function

C

is a linear mapping, that is, it satisfies

C(m)=Am

for the following

n\times k

-matrix

A

with elements from

F

:

C(m)=Am={\begin{bmatrix}1&a_{0}&a_{0}^{2}&\dots &a_{0}^{k-1}\\1&a_{1}&a_{1}^{2}&\dots &a_{1}^{k-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&a_{n-1}&a_{n-1}^{2}&\dots &a_{n-1}^{k-1}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}

이 행렬은 $F$ $F$ 위의 반데르몽 행렬입니다 $F$ 즉, 리드-솔로몬 코드는 선형 코드이며, 고전적인 인코딩 절차에서 생성 $A$ 은 A ${\displaystyle$ A $}$ 입니다 $A$

체계적인 인코딩 절차: 값의 초기 시퀀스로서 메시지

체계적인 리드-솔로몬 코드를 생성하는 대체 인코딩 절차가 있습니다. 여기서는 다른 다항식 $p_{m}$ ${\$ 을 사용합니다 $p_{m}$ 이 변형에서 다항식 $p_{m}$ ${\$ 은 $k$ $k$ 보다 작은 차수의 고유 다항식으로 정의되어 $p_{m}$ $k$ 다음과 같습니다.

p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.

이

다항식

p_{m}

{\

을 m

m

에서

p_{m}

계산하려면

m

라그랑주 보간법을 사용할 수 있습니다. 발견되면 다른 지점

a_{k},\dots ,a_{n-1}

a_{k},\dots ,a_{n-1}

-

a_{k},\dots ,a_{n-1}

{\

에서 평가됩니다

a_{k},\dots ,a_{n-1}

C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}

This variant is systematic since the first $k$ entries, $p_{m}(a_{0}),\dots ,p_{m}(a_{k-1})$ , are exactly $m_{0},\dots ,m_{k-1}$ by the definition of $p_{m}$ .

이산 푸리에 변환과 그 역

이산 푸리에 변환은 기본적으로 인코딩 절차와 동일합니다. 이 변환은 생성기 $p_{m}$ $p_{m}$ ${\$ 을 사용하여 $p_{m}$ 위와 같은 메시지 값으로 평가 지점 집합을 매핑합니다.

C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}

역 푸리에 변환은 n < q 메시지 값의 오류 없는 집합을 다시 k 계수의 인코딩 다항식으로 변환하는 데 사용될 수 있으며, 이것이 작동하기 위해서는 메시지를 인코딩하는 데 사용되는 평가 포인트 집합이 α의 증가하는 거듭제곱의 집합이어야 한다는 제약 조건을 가지고 있습니다.

a_{i}=\alpha^{i}

a_{0},\dots,a_{n-1}=\{1,\alpha,\alpha^{2},\dots,\alpha^{n-1}\

그러나 라그랑주 보간은 평가 포인트 세트 또는 메시지 값의 오류 없는 세트의 요구 사항에 대한 제약 없이 동일한 변환을 수행하며 체계적인 인코딩 및 Gao 디코더의 단계 중 하나에서 사용됩니다.

BCH 보기: 계수 시퀀스로서의 코드워드

이 보기에서 메시지는 다항식 $p(x)$ ${\displaystyle$ p $(x)}$ 의 계수로 해석됩니다 $p(x)$ 송신자는 $n\leq q-1$ $n-1$ $n\leq q-1$ $n\leq q-1$ - $n\leq q-1$ ${\displaystyle$ $n-1$ $}$ 인 $s(x)$ $n-1$ n $s(x)$ ≤ q - 1 ${\displaystyle$ $n$ $\leq q-1}$ 의 관련 $s(x)$ ( $s(x)$ ${\displaystyle$ $s$ $(x)}$ 을 계산하여 $n\leq q-1$ $s(x)$ ( $s(x)$ ${\displaystyle$ s $(x)}$ 을 보냅니다 $s(x)$ $s(x)$ ( $s(x)$ $s(x)$ 은 $k-1$ - $k-1$ $k-1$ 인 메시지 다항식 $p(x)$ ${\displaystyle$ p $(x)}$ 를 곱하여 구성됩니다 $s(x)$ $k-1$ 송신자와 수신자 모두에게 알려진 $n-k$ $n-k$ - $n-k$ $n-k$ 차수의 $g(x)$ 생성기 다항식 $g(x)$ ${\displaystyle$ g $(x))$ 를 사용합니다. 생성기 $g(x)$ g $g(x)$ ${\displaystyle$ g $(x))$ 는 근이 갈루아 필드 원시 $\alpha$ $\alpha$ 의 순차적 거듭제곱인 다항식으로 정의됩니다 $g(x)$ .

g(x)=\left(x-\alpha ^{i}\right)\left(x-\alpha ^{i+1}\right)\cdots \left(x-\alpha ^{i+n-k-1}\right)=g_{0}+g_{1}x+\cdots +g_{n-k-1}x^{n-k-1}+x^{n-k}

"narrow 감지 코드"의 경우 $i=1$ = $1 {\$ displaystyle i=1}입니다.

{\displaystyle \mathbf {C} =\left\{\left(s_{1},s_{2},\dots,s_{n}\right)\;{\Big}\;s(a)=\sum_{i=1}^{i}a^{i}{\text{는 적어도 근을 갖는 다항식입니다}\alpha^{1},\alpha^{2},\alpha^{k}\right\}.

체계적인 부호화 절차

리드-솔로몬 코드의 BCH 뷰에 대한 인코딩 절차는 각 코드워드가 메시지를 접두사로 포함하고 단순히 오류 수정 기호를 접미사로 추가하는 체계적인 인코딩 절차를 산출하도록 수정될 수 있습니다. 여기서 인코더는 $s(x)=p(x)g(x)$ = p $)$ g( $p(x)$ ${\displaystyle$ s $(x$ ) = p(x) g(x $)}$ 를 보내는 대신 k $p(x)$ {\displaystyle k} 가장 큰 모노말의 계수가 p(x) {\displaystyle p(x)}의 해당 계수와 동일하도록 전송된 다항식 s(x) {\displaystyle s(x)}를 구성합니다. and the lower-order coefficients of $s(x)$ are chosen exactly in such a way that $s(x)$ becomes divisible by $g(x)$ . Then the coefficients of $p(x)$ are a subsequence of the coefficients of $s(x)$ . 전체적으로 체계적인 코드를 얻기 위해 메시지를 계수 시퀀스로 해석하여 $p(x)$ 메시지 다항식 $p(x)$ $p(x)$ 를 구성합니다.

공식적으로 $p(x)$ 은 $t=n-k$ $p(x)$ $t=n-k$ ) ${\$ $displaystyle$ p( $x$ $)}$ 에 x t ${\displaystyle$ x $^{$ $t}}$ 를 $x^{t}$ t = n $t=n-k$ - k {\ $displaystyle$ t = n-k} 체크 기호가 들어갈 자리를 마련하고, 해당 곱을 g( $p(x)$ ) {\displaystyle g(x)}로 나누어 나머지를 구한 다음 이를 차감하여 나머지를 보상합니다. $t$ $t$ 검사 $t$ 기호는 나머지 $s_{r}(x)$ $s_{r}(x)$ 을 계산하여 생성됩니다 $s_{r}(x)$

s_{r}(x)=p(x)\cdot x^{t}\ {\bmod {\ }}g(x).

나머지는 최대 $t-1$ - $t-1$ $t-1$ 의 차수를 갖는 $t-1$ 반면 $p(x)\cdot x^{t}$ $p(x)\cdot x^{t}$ ( $x$ ⋅ x ${\displaystyle p(x)\cdot$ x $^{$ t}}에서 $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ t - $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ , $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ - $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ x $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ , $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ ${\displaystyle$ x $^{t-1}, x^{t-2},\dots, x^{1},$ x $^{0}$ 의 계수는 0입니다. 따라서 $s(x)$ ) $s(x)$ 의 다음 정의는 첫 $번째$ k $k$ {\ $displaystyle$ k} $p(x)$ 가 $p(x)$ p $p(x)$ ) $p(x)$ {\ $displaystyle$ p( $x)}$ 의 계수와 동일하다는 특성을 $s(x)$ 갖습니다 $p(x)$

s(x)=p(x)\cdot x^{t}-s_{r}(x)\,.

$s(x)$ 코드워드 $s(x)$ ( $s(x)$ ${\displaystyle$ s $(x)}$ 는 $s(x)$ 실제로 $\mathbf {C}$ ${\$ 의 요소이며, 즉 $\mathbf {C}$ 생성 다항식 $g(x)$ $g(x)$ 로 나눌 수 있습니다 $g(x)$ ^[10]

s(x)\equiv p(x)\cdot x^{t}-s_{r}(x)\equiv s_{r}(x)-s_{r}(x)\equiv 0\mod g(x)\,.

특성.

리드-솔로몬 코드는 [n, k, n - k + 1] 코드입니다. 즉, 차원 k와 최소 해밍 거리 ${\textstyle d_{\min }=n-k+1.}$ = ${\textstyle d_{\min }=n-k+1.}$ - k ${\textstyle d_{\min }=n-k+1.}$ + ${\textstyle d_{\min }=n-k+1.}$ 길이 n(F 이상)의 선형 블록 코드입니다 ${\textstyle d_{\min }=n-k+1.}$ {\textstyle d_{\min } = $n-k+1$ .} ${\textstyle d_{\min }=n-k+1.}$ 리드-솔로몬 코드는 최소 거리가 크기의 선형 코드(n, k)에 대해 가능한 최대값을 갖는다는 점에서 최적이며, 이를 싱글톤 바운드라고 합니다. 이러한 코드는 MDS(Maximum Distance Separable) 코드라고도 합니다.

리드-솔로몬 코드의 오류 수정 능력은 $n-k$ 거리 또는 이에 준하는 $n-k$ n - $n-k$ $n-k$ 에 의해 블록 내 중복성의 척도로 결정됩니다. 오류 기호의 위치를 미리 알 수 없는 경우 리드-솔로몬 코드는 오류 기호를 최대 $(n-k)/2$ ( $(n-k)/2$ - k $(n-k)/2$ ) $(n-k)/2$ / $(n-k)/2$ ${\displaystyle ($ n - k) / 2 $}개$ 까지 $(n-k)/2$ 수정할 수 있습니다. 즉, 블록에 중복 기호가 추가된 만큼 오류를 절반까지 수정할 수 있습니다. 때때로 오류 위치가 미리 알려져 있습니다(예: 복조기 신호 대 잡음비의 "측면 정보"). 이를 소거라고 합니다. 리드-솔로몬 코드(다른 MDS 코드와 마찬가지로)는 오류보다 두 배 많은 삭제를 수정할 수 있으며, 오류와 삭제의 모든 조합은 $2E$ + $S$ ≤ n - $k$ 의 관계를 만족하는 한 수정할 수 있습니다. 여기서 $E$ $E$ 는 $E$ 오류 수이고 $S$ $S$ 는 $S$ 블록의 삭제 수입니다.

이론적 오류 경계는 FSK의 AWGN 채널에 대해 다음 공식을 통해 설명할 수 있습니다.^[11]

P_{b}\approx {\frac {2^{m-1}}{2^{m}-1}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }

기타 변조 방식의 경우:

P_{b}\approx {\frac {1}{m}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }

여기서

{\textstyle t={\frac {1}{2}}(d_{\min }-1)}

=

{\textstyle t={\frac {1}{2}}(d_{\min }-1)}

(

P_{s}=1-(1-s)^{h}

min - 1 )

h={\frac {m}{\log _{2}M}}

textstyle t = {\

frac

{1

}{2

}}(d_{\min }-1)}, Ps = 1 - (1 - s) h {\displaystyle P_{s} = 1 - (1-s)^{h}}, h = m log 2 ⁡ M {\displaystyle h = {\frac {m}{\log _{2}M}},

s

s

는

s

코드화되지 않은 AWGN 케이스의 심볼 오류율이고 M

{\displaystyle

M

}

은

M

변조 차수입니다.

리드-솔로몬 코드의 실용적인 사용을 위해서는 $2^{m}$ ${\$ 개의 $2^{m}$ 가 $F$ $2^{m}$ 있는 $유한$ 필드 F $F$ 를 사용하는 것이 일반적입니다. 이 경우 각 기호는 $m$ $m$ -bit $m$ 값으로 나타낼 수 있습니다. 송신자는 데이터 포인트를 인코딩된 블록으로 전송하고 인코딩된 블록의 심볼 수는 $n=2^{m}-1$ = $n=2^{m}-1$ - 1 $display n$ = 2^{ $m$ }-1}입니다. 따라서 8비트 심볼에서 작동하는 리드-솔로몬 코드는 블록당 n = 28 - 1 = 255 {\display n = 2^{8}-1 = 255}개의 심볼을 가집니다. (이 값은 바이트 지향 컴퓨터 시스템이 널리 보급되어 있기 때문에 매우 인기 있는 값입니다.) 블록 내 데이터 심볼의 k ${\displaystyle k$ $},$ $k$ $k<n$ < $k<n$ ${\displaystyle$ k< $n}$ 인 $k<n$ 숫자 $k$ 는 설계 파라미터입니다. 일반적으로 사용되는 코드는 n = 255 {\displaystyle n = 255} - symbol $k=223$ 에서 k = ${\$ displaystyle k = $(n,k)=(255,223)$ 223} 8비트 데이터 심볼에 32개의 8비트 패리티 심볼을 추가하여 인코딩하며, 이는 (n, k) = (255, 223) {\displaystyle (n, k) = (255, 223)} 코드로 표시되며, 블록당 최대 16개의 심볼 오류를 수정할 수 있습니다.

위에서 설명한 리드-솔로몬 코드 속성은 특히 오류가 발생하는 애플리케이션에 적합합니다. 이는 코드에 오류가 있는 비트 수는 상관없기 때문입니다. 한 심볼의 여러 비트가 손상된 경우 단일 오류로 계산됩니다. 반대로, 데이터 스트림이 오류 버스트나 드롭아웃이 아니라 무작위 단일 비트 오류로 특징지어지는 경우, 리드-솔로몬 코드는 일반적으로 이진 코드에 비해 좋지 않은 선택입니다.

리드-솔로몬 코드는 컨볼루션 코드와 마찬가지로 투명 코드입니다. 즉, 채널 기호가 선을 따라 어딘가로 반전된 경우 디코더가 계속 작동합니다. 결과는 원래 데이터의 반전이 될 것입니다. 그러나 리드-솔로몬 코드는 코드가 짧아지면 투명도를 잃게 됩니다. 단축 코드의 "누락" 비트들은 데이터의 보완 여부에 따라 0이나 1로 채워져야 합니다. (즉, 기호들이 반대로 바뀌면 제로 메움은 1 메움으로 바뀌어야 합니다.) 이러한 이유로 리드-솔로몬 디코딩 전에 데이터 감지(즉, 참 또는 보완)를 해결해야 합니다.

리드-솔로몬 코드가 순환적인지 아닌지는 구성의 미묘한 세부 사항에 달려 있습니다. 코드워드가 다항식의 값인 리드와 솔로몬의 원래 관점에서, 코드를 순환적으로 만드는 방식으로 평가 포인트의 순서를 선택할 수 있습니다. In particular, if $\alpha$ is a primitive root of the field $F$ , then by definition all non-zero elements of $F$ take the form $\alpha ^{i}$ for $i\in \{1,\dots ,q-1\}$ , where $q= F$ . Each polynomial $p$ over $F$ gives rise to a codeword $(p(\alpha ^{1}),\dots ,p(\alpha ^{q-1}))$ . ↦ $a\mapsto p(\alpha a)$ a) {\ $displaystyle$ a $\mapstop$ p $(\alpha$ a)} 함수도 $같은$ 차수의 다항식이므로, 이 함수는 코드워드(p(α 2), …, p(α q) {\displaystyle(p(\alpha ^{2}),\dots,p(\alpha ^{q})}; α = α 1 {\displaystyle \alpha ^{q}=\alpha ^{1}}가 유지되므로, 이 코드워드는 $p$ ${\displaystyle$ p $}$ 에서 파생된 원래 코드워드의 순환 왼쪽 시프트입니다 $p$ 따라서 원시 루트 파워의 시퀀스를 평가 포인트로 선택하면 원래 보기 리드-솔로몬 코드가 순환됩니다. BCH 보기의 리드-솔로몬 코드는 BCH 코드가 순환적이기 때문에 항상 순환적입니다.

언급

설계자는 리드-솔로몬 코드 블록의 "자연스러운" 크기를 사용할 필요가 없습니다. "단축"이라고 알려진 기술은 더 큰 코드에서 원하는 크기의 더 작은 코드를 생성할 수 있습니다. 예를 들어, 널리 사용되는 (255,223) 코드는 소스 블록의 사용되지 않는 부분을 95개의 이진 제로로 패딩하고 전송하지 않음으로써 (160,128) 코드로 변환될 수 있습니다. 디코더에서 블록의 동일한 부분은 이진 0으로 로컬로 로드됩니다. Delsarte–Goethals–Seidel^[12] 정리는 단축된 리드-솔로몬 코드의 적용 예를 보여줍니다. 단축과 병행하여 천공으로 알려진 기술은 인코딩된 패리티 심볼 중 일부를 생략할 수 있습니다.

BCH 뷰 디코더

이 섹션에서 설명하는 디코더는 계수 시퀀스로 코드워드의 BCH 뷰를 사용합니다. 인코더와 디코더 모두에게 알려진 고정된 생성기 다항식을 사용합니다.

피터슨-고렌슈타인-지에러 디코더

Daniel Gorenstein과 Neal Zierler는 1960년 1월 Zierler의 MIT Lincoln Laboratory 보고서에 기술된 디코더를 개발했고 이후 1961년 6월 논문에 기술되었습니다.^[13] Gorenstein-Zierler 디코더 및 BCH 코드에 대한 관련 작업은 W에 의한 오류 수정 코드 책에 설명되어 있습니다. 웨슬리 피터슨 (1961).^[14]

공식화

전송된 메시지 $(c_{0},\ldots ,c_{i},\ldots ,c_{n-1})$ $(c_{0},\ldots ,c_{i},\ldots ,c_{n-1})$ $(c_{0},\ldots ,c_{i},\ldots ,c_{n-1})$ $(c_{0},\ldots ,c_{i},\ldots ,c_{n-1})$ - $(c_{0},\ldots ,c_{i},\ldots ,c_{n-1})$ ${\displaystyle(c_{0},\ldots, c_{i},\ldots, c_{n-1$ 는 다항식 s(x)의 계수로 표시됩니다.

s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}

리드-솔로몬 인코딩 절차의 결과로 s(x)는 생성기 다항식 g(x)로 나뉩니다.

g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),

여기서 α는 원시 원소입니다.

s(x)는 생성기 g(x)의 배수이므로 모든 근을 "상속"합니다.

s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0

그러므로,

s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k

전송된 다항식은 에러 다항식 e(x)에 의해 전송 중에 손상되어 수신된 다항식 r(x)를 생성합니다.

r(x)=s(x)+e(x)

e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}

계수 e는_i x의 거듭제곱에서 오차가 없으면 0이고, 오차가 있으면 0이 아닙니다. 만약 x의 서로 다른 거듭제곱 i에서 ν 오류가 있다면,

e(x)=\sum _{k=1}^{\nu}e_{i_{k}}x^{i_{k}

디코더의 목표는 오류 수(ν), 오류 위치(i) 및 해당 위치(e)의 오류 값을 찾는 것입니다. 이 중에서 e(x)를 계산하고 r(x)에서 빼서 원래 전송된 메시지 s(x)를 얻을 수 있습니다.

신드롬 해독

디코더는 $\alpha ^{1}\dots \alpha ^{n-k}$ $\alpha ^{1}\dots \alpha ^{n-k}$ 1 … $\alpha ^{1}\dots \alpha ^{n-k}$ - k $\alpha ^{1}\dots \alpha ^{n-k}$ {\ $displaystyle \alpha^{1}\dots \alpha^{n-k}}$ 에서 받은 다항식을 평가하는 것으로 시작합니다 $\alpha ^{1}\dots \alpha ^{n-k}$ 우리는 그 평가의 결과를 "신드롬", S라고_j 부릅니다. 다음과 같이 정의됩니다.

{\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}\left(\alpha ^{j}\right)^{i_{k}},\quad j=1,2,\ldots ,n-k\end{aligned}}

s(\alpha ^{j})=0

섹션과 같이 s(x) {\displaystyle s(x)}가 αj {\displaystyle \alpha ^{j}}에 루트가 있으므로 s

s(\alpha ^{j})=0

j

s(\alpha ^{j})=0

=

s(\alpha ^{j})=0

{\

displaystyle

s(\

alpha

^{j

}) = 0}임을 유의하십시오.

신드롬을 살펴보는 것의 장점은 메시지 다항식이 탈락한다는 것입니다. 즉, 신드롬은 오류와 관련된 것일 뿐이며, 전송되는 메시지의 실제 내용에 영향을 받지 않습니다. 신드롬이 모두 0인 경우 알고리즘은 여기서 멈추고 메시지가 전송 중에 손상되지 않았다고 보고합니다.

오류 로케이터 및 오류 값

편의상 오차 로케이터 X_k 및 오차 값 Y를_k 다음과 같이 정의합니다.

X_{k}=\alpha ^{i_{k}},\ Y_{k}=e_{i_{k}}

그런 다음 이러한 오류 로케이터 및 오류 값으로 신드롬을 다음과 같이 기록할 수 있습니다.

S_{j}=\sum_{k=1}^{\nu}Y_{k}X_{k}^{j}

$(\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}$ ) $(\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}$ = $(\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}$ $(\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}$ ∗ k = $(\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}$ (α k) j = X k j {\displaystyle(\alpha ^{j})이기 때문에 신드롬 값의 이러한 정의는 이전과 동일합니다. $^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}}$ .

신드롬은 2개의 ν 미지수에서 $n$ - k ≥ 2 ν 방정식 체계를 제공하지만, 그 방정식 체계는 X에서 비선형적이고 명확한 해결책을 가지고 있지 않습니다. 그러나_k X가 알려진 경우(아래 참조), 신드롬 방정식은_k Y 오류 값에 대해 쉽게 풀 수 있는 선형 방정식 체계를 제공합니다.

{\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &\ddots &\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots\\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}}

결과적으로, 문제는_k X를 찾는 것인데, 가장 왼쪽 행렬이 알려져 있고, 방정식의 양변에 그 역행렬을 곱하여 Y를_k 산출할 수 있기 때문입니다.

오류의 위치가 이미 알려진 이 알고리즘의 변형(삭제 코드로 사용되는 경우)에서는 이것이 끝입니다. 오류 위치(X_k)는 이미 다른 방법으로 알려져 있습니다(예를 들어 FM 전송에서 비트스트림이 불분명하거나 간섭으로 극복된 구간은 주파수 분석으로부터 확률적으로 결정 가능합니다). 이 시나리오에서는 $n-k$ - k $n-k$ {\ $displaystyle n-k}$ 오류를 $n-k$ 수정할 수 있습니다.

나머지 알고리즘은 오류를 찾는 역할을 하며 지금까지 $v$ 된 $v$ v ${\displaystyle$ v $} 대신$ $2v$ 최대 $2v$ $2v$ 까지의 신드롬 값이 필요합니다. 위치를 모른 채 수정할 수 있는 오류 수정 기호를 두 배 더 추가해야 하는 이유입니다.

오차 로케이터 다항식

선형 방정식 체계를 생성하는 선형 순환 관계가 있습니다. 그 방정식들을 풀면 그 오류 위치 X를_k 알 수 있습니다.

오차 로케이터 다항식λ(x)를 다음과 같이 정의합니다.

\Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu}x^{\nu}

λ $($ x)의 0은 $X_{k}^{-1}$ X k $X_{k}^{-1}$ - 1 {\ $displaystyle X_{$ k $X_{k}^{-1}$ 1}}입니다. $x=X_{k}^{-1}$ 은 x = X $x=X_{k}^{-1}$ - 1 $displaystyle$ x = $X_$ {k}^{-1}이면 곱셈된 항 중 하나가 0(1 - X k - 1 ⋅ X k) = 1 - 1 = 0 {\displaystyle (1-X_{k}^{-1}\cdot X_{k}) = 1-1=0}이므로 전체 다항식이 0으로 평가됩니다.

\Lambda (X_{k}^{-1})=0

$1\leq j\leq \nu$ ${\displaystyle$ j $}$ 를 1 $1\leq j\leq \nu$ $1\leq j\leq \nu$ $1\leq j\leq \nu$ ν {\ $displaystyle 1\leq$ j\leq \n인 임의의 정수라고 가정합니다. $u$ 양변에 $Y_{k}X_{k}^{j+\nu }$ X $Y_{k}X_{k}^{j+\nu }$ j $Y_{k}X_{k}^{j+\nu }$ + $Y_{k}X_{k}^{j+\nu }$ $ν$ {\ $displaystyle$ Y_ ${k$ }X_ ${k$ }^{j+\n $u}}$ 이고 $Y_{k}X_{k}^{j+\nu }$ 여전히 0입니다.

{\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0.\\[1ex]&Y_{k}X_{k}^{j+\nu }\left(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu}X_{k}^{-\nu}\right)=0.\\[1ex]&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu}Y_{k}X_{k}^{j+\nu}X_{k}^{-\nu}=0.\\[1ex]&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu}Y_{k}X_{k}^{j}=0.\end{align}}

k = 1부터 ν까지 합하면 여전히 0이 됩니다.

\sum _{k=1}^{\nu }\left(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0

각 항을 각자의 합으로 모읍니다.

\left(\sum_{k=1}^{\n)u}Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0

합산에 영향을 받지 않는 $\Lambda$ λ ${\$ displaystyle $\Lambda$ \Lambda }의 상수 값을 추출합니다.

\left(\sum_{k=1}^{\n)u}Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu}Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0

이러한 요약은 이제 우리가 알고 대체할 수 있는 증후군 값과 동등합니다! 따라서 다음과 같이 감소합니다.

S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu}S_{j}=0

$S_{j+\nu }$ + $S_{j+\nu }$ ν {\displaystyle S_{j+\n 빼기 $u}}$ 양측 수율 $S_{j+\nu }$

S_{j}\Lambda_{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu}

j는 1과 v 사이의 임의의 정수로 선택되었고, 이 동등성은 모든 값에 대해 참임을 기억하세요. 따라서 우리는 단순한 하나가 아니라 v선형 방정식을 가지고 있습니다. 따라서 오차 위치 다항식의 계수 λ에 대해 다음과 같은 선형 방정식 체계를 해결할 수 있습니다.

{\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\vdots \\S_{\nu}&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}

위는 디코더가 ν 오류 수를 알고 있지만 아직 그 수가 결정되지 않았다고 가정합니다. PGZ 디코더는 ν을 직접 결정하는 것이 아니라 연속된 값을 시도하여 검색합니다. 디코더는 먼저 평가판 ν에 대해 가장 큰 값을 가정하고 해당 값에 대한 선형 시스템을 설정합니다. 방정식을 풀 수 있는 경우(즉, 행렬 행렬식이 0이 아닌 경우) 해당 시행 값은 오류 수이다. 선형 시스템을 해결할 수 없는 경우 시행 ν을 1로 줄이고 다음으로 작은 시스템을 검사합니다(Gill n.d., p. 35).

오차 로케이터 다항식의 근 찾기

마지막 단계에서 찾은 계수 λ를 사용하여 오차 위치 다항식을 만듭니다. 오류 위치 다항식의 근은 철저한 검색으로 찾을 수 있습니다. 오차 로케이터 X는_k 그 근들의 역수입니다. 오차 위치 다항식의 계수 순서는 역전될 수 있으며, 이 경우 역전된 다항식의 근은 오차 로케이터 $X_{k}$ $X_{k}$ ${\$ $X_{k}^{-1}$ $X_{k}^{-1}$ k $X_{k}^{-1}$ - $X_{k}^{-1}$ ${\$ 입니다. $X_{k}^{-1}$ 중국 검색은 이 단계의 효율적인 구현입니다.

오차값 계산

일단 에러 로케이터_k X가 알려지면, 에러 값들이 결정될 수 있습니다. 이것은 위에 주어진 오차 방정식 행렬에서_k Y에 대한 직접 해를 사용하거나 포니 알고리즘을 사용하여 수행할 수 있습니다.

오차 위치 계산

X의 $\alpha$ _k 로그 베이스 $\alpha$ $\alpha$ 를 취하여 i를_k 계산합니다. 이는 일반적으로 사전 계산된 룩업 테이블을 사용하여 수행됩니다.

오류 수정

마지막으로 e(x)는 i와_k e에서_{i_k} 생성된 다음 r(x)에서 빼서 오류를 수정하고 원래 전송된 메시지 s(x)를 가져옵니다.

예

RS(7,3) 코드에 대해 $α$ = $3$ 및 $t$ = 4(PDF417 바코드에서 사용됨)의 $GF (929)$ 에 정의된 리드-솔로몬 코드를 고려해 보겠습니다. 생성 다항식은

g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522

메시지 다항식이

p (x)

=

3

x + 2

x

+

1

인 경우, 체계적인 코드워드는 다음과 같이 인코딩됩니다.

s_{r}(x)=p(x)\,x^{t}{\bmod {g}}(x)=547x^{3}+738x^{2}+442x+455

s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474

전송 오류로 인해 이 문제가 대신 수신될 수 있습니다.

r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474

신드롬은 α의 rat power를 평가하여 계산됩니다.

S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732

S_{2}=r(3^{2})=637,\;S_{3}=r(3^{3})=762,\;S_{4}=r(3^{4})=925

{\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}

가우스 제거 사용:

{\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}}

Λ(x) = 329 x² + 821 x + 001, with roots x₁ = 757 = 3⁻³ and x₂ = 562 = 3⁻⁴

계수를 반대로 계산하여 양의 지수를 갖는 근을 생성할 수 있지만 일반적으로 이를 사용하지 않습니다.

R(x) = 001 x² + 821 x + 329, with roots 27 = 3³ and 81 = 3⁴

오류 위치에 해당하는 루트의 로그(오른쪽에서 왼쪽, 위치 0은 코드워드의 마지막 항)를 사용합니다.

오차값을 계산하려면 포니 알고리즘을 적용합니다.

Ω(x) = S(x) Λ(x) mod x⁴ = 546 x + 732

Λ'(x) = 658 x + 821

e₁ = −Ω(x₁)/Λ'(x₁) = 074

e₂ = −Ω(x₂)/Λ'(x₂) = 122

$e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ + e $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ = $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ x $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ + $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ 4 ${\displaystyle e_{1}x^{3}+e_{2$ 수신된 다항식 r(x)로부터 $}x^{4$ } $=$ 74x^{ $3}+122x^{4}}$ 는 원본 코드워드를 재생합니다.

베를레캄프-매시 디코더

Berlekamp–Massey 알고리즘은 오류 로케이터 다항식을 찾기 위한 대체 반복 절차입니다. 각 반복 동안 오류 수가 가정된 λ(x)의 현재 인스턴스를 기반으로 불일치를 계산합니다.

\Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}

그런 다음 다시 계산된 δ이 0이 되도록 λ(x) 및 e를 조정합니다. Berlekamp–Massey 알고리즘은 절차에 대한 자세한 설명을 제공합니다. 다음 예제에서는 C(x)를 사용하여 λ(x)를 나타냅니다.

예

위의 Peterson Gorenstein Zierler 예제와 동일한 데이터 사용:

n	S_n+1	d	C	B	b	m
0	732	732	197 x + 1	1	732	1
1	637	846	173 x + 1	1	732	2
2	762	412	634 x² + 173 x + 1	173 x + 1	412	1
3	925	576	329 x² + 821 x + 1	173 x + 1	412	2

C의 최종 값은 오차 로케이터 다항식인 λ(x)입니다.

유클리드 디코더

오차 로케이터 다항식과 오차값 다항식을 모두 계산하는 또 다른 반복적인 방법은 스기야마의 확장 유클리드 알고리즘의 적응을 기반으로 합니다.

syndrome 및 e 오류에 대해 S(x), λ ω(x) 및 ω(x)를 정의합니다.

{\begin{aligned}S(x)&=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}\\[1ex]\Lambda (x)&=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1\\[1ex]\오메가(x)&=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}\end{aligned}

핵심 방정식은 다음과 같습니다.

\Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)

For t = 6 and e = 3:

{\begin{bmatrix}\Lambda _{3}S_{6}&x^{8}\\\Lambda _{2}S_{6}+\Lambda _{3}S_{5}&x^{7}\\\Lambda _{1}S_{6}+\Lambda _{2}S_{5}+\Lambda _{3}S_{4}&x^{6}\\S_{6}+\Lambda _{1}S_{5}+\Lambda _{2}S_{4}+\Lambda _{3}S_{3}&x^{5}\\S_{5}+\Lambda _{1}S_{4}+\Lambda _{2}S_{3}+\Lambda _{3}S_{2}&x^{4}\\S_{4}+\Lambda _{1}S_{3}+\Lambda _{2}S_{2}+\Lambda _{3}S_{1}&x^{3}\\S_{3}+\Lambda _{1}S_{2}+\Lambda _{2}S_{1}&x^{2}\\S_{2}+\Lambda _{1}S_{1}&x\\S_{1}\end{bmatrix}}={\begin{bmatrix}Q_{2}x^{8}\\Q_{1}x^{7}\\Q_{0}x^{6}\\0\\0\\0\\\Omega _{2}x^{2}\\\Omega _{1}x\\\Omega _{0}\end{bmatrix}

중간 항은 λ와 증후군의 관계로 인해 0입니다.

확장 유클리드 알고리즘은 다음과 같은 형태의 일련의 다항식을 찾을 수 있습니다.

A_i(x) S(x) + B_i(x) x^t = R_i(x)

i가 증가함에 따라 R의 정도가 감소합니다. 일단_i R(x) < t/2 정도가 되면,

A(x) = λ(x)

B(x) = -Q(x)

R(x) = ω(x).

B(x)와 Q(x)는 저장할 필요가 없으므로 알고리즘은 다음과 같습니다.

R : = x R : = S(x) A : = 0 A : = 1 i : = 0, R ≥ t/2 i : = i + 1 Q : = R / R : = R - Q RA : = A - Q A

λ(x)의 저차항을 1로 설정하려면 λ(x)와 ω(x)를 A(0)로 나눕니다.

λ(x) = A / A(0)

ω =(x) = R / A(0)

A_i(0)는 A의_i 상수(저차수) 항입니다.

예

위의 Peterson-Gorenstein-Zierler 예제와 동일한 데이터 사용:

i	R_i	가_i
−1	001 x⁴ + 000 x³ + 000 x² + 000 x + 000	000
0	925 x³ + 762 x² + 637 x + 732	001
1	683 x² + 676 x + 024	697 x + 396
2	673 x + 596	608 x² + 704 x + 544

Λ(x) = A₂ / 544 = 329 x² + 821 x + 001

Ω(x) = R₂ / 544 = 546 x + 732

이산 푸리에 변환을 사용한 디코더

이산 푸리에 변환을 디코딩에 사용할 수 있습니다.^[15] 신드롬 이름과 충돌하지 않도록 c(x) = s(x) 인코딩된 코드워드를 지정합니다. r(x)와 e(x)는 위와 같습니다. C(x), E(x) 및 R(x)를 c(x), e(x) 및 r(x)의 이산 푸리에 변환으로 정의합니다. r(x) = c(x) + e(x)이고, 이산 푸리에 변환은 선형 연산자이므로 R(x) = C(x) + E(x)입니다.

이산 푸리에 변환을 사용하여 r(x)를 R(x)로 변환합니다. 이산 푸리에 변환에 대한 계산은 신드롬에 대한 계산과 동일하므로 R(x) 및 E(x)의 t 계수는 신드롬과 동일합니다.

R_{j}= E_{j}=S_{j}=r(\alpha ^{j})\qquad {\text{for }}1\leq j\leq t

$R_{1}$ ${\$ 부터 $R_{1}$ $R_{t}$ ${\$ 까지 신드롬(동일)으로 $R_{t}$ 사용하고 위 디코더의 메서드를 사용하여 오류 로케이터 다항식을 생성합니다.

v = 오류 수를 지정합니다. 알려진 계수 $E_{1}$ ${\$ $E_{t}$ ${\$ 오차 로케이터 다항식 및 이러한 공식을 사용하여 E(x)를 생성합니다.

{\begin{aligned}E_{0}&=-{\frac {1}{\Lambda _{v}}}(E_{v}+\Lambda _{1}E_{v-1}+\cdots +\Lambda _{v-1}E_{1})\\E_{j}&=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{v}E_{j-v})&{\text{for }}t<j<n\end{aligned}}

그런 다음 C(x) = R(x) - E(x)를 계산하고 C(x)의 역변환(polynom 보간)을 수행하여 C(x)를 생성합니다.

오류 수정 경계를 벗어나는 디코딩

싱글턴 바운드는 $크기$ (n, $k$ )의 선형 블록 코드의 최소 거리 d가 n - k + $1$ 만큼 상한임을 나타냅니다. 거리 d는 일반적으로 $오류$ 수정 기능을 ⌊( $d-1$ ) / 2 ⌋로 제한하는 것으로 이해되었습니다. 리드-솔로몬 코드는 이 경계를 동일하게 달성하므로 $최대$ ⌊ $(n-k$ )/2 ⌋ 오류를 수정할 수 있습니다. 그러나 이 오류 수정 경계는 정확하지 않습니다.

1999년, MIT의 마두 수단과 벤카테산 구루스와미는 "리드-솔로몬과 대수기하학 코드의 개선된 디코딩"을 발표하여, 코드의 최소 거리의 절반 이상의 오차를 수정할 수 있는 알고리즘을 도입했습니다.^[16] 리드-솔로몬 코드에 적용되며, 더 일반적으로는 대수 기하학 코드에 적용됩니다. 이 알고리즘은 코드워드 목록(리스트 디코딩 알고리즘)을 생성하고 $GF(2^{m})$ $GF(2^{m})$ 및 그 $GF(2^{m})$ 확장에 대한 다항식의 보간 및 인수분해를 기반으로 합니다.

소프트 디코드

위에서 설명한 대수적 디코딩 방법은 어려운 결정 방법이며, 이는 모든 심볼에 대해 그 값에 대해 어려운 결정이 내려짐을 의미합니다. 예를 들어, 디코더는 각 심볼에 심볼의 정확도에 대한 채널 복조기의 신뢰도에 대응하는 추가 값을 연관시킬 수 있습니다. 이론적 한계에 가까운 오류 수정 성능을 달성하기 위해 반복적인 연판정 믿음 전파 디코딩 방법을 사용하는 LDPC 및 터보 코드의 출현은 연판정 디코딩을 기존 대수 코드에 적용하는 데 관심을 불러일으켰다. 2003년 Ralf Koetter와 Alexander Vardy는 수단과 Guruswami의 연구를 기반으로 리드-솔로몬 코드에 대한 다항식 시간 연판정 대수 목록 디코딩 알고리즘을 제시했습니다.^[17] 2016년에는 스티븐 J. 프랭크와 조셉 H. 테일러는 새로운 연판정 디코더를 출판했습니다.^[18]

MATLAB 예제

인코더

여기서는 인코더에 대한 간단한 MATLAB 구현을 제시합니다.

함수 인코딩 = rsEncoder(msg, m, prim_poly, n, k)     % Reed-Solomon 알고리즘을 사용한 RSENCODER 인코딩 메시지     % m은 심볼당 비트 수입니다.     % prim_poly: 원시 다항식 p(x). 즉 DM의 경우 301입니다.     % k는 메시지의 크기입니다.     % n은 total size (k+ redundant)     % 예제: msg = uint8('테스트')     % enc_msg = rsEncoder(msg, 8, 301, 12, numel(msg));      % 알파를 잡으세요.     알파 = 여자친구(2, m, prim_poly의);      % 리드-솔로몬 생성 다항식 g(x) 가져오기     g_x = genpoly(k, n, 알파);      % 정보에 X^(n-k)를 곱하거나 끝에 0이 있는 패드만 있으면 됩니다.     % 중복 정보를 추가할 공간을 확보합니다.     msg_ = 여자친구([msg 영점(1, n - k)], m, prim_poly의);      % 다음으로 확장 메시지의 나머지 분할 내용을 가져옵니다.     % 리드-솔로몬 생성 다항식 g(x)     [~, 잔금의] = 디콘브의(msg_, g_x);      % 이제 중복 정보와 함께 메시지를 반환합니다.     암호화된 = msg_ - 잔금의;  끝.  % 리드-솔로몬 생성 다항식 g(x)를 구하여라. 그런데 이것은 다음과 같습니다. % matlab의 rsgenpoly 함수와 동일합니다. 함수 g = genpoly(k, n, alpha)     g = 1;     % 갈루아 분야의 곱셈은 단지 컨볼루션일 뿐입니다.     위해서 k = 모드(1 : n - k, n)         g = 회중의(g, [1 알파 .^ (k)]);     끝. 끝.

디코더

이제 디코딩 부분:

함수 [decoded, error_pos, error_mag, g, S] = rsDecoder (부호화, m, prim_poly, n, k)     % RSDECODER 리드-솔로몬 인코딩 메시지 디코딩     %   예제:     % [dec, ~, ~, ~] = rsDecoder(enc_msg, 8, 301, 12, numel(msg))     max_ = 바닥.((n - k) / 2);     orig_vals = 암호화된.x;     % 오차 벡터 초기화     과오 = 영점(1, n);     g = [];     S = [];      % 알파를 잡으세요.     알파 = 여자친구(2, m, prim_poly의);      % 신드롬 찾기(생성기로 메시지를 나누는지 확인)     % 다항식 결과는 0)     신드 = 다각형의(암호화된, 알파 .^ (1:n - k));     신드롬 = 다듬다(신드);      % 모든 신드롬이 0인 경우(완전 분할) 오류가 없습니다.     한다면 비었습니다.(신드롬.x)         해독된 = orig_vals(1:k);         error_pos = [];         error_mag = [];         g = [];         S = 신드;         돌아가다;     끝.      % 유클리드 알고리즘 준비(오류 찾기에 사용)     % 다항식)     r0 = [1, 영점(1, 2 * max_)]; r0 = 여자친구(r0, m, prim_poly의); r0 = 다듬다(r0);     size_r0 = 길이(r0);     r1 = 신드롬;     f0 = 여자친구([영점(1, size_r0 - 1) 1], m, prim_poly의);     f1 = 여자친구(영점(1, size_r0), m, prim_poly의);     g0 = f1; g1 = f0;      % 의 다항식 r0(x)와 신드롬(x)에 대해 유클리드 알고리즘을 수행합니다.     % 오차 찾기 다항식을 찾기 위해 순서를 정합니다.     하는 동안에 진실의         % 긴 나눗셈을 합니다.         [몫의, 잔금의] = 디콘브의(r0, r1);         % 0을 몇 개 더합니다.         몫의 = 패드를 대다(몫의, 길이(g1));          % 몫*g1 및 패드 찾기         c = 회중의(몫의, g1);         c = 다듬다(c);         c = 패드를 대다(c, 길이(g0));          % g0-quotient*g1 가스 업데이트         g = g0 - c;          % 나머지(x)의 정도가 max_errors보다 작은지 확인         한다면 모든.(잔금의(1:끝. - max_) == 0)             브레이크.;         끝.          % r0, r1, g0, g1을 업데이트하고 선행 0을 제거합니다.         r0 = 다듬다(r1); r1 = 다듬다(잔금의);         g0 = g1; g1 = g;     끝.      % 선행 0 제거     g = 다듬다(g);      % 이 갈루아 필드에서 오차 다항식의 0을 구합니다.     evalPoly = 다각형의(g, 알파 .^ (n - 1 : - 1 : 0));     error_pos = 여자친구(찾아내다(evalPoly == 0), m);      % 오류 위치가 발견되지 않으면 받은 작업을 반환합니다. 왜냐하면     % 기본적으로 우리가 할 수 있는 것은 아무것도 없고 우리는 받은 메시지를 반환합니다.     한다면 비었습니다.(error_pos)         해독된 = orig_vals(1:k);         error_mag = [];         돌아가다;     끝.      % 오차 다항식을 풀기 위한 선형계를 준비하고 오차를 구합니다.     % 규모의     size_error = 길이(error_pos);     신드롬_발스 = 신드롬.x;     b(:, 1) = 신드롬_발스(1:size_error);     위해서 idx = 1 : size_error         e = 알파 .^ (idx * (n - error_pos.x));         과오를 범하다 = e.x;         음.정말(idx, :) = 과오를 범하다;     끝.      % 선형계를 풀기     error_mag = (여자친구(음.정말, m, prim_poly의) \ 여자친구(b, m, prim_poly의))';     % 오차 벡터에 오차 크기를 적용합니다.     과오(error_pos.x) = error_mag.x;     % 이 벡터를 갈루아 필드로 가져갑니다.     에러_gf = 여자친구(과오, m, prim_poly의);      % 이제 오류를 수정하려면 인코딩된 코드로 추가하기만 하면 됩니다.     decoded_gf = 암호화된(1:k) + 에러_gf(1:k);     해독된 = decoded_gf.x;  끝.  % Galois 배열에서 선행 0 제거 function gt = 트림(g)     gx = g.x;     gt = 여자친구(gx(찾아내다(gx, 1) : 끝.), g.m, g.prim_poly의); 끝.  % 선행 0을 추가합니다. 함수 xpad = 패드(x, k)     렌 = 길이(x);     한다면 렌 < k         xpad의 = [영점(1, k - 렌) x];     끝. 끝.

리드 솔로몬 원본 뷰 디코더

이 섹션에서 설명하는 디코더는 코드워드의 리드 솔로몬 원래 뷰를 다항식 값의 시퀀스로 사용하며, 여기서 다항식은 인코딩할 메시지를 기반으로 합니다. 동일한 고정 값 세트가 인코더 및 디코더에 의해 사용되고 디코더는 수신된 메시지로부터 인코딩 다항식(및 선택적으로 에러 로케이팅 다항식)을 복구합니다.

이론 디코더

Reed & Solomon(1960)은 가장 일반적인 메시지 다항식을 찾아 오류를 수정하는 이론적 디코더를 설명했습니다. 디코더는 $a_{1}$ ${\$ 부터 $a_{1}$ ${\$ 까지의 값 집합과 $a_{n}$ 코드워드의 시퀀스를 생성하기 위해 사용된 인코딩 방법만 알고 있습니다. 원본 메시지, 다항식 및 오류를 알 수 없습니다. 디코딩 절차는 수신된 코드워드의 오류를 합리적으로 제거하기 위해 충분한 수의 일치 다항식이 생성될 때까지 한 번에 k개의 다양한 코드워드 값의 하위 집합에 대한 라그랑주 보간과 같은 방법을 사용하여 잠재 다항식을 반복적으로 생성할 수 있습니다. 다항식이 결정되면 해당 코드워드 값을 다시 계산하여 코드워드의 오류를 수정할 수 있습니다. 안타깝게도 가장 단순한 경우를 제외한 모든 경우에 부분집합이 너무 많아서 알고리즘이 비현실적입니다. 부분 집합의 수는 이항 계수, ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$ ( ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$ k ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$ ) = n ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$ ! ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$ ( $n$ - k $)$ ! k ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$ ! {\textstyle {\binom {n} {k}} = {n! \over (n-k) ! k ! $}}$ 그리고 부분 집합의 수는 작은 코드에서도 실행할 수 없습니다 $.$ 3개의 오류를 수정할 수 있는 $(255,249)$ ( $(255,249)$ $(255,249)$ $(255, 249)$ 코드의 $(255,249)$ 경우 순진한 이론 디코더는 3,590억 개의 부분 집합을 검사합니다.

베를레캄프 웰치 디코더

1986년, '베를레캄프(Berlekamp)'라는 이름의 디코더가Welch 알고리즘은 오류에 해당하는 입력 값에 대해 0을 생성하는 오류 "로케이터" 다항식뿐만 아니라 원래 메시지 다항식을 복구할 수 있는 디코더로 개발되었으며, 시간 복잡도 $O(n^{3})$ $O(n^{3})$ $O(n^{3})$ 이며 $O(n^{3})$ $n$ 서 n{\ $displaystyle$ n}은 $n$ 메시지의 값 수이다. 그런 다음 복구된 다항식을 사용하여 원래 메시지를 복구(필요에 따라 다시 계산)합니다.

예

RS(7,3), GF(929) 및 평가점 집합 a = i - 1을 이용한

a = {0, 1, 2, 3, 4, 5, 6}