[bognev 0]

Типа того:

unsigned short S[256]; // это входные сэмплы.. их можно вообще не хранить, а просматривать в цикле по мере поступления..

unsigned short Smid = 0;
unsigned short Smin = 0;
unsigned short Smax = 65535;

for (int i = 0; i < 256; i++)
{
  if (Smid < S[i])
  {
    if (S[i] < Smax)
    {
      Smin = Smid;
      Smid = S[i];
    }
  }
  else
  if (S[i] < Smid)
  {
    if (Smin < S[i])
    {
      Smax = Smid;
      Smid = S[i];
    }
  }
}

return Smid;

Ваш алгоритм ищет максимальное значение :-)

 

Нахождение места для нового отсчета в отсортированном массиве делается дихотомией.

log2(256) = 8 тактов

 

Вся задача сводится к тому, как хранить массив, чтобы в него в нужное, уже найденное место, вставить отсчет за заданное кол-во тактов. вот и всё.

Если я правильно понял, то это делить пополам массив, потом выбирать в какой интервал попадает, потом опять делить и так повоторять?

[ViKo 1]

А если идут числа: много малых, например, 2, а потом два больших, например, 99 и 100, то результат должен быть 2, а не 99. По-моему, без сортировки всего массива не обойтись.

[FatRobot 1]

Все так. Точнее:

берем значение из середины интервала.

сравниваем вход с этим значением.

определяем следующий интевал

Каждая такая итерация даст вам очередной младший разряд к искомому индексу.

 

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

 

 

Если я правильно понял, то это делить пополам массив, потом выбирать в какой интервал попадает, потом опять делить и так повоторять?

[blackfin 24]

Ваш алгоритм ищет максимальное значение :-)

Да.. похоже, что так.. Виноват!..

[FatRobot 1]

Ах да. Вам нужно еще следить за самым старым отсчетом в сортированном массиве.

 

Я думаю, что все закончится регистровым файлом для отсчетов и ЛЗ с модификацией для истории индексов самого старого отсчета. итого где-то ( 256 х 16 + 256 х 8 ) FFs.

Также для работы потребуется несложная арифметика + мультиплексоры. Нормально.

 

Вот в этом сигнале в окне на 256 отсчетов надо находить среднее.

[bognev 0]

Несколько подходов:

 

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

Сложность в том, что средняя сложность хорошего сортировщика O(n*log(n)), в то время как худший случай для того же хорошего сортировщика всегда O(n^2). Вот между двумя этими значениями вам придется скакать при расчете кол-ва буферов и исполнительных модулей сортировки

 

2. Решаете задачу вставления отсчета в уже сортированный массив. поиск делается за log2(n) тактов. Скорость вставки зависит от того, как хранится массив. Либо задача поиска и вставки решается с применением связанного списка. Но на каждый отсчет требуется в среднем n/2 операций, и n в худшем случае.

 

3. pipeline сортировщик (например пузырьковый). тут воля для фантазии огромна, как и требование к ресурсам. Особенно с учетом исходной задачи построения ранга по 16-ти битовым остчетам. Вставление отсчета в уже сортированный массив тоже можно конвеерезировать.

 

И наверное лучше сначала компрессировать отсчеты до 4-8 бит, взяв логарифм

Я правильно понимаю, что если изначально все элементы нули, то метод вставки позволяет сформировать отсортированный массив по мере поступления отсчетов и нет необходимости в предварительной сортировщике?

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

[FatRobot 1]

Все так. в начале работы все элементы должны иметь одно значение.

Через 256 поступивших отсчетов ваш массив будет заполнен отсортированными значениями. Следующие пришедшие остчеты будут вставляться уже в отстортированный массив.

 

 

[RobFPGA 30]

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

 

Ах да. Вам нужно еще следить за самым старым отсчетом в сортированном массиве.

 

Я думаю, что все закончится регистровым файлом для отсчетов и сдвиговыи регистром с модификацией для истории индексов самого старого отсчета. итого где-то ( 256 х 16 + 256 х 8 ) FFs.

Также для работы потребуется несложная арифметика + мультиплексоры. Нормально.

Я как-то делал модуль медианного фильтра, правда в моем случае надо было сделать 256 паралельных фильтров с окном N=7-15 отсчетов, 34 bit. Cортировка вставкой, N тактов на отсчет. Получалась несложная структура read_ram->logic->write_ram, малого размера которая хорошо конвеерезируется (на V5 работало >300 MHz). У меня N таких модулей работали в паралель обеспечивая потоковую фильтрацию.

 

Выстроив К таких модулей в цепочку думаю можно малыми ресурсами получит N/K тактов на осчет для одного канала.

 

Успехов! Rob.

[blackfin 24]

Любопытный документик попался: Fast median search: an ANSI C implementation

3.4 Non-recursive search using median WIRTH()

The pseudo-code for this algorithm is given in the book, and in wirth.c (see

code section below) a literal translation is done from Pascal to ANSI C. It does not

try to sort out the complete array but browses through the input array just enough

to determine what is the kth smallest element in the input list. It is not recursive

and does not need to allocate any memory, nor does it use any external function.

As a result, it gains a factor 25 in speed compared to the qsort() based method.

 

3.5 Quick select

This algorithm was published in [Numerical Recipes].

Speedwise, it is a close tie with Wirth’s method. On the average, this one is

faster, however.

В статье приведены бенчмарки различных алгоритмов и исходные коды на "С".

[FatRobot 1]

да, я писал о таком решении ранее.

 

Там, кстати, количество модулей сортировки будет интересно рассчитываться итеративно:

количество тактов для сортирвки вставкой будет зависеть от количества новых отсчетов. а количество новых отсчетов в свою очередь зависит от кол-ва тактов, которое тратится на сортировку одним модулем

 

Там есть вопрос, который не очевидно, на мой взгляд, решается: следить за историей отсчетов, чтобы освобождаться от старых. Или сортировать все "как с чистого листа".

 

Выстроив К таких модулей в цепочку думаю можно малыми ресурсами получит N/K тактов на осчет для одного канала.

[RobFPGA 30]

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

 

...

количество тактов для сортирвки будет (количество новых отсчетов) * log2( размер массива ) при сортировке вставкой с доп.

...

Там есть вопрос, который не очевидно, на мой взгляд, решается: следить за историей отсчетов, чтобы освобождаться от старых. Или сортировать все "с нуля".

 

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

В памяти хранится значение отсчета и индекс давности - соответственно за один проход получалось вставить новый в правильную позицию и выбросить самый старый отсчет.

 

Успехов! Rob

[bognev 0]

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

 

 

Я как-то делал модуль медианного фильтра, правда в моем случае надо было сделать 256 паралельных фильтров с окном N=7-15 отсчетов, 34 bit. Cортировка вставкой, N тактов на отсчет. Получалась несложная структура read_ram->logic->write_ram, малого размера которая хорошо конвеерезируется (на V5 работало >300 MHz). У меня N таких модулей работали в паралель обеспечивая потоковую фильтрацию.

 

Выстроив К таких модулей в цепочку думаю можно малыми ресурсами получит N/K тактов на осчет для одного канала.

 

Успехов! Rob.

У меня полная противоположность) надо окном на 256 отчётов сделать сортировку в 8 параллельных каналах. Хотелось бы, чтобы алгоритм позволяли обрабатывать все каналы последовательно.

 

Любопытный документик попался: Fast median search: an ANSI C implementation

 

В статье приведены бенчмарки различных алгоритмов и исходные коды на "С".

Спасибо, очень полезная статья. По мне так наиболее просто реализуется алгоритм Optimized sorting networks, но на 256 отчётов плохо масштабируется.

 

да, я писал о таком решении ранее.

 

Там, кстати, количество модулей сортировки будет интересно рассчитываться итеративно:

количество тактов для сортирвки вставкой будет зависеть от количества новых отсчетов. а количество новых отсчетов в свою очередь зависит от кол-ва тактов, которое тратится на сортировку одним модулем

 

Там есть вопрос, который не очевидно, на мой взгляд, решается: следить за историей отсчетов, чтобы освобождаться от старых. Или сортировать все "как с чистого листа".

А можно привести пример или более детально описать алгоритм? А то как то плохо пока представляю для себя реализацию. Именно в плане того, что есть сортировка вставкой на 256 отчётов, 1 отсчёт на 40 тактов, по методу дихотомии понадобится 8 тактов на сортировку и получается, что этот алгоритм можно разбить на несколько параллельных модулей сортировки?

 

Что можете сказать про подобную реализацию? http://www.ntu.edu.sg/home/sfahmy/files/pa.../ietcdt2009.pdf

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

[Maverick_ 15]

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

 

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

предлагаю попробовать следующим образом:

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

Таким образом, у Вас в памяти всегда отсортированный массив...

PS Только здесь Вам нужно будет решить одну возможную колизию чтение и запись по одному и тому же адресу в один и тот же момент времени...

[Golikov 0]

Каждые 40 тактов поступает новый 16 разрядный отсчет

 

размер памяти в таком решении определяется диапазоном значений, а не числом элементов!

так что память должна быть на 65536 байт

 

И не решается проблема устранения самого старого отсчета. И поиска какой-же теперь из них средний...

[Maverick_ 15]

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

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

Если заполняется какой-то дипазон памяти, то должна быть схема которая будет отслеживать диапазон (для этого потребуется нахождение максимального и минимального значения среди данных - привел ниже пример описания), тогда медианное значение будет находиться по адресу (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;