
(51) 
A(x) = A^{[0]}(x^{2}) + x A^{[1]}(x^{2})  (52) 
()^{2} = ()^{2}  (53) 
=   (54) 
1,,,...,  (55) 
1,,,...,  (56) 
,,...,  (57) 
1,  ,  ,...,  .  (58) 
The recursive calls of DFT(n, A,) defines a ordering of the coefficients of A shown on Figure 1. Let us call this ordering the DFT ordering of A.
THIS PART REQUIRES PROCESSING COMPLETELY BY HAND THE CASE n = 8.
THE FORMULA FOR t IN THE ABOVE ALGORITHM NEEDS TO BE CHECKED.
000, 001, 010, 011, 100, 101, 011, 111  (59) 
000, 100, 010, 110, 001, 101, 110, 111  (60) 
f = f^{+}  f^{} and g = g^{+}  g^{}  (61) 
f g = f^{+}g^{+} + f^{}g^{}  f^{+}g^{}  f^{}g^{+}  (62) 
 c_{k}  (k + 1)   f     f    (63) 