# Patent

## Title
Hybrid ARQ transmission method with effective channel matrix and decision statistics resetting

## Abstract

A method for decoding of multiple wireless signals by a chase combining hybrid-automatic-repeat-request CC-HARQ receiver includes demodulating wireless signals received from respective mobile sources using an effective channel matrix and decision statistics; updating log-likelihood-ratios LLRs and decoding the received codewords using the corresponding updated LLRs; determining set of correctly decoded codewords using a cyclic redundancy check; updating the effective channel matrix and decision statistics responsive to the step of determining; and resetting the effective channel matrix and decision statistics in the event that the number of decoding errors for a codeword exceeds its maximum limit after storing the updated LLRs of all remaining erroneously decoded codewords for which the number of decoding errors is below the respective maximum limit.

## Background
This application claims the benefit of U.S. Provisional Application No. 61/049,794, entitled “Efficient receiver for Chase-Combining Hybrid ARQ”, filed on May 2, 2008, and U.S. Provisional Application No. 61/049,790, entitled “SINR Computation for Multi-Codeword Chase Combining Hybrid ARQ Systems”, filed on May 2, 2008, the contents of both which are incorporated by reference herein.


BACKGROUND OF THE INVENTION
The present invention relates generally to wireless communications, and more particularly, to a hybrid automatic-repeat-request (HARQ) reception method with channel state information.
HARQ systems combine ARQ and error control coding to achieve high throughput and high reliability. Unlike ARQ systems where packets decoded previously in error are simply discarded, in HARQ systems all the received signals are combined to enhance performance. Chase-combining HARQ (CC HARQ) is a simple HARQ scheme where the transmitter transmits the same codeword (using the same modulation and coding scheme) upon receiving a decoding error message from the receiver.
Referring to the diagram in FIG. 1, we consider a multiple access channel where K users 11-13 communicate with a base station 10 equipped with multiple antennas. The communication system in which the wireless users and base station communicate employs Chase-combining Hybrid-Automatic-Repeat-Request (CC-HARQ), which is a simple HARQ scheme where each user re-transmits its encoded signal, using its original (first transmission) modulation and coding scheme) upon receiving a decoding error message (NACK) from the receiver of the base station 10. An optimal Chase-combiner utilizes received sufficient statistics from all the received signal transmissions to perform pre-demodulation combining in every time slot. It is not suitable for implementation, particularly, in multi-user systems due to its high memory requirement and complexity.
A conventional receiver that is used for chase combining, implements post-demodulation bit-level combining in which the log-likelihood ratios (LLRs) for each coded bit are added up across all received transmissions. An optimal chase combining receiver is also known in the prior art and this receiver implements pre-equalization symbol-level combining. The optimal receiver can offer significant gains over the conventional one since the latter does not fully exploit the available received observations. However, in practice the conventional one is preferred because the optimal receiver requires prohibitive complexity and memory consumption.
Accordingly, there is a need for a Chase-combining hybrid automatic-repeat-request (CC-HARQ) receiver technique that achieves the performance of the optimal receiver technique, but with the memory requirement and complexity of the conventional receiver.
SUMMARY OF THE INVENTION
In accordance with the invention, a method for decoding of multiple wireless signals by a chase combining hybrid-automatic-repeat-request CC-HARQ receiver includes demodulating wireless signals received from respective mobile sources using an effective channel matrix and decision statistics; updating log-likelihood-ratios LLRs and decoding the received codewords using the corresponding updated LLRs; determining set of correctly decoded codewords using a cyclic redundancy check; updating the effective channel matrix and decision statistics responsive to the step of determining; and resetting the effective channel matrix and decision statistics in the event that the number of decoding errors for a codeword exceeds its maximum limit after storing the updated LLRs of all remaining erroneously decoded codewords for which the number of decoding errors is below the respective maximum limit.



BRIEF DESCRIPTION OF DRAWINGS
These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings.
FIG. 1 is a diagram of an exemplary wireless network, with multiple mobile signal sources 11-13 transmitting to a destination base-station 10, in which the inventive receiver technique can be employed.
FIG. 2 is a block diagram of chase combining hybrid automatic-repeat-request CC-HARQ receiver signal processing in accordance with the invention.
FIG. 3 is a block diagram of the receiver signal processing of FIG. 2 with added SINR feedback, in accordance with the invention.



DETAILED DESCRIPTION
The invention is directed to a hybrid automatic-repeat-request (HARQ) receiver technique that uses a key transformation of the received sufficient statistics in the absence of packet errors, to obtain an equivalent sufficient statistic which is simple to store and update and which allows pre-equalization symbol level combining. In the presence of packet errors, the inventive technique leverages post-demodulation bit-level combining.
We consider a multi-codeword (MCW) chase combining hybrid automatic-repeat-request (CC-HARQ ) system in which K codewords in a signal are first simultaneously transmitted using K physical (or virtual) antennas. These antennas could be co-located at the same transmitter or they could belong to different users. For the sake of exposition, let us assume that each antenna belongs to one user. The transmissions are received by a receiver and the K codewords in signals are then decoded by the receiver. The receiver sends a separate acknowledge/non-acknowledge ACK/NACK signal for every codeword it decodes. Upon receiving an ACK, the user transmits a new codeword whereas upon receiving a NACK signal it re-transmits the same codeword. A packet error is declared for user k, if its codeword cannot be successfully decoded after a maximum number of repetitions. Thus, K codewords of a signal are transmitted in every round. The objective is to design a receiver that can efficiently decode the codewords in signals by utilizing all the received observations and without incurring significant memory or complexity overhead.
The chase-combining CC-HARQ receiver is described by the block diagram in FIG. 2. Detailed derivations and analysis are provided after the discussions below respecting FIG. 2. and FIG. 3. The key feature of the inventive receiver technique is that correctly decoded codewords are subtracted from the received observations between two consecutive rounds. The buffers are reset whenever one or more codewords cannot be correctly decoded even after their maximum number of repetitions, after storing the log-likelihood-ratios (LLRs) computed for the remaining erroneously decoded codewords (which have not reached their maximum number of repetitions) as base LLRs. The LLRs for subsequent decoding of such codewords are then obtained as the sum of these base LLRs and the LLRs obtained via pre-equalization symbol level combining which is done using only the subsequent received observations.
Referring again to FIG. 2, a diagram of the inventive CC-HARQ receiver signal processing, initially in step 200 the receiver resets the effective channel matrix S=[ ] and resets the effective decision statistics z=[ ]. For each user k, the receiver sets the counter qk=0 and resets the base LLR vector Lk=0 and it sets t=0. At the next step, 201, the receiver increments t=t+1, receives observations yt and determines the channel matrix Ht for the current round t, and then increments the counter qk=qk+1 for all k users. In the following step, 202, the receiver updates the effective channel matrix S=S+(Ht)*Ht and updates the effective decision statistics z=z+(Ht)*yt, where ( )* denotes a conjugate transpose operation. In the subsequent step 203, the receiver demodulates the K received codewords using the effective channel matrix S and effective decision statistics z, assuming the model z=Sx+v, where x is the K length vector of the transmitted symbols corresponding to the K codewords and v is a Gaussian noise vector with covariance αS, where α is a positive scalar.
Then, in the next step 204, the receiver uses updated log-likelihood ratios LLRs lk+Lk to decode the codeword k, where 1≦k≦K. The receiver then, 205, runs a cyclic redundancy check (CRC) for each decoded codeword. The users whose codewords fail the CRC form the set U and the users whose codewords pass the CRC form the set C. The receiver then 206 sends an acknowledgement to each user k in C and a non-acknowledgement to each user k in U. The receiver then 207 resets the counter and base LLR vector for each user in C.
The receiver in step 208 then checks if there is a user in set U, of users whose codewords failed the cyclic redundancy check, which has reached its maximum repetition limit. If not the effective channel matrix S and effective decision statistics z are updated 212 by first reconstructing (i.e., re-encoding and re-modulating) the correctly decoded codewords corresponding to users in C. Then for each q in the set U of users, the receiver updates zq=zq−ΣiεcSqi{circumflex over (x)}i. Next, for each k in the set C of users the receiver replaces the row k and column k of S with the K length vector of all zeros. The corresponding decision statistic is set to 0, i.e., zk=0. On the other hand, if there is a user in set U which has reached its maximum repetition limit then the receiver declares a packet error for that user and resets the counter qk and the base LLR vector Lk 209. In the next step 210, the receiver updates the base LLR Lk=Lk+lk for each user k in U which has not reached its maximum repetition limit. Then the effective channel matrix S and effective decision statistics z are reset 211. If the increment timer has not maxed out, then receiver processing returns to step 201 and repeats the subsequent steps 202-212. Otherwise the receiver has finished processing the signals 214.
The diagram of FIG. 3 shows the inventive chase-combining hybrid-automatic-repeat-request CC-HARQ of FIG. 2, with the addition of a signal-to-noise-ratio SINR feedback 213-2 in the repeat path for each incremental processing of steps 201-212. The objective is to compute and feed back an SINR before the start of any round to each user who is supposed to transmit a new codeword in that round. This allows the users to use rates that are well-matched to their received SINRs and hence improve the system throughput. The key advantage in the inventive method is that SINRs for all users whose codewords have been correctly decoded in the current round are computed using the effective channel matrix S, the channel estimates for the next round and by exploiting the fact that the erroneously decoded users that have not reached their maximum respective repetition limits will re-transmit their codewords. Thus, the SINR computation for a user efficiently exploits the information about the interference, i.e., the code words transmitted by other users, that is present in the previous received observations.
A simple complexity reduction feature that can be incorporated in the receiver of FIG. 2 or FIG.3 is the following. The receiver may choose not to demodulate and decode some or all of the codewords and decide that these codewords were decoded erroneously. Clearly by avoiding demodulating and decoding some or all of the codewords the receiver can reduce the complexity in the current round. The drawback is that such an approach if not used judiciously can increase the packet error rate and reduce the throughput. Nevertheless, using an appropriate rule based on the effective channel matrix, the modulation and coding schemes employed by the users and possibly the decision statistics, the receiver can determine the set of users it will demodulate and decode. It then decides that the codewords of the remaining users were decoded erroneously. Thus the set of users in U is formed by these users along with the users whose codewords were indeed decoded but failed the CRC. An advantage of this approach is that the receiver can avoid demodulating and decoding a codeword for which it deems that an error is very likely.
Chase-Combining Hybrid ARQ
System Model
We consider a narrow-baud multiple access channel model with K users and a base-station equipped with Nr receive antennas. The communication takes place over multiple slots (or rounds) and in any slot each user can transmit at-most one codeword. The channel model for a symbol interval in the ith round (slot) is given by1:

yi=Hisi+ni,   (1)

where Hi=[Hi,1, . . . , Hi,K] is the NT×Σk=1Knk channel matrix with Nr≧Σk=1Knk and where nk is the number of transmit antennas of the kth user. The Nr×nk matrix Hi,k corresponds to the channel matrix seen by the base-station from user k. ni is a possibly colored Gaussian noise vector which is independent across different symbol intervals. si=[si,1; . . . ; si,K] is the vector of transmitted symbols and the kth sub-vector si,k of length nk, consists of the symbols transmitted by the kth user and its elements are either all zero (when the kth transmitter is silent) or they are symbols drawn from some regular constellation. The model in (1) also describes the channel output seen on any tone in an OFDMA uplink. We now briefly describe the Chase-combining HARQ. In this scheme each user re-transmits the same codeword upon receiving a NACK from the receiver, whereas upon receiving an ACK it either remains silent or transmits a new codeword corresponding to a new message. User p, 1≦p≦K is allowed upto Mr≧1 transmissions for a codeword, which implies that it can re-transmit the same codeword Mp−1 times. Thus, if user p receives more than Mp−1 consecutive NACKs from the receiver, it will start transmitting a new codeword and the receiver will declare a packet error for user p. Note that without loss of generality, we have assumed that each user can transmit at-most a single codeword during any slot since a user transmitting multiple codewords can be split into multiple virtual users transmitting a single codeword each.

CC-HARQ With Blanking

We first consider an MCW CC-HARQ system with blanking. In such a system. K≧1 codewords are first simultaneously transmitted by the K users, which are then decoded by the receiver. The receiver conducts a cyclic redundancy check (CRC) for every codeword it decodes and sends an ACK to each user whose decoded codeword passed the CRC and a NACK to the remaining ones. Upon receiving a NACK, the user re-transmits its codeword in the next round whereas upon receiving an ACK it remains silent. Consequently, only those, codewords for which a NACK was received are transmitted in the next round. A new set of K codewords can be transmitted either it all codewords have been deemed to be correctly decoded by the receiver or if the maximum codeword transmission limit (which is identical to Q for all codewords) is reached without the successful decoding of at-least one codeword. 2Let us refer to the round when K new codewords are transmitted as a regeneration round (slot) and suppose round 1 is one such round. Then, the discrete-time model of the signal received during a symbol interval in the first round is given by

y1=H1s1+n1,   (2)

where H1=[H1,1, . . . , H1,K] is the matrix denoting the channel response and n1 models the noise plus interference and is assumed to have a covariance matrix Σ1. s1=[s1,1; . . . ; s1,K] denotes the transmitted symbol vector. The receiver proceeds to decode the K codewords and conducts a CRC on each decoded codeword. It accordingly sends an ACK or NACK to each user and only the users who received a NACK transmit in the second round. Continuing this way, the discrete-time model of the signal received during a symbol interval in the ith round (prior to the next regeneration round) can be written as

yi=Hisi+ni, i≧1,   (3)

where Hi=[Hi,1, . . . , Hi,K] is the matrix denoting the channel response and ni models the noise plus interference and is assumed to have a ovarianee matrix Σi. Let Ti⊂ {1, . . . , K} denote the set containing the indices of the undecoded codewords at the start of the ith round so that T1={1, . . . , K}. The symbol vector si=[si,1; . . . ; si,K] contains the re-transmitted symbols from the codewords having indices in Ti, i.e., si,j=s1,j, ∀j ε Ti and si,j=0, ∀j ∉Ti. Thus, without loss of optimality, we can set Hi,j=0, ∀j ∉ Ti. Post whitening, the model in (3) can be written as:

{tilde over (y)}i=Σi−1/2yi={tilde over (H)}isi+ñi,   (4)

where {tilde over (H)}i=Σi−1/2 Hi=[{tilde over (H)}i,1, . . . , {tilde over (H)}i,K].

We now describe memory efficient implementations of the optimal Chase-combining with blanking, which performs pre-equalization symbol-level combining by using the received sufficient statistics. We first consider the case when due to practical constraints the correctly decoded codewords after any round are not canceled from the received observations. Note that to cancel the correctly decoded codewords, we need to re-encode and re-modulate each such codeword prior to subtracting them from the received observations, which may not be feasible due to complexity and/or latency constraints. Then, supposing that round 1 is a regeneration round, the concatenated received observations (for each symbol interval) up to the ith round, which represent the received sufficient statistics, can be modeled as

{tilde over (y)}(i)={tilde over (H)}(i)s1+ñ(i),   (5)

where {tilde over (y)}(i)=[{tilde over (y)}1; . . . ; {tilde over (y)}i], {tilde over (H)}(i)=[{tilde over (H)}1; . . . ; {tilde over (H)}i], {tilde over (H)}q=[{tilde over (H)}q,1, . . . , {tilde over (H)}q,K], ∀ 1≦q≦i and where we have set {tilde over (H)}q,j0, ∀j ∉ Tq & 1≦q≦i. Note that in the ith round only the codewords in Ti should he decoded so that the LLRs must be generated only for these codewords. Further, no side information on the values or the distributions of the symbols of the already decoded codewords is assumed to be available. The received sufficient statistics in (5) can then be used for equalization (or demodulation) but the naive way of doing so would entail significant memory consumption since all the channel matrices and received observations of the previous rounds need to be stored. A smarter memory efficient implementation follows from the simple but key observation that {tilde over (z)}i={tilde over (H)}i†{tilde over (y)}(i) also represents sufficient statistics. {tilde over (z)}i can be modeled as

{tilde over (z)}i=Ãis1+{tilde over (v)}i,   (6)

where Ãi=Σj=1i {tilde over (H)}j†{tilde over (H)}j=Σj=1iHj†Σj−1 Hj and the Gaussian vector {tilde over (v)}i has a covariance matrix which equals Ãi. In particular, the LLRs generated using the ML demodulator on {tilde over (y)}(i) assuming it to be the output of the model in (5), are identical to those generated using the ML demodulator on {tilde over (z)}i assuming it to be the output of the model in (6). The same observation also holds for the LMMSE demodulator. Moreover, {tilde over (z)}i also permits a simple update {tilde over (z)}i{tilde over (z)}i−1+{tilde over (H)}i†{tilde over (y)}i.

Next, consider the case when the correctly decoded codewords can be canceled from the received observations during the time interval between two consecutive rounds. Suppose again that round 1 is a regeneration round so that the signal received during a symbol interval in round 1 is given by (2). After the decoding and CRC steps, let U and C=Uc denote the set of correctly and erroneously decoded codewords, respectively. Thus T2=U is the set of undecoded codewords at the start of round 2. Now, the receiver can cancel the correctly decoded codewords from the observations received during round 1, i.e., it can obtain {tilde over (y)}1−ΣkεT2r {tilde over (H)}1,k,{tilde over (s)}1,k, where {tilde over (s)}1,k, k ε T2c denotes the decision made for s1,k. Then, concatenating with the observations received during round 2, we obtain




  
    
      
        
          
        
        ⁢
        
          
            
              w
              ~
            
            
              (
              2
              )
            
          
          -
          
            
              [
              
                
                  
                    
                      y
                      1
                    
                    ~
                  
                  -
                  
                    
                      ∑
                      
                        k
                        ∈
                        
                          T
                          2
                          c
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        
                          H
                          ~
                        
                        
                          1
                          ,
                          k
                        
                      
                      ⁢
                      
                        
                          s
                          ^
                        
                        
                          1
                          ,
                          k
                        
                      
                    
                  
                
                ;
                
                  
                    y
                    ~
                  
                  2
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        7
        )
      
    
  




In the absence of CRC errors, another simple but key observation is that {tilde over (w)}(2) represents the sufficient statistics to decode the remaining codewords of users in T2, since the codewords are independent across users. 3Continuing in this manner, the concatenated received observations post-cancelation for the ith round can be modeled as

{tilde over (w)}(i)={tilde over (G)}(i)si+ñ(i),   (8)

where {tilde over (w)}(i)=[{tilde over (w)}1; {tilde over (w)}2; . . . ; {tilde over (y)}i] with {tilde over (w)}j={tilde over (y)}j−ΣkεT2c {tilde over (H)}j,k{tilde over (s)}1,k, 1≦j≦i−1 and {tilde over (G)}(i)=[{tilde over (G)}1; . . . ; {tilde over (G)}i] with {tilde over (G)}j=[{tilde over (G)}j,1, . . . , {tilde over (G)}j,K] where {tilde over (G)}j,k={tilde over (H)}j,k, ∀k εTi and {tilde over (H)}j,k0, ∀k ∉ Ti for 1≦j≦i. A memory efficient implementation now follows from the fact that {tilde over (x)}i={tilde over (G)}(i)†{tilde over (w)}(i) are also sufficient statistics and can be modeled as

{tilde over (x)}i={tilde over (B)}is1+ũi,   (9)

where {tilde over (B)}i=Σj=1i {tilde over (G)}j†{tilde over (G)}j and the Gaussian vector ũi has a covariance matrix which equals {tilde over (B)}i. As before, the ML demodulator generates identical LLRs when used on {tilde over (w)}(i) or {tilde over (x)}i, after assuming them to be the outputs of the appropriate models. The same observation holds for the LMMSE demodulator as well. Note that {tilde over (x)}i=[{tilde over (x)}i,k; . . . ; {tilde over (x)}i,K] also permits a simple update: {tilde over (x)}i,k={tilde over (x)}i−1,k+{tilde over (H)}i,k†{tilde over (y)}i−ΣqεTic\Ti−1c {tilde over (B)}k,q{tilde over (s)}i−1,q, k ε Ti, where {tilde over (B)}k,q =Σj=1i {tilde over (G)}j,k†{tilde over (G)}j,q and {tilde over (x)}i,k =0, k ∉ Ti.

In Algorithm 2, we leverage our key observations and provide a memory efficient implementation of the optimal Chase-combining with blanking, with and without codeword cancelation.
Process: Efficient Chase Combining With Blanking


    1. Initialize i=1, S=0, {tilde over (z)}=0.
    2. repeat
    3. Obatin {tilde over (y)}i and {tilde over (H)}i, the observations and the channel matrix post-whitening for the ith round.
    4. Update {tilde over (S)}→{tilde over (S)}+{tilde over (H)}i†{tilde over (H)}i and {tilde over (z)}→{tilde over (z)}+{tilde over (H)}i†{tilde over (y)}i 
    5. Use {tilde over (z)} and {tilde over (S)} with the model in (6) (when codeword cancelation is not allowed) or the model in (9) (when it is allowed) to demodulate the symbols of codewords in Ti and let {lk}kεTi denote the obtained LLR vectors.
    6. Use {lk}kεTi to decode the codewords in Ti.
    7. Conduct CRC on each decoded codeword and let U,C denote the sets of users which fail and pass the CRC, respectively.
    8. Send an ACK for each user in C and a NACK for each user in U.
    9. if Codeword cancelation is allowed then
    10 Re-encode and re-modulate all decoded codewords in C.
    11. For each user j εU update {tilde over (z)}j→{tilde over (z)}j−ΣpεC{tilde over (S)}j,p{tilde over (s)}p.
    12. For each j εC and set {tilde over (z)}j=0 and set all elements in the rows and columns of {tilde over (S)} with indices in {1+Σq=1j−1 nq, . . . , Σq=1j nq} to be zero.
    13. end if
    14. if i=Q and U≠φ then
    15. Declare a packet error for each user in U.
    16. end if
    17. Update i→i+1 and Ti=U.
    18. until i>Q or Ti=φ

CC-HARQ Without Blanking



We now consider an MCW CC-HARQ system without blanking. In such a system. K≧1 codewords are simultaneously transmitted by the K users, which are then decoded by the receiver. The receiver conducts a cyclic redundancy check (CRC) for every codeword it decodes and sends an ACK to each user whose decoded codeword passed the CRC and a NACK to the remaining ones. Upon receiving a NACK, the user re-transmits its codeword whereas upon receiving an ACK it transmits a new codeword. A packet error is declared for user p if its codeword cannot be successfully decoded after a maximum number, say Mp, of transmissions. Thus, K codewords are transmitted in every round. The discrete-time model of the signal received during a symbol interval in the ith round after whitening, can
be written as

{tilde over (y)}i={tilde over (H)}isi+ñi,   (16)

where si is now a vector containing all non-zero modulated symbols and hence {tilde over (H)}i is a matrix with all non-zero columns.

We now consider the optimal Chase-combining without blanking. Recall that we refer to a round as a regeneration round if K new codewords are transmitted during that round. Then consider the ith round and let t≦i be the index of the most recent regeneration round. First supposing that cancelation of codewords from the received observations is not possible, we cam write the concatenated received sufficient statistics as,




  
    
      
        
          
            
              y
              ~
            
            
              (
              i
              )
            
          
          =
          
            
              [
              
                
                  
                    y
                    ~
                  
                  t
                
                ;
                ...
                ⁢
                
                  
                
                ;
                
                  
                    y
                    ~
                  
                  i
                
              
              ]
            
            =
            
              
                
                  
                    
                      [
                      
                        
                          
                            H
                            ~
                          
                          
                            (
                            i
                            )
                          
                          eff
                        
                        ,
                        
                          
                            H
                            ~
                          
                          
                            (
                            i
                            )
                          
                          int
                        
                      
                      ]
                    
                    }
                  
                  
                    
                      F
                      ~
                    
                    
                      (
                      i
                      )
                    
                  
                
                ⁡
                
                  [
                  
                    
                      s
                      i
                    
                    ;
                    
                      s
                      i
                      int
                    
                  
                  ]
                
              
              +
              
                
                  n
                  ~
                
                
                  (
                  i
                  )
                
              
            
          
        
        ,
      
    
    
      
        (
        18
        )
      
    
  




where si=[si,1; . . . ; si,K] is the symbol vector transmitted during a symbol interval in the ith round. The symbols not corresponding to the K codewords of the ith round are collected in the vector siint. On the other hand, consider the case when the correctly decoded codewords can be canceled from the received observations during the time interval between two consecutive rounds. Let Cj,i, t≦j≦i−1 denote the set of indices of codewords that are transmitted in round j and are correctly decoded prior to the ith round. Then, we can obtain the concatenated received statistics post-cancelation, [{tilde over (y)}t−ΣkεCt,i {tilde over (H)}t,kŝt,k; . . . ; {tilde over (y)}i−1−ΣkεCi−1,i {tilde over (H)}i−1,kŝi−1,k; {tilde over (y)}i] and expand it as in the RHS of (18), but where siint now contains the symbols corresponding to codewords that could not be correctly decoded even after the maximum number of transmissions. The concatenated received sufficient statistics with or without codeword cancelation can be used tor the symbol-level pre-equalization combining. In each case, the SINR at the LMMSE equalizer output is given by





  
    
  
  ⁢
  
    
      
        SINR
        
          i
          ,
          k
          ,
          m
        
        eff
      
      =
      
        
          1
          
            
              [
              
                
                  (
                  
                    I
                    +
                    
                      
                        
                          [
                          
                            
                              
                                H
                                ~
                              
                              
                                (
                                i
                                )
                              
                              eff
                            
                            ,
                            
                              
                                H
                                ~
                              
                              
                                (
                                i
                                )
                              
                              int
                            
                          
                          ]
                        
                        †
                      
                      ⁡
                      
                        [
                        
                          
                            
                              H
                              ~
                            
                            
                              (
                              i
                              )
                            
                            eff
                          
                          ,
                          
                            
                              H
                              ~
                            
                            
                              (
                              i
                              )
                            
                            int
                          
                        
                        ]
                      
                    
                  
                  )
                
                
                  -
                  1
                
              
              ]
            
            
              e
              
                
                  k
                  +
                  m
                
                ,
                
                  
                    e
                    k
                  
                  +
                  m
                
              
            
          
        
        -
        1
      
    
    ,
    
      
        
          
            ∀
            
              1
              ≤
              m
              ≤
              
                n
                k
              
            
          
          &
        
        ⁢
        
          
        
        ⁢
        k
      
      ∈
      
        {
        
          1
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              K
              (
              }
            
            ⁢
            1
          
        
      
    
  




after using the appropriate





  
    
      
        H
        ~
      
      
        (
        i
        )
      
      eff
    
    ,
    
      
        
          
            H
            ~
          
          
            (
            i
            )
          
          int
        
        ⁢
        
          e
          k
        
      
      =
      
        
          ∑
          
            j
            =
            1
          
          
            k
            -
            1
          
        
        ⁢
        
          n
          j
        
      
    
    ,
    
      
        ∀
        
          k
          ≥
          
            1
            ⁢
            
              
            
            ⁢
            with
            ⁢
            
              
            
            ⁢
            
              e
              1
            
          
        
      
      =
      0.
    
  
  ⁢
  
    
  




The major drawback in using concatenated received statistics (with or without codeword cancelation) for symbol-level combining is that in order to perform this type of combining, the receiver must store all the received observations and channel matrices starting from the most recent regeneration round. This is because the received observations starting from the most recent regeneration round to the current round are not mutually independent and hence must be jointly processed. Moreover, for any positive maximum codeword re-transmission limit, the memory required may grow unbounded since the number of rounds between two consecutive regeneration rounds is not bounded, making such a combining scheme impractical. Unfortunately, in this case no memory efficient implementations for the optimal combining seem possible. Nevertheless, we consider the case when codeword cancelation is possible and suggest an efficient receiver that leverages both bit-level combining and pre-equalization symbol-level combining and limits memory consumption and complexity to that of the conventional combiner.
An Efficient Technique For Chase Combining Without Blanking
In order to describe our efficient technique, we suppose round 1 to be a regeneration round and assume that there have been no packet errors upto round i. Then, recalling our observation that without loss of optimality, we can re-encode and subtract the correctly decoded codewords from the received vectors, the received sufficient statistics at round i, post-subtraction, can be written as




  
    
      
        
          
            q
            ~
          
          
            (
            i
            )
          
        
        =
        
          
            [
            
              
                
                  
                    
                      
                        
                          y
                          ~
                        
                        1
                      
                      -
                      
                        
                          ∑
                          
                            k
                            ∈
                            
                              c
                              
                                1
                                ,
                                i
                              
                            
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            
                              H
                              ~
                            
                            
                              1
                              ,
                              k
                            
                          
                          ⁢
                          
                            
                              s
                              ^
                            
                            
                              1
                              ,
                              k
                            
                          
                        
                      
                    
                    ;
                    ...
                    ⁢
                    
                      
                    
                    ;
                  
                
              
              
                
                  
                    
                      
                        
                          y
                          ~
                        
                        
                          i
                          -
                          1
                        
                      
                      -
                      
                        
                          ∑
                          
                            k
                            ∈
                            
                              c
                              
                                
                                  i
                                  -
                                  1
                                
                                ,
                                i
                              
                            
                          
                        
                        ⁢
                        
                          
                            
                              H
                              ~
                            
                            
                              
                                i
                                -
                                1
                              
                              ,
                              k
                            
                          
                          ⁢
                          
                            
                              s
                              ^
                            
                            
                              
                                i
                                -
                                1
                              
                              ,
                              k
                            
                          
                        
                      
                    
                    ;
                    
                      
                        y
                        ~
                      
                      i
                    
                  
                
              
            
            ]
          
          =
          
            
              
                
                  H
                  ~
                
                
                  (
                  i
                  )
                
                eff
              
              ⁢
              
                s
                i
              
            
            +
            
              
                
                  n
                  ~
                
                
                  (
                  i
                  )
                
              
              .
            
          
        
      
    
    
      
        (
        20
        )
      
    
  




Then, note that in the absence of packet errors and with codeword cancelation, ({tilde over (H)}(i)eff)†{tilde over (q)}(i) represents sufficient statistics to decode tlie codewords of the K users in round i. Consequently, the pre-equalization symbol-level combining can be done in a memory efficient way, in a manner similar to that used in the efficient technique described for blanking with codeword cancelation. Next, on decoding the K codewords and conducting CRC on each decoded codeword, we obtain the sets Ui & Ci, which denote the sets of codeword indices which fail and pass the CRC step in round i, respectively. Let there be a user k εUi such that qk=Mk, i.e., there is a user k which has been decoded in error and for whom the maximum transmission limit has been reached. Consequently, we declare a packet error for user k. Suppose also that there is at least one user in Ui which has not reached its maximum transmission limit. However, since the codeword corresponding to user k cannot be perfectly canceled, the sufficient statistics for the next (i+1) round will involve more than Σj=1 K nj input symbols. In particular, we will have





  
    
      
        
          
        
        ⁢
        
          
            
              q
              ~
            
            
              (
              
                i
                +
                1
              
              )
            
          
          =
          
            
              [
              
                
                  
                    
                      
                        
                          
                            y
                            ~
                          
                          1
                        
                        -
                        
                          
                            ∑
                            
                              k
                              ∈
                              
                                c
                                
                                  1
                                  ,
                                  
                                    i
                                    +
                                    1
                                  
                                
                              
                            
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              
                                H
                                ~
                              
                              
                                1
                                ,
                                k
                              
                            
                            ⁢
                            
                              
                                s
                                ^
                              
                              
                                1
                                ,
                                k
                              
                            
                          
                        
                      
                      ;
                      ...
                      ⁢
                      
                        
                      
                      ;
                    
                  
                
                
                  
                    
                      
                        
                          
                            y
                            ~
                          
                          i
                        
                        -
                        
                          
                            ∑
                            
                              k
                              ∈
                              
                                c
                                
                                  i
                                  ,
                                  
                                    i
                                    +
                                    1
                                  
                                
                              
                            
                          
                          ⁢
                          
                            
                              
                                H
                                ~
                              
                              
                                i
                                ,
                                k
                              
                            
                            ⁢
                            
                              
                                s
                                ^
                              
                              
                                i
                                ,
                                k
                              
                            
                          
                        
                      
                      ;
                      
                        
                          y
                          ~
                        
                        
                          i
                          +
                          1
                        
                      
                    
                  
                
              
              ]
            
            ⁢
            
              

            
            ⁢
            
              
            
            =
            
              
                
                  [
                  
                    
                      
                        H
                        ~
                      
                      
                        (
                        
                          i
                          +
                          1
                        
                        )
                      
                      eff
                    
                    ,
                    
                      
                        H
                        ~
                      
                      
                        (
                        
                          i
                          +
                          1
                        
                        )
                      
                      int
                    
                  
                  ]
                
                ⁡
                
                  [
                  
                    
                      s
                      
                        i
                        +
                        1
                      
                    
                    ;
                    
                      s
                      
                        i
                        +
                        1
                      
                      int
                    
                  
                  ]
                
              
              +
              
                
                  n
                  ~
                
                
                  (
                  
                    i
                    +
                    1
                  
                
              
            
          
        
      
    
    
      
        (
        21
        )
      
    
  




where si+1int consists of all symbols belonging to the codewords in Ui for whom a packet error was declared. Then, to limit demodulation complexity as well as memory requirement to that of the conventional combiner, we make the following approximation in our receiver. We exploit bit-level combining for all codewords in Ui which have not, reached their maximum transmission limits. In particular, we first store the LLRs computed for these codewords thus far and we assume the next round i+1 to be a regeneration round. Under this assumption pre-equalization symbol-level combining is done in all subsequent rounds. Specifically, for round i+1 we use only the observations {tilde over (y)}i+1, whereas for any non-regeneration round t>i+1 such that no packet errors have occurred in rounds i+1 to t−1, we use the following received observations





  
    
      
        
          
            q
            ~
          
          
            (
            t
            )
          
        
        =
        
          
            [
            
              
                
                  
                    
                      
                        
                          y
                          ~
                        
                        
                          i
                          +
                          1
                        
                      
                      -
                      
                        
                          ∑
                          
                            k
                            ∈
                            
                              c
                              
                                i
                                +
                                
                                  1
                                  ·
                                  t
                                
                              
                            
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            
                              H
                              ~
                            
                            
                              
                                i
                                +
                                1
                              
                              ,
                              k
                            
                          
                          ⁢
                          
                            
                              s
                              ^
                            
                            
                              
                                i
                                +
                                1
                              
                              ,
                              k
                            
                          
                        
                      
                    
                    ;
                    ...
                    ⁢
                    
                      
                    
                    ;
                  
                
              
              
                
                  
                    
                      
                        
                          y
                          ~
                        
                        
                          t
                          -
                          1
                        
                      
                      -
                      
                        
                          ∑
                          
                            k
                            ∈
                            
                              c
                              
                                t
                                -
                                
                                  1
                                  ·
                                  t
                                
                              
                            
                          
                        
                        ⁢
                        
                          
                            
                              H
                              ~
                            
                            
                              
                                t
                                -
                                1
                              
                              ,
                              k
                            
                          
                          ⁢
                          
                            
                              s
                              ^
                            
                            
                              
                                t
                                -
                                1
                              
                              ,
                              k
                            
                          
                        
                      
                    
                    ;
                    
                      
                        y
                        ~
                      
                      t
                    
                  
                
              
            
            ]
          
          =
          
            
              
                
                  H
                  ~
                
                
                  (
                  t
                  )
                
                eff
              
              ⁢
              
                s
                t
              
            
            +
            
              
                
                  n
                  ~
                
                
                  (
                  t
                  )
                
              
              .
            
          
        
      
    
    
      
        (
        22
        )
      
    
  




A set of LLRs are computed in a memory efficient way using ({tilde over (H)}(t)eff)†{tilde over (q)}(t). The LLRs so obtained are used to decode all codewords in round t except those that were also transmitted during round i. For the latter set of codewords, the LLRs fed to their decoders are the sums of the obtained LLRs and the corresponding LLRs stored at the end of round i. Note that subsequent equalization (demodulation) does not use the received observations and channel matrices corresponding to rounds prior to i+1 and hence these can be discarded. Finally for any regeneration round t, without loss of optimality, we use only the received observations {tilde over (y)}t. Note that in contrast to the aforementioned approach, in conventional Chase combining we do bit-level combining for all codewords irrespective of how many times they have been transmitted. Our efficient technique is described in detail in the algorithm given below.

Process Efficient Chase Combining Without Blanking

    1. Initialize {Lk=0, qk=0}k=1K, t=0, {tilde over (z)}=0.
    2. while t≦Tfinish do
    3. Update t→t+1 and obtain {tilde over (y)}t and {tilde over (H)}t, the observations and the channel matrix post-whitening for the tth round.
    4. Update {tilde over (S)}→{tilde over (S)}+{tilde over (H)}t†{tilde over (H)}t and {qk→qk+1}k=1K; {tilde over (z)}→{tilde over (z)}+Ht†{tilde over (y)}t.
    5. Use {tilde over (z)} and {tilde over (S)} to demodulate the symbols of the K codewords and let {lk}k=1K denote the obtained LLR vectors.
    6. Update {lk→Lk+lk}k=1K and use the updated LLRs to decode the K codewords.
    7. Conduct CRC on each decoded codeword and let U,C denote the sets of users which fail and pass the CRC, respectively.
    8. Send an ACK for each user in C and a NACK for each user in U.
    9. For each i ε C and set {tilde over (z)}i=0, qi=0 & Li=0.
    10. if there is a user p ε U such that qp=Mp then
    11. For each user p ε U such that qp=Mp, declare a packet error and set {tilde over (z)}p=0, qp=0 & Lp=0.
    12. For each user p ε U such that qp<Mp, set Lp=lp.
    13. Set {tilde over (S)}=0, {tilde over (z)}=0.
    14. else
    15. For each user i ε U update {tilde over (z)}i→{tilde over (z)}i−ΣpεC{tilde over (S)}i,p{tilde over (s)}p,
    16. For each user i ε C and set all elements in the rows and columns of {tilde over (S)} with indices in {1+Σq=1i−1 nq, . . . , Σq=1i nq} to be zero.
    17. end if
    18. end while

SINR Feedback For Chase Combining



In this section, we consider systems employing chase combining and with a limited feedback link between the receiver and each user. Our objective is to compute and feed back an SINR at the start of any round to each user who is supposed to transmit a new codeword in that round. This allows the users to use rates that are well-matched to their received SINRs and hence improve the system throughput. The underlying assumption is that, channel estimate for all users are available at the start of a round and hence the scheme is more practical in a low-mobility scenario where each user's channel stays approximately constant for the duration of a round and the feedback delay is well within the coherence time.
First, let us consider chase combining with blanking. In such a system. SINRs can be fed back only at the start of a re-generation round in which all the K users transmit new codewords. This is because in other rounds users either remain silent or re-transmit their codewords and hence cannot alter their rates. Then, as a result of the fact that all the information obtained prior to the regeneration round has no further utility, the SINR computation is identical for the conventional as well as the optimal chase-combiners (with or without codeword cancelation). For instance, assuming an LMMSE equalizer and round i to be a regeneration round the SINRs for both pre and post-equalization symbol-level combining are given by,




  
    
      SINR
      
        i
        ,
        k
        ,
        m
      
      feedback
    
    =
    
      
        1
        
          
            [
            
              
                (
                
                  I
                  +
                  
                    
                      
                        H
                        ~
                      
                      i
                      †
                    
                    ⁢
                    
                      
                        H
                        ~
                      
                      i
                    
                  
                
                )
              
              
                -
                1
              
            
            ]
          
          
            e
            
              
                k
                +
                m
              
              ,
              
                
                  e
                  k
                
                +
                m
              
            
          
        
      
      -
      1
    
  
  ,
  
    
      
        
          ∀
          
            1
            ≤
            m
            ≤
            
              n
              k
            
          
        
        &
      
      ⁢
      
        
      
      ⁢
      k
    
    ∈
    
      
        {
        
          1
          ,
          ...
          ⁢
          
            
          
          ,
          K
        
        }
      
      .
    
  




Note that the nk SINRs of the kth user can also be combined into one effective SINR using standard methods such as EESM or MIESM [14].

Next, let us consider systems employing chase combining without blanking. Now at the start of any round we can feedback an SINR to each user who is supposed to transmit a new codeword in that round. Suppose an LMMSE equalizer is used and that user k is eligible for SINR feedback at the stunt of round i, i.e., at the end of round i−1 either user k received an ACK or reached its maximum codeword transmission limit. Then the SINR for post-equalization symbol-level combining can be computed using (17) after setting q=1. On the other hand, with pre-equalization symbol-level combining the SINR can be computed using (19). The key difference between the two SINR computations is that in the pre-equalization symbol-level combining case we exploit the information about the interference, i.e., the codewords transmitted by other users, that is present in the previous received observations. As before, it can be shown that the SINR obtained for pre-equalization symbol-level combining with codeword cancelation is larger than the SINR obtained for pre-equalization symbol-level combining without codeword cancelation, which in turn is larger than the SINR obtained for post-equalization symbol-level combining.
As mentioned before, the optimal pre-equalization symbol-level combining for CC-HARQ without blanking entails a large memory overhead. Consequently, we next incorporate SINR computation and feedback in our efficient technique given in the above process, after assuming that an LMMSE equalizer is used. Moreover, we also generalize it in the following manner, Recall that in the method used in the above process, upon occurrence of a packet error even, we reset the buffers after storing the appropriate LLRs and assume the next round to be a regeneration round. We can indeed extend this method at the expense of additional memory and complexity. In particular, we define a parameter P≧0 that is used to control the memory and complexity overheads. Then at the start of any round i, if the number of packet errors (starting from the recent-most regeneration round) does not exceed P, we can write the concatenated received observations as in (18), where siint is empty and reset the buffers after storing the appropriate LLRs, i.e., the LLRs of the codewords that will be re-transmitted in the current round. We present the generalized process, where for convenience we assume that all users have an identical number of transmit antennas nk=n, ∀ k
Process: Efficient Chase Combining Without Blanking: SINR Feedback













 1:
Initialize {Lk = 0, qk = 0}k=1,K, t = 0, c = 0, {tilde over (F)} = 0, {tilde over (z)} = 0.


 2:
while t ≦ Tfinish do


 3:
Update t → t + 1 and obtain the channel matrix post-whitening for the tth round, {tilde over (H)}t.


 4:
Update {tilde over (F)} → {tilde over (F)} + [{tilde over (H)}t, 0]†[{tilde over (H)}t, 0] and {qk → qk + 1}k=1K.


 5:
For each k: qk = 1, compute and feedback SINRt,k,m = 



  
    1
    
      
        [
        
          
            (
            
              I
              +
              F
            
            )
          
          
            -
            1
          
        
        ]
      
      
        
          
            e
            
              k
              ⁢
              
                
              
            
          
          +
          m
        
        ,
        
          
            e
            k
          
          +
          m
        
      
    
  
  -
  1






 6:
Obtain the received observations post-whitening, {tilde over (y)}t and update {tilde over (z)} → {tilde over (z)} +



[{tilde over (H)}t, 0]†{tilde over (y)}t.


 7:
Use {tilde over (z)} and {tilde over (F)} to demodulate the symbols of the K codewords and let {lk}k=1K denote the obtained LLR vectors.


 8:
Update {lk → Lk + lk}k=1K and use the updated LLRs to decode the K codewords.


 9:
Conduct CRC on each decoded codeword and let U, C denote the sets of users which fail and pass the CRC, respectively.


10:
Send an ACK for each user in C and a NACK for each user in U.


11:
For each i ∈ C and set {tilde over (z)}i = 0, qi = 0 & Li = 0.


12:
Compute G, the number of users p ∈ U such that qp = Mp


13:
if c + G > P then


14:
For each user p ∈ U such that qp = Mp, declare a packet error and set



{tilde over (z)}p = 0, qp = 0 & Lp = 0.


15:
For each user p ∈ U such that qp < Mp; set Lp = lp.


16:
Set {tilde over (F)} = 0, {tilde over (z)} = 0, c = 0.


17:
else


18:
For each user i ∈ U update {tilde over (z)}i → {tilde over (z)}i − Σp∈C {tilde over (F)}i,pŝp.


19:
For each user i ∈ U: qi = Mi, declare a packet error for user i, increment



c → c + 1, swap {tilde over (z)}i with the subvector of {tilde over (z)} formed by its elements



with indices in {n(i − 1) + 1, . . . , ni},



swap each row k and column k of {tilde over (F)}, where k ∈ {n(i − 1) + , . . ., ni}



with row nK + n(c − 1) + k − n(i − 1) and column nK +



n(c − 1) + k − n(i − 1) of {tilde over (F)}, respectively.


20:
For each user i ∈ C set all elements in the rows and columns of {tilde over (F)} with



indices in {n(i − 1) + 1, . . . , ni} to be zero.


21:
end if


22:
end while









The key feature of the inventive receiver techniques is that both post-demodulation bit-level combining as well as pre-equalization symbol level combining are exploited to achieve a superior performance compared to the conventional chase combining receiver, with a comparable memory and complexity requirement. In particular, in each round an effective channel matrix and decision statistics are recursively updated and are subsequently used for demodulation. The resulting LLRs are combined with corresponding previously stored estimates and used for decoding. Based on the results of the CRC and the number of decoding errors that have previously been made for each codeword, the effective channel matrix and decision statistics are again updated and stored along with a set of LLRs.
The present invention has been shown and described in what are considered to be the most practical and preferred embodiments. It is anticipated, however, that departures may be made therefrom and that obvious modifications will be implemented by those skilled in the art. It will be appreciated that those skilled in the art will be able to devise numerous arrangements and variations, which although not explicitly shown or described herein, embody the principles of the invention and are within their spirit and scope.

## Claims

1. A method for decoding of multiple wireless signals by a chase combining hybrid-automatic-repeat-request CC-HARQ receiver, comprising the steps of:
demodulating wireless signals received from respective mobile sources using an effective channel matrix and decision statistics;
updating log-likelihood-ratios LLRs and decoding the received codewords using the corresponding updated LLRs;
determining set of correctly decoded codewords using a cyclic redundancy check;
updating the effective channel matrix and decision statistics responsive to the step of determining; and
resetting the effective channel matrix and decision statistics, in the event that the number of decoding errors for a codeword exceeds its maximum limit, after storing the updated LLRs of all remaining erroneously decoded codewords for which the number of decoding errors is below the respective maximum limit.

2. The method of claim 1, wherein the effective channel matrix and decision statistics are recursively updated pre-demodulation using their previously stored values and the current channel matrix and received observations.

3. The method of claim 1, wherein the effective channel matrix and decision statistics are recursively updated post decoding after reconstructing the correctly decoded codewords.

4. The method of claim 1, wherein the LLRs are updated by combining the current LLR estimates with the corresponding estimates stored when the number of decoding errors for a codeword exceeds its maximum limit.

5. The method of claim 1, wherein the receiver may choose not to demodulate and decode some or all of the codewords and decide that these codewords were decoded erroneously.

6. The method of claim 1, further comprising the step of transmitting back to a respective mobile user a signal-to-noise-ratio responsive to a correct decoding of a signal from the respective mobile source.

7. The method of claim 6 wherein the signal-to-noise-ratio is computed using the updated effective channel matrix, the channel estimates for the next round and the fact that the erroneously decoded codewords that have not reached their maximum respective repetition limits will be re-transmitted.

8. The method of claim 1, further comprising the step of transmitting back to a respective mobile user a signal-to-noise-ratio responsive to a packet error being declared for the signal from the respective mobile source.