2.2 Отбор данных [Оберон / Компонентный Паскаль / Вики]

Содержание

2.2 Отбор данных

2.2 Отбор данных

1. Задача отбора

Это одна из классических задач в программировании — это отбор данных. Задачи такие возникают с завидной регулярностью. Например на Большом адронном коллайдере (БАК) производится столкновение двух бозонов. И операция эта повторяется несколько миллиардов раз. При этом в 85% случаев, бозоны не сталкиваются друг с другом, а пролетают мимо. Они ударяются в стенки детектора столкновений, нагревают его, но толку от таких «мимо-столкновений» нет. Но остаются ещё 15% бозонов, которые всё-таки сталкиваются. При попытке рассмотреть поближе, как они столкнулись, из этих оставшихся 15% столкновений — 85% столкновений оказывается не столкновение бозонов и бозонов, а скажем нуклонов и лептонов. И эти столкновения тоже надо отсеять и т. д. В конечном итоге, после всех отсевов столкновений сотен миллиардов частиц, на доказательство существования бозона Хиггса приходится всего 10 тыс. столкновений. Мало? Безусловно. Достаточно? Ну, видимо, да. Всё-таки 10 тыс. случаев рождения бозона Хиггса, хоть и по косвенным признакам — но зафиксировано было. Да к тому же, 10 тыс. столкновений – это «пять сигма». Физики оценят!))

2. Пороговый отбор чисел

Задача: на вход радиоприёмника поступает ослабленный радиосигнал, вместе с полезным сигналом в приёмник проникает шумовая помеха. Необходимо из массива входных сигналов выделить полезный сигнал. Сигнал поступает в форме азбуки Морзе. Дополнительные данные:

литера «S» — «#.#.#»
литера «О» — «###»
уровень шумового сигнала — ниже 50 единиц.
уровень помехи создаваемый грозой — выше 1000 единиц.

Решение: для того чтобы решить эту задачу необходимо всю задачу разделить на отдельные этапы:

Ввод данных
Отсев шума
Вывод данных

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

2.1 Определение структур данных

Для ввода данных воспользуемся модулем In. Будем считать (и на самом деле для ускорения цифровой обработки сигналов именно так и делается), что входные сигналы не превышают значение 0….+32 тыс.¹⁾, т. е. имеют тип SHORTINT. Вспомним, что для ввода целых чисел есть процедура In.Int. Но мало того что, данные необходимо вводить, поток на ввод надо ещё открыть. Для этого служит процедура In.Open. Как понять, что входные данные закончились? Переменная In.Done примет значение FALSE. Пожалуй, стоит напомнить, что для хранения данных нам потребуется массив, а для пороговых значений — парочка констант. Итак, опишем секцию данных:

CONST
	_разм = 256; (* максимальное значение счётчика для массива *)
VAR
цШум_низ: SHORTINT; (* нижний порог для шума *)
цШум_верх: SHORTINT; (* верхний порог для шума *)
мкцСигнал: ARRAY _разм OF SHORTINT; (* массив полученных замеров сигнала *)
цИтер: INTEGER; (* счётчик чтения входного потока, чтобы не выйти за пределы массива *)
цВрем: INTEGER (* временная переменная для хранения числа, так как In.Int имеет свои особенности *)

2.2 Ввод данных

После задания входных структур давайте введём данные:

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). Т. е. вовсе не факт, что массив будет использован полностью. И если дело будет обстоять именно так, то такой способ организации ввода данных не является оптимальным ²⁾. Любое условие, которое ограничивает (направляет) основную ветку выполнения программы называется охраной, что в стане Паскаля широко применяется (см. комментарий при объявлении цикла с условием на входе). Кроме того, впервые встречается ключевое слово SHORT. Это встроенное средство Компонентного Паскаля позволяет привести тип INTEGER к типу SHORTINT (исключительно для уменьшения занимаемого объёма оперативной памяти компьютера). Порядок приведения чисел был рассмотрен ранее.

По завершении процедуры ввода, выполнять закрытие входного потока не требуется. Итак, мы ввели данные с шумами, теперь их необходимо обработать.

2.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.

В целом представленная процедура имеет общепринятое название в радиотехнике «восстановление формы цифрового сигнала».

Также обратите внимание на то, что переменные цШум Низ и цШум верх на самом деле не изменяются и их можно было определить как константы. Это будет несколько лучше, так как константы нельзя изменять (по ошибке вы можете попытаться это сделать). Кроме того, устанавливаемые уровни сигналов – по сути, тоже константы. И чтобы не искать их по всему коду – можно тоже вынести в одно место.

2.4 Вывод данных на экран

Поскольку у нас уже есть готовые данные для вывода на экран, необходимо придумать способ сделать это доступно для оператора.

Часть символов («#» и «.») уже представлено по условию задачи, и они обозначают «есть сигнал» и «нет сигнала» соответственно. Но у нас появился ещё один сигнал, значение которого равно «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 Сигнал_Печать;

2.5 Общий вид программы

Для запуска всей программы нужно определить запускающую процедуру с признаком экспорта. Пусть она по традиции будет называться «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.

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

2.6 Исходные данные и результат

Пример выделения данных для ввода в программу. В качестве исходных данных предлагаются следующие числа:

(*)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». В первом случае сигнал был детектирован(выделен) точно. Во втором случае, в символ «О», видимо, вмешалась гроза, а в третьем случае сигнал трижды зашкаливал, и скорей всего, смысловой нагрузки не несёт. Вполне возможно, что в этот момент рядом работал мобильный телефон⁴⁾.

Задание

Сделайте так, чтобы литера «О» не была бесполезным определением.
Доработайте так, чтобы вместо морзянки выводились литеры
Попробуйте сделать с помощью типа тСигнал с привязкой процедур.

¹⁾

Если посмотреть на бытовые электросчётчики, то у них класс точности 1%. Для получения такого класса точности, необходимо чтобы измерительный прибор имел измерительный диапазон всего 0…+255, т. е. 1 байт. при этом динамический диапазон составит 48 дБ, а при измерительном диапазоне 0…32 тыс. точность составит 0,003%, что примерно в 300 раз лучше бытового счётчика. При этом динамический диапазон измеряемой величины будет примерно 90 дБ, что является очень хорошим показателем. Так что у нас — превосходный приёмник ,) (между прочим качество компакт-диска не многим лучше — всего 96 дБ)

²⁾

Для хранения данных, число которых заранее неизвестно используется структура, получившая название «связанный список», или проще «цепочка». У него тоже есть недостатки, но в ряде случаев может оказаться более удобным.

³⁾

Если появилась пиковая помеха мы не можем просто так взять, и обнулить её. Дело в том, что именно в этот момент может передаваться и полезный сигнал. Если мы его обратим в ноль — это будет гарантированное искажение, а если приведём к нормальному уровню — нам может и повезёт, и не нужно будет повторно принимать эту часть информации.

⁴⁾

Сигнал SOS принят как международный, и буквально означает «спасите наши души». Существует целый стандарт, который описывает все параметры такого сигнала, и порядок действий при его приёме. Подробнее можно почитать в Википедии. Возможно, кто-то из читающих эту главу таким образом в будущем спасёт не одну человеческую жизнь.

Инструменты пользователя

Инструменты сайта

Содержание