[bognev 0]

я прделожил алгоритм сортировки - оптимальный или нет решает ТС...

Конечно в таком случае возможно нужно будет подумать над схемой ограничения разрядности 16 разрядов до 12 разрядов, т.е. чтобы было до 4096 отсчетов...

затем конечно нужно будет думать над потоковой схемой нахождения среденего/медианы...

 

Добрый день.

 

Диапазон значений можно сжать логарифмом к 0 - 255. В адрес памяти предполагается записывать значение счетчика таких значений? Получается гистограмма, как в приведенной мной статье. Но в этом случае для худшего случая придется пройтись по всем 256 адресам для увеличения/ уменьшения значения счетчика, а это потребует 256 тактов для каждого значения. Или вы другое имели ввиду?

 

[Maverick_ 15]

Добрый день.

 

Диапазон значений можно сжать логарифмом к 0 - 255. В адрес памяти предполагается записывать значение счетчика таких значений? Получается гистограмма, как в приведенной мной статье. Но в этом случае для худшего случая придется пройтись по всем 256 адресам для увеличения/ уменьшения значения счетчика, а это потребует 256 тактов для каждого значения. Или вы другое имели ввиду?

не совсем

Данные превращаем в адрес для памяти (поясню например приходят данные 23, 69, 86 - Вы пишете эти значения в память по адресам 23, 69, 86).

[bognev 0]

не совсем

Тогда если приходит например 64, то по адресу 64 будет лежать 64. прошло много времени, вся память инициализирована значениями от 0 до 4096 например, какое-то масштабирование диапазона данных на диапазон значений адреса? До конца не понимаю как это будет работать?

[Maverick_ 15]

Тогда если приходит например 64, то по адресу 64 будет лежать 64. прошло много времени, вся память инициализирована значениями от 0 до 4096 например, какое-то масштабирование диапазона данных на диапазон значений адреса? До конца не понимаю как это будет работать?

прочитайте мой предыдущий пост пожалуйста, я его дополнил.

[FatRobot 4]

В итоге в ячейках памяти лежат значения по порядку men(i)=i. Как медиану вычислять?

 

не совсем

 

[Maverick_ 15]

В итоге в ячейках памяти лежат значения по порядку men(i)=i. Как медиану вычислять?

прочитайте мой предыдущий пост пожалуйста, я его дополнил.

[bognev 0]

Возможно нужно будет подумать над схемой ограничения разрядности 16 разрядов до 12 разрядов, т.е. чтобы было до 4096 отсчетов (чтобы ограничить размеры памяти)...

Медианное значение будет находиться всегда по адресу MAX_ADDR(памяти)/2, в случае если данные заполняют полностью всю память равномерно.

Если заполняется какой-то дипазон памяти, то должна быть схема которая будет отслеживать диапазон (для этого потребуется нахождение максимального и минимального значения среди N данных - привел ниже пример описания), тогда медианное значение будет находиться по адресу (MAX_DATA - MIN_DATA)/2

 

Поиск максимального и минимального элемента в потоке (массиве)

Разрядность и количество  элементов в массиве   задается в GENERIC

Описание портов:
clk − вход тактовой частоты;
Reset –  вход асинхронного сброса;
En – вход разрешения работы;
Data – N - разрядный вход;
Max_ Count – M-разрядный выход индекса в потоке (массиве) максимального найденного элемента;
Min_Count – M-разрядный выход индекса в потоке (массиве) минимального найденного элемента.
Max_Out – N-разрядный выход максимального найденного элемента;
Min_Out – N-разрядный выход минимального найденного элемента.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;

ENTITY Max_Min IS
GENERIC (vwidth : integer := 11;
count : integer := 7);
PORT(
Reset, Clk, En : IN STD_LOGIC;
Data : IN std_logic_vector (vwidth  downto 0);
Max_Count,Min_Count  : out std_logic_vector (count  downto 0);
Max_Out,Min_Out  : out std_logic_vector (vwidth  downto 0) );
END Max_Min;

ARCHITECTURE Behavioral OF Max_Min IS

signal cnt: std_logic_vector (7  downto 0):= "00000001";

BEGIN

process (Reset,Clk,En,cnt)
variable tmp_max: std_logic_vector (vwidth  downto 0):= (others => '0');
variable count_max: std_logic_vector (count  downto 0):= (others => '0');
begin
if (Reset = '0') then
tmp_max := (others => '0');
count_max := (others => '0');
elsif (Clk'event and Clk = '1') then
if (en = '1') then
if Data > tmp_max then
tmp_max := Data;
count_max := cnt;
end if; end if; end if;
Max_Out <= tmp_max;
Max_Count <= count_max;
end process; 

process (Reset,Clk,En,cnt)
variable tmp_min: std_logic_vector (vwidth  downto 0):= (others => '0');
variable count_min: std_logic_vector (count  downto 0):= (others => '0');
begin
if (Reset = '0') then
tmp_min := (others => '1');
count_min := (others => '0');
elsif (Clk'event and Clk = '1') then
if (en = '1') then
if Data < tmp_min then
tmp_min := Data;
count_min := cnt;
end if; end if; end if;
Min_Out <= tmp_min;
Min_Count <= count_min;
end process;

process (Clk, En, cnt, Reset)
begin
if (Reset = '0') then
cnt <= "00000001";
elsif (Clk'event and clk = '1') then
if (En = '1') then
cnt <= cnt + "00000001";
end if;
end if;
end process;

end behavioral;

 

Если всегда будет приходить 1 2 3 4 6 7 8 9 10, то мин = 1, макс = 10, то среднее будет в 5 ячейке, а в нем всегда 0 будет.

 

[Maverick_ 15]

Если всегда будет приходить 1 2 3 4 6 7 8 9 10, то мин = 1, макс = 10, то среднее будет в 5 ячейке, а в нем всегда 0 будет.

решить этот момент можно:

у Вас память должна быть изначально инициализрована каким-то значением (т.е. по всем адресам записано одно и тоже число которого в потоке нет- расплата увеличение памяти на 1 бит), если Вы считали инициализированное значение, то тогда производите повторное чтение

например

по адресу ((MAX_DATA - MIN_DATA)/2)-1

или

по адресу ((MAX_DATA - MIN_DATA)/2)+1

 

если опять считали инициализированное значение, то можно увеличить например шаг смещения с 1 до N ... тогда

например N =5

по адресу ((MAX_DATA - MIN_DATA)/2)-5

или

по адресу ((MAX_DATA - MIN_DATA)/2)+5

 

PS согласен, предложенное решение не идиально, но как идея думаю может подойти для дальнейших размышлений...

[RobFPGA 35]

Приветствую!

 

я прделожил алгоритм сортировки - оптимальный или нет решает ТС...

Увы это не сортировка :(

 

А можно привести пример или более детально описать алгоритм? А то как то плохо пока представляю для себя реализацию.

Все просто - в буфере на N точек хранится пара val,idx причем val отсортирована по возрастанию, а idx уникальный 0-N-1.

читаем буфер последовательно, сравниваем val с новым входным отсчетом а idx c N-1. соответственно находим позицию где нужно вставить новое значение в выходной поток (первое событие где val>=Val_in) а где удалить старый (idx==N-1). А так как в ЛЮБОМ случае мы один отсчет удалим а один вставим то выходной поток будет равен входному то есть N точек. Логика вставки и удаление реализуется задержкой читаемых данных на такт и мультиплексором на 3 входа выбирающим нужную задержку или входные данные ну и простенький FSM на 4 состояния. Все idx в выходном потоке увеличивается на +1 ну а у нового вставленного отсчета естественно idx=0.

Если выходной поток записывать сразу в буфер то получится на один отсчет N+pipeline_delay тактов.

Но ведь для одного канала можно выходной поток рассматривать как поток чтения для следующего входного отсчета ;)

Тогда получится read_буфер -> K модулей вставки/удаления -> write_буфер. соответственно на отсчет N/K+pipeline_delay

В пределе - получим вариант Fat Robot - 2*N регистров для val и idx, N 3x мультиплексоров, 2*N компараторов и сортировка за такт (ну почти ;) )

 

Ну и многоканальный вариант получается соответствующим индексированием буфера.

 

Успехов! Rob.

[Maverick_ 15]

Приветствую!

 

 

Увы это не сортировка :(

 

 

Все просто - в буфере на N точек хранится пара val,idx причем val отсортирована по возрастанию, а idx уникальный 0-N-1.

читаем буфер последовательно, сравниваем val с новым входным отсчетом а idx c N-1. соответственно находим позицию где нужно вставить новое значение в выходной поток (первое событие где val>=Val_in) а где удалить старый (idx==N-1). А так как в ЛЮБОМ случае мы один отсчет удалим а один вставим то выходной поток будет равен входному то есть N точек. Логика вставки и удаление реализуется задержкой читаемых данных на такт и мультиплексором на 3 входа выбирающим нужную задержку или входные данные ну и простенький FSM на 4 состояния. Все idx в выходном потоке увеличивается на +1 ну а у нового вставленного отсчета естественно idx=0.

Если выходной поток записывать сразу в буфер то получится на один отсчет N+pipeline_delay тактов.

Но ведь для одного канала можно выходной поток рассматривать как поток чтения для следующего входного отсчета ;)

Тогда получится read_буфер -> K модулей вставки/удаления -> write_буфер. соответственно на отсчет N/K+pipeline_delay

В пределе - получим вариант Fat Robot - 2*N регистров для val и idx, N 3x мультиплексоров, 2*N компараторов и сортировка за такт (ну почти ;) )

 

Ну и многоканальный вариант получается соответствующим индексированием буфера.

 

Успехов! Rob.

возможно у меня не сортировка (спорить не буду), но в Вашем случае для 4096 отсчетов слишком расточительно выходит по логике, даже для 256 отсчетов:

 

Кто нибудь сталкивался с эффективным сортировщиком массива отсчетов по возрастанию, например, на 256 отсчетов в реальном времени на плис с оптимальными параметрами по занимаемым ресурсам? Задача стоит в выкусывании несинхронной помехи в принятом сигнале, наиболее эффективным алгоритмом является ранговая обработка. Каждые 40 тактов поступает новый 16 разрядный отсчет, всего предполагается 4096 отсчетов и по ним надо в реальном времени строить ранговый порог. Как с этим проще справиться? Может быть сталкивался кто нибудь?

 

Заранее благодарю за помощь.

 

PS Для малого кол-ва отсчетов Ваш алгоритм можно использовать, например для кол-ва отсчетов 8-32 (сугобо мое мнение). Я бы его и предложил изначально тогда...

[FatRobot 4]

вариант Fat Robot

 

Мне кажется, что после анализа доступных технических решений можно было бы слегка надавить на заказчиков, чтобы они подвинулись в точности оценки медианы, т.к. медиана из 256 значений - это никуда не годная печаль.

 

Ну а дальше смотреть, какие есть варианты приближенного вычисления. Среди них, наверное

- анализ гистограммы. я бы предпочел этот способ. он понятный, простой в реализации, и хорошо настраивается

- усреднение нескольких медиан по короткой выборке

- анализ в частотной области

и т.п.

 

В итоге все отразится в некотором проигрыше в помехоустойчивости/достоверности. Наверняка, могут себе позволить.

[ViKo 1]

Мое предложение.

Имеем 256 х 16 память с произвольным доступом и сдвигом вперед, в которую можно записать данные по любому индексу, а следующие за ним - сдвинуть. Так получаем функцию вставки.

Куда вставить, ищем половинным делением. Причем, можно сравнивать не одним компаратором, а параллельно несколькими. Например, сначала сравниваем входное слово с ячейками по индексам 1/4, 1/2, 3/4 от длины буфера (в данном случае 64, 128, 192). Находим 2 старших бита нашего индекса, куда будем вставлять. Они же определяют область, которую выбираем для дальнейшего сравнения. Допустим, число малое, попали в первую четверть памяти. Дальше сравниваем с ячейками по индексам 1/16, 1/8, 3/16. Находим еще 2 бита. Дальше с 1/64, 1/32, 3/64. Наконец, с 1/265, 1/128, 3/256. За 4 этапа нашли нужный индекс, куда вставлять.

И так, пока не примем все 256 слов. На выход выдаем значение по среднему индексу, понятно. Для следующих 256 слов обнулять память не нужно, сама перепишется при сортировке.

 

P.S. Но, конечно, я бы никогда не боролся с импульсными помехами таким образом. Это, получается, нашли козла отпущения, или самого сговорчивого...

[bognev 0]

Приветствую!

 

 

Увы это не сортировка :(

 

 

Все просто - в буфере на N точек хранится пара val,idx причем val отсортирована по возрастанию, а idx уникальный 0-N-1.

читаем буфер последовательно, сравниваем val с новым входным отсчетом а idx c N-1. соответственно находим позицию где нужно вставить новое значение в выходной поток (первое событие где val>=Val_in) а где удалить старый (idx==N-1). А так как в ЛЮБОМ случае мы один отсчет удалим а один вставим то выходной поток будет равен входному то есть N точек. Логика вставки и удаление реализуется задержкой читаемых данных на такт и мультиплексором на 3 входа выбирающим нужную задержку или входные данные ну и простенький FSM на 4 состояния. Все idx в выходном потоке увеличивается на +1 ну а у нового вставленного отсчета естественно idx=0.

Если выходной поток записывать сразу в буфер то получится на один отсчет N+pipeline_delay тактов.

Но ведь для одного канала можно выходной поток рассматривать как поток чтения для следующего входного отсчета ;)

Тогда получится read_буфер -> K модулей вставки/удаления -> write_буфер. соответственно на отсчет N/K+pipeline_delay

В пределе - получим вариант Fat Robot - 2*N регистров для val и idx, N 3x мультиплексоров, 2*N компараторов и сортировка за такт (ну почти ;) )

 

Ну и многоканальный вариант получается соответствующим индексированием буфера.

 

Успехов! Rob.

 

благодарю за детальное описание) Я сначала почему то думал, что исходный массив на 256 остчетов можно сортировать отдельными модулями, а потом каким то образом объединять, но теперь все стало предельно понятно.

 

Хочу узнать ваше мнение по поводу алгоритма в статье: http://www.ntu.edu.sg/home/sfahmy/files/papers/fpl2005.pdf

Большим его плюсом является независимость занимаемых ресурсов от окна, только количество bram для задержки потока данных на половину длины окна, гистограммный метод. По мне так он больше подходит для такого окна.

 

 

P.S. Но, конечно, я бы никогда не боролся с импульсными помехами таким образом. Это, получается, нашли козла отпущения, или самого сговорчивого...

 

 

Дело в том, что один алгоритм подавления импульсных несинхронных помех есть(межпериодный) и он отлично работает, но только с несинхронными помехами. Но были ситуации, когда шла мощная синхронная помеха и бороться с ней можно было только отстройкой по частоте. Или таким методом, но минусом его является, что помеха длиной в половину окна + 1 отсчет уже не сможет быть задавлена и пришлось искать методы для сортировки на 256 отсчетов. В принципе это не является строгой обязаловкой, я могу отказаться от этого алгоритма , но пока решил, что стоит рассмотреть все возможные варианты реализации такого алгоритма.

Изменено 21 мая, 2015 пользователем bognev

[RobFPGA 35]

Приветствую!

 

возможно у меня не сортировка (спорить не буду), но в Вашем случае для 4096 отсчетов слишком расточительно выходит по логике, даже для 256 отсчетов:

PS Для малого кол-во отсчетов Ваш алгоритм можно использовать, например для кол-во отсчетов 8-32(64)

Вот по ресурсам (Synplify ) для одного модуля - 256 каналов, 15 точек, вход 34 бит. Всего тактов = 256 * 15 + 12(pipeline_delay если мне память не изменяет). Рабочая частота ~350 MHz.

 

От числа каналов и количества точек объем логики мало зависит так как меняется только разрядность соответствующих счетчиков. То есть для 1 канала 256 точек можно грубо оценить размер логики * 8 для варианта 32 такта на отсчет.

 

Естественно этот алгоритм/реализация не оптимален по быстродействию в общем представлении.

Но он оптимален для моей конкретной задачи!

 

Успехов! Rob.

 

Mapping to part: xc5vsx240tff1738-2

Cell usage:

FD 62 uses

FDE 84 uses

FDR 44 uses

FDS 2 uses

GND 1 use

MUXCY 1 use

MUXCY_L 32 uses

RAMB18 1 use

RAMB36 4 uses

VCC 1 use

XORCY 16 uses

LUT1 2 uses

LUT2 24 uses

LUT3 41 uses

LUT4 41 uses

LUT5 14 uses

LUT6 6 uses

 

SRL primitives:

SRL16E 41 uses

 

I/O Register bits: 0

Register bits not including I/Os: 192 (0%)

 

RAM/ROM usage summary

Occupied Block RAM sites (RAMB36) : 5 of 516 (0%)

 

Total load per clock:

BlockMedian|Clk: 243

 

Mapping Summary:

Total LUTs: 169 (0%)

 

[bognev 0]

Мое предложение.

Имеем 256 х 16 память с произвольным доступом и сдвигом вперед, в которую можно записать данные по любому индексу, а следующие за ним - сдвинуть.

А есть такая память?