Memory-minimized architecture for implementing map decoding

The present invention provides a method, computer medium, firmware, and device for minimizing memory requirements for computations for decoding using Maximum Likelihood Probability MAP-based decoding. The method includes the steps of: computing corresponding alpha .alpha. values and beta .beta. values simultaneously and storing in memory said alpha .alpha. values and beta .beta. values computed for .alpha. at time k=1,2, . . ., N/2 and .beta. at time k=N, . . . , (N/2)+1; and computing soft output data for alpha at time k=(N/2)+i and beta at time (N/2)-i+1, i being a positive integer, for N.gtoreq..alpha.>N/2 and 1.ltoreq..beta..ltoreq.N/2, wherein .alpha. and .beta. are parameter values computed by forward and backward recursion, respectively, based on transition probabilities of a selected channel and on input binary data at discrete time k and a parity bit corresponding to one of: a first recursive systematic convolutional encoder and a second recursive systematic convolutional encoder.

FIELD OF THE INVENTION
 The present invention relates to Parallel (Turbo codes) or Serial
 Concateneated Convolutional codes. More specifically, the present
 invention relates to the architecture for implementing parallel or serial
 concatenated convolutional codes for MAP-based decoding algorithms. Both
 parallel and serial concatenated convolutional codes are referred to as
 Turbo codes for simplicity.
 BACKGROUND OF THE INVENTION
 In all different types of MAP-based (Maximum A Posteriori probability)
 algorithms, the decoding of the MAP parameters, i.e., a.sub.k and B.sub.k
 parameters, that represent probabilities of the states of the trellis at
 time k conditioned on the past received signals and the probabilities of
 the trellis states at time k conditioned on the future received signals,
 respectively, is determined in a forward and backward recursion. As shown
 in FIG. 1, after computation (102) of .gamma..sub.j (R.sub.k,s',s), alpha
 and beta parameters for all N data bits are computed (104, 108) and stored
 (106, 110) in memory, where N is a preselected integer. Then the
 conditional joint probability .GAMMA..sub.i is computed (112) based on the
 N values for alpha and the N values for beta. This approach requires
 storing all the information related to alpha and beta information for the
 entire data block. The MAP decoding algorithm is described in more detail
 below.
 The MAP decoding algorithm is a recursive technique that computes the
 Log-Likelihood Ratio (LLR) as:
 ##EQU1##
 where R.sub.k ={d.sub.k.sup.r, y.sub.k.sup..eta. } and s' and s are the
 previous and current states of the system. d.sub.k.sup.r and
 y.sub.k.sup..eta. are the received data and parity bit from the i-th
 encoder. .alpha..sub.k (s) and .beta..sub.k (s) are computed recursively
 as:
 ##EQU2##
 where h.sub..alpha. and h.sub..beta. are normalization factors.
 .gamma..sub.j (R.sub.k,s',s) is computed from transition probabilities of
 the channel, and here the channel is assumed to be a discrete Gaussian
 memoryless channel. .gamma..sub.j (R.sub.k,s',s) is described as:
EQU .gamma..sub.j (R.sub.k,s',s)=Pr{R.sub.k.vertline.d.sub.k =j, S.sub.k =s,
 S.sub.k-1 =s'}.times.Pr{d.sub.k =j.vertline.S.sub.k =s, S.sub.k-1
 =s'}.times.Pr{S.sub.k =s .vertline.S.sub.k-1 =s'} (4)
 The second term in (4) is the transition probability of the discrete
 channel; the third term is equal to 1 or 0 depending on whether it is
 possible to go from state s' to state s when the input data is j; and the
 fourth term is the transition state probabilities and, for equiprobable
 binary data, it is equal to 1/2. Considering R.sub.k ={u.sup.r.sub.k,
 y.sup.ri.sub.k }, u.sup.r.sub.k and y.sup.ri.sub.k are two uncorrelated
 Gaussian variables conditioned on (d.sub.k =j, S.sub.k =s, S.sub.k-1 =s'},
 therefore, the second term in (4) may be divided into two terms:
EQU Pr{R.sub.k.vertline.. . . }=Pr{u.sup.r.sub.k.vertline.. . .
 }.times.Pr{y.sup.ri.sub.k.vertline.. . . }
 If the Turbo block length is equal to N, all N data and parity bits must be
 received before the beta parameters are computed. Then, the backward
 recursion may be used to compute beta parameters using equation (3) above.
 Since the final soft output decoded data are computed using equation (1),
 all alpha and beta parameters for the entire data sequence are retained to
 finish the computations. If the memory length of recursive systematic
 convolutional (RSC) codes in Turbo code is equal to m, then a total of
 2.sup.m states exist for each decoder. Therefore, a total of
 2.sup.m.multidot. N memory space is required for keeping the alpha or beta
 parameters. Also, the decoded data will be available at the end after
 finishing computation of alpha and beta parameters and using equation (1).
 Thus, there is a need for a method, computer medium and device that
 minimize memory is requirements for computing MAP-based decoding
 algorithms.
 SUMMARY OF THE INVENTION
 The present invention minimizes the memory requirements to compute
 MAP-based decoding algorithms. The architecture used to implement the
 present invention minimizes the memory requirement for alpha and beta by a
 factor of 2. Since N, the Turbo block length, is usually a large number in
 Turbo codes, the architecture of the present invention provides a
 significant reduction in hardware requirements. The present invention may
 be implemented by software, firmware, or hardware; for example, hardware
 that may be utilized to implement the present invention includes, but is
 not limited to, an integrated circuit, a microprocessor, or an ASIC
 (application-specific integrated circuit) such as a VLSI chip that is
 presently being built by MITEL corporation.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
 As shown in FIG. 2, after computation (202) of .gamma..sub.j (R.sub.k,s',s)
 transition probabilities of the channel, the parameters alpha (204) and
 beta (208) are computed. The alpha and beta parameters are stored in
 memory (206, 210), and then the soft output values of the estimated data
 sequence are computed (212).
 Each recursive systematic convolutional (RSC) encoder consists of m memory
 elements; at each clock cycle, .alpha..sub.k (s) and .beta..sub.n-k+1 (s)
 parameters are computed simultaneously using 2.sup.m parallel hardware for
 all values of s=1, . . . , 2.sup.m and 1.ltoreq.k.ltoreq.N/2. All of the
 values of .alpha..sub.k (s) and .beta..sub.N-k+1 (s) are stored in memory.
 For (N/2)+1.ltoreq.k.ltoreq.N, at each clock cycle that 2.sup.m values for
 .alpha..sub.k (s) and .beta..sub.N-k+1 (s) are computed, equation (1) is
 used to compute .LAMBDA..sub.1 (d.sub.k). Clearly, .LAMBDA..sub.1
 (d.sub.k) is first computed for k=N/2 and (N/2)+1; and after that, at each
 clock cycle that .alpha..sub.k (s) and .beta..sub.N-k+1 (s) parameters are
 computed, .LAMBDA..sub.1 (d.sub.k) and .LAMBDA..sub.1 (d.sub.N-k+1) are
 immediately computed. The values of .alpha..sub.k (s) and .beta..sub.N-k+1
 (s) parameters for N/2+1.ltoreq.k.ltoreq.k.ltoreq.N are not stored any
 longer since it is no longer necessary to save them. With the present
 invention, the memory requirements for .alpha..sub.k (s) and .beta..sub.k
 (s) computation are reduced from 2.sup.m.multidot. N to
 2.sup.m-1.multidot. N. In many applications with Turbo code, N is a large
 number. Thus, the present invention provides a significant reduction in
 memory requirements for MAP-based decoding algorithms. In addition, the
 present invention allows a parallel architecture for MAP-based decoding
 algorithms to be utilized. Another advantage of the present invention is
 the fact that the soft output decoding for each iteration is immediately
 available after computation of .alpha..sub.k (s) and .beta..sub.k (s)
 parameters with minimum hardware requirements.
 There are M states for each convolutional encoder with m shift registers;
 then M=2.sup.m, i.e., for each alpha and beta there are M different values
 at each time k. In the prior art, alpha is computed from time k=1 up to
 k=N. When alpha has been computed, then beta was computed from time k=N
 down to k=1. Then the soft output for the decoder was computed.
 In contrast, as shown in FIGS. 2 and 3, in the present invention, first the
 data is received. d.sub.k is the input binary data at discrete time k.
 y.sup.1.sub.k and y.sup.2.sub.k are parity bits corresponding to the first
 and the second RSC encoders, respectively. Following computation of
 .gamma..sub.j (R.sub.k,s',s) (202) transition probabilities of the
 channel, the alpha at time k=1 (302) and beta at time k=N (304) are
 computed simultaneously and stored in memory. Then alpha at time k=2 (306)
 and beta at k=N-1 (308) are computed simultaneously and stored in memory.
 This process is continued up to k=N/2, where alpha for N/2 (310) and beta
 for k=(N/2)+1 (312) are computed. Then, each time alpha at time (N/2)+i
 (314, 318, 322, 326) and beta at time (N/2)-i+1 (316, 320, 324, 328) are
 computed, the soft output data .GAMMA..sub.(N/2)+i and
 .GAMMA..sub.(N/2)-i+1 are also computed (.GAMMA..sub.N/2 and
 .GAMMA..sub.(N/2)+1) at 330, .GAMMA..sub.(N/2)+2 and .GAMMA..sub.(N/2)-1
 at 332, .GAMMA..sub.(N/2)+i and .GAMMA..sub.(N/2)-i+1 at 334,
 .GAMMA..sub.N and .GAMMA..sub.1 at 336) where i is a positive integer.
 A device (342) for minimizing memory requirements for computations for
 decoding using Maximum Likelihood Probability MAP-based decoding in
 accordance with the present invention, also shown in FIG. 2, includes: an
 alpha-beta computation unit (338) for computing corresponding alpha
 .alpha. values and beta .beta. values simultaneously and storing said
 alpha .alpha. values and beta .beta. values for k=1, . . . , N/2 and k=N,
 . . . , (N/2)+1, respectively; and an alpha-beta-soft output computation
 unit (340), coupled to the alpha-beta computation unit (338), for
 computing alpha .alpha. values for N.gtoreq.k&gt;N/2 and beta .beta. values
 for 1.ltoreq.k.ltoreq.N/2 and a pair of soft output values corresponding
 to said alpha .alpha. values for N.gtoreq.k.gtoreq.N/2 and beta .beta.
 values for 1 is .ltoreq.k.ltoreq.N/2, wherein alpha .alpha. values and
 beta .beta. values are parameter values computed by forward and backward
 recursion, respectively, based on .gamma..sub.j (R.sub.k,s',s), which is
 determined based on transition probabilities of a selected channel.
 Alternatively, the device may include an integrated circuit, include a
 processor, include an application-specific integrated circuit, or may
 include a computer medium having computer-executable instructions for
 implementing at least part of a function of the computer unit/units.
 It should be understood that the foregoing description is only illustrative
 of the invention. Various alternatives, equivalents and modifications can
 be devised by those skilled in the art without departing from the
 invention. Accordingly, the present invention is intended to embrace all
 such alternatives, equivalents, modifications and variances which fall
 within the scope of the appended claims.