Unified viterbi/turbo decoder for mobile communication systems

A Viterbi/Turbo unified decoder supports both voice and data streams due to the ability of performing Viterbi (convolutional) decoding and Turbo decoding. The Viterbi/Turbo unified decoder of an embodiment reduces the hardware cost by computing path metrics for both Viterbi and Turbo decoding using a single control circuit. The control circuit comprises a plurality of processors and memory banks, and the routing rule for the processors to read/write the path metric information from/to the memory banks are fixed for both Viterbi and Turbo coded inputs.

BACKGROUND

The present invention relates to a unified Viterbi/Turbo decoder in wireless communication systems, and in particular, to a system for receiving and decoding voice and data streams adaptively.

Error control coding techniques involves the use of a channel encoder in the transmitter and a decoder in the receiver. The channel encoder accepts message bits and adds redundancy according to a prescribed rule, thereby producing encoded data at a higher bit rate. The channel decoder exploits the redundancy to decide which message bits were actually transmitted. The purpose of error control coding is to minimize the effect of channel noise. The error control codes are generally classified into block codes and convolutional codes. Convolutional codes are preferred for wireless voice communication systems in which the retransmission of data and its associated delay is intolerable. Block codes are capable of delivering higher throughput and are preferred for the transmission of data where latency is less of a concern.

The Viterbi algorithm is a sequential trellis search algorithm for performing maximum-likelihood (ML) sequence detection, and it is an optimum decoding algorithm for convolutional codes. A published book written by S. B. Wicker, named “Error Control System for Digital Communication and Storage, Pretice Hall, 1995.” disclosed a Viterbi decoder for use in mobile communication systems.

FIG. 1shows a flowchart of a decoding algorithm used in a practical Viterbi decoder. The decoding procedures include quantization, branch metric computation, path metric update, survivor path recording, and output decision generation. The received signals are first recovered by sampling, and then converted to digital signals. The boundaries of frames and code symbols in the digital signals are detected for block synchronization. After branch metric computation, the partial path metrics is updated using the new branch metric, and the surviving path at each node is tagged. Finally, the decoded output sequence based on the survivor path information can be generated.

FIG. 2shows a generic Viterbi decoder20. The Viterbi decoder20includes a branch metric calculating (BMC) unit202, whose output is presented to an Add Compare Select (ACS) unit204. A state controller206provides inputs to the BMC unit202, the ACS unit204and a path metric memory208. The path metric memory208acts as a double buffer and interchanges information with the ACS unit204. A borrow output205of the ACS unit204is presented to a trace-back memory and controller210, whose output is the received information signal211.

Turbo codes, also known as parallel concatenated codes, are a class of codes whose performance is very close to the Shannon capacity limit. Turbo encoders are implemented by connecting convolutional encoders either in parallel or series to produce concatenated outputs. Bit sequences passing from one encoder to another are permuted by a pseudo-random interleaver, and thus low-weight code words produced by a single encoder are transformed into high-weight code words. Third generation (3G) mobile wireless standards, such as Code Division Multiple Access (CDMA) 2000 and Universal Mobile Telecommunication Service (UMTS) require Turbo encoding for data streams. UK patent application number GB2352943A and “Turbo codes, principles and application, Kluwer Academic Publishers, 2000.” Written by B. Vucetic and J. Yuan disclosed embodiments of the Turbo decoder with the Maximum a Posteriori probability (MAP) algorithm and Soft Output Viterbi Algorithm (SOVA).

FIG. 3shows an iterative Turbo decoder based on the MAP algorithm. A received symbol in a Turbo decoder consists of systematic data, representing the actual data being transmitted, and parity data, which represents the coded form of the data being transmitted. A first input r0, being the parity data of the received symbol, is presented to a first MAP decoder302and a second MAP decoder306via an interleaver304. A second input r1, being the systematic data of the received symbol, is presented to the first MAP decoder302. A recursive input311from a deinterleaver310is also presented to the first MAP decoder302. The output303of the first MAP decoder302is then provided to an interleaver308, whose output is provided to the second MAP decoder306. The second MAP decoder306also receives an input from a third input r2and generates two outputs. A first output307aof the second MAP decoder306is provided to the deinterleaver310, whereas the second output307bis provided to another deinterleaver312. The output of the deinterleaver312is provided to a slicer314, which applies a threshold to a soft output to convert it to a hard output, being a received information signal315.

Third Generation (3G) communication systems typically require both convolutional coding, for example, Viterbi coding, and Turbo coding for voice and data signals respectively. It is because the transmission of voice and data provides conflicting requirements for transmission rate versus latency and propagation delay. The current mode of addressing these problems is to provide separate encoding systems: Turbo coding for high data-rate data streams and convolutional coding for voice or low data-rate data streams. The receivers of such systems thus require two independent decoders, resulting in a multiplicity of hardware platforms and increasing cost.

SUMMARY

A unified Viterbi/Turbo decoder is provided which is capable of performing either convolutional decoding or Turbo decoding according to the input coding type. In an embodiment, the decoder comprises a Branch Metric Calculation (BMC) unit, a control circuit, a trace-back unit, an interleaver/de-interleaver, and a Turbo buffer. The BMC unit receives either a Viterbi or Turbo symbols and determines a branch metric associated with each node of the code word. The decoder is configurable to adapt the input, and the control circuit is a common component for the two coding types which fully utilize the memory and processor capacity. The control circuit computes partial path metrics at each node with its processors according to the corresponding branch metric and the partial path metrics at a preceding node stored in a first memory block. The control circuit then stores the computed partial path metrics in a second memory block. For processing the next node, the control circuit reads from the second memory block then stores in the first memory block after computation, and so on. The two memory blocks interchange path metric information with the processors. The order and address for reading and writing the partial path metrics from/to the memory blocks follow a fixed routing rule, which allows the partial path metrics to be processed in parallel to fully utilize the processing capacity. The control circuit then performs either selection or Maximum a Posteriori probability (MAP) calculation depending on the input coding type to identify a surviving path at each node.

The trace-back unit receives the output of the control circuit while performing Viterbi decoding, and it tracks the surviving paths designated by the control circuit. The interleaver/de-interleaver receives the output of the control circuit while performing Turbo decoding, and permutes or recovers the order of its input in a deterministic manner. The Turbo buffer receives the input symbols and the output of the interleaver/de-interleaver, and provides storage for the BMC unit and the interleaver/de-interleaver.

In an embodiment, the control circuit comprises an Add Compare Select Processor (ACSP) array having J ACSPs (J=2m, m belongs to an integer, and m+1 must be less than the constraint length of the encoder, n+1), a path metric calculation unit having the first and second memory blocks, a fixed routing circuit, and a selection and MAP calculation unit. The ACSP array computes the partial path metrics at each node according to the corresponding branch metric. Each ACSP comprises two Add Compare Select units (ACSU) processing the partial path metrics in parallel. The path metric calculation unit stores the partial path metrics associated with a current node and a preceding node in the two memory block. Each memory block comprises I memory banks, wherein I=2m+1. The fixed routing circuit establishes fixed connections between each ACSP and four memory banks, two from each memory block, according to the fixed routing rule. The selection and MAP calculation unit performs either selection or MAP calculation to identify the surviving path at each node. The selection and MAP calculation unit computes a Log-Likelihood Ratio (LLR) according to the branch metrics obtained from the BMC unit and the path metrics obtained from the path metric calculation mean for the Turbo code word.

DETAILED DESCRIPTION

First Embodiment

FIG. 4shows a block diagram of a unified Viterbi/Turbo decoder according to an embodiment of the invention. The unified Viterbi/Turbo decoder4is capable of executing either convolutional or Turbo decoding depending on the encoding method of the received data. The unified Viterbi/Turbo decoder4decodes w-bit noisy symbols received from a noisy input terminal40. The unified Viterbi/Turbo decoder4comprises an input buffer43, a branch metric calculating (BMC) unit41, a control circuit42, an interleaver/deinterleaver buffer45, an interleaver/deinterleaver44, a survivor path updating unit46, a trace-back unit47, and a last-in-first-out (LIFO) buffer48.

As shown inFIG. 4, the control circuit42comprises a path metric calculation unit421with a path memory bank, a fixed routing circuit422, an add-compare-select processor (ACSP) array423, and a selection and MAP calculation unit424. The selection and MAP calculation unit424comprises a selection unit for the convolutional (Viterbi) decoding and a MAP unit for calculating the Log Likelihood Ratio (LLR) of the Turbo decoding. The control circuit42performs the major calculations required in either Viterbi or Turbo decoding, and it is a common working area for both Viterbi and Turbo decoding. The control circuit42is an optimum replacement for individual computation unit of the Viterbi and Turbo decoder. The chip size of a receiver capable of decoding both Viterbi and Turbo codes can thus be reduced. Voice or low data-rate type of input is coded by Viterbi codes and high data-rate type of input is coded by Turbo codes, thus the processing paths for decoding these two input types are different. Both voice streams and data streams are providing to the BMC unit41after receiving, then provided to the control circuit42. The Viterbi encoded streams are provided to the survivor path updating unit46and the trace-back unit47after data processing in the control circuit42, whereas the Turbo encoded streams are provided to interleaver/deinterleaver44and buffers43and45after data processing in the control circuit42to perform interleaving and deinterleaving.

The survivor path updating unit46comprises a Survivor Path Memory (SPM) for storing surviving paths determined at each node in the trellis diagram for Viterbi decoding.

In the first embodiment, the constraint length of the convolutional encoder is 5 (n=4), thus there are 16 states (2n=16) in the Viterbi decoding. The number of ACSPs in the ACSP array423is chosen to be 2m, wherein m must be less than n, and m=2 is chosen in this embodiment. Each ACSP comprises an Add Compare Select Unit (ACSU) pair, thus is capable of processing two inputs simultaneously. Consequently, an efficient design is to provide eight memory banks (2m+1=8) to cooperate with the four ACSPs, as the four ACSPs can process eight partial path metrics simultaneously.

FIG. 5is a block diagram illustrating a control circuit5, which is an exemplary implementation of the control circuit42inFIG. 4according to the first embodiment. The control circuit5comprises memory banks52, a fixed routing circuit54, an Add Compare Select Processor (ACSP) Array56, and a selection and MAP calculation unit58. There are eight memory banks520˜527implementing by Random-Access Memory (RAM) coupled to the fixed routing circuit54. The ACSP array56includes four ACSPs560˜563, and each ACSP further includes two Add Compare Select Units (ACSUs). Each ACSP560˜563corresponds to an Add Compare Select (ACS) unit580˜583in the selection and MAP calculation unit58. The outputs of the ACS units580˜583are provided to Compare Select (CS) units584˜585, and the outputs of the CS units585˜585are provided to another CS unit586.

FIGS. 6aand6billustrates two types of Add Compare Select Unit (ACSU) circuitry for the previous described ACSP. The ACSU inFIG. 6acomprises three adders, two comparators, and three multiplexers, whereas the ACSU inFIG. 6breplaces a comparator with a look up table. The connections and relationships of the two ACSUs are identical.

FIG. 7ashows an exemplary path metric memory bank organization illustrating the read/write selection rule defined by the fixed routing circuit422ofFIG. 4. The memory banks shown inFIG. 5aare physically located in the path metric calculation unit421ofFIG. 4. The disclosed read/write selection rule in the invention is intended to speed the processing by providing and acquiring path metric information to/from the ACSP array422in parallel. The connection lines between the memory bank and the ACSP array426are arranged according to the trellis diagram, which cooperates with the ACSP array423to process the branch metrics and the partial path metrics simultaneously. Each path metric memory bank (MB) is managed by an address generator (AG).

As shown inFIG. 7a, there are 8 memory banks Bank(0)˜Bank(7)) and 4 ACSPs (ACSP0˜ACSP3). Each memory bank comprises two blocks (Block A and Block B) for storing path metric information corresponding to two different time points respectively. The read/write memory selection rule for Viterbi decoding is explained using the following example. A first pair of path metric information is stored in Bank (0) of Block A and Bank (4) of Block A respectively at time point t1. ACSP0obtains the first pair of path metric information for generating two new partial path metrics, and stores the new partial path metrics in Bank (0) of Block B and Bank (1) of Block B at time point t1+p, wherein p indicates the processing time for the ACSP to generate new partial path metrics.

FIG. 7bshows the detail ofFIG. 7a, wherein the numbering and index are shown in binary. There are two memory elements in each bank, thus the ACSPs access each bank twice for processing data in both memory elements. For example, ACSP (00) obtains path metric information from a memory element with state index 0000 and a memory element with state index 1000 in Block A at time point t1. Subsequently, ACSP (00) generates two new partial path metrics, and stores these two new partial path metrics in a memory element with state index 0000 and a memory element with state index 0010 in Block B at time point t1+p. ACSP (01), ACSP (10), and ACSP (11) interact with the memory banks similarly as ACSP (00) at the same time.

After processing the first memory element of each bank, ACSP (00) obtains path metric information from the memory element with state index 0001 and the memory element with state index 1001 in Block A at time point t2. Similarly, ACSP (00) generates two new partial path metrics and stores them in the memory elements with state index 0001 and state index 0011 in Block B at time point t2+p. The remaining ACSPs perform similar read/write procedures as ACSP (00) to process the second memory element of each bank simultaneously.

At the next time point, each ACSP of the ACSP array reads the path metric information from the corresponding banks in Block B for generating new path metric information, and subsequently, storing the new path metric information in Block A. This read/write operation repeats twice, one for the first memory elements and one for the second memory elements of the banks. The ACSPs uses the two blocks (Block A and Block B) iteratively like a double buffer so that the partial path metrics corresponding to the previous node will only get overwrite after obtaining all the partial path metrics of the current node. The path metric information originally stored in Block A will be calculated with a corresponding branch metric and stored in Block B, and subsequently, the path metric information of Block B will be calculated with a corresponding branch metric and stored in Block A, and so on.

The read/write selection rule, also called the routing rule defined by the fixed routing unit for accessing the memory banks is analyzed using the following steps. The number of states is relevant to the constraint length (n+1) of an input symbol for decoding, 2n, and a unique state index Sn−1. . . S2S1S0is assigned to each state. In the first embodiment, constraint length of the encoder is 5 (n=4), resulting sixteen (2n=16) states. The number of memory banks is 2m+1, wherein m+1 must be less than or equal to n. In the first embodiment, m is chosen to be 2, so there are eight memory banks. The bank index Sn−1Sn−2. . . Sn−m−1and the ACSP index Sn−2Sn−3. . . Sn−m−1are indexes indicating the corresponding memory banks and the ACSP.

In the first embodiment, where n=4 and m=2, the memory element with a state index S3S2S1S0denotes that it is included in the memory bank with a bank index S3S2S1, for example, the memory element with state index 0010 is included in the bank001. Each ACSP reads two partial path metrics stored in the memory elements with state index S3S2S1S0according to its ACSP index S2S1. For example, ACSP10reads the partial path metrics stored in the memory elements with state index 0100 or 0101, and state index 1100 or 1101. After the ACSPs generate new partial path metrics, the new partial path metrics will be wrote in the memory elements with state index S3S2S1S0having the two most significant bits (S3S2) identical to the ACSP index. For example, ACSP10writes the new partial path metrics in the memory elements with state index 1000 or 1001, and state index 1010 or 1011.

FIG. 8shows a diagram of path metric memory access for Turbo decoding according to the first embodiment of the invention. The routing rule for Turbo decoding is almost the same as Viterbi decoding, thus they can share the fixed routing unit, the ACSP array, and the memory banks stored in the path metric calculation unit. For Turbo decoding, it is necessary to perform bit reversion for the state index, which means that the memory element with state index 001 becomes 100, and the memory element with state index 011 becomes 110. As shown inFIG. 8, the read/write connections between the memory banks and the ACSPs are identical to the previously described Viterbi decoding, the state indexes (not shown) and the corresponding bank indexes are however been reversed.

As shown inFIG. 4, the BMC unit41computes the branch metric y, whereas the path metric calculation unit421stores the forward path metric α and the backward path metric β computed by the ACSP array423. The three metrics α, β and γ are used in the selection and MAP calculation unit424for obtaining a log-likelihood ratio (LLR) as shown in the following.

Turbo decoding in the first embodiment of the invention utilizes the MAP decoding algorithm to calculate the LLR at each time point according to the branch metric γ, forward path metric α, and backward path metric β.

Second Embodiment

FIG. 9illustrates the path metric memory access according to the second embodiment of the invention. In the second embodiment, constraint length of the encoder is 6 (n=5), thus there are thirty-two (25) states for Viterbi decoding. Four ACSPs (2m, m≦4, choose m=2) and eight memory banks (2m+1) are chosen in the second embodiment. Since there are four memory elements in each memory bank, and each ACSP can only access one memory bank during one cycle, each ACSP needs to read the partial path metrics from the two corresponding memory banks in a first memory block four times, one for each memory element, and similarly, write the newly generated partial path metrics in the two corresponding memory banks in the second memory block four times. The routing rule for reading and writing the memory banks is identical as the first embodiment.

Third Embodiment

FIGS. 10aand10billustrate the path metric memory bank organization and the data structure corresponding to the path metric memory bank for 256-state Viterbi decoding according to the third embodiment of the invention. In the third embodiment, constraint length of the encoder is 9, and again, four ACSPs and eight memory banks are used. Every path metric memory bank has two memory blocks (Block A and Block B), and the block index for Block A and Block B are 0 and 1 respectively. The four ACSPs processes eight states during each cycle, thus for decoding a Viterbi code word with 256 states per code word, the ACSPs spend 32 cycles (256/8 =32) for reading and writing partial path metrics of a node from/in the memory banks.

The same hardware (i.e. ACSPs and memory banks) for 256-state Viterbi decoding is appropriate for 8-state Turbo decoding in terms of processing speed and memory size. For Turbo decoding, constraint length of each encoder is 4(n=3), causing eight possible states.FIG. 11shows the data structure in the path metric memory bank for Turbo decoding according to the third embodiment of the invention. The state index for Turbo decoding is different from Viterbi decoding as it requires bit reversion. The window size in the third embodiment is set to be thirty-two (k=32), and such Turbo decoding decodes a Turbo code word according to thirty-two entries of backward path metric β. In every cycle, the ACSPs process eight states to obtain a backward path metric β and stored in the memory bank according to time sequence t, t+1, t+k−1. In k cycles (k=32 in this embodiment), the ACSPs process 8k (8※32=256) states, and a total of k entries of backward path metrics β and one entry of forward path metric α are generated and stored in the memory bank.

The selection and MAP calculation unit424inFIG. 4obtains the branch metric γ from the BMC unit41, as well as the thirty-two backward path metrics β and one forward path metric α from the memory banks stored in the path metric calculation unit421, and calculates a log-likelihood ratio (LLR) based on these metrics. The result of the selection and MAP calculation unit is outputted to the interleaver/de-interleaver44to generate the result for Turbo decoding.

FIG. 12illustrates the MAP decoding algorithm used in Turbo decoding. There are only four stages of four states are shown inFIG. 10. A backward path metric β is calculated at each stage, but the forward path metric α is only calculated once per code word. The LLR indicates the log of a ratio between probability of one P(1) and probability of zero P(0).

The Viterbi/Turbo unified decoder of the invention is configurable depending on the type of receiving data, and the control circuit is designed to be capable of storing and computing partial path metrics for both Viterbi and Turbo decoding. The routing rule for the ACSP array to access the memory banks is fixed for both decoding types. In an embodiment, the memory banks for storing the partial path metrics are efficiently used in both Viterbi and Turbo decoding. For example, if the decoder is designed to receive either a 256-state Viterbi code word or an 8-state Turbo code word, the window size for Turbo decoding is chosen to be 32 (256/8). The memory banks store eight states of backward path metrics corresponding to 32 time points (stages) when decoding an 8-state Turbo code word, whereas for decoding an 256-state Viterbi code word, the ACSP array processes 8 states during one cycle, thus requires 32 cycles. The memory size and the processing time for the two decoding are therefore approximately the same. In another embodiment, a plurality of Viterbi/Turbo unified decoder of the invention are employed for decoding a bunch of data streams comprising Turbo symbols or/and Viterbi symbols, each decoder is capable of decoding any type of input. The decoding time for each decoder is designed to be approximately the same regardless the decoding scheme. An advantage of such design is to reduce the number of decoder required since each decoder can be used to decode both Viterbi and Turbo code words. Another advantage is that all the decoders can finish the decoding process at approximately the same time, so that the decoders can work in parallel without waiting for the processing delay of certain decoders.

Finally, while the invention has been described by way of example and in terms of the above, it is to be understood that the invention is not limited to the disclosed embodiment. On the contrary, it is intended to cover various modifications and similar arrangements as would be apparent to those skilled in the art. Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.