背景技术
信息处理(计算,通信,数据处理等)中的当前趋势是数字化的。进行数字处理的趋势的原因如下:
1。数据的数字传输最大程度地减小了通道噪声的影响。
2。数字信号易于重新生成。
3。数字处理器参数稳定。
4。数字处理器中的错误很容易预测和控制。
5。数字处理器往往比模拟处理器更通用。
6。数字处理器可以很容易地与无处不在的数字计算机连接。
转换是数据处理的基础。诸如信号分类,编码,冗余减少等的数据处理功能都涉及一种或另一种的变换。傅里叶变换是众所周知的变换的一个例子,该变换在滤波,光谱分析和模式分类中起着核心作用。另一个例子是特征向量,Hotelling或Karhunen-Loeve变换,该变换已广泛用于数据表征和统计分析。其他转换(例如Laplace,Hilbert,Bessel,Laguere,Hermite和Chebyshev)已在所有类型的数据分析中得到广泛使用。 。除了傅里叶变换,对于N维输入数据向量,所有运算都需要N.sup.2的计算运算。计算这些转换的这两个要求需要相对复杂的数字硬件机制。这两个要求还需要较长的变换计算时间。
最近,已经提出了许多变换,无需输入数据相乘即可进行计算,并且仅需要N log.sub.2的数量级。 N次计算。该组中包括著名的Walsh-Hadamard和Haar变换。这些转换本质上是二进制或三次的,非常适合于简单的数字实现和快速计算。这些变换已被用于数据过滤,多路复用,减少冗余,信号表征频谱分析,模式分类和许多其他数据处理操作。发明内容本发明提供了具有以下重要特征的用于数字地实现一类变换的方法和装置:
1。该类具有简单的数字结构,能够以高吞吐率运行。该类的直接成员和反向成员都存在相同的结构。本发明通过仅使用一些逻辑元件,例如移位寄存器和加法器/减法器,提供了简化的机械化和高速操作。,并且可以选择包含乘数。该类的结构由由这些逻辑元素组成的多个相同的简单模块组成。
2。计算成员变换所需的计算数量不超过2N log N.
3。存在用于仅使用加法和减法运算以及使用加法,减法和乘法运算生成成员变换的选项。
4。当前使用的所有二元和三元变换(如Walsh-Hadamard和Haar)都属于此类。
具有上述属性的一类变换提供了特别重要的新颖且显而易见的结果,即可以在整个类上实现单个数字变换处理器,能够针对几乎任何特定类别的数据(例如,风景,打字材料,语音,雷达信号,遥测信号等)和数据处理操作进行优化。这样的变换处理器能够以简单,低成本,高度可靠的数字硬件实现,并以高吞吐率(大于150兆比特/秒)实时运行。
本发明在数学上被定义为尺寸为N = 2.sup.M的变换,其中M = 1、2---。该类中的成员变换T由矩阵级联定义。 ## EQU1 ##,其中## EQU2 ##与## EQU3 ##和## EQU4 ##
该类的几个重要成员在以下示例中进行了更完整的描述:
例1
该类的一个成员由M = 3和N 2.sup给出。 M = 8,而Tjk不能识别矩阵。 ## EQU5 ##
如果将所有w都设置为1,则T = T.sub.3 T.sub.2 T.sub.1是Walsh变换的矩阵。 ## TBL1 ##
示例2
通过使T等于M = 3和N = 2产生另一个称为有理Haar变换的类的成员。 sub.22,T.sub.32,T.sub.33,T.sub.34身份矩阵并将所有w设置为1。 ## EQU6 ##
该类中成员变换T的逆由矩阵级联## EQU7 ##给出,其中## TBL2 ##与## EQU8 ##和## TBL3 ##或## TBL4 ## ## EQU9 ##
示例3
示例2中的T的倒数是:## TBL5 ## ## EQU10 ##
由不同的Tjk矩阵形成的类中的转换总数为## EQU11 ##
对于M = 5,有2.sup.2.spsp4。 = 2 = 16 = 65,536个类别中的不同空间变换。
可以看出,本发明的方法基于将数据矢量分解为与该类别中的变换矩阵相关的系数集合。该类中的每个变换都由基本变换的有序级联组成。级联的每个状态都由加权变换(对角加权矩阵)和生成变换(由+ 1,-1和零元素组成的稀疏矩阵)的乘积组成。获得逆生成变换作为生成变换的伴随(生成矩阵的转置)。该类中的任何成员变换最多需要2N log.sub.2 N个实数计算,其中N是数据向量的维数,N是2的整数幂。取决于权重变换的选择,该类中的成员变换可以是正交变换。本发明可以通过将加法器/减法器模块以级联的形式级联级联以数字方式实现前向变换的类别。每个阶段是前一个阶段的两倍。所有模块都具有相同的结构,并由加法器/减法器,延迟和乘法器构成。逆变换的类别是使用与直接变换的类别相同的加法器/减法器模块的基本结构来实现的。每个阶段中模块的数量是前一阶段中模块数量的一半。
公开/公告号FR2324055A1
专利类型
公开/公告日1977-04-08
原文格式PDF
申请/专利权人 NORTHROP CORP;NORTHROP CORP;
申请/专利号FR19760023392
发明设计人
申请日1976-07-30
分类号G06F7/00;
国家 FR
入库时间 2022-08-22 23:48:14