Генератор избыточных последовательностей чисел с произвольными начальными условиями Советский патент 1986 года по МПК G06F1/02 

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

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

Р,- Р,-П..,.Г.Р..Г-Р;

Р, ,, х„; 2 х,; .

17

1 , Z , « , ,

Г 1

t, 5 J , . . , ,

„ . oS-(

55-0

р + 3,,...,р+г, (1) где X - произвольное начальное условие;

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

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

Подставляя конкретные значения г и р в соотношение (1), при получают табл.1 последовательностей рядов {г,р) чисел.

Как видно из табл,1, при получают известный ряд чисел Фибоначчи при г и ,2,3,,.. - последователности чисел Фибоначчи, при , известную классическую двоичную последовательность.

При ,3,4,... и ,2,3,... получают последовательности обобщенных

г Р

S

г

Р 1 1 2 4 7 3 24 44 81 149 1 2 4 7 12 24 , 37 69

5

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

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

Р,

о

f,2B

-.

0

5

0

5

0

q 2,3,4,...; АГ , J А.1 P, АМ; „а 2p,,,J (i,,,2p.,...;

1 , 2q+l, Sq+l, . . ., где x - произвольное начальное условие;

q - определяет алгоритм получения избыточной последовательности чисел.

При х 5 и получают двоичную последовательность, весовые коэффициенты: которой равны степени двойки.

При ,..., 2 q п получают избыточные последовательности (q -коды), основой которых являются избыточные позиционные системы счисления со смешанным основанием и й 1,5,1 Такие системы счисления ис- польз тот для построения специализированных устройств при помехоустойчивой обработке информации, i

Б табл. приведены некоторые избыточные; последовательности (весовые коэффициенты) для ,2,3,4„

Таблица 1

па- | Последовательности рядов (t-, р,)-чисел

1 1 1 124

3

1

2 3

1

2 3

16 32

64

128

Последовательности q-чисел 1 2 4 6 12 18 36 54 1 2 4 8 12 24 48 72

q n

8 16 32

Цель изобретения - расширение об- ласти применения за счет возможности генерирования избыточных q-чисел с параметрами и произвольными начальными условиями.

На фиг.1 приведена структурная схема предлагаемого устройства; на фиг.2 - функциональная схема коммутатора,

На схеме устройства приведены обозначения: - при генерировании по-50 следовательностей избыточных р-чисел Фибоначчи с производственными начальными условиями; , - при генерировании последовательностей обобщенных избыточных (г,р)-чисел с про- 55 извольными начальными ycлoвиями;q 2 - при генерировании избыточньгх последовательностей q-чисел.

Продолжение табл.I

7

12

3034

29

5

8

ЗГ

16

16 32

64

128

255

108 144

162 288

64

128

255

Генератор избыточных последовательностей чисел содержит блок I синхронизации, последовательно соединенные регистры 2-1 - 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 соединен с выходом элемента

5, асинхронизирующий выход 3-7 соединен с nepBbw входом элемента ИЛИ. Информационный выход 3-6 коммутатора 3 соединен с информационньм входом сумматора 4. Первьй выход 1-1 блока 1 синхронизации соединен с синхронизирующими входами регистров 2-1 - 2-3, а четвертый выход 1-4 - с первым, входом элемента И 6, Неуправля- емьй информационный вход генератора служит для подачи кодовой комбинации начального условия х в регистр 2-1 .Информационный выход 2-1 регист- ра является информационным выходом генератора.

Схема (фиг.2) содержит мультиплексор 9 из г многовходовых элементов И 9-1 - 9-г, элемент И 10, разрешающий работу устройства в режиме формирования (r,p)v q последовательностей, г-1 линии 11 задержки, предназначенной для последовательной во времени передачи содержимого второго ..., г-го и (г+р)-го регистров на сумматор. Выход 3-7 г-1-й линии задержки является синхронизирующим выходом коммутатора 3, выход мультиплексора соединен с информационньгм выходом 3-6 коммутатора 3. Первый ин формационньш вход 3-4 коммутатора соединен с информационными входами элемента И 9-2, которые стробируются сигналами с выхода линии 11 задержки г - информационный вход (второй)3-5 соединен с информационными входами 9-1 элемента И, которые стробируются синхронизирующими сигналом с входа 3-3 коммутатора. Синхронизирующий вход 3-2 и управляющий вход 3-1 ком- мутатора соединены с соответствующими входами элемента И 10, выход которого соединен с выходом линии 11 задержки.

Генерирование последовательности чисел Фибоначчи .(при и ,2,.. осуществляется известным способом.

Номер группы

Т

при этом в работе участвуют регистры 2-1 - 2-3, количество которых определяется величиной (р+О, коммутатор 3, обеспечивающий передачу содержимого (р+1)-го регистра 2-3 на сумматор 4 посредством элемента И 9-1 и единичного выхода элемента 5 запрета. В этом случае на третьем выходе 1-3 блока синхронизации, определяющем режим работы (г,р)V q, будет нулевой сигнал и, следовательно, нулевой сигнал на элемента И 8. В результате этого триггер 7 сохранит нулевое состояние, установленное по сигналу Пуск, и на инверсном выходе элемента 5 запрета установится сигнал, разрешающий прохождение синхроимпу.пь-- сов (СИ) на синхронизирзпощий вход 3-3 коммутатора 3.

На фиг.1 приведена функциональная схема генератора чисел Фибоначчи ,для г+1 и .

Генерирование последовательностей для значений параметров ,3,.. и р производится при подаче на вход 3-1 коммзгтатора 3 единичного значения сигнал:а (r,p)vq с выхода 1-3 блока синхронизации. При этом триггер 7 также сохраняет нулевое состояние, так как с выхода 1-4 блока скнхрокизации задающего режим работы q формирования последовательностей q-чиceл будет нулевой сигнал.

На фиг.1 приведена функциональная схема генератора г,р-чисел, для , Р.

Cyin.Hoc.Tb генерирования избыточных последовательностей q-чисел (при ) заключается в следующем.

Двоичное слово, составленное из последовательных значений весовых коэффициентов в q-коде, разбивается на группы, которые состоят из q двоичных разрядов (табл.2jгде апострофами отмечены границы между группами разрядов .

Т а б л и ц а 2

10

15

Из табл.2 следует, что, например, для формирования i-й позиции второй группы необходимо провести сложение чисел 1-й позиции первой группы и i-1-й позиции второй группы. Для фор- 5 мирования i-1-й позиции третьей группы необходимо произвести сложение i-й позиции первой группы и и i-й позиции второй группы и т.д. Режим сложения двух или трех операндов на сумматоре 4 определяется состоянием триггера 7.

Рассмотрим работу устройства для случая Хд 1.

В начальный момент производится значение значения х 1 в регистр 2-1, сброс в О регистров 2-2 - 2-3 (цепи сброса регистров стандартны и для, упрощения не показаны). Сигналом Пуск триггер 7 устагтавливается в нулевое состояние и запускается блок 1 синхронизации на выработку тактовых импульсов СИ по ВЫХОДУ 1-2. В первом такте на инверсном входе элемента 5 запрета присутствует сигнал, разрешающий прохождение первого тактового импульса на синхронизирующий вход 3-3 коммутатора 3. Текущее значение регистра 2-3 (в данном случае нулевое) по входу 3-5 коммутатора 3 через элемент И 9-1 мультиплексора 9 по информационно1 у выходу 3-6 поступает на второй информационный вход сумматора 4. Сложение с единичным значением регистра 2- синхронией- 35 руется сигналом с вьгхода элемента 5 запрета через элемент ИЛИ 6. Единичным сигналом с выхода 1-3 блока 1 синхронизации (г,р) v и первь1М тактовым импульсом открывается эле- 40 мент И 10, с выхода которого задеранным сигналом с линии I1 стробиру- ется прохождение второго операнда с регистра 2-2 на вход 3-4 коммутатора 3, через элемент И 9-2, информацион- 45 ный выход 3-6 коммутатора 3 и далее на информационньш вход сумматора 4. Единичными сигналами с выхода 3-7

25

коммутатора 3 и с вьгхода 1 -4 блока 1

синхронизации, определяющим режим формирования q-последоБатальности (q-l), открывается элемент И S и триггер 7 устанавливается в едикмчкое. состояние. Сум. гирование с peayj,:;; i s- том предыдущего действия синхронизи- 55 руется единичным сигналом с выхода 3-7 коммутатора 3 через элемент ИЛИ 6, В результате ка выходе сумматора 4

50

0

5

5

5

будет сумма значений содержимых регистров 2-1 - 2-3. Единичным сигналом СИ, задержанным (СИ) с выхода -1 блока синхронизации, производит ся последовательная перезапись текущих значений сумматора 4 на регистр 2-1 , регистра 2-1 производится считывание текущего (в данном случае .(,1) значения последовательности. Так как на инверсном входе элемента запрета присутствует единичный сигнал, то по второму тактовому импульсу предлагаемым способом на сумматоре 4 прово- дится сложение содержимого регистров 2-1 и 2-2. Передача содержимого регистра 2-3 на сумматор 4 запрещается нулевым значением сигнала с вьгхода элемента 5 запрета. Единичным значением сигнала с выхода 3-7 коммутатора через элемент И 8 триггер 7 устанавливается в нулевое состояние.

Сигналом СИ,; с выхода I-I блока 1 синхронизации производится запись содержимого сумматора f 2 Б регистр 2-1 и последовательная передача значения предыдущего регистра в последующий. На выходе генератора ус- танавливается значение второго числа последовательности J5 -2, при этом содержимое регистров 2-1 - 2-3 соответственно рарно 2,1,1. По текущему тактовому импульсу СИ с выхода 1-2 блока синхронизации производится последовательное во времени сложение значений регистров 2-1 - 2-3 на сумматоре 4, при этом триггер 7 устанавливается в нулевое состояние. На выходе генератора устанавливается значение третьего числа последовательности / 4. Значение регистров 2-1 - 2-3 при этом будет соответственно 4,2,1. Четвертый такт аналогичен второму 3 6 и т.д.

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

55

50 Формула изобретения

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

является входом задания начальных условий генератора, выход первого.регистра подключен к первому информационному входу сумматора и является выходом генератора, выход сумматора 5 подключен к рторому информационному входу первого регистра, вход синхронизации которого объединен с входами синхронизации остальных регистров и подключен к первому выходу блока син- О хронизации, вход которого подключен к входу Пуск генератора, выходы регистров с второго по (г-1)-й и выход (г+р)-го регистра подключены к соответствующим входам группы информационных входов коммутатора, первый вход синхронизации которого подключен к второму выходу блока синхронизации, третий выход которого подклю- чен к второму входу синхронизации коммутатора, информационный выход которого подключен к второму информационному входу сумматора, о т л и, - чающийся тем, что, с целью

229749 О

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

15

20

Редактор Н.Гунько

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

Техред 0 Гортвай Корректор С.Шекмар

Заказ 2450/Д8 Тираж 67 Подписное ВНИИ11И Государственного комитета СССР

по делам изобретений и открытий 1I30J, Москва, Ж-35, Раушская наб., д. 4/5

- - -- --- - --.- --- - -. - «.«..„-«.„«.,,|-г-я-пигя,ии ..и- «ь,,

Производственно-полиграфическое предприятие,г.Ужгород,ул.Проектная, 4

Фиг. г

Изобретение относится к вычислительной технике и может быть использовано для получения обобщенных избыточных последовательностей чисел . Цель изобретения - расширение функциональных возможностей за счет возможности генерирования избыточных чисел q с параметрами qr2 и произвольными начальными условиями. Генератор содержит блок синхронизации, регистры, коммутатор, сумматор, элемент запрета, элемент ИЛИ, триггер со счетным входом и элемент И. 2 ил., 2 табл. i (Л