I am trying to understand how Reed Solomon encoding works. Specifically, I am trying to re-generate the example shown in http://www.mathworks.com/help/comm/ref/integerinputrsencoder.html and check if my understanding of Reed Solomon encoding matches with the generated outputs of Matlab.
Assume,
M = 3. N = 7. K = 5. We operate in GF(8)
input message, U = [2 3 5 2 0]
corresponding output codeword, C = [2 3 5 2 0 1 4].
Matlab used default primitives and generator polymonials to generate this output codeword.
Matlab’s default primitive polynomial for GF(8) is D^3 + D + 1.
Matlab’s default generator polynomial for (N = 7, K = 5) reed Solomon code is: G = [1 6 3].
The associated code to generate C from U is following:
% Code starts
clear all ; close all ; clc ;
M = 3 ;
N = 7 ;
K = 5 ;
U = gf([2 3 5 2 0],M);
G = rsgenpoly(7,5) ;
C = rsenc(U,N,K,G)
% Code finishes
I want to know how Matlab is encoding U using Reed-Solomon encoding. I want to generate an output codeword C’ from U and G myself and check if it matches with C.
Based on my understanding of Reed Solomon coding, the polynomials associated with U and G are following:
Input polynomial, u(x) = 2 * x^4 + 3 * x^3 + 5 * x^2 + 2 * x
Generator polynomial, g(x) = x^2 + 6 * x + 3
If I multiply these two polynomials to get output codeword polynomial c’(x), I get the following:
c’(x) = u(x) * g(x)
= (2 * x^4 + 3 * x^3 + 5 * x^2 + 2 * x ) * (x^2 + 6 * x + 3)
= 2 * x^6 + 15 * x^5 + 29 * x^4 + 41 * x^3 + 27 * x^2 + 6 * x … (Line a)
= 2 * x^6 + 7 * x^5 + 5 * x^4 + x^3 + 3 * x^2 + 6 * x . … (Line b)
Here, Line a and b are equivalent under GF(8).
From line b, C’ = [2 7 5 1 3 6 0] But the entries of C’ do not match that of C, which is the output codeword generated by Matlab.
I want to know what mistake I am making. I want to know how I can get the actual value of C from U and G.
Any suggestion will be very appreciated.
Thanks,
Nazmul
The encoder that MATLAB is using creates a systematic cyclic code as you can see by looking at the codeword created: the first 5 symbols are the information symbols.
Your information polynomial is $u(x) = u_4x^4+u_3x^3+u_2x^2+u_1x+u_0$. The codeword polynomial is obtained as follows.
Multiply $u(x)$ by $x^2 = x^{N-K}$ to get $x^2u(x) = u_4x^6+u_3x^5+u_2x^4+u_1x^3+u_0x^2$.
Divide $x^2u(x)$ by $g(x) = x^2 + g_1x + g_0$ to get a quotient $q(x)$ of degree $2$ and a remainder $r(x) = r_1x+r_0$ of degree $1$ or less. The quotient is not needed and can be discarded. In fact, most encoders don't explicitly compute the quotient.
The codeword $c(x)$ is $$x^2u(x) - r(x) = x^2u(x) + r(x) = (u_4x^6+u_3x^5+u_2x^4+u_1x^3+u_0x^2) + r_1x + r_0$$ because addition and subtraction are the same operation (XOR) in GF$(8)$.
The key idea is that the symbols $r_0$ and $r_1$ are added to $x^2u(x)$ in exactly those positions where $x^2u(x)$ has zero coefficients and so they appear "in the clear" as parity checks that follow the $5$ information symbols.
So why does all this work? We have, by construction, that $x^2u(x) = q(x)g(x) + r(x)$ and so it must be that $x^2u(x)-r(x) = x^2u(x)+r(x)$ is a multiple $q(x)g(x)$ of the generator polynomial, and hence is a codeword in the cyclic code generated by $g(x)$.
Your method of simply multiplying $u(x)$ by $g(x)$ also creates a codeword in the cyclic code generated by $g(x)$ but it does not give a systematic codeword in which we can identify the information symbols and parity check symbols via their positions in the codeword.