# 0.2 Multidimensional index mapping  (Page 2/6)

 Page 2 / 6

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}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}\text{and}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}{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}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}\text{or}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}{K}_{2}=b{N}_{1},\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}\text{but}\phantom{\rule{4.pt}{0ex}}\text{not}\phantom{\rule{4.pt}{0ex}}\text{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 $\left(N={R}^{M}\right)$ and a mixed radix [link] .

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

$k={\left(\left({K}_{3}{k}_{1}+{K}_{4}{k}_{2}\right)\right)}_{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

$\stackrel{^}{x}\left({n}_{1},{n}_{2}\right)=x{\left(\left({K}_{1}{n}_{1}+{K}_{2}{n}_{2}\right)\right)}_{N}$
$\stackrel{^}{X}\left({k}_{1},{k}_{2}\right)=X{\left(\left({K}_{3}{k}_{1}+{K}_{4}{k}_{2}\right)\right)}_{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\left(k\right)=\sum _{{n}_{2}=0}^{{N}_{2}-1}\sum _{{n}_{1}=0}^{{N}_{1}-1}\phantom{\rule{4pt}{0ex}}x\left(n\right)\phantom{\rule{4pt}{0ex}}{W}_{N}^{{K}_{1}{K}_{3}{n}_{1}{k}_{1}}\phantom{\rule{4pt}{0ex}}{W}_{N}^{{K}_{1}{K}_{4}{n}_{1}{k}_{2}}\phantom{\rule{4pt}{0ex}}{W}_{N}^{{K}_{2}{K}_{3}{n}_{2}{k}_{1}}\phantom{\rule{4pt}{0ex}}{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

${\left(\left({K}_{1}{K}_{4}\right)\right)}_{N}=0\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}\text{and/or}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}\phantom{\rule{4pt}{0ex}}{\left(\left({K}_{2}{K}_{3}\right)\right)}_{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

$\stackrel{^}{C}\left({k}_{1},{k}_{2}\right)=C\left(k\right)=\sum _{{n}_{2}=0}^{3}\sum _{{n}_{1}=0}^{3}\phantom{\rule{4pt}{0ex}}x\left(n\right)\phantom{\rule{4pt}{0ex}}{W}_{4}^{{n}_{1}{k}_{1}}\phantom{\rule{4pt}{0ex}}{W}_{16}^{{n}_{2}{k}_{1}}\phantom{\rule{4pt}{0ex}}{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 $\stackrel{^}{x}\left({n}_{1},{n}_{2}\right)$ , 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 ?
Wht at the criteria for market ?
Amos
what is difference between monitory policy and fiscal policy?
monetary policy is a policy thrust by National Govt(CBN) to influence government spending, purchase &taxes
Frank
necessity of economics
I will say want,choice,opportunity cost,scarcity,scale of preference
Alao
what is monopoly market.How price output are determined under monopoly market
bisham
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.
Frank
Monopoly market:firm has market power & does not respond to market price
Frank
Explain the process of price determination under perfect competition market with suitable diagram
Price determination under perfect competition via this process :firms have no market power to influence price rather firms respond to market price.
Frank
price is different from demand- demand is amount of commodity
demand is amount /quantity of commodity a potential buyer is willing to buy at a given price at market
Frank
demand is a desire of customer on commodity with the ability to pay it and willing to buy it at given price of commodity
Harika
demand is price of what
show that shortrun average cost
what is economics
what is money
Mbah
what is money
Mbah
Difine macro economics
agaba
money is a medium of exchange between goods and services,maybe inform of currency.
Wesonga
Economics is study of how human beings strive to satisfy numerous wants using limited available resources.
Wesonga
how do you find the maximum number of workers the firms should employ order to produce where there are increasing returns
Jane
what are implications of computing national income?.
agaba
pl
MUDASIRU
what is the formulae for calculating national income
MUDASIRU
it calculated by value added method
Praveen
classify the production units like agriculture, banking, transport etc
Praveen
money is anything that is generally acceptetable for human
Ogbaji
Estimate the net value added(NVA) at fixed cost by each industrial structure
Praveen
definition of unemployment
what are the causes of unemployment?
The main causes of unemployment are listed below. 1. Frictional unemployment 2. Cyclical unemployment 3. Structural unemployment
assani
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.
Yonathan
would opportunity cost exist if there was no scarcity?
assani
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
assani
Politics
Job
politics has done what?
assani
consider time assani
Mary
I'm Emmanuel,...I taught the main cause is the change in gov't.
Emmanuel
...Lack of capital to set up a firm respectively
Emmanuel
🙈
Emmanuel
I would like to bring in Educational levels can also be the cause the cause of the problem respectively
Emmanuel
I think the main causes of unemployment is lack of INFRASTRUCTURAL DEVELOPMENT OVER POPULATION OVER DEPENDENT ON GOVERNMENT LACK OF SELF EMPOWERMENT...
ananti
lack of skills among the new generation is the serious issue.
Vishal
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.
Joe
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...
Joe
can someone Explain Expansionary Monetary Policy and Contractionary Monetary Policy Using one of the instrument of Monetary Policy? Please am kinda lost here?. ta
using a graph show the case of substitute and compliment goods
can anyone give me a simple explanation to Five Sector Macroeconomics?
Emmanuel
Can someone please define what economics is
economics simply is a social science subject that study human behavior.
dajan
economics is a social science which studies human behaviour as a relationship between ends and scarce means that has alternative uses
Alao
Can someone please tell me how to calculate GDP
Emmanuel
emmanual kapal to calculate GDP (Gross Domestic Product) has three method in calculating it (1)income approach (2) expenditure approach (3) value added method
Alao
thanks Alae
Emmanuel
u are welcome
Alao
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 .
Joe
what is the law of demand
keep other thing constant, when the price increases demand decrease when the price decreases demand increases of the commodity.
sj
all things being equal,quantity demanded decrease as price increase and increase as price decrease
Seth
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...
Joe
Other thing remain constant the low price of commodity the high quantity of commodity and vice versa is true
Baraka
Explain Effective demand
What is effective demand
Anita
like Modi is in demand...best example of effective demand
Pranav
Don't get you
Anita
Anita you mean you don't get me or who?
Onyeking
level of demand that represents a real intention to purchase by people with the means to pay
Pranav
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
Got questions? Join the online conversation and get instant answers!