Back to results
US 7,032,166 B2Granted
Method and apparatus for protecting data
AssigneeMassachusetts Institute of Technology
InventorsLeslie David Servi, Eushiuan T. Tsung, Joseph Anthony Cooley, Jeremy Mineweaser
Life of this patent
Estimating the term…
Abstract
In one aspect, a technique is provided for protecting a data set with a parity set defined by a bipartite graph having a degree distribution that includes no parity symbol having a degree less than three. In another aspect, a parity set defined by an irregular bipartite graph is transmitted along with the data set, and corruptions in the data set are decoded using the data set and the parity set. In another aspect, a particularly useful degree distribution for the parity symbols is defined.
Claims53
A method comprising an act of:
- a) protecting a data set that comprises a plurality of data bits with a parity set that comprises a plurality of parity bits, wherein the parity set and the data set have a relationship defined by a bipartite graph comprising a plurality of data points and a plurality of parity points, wherein each data point represents at least one of the plurality of data bits and each parity point represents at least one of the plurality of parity bits, wherein each one of the plurality of parity points has a degree that defines a number of data points to which the one of the plurality of parity points corresponds, the plurality of parity points being selected to have a first degree distribution that is substantially similar to a second degree distribution in which Nj defines a number of parity points of degree j, wherein Nj is equal to zero for values of j from 1 through j* plus 1, and wherein Nj satisfies the following formula for values of j from j* plus 2 to imax;
- ∑
- j
- =
- j
- *
- +
- 2
- imax
-
- N
- j
- =
- Int
-
- [
- s
-
- ∑
- j
- =
- j
- *
- +
- 2
- imax
-
- (
- p
-
-
- k
- j
- -
- j
- *
- -
- 1
- -
- p
-
-
- k
- +
- 1
- -
- A
-
- p
-
-
- k
- j
- -
- j
- *
- )
- ]
- wherein;
- p is a fraction of loss being protected against;
- k is a number of data points in the bipartite graph;
- imax defines a maximum possible degree for the parity points in the bipartite graph;
- s is a scaling factor;
- j* defines a degree of a lowest non-zero degree parity point minus two;
- and
- A is a variable.
63 more elements
At least one computer readable medium encoded with instructions that, when executed, perform a method comprising an act of:
- (a) protecting a data set that comprises a plurality of data bits with a parity set that comprises a plurality of parity bits, wherein the parity set and the data set have a relationship defined by a bipartite graph comprising a plurality of data points and a plurality of parity points, wherein each data point represents at least one of the plurality of data bits and each parity point represents at least one of the plurality of parity bits, wherein each one of the plurality of parity points has a degree that defines a number of data points to which the one of the plurality of parity points corresponds, the plurality of parity points being selected to have a first degree distribution that is substantially similar to a second degree distribution in which Nj defines a number of parity points of degree j, wherein Nj is equal to zero for values of j from 1 through j* plus 1, and wherein Nj satisfies the following formula for values of j from j* plus 2 to imax;
- ∑
- j
- =
- j
- *
- +
- 2
- imax
-
- N
- j
- =
- Int
-
- [
- s
-
- ∑
- j
- =
- j
- *
- +
- 2
- imax
-
- (
- p
-
-
- k
- j
- -
- j
- *
- -
- 1
- -
- p
-
-
- k
- +
- 1
- -
- A
-
- p
-
-
- k
- j
- -
- j
- *
- )
- ]
- wherein;
- p is a fraction of loss being protected against;
- k is a number of data points in the bipartite graph;
- imax defines a maximum possible degree for the parity points in the bipartite graph;
- s is a scaling factor;
- j* defines a degree of a lowest non-zero degree parity point minus two;
- and
- A is a variable.
63 more elements
An apparatus comprising:
- at least one of an encoder to encode a parity set for a data set and a decoder to decode at least a portion of the data set using the parity set;
- wherein the data set comprises a plurality of data bits and the parity set comprises a plurality of parity bits, and
- wherein the parity set and the data set have a relationship defined by a bipartite graph comprising a plurality of data points and a plurality of parity points, wherein each data point represents at least one of the plurality of data bits and each parity point represents at least one of the plurality of parity bits, wherein each one of the plurality of parity points has a degree that defines a number of data points to which the one of the plurality of parity points corresponds, the plurality of parity points being selected to have a first degree distribution that is substantially similar to a second degree distribution in which Nj defines a number of parity points of degree j, wherein Nj is equal to zero for values of j from 1 through j* plus 1, and wherein Nj satisfies the following formula for values of j from j* plus 2 to imax;
- ∑
- j
- =
- j
- *
- +
- 2
- imax
-
- N
- j
- =
- Int
-
- [
- s
-
- ∑
- j
- =
- j
- *
- +
- 2
- imax
-
- (
- p
-
-
- k
- j
- -
- j
- *
- -
- 1
- -
- p
-
-
- k
- +
- 1
- -
- A
-
- p
-
-
- k
- j
- -
- j
- *
- )
- ]
- wherein;
- p is a fraction of loss being protected against;
- k is a number of data points in the bipartite graph;
- imax defines a maximum possible degree for the parity points in the bipartite graph;
- s is a scaling factor;
- j* defines a degree of a lowest non-zero degree parity point minus two;
- and
- A is a variable.
65 more elements
A method comprising an act of:
- (a) protecting a data set that comprises a plurality of data bits with a parity set that comprises a plurality of parity bits, wherein the parity set and the data set have a relationship defined by a bipartite graph comprising a plurality of data points and a plurality of parity points, wherein each data point represents at least one of the plurality of data bits and each parity point represents at least one of the plurality of parity bits, wherein each one of the plurality of parity points has a degree that defines a number of data points to which the one of the plurality of parity points corresponds, the plurality of parity points being selected to have a degree distribution that includes no parity point having a degree less than three.
At least one computer readable medium encoded with instructions that, when executed, perform a method comprising an act of:
- (a) protecting a data set that comprises a plurality of data bits with a parity set that comprises a plurality of parity bits, wherein the parity set and the data set have a relationship defined by a bipartite graph comprising a plurality of data points and a plurality of parity points, wherein each data point represents at least one of the plurality of data bits and each parity point represents at least one of the plurality of parity bits, wherein each one of the plurality of parity points has a degree that defines a number of data points to which the one of the plurality of parity points corresponds, the plurality of parity points being selected to have a degree distribution that includes no parity point having a degree less than three.
An apparatus comprising:
- at least one of an encoder to encode a parity set for a data set and a decoder to decode at least a portion of the data set using the parity set;
- wherein the data set comprises a plurality of data bits and the parity set comprises a plurality of parity bits, and
- wherein the parity set and the data set have a relationship defined by a bipartite graph comprising a plurality of data points and a plurality of parity points, wherein each data point represents at least one of the plurality of data bits and each parity point represents at least one of the plurality of parity bits, wherein each one of the plurality of parity points has a degree that defines a number of data points to which the one of the plurality of parity points corresponds, the plurality of parity points being selected to have a degree distribution that includes no parity point having a degree less than three.
Dependencies are inferred from the claim text.