GB2489280A - Hybrid Automatic Repeat Request (HARQ) - Google Patents

Abstract

A method for transmitting a set of data from a transmitter to a receiver comprises the following steps: - receiving at the receiver the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; - detecting at the receiver an error in the set of data by using the error detecting code; - if an error is detected, transmitting a NACK signal to the transmitter and in response the transmitter sending an error correcting code associated with the set of data and having a size smaller than the size of the set of data 560. The receiver using the error correcting code to correct the received set of data. The error detecting code may be a checksum, CRC as is typical. The error correcting code may be parity data or exclusive-OR (XOR) or Reed-Solomon versions of parity data. A further embodiment may involve sending multiple portions of data and providing an error correcting code for plural portions by combining the data portions. The location of the error in the received set of data may be determined using an iterative correction process (Figure 7). The set of data may be an aggregated packet (Figure 3).

Description

METHOD FOR SENDING DATA, METHOD FOR RECEIVING DATA AND ASSOCIATED DEVICES, COMPUTER PROGRAM AND INFORMATION

STORAGE MEANS

The invention relates to data communication between a sender and a receiver, typically via a network.

The invention proposes a technique for transmitting data, e.g. formed as a data stream, by means of a sending device to a receiving device, e.g. through a communications network, and more particularly to wireless communication stations.

Error control techniques are extensively used in data communication systems to restore data integrity when data is corrupted by transmission errors or is lost.

As an example, a radio channel can cause errors in transmitted packets or blocks under the influence of interferences among users, noises and so forth. A data stream is constituted by a plurality of data blocks and is generally protected against transmission errors by an error detection code.

There are many algorithms to cope with errors. These algorithms may be classified into three categories: FEC (Forward Error Correction) techniques, ARQ (Automatic Repeat Request) techniques and hybrid techniques.

The FEC techniques are based on the transmission of redundant information generally generated by error correction codes. In a sending device, the data units of a stream are grouped together in blocks, each block being then encoded so as to generate a plurality of parity blocks forming redundant information. At the receiver device, the data blocks are decoded from the set of received data and parity blocks. The decoding consists in correcting the errors from the data blocks received, using the parity blocks. The probability of error occurrence is lowered by the redundant information additionally sent.

In the ARQ techniques, a return link is used to request retransmission of the erroneous (i.e. containing at least one error) or lost blocks.

An error detecting code, as a checksum for example, is used in combination with a certain retransmission protocol. Thus the receiver can send an Acknowledgement (ACK)/Negative Acknowledgement (NACK) signal for notifying a transmitter of whether or not received blocks are erroneous. The ACK signal confirms to the transmitter that the receiver has correctly received the corresponding blocks. In contrast, the NACK signal confirms to the transmitter that the receiver has failed to receive the corresponding blocks (no reception or wrong checksum). If the transmitter receives the NACK signal, the transmitter retransmits the corresponding blocks to the receiver. Corrupted or lost data blocks are transmitted repeatedly until correctly received by the receiver.

The ARQ and FEC techniques can both be combined and are then called hybrid techniques. This combination also enables the sender to adjust the quantity of redundancy to be sent relatively to the acknowledgements received.

In the prior art, two main families of hybrid techniques are known.

A first family, known as hybrid ARQ type I, relies on the principle by which, in addition to sending the source blocks, the sender sends redundancy blocks (also called parity blocks) generated by an error correction code. The sending of "proactive" parity blocks leads to lower probability of loss of blocks at arrival. If the channel quality is good enough, all transmission errors should be correctable, and the receiver can retrieve the correct source data block. If the channel quality is bad, and not all transmission errors or lost blocks can be recovered, the receiver detects this situation using the error detection code, and then requests a retransmission of the erroneous blocks, as in the case of ARQ.

The second family, known as hybrid ARQ type II, relies on the principle that the sender first sends source blocks with error detection (i.e. proceeds in this first stage in the same manner as standard ARQ) and then, in a second stage, sends "reactive" redundancy blocks (generated by an error correction code) if all the source blocks have not been correctly received. Thus error correction can be attempted by combining the information received from both transmissions. As a result, Hybrid ARQ type II performs with as good capacity as standard ARO.

Patent application WO 2008/037 750 describes such an hybrid ARO type II technique according to which, if a given block is not acknowledged as correctly received, it is combined by the sender with new blocks to be sent, thus producing parity blocks of an error correction code.

The parity blocks only are sent to the receiver, where the new blocks may be deduced from the parity blocks if the given block was actually correctly received (typically in the case of disordering of blocks, e.g. when such a block is received after the NACK was issued at reception). Patent application Wa 2008/037 750 enhances efficiency (bandwidth consumption) of typical hybrid ARQ type II in the case of late delivery of blocks.

As clear from this example, it is common wisdom that FEC and ARO granularity resides in block-by-block basis. This is because, if an error is not located more accurately than at the block level, it seems necessary for the sender to provide information allowing to correct the whole block.

In this context, the invention provides a method for receiving a set of data, comprising the following steps: -receiving the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; -detecting at least an error in the set of data by using the error detecting code; -if an error is detected, receiving an error correcting code associated with the set of data and having a size smaller than the size of the set of data.

Although the size of the error correcting code is smaller than the size of the set of data, it is generally possible to recover the set of data as explained below, e.g. using the error detecting code.

When the set of data comprises a plurality of data portions, said method may comprise correcting the set of data using the error correcting code and considering successively each of at least two data portions among said data portions is erroneous, possibly each of said data portions is erreonous.

According to such an iterative process, it is possible to recover the set of data when the data portion that is actually erroneous is considered. This is because data correction is generally easier when errors are located and they are located in one of the iterations performed, La when the actually erroneous data portion is considered.

According to a first possible embodiment, the method may comprise: -a step of determining a corrected data portion associated with a given received data portion based on the error correcting code and received data portions different from the given data portion; -a step of detecting an error, by using the error detecting code, in the set of data where said given data portion is replaced with said corrected data portion.

The error detecting code is thus used to check whether replacement of the given portion with the corrected data portion allows recovery of the correct set of data.

In this case, it may be provided that the step of determining a corrected data portion and the step of detecting an error are successively repeated each time with a different given data portion until no error is detected in the detecting step. The iterative process mentioned above is thus used until the relevant portion is considered as determined thanks to the error detecting code. The error correcting code used is for instance a combination of XOR operations, as further explained below. The main advantage of this iterative process is to increase the error correction capacity since the localization of errors is performed outside the error correction decoding.

According to a second possible embodiment, said method may comprise a step of performing a decoding operation based the error correcting code and received data portions different from the at least one given data portion. Such a decoding operation tries to recover said given data portion(s) thanks to the error correcting code received. The code used is for instance a Reed-Solomon code, as further explained below.

The step of performing a decoding operation may then be successively repeated each time with a different given data portion until said decoding operation is successful. It is considered in such a case that the correcting capacity of the code is suficient to successfully decode the error correcting code and received data portions only when the actual erroneous portion(s) is considered as the given data portion(s). Checking with the error detecting code, altough possible, is thus not necessary in such a situation.

The invention also provides a method for sending a set of data, comprising the following steps: -sending the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; -receiving an indication of an error associated with the set of data; -computing an error correcting code associated with the set of data and having a size smaller than the size of the set of data; -sending the computed error correcting code.

This sending method corresponds to the receiving method described above.

When the set of data comprises a plurality of data portions, said error correcting code is computed for instance by combining the data portions; in possible embodiments, combination may be implemented by XOR operations or by Reed-Solomon coding, as further explained below.

When the set of data comprises a plurality of data portions having a common size, the size of the error correction code may in practice be equal to said common size or to a multiple thereof.

The method may also comprise a step of determining the size of the error correcting code based on data indicative of a failure to correct said error based on a previously sent error correcting code. The size of the error correcting code (e.g. parity data units or sub-elements) may thus increase when a preceding attempt to correct was unsuccessful.

The invention also provides a device for receiving a set of data, comprising means for receiving the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; means for detecting at least an error in the set of data by using the error detecting code; and means for receiving an error correcting code associated with the set of data and having a size smaller than the size of the set of data.

In addition, the invention provides a device for sending a set of data, comprising means for sending the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; means for receiving an indication of an error associated with the set of data; means for computing an error correcting code associated with the set of data and having a size smaller than the size of the set of data; and means for sending the computed error correcting code.

Optional features presented above in connection with the receiving and sending methods may also apply to these devices.

The invention furthermore provides a computer program comprising instructions for implementing one of the methods presented above when the program is loaded and executed by a programmable apparatus.

The invention also provides an information storage means, readable by a programmable apparatus, storing computer program instructions for implementing one of the methods presented above when the program is loaded and executed by the programmable apparatus.

Other features and advantages of the invention will appear in light of the following description, made with reference to the appended drawings, where: -Figure 1 shows an examplary communication system; -Figure 2 shows a possible embodiment of a communication apparatus; -Figure 3 illustrates the aggregation scheme proposed by the 802.lln standard; -Figure 4 illustrates the structure of a 802.lla/b/g block acknowledgement message; -Figure 5 is a block diagram showing a method for transmitting data according to a possible embodiment of the invention; -Figure 6 is a block diagram showing a method for receiving data according to a possible embodiment of the invention; -Figure 7 is a block diagram showing a recovery method proposed in an embodiment of the invention.

Figure 1 shows an example of a communication system where the present invention can be implemented. A sending device 101 transmits a plurality of data packets or blocks to a receiving device 102 through a transmission channel 100 that may drop or corrupt the data packets. Feedback information is transmitted from the receiving device 102 to the sending device 101 in order to provide status information on the received data packets.

Figure 2 is a block diagram illustrating a schematic configuration of a communication apparatus 200. The sending device 101 and the receiving device 102 of Figure 1 are for instance each implemented by such a communication apparatus.

Reference numeral 202 corresponds to a random-access memory or RAM, which functions as a main memory, used by a central processing unit (or CPU) 201. The memory capacity of RAM 202 can optionally be expanded by an optional RAM connected to an expansion port (not illustrated). CPU 201 is capable of executing instructions stored in program read-only memory or ROM 203 on powering up of the communicating apparatus. After the powering up, CPU 201 is capable of executing instructions from main memory 202 relating to a software application after those instructions have been loaded from the program ROM 203 or the hard-disc (HD) 206 for example. Such software application, when executed by the CPU 201, causes the steps of the process shown in the flowcharts of Figure 6 and/or Figure 7 to be performed.

Reference numeral 204 corresponds to a network interface that allows the connection of the communication apparatus 200 to the communication channel 100. Data blocks are written to the network interface for transmission or read from the network interface for reception under the control of the software application running in the CPU 201. Reference numeral 205 represents a user interface to display information to, and/or receive inputs from, a user.

An example of a communication system as shown in Figure 1 is a wireless network, such as Wireless Local Area Network (WLAN), where a sending device 101 and a receiving device 102 may operate. An example of such environments is described in IEEE 802.lln-2009, which is an amendment to the IEEE 802.11-2007 wireless networking standard aiming at improving network throughput over the two previous standards -802.lla and 802.llg -with a significant increase in the maximum raw data rate from 54 Mbitls to 600 Mbit/s.

Aside many improvements, IEEE-802.lln has improved the efficiency of the MAC (Media Access Control) protocol using a single acknowledgment (ACK) mechanism for multiple frames and the ability to aggregate multiple frames into a single transmission.

The 802.11 n standard provides that multiple data blocks can be sent per single access to the medium by combining blocks together into one larger set of data, called a frame herebelow. Thus, there are two forms of aggregation: Aggregated Mac Service Data Unit (A-MSDU) and Aggregated Mac Protocol Data Unit (A-MPDU): -A-MSDU creates a block (almost 8 kbytes) by combining data units (typically Mac Service Data Unit, or MSDU, received from the upper layer of network protocol stack) with the same physical source and destination end points and the same traffic class (i.e. 005) into a (larger) block with a common MAC header; -A-MPDU (up to 64k bytes) is essentially a chain of individual 802.11 blocks sent back-to-back with one access to the medium. All the MPDU blocks within an A-MPDU frame are addressed to the same receiver address.

Figure 3 shows the complete aggregation scheme proposed by 802.lln.

The typical 802.11 MAC block (MPDU block 320) can transport an A-MSDU encapsulation 322, formed of K unitary MSDU data units 330, each containing: -an MSDU 340 received from the upper layer; -the data unit header 3301, having a length of 14 octets (Le. 14 8-bit bytes) and consisting of a 16-bit MSDU length field, a 6-octet source address of the constituent MSDU 340, and a 6-octet destination address of the constituent MSDU. The MSDU length field indicates the length, in octets, of the constituent MSDU 340; -padding 3302: the header 3301 together with MSDU 340 are padded with 0 to 3 bytes to round the data unit 330 to a 32-bit word boundary.

The MAC header 321 of MPDU block 320 is a classical 802.11 MAC header (30 byte-long) comprising: -the destination address of the A-MSDU, to. the address of the receiving device that is the next immediate intended receiver of the aggregated frame; -the source address of the A-MSDU, to. the MAC address of the transmitting device that created the A-MSDU; -other fields (Frame control, Duration/ID, Sequence Control, QoS control and HT Control) that characterize the MSDUs of the A-MSDU body 322: the QoS control contains for example one bit flag indicating the presence of an A-MSDU in the body of the MAC frame.

The FCS (Frame Check Sequence) field 323 of MPDU block 320 is the classical CRC-32 checksum (to. error detection code), used to validate the integrity of the MPDU block 320.

In an A-MPDU frame 300, fully formed MPDU blocks 320 are logically aggregated at the bottom of the MAC layer. Each MFDU block 320 is prefixed by a MPDU delimiter 310 and possibly padded (by padding zone 3102) to round to a 32-bit word boundary. The MPDU delimiter 3101 embeds a proper CRC field and a length field, useful for a receiver to respectively validate its integrity and parse the A-MPDU framing structure.

In order to improve transport efficiency, A-MSDU aggregation may be used in combination with A-MPDU aggregation to increase the amount of data in a single transmission.

Like any wireless transmission, the larger the frame is, the less likely it will be received with no errors. Accordingly the standard provides that, unlike in an A-MSDU, individual MPDU blocks 320 have their own error detecting code or CRC: an error in one MPDU block 320 can thus be distinguished from errors affecting other MPDU blocks 320 in the A-MPDU frame 300.

It should be noticed also that error in wireless transmission are generally related to data integrity, whereas error in wired transmission are mostly due to data loss (due to network congestion).

Figure 4 displays the format of a 802.llaIbIg/n Block-Acknowledgement message (BA message, 400).

To inform the sender which blocks have been lost in a frame, a "Block ACK Bitmap" field 440 is designed in the BA message 400 as illustrated.

It is a 8-byte field in case of compressed BA (802.11 n) or 128-byte field in case of uncompressed BA (802.lla/b/g), and thus it can support up to 128 * 8 = 1024 blocks in a single frame.

A "Block ACK Starting Sequence Control' field 430 is used to record the sequence number of the first block in the frame concerned. A "BA control' field 420 is used for quality-of-service negotiation between sender and receiver MAC layers (e.g. acknowledgement policy, compressed BA or not, traffic identifiers). A "BA header" 410 contains the address of the transmitter and of the receiver, for instance. The FCS field 450 is the classical CRC-32 checksum, used to validate the integrity of the BA message.

Figure 5 shows a transmitting method according to an embodiment of the present invention, implemented here at the sending device 101. This method allows the transmission of blocks from a list L of blocks to be transmitted.

The list L represents for example a buffer memory containing packets of data. A packet is written in the buffer if it is to be transmitted, and is removed from the buffer after being transmitted. Consequently, the buffer memory, and thus the list L, is assumed to be continuously updated by the sending device 101 in order to contain only packets that are waiting for transmission. The way of implementing the list L described above is not limitative and any other implementation can be used, such as using one buffer memory for storing all packets and tagging those that are waiting for transmission.

In accordance with 802.lln usage, the L blocks are MPDU blocks 320. According to the used aggregation scheme (mostly related to MSDU data unit size), those blocks contain upper layer MSDU 340 which are encapsulated in any of the following modes: -in MSDU data units 330 according to Figure 3 (dual aggregation scheme) -in MPDU blocks 310 (single MPDU aggregation scheme).

The sending device 101 transmits data blocks from the list L (step 510) to the receiving device 102 with a CRC checksum appended to each said data block and monitors the received acknowledgments to determine if there exist any unacknowledged data blocks (step 520).

In accordance to 802.lln usage, an acknowledgement for any of the L blocks is a 802.lln Block-acknowledgement 400 (following 802.11 standard recommendations). The "Block ACK Starting Sequence Control' field 430 associated with the "Block ACK Bitmap" field 440 indicates the MPDU block(s) in error (considered as "unacknowledged', or also called "negatively acknowledged').

If it is determined that at least one (MPDU) data block is unacknowledged, a recovery procedure is executed based on the teachings of the present invention following the steps 530 to 560 as now explained.

In step 530, one (e.g. MPDU 320) block is selected among the negatively acknowledged packets. Contrary to the prior art solution consisting in retransmitting the whole lost packet, it is proposed here to retransmit a packet which size will be a sub-part of (i.e. strictly smaller than) the original packet size.

In this respect, in step 540, a value k (k being an integer strictly greater than 1) is determined such that retransmission will be implemented based on data having a size of 1/k of the original block size, or a multiple thereof (while remaining strictly smaller in size than the original block). The value k can be derived in practice from either: -a packet error rate (PER) statistic: for example, a given PER (e.g. %) would require a number M of parity data units, with M=PER*K, to support theoretically a successful recovery phase (of the K data units forming the block) at the receiver; it may be reminded that, in a conventional manner, a correcting code must be such that the percentage of parity elements relative to the number of data elements is at least equal to the percentage loss (PER) on the network; -according to the aggregation scheme used at initial transmission if dual aggregation was used (as explained above in the context of 802.lln), k may for instance take the value of the number K of data units 330 in the original MPDU block 310.

In prior art solutions, the encoder has to inform the decoder about the coding parameters. Typically, a block code C' takes a K'-symbol information word and transforms this into an N'-symbol codeword, where N' > K' and M'=N'-K' represents the amount M' of redundancy added by the code.

In the solution proposed here, the parameters n and k of the code may not have to be set once for all and shared during a setting step between the encoder at the sending device and the decoder at the receiving device. The coding scheme used is however known at the transmitter and at the transmitter; it may for instance be a fixed coding scheme. The number k of data units (or sub-elements) in the data block to be combined in a parity data unit as explained below may be kept dynamic and may thus vary from one data packet to another, according to step 540 where a given value k is selected.

In addition, packet error statistics may for instance be a fruitful means to determine the redundancy level (Le. the number M=n-k of parity data units) with respect to a given set of k data units or sub-elements. As will be explained further below in reference to Figure 6 (step 660), the receiver is able to provide the result of a recovery phase for an erroneous data packet. If the sender receives such an indication (precisely, in the frame of the 802.11 standard, receiving a first negative Block-acknowledgement for the erroneous data block, and further a second negative Block-acknowledgement indicating the retransmission was not sufficient to recover the original data block), then the receiver would increase the redundancy level of the parity code. Such a process is advantageous in that the retransmission exchanges are reduced (they may start with 1 redundancy data unit for each set of k data units); this reduces in consequence the latency for error recovery.

As will be seen later in reference to Figure 6, the decoder at the receiver location could detect values n and k as follows: -If dual aggregation is used and it is chosen to use k=K as mentioned above, the source data (received initially) dynamically indicates a number of MSDU data units 330 in the concerned erroneous MPDU (thus the value K). The size of the parity element (from which the values M and n=k+M can be determined) would be the value of the greater MSDU data units 330 (padding is used for other MSDU data units 330 if required in calculation, like in the case of VBR video transport where several successive MSDUs have different payload sizes).

-In other case, the size of retransmitted packet(s) dynamically indicates the value k. It should be noted that, as mentioned above, the size of the retransmitted packet is a multiple of (1/k) times the original size of the erroneous MPDU packet.

-The number of retransmitted parity data units dynamically indicates the number M of redundancy FECs.

Generating M parity data units (or sub-elements) from k data units (or sub-elements), as in step 550, can be implemented with various error-correcting codes in order to encode the parity data, such as a Reed-Solomon code (where a given number of parity codes allows correction of the same number of errors), or the simplest, such as a code based on the use of EXCLUSIVE-ORs (XORs) (where only one parity code is used) as further explained below.

The correcting capacity of a code is defined by its minimum distance D and depends on the rate of the code (k/n) and how the parity symbols are generated from the information symbols. The greater the minimum distance, the higher is the correcting capacity of the code. The highest correcting capacity is obtained when D = n -k + 1. Codes providing such minimum distance are called maximum distance separable (MDS) codes. Reed-Solomon codes (RS codes) are well known MDS codes that provide efficient encoding.

In the context of a use of an error-correcting code of Reed-Solomon type, the encoding can be performed at packet level, by choosing a Reed-Solomon code RS( (k+M)*MSDU_size, k*MSDU_size), where MSDU_size is the size of a MSDU data unit 330. Techniques to generate parity packets from a plurality of data packets using a code C(n,k) are also proposed in patent application W02008/037750.

In the context of a use of EXCLUSIVE ORs (XOR5) to generate a parity data unit, the k source data units are combined as follows: -let "P1,P2,...,Pk" be the k data units of the stream, each data unit having a size of m bits, and "p7 be the value of the ith bit of the data unit p -let "1' be the parity packet to be generated and ?" be the value of the ith bit of the parity packet; -then: = pmod2)Vi e {1,..,m} Thus, it is sufficient to perform the bit-by-bit sum over the k data units received to obtain the parity data unit, thanks to which it will be possible to recover at the receiver side the lost sub-packet based on the k+1 data units (k data units initially received and 1 parity data unit). This operation, which is very easy to implement on embedded hardware, requires one processing cycle (or CPU -Central Processing Unit -cycle) for each code word transmitted, which induces a very low processing time.

Once the M parity sub-elements or data units computed, step 560 will proceed to the encapsulation of these data units as new retransmission packet(s) to be sent. A retransmitted packet will carry the parity sub-element(s) having a sequence number (or windowing marking) that is identical and the same as the source block, in 802.lln context, MAC Header 320 has to be composed as follow: the retry' flag is set to 1 in the "Frame control' field, and the "Sequence Control' duplicates the starting sequence number used for the erroneous source packet. If M>1, an aggregation scheme like A-MSDU is preferably used to convey the several parity data units (or sub-elements), so that the receiver will automatically detect the parity values thanks to: -the number of parity MSDU data units present in the retransmitted MPDU (value M), and -the size of any parity MSDU which allows to determine the number K ( K= original_MPDU_320_size I MSDU_ 340_size).

An advantage of such a scheme is to allow the receiver to know if a classical retransmission is occurring (MPDU size equals original size, readable through the MPDU delimiter 3101), or otherwise if parity coding according to the invention is used.

Figure 6 shows a receiving method according to an embodiment of the present invention, implemented at the receiving device 102. This method allows the recovery of erroneous data blocks from a list L of data blocks (e.g. MPDU in 802.11 context) transmitted by the sending device 101, when a sufficient number of parity sub-elements (e.g. parity MSDU data units sent according step 560 in the 802.11 context) have been received, by avoiding the reception of whole-size retransmitted data blocks.

At step 610, parity sub-elements and data blocks are received by the receiving device. In step 620, the receiving device uses control information included in the header of the received packets to identify the existence of a retransmitted data (in 802.lln, the retry' flag should be set to 1 in the "Frame control' field of 321), and uses the length of received data (in 802.lln, the MPDU delimiter 3101 contains such a field) to identify the existence of parity data (parity sub-elements) as provided by the invention (instead of classical retransmitted data, which would have the same size as data received during original transmission).

If test 620 is positive, parity data is processed by steps 630 and 700.

If test 620 is negative, step 640 is executed (normal behaviour, i.e. the received data are data blocks received for the first time or retransmitted).

If it is determined at step 640 that the received packet is erroneous (FCS 323 is false), the receiving device 102 requests additional retransmission packets belonging to the same sequence, for instance in the form of parity data units or sub-elements as proposed above. When such packets are received (step 620 is then positive), steps 630, 600 and 650 are executed to determine if the recovery is now possible, as now explained.

In step 630, the M parity sub-element(s) are extracted from the retransmission packet. According to the retransmitted packet structure (see explanations in connection with step 560), the coding parameters (value k and number M of parity sub-elements) are determined in order to perform the decoding step 700. Those extracted sub-elements will be processed by step 700, as explained below with reference to Figure 7. If recovery step 700 is successful (test 650 positive), the process ends: a positive acknowledgement relating to the original packet is sent at step to the sender. Otherwise (test 650 negative), step 660 is executed.

At step 660, feedback information sent from the receiving device informs the sending device about the recoverability status of the packet block, and thus triggers the transmission by the sending device of further packets if necessary (see explanations above in connection with step 550).

As already mentioned, the receiver does not know (i.e. has no way of detetermining), based on error detection codes received, which data unit (here which MSDU data unit) is incorrect in the whole erroneous block (because the block has a unique CRCIFCS checksum covering the whole block, and no checksum dedicated per data unit).

Figure 7 shows an exemplary method to locate the error using the parity data received, here in the context of a solution using an EXCLUSIVE ORs (XOR5) to generate a parity data as mentioned above. As further explained below, the receiver has to iterate to find the right place where the error was located, and thus in the present case where to introduce the parity sub-element, and to re-check, at each iteration, the whole block integrity.

Steps 710 and 720 allow a loop to place the parity sub-element, from index 1 to maximum index K (where K is the number of sub-elements in the original whole block, this block containing a FCS checksum).

For a given location index i of the parity sub-element, steps 730 and 740 support the XOR decoding of a virtually reconstructed block. The decoding (here the bit-wise addition of original sub-elements, except for the sub-element of index i which is replaced by the parity sub-element) results in providing a sub-element Si, which would be the original sub-element at place i (if the error is actually located here).

To validate this, the resulting block is reconstructed with Si at place i (step 750), and error detection thanks to the FCS checksum is performed (step 760) : if the built checksum (i.e. the checksum of the resulting block) is the same as the original FCS field of the previously received original data block (e.g. field 323 of block 320, in the 802.11 context), test 770 is positive: the recovery procedure is successful and the recovered packet is sent back to step 650 of figure 6 with a success indication.

If the built checksum is different than the original FCS checksum (test 770 negative), a new loop is performed by moving the place of the parity sub-element to place i-'-l (thanks to the loop mentioned above). In case all indexes have been tested, algorithm ends at test 780 with a failure indication sent to step 650 of figure 6.

When using an error-correcting code of Reed-Solomon type applied at block level (instead of the coding obtained by XOR5) as proposed above, the procedure may be easily derived from the procedure just described in the case of a code based on XORs.

Precisely, all the received M parity data units (received during retransmission), along with K source data units (i.e. the original block divided in K sub-elements) are provided to the RS(n,K) decoder. The iteration loop is kept in order to test a RS decoding for each possible location (determined by an index i) of the erroneous MSDU data unit. In case of multiple errors (thus multiple parity data units), several indexes are managed and the various possible combinations of locations for each parity packet are tested.

If a RS decoding is successful, the loop ends. This is an important advantage of the proposed algorithm, to increase efficiency of RS decoding: as known in the art, when locations of the error symbols are not known in advance, then a Reed-Solomon code can correct half as many errors as there are redundant symbols added to the block. So by iteratively trying several error locations (like an erasure), the RS code (like any MDS code, see above) is able to obtain its highest correcting capacity.

As a result, if recovery was successfully performed, the reconstructed block is sent back to step 650 of figure 6 with a success indication. Otherwise, a failure indication is provided. It may be noted that there is no need to check the associated FCS after the successful RS decoding because Reed-Solomon has an extremely low probability of error.

The above example is only a possible implementation of the invention, which is not limited thereto.

Claims (14)

1. CLAIMS1. Method for receiving a set of data, comprising the following steps: -receiving the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; -detecting at least an error in the set of data by using the error detecting code; -if an error is detected, receiving an error correcting code associated with the set of data and having a size smaller than the size of the set ofdata.
2. 2. Method according to claim 1, wherein the set of data comprises a plurality of data portions, said method comprising correcting the set of data using the error correcting code and considering successively each of said data portions is erroneous.
3. 3. Method according to claim 1, wherein the set of data comprises a plurality of data portions, said method comprising: -a step of determining a corrected data portion associated with a given received data portion based on the error correcting code and received data portions different from the given data portion; -a step of detecting an error, by using the error detecting code, in the set of data where said given data portion is replaced with said corrected data portion.
4. 4. Method according to claim 3, wherein the step of determining a corrected data portion and the step of detecting an error are successively repeated each time with a different given data portion until no error is detected in the detecting step.
5. 5. Method according to claim 1, wherein the set of data comprises a plurality of data portions including at least one given data portion, said method comprising a step of performing a decoding operation based the error correcting code and received data portions different from the at least one given data portion.
6. 6. Method according to claim 5, wherein the step of performing a decoding operation is successively repeated each time with a different given data portion until said decoding operation is successful.
7. 7. Method for sending a set of data, comprising the following steps: -sending the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; -receiving an indication of an error associated with the set of data; -computing an error correcting code associated with the set of data and having a size smaller than the size of the set of data; -sending the computed error correcting code.
8. 8. Method according to claim 7, wherein the set of data comprises a plurality of data portions and wherein said error correcting code is computed by combining the data portions.
9. 9. Method according to claim 7, wherein the set of data comprises a plurality of data portions having a common size and wherein the size of the error correction code is equal to said common size or to a multiple thereof.
10. 10. Method according to any of claims 7-9, comprising a step of determining the size of the error correcting code based on data indicative of a failure to correct said error based on a previously sent error correcting code.
11. 11. Device for receiving a set of data, comprising: -means for receiving the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; -means for detecting at least an error in the set of data by using the error detecting code; -means for receiving an error correcting code associated with the set of data and having a size smaller than the size of the set of data.
12. 12. Device for sending a set of data, comprising: -means for sending the set of data and an error detecting code adapted to detect an error whatever its location in the set of data; -means for receiving an indication of an error associated with the set of data; -means for computing an error correcting code associated with the set of data and having a size smaller than the size of the set of data; -means for sending the computed error correcting code.
13. 13. Computer program comprising instructions for implementing the method according to any claims I to 10 when the program is loaded and executed by a programmable apparatus.
14. 14. Information storage means, readable by a programmable apparatus, storing computer program instructions for implementing the method according to any claims 1 to 10 when the program is loaded and executed by the programmable apparatus.