node can be in the priority queue at the same time this is one of the u201c lazy u201d features of the lazy viterbi decoder for example instead of demanding that all nodes be uniquely stored in the system a test for priority queue membership is traded for a delayed test for trellis membership this choice is advantageous because the check can be avoided altogether if a shadow node is still in the priority queue when the decoder terminates moreover trellis membership is easier to test than priority queue membership as described below the trellis data structure is a sparse matrix the sparse matrix is called sparse because in practice only a small fraction of the trellis nodes are actually expanded the sparse matrix is a matrix because the two indices s and t belong to an interval of integers many sparse matrix representations including a dense matrix could be used to represent the trellis in one embodiment the trellis is implemented as a hash table where the pair s t is the hash key using standard techniques trellis lookup and insertion can be implemented in expected constant time in alternative embodiments the u201c sparse array trick u201d could be employed for.