臺灣博碩士論文加值系統

在數位信號處理系統領域中， 快速 Walsh Hadamard 轉換，是一種單純且重要的演算法，快速 Walsh Hadamard 轉換，其基本定義中即具備遞迴的特性。 因此快速 Walsh Hadamard 轉換，是很適用於張量乘積的公式模式。而張量乘積也可被用來表示互連網路的拓樸架構。在本論文中，我們將整合具備遞迴演算法的張量乘積公式，以及互連網路模式，來設計在不同的互連網路架構上的快速Walsh Hadamard 轉換，分別是hypercube網路、 omega網路 、以及baseline網路。設計過程中，當提供一種特殊的互連網路時，從具備快速Walsh Hadamard轉換的張量乘積公式開始，我們將推導出其相對應的互連網路形式的張量乘積公式。這種演譯結果，將有助於設計具備數位信號處理系統的大型積體電路演算法。

The fast Walsh Hadamard transform is a simple and important algorithm in digital signal processing, especially, in digital image compression. The fast Walsh Hadamard transform is a block recursive algorithm, which can be easily expressed as a tensor product formula. Also, the tensor product notation can be used to express the topology of interconnection networks. In this thesis, we will emerge the specification of tensor product formulation of block recursive algorithms and interconnection networks to design fast Walsh Hadamard transform algorithms on various interconnection networks, including hypercube networks, omega networks, and baseline networks. The design process starts from a tensor product formula of the fast Walsh Hadamard transform. Given a specific interconnection network, we will manipulate the tensor product formula of the fast Walsh Hadamard transform to an equivalent formula which fits the form of the tensor product formula of that interconnection network. The resulting algorithms are suitable for designing VLSI circuits of DSP algorithms.

Table of Contents
中文摘要 …………………………………………..…..…………………………. i
Abstract …………..………………………………………….…………………. ii
List of Figures …………….…………………………………..………………… iv
Chapter 1 Introduction ..…………………………………………………...…1
Chapter 2 Tensor Product Notation ………………………………………….. 3
Chapter 3 Fast Walsh Hadamard transform algorithm ……………………. 6
Chapter 4 Designing fast Walsh Hadamard Transform on Various
Interconnection Networks ……………………………………….. 8

4.1 Fast Walsh Hadamard Transform on Hypercube Networks ……….. 10

4.2 Fast Walsh Hadamard Transform on Omega Networks …………… 12
4.3 Fast Walsh Hadamard Transform on Baseline Networks ………… 13
Chapter 5 Conclusions and Future Works …………………………………… 20
Bibliography …………………….………………………………………………… 21
Acknowledgement ……………….………………………..…..………………… 23
Vita ………………………………….………………………..…..………………… 24

[1] J. W. Brewer. Kronecker products and matrix calculus in system theory. IEEE
Transaction on Circuits and Systems, 25:772—781, 1978.
[2] D. L. Dai, S. K. S. Gupta, S. D. Kaushik, J. H. Lu, R. V. Singh, C.-H. Huang, P. Sadayappan,
and R. W. Johnson. EXTENT: A portable programming environment
for designing and implementing high-performance block-recursive algorithms. In
Proceedings of Supercomputing ’94, pages 49—58, 1994.
[3] M.-H. Fan, C.-H. Huang, and Y.-C. Chung. A programming methodology for
designing parallel prefix algorithms on cube networks. In Proceedings of ICPP
Workshop on Compiler/Runtime Techniques for Parallel Computing, pages 607—
614, 2002.
[4] M.-H. Fan, C.-H. Huang, Y.-C. Chung, J.-S. Liu, and J.-Z. Lee. A programming
methodology for designing parallel prefix algorithms. In Proceedings of the 2001
International Conference on Parallel Processing, pages 463—470, 2001.
[5] J. Hennessy and D. Patterson. Computer Architecture. Mogan Kaufmann, 3rd.
edition, 2002.
[6] C.-H. Huang, J. R. Johnson, and R. W. Johnson. A tensor product formulation
of Strassen’s matrix multiplication algorithm. Appl. Math Letters, 3(3):104—108,
1990.
[7] C.-H. Huang, J. R. Johnson, and R. W. Johnson. Generating parallel programs
from tensor product formulas: A case study of Strassen’s matrix multiplication
algorithm. In Proceedings of the 1992 International Conference on Parallel Processing,
volume III, Algorithms and Applications, pages III:104—108, 1992.
[8] K. Hwang and Z. Xu. Scalable Parallel Computing. McGraw-Hill, 1998.
[9] J. R. Johnson, R.W. Johnson, D. Rodriguez, and R. Tolimieri. A methodology for
designing, modifying and implementing Fourier transform algorithms on various
architectures. Circuits Systems Signal Process, 9(4):450—500, 1990.
[10] R. W. Johnson, C.-H. Huang, and J. R. Johnson. Multilinear algebra and parallel
programming. The Journal of Supercomputing, 5(2—3):189—217, 1991.
[11] S. D. Kaushik, S. Sharma, and C.-H. Huang. An algebraic theory for modeling
multistage interconnection networks. Journal of Information Science and Engineering,
9(1):1—26, 1993.
[12] S. D. Kaushik, S. Sharma, C.-H. Huang, J. R. Johnson, R. W. Johnson, and P. Sadayappan.
An algebraic theory for modeling direct interconnection networks.
Journal of Information Science and Engineering, 12(1):25—49, 1996.