Конспинф2

Стандарт 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

Почему это происходит? Пусть дано число 500310=10011100010112=011001001110001011. Последние две

цифры мантиссы оказались за пределами разрядной сетки. При обратном переводе в десятичную систему получим число 5000 – ближайшее округленное до кратного числу 4.

Формат числа половинной точности

Смещение (или сдвиг) порядка: 25−1 − 1 = 15 – число, которое необходимо прибавить к истинному порядку исходного числа. Оно записывается в биты поля Порядок. Для формата половинной точности под порядок выделяется 5 бит разрядной сетки, т.е. максимальное смещенное значение порядка – 31.

Информатика

7

Категории отображаемых значений

Лекция №4

Логические основы вычислительной техники

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

Комбинационные схемы = ( 1, … , ):

•Элементы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ, ИСКЛ-ИЛИ

•Мультиплексоры и демультиплексоры

•Шифраторы и дешифраторы

•Компараторы

•Комбинационные сумматоры

Простые цифровые автоматы ( + 1) = ( 1, … , , ( )):

•Триггеры

•Регистры

•Счетчики

Логическая переменная (в рамках классической двухзначной логики) – это переменная, которая может принимать только 2 значения: истина или ложь.

Логическая функция – функция от некоторых логических переменных, возвращающая значения на множестве

{Истина; Ложь}.

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

Если имеется логических переменных, то:

•Уникальных комбинаций значений переменных будет 2

•Всего возможно построить 22 уникальных логических функций

o Если переменная 1, то уникальных логических функций: 221 = 4. o Если переменных 2, то уникальных логических функций: 222 = 16.

Информатика

9

Однозначность взаимопреобразований

Логические функции от одной переменной

Инверсия логической переменной истинна, если сама переменная ложна, и наоборот. Обозначение: ( ) = ̅.

Инверсия часто используется как часть других схем на их входе или выходе. В этом случае она обозначается кружком.

Множество логических функций от двух переменных

Заметим, что уникальных функций всего 8. Каждой соответствует инверсированная пара, иными словами:

̅̅̅̅̅̅

= 15−, [0,15].

F1(x1,x2) – конъюнкция

Элементарная логическая функция (логическое произведение, И). Конъюнкция истинна тогда и только тогда, когда все ее аргументы истинны.

F7(x1,x2) – дизъюнкция

Элементарная логическая функция (логическое сложение, ИЛИ). Дизъюнкция истинна, если хотя бы один ее аргумент истинен.

Информатика

11

F6(x1,x2) – строгая дизъюнкция

Сложение по модулю 2, исключающее ИЛИ. Обозначение: .

F8(x1,x2) – Элемент Вебба (стрелка Пирса)

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

F14(x1,x2) – Функция штрих Шеффера

Реализует функцию И-НЕ. Является базисным элементом, т.е. только через И-НЕ можно реализовать любую функцию. Обозначение: |.

Прочие функции от двух переменных

•F13 – импликация ( 1 → 2)

•F2 – отрицание импликации

•F11 – обратная импликация ( 2 → 1)

•F4 – отрицание обратной импликации

•F12 – отрицание первого аргумента

•F9 – отрицание М2

•F12 – отрицание второго аргумента

Совершенные конъюнктивная и дизъюнктивная нормальные формы

Конъюнкт – конъюнкция некоторых переменных или их отрицаний.

Дизъюнкт – дизъюнкция некоторых переменных или их отрицаний.

Если конъюнкт (дизъюнкт) состоит из всех переменных функции или их отрицаний, где каждая переменная участвует лишь единожды, то такой конъюнкт (дизъюнкт) называется совершенным.

Минтерм (конституента единицы) – это логическая функция, принимающая значение истина только на одном наборе значений своих аргументов. Формальная запись минтерма – это конъюнкция всех аргументов функции, взятых с отрицанием или без него. Среди множества функций от переменных есть 2 минтермов. Минтерм – это совершенный конъюнкт.

Макстерм (конституента нуля) – это логическая функция, принимающая значение ложь только на одном наборе значений своих аргументов. Формальная запись макстерама – это дизъюнкция всех аргументов функции, взятых с отрицанием или без него. Среди множества функций от переменных есть 2 макстермов. Макстерм – это совершенный дизъюнкт.

Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конечного числа конъюнктов. Совершенная ДНФ

(СДНФ) – дизъюнкция совершенных конъюнктов (т.е. минтермов). Любая логическая функция, не являющаяся логическим нулем, имеет только одну СДНФ.

Конъюнктивная нормальная форма (КНФ) – конъюнкция конечного числа дизъюнктов. Совершенная КНФ

(СКНФ) – конъюнкция совершенных дизъюнктов (т.е. макстермов). Любая логическая функция, не являющаяся логической единицей, имеет только одну СКНФ.

Выполнимая логическая функция - логическая функция, не являющаяся константой нуля или константой единицы. Представления выполнимой логической функции в виде СКНФ или СДНФ равнозначны, но иногда требуют разного количества операций.

Информатика

12

Логические законы и правила

•Коммутативный

= ,

+ = +

•Ассоциативный

( ) = ( ) ,

+ ( + ) = ( + ) +

•Дистрибутивный

( + ) = + ,

+ = ( + )( + )

•Закон двойного отрицания

̅ =

•Закон идемпотентности

= ,

+ = ,

̅ = 0, + ̅ = 1

•+ 0 = ,

+ 1 = 1,

0 = 0,

1 =

Информатика

13

̅̅̅̅̅̅̅̅ ̅

+ = ,

̅̅̅̅ ̅

= +

•Правило раскрытия импликации

→ = ̅ +

•Правила раскрытия эквивалентности

≡ = ( → )( → ),

≡ = + ̅ ̅

•Правило раскрытия строгой дизъюнкции

= ̅ + ̅

Лекция №5

Минимизация логических функций

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

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

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

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

Метод эквивалентных логических преобразований

Получение МДНФ (МКНФ) через упрощение СДНФ (СКНФ) по правилам преобразования.

Диаграмма Вейча (карта Карно)

Графический способ минимизации логических функций. Работает на основе операций склеивания и поглощения. Представляет собой особым образом переупорядоченную таблицу истинности.

Информатика

14