Таблица поиска

Большинство микроконтроллеров общего назначения не имеют модуля FPU (англ. floating point unit), ускоряющего операции с плавающей запятой. Однако не все задачи можно свести к целочисленным расчетам — работать с вещественными числами всё же приходится. Если устройство бюджетное, то, вероятнее всего, тактовая частота у используемого МК невелика. Для ускорения сложных расчетов часто прибегают к так называемой таблице поиска (англ. lookup table), которая содержит заранее просчитанные значения функции.

Допустим, нам нужны значения синуса при целочисленных углах α ∈ [0;90] градусов. Рассчитать их можно с помощью рядов, используя численный метод.

sin(x) = x — x³ / 3! + x⁵ / 5! + …

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

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

float sin(uint8_t angle) {
    // conversion from radians to degrees
    float a = (float)angle * 3.1415926f / 180.0f; 
    return (float) (a - (a * a * a) / 6.0f + (a * a * a * a * a) / 120.0f);
}

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

При маленьких значениях угла поведение функции синуса похоже на линейную функцию y(x) = x. Этим свойством часто пользуются физики при расчётах. Другими словами, если нужно повысить точность — не обязательно увеличивать таблицу, можно хранить лишь точки в нужных местах, а значение при малых углах брать равным самому углу.

В примере приведена таблица с float-значениями. Но это не всегда нужно: в регистр ЦАП нужно записывать целочисленное значение, поэтому в зависимости от ситуации имеет смысл отмасштабировать значения.

float sin(uint8_t a) {
	static const float sin_table[] = {
    	0.0000f, 0.0175f, 0.0349f, 0.0523f, 0.0698f,
    	0.0872f, 0.1045f, 0.1219f, 0.1392f, 0.1564f,
    	// ...
    	1.0000f,
    };
    return sin_table[a];
}

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

Рассмотрим другой пример, более сложный. Допустим, в качестве датчика температуры в устройстве используется что-то аналоговое, например NTC-термистор. Его сопротивление зависит от температуры и описывается уравнение Стейнхарта-Харта:

1 / T = A + B · ln(R) + C · ln³(R)

В реальности нет никакого практического смысла пересчитывать значения АЦП в сопротивление, а затем подставлять его в это уравнение. Создавать массив из 1024 просчитанных температур (для 10-битного АЦП) также не всегда возможно. В отличие от предыдущего примера, в данном случае можно заменить «тяжелую» функцию расчета на более «легкую», применив ту же таблицу поиска и используя кусочно-линейную аппроксимацию (англ. piecewise linear function).

Разбив нелинейную функцию на 32 линейных участка, можно более или менее точно описать функцию прямыми. Далее, получив значение АЦП, очень легко определить участок, которому принадлежит точка (интервал [a;b]). Осталось рассчитать положение данного отсчета на прямой.

f(x) = a + (b — a) · x / 32

Пример реализации представлен ниже.

uint32_t NTC_ADC2Temperature(uint32_t adc_value) {
    static const uint32_t ntc_table[33] = {
        // ...
    };
    static const uint32_t a, b;
    
    a = ntc_table[(adc_value >> 5)    ]; // >> 5 => / 32
    b = ntc_table[(adc_value >> 5) + 1];
    // adc_value & 0x001F -- interval [a; b]
    return a + ((b - a) * (adc_value & 0x001F)) / 32; 
};

Помните, что операция деления эффективно заменяется на операцию смещения (которая выполняется за один такт), если речь идет о степенях двойки. В примере по этой причине размер таблицы выбран равным 32.