Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf

угольником, вершинами которого, кроме занятых клеток, могут быть и нули главной диагонали. Однако необходимо напомнить, что при синтезе такого ГПСЧ особого внимания требует вопрос, касающийся интервалов сдвига между двоичными последователь­ ностями, генерируемыми на выходах полусумматоров.

Рассмотрим пример, иллюстрирующий метод синтеза парал­

^ 22/ = 2й . Но для этого требуется, чтобы суммарное число разрядов в регистрах сдвига было т + п Ss 16.

Желая получить наиболее простое устройство, пойдем на компромиссное решение, выбрав в качестве генераторов исход­ ных последовательностей максимальной длины 11-разрядный и 7-разрядный регистры сдвига с одним полусумматором в цепи

Перейдем к выбору связей от разрядов регистров к полу­ сумматорам, представляющим разряды ГПСЧ. Для этого по­

290

X ft + 1, Y k. Нетрудно видеть, что на любой совокупности клеток с двумя различными знаками не удается построить замкнутый многоугольник.

Общее количество клеток, занятых в таблице, равно 23, в то время как максимальное число линейно независимых выходов

тп — 1 = 17. Поэтому число независимых линейных соот­

Рис. 129. Пример синтеза параллельного ГПСЧ на основе семи- и одиннадцатиразрядных регист­ ров сдвига:

клетки, обозначенные символами О. *, □> соответ­ ствуют разрядам двоичных чисел Х^, Х^+1, Y ^

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

логию связей для всех 16 полусумматоров и их распределение

случая все шесть независимых линейных соотношений имеют вид!

х$ Ф Xj ф у2 ф у3= 0, f-\-g + A = 18.

Суммируя в различных комбинациях эти уравнения, можно получить все возможные соотношения, связывающие чисела X*,

решим уравнение (7.24), подставляя в правую часть все возмож­

Анализируя полученную таблицу и учитывая выражение (7.22), обнаружим, что минимальный интервал сдвига между последо­ вательностями будет равен min (s/7) я» 8 N = 16376 за исклю­ чением двух пар разрядов (h = —10 и 5, h = —9 и 6), для кото­ рых min (Sji) ^ N = 2047.

Рассмотренный пример показывает, что табличный метод анализа линейной зависимости между разрядами ГПСЧ позволяет сравнительно просто, не прибегая к услугам ЦВМ, синтезиро­ вать параллельный генератор на основе двух регистров сдвига. Благодаря простоте и наглядности метода удалось сократить

2 9 2

число разрядов в регистрах сдвига с 24 до 18. При этом ошибка вычислений, возникающая вследствие такого сокращения остается

При проектировании СтВМ возникает вопрос: использовать ли для преобразования переменных последовательности псевдослу­ чайных чисел или применить для этих целей истинно случайные числа, генерируемые в устройствах с физическими источниками шума.

Чтобы ответить на этот вопрос, необходимо сравнить возмож­ ности генераторов случайных и псевдослучайных чисел с точки зрения быстродействия, качества генерируемых последователь­ ностей, а также сложности их реализации. В связи с этим прежде всего определим требования, предъявляемые к параметрам гене­ раторов в СтВМ. Как известно, для получения высоких характе­ ристик СтВМ (точности и быстродействия) быстродействие ГСП должно быть максимально приближено к быстродействию логи­ ческих элементов, используемых для построения операционной части машин, т. е. должно лежать в диапазоне от единиц до со­ тен МГц. Требования к качеству случайных последовательностей, т. е. к степени соответствия их статистических характеристик характеристикам гипотетической последовательности, можно опре­ делить исходя из необходимой точности вычислений.

Будем характеризовать степень приближения распределения чисел в реальной последовательности к равномерному распре­ делению отклонением вероятности появления единиц в разрядах

двоичных чисел А = (а1, а 2, . . ., at).

Так как погрешность преобразования еи = р (и) — А 2~1 зави­ сит не только от степени равновероятности 0 и 1 в разрядах слу­ чайного числа, но также и от логической схемы преобразователя «код — вероятность», для конкретности произведем эту оценку, как и раньше, для преобразователя, построенного на основе схемы сравнения (см. стр. 78). Причем ограничимся рассмотре­ нием частных случаев, поскольку для произвольных значений ех, е2, . . ., еi определение погрешности еи представляет большие трудности.

Как известно, в случае преобразования кода А = (1, 0, . . ., 0) выход преобразователя и есть функция только одной переменной

293