Байки 90-х
Псевдослучайная последовательность

— Как конечные пользователи канала связи мы должны принять участие в испытаниях доработанной системы – заявляет мне начальник.
— Собственно говоря, наше участие простое – принесем ноутбук и блок сопряжения, подключимся к системе и станем непрерывно выдавать из компьютера информационные кадры как «полезную нагрузку». Разработчики погоняют систему в разных режимах, а затем телеметристы выдадут нам принятый массив данных. Мы проверим контрольные суммы (пардон, циклически избыточный код) каждого кадра и, если найдем ошибки, внесем их число в протокол испытаний. Задание ясно?
— Да.
— Подготовь программу для испытаний.
— А выдавать-то чего будем? Решетку AA55?
— Решетка – это каменный век. Выдавать надо псевдослучайную последовательность с помощью примитивного полинома Галуа.
— А что это такое?
— Деревня! Прочитай. Там все очень просто.
Прочитал, алгоритм действительно простой:

;---- ВЫДАЧА ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ----

ПСП:  MOV       EBX,ЗНАЧЕНИЕ   ;ПЕРВОНАЧАЛЬНО ВСЕ ЕДИНИЦЫ
      MOV       CX,ДЛИНА_ПСП   ;НОМЕРА ОТВОДОВ ОБРАТНОЙ СВЯЗИ

;---- ВЫСТАВЛЯЕМ ПОЗИЦИЮ ОТВОДА ОБРАТНОЙ СВЯЗИ ----

M1:   MOV       EAX,1
      XCHG      CH,CL
      SHL       EAX,CL
      XCHG      CH,CL

;---- ОБРАБАТЫВАЕМ ОЧЕРЕДНОЙ БИТ ----

      ROR       EBX,1
      JNB       M2

;---- ОЧЕРЕДНОЙ БИТ - ЕДИНИЦА ----

      AND       EAX,EBX ;ВЫДЕЛЯЕМ СИГНАЛ ОБРАТНОЙ СВЯЗИ
      MOV       EAX,1
      JNZ       @
      SHL       EAX,CL
      OR        EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=0, ДОПИСЫВАЕМ 1
      JMPS      M4
@:    SHL       EAX,CL
      NOT       EAX
      AND       EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=1, ДОПИСЫВАЕМ 0
      JMPS      M4

;---- ОЧЕРЕДНОЙ БИТ - НОЛЬ ----

M2:   AND       EAX,EBX ;ВЫДЕЛЯЕМ СИГНАЛ ОБРАТНОЙ СВЯЗИ
      MOV       EAX,1
      JZ        @
      SHL       EAX,CL
      OR        EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=1, ДОПИСЫВАЕМ 1
      JMPS      M3
@:    SHL       EAX,CL
      NOT       EAX
      AND       EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=0, ДОПИСЫВАЕМ 0

;---- ВЫДАЧА НУЛЯ ----

M3:  CLC
     RCR       БАЙТ,1
     JMPS      @

;---- ВЫДАЧА ЕДИНИЦЫ ----

M4:  STC
     RCR       БАЙТ,1

;---- ВЫДАЧА БАЙТА ПСП ----

@:   DEC       БИТЫ    ;БАЙТ ЕЩЕ НЕ КОНЧИЛСЯ ?
     JNZ       M1

     MOV       БИТЫ,8  ;ОПЯТЬ 8 БИТ
     MOV       ЗНАЧЕНИЕ,EBX ;ДЛЯ ПРОДОЛЖЕНИЯ ПСП
     MOV       AL,БАЙТ ;ВЫДАЛИ ОЧЕРЕДНОЙ БАЙТ ПСП
     RET

Эта подпрограмма выдает все возможные комбинации нулей и единиц (кроме одних нулей) заданной длины в псевдослучайном порядке. В нашем случае для длины 32 бит получается полмиллиарда псевдослучайных байт до повторения последовательности. Красота!

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

Второй день испытаний.
Опять все подключили и уже собирались уйти, как вдруг по громкоговорящей из аппаратной доклад: сигнал «полезной нагрузки» пропал!
Что за черт? Да тут всего один кабель в систему уходит. Перезапустили программу. Опять доклад: сигнал исчез. Полчаса, час пытаемся что-то исправить, хотя попытки большей частью сводятся к хождению вокруг стола с компьютером и пожиманию плечами. Все повторяется: при включении компьютера аппаратная видит «несущую» (а это что? Нет у нас никакой «несущей»!), затем запускаем программу и сигнал опять пропадает.
Вдруг через час в переговоры с аппаратной вмешивается телеметрист: да нет никакого пропадания сигнала! Я все нормально принимаю, как и вчера.
Фу-ты, ну-ты. Вчера же действительно все было нормально!
Начинаем разбираться.
Оказывается, вчера в аппаратной дежурил молодой специалист. Его спросили, есть сигнал «полезной нагрузки»? Он глянул на осциллограф – а там бежит наша шумоподобная псевдослучайная последовательность. Он же не знает, как должен выглядеть сигнал, поэтому спокойно докладывает: да, есть.
А сегодня дежурит опытный человек, много раз проводивший испытания. Но вот таких сигналов «полезной нагрузки» ему никогда не давали. Включаем компьютер – он докладывает, что видит «несущую» (это на самом деле выдача одних нулей). А когда программа начинает выдавать псевдослучайную последовательность, он вместо доклада «вижу шумоподобный сигнал» сразу делает ложный вывод: сигнал исчез.

А этот Эварист Галуа был голова! И вообще личность удивительная. Ведь всего-то 21 парню было, когда его смертельно ранили на дуэли, причем с дуэлью там дело какое-то темное. Но он успел такой вклад в развитие математики (читай, в развитие всей науки) сделать!
В том числе псевдослучайные последовательности получаются такие, что от белого шума не отличишь!