• Trace
  
  
  • the path marker for the search - essentially defines the path we have taken to the current point in the search
    
    
  • traces are what "move" through the search graph as we search
    
    
  • maintains the total path score for a point in the search
    
    
• History
  
  
  • used by the trace to keep track of its location in the search hierarchy
    
    
  • used for comparison of traces - if two traces have the same history then they are effectively at the same point in the search
    
    
  • the way the history is specified is dependent on the search mode (network decoding vs. N-symbol decoding)