Основы алгебры логики

ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

1. Общие сведения о конечных цифровых автоматах

2. Основы алгебры логики

3. Синтез комбинационных схем

Общие сведения о конечных цифровых автоматах

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

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

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

Отличительные особенности реальных цифровых автоматов:

· имеют дискретное конечное множество внутренних состояний, входных и выходных сигналов, а также число входных и выходных каналов;

· переход из одного состояния в другое осуществляется скачкообразно в дискретные моменты времени;

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

Цифровые автоматы функционируют в дискретные моменты времени, временной интервал Т между которыми называется тактом.

В зависимости от того, чем определяется время Т, различают автоматы синхронного и асинхронного действия.

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

Для цифрового автомата асинхронного действия Т ¹ const и определяется моментами поступления входных сигналов, а переход автомата из одного состояния в другое осуществляется при неизменном состоянии входа.

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

Абстрактные цифровые автоматы рассматриваются как «черный ящик», имеющий один вход и один выход, т.е. при рассмотрении таких автоматов отвлекаются от структуры как самого цифрового автомата, так и его входных Z (t) и выходных W (t).

Для задания абстрактного автомата необходимо знать три алфавита:

· входной Z = [ z ₀, z ₁, z ₂,..., z_F ],

· выходной W = [ w ₀, w ₁, w ₂,..., w_G ],

· состояний А = [а₀, а ₁, a ₂,..., а_M ].

Тогда закон функционирования абстрактного цифрового автомата может быть задан уравнениями:

(1)

где d (а, z) — функция переходов автомата; l (a, z) — функция выходов автомата; а₀ — начальное состояние автомата; a (t), z (t), w(t) — состояния автомата, входной и выходной сигнал в момент времени t соответственно.

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

(2)

где m [ a (t)] —сдвинутая функция выхода.

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

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

(3)

т.е. каждому входному сигналу z (t) сопоставляется свой выходной сигнал w (t).

Наиболее распространенными стандартными способами задания абстрактных цифровых автоматов является задание их с помощью матриц, таблиц переходов и выходов, а также с помощью направленного графа, вершины которого отождествляются с состояниями автомата, а соединяющие их стрелки — с входными и выходными сигналами.

В случае, когда два цифровых автомата с общим входным и выходным алфавитом индуцируют одно и то же отображение множества слов во входном алфавите в множество слов в выходном алфавите, такие автоматы эквивалентны.

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

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

Основы алгебры логики

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

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