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

 

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

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

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

РЕСПУБЛИК (5D4G06F 102

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

ГО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ /, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (54) ГЕНЕРАТОР ИЗБЫТОЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ С ПРОИЗВОЛЬНЫМИ НАЧАЛЬНЫМИ УСЛОВИЯМИ (57) Изобретение относится к вычислительной технике и может быть использовано для получения обобщенных избыточных последовательностей чисел. Цель изобретения — расширение функциональных возможностей за счет возможности генерирования избыточных чисел q с параметрами q=.2 и произвольными начальными условиями, Генератор содержит блок синхронизации, регистры, коммутатор, сумматор, элемент запрета, элемент ИЛИ, триггер со счетным входом и элемент И, 2 ил.

2 табл.

C ф (ZI) 3795983/24-24 (22) 26.09 ° 84 (46) 07,05.86.Бюл. И 17 (72) Н,А.Збродов (53) 681.325(088.8) (56) Авторское .свидетельство СССР

У 662926, кл. G 06 F 1/02, 1976.

Авторское свидетельство СССР

И 1104493, кл. G 06 F 1/02, 1984, „„SU„„1229749 А 1

1229749

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

Значение параметра

21 34 55

1 ) 2

9 „ 13 19

) ) 1 2 " 4 6

I 1 1 1 2 3 4

7 IG

1 1 2 4 7 13 24 44 81 149

1 1 1 2 4 7 12 24 37 69

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

, = Р;- " ;., Р,.р;

-8,., - .„ Ър = 2 х

I = 1 у2у э о ° р !5 р — С,)„... ., 2 S-(»).

Э

p + 3q ° ° ° »Р+гю (1) где х — произвольное начальное условие; 2О

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

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

Как видно из табл,l, при r=р=) получают извес-.íûé ряд чисел Фибоначчи, 9 при r=l и р=l,2,3, °,. — последователь1 ности чисел фибоначчи, при r=n, р=О— известную классическую двоичную последовательность.

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

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

Для построения специализированных устройств при помехоустойчивой обработке информации необходимо генерировать избыточные последовательности чисел с произвольными начальными условиями, определяемые следующим рекуррентным соотношением: х; р =2(> у ° в э; P = ZP ) -1

q = 2,3,4... ф1 ф= 2P;,; p„=f ; / . ° );

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

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

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

При х =1,2... 2 < q < n получают избыточные последовательности (q коды)> основой которых являются избыточные позиционные системы счисления со смешанным основанием d.=.2 и Ы =1,5„ Такие системы счисления используют для построения специализированных устройств при помехоустойчивой обработке информации, Б табл.1 приведены некоторые избыточные последовательности (весовые коэффициенты) для )=1,2,3,4.

Таблица 1

1229749

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

Значение па- Последовательности рядов, р,) -чисел раме гра г

1 1 1 1 2 4 7

34!

1 1 2 4 8 15 29

1 1 1 2 4 8 15

1 1 1 1 2 4 8

1 1 2 4 8 16 31

108 208

43 90

28 52

28

60 120 235

4 1

1 1 1 2 4 8 16 31 60 117

1 l 1 1 2 4 8 16 31 60

1 2 4 8 16 32 64

128 255

r=n

Значение параметра при х =1

Последовательности q-чисел

1 2 4 6 12 18 36 54 108 162

1 2 4 8 12 24 48 72 144 288

q =г

1 2 4 8 16 32 64 128 255

q =n

Цель изобретения — расширение об- 4О ласти применения эа счет воэможности генерирования избыточных q-чисел с параметрами ц=2 и произвольными начальными условиями.

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

На схеме устройства приведены обозначения: р=2 — при генерировании по->!! следовательпостей избыточных р-чисел

Фибоначчи с производственными начальными условиями, r=2, р 1 — при генерировании последовательностей обобщенных избыточных (r,p}-чисел с про- >> иэвольными начальными условиями;ц2— при генерировании избыточных последовательностей q-чисел.

Генератор избыточных последовательностей чисел содержит блок 1 синхронизации, последовательно соединенные регистры 2-1 — 2-3, коммутатор 3, сумматор 4, элемент 5 запрета, элемент ИЛИ 6, триггер 7 со счетным входом, элемент И 8, Кроме того, первый, ..., r-й информационные входы 3-4 — 3-5 коммутатора 3 соединены соответственно с информационными выходами регистров со второго по r-й и (r+p)-й, управляющий вход 3-1 коммутатора 3 соединен с третьим выходом 1-3 блока 1 синхронизации, второй выход. 1-2 которого соединен с первым синхрониэирующим входом 3-2 коммутатора 3.Второй синхронизирующий вход 3-3 коммутатора 3 соединен с выходом элемента

1"29749

Т а б л и ц а 2

Номер группы 3

) 2

i-I i з-1

12 6 4 2 1

Р (q 2x, l) 18

5, асинхронизирующий выход 3-7 соединен с первым входом элемента ИЛИ.

Информационный выход 3-6 коммутатора

3 соединен с информационным входом сумматора 4. Первый выход 1-1 блока

1 синхронизации соединен с синхронизирующими входами регистров 2-1

2-3, а четвертый выход 1-4 — с первым. входом элемента И 6 ° Неуправля- 1О емый информационный вход генератора служит для подачи кодовой комбинации начального условия х в регистр

2-I.Информационный выход 2-1 регист- . ра является информационным выходом 15 генератора.

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

9-1 элемента И, которые стробируются синхронизирующими сигналом с входа 3-3 коммутатора. Синхрониэирующий вход 3-2 и управляющий вход 3-1 коммутатора соединены с соответствующими входами элемента И 10, выход которого соединен с выходом линии 11 задержки.

Генерирование последовательности чисел Фибоначчи,(при r ==1 и p=l 2,...) осуществляется известным способом, I

Номер позиции в группе i-1 при этом в работе участвуют регистры

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

III II

Пуск, и на инверсном выходе элемента 5 запрета установится сигнал, разрешающий прохождение синхроимпулъ-соВ (СИ) на синхронизирующий вход

3-3 коммутатора 3.

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

Генерирование последовательностсй дпя значений параметров r=2,3,... и р=l производится при подаче на вход

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

На фиг.l приведена функциональная схема генератора r,р-чисел, для г=2, p=l.

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

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

1229749

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

i-I-й позиции второй группы. Для фор- 5 мирования i-I-й позиции третьей группы необходимо произвести сложение i-й позиции первой группы и i-1 и

i-й позиции второй группы и т.д, Режим сложения двух или трех операндов на сумматоре 4 определяется состоянием триггера 7.

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

В начальный момент производится значение значения х =l в регистр 2-1, сброс в "0" регистров 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 синхронизи- 35 руется сигналом с выхода элемента 5 запрета через элемент ИЛИ 6. Единичным сигналом с выхода 1-3 блока 1 синхронизации (r,р) у q=l и первым тактовым импульсом открывается эле- 40 мент И 10 с выхода которого задержанным сигналом с линии 11 стробируется прохождение второго операнда с регистра 2-2 на вход 3-4 коммутатора

3, через элемент 1I 9-2, информацион- 45 ный выход 3-6 коммутатора 3 и далее на информационный вход сумматора 4.

Единичными сигналами с выхода 3-7 коммутатора 3 и с выхода 1 4 блока ! синхронизации, определяющим режим 50 формирования q-последоватал носги (q= l), открывается элемент И 8 и триггер 7 устанавливается в единичное состояние. ",ул.-:ирование с резу..:-— том предыдущего действия синхронизи- 55 рует".ÿ единичным сигналом с выхода

3-7 коммутатора 3 через элемент ИЛИ 6.

В результате на выходе сумматова 4 будет сумма значений содержимых регистров 2-1 — 2-3. Единичным сигналом СИ, задержанным (СИ,) с выхода

l-l блока синхронизации, производится последовательная перезапись текущих значений сумматора 4 на регистр 2-1, регистра 2-1 производится считывание текущего (в данном случае P- =1) зна1 чения последова-,åëüíîñòè. Так как на инверсном входе элемента запрета присутствует единичный сигнал, то по второму тактовому импульсу предлагаемым способом на сумматоре 4 проводится сложение содержимого регистров

2 †и 2-2. Передача содержимого регистра 2-3 на сумматор 4 запрещается нулевым значением сигнала с выхода элемента 5 запрета. Единичным значением сигнала с выхода 3-7 коммутатора через элемент И 8 триггер 7 устанавливается в нулевое состояние.

Сигналом СИ с выхода 1-1 блока ! синхронизации производится запись содержимого сумматора P =2 в регистр 2-1 и последовательная передача значения предыдущего регистра в последующий. На выходе генератора устанавливается значение второго числа последовательности р =2, при этом содержимое регистров 2-1 — 2-3 соответственно равно 2,1,1. По текущему тактовому импульсу СИ с выхода 1-2 блока синхронизации производится последовательное во времени сложение значений регистров 2-1 — 2-3 на сумматоре 4, при этом триггер 7 устанавливается в нулевое состояние. На выходе генератора устанавливается значение третьего числа последовательности t =4. Значение регистров 2-1

2-3 при этом будет соответственно

4,2,1. Четвертый такт аналогичен второму. Р =-6 и т.д.

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

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

9 12297 является входом задания начальных условий генератора, выход первого регистра подключен к первому информационному входу сумматора и является выходом генератора, выход сумматора подключен к второму информационному входу первого регистра, вход синхроI низации которого объединен с входами синхронизации остальных регистров и подключен к первому выходу блока син- о хронизации, вход которого подключен к входу "IIycxп генератора, выходы регистров с второго по (r-1)-й и выход (г+р)-го регистра подключены к соответствующим входам группы информа- >5 ционных входов коммутатора, первый вход синхронизации которого подключен к второму выходу блока синхронизации, третий выход которого подклю чен к второму входу синхронизации 20 коммутатора, информационный выход которого подключен к второму информационному входу сумматора, о т л и— ч а ю шийся тем, что, с целью

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

ИЛИ подключен к входу синхронизации сумматора, вход сброса триггера со счетным входом соединен с входом блока синхронизации.

)229749

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

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

Редактор H.Ãóíüêo

Заказ 2450/48 Тираж 67! Подписное

ВНИИПИ Государственно-.î комитета СССР по делам изобретений и открытий !!303), Москва, Ж-35, Раушская наб,, д. 4/5

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