Разработка эффективных форматов микрокоманд для различных способов микропрограммирования
Общие сведения об управляющих автоматах, построенных на основе принципа программируемой логики. Программно-вычислительный комплекс разработки эффективных форматов микрокоманд для различных способов кодирования. Алгоритмы кодирования операционной части.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 26.06.2012 |
| Размер файла | 2,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ВВЕДЕНИЕ
Функция любого управляющего автомата -- генерирование последовательности управляющих слов (микрокоманд), определенной реализуемым алгоритмом с учетом значений осведомительных сигналов. Если заранее разместить в запоминающем устройстве все необходимые для реализации заданного алгоритма (группы алгоритмов) микрокоманды, а потом выбирать их из памяти в порядке, предусмотренном алгоритмом (с учетом значения осведомительных сигналов), то получим управляющий автомат, структура которого слабо зависит от реализуемых алгоритмов, а поведение в основном определяется содержимым запоминающего устройства.
При проектировании управляющего автомата с программируемой логикой (УА) необходимо выбрать формат (форматы) микрокоманд (микрокоманды), способы кодирования микроопераций и адресации микрокоманд.
Эти параметры должны выбираться таким образом, чтобы максимально соответствовать решению поставленной задачи - упрощению реализации, снижению стоимости или же быстродействию управляющего автомата.
Выбор способа кодирования определяется требованиями к объему хранимых микрокоманд, быстродействию автомата, а также данным о количестве различных МК и МО в микропрограмме и ее структуре (степени разветвленности алгоритма).
Точных рекомендаций по выбору способа кодирования для каждой конкретной микропрограммы не существует и поэтому решения, принимаемые разработчиком, носят субъективный характер. Один из возможных подходов к решению этого этапа заключается в просмотре качественной и предварительной количественной оценке в соответствии с критерием оптимальности, нескольких вариантов кодирования. Однако этот путь связан со значительными трудозатратами. Определение формата МК позволяет уточнить принятые решения с помощью некоторых количественных оценок, в частности по разрядности операционной и адресной частей МК.
Дипломная работа посвящена разработке программно вычислительного комплекса предназначенного для разработки эффективных форматов микрокоманд для различных способов микропрограммирования.
В первом разделе изложена постановка задачи проекта, его основные цели, входные и выходные данные.
Во втором разделе дается обзор литературных источников, включающий общие сведения об управляющих автоматах, построенных на основе принципа программируемой логики, способах адресации микрокоманд, перечислены алгоритмы кодирования операционной части.
В третьем разделе изложен системный анализ объекта проектирования, выполненный в соответствии с девятью его принципами.
В четвертом разделе представлен вариантный анализ алгоритмов микропрограммирования в соответствии с выбранными критериями, такими как быстродействие, длина операционной части микрокоманды и сложность реализации формирователя сигналов микроопераций.
В пятом разделе рассматривается концептуальная модель программно-вычислительного комплекса, уделяется особое внимание определению объектов программирования и их атрибутам.
Шестой раздел посвящен описанию программы, включающий в себя описание основных классов, их полей и методов, а так же описание алгоритмов.
Седьмой раздел содержит результаты тестирования программно-вычислительного комплекса на различных примерах.
В восьмом разделе производится расчет основных технико-экономических обоснований проекта, доказывающих экономическую эффективность разрабатываемого проекта.
Девятый раздел посвящен охране труда. В этом разделе производится анализ условий труда в рабочем помещении и проводится расчет естественного освещения.
В десятом разделе, посвященном безопасность в чрезвычайных ситуациях, необходимо оценить радиационную обстановку на объекте при загрязнении радиоактивными веществами после аварии на АЭС.
1. ПОСТАНОВКА ЗАДАЧИ
1.1 Цель проектирования
Необходимо разработать программно-аппаратный комплекс, предназначенный для разработки эффективных форматов микрокоманд для различных способов микропрограммирования.
Программно-вычислительный комплекс должен следовать главным целям:
- кодирование набора микрокоманд с указанным списком микроопераций различными видами микропрограммирования;
- выдача характеристик форматов микрокоманд, таких как длина формата, сложность кодирования;
- выводить статистические данные в виде наглядных графиков.
Программно-вычислительный комплекс может быть использован на практических занятиях по дисциплине «Цифровые ЭВМ» в ВУЗах и в качестве тренажера для самостоятельной работы всех заинтересованных лиц.
1.2 Описание исходных данных
Входные данные представлены списком микрокоманд и входящих в нее микроопераций, перечисленных через запятую.
Пример записи:
Y1=y2,y7,y1,y9,y11,y5
Исходными данными к проекту являются схема алгоритма функционирования управляющего автомата, список и содержание микрокоманд, способы микропрограммирования. Критериями для вариантного анализа являются длина операционной части микрокоманды, сложность формирователя сигналов микроопераций, быстродействие.
1.3 Описание выходных данных
Конечная цель проектирования - создание программно-вычислительного комплекса, реализующего алгоритмы оптимизации структуры операционной части микрокоманд и вывод статистических данных на экран.
Выходные данные представляют собой следующее:
- список исходных незакодированных микроопераций;
- формат микрокоманд, закодированных одним из способов микропрограммирования;
- список булевых функций для ФСМО;
- список булевых функций для ФСМО, минимизированных для вертикального способа кодирования;
- статистические данные.
2. ОБЗОР ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ ПО ТЕМЕ ПРОЕКТИРОВАНИЯ
2.1 Общие сведения об управляющих автоматах (УА), построенных на основе принципа программируемой логики
В основе идеи микропрограммирования (использования принципа «программируемой» логики) лежит тот факт, что для инициирования любой микрооперации (МО) или их совокупности достаточно сформировать управляющее двоичное слово, в котором каждый бит соответствует одному управляющему сигналу, инициирующему конкретную МО. Такое управляющее слово называют микрокомандой (МК). Последовательность МК, реализующих определенный алгоритм функционирования управляющего автомата (УА), образует микропрограмму (МП) [1].
Характерной особенностью УА с программируемой логикой является хранение МП в специализированном постоянном запоминающем устройстве (ПЗУ), называемом памятью микропрограмм (ПМП). Обобщенная структура УА с хранимой в памяти логикой изображена на рисунке 2.1.
Рисунок 2.1 - Обобщенная структура УА с программируемой логикой
В состав устройства кроме ПМП входят:
- регистр микрокоманды (РМК);
- регистр адреса микрокоманды (РАМК);
- формирователь сигналов микроопераций (ФСМО);
- формирователь адреса микрокоманды (ФАМК).
Запуск микропрограммы выполнения того или иного вычислительного процесса осуществляется в результате подачи на РАМК «начального адреса» МП (адреса первой микрокоманды конкретной МП) и последующего выбора текущей МК по сигналу ЧтМК (чтение МК). Выбранная МК попадает на РМК.
Каждая МК в общем случае должна содержать операционную (М) и адресную (Х . А) части. Код операционной части поступает на ФСМО, на выходе которого формируются управляющие сигналы y1, y2,…, ym, инициирующие выполнение МО в обрабатывающем устройстве. Код адресной части МК состоит из двух полей. Первая часть адресного кода (X), задающая номер проверяемого логического условия, подается на ФАМК. Формирователь адреса среди поступивших на его информационные входы осведомительных сигналов x1, x2, …, xn выбирает xX (сигнал с номером, заданным полем X МК) и в зависимости от его значения (0 или 1) формирует адрес следующей исполняемой МК, который фиксируется в РАМК.
Кодовые комбинации в поле микроопераций (поле М) в микрокоманде могут быть сформированы в соответствии с тремя различными способами микропрограммирования:
- горизонтальным;
- вертикальным;
- смешанным [2].
2.2 Адресация микрокоманд
Исходными данными для проектирования УА является микропрограмма, представленная, например, в форме ГСА. Каждая операторная вершина должна реализоваться в один такт машинного времени, причем после операторной вершины в ГСА может следовать:
- операторная вершина;
- условная вершина, оба выхода которой или один из них соединены с операторными вершинами;
- цепочка из двух или более условных вершин, выходы которых соединены с условными вершинами.
В первом случае осуществляется безусловный переход к следующей микрокоманде, и адрес этой единственной микрокоманды (А1) должен размещаться в поле адреса выполняемой микрокоманды [3].
Во втором случае необходимо сделать выбор одного из двух возможных следующих адресов. В поле адреса микрокоманды следует разместить:
- номер х логического условия, по значению которого осуществляется выбор;
- адрес А1 микрокоманды, которая будет выполняться, если указанное условие истинно;
- адрес АО микрокоманды, которая будет выполняться, если указанное условие ложно.
В третьем случае количество проверяемых в микрокоманде условий и адресов переходов может быть произвольным, в т. ч. и достаточно большим. В этом случае длина микрокоманды может быть весьма велика.
При выборе формата микрокоманды нужно учитывать следующие обстоятельства:
- следует эффективно использовать разряды поля, обеспечив по возможности его минимальную длину;
- желательно ограничиться единственным форматом микрокоманды, в крайнем случае, выбирать минимально возможное разнообразие форматов.
Справедливость первого требования очевидна. Относительно второй предпосылки можно заметить, что при большом числе форматов соответственно усложняется схема декодирования микрокоманды.
Следовательно, если в рамках одного формата микрокоманды обеспечить реализацию всех возможных вариантов следования вершин, то в третьем случае потребуется предусмотреть в микрокоманде несколько полей номеров логических условий и столько же плюс одно поле адресов микрокоманд. Учитывая, что в большинстве алгоритмов длинные цепочки логических вершин встречаются довольно редко, организация подобного формата микрокоманды будет весьма неэффективна -- ведь для второго случая будут использоваться только одно поле логического условия и два поля адреса, а для первого случая -- только одно поле адреса [1].
Чаще всего в быстродействующих УА используется формат микрокоманды, приведенный на рисунке 2.2. Такой способ адресации микрокоманд принято называть принудительным, здесь явно указываются оба возможных адреса перехода, причем расположение микрокоманд в ячейках памяти может быть произвольным.
|
Микрооперация (МО) |
Логическое условие (ЛУ) |
Адрес микрокоманды |
Рисунок 2.2 - Формат МК при принудительной адресации
Особенности этого способа адресации в том, что здесь в обязательном порядке присваивается адрес следующей исполняемой микрооперации. Выполнение микрокоманды предполагает в этом случае исполнение микрооперации, включенной в микрокоманду, анализ проверки логического условия и передачу управления на четный или нечетный адрес, который зависит от сигнала, выработанного формирователем адресов микрокоманды. Если в ГСА имеется большое число линейных участков и, следовательно, безусловных переходов, то применение принудительной адресации ведет к неэффективному использованию памяти. В таком случае следует использовать другой тип адресации - естественную. Формат микрокоманды представлен на рисунке 2.3.
Рисунок 2.3 - Форматы МК при естественной адресации
В данном случае В - это бит-маркер, который равен 1, если микрокоманда управляющая и равен 0, если микрокоманда операционная [2].
2.3 Алгоритмы кодирования операционной части
2.3.1 Горизонтальное кодирование
При горизонтальном способе кодирования МО (рисунок 2.4) под каждый управляющий сигнал yi (i=1, 2,…, m) в операционной (М) части МК выделяется один (свой) двоичный разряд, что позволяет в рамках одной МК формировать любые сочетания управляющих сигналов. ФСМО для такого способа кодирования обладает наименьшей стоимостью и минимальным временем срабатывания.
Рисунок 2.4 - Горизонтальное кодирование
Недостаток - линейный рост длины поля операционной части при увеличении общего количества выполняемых МО.
Общее число микроопераций в ЭВМ может достигать нескольких сотен, поэтому, под операционную часть требуется отводить большое количество разрядов. Горизонтальное кодирование применяется при относительно небольшом количестве микроопераций [1].
2.3.2 Вертикальное кодирование
При вертикальном способе кодирования (рисунок 2.5) каждой различимой совокупности МО, включенной в ту или иную МК, присваивается позиционный код минимальной длины , где - количество различимых по операционной части МК. ФСМО в этом случае представляет собой комбинационную схему (КС), реализующую m булевых функций от k переменных.
Рисунок 2.5 - Вертикальный способ кодирования
Этот способ кодирования требует наименьшего количества разрядов в операционной части микрокоманды. Однако при этом необходимо использовать дешифратор на большое количество выходов. При вертикальном кодировании в микрокоманде указывается лишь одна микрооперация, что приводит к увеличению длины микропрограмм [1].
2.3.3 Горизонтально-вертикальное кодирование
При горизонтально-вертикальном способе кодирования МО (рисунок 2.6) все множество МО разбивается на подмножества, в каждое из которых включаются только несовместимые по времени исполнения МО. Внутри каждого подмножества сигналы управления кодируются вертикальным способом. Подмножества в операционной части МК располагаются по горизонтальному принципу. Другое название этого способа - кодирование раздельными полями. Расшифровка кодов МО осуществляется ФСМО, представляющим собой R дешифраторов (по одному на каждое выделенное подмножество МО).
Рисунок 2.6 - Горизонтально-вертикальное кодирование
Каждому полю соответствует свой дешифратор микроопераций. Группа содержит те микрооперации, которые не встречаются вместе в одной микрокоманде. Из группы может выполниться только одна микрооперация. Одновременно выполняемые микрооперации в такте размещаются в разные группы. Этот способ кодирования обеспечивает меньшую гибкость, чем горизонтальное кодирование. Изменение хотя бы одной микрокоманды может потребовать нового разбиения полей [1].
2.3.4 Вертикально-горизонтальное кодирование
При вертикально-горизонтальном способе кодирования (рисунок 2.7) все множество МО также делится на подмножества, однако в каждое подмножество включаются только те МО, которые связаны между собой отношением совместимости по времени исполнения (встречаются вместе хотя бы в одной МК). Для всех этих подмножеств выделяется в операционной части МК одно поле М3, длина которого определяется максимальным количеством МО в подмножествах. Принцип кодирования МО в поле М3 - горизонтальный. Идентифицирующее поле М2 заполняется вертикальным кодом номера подмножества, зафиксированного в поле М3. Отличительной особенностью вертикально-горизонтального способа кодирования является требование несовместимости выделенных подмножеств МО между собой. Удовлетворить этому требованию можно, выделив наиболее часто встречающиеся в МК микрооперации в отдельное подмножество (универсальную группу). Кодирование МО универсальной группы - горизонтальное. Код универсальной группы помещается в поле М1 операционной части МК. Другое название этого способа - кодирование несовместимыми подмножествами МО.
Рисунок 2.7 - Вертикально-горизонтальный способ кодирования
Вертикально-горизонтальное кодирование позволяет строить оптимальные программы, как по длине микрокоманды, так и по длине микропрограммы. Но при этом теряется стройность микропрограммирования, так как используется косвенное кодирование. Схемная реализация является наиболее сложной из всех способов формирования управляющих сигналов [1].
2.4 Оценка трудоемкости при кодировании различными способами
Горизонтальное кодирование:
а) определяется разрядность операционной части микрокоманды, на каждую микрооперацию отводится один разряд. Длина кода К:
К = m, где m - общее число микроопераций.
Вертикальное кодирование:
а) определяется разрядность операционной части;
б) каждой микрокоманде присваивается неизбыточный двоичный код. Длина кода К
К =
где - количество различимых по операционной части микрокоманд.
Горизонтально-вертикальное кодирование:
а) определяется число групп, которое определяется оптимальным количеством одновременно выполняемых микроопераций;
б) определяется число функциональных сигналов в конкретной группе, одновременно выполняемые микрооперации находятся в различных группах;
в) определяется разрядность каждой группы при вертикальном кодировании;
г) определяется разрядность операционной части микрокоманды для всех групп.
Вертикально-горизонтальное кодирование:
а) определяется число функциональных сигналов в группе, которая может быть определено числом одновременно выполняемых микроопераций при горизонтальном кодировании;
б) определяется возможность сочетания микроопераций и разрядность, соответствующая минимальному числу микроопераций в группе;
в) определяется число групп, которое определяется совокупностью микроопераций;
г) определяется разрядность вертикального кодирования числа групп;
д) определяется разрядность операционной части микрокоманды при горизонтальном кодировании микрооперации в группе и вертикальном кодировании номера группы. В смешанном микропрограммировании длина любого поля К =, длина операционной части m = ?mi .
3. СИСТЕМНЫЙ АНАЛИЗ АППАРАТНО-ПРОГРАММНОГО КОМПЛЕКСА
Основным достоинством управляющего автомата с программируемой логикой является его универсальность, а значит, относительная простота проектирования аппаратных средств. Однако это достигается за счет увеличения сложности программного (микропрограммного) обеспечения, что приводит к снижению производительности и росту затрат памяти. Целью работы является исследование форматов микрокоманд для различных способов микропрограммирования, что позволит наиболее рационально использовать ресурсы памяти устройства, что в свою очередь повысит быстродействие выполнения задач, а так же наиболее оптимальную структуру управляющего устройства.
3.1 Принцип конечной цели
Для выполнения проекции данного принципа на проектируемый программный продукт необходимо представить его в виде «черного ящика» (рисунок 3.1). Тогда входными данными, вектор X, будут являться наборы микрокоманд. Выходными данными, вектор Y, в этом случае будут являться статистические данные. Управляющие параметры, вектор Z - способы кодирования микроопераций.
Рисунок 3.1 - Проектируемая система в виде «черного ящика»
Тогда для выполнения равенства Y=F(X,Z) проектируемая система должна выполнять следующие функции (в совокупности представляющие собой функцию F):
- кодирование наборов микрокоманд;
- выявление ошибок в исходных данных;
- анализ результатов;
- сбор статистических данных.
3.2 Принцип единства
На основании выделенных функций проектируемой системы можно выделить следующие подсистемы:
- подсистема взаимодействия с пользователем;
- подсистема кодирования микрокоманд;
- подсистема выявления ошибок;
- подсистема анализа результатов;
- подсистема ведения статистики.
3.3 Принцип связности
Совокупность подсистем проектируемой программной системы и их связей - данными, которыми эти подсистемы обмениваются друг с другом и с внешней средой, - образует ее структуру. Структура проектируемой системы представлена на рисунке 3.2.
Рисунок 3.2 - Структура проектируемой системы
3.4 Принцип модульности
В проектируемой системе целесообразно выделить следующие модули:
- интерфейсный модуль;
- модуль кодирования;
- модуль выявления ошибок;
- модуль анализа результатов;
- модуль ведения статистики.
3.5 Принцип иерархии
Объектом проектирования является аппаратно-программный комплекс, который содержит головную программу, а так же ее подуровни (рисунок 3.3).
Рисунок 3.3 - Иерархическая схема программы.
3.6 Принцип функциональности
Функции системы в целом рассмотрены в связи с принципом конечной цели. Рассмотрим функции, входные и выходные данные выделенных подсистем.
Основной функцией подсистемы взаимодействия с пользователем является считывание набора микрокоманд с их последующей обработкой.
Подсистема кодирования должна закодировать набор входящих микрокоманд одним из способов микропрограммирования - горизонтальным, вертикальным, вертикально-горизонтальным или горизонтально-вертикальным.
Подсистема выявления ошибок служит для проверки корректности введенных данных. Если заданный набор микрокоманд корректен, то данные направляются на последующую обработку, т.е. кодируются. В противном случае пользователю выдается сообщение об ошибке.
Подсистема анализа результатов предполагает анализ полученных данных, а так же оценку сложности кодирования.
Подсистема сбора статистических данных собирает проанализированные данные, а так же сообщения об ошибках, на выходе - вывод полученных данных на экран.
3.7 Принцип развития
Проектируемая система может быть расширена следующим образом:
- задание способа адресации микрокоманды;
- считывание заданной граф-схемы алгоритма и преобразование ее в набор микрокоманд.
3.8 Принцип централизации и децентрализации
Принцип централизации и децентрализации в данной системе не применим, так как в ней используется только централизованное управление смены вида кодирования микрооперации.
3.9 Принцип учета неопределенности и случайностей
В проектируемой системе следует предусмотреть возможность реакции на некорректные с точки зрения системы действия оператора, например:
- ввод некорректных исходных данных;
- удаление рабочих файлов;
- отсутствие соответствующего программного обеспечения.
4. ВАРИАНТНЫЙ АНАЛИЗ ПЛАТФОРМ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ
Для выбора протокола используется метод анализа иерархии (МАИ). МАИ является систематической процедурой для иерархического представления элементов, определяющих суть любой проблемы. Метод состоит в декомпозиции проблемы на всё более простые составные части и дальнейшей обработки последовательных суждений лица принимающего решение по парным сравнениям. В результате может быть выражена относительная степень (интенсивность) взаимодействия элементов в иерархии. В результате получаются численные выражения этих суждений. МАИ включает в себя процедуры синтеза множественных суждений, получение приоритетных критериев и нахождение альтернативных решений. Полученные знания являются оценками в шкале отношений и соответствуют жёстким оценкам [15].
Для начала выделим критерии, по которым можно выбирать тот или иной способ микропрограммирования:
- быстродействие (А1);
- сложность реализации программы (А2);
- длина операционной части МК (А3);
- объем занимаемой памяти (А4);
- сложность реализации ФСМО (А5);
На основе этих критериев построим матрицу парных сравнений второго уровня, где строки и столбцы составляют выбранные критерии. Сравнение критериев проведём по шкале относительной важности согласно с таблицей 4.1:
Таблица 4.1 - Оценка критериев
|
Интенсивность относительной важности |
Определение |
|
|
1 |
Равная важность |
|
|
3 |
Умеренное превосходство одного над другим |
|
|
5 |
Существенное или сильное превосходство |
|
|
7 |
Значительное превосходство |
|
|
9 |
Очень сильное превосходство |
|
|
2,4,6,8 |
Промежуточные значения между двумя соседними суждениями |
Таким образом, получим матрицу суждений, приведённую в таблице 4.2.
Таблица 4.2 - Матрица парных сравнений 2-го уровня.
|
Критерий |
Быстродействие |
Сложность реализации программы |
Длина операционной части МК |
Объем занимаемой памяти |
Сложность реализации ФСМО |
|
|
Быстродействие |
1 |
3 |
7 |
8 |
5 |
|
|
Сложность реализации программы |
1/3 |
1 |
6 |
8 |
4 |
|
|
Длина операционной части МК |
1/7 |
1/6 |
1 |
3 |
1/6 |
|
|
Объем занимаемой памяти |
1/8 |
1/8 |
1/3 |
1 |
1/6 |
|
|
Сложность реализации ФСМО |
1/5 |
1/4 |
6 |
6 |
1 |
4.1 Оценка критериев (второй уровень иерархии)
4.1.1 Синтез локальных приоритетов для матрицы парных сравнений 2-го уровня
Вычислим вектор локальных приоритетов для составленной матрицы, используя формулу
, где и (4.1)
Найдем сумму всех значений по формуле
, где (4.2)
Рассчитаем значения компонент вектора локальных переменных по формуле
, где (4.3)
Проверим нормализацию полученных значений по формуле
(4.4)
При заданной точности вычисление вектора локальных приоритетов произведено без погрешности.
4.1.2 Исследование на согласованность матрицы парных сравнений 2-го уровня
Необходимо провести анализ согласованности матрицы второго уровня. Для этого вычислим сумму элементов каждого столбца матрицы суждений второго порядка по формуле
, где (4.6)
Далее определим наибольшее собственное значение матрицы суждений по формуле
(4.7)
Используя полученные данные, определим индекс согласованности (ИС) по формуле
, где n - размерность матрицы (4.8)
Используя индекс согласованности (ИС) вычислим отношение согласованности (ОС), по формуле
, где СС - случайная согласованность (4.9)
СС - случайная согласованность, является табличным значением для матрицы конкретного размера, и берётся из таблицы 4.3.
Таблица 4.3 - Таблица случайной согласованности.
|
Размерность квадратной матрицы |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
СС |
0 |
0 |
0.58 |
0.9 |
1.12 |
1.24 |
1.32 |
1.41 |
1.45 |
1.49 |
Для матрицы размерностью 5x5 СС=1.12.
Так как критерием хорошей согласованности является отношение по величине составляющее менее 10%, то можно сделать вывод, что матрица является согласованной.
4.1.3 Анализ результатов оценки критериев
По полученным значениям вектора локальных приоритетов можно сделать выводы о важности критериев и отсортировать критерии по их значимости.
Ниже приведены критерии в порядке убывания их приоритетов:
- быстродействие (0.5404);
- сложность реализации программы (0.323);
- длина операционной части МК (0.0579);
- объем занимаемой памяти (0.0353);
- сложность реализации ФСМО (0.0434).
Исходя из этих данных, можно сделать вывод, что критерий «Быстродействие» является наиболее важным критерием. Критерий «Сложность реализации программы» также имеет большой приоритет. Остальные критерии являются малозначимыми.
4.2 Оценка альтернатив (третий уровень иерархии)
Проведем сравнительную оценку каждой из альтернатив относительно каждого из критериев. Обозначение видов кодирования: А - горизонтальное, Б - вертикальное, В - горизонтально-вертикальное, Г - вертикально-горизонтальное. Получим матрицы третьего уровня иерархии размерностью n=4. Для каждой из матриц, вычислим векторы локальных приоритетов xi и отношения согласованности ОС.
4.2.1 Критерий «Быстродействие»
Таблица 4.4 - Матрица парных сравнений для критерия «Быстродействие»
|
Быстродействие |
А |
Б |
В |
Г |
|
|
А |
1 |
3 |
5 |
9 |
|
|
Б |
1/3 |
1 |
4 |
5 |
|
|
В |
1/5 |
1/4 |
1 |
2 |
|
|
Г |
1/9 |
1/5 |
1/2 |
1 |
Вычислим собственный вектор локальных приоритетов матрицы, используя формулу (4.1):
Найдем сумму всех значений по формуле (4.2):
Рассчитаем значения компонент вектора локальных переменных по формуле (4.3):
; ;
Проверим нормализацию полученных значений по формуле (4.4):
При заданной точности вычисление вектора локальных приоритетов произведено без погрешности.
Для проверки согласованности вычислим сумму элементов каждого из столбцов матрицы по формуле (4.6):
Определим наибольшее собственное значение матрицы суждений по формуле (4.7):
Используя полученные данные, определим индекс согласованности (ИС) по формуле (4.8):
Вычислим отношение согласованности (ОС) по формуле (4.9):
Для матрицы размерностью 4x4 СС=0.9.
Так как критерием хорошей согласованности является отношение по величине составляющее менее 10%, то можно сделать вывод, что матрица является согласованной.
4.2.2 Критерий «Сложность реализации программы»
Таблица 4.5 - Матрица парных сравнений для критерия «Сложность реализации программы».
|
Сложность |
А |
Б |
В |
Г |
|
|
А |
1 |
1/3 |
1/7 |
1/8 |
|
|
Б |
3 |
1 |
1/4 |
1/5 |
|
|
В |
7 |
4 |
1 |
1/3 |
|
|
Г |
8 |
5 |
3 |
1 |
Вычислим собственный вектор локальных приоритетов матрицы, используя формулу (4.1):
Найдем сумму всех значений по формуле (4.2):
Рассчитаем значения компонент вектора локальных переменных по формуле (4.3):
;;
Проверим нормализацию полученных значений по формуле (4.4):
При заданной точности вычисление вектора локальных приоритетов произведено без погрешности.
Для проверки согласованности вычислим сумму элементов каждого из столбцов матрицы по формуле (4.6):
Определим наибольшее собственное значение матрицы суждений по формуле (4.7):
Используя полученные данные, определим индекс согласованности (ИС) по формуле (4.8):
Вычислим отношение согласованности (ОС) по формуле (4.9):
Для матрицы размерностью 4x4 СС=0.9.
Так как критерием хорошей согласованности является отношение по величине составляющее менее 10%, то можно сделать вывод, что матрица является согласованной.
4.2.3 Критерий «Длина операционной части МК»
Таблица 4.6 - Матрица парных сравнений для критерия «Длина операционной части МК».
|
Длина МК |
А |
Б |
В |
Г |
|
|
А |
1 |
1/9 |
1/5 |
1/3 |
|
|
Б |
9 |
1 |
3 |
5 |
|
|
В |
5 |
1/3 |
1 |
3 |
|
|
Г |
3 |
1/5 |
1/5 |
1 |
Вычислим собственный вектор локальных приоритетов матрицы, используя формулу (4.1):
Найдем сумму всех значений по формуле (4.2):
Рассчитаем значения компонент вектора локальных переменных по формуле (4.3):
; ;
Проверим нормализацию полученных значений по формуле (4.4):
При заданной точности вычисление вектора локальных приоритетов произведено без погрешности.
Для проверки согласованности вычислим сумму элементов каждого из столбцов матрицы по формуле (4.6):
Определим наибольшее собственное значение матрицы суждений по формуле (4.7):
Используя полученные данные, определим индекс согласованности (ИС) по формуле (4.8):
Вычислим отношение согласованности (ОС) по формуле (4.9):
Для матрицы размерностью 4x4 СС=0.9.
Так как критерием хорошей согласованности является отношение по величине составляющее менее 10%, то можно сделать вывод, что матрица является согласованной.
4.2.4 Критерий «Объем занимаемой памяти»
Таблица 4.7 - Матрица парных сравнений для критерия «Объем занимаемой памяти»
|
Объем памяти |
А |
Б |
В |
Г |
|
|
А |
1 |
1/8 |
1/7 |
1/6 |
|
|
Б |
8 |
1 |
3 |
4 |
|
|
В |
7 |
1/3 |
1 |
2 |
|
|
Г |
6 |
1/4 |
1/2 |
1 |
Вычислим собственный вектор локальных приоритетов матрицы, используя формулу (4.1):
Найдем сумму всех значений по формуле (4.2):
Рассчитаем значения компонент вектора локальных переменных по формуле (4.3):
; ;
Проверим нормализацию полученных значений по формуле (4.4):
При заданной точности вычисление вектора локальных приоритетов произведено без погрешности.
Для проверки согласованности вычислим сумму элементов каждого из столбцов матрицы по формуле (4.6):
Определим наибольшее собственное значение матрицы суждений по формуле (4.7):
Используя полученные данные, определим индекс согласованности (ИС) по формуле (4.8):
Вычислим отношение согласованности (ОС) по формуле (4.9):
Для матрицы размерностью 4x4 СС=0.9.
Так как критерием хорошей согласованности является отношение по величине составляющее менее 10%, то можно сделать вывод, что матрица является согласованной.
алгоритм кодирование микрокоманда
4.2.5 Критерий «Сложность реализации ФСМО »
Таблица 4.8 - Матрица парных сравнений для критерия «Сложность реализации ФСМО»
|
Сложность ФСМО |
А |
Б |
В |
Г |
|
|
А |
1 |
8 |
5 |
6 |
|
|
Б |
1/8 |
1 |
1/6 |
1/5 |
|
|
В |
1/5 |
6 |
1 |
4 |
|
|
Г |
1/6 |
5 |
1/4 |
1 |
Вычислим собственный вектор локальных приоритетов матрицы, используя формулу (4.1):
Найдем сумму всех значений по формуле (4.2):
Рассчитаем значения компонент вектора локальных переменных по формуле (4.3):
; ;
Проверим нормализацию полученных значений по формуле (4.4):
При заданной точности вычисление вектора локальных приоритетов произведено без погрешности.
Для проверки согласованности вычислим сумму элементов каждого из столбцов матрицы по формуле (4.6):
Определим наибольшее собственное значение матрицы суждений по формуле (4.7):
Используя полученные данные, определим индекс согласованности (ИС) по формуле (4.8):
Вычислим отношение согласованности (ОС) по формуле (4.9):
Для матрицы размерностью 4x4 СС=0.9.
Так как критерием хорошей согласованности является отношение по величине составляющее менее 10%, то можно сделать вывод, что матрица является согласованной.
4.2.6 Анализ результатов оценки альтернатив
По полученным значениям векторов локальных приоритетов можно сделать выводы о важности альтернатив для каждого из критериев.
Критерий «Быстродействие».
а) альтернатива А (0.5775);
б) альтернатива Б (0.2722);
в) альтернатива В (0.0953);
г) альтернатива Г (0.055).
Альтернатива А имеет значительное преимущество в данном критерии над остальными альтернативами.
Критерий «Сложность реализации программы».
а) альтернатива Г (0.5555);
б) альтернатива В (0.2934);
в) альтернатива Б (0.1045);
г) альтернатива А (0.0466).
Очевидно, что Альтернатива Г имеет значительное преимущество по данному критерию над остальными альтернативами.
Критерий «Длина операционной части МК».
а) альтернатива Б (0.5811);
б) альтернатива В (0.2549);
в) альтернатива Г (0.1631);
г) альтернатива А (0.0482).
Альтернатива Б имеет значительное преимущество в данном критерии над остальными альтернативами.
Критерий «Объем занимаемой памяти».
а) альтернатива Б (0.5017);
б) альтернатива В (0.287);
в) альтернатива Г (0.1631);
г) альтернатива А (0.0482).
Альтернатива Б имеет значительное преимущество в данном критерии над остальными альтернативами.
Критерий «Сложность реализации ФСМО ».
а) альтернатива А (0.646);
б) альтернатива В (0.0002);
в) альтернатива Г (0.2429);
г) альтернатива Б (0.1109).
Альтернатива А имеет преимущество в данном критерии над остальными альтернативами.
Из полученных данных можно сделать вывод, что наибольшее предпочтение в выборе критерия «Длина операционной части МК» следует отдать альтернативе Б, а при выборе критериев «Сложность реализации ФСМО» и «Быстродействие» - альтернативе А.
4.3 Синтез глобальных приоритетов
Рассчитаем глобальные приоритеты для каждой альтернативы. Для удобства сведем вектор локальных приоритетов матрицы парных сравнений второго уровня в вектор X (таблица 4.9), а вектора локальных приоритетов матриц парных сравнений третьего уровня в матрицу Z, показанную в таблице 4.10.
Таблица 4.9 - Вектор локальных приоритетов второго уровня.
|
X |
1 |
2 |
3 |
4 |
5 |
|
|
0.5404 |
0.323 |
0.0579 |
0.0353 |
0.0434 |
Таблица 4.10 - Матрица локальных приоритетов третьего уровня.
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
A |
0.5775 |
0.0466 |
0.05 |
0.0482 |
0.646 |
|
|
Б |
0.2722 |
0.1045 |
0.5811 |
0.5017 |
0.0002 |
|
|
В |
0.0953 |
0.2934 |
0.2549 |
0.287 |
0.2429 |
|
|
Г |
0.055 |
0.5555 |
0.114 |
0.1631 |
0.1109 |
Функция полезности k-й альтернативы имеет вид
, (4.10)
где k - индекс альтернативы, xi - элемент вектора локальных приоритетов второго уровня, zik - элемент матрицы локальных приоритетов третьего уровня.
Проверим нормализацию полученных значений:
При заданной точности вычисление вектора глобальных приоритетов произведено без погрешности.
Проверим согласованность иерархии.
Для этого необходимо вычислить индекс согласованности, определяемый как сумма произведений индексов согласованностей критериев на их приоритеты, по следующей формуле
, (4.11)
Далее необходимо вычислить отношение согласованности для заданного числа элементов по формуле
, (4.12)
Для матрицы размерностью 5x5 СС=1.12.
Количественные оценки вкладов матриц (критериев) парных сравнений 3-го уровня во всю иерархию:
4.4 Количественные оценки вкладов критериев в конечный результат
Определим количественные оценки вкладов критериев в конечный результат.
Альтернатива А:
Рассмотрим вклад каждого из критериев подробнее и сделаем выводы.
Критерий «Быстродействие» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации программы» внес следующий вклад в процентном отношении:
Критерий «Длина операционной части МК» внес следующий вклад в процентном отношении:
Критерий «Объем занимаемой памяти» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации ФСМО » внес следующий вклад в процентном отношении:
Исходя из этих данных, можно сделать вывод, что критерий «Быстродействие» внес наибольший вклад в конечный результат данной альтернативы по причине того, что имел наивысший приоритет. Остальные критерии не оказали сильного влияния на результат.
Альтернатива Б:
Критерий «Быстродействие» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации программы» внес следующий вклад в процентном отношении:
Критерий «Длина операционной части МК» внес следующий вклад в процентном отношении:
Критерий «Объем занимаемой памяти» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации ФСМО » внес следующий вклад в процентном отношении:
Исходя из этих данных, можно сделать вывод, что критерий «Быстродействие» внес наибольший вклад в конечный результат данной альтернативы по причине того, что имел наивысший приоритет. Остальные критерии не оказали сильного влияния на результат.
Альтернатива В:
Рассмотрим вклад каждого из критериев подробнее и сделаем выводы.
Критерий «Быстродействие» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации программы» внес следующий вклад в процентном отношении:
Критерий «Длина операционной части МК» внес следующий вклад в процентном отношении:
Критерий «Объем занимаемой памяти» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации ФСМО » внес следующий вклад в процентном отношении:
Исходя из этих данных, можно сделать вывод, что критерий «Сложность реализации программы» внес наибольший вклад в конечный результат данной альтернативы по причине того, что имел наивысший приоритет. Остальные критерии не оказали сильного влияния на результат.
Альтернатива Г:
Рассмотрим вклад каждого из критериев подробнее и сделаем выводы.
Критерий «Быстродействие» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации программы» внес следующий вклад в процентном отношении:
Критерий «Длина операционной части МК» внес следующий вклад в процентном отношении:
Критерий «Объем занимаемой памяти» внес следующий вклад в процентном отношении:
Критерий «Сложность реализации ФСМО » внес следующий вклад в процентном отношении:
Исходя из этих данных, можно сделать вывод, что критерий «Сложность реализации программы» внес наибольший вклад в конечный результат данной альтернативы по причине того, что имел наивысший приоритет. Остальные критерии не оказали сильного влияния на результат. Наибольшее предпочтение в выборе критерия «Длина операционной части МК» следует отдать альтернативе Б, а при выборе критериев «Сложность реализации ФСМО» и «Быстродействие» - альтернативе А.
5. КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ПРОЕКТА
Под объектом проектирования необходимо рассматривать программно вычислительный комплекс для разработки и исследования форматов микрокоманд для различных способов микропрограммирования.
Рисунок 5.1 - Концептуальная модель проекта
На данной диаграмме можно выделить следующие элементы, выступавшие в роли объектов:
- пользователь с атрибутом набор команд, операции - ввести набор команд, изменить набор команд;
- кодирование набора микрокоманд, атрибут - способ кодирования, операция - провести кодирование;
- анализ результатов кодирования с атрибутами: время реализации, сложность кодирования, ширина форматов микрокоманды, операция - сравнение данных для различных способов кодирования;
- ведение статистики, атрибут - сложность кодирования, ширина форматов микрокоманд, операция - получить статистические данные;
- сообщение об ошибке с атрибутом тип ошибки, операции - определить ошибку;
- программа с атрибутом интерфейс.
6. ОПИСАНИЕ ПРОГРАММЫ
Разработанный программно-вычислительный комплекс ориентирован на разработку эффективных форматов микрокоманд для различных способов микропрограммирования.
6.1 Общие сведения
Разработка комплекса велась на языке C# (C Sharp). Файл программы называется Kodirovochki.exe.
Программная часть комплекса должна соответствовать следующим требованиям:
- наличие операционной системы не младше Windows XP;
- наличие установленной программы Microsoft Office Excel;
- наличие установленной библиотеки .NET Framework 4.0;
- 100 МБ свободной памяти на жестком диске компьютера для размещения требуемых файлов проекта и небольшого пространства подкачки для оперативной памяти.
6.2 Структура программно-вычислительного комплекса
В проектируемой системе существуют следующие классы:
- класс Form1;
- класс Graf;
- класс Program;
- класс PermutationsWithRepetition;
- класс Statistic.
Рассмотрим подробней каждый из классов.
6.2.1 Класс Form1
Данный класс предназначен для объединения всех подклассов в единую программную систему, а также формирование дружественного пользователю интерфейса. Его функциями являются:
- формирование интерфейса для ввода входных данных (кнопка Открыть Файл - метод button1_Click( ) ). Результатом работы является вывод на экран исходных данных;
- выбор метода и инициирования кодирования, а так же вывод данных (кнопка Горизонтальное - метод button2_Click( ), кнопка Вертикальное - метод button3_Click( ), кнопка Горизонтально-Вертикальное - метод button4_Click( ), кнопка Вертикально-Горизонтальное - метод button5_Click( ), кнопка Графики - метод button6_Click( ) ). Результатом работы является вывод на экран таблиц кодирования микрокоманд, булевых функций для ФСМО, а так же вывод оптимизированных булевых функций для ФСМО.
6.2.2 Класс Graf
Основное назначение класса - поиск максимальных подграфов в неориентированном графе методом ветвей и границ. Класс содержит следующие методы:
- List<List<int>> FindAllCliques( int[,] gmatrix ) - метод, предназначенный для поиска подграфов. На вход подается граф связности, представленный двумерным массивом, на выходе формируется список списков, содержащий номера вершин, составляющих максимальные подграфы;
- SubtractSet(List<int> set, int vert) - метод, предназначенный для вычитания очередной вершины из множества кандидатов на расширение подграфа;
- SubtractSet(List<int> set1, List<int> set2) - метод, в котором реализовано вычитание одного множества из другого;
- List<int> G(int vert) - метод, определяющий список вершин, не смежных с указанной в параметре.
Класс содержит поле public static int[,] gmatrix, содержащее в себе текущий обрабатываемый граф.
6.2.3 Класс Program
Класс предназначен непосредственно для кодирования набора микрокоманд одним из четырех способов микропрограммирования - горизонтальным, вертикальным, горизонтально-вертикальным или вертикально-горизонтальным. Содержит следующие поля:
- public static List<List<string>> MasMK - двумерный динамический массив, предназначенный для хранения исходной микропрограммы;
- public static List<List<string>> MasMO - двумерный динамический массив, предназначенный для хранения информации о том, в каких микрокомандах встречается каждая микрооперация;
- public static List<int> listOfMicOp - список номеров микрооперций, встречающихся в микрпрограмме;
- public static int dlinKod - поле типа int, которое хранит длину формата команды при любом виде кодирования;
- public static bool errorMOcopy - булевый флаг, свидетельствующий о наличии ошибки «В микрокоманде встречаются одинаковые микрооперации», изначально имеет значение false.
Методы, реализованные в классе Program:
- static void Main() - главный метод, который запускает программу;
- public static string ReadFile(String path) - считывание файла с исходным списком микроопераций;
- public static int FindNumberOfOperation() - создание массива, хранящего список всех микроопераций;
- private static bool NotDuplicate(string p) - проверка исходных данных на корректность, а именно поиск повторяющихся микрокоманд в микрооперации;
- public static int[,] gorizont() - кодирование микроопераций горизонтальным способом;
- private static bool FindOperation(string p, int stroka) - поиск микрооперации заданного номера в микрокоманде;
- internal static int[,] vertikal() - кодирование набора микрокоманд горизонтальным способом;
- private static int StrokaMaxRank(int[,] arr) - поиск максимального ранга строки в массиве с учетом уже выбранных строк;
- private static int StrokaMaxRankFromKod(int[,] arr) - ищет строку с максимальным рангом в сгенерированном массиве кодов с учетом уже выбранных строк, используется для генерации кодов вертикального кодирования;
- internal static string[] getBoolForGorizont() - выдает список булевых функций для горизонтального кодирования;
- internal static string[] getBoolForVertical() - выдает список булевых функций для вертикального кодирования;
- private static void getTableMicroOperation(int[,] verKod) - поиск иформации о том, в какой микрокоманде хранится заданная микрооперация;
- internal static string[] optimisationBoolForVert() - выдает список оптимизированных булевых функций для вертикального кодирования;
- private static void conglutination(int num) - поглощение строк ядерной строкой при минимизации таблицы покрытий;
- private static bool skleivanie(int i, int g, int num) - проверка на склеиваемость списка булевых функций;
- internal static int[] FindMinCover(int[,] workArray) - поиск минимального покрытия графа;
- internal static string gorVertKod() - кодирование горизонтально-вертикальным способом;
- private static int YestStroka(List<string> list,List<int> list_2) - поиск пустых строк в исходном файле;
- private static List<List<int>> CheckForOverlay(int[,] subArray, int[] minCover, List<List<int>> subGrafs) - формирование универсальной группы микроопераций;
- internal static string vertGorKod() - кодирование вертикально-горизонтальным способом;
- private static int[,] FindSovmestOper() - поиск совместимых микроопераций в группе.
6.2.4 Класс PermutationsWithRepetition
Класс предназначен для генерации всех возможных комбинаций заданной длины для заданного множества элементов. Эти комбинации далее используются для формирования кодов. Содержит поля:
- private int variationLength - поле типа int, которое определяет длину комбинаций;
- private int[] source - массив исходных элементов, в котором производятся перестановки.
Класс содержит единственный метод int[,] getVariations( ), который возвращает двумерный числовой массив, содержащий коды заданной длины.
6.2.5 Класс Statistic
Класс предназначен для сбора статистических данных в таблицу, оценку сложности, а так же последующий вывод их на экран в виде графиков.
Методы, реализованные в классе:
public static int [, ]getStatistData() - создание массива, хранящего статистич данные (длина кода, сложность ФСМО).Данные считываются из файла Exel, лежащего в директории проекта;
public static writeStatistData(int [, ]) - запись статистических данных в двумерный массив;
public static grafiki(int[,]) - отображение данных в виде графиков.
6.3 Описание основных алгоритмов
В разработанном программно-вычислительном комплексе использованы следующие алгоритмы: четыре алгоритма микропрограммирования (описанные в пункте 2.3), алгоритм Брона - Кербоша для поиска максимальных подграфов, алгоритм поиска минимального покрытия, алгоритм минимизации логических функций методом Квайна.
6.3.1 Алгоритм Брона - Кербоша
Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа [16].
Алгоритм оперирует тремя множествами вершин графа:
- множество compsub -- множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. Строится рекурсивно;
- множество candidates -- множество вершин, которые могут увеличить compsub;
- множество not -- множество вершин, которые уже использовались для расширения compsub на предыдущих шагах алгоритма.
Алгоритм является рекурсивной процедурой, применяемой к этим трем множествам.
ПРОЦЕДУРА extend (candidates, not):
ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates,
ВЫПОЛНЯТЬ:
1. Выбираем вершину v из candidates и добавляем ее в compsub;
2. Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v;
3. ЕСЛИ new_candidates и new_not пусты;
4. ТО compsub - клика;
5. ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not);
6. Удаляем v из compsub и candidates и помещаем в not [16].
6.3.2 Алгоритм поиска минимального покрытия
Для нахождения минимального покрытия используются такие алгоритмы:
- алгоритм полного перебора. Основан на методе упорядочения перебора подмножеств множества А;
- алгоритм граничного перебора по вогнутому множеству. Основан на одноименном методе сокращения перебора;
- алгоритм разложения по столбцу таблицы покрытия. Основан на методе сокращения перебора, который состоит в рассмотрении только тех строк таблицы покрытия, в которых имеется «1» в выбранном для разложения столбце;
- алгоритм сокращения таблицы покрытия. Основан на методе построения циклического остатка таблицы покрытия, для которого далее покрытие строится методами граничного перебора либо разложения по столбцу [17].
1. Считаем исходную таблицу покрытий текущей, а множество ядерных строк - пустым.
2. Находим ядерные строки, запоминаем множество ядерных строк. Текущую таблицу покрытий сокращаем, вычеркивая ядерные строки и все столбцы, покрытые ими.
3. Вычеркиваем антиядерные строки.
4. Вычеркиваем поглощающие столбцы.
5. Вычеркиваем поглощаемые строки.
6. Если в результате выполнения пунктов с 1 по 4 текущая таблица покрытий изменилась, снова выполняем пункт 1, иначе преобразование заканчиваем.
6.3.3 Алгоритм минимизации логических функций методом Квайна
Метод Квайна -- способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:
а) на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
б) на втором этапе -- переход от сокращённой формы к минимальной форме.
Подобные документы
Общие сведения об управляющих автоматах, построенных на основе принципа программируемой логики. Горизонтально-вертикальное кодирование. Алгоритмы кодирования операционной части. Анализ результатов оценки критериев. Алгоритм поиска минимального покрытия.
дипломная работа [1,8 M], добавлен 07.08.2012Методы арифметического кодирования. Основные функции программ, реализующие алгоритмы кодирования по методам Хаффмана, Голомба, Фибоначчи и Элиаса. Разработка программно-аппаратных средств оптимального арифметического кодирования и их экономический расчет.
дипломная работа [1,1 M], добавлен 26.05.2012Рассмотрение различных дистрибутивов операционной системы. Изучение протоколов обмена данными и форматов физического хранения данных. Разработка дистрибутива на основе операционной системы Linux для функционирования в составе сетевого хранилища StarNAS.
курсовая работа [1,6 M], добавлен 05.11.2015Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования.
контрольная работа [491,4 K], добавлен 15.10.2013Анализ способов кодирования информации. Разработка устройства кодирования (кодера) информации методом Хемминга. Реализация кодера–декодера на базе ИМС К555ВЖ1. Разработка стенда контроля передаваемой информации, принципиальная схема устройства.
дипломная работа [602,9 K], добавлен 30.08.2010Обзор различных методик и программ кодировки информации. Восстановление поврежденных файлов. Конфиденциальность и контроль за личными сведениями. Преобразование форматов файлов и способов кодировки. Утилиты - конвертеры и перекодировщики. Windows Vista.
курсовая работа [283,4 K], добавлен 14.11.2008Обработка изображений на современных вычислительных устройствах. Устройство и представление различных форматов изображений. Исследование алгоритмов обработки изображений на базе различных архитектур. Сжатие изображений на основе сверточных нейросетей.
дипломная работа [6,1 M], добавлен 03.06.2022Структура внешнего интерфейса. Алгоритмы функционирования микроЭВМ, его структурная и функциональная схемы. Формат микрокоманд и разработка микропрограммы. Диаграмма синхроимпульсов при использовании микропроцессора. Временная диаграмма работы микроЭВМ.
курсовая работа [2,6 M], добавлен 18.06.2012Сущность линейного и двухмерного кодирования. Схема проверки подлинности штрих-кода. Анализ способов кодирования информации. Расчет контрольной цифры. Штриховое кодирование как эффективное направление автоматизации процесса ввода и обработки информации.
презентация [1,1 M], добавлен 05.10.2014Общая характеристика растровых и векторных графических форматов: поддержка графическими редакторами, применение и отличия друг от друга. Специфика алгоритмов кодирования данных в исследуемых форматах, их совместимость с программным обеспечением.
презентация [25,2 K], добавлен 06.01.2014
