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

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

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


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

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

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

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

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


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

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


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

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

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


Время.


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

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

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

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

Порты.


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть $Pname$ — имя конкретного порта, значение этого порта на временном шаге $k$ мы будем обозначать как $Pname(k)$, в свою очередь $i$-тый бит того же значения — как $Pname[i](k)$, или просто $Pname[i]$, если из контекста понятно, о каком именно шаге идет речь.

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


Читатель, знакомый с понятием конечного автомата, в аксиоме 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) реализуют одноименные логические функции. Экземпляры этих типов имеют каждый по два однобитных порта входа, именуемые как $arg1$ и $arg2$, и по одному однобитному порту выхода $r$.

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

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

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

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

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

$r(k) = arg1(k) + arg2(k)\ (mod 2)$;
$c(k) = arg1(k) \ \ AND \ \ arg2(k)$;

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

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


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

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

Если $comm(k) = , то
$out(k) = in1(k)$;
иначе
$out(k) = in2(k)$;

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

Если $comm(k) = , то
$out1(k) = in(k)$ и
$out2(k) = ;
иначе
$out1(k) = и
$out2(k) = in(k)$.
gwdiyducam7dv9cnzwptr2fy6qk.jpeg
(рис 3а и 3b прямого и обратного мультиплексоров)

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


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

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

E4) Блок прямой конкатенации (рис 4a). Этот тип блоков является параметрическим, параметрами для него служат количество и разрядности входных портов $in1, in2, … in\_q$. Блок прямой конкатенации $*(n_1,n_2,…,n_q)$ объединяет $q$ шин размерностей $n_1,n_2,…,n_q$ в одну шину размерности $n_1+n_2+⋯+n_q$, сохраняя общий порядок нумерации битов. Это означает, что если $u_1$ — значение $n_1$-битного пота $in1$, $u_2$ — значение $n_2$-битного пота $in2$, … $u_q$ — значение $n_q$-битного пота $in\_q$, то значением $(n_1+n_2+⋯+n_q)$ -битного порта $out$ будет слов $w$, являющееся конкатенацией слов $u_1,u_2,…u_q$ (например, если $q=2, n_1=3, n_2=4, u=, то $w=”0010011”$). Более формально блок прямой конкатенации с параметрами $(n_1,n_2,…,n_q)$ можно описать так:

$out[0](k) = in1[0](k)$;
*
*
*
$out[n_1 - 1](k) = in1[n_1 - 1](k)$;
$out[n_1+0](k) = in2[0](k)$;
*
*
*
$out[n_1+n_2-1](k) = in2[n_1-1](k)$;
*
*
*
$out[n_1+n_2+⋯+n_q-1](k) = inq[n_q-1](k)$;
ehsub1_nxrauqqrdwaoza9zcsjm.jpeg
рис 4 Блоки прямой и обратной конкатенации

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

$out1[0](k) = in[0](k)$;
*
*
*
$out1[n_1 - 1](k) = in[n_1 - 1](k)$;
$out2[0](k) = in[n_1+0](k)$;
*
*
*
$out2[n_2-1](k) = in[n_1+n_2-1](k)$;
*
*
*
$outq[n_q-1](k) = in[n_1+n_2+⋯+n_q-1](k)$;

E6) Пусть $n$ — какое-то натуральное число, $p: \{0,1,…,n-1\} ->\{0,1, …, n-1\}$» /> — произвольная перестановка n-элементного множества. Каждой такой перестановке мы сопоставим блок <img src= с одним $n$-битным портом входа и одни $n$-битным портом выхода. Действия блока $π(p)$ будут заключается в том, чтобы подействовать перестановкой p на номера разрядов входного сигнала:

$out[p(0)](k) = in[0](k)$;
$out[p(1)](k) = in[1](k)$;
*
*
*
$out[p(n-1)](k) = in[n-1](k)$;

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

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


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

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

Регистры.


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

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

$s(0) = random$;
$s(k+1) = in(k)$;
$out(k)=s(k)$;

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

$s(0) = random$;

если $enable(k)=1$, то
$s(k+1) = in(k)$,
иначе
$s(k+1) = s(k)$;

$out(k)=s(k)$;

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

$s(0) = random$;

если $reset(k)=”1”$, то
$s(k+1) = ,
иначе`
$s(k+1) = in(k)$;

$out(k)=s(k)$;

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

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

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

$s(0) = random$;

если $reset(k)=”1”$, то
$s(k+1) = ,
иначе
{
если $enable(k)=”1”$, то
$s(k+1) = in(k)$,
иначе
$s(k+1) = s(k)$;
};
$out(k) = s(k)$;

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


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


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

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

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

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


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

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


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

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

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

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

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

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

  1. Пусть все фронты $F_0,… F_{(n-1)}$ уже построены, а значения всем входящим в их состав портам уже приписаны.
  2. В качестве базы для построения $F_n$ возьмем пустое множество.
  3. Каждой шине, имеющей своим началом выходной порт из фронта $F_{(n-1)}$, припишем то же самое значение, что было ранее приписано этому порту (необходимость соответствовать аксиоме B5).
  4. Выделим в схеме каждый логический блок, у которого по крайней мере один его входной порт соединен шиной с выходным портом, находящимся в составе фронта $F_{(n-1)}$, а все остальные входные порты этого блока соединены шинами с какими-либо выходными портами, находящимися в составе любого из уже построенных фронтов $F_0, … , F_{(n-1)}$.
    kyf_osqdr-xyphssdt6twlhcnic.jpeg
    рис 6, поясняющий это сложное предложение.
  5. Каждому входному порту каждого выделенного блока припишем значение, равное значению того единственного выходного порта, с которым этот входной порт соединен общей шиной (необходимость соответствовать аксиомам B5 и P5). Поскольку согласно пункту 4) упомянутый выходной порт принадлежит одному из фронтов $F_0, … , F_{(n-1)}$, то по индуктивному предположению (пункт 1)) его значение нам уже известно.
  6. Все входные порты выделенных блоков добавим к множеству $F_n$.
  7. Если выделенный блок имеет тип функционального (не является регистром), то по значениям, приписанным его входным портам, вычислим значения всех его выходных портов (необходимость соответствовать аксиоме P7), после чего их тоже добавим к фронту $F_n$.
  8. Если какой-либо внешний входной порт соединен общей шиной с выходным портом, находящимся в составе фронта $F_{(n-1)}$, то припишем первому из них значение последнего (необходимость соответствовать аксиомам B5 и P5), а затем добавим первый к фронту $F_n$.
  9. На этом <p class=© Habrahabr.ru