Расчет значений ПСП, быстрый расчет значения ПСП, которое будет через 1000 и более тактов Опции

[Mt_]

Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.

[Rst7]

Конктретику по реализации ГПСП в студию. Хотя сразу напрашивается решение запустить второй, третий, и т.д. генераторы с нужной фазой относительно первого.

[Mt_]

Конктретику по реализации ГПСП в студию. Хотя сразу напрашивается решение запустить второй, третий, и т.д. генераторы с нужной фазой относительно первого.

Конкретика пока с тадии разработки. Она как раз будет зависеть от возможности решения поставленной задачи.
Например:

Запуск параллельных ПСП пока не очень нравиться по ряду причин.

[Rst7]

Например:

Как Вы думаете, что я Вам могу ответить на такой пример? Хотя-бы заявили длину сдвигового регистра и способ выполнения обратных связей, не говоря уже о том, где планируется имплементация всей лавки, в ПЛИС или в процессоре?

[mvm54]

Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.

В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени». Вопросы радиоэлектроники, вып.7, 1969г. Серия Техника радиосвязи.

Для изделий которые разрабатывали еще НАШИ дедушки в мезозойскую эру (домикросхемная эра, эпоха микромодулей) разрабатывались так называемые «прикуриватели», которые решали вашу задачу.

[Rst7]

В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени».

А есть скан? Я бы с удовольствием покурил на досуге.

[mvm54]

А есть скан? Я бы с удовольствием покурил на досуге.

Скана нет. надо искать в архивах пожелтевшие страницы.

[Oldring]

Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.

Как всегда всё упирается в компромисс. Самый быстрый способ - забить таблицу. Один такт.

[Mt_]

Как Вы думаете, что я Вам могу ответить на такой пример? Хотя-бы заявили длину сдвигового регистра и способ выполнения обратных связей, не говоря уже о том, где планируется имплементация всей лавки, в ПЛИС или в процессоре?

Реализуется в плис. Разрядность желательно не менее 16 бит.

Как всегда всё упирается в компромисс. Самый быстрый способ - забить таблицу. Один такт.

К сожалению, так много памяти у меня нет в распоряжении.

[Oldring]

К сожалению, так много памяти у меня нет в распоряжении.

У нарисованного Вами регистра период - 7 состояний. Берете остаток от деления на 7 и получаете результат в таблице с 7 элементами.

[Mt_]

У нарисованного Вами регистра период - 7 состояний. Берете остаток от деления на 7 и получаете результат в таблице с 7 элементами.

Это я для примера нарисовал. Надо более 16 бит

[Rst7]

Предлагаю следующий вариант.

Для выбранного полинома постройте логические функции, которые будут возвращать значение m последовательности через 1,2,4...2^n шагов. Каждая такая функция для каждого бита регистра будет представлять исключающее или между набором бит входных данных (всего порядка n^2 операций XOR, во что превратится имплементация на выбранной архитектуре ПЛИС надо смотреть по результатам синтеза). Затем, исходя из двоичного представления числа k, которое говорит, на сколько тактов нужно сдвинуть последовательность, пропускаем значение сдвигового регистра через полученные функции (т.е. если в какой-либо битовой позиции числа k стоит 1, то пропускаем через соответствующую функцию). Итого, вычислительное время будет O(log(n)). Ну либо офигительное развесистое дерево ячеек ПЛИС, если общая задержка устроит.

В любом случае реализация будет огромной против необходимого набора доп. генераторов.

[mvm54]

А есть скан? Я бы с удовольствием покурил на досуге.

Сделал pdf статьи «В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени»», весит 6м. Прикрепить не удалось. Могу выслать на почту.

[disel]

Сделал pdf статьи «В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени»», весит 6м. Прикрепить не удалось. Могу выслать на почту.

Положите не какой нибудь файлообменик

[mvm54]

Положите не какой нибудь файлообменик

http://www.rapidshare.ru/1295989

[des00]

Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.

вопрос не понял, что мешает тупо сразу прогнать 1000 и более тактов, тем более на фпга ?

[Guest_TSerg_*]

Все поняли так - просто не хочется.

[Rst7]

Все поняли так - просто не хочется.

Не факт. Если там длины порядка 30-40-50, то "прогнать" не спасет

Перезалил статью в закрома upload/Books.

[des00]

Не факт. Если там длины порядка 30-40-50, то "прогнать" не спасет

длинна ПСП ? а какая разница, на фпга нет проблемы считать за 1 такт 2^N тактов ПСП, будет ограничение только по частоте и ресурсу. Если размер шага ограничен, то совершенно не вижу проблем, как это сделать за 1 или N тактов.

[mvm54]

вопрос не понял, что мешает тупо сразу прогнать 1000 и более тактов, тем более на фпга ?

Такая задача встает при применении полиномов с разрядностью от 30 и далее .... И сколько часов...суток.... фпга будет вводить систему в синхронизм????

[Rst7]

Кстати, при раскуривании статьи стало понятно, как действовать. Надо выбирать коэффициенты a (обозначения в статье) не для произвольного k, а для k=1,2,4...2^n и комбинировать уже их (как я описал выше). Итого нужна будет таблица размером n*n бит, потом из этой таблицы получаются нужные коэффициенты. Итого, смена сдвига требует n тактов для вычисления коэффициента а (n бит - n выборок из таблицы), и задержка на вычисление уже сдвинутой последовательности - чисто комбинационная (см. рис 2 статьи).

а какая разница, на фпга нет проблемы считать за 1 такт 2^N тактов ПСП, будет ограничение только по частоте и ресурсу.

Дык ресурсами видимо тоже не богаты.

[des00]

Дык ресурсами видимо тоже не богаты.

только что попробывал ПСП 2^43, выдает 64 бита за такт. 291LC на сыклоне

[Oldring]

Это я для примера нарисовал. Надо более 16 бит

Четче нужно формулировать условие задачи.
Впрочем, Вам уже всё рассказали.

[Rst7]

только что попробывал ПСП 2^43, выдает 64 бита за такт. 291LC на сыклоне

Ну выдает. Наличие сразу 64х бит меняет число 2^43 на 2^37, что примерно 1.4E11. Даже если тактовая 1ГГц, время полного перебора больше двух минут. А если там степень не 43, а больше?

Я к тому, что кайф в предлагаемом мною аналитическом решении есть

[des00]

Ну выдает. Наличие сразу 64х бит меняет число 2^43 на 2^37, что примерно 1.4E11. Даже если тактовая 1ГГц, время полного перебора больше двух минут. А если там степень не 43, а больше?

эээ, в вопросе звучало как можно быстро передвинуть ПСП на 1000 символов, сделать ПСП на 100 символов и за 10 тактов вы подвинетесь как надо. В общем случае надо смотреть %)

Я к тому, что кайф в предлагаемом мною аналитическом решении есть

дык я же не спорю с этим %)

[Builder]

Это я для примера нарисовал. Надо более 16 бит

А максимально сколько?

[Mt_]

А максимально сколько?

Нет придела совершенства . но более 32 будет уже излишним.

[samurad]

Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.

Интересно узнать, в чем сейчас практический смысл (польза) от быстрого расчета значения регистра через произвольно большое число тактов? В 1969 г., как следует из мотивировки вышеупомянутой статьи, экономили на каждом бите, чтобы получить разные ПСП. Сейчас ресурсы стали намного дешевле...

[Mt_]

Интересно узнать, в чем сейчас практический смысл (польза) от быстрого расчета значения регистра через произвольно большое число тактов? В 1969 г., как следует из мотивировки вышеупомянутой статьи, экономили на каждом бите, чтобы получить разные ПСП. Сейчас ресурсы стали намного дешевле...

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

[Rst7]

Ээээ, господа, а вы там случайно не для целей шифрования пытаетесь использовать такие генераторы? А то они нифига не криптостойкие, в курсе?

[Mt_]

Ээээ, господа, а вы там случайно не для целей шифрования пытаетесь использовать такие генераторы? А то они нифига не криптостойкие, в курсе?

Нет. Измерение BER.

[Rst7]

Измерение BER.

Годиццо

[samurad]

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

В таком случае быстрая генерация произвольного состояния регистра мало чем поможет.
А поможет простая параллельная генерация нескольких ПСП с взаимными сдвигами, перекрывающими вероятное окно поиска временно "потерянной" ПСП. Не знаю, какую динамику ухода опорного генератора и какой интервал "пропадания" сигнала вы рассматриваете, но во многих случаях такой уход по сравнению со скоростью практических ПСП небольшой, соответственно нужный размер окна тоже небольшой.

[Mt_]

В таком случае быстрая генерация произвольного состояния регистра мало чем поможет.
А поможет простая параллельная генерация нескольких ПСП с взаимными сдвигами, перекрывающими вероятное окно поиска временно "потерянной" ПСП. Не знаю, какую динамику ухода опорного генератора и какой интервал "пропадания" сигнала вы рассматриваете, но во многих случаях такой уход по сравнению со скоростью практических ПСП небольшой, соответственно нужный размер окна тоже небольшой.

В моей задаче впосле достаточно генерации одного сдвинутого ПСП, что решается

В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени». Вопросы радиоэлектроники, вып.7, 1969г. Серия Техника радиосвязи.

[samurad]

В моей задаче впосле достаточно генерации одного сдвинутого ПСП, что решается

Надо понимать, метод различных соединений обратной связи, описанный с статье 69 г., вам помог?

[Mt_]

Надо понимать, метод различных соединений обратной связи, описанный с статье 69 г., вам помог?

да.