1. Field of the Invention
This invention relates to a decoder of a convolutional coded data stream. More particularly this invention relates to an improved traceback facility for a Viterbi decoder.
2. Description of the Related Art
Viterbi decoders are important in modern telecommunications, in which digital signals are convolutionally encoded. In a modern application, coded orthogonal frequency division multiplexing ("COFDM") requiring a convolutional code has been proposed in the European Telecommunications Standard DRAFT pr ETS 300 744 (May 1996), which specifies the framing structure, channel coding, and modulation for digital terrestrial television. This standard was designed to accommodate digital terrestrial television within the existing spectrum allocation for analog transmissions, yet provide adequate protection against high levels of co-channel interference and adjacent channel interference. A flexible guard interval is specified, so that the system can support diverse network configurations, while maintaining high spectral efficiency, and sufficient protection against co-channel interference and adjacent channel interference from existing Phase Alternating Line System ("PAL")/Sequential Coleur A'Memorie ("SECAM") services. Two modes of operation are defined: a "2K mode", suitable for single transmitter operation and for small single frequency networks with limited transmitter distances, and an "8K mode". The latter can be used for either single transmitter operation or for large single frequency networks. Various levels of quadrature amplitude modulation ("QAM") are supported, as are different inner code rates, in order to balance bit rate against ruggedness. The system is intended to accommodate a transport layer according to the Moving Picture Experts Group ("MPEG"), and is directly compatible with MPEG-2 coded TV signals (International Organization for Standardization/International Electrotechnical Commission ("ISO/IEC") Specification 13818).
In the noted European Telecommunications Standard data carriers a COFDM frame can be either quadrature phase shift keyed ("QPSK"), 16-QAM, 64-QAM, non-uniform 16-QAM, or non-uniform 64-QAM using Gray mapping.
In the following discussion reference may be to FIG. 1, which illustrates a simplified transition trellis diagram 167 according to a one-step Viterbi decoding process at a coding rate of 1/2, according to convolutional encoding with a constraint length K=3, and a generator polynomial EQU G(x)=(x.sup.2 +x+1, x.sup.2 +1). (1)
The rate 1/2 indicates that for every one bit input, the encoder generates two bits. The constraint length K is the maximum number of signals that can be used to generate an output. Using a transition trellis diagram such as diagram 167, and an incoming data sequence, it is possible to generate an output stream following a sequence of states S. In the diagram 167 a particular state S.sub.t can be represented by two bits. For example, state S.sub.t can assume the value 2 (binary 10), indicated by reference numeral 169. In the representation of diagram 167, in state S.sub.t+1 the bits of state S.sub.t are shifted by one position, and an incoming data bit occupies the rightmost (least significant bit) position. Thus, the state value 169 can legally transition to values 171 and 173 in state S.sub.t+1. For these two transitions, the convolutional encoder will produce values 175 and 177 respectively, indicated more generally as x.sub.t y.sub.t. All possible state transitions can be calculated for the encoder, i.e. given S.sub.t and data bit d.sub.t, the next state S.sub.t+1, x.sub.t and y.sub.t can be evaluated.
The path metric is a measurement of the likelihood that the state is on the original encoder state sequence at that time. The smaller the path metric, the more probable the state is, and vice versa. The branch metric is a measurement of the probability value attached to each branch depending on the input. The branch metric is taken as the Hamming weight, which is the number of differing bits between a received symbol xy.sub.rx and an expected symbol xy along every branch in each transition as shown in FIG. 1. Traceback is the method of going back through the trellis to find the initial state which produced the state with the smallest path metric.
In the preferred embodiment a 2-step decoding process is employed, corresponding to moving through the trellis two steps at a time. This doubles the time to calculate each step, and each traceback yields two bits, rather than one. However the number of calculations required at each state has also doubled, as each state now has four possible paths to be calculated. Only one path is required to be maintained in memory for each state. That path, known as the surviving path, is the one having the smallest path metric and is thus the most likely path.
Puncturing has the effect of producing a higher rate of data transmission, as the code is more efficient. In exemplary Table 2, the convolutional encoder (not shown) encodes data to produce symbols x.sub.t and y.sub.t, which are then punctuated according to the puncturing matrix
x: 1 0 PA1 y: 1 1
to produce x'.sub.t and y'.sub.t, which are then retimed to be transmitted as I,Q in quadrature phase shift keyed modulation. When decoding with punctured data, the omitted bits do not contribute to the branch metric calculation.
TABLE 1 ______________________________________ data d.sub.0 d.sub.1 d.sub.2 d.sub.3 d.sub.4 ______________________________________ xy x.sub.0 y.sub.0 x.sub.1 y.sub.1 x.sub.2 y.sub.2 x.sub.3 y.sub.3 x.sub.4 y.sub.4 x'y' x.sub.0 y.sub.0 y.sub.1 x.sub.2 y.sub.2 y.sub.3 x.sub.4 y.sub.4 IQ x.sub.0 y.sub.0 y.sub.1 x.sub.2 y.sub.2 y.sub.3 x.sub.4 y.sub.4 ______________________________________
In the simple example given above, branch metrics were calculated using the Hamming Weight. Significant improvements result if, instead of receiving either a 1 or 0, we receive a multiple bit representation of each x.sub.rx and y.sub.rx showing the relative likelihood of the signal being a 1 or 0. Thus, in a 16 level (4-bit) soft decoding, a 1 is represented by 15 (binary 1111).
In 16 level decoding, if, for example, xy.sub.rx =(3, 14) are received, the branch metrics may be calculated as shown in Table 2. When calculating new path metrics, the respective path metrics are calculated using these soft-calculated branch metrics, giving significant improvements in decoder performance. In the preferred embodiment, an 8 level (3-bit) soft decoding is used. Traceback is implemented using a systolic array, as explained below in detail.
TABLE 2 ______________________________________ expected xy.sub.rx branch calculation result ______________________________________ 00 0 .vertline.0-3.vertline. + .vertline.0-14.vertline. 17 01 1 .vertline.0-3.vertline. + .vertline.15-14.vertline. 4 10 2 .vertline.15-3.vertline. + .vertline.0-14.vertline. 26 11 3 .vertline.15-3.vertline. + .vertline.15-14.vertline. 13 ______________________________________
In the preferred embodiment, data is convolutionally encoded using a constraint length K=7, which corresponds to a trellis having 64 states. A partial representation of a 2-step transition trellis diagram for this situation is illustrated in FIG. 2.
In the noted European Telecommunications Standard there is an outer Reed-Solomon code, and an inner punctured convolutional code, based on a mother convolutional code of rate 1/2 with 64 states, and having generator polynomials G.sub.1 =171.sub.OCT for X output and G.sub.2 =133.sub.OCT for Y output. In one mode of operation, other punctured rates of 2/3, 3/4, 5/6 and 7/8 are allowed.
During the Viterbi decoding process, traceback requires a substantial amount of processing time and hardware resources. The traceback module in a Viterbi decoder also represents an important production cost.