Trellis decoder for decoding data stream including symbols coded with multiple convolutional codes
View Patent ↗A trellis decoder decodes a stream of encoded symbols, including symbols of a first type (e.g. symbols encoded with a first trellis code) and symbols of a second type (e.g. encoded with a second, more robust, trellis code), without storing path indicators along a trellis for symbols of the first type. In this way, limited memory may be used to store path indicators along the trellis for symbols of the second type. This allows for more accurate decoding of the symbols of the second type. For transitions from symbols of the second type to symbols of the first type, states of the trellis decoder may be stored. In this way, paths may be traced back along the trellis for trellis decoding, without the path indicators for the symbols of the first type.
1. A method of trellis decoding a symbol stream comprising symbols of a first type and symbols of a second type, symbols of the first type are encoded using a first convolutional code and symbols of the second type are encoded using a second convolutional code, the method comprising:
for symbols of the first type, storing a plurality of states along each path of a trellis based on a comparison of incremental error metrics and storing an additional plurality of states along each path of a phase inverted trellis;
for symbols of the second type, storing a plurality of path indicators along each path of the trellis and storing an additional plurality of path indicators along each path of the phase inverted trellis, wherein path indicators are associated with each leg of each path; and
tracing back along a candidate path to decode a symbol according to the plurality of states, the plurality of path indicators, the additional plurality of states and the additional plurality of path indicators.
2. The method of claim 1 , comprising choosing the symbol according to the plurality of additional states and the plurality of additional path indicators or the plurality of states and the plurality of path indicators.
3. The method of claim 2 , wherein choosing comprises:
finding a first maximum likelihood path for a portion of the symbol stream along a first trellis;
finding a second maximum likelihood path for the portion of the symbol stream along a second trellis.
4. The method of claim 3 , comprising decoding the symbol using the first maximum likelihood path if the first maximum likelihood path has less error than the second maximum likelihood path.
5. A trellis decoder for decoding symbols in a symbol stream comprising symbols of a first type and symbols of a second type, the symbols of the first type are encoded using a first convolutional code and the symbols of the second type are encoded using a second convolutional code, the trellis decoder comprising:
a path metric calculator operable to calculate an incremental error metric for legs of at least two arriving paths for each state of the trellis decoder and operable to calculate a minimum incremental error metric for the at least two arriving paths for each state;
a path memory operable to store a path indicator of each leg of each path associated with the minimum incremental error for states along a trellis for arriving symbols of the second type,
the path memory operable to store states along each path of the trellis for arriving symbols of the first type that arrive immediately prior to symbols of the second type;
a path trace-back calculator operable to decode a symbol of the second type according to the path indicators and the states; and
a multiplexer operable to multiplex outputs of the trace-back calculator with place holders corresponding to symbols of the first type.
6. The trellis decoder of claim 5 , wherein the path metric calculator is operable to calculate a path error metric for a path through each state of the trellis decoder along a phase inverted trellis including a previous path error metric for that path and the minimum incremental error metric for at least two arriving paths for each state, the trellis decoder further comprising:
path metric registers for storing path metrics for each state along the phase inverted trellis; and
path memory operable to store a path indicator of each leg of each path associated with the minimum incremental error for that state along the phase inverted trellis, for arriving symbols of the second type, the path memory operable to store states of the trellis decoder along each of the paths of the phase inverted trellis for arriving symbols of the first type, arriving immediately prior to symbols of the second type along each of the paths.