
	Главная Схемы Документация Студентам Программы Поиск Top50

Поиск по сайту

Навигация

Главная

Схемы

Документация

Файлы

Информация

Студентам

Студентам > Рефераты > Вычислительные машины и системы

Вычислительные машины и системы

Страница: 7/12

называют 2 алфавитом 0 переменной x 4i 0. В современных ЭВМ алфавит вход-

ных и выходных сигналов состоит из двух букв: 0 и 1.

На входы модели поступают в каждый тактовый момент упорядо-

ченные наборы букв, называемые 2 словами 0. Множество всех допустимых

наборов слов называется 2входным алфавитом 0 X данной схемы. Анало-

гично множество всех допустимых комбинаций, образуемых выходными

сигналами, называется 2выходным алфавитом 0 Y.

Математические модели отражают зависимость между входными и

выходными переменными схемы посредством системы уравнений:

y 4j 0(t) = f{x 41 0(t),x 42 0(t)...,x 4l 0(t), q 41 0(t),q 42 0(t),,...,q 4s 0(t)} (I)

где j = 1,2,...,m, а переменные q 41 0,q 42 0,...,q 4s 0 отражают внутренние

состояния схемы.

Если переменные y 4i 0 не зависят от внутреннего состояния схе-

мы, то одинаковым наборам входных переменных соответствует один и

тот же набор выходных переменных. Такие схемы называются 2комбина-

2ционными 0.

При этом система уравнений может быть записана в виде:

y 4j 0(t) = f{x 41 0(t),x 42 0(t)...,x 4l 0(t)}, где j = 1,2,...,m. (II)

Функции такого вида могут принимать только конечное число

значений, и зависят от аргументов, также принимающих конечное

число значений. Такие функции называются 2 переключательными 0.

В дальнейшем мы будем рассматривать переключательные функ-

ции, которые могут принимать только два значения - 0 и 1, и аргу-

менты которых также могут принимать только одно из этих двух зна-

чений. Такие переключательные функции получили название 2 булевых

2функций 0.

Если выходные переменные y 4i 0(t) зависят не только от входных

переменных, но и от внутреннего состояния схемы, то для полного

ее описания необходимо указать еще одну систему уравнений:

- 3 -

q 4n 0(t+1) = 7f 0{x 41 0(t),x 42 0(t)...,x 4l 0(t), q 41 0(t),q 42 0(t),,...,q 4s 0(t)}, (III)

где n = 1,2,...,s.

Эта система отражает зависимость внутреннего состояния схемы

в (t+1) такте от ее состояния и входных сигналов в такте t.

Схемы, описываемые уравнениями I и III, получили название

2цифровых автоматов 0.

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

1) входной алфавит слов X;

2) выходной алфавит слов Y;

3) алфавит внутренних состояний Q;

4) начальное состояние автомата q 40 0;

5) функция переходов A(q,x);

6) функция выходов B(q,x).

2Функция переходов 0 определяет зависимость состояния автомата

q(t+1) в момент времени t+1 от состояния автомата q(t) и входного

сигнала x(t) в момент t.

2Функция выходов 0 определяет зависимость выходного сигнала

y(t) от состояния автомата q(t) и входного сигнала x(t).

Автомат, описываемый системой уравнений

72 0 q(t+1) = A{q(t),x(t)},

72 0 y(t) = B{q(t),x(t)}

называется 2автоматом Мили 0.

Автомат, выходной сигнал которого y(t) в тактовый момент t

зависит только от состояния автомата q(t) и не зависит от входно-

го сигнала, называется 2 автоматом Мура 0 и описывается системой:

72 0 q(t+1) = A{q(t),x(t)},

72 0 y(t) = B{q(t)}.

ПЕРВЫЙ СЕМЕСТР

ЛЕКЦИЯ N 6

2МЕТОДЫ УПРОЩЕНИЯ (МИНИМИЗАЦИИ) БУЛЕВЫХ ФУНКЦИЙ

Сложные булевы функции могут быть построены из более прос-

тых.

2Элементарными функциями 0 называются функции, образованные пу-

тем использования однотипных логических операций: только операции

И, только операции ИЛИ и т.д.

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

вать не все элементарные функции, а только ту или иную часть их,

называемую системой. Система элементарных функций f 41 0, ..., f 4k 0 на-

зывается функционально полной, если любую сложную булеву функцию

можно записать в виде формулы через функции f 41 0, ..., f 4k 0.

Так, любую функцию можно представить с помощью одних только

операций И-НЕ или только операций ИЛИ-НЕ.

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

система из трех функций: И, ИЛИ и НЕ.

Используя законы алгебры логики, можно упрощать сложные ло-

гические выражения. Упрощение заключается в уменьшении количества

букв и количества отрицаний в выражении, что позволяет упростить

схему устройства с жесткой логикой или программу устройства с

программируемой логикой. Такое упрощение позволяет уменьшить се-

бестоимость и увеличить быстродействие устройства.

Рассмотрим функцию

4_________

7( 4_ 7 ) 4 _

f(a,b.c) = a 5. 72 0b V a 5. 0c 72 0 V a 5. 0b

79 0

Используя законы алгебры логики, можно привести эту функцию

к виду:

4_ 0 5 0 4_ 0 4 _ 0 4_ __ _ 0 4_ _

f(a,b.c) = a 5. 0(b 5. 0(a 5 0V 5 0c)) V a 5. 0b = ab V abc V ab = ab V ab

4применяем 0 4 0 4 применяем

4законы де Моргана 0 4 закон поглощения

Одной и той же логической функции может быть поставлено в

соответствие неограниченное количество различных эквивалентных

формул. Наиболее удобными для практического использования являют-

ся так называемые 2нормальные формы 0 представления сложных логичес-

ких функций.

2Элементарной конъюнкцией 0 Q называется логическое произведе-

ние переменных и их отрицаний, причем каждая переменная должна

встречаться в произведении только один раз.

- 2 -

4_ _

Пример элементарной конъюнкции: Q = x 41 0x 42 0x 43 0x 44 0x 46 0.

Аналогично 2элементарной дизъюнкцией 0 В называется логическая

сумма переменных и их отрицаний, причем каждая переменная должна

встречаться в сумме только один раз.

Пример элементарной дизъюнкции: D = x 41 0 V x 43 0 V x 44 0.

Формула, эквивалентная заданной и представляющая собой логи-

ческую сумму элементарных конъюнкций, называется 2дизъюнктивной

2нормальной формой 0 (ДНФ) заданной формулы. Дизъюнктивная нормаль-

ная форма существует для любой логической функции.

Аналогично считается, что логическая функция задана своей

2конъюнктивной 0 2нормальной формой 0 (КНФ), если она выражена посредс-


¹	²	³	⁴	⁵	⁶	⁷	⁸	⁹	¹⁰	¹¹	¹²