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

Как конечные пользователи канала связи мы должны были принять участие в испытаниях доработанной системы связи. Собственно говоря, наше участие было простое – принести ноутбук и блок сопряжения, подключить к системе и непрерывно выдавать из компьютера любые информационные кадры как некоторую «полезную нагрузку».

Разработчики должны были гонять систему в разных режимах, а затем телеметристы выдать нам принятый массив данных. После этого мы должны были проверить контрольные суммы (пардон, циклически избыточный код) каждого кадра и, если найдем ошибки, внести их число в протокол испытаний.

Поэтому надо было подготовить простую программу (в смысле ПО) для испытаний. И встал вопрос, что выдавать в качестве «информации»? Решили все-таки не тривиальную «решетку» 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 дня. В первый день мы подключили ноутбук и ушли, так как во время собственно испытаний нам делать нечего. Вечером обработали принятые данные, все в порядке.

Второй день испытаний. Опять все подключили и уже собирались уйти, как вдруг по громкоговорящей из аппаратной доклад: сигнал «полезной нагрузки» пропал!

Что за черт? Да тут всего один кабель в систему уходит. Перезапустили программу. Опять доклад: сигнал исчез. Полчаса, час пытаемся что-то исправить, хотя попытки большей частью сводятся к хождению вокруг стола с компьютером и пожиманию плечами.

Все повторяется: при включении компьютера аппаратная заявляет, что видит «несущую» (а это что? Нет у нас никакой «несущей»!), затем запускаем собственно программу и сигнал опять пропадает. Вдруг через час в переговоры с аппаратной вмешивается телеметрист: да нет никакого пропадания сигнала! Я все нормально принимаю, как и вчера.

Фу-ты, ну-ты. Вчера же действительно все было нормально!

Начинаем разбираться.

Оказывается, вчера в аппаратной дежурил молодой специалист. Его спросили, есть сигнал «полезной нагрузки»? Он глянул на осциллограф – а там бежит наша шумоподобная псевдослучайная последовательность. Он же не знает, как должен выглядеть сигнал, поэтому спокойно докладывает: да, есть.

А сегодня дежурит опытный человек, много раз проводивший испытания. Но вот таких сигналов «полезной нагрузки» ему, похоже, никогда не давали. Включаем компьютер – он докладывает, что видит «несущую» (это на самом деле выдача одних нулей). А когда программа начинает выдавать псевдослучайную последовательность, он вместо доклада «вижу шумоподобный сигнал» сразу делает ложный вывод: сигнал исчез, белый шум.

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

Это заставило задуматься о математике вообще и о необычных людях, двигавших ее (а, заодно, и развитие всей науки) вперед. Мы использовали полином Галуа. Всего 20 лет жизни Эвариста Галуа и 4 года его занятие математикой оставили такое наследие, которым мы, не задумываясь, пользуемся до сих пор.

Конечно, работы Галуа появились не на пустом месте. Можно сказать, что он принял знамя из рук Нильса Абеля, тоже обидно рано ушедшего из жизни. И после нелепой смерти Галуа, на дуэли, да еще при мутных обстоятельствах, развитие математики, конечно, не остановилось. Например, уже через двадцать лет появились полиномы Чебышева, которыми мы пользуемся каждый раз, когда с помощью FPU считаем триногометрические функции.

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

Если бы Галуа не погиб в юном возрасте, сколько бы еще открытий мог бы сделать. А если бы он с Чарльзом Бэббиджем бы встретился, ну или бы с Адой Лавлейс, возможно, жили бы мы сейчас совсем в другом компьютерном мире…

Let’s block ads! (Why?)

Read More

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *