Polar codes for efficient encoding and decoding in redundant disk arrays

Patent metadata

Field	Value
Publication number	US-9304859-B2
Application number	US-201214122404-A
Country	US
Kind code	B2
Filing date	Dec 29, 2012
Priority date	Dec 29, 2012
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

Abstract

An improved technique applies polar codes to storage data to improve the reliability of a storage system that uses high-performance, solid-state disks as part of a RAID group for storing frequently-accessed data. Along these lines, a high-performance storage system having n solid-state disks assigns k of those disks as payload disks. The storage system partitions the payload data into a data vector that has k data symbols. The storage system then applies, to the k payload symbols, a (n, k) polar code generator matrix derived from k rows of the ┌ log 2 n┐-times Kronecker product of the matrix
  ( 1 0 1 1 )
to produce n encoded symbols and stores each of the encoded payload symbols in a solid-state disk of the RAID group.

First claim

What is claimed is:

1. A method of reliably storing data within a storage system having high-performance, solid-state disks arranged as part of a RAID group having n solid-state disks of which k solid-state disks are payload disks, k being less than n, the method comprising:
partitioning the payload data into a data vector that includes k data symbols;
applying an (n, k) polar code generator matrix to the payload vector to produce a codeword that includes n encoded symbols, the (n, k) polar code generator matrix including exactly k rows of an n×n matrix that is derived from ┌ log 2 n┐-times Kronecker product of a 2×2 polar seed matrix with itself, the k rows having indices equal to the indices of the k payload symbols of the data vector; and
storing each of the n encoded symbols of the codeword in a solid-state disk of the RAID group.

2. The method of claim 1 ,
wherein n=2 s for a positive integer s;
wherein applying the (n, k) polar code generator matrix to the payload vector includes:
for a positive integer l, splitting the payload data vector into a set of v=2 l payload data subvectors, the i th payload data subvector for each index i satisfying 1≦i≦v having k i payload symbols for some positive integer k i satisfying Σ i=1 v k i =k,
generating, from the (n, k) polar code generator matrix, a set of v outer code generator matrices, the i th outer code generator matrix of the set of v outer code generator matrices for each index i satisfying 1≦i≦v being a (N, k i ) polar code generator matrix including exactly k i rows of the N×N matrix derived from (s−l)-times Kronecker product of the 2×2 polar seed matrix with itself, N being equal to 2 s−l ,
generating, from the (n, k) polar code generator matrix, (v, v−i+1) inner code generator matrix for each index i satisfying 1≦i≦v being a (v, v−i+1) polar code generator matrix including the (v−i+1) rows of the v×v matrix derived from l-times Kronecker product of the 2×2 polar seed matrix with itself, where v inner codes are nested ones,
producing a v×N matrix of intermediate symbols from products of each payload data subvector of the set of v payload data subvectors by a corresponding outer code generator matrix of the set of v outer code generator matrices, and
generating a v×N matrix of final encoded symbols from a product of the v×N matrix of intermediate symbols and the first inner code generator matrix of the set of v inner codes generator matrices, the n encoded symbols being the elements of the v×N matrix of final encoded symbols.

3. The method of claim 2 ,
wherein generating the set of v outer codes generator matrices includes:
performing a bit reversal operation on i to produce a bit-reversed index i*;
for each index j satisfying 1≦j≦N:
extracting a row of the N×N matrix derived from (s−l)-times Kronecker product of the 2×2 polar seed matrix having index j* to produce the j th row of the i* th outer code generator of the set of v outer code generators.

4. The method of claim 2 ,
wherein generating the set of v outer code generators includes:
producing a set of indices by which the set of v outer code generator matrices are arranged in an ascending order by value of k i ; and

wherein generating the v×v inner code generator includes:
multiplying a row swapping matrix and the v×v matrix derived from l-times Kronecker product of the 2×2 polar seed matrix with itself, the row swapping matrix arranging the rows and columns of the v×v inner code matrix according to the set of indices, the v×v inner code generator being an low triangular matrix.

5. The method of claim 4 ,
wherein the set of v outer code generator matrices represents systematic outer codes; and
wherein generating the set of v outer code generator matrices further includes:
for each index i satisfying 1≦i≦v:
concatenating a k i ×k i identity matrix with a k i ×(N−k i ) check symbols generation matrix B (i) .

6. The method of claim 5 ,
wherein the 2×2 polar seed matrix is

F
=

(

1

0

1

1

)

,

diagonal elements of the first inner code generator matrix having a value of unity, this matrix is low triangular one;
wherein generating the v×N matrix of final encoded symbols, i.e. codeword, includes:
for each index i satisfying 1≦i≦v:
for each index j satisfying 1≦j≦k i :
setting the (i, j) th element of the v×N matrix of final encoded symbols equal to the j th element of the i th payload data subvector; and

generating an inverse of the first inner code transposed generator matrix,
for each index i satisfying v≧i≧1, and in order of decreasing values of i:
forming a first 1×(v−i+1) subarray of the inverse of the first inner code transposed generator matrix from the i th row and final v−i+1 columns,
forming a first (v−i+1)×k i subarray of the v×N matrix of final encoded symbols from the final v−i+1 rows and first k i columns of the v×N matrix of final encoded symbols,
multiplying the first 1×(v−i+1) subarray of the inverse of the first inner code transposed generator matrix and the first (v−i+1)×k i subarray of the v×N matrix of final encoded symbols to form a 1×k i intermediate term,
multiplying the 1×k i intermediate term and the k i ×(N−k i ) check symbol generation matrix B (i) to form a first 1×(N−k i ) product term,
forming a second 1×(v−i) subarray of the inverse of the first inner code transposed generator matrix from the i th row and final v−i columns of the inverse of the first inner code transposed generator matrix,
forming a second (v−i)×(N−k i ) subarray of the v×N matrix of final encoded symbols from the final v−i rows and last N−k i columns,
multiplying the second 1×(v−i) subarray of the inverse of the first inner code transposed generator matrix and the second (v−i)×(N−k i ) subarray of the v×N matrix of final encoded symbols to form the second 1×(N−k i ) product term, and
setting an array including the final N−k i elements of the i th row of the v×N matrix of final encoded symbols equal to a difference between a the first 1×(N−k i ) product term and the second 1×(N−k i ) product term.

7. The method of claim 2 :
after generating the v×N matrix of final encoded symbols, extracting a set of erased encoded symbols;
producing an initial erasure index h based on the first row of the v×N matrix of final encoded symbols that has an erased final encoded symbol;
forming an outer subset of the final v−h+1 outer code generator matrices of the set of v outer code generator matrices;
forming a set of v−h+1 inner shortened subcode generator matrices, the i th inner shortened subcode generator matrix of the set of v−h+1 inner shortened subcode generator submatrices being a (v−i+1)×(v−h+1) matrix that includes the final v−i+1 rows and the final v−h+1 columns of the first inner code generator matrix, i satisfying h≦i≦v;
for each index i satisfying h≦i≦v:
performing a decoding operation on a (v−h+1)×N submatrix given by final v−h+1 rows of the v×N matrix of final encoded symbols in the i th inner shortened subcode generator matrices of the set of v−h+1 inner shortened subcode generator matrices to produce a 1×N array of int

Assignees

• Emc Corp

Inventors

• Aliev Artem Alexandrovich
• Miloslavskaya Vera Dmitriyevna
• Trifonov Peter Vladimirovich

Classifications

• H03M13/13

  Linear codes · CPC title

• G06F11/108 Primary

  Parity data distribution in semiconductor storages, e.g. in SSD · CPC title

• G06F11/2058

  using more than 2 mirrored copies · CPC title

• G06F2211/1009

  Cache, i.e. caches used in RAID system with parity · CPC title