Convolutional and Turbo Codes Modules¶

Interleavers¶

This module contains tools to create interleavers for turbo-like code.

Both QPP (quadratic permutation polynomial) interleavers and random interleavers are supported.

class Interleaver(**kwargs)¶

Bases: lpdec.persistence.JSONDecodable

An interleaver of a given size s is a permutation on the set {0, ..., s-1}.

The permutation function is available by just calling the interleaver object. Additionally, its inverse is supplied by the inv() function.

static random(length)¶: Creates and returns a random interleaver of the given length.

__call__(i)¶: The permutation function.

inv(i)¶: The inverse permutation function.

inverted()¶: Returns an interleaver whose permutation is the inverse of this one.

shuffle(sequence)¶

Randomly permute the elements of x in-place.

This method implements the Knuth shuffle procedure and thus provides better distribution than the random.shuffle.

factorize(n)¶: Factorize the given number n, returning a dict that maps factors to their multiplicity.

randomf1(size, factors)¶: Creates a random number f1 in [1, size) such that for all x in factors: x mid f1

randomf2(size, kernel)¶: Creates a random number f2 in [1,size) such that kernel|f2

randomf1f2(size, onlyQI=False)¶: Generate random coefficients f1,f2 for a QPP interleaver of given size

allf1(size)¶: Generates all valid coefficients f1 for a QPP interleaver of given size

allf2(size, onlyQI=False)¶

Generates all valid f2 coefficients for a QPP interleaver of given size.

If onlyQI is true, only generate coefficients that lead to a QPP with a QPP inverse.

randomQPP(size, onlyQI=False)¶

Generate a random QPP of given size and return a corresponding Interleaver instance.

The optional onlyQI parameter, if set to True, specifies that only QPPs with a quadratic inverse should be selected.

allQPPInterleavers(size, unique=True, onlyQI=False)¶

Generates all QPP interleavers of a given size.

If unique=True, interleavers with different f1,f2-coefficients that generate the same function are contained only once. If onlyQI=True, only QPPs with a quadratic inverse are considered.

class LTEInterleaver(k)¶

Bases: lpdec.codes.interleaver.Interleaver

The class of interleavers specified for 3GPP LTE Turbo Codes.

Convolutional Codes¶

This module contains classes for trellis-based code definitions.

class ConvolutionalEncoder(filename=None, transitionTable=None, name=None)¶

Bases: lpdec.persistence.JSONDecodable

A class for representing convolutional encoders.

Convolutional encoders are defined by a state transition function: For a given current state and input bit, the table outputs the subsequent state and the output bit emitted during this transition. Note that, at the moment, only one output per transition is supported. The table can be read from a text file containing lines of the format

a b c d

where a is the state before transition, b is the input bit, c the next state, and d the output bit.

stateTransition(state, inputBit)¶: Returns next state and parity output for given state/input as a tuple.

stateTransitionBack(state, inputBit)¶

The “pseudo-inverse” function of stateTransition().

More specifically, returns a tuple (origState, outputBit) such that the encoder transits from origState to state when fed an inputBit and emits outputBit thereby.

class RepeatAccumulateEncoder¶

Bases: lpdec.codes.convolutional.ConvolutionalEncoder

The finite state machine corresponding to an RA code.

class LTEEncoder¶

Bases: lpdec.codes.convolutional.ConvolutionalEncoder

The encoder given by (1+D+D^3)/(1+D^2 + D^3), as defined in the LTE standard.

class TDInnerEncoder¶

Bases: lpdec.codes.convolutional.ConvolutionalEncoder

The convolutional encoder given by 1/(1+D^2), used as inner encoder in 3-D Turbo Codes.

Trellis Graphs¶

class Arc(Node tail, Node head, int infobit, int parity, int pos, int state)¶

Bases: object

Data class representing an arc in a trellis (arcs are sometimes called branches or edges in literature).

Parameters:

tail (Node) – Tail (starting point) of the arc.
head (Node) – Head (end point) of the arc.
infobit (int) – Information bit (also called input bit, systematic bit) corresponding to this arc.
parity (int) – Parity bit (also called output bit) corresponding to this arc.
pos (int) – Position (time step) of this arc’s tail in the trellis.
state (int) – State of this arc’s tail in the trellis.

cost¶: cost: ‘double’

kpaths_candidate¶: kpaths_candidate: object

lp_var¶: lp_var: object

orig_cost¶: orig_cost: ‘double’

remove(self)¶: Remove the arc from the trellis, updating head and tail.

class Node¶

Bases: object

A trellis node (vertex). Has a (time-domain) position and a state.

binaryState¶: binaryState: object

inArc_0¶: inArc_0: lpdec.codes.trellis.Arc

inArc_1¶: inArc_1: lpdec.codes.trellis.Arc

inArcs(self)¶

Return a tuple of the (up to two) ingoing arcs of this node.

It is guaranteed that the “zero” in arc appears first, if it exists.

kpaths¶: kpaths: object

outArc_0¶: outArc_0: lpdec.codes.trellis.Arc

outArc_1¶: outArc_1: lpdec.codes.trellis.Arc

outArcs(self)¶

Return a tuple of the (up to two) outgoing arcs of this node.

It is guaranteed that the “zero” out arc appears first, if it exists.

path_cost¶: path_cost: ‘double’

pred_arc¶: pred_arc: lpdec.codes.trellis.Arc

class Segment¶

Bases: object

One segment (vertical slice) of a trellis.

Consists of up to numstates nodes, some of which may be None. Can be used like a dict mapping state number to node. For fast access, use the C-level, e.g. <Node>(segment.nodes[i]).

allArcsOfInfoBit(self, int bit)¶: Generator that yields all arcs which have the given information bit (0 or 1).

allArcsOfParity(self, int bit)¶: Yield all arcs which have the given parity bit (0 or 1).

connectBackward(self, Segment prev, encoder)¶: Creates incoming arcs and source nodes in the previous segment, if necessary.

connectForward(self, Segment next, encoder)¶: Creates outgoing arcs from self and target nodes in the next segment, if necessary.

fix_info¶: fix_info: ‘int’

fix_parity¶: fix_parity: ‘int’

g_info¶: g_info: ‘double’

g_info_index¶: g_info_index: ‘int’

g_parity¶: g_parity: ‘double’

g_parity_index¶: g_parity_index: ‘int’

info_code_bit¶: info_code_bit: ‘int’

info_code_ratio¶: info_code_ratio: ‘double’

items(self)¶

keys(self)¶

parity_code_bit¶: parity_code_bit: ‘int’

parity_code_ratio¶: parity_code_ratio: ‘double’

setCost(self, double infoCost, double parityCost)¶

Set the cost on the arcs in this segments.

The cost of each Arc arc in the segment will be calculated as arc.infobit * infoCost + arc.parity * parityCost.

Parameters:	infoCost (double) – Cost associated with setting the information bit corresponding to this segment to `1`. parityCost (double) – Cost associated with setting the parity bit corresponding to this segment to `1`.

values(self)¶

class Trellis(encoder, int length, int states=-1, str infoTail='out', str parityTail='out', str name=None)¶

Bases: object

A trellis.

allArcs(self)¶

Generator over all arcs in the trellis in canonical order.

The arcs are yielded left to right, top-state to down-state, infobit 0 to infobit 1.

append(self, Segment seg)¶: Hacky method to allow appending a segment at the end.

clearArcCosts(self)¶

encode(self, __Pyx_memviewslice path) → __Pyx_memviewslice¶

Encode the given path, return the corresponding parity output.

The length of path must be at least self.insize; for convenience additional bits (e.g. tail bits) will be ignored instead of raising an error.

endVertex¶: endVertex: lpdec.codes.trellis.Node

inArcs(self, int pos)¶

Returns the arcs corresponding to the pos-th input bit.

This function respects the infoTail and parityTail attributes.

infoTail¶: The info tail bit interpretation – “in”, “out” or “drop”.

initVertex¶: initVertex: lpdec.codes.trellis.Node

name¶: name: str

outArcs(self, int pos)¶

Returs the arcs corresponding to the pos-th output bit.

This function respects the infoTail and parityTail attributes.

parityTail¶: The parity tail bit interpretation – “in”, “out” or “drop”.

segmentAndLabel(self, int i, str l)¶

Returns segment and label type corresponding to a specific bit in the input or output.

The method returns a tuple (seg, lab) such that the arcs labeled lab (∈ {INFO, PARITY}) in the seg-th trellis segment correspond to the i-th input bit (if l=”in”) or the i-th output bit (if l=”out”), respectively, of the trellis viewed as an encoder.

states¶: states: ‘int’

Turbo Codes¶

class TurboVertex¶

Bases: object

Base class for all vertices of turbo-like codes.

The class property isStopper tells whether the vertex is a “stopper”, that is, doing more complicated things with the incoming bits than just routing them to a specific output position. At the moment, the information source, code vertex, and constituend encoders are stoppers, while (de)muxing vertices are no stoppers.

connect(target, size, interleaver=None)¶

Connect size bits of this vertex’ output to the input of target.

Creates an InterleaverArc if an interleaver is specified, or an ordinary TurboArc otherwise.

class InformationSource(infobits)¶

Bases: lpdec.codes.turbolike.TurboVertex

The vertex representing the information source in a turbo-like code. Each code must have exactly one information source.

The information source can be connected to several vertices, which is interpreted such that each connection carries a complete copy of the information input.

connect(target, interleaver=None)¶: Convenience function: Automatically determine the size

class EncoderVertex(encoder, length, name=None, **kwargs)¶

Bases: lpdec.codes.turbolike.TurboVertex

Represents a constituent convolutional encoder. Each encoder has an associated Trellis graph. Depending on the termination scheme used, the output might be larger than the input.

connect(target)¶: Convenience function: Automatically sets size.

class MuxVertex(style='sequential', name=None)¶

Bases: lpdec.codes.turbolike.TurboVertex

A MuxVertex takes several inputs and muxes them together into one output.

Muxing is performed in either of the following styles:

'sequential': The bits of the inputs are sequentially concatenated
'alternating': The inputs are “interleaved” into the output.

Example

Assume there are three inputs of length four each, so we have the bits

from input a: a1 a2 a3 a4
from input b: b1 b2 b3 b4
from input c: c1 c2 c3 c4

Sequential muxing outputs a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4, while alternating muxing yields a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4.

Parameters:	style ({‘sequential’, ‘alternating’}, optional) – Selects the muxing scheme, which defaults to ‘sequential’.

connect(target, interleaver=None)¶: Connect to the target; automatically sets the size of the outgoing arc. Note that this method has to be called /after/ all ingoing connections have been defined, since the total size is not known before.

outPosition(inArc, inBit)¶: Returns a tuple (arc, pos) such that the inBit-th bit incoming through inArc is the pos-th bit on arc. Note that arc will always be the single output arc.

inPosition(outArc, outBit)¶: Returns a tuple (arc, pos) such that the pos-th bit incoming through arc is the outPos-th bit on outArc (which must be the single output arc).

class DeMuxVertex(pattern, name=None)¶

Bases: lpdec.codes.turbolike.TurboVertex

Takes a single input and splits its bits into a number of output arcs.

DeMuxVertex acts as a counterpart of a MuxVertex. Which bit goes to which output is determined by a pattern, which is a tuple of output positions. For instance, the pattern (0,1,1) means that every third bit goes to the first output and the rest go to the second output.

More formally, if $(p_1, \dots, p_k)$ is a pattern, then the i-th input bit goes to output $p_{i mod k}$ . Note how this supports outputs of different length.

connect(target, interleaver=None)¶

Connects this demuxer to another vertex, optionally using an interleaver.

This method has to be called after the input connection has been made, and each call corresponds to the next symbol of the pattern. The size is determined automatically from the insize and the pattern.

Parameters:	target (TurboVertex) – The target vertex to connect to. interleaver (`Interleaver`, optional) – An interleaver to use. If left out, no interleaving is performed.

inPosition(outArc, outPos)¶

Compute input position routed to outPos-th bit on outArc.

Returns a tuple (arc, pos) such that the pos-th input bit on arc (the single incoming arc) is routed to the outPos-th bit on outArc.

outPosition(inArc, inBit)¶

Compute output position and arc to which inBit of the single inArc is routed.

Returns a tuple (arc, pos) such that the inBit-th input bit on inArc (the single incoming arc) is routed to the pos-th bit of arc.

class CodeVertex¶

Bases: lpdec.codes.turbolike.TurboVertex

A CodeVertex represents the codeword of a turbo-like code.

It has a single incoming arc, the bits of which comprise the codeword.

class TurboArc(size, tail, head)¶

Bases: object

A TurboArc connects two TurboVertex instances.

It has the attributes:

size, the number of bits transfered through the arc
tail, the vertex where it starts,
head, the vertex where it ends.

endPosition(start)¶

Returns the position to which start-th input bit is wired.

This is the identity mapping for non-interleaver arcs.

startPosition(end)¶

Returns the position which is wired to the end-th bit in the output.

This is the identity mapping for non-interleaver arcs.

endOfPath(i)¶

Compute where the i-th bit on this arc encounters the next stopper vertex.

Returns a tuple (vertex, pos) such that the i-th bit of this arc is wired to the pos-th input bit of vertex, which is a stopper vertex (encoder or codeword). In other words, this method identifiers the terminal position of the i-th bit on its path through muxers and demuxers.

startOfPath(i)¶

Compute where the i-th bit of this arc originates at an encoder or InformationSource.

This is complementary to endOfPath: Returns a tuple (vertex, pos) such that the bit at position i at the /end/ of this arc originates from vertex (encoder or InformationSource) at output position pos.

class InterleaverArc(interleaver, tail, head)¶

Bases: lpdec.codes.turbolike.TurboArc

A TurboArc with an interleaver that permutes the bits between tail and head.

class TurboLikeCode(vertices, name)¶

Bases: lpdec.codes.BinaryLinearBlockCode

Defines a turbo-like code consisting of vertices and arcs as defined above.

matchingPath(source, path, target)¶

Compute the path in target‘s trellis matching path in source‘s trellis.

Both source and target must be encoder vertices. This method only works if both encoders are connected directly to the information source, as in standard turbo codes. The inner encoder of 3D turbo codes, for example, would not be supported.

encodePath(path, encoder)¶

Try to encode the given path in the trellis of EncoderVertex encoder to a codeword.

This will only work if the encoder is directly connected to the information source.

trellisSegmentsOfOutBit(i)¶

Returns those arcs of the trellis graphs in code that define the i-th output bit.

If i is in the systematic part, i.e. a copy of an input bit, the returned list contains a list of arcs for each segments corresponding to that bit – i.e. in the case of a standard turbo code, this would return the “one”-arcs of the i-th segment of trellis1 and the π(i)-th segment of trellis2.

If on the other hand the i-th bit corresponds to a parity bit of some trellis (or termination bits), the returned list has length one, its only element being the list of arcs corresponding to that bit (“parity”-arcs in case of a normal parity bit, “one”-arcs for termination bits).

class StandardTurboCode(encoder, interleaver, name)¶

Bases: lpdec.codes.turbolike.TurboLikeCode

A conventional parallely concatenated turbo code.

The code uses the following encoding scheme:

u −−−+−−−−−−−−−−−−−−−−‣
     |
     +−−−[Encoder1]−−−‣
     |
[Interleaver]
     |
     +−−−[Encoder2]−−−‣

The encoders are terminated. The output is muxed in the following way: [input][enc1 termination][enc1 output (incl. tail)][enc2 termination][enc2 output (incl. tail)] If k is the size of the information word, the blocklength is thus 3*k+4*M, where M is the memory of the encoder.

class LTETurboCode(infolength)¶

Bases: lpdec.codes.turbolike.StandardTurboCode

Turbo code as defined in the 3GPP LTE standard.

class ThreeDTurboCode(K, outerInterleaver, innerInterleaver, name)¶

Bases: lpdec.codes.turbolike.TurboLikeCode

A 3-dimensional turbo code, i.e. a standard turbo code with an additional “patch” encoder.

A part of the output bits of the normal encoders are sent through a smaller third encoder to improve performance.