Maverick_ 15 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба Вот моя наброска самой простой реализации (не проверял, но логически вроде верно) - на вход поставить паралельно-последовательный конвертор, чтобы на вход моего модуля данные (Ваши 25 чисел) приходили последовательно) library ieee; use ieee.std_logic_1164.all; library work; package Const_type is type my_array is array (0 to 255) of std_logic_vector (7 downto 0); end package; library IEEE; use IEEE.STD_LOGIC_1164.ALL; USE ieee.numeric_std.ALL; use work.Const_type.all; entity hist is Port ( CLK : in std_logic; rst : in std_logic; indata : in std_logic_vector (7 downto 0); ready : out std_logic; outdata : out std_logic_vector (7 downto 0); ); end hist; architecture behavioral of hist is signal table_index : my_array; signal reg_data : std_logic_vector (7 downto 0); signal reg_index : std_logic_vector (7 downto 0); signal reg_state : std_logic_vector (1 downto 0);; begin process (all) begin if (rst = '1') then reg_index <= (OTHERS => (OTHERS => '0')); reg_state <= (others => '0'); reg_ready <= '0'; reg_index <= (others => '0'); reg_data <= (others => '0'); elsif (CLK'event and CLK ='1') then if reg_state = "00" then -- read data from table reg_data <= indata; reg_index <= table_index(to_integer(unsigned(indata))); reg_state <= std_logic_vector( unsigned(reg_state) + 1); reg_ready <= '0'; elsif reg_state = "01" then -- calculation index reg_state <= std_logic_vector( unsigned(reg_state) + 1); reg_index <= std_logic_vector( unsigned(reg_index) + 1); elsif reg_state = "10" then -- write new date to table reg_state <= (OTHERS => '0'); table_index (to_integer(unsigned(reg_data))) <= reg_index; reg_ready <= '1'; end if; end if; end process; outdata <= table_index (to_integer(unsigned(reg_data))); ready <= reg_ready; end behavioral; Реализация простая есть так сказать 3 состояния/такта (reg_state). На каждом состоянии/такте происходит соотвующая операция: 1. чтение данных из таблицы; 2 инкремент индекса 3 запись нового значения индекса в таблицу Далее все начинается сначала... PS Далее делаем второй модуль который сделать по сигналу ready сравнивает значение индексов (выход outdata) с предыдущим значение. Внутренний регистр в котором будет храниться максимальное число инициализируете максимальным числом (как то так reg_max <= (others => '1');) не проверял - наброски... library ieee; use ieee.std_logic_1164.all; library work; package Const_type is type my_array is array (0 to 24) of std_logic_vector (7 downto 0); end package; library IEEE; use IEEE.STD_LOGIC_1164.ALL; USE ieee.numeric_std.ALL; use work.Const_type.all; entity parallel2serial is generic( num : integer:= 25 ); port ( i_clk : in std_logic; i_rstb : in std_logic; i_data_ena : in std_logic; i_data : in my_array; o_data_valid : out std_logic; o_data : out std_logic_vector (7 downto 0)); end parallel2serial; architecture rtl of parallel2serial is signal r_data : my_array; signal r_count : integer range 0 to (num-1); begin p_paralle2serial : process(all) begin if(i_rstb='0') then r_count <= 0; elsif(rising_edge(i_clk)) then if i_data_ena = '1' then r_count <= r_count + 1; o_data <= i_data(r_count); end if; if r_count = 24 then o_data_valid <= '1'; else o_data_valid <= '0'; end if; end if; end process p_paralle2serial; Будут вопросы спрашивайте :) паралельная pipeline реализация займет больше ресурсов чем представленная последовательная реализация Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
xvr 12 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба 2 ТС - у вас какая задача: найти самое часто встречаемое число, или число которое встречается более половины раз? Это как бы разные задачи :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ЕвгенийЗлыднев 0 12 сентября, 2019 Опубликовано 12 сентября, 2019 (изменено) · Жалоба 6 часов назад, MrGalaxy сказал: Евгений Злыднев, Код непонятен. Первый if понятно, асинхронная установка, второй if тоже понятно, работа по фронту, а дальше ничего не понимаю... Синхронный if не предусматривает else. Разве Квартус на такую конструкцию не ругается? Вроде должен. Вам правильно посоветовали вычислить гистограмму. Я бы это сделал за один такт, т.к. входной массив уже заполнен (это тот случай, когда оператор цикла в ПЛИС уместен). За следующий такт проанализировал бы полученную гистограмму и выдал сигнал на выход. Длительность такта подобрал бы при симуляции. И не стесняйтесь в коде писать комментарии, самому проще будет, как можно писать код без единого комментария! Else желательно писать под соответствующим then, т.е. с необходимым отступом, так код будет лучше читаться. Потом, когда проект отладите и будете ставить исходники на учёт в ОТД, подробные комментарии уберёте. :) Вот цитата из статьи которую я привел. Она говорит почему я не хочу таблицы. Цитата для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями? В несколько раз больше исходного массива это слишком. Мне нужно чтобы поменьше ресурсов тратить. 1 час назад, xvr сказал: 2 ТС - у вас какая задача: найти самое часто встречаемое число, или число которое встречается более половины раз? Это как бы разные задачи :) Самое часто встречаемое и в тоже время больше половины раз. Т.е из 13 из 25 если встретилось то это оно. Если даже 12 из 25, то выдавать нули. 2 часа назад, Maverick_ сказал: Вот моя наброска самой простой реализации (не проверял, но логически вроде верно) - на вход поставить паралельно-последовательный конвертор, чтобы на вход моего модуля данные (Ваши 25 чисел) приходили последовательно) library ieee; use ieee.std_logic_1164.all; library work; package Const_type is type my_array is array (0 to 255) of std_logic_vector (7 downto 0); end package; library IEEE; use IEEE.STD_LOGIC_1164.ALL; USE ieee.numeric_std.ALL; use work.Const_type.all; entity hist is Port ( CLK : in std_logic; rst : in std_logic; indata : in std_logic_vector (7 downto 0); ready : out std_logic; outdata : out std_logic_vector (7 downto 0); ); end hist; architecture behavioral of hist is signal table_index : my_array; signal reg_data : std_logic_vector (7 downto 0); signal reg_index : std_logic_vector (7 downto 0); signal reg_state : std_logic_vector (1 downto 0);; begin process (all) begin if (rst = '1') then reg_index <= (OTHERS => (OTHERS => '0')); reg_state <= (others => '0'); reg_ready <= '0'; reg_index <= (others => '0'); reg_data <= (others => '0'); elsif (CLK'event and CLK ='1') then if reg_state = "00" then -- read data from table reg_data <= indata; reg_index <= table_index(to_integer(unsigned(indata))); reg_state <= std_logic_vector( unsigned(reg_state) + 1); reg_ready <= '0'; elsif reg_state = "01" then -- calculation index reg_state <= std_logic_vector( unsigned(reg_state) + 1); reg_index <= std_logic_vector( unsigned(reg_index) + 1); elsif reg_state = "10" then -- write new date to table reg_state <= (OTHERS => '0'); table_index (to_integer(unsigned(reg_data))) <= reg_index; reg_ready <= '1'; end if; end if; end process; outdata <= table_index (to_integer(unsigned(reg_data))); ready <= reg_ready; end behavioral; Реализация простая есть так сказать 3 состояния/такта (reg_state). На каждом состоянии/такте происходит соотвующая операция: 1. чтение данных из таблицы; 2 инкремент индекса 3 запись нового значения индекса в таблицу Далее все начинается сначала... PS Далее делаем второй модуль который сделать по сигналу ready сравнивает значение индексов (выход outdata) с предыдущим значение. Внутренний регистр в котором будет храниться максимальное число инициализируете максимальным числом (как то так reg_max <= (others => '1');) не проверял - наброски... library ieee; use ieee.std_logic_1164.all; library work; package Const_type is type my_array is array (0 to 24) of std_logic_vector (7 downto 0); end package; library IEEE; use IEEE.STD_LOGIC_1164.ALL; USE ieee.numeric_std.ALL; use work.Const_type.all; entity parallel2serial is generic( num : integer:= 25 ); port ( i_clk : in std_logic; i_rstb : in std_logic; i_data_ena : in std_logic; i_data : in my_array; o_data_valid : out std_logic; o_data : out std_logic_vector (7 downto 0)); end parallel2serial; architecture rtl of parallel2serial is signal r_data : my_array; signal r_count : integer range 0 to (num-1); begin p_paralle2serial : process(all) begin if(i_rstb='0') then r_count <= 0; elsif(rising_edge(i_clk)) then if i_data_ena = '1' then r_count <= r_count + 1; o_data <= i_data(r_count); end if; if r_count = 24 then o_data_valid <= '1'; else o_data_valid <= '0'; end if; end if; end process p_paralle2serial; Будут вопросы спрашивайте :) паралельная pipeline реализация займет больше ресурсов чем представленная последовательная реализация Я обязательно попробую ваш вариант. Хотя бы для сравнения с моим. Спасибо. Изменено 12 сентября, 2019 пользователем ЕвгенийЗлыднев Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба 36 minutes ago, ЕвгенийЗлыднев said: Я обязательно попробую ваш вариант. Хотя бы для сравнения с моим. Спасибо. Спасибо, отпишитесь пожалуйста по результатам реализации Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ЕвгенийЗлыднев 0 12 сентября, 2019 Опубликовано 12 сентября, 2019 (изменено) · Жалоба 17 часов назад, RobFPGA сказал: Приветствую! Основная ошибка в неправильном алгоритме который вы пытаетесь повторить. Даже у меня не получится реализовать неправильный алгоритм У вас какое условие? Как понять что число "наиболее часто встречается" - естественно надо посчитать эти встречи (вот вам и обьяснение, "а при чем тут гистограммы". А так как какое конкретное число нам будет встречаться мы не знаем то хорошо бы иметь свой счетчик для каждого возможного значение числа. Вот вам и таблица на 256x5. Ну а дальше начинаем оптимизировать по условиям задачи - ограничение длины последовательности и конкретный порог превышения дают нам уверенность что таких счетчиков достаточно будет (длина - порог)+1 (намекну - что если первые 13 чисел у вас будут все разные? ). Удачи! Rob. Что касается не правильного исходного алгоритма то я попробовал на Матлабе его реализовать. У меня все работает как надо. Но на плис не хочет это синтезировать. a1 = [46,46,46,46,46,46,46,46,46,46,46,46,46,11,10,9,8,7,6,5,4,3,2,1,0]; %массив conf = 0;% начальное значение и количество, не нашедших пары и оставшихся "стоять" candidate = 1; %начальное значение "кандидата" b = randsample(a1,25);% перемещиваем исходный массив for i=1:length(b)% начинаем алгоритм поиска наиболее частого значения в массиве if (conf == 0) % если нет "одиноких" чисел, то присваеиваем значение текущего "одинокому" candidate = b(i); conf=conf+1; elseif candidate == b(i)% если есть "одинокие", то сравниваем рядом стоящие conf=conf+1; else conf=conf-1; end conf candidate end А можете по коду еще посмотреть в чем может быть ошибка? может с индексами что не так? или из-за того что я i и j ограничил по разрядности? Вчера к сожалению не тот снимок привел. Вот более подробная диаграмма. Опишу алгоритм подробнее: 1) По уровню "1" на сигнале Go начинаем сортировать. Когда все по нулям просто увеличиваем счетчики i и j на 1. Значение ibn записываем в регистр temp. 2) Далее, сравниваем предыдущий элемент со следующим. Если равны то увеличиваем значение j и также в temp перезаписываем значение которое там уже есть. Если не равны то уменьшаем j и переписываем значение ibn(i+1) в temp. Каждое сравнение это один такт, i увеличиваем каждый такт. 3) Когда алгоритм отработал (i=24) если j больше нуля то записываем в регистр nomer данные из регистра temp. Если j больше нуля то записываем нули (у меня в коде 1, это для эксперимента было). Когда алгоритм отработал он ставит сигнал done в единицу. После этого возникают вопросы: Почему I не с нуля стартует, а с 3. И то увеличивается, то уменьшается. Хотя я четко обозначил что на каждом шагу она должна только увеличиваться. Почему номер не выдается как нужно? Кто-то может просто повторить это алгоритм? Был бы очень признателен. Он очень ведь компактный. Всего несколько строк. Видео урок как это подобное реализуется в учебнике и примеры я выложил. Там вроде все доступно. Если честно не думал, что вызовет столько затруднений мой пример у людей. Что касается других вариантов и алгоритмов то это круто что столько отзывов последовало. Но у меня уже какой-то азарт реализовать это алгоритм, Потому что учебные примеры так легко получились, и так ясно работают что мне как-то обидно за себя что я не могу простейший алгоритм реализовать. Хотя вся информация уже есть, и видео уроки и учебник (( Если получатся несколько вариантов то я хоть сравню их. И выберу лучший, так даже более правильно будет. Если что для другого случая применю потом. Я все компоненты свои сохраняю, и потом как типовые использую. Просто меняю разрядность и т.п. Так что несколько вариантов лишними не будут. Изменено 12 сентября, 2019 пользователем ЕвгенийЗлыднев Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RobFPGA 27 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба Приветствую! 7 minutes ago, ЕвгенийЗлыднев said: Что касается не правильного исходного алгоритма то я попробовал на Матлабе его реализовать. У меня все работает как надо. А ежики такие упорные ... Этот алгоритм работает только когда вы ТОЧНО знаете что у вас во входном массиве ЕСТЬ >=N/2+1 одинаковых чисел. А по вашему входному условию вы этого не знаете. Я же предлагал оценить работу этого алгоритма для длины 3. Ведь алгоритм от этого не меняется. Удачи! Rob. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ЕвгенийЗлыднев 0 12 сентября, 2019 Опубликовано 12 сентября, 2019 (изменено) · Жалоба 22 минуты назад, RobFPGA сказал: Приветствую! А ежики такие упорные ... Этот алгоритм работает только когда вы ТОЧНО знаете что у вас во входном массиве ЕСТЬ >=N/2+1 одинаковых чисел. А по вашему входному условию вы этого не знаете. Я же предлагал оценить работу этого алгоритма для длины 3. Ведь алгоритм от этого не меняется. Удачи! Rob. Если не обнаружил такого то пусть нули выдает. На самом деле там скорее всего либо одно и тоже число, либо нули. На всякий случай нужен это алгоритм для проверки. int* majority(int[] array, int N) { int confidence = 0; // количество людей, не нашедших пары и оставшихся стоять int* candidate = NULL; // последний человек, не нашедший пару -- // возможно, его элемент встречается чаще всего // проходим по массиву и усаживаем пары с разными элементами for (int i = 0; i<N; i++) { // если до сих пор все сидят, то следующему пока придётся постоять if (confidence == 0) { candidate = array+i; confidence++; } // иначе следующий либо садится с одним из стоящих, // либо будет стоять вместе с ними, если у него такой же элемент else if (*candidate == array[i])) confidence++; else confidence--; } return confidence > 0 ? candidate : NULL; } В исходном алгоритме в последней строке возвращается candidate, если confidence больше нуля. А если меньше то NULL возращает. У меня там же есть условие что j должно быть больше 0. j аналог confidence. Т.е вроде все соблюдено. Что такое длина 3 ? не совсем понял. Изменено 12 сентября, 2019 пользователем ЕвгенийЗлыднев Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба Input: [1, 4, 3, 3, 2, 5] Sum = 18 As in this example, we have n = 5: Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15=> 18 - 15 = 3 so 3 is the duplicate но Input: [1, 2, 3, 2, 3, 4] Sum = 15As in this example we have n = 5, Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15/!\ Not working Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ЕвгенийЗлыднев 0 12 сентября, 2019 Опубликовано 12 сентября, 2019 (изменено) · Жалоба 17 минут назад, Maverick_ сказал: Input: [1, 4, 3, 3, 2, 5] Sum = 18 As in this example, we have n = 5: Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15=> 18 - 15 = 3 so 3 is the duplicate то есть надо просто сложить все числа входные и вычесть их из константы 1+2+3+...225? и получим результат? Не увидел ваших замечаний, и проверил сразу в матлабе. не работает алгоритм если как и вашем примере сумма элементов меньше. Изменено 12 сентября, 2019 пользователем ЕвгенийЗлыднев Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RobFPGA 27 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба Приветствую! 27 minutes ago, ЕвгенийЗлыднев said: Что такое длина 3 ? не совсем понял. Поведение алгоритма не должно меняться от размера массива. Ведь так? 3 hours ago, RobFPGA said: Проверьте этот же алгоритм для длинны 3 точки (2 из 3) Каков будет ответ для входных чисел 1,2,3 и 1,2,1 ? Еще раз - В оригинальном описании этого алгоритма говорится что если вы УЖЕ ЗНАЕТЕ что во входной последовательности есть N/2+1 одинаковых чисел то этот алгоритм выдаст это число. А вот если вы этого не знаете - то этот алгоритм выдаст возможного кандидата на такое число И чтобы убедится что это число действительно встречается N/2+1 вам надо еще раз пройтись по массиву и посчитать число включений этого кандидата. 13 minutes ago, Maverick_ said: Input: [1, 4, 3, 3, 2, 5] Sum = 18 As in this example, we have n = 5: Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15=> 18 - 15 = 3 so 3 is the duplicate Input: [1,4,3,3,2,7] -> ?? Удачи! Rob. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ЕвгенийЗлыднев 0 12 сентября, 2019 Опубликовано 12 сентября, 2019 (изменено) · Жалоба 7 минут назад, RobFPGA сказал: Приветствую! Поведение алгоритма не должно меняться от размера массива. Ведь так? Еще раз - В оригинальном описании этого алгоритма говорится что если вы УЖЕ ЗНАЕТЕ что во входной последовательности есть N/2+1 одинаковых чисел то этот алгоритм выдаст это число. А вот если вы этого не знаете - то этот алгоритм выдаст возможного кандидата на такое число И чтобы убедится что это число действительно встречается N/2+1 вам надо еще раз пройтись по массиву и посчитать число включений этого кандидата. [1,4,3,3,2,7] -> ?? Удачи! Rob. Все понял про что вы :-) Про количество входных сигналов . В симуляции я же задаю сигналы, я знаю что там содержится. Если бы там его не было и выдавал бы странное значение это было бы нормально. Но он все равно не работает. Вторым проходом можно заняться когда уже первый будет нормальный. Т.е. хотя бы для начала первый сделать надо. Самое странное то что я задаю напрямую не хочет показать. Изменено 12 сентября, 2019 пользователем ЕвгенийЗлыднев Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 16 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба On 9/11/2019 at 4:16 PM, ЕвгенийЗлыднев said: Есть 25 чисел, каждое 8 бит. Надо найти наиболее часто встречающиеся среди них т.е. если число встречается 13 и больше раз, это то что мы ищем. Вот мой вариант решения: #include "stdafx.h" unsigned char src[25] = {46,46,46,46,46,46,46,46,46,46,46,46,46,11,10,9,8,7,6,5,4,3,2,1,0}; unsigned char bits; unsigned char freq; int _tmain(int argc, _TCHAR* argv[]) { int i,j; bits = 0; for (i = 0; i < 8; i++) { freq = 0; for (j = 0; j < 25; j++) { freq += (src[j] >> i) & 1; } if (freq > 12) bits |= (1 << i); } freq = 0; for (j = 0; j < 25; j++) if (bits == src[j]) freq++; if (freq > 12) printf("Most frequent src = %d",bits); else printf("Most frequent src not found!"); return 0; } За три такта на верилоге можно посчитать, КМК.. :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ЕвгенийЗлыднев 0 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба 13 минут назад, blackfin сказал: Вот мой вариант решения: #include "stdafx.h" unsigned char src[25] = {46,46,46,46,46,46,46,46,46,46,46,46,46,11,10,9,8,7,6,5,4,3,2,1,0}; unsigned char bits; unsigned char freq; int _tmain(int argc, _TCHAR* argv[]) { int i,j; bits = 0; for (i = 0; i < 8; i++) { freq = 0; for (j = 0; j < 25; j++) { freq += (src[j] >> i) & 1; } if (freq > 12) bits |= (1 << i); } freq = 0; for (j = 0; j < 25; j++) if (bits == src[j]) freq++; if (freq > 12) printf("Most frequent src = %d",bits); else printf("Most frequent src not found!"); return 0; } За три такта на верилоге можно посчитать, КМК.. :) К сожалению, не всегда как видно можно даже простые алгоритмы на Плис реализовать. Хоть за 3 такта хоть за 25. Поэтому ваш потом попробую написать. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Nick_K 0 12 сентября, 2019 Опубликовано 12 сентября, 2019 · Жалоба Вот сижу второй день и смотрю, как люди изобретают велосипед, для немного переделанного стека MAC... Подсказка: для конкретно этого случая стек на 13 "адресов". Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
