Fast Finite Field Hartley Transforms Based on Hadamard Decomposition
This work provides efficient algorithms for FFHT, benefiting applications in multiple access systems and spread spectrum sequences, though the novelty is incremental as it builds on known decomposition techniques.
The paper introduces fast algorithms for the finite field Hartley transform (FFHT) by decomposing it using Hadamard-Walsh transforms, achieving lower multiplicative complexity that meets theoretical bounds for all investigated cases.
A new transform over finite fields, the finite field Hartley transform (FFHT), was recently introduced and a number of promising applications on the design of efficient multiple access systems and multilevel spread spectrum sequences were proposed. The FFHT exhibits interesting symmetries, which are exploited to derive tailored fast transform algorithms. The proposed fast algorithms are based on successive decompositions of the FFHT by means of Hadamard-Walsh transforms (HWT). The introduced decompositions meet the lower bound on the multiplicative complexity for all the cases investigated. The complexity of the new algorithms is compared with that of traditional algorithms.