Открыть список
Как стать автором
Обновить
  • по релевантности
  • по времени
  • по рейтингу

Тестируем свежеиспечёные SSE модификации FFT/MDCT

Чулан
Написал для своего детища SSE-реализацию комплексного FFT и MDCT. Результаты поразили даже меня:
преобразование/вариант без SSE SSE-модификация
2000000 * FFT-128 16,7с 13,3с 5,1с 3,7с
1000000 * MDCT-512 17,4с 15,3с 10,4с


Вычислялось два миллиона 128-точечных комплексных FFT и один миллион 512-точечных MDCT. Процессор Intel® Core(TM)2 Duo CPU E8400 @ 3.00GHz

Интересно можно ли это кому-нибудь продать или лицензировать? :)
Всего голосов 6: ↑4 и ↓2 +2
Просмотры415
Комментарии 4

MATLAB и быстрое преобразование Фурье

АлгоритмыMatlab
Из песочницы
По работе неоднократно сталкивался с необходимостью быстро определить наличие в сигнале гармонических составляющих. Часто для примерной оценки достаточно воспользоваться алгоритмом быстрого преобразования Фурье. Тем более, что его реализации есть практически во всех математических пакетах и библиотеках, да и собственноручно реализовать не составит особого труда. Между тем, опыт показывает, что, при всей своей простоте, метод начинает вызывать некоторые вопросы, когда возникает необходимость не просто посмотреть наличие дискреток в сигнале, но и выяснить их абсолютные значения, т.е. нормализовать полученный результат.

В этой статье я постараюсь объяснить, что же все-таки выдает в качестве результата fft (Fast Fourier transform) на примере MATLAB (и в качестве бонуса проведу небольшой ликбез по этому весьма полезному, на мой взгляд, языку).
Читать дальше →
Всего голосов 41: ↑33 и ↓8 +25
Просмотры198.6K
Комментарии 52

Быстрое умножение многочленов при помощи преобразования Фурье — это просто

Алгоритмы
Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Читать дальше →
Всего голосов 112: ↑105 и ↓7 +98
Просмотры66K
Комментарии 38

Почему в WiMax и LTE используют OFDM

АлгоритмыБеспроводные технологииСтандарты связиСотовая связь
Tutorial


Аббревиатура OFDM расшифровывается как Orthogonal frequency-division multiplexing. В русскоязычной литературе встречается несколько различных переводов, несущих, в принципе, один смысл: OFDM — это механизм мультиплексирования (уплотнения) посредством ортогональных поднесущих.



В статье описаны плюсы и минусы механизма OFDM. Рассмотрен принцип функционирования с физико-математической позиции. Статья содержит вводное описание радиофизических терминов, необходимых для понимания материала широкому кругу читателей.





Иллюстраций: 18, символов: 27 399, строк кода: 99.



Читать дальше →
Всего голосов 273: ↑269 и ↓4 +265
Просмотры106.8K
Комментарии 61

Новый алгоритм MIT в десятки раз ускоряет быстрое преобразование Фурье

Алгоритмы


На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.
Читать дальше →
Всего голосов 94: ↑65 и ↓29 +36
Просмотры20.3K
Комментарии 34

История реверс-инжиниринга одного пушистого зверька

Звук


Тихим утром третьего января, когда Москва уже дремала после новогодних праздников, в нашей квартире раздался звонок в дверь. Почта наконец-то доставила посылку с новогодними подарками, заказанными на Амазоне. Среди прочего в ней находился и подарок для сына — электронный питомец Furby. Покупка его была, в общем-то импульсной. Игрушка значилась в бестселлерах новогоднего сезона и стоила относительно недорого. В сортах Furby я не разбирался, но когда-то давно что-то позитивное об игрушке слышал.

Сынишку, в силу его годовалого возраста, подарок не сильно впечатлил, а позволять бросать сложное электронное устройство на пол и отрывать этому устройству уши мне было жалко, и все шло к тому, чтобы убрать подарок на полку до лучших времен, однако мой взгляд пал на одну надпись на красочной упаковке…
Читать дальше →
Всего голосов 321: ↑315 и ↓6 +309
Просмотры144.2K
Комментарии 82

Игра Жизнь и преобразование Фурье

Ненормальное программированиеПрограммированиеМатематика
Многие слышали о великом и ужасном быстром преобразовании Фурье (БПФ / FFT — fast fourier transform) — но как его можно применять для решения практических задач за исключением JPEG/MPEG сжатия и разложения звука по частотам (эквалайзеры и проч.) — зачастую остается неясным вопросом.

Недавно я наткнулся на интересную реализацию игры «Жизнь» Конвея, использующую быстрое преобразование Фурье — и надеюсь, оно поможет вам понять применимость этого алгоритма в весьма неожиданных местах.
Читать дальше →
Всего голосов 79: ↑71 и ↓8 +63
Просмотры60.2K
Комментарии 76

Идентификация быстрых термических процессов

Open sourceМатематика
Недавно мне удалось завершить часть работы по очень интересному проекту в ФТИ им. Иоффе и получить достаточное количество экспериментальных данных, для того чтобы поделиться с Вами.
Физики из СПб ФТИ им. Иоффе занимаются выращиванием нитрид галлиевых полупроводниковых структур, которые обладают неплохими показателями скорости носителей заряда при переходе и большим коэффициентом теплопроводности. Процесс роста такой структуры проходит при температуре 1000 С (1273 К) и атмосферном давлении. Все происходит в специальной камере, находящейся в герметичной зоне. При выращивании структуры весь объем реактора и герметичной зоны заполняется азотом. В процессе роста структуры подложкодержатель вращается с частотой один раз в секунду. Такие операции относятся к быстрым термическим процессам, скорость изменения температуры в которых варьируется от нескольких единиц до сотен градусов в секунду.

Моей задачей было управление температурой графитового подложкодержателя при помощи индуктивного нагрева.
Технические характеристики установки выглядят следующим образом. Для измерения температуры используется лазерный пирометр, снимающий данные в центре графита. Частота съема информации 10 раз в секунду, шаг измерения 1 градус. Значение мощности передаваемой графиту полагается прямо пропорциональным мощности на индукторе. У генератора управляющего индуктором имеется цифровой выход, по которому передаются значения напряжения, тока и мощности.
Результаты экспериментального отжига
Всего голосов 60: ↑56 и ↓4 +52
Просмотры19.4K
Комментарии 20

Преобразование Фурье в действии: точное определение частоты сигнала и выделение нот

Разработка веб-сайтовПрограммирование
Из песочницы
последняя редакция статьи доступна на сайте makeloft.xyz

Начнём с пианино. Очень упрощёно этот музыкальный инструмент представляет собой набор белых и чёрных клавиш, при нажатии на каждую из которых извлекается определённый звук заранее заданной частоты от низкого до высокого. Конечно, каждый клавишный инструмент имеет свою уникальную тембральную окраску звучания, благодаря которой мы можем отличить, например, аккордеон от фортепиано, но если грубо обобщить, то каждая клавиша представляет собой просто генератор синусоидальных акустических волн определённой частоты.

Когда музыкант играет композицию, то он поочерёдно или одновременно зажимает и отпускает клавиши, в результате чего несколько синусоидальных сигналов накладываются друг на друга образуя рисунок. Именно этот рисунок воспринимается нами как мелодия, благодаря чему мы без труда узнаём одно произведение, исполняемое на различных инструментах в разных жанрах или даже непрофессионально напеваемое человеком.

image

Читать дальше →
Всего голосов 74: ↑72 и ↓2 +70
Просмотры203.1K
Комментарии 47

Самодельный Фурье-спектрометр

DIY или Сделай самЭлектроника для начинающих
image Однажды я прочитал в Википедии статью про Фурье-спектрометр, и мне захотелось самостоятельно сделать такой. Эта задача совсем не простая, но действующий макет спектрометра все же удалось сделать. Сразу предупрежу — это не инфракрасный спектрометр, так что особенно интересных измерений им не провести.

О том, как же работает Фурье-спектрометр, и как его можно сделать в домашних условиях — далее (осторожно, много картинок!).
Читать дальше →
Всего голосов 63: ↑63 и ↓0 +63
Просмотры49.9K
Комментарии 39

Аудиокодек своими руками — это просто

Разработка веб-сайтовПрограммирование
Tutorial
актуальная редакция статьи на сайте Makeloft

Думаю, что для многих людей аудиокомпрессия с потерями напоминает магический чёрный ящик, где удивительно сложным образом с применением математической алхимии ужимаются данные за счёт утраты избыточной информации, плохоразличимой или неслышимой ухом человека, и, как следствие, некоторого снижения качества записи. Однако сразу оценить существенность таких потерь и понять их суть не очень-то просто. Но сегодня мы постараемся выяснить, в чём же там дело и благодаря чему вообще возможен подобный процесс сжатия данных в десятки раз

Пора снять завесу, отворить дверцу и воочию взглянуть на таинственный алгоритм будоражащий умы и сердца, добро пожаловать на сеанс с разоблачением!


Читать дальше →
Всего голосов 29: ↑26 и ↓3 +23
Просмотры30.7K
Комментарии 28

Ограниченность преобразования Фурье или почему стоит доверять своему слуху

Алгоритмы
Из песочницы
Последние несколько десятков лет задача распознавания аккордов музыкальной композиции ставилась довольно часто. Казалось бы, этот не столь оригинальный сервис был и остается довольно распространенным среди приложений, работающих со звуком (Ableton, Guitar Pro), однако универсального, срабатывающего всегда алгоритма не существует до сих пор. В этой статье я постараюсь раскрыть одну из множества причин неидеальной работы подобных сервисов на примере алгоритмов, использующих в своей основе преобразование Фурье.

Большинство аудиоформатов хранит информацию в виде зависимости амплитуды от времени (например, .wav) или в виде коэффициентов частотного преобразования (.mp3, .aac, .ogg), однако современные сложные алгоритмы цифровой обработки сигналов работают с частотной составляющей звуков. Приходится иметь дело с двойным переходом, из амплитудной области в частотную, затем обратно. На данный момент осуществление такого переход без потерь в качестве является достаточно распространенной проблемой с множеством неоднозначных решений.
Читать дальше →
Всего голосов 18: ↑13 и ↓5 +8
Просмотры13.9K
Комментарии 12

Как использовать IPP FIR фильтры в приложениях максимально эффективно

Блог компании IntelВысокая производительностьПрограммированиеПараллельное программирование
В библиотеке Intel Performance Primitives (IPP), начиная с версии 8.2, планомерно осуществляется переход от внутреннего распараллеливания функций к внешнему. Причины такого решения изложены в статье Функции IPP c поддержкой бордюров для обработки изображений в нескольких потоках.

В этом посте будут рассмотрены функции, реализующие фильтр с конечным откликом — FIR фильтр (Finite Impulse Response).
Читать дальше →
Всего голосов 8: ↑8 и ↓0 +8
Просмотры5.6K
Комментарии 0

Функции шума и генерирование карт

Разработка игрАлгоритмы
Перевод


Когда я изучал обработку аудиосигналов, мой мозг начал проводить аналогии с процедурным генерированием карт. В статье излагаются принципы, связывающие обработку сигналов с генерированием карт. Не думаю, что открыл что-то новое, но некоторые выводы были для меня в новинку, поэтому я решил записать их и поделиться с читателями. Я рассматриваю только простые темы (частоту, амплитуду, цвета шума, использование шума) и не затрагиваю другие темы (дискретные и непрерывные функции, фильтры FIR/IIR, быстрое преобразование Фурье, комплексные числа). Математика статьи в основном связана с синусоидами.

Эта статья посвящена концепциям, начиная с самых простейших и заканчивая более сложными. Если вы хотите перейти сразу к генерированию рельефа с помощью функций шума, то изучите другую мою статью.
Читать дальше →
Всего голосов 30: ↑30 и ↓0 +30
Просмотры23.9K
Комментарии 5

Реализация узла БПФ с плавающей точкой на ПЛИС

Open sourceАлгоритмыМатематикаFPGAПрограммирование микроконтроллеров
Всем привет! В этой статье речь пойдет о реализации быстрого преобразования Фурье в формате с плавающей точкой на ПЛИС. Будут показаны основные особенности разработки ядра от самой первой стадии до готового конфигурируемого IP-ядра. В частности, будет проведено сравнение с готовыми ядрами фирмы Xilinx, показаны преимущества и недостатки тех или иных вариантов реализации. В статье будет рассказано о главной особенности ядра БПФ и ОБПФ — об отсутствии необходимости переводить данные в натуральный порядок после БПФ и ОБПФ для их совместной связки. В этой статье я постараюсь отразить всё тонкости реализации проекта под названием FP23FFTK, приведу реальные примеры использования готового ядра. Проект написан на языке VHDL и заточен под FPGA фирмы Xilinx последних семейств.


Читать дальше →
Всего голосов 43: ↑42 и ↓1 +41
Просмотры24.5K
Комментарии 5

Достижение максимальной производительности Быстрого Преобразования Фурье на основе управления данными

Высокая производительностьC++CПараллельное программированиеПрототипирование
Из песочницы
Recovery mode
Статья поддерживается здесь:
[3] Caterpillar Implementation Based on Generated Code

// не вижу смысла писать на ресурсе а) с цензурой тэгов б) где каждый проходящий бот, набравший рейтинг галиматьей, сносит твой рейтинг и объяснение причины с него не требуется
Всего голосов 23: ↑22 и ↓1 +21
Просмотры16.9K
Комментарии 15

Измерим гармонию — анализатор звукового спектра на STM32L4 Discovery

ГаджетыНосимая электроникаDIY или Сделай сам
В предыдущей публикации мы подключали дешевый китайский LCD экран к плате STM32L4 Discovery. Теперь мы попробуем реализовать на этой комбинации что-то выходящее за рамки традиционного моргания светодиодом, а именно анализатор звукового спектра, который использует имеющийся на плате микрофон. Заодно я расскажу, как пользоваться операционной системой FreeRTOS, и зачем она нужна, а также почему в нотной октаве 12 нот, и чем 53 ноты лучше, чем 12.



Читать дальше →
Всего голосов 17: ↑17 и ↓0 +17
Просмотры14K
Комментарии 14

Взгляд пешехода-математика: почему наши дороги — «гуано»

ФизикаТранспортУрбанизм
В этой заметке я не собираюсь причитать как старая бабка «всё разворовали, упыри!!», потому что не интересуюсь кто это делает и делает ли. Не интересует меня и излюбленная темка автомобилистов «задолбали эти ямки и колдобинки!», лично мне не на чем их объезжать: в вопросах выбора транспортных средств я предпочитаю ретранслировать мнение Андрея Рубанова из его книги «Йод» (э маст хэв ящитаю), в мирное же время есть велосипед и автобус. У меня нет и претензий к нашим ремонтным службам, кладущим, как о том пишут в этих ваших интернетиках, битумную смесь на дождик и снежок вопреки мнению этих самых интернетов. Я простой пешеход, и пока ещё меня устраивает сложившееся положение вещей.

Кстати, я и не математик вовсе, а всего-то студент а-ля математик-прикладник. Если кто не в курсе, это такие чуваки и чувихи (да простит меня офисный планктон), по долгу своих профессий вынужденные перерабатывать в алгоритмы математические формулы именитых и широко известных в узких кругах теоретиков. Эти наколенкеписаные алгоритмы в свою очередь работают сначала в прикладных исследованиях, а затем идут в прикладной софт, если вдруг по велению судьбы рынок возжелает закупить наработки математика-прикладника, погрязшего по уши в фортрано-матлабо-пропитоненных сорцах.

Так исторически повелось, что на студенческой скамье мне пришлось периодически решать задачи, за которые никакой другой более обеспеченный и, надо полагать, более разумный хомосапиенс не брался. И вот, по долгу своей студенческой стези познакомили меня с одной задачкой из области дорожно-строительных конструкций. Тема была «бесперспективняк». «О, чёт новенькое», — подумал я, и взялся за решение чисто в обмен на получение практических скиллов, бесплатно. Итоги работы меня немного удивили. Но обо всём по порядку, должным для гиктаймс стилем «научпоп для уставших за день сисадминов и начинающих лысеть погромиздов» ;)
Читать дальше →
Всего голосов 88: ↑66 и ↓22 +44
Просмотры39.3K
Комментарии 186

AdBlock для радио

Звук
Перевод
Автор статьи — польский программист Томек Рекавек, разрабатывает проект Jackrabbit Oak в рамках Apache Software Foundation для Adobe. Статья опубликована в личном блоге автора 24 февраля 2016 года.

Польское «Радио-3» (так называемая «Тройка») знаменито хорошей музыкой и интеллигентными ведущими. С другой стороны, оно страдает наличием громких и раздражающих рекламных блоков в трансляции, где обычно рекламируется какая-нибудь электроника или лекарство. Я слушаю «Тройку» почти постоянно на работе и дома, поэтому задался вопросом: как удалить рекламу? Кажется, мне удалось найти решение.

Цифровая обработка сигналов


Моя цель — создать приложение, которое приглушает рекламу. Коммерческий блок начинается и заканчивается джинглами, поэтому программа должна распознать эти конкретные звуки и выключить звук между ними.

Знаю, что данная область математики/информатики называется цифровой обработкой сигналов, но мне DSP всегда казалась магией. Что ж, отличная возможность узнать что-то новое. Я провёл день или два, пытаясь выяснить, какой механизм использовать для анализа аудиопотока. И в конце концов нашёл то что надо: это взаимная корреляция или кросс-корреляция (cross-correlation).
Читать дальше →
Всего голосов 45: ↑45 и ↓0 +45
Просмотры16.8K
Комментарии 61

Реализация целочисленного БПФ на ПЛИС

АлгоритмыМатематикаFPGAПрограммирование микроконтроллеров
Всем привет!

Однажды меня спросили заказчики, нет ли у меня в проектах целочисленного БПФ, на что я всегда отвечал, что это уже сделано другими в виде готовых, хоть и кривых, но бесплатных IP-ядер (Altera / Xilinx) – берите и пользуйтесь. Однако, эти ядра не оптимальны, обладают набором «особенностей» и требуют дальнейшей доработки. В связи с чем, уйдя в очередной плановый отпуск, который не хотелось провести бездарно, я занялся реализацией конфигурируемого ядра целочисленного БПФ.


КДПВ (процесс отдладки ошибки переполнения данных)

В статье я хочу рассказать, какими способами и средствами реализуются математические операции при вычислении быстрого преобразования Фурье в целочисленном формате на современных кристаллах ПЛИС. Основу любого БПФ представляет узел, который носит название «бабочка». В бабочке реализуются математические действия – сложение, умножение и вычитание. Именно о реализации «бабочки» и её законченных узлов будет идти рассказ в первую очередь. За основу взяты современные семейства ПЛИС фирмы Xilinx – это серия Ultrascale и Ultrascale+, а также затрагиваются старшие серии 6- (Virtex) и 7- (Artix, Kintex, Virtex). Более старшие серии в современных проектах – не представляют интереса в 2018 году. Цель статьи – раскрыть особенности реализации кастомных ядер цифровой обработки сигналов на примере БПФ.
Читать дальше →
Всего голосов 55: ↑55 и ↓0 +55
Просмотры16.3K
Комментарии 29
1