01.06.2022 20:47
Sergey_Kovalenko 30 3100 Источник


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

Предыдущие черновики:
… Примерное оглавление.
… Вычислительная модель.
… Быстродействие логических схем.

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


Простой способ представить себе работу элементарной логической схемы


Логическая схема и ее компоненты


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


(Схема "=" )
Логическая схема способны производить вычисления, при этом они оперирует двоичными словами: “данными”. Выходные порты (заполненные полукруги) нужны, чтобы отправлять данные, входные порты (белые полукруги) — чтобы их принимать, шины — чтобы передавать данные от выходных портов к входным. Функциональные логические блоки нужны, чтобы данные неким образом преобразовывать, а блоки-регистры — чтобы их временно запоминать.

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

Такт, как эпоха


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

Процесс вычислений в схеме без регистров


По определению значение, которые функциональный блок на данном такте выставит на том или ином своем порту выхода, полностью определяется именем порта выхода, типом блока и значениями, которые на этом такте примут его входные порты. Например, функциональные блоки элементарного типа “+” реализуют сложение двух однобитных чисел: порту "$c$" блок этого типа выставит значение “1” тогда и только тогда, когда оба его входных порта "$arg1$" и "$arg2$" на этом тате приняли значения “1”, а значение порта “$r$” окажется равным “1” лишь в том случае, когда среди значений "$arg1$" и "$arg2$" единица в точности одна. У блоков-констант нет портов входа, на каждом такте своим портам выхода они выставляют одно и тоже значение: блок “ноль” выставляет “0”, блок “единица” выставляет “1”. Спецификация функциональных блоков всех элементарных типов описана в аксиомах E1-E7 статьи “Вычислительная модель”.


(рисунок однобитного +)

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


(Cхема равенства с аппендиксом из константы в продолжение одного такта. Начало).

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


(Продолжение: рассылка конвертов 1 этап).

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


(Продолжение: рассылка конвертов 2 этап).

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


(Рассылка конвертов. Конец: все порты получили значения).

Особенности поведения регистров


Элементарные регистры способны хранить в себе однобитные слова — значения регистра. Значения регистров меняются только при смене тактов. Слово, которое появится на единственном выходном порте "$out$" регистра в текущий такт, является копией значения, которое имеет регистр в этот такт времени. То, какое значение будет хранить регистр в следующем такте, полностью определяется настоящим значением регистра и значениями его входных портов, принятыим ими на текущем такте. Все регистры имеют входной порт "$in$", некоторые типы — входные поры "$reset$" и "$enable$" в любых сочетаниях. В зависимости от наличия тех или иных портов и значений, принятых этими портами на текущем такте, значение регистра в следующий такт времени либо сохраняется прежним, либо копирует значение, принятое на текущем такте портом "$in$", либо обнуляется.

Для регистра с одним единственным входным портом "$in$" значение, которое этот регистр будет иметь в следующий такт времени в точности равно значению, которое принял порт "$in$" на текущем такте. Если регистр имеет порт "$reset$" и значение, принятое этим портом на текущем такте есть “1”, то на следующем такте значение регистра станет “0” вне зависимости от других условий.

Чтобы значение регистра можно было сохранять несколько тактов подряд, в некоторые типы регистров добавлен порт "$enable$": без учета влияния порта reset, если на текущем такте порт "$enable$" принял “0”, то значение регистра на следующий такт останется прежним, если “1”, то оно с копирует значение, принятое на этом такте портом "$in$".

Значение любого элементарного регистра в нулевой такт случайно.


(рисунок, поясняющий работу регистров)

Спецификация всех регистров, принятых в этой книге за элементарные, описаны в аксиомах E8-E11 статьи “Вычислительная модель”.

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


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



(рисунок, поясняющий работу пульсара в продолжение одного такта)

Замечание по поводу именования портов


Все внешние порты схемы наделяются собственными именами и никакой путаницы в их назывании не будет. В то же время мы неоднократно будем встречать схемы, в которых присутствуют сразу несколько блоков одного и того типа и у каждого из этих блоков есть порт с одним и тем же именем “$A \_port$”. Пусть "$X \_block$" и "$Y \_block$" – собственные имена блоков, обладающих портом с именем “$A \_port$”. Чтобы точно указать о каком именно порте идет речь к имени порта справа через точку будем приписывать собственное имя логического блока, к которому он принадлежит: "$X \_block.A \_port$" – "$A \_port$" блока "$X \_block$", "$Y \_block.A \_port$" – "$A \_port$" блока "$Y \_block$".

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

Схема каскадного компаратора


Определение старшинства между двоичными словами


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

Пусть даны два m-битных слова: $x = x_0, …, x_m-1$ и $y = y_0, …, y_m-1$.
Какое-то число начальных членов этих слов могут быть одинаковыми, то есть: $x_1 = y_1, …, x_i = y_i$. Если эти слова совпадают не во всех позициях и $k$ – наименьшая из позиций, где они отличны, то меньшим считается то слово, у которого на $k$-той позиции стоит «0». Например из двух 7 битных слов «0101000» и «0100111» в лексикографическом порядке второе меньше первого.

В следующем пераграфе мы докажем, что если каждое из слов $x$ и $y$ интерпретировать как запись натурального числа в двоичной системе исчисления: то есть $n(x) = x_0 * 2^{m-1} + …+ x_{m-1} *2^0$, $n(y) = y_0 * 2^{m-1} + …+ y_{m-1} *2^0$, то слово $x$ тогда и только тогда меньше слова $y$ в лексикографическом порядке, кода натурально число $n(x)$, выраженное словом x, меньше натурального числа $n(y)$, выраженного словом $y$ (это утверждение кажется очевидным, но все-таки попробуйте доказать его точно).

Абстрактное описание алгоритма сравнения


Само определение лексикографического порядка содержит в себе алгоритм его вычисления. Действительно, все что мы должны делать — это синхронно перебирать последовательности символов обоих слов до тех пор, пока не обнаружим позицию $k$, на которой символы $x_k$ и $y_k$ различны. То слово, у которого в позиции $k$ стоит 0 и будет меньшим.

В пошаговом виде, описанный алгоритм выглядит так:

  1. Ввести два булевых слова-состояния: первое — “просмотрев символы слов до позиции 0 включительно, установлено, что $x<y$” или коротко — $(x<y)_0$, и второе: “просмотрев символы слов до позиции 0 включительно, установлено, что $y<x$”, коротко — $(y<x)_0$. Обоим словам-состояниям присвоить значение “ложь”, перейти к 2)
  2. Проверить одинаковы ли символы $x_0$ и $y_0$. Если они различны и $x_0 =$ “0”- присвоить значение истина состоянию $(x<y)_0$, если они различны и $y_0 =$ “0” — присвоить значение истина состоянию $(y<x)_0$. Перейти к циклическому повторению 3)-5)
  3. Если рассматриваемая позиция $i$ в словах $x$ и $y$ — последняя, перейти к 7). Иначе в обоих словах перейти к позиции $i+1$, а в алгоритме к шагу 4)
  4. Ввести слова-состояния: слово $(x<y)_{i+1}$ — “просмотрев слова вплоть до позиции $i+1$, установлено, что $x<y$”, и слово $(y<x)_{i+1}$ — “просмотрев слова вплоть до позиции $i+1$, установлено, что $y<x$”. Обоим только что введенным словам-состояниям присвоить значения «ложь». Если хотя бы одно из слов-состояний предыдущей позиции $(x<y)_i$ или $(y<x)_i$ имеет значение «истина» (уже установлено какое из слов меньше), никаких действий над символами $x_{i+1}$ и $y_{i+1}$ не требуется. Просто копируем $(x<y)_i$ в $(x<y)_{i+1}$, $(y<x)_i$ в $(y<x)_{i+1}$. Снова переходим к 3). Иначе переходим к 5).
  5. Если мы здесь, значит анализ $i$ ранее просмотренных позиций слов $x$ и $y$ не смог дать ответ, какое из слов меньше. Сравним текущие позиции $x_{i+1}$ и $y_{i+1}$. Если они различны и $x_{i+1} =$ “0”- присвоить значение истина слову-состоянию $(x<y)_{i+1}$, если они различны и $y_{i+1} = $“0” — присвоить значение истина состоянию $(y<x)_{i+1}$. Вернуться к циклическому повторению шага 3).
  6. Конец алгоритма. Мы просмотрели все m позиций. Логика алгоритма такова, что только одно из слов-состояний: $(x<y)_{m-1}$, или $(y<x)_{m-1}$, может в итоге иметь значение “истина”, тем самым отвечая на вопрос, какое из слов меньше. Если оба этих слова-состояния остались ложными, то слова $x$ и $y$ в точности совпадают.

Интерфейс схемы компаратора


Прежде чем строить схему какого-либо алгоритма, нужно определиться, в каком виде мы собираемся подавать исходные данные, а в каком виде — снимать результат. Компаратор, который мы построим ниже будет способен сравнивать два m-битных слова за один такт. Передаваться эти слова будут в качестве значений внешних выходных $m$-битных портов "$x$" и "$y$". Результат сравнения будет выводится как значения внешних входных 1-битных портов "$(x<y)?$" и "$(y<x)?$", при этом значение “1” будет интерпретироваться как истина, а значение “0” — как ложь. Если оба порта "$(x<y)?$" и "$(y<x)?$" на этом кате имеют значение ложь, значит поступившие на порты $x$ и $y$ в начале этого такта слова идентичны.
image

(интерфейс компаратора)

С интерфейсом схемы мы определились, пора теперь разобраться со знаком вопроса.

Операционная ячейка схемы компаратора


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

В своей логической конструкции описанный выше алгоритм сравнения сводится к следующему:

Находясь над позицией $i$ и наблюдая пару символов $(x_i, y_i)$, мы получаем результат обработки всех предыдущих пар $(x_0, y_0), …, (x_{i-1}, y_{i-1})$ закодированное в значениях однобитных слов-состояний $(x<y)_{i-1}$ и $(y<x)_{i-1}$.

Если одно из этих состояний уже имеет значение “истина”, или же $x_i = y_i$, то все, что надо сделать — это передать без изменений значения обоих этих слов обработчику символов следующей позиции, но уже под видом $(x<y)_i$ и $(“y<x”)_i$.

Если же оба слова $(x<y)_{i-1}$ и $(y<x)_{i-1}$ имеют значение “ложь”, то значения слов-состояний $(x<y)_i$ и $(y<x)_i$ определяется тем, каковы символы $x_i$, или $y_i$. Если эти символы одинаковы, то обеим словам $(x<y)_i$ и $(y<x)_i$ следует приписать ложь. Если же символы различны, то одному из них нужно приписать “истина”, а другому — ложь.

Давайте теперь подробно разберем схемы ячейек-обработчиков.

На рисунке … изображен обработчик пары первых символов слов $x$ и $y$.


(Головная ячейка компаратора)

Плеяда блоков "$dif \_and_1$" (тип "$and$"), "$dif \_not$" (тип "$not$"), "$dif \_or$" (тип "$or$") и "$dif\_and_r$" (обведена сиреневым пунктирным прямоугольником) имеет назначение выяснить, различны ли $x_0$ и $y_0$. Только в том случае, если первые символы слов $x$ и $y$ различны выходной порт "$r$" блока "$dif \_and_r$" посылает в голубую шину значение “1”. Действительно, если значение выходного порта блока "$dif\_and_r$" равно единице, значит и оба его входных порта также на текущем такте приняли значение единица. Порт "$dif \_and_r.arg1$" примет значение “единица”, только если оба символа $x_0$ и $y_0$ одновременно не являются единицей. Далее, порт «dif\_and_r.arg2» будет единицей в точности тогда, когда хотя бы один из символов $x_0$ или $y_0$ является единицей. Вместе два последних предложения доказывают, что "$dif \_and_r.r$" на текущем такте будет иметь значение “1”, только если первые символы поданных в этот такт слов $x$ и $y$ различны.

После того как порт "$dif \_and_r.r$" выдал свое значение, вступают в игру прямые мультиплексоры "$mux_1$" и "$mux_2$". Если первые символы сравниваемых слов одинаковы, то на порты "$comm$" обоих мультиплексоров поступит “0”, соответственно они оба на свой выход скопируют значения своих портов "$arg1$", то есть “0”. Если же символы $x_0$ и $y_0$ различны, значением выходов мультиплексоров станут копии значений их вторых портов входа "$arg2$". В этом случае значением слова $(x<y)_0$ станет копия $y_0$, а значением слова $(y<x)_0$ – копия $x_0$.

Не трудно проверить, что такой способ придавать значения словам $(x<y)_0$ и $(y<x)_0$, когда $x_0$ и $y_0$ не одинаковы, действительно правильно устанавливает какое из слов: $x$ или $y$ меньше в лексикографическом сравнении. Если $x_0 = $«1», то $y_0 = $«0» и слово $(x<y)_0$ копирует $y_0$, то есть получает, как и должно, значение “ложь”, а $(y<x)_0$ копирует $x_0$, то есть получает, как и должно, значение “истина”. Если же $x_0 = $«0», то тогда $y_0 = $«1», соответственно $(x<y)_0$ получает значение “истина”, а $(y<x)_0$ — значение “ложь".

И так, мы доказали, что приведенная схема обработчика двух самых первых символов слов $x$ и $y$ правильно вычисляет слова-состояния $(x<y)_0$ и $(y<x)_0$. Рассмотри теперь обработчик, применимый для всех последующих позиций.


(Регулярная ячейка компаратора)

По сравнению с предыдущим рисунком здесь добавилась плеяда блоков в кирпичном прямоугольнике и блок типа “$and$” "$con \_and$". Одновременно с этим исчез блок-константа и немного поменялись маршруты потоков данных. Самым главным же изменением, которое повлекло все остальные, стало добавление шин, по которым поступают слова-состояния $(x<y)_{i-1}$ и $(y<x)_{i-1}$ от обработчика позиции $i-1$.

При обработке всех позиций, кроме первой, для того, чтобы значения слов $(x<y)_i$ и $(y<x)_i$ не стали простыми копиями $(x<y)_{i-1}$ и $(y<x)_{i-1}$, должны выполняться сразу два условия:

  1. оба слова $(x<y)_{i-1}$ и $(y<x)_{i-1}$ должны иметь значение “ложь”;
  2. значения $x_i$, и $y_i$ должны быть разными.

Второе условие, как и на предыдущем рисунке выполняет плеяда блоков с префиксом "$dif \_$" — она заключена в сиреневый пунктирный прямоугольник. Первое условие проверятся плеядой блоков с префиксом "$s \_$": блоком типа “$or$” "$s \_or$" и блоком типа “$not$” "$s \_not$". Значение выхода блока "$s \_not$" тогда и только тогда равно “1”, когда значение выхода блока "$s \_or$" равно “0”. Последнее будет наблюдаться в том и только в том случае, кода оба слова $(x<y)_{i-1}$ и $(y<x)_{i-1}$ имеют значение “0”.

Блок "$con \_and$" посылает на мультиплексоры “1” только в том случае, если выполнены оба условия. Сценарий, при котором на порты "$com$" мультиплексоров подана “1” ничем не отличается от аналогичного сценария для обработчика головной части: если символы $x_i$ и $y_i$ различны, то значения $(x<y)_i$ и $(y<x)_i$ будут содержать в себе ответ, какое из слов: $x$ или $y$ в лексикографическом порядке меньше другого. Если же на порты "$com$" поданы “0”-ли, то значением выходного порта каждого мультиплексора будет копия значения его входного порта "$arg1$" а слова $(x<y)_i$ и $(y<x)_i$, как и требует алгоритм, будут копиями слов $(x<y)_{i-1}$ и $(y<x)_{i-1}$.

Схема целиком


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

image

(компактное представление головного обработчика)

image

(компактное представление регулярного обработчика)

Остается соединить ячейки между собой и правильно подать на них позиции слов x и y (рис ...). Для разделения 3-битных слов x и y на последовательность их 1-битных символов в схеме используется два блока обратной конкатенации типа "$*^{-1}(1,1,1)$": "${*^{-1}}_x$" и "${*^{-1}}_y$". Мелкие детали схему можно рассмотреть с увеличением, если щелкнуть по ней мышкой.


(схема целиком)

Двоичное представление натуральных чисел


Позиционное исчисление с основанием 2


Всякому двоичному слову $x = x_0, … x_m$ (каждое $x_i$ есть либо 0, либо 1) можно поставить в соответствие натуральное число $n(x)$ по правилу $n(x) = x_0 * 2^m + … + x_m * 2^0$. Сумму членов правой части последнего равенства мы будем называть двоично-степенным разложением числа $n(x)$, а двоичное слово $x$ — двоичным представлением числа $n(x)$, или по-другому — его записью в позиционной системе исчисления с основанием 2. Например, двоичному слову «100» соответствует число $1*2^2 + 0*2^1 + 0*2^0 = 4$. В то же время число “сто” представимо как $64 + 32 + 4 = 2^6 + 2^5 + 2^2$, поэтому оно, например, соответствует двоичному слову «01100100», порождающему двоично-степенное разложение: «сто»$ = 0*2^7 + 1*2^6 + 1*2^5 + 0*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 0*2^0$.

В этой книге при построении логических схем в основном будет использоваться именно двоичная система исчисления, поэтому часто мы не будем различать само число $n(x)$ и его двоичную запись $x$. Двоичные записи натуральных чисел мы будем называть двоичными (натуральными) числами.

Пусть $n$ — какое-либо натуральное число, а $x_0 * 2^m + x_1 * 2^{m-1} + … + x_m * 2^0 = n$ — какое-либо двоично-степенное разложение $n$ (каждый коэффициент $x_i$ есть либо 1, либо 0). Коэффициент $x_{m-i}$ при i-той степени двойки в этом разложении мы будем обозначать как $p_i = p_i(x)$ — и называть $i$-тым (двоичным)разрядом числа $n$ в его двоичной записи $x$. Согласно последнему определению:
$x_0 = p_m $,
$* $
$x_i = p_{m - i} $
$* $
$x_m = p_0$.

Чуть позже мы покажем, что значение $i$-того разряда числа $n$ одинаково во всех двоичных записях $n$, куда этот разряд входит, и поэтому вместо $p_i(x)$, мы сможем позволить себе писать $p_i(n)$. Например, двоичным представлением числа “один” будут записи “1”, “01”, “001” “0001” — у них у всех значение нулевого разряда есть 1, у тех же записей, в которых есть разряд номер один — его значения одинаково и равно 0, и так дале.

По поводу двоичного представления чисел естественно возникают два вопроса:

  1. Всякое ли натуральное число можно представить в двоичном виде?
  2. Если такое представление у некоторого натурального числа имеется, единственно ли оно?

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

Существование двоичного представления для любого натурального числа


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

Число 0 представимо так: $0 = 0*2^0$;

Число 1 тоже: $1 = 1*2^0$;

Предположим, что для всех натуральных чисел, меньших $n$ мы уже доказали возможность их представления в двоичном виде, покажем, что и само $n$ тоже можно так представить.

Число n либо четное, либо нечетное.

Если $n$ — четное и $n$ не ноль, то $n/2$ — есть некоторое натуральное число $k$, строго меньшее $n$. По индукционному предположению число $k$ можно представить как $k = x_0*2^m + ... + x_m*2^0$, где каждое $x_i$ есть либо 0, либо 1. Но $n = 2k = 2*(x_0*2^m + ... + x_m*2^0) = x_0*2^{m+1} + ... + x_m * 2^1 + 0*2^0$. Откуда следует, что двоичным представлением $n$ будет, например, двоичная последовательность $y = x_0, ... x_m, 0$.

Если $n$ — нечетное число, то число $(n-1)$ — строго меньше $n$ и является четным. Опять же, по предположению индукции число $(n-1)$ имеет некоторое двоичное представление: $(n-1) = x_0*2^m + ... x_{m-1}*2^1+ x_m*2^0$. Поскольку все, быть может кроме последнего слагаемого в этой сумме заведомо делятся на 2, то $(n-1)$ будет четным тогда и только тогда, когда четным является последнее слагаемое $x_m *2^0 = x_m$, но в таком случае $x_m$ должно быть нулем. Таким образом $(n-1) = x_0*2^m + ... x_{m-1}*2^1+ 0 *2^0$, но тогда $n = (n-1) + 1 = (n-1) = (x_0*2^m + ... x_{m-1}*2^1+ 0 *2^0) + 1 = x_0*2^m + ... x_{m-1}*2^1+ 1*2^0$ — есть двоично-степенное представление числа $n$.

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

Разложение степеней двойки. Геометрическая интерпретация


Чтобы решить вопрос единственностью, в алгоритме прибавления/вычитания единицы и еще много где, нам понадобится одно замечательное тождество:

$(2^{k-1} + 2^{k-2} + ... + 2^0) + 1 = 2^k $



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

Пусть $k>1$. Представьте $2^k$ одинаковых карандашей, уложенных в ряд и маленький флажок ровно в середине. Этот флажок займет положение аккуратно между острием предыдущего и тупым концом следующего карандаша в их ряду. Число карандашей в ряду слева от флажка будет $2^{k-1}$ штук, справа столько же.



(Слева от флажка $2^2$ карандашей справа столько же)

Если число карандашей в группе слева от флажка больше одного (то есть $2^{k-1} >1$), то переместим флажок в середину этой группы. Теперь слева от флажка $2^{k-2}$ карандаша, а справа $2^{k-1} + 2^{k-2}$.



(Слева от флажка $2^1$ карандаш, справа $2^2 + 2^1$ )

Будем перемещать флажок в середину остающегося от него по левую сторону группы карандашей вновь и вновь до тех пор, пока в ней не останется всего один карандаш. В этот момент справа число карандашей будет выражаться суммой $2^{k-1} + 2^{k-2} + ... + 2^0$. Для завершения доказательства остается только заметить, что общее число карандашей справа и слева от перемещения флажка никак не менялось и по-прежнему равно $2^k$.



(Слева от флажка $2^0 =1$ карандаш, справа $2^2 + 2^1 + 2^0$, всего в ряду $2^3$ карандашей)

Сравнение натуральных чисел в их двоичном представлении


Сейчас мы аккуратно докажем утверждение, которое применительно к десятичным числам воспринимается обычно как самоочевидное. Будем считать, что символ «0» меньше символа «1», тогда справедлива:

Лемма о сравнении двоичных чисел: Пусть $x = x_0 ... x_m$ и $y = y_0, ... y_m$ — двоичные слова одинаковой длины $m$, $n(x) = x_0*2^m + ... + x_m*2^0$ и $n(y) = y_0*2^m + ... + y_m*2^0$ — натуральные числа, которых эти двоичные слова представляют. Число $n(x)$ тогда и только тогда меньше числа $n(y)$, когда в первой слева позиции слов $x$ и $y$, в которой их символы различны, символ слова $x$ меньше, чем символ слова $y$. То есть, если $x_0 = y_0, x_1 = y_1, ..., x_{k-1} = y_{k-1}$, и $k$ — наименьший номер, такой что $x_k \neq y_k$, то неравенство $n(x)<n(y)$ равносильно неравенству $x_k < y_k$

Лемму о сравнении можно переформулировать еще и так: если длины слов $x$ и $y$ совпадают, то число $n(x)$ тогда и только тогда меньше числа $n(y)$, когда по отношению к лексикографическому порядку слово $x$ меньше слова $y$. Таким образом схема компаратора двоичных слов, которую мы построили в предыдущем параграфе, подходит и для сравнения величины двоичных чисел.

Доказательство.
Пусть $x$ и $y$ не совпадают полностью и $k$ — наименьший номер среди тех их позиций, в которых символы этих слов различны. Тогда $x_0 = y_0, x_1 = y_1, ..., x_{k-1} = y_{k-1}$, а значит первые $k$ слагаемых суммы $x_0*2^m + ... + x_m*2^0 = n(x)$ совпадают с первыми $k$ слагаемых суммы $y_0*2^m + ... + y_m*2^0 = n(y)$. Вычеркнем из обоих сумм эти первые $k$ слагаемых — такое действие на знак неравенства все равно никак не повлияет.

Первоначальная задача теперь свелась к необходимости сравнить суммы $x_k*2^{m-k} + ... + x_m*2^0 = n(x')$ и $y_k*2^{m-k} + ... + y_m*2^0 = n(y')$ (слово $x'$ есть последовательность $x_k, ... x_m$, а слово $y'$ есть последовательность $y_k, ... y_m$), причем нам заведомо известно, что $x_k \neq y_k$.

Предположим, что $x_k < y_k$. Последнее неравенство возможно только если $x_k = 0$, а $y_k = 1$, то есть $n(x') = 0*2^{m-k} + x_{k+1}*2^{m-k-1} + ... + x_m*2^0$ и $n(y) = 1*2^{m-k} + y_{k+1}*2^{m-k-1} + ... + y_m*2^0$. Поскольку все коэффициенты $x_i$ и $y_i$ в только что написанных суммах могут быть только нулями и единицами, то $n(x')$ заведомо не превосходит суммы $2^{m-k-1} +... + 2^0 = 2^{m-k} - 1$ (разложение степени двойки), а $n(y')$ заведомо не меньше суммы $1*2^{m-k} + 0*2^{m-k-1} + ... + 0*2^0 = 2^{m-k}$. Очевидным образом $2^{m-k} - 1$ строго меньше чем $2^{m-k}$, откуда следует, что $n(x')$ строго меньше $n(y')$, а значит и $n(x)$ строго меньше $n(y)$.

При симметричном предположении, что что $y_k < x_k$ рассуждения повторяются с точностью до замены буквы $x$ на букву $y$ и наоборот. Если читатель их проделает, то получит, что в этом случае $n(y)$ должно быть строго меньше $n(x)$. Тем самым все случаи (включая полное совпадения $x$ и $y$) нами рассмотрены и доказательство леммы можно считать завершенным.

Следствие (почти однозначность представления): Никакое натуральное число не может иметь двух различных двоичных представлений одной и той же длинны $m$.

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

Конечно, отказавшись от требования равенства длин представлений, мы обнаружим, что утверждение о единственности перестает быть верным. Например, число “один” представляют двоичные слова “1”, “01”, “001” и так далее.

Упражнение: докажите, что у всякого натурального числа большего нуля существует в точности одно двоичное представление, первым символом которого является “1”.

Конкатенация двоичных представлений


В математике конкатенацией $x*y$ (не обязательно двоичных) слов $x$ и $y$ называется слово, получающееся приписыванием слова $y$ непосредственно справа от $x$. Например, если $x=$”$abc$”, $y=$”$dfg$”, то $x*y = $“$abcdfg$”, а $y*x = $"$dfgabc$". Еще один пример уже для двоичных слов: $“1111” * ”000” = “1111000”$.

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

На формальном языке математики точное определение конкатенации звучит следующим образом: пусть $x = x_0, … x_m$ – цепочка символов длины $m+1$, $y = y_0, … y_n$ — цепочка символов длины $n+1$, тогда $x*y = (x*y)_0, … (x*y)_{m+n+1}$ — цепочка символов длины $m+n+2$, такая что символ $(x*y)_i$ совпадает с $x_i$ в случае, когда $i \leq m$, и совпадает с $y_{i – m - 1}$ в случае, когда $i>m$.

Легко проверить, что операция конкатенации ассоциативна, то есть для любых слов $x$, $y$ и $z$: $(x*y)*z = x*(y*z)$. В то же время конкатенация не коммутативна, если в словах разрешено использовать хотя бы два различных вида символов: $111*000 = 111000 \neq 000111 = 000*111$.
Для дальнейшего изложения нам также будет удобно вести еще несколько специальных определений.

Длину слова $w$, то есть число символов, составляющих w, будем обозначать как $|w|$.
Слово “$00...0$”, составленное из $k$ нулей, мы будем обозначать как $0^k$.
Слово “$11...1$”, составленное из $m$ единиц, мы будем обозначать как $1^m$.
Пустое слово “”, то есть слово, не содержащее ни одного символа, в математик по традиции обозначается греческой буквой $\varepsilon$ (эпсилон). Нам будет удобно считать, что пустое слово также представляет натуральное число: $n( \varepsilon ) = 0$.

Очевидным образом:
$0^p*0^q = 0^{p+q}$;
$1^p*1^q = 1^{p+q}$;
$0^0 = 1^0 = \varepsilon$;
$|0^k| = |1^k| = k$;
$|\varepsilon | = 0$;
для любого слова $x$: $\varepsilon * x = x * \varepsilon = x$;
для любых слов $x$ и $y$: $|x*y| = |x| + |y|$

В отношении того, как конкатенация двоичных слов влияет на величину представляемых этими словами чисел, верна следующая

Лемма о свойствах конкатенации двоичных чисел:

  1. $n(0^k) = 0$ — любая цепочка нулей является двоичным представлением числа ноль;
  2. $n(1^k) = 2^k - 1$ (лемма о разложении степени двойки);
  3. для любого двоичного слова $x$: $n(0^k * x) = n(x)$ (дописывание нулей слева к двоичному представлению, не меняет представляемого им числа);
  4. для любого двоичного слова $x$: $n(x * 0^k) = n(x) * 2^k$ (дописывание к двоичному слову каждого нуля справа увеличивает представляемое им число в 2 раза);
  5. для любых двоичных слов $x$ и $y$$n(x*y) = n(x) * 2^|y| + n(y)$;


Ее доказательство элементарно и предоставляется читателю в качестве еще одного упражнения.

Арифметические действия над двоичными числами


Если двоичное слово x представляет натуральное число, то само это слово мы договорились назвать двоичным числом. Давайте теперь для каждой арифметической операции $op$ над натуральными числами построим ее аналог $op’$ над множеством чисел двоичных. В своих определениях мы будем стремиться к тому, чтобы не было разницы между числом, которое представляет результат выполнения $op’$ над двоичными словами и числом, которое получено
в результате выполнения $op$ непосредственно над числами, которые эти аргументы-слова представляли. Сейчас вам все станет ясно на примере.

Суммой $x + y$ двоичных чисел $x$ и $y$ мы будем считать любое двоичное слово $z$, представляющее число $n(x)+n(y) = n(z)$. Так суммой двоичных чисел «001» и «100» является, например, двоичное число «00101».

Произведением $x*y$ двоичных чисел $x$ и $y$ назовем всякое двоичное слово $z$, представляющее число $n(x)*n(y) = n(z)$. Скажем произведением двоичных чисел «10», представляющего число 2 и «100», представляющего число 4 может считаться двоичное число «1000», поскольку оно представляет число 8.

Двоичное число $x$ считается меньше двоичного числа $y$ тогда и только тогда, когда $n(x) < n(y)$. Из доказанного нами выше следует, что двоичное число $x$ меньше одинакового с ним по длине двоичного числа $y$ тогда и только тогда, когда слово $x$ в лексикографическом порядке меньше слова $y$.

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

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

Каскадная схема для прибавления и вычитания из числа единицы


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


Пусть $x$ – двоичное натуральное число и мы хотим прибавить к $x$ единицу. Как это сделать?

Проще всего прибавлять единицу к числам, оканчивающимся на 0. Легко сообразить, что, если $x = w*”0”$, то $x+1 = w*”1”$ (читатель может проверить это обратившись к двоично-степенному представлению $n(x)$ или воспользовавшись пунктом 5) леммы о конкатенации). Как иллюстрация: $n(“100”) = 4$, $n(“1”) = 1$, $n(“101”) = 5$, поэтому $“100” + “1” = “101”$.

Другой сравнительно простой случай для прибавления единицы — это, когда двоичное число $x$ состоит из одних только единиц, то есть $x = 1^k$. Согласно лемме о разложении степени двойки слово $1^k$ представляет число $2^k- 1$, следовательно слово $x+1$ должно представлять $2^{k-1}$, для чего сгодится, например двоичное число $“1”*0^k$ ( $“111” = 4+2+1 = 8-1$, $“111”+”1” = “1000” = 8$ ).

Рассмотрим теперь произвольное двоичное число $х$, заканчивающееся символом единица, но не состоящее только из одних единиц. Пусть $m$ — длина $x$, а $k+1$ — наименьший по номеру разряд числа $x$, в котором стоит символ “0”. В таком случае слово $x$ можно представить как $x = w*”0”*1^k$, где $w = x_0, … x_{m-k-1}$ (например, двоичное слов «1010111» можно представить как «101»$*$«0»$*$«111»). Следовательно, двоично-степенное разложение $n(x)$ будет иметь вид:

$n(x) = (x_0 * 2^m + … + x_{m-k-1} * 2^{k+1}) + 0*2^k + (1*2^{k-1} + …+ 1*2^0)$,

где внутри вторых скобок стоит двоично-степенное разложение числа $n(1^k)$. Но по лемме о разложении степени двойки $n(1^k) = 2^k - 1$, откуда:

$n(x+1) = n(x) +1 = (x_0 * 2^m + … + x_{m-k-1} * 2^{k+1}) + 0*2^k + (2^k-1) + 1 =$
$= (x_0 * 2^m + … + x_{m-k-1} * 2^{k+1}) + 1*2^k + (0*2^{k-1} + … + 0*2^0) = n(w*1*0^k)$.

Последняя цепочка равенств показывает, что в качестве $x+1$ мы можем взять слово $w*”1”*0^k$.

Утверждение предыдущего абзаца можно доказать и по-другому. Обратимся к лемме о конкатенации и напишем цепочку равенств:

$n(x+1) = n(x) + 1 = n(w*”0”*1^k) + 1 = 2^{k+1}*n(w) + n(“0”*1^k) +1 = $
$= 2^{k+1}*n(w) + 2^k +0 = 2^{k+1}*n(w) + n(“1”*0^k) = n(w*”1”*0^k)$.

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

!) Чтобы прибавить к двоичному числу x единицу нужно первый c справа ноль в слове x заменить на единицу, а все стоящие перед этим нулем единицы — на нули.

Пример: $“1010111” + “1” = “1011000”$ (проверьте).

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

В остальном вычитать единицу проще всего из слов, которые на единицу заканчивающихся: для двоичного слова $x$ вида $x=w*1$ в качестве $x - 1$ можно зять слово $w*0$. Доказать последнее утверждение можно либо обратившись к двоично-степенному разложению $x$, либо воспользовавшись леммой о свойствах конкатенации и написав цепочку равенств:

$n(w*”1” - ”1”) = n(w*”1”) - 1 = 2*n(w) + 1 – 1 = 2*n(w) + 0 = $
$= 2*n(w) + n(“0”) = n(w*0)$.

Следующий сравнительно простой случай для вычитания единицы — это слова вида $“1”*0^k$. Поскольку $n(“1”*0^k) = 2^k$, то по лемме о разложении степеней двойки: $n(“1”*0^k - “1”) = n(“1”*0^k ) - 1 = 2^k –1 = n(0*1^k)$. Таким образом в качестве разности $“1”*0^k - “1”$ можно взять слово $0*1^k$.

Осталось рассмотреть проблему вычитания единицы из таких двоичных чисел, которые оканчиваются на 0, но при этом не являются словами вида $“1”*0^k$ и не состоят из одних нулей. Пусть $x$ – такое слово, тогда его можно представить как $x=w*”1”*0^k$. Нетрудно сообразить, что на роль $x-1$ подойдет слово $w*”0”*1^k$ — это можно доказать, как и с прибавлением единицы, обратившись к двоично-степенному разложению $x$, но можно и воспользоваться леммой о конкатенации:

$n(x-1) = n(x) - 1 = 2^{k+1} * n(w) + 2^k – 1 = 2^{k+1} * n{w} + n{“0”*1^{k}} = n{w*”0”*1^k}$.

Мы можем собрать все рассмотренные случаи для вычитания из числа единицы в один алгоритм с простой и короткой формулировкой:

!!) Чтобы вычесть из двоичного числа $x \neq 0$ единицу, нужно первую c справа единицу в слове $x$ заменить на ноль, а все стоящие перед этой единицей нули — на единицы.

Как вы сами видите, алгоритмы вычитания и прибавления к числу единицы очень похожи: каждый из них предписывает заменить на противоположные все символы слова $x$ с правого края вплоть до первого нуля, в случае прибавления, и вплоть до первой единицы, в случае вычитания из $x$ единицы. Из-за этой похожести мы совместим эти две операции в одной логической схеме.

Алгоритм прибавления и вычитания единицы в абстрактном виде


И так, чтобы прибавить или вычесть единицу из двоичного числа $x$, мы должны на каком-то участке от правого края $x$ заменить все символы на противоположные, а вне этого участка оставить их как есть. Алгоритм, который будет выполнять эти преобразования мы выстроим подобно тому, как был построен алгоритм сравнения двух слов.

За изменения в каждом разряде $p_i(x)$ слова $x$ назначим ответственными отдельную плеяду элементарных блоков, или, как мы ее будем еще называть, — операционную ячейка $cell_i$. Теперь нам нужно придумать способ, как сообщить ячейке $cell_i$, следует ли той заменить символ в разряде $p_i$ на противоположный или оставить его как есть. Подобно тому, как это организовано в алгоритме сравнения двоичных слов, потребуем, чтобы команда на изменение или сохранение значения $p_i$ приходила от предыдущей по номеру ячейки $cell_{i-1}$ (теперь $cell_{i-1}$ расположена справа от $cell_i$).

При таком способе организации алгоритма на ячейку $cell_i$ кроме задачи опционального изменения значений $p_i(x)$, ложится еще и ответственность за то, какие команды она пошлет ячейке $cell_{i+1}$. Поскольку прекращение каскада изменений в разрядах слова $x$ во время прибавления и во время вычитания единицы наступают при разных условиях, $cell_i$ должна также получать сведения о том, какая именно из этих двух операций в данный момент выполняется. Что ж, общий эскиз алгоритма мы обговорили, перейдем к конкретной его реализации:

  1. Положить $i=0$. Ввести два однобитных слова-состояния $(+1)_0$ и $(-1)_0$. Если на данном такте к слову $x$ должна быть прибавлена единица, положить $(+1)_0 =$ “истина”, $(-1)_0 = $“ложь”. Если единица должна быть отнята — положить $(+1)_0 = $“ложь”, $(-1)_0 = $“истина”. Перейти к шагу 2.
  2. Ввести два однобитных слова состояния: $(+1)_{i+1}$, имеющего смысл — “идет прибавление единицы, разряд $p_{i+1}$ должен быть преобразован”, и $(-1)_{i+1}$, имеющего смысл — “идет вычитание единицы, разряд $p_i$ должен быть преобразован”.

    Присвоить словам $(+1)_{i+1}$ и $(-1)_{i-1}$ значение по умолчанию “ложь”. Если $(+1)_i = $ “истина” и $p_i(x) = “1”$, то исправить значение $(+1)_{i+1}$ на “истина”. Если $(-1)_i =$ “истина” и $p_i(x) = “0”$, то исправить значение $(-1)_{i+1}$ на “истина”.

    Если хотя бы одно из слов-состояний $(+1)_i$ или $(-1)_i$ имеет значение истина, изменить символ в разряде $p_i$ слова $x$ на противоположный. Перейти к шагу 3.
  3. Если $p_i$ — самый большой разряд в $x$, то алгоритм завершен. Значения слов состояний $(+1)_{i+1}$ и $(-1)_{i+1}$ в таком случае трактуются как “произошло переполнение в результате операции +1” и “производилось недопустимое вычитание 1 из нуля” соответственно.

    Если $p_i$ — не последний разряд в $x$, то увеличить $i$ на единицу и вернуться к шагу 2.


Интерфейс логической схемы прибавления/вычитания единицы


Ниже мы построим схему способную на каждом такте прибавлять или вычитать единицу к текущему $m$-битному значению ее внешнего порта выхода $“x”$. Результат будет выведен на внешний $m$-битный входной порт $“(x \pm 1)”$. Какая именно операция будет выполнятся на данном задается с помощью текущих значений внешних однобитных выходных портов “(+1)” и “(-1)”. Чтобы результат был корректны, не более чем одному из портов $“(+1)”$ и $”(-1)”$ разрешено иметь значение “1”. Если оба этих порта имеют значение “0”, то значением порта $“(x \pm 1)”$ окажется само $x$. Случаи, когда единица вычитается из нуля, или для записи числа x+1 не достаточно m разрядов, отслеживаются внешними однобитными входными портами $“too \_small”$ и $“too \_big”$: если значение одного из них “истина”, значит произошла соответствующая ошибка и результат в $“(x \pm 1)”$ не корректен.

image

(интерфейс)

Перейдем теперь к внутренней архитектуре схемы.

Операционная ячейка


Схема операционной ячейки, представленная на рисунке …, разделена пунктирными прямоугольниками на две зоны: верхнюю — внутри кирпичного цвета прямоугольника, и нижнюю — внутри прямоугольника сиреневого цвета. Блоки нижней зоны отвечают за преобразование i-того разряда слова $x$, а блоки верхней — за формирования слов-команд для следующей по номеру операционной ячейки. Рассмотрим каждую зону подробно.


Начнем с нижней. Слова-команды $(+1)_i$ и $(-1)_i$, посланные предыдущей ячейкой поступают на входные порты блока “$or$”. Если хотя бы одно из этих слов имеет значение “истина”, блок “$or$” посылает на входной порт “$com$” мультиплексора "$mux_d$" значение “1”, в противном случае на этот порт приходит ноль “0”.

Блок “$not$” преобразует поступивший на его вход символ разряда $p_i(x)$ в противоположный, а результат посылает на вход "$arg2$" мультиплексора “$mux_d$”. В свою очередь, на "$arg1$" того же мультиплексора подается $p_i(x)$ в неизменном виде. Таким образом, если на текущем такте значение порта “$mux_d.com$” равно нулю, то $i$-тый разряд слова $(x \pm 1)$ будет копией $i$-того разряда слова $x$. В противном случает случае символом зазряда $p_I(x \pm 1)$ станет символ, противоположный $p_i(x)$.

Переходим к верхней зоне. Сюда входит “генератор лжи” — “0” и два прямых мультиплексора: "
"$mux_m$" и "$mux_p$", выходы которых формируют слова-команды $(-1)_{i+1}$ и $(+1)_{i+1}$. Давайте проверим, что значения эти слов получаются правильными.

Рассмотрим работу мультиплексора “$mux_m$”, отвечающего за команду $(-1)_{i+1}$. В зависимости от значения, полученного входным портом "$mux_m.com$", мультиплексор "$mux_m$" выбирает, какое из слов станет значением его выходного порта “$r$”: слово $(-1)_i$ на его входе “$arg1$”, или слово “0” на его входе “$arg2$”.

Когда $(-1)_i = “0”$, выбор не имеет значения: поскольку в этом случае, как и требует алгоритм, значение $(-1)_{i+1}$ все равно окажется нулем, то есть “ложью”. Осталось проверить правильность формирования $(-1)_{i+1}$ в условиях, когда $(-1)_i$ имеет значение “истина”.

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

Значением порта “$mux_m.com$” является копия символа в разряде $p_i(x)$. Если $p_i(x) =”1”$, мультиплексор “$mux_m$” копирует на выход “$mux_m.r$” значение своего входного порта “$arg2$”, то есть “ложь”. Как и требуется, в этом случае $(-1)_{i+1}$ получает значение “ложь”, тем самым обрывая каскад изменений. Если же $p_i(x) = “0”$, порт “$mux_m.r$” копирует значение порта, “$mux_m.arg1$”, то есть слово $(-1)_i$, которое по предположению выражает истину и, как того и требует алгоритм, каскад изменений разрядов $x$ продолжается.

Анализ правильности установления мультиплексором “$mux_p$” значений слова $(+1)_{i+1}$ проводится аналогично и предоставляется читателю.

Схема целиком


Чтобы получить полный чертеж схемы, реализующей прибавление/вычитание единицы из m-битного числа x, нам остается только соединить в каскад m описанных выше операционных ячеек и правильно подключить их к внешним портам. Как и в схеме компаратора, для разделения m-битного x на однобитные разряды мы применим блок обратной конкатенации $*^{-1}(1^m)$. Для объединения полученных на выходах ячеек m однобитных разрядов $p_i(x \pm 1)$ в одно m-битное слово $(x+1)$ используем блок прямой конкатенации $*(1^m)$. Вся схема целиком изображена на рисунке ниже.


Примерный план следующей статьи.


Составные блоки как обозначения фрагментов схемы.
… Проблема неинформативного дублирования.
… Сравнение работы фрагмента схемы с работой блока.
… Блок клок, который ничего не делает, наглядное преобразование фрагмента в блок.
… Использование готовых схем в качестве составных блоков в неэлементарных схемах
(пример с мультиплексором, рекурсивное определение компаратора и схемы \pm 1)
....K-битные массивы регистров и мультиплексоров.
… Схема “часы”.

Упрощенный взгляд на латентность схемы.
… Взгляд на работу блока как на преобразователь данных.
… Задержки в самом длинном пути.

Прямое, обратное и обоюдонаправленное адресное дерево.
… Адресное дерево как обобщение многоходового мультиплексора (интерфейс).
....K-битные массивы регистров и мультиплексоров.
… Развернутый чертеж n-битного k-ходового дерева для k=8 и k=7.
… Рекурсивное определение. Глубина.
… Замечание об энергоэффективности.
… Однопортовая пользовательская RAM.

Простейшие стеки
… Цепочка сдвиговых регистров и цепочка регистров задержки.
… Цепочка с возможностью извлечения данных.
… Идеальный абстрактный стек и абстрактный стек конечной длины, интерфейс схемы.
… Интерфейс и реализация одной ячейки памяти простейшего стека.
… Схема целиком, рекурсивное определение.
… Устройства контроля опустошения и наполнения с использованием счётчика.

Каскадная очередь.
… Абстрактное определение идеальной очереди, очередь конечного объема.
… Идея реализации на основе стека.
… Контроль точки записи.
… Управление одной ячейкой памяти очереди.
… Схема целиком, рекурсивное определение.

Каскадный сумматор двух k-битных чисел.
… Алгоритм сложения столбиком для двоичных чисел.
… Интерфейс и реализация ячейки, обрабатывающий i-тый разряд.
… Интерфейс и реализация всего устройства.
… Рекурсивное определение, оценка глубины и объема.
… Двухтактный сумматор

Комментарии (30)


  1. ermouth
    01.06.2022 21:26
    #24400268
    +5

    Простите, но совершенно невозможно же читать и смотреть, просто кровь из глаз.

    Для логических вентилей существуют стандартные обозначения, которые в любой версии (ANSI, IEC, ГОСТ – на выбор) гораздо лучше ваших самопальных, которые сплошь визуальный мусор.

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

    UPD. Для примера – как нужно записывать доказательство существование двоичного представления https://math.stackexchange.com/a/1966217/647986, просто сравните читаемость.


    1. Sergey_Kovalenko Автор
      01.06.2022 23:04
      #24400534
      +1

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

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

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


      1. ermouth
        01.06.2022 23:17
        #24400548

        не так много стандартных

        Пока не было ни одного нестандартного, и я уверен на 100%, что и не будет, в логических вентилях что-то новое выдумать сложно.

        Легко писать доказательство одному математику

        Я не математик, но то, что в примере читаю без запинок, а то, что у вас... Вы же не в Труды Стекловки пишете, правда? )


        1. Sergey_Kovalenko Автор
          01.06.2022 23:26
          #24400562
          +1

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

          В идеологических спорах трудно найти "правильную" точку зрения.


          1. karambaso
            02.06.2022 06:58
            #24400878
            +1

            В идеологических спорах трудно найти "правильную" точку зрения.

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

            Ну и до кучи - а почему бы не сократить подачу и не написать просто формулу для вашего устройства из примера? Отображение схемы на формулу объяснить очень просто, знаки "и", "или" можно даже на "*", "+" заменить, что бы максимально просто было. И краткость получится, не нужно отслеживать лабиринт из проводов на схеме.

            ЗЫ. Вчера смотрел новые посты, ваш сначала был, потом исчез. Хотел написать комментарий, а вы "сбежали", вместе с текстом в черновики. Хотя в результате обнаружил возможность постоянно держаться в топе списка - прячем в черновики и выкладываем снова раз в несколько часов. Вы так намеренно делали? Или стесняетесь критики и прячетесь в черновиках? Стесняться не надо, ошибки нужно признавать и исправлять, а прятаться постоянно - выглядит не очень.


            1. Sergey_Kovalenko Автор
              02.06.2022 07:27
              #24400908

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

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


    1. Ivanii
      02.06.2022 09:17
      #24401104
      +2

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


      1. Sergey_Kovalenko Автор
        02.06.2022 09:46
        #24401234

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

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

        Я предпочитаю придерживаться логики и соображений удобства. Надеюсь, вскоре и вы полюбите фристайл.


  1. AlexanderS
    02.06.2022 10:15
    #24401312

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


    1. Sergey_Kovalenko Автор
      02.06.2022 10:36
      #24401392
      -1

      А если миллион разных сценариев, но все их можно коротко описать словами. У стека даже конечной длинны бесконечно много непериодических сценарием поведения на множестве тактов [0, infinity). Как описать их все с помощью временных диаграмм?


      1. AlexanderS
        02.06.2022 11:02
        #24401516

        Зачем описывать все? Нужно обеспечить начальное базовое понимание. А дальше человек может сам хоть во временной области рисовать, хоть схемой, хоть словами, хоть математическим эквивалентом. Тут… все зависит от того на кого статья ориентирована. Я, например, и так разберусь. А вот для новичков будет тяжело.


        1. Sergey_Kovalenko Автор
          02.06.2022 11:39
          #24401642

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


  1. GarryC
    02.06.2022 10:23
    #24401334
    +2

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


    1. Sergey_Kovalenko Автор
      02.06.2022 10:44
      #24401440
      -1

      Принашу извинения за свои ошибки в словах.
      В остальном: мир не постоянен - все меняется.


  1. kmatveev
    02.06.2022 13:52
    #24402196
    +1

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

    1. Функциональность блока обозначается отдельным словом внизу, в отдельной рамке, да ещё и курсивом. На схемах ближе к концу статьи эти обозначения разглядеть невозможно. Обозначения в виде формы блока гораздо нагляднее

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

    3. Подписи для входов и выходов базовых блоков в большинстве случаев можно опустить

    4. Убивает то, что у автора для базовых блоков входные параметры незакрашенные, а выходные - закрашенные. А для схемы - наоборот.

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

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


    1. Sergey_Kovalenko Автор
      02.06.2022 14:16
      #24402274

      Спасибо за критику. Буду думать как улучшить.

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

      2) Я подумаю на этим.

      3) Подписи портов логических блоков опустить не получится, если есть желание менять местоположение портов относительно иконки блока.

      4)Насчет визуальной путанницы между входными/выходными портами схемы и ее блоков я дал подробное объяснение с начале статьи "Быстродействие элементарных схем", надеюсь, прочитав его, вы поймете мои мотивы и их логику.

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


      1. kmatveev
        02.06.2022 17:01
        #24402882
        +1

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

        1. Аналогично предыдущему, я не утверждал, что для всех случаев нужно убрать подписи, а для тех, где назначение порта очевидно. Это так, например, для всех стандартных блоков. У вас же входные и выходные порты различаются цветом, так зачем на базовом блоке "not" ещё что-то подписывать?

        2. Открыл предыдущую статью, охренел от её размера, на глаз не нашёл, где там это написано. Если логика "по проводкам сигнал идёт от чёрного к белому", то меня бы устроил такой ответ


        1. Sergey_Kovalenko Автор
          02.06.2022 17:21
          #24402984

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

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

          Пояснения, касающиеся понятия внешних входных и внешних выходных портов на схеме

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

          Однако, это не так. Наши формальные определения с такой аналогией идут в разрез.

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

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

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

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

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

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


          1. kmatveev
            02.06.2022 18:37
            #24403200

            Книга действительно рассчитана непонятно на кого, она плоха для всех. В ней нет ничего нового, значит не на электронщиков. Она плохо подходит для обучения, значит не на новичков. Для инженеров она слишком формалистична и непрактична. Если на математиков - нафига городить схемы вообще, достаточно сказать, что есть функции and, or, not, и всё, дальше достаточно любого математического формализма. Вы оправдываетесь, что вы математик, я верю плохо, как раз математикам свойственно делать всё максимально компактно и использовать иероглифы для выразительности.

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


            1. Sergey_Kovalenko Автор
              02.06.2022 18:52
              #24403232

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


              1. ermouth
                02.06.2022 22:28
                #24403786

                https://eccc.weizmann.ac.il/resources/pdf/OBDD-Book.pdf

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

                http://www.ime.cas.cn/icac/learning/learning_3/201909/P020190909561648570397.pdf тут немного про другое, гораздо ближе к реализации, но кое-где с вашими предыдущими публикациями отчасти пересекается. Подача очень формальная местами, но, кажется, вам так нравится.

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


                1. Sergey_Kovalenko Автор
                  03.06.2022 00:10
                  #24403948

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


                  1. ermouth
                    03.06.2022 06:30
                    #24404266

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

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

                    Вы насколько всерьёз будете относиться к выкладкам человека, который напишет что-нибудь типа «абазначем за ℂ множество вещественных чисел»? А ваша работа пока именно так выглядит.


                    1. Sergey_Kovalenko Автор
                      03.06.2022 08:30
                      #24404434

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


  1. Shmuma
    03.06.2022 11:35
    #24405174
    +1

    Большое спасибо за интересный материал и что не бросаете писать!

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

    С верилогом, наверное, много возни, но тоже не фатально. Например в известной книжке "Designing Video Game Hardware in Verilog" это решено через web-среду со всеми примерами.

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


    1. Sergey_Kovalenko Автор
      03.06.2022 13:05
      #24405626

      Спасибо за добрые слова и снисходительность к моему мышлению позапрошлого века. Да было бы здорово поэкспериментировать, - правда я в делах написания непосредственно HDL-программ не сведущ как первокурсник. Думаю, в каких-то азах недолго разобраться: концепция мне ясна. Я анализировал как синтаксис, так и семантику Verilog и VHDL, когда продумывал свой упрощенный язык. У меня была мечта, что кто-то среди нынешних студентов поможет мне сделать эксперименты. Это было бы полезно для такого человека, я думаю, Плюс возможность получать консультации по реализации тех или иных алгоритмов. Если вы можете меня порекомендовать кому-нибудь, буду благодарен.

      Книгу "Designing Video Game Hardware in Verilog" не видел, но обязательно посмотрю.


  1. gochaorg
    03.06.2022 23:21
    #24407532

    Предложение

    1. Ввести понятие памяти, бита - это про rs и t триггеры и как строится ячейка памяти и из чего она состоит. Просто на одной булевой логике не уедешь, т.к. не понятно как эта логика может содержать вычисления. Тот же вопрос сумматора необходимо понятие бита переноса. Я может плохо смотрел, его не увидел по биты памяти.

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

    3. Не плохо бы посвятить главу вопросу булевой логики при реализации ее в физике, те же диоды, транзисторы и т.д. в качестве примера физических воплощений привести примеры "домино" компьютер и компьютеры основанные на водных устройствах и та же машина Тюнинга в биологической клетке, не стандартные виды компьютеров это интересно. Можно отдельно разобрать логику "домино" компьютера, т.к. она на прямую не содержит И,ИЛИ,НЕ, но к ней сводиться через другие операции. Можно ещё вспомнить про компьютерные схемы из красной пыли/песка в Minecraft.

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

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

    То же применение, это не обязательно только специализированные языки проектирования схем/ПЛИС или как их там... А те же симуляторы микро-схем, коих много, да хоть Minecraft.

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

    Можно ещё вспомнить, что многие схемы были готовы и печатались в отдельных журнал в период позднего СССР


    1. Sergey_Kovalenko Автор
      03.06.2022 23:34
      #24407550

      1) Среди элементарных блоков присутствую однобитные регистры с/без портом "enable" и "reset" во всех комбинациях.

      2) Об этом есть немного в предыдущей статье "быстродействие элементарных схем", но понятие бистабильности как таковое не затрагивается, поскольку намеренно выбран более высокий уровень абстракции.

      3) Есть некоторая цель и лимит страниц средней книги. Не получится написать обо всем.

      4) Формальные языки в этой книге всего лишь средство, не цель исследования.


    1. gochaorg
      03.06.2022 23:49
      #24407594

      Извините, прострел предыдущую статью по фронт сигнала там есть.


      1. Sergey_Kovalenko Автор
        03.06.2022 23:55
        #24407612

        Да извинятся в общем-то не за что. Спрашивайте - если смогу, постараюсь ответить.