Kitz ADSL Broadband Information
adsl spacer  
Support this site
Home Broadband ISPs Tech Routers Wiki Forum
 
     
   Compare ISP   Rate your ISP
   Glossary   Glossary
 
Please login or register.

Login with username, password and session length
Advanced search  

News:

Pages: [1] 2 3 ... 8

Author Topic: Maths - hollow curve phenomenon detector - algorithm design  (Read 8028 times)

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Maths - hollow curve phenomenon detector - algorithm design
« on: January 19, 2022, 01:24:46 AM »

Referring to https://forum.kitz.co.uk/index.php/topic,24614.msg414054.html, here’s a pretty ugly picture of the DSL blight which I named "the hollow curve phenomenon" for want of a better term. This has affected my lines many times over the last two years.



In reality I would be working on y = bitloading values of 0…15, not a curvy SNR graph.

Generality: there may well be non-zero values below x<32, unlike in the above example. In either case any values below x<32 are upstream values and are data to be ignored.

What I want to do is write some pseudo-code to start with, or C, to detect the presence of this illness by inspecting some graph and determining whether it looks like the above or looks normal, normal being with a single hump, but ignoring any sharp dips due to DSL weirdness such as a pilot tone or narrow interference. I’m hoping you all can contribute some all mathematical ideas that will make it highly robust and very fast. The finished code will be written in code for the iOS Shortcuts engine, which is painfully slow these days in iPadOS 15, so minimising the number of lines of code is the way to go.
 
There are various ways of detecting the double maximum (ill; hollow curve) versus single maximum (healthy) but these only work properly if you filter out the aforementioned sharp dips. I wonder if such filtering might be the way to go before anything else is done. At least after that life is simple. The other method is to try to design a single algorithm that is immune to such dips while detecting the ‘genuine’ double maxima.

The simplest (‘cheapo’) test I can think of is simply three ycooord tests, at x==40, x==60, x==85. I’m not sure that that is general enough. In the aforementioned example there’s a small sharp dip worryingly close to x = 85. Something like
        hollow = y[60] < y[40] && y[60] < y[85];

The mathematical ‘heavyweight’ method I can think of would be:
  • moving averaging filter to remove the sharp dips, affects the entire data though, which is a worry
  • test for local maxima by calculating first derivative at x==40, 60, 85 and
  • checking that first derivative goes from negative to positive in that region errm around x==60 [vague].
The problem with the latter ‘heavyweight’ method is where and how to apply the sign change test. Also the whole thing is too much code, and is overkill unless its potential robustness turns out to be needed because the first, cheap method proves too fragile.

One kind of sharp dip, which is extremely severe, is the pilot tone, which dips all the way down from y==whatever, 11, maybe, down to y==bitloading of 2, x==unpredictable. The width is extremely narrow. This can really mess up the simple test and can score a false positive if the test is e.g. y[60] and the pilot tone is also at say x==60 even though there is otherwise only a single smooth hump overall, a single local maximum.

Comments, suggestions? Ways to ensure method 1 (‘cheapo’) can be made reliable?

The y data is presented as a list of ASCII decimal numbers separated by newlines. I also need to find a very cheap way of converting all those decimal strings into numbers in an array, as otherwise I can’t think of any way of finding line 40, 60, 85 say. I’m not sure I can afford a loop with 80 iterations or worse. I could do with some help with this problem, which despite sounding simple could be a showstopper given the limitations of the iOS Shortcuts engine.
« Last Edit: January 21, 2022, 08:49:49 AM by Weaver »
Logged

burakkucat

  • Respected
  • Senior Kitizen
  • *
  • Posts: 38300
  • Over the Rainbow Bridge
    • The ELRepo Project
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #1 on: January 19, 2022, 03:41:13 PM »

My first (and currently only) suggestion is to restrict the domain of the X-axis values to be considered. I would use:

100 > X > 32
Logged
:cat:  100% Linux and, previously, Unix. Co-founder of the ELRepo Project.

Please consider making a donation to support the running of this site.

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #2 on: January 19, 2022, 09:21:23 PM »

Agreed. In some other data I immediately found a dip all the way down to y=2 due to pilot tone (which I don’t fully understand - Kitz where are you ? ;) ) at around tone 60 iirc. That kind of thing is going to be a nuisance to deal with.
« Last Edit: January 21, 2022, 09:44:14 PM by Weaver »
Logged

burakkucat

  • Respected
  • Senior Kitizen
  • *
  • Posts: 38300
  • Over the Rainbow Bridge
    • The ELRepo Project
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #3 on: January 19, 2022, 10:10:14 PM »

As 100 - 32 = 68, my next suggestion is to perform an initial pass looking at blocks of 4. That should minimise the distraction caused by a pilot tone, etc.

(Why blocks of 4? No real reason other than that 4 x 17 = 68 and 4 > 1.)

I feel the urge to type "first differential".
Logged
:cat:  100% Linux and, previously, Unix. Co-founder of the ELRepo Project.

Please consider making a donation to support the running of this site.

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #4 on: January 19, 2022, 10:51:41 PM »

And average the blocks? or…
Logged

burakkucat

  • Respected
  • Senior Kitizen
  • *
  • Posts: 38300
  • Over the Rainbow Bridge
    • The ELRepo Project
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #5 on: January 19, 2022, 11:21:32 PM »

Just differentiate the arithmetic mean and find the turning point(s) of the curve. If you have a local maximum, followed by a local minimum, followed by a local maximum then the hollow curve phenomenon has struck again.

Hmm . . . I think you will need to look at the second differential. (My memory of A-level pure mathematics, from 50+ years ago, has faded somewhat.)
Logged
:cat:  100% Linux and, previously, Unix. Co-founder of the ELRepo Project.

Please consider making a donation to support the running of this site.

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #6 on: January 20, 2022, 04:40:30 AM »

I understand the calculus rationale. However the pilot tone thing has a huge spike in both first and second derivatives.

l would rather not do differentiation; recte finite differences here, since the bits-per-bin data are discrete integer-valued (y). The reason is because having a loop with lots of subtractions in it will be slow, as Shortcuts is incredibly slow.

What were you saying before about four quarters? My most urgent need is to get rid of all spikes, pilot tone being the main one. Wobble of y +/- 1 is also a nuisance, some being mere quantisation noise.
Logged

burakkucat

  • Respected
  • Senior Kitizen
  • *
  • Posts: 38300
  • Over the Rainbow Bridge
    • The ELRepo Project
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #7 on: January 20, 2022, 03:16:33 PM »

I'm not too sure what I was thinking about, late yesterday.  :-[

At the moment, I can't see a clear forward path to a boolean answer to a query asking if a "hollow curve" is present.

Random thought. Suppose that the bit loading per sub-carrier index is "harvested", once, at the same time each 24 hour period. Now subtract that of dayn from that of dayn+1 to give the delta on dayn+1. What would that delta show when the "hollow curve phenomenon" first appears?
Logged
:cat:  100% Linux and, previously, Unix. Co-founder of the ELRepo Project.

Please consider making a donation to support the running of this site.

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #8 on: January 20, 2022, 08:55:57 PM »

Yes, it would, but that won’t fit in the spec for this as I was going to add this in as an additional immediate health check amongst those already checked in the application program that I write about some weeks ago, an iOS Shortcuts app that checks all the modems and delivers a very succinct report - good or bad and if bad it gives the details. That program does not run continuously so that rules out your idea, because iOS doesn’t allow Shortcuts programs to run continuously - they’re UI-modal, locking up the UI, with no multitasking and no thought given to what should happen if you run two Shortcuts programs - in other words a complete design dog’s breakfast. Perhaps tolerable on an iPhone for very short excution-time programs, but not suitable for an iPad with a big screen and several very slow Shortcuts programs wanting to run side by side. But apart from being painfully slow in iOS 15 the result works really well and does what it’s supposed to.

I was thinking about a crude spike detector that looks at x==60 for a dip down to y=2 (or maybe 3,4 for a bit of insurance) and then if it sees one at x==60 it walks sideways in increasing x+=2 to get away from the spike. Then y[x==60 or 62] now is compared against y[40] and y[85] as mentioned in my first post. Something like
        hollow = y[x==60 or 62] < y[40] && y[x==60 or 62] < y[85];

The benefit of this is that it has no loops in it, given the painful slowness of Shortcuts iOS15

« Last Edit: January 20, 2022, 09:04:36 PM by Weaver »
Logged

burakkucat

  • Respected
  • Senior Kitizen
  • *
  • Posts: 38300
  • Over the Rainbow Bridge
    • The ELRepo Project
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #9 on: January 20, 2022, 10:42:06 PM »

I was thinking about a crude spike detector that looks at x==60 for a dip down to y=2 (or maybe 3,4 for a bit of insurance) and then if it sees one at x==60 it walks sideways in increasing x+=2 to get away from the spike. Then y[x==60 or 62] now is compared against y[40] and y[85] as mentioned in my first post. Something like

        hollow = y[x==60 or 62] < y[40] && y[x==60 or 62] < y[85];

I am not that certain . . . but it certainly is worth testing.
Logged
:cat:  100% Linux and, previously, Unix. Co-founder of the ELRepo Project.

Please consider making a donation to support the running of this site.

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #10 on: January 21, 2022, 12:24:29 AM »

There’s a bug in that expression. Because of quantisation noise, the value of y can go up/down by 1 in a semi-random fashion. For this reason I’ve adapted the expression to give:
        hollow = y[x==60 or 62] < y[40] - 1 && y[x==60 or 62] < y[85] - 1;

This is I hope correct? The y values can wobble up and down by 1 so y1 < y2 should really read y1 < y2 -1 - that’s my reasoning. Please someone sanity check me on this.

I’ve written the Shortcuts code for this. It has absolutely zero loops in the Shortcuts code[!], letting the engine runtime do the work at low level that I would otherwise have to write in lines of Shortcuts source code. This means that it’s not slow. It gets the bitloading data file from each modem as http://modem:8000/data/Bits/ and uses regexes like ^\X*\n[ \t]*40[ \t]+(\d+)\X*$ to get y[40] for example, searching the whole of the text for a line like
    40  11

which means tone=40 bitloading=11 bits. Same for tone 60 or thereabouts and for tone 85.

I need to look back at some of the old bitloading hollow curve illness reports (not the SNR reports).

I need to test what happens if there are some small dips due to interference, downwards-going just a few bits deep and say 2-3 tones wide. My worry is that such could be mistaken for hollow curve. A more sophisticated test, which is capable of moving the y[x60] point sideways more, that would presumably do the trick but the details escape me just now.



A question: when writing posts in the forums, it does of course go crackers when I try to write certain things inside [ ]. How do I work around that?



A question for all ADSL experts : is the bitloading[pilot_tone] == 2 thing something that is always exactly true? I didn’t know whether the value can be zero or > 2 or what. Because I didn’t know, for now I made the pilot tone test "(bitloading y < 4)".
« Last Edit: January 21, 2022, 02:23:09 AM by Weaver »
Logged

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #11 on: January 21, 2022, 01:18:26 AM »

Here’s an example. Very very serious disease. What I also want is very mild early onset so the algorithm can detect the onset really early and warn in good time. The very serious disease thing would be detected by the min-sync rate test in any case.





And here are the latest perfectly healthy pictures:





« Last Edit: January 21, 2022, 01:40:47 AM by Weaver »
Logged

Weaver

  • Senior Kitizen
  • ******
  • Posts: 11459
  • Retd s/w dev; A&A; 4x7km ADSL2 lines; Firebrick
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #12 on: January 21, 2022, 02:19:24 AM »

A further thought. Using any kind of averaging, smoothing type filter would surely make the depth of the pilot tone dip much higher, would it not? Thus increasing the danger that a pilot tone in the wrong place could be mistaken for a hollow curve y-min if the smoothing filter was applied first, before all other inspection, and therefore affecting all data pilot tone dip included.

Despite this earlier post of mine which I had completely forgotten, I still don’t understand the data in pilot tone thing.



ALGORITHM II

Another idea about the central comparison in the algorithm. Take the two points ( 40, y40-1 ), ( 85, y85-1 ). Then consider the data point ( 60 or 62, y6x) where y6x is the corresponding data y value. Now draw a straight line between the first two points. Then where it reaches x=60 or 62, solve for ymid = y; that is the y value of the straight line at the middle point x== x60 = (60 or 62). Now we have
    hollow_curve = ( y6x < ymid );  ymid = y40 - 1 + (y85 - y40)*(x60 - 40.0)/(85.0 - 40.0) — is that correct ?

I’m not sure if this is an improvement or not. It certainly handles one potential problem case, which is where the y85 value is really low, because the whole thing is very peaky/pointy, not like a nice rounded / domed loaf kind of shape. If the y85 value is really low then the second of the tests in the && in the first algorithm will be in danger and the expression will fail to spot very early mild hollow curve onset.
« Last Edit: February 11, 2022, 04:30:20 AM by Weaver »
Logged

jelv

  • Helpful
  • Kitizen
  • *
  • Posts: 2054
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #13 on: January 21, 2022, 08:16:38 AM »

A question: when writing posts in the forums, it does of course go crackers when I try to write certain things inside [ ]. How do I work around that?

Enclose the text in [nobbc]...[/nobbc] tags (which I had to do in this post so they would show - start a quote of this post to see how).
« Last Edit: January 21, 2022, 08:19:40 AM by jelv »
Logged
Broadband and Line rental: Zen Unlimited Fibre 2, Mobile: Vodaphone
Router: Fritz!Box 7530

burakkucat

  • Respected
  • Senior Kitizen
  • *
  • Posts: 38300
  • Over the Rainbow Bridge
    • The ELRepo Project
Re: Maths - hollow curve phenomenon detector - algorithm design
« Reply #14 on: January 21, 2022, 06:46:48 PM »

Here’s an example. Very very serious disease. What I also want is very mild early onset so the algorithm can detect the onset really early and warn in good time. The very serious disease thing would be detected by the min-sync rate test in any case.

<snip>



And here are the latest perfectly healthy pictures:

<snip>


If it would not be too inconvenient, would you please send me (via e-mail) the "xdslctl info --Bits" data for those four plots? I would like to generate those plots with my usual utility, so I can see how different the plots look when compared with the "Easy Stats (tm)" output that you have shown, above.
Logged
:cat:  100% Linux and, previously, Unix. Co-founder of the ELRepo Project.

Please consider making a donation to support the running of this site.
Pages: [1] 2 3 ... 8