9) Логические схемы

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

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

3. В главе рассматриваются основные логические элементы и возможности их физической реализации; приводятся методики анализа и синтеза логических схем с использованием аппарата булевой алгебры.

ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

4.Элементарные логические операции над двоичными переменными реализуются схемами, которые называются логическими элементами. Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции.

5.Логическая функция реализуется логическим элементом ИЛИ (дизъюнктором) и изображается на схемах в следующем виде:

6.Логическая функция f(x1, x2, ..., xn) = x1 x2 ... xn реализуется логическим элементом И (конъюнктором):

7 . Логическая функция реализуется логическим элементом НЕ (инвертором):

8.Cхему, показывающую связи между различными логическими элементами, где сами элементы представлены условными обозначениями, называют логической (более корректно - функциональной) схемой.

9. Набор элементов для построения логической схемы является функционально полным, если реализуемые этими элементами булевы функции образуют функционально полную систему функций, т.е. с их помощью можно выразить любые другие логические функции. Дизъюнктор, конъюнктор и инвертор образуют функционально полный набор.

10. Сформулируем основные требования к логическим элементам вычислительных устройств.

Высокое быстродействие. Суть этого требования вполне ясна, так как именно быстродействие элементов определяет в конечном счете быстродействие вычислительной машины. Для логических элементов существенную роль в этом отношении играет время переключения.

Достаточно большая нагрузочная способность. Нагрузочная способность определяет число других элементов, которые можно подключать к выходу данного элемента, сохраняя нормальные условия его работы.

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

Малая потребляемая мощность. Потребляемая элементами мощность рассеивается, главным образом, в виде тепла. Большое тепловыделение нарушает режимы работы схем и ограничивает <плотность упаковки> элементов, что ведет к увеличению размеров элементов, а значит, и машины в целом.

Как можно меньшее количество физических элементов. Схемы, требующие меньшего количества физических элементов, оказываются эффективнее как с экономической точки зрения, так и с точки зрения надежности и долговечности.

10)Формула Шеннона

Существует множество ситуаций, когда возможные события имеют различные вероятности реализации. Например, если монета несимметрична (одна сторона тяжелее другой), то при ее бросании вероятности выпадения "орла" и "решки" будут различаться.

Ф ормулу для вычисления количества информации в случае различных вероятностей событий предложил К. Шеннон в 1948 году. В этом случае количество информации определяется по формуле: (2.2)

где I - количество информации;

N - количество возможных событий;

рi - вероятность i-го события.

Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут равны:

Р1 = 1/2, р2 = 1/4, р3 = 1/8, р4 = 1/8.

Тогда количество информации, которое мы получим после реализации одного из них, можно рассчитать по формуле (2.2):

I = -(l/2 log2l/2 + l/4 log2l/4 + l/8 log2l/8 + l/8 log2l/8) = (1/2 + 2/4 + 3/8 + 3/8) битов = 14/8 битов = 1,75 бита.

Этот подход к определению количества информации называется вероятностным.

Д ля частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (pi= 1/N), величину количества информации I можно рассчитать по формуле: (2.3)

По формуле (2.3) можно определить, например, количество информации, которое мы получим при бросании симметричной и однородной четырехгранной пирамидки:

I = log24 = 2 бита. Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной (1,75 бита), когда события неравновероятны.

Количество информации, которое мы получаем, достигает максимального значения, если события равновероятны.

Выбор оптимальной стратегии в игре "Угадай число". На получении максимального количества информации строится выбор оптимальной стратегии в игре "Угадай число", в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй - должен "угадать" задуманное число. Если рассмотреть эту игру с информационной точки зрения, то начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел).

При оптимальной стратегии интервал чисел всегда должен делиться пополам, тогда количество возможных событий (чисел) в каждом из полученных интервалов будет одинаково и отгадывание интервалов равновероятно. В этом случае на каждом шаге ответ первого игрока ("Да" или "Нет") будет нести максимальное количество информации (1 бит).

Как видно из табл. 1.1, угадывание числа 3 произошло за четыре шага, на каждом из которых неопределенность знаний второго участника уменьшалась в два раза за счет получения сообщения от первого участника, содержащего 1 бит информации. Таким образом, количество информации, необходимое для отгадывания одного из 16 чисел, составило 4 бита.

Таблица 2.1. Информационная модель игры "Угадай число"