<< Chapter < Page Chapter >> Page >

Reference [link] should be consulted for the details of these conditions and examples. Two classes of index maps are definedfrom these conditions.

Type-one index map:

The map of [link] is called a type-one map when integers a and b exist such that

K 1 = a N 2 and K 2 = b N 1

Type-two index map:

The map of [link] is called a type-two map when when integers a and b exist such that

K 1 = a N 2 or K 2 = b N 1 , but not both.

The type-one can be used only if the factors of N are relatively prime, but the type-two can be used whether they are relatively prime ornot. Good [link] , Thomas, and Winograd [link] all used the type-one map in their DFT algorithms. Cooley and Tukey [link] used the type-two in their algorithms, both for a fixed radix ( N = R M ) and a mixed radix [link] .

The frequency index is defined by a map similar to [link] as

k = ( ( K 3 k 1 + K 4 k 2 ) ) N

where the same conditions, [link] and [link] , are used for determining the uniqueness of this map in terms of the integers K 3 and K 4 .

Two-dimensional arrays for the input data and its DFT are defined using these index maps to give

x ^ ( n 1 , n 2 ) = x ( ( K 1 n 1 + K 2 n 2 ) ) N
X ^ ( k 1 , k 2 ) = X ( ( K 3 k 1 + K 4 k 2 ) ) N

In some of the following equations, the residue reduction notation will be omitted for clarity. These changes of variablesapplied to the definition of the DFT given in [link] give

C ( k ) = n 2 = 0 N 2 - 1 n 1 = 0 N 1 - 1 x ( n ) W N K 1 K 3 n 1 k 1 W N K 1 K 4 n 1 k 2 W N K 2 K 3 n 2 k 1 W N K 2 K 4 n 2 k 2

where all of the exponents are evaluated modulo N .

The amount of arithmetic required to calculate [link] is the same asin the direct calculation of [link] . However, because of the special nature of the DFT, the integer constants K i can be chosen in such a way that the calculations are “uncoupled" andthe arithmetic is reduced. The requirements for this are

( ( K 1 K 4 ) ) N = 0 and/or ( ( K 2 K 3 ) ) N = 0

When this condition and those for uniqueness in [link] are applied, it is found that the K i may always be chosen such that one of the terms in [link] is zero. If the N i are relatively prime, it is always possible to make both terms zero. If the N i are not relatively prime, only one of the terms can be set to zero. When they are relatively prime, there is a choice, itis possible to either set one or both to zero. This in turn causes one or both of the center two W terms in [link] to become unity.

An example of the Cooley-Tukey radix-4 FFT for a length-16 DFT uses the type-two map with K 1 = 4 , K 2 = 1 , K 3 = 1 , K 4 = 4 giving

n = 4 n 1 + n 2
k = k 1 + 4 k 2

The residue reduction in [link] is not needed here since n does not exceed N as n 1 and n 2 take on their values. Since, in this example, the factors of N have a common factor, only one of the conditions in [link] can hold and, therefore, [link] becomes

C ^ ( k 1 , k 2 ) = C ( k ) = n 2 = 0 3 n 1 = 0 3 x ( n ) W 4 n 1 k 1 W 16 n 2 k 1 W 4 n 2 k 2

Note the definition of W N in [link] allows the simple form of W 16 K 1 K 3 = W 4

This has the form of a two-dimensional DFT with an extra term W 16 , called a “twiddle factor". The inner sum over n 1 represents four length-4 DFTs, the W 16 term represents 16 complex multiplications, and the outer sum over n 2 represents another four length-4 DFTs. This choice of the K i “uncouples" the calculations since the first sum over n 1 for n 2 = 0 calculates the DFT of the first row of the data array x ^ ( n 1 , n 2 ) , and those data values are never needed in the succeeding row calculations. The row calculations are independent,and examination of the outer sum shows that the column calculations are likewise independent. This is illustrated in [link] .

Questions & Answers

how environment affect demand and supply of commodity ?
Amos Reply
Wht at the criteria for market ?
what is difference between monitory policy and fiscal policy?
Malik Reply
monetary policy is a policy thrust by National Govt(CBN) to influence government spending, purchase &taxes
necessity of economics
Pamela Reply
I will say want,choice,opportunity cost,scarcity,scale of preference
what is monopoly market.How price output are determined under monopoly market
b) Monopoly market is an impecfect market where s single firm having the innovation to produce a particular commodity.Prices are determined through output since there are no other competitive.
Monopoly market:firm has market power & does not respond to market price
Explain the process of price determination under perfect competition market with suitable diagram
bisham Reply
Price determination under perfect competition via this process :firms have no market power to influence price rather firms respond to market price.
price is different from demand- demand is amount of commodity
Effah Reply
demand is amount /quantity of commodity a potential buyer is willing to buy at a given price at market
demand is a desire of customer on commodity with the ability to pay it and willing to buy it at given price of commodity
demand is price of what
Faith Reply
show that shortrun average cost
Baby Reply
what is economics
Mbah Reply
what is money
what is money
Difine macro economics
money is a medium of exchange between goods and services,maybe inform of currency.
Economics is study of how human beings strive to satisfy numerous wants using limited available resources.
how do you find the maximum number of workers the firms should employ order to produce where there are increasing returns
what are implications of computing national income?.
what is the formulae for calculating national income
it calculated by value added method
classify the production units like agriculture, banking, transport etc
money is anything that is generally acceptetable for human
Estimate the net value added(NVA) at fixed cost by each industrial structure
definition of unemployment
Adam Reply
what are the causes of unemployment?
Mbubi Reply
The main causes of unemployment are listed below. 1. Frictional unemployment 2. Cyclical unemployment 3. Structural unemployment
We can also categorize the causes on a broader sense as: 1. Political and 2. Social cause As unemployeement root causes are embaded in this two.
would opportunity cost exist if there was no scarcity?
yes just because the opportunity cost arose when there is Alternative to choose among the alternatives.
I am thinking that, if our resources were unlimited, then there wouldn't be any need to forgo some wants. Hence the inexistence if opportunity cost
politics has done what?
consider time assani
I'm Emmanuel,...I taught the main cause is the change in gov't.
...Lack of capital to set up a firm respectively
I would like to bring in Educational levels can also be the cause the cause of the problem respectively
lack of skills among the new generation is the serious issue.
Where I come from , I don't see why education or personal aspects seem to do with unimployment, technically the motivation and eigerness in all works of live is there , dispite the cultural influence and physical bearriors;the thing we lacking is Government Support and open market ethics.
sorry about that-(repation). We have a over powering ethical political system that's displacing the marketing asspects of economy and causing large scale unemployment right across the board...
can someone Explain Expansionary Monetary Policy and Contractionary Monetary Policy Using one of the instrument of Monetary Policy? Please am kinda lost here?. ta
Emmanuel Reply
using a graph show the case of substitute and compliment goods
Ade Reply
can anyone give me a simple explanation to Five Sector Macroeconomics?
Can someone please define what economics is
jason Reply
economics simply is a social science subject that study human behavior.
economics is a social science which studies human behaviour as a relationship between ends and scarce means that has alternative uses
Can someone please tell me how to calculate GDP
emmanual kapal to calculate GDP (Gross Domestic Product) has three method in calculating it (1)income approach (2) expenditure approach (3) value added method
thanks Alae
u are welcome
in basic terms economics is revered to as battery system, it date back to when Men sees the need to exchange sapless goods and produce to gain , either wealth , basic necessities or to establish trading ties for personal benefit or social asspects in terms of coexistence and continuity, future .
what is the law of demand
Berlinda Reply
keep other thing constant, when the price increases demand decrease when the price decreases demand increases of the commodity.
all things being equal,quantity demanded decrease as price increase and increase as price decrease
there's practial joke to it ..." the higher the demand ; scarcity, increase in production and drop in quality"... quite the controversy - for example China vs Europe, United States and we are all boxed up in between somewhere...
Other thing remain constant the low price of commodity the high quantity of commodity and vice versa is true
Explain Effective demand
Anita Reply
What is effective demand
like Modi is in demand...best example of effective demand
Don't get you
Anita you mean you don't get me or who?
level of demand that represents a real intention to purchase by people with the means to pay
in a comparison of the stages of meiosis to the stage of mitosis, which stages are unique to meiosis and which stages have the same event in botg meiosis and mitosis
Leah Reply
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, Fast fourier transforms. OpenStax CNX. Nov 18, 2012 Download for free at http://cnx.org/content/col10550/1.22
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?