Только лучшие рефераты рунета    
 
 

Партнеры:



 
 

Реферат "Вычислительные машины"






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

 

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).

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

 7(

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

 7*

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

 79

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

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

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

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

 7(

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

 7*

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

 79

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

ЛЕКЦИЯ N 5

 2ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ УЗЛОВ ЭВМ

Если для двух любых состояний q 4i 0 и q 4j 0 автомата имеется вход-

ной сигнал, переводящий автомат из состояния q 4i 0 в q 4j 0, то такой

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

Мура имеет  2полную систему выходов 0, если выходные сигналы различны

для всех его состояний.

При построении схем ЭВМ в качестве элементов памяти исполь-

зуются элементарные автоматы.  2Элементарный автомат 0 - это автомат

Мура с двумя внутренними состояниями, двумя различными выходными

сигналами и несколькими входами, обладающий полными системами пе-

реходов и выходов.

 2ТЕОРИЯ БУЛЕВЫХ ФУНКЦИЙ

Булевыми функциями называют переключательные функции, кото-

рые так же, как и их аргументы, принимают только два значения:

0 и 1.

Булевы функции могут быть заданы в виде формул или таблиц.

Формулы позволяют представлять функции в более компактном виде,

чем таблицы, так как таблица для функции от n аргументов будет

содержать 2 5n 0 строк (или столбцов, в зависимости от формы табли-

цы). С другой стороны, таблицы дают наглядное представление для

простых функций.

Приведем в качестве примера наиболее часто встречающиеся

функции от одной и двух переменных:

1) Переменная x:

f(x) = x

2) Инверсия переменной x (функция НЕ):

 4_

f(x) = x

3) Константа нуля:

f(x) = 0

4) Константа единицы:

f(x) = 1

.

- 2 -

5) Дизъюнкция (функция ИЛИ):

f(x 41 0,x 42 0) = x 41 0 V x 42

Может встречаться другое обозначение: f(x 41 0,x 42 0) = x 41 0 | x 42 0.

Таблица истинности (соответствия) для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 1 ¦

L-----+-----+----------

6) Конъюнкция (функция И):

f(x 41 0,x 42 0) = x 41 0  5. 0 x 42

Может встречаться другое обозначение: f(x 41 0,x 42 0) = x 41 0 & x 42 0.

Таблица истинности для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0  5. 0 x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 0 ¦

¦ 1 ¦ 0 ¦ 0 ¦

¦ 1 ¦ 1 ¦ 1 ¦

L-----+-----+----------

7) Функция ИЛИ-НЕ:

 4_______

f(x 41 0,x 42 0) = x 41 0 V x 42

Таблица истинности для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 1 ¦

¦ 0 ¦ 1 ¦ 0 ¦

¦ 1 ¦ 0 ¦ 0 ¦

¦ 1 ¦ 1 ¦ 0 ¦

L-----+-----+----------

.

- 3 -

8) Функция И-НЕ:

 4_______

f(x 41 0,x 42 0) = x 41 0  5. 0 x 42

Таблица истинности для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 1 ¦

L-----+-----+----------

9) Функция ИСКЛЮЧАЮЩЕЕ ИЛИ (сумма по модулю 2):

f(x 41 0,x 42 0) = mod2(x 41 0,x 42 0)

Таблица истинности для этой функции имеет вид:

------T-----T-------------¬

¦ x 41 0 ¦ x 42 0 ¦ mod2(x1,x2) ¦

+-----+-----+-------------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 0 ¦

L-----+-----+--------------

 2Аксиомы алгебры логики

В алгебре логики определено отношение эквивалентности (=) и

три операции: дизъюнкция, конъюнкция и отрицание.

Отношение эквивалентности удовлетворяет следующим свойствам:

x=x - рефлексивность; если x=y, то y=x - симметричность; если x=y

и y=z, то x=z - транзитивность. Из отношения эквивалентности сле-

дует 2 принцип подстановки 0: если x=y, то в любой формуле, содержа-

щей x, вместо x можно подставить y, и будет получена эквивалент-

ная формула.

Алгебра логики определяется следующей системой аксиом:

x = 0, если x  7- 0 1 7 )

 78 0 (1)

x = 1, если x  7- 0 0 7 0

1 V 1 = 1 7 )

 78 0 (2)

0 5 . 0 0 = 0 7 0

- 4 -

0 V 0 = 0 7 )

 78 0 (3)

1  5. 0 1 = 1 7 0

0 V 1 = 1 V 0 = 1 7 )

 78 0 (4)

0 5 . 0 1 = 1 5 .  00 = 0 7 0

 4_

0 = 1 7 )

 4_ 0  78 0 (5)

1 = 0 7 0

Аксиома (1) утверждает, что в алгебре логики рассматриваются

только двоичные переменные, аксиомы (2)-(4) определяют операции

конъюнкции и дизъюнкции, а аксиома 5 - операцию отрицания.

Если в аксиомах (2)-(5), заданных парами утверждений, произ-

вести взаимную замену операций дизъюнкции и конъюнкции, а также

элементов 0 и 1, то из одного утверждения пары будет получено

другое. Это свойство называется принципом двойственности.

 2Теоремы алгебры логики

С помощью аксиом алгебры логики можно доказать целый ряд те-

орем и тождеств. Одним из эффективных методов доказательства тео-

рем является 2 метод перебора 0 всех значений переменных: если теоре-

ма истинна, то при подстановке любых значений переменных в обе

части выражения, формулирующего утверждение теоремы, должно полу-

читься тождество.

Методом перебора можно убедиться в справедливости следующих

теорем:

идемпотентные законы

x V x = x 7 )

 78

x  5. 0 x = x 7 0

коммутативные законы

x V y = y V x 7 )

 78

x  5. 0 y = y  5. 0 x 7 0

ассоциативные законы

(x V y) V z = x V (y V z) 7 )

 78

(x  5. 0 y)  5. 0 z = x  5. 0 (y  5. 0 z) 7 0

.

- 5 -

дистрибутивные законы

x  5. 0 (y V z) = x  5. 0 y V x  5. 0 z 7 )

 78

x V y  5. 0 z = (x V y) 5. 0(x V z) 7 0

законы отрицания 4 _

x V x = 1 7 )

 4_ 0  78

x  5. 0 x = 0 7 0

0 V x = x 7 )

 78

1  5. 0 x = x 7 0

1 V x = 1 7 )

 78

0  5. 0 x = 0 7 0

законы двойственности (теоремы де Моргана)

 4_____ _ _

x V y = x  5.  0y 7 )

 4_____ 0  4_ 0  4_ 0  78

x  5. 0 y = x V y 7 0

закон двойного отрицания 4  0  4 _____

 7( 0  4_ 7 )

 72 0 x 7 2 0 = x

 79 0

законы поглощения

x V x  5. 0 y = x 7 )

 78

x 5. 0(x V y) = x 7 0

операции склеивания 4 _

x  5. 0 y V x  5. 0 y = x 7  0  7)

 4_ 0  78

(x V y) 5. 0(x V y) = 7  0x  70

операции обобщенного склеивания

 4_ _

x 5. 0y V x 5. 0z V y 5. 0z = x 5. 0y V x 5. 0z  5  7)

 4_ 0  5  4_ 5  0  78

(x V y) 5. 0(x V z) 5. 0(y V z) = 7  0(x V y) 5. 0(x V z)  70

 4_

x V x  5. 0 y = x V y 7 )

 4_ 0  78

x 5. 0(x V y) = x 7  5. 0 y  70

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

ЛЕКЦИЯ 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 В называется логическая

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

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

 4_

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

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

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

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

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

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

 2конъюнктивной 0  2нормальной формой 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_ _

f(a,b.c) = ab V ab,

КНФ будет иметь вид

 4_ _

f(a,b.c) = (a V b)(b V c).

Одна и та же функция путем эквивалентных преобразований мо-

жет быть представлена различными КНФ и ДНФ. Из всей совокупности

нормальных форм, представляющих данную функцию, выделяют одну КНФ

и одну ДНФ, именуемые совершенными.

 2Минтермом 0 (m) n аргументов называется логическое произведе-

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

изведение в прямой или инверсной форме.

Минтермы могут быть пронумерованы, причем номер минтерма оп-

ределяется как десятичный эквивалент двоичного числа, образован-

ного из значений переменных, входящих в данный набор: если пере-

менная входит в прямой форме, то ей соответствует единица, если в

инверсной - ноль.

 2Макстермом 0 (M) n аргументов называется логическая сумма этих

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

или инверсной форме. Номер макстерма задается аналогично номеру

минтерма.

.

- 3 -

Рассмотрим в качестве примера случай двух аргументов:

------T-----T-------------T--------------¬

¦ a ¦ b ¦ минтерм ¦ макстерм ¦

+-----+-----+-------------+--------------+

¦ ¦ ¦  4_ 0  4_ 0 ¦  4_ 0  4_ 0 ¦

¦ 0 ¦ 0 ¦ m 40 0 = a 5. 0b ¦ M 40 0 = a V b ¦

¦ ¦ ¦  4_ 0 ¦  4_ 0 ¦

¦ 0 ¦ 1 ¦ m 41 0 = a 5. 0b ¦ M 41 0 = a V b ¦

¦ ¦ ¦  4_ 0 ¦  4_ 0 ¦

¦ 1 ¦ 0 ¦ m 42 0 = a 5. 0b ¦ M 42 0 = a V b ¦

¦ ¦ ¦  4  0 ¦ ¦

¦ 1 ¦ 1 ¦ m 43 0 = a 5. 0b ¦ M 43 0 = a V b ¦

L-----+-----+-------------+---------------

Минтермы и макстермы можно геометрически представить на кар-

тах (диаграммах) Вейча. Так, для двух переменных карта Вейча бу-

дет представлять собой квадрат, причем левая половина квадрата

определяется переменной a, а верхняя половина квадрата - перемен-

ной b. Это означает, что левая 4_ 0 половина квадрата соответствует

значению переменной a, правая - a, верхняя половина соответствует

 4_

b, нижняя b.

Карта Вейча для двух переменных:

 4_

 2a a

------T-----¬

¦ ¦  4_ 0 ¦

 2b  0¦ a 5. 0b ¦ a 5. 0b ¦

¦ ¦ ¦

+-----+-----+

 4_ 0 ¦  4_ 0 ¦  4_ 0  4_ 0 ¦

 2b  0¦ a 5. 0b ¦ a 5. 0b ¦

¦ ¦ ¦

L-----+------

.

- 4 -

Карта Вейча для 5  0трех переменных:

 4_

 2a a

 5-------+------¬ -------+------¬

--------T-------T-------T-------¬

¦  4_ 0 ¦ ¦  4_ 0 ¦  4_ 0  4_ 0 ¦

 2b  0¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦

¦ ¦ ¦ ¦ ¦

+-------+-------+-------+-------+

 4_ 0 ¦  4_ 0  4_ 0 ¦  4_ 0 ¦  4_ 0  4_ 0 ¦  4_ 0  4_ 0  4_ 0 ¦

 2b  0¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦

¦ ¦ ¦ ¦ ¦

L-------+-------+-------+--------

 4_ 0  5L------T------- 4 _

 2c 0  2c c

 2Свойства минтермов и макстермов:

1) Минтерм является инверсией некоторого макстерма и наобо-

рот: 4 _

m 4i 0 = M

2 5n 0-1-i

 4_

M 4i 0 = m

2 5n 0-1-i

 4_

Пример: m 41 0 = 4  0M 42 0 (заштрихованная площадь соответствует макс-

терму, незаштрихованная - минтерму).

 1-TTT 0T 1-- 0-¬

 1+++++ ¦

 1++++ 0L 1TTT 0+

 1+++++++++

 1L+++++++-

2) Логическая сумма всех минтермов для любого заданного чис-

ла переменных равна 1.

2 5n 0-1

V m 4i 0 = 1.

i=0

3) Логическое произведение всех макстермов для любого задан-

ного числа переменных равно 0.

2 5n 0-1

 7L 0 M 4i 0 = 0.

i=0

- 5 -

4) Два неодинаковых минтерма или макстерма имеют хотя бы од-

ну переменную, входящую в один из них в прямой, а в другой - в

инверсной форме, следовательно

m 4i 5. 0m 4j 0 = 0, если i  7- 0 j;

M 4i 0 V M 4j 0 = 1, если i  7- 0 j.

 2Основная теорема алгебры логики 0: любую булеву функцию от n

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

называется 2 совершенной нормальной дизъюнктивной формой 0, или логи-

ческим произведением макстермов, которое называется 2 совершенной

 2нормальной конъюнктивной формой 0.

Логические функции отражают не только принцип работы некото-

рых частей ЭВМ, но и их состав, если каждой элементарной функции

соответствует реальный физический элемент. Любая сложная логичес-

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

часть построена с помощью такого набора элементов, который реали-

зует все функции одной из функционально полных систем. Такой на-

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

Поскольку каждая функция может быть представлена в виде раз-

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

на при помощи различных логических схем. Очевидно, что более

простому логическому уравнению соответствует более простая схема.

Упрощение (минимизация) функции сводится к получению ее минималь-

ной дизъюнктивной или конъюнктивной нормальной формы, т.е. такой

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

знаков логических операций.

Существует несколько методов минимизации. В дальнейшем мы

рассмотрим метод непосредственных преобразований и метод диаграмм

Вейча.

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

ЛЕКЦИЯ N 7

 2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

 2Метод непосредственных преобразований

Суть данного метода заключается в том, что минимизация ис-

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

ным членам или группам членов формулы, выражающей данную логичес-

кую функцию, основных законов алгебры логики с целью получения

минимальной формы функции, т.е. такой, которая не содержит лишних

переменных или членов.

Лишними переменными или членами являются те, которые не вли-

яют на значение преобразуемой формулы.

Пример:

 4_  5  4_

x 41 5. 0x 42 5. 0x 43 0 V x 41 5. 0x 42 5. 0x 43 0 = x 42 5. 0x 43 5. 0(x 41 5  0V 5  0x 41 0) = x 42 5. 0x 43 5. 01 = x 42 5. 0x 43

т.е. в исходной формуле лишней являлась двоичная переменная x 41 0.

Примечание: произведенная операция называется "склеиванием"

членов формулы.

Действия, отвечающие методу непосредственных преобразований,

обычно проводятся в следующем порядке:

1) Выявляются группы двоичных переменных исходной формулы, к

которым можно применить операцию склеивания или другие законы ал-

гебры логики, приводящие выражение к более простой форме.

2) Упрощение исходной формулы путем применения к выявленным

группам соответствующих законов.

3) Преобразование промежуточной логической формулы с целью

образования таких групп переменных, к которым можно применить уп-

рощающие законы алгебры логики. Здесь могут проводиться:

- группирование членов;

- действия по раскрытию скобок и выносу за скобки;

- добавление фиктивных членов, т.е. таких, совокупность ко-

торых тождественно равна нулю;

- логическое умножение одного или нескольких членов на логи-

ческую сумму переменной и ее отрицания.

4) Упрощение преобразованной промежуточной логической форму-

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

ДНФ.

5) Выявление и удаление из полученной предварительной формы

лишних членов, что дает минимальную форму исходной логической

функции.

В качестве примера рассмотрим минимизацию следующей функции:

 4_ _ _ _

f(a,b,c) = ab V bc V bc V ab =

- 2 -

(используем метод умножения всех членов формулы на сумму тех пе-

ременных и их отрицаний, которые отсутствуют в данном члене;)

 4_ _ _ _ _ _ _ _

= ab(cVc) V bc(aVa) V bc(aVa) V ab(cVc) =

(в результате, отбросив повторяющиеся члены, получаем СДНФ функ-

ции;)

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

= abc V abc V abc V abc V abc V abc V abc V abc =

L-- L=- L-- L=-

 4_ __ _ _ _ __ _

= abc V abc V abc V abc V abc V abc =

(перегруппировываем члены с целью их упрощения)

 4_  9  4 _ _ _ _ _

= b 9c 0(aVa) V ab(cVc) V ac(bVb) =

(окончательно получим)

 4_ _ _

= bc V ab V ac.

Однако группирование членов после умножения можно провести и

несколько иначе:

 4_ _ _ _ _ _ _ _ _

f(a,b,c) = ab(cVc) V bc(aVa) V ac(bVb) = ab V bc V ac.

Следовательно, данная функция имеет две минимальные формы.

Недостатком метода непосредственной минимизации является

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

Кроме того, метод в целом весьма трудоемок, результат минимизации

в сильной степени зависит от квалификации и интуиции человека,

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

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

 2Метод минимизации с помощью карт Вейча

Данный метод наиболее применим в инженерной практике благо-

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

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

(до 8). Преимущество этого метода состоит в том, что нет необхо-

димости приводить функцию к СДНФ.

Рассмотрим изображение на карте Вейча функции

 4__ _ _ _ __ _ __ _

f(a,b,c,d) = cd V abd V abc V abcd V abcd V bcd

- 3 -

При нанесении заданной функции на карту никаких предвари-

тельных преобразований не проводится. Каждый дизъюнктивный член

рассматривается в отдельности, и в соответствующие ему квадратики

вписывается 1 (т.е. дизъюнктивный член развертывается до минтер-

мов).

Например, нанесение на карту вейча заданной функции выполня-

ется в следующей последовательности:

a

----+---¬

-----T---T---T---¬ ----T---T---T---¬ ----T---T---T---¬

¦¦  _1 . ¦ ¦ ¦  _1 . ¦ ¦  _1 . ¦  _1 . ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦  _1 . ¦

b ++---+---+---+---+¬ +---+---+---+---+ +---+---+---+---+

¦¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦  _1 . ¦

L+---+---+---+---++ d +---+---+---+---+ +---+---+---+---+

¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦

+---+---+---+---+- +---+---+---+---+ +---+---+---+---+

¦  _1 . ¦ ¦ ¦  _1 . ¦ ¦ 1 ¦ ¦ ¦ 1 ¦ ¦ 1 ¦ ¦ ¦ 1 ¦

L---+---+---+---- L---+---+---+---- L---+---+---+----

L---T----

 4__ 0 c 4  0  4 __ _ __ _ _ _

cd cd V abd cd V abd V abc

----T---T---T---¬ ----T---T---T---¬ ----T---T---T---¬

¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦

+---+---+---+---+ +---+---+---+---+ +---+---+---+---+

¦ ¦ ¦ ¦ 1 ¦ ¦ ¦ ¦ ¦ 1 ¦ ¦ ¦ ¦ ¦ 1 ¦

+---+---+---+---+ +---+---+---+---+ +---+---+---+---+

¦ ¦ ¦ ¦ ¦ ¦  _1 . ¦ ¦ ¦ ¦ ¦ 1 ¦  _1 . ¦  _1 . ¦ ¦

+---+---+---+---+ +---+---+---+---+ +---+---+---+---+

¦ 1 ¦ ¦  _1 . ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦

L---+---+---+---- L---+---+---+---- L---+---+---+----

 4__ _ _ _ __ _ _ _ __ _ _ _

cd V abd V abc V cd V abd V abc V cd V abd V abc V

 4__ _ __ _ __ __ _ __

V abcd V abcd V abcd V abcd V abcd V bcd

Следующий шаг заключается в нахождении на карте простых имп-

ликант, т.е. в склеивании минтермов. Нахождение простых импликант

является результатом последовательного применения теоремы:

 4_

x 41 0x 42 0x 43 0...x 4n 0 V x 41 0x 42 0x 43 0...x 4n 0 = x 42 0x 43 0...x 4n

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

группировки минтермов, отмеченных единицей.

Рассмотрим правила группировки на диаграмме для четырех пе-

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

- 4 -

числа переменных. Группирование выполняется в следующем порядке:

а) группа из восьми членов может быть представлена одной пе-

ременной, если две смежные строки, либо два смежных столбца, либо

две крайние строки, либо два крайних столбца, соответствующих

этой переменной, заполнены единицами;

б) группа из четырех членов может быть представлена посредс-

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

- строка диаграммы,

- столбец диаграммы,

- квадрат из двух строк и двух столбцов,

- концы двух смежных строк,

- концы двух смежных столбцов,

- четыре угла диаграммы;

в) группа из двух членов может быть представлена посредством

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

- два смежных квадратика,

- два противоположных конца одной строки,

- два противоположных конца одного столбца.

При группировке единиц на диаграмме необходимо попытаться

сначала образовать члены, содержащие одну переменную, затем чле-

ны, содержащие две переменные, и, наконец, члены, содержащие три

переменные. Один и тот же минтерм может входить 2 несколько раз 0 в

выражение функции, не изменяя ее значения. Поэтому единицу или

группу единиц можно несколько раз включать в различные комбина-

ции. В нашем случае минимизированная функция будет иметь вид:

 4__ _ _ _  0  4_ _ 0 ___

f(a,b,c,d) = cd V abd V abc V abd V bcd V abd.

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

ЛЕКЦИЯ N 8

 2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

(окончание)

Обычно для проверки правильности результата, полученного с

помощью одного из методов минимизации, либо используют другой ме-

тод (хотя при наличии у функции нескольких минимальных форм могут

быть получены несовпадающие результаты), либо проверяют на тож-

дественность исходную и минимальную формы методом перебора всех

возможных комбинаций значений переменных (однако уже для 20 пере-

менных число возможных комбинаций превышает миллион).

В качестве примера проведем минимизацию рассматривавшейся

ранее функции

 4_ _ _ _

f(a,b,c) = ab V bc V bc V ab

с помощью карты Вейча. Как видно из диаграммы, возможны две мини-

мальные дизъюнктивные формы:

a

----+---¬

----T---T---T---¬

b ¦ 1 ¦ ¦  _1 . ¦  _1 . ¦

+---+---+---+---+

¦ 1 ¦  21 0 ¦  21 0 ¦ ¦

L---+---+---+----

L---T----

c

 4_ _  0  4_

f(a,b,c) = ac V ab V bc

a

----+---¬

----T---T---T---¬

b ¦  _1 . ¦ ¦  21 0 ¦  _1 . ¦

+---+---+---+---+

¦ 1 ¦ 1 ¦  21 0 ¦ ¦

L---+---+---+----

L---T----

c

 4_ _  0  4_

f(a,b,c) = bc V ac V ab

.

- 2 -

 2ЭЛЕМЕНТЫ И УЗЛЫ ЭВМ

===================

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

Системой элементов ЭВМ называется функционально полный набор

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

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

Система элементов чаще всего избыточна по своему составу,

что позволяет строить схемы с более простой топологией межэле-

ментных связей и более экономные по количеству используемых эле-

ментов.

Классификация логических элементов:

1) По способу представления информации и типу межэлементных

связей различают элементы импульсного, потенциального, импуль-

сно-потенциального и динамического типа.

Примечание: в современных ЭВМ применяются потенциальные и

динамические элементы.

2) По функциональному назначению элементы принято разделять

на  2типовые и элементы специального назначения 0. К  2типовым 0 относят-

ся логические, запоминающие и формирующие элементы. Логические

элементы предназначены для преобразования информации, запоминаю-

щие - для ее хранения, а формирующие элементы - для восстановле-

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

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

пям. К элементам 2 специального назначения 0 относятся усилители сла-

бых сигналов, генераторы токов и напряжений специальной формы и

другие элементы, не изменяющие информационного содержания сигна-

лов.

3) В зависимости от используемых физических явлений логичес-

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

водниковые, электромагнитные и др.

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

Общие технические характеристики:

- температурный диапазон,

- надежность,

- стоимость.

Специфические характеристики:

- функциональные возможности элемента,

- нагрузочная способность,

- быстродействие,

- 3 -

- помехоустойчивость,

- потребляемая мощность.

Функциональные возможности логического элемента характеризу-

ются выполняемой им операцией и коэффициентами разветвления и

объединения, т.е. факторами, влияющими на структуры более сложных

схем, построенных с применением данного элемента.

При этом под  2коэффициентом разветвления 0  2n 0 понимают число

входов последующих ячеек, которые могут управляться от выхода

данной ячейки, а под  2коэффициентом объединения 0  2m 0 - число входов,

которое может иметь ячейка. Величины m и n ограничиваются услови-

ями сохранения нормального электрического режима ячейки.

 2Нагрузочная способность 0 в общем случае определяется током,

который может быть отдан ячейкой во внешние цепи (нагрузку). В

случае однородных нагрузок, создаваемых входами идентичных ячеек,

нагрузочная способность оценивается коэффициентом разветвления n.

 2Быстродействие 0 логического элемента определяется скоростями

его перехода из состояния "0" в состояние "1" и обратно. Переход-

ные процессы изменения состояния элемента состоят из двух этапов:

задержки и формирования фронта или спада сигнала. Длительность

задержек и фронтов зависит от динамических свойств логического

элемента.

Однако для оценки быстродействия часто используют обобщенную

характеристику - 2 среднее время задержки 0. В этом случае моментом

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

сигналом некоторого определенного уровня (например, 0,5 от уста-

новившегося значения). Моментом появления сигнала на выходе также

считают момент достижения выходным сигналом этого уровня.

Так как длительности переходных процессов при включении и

выключении транзистора в общем случае не равны, то проводят обоб-

щение и говорят о среднем времени задержки сигнала на ячейку.

Время задержки при формировании спада

t 4сп

t 5' 4з 5  0= t 4з.сп  0+ 4  0--- ,

2

а время задержки при формировании фронта

t 4фр

t 5" 4з 5  0= t 4з.фр  0+ 4  0--- .

2

Среднее время задержки на один каскад схемы

t 5' 4з 0 + t 5" 4з

t 4з.ср 0 = --------- 5.

2

- 4 -

Одна из важнейших характеристик элемента - его  2помехоустой-

 2чивость 0. Различают статическую и динамическую помехоустойчивость.

При определении статической помехоустойчивости помеха рассматри-

вается как длительно действующий уровень потенциала, а при опре-

делении динамической помехоустойчивости - как импульс определен-

ной длительности. Устойчивость элемента к воздействию длительной

помехи меньше, чем к воздействию кратковременной помехи при оди-

наковых амплитудах. Устойчивость к воздействию динамической поме-

хи тем ниже, чем выше быстродействие элемента.

С увеличением степени интеграции элементов ЭВМ все большую

роль начинает играть такой параметр, как 2 рассеиваемая мощность 0.

Следует отметить, что закрытому состоянию соответствует один уро-

вень рассеивания мощности (P 4з 0), а открытому - другой (P 4о 0). Обычно

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

состоянии, а половину - в закрытом, и определяют среднюю рассеи-

ваемую мощность следующим образом:

P 4з 0 + P 4о

P 4ср 0 = ------- .

2

Рассеиваемая мощность может зависеть как от нагрузки, так и

от схем, включенных на входе.

 1Классификация логических элементов по типу радиокомпонентов,

 1на которых реализуются логические функции 2.

Можно выделить следующие наиболее часто употребляемые на

данный момент типы логических элементов:

- транзисторно-транзисторная логика с диодами Шотки (ТТЛШ);

- КМОП-логика (логика на базе комплементарных полевых тран-

зисторов со структурой металл-окисел-полупроводник);

- КМДП-логика (логика на базе комплементарных полевых тран-

зисторов со структурой металл-диэлектрик-полупроводник);

- интегральная инжекционная логика (ИИЛ, И 52 0Л, I 52 0L).

Следует отметить также некоторые типы элементов, которые в

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

низкого быстродействия или большой рассеиваемой мощности.

- резисторно-транзисторная логика (РТЛ, RTL);

- резисторно - конденсаторная транзисторная логика (РКТЛ,

RCTL);

- диодно-транзисторная логика (ДТЛ, DTL);

- транзисторно-транзисторная логика (ТТЛ, TTL);

- транзисторная логика с эмиттерными связями (ЭСЛ, TECL).

- транзисторная логика с непосредственными связями (DCTL).

- МОП-логика;

- МДП-логика (MDS).

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

ЛЕКЦИЯ N 9

 2ЭЛЕМЕНТЫ И УЗЛЫ ЭВМ

===================

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

Электронную схему, выполняющую какие либо операции над одним

машинным словом, называют  2узлом 0 ЭВМ. Многие узлы ЭВМ строятся на

базе логических элементов.

Общие требования к проектируемому устройству:

- устройство должно полностью соответствовать своему функци-

ональному назначению, т.е. выполнять заданные в ТЗ функции;

- быстродействие, энергопотребление, надежность, устойчи-

вость к вредному воздействию окружающей среды (температура, влаж-

ность, давление, вибрация, удары, статическое электричество,

внешние магнитные поля, электромагнитные помехи и пр.) должны со-

ответствовать заданным в ТЗ параметрам;

- устройство должно быть максимально простым, чтобы обеспе-

чить высокое быстродействие и надежность, а также низкую себесто-

имость.

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

наборов логических элементов, особенно в случае различной техно-

логии изготовления (ТТЛ и ТТЛШ, ТТЛ и КМОП, ТТЛ и ЭСЛ и т.п.),

необходимо тщательно проверить эти наборы на совместимость во

всем рабочем диапазоне температур и на отсутствие состязаний в

спроектированной схеме.

Требуется проверить:

- соответствие по номинальному напряжению питания;

- соответствие по входным и выходным характеристикам логи-

ческих элементов, особенно по уровням 0 и 1;

- соответствие элементов по быстродействию;

- соответствие по переходным процессам.

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

 2Амплитудная передаточная характеристика 0 U 4вых  0= 4  0f(U 4вх 0) опре-

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

тойчивость, амплитуду и уровни стандартного сигнала. Вид характе-

ристики зависит от типа логического элемента (ЭСЛ, ТТЛ и т.д.) и

 

Назад | Следующая страница
В начало реферата


 
     
 

2021 © Copyright, Abcreferats.ru
E-mail:

 

диваны, кухни, кресла похудение, спортивное питание Каталог офисной мебели