Информатика

ИНФОРМАТИКА Конспект лекций, семестр 1 Преподаватель: Смирнов Сергей Сергеевич Кафедра: Общей информатики Заведующий кафедры: Карпов Дмитрий Анатольевич Сергей Литвиненко [email protected] Московский технологический университет, 2020 Недоработки Вставить таблицу с примером ........................................................................................................................................ 5 Функциональная схема..................................................................................................................................................23 УГО ...................................................................................................................................................................................23 Обобщенная схема ........................................................................................................................................................23 Оглавление Информация ..................................................................................................................................................................... 1 О термине ..................................................................................................................................................................... 1 Свойства информации ................................................................................................................................................. 2 Признаки перехода к информационному обществу ................................................................................................ 2 Системы счисления .......................................................................................................................................................... 3 Позиционные системы счисления .............................................................................................................................. 3 Перевод чисел из системы с основанием N в систему с основанием M, где M=NK, и наоборот ......................... 3 Позиционные смешанные системы счисления ............................................................................................................. 4 Коды представления чисел ............................................................................................................................................. 4 Прямой код ................................................................................................................................................................... 4 Обратный код ............................................................................................................................................................... 4 Дополнительный код ................................................................................................................................................... 4 Модифицированные коды .......................................................................................................................................... 5 Код со смещением ....................................................................................................................................................... 5 Разрядная сетка............................................................................................................................................................ 5 Формы представления чисел .......................................................................................................................................... 5 Разрядная сетка............................................................................................................................................................ 6 Форма с фиксированной точкой ................................................................................................................................. 6 Форма с плавающей точкой ........................................................................................................................................ 7 Стандарт IEEE 754 ......................................................................................................................................................... 7 Алгоритм получения числа с плавающей точкой...................................................................................................... 8 Алгоритм восстановления десятичного числа .......................................................................................................... 8 Характеристики некоторых форматов стандарта ..................................................................................................... 9 Категории отображаемых значений .......................................................................................................................... 9 Логические основы вычислительной техники .............................................................................................................. 9 Способы задания логических функций ....................................................................................................................10 Однозначность взаимопреобразований .................................................................................................................11 Логические функции от одной переменной............................................................................................................11 Множество логических функций от двух переменных...........................................................................................12 Совершенные конъюнктивная и дизъюнктивная нормальные формы................................................................12 Логические законы и правила ..................................................................................................................................14 Минимизация логических функций .............................................................................................................................15 Метод эквивалентных логических преобразований ..............................................................................................15 Диаграмма Вейча (карта Карно) ...............................................................................................................................15 Дешифраторы .................................................................................................................................................................20 Таблица истинности ...................................................................................................................................................20 Функциональная схема..............................................................................................................................................20 Условное графическое обозначение ........................................................................................................................20 Традиционное применение ......................................................................................................................................21 Реализация логической функции 4 переменных ....................................................................................................21 Мультиплексоры ............................................................................................................................................................21 Идея работы ...............................................................................................................................................................21 Таблица истинности мультиплексора 4-1 ................................................................................................................22 Функциональная схема..............................................................................................................................................22 Условное графическое обозначение ........................................................................................................................22 Традиционное применение ......................................................................................................................................22 Реализация логической функции 4 переменных ....................................................................................................22 Демультиплексоры ........................................................................................................................................................23 Таблица истинности ...................................................................................................................................................23 Функциональная схема..............................................................................................................................................23 Условное графическое обозначение ........................................................................................................................23 Традиционное применение ......................................................................................................................................23 Шифраторы .....................................................................................................................................................................23 Таблица истинности ...................................................................................................................................................24 Комбинационная схема.............................................................................................................................................24 Условное графическое обозначение ........................................................................................................................24 Традиционное использование .................................................................................................................................24 Преобразователь 3-хразрядных отрицательных чисел из прямого кода в дополнительный............................25 Триггеры ..........................................................................................................................................................................25 Классификация ...........................................................................................................................................................26 Асинхронный RS-триггер на элементах ИЛИ-НЕ .....................................................................................................27 Асинхронный RS-триггер на элементах И-НЕ ..........................................................................................................27 Синхронный статический RS-триггер........................................................................................................................28 Синхронный двухступенчатый статический RS-триггер с асинхронными входами .............................................28 D-триггер .....................................................................................................................................................................28 T-триггер......................................................................................................................................................................29 Счетчики ..........................................................................................................................................................................29 Классификация ...........................................................................................................................................................30 Четырехразрядный суммирующий двоичный счетчик на T-триггерах с последовательным переносом ........30 Синтез счетчиков ........................................................................................................................................................30 Регистры ..........................................................................................................................................................................32 Четырехразрядный параллельный регистр на D-триггерах ...................................................................................33 Сдвиговый регистр .....................................................................................................................................................33 Регистр с последовательным приемом и выдачей, реализующий сдвиг вправо ...............................................35 Регистр с последовательным приемом и выдачей, реализующий сдвиг влево .................................................35 Регистр с последовательным приемом, параллельно-последовательной выдачей, реализующий сдвиг вправо .........................................................................................................................................................................35 Регистр с последовательным приемом, последовательной выдачей, с выбором направления счета ............36 Регистр с параллельно-последовательным приемом и выдачей, реализующий сдвиг вправо ........................36 Универсальный сдвиговый регистр (на примере одного разряда) ......................................................................36 Задача: разработать простой кодовый замок для комбинации из 4 десятичных цифр .....................................37 Сумматоры ......................................................................................................................................................................37 Четвертьсумматор......................................................................................................................................................37 Полусумматор ............................................................................................................................................................37 Полуодноразрядный двоичный сумматор ..............................................................................................................38 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Лекция №1-2 Информация О термине • • • • • • Рональд Фишер, 1921 год: набор статистических данных; Ральф Хартли, 1928 год: математическая переменная; Клод Шеннон – передача сигнала для устранения неопределенности; Норберт Виннер, 1948 год: обозначение содержания, полученного нами из внешнего мира в процессе приспосабливания к нему. «Информация – это информация, а не материя или энергия»; Виктор Михайлович Глушков: совокупность сведений, которые циркулируют в природе и обществе; Борис Коллендер: определенное разнообразие. Определения информации Без учета смысловой составляющей С учетом смысловой составляющей Без учета новизны смысла Федеральный закон №149: С учетом новизны смысла 1) Информация – сведения (сообщения, данные) независимо от формы их представления; 2) Информационные технологии – процессы, методы поиска, сбора, хранения, обработки, распространения информации и способы осуществления таких процессов и Метод методов; интерпретации 3) Информационная система – совокупность содержащейся в базах данных информации и обеспечивающих ее обработку информационных технологий и технических средств; 4) Информационно-телекоммуникационная сеть – Сведения, Оценка новизны технологическая система, предназначенная для передачи по доступные к сведений пониманию линиям связи информации. Материальный объект Информация – это новые сведения о чем-либо, полученные при помощи некоторого метода интерпретации данных, считанных с материального носителя. Пополнение сведений Новые сведения Данные – это сигналы, зафиксированные на материальном носителе, искусственным или естественным образом. Сигнал – это событие, повлекшее изменение некоторой физической величины. Метод интерпретации накладывает определенную структуру на данные и предписывает определенные действия для извлечения полезных сведений из данных. Без метода интерпретации невозможно получить сведения из данных. Если же методов несколько, то возможно получение различных сведений из одних данных. Уже известные сведения Информатика 1 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Свойства информации • • • • • • • • • • Объективность информации. Информация объективна, если она не зависит ни от методов ее фиксации, чьего-либо мнения. Точность информации определяется степенью ее близости к реальному состоянию объекта, процесса, явления и т.п. Достоверность информации. Информация достоверна, если она отражает истинное положение дел. Объективная информация всегда достоверна, но достоверная информация может быть как объективной, так и субъективной. Полнота информации. Если информации достаточно для понимания и принятия решения, информация полная. Актуальность информации – ее важность в настоящее время Полезность информации – ее нужность. Синтаксическая адекватность. (вписать с фотки) Связанность. Информация не бывает изолированной от материальных объектов, а всегда характеризуется связанностью со своим носителем. Осмысленность. Смысл информации сохраняется независимо от формы ее представления. Неисчерпаемость. Информация не подвержена физическому старению, обладает возможностью неограниченного тиражирования и накопления. Информатика (обобщенно) (первая концепция) – междисциплинарное научное направление, изучающее ИНФОРМ АЦИЯ + АВТОМ АТИКА вопросы производства, хранения, накопления, передачи, обработки и использования информации. Информатика (вторая концепция) – это методология работы с информацией, определяющая информационную культуру личности человека. Признаки перехода к информационному обществу • • • • • Объектом и результатом труда большей части населения является информация Информация – товар, определяющий экономические показатели У граждан нет проблем с доступом к информации Существует необходимая техническая база для распространения и обработки информации Информация является оружием. Информатика 2 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Лекция №3 Системы счисления Системы счисления Позиционные Kичные Традиционные K-ичные Системы счисления (СС) – это совокупность правил наименования и записи чисел, а также выполнения арифметических операций. Непозиционные Смешанные KQ-ичные Аддитивные Позиционные системы счисления Позиционная СС – СС, в которой значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда). Основание СС K – количество базовых символов в K-ой СС. Десятичная Двоичная ... 2-10-ичная ... Римская Палочковая ... Методы перевода чисел из 10-ой системы: 1. столбиком) 2. Машинный алгоритм (деление Метод подбора: a. Подобрать число 𝑌 = 𝑛 𝐾 такое, что Y ≤ X < K n+1 и выписать его. b. Найти разность D = X − Y. c. Проверить: если D = 0, перевод окончен. Иначе перейти к пункту a, считая D = X. d. Подсчитать количество одинаковых Y и записать эту цифру в соответствующую позицию n. e. Достаточная точность. Конечная дробь в одной СС может представляться бесконечной непериодической дробью в другой СС. В таком случае для расчета достаточного количества разрядов после запятой пользуются следующим правилом: Если единица младшего разряда числа X, заданного в P-ой СС, есть 𝑃 −𝑚 , то в его K-ой записи следует сохранить L разрядов после запятой, где L удовлетворяет условию: 𝑃 −𝑚 𝐾 −𝐿 > > 𝐾 −(𝐿+1) 2 Перевод чисел из системы с основанием N в систему с основанием M, где M=NK, и наоборот 1. Из СС с основанием N в СС с основанием M: В записи числа с основанием N нужно выделять группы разрядов размером K и переводить каждую группу в соответствующую цифру M-ой системы. При переводе дробной части группы выделяются, начиная со старших членов. Недостающие разряды в группах заполняются нулями. Информатика 3 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. 2. Из СС с основанием M в СС с основанием N Каждая цифра числа записывается в системе с основанием M записывается как число из K разрядов в системе с основанием N. Позиционные смешанные системы счисления Каждая десятичная цифра записывается в двоичном представлении. Используется в калькуляторах, цифровых часах. Преимущества: • легкий ввод-вывод числовой информации Недостатки: • • повышенный расход памяти, т.к. для некоторых цифр приходится выделять излишние участки памяти осложнены арифметические операции вследствие переполнения разрядов Лекция №3 Коды представления чисел Коды представления чисел Прямой код Обратный код Дополнительный код Прямой код Предназначен для отображения целых и дробных чисел со знаком. Сначала ставится знаковый разряд (0 – положительное, 1 – отрицательное). На бумаге знаковый разряд отделяется точкой. Затем записывается само число. Например, 0.1011,12ПР = 11,510; 1.1011,12ПР = -11,510. Модифицированный обратный код Модифицированный дополнительный код Код со смещением Обратный код Положительные числа в обратном коде выглядят так же, как и в прямом, отрицательные формируются следующим образом: ставится знаковый разряд (1), а затем записывается положительное число с инвертированными цифрами (0 → 1, 1 → 0). Например, 10102ОБР = 1010; 1.01012ОБР = -1010. N-битное число в обратном коде содержит N-1 значащих разрядов и 1 знаковый! Дополнительный код Применяется для представление целых и дробных чисел со знаком. Образуется следующим образом: • • Положительные числа выглядят так же, как и в прямом коде В знаковый разряд отрицательных чисел ставится единица, далее берется число в обратном коде, и к младшему разряду арифметическим образом прибавляется единица. -1410 = 1.00102ДОП Информатика 4 Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. -810 = 1.10002ДОП Альтернативный способ перевода. Нужно переписать все биты исходного числа справа налево до первой единицы, включая ее. Остальные биты инвертировать. Поставить знаковый разряд. 1. Есть только +0 2. Дополнительный код N-разрядного отрицательного числа есть дополнение модуля этого числа до 0. 3. Есть невостребованная комбинация (-8 требует уже 5 бит). Модифицированные коды Для придания однозначности записи числа могут использоваться модифицированный обратный и дополнительный код. В модифицированных кодах используются два знаковых разряда: • • • • 00 – положительное число 11 – отрицательное число 01 – положительное число с переполнением 10 отрицательное число с переполнением Правила вычислений в модифицированных кодах такие же. Код со смещением Позволяет сдвинуть числовую шкалу, содержащую как отрицательные, так и положительные числа, полностью в область положительных чисел. Вставить таблицу с примером Если n – доступное количество разрядов, то 2𝑛−1 − максимальное число в смещенном коде, записываемое как 1. .1; 1 − 2𝑛−1 − минимальное число в смещенном коде, записываемое как 0. .0; 2𝑛−1 − 1 − величина смещения; При выполнении арифметических операций необходимо учитывать смещение. Чтобы получить в конце верный результат, смещение необходимо вычесть. Разрядная сетка Разрядная сетка – это множество двоичных разрядов, выделяемых в памяти для изображения чисел. Величина разрядной сетки зависит от разрядности процессора. От того, как именно она используется, зависят диапазон и точность представления чисел. При выполнении арифметических операций возможны случаи, когда результат не помещается в разрядную сетку. Если число вышло за пределы РС слева, говорят о переполнении разрядной сетки. Если число вышло за пределы разрядной сетки справа, то говорят о возникновении машинного нуля. Лекция №4 Формы представления чисел Информатика 5 Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Форма представления чисел – это вариант распределения разрядов имеющейся разрядной сетки между отдельными структурными элементами в записи числа. n-1 n-2 … 2 1 Разрядная сетка Разрядная сетка – это множество двоичных разрядов, выделяемых в памяти для хранения чисел. Ее величина зависит от разрядности процессора. Если число вышло за пределы разрядной сетки слева, говорят о переполнении разрядной сетки. Если число вышло за пределы разрядной сетки справа, говорят о возникновении машинного нуля. Форма с фиксированной точкой Формы представления чисел С фиксированной точкой Где-то в середине сетки Слева от старшего разряда С плавающей точкой Для хранения целых неотрицательных чисел отводится одна ячейка памяти (8 битов). Например, число А2 = = 111100002 будет храниться в ячейке памяти следующим образом: Справа от младшего разряда Без знака (только положительные) Со знаком Целые числа в компьютере хранятся в памяти в формате с фиксированной точкой. В этом случае каждому разряду ячейки памяти соответствует всегда один и тот же разряд числа, а "запятая" "находится" справа после младшего разряда, то есть вне разрядной сетки. 1 1 1 1 0 0 0 0 Максимальное значение целого неотрицательного числа достигается в случае, когда во всех ячейках хранятся единицы. Для n-разрядного представления оно будет равно 2𝑛 − 1. Диапазон изменения целых неотрицательных чисел: от 0 до 255. Для хранения целых чисел со знаком отводится две ячейки памяти (16 битов), причем старший (левый) разряд отводится под знак числа (если число положительное, то в знаковый разряд записывается 0, если число отрицательное - 1). Представление в компьютере положительных чисел с использованием формата "знак-величина" называется прямым кодом числа. Например, число 200210 = 111110100102 будет представлено в 16разрядном представлении следующим образом: 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 Максимальное положительное число (с учетом выделения одного разряда на знак) для целых чисел со знаком в n-разрядном представлении равно 2𝑛−1 − 1. Для представления отрицательных чисел используется дополнительный код. Дополнительный код позволяет заменить арифметическую операцию вычитания операцией сложения, что существенно упрощает работу процессора и увеличивает его быстродействие. Информатика 6 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Форма с плавающей точкой Арифметические операции • • • Сложение и вычитание: сначала производится выравнивание порядков (меньший по модулю порядок числа увеличивается до величины большего, а мантисса уменьшается в такое же количество порядков), а затем происходит сложение и вычитание мантисс. Умножение: порядки складываются, мантиссы перемножаются. Деление: из порядка делимого вычитается порядок делителя, а мантисса делится на мантиссу делителя. В конце арифметических действий производится нормализация результата. Стандарт IEEE 754 IEEE 754 — широко распространённый стандарт, описывающий формат представления чисел с плавающей точкой. Используется в программных и аппаратных реализациях арифметических. Форматы стандарта: • • • • Число половинной точности (разрядная сетка 2 байта) Число одинарной точности (разрядная сетка 4 байта) Число двойной точности (разрядная сетка 8 байт) Число четверной точности (разрядная сетка 16 байт) Представление мантиссы В записи числа используется нормализованная мантисса. Но реализация нормализации отличается от общей идеи. Дело в том, что в традиционном нормализованном числе единица в старшем бите мантиссы есть всегда. Следовательно, ее можно не сохранять, но «подразумевать». Поэтому стандарт определяет мантиссу следующим образом: она состоит из неявного бита, который всегда равен 1, двоичной точки и остальных разрядов. Получается, что мантисса охватывает диапазон чисел [1, 2). Мантисса представляется в прямом коде. При выполнении арифметических операций с мантиссами не забывать про мнимые единицы! Представление порядка Порядок числа записывается в смещенном коде, т.е., к нему прибавляется фиксированное число, чтобы порядок был всегда неотрицательным. Это упрощает выполнения операций над порядками, избавляет от знакового разряда порядка. Истинный порядок может быть и положительным, и отрицательным. Все доступные разряды порядка разделяются поровну между его положительными и отрицательными значениями. При выполнении арифметических операций процессор учитывает сдвиг. Одна комбинация резервируется для специальных нужд. Ограничения точности для целых чисел • • • • • • Целые между 0 и 2047 представляются точно Целые между 2048 и 4095 округляются вниз до кратного 2 (четному числу) Целые между 4096 и 8191 округляются вниз до кратного 4 Целые между 8192 и 16383 округляются вниз до кратного 8 Целые между 16384 и 32767 округляются вниз до кратного 16 Целые между 32768 и 65535 округляются вниз до кратного 32 Информатика 7 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Почему это происходит? Пусть дано число 500310=10011100010112=011001001110001011. Последние две цифры мантиссы оказались за пределами разрядной сетки. При обратном переводе в десятичную систему получим число 5000 – ближайшее округленное до кратного числу 4. Формат числа половинной точности ± Порядок 1 5 Мантисса 10 25−1 Смещение (или сдвиг) порядка: − 1 = 15 – число, которое необходимо прибавить к истинному порядку исходного числа. Оно записывается в биты поля Порядок. Для формата половинной точности под порядок выделяется 5 бит разрядной сетки, т.е. максимальное смещенное значение порядка – 31. Формат числа одинарной точности ± Порядок Мантисса 1 8 23 Под порядок выделено 8 бит, поэтому смещение: 28−1 − 1 = 127. Формат двойной точности ± Порядок Мантисса 1 11 52 Под порядок выделено 11 бит, поэтому смещение: 211−1 − 1 = 1023. Алгоритм получения числа с плавающей точкой 1. Перевести число из K-ичной системы счисления в двоичную (прямой код); 2046 = +11111111110 2. Представить двоичной число в нормализованной форме: 1. < 𝑛 разрядов >∗ 2𝑛 ; 11111111110 = 1.1111111110 ∗ 210 3. Рассчитать смещенный порядок числа: (𝑛 + 𝑚)2 , где 𝑚 – смещение, зависящее от формата хранения; 10 + 15 = 25 = 11001 4. Разместить знак, порядок и мантиссу в соответствующие разряды сетки; 0110011111111111 5. Разбить полученное число на тетрады и записать полученные двоичные разряды в виде числа в 16-ичной системе. 0110 0111 1111 1111 = 67𝐹𝐹. Алгоритм восстановления десятичного числа 1. Расписать по знакам исходное 16-ричное число на двоичные разряды; 𝐴𝐵𝐶𝐷16 = 1010101111001101 2. По первому биту определить знак числа; 𝐴𝐵𝐶𝐷16 = 1 … , ⇔ знак " − " 3. Вычислить истинный порядок: из смещенного порядка вычесть сдвиг порядка; 01010 − 15 = −5 Информатика 8 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. 4. Записать знак, подразумеваемую единицу, в дробную часть выписать мантиссу, умножить полученное число на 2истинный порядок , упростить полученное выражение; −1.1111001101 ∗ 2−5 = −0.000011111001101 5. Перевести полученное число в десятичную систему счисления. Характеристики некоторых форматов стандарта Характеристика форматов Количество битов в знаке Количество битов в экспоненте (порядке) Количество битов в мантиссе Общее число битов Смещение экспоненты Область значений экспоненты Самое маленькое нормализованное число Самое большое нормализованное число Диапазон десятичных дробей Самое маленькое ненормализованное число Название типа в C/C++ Одинарная точность 1 8 23 32 127 От -126 до 127 2-126 2128 От 10-38 до 1038 10-45 Float Двойная точность 1 11 52 64 1023 От -1022 до 1023 2-1022 21024 От 10-308 до 10308 10324 Double Категории отображаемых значений Тип числа Нормализованное число Ненормализованное число Ноль Бесконечность Знак ± ± ± ± Порядок 0 0, то каждый следующий набор отличается от предыдущего значением только одной переменной. Типы интервалов * Информатика 15 * * * * * * * * Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Интервал размера 1 Вырожденный случай. Упрощения не происходит. Интервал может встречаться на любых диаграммах. * Интервал размера 2 Упрощается одна переменная. Интервалы могут встречаться на любых диаграммах. * * * * * * * * * * Интервал размера 4 Упрощается 2 переменных. Некоторые интервалы встречаются, начиная с диаграммы Вейча для функции от 3 переменных. Интервалы размером 8 Упрощается 3 переменных. Некоторые интервалы встречаются, начиная с диаграммы Вейча для функции от 4 переменных. Алгоритм минимизации 1. Нарисовать исходную таблицу диаграммы и сделать ее разметку в зависимости от количества переменных функции. 2. Заполнить таблицу значениями функции с учетом цели минимизации (удобно выписывать только 1 для МДНФ и только 0 для МКНФ). 3. Выделить контурами интервалы из единиц (МДНФ) или нулей (МКНФ), соблюдая следующие правила: a. Необходимо стараться выделить максимально большие интервалы; b. Каждый новый интервал должен содержать хотя бы одно значение, принадлежащее только ему; c. Необходимо выделить минимально возможное количество интервалов. 4. Выписать формулу МДНФ (МКНФ), для чего: a. Для каждого интервала выписать конъюнкт (дизъюнкт), в который будут входить только те переменные или их отрицания, которые сохраняют свое значение на интервале. Остальные переменные упростятся. b. Соединить выписанные конъюнкты (дизъюнкты) через дизъюнкцию (конъюнкцию). Диаграмма Вейча для функции от 2 переменных МДНФ: 𝑦 𝑦̅ 𝑥 𝑓(11) 𝑓(10) 𝑥̅ 𝑓(01) 𝑓(00) МКНФ: 𝑦 𝑦̅ 𝑥 𝑓(00) 𝑓(01) 𝑥̅ 𝑓(10) 𝑓(11) Диаграмма Вейча для функции от 3 переменных МДНФ: 𝑦 𝑦̅ Информатика 16 Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. 𝑥 𝑓(110) 𝑓(111) 𝑓(101) 𝑓(100) 𝑥̅ 𝑓(010) 𝑓(011) 𝑓(001) 𝑓(000) 𝑧̅ 𝑧 𝑧̅ МКНФ: 𝑦 𝑦̅ 𝑥 𝑓(001) 𝑓(000) 𝑓(010) 𝑓(001) 𝑥̅ 𝑓(101) 𝑓(100) 𝑓(110) 𝑓(111) 𝑧̅ 𝑧 𝑧̅ Диаграмма Вейча для функции от 4 переменных МДНФ: 𝑏̅ 𝑏 𝑓(1100) 𝑓(1101) 𝑓(1001) 𝑓(1000) 𝑐̅ 𝑎 𝑓(1110) 𝑓(1111) 𝑓(1011) 𝑓(1010) 𝑐 𝑓(0110) 𝑓(0111) 𝑓(0011) 𝑓(0010) 𝑎̅ 𝑓(0100) 𝑓(0101) 𝑓(0001) 𝑓(0000) 𝑐̅ 𝑑̅ 𝑑̅ 𝑑 МКНФ: 𝑏̅ 𝑏 𝑓(0011) 𝑓(0010) 𝑓(0110) 𝑓(0111) 𝑐̅ 𝑎 𝑓(0001) 𝑓(0000) 𝑓(0100) 𝑓(0101) 𝑐 𝑓(1001) 𝑓(1000) 𝑓(1100) 𝑓(1101) 𝑎̅ 𝑓(1011) 𝑓(1010) 𝑓(1110) 𝑓(1111) 𝑐̅ 𝑑̅ 𝑑̅ 𝑑 Наборы значений функции для МКНФ по отношению к МДНФ инвертируются. Пусть дана таблица истинности логической функции: 𝒂 𝒃 𝒄 𝒅 𝒇 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 1. Составим для данной функции диаграмму Вейча (МДНФ) и выделим интервалы: 𝑏̅ 𝑏 𝑎 1 1 1 1 1 0 1 1 1 1 0 1 𝑐̅ 𝑐 𝑎̅ Информатика 17 𝑐̅ Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. 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 Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. 𝑑̅ 𝑑̅ 𝑑 По данной диаграмме составим формулу: 𝐹МДНФ = 𝑎𝑐 + 𝑏𝑐𝑑 + 𝑎𝑏𝑑 + 𝑏𝑐𝑑 + 𝑎𝑏𝑐 2. Составим для данной функции диаграмму Вейча (МКНФ) и выделим интервалы: 𝑏̅ 𝑏 1 1 0 1 𝑐̅ 1 0 1 𝑐 1 1 1 1 0 0 1 𝑑̅ 𝑑 𝑑̅ 𝑎 𝑎̅ 𝑐̅ По данной диаграмме составим формулу: 𝐹МКНФ = (𝑏̅ + 𝑐̅ + 𝑑)(𝑎 + 𝑏 + 𝑐 + 𝑑)(𝑎 + 𝑏̅ + 𝑐 + 𝑑̅ )(𝑎̅ + 𝑏 + 𝑐̅) Диаграмма Вейча для функции от 5 переменных МДНФ: 𝑏̅ 𝑏 𝑒 𝑒̅ 𝑒 𝑓(11001) 𝑓(11011) 𝑓(11010) 𝑓(11000) 𝑓(10000) 𝑓(10010) 𝑓(10011) 𝑓(10001) 𝑐̅ 𝑎 𝑓(11101) 𝑓(11111) 𝑓(11110) 𝑓(11100) 𝑓(10100) 𝑓(10110) 𝑓(10111) 𝑓(10101) 𝑐 𝑎̅ 𝑓(01101) 𝑓(01111) 𝑓(01110) 𝑓(01100) 𝑓(00100) 𝑓(00110) 𝑓(00111) 𝑓(00101) 𝑓(01001) 𝑓(01011) 𝑓(01010) 𝑓(01000) 𝑓(00000) 𝑓(00010) 𝑓(00011) 𝑓(00001) 𝑐̅ 𝑑̅ 𝑑 𝑑̅ 𝑑̅ 𝑑 МКНФ: 𝑏̅ 𝑏 𝑒 𝑒̅ 𝑒 𝑓(00110) 𝑓(00100) 𝑓(00101) 𝑓(00111) 𝑓(01111) 𝑓(01101) 𝑓(01100) 𝑓(01110) 𝑐̅ 𝑎 𝑓(00010) 𝑓(00000) 𝑓(00001) 𝑓(00011) 𝑓(01011) 𝑓(01001) 𝑓(01000) 𝑓(01010) 𝑐 𝑓(10010) 𝑓(10000) 𝑓(10001) 𝑓(10011) 𝑓(11011) 𝑓(11001) 𝑓(11000) 𝑓(11010) 𝑎̅ 𝑓(10110) 𝑓(10100) 𝑓(10101) 𝑓(10111) 𝑓(11111) 𝑓(11101) 𝑓(11100) 𝑓(11110) 𝑐̅ Информатика 18 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. 𝑑̅ 𝑑 Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. 𝑑̅ 𝑑 𝑑̅ Минимизация частично определенных логических функций В некоторых задачах нам известно, что определенные входные комбинации никогда не возникнут. В таком случае неопределенные значения интерпретируются так, как удобно. Пусть дана частично определенная логическая функция: 𝒂 𝒃 𝒄 𝒅 𝒇 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 ∗ 1 0 1 1 ∗ 1 1 0 0 ∗ 1 1 0 1 ∗ 1 1 1 0 ∗ 1 1 1 1 ∗ 1. Составим для данной функции диаграмму Вейча (МДНФ), считая неопределенные значения истинными. 𝑏̅ 𝑏 ∗ ∗ 1 1 ∗ ∗ 𝑐̅ 𝑎 ∗ ∗ 𝑐 1 1 𝑎̅ 1 1 𝑑̅ 𝑐̅ 𝑑̅ 𝑑 По данной диаграмме составим формулу: 𝐹МДНФ = 𝑎 + 𝑏̅𝑐̅𝑑 + 𝑏𝑐𝑑 + 𝑏̅ 𝑑̅ 2. Составим для данной функции диаграмму Вейча (МКНФ), считая неопределенные значения ложными. 𝑏̅ 𝑏 𝑎 𝑐̅ ∗ ∗ ∗ ∗ ∗ ∗ 𝑑̅ 𝑑 𝑑̅ 𝑐 𝑎̅ 𝑐̅ По данной диаграмме составим формулу: 𝐹МКНФ = (𝑏 + 𝑐̅ + 𝑑̅ )(𝑎̅ + 𝑐̅)(𝑏̅ + 𝑑)(𝑐 + 𝑑̅ ) Приведение минимизированной функции к заданному логическому базису На примере 𝐹(79𝐶𝐷). (МДНФ к базису ИЛИ-НЕ) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅ ̅ + 𝑐 + 𝑑 + ̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅ 𝐹МДНФ = 𝑎𝑐̅ + 𝑏𝑐̅𝑑̅ + 𝑏𝑐𝑑 + 𝑎̅𝑏̅𝑐 + 𝑎̅𝑏̅𝑑 = ̅̅̅̅̅̅̅ 𝑎̅ + 𝑐 + 𝑏 𝑏̅ + 𝑐̅ + 𝑑̅ + 𝑎 + 𝑏 + 𝑐̅ + ̅̅̅̅̅̅̅̅̅̅̅̅̅ 𝑎 + 𝑏 + 𝑑̅ (МДНФ к базису И-НЕ) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅ 𝐹МДНФ = 𝑎𝑐̅ + 𝑏𝑐̅𝑑̅ + 𝑏𝑐𝑑 + 𝑎̅𝑏̅𝑐 + 𝑎̅𝑏̅𝑑 = 𝑎𝑐̅ ∗ ̅̅̅̅̅ 𝑏𝑐̅𝑑̅ ∗ ̅̅̅̅̅ 𝑏𝑐𝑑 ∗ ̅̅̅̅̅ 𝑎̅𝑏̅ 𝑐 ∗ ̅̅̅̅̅ 𝑎̅𝑏̅ 𝑑 Информатика 19 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. (МКНФ к базису ИЛИ-НЕ) 𝐹МКНФ = (𝑎̅ + 𝑏 + 𝑐̅)(𝑏̅ + 𝑐̅ + 𝑑)(𝑎 + 𝑏 + 𝑐 + 𝑑)(𝑎 + 𝑎̅ + 𝑐 + 𝑑̅ ) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (𝑎̅ + 𝑏 + 𝑐̅) + ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (𝑎 + 𝑏 + 𝑐 + 𝑑) + ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (𝑏̅ + 𝑐̅ + 𝑑) + ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (𝑎 + 𝑎̅ + 𝑐 + 𝑑̅ ) (МКНФ к базису И-НЕ) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅ ∗ 𝑎 ̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅ 𝐹МКНФ = (𝑎̅ + 𝑏 + 𝑐̅)(𝑏̅ + 𝑐̅ + 𝑑)(𝑎 + 𝑏 + 𝑐 + 𝑑)(𝑎 + 𝑎̅ + 𝑐 + 𝑑̅ ) = ̅̅̅̅̅ 𝑎𝑏̅ 𝑐 ∗ 𝑏𝑐𝑑 ̅𝑏̅𝑐̅𝑑̅ ∗ 𝑎 ̅𝑏𝑐̅𝑑 Лекция №6 Дешифраторы Дешифратор – комбинационная схема, обладающая 𝑛-адресными входами, одним разрешающим входом и 2𝑛 выходами. На адресные входы подается двоичное число, которое в своем десятичном представлении задает номер выхода, на котором формируется значащий сигнал. Предназначена для преобразования 𝑛разрядного двоичного кода в унитарный двоичный код разрядности 2𝑛 . В унитарном коде только один разряд из множества может принимать значение 1 (или 0). Это означает, что двоичное число (в своем десятичном представлении) задает номер того выхода, на котором появится 1 (или 0, если выходы инверсные). Таблица истинности 𝑬 𝒙𝟏 1 0 1 0 1 1 1 1 0 x 𝒙𝟎 1 1 x 𝒒𝟎 1 𝒒𝟏 1 𝒒𝟐 1 𝒒𝟑 1 Функциональная схема Условное графическое обозначение Стандарт Logisim Информатика 20 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. В зависимости от реализации входы и выходы могут быть как прямые, так и инверсные. Традиционное применение • • • В составе схем управления другими устройствами для последовательной подачи разрешающих сигналов; В составе схем преобразователей кодов; Для реализации логических функций. Реализация логической функции 4 переменных В данном примере используется функция 𝑓 = 𝑓{1𝐸6𝐹}. DC 4-16 DC 3-8 DC 2-4 Мультиплексоры Мультиплексор – комбинационная схема, у которой имеется 2𝑛 информационных входов, 𝑛 адресных входов, может присутствовать разрешающий вход и имеется 1 выход. Представляет собой управляемый переключатель, т.е. осуществляет подключение одного из информационных входов к единственному выходу под управлением адресных и разрешающего кодов. Сигнал на разрешающем коде управляет мультиплексором в целом: либо разрешает прохождение сигналов на выход, либо нет (в этом случае на выходе обычно 0). Идея работы На данной схеме: • • • • Информатика 21 𝐷 = 2𝑛 – информационные входы; 𝐴 = 𝑛 адресные входы; 𝐸 – разрешающий вход; 𝑄(𝐷, 𝐴, 𝐸) – результат на выходе. Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Таблица истинности мультиплексора 4-1 𝑬 𝑨𝟏 1 0 1 0 1 1 1 1 0 x 𝑨𝟎 1 1 x 𝑸 𝐷0 𝐷1 𝐷2 𝐷3 Функциональная схема В основе мультиплексора лежит дешифратор. Условное графическое обозначение Стандарт Logisim Традиционное применение • • «Ленивая» реализация логических функций, когда минимизацией можно пренебречь. Удобно для разработчика, но приводит к дополнительным затратам. В качестве коммутатора 𝑛 к 1: o Для преобразования параллельного входа в последовательный; o Для поочередного подключения многих источников информации к одному потребителю. Реализация логической функции 4 переменных В данном примере реализуется логическая функция 𝑓 = 𝑓{1𝐸6𝐹}. MUX 16-1 MUX 8-1 MUX 4-1 Информатика 22 MUX 2-1 и MUX 4-1 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Демультиплексоры Демультиплексор – комбинационная схема, у которой имеются: один информационный вход, 𝑛 адресных входов, 2𝑛 выходов, может присутствовать разрешающий вход. Осуществляет коммутацию единственного информационного входа к одному из выходов под управлением адресных и разрешающего входов. Сигнал на разрешающем входе управляет демультиплексором в целом: либо разрешает прохождение сигналов на выход, либо нет. В виде самостоятельной схемы не выпускаются. Реализуются на базе дешифратора. Таблица истинности 𝑬 𝑨𝟏 1 0 1 0 1 1 1 1 0 x 𝑨𝟎 1 1 x 𝑸𝟎 D 𝑸𝟏 D 𝑸𝟐 D 𝑸𝟑 D Функциональная схема Функциональная схема Условное графическое обозначение Стандарт Logisim В зависимости от реализации входы и выходы могут быть как прямыми, так и инверсными. Традиционное применение • • В качестве коммутатора 1 к 𝑛 (для поочередного подключения одного источника информации ко многим потребителям); Для реализации логических функций (получается реализация на дешифраторах) Шифраторы Шифратор – комбинационная схема, выполняющая обратную дешифратору функцию, имеющая: 2𝑛 информационных входов, 𝑛 выходов. Преобразует номер информационного входа, на котором сформирован значащий уровень сигнала, из десятичной системы счисления в двоичную. Виды шифраторов: Информатика 23 Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. • • • • Полные формируют весь доступный по разрядности диапазон двоичных чисел; Неполные ориентированы на ограниченный диапазон (например, 10-4 формирует числа от 0000 до 1010); Простые – правильная комбинация задается унитарным кодом; Приоритетные – если на входе любая комбинация, но на выходе будет код, соответствующий старшему входному сигналу. Таблица истинности 𝒙𝟎 1 𝒙𝟏 1 𝒙𝟐 1 𝒙𝟑 1 𝒙𝟒 1 𝒙𝟓 1 𝒙𝟔 1 𝒙𝟕 1 𝒚𝟎 1 1 1 1 𝒚𝟏 1 1 1 1 𝒚𝟐 1 1 1 1 Комбинационная схема Условное графическое обозначение Стандарт Logisim (шифратор приоритетов) Традиционное использование • • Получение кодов нажатых клавиш; В составе преобразователей кодов. Информатика 24 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Преобразователь кодов С помощью дешифратора и шифратора приоритетов можно создать преобразователь кодов – комбинационную схему, возвращающую значения в зависимости от входных сигналов, решающую поставленную задачу. Задача: разработать преобразователь кодов 3-хразрядных отрицательных чисел из прямого кода в дополнительный. Таблица истинности Реализация X2 X1 X0 Y2 Y1 Y0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 Лекция №7 Триггеры Триггер – это простейший цифровой автомат, который представляет собой элементарную ячейку памяти и может хранить один бит информации. Может находиться в одном из двух состояний – 0 или 1. Реализуется на базисных элементах (И-НЕ, ИЛИ-НЕ). Эффект запоминания возникает благодаря наличию обратных связей между элементами. Триггеры могут использоваться как самостоятельно в составе других устройств, так и образовывать более сложные устройства (например, счетчики). Информатика 25 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Триггеры По логическому функционированию По способу записи информации По количеству ступеней RS Синхронные Одноступенчатые D Асинхронные Двухступенчатые T K И другие Классификация 1. По логическому функционированию: RS, D, T, JK (основные типы); 2. По способу записи информации: a. Асинхронные: Запись информации осуществляется в момент подачи сигнала на информационные входы. b. Синхронные: Сигнал синхронизации – это последовательность дискретных импульсов стабильной частоты. i. Со статическим управлением (стробируемые): Воспринимает информационные сигналы во время действия активного уровня на входе C, т.е. пока C=1, происходит постоянная перезапись информации, а когда C=0, происходит фиксация состояния триггера. ii. С динамическим управлением (тактируемые) (фронтовые триггеры): Воспринимает информационные сигналы в моменты переключений синхроимпульса (0 → 1 или 1 → 0), т.е. в моменты прихода переднего или заднего фронта сигнала. Информатика 26 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Запись возможна только в присутствии разрешающего сигнала C (Clock), т.е. сигнала синхронизации. Вход C называется прямым динамическим, если переключение триггера происходит в момент прихода переднего фронта, инверсным динамическим – если переключение происходит в момент прихода заднего фронта. Для цифровых автоматов синхронизация очень важна, поскольку позволяет согласовывать во времени процессы чтения и записи, происходящие в разных частях схемы, реализуя, таким образом, алгоритм работы устройства. 3. По количеству ступеней: a. Одноступенчатые: Для запоминания используется только одна ступень. Возникают проблемы при записи и считывании информации в пределах одного такта. Что считано: старая информация или новая? b. Двухступенчатые: Состоят из двух одноступенчатых, работающих в противофазе. Работают в 2 раза медленнее, но решают проблему одноступенчатых триггеров: когда вторая ступень еще хранит старую информацию, первая уже может принимать новую. Поскольку реальные времена срабатывания элементов зависят от незначительных отклонений в процессе их изготовления, то при включении питания триггер непредсказуемо принимает одно из двух состояний. Это приводит к необходимости выполнять первоначальную установку триггера в требуемое исходное состояние. Асинхронный RS-триггер на элементах ИЛИ-НЕ Хранение Схема 3 Сброс Схема 4 Хранение Схема 5 Запрещенная комбинация (идеальный случай) Схема 6 Запрещенная комбинация (в реальности) Схема 7 Асинхронный RS-триггер на элементах И-НЕ При рассмотрении всех нижеследующих триггеров за основу возьмем реализацию на элементах И-НЕ. Информатика 27 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Синхронный статический RS-триггер Синхронный двухступенчатый статический RS-триггер с асинхронными входами D-триггер Триггер-задержка – хранит предыдущее состояние до прихода очередного синхроимпульса. Информатика 28 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. T-триггер Триггер-счетчик – с приходом очередного счетного импульса меняет свое состояние на противоположное. Таблица истинности для синхронного T-триггера: Схема 14 Счетчики Счетчик – это цифровой автомат, реализованный на триггерах. Подсчитывает некое количество импульсов. Счет хранится в двоичном коде. Параметры счетчика: • • • Модуль счета 𝑀 – максимальное количество единичных импульсов, которое может быть сосчитано счетчиком. Счетчик обнуляется, когда приходит 𝑀-ый импульс. Шаг счета – приращение значения счетчика при приходе очередного импульса. Направление счета – в сторону увеличения или уменьшения значений. Информатика 29 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Классификация Счетчики По модулю счета По шагу счета По направлению счета По способу организации межразрядных связей Двоичные 1 Суммирующие Последовательный Двоично-десятичные 2 Вычитающие Параллельный С постоянным модулем счета ... Реверсивные Комбинированный С переменным модулем счета 𝐾<𝑀 О способах организации межразрядных связей В счетчиках с последовательным переносом (асинхронные счетчики) переключение триггеров разрядных схем осуществляется последовательно один за другим. В счетчиках с параллельным переносом (синхронные счетчики) переключение всех триггеров разрядных схем осуществляется одновременно по сигналу синхронизации. В счетчиках с комбинированным последовательно-параллельным переносом используются различные комбинации способов переноса. Четырехразрядный суммирующий последовательным переносом двоичный счетчик на T-триггерах с Схема 15 Временная диаграмма Схема 16 у Олега Синтез счетчиков Синтезируем счетчик со следующими параметрами: • • • Максимальное значение: 9 Шаг счета: 4 Направление счета: вычитание Таблица истинности В этом шаге идет построение таблицы истинности счетчика. Соответствующая элементам левого столбца группа значений правого столбца – это значение, которое должен будет хранить счетчик на следующем такте. 𝑸𝟑 (𝒕) 𝑸𝟐 (𝒕) 𝑸𝟏 (𝒕) 𝑸𝟎 (𝒕) 𝑸𝟑 (𝒕 + 𝟏) 𝑸𝟐 (𝒕 + 𝟏) 𝑸𝟏 (𝒕 + 𝟏) 𝑸𝟎 (𝒕 + 𝟏) 1 1 Информатика 30 Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. 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 ∗ ∗ ∗ ∗ ∗ ∗ Минимизация функций Qi(t+1) Получили 4 логические функции. Для синтеза оптимального счетчика имеет место минимизация логических функций. Заметим, что в нашем случае 𝑄0 (𝑡) = 𝑄0 (𝑡 + 1). Остальные функции минимизируем методом Вейча-Карно. 𝑄3 (𝑡 + 1) = 𝑏 𝑏̅ * * 𝑎 * * * * 1 1 𝑎̅ 𝑑̅ 𝑑 ̅ 𝑏𝑐 𝑑̅ 𝑐̅ 𝑐 𝑐̅ 𝑄2 (𝑡 + 1) = 𝑏 𝑏̅ * * 1 1 𝑎 * * * * 𝑎̅ 𝑑̅ 1 1 𝑑̅ 𝑑 ̅ 𝑏𝑐̅ 𝑐̅ 𝑐 𝑐̅ 𝑄1 (𝑡 + 1) = 𝑏 𝑏̅ * * 𝑎 * * * * 1 1 𝑎̅ 1 1 𝑑 𝑑̅ 𝑑̅ ̅ 𝑏𝑐 + 𝑎̅𝑏𝑐̅ 𝑄0 (𝑡 + 1) = 𝑑 𝑐̅ 𝑐 𝑐̅ Синтез счетчика Синтезировать счетчик можно двумя путями. С помощью преобразователя кодов Это «ленивая» реализация счетчика с помощью преобразователя кодов. Требуются дешифратор и шифратор приоритетов. Информатика 31 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Оптимизированный счетчик Минимизировав логические функции, изобразим их на схеме. При этом не забываем, что нумерация разрядов идет в обратном порядке: Требуемый счетчик синтезирован. Лекция №8 Регистры Регистром называется цифровой автомат, реализованный на триггерах, основным назначением которого является прием двоичной информации, временное хранение двоичной информации и выдача информации потребителю. Этот минимум операций выполняет простейший регистр, который называется регистром хранения. Запись и выдача информации осуществляется на все разряды одновременно (т.е. в параллельном коде). Усовершенствованный регистр (сдвиговый) может также выполнять операцию сдвига информации вправо и влево (умножение или деление на 2). Информатика 32 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Благодаря операции сдвига становятся возможными различные способы приема и выдачи информации: • • • • Параллельный прием Параллельная выдача Последовательный прием Последовательная выдача Таким образом, сдвиговый регистр может: • • Преобразовывать последовательный код в параллельный и наоборот Быстро выполнять операции умножения и деления на 2 Регистры классифицируют по: • • • Количеству разрядов Триггерам, на которых они реализованы Способу приема и выдачи данных o Параллельные (простейшие триггеры хранения) o Последовательные (последовательный прием, последовательная выдача) o Параллельно-последовательные (универсальный сдвиговый регистр) Четырехразрядный параллельный регистр на D-триггерах Сдвиговый регистр Триггеры сдвигового регистра связаны между собой цепями переноса, что позволяет одновременно переносить содержимое отдельного триггера регистра в соседний триггер, осуществляя операцию сдвига. Сдвиг характеризуется: • • Направлением – влево или вправо Типом o Логический (в освободившийся крайний триггер заносится 0) o Арифметический (содержмое регистра понимается как число в дополнительном коде. При сдвиге влево справа появляется 0, при сдвиге вправо слева дублируется предыдущее значение) o Циклический (вытесняемое из регистра значение заносится в освободившийся триггер на другом конце) Информатика 33 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Сдвиговый триггер Логический Арифметический Циклический Логический сдвиг влево Логический сдвиг вправо Арифметический сдвиг влево Арифметический сдвиг вправо СХЕМЫ Информатика 34 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Регистр с последовательным приемом и выдачей, реализующий сдвиг вправо Регистр с последовательным приемом и выдачей, реализующий сдвиг влево Регистр с последовательным приемом, параллельно-последовательной выдачей, реализующий сдвиг вправо Информатика 35 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Регистр с последовательным приемом, последовательной выдачей, с выбором направления счета Регистр с параллельно-последовательным приемом и выдачей, реализующий сдвиг вправо Универсальный сдвиговый регистр (на примере одного разряда) Информатика 36 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Задача: разработать простой кодовый замок для комбинации из 4 десятичных цифр Для управления записью в регистры потребуется комбинация счетчика и дешифратора. Счетчик будет подсчитывать количество нажатых клавиш, а дешифратор преобразовывать это количество в разрешающие сигналы для того регистра, который должен запомнить очередную нажатую клавишу. Сумматоры Сумматор – цифровое устройство, предназначенное для сложения двух чисел в разных кодах. Если используются специальные коды, то на сумматоре можно выполнять вычитание. Сумматоры По системам счисления Кол-во обрабатываемых разрядов Число входов и выходов Способ представления и обработки Возможность сохранения результата Межразрядные переносы 2 Одноразрядные Четвертьсумматоры Последовательный Комбинационный Последовательный перенос 2-10 Многоразрядные Полусумматоры Параллельный Накапливающий Параллельный перенос 10 Полные одноразрядные двоичные сумматоры Условный перенос другие Сквозной перенос Четвертьсумматор Четвертьсумматор – это простейший двоичный сумматор. Имеет два входа для двух одноразрядных чисел и один выход, на котором формируется сумма. Таблица истинности Четвертьсумматор основан на элементе «исключающее ИЛИ» и имеет такую же таблицу истинности. 𝒂 1 1 𝒃 1 1 𝒔 1 1 Полусумматор Полусумматор – это комбинационная схема, которая вырабатывает сигналы суммы (S) и переноса (C) как результат сложения двух одноразрядных чисел. Информатика 37 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Таблица истинности Полусумматор основан на элементах «исключающее ИЛИ» для суммы и «И» для переноса. 𝒂 1 1 𝒃 1 1 𝒔 1 1 𝒄 1 Функциональная схема Условное графическое обозначение Полный одноразрядный двоичный сумматор В отличие от полусумматора полный одноразрядный двоичный сумматор должен воспринимать 3 входных сигнала: 2 одноразрядных сигнала и сигнал переноса от предыдущего разряда. В качестве результата возвращает сумму и перенос в следующий разряд. Таблица истинности 𝒂𝒊 1 1 1 1 𝒃𝒊 1 1 1 1 𝒄𝒊 1 1 1 1 𝒔𝒊 1 1 1 1 1 𝒄𝒊+𝟏 1 1 1 1 Функциональная схема Многоразрядный сумматор параллельного действия с последовательным переносом Аргументы подаются одновременно по всем разрядам. Для сложения двух многоразрядных двоичных чисел на каждый разряд необходим один полный одноразрядный сумматор. Сумматор последовательного действия Сумматор последовательного действия состоит из одноразрядного сумматора, выход переноса которого соединен с его же входом переноса через элемент задержки (D-триггер). Операция суммирования во всех Информатика 38 Error! Use the Home tab to apply Заголовок 1 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. Error! Use the Home tab to apply Заголовок 2 to the text that you want to appear here. разрядах производится с помощью одного и того же сумматора последовательно во времени, начиная с младшего разряда. Резюме Данный курс является введением в цифровую автоматику и схемотехнику. Бла-бла-бла концовка лекций. Информатика 39