CECCO::Trellis< T > Struct Template Reference

Trellis with field-labelled edges between consecutive layers. More...

#include <trellises.hpp>

Classes
struct	Viterbi_Workspace
	Workspace for Viterbi decoding on this trellis. More...
struct	BCJR_Workspace
	Workspace for binary BCJR forward-backward decoding. More...

Public Member Functions
Construction
	Trellis ()
	Construct the one-vertex source trellis.
void	add_edge (size_t segment, uint32_t id_from, uint32_t id_to, T value)
	Add one edge in segment segment.
Trellis	operator* (const Trellis &other) const
	Product trellis with componentwise added edge labels.
Information
size_t	get_maximum_depth () const noexcept
	Maximum number of vertices in any layer.
Field Conversion
template<FiniteFieldType U>
Trellis< U >	merge_segments () const
	Merge groups of base-field segments into extension-field labels.

Public Attributes
std::vector< std::vector< details::Vertex< T > > >	V
	Vertices by layer; V[s][i].id == i.
std::vector< std::vector< details::Edge< T > > >	E
	Edges by segment; E[s] connects V[s] to V[s + 1].

Text and TikZ Output
template<typename WS>
std::ostream &	print (std::ostream &os, const WS *ws) const
	Write a segment-by-segment text representation.
std::ostream &	print (std::ostream &os) const
	Write a segment-by-segment text representation without edge costs.
template<typename WS>
void	tikz_header (std::ostream &file) const
	Write TikZ style definitions.
template<typename WS> requires FiniteFieldType<T> && (T::get_size() <= 64)
void	tikz_picture (std::ostream &file, const WS *ws, size_t frontier) const
	Write one TikZ picture of the trellis.
template<typename WS> requires FiniteFieldType<T> && (T::get_size() <= 64)
void	export_as_tikz (const std::string &filename, const WS *ws) const
	Export a standalone TikZ fragment with workspace metrics.
void	export_as_tikz (const std::string &filename) const
	Export a standalone TikZ fragment without workspace metrics.
std::ostream &	operator<< (std::ostream &os, const Trellis &Tr)
	Stream output via print.

Detailed Description

template<FieldType T>
struct CECCO::Trellis< T >

Trellis with field-labelled edges between consecutive layers.

Template Parameters

T	Field type used for edge labels

Vertices are stored by layer in V and edges by segment in E. Segment s connects layer s to layer s + 1. The invariant is V[s][i].id == i; Viterbi and BCJR workspaces index their arrays by edge from_id and to_id.

Use add_edge to build a trellis manually, operator* to form trellis products, and merge_segments to combine several base-field segments into one extension-field segment. Decoders in codes.hpp use the nested workspace types for path metrics and edge costs.

Trellis<Fp<2>> Tr;
Tr.add_edge(0, 0, 0, 0);
Tr.add_edge(0, 0, 1, 1);
size_t depth = Tr.get_maximum_depth();
Tr.export_as_tikz("trellis.tikz");  // for fields of size <= 64

See also

Vector<T> for received words and LLR vectors

FiniteFieldType for TikZ export constraints

Definition at line 130 of file trellises.hpp.

Constructor & Destructor Documentation

Trellis()

template<FieldType T>

CECCO::Trellis< T >::Trellis

(

)

Construct the one-vertex source trellis.

Definition at line 379 of file trellises.hpp.

Member Function Documentation

add_edge()

template<FieldType T>

void CECCO::Trellis< T >::add_edge	(	size_t	segment,
		uint32_t	id_from,
		uint32_t	id_to,
		T	value )

Add one edge in segment segment.

Parameters

segment	Segment index; connects layer segment to segment + 1
id_from	Source vertex id in layer segment
id_to	Target vertex id in layer segment + 1
value	Edge label

Exceptions

std::invalid_argument

if id_from is missing, id_to breaks the id/index invariant, or the edge already exists

Definition at line 384 of file trellises.hpp.

export_as_tikz() [1/2]

template<FieldType T>
requires FiniteFieldType<T> && (T::get_size() <= 64)

void CECCO::Trellis< T >::export_as_tikz

(

const std::string &

filename

)

const

Export a standalone TikZ fragment without workspace metrics.

Parameters

filename

Output filename

Available only for finite fields of size at most 64.

Definition at line 697 of file trellises.hpp.

export_as_tikz() [2/2]

template<FieldType T>
requires FiniteFieldType<T> && (T::get_size() <= 64)

template<typename WS>
requires FiniteFieldType<T> && (T::get_size() <= 64)

void CECCO::Trellis< T >::export_as_tikz	(	const std::string &	filename,
		const WS *	ws ) const

Export a standalone TikZ fragment with workspace metrics.

Parameters

filename	Output filename
ws	Optional decoding workspace; if non-null, metrics and edge costs are shown

Available only for finite fields of size at most 64.

Definition at line 686 of file trellises.hpp.

get_maximum_depth()

template<FieldType T>

size_t CECCO::Trellis< T >::get_maximum_depth ( ) const

noexcept

Maximum number of vertices in any layer.

Definition at line 441 of file trellises.hpp.

merge_segments()

template<FieldType T>

template<FiniteFieldType U>

Trellis< U > CECCO::Trellis< T >::merge_segments

(

)

const

Merge groups of base-field segments into extension-field labels.

Template Parameters

U	Extension field with T ⊆ U

Returns

Trellis over U

Consecutive groups of [U:T] segments are replaced by one segment whose labels are the corresponding U elements. A final incomplete group is zero-padded.

Definition at line 706 of file trellises.hpp.

operator*()

template<FieldType T>

Trellis< T > CECCO::Trellis< T >::operator*

(

const Trellis< T > &

other

)

const

Product trellis with componentwise added edge labels.

Parameters

other

Trellis with the same number of segments

Returns

Trellis whose vertices are pairs of vertices from the operands

Exceptions

std::invalid_argument

if the numbers of segments differ

Definition at line 412 of file trellises.hpp.

print() [1/2]

template<FieldType T>

std::ostream & CECCO::Trellis< T >::print

(

std::ostream &

os

)

const

Write a segment-by-segment text representation without edge costs.

Parameters

os	Output stream

Returns

Output stream

Definition at line 533 of file trellises.hpp.

print() [2/2]

template<FieldType T>

template<typename WS>

std::ostream & CECCO::Trellis< T >::print	(	std::ostream &	os,
		const WS *	ws ) const

Write a segment-by-segment text representation.

Parameters

os	Output stream
ws	Optional workspace; if non-null, edge costs are printed with edge labels

Returns

Output stream

Definition at line 517 of file trellises.hpp.

tikz_header()

template<FieldType T>

template<typename WS>

void CECCO::Trellis< T >::tikz_header

(

std::ostream &

file

)

const

Write TikZ style definitions.

Parameters

file	Output stream

Definition at line 544 of file trellises.hpp.

tikz_picture()

template<FieldType T>
requires FiniteFieldType<T> && (T::get_size() <= 64)

template<typename WS>
requires FiniteFieldType<T> && (T::get_size() <= 64)

void CECCO::Trellis< T >::tikz_picture	(	std::ostream &	file,
		const WS *	ws,
		size_t	frontier ) const

Write one TikZ picture of the trellis.

Parameters

file	Output stream
ws	Optional decoding workspace; if non-null, metrics and edge costs are shown
frontier	Viterbi frontier layer to highlight

Available only for finite fields of size at most 64.

Definition at line 563 of file trellises.hpp.

Friends And Related Symbol Documentation

operator<<

template<FieldType T>

std::ostream & operator<< ( std::ostream & os, const Trellis< T > & Tr )

friend

Stream output via print.

Definition at line 538 of file trellises.hpp.

Member Data Documentation

E

template<FieldType T>

std::vector<std::vector<details::Edge<T> > > CECCO::Trellis< T >::E

Edges by segment; E[s] connects V[s] to V[s + 1].

Definition at line 365 of file trellises.hpp.

V

template<FieldType T>

std::vector<std::vector<details::Vertex<T> > > CECCO::Trellis< T >::V

Vertices by layer; V[s][i].id == i.

Definition at line 363 of file trellises.hpp.

---

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

• trellises.hpp