Séminaire Lotharingien de Combinatoire, B18r (1987), 8 pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1988, 358/S-18, p.
119-126.]
Ulrich Oberst
Explizite Rekursionsformeln zur schnellen
Fouriertransformation
Abstract.
The Fast Fourier Transform plays an important role in many areas of
applied mathematics. An essential idea is the reduction of the
Fourier transform of a group to the one of subgroups or factor groups.
In this lecture, I provide explicit and easily programmable
rrecursion formulas in the general case of a finite commutative group.
The generalization to non-commutative groups (as for example in a
paper by Beth) is possible but still needs to be carried out in detail.
The following version is available:
The paper has been finally published under the title
"Some combinatorial properties of the Thue-Morse sequence
and a problem in semigroups" in
Theoret. Comput. Sci. 63 (1989), 333-348.