#include <rs.h>

Collaboration diagram for leansdr::rs_engine:

Public Member Functions
	rs_engine ()

bool	syndromes (const u8 poly, u8 synd)

u8	eval_poly_rev (const u8 *poly, int n, u8 x)

u8	eval_poly (const u8 *poly, int deg, u8 x)

void	encode (u8 msg[204])

bool	correct (u8 synd[16], u8 pout[188], u8 pin[204]=NULL, int *bits_corrected=NULL)

Public Attributes
gf2x_p< unsigned char, unsigned short, 0x11d, 8, 2 >	gf

u8	G [17]

Detailed Description

Definition at line 97 of file rs.h.

Constructor & Destructor Documentation

◆ rs_engine()

leansdr::rs_engine::rs_engine ( )

inline

Definition at line 105 of file rs.h.

References leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::exp(), i, leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::mul(), and leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::sub().

     {
         // EN 300 421, section 4.4.2, Code Generator Polynomial
         // G(X) = (X-alpha^0)*...*(X-alpha^15)
         for (int i = 0; i <= 16; ++i)
             G[i] = (i == 16) ? 1 : 0; // Init G=1
         for (int d = 0; d < 16; ++d)
         {
             // Multiply by (X-alpha^d)
             // G := X*G - alpha^d*G
             for (int i = 0; i <= 16; ++i)
                 G[i] = gf.sub((i == 16) ? 0 : G[i + 1], gf.mul(gf.exp(d), G[i]));
         }
 #if DEBUG_RS
         fprintf(stderr, "RS generator:");
         for (int i = 0; i <= 16; ++i)
             fprintf(stderr, " %02x", G[i]);
         fprintf(stderr, "\n");
 #endif
     }

Here is the call graph for this function:

Member Function Documentation

◆ correct()

bool leansdr::rs_engine::correct	(	u8	synd[16],
		u8	pout[188],
		u8	pin[204] = `NULL`,
		int *	bits_corrected = `NULL`
	)

inline

Definition at line 201 of file rs.h.

References leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::div(), leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::exp(), leansdr::hamming_weight(), i, leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::inv(), and leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::mul().

Referenced by leansdr::rs_decoder< leansdr::u8, 0 >::run().

     {
         // Berlekamp - Massey
         // http://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm#Code_sample
         u8 C[16] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; // Max degree is L
         u8 B[16] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
         int L = 0;
         int m = 1;
         u8 b = 1;
         for (int n = 0; n < 16; ++n)
         {
             u8 d = synd[n];
             for (int i = 1; i <= L; ++i)
                 d ^= gf.mul(C[i], synd[n - i]);
             if (!d)
             {
                 ++m;
             }
             else if (2 * L <= n)
             {
                 u8 T[16];
                 memcpy(T, C, sizeof(T));
                 for (int i = 0; i < 16 - m; ++i)
                     C[m + i] ^= gf.mul(d, gf.mul(gf.inv(b), B[i]));
                 L = n + 1 - L;
                 memcpy(B, T, sizeof(B));
                 b = d;
                 m = 1;
             }
             else
             {
                 for (int i = 0; i < 16 - m; ++i)
                     C[m + i] ^= gf.mul(d, gf.mul(gf.inv(b), B[i]));
                 ++m;
             }
         }
         // L is the number of errors
         // C of degree L is now the error locator polynomial (Lambda)
 #if DEBUG_RS
         fprintf(stderr, "[L=%d  C=", L);
         for (int i = 0; i < 16; ++i)
             fprintf(stderr, " %d", C[i]);
         fprintf(stderr, "]\n");
         fprintf(stderr, "[S=");
         for (int i = 0; i < 16; ++i)
             fprintf(stderr, " %d", synd[i]);
         fprintf(stderr, "]\n");
 #endif
 
         // Forney
         // http://en.wikipedia.org/wiki/Forney_algorithm  (2t=16)
 
         // Compute Omega
         u8 omega[16];
         memset(omega, 0, sizeof(omega));
         // TODO loops
         for (int i = 0; i < 16; ++i)
             for (int j = 0; j < 16; ++j)
                 if (i + j < 16)
                     omega[i + j] ^= gf.mul(synd[i], C[j]);
 #if DEBUG_RS
         fprintf(stderr, "omega=");
         for (int i = 0; i < 16; ++i)
             fprintf(stderr, " %d", omega[i]);
         fprintf(stderr, "\n");
 #endif
 
         // Compute Lambda'
         u8 Cprime[15];
         for (int i = 0; i < 15; ++i)
             Cprime[i] = (i & 1) ? 0 : C[i + 1];
 #if DEBUG_RS
         fprintf(stderr, "Cprime=");
         for (int i = 0; i < 15; ++i)
             fprintf(stderr, " %d", Cprime[i]);
         fprintf(stderr, "\n");
 #endif
 
         // Find zeroes of C by exhaustive search?
         // TODO Chien method
         int roots_found = 0;
         for (int i = 0; i < 255; ++i)
         {
             u8 r = gf.exp(i); // Candidate root alpha^0..alpha^254
             u8 v = eval_poly(C, L, r);
             if (!v)
             {
                 // r is a root X_k^-1 of the error locator polynomial.
                 u8 xk = gf.inv(r);
                 int loc = (255 - i) % 255; // == log(xk)
 #if DEBUG_RS
                 fprintf(stderr, "found root=%d, inv=%d, loc=%d\n", r, xk, loc);
 #endif
                 if (loc < 204)
                 {
                     // Evaluate e_k
                     u8 num = gf.mul(xk, eval_poly(omega, L, r));
                     u8 den = eval_poly(Cprime, 14, r);
                     u8 e = gf.div(num, den);
                     // Subtract e from coefficient of degree loc.
                     // Note: Coeffients listed by decreasing degree in pin[] and pout[].
                     if (bits_corrected)
                         *bits_corrected += hamming_weight(e);
                     if (loc >= 16)
                         pout[203 - loc] ^= e;
                     if (pin)
                         pin[203 - loc] ^= e;
                 }
                 if (++roots_found == L)
                     break;
             }
         }
         if (pin)
             return syndromes(pin, synd);
         else
             return false;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ encode()

void leansdr::rs_engine::encode ( u8 msg[204] )

inline

Definition at line 164 of file rs.h.

References leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::div(), i, leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::mul(), and leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::sub().

     {
         // TBD Avoid copying
         u8 p[204];
         memcpy(p, msg, 188);
         memset(p + 188, 0, 16);
         // p = msg*X^16
 #if DEBUG_RS
         fprintf(stderr, "uncoded:");
         for (int i = 0; i < 204; ++i)
             fprintf(stderr, " %d", p[i]);
         fprintf(stderr, "\n");
 #endif
         // Compute remainder modulo G
         for (int d = 0; d < 188; ++d)
         {
             // Clear monomial of degree d
             if (!p[d])
                 continue;
             u8 k = gf.div(p[d], G[0]);
             // p(X) := p(X) - k*G(X)*X^(188-d)
             for (int i = 0; i <= 16; ++i)
                 p[d + i] = gf.sub(p[d + i], gf.mul(k, G[i]));
         }
 #if DEBUG_RS
         fprintf(stderr, "coded:");
         for (int i = 0; i < 204; ++i)
             fprintf(stderr, " %d", p[i]);
         fprintf(stderr, "\n");
 #endif
         memcpy(msg + 188, p + 188, 16);
     }

Here is the call graph for this function:

◆ eval_poly()

u8 leansdr::rs_engine::eval_poly	(	const u8 *	poly,
		int	deg,
		u8	x
	)

inline

Definition at line 153 of file rs.h.

References leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::add(), and leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::mul().

     {
         // poly[0]*x^0 + .. + poly[deg]*x^deg with Hörner method.
         u8 acc = 0;
         for (; deg >= 0; --deg)
             acc = gf.add(gf.mul(acc, x), poly[deg]);
         return acc;
     }

Here is the call graph for this function:

◆ eval_poly_rev()

u8 leansdr::rs_engine::eval_poly_rev	(	const u8 *	poly,
		int	n,
		u8	x
	)

inline

Definition at line 143 of file rs.h.

References leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::add(), i, and leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::mul().

     {
         // poly[0]*x^(n-1) + .. + poly[n-1]*x^0 with Hörner method.
         u8 acc = 0;
         for (int i = 0; i < n; ++i)
             acc = gf.add(gf.mul(acc, x), poly[i]);
         return acc;
     }

Here is the call graph for this function:

◆ syndromes()

bool leansdr::rs_engine::syndromes	(	const u8 *	poly,
		u8 *	synd
	)

inline

Definition at line 132 of file rs.h.

References leansdr::gf2x_p< Te, Tp, P, N, ALPHA >::exp(), and i.

Referenced by leansdr::rs_decoder< leansdr::u8, 0 >::run().

     {
         bool corrupted = false;
         for (int i = 0; i < 16; ++i)
         {
             synd[i] = eval_poly_rev(poly, 204, gf.exp(i));
             if (synd[i])
                 corrupted = true;
         }
         return corrupted;
     }