Hybrid ARQ method for packet data transmission

ES 2 359 166 T3

DESCRIPTION

Hybrid ARQ method for packet data transmission

Description

The present invention relates to a method for modifying a sequence of bits in an ARQ retransmission in a communication system. Furthermore, the invention relates to a corresponding receiver and transmitter.

A common technique in communication systems with unreliable and time-varying channel conditions is to correct errors based on automatic repeat request (ARQ) schemes together with a prospective error correction (FEC) technique called hybrid aRq (HARQ ). If an error is detected by a commonly used cyclic redundancy check (CRC), the receiver of the communication system requests the transmitter to resend the data packets received in error.

S. Kallel, Analysis of a type II hybrid ARQ scheme with code combining, IEEE Transactions on Communications. Vol. 38, No. 8, August 1990 and S. Kallel, R. Link, S. Bakhtiyari, Throughput performance of Memory ARQ schemes, IEEE Transactions on Vehicular Technology, Vol. 48, No. 3, May 1999, define three types different from ARQ schemes:

* Type I: The received erroneous packets are discarded and a new copy of the same packet is retransmitted and decoded separately. There is no combination of versions received before and after said package.

* Type II: received erroneous packets are not discarded, but are combined with additional retransmissions for subsequent decoding. Retransmitted packets sometimes have higher coding rates (coding gain) and are combined at the receiver with stored software information from previous transmissions.

* Type III: It is the same as Type II with the condition that each retransmitted packet is now self-encoding. This implies that the transmitted packet is decodable without combining with previous packets. This is useful if some packages are corrupted in such a way that the information can hardly be reused. If all the transmissions carry identified data, this can be considered as a special case called HARQ Type III with only one version of redundancy.

Obviously, Type II and III schemes are more intelligent and show a performance gain over Type I, because they provide the ability to reuse information from previously received erroneous packets. There are basically three schemes to reuse the redundancy of previously transmitted packets:

* Software combination * Code combination * Software combination and Code combination

Software combination

Using a combination of software, the relay packets carry identical information compared to previously received information. In this case, the multiple received packets are combined on a symbol-by-symbol or bit-by-bit basis as described, for example, in D. Chase, Code combining: A maximum-likelihood decoding approach for combining an arbitrary number of noisy packets , IEEE Trans. Commun., Vol. COM-33, p. 385-393, May 1985 or BA Harvey and S. Wicker, Packet Combining Systems based on the Viterbi Decoder, IEEE Transactions on Communications, Vol. 42, 2/3/4, April 1994. By combining these software decision values ​​of all received packets, the reliabilities of the transmitted bits will increase linearly. with the number and power of the received packets. From the point of view of the decoder, the same FEC scheme (with constant code rate) will be used in all transmissions. Therefore, the decoder does not have to know how many retransmissions have been made, since it only sees the combined soft decision values. In this scheme all transmitted packets will have to carry the same number of symbols.

Code combination

The code combination concatenates the received packets to generate a new codeword (decreasing code rate with increasing transmission number). Therefore, the decoder has to be aware of the FEC scheme to apply at each moment of transmission. Code blending offers greater flexibility with respect to software blending, as the length of retransmitted packets can be altered to suit channel conditions. However, this requires transmitting more meaningful data regarding the software mix.

Software Combination and Code Combination

In case the retransmitted packets carry some symbols identical to previously transmitted symbols

ES 2 359 166 T3 and some different code symbols of these, identical code symbols are combined using software combination as described in the section entitled "Software combination", while the remaining code symbols will be combined using software combination. code. Here, the signaling requirements will be similar to the code combination.

It has been shown in MP Schmitt, Hybrid ARQ Scheme employing TCM and Packet Combining, Electronics Letters Vol. 34, No. 18, September 1998, that the HARQ operation for Trellis Coded Modulation (TCM) can be improved by rearranging the symbol constellation for the retransmissions. The performance gain results from maximizing the Euclidean distances between the symbols applied on the retransmissions, because the rearrangement has been carried out on the basis of symbols.

Considering high-order modulation schemes (with modulation symbols carrying more than two bits), combining methods that employ software combining have a major drawback: bit reliabilities within symbols combined by software will be in a constant relationship across all retransmissions, that is, the least reliable bits from previous transmissions received will remain less reliable after more transmissions have been received and, analogously, the most unreliable bits. Reliability of previous transmissions received will continue to be more reliable after more transmissions have been received.

Variable bit reliabilities evolve from the limitation of the 2-dimensional signal constellation application, where modulation schemes carrying more than 2 bits per symbol cannot have the same mean reliabilities for all bits on the assumption that all symbols are transmitted with equal probability. The term average reliabilities consequently means the reliability of a particular bit over all symbols of a constellation of signals.

Employing a constellation of signals for a 16 QAM modulation scheme according to figure 1 showing a constellation of Gray coded signals with a given order of application of bits Í1q1Í2q2, the bits applied on the symbols differ considerably from each other in average reliability in the first transmission of the packet. In more detail, bits i1 and q1 have high mean reliability, since these bits apply to middle spaces of the signal constellation diagram with the consequences that their reliability is independent of whether the bit transmits a one or a zero.

In contrast, bits i2 and q2 have a low average reliability, since their reliability depends on whether they transmit a one or a zero. For example, for the i2 bit, 1s are applied to the outer columns, while zeros are applied to the inner columns. Similarly, for the q2 bit, ones are applied to the outer rows, while zeros are applied to the inner rows.

For the second and subsequent retransmissions, the reliabilities of the bits will be in a constant relationship to each other, which is defined by the constellation of signals used in the first transmission, that is, the bits ¡1 and q-ι will always have an average reliability higher than bits i2 and q2 after any number of retransmissions.

In WO 02/067491 a method has been proposed which, in order to improve the performance of the decoder, it would be quite beneficial to have equal or almost equal mean bit reliabilities after each received transmission of a packet. Therefore, the bit reliabilities are adapted to retransmissions so that the mean bit reliabilities are averaged. This is accomplished by choosing a predetermined first constellation and at least one second signal constellation for the transmissions, so that the combined average bit reliabilities for the respective bits of all transmissions are nearly equal.

Therefore, the rearrangement of the signal constellation results in a shifted bitmap, where the Euclidean distances between modulation symbols can be altered from one retransmission to another due to the movement of the constellation points. As a result, the average bit reliabilities can be desired manipulated and averaged to increase the performance of the FEC decoder at the receiver.

In the solution proposed above, the benefits of constellation rearrangement are realized through a parameterized bit-to-symbol application entity. For reasons of complexity or efficient implementation, it may be advantageous for a communication system to have a non-parameterized standard application entity.

“Enhanced HARQ Method with Signal Constellation Rearrangement TSG-RAN WORKING GROUP 1 MEETING No. 19, February 27, 2001 describes a hybrid HARQ method with signal constellation rearrangement for 16 QAM and 64 QAM modulation. By averaging the reliabilities of the bits carried by symbols transmitted repeatedly in retransmissions, the system exhibits a performance gain.

Accordingly, the object of the present invention is to provide an ARQ transmission method, a transmitter and a receiver with better error correction performance without a parameterized bit-to-symbol application entity.

This object is achieved by the methods and apparatus set forth in the independent claims.

ES 2 359 166 T3

The idea behind the present invention is to modify the input bit sequence before inputting them into the application entity. This modification of the signal constellation can be achieved by using an interleaver and a logic bit inverter, which invert and / or swap the positions of the signal constellation bits depending on the retransmission number parameter m. Therefore, the beneficial effects of a constellation rearrangement are achieved without the need for a parameterized bit-to-symbol application entity. As a result, the sequence output after processing by the interleaver, the logical bit inverter, and a non-parameterized standard application entity cannot be distinguished from the output of a parameterized bit-to-symbol application entity that employs various redisposition schemes. constellation.

For a better understanding of the invention, preferred embodiments will now be described with reference to the accompanying drawings.

Figure 1 is an exemplary constellation of signals for illustrating a 16 QAM modulation scheme with Gray coded bit symbols.

Figure 2 depicts four examples of signal constellations for a 16 QAM modulation scheme with Gray coded bit symbols.

And Figure 3 is an exemplary embodiment of a communication system employing the method underlying the invention.

Next, the concept of a logarithmic likelihood ratio (LLR) as a metric for bit reliabilities will be described. First, the direct calculation of the bit LLRs within the applied symbols for a single transmission will be shown. The LLR calculation will then be extended to the case of multiple transmissions.

Single transmission

The mean LLR of the i-th bit bnⁱ under the condition that the symbol sn has been transmitted for a transmission on a channel with additive white Gaussian noise (AWGN) and symbols of equal probability gives:

<img file="ES2359166T3_D0001.tif" />

where rn = sn denotes the average received symbol under the condition that the sn symbol has been transmitted (AWGN case), dn, m² denotes the square of the Euclidean distance between the received symbol rn and the symbol sm, and Es / N0 denotes the observed signal-to-noise ratio.

It can be seen from equation (1) that the LLR depends on the signal-to-noise ratio Es / N0 and the Euclidean distances dn, m between the points of the signal constellation.

Multiple streams

Considering multiple transmissions, the mean LLR after the kth transmission of the ith bit bn under the condition that the symbols sn^(I) have been transmitted on independent AWGN channels and symbols of equal probability give:

<img file="ES2359166T3_D0002.tif" />

where j denotes the j-th transmission ((j-1) -th retransmission). Analogously to the case of single transmission, the mean LLRs depend on the signal-to-noise ratios and the Euclidean distances at each transmission time.

If no constellation rearrangement is performed, the Euclidean distances dn, m^(j) = dn, m⁽¹⁾ they are constant for all transmissions and therefore the bit reliabilities (LLRs) after k transmissions will be defined by the observed signal-to-noise ratio at each transmission time and the signal constellation points of the first transmission. For higher level modulation schemes (more than 2 bits per symbol) this results in varying mean LLRs for the bits, which in turn results in different mean bit reliabilities. Differences in average reliabilities remain across all retransmissions and lead to decoder performance degradation.

ES 2 359 166 T3

In the following, the case of a 16 QAM system giving rise to 2 high reliability bits and 2 low reliability bits will be considered exemplary, where, with respect to low reliability bits, the reliability depends on transmitting a one or a zero (see figure 1). Therefore, in general there are 2 levels of reliabilities where the second level can be further subdivided.

Level 1 (High reliability, 2 bits): Applying bits for ones (zeros) separated in the positive (negative) half real space for the i-bits and the imaginary half space for the q-bits. Here, it makes no difference whether the ones are applied to the positive or negative half space.

Level 2 (Low Reliability, 2 bits): Ones (zeros) are applied to inner (outer) columns for i-bits or inner (outer) rows for q-bits. Since there is a difference for the LLR depending on the application to the inner (outer) columns and rows, Level 2 is further classified into:

Level 2a: Application of i_n to interior columns and from q_n to inner rows, respectively.

Level 2b: Inverted application of Level 2a: Application of i_n to exterior columns and from q_n to outer rows, respectively.

To guarantee an optimal averaging process over the transmissions for all bits, the reliability levels must be altered.

Consider that the order of bit application is open before the initial transmission, but has to remain during retransmissions, for example, apply bits for initial transmission: i1g1i2g2 =&gt; apply bits in all retransmissions: i1g1i2g2.

Some examples of possible constellations are shown in figure 2. The resulting bit reliabilities according to Figure 2 are set out in Table 1.

TABLE 1

<td>Constellation</td><td>Bit 1</td><td>Bit q1</td><td>Bit i2</td><td>Bit q2</td>

<td> 1</td><td>High reliability (Level 1)</td><td>High reliability (Level 1)</td><td>Low reliability (Level 2b)</td><td>Low reliability (Level 2b)</td>

<td> 2</td><td>Low reliability (Tier 2a)</td><td>Low reliability (Tier 2a)</td><td>High reliability (Level 1)</td><td>High reliability (Level 1)</td>

<td> 3</td><td>Low reliability (Level 2b)</td><td>Low reliability (Level 2b)</td><td>High reliability (Level 1)</td><td>High reliability (Level 1)</td>

<td> 4</td><td>High reliability (Level 1)</td><td>High reliability (Level 1)</td><td>Low reliability (Tier 2a)</td><td>Low reliability (Tier 2a)</td>

In the following it is assumed that m denotes the transmission number parameter, with m = 0 denoting the first transmission of a packet in the ARQ context. B also denotes the number of bits that make up a symbol in the applying entity. Typically, b can be any integer, where the most frequently used values ​​for communication systems are a power integer of 2.

Without loss of generality it can also be assumed that the number of bits n used as input to the interleaving process is divisible by b, that is, n is an integer multiple of b. Those skilled in the art will realize that if this is not the case, the input bit sequence can easily be completed with dummy bits until the above condition is met.

As described above, for a given modulation, various levels of reliability can be identified. The interleaving process should thus average the reliabilities of the b bits over the retransmissions so that all the b bits are on average equally reliable. This means that the interleaver has to change the positions of the b bits within a symbol (also called a curl in the art) so that each of the original bits applies as frequently to all reliability levels as any other of the b bits. This means that collation is an intra-symbol bit collation process.

Furthermore, there may be several bit positions whose reliabilities depend on the logical bit value (low or high). When a bit is applied during the non-first time at that position, this bit should also be logically inverted.

With these rules, you can build configurations that determine the interleaving and inverting process for a retransmission number m.

In theory, perfect averaging of reliabilities could only be possible after an infinite or very high number of retransmissions. In these cases, there could thus be several alternatives that differ from the sequence of

ES 2 359 166 T3 interleaver or inverter configurations. Which of these alternatives is chosen is left to the choice of the system designer, since it will not make a difference in performance.

If the signal constellation is to be kept as in figure 1, in order to obtain constellation 2 from constellation 1 in figure 2, the following processes must be executed, where the order is irrelevant:

* original bit swap positions i1 and i2 * original bit swap positions q1 and q2 * logical inversion of original bits i1 and q1

Alternatively, the bits ending in positions 1 and 2 can also be inverted.

An example depending on the transmission number is shown in the following table, where the bits always refer to the first transmission, and a long stroke above a character denotes logical inversion of said bit:

TABLE 2

Constellation number Interleaver and inverter functionality

<td> 1</td><td>Í1Q1 / 2Q2</td>

<td> 2</td><td>í&gt; Wi ° ¡zWh</td>

<td> 3</td><td>WiQi⁰ ¡₂what₂i ^</td>

<td> 4</td><td>w₂what₂</td>

The first examples shown in each row of table 2 correspond to the constellations shown in the figure

2. As is readily apparent from Table 2, signal constellation 2 is obtained from constellation 1 by swapping (swapping) bit positions i1 and i2 as well as bits q1 and q2 and inverting the bit pair i1, q1, or all bits. Similarly, the constellation of signals 3 is obtained from the constellation 1 by exchanging the bit positions i1 and i2 as well as those of the bits q1 and q2 with each other respectively and inverting the pair of bits i2, q2 in an alternative. In the other alternative, only the bit positions are swapped and no inversion is required. Finally, the signal constellation 4 is obtained from the constellation 1 by inverting the pair of bits i2, q2 or all the bits of the symbol without exchanging any bit position.

From this you can choose different strategies for transmission numbers (not exhaustive):

TABLE 3

<td>Transmission No.</td><td>Constellation number</td><td>Constellation number</td><td>Constellation number</td><td>Constellation number</td><td>Constellation number</td><td>Constellation number</td>

<td> 1</td><td> 1</td><td> 1</td><td> 1</td><td> 1</td><td> 1</td><td> 1</td>

<td> 2</td><td> 2</td><td> 2</td><td> 3</td><td> 4</td><td> 4</td><td> 3</td>

<td> 3</td><td> 3</td><td> 4</td><td> 2</td><td> 2</td><td> 3</td><td> 4</td>

<td> 4</td><td> 4</td><td> 3</td><td> 4</td><td> 3</td><td> 2</td><td> 2</td>

Figure 3 depicts an exemplary embodiment of a communication system employing the method underlying the invention.

At transmitter 100, a sequence of bits is obtained from a prospective error correction (FEC) encoder (not shown) and subsequently fed into an interleaver 110 and a bit logic inverter 120. The interleaver 110 and the bit logic inverter they are dependent on the retransmission number parameter m and modify the input bit sequence. Subsequently, the bit sequence is input to applicator / modulator 130 which is a non-parameterized standard application entity. The applicator typically uses one of the signal constellations depicted in Figure 2 and applies the b bits onto a symbol that is transmitted on communication channel 200. The communication channel is typically a radio communications channel experiencing channel conditions. unreliable and variable in time.

The interleaving / inversion settings are stored in the transmitter and receiver or stored in the transmitter and sent to the receiver.

At receiver 300, the complex symbols are first input into a decoupler / demodulator 330 which demodulates the received symbols to a corresponding bit domain sequence (eg, the sequence of LLRs). This sequence is subsequently input into a logic inverter 320 and subsequently into a deinterleaver 310 from which the obtained bit domain sequence is output.

The interleaver and de-interleaver operate according to the known interleaving / deinterleaving technique by applying a specific, pseudo-random or random permutation of the input bit or symbol sequences, i.e. swapping (swapping) the positions of the bits or symbols within a sequence . In the realization before

ES 2 359 166 T3 described, the interleaver is an intra-symbol bit interleaver that changes the position of the bits that make up a symbol in the application entity.

The bit logic inverter operates according to a known technique of inverting the logic value of a bit, that is to say it goes from a low logic value to a high logic value and vice versa. In a practical realization for a receiver that works with log probability ratios, this inversion operation is equivalent to a sign inversion of the log probability ratio.

If a retransmission is triggered by an automatic repeat request issued by an error detector (not shown) with the result that an identical data packet is transmitted by the transmitter 100, at the detacher / demodulator 330, the data packets Previously received errors are combined in software with the retransmitted data packets. Due to the modification of the bit sequence by the interleaver and the logical bit inverter, the average bit reliabilities are averaged resulting in higher throughput at the receiver.

Although the above described method has been described using Gray encoded signals and a 15 QAM modulation scheme, it is clear to those of skill that other suitable coding and modulation schemes can equally be used to obtain the benefits of the invention.