Andrew Que Sites list Photos
Projects Contact
Main

July 01, 2020

Bounded Variable Sigmoid Mapping Function for Curving Random Numbers

So the other day I wrote about a curving function for random numbers that can weight them more toward high or low values. What if we want numbers more concentrated at a center? We can use a Box-Muller transform and get numbers with Gaussian distribution. The problem with that is the numbers are unbounded. That is, there is no limit to how much derivation from the center there can be. We want a fixed upper and lower limit. I've tried doing this in the past with a ranged Box-Muller transform but it isn't quite as configurable as I would like. Then I ran across this post on Stack Exchange. It is a variable Sigmoid function bound between 0 and 1. Here is an implementation:

Coefficient: unknown.
Standard deviation: unknown.

This is a fantastic function. For coefficient values less than 1 and greater than zero, the function exhibits Gausian distribution. This produces numbers around a center point (0.5) that can deviate to some maximum on either side (0 or 1) with control over how likely deviation (something akin to standard deviation). However, it is more versatile than that. For coefficients greater than 1, the function produces reverse Gaussian distribution, pushing the results to the sides and making the middle less likely. There are applications for both. However, let's first look at the transform function. The Stack Exchange post gives it as:

y = 1 - 1 1 + ( 1 x - 1 ) - c

But I like this form better as it is easier to read:

y = 1 1 + ( x - 1 - 1 ) c

It is a bounded function but is actually undefined at the end-points. I could see why x=0 didn't work (divide-by-zero), but it wasn't initially obvious why x=1 didn't work. This identity makes it more obvious:

x c = e c ln ( x )

So if x=1, the value inside the parenthesis becomes 0, and you cannot take the natural log of 0 as it is undefined at 0.

Looking at the function it is easy to deduce that at the end point y=0 when x=0 and y=1 when x=1, but we can prove it mathematically:

lim x 0 + 1 1 + ( x - 1 - 1 ) c = 0 lim x 1 - 1 1 + ( x - 1 - 1 ) c = 1

So a complete definition would be:

y = { 0 x = 0 1 1 + ( x - 1 - 1 ) c 0 < x < 1 1 x = 1 { x : 0 = x = 1 } { c : c > 0 } { y : 0 = x = 1 }

Now there must be a relation between the coefficient in this equation and the standard deviation. Sadly, I have was unable to find it before publishing this article.

November 16, 2017

Impulse Noise Filtering - Slew Limit Filter

In the past few articles in this series I have demonstrated using a median filter to mitigate impulse noise. The problem with a median filter is that even using a small window size and taking advantage of the speed of a mostly sorted list entering an insertion sort, the filter is still significantly slower than a windowed average. There is another option. It does not filter as nicely as a median filter but does help to dampen impulse noise.

The slew rate is a measure of how quickly voltage changes over time. A windowed average acts as limiter on slew rate but usually not enough to attenuate impulse noise. However one can directly limit the slew rate of a signal. The equation is quite simple:

For each sample of the input (an) the filter output (fn) has its change (Δn) limited to the last to some maximum (smax). If the magnitude of change is less than the maximum, the filter output is the same as the input. If the magnitude exceeds the change the filtered output is modified by the maximum change but no further.

Following the examples of previous article on this subject, here is an example of the filter output:

There is some distortion on the signal caused by the impulse noise but the filtered output is fairly effective at eliminating the large spikes. When used in combination with a first-order low-pass filter the input signal is fairly clear.

The reason this kind of filter is attractive is because of how simple it is to implement.

//-----------------------------------------------------------------------------
// Uses:
//   In-place filter of input buffer.
// Input:
//   data - Data to filtered..
//   dataSize - Number of data points.
//   limit - Maximum change allowed.
// Output:
//   Filtered output is returned in 'data'.
// Author:
//   Andrew Que <https://www.DrQue.net/>
//-----------------------------------------------------------------------------
static inline void slewLimitFilter
(
  int * data,
  size_t dataSize,
  int limit
)
{
  for ( size_t index = 1; index < dataSize; index += 1 )
  {
    int delta = data[ index ] - data[ index - 1 ];
    if ( delta > limit )
      data[ index ] = data[ index - 1 ] + limit;
    else
    if ( delta < -limit )
      data[ index ] = data[ index - 1 ] - limit;
  }
}

Just as with any filter, artifacts are introduced by the slew limit filter.

This sine wave has become a triangle wave because the slew limit is too low. This shape is the result of the filter attenuating the actual data signal. This is an other demonstration.

Here is a clean signal, but because the slew limit is too low the filter cannot keep up with the rate of change of the true signal.

The other problem with the slew limit filter is that it is not very strong.

Here the impulse noise has been doubled and the filter has produced a very messy result. So the filter is clearly not a replacement for a median filter. If you can afford the processing power, use the median filter. If you cannot, the slew limit filter may be a possibility. It depends on what the impulse noise looks like, and how much signal distortion can be tolerated.

October 11, 2017

Examining Old Algorithms

Back in the late 1990s I was working on a game inspired by the old BBS game Trade Wars 2002. I was looking to have a more advanced value system for traded goods. The other day I was interested in the algorithm I had come up with because I knew it was rather strange. So I decided to find the code and graph the value function I had created. Here is a graph of the function I created.

The purpose of the algorithm was to produce a monetary value based on several attributes that summed to an overall quality rank. Think of this like a gemstone where 100% would be completely flawless and 0% complete flawed. One of the attribute flags could change the value by a scale factor.

When I wrote this algorithm I didn’t know much about the curving numbers. I setup a kind of liner piece-wise function. Six of the steps are fairly obvious: 30, 50, 80, 92 and 98. Probably less intentional were the last two steps. The first happens at 19/32768, and the second 448/32768. My goal was likely to make the slope toward zero more gradual near the end, but since I didn’t understand graphing a function the actual results were not at all what was expected.

The graph is shown on a logarithmic scale so the nuances like the strange end are clearly visible. All the values are actually linear and the curves of (like the one from 2% to 30%) is just a result of the logarithmic scale.

If I were to write this algorithm today I probably would use a second degree polynomial or an exponential function. Something like:

or

By varying the coefficients a, b, and c I would have a continuous function that curved. The exponential function

will produce the following graph which is fairly close to what the game would have needed.

Like most of my programming projects the game never amounted to much more than a concept. I spent more time fighting with the 640 KiB barrier at the time than doing much development work. It is interesting to look at how I approached math problems when I didn’t know any formal math outside of arithmetic.

January 12, 2017

Orthogonal Function with Dot Product Test

Playing some more with orthogonal functions to try and get a better handle of why a Fourier transform works. I decided I would try some simple functions I can work with easily to test orthogonality. The definition for as orthogonal function is one such that:

So I decided to use two very simple functions over the interval b = -a.

Orthogonal test:

Remember that ab even power b is the same for a and -a. Thus:

So my two functions are orthogonal. Now for something crazy.

I want to extract the coefficient for b. So I can to a projection for x2.

Notice how c does not show up in this result.

The same for x3.

Here, b does not show up in the result.

I verified this using a discrete check in a speadsheet. While I expected it would work, watching it actually do so was interesting.