Efficient generalized tensor product codes encoding schemes

Patent metadata

Field	Value
Publication number	US-10333554-B2
Application number	US-201715639475-A
Country	US
Kind code	B2
Filing date	Jun 30, 2017
Priority date	Jun 30, 2017
Publication date	Jun 25, 2019
Grant date	Jun 25, 2019

Abstract

A method for generating a binary GTP codeword, comprised of N structure stages and each stage comprises at least one BCH codeword with error correction capability greater than a prior stage and smaller than a next stage, includes: receiving a syndrome vector s of a new stage 0 binary BCH codeword y over a field GF(2 m ) that comprises Δt syndromes of length m bits, wherein the syndrome vector s comprises l-th Reed-Solomon (RS) symbols of Δt RS codewords whose information symbols are delta syndromes of all BCH codewords from stage 0 until stage n−1; and multiplying s by a right submatrix Ũ of a matrix U, wherein U is an inverse of a parity matrix of an BCH code defined by t n , wherein the new binary BCH codeword is y =Ũ· s .

First claim

What is claimed is:

1. A computer implemented method for generating a binary Generalized Tensor Product (GTP) codeword, comprised of N structure stages wherein N is an integer greater than 1 and each stage is comprised of at least one BCH codeword with error correction capability greater than a prior stage and smaller than a next stage, the method executed by the computer comprising the steps of:
receiving new stage 0 binary BCH codeword y over a field GF(2 m ) from a communication channel;
receiving a syndrome vector s of the new stage 0 binary BCH codeword y that comprises Δt syndromes of length m bits, wherein Δt=t n −t 0 , t 0 is the error correction capability of the stage 0 BCH codeword, t n is an error correction capability of a stage n BCH codeword to which a new binary BCH codeword y will be added, wherein the syndrome vector s comprises l-th Reed-Solomon (RS) symbols of Δt RS codewords whose information symbols are delta syndromes of all BCH codewords from stage 0 until stage n−1, wherein l indexes the BCH codeword to which y will be added; and
multiplying s by a right submatrix Ũ of a matrix U, wherein U is an inverse of a parity matrix of an BCH code defined by t n , wherein the submatrix Ũ is of size mt 0 ×mΔt, wherein the new binary BCH codeword is y =Ũ· s .

2. The method of claim 1 , wherein multiplying s by right submatrix Ũ of matrix U comprises multiplying each component of the syndrome vector s by a component of submatrix Ũ by a binary logic function in a single hardware cycle to yield a component product, wherein submatrix Ũ is calculated before receiving syndrome vector s of new binary BCH codeword y , and multiplexing the component products into a single output that represents the new binary BCH codeword y .

3. The method of claim 2 , wherein the syndrome vector s is demultiplexed into separate Ũ matrices.

4. The method of claim 1 , wherein multiplying s by right submatrix Ũ of matrix U further comprises:
multiplying each component of the syndrome vector s by a component of reduced submatrix Ũ′ by a binary logic function in a single hardware cycle to yield a component product, wherein reduced submatrix defined by Ũ′(x)=Ũ(x)/g 0 (x), wherein columns of submatrices Ũ′ and Ũ are represented as polynomials and each column of Ũ′(x) is the column of Ũ(x) divided by g 0 (x), are calculated before receiving syndrome vector s of new binary BCH codeword y ;
multiplexing the component products into a temporary output; and
convolving the temporary output with a common multiplier g 0 (x) to yield the single output that represents the new binary BCH codeword y , wherein g 0 (x) is a common multiplier of all columns of submatrix Ũ represented as polynomials and is calculated before receiving syndrome vector s of new binary BCH codeword y .

5. The method of claim 4 , wherein the syndrome vector s is demultiplexed into separate Ũ′ matrices.

6. The method of claim 4 , wherein convolving the temporary output with a common multiplier g 0 (x) is performed over multiple clock cycles.

7. The method of claim 1 , wherein multiplying s by a right submatrix Ũ of a matrix U further comprises:
calculating a polynomial h j (x) by multiplying syndrome vector s by a matrix H j formed by concatenating the m polynomials h j,l as columns, wherein polynomials

h

j
,
l

⁡

(
x
)

=

U
_

mj
+
l

′

⁡

(
x
)

/

M
j

⁡

(
x
)

⁢

⁢
and
⁢

⁢

M
j

⁡

(
x
)

=

∏

i
=

t
0

+
1

i
≠

j
+

t
0

+
1

t
1

⁢

⁢

m
i

⁡

(
x
)

m i (x) wherein m i (x) is an i-th minimal polynomial of the BCH code C 1 with correction capability of t 1 and is calculated before receiving syndrome vector s of new binary BCH codeword y ;
multiplying h j (x) by M j (x), and summing over j=0 to Δt−1;
multiplexing the sums of the products h j (x)×M j (x) into a temporary output; and
convolving the temporary output with a common multiplier g 0 (x) to yield the single output that represents the new binary BCH codeword y , wherein g 0 (x) is a common multiplier of all columns of submatrix Ũ represented as polynomials and is calculated before receiving syndrome vector s of new binary BCH codeword y .

8. The method of claim 7 , wherein the syndrome vector s is demultiplexed into separate sets of H j and M j .

9. The method of claim 7 , wherein convolving the temporary output with a common multiplier g 0 (x) is performed over multiple clock cycles.

10. A computer processor configured to execute a program of instructions to perform the method steps generating a binary Generalized Tensor Product (GTP) codeword, comprised of N structure st

Assignees

• Samsung Electronics Co Ltd

Inventors

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

Classifications

• H03M13/2909

  Product codes · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title

• H03M13/152 Primary

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

• H03M13/616 Primary

  Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations · CPC title

• H03M13/617

  Polynomial operations, e.g. operations related to generator polynomials or parity-check polynomials · CPC title