Релейно контактные схемы в ЭВМ

Первая электронно-вычислительная машина была создана в 1946 г. в США. Для записи и обработки в ЭВМ числовой и символьной информации удобным с технической точки зрения оказался язык двоичных чисел — нулей и единиц. Поэтому естественно было ожидать, что методы математической науки, исследовавшей двузначные функции, рано или поздно найдут применение в процессе создания такой техники. Впервые предположение о возможности применения алгебры логики в технике было высказано в 1910 г. известным физиком П.Эренфестом (1880— 1933). Булевы Функции стали математическим аппаратом для исследования релейно-контактных схем (эта связь окончательно была осознана в 1930-х гг.), а сами схемы к середине XX в. нашли многочисленные применения в автоматической технике — в телефонии, железно-дорожной сигнализации, централизации и блокировке, релейной защите, телемеханике и, наконец, — при проектировании быстродействующих ЭВМ. О некоторых простых, но очень важных ре-лейно-контактных схемах, используемых в ЭВМ, и пойдет речь в настоящем параграфе.

Двоичный полусумматор

Числа в ЭВМ хранятся в двоичной системе в ячейках памяти поразрядно. С технической точки зрения в двоичной системе оказалось удобно не только хранить числа, но и выполнять над ними различные действия. Так, сложение двоичных чисел осуществляется на основе следующих правил:

[cbm]0+ 0 = 0,\quad 0 + 1 = 1,\quad 1 + 0=1,\quad 1 + 1 = 10.[/cbm]

Сложение по этим правилам делается по каждому разряду двух ячеек, в которых хранятся слагаемые. Если же происходит переполнение данного разряда (что возможно только при сложении [cbm]1+1[/cbm] ), то происходит перенос единицы в следующий разряд. Таким образом, процесс сложения в одном разряде может быть охарактеризован двумя булевыми функциями: [cbm]S(x,y)[/cbm] и [cbm]P(x,y)[/cbm] , зависящими от складываемых чисел [cbm]x[/cbm] и [cbm]y[/cbm] . Первая функция [cbm]S(x,y)[/cbm] представляет собой значение суммы, записываемое в тот же разряд соответствующей ячейки, в котором происходит сложение. Вторая функция — функция переноса [cbm]P(x,y)[/cbm] — дает значение числа, переносимого в следующий, более старший разряд при переполнении разряда, в котором происходит сложение. Таблица истинности этих функций следующая:

[cbm]\begin{array}{|c|c||c|c|}\hline x& y& S(x,y)& P(x,y)\\\hline 0&0&0&0\\ 0&1&1&0\\ 1&0&1&0\\ 1&1&0&1\\\hline \end{array}[/cbm]

Используя СДН-формы, выписываем для них выражения, по которым легко построить соответствующие релейно-контактные схемы:

[cbm]S(x,y)=x'y\lor xy',\qquad P(x,y)= xy\,.[/cbm]

Одноразрядный двоичный сумматор

При сложении двух чисел описанные в предыдущем пункте действия совершаются лишь в первом (самом младшем) разряде ячеек, хранящих слагаемые. Во всех же остальных разрядах, начиная со второго, в процессе сложения участвуют уже не два слагаемых [cbm]x_k[/cbm] и [cbm]y_k[/cbm] , но еще и число, переносимое из предыдущего разряда и равное значению функции переноса [cbm]P_{k-1}(x_{k-1},y_{k-1})[/cbm] в этом разряде. Таким образом, функция сумма [cbm]S_k[/cbm] в k-м разряде [cbm](k\geqslant2)[/cbm] зависит от трех аргументов, т.е. [cbm]S_k=S_k(x_k,y_k,P_{k-1})[/cbm] . От этих же аргументов зависит и функция переноса из k-го разряда [cbm]P_k(x_k,y_k,P_{k-1})[/cbm] . Составим таблицу значений этих функций:

[cbm]\begin{array}{|c|c|c||c|c|}\hline x_k& y_k& P_k& S_k(x_k,y_k,P_{k-1})& P_k(x_k,y_k,P_{k-1})\\\hline 0&0&0&0&0\\ 0&0&1&1&0\\ 0&1&0&1&0\\ 0&1&1&0&1\\ 1&0&0&1&0\\ 1&0&1&0&1\\ 1&1&0&0&1\\ 1&1&1&1&1\\\hline \end{array}[/cbm]

Используя СДН-формы, найдем для них выражения, которые затем упростим, преобразуя тождественным образом:

[cbm]\begin{aligned} S(x,y,p)&= \bigvee\limits_{S(\alpha, \beta, \gamma)=1} x^{\alpha} y^{\beta} p^{\gamma}= x^0y^0p^1 \lor x^0y^1p^0 \lor x^1y^0p^0 \lor x^1y^1p^1=\\ &=x'y'p \lor x'yp' \lor xy'p' \lor xyp= (x'y'\lor xy)p' \lor (x'y\lor xy')p'\,;\\[5pt] P(x,y,p)&= \bigvee\limits_{P(\alpha, \beta,\gamma)=1} x^{\alpha}y^{\beta}p^{\gamma}= x^0y'p' \lor x^1y^0p^1 \lor x^1y^1p^0 \lor x^1y^1p^1=\\ &=x'yp \lor xy'p \lor xyp' \lor xyp= (x'yp\lor xyp) \lor (xy'p\lor xyp) \lor (xyp'\lor xyp)=\\ &=(x'\lor x)yp \lor (y'\lor y)xp \lor (p'\lor p)xy = xp\lor yp\lor xy\,.\end{aligned}[/cbm]

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


Шифратор и дешифратор

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

[cbm]\begin{array}{|c|c||c|c|}\hline \operatorname{Decimal} & \operatorname{Binary} & \operatorname{Decimal} & \operatorname{Binary}\\\hline 0& 0000& 5& 0101\\ 1& 0001& 6& 0110\\ 2& 0010& 7& 0111\\ 3& 0011& 8& 1000\\ 4& 0100& 9& 1001\\\hline \end{array}[/cbm]

Каждую колонку из нулей и единиц в правом столбце таблицы можно мыслить себе как колонку значений одной из булевых функций: [cbm]f_1,f_2,f_4,f_8[/cbm] . Нужно лишь отчетливо усмотреть булеву (т.е. двузначную) природу ее аргументов.

В самом деле, можем считать, что каждая из этих функций зависит от десяти аргументов

[cbm]x_0,~ x_1,~ x_2,~ x_3,~ x_4,~ x_5,~ x_6,~ x_7,~ x_8,~ x_9\,.[/cbm]

Причем зависимость следующая (она обусловлена предыдущей таблицей соответствий):

[cbm]\begin{array}{|c|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline x_0 & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 & x_9 & f_8 & f_4 & f_2 & f_1\\\hline 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& \mathsf{1} & 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \mathsf{1} \\ 0& 0& \mathsf{1} & 0& 0& 0& 0& 0& 0& 0& 0& 0& \mathsf{1} & 0\\ 0& 0& 0& \mathsf{1} & 0& 0& 0& 0& 0& 0& 0& 0& \mathsf{1} & \mathsf{1} \\ 0& 0& 0& 0& \mathsf{1} & 0& 0& 0& 0& 0& 0& \mathsf{1} & 0& 0\\ 0& 0& 0& 0& 0& \mathsf{1} & 0& 0& 0& 0& 0& \mathsf{1} & 0& \mathsf{1} \\ 0& 0& 0& 0& 0& 0& \mathsf{1} & 0& 0& 0& 0& \mathsf{1} & 0& 0\\ 0& 0& 0& 0& 0& 0& 0& \mathsf{1} & 0& 0& 0& \mathsf{1} & 0& \mathsf{1} \\ 0& 0& 0& 0& 0& 0& 0& 0& \mathsf{1} & 0& \mathsf{1} & 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& \mathsf{1} & \mathsf{1} & 0& 0& \mathsf{1} \\\hline \end{array}[/cbm]

Каждая из функций [cbm]f_1,f_2,f_4[/cbm] и [cbm]f_8[/cbm] зависит от десяти аргументов. Поэтому таблица их значений должна содержать (что установлено при доказательстве теоремы 10.3) [cbm]2^{10}[/cbm] строк. Отсутствие остальных строк в приведенной таблице означает, что на указанных десяти наборах значений аргументов

[cbm]x_0,~ x_1,~ x_2,~ x_3,~ x_4,~ x_5,~ x_6,~ x_7,~ x_8,~ x_9\,.[/cbm]

функции должны принимать указанные значения, а на остальных наборах их значения могут быть какими угодно. Это, в свою очередь, означает, что в качестве каждой из функций [cbm]f_1,f_2,f_4,f_8[/cbm] можно взять довольно много (но все же конечное число) функций.

Используя СДН-форму, найдем, например, выражение для [cbm]f_8[/cbm] (считая, что на всех не указанных наборах значений ее аргументов она принимает значение 0):

[cbm]\begin{aligned}f_8(x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9)&= x'_0 x'_1 x'_2 x'_3 x'_4 x'_5 x'_6 x'_7 x'_8 x'_9 \lor x'_0 x'_1 x'_2 x'_3 x'_4 x'_5 x'_6 x'_7 x'_8 x_9= \\[2pt] &= x'_0 x'_1 x'_2 x'_3 x'_4 x'_5 x'_6 x'_7 (x_8x'_9\lor x'_8x_9). \end{aligned}[/cbm]

Для остальных функций [cbm]f_1,f_2[/cbm] и [cbm]f_4[/cbm] найти соответствующие выражения предлагается самостоятельно.

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: