# US 2006/0156178 A1 · Data error control

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0156178 A1
- Document ID: US20060156178A1
- Status: Published application
- Kind: A1
- Application number: 11/187,737
- Filed: 2005-07-22
- Published: 2006-07-13
- Earliest claimed: 2004-07-22
- Assignees: SeaChange International, Inc.
- Inventors: Xiaobing Lee; David Agans; Bruce Mann
- Web page: https://patentgrep.com/patent/US20060156178A1

## CPC

- H04L 1/0045: {Arrangements at the receiver end}
- G06F 11/1092: {Rebuilding, e.g. when physically replacing a failing disk}
- H03M 13/11: using multiple parity bits
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- H03M 13/3746: {with iterative decoding}
- H04L 1/0041: {Arrangements at the transmitter end}
- H04L 1/0057: {Block codes (H04L1/0061, H04L1/0064 take precedence)}
- H04L 2001/0096: {Channel splitting in point-to-point links}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Multiple corruptions and/or erasures in data storage or data communication systems are corrected. An encoder generates M of parity fields from N data channels. Each item of the generated parity fields is the result of simple exclusive-or operations on one item from one or more data fields and possibly one item from one or more of the other parity fields. A decoder can regenerate as many as M missing or corrupted fields of either data or parity using combinations of correct and/or previously corrected items as inputs using M independent parity equations to solve for and correct each missing or corrupted item in turn.

## Claims

### Claim 1

A method for data error correction comprising:
receiving at least some channels of N+M channels of encoded data that represent N channels of source data, wherein each channel of the N+M channels of encoded data includes a series of entries, the N+M channels of encoded data satisfying parity equations such at least some entries contribute to M of the parity equations; and
iteratively reconstructing entries of one or more channels of the N+M channels of encoded data, at each iteration applying one or more of the parity equations to received or reconstructed entries of the N+M channels of encoded data to reconstruct an entry in each of the one or more of the N+M channels.

### Claim 2 (depends on 1)

The method of claim 1 wherein iteratively reconstructing the entries includes reconstructing entries in two or more of the channels.

### Claim 3 (depends on 2)

The method of claim 2 wherein at each iteration, reconstructing at least some of the entries in the two or more channels uses an entry in another of the two or more channels reconstructed in that iteration.

### Claim 4 (depends on 2)

The method of claim 2 wherein reconstructing each entry includes applying a single one of the parity equations to received or reconstructed entries.

### Claim 5 (depends on 4)

The method of claim 4 wherein reconstructing at least some entries includes applying a parity equation to a reconstructed entry.

### Claim 6 (depends on 1)

The method of claim 1 wherein iteratively reconstructing the entries includes at each iteration reconstructing an entry in one of the one or more channels to be reconstructed using a combination of the parity equations which combination is independent of entries in at least one other of the one or more channels to be reconstructed.

### Claim 7 (depends on 6)

The method of claim 6 wherein the combination of parity equations is independent of entries in all others of the one or more channels to be reconstructed.

### Claim 8 (depends on 7)

The method of claim 7 wherein the one or more channels to be reconstructed includes M channels to be reconstructed, and the combination of parity equations is independent of entries in M−1 of the channels.

### Claim 9 (depends on 1)

The method of claim 1 further comprising determining channels of the N+M channels that were not received, and iteratively reconstructing entries in the one or more channels includes reconstructing entries in channels that were not received.

### Claim 10 (depends on 1)

The method of claim 1 further comprising detecting errors in entries in the received channels, and iteratively reconstructing entries in the one or more channels includes reconstructing entries in channels in which the errors were detected.

### Claim 11

A method for data error correction comprising:
receiving at least some channels of N+M channels of encoded data that represent N channels of source data, wherein each channel of the N+M channels of encoded data includes a series of entries, the N+M channels of encoded data satisfying parity equations such that each entry in at least some of the N+M channels of encoded data contributes to at least some of the parity equations; and
reconstructing at least two of the N+M channels from the received channels, including forming combinations of the parity equations to reconstruct entries in the channels being reconstructed, each combination of parity equations being independent of all entries in at least some of the channels being reconstructed.

### Claim 12 (depends on 11)

The method of claim 11 reconstructing the at least two channels includes reconstructing each of the at least two channels independently of other of the at least two channels.

### Claim 13 (depends on 12)

The method of claim 12 wherein reconstructing the at least two channels includes reconstructing said channels concurrently.

### Claim 14 (depends on 12)

The method of claim 12 wherein reconstructing the at least two channels includes reconstructing said channels in sequence.

### Claim 15

A method for data error correction comprising:
receiving encoded data, including receiving at least N channels of encoded data of N+M channels of encoded data that represent N channels of source data; and
correcting errors in the received encoded data, including using the received at least N channels of encoded data to correct errors in at least m>M/2 other of the channels of encoded data;
wherein each channel of the N+M channels of encoded data including a series of entries, the channels of encoded data satisfying parity equations such that each entry in at least some of the N+M channels of encoded data contributes to at least M independent parity equations.

### Claim 16 (depends on 15)

The method of claim 15 wherein correcting errors in the received encoded data includes using the received at least N channels of encoded data to correct errors in M other of the channels of encoded data.

### Claim 17 (depends on 15)

The method of claim 15 wherein M is at least three.

### Claim 18 (depends on 17)

The method of claim 17 wherein M is at least four.

### Claim 19 (depends on 18)

The method of claim 18 wherein M is at least five.

### Claim 20 (depends on 15)

The method of claim 15 wherein receiving the at least N channels of encoded data includes receiving said channels without error.

### Claim 21 (depends on 15)

The method of claim 15 wherein receiving the encoded data includes receiving one or more channels other than the received N channels with errors.

### Claim 22 (depends on 21)

The method of claim 21 wherein receiving the one or more channels with errors includes receiving said channels with substitution errors.

### Claim 23 (depends on 21)

The method of claim 21 wherein receiving the one or more channels with errors includes receiving said channels with erasure errors.

### Claim 24 (depends on 15)

The method of claim 15 wherein receiving the encoded data includes not receiving one or more channels other than the received N channels.

### Claim 25 (depends on 15)

The method of claim 15 wherein correcting the errors in the received encoded data includes determining a set of error-free channels, the set of error-free channels including at least N channels of encoded data that were received without error.

### Claim 26 (depends on 15)

The method of claim 15 wherein correcting the errors further includes determining entries in a set of repaired channels, the set of repaired channels being distinct from the set of error-free channels.

### Claim 27 (depends on 15)

The method of claim 15 wherein correcting the errors further includes determining entries in a set of repaired channels, including applying the parity equations to entries in the set of channels of encoded data that were received without error to determine entries in a corrected set of channels of data, the corrected set of channels not in the set of channels of encoded data that were received without error.

### Claim 28 (depends on 27)

The method of claim 27 wherein applying the parity equations to entries in the set of channels includes iterating over successive entries in the series of entries in at least one of the repaired channels.

### Claim 29 (depends on 28)

The method of claim 28 wherein iterating over the successive entries includes, for each successive entry, applying at least one of the parity equations to determine said entry.

### Claim 30 (depends on 15)

The method of claim 15 wherein correcting the errors further includes iterating over entries in the least m other channels of encoded data.

### Claim 31 (depends on 30)

The method of claim 30 wherein iterating over the entries includes iteratively determining each entry using one or more of the parity equations.

### Claim 32 (depends on 31)

The method of claim 31 wherein determining each entry using one or more of the parity equations includes using one or more of the parity equations in a combination that does not depend on one or more of the at least m other channels of encoded data.

### Claim 33

A data decoder comprising:
an input for receiving at least some of N+M channels of encoded data, the channels representing N channels of source data and satisfying parity processes such that at least some of the entries contribute to M of the parity equations;
a data processor configured to iteratively reconstruct entries of one or more of the N+M channels of encoded data, including, at each iteration, applying one or more of the parity equations to reconstruct at least one of the entries in each of the one or more of the N+M channels.

### Claim 34

Software stored on computer-readable media comprising instructions for causing a data processing system to:
in successive iterations, reconstruct entries of one or more of N+M channels of encoded data, the channels representing N channels of source data and satisfying parity processes such that at least some of the entries contribute to M of the parity equations, and
at each iteration, applying one or more of the parity equations to reconstruct at least one of the entries in each of the one or more of the N+M channels.

### Claim 35

A method for data error protection comprising:
accepting source data;
representing the source data as N channels of source data, each including a series of I entries; and
encoding the N channels of source data to form N+M channels of encoded data, the channels of encoded data satisfying at least M×I independent parity equations, at least I entries of some of the channels of encoded data each being an argument to at least M of the parity equations.

### Claim 36 (depends on 35)

The method of claim 35 wherein encoding the N channels includes augmenting the N channels of source data with M channels of parity data, each including a series of at least I entries.

### Claim 37 (depends on 36)

The method of claim 36 wherein each entry of the N channels of source data is an argument to M of the parity equations.

### Claim 38 (depends on 36)

The method of claim 36 wherein in at least some of the M channels of parity data at least I entries in the channel are each an argument to at least 2 of the parity equations.

### Claim 39 (depends on 38)

The method of claim 38 wherein in at least some of the M channels of parity data at least I entries in the channel are each an argument to at least M of the parity equations

### Claim 40 (depends on 36)

The method of claim 36 wherein each channel of parity data is associated with a class of parity equations, the class of parity equations being associated with a set of the N+M channels that contribute arguments to the parity equations and relative offsets of entries in the channels that contribute to any of the equations in the class.

### Claim 41 (depends on 40)

The method of claim 40 wherein the offsets for at least some of the classes of parity equations are such that the relative offsets of the entries form a diagonal line across the N channels of source data when arranged as an array of N columns by I rows.

### Claim 42 (depends on 35)

The method of claim 35 wherein representing the source data as N channels of source data includes concatenating a series of extra entries with the series of I entries.

### Claim 43 (depends on 42)

The method of claim 42 wherein encoding the N channels of source data to form N+M channels of encoded data includes applying at least some of the parity equations to extra entries and entries representing the source data to determine entries of the encoded data.

### Claim 44 (depends on 42)

The method of claim 42 wherein the extra entries have zero values.

### Claim 45 (depends on 42)

The method of claim 42 wherein encoding the data further includes determining the extra entries as a key to the encoded data.

### Claim 46 (depends on 35)

The method of claim 35 wherein the encoding of the data enables reconstruction of the source data from any N of the N+M channels of encoded data.

### Claim 47 (depends on 35)

The method of claim 35 wherein the encoding of the data enables detection of errors in M−1 of the N+M channels of encoded data.

### Claim 48 (depends on 35)

The method of claim 35 wherein accepting the source data includes accepting the source data as one or more data streams, representing the one or more data streams as N channels, and encoding the data includes processing the accepted data using a cross-convolutional encoding approach across the N channels to produce the N+M channels of encoded data as a stream of data.

### Claim 49 (depends on 35)

The method of claim 35 wherein any two of the parity equations share at most one entry of the N+M channels as an argument.

### Claim 50

Software stored on computer-readable media comprising instructions for causing a data processing system to:
accept source data;
represent the source data as N channels of source data, each including a series of I entries; and
encode the N channels of source data to form N+M channels of encoded data, the channels of encoded data satisfying at least M×I independent parity equations, at least I entries of some of the channels of encoded data each being an argument to at least M of the parity equations.

### Claim 51

A method for data error protection comprising:
accepting source data;
representing the source data as N channels of source data, each including a series of I entries;
encoding the N channels of source data to form N+M channels of encoded data, the channels of encoded data satisfying at least M×I independent parity equations, at least I entries of some of the channels of encoded data each being an argument to at least M of the parity equations; and
handling the N+M channels of encoded data;
iteratively reconstructing entries in one or more channels of the N+M channels of encoded data, at each iteration applying one or more of the parity equations to received or reconstructed entries of the N+M channels of encoded data to reconstruct an entry in each of the one or more of the N+M channels; and
recovering the source data using the reconstructed entries.

### Claim 52

A method for data error control comprising:
accepting source data;
representing the source data as N channels of source data, each including a series of I entries;
encoding the N channels of source data to form N+M channels of encoded data, the channels of encoded data satisfying at least M×I independent parity equations, at least I entries of some of the channels of encoded data each contributing to at least M of the parity equations;
handling the N+M channels of encoded data, including introducing errors into at least m>M/2 of the N+M channels; and
recovering the source data from the handled channels of encoded data.

### Claim 53 (depends on 51)

The method of claim 51 wherein encoding the N channels includes augmenting the N channels of source data with M channels of parity data.

### Claim 54 (depends on 51)

The method of claim 51 wherein handling includes transmitting the channels over different paths.

### Claim 55 (depends on 54)

The method of claim 54 wherein transmitting the channels over different paths includes transmitting the channels over different communication links.

### Claim 56 (depends on 54)

The method of claim 54 wherein transmitting the channels over different paths includes transmitting the channels at different times.

### Claim 57 (depends on 54)

The method of claim 54 wherein transmitting the channels over different paths includes transmitting the channels in different packets.

### Claim 58 (depends on 51)

The method of claim 51 wherein handling includes storing the channels in different storage devices.

### Claim 59 (depends on 51)

The method of claim 51 wherein recovering the source data includes correcting errors in the handled channels of encoded data, including using least N channels of encoded data to correct errors in at least m>M/2 other of the channels of encoded data.

### Claim 60

A method for distributed storage of data comprising:
accepting source data;
representing the source data as N channels of source data, each including a series of I entries;
encoding the N channels of source data to form N+M channels of encoded data, the channels of encoded data satisfying at least M×I independent parity equations, at least I entries of some of the channels of encoded data each being an argument to at least M of the parity equations; and
distributing the N+M channels of encoded data to separate storages;
retrieving at least some of the N+M channels of encoded data from the separate storages;
iteratively reconstructing entries in one or more channels of the N+M channels of encoded data using the retrieved channels, at each iteration applying one or more of the parity equations to received or reconstructed entries of the N+M channels of encoded data to reconstruct an entry in each of the one or more of the N+M channels; and
recovering the source data using the reconstructed entries.
