Я знаю, что это давно, но вот некоторые заметки по математике с фиксированной запятой из библиотеки, которую я написал.
Обзор использования математики с фиксированной точкой
Ключевые идеи, которые возникают при реализации математических областей квантованного типа или типа DSP, включают в себя, как представлять дробные единицы и что делать, когда математические операции вызывают переполнение целочисленных регистров.
Плавающая точка (числа с плавающей запятой или двойные типы в C, C ++) чаще всего используются для представления дробных единиц, но они не всегда доступны (без аппаратной поддержки или на младших микроконтроллерах без поддержки программного обеспечения библиотеки). Если аппаратная поддержка недоступна, то с помощью библиотеки программного обеспечения может быть предоставлена плавающая точка, однако, как правило, эти библиотеки на порядок медленнее, чем аппаратные реализации. Если программист умен, вместо программного числа с плавающей запятой можно использовать целочисленную математику, что приводит к гораздо более быстрому коду. В этих случаях дробные единицы могут быть представлены целочисленными регистрами (short, int, long), если используется коэффициент масштабирования.
Масштабирование и обтекание
При создании масштабируемых целочисленных представлений чисел возникают следующие две проблемы:
Масштабирование - программист должен отслеживать дробный коэффициент масштабирования вручную, тогда как при использовании чисел с плавающей запятой компилятор и библиотека с плавающей запятой делают это для программиста.
Переполнение и Обтекание - при добавлении двух больших чисел результат может быть больше, чем может поместиться в целочисленное представление, что приведет к ошибкам обтекания или переполнения. Хуже того, эти ошибки могут остаться незамеченными в зависимости от настроек предупреждений компилятора или типов операций. Например, возьмите два 8-битных числа (обычно символ в C / C ++)
символ а = 34, б = 3, с;
// и вычисляем
* * 1016 с = а * Ь;
// Умножим их вместе, и результат получится равным 102, что по-прежнему соответствует 8-битному результату. Но
// что происходит, если b = 5?
с = A * B; // реальный ответ 170, но результат будет -86
Этот тип ошибки называется переполнением или переносом ошибки и может быть обработан несколькими способами. Мы могли бы использовать более крупные целочисленные типы, такие как шорты или целые числа, или мы могли бы заранее проверить числа, чтобы увидеть, приведет ли результат к переполнению. Что лучше? Это зависит от обстоятельств. Если мы уже используем самый большой натуральный тип (например, 32-разрядное целое число в 32-разрядном ЦП), то нам, возможно, придется проверить значение до выполнения операции, даже если это повлечет за собой некоторое снижение производительности во время выполнения.
потеря точности
Истинные представления с плавающей запятой могут поддерживать относительно произвольный набор точности в диапазоне операций, однако при использовании математики с фиксированной запятой (масштабируемой) процесс масштабирования означает, что мы в конечном итоге выделяем часть доступных битов с желаемой точностью. Это означает, что математическая информация, которая меньше коэффициента масштабирования, будет потеряна, что приведет к ошибке квантования.
Пример простого наивного масштабирования. Давайте попробуем представить число 10.25 целым числом, которое мы могли бы сделать, например, умножить значение на 100 и сохранить результат в целочисленной переменной. итак имеем:
10.25 * 100 ==> 1025
Если бы мы хотели добавить другое число, скажем, 0,55, мы бы взяли 1,55 и тоже увеличили бы его на 100. так что
0,55 * 100 ==> 155
Теперь, чтобы сложить их вместе, мы добавим целые числа
1025 + 55 ==> 1070
Но давайте посмотрим на это с помощью некоторого кода:
void main (void)
{
int myIntegerizedNumber = 1025;
int myIntegerizedNumber2 = 155;
int myIntegerizedNumber3;
myIntegerizedNumber3 = myIntegerizedNumber1 + myIntegerizedNumber2;
printf("%d + %d = %d\n",myIntegerizedNumber1,myIntegerizedNumber2,myIntegerizedNumber3);
}
Но теперь наступает первый из нескольких вызовов. Как мы имеем дело с целыми и дробными частями? Как мы отображаем результаты? Компилятор не поддерживается, мы, как программист, должны разделять целочисленные и дробные результаты. Приведенная выше программа печатает результат как 1070, а не 10.70, потому что компилятор знает только о тех целочисленных переменных, которые мы использовали, а не о наших намеченных масштабированных определениях.
Мышление в степенях 2 (основание)В предыдущем примере мы использовали математику base10, которая, хотя и полезна для людей, не является оптимальным использованием битов, поскольку все числа в машине будут использовать двоичную математику.Если мы используем степени двойки, мы можем указать точность в терминах битов вместо base10 для дробной и целочисленной частей, и мы получим несколько других преимуществ:
Простота записи - например, с 16-битным целым числом со знаком (обычно это сокращение от C / C ++), мы можем сказать, что это число «s11.4», что означает его число, которое подписано с 11 битами целого числа и 4 битами дробной точности.Фактически, один бит не используется для представления знака, но число представляется как формат дополнения до 2.Однако фактически 1 бит используется для представления знака с представленной точки точности.Если число не подписано, то мы можем сказать, что оно равно 12,4 - да, то же самое число теперь имеет 12 целочисленных битов точности и 4 бита дробного представления.Если бы мы использовали математику base10, такое простое сопоставление было бы невозможным (я не буду вдаваться во все возникающие проблемы с base10).Хуже того, потребуется выполнить много операций деления на 10, что является медленным и может привести к потере точности.
Простота изменения радиуса точности.Использование оснований base2 позволяет нам использовать простые сдвиги (<< и >>), чтобы перейти от целого числа к фиксированной точке или перейти от различных представлений с фиксированной точкой.Многие программисты предполагают, что основание радиуса должно быть кратным байту, например, 16 или 8 бит, но на самом деле использование достаточной точности и не более (например, 4 или 5 бит для небольших графических приложений) может дать гораздо больший запас, поскольку целая часть получит оставшиеся биты.Предположим, нам нужен диапазон +/- 800 и точность 0,05 (или 1/20 в десятичном виде).Мы можем подогнать это к 16-битному целому числу следующим образом.Первый бит выделяется для подписи.Это оставляет 15 бит разрешения.Теперь нам нужно 800 отсчетов дальности.Log2 (800) = 9,64. Итак, нам нужно 10 бит для целочисленного динамического диапазона.Теперь давайте посмотрим на дробную точность, нам нужно log2 (1 / (0,05)) = 4,32 бита, округленное до 5 бит.Таким образом, мы могли бы в этом приложении использовать фиксированный радиус s10,5 или 10-битное целое число со знаком и 5-битное дробное разрешение.Еще лучше, он все еще вписывается в 16-битное целое число.Теперь есть некоторые проблемы: хотя дробная точность составляет 5 бит (или 1/32 или около 0,03125), что лучше, чем требование 0,05, она не идентична, и поэтому с накопленными операциями мы получим ошибки квантования.Это может быть значительно уменьшено путем перехода к большему целому и основному числу (например, 32-битное целое число с более дробными битами), но часто это не является необходимым, и манипулирование 16-битными целыми числами гораздо более эффективно как в вычислениях, так и в памяти для небольших процессоров.Выбор этих целочисленных размеров и т. Д. Должен быть сделан с осторожностью.Несколько замечаний о точности с фиксированной точкой При сложении чисел с фиксированной точкой важно выровнять их радиальные точки (например, вы должны добавить 12,4 и 12,4 числа или даже 18,4 + 12,4 + 24,4, когда целая часть представляет количество используемых битов, а нефизический размер объявленного целочисленного регистра).Теперь, и здесь начинается некоторая хитрость, в результате, чисто говоря, 13,4 числа!Но это становится 17 битами - поэтому вы должны быть осторожны, чтобы следить за переполнением.Один из способов - поместить результаты в больший 32-битный регистр с точностью 28,4.Другой способ - проверить и посмотреть, установлены ли на самом деле старшие биты любого из операндов - если нет, то числа можно безопасно добавлять, несмотря на ограничения точности ширины регистра.Другим решением является использование насыщающей математики - если результат больше, чем может быть занесено в регистр, мы устанавливаем для результата максимально возможное значение.Также обязательно следите за знаком.Добавление двух отрицательных чисел может привести к переносу так же просто, как два положительных числа.
Интересная проблема, возникающая при проектировании конвейеров с фиксированным радиксом, заключается в том, чтобы отслеживать, какая часть доступной точности фактически используется. Хотя вы, возможно, используете это, это особенно верно для таких операций, как преобразования Фурье и т. П., Которые могут привести к тому, что некоторые ячейки массива будут иметь относительно большие значения, в то время как другие будут иметь почти нулевую математическую энергию.
Некоторые правила: добавление 2 M битовых чисел приводит к результату точности M + 1 бит (без проверки на переполнение) Добавление N M битовых чисел приводит к результату точности M + log2 (N) бит (без проверки на переполнение)
Умножение числа бит M на число бит N приводит к результату точности бит N + M (без проверки на переполнение)
Насыщенность может быть полезна в некоторых обстоятельствах, но может привести к снижению производительности или потере данных.
Добавление ...
При сложении или вычитании фиксированных чисел радиуса точки радиуса должны быть предварительно выровнены. Например: для добавления A используется число s11.4, а B - число 9.6. Нам нужно сделать выбор. Мы могли бы переместить их сначала в более крупные регистры, скажем, в 32-битные регистры. в результате A2 - число s27.4, а B2 - число s25.6. Теперь мы можем безопасно сдвинуть A2 вверх на два бита, так что A2 = A2 << 2. Теперь A2 - это число s25.6, но мы не потеряли никаких данных, потому что старшие биты первого A могут быть сохранены в большем регистре без потери точности. </p>
Теперь мы можем добавить их и получить результат C = A2 + B2. В результате получается число s25.6, но на самом деле точность равна 12,6 (мы используем большую целую часть, которая получается из A, которая составляет 11 бит, и большую дробную часть, которая получается из B, которая составляет 6 бит, плюс 1 бит из операции сложения ). Таким образом, это число s12.6 имеет 18 + 1 бит точности без потери точности. Но если нам нужно преобразовать его обратно в число с 16-битной точностью, нам нужно будет сделать выбор в отношении того, какую долю точности сохранить. Самый простой способ - сохранить все целочисленные биты, поэтому мы сдвигаем C на достаточное количество битов, чтобы знаковые и целочисленные биты помещались в 16-битный регистр. Таким образом, C = C >> 3 приводит к числу s12.3. Пока мы отслеживаем основную точку, мы будем сохранять точность. Теперь, если бы мы проверили A и B заранее, мы могли бы узнать, что мы можем сохранить больше дробных бит.
Умножение ...
Умножение не требует выравнивания радиуса перед операцией. Предположим, у нас есть два числа, как в нашем примере добавления. A - это число с точностью s11.4, которое мы переместили в A2, теперь это большой регистр s27.4 (но все еще используется бит s11.4). B - это число s9.6, которое мы переходим в B2, теперь это большой регистр s25.6 (но все еще используется число s9.6). C = A2 * B2 приводит к тому, что C является числом s20.10. обратите внимание, что C использует весь 32-битный регистр для результата. Теперь, если мы хотим получить результат обратно в 16-битный регистр, мы должны сделать несколько трудных решений. Во-первых, у нас уже есть 20 битов с целочисленной точностью, поэтому любая попытка (без учета количества фактически используемых битов) согласовать результат с 16-битным регистром должна привести к некоторому типу усечения. Если мы возьмем верхние 15 битов результата (+1 бит для точности знака), мы, программисты, должны помнить, что это увеличило на 20-5 = 5 битов точности. Поэтому, даже если мы сможем разместить верхние 15 бит в 16-битном регистре, мы потеряем нижние 16 битов точности, и мы должны помнить, что результат масштабируется на 5 бит (или целое число 32). Интересно, что если предварительно протестировать и A, и B, мы можем обнаружить, что, хотя они имеют указанное входящее прецизионное значение, записанное в записанном виде, они могут на самом деле не содержать этого числа живых, установленных битов (например, если по соглашению программиста A является числом s11.4, но его фактическим значением равно целому числу 33 или фиксированному основанию 2 и 1/16, тогда у нас может не хватить столько битов для усечения в C).
(также библиотека здесь: https://github.com/deftio/fr_math)