HK1018559B - Method and apparatus for data recovery in arq system - Google Patents

Description

Method and apparatus for recovering data in automatic repeat request system

Technical Field

The present invention relates generally to the field of data processing and communications, and more particularly to recovery of data transmitted over a communication channel and retrieved from memory.

Background

In digital data systems, it is common for data stored in memory and transmitted over a communication channel to be corrupted by errors. The techniques typically used to detect errors and/or correct detected errors are various. One example of an error detection technique is the well-known Cyclic Redundancy Code (CRC) check. Other techniques using information block codes and convolutional codes can perform both error detection and error correction. Additional coding bits are added to the data bits for error detection and correction. When data is received from a communication channel or retrieved from memory, the received or retrieved data is decoded in the same manner with additional bits to detect if some of the data is in error. One way to consider these decoding processes is to model them as a human being's ability to correct spelling errors when reading printed text. Because words differ greatly from one another, readers intuitively know what meaning that word has.

These error detection and/or correction coding techniques all add redundant information to varying degrees. Adding more redundancy to a unit of data makes it easier for errors to be correctly detected and, in some cases, corrected. Unfortunately, as the number of coding/redundancy bits increases, the overall "throughput" of the data decreases. In other words, the actual data content transmitted per unit time is reduced. Furthermore, as the number of encoding/redundancy bits increases, the complexity of the encoding/decoding algorithm increases, which consumes limited data processing resources and slows down the data processing time.

In certain relatively "clean" environments, where data is less likely to be corrupted, fewer encoding/redundancy bits may be used in conjunction with a simpler error detection and/or correction process. However, such simplification is often not an option in less favorable environments with a significant amount of noise, interference, etc. Consider, for example, a wireless communication environment. The radio frequency communication channel is blocked by a number of disruptive factors including noise that is present throughout, nearly continuously changing communication channel characteristics, multipath fading, time drifts that cause inter-symbol interference, interference from adjacent channel communications, and a large group of other factors.

One communication protocol (i.e., process) used to protect against these various corrupting factors is automatic repeat request (ARQ) transactions. Pure ARQ systems that use only error detection-error correction are not used. More specifically, a data packet with some type of error detection bit/code is transmitted from a transmitter to a receiver over a communication channel. The receiver processes each received data packet with error detection bits contained in the data packet to determine whether the data packet was received correctly. If the packet is received completely accurately, the receiver sends back an acknowledgement signal (ACK) to the transmitter. If an error is detected, the receiver sends a Negative Acknowledgement (NAK) back to the transmitter and discards the packet, waiting for the same packet to be retransmitted from the transmitter. In addition, a predetermined timing window is defined to allow the transmitter sufficient time to transmit information, the receiver sufficient time to receive and process information, and then an ACK or NAK signal is transmitted to the transmitter. If the transmitter does not receive an ACK within a predetermined window or receives a NAK signal during the window, the transmitter retransmits the data packet.

In an environment, such as wireless communications, where noise or other data may be corrupted, a large number of retransmissions may occur before the data is properly received. It is worth noting that. Regardless of how many times a data packet is sent/retransmitted, the receiver does not become "clever" to understand how to decode the correct information from a later retransmitted data packet. In other words, the probability of correctly receiving a packet in any given retransmission of a data packet is no better than the probability of the previous retransmission of that packet.

One possible option to improve such ARQ protocols is to add Forward Error Correction (FEC) bits to the data packets to permit some degree of bit correction. An example of such a "hybrid" technique is to replace the CRC error detection bits with Bose-Chaudhuri-hocquenghem (bch) parity bits. If the receiver can correct the erroneous bits, an acknowledgement can be sent to the transmitter without further retransmission. Even with such a hybrid technique that can correct a limited number of forms of errors, such a hybrid technique (as with pure ARQ protocols) does not utilize the information contained in previously received packets. Data packets with errors under pure ARQ protocols or with errors that cannot be corrected using hybrid techniques are simply discarded and require a continuous sequence of retransmissions.

What is needed is a data recovery technique that can be used, for example, in ARQ protocols that utilizes information contained in previously transmitted data packets, i.e., data packets that have errors, rather than discarding them, so that currently received retransmitted data packets can be corrected using information from previously received data packets. Many bits in previously transmitted packets are likely to be correct, while in most cases only one or a few bits are corrupted. It is a primary object of the present invention to utilize the correct information accumulated from previously transmitted packets to generate correct data packets. However, such a technique should not consume excessive processing time and, possibly, should minimize the amount of memory required for such processing so that the technique can be used in a variety of different environments with limited memory resources, such as in portable/mobile wireless devices. Therefore, it would be attractive to have forward error correction in an ARQ protocol without adding forward error correction bits to each data packet.

Disclosure of Invention

It is an object of the invention to provide a data recovery system in which correct data units are recovered using information contained in previously received/transmitted but unacceptable data units.

It is a further object of this invention to provide such a data recovery technique in the context of automatic repeat request (ARQ) transactions. So that the data can be corrected without having to add further forward error correction bits on the data unit.

It is a further object of the present invention to provide an error recovery technique that can effectively recover data in a harsh environment without adding forward error correction bits to the data packets, without requiring a complex forward error data correction encoding process, or without requiring significant memory resources.

The present invention addresses the various problems noted above and meets these and other objectives. In an automatic repeat request data transmission system in which data units are received, checked for errors, and retransmitted if errors are detected, thereby producing a group of data units, for such a system the invention performs a first reconstruction operation on alternate data units in the sequence and performs a second reconstruction operation on other data units in the sequence to reconstruct an acceptable data unit. One of the reconstruction operations may include determining a majority voted data unit based on a currently received data unit and a previously received data unit in the sequence. Additional reconstruction operations may include performing a direct comparison of the majority voted data with the currently received data unit to identify those bit positions having different bit values. The bit value or values at those bit positions are changed in order to expect a correct data unit to be generated. The alternative application of the voting and packet comparison reconstruction techniques in a pure automatic repeat request (ARQ) environment (i.e., an environment without forward error correction) is extremely efficient because in a high bit error rate environment a communication unit can significantly improve its performance and increase the probability of correctly receiving a transmitted packet in a shorter period of time.

In a preferred embodiment using alternating majority voting and group comparison data cell reconstruction techniques, the majority voting is less effective when the voted group is even because it is difficult to resolve a "split fall" vote. For example, if there are 4 packets participating in the vote, what value should be assigned to a bit position when there are two packets with a bit position having a value of "1" and two packets with a bit position having a value of "0? Rather than arbitrarily selecting a "1" or "0," the preferred embodiment of the present invention employs majority voting only for odd-numbered received data packets and directly compares the currently received data packet to the majority voted packet for even-numbered data packets to avoid this tie-breaking dilemma. In both majority voting and direct comparison techniques, information in previously received data packets is utilized, which increases the likelihood of obtaining a correct packet.

Since the majority voting and direct comparison operations are relatively simple to implement, a relatively small amount of data processing resources and time are consumed. The present invention also provides a new technique for utilizing information contained in previously received but erroneous packets with a minimum amount of memory. Although the information in the erroneous packet received from the previous is preserved, the packet itself is not stored. Instead, the present invention accumulates the sum of the bits at each corresponding bit position in the reconstructed data packet from each received data unit at that bit position. A threshold is then determined based on the number of data units retransmitted in the sequence, to which each accumulated sum is compared. If the accumulated sum is less than or equal to the threshold value, the bit value of the corresponding bit position of the reconstructed data packet is specified as 0. Otherwise, the bit value of the corresponding bit position in the reconstructed data packet is defined as 1.

The technical scheme of the invention comprises the following steps:

a data processing method includes:

receiving an erroneous version of a sequence of data packets, the sequence comprising a first version and one or more retransmitted versions;

reconstructing the data packet using the sequence, comprising:

-determining whether the currently received version with errors is an odd or even number of said sequences;

-performing a first data packet reconstruction operation or a second data packet reconstruction operation depending on the result of the determining step;

-wherein said first data packet reconstruction operation comprises performing a majority voting operation on a version of said sequence to produce a majority voted data packet that is a reconstructed data packet of the first data packet reconstruction operation;

-wherein the second data packet reconstruction operation comprises: comparing a majority voted data packet of a previously performed first data packet reconstruction operation with said currently received version, identifying one or more positions having different bit values, and changing one or more of the bit values, the data packet having one or more changed bit positions being a reconstructed data packet of the second data packet reconstruction operation;

-checking the reconstructed data packet for errors; and

-sending an acknowledgement signal if the reconstructed data packet is found acceptable in said checking step.

(ii) a receiver for use in a data communication system in which a transmitter is arranged to transmit a data packet a plurality of times over a data communication link to produce a sequence of erroneous versions of said data packet, said receiver comprising a data processor and a transceiver coupled to the data communication link for receiving the sequence, wherein the data processor is arranged to reconstruct said data packet using apparatus comprising:

-means for determining whether a currently received version with errors is an odd or even number of said sequences;

-means for performing either a first data packet reconstruction operation or a second data packet reconstruction operation in dependence upon the determination made by said determining means, wherein said first data packet reconstruction operation comprises performing a majority voting operation on the version of said sequence to produce a majority voted data packet that is the reconstructed data packet of the first data packet reconstruction operation, and wherein the second data packet reconstruction comprises: comparing a majority voted data packet of a previously performed first data packet reconstruction operation with said currently received version, identifying one or more positions having different bit values, and changing one or more of the bit values, the data packet having the one or more changed bit values being a reconstructed data packet of a second data packet reconstruction operation;

-means for checking the reconstructed data packet for errors; and

-means for sending an acknowledgement signal when the reconstructed data packet is found to be acceptable in said checking step.

Drawings

These and other objects of the invention, as well as certain embodiments of the invention, will be described in conjunction with the following drawings, wherein like reference numerals denote like elements, and wherein:

FIG. 1 is a functional block diagram of a data communication system according to one embodiment of the present invention;

FIG. 2 is a flow diagram illustrating a method according to one embodiment of the invention;

3A-3C illustrate examples of data messages and data packets contained in the data messages;

FIG. 4 illustrates a majority vote packet;

FIG. 5 illustrates a bit accumulation function according to one embodiment of the present invention;

FIG. 6 illustrates a direct comparison of a received data packet and a majority vote packet;

fig. 7 is a schematic diagram of a multi-site relay wireless communication system in which the present invention may be embodied;

FIG. 8 is a functional block diagram of a wireless data network in which the present invention may be used;

fig. 9 is a functional block diagram of a portable/mobile transceiver unit that may be used in accordance with the present invention;

FIG. 10 is a flow diagram illustrating a data recovery process according to one embodiment of the invention;

FIG. 11 is a flow diagram illustrating direct compare operations that may be implemented according to one embodiment of the present invention;

FIG. 12 is a flow diagram illustrating a majority voting process that may be performed according to one embodiment of a data recovery scheme of the present invention.

Detailed Description

In the following description, for purposes of explanation and not limitation, specific details are set forth such as particular circuits, interfaces, techniques, etc. in order to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. In other instances, detailed descriptions of well-known methods, devices, and circuits are omitted so as not to obscure the description of the present invention with unnecessary detail.

The present invention is illustrated by way of example only in the sense of a data communication system. The following embodiments illustrate the specific application of the present invention to a wireless communication environment, in which the present invention is not limited to wireless communication or any type of data communication. Other applications of the present invention may be any type of data processing system that must receive and/or access potentially corrupted data, including, for example, various data transferred from or to a storage device.

Thus, fig. 1 illustrates a data communications network in wired form, which includes a transmitter 12, such as a data processor 20, which transmits data packets over a network bus 16 to a data receiver 14, which receiver 14 may be another data processor or some other device, such as an external device. Both data processors 20 and 26 have their respective memories 22 and 28 and both data processors include respective transceivers 24 and 30 for exchanging packet information over the network bus 16. The data processor 20 and transceiver format the data according to the corresponding protocol for transmission over the network bus 16, including dividing the data into data units or data packets and adding/encoding error detection bits. The data processor 26 processes the data units received from the transceiver 30 in accordance with an algorithm stored in the memory 28 to detect whether each data unit was received correctly. In a particularly advantageous application of the invention, an automatic repeat request (ARQ) protocol is used between the sender and the receiver, such that when a data unit is correctly received by the receiver 14, the receiver 14 sends back an Acknowledgement (ACK) to the sender 12 via the network bus 16. If a data unit is correctly received and cannot be correctly reconstructed in accordance with the present invention, receiver 14 sends a negative acknowledgement to transmitter 12 via network 16, in response to which the transmitter retransmits the same data unit.

Now, with reference to fig. 2: the receiver data processor 26 uses data recovery techniques to correctly recover the data unit from the series of retransmitted versions of the data unit. Although the sequence of data units described below is meant to be retransmitted over a communication channel (wired or wireless), the sequence of data units may also result from multiple accesses of the same data unit from a data storage device. The number of retransmissions or accesses is of course a design parameter of any one system. A higher number of retransmissions or accesses may be specified in a more error prone system. Whereas a lower limit may be specified in a system or environment that is relatively error free.

In the data recovery process 40, a data unit is received and error checked (block 41). If the current data unit is received without errors (or if otherwise an acceptable bit error rate is used, e.g., digital sound can tolerate some bit errors), an Acknowledgement (ACK) is sent back from the receiver 14 to the transmitter 12 (block 47), and then the next received data unit is checked for errors (block 41). Otherwise it is determined whether this is the first transmission of a data unit (block 43). If so, the receiver 14 requests a retransmission of the data unit (block 44) and returns to receiving the retransmitted data unit and checking for errors (block 41).

If this is a retransmission of the data unit, a determination is made as to whether this data unit is an "alternate" data unit (block 48). As an example, alternate data units may correspond to "odd" transmissions of the same data unit, i.e., transmission 1, retransmission 3, retransmission 5, etc. On the other hand, alternating data units may correspond to "even" transmissions, i.e., retransmission 2, retransmission 4, retransmission 6, and so on. If the data unit is an alternate data unit, a first data unit reconstruction operation is performed (block 50). Otherwise a second type of data unit reconstruction operation is performed (block 51).

After the first or second data unit reconstruction operation is performed, a determination is made at block 54: whether the reconstructed data unit is valid, i.e. whether the reconstructed data unit has no bit errors or is below a predetermined bit error threshold. If so, control returns to block 47 where the receiver 14 sends an acknowledgement back to the transmitter 12. Otherwise, control returns to block 44 to request retransmission of the data unit.

The present invention can be applied to any data format as long as data is transmitted in units. For example, FIG. 3A shows one example of a format for a digital data message. The message may begin with a header, and the bits of the header may be assigned to any number of different functions, including the start of the data message, address information for the sender and/or receiver, the length of the message, and so forth. An example of such a header is a standard Internet Protocol (IP) header. The header is followed by a data packet, represented in fig. 3 as packet No. 1, packet No. 2, packet No. 3.

Each packet shown in fig. 3B includes both data and error detection bits. In other words, not all bits in each packet correspond to substantial information to be transmitted. It is clear that the term data packet is sometimes used in the present invention, but the present invention can be used for any data unit and is not necessarily limited to data packets.

Fig. 3C shows a specific example of the structure of one data packet. A predetermined number of data bits in a first portion of the data packet is followed by a second portion, namely a cyclic redundancy check bit (CRC). Cyclic redundancy checking only provides error detection-it is not used to correct errors. Well-known examples of CRC include CRC-CCITT and CRC-16. The present invention may also use forward error detection and correction bits, such as BCH parity bits. However, one of the advantages of the present invention is that forward error correction bits and encoding/decoding algorithms do not need to be used in data recovery.

One of the first and second data unit reconstruction operations may be a majority voting operation, as will be described herein in connection with the example illustration of FIG. 4. In the preferred embodiment, the majority voting technique is applied in alternating odd data packet transmissions. Thus, in the simple example shown in fig. 4, the majority voting operation is performed on three transmissions of a data packet. Each data packet may contain 32 data bits and 16 CRC bits in this non-limiting example. If two or three bits have the same value at a particular bit position, that bit position is assigned the value in the majority voted data packet. Two examples of the first 8-bit byte of three data packets show that at the 4 th bit position, a majority vote of 1, 1 and 0 results in a 1. In contrast, at the 7 th bit position, the bit values for majority voting are 0, 1 and 0, with the result that the 7 th bit position is assigned a value of 0. Although not illustrated, any portion of the bits of the data packet may be used to implement a majority voting operation. However, performing majority voting on the entire data packet including all 32 data bits and 16 CRC bits may yield more information.

The majority voted packet combines the accumulated bit information from the 1 st, 2 nd and 3 rd data packets into a single data packet. As shown in fig. 4, many of these bits are received correctly (all 0's and all 1's in a particular bit position). Even among those bit positions that have different bit values and for which a majority decision is required, the probability that a majority vote can yield a corresponding correct bit value is still quite high. After the majority voted packet is generated, a CRC operation is performed on the data packet to determine whether it is correct or within acceptable tolerances.

A particularly advantageous, but non-limiting, implementation of the present invention is a new bit accumulation performance used in the majority vote determination process. Memory savings and complexity reduction are achieved by generating and maintaining a bit accumulator for each bit position in a data packet rather than storing each received data packet in memory and then retrieving each of these stored data packets for use in a majority voting operation. Each bit of the received data packet is added to a corresponding bit accumulator. Thus, if there are 48 bits per data packet, the data packet will have 48-bit accumulators, each of which is 1 byte in size. A bit value of "1" will cause a "1" to be added to the bit accumulator for that bit position, while a bit value of "0" will not change the value of the corresponding bit accumulator. In this manner, a continuously summed sum of the total number of "1" per bit position in the data packet is maintained. The value of the sum in each bit accumulator is compared to the number of data packets received. The majority voted bit is set to "1" if the value of the sum of the bit accumulators exceeds a certain threshold, otherwise the majority voted bit is set to "0". The threshold may be specified as half the number of packets received.

Such a bit accumulator is particularly advantageous in environments where a large number of packet retransmissions may be required. For example, assuming that the total number of allowed packet retransmissions is 255, each bit accumulator can be specified as a single 8-bit (i.e., 1 byte) field. In other words, each byte is a separate packet accumulator. With this structure, a data packet having 16 data bytes and 2 CRC bytes requires 144 bit accumulators (i.e., 144 bytes) to correspond to up to 255 data packet retransmissions. This can provide significant RAM savings as compared to having each packet retransmission stored separately in RAM. If a packet is sent 255 times, storing each packet separately would require 255 x 18 bytes-4590 bytes of RAM. In the bit accumulator used in the present invention, only 144 bytes are needed, resulting in significant memory savings. Another configuration only allows the data packet to be retransmitted a total of 15 times and uses a 4-bit (nibble) bit accumulator area. This structure allows a single RAM byte to support 2bit accumulators.

In the case of an odd data packet reception, the bit value of each bit position of the received data packet is added to the corresponding bit accumulator to create a new majority voted data packet. This new majority voted data packet is then processed using the CRC algorithm. If it passes the CRC validation, the majority voted data packet is accepted and an acknowledgement is generated to the sender to indicate that the packet was received correctly. If the majority voted packet is still in error, a negative acknowledgement is sent back to the sender so that the packet can be retransmitted.

Although majority voting can be used for occasional packet reception, this technique is not as effective because there is a potential "tie", i.e., there may be two "1" s and two "0" s in a single bit position when 4 packets are received. In contrast, in the preferred embodiment of the invention, even data packets (with unacceptable errors in receipt) are compared directly to majority voted data packets calculated in the receipt of previous odd data packets. The data packet bit values of the even data packets are added to the data packet bit accumulator as described above. However, majority voting itself is not performed, so that the majority voted packet (for which direct comparison is made) remains the same as that calculated by the previous odd data packet reception.

An example of a direct comparison data cell reconstruction technique is shown in fig. 6. Direct comparison, for example, is performed using an exclusive-or operation (XOR), where the result is a binary "1" when the bits of the two compared data packets are different, and a "0" when the two bits are the same. As with majority voting, the direct comparison may be performed on a portion of the bits of the data packet, or more preferably, on all of the data bits of the packet. To achieve the latter, for example, all data bits and CRC bits of the received data packet are shown to be compared with all data and CRC bits of the majority voted data packet.

If the number of bit differences exceeds the threshold, care is taken to discard the packet and send a negative acknowledgement signal to the transmitter for reasons that will be explained below. However, if the packets differ by only a few bit positions, then these different bits are systematically set to all possible combinations, with the operation of the CRC algorithm being performed on each possible combination to verify the correctness of the data. In other words, if one of the different bit positions is currently set to "1", it is changed to "0", and the CRC algorithm is checked. If there are two bit positions that differ, 4 different possible bit combinations are tried. For three bit positions, 8 possible bit combinations are tried, and so on. Thus, the number of possible bit combinations is equal to 2bitdifs, where "bitdifs" is equal to the number of different bits. If any of these bit combinations produces a valid CRC check, the receiver produces an acknowledgement and accepts the corrected packet. If a valid packet cannot be recovered, a negative acknowledgement signal is sent.

The alternating process between the two data unit reconstruction techniques, i.e., even and odd packet reception, continues until the packet is either correctly acknowledged or a maximum number of repeated attempts has been reached. In the example of the structure using the 8-bit accumulator described above, the maximum allowed number of repeated attempts/retransmissions is 255.

There is a practical limit to the number of allowable bit differences when determining the threshold for the direct comparison technique. The first problem is the processing time involved in calculating the CRC over all possible combinations. This processing time must be limited to ensure that the receiver provides some sort of correct acknowledgement/negative acknowledgement signal to the transmitter within a predetermined amount of time (e.g., within a fraction of a second). This ACK/NAK transmit time window may exceed by much if the receiver spends too much time trying all possible bit combinations. A second problem is the problem of "counterfeiting" which is the problem of receiving a packet that is considered to be correct but not the one that the transmitter actually transmitted. If the number of bit differences between two packets is large, the probability of correcting a packet to an incorrect value but being able to pass CRC validation increases. Thus, the cost of accepting more bit differences in the direct comparison technique is longer data processing time, increased power consumption, and higher probability of "counterfeiting".

One obvious characteristic of the invention is that: discarding those erroneous or uncorrectable packets does not result in the loss of important information in those erroneous data packets. Instead, the present invention utilizes both majority voting and direct-comparison error-correction techniques to retain and utilize this important information.

For example, consider an environment with a Bit Error Rate (BER) of two percent, where a data packet contains 4 bytes of data and 2 bytes of CRC code bits, for a total of 48 bits. In such an environment, the probability that a data packet will contain one or more errors in each transmission is high (62%), and without the present invention, the probability that any transmission of a data packet will be received without errors can be determined according to the following equation:

P_{good packet}＝(P_{correct bit})^{number of bits}(1) thus, the probability of receiving any packet with one or more bit errors may be determined by:

P_{error packet}＝1-(P_{correct bit})^{number of bits}(2) in this 2% bit error rate environment, the probability of correct reception of a single bit is 98% (i.e., P)_{correct bit}98%). However, if the total number of data bits in a packet increases from 4 bytes to 16 bytes (144 bits total), the probability of containing an error in the packet becomes very high (94.5%). Thus, current techniques that simply drop packets with errors and expect the next transmission to result in a transmission without errors are impractical and inefficient. Without the aid of the data recovery/reconstruction technique of the present invention, the probability of successfully receiving an acceptable data packet in two data transmissions is given by:

P_success＝P_{good packet}+(P_{error packet})(_{Pgood packet}) (3) for a 48-bit packet, the probability of successfully receiving the packet in two attempts is 61.8% in a 2% bit error environment, which is not particularly encouraging even for such a relatively low bit error rate environment.

However, by appending direct comparisons to even-coded transmissions and majority voting to odd-numbered transmissions, the probability of correctly receiving multiple transmitted data packets is significantly improved in accordance with the preferred embodiment of the present invention. For each of these two error correction techniques, the following probability calculations help to quantify this improvement.

For the direct comparison technique, assuming that only a 2-bit difference is allowed between different packets, the probability of successfully decoding a packet transmitted only twice can be determined as follows:

where P is_{1-bit pkt error}＝48(1-P_{correct bit})(P_{correct bit})^{num of bits-1} (5)

And P_{1-bit pkt error(not same as previous pkt)}

＝47(1-P_{cooect bit})(P_{cooect bit})^{num of bits-1}(6) When the direct comparison technique is incorporated, the probability of correctly receiving a data packet increases from about 62% to 67%. This increase is modest because the received packet and the majority voted packet in this case are allowed to differ by only 2 bits. In other words, each of the two packets allows only one bit in error and a single bit error in both packets cannot yet be co-located. However, if the number of allowed bit differences is increased to include three or four bit differences, the probability of successful reception will increase significantly.

Adding the above majority vote to the data recovery process improves the error correction probability for packets that have been sent 3 times. Using the above formula for the probability of correctly receiving a packet sent once, the probability of receiving a packet sent three times without majority voting can be obtained as follows:

P_success＝P_{good pkt}+(P_{error pkt})(P_{good pkt})+(P_{error pkt})²(P_{good pkt}) (7)

in a 2% bit error rate environment, P is the bit error rate for a 48-bit data packet_success74.8%. If majority voting is included, the probability of correctly receiving a packet sent in triplicate is as follows:

P_success＝P_{good pkt}+(P_{error pkt})(P_{good pkt})

+(P_{error pkt})²(P_{good pkt})+(P_{error pkt})³

(P_{good majority vote}) (8)

wherein P is_{good majority vote}

＝[3(P_{correct bit})²(1-P_{correct bit})+(P_{correct bit})³]^{num of bits}(9) The probability of correctly receiving a packet when using majority voting is 98.7%.

If both direct comparison and majority voting techniques are added at the same time, the probability of correctly decoding a 48-bit packet received by sending only three times in a 2% bit error rate environment is nearly 100%. It is clear that this increase in the probability of correctly recovering the data packet is obtained without appending further forward error correction bits to the data packet. Instead, the present invention will train the receiver so that it more "smartly" applies the valuable information in previously received data packets to correct the currently received data packet. Furthermore, the direct comparison and majority voting technique requires only minimal time, computation, and memory resources. The invention enables to recover transmitted data packets closer and closer to correctly with each new reception, even in particularly noisy environments and thus requiring more than three transmissions.

One potential use of the present invention is in the field of wireless communications where data processing is limited, memory space is conserved, and the communication environment is generally harsh (higher bit error rates). An example of a communication system is the trunked wireless relay system 100 shown in figure 7. The trunk wireless trunking system 100 is a "multi-site" system in which the site controller S1 receives a call from a mobile wireless device and coverage area a1 requesting a channel to communicate with a particular callee or group of callees. The caller requests the channel by pressing the "push-to-talk" (PTT) button on his portable/mobile radio transceiver. This operation tells the site controller, via inbound digital control messages that are propagated on the designated radio frequency control channel: an audio operating channel is required. The site controller S1 assigns an operating channel to the caller and instructs the caller' S wireless unit to switch from the control channel to the assigned operating channel. This designated operating channel supports communications within the area covered by the site.

In addition, the site control may send a control message to the multi-site switch 104 that includes the designated operating channel. The exchange then sends a channel request to the other site controller and routes the audio signal to establish a path for the audio signal between the radio site repeater serving the caller and the radio site repeater serving the callee. In addition, other audio signal paths may be established in a similar manner so that one or more dispatch consoles 106 and users of landline telephones (via central telephone interconnect switch 108) can be included in the communication. Upon receipt of the channel request message, each of these secondary site controllers may assign a radio frequency operating channel to the call (e.g., if the callee specified by the caller's channel request message happens to be physically located within the coverage area serviced by the corresponding radio frequency transceiver site). At the same time, the multi-switch 200 ensures that the caller' S audio signal has been routed from the active radio frequency receiver of site S1 to the active transmitters of the remaining sites participating in the call. More details are provided, for example, in U.S. patent 5,200,954.

Data communication may be implemented over a data network using portable/mobile wireless units. For example, fig. 8 illustrates two different types of networks, including an ethernet network 110 and a wireless data network 112. Ethernet 110 and wireless network 112 operate in an "internet-mode" using a gateway 114 and data interface module 126. Data gateway 114 provides an interface for translating messages between two networks. The data gateway is connected to host computers 116, 118 and 120 on ethernet coax 114 using, for example, a standard protocol such as TCP/IP. In the rf data network 112, a data interface module 126 is connected to a plurality of stations 122 and 124, which communicate with one or more wireless units 128 and 130 via an rf communication channel. Wireless data terminals 132 and 134 (e.g., laptop computers) may be connected to the wireless devices 128 and 130, respectively, for data communication.

To effect communication from the wireless data terminal 132 to host computer a, the wireless device 128 informs the station 122 via the radio frequency control channel that it has a message and requests a radio frequency operating channel. Station 122 designates an available radio frequency operating channel and notifies wireless device 128. Site 122 then routes a call to data interface module 126, which forwards the dispatch to data gateway 114 to establish a data path between the data gateway and the rf operating channel. Wireless device 128 separates the message into packets and sends the packets to station 122 over the radio frequency operating channel. Station 122 forwards the data packet in its received form to data gateway 114 via data interface module 126. After the data gateway 114 receives the burst of message packets, it checks and ascertains whether they were received correctly and sends one or more acknowledgement signals back to the wireless device over the radio frequency operating channel. If the data packet is not received correctly, a negative acknowledgement signal is sent to the wireless device, which then retransmits another burst containing the packet that was not received correctly by the data gateway. This process continues until the data gateway 114 receives the entire message or the wireless device exhausts its retransmission attempts. If the data gateway 114 successfully receives the data message, the data gateway 114 sends the message to the host computer 116 via the bus 114.

The general architecture of a suitable mobile portable radio unit for use in the present invention is microprocessor based, as shown in fig. 9. Microprocessor 150 is provided with suitable memory 152 and input/output (I/O) circuitry 154 to interface with the wireless device display, keypad, push-to-talk (PTT) switch, and audio circuitry 168, which provides audio output to a speaker and receives analog audio input from a microphone. A modem 156 serves as a digital interface to voice encryption, vehicle location, multi-site switching stations, and other types of digital communication subsystems, including wireless data terminal 132. In some cases it is desirable that error detection algorithms like CRC checking are implemented in hardware rather than in software. If this is the case, the modem 156 may include hardware circuitry in addition to the modulation/demodulation functions to implement error detection and/or correction functions. The I/O circuitry 154 also allows for appropriate programming by the microprocessor 150 of the rf receiver 162 and transmitter 160, which, through a conventional signal combiner 164, allows duplex communication over a common antenna 166, as will be understood by those skilled in the art. The wireless data terminal 132 communicates through an RS-232 cable 158 connected to a modem 156.

The method of implementing the invention in a wireless communication network such as that described above will be described in further detail below. Specifically, the data recovery process implemented by the wireless receiver, which receives data packets transmitted via the wireless channel, will be described herein with reference to the flowchart shown in fig. 10. Initially, the packet count variable PACKETCNT is set equal to zero (block 180). A data packet is then received (block 182) and the packet count variable is incremented by 1 (block 184). Assuming the data packet has a format similar to that shown in fig. 4-6, a CRC check is performed on the received packet to detect any errors (block 186). If the CRC check confirms that the data packet was received correctly (block 188), the receiver sends an acknowledgement signal over the wireless communication channel (block 202) and control returns to block 182 to receive the next data packet. Otherwise, the bit value of the received data packet is appended to the corresponding bit accumulator reserved for this data packet (block 190). A determination is made in block 192: whether the current packet count is odd, i.e., whether this is an even or odd number of retransmissions of this data packet. If there are an odd number of transmissions, then the majority vote data unit recovery algorithm, which is illustrated in more detail in FIG. 11, is implemented (block 194). If this is an even number of transmissions, then a direct compare data recovery process is implemented as shown in FIG. 12 (block 196). After performing either of the data recovery operations shown in fig. 11 and 12, control returns to block 198 to determine whether the packet has been successfully decoded using the CRC check. If not, a retry is requested in block 200, with control returning to block 182 to receive the retransmitted packet. Otherwise the reconstructed data packet is acceptable and an acknowledgement signal is sent (block 202) while the next substantive data packet is processed in block 204.

The direct comparison algorithm (block 210) is now described in conjunction with the flowchart shown in FIG. 11. The majority of data packets calculated for the odd-numbered transmission of data packets immediately prior to the currently received even-numbered transmission of data packets are xored with the currently received even-numbered data packets in a similar manner as shown in fig. 6 (block 212). The sum of the mutually different numbers of bits as a result of the exclusive-or comparison (i.e., the sum of the numbers of bit positions having an exclusive-or output of "1") is assigned to the variable DITDIF (block 214). A determination is then made (block 216) to see if the variable BITDIF is less than or equal to a predefined threshold. As mentioned before, the threshold is a compromise between the time/resources of data processing required to improve data recovery performance and to calculate the CRC in terms of the number of bit combinations suggested as a result of this bit disparity. If the number of differing bits exceeds the threshold, the success flag is set to false (block 218). Control returns to fig. 10 where a retry request is made to cause the data packet to be retransmitted. Otherwise, a list of possible trial data packets is generated using different bit combinations (block 220). One of those possible trial data packets is selected (block 222) and a CRC check calculation is performed (block 224). If the CRC check is satisfactory (block 226), then the success flag is set to true (block 232) and control returns to FIG. 10 where an acknowledgement signal is sent. Otherwise, a determination is made at block 228 to see if all possible combinations of trial data packets have been analyzed. If not, control passes back to block 222 to select a possible trial data packet that has not yet been analyzed. Otherwise, all possible attempted data packets produce unacceptable results. The success flag is set to false (block 230) and control returns to fig. 10 to send a negative acknowledgement signal to cause the data packet to be retransmitted.

The majority voting algorithm (block 250) will now be described in conjunction with the flow chart shown in FIG. 12. In block 252, a variable total is set, which corresponds to the total number of bits in the data packet. The total number of bits is set to 48, according to a non-limiting example used in the present invention. The bit accumulator is initialized as a variable BITNUM that "points" to one of the bit positions in the data packet. A threshold variable T is specified in block 254. One example method of calculating the threshold is to divide the packet count by 2 and truncate the ("TRUNC") remainder.

A determination is made in block 256: whether the sum of the bits in the bit accumulator for the current bit position being pointed to exceeds the threshold T (block 256). If so, the bit value for this number of bits in most data packets is set to 1 (block 258). If there is an override, then the bit value for this bit position in most data packets is set to 0 (block 260). Then at block 262, the variable BITNUM is incremented by 1 to point to the next bit position/bit accumulator. A determination is made in block 264: whether the new bit position (BITNUM) is less than the total number of bits in the data packet. If so, the process of blocks 256-264 is repeated. Otherwise, the majority voting operation on this data packet is completed and a CRC check is performed in block 266. If the result of the CRC check is good (block 268), then the success flag is set equal to true (block 272); otherwise the success flag is set to false (block 270). Control then returns to fig. 10 to either send an acknowledgement (block 202) or request a retry (block 200).

The present invention thus utilizes information from previously received data packets to recover data that reconstructs the data packets with an ever increasing probability of reconstructing the actually transmitted data packets given a bit error rate of less than 50%. With each new reception, the accumulated information makes the receiver more likely to acquire the actually transmitted data packet. This utilization of information that might otherwise be discarded makes highly efficient and practical bit error correction particularly useful for transceivers having limited data processing and/or memory resources in harsh communication environments.

While the present invention has been described with reference to particular embodiments thereof, the scope of the invention and its applications and features may be extended to other embodiments and limited only by the following claims.

Claims (19)

1. A method of data processing, comprising:

receiving an erroneous version of a sequence of data packets, the sequence comprising a first version and one or more retransmitted versions;

reconstructing the data packet using the sequence, comprising:

-determining (48) whether the currently received version with errors is an odd or even number of said sequences;

-performing a first data packet reconstruction operation (50) or a second data packet reconstruction operation (52) depending on the result of the determining step (48);

-wherein said first data packet reconstruction operation (50) comprises performing a majority voting operation on a version of said sequence to produce a majority voted data packet which is the reconstructed data packet of the first data packet reconstruction operation (50);

-wherein the second data packet reconstruction operation (52) comprises: comparing the majority voted data packet of the previously performed first data packet reconstruction operation with said currently received version, identifying one or more positions having different bit values, and changing one or more of the bit values, the data packet having one or more changed bit positions being the reconstructed data packet of the second data packet reconstruction operation (52);

-checking (54) the reconstructed data packet for errors; and

-sending (47) an acknowledgement signal if the reconstructed data packet is found acceptable in said checking step (54).

2. The method of claim 1, wherein the second data packet reconstruction operation comprises performing an exclusive-or operation on the majority voted data packet of the previously performed first data packet reconstruction operation and the currently received version.

3. The method of claim 1 or 2, wherein the second data packet reconstruction operation comprises comparing the number of different bit values with a first threshold value and performing the changing step when the number of different bit values is less than the first threshold value.

4. The method of claim 1 or 2, wherein the second data packet reconstruction operation (52) further comprises: it is determined whether the reconstructed data packet of the second data packet reconstruction operation (52) is acceptable and, if not, a different one of the different bit values is changed.

5. The method of claim 1, wherein the data packet includes data bits and error detection bits, and wherein the step of verifying (54) includes performing a calculation of a cyclic redundancy code on the reconstructed data packet.

6. The method of claim 4, further comprising: if an unacceptable error is detected at the checking step (54), retransmission of the data packet is requested.

7. The method of claim 1, wherein the majority voting operation further comprises comparing the number of non-matching bits to a second threshold.

8. The method of claim 1, wherein the majority voting operation comprises maintaining a bit accumulator for each respective bit position in the data packet such that each bit accumulator sums the bit values in the respective bit positions from each version of the data packet.

9. The method of claim 8, wherein the majority voted data packet is determined according to the following steps:

accumulating for each respective bit position in the data packet a sum of bit values from the respective bit position of each version in the sequence;

determining a second threshold based on the number of versions in the sequence;

comparing each accumulated sum to the second threshold;

setting the bit value of the corresponding bit position of the majority voted data packet to 0 if the accumulated sum is less than or equal to the second threshold; and

if the accumulated sum is greater than the second threshold, the bit value of the corresponding bit position of the majority voted data packet is set to 1.

10. The method of claim 9, wherein the second threshold determining step comprises:

the number of data packets in the sequence is divided by 2 and the resulting quotient is truncated.

11. The method of claim 9, said steps being performed for each bit position in the reconstructed data packet.

12. The method of claim 9, said steps being performed only for a portion of the bit positions in the reconstructed data packet.

13. The method of claim 1, wherein the data packet includes data bits and error detection bits and does not include error correction bits.

14. The method of one of claims 1, 2, 5, 7-13, wherein said first digital unit reconstruction operation (50) is performed if said currently received erroneous version is an odd number of said sequences, and said second data packet reconstruction operation (52) is performed if said currently received erroneous version is an even number of said sequences.

15. A receiver for use in a data communication system in which a transmitter is arranged to transmit a data packet a plurality of times over a data communication link to produce a sequence of erroneous versions of said data packet, said receiver comprising a data processor and a transceiver coupled to the data communication link for receiving the sequence, wherein the data processor is arranged to reconstruct said data packet using apparatus comprising:

-means for determining whether a currently received version with errors is an odd or even number of said sequences;

-means for performing either a first data packet reconstruction operation or a second data packet reconstruction operation in dependence upon the determination made by said determining means, wherein said first data packet reconstruction operation comprises performing a majority voting operation on the version of said sequence to produce a majority voted data packet that is the reconstructed data packet of the first data packet reconstruction operation, and wherein the second data packet reconstruction comprises: comparing a majority voted data packet of a previously performed first data packet reconstruction operation with said currently received version, identifying one or more positions having different bit values, and changing one or more of the bit values, the data packet having the one or more changed bit values being a reconstructed data packet of a second data packet reconstruction operation;

-means for checking the reconstructed data packet for errors; and

-means for sending an acknowledgement signal when the reconstructed data packet is found to be acceptable in said checking.

16. The receiver of claim 15, wherein the receiver is a portable radio unit and the data communication link is a wireless radio frequency channel.

17. The receiver of claim 15 wherein the data processor is arranged to maintain a bit accumulator for one or more bit positions in the reconstructed data packet of the first data reconstruction operation to store a sum of the bit values for the corresponding bit position from each of the versions in the sequence.

18. The receiver of claim 17, wherein the data processor is arranged to determine a threshold based on the number of versions, to compare each cumulative sum value with the threshold, and to set the bit value of the corresponding bit position of the majority voted data packet to 0 if the cumulative sum value is less than or equal to the threshold, and to set the bit value of the corresponding bit position of the majority voted data packet to 1 if the cumulative sum value is greater than the threshold.

19. The receiver of claim 15, wherein the processor is arranged to change one or more of the different bit values to produce a new reconstructed data packet of the second data packet reconstruction operation if the reconstructed data packet of the second data packet reconstruction operation is not acceptable.