File conv_core.h¶

FileList > conv > conv_core.h

Convolutional codes: the code description, the encoder, and the maximum-likelihood decoder that reads the same description. More...

#include "clib_common.h"
#include "dp_state.h"
#include <stddef.h>
#include <stdint.h>

Classes¶

Type	Name
struct	conv_code_t A rate-1/n convolutional code.
struct	conv_enc_t Encoder state: the shift register, and nothing else.

Public Functions¶

Type	Name
int	conv_code_valid (const conv_code_t * c) Is `c` a code this file can represent?
void	conv_enc_init (conv_enc_t * s) Reset the encoder to the all-zero state.
size_t	conv_encode (conv_enc_t * s, const conv_code_t * c, const uint8_t * in, size_t n_in, uint8_t * out, size_t max_out) Encode `n_in` bits, emitting`n_in * c->n` symbols.
JM_FORCEINLINE uint32_t	conv_next_state (const conv_code_t * c, uint32_t state, unsigned bit) The state reached from `state` on`bit` .
unsigned	conv_outputs (const conv_code_t * c, uint32_t state, unsigned bit) The output word for one branch — the expression of the code.
JM_FORCEINLINE uint32_t	conv_states (const conv_code_t * c) Number of trellis states, `2^(k-1)` .

Macros¶

Type	Name
define	CONV_K_MAX `9` Largest constraint length; 2^(k-1) states, so 256 at k = 9.
define	CONV_N_MAX `6` Largest number of outputs per input bit (rate 1/n).

Detailed Description¶

A rate-1/n convolutional code is four numbers — a constraint length, an output count, a generator polynomial per output, and which outputs are inverted. This file holds that description once and derives everything from it, so an encoder and a decoder cannot disagree about what the code is.

The one expression¶

conv_outputs is what the family of codes emits, and it is the only place that says so. conv_encode calls it to produce symbols; a Viterbi decoder calls it to build the trellis it searches. An encoder that computed the outputs and a decoder that computed them again would be two implementations of one primitive, and the detail that drifts between them is never the arithmetic — it is a convention.

CCSDS is the worked example and the warning: 131.0-B-3 inverts the second output and most codes invert nothing. Omitting that inversion produces a code that decodes its own output perfectly and interoperates with nothing; measured on the CCSDS code, a decoder that omits it gets 39.2 % of bits wrong. As a field of conv_code_t the mistake is a wrong argument. As a constant inside an encoder it is a wrong encoder, and the matching decoder hides it.

Nothing here is CCSDS¶

The CCSDS configuration lives in ccsds_tm/ccsds_tm.h as CCSDS_TM_CONV, because a channel-coding standard picking a code is not the same fact as the code existing. Point this at the deep-space rate-1/6 code, at a K = 9 experiment, or at whatever a caller brings — the trellis is identical and only the table changes.

Conventions¶

Bits are unpacked, one per byte in the LSB, matching wfm_frame_bits, dp_crc16_ccitt and the ccsds_tm kernels.
The register holds the newest input in the high stage: reg = (reg >> 1) | (b << (k-1)). A state is the k-1 bits that survive, so state + bit -> reg = (bit << (k-1)) | state, and the next state is reg >> 1. Deriving this the other way round yields a trellis that is perfectly self-consistent and decodes nothing a conforming encoder produced, which is why test_conv_core.c pins the two against each other rather than each against itself.
Polynomials are written as the standard writes them, left to right with the newest input at the left: CCSDS's G1 = 1111001 is 0171.

See also: docs/design/viterbi.md for the decoder's design and its measurements.

Public Functions Documentation¶

function conv_code_valid¶

Is c a code this file can represent?

int conv_code_valid (
    const conv_code_t * c
)

Parameters:

c The code.

Returns:

Non-zero if usable: k in [2, CONV_K_MAX], n in [1, CONV_N_MAX], and every polynomial within k bits and non-zero. A zero polynomial is an output that carries no information, which is a typo rather than a code.

function conv_enc_init¶

Reset the encoder to the all-zero state.

void conv_enc_init (
    conv_enc_t * s
)

function conv_encode¶

Encode n_in bits, emittingn_in * c->n symbols.

size_t conv_encode (
    conv_enc_t * s,
    const conv_code_t * c,
    const uint8_t * in,
    size_t n_in,
    uint8_t * out,
    size_t max_out
)

Parameters:

s Encoder state, carried across calls.
c The code.
in n_in unpacked input bits.
n_in Number of input bits.
out Receives n_in * c->n unpacked symbols, outputs in polynomial order per input bit.
max_out Capacity of out.

Returns:

Symbols written, or 0 if the code is invalid or max_out is too small — in which case out is untouched.

function conv_next_state¶

The state reached from state onbit .

JM_FORCEINLINE uint32_t conv_next_state (
    const conv_code_t * c,
    uint32_t state,
    unsigned bit
)

function conv_outputs¶

The output word for one branch — the expression of the code.

unsigned conv_outputs (
    const conv_code_t * c,
    uint32_t state,
    unsigned bit
)

Output j is bit j of the result, matching the order the polynomials are given in and the order conv_encode emits them — so for CCSDS, bit 0 is C1 and bit 1 is C2.

Parameters:

c The code.
state Trellis state: the k-1 previous input bits.
bit The new input bit (0 or 1).

Returns:

n bits, output j in bit j, inversion applied.

function conv_states¶

Number of trellis states, 2^(k-1) .

JM_FORCEINLINE uint32_t conv_states (
    const conv_code_t * c
)

Macro Definition Documentation¶

define CONV_K_MAX¶

Largest constraint length; 2^(k-1) states, so 256 at k = 9.

#define CONV_K_MAX `9`

define CONV_N_MAX¶

Largest number of outputs per input bit (rate 1/n).

#define CONV_N_MAX `6`

The documentation for this class was generated from the following file native/inc/conv/conv_core.h