A Study for the Reed-Solomon Cod

作者: 早安我的猫咪 | 来源:发表于2018-10-23 16:04 被阅读13次

Introduction

Reed-Solomon (RS) code is an error-correcting code first proposed
by Reed and Solomon in 1960, which is the most frequently applied digital error correction code around the word. The applications include data storage(hard drives, CD/DVD/Blue Ray), data transmission and common commercial activities(bar codes, QR codes) .
RS code has the advantage of high capability of correcting random or burst errors since it encodes groups of bits instead of one bit at a time. Redundant datas are generated so that the original data can be reconstructed with part of the stored or received data loss. People often back up important files which can be regarded as kind of data loss protection with redundant data. However, backup is just a copy of the original datas while the redundant data generated in the RS code is a fusion of the all the original data parts, which is more efficient for storage and error correction.
In this article, I have run through the procedure of the RS code and hope it is usefull for you to understand what is going on with this erasure code. Its application in the distributed strorage system are briefly introduced at the end. Part of implementations in pure Go are also provided whose source files can be found on the Githup website .

Galois Field

The finite field is also called Galois field which has finite elements and the property that arithmetic operations on field elements always have a result in the field. In the sequel, we illustrate two kind of representations of the finite elements and its arithmetic operations.

Proposition 1. For any prime $p$ and any natual number $r$ there exists a finite field with $p^{r}$ elements and vice versa.

With the proposition 1, the Galois Field is denoted as $GF(p^{r})$ . In fact, the nature of RS encoding is mapping $k$ elments of $GF(2^{r})$ into another $n$ elements of $GF(2^{r})$ and $k+2\leq n< 2^{r}$ . This Galois fields can be represented with the help of $\mathbf{Z}_{2}[x]$ , the set of polynomials with coefficients in the field of two elements $\mathbf{Z}_{2}$ , namely the polynomial representation as
$0,1,x,x+1,x^{2},..,x^{r-1}+x^{r-2}+...+1 \tag{1}$
This representation can also be seen as a $r$ -bit digit or binary vector.

Proposition 2. $GF(q)$ has cyclic the multiplicative group $\{\alpha, \alpha^{2},...,\alpha^{q-1}=1\}$ , where $\alpha$ is the primitive element.

Thus, $GF(2^{r})$ has the exponential representation as
$0, 1(=\alpha^{255}), \alpha, \alpha^{2},..., \alpha^{2^{r}-2} \tag{2}$
which is a better choice for the ' $\times$ ' and ' $/$ ' operation. Even a binary matrix can be used to represente the elements. For example, we can establish a bijection between the vector representation and matrix representation over $GF(2^{4})$ as follows

Matrix representation

where the first column is the vector representation and the columns satisfy $column(i)=2\times column(i-1)$ . This matrix representation transforms arithmetic over $GF(2^{4})$ into arithmetic over $GF(2)$ which only has XOR, AND operations.

Galois Field Arithmetic

In this section, we discuss arithmetic in $GF(2^{8})$ , whose element corresponds a byte data.

Addition and Subtraction

Addition and subtraction are operated under the polynomial representation (also a byte in $GF(2^{8})$ ) and both are equivalent to XOR operation

func galAdd(a, b byte) byte {
    return a ^ b
}

func galSub(a, b byte) byte {
    return a ^ b
}

Multiplication and Division

The multiplication is operated with the exponential representation $(2)$ , before that we should establish a bijection (injection and surjection) between the two representations. Suppose
$\alpha^{i} -> 2^{i}$
where $0\leq i \leq 2^{8}-2=254$ . According to proposition 2, $\forall j\geq 255,\alpha^{j}=\alpha^{j-255}$ .

Proposition 3. $GF(2^{8})$ has the irreducible polynomial $f(x)=x^{8}+x^{4}+x^{3}+x^{2}+1$ which has no factors of smaller polynomials.

The irreducible polynomial is necessary to establish the bijection since some $2^{i}$ term are no longer in $GF(2^{8})$ . Let $f(\alpha) =0$ , we have $\alpha^{8}=\alpha^{4}+\alpha^{3}+\alpha^{2}+1=2^{4}+2^{3}+2^{2}+1=00011101$
or 0x1d . For convenience, we record the bijection with a table, namely called exponent table, whose indexs is the exponents of elements in exponential representation and value is elements in byte representation.

var expTable = [255]byte{0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, ..., 0x8e}

Use logTable[expTable[ $i$ ]]= $i$ , the logarithmic table is generated,

var logTable = []byte{
    0, 0, 1, 25, 2, 50, 26, 198,
    ...
    116, 214, 244, 234, 168, 80, 88, 175,
}

With these tables, the $\times$ and $/$ functions in $GF(2^8)$ are easily defined,

func galMultiply(a, b byte) byte {
    if a == 0 || b == 0 {
        return 0
    }

    logA := int(logTable[a])
    logB := int(logTable[b])

    sum := logA+logB

    if sum>254 {
        sum -= 255
    }
    return expTable[sum]
}

func galDivide(a, b byte) byte {
    if a == 0 {
        return 0
    }
    if b == 0 {
        panic("Argument 'divisor' is 0")
    }
    logA := int(logTable[a])
    logB := int(logTable[b])
    logResult := logA - logB
    if logResult < 0 {
        logResult += 255
    }
    return expTable[logResult]
}

Based on the result above, the power and inverse functions can be further obtained. In fact, the method to establish the bijection is not unique. The original paper of Reed and Solomon in 1960 provides another method with finite difference equation which has better computability.

RS Code

Coding Matrix Method

1. Orignal approach:
For arbitrary $k$ 8-bit symbols, $m_{0}$ , $m_{1}$ , $...$ , $m_{k-1}$ , we have the message polynomial
$m(x)=m_{0}+m_{1}x+...+m_{k-1}x^{k-1},$
with this $m(x)$ , $2^{8}$ codewords, i.e. $m(0)$ , $m(1)$ , $...$ , $m(\alpha^{r-2})$ are obtained and the the encoded messages, which will be transmitted or stored, are $n$ of the codewords (professionally called stripe). Using linear algebra, the stripe are denoted collectively as follows
$\begin{bmatrix} m(\alpha_{1})\\ m(\alpha_{2})\\ ...\\ m(\alpha_{n}) \end{bmatrix} = \begin{bmatrix} 1 & \alpha_{1} & ... & \alpha_{1}^{k-1} \\ 1 & \alpha_{2} & ...&\alpha_{2}^{k-1} \\ ... & ... & ...&... \\ 1 & \alpha_{n} & ...&\alpha_{n}^{k-1} \end{bmatrix} \begin{bmatrix} m_{0}\\ m_{1}\\ ...\\ m_{k-1} \end{bmatrix}\tag{3}$
Note that we only discuss one byte a shard (the messages are splited into multiple shards for encoding) here, in practice one input shard (data shard) contains thousands of bytes, in this case the output shard (code shard) contains same size of byte as input shard and the vectors in $(3)$ becomes matrice.

Coding procedure :
1.Split the whole message into same size input shards;
2. Build the Vandermonde matrix (coding matrix);
3. Multiplies the coding matrix by input shards to produce output shards.

func (r reedSolomon) Split(data []byte) ([][]byte, error) {
    if len(data) == 0 {
        return nil, ErrShortData
    }
    // Calculate number of bytes per data shard.
    perShard := (len(data) + r.DataShards - 1) / r.DataShards

    if cap(data) > len(data) {
        data = data[:cap(data)]
    }

    // Only allocate memory if necessary
    if len(data) < (r.Shards * perShard) {
        // Pad data to r.Shards*perShard.
        padding := make([]byte, (r.Shards*perShard)-len(data))
        data = append(data, padding...)
    }

    // Split into equal-length shards.
    dst := make([][]byte, r.Shards)
    for i := range dst {
        dst[i] = data[:perShard]
        data = data[perShard:]
    }

    return dst, nil
}

func vandermonde(rows, cols int) (matrix, error) {
    result, err := newMatrix(rows, cols)
    if err != nil {
        return nil, err
    }
    for r, row := range result {
        for c := range row {
            result[r][c] = galExp(byte(r), c)
        }
    }
    return result, nil
}

// Multiplies a subset of rows from a coding matrix by a full set of
// input shards to produce some output shards.
// 'matrixRows' is The rows from the matrix to use.
// 'inputs' An array of byte arrays, each of which is one input shard.
// The number of inputs used is determined by the length of each matrix row.
// outputs Byte arrays where the computed shards are stored.
func (r reedSolomon) codeSomeShards(matrixRows, inputs, outputs [][]byte) {
    for c := 0; c < r.DataShards; c++ {
        in := inputs[c]
        for iRow := 0; iRow < outputCount; iRow++ {
            if c == 0 {
                galMulSlice(matrixRows[iRow][c], in, outputs[iRow], r.o.useSSSE3, r.o.useAVX2)
            } else {
                galMulSliceXor(matrixRows[iRow][c], in, outputs[iRow], r.o.useSSSE3, r.o.useAVX2)
            }
        }
    }
}

Since any $k$ rows of Vandermonde matrix are linearly independent, with arbitrary $k$ correct code shards, the original $k$ data shards can be reconstructed by multiplying the corresponding inverse matrix

func (r reedSolomon) reconstruct(shards [][]byte) error {

    // Pull out an array holding just the shards that
    // correspond to the rows of the submatrix.  These shards
    // will be the input to the decoding process that re-creates
    // the missing data shards.
    subShards := make([][]byte, r.DataShards)       
    validIndices := make([]int, r.DataShards)       
    subMatrixRow := 0
    for matrixRow := 0; matrixRow < r.Shards && subMatrixRow < r.DataShards; matrixRow++ {
        if len(shards[matrixRow]) != 0 {
            subShards[subMatrixRow] = shards[matrixRow]
            validIndices[subMatrixRow] = matrixRow
            subMatrixRow++
    }
    
    // Pull out the rows of the matrix that correspond to the
    // shards that we have and build a square matrix.  This
    // matrix could be used to generate the shards that we have
    // from the original data.
    subMatrix, _ := newMatrix(r.DataShards, r.DataShards)
    for subMatrixRow, validIndex := range validIndices {
        for c := 0; c < r.DataShards; c++ {
            subMatrix[subMatrixRow][c] = r.m[validIndex][c]
        }

    // Invert the matrix
    dataDecodeMatrix, err = subMatrix.Invert()
    if err != nil {
        return err
    }

    // Re-create any data shards that were missing.
    //
    // The input to the coding is all of the shards we actually
    // have, and the output is the missing data shards.  The computation
    // is done using the special decode matrix we just built.
    outputs := make([][]byte, r.ParityShards)
    matrixRows := make([][]byte, r.ParityShards)
    outputCount := 0

    for iShard := 0; iShard < r.DataShards; iShard++ {
        if len(shards[iShard]) == 0 {
            if cap(shards[iShard]) >= shardSize {
                shards[iShard] = shards[iShard][0:shardSize]
            } else {
                shards[iShard] = make([]byte, shardSize)
            }
            outputs[outputCount] = shards[iShard]
            matrixRows[outputCount] = dataDecodeMatrix[iShard]
            outputCount++
        }
    }
    r.codeSomeShards(matrixRows, subShards, outputs[:outputCount], outputCount, shardSize)

    return nil
}

However, in practice, we usually do not know which one is correct or corrupted for the $n$ received codewords. In this case, the plurality of votes method is necessary and
$\left(\begin{array}{c} n-s\\k \end{array} \right)>\left(\begin{array}{c} s+k-1\\k \end{array} \right)$
or
$s<\frac{n-k+1}{2}$
where $s$ is number of unkown errors, therefore $n=k+2s$ always satisfies the in-equation. Another approach is to use the Berlekamp-Welsh Algorithm which avoids the heavy computation of votes:

Berlekamp-Welsh decoder:
1. Send $m(\alpha_{1}),m(\alpha_{2}),...,m(\alpha_{n})$ , receive $m'(\alpha_{1}),m'(\alpha_{2}),...,m'(\alpha_{n})$ , and most $s$ of them such that $m(\alpha_{i})\neq m'(\alpha_{i})$ ；
2. $E(x)=x^{s}+b_{s-1}x^{s-1}+...+b_{0}$ , $Q(x)=a_{k+s-1}x^{k+s-1}+a_{k+s-2}x^{k+s-2}+...+a_{0}$
3. Solve the coefficients of co $E(x)$ , $Q(x)$ with $Q(\alpha_{i})=m'(\alpha_{i})E(\alpha_{i})$
4. Derive $m(x)=Q(x)/E(x)$ .

In fact, $\forall m(\alpha_{i})\neq m'(\alpha_{i})$ , $E(\alpha_{i})=0$ .

The implicite principle: $Q'(x)/E'(x)$ and $Q(x)/E(x)$ agree on at least $k+s$ points. $E'(x)$ and $E(x)$ both have at most $s$ zero points. Elimilate $E'(x)$ and $E(x)$ , $Q'(x)/E'(x)$ and $Q(x)/E(x)$ are degree at least $k-1$ and agree on at least $k$ points, thus $Q'(x)/E'(x)=Q(x)/E(x)=m(x)$ .

2. Systematic coding matrix:

In the original approach, all the code shards have been encoded. While in the systematic encoding, the original data shards become part of the code shards and only the parity shards should be encoded. In other words, the stripe contains the original datas and parity codewords together no longer codewords only. The coding matrix is composed of the top square identity matrix and the parity matrix. There are three methods of building the coding matrix in this systematic way:

Elementary transform on the Vandermonde matrix as the procedure 1.

func buildMatrix(dataShards, totalShards int) (matrix, error) {
    vm, err := vandermonde(totalShards, dataShards)
    if err != nil {
        return nil, err
    }

    top, err := vm.SubMatrix(0, 0, dataShards, dataShards)
    if err != nil {
        return nil, err
    }

    topInv, err := top.Invert()
    if err != nil {
        return nil, err
    }

    return vm.Multiply(topInv)
}

Parity matrix is a transposed Vandermonde matrix.

func buildMatrixPAR1(dataShards, totalShards int) (matrix, error) {
    result, err := newMatrix(totalShards, dataShards)
    if err != nil {
        return nil, err
    }

    for r, row := range result {
        // The top portion of the matrix is the identity
        // matrix, and the bottom is a transposed Vandermonde
        // matrix starting at 1 instead of 0.
        if r < dataShards {
            result[r][r] = 1
        } else {
            for c := range row {
                result[r][c] = galExp(byte(c+1), r-dataShards)
            }
        }
    }
    return result, nil
}

Parity matrix is a transposed Cauchy matrix. Cauchy matrices are easier to invert than general matrices [8].

func buildMatrixCauchy(dataShards, totalShards int) (matrix, error) {
    result, err := newMatrix(totalShards, dataShards)
    if err != nil {
        return nil, err
    }

    for r, row := range result {
        // The top portion of the matrix is the identity
        // matrix, and the bottom is a transposed Cauchy matrix.
        if r < dataShards {
            result[r][r] = 1
        } else {
            for c := range row {
                result[r][c] = invTable[(byte(r ^ c))]
            }
        }
    }
    return result, nil
}

Generator Polynomial Method

Define the generator polynomial:
$g(x)=(x-\alpha)(x-\alpha^{2})\dots(x-\alpha^{2s})$
and the codeword polynomial can be directly computed as
$c(x)=m(x)g(x)$
For the systematic form, which is more often used in practice, we define
$b(x)=x^{2s}m(x) \quad mod\quad g(x)$
then the codeword polynomial becomes
$c(x)=x^{2s}m(x)-b(x)$
where $-b(x)$ is the parity codeword polynomial. All the polynomial operation above is processed over $GF(2^8)$ . It is also observed that the correction of received message can be checked by testing its divisibility by g(x), and there is no need to decode for the systematic encoding if the answer is affirmative. Otherwise, we denote $r(x)=c(x)+e(x)$ and suppose there are $v(<s)$ errors

Syndrome based decoder:
1.Calculate the $2s$ Syndromes: $S_{j}=r(\alpha^{j})=e(\alpha^{j})$
2. Solve
$\begin{bmatrix} S_{1} & S_{2}& ... & S_{v} \\ S_{2} & S_{3} & ...&S_{v+1} \\ ... & ... & ...&... \\ S_{v} & S_{v+1} & ...&S_{2v-1} \end{bmatrix} \begin{bmatrix} \Lambda_{v}\\ \Lambda_{v-1}\\ ...\\ \Lambda_{1} \end{bmatrix}=\begin{bmatrix} -S_{v} \\ -S_{v+1}\\ ...\\ -S_{2v}\tag{4} \end{bmatrix}$ and use Chien search solve $\Lambda(x)=\Lambda_{v}x^{v} +\Lambda_{v-1}x^{v-1}+...+1=0$ to derive the $v$ roots, denoted as, $x_{1},..,x_{v}$ .
3. Use Forney algorithm to solve $\begin{bmatrix} x_{1}^{-1} & x_{2}^{-1}& ... & x_{v}^{-1} \\ x_{1}^{-2} & x_{2}^{-2} & ...&x_{v}^{-2} \\ ... & ... & ...&... \\ x_{1}^{-2s} & x_{2}^{-2s} & ...&x_{v}^{-2s} \end{bmatrix} \begin{bmatrix} e_{i_{1}}\\ e_{i_{2}}\\ ...\\ e_{i_{v}} \end{bmatrix}=\begin{bmatrix} S_{1} \\ S_{2}\\ ...\\ S_{2s} \end{bmatrix}$
4. The index $i_{j}$ of $e_{i_{j}}$ are determined by looking up the logarithmic table of $x_{j}^{-1}$ .
5. Compute $e(x)=\sum_{j=1}^{v}e_{i_{j}}x^{-i_{j}}$ and $c(x) = r(x)-e(x)$ .

It is worth mentioning that all the syndromes are zeros if $r(x)=c(x)$ , this can be used to check if the received message is corrupted or if the message was completely constructed. RS encoding is relatively straightforward for the generator approach, but decoding needs complicated algebraic computation, especially for the step 2. Because the real value of $v$ is unknown and the normal way has to use the trial value untill the matrix in $(4)$ is nonsingular. Other algebraic methods for the evaluation of this error location polynomial $\Lambda(x)$ include Berlekamp–Massey algorithm and Extended Euclidean algorithm.
This syndrome based decoder can be implemented with different hardware unit such as matrix vector multiplication unit, remainder unit, and performs hard-decision decoding up to $s$ errors. Hard-decision decoding decides the bit according to the a threshold, where each bit is definitely one or zero. While soft-decision decoding requires additional reliability information to improve the decision, which has better coding gain for the white Guassian channel [2].

RS Code in Distributed Storage Systems

The RS code are stored in different disks in the distributed storage systems, and the performance of the arasure code in distributed storage systems involves disk I/O and repair bandwidth overhead.

Rotated Reed-Solomon code

In the conventional RS code, all the parity blocds are encoded with data blocks in the same strip, while in the rotated reed-solomon code, parity blocks may be generated with different stripes as in the following figure,

RRS code

when the disk 5 in the figure fails, this method reduceS 3 operations of reading the data blocks than the conventional RS code [5].

Local Reconstruction Code (LRC)

LRC introduces local parity codes which requires slightly more storage space than conventional RS code, but significantly reduce the number of participating data discs for encoding, thus it is beneficial to the reduction of bandwidth and disc I/O overhead. The figure of pyramid code is shown as follows [6]

Pyramid

However, repair of the global redundancy still needs to access all data discs, another LRC approach in [7] further introduces parity code ( $S_{3}$ in the figure) for the global parity codes ( $P_{1}$ , $P_{2}$ , $P_{3}$ , $P_{4}$ ) to avoid this undesirable situation. By choosing the coefficients of $c_{1}^{'}$ , $c_{2}^{'}$ , $c_{3}^{'}$ , $c_{4}^{'}$ and $c_{5}^{'}$ , $c_{6}^{'}$ properly, the parity code of $S_{3}$ can be calculated by the existing parity codes $S_{1}$ and $S_{2}$ . Thus parity code $S_{3}$ does not have to occupy additional storage.

HDFS-Xorbas

Observation: Copy is kind of LRC.

References

[1] I. Reed and G. Solomon, BPolynomial codes over certain finite fields,[ J. Soc. Ind. Appl. Math., vol. 8,
no. 2, pp. 300–304, Jun. 1960.
[2] Wicker and Bhargava, Reed-Solomon Codes and Their Applications, 1994.
[3] James S. Plank and Lihao Xu, Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Network Storage Applications.
[4] Reed–Solomon codes for coders.
[5] Khan O, Burns R C, Plank J S, et al. Rethinking erasure codes for cloud file systems: minimizing I/O for recovery and degraded reads.
[6] Huang Cheng, Chen Minghua, Li Jin. Pyramid codes: flexible schemes to trade space for access efficiency in reliable data storage systems.
[7] Sathiamoorthy M, Asteris M, Papailiopoulos D, et al. Xoring elephants: novel erasure codes for big data.
[8] J. Blomer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, and D. Zuckerman, An XOR-Based Erasure-Resilient Coding Scheme.

A Study for the Reed-Solomon Cod

Introduction

Galois Field

Galois Field Arithmetic

Addition and Subtraction

Multiplication and Division

RS Code

Coding Matrix Method

Generator Polynomial Method

RS Code in Distributed Storage Systems

Rotated Reed-Solomon code

Local Reconstruction Code (LRC)

References

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读