IP Library › Granted Patent US 7,539,929
Granted Patent B1
US 7,539,929 · App. 11/154,886 · Granted May 26, 2009

Error correction for data communication

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 7,539,929
App. No.
11/154,886
Granted
May 26, 2009
Kind
B1
Abstract

Generating a check matrix includes defining a generator function operable to yield check bits associated with a word. A set of primitive elements is calculated from the generator function. A set of check matrix columns is generated, where each check matrix column includes a matrix having a subset of the set of primitive elements. A check matrix is generated from a subset of the set of check matrix columns, where the check matrix yields a syndrome that comprises an error pattern for the word. The check matrix is reported.

Claims (263)

1. A method for performing error correction, comprising:

receiving a vector including shuffled symbols from a plurality of code words;

rearranging the shuffled symbols to form a code word comprising a word and a plurality of check bits, the word comprising a plurality of symbols;

generating a syndrome from the check bits, the syndrome comprising an error pattern;

identifying a symbol of the word having an error; and

correcting the error of the symbol according to the error pattern.

2. The method of claim 1 , further comprising:

generating the code word by multiplying the word and a generation matrix; and

transmitting the code word.

3. The method claim 1 , wherein identifying the symbol having the error comprises:

selecting a portion of the syndrome; and

searching a lookup table according to the portion to identify the symbol.

4. The method of claim 1 , wherein correcting the error of the symbol according to the error pattern comprises performing an exclusive-or operation on the symbol and the error pattern.

5. The method of claim 1 , further comprising identifying a check bit having an error.

6. The method of claim 1 , wherein generating a syndrome from the check bits comprises generating the syndrome using a check matrix comprising sixteen rows comprising:

Row

Entries

1

10001000100010001000100010001000100000000000000000000000000000

00000000001100101100010011010001100010111011010001010011111100

100111101010001000111000000000000000

2

01000100010001000100010001000100010000000000000000000000000000

00000000000010111010011010011001010011000110111001011010000010

110100010111001110100100000000000000

3

00100010001000100010001000100010001000000000000000000000000000

00000000000001111101001101001110101001100001010100001111000001

011010001011100111010010000000000000

4

00010001000100010001000100010001000100000000000000000000000000

00000000001000011100100110100111010100110010100010100111101000

001111000101010001100001000000000000

5

00010100111111001001111010100010001110001000100010001000100010

00100010000000000000000000000000000000000000001100101100010011

010001100010111011010000100000000000

6

10010110100000101101000101110011101001000100010001000100010001

00010001000000000000000000000000000000000000000010111010011010

011001010011000110110000010000000000

7

01000011110000010110100010111001110100100010001000100010001000

10001000100000000000000000000000000000000000000001111101001101

001110101001100001010000001000000000

8

00101001111010000011110001010100011000010001000100010001000100

01000100010000000000000000000000000000000000001000011100100110

100111010100110010100000000100000000

9

11001011000100110100011000101110110100010100111111001001111010

10001000111000100010001000100010001000100010000000000000000000

000000000000000000000000000010000000

10

00101110100110100110010100110001101110010110100000101101000101

11001110100100010001000100010001000100010001000000000000000000

000000000000000000000000000001000000

11

00011111010011010011101010011000010101000011110000010110100010

11100111010010001000100010001000100010001000100000000000000000

000000000000000000000000000000100000

12

10000111001001101001110101001100101000101001111010000011110001

01010001100001000100010001000100010001000100010000000000000000

000000000000000000000000000000010000

13

00000000000000000000000000000000000011001011000100110100011000

10111011010001010011111100100111101010001000111000100010001000

100010001000100010000000000000001000

14

00000000000000000000000000000000000000101110100110100110010100

11000110111001011010000010110100010111001110100100010001000100

010001000100010001000000000000000100

15

00000000000000000000000000000000000000011111010011010011101010

01100001010100001111000001011010001011100111010010001000100010

001000100010001000100000000000000010

16

00000000000000000000000000000000000010000111001001101001110101

00110010100010100111101000001111000101010001100001000100010001

000100010001000100010000000000000001

7. A system for performing error connection, comprising:

an input operable to receive a vector including a plurality of shuffled symbols from a plurality of code words;

a symbol sorter operable to rearrange the shuffled symbols to form a code word comprising a word and a plurality of check bits, the word comprising a plurality of symbols;

a syndrome generator coupled to the input and operable to generate a syndrome from the check bits, the syndrome comprising an error pattern;

a lookup table coupled to the syndrome generator and operable to identify a symbol of the word having an error; and

an error corrector coupled to the lookup table and operable to correct the error of the symbol according to the error pattern.

8. The system of claim 7 , further comprising:

a check bit generator operable to generate the code word by multiplying the word and a generation matrix; and

an output coupled to the check bit generator and operable to transmit the code word.

9. The system of claim 7 , wherein the lookup table is operable to identify the symbol having the error by:

selecting a portion of the syndrome; and

searching a lookup table according to the portion to identify the symbol.

10. The system of claim 7 , wherein error corrector is operable to correct the error of the symbol according to the error pattern by performing and exclusive-or operation on the symbol and the error pattern.

11. The system of claim 7 , wherein the syndrome generator is operable to identify a check bit having an error.

12. The system of claim 7 , wherein the syndrome generator is operable to generate the syndrome using a check matrix comprising sixteen rows comprising:

Row

Entries

1

10001000100010001000100010001000100000000000000000000000000000

00000000001100101100010011010001100010111011010001010011111100

100111101010001000111000000000000000

2

01000100010001000100010001000100010000000000000000000000000000

00000000000010111010011010011001010011000110111001011010000010

110100010111001110100100000000000000

3

00100010001000100010001000100010001000000000000000000000000000

00000000000001111101001101001110101001100001010100001111000001

011010001011100111010010000000000000

4

00010001000100010001000100010001000100000000000000000000000000

00000000001000011100100110100111010100110010100010100111101000

001111000101010001100001000000000000

5

00010100111111001001111010100010001110001000100010001000100010

00100010000000000000000000000000000000000000001100101100010011

010001100010111011010000100000000000

6

10010110100000101101000101110011101001000100010001000100010001

00010001000000000000000000000000000000000000000010111010011010

011001010011000110110000010000000000

7

01000011110000010110100010111001110100100010001000100010001000

10001000100000000000000000000000000000000000000001111101001101

001110101001100001010000001000000000

8

00101001111010000011110001010100011000010001000100010001000100

01000100010000000000000000000000000000000000001000011100100110

100111010100110010100000000100000000

9

11001011000100110100011000101110110100010100111111001001111010

10001000111000100010001000100010001000100010000000000000000000

000000000000000000000000000010000000

10

00101110100110100110010100110001101110010110100000101101000101

11001110100100010001000100010001000100010001000000000000000000

000000000000000000000000000001000000

11

00011111010011010011101010011000010101000011110000010110100010

11100111010010001000100010001000100010001000100000000000000000

000000000000000000000000000000100000

12

10000111001001101001110101001100101000101001111010000011110001

01010001100001000100010001000100010001000100010000000000000000

000000000000000000000000000000010000

13

00000000000000000000000000000000000011001011000100110100011000

10111011010001010011111100100111101010001000111000100010001000

100010001000100010000000000000001000

14

00000000000000000000000000000000000000101110100110100110010100

11000110111001011010000010110100010111001110100100010001000100

010001000100010001000000000000000100

15

00000000000000000000000000000000000000011111010011010011101010

01100001010100001111000001011010001011100111010010001000100010

001000100010001000100000000000000010

16

00000000000000000000000000000000000010000111001001101001110101

00110010100010100111101000001111000101010001100001000100010001

000100010001000100010000000000000001

13. A hardware-based logic for performing error corrections comprising:

a logic embodied in a hardware medium and operable to:

receive a vector including a plurality of shuffled symbols from a plurality of code words;

rearrange the shuffled symbols to form a code word comprising a word and a plurality of check bits, the word comprising a plurality of symbols;

generate a syndrome from the check bits, the syndrome comprising an error pattern;

identify a symbol of the word having an error; and

correct the error of the symbol according to the error pattern.

14. The hardware-based logic of claim 13 , wherein the logic embodied in the hardware medium is further operable to:

generate the code word by multiplying the word and a generation matrix; and

transmit the code word.

15. The hardware-based logic of claim 13 , wherein the operation to identify the symbol having the error comprises:

selecting a portion of the syndrome; and

searching a lookup table according to the portion to identify the symbol.

16. The hardware-based logic of claim 13 , wherein the operation to correct the error of the symbol according to the error pattern comprises:

performing an exclusive-or operation on the symbol and the error pattern.

17. The hardware-based logic of claim 13 , wherein the logic embodied in the hardware medium further comprises an operation to:

identify a check bit having an error.

18. The hardware-based logic of claim 13 , wherein the syndrome is generated using a check matrix comprising sixteen rows comprising:

Row

Entries

1

10001000100010001000100010001000100000000000000000000000000000

00000000001100101100010011010001100010111011010001010011111100

100111101010001000111000000000000000

2

01000100010001000100010001000100010000000000000000000000000000

00000000000010111010011010011001010011000110111001011010000010

110100010111001110100100000000000000

3

00100010001000100010001000100010001000000000000000000000000000

00000000000001111101001101001110101001100001010100001111000001

011010001011100111010010000000000000

4

00010001000100010001000100010001000100000000000000000000000000

00000000001000011100100110100111010100110010100010100111101000

001111000101010001100001000000000000

5

00010100111111001001111010100010001110001000100010001000100010

00100010000000000000000000000000000000000000001100101100010011

010001100010111011010000100000000000

6

10010110100000101101000101110011101001000100010001000100010001

00010001000000000000000000000000000000000000000010111010011010

011001010011000110110000010000000000

7

01000011110000010110100010111001110100100010001000100010001000

10001000100000000000000000000000000000000000000001111101001101

001110101001100001010000001000000000

8

00101001111010000011110001010100011000010001000100010001000100

01000100010000000000000000000000000000000000001000011100100110

100111010100110010100000000100000000

9

11001011000100110100011000101110110100010100111111001001111010

10001000111000100010001000100010001000100010000000000000000000

000000000000000000000000000010000000

10

00101110100110100110010100110001101110010110100000101101000101

11001110100100010001000100010001000100010001000000000000000000

000000000000000000000000000001000000

11

00011111010011010011101010011000010101000011110000010110100010

11100111010010001000100010001000100010001000100000000000000000

000000000000000000000000000000100000

12

10000111001001101001110101001100101000101001111010000011110001

01010001100001000100010001000100010001000100010000000000000000

000000000000000000000000000000010000

13

00000000000000000000000000000000000011001011000100110100011000

10111011010001010011111100100111101010001000111000100010001000

100010001000100010000000000000001000

14

00000000000000000000000000000000000000101110100110100110010100

11000110111001011010000010110100010111001110100100010001000100

010001000100010001000000000000000100

15

00000000000000000000000000000000000000011111010011010011101010

01100001010100001111000001011010001011100111010010001000100010

001000100010001000100000000000000010

16

00000000000000000000000000000000000010000111001001101001110101

00110010100010100111101000001111000101010001100001000100010001

000100010001000100010000000000000001

19. A system for performing error correction, comprising:

means for receiving a vector including a plurality of shuffled symbols from a plurality of code words;

means for rearranging the plurality of shuffled symbols to form a code word comprising a word and a plurality of check bits, the word comprising a plurality of symbols;

means for generating a syndrome from the check bits, the syndrome comprising an error pattern;

means for identifying a symbol of the word having an error; and

means for correcting the error of the symbol according to the error pattern.

20. A method for performing error correction, comprising:

generating a code word by multiplying a word and a generation matrix, the code word comprising the word and a plurality of check bits, the word comprising a plurality of symbols;

shuffling the symbols from the code word and one or more other code words;

transmitting a vector including the shuffled symbols;

receiving the vector;

rearranging the shuffled symbols to form the code word;

generating a syndrome from the check bits, the syndrome comprising an error pattern;

identifying a symbol of the word having an error by;

selecting a portion of the syndrome; and

searching a lookup table according to the portion to identify the symbol; and

correcting the error of the symbol according to the error pattern by performing an exclusive-or operation on the symbol and the error pattern.

Assignments (6)
RELEASE OF SECURITY INTEREST Recorded Jan 22, 2015
From: WELLS FARGO BANK, NATIONAL ASSOCIATION, AS COLLATERAL AGENT
To: BROCADE COMMUNICATIONS SYSTEMS, INC.; FOUNDRY NETWORKS, LLC
Reel/Frame 034804/0793 →
RELEASE OF SECURITY INTEREST Recorded Jan 21, 2015
From: BANK OF AMERICA, N.A., AS ADMINISTRATIVE AGENT
To: BROCADE COMMUNICATIONS SYSTEMS, INC.; INRANGE TECHNOLOGIES CORPORATION; FOUNDRY NETWORKS, LLC
Reel/Frame 034792/0540 →
SECURITY AGREEMENT Recorded Jan 20, 2010
From: BROCADE COMMUNICATIONS SYSTEMS, INC.; FOUNDRY NETWORKS, LLC; INRANGE TECHNOLOGIES CORPORATION; MCDATA CORPORATION; MCDATA SERVICES CORPORATION
To: WELLS FARGO BANK, NATIONAL ASSOCIATION, AS COLLATERAL AGENT
Reel/Frame 023814/0587 →
SECURITY AGREEMENT Recorded Dec 22, 2008
From: BROCADE COMMUNICATIONS SYSTEMS, INC.; FOUNDRY NETWORKS, INC.; INRANGE TECHNOLOGIES CORPORATION; MCDATA CORPORATION
To: BANK OF AMERICA, N.A. AS ADMINISTRATIVE AGENT
Reel/Frame 022012/0204 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 19, 2007
From: SANERA SYSTEMS, INC.
To: BROCADE COMMUNICATIONS SYSTEMS, INC.
Reel/Frame 020271/0577 →
CORRECTIVE ASSIGNMENT TO CORRECT THE APPLICATION SERIAL NUMBER AND APPLICATION FILING DATE PREVIOUSLY RECORDED ON REEL 018753 FRAME 0505. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNMENT OF THE ENTIRE RIGHT, TITLE AND INTEREST AS RECITED IN THE ORIGINAL ASSIGNMENT DOCUMENT.. Recorded Jan 18, 2007
From: STERN, ULRICH; CHAMDANI, JOSEPH I; FANG, YU; YANG, LIUXI
To: SANERA SYSTEMS INC., A DELAWARE CORPORATION
Reel/Frame 018770/0744 →