PROJECTION ALGORITHMS FOR DISCRETE FOURIER TRANSFORM TWIDDLE FACTORS GENERATION

Abstract

The present invention is related to Discrete Fourier Transform (DFT) Twiddle Factors (TFs) generation algorithms. It presents New Projection Algorithms (NPAs) to generate any required TF of the DFT matrix by providing only a small stored portion of the TFs that are stored in a Memory Storage (MS). The present invention presents how to exploit the existence of symmetries and the existence of similarities among the TFs of the DFT matrix to construct a methodology of operation to be able to formulate the NPAs. The use of the NPAs will avoid the need of retrieving that required TF from pre-saved lookup tables of the DFT matrix and also will avoid the need to calculate it with slow complicated algorithms like CORDIC as used by prior arts.

Claims

1. A new DFT TFs projection algorithms comprising the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306 and the NPA-4 401 of EMB-4 406 are presented to generate any required IT of the DFT matrix by providing only a small portion of the TFs that are stored in an MS.

2. The present invention presents how to exploit the existence of symmetries and similarities among the TFs of the DFT matrix to construct a methodology of operation to be able to formulate the DFT TFs NPAs of claim 1.

3. The DFT TFs NPAs of claim 1 will generate any required TF of the DFT matrix that will avoid the need of retrieving that TF from pre-saved lookup tables of the DFT matrix and also will avoid the need to calculate it with slow complicated algorithms like CORDIC as used by prior arts.

4. The DFT TFs NPAs of claim 1 are very efficient due to their low MS requirements, high speed and low power consumption. Such efficiency is vital for real time computation of the DFT with large number of samples in the time domain to be transformed to frequency domain.

5. The NPA-1 101 of EMB-1 106 of claim 1 will require only N stored TFs in an MS to generate any required TF of the N.sup.2 DFT matrix that will reduce the MS requirements by a factor of $\left(1-\frac{1}{N}\right)\times 100\%.$ The NPA-1 works for any odd or even value of N.

6. The NPA-2 201 of EMB-2 206 of claim 1 requires only $\left(.Math.\frac{N}{2}.Math.+1\right)$ stored TFs in an MS to generate any required TF of the N.sup.2 DFT matrix that will reduce the MS requirements by a factor of $\left(1-\frac{\left(.Math.\frac{N}{2}.Math.+1\right)}{N^2}\right)\times 100\%.$ The NPA-2 works for any odd or even value of N.

7. The NPA-3 301 of EMB-3 306 of claim 1 requires only $\left(\frac{N}{2}+1\right)$ stored TFs in an MS to generate any required TF of the N.sup.2 DFT matrix that will reduce the MS requirements by a factor of $\left(1-\frac{\left(\frac{N}{2}+1\right)}{N^2}\right)\times 100\%.$ The NPA-3 works only for any even value of N.

8. The NPA-4 401 of EMB-4 406 of claim 1 requires only $\left(.Math.\frac{N}{4}.Math.+1\right)$ stored TFs in an MS to generate any required TF of the N.sup.2 DFT matrix that will reduce the MS requirements by a factor of $\left(1-\frac{\left(.Math.\frac{N}{4}.Math.+1\right)}{N^2}\right)\times 100\%.$ The NPA-4 works only for any even value of N.

9. The DFT TFs NPAs of claim 1 including the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306 and the NPA-4 401 of EMB-4 406 can also be easily adapted and used to calculate the TFs needed to calculate the IDFT.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0029] FIG. 1 is the schematic block diagram of operation of EMB-1 of the present invention.

[0030] FIG. 2 is the schematic block diagram of operation of EMB-2 of the present invention.

[0031] FIG. 3 is the schematic block diagram of operation of EMB-3 of the present invention.

[0032] FIG. 4 is the schematic block diagram of operation of EMB-4 of the present invention.

[0033] FIG. 5 is the flowchart diagram of the NPA-1 of EMB-1 of the present invention.

[0034] FIG. 6 is the flowchart diagram of the NPA-2 of EMB-2 of the present invention.

[0035] FIG. 7 is the flowchart diagram of the NPA-3 of EMB-3 of the present invention.

[0036] FIG. 8 is the flowchart diagram of the NPA-4 of EMB-4 of the present invention.

[0037] FIG. 9 is the simulated comparison result plot of the Minimum Number of Required TFs (MNRTF) computations (logarithmic scale) versus the number of points N (logarithmic scale) for the NPA-1 of EMB-1, the NPA-2 of EMB-2, the NPA-3 of EMB-3, the NPA-4 of EMB-4 of the present invention and the DFT.

[0038] FIG. 10 is the simulated comparison result plot of the MNRTF computations (logarithmic scale) versus the number of points N (linear scale) for the NPA-1 of EMB-1, the NPA-2 of EMB-2, the NPA-3 of EMB-3, the NPA-4 of EMB-4 of the present invention and the DFT.

[0039] FIG. 11 is the simulated comparison result plot of the Twiddles Percentage Ratio (TPR) of the MNRTF computations (logarithmic scale) versus the number of points N (logarithmic scale) for the NPA-1 of EMB-1, the NPA-2 of EMB-2, the NPA-3 of EMB-3, the NPA-4 of EMB-4 of the present invention and the DFT.

[0040] FIG. 12 is the simulated comparison result plot of the TPR of the MNRTF computations (logarithmic scale) versus the number of points N (linear scale) for the NPA-1 of EMB-1, the NPA-2 of EMB-2, the NPA-3 of EMB-3, the NPA-4 of EMB-4 of the present invention and the DFT.

[0041] FIG. 13 is the simulated comparison result plot of the Percentage Memory Reduction Ratio (PMRR) computations (linear scale) versus the number of points N (logarithmic scale) for the NPA-1 of EMB-1, the NPA-2 of EMB-2, the NPA-3 of EMB-3, the NPA-4 of EMB-4 of the present invention and the DFT.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0042] The N complex valued numbers, generated by the DFT for the time-sampled signal x.sub.n, are shown in Eq.(1).

[00008]$\begin{array}{cc}{X}_k=\underset{n=0}{\overset{N-1}{.Math.}}{X}_n\times e^{\left(\frac{-j2\pi \times \left(n\times k\right)}{N}\right)}=\underset{n=0}{\overset{N-1}{.Math.}}{X}_n\times W_N^{\left(n\times k\right)}\forall n,k\in \psi =\left\{0,1,2,.Math.,\left(N‐1\right)\right\}\wedge \forall N\in {\rho }_1\wedge \forall X_k,x_n\in ℂ& \left(1\right)\end{array}$

[0043] The N complex valued numbers generated by the Inverse DFT (IDFT) for the frequency-sampled X.sub.k are shown in Eq.(2).

[00009]$\begin{array}{cc}{X}_n=\underset{k=0}{\overset{N-1}{.Math.}}{X}_k\times e^{\left(\frac{j2\pi \times \left(n\times k\right)}{N}\right)}=\underset{k=0}{\overset{N-1}{.Math.}}{X}_k\times W_N^{\left(-\left(n\times k\right)\right)}\forall n,k\in \psi \wedge \forall N\in {\rho }_1\wedge \forall X_k,x_n\in ℂ& \left(2\right)\end{array}$

[0044] where:

[0045] X.sub.k are the frequency harmonics.

[0046] x.sub.n are the signal time samples.

[0047] k is the index in the frequency domain.

[0048] n is the index in the time domain.

[0049] is a complex number.

[0050] j=√{square root over (−1)}.

[0051] Equation (3) presents W.sub.N, which is the principal N.sup.th root of unity of Eq.(1) and Eq.(2).

[00010]$\begin{array}{cc}{W}_N=e^{\left(\frac{-j2\pi }{N}\right)}=\cos \left(\frac{2\pi }{N}\right)-j\sin \left(\frac{2\pi }{N}\right)\forall N\in {\rho }_1\wedge \forall W_N\in ℂ& \left(3\right)\end{array}$

[0052] The matrix form of Eq.(1) is shown in Eq.(4). Equation (4) shows the DFT matrix.

[0053] The compact DFT matrix form of Eq.(4) is shown in Eq.(5).

[00011]$\begin{array}{cc}\left[\begin{array}{c}{X}_0\\ X_1\\ X_2\\ .Math.\\ X_{N-1}\end{array}\right]=\left[\begin{array}{ccccc}{W}_N^{\left(0\times 0\right)}& W_N^{\left(0\times 1\right)}& W_N^{\left(0\times 2\right)}& .Math.& W_N^{\left(0\times \left(N-1\right)\right)}\\ W_N^{\left(1\times 0\right)}& W_N^{\left(1\times 1\right)}& W_N^{\left(1\times 2\right)}& .Math.& W_N^{\left(1\times \left(N-1\right)\right)}\\ W_N^{\left(2\times 0\right)}& W_N^{\left(2\times 1\right)}& W_N^{\left(2\times 2\right)}& .Math.& W_N^{\left(2\times \left(N-1\right)\right)}\\ .Math.& .Math.& .Math.& \ddots & .Math.\\ W_N^{\left(\left(N-1\right)\times 0\right)}& W_N^{\left(\left(N-1\right)\times 1\right)}& W_N^{\left(\left(N-1\right)\times 2\right)}& .Math.& W_N^{\left(\left(N-1\right)\times \left(N-1\right)\right)}\end{array}\right]\times \left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ .Math.\\ x_{N-1}\end{array}\right]\forall X,x,W_N\in ℂ\wedge \forall N\in {\rho }_1& \left(4\right)\end{array}$$\begin{array}{cc}\left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ .Math.\\ x_{N-1}\end{array}\right]=\left[\begin{array}{ccccc}{W}_N^{\left(0\right)}& W_N^{\left(0\right)}& W_N^{\left(0\right)}& .Math.& W_N^{\left(0\right)}\\ W_N^{\left(0\right)}& W_N^{\left(1\right)}& W_N^{\left(2\right)}& .Math.& W_N^{\left(N-1\right)}\\ W_N^{\left(0\right)}& W_N^{\left(2\right)}& W_N^{\left(4\right)}& .Math.& W_N^{\left(2\times \left(N-1\right)\right)}\\ .Math.& .Math.& .Math.& \ddots & .Math.\\ W_N^{\left(0\right)}& W_N^{\left(\left(N-1\right)\times 1\right)}& W_N^{\left(\left(N-1\right)\times 2\right)}& .Math.& W_N^{\left(\left(N-1\right)\times \left(N-1\right)\right)}\end{array}\right]\times \left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ .Math.\\ x_{N-1}\end{array}\right]\forall X,x,W_N\in ℂ\wedge \forall N\in {\rho }_1& \left(5\right)\end{array}$

[0054] When an integer number A is divided by another integer number B as shown in Eq.(6), the modulo's operation result is the remainder R. The modulo operator is denoted by the symbol as presented in Eq.(7).

[00012]$\begin{array}{cc}\frac{A}{B}=Q\mathrm{and}\mathrm{the}\mathrm{remainder}\mathrm{is}R& \left(6\right)\end{array}$$\begin{array}{cc}{B}_{\left(A\right)}^{}=R& \left(7\right)\end{array}$

[0055] Where:

[0056] A is the dividend, A ∈ ={ . . . , −2, −1, 0, 1, 2, . . . }.

[0057] B is the divisor, B ∈ \{0}.

[0058] Q is the quotient, Q ∈ .

[0059] R is the remainder, R ∈ φ={0, 1, 2, . . . , (B−1)}.

Embodiment-1

[0060] In EMB-1 106 of the present invention as shown in FIG. 1, we are going to find the formulation for the NPA-1 101 that will enable us to generate any required TF W.sub.N.sup.(n×k) 102 of the DFT matrix.

[0061] Instead of storing the N.sup.2 TFs that are needed to calculate the DFT which require large MS requirements, only N TFs that are members of the set ζ.sub.1{W.sub.N.sup.(0), W.sub.N.sup.(1), . . . , W.sub.N.sup.(N−1)} ∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈ are needed to be stored in an MS 103.

[0062] The NPA-1 101 will be used to project a specific value to the required TF W.sub.N.sup.(n×k) 102 from one of the N TFs of the ζ.sub.1 104 vector that is stored in an MS 103.

[0063] The outcome 105 of the NPA-1 101 will be the projected required TF W.sub.N.sup.(n×k) 102.

[0064] The NPA-1 PE formulation is presented below.

[0065] The property shown in Eq.(8) is the PE of EMB-1 106 and it will be used to design the NPA-1.

W.sub.N.sup.(n×k)=⁽⁸⁾

∀n,k,.sub.N.sup.(n×k)∈ψ{circumflex over ( )}∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈

[0066] By using Eq.(8), we can project a specific value to the required TF W.sub.N.sup.(n×k) 102 from one of the N TFs of the ζ.sub.1 104 vector.

[0067] The MS arrangement of the NPA-1 is presented below.

[0068] FIG. 1 shows how the elements of the set ζ.sub.1 are pre-calculated, arranged and stored in an MS 103 to construct the ζ.sub.1 104 TFs vector.

[0069] The N elements of the ζ.sub.1 104 TFs vector are constructed according to Eq.(9).

[00013]$$\begin{gathered} \begin{array}{cc}{\zeta }_1\left[G_1\right]=W_N^{\left(G_1\right)}=\cos \left(\frac{2\pi }{N}\times G_1\right)-j\sin \left(\frac{2\pi }{N}\times G_1\right) \\ \forall G_1\in \psi \wedge \forall N\in {\rho }_1\wedge \forall W_N\in ℂ& \left(9\right)\end{array} \end{gathered}$$

[0070] The memory location index of the ζ.sub.1 104 TFs vector is G.sub.1.

[0071] The NPA-1 101 is connected to the ζ.sub.1 104 TFs vector that is stored in an MS 103.

[0072] From Eq.(8) and Eq.(9), the NPA-1 101 of EMB-1 106 of the present invention is realized as shown in the flowchart of FIG. 5. The operation steps of the flowchart of the NPA-1 101 are presented below.

[0073] The flowchart of FIG. 5 starts at step 501; then, step 502 will read the values of n and k for the required TF W.sub.N.sup.(n×k) 102.

[0074] Step 503 will calculate the value of .sub.N.sup.(n×k) using Eq.(7).

[0075] Step 504 will read the value of the TF stored in the memory location of index .sub.N.sup.(n×k) of the ζ.sub.1 104 TFs vector.

[0076] According to Eq.(10), Step 505 will project and assign the value of ζ.sub.1[.sub.N.sup.(n×k)] to the required TF W.sub.N.sup.(n×k) 102.

W.sub.N.sup.(n×k)=ζ.sub.1[.sub.N.sup.(n×k)]  (10)

∀n,k,.sub.N.sup.(n×k)∈ψ{circumflex over ( )}∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈

[0077] The NPA-1 101 is ended at step 506.

Embodiment-2

[0078] In EMB-2 206 of the present invention as shown in FIG. 2, we are going to find the formulation for the NPA-2 201 that will enable us to generate any required TF W.sub.N.sup.(n×k) 202 of the DFT matrix.

[0079] Instead of storing the N.sup.2 TFs that are needed to calculate the DFT which require large MS requirements, only

[00014]$\left(.Math.\frac{N}{2}.Math.+1\right)$

TFs that are members of the set

[00015]${\zeta }_2=\left\{W_N^{\left(0\right)},W_N^{\left(1\right)},.Math.,W_N^{\left(.Math.\frac{N}{2}.Math.\right)}\right\}$

∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈ are needed to be stored in an MS 203.

[0080] The NPA-2 201 will be used to project a specific value to the required TF W.sub.N.sup.(n×k) 202 from one of the

[00016]$\left(.Math.\frac{N}{2}.Math.+1\right)$

TFs of the ζ.sub.2 204 vector that is stored in an MS 203.

[0081] The outcome 205 of the NPA-2 201 will be the projected required TF W.sub.N.sup.(n×k) 202.

[0082] The NPA-2 201 PEs formulation is presented below.

[0083] We have the property of Eq.(11).

W.sub.N.sup.(−(n×k))=(W.sub.N.sup.(n×k)*=  (11)

∀n,k,.sub.N.sup.(n×k)∈ψ{circumflex over ( )}∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈

[0084] From Eq.(8) and Eq.(11), we can get Eq.(12).

W.sub.N.sup.(n×k)==()*  (12)

∀n,k,.sub.N.sup.(n×k)∈ψ{circumflex over ( )}∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈

[0085] Let

[00017]$\stackrel{\left(n\times k\right)}{H}$

be defined as shown in Eq.(13).

[00018]$\begin{array}{cc}\stackrel{\left(n\times k\right)}{H}=1-\left(.Math..Math.\right)=\{\begin{array}{cccc}1& \Leftarrow & \forall N_{\left(n\times k\right)}^{}& \in \\ 0& \Leftarrow & \forall N_{\left(n\times k\right)}^{}& \in \end{array}\begin{array}{c}{\beta }_1=\left\{0,1,2,.Math.,\left(.Math.\frac{N}{2}.Math.\right)\right\}\\ {\beta }_2=\left\{\left(.Math.\frac{N}{2}.Math.+1\right),\left(.Math.\frac{N}{2}.Math.+2\right),.Math.,\left(N-1\right)\right\}\end{array}& \left(13\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_1.Math.\forall W_N\in$

[0086] Where └ ┘ is the floor symbol. └┘ is the floor of that is the nearest integer ≤.

[0087] Using Eq.(12) and Eq.(13), we can get Eq.(14).

[00019]$\begin{array}{cc}{W}_N^{\left(n\times k\right)}=\{\begin{array}{cccc}& =& {\left(\right)}^{\star }& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=1\\ & =& {\left(\right)}^{\star }& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=0\end{array}& \left(14\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_1.Math.\forall W_N\in$

[0088] From examining Table 1, we can clearly notice that by only storing

[00020]$\left(.Math.\frac{N}{2}.Math.+1\right)$

TFs of the ζ.sub.2 204 vector in an MS 203, we can generate any required TF W.sub.N.sup.(n×k) 202 of the DFT matrix.

[0089] From Eq.(14) and Table 1, we can get Eq.(15) that shows the two PEs of EMB-2 206 that will be used to design the NPA-2 201. Equation (15) can be used to generate any required TF W.sub.N.sup.(n×k) 202.

TABLE-US-00001 TABLE 1 [00021]$\mathrm{Does}\delta \in {Ϛ}_2?|\forall \stackrel{\left(n\times k\right)}{H}=1.Math.\forall \stackrel{\left(n\times k\right)}{H}=0.Math.\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_1.Math.W_N\in$ # δ [00022]$\forall \stackrel{\left(n\times k\right)}{H}=1$ [00023]$\forall \stackrel{\left(n\times k\right)}{H}=0$ 1 Yes No 2 ( )* No Yes

[00024]$\begin{array}{cc}{W}_N^{\left(n\times k\right)}=\{\begin{array}{cc}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=1\\ {\left(\right)}^{\star }& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=0\end{array}& \left(15\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_1.Math.\forall W_N\in$

[0090] By using Eq.(15), we can project a specific value to the required TF W.sub.N.sup.(n×k) 202 from one of the

[00025]$\left(.Math.\frac{N}{2}.Math.+1\right)$

TFs of the ζ.sub.2 204 vector.

[0091] The MS arrangement of the NPA-2 201 is presented below.

[0092] FIG. 2 shows how the elements of the set ζ.sub.2 are pre-calculated, arranged and stored in an MS 203 to construct the ζ.sub.2 204 TFs vector.

[00026]$\left(.Math.\frac{N}{2}.Math.+1\right)$

[0093] The elements of the ζ.sub.2 204 TFs vector are constructed according to Eq.(16).

[00027]$$\begin{gathered} \begin{array}{cc}{\zeta }_2\left[G_2\right]=W_N^{\left(G2\right)}=\cos \left(\frac{2\pi }{N}\times G_2\right)-j\sin \left(\frac{2\pi }{N}\times G_2\right) \\ \forall G_2\in {\beta }_1.Math.\forall N\in {\rho }_1.Math.\forall W_N\in & \left(16\right)\end{array} \end{gathered}$$

[0094] The memory location index of the ζ.sub.2 204 TFs vector is G.sub.2.

[0095] The NPA-2 201 is connected to the ζ.sub.2 204 TFs vector that is stored in an MS 203.

[0096] From the above equations, the NPA-2 201 of EMB-2 206 of the present invention is realized as shown in the flowchart of FIG. 6. The operation steps of the flowchart of the NPA-2 201 are presented below.

[0097] The flowchart of FIG. 6 starts at step 601, then step 602 will read the values of n and k for the required TF W.sub.N.sup.(n×k) 202.

[0098] Step 603 will calculate the value of .sub.N.sup.(n×k) using Eq.(7).

[0099] Step 604 will calculate the value of

[00028]$\stackrel{\left(n\times k\right)}{H}$

using Eq.(13).

[0100] Step 605 will check if

[00029]$\stackrel{\left(n\times k\right)}{H}$

is equal to 1. If it is equal to 1, then step 606 will be executed, if it is not equal to 1, then step 608 will be executed.

[0101] Step 606 will read the value of the TF stored in the memory location of index .sub.N.sup.(n×k) of the ζ.sub.2 204 TFs vector.

[0102] According to Eq.(17), step 607 will project and assign the value of ζ.sub.2[] to the required TF W.sub.N.sup.(n×k) 202.

W.sub.N.sup.(n×k)=ζ.sub.2[]  (17)

∀n,k∈ψ{circumflex over ( )}∀.sub.N.sup.(n×k)∈β.sub.1{circumflex over ( )}∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈

[0103] The NPA-2 201 is ended at step 610.

[0104] Step 608 will read the value of the TF stored in the memory location of index (N−.sub.N.sup.(n×k)) of the ζ.sub.2 204 TFs vector.

[0105] According to Eq.(18), step 609 will project and assign the value of (ζ.sub.2[N−.sub.N.sup.(n×k)])* to the required TF W.sub.N.sup.(n×k) 202.

W.sub.N.sup.(n×k)=(ζ.sub.2[N−.sub.N.sup.(n×k)])*  (18)

∀n,k∈ψ{circumflex over ( )}∀.sub.N.sup.(n×k)∈β.sub.2{circumflex over ( )}∀N∈ρ.sub.1{circumflex over ( )}∀W.sub.N∈

[0106] The NPA-2 201 is ended at step 610.

Embodiment-3

[0107] In EMB-3 306 of the present invention as shown in FIG. 3, we are going to find the formulation for the NPA-3 301 that will enable us to generate any required TF W.sub.N.sup.(n×k) 302.

[0108] Instead of storing the N.sup.2 TFs that are needed to calculate the DFT which require large MS requirements, only

[00030]$\left(\frac{N}{2}+1\right)$

TFs that are members of the set

[00031]${\zeta }_3=\left\{W_N^{\left(0\right)},W_N^{\left(1\right)},.Math.,W_N^{\left(\frac{N}{2}\right)}\right\}$

∀N∈ρ.sub.2{circumflex over ( )}∀W.sub.N∈ are needed to be stored in an MS 303.

[0109] The NPA-3 301 will be used to project a specific value to the required TF W.sub.N.sup.(n×k) 302 from one of the

[00032]$\left(\frac{N}{2}+1\right)$

TFs of the ζ.sub.3 304 vector that is stored in an MS 303.

[0110] The outcome 305 of the NPA-3 301 will be the projected required TF W.sub.N.sup.(n×k) 302.

[0111] The NPA-3 301 PEs formulation is presented below.

[0112] We have the properties shown in Eq.(19), Eq.(20) and Eq.(21).

[00033]$\begin{array}{cc}{W}_N^{\left(\left(n\times k\right)\mp \frac{N}{2}\right)}=-\left(W_N^{\left(n\times k\right)}\right)\forall n,k\in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in & \left(19\right)\end{array}$$\begin{array}{cc}{W}_N^{\left(\mp \frac{N}{2}\right)}=-\left(W_N^{\left(n\times k\right)}\right)\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in & \left(20\right)\end{array}$$\begin{array}{cc}{W}_N^{\left(\mp \frac{N}{2}\right))}=-\left(W_N^{\left(n\times k\right)}\right)\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in & \left(21\right)\end{array}$

[0113] From Eq.(8), Eq.(19), Eq.(20), and Eq.(21), we get Eq.(22).

[00034]$\begin{array}{cc}\begin{array}{c}{W}_N^{\left(\mp \frac{N}{2}\right)}=\text{}{W}_N^{\left(+\frac{N}{2}\right)}\\ =W_N^{\left(-\frac{N}{2}\right)}\\ ={\left(W_N^{\left(\right)}\right)}^{\star }\\ =\text{}{W}_N^{\left(\mp \frac{N}{2}\right))}\\ =\text{}{W}_N^{\left(+\frac{N}{2}\right))}\\ =W_N^{\left(-\frac{N}{2}\right))}\\ =\text{}{W}_N^{\left(\left(n\times k\right)\mp \frac{N}{2}\right)}\\ =\text{}{W}_N^{\left(\left(n\times k\right)+\frac{N}{2}\right)}\\ =W_N^{\left(\left(n\times k\right)-\frac{N}{2}\right)}\\ =-W_N^{\left(\right)}\\ =\text{}-W_N^{\left(n\times k\right)}\end{array}& \left(22\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in$

[0114] From Eq.(12) and Eq.(22), we get Eq.(23).

[00035]$\begin{array}{cc}\begin{array}{c}{W}_N^{\left(n\times k\right)}=W_N^{\left(\right)}\\ ={\left(W_N^{\left(N-\right)}\right)}^{*}\\ =-W_N^{\left(+\frac{N}{2}\right)}\\ =-W_N^{\left(+\frac{N}{2}\right)}\\ =-W_N^{\left(-\frac{N}{2}\right)}\\ =-(\left(W_N^{{\left(\frac{N}{2}-\right)}^{*}}\right)\\ =-W_N^{\left({\mp \frac{N}{2})}^{}\right)}\\ =-W_N^{\left({+\frac{N}{2})}^{}\right)}\\ =-W_N^{\left({-\frac{N}{2})}^{}\right)}\\ =-W_N^{\left(\left(n\times k\right)\mp \frac{N}{2}\right)}\\ =-W_N^{\left(\left(n\times k\right)+\frac{N}{2}\right)}\\ =-W_N^{\left(\left(n\times k\right)-\frac{N}{2}\right)}\end{array}& \left(23\right)\end{array}$$\forall n,k,\begin{array}{cc}{N}_{\left(n\times k\right)}^{}& \in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in \end{array}$

[0115] From Eq.(13) and Eq.(23), we get Eq.(24).

[00036]$\begin{array}{cc}\begin{array}{c}{W}_N^{\left(n\times k\right)}=-W_N^{\left(\left(n\times k\right)\mp \frac{N}{2}\right)}\\ =\{\begin{array}{c}\begin{array}{c}{W}_N^{\left(\right)}={\left(W_N^{\left(N-\right)}\right)}^{*}=-W_N^{\left(\mp \frac{N}{2}\right)}=\\ -W_n^{\left(+\frac{N}{2}\right)}=-W_N^{\left(-\frac{N}{2}\right)}=-\left({\left(W_N^{\left(\frac{N}{2}-\right)}\right)}^{*}\right)\\ -W_N^{\left({\mp \frac{N}{2})}^{}\right)}=-W_N^{\left({+\frac{N}{2})}^{}\right)}=-W_N^{\left({-\frac{N}{2})}^{}\right)}\end{array}\}\Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=1\\ \begin{array}{c}{W}_N^{\left(\right)}={\left(W_N^{\left(N-\right)}\right)}^{*}=-W_N^{\left(\mp \frac{N}{2}\right)}=\\ -W_n^{\left(+\frac{N}{2}\right)}=-W_N^{\left(-\frac{N}{2}\right)}=-\left({\left(W_N^{\left(\frac{N}{2}-\right)}\right)}^{*}\right)\\ -W_N^{\left({\mp \frac{N}{2})}^{}\right)}=-W_N^{\left({+\frac{N}{2})}^{}\right)}=-W_N^{\left({-\frac{N}{2})}^{}\right)}\end{array}\}\Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=0\end{array}\end{array}& \left(24\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in$

[0116] From examining Table 2, we can clearly notice that by only storing

[00037]$\left(\frac{N}{2}+1\right)$

TFs of the ζ.sub.3 304 vector in an MS 303, we can generate any required TF W.sub.N.sup.(n×k) 302.

[0117] From Eq.(24) and Table 2, we can get Eq.(25) that shows the five PEs of EMB-3 306 that will be used to design the NPA-3 301. Equation (25) can be used to find any required TF W.sub.N.sup.(n×k) 302.

[0118] By using Eq.(25), we can project a specific value to the required TF W.sub.N.sup.(n×k) 302 from one of the

[00038]$\left(\frac{N}{2}+1\right)$

TFs of the ζ.sub.3 304 vector.

[0119] The MS arrangement of the NPA-3 301 is presented below.

[0120] FIG. 3 shows how the elements of the set ζ.sub.3 are pre-calculated, arranged and stored in an MS 303 to construct the ζ.sub.3 304 TFs vector.

[0121] The

[00039]$\left(\frac{N}{2}+1\right)$

elements of the ζ.sub.3 304 TFs vector are constructed according to Eq.(26).

TABLE-US-00002 TABLE 2 [00040]$\mathrm{Does}\gamma \in {Ϛ}_3?|\forall \stackrel{\left(n\times k\right)}{H}=1.Math.\forall \stackrel{\left(n\times k\right)}{H}=0.Math.\forall n,k,n_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in$ # γ [00041]$\forall \stackrel{\left(n\times k\right)}{H}=1$ [00042]$\forall \stackrel{\left(n\times k\right)}{H}=0$ 1 .sup.) Yes No 2 ( .sup.))* No Yes 3 [00043]$-W_N^{\left({𝔐}_N^{\left(n\times k\right)}\mp \frac{N}{2}\right)}$ No No 4 [00044]$-W_N^{\left({𝔐}_N^{\left(n\times k\right)}+\frac{N}{2}\right)}$ No No 5 [00045]$-W_N^{\left({𝔐}_N^{\left(n\times k\right)}-\frac{N}{2}\right)}$ No Yes 6 [00046]$-\left({\left(W_N^{\left(\frac{N}{2}{𝔐}_N^{\left(n\times k\right)}\right)}\right)}^{*}\right)$ No No 7 [00047]$-W_N^{\left({𝔐}_N^{\left({𝔐}_N^{.Math.n\times k)}\mp \frac{N}{2}\right)}\right)}$ No Yes 8 [00048]$-W_N^{\left({𝔐}_N^{\left({𝔐}_N^{.Math.n\times k)}+\frac{N}{2}\right)}\right)}$ No Yes 9 [00049]$-W_N^{\left({𝔐}_N^{\left({𝔐}_N^{.Math.n\times k)}-\frac{N}{2}\right)}\right)}$ No Yes

[00050]$\begin{array}{cc}{W}_N^{\left(n\times k\right)}=\{\begin{array}{cc}{W}_N^{)}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=1\\ {\left(\right))}^{*}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=0\\ -{-\frac{N}{2})}^{}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=0\\ -{+\frac{N}{2})}^{})& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=0\\ -{-\frac{N}{2})}^{})& \Leftarrow \forall \stackrel{\left(n\times k\right)}{H}=0\end{array}& \left(25\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2.Math.\forall W_N\in$

[00051]$\begin{array}{cc}{\zeta }_3\left[G_3\right]=W_N^{\left(G_3\right)}=\cos \left(\frac{2\pi }{N}\times G_3\right)-j\sin \left(\frac{2\pi }{N}\times G_3\right)\forall G_3\in {\beta }_3=\left\{0,1,.Math.,\left(\frac{N}{2}\right)\right\}.Math.\forall N\in {\rho }_2.Math.\forall W_N\in & \left(26\right)\end{array}$

[0122] The memory location index of the ζ.sub.3 304 TFs vector is G.sub.3.

[0123] The NPA-3 301 is connected to the ζ.sub.3 304 TFs vector that is stored in an MS 303.

[0124] From the above equations, the NPA-3 301 of EMB-3 306 of the present invention is realized as shown in the flowchart of FIG. 7. The operation steps of the flowchart of the NPA-3 301 are presented below.

[0125] The flowchart of FIG. 7 starts at step 701, then step 702 will read the values of n and k for the required TF W.sub.N.sup.(n×k) 302.

[0126] Step 703 will calculate the value of .sub.N.sup.(n×k) using Eq.(7).

[0127] Step 704 will calculate the value of

[00052]$\stackrel{\left(n\times k\right)}{H}$

using Eq.(13).

[0128] Step 705 will check if

[00053]$\stackrel{\left(n\times k\right)}{H}$

is equal to 1. If it is equal to 1, then step 706 will be executed, if it is not equal to 1, then step 708 will be executed.

[0129] Step 706 will read the value of the TF stored in the memory location of index .sub.N.sup.(n×k) of the ζ.sub.3 304 TFs vector.

[0130] According to Eq.(27), step 707 will project and assign the value of ζ.sub.3[.sub.N.sup.(n×k)] to the required TF W.sub.N.sup.(n×k) 302.

W.sub.N.sup.(n×k)=ζ.sub.3[.sub.N.sup.(n×k)]  (27)

∀n,k,∈ψ{circumflex over ( )}∀.sub.N.sup.(n×k)∈β.sub.3{circumflex over ( )}∀N∈ρ.sub.2{circumflex over ( )}∀W.sub.N∈

[0131] The NPA-3 301 is ended at step 710.

[0132] Step 708 will read the value of the TF stored in the memory location of index (N−.sub.N.sup.(n×k)) or

[00054]$\left(N_{\left(n\times k\right)}^{}-\frac{N}{2}\right)\mathrm{or}\left({+\frac{N}{2})}^{}\right)\mathrm{or}\left({-\frac{N}{2})}^{}\right)$

of the ζ.sub.3 304 TFs vector.

[0133] According to Eq.(28), step 709 will project and assign the value of (ζ.sub.3[N−.sub.N.sup.(n×k)])* or

[00055]$\left(-{\zeta }_3\left[N_{\left(n\times k\right)}^{}-\frac{N}{2}\right]\right)\mathrm{or}\left(-{\zeta }_3\left[{+\frac{N}{2})}^{}\right]\right)\mathrm{or}\left(-{\zeta }_3\left[{-\frac{N}{2})}^{}\right]\right)$

to the required W.sub.N.sup.(n×k) 302.

[00056]$\begin{array}{cc}{W}_N^{\left(n\times k\right)}={\left({\zeta }_3\left[N-N_{\left(n\times k\right)}^{}\right]\right)}^{*}=-{\zeta }_3\left[N_{\left(n\times k\right)}^{}-\frac{N}{2}\right]=-{\zeta }_3\left[{+\frac{N}{2})}^{}\right]=-{\zeta }_3\left[{-\frac{N}{2})}^{}\right]& \left(28\right)\end{array}$$\forall n,k\in \psi .Math.N_{\left(n\times k\right)}^{}\in {\beta }_4=\left\{\left(\frac{N}{2}+1\right),\left(\frac{N}{2}+2\right),.Math.,\left(N-1\right)\right\}.Math.\forall N\in {\rho }_2.Math.\forall W_N\in$

[0134] The NPA-3 301 is ended at step 710.

Embodiment-4

[0135] In EMB-4 406 of the present invention as shown in FIG. 4, we are going to find the formulation for the NPA-4 401 that will enable us to generate any required TF W.sub.N.sup.(n×k) 402.

[0136] Instead of storing the N.sup.2 TFs that are needed to calculate the DFT which require large MS requirements, only

[00057]$\left(.Math.\frac{N}{4}.Math.+1\right)$

TFs that are members of the set

[00058]${Ϛ}_4=\left\{W_N^{\left(0\right)},W_N^{\left(1\right)},.Math.,W_N^{\left(.Math.\frac{N}{4}.Math.\right)}\right\}\forall N\in {\rho }_2.Math.\forall W_N\in$

are needed to be stored in an MS 403.

[0137] The NPA-4 401 will be used to project a specific value to the required TF W.sub.N.sup.(n×k) 402 from one of the

[00059]$\left(.Math.\frac{N}{4}.Math.+1\right)$

TFs of the ζ.sub.4 404 vector that is stored in an MS 403.

[0138] The outcome 405 of the NPA-4 401 will be the projected required TF W.sub.N.sup.(n×k) 402.

[0139] The NPA-4 401 PEs formulation is presented below.

[0140] Let be

[00060]$\stackrel{\left(n\times k\right)}{Q}$

defined as in Eq.(29).

[00061]$\begin{array}{cc}\stackrel{\left(n\times k\right)}{Q}=.Math..Math.\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2& \left(29\right)\end{array}$

[0141] From Eq.(29), the computation of

[00062]$\stackrel{\left(n\times k\right)}{Q}$

will result one of the values shown in Eq.(30).

[00063]$\begin{array}{cc}\stackrel{\left(n\times k\right)}{Q}=\{\begin{array}{cc}0& \Leftarrow \forall N_{\left(n\times k\right)}^{}\in {\lambda }_1=\left\{0,1,2,.Math.,.Math.\frac{N}{4}.Math.\right\}\\ 1& \Leftarrow \forall N_{\left(n\times k\right)}^{}\in {\lambda }_2=\left\{\left(.Math.\frac{N}{4}.Math.+1\right),\left(.Math.\frac{N}{4}.Math.+2\right),.Math.,.Math.\frac{N}{2}.Math.\right\}\\ 2& \Leftarrow \forall N_{\left(n\times k\right)}^{}\in {\lambda }_3=\left\{\left(.Math.\frac{N}{2}.Math.+1\right),\left(.Math.\frac{N}{2}.Math.+2\right),.Math.,.Math.\frac{\left(3\times N\right)}{4}.Math.\right\}\\ 3& \Leftarrow \forall N_{\left(n\times k\right)}^{}\in {\lambda }_4=\left\{\left(.Math.\frac{\left(3\times N\right)}{4}.Math.+1\right),\left(.Math.\frac{\left(3\times N\right)}{4}.Math.+2\right),.Math.,\left(N-1\right)\right\}\end{array}& \left(30\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2$

[0142] From Eq.(24), we can get Eq.(31).

[0143] From examining Table 3, we can clearly notice that by only storing

[00064]$\left(.Math.\frac{N}{4}.Math.+1\right)$

TFs of the ζ.sub.4 404 vector in an MS 403, we can generate any required TF W.sub.N.sup.(n×k) 402.

TABLE-US-00003 TABLE 3 [00065]$\mathrm{Does}\phi \in {Ϛ}_4?|\left(\forall \stackrel{\left(n\times k\right)}{Q}\in \left\{0,1,2,3\right\}\right).Math.\left(\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_2.Math.W_N\in \right)$ # φ [00066]$\forall \stackrel{\left(n\times k\right)}{Q}=0$ [00067]$\forall \stackrel{\left(n\times k\right)}{Q}=1$ [00068]$\forall \stackrel{\left(n\times k\right)}{Q}=2$ [00069]$\forall \stackrel{\left(n\times k\right)}{Q}=3$ 1 Yes No No No 2 ( )* No No No Yes 3 [00070]$-W_N^{\left(N_{\left(n\times k\right)}^{}\mp \frac{N}{2}\right)}$ No No No No 4 [00071]$-W_N^{\left(N_{\left(n\times k\right)}^{}+\frac{N}{2}\right)}$ No No No No 5 [00072]$-W_N^{\left(N_{\left(n\times k\right)}^{}-\frac{N}{2}\right)}$ No No Yes No 6 [00073]$-\left({\left(W_N^{\left(\frac{N}{2}-N_{\left(n\times k\right)}^{}\right)}\right)}^{*}\right)$ No Yes No No 7 [00074]$-W_N^{\left(N_{\left(N_{{.Math.n\times k)}_{\mp }}^{}\frac{N}{2}\right)}^{}\right)}$ No No Yes No 8 [00075]$-W_N^{\left(N_{\left(N_{{.Math.n\times k)}_{+}}^{}\frac{N}{2}\right)}^{}\right)}$ No No Yes No 9 [00076]$-W_N^{\left(N_{\left(N_{{.Math.n\times k)}_{-}}^{}\frac{N}{2}\right)}^{}\right)}$ No No Yes No

[0144] From Eq.(31) and Table 3, we can get Eq.(32) that shows the six PEs of EMB-4 406 which will be used to design the NPA-4 401. Equation (32) can be used to find any required TF W.sub.N.sup.(n×k) 402.

[00077]$\begin{array}{cc}{W}_N^{\left(n\times k\right)}=\{\begin{array}{cc}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{Q}=0\\ -\left({\left(\right)}^{*}\right)& \Leftarrow \forall \stackrel{\left(n\times k\right)}{Q}=1\\ -{-\frac{N}{2})}^{}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{Q}=2\\ -{+\frac{N}{2}))}^{}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{Q}=2\\ -{-\frac{N}{2}))}^{}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{Q}=2\\ {\left(\right)}^{*}& \Leftarrow \forall \stackrel{\left(n\times k\right)}{Q}=3\end{array}& \left(32\right)\end{array}$$\forall n,k,N_{\left(n\times k\right)}^{}\in \psi .Math.\forall N\in {\rho }_4.Math.\forall W_N\in$

[0145] By using Eq.(32), we can project a specific value to the required TF W.sub.N.sup.(n×k) 402 from one of the

[00078]$\left(.Math.\frac{N}{4}.Math.+1\right)$

TFs of the ζ.sub.4 404 vector.

[0146] The MS arrangement of the NPA-4 401 is presented below.

[0147] FIG. 4 shows how the elements of the set ζ.sub.4 are pre-calculated, arranged and stored in an MS 403 to construct the ζ.sub.4 404 TFs vector.

[0148] The

[00079]$\left(.Math.\frac{N}{4}.Math.+1\right)$

elements of the ζ.sub.4 404 TFs vector are constructed according to Eq.(33).

[00080]$$\begin{gathered} \begin{array}{cc}{\zeta }_4\left[G_4\right]=W_N^{\left(G_4\right)}=\cos \left(\frac{2\pi }{N}\times G_4\right)-j\sin \left(\frac{2\pi }{N}\times G_4\right) \\ \forall G_4\in {\lambda }_1.Math.\forall N\in {\rho }_2.Math.\forall W_N\in & \left(33\right)\end{array} \end{gathered}$$

[0149] The memory location index of the ζ.sub.4 404 TFs vector is G.sub.4.

[0150] The NPA-4 401 is connected to the ζ.sub.4 404 TFs vector that is stored in an MS 403.

[0151] From the above equations, the NPA-4 401 of EMB-4 406 of the present invention is realized as shown in the flowchart of FIG. 8. The operation steps of the flowchart of the NPA-4 401 are presented below.

[0152] The flowchart of FIG. 8 starts at step 801, then step 802 will read the values of n and k for the required TF W.sub.N.sup.(n×k) 402.

[0153] Step 803 will calculate the value of .sub.N.sup.(n×k) using Eq.(7).

[0154] Step 804 will calculate the value of

[00081]$\stackrel{\left(n\times k\right)}{Q}$

using Eq.(29).

[0155] Step 805 will check if

[00082]$\stackrel{\left(n\times k\right)}{Q}$

is equal to 0. If it is equal to 0, then the path of connector CC1 806 will be followed and step 812 will be executed. If it is not equal to 0, then step 807 will be executed.

[0156] Connector CC1 806 is connecting step 805 and step 812.

[0157] Step 807 will check if

[00083]$\stackrel{\left(n\times k\right)}{Q}$

is equal to 1. If it is equal to 1, then the path of connector CC2 808 will be followed and step 814 will be executed. If it is not equal to 1, then step 809 will be executed.

[0158] Connector CC2 808 is connecting step 807 and step 814.

[0159] Step 809 will check if

[00084]$\stackrel{\left(n\times k\right)}{Q}$

is equal to 2. If it is equal to 2, then the path of connector CC3 810 will be followed and step 817 will be executed. If it is not equal to 2, meaning that

[00085]$\stackrel{\left(n\times k\right)}{Q}$

is equal to 3, then the path of connector CC4 811 will be followed and step 819 will be executed.

[0160] Connector CC3 810 is connecting step 809 and step 817.

[0161] Connector CC4 811 is connecting step 809 and step 819.

[0162] Step 812 will read the value of the TF stored in the memory location of index .sub.N.sup.(n×k) of the ζ.sub.4 404 TFs vector.

[0163] According to Eq.(34), step 813 will project and assign the value of ζ.sub.4[.sub.N.sup.(n×k)] to the required TF W.sub.N.sup.(n×k) 402.

W.sub.N.sup.(n×k)=ζ.sub.4[.sub.N.sup.(n×k)]  (34)

∀n,k,∈ψ{circumflex over ( )}∀.sub.N.sup.(n×k)∈λ.sub.1{circumflex over ( )}∀N∈ρ.sub.2{circumflex over ( )}∀W.sub.N∈

[0164] The NPA-4 401 is ended at step 816.

[0165] Step 814 will read the value of the TF stored in the memory location of index

[00086]$\left(\frac{N}{2}-N_{\left(n\times k\right)}^{}\right)$

of the ζ.sub.4 404 TFs vector.

[0166] According to Eq.(35), step 815 will project and assign the value of

[00087]$\left(-{\left({\zeta }_4\left[\frac{N}{2}-{𝔐}_N^{\left(n\times k\right)}\right]\right)}^{*}\right)$

to the required TF W.sub.N.sup.(n×k) 402.

[00088]$\begin{array}{cc}{W}_N^{\left(n\times k\right)}=\left(-{\left({\zeta }_4\left[\frac{N}{2}-N_{\left(n\times k\right)}^{}\right]\right)}^{*}\right)\forall n,k\in \psi .Math.\forall N_{\left(n\times m\right)}^{}\in {\lambda }_2.Math.\forall N\in {\rho }_2.Math.\forall W_N\in & \left(35\right)\end{array}$

[0167] The NPA-4 401 is ended at step 816.

[0168] Step 817 will read the value of the TF stored in the memory location of index

[00089]$\left(N_{\left(n\times k\right)}^{}-\frac{N}{2}\right)\mathrm{or}\left(N_{\left(N_{\left(n\times k\right)}^{}+\frac{N}{2}\right)}^{}\right)\mathrm{or}\left(N_{\left(N_{\left(n\times k\right)}^{}-\frac{N}{2}\right)}^{}\right)$

of the ζ.sub.4 404 TFs vector.

[0169] According to Eq.(36), step 818 will project and assign the value of

[00090]$\left(-{\zeta }_4\left[N_{\left(n\times k\right)}^{}-\frac{N}{2}\right]\right)\mathrm{or}\left(-{\zeta }_4\left[N_{\left(N_{\left(n\times k\right)}^{}+\frac{N}{2}\right)}^{}\right]\right)\mathrm{or}\left(-{\zeta }_4\left[N_{\left(N_{\left(n\times k\right)}^{}-\frac{N}{2}\right)}^{}\right]\right)$

to the required TF W.sub.N.sup.(n×k) 402.

[00091]$\begin{array}{cc}{W}_N^{\left(n\times k\right)}=\left(-{\zeta }_4\left[N_{\left(n\times k\right)}^{}-\frac{N}{2}\right]\right)=\left(-{\zeta }_4\left[N_{\left(N_{\left(n\times k\right)}^{}+\frac{N}{2}\right)}^{}\right]\right)=(-{\zeta }_4[N_{\left(N_{\left(n\times k\right)}^{}-\frac{N}{2}\right)}^{}])\forall n,k\in \psi .Math.\forall N_{\left(n\times k\right)}^{}\in {\lambda }_3.Math.\forall N\in {\rho }_2.Math.\forall W_N\in & \left(36\right)\end{array}$

[0170] The NPA-4 401 is ended at step 816.

[0171] Step 819 will read the value of the TF stored in the memory location of index (N−.sub.N.sup.(n×k)) of the ζ.sub.4 404 TFs vector.

[0172] According to Eq.(37), step 820 will project and assign the value of (ζ.sub.4[N−.sub.N.sup.(n×k)])* to the required TF W.sub.N.sup.(n×k) 402.

W.sub.N.sup.(n×k)=(ζ.sub.4[N−.sub.N.sup.(n×k)])*  (37)

∀n,k∈ψ{circumflex over ( )}∀.sub.N.sup.(n×k)∈λ.sub.4{circumflex over ( )}∀N∈ρ.sub.2{circumflex over ( )}∀W.sub.N∈

[0173] The NPA-4 401 is ended at step 816.

[0174] Performance Evaluation

[0175] The TPR is the percentage ratio of the MNRTF that is needed to be stored in an MS 103 or MS 203 or MS 303 or MS 403 to the N.sup.2 total TFs needed to calculate the DFT as shown in Eq.(38).

[00092]$\begin{array}{cc}\mathrm{TPR}=\left(\frac{MNRTF}{N^2}\right)\times 100\%\forall N\in {\rho }_1& \left(38\right)\end{array}$

[0176] From Eq.(38), the PMRR for the memory requirements for storing the TFs that are needed to calculate the DFT is shown in Eq.(39).

[00093]$\begin{array}{cc}\mathrm{PMRR}=\left(1-\frac{\mathrm{MNRTF}}{N^2}\right)\times 100\%\forall N\in {\rho }_1& \left(39\right)\end{array}$

[0177] Table 4 presents a comparison between the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306, the NPA-4 401 of EMB-4 406 of the present invention and the DFT regarding their MNRTF, TPR, PMRR, the number of samples in the time domain N to be transformed to frequency domain using DFT and the number of their PEs.

[0178] From Table 4, it is clear to notice that the NPA-4 401 of EMB-4 406 that works for ∀N∈ρ.sub.2 has the lowest MNRTF, lowest TPR and the highest PMRR. So, it has a better performance when compared with the performance of the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306 of the present invention and the DFT.

[0179] From Table 4, it is clear to notice that the NPA-2 201 of EMB-2 206 that works ∀N∈ρ.sub.1 and the NPA-3 301 of EMB-3 306 that works ∀N∈ρ.sub.2 have the same MNRTF, the same TPR and the same PMRR when compared ∀N∈ρ.sub.2.

[0180] From Table 4, it is clear to notice that the DFT has the highest MNRTF, highest TPR and the lowest PMRR. So it has the lowest performance when compared with the performance of the NPA-1 101 of EMB-1 106 that works ∀N∈ρ.sub.1, the NPA-2 201 of EMB-2 206 that works ∀N∈ρ.sub.1, the performance of the NPA-3 301 of EMB-3 306 that works ∀N∈ρ.sub.2, and the NPA-4 401 of EMB-4 406 that works ∀N∈ρ.sub.2.

TABLE-US-00004 TABLE 4 Number of NPA No./ Projection Type MNRTF TPR PMRR N is: Equations 1 N [00094]$\left(\frac{1}{N}\right)\times 100\%$ [00095]$\left(1-\frac{1}{N}\right)\times 100\%$ Odd or Even 1 2 [00096]$\left(.Math.\frac{N}{2}.Math.+1\right)$ [00097]$\left(\frac{\left(.Math.\frac{N}{2}.Math.+1\right)}{N^2}\right)\times 100\%$ [00098]$\left(1-\frac{\left(.Math.\frac{N}{2}.Math.+1\right)}{N^2}\right)\times 100\%$ Odd or Even 2 3 [00099]$\left(\frac{N}{2}+1\right)$ [00100]$\left(\frac{\left(\frac{N}{2}+1\right)}{N^2}\right)\times 100\%$ [00101]$\left(1-\frac{\left(\frac{N}{2}+1\right)}{N^2}\right)\times 100\%$ Even 5 4 [00102]$\left(.Math.\frac{N}{4}.Math.+1\right)$ [00103]$\left(\frac{\left(.Math.\frac{N}{4}.Math.+1\right)}{N^2}\right)\times 100\%$ [00104]$\left(1-\frac{\left(.Math.\frac{N}{4}.Math.+1\right)}{N^2}\right)\times 100\%$ Even 6 DFT N.sup.2 100% 0% Odd or — Even

[0181] From Table 4, it is clear to notice that the NPA-1 101 of EMB-1 106 that works ∀N∈ρ.sub.1 has the highest MNRTF, the highest TPR and the lowest PMRR. So, it has the lowest performance when compared with the performance of the NPA-2 201 of EMB-2 206 that works ∀N∈ρ.sub.1, the performance of the NPA-3 301 of EMB-3 306 that works ∀N∈ρ.sub.2, and the performance of the NPA-4 401 of EMB-4 406 that works ∀N∈ρ.sub.2.

[0182] Having a low MNRTF is highly recommended since it will result in low MS requirements for the TFs that will have to be stored in an MS 103 or MS 203 or MS 303 or MS 403 and to be used by the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306 and the NPA-4 401 of EMB-4 406 respectively to generate any required TF of the DFT matrix.

[0183] A low MNRTF results in a low power consumption. It is desired to have a low MNRTF that will result in a low TPR. Also, it will result in a high PMRR that is also desired. A high MNRTF is not desired since it will result in a high TPR and a low PMRR.

[0184] FIG. 9 shows the simulated comparison results plot of the MNRTF computations (logarithmic scale) versus the number of points N (logarithmic scale) for the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306, the NPA-4 401 of EMB-4 406 of the present invention and the DFT.

[0185] FIG. 10 shows the simulated comparison results plot of the MNRTF computations (logarithmic scale) versus the number of points N (linear scale) for the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306, the NPA-4 401 of EMB-4 406 of the present invention and the DFT.

[0186] FIG. 11 shows the simulated comparison results plot of the TPR of the MNRTF computations (logarithmic scale) versus the number of points N (logarithmic scale) for the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306, the NPA-4 401 of EMB-4 406 of the present invention and the DFT.

[0187] FIG. 12 shows the simulated comparison results plot of the TPR of the MNRTF computations (logarithmic scale) versus the number of points N (linear scale) for the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306, the NPA-4 401 of EMB-4 406 of the present invention and the DFT.

[0188] FIG. 13 shows the simulated comparison results plot of the PMRR computations (linear scale) versus the number of points N (logarithmic scale) for the NPA-1 101 of EMB-1 106, the NPA-2 201 of EMB-2 206, the NPA-3 301 of EMB-3 306, the NPA-4 401 of EMB-4 406 of the present invention and the DFT.

[0189] For the IDFT, the IDFT matrix form of Eq. (2) is shown in Eq.(40).

[00105]$\begin{array}{cc}\left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ .Math.\\ x_{N-1}\end{array}\right]=\left[\text{⁠}\begin{array}{ccccc}{W}_N^{\left(-\left(0\times 0\right)\right)}& W_N^{\left(-\left(0\times 1\right)\right)}& W_N^{\left(-\left(0\times 2\right)\right)}& .Math.& W_N^{\left(-\left(0\times \left(N-1\right)\right)\right)}\\ W_N^{\left(-\left(1\times 0\right)\right)}& W_N^{\left(-\left(1\times 1\right)\right)}& W_N^{\left(-\left(1\times 2\right)\right)}& .Math.& W_N^{\left(-\left(1\times \left(N-1\right)\right)\right)}\\ W_N^{\left(-\left(2\times 0\right)\right)}& W_N^{\left(-\left(2\times 1\right)\right)}& W_N^{\left(-\left(2\times 2\right)\right)}& .Math.& W_N^{\left(-\left(2\times \left(N-1\right)\right)\right)}\\ .Math.& .Math.& .Math.& \ddots & .Math.\\ W_N^{\left(-\left(\left(N-1\right)\times 0\right)\right)}& W_N^{\left(-\left(\left(N-1\right)\times 1\right)\right)}& W_N^{\left(-\left(\left(N-1\right)\times 2\right)\right)}& .Math.& W_N^{\left(-\left(\left(N-1\right)\times \left(N-1\right)\right)\right)}\end{array}\right]\times \left[\text{⁠}\begin{array}{c}{X}_0\\ X_1\\ X_2\\ .Math.\\ X_{N-1}\end{array}\right]\forall X,x,W_N\in .Math.\forall N\in {\rho }_1& \left(40\right)\end{array}$

[0190] From Eq.(40), we can get the compact IDFT matrix form of the IDFT as shown in Eq.(41).

[00106]$\begin{array}{cc}\left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ .Math.\\ x_{N-1}\end{array}\right]=\left[\text{⁠}\begin{array}{ccccc}{W}_N^{\left(0\right)}& W_N^{\left(0\right)}& W_N^{\left(0\right)}& .Math.& W_N^{\left(0\right)}\\ W_N^{\left(0\right)}& W_N^{\left(-1\right)}& W_N^{\left(-2\right)}& .Math.& W_N^{\left(-\left(1\times \left(N-1\right)\right)\right)}\\ W_N^{\left(0\right)}& W_N^{\left(-2\right)}& W_N^{\left(-4\right)}& .Math.& W_N^{\left(-\left(2\times \left(N-1\right)\right)\right)}\\ .Math.& .Math.& .Math.& \ddots & .Math.\\ W_N^{\left(0\right)}& W_N^{\left(-\left(\left(N-1\right)\times 1\right)\right)}& W_N^{\left(-\left(\left(N-1\right)\times 2\right)\right)}& .Math.& W_N^{\left(-\left(\left(N-1\right)\times \left(N-1\right)\right)\right)}\end{array}\right]\times \left[\text{⁠}\begin{array}{c}{X}_0\\ X_1\\ X_2\\ .Math.\\ X_{N-1}\end{array}\right]\forall X,x,W_N\in .Math.\forall N\in {\rho }_1& \left(41\right)\end{array}$