Асинхронное устройство cordic алгоритма для цифро-сигнальных процессоров
Изобретение относится к области вычислительной техники. Технический результат заключается в снижении потребляемой мощности, упрощении конструкции и повышении быстродействия при асинхронном обмене данными. Раскрыто асинхронное устройство CORDIC алгоритма для цифро-сигнальных процессоров, содержащее блок увеличения числа однотипных данных, блок инициализации и условного перехода итераций, базовый блок вычислений, сдвиговый регистр, первое арифметически-логическое устройство, второе арифметически-логическое устройство, регистр обратной связи, формирователь тактовых сигналов, формирователь снижения выходных данных, при этом входом служит по меньшей мере один вход блока увеличения числа однотипных данных, выход которого соединен с первым входом второго арифметически-логического устройства, выход формирователя тактовых сигналов соединен с первым входом блока инициализации и условного перехода итераций и вторым входом сдвигового регистра, выход которого соединен со вторым входом блока инициализации и условного перехода итераций, выход которого соединен с первым входом сдвигового регистра, вторым входом и четвертым входом первого арифметически-логического устройства, выход базового блока вычислений соединен с первым входом и третьим входом первого арифметически-логического устройства и соединен со вторым входом второго арифметически-логического устройства, первый выход и второй выход первого арифметически-логического устройства соединены соответственно с третьим входом и четвертым входом второго арифметически-логического устройств, выход которого соединен с входом регистра обратной связи и входом формирователя снижения выходных данных, выход регистра обратной связи соединен с входом базового блока вычислений, и выход формирователя снижения выходных данных служит выходом устройства и соединен с управляющим входом блока увеличения числа однотипных данных. 5 ил.
Изобретение относится к устройствам цифровых вычислений и обработки данных и предназначено для вычисления итерационным методом CORDIC (COordinate Rotation DIgital Computer) сходящихся процессов, например, квадратных, кубических корней, деления и т.д.
Метод приближения CORDIC широко используется в вычислительных процессах. Алгоритм CORDIC был описан достаточно давно (J.E. Voider. The CORDIC trigonometric computing technique. IRE Trans. Electron. Comput. Sept. 1959, Vol. EC-8, No. 3, pp. 335-339). Существуют различные методы реализации алгоритма CORDIC, например, на базе ПЛИС (Дмитрий Дайнеко. Реализация CORDIC алгоритма на ПЛИС. Компоненты и технологии, №12, 2011). Кроме того, это алгоритмическое решение используется для быстрого преобразования Фурье (Despain A.M. Fourier Transform Computations Using CORDIC Iterations. IEEE Transactions On Computers. 1974, Vol. 23, pp. 993-1001).
Известен модуль CORDIC для повторяющегося приближения векторного вращения через ротационный угол (см., например, патент США US 7606852).
Для реализации алгоритма CORDIC используется большое количество матриц (Chang L.W. and Lee S.W. Systolic Arrays for the discrete Cosine Transform. IEEE Trans. On Signal Processing. Nov. 1991, Vol. 29, No. 11, pp. 2411-2418), а также отдельные процессорные узлы для вычислений (Wang S. and Piuri V. A unified View of CORDIC Processor Design. Application Specific Processors. Edited by Earl E. Swartzlander, Jr. Kluwer Academic Press. November 1996, Ch. 5, pp. 121-160).
Наиболее близким является устройство для реализации CORDIC алгоритма при выполнении различных математических операций согласно XILINX, LogiCORE IP CORDIC v4.0, DS249. March 1, 2011 Product Specification.
Ограничением всех известных технических решений является существенные аппаратные затраты, выражающиеся в необходимости использования, кроме базового блока вычислений, большого количества таблиц памяти, большого числа арифметически-логических устройств, других логических устройств, регистров, сумматоров и т.д. При этом необходимо обеспечить жесткую временную синхронизацию работы всех функциональных блоков, и по этой причине эффективность работы (быстродействие) известных технических решений недостаточно высока. Известные устройства характеризуются длительным процессом подготовки к вычислениям, необходимостью согласования временных диаграмм и дополнительными аппаратными затратами.
Решаемая изобретением задача заключается в улучшении технико-эксплуатационных характеристик устройства CORDIC алгоритма.
Технический результат, достигаемый при использовании изобретения, заключается в снижении потребляемой мощности, упрощении конструкции и повышении быстродействия при асинхронном обмене данными.
Для решения поставленной задачи с достижением заявленного технического результата асинхронное устройство CORDIC алгоритма для цифро-сигнальных процессоров содержит блок увеличения числа однотипных данных, блок инициализации и условного перехода итераций, базовый блок вычислений, сдвиговый регистр, первое арифметически-логическое устройство, второе арифметически-логическое устройство, регистр обратной связи, формирователь тактовых сигналов, формирователь снижения выходных данных. Входом устройства служит по меньшей мере один вход блока увеличения числа однотипных данных, выход которого соединен с первым входом второго арифметически-логического устройства. Выход формирователя тактовых сигналов соединен с первым входом блока инициализации и условного перехода итераций и вторым входом сдвигового регистра, выход которого соединен со вторым входом блока инициализации и условного перехода итераций. Выход блока инициализации и условного перехода итераций соединен с первым входом сдвигового регистра, а также вторым входом и четвертым входом первого арифметически-логического устройства. Выход базового блока вычислений соединен с первым входом и третьим входом первого арифметически-логического устройства и вторым входом второго арифметически-логического устройства. Первый выход и второй выход первого арифметически-логического устройства соединены соответственно с третьим входом и четвертым входом второго арифметически-логического устройства, выход которого соединен с входом регистра обратной связи и входом формирователя снижения выходных данных. Выход регистра обратной связи соединен с входом базового блока вычислений. Выход формирователя снижения выходных данных служит выходом устройства.
Преимущества, а также особенности настоящего изобретения поясняются с помощью варианта его выполнения со ссылками на фигуры.
На фиг. 1 изображена функциональная схема заявленного устройства.
На фиг. 2 схематично показан известный алгоритм CORDIC работы устройства согласно фиг. 1.
На фиг. 3, 4, 5 приведены графики итерационного процесса, где:
на фиг. 3 представлен график итерационного процесса, например, для выполнения операции деления;
на фиг. 4 представлено то же, что фиг. 3, но в увеличенном масштабе;
на фиг. 5 представлен результат выполнения операции деления при различных входных данных (полные циклы).
Перечень позиций на фиг. 1:
1 - блок увеличения числа однотипных данных
2 - блок инициализации и условного перехода итераций
3 - базовый блок вычислений
4 - сдвиговый регистр
5 - первое арифметически-логическое устройство
6 - второе арифметически-логическое устройство
7 - регистр обратной связи
8 - формирователь тактовых сигналов
9 - формирователь снижения выходных данных
10 - вход (шина входных сигналов)
11 - выход (шина выходных сигналов)
12-22 - шины данных (сигнальные).
Асинхронное устройство CORDIC алгоритма для цифро-сигнальных процессоров (фиг. 1) содержит блок 1 увеличения числа однотипных данных, блок 2 инициализации и условного перехода итераций, базовый блок 3 вычислений, сдвиговый регистр 4, первое арифметически-логическое устройство 5, второе арифметически-логическое устройство 6, регистр 7 обратной связи, формирователь 8 тактовых сигналов, формирователь 9 снижения выходных данных. Входом 10 служит по меньшей мере один вход блока 1 увеличения числа однотипных данных, выход которого соединен с первым входом второго арифметически-логического устройства 6. Выход формирователя 8 тактовых сигналов соединен с первым входом блока 2 инициализации и условного перехода итераций и вторым входом сдвигового регистра 4. Выход сдвигового регистра 4 соединен со вторым входом блока 2 инициализации и условного перехода итераций. Выход блока 2 инициализации и условного перехода итераций соединен с первым входом сдвигового регистра 4, вторым входом и четвертым входом первого арифметически-логического устройства 5. Выход базового блока 3 вычислений соединен с первым входом и третьим входом первого арифметически-логического устройства 5 и соединен со вторым входом второго арифметически-логического устройства 6. Первый выход и второй выход первого арифметически-логического устройства 5 соединены соответственно с третьим входом и четвертым входом второго арифметически-логического устройства 6. Выход второго арифметически-логического устройства соединен с входом регистра 7 обратной связи и входом формирователя 9 снижения выходных данных. Выход регистра 7 обратной связи соединен с входом базового блока 3 вычислений. Выход формирователя 9 снижения выходных данных служит выходом устройства.
Предложенное устройство характеризуется тем, что с целью реализации автономного процесса обмена, упрощения приема данных и формирования вычисленных результатов входные воздействия не регламентированы по времени поступления, а выходная реакция устройства определяется автоматически при завершении итерационного процесса. Известные устройства характеризуются длительным процессом подготовки к вычислениям, необходимостью согласования временных диаграмм и дополнительными аппаратными затратами в сравнении с заявленным устройством.
Иллюстрация алгоритма CORDIC представлена на фиг. 2. Алгоритм основан на последовательном (итерационном) приближении текущего значения к искомому. Например, для операции деления проверяется условие:
Y⋅Z[i]-X≤0?
где Y - делитель, X - делимое, Z [i] - итерационная величина искомого значения на i-том шаге. На каждом итерационном шаге вычитается или прибавляется Δ[i] согласно следующим выражениям:
Z[i]-Δ[i] или Z[i]+Δ[i],
где Δ[i] на каждом шаге уменьшается в два раза (фактическая операция - сдвиг вправо на один разряд). На фиг. 2 показано изменение величины в итерационном процессе - V1, V2, V3, при этом V2-V1 соответствует углу смещения (поворота) в два раза больше угла, соответствующего последующему изменению V2-V3. Таким образом, на фиг. 2 показана величина изменения Δ[i] в два раза на следующем итерационном шаге.
В заявленном устройстве базовый блок 3 вычислений может выполнять различные, заранее заданные функции, например, деление, суммирование, возведение в степень, извлечение корней и т.п.
Заявленное устройство имеет блок 1 увеличения числа однотипных данных для повторения входных воздействий (это может быть один или два входа в зависимости от типа базового блока 3), сигналы на который поступают с входа 10 по шине 12.
На вход 10 (или входы) в асинхронном режиме подаются данные для вычисления. Если входной буфер задействован в блоке 1, то устройство остается в режиме вычисления предыдущего незаконченного итерационного процесса, и запись новых данных не допускается. После завершения итерационного процесса в блок 1 загружаются новые данные, и начинается следующий итерационный процесс. При этом на выходе блока 1 (на шине 13) сохраняются n-число раз данные, которые поступили по шине 12, где n - число разрядов в слове (word). Итерационный процесс длится с числом тактов, эквивалентных числу разрядов в слове.
Базовый блок 3 зависит от типа выполняемой операции. Например, для вычисления квадратного корня текущее в итерационном процессе значение возводится в квадрат в этом блоке (word^2). Таким образом, по шине 15 передается слово на первый арифметически-логический блок 5, где осуществляется операция сложения/вычитания с итерационной величиной, формируемой в блоке 2 и сдвиговом регистре 4. В блоке 2 инициализации и условного перехода итераций на начальном этапе формируется максимальное значение Δ[i], лежащее в диапазоне 0,5 от 1, что соответствует предельному значения положительного числа в формате чисел с фиксированной точкой. Это обеспечивается сигналом сброса по первому входу. После окончания сигнала сброса в процесс включается кольцо, состоящее из блока 2 и сдвигового регистра 4, обеспечивающее итерационный процесс и деление значения Δ[i] на два в каждом такте, что соответствует сдвигу вправо на один разряд.
Блок 2 по первому тактовому сигналу инициируется в заданное состояние (например, максимальное значение - предельная величина диапазона вычислений), которое в каждом такте через сдвиговый регистр 4 уменьшается в два раза (shift>>1), осуществляя сдвиг в сторону младших разрядов на один разряд. Это выражение справедливо, например, для данных с фиксированной запятой в формате 2S complement как представление чисел в формате от +1 до -1: например, максимальное положительное число представляется как 0.11111…1, а минимальное число (максимальная абсолютная величина отрицательного числа) - как 1.0000…0.
Итерационная величина Δ[i] на шине 19 есть величина для сложения и вычитания, постоянно изменяемая на каждом такте, которая поступает на второй и четвертый входы арифметически-логического блока 5. На шинах 16 и 17 формируются данные +/- («плюс/минус»), которые поступают на третий и четвертый входы второго арифметически-логического устройства 6. В зависимости от того, какая величина больше - на шинах 13 или 15, - фактор сравнения исходной величины и необходимой для вычисления величины выбирается во втором арифметически-логическом блоке 6 данных с шины 16 или 17. Таким образом, осуществляется итерационное приближение к вычисляемой величине Δ1[i] на шине 18.
Арифметически-логическое устройство 5 выполняет функцию сложения и вычитания одновременно: на его первом выходе формируется сложение чисел, поступающих на первый и второй входы ([1]+[2]). На втором выходе выполняется вычитание чисел, поступающих на третий и четвертый входы ([3]+[4]). Арифметически-логическое устройство 6 фактически является вычитателем с условным формированием результата. Если число, поступающее на первый вход, больше числа на втором входе, то на выходе (шина 18) формируется сигнал с четвертого входа, в противном случае - с третьего входа.
В формирователе 9 снижения выходных данных осуществляется сравнение числа с количеством разрядов в слове. В момент, когда число сдвигов в сдвиговом регистре 4 эквивалентно числу разрядов, формируется выходной сигнал на шине 22 с одновременным разрешением выдачи результата на выход 11. Одновременно с этим также формируется сигнал для загрузки следующих данных во входные буферы блока 1. Связь для передачи указанного сигнала для загрузки на фиг. 1 для простоты показана пунктирной линией, при этом выход формирователя 9 снижения выходных данных соединен с управляющим входом блока 1.
Окончание процесса вычисления позволяет производить обработку следующих данных с входа 10.
Формирователь 8 тактовых сигналов обеспечивает формирование сигнала сброса (начало итерационного процесса).
Регистр 7 обратной связи является регистром памяти для сохранения текущего значения. Регистр 7 обеспечивает работу схемы с обратной связью в соответствии с принципом построения последовательностных (рекурсивных) схем.
На фиг. 3-5 приведены графики итерационного процесса для выполнения операции деления.
На фиг. 3 представлена кривая итерационного процесса в последовательности различных значений входных данных, поступающих на вход 10. На фиг 4 показан фрагмент фиг. 3 одного итерационного цикла (увеличенный масштаб по оси X).
На фиг. 5 показаны результаты выполнения операции деления для входных данных на фиг. 3.
Заявленное устройство является полностью автономным с асинхронным принципом обмена данными между загрузкой данных и формированием вычисленного результата.
Таким образом, во-первых, удалось разработать асинхронное устройство, функционирующее в алгоритмах последовательного приближения структуры CORDIC, которое эффективно для выполнения любых вычислений. При этом основным результатом работы является снижение потребляемой мощности за счет асинхронного принципа работы, при котором устройство обрабатывает информацию только при наличии входных данных. Кроме того, достигается уменьшение аппаратных затрат, поскольку не требуется блоков подготовки загрузки данных, вычисления окончания процесса итерации - это происходит в автоматическом режиме. В-третьих, повышается быстродействие, т.к. итерационные процессы вычисления величин Δ[i] и Δ1[i] происходят одновременно. Эти три фактора значительно повышают эффективность использования данного устройства.
Наиболее успешно заявленное асинхронное устройство CORDIC алгоритма для цифро-сигнальных процессоров промышленно применимо в отдельных IP-блоках или непосредственно в цифро-сигнальных процессорах. Данное устройство может широко применяться вычислительных средах с автономным разделением функций с целью ускорения вычислительного процесса.
Асинхронное устройство CORDIC алгоритма для цифро-сигнальных процессоров, содержащее блок увеличения числа однотипных данных, блок инициализации и условного перехода итераций, базовый блок вычислений, сдвиговый регистр, первое арифметически-логическое устройство, второе арифметически-логическое устройство, регистр обратной связи, формирователь тактовых сигналов, формирователь снижения выходных данных,
при этом входом служит по меньшей мере один вход блока увеличения числа однотипных данных, выход которого соединен с первым входом второго арифметически-логического устройства,
выход формирователя тактовых сигналов соединен с первым входом блока инициализации и условного перехода итераций и вторым входом сдвигового регистра, выход которого соединен со вторым входом блока инициализации и условного перехода итераций, выход которого соединен с первым входом сдвигового регистра, вторым входом и четвертым входом первого арифметически-логического устройства,
выход базового блока вычислений соединен с первым входом и третьим входом первого арифметически-логического устройства и соединен со вторым входом второго арифметически-логического устройства,
первый выход и второй выход первого арифметически-логического устройства соединены соответственно с третьим входом и четвертым входом второго арифметически-логического устройств, выход которого соединен с входом регистра обратной связи и входом формирователя снижения выходных данных,
выход регистра обратной связи соединен с входом базового блока вычислений, и
выход формирователя снижения выходных данных служит выходом устройства и соединен с управляющим входом блока увеличения числа однотипных данных.
