ГЕНЕРАТОР КОДОВЫХ КОМБИНАЦИЙ

Полезная модель относится к области вычислительной и криптографической техники и может быть использована в цифровых вычислительных устройствах для формирования полных кодовых последовательностей двоичных и недвоичных чисел, включая нулевые значения.
Известен генератор псевдослучайной последовательности с запрещенными комбинациями, содержащий генератор тактовых импульсов, реверсивный регистр сдвига, два сумматора по модулю два, два элемента И, коммутатор, элемент НЕ, источник управляющего сигнала, группу элементов задержки, группу элементов запрета, дешифратор и элемент ИЛИ [1]. Известный генератор позволяет генерировать кодовую последовательность двоичных чисел как в прямом, так и в обратном порядке, которая используется в системе тестового диагностирования цифровых устройств с учетом запрета заранее заданной тестовой комбинации.
Недостаток известного генератора псевдослучайной последовательности двоичных чисел с запрещенными комбинациями состоит в том, что начальное (исходное) состояние регистра сдвига не может быть нулевым. При нулевых начальных условиях регистра сдвига суммирование по модулю два последовательности 0, 0, …, 0, составленной только из двоичных «нулевых» чисел, приводит к тому, что на выходе этого сумматора по модулю два будут формироваться только нулевые сдвигающие импульсы для регистра сдвига и другие кодовые последовательности двоичных чисел на выходе генератора формироваться не будут, что свидетельствует об ограниченных функциональных возможностях известного генератора.
n
n
n
n
Наиболее близким к предлагаемому известным техническим решением является генератор псевдослучайных последовательностей, содержащий генератор тактовых импульсов, сумматор по модулю два и регистр сдвига, составленный из m последовательно соединенных между собой D-триггеров, а также n буферных элементов, n умножителей, нелинейный генератор, параллельный регистр коммутации, параллельный регистр обратной связи и параллельный регистр n разрядов [2]. За счет использования двух замкнутых цепочек регистров сдвига, в одну из которых включен сумматор по модулю два с n входами, а в другую замкнутую цепочку регистра сдвига подключен нелинейный генератор, обеспечивается генерация большого числа М - последовательностей двоичных чисел, которые повторяются через период, равный 2·(2-1). Отметим, что в типовом генераторе псевдослучайных последовательностей, который составлен из регистра сдвига, замкнутом через сумматор по модулю два, период повторения равен (2-1). Поэтому в прототипе формируется в 2 раз больше псевдослучайных последовательностей двоичных чисел, чем в других известных генераторах псевдослучайных чисел, при этом нулевая кодовая последовательность не формируется.
Недостаток прототипа состоит в том, что буферные элементы в схеме нелинейного генератора приводятся в исходное состояние («обнуляются») либо дополнительными управляющими сигналами или путем отключения электрического питания, что увеличивает время генерации псевдослучайной кодовой комбинации, кроме того, техническая реализация известного в прототипе генератора сложная и не формируется нулевая кодовая последовательность.
Целью полезной модели (техническим результатом) является расширение функциональных возможностей генерации кодовых комбинаций путем формирования полной псевдослучайной двоичной и недвоичной кодовой комбинации, включая нулевой недвоичный элемент, и повышение быстродействия генератора кодовых комбинаций за счет замены буферных элементов логическим элементом И на m входов.
m
Сущность полезной модели состоит в том, что, кроме известных и общих отличительных признаков, а именно: генератора тактовых импульсов, сумматора по модулю два и регистра сдвига, составленного из m последовательно соединенных между собой D-триггеров, предлагаемый генератор кодовых комбинаций содержит элемент ИЛИ на два входа, элемент И на m входов и дешифратор на m входов и 2 выходов, инверсные выходы всех m D-триггеров регистра сдвига подключены к m входам элемента И, выход которого связан с одним входом элемента ИЛИ, другой вход которого подключен к выходу m-го D-триггера и к одному входу сумматора по модулю два, другой вход которого соединен с выходом первого D-триггера, информационный вход которого подключен к выходу элемента ИЛИ, выходы m D-триггеров регистра сдвига подключены к m входам дешифратора.
m
Новизна полезной модели заключается в том, что генератор кодовых комбинаций содержит элемент ИЛИ на два входа, элемент И на m входов и дешифратор на m входов и 2 выходов, инверсные выходы всех m D-триггеров регистра сдвига подключены к m входам элемента И, выход которого связан с одним входом элемента ИЛИ, другой вход которого подключен к выходу m-го D-триггера и к одному входу сумматора по модулю два, другой вход которого соединен с выходом первого D-триггера, информационный вход которого подключен к выходу элемента ИЛИ, выходы m D-триггеров регистра сдвига подключены к m входам дешифратора, что обеспечивает расширение функциональных возможностей генерации двоичных и недвоичных кодовых комбинаций путем формирования кодовой комбинации, включая нулевой недвоичный элемент, и повышение быстродействия генератора кодовых комбинаций.
Схема генератора кодовых комбинаций представлена на фиг.1, таблица соответствия состояний элементов генератора приведена на фиг.2. На фиг.1 и 2 обозначено:
Т - D триггер, цепочка из m элементов которых образует m - разрядный регистр сдвига;
М2 - сумматор по модулю два;
G - генератор тактовых импульсов;
& - элемент И с m входами (многовходовый);
1 - элемент ИЛИ на два входа (двухвходовый);
R - асинхронный нулевой установочный вход D-триггера;
S - асинхронный единичный установочный вход D-триггера;
MUX - собирающая шина для предъявления двоичного кода с выходов D-триггеров;
m
DC - дешифратор на m входов и 2 выходов.
m
В исходном положении (статика) генератор кодовых комбинаций представляет собой замкнутую цепочку, составленную из m D-триггеров, сумматора М2 по модулю два и двухвходового элемента ИЛИ, один из входов которого подключен к выходу многовходового элемента И. Входы многовходового элемента И связаны с инверсными выходами m D-триггеров регистра сдвига, прямые выходы которого подсоединены к m входам дешифратора DC. Начальное состояние регистра сдвига нулевое, что выгодно отличает предлагаемый генератор от известных генераторов псевдослучайных чисел, в которых отсутствует нулевое исходное состояние регистра сдвига, тем, что предлагаемый генератор генерирует четное число кодовых комбинаций и все элементы недвоичного кода 2, включая нулевой, на выходе дешифратора. Нулевые начальные условия всех D-триггеров регистра сдвига устанавливаются с помощью управляющих сигналов, подаваемых на асинхронные нулевые установочные входы R. Все m D-триггеров регистра сдвига находятся в одинаковом состоянии. Их прямые выходы соответствуют «0» и подключены к собирающей шине MUX, а инверсные выходы всех D-триггеров отвечают состоянию «1».
Предлагаемый генератор кодовых комбинаций работает следующим образом.
При поступлении первого тактового (синхронизирующего) импульса с выхода генератора G на синхронизирующие входы С (Clock) всех D-триггеров регистра сдвига с инверсных выходов всех m этих D-триггеров регистра сдвига направляются импульсы, соответствующие сигналам «1», через многовходовый элемент И на один вход двухвходового элемента ИЛИ, на другой вход которого подается выходной импульс m-го D-триггера регистра сдвига, соответствующий сигналу «0». Двухвходовый элемент ИЛИ включается и его выходной сигнал «1» поступает на прямой информационный вход первого D-триггера регистра сдвига, под действием которого первый D-триггер переходит в другое устойчивое состояние, а именно: на прямом выходе формируется напряжение, соответствующее «1», а на инверсном выходе образуется «0». Выходной сигнал «1» первого D-триггера регистра сдвига поступает на один вход сумматора М2 по модулю два, на собирающую шину MUX и на первый вход дешифратора DC, который предъявляет на своем первом выходе нулевой элемент «0» недвоичного кода. Логический элемент И отключается, т.к. с инверсного выхода первого D-триггера регистра сдвига подается импульс «0», а с инверсных выходов всех остальных D-триггеров регистра сдвига поступают «1». На выходе элемента ИЛИ формируется перепад напряжения, который поступает на информационный вход первого D-триггера и переводит его в единичное состояние.
При поступлении второго тактового (синхронизирующего) импульса с выхода генератора G тактовых сигналов на синхронизирующие С входы всех D-триггеров регистра сдвига работа генератора кодовых комбинаций повторяется. Все D-триггеры сохраняют свое устойчивое состояние, кроме второго D-триггера, так как на их информационных входах находятся низкие потенциалы «0». К информационному входу второго D-триггера подключен выход сумматора по модулю два М2 с высоким потенциалом, соответствующим «1», поэтому под действием второго тактового импульса второй D-триггер сменил свое устойчивое состояние с «0» на «1». Таким образом, по окончании второго тактового импульса первый D-триггер сохранит свое устойчивое состояние «1», второй D-триггер перейдет в состояние «1», а все остальные D-триггеры регистра сдвига сохранят свое устойчивое состояние «0».
m
m
m
Третий тактовый импульс изменит состояния триггеров регистра сдвига следующим образом: первый триггер (Т1) сохранит положение «1», второй триггер (Т2) перейдет в состояние «0», Т3 в состояние «1», а остальные триггеры сохранят низкий уровень потенциала «0» на своих прямых выходах. При поступлении четвертого и последующих тактовых импульсов до m-ого работа генератора протекает аналогично ранее рассмотренному порядку, напряжение на выходе сумматора по модулю два М2 не изменяется. С приходом m-ого тактового импульса алгоритм суммирования элемента М2 изменяется, а именно: при поступлении на входы сумматора по модулю два М2 одинаковых символов «1» или «0» выходной сигнал сумматора М2 равен «0», при появлении разных сигналов на входах сумматора М2 его выходной сигнал равен «1». Сумматор по модулю два М2 обеспечивает известный псевдослучайный характер формирования последовательности двоичных чисел, число которых определяется по формуле 2-1. Предлагаемый генератор кодовых комбинаций формирует полную четную комбинацию двоичных символов n=2, включая нулевую позицию, и комбинацию недвоичных чисел на выходах дешифратора, включая нулевую позицию, в то время как известные типовые генераторы псевдослучайных комбинаций двоичных чисел формируют на одну комбинацию меньше, то есть 2-1 и всегда нечетное количество комбинаций, а нулевую недвоичную позицию не формируют. При переборах кодовых комбинаций криптографическому аналитику придется учитывать еще один возможный (нулевой) элемент кода, что повышает криптографическую защиту передачи конфиденциальной информации.
В качестве примера (фиг.2) рассмотрим порядок работы предлагаемого генератора с регистром сдвига, составленным из трех D-триггеров, когда m=3. В таблице на фиг.2 приведены состояния выходных потенциалов элементов схемы генератора в каждом такте (шаге) генератора тактовых импульсов.
3
Из таблицы видно, что, начиная с 9-го шага происходит повторение кодовых комбинаций. Таким образом, предлагаемый генератор обеспечивает максимально возможное число кодовых комбинаций 2=8.
Промышленная осуществимость полезной модели обосновывается тем, что в ней использованы известные в аналоге и прототипе узлы и элементы по своему прямому функциональному назначению. В организации-заявителе изготовлен макет устройства в 2013 году.
m
Положительный эффект (технический результат) от использования полезной модели состоит в том, что расширяются функциональные возможности генерации кодовых комбинаций путем формирования полной псевдослучайной двоичной и недвоичной кодовой комбинации, включая нулевой недвоичный элемент кода. В предлагаемом генераторе кодовых комбинаций используются все полученные 2 кодовые комбинации для шифрования при передаче двоичной последовательности чисел на передающей стороне и для дешифрации принятой двоичной последовательности чисел на приемной стороне системы передачи и приема данных без какого-либо остатка неиспользованных кодовых комбинаций, что свидетельствует о повышении не менее чем на 10…15% продуктивности генератора кодовых комбинаций в качестве характеристики его эффективной работы.
Кроме того, повышается не менее чем на 15…20% быстродействие генератора кодовых комбинаций за счет замены сложно управляемых буферных элементов в устройстве-прототипе на логический элемент И с m входами.
Источники информации
1. Патент RU 38510 на полезную модель «Генератор псевдослучайной последовательности с запрещенными комбинациями», МПК G06F 7/58, приоритет: 21.01.2004, авторы и патентообладатели: Афонский А.В., Белоглазов A.M. и др., (аналог).
2. Патент RU 2446444 на изобретение «Генератор псевдослучайных последовательностей», МПК G06F 7/58, приоритет: 12.11.2010, авторы: Захаров В.М., Зелинский Р.В. и др., патентообладатель: ГОУ ВПО Казанский ГТУ им. А.Н.Туполева, (прототип).