Method and apparatus for error management

• US 7,596,743 B2
• Filed: 09/28/2005
• Issued: 09/29/2009
• Est. Priority Date: 09/28/2005
• Status: Active Grant

• Current Assignee: ATI Technologies Incorporated (Advanced Micro Devices, Inc.)
• Original Assignee: ATI Technologies Incorporated (Advanced Micro Devices, Inc.)
• Inventors: Goma, Sergiu, Aleksic, Milivoje
• Primary Examiner(s): Lamarre; Guy J
• Application Number:
  US11/236,921
• Publication Number:
  US 20070089044A1
• Time in Patent Office: 1,462 Days
• Field of Search: 714/755, 714/777, 714/786, 714/800
• US Class Current: 714/777
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control

Abstract

To derive a Hamming code to manage data errors a set of at least four parity bit positions is selected for parity bits which will protect a set of data bits (where each data bit has a data bit position in the data bit set). A syndrome is determined for each data bit position. This involves selecting a unique sub-set of at least three parity bit positions. The unique sub-set shares at least one parity bit position with at least one other unique sub-set of at least three parity bit positions. A parity bit value may then be calculated for each parity bit position based on the determined syndromes. The header of a packet may be provided with a word which defines the length of the packet and an error management code generated utilizing this word so that errors in the word may be detected and, possibly, corrected.

Claims

1. A machine implemented data bit error management method comprising:

for a set of data bits, each data bit having a data bit position in said data bit set, generating a set of at least four parity bits, each parity bit having a parity bit position in said parity bit set, said generating comprising, for a given parity bit position;

calculating a parity bit for said given parity bit position from data bits at selected data bit positions such that each data bit position is selected for inclusion in the calculation of parity bits in at least three parity bit positions, said at least three parity bit positions being a sub-set of all possible parity bit positions, and such that, for a selected data bit position included in the calculation of a given sub-set of parity bit positions, said given subset of parity bit positions is unique to said selected data bit position, a base 2 number defined by said given sub-set has a lower numerical value than does a base 2 number defined by a sub-set unique to any next higher order data bit position, and at least one other data bit position is included in the calculation of at least one parity bit position of said given sub-set of parity bit positions; and

transmitting said set of data bits and said set of parity bits.

2. The method of claim 1 wherein each data bit position is included in the calculation of 2n+1 parity bits, where n is a positive integer.

3. The method of claim 2 wherein all possible sub-sets where n is 1 are chosen before any sub-sets are chosen where n is 2 and where all possible sub-sets where n is 2 are chosen before any sub-sets are chosen where n is 3.

4. The method of claim 1 wherein each data bit position is included in the calculation of 2n+2 parity bits, where n is a positive integer.

5. The method of claim 4 wherein all possible sub-sets where n is 1 are chosen before any sub-sets are chosen where n is 2 and where all possible sub-sets where n is 2 are chosen before any sub-sets are chosen where n is 3.

6. The method of claim 1 wherein the number of parity bits, p, in said set of parity bits is determined from the number of data bits, d, in said set of data bits based on the following equation:

d+p+1<

2^p.

7. The method of claim 1 further comprising choosing each said sub-set so as to maximize the number of sub-sets of equal size.

8. The method of claim 1 wherein said calculating comprises applying an XOR operation serially to said data bits at said selected data bit positions.

9. A machine implemented data bit error management method comprising:

selecting a set of parity bit positions for parity bits to protect a set of data bits, each data bit having a data bit position in said data bit set, said number of parity bits being at least four;

associating each data bit position with a different syndrome, each syndrome comprising a sub-set of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set and wherein said associating is such that a syndrome associated with a lower order data bit position equates to a word with a lower numerical value than does a syndrome associated with a next higher order data bit position;

calculating a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position; and

transmitting said set of data bits and said set of parity bit.

10. The method of claim 9 wherein each said sub-set has at least 2n+1 parity bit positions, where n is a positive integer.

11. The method of claim 10 wherein all possible sub-sets where n is 1 are chosen before any sub-sets are chosen where n is 2 and where all possible sub-sets where n is 2 are chosen before any sub-sets are chosen where n is 3.

12. The method of claim 9 wherein said sub-set has at least 2n+1 parity bit positions, where n is a positive integer.

13. The method of claim 11 wherein all possible sub-sets where n is 1 are chosen before any sub-sets are chosen where n is 2 and where all possible sub-sets where n is 2 are chosen before any sub-sets are chosen where n is 3.

14. The method of claim 9 further comprising choosing each said sub-set so as to maximize the number of sub-sets of equal size.

15. A computer readable storage media comprising computer readable instructions which, when controlling a parity generator, cause said parity generator to:

select a set of parity bit positions for parity bits to protect a set of data bits, each data bit having a data bit position in said data bit set, said number of parity bits being at least four;

associate each data bit position with a different syndrome, each syndrome comprising a sub-set of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set and wherein said associating is such that a syndrome associated with a lower order data bit position defines a base 2 number with a lower numerical value than does a syndrome associated with a next higher order data bit position;

calculate a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position.

16. The method of claim 15 wherein each said sub-set has at least 2n+1 parity bit positions, where n is a positive integer.

17. A transmitter comprising:

a parity generator for generating a set of at least four parity bits to protect a set of data bits, each parity bit having a parity bit position in said parity bit set, each data bit having a data bit position in said data bit set;

said parity generator associating each data bit position with a different syndrome, each syndrome comprising a sub-set of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set and wherein said associating is such that a syndrome associated with a lower order data bit position defines a base 2 number with a lower numerical value than does a syndrome associated with a next higher order data bit position;

said parity generator calculating a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position.

18. The transmitter of claim 17 wherein each said sub-set has at least 2n+1 parity bit positions, where n is a positive integer.

19. The transmitter of claim 17 further comprising a buffer for receiving said set of data bits and said set of parity bits such that said set of parity bits are appended to one end of said set of data bits.

20. A receiver comprising:

a parity generator for generating a set of at least four parity bits from a set of received data bits, each parity bit having a parity bit position in said parity bit set, each received data bit having a data bit position in said data bit set;

said parity generator associating each data bit position with a different syndrome, each syndrome comprising a sub-set of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set and such that each data bit position is included in the calculation of 2n+2 parity bits, where n is a positive integer; and

said parity generator calculating a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position.

21. The receiver of claim 20 further comprising a comparator for comparing a set of parity bits calculated by said parity generator with a set of parity bits received with said set of received data bits.

22. The receiver of claim 21 further comprising a syndrome decoder operatively coupled to an output of said comparator, said syndrome decoder associating said each data bit position with said different syndrome.

23. The receiver of claim 22 further comprising a bank of correction comparators, each correction comparator input with one received data bit and with an output of said syndrome decoder, said bank of correction comparators outputting a set of data bits from said receiver.

24. The receiver of claim 23 wherein said syndrome decoder has outputs to indicate no error, a corrected error, and an indeterminate error.

25. The receiver of claim 24 wherein said set of received data bits is three data bits in size and said set of parity bits is six parity bits in size.

26. The receiver of claim 24 wherein said set of received data bits is eight data bits in size and said set of parity bits is eight parity bits in size.

27. A system for managing data errors, comprising:

a transmitter comprising;

a transmitter parity generator for generating a set of at least four parity bits to protect a set of data bits, each parity bit having a parity bit position in said parity bit set, each data bit having a data bit position in said data bit set;

said transmitter parity generator associating each data bit position with a different syndrome, each syndrome comprising a sub-set of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set and wherein said associating is such that a syndrome associated with a lower order data bit position defines a base 2 number with a lower numerical value than does a syndrome associated with a next higher order data bit position; and

said transmitter parity generator calculating a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position; and

a receiver comprising;

a receiver parity generator for generating a set of at least four parity bits from a set of received data bits, each parity bit having a parity bit position in said parity bit set, each received data bit having a data bit position in said data bit set;

said receiver parity generator associating each data bit position with a different syndrome, each syndrome comprising a sub-set of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set; and

said receiver parity generator calculating a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position.

28. Apparatus to transmit a data packet comprising:

said data packet having a header and payload data, said header comprising a data length word based on a length of said payload data, and an error management code dependent on said data length word;

a parity generator for deriving said error management code, said parity generator generating a set of at least four parity bits to protect said data length word, each parity bit having a parity bit position in said parity bit set, each data bit in said data length word having a data bit position in said data length word;

said parity generator associating each data bit position with a different syndrome, each syndrome comprising a subset of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set and such that a base 2 number defined by a syndrome associated with a lower order data bit position has a lower numerical value than does a base 2 number defined by a syndrome associated with a next higher order data bit position; and

said parity generator calculating a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position.

29. Apparatus to receive a data packet comprising:

said data packet comprising a header and payload data;

said header comprising a data length word, and a received error management code;

a parity generator for deriving a calculated error management code, said parity generator generating a set of at least four parity bits from said data length word, each parity bit having a parity bit position in said parity bit set, each data bit in said data length word having a data bit position in said data length word;

said parity generator associating each data bit position with a different syndrome, each syndrome comprising a sub-set of at least three parity bit positions, such that each said sub-set has at least one parity bit position shared with at least one other said sub-set and wherein said associating is such that a syndrome associated with a lower order data bit position defines a base 2 number with a lower numerical value than does a syndrome associated with a next higher order data bit position; and

said parity generator calculating a parity bit value for each parity bit position from all data bit positions associated with said each parity bit position.

30. The apparatus of claim 29 further comprising a comparator for comparing said received error management code with said calculated error management code and, based on said comparison, selectively correcting said data length word.