Method and apparatus for error management

• US 8,769,384 B2
• Filed: 01/25/2012
• Issued: 07/01/2014
• Est. Priority Date: 09/28/2005
• Status: Active Grant

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Inventors: Goma, Sergiu, Aleksic, Milivoje
• Primary Examiner(s): LAMARRE, GUY J
• Application Number:
  US13/357,853
• Publication Number:
  US 20120124447A1
• Time in Patent Office: 888 Days
• Field of Search: 714/755, 714/777, 714/786, 714/800, 714/785
• 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 method of decoding at least twenty four data bits accompanied by a plurality of parity bits generated using a plurality of parity bit equations, said method comprising

calculating from said data bits and said plurality of parity bits a syndrome (SYN), using said plurality of parity bit equations;

determining an index i from said syndrome (SYN);

correcting a one bit error in the i^th position within said data bits;

wherein i=0 when said SYN=0x07;

i=1 when said SYN=0x0B;

i=2 when said SYN=0x0D;

i=3 when said SYN=0x0E;

i=4 when said SYN=0X13;

i=5 when said SYN=0x15;

i=6 when said SYN=0x16;

i=7 when said SYN=0x19;

i=8 when said SYN=0x1A;

i=9 when said SYN=0x1C;

i=10 when said SYN=0x23;

i=11 when said SYN=0x25;

i=12 when said SYN=0x26;

i=13 when said SYN=0x29;

i=14 when said SYN=0x2A, i=15 when said SYN=0x2C, i=16 when said SYN=0x31;

i=17 when said SYN=0x32;

i=18 when said SYN=0x34;

i=19 when said SYN=0x38;

i=20 when said SYN=0x1F;

i=21 when said SYN=0x2F;

i=22 when said SYN=0x37;

i=23 when said SYN=0x3B.

2. The method of claim 1, wherein said plurality of parity bits comprises at least six parity bits.

3. The method of claim 2, wherein said syndrome has six bits.

4. The method of claim 1, wherein said plurality of parity bits comprises 8 bits.

5. The method of claim 4, wherein said syndrome has 8 bits.

6. The method of claim 4, wherein said syndrome has 6 bits.

7. Computer readable medium storing processor executable instructions adapting a machine comprising a processor to perform the method of claim 1.

8. A data decoder for decoding ECC encoded data comprising at least twenty four data bits and a plurality of provided parity bits generated using a parity bit generator, said decoder comprising

a parity bit generator for calculating parity bits from said data bits;

a syndrome calculator for calculating a syndrome (SYN) from said parity bits as calculated and said provided parity bits;

a syndrome decoder for determining an index value i from said syndrome (SYN);

error correcting logic for correcting a one bit error in the i^th position within said data bits;

wherein said syndrome decoder decodes i=0 when said syndrome calculator calculates SYN=0x07;

i=1 when said syndrome calculator calculates SYN=0x0B;

i=2 when said syndrome calculator calculates SYN=0x0D;

i=3 when said syndrome calculator calculates SYN=0x0E;

i=4 when said syndrome calculator calculates SYN=0x13;

i=5 when said syndrome calculator calculates SYN=0x15;

i=6 when said syndrome calculator calculates SYN=0x16;

i=7 when said syndrome calculator calculates SYN=0x19;

i=8 when said syndrome calculator calculates SYN=0x1A;

i=9 when said syndrome calculator calculates SYN=0x1C;

i=10 when said syndrome calculator calculates SYN=0x23;

i=11 when said syndrome calculator calculates SYN=0x25;

i=12 when said syndrome calculator calculates SYN=0x26;

i=13 when said syndrome calculator calculates SYN=0x29;

i=14 when said syndrome calculator calculates SYN=0x2A, i=15 when said syndrome calculator calculates SYN=0x2C, i=16 when said syndrome calculator calculates SYN=0x31;

i=17 when said syndrome calculator calculates SYN=0x32;

i=18 when said syndrome calculator calculates SYN=0x34;

i=19 when said syndrome calculator calculates SYN=0x38;

i=20 when said syndrome calculator calculates SYN=0x1F;

i=21 when said syndrome calculator calculates SYN=0x2F;

i=22 when said syndrome calculator calculates SYN=0x37;

i=23 when said syndrome calculator calculates SYN=0x3B.

9. The method of claim 8, wherein said plurality of parity bits comprises 8 bits.

10. The method of claim 9, wherein said syndrome has 8 bits.

11. The method of claim 9, wherein said syndrome has 6 bits.

12. Computer readable medium storing processor executable instructions adapting a machine comprising a processor to perform the method of claim 8.

13. A data decoder for decoding ECC encoded data comprising at most sixty-four data bits and a plurality of provided parity bits generated using a parity bit generator, said decoder comprising

a parity bit generator for calculating parity bits from said data bits;

a syndrome calculator for calculating a syndrome (SYN) from said parity bits as calculated, and said provided parity bits;

a syndrome decoder for determining an index value i from said syndrome (SYN);

error correcting logic for correcting a one bit error in the i^th position within said data bits;

wherein said syndrome decoder decodes i=0 when said syndrome calculator calculates SYN=0x07;

i=1 when said syndrome calculator calculates SYN=0x0B;

i=2 when said syndrome calculator calculates SYN=0x0D;

i=3 when said syndrome calculator calculates SYN=0x0E;

i=4 when said syndrome calculator calculates SYN=0x13;

i=5 when said syndrome calculator calculates SYN=0x15;

i=6 when said syndrome calculator calculates SYN=0x16;

i=7 when said syndrome calculator calculates SYN=0x19;

i=8 when said syndrome calculator calculates SYN=0x1A;

i=9 when said syndrome calculator calculates SYN=0x1C;

i=10 when said syndrome calculator calculates SYN=0x23;

i=11 when said syndrome calculator calculates SYN=0x25;

i=12 when said syndrome calculator calculates SYN=0x26;

i=13 when said syndrome calculator calculates SYN=0x29;

i=14 when said syndrome calculator calculates SYN=0x2A, i=15 when said syndrome calculator calculates SYN=0x2C, i=16 when said syndrome calculator calculates SYN=0x31;

i=17 when said syndrome calculator calculates SYN=0x32;

i=18 when said syndrome calculator calculates SYN=0x34;

i=19 when said syndrome calculator calculates SYN=0x38;

i=20 when said syndrome calculator calculates SYN=0x1F;

i=21 when said syndrome calculator calculates SYN=0x2F;

i=22 when said syndrome calculator calculates SYN=0x37;

i=23 when said syndrome calculator calculates SYN=0x3B;

i=24 when said syndrome calculator calculates SYN=0x43;

i=25 when said syndrome calculator calculates SYN=0x45;

i=26 when said syndrome calculator calculates SYN=0x46;

i=27 when said syndrome calculator calculates SYN=0x49;

i=28 when said syndrome calculator calculates SYN=0x4A;

i=29 when said syndrome calculator calculates SYN=0x4C;

i=30 when said syndrome calculator calculates SYN=0x51;

i=31 when said syndrome calculator calculates SYN=0x52;

i=32 when said syndrome calculator calculates SYN=0x54;

i=33 when said syndrome calculator calculates SYN=0x58;

i=34 when said syndrome calculator calculates SYN=0x61;

i=35 when said syndrome calculator calculates SYN=0x62, i=36 when said syndrome calculator calculates SYN=0x64;

i=37 when said syndrome calculator calculates SYN=0x68;

i=38 when said syndrome calculator calculates SYN=0x70;

i=39 when said syndrome calculator calculates SYN=0x83;

i=40 when said syndrome calculator calculates SYN=0x85;

i=41 when said syndrome calculator calculates SYN=0x86;

i=42 SYN=0x89;

i=43 when said syndrome calculator calculates SYN=0x8A;

i=44 when said syndrome calculator calculates SYN=0x3D;

i=45 when said syndrome calculator calculates SYN=0x3E;

i=46 when said syndrome calculator calculates SYN=0x4F;

i=47 when said syndrome calculator calculates SYN=0x57;

i=48 when said syndrome calculator calculates SYN=0x8C;

i=49 when said syndrome calculator calculates SYN=0x91;

i=50 when said syndrome calculator calculates SYN=0x92;

i=51 when said syndrome calculator calculates SYN=0x94;

i=52 when said syndrome calculator calculates SYN=0x98;

i=53 when said syndrome calculator calculates SYN=0xA1;

i=54 when said syndrome calculator calculates SYN=0xA2;

i=55 when said syndrome calculator calculates SYN=0xA4;

i=56 when said syndrome calculator calculates SYN=0xA8;

i=57 when said syndrome calculator calculates SYN=0xB0;

i=58 when said syndrome calculator calculates SYN=0xC1;

i=59 when said syndrome calculator calculates SYN=0xC2;

i=60 when said syndrome calculator calculates SYN=0xC4;

i=61 when said syndrome calculator calculates SYN=0xC8;

i=62 when said syndrome calculator calculates SYN=0xD0;

i=63 when said syndrome calculator calculates SYN=0xE0.

14. A machine implemented method of decoding at most sixty four data bits accompanied by a plurality of parity bits generated using a parity bit generator, comprising:

calculating from said data bits and said parity bits data bits a syndrome (SYN), using said parity bit generator;

determining an index i from said syndrome;

correcting a one bit error the i^th position within said data bits;

wherein i=0 when said SYN=0x07;

i=1 when said SYN=0x0B;

i=2 when said SYN=0x0D;

i=3 when said SYN=0x0E;

i=4 when said SYN=0x13;

i=5 when said SYN=0x15;

i=6 when said SYN=0x16;

i=7 when said SYN=0x19;

i=8 when said SYN=0x1A;

i=9 when said SYN=0x1C;

i=10 when said SYN=0x23;

i=11 when said SYN=0x25;

i=12 when said SYN=0x26;

i=13 when said SYN=0x29;

i=14 when said SYN=0x2A, i=15 when said SYN=0x2C, i=16 when said SYN=0x31;

i=17 when said SYN=0x32;

i=18 when said SYN=0x34;

i=19 when said SYN=0x38;

i=20 when said SYN=0x1F;

i=21 when said SYN=0x2F;

i=22 when said SYN=0x37;

i=23 when said SYN=0x3B;

i=24 when said SYN=0x43;

i=25 when said SYN=0x45;

i=26 when said SYN=0x46;

i=27 when said SYN=0x49;

i=28 when said SYN=0x4A;

i=29 when said SYN=0x4C;

i=30 when said SYN=0x51;

i=31 when said SYN=0x52;

i=32 when said SYN=0x54;

i=33 when said SYN=0x58;

i=34 when said SYN=0x61;

i=35 when said SYN=0x62, i=36 when said SYN=0x64;

i=37 when said SYN=0x68;

i=38 when said SYN=0x70;

i=39 when said SYN=0x83;

i=40 when said SYN=0x85;

i=41 when said SYN=0x86;

i=42 when said SYN=0x89;

i=43 when said SYN=0x8A;

i=44 when said SYN=0x3D;

i=45 when said SYN=0x3E;

i=46 when said SYN=0x4F;

i=47 when said SYN=0x57;

i=48 when said SYN=0x8C;

i=49 when said SYN=0x91;

i=50 when said SYN=0x92;

i=51 when said SYN=0x94;

i=52 when said SYN=0x98;

i=53 when said SYN=0xA1;

i=54 when said SYN=0xA2;

i=55 when said SYN=0xA4;

i=56 when said SYN=0xA8;

i=57 when said SYN=0xB0;

i=58 when said SYN=0xC1;

i=59 when said SYN=0xC2;

i=60 when said SYN=0xC4;

i=61 when said SYN=0xC8;

i=62 when said SYN=0xD0;

i=63 when said SYN=0xE0.

15. The method of claim 14, wherein said plurality of parity bits comprises at least 8 parity bits.

16. The method of claim 15, wherein said syndrome has 6 bits.