Лекции / Схемотехника ЭВМ. Лекция 14. Компараторы

Глава 5. Цифровые компараторы

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

Цифровые компараторы находят широкое применение для реализации операций сравнения порядков и мантисс чисел, представленных в форме с плавающей запятой, построения счётчиков и сумматоров по произвольному модулю, для организации ветвящихся процессов (условных переходов) в блоках микропрограммного управления, в устройствах контроля и диагностики цифровых приборов, для выявления нужного кода в последовательном потоке данных, в таймерах, для определения внешних устройств, взаимодействующих в данный момент времени с ЭВМ, для сигнализации о выходе величины за пределы допуска, в цифровых следящих системах для определения направления воздействия, в устройствах стабилизации, для сравнения признаков (тэгов) в КЭШ-памяти, для определения границ страниц памяти; в качестве программируемого дешифратора (детектора состояний) и т.д.

Вцифровых устройствах наиболее часто встречаются следующие операции сравнения чисел: сравнение по модулю, сравнение чисел с учётом их знаков, сравнение порядков и мантисс чисел, представленных

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

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

• компараторы по величине или схемы сравнения чисел (magnitude comparator);

• компараторы тождественности (идентичности, равенства) или схемы равнозначности кодов (identity comparator);

• компараторы, программируемые пережигаемыми перемычками

(fuse-programmable identity comparator);

• адресные компараторы (address comparator), являющиеся, по существу, программируемыми дешифраторами (детекторами) состояний.

5.1. Компараторы по величине

Рассмотрим уравнения и структуру простейшего компаратора, предназначенного для сравнения двух одноразрядных чисел. Его функционирование представлено в табл.5.1, где а и b - одноразрядные срав-

ниваемые числа; F< - выходной сигнал отношения «a меньше b» (F< - сокращенная запись Fa<b) и т.д.

Таблица 5.1

Таблица истинности для однобитного компаратора

	набораНомер	a	b	F<	F=	F>	F≤	F≥
	0	0	0	0	1	0	1	1
	1	0	1	1	0	0	1	0
	2	1	0	0	0	1	0	1
	3	1	1	0	1	0	1	1

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

«1», если нет, то «0».

Из табл.5.1 получаем

F< =

(5.1)

ab ,

F= =

(5.2)

ab +ab = a b ,

,

(5.3)

F> = ab

F≤ =

=

,

(5.4)

a

F>

+b = ab

F≥ = a +

=

b

ab = F< .

(5.5)

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

двух. Например, если за основные взять отношения F< и F=, то отношение F> может быть получено как

F> =

F

<

F

= =

F< +F=

.

(5.6)

Выражение (5.6) говорит о том, что a > b, если a и не меньше и не равно b. Аналогично можно записать

F= =

F

<

F

> =

F< + F>

;

(5.7)

F< =

=

> =

.

(5.8)

F

F

F= + F>

Напомним, что F= = ab +ab называется функцией равнозначности двух переменных, причём она является отрицанием функции «сумма по

модулю 2» ( ab +ab = a b ).

В связи с тем, что уравнения (5.1) - (5.5) легко реализуются простейшими логическими элементами, однобитовый компаратор не выполняется в виде специализированной интегральной схемы. Он применяется в основном для сравнения многоразрядных чисел, представленных последовательными кодами, причём на его входы числа подаются поразрядно старшими разрядами вперед. Среднее время сравнения большой совокупности произвольных чисел в данном случае равно n/2, где n - разрядность чисел (минимальное время - 0 тактов, а максимальное - n тактов).

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

нение (5.9)).

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

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

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

величине выполняется с тремя выходами F<, F= и F>. Следует обратить внимание, что в строках табл.5.1, соответствующих только этим трём отношениям, присутствует одна единица.

Рассмотрим теперь уравнения, описывающие наращиваемые компараторы, на примере четырёхразрядных микросхем, и структуры многоразрядных компараторов, выполненных на их основе. На рис.5.1 иллюстрируется идея построения наращиваемых компараторов.

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

F< ; F= ; F>

A

a3

a2

a1

a0

...

B

b3

b2

b1

b0

...

f< ; f= ; f>

F< ; F= ; F>

A

a3

a2

a1

a0

B

b3

b2

b1

b0

f< ; f= ; f>

Рис.5.1. Иллюстрация наращивания разрядности сравниваемых двоичных чисел

Индексация переменных ai и bi выделенных старших разрядов соответствует индексации разрядов на функциональном обозначении микросхемы компаратора (рис.5.2).

Фактический вес этих разрядов в общем случае может быть любым. Отношение F< для чисел А и В будет выполняться в пяти случаях:

1)a3 < b3;

2)a3 = b3 и a2 < b2;

3)a3 = b3 и a2 = b2 и a1 < b1;

4)a3 = b3 и a2 = b2 и a1 = b1 и a0 < b0;

5)a3 = b3 и a2 = b2 и a1 = b1 и a0 = b0 и f< = 1,

где f< - отношение А < В для всей оставшейся части младших разрядов сравниваемых чисел (считаем, что значение f< известно, а как оно получено, пока нас не интересует).

	a3	= =
	a2
	a1
	a0		F<
	b3
			F=
	b2
	b1		F>
	b0
	f<
	f=
	f>

Рис.5.2. Функциональное обозначение четырёхразрядного наращиваемого компаратора

С учётом сказанного, можно записать следующее уравнение:

F< = a3b3 +a3 b3 a2b2 +

+a3 b3 a2 b2 a1b1 + (5.9) +a3 b3 a2 b2 a1 b1 a0b0 +

+a3 b3 a2 b2 a1 b1 a0 b0 f<.

Отношение F= будет выполняться, когда все разряды сравниваемых чисел равны:

F= = a3 b3 a2 b2 a1 b1 a0 b0 f= , (5.10)

где f= - отношение А = В для всей оставшейся части младших разрядов сравниваемых чисел.

Выражение для F> может быть записано либо по форме, аналогичной уравнению (5.9), а именно:

F> = a3b3 +a3 b3 a2 b2 +

+a3 b3 a2 b2 a1b1 + (5.11) +a3 b3 a2 b2 a1 b1 a0 b0 +

+a3 b3 a2 b2 a1 b1 a0 b0 f>,

где f> - отношение А > B для всей оставшейся части младших разрядов сравниваемых чисел, либо в виде (см. выражение (5.6))

F> =	F	<	F	= f> =	F< + F=	f> = F< + F= +		f	> .		(5.12)

Применяя формальные методы минимизации, для функций F< и F> можно получить следующие выражения:

F< = a3b3 +a3b3 a2b2 +

+a3		b	3 a2			b	2		a	1b1	+
											(5.13)

+a3b3 a2 b2 a1b1 a0b0 +

+a3b3 a2 b2 a1b1 a0 b0 f<,

F> = a3b3 +a3b3 a2 b2 +

+	a	3b3		a	2b2	a1		b	1		+
											(5.14)

+a3b3 a2b2 a1b1 a0 b0 +

+a3b3 a2b2 a1b1 a0b0 f>.

Итак, зная четыре старших разряда сравниваемых многоразрядных чисел и сигналы отношения f< , f= и f> для всей оставшейся части

младших разрядов этих чисел, можно легко вычислить окончательные

отношения F<, F= и F>.

Если теперь требуется увеличить разрядность сравниваемых чисел в сторону старших разрядов на четыре (см. числа A′ и B′ в верхней части рис.5.1), то и в этом случае можно записать те же уравнения (5.9) - (5.14), причём в качестве f< , f= и f> в них будут фигурировать

отношения F<, F= и F>, полученные для нижней части рис.5.1. Ясно, что таким образом можно увеличивать разрядность сравниваемых чисел до

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

Входы ai и bi принято называть информационными, а входы f< , f= и f> - расширительными или каскадными. Примерами таких из-

делий могут служить интегральные схемы типа 134СП1 (74L85),

К555СП1 (SN74LS85N), 564ИП2 (CD4585AK), CD4063B и др. Хотя в функциональном отношении все эти интегральные схемы близки друг другу, нужно знать, что они выполняют несколько различающиеся функции, т.е. не являются полностью взаимозаменяемыми. Различия определяются прежде всего тем, по каким конкретно уравнениям реализуются отношения F<, F= и F> этих микросхем. Именно последнее будет определять, как выполняются в них другие важные требования, предъявляемые к наращиваемым компараторам, а именно:

• если для четырёх информационных разрядов отдельно взятой микросхемы выполняется отношение А < B или А > В, то её соответствующие выходные сигналы не должны зависеть от сигналов f< , f=

иf> ;

•при равенстве всех информационных входов отдельно взятой микросхемы (А = В) последняя должна транслировать на свои выходы сигналы отношений, выработанные в более младших разрядах;

•микросхема компаратора должна иметь возможность выдавать любое из пяти отношений;

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

•компаратор должен обеспечивать возможность наращивания разрядности сравниваемых чисел по последовательной и параллельной (пирамидальной) схеме;

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

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

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

5.1.1.Структуры на микросхеме 134СП1 (74L85)

Вмикросхеме 134СП1 (74L85) выходные сигналы реализованы по уравнениям (5.9) - (5.11). Представляет интерес выяснить, как зависят выходные сигналы отдельно взятой микросхемы от всех возможных наборов сигналов на расширительных входах при различном отношении между числами, представленными только информационными входами (А < B, A = B, A > B). Используя уравнения (5.9) - (5.11), составим таблицу (табл.5.2).

Таблица 5.2 Таблица истинности для ИС 134СП1 (74L85)

	Входы						Выходы
f<	f=	f>		A < B				A = B				A > B
			F<	F=	F>	F<		F=		F>	F<	F=	F>
0	0	0	1	0	0	0		0		0	0	0	1
0	0	1	1	0	0	0		0		1	0	0	1
0	1	0	1	0	0	0		1		0	0	0	1
0	1	1	1	0	0	0		1		1	0	0	1
1	0	0	1	0	0	1		0		0	0	0	1
1	0	1	1	0	0	1		0		1	0	0	1
1	1	0	1	0	0	1		1		0	0	0	1
1	1	1	1	0	0	1		1		1	0	0	1

134СП1 (74L85)

Из табл.5.2 можно получить следующие выражения:

	F<	при	f<	f=	f> = 0××;
F< =	F≤	при	f<	f=	f> = 1××;
	0	при	f<	f=	f> = ×0×;
F= =	F=	при	f<	f=	f> = ×1×;
	F>	при	f<	f=	f> = ××0;
F> =	F≥	при	f<	f=	f> = ××1.

Из табл.5.2 видно, что выходные сигналы F< и F> при выполнении условий соответственно A < B и A > B никак не зависят от сигналов f< ,

f= и f> , а при А = В любые наборы расширительных входов однознач-

но (идентично) транслируются на выходы микросхемы.

На рис.5.3 показана структура для реализации 16-разрядного компаратора, отражающая идею наращивания, проиллюстрированную на рис.5.1. На рис.5.3 указаны все разряды только для числа А, а разряды числа В располагаются аналогично.

Что подавать на расширительные входы младшей микросхемы зависит от того, какие отношения необходимо получить на выходе. Если требуются отношения F<, F= и F>, то необходимо установить f< = f> = 0 и f= = 1 (это условие равенства фактически отсутствую-

щих еще более младших разрядов). Если требуются отношения F< и F>, то f< = 1, f> = 0, а f= = x, если выход F= не используется, f= = 1, если

выход F= используется, f= = 0, если на выходе необходимо установить значение F= = 0 и т.д. (табл.5.3).

Таблица 5.3

Установление выходных соотношений для ИС 134СП1(74L85)

Отношения,
	требуемые					Входы
	на выходах
F<		F=		F>	f<	f=	f>
F<		F=		F>	0	1	0
		0				0
F≤		F=		F>	1	1	0
		0				0
F<		F=		F≥	0	1	1
		0				0
F≤		F=		F≥	1	1	1
		0				0
			134CП1 (74L85)

Так как в табл.5.3 представлены все 8 наборов сигналов f< , f= и f> , то любые другие комбинации сигналов на выходах F<, F= и F> не

могут быть реализованы. Изменяя наборы входных расширительных сигналов на младшей микросхеме в соответствии с табл.5.3, можно получить и другие комбинации сигналов отношения на выходах. В этом случае сигналы f< , f= и f> рассматриваются как управляющие.