存储器压缩

摘要

本发明的示范实施例包括用于压缩数据以在存储器中进行存储的方法。根据一个实施例，所述方法基于查寻表值的单调有序序列来形成值的集合。针对所述集合中的一对或更多对配对值，该示范方法生成配对中的值的差。在以基于所述差的值替换配对中的值中的一个来修改所述集合之后，该示范方法把基于所述修改集合的最终值存储在存储器中。本发明还包括用于存储查寻表值的存储器。一个示范存储器包括译码器、编码器以及一个或更多个由交叉互连线构成的图案，所述交叉互连线将译码器和编码器互连。可以在一个或更多个与隔离材料垂直交织的由导体轨道制成的平坦层上实现所述由交叉互连线构成的图案。

权利要求

1.一种用于压缩数据以在存储器中进行存储的方法，该方法包括以下步骤：形成步骤，其通过按单调顺序对查寻表值重新排序来形成查寻表值的有序集合；

配对步骤，其将所述有序集合中的相邻值配对，以形成多个非交叠配对值；

生成步骤，其针对一对或更多对配对值，生成所述配对值中的值之间的差；

替换步骤，其通过以对应的差来替换所述配对值中的一个值，来缩减存储查询表值所需的位数，以生成压缩有序集合；以及存储步骤，其将所述压缩有序集合存储在所述存储器中，

其中，所述生成步骤包括生成所述配对值中的值之差和所述配对值中的值之和的步骤，所述替换步骤包括以基于所述差的值来替换所述配对值中的值中的一个和以基于所述和的值来替换所述配对值中的值中的另一个的步骤。

2.根据权利要求1所述的方法，其中，修改所述集合的步骤还包括保持所述配对值中的值中的另一个的步骤。

3.根据权利要求2所述的方法，该方法还包括迭代重复步骤，所述迭代重复步骤在所述存储步骤之前迭代重复所述生成步骤和所述替换步骤。

4.根据权利要求3所述的方法，其中，所述配对中的一个或更多个针对不同的迭代而不同。

5.根据权利要求1所述的方法，其中，所述压缩有序集合包括所述查寻表值中的至少一个。

6.根据权利要求1所述的方法，该方法还包括丢弃步骤，所述丢弃步骤丢弃所述和的最低有效部分。

7.根据权利要求1所述的方法，该方法还包括迭代重复步骤，所述迭代重复步骤在所述存储步骤之前迭代重复所述生成步骤和所述替换步骤。

8.根据权利要求7所述的方法，其中，对值的配对针对不同的迭代而不同。

9.根据权利要求1所述的方法，其中，该方法还包括串接值生成步骤，该串接值生成步骤通过串接来自最终迭代的与所述最终迭代中的配对值相对应的每个所述和及所述差来生成串接值，并且将所述串接值存储为最终值的步骤。

10.根据权利要求1所述的方法，该方法还包括迭代重复步骤和串接值生成步骤，所述迭代重复步骤迭代重复所述生成步骤和所述替换步骤，直到所述和中的一个包括所述序列中的全部查寻表值的总和为止，所述串接值生成步骤通过串接来自对应迭代的所述和及所述差来生成串接值，并且将所述串接值存储为最终值的步骤。

11.根据权利要求1所述的方法，该方法还包括确定步骤，所述确定步骤基于针对一对或更多对配对值生成的和及差的组合来确定一个或更多个组合值，其中，以基于所述差的值来替换所述配对值中的值中的一个的步骤包括以所述组合值的最低有效部分来替换所述配对值中的值中的一个的步骤。

12.根据权利要求1所述的方法，该方法还包括重建步骤，所述重建步骤根据预定重建公式，基于存储在存储器中的所述压缩有序集合中的所述一个或更多个值，来重建一个或更多个查寻表值。

13.根据权利要求1所述的方法，其中，所述查寻表值包括根据单调函数导出的值。

14.根据权利要求13所述的方法，该方法还包括应用步骤，所述应用步骤应用所述形成步骤、所述生成步骤、所述替换步骤以及所述存储步骤中的每一个，来分割分段单调函数中的单调段。

15.根据权利要求1所述的方法，其中，所述查寻表值包括按单调顺序排列的非单调值。

16.根据权利要求15所述的方法，该方法还包括设置步骤和存取步骤，所述设置步骤把所述压缩有序集合中的值设置在所述存储器的第一层上，而所述存取步骤经由设置在所述存储器的第二层上的一条或更多条交叉地址线来存取所述压缩有序集合中的值中的一个或更多个。

17.一种用于压缩数据以在存储器中进行存储的方法，该方法包括以下步骤：形成步骤，其通过按单调顺序重新排列查寻表值，来形成查寻表值的有序集合：配对步骤，其将所述有序集合中的相邻值配对，以形成多个非交叠配对值；

生成步骤，其针对一对或更多对配对值，生成所述配对中的值的差和所述配对值中的值的和；

替换步骤，其通过以对应的和及差替换所述配对值中的值来缩减存储查询表值所需的位数以生成压缩有序集合，而缩减存储所述有序集合所需的位数；以及存储步骤，其将所述压缩有序集合存储在所述存储器中。

18.根据权利要求17所述的方法，其中，该方法还包括串接值生成步骤，该串接值生成步骤通过串接针对各配对值的各所述和与所述差来生成串接值并将所述串接值存储为最终值的步骤。

19.根据权利要求17所述的方法，该方法还包括迭代重复步骤，所述迭代重复步骤在所述存储步骤之前迭代重复所述生成步骤和所述替换步骤。

20.根据权利要求19所述的方法，其中，该方法还包括串接值生成步骤，该串接值生成步骤通过串接来自最终迭代的与所述最终迭代的配对相对应的所述和与所述差，来生成串接值，并且将所述串接值存储为最终值的步骤。

21.根据权利要求17所述的方法，该方法还包括舍入步骤，所述舍入步骤把每个和舍入至最近的单位，以形成一个或更多个修改和，其中，所述替换步骤包括以对应的差和所述修改和替换所述配对值中的值的步骤。

22.根据权利要求21所述的方法，该方法还包括迭代重复步骤，所述迭代重复步骤在所述存储步骤之前迭代重复所述生成步骤、所述舍入步骤以及所述替换步骤，该方法还包括串接值生成步骤，所述串接值生成步骤通过串接来自最终迭代的与所述最终迭代的配对相对应的所述和与所述差，来生成串接值，并且将所述串接值存储为最终值的步骤。

23.根据权利要求17所述的方法，该方法还包括组合值生成步骤，所述组合值生成步骤通过组合所述差值与所述和值来生成针对一对或更多对所述配对值的组合值，其中，所述替换步骤包括以基于所述和值和所述组合值的最低有效部分的值替换所述配对值中的值的步骤。

24.根据权利要求17所述的方法，其中，所述查寻表值包括根据单调函数导出的值。

25.根据权利要求24所述的方法，该方法还包括应用步骤，所述应用步骤应用所述形成步骤、所述生成步骤以及所述替换步骤，来分割分段单调函数中的单调段。

26.根据权利要求17所述的方法，其中，所述查寻表值包括按单调顺序排列的非单调值。

27.根据权利要求26所述的方法，该方法还包括设置步骤和存取步骤，所述设置步骤把所述压缩有序集合中的值设置在所述存储器的第一层上，而所述存取步骤经由设置在所述存储器的第二层上的一条或更多条交叉地址线来存取所述压缩有序集合中的值中的一个或更多个。

28.根据权利要求17所述的方法，该方法还包括丢弃步骤，所述丢弃步骤在所述替换步骤之前丢弃所述和的最低有效部分。

29.一种用于压缩数据以在存储器中进行存储的方法，该方法包括以下步骤：形成步骤，其通过按单调顺序重新排列查寻表值来形成查寻表值的有序集合，所述有序集合包括非交叠配对值(f0，f1)和(f2，f3)；

d0和d2生成步骤，其通过确定f0与f1之差来生成d0，并且通过确定f2与f3之差采生成d2；

s0和s2生成步骤，其通过确定f0和f1的和来生成s0，并且通过确定f2和f3的和来生成s2；

替换步骤，其通过以d0替换f1，以d2替换f3，以s0替换f0、以s2替换f2来缩减存储查寻表值所需的位数，以生成压缩有序集合；以及存储步骤，其基于所述修改集合把所述压缩有序集合存储在所述存储器中。

30.根据权利要求29所述的方法，该方法还包括在所述存储步骤之前的以下步骤：对所述压缩有序集合中的值进行配对以生成配对值(f0，f2)和(d0，d2)；

通过确定f0与f2之差生成d1，并且通过确定d0与d2之差生成d3；以及以d1替换f2并以d3替换d2。

31.根据权利要求29所述的方法，该方法还包括以下步骤：通过串接s0和d0来生成第一串接值；

通过串接s2和d2来生成第二串接值；以及

把所述串接值存储为最终值。

32.根据权利要求29所述的方法，该方法还包括通过组合s0和d0生成c0并通过组合s2和d2生成c2的步骤，其中，所述替换步骤还包括以s0替换f0、以s2替换f2、以c0的最低有效部分替换d0以及以c2的最低有效部分替换d2的步骤。

33.根据权利要求29所述的方法，该方法还包括以下步骤：对修改集合中的值进行配对以生成配对值(s0，s2)和(d0，d2)；

通过确定s0与s2的和生成s1，并且通过确定d0与d2的和生成s3；

通过确定s0与s2之差生成d1，并且通过确定d0与d2之差生成d3；并且其中，所述替换步骤还包括以s1替换s0、以d1替换s2、以s3替换d0以及以d3替换d2的步骤。

34.根据权利要求33所述的方法，该方法还包括：

通过串接s1、d1、s3以及d3来生成串接值的步骤；和把所述串接值存储为最终值。

35.一种用于压缩数据以在存储器中进行存储的设备，该设备包括以下装置：形成装置，其通过按单调顺序对查寻表值重新排序来形成查寻表值的有序集合；

配对装置，其将所述有序集合中的相邻值配对，以形成多个非交叠配对值；

生成装置，其针对一对或更多对配对值，生成所述配对值中的值之间的差；

替换装置，其通过以对应的差来替换所述配对值中的一个值，来缩减存储查询表值所需的位数，以生成压缩有序集合；以及存储装置，其将所述压缩有序集合存储在所述存储器中，

其中，所述生成装置包括用于生成所述配对值中的值之差和所述配对值中的值之和的装置，所述替换装置包括用于以基于所述差的值来替换所述配对值中的值中的一个和以基于所述和的值来替换所述配对值中的值中的另一个的装置。

36.一种用于压缩数据以在存储器中进行存储的设备，该设备包括以下装置：形成装置，其通过按单调顺序重新排列查寻表值，来形成查寻表值的有序集合：配对装置，其将所述有序集合中的相邻值配对，以形成多个非交叠配对值；

生成装置，其针对一对或更多对配对值，生成所述配对中的值的差和所述配对值中的值的和；

替换装置，其通过以对应的和及差替换所述配对值中的值来缩减存储查询表值所需的位数以生成压缩有序集合，而缩减存储所述有序集合所需的位数；以及存储装置，其将所述压缩有序集合存储在所述存储器中。

37.一种用于压缩数据以在存储器中进行存储的设备，该设备包括以下装置：形成装置，其通过按单调顺序重新排列查寻表值来形成查寻表值的有序集合，所述有序集合包括非交叠配对值(f0，f1)和(f2，f3)；

d0和d2生成装置，其通过确定f0与f1之差来生成d0，并且通过确定f2与f3之差采生成d2；

s0和s2生成装置，其通过确定f0和f1的和来生成s0，并且通过确定f2和f3的和来生成s2；

替换装置，其通过以d0替换f1，以d2替换f3，以s0替换f0、以s2替换f2来缩减存储查寻表值所需的位数，以生成压缩有序集合；以及存储装置，其基于所述修改集合把所述压缩有序集合存储在所述存储器中。

说明书

存储器压缩

技术领域

[0001] 本发明基于具体实现的具有针对诸如查寻表或程序的固定数据的存储器需求的微处理器，使得能够实现尺寸缩小和成本缩减的低成本电子装置。

背景技术

[0002] 电子装置通常用于微处理器，以执行从非常简单到非常复杂排列的各种任务。当一装置(诸如电子通信装置、远程控制装置、其它移动装置等)被设计用于特定功能或功能时，与这些功能相对应的程序一旦开发完成，就通常存储在只读存储器(ROM)中。在ROM中也可以存储诸如用于需要计算如指数或对数函数，或者三角函数的一些函数的值的查寻表的其它固定数据。

[0003] 低成本且结构紧凑的ROM是掩模型可编程ROM。在掩模型可编程ROM中，地址被编码成在与地址相对应的许多信号线中的一条上提供逻辑电平。地址线与位线交叉，而位线与设计的输出字相对应，并且在每条地址线和位线的交叉处设置有一个晶体管，其中，二进制“1”是针对该地址设计的位输出。事实上，这种ROM等同于巨大的针对每个输出位的OR选通，在该选通中，如果地址A1.OR.A2.OR.A3.…有效，则确定其为“1”，否则，确定其为“0”。

[0004] 为表示存储的“1”而使用的晶体管向每个多输入OR选通提供输入。图1示出了这种ROM，其中，针对1024个地址中的每个存储了长度32位的字。如果希望更大的存储器，可以重复图1中的图案来形成每行1024个字的连续多行，并且可以提供行选择线，使得能够从选择线输出，该输出与激活的特定列地址线一起选择特定的字。

[0005] 利用恰当设计的位图案、在制造过程期间使用的定制设计的扩散和/ 或接触和/或金属化掩模来设置晶体管。因为掩模制造技术是昂贵的，所以其仅在ROM的内容被期望固定用于高容量的生产单位中时使用。因为这样的便利性，即，可以在希望的内容已知并以后填充之前制造存储器，也可以在使用中修改该存储器的内容，所以更通常优先于掩模型ROM来选择诸如电或UV可擦可再编程只读存储器(EAROM、EEROM、RPROM、“闪速”存储器等)和其它更多近来的诸如铁电体存储器的非易失性存储器开发的其它形式的存储器。要说的是，掩模型可编程ROM的硅面积和随之的成本优点迄今没有充分超过现场编程的便利性。 [0006] 在保持某些灵活性的同时可以获取掩模型ROM的优点的一些解决方案包括存储程序的成熟部分(即，子程序)，或者在掩模型ROM中显示用于数学函数的固定表或字符集，从而在可再编程存储器中通过一较小的程序来链接并调用它们。这样，如果需要替换掩模型ROM例程，则仅需要在可再编程ROM中设置该替换的例程并饶过该掩模型ROM版本，即，一种已知为“修补”的处理。然而，掩模型ROM的面积优势仍不足于促进这种技术的宽泛使用。因而，与到目前为止的掩模型ROM相比，需要意义重大的更紧凑且更经济的固定内容存储器。

发明内容

[0007] 本发明的示范实施例包括用于在存储器中压缩用于存储的数据的方法。根据一个实施例，所述方法包括基于查寻表值中的一单调有序序列来形成一组值。针对所述组中的一对或更多对配对的值，示范方法生成所述配对中的值的差。在利用基于所述差的一值来替换所述配对中的所述值中的一个来修改所述组之后，示范方法把基于所述修改的组的最终值存储在存储器中。

[0008] 根据一个实施例，在所述修改配对中的剩余值保持不变。在第一次迭代之后，基于所述修改组的最终值被存储在存储器中。另选地，可以执行附加迭代以进一步压缩数据存储。例如，在第二次迭代中，示范方法形成未修改值之间的配对，并且形成修改值之间的配对，接着生成在新的配对中的所述值的新的差。随后，示范方法利用基于所述差的一值 替换所述配对中的所述值中的一个来修改当前组。重复该过程直到已经完成预定次数的迭代为止。在完成最终迭代之后，把通过最终迭代生成的基于值的所述修改组的最终值存储在存储器中。

[0009] 根据另一实施例，利用基于在所述配对中的所述值的和生成的值来替换在所述修改对中的剩余值。在该第一次迭代之后，连接各配对的和与差来生成最终值。另选地，可以执行附加迭代以进一步压缩数据存储。例如，在第二次迭代中，示范方法形成所述和值之间的配对，并且形成所述差值之间的配对，接着生成在每个新的配对中的所述值的新的和差。重复该过程直到已经完成预定次数的迭代为止。在完成最终迭代之后，连接与最终迭代的配对相对应的和与差来生成最终值。

[0010] 在一个实施例中，通过利用发明的算法，把用于存储字长L1数量2N1 的ROM从总大N1 N2 N2小L1×2 位压缩成存储L2位2 字、总计L2×2 位的ROM，其中，L2＞L1和N2＜N1。 [0011] 一种应用是为规则函数F(x)提供查寻表，其中，通过与x相对应的二进制位图案寻址该查寻表，并输出预存储在那个位置处的值F。在这种情况下，第一次压缩根据前述地址利用它们的三角(delta)值来替换函数的更替值。另选地，每对相邻值可以用它们的废除了最低有效位(LSB)的和与它们的差来替换。当函数是规则函数时，连续值之间的差远小于函数值本身，由此可以存储很少的位。

[0012] 第二次算法可以包括重复该压缩过程，其被理解为根据第一级输入偶数地址值的阵列，接着分开输入偶数地址三角值阵列，由此获得函数值，两个第一次差和一个第二次差替换四个函数值。第二次差通常也小于第一次差，由此，可以利用比第一次差更少的位来存储，完成进一步压缩。公开了系统的过程，用于基于修改的其中废除了和项的LSB的蝶式运算，利用快速沃尔什变换来构建更高次的压缩算法。当读取ROM的时候，利用逆变换重建值。

[0013] 第二执行通过存储共同或接近共同最高有效位(MSB)图案和不同LSB图案来存储数字上相邻的值的字块(block)，由此，缩减存储的每值平均位数。如果在一字块中的共同最高有效位图案允许不同多达+l或-1， 则可以允许更适宜的字块大小，即，规整的字块大小。。接着，与最低有效部分相关联的附加位确定该共同最高有效部分是否必须针对一具体检索值递增或递减。第二执行与第一执行相比允许更简单的重建。

[0014] 本发明还包括用于存储多个查寻表值的存储器，其中，各查寻表值与包括多个地址符号的地址相关联。一个示范存储器包括解码器、编码器，以及一个或更多个由交叉连接线构成的图案。解码器通过解码所述多个地址符号中的一个或更多个生成针对解码器输出中的一个的使能信号，而编码器基于该使能信号生成输出字。由交叉互连线构成的图案把每个解码器输出连接至编码器输入。为了缩减存储器的大小，本发明的一些方面为了利用存储器的垂直维度，利用一个或更多个与隔离材料垂直地交织的由导体轨道制成的平面层来形成由交叉互连线构成的图案。

[0015] 针对这种存储器的一个示范使用是，允许压缩存储器大小用于存储不规则函数的值，甚或存储诸如计算机程序指令的随机值。在这种情况下，发明的算法按存储的数字次序运算函数或数据值，其可以按固定图案置换芯片上的地址线来完成。接着，针对规则函数描述的压缩过程可用于利用与存储在任何位置的最靠近的绝对值数据值有关的它们的三角值来替换确定的绝对值数据值，与存储绝对值数据值相比存储该三角值使用了较少的位。如果两个或更多个相邻值相同，那么可以压缩成一个，并且利用OR选通输入合并相对应地址线。每个OR选通输入需要一个晶体管，由此，等效于按照硅面积占用的存储器位。 [0016] 寻址的已经利用M次算法压缩过的值的重建包括只要激活M条相邻地址线中的一条就读取长度L2位的字。接着，根据其中激活的地址线合并其包括基值、第一次和更高次差的组成部分。可以利用M-线到log2(M)线优先级编码器来组合M条地址线中的每一组，以获得log2(M)位用于系统地使能重建组合逻辑。

[0017] 利用本发明，通过使用依赖于算法次序的2与5之间的因子和重建组合逻辑的量可以典型地缩减ROM硅面积。当压缩的数据是计算机程序时，当然需要按照原样，从而，总是发生精确位重建。

[0018] 在示范存储器执行的第二方面，通过置换地址线把数据分类到数字 次序中，来完成ROM随机内容的压缩。因为在置换图案内有效地存储信息，所以与信息位相比，在ROM中利用较少实际位元存储相同位数的信息是可以的。因为可以在芯片上容纳通过绝缘层隔开的非常多的互连图案层，所以可以制造地址线的大量的不同置换图案，每个置换图案都包含信息，由此，利用垂直维度来存储增量的信息。

附图说明

[0019] 图1例示了掩模型可编程只读存储器(ROM)。

[0020] 图2例示了一个示范规则函数的图。

[0021] 图3例示了一个示范压缩算法。

[0022] 图4例示了示范重建逻辑。

[0023] 图5例示了真实单调函数与指数近似法之间的比较图。

[0024] 图6A-6D例示了用于消除碟式电路的为重建存储的数据的第一层的一个示范过程。

[0025] 图7例示了常规MOS晶体管。

[0026] 图8例示了一个示范存储器电路的构造。

[0027] 图9A和9B例示了一个示范行地址解码器。

[0028] 图10例示了用于按分类顺序排列存储的数据的一个示范过程。 [0029] 图11例示了针对利用随机数据的第一次压缩的存储器的一个示范执行。 [0030] 图12A-12C例示了用于地址解码的一个示范执行。

[0031] 图13例示了一个示范优先级编码器。

[0032] 图14A到14B比较了示范编码器和解码器组合。

具体实施方式

[0033] 首先，对本发明的示范应用进行描述，其中，需要针对希望用于特定计算的规则函数(例如，单调增函数)的值的查寻表。等式(1)把示范函数表示为：

[0034] Fa(x)＝log2(1+a-x)(1)

[0035] 其中，“a”是对数的底数。该函数在美国专利申请第______________号(代理案卷号4015-5281和4015-5287)中描述的对数算术运算中提到过，该美国专利申请通过引用并入于此。

[0036] 图2中示出了底数为2的该函数的图，x的值在按512划分的0到16383之间，即，x的值在二进制小数点右边有9位，而在二进制小数点左边有5位。针对由XM表示的作为512x的补码标绘了该函数，其范围为0到32并且随着自变量XM增大而给出单调增函数值。
希望的是，针对任何根据16384个可能离散表列值给出的x值，提供对精度为23位二进制位置的函数值的快速存取。另选地，可以使用底数e，在该情况下，利用24位二进制位置实现类似的精度。

[0037] 针对后者，未压缩查寻表包括16384个24位字，总计393216位。字的值应当舍入为最近的LSB，一个具有后面要描述的重要含义的事实。然而，无论那些值怎样，都需要施加给这些查寻表值的任何压缩或解压缩算法，以按位精确方式再现希望的舍入值。 [0038] 针对x值大于17.32的情况，当x＞24时，对于底数为e的情况，函数就24位精度而言为零，而对于底数为2的情况，函数为零。这可以理解为对于x＞24，即x＞11xxx.xxxxxxxxx或XM＜00xxxxxxxxxxxx，F(x)＝0；由此仅需要XM＞00111111111＝4095的值。然而，这是针对示范函数来说特定的，由此这里不进行详述；相反将考虑提供全部16384个值。

[0039] 针对自变量XM中仅1位最低有效位差的连续值之间的差明显地远小于函数本身，因而可以用更少的位表示。对于任何光滑函数来说，这种观察都是真实的。因此，一阶压缩算法包括仅针对XM的偶数地址值存储24位值，而对于奇数地址，存储相对于前一偶数值的增量。

[0040] 针对示范函数的直接计算表明，遇到的最高增量为16376(乘以2-24)，这可以容纳在14位字内。因此，ROM可以重构为8192个24位的字和8192个14位的字。对于偶数地址XM仅需要24位值，而对于奇数地址XM需要24位和14位值来读取和相加。由此，将ROM从16384×24＝393216位压缩至8 192×(24+14)＝311296位，节省了21％，或者压缩至原大小的79％。

[0041] 二阶算法可以通过应用这样的过程来导出，即，在该过程中，利用到8192个24位值的第一阵列的一值和分开地到8192个14位三角值的第二阵列的三角值来替换配对的相邻值。第一次应用采用原始的函数生成两个分开的三角值，其粗略地加倍单间隔的三角值，由此需要15位存储，该算法针对14位第一次三角值的第二次应用生成第二次三角值，其理论上应当在0到31的范围中，需要5位。然而，由于上述函数针对最近24位字的舍入，导致第二次三角值的范围增加至最小-1到最大33，需要6位存储。这种上升是因为一个值可以向下舍入而相邻字向上舍入，所以桉1或2增加(或减小)三角值。

[0042] 现在，ROM大小已经缩减成24、15、14以及6位值中的每个都为4096位，总计4096×59=241664位，节省39％，或压缩至原大小的61％。希望的值的重建包括利用 的最高有效12位寻址4096×59位ROM，以获得长度分别位24、15、14，以及6位的四个子字；
接着，使用 的最低有效2位来控制根据所述四个子字的希望的值的重建，如下列： [0043] 分别用F、D2、D1，以及DD表示24、15、14，以及6位值，对于 LSB=00来说，该希望的值是F

[0044] 01 P+19l

[0045] 1O F+D2

[0046] 11 F+D1+D2+DD

[0047] 形成F+D1需要14位加法器；形成F+D2需要15位加法器，而形成D2+DD需要6位加法器。由此，为重建希望的值需要35位的全加法器单元。针对示范函数的情况，通过按1缩减存储的15位D2值，并且利用下面的规则可以把-l到33的DD范围移位成O到34： [0048] 对于 LSB=00来说，该希望的值是F

[0049] 01 F+D1

[0050] 10 F+D2+1

[0051] 11 F+D1+D2+DD

[0052] 由此，6位加法器根据 的LSB把1或者DD加到D2，而通常可以加一值DD0或DD1，以允许DD的从负到正的任何范围被容纳。

[0053] 图3描绘了这种通过对获取相邻值之间的差的过程进行迭代而用于 压缩的算法。希望的要存储的值最初是16384个用f0、f1、f2、…、f6…等一直到f(16384)表示的24位值。获取差的过程的第一应用保持偶数值不变，但是把每个奇数值用根据前述偶数值的差替换了。例如，用d4＝f5-f4替换了f5。对于示范光滑函数来说，要按最大14位长的值计算这些差，其是小于原始24位值的1024次。即使利用几乎为一直线的光滑函数，一种可能是，期望仅按范围的要成为16384次分之一的第16384分之一分开的两个值之间的差小于最大原始值，并由此缩短14位。一般地，针对任何光滑函数来说，约束发生这种字长的缩短。因而，在第二行中，函数值被表示为8192对值，每对值中一个是24位长，而另一个是
14位长。

[0054] 在图3中的第三行中，分开示出了用f0、f2、f4…表示的偶数值和用d0、d2、d4…表示的差值，来例示针对剩余f值和分开针对d值应用求差算法。在第4行中示出的结果是，每第2偶数值，即，原始值中的每第4偶数值此刻保持不变为24位值，而在诸如f2-f0之间的偶数值变成了15位差。每个交替的d值照样保持不变的14位值，而那些在诸如d6-d4之间的值就缩减成位6位第二次差。现在，原始16384个24位值被压缩成了4096组包括24位、15位，14位以及6位值的值。

[0055] 可以迭代该过程直到值中的多数仅大约2位长的高次差为止。这些最终的高次差因原始24位值被向上舍入或向下舍入至最近的24位二进制位置而形成相当随机的图案。存储器的总大小根据迭代地应用了多少次求差算法来缩减。

[0056] 图4示出了用于第二次差压缩算法的重建逻辑。在图的上部示出的存储16384个24位字的原始方法包括将14位地址施加至其的查寻表。图的下部描绘了第二次差压缩技术，其中，查寻表已经缩减成4096个59位值。仅利用原始14位地址的最高有效12位来寻址压缩成4096个59位值的查寻表，其有效地限定了四个一组的目标值位于其内的值。把包括24位绝对值、15位双间隔的差、14位单间隔的差以及6位第二次差的所述59位值施加至如图所示的相应的加法器。根据第二最低有效的位来使能第一列加法器，如果所述位是“1”，则相加15位差和24位值， 并且相加6位第二次差和14位差，否则，如果使能位是“0”，则传递24位值而不与15位值相加，并且传递14位值而不与6位值相加。如果原始14位地址的最低有效位是“1”，则第二列加法器相加第一列两个加法器的输出，否则其传递不变的24位值。这样，原始14位地址的两个最低有效位控制根据4个一组的值来生成所述值。

[0057] 可以通过注释D2几乎两倍于D1来进行进一步的节省，由此，仅需要存储15位D2加上一修正来应用至14位值INT(D2/2)＝右移(RightShift)(D2)，以便获得D1的精确位的值。该修正是用D1-(D2/2)表示的第二次差，其根据直接计算创立，占用范围-1到8，需要4位存储。接着，可以进一步实现该第二次差几乎等于值DD的1/4。由此，可以用根据DD/4的差替换它，其根据直接计算具有范围-1到+1，需要2位存储，并且有效为第三次差，其可以用DDD表示。

[0058] 由此，为了再现16384个位精确的24位函数值中的每个，存储的值包括4096组如下所示的四个一组的值：

[0059] 24位值：F(4i)

[0060] 15位值：D2(4i)＝F(4i+2)-F(4i)

[0061] 6位值：DD(4i)＝(F(4i+3)-F(4i+2))-(F(4i+1)-(F(4i))

[0062] 2位值：DDD(4i)＝(INT(D2((4i)/2))-(F(4i+1)-F(4i))

[0063] -INT(DD(4i)/4)

[0064] 接着，四个函数值F(4i)、F(4i+1)、F(4i+2)、F(4i+3)根据下列函数值精确位地重建：

[0065] F(4i+1)＝F(4i)+INT(D2(4i)/2)+INT(DD(4i)/4)

[0066] -DDD(4i)

[0067] F(4i+2)＝F(4i)+D2(4i)

[0068] F(4i+3)＝F(4i)+INT(D2(4i)/2)+DD(4i)

[0069] +INT(DD(4i)/4)-DDD(4i)

[0070] 代替96位地用总计47位替换了4个一组原始24位值，压缩系数稍微超过2∶1。 [0071] 反之亦然，另选地，可以仅存储14位D1加上一修正来应用至2D1， 以获得D2。由此，诸如存储下列的其它排列是可能的：

[0072] 24位值F(4i)

[0073] 14位值D1＝F(4i+1)-F(4i)

[0074] 6位值DD＝(F(4i+3)-F(4i+2))-D1

[0075] 2位值DDD＝(F(4i+2)-F(4i))-(2D1+INT(DD/4))

[0076] 其可以导致稍微更简单的重建。应当懂得，诸如INT(DD/4)的运算表示省略使用DD的两个LSB的直接逻辑函数。

[0077] 在计算所示利用不同次的算法完成了压缩的表之前，将基于修改的沃尔什变换开发更高次压缩的更系统的形式。沃尔什变换法形成配对的相邻值的和与差，并利用该和与差替换原始值。例如，在第一次迭代中，为了压缩包括f0、f1、f2，以及f3的数据，用s0＝f0+f1替换f0，用f1-f0替换f1，用s2＝f2+f3替换f2，而用d2＝f3-f2替换f3。计算一对值的和与差的电路被称为蝶式电路。

[0078] 所有的和相邻地跟随所有的差排列。已经看到的差是比和短的字。接着，重复有关和值的字块的过程，并接着分开地重复有关差值的字块的过程，和值与差值各为原始值的一半长度，以获得针对更高次算法的第二次算法等。针对16384个值的最高次算法是14次。在该点上，字块仅各具有一个值，由此，不能被进一步压缩。事实上，第14次算法是16384点沃尔什变换，而较低次算法停在全沃尔什变换的中间级处。连接与最终迭代相关联的和值与差值，以形成存储在存储器中的最终压缩值。应当懂得，最终迭代可以是任何所选的迭代，并由此，不需要是第14次迭代。

[0079] 当形成两个24位值的和时，字长可以增加一位。然而，和与差总是具有相同的最低有效位，其由此可以废除它们中的有关一位而不会丢失信息。通过根据和并且利用下面的等式(2)代替地废除它，防止和的长度增加。

[0080]

[0081] 在重建的时候，把差与和相加或者与和相减，并且通过把其LSB馈给到第一加法器/减法器级的进位/借位输入中，使用两次该LSB来代替缺失 的和LSB。算术地，修改的变换蝶式可以写成为：

[0082] SUM(i)＝INT((F(2i+1)+F(2i))/2)

[0083] DIFF(i)＝(2i+1)-F(2i)

[0084] 而重建可以写成为：

[0085] F(2i+1)＝SUM(i)+INT(DIFF(i)/2)+AND(1，DIFF(i))

[0086] F(2i)＝SUM(i)-INT(DIFF(i)/2)-AND(1，DIFF(i))

[0087] 上述等式是公知的在沃尔什-傅立叶变换中使用的蝶式运算的修改形式： [0088] SUM(i)＝F(2i+1)+F(2i)

[0089] DIFF(i)＝F(2i+1)-F(2i)

[0090] 而其逆变换为：

[0091] F(2i+1)＝(SUM(i)+DIFF(i))/2

[0092] F(2i)＝(SUM(i)-DIFF(i))/2

[0093] 可以利用上述修改的蝶式构成一个快速的、底数为2、伪沃尔什变换(伪FWT)，以将成组的两个相邻值变换成一个值和一个三角值，或者将成组的四个相邻值变换成一个值、两个三角值，一个第二次三角值，等。将其制成系统的过程，以探索更高次算法的特性并且执行更高次算法。下面给出了针对适当的伪沃尔什变换的FORTRAN代码： [0094] C F IS THE GROUP OF M VALUES TO BE PSEUDO-WALSH

[0095] TRANS FORMED

[0096] C AND N＝LOG2(M)IS THE ORDER OF THE ALGORITHM

[0097] SUBROUTINE PSWLSH(F，M，N)

[0098] INTEGER*4F(*)，SUM，DIFF

[0099] N1＝M/2

[0100] N2＝1

[0101] DO 1I＝1，N

[0102] L0＝1

[0103] DO 2J＝1，N1

[0104] L＝L0

[0105] DO 3K＝1，N2

[0106] SUM＝(F(L+N2)+F(L))/2

[0107] DIFF＝F(L+N2)-F(L)

[0108] F(L+N2)＝DIFF

[0109] F(L)＝SUM

[0110] L＝L+1

[0111] 3CONTINUE

[0112] L0＝L+N2

[0113] 2CONTINUE

[0114] N1＝N1/2

[0115] N2＝2*N2

[0116] 1CONTINUE

[0117] RETURN

[0118] END

[0119] 下表示出了利用不同次伪沃尔什算法完成示范函数的数据压缩的量 [0120]

[0121] 圆括号内的位计数是在使用利用了标准蝶式运算的沃尔什变换时获得的。标准沃尔什变换的次级压缩部分地是因和项的字长增加造成的，而部分地是因形成更高次差时原始表值中的舍入误差的扩大造成的，其在使用修改的蝶式并且废除和项的LSB时很少值得注意。针对两种情况，原始值的精确位重建是在应用恰当的逆算法时完成的。针对底数2-x的情况，计算函数Fa(x)＝log2(2 )至23个二进制位置，而针对底数e的情况，计算至24个二进制位置，其表示相似的精度。

[0122] 因而，利用最终的第14次变换运算整个阵列，查寻表缩减至单字32085(23188)位宽，其平均小于每表值2位；但每个值都可以重建成24位(23位)精度。单字不再是一个表，并且不需要地址，因为其总是被“读取”，所以这些值正好可以硬布线成重建加法器的输入。然而，需要14级重建加法器，并且需要数量大约65000个一位加法器单元。因为加法器单元大于存储器位，所以其不表示最小硅面积。最小面积是按存储的位数与针对值重建所需的加法器单元数之间的某些折衷方案获得的。尽管如此，仍然出现大约4或5的硅面积缩减系数是完全可行的。

[0123] 还可以包括的是，上述方法示出了创建一种计算光滑函数的任何离散值的机器。存储器表具有消失的局限性，其被针对加法器树的硬布线输入代替。这可以导致又一级简化，在该简化中，加零的加法器级可以简化成仅处理来自前一级的进位传送，并且同样地，可以类似地简化在加法器的输入中的一个上总是具有“1”的加法器。

[0124] 伪FWT表压缩算法还可以应用至为存储使用底数2的对数并且X2 为9位长时的-0.X2值2 /loge(2)所需的512字表。该函数接近上述示范函数，其可以在自变量范围的一部分上满足。有用的是，在整个范围上使用该近似法，来仅存储所需的修正，其具有更短的字长。

[0125] 利用底数2，当自变量从0.X2到1.X2、2.X2等改变时针对底数2的指数函数的位图案利用一个移位重复，由此仅需要合成针对由0.X2表示 的其中x2是9位值的主要范围的位图案。下表给出了要存储以合成该函数所需的总位数，舍入至二进制小数点后最近的23位，用于从O到511的自变量x2的值。

[0126]算法次数 字数 总字长 总位数
O 512 23 ll776
1 256 37 9472
2 128 57 7296
3 64 89 5696
4 32 139 4448
5 16 2l9 3504
6 8 358 2864
7 4 585 2340
8 2 974 1948
9 l 1608 l608

[0127] 仅利用具有固定的、硬布线输入的受控加法器，在不需要存储器的情况下，最终行构成了用于计算该函数的机器。

[0128] 除上述位置外，需要针对该指数函数的修正，以获得Fa(x)＝log2 (2-x)或Fs(x)-x＝-log2(1-2 )的值，其被用于对数算法中，用于对数域中的加法或减法。 [0129] 在图5中针对底数2的情况绘出了希望的值Fa与Fs以及指数函数之间的差。这些差可以存储在查寻表中，其占用空间小于原始函数，芯片面积近似地表示为曲线下方的到底部右侧的三角形面积。而且，因为该修正还形成规则函数，所以，该表也可以利用在此所述的技术压缩。

[0130] 在压缩算法的变形中，可以大量地取消重建加法器。这是基于给出的24位值和给出的14位三角值的和总是造成相同14位LSB的结果而实现的。由此，正当有效的是，存储预先计算的24位和14位值的和，即，cO=fO+dO的14位LSB来代替14位三角值，即，dO。然而，还必需存储附加位，该附加位表示14位三角值到24位值的和是否造成从第14位到第15位的进位。由此，通过存储15位代替14位，可以取消重建加法器 的第一个14位。第15位被施加至针对最高有效10位的进位传送电路。进位传送电路比全加法器更简单，而如果在应用中存在将第15位插入其中的后一级加法，则可以取消该进位传送电路。这借助于图
6进行说明。实际上，保留了一对原始值的最低有效位，但与共同最高有效部分相关联。另外，附加位表示最高有效部分是否必须在重建所述对的第二值时递增。 [0131] 图6A示出了用于根据选择控制线对相同的14位值与24位值进行相加或相减以生成两个另选值中的一个的常规蝶式电路。图6B示出了可以简化成14位加法器的蝶式电路，用于对14位值和24位值的14位LSB进行相加或相减，以生成结果的两个另选14位LSB中的一个，根据组合24位值的10位MSB的加法运算或减法运算加上一进位或借位位，来生成两个另选10位MSB图案中的一个。如果14位加法/减法器没有生成借位或进位，则MSB图案可以相同。在图6C中，简单地预存储两个另选14位结果，代替24位值地连同
10位MSB一起存储与差(减法)运算相对应的结果，而代替14位值地存储与和结果相对应的结果。然而，第15位需要表示10位MSB在和的情况下是否相同或递增1。在差的情况下第15位总是零，并且被示为沿着根据24位字的14位LSB的针对选择器的输入。如果零在存储器中作为缺少的晶体管来执行，则零列不占据硅面积。如果需要，则在图6C中仍需要进位传送器，以递增10位MSB。

[0132] 不需要明确地设置图6C中的选择器。在存储器中，地址位选择许多存储值中的一个或另一个是固有的。因此，根据选择线简单地选择两个另选14(或15)位图案，其是14位地址的最低有效位。按地址的13位MSB寻址10位MSB。由此，存储器包括8192个10位字和16384个14/15位字，总计319488位，考虑取消14位加法器，其是超过8192位。最后，图6D示出了通过在随后的加法器中随进位位延迟递增10位MSB并且简单地向前馈给要在常规机会下使用的进位位来省略进位传送器的情况。

[0133] 在图6中把24位字分成10位部分和14位部分起因于显示从未大于14位值的偶数与奇数寻址值之间的三角值的示范函数。10位MSB在偶数与相邻的奇数寻址值之间总是相同或仅差1。类似地，分开的两部分值 之间的差从未大于15位值，而分开的四部分值之间的差从未大于16位值。由此，4(甚或5)个一组的相邻值除可能的增量1之外还具有相同最高有效8位，同时具有不同的最低有效16位部分。由此，另选实现是把存储器设置为4096个8位值和16384个17位值，第17位表示8位MSB是否必须按1递增。其把位数缩减成311296位。示出存储器的针对不同拆分的位数的表如下所示。

[0134]组大小 MSB位数 LSB(+1)位数 存储器位数
2 10 15 319488
4 8 17 311296
8 7 18 309248
16 6 19 317440
32 5 30 330240
64 4 21 345088

[0135] 该表表示存在最小化位数的最佳拆分。

[0136] 现在，可以通过识别每组内单调增加值的LSB图案来迭代该过程。例如，在最后的情况下，在每组64个值中，没有两个相邻值可以相差大于14位值。由此，可以把些值分成每组2个的32组，针对每对存储7位MSB(其可以必须按1递增)和两个另选14位或位LSB图案，第15位表示7位MAB是否应当递增1。

[0137] 下面，示出了用于表示每64个21位值一组的多组不同方式，隐含存储器的总位数。

[0138]组大小 MSB位数 LSB(+1)位数 针对64组的位数 存储器总计
2 7 15 1184 304128
4 5 17 1168 300032
8 4 18 1184 304128

[0139] 针对每32个值一组的多组的情况重复该过程生成：

[0140]组大小 MSB位数 LSB(+1)位数 针对64组的位数 存储器总计
2 6 15 576 297472
4 4 17 576 297472
8 3 18 588 303616

[0141] 针对每16个值一组的多组的情况，获得：

[0142]组大小 MSB位数 LSB(+1)位数 针对64组的位数 存储器总计
2 5 15 280 292864
4 3 17 284 296960

[0143] 对于任何给定的规则函数的表来说，可以执行上述试验并确该方法将获得最小数目的存储位。

[0144] 上述方法不仅可以用于光滑函数，而且可以用于分段光滑函数。例如，如果每次利用上述任一技术压缩每32个一组值的多组，则仅需要针对每32个一组中的值来表示一光滑函数，即，连续函数。那么，不同组之间的不连续性是不重要的。

[0145] 为了说明针对更随机的数据怎样可以应用该技术，首先描述了典型的MOS ROM的构造。图7示出了MOS晶体管的构造。导体栅电极由具有高熔点的导体材料制成，以使耐受处理温度，并且利用通常由二氧化硅制成的硅绝缘层与硅基板分开。通常，首先利用栅电极结构覆盖整个基板并接着刻蚀除希望栅电极所在位置之外的部分来制作栅极及其下面的氧化物绝缘体。接着，通过在栅电极的任一侧上植入杂质来形成漏电极和源电极，栅电极充任其自己的掩模，以确保漏电极和源电极精确地抵靠栅电极。植入的杂质必须允许通过把温度刚好升高至硅的熔点之下与硅基板晶体结构结合成整体。按这种方法形成了MOS晶体管，通过淀积铝互连轨道来互连它们。

[0146] 图8示出了按这种方法构造的ROM。源电极和漏电极扩散的交替条纹形成大量的其源电极和漏电极并联的晶体管。这些晶体管设置在没有刻蚀过栅电极结构的地方。在希望存储二进制1的地方设置一晶体管，在要存储二进制0的地方没有设置晶体管。实际上，在图8中，晶体管被示为包括在漏电极线上方的来自源电极线的一栅电极和在漏电极线下方的来自源电极线的一栅电极。两者都通过同一选通脉冲使能，并由此实际上是两个晶体管并联。总而言之，分开的漏电极线的数目对应于位数。针对同一字的所有源电极线都在左手侧连接至字行使能信号，其被 拉接于地，以读取该行的字。

[0147] 不同列的晶体管对应于行中的不同字。地址解码器接受二进制地址输入并且将一使能信号施加在一个列中的所有栅电极上。由此使能针对漏电极线的特定字的所有位。如果在该位置中包含零，则通过导通晶体管来下拉漏电极线，否则，如果晶体管缺失(对应于字中的0)，则不下拉漏电极线。

[0148] 可以构成多行字，并且地址线由顶至底贯穿所有行。把针对每个字行的源电极使能线连接至第二行地址解码器，从而整个地址接着成为列地址和行地址的组合。在图9A和9B中示出了下拉使能字行的源电极线的合适的行地址解码器。

[0149] 如图9A所示，级联创建模块包括两个其源电极共用为“共源电极(cascoding)输入”C的MOS晶体管。地址线连接至一个晶体管的栅电极，而其漏电极产生一补偿地址信号，其连接至其它晶体管的栅电极。该结果是任一晶体管或源电极与漏电极之间的传导依赖于地址线是高还是低。图9B中示出了这种创建模块的级联，其中地址位A1控制的第一器件的漏电极连接部DR1和DR2连接至该链式结构中高一级的都由地址位A2控制的两个相同创建模块的源电极连接部。它们的漏电极连接部依次连接至全部由地址位A3控制的配对的创建模块，以表示8个漏电极连接部，等。这样，通过创建模块的二进制树解码N位地址N位图案来生成从2 最终漏电极连接部到注释为“芯片使能”的第一源电极连接部的通路。 [0150] 下拉芯片使能线接着下拉漏电极连接部中的与使能通路相对应的一个，其依次下拉字行源电极线中的一条，其依次下拉针对该字行的漏电极线，通过列地址导通与该字行相对应的字晶体管。感测放大器(未示出)检测其位线允许从电源汲取电流并且产生与地址字相对应的输出使能位图案。该感测放大器补偿通过晶体管的长链式结构的损耗，并向针对存储器的外部处理器提供缓冲的逻辑电平输出。

[0151] 图10示出了包含随机值的存储器怎样可以按数值次序排列。字被简单地分类并按数字次序排列，同时保持连接至地址解码器的同一输出线， 这需要解码的地址线如图所示交叉，其可以容纳有合适的多层互连图案。地址线可以按不同的交叉图案再排列，用于连接至字的下一行，其很可能按完全不同的次序分类。这在其本身来说没有完成压缩，而仅仅是例示可能性，在仍读出与每个地址相关联的正确值的同时按数值的平滑单调递增次序排列芯片上的随机数据。

[0152] 图11例示了利用解码器、交叉线图案，以及编码器来执行存储器的针对随机数据的第一次压缩。与图10相比，已经去除了按值分类次序的每个另选全字。现在，针对去除的字的前一字按其自身地址和省略的字的地址寻址，该省略的字的地址由于包括一OR选通而邻接于所述前一字的地址，用于OR两个地址。现在，省略的字的地址线使能缩短的三角字，其要通过重建逻辑相加于前一字，以便生成省略的字。存储器的位数在每对两个输入OR选通的成本方面，已经缩减至针对每对原始全字的一全字和1三角字。两-输入OR选通最大存在4个晶体管，其可以计数为四位。在估计节省的硅面积量方面，这应当与三角字长相加。

[0153] 地址线交叉图案还需要芯片面积。通过在全字下方再设置OR选通，交叉连接图案可以利用适当数目的彼此绝缘或互相隔离的金属化层来贯穿全字占用的面积的顶部。可以利用光刻计数制造这种层。针对本发明的目的，假定可以使用基本上数目不限的金属化层，并且绝缘层隔离交叉互连线和/或交叉互连线的图案，以防止不必要的接触。的确，利用互连图案的层上层结构，以便利用相同的芯片面积、采用垂直维度来存储更多数据。 [0154] 当大于第一次的差可能没有显示有意义的规则性时，在延伸针对随机数据的更高次差算法的概念上是必须要注意的。代替地，选择一个全字作为针对一组字的基值，并且利用它们的从该基值起的三角值替换该组中的其它字，可以改进压缩的效率。例如，可以用f0、d1＝f1-f0、d2＝f2-f0，以及d3＝f3-f0来替换四个一组的值f0、f1、f2，以及f3。接着，4个地址的逻辑OR必须寻址值f0。四个输入选通最大为8个晶体管。该4个输入OR选通占用的硅面积是用于把3个全字f1、f2，以及f3缩减成三个三角字d1、d2，以及d3而节省的成本。4输入OR选通仅两倍复杂于2 输入OR选通，而当前存储器缩减为大约3倍大。由此，与获得的节省相比，已经缩减了OR选通的消耗(overhead)。无论要存储的两个数据值在哪里相同并由此按值分类的次序彼此紧邻地出现，就利用单一值替换它们，并且没有三角值需要存储。因而，不需要与零三角值相对应的地址线，而且可以利用如图12所示的AND-OR选通把针对单个存储的值的两个地址线的OR吸收到地址解码的最后级中。 [0155] 图12A示出了图9类型的用于例如把8地址位解码成256地址线的两个解码器。因为图9具有漏极开路输出，所以必须添加上拉晶体管(电阻器)以把输出重置成已知的存储器读取之间的状态。一个解码器的256线(A0…A255)与另一个解码器的256线(B0…B255)交叉，以获得65536个交叉点。当必须解码65536条线中的单个一条时，在该连接点处设置2输入AND选通，由于比较起来可以忽略8*256线解码器中的晶体管数，所以如图12B所示，给出了每输出线4晶体管的地址解码器复杂性。然而，当仅需要两个地址的OR时，图
12C示出了怎样可以不利用附加晶体管重连接两个AND选通的8个晶体管来形成AND-OR。 [0156] 利用上述技术分析在移动装置中使用的一些典型的DSP程序来进行对可能节省的估计。包括8464个16位指令的第一程序被检测到仅包括911个不同的16位值。明显地，许多值被重复了多次，并且上述仅存储这些一次和利用AND-OR地址解码的技术可以在芯片面积中近似地节省系数达9，而不需要使用任何三角值。2296个字的第二程序被发现仅包括567个不同的16位值，而且允许有效压缩系数。合并的程序从10760个字压缩至
1397个字。在常规存储器的地址解码器中需要在AND-OR地址解码中使用的每地址4个晶体管，由此，没有增加复杂性。对大小缩减的更精确的估计把地址解码器的每地址4个晶体管增加至存储器阵列的每字16个晶体管，以获得针对常规存储器的每字总计20个晶体管，其缩减成4+16/9个晶体管，其大约表示缩减系数3。

[0157] 当要存储的字数超过可能的值数时，例如，存储1百万个16位字，明显的是，利用按其要存储的同一字使能实现特定的16位字的AND-OR地址解码来合并全部地址，从不需要存储多于65536个值。一个这种类 型的存储器受益于使用更多的重叠互连层来处理AND-OR寻址的复杂互连图案。由此，这种技术是利用芯片上垂直维度(更多互连层)来实现更多有效存储的方法。

[0158] 针对后者的情况，甚至不需要存储65536个可能的字。需要已经把合适地址线AND-OR处理成65536条线中的一条，以使生成从0到65535的值的输出。一个称做优先级编码器的装置可以用作65536∶16线编码器，其是16∶65536线地址解码器的逆函数。可以利用每输入最多6个晶体管来构造优先级编码器，其小于其它方面所需的每字16位。图13示出了一优先级编码器。

[0159] 一组编码成0到N-l的N输入被分成了第一个一半0到N/2-1和第二个一半N/2到N-1。从第一和第二个一半中选择配对的对应线，例如，如图所示的0线和N/2线要一起OR处理。如果输入中的任一个是1，则NOR选通给出逻辑“0”。如果下输入是1，则N型晶体管的导通并连接上输入，其必须为0，以输出B。如果任一输入为1，则P型晶体管导通，并且如果上输入是1则连接上输入至输出B。由此，如果输入中的任一个是1，则输出B具有上输入的极性，否则输出B为开路。如果有源输入线设置在输入的上半部，则全部输出B的输出并联形成导线接通的OR，给出1，否则输出“0”。这是希望的编码的最高有效位。接着，针对N/2重复该过程，输出A0至A(N/2-1)，以生成希望的编码的第二最高有效输出位，等。由此，为完整地编码输入线所需的级数是N/2+N/4+N/8…＝N-1，并且每级包括6个晶体管(4个晶体管NOR选通加上P和N型晶体管)。

[0160] 如图14所示，地址编码器及其逆编码器(优先级编码器)的合并刚好再现输入。然而，如果线交叉，则生成任何1∶1映射(还已知为替换盒或S盒，或者信息无损编码)。
如果一些地址是被AND-OR处理过，隐含一些输出值缺失，则生成多比一映射或信息有损编码。由此，可以按这种方式生成任何具有输出字长等于地址字长度的只读存储器。当这种信息是图14A与14B之间的唯一差别时，其明显地存储在地址线交叉或置换图案中。利用在地址解码器中估计的每线4个晶体管和在优先级 编码器中的6晶体管示出了针对超过
1024个10位字的存储器的节省。然而，利用多互连层，可以生成几个不同的互连图案，全部共享同一优先级编码器和地址解码器，提供选择希望的互连图案的方法。由如图13所示的P和N型晶体管并联组成的、每线一系列导通开关可以用于其。由此，可以选择互连图案的N
数目M，并且可以利用每字2+10/M晶体管生成大小M.2 个N位字的存储器，当层数增加时，示出了增加的效率。可以的是，可以使用单晶体管导通开关，例如通过生成电源-V1(用于P型开关)或Vcc+V1(用于N型开关)，以确保针对逻辑1或逻辑0电平的开关导通。 [0161] 概括地，已经示出了存储的数据的表，其表示可以通过仅存储数字地相邻的值的每组的一个基值，加上针对该组中的其它值的根据基值的三角值来压缩单调函数。另选地，利用修改的蝶式运算，可以利用沃尔什变换来变换成组的值。因为存储器表已经消失，所以后者的限制情况导致这样的性能，即，利用具有固定输入的加法器阵列来合并任何单调函数。公开了针对存储三角值的一个另选，包括存储预计算的三角值相加的结果的LSB部分，如果需要针对MS部分的进位，则加上附加位来表示，由此取消多数重建加法器。这种技术扩展至分段单调函数，其中，函数是针对每个压缩组的单调函数。接着，该技术通过设想通过置换地址线要首先按数字次序存储数据，扩展至针对计算机程序的随机数据。 [0162] 当任何三角值为零时，其不需要存储，也不生成地址线来寻址该三角值，由此，允许简化需要基字的地址的OR处理。分析典型的DSP程序表明，可以单独利用这种技术完成多数压缩。而且，可以代替存储全部可能的输出值地通过利用每地址线6个晶体管的优先级编码器生成它们，其在可能的输出值数大于64时更加有效。接着信息驻留在把地址解码器连接至优先级编码器的互连图案中。最后，示出的是，通过采用垂直维度来构造几个这种互连图案，并且针对每字使用的晶体管数的缩减(基本上每字1或2晶体管)，利用导通开关选择希望的图案，可以存储几组随机数据的存储器。

[0163] 当然，在不脱离本发明的实质特征的情况下，与在此具体阐述的那 些相比，可以按其它方式执行本发明。具体实施例被视为在全部方面是例示性而非限制性的，并且落入所附权利要求的含义和等同范围内的全部变化都被涵盖于此。