bognev 0 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Типа того: 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 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба А если идут числа: много малых, например, 2, а потом два больших, например, 99 и 100, то результат должен быть 2, а не 99. По-моему, без сортировки всего массива не обойтись. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
FatRobot 1 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Все так. Точнее: берем значение из середины интервала. сравниваем вход с этим значением. определяем следующий интевал Каждая такая итерация даст вам очередной младший разряд к искомому индексу. Некоторые ухищрения будут связаны с серединой для интевала с четным числом отсчетов, но они не существенные, и вы справитесь Если я правильно понял, то это делить пополам массив, потом выбирать в какой интервал попадает, потом опять делить и так повоторять? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 24 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Ваш алгоритм ищет максимальное значение :-) Да.. похоже, что так.. Виноват!.. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
FatRobot 1 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Ах да. Вам нужно еще следить за самым старым отсчетом в сортированном массиве. Я думаю, что все закончится регистровым файлом для отсчетов и ЛЗ с модификацией для истории индексов самого старого отсчета. итого где-то ( 256 х 16 + 256 х 8 ) FFs. Также для работы потребуется несложная арифметика + мультиплексоры. Нормально. Вот в этом сигнале в окне на 256 отсчетов надо находить среднее. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
bognev 0 20 мая, 2015 Опубликовано 20 мая, 2015 (изменено) · Жалоба Несколько подходов: 1. Наполняете очердной буфер. ставите его в очередь к сортировщику. свободный исполнительный модуль сортировки берет буфер из очереди и сортирует его. Сложность в том, что средняя сложность хорошего сортировщика O(n*log(n)), в то время как худший случай для того же хорошего сортировщика всегда O(n^2). Вот между двумя этими значениями вам придется скакать при расчете кол-ва буферов и исполнительных модулей сортировки 2. Решаете задачу вставления отсчета в уже сортированный массив. поиск делается за log2(n) тактов. Скорость вставки зависит от того, как хранится массив. Либо задача поиска и вставки решается с применением связанного списка. Но на каждый отсчет требуется в среднем n/2 операций, и n в худшем случае. 3. pipeline сортировщик (например пузырьковый). тут воля для фантазии огромна, как и требование к ресурсам. Особенно с учетом исходной задачи построения ранга по 16-ти битовым остчетам. Вставление отсчета в уже сортированный массив тоже можно конвеерезировать. И наверное лучше сначала компрессировать отсчеты до 4-8 бит, взяв логарифм Я правильно понимаю, что если изначально все элементы нули, то метод вставки позволяет сформировать отсортированный массив по мере поступления отсчетов и нет необходимости в предварительной сортировщике? Изменено 20 мая, 2015 пользователем bognev Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
FatRobot 1 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Все так. в начале работы все элементы должны иметь одно значение. Через 256 поступивших отсчетов ваш массив будет заполнен отсортированными значениями. Следующие пришедшие остчеты будут вставляться уже в отстортированный массив. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RobFPGA 30 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Приветствую! Ах да. Вам нужно еще следить за самым старым отсчетом в сортированном массиве. Я думаю, что все закончится регистровым файлом для отсчетов и сдвиговыи регистром с модификацией для истории индексов самого старого отсчета. итого где-то ( 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 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Любопытный документик попался: 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 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба да, я писал о таком решении ранее. Там, кстати, количество модулей сортировки будет интересно рассчитываться итеративно: количество тактов для сортирвки вставкой будет зависеть от количества новых отсчетов. а количество новых отсчетов в свою очередь зависит от кол-ва тактов, которое тратится на сортировку одним модулем Там есть вопрос, который не очевидно, на мой взгляд, решается: следить за историей отсчетов, чтобы освобождаться от старых. Или сортировать все "как с чистого листа". Выстроив К таких модулей в цепочку думаю можно малыми ресурсами получит N/K тактов на осчет для одного канала. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RobFPGA 30 20 мая, 2015 Опубликовано 20 мая, 2015 · Жалоба Приветствую! ... количество тактов для сортирвки будет (количество новых отсчетов) * log2( размер массива ) при сортировке вставкой с доп. ... Там есть вопрос, который не очевидно, на мой взгляд, решается: следить за историей отсчетов, чтобы освобождаться от старых. Или сортировать все "с нуля". Я не стал заморачиваться с бинарным поиском в массиве - поскольку потом все равно надо будет в худшем случае проходить по всему массиву для сдвига при вставке нового, поиске и удалении старого отсчета. В памяти хранится значение отсчета и индекс давности - соответственно за один проход получалось вставить новый в правильную позицию и выбросить самый старый отсчет. Успехов! Rob Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
bognev 0 20 мая, 2015 Опубликовано 20 мая, 2015 (изменено) · Жалоба Приветствую! Я как-то делал модуль медианного фильтра, правда в моем случае надо было сделать 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 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Кто нибудь сталкивался с эффективным сортировщиком массива отсчетов по возрастанию, например, на 256 отсчетов в реальном времени на плис с оптимальными параметрами по занимаемым ресурсам? Задача стоит в выкусывании несинхронной помехи в принятом сигнале, наиболее эффективным алгоритмом является ранговая обработка. Каждые 40 тактов поступает новый 16 разрядный отсчет, всего предполагается 4096 отсчетов и по ним надо в реальном времени строить ранговый порог. Как с этим проще справиться? Может быть сталкивался кто нибудь? Заранее благодарю за помощь. предлагаю попробовать следующим образом: например у Вас данные от 0 до 255. Делаем память на 256 значений (думаю здесь будет лучше использовать двухпортовую память - один порт для записи, второй для чтения). Данные превращаем в адрес для памяти (поясню например приходят данные 23, 69, 86 - Вы пишете эти значения в память по адресам 23, 69, 86). Таким образом, у Вас в памяти всегда отсортированный массив... PS Только здесь Вам нужно будет решить одну возможную колизию чтение и запись по одному и тому же адресу в один и тот же момент времени... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Golikov 0 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Каждые 40 тактов поступает новый 16 разрядный отсчет размер памяти в таком решении определяется диапазоном значений, а не числом элементов! так что память должна быть на 65536 байт И не решается проблема устранения самого старого отсчета. И поиска какой-же теперь из них средний... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Возможно нужно будет подумать над схемой ограничения разрядности 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; Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться