Задачка: декодер морзе.

[valexey_u]

Почитал я тут последние топики, и решил что эту парсерно-автоматную тематику нужно как-то разбавить чем-то более осязаемым, так что ловите еще одну задачку.

У задачки есть один нюанс - мне интересней всего увидеть идиоматическое решение на Обероне-1/07/12, то есть решение на этих языках тех, кто на Обероне (или его производных вроде КП) имеет опыт написание приложений (и желательно не на досуге забавы для, а для чего-то продакшинообразного).

Итак задачка: к нам идет поток данных (например с ком-порта, но это не важно), эти данные - грубо говоря амплитуда сигнала (интенсивность света, или громкость звука, по частотам там информации нет). Частоту сэмплирования мы знаем (можем считать, для определенности, что у нас 100 сэмплов в секунду). Ну и собственно задача - дешифровать посылку которая закодирована азбукой морзе. Думаю на картинке оно будет нагляднее:






На обоих изображениях построен график по полученным данным. На обоих картинках сигнал SOS, только во втором случае, как видим, уровень сигнала плавал (ну и передатчики/генераторы сигнала были разные).

По мере дешифрации понятное дело нужно информацию выводить скажем через какой-нибудь модуль Out. Поток данных бесконечный, поэтому дождаться конца, а потом дешифровать все одним скопом не выйдет.

Возможные упрощения задачи (собственно которыми, видимо, нужно воспользоваться для первого "релиза", да, чем быстрее релиз первый, тем лучше):
1) Мы знаем темп передачи данных. То есть знаем длительность точки, тире и пауз между ними. Эти длительности зашиты в передатчике.
2) Можно считать что в первой версии пользователь вполне согласен вручную подстраивать декодер выставляя уровень сигнала (то есть в первом примере он скорее всего выставил бы, что все что выше 90та это сигнал (точка, или тире))
3) Можно считать что уровень сигнала у нас либо не плавает либо плавает слабо (не будет той каки что на втором графике). Но сам уровень сигнала мы не знаем (но см. пункт 2).

Вроде бы все. Если есть вопросы - задавайте.

Во вложении примеры данных (первая колонка - номер сэмпла, вторая колонка - сами данные).

Напомню, что интересней всего увидеть реализацию на идиоматическом Обероне (1/07/12) тех кто на Обероне пишет. Но конечно принимаются решения и на других языках от других людей :-)

[Илья Ермаков]

Архитектурно я бы организовал так:

Код: [Выделить]

MODULE Morze;

CONST
short* = FALSE; long* = TRUE;

TYPE
Decoder* = POINTER TO ABSTRACT RECORD END;
Writer* = POINTER TO ABSTRACT RECORD END;

PROCEDURE (w: Writer) Write* (sign: BOOLEAN), NEW, ABSTRACT;

PROCEDURE (d: Decoder) ConnectTo* (w: Writer), NEW, ABSTRACT;
PROCEDURE (d: Decoder) ProcessSample* (x: BYTE), NEW, ABSTRACT;
PROCEDURE (d: Decoder) Config* (VAR settings: ANYREC), NEW, ABSTRACT;

END Morze.

Decoder - реагирующая на очередной сэмпл "машина состояний" с памятью. И "играть" с тем, что она там помнит и в какой момент переходит между состояниями. Конфигурирование может быть разным для разных реализаций.

В случае (1) Алексея знать длину пауз не нужно, это уж избытгочная роскошь. Можно для простейшего случая взять такой конфиг:
      SimpleSettings* = RECORD
         signLevel*: BYTE;
         minShortLength, minLongLength: INTEGER (* в сэмплах *)
      END;
Однако этот случай уже будет плевать на длину пауз и, кроме того, будет устойчив к совсем коротким "артефактам", короче, чем minShortLength.

И состояние Decoder-а:
currentSample: INTEGER;
state: (back, signal);
signalBeg: INTEGER

Код: [Выделить]

PROCEDURE (d: SimpleDecoder) ProcessSample* (x: BYTE);
  VAR len: INTEGER;
BEGIN
  INC(d.currentSample);
  CASE d.state OF
  | back:
    IF x > d.conf.signLevel THEN
      d.state := signal; d.signalBeg := currentSample
    END
  | signal:
    IF x < d.conf.signLevel THEN
      len := d.currentSample - d.signalBeg;
      IF len > d.conf.minLongLength THEN
        d.out.Write(long)
      ELSIF len > d.conf.minShortLength THEN
        d.out.Write(short)
      END;     
      d.state := back
    END
  END
END ProcessSample;


[valexey_u]

Да, спасибо за общую архитектурную раскладку.

Длительность пауз, на сколько я помню, регламентирована, поэтому я и упомянул и их тоже.

И хотелось бы получить полное решение (желательно на обероне, так мне будет проще проверить/понять/протестировать, иначе какое-нибудь решение на КП мне придется вручную, в меру своего кривого понимания, транслировать в Оберон (не Оберон-2)). Меня кроме архитектуры и основных алгоритмов интересуют также нюансы реализации всего этого на Обероне.

[Илья Ермаков]

Я пас, времени нет.

И не вижу я там дальше никаких нюансов реализации.... Если потом не вести речь про достижение сверхбыстродействия (когда не допустимо каждый сэмпл сообщать вызовом процедуры).

Есть чисто нюансы обработки сигнала (логика декодера - его состояния и Decode).

Касательно чистого Оберона - ну, ООП процедурными полями будешь имитировать, а как же...

[valexey_u]

Я пас, времени нет.

И не вижу я там дальше никаких нюансов реализации.... Если потом не вести речь про достижение сверхбыстродействия (когда не допустимо каждый сэмпл сообщать вызовом процедуры).

Есть чисто нюансы обработки сигнала (логика декодера - его состояния и Decode).

Точечки и тире надо еще в буквы сложить. И нужно уметь восстанавливаться после сбоя (ложные срабатывания/распознования точек-тире будут точно).

[valexey_u]

Есть чисто нюансы обработки сигнала (логика декодера - его состояния и Decode).

Если я правильно понял, Декодер у тебя это как раз то, что собирает из точек и тире буквы. И вот это то и есть самое интересное (процентов 65-70 от общего интересного). В том числе реализация :-)

Дергать на каждый сэмпл функцию можно конечно. Это достаточно дешево сейчас практически везде (ибо у нас всего 100 сэмплов в секунду).

[Romiras]

По мне, так самая сложная часть задачи заключается в декодировании сигнала с помехами, то есть получении восстановленной битовой последовательности. А расшифровка Морзе - уже дело техники.

[valexey_u]

По мне, так самая сложная часть задачи заключается в декодировании сигнала с помехами, то есть получении восстановленной битовой последовательности. А расшифровка Морзе - уже дело техники.

Это не совсем так.

Во первых см. упрощения 1,2,3 задачи. они взяты не от балды, а из практики. Во вторых даже если у тебя есть идеальный сигнал (а с упрощениями оно примерно так и выходит), то все равно никто не гарантирует, что передача не прервется на половине буквы (банально вырубили передатчик до окончания передачи) и не продолжится затем с половины другой буквы. При этом, ясное дело, программа не должна впасть в маразм, она должна (возможно пропустив сколько-то точек-тире) продолжить корректно расшифровывать передачу.

Ясное дело, что поле первого "релиза" можно будет подумать как добавить помехозащищенность. Но вначале нужно обязательно выпустить релиз упрошенной версии. Лучше 20 раз по разу, чем ни разу 20 раз :-)

[Peter Almazov]

Я никогда не занимался цифровой фильтрацией, поэтому то, что изложу – взгляд абсолютного дилетанта.

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

Затем, имея опорный сигнал, делаем выборки из отфильтрованного. Если за период опорного сигнала было больше превышений нуля, то пишем в выходной буфер 1, если меньше – пишем -1. Если болтаемся вблизи нуля, можно записать 0 – неуверенный символ.

Затем, с помощью КА, измеряем длительности непрерывных отсчетов в буфере, например, -1 длиной 10 считаем разделителем символов, +1 длиной 3 и больше – тире, и т. д.

Затем распознаем то, что получилось между разделителями символов.

[vlad]

Итак задачка:

Во-первых, я уверен на 99%, что задачка имеет простое/шаблонное аппаратное решение. Что-то типа сдвигового регистра (по-моему так называется) + минимальная аналоговая обвязка для сглаживания/нормирования сигнала. Если уж ты взял в руки паяльник - почитай там какой-нибудь ликбез по цифровой электронике.

Во-вторых, все упирается в характер конкретного сигнала (и помех). Т.е., тебе самому медитировать/экспериментировать над этим сподручнее. Ну и ликбез по цифровым фильтрам (хотя ты вроде и так в этой теме хорошо разбираешься). Понятно, что там будет память на сколько-то последних сэмплов + эвристики.

Оберон здесь, как и другой ЯП - постольку поскольку. Ты давай пиши, а эксперты-оберонщики поправят

[valexey_u]

Итак задачка:

Во-первых, я уверен на 99%, что задачка имеет простое/шаблонное аппаратное решение. Что-то типа сдвигового регистра (по-моему так называется) + минимальная аналоговая обвязка для сглаживания/нормирования сигнала. Если уж ты взял в руки паяльник - почитай там какой-нибудь ликбез по цифровой электронике.

У меня пока нет паяльника :-)
И нет, простого аппаратного решения тут нет. Собственно вот пример работы детектора:
http://m.youtube.com/watch?v=7wdtTxa_YSc

Как видим, там та же самая ручная подстройка уровня. Единственное что у них лучше - сигнал можно выделять не только по амплитуде, но и по частоте. А у нас тут информации по частоте нет.

Во-вторых, все упирается в характер конкретного сигнала (и помех). Т.е., тебе самому медитировать/экспериментировать над этим сподручнее. Ну и ликбез по цифровым фильтрам (хотя ты вроде и так в этой теме хорошо разбираешься). Понятно, что там будет память на сколько-то последних сэмплов + эвристики.

Да не, у меня на самом деле есть какое-то решение. :-)

Кроме того, с упрощениями 1,2,3 та часть задачи, на которой вы все сосредоточились, скорее всего оказывается решена Ильей. Нужно лишь дополнить его решение декодером.

Оберон здесь, как и другой ЯП - постольку поскольку. Ты давай пиши, а эксперты-оберонщики поправят

А вот и нет. У Оберона я вижу ряд нюансов, и мне интересно как они будут отражены в коде тех, кто умеет на нем писать.

PS. Господа, вы переусложняете и откровенно игнорируете условия задачи :-)

[valexey_u]

Я никогда не занимался цифровой фильтрацией, поэтому то, что изложу – взгляд абсолютного дилетанта.

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

Ну-у. В принципе да, почему нет? С другой стороны этот меандр может быть весьма высокочастотным, либо низкочастотным и при этом не кратным нашим 100 сэмплам.

Поэтому входной сигнал надо распараллелить – один канал должен восстанавливать этот исходный меандр, второй – фильтровать исходный сигнал, в частности, убирать постоянную и низкочастотную составляющую. Чтобы отсчеты были положительными и отрицательными, и, в среднем, не плавали вверх-вниз относительно нуля.

Ну, в первой версии от нас этого не требуется, а во-второй версии, да. Фильтрацию можно прикрутить. Но у нас есть проблема - характерные частоты "помех' (плавание уровня) в принципе не далеко лежат от частоты полезного сигнала. Поэтому полностью фильтрацией избавиться от плавания туда-сюда не получится.

Затем, с помощью КА, измеряем длительности непрерывных отсчетов в буфере, например, -1 длиной 10 считаем разделителем символов, +1 длиной 3 и больше – тире, и т. д.

Затем распознаем то, что получилось между разделителями символов.

А вот этой части нам сейчас как раз и не хватает. На обероне.

[valexey_u]

Кстати, вскрытие показало, что первый образец (там где хорошо) был закодирован невалидно (там совершенно не правильные интервалы внутри буквы и между буквами). Так что вот новый образец, где уровень в общем то не плавает, и при этом закодирован верно. Точнее даже два образца (первый - одно слово, второй - два слова).

[valexey_u]

Оставлю ка я эту картинку здесь. Вдруг кто не видел еще:

[Илья Ермаков]

Хе, неожиданное открытие
Я всегда считал, что код Морзе префиксный - и паузы между буквами не нужны