Физика двоичной логики

3bd955b4d9f3549ce8edfec123021094.png


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

О системах счисления


Система счисления — это метод записи чисел. В повседневной жизни мы используем арабскую систему счисления, а именно десятичную позиционную. По мнению историков, арабские цифры появились в Индии ориентировочно до 5 века нашей эры. В Европу они пришли в начале второго тысячелетия из арабских стран, собственно, поэтому и принято называть привычные нам цифры арабскими. В России арабская система счисления появилась в 14–15 веке, а к 18 веку и вовсе вытеснила отечественную разработку под названием цифирь

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

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

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

Цифровая абстракция


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

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

Логические выражения

Алгебра логики — это раздел математики над логическими выражениями. Под логическими выражениями подразумеваются суждения, высказывания, предложения и т.п., истинность которых можно определить однозначно — правда или ложь. Разумеется, не любое высказывание является логическим. Например, выражение «в декабре 31 день» является логическим, потому что однозначно истинно, а выражение «новая матрица — сомнительное кинопроизведение» не является логическим, поскольку отражает субъективную позицию и содержит неопределенную характеристику «сомнительное», хотя спорить с данным тезисом довольно сложно, если и вообще возможно. Вопросительные высказывания также не являются логическими выражениями, так как судить об их истинности не имеет смысла. Также стоит отметить, что зачастую сложно определить, является ли выражение логическим. Так, выражение «площадь России составляет 17 130 000 квадратных километров» в определенной ситуации можно считать логическим, а в другой нет. Определить точную площадь невозможно, поэтому данное высказывание будет считаться логическим в том случае, если эта оценка будет приемлемой на практике.

Логические связки

Разобравшись непосредственно с логическими выражениями, определим операции над ними. Под операциями над логическими выражениями принято подразумевать логические связки. Типичными примерами логических связок являются «и», «или», «если …, то» и т.п., позволяющие составлять из логических выражений новые. Например, «Столица России — Москва и столица США — Вашингтон». Это высказывание является истинным, поскольку его составные также являются истинными. Подробнее логические связки и правила их работы мы разберем далее.

Математический язык


В рамках данной части будут введены основные логические операции и их обозначения, аксиомы алгебры логики и её законы.

Логические операции


Символами A и B обозначены условные логические высказывания. На логические операции распространяется определенный порядок выполнения:

  1. Инверсия;
  2. Конъюнкция и штрих Шеффера;
  3. Дизъюнкция и стрелка Пирса;
  4. Импликация и сложение по модулю 2;
  5. Эквивалентность;


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

Аксиомы

c4193be6727fca7b815c996ee2f85e12.png

Свойства и законы

3cc640271b03a53e8e1edba329925337.png


Булевы функции


Булева функция — это брат-близнец функций из алгебры. Только вместо чисел в качестве переменных в ней логические высказывания. 

Предположим, у нас есть такая простецкая функция:

»Если A истинно, то B тоже истинно», где А и В — это некие логические высказывания.

На математическом языке эта функция имеет такой вид:

3005b5039074a279b6d0ca0225ac3888.png


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

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


На булевы функции распространяются законы и правила алгебры логики. Применим их для упрощения булевой функции f (A, B, C):

ff3c1a716d25c6120f4bf7d29f1d4669.jpg


С таким видом этой функции работать проще. В том числе проще и составить таблицу истинности:

Базис


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

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

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


Логические схемы необходимы для реализации функций алгебры логики в цифровом устройстве. Для составления логических схем используются логические вентили (элементарные логические схемы), реализующие логические операции. Упомянутые базисы позволяют сократить перечень логических вентилей, хотя и стремление к полной минимизации этого перечня путем использования наименьших базисов не совсем практично. Мы рассмотрим логические вентили упомянутого базиса {И, ИЛИ, НЕ} 

Логические вентиль И


a02b3f33b7088531e8835f4a78f9c033.png


У логического вентиля И два входа (А, В) и один выход (Z). Вентиль можно описать логической функцией Z=F (A, B)=A & B и таблицей истинности:

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


90ed5e7384b3d3d738cf72846e66b1f3.png


У логического вентиля ИЛИ, как и у вентиля И, два входа и один выход. Его описывает функция Z=F (A, B)=A v B и таблица истинности:

Логический вентиль НЕ


f0ec1a55b7431556c9013f98bca2f963.jpg


Логический вентиль НЕ имеет только один вход и один выход. На выход поступает инвертированное значение А. Функция вентиля НЕ: Q=F (A)=¬A

7bdb04726a9f9b537aec3368efddd4c5.png


Обозначения по ГОСТ и другим стандартам

Сумматор


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

Разберемся с чем мы будем оперировать: две двоичных цифры. При сложении чисел нам, так или иначе, придется работать с переносом. Например, при сложении двух единиц в двоичной системе счисления мы получим 10:

a1168fd5ee267bfb39abbbddf6997cbd.png


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

c3ae46181fe085a28d658992cdbedc28.png


Запомним эту функцию.

Добавим в наш сумматор перенос: как с предыдущего разряда (еще один вход), как и для следующего (ещё один выход).

Таблица истинности для сумматора с переносом:


Теперь необходимо составить две булевы функции: для переноса и новую для разряда.

Чисто математически перенос для разряда — это ещё одно слагаемое в сумме. У нас уже есть функция для суммы, воспользуемся ей:

adebb5059a9638eb494491072fd946bd.png


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

Перенос равен единице в том случае, если из трех входных величин как минимум две равны единицы. Исходя из этого, можно составить вот такую функцию:

e70ce8ba9f1d8d2cad335b653c882207.jpg


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

1f7a0bafdc1a812aea50e7341f529974.png


Обозначение будет использовано в следующих схемах. Теперь составим схему для функции переноса:

00d16301d03c7b9d5096ded217ca1f97.png


Имея две логические схемы мы можем составить из них одноразрядный двоичный сумматор:

566ae3c8e49e3ed101826aebee51f5d9.png


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

8c064d59264e41eb5b2b3d7bf19d2283.png


Физика логического уровня


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

Физические принципы


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

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

df0a6da544fe2f1eaa714ebd784a07ce.png


Логический вентиль AND в Z1, реализованный с помощью металлических пластин. Более подробное описание устройства Z1 тут.

Конечно же, такие механизмы часто заедали и искажали результат, делая Z1 почти бесполезной на практике. В Z2-Z4 Цузе заменил пластины на электромагнитные реле и даже просил у правительства Третьего Рейха денег на полностью электронные компоненты, но ему отказали.

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

8ff491f041005aab2c2a0451a3f0bbd5.jpg


Радиолампа (двойной триод)

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

f9e76ad6cfe989ed12ddcb31416daa10.png


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

Хоть устройства на лампах работают быстрее механических и электромеханических, радиолампа остается крайне ненадежным прибором. Колба может потерять герметичность, спираль нагрева со временем перегорает, а сама лампа потребляет много энергии и имеет внушительные габариты. Если учитывать что первые ЭВМ состояли из тысяч ламп, обслуживание лампового монстра превращалось в головную боль для инженеров. 

В 1947 Уильям Шокли, Джон Бардин и Уолтер Браттейн создали усилитель нового типа, состоявший из германиевой пластины и полоски золотой фольги. Спустя несколько лет им присудили Нобелевскую премию по физике. Этим изобретением был транзистор — устройство, полностью изменившее индустрию вычислительной техники.

590e009f42f78cae9fad36c2a89457fe.jpg


Копия первого в мире работающего транзистора.

Транзистор


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

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

Сегодня, после нескольких десятилетий развития полупроводниковых технологий, инженеры способны «упаковать» около одного миллиарда МОП-транзисторов на квадратном сантиметре кристалла кремния (с себестоимостью транзистора менее десяти микроцентов). 

Полупроводники


Выше мы говорили о «полупроводниковых технологиях». Что такое полупроводник? Некоторые могут подумать, что полупроводники проводят электрический ток в два раза хуже обычных проводников (таких, как медь, золото или серебро). Это не так! МОП-транзисторы изготавливаются из кремния, элемента 14-й группы (4-й по устаревшей классификации, далее будем придерживаться именно ей). Благодаря 4 электронам, атом кремния может образовывать связи с 4 соседними атомами, формируя кристаллическую решетку. Кремний — так себе проводник (точнее плохой, так как все электроны заняты в ковалентных связях), однако при добавлении в него небольшого количества другого вещества (легировании) его проводимость может улучшиться. Если добавить атом 5 группы (примесь n-типа), то в нем останется один свободный электрон, который легко «гуляет» внутри кристаллической решетки. А если добавить элемент 3 атомной группы (примесь p-типа), то в атоме примеси будет отсутствовать один электрон (дырка). Дырка может перемещаться в кристаллической решетки подобно электрону, причем она будет вести себя как положительно заряженная частица. Отсюда и название «полупроводник» — с помощью концентрации примесей можно управлять проводимостью кремния.

1c6b3c50131181bdb5b915eed8a61d26.png


Кристаллическая решетка атомов кремния. В качестве примеси n-типа (центр) использован мышьяк (атом, потерявший электрон, становится положительным ионом), в качестве примеси p-типа (справа) использован бор (при перемещении дырки атом бора получает дополнительный электрон и становится отрицательным ионом).

n-МОП и p-МОП транзисторы


Полевой МОП-транзистор можно представить в виде «сэндвича» из нескольких слоев. Верхний слой называется затвором. Он наложен на слой изолятора — диоксида кремния (SiO2, иногда его называют просто оксидом). Этот слой в свою очередь располагается над кремниевой пластиной, называемой подложкой. Сегодня в качестве металла затвора используется поликристаллический кремний, поскольку он не плавится в ходе высокотемпературной обработки кристалла. Слои металл-оксид-полупроводника образуют конденсатор, в котором тонкий слой оксида (диэлектрик) изолирует металлическую пластину от полупроводниковой. 

Существуют два вида полевых МОП-транзисторов: n-МОП и p-МОП. В транзисторах n-типа, называемых n-МОП, области, где расположены полупроводниковые примеси n-типа — в свою очередь называемые истоком и стоком — находятся рядом с затвором, причем вся эта структура размещается на подложке p-типа. В транзисторах же p-МОП и исток, и сток — это области p-типа, размещенные на подложке n-типа.

906ba5e7832ba4a980a7c5787b095235.png


Полевой МОП-транзистор ведет себя как переключатель, управляемый приложенным к нему напряжением. В таком транзисторе напряжение перехода создает электрическое поле, включающее или отключающее линию связи между источником и стоком.

ae3e02f2b3cae0c5cc0ec855956f6b6d.png


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

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

Логические вентили на КМОП-транзисторах


Для подробного описания построения всевозможных логических вентилей здесь просто не хватит места. Поэтому в качестве примера возьмем простейшие логические элементы и рассмотрим их реализацию на КМОП-транзисторах. Вентиль НЕ:

2ad864140dbc35d90c3574a597d2722f.png


n-МОП-транзистор N1 включен между землей GND и выходным контактом Y. В свою очередь, p-МОП транзистор P1 включен между напряжением питания VDD и выходным контактом Y. Напряжение на входном контакте А управляет переходами обоих транзисторов.

Если напряжение на А соответствует логическому нулю, то транзистор N1 выключен, а транзистор P1 включен. При этом, напряжение на контакте Y равно напряжению питания, а не земли, что соответствует логической единице. В этом случае говорят, что Y «подтянут» к единице. Включенный транзистор P1 хорошо передает логическую единицу (равную напряжению питания), то есть напряжение на контакте Y очень близко к VDD. Если же напряжение на контакте А равно логической единице, то транзистор N1 включен, а транзистор P1 выключен, и напряжение на контакте Y равно напряжению земли, что соответствует логическому нулю. В этом случае говорят, что Y «подтянут» к нулю. Включенный транзистор N1 хорошо передает логический ноль, то есть напряжение на контакте Y очень близко к GND. Получается, что если A=1, то Y=0, а если A=0, то Y=1. Это соответствует таблице истинности для логического вентиля НЕ.

Схемы вентилей И-НЕ и ИЛИ-НЕ с двумя входами:

3e335589dcede2c3ba5cf315a7298a8f.png


Вентиль И-НЕ

n-МОП-транзисторы N1 и N2 соединены последовательно. Причем, чтобы замкнуть выходной контакт на землю GND — то есть понизить логический уровень, оба этих транзистора должны быть включены. В то время как p-МОП-транзисторы P1 и P2 соединены

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

fe997b83be46e714a46e61ec9bfa3f26.png

Вентиль ИЛИ-НЕ

В этом случае все ровно наоборот. n-МОП транзисторы соединены параллельно, а p-МОП последовательно.

Заключение


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

Computer Systems: A Programmer’s Perspective

The Elements of Computing Systems (Nand2Tetris)

Digital Design and Computer Architecture

stf9uiznc_h9q5qyjl2fw7sx0m0.png

© Habrahabr.ru