Details

Цель работы: снижение сложности вычисления свёртки сверхдлинных сигналов и уменьшение затрат памяти. Перечень подлежащих разработке вопросов: 1. Провести обзор существующих алгоритмов «быстрой свертки» и оценка их сложности; 2. Разработка алгоритма «быстрой свертки» двух длинных сигналов; 3. Снижение количества требуемой памяти при реализации «быстрой свертки». Работа проведена на базе лаборатории высшей школы прикладной физики и космических технологий СПбПУ, где были произведены основные расчеты сложности операций, оценка затрат памяти алгоритмов. Были проведены расчеты, анализ. Использовались метод аналитического расчёта вычислительной сложности, алгоритмы на основе БПФ radix-2, метод перекрытия с накоплением. В результате был получен, алгоритм, снижающий вычислительную сложность относительно «медленных» методов свёртки и требования к памяти относительно «быстрого» метода свёртки, что может быть использован в системах, имеющих ограничения памяти, например, платы с FPGA.

The purpose of the work: reducing the complexity of computing the convolution of very long signals and reducing memory costs. The list of issues to be developed: 1. To review existing "fast convolution" algorithms and assess their complexity; 2. To develop a "fast convolution" algorithm for long signals; 3. To reduce the amount of memory required when implementing "fast convolution". The work was carried out on the basis of the laboratory of the Higher School of Applied Physics and Space Technologies of SPbPU, where the main calculations of the complexity of operations, assessment of the memory costs of the algorithms were made. Calculations and analysis were carried out. The method of analytical calculation of computational complexity, algorithms based on the radix-2 FFT, and the overlapping method with accumulation were used. The result was an algorithm that reduces the computational complexity relative to the "slow" convolution methods and the memory requirements relative to the "fast" convolution method, which can be used in systems with memory limitations, such as FPGA boards.