leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN > Struct Template Reference

#include <bch.h>

Inheritance diagram for leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >:

Collaboration diagram for leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >:

Public Member Functions
	bch_engine (const bitvect< T, NP > *polys, int _npolys)
void	encode (const uint8_t *msg, size_t msgbytes, uint8_t *out)
int	decode (uint8_t *cw, size_t cwbytes)

Private Member Functions
TGF	eval_poly (const bitvect< T, DP > &poly, bool is_trunc, int rootexp)
TGF	eval_poly (const TGF *poly, int deg, int rootexp)

Private Attributes
bitvect< T, DP > *	truncpolys
int	npolys
int *	syndpolys
bitvect< T, N >	g
gf2n< TGF, DP, 2, GFTRUNCGEN >	GF

Detailed Description

template<typename T, int N, int NP, int DP, typename TGF, int GFTRUNCGEN>
struct leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >

Definition at line 42 of file bch.h.

Constructor & Destructor Documentation

bch_engine()

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::bch_engine ( const bitvect< T, NP > *  polys, int  _npolys  )

inline

Definition at line 44 of file bch.h.

References leansdr::fail(), and i.

        : npolys(_npolys)
    {
        // Build the generator polynomial (product of polys[]).
        g = 1;
        for (int i = 0; i < npolys; ++i)
            g = g * polys[i];
        // Convert the polynomials to truncated representation
        // (with X^DP omitted) for use with divmod().
        truncpolys = new bitvect<T, DP>[npolys];
        for (int i = 0; i < npolys; ++i)
            truncpolys[i].copy(polys[i]);
        // Check which polynomial contains each root.
        // Note: The DVB-S2 polynomials are numbered so that
        // syndpoly[2*i]==i, but we don't use that property.
        syndpolys = new int[2 * npolys];
        for (int i = 0; i < 2 * npolys; ++i)
        {
            int j;
            for (j = 0; j < npolys; ++j)
                if (!eval_poly(truncpolys[j], true, 1 + i))
                    break;
            if (j == npolys)
                fail("Bad polynomials/root");
            syndpolys[i] = j;
        }
    }

Here is the call graph for this function:

Member Function Documentation

decode()

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

int leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::decode ( uint8_t *  cw, size_t  cwbytes  )

inlinevirtual

Implements leansdr::bch_interface.

Definition at line 85 of file bch.h.

References leansdr::divmod(), and i.

    {
        //again:
        bool corrupted = false;
        // Divide by individual polynomials.
        // TBD Maybe do in parallel, scanning cw only once.
        bitvect<T, DP> *rem = new bitvect<T, DP>[npolys]; // npolys is not static hence 'bitvect<T, DP> rem[npolys]' does not compile in all compilers
        for (int j = 0; j < npolys; ++j)
        {
            rem[j] = divmod(cw, cwbytes, truncpolys[j]);
        }
        // Compute syndromes.
        TGF *S = new TGF[2 * npolys]; // npolys is not static hence 'TGF S[2 * npolys]' does not compile in all compilers
        for (int i = 0; i < 2 * npolys; ++i)
        {
            // Compute R(alpha^(1+i)), exploiting the fact that
            // R(x)=Q(x)g_j(X)+rem_j(X) and g_j(alpha^(1+i))=0
            // for some j that we already determined.
            // TBD Compute even exponents using conjugates.
            S[i] = eval_poly(rem[syndpolys[i]], false, 1 + i);
            if (S[i])
                corrupted = true;
        }
        if (!corrupted)
        {
            delete[] S;
            delete[] rem;
            return 0;
        }
#if 0
      fprintf(stderr, "synd:");
      for ( int i=0; i<2*npolys; ++i ) fprintf(stderr, " %04x", S[i]);
      fprintf(stderr, "\n");
#endif

        // S_j = R(alpha_j) = 0+E(alpha_j) = sum(l=1..L)((alpha^j)^i_l)
        // where i_1 .. i_L are the degrees of the non-zero coefficients of E.
        // S_j = sum(l=1..L)((alpha^i_l)^j) = sum(l=1..L)(X_l^j)

        // Berlekamp - Massey
        // http://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm
        // TBD More efficient to work with logs of syndromes ?

        int NN = 2 * npolys;
        TGF *C = new TGF[NN];
        C[0] = 1;
        TGF *B = new TGF[NN];
        B[0] = 1;
        // TGF C[NN] = { crap code
        //     1,
        // },
        //     B[NN] = {
        //         1,
        //     };
        int L = 0, m = 1;
        TGF b = 1;
        for (int n = 0; n < NN; ++n)
        {
            TGF d = S[n];
            for (int i = 1; i <= L; ++i)
                d = GF.add(d, GF.mul(C[i], S[n - i]));
            if (d == 0)
                ++m;
            else
            {
                TGF d_div_b = GF.mul(d, GF.inv(b));
                if (2 * L <= n)
                {
                    TGF *tmp = new TGF[NN]; // replaced crap code
                    memcpy(tmp, C, sizeof(tmp));
                    for (int i = 0; i < NN - m; ++i)
                        C[m + i] = GF.sub(C[m + i], GF.mul(d_div_b, B[i]));
                    L = n + 1 - L;
                    memcpy(B, tmp, sizeof(B));
                    b = d;
                    m = 1;
                    delete[] tmp;
                }
                else
                {
                    for (int i = 0; i < NN - m; ++i)
                        C[m + i] = GF.sub(C[m + i], GF.mul(d_div_b, B[i]));
                    ++m;
                }
            }
        }
        // L is the number of errors.
        // C of degree L is the error locator polynomial (Lambda).
        // C(X) = sum(l=1..L)(1-X_l*X).
#if 0
      fprintf(stderr, "C[%d]=", L);
      for ( int i=0; i<NN; ++i ) fprintf(stderr, " %04x", C[i]);
      fprintf(stderr, "\n");
#endif

        // Forney
        // http://en.wikipedia.org/wiki/Forney_algorithm
        // Simplified because coefficients are in GF(2).

        // Find zeroes of C by exhaustive search.
        // TODO Chien method
        int roots_found = 0;
        for (int i = 0; i < (1 << DP) - 1; ++i)
        {
            // Candidate root ALPHA^i
            TGF v = eval_poly(C, L, i);
            if (!v)
            {
                // ALPHA^i is a root of C, i.e. the inverse of an X_l.
                int loc = (i ? (1 << DP) - 1 - i : 0); // exponent of inverse
                // Reverse because cw[0..cwbytes-1] is stored MSB first
                int rloc = cwbytes * 8 - 1 - loc;
                if (rloc < 0)
                {
                    // This may happen if the code is used truncated.
                    delete[] C;
                    delete[] B;
                    delete[] S;
                    delete[] rem;
                    return -1;
                }
                cw[rloc / 8] ^= 128 >> (rloc & 7);
                ++roots_found;
                if (roots_found == L)
                    break;
            }
        }

        delete[] C;
        delete[] B;
        delete[] S;
        delete[] rem;

        if (roots_found != L)
            return -1;
        return L;
    }

Here is the call graph for this function:

encode()

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

void leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::encode ( const uint8_t *  msg, size_t  msgbytes, uint8_t *  out  )

inlinevirtual

Implements leansdr::bch_interface.

Definition at line 74 of file bch.h.

References i, leansdr::parity(), leansdr::shiftdivmod(), and leansdr::bitvect< T, N >::v.

    {
        bitvect<T, N> parity = shiftdivmod(msg, msgbytes, g);
        // Output as bytes, coefficient of highest degree first
        for (int i = N / 8; i--; ++out)
            *out = parity.v[i / sizeof(T)] >> ((i & (sizeof(T) - 1)) * 8);
    }

Here is the call graph for this function:

eval_poly() [1/2]

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

TGF leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::eval_poly ( const bitvect< T, DP > &  poly, bool  is_trunc, int  rootexp  )

inlineprivate

Definition at line 226 of file bch.h.

References i.

    {
        TGF acc = 0;
        int re = 0;
        for (int i = 0; i < DP; ++i)
        {
            if (poly[i])
                acc = GF.add(acc, GF.exp(re));
            re += rootexp;
            if (re >= (1 << DP) - 1)
                re -= (1 << DP) - 1; // mod 2^DP-1 incrementally
        }
        if (is_trunc)
            acc = GF.add(acc, GF.exp(re));
        return acc;
    }

eval_poly() [2/2]

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

TGF leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::eval_poly ( const TGF *  poly, int  deg, int  rootexp  )

inlineprivate

Definition at line 245 of file bch.h.

References i.

    {
        TGF acc = 0;
        int re = 0;
        for (int i = 0; i <= deg; ++i)
        {
            acc = GF.add(acc, GF.mul(poly[i], GF.exp(re)));
            re += rootexp;
            if (re >= (1 << DP) - 1)
                re -= (1 << DP) - 1; // mod 2^DP-1 incrementally
        }
        return acc;
    }

Member Data Documentation

g

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

bitvect<T, N> leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::g

private

Definition at line 262 of file bch.h.

GF

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

gf2n<TGF, DP, 2, GFTRUNCGEN> leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::GF

private

Definition at line 264 of file bch.h.

npolys

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

int leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::npolys

private

Definition at line 260 of file bch.h.

syndpolys

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

int* leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::syndpolys

private

Definition at line 261 of file bch.h.

truncpolys

template<typename T , int N, int NP, int DP, typename TGF , int GFTRUNCGEN>

bitvect<T, DP>* leansdr::bch_engine< T, N, NP, DP, TGF, GFTRUNCGEN >::truncpolys

private

Definition at line 259 of file bch.h.

---

The documentation for this struct was generated from the following file:

• plugins/channelrx/demoddatv/leansdr/bch.h