Bose-chaudhuri-hocquenchem (BCH) encoding and decoding tailored for redundant array of inexpensive disks (RAID)

Patent metadata

Field	Value
Publication number	US-10387254-B2
Application number	US-201715730943-A
Country	US
Kind code	B2
Filing date	Oct 12, 2017
Priority date	Oct 12, 2017
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

Abstract

A method of encoding generalized concatenated error-correcting codes includes providing a parity matrix {tilde over (H)} j of a j-th layer code and predefined syndrome {tilde over (s)} of length n−{tilde over (k)} j , where the first n-k l coordinates are zero, n is a length of a codeword c of a first layer BCH code C l of dimension {tilde over (k)} j , codeword c satisfies {tilde over (H)} j c={tilde over (s)}, a first layer code includes only a BCH code, and each subsequent layer includes a Reed-Solomon (RS) stage followed by a BCH code; finding a square matrix R, of dimension (n−{tilde over (k)} j )(n−{tilde over (k)} j ) such that R j {tilde over (H)} j =(A|I), where A is an arbitrary matrix, R j =(Q j |T j ), where Q has n−k l columns T j and has k 1 −{tilde over (k)} j columns; finding a vector c−(a b) where a is a vector of length {tilde over (k)} j and b is a vector of length n−{tilde over (k)} j ; and solving
( A | I ) ⁢ ( a b ) = ( Q j | T j ) ⁢ s ~ = T j ⁢ s ⁢ ⁢ where ⁢ ⁢ a = 0 ⁢ ⁢ and ⁢ ⁢ b = T j ⁢ s ,
where a=0 and b=T j s, and codeword c is nonzero only on the last n−{tilde over (k)} j =n−k j bits.

First claim

The invention claimed is:

1. A computer implemented method of encoding generalized concatenated error-correcting codes, comprising the steps of:
receiving a codeword {tilde over (C)} j comprising n r rows, wherein n r >=1, of n bits each with k M information bits, k M <n, n>=1, wherein codeword {tilde over (C)} j is a code with parity check matrix

H
j

=

(

H
1

Δ
~

21

Δ
~

32

⋮

Δ
~

j
-
1

,
j

)

wherein matrix H 1 is the parity check matrix of code C 1 , matrix

Δ
~

j
-
1

,
j

=

(

Δ
~

j
-
1

,
j

ext
j

)

,

where {tilde over (Δ)} j−1,j has L j rows and ext j has L j −δ j rows, and matrix Δ j−1,j represents the additional checks for codewords in C j that are not in C j−1 and has δ j rows;
partitioning the k M information bits into n r blocks, wherein each layer comprises k j+1 RS −k j RS blocks of {tilde over (k)} j bits each for j=2, . . . , L, wherein L is a number of layers of weak (BCH) code C 1 , wherein each layer, except for a first layer, comprises a Reed Solomon (RS) stage followed by a BCH code, and the first layer includes only a BCH code, and {tilde over (k)} j is a dimension of codeword {tilde over (C)} j ;
encoding a first k 2 RS blocks with a code C 1 and computing syndromes S ij ={tilde over (Δ)}S j (x i ) wherein a vector of syndromes

(

S
12

,
…
⁢

,

S

k
2
RS

,
2

)

is information encoded by Reed Solomon code RS 2 , wherein a resulting RS 2 codeword is given by

(

S
12

,
…
⁢

,

S

k
2
RS

,
2

,

S

k
2
RS

+
1

,
2

,
…
⁢

,

S

n
r

,
2

)

;

transforming information blocks of size {tilde over (k)} j , for j=2, . . . , L and i∈{k j RS +1, . . . , k j+1 RS } into blocks u i , i=1 to n r , of size k j using zero padding in coordinates specified by unit vectors;
encoding block u i with an encoder for C j to compute codeword x i ;
calculating a vector b of length n−{tilde over (k)} j from

b
=

T
j

⁡

(

S

i
⁢

⁢
2

⋮

S

Assignees

• Samsung Electronics Co Ltd

Inventors

• Twitto Moshe
• Shany Yaron
• Dor Avner
• Erez Elona
• Kong Jun Jin

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/2906

  using block codes (H03M13/2957 takes precedence) · CPC title

• H03M13/1515 Primary

  Reed-Solomon codes · CPC title

• H03M13/152 Primary

  Bose-Chaudhuri-Hocquenghem [BCH] codes · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title