Это одна из классических задач в программировании — это отбор данных. Задачи такие возникают с завидной регулярностью. Например на Большом адронном коллайдере (БАК) производится столкновение двух бозонов. И операция эта повторяется несколько миллиардов раз. При этом в 85% случаев, бозоны не сталкиваются друг с другом, а пролетают мимо. Они ударяются в стенки детектора столкновений, нагревают его, но толку от таких «мимо-столкновений» нет. Но остаются ещё 15% бозонов, которые всё-таки сталкиваются. При попытке рассмотреть поближе, как они столкнулись, из этих оставшихся 15% столкновений — 85% столкновений оказывается не столкновение бозонов и бозонов, а скажем нуклонов и лептонов. И эти столкновения тоже надо отсеять и т. д. В конечном итоге, после всех отсевов столкновений сотен миллиардов частиц, на доказательство существования бозона Хиггса приходится всего 10 тыс. столкновений. Мало? Безусловно. Достаточно? Ну, видимо, да. Всё-таки 10 тыс. случаев рождения бозона Хиггса, хоть и по косвенным признакам — но зафиксировано было. Да к тому же, 10 тыс. столкновений – это «пять сигма». Физики оценят!))
Задача: на вход радиоприёмника поступает ослабленный радиосигнал, вместе с полезным сигналом в приёмник проникает шумовая помеха. Необходимо из массива входных сигналов выделить полезный сигнал. Сигнал поступает в форме азбуки Морзе. Дополнительные данные:
Решение: для того чтобы решить эту задачу необходимо всю задачу разделить на отдельные этапы:
По хорошему, можно было бы и проанализировать, что получается. Но задача парсера, как значительно более сложная пока рассматриваться не будет. Также пока не будем рассматривать вопросы алгоритмической оптимизации исполнения программы.
Для ввода данных воспользуемся модулем In
. Будем считать (и на самом деле для ускорения цифровой обработки сигналов именно так и делается), что входные сигналы не превышают значение 0….+32 тыс.1), т. е. имеют тип SHORTINT
. Вспомним, что для ввода целых чисел есть процедура In.Int
. Но мало того что, данные необходимо вводить, поток на ввод надо ещё открыть. Для этого служит процедура In.Open
. Как понять, что входные данные закончились? Переменная In.Done
примет значение FALSE
. Пожалуй, стоит напомнить, что для хранения данных нам потребуется массив, а для пороговых значений — парочка констант. Итак, опишем секцию данных:
CONST _разм = 256; (* максимальное значение счётчика для массива *) VAR цШум_низ: SHORTINT; (* нижний порог для шума *) цШум_верх: SHORTINT; (* верхний порог для шума *) мкцСигнал: ARRAY _разм OF SHORTINT; (* массив полученных замеров сигнала *) цИтер: INTEGER; (* счётчик чтения входного потока, чтобы не выйти за пределы массива *) цВрем: INTEGER (* временная переменная для хранения числа, так как In.Int имеет свои особенности *)
После задания входных структур давайте введём данные:
PROCEDURE Сигнал_Получ; BEGIN FOR цИтер := 0 TO (_разм - 1) DO (* цикл обнуления исходного массива сигналов *) мкцСигнал[цИтер] := 0 END; цИтер := 0; (* предварительное обнуление счётчика *) In.Open; (* открываем входной поток на чтение *) WHILE (In.Done) & (цИтер < _разм) (* охрана цикла *) In.Int(цВрем); (* чтение сигнала в цикле *) мцСигнал[цИтер] := SHORT(цВрем); (* принудительное преобразование типа *) INC(цИтер) (* приращение счётчика цикла с условием по входу *) END; END Сигнал_Получ;
Для облегчения контроля ввода данных в тексте были определены две дополнительных переменных, о которых пока не было сказано ни слова. Это константа разм
и счётчик цикла цИтер
. Константа нужна для того, что один раз её определив, не нужно было выискивать её по всему тексту. Если потребуется под массив выделить больше места — в следующий раз будет достаточно переопределить константу. Переменная счётчика цикла нам бы потребовалась в любом случае. Также в начале процедуры ввода нам потребовалось обнулить весь массив, при этом надо обратить внимание, что в целочисленном цикле константа _разм
уменьшена на 1
. Это связано только с тем, что диапазон массива сигналов индексируется от 0 до 255
(т. е. 256 элементов). Если этого не сделать, то попытка обратиться к элементу массива с номером 256 закончится крахом. Это несколько необычно для людей, привыкших считать что автобусов, домов и квартир с номером 0
не существует. Чуть позже будет показано, как этот несколько странный момент обратить в преимущество.
После целочисленного цикла, переменная цИтер
опять получает присвоение, так как после целочисленного цикла она будет равна «255».
Цикл с условием на входе имеет сложное условие. Цикл будет повторяться до тех пор, пока есть данные на входе (In.Done:=TRUE
), и не закончится массив (цИтер := 255
). Т. е. вовсе не факт, что массив будет использован полностью. И если дело будет обстоять именно так, то такой способ организации ввода данных не является оптимальным 2). Любое условие, которое ограничивает (направляет) основную ветку выполнения программы называется охраной, что в стане Паскаля широко применяется (см. комментарий при объявлении цикла с условием на входе). Кроме того, впервые встречается ключевое слово SHORT
. Это встроенное средство Компонентного Паскаля позволяет привести тип INTEGER
к типу SHORTINT
(исключительно для уменьшения занимаемого объёма оперативной памяти компьютера). Порядок приведения чисел был рассмотрен ранее.
По завершении процедуры ввода, выполнять закрытие входного потока не требуется. Итак, мы ввели данные с шумами, теперь их необходимо обработать.
Выше у нас были определены пороги для просто шумов, и для мощных импульсных помех (например, разряд молнии за десятки километров от места приёма, либо сработавший мобильный телефон, который рядом с приёмником даст довольно мощную помеху).
Для отсева будем использовать условия. Если сигнал шумовой — сбросим значение ячейки массива в ноль. Если же мощнейшая помеха — просто обрежем её по уровню чуть выше нормального сигнала3). Также следует обратить внимание на то, что в условии задачи не сказано какой именно уровень сигнала является полезным. И это правильно, так как источник сигнала может находиться ближе или дальше, могут образовываться условия для лучшего прохождения сигнала за счёт ионизации атмосферы, а может и наоборот — проплывающий мимо источника сигнала крупный корабль может в несколько раз ослабить сигнал, и даже исказить его.
Вот пример того, как можно отсеять помехи:
PROCEDURE Сигн_Ограничить; BEGIN цШум_низ := 50; цШум_Верх := 1000; FOR цИтер := 0 TO _разм - 1 DO IF sig[цИтер ] < цШум_низ THEN sig[цИтер ] := 0 ELSIF sig[цИтер ] > цШум_Верх THEN sig[цИтер ] := 600 ELSE sig[цИтер ] := 500 END; END; END Сигн_Ограничить;
Как видно из кода, через альтернативную ветку ELSIF
уровень сигнала устанавливается несколько выше(600), чем устанавливается сигнал попавший в достоверный диапазон(500). Это может пригодиться, как индикатор того, что это была точка завышенного сигнала. Уровень полезного сигнала был выбран на уровне «500» потому, что он примерно соответствует середине измерительного диапазона 50…1000.
В целом представленная процедура имеет общепринятое название в радиотехнике «восстановление формы цифрового сигнала».
Также обратите внимание на то, что переменные цШум Низ
и цШум верх
на самом деле не изменяются и их можно было определить как константы. Это будет несколько лучше, так как константы нельзя изменять (по ошибке вы можете попытаться это сделать). Кроме того, устанавливаемые уровни сигналов – по сути, тоже константы. И чтобы не искать их по всему коду – можно тоже вынести в одно место.
Поскольку у нас уже есть готовые данные для вывода на экран, необходимо придумать способ сделать это доступно для оператора.
Часть символов («#» и «.») уже представлено по условию задачи, и они обозначают «есть сигнал» и «нет сигнала» соответственно. Но у нас появился ещё один сигнал, значение которого равно «600». И его надо как-то тоже обозначать. Поскольку он превышает нормальный уровень нужно визуально указать на этот факт. Очень удобно будет использовать символ «^». Ниже примерный вид процедуры, который мог бы это сделать:
PROCEDURE Сигнал_Печать; CONST _п = " "; (* пауза в передаче сигнала *) _s = "#"; (* полезный сигнал *) _м = "^"; (* молния? *) BEGIN мЛог.String('[Начало приёма]'); мЛог.Ln; FOR цИтер := 0 TO _разм - 1 DO IF мцСигнал[i] = 0 THEN мЛог.String(_п) ELSIF мцСиг[i] = 500 THEN мЛог.String(_s) ELSE мЛог.String(_м) END; END; мЛог.Ln; мЛог.String('[Конец приёма]'); мЛог.Ln END Сигнал_Печать;
Для запуска всей программы нужно определить запускающую процедуру с признаком экспорта. Пусть она по традиции будет называться «Start». Также нельзя забывать про правило упреждающего объявления (вспоминаем содержание прошлых глав). Полный текст программы ниже.
Привет9.odc
MODULE КнигаПривет9; (* это программа на языке Компонетный Паскаль. Она показывает как можно вводить данные и обрабатывать их*) IMPORT мВв := In, мЛог := Log, Math; CONST _разм = 256; VAR цШум_низ: SHORTINT; цШум_верх: SHORTINT; мцСигнал: ARRAY _разм OF SHORTINT; цИтер: INTEGER; цВрем: INTEGER; PROCEDURE Сигнал_Получ; BEGIN FOR цИтер := 0 TO(_разм - 1) DO мцСигнал[цИтер] := 0 END; цИтер := 0; мВв.Open; WHILE (мВв.Done) & (цИтер < _разм) DO мВв.Int(цВрем); мцСигнал[цИтер] := SHORT(цВрем); INC(цИтер) END; END Сигнал_Получ; PROCEDURE Сигнал_Ограничить; BEGIN цШум_низ := 50; цШум_верх := 1000; FOR цИтер := 0 TO _разм - 1 DO IF мцСигнал[цИтер] < цШум_низ THEN мцСигнал[цИтер] := 0 ELSIF мцСигнал[цИтер] > цШум_верх THEN мцСигнал[цИтер] := 600 ELSE мцСигнал[цИтер] := 500 END; END; END Сигнал_Ограничить; PROCEDURE Сигнал_Печать; CONST _п = "."; (* пауза в передаче сигнала *) _s = "#"; (* полезный сигнал *) _м = "^"; (* молния? *) BEGIN мЛог.String('[Начало приёма]'); мЛог.Ln; FOR цИтер := 0 TO _разм - 1 DO IF мцСигнал[цИтер] = 0 THEN мЛог.String(_п) ELSIF мцСигнал[цИтер] = 500 THEN мЛог.String(_s) ELSE мЛог.String(_м) END; END; мЛог.Ln; мЛог.String('[Конец приёма]'); мЛог.Ln END Сигнал_Печать; PROCEDURE Старт*; VAR BEGIN Сигнал_Получ; Сигнал_Ограничить; Сигнал_Печать END Старт; BEGIN END КнигаПривет9.
В процедуре Старт
определены последовательные вызовы для обработки цифрового сигнала. Код разбит на довольно мелкие процедуры, что вполне позволяет оценить, что делает каждая из них даже без комментариев.
Кроме того, обратите внимание, что литера «О» у нас нигде не используется, а значит она не нужна в константах, но это становится понятно, только получения рабочего кода.
И обратите внимание, что все три вызова внутренних процедур внутри процедуры Старт
есть ничто иное, как прямое указание-подсказка на создание типа тСигнал
, с привязкой этих процедур к этому типу.
Пример выделения данных для ввода в программу. В качестве исходных данных предлагаются следующие числа:
(*)TestHello9.Start 5 8 78 40 123 32 465 1 322 567 401 0 234 32 658 23 61 23 14 18 22 34 2 2 18 32 44 41 49 51 48 67 2 1320 930 999 30 254 29 171 25 160 2 5 4 6 7 8 1350 4380 2356 2 2 2 2 2
Чтобы программа смогла их получить на вход, необходимо выделить их, и нажать на КОММАНДЕР (как на врезке).
В результате компиляции и выполнения программы будет выведена следующая информация:
компилируется "КнигаПривет9" 588 524 старый модуль КнигаПривет9 выгружен [Начало приёма] ..#.#.#.###.#.#.#............#.#.^##.#.#.#......^^^............................................................ .............................................................................................................. ................................... [Конец приёма]
Обратите внимание на размер всей программы: 588 байт.
Из выведенного сигнала видно, что была передана комбинация букв: «SOS SOS O». В первом случае сигнал был детектирован(выделен) точно. Во втором случае, в символ «О», видимо, вмешалась гроза, а в третьем случае сигнал трижды зашкаливал, и скорей всего, смысловой нагрузки не несёт. Вполне возможно, что в этот момент рядом работал мобильный телефон4).
тСигнал
с привязкой процедур.