СЧЕТЧИК С СОХРАНЕНИЕМ КОЛИЧЕСТВА ЕДИНИЦ
COUNTER WITH SAVING THE NUMBER OF UNITS

ОБЛАСТЬ ТЕХНИКИ
Изобретение относится к области вычислительной техники и автоматики, предназначено для генерации многовыходных кодовых комбинаций и может быть использовано в задачах криптографии и задачах минимизации с помощью аппарата линейного программирования.
ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ
Известен счетчик с переменным модулем счета (Схемотехника ЭВМ. Сборник задач: учебное пособие. - М.: НИЯУ МИФИ, 2012. - 240 с., рис. 72, с. 79-81), содержащий счетчик, схему сравнения и элемент ИЛИ, причем выходы счетчика соединены с первой группой входов схемы сравнения, вторая группа входов которой соединена с внешними входами задания модуля счета, а выход схемы сравнения соединен с первым входом элемента ИЛИ, второй вход которого подключен к внешнему входу начальной установки, а выход элемента ИЛИ соединен с входом синхронной установки счетчика в нулевое состояние. Данный счетчик позволяет оперативно изменять (программировать) модуль пересчета.
Недостатком данного устройства является формирование последовательных двоичных наборов, которые не сохраняют количество единичных бит.
1
2
n
1
2
n
1
2
n-1
1
2
n
1
2
n
1
2
n
1
2
n
1
2
n
Известен счетчик групповой структуры с переменным модулем (RU №2617329 С1, МПК H03K 23/40, G06F 17/00, заявлен 21.03.2016, публикован 24.04.2017, Бюл. №12) содержащий группу из N счетчиков 1, 1, …, 1, первую группу из N схем сравнения 2, 2, …, 2, группу из N-1 сумматоров 3, 3, …, 3, вторую группу из N схем сравнения 4, 4, …, 4, первую группу из N элементов ИЛИ 5, 5, …, 5, вторую группу из N элементов ИЛИ 6, 6, …, 6, дешифратор 7, мультиплексор 8, группу из N внешних входов задания модулей счета 9, 9, …, 9, внешние входы задания суммарного модуля счета 10, внешние входы задания количества счетчиков 11, внешний вход синхронизации 12, внешний вход сброса 13, внешний вход разрешения работы 14, группу из N внешних выходов 15, 15, …, 15, внешний выход переноса счетчика 16. Алгоритм работы счетчика основан на установке в нулевое состояние младших групп счетчика при достижении в текущей группе значения суммарного модуля МА.
Недостатком данного устройства является формирование последовательных двоичных наборов, которые не сохраняют количество единичных бит.
Известен генератор m-разрядных двоичных последовательностей с неубывающим числом единиц (описан в Устройстве для решения комбинаторных задач SU №1672466 Α1, МПК G06F 15/20, заявлено 31.05.1989, опубликовано 23.08.1991, Бюл. №31 и в Устройстве для вычисления комбинаторных функций RU №2006934 С1, МПК G06F 15/20, заявлено 01.07.1991, опубликовано 30.01.1994), содержащий группу из m загрузочных триггеров с прямыми и инверсными выходами и начальной установкой в начальное состояние, треугольную матрицу (из m столбцов и m строк) разрядных триггеров с начальной установкой в нулевое состояние, группы элементов И и элементов ИЛИ, которые также образуют треугольные матрицы, и группу выходных элементов ИЛИ, объединяющие прямые выходы триггеров в разрядных столбцах треугольной матрицы.
Недостатком данного устройства являются большие аппаратные затраты и низкое быстродействие, что связано с последовательным формированием следующего состояния последовательности.
1
2
g
1
2
g
1
2
g
1
2
(Ki)
1
2
(Ki)
1
2
(Ki)
Наиболее близким устройством, того же назначения к заявленному изобретению по совокупности признаков, является принятый за прототип, счетчик групповой структуры с сохранением количества единиц в группах (RU №2736704 С1, МПК H03K 23/40, G06F 17/00, заявлен 17.03.2020, опубликован 19.11.2020, Бюл. №32) содержащий внешнюю входную N разрядную шину данных DI, внешнюю выходную N разрядную шину QO, группу из G групповых счетчиков 1, 1, …, 1, первую группу из G элементов И 2, 2, …, 2, группу из G элементов ИЛИ 3, 3, …, 3, блок межгрупповых переносов 4, внешний вход синхронизации CLK, внешние входные G разрядные шины разрешения загрузки в группы EL, параллельного счета групп ЕР и последовательного счета групп ЕС, внешний выход переноса СО. Каждый из групповых счетчиков 1i (где i = 1, …, G) состоит (Ki) разрядов (где N = K1+K2+…+KG) и содержит из (Ki) D-триггеров 5, 5, 5, формирователь переноса 6, группу из (Ki) формирователей кода с сохранением количества единиц 7, 7, …, 7, группу из (Ki) мультиплексоров MX 8, 8, …, 8, элемент ИЛИ 9 и внутреннюю (Ki) разрядную шину QT выходов триггеров.
Недостатком данного устройства является выполнение переходов для каждого входного набора единиц Ki только по одному графу переходов и большие аппаратные затраты на формирование кода следующего состояния.
ЗАДАЧА ИЗОБРЕТЕНИЯ
Задачей изобретения является разработка аппаратных средств, которые сохраняют количество единиц в последовательных состояниях счетчика.
В задачах криптографии при формировании блочных шифров устройство предназначено для реализации операций рассеивания и перемешивания в наборах раундовых функций при одновременной параллельной обработке нескольких групп данных по различным графам переходов.
В комбинаторных задачах и задачах целочисленного линейного программирования устройство предназначено для генерации перестановок без повторов.
Техническим результатом изобретения является расширение арсенала средств того же назначения, в части возможности сохранения заданного количества единиц в наборах последовательных состояний счетчика, управлять выбором графа перехода для состояний счетчика и уменьшение аппаратных затрат.
КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ
3
2
1
0
3
2
1
0
Указанный технический результат при осуществлении изобретения достигается тем, что счетчик с сохранением количества единиц содержит внешние входы устройства D3, D2, D1, D0, внешние управляющие входы Y1, Y0, внешние выходы устройства Q3, Q2, Q1, Q0, внешний выход переноса CR, синхронные D-триггеры с входом СЕ разрешения работы 1, 1, 1, 1, мультиплексоры 2, 2, 2, 2, логический элемент ИЛИ-НЕ 3, двухразрядный двоичный счетчик 4, а также содержит внешний вход разрешения работы 5 и внешний вход синхронизации 6,
3
2
1
0
причем внешние входы устройства D3, D2, D1, D0 соединены с нулевыми входами соответствующих мультиплексоров 2, 2, 2, 2,
3
2
1
0
внешний вход разрешения работы 5 и внешний вход синхронизации 6 соединены с соответствующими одноименными входами СЕ разрешения работы и входами С синхронизации D-триггеров 1, 1, 1 1 и двоичного счетчика 4,
3
2
1
0
внешние управляющие входы Y1, Y0 соединены с соответствующими адресными входами S1, S0 мультиплексоров 2, 2, 2, 2 и подключены к первому и второму входам логического элемента ИЛИ-НЕ 3, выход которого соединен с входом R синхронной установки счетчика 4 в нулевое состояние, выход которого является внешним выходом переноса CR,
3
2
1
кроме того, выход D-триггера 1 соединен с первым и вторым информационными входами мультиплексора 2 и третьим информационным входом мультиплексора 2,
2
1
0
выход D-триггера 1 соединен с первым информационным входом мультиплексора 2, а также соединен со вторым и с третьим информационными входами мультиплексора 2,
1
3
2
0
выход D-триггера 1 соединен со вторым информационным входом мультиплексора 2, с третьим информационным входом мультиплексора 2, и с первым информационным входом мультиплексора 2,
0
3
1
выход D-триггера 1 соединен с первым и третьим информационными входами мультиплексора 2 и со вторым информационным входом мультиплексора 2,
3
2
1
0
3
2
1
0
причем выходы мультиплексоров 2, 2, 2, 2 соединены с входами D соответствующих D-триггеров 1, 1, 1 1, выходы которых являются соответствующими внешними выходами устройства Q3, Q2, Q1, Q0.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
На фиг. 1 приведена функциональная схема предлагаемого счетчика с сохранением количества единиц. На фиг. 2 приведено условное графическое обозначение предлагаемого счетчика. В таблице 1 приведены выполняемые микрооперации счетчика. В таблице 2 приведены задаваемые графы переходов счетчика.
На фиг. 1-2, в таблицах 1-2 и в тексте приняты следующие обозначения:
D3, D2, D1, D0 - внешние входы устройства,
Y1, Y0 - внешние управляющие входы,
Q3, Q2, Q1, Q0 - внешние выходы устройства,
CR - внешний выход переноса,
G - графы переходов,
V1, V2, V3 - варианты коммутации межразрядных цепей переноса,
С - синхровходы счетчика СТ и триггеров Т,
СЕ - входы разрешения работы,
CR - внешний выход переноса,
СТ - двухразрядный двоичный счетчик,
D - информационный вход триггера,
K - количество единиц,
MX - мультиплексор,
N=4 - количество разрядов,
R - синхронный вход установки триггера в нулевое состояние, S1, S0 - адресные входы мультиплексоров, Τ - триггер.
3
2
1
0
1, 1, 1 1 - синхронные D-триггера с входом СЕ разрешения работы,
3
2
1
0
2, 2, 2, 2 - мультиплексоры,
3 - логический элемент ИЛИ-НЕ,
4 - двухразрядный двоичный счетчик,
5 - внешний вход разрешения работы СЕ,
6 - внешний вход синхронизации С.
3
2
1
0
3
2
1
0
Счетчик с сохранением количества единиц содержит внешние входы устройства D3, D2, D1, D0, внешние управляющие входы Y1, Y0, внешние выходы устройства Q3, Q2, Q1, Q0, внешний выход переноса CR, синхронные D-триггеры с входом СЕ разрешения работы 1, 1, 1 1, мультиплексоры 2, 2, 2, 2, логический элемент ИЛИ-НЕ 3, двухразрядный двоичный счетчик 4, а также содержит внешний вход разрешения работы 5 и внешний вход синхронизации 6.
3
2
1
0
Внешние входы устройства D3, D2, D1, D0 соединены с нулевыми входами соответствующих мультиплексоров 2, 2, 2, 2.
3
2
1
0
Внешний вход разрешения работы 5 и внешний вход синхронизации 6 соединены с соответствующими одноименными входами СЕ разрешения работы и входами С синхронизации D-триггеров 1, 1, 1 1 и двоичного счетчика 4.
3
2
1
0
Внешние управляющие входы Y1, Y0 соединены с соответствующими адресными входами S1, S0 мультиплексоров 2, 2, 2, 2 и подключены к первому и второму входам логического элемента ИЛИ-НЕ 3. Выход логического элемента ИЛИ-НЕ 3 соединен с входом R синхронной установки счетчика 4 в нулевое состояние, выход которого является внешним выходом переноса CR.
3
2
1
Выход D-триггера 1 соединен с первым и вторым информационными входами мультиплексора 2 и третьим информационным входом мультиплексора 2.
2
1
0
Выход D-триггера 1 соединен с первым информационным входом мультиплексора 2, а также соединен со вторым и с третьим информационными входами мультиплексора 2.
1
3
1
0
Выход D-триггера 1 соединен со вторым информационным входом мультиплексора 2, с третьим информационным входом мультиплексора 2, и с первым информационным входом мультиплексора 2.
0
3
1
Выход D-триггера 1 соединен с первым и третьим информационными входами мультиплексора 2 и со вторым информационным входом мультиплексора 2.
3
2
1
0
3
2
1
0
Выходы мультиплексоров 2, 2, 2, 2 соединены с входами D соответствующих D-триггеров 1, 1, 1 1.
3
2
1
0
Выходы D-триггеров1, 1, 1 1 являются соответствующими внешними выходами устройства Q3, Q2, Q1, Q0.
ПОДРОБНОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ
Принцип работы предлагаемого устройства состоит в следующем. Предлагаемый счетчик позволяет генерировать на внешних выходах Q счетчика N разрядные кодовые комбинации (N=4), в которых сохраняется заданное количество единиц К. При этом в устройстве можно задавать (программировать) единичные значения на соответствующих внешних входах данных D3, D2, D1, D0 (К≤N).
3
2
1
0
Предлагаемый счетчик реализован на четырех синхронных D-триггерах 1, 1, 1 1. На внешних управляющих входах Y1, Y0 задается номер варианта (V1, V2 или V3) коммутации межразрядных цепей переноса или режим начальной загрузки. В таблице 1 приведены выполняемые микрооперации (загрузка или сдвиг) и цепи межразрядных переносов. Например, вариант V1 и 0-3-2-1-0 соответствует следующим межразрядным сдвигам: из 0-го разряда в 3-й разряд, из 3-го разряда во 2-й разряд, из 2-го разряда в 1-й разряд и из 1-го разряда в 0-й разряд. Все межразрядные сдвиги осуществляются одновременно по фронту 0/1 синхросигналов С на внешнем входе 6.
Счетчик осуществляет переходы в соответствии с графами состояний при единичном значении разрешающего сигнала СЕ на внешнем входе 5 в соответствии с графами состояний G. Функционирование счетчика приведено в таблице 2 в виде графов переходов G, последовательности состояний. В вершинах графа указаны значения десятичных кодов состояний выходов Q (Q3 старший разряд, Q0 - младший). В номере графа G первая цифра указывает количество единиц в состояниях, а вторая - порядковый номер. Например, граф G25 - в разрядах Q3, …, Q0 кода состояний содержится две единицы, а цифра 5 - порядковый номер графа. В начальное состояние (первая левая вершина графа) счетчик устанавливается в режиме загрузки (Y1=0, Υ0=0). Одноименные графы G в таблице 2 указывают на одинаковую последовательность переходов между состояниями.
При одной единице (К=1 из 4) и трех единицах (К=3 из 4) графы переходов соответственно G11, G12, G13 и G31, G32, G33 определяются только номером варианта (V1, V2 или V3) коммутации межразрядных цепей переноса для всех соответствующих начальных значений. При двух единицах (К=2 из 4) переходы возможны по шести графам G21, …, G26 в зависимости от номера варианта (V1, V2 или V3) коммутации межразрядных цепей переноса и от начальных данных на входах D3, D2, D1, D0 или состояния установленного на выходах при смене варианта (V1, V2 или V3) коммутации. В графах G23, G24 и G26 (при К=2) соответствующих вариантов (V1, V2 или V3) коммутации межразрядных цепей переноса содержится только по две вершины для устойчивых состояний счетчика.
Кроме того, в устройстве осуществляется счет тактов двухразрядным двоичным счетчиком 4. При этом на каждом четвертом такте формируется единичное значение сигнала переноса CR=1. Синхронная установка по входу R в начальное нулевое состояние счетчика 4 осуществляется в режиме загрузки (Y1=0, Υ0=0).
Предлагаемый счетчик работает следующим образом. Алгоритм работы счетчика заключается в следующем.
3
2
1
0
Перед началом работы, в режиме параллельной загрузки (Υ1=0, Υ0=0), на внешних входах D3, D2, D1, D0 задается начальное значение кода, содержащее К единиц. Запись в D-триггеры 1, 1, 1 1 проводится по синхросигналу С на внешнем входе 6 при единичном значении сигнала разрешения работы СЕ на внешнем входе 5. Одновременно формируется единичное значение на выходе логического элемента ИЛИ-НЕ 3, которое передается на вход R счетчика 4, по которому осуществляется синхронная установка в нулевое состояние счетчика 4.
3
2
1
0
Далее на управляющих входах Y1 и Y0 устанавливается код в соответствии с таблицей 1, соответствующий номеру варианта (V1, V2 или V3) коммутации межразрядных цепей переноса. Переходы в следующие состояния в соответствии с графами G проводятся по следующим синхросигналам С на внешнем входе 6. Значения с выходов синхронных D-триггеры 1, 1, 1 1 передаются на внешние выходы устройства Q3, Q2, Q1, Q0. Одновременно в двухразрядном двоичном счетчике 4 осуществляется счет синхросигналов С и на каждом четвертом такте на выходе счетчика 4 формируется единичное значение, которое передается на внешний выход переноса CR=1.
Далее в процессе работы перед очередным синхросигналом С можно изменить значение кода на управляющих входах Y1 и Y0 в соответствии с таблицей 1, соответствующее новому номеру варианта (V1, V2 или V3) коммутации межразрядных цепей переноса. При этом устройство продолжит переходы в соответствии с задаваемым графом G, начиная с состояния, установленного в предыдущий момент времени, и двоичный счетчик 4 также продолжит счет с текущего значения.
3
2
1
0
Кроме того, в процессе работы перед очередным синхросигналом С можно задать новое требуемое значение кода на внешних входах D3, D2, D1, D0 содержащее К единиц и установить режим параллельной загрузки (Y1=0, Υ0=0), при котором значение кода будет загружено в D-триггеры 1, 1, 1 1 по синхросигналу С на внешнем входе 6 и при этом одновременно осуществляется синхронная установка в нулевое состояние счетчика 4.
В сравнении с прототипом в предлагаемом устройстве сокращаются аппаратные затраты, т.к. отсутствуют формирователи следующего состояния, а значения кода следующего состояния осуществляется за счет задания варианта коммутации межразрядных цепей переносов между разрядами счетчика.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемый счетчик соответствует заявляемому техническому результату - реализует на выходах генерацию кодовых комбинаций с сохранением количества единиц в наборах последовательных состояний счетчика, имеет возможность задавать начальное состояние счетчика и задавать вариант коммутации межразрядных цепей переносов между разрядами счетчика для соответствующих графов переходов, а также уменьшаются аппаратные затраты.