CN1831791B - 一种快速地址变换的软件实现方法 - Google Patents

Abstract

本发明公开了一种利用软件实现的快速地址变换的方法，该方法包括以下步骤：初始化方法中的参数；缓冲区数据初始化；数据地址变换方式选择，数据运算；新数据输入；判断并结束处理。本发明主要通过将以列数据分成两个线性部分的方法，同时特殊情况下，使用快速地址映射方法，从减少处理器进行判断的计算，达到降低处理器开销的目的，同时也可以减少处理器的所消耗的能量，延长处理器的工作时间。

Description

一种快速地址变换的软件实现方法

技术领域

本发明涉及计算机寻址技术，尤其涉及一种利用软件实现快速地址变换的方法。

背景技术

计算机技术已经应用到各个领域，在各个不同的领域中由于不同的应用方法和各种限制，对计算机寻址技术有着不同的要求。例如，在数字信号处理中，对数字信号进行滤波、卷积、傅里叶变换等等操作。进行这些操作需要对历史数据进行保存，以用于后续运算，并且对数据有时间上对齐的要求。

尤其是数字滤波是语音和图像处理、模式识别、谱分析等应用中的一个基本算法。

以一个卷积运算为例。

$y\left(n\right)=\underset{k=0}{\overset{N}{\mathrm{\Σ}}}x(n-k)\·h\left(k\right)$

为了运算y(n)必须将以前的N个数据保存进行运算。为了使数据可以在计算机上进行运算，需要对所保存的数据地址不断进行修改。图1将在n＝i和n＝i+1时，h(k)和x(n)对应关系显示出来。

为了达到上述目的，最直接的修改方法就是直接将整体数据进行对应于一个时间单位的地址搬移。这个方法比较适应数据长度比较短的情况；如果数据长度比较长的情况下就会花费很多额外的开销。

上述卷积运算为例，如图1所示。当n＝i运算完毕后，需要进行n＝i+1的时候，整个数据进行地址搬移就是和图中表达出来的一样，将n＝i时，对应h(k)行的N位置上的数据丢弃，依次将各个数据向右搬移，给对应h(k)行的0位置腾空，然后将新的数据样本i+1放置在对应h(k)行的0位置上。这样，每次运算完毕都要进行大量的数据地址搬移的运算。

为了减少计算量，一种循环寻址的思想被广泛运用。要求在存储器中开辟一个缓冲区作为滑动窗，用以保存最新一批数据参与运算。如果有新的数据到来，它将覆盖最早的数据。具体实现就是将物理上连续的一段线性的存储空间看成逻辑上是环形的。这样在数据寻址到物理存储空间的结束地址的时候，自动返回指向物理存储空间的起始地址，形成逻辑上的环形的存储空间。

图2中，图2-(a)所示为n＝i时，h(k)和x(n)之间的对应关系。不失一般性，x(i)的起点位置并不在物理缓冲区的开始位置。图2-(b)所示为n＝i+1时，h(k)和x(n)之间的对应关系。可以看到此时数据x(i-N)已经不需要了，所以按照循环寻址的思路就是将新输入的样本数据放到当前时刻不需要的历史数据x(i-N)所处的和h(2)对应得位置上，这样就能够模拟逻辑上的环形缓冲区。

现在有些专用的设备和器件通过硬件提供了低开销的循环寻址功能。但是，很多通用的处理器并没有提供这个功能，需要通过软件技术来实现。

上述第一种方法，在历史数据长度比较短的情况下，直接进行数据搬移的计算量不大，但是如果历史数据比较长的情况下，需要进行的数据搬移就要很大的计算量.

上述第二种方法，由于新数据存储在不再使用的历史数据的存储单元，使得每次参加运算的一系列历史数据的起始位置都是不同的，所以无法预知什么时候进行地址映射。在进行计算之前首先要判断该数据的地址是否是缓冲区的结束地址，如果是缓冲区德结束地址，下一个地址就要使用映射方式了。每个参加运算的地址都要进行判断，开销非常大。

当今，计算机技术飞速发展，功能强大电子产品进入人们的生活之中，比如手机，数码摄像机等等。这些产品方便生活，同时由于这些产品都是使用电池供电，这就对处理器的能耗提出了更高的要求。上述两个方法中都有繁琐的计算，这就使得产品工作时间缩短，使用不方便。

发明内容

有鉴于此，为了减少处理器的开销，快速进行地址变换，本发明提出一种利用软件实现快速地址变换的方法。

一种利用软件实现快速地址变换的方法，其特征在于：包括一下步骤：

A初始化方法中的参数；

B缓冲区数据初始化；

C数据地址变换方式选择，数据运算；

D新数据输入；

E判断并结束处理。

进一步，所述方法步骤A中需要初始化的参数包括：缓冲区长度、缓冲区起始单元、缓冲区结尾单元。

进一步，所述方法步骤B中，将需要进行处理的数据依次存入缓冲区中。当数据依次存满整个缓冲区时或者需要进行运算的数据全部存储完时进行数据运算。

进一步，所述方法步骤C中数据运算，当所需历史数据长度比较长时，根据当前指针的位置，将整个缓冲区中的数据分为两个线性的部分。将两个部分分别进行运算然后再汇总得到最终的结果。数据运算完毕后，需要进行循环地址的判决，以决定指针是否已经到达缓冲区的结尾。如果指针到达了缓冲区的结尾，将指针映射到缓冲区的开始位置。在进行循环地址映射时，当指针到达缓冲区结尾时，某些情况下，可以使用快速的映射方法，即直接将指针映射到缓冲区的开始位置。

进一步，所述方法步骤C中数据运算，当所需历史数据长度比较短时，直接进行数据搬移。

进一步，所述方法步骤D中，新输入的数据样本，根据已经完成的数据运算情况，存放在不再使用的历史数据的位置上。

进一步，所述缓冲区的存储空间采用物理上连续的地址单元，也可以为逻辑上连续的地址单元；所述被处理数据可以为一个存储单元，也可以为几个存储单元组合起来的数据块。

通过本发明，大大减少了运算过程中的地址比较判决计算，降低了处理器的计算开销，可以节省处理时间，降低了处理器能量消耗，强力支持了现在使用电池的电子产品的长时间工作.

附图说明

图1在n＝i和n＝i+1时h(k)和x(n)对应关系示意图；

图2循环寻址方式在n＝i和n＝i+1时h(k)和x(n)对应关系示意图；

图3物理不连续的缓冲区示意图；

图4几个存储单元组合起来的物理连续数据块示意图；

图5几个存储单元组合起来的物理不连续数据块示意图。

具体实施方式

以一个卷积运算为例。

$y\left(n\right)=\underset{k=0}{\overset{N}{\mathrm{\Σ}}}x(n-k)\·h\left(k\right)$

首先初始化长度寄存器(BK)、有效基地址(EFB)、尾地址(EOB)。然后，按照缓冲区的安排顺序将数据依次填充。

根据长度寄存器(BK)的大小，来决定采用数据搬移进行寻址，还是采用本发明提到的循环寻址。如果采用数据搬移，如图1所示，在n＝i运算完毕后，将要进行n＝i+1的计算，由于在和h(N)对应的数据已经成为没有用的历史数据，将和h(N-1)对应的数据搬移到和h(N)对应的存储单元。这样依次搬移数据后，将和h(0)对应的存储单元空闲出来，新的样本数据i+1就可以存入到这个存储单元中。然后再进行运算，直到运算结束。

如果采用本发明提到的循环寻址，如图2所示，不失一般性，x(n)的起点不在物理缓冲区的开始地址，在h(3)对应的存储单元。这样依照本发明的分解思想。整个数据串被分为两个部分，h(0)～h(3)和h(4)～h(N)，在这两个部分由于中间没有被打断，所以在计算过程中不用进行地址的判断，直接运算。

本次运算结束后，起点地址需要后移，这时才进行一次地址比较来决定起点地址是否已经到达缓冲区的边界(图2所示方式为缓冲区的开始边界)，依照图2-(a)所示，下一个起点地址为h(2)对应的地址。如果本次运算为缓冲区的边界，比如h(0)对应地址，就使用循环地址映射将运算起点地址映射到h(N)。

如此不断进行运算，直到整个数据计算完毕。

上述实施例中，在进行循环地址映射时，如果缓冲区的长度为2的整数次幂，比如2的4次幂，缓冲区长度为16，即N＝15，可以采用快速地址映射，直接将地址加1，取地址加1后的后四位就回到缓冲区的另外一个边界了。分配给和h(0)，h(1)，......，h(15)对应的缓冲区地址的二进制表示为1111，1110，......，0000。当本次运算的起始地址为1111时，下一个起点地址就应该是0000了。给1111加1成为10000，取后四位就是0000了，不用进行另外的计算就可以直接快速映射到正确的地址了。

上述实施例为缓冲区为一个物理上连续的存储单元。也可以是物理上不连续的存储单元。如图3所示，在这种情况下，地址递增不是简单的加1操作，而是地址指针向下一个地址。其余计算同上一具体实施例。

上述实施例为要处理的数据为单个的存储单元.处理数据也可以为几个存储单元组合起来的数据块，如图4所示，数据块可以是物理上连续存储单元，图中A，B，C分别代表组成数据块的数据，此处只表示数据块的包含A，B，C三个结构相同的数据部分，并不代表相同的具体数据；如图5所示，数据块也可以是物理上不连续的存储单元.第一种情况下，地址递增也不是加1，而是加一个固定的常数；第二种情况下，是地址指针指向下一个地址.处理过程同上述实施例.

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，因此本发明保护范围以权利要求书的保护范围为准。

Claims (9)

1.一种应用于计算机寻址中，利用软件实现快速地址变换的方法，其特征在于：包括以下步骤：

A初始化方法中的参数；

B缓冲区数据初始化；

C数据地址变换方式选择，数据运算，当所需历史数据长度比较长时，根据当前指针的位置，将整个缓冲区中的数据分为两个线性的部分，将两个部分分别进行运算然后再汇总得到最终的结果；

D新数据输入；

E判断并结束处理。

2.根据权利要求1所述方法，其特征在于：所述方法步骤A中需要初始化的参数包括：缓冲区长度、缓冲区起始单元、缓冲区结尾单元。

3.根据权利要求1所述方法，其特征在于：所述方法步骤B中，将需要进行处理的数据依次存入缓冲区中，当数据依次存满整个缓冲区时或者需要进行运算的数据全部存储完时进行数据运算。

4.根据权利要求1所述方法，其特征在于：所述方法步骤C中数据运算完毕后，需要进行循环地址的判决，以决定指针是否已经到达缓冲区的结尾，如果指针到达了缓冲区的结尾，将指针映射到缓冲区的开始位置。

5.根据权利要求4所述方法，其特征在于：所述方法步骤C中，当指针到达缓冲区结尾时，使用快速的映射方法，即直接将指针映射到缓冲区的开始位置。

6.根据权利要求1所述方法，其特征在于：所述方法步骤C中数据运算，当所需历史数据长度比较短时，直接进行数据搬移。

7.根据权利要求1所述方法，其特征在于：所述方法步骤D中，新输入的数据样本，根据已经完成的数据运算情况，存放在不再使用的历史数据的位置上。

8.根据权利要求1所述方法，其特征在于：所述缓冲区的存储空间采用物理上连续的地址单元或逻辑上连续的地址单元。

9.根据权利要求1所述方法，其特征在于：所述被处理数据为一个存储单元或几个存储单元组合起来的数据块。

Images