| ™ |
TreeFT: Tree Structured Frequency Analysis
by Tom Veatch
Given a sampled data array \(X[0..2^M-1]\), and a bend count \(b\ in\ 0..(N/2)-1 \), define
\(DFT(b,N=2^M,X) = \large\sum_{s=0}^{N-1} X[s] * e^{isTb/N}\)(\(T=2\pi\)).
Notice the angles (clock hands, powers of an imaginary base-step point on the unit circle in the imaginary plane) \(isTb/N\) rotate around the imaginary plane \(b\) times as the sample count \(s\) ranges from \(0\) to \(N\).
What if the angles always were to rotate once and only once around the imaginary plane?
First, orthogonality of the successive frequencies \(b\) is lost, but not after subtraction.
Second, the amount of data for each successive frequency \(b\) reduces by half. At the end, after not many steps, is one sample per bend and that is indeed the sample itself (modulo subtractions, if we want to try that). Third, the ratio of successive bends is not \(\frac{b+1}{b}\) as with Fourier where quite fine grained frequency analysis occurs at higher and higher frequencies. Instead the ratio between successive bends is \(frac{2}{1}\): it doubles each frequency layer, doing the natural thing. Hence a 1024-point TreeFT will distinguish only 10 frequency bands.
\(TreeFT(v,N=2^M,X)[bits] = \large\sum_{s=y}^{z} X_s * e^{isTb/N}\)It might be friendly to explore this from a few directions, considering the different parameters and values and relationships that may fall out as we build up a tree of such frequency analysis results. So the work will start with a sample array of some size \(N\) and let's make it a convenient power of \(2\), so \(N=2^M\), and so we can subdivide it in half repeatedly until each bin has only one sample, that is, \(M\) times. Then certain dependent figures fall out. Let's let M=5 and examine the pattern:where bits is a positive integer of \(v\) bits counting from 0 to =0 for the first half, for the 2nd half, 00 for the first quarter, 01 for the second quarter, 10 for the third quarter, 11 for the fourth quarter, etc.
and \(y[bits] = \large\sum_{i=0}^{v-1} bits[i]*2^{M-i-1}\)
and \(z[bits] = y[bits+1]-1\).
| \(v=level\ \ \ \ \ \) | \(B=\# bins=2^{v}\ \ \ \ \ \ \) | \(S=\# samples/bin\ \ \ \ \ \ \) | values of y | values of z | c = counter = bits = bin #'s at this level |
| 0 | \(2^0=1\) | \(2^{M-v}=2^5=32\) | 0 | 31 | 0 |
| 1 | \(2^1=2\) | \(2^{M-v}=2^4=16\) | 0,16 | 15,31 | 0,1 |
| 2 | \(2^2=4\) | \(2^{M-v}=2^3=8\) | 0,8,16,24 | 7,15,23,31 | 0,1,2,3 |
| 3 | \(2^3=8\) | \(2^{M-v}=2^2=4\) | 0,4,8,12,16,20,24,28\(\ \ \ \ \ \ \) | 3,7,11,15,19,23,27,31 | 0,1,..7 |
| 4 | \(2^4=16\) | \(2^{M-v}=2^1=2\) | 0,2,4,..30 | 1,3,5,..31 | 0,1,..15 |
| 5 | \(2^5=32\) | \(2^{M-v}=2^0=1\) | 0,1,2,..31 | 0,1,2,..31 | 0,1,..31 |
If you think about the bits in the numbers \(y\) and \(z\) you will see that corresponding values \(y[c] = c<<(M-v)\), and \(z[c] = (c+1)<<(M-v)-1\).
\(TreeFT(v,2^M=N,X)[c] = \large\sum_{s=c<<(M-v)}^{(c+1)<<(M-v)+1} X_s * e^{isTv/N} \)Using a divacon breakdown, we would like to see
\(\begin{align} \text{TreeFT}\ :=\ (\ &\ v=M\ ?\ id \\ & \text{else}\ \text{combine}\ :\ \text{postadjust}\ :\ \text{TreeFT}\ :\ !\text{preadjust}\ :\ d_{lr}) \end{align}\)So preadjust does its work as the tree expands, after the division of the array produces two subarrays. I think it should be its own PDC to calculate a return value p for each subarray, because each of those is an FT, DFT, FFT, or PFT (b==1) of its own. At the same time it needs to keep the data around for the next layer to also work on. So let preadjust\(=(PFT[1], subarray[i])\), and !preadjust (leftsubarray, rightsubarray) = (preadjust leftsubarray, preadjust right subarray), the outputs are each \(( p, X )\) with \(p\) a complex frequency, and \(X\) the \(v\)-level data it came from .
The next step in the composition, TreeFT, then takes the data from preadjust which is everything needed, hopefully, to build a tree node in a TreeFT tree. Which is not true because although it has its subtree values in the preadjust outputs, it still has to combine those subarrays and run a PFT on the joint subarray to get its own complex FT[b] sum. I don't like it.
The preadjusts have themselves by now recursively generated their PFT complex sum values, which are then, now, in subtrees contained in the output of each preadjust, so that's a whole subtree now at our own level, except we lack the single complex sum for the data array for our node. We could combine it with \(c_{lr}\) from the subarrays, or this could be initiated before we even did the division in the first place.
Now that makes sense. Fix \(d_{treeft}\) such that first it takes the array it is about to divide and runs PFT[b=0] on it yielding a complex sum \(p\), and THEN it splits the data array like \(d_{lr}\) normally does. Putting these into a 3-tuple, \(d_{tree}\) yields that to its caller. Something then applies a recursive call of some kind to the 3-tuple's two data arrays. Okay let's make the div be \((id,d_{lr}\). then the subarrays are there and the this-node-level array is also there. Then let either preadjust or TreeFT trigger the PFTs cleanly, separating calculation from division:
recurse (3-tuple) \(= (PFT, id, id).\)Since basefunc = id, we are almost good there, but there is no subtree in it, so basefunc should be of 2 samples, and be (PFT of the pair, id, id) so it has the same node-and-daughters structure needed upstairs in the tree.
TreeFT keeps calling itself thus subdividing and recursively subdividing (unless finally at a leaf where only one sample is the whole subarray), forming in this process the whole process we don't have to think about, except that the output of it should be a merge of an adjustment of its daughters' return values, and that means TreeFT itself and its basefunc should be full, proper nodes in the (results) tree, containing its own complex frequency component for its v,c bend count and position in the tree, as well as its daughters.
Let's try the PFT initiation as preadjust, :
preadjust (3-tuple i.e. (array,q,r)) \(= (p,q,r) = (PFT, id, id).\)A tree is a recursion of nodes, each node is itself and its daughters, which if there are two, makes it a 3-tuple including one for self and two for the daughters. So defining the nodes is the whole job. There seems to be a life process of a tree node as a 3-tuple.
- In its first incarnation it is three data arrays (A,A1,A2) where the division \(d_{lr} A = (A1,A2)\).
- In its second incarnation, it is one data array and two complex sum values perhaps including their own (third-incarnation) subtrees, as in ( A, p1, p2 ). or ( A, (p1,(..), (p2,(..) ).
- In its last incarnation, it is all and only complex sum values as in (p (q,(..)), (r,(..))).
So \(d_{tree}\) creates first-incarnation 3-tuples as it recursively builds up the analysis tree.
Then basefunc takes a first incarnation of a preterminal node and directly constructs a final and third incarnation of itself, which is trivial since the frequency analysis of a data frame consisting of a single sample is that sample value itself.
And preadjust takes second incarnations, which, from the bottom near the leaves of the analysis tree, are directly above the pre-terminals and directly include the third-incarnation preterminals. Then preadjust turns the second incarnation into a third incarnation.
Zipping up the tree, everything is finally a third incarnation and you have your tree structured result, where each node is a complex value being a frequency component for its frequency and sub-array, and also points to or contains two subarray frequency components.
Let me describe it again; redundancy doesn't hurt while learning.
So we see that preadjust is a local operation operating only on the data array within the 3-tuple fed to it by our sub-tree-constructing divide function (after basepred/basefunc), and yielding a 3-tuple of a value and two subtrees also comprising values only. (p (q(..),r(..))), which is what we'd like. Whereas \(d_{tree}\) yields up three arrays, one split into the other two.
Working our way up the tree, it looks like our work is already all done: combination = id, postadjust=id. In the case of combine, because both the node and its daughters are already present without active recombination, due to the wierd \(d_{tree}\) division function, the combination step doesn't need to combine anything. The structure of the result is constructed during the division phase and remains throughout the process within the computation graph itself. This violates George's definitional assertion regarding combine functions, namely \(c\ :\ d\ =\ d^{-1}\ :\ d\ =\ id\), although \( c.0\ :\ d.0\ =\ id\ ) and the rest could be considered mere annotation or side information, thus ignoreable for our purposes.
In the case of postadjust, there are already complex values for all nodes in the tree at and below a node by the time preadjust is completed, so there is no work for postadjust to do.
Finally, TreeFT itself is really just the synergy of all this, so it doesn't need to have any other definition of what else it might do; it's really the chain linking each level to the next level, and otherwise (except at the leaf of the tree) it doesn't do anything of itself, Even though TreeFT is the action in the center of it all, is has no other definition than the parallel decomposition gives to the whole process. I'm always looking for TreeFT to do something itself, but that's missing the point, that TreeFT is basically a recursion.
Hence we can write as math:
\(\begin{align} \text{TreeFT}\ :=\ (\ &\ v=M\ ?\ id \\ & \text{else}\ id\ :\ id :\ \text{TreeFT}\ :\ (PFT[1],id,id)\ :\ (id,d_{lr})) \end{align}\)or as Divacon code:
\text{TreeFT}\ :=\ PDC(divide=(id,d_{lr}), combine=id, preadjust=(PFT[1], id, id), postadjust=id, basepred="v=M-1", basefunc=(PFT[1],id,id))where
See the original PFT discussion here.
\(PFT_{b,N}\ X\ =\ c_{eo} : ma(S_b) :\ !\ PFT_{ b,\frac{N}{2}}\ :\ d_{eo}\ X\ \ \ \ \ \) Fourier Transform of data X[0..N-1] at a frequency of b rotations in 0..N-1 samples.
Where: \(c_{eo}\ :\ d_{eo}\ =\ d_{eo}^{-1} : d_{eo} = id\) \(c,d\) mean combine and divide. Here by evens and odds (think deal out, shuffle together). \(ma(w)(a,b) = a + w * b\) Kernel of all the local operations, a multiply and an add \(S_b=e^{iTb/N}\) Basic step angle a.k.a. twiddle factor. \(T=2\pi\).
This work seems a bit drafty, since for example and incidentally, inside level \(v\) node \(C\) we don't actually know our own place in the world, though, we could let \(c=0\), \(c+1=1\), and upstairs let the combine function do the renumbering, assuming numbering is needed which it might not be given the tree structure already encoding it. Similarly it needs to get parameter-passing right; TreeFT might need to be parameterized by \(v,N\) in addition to the data array that it applies to.