Patent Description:
A Fast Fourier Transform (FFT) is widely utilized in radar systems and communication systems. The FFT is a generic name for a class of efficient computations to implement a Discrete Fourier Transform (DFT) to map data from a time domain to a frequency domain. The FFT efficiently maps the data in the time domain to the frequency domain by dividing processing into multiple radix stages where each stage comprises one or more radix kernels to perform computations of the DFT. The radix kernels receive as few as two inputs, perform multiplications and additions on the inputs based on the computations of the DFT, and provide as few as two outputs. The outputs of a radix kernel of one stage are provided to a respective radix kernel of another stage until the data in the time domain is mapped to the frequency domain. <CIT> discloses an example of an FFT implementation.

The drawings are for the purpose of illustrating example embodiments, but it is understood that the embodiments are not limited to the arrangements and instrumentality shown in the drawings.

A Fast Fourier Transform (FFT) maps data in a time domain to a frequency domain based on computations of signed binary integers. A common way to improve resolution of the computations and efficiency is to perform the FFT using one or more radix kernels where a fixed shifting is applied to an input of the radix kernels and after an output of a butterfly of the radix kernels. In an example, the shifting of the input of the radix kernel is a fixed left shift of signed binary integers and the shifting after the output of the butterfly is a fixed right shift of signed binary integers. The left shifting makes lower bits of signed binary integers input to the butterfly and twiddle factor multiplier available for computations by the radix kernels and the right shifting shifts out least significant bits (LSBs) of signed binary integers resulting from the computations that are at a higher resolution than a resolution of the signed binary integers to be output by the radix kernel. The fixed shifting does not result in the computations being performed at an optimum resolution because the available resolution for a computation differs depending on a magnitude of the signed binary integers.

Embodiments disclosed herein describe an adaptive bit shifting of signed binary integers input to the radix kernel and after an output of the butterfly of the radix kernel based on a leading bits count of signed binary integers input to the radix kernel. The bit shifting improves resolution of computations performed by the butterfly and twiddle factor multiplier of the radix kernel. An adaptive left bit shifter is arranged prior to the twiddle factor multiplier and performs an adaptive left shift by N of signed binary integers received by the radix kernel. An adaptive right bit shifter is arranged after an output of the butterfly and performs an adaptive right shift by M of signed binary integers output by the butterfly. In examples, M and N are integers based on the leading bit count determined by a leading bit analyzer which analyzes the signed binary integers input to the radix kernel. The leading bit analyzer determines the leading bit count by identifying a signed binary integer of the signed binary integers input having a maximum absolute value, counting a number of contiguous most significant bits (MSBs) with a same value of the sign bit for the signed binary integer having a maximum absolute value, and subtracting one to arrive at the leading bit count. The shift N, M of the adaptive left bit shifter and adaptive right bit shifter of the radix kernel is set based on accessing a look up table which indicates the left shift and right shift for the leading bit count. The output of the radix kernel is then provided to another radix kernel in another stage of radix kernels to continue the FFT. In examples, the adaptive left bit shifter results in MSBs not needed to store the magnitude of the signed binary integer input to the radix kernel shifted out and corresponding <NUM> bit LSBs inserted for use in increasing resolution of computations by the radix kernel. Further, the adaptive right bit shifter may perform an adaptive right shift of the output of the butterfly to preserve a certain number of the LSBs associated with the computation performed by the radix kernel at a higher resolution and insertion of a <NUM> bit as an MSB of the signed binary integer for each right shift. Well-known instructions, protocols, structures, and techniques have not been shown in detail in order not to obfuscate the description.

<FIG> is an example signal processing system <NUM> for performing a Fast Fourier Transform (FFT) based on an adaptive bit shifting to map data in a time domain to a frequency domain in accordance with an embodiment. The signal processing system <NUM> comprises one or more radix stages <NUM> to perform the FFT which in an example may be three or more radix stages shown as radix stages <NUM>-<NUM> to <NUM>-<NUM>. The radix stages <NUM> may comprise one or more radix kernels as described below. Further, the signal processing system <NUM> may have a controller <NUM> which controls operation of the radix stage <NUM>, a lookup table (LUT) <NUM> with adaptive scaling capability as described in more detail below, and a leading bit analyzer <NUM>. Components of the signal processing system <NUM> may be each implemented using circuitry such as one or more of analog circuitry, mix signal circuitry, memory circuitry, logic circuitry, processing circuitry that executes code stored in a memory that when executed by the processing circuitry perform the disclosed functions, and combinations thereof.

The signal processing system <NUM> may be a component of another system such as a communication system or radar system (not shown) which receives data in a time domain and provides the data in the time domain to the signal processing system <NUM>. The data may be samples of a signal received from a transmitter in the case of the communication system or reflected off an object in the case of the radar system. The signal processing system <NUM> may perform the FFT of the data to map the data from the time domain into the frequency domain.

The FFT may be an efficient implementation of a Discrete Fourier Transformation (DFT) which transforms data in the time domain into the frequency domain. The DFT is represented as: <MAT> where X[k] is a DFT value for index k in the frequency domain, x[n] is an nth sample of data x in a time domain and L is the length of the data x. The DFT requires L complex multiplications and L*(L-<NUM>) complex additions to perform the transformation for an L-sample data in a time domain to the frequency domain.

To reduce the number of operations of the FFT, the signal processing system <NUM> may perform the FFT in one or more radix stages <NUM> to convert the data in the time domain to the frequency domain with fewer operations than the DFT. The FFT performed as the radix stages may begin with providing the data in the time domain to a first radix stage <NUM>-<NUM> as an input vector <NUM>. The first radix stage <NUM>-<NUM> may then output a result vector <NUM> which is then input into a second radix stage <NUM>-<NUM>. The second radix stage <NUM>-<NUM> may then process the result vector <NUM> and output a result vector <NUM> which is input to a third radix stage <NUM>-<NUM>. This process may continue until the data is transformed from the time domain into the frequency domain.

In examples, the input vector and the result vector may comprise complex numbers with an imaginary and real component each represented by a signed binary integer with a bit width W. In an example, the signed binary integer may be a two's complement signed binary integer. The signed binary integer may have a most significant bit (MSB) which indicates whether binary integer is a positive or a negative number. For example, an MSB which is a <NUM> bit may indicate that the integer is negative and an MSB which is a <NUM> bit may indicate that the integer is positive. Further, this sign bit is replicated in the binary integer to lower significant bits (LSB) not used to represent an absolute magnitude of the binary integer.

Computations of the radix stage <NUM> may be performed in terms of the signed binary integers. A common way to improve resolution of the computations is to scale the signed binary integers by a fixed shift operation. In an example, the scaling may include a fixed left shift operation and a fixed right shift operation. The left shift operation may include shifting out an MSB of the signed binary integer and insertion of <NUM> bits as an LSB of the signed binary integer for each left shift making lower bits of the signed binary integer available to perform the computations of the radix stage <NUM> at a higher resolution. The shifting by a fixed right shift operation is a fixed right shift operation to shift out LSB at the higher resolution to form a signed binary integer with a resolution of the signed binary integer prior to the fixed left shift operation.

The fixed shifting does not result in the computations of the radix stage <NUM> being performed at an optimum resolution because available bits for a computation differ depending on a magnitude of the signed binary integer. The fixed right shift further results in loss of resolution associated with the computation of the radix stage <NUM>.

Embodiments disclosed herein describe an adaptive left bit shift and adaptive right bit shift of signed binary integers based on a leading bits count of signed binary integers of a result vector input to the radix stage <NUM>. The adaptive bit shifting may improve resolution of computations performed by the radix stage <NUM>. The adaptive bit shifting may be an adaptive left shift of signed binary integers by N and an adaptive right shift by M of signed binary integers, where M and N are integers, based on the leading bit count. In an example, the leading bit analyzer <NUM> may receive a result vector <NUM> of the radix stage <NUM> which comprises signed binary integers. The leading bit analyzer <NUM> determines the leading bit count by identifying a signed binary integer of the signed binary integers input having a maximum absolute value, counting a number of contiguous MSBs with a same value of the sign bit for the signed binary integer having a maximum absolute value, and subtracting one to arrive at the leading bit count. For example, if the result vector includes <NUM> bit signed binary integer values, then a value of <NUM> with a <NUM> sign bit may include <NUM> leading bits and a value of -<NUM> with a <NUM> sign bit may include two leading bits. The controller <NUM> may access the look up table <NUM> based on the leading bit count to determine the adaptive left shift and the adaptive right shift for the result vector which is then input into a radix stage <NUM> along with an indication of the adaptive left shift and adaptive right shift provided by the controller <NUM>. In examples, the adaptive left shift results in MSBs not needed to store the magnitude of a signed binary integer in the result vector shifted out and corresponding <NUM> bit LSBs inserted for use in increasing resolution of computations by the radix stage <NUM>. Further, the adaptive right shift of the output vector preserves a certain number of the LSBs associated with the computation performed by the radix stage <NUM> at a higher resolution and insertion of a <NUM> bit as an MSB of the signed binary integer for each right shift.

In an example, the first radix FFT stage <NUM>-<NUM> may receive an indication of a fixed left shift and a fixed right shift shown as <NUM> left shift and <NUM> right shift. Subsequent radix stages such as radix FFT stage <NUM>-<NUM> and radix FFT stage <NUM>-<NUM> may receive an indication of the adaptive left shift and adaptive right shift based on accessing the look up table <NUM>. The radix FFT stage <NUM> which receives the indication of the adaptive left shift and adaptive right shift may depend on whether a leading bit count is available for the input vector or resultant vector input to the radix FFT stage <NUM>. In the example, the leading bit count may not be known for the input vector but known for the resultant vector, such that radix stage <NUM>-<NUM> and radix stage <NUM>-<NUM> receive an indication of the adaptive left shift and adaptive right shift but not radix stage <NUM>-<NUM>. Other variations are also possible.

<FIG> illustrates an example radix kernel <NUM> arranged with adaptive bit shifting in accordance with an embodiment. The signal processing system <NUM> may have one or more radix stages <NUM> and one or more radix kernels <NUM> in a radix stage <NUM>, shown as radix kernel <NUM>-<NUM> to <NUM>-<NUM> in an example. The radix kernel <NUM> of a radix stage <NUM> performs computations as described below to transform the data of the input vector <NUM> which is in the time domain into the frequency domain. A number of radix FFT stages <NUM> and a number of radix kernel <NUM> in a radix stage <NUM> to perform the FFT may depend on a number of complex numbers in a vector <NUM> (e.g., input vector or result vector) and a number of complex numbers received by each of the radix kernel <NUM> in each radix FFT stage <NUM>.

In an example, the radix kernel <NUM> may have an adaptive left bit shifter <NUM>, butterfly <NUM>, a twiddle factor multiplier <NUM>, an adaptive right bit shifter <NUM>, and a mapper <NUM> to perform computation of the FFT. Components of the radix kernel <NUM> may be each implemented using circuitry such as one or more of analog circuitry, mix signal circuitry, memory circuitry, logic circuitry, processing circuitry that executes code stored in a memory that when executed by the processing circuitry perform the disclosed functions, and combinations thereof.

Each radix kernel <NUM> may receive a subset of the complex numbers of the input vector or result vector. The radix kernel <NUM> may be one of a radix-<NUM> kernel (RDX2) and radix-<NUM> (RDX4) kernel in an example. The radix-<NUM> kernel consists of receiving two complex number inputs x0, x1 and performing two additions and two multiplications with a twiddle factor to produce two complex number output data y0, y1 in accordance with the equations y0=x0+t*x1 and y1=x0+t*x1 where "t" is referred to as a "twiddle factor. " The multiplications may be performed by the twiddle factor multiplier <NUM> of the radix kernel <NUM> and the additions may be performed by the butterfly <NUM> of the radix kernel <NUM>.

A L-sample FFT based on the radix-<NUM> kernel consists of Log(L) stages of radix <NUM> kernel where an output of a radix-<NUM> kernel of one radix stage is provided as an input of a radix-<NUM> kernel of another radix stage and each radix stage consists of L/<NUM> radix <NUM> kernels.

The radix-<NUM> kernel is even more computationally efficient than the radix-<NUM> kernel. The radix-<NUM> kernel receives four complex number inputs and provides four complex number outputs. A L-sample FFT based on the radix-<NUM> kernel requires fewer radix stages and fewer butterflies than using the radix-<NUM> kernel. For example, to calculate a <NUM>-point FFT, the radix-<NUM> kernel takes log<NUM>(<NUM>) or <NUM> stages, while the radix-<NUM> kernel takes only log<NUM>(<NUM>) or <NUM> radix stages.

In an example, the radix kernel <NUM> in the form of the radix-<NUM> kernel may receive as input signed binary integers of the real and imaginary components of the two complex numbers. The radix kernel <NUM> in the form of the radix-<NUM> kernel may receive as input signed binary integers of the real and imaginary components of four complex numbers. Similarly, the output of the radix-<NUM> kernel may be signed binary integers of the real and imaginary components of the two complex numbers and the output of the radix-<NUM> kernel may be signed binary integers of the real and imaginary components of the four complex numbers.

The adaptive left bit shifter <NUM> and an adaptive right bit shifter <NUM> may scale an input to the radix kernel <NUM> and output of the butterfly <NUM> to improve resolution of computations associated with the butterfly <NUM> and twiddle factor multiplier <NUM>. The input shown as I comprises complex numbers and a component of a complex number input into the radix kernel <NUM> may be a signed binary integer with a bit width W. In an example, the shifting of the input is a left shift operation by the adaptive left bit shift <NUM> of the signed binary integers of the input to improve resolution of the computation of the butterfly <NUM> and twiddle factor multiplier <NUM>. The left shift may comprise shifting out an MSB of the signed binary integer and insertion of <NUM> bits as an LSB of the signed binary integer for each left shift making lower bits of the signed binary integer available to perform the computations at a higher resolution. Computations by the radix kernel <NUM> may also be performed at a bit width B where B>W, but the output O of the radix kernel <NUM> may be bit width W. The shifting of the output of the butterfly <NUM> is a right shift operation by the adaptive right bit shifter <NUM> on the signed binary integers output by the butterfly <NUM> to shift LSBs out to preserving zero or more of the LSB at the higher resolution and insertion of a <NUM> bit as an MSB of the signed binary integer for each right shift. The range of right shifting may be based on a difference between the number of bits of the signed binary integer output by the butterfly B and the number of bits of the signed binary integer output by the radix kernel <NUM> W which is (B-W+<NUM>). The mapper <NUM> may then map the lower W bits of the B bit signed binary integers output of the butterfly to W bit signed binary integers which is output by the radix kernel <NUM> as output O of complex numbers having components of signed binary integers.

To illustrate, the radix kernel <NUM> may receive a <NUM> bit signed binary integer which is left shifted by four to form a <NUM> bit signed binary integer. The butterfly <NUM> may perform the butterfly based on the <NUM> bit signed binary integer. Then, the radix kernel <NUM> may perform a right shift. The right shift may shift out one LSB of the <NUM> bit signed binary integer for each right shift. A right shift of four may result in a <NUM> LSB being shifted out. The mapper <NUM> may then map the lower <NUM> bits of the <NUM> bit signed binary integers output of the butterfly to <NUM> bit signed binary integers which is output by the radix kernel <NUM>. In an example, the right shift may be a rounded right shift where the LSB of the <NUM> bit signed binary integer is rounded up if the <NUM> bits which are shifted out is greater than a value of <NUM> and otherwise not rounded up.

In an example, the left shift by the adaptive left bit shifter <NUM> may be a multiplication N in an example by a power of <NUM> and the right shift by the adaptive right bit shifter <NUM> may be a division M by a power of two. The controller <NUM> may select the N and M based on a number of leading bits associated with signed binary integers of the input to the radix kernel <NUM>. The left shift and right shift may be selected by the controller <NUM> accessing the look up table <NUM> which indicates the selected shift based on the number of leading bits. In an example, the N for the radix-<NUM> kernel and the radix-<NUM> kernel may be a power of <NUM> selected from <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, M for the radix-<NUM> kernel may be a power of <NUM> selected from <NUM>, <NUM>, <NUM>, and <NUM>, and M for the radix-<NUM> kernel may be a power of <NUM> selected from <NUM>, <NUM>, <NUM>, <NUM>, <NUM>.

In an example, the controller <NUM> may receive an instruction from higher level processing of the communication system to cause the radix kernel <NUM> to configure the adaptive left bit shifter <NUM> and the adaptive right bit shifter <NUM>. The instruction may indicate that the controller <NUM> is to set the adaptive left bit shifter <NUM> and the adaptive right bit shifter <NUM> with a shift value indicated by the look up table <NUM> and the number of leading bits of the signed binary integers input to the radix kernel <NUM>, in which the case the shifting is adaptive for the input and output of the radix kernel <NUM>. In some examples, the instruction may indicate whether only the adaptive right bit shifter <NUM> or both of the adaptive left bit shifter <NUM> or adaptive right bit shifter <NUM> may be adaptively set. A bit in the instruction may indicate whether or not the shifting is adaptive for both the adaptive left bit shifter <NUM> and adaptive right bit shifter <NUM> or only adaptive for the adaptive right bit shifter <NUM>. Other combinations of adaptive bit shifting are also possible.

<FIG> illustrates an example implementation of a radix kernel <NUM> in the form of radix-<NUM> kernel <NUM> in accordance with an embodiment. The radix-<NUM> kernel <NUM> may receive two complex number represented by <NUM> bit signed binary integers as input. The adaptive left bit shifter <NUM> may shift each of the <NUM> bit signed binary integers by a left shift which varies from N=<NUM> to <NUM>. In an example, processing of the radix-<NUM> kernel may include computations of the twiddle factor multiplier <NUM> and the butterfly <NUM> at a higher resolution than <NUM> bits and an output of the butterfly <NUM> may be two <NUM> bit signed binary integers based on the butterfly performing computations at the increased resolution. The adaptive right bit shifter <NUM> may shift the <NUM> bits of each signed binary integers which are received by a right shift which varies from M=<NUM> to <NUM> so that zero or more LSBs of the <NUM> bits after the right shift is LSBs of the <NUM> bit signed binary integers of the two complex numbers output by the radix-<NUM> kernel <NUM> by the mapper <NUM>. The left shift and right shift may be determined based on the leading bit count of the signed binary integers input to the radix-<NUM> kernel <NUM> and indicated by the look up table <NUM> to improve resolution of the computations of the radix-<NUM> kernel <NUM>.

To illustrate operation of the radix-<NUM> kernel <NUM>, the adaptive left bit shifter <NUM> may receive two complex numbers of signed binary integers of <NUM> bits. The two signed binary integers may have a minimum of <NUM> leading bits in the example and the adaptive left bit shifter <NUM> may shift the <NUM> bits of the input by a left shift which in this example is N=<NUM> bits to produce signed binary integers of <NUM> bits with <NUM> bits shifted in as LSBs set to zero to increase resolution of computations with the <NUM> bit signed binary integers. The computations of the twiddle factor multiplier <NUM> and the butterfly <NUM> may be performed at a higher resolution than <NUM> bits which results in the butterfly <NUM> outputting signed binary integers of <NUM> bits in this example. The adaptive right bit shifter <NUM> may shift each of the signed binary integers of <NUM> bits by a right shift which in this example is M=<NUM> bits. The <NUM> LSBs of the <NUM> bit signed binary integers is preserved. The <NUM> bit signed binary integers are then mapped to signed binary integers of <NUM> bits by the mapper <NUM> and the radix-<NUM> kernel <NUM> may output two complex numbers. The shifting may increase resolution of the computations of the radix-<NUM> kernel <NUM> by <NUM> bits, where <NUM> bits of resolution are added by each of the left shift and right shift in this example.

<FIG> illustrates a detailed example implementation of the radix kernel <NUM> in the form of the radix-<NUM> kernel <NUM> in accordance with an embodiment. The radix-<NUM> kernel <NUM> processes two inputs x0, x1 and provides two outputs y0, y1. Further, to process a vector of length L=<NUM>', L/<NUM> radix kernels may be needed per radix stage. The radix-<NUM> kernel <NUM> may include adaptive left bit shifters <NUM>, multipliers <NUM>, a butterfly <NUM>, and adaptive right bit shifters <NUM>. The input may be complex numbers. Further, the adaptive left bit shifters <NUM> may receive an indication of a left shift from the controller <NUM> and perform a left shift of components of the complex number input which is then provided to the multipliers <NUM> which perform a complex multiplication with a twiddle factor tn (where n is an integer) also input to the multipliers <NUM>. The output of the multipliers <NUM> is provided to the butterfly <NUM> which comprises summers <NUM> which performs a complex addition. An output of the butterfly <NUM> is input to adaptive right bit shifters <NUM> which also receives an indication of a right shift from the controller <NUM> and performs a right shift of the output of the butterfly <NUM>. The signed binary integers output by the adaptive right bit shifter <NUM> may be mapped to a signed binary integer with a bitwidth W and two complex numbers output by the radix-<NUM> kernel <NUM>.

<FIG> illustrates an example implementation of a radix kernel <NUM> in the form of radix-<NUM> kernel <NUM> in accordance with an embodiment. The radix-<NUM> kernel may receive four complex numbers represented by <NUM> bit signed binary integers as input. An adaptive left bit shifter <NUM> may shift each of the <NUM> bit signed binary integers by a left shift which varies from N=<NUM> to <NUM>. In an example, processing of the radix-<NUM> kernel <NUM> may include computations of the twiddle factor multiplier <NUM> and the butterfly <NUM> at a higher resolution than <NUM> bits and an output of the butterfly <NUM> may be <NUM> bit signed binary integers based on the butterfly performing computations at the increased resolution. An adaptive right bit shifter <NUM> may shift the <NUM> bits of each signed binary integers which are received by a right shift which varies from M=<NUM> to <NUM> so that zero or more LSBs of the <NUM> bits after the right shift is LSBs of the <NUM> bit signed binary integers of the four complex numbers output by the radix-<NUM> kernel <NUM> by the mapper <NUM>. The left shift and right shift may be determined based on the leading bit count of the signed binary integers input to the radix-<NUM> kernel <NUM> and indicated by the look up table <NUM> to improve resolution of the computations of the radix-<NUM> kernel <NUM>.

To illustrate operation of the radix-<NUM> kernel <NUM>, the adaptive left bit shifter <NUM> may receive four complex numbers of signed binary integers of <NUM> bits. The signed binary integers may have a minimum of <NUM> leading bits in the example and the adaptive left bit shifter <NUM> may shift the <NUM> bits of the input by a left shift which in this example is M=<NUM> bits to produce signed binary integers of <NUM> bits with <NUM> bits shifted in as LSBs set to zero to increase resolution of computations with the <NUM> bit signed binary integers. The computations of the twiddle factor multiplier <NUM> and the butterfly <NUM> may be performed at a higher resolution than <NUM> bits which results in the butterfly <NUM> outputting signed binary integers of <NUM> bits in this example. The adaptive right bit shifter <NUM> may shift each of the signed binary integers of <NUM> bits by a right shift which in this example is N=<NUM> bits to produce signed binary integers of <NUM> bit. The <NUM> LSBs of the <NUM> bit signed binary integers is preserved. The <NUM> bit signed binary integers is then mapped to signed binary integers of <NUM> bits by the mapper <NUM> and the radix-<NUM> kernel <NUM> may output four complex numbers. The shifting may increase resolution of the computations of the radix kernel <NUM> by <NUM> bits, where <NUM> bits of resolution is added by the left shift and four bits of resolution is added by the right shift in this example.

<FIG> illustrates a detailed example implementation of the radix kernel <NUM> in the form of a radix-<NUM> kernel <NUM> in accordance with an embodiment. The radix-<NUM> kernel <NUM> processes four inputs x0, x1, x2, x3 and provides four outputs y0, y1, y2, and y3. Further, to process a vector of length L=<NUM>n, L/<NUM> radix kernels may be needed per radix stage. The radix-<NUM> kernel <NUM> may include adaptive left bit shifters <NUM>, multipliers <NUM>, a butterfly <NUM>, and adaptive right bit shifters <NUM>. The input may be complex numbers. Further, the adaptive left bit shifters <NUM> may receive an indication of a left shift from the controller <NUM> and perform a left shift of components of the complex number input which is then provided to the multipliers <NUM> which perform a complex multiplication with a twiddle factor tn (where n is an integer) also input to the multipliers <NUM>. The output of the multipliers <NUM> is provided to the butterfly <NUM> which comprises summers <NUM> which performs a complex addition. An output of the butterfly <NUM> is input to adaptive right bit shifters <NUM> which also receives an indication of a right shift from the controller <NUM> and performs a right shift of the output of the butterfly <NUM>. The signed binary integers output by the adaptive right bit shifter <NUM> may be mapped to a bitwidth W and four complex numbers output by the radix-<NUM> kernel <NUM>.

<FIG> illustrates example lookup tables <NUM>-<NUM> which the controller <NUM> accesses to set the adaptive left bit shifter <NUM> and adaptive right bit shifter <NUM> for the radix kernel <NUM> in accordance with an embodiment. In an example, the lookup table <NUM> may be stored in a memory of the signal processing system <NUM>.

Table <NUM> may be used to select a left shift of the adaptive left bit shifter <NUM> of the radix-<NUM> kernel <NUM> and a right shift of the adaptive right bit shifter <NUM> of the radix-<NUM> kernel <NUM>. The table <NUM> may indicate left shift (inLSH) and right shift (outRSH) based on a leading bit count (CLB) associated with an output of a previous stage which is an input to the radix-<NUM> kernel <NUM>. For example, the table <NUM> may indicate that if the input to the radix-<NUM> kernel <NUM> has <NUM> leading bits, then the left shift of the adaptive left bit shifter <NUM> may be set to N=<NUM> and the right shift of the adaptive right bit shifter <NUM> may be set to M=<NUM>. The left shift of <NUM> may increase resolution of computations by the radix-<NUM> kernel <NUM> by two bit and the right shift of zero may increase resolution by <NUM> bits because the LSBs of the <NUM> bits when mapped to the <NUM> bits is preserved. The table <NUM> may further indicate that as a result of the shifting the resolution of the radix-<NUM> kernel <NUM> is improved by +<NUM> bits. In another example, the table <NUM> may indicate that the input to the radix-<NUM> kernel <NUM> has <NUM> leading bits and the left shift for the adaptive left bit shifter <NUM> may be set to N=<NUM> and the right shift of the adaptive right bit shifter <NUM> may be set to M=<NUM>. The left shift of <NUM> may not increase resolution because any increase in resolution may result in saturation of the computation in the radix-<NUM> kernel <NUM> in this example. The right shift of <NUM> may result in an increase in resolution of +<NUM> bits after the LSB of the <NUM> bits is mapped to a <NUM> bit signed binary integer. The table <NUM> may further indicate that as a result of the shifting the output improves resolution by +<NUM> bits.

Table <NUM> may be used to select a left shift of the adaptive left bit shifter <NUM> of the radix-<NUM> kernel <NUM> and a right shift of the adaptive right bit shifter <NUM> of the radix-<NUM> kernel <NUM>. The table <NUM> may indicate left shift and right shift based on a leading bit count associated with an output of a previous stage which is the input to the radix-<NUM> kernel <NUM>. For example, the table <NUM> may indicate that if the input to the radix-<NUM> kernel <NUM> has <NUM> leading bits, then the left shift of the adaptive left bit shifter <NUM> may be set to N=<NUM> and the right shift of the adaptive right bit shifter <NUM> may be set to M=<NUM>. The left shift of <NUM> may increase resolution of computations by the radix-<NUM> kernel <NUM> by three bit and the right shift of zero may increase resolution by <NUM> bits because the LSBs of the <NUM> bits when mapped to the <NUM> bits is preserved. The table <NUM> may further indicate that as a result of the shifting the resolution of the radix-<NUM> kernel <NUM> is improved by +<NUM> bits. In another example, the table <NUM> may indicate that the input to the radix-<NUM> kernel <NUM> has <NUM> leading bits and the left shift for the adaptive left bit shifter <NUM> may be set to N=<NUM> and the right shift of the adaptive right bit shifter <NUM> may be set to M=<NUM>. The left shift of <NUM> may not increase resolution. The right shift of <NUM> may result in an increase in resolution of +<NUM> bits after the LSB of the <NUM> bits is mapped to a <NUM> bit signed binary integer. The table <NUM> may further indicate that as a result of the shifting the output improves resolution by +<NUM> bit.

In examples, the look up table <NUM> may take other forms. For example, the input left shift or output right shift may be greater than four for a leading bit count. Further, the look up table <NUM> may have a same left shift and right shift for zero and one leading bit count as shown in table <NUM> for a radix-<NUM> kernel <NUM> and table <NUM> for a radix-<NUM> kernel <NUM> to avoid a magnitude of a complex number after left and right shifting exceeding <NUM>. A shift of signed binary integers of the real and imaginary components of a complex number to full resolution (<NUM> bit signed integer needed to represent the magnitude) may lead to a maximum magnitude of <NUM> for each component of a complex number after radix kernel processing which results in a magnitude of the complex number exceeding a unit circle. To avoid this, additional resolution of the signed binary integers with B bit width is not preserved unless two or more leading bits are available in the signed binary integer. The signed binary integer of the real and imaginary components of a complex number are shifted so that the magnitude for each component of the complex number after the radix kernel processing will have a maximum magnitude of the complex number of <NUM> (<NUM> bit signed integer needed to represent the magnitude). Other variations are also possible.

<FIG> illustrates an example operation <NUM> of a plurality of radix stages <NUM>-<NUM> to perform the FFT in accordance with an embodiment. In this example, the radix kernel <NUM> in each stage may be a radix-<NUM> kernel <NUM> and an output of one radix stage may be an input to another radix stage.

The input which is provided to the radix stage <NUM> may be complex numbers defined by <NUM> bit signed binary integers. In this example, the <NUM> bits may represent an input value of range of - <NUM> to <NUM> stored as <NUM> bits of the <NUM> bits which means that the most significant <NUM> bits of the <NUM> bits are not used to represent the input value. In the first radix stage <NUM>, no input shifting may be performed on the input and a fixed right shift of four may be applied to the output of the butterfly <NUM>. Each of the <NUM> bit signed binary integers output by the butterfly <NUM> of the radix-<NUM> kernel <NUM> may be mapped to <NUM> bits. If the output of the butterfly <NUM> is signed binary integers in the range of -<NUM> to <NUM>, then the <NUM> bit signed binary integers output may have <NUM> leading bits.

The radix stage <NUM> may receive the signed binary integers output from the first radix stage <NUM>. In the radix stage <NUM>, the adaptive left bit shifting and adaptive right bit shifting may be based on the leading bits count of the <NUM> bit signed binary integers output from the first stage <NUM> which is now input to the radix stage <NUM>. In this example, the output of the <NUM> bit signed binary integers from the radix stage <NUM> which is input to the radix stage <NUM> may have <NUM> leading bits. An example look-up table may indicate a left shift of <NUM> for the adaptive left bit shifter <NUM> and a right shift of <NUM> for the adaptive right bit shifter <NUM> which results in an increase of resolution of <NUM> of the <NUM> bit signed binary integers output by the radix stage <NUM> for a total increase of resolution of <NUM> of the FFT. Further, in an example, the <NUM> bit signed binary integers output may have values ranging from -<NUM>,<NUM> to <NUM>,<NUM> represented by <NUM> bits. The <NUM> bit signed binary integers output may have <NUM> leading bits.

The radix stage <NUM> may receive the <NUM> bit signed binary integers output from the second radix stage <NUM>. In the radix stage <NUM>, the adaptive left bit shifting and adaptive right bit shifting may be based on the number of leading bits in the <NUM> bit signed binary integers output from the second radix stage <NUM>. In this example, the <NUM> bit signed binary integers output from the second radix stage <NUM> which is input to the third radix stage <NUM> may have <NUM> leading bits. The example look-up table may indicate a left shift of <NUM> for the adaptive left bit shifter <NUM> and a right shift of <NUM> for the adaptive right bit shifter <NUM> which results in an increase of resolution of <NUM> of the <NUM> bit signed binary integers output by the radix stage <NUM> to a total increase in resolution of <NUM> of the FFT. Further, in an example, the <NUM> bit signed binary integers output may have values ranging from -<NUM>,<NUM>,<NUM> to <NUM>,<NUM>,<NUM> represented by <NUM> bits. The <NUM> bit signed binary integers output may have <NUM> leading bit. This process may be repeated for additional stages until the FFT is completed.

In an example, a total accumulation of resolution determined by the radix stages may be used to process the frequency domain representation of the input provided to the signal processing system <NUM>. The total accumulation may be an indication of scaling of the frequency domain representation and is accounted for subsequent processing of the frequency domain representation.

<FIG> & <FIG> are flow charts of example functions associated with performing the FFT based on the radix kernel <NUM> with adaptive bit shifting in accordance with an embodiment. In a radix kernel <NUM> of first radix stage, a fixed left shift may be applied to signed binary integers with a bit width of <NUM> bits input to the radix kernel <NUM> at <NUM> in <FIG>. At <NUM>, a butterfly <NUM> and a twiddle factor multiplier <NUM> is executed based on the fixed left shifted input. At <NUM>, a fixed right shift is applied to signed binary integers of an output of the butterfly <NUM>. The output of the butterfly <NUM> may be signed binary integers with a bit width greater than the bit width of the input to the radix kernel <NUM> such as <NUM> bits. At <NUM>, signed binary integers of the fixed right shifted output is mapped to signed binary integers with the bit width smaller than the output of the butterfly of the first stage such as <NUM> bits which is output by the radix kernel <NUM>. At <NUM>, a number of leading bits in the signed binary integers of the output of the first radix stage is counted. The number of leading bits may be for a signed binary integer with maximum absolute magnitude of the output of the first radix stage.

The output of the radix kernel <NUM> which is signed binary integers may be provided to a second radix stage as an input to the second radix stage. Referring to <FIG>, at <NUM>, an adaptive left shift and an adaptive right shift is determined from the look up table <NUM> based on the leading bit count associated with the output of the first stage which is now input to the second radix stage. At <NUM>, the adaptive left shift is applied to the signed binary integers output by a previous radix stage now input to a current radix stage. If the previous radix stage is the first stage, then current radix stage is the second radix stage which receives the output of the first stage. At <NUM>, the butterfly <NUM> and twiddle factor multiplier <NUM> is executed on the adaptive left shifted input. At <NUM>, the adaptive right shift indicated by the look up table <NUM> is applied to signed binary integers of the output of the butterfly <NUM> of the second stage. At <NUM>, the shifted output of the butterfly is mapped to signed binary integers with the bit width smaller than the output of the butterfly of the second stage such as <NUM> bits which is output by the radix kernel <NUM>. At <NUM>, a number of leading bits in the signed binary integers of the output of the second radix stage is counted. The number of leading bits may be for a signed binary integer with maximum absolute magnitude of the output of the second radix stage. Processing then returns to perform the radix kernel <NUM> in a subsequent radix stage if additional stages are to be processed until the FFT of the input to the first radix stage is completed.

In some examples, the leading bit count of the input to the first radix kernel in a first stage may be counted. In this case, an adaptive left shift and adaptive right shift may be determined and applied to the input and output of the butterfly rather than applying a fixed left shift and fixed right shift in the first radix stage.

In one embodiment, a method is disclosed for performing a Fast Fourier Transformation (FFT). The method comprises: receiving a first input at a first radix kernel of the FFT comprising signed binary integers, the signed binary integers of the first input each representing a component of a complex number associated with a time domain signal and having a bit width; applying a fixed left shift to the signed binary integers of the first input; performing a first radix kernel operation on the shifted first input at a higher bit resolution than the bit width; applying a fixed right shift to signed binary integers of an output of a butterfly of the first radix kernel operation which are mapped to the bit width to provide a first output of the first stage of the FFT; determining a leading bit count of signed binary integers in the first output; receiving the first output at a second radix kernel of the FFT which is a second input to the second radix kernel; applying an adaptive left shift to signed binary integers of the second input based on the leading bit count; performing a second radix kernel operation on the shifted second input at the bit resolution higher than the bit width; and applying an adaptive right shift based on the leading bit count to signed binary integers of an output of a butterfly of the second radix kernel operation which is mapped to the bit width to provide a second output of the second stage of the FFT; wherein the adaptive left shift and adaptive right shift determines a resolution of the FFT. In an example, the method further comprises providing an output of one radix kernel to an input of another radix kernel until the first input is transformed into the frequency domain. In an example, determining the leading bit count in the first output comprises counting a contiguous number of most significant bits which is the same as the sign bit in a signed binary integer of the first output which has a maximum absolute magnitude. In an example, the signed binary integers of the first output and the second output have the bit width. In an example, the first output and the second output comprise complex numbers each having components of signed binary integers. In an example, the first input, first output, and second output each comprises two complex numbers and the radix kernel is a radix-<NUM> kernel. In an example, the first input, first output, and second output each comprises four complex numbers and the radix kernel is a radix-<NUM> kernel. In an example, a number of the adaptive left shift is less than or equal to the leading bit count. In an example, a number of the adaptive right shift is less than or equal to a difference between the bit resolution higher than the bit width and the bit width. In an example, applying the adaptive right shift comprises accessing a lookup table which indicates a number of right shift based on the leading bit count applied to a signed binary integer of the output of the first radix kernel operation. In an example, applying the adaptive left shift comprises accessing the lookup table which indicates a number of left shift based on the leading bit count applied to a signed binary integer of the output of the first radix kernel operation.

In another embodiment, a signal processing system for performing a Fast Fourier Transformation (FFT) is disclosed. The system comprises: a first stage of the FFT which has a first radix kernel arranged to receive a first input comprising signed binary integers, the signed binary integers of the first input each representing a component of a complex number associated with a time domain signal and having a bit width; apply a fixed left shift to the signed binary integers of the first input; performing a first radix kernel operation on the shifted first input at a bit resolution higher than the bit width; apply a fixed right shift to signed binary integers of an output of a butterfly of the first radix kernel operation which is mapped to the bit width to provide a first output of the first stage of the FFT; and determine a leading bit count of signed binary integers in the first output; a second stage of the FFT which has a second radix kernel arranged to receive the first output which is a second input to the second radix kernel; apply an adaptive left shift to signed binary integers of the second input based on the leading bit count; perform a second radix kernel operation on the shifted second input at the bit resolution higher than the bit width; and apply an adaptive right shift based on the leading bit count to signed binary integers of an output of a butterfly of the second radix kernel operation which is mapped to the bit width to provide a second output of the second stage of the FFT; wherein the adaptive left shift and adaptive right shift determines a resolution of the FFT. In an example, the first radix kernel operation and the second radix kernel operation comprise a Discrete Fourier Transform (DFT). In an example, the butterfly comprises partial computations of the DFT. In an example, the first radix kernel arranged to determine the leading bit count in the first output comprises the first radix kernel arranged to count a contiguous number of identical most significant bits which is the same as the sign bit in a signed binary integer of the first output which has a maximum absolute magnitude. In an example, the first output and the second output comprise complex numbers each having components of signed binary integers. In an example, a number of the adaptive left shift is less than or equal to the leading bit count. In an example, a number of the adaptive right shift is less than or equal to a difference between the bit resolution higher than the bit width and the bit width. In an example, the second stage arranged to apply the adaptive right shift comprises a controller arranged to access a lookup table which indicates a number of right shift based on the leading bit count applied to a signed binary integer of the output of the first radix kernel operation. In an example, the second stage arranged to apply the adaptive left shift comprises a controller arranged to access the lookup table which indicates a number of left shift based on the leading bit count applied to a signed binary integer of the output of the first radix kernel operation.

A few implementations have been described in detail above, and various modifications are possible. The disclosed subject matter, including the functional operations described in this specification, can be implemented in electronic circuitry, computer hardware, firmware, software, or in combinations of them, such as the structural means disclosed in this specification and structural equivalents thereof: including potentially a program operable to cause one or more data processing apparatus such as a processor to perform the operations described (such as a program encoded in a non-transitory computer-readable medium, which can be a memory device, a storage device, a machine-readable storage substrate, or other physical, machine readable medium, or a combination of one or more of them).

While this specification contains many specifics, these should not be construed as limitations on the scope of what may be claimed, but rather as descriptions of features that may be specific to particular implementations.

Similarly, while operations are depicted in the drawings in a particular order, this
should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. Moreover, the separation of various system components in the implementations described above should not be understood as requiring such separation in all implementations.

Use of the phrase "at least one of" preceding a list with the conjunction "and" should not be treated as an exclusive list and should not be construed as a list of categories with one item from each category, unless specifically stated otherwise. A clause that recites "at least one of A, B, and C" can be infringed with only one of the listed items, multiple of the listed items, and one or more of the items in the list and another item not listed.

Claim 1:
A method for performing a Fast Fourier Transformation (FFT), the method comprising:
receiving a first input at a first radix kernel of the FFT comprising signed binary integers, the signed binary integers of the first input each representing a component of a complex number associated with a time domain signal and having a bit width;
applying a fixed left shift to the signed binary integers of the first input;
performing a first radix kernel operation on the shifted first input at a bit resolution higher than the bit width;
applying a fixed right shift to signed binary integers of an output of a butterfly of the first radix kernel operation which are mapped to the bit width to provide a first output of the first stage of the FFT;
determining a leading bit count of signed binary integers in the first output;
receiving the first output at a second radix kernel of the FFT which is a second input to the second radix kernel;
applying an adaptive left shift to signed binary integers of the second input based on the leading bit count;
performing a second radix kernel operation on the shifted second input at the bit resolution higher than the bit width; and
applying an adaptive right shift based on the leading bit count to signed binary integers of an output of a butterfly of the second radix kernel operation which are mapped to the bit width to provide a second output of the second stage of the FFT;
wherein the adaptive left shift and adaptive right shift determines the bit resolution of the FFT.