Как сделать "усреднитель" битовой последовательноости.

[dr.ON]

Как программно сделать аналог RC-цепочки на которую поступает прямоугольный сигнал( 0 - 1)

нада вычислить грубо говоря скользящее соотношение "1" и "0".

т.е.
...11000101010... - результат 50%
...100100100100... - 33%
...110110110110... - 66%

************************************************
sum = sum * 0.999 + X * 0.001
где X = 1 или 0
( ну это правда совсем извращения( нелинейность))
хотя не так уж и звращенно. Работает красиво.
************************************************
if( X == 1)
{
sum = sum + ( ( 1 - sum) / 1000)
}
else
{
sum = sum - ( sum / 1000)
}

Ктонибудь знает как проще?

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^
P.S. Забыл сказать - это нужно для реализации на 8ми битном микроконтроллере и следовательно решения в лоб( типа выделяем массив на N бит( кольцевой), кидаем туда биты и каждый раз пересчитываем "1" и "0" и делим вконце) неприемлемы.

P.S.Пока решил по первому методу
uint16 sum;
.............
sum -= ( sum >> 8);
if( X)
{
sum += 256;
}
.............

[lukas]

а отчего пересчитывать неприемлемо? сколько есть тактов на всякое? тот уинт16 как колцевой буфер использовать. считать както так http://en.wikipedia.org/wiki/Popcount говорят, на некоторых архитектурах даже спец инструкция такая есть.

[dr.ON]

Сообщение от lukas

а отчего пересчитывать неприемлемо? сколько есть тактов на всякое?...

От того что усреднять хочется например ~512 последних бит.
Это многовато.

[MadFish]

dr.ON, а чем не подходит школьная арифметика? 512 бит=100 % 1 бит = 0.1953125 %
пришла 1 добавили 0.1953125 нолик отняли?

[dr.ON]

Сообщение от MadFish

dr.ON, а чем не подходит школьная арифметика? 512 бит=100 % 1 бит = 0.1953125 %
пришла 1 добавили 0.1953125 нолик отняли?

А какой результат будет у последовательности
10101010101..... ? А должен быть 50%

************************************************
Еще одно решение( но оно посложнее первого)
..........
if( ( cnt1 > 512) || ( cnt0 > 512))
{
cnt0 = cnt0 / 2;
cnt1 = cnt1 / 2;
}
if( X == 1)
{
cnt1++;
}
else
{
cnt0++;
}
res = cnt1 * 100 / ( cnt1 + cnt0)
.........................

[lordv]

Нет, с усреднением не пойдёт, как я и предполагал.

Смотри, если у тебя последовательность шла вначале из одних нулей - у тебя наполняется cnt0.
Допустим, единиц вообще не было.
Далее, при превышении порога в 512 cnt0 ополовинивается и становится равным 256.
Допустим, дальше пошли одни единицы - у тебя среднее будет расти 0 до 0.66, и тут у тебя cnt1 достигает порога в 512.
cnt1 ополовинивается и равен 256.
Далее опять идут одни единицы.
Среднее скачком падает до 0.33, затем растёт до 0.66, пока cnt1 опять не переполняется.
Далее опять идут единицы, и опять среднее меняется от 0.33 до 0.66.
И так далее.

Т.е. функция среднего сигнала для данной последовательности будет иметь пилообразный вид с максимумом 0.66, а в реальности она должна быть гладкой и асимпотически стремиться к единице.

Хотя, если характер распределение единиц более-менее случайный (Гауссово распределение, например), то такой алгоритм, скорее всего, подойдёт, хотя математически доказать, наверное, уже не смогу, позабыл всё :-)

[dr.ON]

Сообщение от lordv

Смотри, если у тебя последовательность шла вначале из одних нулей - у тебя наполняется cnt0.
Допустим, единиц вообще не было.
Далее, при превышении порога в 512 cnt0 ополовинивается и становится равным 256.
Допустим, дальше пошли одни единицы - у тебя среднее будет расти 0 до 0.66, и тут у тебя cnt1 достигает порога в 512.
cnt1 ополовинивается и равен 256.

+ ополовинивается cnt0
= 256 / ( 256 + 128) ~ 0, 66
Никаких скачков не будет

[][irurg]

простите что вмешиваюсь, не понял чем вариант MadFish не устроил?

Сообщение от dr.ON

у последовательности10101010101..... ?

из 512 бит получается 256 "1", = 256*0,1953%=49,996% , что и требовалось доказать. нули просто не учитываем ..

[dr.ON]

Сообщение от ][irurg

из 512 бит получается 256 "1", = 256*0,1953%=49,996% , что и требовалось доказать. нули просто не учитываем ..

После этого пошли еще 512 бит ...101010...
что получится ?
а должно 50%!

тока он предлагал так:
101010
..+0,1953%-0,1953%+0,1953%-0,1953%+0,1953%-0,1953%+0,1953%-0,1953%...
и того значение не меняется и "трусится" в произвольной точке сколь угодно долго

[][irurg]

секунду. условие было

Сообщение от dr.ON

усреднять хочется например ~512 последних бит.

т.е. количесвто бит известно заранее.
он просто ошибся в ниписании, имел ввиду как понимаю: на 1 - прибавляем %, на 0 не делаем ничего. получаем соотв % "1". если наоброт - процент "0".
если известно общее количество бит, то способ самый правильный имхо

почему кстати нельзя просто считать соотношение?

if (X==1) sum1+=1;
sum+=1;
sred1=100*sum1/sum; // percent of "1"
sred0=100-sred1; // percent of "0"

[dr.ON]

Сообщение от ][irurg

т.е. количесвто бит известно заранее.

Нет приблизительно.
Эта задача для оценки мгновенного соотношения 1 и 0 в бесконечной последовательности в окне размером примерно 512.


Я же в самом начале написал СКОЛЬЗЯЩЕЕ( и даже выделил жирным).
т.е. загнал 512 бит получил результат.
загнал еще один, опять получил и т.д.
т.е. НАПРИМЕР +-
учитываем
с 0го по 511 бит
затем с 1 по 512
2 ... 513
..........

[DeniSS1]

Проще никак. Потому что для

Сообщение от dr.ON

с 0го по 511 бит
затем с 1 по 512
2 ... 513
..........

тебе нужно знать последовательность битов.
Поясню про

Сообщение от dr.ON

sum = sum * 0.999 + X * 0.001
где X = 1 или 0

Допустим, есть последовательность из 1000 битов (считать проще), идущих чередованием 0101... Поступает 1. Мы имеем промежуток 10101...101. В нём 502 единицы и 498 нулей. Получается 50.2% единиц. Считаем по формуле. sum = 50 * 0.999 + 1 * 0.001 = 49.95 + 0.001 = 49.951. На первый взгляд разница не существенна, но если дальше если каждый второй бит будет единицей, то получится лажа

Единственный выход, который вижу: хранить небольшое кол-во битов (например, 64 или 128) и считать тоже самое скользящее соотношение для них.

[dr.ON]

Сообщение от DeniSS1

имеем промежуток 10101...101. В нём 502 единицы и 498 нулей.....

Мне кажется 501/499 ( но это ерунда)

Сообщение от DeniSS1

Получается 50.2% единиц. Считаем по формуле. sum = 50 * 0.999 + 1 * 0.001 = 49.95 + 0.001 = 49.951. На первый взгляд разница не существенна, но если дальше если каждый второй бит будет единицей, то получится лажа

Дальше плохо понимаю.
Вот график и и сама "модель" в экселе ( 100% = 65535)


P.S. Битовая последовательность шумоподобная( 1010.. и т.д. это для проверки алгоритмов)
Хранить требуемое колво бит нет возможности и не нужно.