Русский
Русский
English
Статистика
Реклама

Галуа

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

14.01.2021 20:16:39 | Автор: admin

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

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

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

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

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

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru