自适应算术编码的FPGA实现

自适应算术编码的FPGA实现（通用8篇）

篇1：自适应算术编码的FPGA实现

自适应算术编码在一次扫描中可完成两个过程，即概率模型建立过来和扫描编码过程。

自适应算术编码在扫描符号序列前并不知道各符号的统计概率，这时假定每个符号的概率相等，并平均分配区间[0，1]。然后在扫描符号序列的过程中不断调整各个符号的概率。同样假定要编码的是一个来自四符号信源{A，B，C，D}的五个符号组成的符号序列：ABBCD。编码开始前首先将区间[0,1]等分为四个子区间，分别对应A，B，C，D四个符号。扫描符号序列，第一个符号是A，对应区间为[0,0.25]，然后改变各个符号的统计概率，符号A的概率为2/5，符号B的概率为1/5，符号C的概率为1/5，符号D的概率为1/5，再将区间[0,0.25]等分为五份，A占两份，其余各占一份。接下来对第二个符号B进行编码，对应的区间为[0.1,0.15],再重复前面的概率调整和区间划分过程。具体的概率调整见表1。

篇2：自适应算术编码的FPGA实现

在利用FPGA实现自适应算术编码的过程中，首先遇到的问题就是将浮点运算转化为定点运算，即将[0,1]区间的一个小数映射为一个便于硬件实现的定点数。考虑到硬件实现的简便性，本文中将[0,1]之间的浮点数与[0,256]之间的定点数对应。相应的对应关系如表2所示。

表2浮点与定点之间的关系

浮点00.20.50.71定点051128179256

编码器在实现编码的整个过程中按照耦合弱、聚合强的原则分为四个模块：修改码表、计算确定区间、并行编码、串行输出。四个模块相对独立，通过输入、输出信号使其构成一个整体。系统的顶层结构如图2所示。

3.2码表的设计及修改

自适应算术编码器可以在许多场合中得到应用。本文实现的自适应算术编码器应用在采用6符号对小波变换系数进行零树编码的小波域视频编码中[3]，因此设计的码表中含有六个符号。这样根据自适应算术编码的基本原理，将区间分成六个子区间，整个区间含水量有七个分割点。所以码表可以用七个8位寄存器表示。初始时设定等概率，这时七个寄存器可以顺序地存储0到6这七个数，即每个子区间的数值为1。随着符号不断地输入，自适应地修改码表，并且在修改码表的过程中时刻要保持寄存器中的数值是递增的。

修改码表时，首先判断输入符号，确定其所在区间，同时为后续模块输出该子区间的两个端点值l_count和h_count以及码表的最后一个端点值scale，然后进行码表的修改：将当前符号所在区间之后的所有端点值都加1，即当前区间及后面所有子我间的h_count=h_count+1,这样即完成了码表的修改。在数值不断累加过程中，寄存器中的数值为255时，需要对每一个寄存器中的值都取半，并同时对相邻的两个寄存器中的值进行比较，时刻保持数值是递值的。这样，处理前后的概率十分接近，对压缩比影响不大。

修改码表模块在输出h_count、l_count和scale之后，后面的计算子区间的模块即可进行计算;而修改码表模块在输出h_count、l_count和scale之后，亦可进行码表的修改。因此，这两个操作可以采用并行处理的方法实现，极大地节省了所用的时钟周期，相应地提高了速度，达到了优化的目的。表3给出了输入符号为3(对应于寄存器2与寄存器3之间的区间)时码表的修改过程。

表3码表修改前后对照表

寄存器0123456修改前04345677112233修改后04345778113234修改前023545657234255修改后011272829117127

3.3区间计算及确定

初始时符号所在的总区间为high=0xff,low=0(high和low分别表示已编码的符号序列所在子区间的上下界)。随着符号的不断输入，high和low的值也不断地减小，用以表示输入符号序列所对应的子区间。通过如下的公式可确定输入符号的区间：

计算时，最耗资源的是乘法器和除法器。本方案中乘法器采用参数化模块lpm中的lpm_mult生成。而除法器则自动编写。虽然占用的时钟周期较多，但与使用lpm相比，这样做可以大大地提高工作频率，从总体上提高性能。

3.4并行编码

在区间计算过程中，high和low总是有限值，不可能无限制地划分下去。为了能够实现连续的编码，通过对high和low的处理，可以实现利用有限长的寄存器表示无限精度的区间，即在不断修改high和low的过程中输出high和low中相同的高端位，形成输出码流。详细过程如下：

在区间确定之后，将low和high按位比较，若首位相同，则输出首位二进制码，产生输出码流，同时把low和high左移，low末位补0，high末位补1。循环比较输出，直到首位不同为止。如：

high=00110110

low=00100111

输出码流为001,而high和low的结果为：

high=10110111

low=00111000

通过这种连续地处理便可生成符号序列的自适应算术编码结束。但随着待编码符号序列的不断输入，可能会出现high和low十分接近，并且high和low的首位没有相同位的情况，如：

high=10000000

low=01111111

称这种现象为产生了下溢。产生下溢后，后面的编码都失去了意义，此时需要特殊处理。

对于下溢的处理方法为：保留首位，同时删除紧接在首位后的high中连续的0和low中连续的1，并且保证对high和low删除的位数相同，若连续0和连续1的位数不同，则取其较小者;然后high和low左移相同的位数，同时high的低位补1，low的低位补0。表4给出了下溢处理前后high和low值。

表4下溢处理前后对照表

下溢处理前下溢处理后下溢个数high10001000110001113low0111011100111000

经过处理后，扩大了区间，使得后面的编码可以顺利地进行。

在考虑了下溢的编码输出中，下溢作为输出码流的一部分，使得解码时能对下溢进行同样的处理，达到编解码的一致。但是下溢产生后并不马上输出，只记下下溢的个数，下溢则是在下一个符号编码时进行输出的。在下一个符号编码时，如果high和low比较后高端有相同位则输出下溢，即在第一个输出后紧接着插入首位的反，插入首则反的个数为前面产生下溢的个数，然后输出相同的次高位及以后相同的各位。这样处理既保留了下溢的信息又使得输出码流不偏离编码符号所在的子区间，使得解码时很容易处理。但是如此high和low比较后没有相同输出则不输出下溢，而是把两次产生的下溢的个数进行累加，再输入下一个符号，直到high和low有相同首位才输出下溢。

例如：在一个符号编码计算后得到的high=11010010和low=11001101，而前一个符号编码产生的下溢为1个，比较后输出为1010，同时记录下产生的下溢2个，如表5所示。

表5含有下溢的编码输出

highlow下溢输出编码输出前110100101100110111010编码输出后11011111001000002

3.5串行输出

并行编码后产生的码流存储在并行数据中，但在大多的情况下只有两、三个输出，甚至没有输出，若采用并行输出，就会产生极大的浪费。为了充分利用资源，在并行编码之后进行并/串转换，使其一位一位地输出，并且这个输出过程与下一个符号编码的过程并行完成，因此并不占用多余的时钟周期。

在编码过程中，当一个符号编码结束后，触发reload信号，通知此次编码结束，进行下一次编码，读取输入的符号。同时需判断输入是否合法，如果是合法的输入，就进行编码;否则停止编码，否则停止编码，处于等待状态，直到复位信号ret置1，重新初始化、编码。

图3

4仿真结果

本文算法采用VHDL硬件描述语言实现，并在ALTERA公司的MAX+plusⅡ软件上编译仿真。市府采用全局同步时钟，避免了毛剌的产生，保证了信号的稳定性。编码的仿真结果如图书3所示。

其中，rst、clk、c为输入信号，rst为模块中各寄存器的初始化信号，clk为时钟同步信号，而c则为输入的编码信号;out_flag、out_bit、reload、end_code、为输出信号，out_flag和out_bit分别为输出标志位和输出位(若out_falg=1,则此时out_bit为有效输出;否则out_bit输出无效)，reload为一个符号编码结束)下一个符号输入的标志位，end_code为编码结束的标志(若end_code=0，则继续编码，否则编码结束)。

在进行性能仿真时[4]，采用的器件是FLEX1K系列的EP1K30TC144-1器件，其最大工作频率为40MHz，消耗1533个LC，平均编码时间为20个时钟周期。一个符号的编码时间不到500ns，对于QCIF格式的图像完全可以满足每秒钟实时编码30帧图像的要求。

篇3：自适应算术编码的FPGA实现

随着现场可编程阵列FPGA的容量、功能以及可靠性的不断提高，采用FPGA设计自适应算术编码器成为一个新的途径。本文充分利用FPGA高速、实时的特点，对原编码器算法进行优化，采用并行运算及流水线设计，最终在FPGA上以较优的速度和资源实现了硬件编码。

1 自适应二进制算术编码的原理

自适应二进制算术编码的编码过程分为概率估计、二进制算术编码以及区间分割与重整三部分，如图1。

系统以待编码比特(Bin)以及上下文编号(CtxIdx)为输入，其概率模型包括低概率符号(LPS)和高概率符号(MPS)的概率状态(StateIdx)。概率估计模块分为概率状态的初始化和重置与概率模型的更新两部分。概率状态的初始化和重置是指在H.264的基本编码单元———片开始时，某些预定义的概率状态通过特定的概率模型进行初始化。概率模型的更新是指：除一个外，所有概率模性均是自适应模型，在每个符号被编码后会自动更新概率模型。LPS量化后的概率值以σ为编号，进行如图2所示的刷新。刷新的具体过程见参考文献[3]。H.264标准中采取概率状态转移表的方式实现概率状态更新。

二进制算术编码部分采用表格的方式避免了乘法运算。算术编码器内在状态被描绘为两个量：当前间隔范围R和当前编码基础L。对于Bin的主要编码流程如图3所示，包括R通过给定的概率估计细分，概率模型的更新以及重整，具体流程解释见参考文献[3]。

区间分割与重整部分主要是对编码器存储精度的控制。在CABAC编码器中存储精度要求在8～9位，即如果新的区间范围R不在合法范围[28,29]之内，则需要进行重整化操作。每个周期重整化都要被执行，输出一位或多位数据。

2 自适应算术编码器的改进

H.264标准中的CABAC编码流程是串行的，适合软件实现，但执行速度很慢且效率低下。而硬件实现的最大优势在于其并行性，可以大大提高执行效率。因此，为了设计出高速的编码器电路，在不改变算法实质的前提下，将标准中的编码流程进行相应的改进，以利于硬件实现。本文主要提出以下改进措施：

(1)对概率状态转移表的改进。H.264中对于概率状态的转移通过概率模型索引pStateIdx进行表征。在进行概率状态转移时，首先判断当前Bin是否为MPS，然后再对该Bin查概率状态表进行状态转移，见表1。对概率状态表的硬件实现通常是采用RAM或寄存器堆搭建而成。经过深入分析，发现表中transIdxMPS的值正好是索引pStateIdx值(除62和63以外)加1所得，故对于(p StateIdx,transIdxMPS)表的实现，不再采取RAM方式，而是以选择器和加法器的方式实现，改进后流程如图4。经过硬件验证，发现优化后的面积为原来面积的90%，且不改变关键路径。

(2)对于LPS对应的码字区间宽度R的查找表的改进[4]。如前所述，在CABAC中算术编码采用基于表格的查找法，故区间宽度R的值对应于64×4的RangeLPS表。在设计中，采用64×4的ROM来存放数值。但是依照H.264标准设计，ROM的入口地址不仅取决于6 bit的概率状态索引值σ，还取决于区间宽度参数ρ的值，这种数据依存关系无疑增加了运算量。且输出是串行，不利于流水线设计，这样就将降低了系统的时钟频率。故采用一种并行设计方案，以σ为输入地址查表，结果得到4个不同的输出，将它们锁存后，利用多路选择器以R[7:6作为控制端选出所需的值。两种不同的实现方式见图5。

(3)对区间重整模块的改进。在重整过程中，必须满足R在[28,29]范围内,每次递归运算后，R可能会变得更小，所以要保持上述要求，就需要对寄存器进行由低位向高位的移位，同时空出来的低位补零，直到第一个非零位在寄存器允许的取值范围移到最高位。当然L也要通过移位与R保持一致的精度。用软件完成概率区间重整需要多次循环，直接串行实现还将占用数量不等的时钟周期。经过仔细研究发现，重整化的循环次数count等于R二进制化值前导零的数目。故R值的更新很简单，只要R左移count位即可，在硬件设计中直接采取移位寄存器即可完成。对于L值的更新较复杂，如果L值移出的count位全为1，则重整化后的L值即为原L值移位count位后的值;否则将移位后L值的最高位置0。总之，采用分离R与L重整的优化方法，使其不必在编码时相互等待，从而加快二元判决编码的速度，改善编码性能。

3 自适应二进制算术编码器的FPGA实现

根据上节的改进编码流程，将整个编码器设计为三个主要模块：概率估计模块、二进制算术编码模块、区间分割与重整模块，如图6所示。电路实现主要分为6级流水线。在第1级流水线中，输入数据进入上下文模型，读取相应数据供后级调用。第2级流水线包含两个模块：概率估计模块和二进制算术编码模块。在软件实现中，这两个模块是串行的，但在硬件设计中，本文抽取两个模块的输入端，同时给它们数据，使其达到并行计算，提高了编码速度。在第3级流水线中，进行的是概率区间R的重整与上下文模型的更新。这也是两个并行运算，同时由于L重整要用到R重整的相关参数，因此放在下一个流水线。第4级流水线完成L的重整。第5级流水线实现数据的最后输出。

在电路设计中，为实现流水线及并行计算，一些关键的模块不可忽略。如采用加法器与选择器完成状态转移表，节约面积;采用移位寄存器完成区间重整，减少运算复杂度，缩短关键路径;采用几个模块并行执行，提高时钟频率等。

4 电路仿真及性能分析

本文的算法经过VC++仿真验证，可对H.264标准中的主要视频码流进行编码，其结果与H.264标准程序JM8.6相同。电路结构采用Verilog语言进行RTL级描述，并用modelsim6.0软件仿真通过。仿真波形如图7所示。

由图7可以看出，数据输出周期数不确定。这是因为，在输出模块对数据进行整理时，其产生的有用数据位数不确定，而只有达到32位时才进行输出，故输出数据的周期性也不确定。

电路在spartan3 FPGA上进行综合、布局布线，使用Synplify工具进行综合，最高时钟频率为90.4 MHz。将综合好的edif电路网表文件输入到后端由FPGA厂商Xilinx提供的Foundation软件进行布局布线，生成二进制流文件，逻辑单元为769，占总资源的22%。

使用本文设计的电路对H.264标准中一些标准视频序列进行测试，序列质量为QP=28，并与H.264标准程序JM8.6、文献[5]中H.264的MQ编码器以及文献[6中JPEG2000的MQ编码器的编码时间作比较，得出如表2所示的结果。

综上，本文设计的算术编码器在速度上较软件实现及其他硬件电路实现有较大提升，资源占用率也较少，不仅能完成H.264标准中基本档次的编码，还有望应用于更大尺寸、更高质量的实时视频压缩编码。

本文在对H.264标准中自适应二进制算术编码器研究和分析的基础上，提出其FPGA电路结构，采用流水线方式实现了电路。本结构经spartan3 FPGA实现，吞吐量为每周期1 bit，最大时钟频率为90.4 MHz，能够适应H.264中level3及以上档次实时视频编码的要求。

参考文献

[1]OSORIO O,BRUGUERA J.Arithmetic coding architecture for H.264/AVC CABAC compression system.in Proc.Eu-romicro Symposium on Digital System Design,2004:62-69.

[2]MARPE D,SCHWARZ H,WIEGAND T.Context-based adaptive binary arithmetic coding in the H.264/avc video compression standard[J].IEEE Circuits and Systems for Video Tech,2003,13(7):620-635.

[3]Joint video team(JVT)of ISO/IEC MPEG and ITU-T VCEG draft ITU-T recommendation and final draft interna-tional standard of joint video specification[S].Pattaya,Thai-land:Final Committee Draft,Document JVT-G050,7th Meeting,2003:7-14.

[4]BOSSEN F.CABAC cleanup and complexity reduction.in Joint Video Team of ISO/IEC JTC1/SC29/WG11&ITU-T SG16/Q.6Doc.JVTE086,Geneva,Switzerland,2002(10).

[5]V H Ha,W-S.Shim,J.-W.Kim.Real-time MPEG-4AVC/H.264CABAC entropy coder,in Proc.Int.Conf.Com-sumer Electron.(ICCE),2005:255-256.

篇4：自适应算术编码的FPGA实现

摘要：为通过雷达编码技术可以使雷达性能得到提高。本文主要研究优化雷达相位编码使得雷达空时自适应处理器的输出信噪比最大的问题。本文考虑以下约束：保证雷达编码与已知巴克码达到一定的相似度、空间和时间多普勒频率估计准确度达到一定的要求，同时考虑到雷达能量的鲁棒性问题。对于上述非凸二次约束优化问题，我们用了快速有效的秩一分解方法。通过仿真实验可以证明，这种相位雷达编码可以使雷达性能提高。

关键词：雷达编码；空时自适应处理器；半定规划；鲁棒性

中图分类号：TN955

文献标识码：A

DOI：10.3969/j.issn.1003-6970.2015.09.006

0 引言

近些年来，随着电子技术的迅猛发展以及雷达新理论、新技术的不断涌现，现代雷达己成为可以测量目标距离、方位、仰角和速度等信息的重要电子设备。由于雷达工作环境日益复杂，如何使雷达在恶劣的环境下，提高其探测目标的能力是人们研究的重点问题。

通常人们采用设计雷达波形（幅度、相位、频率）来提高雷达性能的方法。目前，关于通过雷达波形设计提高雷达检测性能方面有一系列的De Maio等。而传统的滤波器一般只在空域或时域空间内进行信号处理，很多情况下这种一维的滤波器已不能满足实际的需要。空时白适应处理技术，即同时在空域和时域内对信号进行处理，可实现更强的杂波抑制。巴克码具有尖锐的白相关函数，合理的距离分辨率和峰值旁瓣电平。因此，设计空时白适应雷达波形时，可考虑与已知巴克码的相似度约束。

本文研究通过设计雷达相位编码，使空时自适应处理器的输出信噪比最大。除了与已知巴克码的相似度约束外，考虑由系统不稳定引起的雷达编码能量的鲁棒性问题。即在下述约束下使空时白适应处理器的输出信噪比最大：考虑鲁棒性的能量约束，空间多普勒频率估计准确度，时间内多普勒频率估计准确度，相似度约束。上述问题为非凸二次约束问题，将其松弛成半定规划问题求解。通过仿真画出雷达编码检测概率图、CRB图以及模糊函数图来分析相位编码雷达的性能。

3 结论

篇5：自适应算术编码的FPGA实现

报文是通信交换与传输的基本数据单元,承载了数据信息,在实际使用中,为便于观察、交互,许多格式具有特定字符特征,比如广泛使用的NMEA—0183协议。随着信息时代的来临,各种报文的信息呈现海量特性,为共享、存储、分发带来较大压力。比如覆盖整个城市的车辆(公交车、出租车)监控、调度系统,各车辆将自身属性(如位置、状态)等通过特定报文格式经无线信道传输至中心,同时,中心会为各车辆建立历史情况数据库,数量巨大的车辆信息给通信、存储带来不便。同样,在部分窄带信道(如短波、超短波信道)传输报文时,信道速率的提升(功率、天线增益)潜力非常有限,为在有限的带宽中传输尽可能多的信息量,从信源角度进行压缩编码是一种较好的方法。

报文的自身特点要求其压缩编码必须为无损、可逆的,典型的无损编码方法有基于统计模型的BCD编码、Huffman编码和算术编码[1],基于字典模型的LZW编码[2]等。其中,BCD编码可认为是一种等概率Huffman编码模型,而Huffman编码中存在比特数必须取整的问题,其限制了压缩比,LZW编码不适用于猝发、较短报文的处理,上述方法均不适用。算术编码采用以一个单独的浮点数代替一串输入符号的思想,避开了使用一个特定码字代替一个输入符号,被认为是最逼近熵编码[3]极限的一种编码方法,得到了广泛的应用。基于这样一种现状,本文从信源角度出发,提出将算术编码应用于字符型报文的压缩,并对其作出相应优化,经测试,压缩效果良好,大幅提高了报文的传输效率,尤其是窄带信道下的报文传输,效果更为明显。

1算术编码原理

算术编码的基本原理可参考文献[1,4],且根据字符概率统计方法的不同,具体分为静态算术编码和自适应算术编码。静态算术编码的实现包括概率模型建立和扫描编码两个过程,计算量较大,且各符号概率是通过统计信源所有信息而得,由信息熵可知,其压缩效果受限;而自适应算术编码并不需要在编码前统计信源符号的概率分布,而是在编码过程中,随着符号的读入实时地动态更新信源符号的概率分布,从而统计出各符号相对于上下文的概率,压缩效果好于静态模型[5]。

下面以静态算术编码为例,对编码过程具体描述如下

假设某报文字符集合由3个字符{a1,a2,a3}组成,现有一条报文为“a2a3a3a2”, 其字符概率分布如表1所示,P表示字符Code的概率,Range表示字符Code的相应的初始子区间。编码开始之前,初始区间为半开区间[0.0,1.0),如图1中R(begin)所示,依据概率分布,将之分为 [0.0,0.2)、[0.2,0.6)、[0.6,1.0) 互不重叠的3个子区间,分别对应于字符a1、a2、a3,以保证报文中不同字符对应不同的区间;读入第一个符号a2,其对应区间R(a2)映射为 [0.20,0.60),同样依据概率分布将R(a2)再细分为3个子区间。按此过程,逐个读入字符,可发现区间范围逐渐缩小,并在编码结束时,区间缩小为[0.54880,0.57440),即R(a2a3a3a2),且该区间任何一个实数均可以作为编码结果,编解码端采用相同的处理机制即可正确地解码。

2一种新的字符型报文压缩技术

理论上,按照上述方法可以完成算术编码,但是在具体实现过程中还是存在一些问题的,比如概率模型建立、浮点精度等问题。本文提出的字符型报文压缩技术通过引入静态概率表和自适应概率表的建立,实现整数化算术编码,并提出一种直接、有效的编码区间移位方法,不仅解决了这些问题,且压缩比接近或达到熵编码理论的最大值,具体编码步骤见图2。

2.1静态概率表的建立

报文压缩过程中,在初次编码时首先需要对该报文的字符集合进行静态频率表的建立,也即频率表的初始化工作,其主要体现在图2中的预处理步骤。对于静态频率表的建立,现提出其可根据经验值建立,以使报文在编码起始阶段就能够达到较好的压缩效果;也可将其设置为等概率频率表,即Pi=1/N,并且在编码过程中,可根据读入报文动态地进行更新。

2.2自适应概率表的建立

在使用算术编码对读入报文进行编码的过程中,频率表的更新在很大程度上影响着编码效率和压缩比。对于频率表的更新给出了一种优化的自适应更新方法,具体采用两种方式,一是在编码过程中逐字符进行更新,即对本条报文中各个字符进行算术编码后,均更新频率表,具体在图2中表示为“更新频率表方式一”步骤。但是,这种对频率表的更新方式会占用一定的计算量,若计算资源受限则无法适用。对此,提出另外一种方式,即频率表的更新以若干条报文为单位进行,对单条报文逐个字符进行算术编码后,仅记录各个字符出现的次数,在达到设定的若干条报文编码结束后再根据记录情况进行频率表的更新,具体在图2中表示为“更新频率表方式二”步骤。其中,更新频率表方式一充分考虑了字符概率问题,尽可能地增大了报文压缩比,而方式二更是满足了计算资源受限的环境。

2.3整数化算术编码

算术编码在具体实现过程中存在一个致命的缺点,随着信源符号的持续读入,表达编码区间的小数的精度越来越高,其对算术编码在计算机上的实现造成了障碍。文献[6]提出了整数化算术编码的思想,即对于编码区间的表示只取尾数,比如上述举例区间[0.54880,0.57440)可表示为[5488,5744),同时每编码一个符号,均对区间按照一定规则进行更新以及放大,保证下一次编码区间的划分精度。假设算术编码所采用的初始编码区间为[0, Max],Max为区间最大值,一般设置为0xFFFF,编码过程中区间为[Low,High],区间范围为Range,其中Low为区间下沿,初始为0,High为区间上沿,初始为Max,现读入字符为C,其概率为P,累计频率为 CumP,则编码区间的更新公式如式(1)—式(3)所示,而编码区间的放大、移位方法具体参考文献[6,7],且区间放大和移位的信息就是输出码字。该方法使得算术编码可以在有限区间上模拟无限区间的运算,克服了使用计算机时精度受限的问题。

$\begin{array}{l}\text{R}\text{a}\text{n}\text{g}\text{e}=\text{Η}\text{i}\text{g}\text{h}-\text{L}\text{o}\text{w}+1(1)\\ \text{Η}\text{i}\text{g}\text{h}=\text{L}\text{o}\text{w}+\text{R}\text{a}\text{n}\text{g}\text{e}(\text{C}\text{u}\text{m}\text{Ρ}+\text{Ρ})-1(2)\\ \text{L}\text{o}\text{w}=\text{L}\text{o}\text{w}+\text{R}\text{a}\text{n}\text{g}\text{e}\text{C}\text{u}\text{m}\text{Ρ}(3)\end{array}$

但是,显然并不是每编码一个字符都需要进行这样的移位处理,在文献[7]在文献[6]的基础上针对DSP流水线结构提出了一种通过查表判断是否进行移位操作的方法,其不可避免地需要频繁地查表,且适用范围有限。现从编码区间满足解码的基本条件出发(以下称之为可译性),提出一种直接、有效的移位方法,其不仅减少了运算量,而且进一步提高了压缩比。

假设在编码某一字符后自适应频率表中统计的总累计频数为_Total_Freq,当前区间上沿为High,下沿为Low,则可译性可表示为:

$\text{Η}\text{i}\text{g}\text{h}-\text{L}\text{o}\text{w}>=\_\text{Τ}\text{o}\text{t}\text{a}\text{l}\_\text{F}\text{r}\text{e}\text{q}(4)$

其实质是指当前编码区间按照总累计频数和各字符的累计频数进行细分区间时,最小区间的大小_Min_Part应满足条件:

$\_\text{Μ}\text{i}\text{n}\_\text{Ρ}\text{a}\text{r}\text{t}>=1(5)$

其中,在满足式(4)条件下,当且仅当某一的字符累计频数为1时,式(5)才有可能出现相等的情况。具体编码过程中,若当前编码区间不满足可译性,则进行移位操作(具体参考文献[6]提出的方法),且在区间扩展过程中,若区间满足可译性,即编码下一个字符。同时,_Total_Freq一直处于动态变化中,也即可译性可以根据编码的进展自适应地判断是否需要移位操作。经验证,尤其是在编码初期,减少不必要的移位次数更多,其压缩效果更加明显。

3采用NMEA—0183协议的仿真实验结果

NMEA—0183是美国国家海洋电子协会为海用电子设备制定的标准格式,本节以此报文协议中大地坐标信息格式为例,并假设基于该格式的一条报文Message为:“$GPGLL,0123.4567,S,89012.3456,E,78901.234,A*56”,选取BCD扩展码、Huffman编码和算术编码三种方式进行压缩以及比较。

由于该协议的字符集合由33个字符组成,若使用BCD扩展码压缩,则每个字符需要6个二进制位表示;对于使用Huffman编码压缩,可参考文献[1]中所述方法;同时使用本论文提出的方法压缩。首先仅对一条报文压缩,然后,逐渐增加报文Message的条数至100条,若将压缩比定义为压缩前数据量与压缩后数据量的比值,则对1条、100条报文压缩的数据结果如表2所示,并将Huffman编码和算术编码的压缩过程分别绘制成图3、图4。

通过表2的压缩数据可发现,使用本论文提出的面向字符型报文的算术编码方法对报文进行压缩得到的压缩比相比较其它两种方式有显著的提高。尤其是当字符串的长度越大,字符的概率越明显时,使用算术编码方式的压缩比可以接近甚至达到理论熵极限,而BCD编码和Huffman编码由于未考虑字符间的联合概率等原因,压缩效果相对较差。比如本实例中,当报文条数增至100条时,其压缩比为1.9296,已经非常接近理论压缩比。同时,通过图3、图4的压缩比趋势可以再次验证这一结论。此外,经过对某短波报文传输系统进行连续4个小时的测试,比对结果发现其压缩比平均达到了2.5,效果良好。

4总结

本论文根据报文的字符集合特点,提出了一种适用于字符型报文的无损压缩方法,目前,本方法已在某短波报文传输系统中得到应用, 实现平均约2.5倍的压缩比,压缩后报文长度的缩短还大大降低了传输延时,取得了良好的效果。同时,本文虽面向字符型报文,但其核心实现原理仅对元素集合概率相关,可扩展至任意有限元素集合的报文传输中,在此不再赘述。需要同时指出的是,报文的压缩仅属于报文编码的一部分内容,为能够在工程中应用,还需要统筹考虑报文的同步、校验、纠错、关联、时延等方面,不属于本文探讨的内容,但进行报文压缩后,为采用其它编码方法带来了较大的应用空间。

摘要：文中面向字符型报文,提出了一种全新的无损报文压缩技术。该技术引入算术编码,提出了报文字符集合静态概率表的建立以及自适应概率表更新方法,并提出了一种直接、有效的编码区间移位方法。文中首先采用实例对算术编码原理进行了详细介绍,其次阐述了压缩技术方案原理,并给出了程序设计流程图。最后,以NMEA—0183格式报文为样本进行测试,给出了算术编码以及其它几种无损压缩编码的实验结果,并进行了比较分析。结果表明,文中提出的方法具有良好的压缩效果。

关键词：无损压缩,字符型报文,算术编码

参考文献

[1]Sayood K.数据压缩导论.北京:人民邮电出版社,2009

[2]王平.LZW无损压缩算法的实现与研究.计算机工程,2002;28(7):98—150

[3] Shannon C E.A mathematical theory of communication.Bell SystemTechnical Journal,1948;27:379—423,623—656

[4]李彬,倪桂强,罗健欣.多阶自适应算术编码研究.微型机与应用,2010;29(12):71—74

[5]杨文涛,刘卫忠,郑立新,等.多阶上下文自适应二进制算术编码实现.华中科技大学学报(自然科学版),2007;35(3):42—45

[6] Witten I H,Neal R M,Cleary J G.Arithmetic coding for data com-pression.Communications of the ACM,1987;30(6):520—541

篇6：自适应算术编码的FPGA实现

关键词:常规PID控制器 恒温箱

中图分类号:TP273文献标识码:Ａ文章编号:1674-098X(2011)02(b)-0121-02

1 模糊自适应PID控制原理及结构

模糊自适应PID控制基本原理:以误差e和误差变化作为输入,运行中不断检测e和,并利用模糊规则进行模糊推理,查询模糊矩阵表调整参数,满足不同时刻的e和对PID参数自整定的要求,利用模糊规则在线修改PID参数,以使被控对象具有良好的静态、动态性能。模糊自适应PID控制系统结构如图1所示。常规PID控制器作为一种线性控制器,其离散的控制规律为:

对于系统被控过程中不同的|e|和||,PID参数、、的自整定原则如下:(1)误差|e|较大时,为加快系统的响应速度,使系统具有快速跟踪性能,应取较大和较小。同时,为了防止积分饱和。避免系统超调过大,应限制或使其为零。(2)误差|e|和||中等时,为使系统超调较小,应取较小,适当和,特别是的取值对系统响应影响较大(一般取值较小)。(3)误差|e|较小时,为使系统具有较好稳态性能,应取较大和。同时,为避免系统在平衡点附近出现振荡,应取合适的值。||较大时,取较小;||较小时,取较大。

考虑到上述原则,在该设计中,模糊控制器采用2输入,3输出的结构。以误差e和误差变化作为输入,经量化和模糊化处理后,查询模糊控制规则表,得到模糊输出量、、,再经解模糊和量化因子输出精确量,并将该输出量与传统PID相结合输出系统的控制量。输人语言变量e和以及输出语言变量、、的模糊集论域均设为{-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6},取相应论域上的语言值为{NB,NM,NS,ZO,PS,PM,PB}。考虑到对论域的覆盖程度及灵敏度,鲁棒性和稳定性等原则,各模糊子集隶属度函数均采用三角形隶属函数。

模糊规则采用“if e is A andis B thenis C andis D andis E”的方式,控制器参数模糊推理过程采取Mam-dani直接推理法,“与”运算采用极小运算,“或”运算采用极大运算,模糊蕴含运算采用极小运算,模糊规则综合采用极大运算,去模糊化采用重心法且其计算公式为:

(2)

根据PID参数调整原则,输出量、、一轮决策将最多涉及147条推理规则。

2 恒温箱温度控制系统硬件电路设计

温度控制目前大多采用以单片机或CPU为核心的控制系统,这些以软件控制和运算的系统相比于硬件系统速度要慢、实时性差且可靠性低。FPGA作为一种新型的数字逻辑器件,具有集成度高、可重复编程、逻辑实现能力强、设计灵活等特点,使用其内部逻辑模块单元实现所需功能,各个模块并行运行,与传统的基于CPU并行计算不同,FPGA内部结构真正实现并行计算,而不是宏观上并行微观上分时运算,这使得系统运算速度快、实时性强。

该设计采用Altera公司的Cyclone系列FPGA器件EP1C12为核心控制器来测量与控制恒温箱内温度。通过键盘向FPGA输入设定温度,现场温度参数由热电偶传感器转换成电动势信号,经A／D转换和滤波后,将实时的数字测量值送入FPGA。FPGA将比较温度的设定值与测量值,经模糊自适应PID控制算法运算处理后,输出相应控制信号,确保恒温箱内温度变化范围始终保持在设定值的误差范围内。系统的液晶显示用于实时显示控制系统的当前温度值、温度变化曲线、参数配制等信息;键盘用于设定控制系统的初始定值及初始参数信息;Flash,SDRAM,C等用于实现存储空间的扩展。图2为系统整体硬件结构框图。

此外,在FPGA中还集成有Altera公司提供的NIOS II软核处理器,FPGA一方面通过内部的双口RAM与其内部的硬件逻辑控制模块进行通讯,获取控制模块的状态信息并配置其参数;另一方面监控显示模块和键盘模块。FPGA内部逻辑示意图如图3所示。模糊自适应PID控制模块是整个控制系统的核心,可实现模糊参数自整定PID控制算法。为便于实现计算机的实时控制,采用离线计算,在线查表方式。如有需要,只需重新修改控制算法模块,并重新配置FPGA,就可实现控制算法升级。

3 嵌入式软件设计

基于NIOS软核CPU的嵌入式软件设计采用C语言编写完成,该嵌入式软件设计主要实现人机交互和模糊自适应PID控制模块监控两部分功能。温度控制系统上电启动后,首先初始化系统,然后模糊自适应PID控制模块读双口RAM1获得控制器的初始参数信息,并进行控制运算,根据运算所得结果在显示屏上显示当前温度控制系统的参量及温度变化曲线等当前状态信息,同时将这些实时控制参数及状态信息写入双口RAM2保存,NIOS软核处理器再由RAM2中读取数据,获得模糊自适应PID控制模块的当前状态信息。若由键盘重新输入新的温度设定值,则当系统读取到该值时,自动查询模糊控制规则表修改双口RAM1中的配置参数值,重新代入模糊自适应PID控制模块进行运算,并将新的参数值及系统实时状态信息写入双口RAM2保存且反馈给NIOS软核;若无键盘输入,则系统状态保持不变。

4 实际运行结果及存在问题

对于具有大惯性、大滞后等特点的温度控制系统,基于FPGA的温度模糊自适应PID控制器可取得良好的控制效果且自适应能力强。但在控制器的应用过程中仍存在一些问题,如模糊规则和隶属函数的优化、系统抗干扰性能的增强等。因此,仍需进一步完善和修改该控制系统。

5 结语

该设计基于高密度的可编程逻辑器件FPGA,在传统PID控制器的基础上利用模糊控制的优点控制恒温箱的温度。结果表明,该控制系统具有良好的动、静态性能和鲁棒性能,对参数时变具有很好的适应能力,实时计算量小,调校方便,且具有良好的升级性能和灵活性。市場应用前景较好。

篇7：浅谈自适应滤波器的FPGA实现

1.1 自适应滤波。

自适应滤波是在部分信号特征未知的条件下,根据某种最佳准则,从已知的部分信号特征决定的初始条件出发,按某种自适应算法进行递推,在完成一定次数的递推之后,以统计逼近的方式收敛于最佳解。

1.2 自适应滤波器结构。

自适应滤波器结构与它的算法有着紧密的联系,这是因为自适应滤波器不但要估计滤波器所能实现期望信号的输出,又要不断估计滤波参数,使其朝有利于目标方向的调整,并保证滤波器的稳定可靠工作。

为此,结构的选取不仅会影响到计算复杂度(即每次迭代的算术操作数),还会对达到期望性能标准所需的迭代次数(自适应收敛的时间)产生影响。另外,不同的结构还有特定的应用场合,需要根据实际环境来选择相应的结构和算法。自适应滤波器根据其冲击响应的形式一般分为有限冲击响应自适应滤波器(FIR)、自适应格型滤波器和无限冲击响应自适应滤波器(IIR)三种结构。

2 FPG设计流程

FPGA器件具有集成度高、体积小、可通过用户编程实现专门应用的功能。它允许电路设计者利用基于计算机的开发平台,经过设计输入、仿真、测试和校验,直至达到满意的效果。使用FPGA器件不但大大缩短系统的研制周期,减少资金的投入,采用FPGA器件还可以将原来的电路板级产品集成为芯片级产品,从而降低了功耗,提高了可靠性,同时还可以很方便地对设计进行在线修改。下边对其设计流程做简单介绍:

可编程逻辑器件的设计是利用EDA开发软件和编程工具对器件开发的过程。

高密度复杂可编程逻辑器件的设计。它主要包括设计准备、设计输入、功能仿真、设计处理、时序仿真和器件编程测试等六个步骤。

(1)设计准备。在系统设计之前,首先要进行方案论证、系统设计和器件选择等准备工作。一般采用自上而下的设计方法,也可采用传统的自下而上的设计方法。

(2)设计输入。设计输入将所设计的系统或电路以开发软件要求的某种形式表示出来,并送入计算机的过程称为设计输入。设计输入通常有以下集中形式:a.原理图输入方式;b.硬件描述语言输入方式;c.波形输入方式。

(3)功能仿真。功能仿真也叫做前仿真。用户所设计的电路必须在编译之前进行逻辑功能验证,此时的仿真没有延时信息,对于初步的功能检测非常方便。仿真中如发现错误,则返回设计输入中修改逻辑设计。

(4)设计处理。设计处理是器件设计中的核心环节。在设计处理过程中,编译软件将对设计输入文件进行逻辑化简、综合优化和适配,最后产生编程用的编程文件。主要有:a.语法检查和设计规则检查;b.逻辑优化和综合;c.适配和分割;d.布局和布线。

(5)时序仿真。时序仿真又称后仿真或延时仿真。由于不同器件的内部延时不一样,不同的布局布线方案也给延时造成不同的影响,因此在设计处理以后,对系统和各模块进行时序仿真,分析其时序关系,估计设计的性能以及检查和消除竞争冒险等是非常有必要的。

(6)器件编程测试。时序仿真完成后,软件就可产生供器件编程使用的数据文件。

3 自适应滤波器的FP-GA设计

自适应滤波器的FPGA设计是利用算法选取的最佳自适应参数(阶数、步长系数),实现从算法模型到电路模型的转换并下载到芯片的过程。一般地,数字滤波器的FPGA实现是用VHDL硬件描述语言通过编写底层代码实现的。

经过研究实践证明用FPGA来实现自适应滤波器,最理想的算法是最小均方(LMS)算法。

3.1 算法描述。

输出信号y(n)、输出误差e(n)的计算公式为:y(n)=w(n)XT(n),e(n)=d(n)-y(n)=d(n)-w(n)XT(n)。

其中,x(n)表示第n个时刻输入信号向量,M为滤波器的阶数,d(n)表示第n个时刻的输入期待响应,y(n)、e(n)分别表示第n个时刻的输出信号与输出误差,w(n)表示n时刻权系数向量。权系数是不断更新的,权系数的更新使用下式:

w(n+1)=w(n)+μ[-!(n)]

式中μ表示收敛因子,自适应滤波器收敛的条件是。

其中"max是输入信号的自相关矩阵此时,权系数的更新可以表示为w(n+1)=w(n)+2μe(n)x(n)。

权系数可以非常方便的更新,但是有一个问题:对当前的权系数进行更新,必须知道当前时刻的误差信号e(n),显然必须在输出信号y(n)与误差信号e(n)计算完毕后才能进行权系数的更新;换言之,权系数的更新与滤波(y(n)的计算)不能同步进行。如果能够实现权系数的更新与滤波同步进行,那么在滤波的同时权系数也被更新了,这样,自适应滤波器的滤波速度将提高将近一倍,为了实现这一点,必须对LMS算法进行改进。权系数的更新之所以不能与滤波同步自适应算法还能成立,权系数更新与y(n)的计算就能够同步进行了。改进后的权系数更新方程为:w(n+1)=w(n)+2μe(n-1)x(n-1)。

3.2 硬件设计。

由LMS算法的递推式可以看出,LMS自适应滤波器可由延时单元、加法器与乘法器组成。其中第一个式子就是FIR横向滤波器的表达式,这可以由抽头延迟线构成;第二个式子是误差产生模块,用减法器就可以实现;第三个式子是实现误差更新,可由加法器、延迟模块与乘法器实现。由此,可以得到LMS自适应FIR滤波器的抽象模型和电路结构图。

这里设计一个8阶自适应滤波器,如图2所示。在图中,我们可以看到A1、B、C1、D1、E1、G1用于计算输出信号y(n)(即滤波器的追踪部分),由于在运算过程中,累加器的内容不断变化,等运算完毕以后,才等于输出信号y(n)。要保存y(n)的值,必须提供一个寄存器,它就是图2中的寄存器G1。F用于产生输出误差e(n),并将误差锁存在寄存器G2中,以供更新权系数只用;A1、A2、B、C2、D2、E2用于更新权系数(即滤波器的训练部分),更新过程中采用的误差为上一次计算所产生的并保存在寄存器G2中的误差e(n-1)。从图2中可以看出,x(n-1)与e(n-1)相乘用的是乘法器,但是二者的乘积与2μ相乘,使用一个数据选择器来实现。这是因为2μ为收敛因子的两倍,通常数值远小于1,只要满足收敛条件,它的值大一点或者小一点对滤波效果影响并不是很明显。

最后就可以通过移位运算来代替乘法运算,从而大大减少电路所耗的硬件资源;不仅如此,由于这样实现起来电路的延时远小于一个乘法器的延时,用数据选择器代替乘法器可以很大程度上提高滤波器的最高采样频率。当移位寄存器A1和寄存器A2用于存放输入数据x(n),移位寄存器B中存放的是权系数。当采样的输入信号x(n)准备好以后,应发出一个准备好的信号READY给滤波电路的控制器,它就可以开始滤波了。

小结:自适应滤波器设计是信号处理中的一个非常重要组成部分。在实际应用中,由于没有充足的信息来设计固定系数的数字滤波器,因此设计规则会在滤波器正常运行时改变,为此我们应当认真研究自适应滤波器。由于本人水平有限,文章中如有问题,敬请指正。

摘要：自适应滤波器作为智能天线技术中的核心部分。它的性能就显的非常重要,随着现场可编程门阵列(FPGA)的出现将电路板级产品集成为芯片级产品,提高了可靠性,并能对自适应滤波器设计进行在线修改。本文简单介绍了自适应滤波器和FPGA设计方法,分析了基于FPGA的自适应滤波器的设计。

关键词：自适应滤波器,智能天线,FPGA,在线

参考文献

[1]何永泰.DA自适应数字滤波器在FPGA中实现的改进研究[J].云南师范大学学报,2007.

[2]陈艳.一种改进的自适应滤波器的原理与FPGA实现[J].电子工程师,2004.

[3]余胜泉.自适应LMS滤波器在FPGA中的实现[J].微计算机信息,2006.

篇8：自适应算术编码的FPGA实现

关键词：高速网络；负载均衡；负载均衡技术；网络处理

中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)15-30729-02

Implementation of self-adapting Load Balance Technique of High-speed Network

ZHENG Zhi-xian1, CHEN Hua1,2, XU Rong-sheng3

(1. Fujian Communication Technology College, Fuzhou 350007, China; 2. Fuzhou University, Fuzhou 350002, China; 3. Network Security Lab, Institute of High Energy Physics, CAS, Beijing 100049, China)

Abstract:Gbit network developes andits scale and speed have brought a new challenge to network processing .The difficulty of processing technology for High-speed network is how to make processing speed match network speed.The load balance technique can solve it.The present researches all base on the NP, and the hardware requirement are higher.The thesis puts forward a software solution to achieve load balance for network processing.And it is proved that the solution is well done .

Key words:High-speed network; load balance; load balance technique; network processing

1 引言

Gbit网络的出现，其规模和速度都给网络处理带来了新的挑战，如何实现在高速链路中的处理能力也成为了当前各种网络处理系统讨论的焦点。一种观点认为高速网中的网络处理是不实际的，因为当前的技术很难实现处理速度与网络速度的匹配，丢包的问题势必造成很高的错误；另一种观点是利用多个处理器并行工作，将网络流量分成单个处理器能处理的多个部分，以实现高速网络中的网络处理。由此可见，研究网络流的负载均衡技术在现实中具有重要的意义。目前在网络中负载均衡技术应用较多是网络处理器（NP）[1,2]。这些应用需要从硬件上改造网络处理能力，下面提出一个软件方案，在现有的条件基础上实现大规模网络的负载均衡。

2 技术背景

2.1 负载均衡技术

负载均衡技术[4]通过一些工具实时地分析数据包，掌握网络中的数据流量状况，把任务合理均衡地分配出去，用多个设备共同完成任务，从而以较低成本消除网络瓶颈，提高网络的灵活性和可靠性。负载均衡技术面临的问题有3方面：负载状况的定义、如何获取网络数据以及获取后如何处理的问题。而如何处理实际上就是选择合适的负载均衡算法，它能保证设备协同完成任务，消除或避免现有的网络负载不均、数据流量拥挤和响应时间长的瓶颈。

2.2 负载均衡

将负载均衡技术应用在网络处理系统中，是为了解决高速网的网络速度与处理速度不匹配的问题，将从网络中均衡地捕获的数据包再分配给各处理节点进行处理。所以负载均衡技术满足以下条件将更有利于实现网络分析处理：

(1)属于同一IP的所有数据包应由同一个捕获节点完成。

(2)同一类型的数据包，即使用同一协议的数据包集中在一起以便共同处理。

(3)可扩展性和容错性。随网络中的流量发生变化，捕获节点负载分配不均或崩溃时，负载均衡技术都能针对具体情况进行响应，调整数据捕获节点之间的负载，使之重新达到均衡，并且使对其余数据分析处理器的影响降低到最小。

如何在多个数据捕获器之间分配流量是关键问题。其分配方法，在分流节点按照控制节点根据当前情况定义的策略向各捕获节点分配任务，通过调整对应于捕获节点的这些策略来保证每个数据捕获节点的负载均衡。

3 流量分配策略

网络处理第一步就是捕获所有网络流。通常情况下，数据捕获器直接连接到主要入口和路由出口处。它就像sniffer软件那样捕获经过路由器的IP包。分离网络数据流是常用的解决方式。我们可以采用好几种策略。本节给出动态流量分配思想：选择一种或多种被检测网段内主要的服务类型的流量单独对其进行处理，其余类型的流量合并为一类，并且每一种类型的流量都按照一定的流量分配算法分配到各个网络捕获节点，其结构图如图1所示。

图1 动态流量分配结构

3.1 动态负载均衡策略

分离网络数据流是负载均衡常用的解决方式。我们可以采用以下几种策略。

3.1.1 以IP段来分类

每个单位网络都有它们自己的IP段。比如，某单位的IP段是137.138.1.1至137.138.2.254。因此，如果有3个DC，我们就能以以下的方式自动地捕获数据包：

DC1 ------------- 137.138.1.1

DC2 ------------- 137.138.1.2

DC3 ------------- 137.138.1.3

DC1 ------------- 137.138.1.4

……

DC2 ------------- 137.138.2.254

3.1.2 以流入或流出来分类

由于网络捕获器通常直接连接到机构的中心交换机或路由器上，多数IP包很自然地被分成2类，即流入包和流出包。因此很容易设置一部分网络捕获器捕获流入包而另一部分捕获流出包。

3.1.3 以协议来分类

TCP/IP协议模型中，TCP层有两个协议：TCP和UDP。所以我们可以分配一部分网络捕获器只处理TCP包而另一部分只处理UDP数据。网络捕获器的数量取决于网络数据流和网络捕获器的硬件性能。

一般情况下仅使用其中的一种是不能均衡DC的负载。比如，一些企业流入流量比流出流量大得多，而大部分网络服务提供商则流出流量比流入流量大得多。而且不同类型的流量比率也不全是一样的。流量状况经常发生变化。因此为了在捕获器间更好地均衡负载，最好是三种策略的组合。

有很多方式组合这些负载方法。这些方式组合很大程度上取决于开发者的环境需要。每个DC分配的IP范围有静态分配和动态分配两种选择。一般后者比前者更适合网络处理应用。下面我们提出实现动态负载均衡网络流的过程。

3.2 动态负载均衡实现

每个捕获器上有个配置文件，指明本机捕获的IP段和所覆盖的协议。捕获器从中央管理器获取其配置文件。每个捕获器有个运行中的daemon来检查自己的状态，如CPU、内存和网络使用情况，然后把结果送给每个机器。中央管理器检查捕获器的状态，然后给每台机器做最新的配置。它把所有的捕获器看成一个整体，并定期地刷新。如果一个捕获器崩溃了，中央管理器不能接收到该机器的状态，那么就把崩溃机器负责的负载均衡到其他捕获器上。如果一个新的捕获器加入，中央管理器将被告知然后为每个捕获器创建配置文件。这样移走或增加捕获器变得更容易、更安全。

3.2.1 捕获器的综合负载指数

每个捕获器上都有一个daemon定期发送综合负载情况。daemon从本机/proc/目录里获取各种基本负载信息。该程序将本机上的CPU Load、登录会话数、内存用度等进行综合计算，再传给中央管理器。

/proc/loadavg：CPU平均负载

/proc/meminfo：内存使用情况

/proc/stat：swap使用情况

/proc/net/dev：网络流量情况

……

然后，根据一定的综合负载算法得出本机的综合负载指数GLI。下面介绍综合负载算法。

3.2.2 综合负载算法

本机负载指标主要记录各种负载信息，如当前CPU负载CPULOAD、当前内存利用情况MEMORY、当前磁盘交换分区使用情况SWAP、当前网卡负载NICLOAD。

综合负载可以通过以下公式计算出：

GLI=R1*CPULOAD+R2*MEM+R3*SWAP+R4* NICLOAD，其中∑Ri=1。

若当前的系数Ri不能很好地反映应用的负载，系统管理员可以对系数不断地修正调整，直到找到贴近当前应用的一组系数。

另外，关于发送负载信息时间间隔的设置，虽然很短的间隔可以跟确切地反映各个节点的负载并及时作出调整，但是很频繁地查询（如1秒钟几次）会给节点带来一定的负载。所以，这里要有个折衷，我们一般建议将时间间隔设置在5至20秒之间。

我们依据上述算法思想做了一个评估实验，测试了大量配置相同的机器的运行情况，得出每个机器上的CPU、内存、交换空间、进程数等，然后估算出各个参量值的权重系数{0.4,0.3,0.1,0.2}：

表1各种负载系数

于是得出综合负载指数为：

GLI=R1*CPULOAD+R2*MEM+R3*SWAP+R4* NICLOAD，其中∑Ri=1。

3.3 中央管理器

将要处理的网络IP数列出，同时根据协议类别形成多个任务。中央管理器接收到各个捕获器的综合负载指数，根据其负载能力分配任务。在系统运行过程中，流量发生变化，则需要对各种流量对应的捕获器作调整，并将任务重新同步发送到各捕获器上。每个捕获器上的配置如下：

task.conf文件

seize

{ host ipaddr;

protocol pro;

int port; };

……

4 数据捕获的设计

BPF包捕获技术提供了基于内核的过滤和缓冲，在高速高负载网络中可获得较好的性能。每个捕获器的网络数据捕获基于libpcap。libpcap作为一个通用可移植的包捕获API函数库，提供了对BPF的内在支持，为底层网络监听提供一个可移植框架。BPF改进了过滤方式，使用基于寄存器的过滤求值程序， 同时还使用了一种简单的缓冲策略， BPF的性能大幅度得提高。BPF过滤器和缓冲器是经过优化的，用户可用BIOCSBLEN ioct1()增加缓冲区长度。

每个捕获器将读入其配置文件，通过libpcap的Pcap_setfilter来设置过滤器，完成给它分配的捕获任务。在实现上，为提高捕获速度，技术上做以下改进：引入“零拷贝”技术[3]。

传统的Libpcap采用BPF方式来实现对网络数据的采集，从网卡抓包到应用程序获取数据包要经历3次拷贝：网卡到内核缓冲区；内核中复制一份，一份交给正常的应用程序，另一份交给抓包程序；内核到应用层的拷贝。这三次拷贝中主要是后两次所消耗的资源比较大，影响系统的整体性能。引入零拷贝技术，取消后两次拷贝操作，让应用程序直接访问网卡复制到内核缓冲区的数据包，实现CPU的零参与，彻底消除CPU在这方面的负载。

零拷贝技术首先利用DMA方式将网络数据包直接传递到系统内核预先分配的地址空间中，避免CPU的参与；同时将系统内核中存储数据包的内存区域映射到网络数据获取的应用程序空间，以对这块内存进行访问，从而减少了系统内核向用户空间的内存拷贝，同时减少了系统调用的开销。

5 性能测试

3台捕获机与中央管理机均为PC机，操作系统为RedHat 7.3，处理器为P4 2．0GHz，内存为256MBDDR，硬盘为40GB，千兆以太网卡；使用用IXIA网络测试仪发送ip段为192.168.10.1～192.168.10.10的网络数据，数据丢包率低于0.01%。

6 结束语

这种软件负载均衡技术是实现高速网络环境下网络处理的有效途径之一。该方式具有高可用性，高扩展性，使得网络处理系统能更好地适应网络带宽不断增加的趋势。因而进一步研究有很强的应用前景。该技术可以实现基于网络层的数据转发和负载均衡调度。在此基础上进行改进可以实现千兆带宽的网络入侵检测、千兆带宽的网络取证等网络处理。

参考文献：

[1] 陈宇，薛鹏，翟伟斌，刘宝旭，许榕生．基于IXP2400开发NIDS负载均衡器的研究[J]．计算机工程，2007,33(1):104-105,127.

[2] 郑爱蓉，施恩，杨彬，陈宇，许榕生．基于IXP2400千兆防火墙包分类算法的设计与实现[J]．计算机应用研究，2005,22(9):237-239.

[3] 杨武，方滨兴，云晓春，等．基于骨干网的并行集群入侵检测系统[J]．哈尔滨工业大学学报，2004,36(3):274-275.

[4] 负载均衡技术：http://publish.it168.com/cword/2876.shtml.