Схемы из функциональных элементов реферат

Обновлено: 07.07.2024

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

Рубрика	Коммуникации, связь, цифровые приборы и радиоэлектроника
Вид	курсовая работа
Язык	русский
Дата добавления	26.12.2012
Размер файла	859,7 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

1. Описание функциональной схемы

1.1 Описание элементов схемы

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

2.1 Выбор контроллера

2.2 Выбор элементов схемы

2.3 Описание принципиальной схемы

3. Разработка программы управления

3.1 Логика работы системы

3.2 Описание работы программы

3.3 Описания интерфейса программы с пользователем

Техническое задание

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

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

Для отображения информации используется LCD 16x2.

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

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

При возникновении опасности пожара система выполняет включение блока пожаротушения.

Введение

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

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

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

высокая степень миниатюризации,

работоспособность в жестких условиях эксплуатации;

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

1. Функциональная схема устройства

1.1 Описание элементов схемы

Данная система ориентирована на охрану дома и соответственно обеспечивает контроль типовых датчиков: датчик движения, датчик температуры и датчик дыма.

Так же предусмотрен стандартный шлейф из нормально замкнутых датчиков, размыкание которых обрабатывается микроконтроллером. Для индикации состояния используются LCD семисегментный индикатор. Для управления системой предусмотрены 16 клавиш, позволяющие задавать режимы устройства. Постановки на охрану или снятие с нее осуществляется подключением соответствующих электронных ключей. Таким образом, исключается вероятность взлома. При возникновении нарушения срабатывает звуковая сигнализация, реализованная в виде типовой сирены. Вся информация о нарушениях и постановки/снятия с охраны передается на удаленный компьютер через последовательный интерфейс RS-485.

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

- специализированный жидкокристаллический дисплей LCD, необходимый для отображения параметров работы системы, введённых пользователем.

- клавиатура содержит 16 кнопок. Это позволяет упростить логику и обеспечивает большое удобство работы с системой. На ней расположены кнопки:

- 0-9 цифры для ввода кода.

- преобразователь электронного интерфейса RS485 + - 12 В, который создаёт требуемые +/ - 12 В засчёт встроенного внутреннего генератора и конденсаторов обвязки, подключённых к данному чипу.

- контакты на размыкание.

- микроконтроллерный датчик температуры DS1820.

- микроконтроллерный датчик движения.

- микроконтроллерный датчик дыма.

- блок звуковой индикации.

- постановки на охрану или снятие с нее осуществляется подключением электронного замка.

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

2.1 Выбор контроллера

В начале работы я проанализировал несколько различных серий контроллеров: AVR, PIC и МК-51. При этом я учитывал, что контроллер должен удовлетворять требованиям к разрабатываемому устройству по следующим параметрам:

· количество портов 15,

· желательно знакомая архитектура.

· Соотношение цены и качества.

Вначале рассмотрим серию AVR - ядро базируется на RISC архитектуре. Имеется регистровый файл быстрого доступа, который содержит 32 регистра общего назначения. Они непосредственно связанны с арифметико-логическим устройством (ALU), и мощной системой команд. При совершении одного тактового цикла из регистрового файла извлекаются два операнда. При этом выполняется команда, и результат записывается в регистр назначения. Производительность такой высокоэффективной архитектуры во много раз больше, чем стандартные CISC микроконтроллеры, например 51 серия.

AVR работают в широком диапазоне питающих напряжений от 2,7 В до 6,0 В. Ток потребления в активном режиме зависит от величины напряжения питания и частоты, на которой работает микроконтроллер, и составляет менее 1 мА для 500 кГц, 5 . 6 мА для 5 МГц и 8 . 9 мА для частоты 12 МГц. AVR также могут быть переведены программным путем в один из двух режимов пониженного энергопотребления.

Температурные диапазоны работы микроконтроллеров AVR - коммерческий (0 . 70 С) и индустриальный (-40 . +85 С).

Структурная схема микроконтроллера приведённая на рис. 2.1. содержит порты ввода/вывода и интерфейсные схемы.

Рис. 1 - Структурная схема AVR:

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

Такое построение обеспечивает существенное повышение производительности за счет:

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

б) расширения до 16 бит разрядной сетки шины данных памяти программ.

Следующим шагом на пути увеличения быстродействия AVR является использование технологии конвейеризации, у микроконтроллеров семейства MCS51 короткая команда выполняется за 12 тактов генератора (1 машинный цикл), в течение которого процессор последовательно считывает код операции и исполняет ее.

Каждый из 32-х регистров общего назначения длиной 1 байт непосредственно соединен с арифметико-логическим устройством (ALU) процессора. Это означает, что в AVR существует 32 регистра-аккумулятора (сравните с MCS51). Это позволяет в сочетании с конвейерной обработкой выполнять одну операцию в ALU за один машинный цикл.

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

2 Кбайт Flash- памяти с поддержкой внутрисистемного программирования SPI- последовательный интерфейс для загрузки программного кода Ресурс: 1000 циклов записи/ стирания.

128 байта EEPROM: Ресурс: 100 000 циклов запись/ стирание 15 программируемых линий I/O.

Питание VCC: от 2.7 В до 6.0 В.

Полностью статический режим работы:

От 0 до 10 МГц, при питании от 4.0 В до 6.0 В

От 0 до 4 МГц, при питании от 2.7 В до 6.0 В

Производительность, вплоть до 10 MIPS при 10 МГц

Один 16-ти разрядный таймер/ счетчик с отдельным предварительным делителем частоты с режимами сравнения и захвата.

Выбираемые 8, 9, или 10-ти разрядные режимы широтно- импульсной модуляции (ШИМ).

Внешние и внутренние источники прерывания.

Программируемый следящий таймер с встроенным тактовым генератором.

Встроенный аналоговый компаратор.

Экономичные режимы ожидания и пониженного энергопотребления.

Программируемая блокировка для безопасности программного обеспечения.

Рис.2 1 - Расположение выводов контролдлера:

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

Другой рассмотренный мной контроллер PIC16F626 наиболее распространенный и используемый контроллер серии PIC. Он обеспечивает необходимые параметры для реализации проекта по числу портов и внутренним ресурсам: таймеру памяти и частоте работы.

Рис. 2.2 - Расположение выводов PIC:

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

При создании микроконтроллеров семейства МК-51 используется гарвардская архитектура, при которой память программ (ПЗУ) и память данных (ОЗУ) имеют раздельное адресное пространство. При использовании такой архитектуры для обращения к ячейкам памяти разного типа используются разные типы команд.

Объём максимального размера адресного пространства для каждого типа памяти составляет 64 Кбайта. Но только 4 Кбайта ПЗУ и 128 байт ОЗУ располагаются непосредственно на кристалле МК 8051 АН. Существует возможность подключения внешней памяти МК семейства MCS-51 (т. е. архитектура является открытой).

Это позволяет подключить внешнее ПЗУ и достаточное количество портов (4Ч8). В моем случае выбранный контроллер обеспечивает избыточное количество портов 4х8 что упрощает схемотехническое проектирование.

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

Внимательно изучив свойства приведённых выше микроконтроллеров, а также сравнивая их с перечисленными требованиями (которые вытекают из совокупности необходимых параметров для разрабатываемого устройства), я сделала вывод, что наилучшим выбором будет использование МК-51, так как у него наиболее доступная цена, при этом достаточное количество портов, памяти и функций.

Также его архитектура знакома мне из курса лабораторных работ. Следовательно, с ней мне будет наиболее удобно выполнять курсовую работу. А также важно то, что у него имеются необходимые мне команды деления и умножения, которые в RISC архитектуре реализуются достаточно большими подпрограммами и тем самым требуется больше памяти для управляющей программы.

2.2 Выбор элементов схемы

Выбраны интеллектуальные цифровые датчики температуры, сейчас наиболее распространены 2 типа датчиков. Один с четырех проводным подключением по шине I2C, второй по шине 2-3-х проводной ware(3-х проводная шина когда дополнительно 3-я используется для питания датчика).

Аннотация: Логические схемы (схемы из функциональных элементов) и реализуемые ими функции. Задачи синтеза и анализа схем. Логические схемы и линейные программы. Примеры логических схем: сложение по модулю 2 и двоичный сумматор

В этой и следующей лекциях мы свяжем два основных предыдущих раздела нашего курса: булевы функции и графы. В курсе "Основы дискретной математики" мы рассматривали два основных представления булевых функций: табличное и с помощью формул общего вида или формул специального вида, в частности, дизъюнктивных или конъюнктивных нормальных форм и многочленов Жегалкина . К сожалению, эти способы не позволяют эффективно представлять функции от большого числа переменных: таблица для функции от n переменных всегда содержит 2 n строк, многочлен Жегалкина может включать до 2 n слагаемых (и для большинства функций по порядку столько и включает). Такие представления нельзя реализовать на практике уже для n порядка нескольких десятков. Могло показаться, что сокращенные ДНФ , которые мы научились эффективно строить с помощью метода Блейка , и минимальные ДНФ, которые можно получить, удаляя из сокращенных "лишние" конъюнкции (впрочем, хороший алгоритм для такого удаления неизвестен), дают существенно более экономные представления. булевых функций. Но в общем случае это не так. Для большинства булевых функций от n переменных минимальные ДНФ имеют экспоненциальный от n размер. В качестве примера конкретной простой функции с длинной ДНФ можно рассмотреть линейную функцию, определяющую нечетность суммы аргументов: odd(X₁,X₂. X_n)= X₁ +X₂ +. + X_n (см. задачу 3.1).

Те два представления булевых функций, которые мы рассматриваем в этом разделе: логические схемы ( схемы из функциональных элементов ) и упорядоченные бинарные диаграммы решений (УБДР), тоже для большинства функций имеют экспоненциальные размеры от числа переменных. Но во многих ситуациях они позволяют построить достаточно компактные представления естественно возникающих на практике булевых функций от сотен и даже тысяч агументов.

Логические схемы (схемы из функциональных элементов)

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

$B_<0> Чтобы не усложнять определение , зафиксируем конкретный базис =\< \wedge , \vee , \neg \>$
и определим схемы в этом базисе.

Определение 2.1. Логической схемой ( схемой из функциональных элементов ) в базисе B₀ называется размеченный ориентированный граф без циклов S=(V,E) , в котором

вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
в каждую из остальных вершин входит одно или два ребра; вершины, в которые входит одно ребро помечены функцией а вершины, в которые входят по два ребра, - одной из функций или Такие вершины называются функциональными элементами .

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

$v \in V$

Определение 2.2. Глубина вершины в схеме S=(V,E) - это максимальная длина пути из входов S в v .

Глубиной D(S) схемы S назовем максимальную из глубин ее вершин.

$v \in V$

Пусть входы схемы S помечены переменными x₁, . , x_n . С каждой вершиной схемы S свяжем булеву функцию f_v(x₁. , x_n) , реализуемую в этой вершине. Определим f_v индукцией по глубине v .

Определение 2.3.

Базис: v имеет глубину 0. Тогда это входная вершина , которая помечена некоторой переменной x_i . Положим f_v(x₁. , x_n) = x_i .

Шаг индукции. Пусть всем вершинам w глубины уже сопоставлены функции f_w и пусть v - произвольная вершина глубины k+1 . Тогда

$\neg$

если v помечена и в нее входит ребро (w,v) , то положим

$f_v(x_1,\ldots , x_n) = \neg f_w(x_1,\ldots , x_n) ;$

$\wedge$

если v помечена и в нее входят два ребра (w₁,v) и (w₂,v) , то положим

$f_v(x_1,\ldots , x_n) = f_<w_1> (x_1,\ldots , x_n) \wedge f_(x_1,\ldots , x_n);$

$\vee$

если v помечена и в нее входят два ребра (w₁,v) и (w₂,v) , то положим

$f_v(x_1,\ldots , x_n) = f_<w_1> (x_1,\ldots , x_n) \vee f_(x_1,\ldots , x_n).$

Нетрудно понять, что шаг индукции в этом определении корректен, так как, если в схеме S имеется ребро (w,v) и глубина вершины v равна k+1 , то глубина вершины w не превосходит k и для нее f_w уже определена по индукционному предположению.

Определение 2.4. Схема S реализует набор булевых функций g₁, g₂, . , g_m , если для каждого в схеме существует такая вершина v_i , что = g_i" />
.

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

Определение 2.5. Сложность L(S) схемы S - это число функциональных элементов в S . Сложность L(f) булевой функции f(x₁, . x_n) - это наименьшая из сложностей схем , реализующих эту функцию.

Отношения между булевыми функциями и схемами естественно приводят к двум следующим основным проблемам.

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

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

Пример 2.1. Рассмотрим схему S₁ с тремя входными переменными x, y и z , изображенную на рис. 2.1 и решим для нее проблему анализа.

В соответствии с данным выше определением вершины схемы S₁ реализуют следующие функции:

, (x,y,z) = \neg z" />
, (x,y,z) = \neg f_(x,y,z)=\neg ( x \wedge y)" />
, (x,y,z) = f_(x,y,z) \wedge z = \neg ( x \wedge y) \wedge z" />
, (x,y,z) =f_(x,y,z) \wedge f_(x,y,z)= x \wedge y \wedge \neg z" />
и, наконец, (x,y,z) =f_(x,y,z) \vee f_(x,y,z) = (\neg ( x \wedge y) \wedge z) \vee ((x \wedge y )\wedge \neg z)" />
.

$(x \wedge y)$

Глубина этой схемы D(S₁)= 4 , а ее сложность L(S₁)=6 . В то же время формула для результирующей функции f_f содержит 7 функциональных знаков. За счет чего достигнута экономия? За счет того, что функция в схеме S₁ вычисляется один раз в вершине a , а в формуле приходится вычислять ее дважды.

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

В настоящее время контактные схемы используются редко ввиду их невысокого быстродействия. Те же функции ù , Ù и Ú реализуются с помощью специальных элементов (полупроводниковых и др.), которые мы будем называть функциональными элементами.

Каждый Функциональный элемент имеет n упорядоченных входов и один выход. При каждом наборе сигналов на входах (1 – есть сигнал, 2 –нет) может возникнуть определенный сигнал (0 или 1) на выходе.

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

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

1. Некоторые входы одного элемента соединить с входами других элементов (см. рис), что отвечает композиции соответствующих функций;

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

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

Соединения следующего вида, когда выход данного функционального элемента соединяется со входом, называются Недопустимыми. Схемы с такими соединениями (cм. рисунки) не смогут функционировать, если соответствующие входы являются существенными.

Пример 1. Синтезировать логическую схему, реализующую булеву функцию

Минимизируя в классе ДНФ, получим представление . Следовательно, здесь переменные X2, X3 – фиктивные, от них значение функции не зависит. Соответствующая схема показана на рисунке

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

Тогда

Учитывая, что , полученную формулу можно упростить: Соответствующая схема изображена на рисунке.

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

Пример 2. Синтез N–разрядного сумматора.

Построим логическую схему, реализующую суммирование двух N–разрядных чисел, представляющих в двоичной системе исчисления. Пусть и -- два данных числа, где Xi и Yi – их цифры (0 или1). Пусть -- их сумма и -- число, цифры которого соответствуют переносам знаков в следующий разряд при обычном способе суммирования многозначных чисел.

Цифры Zi и переносы знака Pi, легко видеть, определяются следующими условиями

Если в распоряжении не имеется элементов, соответствующих сумме по модулю 2, то необходимо представить через конъюнкцию, дизъюнкцию и отрицание:

На следующей схеме представлен одноразрядный сумматор Si, который на выходе выдает значения Zi и Pi+1 :

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

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

Пример 6.22. Выберем в качестве множества

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

Переменное (точнее, значение этого переменного) подается на вход структурного элемента, называемого инвертором (рис. 6.24, а) и вычисляющего отрицание. Снимаемое с выхода инвертора отрицание , т.е. функция , подается на один из входов конъюнктора (рис. 6.24,5), на второй вход которого подается переменное . На выходе конъюнктора появляется функция . Аналогично прослеживается вычисление функции . Обе эти функции подаются на входы дизъюнктора (рис. 6.24, в), с выхода которого снимается функция (это не что иное, как сумма по модулю 2: ). И наконец, эта функция подается на вход инвертора, на выходе которого уже получается функция

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

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

Введем обозначение: если обозначаем подмножество переменных .

Определение 6.14. Пусть фиксированы множества: (булевых переменных).

Схемой из функциональных элементов над базисом (СФЭ), или просто схемой над базисом , либо некоторой константой из ;

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

При изображении схем входы обозначаются кружочками, а вершины, не являющиеся входами, — треугольниками, внутри которых записано обозначение функции, помечающей данную вершину. Выходы отмечаются "выходными" стрелками. На рис. 6.25 приведена СФЭ над базисом .

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

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

Определение 6.15. Пусть задана СФЭ над базисом 1. Принимается, что каждый вход СФЭ вычисляет булеву функцию, которой он помечен (т.е. некоторое переменное или константу).

2. Если вершина помечена функцией заходящая в нее дуга с номером исходит из вершины , которая вычисляет функцию , то вершина v вычисляет суперпозицию .

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

Пример 6.23. Рассмотрим СФЭ на рис. 6.25. Вершины и — входы СФЭ. Эти вершины вычисляют соответственно функции . Тогда вершина , равно как и вершина , согласно определению 6.15, вычисляет функцию (штрих Шеффера), а вершина (выход сети) — функцию , которая, как известно, равна конъюнкции .

СФЭ, изображенная на рис. 6.26, имеет два выхода, вычисляющие функции и .

Определение 6.16. Булева функция, вычисляемая СФЭ над базисом

В общем случае, если — множество всех переменных, которые служат метками входов схемы , т.е. булев оператор.

Замечание 6.10. В некоторых случаях функцию, вычисляемую данной СФЭ, определяют несколько иначе, полагая, что это функция, вычисляемая любой вершиной из подмножества выделенных вершин СФЭ. В частности, это могут быть и выходы. В любом случае договоримся из выделенных (в только что указанном смысле) вершин схемы проводить "выходную" стрелку.

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

Можно доказать и обратное: по любому булеву оператору может быть построена СФЭ над базисом Пример 6.24. Зададим таблицей булев оператор, отображающий (табл. 6.9).

Из таблицы легко увидеть, что (функция есть не что иное, как мажоритарная функция от переменных , и выше написана минимальная ДНФ для нее, см. пример 6.12). Представим функцию в базисе Жегалкина. Используя законы де Моргана, получим

СФЭ для булева оператора, заданного в табл. 6.9, над базисом Жегалкина приведена на рис. 6.27.
При проектировании СФЭ полезно иметь в виду числовой параметр, называемый ее сложностью.
Сложность СФЭ — это число ее вершин, не являющихся входами.
Приведенная на рис. 6.27 СФЭ над базисом Жегалкина имеет сложность 5.

Рассмотрим теперь СФЭ для того же оператора над стандартным базисом. По таблице (см. табл. 6.9) строим СДНФ для функции

Карта Карно для этой функции, изображенная на рис. 6.28, показывает, что ее нельзя минимизировать (точнее, записанная выше СДНФ и есть минимальная ДНФ для этой функции).

Но можно пойти по другому пути. Мы можем рассматривать табл. 6.9 как таблицу, определяющую частичную булеву Функцию . Минимизируя эту функцию по карте Карно*, изображенной на рис. 6.29, получаем

*На этой карте мы явно обозначили наборы, на которых функция принимает значение 0, проставив нули в соответствующих клетках. Тем самым мы хотим еще раз зафиксировать внимание на том, что не следует путать нули с прочерками: прочерк в клетке карты, задающей частичную функцию, означает, что на данном наборе значение функции не определено, т.е. не равно ни 0, ни 1.

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

Булев оператор, рассмотренный в этом примере, вычисляет двухразрядную сумму (по модулю 2) трех одноразрядных слагаемых. Его можно считать также одноразрядным двоичным сумматором — функциональным блоком многоразрядного двоичного сумматора — для двух слагаемых. Тогда функция г/1 интерпретируется как "сигнал переноса" в старший разряд. На рис. 6.31 изображено "соединение" трех СФЭ (таких, как показано на рис. 6.30), с помощью которого вычисляется сумма двух трехразрядных двоичных чисел. На третий вход сумматора для младшего разряда подается константа 0, а "сигнал переноса" старшего разряда есть старший разряд суммы, которая в общем случае будет четырехразрядным числом.

Замечание 6.11. Если мы проектируем СФЭ над стандартным базисом и хотим минимизировать ее сложность, то нам необходимо прежде всего построить соответствующую минимальную ДНФ. В этом случае мы можем принять во внимание еще один критерий, по которому минимизируется сама ДНФ, — число отрицаний. Среди всех минимальных (в смысле определения 6.6) ДНФ следует отобрать те, в которых число вхождений переменных под знаком отрицания является наименьшим. С точки зрения сложности СФЭ, которая будет построена по минимальной ДНФ, это означает, что в ней минимизируется число "инверторов" — вершин СФЭ, помеченных функцией отрицания.

Например, для функции, заданной картой Карно (рис. 6.32), к ядру, состоящему из простых импликант и , следует добавить простую импликанту , а не , поскольку она не содержит отрицаний.

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

4. Если в схеме из функциональных элементов S1 ее вход соединить с выходом некоторого функционального элемента из S1 без образования цикла для какого-либо функционального элемента (то есть его выход не должен соединяться, быть может, через другие функциональные элементы из S1 с его входом), то получившаяся конструкция S является схемой из функциональных элементов. Выходом S будет выход S1, а входами S - все входы S1, кроме того, который соединен с выходом функционального элемента. На рис.2.21 приведен пример подобной схемы:

Определение схемы из функциональных элементов завершено.

Теперь определим булевскую функцию, реализуемую данной схемой.

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

2. Если схема S1 реализует булевскую функцию f(x1,x2,…,xn), то схема S, построенная в п.2 определения схемы из функциональных элементов, реализует булевскую функцию, полученную из f(x1,x2,…,xn) отождествлением переменных, отвечающих объединенным входам схемы S1.

3. Пусть схема S1 реализует булевскую функцию f(x1,x2,…,xn), а схема S2 - булевскую функцию g(y1,y2,…,ym). Считаем, что все переменные x1,x2,…,xn,y1,y2,…,ym попарно различны. Тогда схема S, построенная в п.3 определения схемы из функциональных элементов, реализует булевскую функцию g(y1, y2, …, yi-1, f(x1,x2,…,xn), yi-1, … , ym), то есть функцию, получаемую путем подстановки в функцию g(y1,y2,…,ym) вместо аргумента yi, сопоставленного входу схемы S2, соединенному с выходом S1, функции f(x1,x2,…,xn).

4. Булевская функция, реализуемая схемой S, построенной в п.4 определения схемы из функциональных элементов, получается из булевской функции, реализуемой схемой S1, операцией, типа описанной в п. 3 настоящего определения. Например, приведенная на рис.2.21 схема реализует функцию f(x1,x2,x3,x4) = Ø( x1&Ø x2&(Øx3Úx4)).

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

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

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

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

Пусть имеются два двоичных числа:

X = xn xn-1 xn-2 … x2 x1 и Y = yn yn-1 yn-2 … y2 y1

(Здесь xi, yj - двоичные цифры 0 или 1.)

Требуется получить число Z, равное сумме чисел X и Y.

Рассмотрим вначале одноразрядный двоичный сумматор на два входа.

Здесь: xi - i- тая цифра числа X; yi - i-тая цифра числа Y; zi - i-тая цифра результата сложения - числа Z; pi+1 - перенос в следующий, (i+1)-ый разряд.

Опишем выходы сумматора как булевские функции его входов в виде следующей таблицы:

xi	yi	zi	pi+1
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

zi = f1(xi,yi) = Øxi&yi Úxi&Øyi; pi+1 = f2(xi,yi) = xi&yi.

Соответствующие схемы из функциональных элементов представлены на рис.2.23.

Рис.2.23. Функциональная схема одноразрядного двоичного сумматора на два входа.

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

В отличие от предыдущего случая теперь мы учитываем перенос из младшего разряда. Здесь: xi - i- тая цифра числа X; yi - i-тая цифра числа Y; pi - перенос из предыдущего, i-го разряда; zi - i-тая цифра результата сложения - числа Z; pi+1 - перенос в следующий, (i+1)-ый разряд.

Опишем выходы сумматора как булевские функции его входов в виде следующей таблицы:

хi	yi	pi	zi	pi+1
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Соответствующие схема из функциональных элементов представлены на рис.2.25.

Рис.2.25. Функциональная схема одноразрядного двоичного сумматора на три входа.

Сложение n-разрядных двоичных чисел можно осуществить, соединив n сумматоров таким образом, как это показано на рис.2.26.

В данной схеме сумматора первый элемент имеет два входа, а все остальные элементы - по три. Появление 1 на выходе yn+1 означает переполнение разрядной сетки, то есть попытка представить число, содержащее больше, чем n двоичных разрядов.

Рис.2.26. Схема n-разрядного двоичного сумматора.

В некоторых схемах сумматоров "замыкают" выход pn+1 последнего элемента на вход p1 первого. Тогда все элементы схемы сумматора будут иметь по три входа. Такое сложение называют циклическим. Оно находит свое применение при выполнении арифметических операций в ЭВМ.

Работа n-разрядного двоичного сумматора напоминает замóк типа "молния". Но есть существенная разность: замóк застегивается "шаг за шагом", последовательно. А сложение на двоичном сумматоре осуществляется "параллельно" за один шаг (такт), и выход полностью определяется текущим состоянием входов, независимо от их количества. То есть, если в момент времени t подать 2n сигналов на входы xn,xn-1, xn-2, … ,x2, x1 и yn,yn-1, yn-2,…,y2 ,y1, то n сигналов на выходах сумматора zn, zn-1, zn-2, … ,z2, z1 появятся в тот же момент времени, без задержки. Схемы из функциональных элементов называют поэтому комбинационными схемами, или схемами без памяти. Они не запоминают результатов своей предыдущей работы.

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

Такие схемы и способы их анализа и синтеза мы рассмотрим ниже.

Логические операции, выполняемые микропроцессором

Микропроцессор компьютера способен выполнять основные логические операции: конъюнкцию & (обозначение AND), дизъюнкцию (обозначение OR), отрицание Ø (обозначение NOT), строгую дизъюнкцию (или сложение по модулю 2) Å (обозначение XOR).

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

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

Но, вообще говоря, слово алгебра в математике понимается значительно шире.

А именно: Алгеброй называют множество объектов любой природы с определенными и замкнутыми на этом множестве операциями.

Если какая-либо операция l определена на множестве Q и результат ее также принадлежит этому множеству, то говорят, что операция l замкнута на этом множестве, или множество замкнуто относительно операции l. Например, множество натуральных чисел N замкнуто относительно операций сложения и умножения натуральных чисел, но не замкнуто относительно операций вычитания и деления, которые могут в качестве результата давать значения, не принадлежащие множеству натуральных чисел (вычитание – отрицательные числа, а деление – дробные).

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

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

Точно так же, рассмотренная в § 2 настоящей главы логика высказываний является алгеброй. Это алгебра высказываний, объектами которой являются высказывания, а определенными и замкнутыми на этих объектах являются операции дизъюнкции, конъюнкции и отрицания.

Две последние алгебры принадлежат к особому типу алгебр, называемых булевыми.[8])

дистрибутивность + относительно ´ и ´ относительно +:

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

коммутативность min и max:

min (x,y)=min(y,x), max (x,y)=max(y,x);

ассоциативность min и max:

min (x, min (y,z)) =min (min (x, y),z),

max (x, max (y,z)) =max (max (x, y),z);

дистрибутивность min относительно max:

min (x, max(y,z)) = max(min(x,y),min(x,z)),

max (x, min(y,z)) = min(max(x,y),max(x,z));

идемпотентность min и max:

свойства констант 0 и 1:

min(x,0)=0, min(x,1)=x, max(x,0)=x, max(x,1)=1.

Рекомендация: Проверьте (хотя бы на примерах) справедливость этих соотношений

[1] ) Кроме этих значений часто используются обозначения: T (true – истина) и F (false – ложь), а также 1 и 0.

[2] ) F и Ф называют в этом случае подформулами формулы логики высказываний.

[3] ) Естественно, логикой высказываний не исчерпывается все многообразие логических рассуждений. Кроме логики высказываний, важное значение имеют логика предикатов, модальная логика, нормативная логика, временная логика, многозначная логика, нечеткая логика и т.д.

[4] ) Как такое утверждение В найти или построить - это и есть часть доказательства, зачастую носящая эвристический, то есть поисковый, характер и относится к содержанию математической дисциплины, теорема из которой доказывается. Для нас важна форма доказательства, то есть, его структура.

[5] ) Как известно, формула А~В эквивалентна конъюнкции (AÉB)&(BÉA).

[6] ) См. книгу: Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. –М.:Наука, 1966. –120 с.

[7] ) Заинтересованному читателю можем порекомендовать, например, книгу: О.А. Маслюков. Вычислительная техника и программирование. -М.:Высшая школа,1993.-208 с.

[8] ) Название булевы эти алгебры получили в честь известного английского математика Джорджа Буля (1815-1864).

[9] ) Более подробную информацию о булевых алгебрах можно получить в книге: И.М. Яглом. Необыкновенная алгебра. -М.: Наука, 1968. -70с.

Раздел: Информатика, программирование
Количество знаков с пробелами: 47833
Количество таблиц: 11
Количество изображений: 7

Читайте также: