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

 

1. ГЕНЕРАТОР ДВОИЧНЫХ ЧИСЕЛ , содержащий генератор импульсов, распределитель импульсов, два регистра сдвига, сумматор, вычитатель, первый блок сравнения, два коммутатора, три триггера, два элемента ИЛИ, семь элементов И и первый элемент задержки, причем выход генератора импульсов подключен к объединенным входам синхронизации распределителя импульсов, первого, второго регистров сдвига и первого блока сравнения, выход сумматора подключен к информационному входу первого регистра сдвига, выход п-го разряда распределителя импульсов, где п - количество разрядов двоичного числа, подключен к объединенным входам сброса первого и второго триггеров, первому входу первого элемента И и входу первого элемента задержки, выход которого подключен к входу сброса первого блока сравнения, выход первого регистра сдвига подключен к первому информационному входу сумматора , второй информационный вход которого подключен к выходу второго элемента И, вход установки первого триггера подключен к выходу третьего элемента И, первый и второй входы которого подключены соответственно к выходу признака равенства первого блока сравнения и выходу первого элемента И соответственно, прямой выход первого триггера подключен к первому входу четвертого элемента И, выход которого подключен к выходу генер ;тора двоичных чисел, прямой выход второго триггера подключен к первому входу пятого элемента И, прямой выход третьего триггера подключен к первому входу второго элемента И, отличающийся тем, что, с целью расширения области применения за счет генерирования последовательности чисел, для которых число два является примитивным элементом в поле Галуа. в него введены генератор одиночных импульсов, второй и третий блоки сравнения и второй элемент задержки, причем выход первого регистра сдвига подключен к первому информационному входу первого блока сравнения, выход второго регистра сдвига подключен к второму входу пятого элемента И и первому входу первого Q S элемента ИЛИ, выход которого подключен (Л к первому информационному входу первого коммутатора, выход которого через второй элемент задержки подключен к информационному входу второго регистра сдвига и первому информационному входу второго блока сравнения, первый вход шестого элемента И и управляюш,ий вход первого to коммутатора объединены и подключены к прямому выходу второго триггера, выход генератора одиночных импульсов подключен к второму входу первого элемента ИЛИ и оо ю входу установки третьего триггера, инверсный выход которого подключен к объединенным управляющим входам первого и второго регистров сдвига, выходы с первого по п-й распределителя импульсов подключены через второй коммутатор к входам, второго элемента ИЛИ, выход которого подключен к объединенным второму информационному входу первого блока сравнения, второму информационному входу второго блока сравнения, второму входу четвертого элемента И, второму входу шестого элемента И, выходы пятого и шестого элементов И подключены соответственно к входу уменьшаемого и входу вычитаемого вычитателя.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 G 06 F 1/02

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

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3776964/24-24 (22) 27.07.84 (46) 30.12.85. Бюл. № 48 (71) Ордена Ленина институт кибернетики им. В. М, Глушкова АН УССР (72) В. Л. Баранов и Е. А. Смичкус (53) 681.325 (088.8) (56) Авторе:.ое свидетельство СССР № 647680, кл. G 06 F 1/02, 1979.

Авторское свидетельство СССР № 1062674, кл. G 06 F 1/02, 1983. (54) (57) 1. ГЕНЕРАТОР ДВОИЧНЫХ ЧИСЕЛ, содержащий генератор импульсов, распределитель импульсов, два регистра сдвига, сумматор, вычитатель, первый блок сравнения, два коммутатора, три триггера, два элемента ИЛИ, семь элементов И и первый элемент задержки, причем выход генератора импульсов подключен к объединенным входам синхронизации распределителя импульсов, первого, второго регистров сдвига и первого блока сравнения, выход сумматора подключен к информационному входу первого регистра сдвига, выход п-го разряда распределителя импульсов, где п — количество разрядов двоичного числа, подключен к объединенным входам сброса первого и второго триггеров, первому входу первого элемента И и входу первого эле- мента задержки, выход которого подключен к входу сброса первого блока сравнения, выход первого регистра сдвига подключен к первому информационному входу сумматора, второй информационный вход которого подключен к выходу второго элемента И, вход установки первого триггера подключен к выходу третьего элемента И, первый и второй входы которого подключены соответственно к выходу признака равенства первого блока сравнения и выходу первого элемента И соответственно, прямой выход первого триггера подключен к первому входу четвертого элемента И, выход которого

„„SU„„1201827 A подключен к выходу генератора двоичных чисел, прямой выход второго триггера подключен к первому входу пятого элемента И, прямой выход третьего триггера подключен к первому входу второго элемента И, отличающийся тем, что, с целью расширения области применения за счет генерирования последовательности чисел, для которых число два является примитивным элементом в поле Галуа, в него введены генератор одиночных импульсов, второй и третий блоки сравнения и второй элемент задержки, причем выход первого регистра сдвига подключен к первому информационному входу первого блока сравнения, выход второго регистра сдвига подключен к второму входу пятого элемента И и первому входу первого © элемента ИЛИ, выход которого подключен к первому ииформаииоииому входу первогО (/) коммутатора, выход которого через второй элемент задержки подключен к информа- С„ ционному входу второго регистра сдвига и первому информационному входу второго Я блока сравнения, первый вход шестого элемента И и управляющий вход первого

Фв коммутатора объединены и подключены к прямому выходу второго триггера, выход („) генератора одиночных импульсов подключен в к второму входу первого элемента ИЛИ и входу установки третьего триггера, инверсный выход которого подключен к объединенным управляющим входам первого и второго регистров сдвига. выходы с первого по и-й распределителя импульсов подключены через второй коммутатор к входам. второго элемента ИЛИ, выход которого под-. ключен к объединенным второму информа- ) ционному входу первого блока сравнения, второму информационному входу второго блока сравнения, второму входу четвертого элемента И, второму входу шестого элемента И, выходы пятого и шестого элементов И подключены соответственно к входу уменьшаемого и входу вычитаемого вычитателя, 1201827 выход которого подключен к объединенным второму информационном входу первого коммутатора и первому информационному входу третьего блока сравнения, выход признака превышения второго блока сравнения подключен к первому входу седьмого элемента И, второй вход которого подключен к входу сброса второго триггера, вход установки которого подключен к выходу седьмого элемента И, второй вход второго элемента И объединен с вторым информационным входом третьего блока сравнения и подключен к первому выходу распределителя импульсов, и-й выход которого подключен к входу синхронизации генератора одиночных импульсов, управляющий вход которого подключен к входу запуска генератора двоичных чисел, выход признака равенства третьего блока сравнения подключен к второму входу первого элемента И, выход которого подключен к входу сброса третьего триггера, входы синхронизации второго и третьего блоков сравнения объединены и подключены к выходу генератора импульсов, входы сброса второго и третьего блоков сравнения объединены и подключены к выходу первого элемента задержки, установочные входы первого и второго регистров сдвига подключены к входу обнуления генератора двоичных чисел.

Изобретение относится к автоматике и вычислительной технике и предназначено для генерирования простых чисел, для которых число два является примитивным элементом в поле Галуа.

Цель изобретения — расширение области применения генератора двоичных чисел.

На фиг. 1 изображена структурная схема предлагаемого генератора двоичных чисел; на фиг. 2 — структурная схема блока сравнения.

Генератор двоичных чисел (фиг. ) содержит генератор 1 импульсов, распределитель 2 импульсов, регистры 3 и 4 сдвига, сумматор 5, вычитатель 6, блоки 7 — 9 сравнения, коммутаторы 10 и l I, триггеры 2 — 14, элементы ИЛИ 15 и 16, генератор 17 одиночных импульсов, элементы И 18 — 24, элементы 25 и 26 задержки, вход 27 запуска устройства, информационный выход 28 устройства.

Блок сравнения (фиг. 2) содержит J-Ктриггеры 29 и 30, элемент ИЛИ-НЕ 31, элементы И 32 и ЗЗ, элементы HE 34 и 35, два информационных входа 36 и 37, вход

38 сброса, вход 39 синхронизации, выход 40

2. Генератор по п. 1, отличающийся тем, что блок сравнения содержит два J-К-триггера, элемент ИЛИ-НЕ, два элемента И, два элемента НЕ, причем первый информационный вход блока подключен к первому входу первого элемента И и через первый элемент НЕ к первому входу второго элемента И, второй информационный вход блока подключен к второму входу второго элемента И и через второй элемент HE к второму входу первого элемента И, выход которого подключен к J-входу первого

J-К-триггера и К-входу второго J-К-триггера, выход второго элемента И подключен к J-входу второго J-К-триггера и

К-входу первого триггера, входы синхронизации обоих J-К-триггеров объединены и подключены к входу синхронизации блока, входы сброса обоих J-К-триггеров, объеди. нены и подключены к входу сброса блока, прямой выход первого J-К-триггера подключен к первому входу элемента ИЛИ-НЕ и является также выходом признака превышения блока, прямой выход второго J-Ктриггера подключен к второму входу элемента ИЛИ-НЕ и является также выходом признака принижения блока, выход элемента ИЛИ-НЕ подключен к выходу признака равенства блока. признака превышения, выход 41 признака равенства и выход. 42 признака принижения.

Генератор двоичных чисел работает следующим образом.

Генератор 1 импульсов вырабатывает последовательность тактовых импульсов частоты f, из которой п-разрядный распределитель 2 импульсов формирует и последователь; ностей импульсов частоты f/ï и сдвинутых друг относительно друга на время 1/f. С помощью коммутатора 11, выполненного в виде клавишного переключателя или в виде параллельного набора электронных ключей, управляемых внешними сигналами, задают двоичный код простого числа, подключая в единичных разрядах кода выход соответствующего разряда распределителя 2 импульсов к входам элемента ИЛИ 16. На выходе элемента ИЛИ 16 формируется последовательный двоичный код простого числа А, который периодически генерируется в течение времени и/f.

В исходном состоянии триггеры 12 — 14 находятся в нулевом состоянии. Триггеры 12 и 13 устанавливаются в нулевое состояние импульсами и-го разряда распределителя 2

1201827 импульсов, а триггер 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/f) в регистр 4 сдвига и в течение и тактов под действием тактовых импульсов генератора 1 импульсов записывает в регистр 4 сдвига двоичный код начального числа Ар = 1. В следующие п тактов начальный двоичный код 00...01 под действием тактовых импульсов генератора 1 импульсов сдвигается с выхода регистра 4 сдвига, содержащего и разрядов, и через элемент ИЛИ 15, коммутатор 10 и элемент 26 задержки вновь записывается в регистр 4 сдвига в виде двоичного кода 00...010

5 (А = 2), так как элемент 26 задержки сдвигает последовательный двоичный код за время и тактов на один разряд в сторону старших разрядов, т.е. выполняет функцию умножения числа А на два. В дальнейшем за время каждых п тактов последовательный двоичный код регистра 4 сдвига увеличивается в два раза. В это время блок 8 сравнения каждые и тактов сравнивает текущее значение числа А„, — — 2AL, формируемое на выходе элемента 26 задержки с заданным простым числом, формируемым на выходе элемента ИЛИ 16. Если A;+q N, то на выходе блока 8 сравнения действует нулевой сигнал, элемент И 24 закрыт и триггер 13 сохраняет нулевое состояние.

Как только текущее значение числа А; превысит заданное значение простого числа N (A; +< N) на выходе признака превышения блока 8 сравнения формируется единичный сигнал, который открывает элемент И 24. Импульс п-го разряда распредер лителя 2 импульсов проходит через элемент

И 24 и устанавливает триггер 13 в единичное состояние, в котором находится п тактов и сбрасывается в нулевое состояние следующим импульсом п-го разряда распределителя 2 импульсов. Единичный сигнал прямого выхода триггера 13 открывает элементы

И 22 и 23, а также переключает коммутатор

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

Вычитатель 6 выполняет последовательное вычитание из двоичного кода числа А двоичный код простого числа N, а последовательный двоичный код разности Ai, — N с выхода вычитателя 6 записывается, начиная с младшего разряда, через коммутатор 10 и

40 элемент 26 задержки в регистр 4 сдвига под действием тактовых импульсов генератора 1 импульсов. Блок 9 сравнения сравнивает последовательный двоичный код разности

А — N с константой единицы, которая зада4 ется импульсом первого разряда распределителя 2 импульсов. Если А; — Njp то на выходе блока 9 сравнения действует нулевой сигнал и устройство продолжает работать аналогичным образом, но с нччального числа в регистре 4 сдвига, равного 2

so (А — N), так как в процессе сдвига на один разряд элементом 26 задержки код А1 — N увеличился вдвое. Если А; — N = 1, то на выходе признака равенства блока 9 сравнения формируется единичный сигнал, который открывает элемент И 18. Импульс п-го разряда распределителя 2 импульсов через элемент И 18 устанавливает триггер 14 в нулевое состояние.

1201827

Если в это время В; = N и на выходе признака равенства блока 7 сравнения действует единичный сигнал, то элемент И 20 открывается и импульс, действующий на выходе элемента И 18, проходит также через элемент И 20 и устанавливает триггер 12 в единичное состояние, в котором он будет находиться п тактов и сбрасывается в нулевое состояние следующим импульсом и-го разряда распределителя 2 импульсов.

Единичный сигнал прямого выхода триггера !2 открывает элемент И 21, через который последовательный двоичный код заданного простого числа N поступает на выход 28 устройства, так как в случае А» — N = 1 и

Bi = М заданное простое число N обладает !5 дополнительным свойством, которое заключается в том, что для данного простого числа Nчисло 2 является при,митивным элементом в поле », (поле Галуа). После генерации двоичного кода простого числа для которого число два является примитивным элементом в поле Галуа, устройство возвращается в исходное состояниее, так как триггеры 12 — 14 находятся в нулевом состоянии, а регистры 3 и 4 устанавливаются в нулевое состояние по управляющему сигналу инверсного выхода триггера 14.

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

30 кода простого числа и запуска устройства по входу 27.

В процессе работы устройства возможен случай, когда при А» — — N = 1, В; 7 N В этом случае на выходе блока 7 сравнения действует нулевой сигнал, блокирующий элемент И 20, триггер !2 сохранит нулевое состояние, в котором элемент И 21 блокируется. так как в случае А; — N = 1, В; 4 N для заданного на коммутаторе 11 простого числа число 2 не является примитивным элементом в поле Галуа.

Блоки 7 — 9 сравнения (фиг. 2) работают следующим образом.

В конце каждого шага вычислений триггеры 29 и 30 устанавливаются в нулевое состояние сигналом, действующем на входе

38 сброса.

По импульсам синхронизации генератора 1 импульсов, действующих на входе 39 синхронизации, на информационные входы 36 и 37 поступают, начиная с младших разрядов, последовательные двоичные коды двух сравниваемых величин Х и Y. Если коды младших разрядов таковы, что Х = 1, а Y =- О, то на выходе элемента И 33 сформируется единичный сигнал, который по тактовому импульсу, действующему по входу 39 синхронизации, установит по входу J триггер 30 в единичное состояние, так как на его К-входе действует нулевой сигнал выхода элемента И 32.

Если X =- О, à Y = 1, то на выходе элемента И 32 сформируется единичный сигнал, который по тактовому импульсу на входе 39 синхронизации устанавливает по входу J триггер 29 в единичное состояние, так как на его К-входе действует нулевой сигнал выхода элемента И 33.

Если Х = 1, Y = 1, то элементы И 32 и 33 блокируются нулевыми сигналами элементов НЕ 34 и 35 соответственно и триггеры 29 и 30 сохраняют нулевое состояние.

В этом случае на выходе элемента ИЛИНЕ 31 из нулевых сигналов прямых выходов триггеров 29 и 30 формируется единичный сигнал, поступающий на выход 41 признака равенства.

Аналогичным образом последовательно во времени сравниваются все разряды последовательных двоичных кодов Х и У, после сравнения последнего разряда которых на одном из выходов 40 — 42 формируется единичный сигнал, если Х, У, Х = Y или Х У соот ветст ве ни о.

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

1201827

Фиг /

Фиг о

Составитель С. Курош

Редактор Ю. Середа Техред И. Верес Корректор Л. Пилипенко

Заказ 8091/49 Тираж 709 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4