Как стать автором
Обновить

26 терабит/с по оптоволокну одним лазером

Сетевые технологии *
В журнале Nature Photonics опубликовано описание новой технология передачи данных по оптоволокну на скорости до 26 Тбит/с вместо нынешних максимальных 1,6 Тбит/с.

Группа немецких инженеров под руководством профессора Вольфганга Фройде (Wolfgang Freude) из университета Карлсруэ применила в оптоволокне технику OFDM (ортогональное частотное разделение каналов с мультиплексированием), которая широко используется в беспроводной связи (802.11 и LTE), цифровом телевидении (DVB-T) и ADSL.

В оптоволокне использовать OFDM сложнее, ведь тут нужно разделить на поднесущие световой поток. Раньше единственным способом сделать это было использование отдельного лазера для каждой поднесущей.
Читать дальше →
Всего голосов 52: ↑45 и ↓7 +38
Просмотры 20K
Комментарии 50

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

Алгоритмы *


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

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

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

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

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

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

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

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

image

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

Спектральный анализ сигналов

Программирование *Алгоритмы *Математика *
Из песочницы
image

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

Под катом краткий обзор метода выделения гармоник из произвольного сигнала с помощью цифрового гетеродинирования, и немного особой, Фурье-магии.
Читать дальше →
Всего голосов 56: ↑52 и ↓4 +48
Просмотры 245K
Комментарии 22

Машинное обучение — 4: Скользящее среднее

Блог компании Нерепетитор.ру Математика *Машинное обучение *
Tutorial
Принято считать, что две базовые операции «машинного обучения» — это регрессия и классификация. Регрессия — это не только инструмент для выявления параметров зависимости y(x) между рядами данных x и y (чему я уже посвятил несколько статей), но и частный случай техники их сглаживания. В этом примере мы пойдем чуть дальше и рассмотрим, как можно проводить сглаживание, когда вид зависимости y(x) заранее неизвестен, а также, как можно отфильтровать данные, которые контролируются разными эффектами с существенно разными временными характеристиками.

Один из самых популярных алгоритмов сглаживания, применяемый, в частности, в биржевой торговле — это скользящее усреднение (включаю его в цикл статей по машинному обучению с некоторой натяжкой). Рассмотрим скользящее усреднение на примере колебаний курса доллара на протяжении нескольких последних недель (опять-таки в качестве инструмента исследования используя Mathcad). Сами расчеты лежат здесь.



Читать дальше →
Всего голосов 15: ↑12 и ↓3 +9
Просмотры 26K
Комментарии 13

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

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

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

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


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

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

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


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

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

Программирование *Математика *Программирование микроконтроллеров *
Из песочницы
Введение

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

Данный опус не претендует на полноту и связность изложения.
Читать дальше →
Всего голосов 30: ↑22 и ↓8 +14
Просмотры 44K
Комментарии 51

Применение преобразования Фурье для создания гитарного тюнера на Android. Часть 1

Java *Разработка мобильных приложений *Алгоритмы *
Из песочницы

В основе спектрального анализа звуковых данных лежит алгоритм, который носит название преобразование Фурье. При раскладывании исходного звукового сигнала на частотные составляющие, отдельные частоты называются гармониками. Основная гармоника определяет высоту звучания, а второстепенные гармоники определяют его тембр. Есть достаточно много мобильных приложений, которые используют преобразование Фурье для того, чтобы отобразить весь спектр частот (гармоник). Так же, есть мобильные приложения, которые служат для настройки гитар. Они работают по принципу: основная гармоника находится по самому высокому значению амплитуды в спектре. Такое утверждение не совсем верно, потому что основная гармоника определяется самой наименьшей из всех кратных этой гармонике, либо шагом между гармониками. Возникает необходимость найти способ, который позволит отобразить значение основной гармоники в спектре звукового сигнала.

В первой части статьи мы рассмотрим принцип работы дискретного преобразование Фурье, а также возможность записывать звуковые данные с Android устройства с помощью класса AudioRecord.
Читать дальше →
Всего голосов 14: ↑14 и ↓0 +14
Просмотры 12K
Комментарии 5

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

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

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

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

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

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

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

Пример расчета реакции сигнала с применением преобразования Фурье в среде МАТЛАБ

Алгоритмы *Математика *
При решении задач передачи данных через линии, представленные частотными характеристиками, применяются преобразования Фурье – перевод сигналов из временной области в частотную область и обратно. Среда МАТЛАБ имеет полный набор функций для решения подобных задач. В этой работе разобран пример вычисления в МАТЛАБ реакции сигнала прошедшего через линию, характеристика которой измерена на частотах, не совпадающих с частотой передачи данных. Надеюсь, что этот пример позволит легче разобраться с особенностями технологии преобразования сигналов в среде МАТЛАБ.

Условие задачи


Необходимо определить изменение формы двоичного цифрового сигнала проходящего через фильтр и сигнальную линию. Сигнал задан амплитудой и скоростью передачи. Фильтр второго порядка, нормированный относительно частоты передачи данных, задан постоянными времени. Передаточная функция сигнальной линии представлена измеренной частотной характеристикой в комплексной форме.

Среда, используемая для вычисления и отображения данных – MATLAB R2015а.
В качестве примера исходных данных взяты следующие отношения, опубликованные на сайте www.StatEye.org для версии метода StatEye 3.0 GUI [1, 2, 3].

Скорость передачи данных bps = 10,3125 Гбит/с. Постоянные времени нормированного фильтра второго порядка совпадают, их обратная величина составляет ¾ частоты передачи данных. Сигнальная линия представлена частотной характеристикой. Измерение характеристики выполнено на частотах channel.f = 0,006495:0,0012475:20 ГГц. Заданное число точек дискретизации преобразования Фурье: points = 2^13.
Читать дальше →
Всего голосов 13: ↑13 и ↓0 +13
Просмотры 9.3K
Комментарии 6

Моделирование водной поверхности с применением БПФ и DSP-процессора NeuroMatrix

Работа с 3D-графикой *Программирование микроконтроллеров *Процессоры
Уже давно известное быстрое преобразование Фурье используется не только для решения задач цифровой обработки сигналов, распознавания объектов на изображении, но и в компьютерной графике. Джерри Тессендорфом была описана математическая модель, позволяющая синтезировать океанские волны и анимировать их в реальном времени. В основе этой модели лежит двумерное БПФ.

Когда мне была поставлена задача разработать приложение для DSP-процессора, визуализирующее работу БПФ, я понял, что моделирование волн отлично подойдет для этой цели.

Всего голосов 23: ↑21 и ↓2 +19
Просмотры 4.8K
Комментарии 2

Проектирование оконных функций, суммирующихся в единицу с заданным уровнем перекрытия

Математика *Звук
Tutorial
Существует ряд задач, в которых длительный по времени сигнал разбивается на сегменты, каждый из которых обрабатывается по отдельности. В частности, такой подход используется для анализа сигнала с помощью оконного преобразования Фурье, или наоборот, при синтезе; а также при спектральной обработке типа удаления шума, изменения темпа, нелинейной фильтрации, сжатии аудиоданных и других.

Сам процесс разбиения математически представляется умножением на некоторую весовую (оконную) функцию со смещением. Для самого простого окна — прямоугольного — это может выглядеть так:

Исходный сигнал:



Разбиения:


Читать дальше →
Всего голосов 28: ↑27 и ↓1 +26
Просмотры 9.2K
Комментарии 21

Об авторегрессионном оценивании спектральной плотности стационарного сигнала

Data Mining *Алгоритмы *Математика *Matlab *
Методы спектрального оценивания стационарных случайных процессов, основанные на быстром преобразовании Фурье (БПФ), хорошо известны и широко применяются в инженерной практике. К их недостаткам следует отнести, в частности, высокую дисперсию (низкую точность) оценки при недостаточно длительном интервале наблюдения за процессом, что визуально обычно проявляется в сильной «изрезанности» графика спектральной плотности мощности(СПМ). Одним из альтернативных методов спектрального оценивания является авторегрессионный метод, рассмотренный на примере ниже, который в инженерной практике известен гораздо меньше. Метод во многих случаях позволяет сравнительно просто получить гораздо более качественную оценку СПМ (рис.1), а иногда и более глубокие сведения об исследуемом случайном процессе.

image
Рис.1 Классическая и авторегрессионная оценка СПМ «короткого» процесса
Читать дальше →
Всего голосов 26: ↑25 и ↓1 +24
Просмотры 6.4K
Комментарии 4

Как на GO решить задачку по распознаванию аудио

Блог компании BI.ZONE
Недавно BI.ZONE приняла участие в конференции HighLoad++. Понятное дело, что мы приехали туда не просто поглазеть на чужие стенды, а привезли кое-что интересное. Сотрудники из разных отделов компании приготовили для гостей конференции задачи, за решение которых мы предлагали призы. Одна из задач по Golang была посвящена распознаванию звука. Мы попросили ее автора рассказать о ней.

Постановка задачи


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

Загадки быстрого преобразования Фурье

Программирование *Алгоритмы *Математика *Звук Визуальное программирование *
Tutorial

• Метод фазово-амплитудной интерполяции (ФАИ)

• Точное определение частоты, амплитуды и фазы гармоник сигнала

• Выявление резонансов

Алгоритм быстрого преобразования Фурье (БПФ) - важный инструмент для анализа и обработки сигналов различной природы.

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

Хотя в процессе преобразования никакая информация о сигнале не утрачивается (вычисления обратимы до округлений) алгоритму присущи некоторые особенности, которые затрудняют высокоточный анализ и тонкую обработку результатов в дальнейшем.

В статье представлен действенный способ преодоления таких "неудобных" особенностей алгоритма.

Читать на английском

Читать на русском
Всего голосов 14: ↑13 и ↓1 +12
Просмотры 5.8K
Комментарии 93

10 лучших алгоритмов 20 века

Блог компании Timeweb Cloud Алгоритмы *Математика *История IT Научно-популярное
Перевод
Прим. Эта статья была опубликована в майском номере 2000 года журнала SIAM. На рубеже веков появилась «мода» на подведение итогов уходящего столетия. И алгоритмы этой участи не избежали. В этой статье авторы делают обзор 10 лучших алгоритмов 20 века. Возможно, вам будет интересно узнать, какие алгоритмы, по мнению авторов списка, внесли наибольший вклад в развитие науки.

Algos — греческое слово, означающее боль. Algor — латинское слово, означающее холод. Но ни то, ни другое не является корнем слова «алгоритм», которое происходит от имени Аль-Хорезми – арабского ученого девятого века – чья книга «al-jabr wa’l muqabalah» (Китаб аль-джебр ва-ль-мукабала) переросла современные учебники по алгебре для средней школы. Аль-Хорезми подчеркивал важность методических процедур для решения задач. Будь он сегодня здесь, то, несомненно, был бы впечатлен вершинами математического метода, названного в его честь.

Часть из лучших алгоритмов компьютерной эры были освещены в январско-февральском выпуске 2000 года журнала Computing in Science & Engineering — совместном издании Американского института физики и Компьютерного общества IEEE. Приглашенные редакторы Jack Dongarra (Джек Донгарра) из Университета Теннесси и Francis Sullivan (Фрэнсис Салливан) из Института оборонного анализа составили список из 10 алгоритмов, который они назвали «Top Ten Algorithms of the Century».

«Мы попытались собрать 10 алгоритмов, оказавших наибольшее влияние на развитие и практику науки и техники в 20 веке», — пишут Донгарра и Салливан. По признанию авторов, как и в любом рейтинге, их выборы неизбежно будут спорными. Когда дело доходит до выбора лучшего алгоритма, кажется, что он и вовсе не существует.

Итак, вот список 10 лучших алгоритмов в хронологическом порядке. (Все даты и имена стоит воспринимать как аппроксимацию первого порядка. Большинство алгоритмов формируются в течение времени при участии многих ученых).
Читать дальше →
Всего голосов 48: ↑47 и ↓1 +46
Просмотры 34K
Комментарии 44