[Алгоритмы, Читальный зал, История IT] Тестирование псевдослучайной последовательностью
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Как конечные пользователи канала связи мы должны были принять участие в испытаниях доработанной системы связи. Собственно говоря, наше участие было простое – принести ноутбук и блок сопряжения, подключить к системе и непрерывно выдавать из компьютера любые информационные кадры как некоторую «полезную нагрузку».Разработчики должны были гонять систему в разных режимах, а затем телеметристы выдать нам принятый массив данных. После этого мы должны были проверить контрольные суммы (пардон, циклически избыточный код) каждого кадра и, если найдем ошибки, внести их число в протокол испытаний.Поэтому надо было подготовить простую программу (в смысле ПО) для испытаний. И встал вопрос, что выдавать в качестве «информации»? Решили все-таки не тривиальную «решетку» 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 считаем триногометрические функции.Но все-таки личность математика тоже играет важную роль. Еще в античности философы, а заодно и математики, рассказывали друг другу шутку-софизм про Ахиллеса и черепаху. При этом они находились в шаге от великого математического открытия: сумма бесконечного числового ряда может быть конечной. Но тогда рядом не оказалось мальчишки со свежим взглядом, вроде Галуа, который бы вместо идиотского вывода «Ахиллес никогда не догонит черепаху», сделал бы шаг в правильном направлении: «Ахиллес никогда не догонит черепаху за заданное время, за первую секунду, но за вторую уже перегонит» - значит, несмотря на бесконечное деление времени на части, сумма этих бесконечных частей конечна! Такого математика тогда не нашлось и ряды (которые мы не совсем правомерно называем рядами Тейлора) отодвинулись на тысячи лет.Если бы Галуа не погиб в юном возрасте, сколько бы еще открытий мог бы сделать. А если бы он с Чарльзом Бэббиджем бы встретился, ну или бы с Адой Лавлейс, возможно, жили бы мы сейчас совсем в другом компьютерном мире…
===========
Источник:
habr.com
===========
Похожие новости:
- [Информационная безопасность, Управление сообществом, Читальный зал, Будущее здесь] Скоро будет самая беззащитная страна. Системный взгляд на проблемы информационной безопасности в России
- [Алгоритмы, Математика, Машинное обучение, Искусственный интеллект] Алгоритм обучения нейронных сетей с помощью нового вида чисел
- [История IT, Криптовалюты] У программиста из США остались две попытки для открытия самоуничтожающейся флешки. Там ключ к биткойнам на $237 млн
- [Высокая производительность, Информационная безопасность, Программирование, Читальный зал] Оцените шансы хакнуть криптообменник и получить книжку с кабанчиком в подарок
- [Алгоритмы, Поисковая оптимизация] Идеальное хэширование
- [Читальный зал, Лайфхаки для гиков, Мозг, Здоровье] Человеческий организм различает только две поры года (перевод)
- [История IT, Краудсорсинг] «Википедии» — 20 лет
- [Читальный зал, Научно-популярное, Мозг, Удалённая работа] Музыка фоном: помогают ли сконцентрироваться Моцарт, белый шум и тяжелый рок?
- [Законодательство в IT, История IT, Социальные сети и сообщества, IT-компании] IT-компании отказываются размещать сервера Parler на своих площадках из-за давления на соцсеть Amazon, Google и Apple
- [Законодательство в IT, Облачные сервисы, История IT, Социальные сети и сообщества, IT-компании] Parler в осаде: Apple и Google удалили приложение, Amazon собирается отключить соцсеть от хостинга
Теги для поиска: #_algoritmy (Алгоритмы), #_chitalnyj_zal (Читальный зал), #_istorija_it (История IT), #_galua (галуа), #_psevdosluchajnost (псевдослучайность), #_jumor (юмор), #_algoritmy (
Алгоритмы
), #_chitalnyj_zal (
Читальный зал
), #_istorija_it (
История IT
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 17:20
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 Как конечные пользователи канала связи мы должны были принять участие в испытаниях доработанной системы связи. Собственно говоря, наше участие было простое – принести ноутбук и блок сопряжения, подключить к системе и непрерывно выдавать из компьютера любые информационные кадры как некоторую «полезную нагрузку».Разработчики должны были гонять систему в разных режимах, а затем телеметристы выдать нам принятый массив данных. После этого мы должны были проверить контрольные суммы (пардон, циклически избыточный код) каждого кадра и, если найдем ошибки, внести их число в протокол испытаний.Поэтому надо было подготовить простую программу (в смысле ПО) для испытаний. И встал вопрос, что выдавать в качестве «информации»? Решили все-таки не тривиальную «решетку» 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 =========== Источник: habr.com =========== Похожие новости:
Алгоритмы ), #_chitalnyj_zal ( Читальный зал ), #_istorija_it ( История IT ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 17:20
Часовой пояс: UTC + 5