An efficient recursive algorithm and an explicit formula for calculating update vectors of running walsh-hadamard transform
作者： Barzan Mozafari , Mohammad H. Savoji
DOI: 10.1109/ISSPA.2007.4555315
关键词: Sliding window protocol 、 Algorithm 、 Digital signal processing 、 Sequence 、 Signal processing 、 Algorithm design 、 Mathematics 、 Hadamard transform 、 Fast Walsh–Hadamard transform 、 Walsh function
摘要: Walsh-Hadamard transform (WHT) has many applications in digital signal processing including bioinformatics. While there are efficient algorithms for implementing this such as fast WHT (FWHT), performing continuously on a sliding window over long sequence is time consuming. As it not reasonable to compute separate upon arrival of every new sample, another implementation named running (RWHT) been introduced (G. Deng and A. Ling, 1996) which needs have some update vectors pre-calculated. In paper we report an recursive algorithm find these vectors. Also propose easy-to-compute explicit formula computing coefficients computation independent the vector size. A proof comparison between proposed based also given.
sci-hub.se 参考文章(6)
G. Deng, A. Ling, A running Walsh-Hadamard transform algorithm and its application to isotropic quadratic filter implementation european signal processing conference. pp. 1- 4 ,(1996)
Neungsoo Park, N.K. Prasanna, Cache conscious Walsh-Hadamard transform international conference on acoustics, speech, and signal processing. ,vol. 2, pp. 1205- 1208 ,(2001) , 10.1109/ICASSP.2001.941140
J. Johnson, M. Puschel, In search of the optimal Walsh-Hadamard transform international conference on acoustics, speech, and signal processing. ,vol. 6, pp. 3347- 3350 ,(2000) , 10.1109/ICASSP.2000.860117
J. R. Johnson, R. W. Johnson, D. Rodriguez, R. Tolimieri, A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures Circuits Systems and Signal Processing. ,vol. 9, pp. 449- 500 ,(1990) , 10.1007/BF01189337
J.A. Berger, S.K. Mitra, J. Astola, Power spectrum analysis for DNA sequences information sciences signal processing and their applications. ,vol. 2, pp. 29- 32 ,(2003) , 10.1109/ISSPA.2003.1224807
SD Kaushik, C-H Huang, RW Johnson, P Sadayappan, JR Johnson, None, Efficient transposition algorithms for large matrices conference on high performance computing (supercomputing). pp. 656- 665 ,(1993) , 10.1145/169627.169814