Генератор двоичных чисел

)3ЬйЬ,:)11;1 Р 1;,ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Ордена Ленина институт киберим. В. М, Глушкова АН УССР(54) (57) 1. ГЕНЕРАТОР ДВОИЧНЫХ ЧИСЕЛ, содержащий генератор импульсов, распределитель импульсов, два регистра сдвига, сумматор, вычитатель, первый блок сравнения, два коммутатора, три триггера, два элемента ИЛИ, семь элементов И и первый элемент задержки, причем выход генератора импульсов подключен к объединенным входам синхронизации распределителя импульсов, первого, второго регистров сдвига и первого блока сравнения, выход сумматора подключен к информационному входу первого регистра сдвига, выход и-го разряда распределителя импульсов, где п - количество разрядов двоичного числа, подключен к объединенным входам сброса первого и второго триггеров, первому входу первого элемента И и входу первого эле. мента задержки, выход которого подключен к входу сброса первого блока сравнения, выход первого регистра сдвига подключен к первому информационному входу сумматора, второй информационный вход которого подключен к выходу второго элемента И, вход установки первого триггера подключен к выходу третьего элемента И, первый и второй входы которого подключены соответственно к выходу признака равенства первого блока сравнения и выходу первого элемента И соответственно, прямой выход первого триггера подключен к первому входу четвертого элемента И, выход которого подключен к выходу генератора двоичных чисел, прямой выход второго триггера подключен к первому входу пятого элемента И, прямой выход третьего триггера подключен к первому входу второго элемента И, отличающийся тем, что, с целью расширения области применения за счет генерирования последовательности чисел, для которых число два является примитивным элементом в поле Галуа, в него введены генератор одиночных импульсов, второй и третий блоки сравнения и второй элемент задержки, причем выход первого регистра сдвига подключен к первому информационному входу первого блока сравнения, выход второго регистра сдвига подключен к второму входу пятого элемента И и первому входу первогоэлемента ИЛИ, выход которого подключен к первому информационному входу первогО Я коммутатора, выход которого через второй элемент задержки подключен к информа- С ционному входу второго регистра сдвига и первому информационному входу второго Я блока сравнения, первый вход шестого элемента И и управляющий вход первого3 авв коммутатора объединены и подключены к прямому выходу второго триггера, выход С ) генератора одиночных импульсов подключен ювао к второму входу первого элемента ИЛИ и входу установки третьего триггера, инвер.сный выход которого подключен к объединенным управляющим входам первого и второго регистров сдвига. выходы с первого по п-й распределителя импульсов подключены через второй коммутатор к входам, второго элемента ИЛИ, выход которого подключен к объединенным второму информа- )р ционному входу первого блока сравнения, второму информационному входу второго блока сравнения, второму входу четвертого элемента И, второму входу шестого элемента И, выходы пятого и шестого элементов И подключены соответственно к входу уменьшаемого и входу вычитаемого вычитателя,1201827 выход которого подключен к объединенным второму информационному входу первого коммутатора и первому информационному входу третьего блока сравнения, выход признака превышения второго блока сравнения подключен к первому входу седьмого элемента И, второй вход которого подключен к входу сброса второго триггера, вход установки которого подключен к выходу седьмого элемента И, второй вход второго элемента И объединен с вторым информационным входом третьего блока сравнения и подключен к первому выходу распределителя импульсов, и-й выход которого подключен к входусинхронизации генератора одиночных импульсов, управляющий вход которого подключен к входу запуска генератора двоичных чисел, выход признака равенства третьего блока сравнения подключен к второму входу первого элемента И, выход которого подключен к входу сброса третьего триггера, входы синхронизации второго и третьего блоков сравнения объединены и подключены к выходу генератора импульсов, входы сброса второго и третьего блоков сравнения объе. динены и подключены к выходу первого элемента задержки, установочные входы первого и второго регистров сдвига подключены к входу обнуления генератора двоичных чисел. Изобретение относится к автоматике и вычислительной технике и предназначено для генерирования простых чисел, для которых число два является примитивным элементом в поле Галуа.Цель изобретения - расширение области применения генератора двоичных чисел.На фиг, 1 изображена структурная схема предлагаемого генератора двоичных чисел; на фиг. 2 - структурная схема блока сравнения.Генератор двоичных чисел (фиг.) содержит генератор 1 импульсов, распределитель 2 импульсов, регистры 3 и 4 сдвига, сумматор 5, вычитатель 6, блоки 7 - 9 сравнения, коммутаторы 10 и 11, триггеры2 - 14, элементы ИЛИ 15 и 16, генератор 17 одиночных импульсов, элементы И 18 - 24, элементы 25 и 26 задержки, вход 27 запуска устройства, информационный выход 28 устройства.Блок сравнения (фиг. 2) содержит 3-К- триггеры 29 и 30, элемент ИЛИ-НЕ 31, элементы И 32 и ЗЗ, элементы НЕ 34 и 35, два информационных входа 36 и 37, вход 38 сброса, вход 39 синхронизации, выход 40 5 1 О 15 20 2. Генераторпо п. 1, отличающийся тем, что блок сравнения содержит два 3-К-триг. гера, элемент ИЛИ-НЕ, два элемента И, два элемента НЕ, причем первый информационный вход блока подключен к первому входу первого элемента И и через первый элемент НЕ к первому входу второго элемента И, второй информационный вход блока подключен к второму входу второго элемента И и через второй элемент НЕ к второму входу первого элемента И, выход которого подключен к 3-входу первого 3-К-триггера и К-входу второго 3-К-триггера, выход второго элемента И подключен к 3-входу второго 3-К-триггера и К-входу первого триггера, входы синхронизации обоих 3-К-триггеров объединены и подключены к входу синхронизации блока, входы сброса обоих 3-К-триггеров, объеди. нены и подключены к входу сброса блока, прямой выход первого 3-К-триггера подключен к первому входу элемента ИЛИ-НЕ и является также выходом признака превышения блока, прямой выход второго 3-К- триггера подключен к второму входу элемента ИЛИ-НЕ и является также выходом признака принижения блока, выход элемента ИЛИ-НЕ подключен к выходу признака равенства блока. признака превышения, выход 41 признака равенства и выход 42 признака принижения.Генератор двоичных чисел работает следующим образом.Генератор 1 импульсов вырабатывает пос. ледовательность тактовых импульсов частоты 1, из которой и-разрядный распределитель 2 импульсов формирует и последователь; ностей импульсов частоты 1/п и сдвинутых друг относительно друга на время 1 й, С помощью коммутатора 11, выполненного в виде клавишного переключателя или в виде параллельного набора электронных ключей, управляемых внешними сигналами, задают двоичный код простого числа, подключая в единичных разрядах кода выход соответствующего разряда распределителя 2 импульсов к входам элемента ИЛИ 16. На выходе элемента ИЛИ 16 формируется последовательный двоичный код простого числа А, который периодически генерируется в течение времени иЛ.В исходном состоянии триггеры 12 - 14 находятся в нулевом состоянии. Триггеры 12 и 13 устанавливаются в нулевое состояние импульсами и-го разряда распределителя 2импульсов, а триггер 14 устанавливается в .нулевое состояние в предыдущем цикле работы устройства. Регистры 3 и 4 сдвига находятся в нулевом состоянии, так как на их входах установки действуют нулевые сигналы, а на их управляющие входы поступает единичный сигнал инверсного выхода триггера 14.Запуск генератора двоичных чисел осуществляют подачей сигнала логической единицы на запускающий вход 27 устройства, который соединен с управляющим входом генератора 17 одиночных импульсов. Из последовательности импульсов п-го разряда распределителя 2 импульсов генератор 17 одиночных импульсов выделяет одиночный импульс, который устанавливает триггер 14 в единичное состояние. Единичный сигнал прямого выхода триггера 14 открывает элемент И 19, через который на вход сумматора 5 начинает поступать последовательность импульсов первого разряда распределителя 2 импульсов. Регистр 3 сдвига, содержащий п разрядов, совместно с сумматором 5 образует счетчик импульсов, действующих на выходе элемента И 19, За время и тактов двоичный код, сдвигаемый с выхода регистра 3 сдвига под действием тактовых импульсов генератора 1 импульсов, увеличивается на единицу младшего разряда, так как сумматор 5 прибавляет к нему в младшем разряде импульс первого разряда распределителя 2 импульсов, а последовательный двоичный код результата суммирования, начиная с младшего разряда, последовательно записывается под действием тактовых импульсов генератора 1 импульсов в регистр 3 сдвига,Блок 7 сравнения сравнивает каждые и тактов последовательные двоичные коды А, действующего на выходе элемента ИЛИ 16, и числа В; формируемого на выходе регистра 3 сдвига.Элемент 25 задержки на длительность тактового импульса формирует из последовательности импульсов и-го разряда распределителя 2 импульсов последовательность импульсов, определяющих конец каждого шага вычислений и сбрасывающих в конце каждого шага блоки 7 - 9 сравнения в исходное состояние.Одиночный импульс с выхода генератора 17 одиночных импульсов после запуска устройства поступает также через элемент ИЛИ 15, коммутатор 10 и элемент 26 задержки на такт (на время 1 Д) в регистр 4 сдвига и в течение и тактов под действием тактовых импульсов генератора 1 импульсов записывает в регистр 4 сдвига двоичный код начального числа Ар = 1. В следующие п тактов начальный двоичный код 0001 под действием тактовых импульсов генератора 1 импульсов сдвигается с выхода регистра 4 сдвига, содержащего и разрядов, и через элемент ИЛИ 15, коммутатор 10 и элемент 26 задержки вновь записывается в регистр 4 сдвига в виде двоичного кода 00010 5(А 4 = 2), так как элемент 26 задержки сдвигает последовательный двоичный код за время и тактов на один разряд в сторону старших разрядов, т.е. выполняет функцию умножения числа А на два. В дальнейшем за время каждых п тактов последовательный двоичный код регистра 4 сдвига увеличивается в два раза. В это время блок 8 сравнения каждые и тактов сравнивает текущее значение числа А, -- 2 А, формируемое на выходе элемента 26 задержки с заданным простым числом, формируемым на выходе элемента ИЛИ 16. Если А; М, то на выходе блока 8 сравнения действует нулевой сигнал, элемент И 24 закрыт и триггер 13 сохраняет нулевое состояние.Как только текущее значение числа А;превысит заданное значение простого числа М (Аи Х) на выходе признака превышения блока 8 сравнения формируется единичный сигнал, который открывает элемент И 24. Импульс п-го разряда распредер лителя 2 импульсов проходит через элементИ 24 и устанавливает триггер 13 в единичное состояние, в котором находится п тактов и сбрасывается в нулевое состояние следующим импульсом п-го разряда распределителя 2 импульсов. Единичный сигнал прямого выхода триггера 13 открывает элементы И 22 и 23, а также переключает коммутатор 10, через который выход вычитателя 6 подключается через элемент 26 задержки к информационному входу регистра 4 сдвига.Вычитатель 6 выполняет последовательное вычитание из двоичного кода числа А двоичный код простого числа М, а последовательный двоичный код разности А - М с выхода вычитателя 6 записывается, начиная с младшего разряда, через коммутатор 10 и 40 элемент 26 задержки в регистр 4 сдвига поддействием тактовых импульсов генератора 1 импульсов. Блок 9 сравнения сравнивает последовательный двоичный код разности А - Х с константой единицы, которая зада ется импульсом первого разряда распределителя 2 импульсов, Если А; - Щ то на выходе блока 9 сравнения действует нулевой сигнал и устройство продолжает работать аналогичным образом, но с нччального числа в регистре 4 сдвига, равного 2 50 (А - М), так как в процессе сдвига на одинразряд элементом 26 задержки код А 1 - Х увеличился вдвое. Если А; - М = 1, то на выходе признака равенства блока 9 сравнения формируется единичный сигнал, который открывает элемент И 18. Импульс п-го разряда распределителя 2 импульсов через элемент И 18 устанавливает триггер 14 в нулевое состояние.Если в это время В; = М и на выходе признака равенства блока 7 сравнения действует единичный сигнал, то элемент И 20 открывается и импульс, действующий на выходе элемента И 18, проходит также че рез элемент И 20 и устанавливает триггер 12 в единичное состояние, в котором он будет находиться п тактов и сбрасывается в нулевое состояние следующим импульсом и-го разряда распределителя 2 импульсов. Единичный сигнал прямого выхода триггера 2 открывает элемент И 21, через который последовательный двоичный код заданного простого числа М поступает на выход 28 устройства, так как в случае А; - М = 1 и В = М заданное простое число М обладает 5 дополнительным свойством, которое заключается в том, что для данного простого числа М число 2 является примитивным элементом в поле 2 (поле Галуа). После генерации двоичного кода простого числа для которого число два является примитивным элементом в поле Галуа, устройство возвращается в исходное состояниее, так как триггеры 12 - 14 находятся в нулевом состоянии, а регистры 3 и 4 устанавливаются в нулевое состояние по управляющему сигналу 25 инверсного выхода триггера 14.Следующий цикл генерации двоичных чисел с определенными свойствами осуществляется аналогичным образом после установки на коммутаторе 11 другого двоичного30 кода простого числа и запуска устройства по входу 27.В процессе работы устройства возможен случай, когда при А = Х = 1, В;М. В этом случае на выходе блока 7 сравнения действует нулевой сигнал, блокирующий элемент И 20, триггер 2 сохранит нулевое состояние, в котором элемент И 21 блокируется, так как в случае А; - М = 1, В;Я для заданного на коммутаторе 11 простого числа число 2 не является примитивным элементом в поле Галуа.40Блоки 7 - 9 сравнения (фиг. 2) работают следующим образом. В конце каждого шага вычислений триггеры 29 и 30 устанавливаются в нулевоесостояние сигналом, действующем на входе38 сброса,По импульсам синхронизации генератора 1 импульсов, действующих на входе 39синхронизации, на информационные входы 36 и 37 поступают, начиная с младшихразрядов, последовательные двоичные кодыдвух сравниваемых величин Х и У, Если коды младших разрядов таковы, что Х = 1,а У =- О, то на выходе элемента И 33 сформируется единичный сигнал, который потактовому импульсу, действующему по входу 39 синхронизации, установит по входу 1триггер ЗО в единичное состояние, так как наего К-входе действует нулевой сигнал выхода элемента И 32.Если Х =- О, а У = 1, то на выходе элемента И 32 сформируется единичный сигнал, который по тактовому импульсу на входе 39 синхронизации устанавливает по входутриггер 29 в единичное состояние, таккак на его К-входе действует нулевой сигналвыхода элемента И 33.Если Х = 1, У =1, то элементы И 32и 33 блокируются нулевыми сигналами элементов НЕ 34 и 35 соответственно и триггеры 29 и 30 сохраняют нулевое состояние.В этом случае на выходе элемента ИЛИНЕ 31 из нулевых сигналов прямых выходовтриггеров 29 и 30 формируется единичныйсигнал, поступающий на выход 41 признакаравенства.Аналогичным образом последовательново времени сравниваются все разряды последовательных двоичных кодов Х и У, послесравнения последнего разряда которых наодном из выходов 40 - 42 формируется единичный сигнал, если Х, У, Х = У или Х(Усоответственно.В конце каждого шага вычислений триггеры 29 и 30 сбрасываются в нулевое состояние импульсом, поступающим с выходаэлемента 25 задержки на вход 38 сбросаблока сравнения.1201827 Фиг Государственного комитет ам изобретений и откры ва, Ж - 35, Раушская на Патент, г. Ужгород, ул. едактор Ю. Середааказ 8091/49ВНИИПИпо дел113035, Мосфилиал ППП Составитель С. Куедрен И. Вересираж 709 Корректор Л. ПилипенкГодпнсноеСССРийд. 4/5Проектная, 4