Layered trellis with field-labelled edges. More...

#include <graphs.hpp>

Classes
struct	Viterbi_Workspace
	Workspace for Viterbi decoding on this trellis. More...
struct	ListViterbi_Workspace
	Workspace for list-output Viterbi decoding on this trellis. More...
struct	BCJR_Workspace
	Workspace for 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.
void	add_parallel_edge (size_t segment, uint32_t id_from, uint32_t id_to, T value)
	Add one edge in segment segment, allowing a parallel edge.
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 >

Layered trellis with field-labelled edges.

Template Parameters

T	Field type used for edge labels

Segment s connects layers s and s + 1. Vertices are stored in V with the invariant V[s][i].id == i; decoding workspaces use these indices for path metrics.

Supports trellis products, segment merging, Viterbi and BCJR workspaces, and text and TikZ export.

Definition at line 167 of file graphs.hpp.

Constructor & Destructor Documentation

◆ Trellis()

template<FieldType T>

CECCO::Trellis< T >::Trellis ( )

Construct the one-vertex source trellis.

Definition at line 476 of file graphs.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 481 of file graphs.hpp.

◆ add_parallel_edge()

template<FieldType T>

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

Add one edge in segment segment, allowing a parallel edge.

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 or id_to breaks the id/index invariant

Unlike add_edge this does not reject an existing (id_from, id_to) edge; use it only where several labels legitimately connect the same two vertices (e.g. the LC-OSD local trellis).

Definition at line 490 of file graphs.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 874 of file graphs.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 863 of file graphs.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 543 of file graphs.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 883 of file graphs.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 514 of file graphs.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 685 of file graphs.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 669 of file graphs.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 696 of file graphs.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 720 of file graphs.hpp.

◆ operator<<

template<FieldType T>

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

friend

Stream output via print.

Definition at line 690 of file graphs.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 472 of file graphs.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 470 of file graphs.hpp.

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

graphs.hpp

Classes

Public Member Functions

Public Attributes

Text and TikZ Output

Detailed Description

Constructor & Destructor Documentation

◆ Trellis()

Member Function Documentation

◆ add_edge()

◆ add_parallel_edge()

◆ export_as_tikz() [1/2]

◆ export_as_tikz() [2/2]

◆ get_maximum_depth()

◆ merge_segments()

◆ operator*()

◆ print() [1/2]

◆ print() [2/2]

◆ tikz_header()

◆ tikz_picture()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ E

◆ V