Digit reverse for mixed radix FFT
AssigneesSharp Microelectronics Technology, Inc., Sharp Kabushiki Kaisha
InventorsRaul A. Aguilar, Jeffrey L. Miller
Life of this patent
Estimating the term…
Abstract
A digit reversing system is disclosed for handling mixed radix FFT operations with arbitrary arrangements of radices. In a first step, all bits in an integer field of size log.sub.2 N are position reversed. In a second step, subfields of the output produced in the first step are individually unreversed at the local level to produce unreversed digits. The output is used for appropriately arranging input terms applied to a mixed-radix multi-stage Fast Fourier Transform (FFT) process.
Claims25
An address generator for generating a sequence of digit reversed signals to be used in conjunction with a transform of N sample points and one or more radix values, the generator comprising:
- a reversed-field sequence generator for generating a series of binary-coded signals respectively representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, where N is a supplied variable, and wherein the bits in the least significant field of size log.sub.2 N bits of the generated signals are reversed from their natural order;
- and
- a digit unreversing unit, operatively coupled to the reversed-field sequence generator for associating subfields of each log.sub.2 N sized field generated by the reversed-field sequence generator with specific reversed digits and unreversing the bits of each such subfield which has a bit-width greater than one, thereby to produce the corresponding digit in nonreversed form;
- wherein said reversed-field sequence generator comprises:
- an adder having a first input port, a second input port and an output port for producing a sum signal representing the sum of first and second binary-coded signals applied respectively to the first and second adder input ports, said adder being a forward adder not having an ability to add backwards;
- feedback means for feeding the sum signal back to the second input port of the adder;
- a first bus twist for supplying a field-reversed signal whose unreversed version represents the variable value N/2 to the first input port of the adder;
- and
- a second bus twist for supplying a field-reversed version of the sum signal as an output of the reversed-field sequence generator.
A method for generating signals representing a digit reversed sequence that is to be used in conjunction with a transform of N sample points where N is a variable and the transform is a multistage transform using a mix of same or different radix values satisfying r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N, the method comprising the steps of:
- receiving a transform-size defining signal defining the value of N;
- in response to the transform-size defining signal, generating a series of binary-coded signals representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, with the bits in the least significant field of size log.sub.2 N bits being reversed from their natural order;
- receiving an associating signal that associates specific subfields of the field generated by the generating step with corresponding reversed digits based on the mix of radix values used by said multistage transform;
- and
- in response to the associating signal, unreversing the bits of each associated subfield of width greater than one-bit to thereby produce the digit in nonreversed form.
A reversed-field sequence generator for generating a series of binary-coded signals respectively representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, with the bits in the least significant field of size log.sub.2 N bits being reversed from their natural order, the reversed-field sequence generator comprising:
- an adder having a first input port, a second input port and an output port for producing a sum signal representing the sum of first and second binary-coded signals applied respectively to the first and second adder input ports., said adder being a forward adder not having an ability to add backwards;
- feedback means for feeding the sum signal back to the second input port of the adder;
- a first bus twist for supplying a field-reversed signal whose unreversed version represents the value N/2 to the first input port of the adder;
- and
- a second bus twist for supplying a field-reversed version of the sum signal as an output of the reversed-field sequence generator.
An address generator for generating a sequence of digit reversed signals to be used in conjunction with a multistage transform of N sample points, said transform being characterized by a mix of same or different radix values satisfying r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N, where N is a variable, the generator comprising:
- a programmable reversed-field sequence generator, responsive to a supplied size signal indicating the value of the variable N, for generating a series of binary-coded signals respectively representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, with the bits in the least significant field of size log.sub.2 N bits reversed from their natural order;
- and
- a digit unreversing unit, operatively coupled to the reversed-field sequence generator and responsive to a supplied associating signal that associates specific subfields of the least significant field generated by the reversed-field sequence generator with corresponding reversed digits based on the mix of radix values used by said multistage transform, said digit unreversing unit being for unreversing the bits of each such subfield which has a bit-width greater than one, thereby to produce the corresponding digit in nonreversed form.
An address generator for generating a sequence of digit reversed signals to be used in conjunction with an FFT transform of N sample points and a mix of sequential radices r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N, where radices r.sub.1 through r.sub.m can be all the same or any of radices r.sub.1 through r.sub.m can be different from another of said radices, the generator comprising:
- a reversed-field sequence generator for generating a series of binary-coded signals respectively representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, with the bits in the least significant field of size log.sub.2 N bits reversed from their natural order;
- and
- a digit unreversing unit, operatively coupled to the reversed-field sequence generator for associating subfields of the field generated by the reversed-field sequence generator with a specific reversed digit and unreversing the bits of each such subfield which has a bit-width greater than one, thereby to produce the corresponding digit in nonreversed form;
- where the digit unreversing unit includes a programable radix-defining means which is programmably configurable to define the individual values of each radix in said mix of sequential radices to correspond with a desired one of plural radix mixes satisfying r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N;
- the programable radix-defining means performing said function of associating subfields of the field generated by the reversed-field sequence generator with specific reversed digits.
An address generator for generating a sequence of digit reversed signals to be used in conjunction with an FFT transform of N sample points and a mix of sequential radices r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N, where N is variable and any of radices r.sub.1 through r.sub.m can be different from another of said radices, the generator comprising:
- a programmable reversed-field sequence generator, responsive to a stored size signal that indicates the value of N, for generating a series of binary-coded signals respectively representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, with the bits in the least significant field of size log.sub.2 N bits reversed from their natural order;
- and
- a digit unreversing unit, operatively coupled to the reversed-field sequence generator for associating each subfield of the field generated by the reversed-field sequence generator with a specific reversed digit and unreversing the bits of each such subfield which has a bit-width greater than one, thereby to produce the corresponding digit in nonreversed form;
- where the digit unreversing unit includes a programmable radix-defining means which is programmably configurable to define the individual values of each radix in said mix of sequential radices to any practical mix satisfying r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N;
- the programmable radix-defining means performing said function of associating subfields of the field generated by the reversed-field sequence generator with specific reversed digits.
A method for generating a sequence of digit reversed signals to be used in conjunction with an FFT transform of N sample points and a mix of sequential radices r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N, where N is variable and any of radices r.sub.1 through r.sub.m can be different from another of said radices, the method comprising the steps of:
- programming a programmable reversed-field sequence generator that is responsive to a supplied size signal indicating the value of N to generate a series of binary-coded signals respectively representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, with the bits in the least significant field of size log.sub.2 N bits reversed from their natural order;
- producing a radix-defining signal for associating each subfield of the field generated by the reversed-field sequence generator with a specific reversed digit that is associated with an individual radix in said mix of sequential radices r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N;
- said producing step also defining the value of each radix in said mix of sequential radices r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m ;
- and
- in response to the radix-defining signal, unreversing the bits of each such subfield which has a bit-width greater than one, thereby to produce the corresponding digit in nonreversed form.
An address generator for generating a sequence of digit reversed signals to be used in conjunction with a multistage transform of N sample points, said transform being characterized by a sequential mix of radix values satisfying r.sub.1 .multidot.r.sub.2 .multidot.r.sub.3 .multidot. . . . .multidot.r.sub.m =N, where N is a variable, the generator comprising:
- reversed-field sequence generating means, responsive to a supplied size signal indicating the value of the variable N, for generating a series of binary-coded signals respectively representing the natural sequence of integers, i=0, 1, 2, 3, . . . , N-1, with the bits in the least significant field of size log.sub.2 N bits that represent said natural sequence of integers being reversed from their natural order;
- and
- digit unreversing means, operatively coupled to the reversed-field sequence generating means and responsive to a supplied associating signal that associates specific subfields of the least significant field generated by the reversed-field sequence generator with corresponding reversed digits based on the sequential mix of radix values used by said multistage transform, said digit unreversing means being for unreversing the bits of each such subfield which has a bit-width greater than one, thereby to produce the corresponding digit in nonreversed form.
Dependencies are inferred from the claim text.