КОМПАРАТОР ДВОИЧНЫХ ЧИСЕЛ

Полезная модель относится к электронике и предназначена для использования в счетных и управляющих устройствах, выполненных на логических элементах 2ИЛИ-НЕ, в частности, из состава серийных микросхем малой степени интеграции.
Известны компараторы двоичных чисел определенной разрядности. См., например, патент США №3251035 НПК 340-146.2, опубликованный 10 мая 1966 г. [1]. Подобные устройства имеют ограниченные возможности по обработке многоразрядных чисел.
Этот недостаток устранен в устройстве, описанном в патенте РФ №2300132 МПК G06F 7/02 и G05B 1/03, опубликованном 27 мая 2007 г. [2]. По своей технической сущности оно наиболее близко заявляемой полезной модели.
A>B
A<B
A=B
Данное устройство содержит входные блоки, выполняющие сравнения пар разрядов чисел одного порядка, блоки объединения результатов частичных сравнений и формирователь сигнала признака равенства чисел. Устройство выполняет функции сравнения двух двоичных чисел А и В произвольной разрядности N: F, F и F, логические выражения которых представляют следующие формулы.
i
i
где a и b - разряды i-го порядка сравниваемых чисел А и В, а взятые в фигурные скобки неравенства представляют логические переменные, принимающие истинные и ложные значения соответственно при выполнении и невыполнении заключенных в скобки неравенств.
N-1
N-1
Устройство последовательно присоединяет результат сравнения очередной пары разрядов чисел следующего по убыванию порядка к результату сравнения фрагментов чисел, содержащих предыдущие разряды. Это снижает быстродействие, так как критическая цепь распространения сигналов от входов a и b старших разрядов чисел до выходов состоит из всех последовательно подключенных функциональных блоков устройства.
Недостатком компаратора двоичных чисел также является сложность его выполнения на микросхемах КМОП и ТТЛ типов и на элементах микросхем малой степени интеграции. В нем используются логические элементы 2ИЛИ и ЗАПРЕТ  которые сложно реализуются в КМОП и ТТЛ схемотехнических базисах, а элементы ЗАПРЕТ представлены не во всех сериях логических микросхем.
Технический результат полезной модели заключается в упрощении устройства за счет уменьшения числа типов используемых логических элементов до одного и в повышении быстродействия за счет уменьшения количества каскадов логических элементов в цепях распространения сигналов от входов до выходов устройства.
i
i
Технический результат достигается тем, что в компараторе двоичных чисел, содержащем блоки сравнения разрядов в количестве, равном разрядности чисел N, и каждый блок сравнения разрядов состоит из первого и второго элементов, первые входы и выходы которых соответственно являются первыми и вторыми входами и выходами блока, первый и второй входы блоков сравнения разрядов подключены к парам входов разрядов a и b первого и второго чисел А и В порядка i=0, 1, … N-1, блоки объединения результатов частичных сравнений, каждый из которых состоит из первого и второго элементов, первые входы которых соответственно являются первым и вторым входами блока, а вторые входы - его третьим и четвертым входами, третьего и четвертого элементов, первые входы которых соответственно соединены с выходами первого и второго элементов, вторые - с четвертым и третьим входами блока, а выходы соответственно являются его первым и вторым выходами, формирователь сигнала признака равенства чисел на логическом элементе 2ИЛИ-НЕ, выход которого является выходом устройства для сигнала равенства сравниваемых чисел - А=В, все элементы устройства являются логическими элементами 2ИЛИ-НЕ, а в каждый входной блок сравнения разрядов дополнительно введен третий логический элемент 2ИЛИ-НЕ, входы которого подключены ко входам блока, а выход соединен со вторыми входами первого и второго элементов, количество блоков объединения результатов частичных сравнений равно N-1, они образуют древовидную цепь, состоящую из нескольких каскадов, число которых K, равно округленному до ближайшего  целого значению логарифма по основанию два от N, то есть  у блоков объединения результатов частичных сравнений, составляющих первый каскад, первые, вторые и третьи, четвертые входы соответственно подключены к первым, вторым выходам блоков сравнения разрядов четных и нечетных номеров, следующих в порядке возрастания от 0 до N-1, если N - четно, или до N-2, если N - нечетно, в каждом следующем каскаде первые, вторые и третьи, четвертые входы блоков объединения результатов частичных сравнений подключены к первым, вторым выходам аналогичных блоков предыдущего каскада в порядке возрастания номеров соответствующих им разрядов сравниваемых чисел, если в предыдущих каскадах отсутствуют связи выходов блока сравнения разрядов и блока объединения результатов частичных сравнений или двух блоков объединения результатов частичных сравнений, первые, вторые выходы этих блоков в порядке возрастания номеров соответствующих разрядов сравниваемых чисел подключены к первому, второму и третьему, четвертому входам последнего по порядку блока объединения частичных результатов сравнения данного каскада, первый и второй выходы блока объединения результатов частичных сравнений последнего К-го каскада соответственно являются выходами устройства для сигналов превышения первого числа вторым - А<В и второго числа первым - А>В, а также подключены ко входам логического элемента 2ИЛИ-НЕ формирователя сигнала признака равенства чисел.
Указанное выполнение устройства позволяет использовать в нем только логические элементы типа 2ИЛИ-НЕ и сократить их количество в критических цепях распространения сигналов от входов до выходов до 2К+3, где
Отличительными признаками полезной модели являются тип и наличие дополнительных элементов, электрические связи элементов и блоков устройства.
Полезная модель поясняется чертежом электрической схемы компаратора двух 7-разрядных двоичных чисел.
i
i
0
0
1
1
1
1
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
2
2
3
3
4
4
5
5
0
0
1
1
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
Компаратор двоичных чисел содержит блоки 1-0, … 1-6 сравнения разрядов в количестве, равном разрядности чисел N=7 и блоки 2-0, … 2-5 объединения результатов частичных сравнений в количестве N-1=6. Каждый блок 1-0, … 1-6 сравнения разрядов состоит из первого, второго и третьего логических элементов 3, 4 и 5 2ИЛИ-НЕ. Первые, вторые входы и выходы элементов 3 и 4 соответственно являются первыми, вторыми входами X, Y и выходами X<Y, X>Y блока, у элемента 5 входы подключены ко входам блока X и Y, а выход соединен со вторыми входами элементов 3 и 4. Первый и второй входы X, Y блоков сравнения разрядов подключены к парам входов a и b разрядов первого и второго чисел А и В в порядке возрастания номеров i=0, 1, … 6. Каждый блок 2-0, … 2-5 объединения результатов частичных сравнений состоит из первого и второго логических элементов 6 и 7 2ИЛИ-НЕ, первые входы которых соответственно являются первым и вторым входами Х и Y блока, а вторые входы - его третьим и четвертым входами Х и Y, третьего и четвертого логических элементов 8 и 9 2ИЛИ-НЕ, первые входы которых соответственно соединены с выходами элементов 6 и 7, вторые - с четвертым и третьим входами Y и X блока, а выходы соответственно являются его первым и вторым выходами ХХ<YY и ХХ>YY. Блоки 2-0, … 2-5 объединения результатов частичных сравнений образуют трехкаскадную древовидную цепь, у блоков 2-0, 2-1 и 2-2, составляющих первый каскад, первые, вторые и третьи, четвертые входы Х, Y и X, Y соответственно подключены к первым, вторым выходам X<Y, X>Y блоков 1-0 и 1-1, 1-2 и 1-3, 1-4 и 1-5 сравнения разрядов четных и нечетных номеров (а, b и a, b (а, b и а, b), (а, b и а, b). Во втором каскаде первые, вторые и третьи, четвертые входы Х, Y и X Y блока 2-3 подключены к первым, вторым выходам ХХ<YY, XX>YY блоков 2-0, 2-1, а входы Х, Y и Х, Y блока 2-4 соответственно подключены к первому, второму выходам блока 2-2 и к первому, второму выходам блока 1-6, так-как при N=7 нечетны количества блоков 1-0, … 1-6 сравнения разрядов и блоков 2-0, … 2-2 объединения результатов частичных сравнений в первом каскаде. В третьем каскаде у блока 2-5 первый, второй и третий, четвертый входы Х, Y и Х, Y соответственно соединены с первыми, вторыми выходами XX<YY, XX>YY блоков 2-3 и 2-4, а его первый и второй выходы соответственно являются выходами устройства для сигналов превышения первого числа вторым - А<В и второго числа первым - А>В, а также подключены ко входам логического элемента 10 2ИЛИ-НЕ формирователя сигнала признака равенства чисел, выход которого является выходом устройства для сигнала равенства сравниваемых чисел - А=В.
Устройство работает следующим образом.
i
i
Сравнение пар разрядов a, и b одного порядка i чисел А и В поясняет следующая таблица.
i
i
Из таблицы видно, что при любой комбинации сигналов a и b только одному из всех признаков соответствует единичный логический сигнал и достаточно формировать только сигналы, идентифицирующие неравенства, по которым можно получить сигнал равенства.
Отвечающая таблице система логических функций имеет вид
ia<b
ia>b
i
i
Сигналы функций F и F системы (1) формируют блоки 1-0, … 1-6 сравнения разрядов на своих первых и вторых выходах X<Y и X>Y, используя сигналы a и b, поступающие на их первые и вторые входы X и Y.
0
0
1
1
Результаты сравнения одноразрядных частей сравниваемых чисел далее идут на входы Х, Y и Х, Y блоков 2-0, … 2-2 объединения результатов частичных сравнений, составляющих первый каскад, которые формируют из них сигналы признаков сравнения трех пар 2-разрядных частей, составленных из разрядов сравниваемых чисел 0-го и 1-го, 2-го и 3-го, 4-го и 5-го порядков.
i+1
i
i+1
i
i+1
i+1
i
i+1
i
Часть первого числа из разрядов aa больше аналогичной части второго - bb, если старший разряд a больше, чем b, а в случае равенства этих разрядов, если первое число имеет  младший разряд a. Аналогичным образом определяется превосходство второго числа из разрядов bb.
Формулы (2) и (3) удается упростить, если ввести в скобки избыточные конъюнкции  и склеить с ними содержащиеся там члены по логическим формулам
i+1 а>b
i+1 а<b
i а>b
i а<b
i+1 а<b
i+1 а>b
i+1 а>b
i+1 а<b
В конечном виде формулы (4), (5) применимы для объединения любых частичных результатов сравнения, если члены F, Fи F, F в них рассматривать как признаки сравнения частей, составленных соответственно из более старших и следующих за ними младших разрядов. Инверсии признаков F и F в них представляют как условие рассмотрения соотношения младших частей одновременно и равенство старших частей, и превосходство одной из них, которое уже вошло в виде признаков F и F, то есть
i a<b
i a>b
0
0
i+1 а<b
i+1 a>b
1
1
1
0
1
0
1
0
1
0
0
0
1
1
Сигналы F и F признаков сравнения частей из младших разрядов поступают на входы Х и Y, a F и F для частей из следующих по старшинству - на входы X и Y. Каждый из блоков 2-0, … 2-5 выполняет функцию , соответствующую признаку ХХ<YY и функцию  для признака XX>YY. С учетом формул (6), применяя логический закон поглощения для конъюнкции -х(у+х)=х, замена условных переменных Х, Y и Х, Y на соответствующие признаки сравнения в выражениях функций блоков объединения результатов частичных сравнений приводит эти выражения к виду, эквивалентному формулам (4) и (5):
1
0
1
0
3
2
3
2
5
4
5
4
6
6
3
2
1
0
3
2
1
0
6
5
4
6
5
4
Во втором каскаде блоки 2-3 и 2-4 из результатов сравнений aa с bb, аа с bb и аа с bb, а с b соответственно формируют признаки сравнения частей из четырех младших и трех старших разрядов: aaaa, bbbb и ааа, bbb. Их затем объединяет блок 2-5 из третьего, в данном случае последнего каскада, выходы которого служат выходами сигналов признаков неравенств А<В и А>В.
Равенство чисел А и В достигается в случае равенства пар составляющих их разрядов одинаковых порядков, но оно же соответствует конъюнкции инверсий признаков неравенств, так как только при А=В будут одновременно ложными оба утверждения о превосходстве А над В и В над А. Сигнал признака А=В, соответствующий конъюнкции , формирует элемент 10 2ИЛИ-НЕ.
Из описания работы устройства должно быть видно, что каждый блок объединения результатов частичных сравнений из двух пар признаков сравнения двух, следующих друг за другом пар частей сравниваемых чисел формирует одну пару признаков для составленных из этих частей фрагментов чисел. На каждом каскаде этих блоков вдвое уменьшается количество сравниваемых частей, из которых можно составить пары, и соответствующих им признаков. Если для одной части пары нет, она передается на ближайший из последующих каскадов, где сможет объединиться с одной оставшейся там без пары частей. Так происходит до полного объединения всех частей.
К
К
К
Максимальное количество N разрядов чисел, признаки которых может объединить древовидная цепь блоков, состоящая из К каскадов, равно 2. А если количество разрядов превысит 2, но останется меньше 2⋅2, понадобится К+1 каскад. Следовательно, количество каскадов К равно степени, в которую следует возвести число 2, чтобы получить ближайшее превышающее N целое число, что выражает формула
K
К-1
K
1
К
Выражение для количества блоков объединения результатов частичных сравнений легко получить для случая равенства разрядности N числу 2, в какой-то целой степени, то есть N=2. Так как в первом каскаде количество блоков равно N/2 и уменьшается вдвое на каждом следующем каскаде, их общее количество будет соответствовать сумме К членов геометрической прогрессии со знаменателем q=0,5. По известному выражению суммы S через q, первый и последний члены прогрессии p=2 и р=1
Это количество останется равным N-1 при любом N потому, что каждое увеличение N на один разряд потребует добавить один блок.
Таким образом, компаратор двух N-разрядных двоичных чисел выполняет свои функции, имея в своем составе 7N-3 логических элемента 2ИЛИ-НЕ, связанных в древовидную цепь, в которой пути распространения сигналов от входов до выходов содержат не более чем  последовательных элементов.