Hi guys, I have a very basic problem. I am able to calculate FFT of an input vector. But now what i want is, to subdivide the input vector into blocks, each having equal number of elements. An FFT needs to be performed on each individual block. The results of these FFTs are then averaged to give the final result. How to accomplish this ? Please pour in.
Calculate FFT in blocks and then average it.
Started by ●August 10, 2010
Reply by ●August 10, 20102010-08-10
On 8/10/2010 8:27 AM, raj malhotra wrote:> Hi guys, > I have a very basic problem. I am able to calculate FFT of an input vector. > > > But now what i want is, to subdivide the input vector into blocks, each > having equal number of elements. An FFT needs to be performed on each > individual block. The results of these FFTs are then averaged to give the > final result. > > How to accomplish this ? Please pour in.It's really simple. 1) Divide the input data into blocks of equal size. (Did the word "vector" confuse you?) Discard any leftover samples. Window each block separately. 2) Perform FFTs on each of the blocks. 3) Since all relative phase information is lost by creating the blocks, compute the magnitudes of the bins. 4) Add like bins from each of the FFTs. Optionally, divide by the number of blocks. In other words, do what you wrote. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 10, 20102010-08-10
On Aug 10, 8:57=A0am, Jerry Avins <j...@ieee.org> wrote:> On 8/10/2010 8:27 AM, raj malhotra wrote: > > > Hi guys, > > I have a very basic problem. I am able to calculate FFT of an input vec=tor.> > > But now what i want is, =A0to subdivide the input vector =A0into blocks=, each> > having equal number of elements. =A0An FFT needs to be performed on eac=h> > individual block. =A0The results of these FFTs are then averaged to giv=e the> > final result. > > > How to accomplish this ? Please pour in. > > It's really simple. > > 1) Divide the input data into blocks of equal size. (Did the word > "vector" confuse you?) Discard any leftover samples. Window each block > separately. > > 2) Perform FFTs on each of the blocks. > > 3) Since all relative phase information is lost by creating the blocks, > compute the magnitudes of the bins. > > 4) Add like bins from each of the FFTs. Optionally, divide by the number > of blocks. > > In other words, do what you wrote. >he *might* want to average the squares of the magnitudes (before square rooting). but, unless he has specific information about the signal period, he does need to toss the phase information. r b-j
Reply by ●August 10, 20102010-08-10
On Aug 10, 5:57=A0am, Jerry Avins <j...@ieee.org> wrote:> 3) Since all relative phase information is lost by creating the blocks, > compute the magnitudes of the bins.If you know the block offsets, then relative phase information isn't lost. This allows options such as coherent averaging for narrower bin-centered filtering, or interpolation of more bins or frequencies between blocks using phase vocoder methods. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M http://www.nicholson.com/rhn/dsp.html
Reply by ●August 10, 20102010-08-10
On 8/10/2010 2:58 PM, Ron N. wrote:> On Aug 10, 5:57 am, Jerry Avins<j...@ieee.org> wrote: >> 3) Since all relative phase information is lost by creating the blocks, >> compute the magnitudes of the bins. > > If you know the block offsets, then relative phase information > isn't lost. This allows options such as coherent averaging > for narrower bin-centered filtering, or interpolation of more > bins or frequencies between blocks using phase vocoder > methods.Do you suppose that anyone who asked the original question could manage to do that? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 10, 20102010-08-10
On Aug 10, 3:54=A0pm, Jerry Avins <j...@ieee.org> wrote:> On 8/10/2010 2:58 PM, Ron N. wrote: > > > On Aug 10, 5:57 am, Jerry Avins<j...@ieee.org> =A0wrote: > >> 3) Since all relative phase information is lost by creating the blocks=,> >> compute the magnitudes of the bins. > > > If you know the block offsets, then relative phase information > > isn't lost. =A0This allows options such as coherent averaging > > for narrower bin-centered filtering, or interpolation of more > > bins or frequencies between blocks using phase vocoder > > methods. > > Do you suppose that anyone who asked the original question could manage > to do that?well, Ron's right (and i missed it too). you have to add (or subtract) a linear phase term (same as rotating the complex value) with slope proportional to the known block offset. i think then you have to do the averaging to the complex values of each bin. r b-j
Reply by ●August 10, 20102010-08-10
On 8/10/2010 4:31 PM, robert bristow-johnson wrote:> On Aug 10, 3:54 pm, Jerry Avins<j...@ieee.org> wrote: >> On 8/10/2010 2:58 PM, Ron N. wrote: >> >>> On Aug 10, 5:57 am, Jerry Avins<j...@ieee.org> wrote: >>>> 3) Since all relative phase information is lost by creating the blocks, >>>> compute the magnitudes of the bins. >> >>> If you know the block offsets, then relative phase information >>> isn't lost. This allows options such as coherent averaging >>> for narrower bin-centered filtering, or interpolation of more >>> bins or frequencies between blocks using phase vocoder >>> methods. >> >> Do you suppose that anyone who asked the original question could manage >> to do that? > > well, Ron's right (and i missed it too). you have to add (or > subtract) a linear phase term (same as rotating the complex value) > with slope proportional to the known block offset. i think then you > have to do the averaging to the complex values of each bin.Not have to, but can. Of course Ron is right. Just remember: the OP asked, among other things, how to divide his "vector" into equal-sized "blocks". Do you imagine that he could have phase aligned the transformed blocks without more instruction than he could follow? I've been helping bewbies for a long time. I must have written about my second-grade classmate who began to whimper during the lunch period, but it's worth repeating here. Going home for lunch had been permitted when we were in first grade. The rule changed when we got to second grade and everyone had to bring lunch to school, even my classmate who lived across the street. (It was a local side street, but his mother didn't allow him to cross it alone.) About the second week of school, the guy began to whimper quietly while we we still in the gym where we gathered to eat. I noticed and asked him what was wrong. He said pitifully, "I have to go to the bathroom." I was puzzled. The door to the boy's room was in plain sight. He said "My mommy has to wipe me." I offered to show him how do to that himself, and all was well. The next day, his mother met him as usual at the gate of the schoolyard to guide him across the street*, but the two of them were just standing there when I came out. He had evidently pointed me out to her, because she addressed me when I approached. I assumed I was in for a scolding, but I was wrong. She thanked me warmly for caring for and educating her little darling. Despite being an articulate kid, I probably wouldn't have been able to express what I thought of her parenting skills even had I wanted to. I said only, "You could have showed him yourself if you wanted him to know." Her son was merely ignorant. She was dumb. Jerry ______________________________ * At that age, I would go alone by bus and subway to the Museum of Natural History to spend the day. My parents gave me half a dollar for the day; $.20 for four fares, $.25 for lunch in the cafeteria, and a nickle just so. (Usually a candy bar.) -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 17, 20102010-08-17
>On 8/10/2010 4:31 PM, robert bristow-johnson wrote: >> On Aug 10, 3:54 pm, Jerry Avins<j...@ieee.org> wrote: >>> On 8/10/2010 2:58 PM, Ron N. wrote: >>> >>>> On Aug 10, 5:57 am, Jerry Avins<j...@ieee.org> wrote: >>>>> 3) Since all relative phase information is lost by creating theblocks,>>>>> compute the magnitudes of the bins. >>> >>>> If you know the block offsets, then relative phase information >>>> isn't lost. This allows options such as coherent averaging >>>> for narrower bin-centered filtering, or interpolation of more >>>> bins or frequencies between blocks using phase vocoder >>>> methods. >>> >>> Do you suppose that anyone who asked the original question couldmanage>>> to do that? >> >> well, Ron's right (and i missed it too). you have to add (or >> subtract) a linear phase term (same as rotating the complex value) >> with slope proportional to the known block offset. i think then you >> have to do the averaging to the complex values of each bin. > >Not have to, but can. Of course Ron is right. Just remember: the OP >asked, among other things, how to divide his "vector" into equal-sized >"blocks". Do you imagine that he could have phase aligned the >transformed blocks without more instruction than he could follow? > >I've been helping bewbies for a long time. I must have written about my >second-grade classmate who began to whimper during the lunch period, but >it's worth repeating here. > >Going home for lunch had been permitted when we were in first grade. The >rule changed when we got to second grade and everyone had to bring lunch >to school, even my classmate who lived across the street. (It was a >local side street, but his mother didn't allow him to cross it alone.) >About the second week of school, the guy began to whimper quietly while >we we still in the gym where we gathered to eat. I noticed and asked him >what was wrong. He said pitifully, "I have to go to the bathroom." I was >puzzled. The door to the boy's room was in plain sight. He said "My >mommy has to wipe me." I offered to show him how do to that himself, and >all was well. > >The next day, his mother met him as usual at the gate of the schoolyard >to guide him across the street*, but the two of them were just standing >there when I came out. He had evidently pointed me out to her, because >she addressed me when I approached. I assumed I was in for a scolding, >but I was wrong. She thanked me warmly for caring for and educating her >little darling. Despite being an articulate kid, I probably wouldn't >have been able to express what I thought of her parenting skills even >had I wanted to. I said only, "You could have showed him yourself if you >wanted him to know." Her son was merely ignorant. She was dumb. > >Jerry >______________________________ >* At that age, I would go alone by bus and subway to the Museum of >Natural History to spend the day. My parents gave me half a dollar for >the day; $.20 for four fares, $.25 for lunch in the cafeteria, and a >nickle just so. (Usually a candy bar.) >-- >Engineering is the art of making what you want from things you can get. >�����������������������������������������������������������������������Hi guys, I started this ques, but sorry i didn't checked the posts. I should clear you that i am not facing a problem in "dividing the input vector" in equal sizes and neither i am confused with the word "vector". lolest!! This , even the kid whom you helped ,would have done. See, i want that each block should have block size as a power of two. So, if the user enter block size as 3, my code will take it 4, likewise if block size is given by user as 13, my code will take it 16. This i have accomplished by : block_size = 1 << (long)ceil(log((double)block_size)/log(2.0)); Now, let say, i enter block_size=6, overlap=1 and no. of elemnts=18 (from 1 to 18) . Than my code will make three blocks of block_size =8 each. 1st block has elements from 1 to 8. 2nd block has elements from 8 to 15 (since overlap is 1). third block has elements as block3[0]=15 (since overlap is 1), block3[1]=16, block3[2]=17, block3[3]=18. Now, i can fill anything or lets say zero in block3[4] to block3[7]. Applied FFTW on each block, and now i am averaging it in this way(of what i am not sure) : lets say output of 3 fft's are in 3 arrays namely arr1. arr2, arr3. Final output after averaging is in "output" array. So i did this, output[0]= (arr1[0]+arr2[0]+arr3[0])/3; till output[3]. this is how i calculated. And for output[4]=(arr1[4]+arr2[4]); till output[7]. The result i am getting is not satisfactory. I will be grateful if you guys could pour in. Thanks & Regards, Raj.
Reply by ●August 17, 20102010-08-17
>>On 8/10/2010 4:31 PM, robert bristow-johnson wrote: >>> On Aug 10, 3:54 pm, Jerry Avins<j...@ieee.org> wrote: >>>> On 8/10/2010 2:58 PM, Ron N. wrote: >>>> >>>>> On Aug 10, 5:57 am, Jerry Avins<j...@ieee.org> wrote: >>>>>> 3) Since all relative phase information is lost by creating the >blocks, >>>>>> compute the magnitudes of the bins. >>>> >>>>> If you know the block offsets, then relative phase information >>>>> isn't lost. This allows options such as coherent averaging >>>>> for narrower bin-centered filtering, or interpolation of more >>>>> bins or frequencies between blocks using phase vocoder >>>>> methods. >>>> >>>> Do you suppose that anyone who asked the original question could >manage >>>> to do that? >>> >>> well, Ron's right (and i missed it too). you have to add (or >>> subtract) a linear phase term (same as rotating the complex value) >>> with slope proportional to the known block offset. i think then you >>> have to do the averaging to the complex values of each bin. >> >>Not have to, but can. Of course Ron is right. Just remember: the OP >>asked, among other things, how to divide his "vector" into equal-sized >>"blocks". Do you imagine that he could have phase aligned the >>transformed blocks without more instruction than he could follow? >> >>I've been helping bewbies for a long time. I must have written about my >>second-grade classmate who began to whimper during the lunch period, but>>it's worth repeating here. >> >>Going home for lunch had been permitted when we were in first grade. The>>rule changed when we got to second grade and everyone had to bring lunch>>to school, even my classmate who lived across the street. (It was a >>local side street, but his mother didn't allow him to cross it alone.) >>About the second week of school, the guy began to whimper quietly while >>we we still in the gym where we gathered to eat. I noticed and asked him>>what was wrong. He said pitifully, "I have to go to the bathroom." I was>>puzzled. The door to the boy's room was in plain sight. He said "My >>mommy has to wipe me." I offered to show him how do to that himself, and>>all was well. >> >>The next day, his mother met him as usual at the gate of the schoolyard >>to guide him across the street*, but the two of them were just standing >>there when I came out. He had evidently pointed me out to her, because >>she addressed me when I approached. I assumed I was in for a scolding, >>but I was wrong. She thanked me warmly for caring for and educating her >>little darling. Despite being an articulate kid, I probably wouldn't >>have been able to express what I thought of her parenting skills even >>had I wanted to. I said only, "You could have showed him yourself if you>>wanted him to know." Her son was merely ignorant. She was dumb. >> >>Jerry >>______________________________ >>* At that age, I would go alone by bus and subway to the Museum of >>Natural History to spend the day. My parents gave me half a dollar for >>the day; $.20 for four fares, $.25 for lunch in the cafeteria, and a >>nickle just so. (Usually a candy bar.) >>-- >>Engineering is the art of making what you want from things you can get. >>����������������������������������������������������������������������� > > >Hi guys, >I started this ques, but sorry i didn't checked the posts. I should clear >you that i am not facing a problem in "dividing the input vector" inequal>sizes and neither i am confused with the word "vector". lolest!! This , >even the kid whom you helped ,would have done. >See, i want that each block should have block size as a power of two. So, >if the user enter block size as 3, my code will take it 4, likewise if >block size is given by user as 13, my code will take it 16. This i have >accomplished by : > >block_size = 1 << (long)ceil(log((double)block_size)/log(2.0)); > >Now, let say, i enter block_size=6, overlap=1 and no. of elemnts=18(from>1 to 18) . Than my code will make three blocks of block_size =8 each. 1st >block has elements from 1 to 8. 2nd block has elements from 8 to 15(since>overlap is 1). third block has elements as block3[0]=15 (since overlap is >1), block3[1]=16, block3[2]=17, block3[3]=18. Now, i can fill anything or >lets say zero in block3[4] to block3[7]. > >Applied FFTW on each block, and now i am averaging it in this way(of whati>am not sure) : lets say output of 3 fft's are in 3 arrays namely arr1. >arr2, arr3. Final output after averaging is in "output" array. So i did >this, >output[0]= (arr1[0]+arr2[0]+arr3[0])/3; till output[3]. >this is how i calculated. >And for output[4]=(arr1[4]+arr2[4]); till output[7]. > >The result i am getting is not satisfactory. I will be grateful if youguys>could pour in. > >Thanks & Regards, >Raj. > >Sorry, its is : output[4]=(arr1[4]+arr2[4])/2; till output[7]
Reply by ●August 17, 20102010-08-17
>>>On 8/10/2010 4:31 PM, robert bristow-johnson wrote: >>>> On Aug 10, 3:54 pm, Jerry Avins<j...@ieee.org> wrote: >>>>> On 8/10/2010 2:58 PM, Ron N. wrote: >>>>> >>>>>> On Aug 10, 5:57 am, Jerry Avins<j...@ieee.org> wrote: >>>>>>> 3) Since all relative phase information is lost by creating the >>blocks, >>>>>>> compute the magnitudes of the bins. >>>>> >>>>>> If you know the block offsets, then relative phase information >>>>>> isn't lost. This allows options such as coherent averaging >>>>>> for narrower bin-centered filtering, or interpolation of more >>>>>> bins or frequencies between blocks using phase vocoder >>>>>> methods. >>>>> >>>>> Do you suppose that anyone who asked the original question could >>manage >>>>> to do that? >>>> >>>> well, Ron's right (and i missed it too). you have to add (or >>>> subtract) a linear phase term (same as rotating the complex value) >>>> with slope proportional to the known block offset. i think then you >>>> have to do the averaging to the complex values of each bin. >>> >>>Not have to, but can. Of course Ron is right. Just remember: the OP >>>asked, among other things, how to divide his "vector" into equal-sized >>>"blocks". Do you imagine that he could have phase aligned the >>>transformed blocks without more instruction than he could follow? >>> >>>I've been helping bewbies for a long time. I must have written about my>>>second-grade classmate who began to whimper during the lunch period,but> >>>it's worth repeating here. >>> >>>Going home for lunch had been permitted when we were in first grade.The> >>>rule changed when we got to second grade and everyone had to bringlunch> >>>to school, even my classmate who lived across the street. (It was a >>>local side street, but his mother didn't allow him to cross it alone.) >>>About the second week of school, the guy began to whimper quietly while>>>we we still in the gym where we gathered to eat. I noticed and askedhim> >>>what was wrong. He said pitifully, "I have to go to the bathroom." Iwas> >>>puzzled. The door to the boy's room was in plain sight. He said "My >>>mommy has to wipe me." I offered to show him how do to that himself,and> >>>all was well. >>> >>>The next day, his mother met him as usual at the gate of the schoolyard>>>to guide him across the street*, but the two of them were just standing>>>there when I came out. He had evidently pointed me out to her, because >>>she addressed me when I approached. I assumed I was in for a scolding, >>>but I was wrong. She thanked me warmly for caring for and educating her>>>little darling. Despite being an articulate kid, I probably wouldn't >>>have been able to express what I thought of her parenting skills even >>>had I wanted to. I said only, "You could have showed him yourself ifyou> >>>wanted him to know." Her son was merely ignorant. She was dumb. >>> >>>Jerry >>>______________________________ >>>* At that age, I would go alone by bus and subway to the Museum of >>>Natural History to spend the day. My parents gave me half a dollar for >>>the day; $.20 for four fares, $.25 for lunch in the cafeteria, and a >>>nickle just so. (Usually a candy bar.) >>>-- >>>Engineering is the art of making what you want from things you can get. >>>����������������������������������������������������������������������� >> >> >>Hi guys, >>I started this ques, but sorry i didn't checked the posts. I shouldclear>>you that i am not facing a problem in "dividing the input vector" in >equal >>sizes and neither i am confused with the word "vector". lolest!! This , >>even the kid whom you helped ,would have done. >>See, i want that each block should have block size as a power of two.So,>>if the user enter block size as 3, my code will take it 4, likewise if >>block size is given by user as 13, my code will take it 16. This i have >>accomplished by : >> >>block_size = 1 << (long)ceil(log((double)block_size)/log(2.0)); >> >>Now, let say, i enter block_size=6, overlap=1 and no. of elemnts=18 >(from >>1 to 18) . Than my code will make three blocks of block_size =8 each.1st>>block has elements from 1 to 8. 2nd block has elements from 8 to 15 >(since >>overlap is 1). third block has elements as block3[0]=15 (since overlapis>>1), block3[1]=16, block3[2]=17, block3[3]=18. Now, i can fill anythingor>>lets say zero in block3[4] to block3[7]. >> >>Applied FFTW on each block, and now i am averaging it in this way(ofwhat>i >>am not sure) : lets say output of 3 fft's are in 3 arrays namely arr1. >>arr2, arr3. Final output after averaging is in "output" array. So i did >>this, >>output[0]= (arr1[0]+arr2[0]+arr3[0])/3; till output[3]. >>this is how i calculated. >>And for output[4]=(arr1[4]+arr2[4]); till output[7]. >> >>The result i am getting is not satisfactory. I will be grateful if you >guys >>could pour in. >> >>Thanks & Regards, >>Raj. >> >> > Sorry, its is : output[4]=(arr1[4]+arr2[4])/2; till output[7]Hi guys, I started this ques, but sorry i didn't checked the posts. I should clear you that i am not facing a problem in "dividing the input vector" in equal sizes and neither i am confused with the word "vector". lolest!! This ,even the kid whom you helped ,would have done. See, i want that each block should have block size as a power of two. So, if the user enter block size as 3, my code will take it 4, likewise if block size is given by user as 13, my code will take it 16. This i have accomplished by : block_size = 1 << (long)ceil(log((double)block_size)/log(2.0)); Now, let say, i enter block_size=6, overlap=1 and no. of elemnts=18 (from 1 to 18) . Than my code will make three blocks of block_size =8 each. 1st block has elements from 1 to 8. 2nd block has elements from 8 to 15 (since overlap is 1). third block has elements as block3[0]=15 (since overlap is 1), block3[1]=16, block3[2]=17, block3[3]=18. Now, i can fill anything or lets say zero in block3[4] to block3[7]. Applied FFTW on each block, and now i am averaging it in this way(of what i am not sure) : lets say output of 3 fft's are in 3 arrays namely arr1. arr2, arr3. Final output after averaging is in "output" array. So i did this, output[0]= (arr1[0]+arr2[0]+arr3[0])/3; till output[3]. this is how i calculated. And for output[4]=(arr1[4]+arr2[4])/2; till output[7]. The result i am getting is not satisfactory. I will be grateful if you guys could pour in. Thanks & Regards, Raj.
