文档章节

一种高精度低复杂度的非线性函数定点计算方法

abcijkxyz
 abcijkxyz
发布于 2016/11/22 16:45
字数 1632
阅读 10
收藏 0
点赞 0
评论 0

 摘要 在嵌入式系统中,由于没有浮点运算单元,当涉及浮点运算的时候需要做定点化处理。查表法是一种常用的方法。表的大小直接关系到计算的精度和复杂度。如何在计算精度和复杂度之间取得平衡,是一个重要的问题。本文根据泰勒公式重新设计了一种新的计算方法。这种方法具有很高的精度,而计算复杂度低,表的大小也很小。

 

引言

在多媒体数字信号处理中,经常要涉及一些非线性函数的计算。例如求开方,非整数幂次运算,对数运算,三角函数的计算等。嵌入式系统中的C编译器虽然提供了相应的库函数,但是在计算密集的地方要实时实现是比较困难的。查表法是一种常用的优化方法。采用这种方法必须根据自变量的范围和精度事先制作一张查找表。显然,输入的范围越大,精度要求越高,则所需的表格越大,需要的存储空间越大。查表法所需的计算就是根据输入值确定表的地址,根据表的地址就可以得到相应的函数值,因而运算量小。查表法比较适合非线性函数是周期函数或已知非线性函数的输入的动态变化范围的情况。本文以对数函数的计算为例阐述计算的过程。

浮点数的规格化

查表法比较适合于周期函数或自变量的动态范围比较小的场合。对于像对数函数Log2这样的非线性函数,输入自变量为任意一个大于0的实数,输出为任意实数。输入和输出的变化范围都很大,直接做表就很困难。有没有一种好的方法来解决表的大小的问题呢?浮点数的规格化方法为我们提供了一种好的思路。

对于任意一个实数x, 根据浮点数的规格化方法,可以把它写成下面的表达式:

      x = a * 2^m

 其中, a 是介于[0.5,1.0]之间的一个纯小数,而m 是一个整数。则求对数可以写成:

      log2(x) = log2(a * 2 ^m) = m + log2(a)

于是,求x的对数,实际上只要求解a的对数就可以了。而a的取值范围为[0.5,1.0].

         如何求得m呢?在嵌入式平台上,一般都有特殊的指令来求解这个值。例如,在TMS320C2X/5X中有一条专门的指令NORM用来对ACC寄存器中的数进行规格书,而在ARM上,ARMV5指令集中有一条CLZ指令来求前导零计数。

查找表

         由于a的取值范围在[0.5,1.0]之间,因此在[-1.0,0.0]之间。输入和输出均可以用Q15的顶点格式表示。可以对a的范围进行均匀划分,每一段的对数值都取每个小区间的左端点的值,这样就可以制作一张查找表。

          下表是把区间[0.5,1.0]均分为10个小区间生成的查找表。

 

查表的地址计算如下:

例如输入为0.877,Q15的定点格式为0.877*2^15 = 28738.

表的地址: Index = ((28738 – 0.5 * 32768)/ (0.5/10))>>15 = 7.

于是,查表所得的对数值为上述第二个表的第7个值,即 -7683.

 

提高查表精度

         提高查表精度的一种简单的方法是采用线性插值的方法。既当计算所得的浮点index不是一个整数的时候,采用线性逼近的方法。而本文采取的方法是用泰勒公式展开的方法,可有效提高计算精度。本文采用下面的泰勒公式展开:

 

泰勒展开式中的2阶项分母里面的2也可以放到导数里面直接计算。x0是与查表地址相对应的输入变量值。这样,把它们做成表格如下:

 

 

仍以上面的输入为例:

0.877,Q15的定点格式为0.877*2^15 = 28738

查表所得的index地址为第7个值,即 -7683.

泰勒公式表达式中: x – x0 = 28738 – 27853 = 885

经过一阶导数计算值: ((x – x0) * 13904)>>13 = 1502;

经过二阶导数的计算值:((((x-x0)*(x-x0))>>15)*(-8179))>>13 = -23;

 

综上,直接查表得到的对数值为:-7683

加上一阶导数的查表计算值为:-7683+1502 = -6181;

加上二阶导数的查表计算值为:-6181+ (-23)= -6204;

 

直接浮点计算的精确值Log2(0.877) = -0.189351252217354

查一次表计算所得浮点值-7683/32768 = -0.234466552734375

查一阶导数表计算所得浮点数值-6181/32768 = - 0.188629150390625

查二阶导数表计算所得浮点数值-6204/32768 = -0.1893310546875

 

由此可见,经过二阶导数查表计算所得的结果精度已经很高了,而计算只需3个乘法。

 

再举一例:求解Log2(10000)

分析与解答:输入是一个很大的正整数。首先求解出指数部分。

                  

于是,只需要求解0.610351525的对数即可。0.610351525的Q15格式为

0.610351525*2^15 = 20000

 

计算index地址为 ((20000-0.5*2^15)* 20 )>>15 = 2;

直接查表得到的对数值为:-24149

加上一阶导数的查表计算值为:-24149+815 = -23334;

加上二阶导数的查表计算值为:-23334+ (-7)= -23341;

 

而Log2(0.610351525)的直接浮点运算值为-0.712287709,Q15的定点表示为

-0.712287709*2^15 = 23340.24365,与上述二阶导数查表计算的定点格式相等。

结语

      

本文所述的方法具有运算精度高,查表表格小的特点,计算复杂度低的特点。非常适合于在嵌入式设备上实现。

本文所阐述的方法,不仅仅适用于以2为底数的对数的计算,也适合任意底对数的计算。同时,也非常适合计算其它一大类非线性函数。例如,开方运算,非整数幂次运算等。不管哪种运算,都只需要4个表格,每个表格10个16位数的数据量,计算只需要3个乘法和3个加法和表格的加载操作。

 

注:本文系作者多年之前的一篇论文改编

 

 

 

 

 

本文转载自:http://www.cnblogs.com/celerychen/archive/2013/03/09/2951527.html

共有 人打赏支持
abcijkxyz
粉丝 61
博文 6195
码字总数 1876
作品 0
深圳
项目经理
TMS320 应用参考 (浮点定点)

一 DSP定点算数运算 1 数的定标 在定点DSP芯片中,采用定点数进行数值运算,其操作数一般采用整型数来表示。一个整型数的最大表示范围取决于DSP芯片所给定的字长,一般为16位或24位。显然...

j_m ⋅ 2012/11/22 ⋅ 0

【转】四种主流温度传感器的优缺点比较

转载 http://mc.dfrobot.com.cn/forum.php?mod=viewthread&tid=13303 选择温度传感产品也许看似小事一桩,但由于可用的产品多种多样,因此这项任务可能令人颇感畏惧。在这篇文章中,笔者将介...

y511374875 ⋅ 02/11 ⋅ 0

如何使用Logistic回归做非线性分类

上回实现了logistic回归的并行化,我们就有了一个压榨CPU的利器。 (我的吐槽之魂已经开始沸腾了,明明是Classification的算法,为什么叫Regression!!!为什么!!!!!!) Logistic回归具...

清雨影 ⋅ 2016/01/31 ⋅ 0

SVM支持向量机一些重要算法二

五、核函数 如果我们的正常的样本分布如下图左边所示,之所以说是正常的指的是,不是上面说的那样由于某些顽固的离群点导致的线性不可分。它是真的线性不可分。样本本身的分布就是这样的,如...

qq_35311970 ⋅ 03/22 ⋅ 0

python机器学习案例系列教程——算法比较

机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普...

luanpeng825485697 ⋅ 04/17 ⋅ 0

国家“千人”王中风教授:如何满足不同应用场景下深度神经网络模型算力和能效需求

基于神经网络的深度学习算法已经在计算机视觉、自然语言处理等领域大放异彩。然而,诸如 VGG、ResNet 和 Xception 等深度模型在取得优越性能的同时往往伴随着极高的存储空间需求和计算复杂度...

技术小能手 ⋅ 2017/12/25 ⋅ 0

常见机器学习算法比较(转)

机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普...

超人学院 ⋅ 2016/07/11 ⋅ 1

机器学习算法比较

机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普...

莫问viva ⋅ 2016/08/31 ⋅ 0

核函数与支持向量机入门

原文传送门:核函数与支持向量机入门 理解支持向量机(Support Vector Machine, SVM)的角度很多。从分类问题入手,由最小化训练错误导出限制条件下的凸优化问题的解,进而由线性可分的硬边界泛...

willheng ⋅ 2015/11/22 ⋅ 0

高精度加、减、乘、除算法实现详解

在说高精度加减乘除运算之前,我们先搞明白什么是高精度运算? 实际上高精度就是说参与运算的数据和运算结果的范围,超出标准数据类型能表示的数据大小范围的运算。这个时候,如果要得到正确...

fanyun_01 ⋅ 04/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从零开始搭建Risc-v Rocket环境---(1)

为了搭建Rocke环境,我买了一个2T的移动硬盘,安装的ubuntu-16.04 LTS版。没有java8,gcc是5.4.0 joe@joe-Inspiron-7460:~$ java -version程序 'java' 已包含在下列软件包中: * default-...

whoisliang ⋅ 10分钟前 ⋅ 0

大数据学习路线(自己制定的,从零开始学习大数据)

大数据已经火了很久了,一直想了解它学习它结果没时间,过年后终于有时间了,了解了一些资料,结合我自己的情况,初步整理了一个学习路线,有问题的希望大神指点。 学习路线 Linux(shell,高并...

董黎明 ⋅ 15分钟前 ⋅ 0

systemd编写服务

一、开机启动 对于那些支持 Systemd 的软件,安装的时候,会自动在/usr/lib/systemd/system目录添加一个配置文件。 如果你想让该软件开机启动,就执行下面的命令(以httpd.service为例)。 ...

勇敢的飞石 ⋅ 18分钟前 ⋅ 0

mysql 基本sql

CREATE TABLE `BBB_build_info` ( `community_id` varchar(50) NOT NULL COMMENT '小区ID', `layer` int(11) NOT NULL COMMENT '地址层数', `id` int(11) NOT NULL COMMENT '地址id', `full_......

zaolonglei ⋅ 26分钟前 ⋅ 0

安装chrome的vue插件

参看文档:https://www.cnblogs.com/yulingjia/p/7904138.html

xiaoge2016 ⋅ 29分钟前 ⋅ 0

用SQL命令查看Mysql数据库大小

要想知道每个数据库的大小的话,步骤如下: 1、进入information_schema 数据库(存放了其他的数据库的信息) use information_schema; 2、查询所有数据的大小: select concat(round(sum(da...

源哥L ⋅ 51分钟前 ⋅ 0

两个小实验简单介绍@Scope("prototype")

实验一 首先有如下代码(其中@RestController的作用相当于@Controller+@Responsebody,可忽略) @RestController//@Scope("prototype")public class TestController { @RequestMap...

kalnkaya ⋅ 56分钟前 ⋅ 0

php-fpm的pool&php-fpm慢执行日志&open_basedir&php-fpm进程管理

12.21 php-fpm的pool pool是PHP-fpm的资源池,如果多个站点共用一个pool,则可能造成资源池中的资源耗尽,最终访问网站时出现502。 为了解决上述问题,我们可以配置多个pool,不同的站点使用...

影夜Linux ⋅ 今天 ⋅ 0

微服务 WildFly Swarm 管理

Expose Application Metrics and Information 要公开关于我们的微服务的有用信息,我们需要做的就是将监视器模块添加到我们的pom.xml中: 这将使在管理和监视功能得到实现。从监控角度来看,...

woshixin ⋅ 今天 ⋅ 0

java连接 mongo伪集群部署遇到的坑

部署mongo伪集群 #创建mongo数据存放文件地址mkdir -p /usr/local/config1/datamkdir -p /usr/local/config2/data mkdir -p /usr/local/config3/data mkdir -p /usr/local/config1/l......

努力爬坑人 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部