СУММАТОР КОДОВ "1 ИЗ N" Российский патент 1999 года по МПК G06F7/50 

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

Известен параллельный сумматор двоичных кодов, содержащий N одноразрядных полных сумматоров (N -количество разрядов в каждом суммируемом коде), при этом первый вход, второй вход и выход суммы i-го одноразрядного полного сумматора (i = 1, 2,..., N) подключен соответственно к входу разряда i-1 первого кода, к входу аналогичного разряда второго кода и к выходу разряда i-1 параллельного сумматора, вход переноса первого одоразрядного полного сумматора и выход переноса N-го одноразрядного полного сумматора подключены соответственно к входу сигнала 0 и к выходу разряда N параллельного сумматора, вход переноса i-го, кроме первого, одноразрядного полного сумматора соединен с выходом переноса (i-1)-го одноразрядного полного сумматора (Пухальский Г. И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах. - М.: Радио и связь, 1990, рис. 3.45, с. 133).

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

Недостатками параллельного сумматора двоичных кодов в случае использования его для сложения кодов "1 из N" являются ограниченные функциональные возможности и большие затраты оборудования.

Первый недостаток определяется тем, что параллельный сумматор двоичных кодов выполняет сложение только совпадающих кодов "1 из N", так как в этих кодах число p = 0, 1,..., N - 1 представляется единицей в разряде p и нулями в остальных разрядах (Янсен Й. Курс цифровой электроники. Том 1. Основы цифровой электроники. М.: Мир, 1987, стр. 150). При этом выход разряда i параллельного сумматора двоичных кодов является выходом числа 2 (i-1) в коде "1 из N", а выходы нечетных чисел отсутствуют.

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

Наиболее близким по технической сущности к предлагаемому изобретению является сумматор уплотненных кодов по авт. свид. СССР N 798830, кл. G 06 F 7/50, 1978 г., фиг. 5, содержащий N групп элементов И, 2N - 1 элементов ИЛИ, N элементов И в каждой группе элементов И, n_k входов в k-м элементе ИЛИ, где N - количество разрядов в каждом суммируемом коде, n_k = k + I для k = 1,2,.. . , N, n_k = 2 N - k + I для k = N + I, N + 2,..., 2 N - 1 , при этом первый вход каждого элемента И j-й группы элементов И (j = 1, 2,..., N) подключен к входу разряда j - 1 первого кода, второй вход i-го элемента И каждой группы элементов И (i = 1,2,..., N) подключен к входу разряда i-1 второго кода, а к выходу разряда k-1 сумматора уплотненных кодов подключены через k-й элемент ИЛИ входы разряда k-1 первого и второго кода (k=1,2,..., N), выход i-го элемента И j-й группы элементов И, удовлетворяющего условию i + j = k (k = 2, 3, . .., 2 N-1), к выходу разряда 2N-1 сумматора уплотненных кодов подключен выход N-го элемента И N-й группы элементов И.

На входы разрядов первого и второго кода сумматора уплотненных кодов поступают сигналы соответственно первого и второго уплотненных кодов, в каждом из которых число i представлено единицами в разрядах 0, 1,..., i-1, число 0 - нулями во всех разрядах. Сигналы разрядов i-1 обоих кодов поступают через i-й элемент ИЛИ на выход разряда i-1 сумматора уплотненных кодов. Сигналы разряда i-1 первого уплотненного кода и разряда j-1 второго уплотненного кода логически умножаются i-м элементом И j-й группы элементов И, выходной сигнал которого поступает через (i+j)-й элемент ИЛИ на выход разряда i + j = 1 сумматора уплотненных кодов. В результате на выходах разрядов последнего образуется код суммы, в котором количество единиц равно сумме количества единиц во входных кодах, и все единицы сдвинуты к разряду 0.

Недостатками сумматора уплотненных кодов в случае использования его для сложения кодов "1 из N" являются наложение входных коlов на выходной код суммы и большие затраты оборудования.

Первый недостаток определяется логическим сложением в выходных разрядах 0,1, ..., N -1 сумматора уплотненных кодов сигналов соответствующих разрядов входных кодов и их суммы.

Второй недостаток определяется, во-первых, тем, что для получения суммы в коде "1 из N" необходимо введение в каждом выходном разряде 0, 1,..., N -1 схемы запрета единиц входных кодов, прямой вход, первый и второй инверсные входы которой соединены соответственно с выходом разряда сумматора уплотненных кодов, с входом аналогичного разряда первого и второго кодов. Схема запрета запрещает прохождение единицы выходного разряда сумматора уплотненных кодов при наличии единицы в разряде хотя бы одного входного кода и разрешает прохождение сигнала суммы при наличии нуля в разряде обоих входных кодов.

Второй недостаток определяется, во-вторых, тем, что для получения кода суммы используется большое, равное N², количество частичных сумм и реализующих их элементов И, так как частичные суммы образуются логическим умножением сигнала каждого разряда первого кода с сигналом каждого разряда второго кода.

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

В заявляемом устройстве указанные недостатки исключаются за счет формирования кода суммы логическим сложением частичных сумм, которые образуются поразрядным логическим умножением входных кодов и попарным логическим умножением сигналов поразрядного логического сложения входных кодов, при этом поразрядным операциям подвергаются одинаковые разряды. В результате входные коды не поступают в код суммы, количество частичных сумм и реализующих их элементов И уменьшается до N (N+1)/2.

На фиг. 1 изображена схема сумматора кодов "1 из N" на пять разрядов, на фиг. 2 - диаграмма, поясняющая сложение кодов "1 из 5".

Сумматор кодов "1 из 5" (фиг. 1) содержит элементы И 1.1, 1.2, 1.3, 1.4, 1.5 первой группы элементов И, элементы И 2.1, 2.2, 2.3, 2.4 второй группы элементов И, элементы И 3.1, 3.2, 3.3 третьей группы элементов И, элементы И 4.1, 4.2 четвертой группы элементов И, элемент И 5.1 пятой группы элементов И, элементы ИЛИ 6.1, 6.2, 6.3, 6.4, 6.5 первой группы элементов ИЛИ, элементы ИЛИ 7.1. 7.2, 7.3, 7.4, 7.5 второй группы элементов ИЛИ, входы 8.1, 8.2, 8.3, 8.4, 8.5 соответственно разрядов 0, 1, 2, 3, 4 первого кода, входы 9.1, 9.2, 9.3, 9.4, 9.5 соответственно разрядов 0, 1, 2, 3, 4 второго кода, выходы 10.1, 10,2,...10.9 соответственно разрядов 0, 1,...,8 сумматора кодов "1 из 5".

Первый вход элемента И 1.1 (1.2, 1.3, 1.4, 1.5) первой группы элементов И и первый вход элемента ИЛИ 6.1 (6.2, 6.3, 6.4, 6.5) подключен к входу 8.1 (8.2, 8.3, 8.4, 8.5) разряда 0 (1, 2, 3, 4) первого кода, второй вход указанных элементов И, ИЛИ подключен к входу 9.1 (9.2, 9.3, 9.4, 9.5) разряда 0 (1, 2, 3, 4) второго кода.

Первый вход элементов И 2.1, 2.2, 2.3, 2.4 второй группы элементов И соединен с выходом элемента ИЛИ 6.1 первой группы элементов ИЛИ, второй вход элемента И 2.1 (2.2, 2.3, 2.4) второй группы элементов И соединен с выходом элемента ИЛИ 6.2 (6.3, 6.4, 6.5) первой группы элементов ИЛИ.

Первый вход элементов И 3.1, 3.2, 3.3 третьей группы элементов И соединен с выхода элемента ИЛИ 6.2 первой группы элементов ИЛИ, второй вход элемента И 3.1 (3.2, 3.3) третьей группы элементов И соединен с выходом элемента ИЛИ 6.3 (6.4, 6.5) первой группы элементов ИЛИ.

Первый вход элементов И 4.1, 4.2 четвертой группы элементов И соединен с выходом элемента ИЛИ 6.3 первой группы элементов ИЛИ, второй вход элемента И 4.1 (4.2) четвертой группы элементов И соединен с выходом элемента ИЛИ 6.4 (65) первой группы элементов ИЛИ.

Первый и второй входы элемента И 5.1 пятой группы элементов И соединен соответственно с выходом элементов ИЛИ 6.4 и 6.5 первой группы элементов ИЛИ.

Выход элемента И 1.1 первой группы элементов И, выход элемента И 2.1 второй группы элементов И, выход элемента И 5.1 пятой группы элементов И, выход элемента И 1.5 первой группы элементов И подключены соответственно к выходам 10.1, 10.2, 10.8, 10.9 разрядов 0, 1, 7, 8 сумматора кодов "1 из 5".

Выход элемента И 1.2 первой группы элементов И и выход элемента И 2.2 второй группы элементов И подключены через элемент ИЛИ 7.1 второй группы элементов ИЛИ к выходу 10.3 разряда 2 сумматора кодов "1 из 5".

Выход элемента И 2.3 второй группы элементов И и выход элемента И 3.1 третьей группы элементов И подключены через элемент ИЛИ 7.2 второй группы элементов ИЛИ к выходу 10.4 разряда 3 сумматора кодов "1 из 5".

Выход элемента И 1.3 первой группы элементов И, выход элемента И 2.4 второй группы элементов И и выход элемента И 3.2 третьей группы элементов И подключены через элемент ИЛИ 7.3 второй группы элементов ИЛИ к выходу 10.5 разряда 4 сумматора кодов "1 из 5".

Выход элемента И 3.3 третьей группы элементов И и выход элемента И 4.1 четвертой группы элементов И подключены через элемент ИЛИ 7.4 второй группы элементов ИЛИ к выходу 10.6 разряда 5 сумматора кодов "1 из 5".

Выход элемента И 1.4 первой группы элементов И и выход элемента И 4.2 четвертой группы элементов И подключены через элемент ИЛИ 7.5 второй группы элементов ИЛИ к выходу 10.7 разряда 6 сумматора кодов "1 ил 5".

В общем случае сумматор кодов "1 из N", где N - количество разрядов в каждом входном коде, содержит N групп элементов И, N элементов И в первой группе элементов И, N + 1 - j элементов И в j-й группе элементов И (j = 2, 3, ...,N), N элементов ИЛИ в первой группе элементов ИЛИ, 2N-5 элементов ИЛИ во второй группе элементов ИЛИ, при этом k-й элемент ИЛИ второй группы элементов ИЛИ (k=1, 2,..., 2N-5) содержит n_k входов, где n_k = для k = 1,2, ..., N-2, n_k = для k = N -1, N,..., 2N-5, символ означает целую часть числа (k+3)/2, первый вход i-го элемента И первой группы элементов И и i-го элемента ИЛИ первой группы элементов ИЛИ (i = 1, 2... , N) подключен к входу разряда i-1 первого кода, второй вход указанных элементов И, ИЛИ подключен к входу разряда i-1 второго кода, первый вход каждого элемента И j - й группы элементов И соединен с выходом (j-1)-го элемента ИЛИ первой группы элементов ИЛИ, второй вход m-го элемента И j-й группы элементов И (m =1, 2,..., N + 1-j) соединен с выходом (m + j -1)-го элемента ИЛИ первой группы элементов ИЛИ, а выход первого элемента И первой группы элементов И, выход первого элемента И второй группы элементов И, выход элемента И N-й группы элементов И и выход N-го элемента И первой группы элементов И подключены соответственно к выходу разрядов 0,1, 2N-3 и 2N -2 сумматора кодов "1 из N", выход p-го элемента И первой группы элементов И (p= 2, 3,..., N -1) подключен через (2p-3)-й элемент ИЛИ второй группы элементов ИЛИ к выходу разряда 2(p-1) сумматора кодов "1 из N", выход m-го элемента И p-й группы элементов И, кроме первого элемента И второй группы элементов И, подключен через (m+2p-5)-й элемент ИЛИ второй группы элементов ИЛИ к выходу разряда m+2p-4 сумматора кодов "1 из N".

Сумматор кодов "1 из 5" работает следующим образом.

На входы 8.1, 8.2, 8.3, 8.4, 8.5 разрядов 0, 1, 2, 3, 4, первого кода и входы 9.1, 9.2, 9.3, 9.4, 9.5 разрядов 0, 1, 2, 3, 4 второго кода (см. фиг. 1) поступают сигналы разрядов соответственно первого и второго кода "1 из 5". В каждом из этих кодов только в одном разряде сигнал равен единице, и числу q = 0, 1, 2, 3, 4 соответствует единица в разряде q (см. фиг. 2).

Элементы И 1.1, 1.2, 1.3, 1.4, 1.5 первой группы элементов И осуществляют поразрядное логическое умножение входных кодов, элементы ИЛИ 6.1, 6.2, 6.3, 6.4, 6.5 первой группы элементов ИЛИ - поразрядное логическое сложение входных кодов. Указанные элементы И образуют частичные суммы одинаковых входных кодов, при этом единица на выходе элемента И 1.1 (1.2, 1.3, 1.4, 1.5) представляет частичную сумму, равную числу 0 (2, 4, 6, 8). Одинаковые входные коды образуют единицу на выходе одного, неодинаковые входные коды - на выходе двух элементов ИЛИ 6.1, 6.2, 6.3, 6.4, 6.5, при этом единица на выходе элемента ИЛИ 6.1 (6.2, 6.3, 6.4, 6.5) представляет число 0 (1, 2, 3, 4).

Элементы И 2.1, 2.2, 2.3, 2.4 второй группы элементов И образуют частичную сумму из сигнала числа 0 с выхода элемента ИЛИ 6.1 и сигнала числа соответственно 1, 2, 3, 4 с выхода элементов ИЛИ 6.2, 6.3, 6.4, 6.5 первой группы элементов ИЛИ, при этом единица на выходе элемента И 2.1 (2.2, 2.3, 2,4) представляет частичную сумму, равную числу 1 (2, 3, 4).

Элементы И 3.1, 3.2, 3.3 третьей группы элементов И образуют частичную сумму из сигнала числа 1 с выхода элемента ИЛИ 6.2 и сигнала числа соответственно 2, 3, 4 с выхода элементов ИЛИ 6.3, 6.4, 6.5 первой группы элементов ИЛИ, при этом единица на выходе элемента И 3.1 (3.2, 3.3) представляет частичную сумму, равную числу 3 (4, 5).

Элементы И 4.1, 4.2 четвертой группы элементов И образуют частичную сумму из сигнала числа 2 с выхода элемента ИЛИ 6.3 и сигнала числа соответственно 3, 4 с выхода элементов ИЛИ 6.4, 6.5 первой группы элементов ИЛИ, при этом единица на выходе элемента И 4.1 (4.2) представляет частичную сумму, равную числу 5 (6).

Элемент И 5.1 пятой группы элементов И образует частичную сумму из сигнала числа 3 и 4 с выхода соответственно элементов ИЛИ 6.4 и 6.5 первой группы элементов ИЛИ, при этом единица на выходе элемента И 5.1 представляет частичную сумму, равную числу 7.

Элементы ИЛИ 7.1, 7.2, 7.3, 7.4, 7.5 второй группы элементов ИЛИ объединяют сигналы частичных сумм, равных соответственно числу 2, 3, 4, 5, 6 и образованных соответствующими элементами И первой, второй, третьей, четвертой групп элементов И.

Сигнал частичной суммы, равной числу 0, 1, 2, 3, 4, 5, 6, 7, 8, с выхода соответственно элемента И 1.1 первой группы элементов И, элемента И 2.1 второй группы элементов И, элементов ИЛИ 7.1, 7.2, 7.3, 7.4, 7.5 второй группы элементов ИЛИ, элемента И 5.1 пятой группы элементов И и элемента И 1.5 первой группы элементов И поступает соответственно на выходы 10.1, 10.2, 10.3, 10.4, 10.5, 10.6, 10.7, 10.8, 10.9 разрядов 0, 1, 2, 3, 4, 5, 6, 7, 8 сумматора кодов "1 из 5". В результате на выходах указанных разрядов последнего образуется код "1 из 10" суммы входных кодов "1 из 5" (пример сложения чисел 0 и 4 в коде "1 из 5" приведен на фиг. 2).

Аналогичным образом работает сумматор кодов "1 из N" любой разрядности.

В известном устройстве, взятом за прототип, сигналы с выходов элементов ИЛИ, осуществляющих поразрядное логическое сложение входных кодов, объединяются в выходных разрядах с сигналами частичных сумм, которые образуются логическим умножением сигналов разрядов первого и второго кодов по принципу "каждый с каждым". Это приводит к наложению входных кодов на код суммы и к большому количеству частичных сумм и реализующих их элементов И, равному N².

В заявляемом устройстве сигналы с выходов элементов ИЛИ, осуществляющих поразрядное логическое сложение входных кодов, используются только для образования частичных сумм, что исключает наложение входных кодов на код суммы и уменьшает количество частичных сумм и реализующих их элементов И до N(N+1)/2, т. е. почти в два раза. Это приводит также к упрощению элементов ИЛИ за счет соответствующего уменьшения количества их входов.

Изобретение относится к цифровой связи, автоматике и вычислительной технике и может быть использовано при реализации параллельных выделителей канальных цифровых сигналов, устройств сигнализации и устройств для подсчета количества единиц в двоичной комбинации. Технический результат заключается в устранении наложения входных кодов на выходной код суммы при одновременном уменьшении затрат оборудования. Технический результат достигается за счет формирования кода суммы логическим сложением частичных сумм, которые образуются поразрядным логическим умножением входных кодов и попарным логическим умножением сигналов поразрядного логического сложением входных кодов. При этом поразрядным операциям подвергаются одинаковые разряды. В результате входные коды не поступают в код суммы. Количество частичных сумм и реализующих их элементов И уменьшается до N(N+1)/2. 2 ил.

Сумматор кодов "1 из N", содержащий N групп элементов И, первую и вторую группы элементов ИЛИ, N элементов И в первой группе элементов И, N элементов ИЛИ в первой группе элементов ИЛИ, где N - количество разрядов в каждом входном коде, при этом первый вход i-го элемента И первой группы элементов И и i-го элемента ИЛИ первой группы элементов ИЛИ (i = 1, 2, ..., N) подключен к входу разряда i - 1 первого кода, второй вход указанных элементов И, ИЛИ подключен к входу разряда i - 1 второго кода, отличающийся тем, что j-я группа элементов И (j = 2, 3, ..., N) содержит N + 1 - j элементов И, вторая группа элементов ИЛИ содержит 2N - 5 элементов ИЛИ, k-й элемент ИЛИ второй группы элементов ИЛИ (k = 1, 2, ..., 2N - 5) содержит n_k входов, где n_k = для k = 1, 2, ..., N - 2, для k = N - 1, N, ..., 2N - 5, символ означает целую часть числа (k + 3)/2, при этом первый вход каждого элемента И j-й группы элементов И соединен с выходом (j - 1)-го элемента ИЛИ первой группы элементов ИЛИ, второй вход m-го элемента И j-й группы элементов И (m = 1, 2, ..., N + 1 - j) соединен с выходом (m + j - 1)-го элемента ИЛИ первой группы элементов ИЛИ, а выход первого элемента И первой группы элементов И, выход первого элемента И второй группы элементов И, выход элемента И N-й группы элементов И и выход N-го элемента И первой группы элементов И подключены соответственно к выходу разряда 0, 1, 2N - 3 и 2N - 2 сумматора кодов "1 из N", выход p-го элемента И первой группы элементов И (p = 2, 3, ..., N - 1) подключен через (2p-3)-й элемент ИЛИ второй группы элементов ИЛИ к выходу разряда 2(p - 1) сумматора кодов "1 из N", выход m-го элемента И p-й группы элементов И, кроме первого элемента И второй группы элементов И, подключен через (m + 2p - 5)-й элемент ИЛИ второй группы элементов ИЛИ к выходу разряда m + 2p - 4 сумматора кодов "1 из N".