"Randy Yates" <randy.yates@sonyericsson.com> wrote in message news:xxp7jwtary5.fsf@usrts005.corpusers.net...> > These are sufficiently complex that it's not obvious that integrating > > improves anything. I'd model it. A lot depends on t1 and the noiselevel.> > I'm glad to know that this isn't a trivial problem in which I'veoverlooked> the answer!Randy, It may be that it's a trivial problem for which I have no clue! Fred
An Academic Detection Question
Started by ●April 5, 2004
Reply by ●April 6, 20042004-04-06
Reply by ●April 7, 20042004-04-07
Randy Yates wrote:> Bernhard Holzmayer <holzmayer.bernhard@deadspam.com> writes: > >> Randy Yates wrote: >>...> >> Still without considering noise, the best solution would probably >> compare the signal with levels '0' and '1' and find the nearer. >> >> This in mind, I'd say, that the same approach should work with >> noise applied. >> Averaging would help to reduce noise influence, but as soon as we >> average over t0, it makes things worse. >> >> Using averaging from the left (until close to t0), comparing >> signal with '0' should show high correlation. >> Averaging from the right (until close to t0), comparing signal >> with '1' should show high correlation. > > Two things: 1) we don't know where t0 is!,obvious, but causes another idea ... Why not just assume a step at a certain point tx, subtract it from the signal, and do this with different values of tx, until best fit?> and 2) I'm presuming a > causal system, so we can't really "average from the right" until > we get to that "right" point in time.Not really, ok. However, there's an implicit knowledge about the signal (that it is a step). Using this knowledge we can "average from the right", because a) average value of white noise is zero b) average value of step signal from right is '1' as long as t>t0 So, just assume an average value of '1' and go on averaging. At the same time keep on averaging with the real 'old' values in parallel. As soon as averaging on the '1' provides ( picking Martin's idea) lesser standard deviation than averaging on the other values, we have t>t0. Now, let's do this from both sides, starting with constant average values, which results in 4 average processes: arbitrary number N (of samples), n is current sample 1) A = average(samples n-N+1, n-N+2,..., n) 2) B = average(samples n-N+1, n-N+2,..., n)-1 3) C = average(samples n-2N+1, n-2N+2, n-N) 4) D = average(samples n-2N+1, n-2N+2, n-N)-1 N must be big enough to reduce noise to a level which is sufficient for the level detection, but small enough for the required precision of t0. If such an N exists, task is solvable. As soon as sample n arrives, we know, that t0 = t(n-N). We know that sample n has arrived, if both values B,C reach their minimum and A,D their maximum. (Evaluation of B,C should be sufficient.)>> Then there's the t0-zone, where both evaluations reveal bad >> correlation, with worst conditions at the point t0.Assuming no noise, A is '0' if t<t0 and '1' if t>t0 and D is '0' if t>t0 and '1' if t<t0 if we're averaging, A is 1/2 at t0, so is D. Product will be 0*1=0 everywhere except in the region of t0, where it is near 1/4. That's what I meant. The same should hold with noise, though not so easily visible. A couple of years ago, I built a discriminator based on a DSP, which tried to retrieve a digitally coded signal (DCF, phase modulation +/-5Hz) on a noisy IF signal (voice modulation==noise). I gathered the samples, placed them in a cyclic buffer and compared the expected carrier signal with the measured. Because I knew, that steps could occur only at certain moments (exactly one second after the other) and with distinct phase jumps, this semantic knowledge made it easy to detect the code. A very naive approach, yet it worked. That's, where my idea comes from.
Reply by ●April 7, 20042004-04-07
On 05 Apr 2004 13:50:48 -0400, Randy Yates <randy.yates@sonyericsson.com> wrote:>This has been a question I've had for a long time. I have >simplified it to its basic components. > >You have a signal x(t) composed as > > x(t) = u(t-t0) + n(t), > >where u(t) is the unit step function, t0 is unknown, and n(t) is >stationary white Gaussian noise. You need to be able to detect the >signal "reliably" (I'll leave the definition of that open for now) >within t1 seconds of t0. > >Now the obvious thing to do to increase reliability is to average. >However, if you average, the unit step becomes a ramp. So in order to >detect the averaged signal within the same time constraint, t0+t1, the >threshold of the detector must be lower. But a lower threshold >degrades the reliability. > >So, is it worth it? Is the increase in reliability due to averaging >more than the decrease in reliability due to the reduced threshold? >-- >Randy YatesHi Randy, nothing much useful to you comes to my mind right now. Except that I'm guessing this is an "age old" problem that's been studied by Ph.D'd for decades. I'll bet you can find lots of good info by searching the web for "signal detection" and "matched filters". Good Luck, [-Rick-]
Reply by ●April 7, 20042004-04-07
"Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message news:4073e323.577893562@news.sf.sbcglobal.net...> On 05 Apr 2004 13:50:48 -0400, Randy Yates > <randy.yates@sonyericsson.com> wrote: > I'll bet you can find lots of good info > by searching the web for "signal detection" > and "matched filters". > > Good Luck, > [-Rick-]Yes, indeed. First mention of matched filtering here isn't it? Good idea to search what's available. What if you first start out asking "what is the matched filter to a step?" http://klimt.iwr.uni-heidelberg.de/mip/adaptive_filters/talks/Michael_Eberle_Matched_Filters.pdf Or, as a final exam question: http://www.tele.ntnu.no/akustikk/fag/tt8304/eksamen/exam_2003.pdf Instead of an infinite step input, most practical treatments are for a finite "step" or rectangular pulse of some length. Maybe that means you want a matched filter for a pulse of length t1 because you don't have more time than t1 to detect the leading edge / "step". Should be the same thing I think. Google on "unit step" "matched filter" to find a lot of stuff.... Fred
Reply by ●April 7, 20042004-04-07
"Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes:> "Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message > news:4073e323.577893562@news.sf.sbcglobal.net... > > On 05 Apr 2004 13:50:48 -0400, Randy Yates > > <randy.yates@sonyericsson.com> wrote: > > I'll bet you can find lots of good info > > by searching the web for "signal detection" > > and "matched filters". > > > > Good Luck, > > [-Rick-] > > Yes, indeed. First mention of matched filtering here isn't it? > Good idea to search what's available. > > What if you first start out asking "what is the matched filter to a step?" > > http://klimt.iwr.uni-heidelberg.de/mip/adaptive_filters/talks/Michael_Eberle_Matched_Filters.pdf > > Or, as a final exam question: > > http://www.tele.ntnu.no/akustikk/fag/tt8304/eksamen/exam_2003.pdf > > Instead of an infinite step input, most practical treatments are for a > finite "step" or rectangular pulse of some length. Maybe that means you > want a matched filter for a pulse of length t1 because you don't have more > time than t1 to detect the leading edge / "step". Should be the same thing > I think. > > Google on "unit step" "matched filter" to find a lot of stuff....Problem is, most treatments don't have the time constraint (the "t1") problem and the corresponding connection to the threshold that I have, as far as I know. -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
Reply by ●April 7, 20042004-04-07
"Randy Yates" <randy.yates@sonyericsson.com> wrote in message news:xxpad1nsrjf.fsf@usrts005.corpusers.net...> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes: > > > "Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message > > news:4073e323.577893562@news.sf.sbcglobal.net... > > > On 05 Apr 2004 13:50:48 -0400, Randy Yates > > > <randy.yates@sonyericsson.com> wrote: > > > I'll bet you can find lots of good info > > > by searching the web for "signal detection" > > > and "matched filters". > > > > > > Good Luck, > > > [-Rick-] > > > > Yes, indeed. First mention of matched filtering here isn't it? > > Good idea to search what's available. > > > > What if you first start out asking "what is the matched filter to astep?"> > > >http://klimt.iwr.uni-heidelberg.de/mip/adaptive_filters/talks/Michael_Eberle_Matched_Filters.pdf> > > > Or, as a final exam question: > > > > http://www.tele.ntnu.no/akustikk/fag/tt8304/eksamen/exam_2003.pdf > > > > Instead of an infinite step input, most practical treatments are for a > > finite "step" or rectangular pulse of some length. Maybe that means you > > want a matched filter for a pulse of length t1 because you don't havemore> > time than t1 to detect the leading edge / "step". Should be the samething> > I think. > > > > Google on "unit step" "matched filter" to find a lot of stuff.... > > Problem is, most treatments don't have the time constraint (the "t1") > problem and the corresponding connection to the threshold that I have, > as far as I know.Randy, Most of the treatments I found were dealing with detecting a rectangular pulse. I'm not sure what difference it makes between detecting a unit step within t1 seconds and detecting a pulse that's t1 seconds long. With the pulse there would be no more energy to detect after t1 seonds. With the step, you aren't allowed to process data any longer than that period of time. So, isn't that the same thing? Said another way, if you have to detect a step waveform within t1 seconds then it doesn't matter what the waveform does thereafter - does it? So, my hypothesis is that doing an optimum job of detecting a pulse that's t1 seconds long (in noise) is an equivalent problem. That is, unless you can predict the future - use a noncausal filter. But, with your time constraint of t1 seconds, that implies a real time process and not one that allows arbitrary latency such that one might define a noncausal filter in some abstract time frame. Fred
Reply by ●April 7, 20042004-04-07
Randy Yates wrote:
...
> Now the obvious thing to do to increase reliability is to average.
> However, if you average, the unit step becomes a ramp.
I've been away, hence this late response. I can see that the sum is a
ramp, but why the average should be one eludes me.
> So in order to
> detect the averaged signal within the same time constraint, t0+t1, the
> threshold of the detector must be lower. But a lower threshold
> degrades the reliability.
Why lower? As the expected value of the ramp I don't understand
increases, shouldn't the threshold increase correspondingly?
...
I'm completely at sea and the following responses haven't enlightened
me.
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by ●April 7, 20042004-04-07
Rick Lyons wrote:> On 05 Apr 2004 13:50:48 -0400, Randy Yates > <randy.yates@sonyericsson.com> wrote: > > >>This has been a question I've had for a long time. I have >>simplified it to its basic components. >> >>You have a signal x(t) composed as >> >> x(t) = u(t-t0) + n(t), >> >>where u(t) is the unit step function, t0 is unknown, and n(t) is >>stationary white Gaussian noise. You need to be able to detect the >>signal "reliably" (I'll leave the definition of that open for now) >>within t1 seconds of t0. >> >>Now the obvious thing to do to increase reliability is to average. >>However, if you average, the unit step becomes a ramp. So in order to >>detect the averaged signal within the same time constraint, t0+t1, the >>threshold of the detector must be lower. But a lower threshold >>degrades the reliability. >> >>So, is it worth it? Is the increase in reliability due to averaging >>more than the decrease in reliability due to the reduced threshold? >>-- >>Randy Yates > > > Hi Randy, > nothing much useful to you comes to > my mind right now. Except that I'm > guessing this is an "age old" problem > that's been studied by Ph.D'd for decades. > I'll bet you can find lots of good info > by searching the web for "signal detection" > and "matched filters". > > Good Luck, > [-Rick-]Before I knew what "DSP" stood for, I used linear regression to get a good answer for a question a little harder than this in one respect: we didn't know the step amplitude. The slope out of the linear regression calculation gave us that. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 7, 20042004-04-07
"Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes:> "Randy Yates" <randy.yates@sonyericsson.com> wrote in message > news:xxpad1nsrjf.fsf@usrts005.corpusers.net... > > "Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes: > > > > > "Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message > > > news:4073e323.577893562@news.sf.sbcglobal.net... > > > > On 05 Apr 2004 13:50:48 -0400, Randy Yates > > > > <randy.yates@sonyericsson.com> wrote: > > > > I'll bet you can find lots of good info > > > > by searching the web for "signal detection" > > > > and "matched filters". > > > > > > > > Good Luck, > > > > [-Rick-] > > > > > > Yes, indeed. First mention of matched filtering here isn't it? > > > Good idea to search what's available. > > > > > > What if you first start out asking "what is the matched filter to a > step?" > > > > > > > http://klimt.iwr.uni-heidelberg.de/mip/adaptive_filters/talks/Michael_Eberle_Matched_Filters.pdf > > > > > > Or, as a final exam question: > > > > > > http://www.tele.ntnu.no/akustikk/fag/tt8304/eksamen/exam_2003.pdf > > > > > > Instead of an infinite step input, most practical treatments are for a > > > finite "step" or rectangular pulse of some length. Maybe that means you > > > want a matched filter for a pulse of length t1 because you don't have > more > > > time than t1 to detect the leading edge / "step". Should be the same > thing > > > I think. > > > > > > Google on "unit step" "matched filter" to find a lot of stuff.... > > > > Problem is, most treatments don't have the time constraint (the "t1") > > problem and the corresponding connection to the threshold that I have, > > as far as I know. > > Randy, > > Most of the treatments I found were dealing with detecting a rectangular > pulse. I'm not sure what difference it makes between detecting a unit step > within t1 seconds and detecting a pulse that's t1 seconds long. With the > pulse there would be no more energy to detect after t1 seonds. With the > step, you aren't allowed to process data any longer than that period of > time. So, isn't that the same thing?Yeah, I think you're right. This is a different way of viewing the problem that I hadn't thought of. Thanks Fred.> Said another way, if you have to detect a step waveform within t1 seconds > then it doesn't matter what the waveform does thereafter - does it?No, I don't think so.> So, my hypothesis is that doing an optimum job of detecting a pulse that's > t1 seconds long (in noise) is an equivalent problem.I agree.> That is, unless you > can predict the future - use a noncausal filter. But, with your time > constraint of t1 seconds, that implies a real time process and not one that > allows arbitrary latency such that one might define a noncausal filter in > some abstract time frame.You're absolutely right - I need this algorithm to run in real-time. I'll have another look at the "standard" detection problems with this alternate viewpoint in mind. Thanks again, Fred. -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
Reply by ●April 7, 20042004-04-07
Hi Jerry, "Jerry Avins" <jya@ieee.org> wrote in message news:40747198$0$1650$61fed72c@news.rcn.com...> I've been away, hence this late response. I can see that the sum is a > ramp, but why the average should be one eludes me.If you average over the last N samples, then a step turns into a ramp of length N. Imagine an FIR filter with all its coefficients set to unity. Or correlating with an length N unit high pulse. I assume this is what is meant by averaging in this case.> > So in order to > > detect the averaged signal within the same time constraint, t0+t1, the > > threshold of the detector must be lower. But a lower threshold > > degrades the reliability.I don't understand Randy's reasoning here either! Help! cheers, Syms.
