Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

METHOD OF SELECTION DECISION MEANS OF IMPLEMENTATION ALGORITHM DIGITAL INFORMATION PROCESSING BASED ON TRUST FUNCTIONAL

Litvinskaya O.S. 1 Salnikov I.I. 1
1 Penza State Technological Academy, Penza, Russia
The paper summarizes the results of applying decision theory to the problem of choosing means of implementing the algorithm of the designed information technology systems. An example of using the provisions of decision theory to select the means to implement the algorithm in the form of alternative devices for digital processing of information.
objective functional
decision making
choice of means to implement
Введение

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

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

Математические методы теории принятия решений разнообразны и основаны на представлении знаний в виде некоторых количественных данных, являющихся оценками предпочтений экспертов. Методы различаются способами представления и обработки предпочтений и часто приводят к разным результатам. В связи с этим возникает проблема выбора стратегии и метода решения конкретной задачи. Критерии для выбора метода в каждом случае будут зависеть от количества и качества доступной информации, от принятой постановки задачи и от ее окружения. Под окружением задачи понимают совокупность факторов внешней по отношению к объекту исследования среды (объект исследования определен на этапе постановки задачи), которые влияют на поведение этого объекта. Степень влияния может быть различной, например, есть задачи, достаточно безразличные к изменению параметров окружения и наоборот; сами изменения могут иметь различный характер (плавные, резкие, качественные и т.д.). Поэтому подход к задачам принятия решения с позиций прикладной математики включает достаточно трудные задачи выбора метода и обоснования полученных результатов [1].

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

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

Постановка задачи

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

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

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

В случае рассмотрения ряда задач из области проектирования ИТС, получим множество частных критериальных функций:  при k =1,2,...,n. Поскольку речь идет о детерминированной связи между множеством Х и множеством Y, то критериальная функция f трансформируется в некоторую функцию J, заданную на множестве Х и являющуюся суперпозицией φ и f:

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

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

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

,

где n - количество интервалов.

В результате приходим к распространенной в приложениях многокритериальной модели принятия решений или задачи  многокритериальной оптимизации вида

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

Многокритериальная модель выбора

На основе анализа ряда методов многокритериальной оптимизации (метод главного критерия, метод линейной свертки, метод максиминной свертки) [1] предлагается метод объективного выбора варианта средств реализации алгоритма ЦОИ при проектировании ИТС с последовательными потоками данных. Метод основан на формировании модели вычислительного процесса и сравнении модели с реальными объектами.

Формирование модели вычислительного процесса осуществляется следующими этапами:

1) выделение параметров модели. Задается множество исходных параметров, принадлежащих множеству альтернатив: параметры сигнала и алгоритма ЦОИ , определяются их максимальные значения :

;

2) нормирование параметров  по максимальным значениям , при этом получаются безразмерные коэффициенты сигналов и алгоритмов ;

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

4) формирование целевого функционала (ЦФ) модели выбора . Вид функционала определяется зависимостью от критериальных функции  и :

где m - количество частных критериальных функций.

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

ЦФ ограничивается двумя условиями:

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

- вид ЦФ может быть монотонным, унимодальным, либо полимодальным;

5) для модели выбора уточняется множество альтернативных вариантов реализации: ;

6) для аналитической модели ЦФ выполняется разделение значений на интервалы, соответствующие вариантам реализации ИТС. Множество вариантов реализации  определяет совокупность интервалов значений целевого функционала :

при этом интервалу значений целевого функционала  приписывается соответствующий вариант реализации . Если неизвестно преобладание какого-либо варианта реализации, то выбирается равномерное разделение области допустимых значений ЦФ на n интервалов;

7) принятие решения для многокритериальной модели в условиях определенности формулируется следующим образом: попадание максимума ЦФ в интервал значений будет определять вариант реализации алгоритма ЦОИ. Процесс принятия решения можно записать в виде выражения:

.

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

Сферой применения предложенного метода выбора являются следующие направления:

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

- выбор средств реализации алгоритмов ЦОИ. В качестве средств реализации рассматривались программные средства, микроконтроллерные и ПЛИС [4];

- выбор микроконтроллеров реализовывал избрание одного из 8, 16 и 32-х - разрядных микроконтроллеров [5];

- выбор средств реализации телевизионных технических средств охраны на основе оценки сложности их структуры[6].

Метод целевого функционала применительно к выбору микроконтроллера

Рассмотрим предложенный метод применительно к выбору микроконтроллеров. В качестве исходных параметров были выделены следующие: динамический диапазон входного сигнала DS , влияющий на формат представления входных данных; скорость потока данных, характеризуемая количеством отсчетов обрабатываемого сигнала в единицу времени ПS; вид преобразования в виде параметра трансформации отсчетов NТО; вид алгоритма ВА, параметр сложности алгоритма CАЛ, количество вычислительных операций NОП , время выполнения операций в алгоритме ТВО, время реализации алгоритма РВ, а также параметры, влияющие на выбор непосредственно микроконтроллеров: производительность РМ, разрядность шины данных NШД, разрядность шины адреса NША, и объем внутренней памяти программ микроконтроллера RМ. В результате нормирования получили множество безразмерных коэффициентов:

.

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

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

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

,

где  - число уровней квантования;  - количество разрядов входных данных;  - разрядность вычислительного средства;

            - критериальная функция коэффициента последовательного потока данных:

где  - максимальная частота,  - минимальное значение максимальной частоты,  - динамический диапазон сигнала, НS/N  - отношение сигнал-шум,  - минимальный уровень  сигнала;

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

.

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

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

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

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

С учетом выше изложенного частная критериальная функция коэффициента трансформации отсчетов примет вид:

;

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

,

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

Существенные параметры представлены критериальной функцией реального времени и коэффициентом вида алгоритмов:

- критериальная функция коэффициента реального времени, учитывающая заданное время выполнения алгоритма по отношению ко времени ввода:

где  - заданное время выполнения алгоритма;  - время поступления входных отсчетов;

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

Частные критериальные функции объединяются обобщающей величиной:

.

Далее формируется ЦФ в виде выражения:

В качестве альтернатив взяты микроконтроллеры малой разрядности (8),  микроконтроллеры средней разрядности (16) и микроконтроллеры большой разрядности (32). Область значений ЦФ разбивается равномерно на три зоны, представляющие собой группы средств реализации. Вопрос выделения зон выбора относится к области экспертных оценок. Необходимо определить приоритеты объектов выбора, учесть их характеристики при распределении значений ЦФ. В работе используется равномерное распределение участков зон, начиная с микроконтроллеров малой разрядности.

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

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

Рецензенты:

  • Федотов Н.Г., д.т.н., профессор, зав. кафедрой экономической кибернетики Пензенского государственного университета, г. Пенза.
  • Светлов А.В., д.т.н., профессор зав. кафедрой радиотехники и радиоэлектронных систем Пензенского государственного университета, г. Пенза.

Работа получена 03.10.2011.