Билет 9

Оглавление

1. Логические элементы и схемы. Типовые логические устройства компьютера: полусумматор, сумматор, триггеры, регистры.

Ценность теории определяется тем, насколько она применима на практике. Создание компьютеров стало возможным только тогда, когда нашли общую точку пересечения, совместились, наложились друг на друга различные теоретические положения: 1833 г. — Чарльз Бэббидж выдвинул идею создания программируемой  вычислительной машины (Аналитическая машина). По его замыслу, она должна была стать «машиной самого универсального характера» — в действительности, ни чем иным, как первым универсальным программируемым компьютером. Аналитическая машина должна была иметь такие компоненты, как «мельница» и «склад» (по современной терминологии — арифметическое устройство и память). Управление перемещениями чисел со «склада» на «мельницу» и обратно, а также управление действиями «мельницы» осуществлялось перфокартами такого же типа, как ранее изобретенные для ткацкого станка Ж. М. Жаккардом. Последовательность карт составляла (как мы бы теперь назвали) программу. Согласно проекту, машина должна была приводиться в действие силой пара. Сотрудницей и помощницей Бэббиджа во многих его научных изысканиях была математик графиня Августа Ада Лавлейс (дочь великого английского поэта дж. Байрона). Она понимала важность аналитических методов и убедила Бэббиджа в необходимости использования в его изобретении двоичной системы счисления вместо десятичной. Она также разработала принципы программирования, что вписало ее имя в историю вычислительной техники как имя первой программистки. Аналитическая машина Бэббиджа не была построена, и программы, написанные Адой Лавлейс, никогда  не отлаживались и не работали, однако некоторые из высказанных ею общих положений (принцип экономии рабочих ячеек, связь рекуррентных формул с циклическими процессами вычислений и др.) сохранили свое принципиальное значение и для современного программирования, а ее определение цикла почти дословно совпадает с приводящимся в современных учебниках программирования.

1673 г. — Годфрид Вильгельм Лейбниц выдвинул идею применения в логике математической символики, предложил использовать двоичную систему счисления для целей вычислительной математики.

1848 г. — Джордж Буль заложил основы алгебры и логики (алгебры высказываний), поставив в соответствие истинному и ложному значениям числа 1 и 0.

1890 г. — Герман Холлерит создал счетно-аналитическую машину, в которой впервые для подсчетов результатов переписи населения США были использованы электричество и перфокарты.

1938 г. — Алан Мэтисон Тьюринг разработал теорию логических автоматов и доказал, что универсальная вычислительная машина теоретически возможна и ей по силам решение практически неограниченного числа различных задач.

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

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

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

Задача 1.

Пусть в некотором конкурсе решается вопрос о допуске того или иного участника к следующему туру тремя членами жюри: Р,Q, R?. Решение положительно тогда и только тогда, когда хотя бы двое членов жюри высказываются за допуск, причем среди них обязательно должен быть председатель жюри . Необходимо разработать устройство для голосования, в котором каждый член жюри нажимает на одну из двух кнопок — «За» или «Против», а результат голосования всех трех членов жюри определяется по тому, загорится (решение принято) или нет (решение не принято) сигнальная лампочка.

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

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

Простейшие преобразователи информации

Цифровой сигнал — это сигнал, который может принимать только одно из двух установленных значений.

Логический элемент НЕ (инвертор) выдает на выходе сигнал, противоположный сигналу на входе, т. е. на его выходе будет 1, если на вход поступит 0 и наоборот.

Логический элемент И, (конъюнктор) выдает на выходе значение логического произведения входных сигналов.

Логический элемент ИЛИ (дизъюнктор) выдает на выходе значение логической суммы входных сигналов.

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

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

Структурная формула логического устройства — это форма описания функции, реализуемой логическим устройством.

К типовым  логическим устройствам ЭВМ относятся сумматоры, полусумматоры, триггеры, счетчики, регистры, шифраторы, дешифраторы.

Сумматоры

Сумматор является основным узлом арифметико-логического устройства ЭВМ и служит для суммирования чисел посредством поразрядного сложения.

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

Одноразрядный сумматор должен иметь два выхода: для суммы и для переносимого значения. У него может быть два  или три входа.

Одноразрядный двоичный сумматор на два входа и два выхода называется одноразрядным полусумматором.

Одноразрядный двоичный сумматор на три входа и два выхода

называется одноразрядным сумматором на три входа.

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

В двоичной системе счисления операция сложения двух двоичных чисел в одном разряде осуществляется по правилу:

Из таблицы видно, что P(X,Y) = X&Y

Формулу для S можно получить двумя способами: либо по алгоритмам получения СДНФ или СКНФ, либо по сводной таблице логических функций двух переменных .

S(X,Y) = = =  &  = & (XY) =

= () & (X Y) = X & & Y

Предпоследняя формула — это СКНФ, последняя— СДHФ.

Для построения функциональной схемы мы воспользуемся структурной формулой () & (X Y) ,так как в ней наименьшее количество операций. Получим структурные формулы и функциональную схему одноразрядного полусумматора:

P(X,Y) = X&Y;   S = & (XY)

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

Из таблицы видно, что значения на выходах 4 и 5 соответствуют значениям переноса и суммы при сложении двоичных чисел (см. первую таблицу истинности).

Триггер

Триггеры являются основными элементами цифровой техники, их широко используют в качестве запоминающих ячеек автоматических и вычислительных устройств. Название «триггер» произошло от английского слова «trigger», означающего «защелка» или «спусковой крючок».

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

Триггер —устройство, которое может запоминать сигналы 0  и 1, демонстрировать их, а в случае необходимости и забывать.

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

Простейший триггер состоит из двух элементов «И—НЕ», входы и выходы которых соединены кольцом: выход первого соединен со входом второго и выход второго — со входом первого. При этом получается устройство с двумя устойчивыми состояниями.

Один вход - S «set» - установка, второй вход -  R «reset» - переустановка или сброс.