bognev 0 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба я прделожил алгоритм сортировки - оптимальный или нет решает ТС... Конечно в таком случае возможно нужно будет подумать над схемой ограничения разрядности 16 разрядов до 12 разрядов, т.е. чтобы было до 4096 отсчетов... затем конечно нужно будет думать над потоковой схемой нахождения среденего/медианы... Добрый день. Диапазон значений можно сжать логарифмом к 0 - 255. В адрес памяти предполагается записывать значение счетчика таких значений? Получается гистограмма, как в приведенной мной статье. Но в этом случае для худшего случая придется пройтись по всем 256 адресам для увеличения/ уменьшения значения счетчика, а это потребует 256 тактов для каждого значения. Или вы другое имели ввиду? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Добрый день. Диапазон значений можно сжать логарифмом к 0 - 255. В адрес памяти предполагается записывать значение счетчика таких значений? Получается гистограмма, как в приведенной мной статье. Но в этом случае для худшего случая придется пройтись по всем 256 адресам для увеличения/ уменьшения значения счетчика, а это потребует 256 тактов для каждого значения. Или вы другое имели ввиду? не совсем Данные превращаем в адрес для памяти (поясню например приходят данные 23, 69, 86 - Вы пишете эти значения в память по адресам 23, 69, 86). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
bognev 0 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба не совсем Тогда если приходит например 64, то по адресу 64 будет лежать 64. прошло много времени, вся память инициализирована значениями от 0 до 4096 например, какое-то масштабирование диапазона данных на диапазон значений адреса? До конца не понимаю как это будет работать? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Тогда если приходит например 64, то по адресу 64 будет лежать 64. прошло много времени, вся память инициализирована значениями от 0 до 4096 например, какое-то масштабирование диапазона данных на диапазон значений адреса? До конца не понимаю как это будет работать? прочитайте мой предыдущий пост пожалуйста, я его дополнил. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
FatRobot 1 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба В итоге в ячейках памяти лежат значения по порядку men(i)=i. Как медиану вычислять? не совсем Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба В итоге в ячейках памяти лежат значения по порядку men(i)=i. Как медиану вычислять? прочитайте мой предыдущий пост пожалуйста, я его дополнил. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
bognev 0 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Возможно нужно будет подумать над схемой ограничения разрядности 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 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Если всегда будет приходить 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 30 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Приветствую! я прделожил алгоритм сортировки - оптимальный или нет решает ТС... Увы это не сортировка :( А можно привести пример или более детально описать алгоритм? А то как то плохо пока представляю для себя реализацию. Все просто - в буфере на 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 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Приветствую! Увы это не сортировка :( Все просто - в буфере на 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 1 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба вариант Fat Robot Мне кажется, что после анализа доступных технических решений можно было бы слегка надавить на заказчиков, чтобы они подвинулись в точности оценки медианы, т.к. медиана из 256 значений - это никуда не годная печаль. Ну а дальше смотреть, какие есть варианты приближенного вычисления. Среди них, наверное - анализ гистограммы. я бы предпочел этот способ. он понятный, простой в реализации, и хорошо настраивается - усреднение нескольких медиан по короткой выборке - анализ в частотной области и т.п. В итоге все отразится в некотором проигрыше в помехоустойчивости/достоверности. Наверняка, могут себе позволить. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Мое предложение. Имеем 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 21 мая, 2015 Опубликовано 21 мая, 2015 (изменено) · Жалоба Приветствую! Увы это не сортировка :( Все просто - в буфере на 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 30 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Приветствую! возможно у меня не сортировка (спорить не буду), но в Вашем случае для 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 21 мая, 2015 Опубликовано 21 мая, 2015 · Жалоба Мое предложение. Имеем 256 х 16 память с произвольным доступом и сдвигом вперед, в которую можно записать данные по любому индексу, а следующие за ним - сдвинуть. А есть такая память? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться