计算二维离散Hartley变换的递归法

Recursive Algorithm for Computing Two-dimensional Discrete Hartley Transform

解放军理工大学,南京210007

PLA University of Science and Technology, Nanjing 210007

在实序列数据处理中,Hartley变换仅需实运算,在存储量和复杂性上要比Fourier变换更经济、更有效,故Hartley变换在图像处理、地震波场模拟等领域已起着愈来愈重要的作用。本文推导出计算二维离散Hartley变换 (2D-DHT)的一种快速递归计算法,对 M×N =2^r×2^s 二维DHT的计算,其计算复杂性为 1/4 MNlog₂ M² N+O(MN) 个实乘和 3/2 MNlog₂ MN +O(MN) 个实加(当r≥s时),以及 1/4 MNlog₂ MN² + O(MN) 个实乘和 3/2 MNlog₂ MN+O(MN) 个实加 (当r<s时),属目前运算量最小的一类算法。

In real sequence data processing, Hartley transform, which involves only real operations, is an economical and efficient alternative to Fourier transform in storage space and computational complexity. So the Hartley transform is playing more important role in applications such as image processing and seismic wave modeling. This paper presents a fast recursive algorithm for computing two dimensional discrete Hartley transform(2D DHT). For DHT calculation of M×N =2^r×2^s real sequence with, the arithmetic complexity is 1/4 MNlog₂ M² N+O(MN) real multiplication and 3/2 MNlog₂ MN +O(MN) real addition (when r≥s), 1/4 MNlog₂ MN² +O(MN) real multiplication and 3/2 MNlog₂ MN+O(MN) real addition (when r<s),Which means the new algorithm involving the least computation.