Hi folks.
Suppose a data set was 'syncopated' sampled, like
x[n] = {x(T_0), x(T_1),x(T_2),...,x(T_(N-1))}
where
T_n = n(A+B) n even
T_n = n(A+B)+A n odd
and A and B are integers.
Is there a way to use the FFT to directly compute the
spectrum of such a signal? The alternative right now is
to interpolate to a regularly sampled grid, and then use
the FFT.
Rune
FFT on 'syncopated' sampled data?
Started by ●July 8, 2009
Reply by ●July 8, 20092009-07-08
On 8 Jul., 10:56, Rune Allnor <all...@tele.ntnu.no> wrote: Hi Rune> Suppose a data set was 'syncopated' sampled, like > > x[n] =3D {x(T_0), x(T_1),x(T_2),...,x(T_(N-1))} > > where > > T_n =3D n(A+B) =A0 =A0 =A0n even > T_n =3D n(A+B)+A =A0n odd > > and A and B are integers. > > Is there a way to use the FFT to directly compute the > spectrum of such a signal? The alternative right now is > to interpolate to a regularly sampled grid, and then use > the FFT.Yes, there's a better way. If you look at how the FFT works you'll notice that it's a recursive splitting into interleaved sequences. So if you do the first level manually, you have two sequences on a regular grid. So you only have to work out the math on the first level, adapt the phase factors and pass the two subsequences to a regular FFT. Cheers, Andy
Reply by ●July 8, 20092009-07-08
Rune Allnor wrote:> Hi folks. > > Suppose a data set was 'syncopated' sampled, like > > x[n] = {x(T_0), x(T_1),x(T_2),...,x(T_(N-1))} > > where > > T_n = n(A+B) n even > T_n = n(A+B)+A n odd > > and A and B are integers. >Andy gave what looks like a pretty clever answer! Is it really correct that you can do this and not end up with a larger number of samples in frequency? Let's see: Take only the odd case samples. They are regularly spaced. FFT them. Now time shift the original samples by as much as you like. Just for argument's sake let's shift them to be on top of the even samples. The equivalent in frequency is to multiply by e^jxxx. OK. Now FFT the original samples. Now there are two frequency sequences that are based on the samples in time being at the same places/instants. By superposition, the frequency samples must coincide, right? But, the time sequence isn't the same as the original because of the time shift applied. Take a similar case but shift the odd samples to be at exactly n(A+B). Now there are 2*N samples in time that we rather *must* FFT with a 2*N transform. Or, if you want to do superposition again: FFT the even samples .. interspersed with zeros. FFT the odd samples .. interspersed with zeros. Add the two sequences - both in time and frequency together. This yields a filled length 2*N sequence in time and a composite 2*N sequence in frequency. Of course, the odd sequence is in the wrong place in time just as before unless A=B. If A~B then it's probably "better" than the first case. What I'm leading up to here is that I'm not at all sure that you can do any of this in place of doing the following: Calculate C/A = (A+B)/A = 1 + B/A. Just for exposition, assume that C/A (thus B/A) is an integer. Then one could sample at an interval of A/C and have a lot of zero-valued samples. But what if C/A is "too big"? Then one might decide to use an interval K*A/C and move the odd samples by (K-1)*A/C (??)from their original locations. It's not exact but it's "close enough" if the numbers are picked reasonably. If C/A isn't an integer, just use the same process but end up moving the odd samples a different amount. There's still an error in timing but the issue is the same. Either way, you end up with sample intervals C/(K*A) and a bunch of zero-valued samples in time. So, maybe it depends on what you're going to do with the sequences. If time registration of the odd samples isn't all that important then maybe fiddling the phase is OK. Arm waving assessment: You probably shouldn't try to get away with less than 2*N samples. Is the bandwidth increase just due to the closeness of the samples? In the limit, if the samples are close enough together you might average them and use N samples. But I'm sure you've thought of that and it's not acceptable. That means there's information in the *difference* between close samples. If so, you better deal with it. The closer A is to B the clearer the need for 2*N samples. But what if A=B/2? Then you need 3*N samples? It seems so as the minimum interval would be B and there would be one zero sample in time for every two nonzero samples. This seems like a special case of sparse sampling and I'm no expert on that topic. Maybe look there. Fred
Reply by ●July 9, 20092009-07-09
> > Is it really correct that you can do this and not end up with a larger > number of samples in frequency? =A0Let's see: > Take only the odd case samples. =A0They are regularly spaced. > FFT them. > Now time shift the original samples by as much as you like. =A0Just for > argument's sake let's shift them to be on top of the even samples. > The equivalent in frequency is to multiply by =A0e^jxxx. > OK. =A0Now FFT the original samples. > Now there are two frequency sequences that are based on the samples in ti=me> being at the same places/instants. > By superposition, the frequency samples must coincide, right? > But, the time sequence isn't the same as the original because of the time > shift applied. >I don't quite under Fred's this example. As pointed out, the odd time sequence doesn't equal to even time sequence. Thus, besides the e^jxxx, the FFT shouldn't be the same. Why do they coincide? Put it this way, The orignal sequence is x(n) =3D=3D> X(e^jw), n \belong_to Z The odd-case sequence is xo(m) <=3D=3D> x(2n+1), n \belong_to Z The even-case sequence is xe(k) <=3D=3D> x(2n), n \belong_to Z There are well known relations between X(e^jw), XO(e^jw), and XE (e^jw), in particular for real x(n) without lack of generality. But in genaral, they don't coincide. Maybe I have missed the point here. Can shed some light?
Reply by ●July 9, 20092009-07-09
On Jul 8, 1:56 am, Rune Allnor <all...@tele.ntnu.no> wrote:> Hi folks. > ... > Is there a way to use the FFT to directly compute the > spectrum of such a signal? The alternative right now is > to interpolate to a regularly sampled grid, and then use > the FFT. > > RuneI'd try 1) fft the data with odd samples set to zero. (even spectrum) 2) fft the data set with even samples set to zero. (odd spectrum) 3) Weight the second (odd) fft with a complex phase correction vector to remove the time delay 4)Sum the even and corrected odd spectra.. Dale B. Dalrymple
Reply by ●July 9, 20092009-07-09
Verictor wrote:>> Is it really correct that you can do this and not end up with a larger >> number of samples in frequency? Let's see: >> Take only the odd case samples. They are regularly spaced. >> FFT them. >> Now time shift the original samples by as much as you like. Just for >> argument's sake let's shift them to be on top of the even samples. >> The equivalent in frequency is to multiply by e^jxxx. >> OK. Now FFT the original samples. >> Now there are two frequency sequences that are based on the samples in time >> being at the same places/instants. >> By superposition, the frequency samples must coincide, right? >> But, the time sequence isn't the same as the original because of the time >> shift applied. >> > > I don't quite under Fred's this example. As pointed out, the odd time > sequence doesn't equal to even time sequence. Thus, besides the > e^jxxx, the FFT shouldn't be the same. Why do they coincide? Put it > this way, > > The orignal sequence is x(n) ==> X(e^jw), n \belong_to Z > The odd-case sequence is xo(m) <==> x(2n+1), n \belong_to Z > The even-case sequence is xe(k) <==> x(2n), n \belong_to Z > > There are well known relations between X(e^jw), XO(e^jw), and XE > (e^jw), in particular for real x(n) without lack of generality. But in > genaral, they don't coincide. Maybe I have missed the point here. Can > shed some light?Put it differently. You have two sets of data of a signal of bandwidth B, each sampled at a rate slightly greater than B, the samples being interleaved with arbitrary offset. Neither set of samples can reproduce the signal; it is undersampled. What mathematical procedure allows the aliased information from both sets to define an accurate reproduction? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 9, 20092009-07-09
On 9 Jul, 05:58, Jerry Avins <j...@ieee.org> wrote:> Put it differently. You have two sets of data of a signal of bandwidth > B, each sampled at a rate slightly greater than B, the samples being > interleaved with arbitrary offset. Neither set of samples can reproduce > the signal; it is undersampled. What mathematical procedure allows the > aliased information from both sets to define an accurate reproduction?Yep. That's where I ended up, too. It seems interpolation onto a regular grid is the way to go: Interpolate both sequences to the half-point in the A+B intervals, and find the missing values as the average between the two interpolants. Rune
Reply by ●July 9, 20092009-07-09
On Jul 9, 12:09 am, Rune Allnor <all...@tele.ntnu.no> wrote:> On 9 Jul, 05:58, Jerry Avins <j...@ieee.org> wrote: > > > Put it differently. You have two sets of data of a signal of bandwidth > > B, each sampled at a rate slightly greater than B, the samples being > > interleaved with arbitrary offset. Neither set of samples can reproduce > > the signal; it is undersampled. What mathematical procedure allows the > > aliased information from both sets to define an accurate reproduction? >.> Yep. That's where I ended up, too. It seems interpolation .> onto a regular grid is the way to go: Interpolate both .> sequences to the half-point in the A+B intervals, and find .> the missing values as the average between the two interpolants. .> .> Rune If A equals B you already have the required samples for a single fft. If A does not equal B, 'the average' is not a correct interpolation. An accurate interpolation might be more expensive than a second fft, a vector multiply and a vector add per block of samples. Dale B. Dalrymple
Reply by ●July 9, 20092009-07-09
Verictor wrote:>> Is it really correct that you can do this and not end up with a >> larger number of samples in frequency? Let's see: >> Take only the odd case samples. They are regularly spaced. >> FFT them. >> Now time shift the original samples by as much as you like. Just for >> argument's sake let's shift them to be on top of the even samples. >> The equivalent in frequency is to multiply by e^jxxx. >> OK. Now FFT the original samples. >> Now there are two frequency sequences that are based on the samples >> in time being at the same places/instants. >> By superposition, the frequency samples must coincide, right? >> But, the time sequence isn't the same as the original because of the >> time shift applied. >> > > I don't quite under Fred's this example. As pointed out, the odd time > sequence doesn't equal to even time sequence. Thus, besides the > e^jxxx, the FFT shouldn't be the same. Why do they coincide? Put it > this way, > > The orignal sequence is x(n) ==> X(e^jw), n \belong_to Z > The odd-case sequence is xo(m) <==> x(2n+1), n \belong_to Z > The even-case sequence is xe(k) <==> x(2n), n \belong_to Z > > There are well known relations between X(e^jw), XO(e^jw), and XE > (e^jw), in particular for real x(n) without lack of generality. But in > genaral, they don't coincide. Maybe I have missed the point here. Can > shed some light?Light: We aren't talking about the Even part and the Odd part of a function. We are talking about samples whose *indices* are calculated using even or odd values of a base index (n). Fred
Reply by ●July 9, 20092009-07-09
Rune Allnor wrote:> On 9 Jul, 05:58, Jerry Avins <j...@ieee.org> wrote: > >> Put it differently. You have two sets of data of a signal of >> bandwidth B, each sampled at a rate slightly greater than B, the >> samples being interleaved with arbitrary offset. Neither set of >> samples can reproduce the signal; it is undersampled. What >> mathematical procedure allows the aliased information from both sets >> to define an accurate reproduction? > > Yep. That's where I ended up, too. It seems interpolation > onto a regular grid is the way to go: Interpolate both > sequences to the half-point in the A+B intervals, and find > the missing values as the average between the two interpolants. > > RuneRune, Any interpolation, certainly using an average value of samples, takes away from the difference between adjacent samples. I think, and mentioned, that it's the difference between adjacent (i.e. the more closely spaced) sample pairs that contains information that you may or may not need. Presumably you need it. Here is an experiment: Select a grid for the temporal samples that is an integer multiple of some reasonable base like: 2*(A+B) which is the interval of the samples with even-n-based indices. n 0 1 2 3 4 5 ..... 0 B+2A 2B+2A 3B+4A 4B+4A 5B+6A ..... The even-based interval is 2*(B+A) The odd-based interval is also 2*(B+A) of course. Arghhhh...I'd rather use C=A+B n 0 1 2 3 4 5 ..... 0 C+A 2C 3C+A 4C 5C+A ..... The even-based interval is 2C The odd-based interval is also 2C of course and B is just for phase or absolute time. Let's assume that A<C/2 so that the odd-based sample points are closer to the preceding sample point. Then, the minimum sample separation is simply A. Reduce the interval, increase the sampling rate by K so that the intervals for the aforementioned samples is 2C/K. This means that the shorter intervals A are now divided into smaller intervals of A/K plus some error. If A/K can be an integer then the lowest value of K will yield the largest interval / the lowest number of samples. If A/K cannot be an integer (e.g. if A=pi) then the error in registration will be: e=A-K*int(A/K) where "int" means "rounded off to the integer amount" so K*int(A/K)<A. It seems to me that there will clearly be "acceptable" values of "e" such as e~the sampling jitter. There may be much larger acceptable values of "e". Limits might be: 1) just ignore all the odd or even-based samples entirely 2) don't ignore them: (a) Register them within the sample jitter error - lotta samples (b) Register them according to a bandwidth criterion such as this 1/e is a measure of the bandwith that's implied by the error. If 1/2C is 10kHz well, that's nice to know. But, more importantly, 1/A let's say is going to be 50kHz. If 1/e is 5GHz then maybe that's overkill. I would decide that 1/e=100kHz might be the very worst I'd accept. That would be that e=1/2A - the grid would just split the intersample short intervals of length A in half. That would be pretty gross but it's a limit to start working with.... As you well know, any averaging is a type of filter. So you may as well be very clear what the effect of that filter would be. Maybe these "numbers" will help in further looks at it. What I don't know is what is the affect of the sparse sampling - that is, I imagine if one samples at intervals of A and, let's just assume for now that B/A is an integer, then there are some samples "missing" unless A=B. For example, if A=B/2 then there would be 4 sample intervals in the 2B period. That means there are 2 contiguous samples "missing" at B and 3B/2. So a lot depends on the underlying bandwidth. If the bandwidth is <1/2B then the added samples do nothing in theory. If the bandwidth is >1/2B then more samples are needed apparently. If the bandwidth is 1/A (with A<B) then the signal is undersampled - and the smaller is A, the greater the undersampling. So, in part, that means that the bandwidth "W" must be 1/2B < W <1/A for this to make sense. A bit rambling but I hope this helps. Fred
