Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования



Скачать 46.67 Kb.
Дата27.11.2012
Размер46.67 Kb.
ТипДокументы

СРАВНЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ ДЛЯ КРАТКОВРЕМЕННОГО СПЕКТРАЛЬНО-ВРЕМЕННОГО ПРЕОБРАЗОВАНИЯ

М.Б.Шалаева

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

E-mail: shalaeva@mail.ru


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

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

В результате анализа изменений отсчетов спектра были выведены общие формулы для получения каждого отсчета спектра на последующей итерации из значения соответствующего отсчета на предыдущей итерации для кратковременного дискретного преобразования Фурье (ДПФ):

, ,

где l – номер этапа вычисления кратковременного ДПФ при сдвиге окна на один отсчет;

и кратковременного дискретного преобразования Хартли (ДПХ):

, ;

, ;

, .

Поскольку при объединении общих формул для косинусной и синусной составляющих не удается избавиться от участия в вычислениях косинусной и синусной компонент:

,

то, следовательно, нужно вычислять косинусные и синусные составляющие на основе предыдущих значений отдельно, а затем полученные результаты суммировать.


Далее была рассчитана вычислительная сложность для следующих преобразований:

  • ДПФ;

  • ДПХ;

  • быстрого дискретного преобразования Фурье (БПФ);

  • быстрого дискретного преобразования Хартли (БПХ);

  • предложенных алгоритмов:

  • преобразования Хартли (ПХ) с использованием предыдущих значений спектра;

  • преобразования Фурье (ПФ), вычисленного из ПХ с использованием предыдущих значений спектра;

  • ПФ с использованием предыдущих значений спектра.

При этом было учтено следующее:

  • операции сложения и умножения представляют собой отдельные операции равносильные по сложности выполнения;

  • операция накопления реализуется посредством сложения;

  • повторяющиеся тригонометрические выражения в матрицах преобразования рассчитываются заранее и в вычислениях используются уже конкретные значения.



Преобразование

Количество базовых операций

Вычислительные затраты Q,

оп.умн./слож. ДЧ

ДПФ







ДПХ





БПФ по основанию 2





БПХ по основанию 2





ПФ с использованием предыдущих значений спектра

Второе и следующие окна:



Первое окно:



следующие окна:



ПФ, вычисленное из ПХ с использованием предыдущих значений спектра

Второе и следующие окна:



Первое окно:



следующие окна:



ПХ с использованием предыдущих значений спектра


Второе и следующие окна:



Первое окно:



следующие окна:



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



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

Кроме представленных математически рассчитанных вычислительных затрат, следует отметить, что в предложенных алгоритмах используются только указанные операции, тогда как в других представленных известных алгоритмах при реальном выполнении требуется дополнительное время на организацию перестановок элементов. И, хотя, первые этапы преобразования быстрых алгоритмов (как правило, 1 и 2) могут быть упрощены, за счет равенства нулю или единице определенных множителей, при достаточно большом N, а следовательно и log2N (т.е. количестве этапов), упрощения оказываются незначительными, а сложность и количество перестановок увеличиваются.

В результате расчетов получилось, что сложность ПФ с использованием предыдущих отсчетов меньше, чем при расчете ПФ через ПХ, но незначительно больше, чем при расчете ПХ предложенным способом. Хотя, следует отметить, что при применении ПФ происходит неэффективное использование памяти, примерно в 2 раза большее, чем при применении ПХ.

Таким образом, при условии невозможности замены алгоритма преобразования хотя бы на одном конце, следует применять преобразование Фурье с использованием предыдущих отсчетов спектра с получением традиционного результата преобразования.

Похожие:

Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconПрограмма: Специализированный программный комплекс «Факторизация»
Программа предназначена для автоматизации вычислений с полиномами, а также для проведения исследований в области вычислительной сложности...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconПрограмма по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура)
Эвм, вычислительной геометрии. Основным содержанием дисциплины является исследования и оценка сложности геометрических построений,...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconСложность алгоритмов. Уметь оценивать сложность всех алгоритмов и программ
Графы. Основные способы хранения графов, их преимущества и недостатки, количество необходимой памяти. Сложности алгоритмов над разными...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconБилет 10. Теория сложности вычислений
Теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconРасширенная алгебра алгоритмов
По­казаны возможности формального преобразования алгоритмов и построения производных алгоритми­ческих конструкций. Приведены примеры...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconСложность алгоритмов 1 Сравнение функций с точки зрения сложности. Введем понятие верхнего и нижнего порядка
Введем понятие верхнего и нижнего порядка одной функции относительно другой функции
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconТеория сложности вычислений
Разрешимые и перечислимые множества. Нумерации вычислимых функций. Модели вычислений. Примеры неразрешимых проблем. Сводимость одних...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconПриказ №01-07/2090 от 31. 08. 2011 года Об открытии групп кратковременного пребывания
В связи с потребностью населения и на основании Положения о группах кратковременного пребывания для детей, не посещающих дошкольные...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconПоложение о группе кратковременного пребывания «Играя, обучаюсь» для детей, не посещающих дошкольные образовательные учреждения
Компенсирующего вида №2098 четыре группы кратковременного пребывания ( далее гкп) для детей в возрасте от 1 года 6 месяцев до 3 лет...
Сравнение вычислительной сложности алгоритмов для кратковременного спектрально-временного преобразования iconМетодическое пособие Казань, 2009 г Данное методическое пособие предназначено для студентов, изучающих процесс разработки алгоритмов и программ для решения сложных задач по программированию
Тексты всех задач упрощены и исключены ограничения на память и время. Приведены идеи решения и примеры анализа нескольких конкретных...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org