METHOD AND APPARATUS FOR ERROR MANAGEMENT

• US 20090313529A1
• Filed: 08/24/2009
• Published: 12/17/2009
• Est. Priority Date: 09/28/2005
• Status: Active Grant

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: ATI Technologies Incorporated (Advanced Micro Devices, Inc.)
• Inventors: Goma, Sergiu, Aleksic, Milivoje
• Granted Patent: US 8,127,208 B2
• Time in Patent Office: Days
• 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 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, such that, for a selected data bit position included in the calculation of a given sub-set of parity bit positions, said given sub-set of parity bit positions is unique to said selected 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.

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 1 wherein each data bit position is included in the calculation of 4n parity bit, where n is a positive integer.

4. 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.

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

6. The method of claim 1 wherein said selecting is such that lower order data bit positions are selected for the calculation of lower order parity bit positions.

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

8. A 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

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

9. The method of claim 8 wherein said associating is such that a syndrome for a lower order data bit position equates to a word with a lower numerical value than does a syndrome for a next higher order data bit position.

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

11. The method of claim 8 wherein said sub-set has at least 4n parity bit positions, where n is a positive integer.

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

13. 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

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.

14. The transmitter of claim 13 wherein said parity bit generator maximizes the number of sub-sets of equal size.

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

16. The transmitter of claim 14 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.