Пример практического применения алгебры логики

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

Примем за аргументы переменные х„ х2, х3, которыми обозначим выключатели на соответствующих этажах. Тогда выходом устройства будет переключательная функция 3 аргументов f(xh х2, х3). Переменная Х|, как и функция f € {0, 1}. Будем считать, что х3 = 1, если выполнено одно из действий над выключателем, причем неважно какое — включить или выключить его. При этом неважно также, что конкретно означает f = 1 — горящую или выключенную лампочку. Важным является другое. Если на одном из этажей произведено действие над выключателем (Xj = 1), то лампочка должна адекватно на него отреагировать. Если на одном из этажей Xj = 1 означает включить лампочку (f= 1), то Xj = 1 на любом другом этаже может означать только ее отключение (f = 0), т.е. действию равно противодействие. Если третий аргумент окажется равным единице (xj = 1), то функция вновь примет единичное значение. Таким образом, равенство 1 двух аргументов обратит функцию f в 0, а трех аргументов — в 1. Описанный алгоритм можно задать таблично (табл. 4.9) или описать аналитически, например в Сов. ДНФ:

Таблица 4.9

Табличное представление алгоритма

Х1

X,

хз

f3

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

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

Цифровые автоматы

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

Понятие цифрового автомата (ЦА) как средства для представления и обработки любых видов информации является одним из основных понятий информатики. Сегодня создаются и используются различные системы и устройства для преобразования дискретной информации, широко применяемые в качестве различного рода технических автоматов, вычислительных устройств и их функциональных блоков, устройств управления роботами, управляющих объектами по заданному алгоритму и т.д. Большой класс таких преобразователей объединяется под общим названием автомат. Некоторые авторы определяют автомат как математическую модель реальных преобразователей дискретной информации. Его функционирование состоит в том, что последовательность zv ... символов конечного или в общем случае бесконечного алфавита Z, поступающая на вход, вызывает на его выходе определенную последовательность tOj, со2, ... символов того же или другого алфавита.

Таким образом, самая общая математическая модель преобразователя дискретной информации (ПДИ) описывается функцией (р: Z* -» W*, которая отображает множество Z* всех последовательностей символов алфавита Z в другое множество W* последовательностей символов алфавита W. Такая интерпретация позволяет схематично представить преобразователь как устройство, реализующее отображение одного множества на другое (рис. 4.34).

Формальная модель ПДИ

Рис. 4.34. Формальная модель ПДИ

Результат преобразования вход => выход (см. рис. 4.34) зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и оттого, что происходило раньше, от предыстории преобразования. Чтобы как-то запоминать предыстории и отличать одну от другой, преобразователь должен иметь память. Для этого в модель (см. рис. 4.34) вводят алфавит состояний Q = {qb с^, ... , qm} и такой преобразователь (рис. 4.35) называют конечным автоматом (КА), если множество входных сигналов Z и множество возможных состояний Q конечны.

Конечный автомат

Рис. 4.35. Конечный автомат

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

Преобразователи дискретной информации, математической моделью которых является АА, называют цифровыми автоматами (ЦА). Одним из наиболее распространенных в настоящее время примеров ЦА является ЭВМ. Автоматы с числом внутренних состояний более одного (|Q| > 1) составляют класс автоматов с памятью. Частным случаем таких автоматов являются комбинационные схемы, выход которых не зависит от состояния и определяется текущим входным символом zf. Математической моделью комбинационной схемы является функция co(t) = Mz(t)).

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

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

Обобщенная схема ЦА

Рис. 4.36. Обобщенная схема ЦА

Комбинационная схема служит для преобразования входных сигналов X и информации о состоянии устройства Q в выходные сигналы Y и сигналы возбуждения элементов памяти U, определяющие смену состояний автомата.

Память строится из предварительно выбранных элементарных автоматов — триггеров.

Функционирование такого автомата в общем виде описывается системой функций:

где X — функция выходов;

8 — функция переходов; у — функция возбуждения триггеров;

X, Y, U, О — двоичные слова:

X = (Х[ ... Х[... xL) — входное слово;

Y = (у[ ... у„ ... yN) — выходное слово;

U = (U[ ... иг... uR) — слово функций возбуждения (ФВ);

Q = (q( ... qr... qR) — слово состояния автомата.

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

и R функций возбуждения:

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >