Why does fir2 do such strange thing for odd filter order (even number of taps)?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Why does fir2 do such strange thing for odd filter order (even number of taps)?

Lev Serebryakov
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512


 I'm trying to understand implementation of fir2 function from package
"signal". It has one strange place: ifft() call itself. Now it looks like

## Transform frequency response into time response and
## center the response about n/2, truncating the excess
if (rem(n,2) == 0)
 b = ifft([grid ; grid(grid_n:-1:2)]);
 mid = (n+1)/2;
 b = real ([ b([end-floor(mid)+1:end]) ; b(1:ceil(mid)) ]);
else
 ## Add zeros to interpolate by 2, then pick the odd values below.
 b = ifft([grid ; zeros(grid_n*2,1) ;grid(grid_n:-1:2)]);
 b = 2 * real([ b([end-n+1:2:end]) ; b(2:2:(n+1))]);
endif

 And I don't understand "Add zeros to interpolate by 2, then pick the
odd values below." part. Why does it do this
interpolate-and-take-odd-values? Why it is required only for even
number of taps? Why does it takes odd values? Is it critical, or even
ones will work too?

 I've read several textbooks, articles and tutorials about FFT-based
FIR designing, and no one mention special processing for even number
of taps (odd order). Every source I read is in agreement with method,
which is used for even order — mirror specter, take ifft(), rotate. It
is clear. And second branch is complete mistery for me.

 I've found this old post

http://octave.1599824.n4.nabble.com/fir1-bug-for-odd-orders-td4642204.html

 But it doesn't explain anything to me, as I don't know which "the
long standing bug about fir1" it refers to, and could not find this
bug in current bugtracker (yes, it is very old post in discontinued
mailing list).

 Could somebody explain this "magic" to me or point to some
explanation on Internet?

 Thank you.

- --
// Black Lion AKA Lev Serebryakov
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)

iQJ8BAEBCgBmBQJUYz8QXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w
ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRGOTZEMUNBMEI1RjQzMThCNjc0QjMzMEFF
QUIwM0M1OEJGREM0NzhGAAoJEOqwPFi/3EePsPwQAJwBcDSexg7Ju3u3J//tzadH
3x+E9GDAWD3UaPB1Z2xW1FF1/yhE1W+OU061P9sr3YusywwpKhwRGjooFXxGW3kS
cMtZr7VBdLxnJQmaU/o8OiwDgbP6Bjqs8vobjrclnsYk1Lnm3od06x/xz5vKxZhN
VWNOA6f9Gazg5NeeaAlL8mXUx9oWPBuH0k9qnLbRUDuCldypDL2/IbR+AO/kcQeC
+hw2oLlDX184ZD4jmUKhKBaCghQC71xRgP8KsObQAAIx01N6ItfGAb+Di47yEbZS
lwkJuLlPV5M0VkuprStmOFTddMb8R8utvXVWpLKvn4vXmolDdtZISsZZVlD5qAg1
8CGHWlY3BejSZ090hSbA3DGJ72fGz57xRfq3lb+qBOmSV1szOeXTuqo8xuKgEtF2
fjanINl6LVDTIdsRROKdz/w89BiOxdaXCFdCwX+0EJeaMBC/2tZ/xcRg5EikFjti
PfmEznLeG1znDDAQrnRJztuXdpnMUuREHhgfQq+XiHb9xgrYFnE4JAE0erjNPxW9
z3TGnDNV/gvu+AR9OGUsLDOpwS40WTmpZXCnwd7P6bMPlh4JfmR1B6xBNBerT0iK
yeDLH7f+jBDYKCS3Om1jalTnC8+WSXWGSyhEnrbymMzwVOucLWMJQGBipQOPqLYu
GAh+1vjuWsWfIH7w/9ax
=EOu2
-----END PGP SIGNATURE-----

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Why does fir2 do such strange thing for odd filter order (even number of taps)?

Mike Miller
Hi Lev,

On Wed, Nov 12, 2014 at 14:05:52 +0300, Lev Serebryakov wrote:

>  And I don't understand "Add zeros to interpolate by 2, then pick the
> odd values below." part. Why does it do this
> interpolate-and-take-odd-values? Why it is required only for even
> number of taps? Why does it takes odd values? Is it critical, or even
> ones will work too?
>
>  I've read several textbooks, articles and tutorials about FFT-based
> FIR designing, and no one mention special processing for even number
> of taps (odd order). Every source I read is in agreement with method,
> which is used for even order — mirror specter, take ifft(), rotate. It
> is clear. And second branch is complete mistery for me.
Have you read about the differences between type I and type II FIR
filters? A type II filter is a symmetric filter with an odd order. This
is what this second case in fir2.m that you are asking about is dealing
with.

The interpolate-ifft-decimate is done to get the half-sample group delay
necessary for a type II filter. If that's not clear, I'd recommend
stepping through the function or doing a simple version of it yourself
to see what the results look like at each step.

>  I've found this old post
>
> http://octave.1599824.n4.nabble.com/fir1-bug-for-odd-orders-td4642204.html
>
>  But it doesn't explain anything to me, as I don't know which "the
> long standing bug about fir1" it refers to, and could not find this
> bug in current bugtracker (yes, it is very old post in discontinued
> mailing list).

I don't know about this either, that was before my time working with
Octave.

HTH,

--
mike

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Why does fir2 do such strange thing for odd filter order (even number of taps)?

Lev Serebryakov
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 13.11.2014 05:32, Mike Miller wrote:

>> And I don't understand "Add zeros to interpolate by 2, then pick
>> the odd values below." part. Why does it do this
>> interpolate-and-take-odd-values? Why it is required only for
>> even number of taps? Why does it takes odd values? Is it
>> critical, or even ones will work too?
>>
>> I've read several textbooks, articles and tutorials about
>> FFT-based FIR designing, and no one mention special processing
>> for even number of taps (odd order). Every source I read is in
>> agreement with method, which is used for even order — mirror
>> specter, take ifft(), rotate. It is clear. And second branch is
>> complete mistery for me.
>
> Have you read about the differences between type I and type II FIR
> filters?
 Of course. It is hard to miss this topic :)

> A type II filter is a symmetric filter with an odd order. This is
> what this second case in fir2.m that you are asking about is
> dealing with.
 I don't understand, why it is done in such strange way :)

> The interpolate-ifft-decimate is done to get the half-sample group
> delay necessary for a type II filter.
 I've been thought other way around: Type II is symmetrical/even taps
(by definition) and half-sample delay is only property. But now I
start to understand this oversampling thing, yes.

 Thank you.

- --
// Black Lion AKA Lev Serebryakov
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)

iQJ8BAEBCgBmBQJUZLolXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w
ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRGOTZEMUNBMEI1RjQzMThCNjc0QjMzMEFF
QUIwM0M1OEJGREM0NzhGAAoJEOqwPFi/3EePi0IP/2MkH3Vvi2zB+nc8M7ss6F3w
NkGN2OBUiyb+Bjl0LdzOVapWIP2oFTJF8vR5IjcrypQGpvwCuo0h2dr1r+hcYm86
XVFXCGavctSB1Igg5e9gbQWMQXzjBiBsmwz7Wq2CKyh72ZJz9IotsPUJSmnM54WC
XVRJ+wOlIzLB9IAfUbMNvwM35l7WyPoD6DK6AMHQjl8W2rVzW69AMue7ryyu+KI1
96vxhJrla5U5hrbC5G1KvmJkGhaKnezBb/xbCLB1Pize6Rr41p69EPhWyVCOrId3
i9KNgbqAx1mQggrfTqQw+cnqFfyBzE+css6EKwhUs8ZQOx2Tlf+/z7Nus3nMNGr6
1BFYHkG/f/gda938CfHt1kJ2qZyW87IHdjg63tRyaNoX8yGrSOnU0JLRyLaz8EeZ
cR2D+V6RyAD2zEnkylcz/bwBd8cou05YfWqZsdflfurhs3k7XISVw2EbTaQGpKzb
J3/SfWXhTfOYQzpghH6L2Ho4qpvRK3PNsPe1tNmEA3e15BVKYv0E6jhaGHOgoVk6
SEOGCMd65jRRBNGRBWcOvH0n5ae9t2cywknn5SBSDK6rGlpmQbVNgMd2AdHWm0fh
aRJpiqdCCyj9K8Th/Lfa79PNeDyhHtZqXr5ZHmY52xCiw4v0W/yDDXl9HZeCGDqf
ycFOjUD0a8x67tGL4kDP
=qEs6
-----END PGP SIGNATURE-----

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave