Methods, architectures, circuits, software and systems for CRC determination

• US 7,360,142 B1
• Filed: 03/03/2004
• Issued: 04/15/2008
• Est. Priority Date: 03/03/2004
• Status: Active Grant

• Current Assignee: Marvell Israel MISL Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell Semiconductor Israel, Ltd. (Marvell Technology Group Limited)
• Inventors: Barash, Dror
• Primary Examiner(s): Chase; Shelly
• Assistant Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US10/794,496
• Time in Patent Office: 1,504 Days
• Field of Search: None
• US Class Current: 714/758
• 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/6516 Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Abstract

Methods, circuits, architectures, and systems for error detection in transmitted data. The method generally includes the steps of (i) partitioning the unit of digital data into one or more full data lines and a remainder, wherein each of the full data lines comprises a predetermined number of data blocks, each of the data blocks has a first fixed length, the predetermined number is an integer of at least 2, and the remainder has a length less than the predetermined number times the first fixed length; (ii) if the remainder contains at least one data bit, adding to the remainder a padding vector having a length sufficient to generate a padded data line having the predetermined number of data blocks; and (iii) performing error checking calculations on the full data lines and the padded data line. The present invention reduces the chip area and power consumption, while improving system performance.

Claims

1. A method of checking a unit of digital data for a transmission error, comprising the steps of:

a) partitioning said unit of digital data into (i) one or more fall data lines and (ii) a remainder, wherein each of said full data lines comprises a predetermined number of data blocks, each of said data blocks has a first fixed length of 2ⁿ bits, where n is an integer of at least 3, said predetermined number is an integer of at least 2, and said remainder has a second length less than said predetermined number times said first fixed length;

b) when said second length is at least one bit, selecting a padding vector from a set of padding vectors stored in a storage table, and adding the padding vector to said remainder, said padding vector having a length sufficient to generate a padded data line having said predetermined number of data blocks; and

c) performing error checking calculations on said full data lines and said padded data line.

2. The method of claim 1, wherein each of said padding vectors in said set of padding vectors is a zero-pad vector.

3. The method of claim 1, further comprising the step of determining whether said remainder has a length of at least one bit.

4. The method of claim 3, wherein said second length is equal to an integer number of said data blocks, said integer number being less than said predetermined number.

5. The method of claim 4, further comprising the step of determining the number of data blocks in said second length.

6. The method of claim 5, wherein said storage table comprises a hash table or a look-up table.

7. The method of claim 6, wherein said padding vector is selected based on information about the number of data blocks in said second length.

8. The method of claim 1, wherein said error checking calculations comprise cyclic redundancy check (CRC) calculations.

9. The method of claim 1, wherein said first fixed length comprises 2^m bits, where m is an integer from 6 to 10.

10. The method of claim 1, wherein said unit of digital data comprises a packet or frame.

11. The method of claim 1, wherein n is an integer from 3 to 6.

12. The method of claim 11, wherein n is 5.

13. The method of claim 1, wherein said performing step comprises (i) generating redundant error checking code from said full data lines and said padded data line and (ii) comparing the redundant error checking code with redundant error checking information transmitted with the unit of digital data.

14. The method of claim 1, wherein said checking step comprises checking each of said full data lines and said padded data line with common circuitry.

15. The method of claim 1, further comprising receiving said digital data.

16. A computer-readable medium storing a set of instructions which, when executed by a signal processing device configured to execute computer-readable instructions, is configured to perform the method of claim 1.

17. The computer-readable medium of claim 16, wherein said set of padding vectors are stored in a hash table or a look-up table.

18. The computer-readable medium of claim 17, wherein said padding vector is selected in response to information comprising said second length of said remainder.

19. The computer-readable medium of claim 16, wherein said padding vector is a zero-pad vector.

20. The computer-readable medium of claim 16, wherein said set of instructions further comprises an instruction to determine a length of said remainder.

21. The computer-readable medium of claim 16, wherein said second length is equal to an integer number of said data blocks, said integer number being less than said predetermined number, and said set of instructions further comprise an instruction to determine the number of data blocks in said second length.

22. The computer-readable medium of claim 16, wherein said error checking calculations comprise cyclic redundancy check (CRC) calculations.

23. The computer-readable medium of claim 16, wherein said set of instructions further comprises instructions to (i) calculate redundant error checking code from said full data lines and said padded data line and (ii) compare the redundant error checking code with redundant error checking information transmitted with the unit of digital data.

24. A method of checking a packet or frame for a transmission error, comprising:

a) partitioning said packet or frame into (i) one or more full data lines and (ii) a remainder, wherein said packet or frame comprises (2^x·

y)+z words, 2^x is the number of words in one of said full data lines, x is an integer of from 1 to 4, y is the number of full data lines in said packet or frame, and z is an integer of less than 2^x, and said remainder has a length less than a fixed length of said full data line;

b) if said length of said remainder is at least one bit, selecting a padding vector from a set of padding vectors stored in a storage table, and adding said padding vector to said remainder, said padding vector having a length sufficient to generate a padded data line having said fixed length; and

c) performing error checking calculations on said full data lines and said padded data line.

25. The method of claim 24, wherein when z is at least 1, said length of said padding vector is 2^x−

z words.

26. The method of claim 24, further comprising selecting said padding vector from a set of padding vectors of varying lengths stored in a storage circuit.

27. A circuit for determining a digital data transmission error, comprising:

a) a data partitioning circuit configured to partition a unit of said digital data into (i) one or more full data lines comprising a plurality of data blocks, each data block having a first fixed length of 2ⁿ bits, where n is an integer of at least 3, and (ii) a remainder, if said unit of digital data is not partitionable into an integer number of said data lines;

b) a storage circuit configured to store a set of padding vectors of varying lengths;

c) a padding circuit configured to add one of said padding vectors to said remainder, if present, to generate a padded data line having a length equal to that of said plurality of data blocks; and

d) an error detection circuit configured to (i) receive said full data lines and said padded data line, and (ii) detect a transmission error in said unit of said digital data from said full data lines and said padded data line.

28. The circuit of claim 27, wherein said storage circuit comprises a hash table or a look-up table;

and said padding circuit further comprises a padding vector selector, configured to select one of said padding vectors.

29. The circuit of claim 27, wherein said storage circuit comprises a hash table or a look-up table.

30. The circuit of claim 29, wherein each of said padding vectors in said set of padding vectors is a zero-pad vector.

31. The circuit of claim 27, wherein said padding circuit selects said one of said padding vectors in response to a remainder information signal, and a state of said remainder information signal corresponds to a length of said remainder.

32. The circuit of claim 31, further comprising a logic circuit configured to generate said remainder information signal.

33. The circuit of claim 27, wherein n is from 3 to 7.

34. The circuit of claim 27, wherein each of said full data lines and said padded data line comprise 2^x data blocks, where x is an integer from 1 to 4.

35. The circuit of claim 27, wherein said unit of digital data comprises a packet or frame.

36. The circuit of claim 27, wherein each of said data blocks consists of a data word.

37. The circuit of claim 27, wherein said data partitioning circuit comprises a deserializer and/or a plurality of data bit storage elements configured to store one or more of said plurality of data blocks.

38. The circuit of claim 27, wherein said error detection circuit comprises a cyclic redundancy checking (CRC) circuit.

39. A receiver, comprising:

a) the circuit of claim 27;

b) a processor in communication with said circuit, configured to process said digital data; and

c) a clock recovery circuit configured to recover a clock signal from serial data received by said receiver.

40. The receiver of claim 39, embodied on a single integrated circuit.

41. The receiver of claim 39, further comprising a divider configured to divide said recovered clock.

42. The receiver of claim 39, wherein said processor is configured to process said full data lines and said padded data line received from said error detection circuit.

43. The receiver of claim 39, wherein said data partitioning circuit comprises a deserializer configured to convert serial digital data into parallel digital data for processing by said error detection circuit.

44. The receiver of claim 39, wherein said unit of digital data comprises a packet or frame.

45. The receiver of claim 44, wherein each of said data blocks consists of a data word.

46. The receiver of claim 44, wherein said processor is further configured to assemble (i) non-data information from said packet or frame and (ii) at least part of said digital data.

47. The receiver of claim 46, further comprising a decoder configured to decode at least part of said non-data information.

48. The receiver of claim 39, further comprising a logic circuit configured to (i) receive said padded data line from said error detection circuit and (ii) remove said padding vector from said padded data line.

49. The receiver of claim 39, wherein said error detection circuit comprises a cyclic redundancy checking (CRC) circuit.

50. A system for transferring data on or across a network, comprising:

a) the receiver of claim 39;

b) at least one transmitter in communication with said receiver, said transmitter being configured to transmit said serial information to said receiver; and

c) at least one receiver port in communication with said receiver for receiving said serial information.

51. The system of claim 50, wherein said error detection circuit comprises a cyclic redundancy checking (CRC) circuit.

52. The system of claim 51, wherein said transmitter further comprises (i) a CRC generator configured to generate CRC information from a data portion of said serial information and (ii) a transmitter processor configured to add said CRC information to or insert said CRC information in said serial information.

53. The system of claim 50, wherein said receiver further comprises a control circuit configured to generate a control signal in response to said error detection circuit detecting at least one of an error and no error in said unit of digital data.

54. The system of claim 50, further comprising a control bus configured to transmit said control signal from said receiver to said transmitter.

55. A network, comprising:

a) a plurality of the systems of claim 50, in communication with each other; and

b) a plurality of storage or communications devices, each of said storage or communications devices being in communication with one of said systems.

56. The network of claim 55, wherein said plurality of storage or communications devices comprises a plurality of storage devices.

57. A circuit for determining a digital data transmission error, comprising:

a) a data partitioning circuit configured to partition a unit of said digital data into (i) one or more full data lines comprising a plurality of data blocks, each data block having a first fixed length, and (ii) a remainder, if said unit of digital data is not partitionable into an integer number of said data lines;

b) a padding circuit configured to add a padding vector to said remainder, if present, to generate a padded data line having a length equal to that of said plurality of data blocks, wherein each of said full data lines and said padded data line has a second fixed length, and said second fixed length is an integer multiple of said first fixed length; and

c) an error detection circuit configured to (i) receive said full data lines and said padded data line, and (ii) detect a transmission error in said unit of said digital data from said full data lines and said padded data line.

58. The circuit of claim 57, wherein said second fixed length consists of 2^m bits, where m is an integer from 6 to 10.

59. A receiver, comprising:

a) a circuit for determining a digital data transmission error, comprising

i) a data partitioning circuit configured to partition a unit of said digital data into one or more full data lines comprising a plurality of data blocks, each data block having a first fixed length, and a remainder, if said unit of digital data is not partitionable into an integer number of said data lines,

ii) a padding circuit configured to add a padding vector to said remainder, if present, to generate a padded data line having a length equal to that of said plurality of data blocks, wherein each of said full data lines and said padded data line has a second fixed length, and said second fixed length is an integer multiple of said first fixed length; and

iii) an error detection circuit configured to (i) receive said full data lines and said padded data line, and (ii) detect a transmission error in said unit of said digital data from said full data lines and said padded data line;

b) a processor in communication with said circuit, configured to process said digital data; and

c) a clock recovery circuit configured to recover a clock signal from serial data received by said receiver.

60. The receiver of claim 59, wherein said second fixed length consists of 2^m bits, where m is an integer from 6 to 10.

61. A circuit for determining a data transmission error, comprising:

a) means for partitioning a unit of said data into (i) one or more full data lines, each comprising a plurality of data blocks, each data block having a first fixed length, and (ii) a remainder, if said unit of digital data is not partitionable into an integer number of said data lines;

b) means for padding said remainder, if said remainder has a non-zero length, to generate a padded data line having a length equal to that of said plurality of data blocks, wherein each of said full data lines and said padded data line has a second fixed length, and said second fixed length is an integer multiple of said first fixed length; and

c) means for detecting a transmission error in said unit of data from said full data lines and said padded data line.

62. A circuit for determining a data transmission error, comprising:

a) means for partitioning a unit of said data into (i) one or more full data lines, each comprising a plurality of data blocks, each data block having a first fixed length of 2ⁿ bits, where n is an integer of at least 3, and (ii) a remainder, if said unit of digital data is not partitionable into an integer number of said data lines;

b) means for storing a set of padding vectors of varying lengths;

c) means for selecting one of said padding vectors and padding said remainder, if said remainder has a non-zero length, to generate a padded data line having a length equal to that of said plurality of data blocks; and

d) means for detecting a transmission error in said unit of data from said full data lines and said padded data line.

63. The circuit of claim 62, wherein each of said padding vectors in said set of padding vectors is a zero-pad vector.

64. The circuit of claim 62, wherein said means for selecting selects said one of said padding vectors in response to a remainder information signal, and a state of said remainder information signal corresponds to a length of said remainder.

65. The circuit of claim 64, further comprising a means for generating said remainder information signal.

66. The circuit of claim 62, wherein n is from 3 to 7.

67. The circuit of claim 62, wherein each of said full data lines and said padded data line comprise 2^x data blocks, where x is an integer from 1 to 4.

68. The circuit of claim 62, wherein said unit of digital data comprises a packet or frame.

69. The circuit of claim 62, wherein each of said data blocks consists of a data word.

70. The circuit of claim 62, wherein said means for partitioning comprises a means for deserializing said data.

71. The circuit of claim 62, wherein said means for detecting comprises a means for calculating cyclic redundancy code.

72. A receiver, comprising:

a) the circuit of claim 62;

b) a means for processing in communication with said circuit, configured to process said data; and

c) a means for recovering a clock signal from serial data received by said receiver.

73. The receiver of claim 72, embodied on a single integrated circuit.

74. The receiver of claim 72, further comprising a means for dividing said recovered clock.

75. The receiver of claim 72, wherein said means for processing processes data received from said means for detecting.

76. The receiver of claim 72, wherein said unit of data comprises a packet or frame.

77. The receiver of claim 76, wherein each of said data blocks consists of a data word.

78. The receiver of claim 76, wherein said means for processing comprises a means for assembling (i) non-data information from said packet or frame and (ii) said unit of data.

79. The receiver of claim 78, further comprising a means for decoding at least part of said non-data information.

80. The receiver of claim 78, wherein said means for processing further comprises a means for removing said padding vector from said padded data line.

81. The receiver of claim 72, wherein each of said full data lines and said padded data line has a second fixed length, and said second fixed length is an integer multiple of said first fixed length.

82. The receiver of claim 81, wherein said second fixed length consists of 2^m bits, where m is an integer from 6 to 10.

83. The receiver of claim 72, wherein said means for detecting comprises a means for calculating cyclic redundancy code.

84. A system for transferring data on or across a network, comprising:

a) the receiver of claim 72;

b) a means for transmitting said serial data to said receiver; and

c) at least one means for receiving said serial data, said means for receiving being in communication with said receiver.

85. The system of claim 84, wherein said means for detecting comprises a first means for calculating cyclic redundancy code.

86. The system of claim 84, wherein said means for transmitting further comprises (i) a second means for calculating cyclic redundancy code and (ii) a means for adding cyclic redundancy code information to or insert cyclic redundancy code information in said serial data.

87. The system of claim 86, wherein said receiver further comprises a means for generating a control signal in response to at least one of (i) an error in said unit of data and (ii) no error in said unit of data detected by said means for detecting.

88. A network, comprising:

a) a plurality of the systems of claim 84, in communication with each other; and

b) a plurality of means for storing or means for communicating data, each of said means for storing or means for communicating data being in communication with at least one of said systems.

89. The network of claim 88, wherein said plurality of means for storing or means for communicating data comprises a plurality of means for storing.