Перейти к содержанию

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

Добавить ссылки
Материал из Викиучебника — открытых книг для открытого мира

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

[править]

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

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

[править]

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

  • символ "S" -- "#.#.#"
  • символ "О" -- "###"
  • уровень полезного сигнала -- выше 50 единиц.
  • уровень помехи создаваемый грозой -- выше 1000 единиц.

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

  1. Ввод данных
  2. Отсев шума
  3. Вывод данных

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

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

[править]

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

CONST
    sig_max = 256; (* максимальное значение счётчика для массива *)
VAR
    p1  : SHORTINT; (* нижний порог для шума *)
    p2  : SHORTINT; (* верхний порог для шума *)
    sig : ARRAY sig_max OF SHORTINT; (* массив полученных замеров сигнала *)
    i: INTEGER; (* счётчик чтения входного потока, чтобы не выйти за пределы массива *)
    tmp : INTEGER (* временная переменная для хранения числа, так как In.Int имеет свои особенности *)

Ввод данных

[править]

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

PROCEDURE GetSignal;
BEGIN
    FOR i:=0 to (sig_max-1) DO          (* цикл обнуления исходного массива сигналов *)
        sig[i]:=0
    END;
    i:=0;                           (* предварительно обнуление счётчика *)
    In.Open;                        (* открываем входной поток на чтение *)
    WHILE (In.Done) & (i<sig_max)   (* охрана цикла *)
        In.Int(tmp);                (* чтение сигнала в цикле *)
        sig[i]:=SHORT(tmp);         (* принудительное преобразование типа *)
        INC(i)                      (* приращение счётчика цикла с условием по входу *)
    END;
END GetSignal;

Для облегчения контроля ввода данных в тексте были определены две дополнительных переменных, о которых пока не было сказано ни слова. Это константа "sig_max" и счётчик цикла "i". Константа нужна для того, что один раз её определив, не нужно было выискивать её по всему тексту. Если потребуется под массив выделить больше места -- в следующий раз будет достаточно переопределить константу. Переменная счётчика цикла нам бы потребовалась в любом случае. Также в начале процедуры ввода нам потребовалось обнулить весь массив, при этом надо обратить внимание, что в целочисленном цикле константа sig_max уменьшена на "1". Это связано только с тем, что диапазон массива сигналов индексируется от 0 до 255 (т.е. 256 элементов). Если этого не сделать, то попытка обратиться к элементу массива с номером 256 закончится крахом. Это несколько необычно для людей, привыкших считать что автобусов, домов и квартир с номером "0" не существует. Чуть позже будет показано, как этот несколько странный момент обратить в преимущество.

После целочисленного цикла, переменная "i" опять получает присвоение, так как после целочисленного цикла она будет равна "255".

Цикл с условием на входе имеет сложное условие. Цикл будет повторяться до тех пор, пока есть данные на входе (In.Done), либо не закончится массив. Т.е. вовсе не факт, что массив будет использован полностью. И если дело будет обстоять именно так, то такой способ организации ввода данных не является оптимальным[2]. Любое условие, которое ограничивает (направляет) основную ветку выполнения программы называется "охраной", что в стане Паскаля широко применяется (см. комментарий при объявлении цикла с условием на входе). Кроме того, впервые встречается ключевое слово SHORT. Это встроенное средство КП позволяет привести тип INTEGER к типу SHORTINT. Порядок приведения чисел был рассмотрен ранее.

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

Отбор данных

[править]

Выше у нас были определены пороги для просто шумов, и для мощных импульсных помех (например, разряд молнии за десятки километров от места приёма, либо сработавший мобильный телефон, который рядом с приёмником даст довольно мощную помеху).

Для отсева будем использовать условия. Если сигнал шумовой -- сбросим значение ячейки массива в ноль. Если же мощнейшая помеха -- просто обрежем её по уровню чуть выше нормального сигнала[3]. Также следует обратить внимание на то, что в условии задачи не сказано какой именно уровень сигнала является полезным. И это правильно, так как источник сигнала может находиться ближе или дальше, могут образовываться условия для лучшего прохождения сигнала за счёт ионизации атмосферы, а может и наоборот -- проплывающий мимо источника сигнала крупный корабль может в несколько раз ослабить сигнал, и даже исказить его.

Вот пример того, как можно отсеять помехи: 

PROCEDURE LimitSig;
BEGIN
    p1:=50;
    p2:=1000;
    FOR i:=0 TO sig_max-1 DO
        IF sig[i]<p1 THEN
            sig[i]:=0
        ELSIF sig[i]>p2 THEN
            sig[i]:=600
        ELSE
            sig[i]:=500
        END;
    END;
END LimitSig;

Как видно из кода, через альтернативную ветку ELSIF уровень сигнала устанавливается несколько выше(600), чем устанавливается сигнал попавший в достоверный диапазон(500). Это может пригодиться, как индикатор того, что это была точка завышенного сигнала. Уровень полезного сигнала был выбран на уровне "500" потому, что он примерно соответствует середине измерительного диапазона 50...1000.

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

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

[править]

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

Часть символов ("#" и ".") уже представлено по условию задачи, и они обозначают "есть сигнал" и "нет сигнала" соответственно. Но у нас появился ещё один сигнал, значение которого равно "600". И его надо как-то тоже обозначать. Поскольку он превышает нормальный уровень нужно визуально указать на этот факт. Очень удобно будет использовать символ "^". Ниже примерный вид процедуры, который мог бы это сделать: 

PROCEDURE OutSig;
CONST
    p = " ";  (* пауза в передаче сигнала *)
    s = "#";  (* полезный сигнал *)
    m = "^";  (* молния? *)
BEGIN
    Log.String('[Начало приёма]'); Log.Ln;
    FOR i:=0 TO sig_max-1 DO
        IF sig[i]=0 THEN
            Log.String(p)
        ELSIF sig[i]=500 THEN
            Log.String(s)
        ELSE
            Log.String(m)
        END;
    END;
    Log.Ln; Log.String('[Конец приёма]');Log.Ln
END OutSig;

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

[править]

Для запуска всей программы нужно определить запускающую процедуру с признаком экспорта. Пусть она по традиции будет называться "Start". Также нельзя забывать про правило упреждающего объявления (вспоминаем содержание прошлых глав). Полный текст программы ниже. 

MODULE TestHello9;
	(* это программа на языке
	Компонетный Паскаль. Она показывает
	как можно вводить данные и обрабатывать их*)

	IMPORT In, Log, Math;

	CONST
		sig_max = 256;
	VAR
		p1: SHORTINT;
		p2: SHORTINT;
		sig: ARRAY sig_max OF SHORTINT;
		i: INTEGER;
		tmp: INTEGER;

	PROCEDURE GetSignal;
	BEGIN
		FOR i := 0 TO(sig_max - 1) DO
			sig[i] := 0
		END;
		i := 0;
		In.Open;
		WHILE (In.Done) & (i < sig_max) DO
			In.Int(tmp);
			sig[i] := SHORT(tmp);
			INC(i)
		END;
	END GetSignal;

	PROCEDURE LimitSig;
	BEGIN
		p1 := 50;
		p2 := 1000;
		FOR i := 0 TO sig_max - 1 DO
			IF sig[i] < p1 THEN
				sig[i] := 0
			ELSIF sig[i] > p2 THEN
				sig[i] := 600
			ELSE
				sig[i] := 500
			END;
		END;
	END LimitSig;

	PROCEDURE OutSig;
		CONST
			p = "."; (* пауза в передаче сигнала *)
			s = "#"; (* полезный сигнал *)
			m = "^"; (* молния? *)
	BEGIN
		Log.String('[Начало приёма]'); Log.Ln;
		FOR i := 0 TO sig_max - 1 DO
			IF sig[i] = 0 THEN
				Log.String(p)
			ELSIF sig[i] = 500 THEN
				Log.String(s)
			ELSE
				Log.String(m)
			END;
		END;
		Log.Ln; Log.String('[Конец приёма]'); Log.Ln
	END OutSig;

	PROCEDURE Start*;
		VAR
	BEGIN
		GetSignal;
		LimitSig;
		OutSig
	END Start;

BEGIN
END 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


Чтобы программа смогла их получить на вход, необходимо выделить их, и нажать на КОММАНДЕР (как на скриншоте слева).





В результате компиляции и выполнения программы будет выведена следующая информация: 

компилируется "TestHello9"   560   524
старый модуль TestHello9 выгружен
[Начало приёма]
..#.#.#.###.#.#.#............#.#.^##.#.#.#......^^^...........................................
..............................................................................................
....................................................................
[Конец приёма]

Обратите внимание на размер программы: 560 байт.

Из выведенного сигнала видно, что была передана комбинация букв: "SOS SOS O". В первом случае сигнал был детектирован(выделен) точно. Во втором случае, в символ "О", видимо, вмешалась гроза, а в третьем случае сигнал трижды зашкаливал, и скорей всего, смысловой нагрузки не несёт. Вполне возможно, что в этот момент рядом работал мобильный телефон[4].

Примечания

[править]
  1. ↑ Если посмотреть на бытовые электросчётчики, то у них класс точности 1%. Для получения такого класса точности, необходимо чтобы измерительный прибор имел измерительный диапазон всего 0...+255, т. е. 1 байт. при этом динамический диапазон составит 48 дБ, а при измерительном диапазоне 0...32 тыс. точность составит 0,003%, что примерно в 300 раз лучше бытового счётчика. При этом динамический диапазон измеряемой величины будет примерно 90 дБ, что является очень хорошим показателем. Так что у нас -- превосходный приёмник ,) (между прочим качество компакт-диска не многим лучше -- 96 дБ)
  2. ↑ Для хранения данных, число которых заранее неизвестно используется структура, получившая название "связанный список", или проще "цепочка". У него тоже есть недостатки, но в ряде случаев может оказаться более удобным.
  3. ↑ Если появилась пиковая помеха мы не можем просто так взять, и обнулить её. Дело в том, что именно в этот момент может передаваться и полезный сигнал. Если мы его обратим в ноль -- это будет гарантированное искажение, а если приведём к нормальному уровню -- нам может и повезёт, и не нужно будет повторно принимать эту часть информации.
  4. ↑ Сигнал SOS принят как международный, и буквально означает "спасите наши души". Существует целый стандарт, который описывает все параметры такого сигнала, и порядок действий при его приёме. Подробнее можно почитать здесь. Возможно, кто-то из читающих эту главу таким образом в будущем спасёт не одну человеческую жизнь.
Источник — https://ru.wikibooks.org/w/index.php?title=Компонентный_Паскаль/Отбор_данных&oldid=163853