Полная версия

Главная arrow Информатика arrow Архитектура ЭВМ и вычислительных систем

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Логические основы и элементы ЭВМ

Начало исследований в области формальной логики было положено работами Аристотеля в IV в. до нашей эры. Однако строго формализованный подход к проблеме впервые был предложен Дж. Булем. В честь него алгебру высказывания называют булевой (булевской) алгеброй, а логические значения — булевыми (булевскими). Основу математической логики составляет алгебра высказываний. Алгебра логики используется при построении основных узлов ЭВМ (дешифратор, сумматор, шифратор).

Алгебра логики оперирует с высказываниями. Под высказыванием понимают повествовательное предложение, относительно которого можно утверждать, истинно оно или ложно. Например, выражение «Расстояние от Москвы до Киева больше, чем от Москвы до Тулы» истинно, а выражение «5 < 2» — ложно.

Высказывания (логические переменные) принято обозначать буквами латинского алфавита (иногда — с индексами): А, В, С, ..., X, Y, а, Ь, с, ..., х, у, z, (*,, х2, ..., ...) и т. д.

Если высказывание С истинно, это обозначается как С= 1 (С= t, true), а если оно ложно, то С= О (С= f, false).

Логические операции и базовые элементы компьютера

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

Схемные элементы ЭВМ. Преобразование информации в ЭВМ осуществляется элементами (схемами) двух классов:

  • • комбинационными;
  • • последовательностными (схемами с памятью).

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

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

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

Логический элемент компьютера — это часть электронной схемы, которая реализует элементарную логическую функцию. Логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-НЕ» или другие (называемые также вентилями), а также триггер. Можно показать, что с помощью этих схем можно реализовать любую логическую функцию, описывающую работу устройств компьютера. Обычно у вентилей бывает от двух до восьми входов и один или два выхода.

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

Рассмотрим логические операции и соответствующие им элементы логических схем.

Конъюнкция. Соединение двух (или нескольких) высказываний в одно с помощью союза и (сж) называется операцией логического умножения, или конъюнкцией. Эту операцию принято обозначать знаками «л, &» или знаком умножения «х». Сложное высказывание А л В истинно только в том случае, когда истинны оба входящих в него высказывания. Истинность такого высказывания задается табл. 1.14.

Логическая схема «И» реализует конъюнкцию двух или более логических значений. Условное обозначение на структур-

Таблица 1.14. Таблицы истинности конъюнкции и логической суммы высказываний

Конъюнкция

Дизъюнкция

А

в

А а В

А

в

A v В

А хог В

0

0

0

0

0

0

0

0

1

0

0

1

1

1

1

0

0

1

0

1

1

1

1

1

1

1

1

0

ных диаграммах схемы «И» с двумя входами представлено на рис. 1.7, а.

Единица на выходе схемы «И» будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет нуль, на выходе также будет нуль.

Связь между выходом z этой схемы и входами х и у описывается соотношением z = x&y (читается как «х и у»). Операция конъюнкции на структурных схемах обозначается знаком «&».

Дизъюнкция. Объединение двух (или нескольких) высказываний с помощью союза или (or) называется операцией логического сложения, или дизъюнкцией. Эту операцию обозначают знаками « , v» или знаком сложения «+». Сложное высказывание А V В истинно, если истинно хотя бы одно из входящих в него высказываний (см. табл. 1.14).

В последнем столбце табл. 1.14 размещены результаты модифицированной операции ИЛИ — Исключающее или (XOR). Отличается от обычного или последней строкой (см. также рис. 1.7, е).

Схема «ИЛИ» реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы «ИЛИ» будет единица, на ее выходе также будет единица.

Условное обозначение на структурных схемах схемы «ИЛИ» с двумя входами представлено на рис. 1.7, б. Знак «1» на схеме происходит от классического обозначения дизъюнкции как «>» (т. е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами х и у описывается соотношением z = х v у (читается как «х или у»).

Инверсия. Присоединение частицы НЕ (not) к некоторому высказыванию называется операцией отрицания (инверсии) и обозначается А (или -Л). Если высказывание А истинно, то В ложно, и наоборот (табл. 1.15).

&

х

У

X • у

X V у

а

х2

х

У

  • *1
  • *2

/ = Х

/ = *

+ *2

г

в

X

У

X V у

д

У

/ = хх © х2

е

X

У

Таблица 1.15. Таблица истинности отрицания

Рис. 1.7. Схемные логические элементы вычислительных машин: а — «И»; б — «ИЛИ»; в — «НЕ»; г — «И-НЕ»; д — «ИЛИ-НЕ»; е — «Исключающее ИЛИ» (сложение по модулю 2)

Л

А

0

1

1

0

Схема «НЕ» (инвертор) реализует операцию отрицания. Связь между входом х этой схемы и выходом і можно записать соотношением і = х, где х читается как «НЕ х» или «Инверсия X».

Если на входе схемы «О», то на выходе «1», и наоборот. Условное обозначение на структурных схемах инвертора — на рис. 1.7, в.

Вентили. Кроме схемных элементов, соответствующих перечисленным логическим операторам, в состав логических схем входят комбинированные связки, именуемые вентилями, например, следующие.

Схема «И - НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И» (табл. 1.16). Связь между выходом і и входами х и у схемы записывают как х л у, или «Инверсия х и у». Условное обозначение на структурных схемах схемы «И-НЕ» с двумя входами приведено на рис. 1.7, г.

Таблица 1.16. Таблица истинности схем «И-НЕ», «ИЛИ-НЕ»

Инверсия х И у

Инверсия х ИЛИ у

X

У

X А у

X

У

х v у

0

0

1

0

0

1

0

1

1

0

1

0

1

0

1

1

0

0

1

1

0

1

1

0

Схема «ИЛИ-НЕ» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата схемы «ИЛИ» (табл. 1.16). Связь между выходом I и входами х и у схемы записывают как х V у, или «Инверсия х или у». Условное обозначение на структурных схемах схемы «ИЛИ-НЕ» с двумя входами представлено на рис. 1.7, д.

Схема «Исключающее ИЛИ» (рис. 1.7, е) соответствует «сложению по модулю два» (см. также табл. 1.14).

Следует отметить, что помимо операций и, или, не в алгебре высказываний существует ряд и других операций. Например, операция эквивалентности (эквиваленции) А ~ В (А= В, или А eqv В) (табл. 1.17).

Таблица 1.17. Таблицы истинности операций эквивалентности и импликации

Эквивалентность

Импликация

А

в

А~ В

А

в

А -> В

0

0

1

0

0

1

0

1

0

0

1

1

1

0

0

1

0

0

1

1

1

1

1

1

Другим примером может служить логическая операция импликации или логического следования (А —> В, A imp В), иначе говоря, «если А, то В» (табл. 1.17).

Высказывания, образованные с помощью логических операций, называются сложными. Истинность сложных высказываний можно установить, используя таблицы истинности. Например, истинность сложного высказывания А л В определяется табл. 1.18.

Таблица 1.18. Таблица истинности высказывания А лВ

А

в

А

в

А л В

0

0

1

1

1

0

1

1

0

0

1

0

0

1

0

1

1

0

0

0

Высказывания, у которых таблицы истинности совпадают, называются равносильными. Для обозначения равносильных высказываний используют знак «=» (А = В). Рассмотрим сложное высказывание л В) V л В) — табл. 1.19.

Таблица 1.19. Таблица истинности выражения л В) V А В)

А

А

в

в

А А В

А а В

(Л л б) V (Л л В)

0

1

0

1

0

1

1

0

1

1

0

0

0

0

1

0

0

1

0

0

0

1

0

1

0

1

0

1

Если сравнить эту таблицу с таблицей истинности операции эквивалентности высказываний А и /^см._табл. 1.17), то можно увидеть, что высказывания (А л В) V л В) и А ~ В тождественны, т. е. ~ В) = (А л В)у (А л В).

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

Свойства операций. Исходя из определений дизъюнкции, конъюнкции и отрицания, устанавливаются свойства этих операций и взаимные распределительные свойства. Приведем примеры некоторых из этих свойств:

• коммутативность (перестановочность):

Ал В = В л А,

А/ В = В V А;

• закон идемпотентности:

А лА = А, AvA = A;

• двойное отрицание:

А = А;

• сочетательные (ассоциативные) законы:

Av (В v С) = (A v В) v С = Av В v С,

А л (В л С) = л Z?) л С = А л 5 лС;

• распределительные (дистрибутивные) законы:

/4 л (5 v С) = (Аа B)v (А л С),

Av (В л C) = (Av В) л (A v С)-,

• поглощение:

Av (А л В) = А,

А л (Av В) = А

  • • склеива н_и е:
    • а В) v (А а В) = В,
    • (Av В) a (A v В) = В
  • • операция переменной с ее инверсией:

А а А = О,

A v А =1;

• операция с константами (0 — false, 1 — true):

A a l, Av l = 1,

Л л 0 = О, Л v 0 = Л;

• законы де Моргана:

А][В=А v В (условно его можно назвать 1-й);

A v В = А а В (2-й) — описывает результаты отрицания переменных, связанных операциями и, или.

Высказывания, образованные с помощью нескольких операций логического сложения, умножения и отрицания, называются сложными. Истинность всякого сложного высказывания устанавливается с помощью таблиц истинности. Сложные высказывания, истинные (true) для любых значений истинности входящих в них простых высказываний, называются тождественно-истинными. Наоборот, тождественно-ложными являются формулы, принимающие значение false для любых значений входящих в него простых высказываний.

В табл. 1.20 приведено доказательство истинности дистрибутивного закона. Аналогичным образом могут быть доказаны и другие тождества.

Таблица 1.20. Доказательство истинности дистрибутивного закона

А

в

с

Bv С

G

>

<

А л В

А л С

л В) V л С)

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

0

0

0

0

0

1

1

1

0

0

0

0

1

0

0

0

0

0

0

0

1

0

1

1

1

0

1

1

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

1

На рис. 1.8, а—е приведены иллюстрации к основным логическим операциям и их композициям (так называемые диаграммы Эйлера — Венна) — области истинности каждого из высказываний и их объединения (дизъюнкции), пересечения (конъюнкции) и других операций. «Первый» из законов де Моргана иллюстрируется рис. 1.8, д, е.

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

Таблица 1.21. Операнды и результаты некоторых побитовых операций

X

У

X & у

X V у

х IMP у

х EQV у

х XOR у

0

0

0

0

1

1

0

0

1

0

1

1

0

1

1

0

0

1

0

0

1

1

1

1

1

1

1

0

Логические операции.

NOT. Поразрядный оператор NOT (не), или дополнение, является одноместной операцией, которая выполняет логическое отрицание на каждом бите, формируя дополнение данного би-

Некоторые примеры диаграмм Эйлера — Венна

Рис. 1.8. Некоторые примеры диаграмм Эйлера — Венна: а — конъюнкция высказываний А и В (and); б — дизъюнкция высказываний А и В (or); в — исключающая дизъюнкция (XOR); г — разность высказываний (А — В); д — иллюстрация к законам де Моргана (дополнение пересечения высказываний); е — иллюстрация к законам де Моргана (объединение дополнений)

нарного значения. Биты, содержавшие бывшие «О», устанавливаются в «1», и наоборот. Например:

1000 = ШТ 0111

Во многих языках программирования (включая С), поразрядный оператор шт обозначается как «~» (тильда). Этот оператор не следует путать с «логическим отрицанием» («!» — восклицательный знак), который обрабатывает все значение как отдельное булевское.

О Я. Побитовый оператор сж (или, «включающее или») обрабатывает две битовые строки равной длины и создает третью (той же длины), где каждый бит является результатом операции «включающее или» над каждой парой входных битов. Например:

0111 = 0101 ОР. ООН

В ЯП С поразрядный оператор сж обозначается символом «|» (вертикальная черта). Его булевский аналог обозначается как «||».

ХОЯ («исключающее или») выполняет логическую операцию хсж на каждой паре соответствующих битов двух строк одинаковой длины. Например:

ОНО = 0101 ХСЖ ООН

В ЯП С поразрядный оператор хсж обозначается как «л» («крышка»).

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

AND. Поразрядный and (и) выполняет логическую операцию and на каждой паре соответствующих битов двух битовых строк. Например:

0001 = 0101 AND ООН

В ЯП С поразрядный оператор and обозначается как «&» (амперсанд). Булевский аналог записывается как «&&» (два амперсанда).

Битовые сдвиги (bit shifts). Эти операции также осуществляются на битовом уровне и являются унарными. В этих операциях биты сдвигаются в регистре (влево или вправо). Поскольку регистры компьютера имеют ограниченный размер, некоторые биты будут «выдвинуты из регистра» с одной из его сторон, и аналогичное число бит должно быть «вдвинуто в регистр» с другой. Основное различие в операциях битовых сдвигов заключается в том, как именно они обрабатывают эти «вдвиги/вы-двиги».

Арифметический сдвиг. При арифметическом сдвиге аннулируются биты, которые сдвинуты из любого конца регистра. Однако при арифметическом сдвиге влево с правой стороны вдвигаются нули, а при сдвиге вправо знаковый разряд остается в крайнем правом разряде, сохраняя знак операнда (рис. 1.9, а, б). Арифметический сдвиг влево на п разрядов эквивалентен умножению на 2" (если не происходит переполнения), в то время как арифметический сдвиг вправо на п эквивалентен делению на 2".

Логический сдвиг. При логическом сдвиге аннулируются биты, которые сдвинуты, и их место занимают нули (в любом конце регистра) — рис. 1.9, в, г. Поэтому, логический и арифметический сдвиги влево оказываются тождественными. Однако логический сдвиг вправо вставляет биты со значением «0» вместо копии знакового разряда. Следовательно, логический сдвиг является более подходящим для двоичных чисел без знака, в то время как арифметический сдвиг — для двоичных со знаком.

Циклический сдвиг или разрядное вращение. В этой операции биты, «выдвигаемые» из регистра в любую сторону,

7

6

5

4

3

2

1

0

1

0

0

1

0

1

0

1

  • 7 6 5 4 3 2 1 0 1 | 01011 | 011 11 | 1
  • 7 6 5 4 3 2 1 0

о I о I о 111011 111 1

1

0

0

0

1

0

1

1

01 о| 1

1111о Чо]

а

б

7

6

5

4

3

2

1

0

7 6

5

4

3 2 10

0

0

0

1

0

1

1

1

0 0

0

1

0 111

0-^ 0 0 0 0 1 0 1

)0010111 00010111 1п1п1п1н1а1н1н1 м г

шг шш ИЖ

т

  • 7 6 5 4 3 2 1 0 О | 01011 1011 111 1
  • 7777777

в

76543210 П 76543210

ф

1

0

0

0

1

0

1

1

о

о

1

0

1

1

1

0

о|оН|о|1|1|1|о 1-И~о1

г

  • 3
  • 110|0|0|1|0|111| |Т| |0|0|1|0|1|1|1|1| [о

ж

Рис. 1.9. Битовые сдвиги:

а — арифметический сдвиг вправо; б — арифметический сдвиг влево; в — логический сдвиг вправо; г — логический сдвиг влево; д — правый циклический сдвиг (вращение); е — левый циклический сдвиг; ж — правый циклический сдвиг через перенос; з — левый циклический сдвиг через перенос

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

Циклический сдвиг «через перенос». В отличие от обычного сдвига (или сдвига «не через перенос») здесь считается, что два конца регистра отделены флажком переноса («п» на рис. 1.9, ж, а). Бит, который «вдвинут» (с любой стороны регистра), — старое значение флажка переноса, а бит, который «выдвинут» (с противоположной стороны) становится новым значением флажка переноса.

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

Битовые манипуляции. Кроме перечисленных команд, существует большая группа операций, в том или ином виде реализованная в различных процессорах и объединяемая под общим названием «битовые манипуляции/жонглирование» (bit manipulation, bit twiddling, bit bashing). Эти операции связаны с задачами обнаружения и коррекции ошибок, алгоритмами шифрации данных и оптимизации, обработки мультимедийных данных, биоинформатики и пр. Например, в ЦП Motorolla 68000 это команды bset (установка битов в «1»), bclr (установка битов в «0») и BTST (переустановка нулевых битов); в систем команд SSE4 это popcnt («Population Count» — подсчет количества битов, например, установленных в «1») и т. д.

Команды группы ABM (Advanced Bit Manipulation Instruction Set Architecture) поддерживают операции над частями слов (подсловами, subwords) размером в 8, 16, 32 или 64 бита (в дальнейшем — битгруппы, БГ). Обзор некоторых команд этого типа приведен в табл. 1.22, 1.23. Здесь обычно Рх входной регистр, Р2 выходной, Ръ управляющий (ключевой, конфигурационный). Различаются следующие классы команд: перестановка бит и/или БГ, сжатие и расширение БГ, а также сравнение бит и/или Б Г.

Таблица 1.22. Обзор команд группы АВМ (перестановки)

Команда

Обозначение

Описание

Длительность в циклах АЛУ

Butterfly

Inverse Butterfly Перестановки

bfly ibf ly

Команды ъ± 1у (перестановка «бабочка») и л.ьгд.у (перестановка «обратная бабочка») осуществляют перестановку битов Рь Исполнительные цепи спроектированы таким образом (сеть Бенеша, см. рис. 1.10, а, б), что единственное исполнение обеих инструкций позволяет получить все л! перестановок п бит

1

Group

Группирование

grp

БГ (например, байт) А переупорядочивается в выходном регистре /?1 в соответствии с указателем, находящимся в Р13. Например, биты Рь которым соответствуют «1»в Я3, перемещаются влево, а те, которым соответствуют «0», — вправо (рис. 1.10, в)

3

Mix

Перемешивание

mix

БГ входных регистров А и А3 разбиваются на пары и поочередно выбираются для помещения в Р2. Порядок выборки определяется модификацией команды (пих.г или тп1х. 1, рис. 1.10, г)

1

Окончание табл. 1.22

Команда

Обозначение

Описание

Длительность в циклах АЛУ

Check,

Excheck

check

excheck

Команды check и excheck выполняют перестановку БГ (длиной в 1,2 или 4 бита) в Р, и Р13. БГ в каждом регистре разбиваются на пары и выбираются в Р2, причем check выбирает левый элемент каждой пары из Pi (рис. 1.10, д) и правый из excheck — в обратном порядке (рис. 1.10, е)

і

Mux

mux

Выполняет 5 перестановок БГ: обратная перестановка бит (рис. 1.10, ж), перестановка частей регистра (рис. 1.10, з), заполнение всех байтов Р2 одинаковым КОДОМ ИЗ Р! и т. д.

і

а

ь

С

d

е

f

g

h pl

а

ь

С

d

е

f

g

h

і

0

і

0

1

1

0

1 'з +

-Уч 1

і

0

і

0

і

і

0

1

0

0

0

а

с

С

f

h Р2

а

0

е

0

f

g

0

h

и к

Рис. 1.10. Битовые манипуляции (АВМ): а — восьмиразрядная перестановка butterfly; б inverse butterfly; в — восьмиразрядная операция grp; г — операция mix.2.1 (64-битовые слова); д — операция check.2; е — excheck. 2; ж — операция mux. 1. rev operation; з — mux. 1 .mix; и — 8-разрядная операция рех; к — pdep

Таблица 1.23. Обзор команд группы АВМ (сжатие-расширение строк)

Команда

Модифи

кация

Обозначение

Описание

Длительность в циклах АЛУ

Parallel Extract Параллельное сжатие

Static

Variable

рех

рех. V

Биты/БГ Рь помеченные «1» в Р13, извлекаются и помещаются в правую часть Р12. Оставшиеся биты слева заполняются нулями (рис. 1.10, и)

1—3

Parallel Deposit

Параллельное

расширение

Static

Variable

pdep pdep.v

Распределяет выровненную вправо (в Рт) последовательность БГ по позициям (в Р12), помеченным «1» в Р3.

Оставшиеся позиции в Р2 заполняются нулями (рис. 1.10, к)

1—3

Population Count Подсчет «населения»

popcount

Подсчет числа битов Рь установленных в «1»

1

Dot Product Скалярное произведение

dotprod

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

1

Bit Matrix Multiply Перемножение битовых матриц

п хП

bmm.IrR

Умножение битовой матрицы размерности л х л на л-мерный битовый вектор. Операция эквивалентна л операциям бо1ргоб

1 (л - 64)

кхп

bmm.2rR

Умножение 2л-битовой матрицы на /гл-битовую матрицу

1

1 х П

bmm.2 r

Перемножение двух я-битовых матриц

1

Впервые функциональный (исполнительный) блок АВМ появляется в процессорах архитектуры К10 (AMD) — см. рис. 3.35.

Синтез и оптимизация схем

При построении схемы, реализующей произвольную таблицу истинности, каждый выход анализируется (и строится схема) отдельно. Для реализации таблицы истинности с помощью логических элементов «И» достаточно рассмотреть только те строки таблицы истинности, которые содержат логические «1» в выходном сигнале. Строки, содержащие в выходном сигнале логический «О», в построении схемы не участвуют. Каждая строка, содержащая в выходном сигнале логическую «1», реализуется схемой логического «И» с количеством входов, совпадающим с количеством входных сигналов в таблице истинности. Входные сигналы, описанные в таблице истинности логической «1», подаются на вход этой схемы непосредственно, а входные сигналы, описанные в таблице истинности логическим «О», подаются на вход через инверторы. Объединение сигналов с выходов схем, реализующих отдельные строки таблицы истинности, производится с помощью схемы логического «ИЛИ». Количество входов в этой схеме определяется количеством строк в таблице истинности, в которых в выходном сигнале присутствует логическая «1».

Рассмотрим конкретный пример. Пусть необходимо реализовать таблицу истинности, приведенную в табл. 1.24.

Таблица 1.24. Таблица истинности некоторой логической функции

Входы

Выходы

*1

х2

*3

х4

У1

У2

0

0

0

0

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

0

1

0

1

0

1

0

1

1

0

1

0

0

1

1

1

0

0

1

0

0

0

0

0

1

0

0

1

0

1

1

0

1

0

0

0

1

0

1

1

0

0

1

1

0

0

1

0

1

1

0

1

0

0

1

1

1

0

0

0

1

1

1

1

0

1

Для построения схемы, реализующей сигнал у,, достаточно рассмотреть строки, выделенные светлой штриховкой. Эти строки реализуются сборкой (микросхемой) 52 на рис. 1.11. Каждая строка реализуется своей схемой «И», затем выходы этих схем объединяются. Для построения схемы, реализующей сигнал у2, достаточно рассмотреть строки, выделенные более темной штриховкой. Эти строки реализуются сборкой З'з. Инвертирование входов схемы осуществляется сборкой 5,.

^1 У2

52

1

1

&

&

&

&

& &

_4

1

)— “V

)— -V

  • —^—
  • 1

Рис. 1.11. Схемная реализация таблицы истинности (табл. 1.24)

В частности, в данном случае

У = (*1 Л х2 А Х3 Л х4 ) V (х, А х2 Л хз Л х4 ) V V (Х, А х2 А Х3 А х4) и т. д.

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

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

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

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

1) хуул(іл}') = хл}'л(іл)') = хлхл}'ліу =

=0лулу=0

  • (законы алгебры логики применяются в следующей последовательности: закон де Моргана, сочетательный закон, правило конъюнкции переменной с ее инверсией и правило операций с константами);
  • 2) xлyv XV yvX=XAyvXAyvX =

= х А (у V у) V X =Х V X = 1

  • (применяется закон де Моргана, выносится за скобки общий множитель, используется правило операций переменной с ее инверсией);
  • 3)

= хл їухл/л^хлгл^у |) = ^хлі'ухлз'л^хлул^хлул^

= (хлуухлулг)у(хлул^ухлул^)=хл^улг

  • (вводится вспомогательный логический сомножитель (у V у), комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);
  • 4) XV yAZVXvyvZ=XvyvZVXAyAZ =

= х V у V ?vxлyл?=xv ^(і'ухлІ'л^^ху Z V у

  • (к отрицаниям неэлементарных формул применяется закон де Моргана, используются двойное отрицание и склеивание);
  • 5)

= xл(y/yлzvyлzvyлz) =

= X А ((у V у А z) V А Z V У А z)) =

= xл(yvyлzv 1) = л: л 1 = х

(общий множитель х выносится за скобки, комбинируются слагаемые в скобках — первое с третьим и второе с четвертым, к дизъюнкции у л z V применяется правило операции пере

менной с ее инверсией);

6) (х Л у V г) А (х V у) V ^ =

= хлулхухлулуу?лху?луу ? =

= 0 V 0 V Z А у V z=ZAXv(zv г) Л V 1) =

= ^ Л X V 1л (у V 1) = 1АХ/у/ ? = (? Л X V г) V у =

= (z V I) Л (XV V у = 1 л (х V V у = х V ? V у

  • (используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);
  • 7) х Л1УЛ(ХЛ^ХЛ}'Л^ ? л /) =

= хлул(хл^ X Л у V ^ Z А 0 =

= хлу л (xлzv X Л у V ^ Z А 0 =

=xлyvxлyл?vxлyл?л/=xлy

(используются закон де Моргана, двойное отрицание и поглощение).

Минимизация логического выражения. Целью минимизации логического выражения, представляющего заданную логическую функцию, является уменьшение стоимости ее реализации (количества используемых логических элементов). Общая схема процесса реализации логической функции такова. Для нее составляется сумма произведений, или дизъюнктивная совершенная нормальная форма. Затем полученное выражение минимизируют до эквивалентной минимальной суммы произведений. Чтобы определить критерий минимизации, вводится понятие стоимости, или величины, логического выражения.

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

Минимизация логических схем

Рис. 1.12. Минимизация логических схем

Стоимость большей схемы (рис. 1.12, а) равна 21:

5 вентилей плюс 16 входных значений.

Инверсия входных значений при подсчете игнорируется. Стоимость более простого выражения (рис. 1.12, б) равна 9:

3 вентиля плюс 6 входных значений.

Теперь можно определить критерий минимизации: сумма произведений считается минимальной, если не существует эквивалентного ей выражения меньшей стоимости.

Стратегия упрощения заданного выражения заключается в следующем. Прежде всего термы-произведения разбиваются на пары, различающиеся единой переменной, которая в одном терме стоит со знаком -> (х), а во втором — без него (х). Затем в каждой паре общее произведение двух переменных выносится за скобки, а в скобках остается терм -х + х, всегда равный 1. Вот что мы получим, применив эту процедуру к первому выражению для функции ./] (на рис. 1.12, а),

/, = (х, А х2 А х3) V (л?! А х2 А х3) V (х, А х2 А Х3) V (х, А Х2 А Х3) =

= X, л х2 л (х3 V х3) V (х, л х,) л х2 л х3 =

— Х| А Х2 л 1 V 1 А Х2 А X 3

= Х[ А х2 V х2 л х3.

Это выражение минимально. Соответствующая ему логическая схема приведена на рис 1.12, б.

Другие схемные элементы ЭВМ

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

Для обозначения этой схемы в английском языке часто употребляется термин flip-flop, что в переводе означает «хлопанье». Это звукоподражательное название электронной схемы указывает на ее способность мгновенно переходить («перебрасываться») из одного состояния в другое и обратно.

Самый распространенный тип триггера — так называемый /?5-триггер (5 и R, соответственно, от англ, set — установка и reset — сброс). Он имеет два симметричных входа S и R и два симметричных выхода 0 и 0, причем выходной сигнал 0 является логическим отрицанием сигнала 0. Условное обозначение /?5-триггера приводится на рис. 1.13, а.

ЛУ-триггер (а), его реализация (б)

Рис. 1.13. ЛУ-триггер (а), его реализация (б)

На каждый из двух входов 5и /? могут подаваться входные сигналы в виде кратковременных импульсов (рис. 1.13, а). На рис. 1.13, 6 показана реализация триггера на базе вентилей «ИЛИ-НЕ» и «И-НЕ».

Перечислим возможные комбинации значений входов и ? триггера, используя его схему и таблицу истинности схемы «ИЛИ-НЕ» (табл. 1.25).

1. Если на входы триггера подать 5= 1, /? = 0, то (независимо от состояния) на выходе 0 верхнего вентиля появится «О». После этого на входах нижнего вентиля окажется Я = 0, 0=0 и выход 0 станет равным «1».

Таблица 1.25. Таблица истинности для ЯЗ1-триггера

5

к

0

0

0

0

Без изменений

0

1

1

0

1

0

0

1

1

1

Не определено

  • 2. При подаче «О» на вход 5 и «1» на вход Я на выходе 0 появится «О», а на 0 «1».
  • 3. Если на входы Я и 5 одновременно подан логический «О», то состояние 0 И 0 не меняется.
  • 4. Состояние триггера при Я = 1 и 5= I считается неопределенным, так как после снятия таких сигналов триггер не переходит однозначно в нужное состояние. Поэтому на состояние входов налагается условие Лл5=0.

Поскольку триггер может запомнить только один разряд двоичного кода, для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8х2|0 = 8192 триггера. Современные микросхемы памяти содержат миллионы триггеров.

Кроме /?5-триггеров известны также ЛС-, Т- и /)-триггеры. УА'-триггер содержит схемные дополнения, которые снимают неопределенность состояния при подаче «1» на оба входа.

Г-триггер имеет единственный вход (Т), при подаче «1» на который осуществляется «переброс» схемы. Г-триггеры могут использоваться для создания двоичных счетчиков (например, счетчик адреса команд, обеспечивающий последовательную выборку слов из оперативной памяти).

/)-триггер имеет информационный вход й и вход синхронизации С. Состояние на выходе /)-триггера отражает информацию, поступившую на его информационный вход в течение воздействия синхросигнала.

Рассмотрим далее одноразрядные сумматоры.

Сумматор по модулю 2 является простейшим среди них и реализует операцию Ахог В (исключающее или, см. табл. 1.14). Обозначение на схемах и реализация сумматора по модулю 2 приводятся на рис. 1.14.

А

В

А 0 В

А В 5, А В

б

Рис. 1.14. Сумматор по модулю 2: а — обозначение на схемах; б — реализация

а

Полусумматор. Вспомним, что при сложении двоичных чисел образуется сумма в данном разряде и при этом возможен перенос в старший разряд. Обозначим слагаемые (А, В), перенос (Р), сумму (?) и рассмотрим соответствующую данной операции табл. 1.26.

Таблица 1.26. Таблица сложения одноразрядных двоичных чисел с учетом переноса в старший разряд (полусумматор)

Слагаемые

Перенос

Сумма

Л

в

Р

5

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

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

Р = А а В.

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

Нужный результат достигается, если результат логического сложения умножить на инвертированный перенос. Таким образом, для определения суммы можно применить выражение (см. сложение по модулю 2):

5 = Л V В а А а В.

На основе полученных логических выражений можно построить схему полусумматора из базовых логических элементов.

Из логической формулы для суммы следует, что на выходе должен стоять элемент логического умножения «И», который имеет два входа. На один из входов подается результат логического сложения исходных величин, т. е. на него должен подаваться сигнал с элемента логического сложения « ИЛИ».

На второй вход требуется подать результат инвертированного логического умножения исходных сигналов А л В, т. е. на второй вход подается сигнал с элемента «НЕ», на вход которого поступает сигнал с элемента логического умножения «И».

Данная схема называется полусумматором, так как реализует суммирование одноразрядных двоичных чисел без учета переноса из младшего разряда (рис. 1.15).

А в s{ А В

а б

Рис. 1.15. Полусумматор: а — обозначение на схемах; б — реализация

Полный одноразрядный сумматор. Полный одноразрядный сумматор должен иметь три входа; Ь( слагаемые и — перенос из предыдущего разряда и два выхода: сумма -51,- и перенос рг Порядок функционирования схемы приводится в табл. 1.27.

Последовательность построения полного сумматора такая же, как и полусумматора. Перенос реализуется с помощью следующей формулы:

Р, =(я, л bi)v (я,, д />,_,) V (6, л

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

= (а,. V Ь, V ) л /г_, V (я,, л Ь, л р1_1).

Таблица 1.27. Таблица сложения для полного одноразрядного сумматора

Слагаемые

Входящий перенос

Выходящий перенос

Сумма

Ь,

Л-1

Л

?У/

0

0

0

0

0

0

0

1

0

1

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

1

0

1

1

1

1

0

1

1

1

1

1

В соответствии с принципами построения схемы по произвольной таблице истинности (см. табл. 1.24, рис. 1.11) можно построить схему полного двоичного одноразрядного сумматора (рис. 1.16, б).

Одноразрядный сумматор

Рис. 1.16. Одноразрядный сумматор: а — обозначение на схемах; б — реализация на логических сборках

 
<<   СОДЕРЖАНИЕ   >>