RS Encoder/ RS Decoder using Matlab

RS Encoder

function U = RSEncoder(M)
 
K = length(M);
m = M.m;
N = 2^m-1;
DegPoly = N - K;
P = flip(rsgenpoly(N, K));
 
LFSR = gf(zeros(1, N-K), m);
 
U = gf(zeros(1, N), m);
U(N-K+1:N) = M;
 
for i = 1 : K
    feedback = LFSR(DegPoly) + M(K-i+1);
    for j = DegPoly : -1 : 2
        LFSR(j) = LFSR(j-1) + feedback*P(j);
    end
    LFSR(1) = feedback * P(1);
end
 
U(1:(N-K)) = LFSR;

---

RS Decoder

function Mhat = RSDecoder(R)
 
a = gf(2, 3);
N = length(R);
K = N - R.m;
m = R.m;
 
S1 = GetSyndrom(R, a);
S2 = GetSyndrom(R, a^2);
S3 = GetSyndrom(R, a^3);
S4 = GetSyndrom(R, a^4);
 
Sm = [S1 S2; S2 S3];
Sv = [S3; S4];
Sigma = Sm\Sv;
 
SigCoeff = [1 flip(Sigma')];
 
Beta = [];
for i = 1 : N
    sig_a = GetSyndrom(SigCoeff, a^(i-1));
    if sig_a == 0
        Beta = [Beta 1/a^(i-1)];
    end
end
 
Em = [Beta(1) Beta(2); Beta(1)^2 Beta(2)^2];
Ev = [S1 S2]';
 
e = Em\Ev;
 
A = a.^[0 : N-1];
NumErr = length(e);
E = gf(zeros(size(R)), m);
 
for i = 1 : NumErr
    E(find(A ==Beta(i))) = e(i);
end
 
Uhat = R + E;
Mhat = Uhat(N-K+2 : N);
 
end

---

분석

인코딩 :
​
 RS방식도 Cyclic방식이기 때문 에 레지스터를 사용하고 LFSR의 마지막 신호가 parity가 된다. 우선 신호가 들어오게 되면 CyclicEncoder와 같이 인코딩이 된다. 여기서 다른 점은 생성다항식이다. RS방 식은 갈루아영역에서 계산되기 때문이다. 생성다항식이 (7, 3) 인코딩의 경우 g(x) = (x-a)(x-a^2)(x-a^3)(x-a^4)이고 U(x)가 g(x) 나누어 떨어지므로 g(x)의 근을 U(x)에 대입하면 값 0이 도출된다. 실제로 코드워드에 생성다항식의 근을 대입하 면 값이 0이 되는 것을 확인하였다.

디코딩 :

우선 우리가 인코딩한 코드에 잡음이 섞이게 되면 오류가 발생할 것이다. 오류가 섞이게 되면 신드롬 검사 를 거쳤을 때 그 값이 0이 아닐 것이고 우리는 이것을 이용하여 에러가 발생한 위치와 그때의 에러 값을 찾아 야한다.

​

우선, 수신된 다항식에 a^i를 대입하여 신드롬을 계산한다. 이때 모두 0이 나온다면 에러를 없을 것이다. 하지만 에러가 아닌 어떠한 a^n 값이 검출되면 에러가 발생하여 신드롬이 0이 아닌 것이다.

​

에러 발생위치를 찾기 위해 Error Locator polynomial을 이용한다. 이 다항식의 근은 1/b 가 되고, 에러 위치 다항식의 근을 구해서 뒤집으면 b, 즉 에러 발생 위치를 확인할 수 있게 된다. 시그마와 베타의 관계식으로 2개의 연립방정식을 세울 수 있고 이 방정식을 계산하여 최종적이 Error를 확인한 다. 에러가 발생한 수신신호에 에러를 더해주어 오류를 정정하여 원 신호를 복구해주는 과정이 RS 디코딩이다. 실제로, 실습을 통해 RS 인코딩/디코딩을 확인해보았다.