Компараторы
Компаратор – комбинационная схема, реализующая сравнение двух операндов, представленных двоичными кодами, т.е. это функциональный узел, функцией которого является проверка условий вида
А = В, А ¹ B, А £ В, А > В, А ³ В, А < В
и вычисление по результатам такой проверки значения логической переменной, которая прини-мает значение 1, если анализируемое условие выполняется, и значение 0 – в противном случае. Здесь A и B – (n + 1)‑разрядные двоичные числа:
A = anan-1…a0, B = bnbn-1…b0.
Поскольку любая операция сравнения многоразрядных чисел основана на сравнении цифр в одноименных разрядах этих чисел, то следует подробно рассмотреть операцию сравнения цифр аi и bi из i-го разряда A и B, соответственно.
Сумма по модулю 2. Сумма по модулю 2 (операция М2) – это ПФ, которая для двух булевых переменных а и b задается табл. 1.4. Для операции М2 используют обозначение Å. Тогда наряду с табл. 1.4 можно записать
y = ai Å bi.
Таблица 1.4
ПФ суммы по модулю 2 для двух булевых переменных а и b
| ai | bi | y |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Для элемента, выполняющего операцию М2, используем УГО на рис. 1.13, а. Пользуясь табл. 1.4, легко выразить операцию М2 в терминах булевой алгебры (рис. 1.13, б)
. (1.3)
Реализация этой ПФ в базисе И-НЕ показана на рис. 1.13, в. А на рис. 1.13, г показана такая реализация функции М2 в базисе И-НЕ, когда не требуется иметь инверсных значений операндов.
Операцию М2 можно записать и для случая, когда число аргументов больше двух
y = xn Å xn-1 Å ¼ Å x0.
Результат такой операции совпадает с результатом вычисления
(xn + xn-1 + ¼ + x0)mod2 –
остатка от деления арифметической суммы аргументов на два (чем и объясняется название этой функции М2). Таким образом, операция М2 (сумма по модулю 2) – многоместная переключательная функция, определяемая как
y = xn Å xn-1 Å ¼ Å x0 = (xn + xn-1 + ¼ + x0)mod2.
ОперацияМ2, как и операции Шеффера и Пирса, обладает функциональной полнотой. Теория ПФ, основанная на операции М2, называется алгеброй Жегалкина. Из всей системы тождеств алгебры Жегалкина выделим такие:
A Å 0 = A, A Å 1 = 
, (1.4)
A Å 
= Å B = ù(A Å B). (1.5)
Здесь А и B – либо логические переменные, либо ПФ. Свойства (1.4) операции М2 позволяют использовать элемент М2 в качестве управляемого инвертора (рис. 1.13, е)
Тождество (1.5) означает, что инверсия одного из операндов в операции М2 приводит к инверсии ее результата.
Рис. 1.13. УГО элемента, выполняющего операцию М2, операция М2 согласно табл. 1.4, реализация ПФ (1.3) в базисе И-НЕ, реализация функции М2 в базисе И-НЕ, когда не требуется иметь инверсных значений операндов, использование элемента М2 в качестве управляемого инвертора, УГО элемента для вычисления ùМ2
Нередко для функции М2 используют и такое название, как неравнозначность, исключающее ИЛИ (XOR). В общем случае неравнозначность – такая ПФ, которая принимает значение 0 на тех наборах своих аргументов, на которых все они равны нулю или единице. На остальных наборах неравнозначность принимает значение 1. Исключающее ИЛИ (XOR) – ПФ, которая равна единице лишь тогда, когда в наборе ее аргументов только один равен единице. Таблицы истинности функцийМ2, неравнозначности и XOR для двух переменных совпадают с табл. 1.4. При большем числе переменных неравнозначность и XOR существенно отличаются от М2, что и подтверждает табл. 1.5. Значит, использование их названий в качестве синонимов М2 неправомерно.
Таблица 1.5
Неравнозначность и XOR при большом числе переменных
| ai | bi | ci | M2 | Неравнозначность | XOR |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Ради удобства выполнения операции сравнения чисел одновременно с функциейМ2 вычисляют и ее инверсию
ùM2 = ù(ai Å bi) = 
.
На рис. 1.13, ж показано УГО элемента для вычисления ùМ2.
Сравнение многоразрядных чисел. По результатам анализа указанных выше отношений между числами а и в можно вычислить следующие ПФ:
;
;
;
;
;
.
Анализируя эти функции, можем заключить, что любые соотношения между числами А и В можно описать суперпозицией двух ПФ
F(A = B) и F(A £ B).
Действительно,
F(A ¹ B) = ùF(A = B),
F(A < B) = F(A £ B) ÙùF(A = B),
F(A ³ B) = ùF(A < B) = ùF(A £ B) Ú F(A = B),
F(A > B) = ùF(A £ B).
Процедуру сравнения чисел
A = anan-1 ... a0;
B = bnbn-1 ... b0
выполняют путем последовательного сравнения (k + 1)-разрядных чисел
Ak = akak-1 ... a0;
Bk = bkbk-1 ... b0;
.
Для того чтобы описать эту процедуру, введем такие две ПФ
jk (Ak, Bk) = F(Ak = Bk);
fk (Ak, Bk) = F(Ak £ Bk).
Вычисление jk и fk начнем с k = 0 (табл. 1.6). Из этой таблицы следует, что
j0 = F(A0 = B0) = ù(a0 Å b0), (1.6)
f0 = F(A0 = B0) Ú F(A0 < B0) = F(A0 £ B0) = ù(a0 Å b0) . (1.7)
Таблица 1.6
Результаты вычислений fk и jk
| a0 | b0 | j0 | f0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Пусть теперь имеем функции j0 и f0, а также числа А1 = а1а0 и B1 = b1 b0. Составим таблицу истинности для функций j1 и f1 (т.е. для k = 1), аргументами которых будут j0, f0, а1, b1. Чтобы облегчить разработку этой таблицы, введем в нее для справки колонки А1 = а1а0 и B1= b1b0. Цифры а1, b1 в этих колонках распределим так же, как они распределены в наборах {j0, f0, а1, b1}, а цифры а и b для каждой строки этих справочных колонок возьмем из табл. 1.6 такие, которые отвечают значениям j0 и f0 в данной строке разрабатываемой таблицы. В табл. 1.6 нет такого сочетания j0, f0 = 10. Следовательно, функции ji и fi на всех наборах { 1, 0, а1, b1 } не определены. Значения ji = F(Ai = Bi) и fi = F(Ai £ Bi) на остальных наборах определим по результатам сравнения чисел Ai и Bi в справочных колонках. Так получим табл. 1.7, используя которую можно найти выражения для j1 и f1.
Таблица 1.7
Таблица истинности для функций j1 и f1
| A1 | a0 | b1 | b0 | j0 | f0 | a1 | b1 | j1 | f1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | * | 0 | * | 1 | 0 | 0 | 0 | * | * |
| 0 | * | 0 | * | 1 | 0 | 0 | 1 | * | * |
| 1 | * | 1 | * | 1 | 0 | 1 | 0 | * | * |
| 1 | * | 1 | * | 1 | 0 | 1 | 1 | * | * |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Точно так же разрабатываются таблицы истинности и формулы для jk и fk при k = 2,3,..., аргументами в которых (наряду с другими) выступают ранее полученные jk–1 и fk–1
(1.8)
.
Ради единообразия формулы для j0 и f0 запишем так:
j0 = j–1 × ù(a0 Å b0);
f0 = f–1 × ù(a0 Å b0) Ú 
.
Ясно, что при j–1 = f–1 = 1 результатами процедуры (1.8) для текущего значения k будут величины
jk = F(Ak = Bk);
fk = F(Ak £ Bk).
Интерес представляют результаты процедуры (1.8) и при других значениях j–1 и f–1. Пусть j–1 = a–1 = 0. Тогда для jk получим
jk = j–1 Ù ù(a0 Å b0) Ù ù(a1 Å b1) Ù¼Ù ù(ak Å bk) = 0.
А вот для fk (k = 0,1,...) последовательно получаем
f0 = f–1 × ù(a0 Å b0) Ú = 0 × F(a0 = b0) Ú F(a0 < b0) = F(A0 < B0),
f1 = f0 × ù(a1 Å b1) Ú 
= F(a0 < b0) × F(a1 = b1) Ú F(a1 < b1) = F(A1 < B1),
fk = F(Ak < Bk).
Теперь легко определить, что при j–1= 0, f–1= 1
jk = 0, fk = F(Ak £ Bk),
а при j–1 = 1, f–1 = 0
jk = F(Ak = Bk), fk = F(Ak < Bk).
Таким образом, сигналы j–1 и f–1 на входе самой первой ступени реализации процедуры (1.8) можно использовать для управления режимом работы компаратора (табл. 1.8), структура которого показана на рис. 1.14.
Рис. 1.14. Структура компоратора
Таблица 1.8
Сигналы j–1 и f–1 на входе первой ступени и режимы работы компаратора
| j | f-1 | jn | Fn |
| 0 | 0 | 0 | F(A< B) |
| 0 | 1 | 0 | F(A £ B) |
| 1 | 0 | F(A = B) | F(A < B) |
| 1 | 1 | F(A = B) | F(A £ B) |
Существенным недостатком такого компаратора является его низкое быстродействие из-за того, что значения jk и fk на выходе k-й ступени получают только после определения значений jk–1 и fk–1. Из анализа (1.8) следует, что после подачи сигнала fk–1 задержка в формировании значения fk составит
tf = tM + tC + tD,
где tM, tC, tD – задержка в элементе ùM2, в конъюнкторе и в дизъюнкторе, соответственно (названные операции выполняются последовательно). Поэтому результат fD будет получен по истечении времени
T= = ntf.
Радикальный способ повышения быстродействия компаратора заключается в следующем. Имея систему выражений (1.8), подставим последовательно выражение для jk–1 и fk–1, начиная с k = 1, в формулы для jk и fk, соответственно. Тогда для jD и fD получим формулы, операндами в которых будут только j–1, f–1= {0, 1} и цифры сравниваемых чисел А и В. Так, к примеру, при n + 1 = 4 для j3 и f3 получим такие формулы:
j3 = j-1 × 
ù(ak Å bk); (1.9)
f3 = 
ù(a3 Å b3) Ú 
ù(a3 Å b3) ×ù(a2 Å b2) Ú
Ú 
ù(ak Å bk) Úf–1 × ù(ak Å bk). (1.10)
Теперь задержка в формировании значения fn не зависит от n и равна
Т= = tf.
Из табл. 1.8 следует, что
jn = j–1 × F(A = B); (1.11)
fn = f–1 × F(A = B) Ú F(A < B). (1.12)
В реальных компараторах помимо (1.11) и (1.12) вычисляют еще и такую функцию:
gn = g–1 ù(jn Ú fn).
Очевидно, что при g–1 = 1 gn = F(A > B). B общем же случае, когда
g–1= {0, 1},
gn = g–1 × (
F(A = B) Ú F(A > B)). (1.13)
Соотношения (1.11), (1.12) и (1.13) при (n + 1) = 4 и реализует ИС 564ИП2 – 4-разрядный компаратор, УГО которого приведено на рис. 1.15. Настройка этой ИС на заданный режим работы производится должным выбором значений управляющих сигналов g–1, j–1 и f–1 по табл. 1.9. Наращивание разрядности компараторов на данной ИС выполняется простым соединением выходов младшей ИС с одноименными входами старшей ИС. Правда, если (n + 1) = 4 × m, то при этом быстродействие (n + 1)-разрядного компаратора составит величину m × tf.
Рис. 1.15. УГО 4-разрядного компаратора
Таблица 1.9
Управляющие сигналы g–1, j–1 и f–1
| g–1 | j–1 | f–1 | g3 | j3 | F3 |
| 0 | 0 | 0 | 0 | 0 | F(A < B) |
| 0 | 0 | 1 | 0 | 0 | F(A £ B) |
| 0 | 1 | 0 | 0 | F(A = B) | F(A < B) |
| 0 | 1 | 1 | 0 | F(A = B) | F(A £ B) |
| 1 | 0 | 0 | F(A ³ B) | 0 | F(A < B) |
| 1 | 0 | 1 | F(A > B) | 0 | F(A £ B) |
| 1 | 1 | 0 | F(A > B) | F(A = B) | F(A < B) |
| 1 | 1 | 1 | F(A > B) | F(A = B) | F(A £ B) |