Browse Prior Art Database

XRS: A System and Method to Compute Reed-Solomon Codes for Storage Systems Using XORs

IP.com Disclosure Number: IPCOM000022471D
Original Publication Date: 2004-Mar-17
Included in the Prior Art Database: 2004-Mar-17
Document File: 3 page(s) / 132K

Publishing Venue

IBM

Abstract

A system and method is disclosed for converting certain Reed-Solomon codes into binary XOR codes for use in storage systems.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 43% of the total text.

Page 1 of 3

XRS: A System and Method to Compute Reed-Solomon Codes for Storage Systems Using XORs

Jim Hafner, Jeff Hartline, Tapas Kanungo

Disclosed is a system and method to compute Reed-Solomon error correcting and erasure codes
[1] using a simple XOR engine for use in disk array storage devices. The general methodology is to convert the RS (Reed-Solomon) code equations from formulas defined over a finite/Galois field, GF(2k), to binary-based XOR parity equations. Generally, arithmetic (especially multiplication) in finite fields is somewhat difficult to implement and is generally done either using lookup tables (of discrete logarithms to convert multiplication to addition of exponents) or using special purpose hardware. The symbols are typically k-bit wide where k is the parameter defining the size of the finite field. Computation of RS code redundancy (and error correction) involves computation of polynomials whose coefficients are the data symbols and whose variables are fixed elements in the field. That is, it involves multiplication of arbitrary data symbols by fixed symbols. The present method has two features. First it converts this multiplication into a binary matrix/vector multiplication; each row of the matrix represents an XOR computation of a subset of the elements of the vector. The matrix represents the fixed symbols and the vector represents a data symbol. Second, once it is represented by XOR computations, the symbols or k-ary bit vectors can be represented by k-ary vectors of arbitrary sized elements (not just bits but bytes, words, disk sectors, cache pages, etc.); each bit in the vector can now represent a larger unit of data. Selection of the size of this unit is not a part of this present method, though the specifics of the XOR engine (e.g., is it special purpose hardware, or a general purpose processor?) as well as other considerations of the application are contributing factors to this decision.

The reader is referred to [1] for the construction of RS codes in general. For the present description, it suffices to observe that any construction of RS code of distance d can be completely described by a generator matrix in the form

In Pn,(d-1)

1 0 ... 0 c1,1 c2,1 ... cd-1,1

0 1 0 0 c1,2 c2,2 ... cd-1,2

               ... ... ... ... ... ... ... ...
0 0 ... 1 c1,n c2,n ... cd-1,n where the ci,jare elements in the finite field, that is, powers of β, a generator for the field. The code now takes n data inputs, represented as an n-ary vector X=(x1,...,xn) of elements in the finite field and computes the product X*G=(x1,...,xn,R1,..,Rd-1), where each redundancy value Rj is the dot product of the input vector X and the jth column of Pn,(d-1). All arithmetic in this product is done over the finite field GF(2k).

The present method is a means to convert both the generator matrix and the input vector representation of the data inputs into binary objects and so convert the computation of the generator matrix into simple XOR equations. This is don...