Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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


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


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

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


[math]\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}[/math]

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


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



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


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


[math]\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}[/math]

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


[math]\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}[/math]

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




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


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


[math]\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}[/math]

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


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


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

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


[math]\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}[/math]

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


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

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


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


[math]\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}[/math]

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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved