Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (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