| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Декодирование DTFM [D3, D5, Win95/98, WinXP]
Вадим © (2004-05-22 17:34:00)Здравствуйте. Задача стоит такая. На линейный вход приходит последовательность цифр в виде DTFM. Необходимо в реальном времени преобразовывать это снова в цифры. DTFM представляет собой смесь двух частот (одной нижней и одной верхней) из следующего ряда: 697, 770, 852, 941 (нижние), 1209, 1336, 1477 и 1633 Гц (верхние). Что позволяет закодировать 16 символов: 1, 2, 3, A, 4, 5, 6, B, 7, 8, 9, C, *, 0, #, D. Таким образом, проблема сводится к тому, чтобы обнаружить наличие или отсутствие данных частот во входном сигнале, но как это сделать не представляю… В обсуждении темы fft.dll ( http://www.delphimaster.ru/cgi-bin/forum.pl?id=1082816087&n=7) видел процедуру, делающую БПФ, и по этому ( http://www.delphikingdom.com/asp/answer.asp?IDAnswer=5489) адресу было что-то подобное, но как этим воспользоваться до меня не доходит. Либо есть более простой выход?
Jeer (2004-07-06 12:53:00) [1]http://algcom.nm.ru/dtmf.zip
Тест DTMF-методов.
В этой версии оставлены только два (простейший и классический Герцель-методы).
Jeer (2004-07-05 18:28:00) [2]Завтра-послезавтра выложу.
Заскочил на минутку.
Насчет исходников - не обессудь, не будет. Не в моих правилах подавать ложечку в ротик, да еще и пережевывать.
Хочешь учиться - помогу, но не более.
Есть такой необходимый, но недостаточный параметр (да простят меня Дамы) - "жопочасы".
Ты их должен наработать:)
Вадим (2004-07-05 14:44:00) [3]To Jeer. Так как на счёт утилитки?
Вадим (2004-06-30 23:21:00) [4]Jeer © (30.06.04 19:56) [28]
> Если интересно - могу выложить тестовую утилитку по DTMF
Ещё бы, если это исходник конечно интересно!
Jeer (2004-06-30 20:12:00) [5]Тестовый сигнал символа "1" ( частоты 697 и 1209 Гц )
http://algcom.nm.ru/snap_01.png
Спектр по Герцелю по ф-ле (3)
http://algcom.nm.ru/snap_02.png
Предварительная обработка окном Blakman
http://algcom.nm.ru/snap_03.png
Спектр обработанного сигнала
http://algcom.nm.ru/snap_03.png
Jeer (2004-06-30 19:56:00) [6]Jeer © (15.06.04 16:38) [26]
Вы ошибаетесь насчет двух последних ячеек Buffer.
Результат определяется по двух последним отсчетам полученным
в результате НАКОПЛЕНИЯ данных в ячейках (переменных) Qk и Qkn1.
Так, что здесь - все нормально.
Я уже упомянул, что стоит рассматривать более корректную реализацию по ф-ле (3). Там все однозначно.
Если интересно - могу выложить тестовую утилитку по DTMF.
Там все нагладно видно.
Там использованы оба варианта определения спектра - по формулам (2) и (3).
Кроме того, для улучшения качества спектрального анализа (устранения явления Гиббса) используется "оконное" взвешивание с различными окнами (Хеннинг, Каппелини, Ханн и тп)
В этой утилите есть возвожность предобработки серии с помощью
десятка различных окон - результат хорошо заметен.
Вадим (2004-06-30 16:13:00) [7]Jeer © (15.06.04 16:38) [26]
> >В итоге Result имеет непредсказуемое значение, зависящее от фазы сигнала в последних ячейках буфера
Это у Вас:)
Почему же только у меня?! Я делал по образцу, предложенному Вами. И, так как Resultвычисляется из Qknи Qkn1, которые в свою очередь являются расчитанными из двух последних ячеек массива Buffer, то, и у Вас, и у других, кто повторит этот алгоритм, результат будет зависеть от ДВУХ ПОСЛЕДНИХ ЯЧЕЕК БУФЕРА! Я, конечно, ценю Вашу попытку мне помочь и чему-то научить, но, в таком случае уж будьте добры не зазнавайтесь и дайте правильную информацию.
Jeer (2004-06-15 16:38:00) [8]Ну, вот вы уже начали думать, это хороший признак.:)
>Ну, хорошо, допустим понятно, что k показывает номер гармоники
Без всяких "ну" и "допустим понятно" - это так и есть.
>Таким образом, очевидно, что "за пределы разрешающей способности"
выходят частоты нижней группы при малых N!
Вы не о том.
При 320 отсчетах ширина спектральной линии dF = 8000/320 = 25 Гц.
В соответствии с "Рекомендациями.." частота может "плавать" от среднего значения до 1.5%, а это дает на наивысшей частоте 1633 Гц возможное отклонение до +/- 25 Гц, что превышает ширину спектральной линии.
Т.е. искомая частота может быть идентифицирована как неверная.
Одним из вариантов, является снижение длины выборки, что расширяет спектральную линию.
В примере приведено N=205
Это дает ширину линии 8000/205 = 39 Гц. Наложение на соседнюю линию все равно есть, но это компромисс.
>Во-первых даже я:-) заметил там грубую ошибку
Это похвально:)
Там еще пара ошибок и тоже "грубых".
>Во-вторых зависимость Qkn от времени носит синусоидальный, а не накопительный характер.
Синусоидальный линейно нарастающий, а это и есть накопление.
>В итоге Result имеет непредсказуемое значение, зависящее от фазы сигнала в последних ячейках буфера
Это у Вас:)
>Как же тогда выявлять сигнал?
Если бы Вы просканировали по частоте от искомой и, например, выше, то увидели бы, что отклик функции Герцеля имеет единственный максимум в одной полуплоскости и много максимумов в другой, причем зависимость носит синусоидальный характер с экпоненциальным затуханием. Этот единственный максимум находится на искомой частоте.
Отсюда понятно, что и как искать.
>В-третьих мне до сих пор не ясно, почему мы обязаны искать частоты именно из частотной сетки, а не те, что нужны?
Потому, что Вы до сих пор не поняли главного: это ДИСКРЕТНОЕ преобразование Фурье и методически правильно
работать по сетке дискретных частот.
Можно представить себе ДПФ как набор из N узкополосных фильтров, однако частотная характеристика их не идеально прямоугольная, а с перекрытием. Поэтому частоты не попадающие точно в сетку тоже, естественно, будут "звенеть" на смежных гребенках.
>Кстати ещё одно странно для меня - везде написано, что для преобразования Фурье размер буфера должен быть степенью двойки, а в алгоритме Герцеля совсем не обязательно...
Это "странно" только для Вас, т.к. Вы еще только начинаете в данном вопросе "барахтаться".
ДПФ не привязано к числу точек никак, с другой стороны, действительно большинство РЕАЛИЗАЦИЙ БПФ чаще всего привязано к степени 2,а почему - читайте литературу или сами догадайтесь.
Могу еще добавить что есть быстрые преобразования основанные на числах Мерсенна, Фибоначчи.
Основная операция "свертка" весьма эффективна с их использованием.
Есть, наконец, другие ортогональные базисные функции (несинус), например Уолша, где тоже имеет место быть быстрое преобразование дискретных функций.
Так, что "тапочки отсмеялись, а носочки мои еще посмеиваются" :)
Вадим (2004-06-12 17:54:00) [9]Jeer © (09.06.04 16:22) [23] (дополнительно)
Ну, хорошо, допустим понятно, что kпоказывает номер гармоники из спектральной сетки, разрешающая способность которой зависит от N. И здесь уже "насмешили тапочки" именно Вы, т.к. в описании алгоритма Герцеля, на которое Вы же дали ссылку, говорится примерно следующее: "значение Nдолжно выбираться исходя из двух противоречивых условий: во-первых, оно должно быть достаточно малым, чтобы успеть различить кратковременные сигналы; во-вторых, достаточно большим, для обеспечения разрешающей способности, т.к. чем больше N, тем лучше эта самая способность". Таким образом, очевидно, что "за пределы разрешающей способности" выходят частоты нижнейгруппы при малых N!
Теперь на счёт "сладкой пилюли". Во-первых даже я:-) заметил там грубую ошибку. Вместо:
for i:=0 to Length(Buffer) do begin
должно быть
for i:=0 to Length(Buffer)-1 do begin
думаю понятно почему. Во-вторых зависимость Qknот времени носит синусоидальный, а не накопительный характер. В итоге Resultимеет непредсказуемое значение, зависящее от фазы сигнала в последних ячейках буфера. Как же тогда выявлять сигнал? В-третьих мне до сих пор не ясно, почему мы обязаны искать частоты именно из частотной сетки, а не те, что нужны? Ведь в алгоритме, предложенном Евгением, искомые частоты так же "не попадают" в сетку и, тем не менее, прекрасно определяются (размер буфера ( N) - 256). В то же время, если искать "по сетке", то действительно, получается не очень хорошо. Кстати ещё одно странно для меня - везде написано, что для преобразования Фурье размер буфера должен быть степенью двойки, а в алгоритме Герцеля совсем не обязательно...
Ну, что, теперь я прав, или уже вместе с тапочками и носки засмеялись? :-)
Вадим (2004-06-11 01:08:00) [10]Jeer © (09.06.04 16:22) [23]
Это, конечно, здорово, но мне не совсем ясно следующее:
> Так как длительность одного сигнала должна быть не менее
> 40 ms, то мы имеем N = 0.04*8000 = 320 отсчетов.
> Однако это приводит к выходу частот верхней группы за пределы
> разрешающей способности.
Правильно ли я понял, что искомая "омега" вычисляется из отношения коэффициента kк кол-ву отсчётов N, и тогда полученная "омега" будет (или должна) отличаться от стандартной (из сетки DTFM) не более, чем на 1,5%? Но зачем вообще нужно подбирать эти k, если в формулу можно просто подставить искомую частоту и частоту дескритизации, как это сделано в примере? А если без kне обойтись, то из какого ряда их выбирать?
Jeer (2004-06-09 16:22:00) [11]Вадим © (09.06.04 00:44) [21]
Это и плохо, т.к. вы полезли в цифровую обработку, а здесь надо иметь некоторый базис, чтобы в результате Ваша задача получила хотя бы решение.
Для занятий DSP безусловно необходимо знание математики, в том числе.
По той ссылке, что я Вам дал, вполне доступно описан алгоритм Герцеля. Если Вы не умеете переходить от формульной записи к алгоритмической, то очень странно, что Вы вообще взялись за это дело:)
Попробуем поправить вместе с Вами положение вещей, если Вы не против, конечно.
Итак, DTMF - способ тонального кодирования символов. (CCITT Recommendation Q.23 и Q.24)
Для представления одного символа используются две частоты из двух групп частот, в каждой из которых
по четыре частоты, итого: алфавит состоит из 16-ти символов.
Для декодирования символа необходимо определить мощности восьми частот и две преобладающие (упрощенно).
Могут быть использованы методы частотной фильтрации, основанные на полосовых рекурсивных или нерекурсивных фильтрах, а также методы основанные на спектральных преобразованиях, например - преобразовании Фурье (ПФ).
Жан Фурье высказал идею о том, что любой сигнал может быть представлен в виде суммы гармонических сигналов.
По сути ПФ - это способ перехода от описания сигнала во временном домене к описанию сигнала в частотном домене. Обратный способ перехода от частотного домена ко временному называется обратным ПФ (ОПФ).
Все сигналы в природе являются "аналоговыми", т.е. непрерывно изменяющимися.
Однако с появлением компьютерной техники, над естественными сигналами стала выполняться дискретизация - приведение сигнала к логической форме представления набором дискрет как во времени, так и по амплитуде.
Для таких оцифрованных (дискретных) сигналов тоже существует ПФ и называется оно ДИСКРЕТНЫМ (ДПФ).
В форме прямой реализации ДПФ требует большого числа операций (число комплексных умножений пропорционально квадрату длины выборки N*N).
Для снижения вычислительных затрат были разработаны ряд методов, получившие общее название быстрого ПФ (БПФ).
(в англо-язычной литературе Fast Fourie Transform - FFT).
Тем не менее, применение БПФ к задачам DTMF приводит к большим вычислительным затратам, т.к. вычисление ДПФ
для отдельных спектральных составляющих выполняется быстрее.
В общем случае, ДПФ работает с комплексными числами, но для случая DTMF восстановление фазовой информации неважно, поэтому можно обойтись только вещественным ДПФ.
Учитывая, что число анализируемых частот весьма мало (8) ряд ученых разработали ускоренные методы детектирования таких сигналов.
К одному из них относится метод Герцеля (Goertzel), основанный на ДПФ.
В основе лежит рекурсивное звено второго порядка.
Разностное уравнение:
Qk[n] = X[n] + Mk*Qk[n-1] - Qk[n-2] (1)
Yk[n] = Qk[n] - Wk*Qk[n-1] (2)
где
Mk = 2*Cos(2*PI*k/N)
Wk = exp(-(2*PI*k*/N)) - множители Фурье
X[n] - входной отсчет в дискретный момент времени n
Yk[n] - выходной отсчет (мощность k-ой гармоники)
Fs - частота дискретизации
N - число отсчетов.
Уравнение (1) вычисляется с частотой Fs,а уравнение (2) с частотой Fs/N, т.к. интересует только лишь
накопленное Yk[N-1] значение.
Величина Yk является комплексной, но т.к. фазовая информация не нужна, уравнение (2) для вычисления модуля трансформируется в (3)
|Yk[N-1]| = sqrt(Qk[N-1]^2 + Qk[N-2]^2 - Mk*Qk[N-1]*Qk[N-2]) (3)
Таким образом (1) и (3) являются искомым разностным уранением для вычисления мощности каждой из восьми частот.
Следующая важная задача - выбор N и Fs. Обычно Fs = 8 кГц.
Так как длительность одного сигнала должна быть не менее 40 ms, то мы имеем N = 0.04*8000 = 320 отсчетов.
Однако это приводит к выходу частот верхней группы за пределы разрешающей способности.
Поэтому необходимо решать задачу оптимального выбора N при заданном допуске различения частоты:
< 1.5% - есть частота
> 3.5 - нет частоты
Собственно, такие расчеты конечно же уже сделаны:)
Один вариантов:
N = 205
F k Mk
697 18 1.703275
770 20 1.635859
852 22 1.562297
941 24 1.482867
1209 31 1.163138
1336 34 1.008835
1477 38 0.790074
1633 42 0.559454
А вот и "сладкая пилюля" :)
Это несколько упрощенная формула.
Правда не сложно ?
function Goertzel(Buffer:array of Single; frequency, samplerate: single):single;
var
Qkn, Qkn1, Qkn2, Wkn, Mk : Single;
i : integer;
begin
Qkn:=0; Qkn1:=0; Qkn2:=0;
Wkn:=2*PI*frequency/samplerate;
Mk:=2*Cos(Wkn);
for i:=0 to Length(Buffer) do begin
Qkn2 = Qkn1; Qkn1 = Qkn;
Qkn =Buffer[i] + Mk*Qkn1 - Qkn2;
end;
Result:=(Qkn - exp(-Wkn)*Qkn1);
end;
Более точно - надо реализовать по ф-лам (1) и (3), но это домашнее задание:)
Damage (2004-06-09 13:39:00) [12]Ясное дело, исходник :))
Вадим (2004-06-09 00:44:00) [13]Jeer © (08.06.04 09:49) [19]
Ну, что ж, если я кого-нибудь насмешил, то это тоже не плохо. Хорошо, когда у кого-то поднимается настроение, даже если этот кто-то тапочки ;-)
А если серьёзно, то возможно Вы и правы, даже наверняка, и в преобразовании Фурье разобраться будет несложно, но мне сейчас не до этого (потребуется время, а есть более актуальные задачи). Тем более думаю, что теперь я смогу решить свою проблему и так (без обид!).
2 Damage:
А прога большая? И вообще это исходник или екзешник? Если екзешник, то я, конечно, не смогу "выцепить полезную функцию" оттуда. А так, посмотрел бы с удовольствием (и благодарностью).
Damage (2004-06-08 20:39:00) [14]2 Вадим:
Если интересует, могу на мыло кинуть прогу, которая спектр
WAV-файла рисует.
Не в реальном времени, конечно (там рукой двигать надо), но функцию полезную оттуда выцепить можно.
Jeer (2004-06-08 09:49:00) [15]Вадим © (04.06.04 23:56) [16]
Рекомендую ознакомится с теорией по преобразованию Фурье, это не так сложно как кажется, заодно не будете "смешить тапочки"
по повожу отличий БПФ, ДПФ и тп.
Evgeny V © (05.06.04 06:48) [17]
>..фактически и есть алгоритм Герцеля
Не знаю, не вникал:)
>когда определяем весьма ограниченное количество частот из >возможного спектра
Это как раз "наш" случай для DTMF (DTFM)
Anonym (2004-06-05 19:18:00) [16]http://teworks.com/dtmf.htm
Evgeny V (2004-06-05 06:48:00) [17]
> Jeer © (02.06.04 12:48) [15]
> Вадим © (04.06.04 23:56) [16]
То что я предложил,фактически и есть алгоритм Герцеля :-)) Быстрее оно только в данном случае, когда определяем весьма ограниченное количество частот из возможного спектра
Вадим (2004-06-04 23:56:00) [18]To Jeer: алгоритм Герцеля я посмотрел ещё когда Вы предложили его впервые (24.05.04 15:38). Но там ведь чистая математика, а разбираться в ней и, тем более, строить по этому алгоритму программу мне пока трудновато:-( Хотя, если он действительно даёт большой выигрыш по времени выполнения, то, возможно, придётся. Правда Вы сравниваете его с БПФ, а тут речь идёт о ДискретномПреобразовании, а оно тоже будет идти быстрее, чем БПФ.
В любом случае - всем спасибо за помощь.
Jeer (2004-06-02 12:48:00) [19]Еще раз - алгоритм Герцеля по приведенной ссылке.
http://factaee.elfak.ni.ac.yu/fu2k33/9mp.html
Это разновидность БПФ, ориентированная на распознавание
ограниченного числа частот в сигнале.
Имеет значительное преимущество в скорости (числе операций) перед обычным БПФ.
Вадим (2004-06-01 01:34:00) [20]To MegaVoltik
Спасибо, обязательно посмотрю, но у меня уже кое-что стало получаться из того, что предложил Евгений.
| |
Страницы: 