WO2011046529A1

WO2011046529A1 - Map decoder architecture for a digital television trellis code

Info

Publication number: WO2011046529A1
Application number: PCT/US2009/005577
Authority: WO
Inventors: Ivonete Markman; Wen Gao
Original assignee: Thomson Licensing SAS
Current assignee: Thomson Licensing SAS
Priority date: 2009-10-13
Filing date: 2009-10-13
Publication date: 2011-04-21
Anticipated expiration: 2012-04-13

Abstract

An apparatus for decoding interleaved trellis-encoded digital data includes a metric generator unit that outputs alpha metrics and beta metrics corresponding to each symbol of interleaved trellis-encoded data groups, an alpha unit that inputs the alpha metrics and outputs accumulated alpha state metrics for each trellis encoded data group, a beta unit that inputs the beta metrics and outputs accumulated beta state metrics for each trellis encoded data group, and a log likelihood ratio unit that computes output values corresponding to the digital data using the accumulated alpha state metrics and accumulated beta state metrics. The decoding apparatus incorporates only one set of the metric generator, the alpha unit, the beta unit, and the log likelihood unit to decode information from the plurality of interleaved trellis encoders instead of using a plurality of separate trellis decoders.

Description

MAP DECODER ARCHITECTURE FOR A DIGITAL TELEVISION TRELLIS CODE

FIELD

[0001] The present invention relates to digital signal decoding and more specifically to a compact architecture for a maximum a posteriori (MAP) decoder for a digital television (DTV) trellis coded _.television signal.

BACKGROUND

[0002] The Advanced Television Systems Committee (ATSC) standard for Digital

Television (DTV) in the United States requires an 8-Vestigial SideBand (VSB) transmission system which includes Forward Error Correction (FEC) as a means of improving the system performance. The FEC system consists of a Reed-Solomon encoder, followed by a byte interleaver, and a trellis encoder on the transmitter side. At the receiver end, there is a corresponding trellis decoder, byte deinterleaver and Reed-Solomon decoder. The ATSC- DTV standard is document A53.doc, dated September 16, 1995 produced by the United States Advanced Television Systems Committee. Figure 1 shows a simplified block diagram of the DTV transmitter and receiver, emphasizing the FEC system.

[0003] The ATSC DTV transmission scheme is not robust enough against Doppler shift and multipath radio interference, and is designed for highly directional fixed antennas, hindering the provision of expanded services to customers utilizing mobile and handheld devices. To overcome these issues, and create a more robust and more flexible system, among other things, it is possible to add a new layer of FEC coding, and more powerful decoding algorithms to decrease the Threshold of Visibility (TOV).

[0004] The added layer of FEC coding can require decoding techniques such as turbo decoding discussed in an article by C. Berrou, A. Glavieux and P. Thitimajshima, entitled "Near Shannon Limit Error - Correcting Coding and Decoding: Turbo-Codes", found in Proceedings of the IEEE International Conference on Communications - ICC'93, May 23- 26, 1993, Geneva, Switzerland, pp. 1064-1070. Another turbo code discussion can be found in the article by M. R. Soleymani, Y. Gao and U. Vilaipornsawai, entitled "Turbo Coding for Satellite and Wireless Communications", Kluwer Academic Publishers, USA, 2002.

[0005] Hence, decoding of signals encoded for ATSC DTV with an added FEC layer can involve trellis decoding algorithms like maximum a posteriori (MAP) decoders as described by L.R. Bahl, J. Cocke, F. Jelinek and J. Raviv, in an article entitled "Optimal Decoding of Liner Codes for Minimizing Symbol Error Rate", found in IEEE Transactions on

Information Theory, Vol. IT-20, No. 2, March 1974, pp. 284-287. Another discussion of trellis codes and a MAP decoder is found in an article written by A.J. Viterbi, entitled "An Intuitive Justification and a Simplified Implementation of the MAP Decoder for

Convolutional Codes", found in IEEE Journal on Selected Areas in Communications, Vol. 16, No. 2, February 1998, pp. 260-264.

[0006] The trellis code employed in the ATSC-DTV standard is a rate 2/3 trellis coded modulation (TCM) code. This code is implemented by coding one bit using a rate ½, 4-state convolutional encoder, and adding an FEC uncoded bit which is differentially precoded. Each set of three coded bits out of the encoder is mapped to an 8-VSB modulator symbol.

[0007] Figure 2 shows a block diagram of the differential precoder, trellis encoder and corresponding 8-VSB symbol mapper. Furthermore, a twelve intrasegment interleaving is employed whereby 12 identical encoders and precoders are sequentially used, processing each a byte at a time, and transmitting each a symbol at a time. In addition, a skip of four encoders/precoders is performed every segment sync.

[0008] Figures 3 and 4 show the 12-encoder interleaving and corresponding 12-decoder deinterleaving, respectively. The reason for the 12-encoder interleaving came from the need to eliminate possible National Television Standard Committee (NTSC) co-channel interference, which coexisted with HDTV for a number of years.

[0009] In the instance of the ATSC trellis code depicted in Figures 2 and 3, the MAP decoder can be used to obtain the soft output of the decision bit-pair (two bits per trellis branch), which is the a posteriori probability (APP) of the decision bit-pair, or equivalently, of the TCM code output symbols. Since the ATSC-DTV trellis code is a composite of 12 interleaved trellis codes, as shown in Figure 3, a straightforward MAP decoder design would replicate the MAP decoder twelve times, as shown in Figure 4. In addition the trellis deinterleaving operation must take into account the skipping of 4 decoders every segment sync, according to the ATSC-DTV standard.

[0010] However, the straightforward approach shown in Figure 4 is hardware intensive and therefore expensive to build in terms of resources such as integrated circuit area and commensurate power consumption. An alternative approach is sought by the inventors.

SUMMARY [0011] The ATSC-DTV standard employs a trellis code with twelve intrasegment interleaving whereby twelve identical encoders and corresponding decoders are sequentially used. In one embodiment, an area-efficient MAP decoder architecture that uses one instead of twelve sets of decoder components is used for an iterative (turbo) decoding FEC system in a mobile ATSC-DTV standard based on the original DTV standard.

[0012] In one embodiment, an apparatus is defined for decoding an input of digital data that is encoded using a plurality of interleaved trellis encoders where each trellis encoder provides a trellis encoded data group for interleaving. The apparatus includes a metric generator unit that outputs metrics corresponding to each symbol of the interleaved trellis- encoded data groups where the metrics include alpha and beta metrics, an alpha unit that inputs the alpha metrics and outputs accumulated alpha state metrics for each trellis encoded data group; a beta unit that inputs the beta metrics and outputs accumulated beta state metrics for each trellis encoded data group; and a log likelihood ratio unit that computes output values corresponding to the digital data using the accumulated alpha state metrics and accumulated beta state metrics. The decoding apparatus is characterized by its feature of using only one set of the metric generator, the alpha unit, the beta unit, and the log likelihood unit to decode information from the plurality of interleaved trellis encoder instead of using 12 sets of decoding components. In addition, the sequence in which the various alpha and beta metrics are processed permit synchronized operations that allows a forward time ordered output of data representing the interleaved trellis-encoded data input stream. The consolidated decoder design may be extended to a general number M of interleaved codes, and also to codes of a different generator matrix than the ATSC-DTV standard.

[0013] Additional features and advantages of the invention are apparent from the following detailed description of illustrative embodiments which proceeds with reference to the accompanying figures.

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] Figure 1 depicts an example block diagram of a digital television transmitter and receiver system;

Figure 2 depicts an example trellis encoder, differential precoder, and symbol mapper for a transmitter in a digital television system;

Figure 3 depicts an example twelve stage trellis encoder and interleaver for a digital television transmitter; Figure 4 depicts an example twelve stage trellis decoder and deinterleaver for a digital television receiver;

Figure 5 depicts an example digital television data frame;

Figure 6 depicts an example digital television field synchronization structure;

Figure 7 depicts an example architecture for a MAP decoder in a digital television receiver according to aspects of the invention;

Figure 8 is a table depicting the data processing blocks in time as processed by MAP decoder units according to aspects of the invention;

Figure 9 depicts the data block relationship between processing units in an example MAP decoder according to aspects of the invention;

Figure 10 depicts data processing block in processing units of a MAP decoder according to aspects of the invention;

Figure 11 depicts an example block diagram of a consolidated trellis decoder deinterleaver architecture according to aspects of the invention;

Figure 12 depicts a metric generator unit block diagram in a MAP decoder using aspects of the invention;

Figure 13 depicts a first (alpha) processing unit block diagram in a MAP decoder using aspects of the invention;

Figure 14 depicts a second (beta) processing unit in a MAP decoder using aspects of the invention; and

Figure 15 depicts a third (log likelihood) processing unit in a MAP decoder using aspects of the invention.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0015] As discussed above, Figure 1 shows one prior art architecture for a DTV system which incorporates forward error correction. Here, input digital data, which may be considered any of video, audio, textual, or other information data, is encoded using a DTV standard and transmitted to a receiver which decodes the digital data. Of particular interest is the decoding system which includes a trellis decoding function in the receiver chain. Figure 2 depicts the precoder, trellis encoding, and symbol mapper of a DTV transmitter. Figure 3 depicts an existing system used on the transmission side showing the 12 interleaved stages of the Figure 2 precoder and trellis encoder function followed by a mapper which accepts the trellis encoded output symbols. A straightforward decoder for such a system is depicted in figure 4 which shows the need for 12 deinterleaved trellis decoders in order to decode the transmission stream produced by the encoder of Figure 3.

[0016] In one aspect of the present invention, an area-efficient MAP decoder architecture for the ATSC-DTV trellis code can be achieved by merging the design of the 12 trellis decoders of Figure 4 and reusing blocks of a MAP decoder architecture, instead of replicating the design of each of the 12 decoders. This architecture is suitable for an iterative (turbo) decoding FEC system in a mobile ATSC-DTV standard based on the original DTV standard.

[0017] Considering the ATSC-DTV standard, Figure 5 shows how the DTV data are organized for transmission. Each data frame consists of two data fields, each containing 313 data segments. The first data segment of each data field is a unique synchronizing signal (data field sync) as shown in Figure 6, including several pseudo random (PN) sequences. The remaining 312 data segments each carry the equivalent of the data from one 188-byte transport packet plus its associated FEC overhead. Each data segment consists of 832 8-VSB symbols. The first 4 symbols are transmitted in binary form and provide segment synchronization, as also shown in Figure 6 (values of: +5, -5, -5, +5). This data segment sync signal also represents the sync byte of the 188-byte MPEG-compatible transport packet. The remaining 828 symbols of each data segment carry data equivalent to the remaining 187 bytes of a transport packet and its associated FEC overhead.

[0018] The maximum a posteriori (MAP) decoding algorithm for convolutional codes was proposed over three decades ago by Bahl et al., but only got increased attention over a decade ago as an iterative soft-output decoder for the class of turbo codes discovered by Berrou et al. Although more complex than the maximum likelihood decoder algorithm proposed by Viterbi, the MAP decoder proposed by Bahl et al. minimizes the probability of symbol error, therefore accomplishing acceptable performance within Signal-to-Noise (SNR) levels of ldB of the Shannon capacity values in iterative decoding systems. In particular, sub-optimum versions of the MAP algorithm, like the max-log-MAP algorithm with a correction factor for the max operation (also called log-MAP algorithm), represent a drastic reduction in computational complexity for a small degradation in the order of tenths of a dB, hence being favored for practical implementations. This is discussed in an article by M. R. Soleymani, Y. Gao and U. Vilaipornsawai, entitled "Turbo Coding for Satellite and Wireless Communications", Kluwer Academic Publishers, USA, 2002. Sub-optimal decoding is presented by Robertson, E. Villebrun and P. Hoeher, in an article entitled "A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain", found in the Proceedings of the IEEE International Conference on Communications - ICC'95, Seattle, WA, 1995, pp. 1009-1013.

[0019] The most basic implementation of the MAP decoder sees the algorithm as a dual- maxima computation combined with forward (alpha) and backward (beta) recursions of the Viterbi algorithm computations. Figure 7 shows a simplified block diagram of the MAP decoder. In the case of the ATSC trellis code, the MAP decoder can be used to obtain the soft output of the decision bit-pair (two bits per trellis branch), which is the a posteriori probability (APP) of the decision bit-pair, or equivalently, of the TCM code output symbols. Thus, the functional blocks of Figure 7 are normally duplicated 12 times in order to achieve the DTV trellis decoder depicted in Figure 4.

[0020] Referring to Figure 7, the metric generator unit consists of the channel metric (rri_c) computation for each 8-VSB input symbol (r), which may be given by:

where k> 1 is the symbol period; σ² is the noise variance and c,, for i = 0, 1 ... 7, are the 8 possible TCM symbols. The channel metrics (ni_c) are then stored for a size of two processing blocks. This processing block, L_pb, is equivalent to the traceback latency of a Viterbi decoder in symbols.

[0021] The metric generator unit also stores the apriori metric (m_apr) received from a previous iteration for a size of two processing blocks. The apriori metrics m_apr(k, j) is given by: m apr fr ) = -^log M_k = j)) (¾ where k > 1 is the symbol period; log(.) is the logarithm function; P(.) is the probability; I_k is the bit-pair at time k and j= 0, 1,2,3, represents the four bit-pair values.

[0022] The metric generator must then send the nic and m_apr stored values to the

corresponding alpha (forward processing) and beta (backward processing) units. The alpha values (airi_c and am_apr) are sent in a first in first out (FIFO) mode, while the beta (brri_c and bm_apr) values are sent in a last in first out (LIFO) mode.

[0023] Figure 8 presents a table depicting the ordering of received data processing blocks (L_p ) numbered in time (p_w), and the respective alpha and beta metrics and accumulated metrics, as well as the LLR calculations. The arrows indicate the latency of processing the first data processing block within the decoder. Observe that the alpha and beta metrics calculated inside the metric generator unit have a latency of 2 L_pb symbols with respect to the MAP decoder input.

[0024] The alpha unit is a modified forward Viterbi decoder which computes the forward state metrics as follows:

[0025]

A{k) = min* (A{k - l) + am_c {k, S_k__i→S_k ) + am_apr {k, S_k__i→S_k )) (3) where k > 1 is the symbol period; min*(.) is the min_star_sum operation, which is performed for all states S_k__} that transit to a given state S_k ; A(k-l) is the alpha accumulated metric at time period k-1, which initial value A(0) = 0; am_c(k, S_k__l→S_k ) is the alpha channel metric associated with the particular state transition in the TCM trellis, chosen to be a particular am_c(k,i) value, when i is the 8-VSB symbol index associated with the trellis state transition ( S_k__l→S_k ) and am_apr(k, S_k_₁→S_k ) is the alpha apriori metric associated with the particular state transition in the TCM trellis, chosen to be a particular am_c(k,j) value, where j is the dual-bit index associated with the trellis state transition ( S_k__{→ S_k ).

[0026] A min_star_sum operation is defined as follows:

min (x_l ,x₂,...,x_N ) = - log(e^'Xl + e^~Xl + ... + e^'x" ) (4) For N=2, we have the following simple formula:

min' ^ ^ -logCe^"*' + e^~Xl ) = min(x,,x₂) - log(l + e^{~ ~xA}) (5) Note that this function can be reduced to finding the minimum of two numbers and adding a (log) correction factor, which can be implemented using a very small look-up table. In addition, equation 5 may be recursively calculated to compute equation 4.

[0027] In Figure 8, observe that the alpha metrics (am_c and am_apr) are sent to the alpha unit with a latency of 2 L_pb symbols and are always processed in forward order. The accumulated alpha metrics, A(k), are then stored while being processed and will be sent to the LLR unit in reverse (LBFO) order of storage, during the following data processing block period, p_w. Therefore, during each p_w, a new data processing block is being processed, while the previously processed accumulated metrics are being sent to the LLR unit. For example, the arrows show that when p_w = 2, the data processing block 0 is being processed by the alpha unit and the accumulated metrics A(k) will be sent to the LLR unit during p_w = 3, while the data processing block 1 is being processed.

[0028] The beta unit is composed of two modified backward Viterbi decoders which compute the backward state metrics as follows:

*_*(*) = ^min* , (*_* (* + 1) + bm_c (k + 1, S_k+1→S_k ) + bm_apr (k + 1, ^k+l ^→ S/c )) (^) where w = 0 or 1, representing the two beta sub-units; k > 1 is the symbol period; min*(.) is the min_star_sum operation, which is performed for all states S_k+i that transit to a given state S_k ; B_w(k+1) is the beta sub-unit w accumulated metric at time period k+1, with initial value Bw( wXLpm) = 0, Lpb is the processing block size and p_w > 0 is the set of even numbers when w = 0 and odd integers when w = 1; bm_c(k+l, S_k+l→S_k ) is the beta channel metric associated with the particular state transition in the TCM trellis, chosen to be a particular bmc(k+l,i) value, when i is the 8-VSB symbol index associated with the trellis state transition ( S_k+1 ^→S_k ) and bm_apr(k+l, S_k+i→ S_k ) is the beta apriori metric associated with the particular state transition in the TCM trellis, chosen to be a particular bm_c(k+l,j) value, where j is the dual-bit index associated with the trellis state transition ( S_k+l→ S_k ).

[0029] In Figure 8, observe that the beta sub-units compute their accumulated metrics backwards in time for a period of 2xL_pb symbols each, and they are staggered in time by L_pb symbols. The beta 0 sub-unit resets its accumulated metric to 0 at the beginning of the even p_w values, while processing the odd numbered data processing blocks. The beta 1 sub-unit resets its accumulated metric to 0 at the beginning of the odd numbered p_w values, while processing the even numbered data processing blocks. For each p_w, the accumulated beta metrics of one of the beta units will be sent to the LLR unit as soon as they are processed: Bo(k) for odd numbered p_w values and i(k) for even numbered p_w values. For example, the arrows show that when p_w = 2, the data processing block 0 is being processed by the beta unit 0 and the accumulated metrics B₀(k) are being concurrently sent to the LLR unit, while the beta unit 1 is processing the data processing block 2.

[0030] The LLR (log likelihood ratio) unit computes the extrinsic information for the input bit-pairs L. as follows:

LLR{k, j) = min* (A{k - l)+ B{k)+ bm_c (k, S_k→S_k__l )) (7)

S_t→S_t.,:j

where k > 1 is the symbol period; min*(.) is the min_star_sum operation, which is performed for all states S_k that transit to a given state 5_t_, and for each particular value of I_k = j and j = 0, 1, 2,3; A(k-l) is the alpha accumulated metric at time period k-1; B(k) is the beta accumulated metric at time period k and bm_c(k, S_k→S_k__l ) is the beta channel metric associated with the particular state transition in the TCM trellis, chosen to be a particular bmc(k,i) value, when i is the 8-VSB symbol index associated with the trellis state transition (¾→ί_Η ).

[0031] In Figure 8, observe that the LLR unit computes and stores its values backwards in time for each data processing block consisting of L_pb symbols. On the following data block period, the LLR values are retrieved in reverse order of storage (LIFO), being therefore delivered in the correct order at the MAP decoder output. For example, the arrows show that when p_w = 3, the data processing block 0 is being processed by the LLR unit and the accumulated metrics LLR(k, j) are being stored; when p_w = 4 the LLR accumulated metrics of the data processing block 0 are then retrieved from memory in the correct order and made available at the output, while the LLR unit is processing the data processing block 1. This represents an overall latency of 4 data processing blocks, or 4 Lp_b symbols with respect to the MAP decoder input.

[0032] The MAP controller unit directs the calculations of the metric generator, alpha, beta and LLR units, by sending all the necessary control signals: reset, logic enables, memory read/write enables and memory read/write address values. Since the TCM code is not a block code, in order to continuously generate the decoded symbol, a sliding window approach is used. Figure 9 shows a simplified diagram of the sliding window approach. The alpha unit processes the data processing unit (L_pb) symbols in the forward direction; each beta sub-unit processes 2xL_pb symbols in the backward direction and the LLR unit computes soft information for L_pb bit-pairs in the backward direction. The beta units process twice the number of symbols to avoid large data processing blocks and allow the beta metrics to converge before the actual LLR calculations start. After the LLR calculations are completed, the window advances by L_pb symbols, or a data processing block. For alternate windows, alternate beta sub-units are utilized.

[0033] Figure 10 shows the diagram of Figure 9 in time, as the data processing blocks are processed. In Figure 10, p_w represents time, associated with the data processing block index at the MAP decoder input, and k represents the index of the input symbols being processed by the various units. For example, when 4 <p_w < 5, the alpha unit (Al) is processing symbols of index 2xL_pb-l < k < 3xL_pb-l in the forward direction; the beta unit 0 (B0) is processing symbols of index 4xL_pb-l≥ k > 3xL_pb-l in the backward direction; the beta unit 1 (Bl) and LLR unit are processing symbols of index 2xLpb-l≥ k > Lp_b-1 in the backward direction; the LLR unit (LLR) is outputting soft bit-pairs associated with the first data block, that is, symbols of index 0 < k < L_pb-1 in the forward direction. Hence, we can observe once again that the latency of the MAP decoder is 4 data processing blocks.

[0034] As discussed above, the MAP decoder architecture of Figure 7 must be duplicated 12 times in order to achieve a straightforward design of the trellis decoder and deinterleaver of Figure 4. As can well be appreciated, this straightforward approach can be intensive in resources such as integrated circuit device area, power consumption, thermal dissipation, and the like. In one aspect of the invention, the 12 separate trellis decoder deinterleavers of Figure 4 can be combined into an architecture that realizes only one trellis decoder function instead of 12 trellis decoder functions.

[0035] Figure 11 depicts an example decoding system according to aspects of the invention. In Figure 10, only one decoder is used, instead of, for example, the 12 decoders in parallel of Figure 4 for ATSC-DTV signal decoding. Figure 11 depicts a modified metric generator 101 coupled to a modified first metric processor (alpha unit 103). The modified metric generator 101 is also coupled to a modified dual second metric processor unit (beta unit 105). The two outputs of the beta sub- units internal to the beta unit are input to a beta unit mux to provide a beta unit 105 output. The alpha unit 103 and beta units 105 produce processed metrics for the last metric processor (log likelihood unit 107) which computes and produces output data bits corresponding to the interleaved symbol input of the consolidated trellis decoder deinterleaver. The MAP controller 109 is used to control and synchronize the processing activities of the functional blocks of Figure 11. The modifications made to each of the function blocks of Figure 11 are discussed below.

[0036] The changes in the metric generator unit 101 to accommodate the consolidation of the 12 decoders into one may be explained by viewing Figure 12. The metric generator is mainly composed of 4 sub-units: the noise power estimator, the channel metric calculator, the channel metric storage RAM and the apriori metric storage RAM. It outputs the alpha and beta channel and apriori metrics to the alpha and beta units, respectively. The noise power estimator may use quantizers to estimate the amount of noise in the input symbols and average the noise to obtain and estimate of the power or variance σ². The channel metric calculator performs the calculation in equation 1. Both RAMs store the channel and apriori metric values for later retrieval.

[0037] In Figures 11 and 12, the channel metric RAM and the a priori metric RAM functional blocks are designed to accommodate the consolation of the 12 decoder design of Figure 4 to a one decoder design. In one aspect of the invention, the storage RAMs are twelve times larger in a consolidated decoder design as opposed to the 12 decoder design of Figure 4, since the new data processing block is now Li_2pb = 12xL_pb- In addition, the memory addresses change to reflect the change in size, with the addition of 4 bits per address. The noise estimator and metric calculator keep the same design used for one decoder.

[0038] In another aspect, modification in the control of the channel metric and a priori metric RAM in Figure 12 accommodates the skipping of 4 trellis decoders every segment sync, for the 12 interleaved decoder. The skipping is such that during the first segment of a field, the order of decoders is 0 to 11; during the second segment, it is 4,5,...,11,0, ...,3; during the third segment, it is 8, ... , 11 ,0, 1 , ... ,7 and so on. The write addresses for the channel metric RAM are designed to perform the decoder skipping, so that all subsequent units see 12 sequential decoders at all times. The write operation into the a priori RAM, as well as the read operations from both RAMs, are sequential; one per decoder, from 0 to 11. Observe that, since the beta metrics are read from memory in reverse order of storage, the first beta (channel and apriori) metrics of each L_12pb block belongs to decoder 11, as opposed to the alpha (channel and apriori) metrics, for which the first of each Li_2pb belongs to decoder 0. Therefore, the sequence of am (alpha) metrics out of the metric generator are: am(0,0), am(0,l ),..., am(0,l l),am(l,0),am( 1,1), ...,am(l,l l), ...,am(L_pb-l,0), am(L_pb-l,l), ...,am(L_pb- 1,11), ..., where am(p,l) stands for arri_c or am_apr, 1 is the decoder number and p is the symbol index within the processing block per decoder. And the sequence of bm (beta) metrics out of the metric generator are: bm(Lpb-l,H), bm(L_Pb-l,10),...,bm(L_pb-l,0),bm(L_pb-2,l l),bm(L_Pb- 2,10), ...,bm(L_pb-2,0), ...,bm(0,l l), bm(0,10), ...,bm(0,0), where bm(p,l) stands for bnic or bm_apr, 1 is the decoder number and p is the symbol index within the processing block per decoder. There is no need to separate the metrics of each decoder (0 to 11), since the operations of the alpha and beta units will naturally realign these metrics before the LLR calculations. This order of alpha and beta metrics out of the metric generator represents the most simple in terms of memory storage and alignment of metrics for the processing by the LLR unit.

[0039] One skilled in the art will realize that the a priori inputs to the metric generation of Figures 11 and 12 are well known contributions in the theory and design of MAP decoders as extensively described in the literature. MAP decoders are generally components of iterative decoders for concatenated or turbo codes, and as such, the a priori inputs come from the extrinsic information of another component decoder. By performing iterations on the received digital stream between the component decoders of a concatenated or turbo system, each decoder passes extrinsic information to the other, that is, receives a priori information from the other, and a more reliable final estimate of the transmitted data is made by the decoders. Thus, the a priori inputs of Figure 12 can be useful for increased reliability of the MAP decoder described herein. The metric generator of Figure 12 sequentially computes and stores the interleaved metrics in memory corresponding to the interleaved trellis encoded data groups and delivers them to its output. The metric generator sequentially stores and delivers received a priori alpha and beta metrics in the same order as the computed alpha and beta metrics. The metric generator has random access memory storage for both the computed and a priori metrics. The random access memory storage is sized to accommodate metric data for all M of the trellis encoders.

[0040] The metric generator also computes and stores the alpha metrics in the sequential forward order of symbol arrival and then delivers the alpha metrics in the sequential forward order of symbol arrival, after a predetermined latency of 2*M*L symbols, where M is the number of interleaved trellis encoders and L is a function of the trellis decoderprocessing block. The metric generator also computes the beta metrics in the sequential forward order of symbol arrival and stores and delivers the beta metrics in the sequential reverse order of symbol arrival, after a predetermined latency of 2*M*L symbols, where M is the number of interleaved trellis encoders and L = L_pb is a function of the trellis decoderprocessing block.

[0041] In one embodiment, the metric generator, operating with an ATSC-DTV trellis modulation, sequentially increments a trellis encoder count with every symbol arrival. The trellis encoder count keeps track of and is cyclic on the number M (M=12 for ATSC-DTV) of interleaved trellis decoders. The metric generator also sequentially increments the symbol count per trellis encoder every M symbols to keep track of the number of symbols received per trellis encoder. The incrementing of the trellis encoder count occurs with the exception that the metric generator increments the trellis encoder count by 4 on the start of every segment, prior to metric computation and storage. Furthermore, the metric generator delivers the alpha metrics in the sequential forward order of trellis encoder and symbol count, and delivers the beta metrics in the sequential reverse order of trellis encoder and symbol count, after a predetermined latency of 2*M*L symbols, where M is the number of interleaved trellis encoders and L is a function of the trellis decoderprocessing block, where L= Lpb.

[0042] Figure 13 depicts a first processing unit also known as an alpha unit. One aspect of the current invention may be described as changes in the alpha unit to accommodate the consolidation of 12 decoders into one. The alpha register and alpha RAM are the blocks that change in the present consolidated design. To accommodate the current invention, the alpha RAM of Figure 13 is twelve times larger than that of a trellis decoder in Figure 4, since the new data processing block is now Li_2p = 12xLpb- Also the alpha register will be twelve times larger. In addition, the memory addresses change to reflect the change in size, with the addition of 4 bits per address. The Add-Compare-Select (ACS) unit is similar to the one used in a traditional Viterbi decoder. This ACS unit of the alpha unit performs the operation of calculating a result for equation 3, where A(k-1) has been previously stored in the alpha register, in the specified position, for each trellis decoder and trellis state. The alpha register keeps stored the accumulated alpha metrics A(k) of the 4-state trellis per decoder, as a carrousel that shifts a decoder on every symbol, in the order 0 to 11. The alpha RAM of Figure 13 stores the accumulated value for every symbol and decoder and trellis state of a processing block, while concurrently retrieving the values of the previous block in reverse order. This is accomplished with one only memory by writing (and reading) in alternate directions for each new data processing block.

[0043] The output of the alpha unit will be sent to the LLR unit, with the following sequence of values within a processing block: A(L_pb-2, 11 , So→S₃), A(Lpb-2, 10, So→S₃), ... , A(Lpb- 2,0,S₀→S₃), A(L_pb-3,l l,S₀-→S₃), A(L_pb-3,10,S₀→S₃), A(L_pb-3,0,S₀→S₃),

A(0,11,S₀→S₃), A(0,10,So→S₃), A(0,0,S₀→S₃), where A(p,l,S₀→S₃) stands for the accumulated alpha metric output, p is the symbol index within the processing block per decoder, 1 is the decoder number, such that, in equation 3, k = 12*p + 1, and So→S₃ are the 4 trellis states. Observe that the alpha accumulated metrics, although processed in the forward order, are sent in reverse order required by the LLR unit.

[0044] In one embodiment, the alpha unit is a forward metric computation unit which sequentially computes alpha state metrics per trellis decoder. The alpha unit sequentially increments the trellis decoder count with every symbol arrival. It does this cyclically on the number M of interleaved trellis encoders. The alpha unit also sequentially increments the symbol count per trellis encoder every M symbols. The alpha unit delivers a set of accumulated alpha state metrics in sequential reverse order of trellis decoders and symbol arrival, for each consecutive block of a predetermined number of symbols M*L, where M is the number of interleaved trellis encoders and L = L_pb is a function of the trellis

decoderprocessing block. In addition, the alpha unit contains one add-compare-select (ACS) unit which performs calculations in accordance with Equation (3) or a derivative equation, and a set of alpha registers which cyclically increment and rotate through the M interleaved trellis encoders retrieving the previous accumulated set of alpha state metrics per trellis decoder or storing a new set of accumulated alpha state metrics acquired from the ACS unit. Furthermore, the alpha unit contains memory storage for the plurality M of trellis encoders.

[0045] Figure 14 depicts a sub-unit of the beta unit. Each beta unit includes two beta sub- units. One aspect of the current invention may be described as changes in the beta unit to accommodate the consolidation of 12 decoders into one. The beta register of each beta sub- unit is the block that changes in the consolidated design. To accommodate the current invention, the beta register is twelve times larger. The Add-Compare-Select (ACS) unit is similar to the one in a traditional Viterbi decoder. The ACS unit of the beta sub-unit of Figure 14 performs the operation of calculating a result for equation 6, where B(k-l) has been previously stored in the alpha register, in the specified position, for each trellis decoder and state. The beta register keeps stored the accumulated alpha metrics of the 4-state trellis per decoder, as a carrousel that shifts a decoder on every symbol, in the order 11 down to 0. The control inputs remain the same, basically signaling the reset of each beta-unit every 2xL_12pb symbols, alternately. As stated above, there are two beta sub-units, each having a Viterbi decoder ACS unit which computes the backward state metrics of B0 and B 1.

[0046] The beta accumulated metric values of one of the beta sub-units are alternately sent to the LLR unit for further processing, with the following sequence of values within a processing block: B(L_pb-l,l l, S₀→S₃), B(L_pb-l,10, S₀→S₃), B(L_pb-l,0,S₀→S₃), B(L_pb- 2,1 l,So→S₃), B(L_pb-2,10,S₀→S₃), ..., B(Lp_b2,0,S₀→S₃), ..., B(l,l 1,S₀→S₃), B(1,10,S₀→S₃), ..., B(l,0,So→S₃), ..., where B(p,l,So→S₃) stands for the accumulated beta metric output, p is the symbol index within the processing block per decoder, 1 is the decoder number, such that, in equation 6, k = 12*p + 1, and S₀→S₃ are the 4 trellis states. Observe that the beta accumulated metrics are processed and sent out in reverse order required by the LLR unit.

[0047] In one embodiment, the beta unit processes the beta metrics in a reverse time order and outputs the accumulated beta state metrics in reverse time order. In addition, the beta unit contains one add-compare-select (ACS) unit which performs calculations in accordance with Equation (6) or a derivative equation, and a set of beta registers which cyclically decrement and rotate through the M interleaved trellis encoders retrieving the previous accumulated set of beta state metrics per trellis decoder or storing a new set of accumulated beta state metrics acquired from the ACS unit. Furthermore, the beta unit contains memory storage for the plurality of trellis encoders. The beta unit is a backward metric computation or processor unit which sequentially computes beta state metrics per trellis encoder for blocks of a predetermined number of symbols (2*M*L symbols, where L = L_pb) at a time, starting at the highest trellis encoder and symbol count. The beta unit sequentially decrements the trellis encoder count for every symbol, cyclically on the number M of interleaved trellis encoders and sequentially decrements the symbol count per trellis encoder every M symbols. The beta unit delivers a set of accumulated beta states metrics in sequential reverse order of trellis encoders and symbol arrival, for a predetermined subset of the block at the end of the computation (the last M*L symbols, where L = L_pb). Furthermore, the beta calculation is repeated on all predetermined blocks of (2*M*L, where L = L_pb) symbols necessary in order to deliver beta state metrics for all distinct predetermined subsets (of M*L symbols, where L = L_pb) which are present in the symbol stream.

[0048] In one embodiment, the beta unit is composed of two beta sub-units which perform their calculations or processing of input metrics in parallel, on predetermined blocks of

(2*M*L, where L = L_pb) symbols which are staggered from each other by a predetermined delay (of M*L symbols, where L = L_pb). Thus, each beta sub-unit is alternately responsible for delivery of a distinct subset of (M*L, where L = L_pb) beta state metrics.

[0049] Figure 15 depicts a third processing unit also known as a log likelihood (LLR) unit. One aspect of the current invention may be described as changes in the LLR unit to accommodate the consolidation of 12 decoders into one. To accommodate the current invention, the LLR RAM is twelve times larger than that required for a 12 decoder design, since the new data processing block is now Lj_2pb = 12xL_pb- In addition, the memory addresses change to reflect the change in size, with the addition of 4 bits per address. The Add-Compare-Select (ACS) unit of the LLR unit of Figure 15 is similar to the one in a traditional Viterbi decoder. The ACS unit of Figure 15 performs the operation of calculating a result for in equation 7, where A(k-l) is received from the alpha RAM, B(k) and bnic(k) are received from the appropriate beta sub-unit. The LLR RAM stores the LLR values for every symbol and decoder of a processing block, while concurrently retrieving the values of the previous block in reverse order. This is accomplished with one only memory by writing (and reading) in alternate directions for each new data processing block.

[0050] The output of the LLR unit are the desired soft output values of the decision bit-pair (two bits per trellis branch), which is the a posteriori probability (APP) of the decision bit- pair, or equivalently, of the TCM code output symbols. They will have the following sequence of values within a processing block: LLR(0,0,0→3), LLR(0,1,0→3),

LLR(0,11,0→3), LLR(1,0,0→3), LLR(1,1,0→3), LLR(1,11,0→3), LLR(L_pb- l,0,0- 3), LLR(L_pb-l_>l,0→3), ...,LLR(L_pb-U l,0→3), where LLR(p,l,0→3) stands for LLR soft output, p is the symbol index within the processing block per decoder, 1 is the decoder number, , such that, in equation 7, k = 12*p + 1, and 0→3 are the 4 bit-pairs. Observe that the LLR values, although processed in reverse order, are sent in the forward order consistent with the data input.

[0051] In one embodiment, the log likelihood ratio unit (LLR) processes the accumulated alpha state metrics and the accumulated beta state metrics to sequentially estimate the decoded data per trellis decoder for blocks of a predetermined number of symbols (M*L symbols, where L = L_Pb) at a time, starting at the highest trellis encoder and symbol count. The LLR unit sequentially decrements the trellis encoder count for every symbol, cyclically on the number M of interleaved trellis encoders and sequentially decrements the symbol count per trellis encoder every M symbols. The LLR unit delivers decoded data in sequential forward order of trellis encoders and symbol count, for each predetermined block of (M*L, where L = L_pb) symbols present in the symbol stream.

[0052] The MAP controller unit directs the calculations of the metric generator, alpha, beta, and LLR units for the 12 merged MAP decoders by sending all the necessary control signals: reset, logic enables, memory read/write enables and memory read/write address values, utilizing a sliding window approach. The main difference of this merged architecture for the MAP controller unit is in the memory addressing. The new memory address counters for a processing block L_pb only increment every 12 symbols, which is equivalent to introducing a 0 to 11 counter, which would enable the memory addressing at the beginning or end of every 12 symbol epoch. The enables for the logic and memory read writes continue operating in the same way, as a function of the symbol enables.

[0053] An integrated circuit device area-efficient MAP decoder architecture for the ATSC- DTV trellis code merges the design of the 12 trellis decoders of the prior art Figure 4 and reuses functional blocks for deinterleaving, instead of replicating the design of one decoder. Figures 11-15 identify the consolidated architecture and highlight the advantage that all of the decoder blocks of Figure 4 are not replicated 12 times in a merged architecture. This results in a considerable savings in silicon area. This architecture is suitable for an iterative (turbo) decoding FEC system in a mobile ATSC-DTV standard based on the original DTV standard. The concepts used in this invention can be extended to other trellis codes composed of multiple interleaved trellis components. In one embodiment, this architecture was implemented in VHDL and utilized in a prototype for a mobile ATSC-DTV receiver.

[0054] The implementations described herein may be implemented in, for example, a method or process, an apparatus, or a combination of hardware and software or hardware and firmware. Even if only discussed in the context of a single form of implementation, the implementation of features discussed may also be implemented in other forms (for example, an apparatus or a program executed in a computer). An apparatus may be implemented in, for example, appropriate hardware, software, and firmware. The methods may be implemented in, for example, an apparatus such as, for example, a processor, which refers to processing devices in general, including, for example, a computer, a microprocessor, an integrated circuit, or a programmable logic device. Processing devices also include communication devices, such as, for example, computers, cell phones, portable/personal digital assistants ("PDAs"), and other devices that facilitate communication of information between end-users.

[0055] Implementations of the various processes and features described herein may be embodied in a variety of different equipment or applications, particularly, for example, equipment or applications associated with data transmission and reception. Examples of equipment include video coders, video decoders, video codecs, web servers, set-top boxes, laptops, personal computers, and other communication devices. As should be clear, the equipment may be mobile and even installed in a mobile vehicle.

[0056] Additionally, the methods may be implemented by instructions being performed by a processor, and such instructions may be stored on a processor-readable medium such as, for example, an integrated circuit, a software carrier or other storage device such as, for example, a hard disk, a compact diskette, a random access memory ("RAM"), a read-only memory ("ROM") or any other magnetic optical, or solid state media. The instructions may form an application program tangibly embodied on a processor-readable medium such as any of the media listed above. As should be clear, a processor may include, as part of the processor unit, a processor-readable medium having, for example, instructions for carrying out a process.

[0057] As required, detailed embodiments of the present invention are disclosed herein; however, it is to be understood that the disclosed embodiments are merely exemplary of the invention, which can be embodied in various forms. Therefore, specific structural and functional details disclosed herein are not to be interpreted as limiting, but merely as a basis for the claims and as a representative basis for teaching one skilled in the art to variously employ the present invention in virtually any appropriately detailed structure. Further, the terms and phrases used herein are not intended to be limiting; but rather, to provide an understandable description of the invention.

Claims

1. An apparatus for decoding digital data, the digital data encoded using a plurality of interleaved trellis encoders, each trellis encoder providing a trellis encoded data group for interleaving, the data group including a stream of trellis encoded symbols, the apparatus comprising:

a metric generator unit that outputs metrics corresponding to each symbol of the interleaved trellis-encoded data groups, the metrics including alpha and beta metrics;

an alpha unit that inputs the alpha metrics and outputs accumulated alpha state metrics for each trellis encoded data group;

a beta unit that inputs the beta metrics and outputs accumulated beta state metrics for each trellis encoded data group; and

a log likelihood ratio unit that computes output values corresponding to the digital data using the accumulated alpha state metrics and accumulated beta state metrics;

wherein only one set of the metric generator, the alpha unit, the beta unit, and the log likelihood unit is used to decode information from the plurality of interleaved trellis encoder.

2. The apparatus of claim 1, further comprising a controller unit that directs operation of the one set.

3. The apparatus of claim 1, wherein the metric generator comprises a processor that sequentially computes and outputs alpha and beta metrics and outputs received a priori alpha metrics and a priori beta metrics in the same order as the computed alpha and beta metrics, and wherein the metric generator random access memory provides computed metric storage and a priori metric storage for the M trellis encoders.

4. The apparatus of claim 1, wherein the alpha unit comprises an add-compare-select unit, alpha registers, and alpha random access memory, wherein the alpha registers cyclically increment and rotate through the M interleaved trellis encoders retrieving a previous set or storing a new set of accumulated alpha state metrics to and from the add-compare-select unit, respectively, and wherein the alpha random access memory provides storage for data from the M trellis encoders.

5. The apparatus of claim 1, wherein the beta unit comprises an add-compare-select unit, beta registers, and beta random access memory, wherein the beta registers cyclically decrement through the M interleaved trellis encoders retrieving or storing a new set a previous accumulated set of beta state metrics, to and from the add-compare-select unit, respectively, and wherein the beta random access memory provides storage for data from the M trellis encoders.

6. The apparatus of claim 1, wherein the log likelihood ratio (LLR) unit comprises an add-compare-select unit and LLR random access memory, wherein the LLR processes the accumulated alpha state metrics and the accumulated beta state metrics in a reverse time order and generates the output values corresponding to the digital data in forward time order.

7. The apparatus of claim 1, wherein the digital data is encoded using 12 interleaved trellis encoders in accordance with the advanced television systems committee (ATSC) standard for digital television (DTV).

8. The apparatus of claim 3, wherein the metric generator delivers two sets of beta metrics wherein a first beta metric is staggered in time compared to a second beta metric by a predetermined number of symbols.

9. The apparatus of claim 3, wherein the metric generator comprises a combination of random access memory and a metric calculator that computes and stores the alpha metrics in a sequential forward order of symbol arrival and outputs the alpha metrics in the sequential forward order of symbol arrival after a predetermined latency and that computes the beta metrics in the sequential forward order of symbol arrival and stores and outputs the beta metrics in a sequential reverse order of symbol arrival after a predetermined latency.

10. The apparatus of claim 3, wherein the metric generator computes the alpha and beta metrics in a sequential forward order of symbol arrival and stores the alpha and beta metrics in an order of trellis encoder count and a symbol count, whereby the metric generator sequentially increments the trellis encoder count with every symbol arrival and sequentially increments the symbol count per trellis encoder every M symbols, with the exception that the metric generator increments the trellis encoder count by 4 on the start of every repeated predetermined number of symbols prior to metric computation and storage.

11. The apparatus of claim 10, wherein the metric generator outputs the alpha metrics in a sequential forward order of the trellis encoder count, and outputs the beta metrics in a sequential reverse order of trellis encoder count after a predetermined latency.

12. The apparatus of claim 1, wherein the alpha unit comprises a forward metric computation unit which sequentially computes alpha state metrics per trellis decoder wherein the alpha unit sequentially increments a trellis decoder count with every symbol arrival, cyclically on the number M of interleaved trellis encoders and sequentially increments the symbol count per trellis encoder every M symbols, the alpha unit outputs a set of accumulated alpha state metrics in a sequential reverse order of symbol arrival for each consecutive block of a predetermined number of symbols.

13. The apparatus of claim 1, wherein the beta unit comprises a backward metric computation unit which sequentially computes beta state metrics per trellis encoder for blocks of a predetermined number of symbols starting at the highest trellis encoder and symbol count, wherein the beta unit sequentially decrements a trellis encoder count for every symbol, cyclically on the number M of interleaved trellis encoders and sequentially decrements a symbol count per trellis encoder every M symbols such that the beta unit outputs a set of accumulated beta states metrics in a sequential reverse order of symbol arrival for a predetermined subset of the block.

14. The apparatus of claim 13 in which the beta unit is composed of two beta units which perform their calculations in parallel, on predetermined blocks of symbols which are staggered with respect to one another by a predetermined delay such that each unit is alternately outputs a distinct subset of beta state metrics.

15. The apparatus of claim 1, wherein the log likelihood ratio unit processes the accumulated alpha state metrics and the accumulated beta state metrics to sequentially estimate the decoded data per trellis decoder for blocks of a predetermined number of symbols and outputs decoded data in a sequential forward order of symbol arrival for each predetermined block of symbols.