R-S 코드 (Reed-Solomon Code)

[무선통신]

R-S 코드 (Reed-Solomon Code)

1. 개요

o 선형 블럭코드 > 순환코드 > BCH 코드 (Hamming 코드) > R-S 코드 관계임.
  BCH 코드의 非이진 형태가 R-S 코드임
  단일에러를 정정하는 해밍코드는 BCH 코드의 특별한 경우임 

o BCH 코드가 랜덤에러를 정정하는데 반해,
  R-S 코드는 연집에러 (Burst Error)를 효율적으로 정정할 수 있음

o 1960년 Irving S. Reed와 G. Solomon에 의해 알려짐
  "Polynomial Codes over Certain Finite Field"

2. R-S 코드

o Galois Field, GF(q)

  - Primitive element (a)가 존재하고, 덧셈/곱셈에 대하여 닫혀진 系
  - q 개의 원소 : 0, 1, a, a², ..... , a^q-2, (a^q-1 = 1, a^q = 0)
  - a는 생성 다항식 G(x) = 0 의 근

  예) GF(2) = {0, 1}, 우리가 알고 있는 이진수 系
      GF(4) = {0, 1, a, a²}, 1 + a + a² = 0

o (n, k) non-binary coding 구성

  - Galois Field, GF(q) 또는 GF(2^m)
  - Code (Block) 길이 : n = q - 1 = 2^m - 1
  - 메시지 길이       : k = q - 1 - 2t = n - 2t
  - t개의 심볼에러 정정 : 2t = n - k
  - 최소 해밍 거리    : d_min = 2t + 1

o 생성 다항식

  - G(x) = (x + a)(x + a²)(x + a³) .... (x + a^2t)

    a는 GF(q)의 Primitive Element

o Encoding

  k개 심볼블럭 -> [Shift Register] ->  생성다항식   -> D(x) x^n-k + R(x)
  D(x) 입력           D(x) x^n-k       G(x)로 나누기     = G(x) Q(x)    

  * n개의 심볼블럭 C(x) = D(x) x^n-k + R(x) = G(x) Q(x)
                   나머지 R(x)는 Redundancy 다항식

o Decoding

  n개의 심볼블럭 -> 2t개 Syndrome 생성 -> 에러위치와   
  r(x) 수신         S_j = r(a^j) + e(a^j)    에러크기 찾기

  * Berle Kamp Algorithm (에러 위치), Forny Algorithm (에러크기)

3. 특징

o Overhead (Redundant Symbol)의 최소화

o 다른 Non-binary Code에 비하여 Decoding 방식이 간편함
  Decoding 방식은 BCH 코드와 같음

o (n, k) 블럭화로 다양한 Code Word 길이의 선택이 가능하다.

o Burst Error (연집에러) 정정 능력이 탁월하다.

o Concatenated Coding 기능

4. 응용 분야

o 디지털 방송

o 디지털 위성방송 시스템 - 예) (204, 188) R-S Code

o 컴퓨터 메모리 또는 디지털 오디오 디스크

o 우주 공간 이용 통신 시스템

 이상