Источник: MIT
Источник: MIT

Исследователи из Массачусетского технологического института разработали алгоритм быстрого вычисления дискретного преобразования Фурье, на определенных задачах работающего в десять раз быстрее классического варианта, созданного еще в 60-х годах. ДПФ — один из столпов цифровой обработки сигналов: например, он применяется в алгоритмах компрессии изображений JPEG и звука MP3. Принцип действия ДПФ — преобразование цифрового сигнала, как набора дискретных значений частот, во взвешенную сумму этих значений. При этом часть частот считаются незначимыми и отбрасываются. Сигналы, содержащие относительно малое число значимых частот, исследователи называют «разреженными» (sparse). Именно на выявлении таких сигналов основан принцип действия нового алгоритма. Чем разреженнее сигнал, тем быстрее работает новый алгоритм.