Yesterday I wrote
>
> Could I suggest that the maximum convolution error is likely to occur
> when whole blocks of bits are 1, thus forcing large integers into the
> transform so that rounding/truncation errors are most likely to occur.
>
> Consider the LL test algorithm x' = (x^2 - 2) (mod 2^p - 1)
>
> If x = 1, then x' = -1, x'' = +1, x''' = -1, etc, etc, for all values
Aaarrghhh! I think I must have consumed too much Old Bushmills
brain solvent ... x = 1, x' = x'' = x''' = -1 ... 8*)
> of p. And -1 (mod 2^p - 1) = (2^p - 2) (mod 2^p -1). Furthermore
> 2^p - 2 = 2 * (2^(p-1) - 1), a number which contains (p-1) consecutive
> 1 bits.
Fortunately my error does not affect this argument.
>
> So running a couple of iterations of the LL test algorithm starting
> at 1 (instead of 4), looking at the max convolution error and checking
> that the value of the residual after 2 iterations is 1, might be
> instructive ... ?
Well, I tried it using a modified version of Richard Crandall's generic
C program lucdwt. Starting with 1 instead of 4 gives the correct
residual 0xFFFFFFFFFFFFFFFE (-1 mod (2^p-1)) for all iterations
and with _zero_ error, provided the transform size > p/32.
So, almost all zero bits and almost all one bits are both very easy
on the transform.
Is it possible to generate "worst case" data, and, if so, would
anyone care to suggest what it might be? e.g. I remember we used
to fill space with 0xE5 on FM disks, or 0x6DB6 on MFM disks,
because these bit patterns were particularly difficult for the
hardware to cope with - thus, if the test pattern was reliable, the
data should be safe.
Bearing in mind the strong links between signal processing and
Fourier transforms, this illustration may possibly be not entirely
without relevance.
My feeling is that running the LL test itself, starting at 4, is
probably as effective a way as any of pseudo-randomly generating
bit patterns for the purpose of testing the FFT logic, unless
someone can demonstrate a better method. (Of course it takes a
few iterations for the mod 2^p-1 to "kick in" and start to
"randomize" the bit pattern - but after less than 50 iterations the
initial conditions have been well and truly obfuscated)
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
