[数据结构与算法]初识FPGA

现场可编程逻辑门阵列FPGA

1.FPGA定义

FPGA现场可编程逻辑门阵列（Field Programmable Gate Array）是在PAL、GAL等可编程器件的基础上进一步发展的产物。它是作为专用集成电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。

1.1FPGA其他简介

与传统模式的芯片设计进行对比，FPGA芯片并非单纯局限于研究以及设计芯片，而是针对较多领域产品都能借助特定芯片模型予以优化设计。从芯片器件的角度讲，FPGA 本身构成了半定制电路中的典型集成电路，其中含有数字管理模块、内嵌式单元、输出单元以及输入单元等。在此基础上，关于FPGA芯片有必要全面着眼于综合性的芯片优化设计，通过改进当前的芯片设计来增设全新的芯片功能，据此实现了芯片整体构造的简化与性能提升。

2.FPGA的设计流程

FPGA的设计流程包括
算法设计、代码仿真以及设计、板机调试，
设计者以及实际需求建立算法架构，利用EDA建立设计方案或HD编写设计代码，通过代码仿真保证设计方案符合实际要求，最后进行板级调试，利用配置电路将相关文件下载至FPGA芯片中，验证实际运行效果。

3.FPGA工作原理

FPGA采用了
逻辑单元阵列LCA（Logic Cell Array）这样一个概念，内部包括
可配置逻辑模块CLB（Configurable LogicBlock）、
输入输出模块IOB（Input Output Block）和
内部连线（Interconnect）三个部分。 现场可编程门阵列（FPGA）是可编程器件，与传统逻辑电路和门阵列（如PAL，GAL及CPLD器件）相比，FPGA具有不同的结构。FPGA利用小型查找表（16×1RAM）来实现组合逻辑，每个查找表连接到一个D触发器的输入端，触发器再来驱动其他逻辑电路或驱动I/O，由此构成了既可实现
组合逻辑功能
又可实现
时序逻辑功能
的基本逻辑单元模块，这些模块间利用金属连线互相连接或连接到I/O模块。FPGA的逻辑是通过
向内部静态存储单元加载编程数据
来实现的，存储在存储器单元中的值决定了逻辑单元的逻辑功能以及各模块之间或模块与I/O间的联接方式，并最终决定了FPGA所能实现的功能，FPGA允许无限次的编程

4.PFGA芯片设计

相比于其他种类的芯片设计，关于 FPGA芯片通常需要设置较高门槛并且拟定严格性较强的基本设计流程。具体在设计时，应当紧密结合 FPGA 的有关原理图，据此实现了规模较大的专门芯片设计。通过
运用Matlab以及C语言的特殊设计算法，应当可以实现全方位的顺利转化，从而确保其符合当前的主流芯片设计思路。在此前提下，如果选择了上述设计思路那么通常需要着眼于有序整合各类元器件以及相应的设计语言，据此保证了可用性与可读性较强的芯片程序设计。运用 FPGA可以实现板机调试、代码仿真与其他有关的设计操作，确保当前的代码编写方式以及设计方案都能符合特定的设计需求。 除此以外，关于设计算法应当将合理性置于首要性的位置， 据此实现了优化的项目设计效果，并且优化了芯片运行的实效性。因此作为设计人员来讲，首先就是要构建特定的算法模块， 以此来完成与之有关的芯片代码设计。这是由于预先设计代码有助
保证算法可靠性，对于整体上的芯片设计效果也能予以显著优化。在全面完成板机调试以及仿真测试的前提下，应当可以在根源上缩短设计整个芯片消耗的周期，同时也致力于优化当前现存的硬件整体结构。例如在涉及到开发非标准的某些硬件接口时，通常都会用到上述的新产品设计模式。
FPGA设计的主要难点是熟悉硬件系统以及内部资源，保证设计的语言能够实现元器件之间的有效配合，提高程序的可读性以及利用率。这也对设计人员提出了比较高的要求，
需要经过多个项目的经验积累才可以达到相关的要求。
在算法设计时需要重点考虑合理性，保证项目最终完成的效果，依据项目的实际情况提出解决问题的方案，提高FPGA的运行效率。确定算法后应当合理构建模块，方便后期进行代码设计。在代码设计时可以利用预先设计好的代码，提高工作效率，增强可靠性。编写测试平台，进行代码的仿真测试和班级调试，完成整个设计过程。FPGA同ASIC不同，开发的周期比较短，可以结合设计要求改变硬件的结构，在通信协议不成熟的情况下可以帮助企业迅速推出新产品，满足非标准接口开发的需求。

5.相关术语介绍

5.1加法器Adder

加法器是产生数的和的装置。加数和被加数为输入，和数与进位为输出的装置为半加器。若加数、被加数与低位的进位数为输入，而和数与进位为输出则为全加器。常用作计算机算术逻辑部件，执行逻辑操作、移位与指令调用。在电子学中，加法器是一种数位电路，其可进行数字的加法计算。三码，主要的加法器是以二进制作运算。由于负数可用二的补数来表示，所以加法器也就不那么必要。

5.2半加器half adder

半加器电路是指对两个输入数据位相加，输出一个结果位和进位，没有进位输入的加法器电路。 是实现两个一位二进制数的加法运算电路。

5.3逐位进位加法器ripple-carry adder

要实现二进制加法，一种自然的想法就是将1位的二进制加法重复32次（即逐位进位加法器）。这样做无疑是可行且易行的，但由于每一位的CIN都是由前一位的COUT提供的，所以第2位必须在第1位计算出结果后，才能开始计算；第3位必须在第2位计算出结果后，才能开始计算，等等。如果是一个32位的加法器，最后的第32位必须在前31位全部计算出结果后，才能开始计算。这样的方法，使得实现32位的二进制加法所需的时间是实现1位的二进制加法的时间的32倍。可以看出，上法是将加法1位1位串行进行的，要缩短进行的时间，就应设法使上叙进行过程并行化。

5.4自动增益控制automatic gain control

自动增益控制（automatic gain control）使放大电路的增益自动地随信号强度而调整的自动控制方法。自动增益控制是限幅输出的一种,它利用线性放大和压缩放大的有效组合对助昕器的输出信号进行调整。当弱信号输入时,线性放大电路工作,保证输出信号的强度;当输入信号达到一定强度时,启动压缩放大电路,使输出幅度降低。也就是说,AGC功能可以通过改变输入输出压缩比例自动控制增益的幅度。AGC细分为AGCi(输入自动增益控制)和AGCo(输出自动增益控制)。

5.5乘法器multiplier

乘法器（multiplier）是一种完成两个互不相关的模拟信号相乘作用的电子器件。它可以将两个二进制数相乘，它是由更基本的加法器组成的。乘法器可以通过使用一系列计算机算数技术来实现。乘法器不仅作为乘法、除法、乘方和开方等模拟运算的主要基本单元，而且还广泛用于电子通信系统作为调制、解调、混频、鉴相和自动增益控制；另外还可用于滤波、波形形成和频率控制等场合，因此是一种用途广泛的功能电路。

5.6电子式电能表Electronic Power Energy Meter

电子式电能表是通过对用户供电电压和电流实时采样，采用专用的电能表集成电路，对采样电压和电流信号进行处理并相乘转换成与电能成正比的脉冲输出，通过计度器或数字显示器显示的物理器械。
电子式电能表与机械式电能表相比有明显优势。例如：防窃电能力强、计量精度高、负荷特性较好、误差曲线平直、功率因数补偿性能较强、自身功耗低，特别是其计量参数灵活性好、派生功能多。由于单片机的应用给电能表注入了新的活力，这些都是一般机械表难以做到的。但是早期的电子式电能表也有一些明显的不足，如工作寿命较短、易受外界干扰、工作可靠性不及机械式电能表等。

5.7专业集成电路ASIC(Application Specific Integrated Circuit)

ASIC即专用集成电路，是指应特定用户要求和特定电子系统的需要而设计、制造的集成电路。 目前用CPLD（复杂可编程逻辑器件）和 FPGA（现场可编程逻辑门阵列）来进行ASIC设计是最为流行的方式之一，它们的共性是都具有用户现场可编程特性，都支持边界扫描技术，但两者在集成度、速度以及编程方式上具有各自的特点。

5.8嵌入式系统Embedded system

嵌入式系统由硬件和软件组成．是能够独立进行运作的器件。其软件内容只包括软件运行环境及其操作系统。硬件内容包括信号处理器、存储器、通信模块等在内的多方面的内容。相比于一般的计算机处理系统而言，嵌入式系统存在较大的差异性， 它不能实现大容量的存储功能，因为没有与之相匹配的大容量介质，大部分采用的存储介质有E-PROM、EEPROM 等， 软件部分以API编程接口作为开发平台的核心。

5.9应用程序接口API（Application Programming Interface）

API（Application Programming Interface，应用程序接口）是一些预先定义的接口（如函数、HTTP接口），或指软件系统不同组成部分衔接的约定。用来提供应用程序与开发人员基于某软件或硬件得以访问的一组例程，而又无需访问源码，或理解内部工作机制的细节。

5.10模拟数字转换器ADC(analog to digital converter)

模拟数字转换器即A/D转换器，或简称ADC，通常是指一个将模拟信号转变为数字信号的电子元件。通常的模数转换器是将一个输入电压信号转换为一个输出的数字信号。由于数字信号本身不具有实际意义，仅仅表示一个相对大小。故任何一个模数转换器都需要一个参考模拟量作为转换的标准，比较常见的参考标准为最大的可转换信号大小。而输出的数字量则表示输入信号相对于参考信号的大小

模数转换器的种类很多，按工作原理的不同，可分成间接ADC和直接ADC.间接ADC是先将输入模拟电压转换成时间或频率，然后再把这些中间量转换成数字量，常用的有中间量是时间的双积分型ADC

1. 并联比较型ADC：由于并联比较型ADC采用各量级同时并行比较，各位输出码也是同时并行产生，所以转换速度快是它的突出优点，同时转换速度与输出码位的多少无关。并联比较型ADC的缺点是成本高、功耗大。因为n位输出的ADC，需要2n个电阻，（2n－1）个比较器和D触发器，以及复杂的编码网络，其元件数量随位数的增加，以几何级数上升。所以这种ADC适用于要求高速、低分辩率的场合 。
2. 逐次逼近型ADC：逐次逼近型ADC是另一种直接ADC，它也产生一系列比较电压VR，但与并联比较型ADC不同，它是逐个产生比较电压，逐次与输入电压分别比较，以逐渐逼近的方式进行模数转换的。逐次逼近型ADC每次转换都要逐位比较，需要（n+1）个节拍脉冲才能完成，所以它比并联比较型ADC的转换速度慢，比双分积型ADC要快得多，属于中速ADC器件。另外位数多时，它需用的元器件比并联比较型少得多，所以它是集成ADC中，应用较广的一种 。
3. 双积分型ADC：属于间接型ADC，它先对输入采样电压和基准电压进行两次积分，以获得与采样电压平均值成正比的时间间隔，同时在这个时间间隔内，用计数器对标准时钟脉冲（CP）计数，计数器输出的计数结果就是对应的数字量。双积分型ADC优点是抗干扰能力强；稳定性好；可实现高精度模数转换。主要缺点是转换速度低，因此这种转换器大多应用于要求精度较高而转换速度要求不高的仪器仪表中，例如用于多位高精度数字直流电压表中 。

5.11数字模拟转换器DAC（digital to analog converter）

数模转换器，又称D/A转换器，简称DAC，它是把数字量转变成模拟的器件。D/A转换器基本上由4个部分组成，即权电阻网络、运算放大器、基准电源和模拟开关。
模数转换器中一般都要用到数模转换器，模数转换器即A/D转换器，简称ADC，它是把连续的模拟信号转变为离散的数字信号的器件。

5.12带点可擦可编程只读储存器EEPROM（Electrically Erasable Programmable read only memory）

指带电可擦可编程只读存储器。是一种掉电后数据不丢失的存储芯片。 EEPROM 可以在电脑上或专用设备上擦除已有信息，重新编程。一般用在即插即用。

5.13可擦除可编程只读储存器EPROM（Erasable Programmable Read-Only Memory）

EPROM由以色列工程师Dov Frohman发明，是一种断电后仍能保留数据的计算机储存芯片——即非易失性的（非挥发性）。它是一组浮栅晶体管，被一个提供比电子电路中常用电压更高电压的电子器件分别编程。一旦编程完成后，EPROM只能用强紫外线照射来擦除。通过封装顶部能看见硅片的透明窗口，很容易识别EPROM，这个窗口同时用来进行紫外线擦除。可以将EPROM的玻璃窗对准阳光直射一段时间就可以擦除。

5.14只读储存器ROM（Read-Only Memory）

只读存储器（Read-Only Memory，ROM）以非破坏性读出方式工作，只能读出无法写入信息。信息一旦写入后就固定下来，即使切断电源，信息也不会丢失，所以又称为固定存储器。ROM所存数据通常是装入整机前写入的，整机工作过程中只能读出，不像随机存储器能快速方便地改写存储内容。ROM所存数据稳定 ，断电后所存数据也不会改变，并且结构较简单，使用方便，因而常用于存储各种固定程序和数据。
除少数种类的只读存储器（如字符发生器）可通用之外，不同种类的只读存储器功能不同。为便于用户使用和大批量生产，进一步发展出可编程只读存储器（PROM）、可擦可编程序只读存储器（EPROM）和带电可擦可编程只读存储器（EEPROM）等不同的种类。ROM应用广泛，诸如Apple II或IBM PC XT/AT等早期个人电脑的开机程序（操作系统）或是其他各种微电脑系统中的轫体（Firmware），所使用的硬件都是ROM。
ROM有多种类型，且每种只读存储器都有各自的特性和适用范围。从其制造工艺和功能上分，ROM有五种类型，即掩膜编程的只读存储器MROM（Mask-programmedROM）、可编程的只读存储器PROM（Programmable ROM）、可擦除可编程的只读存储器EPROM（Erasable Programmable ROM）、可电擦除可编程的只读存储器 EEPROM（Elecrically Erasable Programmable ROM）和快擦除读写存储器（Flash Memory）。

5.15印制电路板PCD(Printed circuit boards)

印制电路板{Printed circuit boards}，又称印刷电路板，是电子元器件电气连接的提供者。按照线路板层数可分为单面板、双面板、四层板、六层板以及其他多层线路板。
由于印刷电路板并非一般终端产品，因此在名称的定义上略为混乱，例如：个人电脑用的母板，称为主板，而不能直接称为电路板，虽然主机板中有电路板的存在，但是并不相同，因此评估产业时两者有关却不能说相同。再譬如：因为有集成电路零件装载在电路板上，因而新闻媒体称他为IC板，但实质上他也不等同于印刷电路板。我们通常说的印刷电路板是指裸板-即没有上元器件的电路板。

5.16边界扫描测试技术Boundary Scan Test Technology

边界扫描测试技术是通过在内部逻辑的边界和外部引腿之间增加条扫描链和测试访问端口，测试激励信息，串行传送的测试方法。边界扫描测试也用厂系统芯片(SOC)内部的各模块的测试。

5.17片上系统SOC（System on Chip）

SoC的定义多种多样，由于其内涵丰富、应用范围广，很难给出准确定义。一般说来， SoC称为系统级芯片，也有称片上系统，意指它是一个产品，是一个有专用目标的集成电路，其中包含完整系统并有嵌入软件的全部内容。同时它又是一种技术，用以实现从确定系统功能开始，到软/硬件划分，并完成设计的整个过程。

5.18电子电路仿真Electronic circuit simulation

指使用数学模型来对电子电路的真实行为进行模拟的工程方法。

1. 仿真系统可以对电路的功能行为进行模拟，而不需要建立实际的电路（这过程可能繁琐而昂贵），因此它是一种很有实用价值的工具。由于仿真系统对真实情况的模拟越来越逼真，许多大学、研究机构都会使用这类工具来辅助电子工程方面的教学。由于电子电路仿真系统一般具有较好的图形化界面，它们常常可以使用户有身临其境的感觉。对于初学者，他们可以在仿真软件的帮助下进行分析、综合、组织和评估所学的知识。
2. 在构建实际的电路之前，对设计进行仿真验证，可以大大地提高设计效率。这是由于，设计人员可以在构建电路之前，预先观察、研究电路的行为，而不必为电路的物理实现付出时间和经济的成本。尤其是集成电路，在物理上实现电路所需的光掩模等电子工艺成本不菲，而集成电路的高复杂性又在面包板上面难以实现，用传统的方法研究电路的行为较为困难。因此，几乎所有的集成电路设计都较为依赖仿真。最著名的模拟仿真是SPICE，而最著名的数字电路仿真器都是基于Verilog或VHDL的。
3. 一些电子仿真系统集成了原理图编辑器、仿真引擎、波形显示功能，这样使用户可以轻松地观察电路行为的即时状态。通常，仿真系统也会包括扩展模型以及电子元件库。其中模型主要包括集成电路专用的晶体管模型，例如BSIM；而元件库会提供很多通用元件，如电阻器、电容器、电感元件、变压器和用户定义的模型（例如受控的电流源、电压源），此外还可以提供Verilog-A或VHDL-AMS中的一些模型）。印刷电路板设计还要求专用的模型，例如线路走线的传输线模型和IBIS模型等。

5.19软硬件协同设计Hardware-Software Co-design

软硬件协同设计是指对系统中的软硬件部分使用统一的描述和工具进行集成开发,可完成全系统的设计验证并跨越软硬件界面进行系统优化。
受电子技术，特别是可编程技术的限制，传统的设计方法是将硬件和软件分为两个独立的部分进行设计。在整个设计过程中，通常采用硬件优先的原则，一般首先进行硬件设计，然后在硬件设计平台上进行软件设计。随着电子技术的发展，各种大规模可编程集成电路得到广泛的应用，传统的设计方法的局限性已成为限制可编程芯片充分发挥性能的障碍，在此基础上，人们开始研究软硬件协同设计技术。软硬件协同设计是依据系统设计为目标，通过综合分析系统软硬件功能及现有资源，最大限度地挖掘系统软硬件的潜能，协同设计软硬件体系结构，使得系统能够运行在最佳的工作状态。

5.20数字信号处理器Digital Signal Processor

数字信号处理器（Digital Signal Processor）是由大规模或超大规模集成电路芯片组成的用来完成数字信号处理任务的处理器。
数字信号处理是将信号以数字方式表示并处理的理论和技术。数字信号处理与模拟信号处理是信号处理的子集。数字信号处理的目的是对真实世界的连续模拟信号进行测量或滤波。因此在进行数字信号处理之前需要将信号从模拟域转换到数字域，这通常通过模数转换器实现。而数字信号处理的输出经常也要变换到模拟域，这是通过数模转换器实现的。

5.21板级支持包BSP(Board Support Package)

板级支持包（BSP）（Board Support Package）是构建嵌入式操作系统所需的引导程序(Bootload)、内核(Kernel)、根文件系统(Rootfs)和工具链(Toolchain) 提供完整的软件资源包。

5.22中断控制器ICU(Interrupt Controller Unit)

多个外部中断源共享中断资源，必须解决相应的一些问题，例如CPU芯片上只有一个INTR输入端，多个中断源如何与INTR连接、中断矢量如何区别、各中断源的优先级如何判定等。可编程中断控制器8259A就是为此目的而设计的，它可以接收多个外部中断源的中断请求，并进行优先级判断，选中当前优先级最高的中断请求，并将此请求送到CPU的INTR端。当CPU响应中断并进入中断服务程序的处理过程后，中断控制器仍负责对外部中断请求的管理。

5.23联合测试行为组织JTAG（Joint Test Action Group）

JTAG是联合测试工作组（Joint Test Action Group）的简称，是在名为标准测试访问端口和边界扫描结构的IEEE的标准1149.1的常用名称。此标准用于验证设计与测试生产出的印刷电路板功能。
在设计印刷电路版时，当前最主要用在测试集成电路的副区块，而且也提供一个在嵌入式系统很有用的调试机制，提供一个在系统中方便的"后门"。当使用一些调试工具像电路内模拟器用JTAG当做信号传输的机制，使得程序员可以经由JTAG去读取集成在CPU上的调试模块。调试模块可以让程序员调试嵌入式系统中的软件。
reference
[1]https://baike.baidu.com/item/%E6%A8%A1%E6%8B%9F%E6%95%B0%E5%AD%97%E8%BD%AC%E6%8D%A2%E5%99%A8/5382125?fromtitle=A%2FD%E8%BD%AC%E6%8D%A2%E5%99%A8&fromid=4883848
[2]https://baike.baidu.com/item/%E5%8F%AA%E8%AF%BB%E5%AD%98%E5%82%A8%E5%99%A8/2399075
[3]https://baike.baidu.com/item/%E7%94%B5%E8%B7%AF%E4%BB%BF%E7%9C%9F
[4]https://baike.baidu.com/item/FPGA