УСТРОЙСТВО ДЛЯ МАЖОРИТАРНОГО ВЫБОРА СИГНАЛОВ

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

Известны мажоритарные модули (например, патент РФ 2300137, кл. G06F 7/38, 2007 г.), которые содержат элементы 2И, трехвходовые мажоритарные элементы и реализуют мажоритарную функцию n аргументов - входных двоичных сигналов либо дизъюнкцию (конъюнкцию) тех же n аргументов.

К причине, препятствующей достижению указанного ниже технического результата при использовании известного мажоритарного модуля для реализации мажоритарной функции, дизъюнкции или конъюнкции n аргументов - входных двоичных сигналов, относятся высокая сложность и низкое быстродействие, т.к. устройство содержит 2xm+N-1 трехвходовых мажоритарных элементов, где m=0,5x(n+1),

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип мажоритарный модуль (патент РФ 2533079, МПК Н03K 19/23, G06F 7/57, 2014 г.), который содержит n информационных входов, первый выход устройства, две группы элементов И, группу элементов ИЛИ и реализующий мажоритарную функцию n аргументов - входных двоичных сигналов либо дизъюнкцию (конъюнкцию) тех же n аргументов.

К причине, препятствующей достижению указанного ниже технического результата при использовании известного мажоритарного модуля для реализации мажоритарной функции, дизъюнкции или конъюнкции n аргументов - входных двоичных сигналов, относятся высокая сложность и низкое быстродействие, т.к. все мажоритарные элементы сгруппированы в три группы так, что в первой и второй группах содержится по m-1 (m=0,5×(n+1), n≠1 есть любое нечетное натуральное число) мажоритарных элементов, а в каждой группе выход предыдущего мажоритарного элемента соединен с вторым входом последующего мажоритарного элемента, все элементы 2И сгруппированы в групп так, что в i-й (i=1…N) группе содержится m-1 элементов 2И и выход предыдущего элемента 2И соединен с первым входом последующего элемента 2И.

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для мажоритарного выбора сигналов, содержащее n информационных входов, первый выход устройства, две группы элементов И, группу элементов ИЛИ, особенность заключается в том, что в него введены вход запуска, второй и третий выходы устройства, выход готовности результата, три триггера, реверсивный двоичный счетчик, n+1 элементов задержки, n+2 элементов НЕ, первая и вторая группы элементов И содержат по n элементов И, группа элементов ИЛИ содержит n+2 элемента, причем вход запуска соединен с входами «сброс» первого триггера, второго триггера, третьего триггера, реверсивного двоичного счетчика, первыми входами первого элемента И, входящего в первую группу элементов И, и первого элемента И, входящего во вторую группу элементов И, выход j-го элемента ИЛИ соединен с первыми входами j+1-го элемента И, входящего в первую группу элементов И, и j+1-го элемента И, входящего во вторую группу элементов И (j=1, …, n-1), выход n-го элемента ИЛИ соединен через n+1-й элемент задержки с входом «установка в 1» третьего триггера, выход третьего триггера соединен с выходом готовности результата, i-й информационный вход соединен через i-й элемент задержки со вторым входом i-го элемента И, входящего в первую группу элементов И, и через i-й элемент НЕ соединен со вторым входом i-го элемента И, входящего во вторую группу элементов И, выход i-го элемента И, входящего в первую группу элементов И, соединен с первым входом i-го элемента ИЛИ и i-ым входом (n+1)-го элемента ИЛИ, выход i-го элемента И, входящего во вторую группу элементов И, соединен со вторым входом i-го элемента ИЛИ и i-ым входом (n+2)-го элемента ИЛИ (i=1, …, n), выход (n+1)-го элемента ИЛИ соединен с суммирующим входом реверсивного двоичного счетчика и входом «установка в 1» первого триггера, выход (n+2)-го элемента ИЛИ соединен с вычитающим входом реверсивного двоичного счетчика и входом «установка в 1» второго триггера, выход переноса «<0» реверсивного двоичного счетчика через n+2-й элемент НЕ соединен с первым выходом устройства, выход первого триггера соединен со вторым выходом устройства, выход второго триггера соединен через n+1-й элемент НЕ с третьим выходом устройства.

На чертеже представлена схема устройства для мажоритарного выбора сигналов, которое содержит n информационных входов 1₁ - 1_n, первую и вторую группы элементов И 2 и 3, которые содержат по n элементов И 2₁ - 2_n и 3₁ - 3_n, группу элементов ИЛИ 4, которая содержит n+2 элемента 4₁ - 4_n+2, n+1 элементов задержки 5₁ - 5_n+1, n+2 элементов НЕ 6₁ - 6_n+2, первый триггер 7, второй триггер 8, реверсивный двоичный счетчик 9, вход запуска 10, первый выход устройства 11, второй выход устройства 12, третий выходы устройства 13, выход готовности результата 14, третий триггер 15. Элементы схемы устройства соединены следующим образом. Вход запуска 10 соединен с входами «установка в 0» первого триггера 7, второго триггера 8, третьего триггера 15, реверсивного двоичного счетчика 9, первыми входами первого элемента И 2₁, входящего в первую группу элементов И и первого элемента И 3₁, входящего во вторую группу элементов И. Выход j-го элемента ИЛИ 4_j соединен с первыми входами j+1-го элемента И 2_j+1, входящего в первую группу элементов И и j+1-го элемента И 3_j+1, входящего во вторую группу элементов И (j=1, …, n-1). Выход n-го элемента ИЛИ 4_n соединен через n+1-й элемент задержки 5_n+1 с входом «установка в 1» третьего триггера 15. Выход третьего триггера 15 соединен с выходом готовности результата 14. i-й информационный вход 1_i соединен через i-й элемент задержки 5_i со вторым входом i-го элемента И 2_i, входящего в первую группу элементов И 2, и через i-й элемент НЕ 6_i соединен со вторым входом i-го элемента И 3_i, входящего во вторую группу элементов И 3. Выход i-го элемента И 2_i, входящего в первую группу элементов И 2 соединен с первым входом i-го элемента ИЛИ 4_i и i-ым входом (n+1)-го элемента ИЛИ 4_n+1. Выход i-го элемента И 3_i, входящего во вторую группу элементов И 3 соединен со вторым входом i-го элемента ИЛИ 4_i и i-ым входом (n+2)-го элемента ИЛИ 4_n+2 (i=1, …, n). Выход (n+1)-го элемента ИЛИ 4_n+1 соединен с суммирующим входом реверсивного двоичного счетчика 9 и входом «установка в 1» первого триггера 7. Выход (n+2)-го элемента ИЛИ 4_n+2 соединен с вычитающим входом реверсивного двоичного счетчика 9 и входом «установка в 1» второго триггера 8. Выход переноса «<0» реверсивного двоичного счетчика 9 через n+2-й элемент НЕ 6_n+2 соединен с первым выходом устройства 11. Выход первого триггера 7 соединен со вторым выходом устройства 12. Выход второго триггера 8 соединен через n+1-й элемент НЕ 6_n+1 с третьим выходом устройства 13.

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

На информационные входы 1₁ - 1_n подаются значения аргументов X₁ -X_n. n - нечетное число, n=2m+1, m=1, 2, ….

На вход запуска 10 подается единичный импульс, который поступает на входы «установка в 0» первого триггера 7, второго триггера 8, третьего триггера 15, реверсивного двоичного счетчика 9 и устанавливает их в нулевое состояние. Импульс запуска поступает одновременно на первые входы первого элемента И 2₁, входящего в первую группу элементов И, и первого элемента И 3₁, входящего во вторую группу элементов И.

Если значение аргумента X₁=1, то это значение поступает через элемент задержки 5₁ на второй вход первого элемента И 2₁, входящего в первую группу элементов И, и импульс запуска проходит на выход первого элемента И 2₁, входящего в первую группу элементов И и поступает:

- через элемент ИЛИ 4_n+1 на вход «Установка в 1» первого триггера 7 и устанавливает его в состояние «1» и на суммирующий вход реверсивного двоичного счетчика 9, увеличивая его состояние на 1,

- проходит на выход элемента ИЛИ 4₁ и включает аналогичную обработку значения следующего аргумента Х₂.

Если значение аргумента X₁=0, то это значение поступает через элемент НЕ 6₁ на второй вход первого элемента И 3₁, входящего во вторую группу элементов И, и импульс запуска проходит на выход первого элемента И 3₁, входящего во вторую группу элементов И, и поступает:

- через элемент ИЛИ 4_n+2 на вход «Установка в 1» второго триггера 8 и устанавливает его в состояние «1» и на вычитающий вход реверсивного двоичного счетчика 9, уменьшая его состояние на 1,

- проходит на выход элемента ИЛИ 4₁ и включает аналогичную обработку значения следующего аргумента Х₂.

Длительность задержки в элементах задержки 5₁ - 5_n равна длительности задержки в элементах НЕ 6₁ - 6_n. Это обеспечивает одинаковое время обработки значения аргумента для значений «0» и «1».

После поступления импульса на выход элемента 4i указанный процесс повторяется для второго аргумента и т.д. После обработки значения n-го аргумента на выход элемента ИЛИ 4_n проходит импульс, который через элемент задержки 5_n+1 проходит на вход «Установка в 1» третьего триггера 15 и устанавливает его значение в «1». На выходе 14 значение «1» свидетельствует о том, что обработка набора значений завершена и соответствующие результаты сформированы. Время задержки в элементе задержки 5_n+1 больше суммарного времени задержки в реверсивном двоичном счетчике 9 и элементе НЕ 6_n+2. Это обеспечивает окончание процесса формирования результатов.

В процессе работы устройства состояние реверсивного двоичного счетчика постоянно меняется, в зависимости от значений аргументов. Если на вычитающий вход поступило более чем m импульсов, то на выходе переноса «<0» реверсивного двоичного счетчика 9 формируется значение «1», которое инвертируется и значение «0» поступает на выход 11. Если более m значений аргументов равны «1», то аналогично на выходе 11 формируется сигнал «1». Таким образом, на выходе 11 реализуется мажоритарная функция.

Сигнал «1» на выходе 12 свидетельствует о том, что хотя бы одно из значений аргументов равно «1». Т.о. на выходе 12 реализуется операция дизъюнкция аргументов.

Значение сигнала «0» на выходе триггера 8 указывает, что все значения аргументов равны «1», и на выходе элемента НЕ 6_n+1 реализуется операция конъюнкция.

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

Сравним характеристики обоих устройств.

В заявленном устройстве его сложность и быстродействие растет линейно от количества аргументов.

Заявленное устройство содержит первую и вторую группы элементов И 2 и 3, которые содержат по n элементов И 2₁ - 2_n и 3₁ - 3_n, группу элементов ИЛИ 4, которая содержит n+2 элемента 4₁ - 4_n+2, n+1 элементов задержки 5₁ - 5_n+1, n+2 элементов НЕ 6₁ - 6_n+2, первый триггер 7, второй триггер 8, реверсивный двоичный счетчик 9, вход запуска 10, первый выход устройства 11, второй выход устройства 12, третий выход устройства 13, выход готовности результата 14, третий триггер 15.

В прототипе все мажоритарные элементы сгруппированы в три группы так, что в первой и второй группах содержится по m-1 (m=0,5×(n+1), n≠1 есть любое нечетное натуральное число) мажоритарных элементов, а в каждой группе выход предыдущего мажоритарного элемента соединен со вторым входом последующего мажоритарного элемента, все элементы 2И сгруппированы в групп так, что в i-й (i=1…N) группе содержится m-1 элементов 2И и выход предыдущего элемента 2И соединен с первым входом последующего элемента 2И.

В таблице приведены значения количества групп N, рассчитанные по приведенной выше формуле, в зависимости от m и n.

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

Так, например, для n=21 заявленное устройство содержит 42 элемента И, 23 элемента ИЛИ, 21 элемент задержки, 23 элемента НЕ, три триггера, реверсивный двоичный счетчик 9. В то время как прототип содержит 352714 групп элементов.

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