井下声波数据压缩系统中FIFO深度的研究

在测井数据高速增长的背景下，实时硬件无损压缩系统得到了广泛应用。不少系统中均使用了Hash查找来提高压缩系统的工作效率。但是，由于Hash冲突的无法避免，Hash查找的查找时间往往是随机的，这就使得下一个待压缩数据进入压缩系统的时间也是随机的。因此，压缩系统数据输入前端的工作频率和压缩模块的工作频率就难以保持同步。为了解决系统模块间异步时钟域同步问题，异步FIFO（FirstInFirstOut）得到了广泛的应用。在异步FIFO设计中的一个关键问题就是FIFO深度的选取，选取合适的FIFO深度不仅可以提高系统性能,而且还可以优化系统的面积和功耗叫目前,针对FIFO深度问题的研究也有很多。比如，在读写频率确定的情况下的FIFO深度经验公式；读写频率成比例时，通过等时长间隔测井FIFO中已有数据量来确定FIFO深度；建立FIFO模型，但是在FIFO内无排队现象的前提下等。多数研究并没有给出FIFO应用的具体环境，没有考虑FIFO深度对具体某一数字系统的影响。针对实际井下声波数据压缩系统（数据输入速率即数据采样频率一定），本文首先研究了Hash桶深的概率分布统计特征，以此得到FIFO输出端数据的概率分布统计特性。在此基础上，利用随机服务系统理论对异步FIFO建模，从理论上得到了FIFO深度，对异步FIFO和整个数据实时压缩系统的设计具有重要的指导意义。

1Hash映射的概率分布特性及FIFO建模

1.1Hash映射的概率分布特性

在基于字典的无损压缩算法（如LZW算法）中，经常会使用Hash函数来提高数据查找效率，从而提高压缩系统的压缩速率。Hash函数本质上是在数据和它的存储地址之间建立一个确定的映射，因而在查找时只需要根据这个映射关系便可以找到此数据的存储位置。然而，对不同的数据经过哈希映射后却可能得到同一个哈希地址即存储地址，这种现象称为哈希冲突。在一般情况下，冲突只能尽可能地减少，而不能完全避免。不少测井数据压缩系统均采用散列性能好，且利于硬件实现的移位异或Hash函数叫可以证明[8]:当Hash映射散列性能好，近似服从均匀分布的情况下，每个Hash桶中的数据量服从Poisson分布，即每个数据到达某个Hash桶的时间间隔服从指数分布。

1.2压缩系统等效和FIFO建模

随机服务系统理论也称排队论，是通过对服务对象来到和服务时间的统计研究，研究性态问题、最优化问题、排队系统的统计推断问题，进而对整个系统进行建模和优化的一门科学図。典型的排队系统如图1所示。

按照此排队系统典型结构，可以把数据压缩系统的输入前端即异步FIFO等效为图1中的“顾客排队”，把数据压缩模块等效为图1中的“服务机构”，就可以建立FIFO的随机服务系统模型。

由于压缩系统的压缩速率的不确定主要是由Hash冲突引起的，且数据到达某个Hash桶的时间间隔是服从指数分布的，因此整个压缩模块完成数据的压缩时间间隔也近似服从指数分布，也就是异步FIFO的读时钟周期服从指数分布。所以,异步FIFO可以用M/M/1/m的排队混合制系统进行建模(M表示指数分布，m表示异步FIFO容量)。在X/Y/Z/A排队系统中，X为顾客到达时间间隔概率分布，Y为服务时间概率分布，Z为服务台数量，A为服务台容量。

2FIFO深度的确定

正是利用这一原理，文献[6]推导出了计算FIFO深度的公式：

式中，t=n，表示单位时间内数据能够到达FIFO的概率。由于本文所设计的压缩系统是实时压缩系统，因此式(1)所求的FIFO深度应该是当q趋近于1时的深度，"是根据常见的压缩系统的压缩速率所取的值。显然，当P>1时，FIFO内是不存在排队问题的。图2所示是在Matlab中计算出的FIFO的深度情况。

由图2可知，当数据源不暂停向压缩系统发送数据时，由于哈希冲突问题将会造成FIFO中可能产生排队现象。根据图2，异步FIFO的容量应设置为4×8b。尽管这样的逼近一定会存在不少误差，但这样大致给出了FIFO深度的范围，最大的好处是改变了以往靠设计者经验设置FIFO深度的问题，而且能有效节省存储器的硬件资源，为后面的硬件系统设计建立一个理论基础，从而提供理论指导。

3结语

本文利用排队论模型对FIFO深度进行建模，并且把FIFO深度和实际的数字系统联系起来分析，这在以往是少见的。FIFO深度的确定可以有效避免依靠设计者经验确定FIFO深度时带来的资源浪费或者容量不够问题，为硬件数据压缩系统提供了理论指导，并且有很好的应用前景。

20211020_617022c63c136__井下声波数据压缩系统中FIF