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

некоторых сумматоров, чтобы обеспечить линейную независимость символов на их выходах.

Вслучае преобразования переменных, используемых в схемах

сразветвлением входящей последовательности, требуется уста­

новить наличие линейных связей между числами Vk, Vk + 1, ...

••■> Vk +q_ v последовательно появляющимися на выходах ГПСЧ за q тактов работы. Для этого в качестве первого шага следует выявить линейные соотношения между векторами Vk и Vk+X (т = = 1, 2, . . . , q — 1). Эти соотношения определяются матрицей коэффициентов |бх ||, полученной умножением матрицы |б | на квадратную матрицу |А | в степени т

1МЧ|6«И11\

новую матрицу размерности (т X ql), которая будет определять линейные соотношения между компонентами векторов Vk, Vk + 1, . . .

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

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

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

285

чтобы величина min (/ + g -f ••• + h), где /, g, ..., h — высшие номера связанных линейной зависимостью разрядов псевдослу­

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

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

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

Рассмотрим задачу выбора связей в двухрегистровом ГПСЧ. Для этого воспользуемся таблицей выходов (рис. 124). Столбцы и строки этой таблицы пронумерованы соответственно числу разрядов первого и второго регистров сдвига. Каждую (г — ;')-ю клетку таблицы сопоставим с выходом полусумматора, соединя­ ющего соответствующие разряды регистров, т. е. vp = xt ф уj. Тогда множество всех клеток этой таблицы будет представлять совокупность всевозможных выходов параллельного ГПСЧ, при­ чем клетки, расположенные в диагоналях таблицы, проходящих сверху — вниз — вправо, будут соответствовать совокупности выходов с одинаковым шагом h = i — j.

Максимальное число линейно независимых выходов, разме­ щаемых в таблице размерности (m х п), равно m + п — 1, что соответствует максимальному числу линейно независимых строк

286

матрицы |б I в выражении (7.42). (Это число также совпадает с максимальным числом выходов, имеющих различный шаг h). Если в таблице размещено к > т + п — 1 выходов, то все к — т —■п + 1 независимых линейных соотношений могут быть

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

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

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

с различным шагом h заполняются к клеток таблицы с соблюде­ нием следующих условий: 1) в каждой диагонали таблицы раз­ мещается не более одной занятой клетки; 2) все или часть заня­ тых клеток не являются вершинами замкнутого многоугольника. Следует заметить, что процедура размещения выходов в таблице небольшой размерности не представляет особого труда. Однако, при т + п > 20 могут возникать ситуации, когда клетки одной из диагоналей таблицы по условию линейной независимости выходов окажутся запрещенными. Избежать этого можно, если заполнить таблицу некоторым упорядоченным способом, напри­ мер, в виде «лестницы» (рис. 126).

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

287

линейно независимых выходов, размещаемых в ней, будет равно т + п — 2, а не m + « - 1 = ftmax, как требуется по условию.

С помощью таблицы выходов можно также выявить линейные

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

о о

о о

о о

О о

v p 0 е + 1) = Х 1 ( к + 1) © У ; ( к + 1) = Xt _x (к) ф У / . х (к),

что соответствует в таблице выходов перемещению выхода vp по диагонали на клетку вверх. Обозначив выход, соответствующий этой клетке, через v’p, можем записать

. . ., v’i в к- м такте работы генератора. Следовательно, анализ линей­ ной зависимости между разрядами ГПСЧ в смежные такты работы можно производить путем анализа в таблице совокупности выхо­

288