Песочница
Материал из Модулярная арифметики
(Различия между версиями)
Turbo (обсуждение | вклад) |
Turbo (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
== Количество операций необходимых для вычисления линейной свертки == | == Количество операций необходимых для вычисления линейной свертки == | ||
| − | + | Пусть задан фильтр длины M и последовательность L и битность входных данных B. | |
| − | Пусть задан фильтр длины M и последовательность L и битность входных данных B. Для выполнения свертки в этом случае потребуется M*L операций умножения размерности B-бит и (M-1)*L операций сложения размерности 2*B-бит. | + | |
| + | === Свертка по обычной формуле === | ||
| + | По опеределению свертка вычисляется по формуле: <math>s(n)=\sum_{m=0}^{n}a(m)b(n-m), n=0...(L+M-2)</math> | ||
| + | |||
| + | Для выполнения свертки в этом случае потребуется M*L операций умножения размерности B-бит и (M-1)*L операций сложения размерности 2*B-бит. | ||
==== Пример ==== | ==== Пример ==== | ||
| Строка 17: | Строка 21: | ||
* Количество операций 16-битного сложения: 1047552 | * Количество операций 16-битного сложения: 1047552 | ||
* Количество операций 8-битного умножения: 1048576 | * Количество операций 8-битного умножения: 1048576 | ||
| + | |||
| + | === Свертка через БПФ по тригонометрическому базису === | ||
Версия 14:34, 22 июля 2013
Содержание |
Количество операций необходимых для вычисления воздействия FIR-фильтра
Пусть задан FIR-фильтр длины M и большая последовательность данных длины K. В этом случае можно разбить последовательность на несколько отрезков длины L и выполнить свертку по методу Overlap-Add или Overlap-Save. При этом метод выполнения свертки оказывается не важен. И количество операций будет пропорционально (K/L)*OPER - где OPER - оличество операций для метода, которым мы делаем линейную свертку.
Количество операций необходимых для вычисления линейной свертки
Пусть задан фильтр длины M и последовательность L и битность входных данных B.
Свертка по обычной формуле
По опеределению свертка вычисляется по формуле: 
Для выполнения свертки в этом случае потребуется M*L операций умножения размерности B-бит и (M-1)*L операций сложения размерности 2*B-бит.
Пример
M = 1024
L = 1024
B = 8 бит
- Количество операций 16-битного сложения: 1047552
- Количество операций 8-битного умножения: 1048576
