Разработка эффективных форматов микрокоманд для различных способов микропрограммирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?роится рекурсивно;
-множество candidates - множество вершин, которые могут увеличить compsub;
-множество not - множество вершин, которые уже использовались для расширения compsub на предыдущих шагах алгоритма.
Алгоритм является рекурсивной процедурой, применяемой к этим трем множествам.
ПРОЦЕДУРА extend (candidates, not):
ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates,
ВЫПОЛНЯТЬ:
1.Выбираем вершину v из candidates и добавляем ее в compsub;
2.Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v;
.ЕСЛИ 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.Находим ядерные строки, запоминаем множество ядерных строк. Текущую таблицу покрытий сокращаем, вычеркивая ядерные строки и все столбцы, покрытые ими.
.Вычеркиваем антиядерные строки.
.Вычеркиваем поглощающие столбцы.
.Вычеркиваем поглощаемые строки.
.Если в результате выполнения пунктов с 1 по 4 текущая таблица покрытий изменилась, снова выполняем пункт 1, иначе преобразование заканчиваем.
6.3.3 Алгоритм минимизации логических функций методом Квайна
Метод Квайна - способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:
а)на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
б)на втором этапе - переход от сокращённой формы к минимальной форме.
1.Начало.
2.Ввести матрицу ДСНФ исходной функции.
.Проверить на склеиваемость i-ю (i=1,m-1: где m - количество строк в ДСНФ) и j-ую (j=i+1, m) строки. Если строки склеиваются, то перейти к пункту 6, в противном случае перейти к пункту 5.
.Формировать массив простых импликант, предварительно пометив символом * ту переменную, по которой данные строки склеиваются.
.Перейти к пункту 2.
.Строку, которая не склеилась ни с одной другой строкой записать в конечный массив.
.Перейти к пункту 2.
.Вывод полученной матрицы.
.Конец.
7. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ КОМПЛЕКСА
Разработанный программно-вычислительный комплекс в изначальном виде имеет следующий вид
Рисунок 7.1 - Изначальная форма программы
На форме расположены три поля - Исходный файл, Формат микрокоманд, Булевы функции для ФСМО. После открытия тестового файла происходит заполнение первого поля
Рисунок 7.2 - Форма после открытия тестового файла
После считывания данных становятся доступными четыре кнопки - Горизонтальное, Вертикальное, ГорВерт, ВертГор, каждая из которых определяет способ кодирования одним из способов - горизонтальным, вертикальным, горизонтально-вертикальным и вертикально-горизонтальным соответственно.
7.1 Горизонтальное кодирование
После нажатия на кнопку Горизонтальное, происходит кодирование соответствующим способом. Результат работы - заполнение поля Формат микрокоманды кодами и подсчет длины кода микрокоманды. Кроме того, становится доступной кнопка Булевы (Гор), после нажатия которой выдается список булевых функций для горизонтального кодирования.
Рисунок 7.3 - Результат работы после нажатия кнопки Горизонтальное
Рисунок 7.4 - Список булевых функций для горизонтального кодирования
7.2 Вертикальное кодирование
Выбираем вертикальное кодирование.
Рисунок 7.5 - Форма после нажатия кнопки Вертикальное
После кодирования становится доступна кнопка Булевы (Верт), которая выдает список булевых функций. После ее выбора становится доступной еще одна кнопка Оптимизация БФВК, которая позволяет провести оптимизацию полученных булевых функций.
Рисунок 7.6 - Список булевых функций для вертикального кодирования
Рисунок 7.7 - Результат оптимизации
7.3 Горизонтально-вертикальное кодирование
Выбрана кнопка ГорВерт. Результат работы представлен на рисунке 7.8
Рисунок 7.8 - Горизонтально-вертикальное кодирование
Результатом работы является список закодированных микрокоманд и перечень групп (G1, G2, G3), содержащий список несовместимых микроопераций.
7.4 Вертикально-горизонтальное кодирование
Выбираем кнопку ВертГор для вертикально-горизонтального кодирования. Результат работы программы представлен на рисунке 7.9.