В поиске недорогих, широко доступных устройств для обработки аудио в реальном времени для научных и творческих задач платформа Arduino кажется удобной альтернативой специализированного аудиопроцессра. Несмотря на тот факт, что платы Arduino обычно используются для управления и сопряжения с другими устройствами, у них на борту имеются АЦП и ЦАП (10-битный, многоканальный ADC и несколько каналов ШИМ, позволяющих организовать DAC), так что можно с помощью микроконтроллера Arduino захватывать звуковые сигналы и производить их - конечно, с весьма специфическими ограничениями. В этой статье авторы (перевод [1]) анализируют архитектуру Arduino/AVR с целью понять, что можно сделать и какие есть ограничения платформы для работы с обработкой сигналов в реальном времени. Было оценено поведение некоторых общих алгоритмов DSP, и показаны ограничения и возможности использования платформы Arduino в этом контексте.

[Введение]

Именем Arduino назван аппаратный и программный проект, который стартовал в 2005 году. Целью этого проекта было упростить подключение различных электрических/электронных устройств к микроконтроллеру. Проект развивался от Processing software IDE 1 (2001) и Wiring software and hardware prototyping platform 2 (2003). Аппаратное, программное обеспечение и документация дизайна была опубликована под свободными лицензиями  (Creative Commons BYSA 2.5, GPL/LGPL и CC BY-SA 3.0, соответственно). Вокруг проекта разрослось большое сообщество, была накоплена богатая база кода и разработок, что благоприятно повлияло на привлечение и поддержку новых пользователей платформы. В настоящий момент доступно множество аппаратных устройств под брендом Arduino, от ограниченных по возможностям 8-битных микроконтроллеров AVR до полноценных 32-битных ARM CPU. Кроме того, есть и другие преимущества Arduino для академического и творческого использования - мобильность (поскольку не требуется мощный источник питания, так что можно питать устройство от батарей несколько часов, если не дней - в зависимости от варианта использования), расширяемость (поскольку был разработан стандартизованный интерфейс в виде так называемых аппаратных шилдов), и цена (фирменные устройства стоят порядка 20 долларов США, а китайские платы Arduino могут стоить около 1..2 доллара [6]).

Arduino Diecimila	Metaboard	Arduino Nano v3.0

Несмотря на все эти достоинства, платформа Arduino имеет определенные ограничения по производительности в сравнении со стандартными процессорами, доступными на рынке, как например процессоры DSP, такие как Blackfin 32-bit RISC компании Analog Device, и основанные на FPGA процессоры компании Xilinx семейства Virtex-7. В этой работе авторы стремились показать возможность платформ, основанных на Arduino, для задач обработки звука в реальном времени, чтобы можно было сделать более четкие предположения при выборе платформ для разработки. Примеры кода можно скачать на страничке IME/USP Computer Music Group webpage (http://compmus.ime.usp.br/en/arduino).

Arduino экспериментально использовался как процессор обработки звука в реальном времени - для оцифровки звука и сигналов управления с эффективной скоростью 15.125 кГц [2], что предоставило базовые параметры для исследований. Также аудиодрайвер ALSA был реализован на плате Arduino Duemilanove [3] для полнодуплексной монофонической 8-битной звуковой карты 44.1 кГц под управлением GNU/Linux.

[Возможности платформы AVR]

Чтобы с помощью процессора AVR, который применяется в самых распространенных платах Arduino, можно было обрабатывать и выводить звук, необходимо четко представлять возможности платформы. В этом исследовании использовался Arduino Duemilanove с микроконтроллером AVR ATmega328P компании Atmel, самая современная версия этой платформы. Это 8-битное RISC ядро, работающее на базовой частоте 16 МГц, с объемом памяти программ (FLASH) 32 килобайта и оперативной памятью 2 килобайта.

Тактирование. Сигналы тактирования предоставляются либо напрямую от генератора, либо частота генератора проходит через внутренний делитель частоты. Тактовые частоты обеспечивают работу CPU, ADC, узлов доступа к памяти и других компонентов и периферийных устройств микроконтроллера. Генератором тактовых сигналов может быть либо кварцевый генератор, либо RC-генератор. Из его частоты вырабатывается системная тактовая частота (system clock) и частота для тактирования подсистемы ввода/вывода (I/O clock). Последняя используется для тактирования ADC и тактирования различных периферийных устройств ввода/вывода. Для некоторых частей системы можно выбрать тактовую частоту, а также независимо задавать значения коэффициента прескалера (делитель, через который проходит частота генератора). В этой разработке авторы использовали прескалер тактовой частоты таймера для управления частотой формирования ШИМ (PWM) при выводе звука, как будет описано далее.

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

Таймеры/счетчики. Таймер, или счетчик, это регистр, который автоматически инкрементирует свое значение с определенной (программируемой) частотой. Когда счетчик при достигает своего максимального значения, он сбрасывается в 0, и сигнализирует об этом переполнении прерыванием (overflow interrupt), в обработчике которого может быть вызваны определенные функции обработки.

Таймеры важны в контексте DSP, потому что они предоставляют традиционный способ выполнить стандартные задачи DSP, как например периодический запуск функции оцифровки входного сигнала (что будет заполнять входной буфер данных), и вывод прямоугольного сигнала ШИМ (PWM), который после фильтра низкой частоты (ФНЧ, обычный интегратор) позволяет получить аналоговый сигнал. У микроконтроллера ATmega328P имеется два 8-битных счетчика и один 16-битный счетчик, и у каждого свой набор возможностей, но все они могут использоваться для генерации ШИМ.

Порты ввода/вывода (GPIO). Микроконтроллеры могут получать цифровые сигналы от внешнего мира и выводить наружу свои собственные сигналы через порты GPIO (General Purpose Input/Output), которые в случае плат Arduino удобно выведены на внешние контакты, что облегчает подключение различных других внешних компонентов и плат. Эти выводы контактов (порты) могут быть прочитаны (что соответствует вводу цифрового сигналов) и записаны (что соответствует выводу цифровых сигналов). Если порты привязаны к каналам входа встроенного в микроконтроллер ADC, то сигнал может быть введен в аналоговой форме (оцифрован) и преобразован в цифровую форму.

В принципе выводы портов микроконтроллера разработаны для работы с двоичными сигналами (лог. 0, лог. 1), представленными соответствующими уровнями напряжения (близкими к 0V и близкими к 5V, разделяемыми по пороговой величине примерно 2V с некоторыми девиациями). Несмотря на это, выводы GPIO оборудованы удобными механизмами для оцифровки ограниченных по уровню входных сигналов, и также позволяют генерировать сигналы разной формы с помощью ШИМ и выходного фильтра ФНЧ. Эти механизмы соответственно аналого-цифровой преобразователь (analog-to-digital converter, ADC) и модуль широтно-импульсной модуляции (pulse-width modulation, PWM), работа которых будет рассмотрена далее.

Память. У микроконтроллера есть 3 отдельных области памяти для сохранения программы и рабочих данных:

В памяти FLASH хранится программа и какие-либо константы, SRAM хранит изменяемые данные, используемые в вычислениях, и EEPROM используется как энергонезависимая перезаписываемая память для хранения каких-либо параметров между рабочими сессиями. Обратите внимание, что размер памяти SRAM задает жесткие ограничения на многие алгоритмы DSP. Например, таблица на 512 точек, заполненная заранее вычисленными значениями формы синусоидального сигнала, займет 25% всего доступного пространства. По этой причине может быть интересным хранить константы подобного рода в памяти программ всякий раз, когда есть нехватка оперативной памяти.

Ввод звука с помощью ADC. Данные могут поступать в микроконтроллер разными способами, и базовым методом для ввода оцифровок звука является использование встроенного ADC, подключенного к внешним выводам микроконтроллера. Также можно вводить звуковые данные через 1 разряд порта GPIO, настроенного как вход. Первый способ, с использованием ADC, позволяет более точно оцифровывать сигнал (аналоговый уровень сигнала напряжением от 0V до напряжения источника опорного напряжения может быть преобразован в цифровую форму с разрешением 8 или 10 бит) и помещать данные его выборки непосредственно в ячейки памяти. Второй способ может читать по одному биту в каждой выборке, представляя сигнал как 0 или 1 в зависимости от того, ниже ли выше уровень сигнала заданного порога (например, с использованием встроенного компаратора).

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

Встроенный в микроконтроллер ADC использует схему выборки и хранения, которая удерживает входное напряжение на постоянном уровне до окончания процесса преобразования сигнала в цифровую форму. ADC работает по принципу последовательного приближения, сравнивая опорные уровни напряжения с входным сигналом для получения оцифровки с точностью до 10 бит. Если требуется повышенная скорость преобразования, то можно пожертвовать точностью, читая только 8 бит оцифровки с отбрасыванием 2 младших бит преобразования. Время преобразования сигнала в цифровую форму занимает время от 13 до 250 мкс, в зависимости от нескольких параметров конфигурации, которые также влияют на точность результата.

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

Вывод звука с помощью ШИМ (PWM). Как только входной сигнал оцифрован и обработан, одним из способов преобразовать его в аналоговую форму будет использование встроенного в микроконтроллер блока формирования ШИМ (pulse-width modulation, PWM, широтно-импульсная модуляция). Этот блок может выводить ШИМ на некоторые выделенные выводы микроконтроллера, за которыми для сглаживания импульсов ШИМ должна стоять схема аналоговой фильтрации. Форма ШИМ кодирует нужную амплитуду сигнала с помощью соотношения длительностей импульсов лог. 0 и лог. 1 своего выхода. Соотношение длительности лог. 1 сигнала ШИМ к длительности его периода определяет выходной уровень - чем меньше это соотношение, тем меньше уровень, см. рис. 1a. Выходные импульсы ШИМ имеют в лог. 0 напряжение около 0V, в лог. 1 около 5V. Если принять за длительность импульса лог. 1 время T1, время периода за T, то уровень выходного сигнала ШИМ U_out, получаемого после фильтра, можно вычислить по формуле:

      5V * T1
U_out = -------
         T

Рис. 1a. Примеры формы сигнала ШИМ. Левое выравнивание импульсов соответствует режиму Fast PWM.

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

Рис. 1b. Как работает ШИМ в качестве цифро-аналогового преобразователя (DAC).

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

Блок PWM (ШИМ) может работать в различных режимах, которые определяют способ кодирования получаемой выходной величины в зависимости от значения счетчика и принципа его работы. В режиме Fast PWM выходной сигнал ШИМ устанавливается в лог. 1 в начале цикла, и становится лог. 0 всякий раз, когда опорная величина счета становится меньше, чем значение счетчика (см. рис. 2). У этого режима есть недостаток в том, что выходные импульсы выровнены по левому краю полного цикла ШИМ. Эта проблема устранена в режиме Phase correct ценой уменьшения в 2 раза выходной частоты модуляции ШИМ. Принцип режима корректной фазы основан на том, что счетчик считает поочередно то вверх, то вниз, вместо того, чтобы сбрасывается в исходное значение по достижению предела счета.

Рис. 2. Формирование выходных импульсов ШИМ в режиме Fast PWM. Обратите внимание, что изменение значения опорного порога счета меняет соотношение длительности выходного сигнала ШИМ.

Частота следования импульсов ШИМ зависит от выбранной тактовой частоты, которая приходит на вход счетчика блока PWM, коэффициента деления прескалера, разрядности счетчика в битах и выбранного режима PWM. Если принять за b разрядность счетчика, за F_clock частоту тактов, p коэффициент деления прескалера, то частота ШИМ может быть вычислена по формуле F_clock / (p*2^b). Это предоставляет нам способ вывода обработанного сигнала с использованием той же инфраструктуры планирования периодических действий, что применялись для опроса значений ADC, когда происходит событие готовности выборке сигнала к обработке.

Также обратите внимание, что размер диапазон счета счетчика определяет разрешающую способность DAC на основе ШИМ, так как изменение скважности формируемых импульсов ШИМ зависит от соотношения текущего значения счетчика и его максимального значения счета. Подробнее про выбор параметров PWM будет рассказано далее.

[Обработка сигнала в реальном времени]

Конечно, главное ограничение для DSP в реальном времени составляет доступное время для обработки выборок сигнала: они должны быть в готовности в момент, когда потребуются программе проигрывания, иначе в звучании будут наблюдаться щелчки и другие нежелательные артефакты. Один проход вычислений, состоящий из анализа выборки, её обработки и расчета значения новой выборки, называется циклом обработки выборки DSP. Многие алгоритмы, тем не менее, оперируют блоками выборок, потребляя на входе и поставляя на выходе блок выборок цифрового сигнала в каждом проходе. Если блок данных состоит из N выборок, и скорость следования выборок составляет R Герц, то период блока обработки DSP составит TDSP = N/R секунд.

Чтобы реализовать такой алгоритм в микроконтроллере, авторы нашли способ (1) накапливать выборки в буфере, (2) планировать периодические вызовы функции, которая обрабатывает выборки в этом буфере, и (3) выводить измененные выборки в определенное время. Применялись следующие внутренние узлы микроконтроллера: ADC для чтения входного сигнала, счетчики и их прерывания для запуска периодически выполняемых задач, и PWM для вывода полученного сигнала. Дополнительно библиотека Arduino предоставляет функцию loop(), которая повторно вызывается, и где авторы реализовали обработку блока данных, когда они становятся доступны.

Механизм PWM предоставляет прерывание с частотой переполнения счетчика, которое может использоваться для планирования запуска функции в периодические интервалы времени. В нашем проекте мы использовали этот механизм для периодического чтения выборок из ADC, и накапливания их в буфере, и при этом организовали запись обработанных выборок из последнего цикла DSP в выходной буфер PWM. В той же функции всякий раз, когда буфер полон и готов к обработке, устанавливается флаг, и функция loop() начинает обработку буфера.

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

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

Параметры ADC. Преобразование ADC занимает примерно 14.5 тактовых периодов ADC, включая время выборки-хранения. Если тактовая частота CPU равна 16 МГц, и прескалер ADC запрограммирован на коэффициент деления p, то период тактов ADC равен p/16 и период преобразования составляет T_conv = (14:5 * p)/16. Ниже в таблице можно увидеть теоретические значения периода преобразования T_conv для всех значений прескалера, и также результаты ~T_conv измеренного времени преобразования для каждого значения прескалера. Также в таблице показана реальная частота преобразования ~f_conv = 1/~T_conv.

Эти измерения были сделаны с использованием функции micros() из API библиотеки Arduino, у которой разрешающая способность составляет около 4 мкс. Это может объяснить тот факт, что имеются отличия измеренного значения от ожидаемого для нижних значений делителя частоты. Была использована 8-битная апроксимация, и для получения 10-бибной апроксимации мы можем ожидать издержки 25% во время преобразования.

Важно заметить, что выбор значения для прескалера ADC ограничивает скорость оцифровки входного сигнала. Поскольку наша реализация использовала прерывание переполнения счетчика для получения выборок от ADC, то период преобразования ADC может быть меньше, чем период цикла PWM. Любой выбор прескалера может привести к тому, что частота оцифровки окажется выше, чем частота циклов PWM, что допустимо, однако снижение значения prescaler снизит качество преобразования.

PWM. Как мы уже выяснили, частота ядра процессора 16 МГц, и 8-битный счетчик с значением прескалера p дает частоту прерывания f_overflow = 10⁶/(p * 2⁴) Гц. Ниже мы можем увидеть в таблице частоты переполнения для всех возможных значений прескалера:

Выбор значений для прескалеров PWM и ADC напрямую определяют частоту оцифровки нашей системы DSP. Если мы установим прескалер ADC так, чтобы период преобразования ADC был меньше, чем период переполнения счетчика PWM, и синхронизируем чтения из входа с записями на выход, то тогда для частотой оцифровки системы DSP станет частота прерываний по переполнения счетчика PWM.

Для подсистемы PWM авторы выбрали режим Fast PWM со значением 1 прескалера для 8-битного счетчика. Это дало частоту выборок 62500 Гц, что достаточно для представления звукового спектра. Тем не менее, если понадобится больше времени для вычислений, можно искусственно снизить частоту только выполнением выборки на входе / выводе выборки в некоторой части прерываний. Для тестов авторы выбрали снижение частоты оцифровки наполовину, чтобы получить больше времени для вычислений. Таким образом, конечный выбор частоты оцифровки остановился на частоте 31250 Гц, что соответствует периоду выборки 32 мкс.

Когда были выбраны значения для размера счетчика PWM и прескалера PWM, осталось только выбрать параметры ADC. Как уже упоминалось, достаточно выбрать такое значение, которое обеспечит период преобразования ADC меньше, чем необходимый период выборки системы. Было выбрано 8-битное преобразование, чтобы соответствовать разрешающей способности PWM, и уменьшить время преобразования. Также было выбрано значение 8 прескалера ADC, с измеренным временем преобразования 19.76 мкс, что в сравнении с периодом преобразования 32 мкс гарантирует, что преобразование завершится перед тем, как из ADC будет запрошена входная выборка.

Ниже показан код для обработчика прерывания (interrupt service routine, ISR) функции контроллера DSP. Переменная x это входной буфер, имя ADCH привязано к регистру ADC, удерживающему входную выборку оцифрованного сигнала, имя OCR2A соответствует регистру генерации выхода PWM и y это выходной буфер.

// Обработчик прерывания Timer2, запускающийся с частотой 62.5 кГц
ISR(TIMER2_OVF_vect)
{
   static boolean div = false;
   div = !div; // это делит частоту пополам до 31.25 кГц
   if (div)
   {
      // 1. Читаем входную выборку сигнала из ADC:
      x[ind] = ADCH;
      // 2. Записываем выходную выборку в блок PWM:
      OCR2A = y[(ind-MIN_DELAY)&(BUFFER_SIZE-1)];
      // 3. Проверка доступности нового блока выборок сигнала:
      if ((ind & (BLOCK_SIZE - 1)) == 0)
      {
         rind = (ind-BLOCK_SIZE) & (BUFFER_SIZE-1);
         dsp_block = true;
      }
      // 4. Инкремент индексов буфера чтения/записи:
      ind++;
      ind &= BUFFER_SIZE - 1;
      // 5. Запуск нового преобразования ADC:
      sbi(ADCSRA,ADSC);
   }
}

Обратите внимание на шаг 3, где осуществляется проверка - если входной индекс делится на размер блока, то устанавливается индекс чтения rind и флагом dsp_block сигнализируется, что новый блок данных готов для вычислений DSP. Между тем функция loop() работает в фоновом режиме, и увидит этот сигнал, и по нему запустит обработку блока. В заключение инкрементируются индексы буферов, после чего выполняется запуск нового преобразования ADC вызовом функции sbi().

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

Немедленно возникли вопросы, следующие из ограничения вычислений при работе в реальном времени:

• Какое максимальное количество операций DSP можно выполнить в реальном времени?
• Какие именно детали реализации имеют значение?

Для ответа на эти вопросы были реализованы 3 разных алгоритма DSP, что описывается в последующих секциях. Был выбран аддитивный синтез, свертка в домене времени и быстрое преобразование Фурье (БПФ, FFT).

[Аддитивный синтез]

Это метод конструирования сложного сигнала путем сложения друг с другом базовых простых сигналов (см. рис. 3). Эта техника широко используется для синтеза новых звуков, как и повторного синтеза сигналов, которые были обработаны (например, спектральными методами).

Рис. 3. Аддитивный синтез: несколько базовых генераторов с независимыми фазой (fi) и амплитудой (ri) комбинируются друг с другом для формирования сложного сигнала.

Высокоуровневый код для простого аддитивного синтеза можно увидеть ниже:

for (n = 0; n < N; n++)
{
   angle = 2.0 * M_PI * t;
   y[n] = 0.0;
   for (k = 0; k < numFreqs; k++)
      y[n] += r[k]*sin(f[k] * angle);
   t += 1.0 / SR;
}

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

ind[k] = (ind[k]+f[k]) & (SINETABLE_SIZE-1);
y[n&(BUFFER_SIZE-1)] += sine[ind[k]] >> pad;

[Свертка в домене времени]

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

Рис. 4. Свертка в домене времени: входной сигнал x[n] сворачивается с ответом импульса фильтра в соответствии с коэффициентами bi, чтобы сгенерировать выходной сигнал y[n]. Это общая схема FIR фильтрации (FIR означает finite impulse response, так называемый фильтр с конечной импульсной характеристикой, КИХ-фильтр).

Высокоуровневый код для свертки в домене времени, реализующей FIR фильтр порядка N:

for (k = 0; k < N; k++)
   y[n] += b[k]*x[n-k];

Пример практической реализации:

for (int n = 0; n < N; n++)
{
   int yn = 0, xtmp;
   for (int i = 0; i < order ; i++)
   {
      xtmp = 127 - TMOD(x, n-i, BUFFER_SIZE);
      yn += xtmp * 10 / 100;
   }
   LIMIT(yn );          // предел a +- 127
   TMOD(y, n, BUFFER_SIZE) = 127 + yn;
}

[Быстрое преобразование Фурье]

БПФ (Fast Fourier Transform, FFT) это умная реализация традиционного преобразования Фурье, позволяющая снизить сложность вычислений с O(n2) до O(n log(n)), где n это количество выборок сигнала в домене времени, или, эквивалентно, число контейнеров частоты, которые описывают спектр частот сигнала после вычисления преобразования Фурье. Алгоритм FFT основан на свойстве избыточности и симметрии промежуточных шагов вычислений и используется во многих обработках сигналов. Общую схему FFT можно увидеть на рис. 5.

Рис. 5. FFT использует принцип "разделяй и властвуй", сохраняя промежуточные результаты для ускорения вычисления спектра сигнала. Рисунок показывает один шаг 8-точечного вычисления FFT, как результаты привязываются к контейнерам частот спектра.

#include < math.h >

#include < avr/io.h >

#include < avr/delay.h >

#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr

#define NP 128

float data[NP];

//Преобразование int в ASCII с помощью библиотеки avrlib:

char *itoa( int value, char *string, int radix );

#include "lcd.c"

void four1(float data[], int nn, int isign)
{
   int n,mmax,m,j,istep,i;
   /* double */float wtemp,wr,wpr,wpi,wi,theta;
   float tempr,tempi;

   n=nn < < 1;
   j=1;
   for (i=1; i < n; i+=2)
   {
      if (j > i)
      {
         SWAP(data[j],data[i]);
         SWAP(data[j+1],data[i+1]);
      }
      m=n >> 1;
      while (m >= 2 && j > m)
      {
         j -= m;
         m >>= 1;
      }
      j += m;
   }
   mmax=2;
   while (n > mmax)
   {
      istep=mmax < < 1;
      theta=isign*(6.28318530717959/mmax);
      wtemp=sin(0.5*theta);
      wpr = -2.0*wtemp*wtemp;
      wpi=sin(theta);
      wr=1.0;
      wi=0.0;
      for (m=1; m < mmax; m+=2)
      {
         for (i=m; i < = n; i+=istep)
         {
            j=i+mmax;
            tempr=wr*data[j]-wi*data[j+1];
            tempi=wr*data[j+1]+wi*data[j];
            data[j]=data[i]-tempr;
            data[j+1]=data[i+1]-tempi;
            data[i] += tempr;
            data[i+1] += tempi;
         }
         wr=(wtemp=wr)*wpr-wi*wpi+wr;
         wi=wi*wpr+wtemp*wpi+wi;
      }
      mmax=istep;
   }
}

void realft(float data[], int n, int isign)
{
   int i,i1,i2,i3,i4,np3;
   float c1=0.5,c2,h1r,h1i,h2r,h2i;
   /*double*/float wr,wi,wpr,wpi,wtemp,theta;

   theta=3.141592653589793/(float) (n>>1);
   if (isign == 1)
   {
      c2 = -0.5;
      four1(data,n>>1,1);
   }
   else
   {
      c2=0.5;
      theta = -theta;
   }
   wtemp=sin(0.5*theta);
   wpr = -2.0*wtemp*wtemp;
   wpi=sin(theta);
   wr=1.0+wpr;
   wi=wpi;
   np3=n+3;
   for (i=2; i < = (n>>2); i++)
   {
      i4=1+(i3=np3-(i2=1+(i1=i+i-1)));
      h1r=c1*(data[i1]+data[i3]);
      h1i=c1*(data[i2]-data[i4]);
      h2r = -c2*(data[i2]+data[i4]);
      h2i=c2*(data[i1]-data[i3]);
      data[i1]=h1r+wr*h2r-wi*h2i;
      data[i2]=h1i+wr*h2i+wi*h2r;
      data[i3]=h1r-wr*h2r+wi*h2i;
      data[i4] = -h1i+wr*h2i+wi*h2r;
      wr=(wtemp=wr)*wpr-wi*wpi+wr;
      wi=wi*wpr+wtemp*wpi+wi;
   }
   if (isign == 1)
   {
      data[1] = (h1r=data[1])+data[2];
      data[2] = h1r-data[2];
   }
   else
   {
      data[1]=c1*((h1r=data[1])+data[2]);
      data[2]=c1*(h1r-data[2]);
      four1(data,n>>1,-1);
   }
}

int main(void)
{
   unsigned char buf[10];
   int i,j;
   float per;
   
   per=4.;
   LCDInit();
   for (j=1; j < =10; j++)
   {
      LCDCommand(1);
      LCDString(itoa(j,buf,10));
      for (i=1; i < =NP; i++)
         data[i]=cos(2.0*3.141592654*(i-1)/per);
      realft(data,NP,1);
   }
   LCDCommand(LCD_Line2);
   LCDString("Done.");
   while(1);
   return 0;
}

[Анализ производительности]

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

С точки зрения обработки звука в реальном времени на Arduino, эти алгоритмы показали ставят естественные вопросы относительно выполнимости их обработки:

• Аддитивный синтез: какое максимальное количество генераторов можно использовать для вычисления новой формы сигнала в реальном времени?
• Свертка в домене времени: какая максимальная длина фильтра допустима при фильтрации звука в реальном времени?
• FFT: какая максимальная длина FFT может быть вычислена в реальном времени?

Ниже показаны полученные результаты.

Аддитивный синтез. В начале цикла DSP алгоритм аддитивного синтеза запускается с использованием определенного количества генераторов, и среднее значение времени синтезатора было взято из большого количества измерений. Были использованы размеры блоков 32, 64 b 128 выборок (большее количество оказалось невозможно обработать в реальном времени) количество генераторов увеличивалось, пока не был достигнут предел времени периода цикла DSP.

Сначала было испробовано использование структур цикла. Из-за того, что циклы требовали инкремента и проверки переменной на каждой итерации, использование одного цикла может оказывать большое влияние на количество генераторов, которое можно использовать для аддитивного синтеза в реальном времени с помощью Arduino.

В любом алгоритме DSP, который работает с блоком выборок, обязательно есть хотя бы один цикл, который обрабатывает все выборки в блоке. Этот цикл может быть устранен ценой перекомпиляции каждый раз, когда длина блока меняется, что очень неудобно. Обычно используется больше циклов, например в аддитивном синтезе для суммирования результатов нескольких генераторов. Была исследована альтернатива удаления этого внутреннего цикла, путем явного написания суммы генераторов. На рис. 6 показано максимальное количество генераторов, которое можно выполнить в реальном времени при использовании цикла и при использовании встраиваемого кода (inline). Путем удаления внутреннего цикла появилась возможность увеличить количество генераторов с 8 до 13 или 14 в зависимости от размера блока.

Рис. 6. Результаты аддитивного синтеза при использовании циклов (верхняя часть рисунка) и встраиваемого, inline-кода (нижняя часть рисунка).

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

Два параметра было использовано для вычисления значения каждого генератора: фаза и амплитуда. Фаза обрабатывалась по обновлению индекса при чтении из таблицы синуса, и амплитуда умножалась на результат, выбранный из этой таблицы. Операции с плавающей точкой также оказались слишком дорогими для использования, поэтому было реализовано 3 способа умножения амплитуды: (1) путем использования одного целочисленного умножения и одного целочисленного деления (2 целочисленные операции), (2) путем использования одного целочисленного деления (1 целочисленная операция), и (3) путем переменного заполнения двоичного кода незначащей информацией для выполнения поразрядного деления или умножения на числа в степени числа 2. На рис. 7 показано время, используемое для алгоритма аддитивного синтеза для этих вариантов. Путем использования операций низкого уровня (с менее точными результатами) и применения встраиваемого кода было увеличено количество генераторов от 3 (когда использовались 2 целочисленные операции и цикл for) до 15 (когда использовались переменные заполнения и встраиваемый код).

Рис. 7. Время, которое занял алгоритм аддитивного синтеза с размером блока 128 выборок, с использованием разного количества и видов операций, и переменным количеством генераторов.

Свертка в домене времени. Второй эксперимент - попытка узнать какой максимальный размер FIR-фильтра можно реализовать в реальном времени для входного сигнала с использованием алгоритмов свертки в домене времени. Был реализован цикл фильтрации с использованием разных типов операций для умножения каждого коэффициента на значения выборок: (1) использование одного целочисленного умножения и одного целочисленного деления, (2) использование переменного дополнения бит, и (3) использование жестко запрограммированного константами дополнения бит. Результаты каждого эксперимента показаны на рис. 8. Эти эксперименты запускались с частотой выборки 31250 Гц и размерами блоков по 32, 64, 128 и 256 выборок сигнала. 

Результаты опять показали, что даже малые изменения реализации приводят к большим различиям в вычислительной мощности. Когда использовалось целочисленное деление, то максимальный полученный порядок фильтра был 1, в то время как при переменном дополнении порядок возрос до 7 и с дополнением с помощью констант получилось достичь порядка фильтра 13 или 14 в зависимости от размера блока. 

Рис. 8. Операция свертки в домене времени с использованием 2 целочисленных операций (верхняя часть рисунка), переменного дополнения (средняя часть рисунка) и постоянного дополнения (нижняя часть рисунка). 

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

Оказалось, что вычисление FFT с той же частотой выборок, которая использовалась в других экспериментах (31250 Гц) было невозможно, так что были подстроены параметры работы микроконтроллера, чтобы достичь состояния, когда был получен расширенный период цикла DSP для того же количества выборок, и FFT стал выполнимым. Путем измерения количества времени, которое тратится на вычисление FFT для указанного количества выборок, было определено, что максимальная частота FFT для блока из 256 выборок будет около 2335 Гц. Ближайшая частота достижима увеличением значения прескалера PWM до 32, этим коэффициентом была установлена частота выборок около 1953 Гц. 

На рис. 9 показан анализ времени FFT на частоте выборок 1953 для различных размеров блока и двух реализаций: с использованием API-функции sin() и использованием предварительно рассчитанной таблицы синусов. В этом сценарии максимальный размер блока, для которого FFT можно рассчитать в реальном времени, составил 256 выборок. Обратите внимание, что даже когда выполнялась операция FFT для размеров блока меньше или равного 256, не оставалось времени выполнить что-то еще с этими результатами вычислений. Например, нельзя применить аддитивный синтез для сигнала, поскольку максимальное количество генераторов, которое можно использовать, было 14 (с ограничением типа и количества операций), в то время как здесь будет нужно то же количество генераторов, что и количество выборок сигнала в заданном размере блока. 

Рис. 9. Время, которое занимает вычисление быстрого преобразования Фурье (FFT) на Arduino для разных размеров блока. Красная линия показывает реализацию с использованием библиотечной функции sin(), и синяя линия показывает реализацию на табличной функции синуса.

По результатам экспериментов стало понятно, что детали реализации алгоритмов, такие как выбор типа данных и и количество и тип операций приводят к большим различиям по возможностям и качеству вычислений. Например, целочисленное умножение и деление отнимают в 2 раза больше времени, чем использование целочисленного суммирования. Количество циклов, как оказалось, тоже имеет большое значение. В эксперименте с аддитивным синтезом количество генераторов было почти удвоено заменой циклов встраиваемым (inline) кодом. Способ работы с переменными также сильно влияет на производительность.

[Ссылки]

1. Real time digital audio processing using Arduino (Andre Jucovsky Bianchi, Marcelo Queiroz, Computer Science Department University of Sao Paulo) site:www.ime.usp.br.
2. Arduino Realtime Audio Processing site:interface.khm.de.
3. Audio Arduino – an ALSA (Advanced Linux Sound Architecture) audio driver for FTDI-based Arduinos site:vbn.aau.dk.
4. AVR336: декодер звукового формата ADPCM.
5. AVR223: Digital Filters with AVR (цифровые фильтры на AVR).
6. Arduino: что там внутри? (FAQ).
7. Digital Sound Processing for on the Arduino site:github.com.
8. Blackfin ADSP-BF538.
9. Библиотека DSP реального времени для Arduino.
10. AVR335: цифровой рекордер звука на AVR и DataFlash.