реклама на сайте
подробности

 
 
> Расчет значений ПСП, быстрый расчет значения ПСП, которое будет через 1000 и более тактов
Mt_
сообщение Dec 11 2009, 10:50
Сообщение #1


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.
Go to the top of the page
 
+Quote Post
3 страниц V   1 2 3 >  
Start new topic
Ответов (1 - 35)
Rst7
сообщение Dec 11 2009, 10:57
Сообщение #2


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 11 2009, 11:28
Сообщение #3


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(Rst7 @ Dec 11 2009, 13:57) *
Конктретику по реализации ГПСП в студию. Хотя сразу напрашивается решение запустить второй, третий, и т.д. генераторы с нужной фазой относительно первого.

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

Запуск параллельных ПСП пока не очень нравиться по ряду причин.
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 11 2009, 11:34
Сообщение #4


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



Цитата
Например:


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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
mvm54
сообщение Dec 14 2009, 09:30
Сообщение #5


Участник
*

Группа: Участник
Сообщений: 42
Регистрация: 29-11-07
Пользователь №: 32 817



Цитата(Mt_ @ Dec 11 2009, 13:50) *
Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.


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

Для изделий которые разрабатывали еще НАШИ дедушки в мезозойскую эру (домикросхемная эра, эпоха микромодулей) разрабатывались так называемые «прикуриватели», которые решали вашу задачу.
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 14 2009, 09:31
Сообщение #6


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



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


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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
mvm54
сообщение Dec 14 2009, 09:36
Сообщение #7


Участник
*

Группа: Участник
Сообщений: 42
Регистрация: 29-11-07
Пользователь №: 32 817



Цитата(Rst7 @ Dec 14 2009, 12:31) *
А есть скан? Я бы с удовольствием покурил на досуге.

Скана нет. надо искать в архивах пожелтевшие страницы.
Go to the top of the page
 
+Quote Post
Oldring
сообщение Dec 14 2009, 13:09
Сообщение #8


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Mt_ @ Dec 11 2009, 13:50) *
Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.



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


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 14 2009, 13:22
Сообщение #9


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(Rst7 @ Dec 11 2009, 14:34) *
Как Вы думаете, что я Вам могу ответить на такой пример? Хотя-бы заявили длину сдвигового регистра и способ выполнения обратных связей, не говоря уже о том, где планируется имплементация всей лавки, в ПЛИС или в процессоре?

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

Цитата(Oldring @ Dec 14 2009, 16:09) *
Как всегда всё упирается в компромисс. Самый быстрый способ - забить таблицу. Один такт.

К сожалению, так много памяти у меня нет в распоряжении.
Go to the top of the page
 
+Quote Post
Oldring
сообщение Dec 14 2009, 15:10
Сообщение #10


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Mt_ @ Dec 14 2009, 16:22) *
К сожалению, так много памяти у меня нет в распоряжении.


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


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 14 2009, 16:11
Сообщение #11


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(Oldring @ Dec 14 2009, 18:10) *
У нарисованного Вами регистра период - 7 состояний. Берете остаток от деления на 7 и получаете результат в таблице с 7 элементами.

Это я для примера нарисовал. Надо более 16 бит
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 14 2009, 18:12
Сообщение #12


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



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

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

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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
mvm54
сообщение Dec 14 2009, 19:27
Сообщение #13


Участник
*

Группа: Участник
Сообщений: 42
Регистрация: 29-11-07
Пользователь №: 32 817



Цитата(Rst7 @ Dec 14 2009, 12:31) *
А есть скан? Я бы с удовольствием покурил на досуге.

Сделал pdf статьи «В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени»», весит 6м. Прикрепить не удалось. Могу выслать на почту.
Go to the top of the page
 
+Quote Post
disel
сообщение Dec 15 2009, 01:50
Сообщение #14


Знающий
****

Группа: Свой
Сообщений: 610
Регистрация: 22-04-05
Пользователь №: 4 410



Цитата(mvm54 @ Dec 14 2009, 22:27) *
Сделал pdf статьи «В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени»», весит 6м. Прикрепить не удалось. Могу выслать на почту.


Положите не какой нибудь файлообменик
Go to the top of the page
 
+Quote Post
mvm54
сообщение Dec 15 2009, 06:45
Сообщение #15


Участник
*

Группа: Участник
Сообщений: 42
Регистрация: 29-11-07
Пользователь №: 32 817



Цитата(disel @ Dec 15 2009, 04:50) *
Положите не какой нибудь файлообменик

http://www.rapidshare.ru/1295989
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 15 2009, 07:23
Сообщение #16


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Mt_ @ Dec 11 2009, 04:50) *
Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.


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


--------------------
Go to the top of the page
 
+Quote Post
Guest_TSerg_*
сообщение Dec 15 2009, 08:04
Сообщение #17





Guests






Все поняли так - просто не хочется. smile.gif
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 15 2009, 08:16
Сообщение #18


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



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


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

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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 15 2009, 08:17
Сообщение #19


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Rst7 @ Dec 15 2009, 02:12) *
Не факт. Если там длины порядка 30-40-50, то "прогнать" не спасет wink.gif


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


--------------------
Go to the top of the page
 
+Quote Post
mvm54
сообщение Dec 15 2009, 08:18
Сообщение #20


Участник
*

Группа: Участник
Сообщений: 42
Регистрация: 29-11-07
Пользователь №: 32 817



Цитата(des00 @ Dec 15 2009, 10:23) *
вопрос не понял, что мешает тупо сразу прогнать 1000 и более тактов, тем более на фпга ? smile.gif

Такая задача встает при применении полиномов с разрядностью от 30 и далее .... И сколько часов...суток.... фпга будет вводить систему в синхронизм????
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 15 2009, 08:22
Сообщение #21


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



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

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


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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 15 2009, 08:28
Сообщение #22


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Rst7 @ Dec 15 2009, 02:22) *
Дык ресурсами видимо тоже не богаты.


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


--------------------
Go to the top of the page
 
+Quote Post
Oldring
сообщение Dec 15 2009, 15:03
Сообщение #23


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Mt_ @ Dec 14 2009, 19:11) *
Это я для примера нарисовал. Надо более 16 бит


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


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 15 2009, 19:59
Сообщение #24


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



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


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

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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 16 2009, 04:20
Сообщение #25


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Rst7 @ Dec 15 2009, 13:59) *
Ну выдает. Наличие сразу 64х бит меняет число 2^43 на 2^37, что примерно 1.4E11. Даже если тактовая 1ГГц, время полного перебора больше двух минут. А если там степень не 43, а больше?


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

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


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


--------------------
Go to the top of the page
 
+Quote Post
Builder
сообщение Dec 19 2009, 14:39
Сообщение #26


iBuilder©
****

Группа: Свой
Сообщений: 519
Регистрация: 14-07-04
Из: Минск
Пользователь №: 322



Цитата(Mt_ @ Dec 14 2009, 18:11) *
Это я для примера нарисовал. Надо более 16 бит
А максимально сколько?
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 20 2009, 12:25
Сообщение #27


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(Builder @ Dec 19 2009, 17:39) *
А максимально сколько?

Нет придела совершенства smile.gif. но более 32 будет уже излишним.
Go to the top of the page
 
+Quote Post
samurad
сообщение Dec 23 2009, 14:51
Сообщение #28


Частый гость
**

Группа: Свой
Сообщений: 121
Регистрация: 9-05-08
Из: Япония
Пользователь №: 37 385



Цитата(Mt_ @ Dec 11 2009, 14:50) *
Здравствуйте.
Есть генератор Псевдо Случайной Последовательности, реализованный на сдвиговом регистре (FSR). Интересует возможность быстро(за разумное количество тактов) расчитать значение регистра, которое будет через 1000 и более, тактов.
Если эта задача не разрешима, предложите другие алгоритмы генерации ПСП, в которых можно реализовать поставленную задачу.

Интересно узнать, в чем сейчас практический смысл (польза) от быстрого расчета значения регистра через произвольно большое число тактов? В 1969 г., как следует из мотивировки вышеупомянутой статьи, экономили на каждом бите, чтобы получить разные ПСП. Сейчас ресурсы стали намного дешевле...
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 24 2009, 08:37
Сообщение #29


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(samurad @ Dec 23 2009, 17:51) *
Интересно узнать, в чем сейчас практический смысл (польза) от быстрого расчета значения регистра через произвольно большое число тактов? В 1969 г., как следует из мотивировки вышеупомянутой статьи, экономили на каждом бите, чтобы получить разные ПСП. Сейчас ресурсы стали намного дешевле...


не терять синхронизацию с потоком ПСП, у которого выбили опреленное количество байт (пакет потерялся).
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 24 2009, 08:53
Сообщение #30


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



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


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 24 2009, 14:09
Сообщение #31


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(Rst7 @ Dec 24 2009, 11:53) *
Ээээ, господа, а вы там случайно не для целей шифрования пытаетесь использовать такие генераторы? А то они нифига не криптостойкие, в курсе?

Нет. Измерение BER.
Go to the top of the page
 
+Quote Post
Rst7
сообщение Dec 24 2009, 14:11
Сообщение #32


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



Цитата
Измерение BER.


Годиццо smile.gif


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
samurad
сообщение Dec 27 2009, 16:39
Сообщение #33


Частый гость
**

Группа: Свой
Сообщений: 121
Регистрация: 9-05-08
Из: Япония
Пользователь №: 37 385



Цитата(Mt_ @ Dec 24 2009, 12:37) *
не терять синхронизацию с потоком ПСП, у которого выбили опреленное количество байт (пакет потерялся).

В таком случае быстрая генерация произвольного состояния регистра мало чем поможет.
А поможет простая параллельная генерация нескольких ПСП с взаимными сдвигами, перекрывающими вероятное окно поиска временно "потерянной" ПСП. Не знаю, какую динамику ухода опорного генератора и какой интервал "пропадания" сигнала вы рассматриваете, но во многих случаях такой уход по сравнению со скоростью практических ПСП небольшой, соответственно нужный размер окна тоже небольшой.
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 27 2009, 18:01
Сообщение #34


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(samurad @ Dec 27 2009, 19:39) *
В таком случае быстрая генерация произвольного состояния регистра мало чем поможет.
А поможет простая параллельная генерация нескольких ПСП с взаимными сдвигами, перекрывающими вероятное окно поиска временно "потерянной" ПСП. Не знаю, какую динамику ухода опорного генератора и какой интервал "пропадания" сигнала вы рассматриваете, но во многих случаях такой уход по сравнению со скоростью практических ПСП небольшой, соответственно нужный размер окна тоже небольшой.

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

Цитата(mvm54 @ Dec 14 2009, 12:30) *
В.В. Калмыков, Е.А. Каплин. «Методы формирования М-последовательностей с произвольным сдвигом во времени». Вопросы радиоэлектроники, вып.7, 1969г. Серия Техника радиосвязи.
Go to the top of the page
 
+Quote Post
samurad
сообщение Dec 29 2009, 03:34
Сообщение #35


Частый гость
**

Группа: Свой
Сообщений: 121
Регистрация: 9-05-08
Из: Япония
Пользователь №: 37 385



Цитата(Mt_ @ Dec 27 2009, 22:01) *
В моей задаче впосле достаточно генерации одного сдвинутого ПСП, что решается

Надо понимать, метод различных соединений обратной связи, описанный с статье 69 г., вам помог?
Go to the top of the page
 
+Quote Post
Mt_
сообщение Dec 30 2009, 02:05
Сообщение #36


Частый гость
**

Группа: Свой
Сообщений: 116
Регистрация: 3-06-05
Из: Санкт-Петербург
Пользователь №: 5 719



Цитата(samurad @ Dec 29 2009, 06:34) *
Надо понимать, метод различных соединений обратной связи, описанный с статье 69 г., вам помог?

да.
Go to the top of the page
 
+Quote Post

3 страниц V   1 2 3 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 22nd July 2025 - 15:54
Рейтинг@Mail.ru


Страница сгенерированна за 0.01754 секунд с 7
ELECTRONIX ©2004-2016