Тестирование псевдослучайной последовательностью

[@Griboks]

А почему вы выбрали такую странную псевдослучайную последовательность? Можно же было просто заранее сгенерировать последовательность с нужными характеристиками.

[@MichaelBorisov]

Почему же странную? Вполне себе типичную, часто применяемую в таких случаях. И качественную. Например, спектр полного периода такой последовательности в точности равен 1 на всех частотах.

Если вычислять заранее: где взять столько памяти, чтобы её хранить? Да и зачем? Вычислять быстрее, чем хранить. Период повторения 32-битного LFSR = 2^32-1 — то есть, за вычетом единицы, а это 4 гигабита, т.е. 500 мегабайт.

[@ilynxy]

Итак. Нам хотели рассказать про применение PRBS (pseudo random binary sequence) при тестировании канала передачи. Было бы интересно (наверное, тем кто не встречался), узнать про применимость PRBS, из каких соображений выбираются полиномы и их длины для LFSR. Почему они называются примитивными полиномами и как получить наибольшую длину последовательности. Что CRC это как раз способ формирования контрольной суммы (и кстати тоже сильно связан с именем Галуа) и проверять «циклический избыточный код» неверно терминологически, верней проверять «контрольную сумму» или, более обобщенно, «проверочное слово», которое может быть сформировано хоть по CRC, хоть по SHA или любому другому алгоритму.

А вместо этого нам рассказали «смищную» историю, про человека который посчитал псевдослучайный поток шумоподобным.

Зачем то софизм про черепаху и Ахиллеса. Поля Галуа кажеца не связаны ни с пределами ни с вопросом дискретно пространство или континуально. Роль отдельных личностей в науке в начале 20 и далее века сильно преувеличена: множество открытий делалось одновременно и независимо в разных частях шарика, просто дозрел аппарат, а кто конкретно это формализовал, не сильно важно — не он, так кто-нибудь еще.

Извините, пригорело: очередная невыносимая порция «прекрасной чуши» этого автора.

[@a_podshivalov]

Стало быть, в вашей «системе связи» не было предусмотрено то, что называется data whitening, когда полезные данные, например, XOR-ятся с псевдослучайной последовательностью?

[@MichaelBorisov]

Наверно, из-за таких ассемблерных программ и говорят, что компиляторы выдают лучший код, чем люди.

Страх и ужас!

Вот альтернативная реализация 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 — это хорошее дело, я этим тоже занимался. Важно, что последовательность непериодическая: некоторые искажения каналов связи на периодических сигналах не обнаруживаются.