Комментарии 5
А почему вы выбрали такую странную псевдослучайную последовательность? Можно же было просто заранее сгенерировать последовательность с нужными характеристиками.
0
Почему же странную? Вполне себе типичную, часто применяемую в таких случаях. И качественную. Например, спектр полного периода такой последовательности в точности равен 1 на всех частотах.
Если вычислять заранее: где взять столько памяти, чтобы её хранить? Да и зачем? Вычислять быстрее, чем хранить. Период повторения 32-битного LFSR = 2^32-1 — то есть, за вычетом единицы, а это 4 гигабита, т.е. 500 мегабайт.
Если вычислять заранее: где взять столько памяти, чтобы её хранить? Да и зачем? Вычислять быстрее, чем хранить. Период повторения 32-битного LFSR = 2^32-1 — то есть, за вычетом единицы, а это 4 гигабита, т.е. 500 мегабайт.
+1
Итак. Нам хотели рассказать про применение PRBS (pseudo random binary sequence) при тестировании канала передачи. Было бы интересно (наверное, тем кто не встречался), узнать про применимость PRBS, из каких соображений выбираются полиномы и их длины для LFSR. Почему они называются примитивными полиномами и как получить наибольшую длину последовательности. Что CRC это как раз способ формирования контрольной суммы (и кстати тоже сильно связан с именем Галуа) и проверять «циклический избыточный код» неверно терминологически, верней проверять «контрольную сумму» или, более обобщенно, «проверочное слово», которое может быть сформировано хоть по CRC, хоть по SHA или любому другому алгоритму.
А вместо этого нам рассказали «смищную» историю, про человека который посчитал псевдослучайный поток шумоподобным.
Зачем то софизм про черепаху и Ахиллеса. Поля Галуа кажеца не связаны ни с пределами ни с вопросом дискретно пространство или континуально. Роль отдельных личностей в науке в начале 20 и далее века сильно преувеличена: множество открытий делалось одновременно и независимо в разных частях шарика, просто дозрел аппарат, а кто конкретно это формализовал, не сильно важно — не он, так кто-нибудь еще.
Извините, пригорело: очередная невыносимая порция «прекрасной чуши» этого автора.
А вместо этого нам рассказали «смищную» историю, про человека который посчитал псевдослучайный поток шумоподобным.
Зачем то софизм про черепаху и Ахиллеса. Поля Галуа кажеца не связаны ни с пределами ни с вопросом дискретно пространство или континуально. Роль отдельных личностей в науке в начале 20 и далее века сильно преувеличена: множество открытий делалось одновременно и независимо в разных частях шарика, просто дозрел аппарат, а кто конкретно это формализовал, не сильно важно — не он, так кто-нибудь еще.
Извините, пригорело: очередная невыносимая порция «прекрасной чуши» этого автора.
+3
Стало быть, в вашей «системе связи» не было предусмотрено то, что называется data whitening, когда полезные данные, например, XOR-ятся с псевдослучайной последовательностью?
0
Наверно, из-за таких ассемблерных программ и говорят, что компиляторы выдают лучший код, чем люди.
Страх и ужас!
Вот альтернативная реализация 32-битного LFSR Галуа с полиномом Ethernet (0xEDB88320). Оригинал на Си:
Результат компиляции GCC 10.2:
Я бы написал иначе:
При реализации LFSR важно избегать условных переходов (JC, JNC и т.д.) потому, что в связи с псевдослучайностью последовательности предсказатель переходов процессора будет очень часто ошибаться. В результате код будет работать в разы медленнее.
Тестирование каналов связи с помощью LFSR — это хорошее дело, я этим тоже занимался. Важно, что последовательность непериодическая: некоторые искажения каналов связи на периодических сигналах не обнаруживаются.
Страх и ужас!
Вот альтернативная реализация 32-битного LFSR Галуа с полиномом Ethernet (0xEDB88320). Оригинал на Си:
uint32_t lfsr_step(uint32_t x)
{
if(x&1)
{
x = x>>1 ^ 0xEDB88320;
}
else
{
x >>= 1;
}
return x;
}
Результат компиляции GCC 10.2:
lfsr_step(unsigned int):
mov eax, edi
shr eax
mov edx, eax
xor edx, -306674912
and edi, 1
cmovne eax, edx
ret
Я бы написал иначе:
lfsr_step(unsigned int):
shr eax,1
sbb ebx,ebx
and ebx, 0xedb88320
xor eax,ebx
ret
При реализации LFSR важно избегать условных переходов (JC, JNC и т.д.) потому, что в связи с псевдослучайностью последовательности предсказатель переходов процессора будет очень часто ошибаться. В результате код будет работать в разы медленнее.
Тестирование каналов связи с помощью LFSR — это хорошее дело, я этим тоже занимался. Важно, что последовательность непериодическая: некоторые искажения каналов связи на периодических сигналах не обнаруживаются.
+3
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Тестирование псевдослучайной последовательностью