"Генератор чисел в кодах "золотой" пропорции" Советский патент 1992 года по МПК G06F1/02 

Фиг.

Изобретение относится к вычислитель- . ной технике и связи и может быть использовано для диагностики узлов ЦВМ и каналов связи, функционирующих с кодами золотой пропорции.

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

На фиг.1 представлена схема генератора чисел в кодах золотой пропорции; на фиг.2 - временная диаграмма работы генератора (при ).

Генератор содержит триггерный ре- гистр 1 сдвига, с первого по третий триггеры 2. - 4, счетчик 5, дешифратор 6, второй элемент 7 запрета, первый 8 и второй 9 элементы И, первый элемент 10 запрета, третий 1.1 и четвертый 12 элементы И, третий элемент 13 запрета, первый 14 и второй 15 элементы ИЛИ, синхронизирующий вхдод 16 генератора, выходы 17-2-17-N разрядов параллельного информационного выхода генератора, последовательный информаци- онный выход 17-1 генератора, выход 18 готовности генератора.

Работу генератора иллюстрирует временная диаграмма (фиг.2) для тактов с второго по седьмой на выводах следующих элементов: последовательность синхроимпульсов (а); (1М-2)-й выход дешифратора 6 (б); (Ы-1)-й выход дешифратора 6 (в); N-й выход дешифратора 6 (г); выход триггера 1-1 (д); выход триггера 1-2 (е); выход триггера 1-3 (ж); выход триггера 1-(М-1)(з); выход триггера 1-N (и); выход триггера 2 (к); выход триггера 4 (л); выход элемента 7 запрета (м); выход элемента И 9 (н); выход элемента 10 запрета (о); выход элемента И 11 (п); выход элемента И 12 (р); выход элемента 13 запрета (с); выход элемента ИЛИ 14 (т); выход элемента ИЛИ 15 (у).

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

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

,f2arV ...(где {X} дробная часть X), которая имеет равномерное распределение на интервале значений от О до 1. Эта последовательность представляет собой ряд дробных частей произведений

целых чисел 1, 2, ... N на на число (X где 2(1+ V5)/2 является основанием системы счисления, порождающей коды золотой пропорции.

Любое действительное число D можно представить в виде суммы

did.

i - k

где п+к+1 - разрядность кода золотой пропорции;.

0,1}-двоичная цифра в i-м разряде кода;

вес i-ro разряда кода золотой пропорции.

На основании теоремы Г.Штейнгауза можно заключить, что значения чисел, определяемые последовательностью { },

{2 }...{ N , наиболее равномерно распределены на интервале от О до 1. Это свойство последовательности положено в основу работы предложенного генератора, который функционально представляет собой N-разрядный счетчик, работающий в кодах золотой пропорции и складывающий единицы с весом .Старший разряд этого счетчика имеет вес , а самый

младший разряд - вес . Поэтому в счетчике находится только дробная часть суммы

единицы с весом .

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

ddd +

0+0 О

0+1 1

1+1 1001

При счете единицы с весом а перенос в разряд с весом а° не учитывается.

Пример генерации случайных чисел для

d 2 а 3 а А . а 5

4; т1}

оо о

ОО У О

о „ о

-Ј«-}

51711143 6

.101-0. О,ООО

А , .

+ - .1

5Символом t-I-I обозначена опера0i 001иия свертки единичных разрядов.

Л -Л Из примера следует, что период равноL} мерно распределенной случайной последо вательности равен 13, т.е. содержит все

10 кодовые комбинации пятиразрядного кода

, 1 о П 1 золотой пропорции. В общем случае периж ,j и иод N-разрядной равномерно распределен n n n 1Ной послеД°ватбльности равен

+ }5-а г 15T F(N+2).

.1

где F(i) - i-e число Фибоначчи. В таблице представлена зависимость

1ООО1периода этой последовательности от раз- + рядности регистра сдвига.

1 Д

Из таблицы видно, что целесообразно выбирать разрядность генератора кратной

00101ДВУМ - 1 25 Основными операциями подсчета дроб1.ной части суммы единиц с весом а 1 являi ются сложение одноименных разрядов по приведенному правилу и свертка единич1010130 НЫХ РазРядов+ и 4 - гОбщее функциональное назначение уз. . лов следующее: триггерный регистр 1 сдви. га предназначен для кольцевого сдвига формируемого кода с возможностью неза 1П1ПЧц висимой установки старших второго и третьр Л его и младшего N-ro разрядов, элементы И

+... {Э а 8 и 9, элемент 7 запрета и элемент ИЛИ 14

.1 . предназначены для выполнения операции

свертки разрядов формируемого кода, счетчик 5 по модулю N, дешифратор 6, элемент 110 1ОИЛИ 15, элементы 10, 13 запрета и элемент

11 предназначены для модификации ис.00010 ходного кода, элемент И 12 - для формиро+ 710 вания синхронизирующего сигнала

1лс разрешения считывания внешним устройством параллельного кода на выходе 17 генератора, а триггеры 2-4 осуществляют

1оо10„ задержку сигнала перехода в младший разряд на два такта.

ц. ., п Рассмотрим работу генератора на примере пятиразрядного кода1.

В исходном состоянии в триггерах (1.1n1)-(1-N), образующих ко.льцевой регистр

+ сдвига, записан код О 0 00 0. Триггеры 2-4,

образующие трехразрядный регистр-сдви- Г Л га также обнулены. На первом и втором |12 :q j | инверсных выходах дешифратора 6 присутствует логическая 1, а на выходах всех остальных элементов генератора О. Работа генератора начинается после подачи на

и.

11 -а

синхронизирующий вход 16 последовательности синхронизирующих импульсов, которая поступает на тактовые входы триггеров (1-1) - (1-N) регистра 1 сдвига и разрешает сдвиг информации по заднему фронту указанных импульсов. Счетчик 5 подсчитывает количество импульсов и по их заднему фронту на выходах дешифратора 6 формируются одиночные импульсы, поступающие через элемент И 12 на выход 18. Этот сигнал разрешает считывание кода внешним устройство с параллельного выхода 17. При синхронизации внешнего устройства сигналом, поступающим с входа 16, с выхода 17-1 считывается последовательный код.

. Время одного периода вращения кода в регистре .Т сдвига равно длительности N тактов. Через N тактов (второй период) на третьем выходе дешифратора 6 появляется единичный импульс, разрешающий прохождение сигнала с синхронизирующего входа

16через элемент И 12 на выход 18 генератора. В результате разрешается считывание выходного кода О 0000 на параллельном информационном выходе 17 генератора. Кроме того, единичный сигнал с третьего выхода дешифратора 6 поступает через второй элемент ИЛИ 15 и открытый элемент 10 запрета на вход установки первого триггера 1-1. Происходит запись в старший разряд формируемого кода логической 1. Считывание параллельного кода на выходе

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

Через следующие N тактов (третий период) на третьем выходе дешифратора 6 вновь появляется единичный импульс и разрешается считывание на параллельном выходе 17,нового выходного кода 1 000 О. Кроме того, единичный сигнал с третьего выхода дешифратора 6 поступает через элемент ИЛИ 15 и открытый элемент И 11 на вход сброса триггера 1-1, который находился в единичном состоянии, а также на информационный вход первого триггера 2. Через два такта эта логическая 1 появляется на выходе третьего триггера 4, который является последним триггером трехразрядного регистра сдвига, образованного триггерами 2-4. Затем сигнал логической 1 поступает через элемент ИЛ И 15 и открытые элементы 10 запрета и ИЛИ 14 на вход установки триггера 1-1.

В начале нового (четвертого периода) преобразования кода на параллельном выходе 17 разрешается считывание выходного кода 0010 0. Затем происходит запись логической 1 в старший разряд аналогично, как и во втором периоде. В начале пятого

периода на информационном выходе 17 формируется выходной код 1010 0. Затем обнуляется старший разряд и формируется сигнал переноса, записываемый в первый

триггер 2.

Через два такта на выходе третьего триггера 4 появляется логическая 1, поступающая через элемент ИЛИ 15, открытый элемент И 11 на вход сброса триггера 1-1.

0 Одновременно этот сигнал поступает на информационный вход первого триггера 2 и через открытый элемент 13 запрета на вход установки N-ro триггера регистра 1 сдвига. Через два такта в младший разряд выходно5 го кода происходит запись логической 1, поступающей с выхода третьего триггера 4. В начале шестого периода на информационном выходе 17 формируется новый выходной код 1 100 1. Затем происходит

0 запись логической 1 в старший разряд и в регистре 1 сдвига устанавливается новый код 11 О О 1. Через (N-2) такта от начала шестого периода на выходах триггеров 1-3 и 1-2 установлены логические 1. Причем

5 самый старший разряд кода записан в триггере 1-2, а самый младший разряд кода - в триггере 1-1. Однако сигнал обнуления этих триггеров по объединенному входу сброса не происходит, так как в этот момент эле0 мент 7 запрета оказывается закрытым нулевым сигналом, поступающим на его вход с первого инверсного выхода дешифратора 6. Только в следующем такте, с появлением на этом входе элемента 7 запрета логической

5 1, происходит обнуление двух старших разрядов кода. Свертка осуществляется без переноса в старший разряд, так как в этот момент элемент И 8 оказывается закрытым нулевым сигналом, поступающим на его

0 вход с второго инверсного выхода дешифратора 6. Таким образом, элемент И 8 блокирует перенос логической 1 в самый младший разряд кода. В начале седьмого периода на параллельном выходе 17 форми5 руется выходной код 0000 1.

Если в процессе дальнейшей работы (13-й период для рассматриваемого примера) в коде оказываются две рядом стоящие единицы, кроме случая, когда они присутст0 вуют в самом младшем и самом старшем разрядах или в двух старших разрядах, то происходит свертка с переносом 1 в старший разряд. В эти моменты логическая 1 с выхода элемента И 9 через открытый эле5 мент 7 запрета поступает на входы сброса триггеров 1-Зи1-2и далее через открытый элемент И 8 и первый элемент ИЛИ 14 на вход установки триггера 1-1. В результате два младших разряда обнуляются, а в старший записывается логическая 1.

В дальнейшем генератор функционирует по описанным алгоритмам, причем изменение разрядности не изменяет эти алгоритмы. Генератор позволяет генерировать последовательность чисел с любой раз- рядностью , для чего необходимо только изменять количество триггеров в регистре.1 сдвига.

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

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

йены соответственно с первым информационным входом второго элемента запрета и с первым входом первого элемента И, третий выход дешифратора соединен с первым входом второго элемента ИЛИ, с вторым входом четвертого элемента И и с управляющим входом третьего элемента запрета, выход которого соединен с входом установки в 1 триггера N-ro (N-разряд- ность кода) разряда триггерного регистра сдвига, первый и второй входы второго элемента И соединены с выходами триггеров второго и третьего разрядов триггерного регистра сдвига, а выход - с вторым информационным входом второго элемента запрета, выход которого подключен к второму входу первого элемента И и к входам установки в О триггеров второго и третьего разрядов триггерного регистра сдвига,, выход триггера первого разряда которого соединен с информационным входом триггера N-ro разряда триггерного регистра сдвига, с управляющим входом первого элемента запрета, с вторым входом третьего элемента И и является последовательным информационным выходом генератора, выход готовности которого соедин.ен с выходом четвертого элемента И и с входами установки в О второго и третьего триггеров, выход первого элемента ИЛИ соединен с входом установки в 1 триггера первого разряда триггерного регистра сдвига, вход установки в О триггера первого разряда которого соединен с выходом третьего элемента И, с информационным входом третьего элемента запрета и с информационным входом первого триггера, выход третьего триггера соединен с вторым входом второго элемента ИЛИ, выход которого соединен с третьим входом третьего элемента И и с вторым информационным входом первого элемента запрета, выходы разрядов триггерного регистра сдвига являются выходами разрядов параллельно информационного выхода генератора.

Изобретение относится к вычислительной технике и связи и может быть использовано для моделирования узлов ЦВМ и каналов связи, функционирующих в кодах золотой пропорции. Цель изобретения - расширение функциональных возможностей за счет генерации равномерно распре- деленных дробных чисел в последовательных и параллельных кодах золотой пропорции. Генератор содержит триггерный регистр 1 сдвига, с первого по третий триггеры 2-4, счетчик 5, дешифратор 6, с первого по третий элементы 7, 10 и 13 запрета, с первого по четвертый элементы И 8, 9, 11 и 12, первый и второй элементы ИЛИ 14 и 15, синхронизирующий вход 16, выход 18 готовности, параллельный информационный выход 17 и последовательный информационный выход 17-1 генератора. 2 ил.

Продолжение таблицы