Способ генерации псевдослучайной двоичной последовательности

Способ генерации псевдослучайной двоичной последовательности

Иллюстрации

Показать все

Реферат

Изобретение относится к областям информатики и вычислительной техники и может быть использовано для построения генераторов псевдослучайной двоичной последовательности (ГПСДП) с большим кодовым циклом.

Известен способ хранения и использования информации, описанный в изобретении «Запоминающее устройство» (см. патент на изобретение №1805500, МПК G11C 19/00, 06.04.1990 г.), характеризующийся применением комбинаторного устройства, базирующегося на n-разрядном двоичном генераторе из сдвигового регистра (CP) и сумматора по модулю два (См2), охваченных управляемыми обратными связями (ОС), каждый вариант которых (ВОС) генерирует свою, отличную от других вариантов, цепочку кодов.

Наиболее близким по технической сущности к заявляемому изобретению является способ, описанный в брошюре [1] - Б.И. Крыжановский. «Электронное колесо», М.: «Знание», «Радиоэлектроника и связь», №5, 1991 г., рис. 6, стр. 18-20], характеризующийся применением комбинаторного устройства, базирующегося на n-разрядном электронном колесе (ЭК) - двоичном генераторе из CP и См2, охваченных управляемыми ОС, обеспечивающем генерацию при различных ВОС и одновременно при сдвигах информации влево или вправо и при четном или нечетном суммировании - в соответствующих различных режимах, для каждого из которых генерируют свою, отличную от других режимов, цепочку кодов (в прототипе - пакет), причем для получения генерации, состоящей из нескольких цепочек, по завершении генерации каждой цепочки переключают режим работы генератора.

Недостатком известного способа является то, что момент переключения режимов (из текущего в очередной) определяют путем отсчета числа синхротактов (СТ) генерации, равного 2ⁿ и соответствующего самой длинной цепочке кодов (один цикл или один пакет) для не вырождающейся генерации. Между тем, для многих режимов имеет место вырождающаяся генерация с более короткой цепочкой кодов, в результате чего на последних синхротактах начнется повтор начальной части цепочки кодов, что снижает качество генерируемой ПСДП в целом. Качественная ПСДП (в том числе и составная) должна иметь как можно более длинную цепочку кодов одного цикла и без их макроповторов, т.е. когда для любой части кодов больше n внутри одного цикла ее первая половина не равна второй.

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

Техническим результатом способа является получение на n-разрядном двоичном генераторе в виде ЭК максимально длинной ПСДП без макроповторов путем составления ее из кодовых цепочек, получаемых во всех возможных режимах работы этого генератора.

Указанный технический результат достигается тем, что способ генерации псевдослучайной двоичной последовательности, характеризующийся применением комбинаторного устройства, базирующегося на n-разрядном электронном колесе (ЭК) - двоичном генераторе из сдвигового регистра (CP) и сумматоре по модулю два (См2), охваченных управляемыми обратными связями (ОС), обеспечивающем генерацию из любого исходного состояния при различных вариантах ОС (ВОС) и одновременно при сдвигах информации влево или вправо и при четном или нечетном суммировании - в соответствующих различных режимах, для каждого из которых генерируют свою, отличную от других режимов, цепочку кодов, причем для получения генерации, состоящей из нескольких цепочек, по завершении генерации каждой цепочки переключают режим работы генератора, отличается тем, что получают псевдослучайную двоичную последовательность (ПСДП) максимально возможной длины для данного генератора без макроповторов, для чего генерируют составную ПСДП - составную цепочку кодов из соответствующих частных ПСДП - частных цепочек кодов, генерируемых поочередно в каждом из возможных режимов работы данного генератора, при этом момент переключения режимов из текущего в очередной определяют для каждой частной цепочки кодов при первом повторе кода соответствующей цепочки, причем повторившиеся коды не включают в составную цепочку кодов, процесс генерации одного цикла ПСДП завершается генерацией соответствующей частной кодовой цепочки в последнем из возможных режимов работы генератора.

На фиг. 1, 2, 3 и 4 соответственно для пояснения способа представлены блок-схема 3-разрядного генератора на основе ЭК и графы генерируемых им кодовых цепочек для ВОС=1,3 рр, лев, нечет, исх. состояние нулевое, для ВОС=1,3 рр, прав., нечет исх. состояние нулевое и для ВОС=3 р, лев, чет, исх. состояние нулевое. Первые две - не вырожденные, т.к. присутствуют все возможные коды, а третья - вырожденная, т.к. отсутствуют коды 010 и 101.

На фиг. 1 показаны CP 1, управляемый коммутатор 2 (См 2) 3, выход 4 генерируемых кодов, ОС 5, вход 6 установки исходного состояния и вход 7 управления коммутатором. Все элементы широкого применения.

Способ осуществляется следующим образом.

Для простоты и ясности пояснений будем оперировать малым значением n. Пусть в соответствии с фиг. 1 используется 3-разрядный генератор на базе ЭК [1] - двоичном генераторе из сдвигового регистра (CP) 1 и сумматора по модулю два (См2) 3, охваченных управляемыми обратными связями (ОС) 5, обеспечивающий генерацию при различных вариантах ОС 5 (ВОС) и одновременно при сдвигах информации влево (на фиг. 1 лев) или вправо и при четном (условно постоянная лог. 1 на дополнительном входе (См2) 3) или нечетном (условно лог. 1 только на 1-м такте на дополнительном входе (См2) 3) суммировании - в соответствующих различных режимах, для каждого из которых генерируют свою, отличную от других режимов, цепочку кодов. Причем для получения генерации, состоящей из нескольких цепочек, по завершении генерации каждой цепочки переключают (с помощью управляемого коммутатора 2) режим работы генератора. При этом получают псевдослучайную двоичную последовательность (ПСДП) максимально возможной длины для данного генератора без макроповторов, для чего генерируют составную ПСДП - составную цепочку кодов из соответствующих частных ПСДП - частных цепочек кодов (фиг. 2, 3, 4), генерируемых поочередно в каждом из возможных режимов работы данного генератора (путем автоматического переключения коммутатора 2 через вход 7 от устройства управления - не показано на фиг. 1 в связи с непринципиальностью в рамках настоящей заявки), при этом момент переключения режимов из текущего в очередной определяют для каждой частной цепочки кодов при первом повторе первого значащего - не нулевого кода соответствующей цепочки, причем повторившийся код не включают в составную цепочку кодов. Процесс генерации одного цикла ПСДП завершается генерацией соответствующей частной кодовой цепочки в последнем из возможных режимов работы генератора.

Пусть, например, очередность режимов генерации осуществляется в порядке генерируемых цепочек кодов, представленных на фиг. 2, 3, 4. Тогда при завершении генерации первой из этих цепочек (фиг. 2), после кода 100 на выходе 4 происходит первый повтор значащего - не нулевого кода 001, который определяют для данной цепочки кодов (например, способом элементарного сравнения), исключают этот код из составной цепочки (например, стирают в CP 1) и переключают генератор в очередной режим работы, генерирующий соответствующую кодовую цепочку (фиг. 3), затем - аналогично - (фиг. 4) и т.д., получая составную кодовую цепочку, используя все 32=4 (2ⁿ) возможных режима генерации данного простейшего генератора.

Совершенно очевидно, что практический интерес имеют генераторы ПСДП с несколько большей разрядностью. Пусть, например, n=16. Тогда число различных вариантов ВОС будет 2ⁿ=65536, а всего различных режимов работы такого генератора на основе ЭК будет: 4 (65536)=262144. Один из этих режимов работы генератора с ВОС=16, 12, 9 и 7 разряды, реализованный фирмой Хьюлетт-Паккард в своем сигнатурном анализаторе HP 5004А, генерирует в одном цикле не вырожденную кодовую цепочку из 65536 различных (ни одного повтора!) 16-разрядных кодов. В 262143 других режимах работы этого генератора генерируются и другие не вырожденные кодовые цепочки такой же большой длины, а также вырожденные кодовые цепочки меньшей длины. В соответствии с [1] размещение кодов в каждой из кодовых цепочек отличается от всех других. Поэтому составная кодовая цепочка в пределах одного цикла не имеет макроповторов. Поясним это для того же 16-разрядного генератора, все генерируемые цепочки которого на условном микроуровне состоят из одних и тех же 16-разрядных кодов - букв соответствующего алфавита, а каждая генерируемая цепочка имеет неповторимый текст, составленный из одних и тех же букв. Теперь, если анализировать всю составную цепочку (условно - макроуровень), то самыми большими ее частями будут две половины. Они не совпадают, т.к. состоят из разных не равных кодовых цепочек. Разделим пситолам каждую половину и получим не совпадающие четвертинки по той же причине. И т.д. до самого микроуровня. Условно про такую составную цепочку можно сказать, что она не имеет макроповторов, что важно для ПСДП.

Имеется две возможности увеличить длину ПСДП.

Первая возможность связана с использованием в составной кодовой цепочке дополнительных частных кодовых цепочек, получаемых на генераторе при записи в него через вход 6 (фиг. 1) ненулевого исходного состояния перед каждой генерацией каждой частной кодовой цепочки. Число возможных исходных состояний генератора равно 2ⁿ, а всего различных кодовых цепочек с учетом сделанного дополнения будет: 4 (2²ⁿ).

Для 3-разрядного генератора общее число частных кодовых цепочек станет: 4 (2²ⁿ)=256. Соответственно увеличится длина ПСДП.

Вторая возможность увеличения длины ПСДП связана с вариациями составной кодовой цепочкой путем перестановок в ней частных кодовых цепочек, т.е. путем соответствующего изменения очередности режимов работы генератора. Для рассматриваемого в качестве примера 3-разрядного генератора вместо указанной выше очередности кодовых цепочек по фигурам 2-3-4-…, например, изменить очередность кодовых цепочек по фигурам 3-2-4 и т.д. Как известно, число возможных перестановок подчиняется факториальному (!) закону. Даже для 3-разрядного генератора это огромное число - факториал от числа всех частных кодовых цепочек: 256! Для генераторов с большей разрядностью число вариантов различных составных кодовых цепочек становится астрономическим, а длина ПСДП - квазибесконечной.

1. Способ генерации псевдослучайной двоичной последовательности, характеризующийся применением комбинаторного устройства, базирующегося на n-разрядном электронном колесе (ЭК) - двоичном генераторе из сдвигового регистра (CP) и сумматоре по модулю два (См2), охваченных управляемыми обратными связями (ОС), обеспечивающем генерацию из любого исходного состояния при различных вариантах ОС (ВОС) и одновременно при сдвигах информации влево или вправо и при четном или нечетном суммировании - в соответствующих различных режимах, для каждого из которых генерируют свою, отличную от других режимов, цепочку кодов, причем для получения генерации, состоящей из нескольких цепочек, по завершении генерации каждой цепочки переключают режим работы генератора, отличающийся тем, что получают псевдослучайную двоичную последовательность (ПСДП) максимально возможной длины для данного генератора без макроповторов, для чего генерируют составную ПСДП - составную цепочку кодов из соответствующих частных ПСДП - частных цепочек кодов, генерируемых поочередно в каждом из возможных режимов работы данного генератора, при этом момент переключения режимов из текущего в очередной определяют для каждой частной цепочки кодов при первом повторе кода соответствующей цепочки, причем повторившиеся коды не включают в составную цепочку кодов, процесс генерации одного цикла ПСДП завершается генерацией соответствующей частной кодовой цепочки в последнем из возможных режимов работы генератора.

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

3. Способ по п. 1, отличающийся тем, что ПСДП удлиняют путем генерации и включения в нее всех различных составных кодовых цепочек, получаемых за счет перестановки в них частных кодовых цепочек, и изменения очередности соответствующих режимов работы генератора.