ГЛАВА 14 На пороге цифрового века

Математическая логика и ее представление в технических устройствах

— Теперь давайте сочтем, сколько у нас всего. Портос?

— Тридцать экю.

— Арамис?

— Десять пистолей.

— У вас, Д'Артаньян?

— Двадцать пять.

— Сколько это всего? — спросил Атос.

— Четыреста семьдесят пять ливров! — сказал д'Артаньян, считавший, как Архимед.

А. Дюма. Три мушкетера

Все началось, конечно, с Аристотеля, который жил в IV веке до нашей эры. Когда читаешь вступление к любой популярной книге, посвященной чему угодно: от изящных искусств до биологии, химии, физики и математики, — возникает впечатление, что Аристотель был каким-то сверхчеловеком. В самом деле, гении встречаются, но нельзя же быть гением настолько, чтобы разработать основы вообще всего, на чем зиждется современная цивилизация! Тем не менее, и авторы не врут, и Аристотель сверхчеловеком не был. Во-первых, знаний было тогда накоплено еще не очень много, и обозреть их все — задача вполне посильная для человека острого ума и выдающихся способностей. Во-вторых, Аристотель работал не один, его метод — коллективный мозговой штурм, это просто история донесла до нас фактически одно только его имя.

Но главное, пожалуй, в другом — древние рассматривали упомянутые нами дисциплины во взаимосвязи. Аристотель четко разделил только науку и ремесла («техно», по-гречески), наука же делились на практические (этику и политику) и теоретические (физику и логику) дисциплины, но и они рассматривались как составные части единой науки. В чем древние, конечно, были более правы, чем мы, вынужденно поделившие области человеческой деятельности на множество автономных разделов.

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

Выдвинутые Аристотелем законы логики, которые с его же подачи стали идентифицироваться с законами мышления вообще, неоднократно пытались привести в математическую форму. Некто Луллий в XIII веке попытался даже механизировать процесс логических рассуждений, построив «Всеобщий решатель задач» (несомненно, это была первая попытка построения «думающей машины»). Формализацией логики занимался Лейбниц, искавший универсальный язык науки, и в конце концов все сошлось в двух работах английского математика Джорджа Буля, который жил и работал уже в середине XIX века. Любопытно название второй из этих работ — «Исследование законов мышления», первая же работа называлась поскромнее, но без «мышления» и тут не обошлось, — в названии фигурировало слово «рассуждения». То есть и сам Буль, и еще сто лет после него, до середины XX века, и все его предшественники в течение двух с большим лишком тысяч лет, прошедших со времен Аристотеля, — никто так и не усомнился, что в основе мышления лежит именно та логика, которая называется «аристотелевой». И лишь в XX веке, после работ Геделя и Тьюринга, и особенно в связи с благополучно провалившимися (как и у Луллия за 700 лет до того) попытками создания «искусственного интеллекта», до ученых, наконец, начало доходить, что мышление вовсе не имеет логической природы, а логика есть лишь удобный способ сделать свои рассуждения доступными окружающим.

Главное же следствие возникновения математической логики выявилось совсем не в исследованиях мышления, где оно виделось Лейбницу и Булю. Его обозначил в своей магистерской диссертации от 1940 года великий Клод Шеннон (рис. 14.1) — оказалось, что булевы законы в точности совпадают с принципами функционирования релейных электрических схем. Что самое поразительное — все компоненты, необходимые для моделирования законов логики с помощью электрических устройств (реле, выключатели), были известны еще до публикации Булем своих работ, но в течение еще почти ста лет никто не обращал на это внимания (Шеннон скромно утверждал, что случилось так, что до него просто никто не владел математикой и электротехникой одновременно). Не обратил на это внимание даже Чарльз Бэббидж, сконструировавший еще задолго до работ Буля механическую вычислительную («аналитическую») машину, — а ведь был знаком и с самим Булем, и с его работами!

Рис. 14.1. Клод Элвуд Шеннон (Claude Elwood Shannon), 1916–2001

_{Фото Lucent Technologies Inc /Bell Labs}

Основные операции алгебры Буля

Булева алгебра имеет дело с абстрактными логическими переменными. Эти переменные можно интерпретировать по-разному, но интерпретацию мы пока отложим.

Вне зависимости от интерпретации, для логических переменных определены некоторые операции, подчиняющиеся определенным правилам. Базовые операции такие:

□ операция логического сложения двух операндов — операция объединения, операция «ИЛИ» («OR»), обозначается обычным знаком сложения;

□ операция логического умножения двух операндов — операция пересечения, операция «И» («AND»), мы будем обозначать ее крестиком, чтобы отличить от обычного умножения;

□ операция отрицания для одного операнда — операция «НЕ» («NOT»), обозначается черточкой над символом операнда.

В математике операция логического сложения (дизъюнкция) обозначается еще знаком v, а умножения (конъюнкция) — ^. Кроме того, операция умножения часто обозначается знаком &, и это обозначение нам встретится, когда мы перейдем к микросхемам. Остальные операции могут быть записаны как сочетания этих трех основных.

Любая конкретная интерпретация булевых операндов — математическая или техническая — должна отвечать правилам булевой алгебры. Например, оказалось, что этим правилам отвечают множества (отсюда другие названия тех же операций: «пересечение» и «объединение»). Программисты имеют дело с логическими переменными 0 и 1, которые также есть одно из представлений булевых операндов.

Следует отчетливо понимать, что вне зависимости от интерпретации (включая и напряжения в релейных цепях по Шеннону), любые булевы объекты ведут себя одинаково: так, операция пересечения множеств совершенно адекватна операции «И» с логическими переменными или соответствующей манипуляции с выключателями в электрической сети.

В булевой алгебре многое совпадает с обычной — например, справедливы правила типа А + В = В + А или А + (В + С) = (А + В) + С), но для нас важны как раз отличия.

Вот они: А + А = А (а не 2А, как было бы в обычной алгебре), а также А х А = А (а не А²). Последнее уравнение в обычной алгебре, впрочем, имело бы решение, причем сразу два: 0 и 1. Таким путем обычно и переходят к интерпретации булевых операндов, как логических переменных, которые могут иметь только два состояния: 1 и 0 или «правда» (true) и «ложь» (false). В этом представлении мы действительно можем попробовать с помощью определенных ранее операций записывать некоторые высказывания в виде уравнений и вычислять их значения, что дает иллюзию формального воспроизведения процесса мышления. Но сначала надо определить, как и в обычной алгебре, правила, которым подчиняются операции, — т. е. таблицу логического сложения и таблицу логического умножения. Они таковы:

Операция отрицания «НЕ» меняет 1 на 0 и наоборот.

Примеры записи логических выражений обычно приводят для каких-нибудь бытовых высказываний, но мы поступим нетрадиционно: приведем пример из области математики. Пусть высказывание состоит в следующем:«x меньше нуля или х больше 1 и у меньше 2». Как записать это высказывание? Введем следующие логические переменные: А = (х < 0); В = (х > 1); С = (у < 2). Как мы видим, все они могут принимать только два значения: «правда» (если условие выполняется) и «ложь» (если не выполняется). Обозначим значение всего выражения через D. Тогда высказывание записывается так:

D = (A + B) x C (1)

Можно записать и так:

D = (A ИЛИ B) И C

Или так:

D = (A OR B) AND C

Или, наконец, так:

D = ((х < 0) OR (х > 1)) AND (у < 2)

Последняя запись хорошо знакома всем, кто изучал язык программирования Pascal. На языке С та же запись выглядит непонятнее:

D =((x < 0)||(x > 1))&&(y < 2)

* * *

Подробности

О великий и могучий язык С! В нем самую простую вещь можно запутать до полной потери смысла. В нашем случае то же самое выражение можно было бы записать, как ((х < 0) | (х > 1)) & (у < 2), и ничего бы не изменилось. В этом языке (в отличие от Pascal) есть две разновидности логических операций: обычные («логическое И» &&, «логическое ИЛИ» ||) и поразрядные («поразрядное И» &, «поразрядное ИЛИ» |). Есть и, соответственно, «логическое НЕ» (!) и «поразрядное НЕ» (~). Термин «поразрядные» означает, что они применимы к многоразрядным двоичным числам. В результате их применения тоже получается многоразрядное двоичное число, необязательно ноль или единица, как в случае логических. Поскольку наши результаты операций сравнения содержат только один двоичный разряд (либо соблюдается, либо не соблюдается), то в данном случае логические и поразрядные операции оказываются идентичны, и можно писать и так, и так. А вот если в операциях участвуют обычные числа, то результат будет разный: «10&&7» равно «логической 1» (отличное от нуля значение всегда интерпретируется, как «правда»), тогда как «10&7» равно 2 (почему, будет рассказано далее). Как мы узнаем в главе 21, эти особенности играют большую роль в программировании микроконтроллеров на языке С.

* * *

Пусть х = 0,5, у = 1. Чему будет равно D в этом случае? Очевидно, что выражение (А + В) примет значение «ложь» (0), поскольку х не удовлетворяет ни одному из условий А и В. Переменная С примет значение «правда» (1), но на результат это уже не повлияет, т. к. произведение 0 на 1, согласно таблице логического умножения, равно 0. То есть D в данном случае есть «ложь». Если же принять значение х = -0,5, оставив у равным 1, то D примет значение «правда».

Интересный оборот примут события, если вместо «OR» между А и В поставить «AND», — легко догадаться, что выражение в скобках тогда не будет «правдой» ни при каком значении х, поскольку условия «х меньше 0» и «х больше 1» взаимоисключающие. Потому результирующее условие D всегда будет принимать значение 0, т. е. «ложь». Но вот если мы изменим выражение следующим образом:

(2)

то есть инвертируем выражение в скобках с помощью операции «НЕ», то получим обратный результат: D всегда будет «правдой» (черточкой над символом или выражением как раз и изображается инверсия). Интересно, что тот же самый результат мы получим, если запишем выражение следующим образом:

(3)

Это свойство выражается в так называемых правилах де Моргана (учителя Буля):

Отметим, что из таблиц логического умножения и сложения вытекает еще одно любопытное следствие. Дело в том, что ассоциация значения «ложь» с нулем, а «правды» с единицей (положительная логика), есть действие вполне произвольное — ничто не мешает нам поступить наоборот (отрицательная логика). Такая замена приводит к тому, что все операции «ИЛИ» меняются на «И» и наоборот (рассмотрите таблицы внимательно). А вот операция «НЕ» к такой замене индифферентна — 0 меняется на 1 в любой логике.

Далее приведены несколько соотношений, которые вместе с правилами де Моргана помогают создавать и оптимизировать логические схемы. Некоторые из них очевидны, иные же — совсем нет.

Ассоциативный закон умножения:

A x B x C = (A x B) x C = A x (B x C)

Ассоциативный закон сложения:

A + B + C = (A + B) + C = A + (B + C)

Другие формулы:

Булева алгебра на выключателях и реле

Для того чтобы представить булевы переменные и операции над ними с помощью технических устройств (то, что сделал Клод Шеннон в своей диссертации), надо придумать схемы, которые воспроизводили бы эти операции согласно изложенным правилам. Для этого осталось сделать только один шаг: пусть наличие напряжения (высокий уровень напряжения) в некоторой точке цепи представляет собой логическую единицу, а отсутствие напряжения (низкий уровень) — логический ноль. В этом случае логика носит название «положительной». Если принять за единицу низкий уровень, а за ноль — высокий, логика будет «отрицательной». Как мы уже знаем, переход с положительной логики на отрицательную означает замену всех «И» на «ИЛИ» и наоборот. В дальнейшем, если это специально не оговорено, мы всегда будем иметь в виду положительную логику.

Самые простые варианты схем, реализующих базовые логические операции в этом случае, показаны на рис. 14.2.

Рис. 14.2. Схемы реализации логических функций на кнопочных выключателях

Здесь операции «И» и «ИЛИ» выполняются обычными кнопками без фиксации. Каждая из них соответствует одной логической переменной, которая принимает значение 1, если контакты замкнуты, и 0 — если разомкнуты. На выходе значению 0 соответствует погасший светодиод, значению 1 — горящий. Легко понять, что работать эти схемы будут именно так, как указано в таблицах для соответствующих логических операций. Для технических устройств правила соответствия входов и выхода называются «таблицами истинности» (или «таблицами состояния») и показаны в табл. 14.1.

Однако если разобраться поглубже, то придется констатировать, что настоящими входными логическими переменными для таких схем являются движения пальца, нажимающего на кнопку. В частности, операция «НЕ» здесь будет означать нажатие на кнопку с замкнутыми контактами, а каскадное соединение таких схем для реализации сложных выражений предполагает наличие человека, транслирующего выходной сигнал одной схемы (состояние светодиода) во входной другой схемы (состояние контактов). Логично поставить вместо такого человека, тупо выполняющего предопределенные действия, техническое устройство. И здесь помогут уже хорошо нам известные электромагнитные реле.

В схемах на рис. 14.3 как для входов, так и для выхода наличие напряжения соответствует логической 1, отсутствие его — логическому 0. (Можно для наглядности подключить к выходу светодиод или лампочку, но суть дела от этого не изменится.)

Рис. 14.3. Схемы реализации логических функций на реле.

Способ подачи входного сигнала не указан, т. к. предполагается, что источник входного напряжения может быть произвольным (разумеется, его мощность должна быть достаточной, чтобы заставить реле сработать) — в том числе и такая же схема на реле. Это иллюстрируется схемой на рис. 14.3 справа, где изображена схема составного элемента «И-НЕ» на трех реле, представляющего собой объединение элемента «И» (такого же, как на рисунке слева) и элемента просто «НЕ» (инвертора), который есть не что иное, как одиночное реле с выходом через нормально замкнутые, а не нормально разомкнутые контакты.

Таблица истинности для элемента «И-НЕ», показанная в табл. 14.2, будет инверсией, представленной в табл. 14.1, таблицы истинности для элемента «И». Легко видеть, что она не совпадает с таблицей для «ИЛИ», как могло бы показаться на первый взгляд. Аналогично составляется элемент «ИЛИ-НЕ» — из схемы «ИЛИ», показанной на рис». 14.3 посередине, и инвертора. Таблица истинности для него также представлена в табл. 14.2.

В большинстве современных применений логических микросхем используются именно элементы «И-НЕ» и «ИЛИ-НЕ», а не чистые «И» и «ИЛИ», — так удобнее и для разработчиков микросхем (где в качестве ключей служат транзисторы, которые инвертируют сигнал, см. далее), и для схемотехников. Для того чтобы было проще разбираться в логических схемах, не заучивая таблицы истинности, работу элементов можно запомнить следующим образом: элемент «И» дает единицу на выходе только, если на входах одновременно есть единица, элемент «ИЛИ» — если хотя бы на одном из входов единица. Возможно, вам еще проще будет запомнить так: элемент «ИЛИ» дает единицу на выходе, если на входах «хотя бы одна единица», а элемент «И» дает ноль на выходе, если на входах «хотя бы один ноль». Элементы с инверсией по выходу будут давать в тех же случаях обратные значения.

Интересно рассмотреть вопрос — а нельзя ли упростить схемы этих комбинированных элементов, исключив из них третье реле, выполняющее инверсию? В самом деле, большинство реле имеют перекидные контакты, так за чем же дело стало — меняем нормально разомкнутые контакты на нормально замкнутые, и все! Легко заметить, что такая замена не будет адекватной — мы инвертируем здесь не общий выход элемента, а выходы каждого реле в отдельности, что равносильно инвертированию входов. Если обратиться к правилам де Моргана, то мы увидим, что такое изменение схемы приведет к тому, что элемент «И» превратится в «ИЛИ-НЕ», а «ИЛИ», соответственно, в «И-НЕ». Я советую читателю посидеть над этими соображениями и вывести таблицы истинности самостоятельно, чтобы убедиться, что все сказанное — правда. Другое полезное упражнение состоит в том, чтобы попытаться самому построить трехвходовые элементы, соответствующие уравнениям А + В + С и А х В х С (они будет состоять из трех реле).

Тем, кто не разобрался как следует в этом по необходимости кратком изложении, среди прочих источников особенно порекомендую обратиться к [16] — книге, написанной очень простым и понятным языком, ориентированным на неподготовленного читателя, но вместе с тем излагающей предмет во всех подробностях.

То же самое, но на транзисторах и диодах

Ясно, что использование реле для построения логических схем — метод, мягко говоря, несовременный. Хотя в истории и отмечены случаи построения целых компьютеров на основе реле (к ним принадлежали, в частности, легендарные Mark-I и Mark-II Говарда Эйкена, запущенные в эксплуатацию в 1944 и 1947 гг., соответственно), но у них было слишком много недостатков: прежде всего, крайне низкие надежность и быстродействие, порядка 20–30 Гц (не килогерц и тем более не мегагерц, а именно герц). Конечно, по сравнению с электромеханическими ручными калькуляторами это было просто сказкой (типовое время операции сложения у Mark-I составляло 0,3 с, т. е. в десятки и сотни раз превышало «быстродействие» человека с механическим калькулятором), и машины эти широко использовались на практике. Тем не менее, такое быстродействие казалось уже тогда недостаточным, потому довольно быстро перешли к использованию ламп, что позволило достичь порогов в десятки и сотни килогерц, а затем и транзисторов, с которыми частота работы возросла до единиц и десятков мегагерц.

* * *

Легенда о «баге»

С использованием реле в компьютерной технике связана легендарная история о возникновении термина «баг», как ошибки в программе. В буквальном переводе «bug» означает «жучок». В 1947 году между контактами одного из реле Mark-II застряла мошка, вызвав неисправность. Когда мошку извлекли, молодая сотрудница Эйкена Грейс Хоппер (позднее — крупнейший авторитет в программировании и единственная в истории женщина-адмирал флота США) приклеила ее между страницами лабораторного журнала с подписью: «первый случай выловленного бага». Страница эта сейчас хранится в музее Смитсоновского института.

* * *

Как же можно построить наши логические элементы на транзисторах? На рис. 14.4 показаны для примера схемы так называемой диодно-транзисторной логики, которая широко использовалась в производстве гибридных микросхем (т. е. еще до изобретения Нойсом и Килби твердотельной микросхемы, см. главу 11).

Рис. 14.4. Схемы реализации логических функций на диодах и транзисторах

В элементе «И-НЕ» (слева) в нормальном состоянии транзистор открыт, и на выходе его логический ноль, так что подача логической единицы на входы ничего не изменит. А подача логического нуля хотя бы на один из входов приведет к тому, что соответствующий диод откроется и станет шунтировать переход база-эмиттер, в результате чего транзистор закроется, и на выходе возникнет логическая единица, что соответствует функции «И-НЕ». Диод в эмиттере нужен для обеспечения надежного запирания транзистора.

На схеме справа наоборот, транзистор в нормальном состоянии заперт, и на выходе логическая единица, а подача хотя бы одной логической единицы на входы откроет соответствующий диод и через него — транзистор, на выходе тогда установится логический ноль, что соответствует функции «ИЛИ-НЕ». «Подпирающий» диод здесь не требуется, зато требуются токоограничивающие резисторы на входах.

Схему инверсии «НЕ» специально рисовать не имеет смысла, т. к. любой транзистор, включенный по схеме с общим эмиттером, как мы знаем из главы 6, есть инвертор.

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

В этих схемах всплывает один вопрос, который для релейных схем был неактуален: с какого именно уровня напряжение считать логическим нулем, а с какого — единицей? В релейных схемах ноль — это полный разрыв цепи, а единица — полное ее замыкание. Здесь же не совсем так: на коллекторе открытого транзистора в левой схеме будет напряжение около 0,8–1 В, в то время как в правой — всего около 0,2–0,3 В. В то же время при закрытом транзисторе вроде бы напряжение логической единицы должно быть равно напряжению питания (токами утечки пренебрегаем). Однако оно тут же упадет, если мы нагрузим выход входом другой схемы типа «ИЛИ-НЕ», поскольку там требуется обеспечить определенный ток базы.

Поэтому для транзисторов и микросхем задают не точный порог изменения с нуля на единицу, который, как мы видим, непостоянен, а пределы: ниже определенного значения считают выход находящимся в состоянии нуля (для схем на рис. 14.4 подойдет значение 1,2–1,5 В), а выше другого определенного значения (например, при питании 5 В пусть это будет 3,5 В) — в состоянии логической единицы. В промежутке схему считают находящейся в нерабочем режиме (в зоне неопределенности). При этом приходится ограничивать число устройств, подключаемых одновременно к выходу (или потребляемый по выходу ток). Для того чтобы расширить возможности таких схем, в серию одинаковых по типу применяемой схемотехники микросхем вводят специальные чипы буферов — т. е. усилителей мощности сигнала, которые никакой логической функции не осуществляют, а просто усиливают сигнал по току. Иногда такие буферы совмещают с функцией инверсии. Но прежде чем мы перейдем к логическим микросхемам, необходимо немного углубиться в теорию и терминологию и понять, что такое двоичные коды и как двоичная арифметика соотносится с булевой алгеброй.

О двоичной и других системах счисления

О том, что мы считаем в десятичной системе потому, что у нас десять пальцев на двух руках, осведомлены, вероятно, все. У древних ацтеков и майя в ходу была двадцатеричная система (вероятно потому, что закрытая обувь в их климате была не в моде). Вместе с тем, история показывает, что привязка к анатомическим особенностям строения человеческого тела совершенно необязательна. Со времен древних вавилонян у нас в быту сохранились остатки двенадцатеричной и шестидесятеричной систем, что выражается в количестве часов в сутках и минут в часах или, скажем, в том, что столовые приборы традиционно считают дюжинами или полудюжинами (а не десятками и пятерками). Так что само по себе основание системы счисления не имеет значения — точнее, оно есть дело привычки и удобства.

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

Позиционные и непозиционные системы счисления.

Десятичная система

Число — одна из самых удивительных абстрактных сущностей. Нет никаких сомнений, что число, количество предметов — есть вполне объективно существующая характеристика. В отличие, к примеру, от понятия цвета, она совершенно независима от самого факта наличия разума у считающего субъекта и даже от наличия самого субъекта. Тем не менее, материального воплощения числа не имеют — «количество», представленное в виде комбинации пальцев рук и ног, зарубок на палочке (вспомните, как Робинзон Крузо вел свой календарь), разложенных на земле веточек, костяшек на счетах или — что для нас самое главное! — черточек или значков на бумаге, есть всего лишь физическая модель некоего идеального абстрактного понятия «числа». Умение считать в уме, которое отличает цивилизованного человека от дикаря, и состоит в том, что мы можем оторваться от такой материальной модели и оперировать непосредственно с абстракцией.

Из понятия числа, как объективно существующей абстракции, вытекает, что его материальное представление может быть произвольным, лишь бы оно подчинялось тем же правилам, что и сами числа (совершенно аналогично булевым переменным). Проще всего считать палочками (и в детском саду нас учат именно такому счету) — в качестве которых могут выступать и пластмассовые стерженьки, и пальцы, и черточки на бумаге. Один — одна палочка, два — две палочки, десять — десять палочек. А сто палочек? Уже посчитать затруднительно, потому придумали сокращение записи: доходим до пяти палочек, ставим галочку, доходим до десяти — ставим крестик:

Узнаете? Конечно, это всем знакомая римская система, сохранившаяся до настоящих времен на циферблатах часов или в нумерации столетий. Она представляет собой пример непозиционной системы счисления — потому что значение определенного символа, обозначающего то или иное число, в ней не зависит от позиции относительно других символов — все значения в записи просто суммируются. То есть записи «XVIII» и «IIIXV» в принципе должны означать одно и то же. На самом деле это не совсем так — в современной традиции принято в целях сокращения записи использовать и позицию: скажем, в записи «IV» факт, что палочка стоит перед галочкой, а не после нее, означает придание ей отрицательного значения, т. е. в данном случае единица не прибавляется, а вычитается из пяти (то же самое относится и к записи девятки «IX»). Если вы человек наблюдательный, то могли заметить, что на часах четверку часто обозначают как «ИИ», а не как «IV» (см. рис. 14.5), что, несомненно, более отвечает духу непозиционной системы. Однако при всех возможных отклонениях главным здесь остается факт, что в основе системы лежит операция суммирования.

Рис. 14.5. Циферблат часов с римскими числами

Большие числа в римской системе записывать трудно, а еще сложнее осуществлять с ними арифметические действия. Поэтому еще в древнем Вавилоне придумали позиционную систему. Позднее в Европе позиционную систему переоткрыл (видимо) Архимед, затем от греков она была воспринята индусами и арабами, а на рубеже I и II тысячелетий опять попала в Европу[19] — с тех пор мы называем цифры арабскими, хотя по справедливости их следовало бы назвать индийскими. Это была уже современная десятичная система в том виде, в котором мы ее используем по сей день, у арабов отличается только написание цифр. С тем фактом, что заимствована она именно у арабов, связано не всеми осознаваемое несоответствие порядка записи цифр в числе с привычным для нас порядком следования текста: арабы, как известно, пишут справа налево. Поэтому значение цифры в зависимости от позиции ее в записи числа возрастает именно справа налево.

* * *

Заметки на полях

Еще один нюанс, дошедший до нас от древнегреческих времен, связан с тем, что греки и римляне не знали нуля. Именно поэтому первым годом нового тысячелетия считается 2001, а не 2000 год — год с двумя нулями относится к предыдущему столетию или тысячелетию. Это происходит потому, что после последнего года до нашей эры («минус первого») идет сразу первый год нашей эры, а не нулевой. На самом деле древние греки были совсем не такими дураками и ноль игнорировали не по скудоумию. Дело в том, что в последовательности объектов, нумерованных от нуля до, например, девяти, содержится не девять предметов, а десять! Чтобы избежать этой путаницы, в быту обычно нумерацию производят, начиная с 1, тогда последний номер будет одновременно означать и количество. В электронике же и в программировании обычно принято нумеровать объекты, начиная с 0, и всегда следует помнить, что номер и количество различаются на единицу (так, байт, о котором далее, может содержать 256 возможных значений, но номер последнего значения равен 255). На всякий случай всегда следует уточнять, откуда ведется нумерация, иначе можно попасть в неприятную ситуацию (скажем, элементы строки в языке Pascal нумеруются с единицы, а в языке С — с нуля).

* * *

Позиционные системы, в отличие от непозиционных, основаны не на простом сложении входящих в них цифр, а на сложении их с учетом присвоенного им «веса» в зависимости от положения цифр в записи. Так, запись «3» и в римской системе, и в арабской означает одно и то же, а вот запись «33» в римской системе означала бы шесть, а в арабской — совсем другое число, тридцать три.

Для строгого определения позиционной системы сначала выбирается некоторое число р, которое носит название основания системы счисления. Тогда любое число в такой системе может быть представлено следующим образом:

а_n·рⁿ + a_n-1·p^n-1 +… + a₁·p¹ + a₀·p⁰. (4)

В самой записи числа степени основания подразумеваются, а не пишутся (и для записи основания даже нет специального значка), поэтому запись будет представлять собой просто последовательность а_n … а₀ (еще раз обратим внимание на то, что запись производится справа налево по старшинству, — обычная математическая запись выглядела бы наоборот). Отдельные позиции в записи числа называются разрядами. Например, в десятичной системе (т. е. в системе с основанием 10) полное представление четырехразрядного числа 1024 таково:

1·10³ + 0·10² + 2·10¹ + 4·10⁰

Ну а как можно представить число в системе счисления с другим основанием? Для любой системы с основанием р нужно ровно р различных цифр — т. е. значков для изображения чисел. Для десятичной системы их десять — это и есть известные всем символы от 0 до 9. Заметим, что выбор начертания этих значков совершенно произволен — так, у арабов и по сей день 1 обозначается, как и у нас, вертикальной палочкой, а вот цифра 2 — знаком

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

Двоичная и шестнадцатеричная системы

В двоичной системе необходимо всего два различных знака для цифр: 0 и 1. Это и вызвало столь большое ее распространение в электронике: смоделировать два состояния электронной схемы и затем их безошибочно различить неизмеримо проще, чем три, четыре и более, не говоря уж о десяти. В середине прошлого столетия советский инженер Николай Петрович Брусенцов построил вычислительную машину, которая работала в троичной системе, и потом всю свою долгую жизнь доказывал ее неоспоримые преимущества. Но несмотря на это, его изобретение так и осталось единственным примером такого рода — слишком сложна реализация электронных элементов, работающих в троичной логике.

Еще важнее, что двоичная система прекрасно согласуется как с представленными ранее логическими переменными, так и с тем фактом, что величина, могущая принимать два и только два состояния и получившая названия бит, есть естественная единица количества информации. Это было установлено в 1948 году одновременно Клодом Шенноном и Норбертом Винером, отцом кибернетики, — меньше, чем один бит, информации не бывает. Разряды двоичных чисел (т. е. чисел, представленных в двоичной системе) также стали называть битами. Слово bit — по-английски означает «кусочек, частица чего-либо». Как термин для обозначения количества информации, слово «бит», говорят, возникло от сокращения Binary digiT — «двоичная цифра».

Представление двоичных цифр с помощью уровней напряжения, как это делается в электронных устройствах, если точно такая же модель числа, как раскладывание на земле палочек и проведение черточек на бумаге. В последних случаях мы оперируем с числами вручную, по правилам арифметики, а в электронных схемах это происходит в автоматическом режиме, без участия человека — вот и вся разница! Это понятие о «модели числа» — очень важный момент, который следует хорошо осмыслить, если вы действительно хотите вникнуть в суть работы цифровых электронных схем.

Итак, запись числа в двоичной системе требует всего двух цифр, начертание которых заимствовано из десятичной системы и выглядит, как 0 и 1. Число, например, 1101 тогда будет выглядеть так:

1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 13

Чтобы отличить запись числа в различных системах, часто внизу пишут основание системы:

1101₂ = 13₁₀.

Если система не указана, то имеется в виду обычно десятичная, но не всегда — часто, когда из контекста понятно, что идет речь об электронных устройствах, не указывают не только основание два, но и под словом «разрядность» имеют в виду количество именно двоичных, а не десятичных разрядов (таков, скажем, смысл термина «24-разрядный цвет»).

Шестнадцатеричная система имеет, как ясно из ее названия, основание шестнадцать. Для того чтобы получить шестнадцать различных знаков, изобретать ничего нового не стали, а просто использовали те же цифры от 0 до 9 для первых десяти и заглавные латинские буквы от А до F для одиннадцатого-шестнадцатого знаков (часто вместо заглавных букв употребляют и строчные, с теми же значениями). Таким образом, известное нам число 13₁₀ выразится в шестнадцатеричной системе, как просто D₁₆. Соответствие шестнадцатеричных знаков десятичным числам следует выучить наизусть: А — 10, В — 11, С — 12, D — 13, Е — 14, F — 15. Значения больших чисел вычисляются по обычной формуле, например:

A2FC₁₆ = 10·16³ + 2·16² + 15·16¹ + 12·16⁰ = 40960 + 512 + 240 + 12 = 41724₁₀.

Перевод из одной системы счисления в другую

Как следует из изложенного, перевод в десятичную систему любых форматов не представляет сложности и при надлежащей тренировке может осуществляться даже в уме. Для того чтобы быстро переводить в десятичную систему двоичные и шестнадцатеричные числа, следует выучить наизусть таблицу степеней двойки до 16 (табл. 14.3) и представления некоторых чисел в двоичной и шестнадцатеричной формах (табл. 14.4).

Буква h добавляется к шестнадцатеричному представлению числа, чтобы отличить его от десятичного, не используя индекса 16 (в разных языках программирования есть и другие способы, см. далее). На первое время достаточно запомнить только маленькие числа, а для образования двоичных и шестнадцатеричных чисел понять принцип, остальное выучится позже само.

Из табл. 14.4 видно, что из двоичной в шестнадцатеричную системы и обратно переводить совсем просто. Двоичное число достаточно разбить на тетрады (т. е. группы из 4-х цифр) и перевести каждую в отдельности. Например, число 59₁₀, т. е. 0011 1011₂, будет равно 3Bh. Еще проще обратный перевод — каждое шестнадцатеричное число заменяется группой из 4-х двоичных цифр. Соответственно, число A2FC₁₆ выразится так: 1010 0010 1111 1100₂. Заметьте, что пробелы между тетрадами в двоичных числах введены просто для удобства восприятия, подобно пробелам между тройками разрядов (классами) в записи больших десятичных чисел, и никакой иной нагрузки не несут. При записи двоичных чисел в тексте программ, как ассемблерных, так и программ на языках высокого уровня, естественно, эти пробелы ставить запрещается. Обычно при этом для удобства ведущие нули нередко не опускаются (хотя в табл. 14.4 они и опущены) — число 15 чаще всего записывается в виде 0Fh. Почему так удобнее, вы поймете далее.

* * *

Заметки на полях

Почему в табл. 14.4 приведены именно эти числа? Числа, на единицу меньшие степени двойки, имеют в электронике и в программировании большое значение. Если вы посмотрите в таблицу внимательно, то увидите, что наибольшее число с количеством разрядов, равным степени двойки, содержит единицы во всех разрядах, т. е. как раз и равно этой степени минус единица. При этом количество всех чисел с таким количеством разрядов равно степени двойки. Другими словами, память, содержащая ровно 256 (2⁸) ячеек, будет иметь номер (адрес) последней ячейки, равный 255, или FFh. Наибольшее число, до которого может досчитать 8-разрядный двоичный счетчик, также равно FFh, поскольку если подать на него еще один импульс (257-й по счету), он обнулится, ибо 9-го разряда, где могла бы записаться старшая единица, у него не существует. Потому с такими числами приходится иметь дело очень часто, даже чаще, чем с собственно степенями двойки.

* * *

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

Для начала запомним, что разряды двоичного числа нумеруются с нуля — т. е., к примеру, разряд номер 3 окажется четвертым справа. Теперь пусть мы имеем, например, десятичное число 59. Подбираем наибольшую степень двойки из табл. 14.3, не превышающую этого числа: 32, что есть 5-я степень. Ставим 1 в 5-м разряде: 100000. Вычитаем подобранную степень из исходного числа (59–32 = 27) и подбираем для остатка также степень, его не превышающую: 16 (2⁴). Ставим единицу в 4-м разряде: 110000. Повторяем процедуру вычитания-подбора: 27–16 = 11, степень равна 8 (2³), ставим единицу в 3-м разряде: 111000. Еще раз: 11 — 8 = 3, степень равна 2 (2¹), так что 2-й разряд оказался пропущен, ставим в нем ноль, а единицу во 1-м разряде: 111010. Последнее вычитание дает 1, которую и ставим в младший (нулевой) разряд, окончательно получив 59₁₀ = 111011₂.

Байты

Слово «байт» (byte) представляет собой сокращение от BinarY digiT Eight — «восемь двоичных цифр». Другими словами, байт — это просто восьмиразрядное двоичное число. Соответственно, он имеет ровно два шестнадцатеричных разряда, или две двоичных тетрады. Такой байт был введен фирмой IBM в конце 50-х годов прошлого века, до этого (а в СССР — и после этого, вплоть до 1969 года) применялись байты с другим количеством разрядов: 5, 6 и 7.

Почему именно 8 разрядов? Да просто потому, что так удобно — число кратно степени двойки, т. е. легко масштабируется. Скажем, шестнадцатиразрядное число — просто два байта, записанные подряд, подобно тетрадам в самом байте. В то же время число в 8 разрядов — относительно невелико и одновременно достаточно емко: имеет 256 значений, которых с лихвой хватает, к примеру, для представления всех печатных знаков европейских алфавитов. Поэтому в настоящее время байт — общепринятая единица измерения информации, т. к. основную единицу — бит — на практике применять неудобно из-за ее мелковатости, числа получаются слишком большими. Применяют и меньшие единицы: кроме бита, это полубайт, или тетрада — одно шестнадцатеричное число.

Для современной электронной техники характерны большие, чем байт, числа — двухбайтовые (65 536 значений), четырехбайтовые (32 двоичных разряда или 4 294 967 296 значений) и даже восьмибайтовые числа. Все они часто называются словами: «word». Так, в памяти современных персональных компьютеров минимальная ячейка памяти содержит 32 бита (или 4 байта), хотя измеряют объем памяти все равно в традиционных байтах.

* * *

О ЕДИНИЦАХ ИНФОРМАЦИИ

В однобуквенных сокращениях принято обозначать байт большой буквой (Б), чтобы отличить его от бита (б), но в критичных случаях во избежание разночтений следует писать полностью: «Мбайт», «Мбит». Тем более что отечественный ГОСТ 8.417-2002 предусматривает однобуквенное сокращение для байта (Б), но не предусматривает его для бита. С приставками также имеется некоторая путаница. В 1999 году Международная электротехническая комиссия (МЭК) с большим опозданием попыталась устранить неоднозначность в обозначениях кратности, введя специальные двоичные приставки киби (вместо «кило»), меби (вместо «мега») и гиби (вместо «гига»), означающие умножение на 1024 вместо 1000. Однако «килобайты» и «мегабайты» к тому времени настолько прижились, что эти не очень удачно звучащие обозначения так и не стали общепринятыми. Приставку «кило» в единицах информации, согласно тому же отечественному стандарту, следует писать с большой буквы (Кбайт), чтобы подчеркнуть, что речь идет об умножении на 1024, а не на 1000. Однако для приставок «мега» и «гига» (а также всех остальных) такого удобного приема уже нет, поэтому это правило на практике соблюдают редко (в этой книге я его также не придерживаюсь). На практике еще можно встретить обозначение единиц информации из одной буквы (например, «256 К памяти»), но пользоваться таким способом не следует, т. к. часто приходится гадать — идет ли тут речь о килобитах или килобайтах.

* * *

Впрочем, есть одна область, где традиционно употребляются именно биты (а также мегабиты и гигабиты), а не байты — это характеристики последовательных цифровых линий передач. К примеру, всем знакомая характеристика модемов в 56 К означает именно 56 кбит в секунду, а так называемые широкополосные линии связи имеют скорости передачи порядка мегабит в секунду. Это связано с тем, что передача именно восьмиразрядными пакетами битов там применяется редко — скажем, стандарт RS232, который мы будем еще рассматривать в этой книге, предусматривает восемь значащих разрядов (т. е. один байт), но помимо этого передаются, как минимум, еще два бита: столовый и стартовый, итого 10. В компьютерных сетях пакеты и вовсе могут иметь переменную длину, поэтому байтами в сетях информацию считают только, когда речь идет об отправленной или принятой информации, но не о той, которая реально передается, — последняя может включать в себя достаточно много всяких служебных битов и целых байтов.

Кстати, часто употребляющийся термин «боды» не равносилен битам в секунду, как это часто ошибочно считают, бездумно записывая фразы вроде «скорость модема 56 бод». Бод — это количество посылок в секунду, где одна посылка может нести несколько битов. Так, базовая для телефонных модемов скорость передачи составляет 2400 бод, но при этом она может быть равна 4800 или 9600 бит/с, в зависимости от того, сколько бит содержится в посылке. Кроме того, скорость, выраженная в бодах, всегда представляет собой полную скорость канала, включающую все служебные поля и отдельные дополнительные биты (вроде бита четности), и потому количество реально передаваемой информации представляет плохо. По этим причинам единицей «бод» в повседневной практике лучше не пользоваться.

Запись чисел в различных форматах

Шестнадцатеричный формат записи часто еще обозначают как HEX (hexadecimal), двоичный — как BIN (binary), а десятичный — как DEC (decimal). Кроме этого, в ходу еще так называемый двоично-десятичный формат — BCD (binary-coded decimal), о котором далее. Дело в том, что с помощью матричных шрифтов на компьютерах с текстовыми дисплеями воспроизводить индексы было невозможно, и вместо того, чтобы обозначать основания системы цифрой справа внизу, их стали обозначать буквами: «В» (или «Ь») — означает двоичную систему, «Н» (или «h») — шестнадцатеричную, отсутствие буквы означает десятичную систему:

13 = 00001101b = 0Dh.

Такая запись принята в языке ассемблера для процессоров Intel и стала общепринятой. Популярность языка С внесла в это дело некоторый разнобой: там десятичная система не обозначается никак, двоичная — буквой «Ь», а вот шестнадцатеричная — буквой «х», причем запись во всех случаях предваряется нулем (чтобы не путать запись числа с идентификаторами переменных, которые всегда начинаются с буквы):

13 = 0b00001101 = 0xD.

Такая запись также принята в ассемблере для микроконтроллеров AVR, который мы будем изучать далее. Запись ODh ассемблер AVR не «понимает», зато «понимает» представление НЕХ-формата, принятое в языке Pascal: $0D. Обратите внимание, что запись в НЕХ-формате обычно ведется в двухразрядном виде — даже если число имеет всего один значащий разряд, как в нашем случае, то в старшем пишется 0. То же самое относится и к двоичной записи, которая дополняется нулями до восьми разрядов. Таким образом подчеркивается, что речь идет о восьмиразрядных устройствах. А вот для десятичного представления ведущих нулей следует остерегаться — чтобы еще больше запутать пользователя, разработчики AVR-ассемблера приняли для представления редко употребляемых восьмеричных чисел запись просто с ведущим нулем, без букв: например, 77 означает просто десятичное 77, а вот 077 будет означать 7·8 + 7 = 63₁₀.

Несколько слов о двоично-десятичном формате BCD. Электронные устройства «заточены» под использование двоичных и родственных им систем счисления, потому что основой являются два состояния, т. е. двоичная цифра. Так что, соединив несколько устройств вместе с целью оперирования с многоразрядными числами, мы всегда будем получать именно двоичное число, и оперировать с ним оказывается значительно проще. Но для понимания человеком десятичный формат необходим — в десятичном виде числа приходится представлять всегда, когда речь идет о выводе, например, на цифровой дисплей. Для этой цели приходится преобразовывать двоичные/шестнадцатеричные числа в десятичные и хранить их в таких же байтовых регистрах или ячейках памяти.

Это можно делать двумя путями: в виде упакованного и неупакованного BCD. Неупакованный формат попросту означает, что мы тратим на каждую десятичную цифру не тетраду, как минимально необходимо, а целый байт. Зато при этом не возникает разночтений: 05h = 05₁₀, и никаких проблем. Однако ясно, что это крайне неэкономично — байтов требуется в два раза больше, а старший полубайт при этом все равно всегда ноль. Потому BCD-числа при хранении и передаче по каналам связи всегда упаковывают, занимая и старший разряд второй десятичной цифрой, — скажем, число 59 при этом и запишется, как просто 59h. Однако 59h — это не 59! Ведь мы раньше установили, что записи 59h соответствует 5·16 + 9 = 89, что вообще ни в какие ворота не лезет.

Причина в том, что двоично-десятичная запись числа не совпадает с шестнадцатеричной. Поэтому в общем случае перед проведением операций с упакованными BCD-числами их распаковывают, перемещая старший разряд в отдельный байт и заменяя в обоих байтах старшие полубайты нулями. Иногда для проведения операций с BCD-числами в микропроцессоре или микроконтроллере предусмотрены специальные команды, так что «вручную» заниматься упаковкой-распаковкой не требуется. В качестве примера хранения чисел в упакованном BCD-формате можно привести значения часов, минут и секунд в микросхемах энергонезависимых часов RTC (о них см. главу 22).

Немного двоичной арифметики

Правила двоичной арифметики значительно проще, чем десятичной, и включают две таблицы: сложения и умножения — несколько похожие на те же таблицы для логических переменных:

Как мы видим, правила обычного умножения одноразрядных двоичных величин совпадают с таковыми для логического умножения. Однако правила сложения отличаются, поскольку при сложении двух единиц результат равен 2, и появляется перенос в следующий разряд. Учитывая, что умножение многоразрядных чисел сводится к сложению отдельных произведений, там придется этот перенос учитывать (как это делается на практике, мы увидим в главе 15).

Сложности начинаются, когда мы хотим в двоичной системе представить отрицательные и дробные числа, причем не выходя за рамки двух знаков «ноль» и «единица», ибо в электронной схеме другие знаки представлять нечем.

Отрицательные двоичные числа

Самый простой метод представления отрицательных чисел — отвести один бит (логичнее всего — старший) для хранения знака. По причинам, которые вы поймете далее, значение 1 в этом бите означает знак «минус», а 0 — знак «плюс». Что произойдет с нашим числом при таком представлении?

В области положительных чисел не произойдет ничего, кроме того, что их диапазон сократится вдвое, — например, для числа в байтовом представлении вместо диапазона 0…255 мы получим всего лишь 0…127 (0000 0000–0111 1111). А отрицательные числа будут иметь тот же диапазон, только старший бит у них будет равен 1. Все просто, не правда ли?

Нет, неправда. Такое представление отрицательных чисел совершенно не соответствует обычной числовой оси, на которой влево от нуля идет минус единица, а затем числа по абсолютной величине увеличиваются. Здесь же мы получаем, во-первых, два разных нуля («обычный» 0000 0000 и «отрицательный» 1000 0000), во-вторых, оси отрицательных и положительных чисел никак не стыкуются, и производство арифметических операций превратится в головоломку. Поэтому поступим так: договоримся, что -1 соответствует число 255 (1111 1111), — 2 — число 254 (1111 1110) и т. д. вниз до 128 (1000 0000), которое будет соответствовать -128 (и общий диапазон всех чисел получится от -128 до 127). Очевидно, что если вы при таком представлении хотите получить отрицательное число в обычном виде, то надо из значения числа (например, 240) вычесть максимальное значение диапазона (255) плюс 1 (256). Если отбросить знак, то результат такого вычитания (16 в данном случае) называется еще дополнением до 2 для исходного числа (а само исходное число 240 — дополнением до 2 для 16). Название «дополнение до 2» используется независимо от разрядности числа, потому что верхней границей всегда служит степень двойки (в десятичной системе аналогичная операция называется «дополнение до 10»).

Что произойдет в такой системе, если вычесть, например, 2 из 1? Запишем это действие в двоичной системе обычным столбиком:

В первом разряде результата мы без проблем получаем 1, а уже для второго нам придется занимать 1 из старших, которые сплошь нули, поэтому представим себе, что у нас будто бы есть девятый разряд, равный 1, из которого заем в конечном итоге и происходит:

На самом деле девятиразрядное число 1 0000 0000 есть не что иное, как 256, т. е. то же самое максимальное значение плюс 1, и мы здесь выполнили две операции: прибавили к уменьшаемому эти самые 256, а затем выполнили вычитание, но уже в положительной области для всех участвующих чисел.

А что результат? Он будет равен 255, т. е. тому самому числу, которое, как мы договорились, и представляет — 1. Получается, что вычитание в такой системе происходит автоматически правильно, независимо от знака участвующих чисел. Если хотите, можете потренироваться и проверить, скажем, что будет, если в этой системе вычесть 240 из 100.

Немного смущает только эта самая операция нахождения дополнения до 2, точнее, в данном случае, до 256 — как ее осуществить на практике, если схема всего имеет 8 разрядов? В дальнейшем мы увидим, что иногда ее осуществлять вовсе не надо — некоторые электронные схемы ведут себя так, что при осуществлении вычитания вся процедура осуществляется автоматически. Особенно наглядно это выглядит для двоичных реверсивных счетчиков, которые мы будем рассматривать в главе 16.

В точности так же ведут себя и соответствующие команды в микропроцессорах — и если вы захотите произвести операцию вычитания числа 2 из содержимого восьмибитового регистра, содержащего число 1, то в регистре окажется число 255 (все единицы). А интерпретация результата — как отрицательного числа или как положительного — это уже ваши трудности.

В микропроцессорах есть обычно и команда, которая возвращает дополнение до 2, в большинстве ассемблеров она называется NEG, от слова «негативный», потому что меняет знак, если мы договариваемся считать числа «со знаком». А как ее можно было бы осуществить «вручную», не обращаясь в действительности к 9-му разряду? Вернемся к рассмотренным ранее примерам и выпишем столбиком исходные числа, результаты операции нахождения дополнения до 2 и результат еще одной манипуляции, которая представляет собой вычитание единицы из дополнения до 2, т. е., что то же самое, просто вычитания исходного числа из наивысшего числа диапазона (255):

Если мы сравним двоичные представления в верхней и нижней строках, то увидим, что они могут быть получены друг из друга путем инверсии каждого из битов. Эта операция называется нахождением дополнения до 1 (потому что число, из которого вычитается, содержит все 1 во всех разрядах; для десятичной системы аналогичная операция называется дополнение до 9). Для нахождения дополнения до 1 девятый разряд не требуется, да и схему можно построить так, чтобы никаких вычитаний не производить, а просто переворачивать биты. То есть, для полного сведения вычитания к сложению надо проделать три операции:

1. Найти дополнение до 1 для вычитаемого (инвертировать его биты).

2. Прибавить к результату 1, чтобы найти дополнение до 2.

3. Сложить уменьшаемое и дополнение до 2 для вычитаемого.

Заметим, что все сложности с этими многочисленными дополнениями связаны с наличием нуля в ряду натуральных чисел — если бы его не было, дополнение было бы всего одно, и операция вычитания упростилась. Так может, греки все же были в чем-то правы?

В заключение обратим внимание на еще одно замечательное свойство двоичных чисел, которое часто позволяет значительно облегчить операции умножения и деления, а именно: умножению на 2 соответствует операция сдвига всех разрядов числа на один разряд влево, а операции деления на 2 — вправо. Крайние разряды (старший при умножении и младший при делении) в общем случае при этом должны теряться, но в микропроцессорах есть специальный бит переноса, в который эти «потерянные» разряды помещаются. Противоположные крайние разряды (младший при умножении и старший при делении) в общем случае замещаются нулями, но могут и замещаться значением бита переноса, что позволяет без лишних проблем делить и умножать числа с разрядностью больше одного байта. Как можно догадаться, умножению и делению на более высокие степени двойки будет соответствовать операция сдвига в нужную сторону на иное (равное степени) число разрядов.

Излишне говорить, что операцию сдвига разрядов в электронных схемах производить неизмеримо проще, чем операции деления и умножения. Есть и специальные схемы для этой операции — сдвиговые регистры, которые мы также будем «проходить» (в главе 16).

Дробные числа

Сразу заметим, что в некомпьютерной электронике дробными числами стараются не пользоваться. При необходимости их переводят в целые, умножая на соответствующую степень десяти (а чаще — даже на степень 2, что проще), при этом все остальные участвующие в расчетах величины также масштабируются в нужное число раз. Затем при выводе, к примеру, на цифровой дисплей, запятая просто устанавливается в нужном месте (иногда заранее, и без возможности изменения ее положения). То есть, для цифровой схемы не существует значения температуры, равного 30,81 градуса, а есть число 3081 в BCD-формате. Примерно те же действия мы производили, когда конструировали цифровой термометр в главе 13, — на самом деле он показывает целое число милливольт в нужном масштабе.

И все же — как мы можем при необходимости представить дробные числа, если двоичные разряды ничего о таковых «не знают» и могут воспроизводить только целые числа в соответствии с формулой (4)? Мы не будем рассматривать расширение этой формулы, включающее в себя представление в позиционной системе не только целых, но и всех действительных чисел «с плавающей запятой», т. к. в электронике такой вариант не хождения не имеет. В электронике и компьютерной технике используют другой способ представления действительных чисел — с помощью мантиссы и порядка, в так называемом нормализованном виде. При этом место запятой фиксируется:

0,0125 = 0,125·10^-1,

1254,81 =0,125481·10⁴.

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

Легко заметить, что и саму запятую, и основание степени тут можно опустить, записывая в память лишь мантиссу и порядок — конечно, если всегда помнить, что мы имеем в виду. Например, можно сделать так: отвести в памяти три байта, из которых первые два хранят цифры мантиссы, а третий отведен под порядок. Легко также подсчитать, каков будет диапазон чисел, могущих быть представленными таким образом, — число, которое представляет мантиссу, будет укладываться в диапазон от -32768 до 32767, т. е. иметь от 4 до 5 значащих десятичных цифр. На практике операции с дробными числами можно производить несколько проще, и мы будем их осваивать в главе 20.

Коды, шифры и дешифраторы

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

Код в общем случае — это совокупность правил (т. е. алгоритм) для представления информации в какой-либо форме. Процесс применения к информационному сообщению этих правил называется кодированием, при этом полученная группа знаков или сигналов также называется кодом. Обратная операция — восстановление сообщения по известному коду — носит название декодирования. Например, код Морзе позволяет записать с помощью двух знаков — точки и тире — любую букву или цифру. Закодированное таким образом сообщение можно передавать с высокой надежностью в различных средах, характеризующихся высоким уровнем помех (в виде звуковых сигналов, в том числе по радио, в виде вспышек света разной длительности, перестукиванием через стены и т. п.).

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

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

На рис. 14.6 приведены различные стандартные коды для первых девяти букв латинского алфавита. Следует отметить, что азбука Брайля — система письменности для слепых (где жирная точка соответствует наличию выпуклости, а «худая» — ее отсутствию) — в полной мере является двоичным кодом, мало того, из принципа ее построения было многое заимствовано в современных системах компьютерных кодировок. А вот код Морзе, хотя и состоит из точек и тире, двоичным кодом не является: в нем используется как минимум еще один знак — пауза. Зато код Морзе намного экономичнее обычных двоичных кодов, таких, как ASCII, поскольку имеет переменное число точек-тире для каждого символа, и часто встречающиеся буквы в нем короче, чем редко встречающиеся.

Рис. 14.6. Некоторые коды первых латинских букв

_{Для кодировки ASCII в скобках дано десятичное значение}

Понятие шифра, строго говоря, к электронике не относится. Шифр — это просто код, построенный специальным образом для обеспечения секретности при передаче сообщений, и занимается этим довольно сложная математическая дисциплина — криптография. Тем не менее, в электронике довольно часто употребляют наименование «дешифраторы» — для обозначения элементов, которые предназначены для преобразования одной разновидности кода в другую.

Типичным примером может служить микросхема К561ИД5 (рис. 14.7, а), которая преобразует двоично-десятичное число, подаваемое на входы X, в специальный код для управления семисегментными индикаторами. Сам такой индикатор вместе с таблицей его состояний представлен на рис. 14.8. В этой таблице в колонке под заголовком «BIN» представлены двоичные числа, соответствующие входам X дешифраторов на рис. 14.7.

Рис. 14.7. Разводка выводов дешифраторов К561ИД5 (а) и 514ИД1/514ИД2 (б)

Рис. 14.8. Обозначения сегментов и таблица состояний семисегментного индикатора

Отметим, что К561ИД5 «заточена» под управление ЖК-дисплеями, и потому имеет двухполярное питание и содержит отдельный вход F, на который подаются прямоугольные импульсы частотой несколько десятков герц (иначе, как мы знаем из главы 7, сегмент ЖК-индикатора будет засвечен навсегда). Сигнал на входе Е «защелкивает» выход — если на нем логический ноль (напряжение «земли»), то коды на выходе не будут меняться независимо от состояния входов, в нормальном состоянии там должна быть логическая единица (напряжение питания).

Если нужно управлять светодиодными индикаторами, для которых двухполярное пульсирующее питание не требуется, то выходы отрицательного питания и «земли» объединяют и на вход F подают напряжение «земли» (логического нуля). По выходам a-f при этом приходится ставить дополнительные ключевые транзисторы или эмиттерные повторители для управления сегментами индикаторов, т. к. выходной ток микросхем серии 561 для непосредственного управления светодиодами недостаточен.

Микросхема К561ИД5 основана на так называемой технологии КМОП. А специально предназначенные для управления светодиодными индикаторами дешифраторы 514ИД1 и 514ИД2 (рис. 14.7, б) основаны на технологии ТТЛ и потому ограничены одним напряжением питания (максимум 5,5 В), зато выходы у них намного мощнее (подробнее о технологиях логических микросхем и их электрических характеристиках мы узнаем из главы 15).

Различаются 514ИД1 и 514ИД2 полярностью выхода — у первого наружу выведен эмиттер выходного транзистора, коммутирующий ток через сегмент на «землю», а у второго — на выходе открытый коллектор. Таким образом, 514ИД1 предназначена для управления сегментными индикаторами с общим катодом, который подсоединяется к «земле», а 514ИД2 — индикаторами с общим анодом, который подсоединяется к питанию. Другое отличие — у 514ИД1 имеются встроенные токоограничивающие резисторы номиналом приблизительно 1 кОм, т. е. при падении напряжения на сегменте примерно 1,8–2 В (стандартном для красного светодиода) выходной ток будет составлять около 3 мА.

У 514ИД2 таких резисторов не имеется, и их приходится ставить дополнительно, непосредственно к выходу дешифратора индикатор присоединять нельзя. Зато здесь можно гибко управлять яркостью свечения в зависимости от индивидуальных характеристик индикаторов — зеленые и желтые индикаторы при одинаковом токе имеют большее падение напряжения, чем красные (номинально 2,4 В против 1,8 В), и могут светиться тусклее. При токе через сегмент около 5–6 мА сопротивление токоограничивающего резистора должно быть в пределах 360–510 Ом. Большими по размеру индикаторами, где прямое падение напряжения на сегменте удвоенное, с помощью этих микросхем приходится управлять также через внешние ключи, подключенные к более высокому напряжению.

При подаче напряжения «земли» на вывод «Г» этих микросхем все сегменты оказываются погашенными. Это позволяет осуществлять динамическую индикацию — управление многоразрядными индикаторами, при котором в каждый момент времени светится только один десятичный разряд. В результате удается сэкономить на количестве соединений (одноименные сегменты всех разрядов соединяются параллельно) и отчасти на потреблении схемы. Формально говоря, ток через каждый разряд при таком подключении должен увеличиваться пропорционально числу разрядов, чтобы сохранить ту же яркость — например, при четырех разрядах ток должен быть в четыре раза больше, т. к. каждый разряд горит лишь четвертую часть времени (но не забудьте, что у 514ИД2 есть предельное значение — 22 мА). Однако опыт показывает, что пропорциональное увеличение тока необязательно, визуально яркость сохраняется и при меньших значениях мгновенного тока через сегмент, что и позволяет немного сэкономить на питании. Более подробно мы будем говорить о динамической индикации при изучении микроконтроллеров, с помощью которых организовать ее гораздо проще и удобнее, чем с помощью обычных микросхем.