×

Multiply redundant raid system and XOR-efficient method and apparatus for implementing the same

  • US 20060218470A1
  • Filed: 03/15/2005
  • Published: 09/28/2006
  • Est. Priority Date: 03/15/2005
  • Status: Active Grant
First Claim
Patent Images

1. A method for encoding input data including d data symbols (b0, b1, . . . bd−

  • 1) to generate coded data having d+m symbols, each symbol consisting of N bits, where d is an integer greater than 1, m is an integer greater than 3, N is an integer greater than 1, and s is an integer, the method comprising;

    (a) receiving the d data symbols;

    (b) calculating m parity symbols from the d data symbols, wherein each k-th parity symbol for integer k between 0 and m−

    1 is calculated by evaluating a parity polynomial pb

    (x)
    =

    i=0d-1


    bi

    xi
    atx=α

    s+k
    ,
    where α

    is a primitive element of a finite field FN of dimension N over the bit field {0,1}, all N-bit symbols being mapped onto the field FN by a mapping which is a vector space isomorphism over {0,1} using bitwise AND and XOR operations, such that for every integer M between 1 and min(m,d) inclusive, and every ordered subset of M−

    1 integers {i2, . . . iM} between 1 and d−

    1, and every ordered subset of M=31 1 integers {j2, . . . jM} between 1 and m−

    1, the determinant of the matrix (11

    1
    1α

    i2

    j2


    α

    iM

    j2
















    1α

    i2

    jM


    α

    iM

    jM
    )


    is nonzero in the field FN; and

    (c) storing or transmitting the d data symbols and the m parity symbols as the d+m symbols of the coded data.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×