leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr > Struct Template Reference

#include <ldpc.h>

Collaboration diagram for leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >:

Classes
struct	node

Public Types
typedef int64_t	score_t

Public Member Functions
	ldpc_engine ()
	ldpc_engine (const ldpc_table< Taddr > *table, int _k, int _n)
void	print_node_stats ()
int	count_edges (node *nodes, int nnodes)
void	encode (const ldpc_table< Taddr > *table, const SOFTWORD *msg, int k, int n, SOFTWORD *parity, int integrate=true)
score_t	compute_scores (SOFTWORD *m, SOFTWORD *p, SOFTWORD *q, int nc, score_t *score, int k)
int	decode_bitflip (const ldpc_table< Taddr > *table, SOFTWORD *cw, int k, int n, int max_bitflips)

Static Public Member Functions
static void	integrate_bits (const SOFTWORD *in, SOFTWORD *out, int nwords)
static void	diff_bits (const SOFTWORD *in, SOFTWORD *out, int nwords)

Public Attributes
int	k
int	n
node *	vnodes
node *	cnodes

Static Public Attributes
static const int	PPCM = 39

Detailed Description

template<typename SOFTBIT, typename SOFTWORD, int SWSIZE, typename Taddr>
struct leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >

Definition at line 52 of file ldpc.h.

Member Typedef Documentation

score_t

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

typedef int64_t leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::score_t

Definition at line 258 of file ldpc.h.

Constructor & Destructor Documentation

ldpc_engine() [1/2]

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::ldpc_engine ( )

inline

Definition at line 55 of file ldpc.h.

        : vnodes(NULL), cnodes(NULL)
    {
    }

ldpc_engine() [2/2]

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::ldpc_engine ( const ldpc_table< Taddr > *  table, int  _k, int  _n  )

inline

Definition at line 88 of file ldpc.h.

References leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::node::append(), leansdr::fail(), leansdr::fatal(), leansdr::ldpc_table< Taddr >::nrows, leansdr::ldpc_table< Taddr >::q, and leansdr::ldpc_table< Taddr >::rows.

        : k(_k), n(_n)
    {
        // Sanity checks
        if (360 % SWSIZE)
            fatal("Bad LDPC word size");
        if (k % SWSIZE)
            fatal("Bad LDPC k");
        if (n % SWSIZE)
            fatal("Bad LDPC n");
        if (k != table->nrows * 360)
            fatal("Bad table");
        int n_k = n - k;
        if (table->q * 360 != n_k)
            fatal("Bad q");

        vnodes = new node[k];
        memset(vnodes, 0, sizeof(node) * k);
        cnodes = new node[n_k];
        memset(cnodes, 0, sizeof(node) * n_k);

        // Expand the graph.

        int m = 0;
        // Iterate over rows
        for (const typename ldpc_table<Taddr>::row *prow = table->rows;
             prow < table->rows + table->nrows;
             ++prow)
        {
            // Process 360 bits per row.
            int q = table->q;
            int qoffs = 0;
            for (int mw = 360; mw--; ++m, qoffs += q)
            {
                const Taddr *pa = prow->cols;
                for (int nc = prow->ncols; nc--; ++pa)
                {
                    int a = (int)*pa + qoffs;
                    if (a >= n_k)
                        a -= n_k; // Modulo n-k. Note qoffs<360*q.
                    if (a >= n_k)
                        fail("Invalid LDPC table");
                    vnodes[m].append(a);
                    cnodes[a].append(m);
                }
            }
        }
    }

Here is the call graph for this function:

Member Function Documentation

compute_scores()

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

score_t leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::compute_scores ( SOFTWORD *  m, SOFTWORD *  p, SOFTWORD *  q, int  nc, score_t *  score, int  k  )

inline

c, v, s, err, softwords_weight<SOFTBIT,SOFTWORD>(m,*pe));

Definition at line 260 of file ldpc.h.

References leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::node::edges, leansdr::softbit_harden(), and leansdr::softwords_xor().

    {
        int total = 0;
        memset(score, 0, k * sizeof(*score));
        for (int c = 0; c < nc; ++c)
        {
            SOFTBIT err = softwords_xor(p, q, c);
            if (softbit_harden(err))
            {
                Taddr *pe = cnodes[c].edges;
                for (int e = cnodes[c].nedges; e--; ++pe)
                {
                    int v = *pe;
                    int s = err * softwords_weight<SOFTBIT, SOFTWORD>(m, v) * PPCM / vnodes[v].nedges;
                    //fprintf(stderr, "c[%d] bad => v[%d] += %d  (%d*%d)\n",
                    score[v] += s;
                    total += s;
                }
            }
        }
        return total;
    }

Here is the call graph for this function:

count_edges()

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

int leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::count_edges ( node *  nodes, int  nnodes  )

inline

Definition at line 145 of file ldpc.h.

References leansdr::fatal(), i, leansdr::ldpc_table< Taddr >::nrows, leansdr::parity(), leansdr::ldpc_table< Taddr >::q, leansdr::ldpc_table< Taddr >::rows, leansdr::softword_get(), leansdr::softword_zero(), and leansdr::softwords_flip().

    {
        int c = 0;
        for (int i = 0; i < nnodes; ++i)
            c += nodes[i].nedges;
        return c;
    }

Here is the call graph for this function:

decode_bitflip()

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

int leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::decode_bitflip ( const ldpc_table< Taddr > *  table, SOFTWORD *  cw, int  k, int  n, int  max_bitflips  )

inline

Definition at line 285 of file ldpc.h.

References leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::node::edges, leansdr::fail(), lfprintf, leansdr::softbit_harden(), leansdr::softbit_set(), leansdr::softwords_flip(), and leansdr::softwords_xor().

Referenced by leansdr::s2_fecdec< SOFTBIT, SOFTBYTE >::run().

    {
        if (!vnodes)
            fail("LDPC graph not initialized");
        int n_k = n - k;

        // Compute the expected check bits (without the final mixing)
        SOFTWORD *expected = new SOFTWORD[n_k / SWSIZE]; // Forbidden to statically allocate with non constant size
        encode(table, cw, k, n, expected, false);
        // Reverse the integrator mixing from the received check bits
        SOFTWORD *received = new SOFTWORD[n_k / SWSIZE]; // Forbidden to statically allocate with non constant size
        diff_bits(cw + k / SWSIZE, received, n_k / SWSIZE);

        // Compute initial scores
        score_t *score = new score_t[k]; // Forbidden to statically allocate with non constant size
        score_t tots = compute_scores(cw, expected, received, n_k, score, k);
        lfprintf(stderr, "Initial score %d\n", (int)tots);

        int nflipped = 0;

        score_t score_threshold;
        {
            SOFTBIT one;
            softbit_set(&one, true);
            score_threshold = (int)one * 2;
        }

        bool progress = true;
        while (progress && nflipped < max_bitflips)
        {
            progress = false;
            // Try to flip parity bits.
            // Due to differential decoding, they appear as consecutive errors.
            SOFTBIT prev_err = softwords_xor(expected, received, 0);
            for (int b = 0; b < n - k - 1; ++b)
            {
                prev_err = softwords_xor(expected, received, b); //TBD
                SOFTBIT err = softwords_xor(expected, received, b + 1);
                if (softbit_harden(prev_err) && softbit_harden(err))
                {
                    lfprintf(stderr, "flip parity %d\n", b);
                    softwords_flip(received, b);
                    softwords_flip(received, b + 1);
                    ++nflipped; // Counts as one flip before differential decoding.
                    progress = true;
                    int dtot = 0;
                    // Depenalize adjacent message bits.
                    {
                        Taddr *pe = cnodes[b].edges;
                        for (int e = cnodes[b].nedges; e--; ++pe)
                        {
                            int d = prev_err * softwords_weight<SOFTBIT, SOFTWORD>(cw, *pe) * PPCM / vnodes[*pe].nedges;
                            score[*pe] -= d;
                            dtot -= d;
                        }
                    }
                    {
                        Taddr *pe = cnodes[b + 1].edges;
                        for (int e = cnodes[b + 1].nedges; e--; ++pe)
                        {
                            int d = err * softwords_weight<SOFTBIT, SOFTWORD>(cw, *pe) * PPCM / vnodes[*pe].nedges;
                            score[*pe] -= d;
                            dtot -= d;
                        }
                    }
                    tots += dtot;
#if 1
                    // Also update the codeword in-place.
                    // TBD Useful for debugging only.
                    softwords_flip(cw, k + b);
#endif
                    // TBD version soft. err = ! err;
                }
                prev_err = err;
            } // c nodes
            score_t maxs = -(1 << 30);
            for (int v = 0; v < k; ++v)
                if (score[v] > maxs)
                    maxs = score[v];
            if (!maxs)
                break;
            lfprintf(stderr, "maxs %d\n", (int)maxs);
            // Try to flip each message bits with maximal score
            for (int v = 0; v < k; ++v)
            {
                if (score[v] < score_threshold)
                    continue;
                //    if ( score[v] < maxs*9/10 ) continue;
                if (score[v] < maxs - 4)
                    continue;
                lfprintf(stderr, "  flip %d score=%d\n", (int)v, (int)score[v]);
                // Update expected parities and scores that depend on them.
                score_t dtot = 0;
                for (int commit = 0; commit <= 1; ++commit)
                {
                    Taddr *pe = vnodes[v].edges;
                    for (int e = vnodes[v].nedges; e--; ++pe)
                    {
                        Taddr c = *pe;
                        SOFTBIT was_bad = softwords_xor(expected, received, c);
                        if (softbit_harden(was_bad))
                        {
                            Taddr *pe = cnodes[c].edges;
                            for (int e = cnodes[c].nedges; e--; ++pe)
                            {
                                int d = was_bad * softwords_weight<SOFTBIT, SOFTWORD>(cw, *pe) * PPCM / vnodes[*pe].nedges;
                                if (commit)
                                    score[*pe] -= d;
                                else
                                    dtot -= d;
                            }
                        }
                        softwords_flip(expected, c);
                        SOFTBIT is_bad = softwords_xor(expected, received, c);
                        if (softbit_harden(is_bad))
                        {
                            Taddr *pe = cnodes[c].edges;
                            for (int e = cnodes[c].nedges; e--; ++pe)
                            {
                                int d = is_bad * softwords_weight<SOFTBIT, SOFTWORD>(cw, *pe) * PPCM / vnodes[*pe].nedges;
                                if (commit)
                                    score[*pe] += d;
                                else
                                    dtot += d;
                            }
                        }
                        if (!commit)
                            softwords_flip(expected, c);
                    }
                    if (!commit)
                    {
                        if (dtot >= 0)
                        {
                            lfprintf(stderr, "    abort %d\n", v);
                            break; // Next v
                        }
                    }
                    else
                    {
                        softwords_flip(cw, v);
                        ++nflipped;
                        tots += dtot;
                        progress = true;
                        v = k - 1; // Force exit to update maxs ?
                    }
                } // commit
            }     // v
            lfprintf(stderr, "progress %d\n", progress);
#if 0
    fprintf(stderr, "CHECKING TOTS INCREMENT (slow) %d\n", tots);
    score_t tots2 = compute_scores(cw, expected, received, n_k, score, k);
    if ( tots2 != tots ) fail("bad tots update");
#endif
        }

        delete[] score;
        delete[] received;
        delete[] expected;

        return nflipped;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

diff_bits()

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

static void leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::diff_bits ( const SOFTWORD *  in, SOFTWORD *  out, int  nwords  )

inlinestatic

Definition at line 491 of file ldpc.h.

References i, leansdr::softbit_clear(), leansdr::softbit_xor(), leansdr::softword_get(), and leansdr::softword_write().

    {
        SOFTBIT prev;
        softbit_clear(&prev);
        for (int i = 0; i < nwords; ++i, ++in, ++out)
        {
            SOFTWORD w = *in;
            for (int b = 0; b < SWSIZE; ++b)
            {
                SOFTBIT n = softword_get(w, b);
                softword_write(w, b, softbit_xor(prev, n));
                prev = n;
            }
            *out = w;
        }
    }

Here is the call graph for this function:

encode()

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

void leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::encode ( const ldpc_table< Taddr > *  table, const SOFTWORD *  msg, int  k, int  n, SOFTWORD *  parity, int  integrate = true  )

inline

Definition at line 199 of file ldpc.h.

References leansdr::fatal(), i, leansdr::ldpc_table< Taddr >::nrows, leansdr::ldpc_table< Taddr >::q, leansdr::ldpc_table< Taddr >::rows, leansdr::softbit_harden(), leansdr::softword_get(), leansdr::softword_zero(), and leansdr::softwords_flip().

Referenced by leansdr::s2_fecenc::run_frame().

    {
        // Sanity checks
        if (360 % SWSIZE)
            fatal("Bad LDPC word size");
        if (k % SWSIZE)
            fatal("Bad LDPC k");
        if (n % SWSIZE)
            fatal("Bad LDPC n");
        if (k != table->nrows * 360)
            fatal("Bad table");
        int n_k = n - k;
        if (table->q * 360 != n_k)
            fatal("Bad q");

        for (int i = 0; i < n_k / SWSIZE; ++i)
            softword_zero(&parity[i]);

        // Iterate over rows
        for (const typename ldpc_table<Taddr>::row *prow = table->rows; // quirk
             prow < table->rows + table->nrows;
             ++prow)
        {
            // Process 360 bits per row, in words of SWSIZE bits
            int q = table->q;
            int qoffs = 0;
            for (int mw = 360 / SWSIZE; mw--; ++msg)
            {
                SOFTWORD msgword = *msg;
                for (int wbit = 0; wbit < SWSIZE; ++wbit, qoffs += q)
                {
                    SOFTBIT msgbit = softword_get(msgword, wbit);
                    if (!softbit_harden(msgbit))
                        continue;
                    const Taddr *pa = prow->cols;
                    for (int nc = prow->ncols; nc--; ++pa)
                    {
                        int a = (int)*pa + qoffs;
                        // Note: qoffs < 360*q=n-k
                        if (a >= n_k)
                            a -= n_k; // TBD not predictable
                        softwords_flip(parity, a);
                    }
                }
            }
        }

        if (integrate)
            integrate_bits(parity, parity, n_k / SWSIZE);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

integrate_bits()

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

static void leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::integrate_bits ( const SOFTWORD *  in, SOFTWORD *  out, int  nwords  )

inlinestatic

Definition at line 453 of file ldpc.h.

References i, leansdr::softbit_clear(), leansdr::softbit_xor(), leansdr::softword_get(), and leansdr::softword_write().

    {
        SOFTBIT sum;
        softbit_clear(&sum);
        for (int i = 0; i < nwords; ++i)
        {
            SOFTWORD w = in[i];
            for (int b = 0; b < SWSIZE; ++b)
            {
                sum = softbit_xor(sum, softword_get(w, b));
                softword_write(w, b, sum);
            }
            out[i] = w;
        }
    }

Here is the call graph for this function:

print_node_stats()

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

void leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::print_node_stats ( )

inline

Definition at line 137 of file ldpc.h.

Referenced by leansdr::s2_ldpc_engines< bool, hard_sb >::print_node_stats().

    {
        int nedges = count_edges(vnodes, k);
        fprintf(stderr, "LDPC(%5d,%5d)(%.2f)"
                        " %5.2f edges/vnode, %5.2f edges/cnode\n",
                k, n - k, (float)k / n, (float)nedges / k, (float)nedges / (n - k));
    }

Here is the caller graph for this function:

Member Data Documentation

cnodes

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

node* leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::cnodes

Definition at line 84 of file ldpc.h.

k

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

int leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::k

Definition at line 63 of file ldpc.h.

n

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

int leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::n

Definition at line 64 of file ldpc.h.

PPCM

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

const int leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::PPCM = 39

static

Definition at line 256 of file ldpc.h.

vnodes

template<typename SOFTBIT , typename SOFTWORD , int SWSIZE, typename Taddr >

node* leansdr::ldpc_engine< SOFTBIT, SOFTWORD, SWSIZE, Taddr >::vnodes

Definition at line 83 of file ldpc.h.

---

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

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