Генерация синуса

[Barmaley_m]

Достаточно сделать отрицательную обратную связь, и возникают гармонические колебания. 49 байт.

(зануда моде он) Я бы не называл это отрицательной обратной связью. Тут скорее можно говорить о рекурсивном фильтре второго порядка. В общем виде такой фильтр описывается формулой:

a0*y[i] = b0*x[i] + b1*x[i-1] + b2*x[i-2] - a1*y[i-1] - a2*y[i-2]

При отсутствии входного сигнала (все x[i]=0) выходной сигнал такого фильтра может быть одним из следующих:

1) Постоянный уровень (напр. при a0=1, a1=-1, a2=0)
2) Затухающая экспонента (напр. при a0=1, a1=-0.9, a2=0)
3) Нарастающая экспонента (напр. при a0=1, a1=-1.1, a2=0)
4) Постоянная по уровню синусоида (напр. при a0=1, a1=-2..2, a2=1]
5) Затухающая по экспоненте синусоида
6) Нарастающая по экспоненте синусоида

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

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

a0*z^2 + a1*z + a2 = 0

Если оба корня (z1, z2) действительные - выходной сигнал будет постоянным либо экспонентой. Если корни комплексные - то будет синусоида (затухающая, нарастающая или постоянная). При этом, если корни находятся внутри круга abs(z)<1 - то фильтр является стабильным. Если лежат на круге abs(z)=1 - то условно-стабильным. Если за пределами круга - то нестабильным.

В предложенной выше формуле для генерации синуса:
y[i] = k*y[i-1] - y[i-2]

у нас коэффициенты равны соответственно a0=1, a1=k, a2=1. Если k лежит в пределах -2..2 - то получается два комплексных корня на единичной окружности, т.е. как раз то, что и требуется.
(зануда моде офф)

На кодах калькулятора может получиться ещё меньше.

На кодах калькулятора можно сразу вызвать процедуру sin из ПЗУ, кстати!

[Titus]

(зануда моде он) Я бы не называл это отрицательной обратной связью. Тут скорее можно говорить о рекурсивном фильтре второго порядка. В общем виде такой фильтр описывается формулой:

a0*y[i] = b0*x[i] + b1*x[i-1] + b2*x[i-2] - a1*y[i-1] - a2*y[i-2]

Надо заметить, что по этому принципу построен фильтр Герцеля, который считается самой быстрой реализацией ДПФ для небольшого числа полос.

[Barmaley_m]

Да, Герцель - это хорошая вещь. Я с помощью этого метода делал на микроконтроллере детектор сигналов ДТМФ.

[Titus]

Да, Герцель - это хорошая вещь. Я с помощью этого метода делал на микроконтроллере детектор сигналов ДТМФ.

Какое совпадение) Я делал тоже самое)
Что самое интересное, реально самый быстрый ДПФ. Где-то 5-6 тактов на итерацию, на сколько я помню на Cortex-M0.

[introspec]

Достаточно сделать отрицательную обратную связь, и возникают гармонические колебания. 49 байт. На кодах калькулятора может получиться ещё меньше.

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

---------- Post added at 21:23 ---------- Previous post was at 21:19 ----------

Кстати, вот ещё для коллекции ссылка от Serzhsoft:
http://cpu.untergrund.net/adv/tutor/sin_9.html
Он описывает уже немного устарелый морально генератор на дельтах (119 байт), а так же генератор на основе калькулятора (39 байт, 15 секунд работы).

[Barmaley_m]

Генератор синуса на рекуррентной формуле имеет 2 источника погрешности:
1) погрешность в коэффициенте k. Получив округленное значение k, следует вычислить реальный период синуса и прикинуть, достаточна ли точность
2) погрешность при округлении во время текущих вычислений. При определенных условиях она может привести к затуханию сигнала или же наоборот, нестабильности (процесс пойдет вразнос). Нужно испытывать. Чем больше разрядов используется для представления y[i] - тем лучше.
При использовании кодов калькулятора не для вычисления синусов, а для реализации рекуррентной формулы есть шанс повысить ее точность за счет обоих приведенных выше факторов. Может оказаться быстрее, чем вызывать sin.

[introspec]

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

[Barmaley_m]

Только что поигрался с Матлабом. Без округления рекуррентная формула работает безупречно. С округлением искажается амплитуда сигнала и его период (даже несмотря на точное значение k). И это при 16 битах разрешения!

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

[introspec]

Без округления рекуррентная формула не может не работать!
Всё же, раз это 8-и битный синус, довольно важно с моей точки зрения сохранить как можно больше точности (поэтому я и шёл всё же от табличных данных).
В вариант с генерацией нескольких периодов я пока не очень верю, скорее всего по этим данным придётся интерполировать, что означает сравнительно сложный код и дополнительный источник ошибок.

[Barmaley_m]

Да, это помогает!

Только количество периодов не должно делиться на 2. Иначе будут генерироваться повторения. Точность возросла значительно! Я сгенерировал только что 13 периодов косинуса при разрешении данных 8 бит. Вышло очень даже неплохо.