Глава 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

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

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

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

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

55

PDF created with FinePrint pdfFactory Pro trial version http://www.fineprint.com

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

может быть получено как

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

является отрицанием функции «сумма по модулю 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).

56

PDF created with FinePrint pdfFactory Pro trial version http://www.fineprint.com

f< ; f= ; f>

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

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

a3 = = a2

a1 a0

F<

b3

b2 F= b1

b0 F>

f< f= f>

Рис.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< известно, а как оно получено, пока нас не интересует).

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

57

PDF created with FinePrint pdfFactory Pro trial version http://www.fineprint.com

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= - отношение А = В для всей оставшейся части младших разрядов сравниваемых чисел. Выражение для 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< = a3b3 + a3b3 ×a2b2 +

+ a3b3 × a2b2 ×a1b1 + (5.13)

+a3b3 × a2b2 ×a1b1 ×a0b0 +

+a3b3 × a2b2 ×a1b1 ×a0 b0 × f< ,

F> = a3b3 + a3b3 ×a2b2 +

+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>;

58

PDF created with FinePrint pdfFactory Pro trial version http://www.fineprint.com

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

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

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

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

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

Рассмотрим подробнее особенности указанных выше четырёх типов микросхем компараторов и различных структур на их основе. Синтез структур многоразрядных компараторов путем получения соответствующих аналитических выражений применять не будем. Полное аналитическое обоснование структур, выполненных на некоторых типах микросхем, приведено в литературе, например в [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)

134СП1 (74L85)

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

59

PDF created with FinePrint pdfFactory Pro trial version http://www.fineprint.com

Из табл.5.2 видно, что выходные сигналы F< и F> при выполнении условий соответственно A < B и A > B никак не зависят от сигналов f< , f= и f>, а при А = В любые наборы расширительных входов однозначно (идентично) транслируются на выходы микросхемы.

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

Рис.5.3. Первый вариант компаратора для 16-разрядных чисел

Что подавать на расширительные входы младшей микросхемы зависит от того, какие отношения необходимо получить на выходе. Если требуются отношения 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).

60

PDF created with FinePrint pdfFactory Pro trial version http://www.fineprint.com

Таблица 5.3

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

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

Если данная конкретная схема (см. рис.5.3) используется для сравнения 13-пятнадцатиразрядных чисел, то на «свободные» информационные входы ai и bi микросхем необходимо подать любые одинаковые наборы, причём в качестве «свободных» можно использовать как старшие, так и младшие разряды или любые промежуточные. Это правило распространяется и на все другие структуры компараторов. Последние можно получить, если использовать микросхему четырёхразрядного компаратора в режиме преобразователя двух пятиразрядных слов в два одноразрядных слова с сохранением между ними отношений «меньше», «равно», «больше».

Рассмотрим, какие два из трёх выходов F<, F= и F> надо взять в качестве двух одноразрядных слов. Очевидно, что равенство двух одноразрядных слов может быть представлено комбинациями 00 или 11. Так как при отношении А = В устанавливаются выходные сигналы F< = 0, F= = 1 и F> = 0, в качестве двух одноразрядных слов нужно выбрать сигналы F< и F>, в данной ситуации обеспечивающие комбинацию 00. Следовательно, с учётом сказанного выше и пятые информационные разряды (самые младшие из пяти!) должны подаваться на входы f< и f>, причём для сохранения отношений необходимо подавать разряд числа a0 на вход f>, а числа b0 на вход f<. Из табл.5.2 видно, что при А = В идентично транслируются на выходы F< и F> все четыре комбинации входов f< и f> независимо от сигнала на входе f=.

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

Расширительные входы старшей микросхемы можно использовать в качестве управляющих в соответствии с табл.5.3. Выход F< любой микросхемы соединяется с информационным входом b0 следующей (более старшей) микросхемы, а выход F> - с a0, что обеспечивает трансляцию сигналов отношения, выработанных в младших разрядах, на выход. Единственное преимущество данной структуры - более просто развести печатную плату, чем для схемы, представленной на рис.5.3, из-за меньшего числа связей между микросхемами.

Существенным недостатком структур, представленных на рис.5.3 и рис.5.4, является последовательное соединение микросхем, что приводит к возрастанию задержек распространения сигналов. Применяя параллельное (каскадное) соединение микросхем, можно значительно снизить эти задержки.

61

PDF created with FinePrint pdfFactory Pro trial version http://www.fineprint.com