Fast computation of the two-dimensional generalised Hartley transforms

The two-dimensional generalised Hartley transforms (2-D GDHTs) are various half-sample generalised DHTs, and are used for computing the 2-D DHT and 2-D convolutions. Fast computation of 2-D GDHTs is achieved by solving (n₁+(n₀₁/2))k₁+(n₂+(n₀₂ /2))k₂=(n+(½))k mod N, n₀₁, n₀₂ =1 or 0. The kernel indexes on the left-hand side and on the right-hand side belong to the 2-D GDHTs and the 1-D H₃, respectively. This equation categorises N×N-point input into N groups which are the inputs of a 1-D N-point H₃. By decomposing to 2-D GDHTs, an N×N-point DHT requires a 3N/2ⁱ 1-D N/2ⁱ-point H₃, i=1, ..., log₂N-2. Thus, it has not only the same number of multiplications as that of the discrete Radon transform (DRT) and linear congruence, but also has fewer additions than the DRT. The distinct H ₃ transforms are independent, and hence parallel computation is feasible. The mapping is very regular, and can be extended to an n-dimensional GDHT or GDFT easily