Как конечные пользователи канала связи мы должны были принять участие в испытаниях доработанной системы связи. Собственно говоря, наше участие было простое – принести ноутбук и блок сопряжения, подключить к системе и непрерывно выдавать из компьютера любые информационные кадры как некоторую «полезную нагрузку».
Разработчики должны были гонять систему в разных режимах, а затем телеметристы выдать нам принятый массив данных. После этого мы должны были проверить контрольные суммы (пардон, циклически избыточный код) каждого кадра и, если найдем ошибки, внести их число в протокол испытаний.
Поэтому надо было подготовить простую программу (в смысле ПО) для испытаний. И встал вопрос, что выдавать в качестве «информации»? Решили все-таки не тривиальную «решетку» 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 считаем триногометрические функции.
Но все-таки личность математика тоже играет важную роль. Еще в античности философы, а заодно и математики, рассказывали друг другу шутку-софизм про Ахиллеса и черепаху. При этом они находились в шаге от великого математического открытия: сумма бесконечного числового ряда может быть конечной. Но тогда рядом не оказалось мальчишки со свежим взглядом, вроде Галуа, который бы вместо идиотского вывода «Ахиллес никогда не догонит черепаху», сделал бы шаг в правильном направлении: «Ахиллес никогда не догонит черепаху за заданное время, за первую секунду, но за вторую уже перегонит» - значит, несмотря на бесконечное деление времени на части, сумма этих бесконечных частей конечна! Такого математика тогда не нашлось и ряды (которые мы не совсем правомерно называем рядами Тейлора) отодвинулись на тысячи лет.
Если бы Галуа не погиб в юном возрасте, сколько бы еще открытий мог бы сделать. А если бы он с Чарльзом Бэббиджем бы встретился, ну или бы с Адой Лавлейс, возможно, жили бы мы сейчас совсем в другом компьютерном мире…
Griboks
А почему вы выбрали такую странную псевдослучайную последовательность? Можно же было просто заранее сгенерировать последовательность с нужными характеристиками.
MichaelBorisov
Почему же странную? Вполне себе типичную, часто применяемую в таких случаях. И качественную. Например, спектр полного периода такой последовательности в точности равен 1 на всех частотах.
Если вычислять заранее: где взять столько памяти, чтобы её хранить? Да и зачем? Вычислять быстрее, чем хранить. Период повторения 32-битного LFSR = 2^32-1 — то есть, за вычетом единицы, а это 4 гигабита, т.е. 500 мегабайт.