Основные электронные элементы компьютеров и систем и принципы логического проектирования электронных элементов

6 1 ВВЕДЕНИЕ. ЛЕКЦИЯ 1 План лекции: а) предмет и задачи дисциплины; б) классификация компьютеров; в) показатели производительности и эффективности компьютеров. 1.1 Предмет и задачи дисциплины В дисциплине рассматриваются: а) основные электронные элементы компьютеров и систем и принципы логического проектирования электронных элементов; б) функциональные и конструктивные узлы компьютеров и систем: процессоры, память, компоненты ввода-вывода информации, материнские и дочерние платы и пр.; в) системы (многомашинные и многопроцессорные) обработки данных. Материал излагается в предположении, что специалисту, занимающемуся эксплуатацией и обслуживанием компьютеров, а также систем и сетей на их основе, не придётся проектировать интегральные схемы или модули (это область инженеров-конструкторов и технологов электронно-вычислительной аппаратуры). Однако он обязан знать возможности той элементной базы, на которой создана компьютерная система. Поэтому упор сделан на изучение физических принципов действия элементов, схем и функциональных узлов, их характеристик и параметров. Материал разбит на несколько частей. В первой студенты осваивают теорию логического синтеза дискретных устройств, абстрагируясь от их технической реализации. Во второй части изучают организацию и особенности функционирования основных функциональных узлов компьютеров и их подсистем. В третьей части – архитектурные особенности многомашинных и многопроцессорных систем обработки данных. 1.2 Классификация компьютеров 1.2.1 Ядром аппаратного обеспечения информационных систем являются компьютеры разных типов и классов, а также вычислительные комплексы. Они обеспечивают хранение, обработку и обмен информацией с внешней средой. Многообразие решаемых задач и расширение сферы применения компьютеров приводит к увеличению их номенклатуры, что обусловливает потребность в их классификации. Рассмотрим отдельные подходы к их классификации. 1.2.2 Рынок современных компьютеров отличается динамизмом. Почти каждое десятилетие меняются поколения компьютеров, каждые два года – ос- 7 новные типы микропроцессоров. Поэтому любая классификация через какой-то период времени устаревает. Раньше (да и в ряде случаев сейчас) компьютеры классифицировали по быстродействию. С развитием сетевых технологий всё больше начинают использовать другую классификацию, отражающую место и роль компьютера в сети. Рассмотрим данную классификацию: а) мощные машины и вычислительные системы для управления гигантскими сетевыми хранилищами информации. Они обслуживают крупные сетевые банки данных и знаний. По характеристикам их можно отнести к классу суперкомпьютеров, но в отличие от них они являются более специализированными; б) кластерные структуры. Они представляют собой многомашинные вычислительные системы, объединяющие под единым управлением несколько серверов; в) серверы – это компьютеры и системы, управляющие определённым видом ресурсов сети. Различают файл-серверы, серверы приложений, факссерверы, почтовые серверы, коммуникационные серверы, Web-серверы и др.; г) рабочие станции. Термин «рабочая станция» отражает факт наличия в сетях абонентских пунктов, ориентированных на работу профессиональных пользователей с сетевыми ресурсами. Этот термин как бы отделяет их от персональных компьютеров, обеспечивающих работу основной массы непрофессиональных пользователей, работающих обычно в автономном режиме; д) сетевые компьютеры. Они представляют собой упрощённый вариант персонального компьютера, вплоть до карманных персональных компьютеров. Они становятся ещё одним стандартом, объединяющим целый класс компьютеров, производимых массово. Их применение позволяет аккумулировать вычислительные мощности и все виды информационных услуг на серверах в сетях. В связи с этим отпадает необходимость каждому пользователю иметь собственные автономные средства обработки. Таким образом, для подобного вида услуг образуется отдельная ниша, которую должны заполнить сетевые компьютеры, поскольку они обеспечивают: – резкое снижение совокупной стоимости владения вычислительными средствами предприятия, фирмы, корпорации; – повышение производительности работы пользователей при одновременном снижении расходов на обслуживание; – упрощение процессов администрирования, настройки, защиты, модернизации и т.п. Собственные средства обработки в сетевых компьютерах представлены достаточно слабо или вообще отсутствуют. На текущий момент данный класс компьютеров ещё формируется, поэтому нет их единого названия, а можно встретить следующие: «тощие персональные компьютеры», Internet-приборы; браузеры (броузеры), Web PC, Java-терминал, Net Computer и др. 8 1.3 Показатели производительности и эффективности компьютеров 1.3.1 Производительность (П) и общий коэффициент эффективности (Э) являются важными эксплуатационными характеристиками компьютеров, при этом: Э = П / (СК + СЭКС), где СК – стоимость компьютера; СЭКС – затраты на эксплуатацию компьютера за определённый период времени. Так как часто бывает трудно оценить затраты на эксплуатацию, то используют упрощённую формулу: Э = П / СК. Под производительностью компьютера можно было бы понимать количество «вычислительной работы», или, другими словами, количество задач, решаемых данным компьютером в единицу времени. Однако такой подход не учитывает многие объективные и субъективные факторы. Относительно достоверный результат можно получить, если компьютер предназначен для решения определённого класса задач. Но для компьютеров массового спроса такое условие не выполнимо, поэтому их П оценивается упрощённо по скорости выполнения некоторой «смеси» инструкций. Конкретная «смесь» инструкций формируются путём анализа частот исполнения разных инструкций при выполнении программ решения задач некоторого класса. На основе такого анализа отдельным видам инструкций присваиваются весовые коэффициенты. 1.3.2 При использовании «смесей» инструкций П компьютера определяется по формуле: h h S 1 S1 П   kS /  (kStS ), операций (инструкций) в секунду, где ks и ts – соответственно весовой коэффициент и продолжительность выполнения s – й инструкции; h – количество различных инструкций в «смеси». 1.3.3 Существуют разные оценки П компьютеров. Перечислим часто встречаемые оценки, условно объединяемые в три группы: а) абсолютные оценки П (быстродействия) компьютера в целом. Например: – MIP/s (Million of Instruction per Second) – единица П (быстродействия) компьютера, определяемая по скорости выполнения «смеси» инструкций и 9 имеющая размерность млн инстр./с; – CS (Computer Speed) – быстродействие компьютера (количество элементарной типовой работы, выполняемой компьютером в единицу времени); – PCP (Personal Computer Performance) – общий объём работы, выполняемой персональным компьютером при решении пользовательских задач (определяется главным образом пропускной способностью или мощностью основных компонентов компьютера); – MFLOP/s (Million of Floating-point Operation per Second) – единица П высокопроизводительных компьютеров, ориентированных на решение научнотехнических задач, связанных с выполнением больших объёмов вычислений с многоразрядными числами (32, 64, 128, … разрядов) с плавающей точкой (форма FLOAT), размерность – млн опер. с плав. точкой/с; б) абсолютные оценки П (быстродействия) центрального процессора (CPU) компьютера. Например: – PS (Processor Speed) – единица П (быстродействия), определяемая количеством коротких операций (инструкций), выполняемых CPU в одну секунду (она лишь в малой степени характеризует реальную производительность процессора, скорее косвенно оценивает его тактовую частоту в МГц); – D-Benchmark (Dhrystone Benchmark) – единица производительности CPU, определяемая количеством операций над числами с фиксированной точкой в секунду (для её оценки существует эталонная тестовая программа с одноимённым названием); – W-Benchmark (Whetstone Benchmark) – единица производительности CPU, определяемая количеством операций над числами с плавающей точкой в секунду (для её оценки существует эталонная тестовая программа с одноимённым названием); в) относительная (рейтинговая) оценка П (быстродействия) – SI (Speed Index) IBM PC совместимых компьютеров (в известных тестовых алгоритмах в качестве эталона служит модель IBM PC XT), 1.4 Контрольные вопросы для самопроверки 1 Перечислите известные Вам критерии, лежащие в основе классификации компьютеров и систем на их основе. 2 Охарактеризуйте классификацию компьютеров по их месту и роли в информационно-вычислительных (компьютерных) сетях. 3 Какие группы оценок производительности (быстродействия) компьютеров и систем на их основе Вам известны? 4 Чем отличаются абсолютные оценки производительности (быстродействия) компьютеров от относительных? 5 Приведите примеры четырёх – пяти оценок производительности (быстродействия) компьютеров. 10 2 ВВЕДЕНИЕ (продолжение). ЛЕКЦИЯ 2 План лекции: а) понятие комбинационного устройства и конечного автомата; б) синхронизация работы цифровых устройств; в) общие принципы построения современных компьютеров. 2.1 Понятие комбинационного устройства и конечного автомата 2.1.1 Все цифровые устройства можно разделить на две группы: а) комбинационные – устройства, которые не имеют памяти; б) конечные автоматы – устройства, которые имеют память. В комбинационных устройствах (смотри рисунок 2.1) значения выходных переменных Y в течение каждого такта работы определяется значениями входных переменных X только в этом же такте. X Комбинационное устройство Y Рисунок 2.1 – Общий вид комбинационного устройства В конечных автоматах значения выходных переменных Y определяются значениями входных переменных X как в течение рассматриваемого такта работы, так и существовавшими в ряде предыдущих тактов. Для этого в конечных автоматах должны быть запоминающие элементы. При этом память устройства может охватывать не бесконечно большое, а лишь конечное число тактов. Отсюда и следует название устройства – конечный автомат. К этой группе принадлежат все компьютеры. Переменные, сохраняемые в памяти конечного автомата, также как и Y зависят от значений X в предыдущих тактах. 2.1.2 Закон функционирования комбинационного устройства определён, если задано соответствие между его входными и выходными переменными. Это соответствие задаётся в виде одной или нескольких булевых функций (другие употребимые названия булевой функции – переключательная или логическая). Булева функция может быть представлена: – содержательно (вербально или словесно); – таблично; – аналитически (в виде математического выражения). Таблицы, показывающие связь между входными и выходными переменными комбинационных устройств, называют таблицами истинности (или таблицами состояний). Аналитически форма этих связей в общем случае представляет собой систему уравнений, как показано на рисунке 2.2. 11 х1 х2 х3 Комбинационное устройство • • • • • • хn y1 y2 y3 y1 = y1 (х1, х2, х3, . . ., хn); y2 = y2 (х1, х2, х3, . . ., хn); • • • yS = yS (х1, х2, х3, . . ., хn). yS Рисунок 2.2 – Общий вид комбинационного устройства 2.1.3 В конечных автоматах выходные переменные yj зависят не только от входных переменных xi, но и от выходных переменных элементов памяти zk, присутствующих в этом же такте. При анализе и синтезе конечные автоматы разбивают на комбинационную часть и элементы памяти, называемые цепями обратной связи, как показано на рисунке 2.3.. х1 х2 х3 хn • • • Комбинационная часть zr z2 z1 r ••• 2 1 • • • y1 y2 y3 yS Ir I2 Элементы памяти I1 х хn Рисунок 2.3 –n Общий вид конечного автомата Обозначим t и (t + 1) два следующих друг за другом такта работы автомата. Состояние элементов памяти в (t + 1) – й такт определяется множествами как входных переменных xi, так и переменных на входах элементов памяти Ik в предыдущий такт t, то есть: zk( t 1)   k ( x1 , x2 ,..., xn , I1 , I 2 ,..., I r ) t . 12 Приведённое выражение называют функцией переходов. Выходные же переменные yj могут формироваться двояко. В автоматах Мили́ они являются функцией как входных переменных xi, так и выходных переменных элементов памяти zk в этот же такт, то есть: y (j t 1)  f j ( x1 , x2 ,..., xn , z1 , z2 ,..., zr ) ( t 1) . Приведённое выражение называется функцией выхода автомата Мили́. В автоматах же Му́ра выходные переменные yj являются функцией только выходных переменных элементов памяти zk в этом же такте, то есть: y (j t 1)  f j ( z1 , z2 ,..., zr ) ( t 1) . Приведённое выражение называется функцией выхода автомата Му́ра. Функции переходов и выходов конечных автоматов могут выражаться таблицами переходов и выходов. 2.2 Синхронизация работы цифровых устройств Определение из словаря: «Синхронизация – одновременность, совпадение и связь во времени чего-либо совершающегося, параллельность в действии чего-либо». Все цифровые устройства делят на асинхронные (несинхронизируемые) и синхронные (синхронизируемые). В асинхронных устройствах изменение входных сигналов сразу же влечёт за собой соответствующее изменение выходных сигналов. Например, работу логического элемента И можно представить с помощью временных диаграмм, показанных на рисунке 2.4: x1 0 0 0 1 0 1 x1 x2 & y t x2 0 1 0 0 0 1 t y 0 0 0 0 0 1 t Рисунок 2.4 – Иллюстрация переключения асинхронного устройства 13 В синхронных устройствах изменение выходных сигналов, соответствующее новому сочетанию входных сигналов, происходит только после подачи синхронизирующего (тактового) импульса. Например, если синхронизировать работу устройства, выполняющего логическую операцию И, то при наличии x1 = x2 = 1 значение выходного сигнала станет равным 1 только в момент прихода синхронизирующего (С) импульса, то есть С = 1 (смотри рисунок 2.5). С x1 x2 С y t x1 x1 1 1 1 1 x2 1 1 1 1 С 1 1 1 1 y 1 Для сравнения: если бы устройство было асинхронным t x2 t y t y t Рисунок 2.5 – Иллюстрация переключения синхронного устройства 2.3 Общие принципы построения современных компьютеров 2.3.1 К основным принципам построения современных компьютеров относят: – программное управление; – модульность конструкции; – магистральность; – иерархию управления. Идея программного управления была предложена в 1945 году Дж. фон Нейманом. В её основе лежит представление алгоритма решения любой задачи в виде программы вычислений. То есть все вычисления, предписанные алгоритмом решения задачи, должны быть представлены в виде последовательности управляющих слов – команд или инструкций. Инструкции и обрабатываемые ими данные помещаются во внутреннюю память. Внутренняя память организована как линейная последовательность пронумерованных ячеек. Номер 14 ячейки является её адресом – в случае адресной организации1. Каждый тип информации (инструкции и данные) имеют свой формат. Общим является их кодирование двоичными цифрами 0 и 1. Работа компьютера как бы копирует последовательность преобразований, выполняемых человеком по некоторому алгоритму. Отсюда вытекает и структура компьютера (смотри рисунок 2.6), отвечающая принципу программного управления. Особенностями этой структуры являются следующие традиционные признаки: Арифметикологическое устройство (АЛУ) Локальная (микропроцессорная) память Устройство управления Интерфейсная сист ема Центральный процессор Основная (внутренняя) память Постоянное Оперативное запоминающее запоминающее устройство устройство (ПЗУ) (ОЗУ) Системная шина (магистраль) Видеоадаптер (УУ) Источник питания Таймер Видеомонитор (дисплей) Генератор тактовых импульсов Интерфейс клавиатуры Клавиатура Рисунок 2.6 – Классическая структура компьютера а) ядро компьютера образуют процессор – единственный вычислитель и внутренняя память, связанные каналами обмена информацией (локальной шиной); б) линейная организация ячеек всех видов внутренней памяти фиксированного информационного объёма; в) одноуровневая адресация ячеек памяти, стирающая различия между всеми типами информации; г) внутренний машинный язык низкого уровня, содержащий инструкции элементарных преобразований (операций) операндов. Полный набор этих инструкций составляет так называемый набор инструкций (систему команд) дан1 В последующем была предложена ассоциативная (безадресная) память, поиск информации в которой осуществляется не по адресу, а по содержанию информации. 15 ного типа процессора; д) централизованное последовательное управление вычислениями. 2.3.2 Эволюция классической структуры компьютера по-разному проявилась в последующих поколениях компьютеров. Стали широко использоваться децентрализованные построение и управление, что иллюстрирует структура компьютера на рисунке 2.7. Математический сопроцессор Арифметикологическое устройство (АЛУ) Локальная (микропро цессорная) память Устройство управления Интерфейсная система Микропроцессор Основная (внутренняя) память Оперативное Постоянное запоминающее запоминающее устройство устройство (ОЗУ) (ПЗУ) Накопитель на жестком магнитном диске (НЖМД) Накопитель на оптическом диске (НОД) Адаптер НЖМД Адаптер НОД Система магистралей (шин) Видеоадаптер Адаптер принтера Видеомонитор (дисплей) Печатаю щее устройство (принтер) (УУ) Генератор тактовых импульсов Внешняя память Интерфейс клавиатуры Источник питания Сетевой адаптер Таймер Канал связи Клавиатура Рисунок 2.7 – Структура современного компьютера Наличие собственных схем управления в отдельных функциональных узлах (например, в адаптерах) обеспечивает совмещение операций – параллельную работу узлов при обработке различных фаз нескольких инструкций. Отмеченная децентрализация легла в основу стандартизации структур и конструкций современных компьютеров. Общепризнанными стали модульность конструкции, магистральность и иерархия управления. 2.3.3 Модульность конструкции предполагает выделение в структуре компьютера достаточно автономных, функционально и конструктивно законченных устройств. Она делает конструкцию компьютера открытой системой, 16 способной к адаптации и совершенствованию. Стандартизуются и унифицируются оборудование, номенклатура аппаратных и программных средств, средства сопряжения. Магистральность определяет способы обмена информацией между всеми модулями, Стандартизация и унификация конкретизировали иерархию магистралей (шин) и их специализацию. Из-за различий в скорости работы отдельных устройств в структуре компьютера появились: – системная шина, например, PCI – для взаимодействия основных узлов; – периферийная шина, например, ISA (EISA) – для подключения «медленных» периферийных устройств. Иерархия управления характерна тем, что некоторые второстепенные функции управления центрального процессора переданы другим функциональным устройствам. В частности, свои управляющие устройства имеют практически все адаптеры – в их составе имеются процессор и память. Иерархия управления устанавливает и структурную иерархию. Это очевидно из организации таких подсистем; – процессор – сопроцессор; – подсистема памяти (локальная память CPU – кэш – основная память – внешняя память); – подсистема ввода-вывода. 2.4 Контрольные вопросы для самопроверки 1 По какому основному признаку можно определить принадлежность цифрового устройства к группе комбинационных? 2 По какому основному признаку можно определить принадлежность цифрового устройства к группе конечных автоматов? 3 Каким способом (какими способами) можно задать закон функционирования комбинационного устройства? 4 Каким способом (какими способами) можно задать закон функционирования конечного автомата? 5 Какие существуют виды конечных автоматов и каковы их принципиальные различия? 6 С какой целью осуществляется синхронизация работы цифровых устройств? 7 Объясните механизм синхронизации работы цифровых устройств. 8 Объясните принцип программного управления работой компьютера. 9 Объясните принцип модульного построения современных средств вычислительной техники. 10 Какими достоинствами обладает магистральный принцип построения средств вычислительной техники? 11 Объясните суть иерархического принципа построения и управления работой современных средств вычислительной техники. 17 3 ОСНОВЫ ТЕОРИИ ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ УСТРОЙСТВ. ЛЕКЦИЯ 3 План лекции: а) основные положения булевой алгебры (алгебры логики); б) законы, аксиомы, теоремы, тождества и операции булевой алгебры; в) минимизация логических функций; г) виды дискретных электрических сигналов; д) виды входного и выходного интерфейсов цифровых устройств; е) логические элементы цифровой техники. 3.1 Основные положения алгебры логики (булевой алгебры) 3.1.1 Решение всех задач с помощью компьютеров, а также функционирование компьютеров (и других средств цифровой вычислительной техники) происходит в двоичной системе счисления, имеющей базис q = 2. Двоичная система счисления оперирует только двумя цифрами: нуль (0) и единица (1). В то же время математическим аппаратом, на основе которого проектируются и реализуются цифровые устройства и содержащиеся в них логические схемы, является алгебра логики (булева алгебра). Алгебра логики применяется также при решении различных задач обработки информации. 3.1.2 Как известно, предметом рассмотрения булевой алгебры являются высказывания (утверждения), которые могут оказаться либо истинными, либо ложными. Следовательно, истинность высказывания может принимать, подобно цифрам двоичной системы счисления, только два значения: «истина» и «ложь». Если прийти к соглашению, обозначив логическое значение «истина» цифрой 1, а логическое значение «ложь» – цифрой 0, то получим в своё распоряжение две константы, по аналогии с базисными цифрами двоичной системы счисления. А из этого следует, что на физическом уровне для представления логических констант можно применить тот же принцип, что и для представления математических констант (цифр). Высказывания могут быть простыми (логически неделимыми) и сложными (состоящими из простых высказываний). Высказывания, как и любые переменные величины, можно обозначать символами, в частности, буквами латинского алфавита. Примерами простых высказываний и их обозначений могут служить: 1) «значение одноразрядного двоичного числа Х равно единице» обозначим как А (А – логическая переменная); 2) «значение одноразрядного двоичного числа Y равно нулю» обозначим как В (В – логическая переменная). Если утверждение 1 соответствует действительности, то есть X = 1, то значение логической переменной А, то есть «истина» (читается «А»). Если же 18 утверждение 1 не соответствует действительности, то есть X = 0, то значение логической переменной А , то есть «ложь» (читается «НЕ А»). Учитывая принятые обозначения логических констант («истина» = 1; «ложь» = 0), можно приведённые рассуждения представить в табличной форме (смотри таблицу 3.1). Таблица 3.1 – Интерпретация простого логического высказывания Высказывание Реальность Значение одноразрядного двоичного числа Х равно единице X = 1 – «истина» X = 0 – «ложь» Символьное обозначение А А Количественная оценка А=1 А=0 Сложные высказывания образуются путём объединения простых высказываний логическими операциями (связками). По своей сути сложные высказывания являются логическими функциями и обозначаются, как и простые высказывания, символами. В свою очередь сложное высказывание может быть частью другого сложного высказывания более высокого уровня. Как и простые высказывания сложные могут быть истинными или ложными. К основным логическим операциям, на основании определения булевой алгебры (обратитесь за помощью к дисциплине «Физические основы ЭВМ»!), относят И, ИЛИ, НЕ: – операция И (конъюнкция или логическое умножение) для двух логических переменных записывается в виде F = X * Y (читается: «X И Y»); – операция ИЛИ (дизъюнкция или логическое сложение) для двух логических переменных записывается в виде F = X + Y (читается: «X ИЛИ Y»); – операция НЕ (логическое отрицание) записывается в виде F= Х , (читается: «НЕ X»). Примечание – Ранее (в процессе изучения дисциплины «Физические основы ЭВМ») мы пришли к соглашению, что будем использовать вместо символа операции ДИЗЪЮНКЦИЯ «» – символ «+», вместо символа операции КОНЪЮНКЦИЯ «» – символ «*» и вместо символа операции ОТРИЦАНИЕ “  ” – надстрочную черту, например Х ; 3.1.3 Логическую функцию можно представлять в: – смысловой (словесной или вербальной) форме; – табличной форме; – аналитической (математической) форме. Как иллюстрацию данного положения рассмотрим пример решения следующей задачи: «цифровое устройство управления с тремя входами (X, Y, Z) и одним выходом (F) формирует на своём выходе высокоуровневый сигнал управ- 19 ления (UF > 0), если одновременно на двух его входах X и Y присутствуют сигналы высокого уровня (UX > 0 и UY > 0), при этом одновременная подача сигналов с нулевым уровнем на все три входа запрещена»; а) смысловая форма представления логической функции: «функция F трех аргументов X, Y, Z принимает значение 1, если два аргумента X, Y одновременно равны 1 (независимо от значения Z). Одновременное равенство 0 трёх аргументов запрещено. Во всех других случаях функция равна 0». Анализ условия задачи: при трех аргументах максимальное количество наборов равно 8, причем один набор является запрещённым, следовательно, функция недоопределена; б) табличная форма представления функции имеет вид таблицы 3.2. Таблица 3.2 – Табличная форма представления функции X 1 1 1 1 Y 1 1 1 1 Z 1 1 1 1 F – 1 1 Первоначально в таблицу заносятся все возможные комбинации значений аргументов. Затем последовательно комбинация значений аргументов каждой строки таблицы сверяется с условием задачи. Если конкретная комбинация значений аргументов соответствует формулировке задачи, то в колонку, обозначенную F, заносится соответствующее значения логической функции, равное единице или нулю. В качестве значения функции при неизвестных или запрещённых комбинациях значений аргументов1 можно использовать любые символы, отличные от 0 и 1 (в примере использовано тире). По таблице можно записать функцию в аналитической форме; в) аналитическая форма представления функции. Может быть несколько одинаковых по смыслу (но не по форме) записей в виде: – совершенной дизъюнктивной нормальной формы (СДНФ) для истинных значений функции как суммы произведений значений аргументов – наборов – выбираются комбинации значений аргументов, соответствующие истинным значениям функции F  X *Y * Z  X *Y * Z; 1 Наличие неизвестных или запрещённых комбинаций значений аргументов логической функции обязательно оговаривается в условии задачи. По умолчанию конкретная комбинация может принять одно из двух значений – 0 или 1 (опять-таки, исходя из условия задачи) 20 – СДНФ для ложных значений функции как суммы наборов F  X *Y * Z  X *Y * Z  X *Y * Z  X *Y * Z  X *Y * Z; – и после применения закона инверсии (закона де Моргана) к двум последним функциям придём к их записям в виде совершенной конъюнктивной нормальной формы (СКНФ) как произведению сумм значений аргументов, то есть F  ( X  Y  Z ) * ( X * Y * Z ); F  ( X  Y  Z ) * ( X  Y  Z ) * ( X  Y  Z ) * ( X  Y  Z ) * ( X  Y  Z ). 3.2 Законы, аксиомы, теоремы, тождества и операции булевой алгебры 3.2.1 В литературе по компьютерной математике встречается такое определение булевой алгебры: «Булевой алгеброй называют непустое множество В с двумя бинарными операциями  – дизъюнкция (ИЛИ),  – конъюнкция (И) и одной унарной  – отрицание (НЕ), которые удовлетворяют следующим законам для любых элементов (X, Y, Z)  B»: Коммутативный закон: X + Y = Y + X; X * Y = Y * X. Ассоциативный закон: X + (Y + Z) = (X + Y) + Z; X * (Y * Z) = (X * Y) * Z. Законы единицы и нуля: X + 1 = 1; X + 0 = X; X * 1 = X; X * 0 = 0. Законы комбинации с дополнением: X + Х = 1; X * Х = 0. Дистрибутивные законы: X + (Y * Z) = (X + Y ) * (X + Z); X * (Y + Z) = (X * Y ) + (X * Z). Инволютный закон (двойное отрицание) Х = X. Законы поглощения: X + (X * Y) = X ; X * (X + Y) = X; X + ( Х * Y) =X + Y; Х + (X * Y) = Х + Y. Закон склеивания (X * Y) + (X * Y ) = X; Законы идемпотентности: X + X = X; X * X = X; Законы де Моргана: Х  Y  Z  ...  X *Y * Z *...; X *Y * Z *...  X  Y  Z  .... Приведённые законы используются для упрощения (минимизации) булевых функций. Таблицы, характеризующие основные логические операции и приве- 21 дённые в сводной таблице 3.3, называются таблицами истинности. Таблица 3.3 – Таблицы истинности логических операций И, ИЛИ, НЕ Операция И X Y F Операция ИЛИ X Y F 1 1 1 1 1 1 1 1 1 1 1 1 Операция НЕ X F 1 1 Помимо представленных в таблице 3.3 логических операций имеются и другие, перечисленные в таблице 3.4. Таблица 3.4 – Перечень дополнительных логических операций для двух переменных Наименование логической операции Символическое изображение Штрих Шеффера (И-НЕ): Стрелка Пирса (ИЛИ-НЕ) ИМПЛИКАЦИЯ ИСКЛЮЧАЮЩЕЕ ИЛИ РАВНОЗНАЧНОСТЬ F = XY = Х * Y F = XY = Х  Y F=X Y F = X Y F=XY Из приведённых в таблице 3.4 логических операций первые две заслуживают внимание по причине их использования в процессе конструирования аппаратных средств дискретных устройств. Таблицы истинности, соответствующие этим операциям, сведены в таблицу 3.5. Таблица 3.5 – Таблицы истинности логических операций И-НЕ, ИЛИ-НЕ для двух переменных Операция И-НЕ X Y F 1 1 1 1 1 1 1 Операция ИЛИ-НЕ X Y F 1 1 1 1 1 3.2.2 Положение: «Любое логическое выражение (любая логическая функция) может быть представлено в виде формулы, содержащей только операцию  или только операцию ». Следствие: указанный в определении переход осуществляется с помо- 22 щью законов де Моргана. Пример: записать математическое выражение функции F по таблице истинности 3.6, используя только операцию . Таблица 3.6 – Таблица истинности к примеру X 1 1 1 1 Y 1 1 1 1 Z 1 1 1 1 F 1 1 1 1 1 F = Х * Y *Z + Х *Y * Z + X * Y * Z + X * Y *Z + X * Y * Z = = ( X * Y * Z ) * ( X * Y * Z ) * ( X * Y * Z ) * ( X * Y * Z ) * ( X * Y * Z ). 3.2.3 Теоретически доказано, что количество логических операций является избыточным, то есть одни операции могут быть представлены другими, а точнее, их комбинациями. Часто используется операция РАВНОЗНАЧНОСТЬ (X  Y) с отрицанием, то есть Х  Y . В силу специфики изготовления аппаратного обеспечения средств вычислительной техники она заменяет операцию НЕ. Поскольку операция НЕ унарная, а Х  Y – бинарная, то замена позволяет ввести в систему операций только бинарные операции: РАВНОЗНАЧН О , И, ИЛИ. Тогда возникает необходимость представлять через эти три операции такие: НЕ, ИМПЛИКАЦИЯ, РАВНОЗНАЧНО. В этом случае справедливы тождества: Х  X  1; X Y  X 1  Y; ( X  Y )  X  Y  1, которые предлагается студентам доказать самостоятельно с помощью таблиц истинности. 3.3 Минимизация логических функций 3.3.1 Под минимизацией понимается упрощение и преобразование логических функций до вида, приемлемого для их аппаратной реализации и создания простого по составу и эксплуатации узла или модуля вычислительного устройства. Существуют аналитические и графические методы минимизации. К аналитическим методам следует относить и машинные алгоритмы минимизации. Аналитическая минимизация, выполняемая с помощью «ручки и бума- 23 ги», требует определённой интуиции проектировщика и применима для простых функций небольшого числа аргументов. Для минимизации сложных функций разработаны машинные алгоритмы. 3.3.2 Графическая минимизация основана на применении карт Карно. Карта Карно – это прямоугольник, разбитый на клетки, число которых равно максимальному числу наборов функции, т.е. 2n, где n - число аргументов. Каждая клетка соответствует одному набору и туда записывается его значение: 1 или 0. В случае недоопределённой функции клетка может быть заполнена, например, символом (-) для неизвестного набора или символом () – для запрещённого набора. Каждая клетка имеет свой адрес. Ниже на рисунке 3.1 даны рекомендуемые шаблоны адресации клеток карт Карно двух (A,B), трёх (A,B,C) и четырёх (A,B,C,D) аргументов. После заполнения клеток значениями наборов выполняется минимизация функции. B B B A A A A B B B D A 1 C С С D A 1 D C С С Рисунок 3.1 – Рекомендуемые шаблоны адресации клеток карт Карно функций соответственно двух, трёх и четырёх аргументов ПРИМЕР. Из таблицы истинности логической функции F четырёх аргументов A, B, C, D известно, что два набора придают функции значение логической единицы, а именно: F  A  B  C  D  A  B  C  D , и два набора придают функции значение логического нуля, а именно: F  A  B  C  D  A  B  C  D , значения остальных наборов неизвестны. На правой карте рисунка 3.1 в соответствующие клетки проставлены известные значения четырёх наборов. Отыскание минимальной формы функции сводится к объединению соседних клеток, при этом соседними считаются и все крайние клетки с учётом «цилиндричности» карты относительно вертикальной и горизонтальной осей. Можно сформулировать ряд общих правил: а) минимизировать можно как по единичным, так и по нулевым значениям наборов в зависимости от состава функции; б) объединять клетки можно по столбцам, по строкам, по квадратам (учитывая и «цилиндричность» карты); в) число клеток, объединяемых в одну группу, должно быть или 2, или 4, или 8, или 16 и никаким другим (для функций с количеством аргументов не 24 более четырёх); г) количество групп объединяемых клеток может быть любым; д) нужно стремиться объединять в каждую группу как можно большее число клеток и сводить к минимуму количество групп объединяемых клеток. С этой целью полезным будет пункт (е) правил; е) в случае недоопределённой функции её можно доопределить, проставив в клетки неизвестных или запрещённых наборов 1 или 0, если это необходимо для выполнения пункта (д) правил; ж) одна или несколько клеток могут входить в более чем одну группу объединяемых клеток. После объединения клеток можно записать минимальную форму функции, у которой количество наборов равно количеству групп объединённых клеток, т.е. каждый набор соответствует «своей» группе клеток. При этом каждый набор содержит те аргументы, которые являются общими для группы, т.е. не меняют своего значения (например, с 1 на 0 или наоборот). Устройство с n входами и несколькими выходами (например, s) описывается несколькими логическими функциями, количество которых равно количеству выходов, то есть s. Каждая из этих функций может быть функцией n аргументов. Для каждой функции составляется своя карта Карно. Можно минимизировать каждую функцию в отдельности, независимо от остальных, и по ним реализовать схему, которая будет состоять из s отдельных схем, имеющих одни и те же входы. Однако такой путь часто приводит к избыточности элементов в устройстве. Поэтому целесообразно рассматривать все s функций в совокупности. Это значит, что нужно стремиться выделить в них общие наборы или группы наборов, которые могут быть реализованы одним общим узлом. В случае использования карт Карно нужно выделять одинаковые группы клеток. При таком подходе некоторые функции могут оказаться не в минимальной форме, но с этим мирятся ради упрощения устройства. 3.4 Виды дискретных электрических сигналов По виду кодирования двоичных цифр электрическими сигналами на входе и выходе элементы дискретной техники делятся на: – потенциальные; – импульсные. 3.4.1 В потенциальных элементах единице и нулю соответствуют два резко отличающихся уровня напряжения, называемые высоким и низким уровнями. При этом напряжение может быть как положительным, так и отрицательным относительно корпуса, электрический потенциал которого принимается равным нулю (смотри таблицу 3.7). 25 Таблица 3.7 – Пример потенциальных сигналов Полярность уровней напряжения Вид логики Положительная Отрицательная U, В Положительная U, В 1 + 2,5 1 + 2,5 + 0,5 + 0,5 t t U, В U, В Отрицательная t – 0,5 t – 0,5 – 2,5 – 2,5 1 1 В положительной логике: – за логическую единицу принят высокий уровень напряжения (например, + 2,5 В при положительной полярности уровней напряжения или – 0,5 В при отрицательной полярности уровней напряжения); – за логический нуль принят низкий уровень напряжения (то есть + 0,5 В при положительной полярности уровней напряжения или – 2,5 В при отрицательной полярности уровней напряжения). В отрицательной логике кодирование логических единицы и нуля противоположное. U 1 U t а) 1 1 U t б) t в) Рисунок 3.2 – Пример импульсных сигналов 3.4.2 В импульсных элементах в одном варианте логической единице соответствует наличие импульса напряжения, как показано на рисунках 3.2, а, б, причём он может быть как положительным, так и отрицательным. Нулю соответствует отсутствие импульса (рисунок 3.2, а) или значительно меньший по величине импульс (рисунок 3.2, б). В другом варианте единице соответствует положительный, а нулю – отрицательный импульсы (рисунок 3.2, в). 26 3.5 Виды входного и выходного интерфейсов цифровых устройств Информация, поступающая в то или иное цифровое устройство, представляет дискретный (то есть состоящий из нулей и единиц) сигнал – двоичный код. На передачу сигнала отводится конечный отрезок времени, называемый тактом работы устройства. За один такт в случае последовательного интерфейса передаётся один из разрядов двоичного кода, а в случае параллельного интерфейса передаётся вся кодовая комбинация. В общем случае на вход цифрового устройства поступает множество двоичных переменных Х(х1, х2, … , хn), а с выхода снимается множество двоичных переменных Y(y1. y2. … . ys). При этом устройство осуществляет (реализует) определённую связь между входными и выходными переменными. Подобная связь характеризуется (описывается) логическими функциями. 3.6 Логические элементы цифровой техники 3.6.1 В соответствии с тремя основными логическими операциями – И, ИЛИ, НЕ – в схемах цифровых устройств используются следующие логические элементы, представленные на рисунке 3.3. И x1 x2 x3 ИЛИ & y x1 x2 x3 ••• НЕ 1 y x y ••• xn xn а) б) в) Рисунок 3.3 – Графические изображения основных логических элементов Принято на функциональных, монтажных и принципиальных схемах входы элементов обозначать прописными xi, а выходы – yj . Элемент И (называемый также схемой логического умножения, конъюнктором, схемой совпадения, ключом) условно изображается, как показано на рисунке 3.3, а. Элемент ИЛИ (называемый также схемой логического сложения, дизъюнктором, сборкой) условно изображается, как показано на рисунке 3.3, б. Элемент НЕ (называемый также схемой логического отрицания, инвертором) условно изображается, как показано на рисунке 3.3, в. Набор элементов, приведённый на рисунке 3.3, называют основным базисом или основной функционально полной системой элементов. Последнее означает, что с помощью этих элементов можно создать схему, реализующую любую сколь угодно сложную логическую операцию. 27 3.6.2 В интегральной схемотехнике широко используют элементы других базисов: И-НЕ (штрих Шеффера) и ИЛИ-НЕ (стрелку Пирса). На схемах они изображаются, как показано на рисунке 3.4. И-НЕ x1 x2 x3 ИЛИ-НЕ & y x1 x2 x3 ••• xn 1 y ••• xn Рисунок 3.4 – Графические изображения логических элементов базисов И-НЕ, ИЛИ-НЕ Каждый из этих двух элементов представляет собой функционально полную систему элементов. 3.7 Контрольные вопросы для самопроверки 1 Дайте определение алгебры логики (булевой алгебры). 2 Приведите примеры простых и сложных логических высказываний. 3 Какую роль играют логические связки? 4 Почему алгебра логики взята за основу построения дискретных (цифровых устройств)? 5 Приведите примеры не менее семи законов алгебры логики. 6 Изобразите таблицы истинности, характеризующие логические операции, упомянутые в определении алгебры логики. 7 Опишите алгоритм доказательства тождества логических выражений. 8 Опишите особенности аналитической минимизации логических функций на конкретном примере. 9 Опишите особенности графической минимизации логических функций на конкретном примере. 10 Дайте описание видов и форм потенциальных электрических сигналов, используемых в средствах цифровой (дискретной) техники. 11 Дайте описание видов и форм импульсных электрических сигналов, используемых в средствах цифровой (дискретной) техники. 12 Что такое интерфейс и какие виды интерфейсов используются в средствах цифровой (дискретной) техники? 28 4 ФУНКЦИОНАЛЬНЫЕ УЗЛЫ КОМПЬЮТЕРОВ. ЛЕКЦИЯ 4 План лекции: а) триггеры: – определение, назначение, типы; – алгоритм логического синтеза универсального асинхронного JK – триггера; б) счётчики и делители частоты на их основе: – определение, назначение, классификация; – суммирующий счётчик с последовательным переносом; – счётчики с параллельным переносом. 4.1 Триггеры 4.1.1 Определение, назначение, типы триггеров. Триггеры (Тг) являются простейшим цифровым автоматом (в переводе Trigger – спусковой крючок). Он обладает памятью и способен хранить 1 бит двоичной информации (состояние 1 и 0) после окончания действия входных сигналов. При считывании информация сохраняется, а в случае отключения питания – теряется. На долю триггеров приходится ориентировочно 20 – 40% от всех элементов средств вычислительной техники, и везде используется их основное свойство – сохранять состояние до прихода входных сигналов, в качестве которых выступают управляющие, синхронизирующие, информационные сигналы. Как конечный автомат Тг характеризуется такими свойствами: а) число внутренних состояний – два (единица или нуль), что соответствует одной внутренней переменной (z1), обозначаемой для триггера буквой Q; б) число выходных переменных – одна (у1). Значение «у1» совпадает со значением Q, то есть y1t 1  Q t 1 . Q – это основной выход. Наряду с ним у триггера имеется и дополнительный выход – инверсный основному или Q ; в) число входных переменных (х) зависит от типа триггера. Переходный процесс внутри Тг, обусловленный изменениями входных сигналов, протекает за очень короткий промежуток времени, что позволяет применять Тг в качестве запоминающего элемента быстродействующей (сверхоперативной) памяти, которую называют ещё статическим запоминающим устройством. Быстродействие сверхоперативной памяти сопоставимо с быстродействием центральных процессоров (ЦП) современных персональных компьютеров (ПК) и её применение позволяет сгладить противоречие между сравнительно невысокой производительностью основной памяти и высокой производительностью ЦП. Триггеры лежат в основе построения локальной памяти – составной части ЦП, теневой памяти (так называемой кэш-памяти). Кэш-память является буфером между основной памятью (оперативным запоминающим устройством) и другими узлами и устройствами. Кроме перечисленного, триг- 29 геры применяются в качестве переключающих элементов; элементарных ячеек при создании счётчиков импульсов, элементов временной задержки импульсов и т.д. Для Тг принято условное обозначение (рисунок 4.1). Поле для условных меток входов В х о д ы Т . . . Q Q В ы х о д ы Рисунок 4.1 – Условное графическое изображение триггера на схемах Количество и названия входов зависят от типа триггера. Однако независимо от типа триггера, его входы можно разделить на две группы: информационные и управляющие. В зависимости от назначения каждый вход имеет свою условную метку. Состояние Тг отождествляют с сигналом на основном (прямом) выходе Q. Тг находится в единичном состоянии при Q = 1, Q = 0 и нулевом – при Q = 0, Q = 1. Одним из способов управления Тг является его синхронизация, и по этому признаку Тг подразделяют на синхронизируемые (синхронные или тактируемые) и несинхронизируемые (асинхронные). У асинхронного Тг изменение состояния происходит непосредственно с приходом информационного сигнала. В синхронизируемом Тг кроме информационных входов, на которые подаются информационные сигналы, имеется вход (один или несколько) синхронизации или, что то же самое, тактовый вход. Изменение состояния Тг при наличии на информационном входе сигнала может произойти только в момент подачи на вход синхронизации (или синхровход) соответствующего управляющего – разрешающего сигнала. Принцип синхронизации поясняют временные диаграммы рисунка 4.2. Информационный вход Синхровход Выход t t t Рисунок 4.2 – Принцип синхронизации работы триггера Поскольку триггеры относятся к такому типу узлов, состояние которых в текущий момент времени зависит не только от действующих сигналов на входах, но и от его состояния в предшествующий момент времени, то есть от 30 предыстории, то в связи с этим работа триггера описывается не таблицей состояний, а таблицей переходов. В таблице переходов значения выходной величины в момент времени t – до срабатывания Тг – влияют на состояние Тг после его срабатывания – момент времени t+1. Поэтому выходная величина Q t выступает как входная по отношению к величине Q t +1. Все многообразие прикладных задач по созданию логических устройств и узлов решается с помощью ограниченного числа типов триггеров. Перечислим основные типы триггеров, их отличительные характеристики и упрощённые условные обозначения. Словесные описания принципов функционирования и таблицы переходов некоторых типов триггеров приведены в ПРИЛОЖЕНИИ А. Триггер с двумя установочными входами – RS-триггер (SET – установка; RESET – сброс), асинхронный (несинхронизируемый). S T R Q Q RS-триггер устанавливается в единичное состояние (Q = 1) при подаче на установочный вход единицы (S = 1). Сброс единицы на выходе Q осуществляется подачей единицы на вход сброс (R = 1). Данный тип триггера служит основой триггеров других типов; его синхронизируемый вариант используется для хранения промежуточной информации; он является неотъемлемой частью контактных клавишных устройств, т.к. обеспечивает ликвидацию явления «дребезга контактов». Асинхронный (несинхронизируемый) Т-триггер со счётным входом, срабатывающий от положительного перепада входного импульса. Он служит для деления частоты входного сигнала на два. T T  Q Q Т-триггер меняет своё состояние на противоположное с приходом каждого очередного входного импульса. Основная область применения - счётчики импульсов. Соединяя Т - триггеры последовательно, можно создать счётчик, который делит частоту входного сигнала на 4, 8, 16 и т.д. Синхронизируемый по входу C отрицательным перепадом синхроимпульса триггер задержки – D-триггер (delay – задержка). Он обеспечивает задержку во времени входного импульса на один - два такта последовательности синхронизирующих импульсов. 31 D T C Q Q Например, у однотактного D-триггера состояние логической 1 сохраняется после снятия входного сигнала до прихода очередного синхроимпульса. Данный тип триггеров широко применяется при построении регистров. Универсальный синхронизируемый JK-триггер. J T C K Q Q Коммутируя внешние выводы этого Тг, можно получить аналог любого из трёх рассмотренных выше типов триггеров, обладающий соответствующими качествами. В частности, подача на вход J сигнала S, а на вход K – сигнала R превращает JK-триггер в RS-триггер, только следует помнить, что набор R = S =1 является запрещённым. Если объединить входы J и K и подавать на них сигнал Т, то получится Т-триггер. J T C K Q Q Если собрать изображённую внизу схему, то получится D-триггер. J T C K Q Q 4.1.2 Алгоритм логического синтеза универсального асинхронного JKтриггера. Словесное описание принципа функционирования: «Создать устройство с двумя информационными входами (J и K), у которого: – состояние по основному выходу не меняется при отсутствии входных информационных сигналов (если J t = K t = 0, то Q t +1 = Q t = 0 или 1); – единица на основном выходе появляется при подаче на установочный вход J единицы (если J t = 1 и K t = 0, то Q t +1 = 1), и в дальнейшем состояние устройства не должно меняться при любом сигнале на установочном входе; 32 – сброс единицы на основном выходе осуществляется подачей единицы на вход сброса K (если J t = 0 и K t = 1, то Q t +1 = 0), и в дальнейшем состояние устройства не должно меняться при любом сигнале на входе сброса; – наличие единицы на обоих информационных входах инвертирует предыдущее состояние триггера». По словесному описанию составим таблицу переходов (таблица 4.1). Она будет содержать три входных (J t , K t , Q t) и одну выходную (Q t +1) переменные. Количество возможных комбинаций значений входных переменных равно 23 = 8. Таблица 4.1 – Таблица переходов синтезируемого триггера Номер набора в такте t 1 2 3 4 5 6 7 J 1 1 1 1 Такт t Kt 1 1 1 1 t Q 1 1 1 1 t Q t +1 1 1 1 1 По таблице переходов составляется логическая функция. Минимизируем её с помощью карты Карно: Q t +1 Kt Q t 1 1 1 1 Jt в результате получим: Q t 1  J t  Q t  K t  Q t или Q  J  Q  K  Q. С учётом применения элементов базиса И-НЕ преобразуем полученную функцию к виду Q  J Q  K Q и построим функциональную схему триггера (рисунок 4.3). 33 & Q & J & K K & Q & Рисунок 4.3 – Функциональная схема универсального асинхронного JK-триггера Составим матрицу переходов JK-триггера (таблица 4.2). Она применяется при проектировании счётчиков импульсов табличным методом. Матрица переходов определяет значения входных сигналов триггера в зависимости от его перехода из одного состояния в другое (вспомните, что таблица переходов триггера определяет его переходы из одного состояния в другое в зависимости от значений входных сигналов). В основе построения матрицы переходов лежит логическая функция. Таблица 4.2 – Матрица переходов универсального асинхронного JK-триггера Q t → Q t+1 0 → 0 0 → 1 1 → 0 1 → 1 Q t 1  J t  Q t  K t  Q t . при любом K и J = 0 при любом K и J = 1 1  J t  1  K t  0  .J 0  J t  0  K t  1  K t . при любом J и K = 1 при любом J и K = 0 1  J t  0  K t 1  K t 0  J t  1  K t  0  .J Q t → Q t +1 0 → 0 0 → 1 1 → 0 1 → 1 Jt 1 * * Kt * * 1 Примечание – В таблице 4.2 символ «*» обозначает произвольное значение входной переменной. 4.2 Счётчики и делители частоты на их основе 4.2.1 Определение, назначение, классификация счётчиков. Счётчик – это дискретное устройство для подсчёта количества входных импульсов и хранения результата в виде двоичного кода. Счётчики используются для организации последовательного выполнения инструкций программы (программный счётчик); для подсчёта количества циклов выполнения операций; для образования адресов при обращении к внутренней памяти, для построения делителей частоты и пр. По способу подсчёта количества входных импульсов счётчики делятся на: – суммирующие – счёт в прямом направлении как при арифметическом 34 сложении; – вычитающие – счёт в обратном направлении как при арифметическом вычитании; – реверсивные – универсальные, используемые как для суммирования, так и для вычитания; – с произвольным счётом – реализуется любая последовательность счёта. Основной показатель счётчика – модуль счёта КСч (или коэффициент пересчёта) – это количество единиц на входе, которое возвращает счётчик в исходное состояние (ёмкость счётчика). Элементной базой при создании счётчиков служат преимущественно триггеры (например, счётный Т-триггер или универсальный JK-триггер). Необходимое количество триггеров для создания счётчика определяется как ближайшее большее целое число m по формуле m = log2КСч. Другим важным параметром счётчика является его быстродействие, характеризуемое частотой поступления на его вход счётных импульсов. В зависимости от характера связей между триггерами различают счётчики с последовательным и параллельным переносом. 4.2.2 Суммирующий счётчик с последовательным переносом. Рассмотрим на примере счётчика с КСч = 8. Он должен содержать m = = log2 8 = 3 триггера. Соответствующее количество разрядов счётчика равно трём. Старший разряд обозначим Q3, а младший – Q1. Выходные сигналы кодируются: у3 = Q3; у2 = Q2; у1 = Q1. Входной сигнал в рассматриваемом случае может быть только 1 (единица), так как нуль не изменяет состояние счётчика. На основании вышеизложенного составим таблицу переходов (смотри таблицу 4.3). Таблица 4.3 – Таблица переходов суммирующего счётчика с последовательным переносом хt 1 1 1 1 1 1 1 1 Q3t Q2t Q1t Q3t 1 Q2t 1 Q1t 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 35 Из таблицы видно, что частота переключения каждого следующего триггера уменьшается вдвое по сравнению с частотой переключения предыдущего триггера: f1 = fx / 2; f2 = f1 / 2 = fx / 4; f3 = f2 / 2 = f1 / 4 = fx / 8. Следовательно, счётчик можно построить как цепочку последовательно соединённых триггеров (как показано на рисунке 4.4), обладающих свойством деления частоты входного сигнала на два. Используем для этого JK-триггеры, работающие в счётном режиме, то есть управляемые со стороны синхровходов отрицательным перепадом (или задним фронтом) импульса. У1 х J TT1 C K Q1 Q1 У2 J TT2 C K Q2 Q2 У3 J TT3 C K Q3 Q3 1 Рисунок 4.4 – Функциональная схема суммирующего счётчика с последовательным переносом Работу счётчика рисунка 4.4 можно отобразить временными диаграммами рисунка 4.5. х У1 t У2 t У3 t t Рисунок 4.5 – Временные диаграммы суммирующего счётчика с последовательным переносом Рассмотренный счётчик получил название счётчика с последовательным переносом, так как установка старшего (следующего) разряда происходит только после того, как закончится переходный процесс в предыдущем разряде. Это существенно снижает быстродействие счётчика. Поэтому практическое применение нашли счётчики с параллельным (сквозным) переносом. В них выходной сигнал каждого предыдущего разряда передаётся одновременно на входы последующих разрядов. Тем самым уменьшается задержка и повышается быстродействие. 36 4.2.3 Для проектирования счётчиков с параллельным переносом существует специальный метод, называемый табличным методом синтеза. Он подробно рассмотрен в ПРИЛОЖЕНИИ Б на примере логического синтеза суммирующего трёхразрядного счётчика с последовательным счётом и параллельным переносом. Однако этот метод напрямую может быть применён для проектирования любых типов счётчиков, включая и недвоичные. К недвоичным относятся счётчики, у которых количество состояний не равно 2m, где m – количество триггеров в составе счётчика1. Соответствующий количеству состояний модуль счёта может принимать, например, значения КСч = 3, 5, 6, 7, 9. . . . , то есть не кратные 2m. Избыточные состояния, количество которых определяется как 2m – КСч, устраняются с помощью дополнительных связей между входами и выходами триггеров внутри счётчика. Ниже рассматривается синтез недвоичного счётчика, выступающего в роли основного компонента делителя частоты входного сигнала. Суть деления частоты дискретного сигнала заключается в следующем. Пусть имеется непрерывная последовательность импульсов с частотой fХ. Требуется получить тоже непрерывную последовательность импульсов, но уже с частотой fХ / 6. Это значит, что на выходе устройства, выполняющего роль делителя частоты, очередной импульс должен появляться только на каждый шестой импульс входной последовательности. Следовательно, у делителя частоты должен быть такой параметр, значение которого регулярно повторяется в момент прихода каждого шестого импульса. У счётчика в качестве такого параметра может выступать конкретное состояние, то есть любая, но конкретная комбинация значений разрядов (или выходных сигналов триггеров). Если взять за основу рассматриваемый пример делителя частоты на 6, то одну из возможных последовательностей смены состояний счётчика можно представить в виде таблицы 4.4, где x и у – входной и выходной сигналы делителя частоты, соответственно, а количество разрядов (или триггеров) определено по формуле m = log2КСч = log2 6 ≈ 3. Таблица 4.4 – Смена состояний счётчика делителя частоты fх входной последовательности импульсов на 6 x Q3 Q2 Q1 у 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Примечание – В таблице 4.4 в качестве повторяющейся комбинации значений разрядов счётчика взята комбинация Q1 = Q2 = Q3 = 1, хотя может быть взята и любая другая комбинация. 1 Соответственно, счётчики, у которых КСЧ = 2m, называются двоичными 37 В данном случае, Q1, Q2, Q3 являются входными, а у – выходной переменной узла, преобразующего состояние счётчика в выходной сигнал делителя частоты. Работа этого узла описывается логической функцией у = Q1*Q2*Q3. Синтезируем счётчик. Согласно условию он имеет КСЧ = 6, тогда количество триггеров будет равно m = log2КСЧ = log2 6 ≈ 3. Максимальное количество состояний счётчика – восемь, они приведены в таблице 4.5. Таблица 4.5 – Таблица переходов счётчика с последовательным порядком счёта xt 1 1 1 1 1 1 1 1 Q3 t 1 1 1 1 Q2 t 1 1 1 1 Q1 t 1 1 1 1 Q3 t+1 1 1 1 1 Q2 t+1 1 1 1 1 Q1 t+1 1 1 1 1 Выходной код счётчика 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Количество избыточных состояний равно двум, то есть 8 – 6 = 2. Исключённые избыточные состояния отмечены в таблице 4.5 инверсным цветом, что согласуется с данными таблицы 4.4. Тогда таблица переходов недвоичного счётчика примет вид таблицы 4.6. Таблица 4.6 – Таблица переходов недвоичного счётчика xt 1 1 1 1 1 1 Q3 t 1 1 Q2 t 1 1 1 Q1 t 1 1 1 Q3 t+1 1 1 Q2 t+1 1 1 1 Q1 t+1 1 1 1 Выходной код счетчика 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 По таблице переходов 4.6 для каждого триггеры составим карту переходов: Q1 t  Q1 t+1 Q3 Q1 10 – 10 10 01 01 – 01 Q2 t  Q2 t+1 Q3 Q2 Q1 01 – 10 10 00 01 – 11 Q3 t  Q3 t+1 Q3 Q2 Q1 00 – 10 01 00 11 – 00 Q2 В качестве элементной базы для построения схемы счётчика выбираем 38 JK-триггер. Для каждого входа каждого триггера составляем карту Карно, проставив в её клетках сигналы, которые необходимо подать на входы триггера для обеспечения его перехода, указанного в одноимённой клетке карты переходов: J1 t J2 t J3 t Q1  Q3 Q1 1 1 1   1 Q3  K1 t Q1 1 Q3 Q3  Q1  1  Q3 1 Q1    1 Q2 K3 t 1 Q2   Q2 K2 t   1 1  Q2 Q1 Q3 1 Q2    Q2 Минимизируем логические функции в картах Карно (смотри выделенные группы клеток) и получим функции возбуждения: J1 = 1; K1 = 1; J2 = Q1 + Q3; K2 = Q1; J3 = Q1Q2; K3 = Q1Q2. Построим схему делителя частоты, которая содержит схему счётчика и узла, описываемого логической функцией у = Q1*Q2*Q3 (смотри рисунок 4.6). Особые требования к используемому базису отсутствуют. & У1 fХ J T1 Q1 C K У2 1 J T2 Q2 C Q1 K У3 & J T3 Q3 C Q2 K Q3 СИ Рисунок 4.6 – Функциональная схема делителя частоты fУ 39 4.3 Контрольные вопросы для самопроверки 1 Что называется триггером? 2 Где могут применяться триггеры? 3 Каково назначение информационных входов триггера? 4 Каково назначение синхронизирующих входов триггера? 5 Какие типы триггеров Вам известны и в чём заключается их различие? 6 Что представляет из себя таблица переходов триггера? 7 Что представляет из себя матрица переходов триггера? 8 Каков алгоритм табличного метода синтеза счётчиков? 9 В чём отличие счётчиков с параллельным переносом от счётчиков с последовательным переносом? 10 Какие требования предъявляются к счётчикам, на базе которых строятся делители частоты входной последовательности импульсов? 40 5 ФУНКЦИОНАЛЬНЫЕ УЗЛЫ КОМПЬЮТЕРОВ (продолжение). ЛЕКЦИЯ 5 План лекции: а) дешифраторы и шифраторы (определение, назначение, алгоритм логического синтеза); б) мультиплексоры и распределители (определение, назначение, синтез). 5.1 Дешифраторы 5.1.1 Дешифратор (Decoder – DC) – это комбинационное устройство, позволяющее распознавать числа, представленные позиционным n-разрядным двоичным кодом. Дешифраторы применяются в компьютерах для расшифровки адресов ячеек запоминающих устройств, высвечивания букв и цифр в дисплеях и индикаторах и в других устройствах. 5.1.2 Рассмотрим DC двоичного кода с n входами. С помощью такого кода можно раскодировать NМакс = 2n чисел – максимальное количество. Следовательно, дешифратор должен иметь такое же количество выходов. Такой дешифратор называют полным. Дешифратор с меньшим, чем NМакс, количеством выходов называют неполным. Распознавание дешифратором двоичного кода заключается в том, что в зависимости от номера набора, поступившего на его вход, сигнал 1 появится только на одном определённом выходе, а на всех остальных выходах будут сигналы 0. Такой код называют унарным (унитарным), поэтому дешифратор – это преобразователь позиционного двоичного кода в унарный. Дешифраторы могут быть линейные и пирамидальные. Если принимать во внимание только логические характеристики, то любую практическую задачу можно решить с помощью линейного дешифратора. На рисунке 5.1 приведена схема линейного дешифратора трёхразрядного кода, построенная в соответствии с таблицей состояний 5.1, где yi – выходы дешифратора (i = 1, 2, ... , 8). Таблица 5.1 – Таблица состояний линейного дешифратора Входной код дешифратора 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 1 1 1 1 1 1 1 1 41 Q3 Q3 Q2 Q2 Q1 Q1         Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Рисунок 5.1 – Схема линейного дешифратора Схема на рисунке 5.1 составлена в соответствии с логическими функциями: Y1  Q1  Q2  Q3 ; Y2  Q1  Q2  Q3 ; Y3  Q1  Q2  Q3 ; Y4  Q1  Q2  Q3 ; Y5  Q1  Q2  Q3 ; Y6  Q1  Q2  Q3 ; Y7  Q1  Q2  Q3 ; Y8  Q1  Q2  Q3 . Рассмотренный DC реализован на трёхвходовых элементах И. В качестве источников нулевых сигналов (или инверсных значений входных логических переменных) используются инверсные выходы триггеров, то есть, дешифраторы часто работают совместно со счётчиками и регистрами. Однако, ряд таких физических характеристик, как нагрузочная способность триггера (число логических элементов, одновременно подключаемых к одному выходу триггера), число входов логических элементов И-НЕ (ИЛИ-НЕ) и др. вынуждает применять пирамидальные дешифраторы. 5.1.3 В основу синтеза пирамидального дешифратора положен нижеследующий принцип построения. 42 Шаг 1. Рассматривается конечное число младших разрядов входного кода, как правило, равное двум, и для имеющихся комбинаций составляется таблица истинности, в которой каждая комбинация является выходной переменной первой ступени дешифратора. Шаг 2. На основании полученной на шаге 1 таблицы истинности синтезируется первая ступень дешифратора. Шаг 3. К двум младшим разрядам входного кода добавляется один следующий старший разряд и анализируется его конъюнктивная связь с выходными переменными первой ступени (в любой форме), при этом каждая комбинация является выходной переменной второй ступени дешифратора. Шаг 4. На основании этого анализа синтезируется вторая ступень дешифратора. Шаг 5. К трём разрядам входного кода добавляется один следующий старший разряд . . . и т. д., пока не будет рассмотрен последний старший разряд входного кода дешифратора. Например, у трёхразрядного кода Q3, Q2, Q1, заданного таблицей 5.1, рассматриваем два младших разряда Q2, Q1, для которых составляем таблицу, учитывающую все имеющиеся комбинации (таблица 5.2). Таблица 5.2 – Таблица состояний первой ступени пирамидального дешифратора Q2 Q1 1 1 1 1 Комбинации 1 1 1 1 Z1 Z2 Z3 Z4 1 1 1 1 На основании данных таблицы 5.2 синтезируем первую ступень дешифратора, формирующую промежуточные переменные Zi, подаваемые на входы второй ступени. Далее к двум младшим разрядам добавляем следующий, старший, и рассматриваем код Q3, Q2, Q1 в соответствии с таблицей 5.1, где два младших разряда кода заменяем значениями Zi: Q3Z1 ; Q3Z2 ; Q3Z3 ; Q3Z4 ; Q3Z1 ; Q3Z2 ; Q3Z3 ; Q3Z4 . В результате схема пирамидального дешифратора будет иметь вид рисунка 5.2. Рассмотренный принцип синтеза пирамидального дешифратора позволяет использовать при его построении только двухвходовые конъюнкторы вне зависимости от разрядности дешифруемого кода. Другое достоинство заключается в уменьшении числа логических элементов, подключаемых одновременно к одному выходу триггера. Недостатком можно считать большое количество используемых логических элементов по сравнению с линейным дешифратором. 43 Q2 Q2Q1 Q1 Q3 Q3   Z1  Z2  Z3  Z4 Y1  Y2  Y3  Y4  Y5  Y6  Y7  Y8 Рисунок 5.2 – Схема пирамидального дешифратора 5.2 Шифраторы 5.2.1 Шифратор (Сoder – CD) – это комбинационное устройство, выполняющее функции преобразования унарного кода в двоичный код (число). При подаче 1 на один из входов (унарный код) на выходе формируется соответствующий двоичный код. Если число входов CD равно 2n, то число выходов – n. 5.2.2 Рассмотрим синтез схемы CD при n = 3. Таблица состояний имеет вид таблицы 5.3. Таблица 5.3 – Таблица состояний шифратора Входы Х1 1 Х2 1 Х3 1 Х4 1 Х5 1 Выходы Х6 1 Х7 1 Х8 1 Y1 1 1 1 1 Y2 1 1 1 1 Y3 1 1 1 1 44 Для каждого выхода составим логические функции по истинным значениям наборов: Y 1 = Х2 + Х 4 + Х6 + Х8 ; Y 2 = Х3 + Х4 + Х7 + Х8 ; Y 3 = Х5 + Х 6 + Х7 + Х 8 . Следует отметить, что приведённые функции являются результатом преобразований исходных функций, которые здесь не показаны. Исходные логические функции предлагается получить студентам самостоятельно. Таблица 5.3 – Таблица состояний шифратора Входы Х1 1 Х2 1 Х3 1 Х4 1 Х5 1 Выходы Х6 1 Х7 1 Х8 1 Y1 1 1 1 1 Y2 1 1 1 1 Y3 1 1 1 1 Реализуем CD на элементах базиса И-НЕ, для чего преобразуем функции к виду: Y1  X 2 * X 4 * X 6 * X 8 ; Y2  X 3 * X 4 * X 7 * X 8 ; Y3  X 5 * X 6 * X 7 * X 8 . Схема синтезируемого шифратора приведена на рисунке 5.3. X1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 & Y1 & Y2 & Y3 Рисунок 5.3 – Схема шифратора 5.3 Мультиплексоры 5.3.1 Мультиплексор – это устройство, которое подключает общую вы- 45 ходную шину к одному из входов в зависимости от управляющего сигнала, заданного двоичным кодом. Разрядность n управляющего сигнала определяет количество 2n информационных входов, с которых мультиплексор позволяет осуществлять приём информации. Принимая во внимание назначение мультиплексора, можно изобразить его в виде рисунка 5.4. Информационные входы X (x1. x2. x3….. xn) • • • Управляющий сигнал (УС) Мультиплексор Y Общая шина DC Рисунок 5.4 – Структура мультиплексора 5.3.2 Составим функциональную схему мультиплексора на четыре входа, на которые поступают данные (обозначим входы D1. D2. D3. D4). Для управления мультиплексором достаточно применить двухразрядный код Z (z1, z2). Управляющий сигнал расшифровывается дешифратором и с одного из четырёх выходов подаётся на один из четырёх ключей (элементы И), открывая последний для прохождения одного из четырёх информационных сигналов. Взяв за основу эти рассуждения, составим функциональную схему мультиплексора, приведённую на рисунке 5.5. D1 & D2 & 1 z1 УС z2 D3 & D4 & Y DС 0 1 2 1 3 СИ Рисунок 5.5 – Функциональная схема мультиплексора 46 Схема (элемент) ИЛИ объединяет четыре выхода ключей в один канал для передачи сигналов D1, D2, D3, D4. Для повышения надёжности и согласования работы мультиплексора с другими узлами единого дискретного устройства осуществляется синхронизация. 5.4 Распределители 5.4.1 Распределитель – это устройство, которое передаёт информационный сигнал, поступающий на единственный вход х, на один из выходов yi в зависимости от управляющего сигнала (УС), заданного двоичным кодом. Разрядность n управляющего сигнала определяет количество 2n выходов, с которыми распределитель связывает информационный вход. Принимая во внимание назначение распределителя, можно изобразить его в виде рисунка 5.6. Информационный вход Распределитель • • • Выходы Y (y1, y2, y3,…, yS) X Управляющий сигнал (УС) DC Рисунок 5.6 – Структура распределителя 5.4.2 Составим функциональную схему распределителя на четыре выхода y1, y2, y3, y4, на которые передаётся информационный сигнал Х. Для управления распределителем достаточно применить двухразрядный код Z (z1, z2), который подаётся на вход дешифратора. Управляющий сигнал расшифровывается дешифратором, каждый выход которого связан с одним из четырёх ключей. Выходной сигнал дешифратора, соответствующий конкретной кодовой комбинации управляющего сигнала, открывает соответствующий ключ для прохождения информационного сигнала на один из четырёх выходов. Взяв за основу эти рассуждения, составим функциональную схему распределителя, приведённую на рисунке 5.7. Для повышения надёжности и согласования работы распределителя с другими узлами единого дискретного устройства осуществляется синхронизация. 47 & & Х & & z1 УС z2 y1 y2 y3 y4 DС 0 1 2 1 3 СИ Рисунок 5.7 – Функциональная схема распределителя 5.5 Контрольные вопросы для самопроверки 1 Дайте определение и назначение дешифратора. 2 Дайте определение и назначение шифратора. 3 Дайте определение и назначение мультиплексора. 4 Дайте определение и назначение распределителя. 5 Дайте определение унарного (унитарного) кода. 6 Какой дешифратор считае6тся полным? 7 Перечислите причины, которые обуславливают создание пирамидальных дешифраторов. 8 Поясните, как формируются ступени пирамидального дешифратора. 9 Перечислите основные функциональные узлы, входящие в состав мультиплексора. 10 Перечислите основные функциональные узлы, входящие в состав распределителя. 48 6 ФУНКЦИОНАЛЬНЫЕ УЗЛЫ КОМПЬЮТЕРОВ (продолжение). ЛЕКЦИЯ 6 План лекции: а) регистры (определение, назначение, классификация, синтез); б) сумматоры (определение, назначение, алгоритм логического синтеза); в) автоматические генераторы непрерывной последовательности прямоугольных импульсов. 6.1 Регистры 6.1.1 Регистром называют устройство, осуществляющее приём, хранение, некоторые логические преобразования и выдачу двоичных кодов. В отличие от запоминающих устройств в регистрах информация хранится не более нескольких тактов. Запоминающими элементами в регистрах служат триггеры, количество которых равно количеству разрядов хранимых кодов. Регистры подразделяют на: – параллельные регистры, имеющие только параллельный интерфейс – ввод-вывод только в параллельном коде (в основном применяются в качестве сверхоперативной памяти, поэтому называются регистрами памяти); – последовательные регистры, имеющие только последовательный интерфейс, (в основном служат для выполнения логических операций над кодовыми комбинациями, в частности, осуществляют сдвиг кодовой комбинации на один – несколько разрядов, поэтому называются регистрами сдвига); – параллельно-последовательные регистры (например, запись кода в параллельном интерфейсе, а считывание – в последовательном интерфейсе, и наоборот); – реверсивные регистры. В регистрах памяти код записывается или считывается за один такт, а в регистрах сдвига – за n тактов, где n – разрядность кода. 6.1.2 Рассмотрим принцип функционирования и построим схему параллельного четырёхразрядного регистра. Он содержит четыре триггера, в качестве которых применяются, преимущественно RS-триггеры. Для параллельного ввода на вход каждого из четырёх триггеров подаётся соответствующий разряд кода X (x1. x2. x3. x4). Для установки регистра в нулевое исходное состояние (перед записью) нужно предусмотреть подачу сигнала TR («Сброс» или «Уст. нуля») на входы R триггеров. Управление режимами работы регистра осуществляется с помощью комбинационных схем – ключей, размещённых на входах и выходах. Они позволяют производить запись кода при подаче сигнала «Запись» (Зп.) или считывание кода при подаче сигнала «Считывание» (Сч.). Схема параллельного регистра, построенная на RS-триггерах с учётом принципа его работы, приведена на рисунке 6.1. 49 x1  S T1 R x2  S T2 R  x3 S T3 R x4  S T4 R Q1  у1 Q1 Q2  у2 Q2 Q3  у3 Q3 Q4  у4 Q4 TR Запись Сброс (Уст. 0) Считывание Рисунок 6.1 – Схема параллельного регистра Перед записью кодовой комбинации все триггеры устанавливаются в исходное нулевое состояние подачей сигнала TR. Для записи входной информации подаётся импульс «Запись», открывающий входные ключи. При этом сигналы на входах xi должны уже присутствовать. Записанная кодовая комбинация сохраняется, пока не будет подан сигнал TR. Для считывания записанной кодовой комбинации подают сигнал «Считывание», при этом записанная в регистре кодовая комбинация сохраняется. Последовательные регистры запоминают кодовые комбинации, представленные последовательным кодом. Они состоят из последовательно соединённых триггеров. Записью кодовой комбинации управляют тактовые импульсы. На каждый такт происходит сдвиг содержимого предыдущих триггеров в последующие. На рисунке 6.2 изображена схема 4-разрядного регистра, управляемого последовательностью тактовых импульсов. Выход у4 у3 у2 у1 Разряд 4 Разряд 3 Разряд 2 Разряд 1 Вход Такт Рисунок 6.2 – Структурная схема последовательного регистра 50 Запись кодовой комбинации в регистр производится, начиная со старшего разряда. 4-разрядная кодовая комбинация запишется за четыре такта. Например, запись кодовой комбинации 1011 можно смоделировать так, как показано на рисунке 6.3. До записи кодовой комбинации регистр устанавливается в нулевое состояние подачей тактовых импульсов, число которых равно числу разрядов. у4 1 у3 1 у2 1 1 у1 1 1 1 ← Разряды 1011 011 11 1 1 2 3 4 Т а к т Рисунок 6.3 – Схема записи кодовой комбинации в последовательный регистр После записи кодовой комбинации её можно считать либо с последовательного интерфейса (основной выход) за четыре такта, либо с параллельного интерфейса. При считывании с параллельного интерфейса подавать тактовые импульсы не нужно. Последовательные регистры устанавливают на вход устройств, связанных с другими устройствами однопроводной линией связи. Их использование уменьшает быстродействие средств передачи информации. Параллельно-последовательные регистры сочетают в себе свойства как параллельных, так и последовательных регистров. Они позволяют записывать информацию как в параллельном, так и последовательном коде и могут использоваться для преобразования кодов из параллельного в последовательный и наоборот (смотри рисунок 6.4). Выходы параллельного интерфейса Выход последовау4 тельного интерфейса Разряд у3 у2 у1 4 Разряд 3 Разряд 2 Разряд 1 х4 х3 х2 Вход последовательного интерфейса Такт х1 Входы параллельного интерфейса Рисунок 6.4 – Структурная схема параллельно-последовательного регистра Реверсивные регистры обеспечивают сдвиг записанной кодовой комбинации в сторону как младшего, так и старшего разряда. Это оказывается необ- 51 ходимым при реализации арифметических операций над числами, когда все вычисления сводятся к одному действию – сложению прямых и обратных сдвинутых влево или вправо на конечное число разрядов кодовых комбинаций. 6.2 Сумматоры 6.2.1 Всё многообразие математических операций (вычитание, умножение, деление, вычисление тригонометрических функций, извлечение корня и т.д.) можно свести к единственной операции сложения прямых и дополнительных сдвинутых влево или вправо на то или иное число разрядов кодов чисел. Поэтому одним из основных узлов арифметических устройств компьютеров является сумматор. Сумматоры многоразрядных чисел, которыми оперирует компьютер, составляются из одноразрядных сумматоров, выполняющих операцию сложения двух одноразрядных чисел. 6.2.2 Рассмотрим сумматор, выполняющий сложение значений ai и bi разряда i двух двоичных многоразрядных чисел А и В с учётом переноса pi-1 из предыдущего (i - 1)-го разряда и переноса pi+1 в следующий (i +1)-й разряд, как показано схематично на рисунке 6.5. pi +1 А + В • • • n -1 pi -1 ai • • • • • • bi • • • • • • i+1 i i-1 • • • Номера разрядов суммируемых чисел 1 Рисунок 6.5 – Схема сложения двух одноразрядных чисел с учётом переносов С учётом правил арифметического сложения можно заключить, что рассматриваемый сумматор должен иметь: – три входа, на которые подаются сигналы, соответствующие значениям чисел А и В в i - м разряде (ai и bi), и сигнал, соответствующий значению переноса из предыдущего разряда (pi -1); – два выхода, на одном из которых формируется сигнал, соответствующий значению суммы в i - м разряде (si), а на втором формируется сигнал, соответствующий значению переноса в следующий старший разряд (pi+1). В результате модель процедуры арифметического суммирования можно отобразить с помощью таблицы 6.1, на основании данных которой формируются логические функции, описывающие функционирование сумматора. 52 Таблица 6.1 – Суммирование двух одноразрядных двоичных чисел pi -1 1 1 1 1 Сложение ai bi 1 1 1 1 1 1 1 1 Si pi+1 1 1 1 1 1 1 1 1 Запишем логические функции, опуская процедуру их минимизации (процедуру минимизации рекомендуется выполнить студентам самостоятельно): S i  pi 1  ai  bi  pi 1  ai  bi  pi 1  ai  bi  pi 1  ai  bi ; pi 1  ai  bi  pi 1  ai  pi 1  bi . Реализуем сумматор на элементах базиса И-НЕ (смотри рисунок 6.6), преобразовав полученные логические функции к виду: S i  pi 1  ai  bi  pi 1  ai  bi  pi 1  ai  bi  pi 1  ai  bi ; pi 1  ai  bi  pi 1  ai  pi 1  bi . ai bi pi -1 & & & & si & & & & & & & pi +1 & Рисунок 6.6 – Функциональная схема одноразрядного сумматора 53 6.2.3 Используя одноразрядный сумматор, можно построить суммирующее устройство для сложения многоразрядных двоичных чисел А и В. Различают многоразрядные последовательные и параллельные сумматоры. Последовательный многоразрядный сумматор (смотри рисунок 6.7) состоит из одноразрядного сумматора, на входы ai и bi которого из сдвигающих регистров подаются по тактам разряд за разрядом кодовые комбинации чисел А и В, начиная с младшего разряда. Если время задержки элемента задержки равно одному такту (например, использован D-триггер), то сигнал переноса из предыдущего разряда, сформированный в предыдущем такте, поступит на нижний вход сумматора только в очередном такте. В результате на выходе S разряд за разрядом в последовательном интерфейсе будет формироваться двоичное число, равное сумме А и В, которое записывается в сдвигающий регистр. Сдвигающий регистр А ai Сдвигающий регистр В bi S pi -1 Si Сдвигающий регистр S pi+1 P Элемент задержки Рисунок 6.7 – Структурная схема последовательного сумматора Достоинством последовательного сумматора является простота схемы. Недостатком является никое быстродействие, так как для сложения nразрядных чисел требуется (n + 1) такт работы устройства (с учётом возможного переполнения). Параллельный сумматор выполняет процедуру сложения двух многоразрядных чисел значительно быстрее, чем последовательный. В нём процедура сложения производится за один такт во всех n разрядах чисел, подаваемых в параллельном интерфейсе. Для этого параллельный сумматор строят из n одноразрядных сумматоров. Схемы таких сумматоров достаточно сложные, поэтому здесь не приводятся. 6.3 Автоматические генераторы непрерывной последовательности прямоугольных импульсов 6.3.1 Генераторы импульсов применяются для синхронизации работы цифровых устройств и для задания темпа выполнения операций. Ниже рассматриваются генераторы, построенные на основе логических элементов. Для задания режима стабильной работы и непрерывной генерации импульсов в генера- 54 торы вводят так называемые обратные связи – отрицательные и положительные, используя такие пассивные элементы, как резисторы, конденсаторы и кварцевые резонаторы. 6.3.2 Отрицательная обратная связь (ООС) вводится с помощью резистора, связывающего выход и вход одного или нескольких последовательно соединённых логических элементов. В качестве последних применяют логические элементы, обладающие свойством инверсии входного сигнала, в частности, НЕ, И-НЕ, ИЛИ-НЕ. Сам термин «отрицательная обратная связь» означает, что выходной сигнал элемента (или последовательности элементов) подаётся на его вход в обратной полярности. В частности, на рисунке 6.8 показан пример организации отрицательной обратной связи с помощью резистора R в элементе И-НЕ. Входной сигнал х инвертируется элементом и с его выхода через резистор снова подаётся на вход (известно, что такие пассивные элементы, как резистор, конденсатор, не обладают свойством инверсии сигнала). R & х y Рисунок 6.8 – Пример организации ООС Ввод отрицательной обратной связи позволяет изменить режим работы логического элемента с ключевого на усилительный. Это является одним из условий создания автоматического генератора. 6.3.3 Положительная обратная связь (ПОС) вводится с помощью конденсатора или кварцевого резонатора, связывающего выход и вход чётного числа нескольких последовательно соединённых логических элементов. В частности, на рисунке 6.9 показан пример организации положительной обратной связи с помощью конденсатора С в цепочке из дух последовательно включённых элементов И-НЕ. С + х + & & – + y Рисунок 6.9 – Пример организации ПОС Ввод положительной обратной связи, позволяющей задать режим непрерывной генерации импульсов, является вторым условием создания автоматического генератора. 55 6.3.4 Рассмотрим ряд генераторов импульсов, в которых реализованы оба рассмотренных выше условия. В генераторе, собранном по схеме рисунка 6.10, ООС организована с помощью резистора R, охватывающего три последовательно включённых инвертора. ПОС реализуется за счёт конденсатора С, охватывающего два инвертора. R С – + – + Выход Рисунок 6.10 – Схема генератора на трёх инверторах В генераторе на рисунке 6.11 используется два инвертора. Назначение резистора и конденсатора то же. С R + – + Выход Рисунок 6.11 – Схема генератора на двух инверторах В генераторах, схемы которых приведены на рисунках 6.10 и 6.11, период Т следования импульсов определяется постоянной времени τ = R×С, причём Т = α×τ , где α = 1 ÷ 2 и зависит от технологии изготовления инверторов. Более стабильны в работе генераторы импульсов, в которых ООС вводится в каждом инверторе, как показано на рисунке 6.12. «Гибкими» в смысле задания, перенастройки и подстройки требуемой частоты следования импульсов являются генераторы с двумя конденсаторами. Схема одного из подобных генераторов импульсов приведена на рисунке 6.13. 56 С R2 R1 – + Выход + Рисунок 6.12 – Схема генератора на двух инверторах и с двумя цепями ООС С1 R2 R1 С2 + – – + Выход Рисунок 6.13 – Схема генератора с двумя времязадающими конденсаторами Генераторы импульсов с кварцевой стабилизацией частоты выполняются обычно путём включения кварцевого резонатора на место времязадающей ёмкости. Удобны в этом смысле схемы с одной времязадающей ёмкостью – рисунки 6.10 – 6.12, хотя стабилизация частоты возможна и при замене одной из двух ёмкостей на рисунке 6.13. Пример схемы генератора импульсов с кварцевой стабилизацией частоты показан на рисунке 6.14. Кварцевый резонатор R + – + Выход Рисунок 6.14 – Схема генератора импульсов с кварцевым резонатором 6.4 Контрольные вопросы для самопроверки 1 Дайте определение и назначение регистров. 2 Какие типы регистров Вам известны и каковы их отличительные особенности? 3 Опишите процесс записи кодовой комбинации в параллельный регистр и считывания записанной кодовой комбинации. 57 4 Опишите процесс записи кодовой комбинации в последовательный регистр. 5 Постройте логическую модель выполнения арифметической операции суммирования двух одноразрядных чисел с учётом переносов из младшего разряда и в старший разряд. 6 Опишите процесс арифметического сложения двух многоразрядных двоичных чисел в последовательном сумматоре. 7 Перечислите основные условия, обеспечивающие режим автоматической генерации непрерывной последовательности прямоугольных импульсов в генераторах, построенных на основе логических элементов. 8 Что такое «отрицательная обратная связь» и как она реализуется? 9 Что такое «положительная обратная связь» и как она реализуется? 58 7 АРИФМЕТИЧЕСКИЕ ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ. ЛЕКЦИЯ 7 План лекции: а) позиционные системы счисления; б) правила перевода чисел из одной системы счисления в другую; в) двоичная арифметика; г) формы представления чисел в позиционной системе счисления; д) кодирование числовой информации (прямой, обратный и дополнительный коды чисел). Арифметические операции с применением дополнительных кодов. 7.1 Позиционные системы счисления 7.1.1 Под системой счисления понимают способ представления любого числа с помощью некоторого алфавита символов, называемых цифрами. Преимущественное распространение получили позиционные системы счисления, в которых одна и та же цифра имеет различное значение, определяющееся позицией цифры в последовательности цифр, изображающей число. Это значение меняется в однозначной зависимости от позиции, занимаемой цифрой, по некоторому закону. Количество q различных цифр, употребляемых в позиционной системе, называется её основанием. Эти цифры обозначают q целых чисел, обычно 0,1,...,(q - 1). Например, используются: 1) в десятичной системе счисления 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, то есть q10 = 10; (7.1) 2) в двоичной системе счисления 2 цифры: 0, 1, то есть q2 = 2; (7.2) 3) в восьмеричной системе счисления 8 цифр: 0, 1, 2, 3, 4, 5, 6, 7, то есть q8 = 8; (7.3) 4) в шестнадцатеричной системе счисления 16 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, то есть q16 = 16, (7.4) где введены обозначения: 10 – A, 11 – B, 12 – C, 13 – D, 14 – E, 15 – F. 7.1.2 Десятичная система счисления используется в повседневной практике и для внешнего представления результатов вычислений с помощью периферийных устройств отображения информации (мониторы, принтеры и т.п.). Двоичная система счисления используется в цифровой технике для внутреннего представления, обработки и хранения информации. Это связано с тем, что цифровые устройства строится из элементов, имеющих два устойчивых состояния, одно из которых условно принимается за 1, другое – за 0. Шестнадцатеричная 59 система счисления применяется для сокращения длины записи при визуальном отображении кодов адресов и при записи некоторых программ. 7.1.3 Любое число Х в любой позиционной системе счисления с основанием q может быть представлено в виде полинома от основания q: X = kn×qn + kn-1×qn-1 +...+ k1×q1 + k0×q0 + k–1×q–1 + k–2×q–2 +...+ k-m×q-m, (7.5) где в качестве коэффициентов ki могут стоять любые из q цифр, используемых в системе счисления. Полином (7.5) в общем случае носит название ч и с л а с ф и к с и р о в а н н о й т о ч к о й , но имеет две разновидности: 1) X = kn×qn + kn-1×qn-1 + ... + k1×q1 + k0×q0 – число с ф и к с и р о в а н н о й т о ч к о й , то есть целое число; 2) X = k–1×q–1 + k–2×q–2 +...k-m×q-m – число с ф и к с и р о в а н н о й з а п я т о й , то есть правильная дробь. Полином (7.5) можно использовать для перевода чисел из одной системы счисления в другую, если его компоненты ki и q представить в новой системе счисления (примеры приведены ниже). 7.1.4 Принято представлять числа в виде последовательности цифр: kn ... k1 k0 , k –1 k –2 ... k-m, (7.6) целая часть числа дробная часть числа где запятая (точка) отделяет целую часть от дробной. Позиции цифр, отсчитываемые от точки влево и вправо, называют разрядами. «Вес» соседнего слева разряда по отношению к любому исходному в q раз больше «веса» исходного разряда. Веса разрядов соответствуют значению множителя qi в (7.5). Представление в виде числа с фиксированной точкой (или ее разновидности – с фиксированной запятой) влияет на диапазон представляемых чисел и их точность. 7.1.5 В двоичной системе счисления (q2 = 2) цифры ki могут быть равны либо 0, либо 1. Например: 1) положительное целое двоичное число (n = 5) 110111( 2 ) = 1×25 + 1×24 + 0×23 + 1×22 + 1×21 + 1×20, как следует из приведённого разложения его по степеням q = 2, соответствует десятичному числу 55( 10 ) ; 2) положительное целое десятичное число (n = 2) 113( 10 ) = 1×(1010) 2 + 1×(1010) 1 + 11×(1010) 0 , где q = 1010, 60 соответствует двоичному числу 1110001( 2 ) ; 3) положительное дробное двоичное число 110111,101(2) =1×25 + 1×24 + 0×23 + 1×22 + 1×21 + 1×20 + 1×2–1 + 0×2–2 + 1×2–3 соответствует дробному десятичному числу 55,625(10) . В шестнадцатеричной системе счисления число В2Е.4( 16 ) = 11 × 16 2 + 2 × 16 1 + 14 × 16 0 + 4 × 16 -1 = 2862.25( 10 ) . 7.2 Правила перевода чисел из одной системы счисления в другую 7.2.1 В общем виде правила перевода чисел из одной системы счисления в другую формулируются следующим образом: а) для перевода ц е л о г о ч и с л а (или целой части дробного числа) из одной системы счисления в другую нужно выполнить в исходной системе последовательное деление числа и получаемых частных на основание новой системы, а затем записать полученные остатки в обратном порядке, представляя их в новой системе; б) для перевода п р а в и л ь н о й д р о б и (или дробной части числа) из одной системы счисления в другую нужно выполнить в исходной системе последовательное умножение исходной и промежуточных дробей на основание новой системы, выделяя при этом каждый раз целые части, а затем записать полученные целые части в прямом порядке, представляя их в новой системе. 7.2.2 Пример 1. Перевести из двоичной системы счисления в десятичную число 11101.01101( 2 ). В данном случае двоичная система является исходной, а десятичная – новой, при этом основание новой системы (q = 10) в исходной системе 10( 10 ) = 1010 ( 2 ) . Целая часть числа Дробная часть числа 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0(2) =2(10)_ 1 0 0 1(2) = 9(10) 4 (10 ) = 1 0 1 1 1 0 1 = 29 (10 ) 0 ( 10 ) = 0 0 6 ( 10 ) = 1 1 2 ( 10 ) = 0 1 5 ( 10 ) = 1 0 0 . 0 1 1 0 (2) 0 0 1 0 (2) 1 0 1 0 (2) 0 1 1 0 (2) 1 0 1 1 (2) 0 0 1 1 1 1 1 1 1 1 1 0 . 0 1 1 0 1 = 0 . 4 0 6 2 5( 10 ) 61 и само число 11101.01101( 2 ) = 29.40625( 10 ) . Тот же результат получается и при использовании полинома (7.5): 11101.01101( 2 ) = 1× 24 + 1× 23 + 1× 22 + 0× 21 + 1× 20 + + 0 × 2-1 + 1× 2-2 + 1× 2-3 + 0 × 2-4 + 1× 2-5 = 29.40625( 10 ) . 7.2.3 Пример 2. Перевести из десятичной системы счисления в двоичную число 38.15(10 ) . В данном случае десятичная система является исходной, а двоичная – новой, при этом основание новой системы в исходной q2 = (2)10 . Целая часть числа Дробная часть числа _ 3 8 2 3 8 _ 1 9 2 1 8 _ 9 2 1 8 _ 4 2 1 4 _ 2 2 38 (10) = 1 0 0 1 1 0( 2 1 2 ) и само число 38.15 ( 10 )  100110.0010 ( 2 ) . 0 . 1 5 2 3 0 2 6 0 2 1 2 0 2 4 0 0. 1 5( 1 0 )   0. 0 0 1 0 ( 2 ) Примечание – Процесс перевода правильной дроби (или дробной части числа) нужно продолжать до тех пор, пока промежуточные дробные части не обратятся в нуль (как это имело место в первом примере), или не обнаружится период, или пока не будет достигнута желаемая точность (во втором примере перевод сделан с точностью до четвёртого знака после точки). Тот же результат получается и при использовании (7.5): 38.15 ( 10 ) =11×(1010) 1 + 1000×(1010) 0 + 1×(1010) - 1 + 101×(1010) - 2   100110.0010 ( 2 ) . 7.2.4 Пример 3. Перевести из десятичной системы счисления в шестнадцатеричную число 396.05(10). В данном случае десятичная система является исходной, а шестнадцатеричная – новой, при этом основание новой системы в исходной q16 = 16(10) . 62 Целая часть числа Дробная часть числа _ 3 9 6 1 6 3 8 4 _ 2 4 1 6 1 2( 1 0 ) = С ( 1 6 ) 1 6 1( 1 0 ) =1 ( 1 6 ) 8( 1 0 ) =8 ( 1 6 ) 0(16) = С(16) = С(16) = 3 9 6 (10 ) = 1 8 С(16 0 . 0 1 0(10) 8 1 12 ( 1 0 ) 8 1 12 ( 1 0 ) 8 5 6 6 6 0. 0 5( 1 0 ) = = 0. 0 С С ( 1 6 ) ) и само число 396.05 ( 10 )  18С.0СС ( 16 ) . Чтобы воспользоваться для перевода (7.5), нужно знать правила арифметических действий над шестнадцатеричными числами, поэтому такой вариант перевода не рекомендуется применять. 7.2.5 Пример 4. Перевести из шестнадцатеричной системы счисления в десятичную число F9E.A8( 16 ) . В данном случае шестнадцатеричная система является исходной, а десятичная – новой, при этом основание новой системы (q10 = 10) в исходной системе 10( 10 ) = А( 16 ). В рассматриваемом примере, в отличие от предыдущего, проще выполнить перевод с использованием полинома (7.5). Тогда получается F9E.A8 ( 16 ) = 15 × 16 2 + 9 × 16 1 + 14 × 16 0 + 10 × 16 –1 + 8 × 16 –2 = = 3998.65625 ( 10 ) ; 7.2.6 Пример 5. Перевести шестнадцатеричное число в двоичное и наоборот. Для этого существуют простые правила, отличающиеся от рассмотренных ранее. При переводе шестнадцатеричного числа в двоичное достаточно заменить каждую цифру этого числа соответствующим четырёхразрядным двоичным числом, отбрасывая ненужные нули в старших разрядах целой части и в младших разрядах дробной части: 1010 1110 АЕ3.0F ( 16 ) = А Е 0011 0000 1111 3  F ( 16 ) = = 101011100011.00001111 ( 2 ) ; 1D.9C ( 16 ) = 1 D 0001 1101  9 1001 C 1100 ( 16 ) = 11101.100111 ( 2 ) . 63 При переводе двоичного числа в шестнадцатеричное поступают следующим образом: двигаясь от точки влево и вправо разбивают двоичное число на группы по четыре разряда (тетрады), дополняя при необходимости нулями крайние левую и правую тетрады. Затем каждую тетраду заменяют шестнадцатеричной цифрой: 100110.0010011 ( 2 ) = 0010 0110  0010 0110 ( 2 ) = 26.26 ( 16 ) ; 2 6 2 6 11101.01101 ( 2 ) = 0001 1101 0110 1000 ( 2 ) = 1D.68 (16 ) . 1 D 6 8 Примечание – Любое число х можно перевести из шестнадцатеричной системы счисления в десятичную и обратно, применив промежуточное преобразование: Х (16 ) → х ( 2 ) → х ( 10 ) или х ( 10 ) → х ( 2 ) → х ( 16 ). 7.2.7 Одно из применений шестнадцатеричной системы счисления в вычислительной технике – это индикация адресов ячеек внутренней памяти, куда входят оперативное запоминающее устройство (ОЗУ) и постоянное запоминающее устройство (ПЗУ). Каждая из М ячеек, обладающая ёмкостью N бит двоичных разрядов, имеет свой адрес. Адреса начинаются с 0 и заканчиваются (М – 1). Например, адрес первой ячейки 000000 h , второй – 000001 h и т.д., где латинская буква «h» указывает на принадлежность числа шестнадцатеричной системе счисления (hex). 7.3 Двоичная арифметика 7.3.1 Правила выполнения арифметических операций над числами для позиционной системы счисления с любым основанием S задаются таблицами сложения, вычитания и умножения одноразрядных чисел. Ниже представлены таблицы 7.1 – 7 .3 для двоичной арифметики. Таблица 7.1 – Сложение 0+0=0 0+1=1 1+0=1 1+1=0 плюс единица переноса в старший разряд Таблица 7.2 – Вычитание 0–0=0 1–0=1 1–1=0 10 – 1 = 1 с учётом заёма единицы из старшего разряда Таблица 7.3 – Умножение 0×0=0 0×1=0 1×0=0 1×1=1 Сложение двух единиц в любом разряде числа даёт единицу переноса в следующий, старший разряд. При займе единицы из следующего старшего разряда она даёт две единицы в текущем разряде. Умножение многоразрядных чисел производится путём образования частичных произведений и последующего 64 их суммирования. 7.3.2 Пример 6. Вычислить в двоичной системе счисления x = (a + b× c) / (d – e), где a = 10010111,001 ( 2 ); b = 1011,11 ( 2 ); c = 110 ( 2 ); d = 100010 ( 2 ); e = 11101,1 ( 2 ). Решение: а) d – e = 100,1; _ 1 0 0 0 1 0 , 0 1 1 1 0 1 , 1 0 0 0 1 0 0 , 1 б) b × c = 1000110,10; 1 0 1 1, 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0, × 1 1 1 0 0 0 1 1 0 в) a + b × c = 11011101,101; + 1 0 0 1 0 1 1 1 , 1 0 0 0 1 1 0 , 1 1 0 1 1 1 0 1 , 0 0 1 1 0 1 0 1 г) x = (a + b × c) / (d – e) = 110001,01. _ 1 1 0 1 1 0 0 1 _ 1 0 0 1 0 0 _ 1 1 0 1, 1. 0 1 1 0 0, 1. 1 1 0 0 0 1, 0 1 1 1 0 1 0 1 1 1 0 0 1 _ 1 0 0 1 1 0 0 1 Приведённый пример показывает, что двоичная система очень удобна для вычислений. Операция умножения сводится к простому сложению со сдвигом множимого по позиции. Операция деления сводится к вычитанию со сдвигом делителя. 65 7.4 Формы представления чисел в позиционной системе счисления 7.4.1 Существует две формы записи чисел: форма FIXED – с фиксированной точкой (запятой) и FLOAT – с плавающей точкой (запятой). Форма FIXED характеризуется тем, что местоположение точки фиксируется либо перед старшим разрядом (число с ф и к с и р о в а н н о й з а п я т о й , то есть правильная дробь), либо после младшего разряда числа (число с ф и к с и р о в а н н о й т о ч к о й , то есть целое число). В ряде ЭВМ первых поколений преимущественно применялась данная форма. В принципе, все вычисления над числами можно выполнить, представив их в форме FLOAT. Но есть задачи, где выгоднее использовать форму FIXED. В этом случае быстродействие процессора увеличивается. Форма FLOAT происходит от так называемой полулогарифмической формы для записи макро- и микровеличин. Например, скорость света С = 3×105 км /с; масса одного атома водорода m = 1,66×10 –24 г. В общем виде форма FLOAT записывается х =  m × q  P, где (7.7) q – основание системы счисления; m – мантиса числа; р – порядок. В вычислительной технике применяется нормализованный вид FLOAT. При использовании этого вида нужно соблюдать условие: q – 1  m < 1, (7.8) (мантиса меньше единицы и первая цифра дробной части – значащая, то есть отличная от нуля). Например, числа 128,36 и 0,0078 будут представлены в нормализованном виде FLOAT: 0,12836 ×10 3 и 0,78 ×10 –2. Правила выполнения арифметических операций над числами, представленными в форме FLOAT, формулируются следующим образом: а) сложение: пусть требуется вычислить z = x + y , где x = m X × 10 Px ; y = m Y × 10 Py ; для этого: – выравниваются порядки чисел по p Max = max ( p X , p Y) за счёт перемещения мантисы (сдвига) относительно запятой; – алгебраически складываются мантисы; – результат нормализуется, приводится к виду (7.8), при этом может возникнуть порядок нормализации; – порядок результата p Z = p Max + p Нормализации . 66 б) вычитание: вычитание сводится к алгебраическому сложению уменьшаемого с вычитаемым, взятым с обратным знаком, поэтому не требует специального объяснения; в) умножение: нужно перемножить мантисы, нормализовать их произведение, а порядок будет p Z = p X + p Y + p Нормализации ; г) деление: z = x / y = (m X × q Px) / (m Y × q Py ) = (m X / m Y) ×q Px – Py = = m Z × q Pz и, если нужно, нормализовать m Z. 7.4.2 Пример 7. Вычислить z = x + y, где x = 0,5123×10 2, y = 0,86 ×10 2. Если порядки равны, то выравнивание не производится. m Z = m X + m Y = 0,5123 + 0,86 = 1,3723 , получили ненормализованную мантису. Нормализуем её и получим m Z = 0 , 13723 × 10 1 , где p Нормализации = + 1 , тогда p Z = p Max + p Нормализации = 2 + 1 = 3 , и в итоге имеем z = x + y = m Z × 10 Pz = 0 , 13723 × 10 3 . 7.4.3 Пример 8. Вычислить z = x + y, –1 y = 0 , 26 × 10 . Выравниваем порядки: где x = 0 , 2567 × 10 2 , p Max = p X = 2 , тогда x = 0 , 2567 × 10 2 , y = 0 , 00026 × 10 2 ; m Z = m X + m Y = 0 , 2567 + 0 , 00026 = 0 , 25696 (мантиса получилась в нормализованном виде). В итоге z = x + y = m Z × 10 Pz = 0 , 25696 × 10 2 . 7 .5 Кодирование числовой информации (прямой, обратный и дополнительный коды чисел). Арифметические операции с применением дополнительных кодов 7.5.1 Обратный и дополнительный коды. При выполнении привычных алгебраических операций используются числа со знаком « + » и « – ». В компь- 67 ютерах коды чисел представляются в специальной беззнаковой форме. С этой целью введены обратный и дополнительный коды чисел. Тогда операция вычитания заменяется операцией сложения прямого кода уменьшаемого и дополнительного кода вычитаемого. Код числа со знаком вида (7.6) называется прямым кодом. В таком виде числа представляются в привычном для нас виде. Если система счисления двоичная, то для знака достаточно выделить один дополнительный двоичный разряд. Знак может принимать одно из двух значений: « + » обозначается 0 и « – » обозначается 1. Пусть имеется некоторое устройство (регистр, ячейка памяти компьютера), содержащее k разрядов в системе счисления q . Первый слева (старший) разряд хранит признак знака числа. В частности, если в нём 0 , то число положительное и в устройстве хранится прямой код числа. В качестве признака отрицательного числа используется старшая цифра базиса системы счисления (для q = 2 это 1; для q = 10 это 9 ; для q = 16 это F). В остальных разрядах устройства для отрицательного числа записываются цифры базиса, обратные цифрам прямого кода – так называемый обратный код числа. Две цифры базиса называются взаимно – обратными, если их сумма составляет старшую цифру базиса. Иногда употребляют понятие «обратный базис». Например, для базиса q = 10 (0 , 1 . 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9) обратным базисом будет 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 , и обратный код числа с фиксированной точкой х = – 28356( 10 ) в 10разрядном устройстве (форма FIXED) будет представлен так: 9 9 9 9 9 7 1 6 4 3 Признак знака числа (в данном случае отрицательного) [обр] ПРАВИЛО: «Чтобы получить из прямого кода отрицательного числа обратный код, нужно взять (k – 1)-разрядный прямой код числа без знака (то есть модуль числа), дополнив старшие разряды нулями (если потребуется) и заменить цифры в разрядах обратными». В этом же устройстве прямой код числа х1 = + 28,356( 10 ) будет представлен так: 0 0 0 0 0 2 8 3 5 6 Признак знака числа (в данном случае положительного) [прямой] Если выполним действие х + х1 , то получим нуль: – 28356 ( 10 ) + + 28356 ( 10 ) = 0, а если сложим два кода этих же чисел, то во всех разрядах полу- 68 чим девятки: 9 9 9 9 9 7 1 0 0 0 0 0 2 8 9 9 9 9 9 9 9 6 4 3 – обратный код 3 5 6 – прямой код 9 9 9 то есть обратный код нуля. А это неудобно, поэтому был введён дополнительный код. Он позволяет представлять нуль всегда в прямом коде. Если к обратному коду прибавить единицу в младший разряд, то получится дополнительный код числа. Можно получить дополнительный код числа, минуя перевод его в обратный код, для чего следует руководствоваться следующим правилом. ПРАВИЛО: «Для получения дополнительного кода отрицательного числа нужно представить его модуль в устройстве и вычесть прямой код из единицы следующего старшего, по устройству, разряда (то есть (k + 1)-го разряда)». Дополнительный код числа х = – 28356 ( 10 ) в 10 – разрядном устройстве будет представлен так: 9 9 9 9 9 7 1 6 4 4 Признак знака числа (в данном случае отрицательного) [доп] и теперь сложение его с прямым кодом числа х1 = + 28356 нуль: 9 9 9 9 9 7 1 0 0 0 0 0 2 8 1 0 0 0 0 0 0 0 ( 10 ) даёт чистый 6 4 4 – дополнительный код х 3 5 6 – прямой код х1 0 0 0 – прямой код нуля при этом появляется единица переноса в несуществующий следующий старший разряд. Поскольку этого разряда в устройстве нет, то единица теряется, а в устройстве записывается правильный результат, то есть + 0. Подчеркнём дополнительно такие обстоятельства: 1) использование дополнительного кода для изменения знака числа позволяет ограничиться технической реализацией только одной операции сложения (не требуется реализовывать техническую операцию вычитания), при этом вычитание просто сводится к сложению уменьшаемого с дополнительным кодом вычитаемого; 2) если результат получается в прямом коде, то разность положительная, а в дополнительном коде, то разность отрицательная; 69 3) перевод из обратного или дополнительного кода производится по рассмотренным выше правилам. 7.5.2 Пример 9. Вычислить в q = 10 y = x + x1, где x = + 1313; x1 = = – 2626 (оба числа с фиксированной точкой). Решение: а) применив стандартные правила алгебры, получим y = x – x1 = + 1313 – 2626 = – 1313; б) с применением дополнительного кода для 10 – разрядного устройства получим 0 0 0 0 0 0 1 9 9 9 9 9 9 7 9 9 9 9 9 9 8 3 1 3 – прямой код х 3 7 4 – дополнительный код х1 6 8 7 – дополнительный код y а девятка в крайнем левом разряде указывает на то, что получен дополнительный код, следовательно, число y отрицательное; в) модуль числа y вычисляется 1 0 0 0 0 0 0 0, 0 0 0 9 9 9 9 9 9 8 6 8 7 – дополнительный код y 0 0 0 0 0 0 1 3 1 3 – модуль y и окончательный результат: y = – 1313. 7.5.3 Получение дополнительного кода отрицательных двоичных чисел осуществляется по тем же правилам. Пусть в качестве устройства, куда записываются коды, используется 32 – разрядный регистр, у которого первый слева разряд предназначен для хранения признака кода. Например, число с фиксированной точкой – 38 (10 ) = – 100110 ( 2 ) в регистре может быть представлено так: – 38 1 1 1 1 (единицы) 1 1 0 1 1 0 1 0 [доп] 31 30 29 28 7 6 5 4 3 2 1 0 Номер разряда Очень просто получается обратный двоичный код инвертированием каждого разряда (заменой 0 на 1 и 1 на 0). Для получения дополнительного кода достаточно прибавить к младшему разряду единицу. Число с фиксированной точкой – 0,38 (10 ) = – 0,100110 ( 2 ) в регистре может быть представлено так: 70 – 0,38 1 0 1 1 0 1 0 0 0 0 (нули) [доп] 1 2 3 4 5 6 7 8 9 29 30 31 Номер разряда 7.6 Контрольные вопросы для самопроверки 1 Каким основным признаком обладают позиционные системы счисления? 2 Что называется основанием позиционной системы счисления? 3 Запишите полином, с помощью которого можно представлять любое число в любой позиционной системе счисления. 4 Сформулируйте правило перевода целой части числа из одной системы счисления в другую. 5 Сформулируйте правило перевода дробной части числа из одной системы счисления в другую. 6 Каковы особенности представления чисел в форме с фиксированной запятой (точкой) и в форме с плавающей запятой (точкой)? 7 Сформулируйте алгоритмы выполнения основных арифметических операций с числами, представленными в форме с плавающей запятой (точкой). 8 В чём суть представления чисел в «беззнаковой форме»? 9 Что такое «дополнительный код» числа и как он может быть получен?