Задачи для самостоятельного решения.

 

1. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке не лимонад и не вода, стакан стоит между банкой и сосудом с молоком. В каком сосуде находится каждая из жидкостей?

2. В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположение о возможных победителях:

1) Сима будет первой, Валя – второй;

2) Сима будет второй, Даша – третьей;

3) Алла будет второй, Даша – четвертой;

По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое – ложно.

Какое место на соревнованиях заняла каждая из девушек, если все они оказались на разных местах?

 

6.8 Понятия о комбинационных схемах и цифровых автоматах

 

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

Функционально взаимосвязанные группы таких элементов образуют различные узлы ЭВМ, которые оперируют с многоразрядными двоичными кодами, например машинными словами или их частями. К числу типовых узлов ЭВМ относятся:

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

- счетчики, предназначенные для подсчёта числа входных двоичных сигналов;

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

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

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

Несмотря на огромное количество элементов, находящихся в составе ЭВМ, число их разновидностей (типов) относительно невелико. Это существенно упрощает процесс проектирования ЭВМ и повышает технологичность её изготовления. Типовой набор образует систему элементов ЭВМ, которая обладает общими электрическими, конструктивными и технологическими свойствами, использует однотипные связи между элементами, совместимые по своим входным и выходным параметрам.

Устройство ЭВМ, преобразующее двоичную информацию, в общем случае представляется многополюсником с n входами и m выходами. На его входы поступают входные двоичные сигналы xi (i = 1, 2, …, n), а с выхода снимаются выходные сигналы yj (j = 1, 2, …, m).

В любой момент времени наборы этих сигналов образуют соответственно входное слово X (х1, х2, …, хn) и выходное слово Y (у1, у2, …, уm).

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

 

 

В комбинационной схеме (КС) набор выходных сигналов (выходное слово Y) в любой момент времени полностью определяется набором входных сигналов (входным словом X), поступающих в тот же момент (рис. 6. 1). Таким образом, в КС результат обработки информации зависит только от комбинации входных сигналов и вырабатывается одновременно с их поступлением.

Закон функционирования комбинационной схемы полностью определен, если задано соответствием между её входными и выходными словами, например, в виде таблицы. По этой таблице можно получить аналитическую форму зависимости выходных и входных слов КС с использованием соответствующих логических функций (например, в ДСНФ или КСНФ).

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

 

 

Цифровые автоматы

Термин автомат как правило используется в двух аспектах. С одной стороны, автомат – устройство, выполняющее некоторые функции без непосредственного участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом аспекте автомат представляется как «чёрный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний, в которые он под воздействием входных сигналов переходит скачкообразно, практически мгновенно, минуя промежуточное состояние.

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

В цифровых автоматах набор выходных сигналов Y (y1, y2, …, ym) зависит не только от набора входных сигналов X (x1, x2, …, xn), но и от внутреннего состояния Q (q1, q2, …, qk) данного устройства (рис. 6.2).

Цифровые автоматы имеют память, фиксирующую состояние автомата. Наборы переменных X, Y и Q называются соответственно входным, выходным и внутренним алфавитами. Обычно значения этих алфавитов разделяют по временным интервалам t = 0, 1, 2, …, называемым тактами. В течение такта состояние всех трёх алфавитов сохраняются неизменными.

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

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

- конечное множество входных сигналов Х;

- конечное множество выходных сигналов Y;

- произвольное множество Q состояний автомата;

- начальное состояние автомата q₀, как элемент множества Q;

- функция перехода автомата из одного состояния в другое;

- функция выходов автомата.

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

 

Qt+1 = φ(Qt, Xt);

Yt = ψ (Qt, Xt),

 

которые определяют зависимости соответственно состояние автомата Qt+1 и выходного слова Yt от состояния автомата Qt и входного слова Xt. При этом должно быть указано начальное состояние автомата q₀.

В теории автоматов наиболее полно описаны синхронные автоматы.

В зависимости от способа определения выходного сигнала в синхронных автоматах существуют две возможности:

- выходной сигнал однозначно определяется входным сигналом и внутренним состоянием автомата в предшествующий момент (автоматы Мили);

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

Автомат, для которого выходное слово Yt в такте t зависит только от состояния автомата Qt в этом такте и не зависит от входного слова Xt, называет автоматом Мура. Для него функция выходов имеет вид Yt = ψ (Qt).

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

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

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

Дадим общую характеристику логическим и запоминающим элементам ЭВМ.

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

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

Таблица 6.7. Графические изображения комбинационных схем

Наименование элемента	Условное обозначение	Название и логическая запись функции
И		Конъюнкция: y=x1&x2 y=x1x2
ИЛИ		Дизъюнкция: y=x1Vx2 y=x1+x2
НЕ		Инверсия: y=x y = ¬x
ИЛИ-НЕ		Стрелка Пирса: ______ y=x1Vx2 y=x1↑x2
И-НЕ		Штрих Шеффера: ____ y=x1x2 y=x1/x2

 

 

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

Запоминающие элементы выполняют функцию памяти для двоичных переменных 0 и 1, для чего они должны иметь два устойчивых состояния равновесия, одно из которых принимается за «0», а другое за «1». Каждому из этих состояний соответствуют различные выходные сигналы. В запоминающих элементах с помощью входных сигналов устанавливается необходимое состояние, которое сохраняется неизменным после прекращения действия этих сигналов. Указанным требованиям отвечают так называемые триггеры, реализуемые в виде полупроводниковых микросхем различной степени интеграции. Существует несколько различных типов триггеров. Большинство из них применяется для построения узлов ЭВМ, например регистров, счетчиков, некоторых сумматоров и др. Триггеры, выполненные на больших интегральных схемах (БИС), используются также в полупроводниковых запоминающих устройствах (БИС ЗУ). Обычно в каждом корпусе БИС ЗУ размещается несколько тысяч запоминающих элементов.

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

С развитием вычислительной техники постоянно улучшаются и совершенствуются параметры и характеристики элементов ЭВМ.

В качестве примера рассмотрим описание работы узла ЭВМ, называемого сумматором.

Определение:

Узел ЭВМ, выполняющий арифметическое суммирование кодов чисел, называется сумматором.

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

Иногда такое суммирование разбивают на две аналогичные операции: суммирование двух цифр слагаемых и суммирование полученного результата
с переносом из соседнего младшего разряда. Каждая из этих операций выполняется схемой, называемой полусумматором. В табл. 6.7. приведена логика работы сумматора на два входа: х_i и y_i. На его выходах образуется сумма S_i данного разряда и осуществляется перенос Р_i+1 в следующий старший разряд. По таблице можно составить логические выражения
для суммы S_i и переноса Р_i+1:

Преобразуем выражение для суммы S_i к виду

 

 

а) xi yi

На рисунке 6.3. a,b приведены функциональная схема полусумматора, составленная в соответствии с полученными логическими выражениями, и его условное графическое обозначение.

Таблица 6.7. Описание работы сумматора на два входа

Xi	yi	Si	Pi+1

 

Опишем коротко назначение оставшихся функциональных узлов.