Алгоритмы на кристалле. Глава 1: Вычислительная модель

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

Пара слов о том, что мы будем изучать.

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


Какая-то плата. Источник фото ukrmarket.net

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

Конечно, чтобы уметь проектировать микросхему и потом быть в состоянии рассуждать о ее работе, нам потребуется какая-то более-менее точная теория. Созданием такой теории мы сейчас и займемся. Если кто-то из читателей переживает, что он не знает или забыл, где у транзистора база, а где эмиттер, я спешу его успокоить – эти знания нам даже не понадобятся. Рассуждения в книге будут относиться к концептуально более простому и высокому уровню: уровню логических блоков.

Базовые концепции.

Формально объектом нашего изучения будут всякого рода логические схемы. Теорию логических схем мы построим на 5 основных понятиях:

1. понятии логического блока (регистра и функциональных блоков вроде “и”, “или” “не”…);
2. порта данных;
3. понятии проводника данных (шины);
4. понятии внутреннего состояния блока или схемы;
5. и понятии дискретного времени.

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

Изложение теории формальных логических схем для большей понятности разбито на два этапа. На первом этапе мы изучим ту ее ограниченную часть, в которой «строительными кирпичиками» логических схем могут выступать только блоки строго ограниченного набора типов. Язык этой теории во многом аналогичен ассемблеру и другим языкам программирования, в которых любые программы строятся из заведомо ограниченного числа команд. Рассмотрев несколько примеров логических схем, построенных на языке ограниченной теории, мы увидим, что подобно ассемблерным программам такой подход страдает проблемой избыточного дублирования. Типичной будет ситуация, когда некоторые участки схемы многократно в ней повторяются. Впоследствии мы преодолеем проблему дублирования, добавив в нашу теорию возможность определять в ней новые составные блоки, что по духу аналогично переходу от ассемблера к процедурным языкам программирования.

Аксиомы для общих понятий.

Время.

Самая обычная идея о дискретных шагах времени, которые мы буден называть тактами.

Время и все вместе с ним меняется скачками. Все интересующие нас свойства формального времени содержатся в следующей аксиоме:

T) Множество моментов времени может быть отождествлено с натуральным рядом {0, 1, 2, 3, … }.

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

Порты.

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

рис 1 Схема логического «следует».

Мы будем делить порты на внешние и внутренние.

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

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

Следующие 7 аксиом задают формальные свойства, которыми должен обладать всякий порт:

P1) Свойство иметь размерность(количество бит) и тип(входной/выходной,
внешний/внутренний — всего 4 возможных комбинации).

P2) Свойство каждому внутреннему порту принадлежать единственному логическому блоку
внутри схемы, а каждому внешнему порту не принадлежать ни одному из них.

P3) Свойство, обязывающие каждый входной порт быть присоединенным в точности к одной шине, а каждый выходной порт – не более чем к одной шине.

P4) Свойство, обязующее порт принимать какое-то определенное значение на каждом такте. Значениями порта размерности n должны быть двоичные слова длины n.

P5) В любой из тактов значение всякого входного порта равно значению в присоединенной
к нему шине.

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

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

Нам потребуется именовать порты. Внешним портам мы будем давать отдельные «собственные» имена. Что касается внутренних портов, то наш способ их называния будет похож на способ обращения к полю конкретного объекта какого-нибудь класса, принятый в объектно-ориентированных языках программирования. Каждый блок внутри схемы будет относится к какому-то определенному типу (скажем “OR”) и вместе с тем иметь «собственное» имя (скажем ). Чтобы назвать конкретный порт, мы будем указывать собственное имя блока, а затем через точку то универсальное имя, которое этот порт имеет во всех блоках данного типа (например, ).

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

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

Внутренние состояние блока и схемы.

Читатель, знакомый с понятием конечного автомата, в аксиоме P7) легко угадает требование всякому логическому блоку представлять из себя конечный автомат. Если же понятие конечного автомата для вас ново, не переживайте: идея внутреннего состояния логического блока станет для вас тривиальной, как только мы дойдем до описания работы элементарных блоков.

Описание формальных свойств внутреннего состояния содержаться в следующих двух аксиомах:

S1) Множество внутренних состояний S всякого логического блока включает в себя только конечное число элементов.

S2) Внутреннее состояние, в котором окажется логический блок в следующий момент времени, однозначно определяется типом блока, тем, в каком состоянии этот блок находится в данный момент, и тем, какие в данный момент значения принимают его входные порты.

Шины.

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

Несмотря на то, что шина – не обязательное и даже слегка загромождающее теорию понятие, мы это понятие все-таки в нее добавим. Причин для этого две:

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

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

Определение абстрактной шины мы подчиним 5-ти аксиомам:

B1) Каждая шина обладает определенной размерностью (числом бит), размерность шины и
размерность любого порта, с которым соединена эта шина, должны быть одинаковыми.

B2) Среди портов, с которыми соединена шина должен найтись в точности один выходной порт.

B3) Среди портов, с которыми соединена шина должен найтись по крайней мере один входной порт.

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

B5) В любой из тактов значение в шине равно значению того единственного выходного порта, с которым эта шина соединена.

Концы шин, сообщения и сигналы.

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

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

Пример: на рисунке 1 запечатлено, как сообщение “1” распространяется от порта … к портам … и ….

Определение элементарных блоков.

Элементарные логические блоки – последний тип примитивных “кирпичиков”, из которых будут строится логические схемы, а в последствие и более сложные логические блоки. В рамках нашей теории элементарные блоки не имеют «внутренней структуры», однако имеют строго задекларированное поведение. Все принадлежащие элементарным блокам порты, как входные, так и выходные, являются внутренними.

Все многообразие типов элементарных блоков удобно разделить на 5 групп:

1. Блоки константных функций: «0» и «1».
2. Блоки логических функций: «AND», «OR», «NOT» «+».
3. Прямой и обратный однобитный двухходовый мультиплексоры.
4. Блоки прямого отображения:
   
   • блок прямой и обратной конкатенации,
   • блок фиксированной перестановки (в том числе блок инверсии).
5. Однобитные регистры: базовый регистр, регистры сочетающие функции запрета записи и/или сброса.

Теперь по порядку о каждом группе.

Блоки-константы.

E1) Блоки «0» и «1» реализуют одноименные константные функции. Блоки этих типов не имеют портов входа и каждый имеет по одному однобитному порту выхода. Со сменой тактов значения их портов выхода остаются всегда неизменными: односимвольным словом “0” для блока «0» и односимвольным словом “1” для блока «1».

Блоки элементарных логических функций.

E2) Блоки типов «AND» и «OR» (рис 2) реализуют одноименные логические функции. Экземпляры этих типов имеют каждый по два однобитных порта входа, именуемые как и , и по одному однобитному порту выхода .

Если интерпретировать однобитное слово “0”, как логическую «ложь», а однобитное слово “1” – как логическую «истина», то правило задающее значение выходных портов можно записать так:

Для блоков, принадлежащих типу «AND»: (для всякого ) .

Для блоков, принадлежащих типу «OR»: (для всякого ): .

Аналогично блоки, принадлежащие типу «NOT» имеют только один порт входа arg и один порт выхода r. Значения порта выхода устанавливаются правилом .

Блоки типа «+» реализуют сложение двух однобитных чисел, поступивших на их входные порты arg1 и arg2. Значение однобитного выходного порта r устанавливается равным младшему биту этой суммы, а старший бит “передается” в выходной порт c:

;
;


рис 2 Блоки «и», «или», «не», и «+»

Мультиплексоры.

E3) Двухходовые мультиплексоры выполняют важную роль: с их помощью можно управлять направлением, в котором далее будет распространяться сообщение или сигнал.

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

Если , то
;
иначе
;

Обратный однобитный двухходовый мультиплексор действует в некотором смысле наоборот (рис 3b). Подавая подходящий управляющий сигнал на вход , вы тем самым можете выбрать, у какого из двух его выходных портов или значение на текущем такте станет копией сигнала, пришедшего на вход , а у какого это значение окажется словом “0”. Точное правило для обратного мультиплексора выглядит так:

Если , то
и
;
иначе
и
.

(рис 3а и 3b прямого и обратного мультиплексоров)

Блоки прямого отображения.

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

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

E4) Блок прямой конкатенации (рис 4a). Этот тип блоков является параметрическим, параметрами для него служат количество и разрядности входных портов . Блок прямой конкатенации объединяет шин размерностей в одну шину размерности , сохраняя общий порядок нумерации битов. Это означает, что если – значение -битного пота , — значение -битного пота , … — значение -битного пота , то значением -битного порта будет слов , являющееся конкатенацией слов (например, если , то ). Более формально блок прямой конкатенации с параметрами можно описать так:

;
*
*
*
;
;
*
*
*
;
*
*
*
;

рис 4 Блоки прямой и обратной конкатенации

E5) Действия блоков обратной конкатенации прямо противоположно действиям блоков прямой конкатенации (рис 4b). Этот тип блоков тоже параметрический. Блок обратной конкатенации разделяет шину размерности на шин размерностей соответственно, сохраняя при этом общий порядок битов. Формальное определение его поведения таково:

;
*
*
*
;
;
*
*
*
;
*
*
*
;

E6) Пусть – какое-то натуральное число, – произвольная перестановка n-элементного множества. Каждой такой перестановке мы сопоставим блок с одним -битным портом входа и одни -битным портом выхода. Действия блока будут заключается в том, чтобы подействовать перестановкой p на номера разрядов входного сигнала:

;
;
*
*
*
;

E7) В частности, если – это инверсия n-элементного множества ( ), то блок мы будем обозначать как INV() и именовать блоком инверсии.

Класс функциональных блоков.

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

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

Регистры.

Значение выходного порта регистра зависит от значений на его входах не на прямую, а опосредованно, через значение его внутреннего состояния s. Значения состояния однобитного регистра являются двоичные слова “0” или “1”. Значение выходного порта регистра на текущем такте всегда совпадает со значением его внутреннего состояния. В свою очередь значения, которые принимают порты входа регистра на текущем такте, полностью определяют то, каким окажется состояние этого регистра в следующий такт времени. На практике при включении устройства, то есть в нулевой такт времени, внутреннее состояние регистра самопроизвольно может стать равным “0” или “1”. В нашей теории мы будем считать, что установка состояний регистров в нулевой момент происходит случайно.

E8) Простой однобитный регистр имеет один однобитный порт входа и один однобитный порт выхода . Значение внутреннего состояния простого регистра в следующий такт времени всегда является копией того значения, которое его порта входа принял на текущем такте. Более формально описание поведения простого регистра выглядит так:

;
;
;

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

;

если , то
,
иначе
;

;

E10) Однобитный регистр со сбросом имеет два однобитных входных порта и и единственный однобитный порт выхода . Работает также, как и простой регистр с тем лишь отличием, что его состояние на следующем такте обязательно становится равным “0”, если на текущем значение порта есть “1”:

;

если , то
,
иначе`
;

;


рис 5 Почти все типы регистров

E11) Однобитный регистр со сбросом и опциональной записью сочетает в себе продвинутые возможности регистров двух предыдущих типов. Такой регистр включает в себя три однобитных порта входа , и и один однобитный порт выхода . Сброс превалирует над разрешением записи: если на порт reset подана “1”, то состояние на следующем такте будет иметь значение “0” в любом случае.

Формальное описание поведения регистров со сбросом и опциональной записью таково:

;

если , то
,
иначе
{
если , то
,
иначе
;
};
;

Свойства элементарных схем.

Определение.

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

C*) Всякий логический блок должен принадлежать одному из типов, описанных в E1) – E11).

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

Чтение элементарных схем.

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

Метод прямого потока данных.

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

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

Значения портов выхода блоков-констант «0» и «1», если последние присутствуют в схеме, известны всегда (аксиома E1). Значения внешних выходных портов мы знаем по условию (аксиома P6). Также по условию на момент нулевого такта нам известны внутренние состояния всех регистров схемы, поэтому благодаря аксиомам E8-E11 мы без труда можем найти значения, которые на нулевом такте примут их выходные порты.

Определение процедуры:

Внешние выходные порты схемы, выходные порты блоков-констант и выходные порты регистров объявим нулевым фронтом распространения сигнала .

С помощью индукции определим -тый фронт распространения сигнала .

1. Пусть все фронты уже построены, а значения всем входящим в их состав портам уже приписаны.
2. В качестве базы для построения возьмем пустое множество.
3. Каждой шине, имеющей своим началом выходной порт из фронта , припишем то же самое значение, что было ранее приписано этому порту (необходимость соответствовать аксиоме B5).
4. Каждому входному порту , если тот единственный выходной порт, с которым он соединен общей шиной, принадлежит фронту , припишем значение этого выходного порта и включим в состав фронта фронта (необходимость соответствовать аксиомам B5 и P5)
5. Выделим в схеме каждый логический блок, у которого один или большее число его входных портов принадлежит фронту , а все остальные входные порты этого блока входят в состав любого из уже построенных фронтов . Из индуктивного предположения и предыдущего пункта следует, что всем входным портам каждого выделенного блока значения уже приписаны.
   
   рис 6, поясняющий это сложное предложение.
   
6. Если выделенный блок имеет тип функционального (не является регистром), то по значениям, приписанным его входным портам, вычислим значения всех его выходных портов (необходимость соответствовать аксиоме P7), после чего их тоже добавим к фронту .
7. На этом -тый фронт распространения сигнала считается построенным.

Конец процедуры.

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

*) Поскольку множества конструируются непересекающимися (индукция из пунктов 4, 5 и 6), то за всю процедуру их построения каждому порту и каждой шине схемы значения будут приписаны не более одного раза.

**) Если вдруг очередной фронт по завершению своего строительства оказался пуст (в нем не содержится ни одного порта схемы), то и все последующие фронты также будут пусты (непосредственно следует из пунктов 4, 5 и 6). Таким образом на практике построение фронтов стоит продолжать только до тех пор, пока очередной из них не окажется пустым.

Распространение метода на всю временную шкалу.

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

Такое предположение в том числе означает, что всем портам и шинам схемы в процессе построения фронтов были приписаны некоторые значения. Индукцией по номеру фронта несложно показать (сделайте это), что исходя их начальных условий эти значения были единственными не вступающими в противоречия с аксиомами P5-P7, B4-B5, E1-E11. Поскольку условиями исходной задачи предполагалось, что рассматриваемая схема, взятая с некоторыми значениями на ее портах и шинах в каждый такт, — вместе удовлетворяют всей аксиоматике, то из предыдущего замечания следует, что на нулевом такте метод прямого распространения данных действительно позволил эти значения установить (как единственные, которые могли бы удовлетворить аксиомам теории). Отыщем значения портов и шин схемы на всех последующих тактах.

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

Последнее замечание показывает, что если метод прямого распространения данных достиг успеха на нулевом такте, то создается ситуация, когда его можно вновь применить, но уже на такте под номером “1”. Действительно: состояния, в которых будут находится регистры на первом такте, мы только что вычислили, а значения внешних портов выхода в каждый такт времени известны нам по условию.

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

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

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

Примеры.

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

Представленная на рисунке 1 схема, реализует логическую функцию «следует»: на каждом такте значение ее внешнего входного пота (a->b)(k) равно истинностному значению выражения a(k) -> b(k).

На рисунке 7 представлен простой «пульсар». Значение его внешнего порта puls(k) при k=0 (на нулевом такте) случайно. Каждый следующий такт оно меняется на противоположное, чередуя между собой «нули» и «единицы». В качестве упражнения постарайтесь придумать, как построить пульсар, у которого последовательность значений порта puls обязательно начиналась бы с «единицы».


рис 7: схема простого «пульсара»

Поведение схемы, изображенной на рисунке 8, в некотором смысле повторят поведение прямого двухходового мультиплексора. Если на k-том такте значение glob_com равно “0”, то в этот такт значение внешнего входного порта glob_out копирует значение внешнего выходного порта glob_in1, в противном случает на этом такте значение порта glob_out установится равным значению внешнего выходного порта glob_in2. На досуге подумайте, поведение каких элементарных блоков можно проэмулировать с помощью схем, содержащих исключительно отличные от них элементарные блоки.


рис 8: Схема «составного» мультиплексора

Логические противоречия и вычислительная полнота.

Вычислительная неполнота метода прямого распространения данных.

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

Должно ли вычисление все новых фронтов распространения сигнала обязательно завершиться тем, что их объединение (как множеств) вместе с очередным фронтом охватит собою в схеме все ее порты?

Вообще говоря, нет!


рис 9. Схема из циклически соединенных блока прямой и обратной конкатенации

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

Тем не менее существуют такие значения портов и шин для схемы рисунка 9, при которых она вместе с ними удовлетворяют всем аксиомам нашей теории. Все такие значения получаются по следующему рецепту: достаточно для каждого такта как угодно выбрать однобитное значение x1, общее для шины b1 и соединенных с ней портов, затем как угодно выбрать однобитное значение x2, общее для шины b2 и соединенных с ней портов, а в качестве значения x3, общего для шины b3 и соединенных с ней портов, взять конкатенацию x1*x2 (докажите).

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

На рисунке 10 изображена схема, значение портов и шин в которой однозначно определены – все они должны быть равны “1”. Тем не менее, несмотря на однозначность, установить значения порта OR.arg2 методом прямого распространения данных тут не выйдет (проверьте).


рис 10 Схема безо всяких двусмысленностей.

Логические противоречия в значениях элементов схемы.

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

Аксиомы конструкционной группы определяют конструкцию логической схемы, то есть то, что представляют из себя ее элементы и как они должны быть друг с другом соединены. Сюда относятся аксиомы P1-P3, B1-B3 и аксиома C*.

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

Возникает естественный вопрос:

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

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

Этот длинный вопрос имеет очень короткий ответ: “Нет”. Почти хрестоматийной иллюстраций этому служит «зацикленный на себя» блок “NOT” – по сути, парадокс лжеца в «железе».


рис 11. Парадокс лжеца

Каким бы мы не попробовали объявить значение порта not.r: “нулем”, или “единицей”, – передав это значение на порт not.arg и пересчитав значение для not.r заново, в обоих случаях мы придем к противоречию.

Довольно показательно, что схема “пульсара” на рисунке 7 отличается от только что рассмотренной противоречивой схемы наличием единственного регистра на пути зацикливания сигнала от “NOT” к “NOT”. Грубо говоря, наличие регистра вынуждает значение на выходе “NOT” «влиять» не на самое себя в том же такте, а на свое значение тактом позже. Как мы видим, такое «отложенное» круговое влияние уже не создает противоречий.

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

Функциональное влияние портов друг на друга.

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

Непосредственное функциональное влияние.

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

1. является портом входа, а — портом выхода одного и того же функционального элементарного блока;
2. является каким-либо портом выхода, – каким-либо портом входа и оба они соединены общей шиной.

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

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

Подсознательно нам хотелось бы думать, что если порт функционального влияет на порт , то при некоторых условиях значение, принимаемое портом на такте , должно как-то влиять на множество тех значений, которые в этот такт способен принять порт . Однако, как показывает схема на рисунке 12, подобное предположение верно не всегда: формально определенное функциональное влияние еще не означает влияния фактического. Внешний выходной порт glob_in функционально влияет на внешний входной порт glob_out, однако никакого фактического влияния значения порта glob_in на значения порта glob_out оказать не могут.


рисунок 12

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

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

!) при заданных на каждом такте значениях внутренних выходных портов схемы и известных на момент нулевого такта состояниях ее регистров, метод прямого распространения данных позволяет на каждом такте приписать значения абсолютно всем шинам, портам, а так же найти состояния в которых окажутся ее регистры в следующий такт времени;

!!) схема вместе с приписанными ее портам и шинам значениями удовлетворяет всем аксиомам поведенческой группы.

Доказательство !).

Согласно лемме 1 метод прямого распространения данных будет успешен на всей последовательности тактов тогда и только тогда, когда он оказывается успешен на нулевом такте. Отсюда следует, что нам достаточно доказать утверждение !) леммы 2 только для нулевого такта.

Будем действовать от противного. Предположим, что метод прямого распространения данных не достигает успеха: ни для какого объединение фронтов не включает в себя всех портов схемы. Пусть также – наибольший по индексу непустой фронт (если таковые у схемы вообще имеются).

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

Снова предположим обратное. Пусть каждый выходной порт принадлежит некоторому фронту .

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

Получается, что не только выходные, но и все входные порты принадлежат объединению фронтов .

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

Остается построит внутри схемы какой-нибудь цикл функционального влияния.

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

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

Действуя подобно тому, как описано выше, мы сможем построить сколь угодно длинную последовательность портов в которой:

a) каждый порт с нечетным индексом будет являться входным портом некоторого функционального блока, а стоящий перед ним в последовательности порт с четным индексом – выходным портом того же блока.

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

Поскольку количество портов, в том числе и выходных, в любой схеме предполагается конечным, то при наращивании последовательности среди портов с четным индексом обязательно возникнут дубликаты. Пусть i<j – два таких числа, что порт – есть то же самый порт, что и . В таком случае конечная последовательность портов , где
,
,
*
*
*

– будет ни чем иным, как обнаруженным нами циклом функционального влияния.

Полученное только что противоречие полностью доказывает !)

Доказательство !!) :

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

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

A*) Никакая логическая схема не должна содержать циклов функционального влияния.

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