The Stack Decoding class with node+edge combination. More...

#include <CC_StackDecoding.h>

Inheritance diagram for ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >:

Collaboration diagram for ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >:

Public Member Functions
	CC_StackDecoding (const std::vector< unsigned int > &constraints, const std::vector< std::vector< T_Register > > &genpoly_representations)
virtual	~CC_StackDecoding ()
void	reset ()
float	get_stack_score () const
unsigned int	get_stack_size () const
virtual bool	decode (const CC_ReliabilityMatrix &relmat, std::vector< T_IOSymbol > &decoded_message)
virtual void	print_stats (std::ostream &os, bool success)
virtual void	print_dot (std::ostream &os)
Protected Types
typedef CC_SequentialDecoding < T_Register, T_IOSymbol >	Parent
	Parent class this class inherits from.
typedef CC_SequentialDecodingInternal < T_Register, T_IOSymbol, CC_TreeNodeEdgeTag_Empty >	ParentInternal
	Parent class this class inherits from.
typedef CC_TreeNodeEdge < T_IOSymbol, T_Register, CC_TreeNodeEdgeTag_Empty >	StackNodeEdge
	Class of code tree nodes in the stack algorithm.
Protected Member Functions
virtual void	visit_node_forward (CC_TreeNodeEdge< T_IOSymbol, T_Register, CC_TreeNodeEdgeTag_Empty > *node_edge, const CC_ReliabilityMatrix &relmat)
void	remove_node_from_stack (StackNodeEdge *node_edge)
Protected Attributes
std::map< NodeEdgeOrdering, StackNodeEdge *, std::greater < NodeEdgeOrdering > >	node_edge_stack
	Ordered stack of node+edge combos by decreasing path metric.

Detailed Description

template<typename T_Register, typename T_IOSymbol>
class ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >

The Stack Decoding class with node+edge combination.

Template Parameters:

T_Register	Type of the encoder internal registers
T_IOSymbol	Type of the input and output symbols

Member Typedef Documentation

template<typename T_Register , typename T_IOSymbol >

typedef CC_SequentialDecoding<T_Register, T_IOSymbol> ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::Parent [protected]

Parent class this class inherits from.

template<typename T_Register , typename T_IOSymbol >

typedef CC_SequentialDecodingInternal<T_Register, T_IOSymbol, CC_TreeNodeEdgeTag_Empty> ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::ParentInternal [protected]

Parent class this class inherits from.

template<typename T_Register , typename T_IOSymbol >

typedef CC_TreeNodeEdge<T_IOSymbol, T_Register, CC_TreeNodeEdgeTag_Empty> ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::StackNodeEdge [protected]

Class of code tree nodes in the stack algorithm.

Constructor & Destructor Documentation

template<typename T_Register , typename T_IOSymbol >

ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::CC_StackDecoding	(	const std::vector< unsigned int > &	constraints,
		const std::vector< std::vector< T_Register > > &	genpoly_representations
	)		`[inline]`

Constructor

Parameters:

constraints Vector of register lengths (constraint length + 1). The number of elements determines k.

genpoly_representations Generator polynomial numeric representations. There are as many elements as there are input bits (k). Each element is itself a vector with one polynomial value per output bit. The smallest size of these vectors is retained as the number of output bits n. The input bits of a symbol are clocked simultaneously into the right hand side, or least significant position of the internal registers. Therefore the given polynomial representation of generators should follow the same convention.

                                                                              :
                CC_SequentialDecoding<T_Register, T_IOSymbol>(constraints, genpoly_representations),
                CC_SequentialDecodingInternal<T_Register, T_IOSymbol, CC_TreeNodeEdgeTag_Empty>()
    {}

template<typename T_Register , typename T_IOSymbol >

virtual ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::~CC_StackDecoding ( ) [inline, virtual]

Destructor. Does a final garbage collection

{}

Member Function Documentation

template<typename T_Register , typename T_IOSymbol >

virtual bool ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::decode	(	const CC_ReliabilityMatrix &	relmat,
		std::vector< T_IOSymbol > &	decoded_message
	)		`[inline, virtual]`

Decodes given the reliability matrix

Parameters:

relmat	Reference to the reliability matrix
decoded_message	Vector of symbols of retrieved message

Implements ccsoft::CC_SequentialDecoding< T_Register, T_IOSymbol >.

    {
        if (relmat.get_message_length() < Parent::encoding.get_m())
        {
            throw CCSoft_Exception("Reliability Matrix should have a number of columns at least equal to the code constraint");
        }

        if (relmat.get_nb_symbols_log2() != Parent::encoding.get_n())
        {
            throw CCSoft_Exception("Reliability Matrix is not compatible with code output symbol size");
        }

        reset();
        ParentInternal::init_root(); // initialize the root node
        Parent::node_count++;
        visit_node_forward(ParentInternal::root_node, relmat); // visit the root node

        // loop until we get to a terminal node or the metric limit is encountered hence the stack is empty
        while ((node_edge_stack.size() > 0)
            && (node_edge_stack.begin()->second->get_depth() < relmat.get_message_length() - 1))
        {
            StackNodeEdge* node = node_edge_stack.begin()->second;
            //std::cout << std::dec << node->get_id() << ":" << node->get_depth() << ":" << node_stack.begin()->first.path_metric << std::endl;
            visit_node_forward(node, relmat);

            if ((Parent::use_node_limit) && (Parent::node_count > Parent::node_limit))
            {
                std::cerr << "Node limit exhausted" << std::endl;
                return false;
            }
        }

        // Top node has the solution if we have not given up
        if (!Parent::use_metric_limit || node_edge_stack.size() != 0)
        {
            //std::cout << "final: " << std::dec << node_stack.begin()->second->get_id() << ":" << node_stack.begin()->second->get_depth() << ":" << node_stack.begin()->first.path_metric << std::endl;
            ParentInternal::back_track(node_edge_stack.begin()->second, decoded_message, true); // back track from terminal node to retrieve decoded message
            Parent::codeword_score = node_edge_stack.begin()->first.path_metric; // the codeword score is the path metric
            return true;
        }
        else
        {
            std::cerr << "Metric limit encountered" << std::endl;
            return false; // no solution
        }
    }

Here is the call graph for this function:

template<typename T_Register , typename T_IOSymbol >

float ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::get_stack_score ( ) const [inline]

Get the score at the top of the stack. Valid anytime the process has started (stack not empty).

    {
        return node_edge_stack.begin()->first.path_metric;
    }

template<typename T_Register , typename T_IOSymbol >

unsigned int ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::get_stack_size ( ) const [inline]

Get the stack size

    {
        return node_edge_stack.size();
    }

template<typename T_Register , typename T_IOSymbol >

virtual void ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::print_dot ( std::ostream & os ) [inline, virtual]

Print the dot (Graphviz) file of the current decode tree to an output stream

Parameters:

os	Output stream

Implements ccsoft::CC_SequentialDecoding< T_Register, T_IOSymbol >.

    {
        ParentInternal::print_dot_internal(os);
    }

Here is the call graph for this function:

template<typename T_Register , typename T_IOSymbol >

virtual void ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::print_stats	(	std::ostream &	os,
		bool	success
	)		`[inline, virtual]`

Print stats to an output stream

Parameters:

os	Output stream
success	True if decoding was successful

Implements ccsoft::CC_SequentialDecoding< T_Register, T_IOSymbol >.

    {
        std::cout << "score = " << Parent::get_score()
                << " stack_score = " << get_stack_score()
                << " #nodes = " << Parent::get_nb_nodes()
                << " stack_size = " << get_stack_size()
                << " max depth = " << Parent::get_max_depth() << std::endl;
        std::cout << "_RES " << (success ? 1 : 0) << ","
                << Parent::get_score() << ","
                << get_stack_score() << ","
                << Parent::get_nb_nodes() << ","
                << get_stack_size() << ","
                << Parent::get_max_depth() << std::endl;
    }

Here is the call graph for this function:

template<typename T_Register , typename T_IOSymbol >

void ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::remove_node_from_stack ( StackNodeEdge * node_edge ) [inline, protected]

Removes a node from the stack map. Does a full scan but usually the nodes to be removed are on the top of the stack (i.e. beginning of the map).

    {
        typename std::map<NodeEdgeOrdering, StackNodeEdge*, std::greater<NodeEdgeOrdering> >::iterator stack_it = node_edge_stack.begin();

        for (; stack_it != node_edge_stack.end(); ++stack_it)
        {
            if (node_edge == stack_it->second)
            {
                node_edge_stack.erase(stack_it);
                break;
            }
        }
    }

template<typename T_Register , typename T_IOSymbol >

void ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::reset ( ) [inline]

Reset the decoding process

Reimplemented from ccsoft::CC_SequentialDecoding< T_Register, T_IOSymbol >.

    {
        ParentInternal::reset();
        Parent::reset();
        node_edge_stack.clear();
    }

Here is the call graph for this function:

template<typename T_Register , typename T_IOSymbol >

virtual void ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::visit_node_forward	(	CC_TreeNodeEdge< T_IOSymbol, T_Register, CC_TreeNodeEdgeTag_Empty > *	node_edge,
		const CC_ReliabilityMatrix &	relmat
	)		`[inline, protected, virtual]`

Visit a new node Node+edge combo to visit Reliability matrix being used

Implements ccsoft::CC_SequentialDecodingInternal< T_Register, T_IOSymbol, CC_TreeNodeEdgeTag_Empty >.

    {
        int forward_depth = node_edge->get_depth() + 1;
        T_IOSymbol out_symbol;
        T_IOSymbol end_symbol;

        // return encoder to appropriate state
        if (node_edge->get_depth() >= 0) // does not concern the root node
        {
            Parent::encoding.set_registers(node_edge->get_registers());
        }

        if ((Parent::tail_zeros) && (forward_depth > relmat.get_message_length()-Parent::encoding.get_m()))
        {
            end_symbol = 1; // if zero tail option assume tail symbols are all zeros
        }
        else
        {
            end_symbol = (1<<Parent::encoding.get_k()); // full scan all possible input symbols
        }

        // loop through assumption for this symbol place
        for (T_IOSymbol in_symbol = 0; in_symbol < end_symbol; in_symbol++)
        {
            Parent::encoding.encode(in_symbol, out_symbol, in_symbol > 0); // step only for a new symbol place
            float edge_metric = ParentInternal::log2(relmat(out_symbol, forward_depth)) - Parent::edge_bias;

            float forward_path_metric = edge_metric + node_edge->get_path_metric();
            if ((!Parent::use_metric_limit) || (forward_path_metric > Parent::metric_limit))
            {
                StackNodeEdge *next_node_edge = new StackNodeEdge(Parent::node_count, node_edge, in_symbol, edge_metric, forward_path_metric, forward_depth);
                next_node_edge->set_registers(Parent::encoding.get_registers());
                node_edge->add_outgoing_node_edge(next_node_edge); // add forward edge+node combo
                node_edge_stack[NodeEdgeOrdering(forward_path_metric, Parent::node_count)] = next_node_edge;
                //std::cout << "->" << std::dec << node_count << ":" << forward_depth << " (" << (unsigned int) in_symbol << "," << (unsigned int) out_symbol << "): " << forward_path_metric << std::endl;
                Parent::node_count++;
            }
        }

        Parent::cur_depth = forward_depth; // new encoder position

        if (Parent::cur_depth > Parent::max_depth)
        {
            Parent::max_depth = Parent::cur_depth;
        }

        if (node_edge->get_depth() >= 0)
        {
            remove_node_from_stack(node_edge); // remove current node from the stack unless it is the root node which is not in the stack
        }
    }

Here is the call graph for this function:

Member Data Documentation

template<typename T_Register , typename T_IOSymbol >

std::map<NodeEdgeOrdering, StackNodeEdge*, std::greater<NodeEdgeOrdering> > ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >::node_edge_stack [protected]

Ordered stack of node+edge combos by decreasing path metric.

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

/shared/development/google_code/rssoft/libccsoft/lib/CC_StackDecoding.h

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<typename T_Register, typename T_IOSymbol> class ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T_Register, typename T_IOSymbol>
class ccsoft::CC_StackDecoding< T_Register, T_IOSymbol >