- •Информатика - 2
- •Учебное пособие предназначено для бакалавров направления 230200 «Информационные системы».
- •Учебно-методическим центром
- •Содержание
- •Введение
- •Логические основы информатики. Основные понятия и определения
- •Основные понятия и определения алгебры логики
- •1.3. Переключательные функции одного и двух переменных
- •Вопросы по лекции
- •Преобразования логических выражений
- •2.1. Понятие синтеза комбинационных схем
- •2.2. Логические элементы
- •2.3. Аналитическая запись переключательной функции. Построение схем на элементах заданного базиса
- •Вопросы по лекции
- •Комбинационные схемы и конечные автоматы.
- •Синхронный rs-триггер с дополнительным входом установки исходного состояния
- •Двухтактный d-триггер
- •Самым универсальными и сложными являются jk-триггеры. Они могут строиться как со статическим, так и с динамическим управлением. Универсальный jk-триггер
- •Регистры
- •Последовательный регистр
- •Счетчики. Суммирующий счетчик.
- •Вычитающий счетчик. Реверсивный счетчик.
- •Одноразрядный двоичный сумматор
- •Многоразрядные сумматоры
- •Дешифраторы
- •Мультиплексор
- •Демультиплексор
- •Вопросы
- •4. Функциональная и структурная организация эвм
- •4.1. Понятие функциональной и структурной организации
- •4.2. Структура эвм
- •4.2. 1 Процессор
- •Функции процессора:
- •4.2.2. Память эвм
- •4.2.3. Устройство ввода/вывода
- •4.3. Функционирование эвм.
- •1 Счетчик команд Счетчик команд . Фаза чтения машинной команды из озу и запись машинной команды в регистр команд.
- •2.Фаза дешифрации кода операции машинной команды.
- •3.Фаза выполнения машинной команды.
- •4. Переход к выполнению следующей машинной команды
- •2. Структура машинных команд
- •Способ адресации
- •Система операций
- •Вопросы
- •5. Понятие ФайлА и файловОй системЫ
- •Структура данных на магнитном диске
- •Вопросы
- •6. Таблица размещения файлов fat. Базы данных. Основные типы данных.
- •6.1. Таблица размещения файлов fat
- •Структура fat
- •Основные типы данных
- •Обобщенные структуры или модели данных
- •7. Информационная модель канала передачи
- •7.1. Формы представления информации. Виды сигналов.
- •7.2. Спектральное представление сигнала
- •8. Средства коммуникаций и мировые сети
- •8.1.Организация межкомпьютерной связи
- •8.2. Компьютерные сети
- •8.2.1. Топология сетей
- •8.2.2. Наиболее распространенные виды топологий сетей
- •8.2.3. Методы соединения устройств сети
- •8.2.4. Классификация компьютерных сетей по степени географического распространения
- •8.3.Методы соединения локальных сетей.
- •8.4.Способы соединения беспроводных сетей
- •8.7. Сеть интернет
- •16.7.1. Способы связи сетей в Интернет
- •16.7.1.1. Протоколы
- •8.7.2.2. Адреса компьютеров в сети Интернет
- •8.7.3. Основные возможности, предоставляемые сетью Интернет
- •1. World Wide Web — главный информационный сервис.
- •Вопросы
- •9. Основы кодирования информации
- •9.1. Кодирующее отображение
- •9.2. Префексные коды
- •9.3. Оптимальное кодирование
- •9.3.1. Код Шеннона -Фано
- •9.3.2. Блочное кодирование
- •9.3. Код Хафмана
- •Помехоустойчивое кодирование Назначение помехоустойчивых кодов
- •Помехоустойчивое кодирование
- •9.1.4. Инверсный код
- •9.2. Корректирующие коды
- •9.2.1. Код Хемминга
- •Вопросы
- •10. Защита информации безопасность информации и необходимость ее защиты
- •Стандарты по защите информации
- •Группы и модели нарушителей
- •Уровни информационной защиты
- •Межсетевые экраны
- •Криптография. Идентификация пользователей
- •Вопросы
- •Федеральный закон Российской Федерации от 27 июля 2006 г. N 149-фз Об информации, информационных технологиях и о защите информации.
2.3. Аналитическая запись переключательной функции. Построение схем на элементах заданного базиса
Для аналитического представления ПФ используют правило ее записи по единицам:
в таблице истинности выбирают все наборы, на которых ПФ равна единице;
выписывают произведения аргументов, соответствующих этим наборам (при этом, если в этом наборе аргумент равен 1, то он вписывается в произведение без изменения, если же он равен 0, то он вписывается со знаком отрицания);
все полученные произведения соединяются знаком дизъюнкции.
Пример 2.2. Построить схему сумматора по модулю два на элементах И, ИЛИ, НЕ. Таблица истинности для ПФ f6(x1,x2) логической неравнозначности представлена в табл.1.3.
В соответствии с правилом записи ПФ по единицам получим:
Тогда схема сумматора по модулю два будет иметь вид (рис.2.12):
Рис. 2.12. Схема сумматора по модулю два на элементах И, ИЛИ, НЕ
Можно построить схему сумматора только на элементах И-НЕ. Для этого, используя формулы де Моргана, преобразуем выражение f6(x1,x2) следующим образом:
По этому выражению построим схему сумматора по модулю два на элементах И-НЕ (рис.2.13):
Рис.2.13. Схема сумматора по модулю два на элементах И-НЕ
Сумматор по модулю два можно построить и на элементах ИЛИ-НЕ:
Схема представлена на рис.2.14.
Рис.2.14. Схема сумматора по модулю два на элементах ИЛИ-НЕ
Вопросы по лекции
-
Что такое синтез комбинационной схемы?
-
Дайте определение логического элемента.
-
Чему равна функция ?
-
Чему равна функция ?
-
Чему равна функция ?
-
Чему равна функция ?
-
Чему равна функция ?
-
Когда сигнал на выходе логического элемента ИЛИ равен 1?
-
Когда сигнал на выходе логического элемента И равен 1?
-
Когда сигнал на выходе логического элемента НЕ равен 1?
-
Когда сигнал на выходе сумматора по модулю два равен 1?
-
Построит логическую схему используя элементы И-НЕ или ИЛИ-НЕ:
3. ЭВМ – средство обработки информации.
Комбинационные схемы и конечные автоматы.
При любых видах работы с информацией всегда идет речь о ее представлении в виде определенных символических структур. Любое устройство обработки дискретной информации имеет n входов и m выходов. Сигналы на входах соответствуют символам входного алфавита, а выходные – символам выходного алфавита.
Имеются два типа устройств обработки цифровой информации: на основе комбинационных схем и на основе конечных (цифровых) автоматов.
В комбинационных схемах совокупность входных сигналов (входное слово) однозначно определяет совокупность (комбинации) выходных сигналов (выходное слово).
Закон функционирования комбинационной схемы может быть задан несколькими способами. Можно определить таблицу истинности, или систему уравнений булевой алгебры для каждого выхода схемы, или функциональную схему на основе одного из базовых наборов логических элементов.
Синтез комбинационных логических устройств включает в себя составление формализованного задания, преобразование логической функции с целью оптимизации с учетом имеющейся (выбранной) элементной базы и построение принципиальной схемы. В качестве исходных данных может выступать описательное задание, логическая функция или таблица истинности. Преобразование осуществляют с помощью теорем и положений алгебры логики.
Абстрактным синтезом называют последовательность этапов, в результате которой получают функциональную схему комбинационного логического устройства на основе полученных в результате синтеза формальных представлений (таблицы истинности и логических уравнений).
Схему, показывающую связи между логическими элементами, где сами элементы представлены в виде условных обозначений, называют функциональной.
Совершенной нормальной дизъюнктивной формой (СНДФ) называют запись логического уравнения в виде дизъюнкции (логической суммы) минтермов. Минтерм - это коньюнкция входных переменных, соответствующая в таблице истинности единичному значению выходной функции
Совершенной нормальной конъюктивной формой (СНКФ) называют запись логического уравнения в виде конъюнкции (логического произведения) макстермов. Макстерм - это дизьюнкция инверсий входных переменных соответствующая в таблице истинности нулевому значению выходной функции.
В отличие от комбинационных схем конечные автоматы имеют конечное число внутренних состояний.
Выходное слово и переход автомата в следующее состояние однозначно определяются состоянием автомата и входным словом.
Функционирование конечного автомата задается:
-
входным алфавитом: X {x0, x1, x2,…, xi,… xn},
-
выходным алфавитом: Y{у0, y1, y2,…, yi,… ym},
-
алфавитом состояний: Q {q0, q1, q2,…, qi,… qr,}, где q0 – начальное состояние автомата,
-
функцией переходов, определяющей переход автомата из qi состояния в следующее qi+1 состояние: qi+1 = (qi, xi), или как функция времени: Q(t+1) = [Q(t), X(t)].
-
функцией выходов, определяющей выходные сигналы автомата в состоянии qi: yi = (qi, xi) или, как функция времени: Y(t) = [Q(t), X(t)].
Функция выходов (5) соответствует конечному автомату, называемому автоматом Мили. Имеется несколько разновидностей конечных автоматов, используемых в устройствах цифровой обработки. Широко используемой альтернативой автомату Мили является автомат Мура.
Особенностью автомата Мура является его функция выходов. В автомате Мура выходные сигналы зависят только от состояния конечного автомата qi.: yi = (qi) или, как функция времени: Y(t) = [Q(t)].
Основное отличие устройств на основе цифровых автоматов от комбинационных схем заключается в том, что первые содержат элементы памяти для фиксации состояний. Можно считать комбинационные схемы примитивными цифровыми автоматами с одним состоянием.
Элементы памяти цифровых автоматов – триггеры, в свою очередь являются элементарными цифровыми автоматами (автоматами Мура) с двумя устойчивыми состояниями.
Цифровые автоматы могут задаваться графами или таблицами выходов и переходов.
Элементарные автоматы (триггеры)
Электронные цифровые элементы памяти – триггеры, используемые в ЭВМ в качестве ячеек быстрой (статической) памяти, последовательностных схем (регистры сдвига, счетчики) являются простейшими автоматами. Их выходные сигналы зависят не только от комбинаций входных сигналов , но и от значений самих выходных сигналов в предшествующий момент времени.
Триггером называют последовательностную схему с положительной обратной связью и двумя устойчивыми состояниями 0 и 1 (то есть триггер обладает свойством памяти). В общем случае триггер может иметь асинхронные входы предварительной установки, тактовый (синхронизирующий) и информационные входы. К основным типам триггеров относятся:
триггер с раздельной установкой состояний (RS-триггер),
триггер "защелка" (D - триггер),
универсальный триггер (JK - триггер),
триггер со счетным входом (T - триггер).
По способу записи информации триггеры подразделяются на асинхронные и синхронные или тактируемые, а по способу управления - на триггеры со статическим управлением (единичным или реже нулевым уровнем тактового сигнала) и триггеры с динамическим управлением (положительным - из 0 в 1, или отрицательным - из 1 в 0) фронтом тактового сигнала. В последнем случае говорят о триггерах с прямым или инверсным динамическим входом управления.
Основу триггера составляет кольцевая схема из двух инверторов (рис.3.10). Если левый инвертор на выходе имеет единичный сигнал, то он передается на вход правого инвертора. На выходе правого формируется нулевой сигнал, который передается (по цепи обратной связи) на вход левого инвертора. На выходе левого инвертора подтверждается единичный сигнал. Таким образом, это состояние является устойчивым состоянием, которое может сохраняться сколько угодно долго.
В силу симметрии схемы возможно второе устойчивое состояние, при котором на выходе левого инвертора сохраняется нулевой сигнал, а на правом – единичный. Следовательно, представленная схема является схемой элемента с двумя устойчивыми состояниями. Но это еще не триггер. Триггер должен содержать входы, сигналами на которых можно управлять состоянием триггера.
Асинхронный триггер RS-триггер
Асинхронный триггер с раздельной установкой состояний (RS-триггер) имеет два входа:
S (set) – установить (в единичное состояние),
R (reset) – сбросить (установить в исходное состояние).
В таблице 3.1 представлены переходы RS-триггера, а на рис.3.2 – схема и обозначение RS-триггера на функциональных схемах.
Таблица 3.1. |
|||
Переходы RS-триггера |
|||
t |
t+1 |
||
R |
S |
Q(t) |
Q(t+1) |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
не определено |
1 |
1 |
1 |
не определено |
Для RS-триггера существует комбинация входных сигналов (два единичных сигнала, поданных одновременно на входы R и S), которая переводит триггер в неопределенное (неустойчивое) состояние. Это запрещенная комбинация. При этих комбинациях входных сигналов триггер может случайным образом перейти в любое из двух состояний. Для правильного функционирования триггера появление запрещенной комбинации на его входах должно быть исключено.