TAILIEUCHUNG - Digital Signal Processing Handbook P9

Complexity theory of computation attempts to determine how “inherently” difficult are certain tasks. For example, how inherently complex is the task of computing an inner product of two vectors of length N? Certainly one can compute the inner product N=1 xj yj by computing the j N products xj yj and then summing them. But can one compute this inner product with fewer than N multiplications? The answer is no, but the proof of this assertion is no trivial matter. One first abstracts | Feig E. Complexity Theory of Transforms in Signal Processing Digital Signal Processing Handbook Ed. Vijay K. Madisetti and Douglas B. Williams Boca Raton CRC Press LLC 1999 1999 by CRC Press LLC Complexity Theory of Transforms in Signal Processing Ephraim Feig IBM Corporation . Watson Research Center Introduction One-Dimensional DFTs Multidimensional DFTs One-Dimensional DCTs Multidimensional DCTs Nonstandard Models and Problems References Introduction Complexity theory of computation attempts to determine how inherently difficult are certain tasks. For example how inherently complex is the task of computing an inner product of two vectors of length N Certainly one can compute the inner product j i xjyj by computing the N products xjyj and then summing them. But can one compute this inner product with fewer than N multiplications The answer is no but the proof of this assertion is no trivial matter. One first abstracts and defines the notions of the algorithm and its components such as addition and multiplication then a theorem is proven that any algorithm for computing a bilinear form which uses K multiplications can be transformed to a quadratic algorithm some algorithm of a very special form which uses no divisions and whose multiplications only compute quadratic forms which uses at most K multiplications 20 and finally a proof by induction on the length N of the summands in the inner product is made to obtain the lower bound result 6 13 22 25 . We will not present the details here we just want to let the reader know that the process for even proving what seems to be an intuitive result is quite complex. Consider next the more complex task of computing the product of an N point vector by an M x N matrix. This corresponds to the task of computing M separate inner products of N-point vectors. It is tempting to jump to the conclusion that this task requires MN multiplications. But we should not jump to fast conclusions. First the M .

• Tự động hoá
• Tự động hóa
• Năng lượng
• Cơ khí chế tạo máy
• Điện – điện tử
• Kiến trúc xây dựng
• Bài giảng Tự động hóa
• Tự động hóa quá trình sản xuất
• Tự động hóa quá trình lắp ráp
• Định vị chi tiết
• Lắp ráp tự động
• Xác định chế độ lắp ráp tự động
• Ứng dụng Robot trong lắp ráp tự động
• tự động hóa trong xây dựng
• giáo trình tự động hóa trong xây dựng
• bài giảng tự động hóa trong xây dựng
• tài liệu tự động hóa trong xây dựng
• lý thuyết tự động hóa trong xây dựng
• hệ thống tự động hóa trong xây dựng
• Giáo trình Tự động hóa
• Tự động hóa trong hệ thống điện
• Tài liệu tự động hóa
• Tìm hiểu tự động hóa hệ thống điện
• Khái niệm tự động hóa
• Lịch sử tự động hóa
• Sửa chữa thiết bị tự động hóa
• Thiết bị tự động hóa
• Giáo trình Lắp đặt thiết bị đo lường tự động hóa
• Lắp đặt thiết bị đo lường tự động hóa
• Thiết bị đo lường tự động hóa
• Dầu bôi trơn
• đề cương tự động hóa
• phương pháp tự động hóa
• Hệ thống tự động hóa
• Tự động hóa trong quá trình sản xuất
• Hệ thống điều khiển tự động
• Tự động hóa quá trình cắt phôi
• Tự động hóa quá trình kiểm tra
• Tự động điều khiển máy móc
• Tự động hóa quá trình công nghệ
• Lý thuyết điều khiển tự động
• Hệ thống rửa xe tự động
• Đồ án tự động hóa
• Hệ thống tự động
• Kiểm tra tự động
• Thiết bị phân loại tự động
• Hệ thống sản xuất tự động hóa
• lập trình tự động hóa
• tài liệu lập trình tự động hóa
• hướng dẫn lập trình tự động hóa
• phương pháp lập trình tự động hóa
• kinh nghiệm lập trình tự động hóa