МАЖОРИТАРНЫЙ МОДУЛЬ ДЛЯ ОТКАЗОУСТОЙЧИВЫХ СИСТЕМ
MAJORITARY MODULE FOR FAULT-TOLERANT SYSTEMS

Изобретение относится к вычислительной технике и может быть использовано для построения отказоустойчивых средств автоматики, функциональных узлов систем управления и др.
Известны мажоритарные модули (например, патент РФ 2300137, кл. G06F 7/38, 2007 г.), которые содержат элементы 2И, трехвходовые мажоритарные элементы и реализуют мажоритарную функцию n аргументов.
К причине, препятствующей достижению указанного ниже технического результата при использовании известного мажоритарного модуля для реализации мажоритарной функции n аргументов - входных двоичных сигналов, относятся ограниченные функциональные возможности, т.к. устройство не может быть использовано в асинхронных схемах, высокая сложность и низкое быстродействие, т.к. устройство содержит 2×m+N-1 трехвходовых мажоритарных элементов, где m=0,5×(n+1),
.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип мажоритарный модуль (патент РФ 2533079, МПК H03K 19/23, G06F 7/57, 2014 г.), который содержит n информационных входов (n=2m+1, m=1, 2, …), первый выход устройства, n элементов И, два элемента ИЛИ, причем i-ый информационный вход соединен с первым входом i-го элемента И, (i=1, …, n), реализующий мажоритарную функцию n аргументов.
К причине, препятствующей достижению указанного ниже технического результата при использовании известного мажоритарного модуля для реализации мажоритарной функции n аргументов - входных двоичных сигналов, относятся ограниченные функциональные возможности, т.к. устройство не может быть использовано в асинхронных схемах, высокая сложность и низкое быстродействие, т.к. все мажоритарные элементы сгруппированы в три группы так, что в первой и второй группах содержится по m-1 (m=0,5×(n+1), n≠1 есть любое нечетное натуральное число) мажоритарных элементов, а в каждой группе выход предыдущего мажоритарного элемента соединен с вторым входом последующего мажоритарного элемента, все элементы 2И сгруппированы в  групп так, что в i-ой (i=1…N) группе содержится m-1 элементов 2И и выход предыдущего элемента 2И соединен с первым входом последующего элемента 2И.
Техническим результатом изобретения является расширение функциональных возможностей устройства за счет возможности его использования как в синхронных, так и в асинхронных дискретных схемах, уменьшение сложности устройства и повышение его быстродействия.
Указанный технический результат при осуществлении изобретения достигается тем, что в мажоритарный модуль для отказоустойчивых систем, содержащий n информационных входов (n=2m+1, m=1, 2, …), первый выход устройства, n элементов И, два элемента ИЛИ, причем i-ый информационный вход соединен с первым входом i-го элемента И, (i=1, …, n), дополнительно введены вход запуска, второй выход устройства, n+1 элементов задержки, регистр сдвига, причем выход i-го элемента И соединен через i-ый элемент задержки с i-ым входом первого элемента ИЛИ, (i=1, …, n), вход запуска соединен со вторыми входами всех элементов И, с первым тактовым входом и управляющим входом регистра сдвига и через (n+1)-ый элемент задержки с первым входом второго элемента ИЛИ, выход первого элемента ИЛИ соединен со вторым тактовым входом регистра сдвига, (m+2)-ой выход регистра сдвига соединен с первым выходом устройства и вторым входом второго элемента ИЛИ, выход второго элемента ИЛИ соединен со вторым выходом устройства, первый вход данных регистра сдвига соединен с шиной «логическая 1», j-ый вход данных регистра сдвига соединен с шиной «логический 0», j=2, …, m+2.
1
n
1
n
1
n+1
i
i
i
i
i
n
1
2
m+2
1
j
На чертеже представлена схема устройства. Мажоритарный модуль для отказоустойчивых систем содержит n информационных входов (n=2m+1, m=1, 2, …), 1-1, n элементов И 2-2, вход запуска 3, n+1 элементов задержки 4-4, первый элемент ИЛИ 5, второй элемент ИЛИ 6, регистр сдвига 7, первый выход устройства 8, второй выход устройства 9. Элементы схемы соединены следующим образом, i-ый информационный вход 1 соединен с первым входом i-го элемента И 2, (i=1, …, n). Выход i-го элемента И 2 соединен через i-ый элемент задержки 4 с i-ым входом первого элемента ИЛИ 5, (i=1, …, n). Вход запуска 3 соединен со вторыми входами всех элементов И 2-2, с первым тактовым входом (C) и управляющим входом (V) регистра сдвига 7 и через n+1-ый элемент задержки 4n+1 с первым входом второго элемента ИЛИ 6. Выход первого элемента ИЛИ 5 соединен со вторым тактовым входом (С) регистра сдвига 7. (m+2)-ой выход (Q) регистра сдвига 7 соединен с первым выходом 8 устройства и вторым входом второго элемента ИЛИ 6. Выход второго элемента ИЛИ 6 соединен со вторым выходом устройства 9. Первый вход данных (D) регистра сдвига 7 соединен с шиной «логическая 1». j-ый вход данных (D) регистра сдвига 7 соединен с шиной «логический 0», j=2, …, m+2.
Работает устройство следующим образом.
1
n
1
n
На информационные входы 1-1 подаются значения аргументов X-X, n - нечетное число, n=2m+1, m=1, 2, ….
На вход запуска 3 подается единичный импульс, который поступает:
1
1
m+2
1
m+2
- на первый тактовый вход (C) и управляющий вход (V) регистра сдвига 7, при этом в регистр сдвига 7 записывается с входов данных D-D двоичное число 10…0, которое и появляется на выходах Q-Q регистра сдвига 7;
1
n
i
i
i
c
с
2
- на вторые входы всех элементов И 2-2, при этом если значение i-го аргумента X=1, то импульс с входа запуска 3 проходит на выход элемента И 2, и через элемент задержки 4 с временем задержки i×T, (Т - время сдвига на один разряд в регистре сдвига), поступает на i-ый вход первого элемента ИЛИ 5. Сигнал с выхода первого элемента ИЛИ 5 поступает на второй тактовый вход (С) регистра сдвига 7, при этом происходит сдвиг содержимого регистра сдвига 7 вправо;
n+1
и
или
с
и
или
- через (n+1)-ый элемент задержки 4 со временем задержки Т+Т+(n+1)×Т (Т - время задержки в элементе И 2, Т - время задержки в элементе ИЛИ) поступает на первый вход второго элемента ИЛИ 6 и проходит на второй выход устройства 8.
В процессе работы устройства возможны два случая:
m+2
1. Количество значений «1» среди значений аргументов не менее чем m+1. В этом случае, как только поступит на выход первого элемента ИЛИ 5 (m+1)-ый импульс, то на выходе Q регистра сдвига 7 появится сигнал «1», который поступит на первый выход устройства 8, указывая на значение мажоритарной функции, и через второй элемент ИЛИ 6 на выход 9, указывая, что результат вычисления мажоритарной функции готов.
m+2
2. Количество значений «1» среди значений аргументов меньше чем m+1. В этом случае на выходе Q регистра сдвига 7 все время будет сигнал «0». После окончания опроса значений аргументов на первом входе второго элемента ИЛИ 6 появляется сигнал «1», который проходит на второй выход устройства 9, указывая, что результат вычисления мажоритарной функции готов и его значение «0» сформировано на первом выходе 8 устройства.
Особенностью предложенного устройства является то, что как только будет выявлено, что значение мажоритарной функции «1», то оно сразу же поступает на первый выход 8 устройства и на второй выход устройства 9, указывая, что данные готовы. Для большинства двоичных наборов время вычисления единичного значения мажоритарной функции будет меньше времени опроса всех значений аргументов. Это позволяет использовать устройство в асинхронных схемах. Т.е. заявленное устройство имеет более широкие функциональные возможности.
Сравним характеристики обоих устройств.
Максимальная задержка сигнала от подачи сигнала запуска на вход запуска 3 в заявленном устройстве
заяв
и
или
c
Т=Т+2Т+(n+1)×T
и растет линейно от количества аргументов.
1
n
1
n
1
n+1
Заявленный мажоритарный модуль содержит n информационных входов (n=2m+1, m=1, 2, …), 1-l, n элементов И 2-2, вход запуска 3, n+1 элементов задержки 4-4. Первый элемент ИЛИ 5 имеет n входов. Количество разрядов регистра сдвига 7 равно (n+1)/2.
Таким образом, сложность заявленного устройства растет линейно от количества аргументов.
В прототипе все мажоритарные элементы сгруппированы в три группы так, что в первой и второй группах содержится по m-1 (m=0,5×(n+1), n≠1 есть любое нечетное натуральное число) мажоритарных элементов, а в каждой группе выход предыдущего мажоритарного элемента соединен с вторым входом последующего мажоритарного элемента, все элементы 2И сгруппированы в  групп так, что в i-й (i=1…N) группе содержится m-1 элементов 2И и выход предыдущего элемента 2И соединен с первым входом последующего элемента 2И.
В таблице приведены значения количества групп N, рассчитанные по приведенной выше формуле, в зависимости от m и n.
Анализ приведенных значений показывает, что в прототипе сложность и задержка растет не по линейному закону, а значительно сильнее.
Сравнение характеристик прототипа и заявляемого устройства показывает, что заявленное устройство имеет более широкие функциональные возможности, меньшую сложность и большее быстродействие и эффективность его применения растет с количеством аргументов.