The figures above are made with MatrixPlot after implementing the Fast Fourier transform using the code in the NKS book The one on the left is the discrete Fourier transform, and the one on the right is the FFT matrix from the book (I believe there are many others). The one in the middle comes from bit reversal. It can be simplified, but I don’t know how to simplify it algorithmically.
Book Code from NKS online
Book Code from NKS online
In[]:=
DFTMatrix[n_]:=Table[Exp[2Pi*I*i*j/n],{i,0,n-1},{j,0,n-1}]
In[]:=
BitReverseOrder2[n_]:=SortBy[Range[0,2^n-1],Reverse[IntegerDigits[#,2,n]]&]
In[]:=
BitReverseOrder[n_Integer]:=Map[FromDigits[Reverse[#],2]&,IntegerDigits[Range[0,n-1],2,BitLength[n]-1]]+1
In[]:=
BitReverseOrder[a_List]:=a[[BitReverseOrder[Length[a]]]]
Networks from Bit-Reversal
Networks from Bit-Reversal
Given a (partial) function on the integers one gets a network. In this case, the function is bit-reverse.
The networks look similar but what rule makes them? Is there a local rule for it?
In[]:=
Column[Table[Graph[Flatten[Table[{If[n+1<2^k,Style[nn+1,Blue],Nothing],If[FromDigits[Reverse[IntegerDigits[n,2,k]],2]≥n,Style[nFromDigits[Reverse[IntegerDigits[n,2,k]],2],Red],Nothing]},{n,0,2^k-1}]]],{k,8}]]
Out[]=
In[]:=
Grid[Table[{k,Graph[Flatten[Table[{If[n+1<2^k,nn+1,Nothing],If[FromDigits[Reverse[IntegerDigits[n,2,k]],2]>n,nFromDigits[Reverse[IntegerDigits[n,2,k]],2],Nothing]},{n,0,2^k-1}]],If[k<4,VertexLabelsAutomatic,VertexLabelsNone]]},{k,8}],FrameAll]
Out[]=
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 |
Makes edges of arbitrarily long connection. Meaning there is a short way and a fast way, from two perspectives.
In[]:=
Grid[Table[{k,Graph[Flatten[Table[{If[n+1<2^k,nn+1,Nothing],If[FromDigits[Reverse[IntegerDigits[n,2,k]],2]>n,nFromDigits[Reverse[IntegerDigits[n,2,k]],2],Nothing]},{n,0,2^k-1}]],If[k<4,VertexLabelsAutomatic,VertexLabelsNone]],Length[Flatten[Table[{If[n+1<2^k,nn+1,Nothing],If[FromDigits[Reverse[IntegerDigits[n,2,k]],2]>n,nFromDigits[Reverse[IntegerDigits[n,2,k]],2],Nothing]},{n,0,2^k-1}]]]},{k,8}],FrameAll]
Out[]=
Basic FFT
Basic FFT
Rewrite the list
Take every second element
Take the odds and evens, keeping the overall length the same
Translate so they have the white cells = 0 in the same place
Downsample
Repeat
To go backwards, you add instead of splitting.
Visualizing DFT
Visualizing DFT
Comparing DFT with Bit-Reversed Basis with the FFT from the book
Comparing DFT with Bit-Reversed Basis with the FFT from the book
Simplifying the DFT by hand
Simplifying the DFT by hand
It seems that there are ways to simplify the picture of the DFT by carefully choosing a basis, which differs from the bit-reversal basis.
Not sure what the pattern is.
Looks good, but we can go further to simplify the lower right.
This one finally simplifies it.
Not sure this is maximally simplified.