DIY编程器网

标题: 《玩转IP core》之十一：非线性求值的孤独九剑,CORDIC方法 [打印本页]

作者: admin 时间: 2014-10-12 16:26
标题: 《玩转IP core》之十一：非线性求值的孤独九剑,CORDIC方法
虽然出身在城市，比起很多乡村出身的人来说，童年的物质还算是不那么匮乏的。但是，70后们还是没有什么玩具可以打发业余时间的；可能农村的孩子这方面还好点，那时候小河还没有污染。不是“忆苦思甜”了。我记得那时候最喜欢玩的，就是一个老爹发的电子计算器，还是发光二极管的那种。当年我就好奇，这么小小一个东西竟然可以算三角函数，而且比《数学用表》还精确。到了后来进了大学，学习了《数字电子技术》我就更加好奇了：以当年中等规模集成电路的水准，这些非线性函数是怎么计算的呢？工作后，一个偶然的机会，当年还是小沙弥的在下得到了一个名词“CORDIC”（COordinate Rotation DIgital Computer）。终于，某家发现了非线性求值的独孤九剑，这一讲里面就和在座的各位分享。大家注意保密，叫那些逃课的娃儿们哭去吧。（我不在高校做教师，要不也绝对是“四大名捕”之一。）

非线性三招（对应H公司的维护三招）：折线、查找、CORDIC。前两招，广为人知的，不必细表。却说这个“CORDIC姑姑”（50年代生人，也算得姑姑了），却是“养在深闺人未识”。一直从剩女变成了人老珠黄，我们大陆的工程师竟然没有几个认识的。人生的悲哀啊。没有做过CORDIC，事业不完整啊。大伙知道不，米国数字设计界有句名言，翻译过来是：“设计不知C姑姑，纵使总工也马虎”。

再多一句废话，这一讲恐怕是整个讲座里面最数学化的一次了，大家担待了。

几十年前，几位老爷爷为了实现美帝国主义称霸全世界的险恶用心，对某战略轰炸机的导航系统进行了数字化。为了计算球面----也就是地球上----的一个位置坐标，sin和cos比不可缺少的。学过球面坐标系的人，都知道这个道理。这几个老帮子也不是什么善人，居然从三角形求和公式里面想出了CORDIC算法。

现在，大伙开始复原他们的犯罪现场。从大伙儿倒背如流的和角公式开始：

公式两边一起除以cosα

到这里还倒罢了，他们竟然恬不知耻的做了下面的假设

这个里面为什么取

呢？就是为了下面算式里面的乘以正切的算法，简化成了数学移位。真是为了与世界人民为敌，无所不用其极啊。
大家看烦了公式了吧，鄙人也不喜欢用公式唬人。下面我们看看第一次旋转的几何解释。在单位圆上，我们知道

，α是(x, y)对应的圆心角。每次计算，相当于把向量的长度放大了

，向量的角度旋转了α_k。我们算N次运算，再统一除掉放大的总体倍数，就得到需要角度的正余弦值了。

敌亡我之心不死啊，然后这些家伙把公式计算了N次。对应几何解释，就是左右旋转了N下。

于是

这正是《正大综艺》的宣传词：“不看不知道，世界真奇妙”。C=∏_(k=0)^N√(1+〖tan〗^2 α_k )的值和α_k的值都是事先已知的，γ是需要计算正余弦值的角度。再带入初始值

不难计算

麻烦来了，所有角度的sin和cos值都可以获得了。下图是旋转次数与计算误差的对应关系，

。这是老朽用Excel模拟计算的（由于版权问题，没敢用Verilog实现和仿真）。

数学到此为止，老衲讲的都快吐了。现在来个“师夷长技以制夷”，给大家画画CORDIC的流水线（因为是小数运算，假设实数“1”为十六进制的全1，实数值就可以折算了。这是普遍的技巧，不详述。）。还有一个小技巧就是由于每步的放大作用，公式里预先收缩了一把。流水的每一步包含两个移位、一个查找常数值和三次加法，里面的乘法实际上就是XOR可以忽略，简单明了。值得注意的是，这个里面的操作是有符号数运算。

（“元芳，你怎么看？”
“此中必有一个惊天的阴谋！”）

这个阴谋还不止于此，后来很多狼心狗肺的人又发展出了广义的CORDIC算法。如果说求正余弦值是“破剑式”，那么“破刀式”就顺理成章的来了。坏人处处有，这里特别多啊。

这一讲篇幅已经有些过长了，广义的就不展开了。给列位一个单子，看看都能计算什么。（这个是相声里面的“柳活”，说不好咬舌头的。小子姑且试试，列位见笑了。）

能够直接计算的有：sin、cos、tan-1、sinh、cosh、×、÷、tan-1(x / y)、y + xz、

以及

。
可以间接获得的有：ex、tan x、tanh x、ln x、logb x、xt、cos-1 x、 sin-1 x、cos-1 x、 sin-1 x还有

。

（人老了气血不足，肺活量也小了，这段说的有点黄腔走班。待我喘喘气，接着唠。）

有诗赞曰：“非线函数一箩筐，精忠C姑是栋梁。收缩输入满值出，移位加法巧伎俩。不怕数值千般变，旋转逼近能力强。待到规定节拍后，捕获数值良弓藏。”。

下一讲里面，为了体现德语语法的名言“凡是规则皆有例外”，老衲说一说一串触发器的例子，大家拭目以待啊。

《玩转IP core》之一：我们的目标是ASIC
摘要：具体到一个产品里面，到底是采用FPGA还是ASIC，这个问题是多方面确定的。简单说，如果产品出货量小、时间紧、生命周期短，那么FPGA比较适合；反之就建议ASIC。但是，也不是完全绝对的，就像很难说少林和武当那个更牛一样。

《玩转IP core》之二：所见非所得
摘要：Verilog语言是由Gateway设计自动化公司的工程师于1983年末创立的；VHDL语言诞生于1983年，1987年被美国国防部和IEEE确定为标准的硬件描述语言。这个古人也“古”不到哪里去。上板砖！

《玩转IP core》之三：：统一行动听指挥
摘要：现在我们正沿着PCB数据大道，走向芯片大厦----就是大家眼前的巨大的、银色的大厦。我是本次旅行的导游，敝姓十，大叫可以叫我十导。路途之中，为了大家不感到无聊，本人先给大家略略介绍一下，什么是数字电路的时钟。数字电路中，时钟是整个电路最重要、最特殊的信号。

《玩转IP core》之四：踏雪寻熊---面积与速度的协调
摘要：具体到我们的FPGA/ASIC设计，这个“鱼”就是面积，而“熊掌”时钟频率（速度）。能不能很好的协调面积与速度的关系，是衡量一个数字逻辑设计工程师能力的一个重要标准。在本讲座的第二篇里面，会说明各种单元模块的不同面积和速度的基本解构；在第三篇中，则会通过例子，介绍如何在系统中很好综合考虑两者的关系，选择比较合适的实现解构。

《玩转IP core》之五：测试向量生成
摘要：在不考虑电源输入的前提下，在我们系统/板子上，能够不依靠其他外界输入而产生输出信号的器件有木有呢？当然有，而且必须有，那就是大名鼎鼎的晶振了，用来产生我们说过的、对以系统极端重要的系统时钟信号。

《玩转IP core》之六：程咬金的三板斧--系统基本结构

摘要：今天我们开始进入本讲座的第二部分：单元篇。大家将会发现，我们在基本单元设计里面，也就是三板斧：查找表、时分复用和流水线。但是，我们比程大将军稍稍高一点，我们会把这三招糅合，能产生变招。

《玩转IP core》之七：一个计数器引起的思考
摘要：设问句：在进行一个计数器单元设计之前，我们需要什么前提条件呢？首先，需要功能描述（一个计数器嘛，不就是在不是复位“RST”的状态，每来一个时钟内部/输出加一吗？还描述什么啊？磨洋工吧？----“非也，非也”，这个还是要描述一下。至少我们需要知道一下计数器的内部位数吧？也就是，计数器加到多大回到0。）另外，就象我们在前面“菜谱”那一讲里面说过的，需要了解系统需要的时钟频率。

《玩转IP core》之八：小学一年级水平，加法器的结构
摘要：工程设计里面有一个原则：从简单做起。这里面还有一个小故事，今天就不讲了。现在，我们先瞧瞧最简单的一个比特位宽的加法器：半/全加器。全加器的输入为三个一比特的信号a0、a1，还有低位的进位c0；输出也是两个一比特的信号：结果s和进位位c1。

《玩转IP core》之九：小学二年级水平，乘法器的结构
摘要：大伙儿已经通过两次讲座，了解了计数器和加法器大体结构。大家不难发现，同样的一种功能，可能由于需要、工作频率和代价的不同要求，存在若干种不同的结构。这些结构如何选择，实际上是一个艰难的选择。这些选择，很多时候都是靠一个工程师的经验（我们老年人也就靠这个混口饭吃了。要不就被“长江后浪推前浪，前浪死在沙滩上”了）。

《玩转IP core》之十：除法器的结构
摘要：如果各位在加法器和乘法器里面可以欣赏到了变化多端的话，那么在下不得不很遗憾的通知诸位：除法器里面大家只能看到“自古华山一条路”。不是我保守，是除法这个东西的本性。用《数学分析》里的说法，加法和乘法都是线性运算满足交换律的，除法是非线性运算不满足交换律的。这是数学上的根子，可以用来唬人。

《玩转IP core》之十一：非线性求值的孤独九剑,CORDIC方法

摘要：现在来个“师夷长技以制夷”，给大家画画CORDIC的流水线（因为是小数运算，假设实数“1”为十六进制的全1，实数值就可以折算了。这是普遍的技巧，不详述。）。还有一个小技巧就是由于每步的放大作用，公式里预先收缩了一把。

《玩转IP core》之十二：电路串串香，D触发器链
摘要：今个儿寡人给大家讲点有“理论”的：CRC校验（循环冗余校验码，Cyclic Redundancy Check）和编码器。CRC校验的目的就是看接收的一串比特和原来发射的是不是一致，有没有接收误码。CRC在编码界的春典，就是“gCRC16(D) = [D16 + D12 + D5 + 1]”和“1 0001 0000 0001 0001”。给大家一个口诀：“延时触发串一串，遇到一字砍一段。输入牵来异或算，输出导出入口看。”

《玩转IP core》之十三：简直的层层叠，FIR滤波器的串联实现

摘要：今天我们继续信号处理的行程，给大家介绍FIR滤波的串行实现。却说“请介绍FIR滤波器和IIR滤波器的差别”，这可是一道非常典型的面试题。这道题目类似于《哈利波特》里面那个“分院帽”的作用，当然这个题目里面没有宝剑。

《玩转IP core》之十四：我的地盘我做主，锁相与分频
摘要：在做设计的时候，谁都希望片子的输入时钟是稳定的、可靠的，并且和我们系统的采样频率是一致的。这是最理想状态。可惜啊，希望是丰满的，现实是骨感的。很多时候，情况并没有这么理想。这种时候，就需要我们自己调节系统时钟，达到系统工作的目的了。不是大伙儿“无知者无畏”，是不得不为啊。实际上，在很多通讯系统中，对于系统时钟的调节都是不可避免的。

《玩转IP core》之十五：国球与其它，输入输出介绍
摘要：我们现在正式为《第三篇：系统篇》剪彩（哗哗哗，掌声响起来，我心更明白…）。在这一部分里面，会在更高的层次上，分析设计问题。大伙儿不仅仅能看到《单元篇》里面的各个部件的应用，而且会发现系统绝对不是单元的简单的搭积木。在整个讲座里面，“变化”是永远的主题。

《玩转IP core》之十六：来个批发价，多路数字中频系统设计
摘要：数字中频主要分两种类型：数字上变频（DUC）和数字下变频（DDC），它们的主要功能是相反，但原理和实现的方法是十分相似。由于FIR滤波器里面讲的是下采样的例子，这里也就以数字下变频作为例子，这样匹配。

《玩转IP core》之十七：看客做饭，CDMA接收机的同步
摘要：这一讲里面会介绍CDMA系统的同步部分，这不是重点。关键是，大伙儿会看到同样的算法，在终端和基站侧由于系统用户数目不同，会有不同实现。这是给大家的一个启示：不能因循守旧，要与时俱进。

《玩转IP core》之十八：磨刀不误砍柴工，程序的风格
摘要：“代码风格和规则”这个问题，很多人看来不是十分重要。但是，我问问大伙儿几个现象，看看是否遇到过？过了三个月，读不懂自己的程序的，有木有？看别人代码，赶脚不如自己重写的，有木有？做C代码的，竟然能看懂你的程序的，有木有？调试的时候，感觉是老虎吃天----无从下口，有木有？如果有，以老衲的经验，多多少少和“代码风格和规则”有些瓜葛。

----------------------------
如果你从事FPGA研发，或者你对IP core设计感兴趣，欢迎关注《玩转IP core》系列技术讲座，每周三加菲博士与你不见不散，如果针对本讲座有任何技术问题欢迎与加菲进行技术互动可以加入QQ群（FPGA交流圈：23294742），或者去交流区提问：《玩转IP core》交流区

关注与非网官方微博：http://e.weibo.com/eefocus 我们的讲座内容将在微博同步更新。

加菲独家供稿与非网，谢绝任何形式的转载，与非网做你技术生涯中最有价值的电子网站。

欢迎光临 DIY编程器网 (http://diybcq.com/)