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

оказывается несложным вычислить величину максимальной по­ грешности преобразования е„, которая возникает, когда преобра­

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

мых для получения переменных и и к, равновероятны, то погреш­ ность произведения sUv будет равна величине корреляционного момента K Uv (0).

Если коды сомножителей А — В = (1, 0, . . 0), то произве­ дение uv будет функцией только двух переменных х х и у х —uv =

нимая во внимание, что уровень взаимной корреляции между различными разрядами в реальном ГСЧ примерно одинаков, следует считать, что условие К ху (0) ^ 2~<!+1) является необхо­ димым условием достижения заданной точности вычислений.

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

294

К ху (т), — не должны по абсолютной величине превышать 2~(i+n. Так, уже при I = 10 эти значения должны быть не больше чем

0,0005.

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

Что касается источников шума, то сейчас практика распола­ гает полупроводниковыми генераторами шума, обладающими полосой частот шумового спектра от нуля до десятков ГГц, зна­ чительной мощностью спектра (что позволяет во многих случаях обходиться без усилителей), а также высокой стабильностью характеристик при изменении внешних условий и колебаний напряжения источника питания [44].

Поэтому, при проектировании ГСЧ особое внимание надо уделять разработке преобразующих схем генератора, к которым относятся: усилитель шума, пороговые схемы, схемы стробиро­ вания, пересчетные и иные схемы, предназначенные для выравни­ вания вероятностей появления 0 и 1. Усилитель должен сохранять вид корреляционной функции случайного сигнала. Пороговые схемы и схемы выравнивания вероятностей доляшы обеспечить получение случайной двоичной последовательности с заданной степенью отклонения вероятностей р (1) и р (0) от 1/2.

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

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

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

295

пристального внимания. Если на внутриразрядпую корреляцию наибольшее влияние оказывает инерционность преобразующих схем, а также различная чувствительность срабатывания плеч триггера, то корреляция между разрядами ГСЧ вызывается в основном воздействием когерентной помехи от источников питания, импульсов опроса, а также от взаимного проникнове­ ния наводок, возникающих при срабатывании преобразующих схем в разрядах ГСЧ. Для предотвращения такого рода помех необходимо принимать ряд специальных мер, таких, например, как изоляция линий питания от линий машины, фильтрация напряжения питания, экранировка и изоляция источников шума и триггеров [91].

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

Генераторы псевдослучайных чисел лишены, по сути дела, всех недостатков, свойственных физическим ГСЧ.

1. Статистические характеристики двоичных последователь­ ностей в разрядах ГПСЧ вследствие своей структуры практически идеальны: символы 0 и 1 равновероятны и некоррелированы, т. е.

р (1) = р (0), К х (т) = 0 (т Ф 0), К ху (т) == 0. При этом период последовательности может быть сделан сколько угодно большим. Так уже при длине регистра сдвига в 40 разрядов неповторя­ ющаяся последовательность чисел может генерироваться в тече­ ние суток с частотой свыше 107 чисел/с.

2.На статистические характеристики последовательности не влияет ни окружающая среда, ни колебания напряжения источ­ ника питания.

3.Генератор может обладать очень высоким быстродействием,

определяемым только частотой работы логических элементов, из которых он построен. Уже в настоящее время практика рас­ полагает регистрами сдвига, работающими на частотах порядка нескольких сотен МГц [14].

4. Генератор может быть легко выполнен в микроминиатюр­ ном исполнении, так как однородность элементов является благо­ приятным фактором с точки зрения изготовления БИС. При этом число разрядов в регистре сдвига может превышать 100.

Кроме перечисленных преимуществ, применение псевдослу­ чайных чисел в СтВМ открывает дополнительные резервы повы­ шения точности и быстродействия вычислений, которые принци­

296

пиально невозможны при использовании случайных чисел. Так, например, используя псевдослучайную выборку, которая более точно отражает характер распределения, чем истинная случай­ ная выборка того же объема, можно избежать больших отклоне­ ний частоты появления единиц на выходе преобразователя «код —■ вероятность» от вероятности. Если входные данные в машине периодически меняются в каждом цикле решения, то, устана­ вливая регистр сдвига в исходное состояние в начале каж­ дого цикла, можно каждый раз использовать одну и ту же выборку.

Уменьшения дисперсии результата операции можно также добиться за счет использования в цикле решения полного периода псевдослучайной последовательности. При этом дисперсия числа единиц в последовательности на выходе преобразователя код — вероятность оказывается равной нулю, в то время как случай­ ный характер последовательности сохраняется. Окончательное решение об эффективности такого метода повышения точности результата можно сделать, исследовав распределение вероятно­ стей значений функции корреляции между такими последова­ тельностями.

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

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

Например, в произведении двух переменных uv — {х1V х хх^) х X (2/1Z/2V У1У2У3)’ имеющем место при умножении двоичных чисел

297

так как появление на выходах ГПСЧ наборов х хх 2у ху 2 и х 1х 2у 1у 2у3 невозможно. Если же одну из переменных в этом соотношении, например х 2, взять с инверсией, т. е. заменить соотношением

х х ф х 2 = у г тождественным х х ® х 2 ® у х = 1, то теперь дан­ ные наборы будут появляться с вероятностью, соответственно равной х/8 и V i,, поэтому ошибка произведения будет равна

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

ющим примером.

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

Х\— Уг ® Уз, х2= ух 0 у2 ® г/g и х1 ® х 2 = уи

каждое из которыхсоответственно приводит к ошибке е х, е2 и е3, а все вместе — к суммарной ошибке = г х + е2 + е3.

Будем теперь периодически инвертировать переменные х х и х 2 так, как это показано на временных диаграммах (рис. 131). Очевидно, что погрешность результата будет теперь равна сред­ нему арифметическому погрешностей е2 на каждом из четырех участков. Учитывая при этом, что знак погрешностей ех, е2, е3 изменяется на противоположный только при инвертировании

Как видим, результирующая ошибка равна нулю.

298