Компаратор двоичных чисел

Изобретение относится к электронике и предназначено для использования в интегральных микросхемах счетных и управляющих устройств на комплементарных полевых транзисторах структуры металл-окисел-полупроводник (КМОП). Техническим результатом является повышение быстродействия. Устройство содержит блоки сравнения разрядов, содержащие инвертор, элемент 2И-НЕ и элемент 2ИЛИ-НЕ, блоки объединения результатов частичных сравнений, образующие древовидную цепь и реализующие функции , , и формирователь сигнала признака равенства чисел, выполненный на элементе 2ИЛИ-НЕ. 2 з.п. ф-лы, 12 ил., 1 табл.

 

Изобретение относится к электронике и предназначено для использования в интегральных микросхемах счетных и управляющих устройств на комплементарных полевых транзисторах структуры металл-окисел-полупроводник (КМОП).

Известны компараторы двоичных чисел произвольной разрядности. См., например, патент РФ №2300132 МПК G06F 7/02 и G05B 1/03, опубликованный 27 мая 2007 г. [1]. Подобные устройства последовательно объединяют результаты сравнения пар разрядов чисел следующих в определенном порядке степеней, что снижает быстродействие.

Этот недостаток устранен в устройстве, описанном в патенте РФ на полезную модель №189024 МПК G06F 7/02, H03K 5/22, G05B 1/03, опубликованном 06 мая 2019 г. [2]. По своей технической сущности оно наиболее близко заявляемому изобретению.

Наиболее близкий аналог содержит блоки сравнения разрядов и блоки объединения результатов частичных сравнений, образующих древовидную цепь, состоящую из нескольких каскадов, число которых К равно округленному до ближайшего большего целого значению логарифма по основанию два от разрядности сравниваемых чисел N, то есть

Выходы блока объединения результатов частичных сравнений последнего каскада являются выходами устройства для сигналов превышения первого числа вторым и второго числа первым, а также подключены ко входам логического элемента 2ИЛИ-НЕ формирователя сигнала признака равенства чисел.

Блоки сравнения разрядов и блоки объединения результатов частичных сравнений тоже выполнены на логических элементах 2ИЛИ-НЕ, которые объединены в двухкаскадные последовательные цепи, что снижает быстродействие блоков и устройства в целом.

Технический результат изобретения, заключающийся в устранении данного недостатка, достигается тем, что в компаратор двоичных чисел, содержащий блоки сравнения разрядов в количестве, равном разрядности чисел N, каждый блок сравнения разрядов состоит из первого элемента и второго, третьего элементов, первые входы которых подключены к выходу первого элемента, а выходы соответственно являются первым, вторым выходами блока, вход первого элемента и второй вход второго элемента соответственно являются первым и вторым входами блока, третий элемент является логическим элементом 2ИЛИ-НЕ, блоки объединения результатов частичных сравнений, каждый из которых имеет с первого по четвертый входы и состоит из первого и второго элементов, выходы которых соответственно являются вторым и первым выходами блока, формирователь сигнала признака равенства чисел на логическом элементе 2ИЛИ-НЕ, выход которого являются выходом устройства для сигнала равенства сравниваемых чисел - А=В, количество блоков объединения результатов частичных сравнений равно N - 1, они образуют древовидную цепь, состоящую из нескольких каскадов, число которых К, равно округленному до ближайшего большего целого значению логарифма по основанию два от N, то есть у блоков объединения результатов частичных сравнений, составляющих первый каскад, первые, вторые и третьи, четвертые входы соответственно подключены к первым, вторым выходам блоков сравнения разрядов четных и нечетных номеров, следующих в порядке возрастания от 0 до N - 1, если N - четно, или до N - 2, если N - нечетно, в каждом следующем каскаде первые, вторые и третьи, четвертые входы блоков объединения результатов частичных сравнений подключены к первым, вторым выходам аналогичных блоков предыдущего каскада в порядке возрастания номеров соответствующих им разрядов сравниваемых чисел, если в предыдущих каскадах отсутствуют связи выходов блока сравнения разрядов и блока объединения результатов частичных сравнений или двух блоков объединения результатов частичных сравнений, первые, вторые выходы этих блоков в порядке возрастания номеров соответствующих разрядов сравниваемых чисел подключены к первому, второму и третьему, четвертому входам последнего по порядку блока объединения результатов частичных сравнений данного каскада, второй выход блока объединения результатов частичных сравнений последнего К-го каскада является выходом устройства для сигнала превышения второго числа первым - А>В и подключен ко второму входу элемента 2ИЛИ-НЕ формирователя сигнала признака равенства чисел, внесены следующие отличия.

Первый и второй элементы каждого блока сравнения разрядов устройства соответственно являются инвертором и логическим элементом 2И-НЕ, второй вход которого соединен со вторым входом логического элемента 2ИЛИ-НЕ.

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

Формирователь сигнала признака равенства чисел дополнительно содержит инвертор, вход которого подключен к первому выходу блока объединения результатов частичных сравнений последнего К-го каскада, а выход - к первому входу элемента 2ИЛИ-НЕ и является выходом устройства для сигнала превышения первого числа вторым - А<В.

Входы каждого блока сравнения разрядов подключены к паре входов разрядов а, и b, сравниваемых чисел А и В соответствующего порядка i=0, 1, … N - 1, причем, если в цепи распространения выходных сигналов данного блока до выходов устройства содержится четное количество последовательно подключенных блоков объединения результатов частичных сравнений, первый и второй входы блока соответственно подключены ко входам a_i и b_i, а если нечетное -, то ко входам b_i и a_i.

Блоки сравнения разрядов имеют два варианта выполнения, в каждом из них блок содержит с первого по пятый МОП-транзисторы обогащенного типа с индуцированными каналами р-типа и с первого по пятый МОП-транзисторы обогащенного типа с индуцированными каналами n-типа, истоки с первого по четвертый р-МОП-транзисторов подключены к шине положительного напряжения питания, а истоки первого и с третьего по пятый n-МОП-транзисторов - к шине нулевого потенциала, затворы первых р- и n-МОП-транзисторов соединены и являются первым входом блока, сток четвертого р-МОП-транзистора соединен с истоком пятого р-МОП-транзистора, а исток второго n-МОП-транзистора - со стоком третьего n-МОП-транзистора, стоки второго, третьего р-МОП- и второго n-МОП-транзисторов соединены с первым выходом блока, стоки пятого р-МОП- и четвертого, пятого n-МОП-транзисторов соединены со вторым выходом блока.

В первом варианте выполнения блока сравнения разрядов затворы второго, четвертого р-МОП- и третьего, четвертого n-МОП-транзисторов соединены и являются вторым входом блока, а затворы третьего, пятого р-МОП- и второго, пятого n-МОП-транзисторов соединены и подключены к стокам первых р- и n-МОП-транзисторов.

Во втором варианте выполнения блока сравнения разрядов затворы второго, четвертого р-МОП- и третьего, четвертого n-МОП-транзисторов соединены и подключены к стокам первых р- и n-МОП-транзисторов, а затворы третьего, пятого р-МОП- и второго, пятого n-МОП-транзисторов соединены и являются вторым входом блока,

Каждый элемент, выполняющий функцию, единичные значения которой соответствуют выражению а нулевые значения - выражению содержит первые, вторые и третьи МОП-транзисторы обогащенного типа с индуцированными каналами р- и n-типов проводимости, затворы которых попарно соединены и соответственно являются входами сигналов X, Y и Z, истоки первых и третьих р- и n-МОП-транзисторов соответственно подключены к шинам положительного напряжения питания и нулевого потенциала, стоки первого р-МОП- и третьего n-МОП-транзисторов соответственно соединены с истоками вторых р- и n-МОП-транзисторов, стоки которых и стоки третьего р-МОП- и первого n-МОП-транзисторов соединены с выходом элемента.

Каждый блок сравнения разрядов обоих вариантов конструктивно выполнен в виде первой и второй смежных продольными сторонами областей МОП-структур р-типа и примыкающих к ним продольными сторонами также смежных первой и второй областей МОП-структур n-типа, поперек первых областей р- и n-МОП-структур проходит первая полоска затворов, соединенная с первым входом блока, поперек всех четырех областей, проходят вторая полоска затворов, соединенная с крайними со стороны первой полоски затворов р- и n-областями истоков-стоков первых областей р- и n-МОП-структур, и третья полоска затворов, соединенная со вторым входом блока, в отделенных первой полоской затворов частях первых областях р- и n-МОП-структур и во вторых областях р- и n-МОП-структур вторая и третья полоски затворов выделяют по три области истоков-стоков соответствующих типов.

В первом варианте выполнения блока сравнения разрядов первые области р- и n-МОП-структур расположены по краям блока, а вторые области р- и n-МОП-структур примыкают друг к другу, р-область истоков-стоков между первой и второй полосками затворов первой области р-МОП-структур и крайние со стороны третьей полоски затворов р-области истоков-стоков обеих областей р-МОП-структур подключены к шине положительного напряжения питания, n-область истоков-стоков между первой и второй полосками затворов первой области n-МОП-структур и крайние со стороны третьей полоски затворов n-области истоков-стоков обеих областей n-МОП-структур подключены к шине нулевого потенциала, р-область истоков-стоков первой области р-МОП-структур между второй и третьей полосками затворов и крайняя со стороны второй полоски затворов n-область истока-стока второй области n-МОП-структур соединены с первым выходом блока, n-область истоков-стоков первой области n-МОП-структур между второй и третьей полосками затворов и крайняя со стороны второй полоски затворов р-область истока-стока второй области р-МОП-структур соединены со вторым выходом блока.

Во втором варианте выполнения блока сравнения разрядов первые области р- и n-МОП-структур примыкают друг к другу, а вторые области р- и n-МОП-структур расположены по краям блока, р-область истоков-стоков между первой и второй полосками затворов первой области р-МОП-структур и крайние р-области истоков-стоков второй области р-МОП-структур подключены к шине положительного напряжения питания, n-область истоков-стоков между первой и второй полосками затворов первой области n-МОП-структур и крайние n-области истоков-стоков второй области n-МОП-структур подключены к шине нулевого потенциала, р-область истоков-стоков второй области р-МОП-структур между второй и третьей полосками затворов и крайняя со стороны третьей полоски затворов n-область истока-стока первой области n-МОП-структур соединены с первым выходом блока, n-область истоков-стоков второй области n-МОП-структур между второй и третьей полосками затворов и крайняя со стороны третьей полоски затворов р-область истока-стока первой области р-МОП-структур соединены со вторым выходом блока.

Количества блоков сравнения разрядов, выполненных по первому и по второму вариантам, различаются не более, чем на один.

Каждый элемент, выполняющий функцию, единичные значения которой соответствуют выражению а нулевые значения - выражению конструктивно выполнен в виде двух смежных продольными сторонами областей МОП-структур р- и n-типов проводимости, пересеченных поперек тремя общими полосками затворов, разделяющими МОП-структуры на области истоков-стоков соответствующих типов проводимости, первая-третья полоски затворов по порядку соединены со входами сигналов X, Y и Z, крайние р- и n-области истоков-стоков соответственно подключены к шинам положительного напряжения питания и нулевого потенциала, а области истоков-стоков р-типа между второй и третьей полосками затворов и n-типа между первой и второй полосками затворов соединены с выходом элемента.

Указанное выполнение компаратора двоичных чисел позволяет сократить число элементов в блоках сравнения разрядов и в блоках объединения результатов частичных сравнений, а за счет этого уменьшить количество последовательно включенных каскадов логических элементов в цепях распространения сигналов от входов устройства до выходов, предлагаемая схемотехническая реализация элементов устройства на комплементарных МОП-транзисторах дает возможность применения определенных конструктивных решений элементов, обеспечивающих высокую плотность упаковки компаратора двоичных чисел в интегральном исполнении и снижение паразитных емкостей.

Отличительными признаками изобретения являются схемотехническое, конструктивное выполнение функциональных узлов устройства и их связи.

Изобретение поясняют чертежи, фиг. 1, 2, 3 и 4 представляют функциональные электрические схемы компараторов двоичных чисел разрядностью 4, 5, 6 и 7 соответственно, на фиг. 5, 6 и 9 изображены принципиальные электрические схемы соответственно блоков сравнения разрядов первого, второго вариантов исполнения и элемента, выполняющего функцию, единичные значения которой соответствуют выражению а нулевые значения - примененного в блоках объединения результатов частичных сравнений, на фиг. 7, 8 и 10 - схемы конструктивного выполнения этих блоков и элемента, фиг. 11 и 12 демонстрируют возможности объединения р- и n-МОП-структур элементов и блоков сравнения разрядов устройства.

Компаратор двоичных чисел содержит блоки 1-0, … 1-6 сравнения разрядов в количестве, равном разрядности чисел N, в приведенных примерах принимающей значения 4, 5, 6 и 7. Блоки 2-0, 2-1, 2-2, 3-0, 3-1 и 4 объединения результатов частичных сравнений, количество которых равно N - 1, образуют древовидную цепь из нескольких каскадов, число которых К равно округленному до ближайшего большего целого значению логарифма по основанию два от N, то есть К=2 при N=4, а при N=5, 6 и 7 К=3.

Каждый блок 1-0, … 1-7 сравнения разрядов состоит из первого элемента 5 - инвертора, второго и третьего элементов 6 и 7 с логическими функциями 2И-НЕ и 2ИЛИ-НЕ соответственно. Вход инвертора 5 является первым входом блока для переменной и. Первые входы элементов 6 и 7 подключены к выходу элемента 5, вторые входы соединены и являются вторым входом блока для переменной v, а выходы являются первым и вторым выходами блока сравнения разрядов, соответствующими логическим функциям и от входных переменных.

Каждый блок объединения результатов частичных сравнений имеет первый, второй и третий, четвертый входы u₀, v₀ и u₁, v₁, он состоит из первого и второго элементов 8 и 9, выполняющих логическую функцию трех переменных X, Y, Z, единичные значения которой соответствуют выражению а нулевые значения - выражению входы переменных Y элементов 8 и 9 соответственно являются первым и вторым входами u₀ и v₀ блока, входы переменных Z и X обоих элементов 8 и 9 соответственно соединены и являются третьим и четвертым входами u₁ и v₁ блока, выходы элементов 8 и 9 соответственно являются вторым и первым выходами блока, выходные сигналы которых соответствуют инверсиям функций u₁⋅u₀+v₁ и u₁⋅v₀+v₁.

В схемах компараторов 4-, 5-, 6- и 7-разрядных двоичных чисел на фиг.1, 2, 3 и 4 у блоков 2-0, 2-1 и 2-2 объединения результатов частичных сравнений, составляющих первые каскады, первые и вторые входы u₀ и v₀ соответственно подключены к первым и вторым выходам блоков 1-0, 1-2, 1-4, 1-6, сравнивающих разряды а₀ и b₀, а₂ и b₂, а₄ и b₄, а₆ и b₆ с четными номерами, а третьи и четвертые входы u₁ и v₁ - к первым и вторым выходам блоков 1-1, 1-3, 1-5, сравнивающих разряды a₁ и b₁, а₃ и b₃, а₅ и b₅ с нечетными номерами.

Во вторых каскадах первые и вторые входы u₀ и v₀ блоков 3-0 и 3-1 объединения результатов частичных сравнений подключены к первым и вторым выходам блоков 2-0 и 2-2 первого каскада, третьи и четвертые входы u₁ и v₁ у блока 3-0 в каждой схеме соединены с первым и вторым выходами блока 2-1, а у блока 3-1 на фиг. 4 - с первым и вторым выходами блока 1-6, который не имеет пары и. поэтому, не связан с блоками объединения результатов частичных сравнений первого каскада. В аналогичном положении оказался блок 1-4 на фиг. 2, пару с его выходами смогли образовать только выходы блока 3-0, составляющего второй каскад объединения результатов частичных сравнений.

Последние каскады объединения результатов частичных сравнений в схеме на фиг. 1 образует блок 3-0, а на фиг.2, 3 и 4 -блоки 4. Вторые выходы блока 3-0 на фиг.1 и блоков 4 на фиг.2, 3 и 4 являются выходами устройств для сигналов превышения второго числа первым - А>В.

Формирователь сигнала признака равенства чисел состоит из инвертора 10 и логического элемента 11 с функцией 2ИЛИ-НЕ. Вход инвертора 10 подключен к первым выходу блока 3-0 в схеме на фиг. 1 или блока 4 в схемах на фиг. 2, 3 и 4. Выход инвертора 10 соединен с первым входом элемента 11 и является выходом каждого устройства для сигнала превышения первого числа вторым - А<В. Второй вход элемента 11 подключен ко второму выходу блока 3-0 или 4, а выход являются выходом устройства для сигнала равенства сравниваемых чисел - А=В во всех приведенных примерах.

Входы каждого блока 1-0, … 1-6 сравнения разрядов подключены к паре входов разрядов a_i и b_i первого и второго чисел А и В соответствующего порядка i=0, 1, … 6, причем, если в цепи распространения выходных сигналов данного блока 1-0, … 1-6 до выходов устройства содержится четное количество последовательно подключенных блоков 2-0, 2-1, 2-2, 3-0, 3-1, 4 объединения результатов частичных сравнений, первый и второй входы этого блока 1-0, … 1-6 сравнения разрядов соответственно подключены ко входам a_i и b_i, а если нечетное -, то ко входам b_i и a_i.

Так, в схеме фиг.1 выходные сигналы всех блоков 1-0, … 1-3 проходят до выходов по цепям из двух последовательно включенных блоков 2-0 - 3-0 или 2-1 - 3-0 и у всех блоков 1-0, … 1-3 первые и вторые входы u и v соответственно подключены ко входам разрядов а₀ и b₀, a₁ и b₁, а₂ и b₂, а₃ и b₃ первого и второго чисел А и В.

В схемах фиг.2 и 3 и 4 выходные сигналы блоков 1-0, … 1-3 проходят по три каскада блоков 2-0 - 3-0 - 4 или 2-1 - 3-0 - 4, входы u и v блоков 1-0, … 1-3 соответственно подключены ко входам разрядов b₀ и а₀, b₁ и а₁, b₂ и а₂, b₃ и а₃ второго и первого чисел В и А.

У блока 1-4 на фиг.2 входы u и v соответственно подключены ко входам разрядов b₄ и а₄, так как выходные сигналя блока 1-4 непосредственно поступают на входы u₁ и v₁ блока 4, составляющего последний каскад объединения результатов частичных сравнений.

Аналогично, ко входам b₄ и а₄, b₅ и а₅ подключены входы u и v блоков 1-4,1-5 на фиг. 4, выходные сигналы которых проходят последовательные цепи из трех каскадов блоков 2-2 - 3-1 - 4.

Блоки 1-4, 1-5 на фиг. 3 и 1-6 на фиг. 4 связаны с выходами устройства цепями из четного числа каскадов блоков объединения результатов частичных сравнений. На фиг. 3 они состоят из блоков 2-2 и 4, а на фиг. 4 - из блоков 3-1 и 4. Поэтому, входы u и v блоков 1-4, 1-5 на фиг. 3 и блока 1-6 на фиг. 4 соответственно подключены ко входам разрядов а₄ и b₄, а₅ и b₅, а₆ и b₆ первого и второго чисел А и В.

Устройство работает следующим образом.

Сравнение пар разрядов a_i и b_i одного порядка i чисел А и В производится согласно следующей таблице истинности.

Взаимосвязи соответствующих признакам сравнения логических выражений позволяет формировать только более простые сигналы, идентифицирующие неравенства разрядов, по которым можно получить сигнал равенства. Достаточно одной пары сигналов за исключением связанных отношением взаимной инверсии двух пар, соответствующих выражениям из колонок 3 и 4, 5 и 6.

Блоки 1-0, … 1-6 в зависимости от подключения входов u и v формируют на своих первых и вторых выходах и сигналы, соответствующие парам признаков из таблицы 1, занимающих колонки 3 и 6 или 4 и 5.

Результаты сравнения одноразрядных частей сравниваемых чисел далее идут на входы u₀, v₀ и u₁, v₁ блоков 2-0, … 2-2 объединения результатов частичных сравнений, составляющих первый каскад, которые формируют из них результаты сравнения частей, содержащих по два разряда сравниваемых чисел 0-го и 1-го, 2-го и 3-го, 4-го и 5-го порядков.

Часть первого числа из двух разрядов a_i+1a_i больше аналогичной части второго - b_i+1b_i, если старший разряд a_i+1 больше, чем b_i+1, а в случае равенства этих разрядов, если младший разряд a_i первого числа превышает младший разряд b_i второго. Аналогичным образом определяется превосходство части второго числа из разрядов b_i+1b_i.

Части чисел А и В, состоящие из разрядов последовательно убывающих порядков от i до j, в последующем тексте и на схемах обозначены соответственно как A_i-j и B_i-j, а логические выражения признаков их сравнения - как F(A_i-i>B_i-j), F(A_i-i<B_i-j), F(A_i-i>B_i-j), F(A_i-i<B_i-j). Аналогичным образом обозначены выражения признаков сравнения разрядов: F(a_i>b_i), F(a_i<b_i), F(a_i≥b_i), F(a_i≤b_i).

Формулы (1) и (2) удается упростить, если ввести в скобки избыточные конъюнкции , и склеить с ними содержащиеся там члены по логическим формулам

Инвертирование формул (3) и (4) позволяет получить простые логические выражения для остальных признаков неравенства.

Действия, соответствующие формулам (3) - (6), выполняют блоки 2-0, 2-1 и 2-2 объединения результатов частичных сравнений.

Содержащиеся в каждом блоке 2-0 и 2-1 в схеме фиг. 1 и в блоке 2-2 на фиг. 3 элементы 8 и 9 с функцией принимают на входы X, Y, Z сигналы признаков a_i+1>b_i+1, a_i≥b_i, a_i+1≥b_i+1 и a_i+1>b_i+1, a_i>b_i, a_i+1≥b_i+1, i=0, 2, 4, из которых элемент 8 формирует сигнал

который очевидно отвечает формуле (4), а элемент 9 - сигнал

отвечаующий формуле (5).

Элементы 8 и 9 с функцией в блоках 2-0 и 2-1 в схемах Фиг. 2, 3 и 4 и в блоке 2-2 на фиг. 4 имеют на входах X, Y, Z сигналы признаков a_i+1<b_i+1, a_i≤b_i, a_i+1≤b_i+1 и a_i+1<b_i+1, a_i<b_i, a_i+1≤b_i+1, i=0, 2, 4. Их выходные сигналы

и

соответствуют формулам (3) и (6).

Формулы (3) - (6) применимы для объединения результатов сравнения любых частей, если признаки сравнения разрядов, заменить в них признаками сравнения частей из групп разрядов.

В общем виде при i1>j1, i2=j1 - 1>j2 формулы будут выглядеть так:

Объединение результатов сравнения двухразрядных частей по этим формулам выполняют блоки 3-0 и 3-1.

В схеме Фиг. 1 блок 3-0 формирует сигналы по формулам

а в схемах Фиг. 2,3,4- по формулам

Блок 3-1 в схеме фиг. 4 объединяет результаты сравнения частей разной разрядности, он работает по формулам

На Фиг. 1 блок 3-0 составляет последний каскад объединения результатов частичных сравнений, сигнал с его первого выхода, соответствующий формуле (7), через инвертор 10 поступает на выход устройства для сигналов превышения первого числа вторым - А<В, а второй выход в соответствии с формулой (8) непосредственно является выходом сигналов А>В.

В остальных примерах выполнения компаратора двоичных чисел на Фиг. 2, 3 и 4 последний каскад объединения результатов частичных сравнений составляют блоки 4, они формируют конечные выражения признаков сравнения чисел по следующим формулам.

На Фиг. 2

На фиг. 3

На фиг.4

Сигналы признака А=В в данном устройстве формирует элемент 11 2ИЛИ-НЕ как конъюнкцию инверсий сигналов признаков превосходства А над В и В над А, так как оба этих признака могут быть одновременной ложными только в случае равенства чисел А и В.

Из описания работы устройства должно быть видно, что каждый блок объединения результатов частичных сравнений из двух пар признаков сравнения двух, следующих друг за другом пар частей сравниваемых чисел формирует одну пару признаков для составленных из этих частей фрагментов чисел. На каждом каскаде этих блоков вдвое уменьшается количество сравниваемых частей, из которых можно составить пары, и соответствующих им признаков сравнения. Если для одной части пары нет, она передается на ближайший из последующих каскадов, где сможет объединиться с одной оставшейся там без пары частью. Так происходит до полного объединения всех частей.

Максимальное количество N разрядов чисел, признаки которых может объединить древовидная цепь блоков, состоящая из К каскадов, равно 2^К. А если количество разрядов превысит 2^К, но останется меньше 2⋅2^К, понадобится К+1 каскад. Следовательно, количество каскадов К равно степени, в которую следует возвести число 2, чтобы получить ближайшее превышающее N или равное ему целое число, что выражает формула

Выражение для количества блоков объединения результатов частичных сравнений легко получить для случая равенства разрядности N числу 2, в какой-то целой степени, то есть N=2^К, так как в первом каскаде количество блоков равно N / 2 и уменьшается вдвое на каждом следующем каскаде, их общее количество будет соответствовать сумме S_K из К членов геометрической прогрессии со знаменателем q=0,5. Подставив в известную формулу данное значение q, значения первого и последнего членов прогрессии p₁=2^К-1 и р_К=1, получим следующее выражение для суммы S_K.

Количество блоков объединения результатов частичных сравнений останется равным N - 1 при любом N потому, что каждое увеличение N на один разряд потребует добавить один блок.

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

Блоки 1-0, … 1-6 сравнения разрядов имеют два варианта схемотехнического и конструктивного выполнения, представленные на фиг. 5, 6 и 7, 8 соответственно. В каждом варианте блок содержит с первого по пятый МОП-транзисторы 12 - 16 на фиг. 5 и 22 - 26 на фиг.6 обогащенного типа с индуцированными каналами р-типа и с первого по пятый МОП-транзисторы соответственно 17-21 и 27 - 31 обогащенного типа с индуцированными каналами n-типа. Истоки р-МОП-транзисторов 12 - 15 и 22 - 25 подключены к шине +U_П положительного напряжения питания, а истоки n-МОП-транзисторов 17, 19-21 и 27, 29 - 31 - к шине нулевого потенциала. Затворы пар МОП-транзисторов 12 и 17, 22 и 27 соединены и являются первыми входоми и блоков обоих вариантов, стоки р-МОП-транзисторов 15 и 25 соответственно соединены с истоками р-МОП-транзисторов 16 и 26, а истоки n-МОП-транзисторов 18 и 28 - со стоками n-МОП-транзисторов 19 и 29. Стоки МОП-транзисторов 13, 14, 18 и 23, 24, 28 соответственно соединены с первыми выходами блоков первого и второго вариантов выполнения, а стоки МОП-транзисторов 16, 20, 21 и 26, 30, 31 - с их вторыми выходами

В первом варианте выполнения блока сравнения разрядов, см фиг. 5 затворы МОП-транзисторов 13, 15, 19 и 20 соединены и являются вторым входом v блока, а затворы МОП-транзисторов 14, 16, 18 и 21 подключены к стокам МОП-транзисторов 12 и 17.

Во втором варианте выполнения блока сравнения разрядов, см. фиг. 6 затворы МОП-транзисторов 23, 25, 29 и 30 подключены к стокам МОП-транзисторов 22 и 27, а затворы МОП-транзисторов 24, 26, 28 и 31 соединены и являются вторым входом v блока.

КМОП-элементы формируют единицы выполняемых логических функций посредством подключения выходов к шине положительного напряжения питания с помощью каналов МОП-транзисторов р-типа, возникающих у них при наличии на затворах напряжения низкого уровня, и нули подключением выходов к шине нулевого потенциала через открытые каналы n-МОП-транзисторов в присутствии на их затворах высокого уровня напряжения. Функции проводимости последовательных и параллельных соединений МОП-транзисторов соответствуют конъюнкциям и дизъюнкциям функций проводимости транзисторов, которые для р-канальных выражаются инверсией, а для n-канальных - повторением логических уровней на затворах.

В первом варианте выполнения блока сравнения разрядов МОП-транзисторы 12 и 17 образуют инвертор 5, МОП-транзисторы 13, 14 и 18, 19 - элемент 6 2И-НЕ, а МОП-транзисторы 15, 16 и 20, 21 -элемент 7 2ИЛИ-НЕ.

Во втором варианте выполнения блока сравнения разрядов инвертор 5 составляют МОП-транзисторы 22 и 27, элемент 6 2И-НЕ -МОП-транзисторы 23, 24 и 28, 29, а элемент 7 2ИЛИ-НЕ - МОП-транзисторы 25, 26 и 30, 31.

В конструкции первого варианта выполнения блока сравнения разрядов (Фиг. 7) первые области 38 и 39 р- и n-МОП-структур расположены по краям блока, а вторые области 40 и 41 - примыкают друг к другу. Р-область истоков-стоков между первой и второй полосками 42 и 43 затворов в области 38 р-МОП-структур и крайние со стороны третьей полоски 44 затворов р-области и стоков-стоков областей 38 и 40 р-МОП-структур подключены к шине +U_П положительного напряжения питания. N-область истоков-стоков между полосками 42 и 43 затворов в области 39 n-МОП-структур и крайние со стороны полоски 44 затворов n-области истоков-стоков в областях 39 и 41 n-МОП-структур подключены к шине нулевого потенциала. Р-область истоков-стоков в области 38 р-МОП-структур между полосками 43, 44 затворов и крайняя со стороны полоски 43 затворов n-область истока-стока в области 41 n-МОП-структур соединены с первым выходом блока. N-область истоков-стоков в первой области 39 n-МОП-структур между полосками 43, 44 затворов и крайняя со стороны полоски 43 затворов р-область истока-стока в области 40 р-МОП-структур соединены со вторым выходом u v блока.

В местах пересечений полосками 42, 43 и 44 затворов областей 38 и 39 р- и n-МОП-структур соответственно расположены области каналов р-МОП-транзисторов 12, 14, 13 и n-МОП-транзисторов 17, 21, 20, а в местах пересечений полосками 43 и 44 затворов областей 40 и 41 р- и n-МОП структур 40 и 41 - области каналов р-МОП-транзисторов 16, 15 и n-МОП-транзисторов 18, 19.

В конструкции второго варианта выполнения блока сравнения разрядов (Фиг. 8) первые области 45 и 46 р- и n-МОП-структур примыкают друг к другу, а вторые области 47 и 48 р- и n-МОП-структур расположены по краям блока. Р-область истоков-стоков между первой и второй полосками 49 и 50 затворов в области 45 р-МОП-структур и крайние р-области истоков-стоков в области 47 р-МОП-структур подключены к шине +U_П положительного напряжения питания. N-область истоков-стоков между полосками 49 и 50 затворов в области 46 n-МОП-структур и крайние n-области истоков-стоков в области 48 n-МОП-структур подключены к шине нулевого потенциала. Р-область истоков-стоков в области 47 р-МОП-структур между полосками 50, 51 затворов и крайняя со стороны полоски 51 затворов n-область истока- стока в области 46 n-МОП-структур соединены с первым выходом блока. N-область истоков-стоков в области 48 n-МОП-структур между полосками 50, 51 затворов и крайняя со стороны полоски 51 затворов р-область истока-стока в области 45 р-МОП-структур соединены со вторым выходом блока.

Пересечения полосками 49,50 и 51 затворов областей 45 и 46 р- и n-МОП-структур соответственно образуют области каналов р-МОП-транзисторов 22, 25, 26 и n-МОП-транзисторов 27, 29, 28, а пересечения полосками 50 и 51 затворов областей 47 и 48 р- и n-МОП-структур 45 и 46 - области каналов р-МОП-транзисторов 23, 24 и n-МОП-транзисторов 30, 31.

Описанное конструктивное выполнение блоков сравнения разрядов в двух вариантах дает возможность повысить плотность их размещения на поверхности кристалла при интегральном исполнении устройства. На фиг. 12 показан фрагмент компоновки массива таких блоков, которая предусматривает зеркально-симметричное расположение пар блоков обоих вариантов выполнения, позволяющее минимизировать шаг размещения МОП-транзисторных структур за счет двухрядной расстановки областей МОП-структур, уменьшения площади изолирующих областей и совмещения подключенных к шинам питания областей истоков соседних МОП-структур.

Очевидно, что количества блоков сравнения разрядов, выполненных по первому и по второму вариантам, должны быть равны при четной разрядности N сравниваемых чисел или различаться на один при нечетном N.

Каждый элемент 8 и 9, выполняющий функцию, единичные значения которой соответствуют выражению а нулевые значения - выражению см. фиг. 9 содержит первые, вторые, третьи МОП-транзисторы 32, 33, 34 и 35, 36, 37 обогащенного типа с индуцированными каналами р- и n-типов проводимости, затворы которых попарно соединены и соответственно являются входами сигналов X, Y и Z. Истоки р- и n-МОП-транзисторов 32, 34 и 35, 37 соответственно подключены к шине +U_П положительного напряжения питания и к шине нулевого потенциала. Стоки р- и n-МОП-транзисторов 32 и 37 соответственно соединены с истоками р- и n-МОП-транзисторов 33 и 36, стоки которых и стоки МОП-транзисторов 34 и 35 соединены с выходом элемента.

Применение элементов с неполностью определенной функцией оправдано тем, что у каждого такого элемента в данном устройстве логические функции сигналов, поступающих на входы X и Z связаны отношением включения F_X ⊃ F_Z, то есть F_X включает F_Z, так как все единичные значения функции F_Z на определенном наборе значений переменных соответствуют единичным значениям функции F_X, которая имеем еще и другие единичные значения.

Так, у элементов 8 и 9 во всех блоках объединения результатов частичных сравнений на входы X и Z соответственно поступают сигнал признака исключительного превосходства части одного числа над аналогичной частью другого, например, А_1-0>В_1-0 и сигнал признака того же превосходства, дополненного признаком равенства этих же частей, - А_1-0≥В_1-0. Очевидно, что признак вида А_1-0>В_1-0 выполняется только при выполнении признака A_1-0≥В_1-0, все случаи невыполнения которого, совпадают со случаями невыполнения признака А_1-0>B_1-0, а, еще, признак А_1-0≥В_1-0 не может быть ложным, когда истинен признак А_1-0>В_1-0. Это выражается следующими логическими формулами.

Выраженная формулами (10) и (11) логическая взаимосвязь сигналов X и Z позволила упростить связи МОП-транзисторов в схеме элементов 8 и 9, во время синтеза которой были проделаны следующие преобразования формул.

Крайние логические выражения слева и справа в формуле (13) описывают связи соответственно n- и р-МОП-транзисторов в элементах 8 и 9, а формула (12) доказывает то, что управляемые разными сигналами р- и n-МОП-транзисторы, непосредственно подключенные между выходом элемента и шинами питания не могут иметь открытые каналы одновременно. Высокий уровень сигнала X, открывающий канал n-МОП-транзистора 35, никогда не сочетается с низким открывающим р-МОП-транзистор 34 уровнем сигнала Z.

Каждый элемент, выполняющий функцию, единичные значения которой соответствуют выражению а нулевые значения - выражению конструктивно выполнен (Фиг. 10) в виде двух смежных продольными сторонами областей 52 и 53 МОП-структур р- и n-типов проводимости, пересеченных поперек тремя общими полосками 54, 55 и 56 затворов, разделяющими области 52 и 53 на области истоков-стоков соответствующих типов проводимости. Полоски 54, 55, 56 затворов по порядку соединены со входами сигналов X, Y, Z. Крайние р- и n-области истоков-стоков соответственно подключены к шине +U_П положительного напряжения питания и к шине нулевого потенциала, а области истоков-стоков р-типа между полосками 55, 56 затворов и n-типа между полосками 54, 55 затворов соединены с выходом элемента.

Пересечения полосками 54,55, 56 затворов областей 52 и 53 р- и n-МОП-структур соответственно образуют области каналов р-МОП-транзисторов 32, 33, 34 и n-МОП-транзисторов 35, 36, 37. Упрощенная схема элементов 8 и 9 позволила выполнить связи стоков и истоков их р- и n-МОП-транзисторов 32, 33 и 37, 36 простым совмещением, не требующим контактов и проводников. Расположение подключенных к шинам питания истоков МОП-транзисторов 32, 34 и 35, 37 по краям позволяет совмещать их у соседних элементов в общей конструкции устройства, как показано на фиг. 11.

Таким образом, компаратор двух N-разрядных двоичных чисел выполняет свои функции, имея в своем составе КМОП логические элементы, связанные в древовидную цепь, пути распространения сигналов от входов до выходов которой содержат не более последовательных элементов. Устройство формирует сигналы трех признаков сравнения чисел А и В по логическим формулам:

Предлагаемое схемотехническое и конструктивное выполнение элементов устройства позволит повысить плотность его упаковки в интегральном исполнении.

1. Компаратор двоичных чисел, содержащий блоки сравнения разрядов в количестве, равном разрядности чисел N, каждый блок сравнения разрядов состоит из первого элемента и второго, третьего элементов, первые входы которых подключены к выходу первого элемента, а выходы соответственно являются первым, вторым выходами блока, вход первого элемента и второй вход второго элемента соответственно являются первым и вторым входами блока, третий элемент является логическим элементом 2ИЛИ-НЕ, блоки объединения результатов частичных сравнений, каждый из которых имеет с первого по четвертый входы и состоит из первого и второго элементов, выходы которых соответственно являются вторым и первым выходами блока, формирователь сигнала признака равенства чисел на логическом элементе 2ИЛИ-НЕ, выход которого является выходом устройства для сигнала равенства сравниваемых чисел - А=В, количество блоков объединения результатов частичных сравнений равно N - 1, они образуют древовидную цепь, состоящую из нескольких каскадов, число которых К равно округленному до ближайшего большего целого значению логарифма по основанию два от N, то есть , у блоков объединения результатов частичных сравнений, составляющих первый каскад, первые, вторые и третьи, четвертые входы соответственно подключены к первым, вторым выходам блоков сравнения разрядов четных и нечетных номеров, следующих в порядке возрастания от 0 до N - 1, если N - четно, или до N - 2, если N - нечетно, в каждом следующем каскаде первые, вторые и третьи, четвертые входы блоков объединения результатов частичных сравнений подключены к первым, вторым выходам аналогичных блоков предыдущего каскада в порядке возрастания номеров соответствующих им разрядов сравниваемых чисел, если в предыдущих каскадах отсутствуют связи выходов блока сравнения разрядов и блока объединения результатов частичных сравнений или двух блоков объединения результатов частичных сравнений, первые, вторые выходы этих блоков в порядке возрастания номеров соответствующих разрядов сравниваемых чисел подключены к первому, второму и третьему, четвертому входам последнего по порядку блока объединения результатов частичных сравнений данного каскада, второй выход блока объединения результатов частичных сравнений последнего К-го каскада является выходом устройства для сигнала превышения второго числа первым - А>В и подключен ко второму входу элемента 2ИЛИ-НЕ формирователя сигнала признака равенства чисел, отличающийся тем, что первый и второй элементы каждого блока сравнения разрядов соответственно являются инвертором и логическим элементом 2И-НЕ, второй вход которого соединен со вторым входом элемента 2ИЛИ-НЕ, в каждом блоке объединения результатов частичных сравнений оба элемента выполняют логическую функцию трех переменных X, Y, Z, единичные значения которой соответствуют выражению , а нулевые значения - , входы переменных Y первого и второго элементов соответственно являются первым и вторым входами блока, входы переменных Z и X этих элементов соответственно соединены и являются третьим и четвертым входами блока, формирователь сигнала признака равенства чисел дополнительно содержит инвертор, вход которого подключен к первому выходу блока объединения результатов частичных сравнений последнего К-го каскада, а выход - к первому входу элемента 2ИЛИ-НЕ и является выходом устройства для сигнала превышения первого числа вторым - А<В, входы каждого блока сравнения разрядов подключены к паре входов разрядов a_i и b_i сравниваемых чисел А и В соответствующего порядка i=0, 1, … N - 1, причем, если в цепи распространения выходных сигналов данного блока до выходов устройства содержится четное количество последовательно подключенных блоков объединения результатов частичных сравнений, первый и второй входы блока соответственно подключены к входам a_i и b_i, а если нечетное -, то ко входам b_i и a_i.

2. Компаратор двоичных чисел по п. 1, отличающийся тем, что блоки сравнения разрядов имеют два варианта выполнения, в каждом из них блок содержит с первого по пятый МОП-транзисторы обогащенного типа с индуцированными каналами р-типа и с первого по пятый МОП-транзисторы обогащенного типа с индуцированными каналами n-типа, истоки с первого по четвертый р-МОП-транзисторов подключены к шине положительного напряжения питания, а истоки первого и с третьего по пятый n-МОП-транзисторов - к шине нулевого потенциала, затворы первых р- и n-МОП-транзисторов соединены и являются первым входом блока, сток четвертого р-МОП-транзистора соединен с истоком пятого р-МОП-транзистора, а исток второго n-МОП-транзистора - со стоком третьего n-МОП-транзистора, стоки второго, третьего р-МОП- и второго n-МОП-транзисторов соединены с первым выходом блока, стоки пятого р-МОП- и четвертого, пятого n-МОП-транзисторов соединены со вторым выходом блока, в первом варианте выполнения блока затворы второго, четвертого р-МОП- и третьего, четвертого n-МОП-транзисторов соединены и являются вторым входом блока, а затворы третьего, пятого р-МОП- и второго, пятого n-МОП-транзисторов соединены и подключены к стокам первых р- и n-МОП-транзисторов, во втором варианте выполнения блока затворы второго, четвертого р-МОП- и третьего, четвертого n-МОП-транзисторов соединены и подключены к стокам первых р- и n-МОП-транзисторов, а затворы третьего, пятого р-МОП- и второго, пятого n-МОП-транзисторов соединены и являются вторым входом блока, каждый элемент, выполняющий функцию, единичные значения которой соответствуют выражению , а нулевые значения - выражению , содержит первые, вторые и третьи МОП-транзисторы обогащенного типа с индуцированными каналами р- и n-типов проводимости, затворы которых попарно соединены и соответственно являются входами сигналов X, Y и Z, истоки первых и третьих р- и n-МОП-транзисторов соответственно подключены к шинам положительного напряжения питания и нулевого потенциала, стоки первого р-МОП- и третьего n-МОП-транзисторов соответственно соединены с истоками вторых р- и n-МОП-транзисторов, стоки которых и стоки третьего р-МОП- и первого n-МОП-транзисторов соединены с выходом элемента.

3. Компаратор двоичных чисел по п. 2, отличающийся тем, что каждый блок сравнения разрядов обоих вариантов конструктивно выполнен в виде первой и второй смежных продольными сторонами областей МОП-структур р-типа и примыкающих к ним продольными сторонами также смежных первой и второй областей МОП-структур n-типа, поперек первых областей р- и n-МОП-структур проходит первая полоска затворов, соединенная с первым входом блока, поперек всех четырех областей проходят вторая полоска затворов, соединенная с крайними со стороны первой полоски затворов р- и n-областями истоков-стоков первых областей р- и n-МОП-структур, и третья полоска затворов, соединенная со вторым входом блока, в отделенных первой полоской затворов частях первых областях р- и n-МОП-структур и во вторых областях р- и n-МОП-структур вторая и третья полоски затворов выделяют по три области истоков-стоков соответствующих типов, в первом варианте выполнения блока сравнения разрядов первые области р- и n-МОП-структур расположены по краям блока, а вторые области р- и n-МОП-структур примыкают друг к другу, р-область истоков-стоков между первой и второй полосками затворов первой области р-МОП-структур и крайние со стороны третьей полоски затворов р-области истоков-стоков обеих областей р-МОП-структур подключены к шине положительного напряжения питания, n-область истоков-стоков между первой и второй полосками затворов первой области n-МОП-структур и крайние со стороны третьей полоски затворов n-области истоков-стоков обеих областей n-МОП-структур подключены к шине нулевого потенциала, р-область истоков-стоков первой области р-МОП-структур между второй и третьей полосками затворов и крайняя со стороны второй полоски затворов n-область истока-стока второй области n-МОП-структур соединены с первым выходом блока, n-область истоков-стоков первой области n-МОП-структур между второй и третьей полосками затворов и крайняя со стороны второй полоски затворов р-область истока-стока второй области р-МОП-структур соединены со вторым выходом блока, во втором варианте выполнения блока сравнения разрядов первые области р- и n-МОП-структур примыкают друг к другу, а вторые области р- и n-МОП-структур расположены по краям блока, р-область истоков-стоков между первой и второй полосками затворов первой области р-МОП-структур и крайние р-области истоков-стоков второй области р-МОП-структур подключены к шине положительного напряжения питания, n-область истоков-стоков между первой и второй полосками затворов первой области n-МОП-структур и крайние n-области истоков-стоков второй области n-МОП-структур подключены к шине нулевого потенциала, р-область истоков-стоков второй области р-МОП-структур между второй и третьей полосками затворов и крайняя со стороны третьей полоски затворов n-область истока-стока первой области n-МОП-структур соединены с первым выходом блока, n-область истоков-стоков второй области n-МОП-структур между второй и третьей полосками затворов и крайняя со стороны третьей полоски затворов р-область истока-стока первой области р-МОП-структур соединены со вторым выходом блока, количества блоков сравнения разрядов, выполненных по первому и по второму вариантам, различаются не более чем на один, каждый элемент, выполняющий функцию, единичные значения которой соответствуют выражению , а нулевые значения - выражению , конструктивно выполнен в виде двух смежных продольными сторонами областей МОП-структур р- и n-типов проводимости, пересеченных поперек тремя общими полосками затворов, разделяющими МОП-структуры на области истоков-стоков соответствующих типов проводимости, первая-третья полоски затворов по порядку соединены со входами сигналов X, Y и Z, крайние р- и n-области и стоков-стоков соответственно подключены к шинам положительного напряжения питания и нулевого потенциала, а области истоков-стоков р-типа между второй и третьей полосками затворов и n-типа между первой и второй полосками затворов соединены с выходом элемента.