Исследование cordic-алгоритмов для программируемых логических интегральных схем

Размещено на http://www.allbest.ru/

Исследование cordic-алгоритмов для программируемых логических интегральных схем

Тарасенков С.О.

Аннотация

В цифровой обработке сигналов в течение длительного времени доминируют микропроцессоры с такими усовершенствованиями, как однократные многократные накопления команд и специальные режимы адресации. Хотя эти процессоры имеют низкую стоимость и предлагают экстремальную гибкость, они часто не достаточно быстры для достаточно требовательных задач DSP. Появление реконфигурируемых логических компьютеров позволяет повысить скорость выделенных аппаратных решений по затратам, конкурентоспособным с традиционным программным подходом. К сожалению, алгоритмы, оптимизированные для этих систем на базе микропроцессора, обычно плохо отображают аппаратные средства. Хотя аппаратно-эффективные решения часто существуют, доминирование программных систем удерживает эти решения вне внимания. Среди этих аппаратно-эффективных алгоритмов есть класс итерационных решений для тригонометрических и других трансцендентных функций, которые используют только сдвиги и добавляют к выполнению. Тригонометрические функции основаны на векторных вращениях, тогда как другие функции, такие как квадратный корень, реализуются с использованием инкрементного выражения желаемой функции. Тригонометрический алгоритм называется CORDIC. Инкрементные функции выполняются с очень простым расширением к аппаратной архитектуре. Алгоритмы CORDIC обычно дают один дополнительный бит точности для каждой итерации. Тригонометрические алгоритмы CORDIC были первоначально разработаны как цифровое решение для задач навигации в реальном времени.

Ключевые слова: CORDIC, FPGA, вектор, маршрутизаторы, процессор, развертывание, сумматоры, цифровая обработка сигналов

В цифровой обработке сигналов в течение длительного времени доминируют микропроцессоры с такими усовершенствованиями, как однократные многократные накопления команд и специальные режимы адресации. Хотя эти процессоры имеют низкую стоимость и предлагают экстремальную гибкость, они часто не достаточно быстры для достаточно требовательных задач DSP. Появление реконфигурируемых логических компьютеров позволяет повысить скорость выделенных аппаратных решений по затратам, конкурентоспособным с традиционным программным подходом. К сожалению, алгоритмы, оптимизированные для этих систем на базе микропроцессора, обычно плохо отображают аппаратные средства. Хотя аппаратно-эффективные решения часто существуют, доминирование программных систем удерживает эти решения вне внимания. Среди этих аппаратно-эффективных алгоритмов есть класс итерационных решений для тригонометрических и других трансцендентных функций, которые используют только сдвиги и добавляют к выполнению. Тригонометрические функции основаны на векторных вращениях, тогда как другие функции, такие как квадратный корень, реализуются с использованием инкрементного выражения желаемой функции. Тригонометрический алгоритм называется CORDIC. Инкрементные функции выполняются с очень простым расширением к аппаратной архитектуре. Алгоритмы CORDIC обычно дают один дополнительный бит точности для каждой итерации. Тригонометрические алгоритмы CORDIC были первоначально разработаны как цифровое решение для задач навигации в реальном времени.

Алгоритм CORDIC нашел свой путь в различных приложениях, включая математический сопроцессор 8087, калькулятор HP-35, радиолокационные сигнальные процессоры и робототехнику. CORDIC-алгоритмы также были предложены для вычисления дискретного преобразования Фурье, дискретного косинуса, дискретного преобразования Хартли и Чирпа-Z, фильтрации, сингулярной декомпозиции и решения линейных систем.

В этой статье делается попытка исследовать существующие алгоритмы CORDIC, ориентируясь на реализацию в программируемых пользователем вентильных матрицах (FPGA).

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

Рисунок 1 - итеративная архитектура CORDIC

При работе начальные значения загружаются через мультиплексоры в регистры x, y и z. Затем в каждом из следующих n циклов синхронизации значения из регистров передаются через сдвиги и сумматоры-вычитатели, а результаты помещаются обратно в регистры. Сдвиги изменяются на каждой итерации, чтобы вызвать нужный сдвиг для итерации. Аналогично, адрес ПЗУ увеличивается на каждой итерации, так что соответствующее значение элементарного угла представляется на сумматор-вычитатель z. На последней итерации результаты считываются непосредственно из сумматоров-вычитателей. Очевидно, что требуется простая машина состояния, чтобы отслеживать текущую итерацию и выбирать степень сдвига и адрес ПЗУ для каждой итерации. Данная конструкция использует дорожки данных по всему слову (так называемый бит-параллельный дизайн). Бит-параллельные переключатели сдвига переменных плохо отображают архитектуры FPGA из-за высокой потребности в вентиляторах. Если они реализованы, эти переключатели обычно потребуют нескольких уровней логики (то есть сигнал должен будет проходить через несколько ячеек FPGA). Результатом является плохое быстродействие при использовании большого количества логических ячеек.

Более компактная конструкция возможна с использованием битовой последовательной арифметики. Упрощенная логика в бит-последовательном дизайне позволяют работать с гораздо более высокой тактовой частотой, чем эквивалентная параллельная конструкция бит. Разумеется, для каждой итерации дизайн также должен быть синхронизирован w раз (w - ширина слова данных). Бит-последовательный дизайн состоит из трехбитовых последовательных сумматоров-вычитателей, трех сдвиговых регистров и последовательного постоянного запоминающего устройства (ПЗУ). Каждый регистр сдвига имеет длину, равную ширине слова. Также есть некоторые мультиплексоры для выбора отводов сдвиговых регистров для сдвинутых вправо перекрестных терминов (сдвиг выполняется с использованием бит-задержек в последовательных системах бит). В этой конструкции для каждой из n-итераций требуются w-часы, где w - точность сумматоров. При работе мультиплексоры нагрузки слева открываются для периодов времени w для инициализации регистров x, y и z (эти регистры также могут быть загружены параллельно для инициализации). После загрузки, данные сдвигаются прямо через последовательные сумматоры-вычитатели и возвращаются в левый конец регистра. Каждая итерация требует, чтобы w часы возвращали результат в регистр. В начале каждой итерации машина состояния управления считывает знак регистра y (или z) и соответственно устанавливает элементы управления добавлением/вычитанием. Во время n-й итерации результаты могут считываться с выходов последовательных сумматоров, а следующие данные инициализации сдвигаются в регистры.

Простота последовательного проектирования бит очевидна из рисунка 2. cordic навигация процессор

Рисунок 2 - бит последовательный итерационный CORDIC

Даже в этом случае проводка мультиплексоров с переключением крана может представлять проблемы в некоторых ПЛИС. Тем не менее, межсоединение минимально и логика между регистрами проста. Возможность использования крайних битовых тактовых частот составляет большое количество тактовых циклов, необходимых для завершения каждого поворота.

Рассмотренные раннее процессоры CORDIC являются итеративными, что означает, что процессор должен выполнять итерации в n раз быстрее скорости передачи данных. Процесс итерации может развернуться, так что каждый из n элементов обработки всегда выполняет одну и ту же итерацию. Развернутый CORDIC процессор показан на рисунке 4.

Рисунок 3 - развернутый CORDIC процессор

Развертывание процессора приводит к двум значительным упрощениям. Сначала переключатели имеют фиксированный сдвиг, что означает, что они могут быть реализованы в проводке. Во-вторых, значения поиска для аккумулятора угла распределяются как константы для каждого сумматора в цепочке накопления углов. Эти константы могут быть жестко связаны, и не требуют хранения. Весь процессор CORDIC сводится к массиву взаимосвязанных сумматоров-вычитателей. Необходимость в регистрах также устранена, что делает развернутый процессор строго комбинаторным. Задержка в результирующей схеме будет существенной, но время обработки уменьшается от времени, требуемого итеративной схемой. В большинстве случаев, особенно в ПЛИС, нет смысла использовать такую ??крупную комбинаторную схему. В случае большинства архитектур FPGA уже есть регистры, присутствующие в каждой логической ячейке, поэтому добавление регистров конвейера не требует аппаратных затрат.

Развернутый процессор также может быть преобразован в последовательный бит. Каждый сумматор-вычитатель заменяется последовательным устройством, разделенным w-разрядными регистрами сдвига. Регистры сдвига необходимы для извлечения знака элемента y или z до того, как первые биты достигнут следующих сумматор-вычитателей. Правые сдвинутые поперечные члены берутся из фиксированных отводов в сдвиговых регистрах. Также необходим некоторый метод расширения знака для сдвинутых членов. На рисунке 4 показаны две итерации бит-последовательного процессора CORDIC, реализованные в FPGA Atmel 6005 или NSC Clay31.

Рисунок 4 - две итерации бит-последовательного процессора CORDIC

Обратите внимание, что кросс-термин берется из разных отводов сдвигового регистра на каждой итерации. Этот конкретный процессор используется для вычисления величины вектора. Поскольку это процесс векторного режима, и угол результата не требуется, нет необходимости в аккумуляторе угла. На рисунке 6 показана деталь вычитания сумматора для этой конструкции. Для более высокой производительности требуются параллельные процессоры с несколькими бит или развернутый параллельный конвейер. До недавнего времени FPGA не имели требуемой комбинации логических и маршрутизирующих ресурсов для создания параллельного процессора. Это в основном связано с большим количеством перекрестной маршрутизации, требуемой между регистрами x и y на каждой стадии. Кроме того, производительность уменьшается при увеличении ширины слова из-за разброса по всем сумматорам. Серия Xilinx 4000E имеет достаточную маршрутизацию для реализации достаточно компактного параллельного конвейера CORDIC. Его специальная логика переноса обеспечивает приемлемую производительность для сумматоров.

Алгоритмы CORDIC, представленные в этой статье, хорошо известны в исследовательских и суперкомпьютерных кругах. Тем не менее, мой опыт показывает, что большинство современных аппаратных схем DSP выполняются инженерами, которые практически не имеют аналогов в аппаратно-эффективных алгоритмах DSP. Новые разработчики DSP должны ознакомиться с этими алгоритмами и методами их реализации в ПЛИС, чтобы оставаться конкурентоспособными. Алгоритм CORDIC является мощным инструментом в панели инструментов DSP. В этой статье показано, что инструмент можно использовать на вычислительных машинах на базе ПЛИС, которые являются вероятной основой для систем DSP следующего поколения.

Размещено на Allbest.ru