Учебное пособие по информатике 2014. Основы информатики
 Скачать 4.61 Mb.
|
|
Асинхронный RS-триггер. Он имеет два информационных входа — R и S. Вход S (set) используется для установки триггера в состояние «1», а вход R (reset) — в состояние «0», поэтому RS-триггер называют триггером с установочными входами. Работу триггера описывает таблица переходов (таблица 3.2а). Таблица 3.2 – Переходы RS-триггера (а) (б) Входами служат значения входных сигналов R и S, а также значения состояний триггера в текущий момент времени (Q t ). В таблице переходов приведены значения состояний триггера в следующий момент времени (Q t+1 ). Переходы триггера из одного состояния в другое происходят, если на вход R или S подается сигнал «1». При R = 0 и S = 0 состояние триггера не меняется. Такой режим называется режимом хранения. В случае если R = 0 и S = 1 триггер переходит в состояние «1» независимо от того, в каком состоянии он находился до изменения входных сигналов. При R = 1 и S = 0 триггер переходит в состояние «0». Таким образом, для записи «1» в RS-триггер необходимо подать на его входы сигналы R = 0 и S = 1, для записи «0» — сигналы R = 1 и S = 0. Комбинация сигналов R = 1 и S = 1 является запрещенной, состояние триггера при этом не определено. Таким образом, логика переходов RS-триггера аналогична логике работы электрического клавишного выключателя с двумя положениями: «Вкл» и «Выкл». Таблица переходов триггера может быть интерпретирована как таблица истинности комбинационной схемы, в которой значения сигналов на входах 75 R t , S t и значение текущего состояния Q t можно рассматривать как логические переменные, a Q t+1 как логическую функцию (таблица 3.2б). RS-триггер может быть построен на различных логических элементах. Функциональная схема асинхронного RS-триггера, построенного на элементах И-НЕ и ИЛИ-НЕ, а также его условное графическое обозначение (УГО) показаны на рисунке 3.8. Рисунок 3.8 – Асинхронный RS-триггер а – на элементах ИЛИ-НЕ, б – на элементах И-НЕ, в – УГО асинхронного RS- триггера с прямыми входами, г – УГО асинхронного RS-триггера с инверсными входами Условное графическое обозначение триггера кроме основного поля включает в себя дополнительное. В основном поле указывается назначение элемента (триггер), а в дополнительном — обозначение входов, т. е. тип триггера. Инверсный выход триггера отмечается кружком. Инверсными могут быть и входные сигналы. Так, при построении RS-триггера на элементах И—НЕ действующими (активными) являются инверсные значения входных сигналов R и S (сигналы «0»). Это означает, что для переключения триггера из одного состояния в другое нужно подать сигнал «0» на соответствующий вход триггера (R или S). Инверсные входы на схемах также отмечаются кружком. Заметим, что таблицы переходов триггеров обычно приводятся для прямых значений входных сигналов. Асинхронный RS- триггер представляет собой бистабильную ячейку, поэтому он используется как основа при построении практически всех триггеров. Синхронный RS-триггер. Этот триггер имеет дополнительно вход С, на который поступают синхросигналы(такты). Информационные сигналы R и S могут изменять состояние триггера только при значении синхросигнала С=1. Таблица переходов синхронного RS-триггера состоит из двух частей. 76 Первая часть таблицы описывает переходы триггера при С = 1 и совпадает с таблицей переходов асинхронного триггера (таблица 3.2а). Когда С = 0, триггер не меняет своего состояния при любой комбинации сигналов на информационных входах и логика его переходов может быть описана таблицей 3.3. Отметим, что при С = 0 разрешенными являются любые комбинации входных сигналов, в том числе R = 1, S = 1. Таблица 3.3 – Переходы синхронного RS-триггера На рисунке 3.9 приведены функциональные схемы синхронных RS- триггеров, реализованных на элементах И—НЕ и И—ИЛИ—НЕ, и их условное графическое обозначение. Кроме основных входов R и S там показаны дополнительные входы R 1 и S 1 которые являются асинхронными. При подаче сигналов на них состояние триггера может изменяться независимо от значения сигнала С. Следует отметить, что в каждый момент времени можно управлять переходами триггера только с помощью синхронных или асинхронных входов. Рисунок 3.9 – Синхронный RS-триггер а – на элементах И-НЕ, б – на элементах И-ИЛИ-НЕ, в – УГО 77 Асинхронный и синхронный D-триггеры. В вычислительной технике широко применяют D-триггеры, которые реализуют функцию временнóй задержки входного сигнала (D - англ. delay, задержка). Также D-триггеры имеют один информационный вход. Логика работы асинхронного D-триггера описывается таблицей переходов (таблица 3.4а). Таблица 3.4 – Переходы D-триггера (а – асинхронного, б – синхронного) (а) (б) В асинхронном D-триггере состояние (выходной сигнал) Q t+1 повторяет значение входного сигнала D t поэтому асинхронный D-триггер по существу не является элементом памяти и рассматривается только как основа для построения синхронного D-триггера. Функциональная схема и УГО синхронного D-триггера, построенного на основе синхронного RS-триггера, показаны на рисунке 3.10. Для преобразования RS-триггера в D-триггер сигнал D подается на вход S непосредственно, а на вход R — через инвертор. Если при С = 1 на вход D подать сигнал «1», то триггер перейдет в состояние «1», а при подаче сигнала D = 0 в триггер будет записан «0». Таким образом, для записи в D-триггер единицы на вход D нужно подать сигнал «1», а для записи нуля — сигнал «0» (так как триггер синхронный, на вход С необходимо в обоих случаях подавать сигнал «1»). Это делает D-триггер удобным для использования в схемах статической памяти, так как для записи достаточно иметь одну линию на разряд данных. При этом сигнал С является общим для всех разрядов записываемых данных. Рисунок 3.10 – Синхронный D-триггер (а – схема; б – УГО) 78 Логику работы синхронного D-триггера описывает таблица 3.4б. Эту логику можно охарактеризовать выражением «что надо записать в D-триггер, то и подается на его вход». Наличие входа синхронизации позволяет записывать новые данные в триггер только в определенные моменты времени (при С= 1). В промежутках между ними данные в триггере сохраняются без изменения. При чтении данных из триггера его состояние также не меняется. Т-триггер. Этот триггер имеет один информационный вход. Логику работы асинхронного Т-триггера характеризует таблица переходов (таблица 3.5а). Таблица 3.5 – Переходы Т-триггера (а – асинхронного, б – синхронного) (а) (б) При Т = 1 асинхронный Т-триггер меняет свое состояние на противоположное, а при Т = 0 состояние триггера не изменяется. (Аналогичную логику работы имеет кнопочный выключатель настольной лампы, который меняет состояние лампы при каждом нажатии кнопки.) Так как Т-триггер суммирует (или подсчитывает) по модулю два числа единиц, поступающих на его информационный вход, то Т-триггер называют также триггером со счетным входом. Логику работы синхронного Т-триггера описывает таблица 3.5б. Рисунок 3.11 – Асинхронный Т-триггер (а – схема; б – УГО) При С = 0 триггер не изменяет своего состояния, а при С = 1 работает как асинхронный Т-триггер. Функциональная схема Г-триггера может быть 79 построена на основе синхронного RS-триггера (однотактного или двухтактного). Схемы асинхронного и синхронного Т- триггеров показаны на рисунках 3.11 и 3.12 соответственно. Рисунок 3.12 – Синхронный Т-триггер (а – схема; б – УГО) Поскольку на этих схемах сигнал с выхода триггера поступает на его же вход, триггер должен во время переключения сохранять состояние и одновременно воспринять новую информацию. Для устойчивой работы в этом случае целесообразно использовать двухтактные триггеры. JK-триггер. Такие триггеры называют универсальными. Универсальность схемы JK-триггера состоит в том, что простой коммутацией входов и выходов можно получать схемы других типов триггеров. JK -триггер имеет два информационных входа. Вход J используется для установки триггера в состояние «1», а вход К — в состояние «0», т. е. входы J и К аналогичны входам S и R RS-триггера. Отличие JK-триггера от RS-триггера заключается в том, что на входы J и K могут одновременно поступать сигналы «1», в этом случае JK-триггер изменяет свое состояние. Таким образом, он работает так же, как RS-триггер, за исключением комбинации сигналов J=1; К=1, при которой он работает как T-триггер. При С = 1 переходы JK-триггера описывает таблица 3.6. Таблица 3.6 – Переходы JK-триггера Функциональная схема двухтактного JK-триггера и его УГО показаны на рис. 3.13. Этот триггер представляет собой комбинацию RS- и Т-триггеров, что согласуется с логикой его работы. Примеры построения других типов триггеров на основе JK-триггера представлены на рис. 3.14. Следует 80 отметить, что триггер любого типа можно преобразовать в любой другой триггер. Рисунок 3.13 – Двухтактный JK-триггер (а – схема; б – УГО) Рисунок 3.14 – Схемы преобразования JK-триггера (а – D-триггер, б – Т-триггер, в – RS-триггер) 3.2 Машина Тьюринга Переработка информации в системах управления и связи, решение различного рода задач на вычислительных машинах или вручную - все эти процессы целенаправленной переработки информации могут рассматриваться как некоторая упорядоченная последовательность операции. Предписание, определяющее содержание и последовательность операций, переводящих исходные данные в искомый результат, называется алгоритмом. Примерами простейших алгоритмов могут служить последовательности операций, позволяющие выполнять арифметические действия, решать алгебраические уравнения, вычислять площади фигур. Способ построения схемы логического автомата на основании заданной логической функции, которую он должен реализовать, можно также рассматривать как алгоритм синтеза схемы логического автомата. Как упоминалось ранее, переработка информации в управляющем устройстве для формирования сигналов управления также осуществляется при помощи определенного алгоритма - алгоритма управления. Любой алгоритм должен удовлетворять требованиям: определенности, массовости и результативности. Под определенностью алгоритма здесь подразумевается его точность и однозначность, не оставляющая места для произвола. Массовость алгоритма означает его применимость для целого класса задач (а не для одной задачи) при различных вариантах исходных 81 данных. Требованию результативности отвечает алгоритм, приводящий к получению искомого результата после выполнения конечного числа операций. Представим совокупность всех возможных исходных данных, перерабатываемых каким-либо алгоритмом А в виде последовательности 1 , 2 , … , i , … , а все возможные результаты - в виде последовательности 1 , 2 , … , j , … . Тогда любой алгоритм А k , преобразующий исходные данные i в результат j , можно свести к вычислению функции k , указывающей номер результата j по номеру совокупности исходных данных i j = k (i). Но индексы i и j являются целыми числами и всегда могут быть записаны в двоичной системе счисления при помощи конечного набора нулей и единиц. При этом функция k может рассматриваться как логическая функция, преобразующая ситуацию i на входе автомата в ситуацию j на его выходе. Следовательно, любой алгоритм в принципе может быть реализован при помощи соответствующего дискретного автомата. Английский математик Тьюринг предложил абстрактную схему автомата, принципиально пригодного для реализации любого алгоритма. Этот автомат, получивший название "Машина Тьюринга" является автоматом с бесконечной памятью. Запоминающим устройством в машине Тьюринга служит лента, разделенная на ячейки №l, №2, ... так, что эта лента имеет начало (ячейка №1), но не имеет конца (простирается в бесконечность как последовательность натуральных чисел). Рисунок 3.15 – Машина Тьюринга 82 В каждой из ячеек может быть записан нуль или единица. Над лентой перемещается головка Т, управляемая автоматом L, обладающим конечной памятью. Автомат L работает тактами. На его вход поступает информация о символе (0 или 1), считываемой головкой с ленты. Под влиянием команд, получаемых каждый такт от автомата L, головка может оставаться на месте или передвигаться на одну ячейку вправо или влево. Одновременно головка получает от автомата L команды, под влиянием которых она может заменить символ, записанный в ячейке, над которой она находится. Действие машины Тьюринга однозначно определяется исходным заполнением ячеек ленты и оператором преобразования управляющего автомата, который может быть задан таблицей переходов. Обозначим через S i (S 0 =0, S 1 =l) символ, считываемый головкой, через R J (R 0 – стоп, R 1 - влево, R 2 - вправо) - команду на перемещение головки и через q k (k=1,2, … , n) - состояние управляющего автомата. Тогда его таблица переходов может быть представлена таким образом (таблица 3.7). Как видно из таблицы 3.7, действие автомата зависит от входа S и его состояния q. Определенным значениям S i и q i соответствует определенная совокупность значений трех величин: S, R и q, обозначающих соответственно: какой символ S запишет головка на ленту, какова будет команда R на перемещение головки и в какое новое состояние q перейдет автомат L. Следует иметь в виду, что среди состояний q автомата L должно быть по крайней мере одно такое его состояние q * , при котором: головка не изменяет символа S, команда R=R 0 (стоп) и автомат остается в состоянии покоя q * . Придя в состояние q * , автомат заканчивает выполнение алгоритма, и дальнейшая работа машины Тьюринга прекращается. Таблица 3.7 – Таблица переходов Состояние Вход S 0 =0 S 1 =1 q 1 q 2 q 3 … S 0 , R 2 , q k S 1 , R 0 , q s S 1 , R 1 , q p … S 1 , R 1 , q m S 0 , R 1 , q l S 0 , R 2 , q s … Пусть, например, таблица перехода автомата L имеет следующий вид (таблица 3.8) Таблица 3.8 – Таблица переходов Q S 0 1 q * q 1 0, R 0 , q * 1, R 0 , q * 1, R 0 , q * 1, R 2 , q 1 83 Тогда, если в начальный момент автомат находится в состоянии q 1 , а головка расположена над ячейкой, в которой записан символ 1, то головка будет перемещаться вправо до тех пор, пока не обнаружит ячейку с символом 0, заменит его символом 1 и остановится. Если начальное состояние системы (состояние в нулевой такт) и заполнение ленты соответствуют требуемым, то, согласно таблице 3.8 система в последующие два такта перейдет в состояния, показанные в таблице 3.8, и на втором такте остановится. Приведенный пример показывает лишь одну из самых простых задач, решаемых машиной Тьюринга. При соответствующем расширении таблицы переходов можно заставить машину Тьюринга решать сколь угодно сложные задачи и, во всяком случае, любые задачи, которые способна решать какая- либо другая машина. Однако при этом следует иметь в виду, что практическое применение автоматов, построенных по схеме машины Тьюринга, нецелесообразно, ибо число шагов, необходимых для решения сколько-нибудь сложных задач, чрезвычайно велико, а значит, велико и время решения. Тем не менее, теория машин Тьюринга имеет большое значение для решения таких важных вопросов, как существование алгоритма решения того или иного класса задач, а значит, могут выполняться автоматически, в частности, таким универсальным автоматам как цифровая вычислительная машина. 3.3 Кодирование информации Коды как средство тайнописи появились в глубокой древности. Известно, что еще древнегреческий историк Геродот в V в. до н. э. приводил примеры писем, понятных лишь адресату. Секретная азбука использовалась Юлием Цезарем. Над созданием различных секретных шифров работали такие известные ученые средневековья, как Ф. Бэкон, Д. Кардане и др. Появлялись очень хитрые шифры и коды, которые, однако, с течением времени расшифровывались и переставали быть секретом. Первым кодом, предназначенным для передачи сообщений по каналам связи, был код С. Морзе, содержащий разное количество символов для кодирования букв и цифр. Затем появился код Ж. Бодо, используемый в телеграфии, в котором все буквы или цифры содержат одинаковое количество символов. В качестве символов может выступать наличие или отсутствие (пробел) импульса в электрической цепи в данный момент. Коды, использующие два различных элементарных сигнала, называются двоичными. Эти сигналы удобно обозначать символами 0 и 1. Тогда кодовое слово будет состоять из последовательностей нулей и единиц. Двоичное (бинарное) кодирование тесно связано с принципом дихотомии, который реализуется в графическом методе представления двоичной информации в виде графов. Ранее были рассмотрены общие и конкретные вопросы кодирования информации в цифровом автомате. Однако эти методы сами по себе еще не 84 обеспечивают правильность выполнения того или иного алгоритма. Различные алгоритмы выполнения арифметических операций обеспечат правильный результат только в случае, если машина работает без нарушений. При возникновении какого-либо нарушения нормального функционирования результат будет неверным, однако пользователь об этом не узнает, если не будут предусмотрены меры, сигнализирующие о появлении ошибки. Следовательно, с одной стороны, разработчиками машины должны быть предусмотрены меры для создания системы обнаружения возможной ошибки, а с другой стороны, должны быть проработаны меры, позволяющие исправить ошибки. Эти функции следует возложить на систему контроля работы цифрового автомата. Система контроля - совокупность методов и средств, обеспечивающих определение правильности работы автомата в целом или его отдельных узлов, а также автоматическое исправление ошибки. Ошибки в работе цифрового автомата могут быть вызваны либо выходом из строя какой-либо детали, либо отклонением от нормы параметров, например изменением напряжения питания или воздействием внешних помех. Вызванные этими нарушениями ошибки могут принять постоянный или случайный характер. Постоянные ошибки легче обнаружить и выявить. Случайные ошибки, обусловленные кратковременными изменениями параметров, наиболее опасны, и их труднее обнаружить. Поэтому система контроля должна строиться с таким расчетом, чтобы она позволяла обнаружить и по возможности исправить любые нарушения. При этом надо различать следующие виды ошибок результата: 1) возникающие из-за погрешностей в исходных данных; 2) обусловленные методическими погрешностями; 3) появляющиеся из-за возникновения неисправностей в работе машины. Первые два вида ошибок не являются объектом для работы системы контроля. Погрешности перевода или представления числовой информации в разрядной сетке автомата приведут к возникновению погрешности в результате решения задачи. Эту погрешность можно заранее рассчитать и, зная ее максимальную величину, правильно выбрать длину разрядной сетки машины. Методические погрешности также учитываются предварительно. Проверка правильности функционирования отдельных устройств машины и выявление неисправностей может осуществляться по двум направлениям: профилактический контроль, задача которого - предупреждение появления возможных ошибок в работе; оперативный контроль, задача которого - проверка правильности выполнения машиной всех операций. Решение всех задач контроля становится возможным только при наличии определенной избыточности информации. Избыточность может быть создана либо аппаратными (схемными) средствами, либо логическими или информационными средствами. 85 К методам логического контроля, например, можно отнести следующие приемы. В ЭВМ первого и второго поколения отсутствие системы оперативного контроля приводило к необходимости осуществления «двойного счета», когда каждая задача решалась дважды и в случае совпадения ответов принималось решение о правильности функционирования ЭВМ. Если в процессе решения какой-то задачи вычисляются тригонометрические функции, то для контроля можно использовать известные соотношения между этими функциями, например, sin 2 + cos 2 = 1. Если это соотношение выполняется с заданной точностью на каждом шаге вычислений, то можно с уверенностью считать, что ЭВМ работает правильно. Вычисление определенного интеграла с заданным шагом интегрирования можно контролировать сравнением полученных при этом результатов с теми результатами, которые соответствуют более крупному шагу. Такой «сокращенный» алгоритм даст, видимо, более грубые оценки и по существу требует дополнительных затрат машинного времени. Все рассмотренные примеры свидетельствуют о том, что такие методы контроля позволяют лишь зафиксировать факт появления ошибки, но не определяют место, где произошла эта ошибка. Для оперативного контроля работы ЭВМ определение места, где произошла ошибка, т. е. решение задачи поиска неисправности, является весьма существенным вопросом. |