Генератор избыточных последовательностей чисел с произвольными начальными условиями

(504 6 ный комитет сссР ОБ етений и отн 1 ыт осуд действГО ДЕЛАМ ИЗ ЩЕ АНИЕ ИЗОБРЕТЕНИЯ детельствР 1/02,тельство6 Р 1/02,ССР1984 СЕ 1) 3795983/24-24(54) ГЕНЕРАТОР ИЗБЫТОЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ С ПРОИЗВОЛЬНЫМИ НАЧАЛЬНЫМИ УСЛОВИЯМИ(57) Изобретение относится к вычислительной технике и может быть использовано для получения обобщенныхизбыточных последовательностей чисел . Цель изобретения - расширениеФункциональных возможностей за счетвозможности генерирования избыточныхчисел о с параметрами ц=.2 и произвольными начальными условиями, Генератор содержит блок синхронизации,регистры, коммутатор, сумматор, элемент запрета, элемент ИЛИ, триггерсо счетным входом и элемент И, 2 ил2 табл,229749 Поспедовательности рядов (г,р)-чисел Значение параметра 21 34 55 12 93 9 1 2 3 4 61 2 3 4 7 1 О 1 1 2 4 7 13 24 44 81 491 1 1 2 4 7 12 24 37 69 Изобретение относится к вычисли тельной технике и может быть использовано для получения обобщенных избыточных последовательностей чисел,При построении ряда цифровых устройств необходимо генерировать послдовательности рядов (г,р)-чисел с произвольными начальными условиями и определяемые следующим рекуррентным соотношением: Р,= Р;. " 1 Р,,Р, =12 = -8 р+, =:х;р, = 2 ху 2 уэфюр 5р = С,1,;Фз = р + Зр+г, (1)где х - произвольное начальное условие; 2 Ог - максимальное количество единиц, находящихся в соседнихдвоичных разрядах числа иобразующих разрешенную г 1 уппу единиц; 25р - параметр, указывающий намаксимальное количество нулей между разрешенными группами единиц,Подставляя конкретные значения ги р в соотношение (1), при х, =1, получают табл, последовательностейрядов (г,р) чисел,Как видно из табл.1, при г:р= получают известный ряд чисел Фибоначчи,9при г=1 и р=1,2,3, - последователь 1ности чисел фибоначчи, при г=п, р=О -известную классическую двоичную последовательность,При г=2,3,4, , и р=1,2,3, получают последовательности обобщенных1 рядов (г,р)-чисел, используемых припостроении цифровых устройств, которые по быстродействию, диапазонупредставления чисел и помехоустойчивости занимают промежуточное положение между классическими и Фибоначчиевыми цифровыми устройствами.Для построения специализированныхустройств при помехоустойчивой обработке информации необходимо генерировать избыточные последовательности чисел с произвольными начальнымиусловиями, определяемые следующим рекуррентным соотношением:х ; ф =2) увэ Эс = 2,3,4Р,= 2 Р;., Р,+ -Р,1+1, 2 Ц+1, 3(1+1),где х, - произвольное начальное уеловие;ц - определяет алгоритм получения избыточной последовательности чисел.При х = 1 и ц=п йолучают двоичнуюпоследовательность, весовые коэффициенты которой равны степени двойки,1При х =1,2.2ци получают избыточные последовательности( -ксды), основой которых являютсяизбыточные позиционные системы счисления со смешанным основанием с=2и Ы =1,5 Такие системы счисления используют для построения специализированных устройств при помехоустойчивой обработке информации,Б табл.1 приведены некоторые избыточные последовательности (весовые коэффициенты) для 1=1,2,3,4.Таблица 11229749 4Продолжение табл. Значение па-Последовательности рядов , р,) -чисел раметра гР 1 1 1 1 2 4 7 30 34 2 1 1 2 4 8 15 29 1 1 1 2 4 8 151 12 4 8 1 1 2 4 8 16 31 08 208 43 90 28 52 56 28 15 60 120 235 4 1 1 1 1 2 4 8 16 31 60 117 1 1 1 2 4 8 16 31 60 1 2 4 8 16 32 64 128 255 г=п Значение параметрапри х =1 Последовательности ц-чисел 1 2 4 6 12 1836 54 108 162 1 2 4 8 12 24 48 72 144 288 1 2 4 8 16 32 64 128 255 Ч =п Цель изобретения - расширение об О ласти применения эа счет воэможности генерирования избыточных с 1-чисел с параметрами ц=2 и произвольными начальными условиями.На фиг, приведена структурная 45 схема предлагаемого устройства; на , фиг,2 - функциональная схема коммутатора,На схеме устройства приведены обозначения: р=2 - при генерировании последовательпостей избыточных р-чисел Фибоначчи с производственными началь. ными условиями; г=2, р - при генерировании последовательностей обобщенных избыточных (г,р)-чисел с про-иэвольными начальными условиями;ц 2 - при генерировании избыточных последовательностей ц-чисел. Генератор избыточных последовательностей чисел содержит блок 1 синхронизации, последовательно соединенные регистры 2- - 2-3, коммутатор 3, сумматор 4, элемент 5 запрета, элемент ИЛИ 6, триггер 7 со счетным входом, элемент И 8,Кроме того, первый.г-й информационные входы 3-4 - 3-5 коммутатора 3 соединены соответственно с информационными выходами регистров со второго по г-й и (г+р)-й, управляющий вход 3-1 коммутатора 3 соединен с третьим выходом 1-3 блока 1 синхронизации, второй выход. 1-2 которого соединен с первым синхрониэирующим входом 3-2 коммутатора 3.Второй синхронизирующий вход 3-3 коммутатора 3 соединен с выходом элемента1"29749 Т а б л и ц а 2 Номер группы3 2 д 1 3. 12 6 4 2 1 Р (Ч"2,х, 1) 18 1 5, асинхронизирующий выход 3-7 соединен с первым входом элемента ИЛИ. Информационный выход 3-6 коммутатора 3 соединен с информационным входом сумматора 4. Первый выход 1-1 блока 1 синхронизации соединен с синхронизирующими входами регистров 2-1 2-3, а четвертый выход 1-4 - с первым. входом элемента И 6. Неуправля- О емый информационный вход генератора служит для подачи кодовой комбина" ции начального условия х в регистр 2-1,Информационный выход 2-1 регистра является информационным выходом 15 генератора.Схема (фиг.2) содержит мультиплексор 9 иэ г многовходовых элементов И 9-1 - 9-г, элемент И 1 О, разрешающий работу устройства в режиме 2 О формирования (г,р)Ч ц последовательностей, глинии 11 задержки, предназначенной для последовательной во времени передачи содержимого второго,г-го и (г+р)-го регистров на 25 сумматор. Выход 3-7 г-й линии задержки является синхронизирующим выходом коммутатора 3, выход мультиплексора соединен с информационным выходом 3-6 коммутатора 3. Первый ин- ЗО формационный вход 3-4 коммутатора соединен с информационными входами элемента И 9-2, которые стробируются сигналами с выхода линии 11 задержки, г - информационный вход (второй)3-5 соединен с информационными входами 9-1 элемента И, которые стробируются синхронизирующими сигналом с входа 3-3 коммутатора. Синхрониэирующий вход 3-2 и управляющий вход 3-1 ком О мутатора соединены с соответствующими входами элемента И 10, выход которого соединен с выходом линии 11 задержки.Генерирование последовательности чисел Фибоначчи,(при г =1 и р=1,2 ) осуществляется известным способом,Номер позициив группе "1 при этом в работе участвуют регистры2-1 - 2-3, количество которых определяется величиной (р+1), коммутатор 3,обеспечивающий передачу содержимого(р+1)-го регистра 2-3 на сумматор 4посредством элемента И 9-1 и единичного выхода элемента 5 запрета. Вэтом случае на третьем выходе 1-3 блока синхронизации, определяющем режимработы (.,р) М 1, будет нулевой сигнал и, следовательно, нулевой сигчална выходе элемента И 8. В результатеэтого триггер 7 сохранит нулевое состояние, установленное по сигналу1, 1Пуск , и на инверсном выходе элемента 5 запрета установится сигнал,разрешающий прохождение синхроимпулъ сов (СИ) на синхронизирующий вход3-3 коммутатора 3.На фиг, приведена функциональнаясхема генератора чисел Фибона" чи дляг+ и р=2,Генерирование последовательностсйдпя значений параметров г=2,3, ир=1 производится при подаче на вход3- коммутатора 3 единичного значениясигнала (г,р)с с выхода 1-3 блокасинхронизации, При этом триггер 7 также сохраняет нулевое состояние, таккак с выхода 1-4 блока синхронизации,задающего режим работы и формированияпоследовательностей ц-чисел, будетнулевой сигнал,На фиг.1 приведена функциональнаясхема генератора г,р-чисел, для г=2,р=.Сушность генерирования избыточныхпоследовательностей ц-чисел (при ц=2)заключается в следующем.Двоичное слово, составленное изпоследовательных значений весовыхкоэффициентов в ц-коде, разбиваетсяна группы, которые состоят из ц двоичных разрядов (табл,2, где апострофами отмечены границы между группамиразрядов) .Из табл.2 следует, что, например, для формирования 1-й позиции второй группы необходимо провести сложение чисел ь-й позиции первой группы и 1-1-й позиции второй группы. Для фар мирования 1-1-й позиции третьей группы необходимо произвести сложение1-й позиции первой группы и - и 1-й позиции второй группы и т,д, Режим сложения двух или трех операндов на сумматоре 4 определяется состоянием триггера .Рассмотрим работу устройства для случая х,=1.В начальный момент производится значение значения х =1 в регистр 2-1, сброс в "О" регистров 2-2 - 2-3 (цепи сброса регистров стандартны и для упрощения не показаны). Сигналом "Пуск" триггер 7 устанавливается в нулевое состояние и запускается блок 1 синхронизации на выработку тактовых импульсов СИ по выходу 1-2. В первом такте на инверсном входе элемента 5 запрета присутствует сигнал,25 разрешающий прохождение первого тактового импульса на синхронизирующий вход 3-3 коммутатора 3. Текущее значение регистра 2-3 (в данном случае нулевое) по входу 3-5 коммутатора 3 через элемент И 9-1 мультиплексора 9 по информационноыу выходу 3-6 поступает на второй информационный вход сумматора 4. Сложение с единичным значением регистра 2-1 синхронизи руется сигналом с выхода элемента 5 запрета через элемент ИЛИ 6. Единичным сигналом с выхода 1-3 блока синхронизации (г,р) ч ц=1 и первым тактовым импульсом открывается эле мент И 10, с выхода которого задержанным сигналом с линии 11 стробируется прохождение второго операнда с регистра 2-2 на вход 3-4 коммутатора 3, через элемент И 9-2, информацион ный выход 3-6 коммутатора 3 и далее на информационный вход сумматора 4. Единичными сигналами с выхода 3-7 коммутатора 3 и с выхода 1-4 блокасинхронизации, определяющим режим 50 формирования о-последоватал ности (и=1), открывается элемент И 8 и триггер 7 устанавливается в единичное состояние. Суь:рование с резу том предыдущего действия синхронизи руется единичным сигналом с выхода 3-7 коммутатора 3 через элемент ИЛИ 6. В результате на выходе сумматооа 4 будет сумма значений содержимых регистров 2- - 2-3. Единичным сигналом СИ, задержанным (СИ,) с выхода1- блока синхронизации, производится последовательная перезапись текущих значений сумматора 4 на регистр 2-1,регистра 2-1 производится считываниетекущего (в данном случае - =1) значения последовательности. Так как наинверсном входе элемента запрета присутствует единичный сигнал, то повторому тактовому импульсу предлагаемым способом на сумматоре 4 проводится сложение содержимого регистров2-1 и 2-2, Передача содержимого регистра 2-3 на сумматор 4 запрещаетсянулевым значением сигнала с выходаэлемента 5 запрета. Единичным значением сигнала с выхода 3-7 коммутатора через элемент И 8 триггер 7 устанавливается в нулевое состояние.Сигналом СИ с выхода 1-1 блокасинхронизации производится записьсодержимого сумматора=2 в регистр 2-1 и последовательная передача значения предыдущего регистра впоследующий. На выходе генератора устанавливается значение второго числа последовательности р =2, при этом содержимое регистров 2-1 - 2-3 соответственно рарно 2,1,1. По текущему тактовому импульсу СИ с выхода 1-2 блока синхронизации производится последовательное во времени сложение значений регистров 2-1 - 2-3 на сумматоре 4, при этом триггер 7 устанавливается в нулевое состояние. На выходе генератора устанавливается значение третьего числа последовательности=4, Значение регистров 2-1 2-3 при этом будет соответственно 4,2,1, Четвертый такт аналогичен второму Р =6 и т,д.Длявыработки единичных сигналов (г,р)ч у=1 и о 1 при формировании соответствующих последовательностей используют стандартный дешифратор команд.Формула изобретенияГенератор избыточныхпоследовательностей чисел с произвольными начальными условиями, содержащий г+р последовательно включенных регистров с первого по (г+р)-й сумматор, коммутатор и блок синхронизации, причем первый информационный вход первого регистра9 12297 является входом задания начальных условий генератора, выход первого регистра подключен к первому информационному входу сумматора и является выходом генератора, выход сумматора 5 подключен к второму информационному входу первого регистра, вход синхронизации которого объединен с входами синхронизации остальных регистров и подключен к первому выходу блока син-о хронизации, вход которого подключен к входу Пуск генератора, выходы регистров с второго по (г)-й и выход г+р)-го регистра подключены к соответствующим входам группы информа ционных входов коммутатора, первый вход синхронизации которого подключен к второму выходу блока синхронизации, третий выход которого подключен к второму входу синхронизации 30 коммутатора, информационный выход которого подключен к второму информационному входу сумматора, о т л и - ч а ю щ и й с я тем, что, с целью 1 Орасширения области применения за счет возможности генерирования избыточных ц-чисел, в него введены элемент запрета, триггер со счетным входом, элемент И и элемент ИЛИ, причем третий вход синхронизации коммутатора объединен с первым входом элемента ИЛИ и подключен к выходу элемента запрета, прямой вход которого подключен к второму выходу блока синхрониза ции,инверсный вход элемента запрета подключен к выходу триггера со счетным входом счетный вход которого подключен к выходу элемента И, первый вход которого подключен к четвертому выходу блока синхронизации, второй вход элемента И объединен с вторым входом элемента ИЛИ и подключен к выходу сигнала сопровождения информации коммутатора, выход элемента ИЛИ подключен к входу синхронизации сумматора, вход сброса триггера со счетным входом соединен с входом блока синхронизации.229749 Составитель СКурошТехред О.Гортвай Корректор С.Шекмар Редактор Н,Гунько Заказ 2450/48 Тираж 67 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 3035, Москва, Ж, Раушская наб д, 4/5