Разработка метода выбора средств реализации алгоритмов анализа последовательных потоков данных в специализированных системах обработки информации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Литвинская, Ольга Сергеевна

• Литвинская, Ольга Сергеевна
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Литвинская, Ольга Сергеевна

Введение.

1 Задача выбора средств реализации алгоритмов и анализ цифровых устройств обработки информации.

1.1 Область применения метода выбора средств реализации алгоритмов цифровой обработки информации.

1.2 Цифровые методы и средства реализации алгоритмов обработки сигналов.

1.2.1 Программные средства реализации алгоритмов цифровой обработки информации.

1.2.2 Микропроцессорные средства реализации алгоритмов цифровой обработки информации.

1.2.3 Средства реализации алгоритмов цифровой обработки информации на программируемой логике.

1.3 Виды алгоритмов цифровой обработки информации.

1.3.1 Управляющие алгоритмы.

1.3.2 Вычислительные алгоритмы.

1.3.3 Алгоритмы преобразования данных.

1.3.4 Вычислительный процесс как общее средство реализации

• алгоритма.

1.4 Формат представления потока данных.

1.5 Формирование последовательного потока цифровых данных.

1.5.1 Дискретизация аналогового сигнала по времени.

1.5.2 Квантование входного сигнала по уровню.

1.6 Оценочное время выполнения алгоритма.

1.7 Формулировка подхода к методу выбора и обоснования средства реализации заданного алгоритма обработки данных.

Выводы по разделу

2 Разработка количественных оценок сложности вычислительных операций.

2.1 Определение коэффициента сложности вычислительных операций

2.2 Коэффициент сложности модели операций пересылок данных.

2.2.1 Операции пересылок из регистра в регистр.

2.2.2 Операции обращения к памяти.

2.2.3 Операции обращения к стеку.

2.2.4 Операции ввода-вывода.

2.3 Коэффициент сложности модели операций преобразования данных.

2.3.1 Операции сдвига.

2.3.2 Логические операции.

2.3.3 Арифметические аддитивные операции.

2.3.4 Арифметические мультипликативные операции.

2.4 Коэффициент сложности модели операций передачи управления.

2.4.1 Обобщенная схема реализации операции передачи управления.

2.4.2 Условный и безусловный переход.

2.4.3 Операция множественного выбора.

2.4.4 Операции циклических повторений.

2.4.5 Операции вызова-возврата из подпрограмм.

Выводы по разделу 2.

Модели алгоритмов и метод выбора средства реализации

3.1 Обзор моделей вычислительных процессов.

3.2 Обобщенный параметр модели алгоритмов.

3.3 Частные нормированные параметры входного сигнала.

3.3.1 Динамический диапазон входного сигнала.

3.3.2 Скорость последовательного потока данных.

3.3.3 Преобразование входных данных.

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

3.5 Частные нормированные параметры модели алгоритмов.

3.5.1 Сложность алгоритма.

3.5.2 Число операций алгоритма.

3.5.3 Коэффициент реального времени.

3.6 Метод выбора средств реализации алгоритмов на основе целевой функции модели алгоритма.

Выводы по разделу

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

4.1 Назначение программного обеспечения.

4.2 Структура программного обеспечения.

4.3 Ввод данных.

4.4 Обработка данных.

4.5 Анализ результата.

4.6 Исследование зависимостей нормированных параметров от параметров входного сигнала и алгоритма.

4.6.1 Нормированный коэффициент динамического диапазона.

4.6.2 Нормированный коэффициент последовательного потока данных.

4.6.3 Нормированный коэффициент трансформации отсчетов.

4.6.4 Нормированный коэффициент сложности алгоритма.

4.7 Весовые коэффициенты для нормированных параметров.

4.8 Примеры использования программного обеспечения.

Выводы по разделу 4.

Введение диссертации (часть автореферата) на тему «Разработка метода выбора средств реализации алгоритмов анализа последовательных потоков данных в специализированных системах обработки информации»

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

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

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

Обоснованный выбор средств реализации алгоритмов обработки информации имеет существенное значение для устройств и систем, работающих с последовательными сигналами, - телекоммуникационных систем, систем сбора и обработки данных, технического зрения, охраны, отличающихся наличием последовательных каналов связи или последовательных каналов ввода данных. Специализированные системы ЦОИ при эксплуатации работают по фиксированным алгоритмам в отличие от универсальных ЭВМ. Применение специализированных систем ЦОИ обусловлено экономической целесообразностью, например, в телевизионных датчиках с функциями накопления, обнаружения и классификации изображений в системах технического зрения; в датчиках обнаружения и классификации целей в системах целеуказания или в технических системах охраны.

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

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

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

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

- разработка модели вычислительного процесса, позволяющей выделить значимые для выбора средств реализации характеристики алгоритма и входного последовательного потока данных;

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

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

Объектом исследования являются характеристики последовательных временных сигналов, алгоритмы и средства их обработки в специализированных устройствах цифровой обработки информации.

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

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

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

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

2. Разработан критерий выбора средств реализации алгоритмов в специализированных системах, обобщенная характеристика параметров входного сигнала и алгоритма.

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

4. Разработан метод выбора средства реализации алгоритмов но целевой функции, построенный с использованием обобщенной характеристики и коэффициента реального времени.

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

Реализация и внедрение результатов. Исследования проводились на кафедре «Вычислительные машины и системы» Пензенской государственной технологической академии.

Материалы диссертации нашли практическую реализацию при выполнении хоздоговорной НИР "Растр", выполненной по заказу ФГУП Научно-исследовательский и конструкторский институт радиоэлектронной техники (НИКИРЭТ) (г. Заречный Пензенской области).

Результаты диссертационной работы внедрены в НИКИРЭТ. Полученные в диссертационной работе результаты используются также в учебном процессе кафедры «Вычислительные машины и системы» Пензенской государственной технологической академии при обучении студентов по специальности 230101 "Вычислительные машины, комплексы, системы и сети" в дисциплине «Математическая логика и теория алгоритмов».

На защиту выносятся следующие положения:

1. Модель и способ получения количественной оценки сложности вычислительных операций.

2. Обобщенная характеристика, учитывающая параметры входного сигнала и алгоритма его обработки.

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

4. Целевая функция на основе обобщенной характеристики и коэффициента реального времени.

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

6. Программное средство решения задачи выбора средства реализации заданных алгоритмов.

Апробация работы. Основные результаты работы докладывались и обсуждались на: Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов», (г.Пенза, 27-28 мая 2003 ); V Всероссийской научно-технической конференции «Современные охранные технологии и средства обеспечения комплексной безопасности объектов» (г. Заречный Пензенской области, 18—20 мая, 2004 ); II Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов», (г. Пенза, 25-26 мая 2004 ); III Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов», (г. Пенза, 24-25 мая 2005 ); VII Международной конференции «Распознавание 2005» (г.Курск, 4-7 октября 2005 ).

Публикации. По теме диссертации опубликовано 13 научных работ, из них: 6 статьей, 6 тезисов докладов, 1 отчет rio НИР.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 61 наименования и двух приложений. Объем работы: 178 страниц текста, 57 рисунков, 14 таблиц, приложение А на 7страницах, приложение В на 2 страницах.

Заключение диссертации по теме «Теоретические основы информатики», Литвинская, Ольга Сергеевна

Выводы по разделу 4

1. Разработана структура программного обеспечения и выполнено проектирование в среде СУБД Microsoft Access 2003, использующее метод выбора средства реализации алгоритма, обоснованный в данной работе.

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

3. Получены граничные значения нормированных коэффициентов с помощью программного средства.

4. Разработана методика определения весовых коэффициентов, входящих в обобщенную характеристику и позволяющая учесть равномерное влияние всех нормированных коэффициентов на целевую функцию. Значение весовых коэффициентов представлено в таблице 4.7.

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

Заключение

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

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

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

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

3. Обосновано применение коэффициента реального времени /*Гп?рВ для оценки быстродействия алгоритма по времени выполнения операций Тт и времени ввода Твв отсчетов входного сигнала.

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

А) модели алгоритма р^п .

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

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

Список литературы диссертационного исследования кандидат технических наук Литвинская, Ольга Сергеевна, 2005 год

1. Смолов В. Б. Функциональные преобразователи информации. -Л.: Энергоиздат, 1981.-272 с.

2. Анисимов Б. В. Аналоговые вычислительные машины / Б. В. Анисгшов, В. Н. Голубкин М.: Высшая школа, 1971. - 356 с.

3. Сальников И. И. Растровые пространственно — временные сигналы в системах технического зрения: Учеб. пособие. Пенза: ЦНТИ, 1999 — 256 с.

4. Информатика: Учебник для вузов / Под ред. Н. В. Макаровой. -М.: Финансы и статистика, 1997. — 528 с.

5. Информатика. Базовый курс. 2-е издание / Под ред. С. В. Симоновича. — СПб.: Питер, 2003. 640 с.

6. Цилькер Б. Я. Организация ЭВМ и систем / Б. Я. Цилькер, С. А. Орлов. -СПб.: Питер, 2004. 668 с.

7. Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2003. - 208 с.

8. Сальников И. И. Микропроцессорные контроллеры. — Пенза: ПГУ, 2005.— 164 с.

9. Савельев А. Я. Основы информатики: Учеб. для вузов. М.:МГТУ им. Н.Э.Баумана, 2001. - 278 с.

10. Сальников И. И. Проектирование цифровых устройств обработки информации на основе ПЛИС: Учеб. пособие. Пенза: ПГУ, 2002.126 с.

11. Лысиков Б. Г. Арифметические и логические основы ЭЦВМ.

12. Минск: Вышейшая школа, 1974. 262 с.

13. Немнюгин С. A Turbo Pascal 7.0:практикум. СПб.: Питер, 2001. - 256 с.

14. Котельников В. А. Теория потенциальной помехоустойчивости.— М.: Госэнергоиздат, 1956. 225 с.

15. Баскаков С. И. Радиотехнические цепи и сигналы: Учеб. Для вузов по специальности «Радиотехника». — М.: Высш. шк., 2000. 357 с.

16. Алфёрова 3. В. Теория алгоритмов. М.: Статистика, 1973. - 368 с.

17. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.-233 с.

18. Соловьев Г. Н. Арифметические устройства ЭВМ. М.: Энергия, 1978. — 176 с.18.19,20,21.22,23,24,25,26