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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

http://www.rapidshare.ru/1295989

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

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

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

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

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

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

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



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

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

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

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

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

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



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

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

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

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

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

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

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

Годиццо

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

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

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

да.