Method and apparatus for error management

• US 8,127,208 B2
• Filed: 08/24/2009
• Issued: 02/28/2012
• 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:
  US12/546,355
• Publication Number:
  US 20090313529A1
• Time in Patent Office: 918 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 parity bit generator for generating at least eight parity bits {P₀, P₁, P₂ . . . P₇} corresponding to 64 data bits {D₀, D₁, D₂ . . . D₆₃}, comprising:

at least one electronic logic circuit configured to calculate said parity bits as follows;

P₇=D₆₃^D₆₂^D₆₁^D₆₀^D₅₉^D₅₈^D₅₇^D₅₆^D₅₅^D₅₄^D₅₃^D₅₂^D₅₁^D₅₀^D₄₉^D₄₈^D₄₃^D₄₂^D₄₁^D₄₀^D₃₉;

P₆=D₆₃^D₆₂^D₆₁^D₆₀^D₅₉^D₅₈^D₄₇^D₄₆^D₃₈^D₃₇^D₃₆^D₃₅^D₃₄^D₃₃^D₃₂^D₃₁^D₃₀^D₂₉^D₂₈^D₂₇^D₂₆^D₂₅^D₂₄;

P₅=D₆₃^D₅₇^D₅₆^D₅₅^D₅₄^D₅₃^D₄₅^D₄₄^D₃₈^D₃₇^D₃₆^D₃₅^D₃₄^D₂₃^D₂₂^D₂₁^D₁₉^D₁₈^D₁₇^D₁₆^D₁₅^D₁₄^D₁₃^D₁₂^D₁₁^D₁₀;

P₄=D₆₂^D₅₇^D₅₂^D₅₁^D₅₀^D₄₉^D₄₇^D₄₅^D₄₄^D₃₈^D₃₃^D₃₂^D₃₁^D₃₀^D₂₃^D₂₂^D₂₀^D₁₉^D₁₈^D₁₇^D₁₆^D₉^D₈^D₇^D₆^D₅^D₄;

P₃=D₆₁^D₅₆^D₅₂^D₄₈^D₄₆^D₄₅^D₄₄^D₄₃^D₄₂^D₃₇^D₃₃^D₂₉^D₂₈^D₂₇^D₂₃^D₂₁^D₂₀^D₁₉^D₁₅^D₁₄^D₁₃^D₉^D₈^D₇^D₃^D₂^D₁;

P₂=D₆₀^D₅₅^D₅₁^D₄₈^D₄₇^D₄₆^D₄₅^D₄₄^D₄₁^D₄₀^D₃₆^D₃₂^D₂₉^D₂₆^D₂₅^D₂₂^D₂₁^D₂₀^D₁₈^D₁₅^D₁₂^D₁₁^D₉^D₆^D₅^D₃^D₂^D₀;

P₁=D₅₉^D₅₄^D₅₀^D₄₇^D₄₆^D₄₅^D₄₃^D₄₁^D₃₉^D₃₅^D₃₁^D₂₈^D₂₆^D₂₄^D₂₃^D₂₂^D₂₀^D₁₇^D₁₄^D₁₂^D₁₀^D₈^D₆^D₄^D₃^D₁^D₀; and

P₀=D₅₈^D₅₃^D₄₉^D₄₇^D₄₆^D₄₄^D₄₂^D₄₀^D₃₉^D₃₄^D₃₀^D₂₇^D₂₅^D₂₄^D₂₃^D₂₂^D₂₁^D₂₀^D₁₆^D₁₃^D₁₁^D₁₀^D₇^D₅^D₄^D₂^D₁^D₀.

2. A parity bit generator for generating at least six parity bits {P₀, P₁, P₂ . . . P₅} corresponding to twenty four data bits {D₀, D₁, D₂ . . . D₂₃}, comprising:

at least one electronic logic circuit configured to calculate said parity bits as follows;

P₅=D₂₃^D₂₂^D₂₁^D₁₉^D₁₈^D₁₇^D₁₆^D₁₅^D₁₄^D₁₃^D₁₂^D₁₁^D₁₀;

P₄=D₂₃^D₂₂^D₂₀^D₁₉^D₁₈^D₁₇^D₁₆^D₉^D₈^D₇^D₆^D₅^D₄;

P₃=D₂₃^D₂₁^D₂₀^D₁₉^D₁₈^D₁₇^D₁₆^D₉^D₈^D₇^D₃^D₂^D₁;

P₂=D₂₂^D₂₁^D₂₀^D₁₈^D₁₅^D₁₂^D₁₁^D₉^D₆^D₅^D₃^D₂^D₀;

P₁=D₂₃^D₂₂^D₂₁^D₂₀^D₁₇^D₁₄^D₁₂^D₁₀^D₈^D₆^D₄^D₃^D₁^D₀; and

P₀=D₂₃^D₂₂^D₂₁^D₂₀^D₁₆^D₁₃^D₁₁^D₁₀^D₇^D₅^D₄^D₂^D₁^D₀.

3. A machine implemented method of generating at least eight parity bits {P₀, P₁, P₂ . . . P₇} corresponding to sixty four data bits {D₀, D₁, D₂ . . . D₆₃}, said method comprising:

(i) calculating

P₇=D₆₃^D₆₂^D₆₁^D₆₀^D₅₉^D₅₈^D₅₇^D₅₆^D₅₅^D₅₄^D₅₃^D₅₂^D₅₁^D₅₀^D₄₉^D₄₈^D₄₃^D₄₂^D₄₁^;

^D₄₀^D₃₉;

(ii) calculating

P₆=D₆₃^D₆₂^D₆₁^D₆₀^D₅₉^D₅₈^D₄₇^D₄₆^D₃₈^D₃₇^D₃₆^D₃₅^D₃₄^D₃₃^D₃₂^D₃₁^D₃₀^D₂₉^D₂₈^;

^D₂₇^D₂₆^D₂₅^D₂₄;

(iii) calculating

P₅=D₆₃^D₅₇^D₅₆^D₅₅^D₅₄^D₅₃^D₄₅^D₄₄^D₃₈^D₃₇^D₃₆^D₃₅^D₃₄^D₂₃^D₂₂^D₂₁^D₁₉^D₁₈^D₁₇^;

^D₁₆^D₁₅^D₁₄^D₁₃^D₁₂^D₁₁^D₁₀;

(iv) calculating

P₄=D₆₂^D₅₇^D₅₂^D₅₁^D₅₀^D₄₉^D₄₇^D₄₅^D₄₄^D₃₈^D₃₃^D₃₂^D₃₁^D₃₀^D₂₃^D₂₂^D₂₀^D₁₉^D₁₈^D₁₇^D₁₆^D₉^D₈^D₇^D₆^D₅^D₄;

(v) calculating

P₃=D₆₁^D₅₆^D₅₂^D₄₈^D₄₆^D₄₅^D₄₄^D₄₃^D₄₂^D₃₇^D₃₃^D₂₉^D₂₈^D₂₇^D₂₃^D₂₂^D₂₀^D₁₉^D₁₅^D₁₄^D₁₃^D₉^D₈^D₇^D₃^D₂^D₁;

(vi) calculating

P₂=D₆₀^D₅₅^D₅₁^D₄₈^D₄₇^D₄₆^D₄₅^D₄₄^D₄₁^D₄₀^D₃₆^D₃₂^D₂₉^D₂₆^D₂₅^D₂₂^D₂₁^D₂₀^D₁₈^D₁₅^D₁₂^D₁₁^D₉^D₆^D₅^D₃^D₂^D₀;

(vii) calculating

P₁=D₅₉^D₅₄^D₅₀^D₄₇^D₄₆^D₄₅^D₄₃^D₄₁^D₃₉^D₃₅^D₃₁^D₂₈^D₂₆^D₂₄^D₂₃^D₂₂^D₂₁^D₂₀^D₁₇^D₁₄^D₁₂^D₁₀^D₈^D₆^D₄^D₃^D₂^D₁^D₀; and

(viii) calculating

P₀=D₅₈^D₅₃^D₄₉^D₄₇^D₄₆^D₄₄^D₄₂^D₄₀^D₃₉^D₃₄^D₃₀^D₂₇^D₂₅^D₂₄^D₂₃^D₂₂^D₂₁^D₂₀^D₁₆^D₁₃^D₁₁^D₁₀^D₇^D₅^D₄^D₂^D₁^D₀.

4. A machine implemented method of generating at least six parity bits {P₀, P₁, P₂ . . . P₅} corresponding to twenty four data bits {D₀, D₁, D₂ . . . D₂₃}, said method comprising:

(i) calculating P₅=D₂₃^D₂₂^D₂₁^D₁₉^D₁₈^D₁₇^D₁₆^D₁₅^D₁₄^D₁₃^D₁₂^D₁₁^D₁₀;

(ii) calculating P₄=D₂₃^D₂₂^D₂₀^D₁₉^D₁₈^D₁₇^D₁₆^D₉^D₈^D₇^D₆^D₅^D₄;

(iii) calculating P₃=D₂₃^D₂₁^D₂₀^D₁₉^D₁₅^D₁₄^D₁₃^D₉^D₈^D₇^D₃^D₂^D₁;

(iv) calculating P₂=D₂₂^D₂₁^D₂₀^D₁₈^D₁₅^D₁₂^D₁₁^D₉^D₆^D₅^D₃^D₂^D₀;

(v) calculating P₁=D₂₃^D₂₂^D₂₁^D₂₀^D₁₇^D₁₄^D₁₂^D₁₀^D₈^D₆^D₄^D₃^D₁^D₀; and

(vi) calculating P₀=D₂₃^D₂₂^D₂₁^D₂₀^D₁₆^D₁₃^D₁₁^D₁₀^D₇^D₅^D₄^D₂^D₁^D₀.

5. A parity bit generator for generating at least eight parity bits {P₀, P₁, P₂ . . . P₇} corresponding to 64 data bits {D₀, D₁, D₂ . . . D₆₃}, comprising:

(i) means for calculating

P₇=D₆₃^D₆₂^D₆₁^D₆₀^D₅₉^D₅₈^₅₇^D₅₆^₅₅^D₆₄^D₅₃^D₅₂^D₅₁^D₅₀^D₄₉^D₄₈^D₄₃^D₄₂^D₄₁^D₄₀^D₃₉;

(ii) means for calculating

P₆=D₆₃^D₆₂^D₆₁^D₆₀^D₅₉^D₅₈^₄₇^D₄₆^₃₈^D₃₇^D₃₆^D₃₅^D₃₄^D₃₃^D₃₂^D₃₁^D₃₀^D₂₉^D₂₈^D₂₇^D₂₆^D₂₅^D₂₄;

(iii) means for calculating

P₅=D₂₃^D₂₂^D₂₁^D₁₉^D₁₈^D₁₇^D₁₆^D₁₅^D₁₄^D₁₃^D₁₂^D₁₁^D₁₀;

(iv) means for calculating

P₄=D₆₂^D₅₇^D₅₂^D₅₁^D₅₀^D₄₉^D₄₇^D₄₅^D₄₄^D₃₈^D₃₃^D₃₂^D₃₁^D₃₀^D₂₃^D₂₂^D₂₀^D₁₉^D₁₈^D₁₇^D₁₆^D₉^D₈^D₇^D₆^D₅^D₄;

(v) means for calculating

P₃=D₆₁^D₅₆^D₅₂^D₄₈^D₄₆^D₄₅^₄₄^D₄₃^₄₂^D₃₇^D₃₃^D₂₉^D₂₈^D₂₇^D₂₃^D₂₁^D₂₀^D₁₉^D₁₅^D₁₄^D₁₃^D₉^D₈^D₇^D₃^D₂^D₁;

(vi) means for calculating

P₂=D₆₀^D₅₅^D₅₁^D₄₈^D₄₇^D₄₆^₄₅^D₄₄^₄₁^D₄₀^D₃₆^D₃₂^D₂₉^D₂₆^D₂₅^D₂₂^D₂₁^D₂₀^D₁₈^D₁₅^D₁₂^D₁₁^D₉^D₆^D₅^D₃^D₂^D₀;

(vii) means for calculating

P₁=D₅₉^D₅₄^D₅₀^D₄₇^D₄₆^D₄₅^₄₃^D₄₁^₃₉^D₃₅^D₃₁^D₂₈^D₂₆^D₂₄^D₂₃^D₂₂^D₂₀^D₁₇^D₁₄^D₁₂^D₁₀^D₈^D₆^D₄^D₃^D₁^D₀; and

(viii) means for calculating

P₀=D₅₈^D₅₃^D₄₉^D₄₇^D₄₆^D₄₄^D₄₂^D₄₀^D₃₉^D₃₄^D₃₀^D₂₇^D₂₅^D₂₄^D₂₃^D₂₂^D₂₁^D₂₀^D₁₆^D₁₃^D₁₁^D₁₀^D₇^D₅^D₄^D₂^D₁^D₀.

6. A parity bit generator for generating at least six parity bits {P₀, P₁, P₂ . . . P₅} corresponding to twenty four data bits {D₀, D₁, D₂ . . . D₂₃}, comprising:

(i) means for calculating P₅=D₂₃^D₂₂^D₂₁^D₁₉^D₁₈^D₁₇^D₁₆^D₁₅^D₁₄^D₁₃^D₁₂^D₁₁^D₁₀;

(ii) means for calculating P₄=D₂₃^D₂₂^D₂₀^D₁₉^D₁₈^D₁₇^D₁₆^D₉^D₈^D₇^D₆^D₅^D₄;

(iii) means for calculating P₃=D₂₃^D₂₁^D₂₀^D₁₉^D₁₅^D₁₄^D₁₃^D₉^D₈^D₇^D₃^D₂^D₁;

(iv) means for calculating P₂=D₂₂^D₂₁^D₂₀^D₁₈^D₁₅^D₁₂^D₁₁^D₉^D₆^D₅^D₃^D₂^D₀;

(v) means for calculating P₁=D₂₃^D₂₂^D₂₁^D₂₀^D₁₇^D₁₄^D₁₂^D₁₀^D₈^D₆^D₄^D₃^D₁^D₀; and

and

(vi) means for calculating P₀=D₂₃^D₂₂^D₂₁^D₂₀^D₁₆^D₁₃^D₁₁^D₁₀^D₇^D₅^D₄^D₂^D₁^D₀.