Method and apparatus for using fire decoder to correct burst errors in a real-time communications system

• US 6,754,871 B1
• Filed: 07/31/2001
• Issued: 06/22/2004
• Est. Priority Date: 07/31/2001
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Huang, Wenfeng, Sayers, Ian, Pines, Howard, Kaiser, Daryl
• Primary Examiner(s): Chung, Phung M.
• Application Number:
  US09/919,761
• Time in Patent Office: 1,057 Days
• Field of Search: 714/762, 714/746, 714/758, 714/781, 714/785, 714/761
• US Class Current: 714/762
• CPC Class Codes: H03M 13/175 Error trapping or Fire codes
• CPC Class Codes: H03M 13/618 Shortening and extension of codes
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

Error bursts are detected and corrected in a communication system using shortened cyclic codes, such as shortened Fire codes. Data is loaded into a first error syndrome register and a second error syndrome register. The data in the registers may be evaluated to determine if the data bits contain a correctable error. Shortened zero bits are shifted into the second error syndrome register. A number of zero bits are shifted into the first error syndrome register to trap an error burst pattern in the data. A determination is made as to the number of zero bits shifted into the second error syndrome register to trap the location of the error burst in the data. Using the number of zero bits shifted into the second error syndrome register and the error burst pattern, the error in the data is located and corrected.

Claims

1. A method for correcting error bursts in a communication system using a shortened cyclic code, comprising:

loading data and parity bits into a first error syndrome register and a second error syndrome register;

shifting shortened zero bits into the second error syndrome register;

shifting a first set of zero bits into the first error syndrome register, until a predefined number of stages in the first error syndrome register contain a predefined data pattern, to trap an error burst having a burst pattern in a given subset of the stages composing the first error syndrome register;

(i) shifting a second set of zero bits into the second error syndrome register and (ii) comparing the burst pattern in the given subset of stages of the first error syndrome register and the data pattern in a corresponding subset of stages in the second error syndrome register until a match of the burst pattern is found; and

based on (i) the number of zeros shifted into the second error syndrome register and (ii) the error burst pattern, locating and correcting the error burst pattern in the data.

2. The method as claimed in claim 1, wherein the shortened cyclic code is a shortened Fire code.

3. The method as claimed in claim 1, wherein the first error syndrome register is an error pattern register and the second error syndrome register is an error location register.

4. The method as claimed in claim 1, wherein the error burst is a single error burst b(k) of a length t or shorter, the cyclic code having a generator polynomial of type G(x)=(x^2t−

1+1) p(x), wherein p(x) is a prime polynomial over GF(2) with period r₀, satisfying r₀>

(n−

b), when n equals a length of a binary code and b equals a number of shortened bits.

5. The method as claimed in claim 1, wherein the shortened number of zero bits is equal to (r₀−

N+1), where r₀ is the period of the second factor of the shortened cyclic code on which the second error syndrome register is based, and N is the length of the shortened cyclic code.

6. The method as claimed in claim 1, wherein trapping the error burst uses no more than (2t−

2) shifts.

7. The method as claimed in claim 1, wherein trapping the error burst location uses no more than (N+c) shift and compare operations.

8. The method as claimed in claim 1, executed in a signal processor.

9. The method as claimed in claim 8, wherein shifting the zero bits exploits the architecture of the signal processor.

10. The method as claimed in claim 9, wherein a shift operation is executed in a single signal processor instruction cycle.

11. The method as claimed in claim 1, used in a TDMA-based GSM system.

12. The method as claimed in claim 11, executed in a signal processor, wherein the signal processor resources available during inactive time slots are utilized in a background mode to process the shifting-in of the shortened zero bits.

13. The method as claimed in claim 12, wherein processing by the signal processor is distributed over a variable number of inactive radio channel time slots in order to provide enough signal processor resources to correct a frame of data while minimizing frame buffering delays.

14. The method as claimed in claim 1, wherein the error bursts are detected and corrected in real-time.

15. An error trapping decoder for correcting error bursts in a communication system using shortened cyclic codes, comprising:

a first error syndrome shift register, having a structure based on a first factor of a given cyclic code of a given cyclic code family, and a second error syndrome shift register, having a structure based on a second factor of the given cyclic code, the shift registers shifting-in an input binary signal having associated parity check bits generated by a shortened binary cyclic block code belonging to the given cyclic code family;

a first comparator and a second comparator, coupled to the first and second error syndrome shift registers, receiving data bits stored in a predefined number of low-order and high-order stages of the shift registers, respectively;

a buffer receiving the input binary signal;

a correction module coupled to said comparators and said buffer;

said second error syndrome shift register shifting in a shortened number of zero bits after the shift registers have shifted-in the input binary signal;

said second comparator determining the number of shifts needed to trap the error burst by monitoring how many zero bits are shifted into said first error syndrome shift register before the data bits in the high-order stages of the shift register have a predetermined pattern indicating the error burst;

said first comparator determining the number of shifts needed to trap the error burst location, after the shortened number of zero bits are shifted-in, by monitoring how many zero bits are shifted into said second error syndrome shift register before the data bits in the low-order stages of the shift register have a predetermined pattern corresponding to the error burst; and

said correction module, using the shift information determined by said first comparator, locating and correcting the error burst in the input binary signal in the buffer.

16. The decoder as claimed in claim 15, wherein the shortened cyclic code is a shortened Fire code.

17. The decoder as claimed in claim 15, wherein said first error syndrome register is an error pattern register and said second error syndrome register is an error location register.

18. The decoder as claimed in claim 15, wherein the error burst is a single burst b(x) of a length t or shorter, the cyclic code having generator polynomial of type G(x)=(x^2t−

1+1) p(x), wherein p(x) is a prime polynomial over GF(2) with period r₀, satisfying r₀>

(n−

b), where n equals a length of a binary code and b equals a number shortened bits.

19. The decoder as claimed in claim 15, wherein the shortened number of zero bits is equal to (r₀−

N+1) where r₀ is the period of the second factor of the given shortened cyclic code on which the second error syndrome register is based, and N is the length of the shortened cyclic code.

20. The decoder as claimed in claim 15, wherein the number of shifts executed to trap the error burst is no more than (2t−

2) shifts.

21. The decoder as claimed in claim 15, wherein the number of shifts and compare operations executed to trap the error burst location in the input binary signal is no more than (N+c) shift and compare operations.

22. The decoder as claimed in claim 15, executed in a signal processor.

23. The decoder as claimed in claim 22, wherein said second error syndrome shift register shifts the shortened zero bits in a manner exploiting the architecture of the signal processor.

24. The decoder as claimed in claim 23, wherein a shift operation is executed in a single signal processor instruction cycle.

25. The decoder as claimed in claim 15, used in a TDMA-based GSM system.

26. The decoder as claimed in claim 25, executed in a signal processor, wherein signal processor resources available during inactive time slots are utilized in a background mode to process the shifting-in of the shortened number of zero bits.

27. The decoder as claimed in claim 26, wherein processing is distributed over a variable number of inactive radio channel time slots in order to provide enough signal processor resources to correct a frame of data while minimizing frame buffering delays.

28. The decoder as claimed in claim 15, wherein error bursts are detected and corrected in real-time.

29. An apparatus for correcting an error burst in a communication system using shortened cyclic codes, comprising:

means for loading data into a first error syndrome register and a second error syndrome register;

means for shifting shortened zero bits into the second error syndrome register;

means for shifting a first number of zero bits into the first error syndrome register to trap an error burst pattern associated with an error burst in the data;

means for determining a second number of zero bit shifts into the second error syndrome register to trap the error burst location in the data; and

means for locating and correcting the error burst in the data by using the second number of zero bit shifts and the error burst pattern.

30. The apparatus as claimed in claim 29, wherein the shortened cyclic code is a shortened Fire code.

31. The apparatus as claimed in claim 29, wherein the first error syndrome register is an error pattern register and the second error syndrome register is an error location register.

32. The apparatus as claimed in claim 29, wherein the number of shortened zero bits shifted into the second error syndrome register is equal to (r₀−

N+1) where r₀ is the period of the factor of a shortened cyclic code on which the second error syndrome register is based.

33. The apparatus as claimed in claim 29, wherein trapping the error burst pattern uses no more than (2t−

2) shifts.

34. The apparatus as claimed in claim 29, wherein trapping the error burst location uses no more than (N+c) shift and compare operations.

35. The apparatus as claimed in claim 29, executed in a signal processor.

36. The apparatus as claimed in claim 35, wherein said means for shifting exploits the architecture of the signal processor.

37. The apparatus as claimed in claim 36, wherein a shift operation is executed in a single signal processor instruction cycle.

38. The apparatus as claimed in claim 29, used in a TDMA-based GSM system.

39. The apparatus as claimed in claim 38, executed in a signal processor, wherein the signal processor resources available during inactive time slots are utilized in a background mode to process the shifting in of the shortened zero bits.

40. The apparatus as claimed in claim 39, wherein processing is distributed over a variable number of inactive radio channel time slots in order to provide enough signal processor resources to correct a frame of data while minimizing frame-buffering delays.

41. The apparatus as claimed in claim 29, wherein the error bursts are detected and corrected in real-time.

42. A computer-readable medium having stored thereon sequences of instructions, the sequences of instructions including instructions, when executed by a digital processor, causes the processor to perform:

loading data coded with a shortened cyclic code into a first error syndrome register and a second error syndrome register;

shifting shortened zero bits into the second error syndrome register;

shifting a first number of zero bits into the first error syndrome register to trap an error burst pattern in the data;

determining a second number of zero bit shifts into the second error syndrome register to trap an error burst location of the error burst pattern in the data; and

locating and correcting the error burst pattern in the data by using the second number of zero bit shifts and the error burst pattern.

43. The computer-readable medium as claimed in claim 42, wherein the shortened cyclic code is a shortened Fire code.

44. The computer-readable medium as claimed in claim 42, wherein the first error syndrome register is an error pattern register and the second error syndrome register is an error location register.

45. The computer-readable medium as claimed in claim 42, wherein the number of shortened zero bits are equal to (r₀−

N+1), where r₀ is the period of the second factor of the shortened cyclic code on which the second error syndrome register is based.

46. The computer-readable medium as claimed in claim 42, wherein trapping the error burst pattern uses no more than (2t−

2) shifts.

47. The computer-readable medium as claimed in claim 42, wherein trapping the error burst location uses no more than (N+c) shift and compare operations.

48. The computer-readable medium as claimed in claim 42, wherein the digital processor is a digital signal processor.

49. The computer-readable medium as claimed in claim 48, wherein shifting the zero bits exploits the architecture of the digital signal processor.

50. The computer-readable medium as claimed in claim 49, wherein a shift operation is executed in a single digital signal processor instruction cycle.

51. The computer-readable medium as claimed in claim 42, used in a TDMA-based GSM system.

52. The computer-readable medium as claimed in claim 51, executed in a digital signal processor, wherein the digital processor resources available during inactive time slots are utilized in a background mode to process the shifting-in of the shortened zero bits.

53. The computer-readable medium as claimed in claim 52, wherein processing is distributed over a variable number of inactive radio channel time slots in order to provide enough digital signal processor resources to correct a frame of data while minimizing frame-buffering delays.

54. The computer-readable medium as claimed in claim 42, wherein the error burst is detected and corrected in real-time.

55. A method for correcting error bursts in a communication system using a shortened cyclic code, comprising:

loading data coded with a shortened cyclic code into a first error syndrome register and a second error syndrome register;

shifting shortened zero bits into the second error syndrome register;

shifting a first number of zero bits into the first error syndrome register to trap an error burst pattern in the data;

determining a second number of zero bit shifts into the second error syndrome register to trap an error burst location of the error burst pattern in the data; and

locating and correcting the error burst pattern in the data by using the second number of zero bit shifts and the error burst pattern.

56. The method as claimed in claim 55, wherein the shortened cyclic code is a shortened Fire code.