Счетчик с сохранением количества единиц

Изобретение относится к области вычислительной техники и автоматики. Технический результат заключается в обеспечении возможности сохранения заданного количества единиц в наборах последовательных состояний счетчика. Счетчик с сохранением количества единиц содержит внешние входы устройства D3, D2, D1, D0, внешние управляющие входы Y1, Y0, внешние выходы устройства Q3, Q2, Q1, Q0, внешний выход переноса CR, синхронные D-триггеры с входом СЕ разрешения работы 1₃, 1₂, 1₁, 1₀, мультиплексоры 2₃, 2₂, 2₁, 2₀, логический элемент ИЛИ-НЕ 3, двухразрядный двоичный счетчик 4, а также внешний вход разрешения работы 5 и внешний вход синхронизации 6. 2 ил., 2 табл.

 

ОБЛАСТЬ ТЕХНИКИ

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

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

Известен счетчик с переменным модулем счета (Схемотехника ЭВМ. Сборник задач: учебное пособие. - М.: НИЯУ МИФИ, 2012. - 240 с., рис. 72, с. 79-81), содержащий счетчик, схему сравнения и элемент ИЛИ, причем выходы счетчика соединены с первой группой входов схемы сравнения, вторая группа входов которой соединена с внешними входами задания модуля счета, а выход схемы сравнения соединен с первым входом элемента ИЛИ, второй вход которого подключен к внешнему входу начальной установки, а выход элемента ИЛИ соединен с входом синхронной установки счетчика в нулевое состояние. Данный счетчик позволяет оперативно изменять (программировать) модуль пересчета.

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

Известен счетчик групповой структуры с переменным модулем (RU №2617329 С1, МПК H03K 23/40, G06F 17/00, заявлен 21.03.2016, публикован 24.04.2017, Бюл. №12) содержащий группу из N счетчиков 1₁, 1₂, …, 1_n, первую группу из N схем сравнения 2₁, 2₂, …, 2_n, группу из N-1 сумматоров 3₁, 3₂, …, 3_n-1, вторую группу из N схем сравнения 4₁, 4₂, …, 4_n, первую группу из N элементов ИЛИ 5₁, 5₂, …, 5_n, вторую группу из N элементов ИЛИ 6₁, 6₂, …, 6_n, дешифратор 7, мультиплексор 8, группу из N внешних входов задания модулей счета 9₁, 9₂, …, 9_n, внешние входы задания суммарного модуля счета 10, внешние входы задания количества счетчиков 11, внешний вход синхронизации 12, внешний вход сброса 13, внешний вход разрешения работы 14, группу из N внешних выходов 15₁, 15₂, …, 15_n, внешний выход переноса счетчика 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 строк) разрядных триггеров с начальной установкой в нулевое состояние, группы элементов И и элементов ИЛИ, которые также образуют треугольные матрицы, и группу выходных элементов ИЛИ, объединяющие прямые выходы триггеров в разрядных столбцах треугольной матрицы.

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

Наиболее близким устройством, того же назначения к заявленному изобретению по совокупности признаков, является принятый за прототип, счетчик групповой структуры с сохранением количества единиц в группах (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, первую группу из G элементов И 2₁, 2₂, …, 2_g, группу из G элементов ИЛИ 3₁, 3₂, …, 3_g, блок межгрупповых переносов 4, внешний вход синхронизации CLK, внешние входные G разрядные шины разрешения загрузки в группы EL, параллельного счета групп ЕР и последовательного счета групп ЕС, внешний выход переноса СО. Каждый из групповых счетчиков 1i (где i = 1, …, G) состоит (Ki) разрядов (где N = K1+K2+…+KG) и содержит из (Ki) D-триггеров 5₁, 5₂, 5_(Ki), формирователь переноса 6, группу из (Ki) формирователей кода с сохранением количества единиц 7₁, 7₂, …, 7_(Ki), группу из (Ki) мультиплексоров MX 8₁, 8₂, …, 8_(Ki), элемент ИЛИ 9 и внутреннюю (Ki) разрядную шину QT выходов триггеров.

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

ЗАДАЧА ИЗОБРЕТЕНИЯ

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

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

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

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

КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Указанный технический результат при осуществлении изобретения достигается тем, что счетчик с сохранением количества единиц содержит внешние входы устройства D3, D2, D1, D0, внешние управляющие входы Y1, Y0, внешние выходы устройства Q3, Q2, Q1, Q0, внешний выход переноса CR, синхронные D-триггеры с входом СЕ разрешения работы 1₃, 1₂, 1₁, 1₀, мультиплексоры 2₃, 2₂, 2₁, 2₀, логический элемент ИЛИ-НЕ 3, двухразрядный двоичный счетчик 4, а также содержит внешний вход разрешения работы 5 и внешний вход синхронизации 6,

причем внешние входы устройства D3, D2, D1, D0 соединены с нулевыми входами соответствующих мультиплексоров 2₃, 2₂, 2₁, 2₀,

внешний вход разрешения работы 5 и внешний вход синхронизации 6 соединены с соответствующими одноименными входами СЕ разрешения работы и входами С синхронизации D-триггеров 1₃, 1₂, 1₁ 1₀ и двоичного счетчика 4,

внешние управляющие входы Y1, Y0 соединены с соответствующими адресными входами S1, S0 мультиплексоров 2₃, 2₂, 2₁, 2₀ и подключены к первому и второму входам логического элемента ИЛИ-НЕ 3, выход которого соединен с входом R синхронной установки счетчика 4 в нулевое состояние, выход которого является внешним выходом переноса CR,

кроме того, выход D-триггера 1₃ соединен с первым и вторым информационными входами мультиплексора 2₂ и третьим информационным входом мультиплексора 2₁,

выход D-триггера 1₂ соединен с первым информационным входом мультиплексора 2₁, а также соединен со вторым и с третьим информационными входами мультиплексора 2₀,

выход D-триггера 1₁ соединен со вторым информационным входом мультиплексора 2₃, с третьим информационным входом мультиплексора 2₂, и с первым информационным входом мультиплексора 2₀,

выход D-триггера 1₀ соединен с первым и третьим информационными входами мультиплексора 2₃ и со вторым информационным входом мультиплексора 2₁,

причем выходы мультиплексоров 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 - адресные входы мультиплексоров, Τ - триггер.

1₃, 1₂, 1₁ 1₀ - синхронные D-триггера с входом СЕ разрешения работы,

2₃, 2₂, 2₁, 2₀ - мультиплексоры,

3 - логический элемент ИЛИ-НЕ,

4 - двухразрядный двоичный счетчик,

5 - внешний вход разрешения работы СЕ,

6 - внешний вход синхронизации С.

Счетчик с сохранением количества единиц содержит внешние входы устройства D3, D2, D1, D0, внешние управляющие входы Y1, Y0, внешние выходы устройства Q3, Q2, Q1, Q0, внешний выход переноса CR, синхронные D-триггеры с входом СЕ разрешения работы 1₃, 1₂, 1₁ 1₀, мультиплексоры 2₃, 2₂, 2₁, 2₀, логический элемент ИЛИ-НЕ 3, двухразрядный двоичный счетчик 4, а также содержит внешний вход разрешения работы 5 и внешний вход синхронизации 6.

Внешние входы устройства D3, D2, D1, D0 соединены с нулевыми входами соответствующих мультиплексоров 2₃, 2₂, 2₁, 2₀.

Внешний вход разрешения работы 5 и внешний вход синхронизации 6 соединены с соответствующими одноименными входами СЕ разрешения работы и входами С синхронизации D-триггеров 1₃, 1₂, 1₁ 1₀ и двоичного счетчика 4.

Внешние управляющие входы Y1, Y0 соединены с соответствующими адресными входами S1, S0 мультиплексоров 2₃, 2₂, 2₁, 2₀ и подключены к первому и второму входам логического элемента ИЛИ-НЕ 3. Выход логического элемента ИЛИ-НЕ 3 соединен с входом R синхронной установки счетчика 4 в нулевое состояние, выход которого является внешним выходом переноса CR.

Выход D-триггера 1₃ соединен с первым и вторым информационными входами мультиплексора 2₂ и третьим информационным входом мультиплексора 2₁.

Выход D-триггера 1₂ соединен с первым информационным входом мультиплексора 2₁, а также соединен со вторым и с третьим информационными входами мультиплексора 2₀.

Выход D-триггера 1₁ соединен со вторым информационным входом мультиплексора 2₃, с третьим информационным входом мультиплексора 2₁, и с первым информационным входом мультиплексора 2₀.

Выход D-триггера 1₀ соединен с первым и третьим информационными входами мультиплексора 2₃ и со вторым информационным входом мультиплексора 2₁.

Выходы мультиплексоров 2₃, 2₂, 2₁, 2₀ соединены с входами D соответствующих D-триггеров 1₃, 1₂, 1₁ 1₀.

Выходы D-триггеров1₃, 1₂, 1₁ 1₀ являются соответствующими внешними выходами устройства Q3, Q2, Q1, Q0.

ПОДРОБНОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Принцип работы предлагаемого устройства состоит в следующем. Предлагаемый счетчик позволяет генерировать на внешних выходах Q счетчика N разрядные кодовые комбинации (N=4), в которых сохраняется заданное количество единиц К. При этом в устройстве можно задавать (программировать) единичные значения на соответствующих внешних входах данных D3, D2, D1, D0 (К≤N).

Предлагаемый счетчик реализован на четырех синхронных 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).

Предлагаемый счетчик работает следующим образом. Алгоритм работы счетчика заключается в следующем.

Перед началом работы, в режиме параллельной загрузки (Υ1=0, Υ0=0), на внешних входах D3, D2, D1, D0 задается начальное значение кода, содержащее К единиц. Запись в D-триггеры 1₃, 1₂, 1₁ 1₀ проводится по синхросигналу С на внешнем входе 6 при единичном значении сигнала разрешения работы СЕ на внешнем входе 5. Одновременно формируется единичное значение на выходе логического элемента ИЛИ-НЕ 3, которое передается на вход R счетчика 4, по которому осуществляется синхронная установка в нулевое состояние счетчика 4.

Далее на управляющих входах 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 также продолжит счет с текущего значения.

Кроме того, в процессе работы перед очередным синхросигналом С можно задать новое требуемое значение кода на внешних входах D3, D2, D1, D0 содержащее К единиц и установить режим параллельной загрузки (Y1=0, Υ0=0), при котором значение кода будет загружено в D-триггеры 1₃, 1₂, 1₁ 1₀ по синхросигналу С на внешнем входе 6 и при этом одновременно осуществляется синхронная установка в нулевое состояние счетчика 4.

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

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

Счетчик с сохранением количества единиц содержит внешние входы устройства D3, D2, D1, D0, внешние управляющие входы Y1, Y0, внешние выходы устройства Q3, 02, Q1, Q0, внешний выход переноса CR, синхронные D-триггеры с входом СЕ разрешения работы 1₃, 1₂, 1₁, 1₀, мультиплексоры 2₃, 2₂, 2₁, 2₀, логический элемент ИЛИ-НЕ 3, двухразрядный двоичный счетчик 4, а также содержит внешний вход разрешения работы 5 и внешний вход синхронизации 6,

причем внешние входы устройства D3, D2, D1, D0 соединены с нулевыми входами соответствующих мультиплексоров 2₃, 2₂, 2₁, 2₀,

внешний вход разрешения работы 5 и внешний вход синхронизации 6 соединены с соответствующими одноименными входами СЕ разрешения работы и входами С синхронизации D-триггеров 1₃, 1₂, 1₁, 1₀ и двоичного счетчика 4,

внешние управляющие входы Y1, Y0 соединены с соответствующими адресными входами S1, S0 мультиплексоров 2₃, 2₂, 2₁, 2₀ и подключены к первому и второму входам логического элемента ИЛИ-НЕ 3, выход которого соединен с входом R синхронной установки счетчика 4 в нулевое состояние, выход которого является внешним выходом переноса CR,

кроме того, выход D-триггера 1₃ соединен с первым и вторым информационными входами мультиплексора 2₂ и третьим информационным входом мультиплексора 2₁,

выход D-триггера 1₂ соединен с первым информационным входом мультиплексора 2₁, а также соединен со вторым и с третьим информационными входами мультиплексора 2₀,

выход D-триггера 1₁ соединен со вторым информационным входом мультиплексора 2₃, с третьим информационным входом мультиплексора 2₂, и с первым информационным входом мультиплексора 2₀,

выход D-триггера 1₀ соединен с первым и третьим информационными входами мультиплексора 2₃ и со вторым информационным входом мультиплексора 2₁,

причем выходы мультиплексоров 2₃, 2₂, 2₁, 2₀ соединены с входами D соответствующих D-триггеров 1₃, 1₂, 1₁, 1₀, выходы которых являются соответствующими внешними выходами устройства Q3, Q2, Q1, Q0.