HK1061751B - Space-efficient turbo decoder - Google Patents

Description

Space efficient turbo decoder

Background

Technical Field

The present invention relates to wireless communication systems. More particularly, the present invention relates to an efficient memory enhancement decoder for use in a wireless Code Division Multiple Access (CDMA) communication system.

Technical Field

Cellular communication systems are characterized by a plurality of radio transceivers, e.g., mobile telephones, each including a transmitter and a receiver, which communicate with one or more base stations.

In a typical CDMA wireless transceiver, an analog Radio Frequency (RF) signal is received by an antenna and down-converted to an Intermediate Frequency (IF) by an RF section. The signal processing circuit performs noise processing and adjusts the amplitude of the signal through an analog Automatic Gain Control (AGC) circuit. The IF section then mixes the signal down with baseband and converts the analog signal to a digital signal. The digital signal is then input to a baseband processor for further signal processing such as turbo decoding to output sound or data.

Similarly, the transmitter receives a digital input from the baseband processor and converts the input to an analog signal. The digital input signal is often an enhancement coded signal. The signal is then filtered and converted up to an intermediate frequency by the IF stage. The gain of the transmit signal is adjusted and the IF signal is converted to RF in preparation for radio transmission.

The link between the transmitter and the receiver is a channel. To increase system capacity, receivers in mobile stations and base stations must operate at lower signal-to-interference ratios (SIRs), or the SIR of the channel must be increased. Special coding schemes are often employed to reduce the required SIR.

Encoding of the communication signal involves superimposing redundant information onto the signal. By strategically superimposing redundant signals on a communication signal transmitted in a noisy environment, the errors introduced by its noisy channel can be reduced to a desirable level. As pointed out by Claude Shannon in 1948, if the information rate of the communication signal is less than the capacity of the channel, a desirable noise level can be obtained without reducing the information rate. If no redundant signal is applied in a noisy environment, noise-free performance is difficult or impossible to achieve.

To improve the performance of wireless communication systems in noisy and Raleigh fading environments, interleavers are often employed after the signal encoder. The interleaver splits the codewords output from the encoder so that the individual bits of a given codeword are decomposed and transmitted at different time instances. Thus, the bits of a given code all undergo independent attenuation, so that the bits affected by a burst error belong to several codewords. At the receiver, the received signal samples are deinterleaved prior to decoding. There are several types of interleavers, including diagonal, convolutional, inter-block, and block interleavers.

An enhancement code is a serial or parallel concatenation of two or more constituent codes that have been separated by one or more code interleavers. Enhancement encoders and decoders are often used to improve error control and reduce the required SIR. The enhancement code is often decoded with an iterative algorithm to achieve a low error rate at signal-to-noise ratios (SNRs) close to the Shannon limit. As a basic part of the enhancement code, a code interleaver and a de-interleaver must be inserted between the composite code encoder and decoder, respectively. The performance of the enhancement code depends on the length and structure of the code interleaver. Good enhanced code performance can be achieved by using interleavers with a pseudo-random structure.

In a wireless CDMA communication system, an turbo encoder often produces a parallel concatenation of convolutional codes and an interleaved version of one or more of the codes. The encoder typically comprises one or more convolutional encoders connected by one or more interleavers. A corresponding turbo decoder typically includes a large number of (logrithmic maximum posteroiri) decoders connected by an inner and outer pair using a loop with an interleaver and a deinterleaver. The loop implements an iterative algorithm to estimate the Log Likelihood Ratio (LLR). In general, if LLR > 0, the decoded bit is most likely to be 1, and if LLR < 1, the decoded bit is most likely to be 0. Based on the LLR, the decoder output is either 1 or 0, indicating a hard decision. The recursive process for determining LLR is referred to as the Log-MAP algorithm and includes two instances of metric calculators, one recursive forward and the other recursive backward.

To increase the efficiency and reduce the cost of the turbo decoder, one or more of the composite decoders are often replaced by a multiplexer and two external memories. The control of the multiplexer is controlled by the signal of the turbo decoder loop, so that a single decoder can replace one or more decoders while keeping the turbo decoder functional integrity.

Unfortunately, such turbo decoders often require at least two external memories, one to store information from a loop portion and the encoder to be used for the other loop portion, and vice versa. External memory banks are typically large and expensive, which results in large and expensive wireless communication devices.

Thus, there is a need in the art for an enhanced decoder that is cost-effective and space-efficient to use in a CDMA system without the need for dual external memory banks. There is also a need for a wireless communication system that utilizes a space-efficient turbo decoder and a method of eliminating the need for dual memories in a corresponding turbo decoder. There is also a need to apply an efficient dual port external memory to the space-efficient incremental decoder of the present invention.

Disclosure of Invention

There is a need in the art for a system that eliminates redundant memory banks in a digital circuit while maintaining the full functionality of the digital circuit. In an illustrative embodiment, the disclosed turbo decoder circuit is suitable for use in a turbo decoder of a wireless communication system. The disclosed turbo decoder includes a first mode of operation in which the turbo decoder uses a first functional loop. The first functional loop includes a memory bank, a read interleaver, a first Multiplexer (MUX), a RAM file, a Log-MAP decoder, a write interleaver, and a second MUX. The disclosed turbo decoder further comprises a second mode of operation in which a second functional loop is used. The second functional loop includes a memory bank, a first MUX, a RAM file, a Log-MAP decoder, and a second MUX.

In one embodiment, the memory bank is a dual port external memory. The disclosed turbo decoder circuit switches between a first mode and a second mode.

The disclosed method and apparatus eliminates the need for two external memories in an enhancement decoder by selectively applying a single external memory in two separate decoder functions and two different modes of operation.

Drawings

Fig. 1 is a block diagram of a wireless communication system constructed in accordance with the techniques disclosed herein.

Fig. 2 is a detailed schematic diagram of a conventional turbo encoder suitable for use in the communication system of fig. 1.

Fig. 3 is a block diagram of a conventional turbo decoder.

Fig. 4 is a detailed block diagram of the space-efficient turbo decoder of fig. 1 having only one external memory.

FIG. 5 is a timing diagram illustrating read and write timing of the turbo decoder shown in FIG. 4.

FIG. 6 is a detailed schematic diagram of the space efficient external memory shown in FIG. 4.

Fig. 7 is a schematic diagram of a conventional CDMA 2000 enhanced code interleaver for reading and writing the dual port external memory shown in fig. 6.

Detailed Description

While the method and apparatus of the present disclosure has been discussed herein with reference to illustrative embodiments suitable for particular applications, it should be understood that the invention is not limited to such discussion. Those skilled in the art and knowledgeable in the art of the technology provided herein will readily recognize other modifications, applications, and embodiments within the scope of the invention and additional fields in which the invention would be of significant utility.

Fig. 1 is a block diagram of a wireless communication system 10 constructed in accordance with the techniques disclosed herein. For simplicity, various components such as antennas, power supplies, clock circuits, amplifiers, etc. are not shown in FIG. 1, but are well known to those skilled in the art and, therefore, will understand how to implement the functions of these components.

The system 10 includes a transmitting device 12 and a receiving device 14. The transmitting device includes an information source 16, a source encoder 18 and a transmitter 20. The transmitter 20 includes an enhancement encoder 22, a channel interleaver 24 and a modulator 26. The output of the information source 16 is input to a source encoder 18. The output of the source encoder 18 is input to an enhancement encoder 22 of the transmitter 20. The output of the turbo encoder 22 is input to a channel interleaver 24. The output of the channel interleaver 24 is input to a modulator 26.

The sink device 14 comprises a sink 28 connected to a source decoder 36, the source decoder 36 being connected to an information store 38. Receiver 28 includes a demodulator 30, a channel deinterleaver 32, and a special spatially efficient turbo decoder 34 constructed in accordance with the techniques disclosed herein. The input of demodulator 30 is connected to the output of modulator 26 of transmitting device 12 via a wireless channel 40. The output of the demodulator 30 is connected to the input of a channel deinterleaver 32. An output of the channel deinterleaver 32 is connected to an input of an enhancement decoder 34. The output of the turbo decoder 34 is input to a source decoder 36, and the output of the source decoder 36 is input to an information store 38. As will be discussed more fully below, the turbo decoder 34 provides optional proportional feedback to the channel deinterleaver 32.

In operation, an information source 16 provides a sound signal or other data to a source encoder 18. The information source 16 may be a person, an input device such as a keyboard or microphone, or other digital source, such as a network. Source encoder 18 digitally encodes information provided by information source 16 into a predetermined electronic format that may be suitable for use by enhancement encoder 22. Source encoders are well known in the art. The details of source encoder 18 depend on the particular application and may be selected by one skilled in the art to meet the requirements of a given application.

The output of the source encoder 18 appears as a stream of digital binary bits dk, which are either 1 or 0. In the present embodiment, the enhancement encoder 22 encodes the bits dk into an enhancement code representing a parallel concatenation of Recursive Systematic Convolutional (RSC) codes. The final enhancement coded bits are input to a channel interleaver 24. Channel with a plurality of channelsThe interleaver 24 reorders the input bits by a pseudo-random permutation function d so that at the ith^thThe bits of a position are moved to the α (i) position according to the pseudo-random law α. The interleaver 24 is implemented in the form of a block interleaver which reads data row by row into a memory block and column by column.

The reordered bits are input to a modulator 26 that prepares the digital enhanced coded interleaved digital signal for transmission over a wireless channel 40. The modulator 26 includes a baseband-IF mixer (not shown) that up-converts the digital baseband signal output by the channel interleaver 24 into an IF signal and an IF-RF mixer (not shown) that converts the IF signal into an RF signal to be radio-transmitted through the channel 40. The modulator 26 also performs functions such as Pseudo Noise (PN virtual Noise) propagation in which in-phase and quadrature signal components are mixed with corresponding PN functions in preparation for wireless transmission. Modulator 26 also superimposes the pilot signal on output signal 42 for transmission through a transmit antenna (not shown) to channel 40.

The demodulator 30 of the receiving device 14 receives the wireless signal 42 output from the modulator 26 of the transmitting device 12 and transmitted over the wireless channel 40. In this embodiment, the wireless signal 42 is a Code Division Multiple Access (CDMA) signal and the system 10 is a CDMA system. Demodulator 30 includes a channel estimator and a tilt receiver followed by RF-IF and IF-baseband circuitry (not shown). As is well known in the art, a rake receiver is a multi-stage receiver having several sets of associated receivers. Each stage estimates the signal received from each user of the system 10. The final estimates are accumulated and then subtracted from the total received signal. Then, together with an estimate of the desired signal received from the user's transmitting device 12, a residual signal is generated and bit estimates are made.

Demodulator 30 demodulates received signal 42 and provides a corresponding digitally demodulated signal to channel deinterleaver 32. The channel deinterleaver 32 passes the permutation function α^-1Deinterleaving the demodulated signal by a permutation function which is the inverse of the permutation function alpha of the channel interleaver 24And (4) counting. In this embodiment, the channel deinterleaver 32 outputs a bit sequence representing a parallel concatenation of constituent RSC codes with the addition of additional noise and interference terms superimposed by the radio channel 40. The enhancement decoder 34 decodes the deinterleaved bitstream using the well-known Log-MAP algorithm.

Unlike conventional turbo decoders that require two or more separate external memories and/or two or more separate Log-MAP decoders, turbo decoder 34 is space efficient, requiring only one external memory and one Log-MAP decoder. Thus, the turbo decoder 34 can be made smaller and less expensive than its conventional counterpart. This helps to reduce the size and cost of the associated receiver system 14 of the digital communication system 10.

Decoded signal output from turbo decoder 34Is a digital signal input to the enhancement encoder 22 of the transmitting device 12Is estimated. Then, the decoded signalFurther decoded and formatted by a source decoder 36 to prepare an information base 38 for output.

Fig. 2 is a detailed schematic diagram of a conventional turbo encoder 22 suitable for use in the communication system 10 shown in fig. 1. The following discussion of the conventional enhancement encoder 22 will aid in understanding the method and apparatus of the present disclosure.

The enhancement encoder 22 includes a first delay 50, a second delay 52 and an interleaver (pi) 54, each of which receives as input a digital bit stream dk. Output y of the first delayer 50_okIs input to the interpolation circuit 56. The output of the second delayer 52 is input to a first encoder 58, the output y of which is_1kTo the interpolation circuit 56. The output of the interleaver 54 is input to a second encoder 60, the output of which isy_2kTo the interpolation circuit 56. Interpolation circuit 56 provides an output to channel interleaver 24 shown in fig. 1. In the present embodiment, the first encoder 58 and the second encoder 60 are both RSC encoders.

In operation, the first delayer 50 delays the digital input sequence d_kAnd corresponding shifted number sequence y_okOutput to the interpolation circuit 56. The second delayer 52 delays the digital input sequence dk and provides a corresponding shifted output to the first encoder 58. The first encoder 58 encodes the delayed digital sequence using convolutional code techniques. The encoder 58 then encodes the corresponding encoded digital signal y_1kOutput to the interpolation circuit 56. Similarly, the second encoder 60 encodes the digital interleaved sequence output by the interleaver 54 with a predetermined permutation function pi. The encoder 60 then encodes the corresponding encoded signal y_2kOutput to the interpolation circuit 56.

The interpolation circuit 56 converts the parallel signal y_0k，y_1kAnd y_2kOrdered into a single sequence, i.e., the enhancement code provided to the channel interleaver 24 shown in fig. 1. The interpolation circuit may also adjust the code rate of the output signal to meet the needs of a given application. The enhancement encoder 22 shown in fig. 2 is an 1/3 rate enhancement encoder in which a data sequence of k input bits is mapped to a codeword of 3k symbols. The output of the interpolation circuit 56 is an 1/3 rate code, but the code rate may be increased by interpolation (e.g., to 1/2).

The well-known Viterbi algorithm is often used for conventional convolutional code decoding, such as from the output of the first RSC encoder 58 code. The Viterbi algorithm computes a maximum approximation (maximum likelihood) scheme that represents the sequence of transmitted data bits m, giving the probability of receiving the sequence y. If we know the apriori information, ML is worse than MAP (without apriori information, then ML and MAP algorithms are substantially equal), and turbo decoding is to estimate apriori information and use it for MAP decoding.

To decode the enhancement encoded signal 42 output by the modulator 26 shown in fig. 1, the following equations (1) through (4) are iteratively solved by the decoder 70:

wherein a negative sign on a variable represents its interleaved value; and

Λ_1kto estimate the sum of received dataA first Log-Likelihood Ratio (LLR) of interest;

to sum and estimateIn an interleaved formLog-likeness ratio of interest (Log-likeliodoratio ratio (llr));

y₀is the observed systematic bit y output from the delay 50 shown in FIG. 2_0kA sequence of (a);

represents an interleaved version of y 0;

y₁is the parity bit y output from the first constituent encoder 58 of fig. 2_1kA sequence of (a);

y₂is the parity bit y output from the second constituent encoder 60 of fig. 2_2kA sequence of (a);

representative ratioTez is a compound of formula (I)_1kRepresents the bit z when in the first mode_1kRepresents extrinsic information referred to as the Log-MAP decoder 76 output, as discussed more fully below;

z₂a vector representing extrinsic information z2k output from the Log-MAP decoder 76 when in the second mode (as will be discussed more fully below).

Λ 1k is defined in equation (1) as the logarithm of the ratio of the possibilities of the two conditions. The molecule is represented in y₀，y₁And z₂Received data bit estimation under received conditionsRepresenting the possibility of 1. Denominator is represented in y₀，y₁And z₂Received data bit estimation under received conditionsRepresenting the probability of 0.

In a similar manner to that described above,defined in equation (2) as the logarithm of the ratio of the possibilities of the two conditions. The molecule is represented in y₀，y₂And z₁Data received in the received conditionThe interleaved version of (a) represents a probability of 1. Denominator is represented in y₀，y₂And z₁Data received in the received conditionRepresents the probability of 0.

External information bit z_1kAnd z_2kΛ of LLR by the following equation and equations (1) and (2), respectively_1kAnd Λ_2kThe following steps are involved:

wherein the variables are defined as previously provided.

Estimation of received dataThe output from hard decision circuit 82 through hard limit Log-MAP decoder 76 is obtained according to the following equation:

the LLRs of equations (1) and (2) are iteratively calculated by enhancement decoder 70 using the well-known Log-MAP algorithm, which is more fully described in the preliminary report published by Virginia Tech in 9 months 1998 and in the article entitled "iterative detection and decoding for wireless communications" written by m.c. valenti. The iterative process is performed in a "window" of information provided by the de-interpolation circuit 72. The information window is cycled through the decoder 70 several times before the next window of data is read from the de-interpolation circuit 72. In the disclosed embodiment of the method and apparatus, the window is equal to 32 words, each of which is a 6-bit value that represents a soft decision made on a bit of the encoded data.

In operation, first, the de-interpolation circuit 72 de-interpolates signals received from a channel de-interleaver, such as the de-interleaver 32 of fig. 1, using application specific methods well known in the art. The de-interpolated signal represents three vectors y as defined above₀，y₁And y₂. The de-interpolated signal is input to a RAM file 74 which buffers the signal.

The decoder 70 can be considered to comprise two functional loops. The first functional loop includes an external memory 80, a read interleaver 90, MUX92, RAM file 74, a Log-MAP decoder 76, a write interleaver 78 and an external memory 88. The second functional loop includes an external memory 88, MUX92, RAM file 74, Log-MAP decoder 76 and external memory 80.

When the decoder 70 is in the first mode of operation, the decoder employs a first functional loop portion. In contrast, when the decoder 70 is in the second mode of operation, the decoder employs a second functional loop portion. The first time the first mode of operation occurs, the contents of the RAM file 74 are clocked into the Log-MAP decoder 76. During a first pass of the first mode of operation, the Log-MAP decoder 76 estimates Λ of the LLR of equation (1) using the data provided by the interpolation circuit 72 and a predetermined initial value for z (since there are no prior values from the Log-MAP decoder 76 to produce the current value for z)_1k. In one embodiment, the initial value of z is zero.

The output of the Log-MAP decoder 76 is input to a write interleaver 78. The write interleaver 78 is used in conjunction with an external memory 88 to implement an interleaving function on the output from the Log-MAP decoder 76. Meanwhile, the output from the Log-MAP decoder 76 is stored in the second external memory 80.

The turbo decoder then switches to the second mode of operation. In the second mode of operation, the MUX92 selects the output from the first external memory 88. The write interleaver 78 and the first external memory 88 include an interleaving function. MUX92 couples the output of first external memory 88 to RAM file 74 which stores the data. The output from the RAM file 74 is coupled to a Log-MAP decoder 76. Thus, it can be seen that in the second mode of operation, the Log-MAP decoder 76 provides data stored in the first external memory 88. The output of the first external memory 88 represents interleaved external informationLog-MAP decoder 76 calculates the values according to equation (2) provided aboveOutput from Log-MAP decoder 76Is coupled to and stored in a second external memory 80.

After the second mode of operation is complete, the turbo decoder 70 switches back to the first mode of operation. In a first mode of operation, mode selector circuit 94 selects the output of read interleaver 90 as the output of MUX 92. The second external memory 80 and the read interleaver 90 perform the de-interleaving function. The output of the read interleaver 90 represents extrinsic informationThus, the external information z₂Read from read interleaver 90 and output by MUX92 to RAM file 74. It should be noted, however, that during the first pass of the first mode of operation (described above), the value of z is set to a pre-determined value as indicated aboveAn initial value is determined first. Thus, the output Λ from the Log-MAP decoder 76_1kAnd the resulting value z output from the read interleaver 90 is not used in the first iteration of the decoding process. However, in the second pass of the first mode of operation, the RAM file 74 will store y₀，y₁And z₂The value is output to the Log-MAP decoder 76.

In any case, during the first mode, the output from the RAM file 74 is coupled to the Log-MAP decoder 76. Log-MAP decoder 76 calculates Λ_1kThe value of (c). Then Λ_1kIs coupled to the write interleaver 78. The output from the write interleaver 78 is then coupled to a first external memory 88. Write interleaver 78 and memory 88 generate valuesThe first external memory 88 stores a valueUntil the turbo decoder 70 switches to the second mode of operation.

Thus, in the first mode of operation, the external information z₂Reads from the second external memory 80 and is coupled by MUX92 and RAM file 74 to the Log-MAP decoder 76, and the output of the Log-MAP decoder 76 is coupled to the write interleaver and written to the first external memory 88. In the second operation mode, the deinterleaved external information z outputted from the first external memory 88₁Is output from MUX92 and coupled by MUX92 and RAM file 74 to Log-MAP decoder 76. The output from the MUX92 is coupled to and stored in the second external memory 80.

For each iteration, the mode of the turbo decoder 70 continues to alternate between the first mode of operation and the second mode of operation. The output of the Log-MAP decoder 76 is specified by a hard decision circuit 82 for each predetermined number of iterations. According to one embodiment of the disclosed method and apparatus, the turbo decoder 70 performs 10 iterations. Thus, after a predetermined number of iterations, hard decision circuit 82 outputs a hard decisionThe output is the initial data input to a corresponding enhancement encoder, such as enhancement encoder 22 of transmitter 12 of FIG. 1And is used to generate the values received from the de-interpolation circuit 72. Enhanced decoder output for hard decision circuit 82Is fed forward to a source decoder, such as source decoder 36 shown in fig. 1.

Legacy turbo decoders require two or more Log-MAP decoders, one corresponding to the Log-MAP decoder 76 in the first mode of operation and another corresponding to the Log-MAP decoder 76 in the second mode of operation.

Fig. 4 is a block diagram of the spatially efficient turbo decoder 34 of fig. 1. Various components such as power supplies, clock circuits, amplifiers, etc. are omitted from fig. 4 for clarity. However, those skilled in the art will know where and how to implement any required elements not shown. The turbo decoder design of the spatially efficient turbo decoder 34 eliminates the need for two separate external memories, such as the two memories 80 and 88 of fig. 3.

The spatially efficient turbo decoder 34 includes a de-interpolation circuit 72, a RAM 74 and a Log-MAP decoder 76. The output of the Log-MAP decoder 76 is connected to the write interleaver 78, a first input of a first MUX100, a hard decision circuit 82 and a signal-to-noise ratio (SNB) estimation circuit 102. The output of the SNB estimation circuit 102 is input to a microprocessor/controller 104 which provides proportional feedback to the channel deinterleaver 32 shown in fig. 1 which provides an input to the de-interpolation circuit 72. The output of the write interleaver 78 is connected to a second input of the first MUX100, the output of the first MUX100 being input to the dual port external memory 110. The output of the dual port external memory 110 is connected to a first input of the second MUX 104 and to an input of the read interleaver 106. The output of read interleaver 106 is coupled to a second input of second MUX 104. The output of second MUX 104 is input to RAM 74. Mode controller circuit 108 is coupled to control terminals of first MUX100, second MUX 104, and dual port external memory 110. Mode controller circuit 108 controls the switching of the MUX to selectively and periodically switch the mode of the turbo decoder 34 between the first and second modes of operation, as discussed more fully herein.

The operation of turbo decoder 34 is functionally similar to turbo decoder 70 of fig. 3. However, fig. 3 includes: the write interleaver 78, first external memory 88, second external memory 80, read interleaver 90, 2:1MUX 92, and mode selector 94 are replaced with circuitry shown in FIG. 4 that includes write interleaver 78, first MUX100, dual port external memory 110, read interleaver 106, second MUX 104, and mode controller 109. Thus, the first functional loop in the disclosed decoder 34 of FIG. 4 includes a dual port external memory 110, a read interleaver 106, a second MUX 104, a RAM file 74, a Log-MAP decoder 76, a write interleaver 78, and a first MUX 100. The second functional loop in the disclosed decoder 34 of fig. 4 includes dual port external memory, a second MUX 104, a RAM file 74, a Log-MAP decoder 76, and a first MUX 100.

The first functional loop is used in a first mode of operation. In a first mode of operation, dual port external memory 110 is read by read interleaver 106, the output of which is selected as the output of second MUX 104 under the control of mode controller 108. Thus, similar to the turbo decoder 70 shown in FIG. 3, in the first mode of operation of the decoder 34, the output of the read interleaver 106 is fed back to the RAM 74. The output from the RAM file 74 is coupled to a Log-MAP decoder 76. The output from the Log-MAP decoder 76 is coupled to a first MUX 100. Mode controller 108 causes MUX100 to select the output from write interleaver 78. Thus, the output from the write interleaver 78 is coupled to and stored in a dual port external memory 110. Similar to the operation of decoder 70 shown in FIG. 3, in the first mode of operation, the output of Log-MAP decoder 76 is LLR Λ_1kIs estimated (see equation 1).

However, the turbo decoder 70 shown in fig. 3 requires two external memories, whereas the decoder 34 shown in fig. 4 only requires one external memory 110 that is readable and writable. In actual operation, the single external memory 110 is much smaller than the two external memories 80 or 88. Experimental results have shown that the dual port external memory 110 is about 2.542 square millimeters compared to 4.356 square millimeters for the two external memories 80 and 88. This represents a 41.6% reduction in memory space or a 1.814 square millimeter savings in space. Such savings are apparent.

In a second mode of operation, the mode controller 108 causes the second MUX 104 to select the output of the dual port external memory 110. Thus, the interleaved external output z of the dual port external memory 110₁Is fed back to the RAM file 74. An output of the RAM file 74 is coupled to an input of a Log-MAP decoder 76. Thus, the Log-MAP decoder 76 estimates the Λ representing the interleaved LLR_2k(see equation (2)). Mode controller 108 causes second MUX 104 to select the output of Log-MAP decoder 76. Thus, the output of the Log-MAP decoder 76 is written to the dual port external memory 110. Thus, the operation of the decoder 34 shown in fig. 4 in the second mode of operation is similar to the operation of the decoder 70 shown in fig. 3 in the second mode of operation.

In the first mode of operation, the write interleaver 78 and the dual port external memory 110 function as an interleaver, i.e., a first functional portion, while the dual port external memory 110 and the write interleaver 78 function as a deinterleaver, i.e., a second functional portion. For the purposes of this discussion, the term "functional portion" refers to each portion that differs from one another by function. Note that according to the above definition, a single circuit implementing two different functions may be considered to have a first functional part and a second functional part corresponding to the first function and the second function, respectively.

Thus, in the first mode of operation, the inputs to the Log-MAP decoder 76 are de-interleaved by functional blocks 110 and 106. The output of the Log-MAP decoder 76 is de-interleaved by functional blocks 78 and 110 and stored in dual port memory for use in the second mode of operation. Thus, the inputs coupled to the Log-MAP decoder 76 in the second mode of operation are previously deinterleaved by the functional blocks 78 and 102 in the first mode of operation.

The output of the Log-MAP decoder 76 is utilized by the SNR estimation circuit 102 to calculate the signal-to-noise ratio (SNR) according to methods known in the art. The resulting SNR is provided to a microprocessor/controller 104 which calculates a channel interleaver scaling value. The details of the calculation of the ratio are application specific and can be determined by one skilled in the art to meet the needs of a given application. This ratio value is fed back to the channel interleaver 32 shown in fig. 1, which appropriately adjusts the channel interleaving function to react to this. Those skilled in the art will appreciate that the channel interleaving feedback channel formed by SNR estimation circuit 102 and microprocessor/controller 104 may be omitted.

Although the present discussion only refers to 1/3 rate turbo decoders, those skilled in the art will appreciate that the disclosed methods and apparatus may be applied to turbo decoders of different rates. Those skilled in the art and familiar with the art will appreciate that the turbo decoder of fig. 4 can be easily scaled or adjusted to accommodate the needs of different decoder ratios or different given applications.

In this embodiment, read interleaver 90 and write interleaver 78 are constructed in accordance with the CDMA 2000 Telecommunications Industry Association (TIA) standard. Interleavers 78 and 90 perform memory address calculations for data to and from external memory 110, these calculations being used as control inputs to dual port external memory 110.

After each certain number iteration (e.g., ten iterations), hard decision circuit 82 hard limits the output of Log-MAP decoder 76 according to equation (5) or a similar equation. The output of hard decision circuit 82 is data d output from source encoder 18 shown in FIG. 1_kEstimate d_k. Estimate d_kInput to the source decoder 36 of fig. 1 as shown.

In one embodiment, the number of turbo decoder iterations is fixed, between 10 and 20 iterations before hard decision circuit 82 samples from the output of Log-MAP decoder 76. The number of iterations, however, depends on the particular application and may be determined dynamically with reference to a quality criterion such as a Cyclic Redundancy Check (CRC) criterion. Thus, other embodiments may make more or fewer iterations, and the number of iterations may be adjusted in the decoder to suit the particular implementation.

Fig. 5 is a timing diagram illustrating read and write timings of the turbo decoder 34 shown in fig. 4. The contents of the two memory addresses of the dual port external memory 110 of fig. 4 are read within a given clock cycle loop of a clock signal sequence 120, and the contents of the two memory addresses are written in a subsequent clock cycle.

Fig. 6 is a detailed schematic diagram of the space-efficient dual-port external memory 110 shown in fig. 4. The dual port external memory 110 includes a first 1:2 Demultiplexer (DEMUX)130 that receives input from the write interleaver 78 or the Log-MAP decoder 76 shown in fig. 4 when the external memory 110 is in the first mode of operation or the second mode of operation, respectively. A first output of the first 1:2DEMUX 130 is connected to an input of a first 1:8DEMUX 132. A second output of the first 1:2DEMUX 130 is connected to an input of an input register 134. An output of the input register 134 is connected to an input of a second 1:8DEMUX 136. The eight parallel outputs of the first 1:8DEMUX are connected to the eight parallel outputs of the second 1:8DEMUX 136, each of which is in turn connected to an input of a different storage element, including a first storage element 138, a second storage element 140, a third storage element 142, a fourth storage element 144, a fifth storage element 146, a sixth storage element 148, a seventh storage element 150, and an eighth storage element 152. Each of the eight storage elements 138-152 is connected to one of the eight parallel input lines of the first 8:1MUX 154, where each of the parallel input lines of the first 8:1MUX 154 is connected to a corresponding parallel input line of the second 8:1MUX 156. The output of the first 8:1MUX 154 is connected to a first input of the 2:1MUX 158. The output of the second 8:1MUX is connected to the input of output register 160. The output of register 160 is connected to a second input of 2:1MUX 158. The output of the 2:1MUX 158 is provided to the RAM 74 shown in FIG. 4 and the read interleaver 106 of FIG. 4. The address selector 162 is coupled to control inputs of the DEMUX 130, 132, and 136 and the MUX 154, 156, and 158. Registers 134 and 160 receive control inputs that enable each other clock cycle through address selector 162 and/or mode controller 108 shown in FIG. 4. The address selector 162 receives inputs from the write interleaver 78, the read interleaver 106, and the mode controller 108 shown in FIG. 4. The write interleaver 78, read interleaver 106 and mode controller 108 provide control inputs to the dual port external memory 103.

In operation, referring to FIGS. 4 and 6, a bit stream representing LLRs output from the Log-MAP decoder 76 or interleaved LLRs output from the write interleaver 78 are input to the 1:2DEMUX 130. In the first mode of operation, the output of the Log-MAP decoder 76 is input to the 1:2DEMUX 130. The LLR bits corresponding to one symbol are written into a selected one of the eight storage elements 138 to 152.

If the external memory 110 is in an interleaver sub-mode, the external memory 110 writes linearly and reads interleaved, which represents the interleaving process. Similarly, when the external memory 110 is in the de-interleaver sub-mode, the external memory 110 interleaves the write linear reads, corresponding to the de-interleaving process.

In the interleaver sub-mode of the first mode of operation, the storage elements that write the LLR bits are based on a linear address that indicates the bit position of a given data frame. The external memory 110 may then be read out interleaved, i.e. the output of the MUX 158 represents the content of the storage elements having an interleaved form representing the linear addressing.

Before the external memory 110 is read, both storage elements are written. A storage element receives the LLR bits associated with a given symbol and has a linear address with 0 as the least significant bit. Another storage element, level 1, is the least significant bit of the linear address. After both storage elements are written, both storage elements are readable.

If the external memory 110 is in the deinterleaver sub-mode, the address selector 162 controls the inputs to the DEMUX 130, 132, and 136 such that the LLRs associated with a given symbol are written interleaved, i.e., to the storage elements associated with the interleaved address of the given symbol. The address of a given symbol corresponds to the de-interleaved bit position of a given data frame. Similarly, the translation of the outputs of MUXs 154, 156, and 158 is controlled by address controller 162 such that external memory 110 is linearly readable, i.e., the contents of the storage elements have a linear address determined by the bit positions of a given data frame.

The read function of the external memory 110 is the inverse of the write function of the external memory 110. For example, writing to the external memory 110 interleaved is similar to reading from the external memory 110 interleaved, but the operations are performed in the reverse order.

The address selector 162 receives inputs from the write interleaver 78, the mode controller 108, and the read interleaver 106 shown in FIG. 4. The address selector 162 uses these inputs to generate control signals for the MUX and DEMUX to write linearly, to write interleaved, to read sequentially and/or to read interleaved depending on the fact of the mode of operation. For example, in a first mode of operation, the external memory 110 functions as an interleaver and writes linearly and reads interleaved. In the second mode of operation, the external memory 110 functions as a deinterleaver and alternately writes (based on an interleaved address input from the write interleaver to the address selector 162) and linearly reads. The manner in which the external memory 110 is written to and read from is controlled by the address selector 162 according to the mode of operation determined by the control input received from the mode controller 108 shown in FIG. 4.

The fact that the mode selection circuit 94 can be implemented with simple timing and clocking circuitry will be apparent to those skilled in the art and will be understood by those skilled in the art. Also, read and write interleavers, such as interleavers 78 and 90, are known in the art.

Fig. 7 is a schematic diagram of a CDMA 2000 enhanced code interleaver 170 for reading and writing to the dual port external memory 110 shown in fig. 6. The enhanced code interleaver 170 may be modified by those skilled in the art to function as either the write interleaver 78 or the read interleaver 106 of FIG. 4.

Referring to fig. 4 and 7, in the present embodiment, the enhanced code interleaver includes a row/column separator 172 receiving an input address from the Log-MAP decoder 76. The input address represents the bit position of a given data frame.

The input address is m + n bits wide. The upper n bits of a given address symbol represent the column and the lower m bits represent the row. The row/column separator 172 outputs m row bits, i.e., the lower m bits, to a bit inverter 174 and a Look-Up Table (LUT) 176. Bit inverter 174 inverts the m bits and provides an output to row/column synthesizer 178. The LUT 176 outputs n bits to the multiplier 180, one bit per column.

The n columns of bits output from the row/column separator 172 are input to an adder 182 which, in response, adds 1 to the n columns of bits received and provides n output columns of bits to the input of the multiplier 180. In response thereto, the multiplier 180 multiplies the output of the LUT 176 and the output of the adder 182 and outputs n column bits to the row/column synthesizer 178. The row/column integrator 178 outputs m + n bits to the external memory 110, where the upper m bits represent the inverted m bits output from the bit inverter 174 and the lower n bits represent the output of the multiplier 180. The bad address output from the row/column synthesizer 178 is selected by the bad address determination circuit 184 and then deleted.

The external memory 102 of fig. 6 utilizes the specific interleaving address generation feature, that is, every two concatenated interleaving addresses will have one of the following addresses: 00 XXXXXX, 01XXXX, 10XXXX and 11 XXXX. The two addresses will not have the same most significant bits. For other interleaving schemes (e.g., for W-CDMA), one skilled in the art can readily determine the appropriate interleaving characteristics such that the two concatenated interleaving addresses differ in some manner, such as by a Look-Up Table mapping.

Those skilled in the art and informed by the present teachings will be able to implement additional modifications, applications, and embodiments within the scope of the disclosed method and apparatus. Accordingly, it is to be understood that the invention is limited only by the appended claims and is not limited to the specific methods and apparatus disclosed herein.

Claims (7)

1. An turbo decoding circuit having a first and second mode of operation, the turbo decoding circuit comprising:

(a) a first functional loop for a first mode of operation, the first loop comprising:

(1) a write interleaver having an input and an output;

(2) a dual port external memory having an input and an output, the input coupled to the write interleaver output;

(3) a read interleaver having an input and an output, the input coupled to the output of the dual port external memory;

(4) a buffer circuit having an input and an output, the input of the buffer being coupled to the output of the read interleaver; and

(5) a Log-MAP decoder having an input and an output, the input coupled to the output of the buffer and the output of the Log-MAP decoder coupled to the write interleaver; and

(b) a second functional loop for a second mode of operation, the second loop comprising:

(1) a dual port external memory;

(2) a buffer circuit having an input coupled to an output of the dual port external memory; and

(3) a Log-MAP decoder having an input coupled to an output of the buffer circuit and an output coupled to an input of the dual interface external memory.

2. The turbo decoder circuit of claim 1, further comprising:

(a) a multiplexer having an output and a first and second input, the first input coupled to the write interleaver and the second input coupled to the output of the Log-MAP decoder, the output of the multiplexer coupled to the input of the dual interface external memory; and

(b) a timing circuit coupled to the multiplexer;

wherein the multiplexer and timing circuit establish the first mode of operation and the second mode of operation by transitioning between the first functional loop and the second functional loop.

3. The turbo decoder circuit of claim 2, further comprising a second multiplexer, the second multiplexer having an output and a first and second input, the first input of the multiplexer being coupled to the output of the read interleaver, the second input of the multiplexer being coupled to the output of the dual port external memory, the output of the second multiplexer being coupled to the input of the buffer circuit.

4. The system of claim 3, wherein the dual port external memory is the only external memory employed by the loop to implement the log-max empirical algorithm.

5. A spatially efficient turbo decoder, comprising:

(a) a loop including a decoder, a write interleaver, a read interleaver and a first memory for implementing a log-max empirical algorithm; and

(b) a first multiplexer coupled between the decoder and the first memory and a second multiplexer coupled to an output of the read interleaver for selectively bypassing the write interleaver or the read interleaver in response to a control signal such that the decoder, the write interleaver, the read interleaver, and the first memory implement a log-max empirical algorithm.

6. The space-efficient turbo decoder of claim 5, further comprising a controller for generating a control signal to control the first and second multiplexers.

7. A spatially efficient turbo decoder, comprising:

(a) a channel deinterleaver in communication with a first memory;

(b) a Log-max post (Log-MAP) decoder connected at an output of the memory, an output of the Log-MAP decoder connected to a hard decision circuit, an output of the hard decision circuit providing an output of the space-efficient turbo decoder;

(c) a write interleaver connected to an output of the Log-MAP decoder, an output of the write interleaver being connected to a first input of a first multiplexer, a second input of the first multiplexer being connected to an output of the Log-MAP decoder, an output of the first multiplexer being connected to an input of a second memory;

(d) a read interleaver coupled to an output of the second memory, an output of the read interleaver coupled to a first input of a second multiplexer, a second input of the second multiplexer coupled to an output of the second memory, an output of the second multiplexer coupled to an input of the first memory, wherein the log-MAP decoder, the write interleaver, the second memory and the read interleaver are configured to implement a log-MAP algorithm; and

(e) a controller for selectively enabling the inputs of the multiplexer such that the Log-MAP decoder, the write interleaver, the second memory and the read interleaver can implement a Log-MAP algorithm.