Байки 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 парню было, когда его смертельно ранили на дуэли, причем с дуэлью там дело какое-то темное. Но он успел такой вклад в развитие математики (читай, в развитие всей науки) сделать!
В том числе псевдослучайные последовательности получаются такие, что от белого шума не отличишь!
Вам пора читать статью "как становятся старыми ... (навешивание ярлыков)" или как-то примерно так она называется.
В данном случае — у Вас тяга к рассказыванию старых баек.
Между тем у Лаптева или Альфа12345, например, такого не наблюдается — они актуальные (т.е. молодые в душе́).
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>Вам пора читать статью "как становятся старыми ... (навешивание ярлыков)" или как-то примерно так она называется.
AS>В данном случае — у Вас тяга к рассказыванию старых баек.
Это неплохо, если они полезны для чего-то.
Между прочим, именно на подходах Галуа — Джордж Марсалья изобрёл xorshift генератор, когда ему было уже под 70.
AS>Между тем у Лаптева или Альфа12345, например, такого не наблюдается — они актуальные (т.е. молодые в душе́).
Я записал
пачку баек из эпохи раннего Интернет-провайдерства.
Сейчас они кончились, вместе с той эпохой. Новых не пишу, потому что не нахожусь в зоне столь бурного и уникального развития. По-вашему, мне уже должно быть сто лет
И по любому эти байки полезнее, чем очередной... мнэээ... флейм на 1000 сообщений, у кого пакрат толще.