Technical Field

[0001] This invention relates generally to error detection and correction apparatus, methods and systems. In particular it relates to detection and correction of data loss during the transmission of a stream of packets, e.g. in a wireless communication system.

Introduction

[0002] A crucial function of wireless broadband systems such as UMTS or LTE is the ability to support transmission of streams of packets containing Internet traffic over the air interface. For example, the Transmission Control Protocol ("TCP") provides end-to-end reliable transmission for Internet packets. TCP is intolerant to significant levels of packet loss because it assumes packet loss is normally due to congestion and responds to packet loss by instantly reducing its throughput data rate to relieve congestion and only slowly building it up again. To send TCP/IP efficiently the wireless link requires error correction functionality to ensure TCP/IP receives a sufficiently error free packet stream to prevent the invocation of its congestion avoidance mechanism.

[0003] In UMTS and LTE, a key element of this error correction functionality resides in the Radio Link Control ("RLC") protocol. RLC has been designed to provide an error rate to client applications sufficiently low that TCP/IP can use it without performance loss. RLC in these systems employs an automatic repeat request ("ARQ") protocol. The packet loss is not required to be strictly zero, since TCP itself contains an ARQ mechanism and its throughput is little impacted at rates below 10 ^"5 .

[0004] ARQ protocols use a straightforward strategy to achieve error correction. The "transmit side" sends a packet, and the "receive side" sends an acknowledgment message containing "ACK", if the receive side receives the packet successfully, or "NACK" if the receive side detects an unsuccessfully received transmission. This acknowledgment message, which contains as little as 1 bit of information (ACK or NACK), is channel coded (for example using a repetition code) and sent to the transmit side as a "feedback signal". The transmit side observes the feedback signal and retransmits RLC packets as needed.

Sophisticated ARQ protocols such as LTE RLC assign a sequence number to each packet, which allows them to use techniques such as cumulative acknowledgement messages (which rather than acknowledging a specific packet, inform the transmit side of the successful reception of all packets up to a given packet sequence number) and negative

acknowledgement messages (indicating specific packets or groups of packets are missing). These ARQ acknowledgement messages contain multiple bits of information, but can be sent far less frequently than once per packet.

[0005] In addition to ARQ protocols, the UMTS and LTE systems also employ a hybrid automatic repeat request ("HARQ") protocol. The use of HARQ is motivated by the observation that even if a packet is received with errors, the physical signal observed at the receive side still contains valuable information about the transmitted data content. To ignore this information is a waste of transmission resources. Instead, the receive side sends a HARQ acknowledgement message for every transmitted HARQ packet. These HARQ

acknowledgement messages are separate from the ARQ acknowledgement messages, and typically one HARQ acknowledgement is sent for each transmitted HARQ packet. When a received packet contains an error, the receive side informs the transmit side by sending a HARQ NACK (HARQ negative acknowledgement) and the transmit side sends the packet again. This may happen several times before the packet is received correctly, with the receiver combining information from successive retransmissions. Once the packet is received correctly, it sends an HARQ ACK to the transmit side and passes the compiled packet up to the RLC layer. The HARQ acknowledgement messages are entirely separate from the acknowledgement messages of the ARQ protocol.

[0006] Hybrid ARQ does not entirely replace ARQ in state of the art wireless systems. The reason is that Hybrid ARQ requires every individual transmission to be acknowledged. The power needed to send such acknowledgement messages sufficiently reliably would introduce excessive interference on the reverse link. In other words, feedback signals are themselves error prone. If a packet is received correctly, but the feedback signal is misinterpreted as NACK, there is no great problem: the transmit side will simply unnecessarily retransmit. A much greater problem arises when a packet is received incorrectly, but although the receive side responded with a NACK, the received feedback signal is misinterpreted as an ACK: in that case the transmit side would continue with the next packet, never retransmitting the lost packet. TCP would experience packet loss, and if the rate of this event occurring is above 10 ^"5 then TCP throughput degrades. The cost of reliably channel encoding HARQ

acknowledgement messages to produce feedback signals to achieve this error rate is excessive since each packet elicits a corresponding feedback signal.

[0007] It is for this reason that UMTS and LTE systems use two error correcting protocols, the HARQ protocol and an ARQ protocol at the RLC layer. The RLC protocol uses strong error protection for feedback signals from its acknowledgement messages but sends these relatively infrequently. These are used to detect when the HARQ protocol missed a packet due e.g. to misinterpreting NACK as ACK. The ARQ receiver has to detect that the packet has not been received. This is done by detecting a missing ARQ sequence number in the outer ARQ protocol (sometimes called "gap detection"), which can only occur after the maximum HARQ delay, and then sending a ARQ "NACK" status report, which is itself subject to HARQ delay, followed by HARQ retransmission of the affected packet. Thus three time delays are involved. Having two error correction protocols is disadvantageous in several ways. The RLC ARQ protocol is slower to detect errors, due to these time delays. The ARQ protocol requires additional protocol overhead. The presence of two protocols leads to greater complexity.

Summary

[0008] It is an aim of the present invention to overcome at least one problem of the prior art. In an embodiment, the invention can reduce the rate of occurrence of NACK-to-ACK errors to a low enough level that their occasional but rare occurrences can be tolerated. When a HARQ transmission failure is detected by the HARQ protocol, this is known very quickly by the transmit side, and the only time penalty is for a new HARQ transmission.

[0009] In an embodiment of the invention, the ARQ protocol can be simplified or even dispensed with.

[0010] The present invention discloses a novel error protection mechanism for HARQ feedback where successive acknowledgement messages are jointly coded to improve reliability. Successive acknowledgement messages are channel encoded into feedback signals using a convolutional code with rate klm (see e.g. Lin & Costello Error Control Coding Prentice Hall 1983). With convolutional codes one input block of k information bits arrives per epoch and is coded into an output block of m>k coded bits. The coded signal at the current epoch depends on the input at the current epoch and the λ-l previous input blocks (λ is called the code constraint length). The decoder introduces a delay when decoding HARQ acknowledgements messages but this delay is more than compensated for by the improved performance and the elimination of the large delays due to NACK to ACK errors.

[0011] 3 GPP LTE specification TS 36.212 discloses the joint coding of HARQ

acknowledgements with other information concurrently sent by the receive side such as channel quality. This can be advantageous when other information needs to be sent concurrently with the HARQ feedback signal. [0012] The present invention is described below with reference to exemplary embodiments and the accompanying drawings, in which:

- Figure 1 is diagram illustrating steps in a conventional HARQ process;

- Figure 2 is a diagram of apparatus according to an embodiment of the invention - Figure 3 is a diagram illustrating steps in a method according to an embodiment of the invention

Multi-process HARQ protocols

[0013] In prior art wireless systems such as LTE the link is synchronous in both directions, i.e. HARQ packets are transmitted at known time intervals or air-interface "frames". The corresponding acknowledgement messages for each HARQ packet are returned in a known following frame. In such synchronous systems each epoch corresponds to an air-interface frame. There can be a significant delay between the transmission epoch of an HARQ packet, the acknowledgement epoch and the next transmission or retransmission. The delay arises because the transmitted HARQ packet take time to reach the destination; it is received over a finite time period; the destination receiver must have time to decode the packet and transmit a response; the response takes a finite time to reach the originator and is received over a finite duration; and the source unit must decode and process the response.

[0014] A simple approach would be for the transmit side to wait until it receives

acknowledgement before transmitting a new packet, a "stop-and-wait" protocol. A

disadvantage of stop-and-wait protocols is the transmission medium remains idle and underused because the transmit side cannot send a new packet until an acknowledgement is returned. This uses the transmission medium inefficiently and is called "protocol stalling".

[0015] To avoid stalling prior art wireless systems such as LTE and UMTS use so called multi-process HARQ, the concept of which is illustrated in Figure 1. The stream of HARQ packets is separated by into a number of sub-streams (called "HARQ processes"), which are transmitted in sequential cyclic order in successive epochs. Having transmitted a packet belonging to (say) process 1, the packets for processes 2,3... are transmitted (in fact LTE uses 8 such processes, but here only 4 are illustrated). By the time that these processes are transmitted, sufficient time has elapsed for the packet on process 1 to be acknowledged and a new transmission or retransmission to be ready. Note that only acknowledgement messages for process 1 are illustrated.

[0016] Transmitted packets (205, 206, 207, 208) are sent by the transmit side unit (100) during successive time frames or packet transmission epochs (200) and a corresponding received packet (210,211, 212, 213) is observed by the receive side unit (150) in the same epoch. Epochs at the transmit side and receive side correspond although there may be a delay between the time at which the signal is sent and the time at which it is received due to propagation time of the signal through the transmission medium (199). Packets from successive processes are transmitted in cyclic order, thus packets 205, 206, 207, 208 belong to processes 1, 2, 3, 4 respectively.

[0017] In practice the receive side needs a certain time to process the received packet (210) to determine whether it has received it correctly, and be ready to transmit a feedback signal. In the figure 1, the acknowledgement message (220) is sent in response during epoch 3. Thus for a given packet transmission epoch, there is a known acknowledgement epoch in which the feedback signal is sent, which is subsequent to the packet transmission epoch. Equally the transmit side needs a positive amount of time to receive and process the feedback signal (220). This time needed to process a received signal is called processing delay (230), which is a positive allowance of time which can be used to perform processing actions. The amount of time actually needed to process a received signal may vary between implementations but is limited to a maximum amount by the HARQ protocol. Thus, although the feedback signal is received in epoch 3, the next transmission of a packet for HARQ process 1 is not until epoch 5. Only acknowledgement messages for packets associated with HARQ process 1 (220) is shown, but similar timings apply for the other HARQ processes. Each complete cycle of four HARQ processes is outlined by an oval shape for emphasis.

[0018] In UMTS and LTE there are eight HARQ processes operating concurrently in a time interleaved fashion, each on a stop-and-wait basis. Since successive packets may require different number of HARQ re-transmissions, it may arise that packets are decoded by the HARQ process in a slightly different order to their original transmission. For this reason, HARQ packets contain a sequence number which allows them to be re-assembled in the correct order at the receive side.

Overview

[0019] In an embodiment of the present invention successive HARQ acknowledgement messages are jointly coded and transmitted in successive epochs using a convolutional code. In UMTS and LTE HARQ, acknowledgement messages comprise one bit per transmitted packet (ACK or NACK). An example of suitable codes are non-terminated non-recursive rate l/m linear convolutional codes ( RC), where for each input epoch, one bit is input (k=l) and m coded symbols are output. These output bits may undergo further processes prior to transmission, for example the number of actually transmitted coded bits can be reduced by puncturing techniques.

[0020] In prior art systems there is a known timing correspondence between a HARQ packet transmitted in a certain epoch and the feedback signal in a corresponding later epoch. In the invention there is a known timing correspondence between the epoch in which the HARQ packet is received and its acknowledgment epoch, i.e. the first epoch in which the coded feedback signal is influenced by the contents of the acknowledgement message. However information about the contents of the acknowledgment message is coded over λ successive feedback signals, together with information about other acknowledgement messages.

[0021] The channel coded feedback signal can be jointly decoded with feedback signals from previous and subsequent epochs which (absent noise and channel impairments) unambiguously indicate the contents of the acknowledgement message. To reliably decode the input block at epoch T with a convolutional code of constraint length λ, the decoder should delay at least λ-l epochs after epoch J (i.e. wait for the coded symbols corresponding Χο λ-1 subsequent coded blocks) and perform joint decoding of the input block along with previous and subsequent input blocks. In practice a longer delay than this is required for optimum performance. This time delay has memory implications when applied to acknowledgement messages. First, potential message buffering requirements are increased both in transmit side and receive side. In the transmit side, the HARQ packet cannot be released before an ACK is received. In the receive side, soft information for HARQ packets that have been negatively acknowledged must be stored until the packet is correctly decoded. However the system advantages compensate for increased memory buffer requirements.

[0022] Performance is dependent on the characteristics of the transmission medium. In Rayleigh fading channels affected by Gaussian noise, measurements indicate that a constraint length 3 rate ½ code with decode delay of 8 provides sufficient performance to provide a NACK to ACK error rate of under 10 ^"5 , at the same operating point where prior art systems provide an error rate of 10 ^"3 .

First Embodiment

[0023] Figure 2 presents a block diagram of an arrangement in accordance with an aspect of the invention. The arrangement includes a transmit side unit (100) and a receive side unit (150). The transmit side unit contains a packet source (105) which produces data packets (which may for example be provided from some external source). The HARQ transmit protocol (1 10) assigns each given packet to be transmitted as data by one of the HARQ processes (112), as already described with reference to prior art. The HARQ processes are time serialized by the process multiplexer (115), modulated (120) and transmitted over the radio antenna (140), in the case that the transmission medium (199) is a radio channel. The radio transmission is received at the receive side unit antenna 180, demodulated (170) and multiplexed into received HARQ processes (165) as already described with reference to prior art where it is submitted to the HARQ receiver protocol (160). If reception is successful it is forwarded to the packet destination (155) which may forward the packet to a destination external to the unit. In any event a HARQ acknowledgement message indicating ACK/NACK is encoded by an ACK/NACK encoder (185) modulated (175) and transmitted via the transmission medium (199) to the transmit side. It is demodulated (125) and stored in a delay unit (130). After the required delay the ACK/NACK decoder (135) decodes the feedback signals and submits the result to the HARQ transmit protocol (110) which retransmits the packet or transmits a new packet.

[0024] The present invention introduces three novel elements compared with prior art: a ACK/NACK encoder (185) which convolutionaly encodes sequential acknowledgement messages; a decoding delay via the delay unit (130); and a ACK/NACK decoder unit (135) which decodes the sequentially coded acknowledgement message after an appropriate delay. The decision of whether a given HARQ packet was received correctly can be taken after receiving the feedback signals of the packet of interest and from d subsequent packets, where d is the decoding delay.

[0025] To permit this delay, one or more additional HARQ processes are introduced. Figure 3 illustrates the introduction of an additional fifth process, as compared with the prior art system illustrated in Figure 1. The additional process sends HARQ packets (209) in epochs 5 and 10. Process 1 transmits a packet for the 2 ^nd time in epoch 6. The feedback signals

(220,221) (illustrated by oval shape) corresponding to packets in transmit epoch 1 and 2 are returned in epoch 3 and 4. This arrangement provides a positive amount of time for processing delay between the end of epoch 4 in which the latter feedback signal (221) is received, and the start of epoch 6 in which the next packet (205) is transmitted on the first HARQ process. The transmit side may employ this processing delay to jointly decode both feedback signals (220,221) in order to determine between whether the acknowledgement message for the packet in epoch 1 contained ACK or NACK, and make the decision whether to perform a new transmission or a retransmission. This joint sequential decoding by the ACK/NACK decoder (135) provides coding gain.

[0026] By contrast with prior art systems, a decoding delay d>0 is used, and the transmit side can observe not just the feedback signal corresponding to the epoch of the packet of interest but also the feedback signals corresponding to d succeeding epochs, where the situation for d=l has been illustrated.

[0027] With the present invention, system delay can be reduced compared to systems with separate HARQ and ARQ protocols. Although the number of HARQ processes is increased, delay caused by retransmissions when a HARQ packet transmission fails is reduced since all retransmissions are handled within the HARQ protocol and a NACK-to-ACK error becomes a sufficiently rare event that packet loss in this situation can be tolerated

Intermittent Transmission

[0028] In a further embodiment of the invention, the packet stream may be temporarily suspended, for example in favour of higher priority data in the same or different device. The following measures can be used to ensure that the decoded acknowledgement performance is maintained if such intermittent transmission occurs.

[0029] At the start of packet transmission, or at the resumption of data transmission after a break, the ACK/NACK encoder starts from well-known state, e.g. using the conventional technique that a series of λ-l zeros (e.g. ACKs) preceded the first actually transmitted feedback signal.

[0030] When transmission of a packet stream is terminated or suspended, a novel method is introduced to "terminate" the encoding of acknowledgements and ensure that there is no loss of performance when decoding the acknowledgement messages near the end of the transmission. Once transmission is suspended, there is no more data sent (for example in LTE there is no more allocation for the uplink or downlink shared channels). However, after the last acknowledgement message is sent on all channels, the receive side continues to send d feedback signals in subsequent epochs. These 'hangover' feedback signals do not correspond to a packet transmission, and they are coded using a pre-defined constant input value e.g. ACK. The receive side receives these d 'hangover' feedback signals, and after receiving the last one performs an ACK/NACK decoding decision.

[0031] In prior art systems such as LTE, a downlink control channel indicates when uplink or downlink HARQ packet transmissions take place. Feedback signals are not returned where there is no corresponding received HARQ packet, and there is no means by which the control channel could signal that this is required. To overcome this limitation a novel type of allocation command is used on the control channel. On the downlink, it informs the receive side that it should not expect data this frame but must send a coded feedback signal corresponding a fixed value of its input (say "ACK") to terminate the ACK/NACK encoder. On the uplink, it would inform the transmit side that no data is to be transmitted on the uplink but a feedback signal is sent on the downlink, again encoding a fixed value.

[0032] If LTE requires to reserve particular frames are needed by other transmissions, for example every 8'th epoch is unavailable for the HARQ transmission, this can be done by signalling so that the transmit side does not send packets in certain epochs and the receiver side does not expect them. In this case it would take longer to cycle through the HARQ processes.

Transmission of Multiple HARQ Packets per Epoch

[0033] In a further embodiment of the invention the packet source (105) can simultaneously transmit multiple HARQ packets each epoch. For example using MIMO or carrier

aggregation LTE and similar systems allows a data stream to send several HARQ packets in one frame. In this case the acknowledgement epoch may need to contain feedback signals which correspond to more than one HARQ packet.

[0034] In the present invention the convolutional coder accepts k input bits per coding epoch and generates m output bits per coding epoch. In the above, only the case of k=\ has been described. The invention is easily extended to allow k>l, i.e. to allow k acknowledgement messages to be encoded at each epoch. The k coded bits corresponding to the

acknowledgement messages are coded to m convolutionaly coded bits, at each coding epoch, using well known rate k/m convolutional coding techniques (see Lin and Costello). The resulting m coded bits at each epoch may be further block coded to b bits using an (b, m) block coder (ibid). If c control data bits (such as buffer state information) are to be

"piggybacked" this can be added to the m coded bits prior to the (b, m+c) block coding operation, to produce the transmitted feedback signal onto which control information is piggybacked. When the feedback signal is received, the (b, m+c) block code is decoded, the c piggybacked control information bits removed, the decoded bit values (preferably as log- likihood ratios) are presented to the delay unit (130) and are convolutionaly decoded after an appropriate delay.

[0035] In a development of this embodiment, packets from two or more packet streams can be transmitted in a single epoch. The convolutional coding of multiple acknowledgements is implemented using a convolutional code with k inputs per coding epoch and m outputs as above, where k is sufficiently large to cater for all streams that may be simultaneously present. Where some streams are absent the corresponding inputs may be set to a known constant value such as ACK, and a different (b ', m) block code may be used in that epoch with e.g. fewer output bits b '<b.

Further Embodiments

[0036] Performance can be further improved by the following method which is performed entirely by the transmit side. The HARQ sequential decoder operates as above, but its output is 'double checked' by a second sequential decoder which operates with a much greater decoding delay hence with better performance. If the second sequential decoder finds that the first has made a NACK->ACK error, it marks the affected packet as negatively acknowledged and performs a complete HARQ retransmission of the affected HARQ packet.

[0037] Prior art systems are known where HARQ messages comprise multiple bits per transmitted packet, for example to guide the transmitter on how much power should be used for the next HARQ transmission. The adaptation of this invention to such a system is straightforward.

[0038] Prior art systems are known that use "bundling" to reduce the number of HARQ message. In such systems, one HARQ acknowledgement indicates either all of a group of packets have arrived or at least one was missed. Thus one acknowledgement serves for more than one HARQ packet. This system can accommodate such a technique, using joint coding of successive bundled acknowledgements.

[0039] The invention is not limited to systems with synchronous timing. Provided the receive side can identify packets, and the transmit side can identify feedback signals and determine correspondence with an HARQ packet, the invention can be applied to non- synchronous systems in a straightforward manner that would be apparent to the skilled person. The prior art illustrations above refer to radio systems but nothing prevents the application of this invention to other transmission media, provided HARQ can be

implemented over that media.

[0040] The invention is not limited to use with multiple stop-and-wait processes. Provided the packet sequence number can be determined, for example by a separate control channel, and the number and order of feedback signals is preserved by the transmission medium, the invention can be adapted for use in conjunction with conventional windowed protocol techniques, by including a packet sequence number in the acknowledgement message (which consequently contains multiple bits of information). The transmit side jointly decodes the feedback signals and determines the sequence number of the acknowledged packets.

[0041] The invention may take the form of a computer program containing one or more sequences of machine-readable instructions for instructing a computer to perform a method as disclosed above, or a data storage medium (e.g. semiconductor memory, magnetic or optical disk) having such a computer program stored therein. The descriptions above are intended to be illustrative, not limiting. Thus it will be apparent to one skilled in the art that

modifications may be made to the invention as described without departing from the scope of the claims set out below.