Реализация алгоритмов на программируемых логических интегральных схемах с архитектурой FPGA

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

Государственное образовательное учреждение высшего профессионального образования «Московский государственный институт радиотехники,

электроники и автоматики (технический университет)»

Марухнич Юрий Алексеевич

Автореферат магистерской диссертации

Реализация алгоритмов на программируемых логических интегральных схемах с архитектурой FPGA

Направление 230100 «Информатика и вычислительная техника»

Магистерская программа 230100.06 «Элементы и устройства вычислительной техники и информационных систем»

МОСКВА 2012

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Развитие САПР и элементной базы открывают новые возможности в плане разработки устройств на ПЛИС. Рост сложности устройств реализуемых на ПЛИС ставит вопрос эффективности методов разработки того или иного устройства. Различные алгоритмы могут быть реализованы различными методами, с различной эффективностью и временем разработки.

Среди других аппаратных платформ (например, усовершенствованная машина RISC (ARM), обработчик цифровых сигналов (DSP), специализированная интегральная схема (ASIC)) технология ПЛИС с архитектурой FPGA комбинирует в себе гибкость и вычислительную эффективность. С удобно разработанной архитектурой, такой как конвейерная обработка и параллельные вычисления, FPGA может достигнуть очень высокой скорости обработки намного быстрее, чем традиционные реализации программного обеспечения. В последних продуктах ПЛИС FPGA произведена интеграция основных логических блоков (CLB) со встроенными микропроцессорами и связанными периферийными устройствами для формирования полной встроенной системы. Это не только гарантирует производительность системы, но также делает проект системы более гибким и адаптируемым, что может значительно уменьшить время, затраченное на проектирование системы.

Объект исследования. Объектом исследования является реализации алгоритмов на ПЛИС. Автоматизация проектирования цифровых СБИС. Различные виды существующих алгоритмов фильтрации. Методы реализации алгоритмов на ПЛИС.

Цель и постановка задачи исследования. Целью диссертационной работы является анализ особенностей реализации алгоритмов на программируемых логических интегральных схемах с архитектурой FPGA. Определение различных методов реализации на ПЛИС. Автоматизация реализации алгоритмов. При этом анализируются существующие методы реализации алгоритмов на ПЛИС.

Для достижения сформулированной цели в диссертации поставлены следующие задачи:

1. Анализ методов реализации алгоритмов на ПЛИС;

2. Исследование архитектуры существующих ПЛИС различных производителей и разработка критериев оценки;

3. Определение качества реализации алгоритмов на FPGA;

4. Исследование возможностей автоматизации аппаратной реализации с использованием моделирования в среде MATLAB;

5. Разработка и представление рекомендаций по выбору и использованию методов реализации алгоритмов на ПЛИС.

Методы исследования. Основные результаты диссертационной работы получены с использованием теории языков описания аппаратуры, методов моделирования и автоматизированного проектирования СБИС, теории информационного поиска.

Научная новизна работы состоит в анализе математических моделей реализации алгоритмов на ПЛИС с архитектурой FPGA, а также в разработке методики и рекомендаций по реализации алгоритмов обработки данных на программируемых логических интегральных схемах с архитектурой FPGA. Оценке эффективности автоматизации аппаратной реализации алгоритмов с использованием моделирования в среде MATLAB.

Практическая значимость работы состоит в том, что в ней произведено исследование алгоритмов адаптивной фильтрации и выбор модели адаптивного фильтра для аппаратной реализации. А также собраны воедино технологии адаптации алгоритмов для аппаратных решений на FPGA. Определена общая эффективность и специфика различных методов реализации алгоритмов. Определена эффективность применения автоматизации аппаратной реализации алгоритмов с использованием моделирования в среде MATLAB. Выработаны рекомендации по путям реализации тех или иных алгоритмов. С учётом выработанных рекомендаций произведено моделирование цифровой системы обработки сигналов с использованием фильтра Калмана.

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

Апробация и практическое внедрение результатов работы. Основные научные положения диссертационной работы докладывались и

обсуждались на научных конференциях, семинарах и конкурсах, в том числе: 59-ая научно-техническая конференция МИРЭА (г. Москва, 2010г.); 60-ая научно-техническая конференция МИРЭА (г. Москва, 2011г.); 10-ая научно-практическая конференция «Современные информационные технологии в управлении и образовании». ФГУП НИИ «Восход» (г. Москва, 2011 г.).

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

цифровой фильтр моделирование интегральный

Во введении обоснована актуальность темы диссертационного исследования, сформулирована цель и основные задачи работы.

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

Модель сообщения и модель наблюдения для цифрового фильтра Калмана задаются уравнениями:

лn = Цn-1лn-1 +Гn-1wn-1;л0 = л(0)

xn = Hnлn + vn

Формирующий шум wn = w[n] и шум измерений vn = v[n] -- стационарные белые последовательности (БШ) с нулевыми средними значениями и КФ вида

Rw[п] = Dwдп;Rv[п] = Dvдn,

где дп -- символ Кронекера.

Шумы wn и vn, по предположению, некоррелированны, начальное значение л0 = л(0) может быть либо детерминированной величиной, либо случайной;

Нп = H(tn), Фп = =Ф(tn),

Гn = Г(tn) -- известные функции времени при интервале дискретизации Т = =tn+1 - tn.

Найти алгоритм цифрового фильтра Калмана (далее ЦФК) и его структурную схему.

Запишем рекуррентную формулу для оценки сообщения в форме линейной комбинации оценки на предыдущем шаге и наблюдения хп:

Найдем дисперсию Dn ошибки еп = - и из условия ее минимума вычислим значения коэффициентов bп и kп:

Вычислим производные:

Приравнивая нулю первую производную, найдем соотношение между коэффициентами bn и kn:

Е[(лп - knxn) ] - E[(bn)] = 0.

Запишем произведение bnво втором слагаемом в виде

bn= bn -- bn(-- ) = bn-- bnen-1,

а для хп в первом слагаемом возьмем уравнение наблюдения. В результате получим

(1-knHn)E(лn) - knE(vn) = bn[E() - E(en-1)].

Используя условия ортогональности E(en-1) = 0 и некоррелированности E(vn) = 0, получим соотношение

Выразив с учетом линейной комбинации, уравнений ФФ и наблюдения и умножив на wn-1, после усреднения получим равенство (ортогональность СВ и wn-1)

E(wn-1) = 0.

Преобразуем правую часть предыдущего соотношения, подставив вместо лn правую часть уравнения сообщения (уравнения ФФ) и воспользуемся ортогональностью и wn-1. В результате получим

Следовательно, искомое соотношение между коэффициентами bп и kп принимает вид

На основе исходной линейной комбинации для оценки , подставив bп, находим РУ ЦФК

Структурная схема ЦФК изображена на рисунке 1.

Рис. 1. Структурная схема цифрового фильтра Калмана

Для реализации фильтра Калмана нужно:

а) выявить входные воздействия (они влияют на изменение состояния системы) и наблюдаемые значения;

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

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

г) оценить начальное состояние системы, т.е. значения переменных состояния и т.н. ковариацию ошибки оценки;

д) наконец, реализовать алгоритм фильтра в соответствии с хорошо известными формулами, подставив в них параметры.

Во второй главе диссертации проведен анализ технологий адаптации алгоритмов для аппаратных решений на FPGA. Проведен анализ существующих архитектур ПЛИС, а также разработанных алгоритмов реализации систем управления на основе ПЛИС с архитектурой FPGA. Цикл проектирования для систем управления, основанных на FPGA, в котором разработанный контроллер CT заменен эквивалентным DT, эмулирующим работу CT, изображен на рисунке 2 и состоит из следующих трех фаз:

· проект контроллера CT: контроллер разработан, чтобы выполнить ряд требуемых спецификаций, таких как повышение времени, максимальное пиковое проскакивание, время установившейся ошибки и т.д. Затем, разработанный контроллер моделируется с обратной связью с заводом CT.

· проект контроллера DT FP: разработанный должным образом контроллер CT дискретизирован через метод дискретизации, основанный на периоде выборки, T, в котором выполнится цифровое моделирование. Обычно, T не должен быть ни слишком большим, ни слишком маленьким относительно системной динамики. Слишком большой или слишком маленький T может вызвать неустойчивость системы (числовой или др.) или отказ встретить требуемые спецификации. Следующие направляющие линии нужно рассмотреть для того, чтобы выбрать T:

o Выберите достаточно маленький T так, чтобы не искажать эффекты. В частности выберите T в соответствии с критерием Найквиста-Шеннона, выбирающий критерий согласно ,где щс - требуемая пропускная способность системы с обратной связью. Общее правило ползунка для того, чтобы выбрать .

o Выберите достаточно маленький T так, чтобы он мог реагировать достаточно быстро на шумы, влияющие на систему.

o Выберите достаточно большой T, чтобы избежать числовых проблем.

Рис. 2. Цикл проектирования систем управления, основанных на FPGA

· проект контроллера DT FXP: дискретизированный контроллер преобразован в FXP. Отметим, что период выборки, который был выбран в предыдущей фазе, будет периодом, в который система FPGA будет работать. Следовательно, получившийся контроллер FXP моделируется с обратной связью наряду со счетчиком CT.

Система управления MPC (Model Predictive Control) может обычно описываться как x(k+1) =Ax(k) +Bu(k), где и являются состояниями и управляют входными векторами соответственно, является матрицей состояний, -- входная матрица. Контроллер MPC может получить входные значения для оптимального управления решая следующую проблему оптимизации:

где p -- длина горизонта оптимизации, m является горизонтом управления, и -- весовые матрицы, -- терминальная весовая матрица и . В данном уравнении отпимизации системные ограничения на вводы управления и состояния -- обычные линейные ограничения. Вышеупомянутая проблема оптимизации может быть описана в стандартной форме квадратичной проблемы (QP):

Где функция от x(k), -- постоянная матрица, определенная весовыми матрицами Pf, Ql и Ri, G -- постоянная матрица, определенная E и F.

В третьей главе проведен анализ методики автоматизации аппаратной реализации адаптивного фильтра с использованием моделирования в среде MATLAB, на примере фильтра Калмана.

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

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

Алгоритм

Алгоритм предсказывает положение движущегося объекта на основе его прошлых позиций, используя оценку фильтра Калмана. Он оценивает нынешнюю позицию по обновлению вектора состояний Кальмана, которое включает в себя положение (х, у), скорость (Vx и Vy) и ускорение (Ах и Ау) движущихся объектов. Вектор состояний Кальмана x_est является постоянной переменной.

% Initial conditions

persistent x_est p_est

if isempty(x_est)

x_est = zeros(6, 1);

p_est = zeros(6, 6);

end

x_est инициализируется как пустой 6x1 вектор-столбец и обновляется каждый раз, когда используется фильтр.

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

Эти законы движения захваченной в переходном состоянии матрицы, содержащей значения коэффициентов х, у, Vx, Vy, Ах и Ау.

% Initialize state transition matrix

dt=1;

A=[ 1 0 dt 0 0 0;...

0 1 0 dt 0 0;...

0 0 1 0 dt 0;...

0 0 0 1 0 dt;...

0 0 0 0 1 0 ;...

0 0 0 0 0 1 ];

Процесс фильтрации состоит из двух этапов:

· Прогноз состояния и ковариационной

Фильтр Калмана использует предварительно оценивается состояние x_est, прогнозировать состояние, x_prd. Прогнозируемое состояние и ковариации рассчитываются:

% Predicted state and covariance

x_prd = A * x_est;

p_prd = A * p_est * A' + Q;

· Оценка

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

% Measurement matrix (Матрица измерений)

H = [ 1 0 0 0 0 0; 0 1 0 0 0 0 ];

Q = eye(6);

R = 1000 * eye(2);

% Estimation (Оценка)

S = H * p_prd' * H' + R;

B = H * p_prd';

klm_gain = (S \ B)';

% Estimated state and covariance (Расчет состояний и ковариации)

x_est = x_prd + klm_gain * (z - H * x_prd);

p_est = p_prd - klm_gain * H * p_prd;

%Compute the estimated measurements (Расчет предполагаемых измерений)

y = H * x_est;

Проведен анализ возможных путей реализации алгоритма, и выбор наиболее оптимального метода. Создано HDL описание блока на языке Verilog, и его функциональная верификация. Проведен анализ параметров полученного блока средствами САПР ISE Design. Приведены выработанные рекомендации по выбору и использованию методов реализации алгоритмов на ПЛИС. Также разработана методика по выбору метода реализации того или иного алгоритма в зависимости от его характеристик.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проанализированы методы реализации алгоритмов на программируемых логических интегральных схемах.

2. Проведено исследование архитектуры существующих программируемых логических интегральных схем различных производителей и разработаны критерии оценки.

3. Определено качество реализации алгоритмов на FPGA

4. Исследованы возможности автоматизации аппаратной реализации алгоритмов с использованием моделирования в среде MATLAB.

5. Разработаны методика и рекомендации по реализации алгоритмов обработки данных на программируемых логических интегральных схемах с архитектурой FPGA.

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