Decoder Implementations¶

class Decoder(code, name)¶

Bases: lpdec.persistence.JSONDecodable

The base class for all decoders, defining a minimal set of methods.

The first constructor argument of all subclasses of Decoder should always be the code to decode. The params() method should only return the remaining arguments.

Parameters:

code (LinearBlockCode) – The code on which this decoder operates.
name (str) – Name of the decoder. If used in a database, the name must be unique.

Variables:

code (LinearBlockCode) – The code instance for which the decoder is configured.
foundCodeword (bool) – This flag holds whether a valid codeword has been found or not. Should be set by implementing subclasses within solve().
mlCertificate (bool) – This flag holds whether the decoder has the ML certificate about the decoder output: if this is true after calling solve(), the solution is guaranteed to be the ML codeword. Subclasses should set this within solve().
status ({OPTIMAL, INFEASIBLE, UPPER_BOUND_HIT, LIMIT_HIT}) – More fine-grained status report of the decoding process. Of interest mainly in the context of branch-and-bound decoding.
llrs (double[::1]) – Log-likelihood ratios of channel output used for decoding.
name (str) – Name of the decoder. If used in a database, the name must be unique.

code¶: code: object

decode(self, __Pyx_memviewslice llrs, __Pyx_memviewslice sent=None, double lb=-INFINITY, double ub=INFINITY)¶

decode(self, llrs, sent=None, lb=-INFINITY, ub=INFINITY)

Decode the given LLR vector and return the solution.

This convenience function sets the LLR vector, calls solve(), and returns solution.

Parameters:	llrs (double[::1]) – LLR vector to decode. sent (np.int_t[::1], optional) – The sent codeword, if it is to be revealed. lb (double, optional) – known lower bound on objective value. ub (known upper bound on objective value.) –

fix(self, int index, int value)¶: Fix codeword variable with index index to value $\in \{0,1\}$ .

fixed(self, int i)¶: Returns True if and only if the given index is fixed.

foundCodeword¶: foundCodeword: ‘bool’

hint¶: hint: ‘__Pyx_memviewslice’

llrs¶: llrs: ‘__Pyx_memviewslice’

mlCertificate¶: mlCertificate: ‘bool’

name¶: name: object

objectiveValue¶: objectiveValue: ‘double’

release(self, int index)¶: Release the constraint on a previously fixed variable.

sent¶: sent: ‘__Pyx_memviewslice’

setLLRs(self, __Pyx_memviewslice llrs, __Pyx_memviewslice sent=None)¶

setLLRs(self, llrs, sent=None)

Set the LLR vector for decoding.

Optionally, the codeword that was actually sent might be given as well, which can speed up simulations if the decoder can exploit this knowledge. Of course, this is only relevant for decoding performance simulations, as in reality th sent word is not available.

Parameters:	llrs (double[::1]) – Vector of channel output log-likelihood ratios. sent (np.int_t[::1], optional) – Optionally, the sent codeword.

setStats(self, stats)¶

solution¶: solution: ‘__Pyx_memviewslice’

solve(self, double lb=-INFINITY, double ub=INFINITY)¶

solve(self, lb=-INFINITY, ub=INFINITY)

Run the solver on llrs. A codeword may be given as hint.

This is the main method to run the decoding algorithm; the LLR vector must be set in advance via the llrs attribute or through decode().

Parameters:	lb (double, optional) – Lower bound on the optimal objective value ub (double, optional) – Upper bound on the optimal objective value. Allows the decoder to terminate when the optimal value is proven to be greater than ub.

stats(self)¶

status¶: status: ‘int’

class ProjectionDecoder(code, longCode, decoderCls, **decoderParams)¶

Bases: lpdec.decoders.base.Decoder

A ProjectionDecoder is used for decoding of an $(n,k)$ code $C$ by actually using a longer code :math:` ilde C` such that $C$ is the projection of tilde C onto the first $n$ coordinates. The ProjectionDecoder inserts zeros into the llrs and cuts the solution such that it acts like a decoder for the projected code to the outside world.

Parameters:	code (LinearBlockCode) – The projected code $C$ longCode (LinearBlockCode) – The long (original) code :math:` ilde C`. decoderCls (Decoder) – Class of the wrapped decoder for the long code. decoderParams – Additional parameters to the wrapped decoder (do not include the code).

fix(self, int index, int value)¶

params(self)¶

release(self, int index)¶

setLLRs(self, __Pyx_memviewslice llrs, __Pyx_memviewslice sent=None)¶

setStats(self, stats)¶

solve(self, double lb=-INFINITY, double ub=INFINITY)¶

stats(self)¶

Integer Programming (IP) based decoders¶

This module contains integer programming (IP) decoders for binary linear block codes, based on the formulation called ‘IPD’ in [HRT12].

class CplexIPDecoder(code, name=None, **kwargs)¶

Bases: lpdec.decoders.cplexhelpers.CplexDecoder

CPLEX implementation of the IPD maximum-likelihood decoder.

For ML simulations, the decoding process can be speed up using a shortcut callback.

z¶: Vector of names of the auxiliary variables

minimumDistance(hint=None)¶

Calculate the minimum distance of code via integer programming.

Compared to the decoding formulation, this adds the constraint $|x| \geq 1$ and minimizes $\sum_{i=1}^n x$ .

class GurobiIPDecoder(code, gurobiParams=None, gurobiVersion=None, name=None)¶

Bases: lpdec.decoders.gurobihelpers.GurobiDecoder

Gurobi implementation of the IPD maximum-likelihood decoder.

Parameters:

code (LinearBlockCode) – The code to decoder.
gurobiParams (dict) – Optional dictionary of parameters; these are passed to the Gurobi model via gurobimh.Model.setParam(). The attributes tuningSet1, tuningSet2 and tuningSet3 contain three sets of parameters that were obtained from the Gurobi tuning tool.
gurobiVersion (str) – Version of the Gurobi package; if supplied, an error is raised if the current version does not match.
name (str) – Name of the decoder. Defaults to “GurobiIPDecoder”.

The number of nodes in Gurobi’s branch-and-bound procedure is collected in the statistics.

Example usage:

>>> from lpdec.imports import *
>>> code = HammingCode(3)
>>> decoder = GurobiIPDecoder(code, gurobiParams=GurobiIPDecoder.tuningSet1, name='GurobiTuned')
>>> result = decoder.decode([1, -1, 0, -1.5, 2, 3, 0])
>>> print(result)

tuningSet1¶

Dictionary to be passed to the constructor as gurobiParams; this set of parameters was obtained from the Gurobi tuning tool on a hard instance for the (155,93) Tanner LDPC code.

tuningSet2¶

As above; second-best parameter set.

tuningSet3¶

As above; third-best parameter set.

static callback(model, where)¶: A callback function for Gurobi that is able to terminate the MIP solver if a solution which is better than the sent codeword has been found.

minimumDistance(hint=None)¶

Calculate the minimum distance of code via integer programming.

Compared to the decoding formulation, this adds the constraint $|x| \geq 1$ and minimizes $\sum_{i=1}^n x$ .

Iterative (Message-Passing) Decoders¶

class IterativeDecoder¶

Bases: lpdec.decoders.base.Decoder

Class for iterative decoders, i.e., min-sum or sum-product.

fix()¶: Variable fixing is implemented by adding fixes to the LLRs. This vector contains $\infty$ for a fix to zero and $-\infty$ for a fix to one.

Adaptive LP Decoder with optional RPC cuts¶

GLPK implementation¶

class AdaptiveLPDecoder¶

Bases: lpdec.decoders.base.Decoder

Implements the adaptive linear programming decoder with optional generation of redundant parity-check (RPC) cuts.

Uses the GLPK C-interface for solving the LP subproblems.

Parameters:

maxRPCrounds (int) – Maximum number of iterations of RPC cuts generation. The value -1 means no limit (as in the paper). If set to 0, no RPC cuts are generated, and the decoder behaves as a normal LP decoder.
minCutoff (float) – Minimum violation of an inequality to be inserted as a cut into the LP model. Defaults to 1e-5. A smaller value might lead to numerical problems, i.e,, an inequality being inserted that is not really a cut and hence the danger of infinite loops. On the other hand, a larger value can make sense, in order to only use “strong” cuts.
removeInactive (int) – Determines if and when inactive constraints are removed from the LP model in order to limit its size. 0 (the default) turns off removal of constraints. A value of -1 means that inactive constraints should be removed after each call to the LP solver. A positive number leads to removal of inactive constraints as soon as the total number of constraints exceeds that number.
removeAboveAverageSlack (bool) – If set to True, during removal of inactive constraints (see above) only those with a slack above the average of all inactive constraints are indeed removed.
keepCuts (bool) – If set to True, inserted cuts are not remove after decoding one frame.

hint¶: An optional “hint” codeword that is somehow believed to be near-optimal. For example, this might be the output of an iterative decoder. The adaptive LP decoder can use that hint to insert active constraints.

Gurobi implementation¶

class AdaptiveLPDecoderGurobi¶

Bases: lpdec.decoders.base.Decoder

Implements the adaptive linear programming decoder with optional generation of redundant parity-check (RPC) cuts.

Uses the gurobimh cython interface.

Parameters:

maxRPCrounds (int) – Maximum number of iterations of RPC cuts generation. The value -1 means no limit (as in the paper). If set to 0, no RPC cuts are generated, and the decoder behaves as a normal LP decoder.
minCutoff (float) – Minimum violation of an inequality to be inserted as a cut into the LP model. Defaults to 1e-5. A smaller value might lead to numerical problems, i.e,, an inequality being inserted that is not really a cut and hence the danger of infinite loops. On the other hand, a larger value can make sense, in order to only use “strong” cuts.
removeInactive (int) – Determines if and when inactive constraints are removed from the LP model in order to limit its size. 0 (the default) turns off removal of constraints. A value of -1 means that inactive constraints should be removed after each call to the LP solver. A positive number leads to removal of inactive constraints as soon as the total number of constraints exceeds that number.
removeAboveAverageSlack (bool) – If set to True, during removal of inactive constraints (see above) only those with a slack above the average of all inactive constraints are indeed removed.
keepCuts (bool) – If set to True, inserted cuts are not remove after decoding one frame.
gurobiParams – Additional parameters passed to the gurobi model.

Static LP Decoder¶

class ExplicitLPDecoder(code, gurobiParams=None, gurobiVersion=None, ml=False, name=None)¶

Bases: lpdec.decoders.gurobihelpers.GurobiDecoder

LP Decoder using the static explicit LP formulation (no auxiliary variables) from [FWK05].

class StaticLPDecoder(code, gurobiParams=None, gurobiVersion=None, ml=False, cascade=False, name=None)¶

Bases: lpdec.decoders.gurobihelpers.GurobiDecoder

LP Decoder using the static LP formulation with auxiliary variables from [FWK05]. Also supports the linear-sized cascaded version from [YWF08] and nonbinary versions of both due to [FSBG09].

Parameters:	ml – When True, the LP is solved with integer contstraints, resulting in ML decoding. cascade – When True, use the cascaded formulation.

createLocalCodePolytope(jname, h, xvars)¶: Adds auxiliary variables and constraints for a local code polytope, given by the local parity-check row h and the according variable dictionary xvars.

Branch-and-Cut Decoder¶

Main B&C Decoder module¶

class BranchAndCutDecoder¶

Bases: lpdec.decoders.base.Decoder

Maximum-Likelihood decoder using a branch-and-cut approach.

Parameters:

selectionMethod ({‘dfs’, ‘bbs’, ‘mixed<steps>/<gap>’}) –
Method to determine the next node from the set of active nodes. Possible values are:
- 'dfs': Depth-first search
- 'bbs': Best-bound search
- 'mixed<steps>/<gap>': Mixed strategy. Uses depth-first search in general but jumps to the node with smallest lower bound every <steps> iterations, but only if the duality gap at the current node is at least <gap>.
maxDecay (float) –
maxDecayDepthFactor (float) –
dfsDepthFactor (float) –
childOrder ({‘01’, ‘10’, ‘llr’, ‘random’}) –
Determines the order in which newly created child branch-and-bound nodes are appended to the list of active nodes. Possible values are:
- '01': child with zero-fix is added first
- '10': child with one-fix is added first
- 'llr': add first the node whose fix-value equals the hard-decision value of the fixed bit.
- 'random': add in random order
The default value is '01'.
highSNR (bool) – Use optimizations for high SNR values. Defaults to False.
lpClass (type) – Class of the LP decoder. Default: AdaptiveLPDecoder.
lpParams (dict) – Parameters for the LP decoder
iterClass (type) – Class of the upper bound provider. Default: IterativeDecoder.
iterParams (dict) – Parameters for the iterative decoder.
initOrder (int, optional) – When using an iterative decoder, this number specifies the re-encoding order used at the initial (root) node. Higher value increases computation time but might lead to a good starting solution.
branchClass (type) – Class of branching rule to use; see also branching.
branchParams (dict) – Parameters for instantiating the branching rule.

minimumDistance()¶: Compute the minimum distance of the code.

Branch Rule Implementations¶

class BranchingRule¶

Bases: lpdec.persistence.JSONDecodable

Base class for branching rules used in a branch-and-bound decoder.

Parameters:	code (`lpdec.codes.BinaryLinearBlockCode`) – The code under consideration. bcDecoder (`BranchAndCutDecoder`) – The decoder instance. lamb (int, optional) – mu (int, optional) –
Variables:	ub (float) – canPrune (bool) – index (int) –

Erasure Decoder¶

class ErasureDecoder(code, name=None)¶

Bases: lpdec.decoders.base.Decoder

A simple decoder for the binary erasure channel.

The decoder behaves a little different than others with respect to the interpretation of LLRs, objective value and solution:

A zero LLR is interpreted as an erasure, any positive value as a guaranteed 0, and any negative value as a guaranteed 1. This has the same effect as multiplying the LLR with $+\infty$ in the normal meaning.
The objective value is $-n$ , where $n$ is the number of filled out erasures. An objective value of $\infty$ indicates a contradictory setting at a check, i.e., a degree-2 check with neighbors fixed to 0 and 1, respectively. This can not occur on the BEC but, for instance, in the context of branch-and-bound.
The solution contains entries $-1$ at positions that could not be filled out.

corrected¶: Contains 0s and 1s in the positions that were filled out by the algorithm, and -1s otherwise.

Polar Code Decoders¶

class PolarSCDecoder¶

Bases: lpdec.decoders.base.Decoder

Implements a successive cancellation decoder for polar codes.

class PolarSCListDecoder¶

Bases: lpdec.decoders.base.Decoder

Implements a successive cancellation list decoder for polar codes.