Low complexity partial parallel architectures for Fourier transform and inverse Fourier transform over subfields of a finite field

Patent metadata

Field	Value
Publication number	US-9734129-B2
Application number	US-201414258679-A
Country	US
Kind code	B2
Filing date	Apr 22, 2014
Priority date	Apr 22, 2014
Publication date	Aug 15, 2017
Grant date	Aug 15, 2017

Abstract

Low complexity partial parallel architectures for performing a Fourier transform and an inverse Fourier transform over subfields of a finite field are described. For example, circuits to perform the Fourier transforms and the inverse Fourier transform as described herein may have architectures that have simplified multipliers and/or computational units as compared to traditional Fourier transform circuits and traditional inverse Fourier transform circuits that have partial parallel designs. In a particular embodiment, a method includes, in a data storage device including a controller and a non-volatile memory, the controller includes an inverse Fourier transform circuit having a first number of inputs coupled to multipliers, receiving elements of an input vector and providing the elements to the multipliers. The multipliers are configured to perform calculations associated with an inverse Fourier transform operation. The first number is less than a number of inverse Fourier transform results corresponding to the inverse Fourier transform operation.

First claim

What is claimed is:

1. A circuit configured to perform an inverse Fourier transform operation based on an input vector and to generate a group of results corresponding to the inverse Fourier transform operation, the circuit comprising:
a first number of inputs, each input configured to receive an element of the input vector and coupled to a multiplexer configured to iteratively produce intermediate values using a delay element in a feedback path that includes a multiplier, the feedback path between a multiplexer input of the multiplexer and a multiplexer output of the multiplexer;
multipliers coupled to the multiplexer outputs and configured to perform multiple iterations of calculations associated with the inverse Fourier transform operation; and
adders coupled to the multipliers and configured to iteratively output subgroups of the group of results corresponding to the inverse Fourier transform operation based on signals from the multipliers,
wherein the first number is less than a number of inverse Fourier transform results in the group of results corresponding to the inverse Fourier transform operation.

2. The circuit of claim 1 , wherein the adders are configured to output a subgroup and at least one additional subgroup, and wherein the subgroup and the at least one additional subgroup together produce an inverse Fourier transform result of the inverse Fourier transform operation.

3. The circuit of claim 1 , wherein the number of inverse Fourier transform results is equal to N, wherein the first number of inputs is equal to q, wherein N and q are each integers, and wherein q is less than N.

4. The circuit of claim 1 , wherein each multiplexer includes a first multiplexer input coupled to a corresponding one of the inputs and a second multiplexer input configured to receive a corresponding feedback value output by a corresponding delay element, and further comprising trace computation units coupled between the multipliers and the adders.

5. A method comprising:
in a data storage device including a controller and a non-volatile memory, wherein the controller includes a circuit to perform an inverse Fourier transform operation based on an input vector to generate a group of results corresponding to the inverse Fourier transform operation, the circuit having a first number of input circuits, each input circuit configured to iteratively output scaled versions of an element of the input vector using a delay element in a feedback path of the input circuit, and multipliers coupled to the input circuits, performing:
receiving, at the input circuits, elements of the input vector;
providing the scaled versions to the multipliers, wherein the multipliers are configured to perform multiple iterations of calculations associated with the inverse Fourier transform operation; and
outputting, via adders coupled to the multipliers and based on signals generated by the multipliers, subgroups of the group of results corresponding to the inverse Fourier transform operation,
wherein the first number is less than a number of inverse Fourier transform results in the group of results corresponding to the inverse Fourier transform operation.

6. The method of claim 5 , further comprising outputting a subgroup and at least one additional subgroup, the subgroup and the at least one additional subgroup outputted based on the multiple iterations to produce an inverse Fourier transform result of the inverse Fourier transform operation.

7. The method of claim 5 , wherein each of the input circuits is associated with a corresponding row of the multipliers, and wherein the first number is less than a second number of elements included in the input vector.

8. The method of claim 5 , wherein the first number of input circuits is associated with cyclotomic co sets of elements of a finite field, and wherein each of the input circuits corresponds to a different cyclotomic coset.

9. The method of claim 5 , wherein the non-volatile memory includes a three-dimensional (3D) memory configuration that is monolithically formed in one or more physical levels of arrays of storage elements having an active area disposed above a silicon substrate, and wherein the data storage device includes circuitry associated with operation of the storage elements.

10. A data storage device comprising:
a non-volatile memory; and
a controller operatively coupled to the non-volatile memory, wherein the controller includes a circuit configured to perform an inverse Fourier transform operation based on an input vector and to generate a group of results corresponding to the inverse Fourier transform operation, the circuit comprising:
a first number of inputs, each input configured to receive an element of the input vector and coupled to a multiplexer configured to iteratively produce intermediate values using a delay element in a feedback path that includes a multiplier, the feedback path between an input of the multiplexer and an output of the multiplexer;
multipliers coupled to the outputs, each multiplier configured to perform calculations associated with the inverse Fourier transform operation;
adders coupled to the multipliers; and
trace computation units coupled between the multipliers and the adders,
wherein the first number is less than a number of inverse Fourier transform results in the group of results corresponding to the inverse Fourier transform operation.

11. The data storage device of claim 10 , wherein the controller comprises a low density parity check (LDPC) encoder, and wherein the LDPC encoder includes the circuit.

12. The data storage device of claim 10 , wherein the controller further includes a decoder that includes the circuit and a Fourier transform circuit, and wherein the decoder is configured to use the circuit or the Fourier transform circuit during a decoding operation performed on a value received from the non-volatile memory.

13. The data storage device of claim 10 , wherein the non-volatile memory includes a three-dimensional (3D) memory configuration that is monolithically formed in one or more physical levels of arrays of storage elements having an active area disposed above a silicon substrate, and wherein the data storage device includes circuitry associated with operation of the storage elements.

14. A Fourier transform circuit comprising:
multipliers;
a pre-multiplication circuit of a group of pre-multiplication circuits that have inputs configured to receive elements of an input vector, the pre-multiplication circuit configured to receive an element of the elements and to route, via a switching circuit, a plurality of multiples of the elements to the multipliers;
a group of adders coupled to the multipliers and configured to perform calculations associated with a Fourier transform operation of the input vector to output subgroups of a group of results corresponding to the Fourier transform operation; and
a first number of terminals configured to output each subgroup of the group of results corresponding to the Fourier transform operation,
wherein the first number is less than a number of Fourier transform results in the group of results corresponding to the Fourier transform operation.

15. The Fourier transform circuit of claim 14 , wherein each of the inputs is configured to sequentially receive multiple elements of the input vector.

16. The Fourier transform circuit of claim 15 , wherein each pre-multiplication circuit is configured to generate, for each received element of the multiple elements, a corresponding plurality of multiples of the received element.

17. The Fourier transform

Assignees

• Sandisk Entpr Ip Llc
• Sandisk Technologies Llc

Inventors

• Zhang Xinmiao
• Tai Ying Yu

Classifications

• H03M13/158

  Finite field arithmetic processing · CPC title

• H03M13/6561

  Parallelized implementations · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title

• H03M13/1545

  Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial · CPC title

• G06F17/141 Primary

  Discrete Fourier transforms · CPC title