Range Extension and Noise Mitigation For Wireless Communication Links Utilizing a CRC Based Single and Multiple Bit Error Correction Mechanism

• US 20080288845A1
• Filed: 05/12/2008
• Published: 11/20/2008
• Est. Priority Date: 05/15/2007
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Sherman, Itay, Lerner, Gregory, Tsfati, Yossi, Dekel, Eli
• Granted Patent: US 8,255,754 B2
• Time in Patent Office: Days
• US Class Current: 714/748
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/6306 Error control coding in combination with Automatic Repeat reQuest [ARQ] and diversity transmission, e.g. coding schemes for the multiple transmission of the same information or the transmission of incremental redundancy H03M13/3761, H03M13/3769 and H03M13/635 take precedence
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0061 Error detection codes
• CPC Class Codes: H04L 1/1845 Combining techniques, e.g. code combining

Abstract

A novel and useful range extension and in-band noise mitigation mechanism that uses conventional CRC error detection codes to correct single and multiple bit errors in packets received over a communications link. The CRC error correction mechanism of the invention is particularly suitable for use with communication protocols with weak error correction capabilities. The mechanism uses the linearity property of the CRC calculation to detect the existence of errors in the received packet. The entire received packet is searched for single bit errors and are corrected in a single cycle. If no single bit errors are found, the mechanism then searches for multiple bit errors. Packet retransmissions are used to detect and mark the location of multiple bit errors. Multiple bit errors are corrected by trying a plurality of hypotheses of single bit error corrections. Each hypotheses pattern is investigated to find matching CRC patterns for correction using the single bit, single cycle CRC error correction method.

Claims

1. A method of extending the range of a wireless communications link, said method comprising the step of:

using a packet cyclic redundancy check (CRC) error detection code as an error correction code to correct one or more bit errors in a received packet.

2. The method according to claim 1, wherein said error correction code corrects single bit errors in a received packet.

3. The method according to claim 1, further comprising the step of using one or more packet retransmissions to further improve probability of reception.

4. The method according to claim 1, further comprising the step of using one or more packet retransmissions to correct multiple bit errors in a received packet.

5. A method of correcting single bit errors in a received packet, said method comprising the steps of:

calculating a cyclic redundancy check (CRC) code for said received packet;

XORing a received CRC code with said calculated CRC code to yield an XOR result therefrom;

determining a bit error location in accordance with said XOR result; and

flipping the value of the bit at said bit error location in said received packet thereby correcting said single bit error.

6. The method according to claim 5, wherein said step of determining comprises searching a table of pre-computed single bit error CRC correction values for an entry matching said XOR result, wherein said bit error location corresponds to the bit location corresponding to said matching entry.

7. The method according to claim 5, wherein said plurality of single bit error CRC correction values are pre-computed for all possible single bit error locations.

8. The method according to claim 5, wherein said single bit error is corrected in a single CRC cycle.

9. A method of correcting single bit errors in a received packet, said method comprising the steps of:

calculating a cyclic redundancy check (CRC) code for said received packet;

XORing said calculated CRC code with a plurality of single bit error CRC correction values to generate a plurality of XOR results therefrom, wherein each CRC correction value corresponds to a single bit packet error;

searching for a match between each XOR result and a received CRC code; and

if a match is found, flipping the value of the bit at a bit location in said received packet corresponding to the bit number of the matching XOR result thereby correcting said single bit error.

10. The method according to claim 9, wherein said plurality of single bit error CRC correction values are pre-computed for all possible single bit error locations.

11. The method according to claim 9, wherein said single bit error is corrected in a single CRC cycle.

12. A method of correcting one or more bit errors in a received packet, said method comprising the steps of:

calculating a cyclic redundancy check (CRC) code for an initial received packet;

utilizing a retransmitted packet to detect the presence of one or more bit errors;

generating a plurality of hypotheses to check, each hypothesis represented by a CRC value;

XORing said calculated CRC code with the CRC value associated with each hypothesis to generate a plurality of XOR results therefrom;

searching for a match between said plurality of XOR results and a received CRC code; and

if a match is found, flipping the value of the bit at one or more bit locations in said initial received packet corresponding to one or more bit numbers of a matching XOR result thereby correcting said one or more bit errors.

13. The method according to claim 12, wherein each hypothesis is calculated a plurality of single bit error CRC correction values pre-computed for all possible single bit error locations.

14. The method according to claim 12, wherein said one or more bit errors are corrected in a single CRC cycle.

15. A method of correcting multiple bit errors in a received packet, said method comprising the steps of:

calculating a cyclic redundancy check (CRC) code for an initial received packet;

utilizing a retransmitted packet to detect the presence of multiple bit errors;

generating a plurality of hypotheses to check, each hypothesis represented by a CRC value;

for each bit position in said received packet, XORing the CRC value of each hypothesis with both a single bit error CRC correction value associated with a particular bit position and said calculated CRC code to generate XOR results therefrom;

searching for a match between said plurality of XOR results and a received CRC code for each bit position in said received packet; and

if a match is found, flipping the value of the bit at the bit location in said initial received packet corresponding to the location of the matching tested bit and the value of one or more bits corresponding to the matching hypothesis thereby correcting said multiple bit errors.

16. The method according to claim 15, wherein each hypothesis is calculated a plurality of single bit error CRC correction values pre-computed for all possible single bit error locations.

17. The method according to claim 15, wherein said multiple bit errors are corrected in a single CRC cycle.

18. The method according to claim 15, wherein said search is halted once an XOR result associated with a hypothesis is found that matches said received CRC code.

19. A software program product embodied in a computer-readable medium, comprising program instructions executable to implement:

a range extension and noise mitigation mechanism operative to use a packet cyclic redundancy check (CRC) error detection code as an error correction code to correct one or more bit errors in a received packet.

20. The software program product according to claim 19, wherein said mechanism comprises the steps of:

calculating a cyclic redundancy check (CRC) code for said received packet;

XORing a received CRC code with said calculated CRC code to yield an XOR result therefrom;

determining a bit error location in accordance with said XOR result; and

flipping the value of the bit at said bit error location in said received packet thereby correcting a single bit error.

21. The software program product according to claim 19, wherein said mechanism comprises the steps of:

calculating a cyclic redundancy check (CRC) code for said received packet;

XORing said calculated CRC code with a plurality of single bit error CRC correction values to generate a plurality of XOR results therefrom, wherein each CRC correction value corresponds to a single bit packet error;

searching for a match between each XOR result and a received CRC code; and

if a match is found, flipping the value of the bit at a bit location in said received packet corresponding to the bit number of the matching XOR result thereby correcting said single bit error.

22. A single chip radio controller, comprising:

a radio for establishing a link to a remote device; and

a range extension and noise mitigation mechanism operative to use a packet cyclic redundancy check (CRC) error detection code as an error correction code to correct one or more bit errors in a received packet

23. The radio according to claim 22, wherein said error correction code corrects single bit errors in a received packet.

24. The method according to claim 22, further comprising the step of using one or more packet retransmissions to further improve probability of reception.

25. The method according to claim 22, further comprising the step of using one or more packet retransmissions to correct multiple bit errors in a received packet.