《玩转IP core》之十：升入小学三年级，除法器的结构

admin

老和尚法海有揭语云：“非常变化缘，与君细攀谈。家中耐参禅，独自心参详。讲解非吾愿，开悟刹那间。菲岛逛长滩，加国枫叶观。”这里面的意思就是说：你好好学我的讲座、领悟要点，就可以获得一份可以出国去度假的薪水了。玩笑，玩笑了。
       
        如果各位在加法器和乘法器里面可以欣赏到了变化多端的话，那么在下不得不很遗憾的通知诸位：除法器里面大家只能看到“自古华山一条路”。不是我保守，是除法这个东西的本性。用《数学分析》里的说法，加法和乘法都是线性运算满足交换律的，除法是非线性运算不满足交换律的。这是数学上的根子，可以用来唬人。
        大家回忆一下小学的时候学的竖式除法运算，下面是一个例子。我们每次算被除数的一部分；余数留下加上被除数的下一位，接着运算，直到需要的精度。

       

       
        大伙儿会惊奇地发现：数字逻辑的除法操作竟然就是小学生方法的引申。嘴不要张那么大，进了蟾蜍，你也不会百毒不侵的。现在还是以一个例子，隆重推出本讲的主角：辗转相除法。还是那样的描述：“我们每次算被除数的一部分；余数留下加上被除数的下一位，接着运算，直到需要的精度。”简单说，就是一步算一个比特。这样，运算的建立时间就是（要求精度的比特数 – 除数比特数）。

       

       
        可能有些人还沉浸在Z80的时代，说还可以逐次减除数，次数计数，最后获得结果。这个嘛，老衲实在不推荐，所以也不多说，言多必失。
       
        虽然，本方案的年代更加古老，古老到都不好考据到底是什么年代的古物了。但是，辗转相除法的最大有点就是建立时间固定。
       
        本讲的内容不多，亲们，请允许在下再多说点“废话”。在设计数字逻辑系统的时候，大多数情况下，建立时间不确定比建立时间长更难以接受。因为这种“不确定的建立时间”的最大值，往往要比“建立时间长”的值还来得大。这样，为了设计里面不冒险，等待时间反而是“建立时间不确定”的更多，系统处理更慢。有人抬杠了：我们有的是时间，可以慢慢等。本人对此无语了。有的是时间，说明设计的不好，冗余太多。换句俗话说就是：败家（某家写作这天正好双“11”，整个QQ群都在讨论“败家”。这个娃儿倒是应景。不过也别出来得瑟啊。好好在家猫冬，大家还不晓得你这样“负责”。）。这样还好意思出来显摆。明显的“雇佣者心态”，要不得的（我善于扣大帽子）。你要是老板，愿意你得员工成天闲着摆龙门阵？你是负责的设计者，也不应该叫某些单元总是空闲。
       
        好了，言归正传，虽然内容不会太多。基于我一向吝啬的本质，也不会用查找表来填充版面。这个讲座我没有稿费的，长短都一样。另外呢，时分复用的结构也不会多说。学好流水线，只要IQ不是负数的，应该都能把流水线改装成时分复用。
         
        睁大眼睛了，下面大伙儿和我一起研究一下流水线乘法器的结构。定义运算里面，被除数是a（位宽M比特），除数是b（位宽N比特，约定M ≥ N），商是c （位宽M – N +1比特，余数是d（位宽N比特）。例子里面没有考虑除到小数位数。如果遇到这样的要求，可以在a后面加若干个“0”完成。这里面还有简化，不是重点，忽略不计了。还得注意b等于“0”时候的溢出处理，也不是重点，同样忽略不计。除法就是麻烦，就好像华妃说的“贱人就是矫情”。下图就是流水线乘法器的基本结构。
         

       

       
         
        每一步都是包含截位、比较、减法和存储相应结果这几个步骤完成。截位是说第n步，截取存储结果的高位比特的M – n +1比特开始的N个比特a’，输入比较器。比较器比较a’和b：a’ ≥ b输出1，否则输出为0。如果比较器输出为1，则把被除数延时链对应的a’位，存为a’ – b的结果，否则保持a’。比较器的结果，同时存入c的第N – n位。最后一步的减法结果就是余数d。
        模仿赵丽蓉大妈对于探戈的口诀，这个除法器也有一个口诀如下：“一步一比特，比较写入商，被除减除数，辗转至最低。”
       
        说到除法器，想起一位失去联系10多年的故人。下面借贵方一片宝地，我做一个寻人启示：“当年拿过我辗转相除法程序的西交大小师妹，就是听过我形容我在Z的办公室的环境是：‘太阳象大桔饼懒洋洋地挂在天上，周围是抹茶冰淇淋般的小山…’的哪位小师妹，请与我联系。联系方法：新浪微波用户‘与非网说书人加菲’”。（澄清一下，没有八卦，没有“不得不说的故事”，更没有“我和XXX的一段情”。）
       
        后面聊一个和除法器可以说有关也可以说无关的话题：在数字信号处理（DSP，Digital Signal Processing）系统里面，如何除一个常数的问题。
       
        先讲一个“除以3”的典故，真人真事啊，恕我不能说出人家的名字。这个典故是我经常在各个算法QQ群里面讲到的。为了提醒算法工程师们，懂点实现多重要。后面为了给这个讲座吸引观众，我故意的只说名字不说内容了，留点悬念（一点小伎俩，希望大家可以理解）。话说某日，算法工程师和实现工程师开会，讨论一个系统方案。方案里面，有一个数值，根据情况不同，可能被除以2、3或者4。实现工程师同意做2和4的情况，这个就相当于算术右移1位或者2位，地球人都知道。他们坚决反对做3的情况，理由是：除法占得DSP/FPGA周期太长，太浪费。在大家争论的脸红耳赤的时候，我不厚道地悠悠说道：“你们什么时候开始用除法操作做常数除法了？”实现工程师立即放弃争论，同意完全按照算法工程师的想法做了。
       
        现在休息五分钟，列位猜测一下其中玄机。
       
        ……滴答，滴答……五分钟到了。现在是见证奇迹的时刻。
       
        首先，信号处理运算里面除法的余数是没有意义的；其次，信号处理允许存在一定的计算误差；最后，信号处理需要这种误差是可估计可控制的。
       
        看公式：
        c = a / 3
           = a × (2 ^ N) / 3 / (2^N)
           = a × ( (2 ^ N) /3) /(2^N)
           = (a × b)  >> N
       
        其中，b =(2 ^ N) /3是常数，可以事先计算； >>是算术右移操作；^是幂运算。进一步，考虑到我们乘法器里面的关于乘以常数的简化方法，上面运算还可以进一步简化。如何，化除法为乘法，哪个还敢说复杂。
       
        这正是：“加乘尚能一大片，除法仅可一条线。误差可控除常数，变乘移位最方便。”
       
        下一讲，我们会介绍如何做一个DIY的计算器。别当真啊，还是玩笑。但是，说实在的也差不多了。
         
        《玩转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 我们的讲座内容将在微博同步更新。
       
        加菲独家供稿与非网，谢绝任何形式的转载，与非网做你技术生涯中最有价值的电子网站。