acvarif 0 18 сентября, 2013 Опубликовано 18 сентября, 2013 (изменено) · Жалоба На данный момент, когда Вы смотрите на перевернутые графы с прореживанием по частоте на базе 2-х точечной бабочки и пытаетесь в уме все это преобразовать в граф на базе 8-ми точечной бабочки с прореживанием по времени у вас получается полная ерунда. Ничего подобного. Возьмите восьмиточечный граф прореживания по частоте и просто наложите его на граф прореживания по времени. Они совпадут. Только накладывать нужно с поворотом на 180 град. Ладошка к ладошке. Стрелки в графе поверните в обратную сторону. Неужели это не заметно? Это же очевидно. В случае БПФ с прореживанием по времени можно 8ми точечный выполнить последовательно выполняя 4 двухточечных, затем последовательно (не параллельно) 2 четырехточечных (вернее две половинки второй стадии) и только на последнем этапе 3_ю стадию восьмиточечного. Похоже и с 16 точками и с 32. Входные данные для каждой операции нужно мультиплексировать, а выходные сохранять в буфере для последующего мультиплексирования на очередную стадию. Изменено 18 сентября, 2013 пользователем Acvarif Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Golikov 0 18 сентября, 2013 Опубликовано 18 сентября, 2013 · Жалоба 8 точек на входе 8 отсчетов на выходе делаем четыре 2 в 2, первая стадия, потом два 4 в 4, вторая стадия, потом одно 8 в 8 - последняя стадия. число умножений 4*2 + 2*4 + 1*8 = 24 делаем четыре 2 в 2, первая стадия, потом четыре 2 в 2, вторая стадия, потом четыре 2 в 2 - последняя стадия. число умножений 4*2 + 4*2 + 4*2 = 24 и какой смысл 8 точечного фурье? почему то под 8 точечным фурье постоянно всплывает 4 бабочки 2 в 2, которые стоят параллельно. Поправьте меня, но мне кажется это не верно... я бы поверил в некое 8 точечное фурье которое делает не 24, а меньше умножений и переводит 8 точек в 8 отсчетов за раз... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
acvarif 0 18 сентября, 2013 Опубликовано 18 сентября, 2013 (изменено) · Жалоба 8 точек на входе 8 отсчетов на выходе делаем четыре 2 в 2, первая стадия, потом два 4 в 4, вторая стадия, потом одно 8 в 8 - последняя стадия. число умножений 4*2 + 2*4 + 1*8 = 24 делаем четыре 2 в 2, первая стадия, потом четыре 2 в 2, вторая стадия, потом четыре 2 в 2 - последняя стадия. число умножений 4*2 + 4*2 + 4*2 = 24 и какой смысл 8 точечного фурье? почему то под 8 точечным фурье постоянно всплывает 4 бабочки 2 в 2, которые стоят параллельно. Поправьте меня, но мне кажется это не верно... я бы поверил в некое 8 точечное фурье которое делает не 24, а меньше умножений и переводит 8 точек в 8 отсчетов за раз... Не так. 4 раза по 2 (первая стадия) но последовательно - всего 2 умножителя на все четыре двухточечных бабочки потому, что используется один и тот же ресурс ПЛИС (или схемка). Хотя 4 операции умножения. Входные данные мультиплексируются, выходные сохраняются в буфере для 2_й стадии. Итак далее... Время выполнения увеличивается, ресурсы сокращаются. Итого Первая стадия 2 умножителя. Вторая 4. Третья 8 -> 2 + 4 + 8 = 14 умножителей, хотя (правильно) 24 операции умножения. Изменено 18 сентября, 2013 пользователем Acvarif Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Sefo 0 18 сентября, 2013 Опубликовано 18 сентября, 2013 · Жалоба Ничего подобного. Возьмите восьмиточечный граф прореживания по частоте и просто наложите его на граф прореживания по времени. Они совпадут. Только накладывать нужно с поворотом на 180 град. Ладошка к ладошке. Стрелки в графе поверните в обратную сторону. Неужели это не заметно? Это же очевидно. В случае БПФ с прореживанием по времени можно 8ми точечный выполнить последовательно выполняя 4 двухточечных, затем последовательно (не параллельно) 2 четырехточечных (вернее две половинки второй стадии) и только на последнем этапе 3_ю стадию восьмиточечного. Похоже и с 16 точками и с 32. Входные данные для каждой операции нужно мультиплексировать, а выходные сохранять в буфере для последующего мультиплексирования на очередную стадию. Я считаю, что инженер в своей работе должен опираться на фундаментальные вещи, такие как, например, математика и физика. Дискретное преобразование Фурье это вполне конкретная (и довольно компактная) формула. Она может быть вычислена множеством способов. В свою очередь, каждый способ вычислений может иметь множество реализаций. Графические схемы быстрого преобразования Фурье, которые Вы приводите, наглядным образом иллюстрируют различные способы вычислений. Графические элементы в этих схемах обозначают совершенно конкретные математические операции. Их взаимное расположение и связи между ними иллюстрируют порядок выполнения этих операций. Каждая такая схема может быть записана в виде математического выражения (пусть и довольно громоздкого). Выполнив, как любят говорить математики, "несложные преобразования" Вы неизбежно получите исходную формулу дискретного преобразования Фурье. Поэтому, каждое действие над схемой эквивалентно выполнению некоего математического преобразования/действия. Скажите, пожалуйста: 1) какое математическое преобразование или действие соответствует повороту графа на 180 градусов ? 2) что за оператор такой "Ладошка к ладошке" ? 3) какие изменения нужно внести в формулу, чтобы на соответствующем ей графе это было бы эквивалентно развороту стрелки в обратном направлении ? Прошу дать обоснованные ответы. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Golikov 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба не туда вы заехали.... лучше скажите БПФ8 и 4 параллельные бабочки 2 в 2 - это одно и тоже или нет? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
acvarif 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба 1) какое математическое преобразование или действие соответствует повороту графа на 180 градусов ? 2) что за оператор такой "Ладошка к ладошке" ? 3) какие изменения нужно внести в формулу, чтобы на соответствующем ей графе это было бы эквивалентно развороту стрелки в обратном направлении ? Прошу дать обоснованные ответы. Формула везде одна и та же, вот эта А способы реализации свертки, тоесть собственно формулы разные. А то, что граф прореживания по времени это граф прореживания по частоте выполненный в обратном направлении это очевидно. Вот еще один способ, который используется во многих современных корках fft лучше скажите БПФ8 и 4 параллельные бабочки 2 в 2 - это одно и тоже или нет? Нет не одно и то же. Это только первая стадия. Нужны еще две стадии согласно графу и формуле. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Golikov 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба строго говоря свертка - это сумма почленных произведений сигналов со сдвигом... и преобразование фурье не свертка, оно просто часто используется при расчете свертки, так как фурье от свертки равно произведению двух фурье от сигналов, но это нюансы... Меня теперь волнует вопрос что же такое БПФ8 в терминологии того что делается выше. если брать бабочку 2 в 2, то обработка 8 точек требует 3 стадии. Если брать БПФ8 делает ли оно все в 1 стадию? бабочка 2 в 2, при обработке массива из 4 элементов требует 2 стадии БПФ8 для обработки 64 элементов также сделает все в 2 стадии если надо обработать 16 элементов, то как быть в случае БПФ8? правомерно ли на следующих стадиях пименять бабочки 2 в 2 и так далее? Можно ли смешивать бабочки? Может кто растолковать на пальцах? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
acvarif 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 (изменено) · Жалоба строго говоря свертка - это сумма почленных произведений сигналов со сдвигом... и преобразование фурье не свертка, оно просто часто используется при расчете свертки, так как фурье от свертки равно произведению двух фурье от сигналов, но это нюансы... Меня теперь волнует вопрос что же такое БПФ8 в терминологии того что делается выше. если брать бабочку 2 в 2, то обработка 8 точек требует 3 стадии. Если брать БПФ8 делает ли оно все в 1 стадию? бабочка 2 в 2, при обработке массива из 4 элементов требует 2 стадии БПФ8 для обработки 64 элементов также сделает все в 2 стадии если надо обработать 16 элементов, то как быть в случае БПФ8? правомерно ли на следующих стадиях пименять бабочки 2 в 2 и так далее? Можно ли смешивать бабочки? Может кто растолковать на пальцах? Посмотрите внимательно на этот граф Там везде бабочки 2 в 2. Давайте по порядку. Допустим у Вас имеются в наличии восемь выборок (у меня именно такая ситуация - все выборки я имею сразу одновременно, только 32 штуки). Чтобы уменьшить количество умножителей (не умножений) Вы вполне законно можете поступить так: 1. Выполняете бабочку с данными x(0), x(4) - получаете данные st1(0), st1(1) для второй стадии. 2. Выполняете опять бабочку 2 в 2 на том же самом схемном компоненте но с входными данными x(2), x(6) - получаете данные st1(2), st1(3) для той же второй стадии И так далее. Все то же самое можно проделать по всему графу вплоть до последней стадии используя всего 2 умножителя. Но время выполнения всего БПФ8 при этом растянется на количество операций. Изменено 19 сентября, 2013 пользователем Acvarif Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Golikov 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба а ну все понятно... чуда не произошло... я просто думал что может есть какая-то магическая "бабочка" которая за раз 8 точек обрабатывает, типа бабочки 2 в 2, но 8 в 8... а это всего лишь просто обработка 8 точек... то есть 3 стадии бабочек, запрятанных в 1 модуль... ну тогда все понятно. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Sefo 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба бабочка 8 в 8 Любопытно, где Вы нашли такой термин? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
acvarif 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 (изменено) · Жалоба а ну все понятно... чуда не произошло... я просто думал что может есть какая-то магическая "бабочка" которая за раз 8 точек обрабатывает, типа бабочки 2 в 2, но 8 в 8... а это всего лишь просто обработка 8 точек... то есть 3 стадии бабочек, запрятанных в 1 модуль... ну тогда все понятно. Когда у Вас стоит задача БПФ32 то Вы также вполне законно можете выполнить последовательно 4 раза полный БПФ8 на одной и той же схеме подготовив твким образом данные для 4_й стадии БПФ32. Ну и так далее. Если в запасе имеется нужное время то таким образом можно существенно сэкономить ресурсы ПЛИС. Что я собственно и предлагаю для реализации БПФ32, поскольку БПФ8 уже выполнен и проверен. Хотя всякие там корки обычно делаются по формуле типа Кроме того БПФ8 там выполняется по алгоритму Винограда - меньше ресурсов. Сам вначале был нацелен на это, но пока до конца не понимаю технику выполнения операций с матрицами. Хотя первый этап (БПФ8) уже имеется. В моем случае формула выглядит так 3 mr ms 7 sl X(k) = X(8r+s) = ∑ W4 W32 ∑ x(4l + m) W8 r = 0 to 8, s = 0 to 4 m=0 l=0 Изменено 19 сентября, 2013 пользователем Acvarif Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Golikov 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба Любопытно, где Вы нашли такой термин? да собственно сам придумал, я как бы пытался подобрать слова чтобы выяснить есть отдельный элемент 8 в 8, или это каскад 2 в 2, выяснил - каскад... выполняется по алгоритму Винограда - меньше ресурсов. что за алгоритм? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Sefo 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба да собственно сам придумал, я как бы пытался подобрать слова чтобы выяснить есть отдельный элемент 8 в 8, или это каскад 2 в 2, выяснил - каскад... Необязательно, это может быть и не каскад вовсе. Интересно, а общеупотребительное "8-ми точечная бабочка" или БПФ-8 чем Вас не устроили? Ведь насколько мне известно бабочки 8 в 7 или 2 в 3 нет. У Вас тут обсуждение количества умножений было, так вот, для справки, для вычисления 8-ми точечной бабочки нужно выполнить всего 2 комплексных умножения. Если считать такую бабочку за 1 такт, то в ПЛИС на 1 комплексный умножитель потребуется 4 вещественных умножителя. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
acvarif 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба что за алгоритм? Страница 135 nussbaymerG.zip Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Golikov 0 19 сентября, 2013 Опубликовано 19 сентября, 2013 · Жалоба Необязательно, это может быть и не каскад вовсе. Интересно, а общеупотребительное "8-ми точечная бабочка" или БПФ-8 чем Вас не устроили? Ведь насколько мне известно бабочки 8 в 7 или 2 в 3 нет. У Вас тут обсуждение количества умножений было, так вот, для справки, для вычисления 8-ми точечной бабочки нужно выполнить всего 2 комплексных умножения. Если считать такую бабочку за 1 такт, то в ПЛИС на 1 комплексный умножитель потребуется 4 вещественных умножителя. Я как раз и пытался понять это просто БПФ-8, то есть преобразование 8 точек или это какой то атомарный модуль типа бабочки 2 в 2, что применяется всегда... для меня откровение что надо всего 2 умножения, пускай даже комплексных... как так? Страница 135 nussbaymerG.zip чет сразу не нашел на 135 странице ничего про виноград... на досуге поразбираюсь, книжеца интересная спасибо... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
