IP Library › Granted Patent US 8,127,208

Granted Patent B2

US 8,127,208 · App. 12/546,355 · Granted Feb 28, 2012

Method and apparatus for error management

Assignee: ATI Technologies ULC

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 8,127,208
App. No.: 12/546,355
Granted: Feb 28, 2012
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

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 (66)

1. A parity bit generator for generating at least eight parity bits {P 0 , P 1 , P 2 . . . P 7 } corresponding to 64 data bits {D 0 , D 1 , D 2 . . . D 63 }, comprising:

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

P 7 =D 63 ^D 62 ^D 61 ^D 60 ^D 59 ^D 58 ^D 57 ^D 56 ^D 55 ^D 54 ^D 53 ^D 52 ^D 51 ^D 50 ^D 49 ^D 48 ^D 43 ^D 42 ^D 41 ^D 40 ^D 39 ;

P 6 =D 63 ^D 62 ^D 61 ^D 60 ^D 59 ^D 58 ^D 47 ^D 46 ^D 38 ^D 37 ^D 36 ^D 35 ^D 34 ^D 33 ^D 32 ^D 31 ^D 30 ^D 29 ^D 28 ^D 27 ^D 26 ^D 25 ^D 24 ;

P 5 =D 63 ^D 57 ^D 56 ^D 55 ^D 54 ^D 53 ^D 45 ^D 44 ^D 38 ^D 37 ^D 36 ^D 35 ^D 34 ^D 23 ^D 22 ^D 21 ^D 19 ^D 18 ^D 17 ^D 16 ^D 15 ^D 14 ^D 13 ^D 12 ^D 11 ^D 10 ;

P 4 =D 62 ^D 57 ^D 52 ^D 51 ^D 50 ^D 49 ^D 47 ^D 45 ^D 44 ^D 38 ^D 33 ^D 32 ^D 31 ^D 30 ^D 23 ^D 22 ^D 20 ^D 19 ^D 18 ^D 17 ^D 16 ^D 9 ^D 8 ^D 7 ^D 6 ^D 5 ^D 4 ;

P 3 =D 61 ^D 56 ^D 52 ^D 48 ^D 46 ^D 45 ^D 44 ^D 43 ^D 42 ^D 37 ^D 33 ^D 29 ^D 28 ^D 27 ^D 23 ^D 21 ^D 20 ^D 19 ^D 15 ^D 14 ^D 13 ^D 9 ^D 8 ^D 7 ^D 3 ^D 2 ^D 1 ;

P 2 =D 60 ^D 55 ^D 51 ^D 48 ^D 47 ^D 46 ^D 45 ^D 44 ^D 41 ^D 40 ^D 36 ^D 32 ^D 29 ^D 26 ^D 25 ^D 22 ^D 21 ^D 20 ^D 18 ^D 15 ^D 12 ^D 11 ^D 9 ^D 6 ^D 5 ^D 3 ^D 2 ^D 0 ;

P 1 =D 59 ^D 54 ^D 50 ^D 47 ^D 46 ^D 45 ^D 43 ^D 41 ^D 39 ^D 35 ^D 31 ^D 28 ^D 26 ^D 24 ^D 23 ^D 22 ^D 20 ^D 17 ^D 14 ^D 12 ^D 10 ^D 8 ^D 6 ^D 4 ^D 3 ^D 1 ^D 0 ; and

P 0 =D 58 ^D 53 ^D 49 ^D 47 ^D 46 ^D 44 ^D 42 ^D 40 ^D 39 ^D 34 ^D 30 ^D 27 ^D 25 ^D 24 ^D 23 ^D 22 ^D 21 ^D 20 ^D 16 ^D 13 ^D 11 ^D 10 ^D 7 ^D 5 ^D 4 ^D 2 ^D 1 ^D 0 .

2. A parity bit generator for generating at least six parity bits {P 0 , P 1 , P 2 . . . P 5 } corresponding to twenty four data bits {D 0 , D 1 , D 2 . . . D 23 }, comprising:

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

P 5 =D 23 ^D 22 ^D 21 ^D 19 ^D 18 ^D 17 ^D 16 ^D 15 ^D 14 ^D 13 ^D 12 ^D 11 ^D 10 ;

P 4 =D 23 ^D 22 ^D 20 ^D 19 ^D 18 ^D 17 ^D 16 ^D 9 ^D 8 ^D 7 ^D 6 ^D 5 ^D 4 ;

P 3 =D 23 ^D 21 ^D 20 ^D 19 ^D 18 ^D 17 ^D 16 ^D 9 ^D 8 ^D 7 ^D 3 ^D 2 ^D 1 ;

P 2 =D 22 ^D 21 ^D 20 ^D 18 ^D 15 ^D 12 ^D 11 ^D 9 ^D 6 ^D 5 ^D 3 ^D 2 ^D 0 ;

P 1 =D 23 ^D 22 ^D 21 ^D 20 ^D 17 ^D 14 ^D 12 ^D 10 ^D 8 ^D 6 ^D 4 ^D 3 ^D 1 ^D 0 ; and

P 0 =D 23 ^D 22 ^D 21 ^D 20 ^D 16 ^D 13 ^D 11 ^D 10 ^D 7 ^D 5 ^D 4 ^D 2 ^D 1 ^D 0 .

3. A machine implemented method of generating at least eight parity bits {P 0 , P 1 , P 2 . . . P 7 } corresponding to sixty four data bits {D 0 , D 1 , D 2 . . . D 63 }, said method comprising:

(i) calculating

P 7 =D 63 ^D 62 ^D 61 ^D 60 ^D 59 ^D 58 ^D 57 ^D 56 ^D 55 ^D 54 ^D 53 ^D 52 ^D 51 ^D 50 ^D 49 ^D 48 ^D 43 ^D 42 ^D 41 ^; ^D 40 ^D 39 ;

(ii) calculating

P 6 =D 63 ^D 62 ^D 61 ^D 60 ^D 59 ^D 58 ^D 47 ^D 46 ^D 38 ^D 37 ^D 36 ^D 35 ^D 34 ^D 33 ^D 32 ^D 31 ^D 30 ^D 29 ^D 28 ^; ^D 27 ^D 26 ^D 25 ^D 24 ;

(iii) calculating

P 5 =D 63 ^D 57 ^D 56 ^D 55 ^D 54 ^D 53 ^D 45 ^D 44 ^D 38 ^D 37 ^D 36 ^D 35 ^D 34 ^D 23 ^D 22 ^D 21 ^D 19 ^D 18 ^D 17 ^; ^D 16 ^D 15 ^D 14 ^D 13 ^D 12 ^D 11 ^D 10 ;

(iv) calculating

P 4 =D 62 ^D 57 ^D 52 ^D 51 ^D 50 ^D 49 ^D 47 ^D 45 ^D 44 ^D 38 ^D 33 ^D 32 ^D 31 ^D 30 ^D 23 ^D 22 ^D 20 ^D 19 ^D 18 ^D 17 ^D 16 ^D 9 ^D 8 ^D 7 ^D 6 ^D 5 ^D 4 ;

(v) calculating

P 3 =D 61 ^D 56 ^D 52 ^D 48 ^D 46 ^D 45 ^D 44 ^D 43 ^D 42 ^D 37 ^D 33 ^D 29 ^D 28 ^D 27 ^D 23 ^D 22 ^D 20 ^D 19 ^D 15 ^D 14 ^D 13 ^D 9 ^D 8 ^D 7 ^D 3 ^D 2 ^D 1 ;

(vi) calculating

P 2 =D 60 ^D 55 ^D 51 ^D 48 ^D 47 ^D 46 ^D 45 ^D 44 ^D 41 ^D 40 ^D 36 ^D 32 ^D 29 ^D 26 ^D 25 ^D 22 ^D 21 ^D 20 ^D 18 ^D 15 ^D 12 ^D 11 ^D 9 ^D 6 ^D 5 ^D 3 ^D 2 ^D 0 ;

(vii) calculating

P 1 =D 59 ^D 54 ^D 50 ^D 47 ^D 46 ^D 45 ^D 43 ^D 41 ^D 39 ^D 35 ^D 31 ^D 28 ^D 26 ^D 24 ^D 23 ^D 22 ^D 21 ^D 20 ^D 17 ^D 14 ^D 12 ^D 10 ^D 8 ^D 6 ^D 4 ^D 3 ^D 2 ^D 1 ^D 0 ; and

(viii) calculating

P 0 =D 58 ^D 53 ^D 49 ^D 47 ^D 46 ^D 44 ^D 42 ^D 40 ^D 39 ^D 34 ^D 30 ^D 27 ^D 25 ^D 24 ^D 23 ^D 22 ^D 21 ^D 20 ^D 16 ^D 13 ^D 11 ^D 10 ^D 7 ^D 5 ^D 4 ^D 2 ^D 1 ^D 0 .

4. A machine implemented method of generating at least six parity bits {P 0 , P 1 , P 2 . . . P 5 } corresponding to twenty four data bits {D 0 , D 1 , D 2 . . . D 23 }, said method comprising:

(i) calculating P 5 =D 23 ^D 22 ^D 21 ^D 19 ^D 18 ^D 17 ^D 16 ^D 15 ^D 14 ^D 13 ^D 12 ^D 11 ^D 10 ;

(ii) calculating P 4 =D 23 ^D 22 ^D 20 ^D 19 ^D 18 ^D 17 ^D 16 ^D 9 ^D 8 ^D 7 ^D 6 ^D 5 ^D 4 ;

(iii) calculating P 3 =D 23 ^D 21 ^D 20 ^D 19 ^D 15 ^D 14 ^D 13 ^D 9 ^D 8 ^D 7 ^D 3 ^D 2 ^D 1 ;

(iv) calculating P 2 =D 22 ^D 21 ^D 20 ^D 18 ^D 15 ^D 12 ^D 11 ^D 9 ^D 6 ^D 5 ^D 3 ^D 2 ^D 0 ;

(v) calculating P 1 =D 23 ^D 22 ^D 21 ^D 20 ^D 17 ^D 14 ^D 12 ^D 10 ^D 8 ^D 6 ^D 4 ^D 3 ^D 1 ^D 0 ; and

(vi) calculating P 0 =D 23 ^D 22 ^D 21 ^D 20 ^D 16 ^D 13 ^D 11 ^D 10 ^D 7 ^D 5 ^D 4 ^D 2 ^D 1 ^D 0 .

5. A parity bit generator for generating at least eight parity bits {P 0 , P 1 , P 2 . . . P 7 } corresponding to 64 data bits {D 0 , D 1 , D 2 . . . D 63 }, comprising:

(i) means for calculating

P 7 =D 63 ^D 62 ^D 61 ^D 60 ^D 59 ^D 58 ^ 57 ^D 56 ^ 55 ^D 64 ^D 53 ^D 52 ^D 51 ^D 50 ^D 49 ^D 48 ^D 43 ^D 42 ^D 41 ^D 40 ^D 39 ;

(ii) means for calculating

P 6 =D 63 ^D 62 ^D 61 ^D 60 ^D 59 ^D 58 ^ 47 ^D 46 ^ 38 ^D 37 ^D 36 ^D 35 ^D 34 ^D 33 ^D 32 ^D 31 ^D 30 ^D 29 ^D 28 ^D 27 ^D 26 ^D 25 ^D 24 ;

(iii) means for calculating

P 5 =D 23 ^D 22 ^D 21 ^D 19 ^D 18 ^D 17 ^D 16 ^D 15 ^D 14 ^D 13 ^D 12 ^D 11 ^D 10 ;

(iv) means for calculating

P 4 =D 62 ^D 57 ^D 52 ^D 51 ^D 50 ^D 49 ^D 47 ^D 45 ^D 44 ^D 38 ^D 33 ^D 32 ^D 31 ^D 30 ^D 23 ^D 22 ^D 20 ^D 19 ^D 18 ^D 17 ^D 16 ^D 9 ^D 8 ^D 7 ^D 6 ^D 5 ^D 4 ;

(v) means for calculating

P 3 =D 61 ^D 56 ^D 52 ^D 48 ^D 46 ^D 45 ^ 44 ^D 43 ^ 42 ^D 37 ^D 33 ^D 29 ^D 28 ^D 27 ^D 23 ^D 21 ^D 20 ^D 19 ^D 15 ^D 14 ^D 13 ^D 9 ^D 8 ^D 7 ^D 3 ^D 2 ^D 1 ;

(vi) means for calculating

P 2 =D 60 ^D 55 ^D 51 ^D 48 ^D 47 ^D 46 ^ 45 ^D 44 ^ 41 ^D 40 ^D 36 ^D 32 ^D 29 ^D 26 ^D 25 ^D 22 ^D 21 ^D 20 ^D 18 ^D 15 ^D 12 ^D 11 ^D 9 ^D 6 ^D 5 ^D 3 ^D 2 ^D 0 ;

(vii) means for calculating

P 1 =D 59 ^D 54 ^D 50 ^D 47 ^D 46 ^D 45 ^ 43 ^D 41 ^ 39 ^D 35 ^D 31 ^D 28 ^D 26 ^D 24 ^D 23 ^D 22 ^D 20 ^D 17 ^D 14 ^D 12 ^D 10 ^D 8 ^D 6 ^D 4 ^D 3 ^D 1 ^D 0 ; and

(viii) means for calculating

P 0 =D 58 ^D 53 ^D 49 ^D 47 ^D 46 ^D 44 ^D 42 ^D 40 ^D 39 ^D 34 ^D 30 ^D 27 ^D 25 ^D 24 ^D 23 ^D 22 ^D 21 ^D 20 ^D 16 ^D 13 ^D 11 ^D 10 ^D 7 ^D 5 ^D 4 ^D 2 ^D 1 ^D 0 .

6. A parity bit generator for generating at least six parity bits {P 0 , P 1 , P 2 . . . P 5 } corresponding to twenty four data bits {D 0 , D 1 , D 2 . . . D 23 }, comprising:

(i) means for calculating P 5 =D 23 ^D 22 ^D 21 ^D 19 ^D 18 ^D 17 ^D 16 ^D 15 ^D 14 ^D 13 ^D 12 ^D 11 ^D 10 ;

(ii) means for calculating P 4 =D 23 ^D 22 ^D 20 ^D 19 ^D 18 ^D 17 ^D 16 ^D 9 ^D 8 ^D 7 ^D 6 ^D 5 ^D 4 ;

(iii) means for calculating P 3 =D 23 ^D 21 ^D 20 ^D 19 ^D 15 ^D 14 ^D 13 ^D 9 ^D 8 ^D 7 ^D 3 ^D 2 ^D 1 ;

(iv) means for calculating P 2 =D 22 ^D 21 ^D 20 ^D 18 ^D 15 ^D 12 ^D 11 ^D 9 ^D 6 ^D 5 ^D 3 ^D 2 ^D 0 ;

(v) means for calculating P 1 =D 23 ^D 22 ^D 21 ^D 20 ^D 17 ^D 14 ^D 12 ^D 10 ^D 8 ^D 6 ^D 4 ^D 3 ^D 1 ^D 0 ; and and

(vi) means for calculating P 0 =D 23 ^D 22 ^D 21 ^D 20 ^D 16 ^D 13 ^D 11 ^D 10 ^D 7 ^D 5 ^D 4 ^D 2 ^D 1 ^D 0 .

Assignments (2)

CHANGE OF NAME Recorded Jan 25, 2012

From: ATI TECHNOLOGIES INC.

To: ATI TECHNOLOGIES ULC

Reel/Frame 027592/0381 →

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 24, 2009

From: GOMA, SERGIU; ALEKSIC, MILIVOJE

To: ATI TECHNOLOGIES INC.

Reel/Frame 023138/0823 →

Continuity (2)

Continuation 11236921 · Sep 28, 2005

Related Publication 20090313529A1 · Dec 17, 2009