Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекция 03 - ЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ ЭВМ.doc
Скачиваний:
83
Добавлен:
19.02.2016
Размер:
276.99 Кб
Скачать

9

Лекция № 3

Логические основы построения эвм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • входной Z= [z0,z1,z2, ... ,zF],

  • выходной W= [w0,w1,w2,...,wG],

  • состояний А= [а0,а1,a2,... ,аM].

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

(1)

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

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

(2)

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

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

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

(3)

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

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

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

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

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