Логические системы в различных функциональных наборах и их реализация

Государственный комитет по образованию Российской Федерации
Московский институт радиотехники, электроники и автоматики
факультет кибернетики
кафедра интеллектуальных технологий и систем
группа ИР-1-95
Тема:
«Логические системы в различных функциональных наборах и их реализация»
Курс:
«Теоретические основы информатики»
Задание № 29.419, 7.942, 26.345
Студент: Лепихов И.М.
Руководитель: Семёнов А.И.
@? ?ЛИМ?
@? Иван Лепихов
Москва 1997
Задание на курсовое проектирование по курсу:
«Теоретические основы информатики»
Студента: Лепихова И.М. гр. ИР-1-95.
Тема: «Логические схемы в различных функциональных наборах и их реа-
лизация»
1.
Исходные данные
1.1.
Строка из шестнадцати символов А = { a0,a1, ..., a15 }
1.2.
Матричный индикатор 5 ? 7 = 35 ячеек.
Множество признаков H = { h0,h1, ..., h35 }
1.3.
Условие формирования строки символов и отображения T:H ? A
? F.
1.4.
Правило выделения ФАЛ из данных пункта 1.3.
1.5.
Интегральный набор К155 (по справочнику)
1.6.
Условие формирования подпространства Ф <= T.
2.
Перечень подлежащих разработке вопросов.
2.1.
а) отображение Т.
б) ФАЛ F1, F2, F3.
в) подмножество Ф <= T.
2.2.
Комбинационная схема совместной реализации ФАЛ F1, F2, F3.
2.3.
Анализ подмножества Ф <= T на толерантность и эквивалентность.
2.4.
Схема автомата, отвечающая состояниям пункта 2.3.
2.5.
Выводы и заключения.
3.
Тема исследования.
3.1.
Структура формальной системы отношения по дополнительно заданной
предметной области знаний.
4.
Перечень графических материалов.
4.1.
Отображение T: H ? A ? F.
4.2.
Комплекс моделей, методов и средств минимизации ФАЛ F1 и F2.
4.3.
Комбинационная схема совместной реализации.
4.4.
Матрица толерантности, карта толерантности для подмножества Ф<=T
4.5.
Схема автомата А.
СОДЕРЖАНИЕ
Введение. 4
1. Исходные данные. 5
1.1. Строка из шестнадцати символов. 5
1.2. Матричный индикатор. 5
1.3. Формирование отображения строки символов. 5
2. Промежуточное исследование исходных данных. 6
2.1. Отображение символов строки А на индикаторе. 6
2.2. Получение ФАЛ 7
2.3. Нахождение номеров ФАЛ по карте Карно 9
2.4. Таблица истинности. 9
2.5. Представление ФАЛ в совершенной нормальной форме. 10
2.6. Минимизация ФАЛ 11
2.7. Представление ФАЛ в виде куба 12
3. Исследование ФАЛ. 13
3.1. Матрица отношений. 13
3.2. Исследование ФАЛ на толерантность. 13
3.3. Исследование ФАЛ на эквивалентность. 14
3.4. Матрица эквивалентности и толерантности. 14
3.5. Диаграмма Эйлера. 15
3.6. Построение комбинационной схемы. 16
Список использованной литературы 17
Заключение 17
Введение.
С развитием электроники приобретают огромное значение электронные ви-
зуальные средства отображения информации.
Эти средства представляют собой разнообразной величины экраны,
оформленные различными способами (циферблаты часов, табло на стадионах и
т.д.) У всех этих средств общая деталь - элемент, отображающий только один
символ.
Эти элементы представляют собой матрицу, в клетках которой смонтированы
светящиеся элементы (лампочки и т.п.) При подаче на них напряжения,
отображается тот или иной символ визуальной информации.
Темой данного курсового проекта является разработка автомата, управ-
ляющего светящимися элементами, для отображения необходимого сообщения
на табло.
Каждый символ сообщения отображается на отдельной матрице (матричном
индикаторе) 5 ? 7 светящихся элементов, то есть каждому символу
соответствует определенная комбинация светящихся элементов матрицы.
В данном курсовом проекте нужно выбрать три признака (светящегося
элемента) и построить автомат, управляющий этими признаками при подаче на
вход четырехразрядного управляющего кода.
Для разработки автомата необходимо произвести анализ на толерантность и
эквивалентность. В заключение необходимо сделать вывод.
1. Исходные данные.
Исходными данными является строка из шестнадцати символов, а так же
матричный индикатор, назначение которого будет подробнее рассмотрено в
пункте 1.2.
1.1. Строка из шестнадцати символов.
Строка из шестнадцати символов выбирается произвольно. Она является
объектом исследования. В данном курсовом проекте используется строка,
приведенная на рисунке 1.1.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
И
В
А
Н
М
И
Х
А
Й
Л
О
В
И
Ч
.
Рис. 1.1. Строка из шестнадцати символов
1.2. Матричный индикатор.
Матричный индикатор - матрица размерностью 5 ? 7 = 35 ячеек. С помощью
матричного индикатора можно любому символу (букве, знаку препинания,
цифре и т.д.) поставить в соответствие набор признаков H = { h1, h2, ..., h35 }.
Внешний вид матричного индикатора представлен на рисунке 1.2.
Рис. 1.2.
1.3. Формирование отображения строки символов.
С помощью матричного индикатора устанавливается соответствие каждому
символу ai из исходной строки символов А (см. п. 1.1) определенный набор
признаков На < H. Например, первому символу «И» можно поставить в
соответствие следующий набор признаков из числа заштрихованных ячеек
индикатора (см. рис. 1.3а) : (1,5,6,10,11,14,15,16,18,20,21,22, 25,26,30,31,35). Это
соответствует отображению на индикаторе, представленному на (рис 1.3б), где
«1» на рисунке означает наличие признака в соответствующей ячейке, а «0» - его
отсутствие. В общем случае при появлении на логическом устройстве
управления матричным индикатором набора
(10001100011001110101110011000110001)
устройство должно выдавать сигнал на соответствующем выходе подтвер-
ждающей, что индикатор распознал символ «И». Аналогично должны рас-
познаваться другие символы строки А, что соответствует отображению T:H ? A,
которое представлено в таблице 1. По горизонтали таблицы расположена строка
А символов, по вертикали 35 признаков Н. Если признак соответствует данной
букве, то на пересечении строки-признака и столбца-буквы ставится «1» и т.д.
до заполнения всей таблицы. Затем производится подсчет единиц в строке.
Для упрощения задачи из всего множества признаков выделяется три
признака из 35-ти, для которых строится таблица истинности, причем число
единиц для каждого признака подбирается равным 7,8 и 9. Таким образом,
устройство классифицирует символы по двум классам объектов: по наличию
или отсутствию трех признаков.
Рис. 1.3а, отображение символа «И» на
индикаторе
Рис. 1.3б, вид матричного индикатора
при изображении символа «И»
2. Промежуточное исследование исходных данных.
В промежуточном исследовании мы поставим в соответствие буквам строки
из 16-ти символов наборы признаков, сформулируем отображение T:H ? A ?
F и выделим 3 ФАЛ. Построим для них таблицу истинности и по картам Карно
найдем их номера.
2.1. Отображение символов строки А на индикаторе.
С помощью матричного индикатора (см. п.1.2) поставим в соответствие бу-
квам строки из пункта 1.1 наборы признаков (см. рис. 2.1).
Рис. 2.1, отображение символов строки А на индикаторе.
Выпишем отдельно буквы и соответствующие им признаки
И 1,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
В 1,2,3,4,6,10,11,15,16,17,18,19,21,25,26,30,31,32,33,34
A 2,3,4,6,10,11,15,16,17,18,19,20,21,25,26,30,31,35
H 1,5,6,10,11,15,16,17,18,19,20,21,25,26,30,31,35
пробел
М 1,5,6,7,9,10,11,13,15,16,20,21,25,26,30,31,35
И 1,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
Х 1,5,7,9,12,14,18,22,24,27,29,31,35
A 2,3,4,6,10,11,15,16,17,18,19,20,21,25,26,30,31,35
Й 1,3,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
Л 3,4,5,7,10,11,15,16,20,21,25,26,30,31,35
O 2,3,4,6,10,11,15,16,20,21,25,26,30,32,33,34
В 1,2,3,4,6,10,11,15,16,17,18,19,21,25,26,30,31,32,33,34
И 1,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
Ч 1,5,6,10,11,15,16,17,18,19,20,25,30,35
. 35
2.2. Получение ФАЛ
В данном курсовом проекте из множества признаков выделено 3 (см. табл.1).
С номерами 1,3,5 для которых и будет построена логическая схема устройства,
диагностирующего их наличие или отсутствие.
Для решения задачи в двухзначной логике необходимо перейти к двоичному
коду, закодировав им каждый из 16-ти символов строки А.
При этом достаточно четырехразрядного двоичного числа, определяющего
значение XYZP, которым в дальнейшем будет кодироваться номер каждого
символа. Например, второй символ «В» должен иметь код 0001, первый «И» -
0000 и т.д.
Таблица истинности для выбранных признаков представлена в таблице 2, где
ФАЛ - функция алгебры логики, в которых значение 1 принимается для кодов,
имеющих значение признака h, равного 1. В общем случае h ? {0,1}. Следует
учесть, что h1?F1, h3?F3, h5?F5.
Отображение T:H ? A ? F
Табл. 1
2.3. Нахождение номеров ФАЛ по карте Карно
Следующим этапом является нахождение 10-значных номеров ФАЛ по карте
Карно, общий вид которой для 4-ех переменных представлен на рисунке 2.2.
Цифры в квадратах являются степенью числа 2 при определении номера ФАЛ,
выбранных в данной работе на рисунке 2.2а,б,в
Рис. 2.2 Карта Карно со степенями двойки
2.4. Таблица истинности.
Табл. истинности для ФАЛ. Табл. 2
Нахождение номера ФАЛ: F1
N(F1) = 20 + 21 + 23 + 25+ 27 + 26 + 29 + 212 + + 213 + 214
= 29419
Нахождение номера ФАЛ: F3
N(F3) = 21 + 22 + 212 + 28+ 29 + 210 + 211 = 7942
Нахождение номера ФАЛ: F5
N(F5) = 20 + 23 + 25 + 26 + 27 + 29+ 210 + 213 + + 214 =
26345
2.5. Представление ФАЛ в совершенной нормальной фор-
ме.
Представим выбранные признаки в совершенной дизъюнктивной нор-
мальной форме (СДНФ) и совершенной конъюнктивной нормальной форме
(СКНФ). Для этого из таблицы истинности ФАЛ (см. табл. 2) выпишем
конституэнты 0 и 1.
ФАЛ в СДНФ примет вид:
F1(X,Y,Z,P) = (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ?
(X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P)
F3(X,Y,Z,P) = (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ?
(X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P)
F5(X,Y,Z,P) = (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ?
(X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P) ? (X,Y,Z,P)
ФАЛ в СКНФ примет вид:
F1(X,Y,Z,P) = (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z
? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P)
F3(X,Y,Z,P) = (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z
? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P) &
(X ? Y ? Z ? P)
F5(X,Y,Z,P) = (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z
? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P) & (X ? Y ? Z ? P)
2.6. Минимизация ФАЛ
Проведем минимизацию полученных ФАЛ при помощи карты Карно и
представим их в ДНФ. Для этого попытаемся оптимальным образом объединить
0-кубы в кубы большей размерности. Клетки, образующие k-куб, дают
минитерм n-k ранга, где n - число переменных, которые сохраняют одинаковое
значение на этом k-кубе. Таким образом, получим ДНФ выбранных ФАЛ.
Рис 2.2а Рис 2.2б Рис 2.2в
Проведем минимизацию алгебраическим путем, воспользовавшись тож-
деством а ? а = а.
1. XYZP ? XYZP ? XYZP ? XYZP ? XYZP ? XYZP ? XYZP ? XYZP ? XYZP ?
XYZP ? XYZP ? XYZP = XYZ ? XZP ? XZP ? YZP ? XYZ ? XZP = ZP ?
XYZ ? XZP ? YZP ? XYZ
2. XYZP ? XYZP ? XYZP ? XYZP ? XYZP ? XYZP? XYZP ? XYZP ? XYZP ?
XYZP = YZP ? YZP ? XZP ? XYZ ? XYZ = XY ? YZP ? YZP ? XZP
3. ? XYZP ? XYZP ? XYZP ? XYZP ? XYZP ? XYZP? XYZP ? XYZP ? XYZP
? XYZP ? XYZP = XZP ? XYP ? XYZ ? XZP ? XZP ? XYZP
2.7. Представление ФАЛ в виде куба
3. Исследование ФАЛ.
3.1. Матрица отношений.
Построить матрицу отношений T:H ? A. Матрица отношений представляет
собой таблицу, строками которой являются записи (кортежи признаков), а
строками отношения, которые имеют все уникальные имена. Матрица от-
ношения представлена в таблице 3.
Матрица отношений. Табл. 3
3.2. Исследование ФАЛ на толерантность.
Определим классы толерантности. Рассмотрим классы толерантности k1, k2,
k3, имеющие общие элементы, следовательно, являющиеся пересекающимися
множествами.
h1 = h(?1) = h(A) = { X0, X1, X3, X5, X6, X7, X9, X12, X13, X14 }
h2 = h(?2) = h(B) = { X1, X2, X8, X9, X10, X11, X12 }
h3 = h(?3) = h(C) = { X0, X3, X5, X6, X7, X9, X10, X13, X14 }
Проанализировав классы h1, h2, h3, можно получить: k1 ? k2 = 0;
k1 ? k3 = 0; k2 ? k3 = 0, т.е. {k1, k2, k3 } - образуют класс толерантности
Результаты исследования занесем в таблицу 3.
3.3. Исследование ФАЛ на эквивалентность.
Определим классы эквивалентности для этого множества А = {Х0, Х1, ...., Х15
} разобьем на классы эквивалентности, получим 6 классов
М1 = {AC} = {X0,X3,X5,X6 X7,X13,X14}
М2 = {AB} = {X1,X12}
М3 = {B} = {X2,X8,X11}
М4 = { } = {X4,X15}
М5 = {ABC} = {X9}
М6 = {BC} = {X10}
При этом каждый класс полностью определяется любым его представителем.
Сопоставив результаты исследования с результатами пункта 3.2 получим
следующие зависимости
М1 ? K1
М2 ? K1
М3 ? K2
М5 ? K1
М6 ? K2
М1 ? K3
М2 ? K2
М5 ? K2
М6 ? K3
М5 ? K3
или
K1 = M1 ? M2 ? M5
K2 = M2 ? M3 ? M5 ? M6
K3 = M1 ? M5 ? M6
Результаты исследования занесены в таблицу 3. Результаты исследования на
эквивалентность и толерантность необходимы для оптимизации построения
логической схемы.
3.4. Матрица эквивалентности и толерантности.
Матрицу эквивалентности и толерантности можно представить в виде
квадрата, по диагонали которого строятся классы эквивалентности, а затем
устраиваются отношения толерантности. Матрица эквивалентности и толе-
рантности представлена в таблице 4.
Матрица эквивалентности и толерантности. Таблица 4.
3.5. Диаграмма Эйлера.
Диаграмма Эйлера дает наглядное представление о том, как распределяются
признаки по классам толерантности и эквивалентности. Диаграмма Эйлера для
выбранных ФАЛ представлена на рисунке 3.5.
Диаграмма Эйлера. Рис. 3.5
3.6. Построение комбинационной схемы.
Комбинационная схема автомата распознавания набора признаков H = {h1, h3,
h5 } построена на основе результатов исследований в пункте 3.1 и пункте 3.4.
Таблица 5
Используя таблицу 5, можно записать следующие отношения:
G1 = (XYZP) ? (XYZP) ? (XYZP) ? (XYZP) ? (XYZP) ? (XYZP) ? (XYZP) =
(XYZP) ? (XYZP) ? (XYZP) ? (XYZ) ? (YZP)
G2 = (XYZP) ? (XYZP)
G3 = (XYZP) ? (XYZP) ? (XYZP)
G4 = (XYZP) ? (XYZP)
G5 = (XYZP)
G6 = (XYZP)
Тогда ФАЛ можно представить в виде:
F1 = G1 ? G2 ? G5
F3 = G2 ? G3 ? G5 ? G6
F5 = G1 ? G5 ? G6
Эти отношения эквивалентны ФАЛ в СДНФ, полученным в пункте 2.5.
Комбинационная схема строилась в два этапа:
1 этап: - построение комбинационной схемы на элементах и, или,
(нестандартных).
2 этап: - замена нестандартных элементов на стандартные и-не
Окончательный вариант комбинационной схемы приведен в приложении 1.
Список использованной литературы
1. В.П. Сигорский. «Математический аппарат инженера» - издательство Киев:
Техника - 1975 г.
Заключение
Проведя анализ на толерантность и эквивалентность, мы построили автомат,
распознающий кортеж признаков H = {h1, h3, h5 }, который состоит из 16 - ти
логических элементов.
17
?ЛИМ?