James William Cooley
James
William Cooley (lahir 1926) adalah seorang matematikawan Amerika. Cooley menerima B.A. sebuah gelar
pada tahun 1949 dari Manhattan College, Bronx, NY, gelar MA pada tahun 1951
dari Universitas Columbia, New York, NY, dan Ph.D. gelar
tahun 1961 dalam matematika terapan dari Universitas Columbia. Dia
adalah seorang programmer komputer John von Neumann di Institute for Advanced
Study, Princeton, NJ, 1953-1956. Dia
bekerja pada perhitungan kuantum mekanik di Courant Institute, New York
University, 1956-1962, ketika ia bergabung dengan Staf Penelitian di Pusat
Penelitian Watson IBM, Yorktown Heights, NY. Setelah
pensiun dari IBM pada tahun 1991, ia bergabung dengan Departemen Teknik
Elektro, Universitas Rhode Island, Kingston, di mana ia menjabat di fakultas
dari program teknik komputer.
Kontribusi yang paling signifikan bagi dunia matematika dan pemrosesan sinyal digital adalah Fast Fourier transform, yang dikembangkan bersama dengan John Tukey (lihat algoritma Cooley-Tukey FFT) saat bekerja untuk divisi riset IBM pada tahun 1965.
Motivasi untuk itu diberikan oleh Dr Richard L. Garwin di IBM Watson Research yang prihatin memverifikasi perjanjian senjata nuklir dengan Uni Soviet untuk pembicaraan GARAM. Garwin berpikir bahwa jika ia memiliki sangat banyak Fourier Transform cepat ia bisa menanam sensor di tanah di negara-negara sekitarnya Uni Soviet. Dia menyarankan ide tentang bagaimana transformasi Fourier dapat diprogram untuk menjadi jauh lebih cepat untuk kedua Cooley dan Tukey. Mereka melakukan pekerjaan, sensor yang ditanam, dan ia dapat menemukan ledakan nuklir yang berjarak 15 kilometer dari mana mereka terjadi.
J.W. Cooley adalah anggota Komite Signal Processing Digital dari IEEE, dan kemudian mendapat beasiswa dari IEEE untuk karyanya pada FFT. Pada tahun 2002 ia menerima IEEE Jack Kilby S. Signal Processing Medal. Dia sangat berkontribusi pada pembentukan terminologi dalam pemrosesan sinyal digital.
Publikasi
James W. Cooley & John W. Tukey (1965): "Suatu algoritma untuk perhitungan mesin seri Fourier kompleks", Matematika. Comput. 19, 297-301.
Cooley, James W., Timothy M. Toolan dan Donald W. Tufts. "Sebuah Subspace Tracking Algoritma Menggunakan Fast Fourier Transform." IEEE Signal Processing Letters. 11 (1) :30-32. Januari 2004.
Nyata, Edward C., Donald W. Tufts dan James W. Cooley. "Dua Algoritma untuk Fast Perkiraan Subruang Tracking." Transaksi IEEE pada Signal Processing. 47 (7) :1936-1945. Juli 1999.
Tufts, D. W., E. C. Riil dan J. W. Cooley. "Cepat Perkiraan Subspace Tracking (CEPAT)." IN: Prosiding IEEE Konferensi Internasional tentang Akustik 1997, Ucapan, dan Signal Processing. IEEE. 1997. Saya :547-550.
Kontribusi yang paling signifikan bagi dunia matematika dan pemrosesan sinyal digital adalah Fast Fourier transform, yang dikembangkan bersama dengan John Tukey (lihat algoritma Cooley-Tukey FFT) saat bekerja untuk divisi riset IBM pada tahun 1965.
Motivasi untuk itu diberikan oleh Dr Richard L. Garwin di IBM Watson Research yang prihatin memverifikasi perjanjian senjata nuklir dengan Uni Soviet untuk pembicaraan GARAM. Garwin berpikir bahwa jika ia memiliki sangat banyak Fourier Transform cepat ia bisa menanam sensor di tanah di negara-negara sekitarnya Uni Soviet. Dia menyarankan ide tentang bagaimana transformasi Fourier dapat diprogram untuk menjadi jauh lebih cepat untuk kedua Cooley dan Tukey. Mereka melakukan pekerjaan, sensor yang ditanam, dan ia dapat menemukan ledakan nuklir yang berjarak 15 kilometer dari mana mereka terjadi.
J.W. Cooley adalah anggota Komite Signal Processing Digital dari IEEE, dan kemudian mendapat beasiswa dari IEEE untuk karyanya pada FFT. Pada tahun 2002 ia menerima IEEE Jack Kilby S. Signal Processing Medal. Dia sangat berkontribusi pada pembentukan terminologi dalam pemrosesan sinyal digital.
Publikasi
James W. Cooley & John W. Tukey (1965): "Suatu algoritma untuk perhitungan mesin seri Fourier kompleks", Matematika. Comput. 19, 297-301.
Cooley, James W., Timothy M. Toolan dan Donald W. Tufts. "Sebuah Subspace Tracking Algoritma Menggunakan Fast Fourier Transform." IEEE Signal Processing Letters. 11 (1) :30-32. Januari 2004.
Nyata, Edward C., Donald W. Tufts dan James W. Cooley. "Dua Algoritma untuk Fast Perkiraan Subruang Tracking." Transaksi IEEE pada Signal Processing. 47 (7) :1936-1945. Juli 1999.
Tufts, D. W., E. C. Riil dan J. W. Cooley. "Cepat Perkiraan Subspace Tracking (CEPAT)." IN: Prosiding IEEE Konferensi Internasional tentang Akustik 1997, Ucapan, dan Signal Processing. IEEE. 1997. Saya :547-550.
John Wilder Tukey
John
Wilder Tukey (16 Juni 1915 - 26 Juli, 2000) adalah seorang matematikawan
Amerika terkenal karena pengembangan algoritma FFT dan box plot.
Isi
Biografi
Tukey lahir di New Bedford, Massachusetts pada tahun 1915, dan memperoleh gelar BA pada tahun 1936 dan M.Sc. pada tahun 1937, dalam bidang kimia, dari Brown University, sebelum pindah ke Princeton University di mana ia menerima gelar Ph.D. dalam matematika.
Selama Perang Dunia II, Tukey bekerja di Fire Control Research Office dan berkolaborasi dengan Samuel Wilks dan William Cochran. Setelah perang, ia kembali ke Princeton, membagi waktunya antara universitas dan AT & T Bell Laboratories.
Di antara banyak kontribusi untuk masyarakat sipil, Tukey bertugas di komite Asosiasi Statistik Amerika yang menghasilkan sebuah laporan menantang kesimpulan dari Laporan Kinsey, Masalah Statistik Laporan Kinsey pada Perilaku Seksual dalam Pria Manusia.
Dia dianugerahi Medali Kehormatan IEEE pada tahun 1982 "Untuk kontribusi untuk analisis spektral proses acak dan Fourier Transform (FFT) algoritma cepat."
Tukey pensiun pada tahun 1985. Dia meninggal di New Brunswick, New Jersey pada 26 Juli 2000.
Kontribusi ilmiah
Pada awal kariernya Tukey bekerja pada pengembangan metode statistik untuk komputer di Bell Labs di mana ia menciptakan istilah "bit".
Kepentingan statistik nya banyak dan beragam. Dia diingat karena perkembangannya dengan James Cooley dari algoritma Cooley-Tukey FFT. Pada tahun 1970, ia memberikan kontribusi signifikan terhadap apa yang sekarang dikenal sebagai pisau lipat estimasi-juga disebut Quenouille-Tukey berlipat. Dia memperkenalkan box plot dalam bukunya tahun 1977, "Analisis Data eksplorasi".
Uji jarak Tukey, distribusi lambda Tukey, uji Tukey dari aditivitas dan lemma Tukey semua menanggung nama-Nya. Dia juga pencipta beberapa metode yang kurang dikenal seperti trimean dan median-median line, alternatif mudah untuk regresi linier.
Pada tahun 1974, ia mengembangkan, dengan Jerome H. Friedman, konsep mengejar proyeksi.
Praktek statistik
Dia juga memberikan kontribusi untuk praktek statistik dan mengartikulasikan perbedaan penting antara eksplorasi analisis data dan analisis data konfirmasi, percaya bahwa banyak metodologi statistik ditempatkan terlalu besar penekanan pada yang terakhir.
Meskipun ia percaya pada utilitas memisahkan dua jenis analisis, ia menunjukkan bahwa kadang-kadang, terutama dalam ilmu pengetahuan alam, ini adalah bermasalah dan disebut situasi seperti ilmu nyaman.
Istilah statistik
Tukey diciptakan istilah statistik banyak yang telah menjadi bagian dari penggunaan umum, tetapi dua coinages paling terkenal dikaitkan dengannya berhubungan dengan ilmu komputer.
Ketika bekerja dengan John von Neumann pada desain komputer awal, Tukey memperkenalkan kata "bit" sebagai kontraksi dari "digit biner". Istilah "bit" pertama kali digunakan dalam sebuah artikel oleh Claude Shannon pada tahun 1948.
Istilah "perangkat lunak", yang Paulus Niquette mengklaim ia menciptakan pada tahun 1953, pertama kali digunakan di cetak oleh Tukey dalam sebuah artikel di American Bulanan matematika tahun 1958, dan dengan demikian beberapa atribut istilah kepadanya. Itu 1958 penggunaan pertama dan atribusi dipertanyakan, mengingat bahwa Prosiding Simposium Nasional Kedua di Quality Control dan Keandalan dalam Elektronika: Washington, DC, 09-10 Januari 1956, diakses pada Hathi Trust, berisi terjadinya lunak jangka .
Tanda kutip
Jika kita butuh saran singkat dari apa eksplorasi analisis data, saya akan menyarankan bahwa
Ini adalah sikap DAN
Sebuah fleksibilitas DAN
Beberapa kertas grafik (atau transparansi, atau keduanya).
Tidak ada katalog teknik dapat menyampaikan kesediaan untuk mencari apa yang dapat dilihat, apakah atau tidak diantisipasi. Namun ini adalah inti dari eksplorasi analisis data. Grafik kertas - dan transparansi - berada di sana, bukan sebagai suatu teknik, melainkan sebagai pengakuan bahwa mata-gambar memeriksa adalah penemu terbaik yang kita miliki dari sesuatu yang tak terduga.
AD Gordon ditawarkan berikut ringkasan prinsip Tukey untuk praktek statistik:
... kegunaan dan keterbatasan statistik matematika, pentingnya memiliki metode analisis statistik yang kuat untuk pelanggaran asumsi yang mendasari penggunaannya, kebutuhan untuk mengumpulkan pengalaman perilaku spesifik metode analisis dalam rangka memberikan panduan tentang penggunaan; pentingnya membiarkan kemungkinan data yang mempengaruhi pilihan metode yang mereka dianalisis, kebutuhan untuk statistik untuk menolak peran 'wali kebenaran terbukti', dan untuk menolak upaya untuk menyediakan sekali-untuk-semua solusi dan rapi atas -unifications subjek, sifat iteratif analisis data, implikasi dari peningkatan daya, ketersediaan dan murahnya fasilitas komputasi, pelatihan statistik.
Jauh lebih baik jawaban perkiraan atas pertanyaan yang tepat, yang sering kabur, dari satu jawaban yang tepat untuk pertanyaan yang salah, yang selalu dapat dibuat tepat.
Sekali statistik waktu hanya dieksplorasi. Kemudian mereka belajar untuk mengkonfirmasi persis - untuk mengkonfirmasi beberapa hal dengan tepat, masing-masing dalam keadaan yang sangat spesifik. Saat mereka menekankan konfirmasi yang tepat, teknik mereka pasti menjadi kurang fleksibel. Sambungan dari teknik yang paling digunakan dengan wawasan masa lalu melemah. Apa pun yang prosedur konfirmasi tidak secara eksplisit melekat itu mencela sebagai 'statistik deskriptif belaka', tidak peduli berapa banyak kita telah belajar dari itu.
Tidak ada data yang dapat ditampilkan dalam sebuah diagram lingkaran, yang tidak dapat ditampilkan LEBIH BAIK dalam beberapa jenis lain dari tabel.
Publikasi
Andrews, David F, Peter J Bickel, Frank R Hampel, Peter J Huber, WH Rogers & John W Tukey (1972). Perkiraan Kuat lokasi: survei dan uang muka. Princeton University Press. ISBN 0-691-08113-1. OCLC 369.963.
Basford, Kaye E & John W Tukey (1998). Analisis grafis dari data MULTIRESPON. Chapman & Hall / CRC. ISBN 0-8493-0384-2. OCLC 154.674.707.
Blackman, R & B John W Tukey (1959). Pengukuran spektrum daya dari sudut pandang teknik komunikasi. Dover Publications. ISBN 0-486-60507-8.
Cochran, William G, Frederick Mosteller & John W Tukey (1954). Masalah statistik laporan Kinsey pada perilaku seksual pada pria manusia. Jurnal dari Asosiasi Statistik Amerika.
Hoaglin, David C, Frederick Mosteller & John W Tukey (eds) (1983). Memahami Kuat dan Exploratory Data Analysis. Wiley. ISBN 0-471-09777-2. OCLC 8.495.063.
Hoaglin, David C, Frederick Mosteller & John W Tukey (eds) (1985). Menjelajahi Data Tabel, Tren dan Bentuk. Wiley. ISBN 0-471-09776-4. OCLC 11.550.398.
Hoaglin, David C, Frederick Mosteller & John W Tukey (eds) (1991). Dasar-dasar eksplorasi analisis varians. Wiley. ISBN 0-471-52735-1. OCLC 23.180.322.
Morganthaler, Stephan & John W Tukey (eds) (1991). Configural polysampling: rute untuk ketahanan praktis. Wiley. ISBN 0-471-52372-0. OCLC 22.381.036.
Mosteller, Frederick & John W Tukey (1977). Analisis data dan regresi: kursus kedua dalam statistik. Addison-Wesley. ISBN 0-201-04854-X. OCLC 3.235.470.
Tukey, John W (1940). Konvergensi dan Keseragaman Topologi. Princeton University Press. ISBN 0-691-09568-X. OCLC 227.948.615.
Tukey, John W (1977). Exploratory Data Analysis. Addison-Wesley. ISBN 0-201-07616-0. OCLC 3.058.187.
Tukey, John W; Ian C Ross, Verna Bertrand (1973 -). Indeks statistik dan probabilitas. R & D Press. ISBN 0-88274-001-6. OCLC 745.715.
Kumpulan karya John W Tukey, diedit oleh William S Cleveland
Brillinger, David R (ed) (1984). Volume I: Time series, 1949-1964. Wadsworth. ISBN 0-534-03303-2. OCLC 10.998.116.
Brillinger, David R (ed) (1985). Volume II: Time series, 1965-1984. Wadsworth. ISBN 0-534-03304-0. OCLC 159.731.367.
Jones, Lyle V (ed) (1985). Volume III: Falsafah dan analisis data, 1949-1964. Wadsworth & Brooks / Cole. ISBN 0-534-03305-9. OCLC 159.731.367.
Jones, Lyle V (ed) (1986). Volume IV: Falsafah dan analisis data, 1965-1986. Wadsworth & Brooks / Cole. ISBN 0-534-05101-4. OCLC 165.832.503.
Cleveland, William S (ed) (1988). Volume V: Graphics, 1965-1985. Wadsworth & Brooks / Cole. ISBN 0-534-05102-2. OCLC 230.023.465.
Mallows, Colin L (ed) (1990). Volume VI: Lebih matematika, 1938-1984. Wadsworth & Brooks / Cole. ISBN 0-534-05103-0. OCLC 232.966.724.
Cox, David R (ed) (1992). Volume VII: Faktorial dan ANOVA, 1949-1962. Wadsworth & Brooks / Cole. ISBN 0-534-05104-9. OCLC 165.366.083.
Braun, Henry I (ed) (1994). Volume VIII: Beberapa perbandingan, 1949-1983. Chapman & Hall / CRC. ISBN 0-412-05121-4. OCLC 165.099.761.
Isi
Biografi
Tukey lahir di New Bedford, Massachusetts pada tahun 1915, dan memperoleh gelar BA pada tahun 1936 dan M.Sc. pada tahun 1937, dalam bidang kimia, dari Brown University, sebelum pindah ke Princeton University di mana ia menerima gelar Ph.D. dalam matematika.
Selama Perang Dunia II, Tukey bekerja di Fire Control Research Office dan berkolaborasi dengan Samuel Wilks dan William Cochran. Setelah perang, ia kembali ke Princeton, membagi waktunya antara universitas dan AT & T Bell Laboratories.
Di antara banyak kontribusi untuk masyarakat sipil, Tukey bertugas di komite Asosiasi Statistik Amerika yang menghasilkan sebuah laporan menantang kesimpulan dari Laporan Kinsey, Masalah Statistik Laporan Kinsey pada Perilaku Seksual dalam Pria Manusia.
Dia dianugerahi Medali Kehormatan IEEE pada tahun 1982 "Untuk kontribusi untuk analisis spektral proses acak dan Fourier Transform (FFT) algoritma cepat."
Tukey pensiun pada tahun 1985. Dia meninggal di New Brunswick, New Jersey pada 26 Juli 2000.
Kontribusi ilmiah
Pada awal kariernya Tukey bekerja pada pengembangan metode statistik untuk komputer di Bell Labs di mana ia menciptakan istilah "bit".
Kepentingan statistik nya banyak dan beragam. Dia diingat karena perkembangannya dengan James Cooley dari algoritma Cooley-Tukey FFT. Pada tahun 1970, ia memberikan kontribusi signifikan terhadap apa yang sekarang dikenal sebagai pisau lipat estimasi-juga disebut Quenouille-Tukey berlipat. Dia memperkenalkan box plot dalam bukunya tahun 1977, "Analisis Data eksplorasi".
Uji jarak Tukey, distribusi lambda Tukey, uji Tukey dari aditivitas dan lemma Tukey semua menanggung nama-Nya. Dia juga pencipta beberapa metode yang kurang dikenal seperti trimean dan median-median line, alternatif mudah untuk regresi linier.
Pada tahun 1974, ia mengembangkan, dengan Jerome H. Friedman, konsep mengejar proyeksi.
Praktek statistik
Dia juga memberikan kontribusi untuk praktek statistik dan mengartikulasikan perbedaan penting antara eksplorasi analisis data dan analisis data konfirmasi, percaya bahwa banyak metodologi statistik ditempatkan terlalu besar penekanan pada yang terakhir.
Meskipun ia percaya pada utilitas memisahkan dua jenis analisis, ia menunjukkan bahwa kadang-kadang, terutama dalam ilmu pengetahuan alam, ini adalah bermasalah dan disebut situasi seperti ilmu nyaman.
Istilah statistik
Tukey diciptakan istilah statistik banyak yang telah menjadi bagian dari penggunaan umum, tetapi dua coinages paling terkenal dikaitkan dengannya berhubungan dengan ilmu komputer.
Ketika bekerja dengan John von Neumann pada desain komputer awal, Tukey memperkenalkan kata "bit" sebagai kontraksi dari "digit biner". Istilah "bit" pertama kali digunakan dalam sebuah artikel oleh Claude Shannon pada tahun 1948.
Istilah "perangkat lunak", yang Paulus Niquette mengklaim ia menciptakan pada tahun 1953, pertama kali digunakan di cetak oleh Tukey dalam sebuah artikel di American Bulanan matematika tahun 1958, dan dengan demikian beberapa atribut istilah kepadanya. Itu 1958 penggunaan pertama dan atribusi dipertanyakan, mengingat bahwa Prosiding Simposium Nasional Kedua di Quality Control dan Keandalan dalam Elektronika: Washington, DC, 09-10 Januari 1956, diakses pada Hathi Trust, berisi terjadinya lunak jangka .
Tanda kutip
Jika kita butuh saran singkat dari apa eksplorasi analisis data, saya akan menyarankan bahwa
Ini adalah sikap DAN
Sebuah fleksibilitas DAN
Beberapa kertas grafik (atau transparansi, atau keduanya).
Tidak ada katalog teknik dapat menyampaikan kesediaan untuk mencari apa yang dapat dilihat, apakah atau tidak diantisipasi. Namun ini adalah inti dari eksplorasi analisis data. Grafik kertas - dan transparansi - berada di sana, bukan sebagai suatu teknik, melainkan sebagai pengakuan bahwa mata-gambar memeriksa adalah penemu terbaik yang kita miliki dari sesuatu yang tak terduga.
AD Gordon ditawarkan berikut ringkasan prinsip Tukey untuk praktek statistik:
... kegunaan dan keterbatasan statistik matematika, pentingnya memiliki metode analisis statistik yang kuat untuk pelanggaran asumsi yang mendasari penggunaannya, kebutuhan untuk mengumpulkan pengalaman perilaku spesifik metode analisis dalam rangka memberikan panduan tentang penggunaan; pentingnya membiarkan kemungkinan data yang mempengaruhi pilihan metode yang mereka dianalisis, kebutuhan untuk statistik untuk menolak peran 'wali kebenaran terbukti', dan untuk menolak upaya untuk menyediakan sekali-untuk-semua solusi dan rapi atas -unifications subjek, sifat iteratif analisis data, implikasi dari peningkatan daya, ketersediaan dan murahnya fasilitas komputasi, pelatihan statistik.
Jauh lebih baik jawaban perkiraan atas pertanyaan yang tepat, yang sering kabur, dari satu jawaban yang tepat untuk pertanyaan yang salah, yang selalu dapat dibuat tepat.
Sekali statistik waktu hanya dieksplorasi. Kemudian mereka belajar untuk mengkonfirmasi persis - untuk mengkonfirmasi beberapa hal dengan tepat, masing-masing dalam keadaan yang sangat spesifik. Saat mereka menekankan konfirmasi yang tepat, teknik mereka pasti menjadi kurang fleksibel. Sambungan dari teknik yang paling digunakan dengan wawasan masa lalu melemah. Apa pun yang prosedur konfirmasi tidak secara eksplisit melekat itu mencela sebagai 'statistik deskriptif belaka', tidak peduli berapa banyak kita telah belajar dari itu.
Tidak ada data yang dapat ditampilkan dalam sebuah diagram lingkaran, yang tidak dapat ditampilkan LEBIH BAIK dalam beberapa jenis lain dari tabel.
Publikasi
Andrews, David F, Peter J Bickel, Frank R Hampel, Peter J Huber, WH Rogers & John W Tukey (1972). Perkiraan Kuat lokasi: survei dan uang muka. Princeton University Press. ISBN 0-691-08113-1. OCLC 369.963.
Basford, Kaye E & John W Tukey (1998). Analisis grafis dari data MULTIRESPON. Chapman & Hall / CRC. ISBN 0-8493-0384-2. OCLC 154.674.707.
Blackman, R & B John W Tukey (1959). Pengukuran spektrum daya dari sudut pandang teknik komunikasi. Dover Publications. ISBN 0-486-60507-8.
Cochran, William G, Frederick Mosteller & John W Tukey (1954). Masalah statistik laporan Kinsey pada perilaku seksual pada pria manusia. Jurnal dari Asosiasi Statistik Amerika.
Hoaglin, David C, Frederick Mosteller & John W Tukey (eds) (1983). Memahami Kuat dan Exploratory Data Analysis. Wiley. ISBN 0-471-09777-2. OCLC 8.495.063.
Hoaglin, David C, Frederick Mosteller & John W Tukey (eds) (1985). Menjelajahi Data Tabel, Tren dan Bentuk. Wiley. ISBN 0-471-09776-4. OCLC 11.550.398.
Hoaglin, David C, Frederick Mosteller & John W Tukey (eds) (1991). Dasar-dasar eksplorasi analisis varians. Wiley. ISBN 0-471-52735-1. OCLC 23.180.322.
Morganthaler, Stephan & John W Tukey (eds) (1991). Configural polysampling: rute untuk ketahanan praktis. Wiley. ISBN 0-471-52372-0. OCLC 22.381.036.
Mosteller, Frederick & John W Tukey (1977). Analisis data dan regresi: kursus kedua dalam statistik. Addison-Wesley. ISBN 0-201-04854-X. OCLC 3.235.470.
Tukey, John W (1940). Konvergensi dan Keseragaman Topologi. Princeton University Press. ISBN 0-691-09568-X. OCLC 227.948.615.
Tukey, John W (1977). Exploratory Data Analysis. Addison-Wesley. ISBN 0-201-07616-0. OCLC 3.058.187.
Tukey, John W; Ian C Ross, Verna Bertrand (1973 -). Indeks statistik dan probabilitas. R & D Press. ISBN 0-88274-001-6. OCLC 745.715.
Kumpulan karya John W Tukey, diedit oleh William S Cleveland
Brillinger, David R (ed) (1984). Volume I: Time series, 1949-1964. Wadsworth. ISBN 0-534-03303-2. OCLC 10.998.116.
Brillinger, David R (ed) (1985). Volume II: Time series, 1965-1984. Wadsworth. ISBN 0-534-03304-0. OCLC 159.731.367.
Jones, Lyle V (ed) (1985). Volume III: Falsafah dan analisis data, 1949-1964. Wadsworth & Brooks / Cole. ISBN 0-534-03305-9. OCLC 159.731.367.
Jones, Lyle V (ed) (1986). Volume IV: Falsafah dan analisis data, 1965-1986. Wadsworth & Brooks / Cole. ISBN 0-534-05101-4. OCLC 165.832.503.
Cleveland, William S (ed) (1988). Volume V: Graphics, 1965-1985. Wadsworth & Brooks / Cole. ISBN 0-534-05102-2. OCLC 230.023.465.
Mallows, Colin L (ed) (1990). Volume VI: Lebih matematika, 1938-1984. Wadsworth & Brooks / Cole. ISBN 0-534-05103-0. OCLC 232.966.724.
Cox, David R (ed) (1992). Volume VII: Faktorial dan ANOVA, 1949-1962. Wadsworth & Brooks / Cole. ISBN 0-534-05104-9. OCLC 165.366.083.
Braun, Henry I (ed) (1994). Volume VIII: Beberapa perbandingan, 1949-1983. Chapman & Hall / CRC. ISBN 0-412-05121-4. OCLC 165.099.761.
John Tukey 's orang tua, Ralph H Tukey dan Adah M Tukey, John
telah diakui bahwa potensi besar sementara dia masih hanya anak, sehingga dia
diatur untuk mendapatkan pelayanan pendidikan di rumah daripada di sekolah. Hal
ini dilakukan karena orang tuanya sendiri adalah guru sekolah yang dilatih di
klasik. Bahkan ia Yohanes ibu Adah yang melakukan sebagian besar guru dari
anaknya, karena sebagai perempuan menikah, ia dilarang dari bekerja sebagai
guru di Massachusetts pada waktu itu. Hal ini juga merupakan pendidikan yang
sangat dipengaruhi Yohanes sepanjang hidupnya:
Pendidikan
mereka adalah metode untuk menanggapi permintaan John dengan memberikan
petunjuk dan menanyakan pertanyaan lebih lanjut daripada memberikan jawaban
langsung, suatu karakteristik yang diwarisi John dan digunakan di seluruh
karirnya.
John juga memiliki manfaat yang sangat baik perpustakaan umum di New Bedford yang dimiliki bahkan jurnal seperti Jurnal American Chemical Society dan Transaksi matematika dari Amerika Serikat. Dia dapat itu untuk mengambil pendidikan ke tingkat tinggi sebelum masuk universitas . Nya pendidikan formal mulai hanya ketika dia masuk Brown University di Providence, Rhode Island, untuk belajar matematika dan kimia.
Setelah Brown Universitas diberikan kepadanya Ijazah Sarjana Muda Kimia di 1936 dan Magister dalam kimia pada tahun berikutnya, Tukey pergi ke Princeton University di 1937 dan berminat untuk belajar untuk doktor dalam kimia. Bahkan ia belajar matematika dan kimia keduanya di tahun pertama tetapi telah kecewa Princeton menemukan bahwa dia tidak memungkinkan untuk bertindak sebagai asisten laboratorium kimia seperti dia telah dilakukan di Brown. Pada waktu selama beberapa tahun ini dia membuat kelancaran transisi dari kimia untuk matematika dan ikut ujian kualifikasi PhD dalam matematika pada tahun 1938. Tukey penelitian ini diawasi oleh Lefschetz dan dia menerima dia doktor di tahun 1939 untuk disertasi Denumerability di topologi yang diterbitkan tahun 1940 sebagai Convergence dan keseragaman dalam topologi. Dia telah tiga makalah telah dipublikasikan sebelum ia telah diberikan dan doktor, setelah lulus, ia diangkat sebagai pengajar di Princeton.
Eksternal,
ada untuk memainkan peran penting dalam arah Tukey's karir terutama akibat dia
bergabung dalam Pengendalian Kebakaran Penelitian kantor untuk berkontribusi
terhadap upaya perang. Ini judul Mei membingungkan pembaca modern untuk
penelitian tidak berurusan dengan 'api' sebagai dalam pembakaran, tetapi 'api'
sebagai studi pada testing. Pekerjaan yang terlibat di sini dan statistik Tukey
dengan cepat menemukan pekerjaan sangat banyak untuk kesukaan dia:
Kepala
sekolah ada masalah matematika, melibatkan ilmu balistik, dan artileri meriam
kontrol, rentang menemukan, menghitung lead untuk pindah sasaran dan
sebagainya. ... ada saran ia mungkin
terlibat dalam kode melanggar.
Terdapat statistik lain di Princeton, juga memberikan kontribusi terhadap upaya perang, khususnya Wilks dan Cochran, dan Tukey segera mulai bertukar ide dengan orang-orang ini.
Ketika
Perang Dunia II berakhir pada 1945 Wilks, dengan waktu ini tentang Tukey's
statistik bakat luar biasa, dia ditawarkan sebuah statistik di dalam departemen
matematika di Princeton. Namun satu pos tidak cukup untuk menyerap energi dan
itu, juga di 1945, Tukey bergabung dengan AT & T Bell Laboratories di mana
temannya termasuk Shewhart, Hamming dan Shannon. Dia juga yang menghabiskan
waktu jumlah besar di Washington pada pemerintah bisnis. Hanya workaholic
seperti Tukey dapat diputar tersebut memiliki peran besar dalam semua tiga
kegiatan tersebut.
Di tahun 1950 Tukey menikah Elizabeth Louise RAPP yang, setelah perkawinan mereka, membuat karir sebagai barang antik agen. Mereka tidak memiliki anak tetapi Elizabeth's saudara Paulis telah menikah dengan Frank Anscombe yang juga seorang ahli statistik yang kadang-kadang bekerjasama dengan Tukey. Paulis dan Frank ada empat anak-anak yang sering pengunjung ke Tukey rumah. Thompson menulis:
John Tukey
ushered di era baru dari statistik. Dia
mempertanyakan Fisherian asumsi yang biasa ketidakpastian dan memberikan kami
masukan ke dalam penyimpangan dari dunia nyata. Hidupnya's kerja terdiri
dari sebagian besar menemukan cara untuk mengumpulkan dan menganalisa data.
Seperti dia pelajari, dia senang hati kami diajarkan dengan cara
menyelesaikan sebuah dunia di mana tidak ada ketidakpastian tetapi hanya
ketidakpastian tentang ketidakpastian. Sebagai beberapa akademik, John
dan Elizabeth Tukey mencapai standar tertinggi untuk hikmat dan baik.
Tukey pertama kontribusi besar untuk statistik menggunakan teknik pengenalan modern untuk perkiraan Spectra waktu seri. EJ hannan, meninjau Tukey's paper tentang topik ini menulis:
Mereka
menunjukkan sikap yang luar biasa keseragaman sifat yang realistis pengakuan
terhadap kompleksitas situasi, yang ragu-ragu akibat dari asymptotic teori,
penggunaan teknik statistik standar sebagai patokan daripada menyediakan (berkata)
tepat interval keyakinan, terus menerus pertanyaan asumsi, penekanan pada aspek
komputer, penekanan pada cara menyampaikan analisis, presentasi ini di biasa
dengan cara utama pengguna daripada di dalam cara mengadopsi matematika
perawatan, awal pengakuan terhadap kualitas unggul dari perangkat digital untuk
tujuan umum (dibandingkan dengan perangkat analog) dan mempunyai pesona dengan
kata-kata dan frasa baru, yang sebagian telah menjadi terbukti. Ada, tentu saja, juga pengenalan metode baru,
beberapa yang telah memberikan sumbangsih yang penting. Termasuk metode
untuk memperkirakan Spectra, Spectra lebih tinggi dari saat, kompleks
demodulation, metode untuk menentukan besarnya dan tanda awal impulses diamati
setelah pengiriman melalui (lebih kurang) tetap linear sistem dan analisis
Fourier logaritma dari spektral untuk memperkirakan Echoes mengetahui.
Tukey itu dijelaskan dalam pembangunan jalan itu ia berpikir tentang subyek dalam pengenalan kepada karya masa depan data analisis diterbitkan pada tahun 1962:
Untuk waktu
yang lama saya menduga bahwa saya adalah seorang ahli statistik, yang tertarik
pada kesimpulan dari khusus ke umum. Tetapi
saya tercinta matematika statistik berkembang, telah menyebabkan saya untuk
heran dan keraguan. Dan ketika saya telah pondered tentang mengapa
teknik tersebut sebagai spektrum analisis rangkaian waktu sehingga telah
terbukti berguna, telah menjadi jelas bahwa mereka 'berurusan dengan fluktuasi'
adalah aspek, dalam banyak situasi, kurang penting dibandingkan dengan aspek
yang sudah diperlukan untuk menangani secara efektif dengan mudah kasus yang
sangat luas di mana data fluktuasi tidak akan lagi menjadi masalah. Semua
di semua, Aku datang untuk merasa bahwa saya adalah bunga di pusat data analisis
...
Pada tahun 1965, di sebuah kertas dengan JW Cooley dipublikasikan di Matematika dari Perhitungan, dia memperkenalkan penting Algoritma Transformasi Fourier cepat. Untuk banyak orang ini akan menjadi pekerjaan yang terbaik untuk diketahui. Namun, hanya sebagian kecil dari sejumlah besar daerah dengan kontribusi signifikan yang dibuat dia. Karyanya pada falsafah dan statistik dari penelitian ini diringkas oleh AD Gordon meliputi topik:
... yang kegunaan dan keterbatasan matematis
statistik; akan pentingnya metode analisis statistik yang kuat untuk
pelanggaran terhadap asumsi yang melandasi mereka menggunakan; yang perlu
kumpulkan pengalaman tingkah laku spesifik metode analisis dalam rangka untuk
memberikan pembinaan tentang penggunaan layanan; pentingnya memungkinkan data
yang kemungkinan's mempengaruhi pilihan metode yang mereka analisis; kebutuhan
untuk statistik untuk menolak peran 'wali terbukti dari kebenaran', dan untuk
menolak upaya untuk menyediakan sekali-untuk-semua rapi dan solusi atas -unifications
dari subjek yang berulang alam data analisis; implikasi dari peningkatan daya,
dan ketersediaan fasilitas murahnya komputasi; pelatihan dari statistik.
Tukey dia menghabiskan seluruh karir di Princeton. Dia menjadi direktur yang baru didirikan Statistik Research Group ketika didirikan pada 1956. Dia pertama Ketua Departemen Statistik yang didirikan di Princeton pada 1965, memegang posisi untuk empat tahun. Di AT & T Bell Laboratories, Tukey telah terlibat dalam pengembangan elektronik komputer. Dia memegang posisi senior di Departemen Statistik dan Analisis Data dari waktu didirikan di AT & T di tahun 1952.
Tukey juga
dibuat besar kontribusi untuk analisis yang berbeda dan masalah pembuatan
serentak kesimpulan tentang sekumpulan parameter nilai dari satu percobaan.
Banyak dari makalah yang ditulis dengan orang lain dan salah seorang
co-penulis, M Mosteller menulis di:
John suka
bekerja dengan orang lain, dan memiliki banyak kenikmatan dalam berpartisipasi
dalam genius. Berbagai
dan luasnya tentang tandai itu. Dia berhasil bekerja pada kedua-besar
dan kecil dan masalah pada kedua masalah teori dan praktis. ... Dia
selalu ingin menanggapi pertanyaan baru, dan ia memberi murah dari waktu dan
ide.
Tukey's lecturing gaya ini tidak biasa. McCullagh dalam menjelaskan Tukey memberikan kuliah di Imperial College, London, pada tahun 1977:
Tukey ambled
naik di podium, beruang yang besar dari seorang laki-laki berpakaian longgar
dan celana hitam kemeja dirajut. Ini
mungkin sekali telah pasangan yang cocok tetapi ketinggalan jaman itu yang
terdengar untuk kirim. ... Dengan hati-hati dan sengaja daftar
judul telah chalked di papan tulis. Kata datang juga, tidak banyak,
seperti kelebihan bidang, disampaikan pada unfaltering memperlambat laju. ...
Ketika itu lengkap, Tukey beralih ke wajah para penonton dan mimbar ... "Komentar,
pertanyaan, saran?" ia meminta pemirsa ... Karena dia
menunggu jawaban, ia clambered ke atas mimbar dan beliau manoeuvred sampai
duduk sila menghadap penonton. ... Kami di khalayak Sabtu seperti
penonton di kebun binatang menunggu untuk menanggung besar untuk memindahkan
atau berkata sesuatu. Tetapi beruang besar yang akan muncul melakukan
hal yang sama, dan merasa tidak nyaman.
McCullagh menunjukkan bahwa:
... Tukey menyukai untuk bermain game dia cara untuk
membuat orang tebak sendiri untuk hal-hal yang dia sudah tahu. Apalagi,
ia menyukai yang memberikan dan mengambil suatu argumen, tetapi ia juga
diharapkan untuk itu berlaku, dan biasanya mereka lakukan.
Tukey telah
banyak diberikan tanda kehormatan atas kontribusi yang beredar. Termasuk SS
Wilks penghargaan dari Asosiasi Statistik Amerika
di tahun 1965, Amerika Serikat National Medal of Science pada tahun 1973 dan
Medali dari Hormatilah dari Institut Jurutera Elektrik Elektronik dan pada
tahun 1982.
Dia sedikit waktu untuk kepentingan di luar keahlian ilmiah yang berlaku itu, tetapi ia menikmati fiksi ilmiah dan membaca novel misteri. Karyanya membawanya ke banyak daerah tak terduga seperti hal memperkaya uranium, bekerja pada pengembangan pesawat mata-mata U2, dan ia mewakili Amerika di konferensi senjata nuklir di Jenewa pada 1959. Selain itu pernah menjabat pada panel banyak laporan tentang isu-isu seperti lingkungan dan sensus.
Pada
tahun 1965,
Drs. James W. Cooley dan John W. Tukey (IEEE 1982 Medal of Honor penerima) menerbitkan sebuah makalah yang
menjelaskan
Fast
Fourier
Transform (FFT) algoritma, yang menyebabkan ledakan dalam pemrosesan
sinyal
digital. Penelitian tengara mereka menawarkan perbaikan besar dalam kecepatan pemrosesan dan memainkan peran penting dalam revolusi digital. Hari ini, pemrosesan sinyal
digital
merupakan
bagian integral dari komunikasi, pengolahan informasi, elektronik konsumen, sistem kontrol, radar dan sonar, diagnosa medis, seismologi, instrumentasi ilmiah dan banyak lagi.
Setelah publikasi kertas, Dr Cooley bertekad untuk membantu orang lain memahami algoritma dan penggunaannya. Sementara di IBM Watson Research Center di Yorktown Heights, NY, ia membuat kontribusi yang tak terhitung jumlahnya untuk promosi FFT, termasuk melayani selama bertahun-tahun di Komite Signal Processing Digital Akustik IEEE, Pidato, dan Signal Processing Society (sekarang IEEE Signal Processing Masyarakat). Nya IEEE Arden House Lokakarya juga meletakkan dasar bagi IEEE Signal Processing Society.
Setelah pensiun dari IBM pada tahun 1991, ia bergabung dengan Departemen Teknik Elektro di University of Rhode Island. Hari ini ia menjabat URI sebagai tambahan dan terus berpartisipasi dalam proyek-proyek penelitian dalam deteksi sinyal.
Sebuah Fellow IEEE dan anggota National Academy of Engineering, Dr Cooley menerima beberapa penghargaan Masyarakat IEEE dan IEEE Centennial medali.
Setelah publikasi kertas, Dr Cooley bertekad untuk membantu orang lain memahami algoritma dan penggunaannya. Sementara di IBM Watson Research Center di Yorktown Heights, NY, ia membuat kontribusi yang tak terhitung jumlahnya untuk promosi FFT, termasuk melayani selama bertahun-tahun di Komite Signal Processing Digital Akustik IEEE, Pidato, dan Signal Processing Society (sekarang IEEE Signal Processing Masyarakat). Nya IEEE Arden House Lokakarya juga meletakkan dasar bagi IEEE Signal Processing Society.
Setelah pensiun dari IBM pada tahun 1991, ia bergabung dengan Departemen Teknik Elektro di University of Rhode Island. Hari ini ia menjabat URI sebagai tambahan dan terus berpartisipasi dalam proyek-proyek penelitian dalam deteksi sinyal.
Sebuah Fellow IEEE dan anggota National Academy of Engineering, Dr Cooley menerima beberapa penghargaan Masyarakat IEEE dan IEEE Centennial medali.
Cooley–Tukey
FFT algorithm
The Cooley-Tukey algoritma, dinamai J.W.
Cooley dan John Tukey, adalah yang paling umum cepat Fourier transform (FFT) algoritma.
Ini kembali mengungkapkan transformasi Fourier diskrit (DFT) dari komposit ukuran
sewenang-wenang N = N1N2 dalam hal DFTs kecil ukuran N1 dan N2, rekursif, dalam
rangka untuk mengurangi waktu komputasi untuk O (N log N) untuk sangat-komposit
N (nomor halus). Karena pentingnya algoritma, varian tertentu dan gaya implementasi
telah menjadi dikenal dengan nama mereka sendiri, seperti yang dijelaskan di
bawah ini.
Karena algoritma Cooley-Tukey istirahat DFT ke DFTs kecil, dapat dikombinasikan secara sewenang-wenang dengan algoritma lain untuk DFT. Misalnya, Rader atau Bluestein Algoritma dapat digunakan untuk menangani faktor prima besar yang tidak bisa diurai oleh Cooley-Tukey, atau algoritma prime-faktor dapat dimanfaatkan untuk lebih efisien dalam memisahkan faktor relatif prima.
Lihat juga cepat Fourier transform untuk informasi tentang algoritma lain FFT, spesialisasi untuk data nyata dan / atau simetris, dan akurasi dalam menghadapi terbatas presisi floating-point.
Karena algoritma Cooley-Tukey istirahat DFT ke DFTs kecil, dapat dikombinasikan secara sewenang-wenang dengan algoritma lain untuk DFT. Misalnya, Rader atau Bluestein Algoritma dapat digunakan untuk menangani faktor prima besar yang tidak bisa diurai oleh Cooley-Tukey, atau algoritma prime-faktor dapat dimanfaatkan untuk lebih efisien dalam memisahkan faktor relatif prima.
Lihat juga cepat Fourier transform untuk informasi tentang algoritma lain FFT, spesialisasi untuk data nyata dan / atau simetris, dan akurasi dalam menghadapi terbatas presisi floating-point.
Sejarah
Algoritma ini, termasuk aplikasi rekursif nya, diciptakan sekitar 1805 oleh Carl Friedrich Gauss, yang menggunakannya untuk interpolasi lintasan asteroid Pallas dan Juno, namun karyanya tidak diakui secara luas (yang diterbitkan hanya anumerta dan neo-Latin). Gauss tidak menganalisis waktu komputasi asimtotik, namun. Berbagai bentuk yang terbatas juga ditemukan kembali beberapa kali selama abad 19 dan awal abad ke-20. FFTs menjadi populer setelah James Cooley IBM dan John Tukey dari Princeton menerbitkan sebuah makalah pada tahun 1965 menciptakan kembali algoritma dan menjelaskan bagaimana melakukan hal itu dengan nyaman pada komputer.
Tukey dikabarkan datang dengan ide selama pertemuan dari presiden komite penasihat AS membahas cara-cara untuk mendeteksi tes-senjata nuklir di Uni Soviet. Peserta lain pada pertemuan itu, Richard Garwin IBM, mengakui potensi metode dan menempatkan Tukey berhubungan dengan Cooley, yang diterapkan untuk masalah yang berbeda (dan kurang-rahasia): menganalisis data kristalografi 3d (lihat juga: FFTs multidimensi) . Cooley dan Tukey kemudian menerbitkan kertas bersama mereka, dan adopsi luas diikuti dengan cepat.
Fakta bahwa Gauss telah dijelaskan algoritma yang sama (meskipun tanpa menganalisa biaya asimtotik nya) tidak menyadari sampai beberapa tahun setelah Cooley dan Tukey 1965 kertas. Kertas mereka dikutip sebagai inspirasi hanya bekerja oleh IJ Baik pada apa yang sekarang disebut FFT algoritma prime-faktor (PFA), algoritma meskipun Baik pada awalnya keliru dianggap setara dengan algoritma Cooley-Tukey, itu cepat menyadari bahwa PFA adalah algoritma sangat berbeda (hanya bekerja untuk ukuran yang memiliki faktor relatif prima dan mengandalkan Teorema Remainder Cina, seperti dukungan untuk berbagai ukuran komposit di Cooley-Tukey).
Algoritma ini, termasuk aplikasi rekursif nya, diciptakan sekitar 1805 oleh Carl Friedrich Gauss, yang menggunakannya untuk interpolasi lintasan asteroid Pallas dan Juno, namun karyanya tidak diakui secara luas (yang diterbitkan hanya anumerta dan neo-Latin). Gauss tidak menganalisis waktu komputasi asimtotik, namun. Berbagai bentuk yang terbatas juga ditemukan kembali beberapa kali selama abad 19 dan awal abad ke-20. FFTs menjadi populer setelah James Cooley IBM dan John Tukey dari Princeton menerbitkan sebuah makalah pada tahun 1965 menciptakan kembali algoritma dan menjelaskan bagaimana melakukan hal itu dengan nyaman pada komputer.
Tukey dikabarkan datang dengan ide selama pertemuan dari presiden komite penasihat AS membahas cara-cara untuk mendeteksi tes-senjata nuklir di Uni Soviet. Peserta lain pada pertemuan itu, Richard Garwin IBM, mengakui potensi metode dan menempatkan Tukey berhubungan dengan Cooley, yang diterapkan untuk masalah yang berbeda (dan kurang-rahasia): menganalisis data kristalografi 3d (lihat juga: FFTs multidimensi) . Cooley dan Tukey kemudian menerbitkan kertas bersama mereka, dan adopsi luas diikuti dengan cepat.
Fakta bahwa Gauss telah dijelaskan algoritma yang sama (meskipun tanpa menganalisa biaya asimtotik nya) tidak menyadari sampai beberapa tahun setelah Cooley dan Tukey 1965 kertas. Kertas mereka dikutip sebagai inspirasi hanya bekerja oleh IJ Baik pada apa yang sekarang disebut FFT algoritma prime-faktor (PFA), algoritma meskipun Baik pada awalnya keliru dianggap setara dengan algoritma Cooley-Tukey, itu cepat menyadari bahwa PFA adalah algoritma sangat berbeda (hanya bekerja untuk ukuran yang memiliki faktor relatif prima dan mengandalkan Teorema Remainder Cina, seperti dukungan untuk berbagai ukuran komposit di Cooley-Tukey).
Radix-2 DIT kasus
Sebuah radix-2 penipisan-in-time (DIT) FFT adalah bentuk yang paling sederhana dan paling umum dari algoritma Cooley-Tukey, meskipun sangat optimal implementasi Cooley-Tukey biasanya menggunakan bentuk lain dari algoritma seperti yang dijelaskan di bawah ini. Radix-2 DIT membagi DFT berukuran N menjadi dua DFTs interleaved (maka nama "radix-2") dengan ukuran N / 2 dengan setiap tahap rekursif.
Transformasi Fourier diskrit (DFT) didefinisikan dengan rumus:
Sebuah radix-2 penipisan-in-time (DIT) FFT adalah bentuk yang paling sederhana dan paling umum dari algoritma Cooley-Tukey, meskipun sangat optimal implementasi Cooley-Tukey biasanya menggunakan bentuk lain dari algoritma seperti yang dijelaskan di bawah ini. Radix-2 DIT membagi DFT berukuran N menjadi dua DFTs interleaved (maka nama "radix-2") dengan ukuran N / 2 dengan setiap tahap rekursif.
Transformasi Fourier diskrit (DFT) didefinisikan dengan rumus:
di mana
k adalah
integer berkisar dari 0 sampai N-1.
Radix-2 DIT pertama menghitung DFTs dari input bahkan-diindeks x_ {2m} \ (x_0, x_2, \ ldots, x_ {N-2}) dan input aneh-diindeks x_ {2m +1} \ (x_1 , x_3, \ ldots, x_ {N-1}), dan kemudian menggabungkan dua hasil untuk menghasilkan DFT dari seluruh urutan. Ide ini kemudian dapat dilakukan secara rekursif untuk mengurangi keseluruhan runtime ke O (N log N). Formulir ini disederhanakan mengasumsikan bahwa N adalah kekuatan dua, karena jumlah titik sampel N biasanya dapat dipilih secara bebas oleh aplikasi, hal ini sering tidak pembatasan penting.
Algoritma Radix-2 DIT menata kembali DFT dari fungsi x_n menjadi dua bagian: jumlah atas indeks genap n = {} 2m dan jumlah di atas indeks ganjil n = {2m +1}:
Radix-2 DIT pertama menghitung DFTs dari input bahkan-diindeks x_ {2m} \ (x_0, x_2, \ ldots, x_ {N-2}) dan input aneh-diindeks x_ {2m +1} \ (x_1 , x_3, \ ldots, x_ {N-1}), dan kemudian menggabungkan dua hasil untuk menghasilkan DFT dari seluruh urutan. Ide ini kemudian dapat dilakukan secara rekursif untuk mengurangi keseluruhan runtime ke O (N log N). Formulir ini disederhanakan mengasumsikan bahwa N adalah kekuatan dua, karena jumlah titik sampel N biasanya dapat dipilih secara bebas oleh aplikasi, hal ini sering tidak pembatasan penting.
Algoritma Radix-2 DIT menata kembali DFT dari fungsi x_n menjadi dua bagian: jumlah atas indeks genap n = {} 2m dan jumlah di atas indeks ganjil n = {2m +1}:
Satu dapat faktor pengali umum e ^ {-
\ frac {2 \ pi i} {N}} k dari jumlah kedua, seperti yang ditunjukkan pada persamaan
di bawah ini. Maka jelas bahwa dua jumlah adalah DFT dari bahkan-diindeks bagian
x_ {} 2m dan DFT aneh-diindeks bagian x_ {2m +1} dari fungsi x_n. Menunjukkan DFT
dari input Bahkan-diindeks x_ {2m} oleh E_k dan DFT dari input Odd-diindeks x_ {2m
+ 1} oleh O_k dan kita memperoleh:
Namun, ini DFTs kecil memiliki panjang N / 2, jadi kita perlu menghitung hanya N / 2 output: berkat sifat periodisitas DFT, output untuk N / 2 \ leq k <N dari DFT panjang N / 2 identik dengan output untuk 0 \ leq k <N / 2. Artinya, E_ {k + N / 2} = E_k dan O_ {k + N / 2} = O_k. Tahap Faktor \ exp [-2 \ pi ik / N] (disebut faktor bermalas) mematuhi hubungan: \ exp [-2 \ pi i (k + N / 2) / N] = e ^ {- \ pi i } \ exp [-2 \ pi ik / N] = - \ exp [-2 \ pi ik / N], membalik tanda O_ {k + N / 2} istilah. Dengan demikian, seluruh DFT dapat dihitung sebagai berikut:
Hasil
ini, mengungkapkan DFT panjang N rekursif dalam hal dua DFTs ukuran N / 2,
adalah inti dari radix-2 DIT Fast Fourier Transform. Algoritma
keuntungan kecepatan dengan kembali menggunakan hasil perhitungan antara untuk
menghitung beberapa output DFT. Perhatikan
bahwa output akhir yang diperoleh oleh + / - kombinasi E_k dan O_k \ exp (-2 \
pi ik / N), yang hanya merupakan ukuran-2 DFT (kadang-kadang disebut kupu-kupu
dalam konteks ini), ketika hal ini umum untuk
tinggal akar yang lebih besar di bawah ini, ukuran-2 DFT digantikan oleh DFT
lebih besar (yang dengan sendirinya dapat dievaluasi dengan FFT).
Diagram aliran data untuk N = 8: a penipisan-in-time radix-2 FFT istirahat panjang-N DFT menjadi dua panjang-N / 2 DFTs diikuti oleh tahap menggabungkan terdiri dari banyak ukuran-2 DFTs disebut "kupu-kupu" operasi ( disebut demikian karena dari bentuk diagram aliran data).
Proses ini adalah contoh dari teknik umum membagi dan menaklukkan algoritma, dalam banyak implementasi tradisional, bagaimanapun, rekursi eksplisit dihindari, dan bukannya satu melintasi pohon komputasi dalam mode breadth-first.
Atas kembali ekspresi dari ukuran-N DFT sebagai dua ukuran-N / 2 DFTs kadang-kadang disebut lemma Danielson-Lanczos, karena identitas itu dicatat oleh kedua penulis pada tahun 1942 [7] (dipengaruhi oleh Runge ini 1903 pekerjaan [2 ]). Mereka menerapkan lemma mereka dalam "mundur" mode rekursif, berulang dua kali lipat ukuran DFT sampai transformasi spektrum konvergensi (meskipun mereka tampaknya tidak menyadari linearithmic [yaitu, urutan N log N] kompleksitas asimtotik mereka telah tercapai). Pekerjaan Danielson-Lanczos mendahului ketersediaan luas komputer dan perhitungan tangan yang diperlukan (mungkin dengan alat bantu mekanis seperti mesin hitung), mereka melaporkan perhitungan waktu 140 menit untuk ukuran 64-DFT operasi masukan nyata untuk 3-5 signifikan digit. Cooley dan Tukey 1965 kertas melaporkan waktu berjalan 0,02 menit untuk DFT ukuran-2048 kompleks pada IBM 7094 (mungkin di 36-bit tunggal presisi, ~ 8 digit). [3] Rescaling waktu dengan jumlah operasi, ini sesuai kira-kira dengan faktor speedup sekitar 800.000. (Untuk menempatkan waktu untuk perhitungan tangan dalam perspektif, 140 menit untuk ukuran 64 sesuai dengan rata-rata hampir 16 detik per operasi floating-point, sekitar 20% di antaranya adalah perkalian.)
Diagram aliran data untuk N = 8: a penipisan-in-time radix-2 FFT istirahat panjang-N DFT menjadi dua panjang-N / 2 DFTs diikuti oleh tahap menggabungkan terdiri dari banyak ukuran-2 DFTs disebut "kupu-kupu" operasi ( disebut demikian karena dari bentuk diagram aliran data).
Proses ini adalah contoh dari teknik umum membagi dan menaklukkan algoritma, dalam banyak implementasi tradisional, bagaimanapun, rekursi eksplisit dihindari, dan bukannya satu melintasi pohon komputasi dalam mode breadth-first.
Atas kembali ekspresi dari ukuran-N DFT sebagai dua ukuran-N / 2 DFTs kadang-kadang disebut lemma Danielson-Lanczos, karena identitas itu dicatat oleh kedua penulis pada tahun 1942 [7] (dipengaruhi oleh Runge ini 1903 pekerjaan [2 ]). Mereka menerapkan lemma mereka dalam "mundur" mode rekursif, berulang dua kali lipat ukuran DFT sampai transformasi spektrum konvergensi (meskipun mereka tampaknya tidak menyadari linearithmic [yaitu, urutan N log N] kompleksitas asimtotik mereka telah tercapai). Pekerjaan Danielson-Lanczos mendahului ketersediaan luas komputer dan perhitungan tangan yang diperlukan (mungkin dengan alat bantu mekanis seperti mesin hitung), mereka melaporkan perhitungan waktu 140 menit untuk ukuran 64-DFT operasi masukan nyata untuk 3-5 signifikan digit. Cooley dan Tukey 1965 kertas melaporkan waktu berjalan 0,02 menit untuk DFT ukuran-2048 kompleks pada IBM 7094 (mungkin di 36-bit tunggal presisi, ~ 8 digit). [3] Rescaling waktu dengan jumlah operasi, ini sesuai kira-kira dengan faktor speedup sekitar 800.000. (Untuk menempatkan waktu untuk perhitungan tangan dalam perspektif, 140 menit untuk ukuran 64 sesuai dengan rata-rata hampir 16 detik per operasi floating-point, sekitar 20% di antaranya adalah perkalian.)
Diagram aliran data untuk N = 8: a penipisan-in-time
radix-2 FFT istirahat panjang-N DFT menjadi dua panjang-N / 2 DFTs diikuti oleh
tahap menggabungkan terdiri dari banyak ukuran-2 DFTs disebut "kupu-kupu"
operasi (disebut demikian karena dari bentuk diagram aliran data).
Pseudocode
Dalam pseudocode, proses di atas dapat ditulis:
Dalam pseudocode, proses di atas dapat ditulis:
X0,...,N−1 ← ditfft2(x, N, s): DFT of (x0, xs,
x2s, ..., x(N-1)s):
if N
= 1 then
X0
← x0
trivial size-1 DFT
base case
else
X0,...,N/2−1
← ditfft2(x, N/2, 2s) DFT of (x0, x2s,
x4s, ...)
XN/2,...,N−1
← ditfft2(x+s, N/2, 2s) DFT of (xs, xs+2s,
xs+4s, ...)
for k
= 0 to N/2−1 combine DFTs of two halves
into full DFT:
t ← Xk
Xk
← t + exp(−2πi k/N) Xk+N/2
Xk+N/2
← t − exp(−2πi k/N) Xk+N/2
endfor
endif
Di sini, ditfft2 (x, N, 1),
menghitung X = DFT (x) out-of-tempat oleh FFT radix-2 Dit, di mana N adalah
kekuatan integer 2 dan s = 1 adalah langkah dari input x array. x + s menunjukkan
array dimulai dengan xs.
(Hasilnya dalam urutan yang benar di X dan tidak lebih sedikit-pembalikan permutasi diperlukan, kebutuhan sering disebutkan dari tahap-bit pembalikan terpisah hanya muncul untuk algoritma di-tempat tertentu, seperti yang dijelaskan di bawah ini.)
Kinerja tinggi implementasi FFT membuat banyak modifikasi pada implementasi algoritma tersebut dibandingkan dengan ini pseudocode sederhana. Misalnya, satu dapat menggunakan kasus dasar lebih besar dari N = 1 untuk amortisasi overhead dari rekursi, faktor bermalas \ exp [-2 \ pi ik / N] dapat precomputed, dan sisa akar yang lebih besar sering digunakan untuk alasan tembolok; ini dan optimasi lain bersama-sama dapat meningkatkan kinerja dengan urutan besarnya atau lebih. [8] (dalam banyak implementasi buku rekursi depth-first dihilangkan seluruhnya dalam mendukung nonrecursive pendekatan luas-pertama, meskipun rekursi depth-first telah berpendapat memiliki lokalitas memori yang lebih baik.) Beberapa ide ini dijelaskan secara lebih rinci di bawah.
(Hasilnya dalam urutan yang benar di X dan tidak lebih sedikit-pembalikan permutasi diperlukan, kebutuhan sering disebutkan dari tahap-bit pembalikan terpisah hanya muncul untuk algoritma di-tempat tertentu, seperti yang dijelaskan di bawah ini.)
Kinerja tinggi implementasi FFT membuat banyak modifikasi pada implementasi algoritma tersebut dibandingkan dengan ini pseudocode sederhana. Misalnya, satu dapat menggunakan kasus dasar lebih besar dari N = 1 untuk amortisasi overhead dari rekursi, faktor bermalas \ exp [-2 \ pi ik / N] dapat precomputed, dan sisa akar yang lebih besar sering digunakan untuk alasan tembolok; ini dan optimasi lain bersama-sama dapat meningkatkan kinerja dengan urutan besarnya atau lebih. [8] (dalam banyak implementasi buku rekursi depth-first dihilangkan seluruhnya dalam mendukung nonrecursive pendekatan luas-pertama, meskipun rekursi depth-first telah berpendapat memiliki lokalitas memori yang lebih baik.) Beberapa ide ini dijelaskan secara lebih rinci di bawah.
Faktorisasi Umum
Langkah dasar dari Cooley-Tukey FFT untuk faktorisasi umum dapat dipandang sebagai ulang menafsirkan DFT 1d sebagai sesuatu seperti 2d DFT. The 1d array input panjang N = N1N2 dimodelkan sebagai 2d N1 × N2 matriks disimpan dalam urutan kolom-besar. Satu melakukan DFTs 1d kecil sepanjang arah N2 (arah non-contiguous), kemudian mengalikan dengan faktor fasa (faktor hiasan), dan akhirnya melakukan DFTs 1d sepanjang arah N1. Transposisi langkah dapat dilakukan di tengah, seperti yang ditunjukkan di sini, atau di awal atau akhir. Hal ini dilakukan secara rekursif untuk transformasi yang lebih kecil.
Secara umum, algoritma Cooley-Tukey rekursif kembali mengungkapkan DFT dari ukuran komposit N = N1N2 sebagai:
Lakukan DFTs N1 ukuran N2.
Kalikan dengan akar kompleks kesatuan yang disebut faktor bermalas.
Lakukan DFTs N2 ukuran N1.
Biasanya, baik N1 atau N2 merupakan faktor kecil (tidak selalu prima), disebut radix (yang bisa berbeda antara tahapan rekursi). Jika N1 adalah radix, itu disebut penipisan dalam waktu (Dit) algoritma, sedangkan jika N2 adalah radix, itu adalah penipisan di frekuensi (DIF, juga disebut algoritma Sande-Tukey). Versi yang disajikan di atas adalah algoritma radix-2 Dit, dalam ekspresi akhir, fase mengalikan transformasi aneh adalah faktor hiasan, dan + / - Kombinasi (kupu-kupu) dari transformasi genap dan ganjil adalah ukuran-2 DFT. (The radix itu DFT kecil kadang-kadang dikenal sebagai kupu-kupu, yang disebut karena bentuk diagram dataflow untuk radix-2 kasus.)
Ada banyak variasi lain pada algoritma Cooley-Tukey. Campur-radix implementasi menangani ukuran komposit dengan berbagai (biasanya kecil) faktor selain dua, biasanya (tetapi tidak selalu) dengan menggunakan O (N2) algoritma untuk kasus dasar utama rekursi [juga memungkinkan untuk mempekerjakan N log N algoritma untuk kasus dasar utama, seperti Rader atau Bluestein Algoritma]. Berpisah radix gabungan sisa akar 2 dan 4, mengeksploitasi fakta bahwa transformasi pertama radix 2 tidak memerlukan faktor hiasan, untuk mencapai apa yang lama dikenal count operasi aritmatika terendah untuk power-of-dua ukuran, meskipun variasi baru-baru ini mencapai bahkan menurunkan jumlah. (Pada komputer masa kini, kinerja lebih banyak ditentukan oleh cache dan pertimbangan pipa CPU daripada jumlah operasi yang ketat, baik dioptimalkan implementasi FFT sering menggunakan sisa akar yang lebih besar dan / atau hard-kode kasus dasar berubah dari ukuran yang signifikan.) Cara lain melihat algoritma Cooley-Tukey adalah bahwa hal itu kembali mengungkapkan ukuran N satu-dimensi DFT sebagai N1 N2 oleh dua dimensi DFT (ditambah twiddles), di mana matriks output dialihkan. Hasil bersih dari semua transposisi ini, untuk algoritma radix-2, sesuai dengan pembalikan bit dari masukan (DIF) atau output (DIT) indeks. Jika, daripada menggunakan kecil radix, yang mempekerjakan radix kira-kira √ N dan input / output eksplisit transposisi matriks, disebut algoritma empat langkah (atau enam langkah, tergantung pada jumlah transposisi), awalnya diusulkan untuk meningkatkan lokalitas memori, misalnya untuk optimasi tembolok atau operasi out-of-core, dan kemudian terbukti menjadi algoritma cache menyadari optimal.
General Cooley-Tukey faktorisasi menulis ulang indeks k dan n sebagai
masing-masing, di mana indeks ka na dan berlari dari 0 .. Na-1 (untuk 1 atau 2). Artinya, re-indeks input (n) dan output (k) sebagai N1 N2 oleh dua dimensi array dalam urutan kolom dan
baris-besar-besar, masing-masing; perbedaan antara indexings ini adalah transposisi,
seperti disebutkan di atas. Ketika ini kembali pengindeksan
disubstitusikan ke rumus DFT untuk nk, yang N_1 n_2 N_2 k_1 lintas jangka hilang (yang eksponensial adalah kesatuan), dan istilah yang
tersisa memberikan
Sewenang-wenang radix r (serta sisa akar campuran) dapat digunakan, seperti yang ditunjukkan oleh Cooley dan Tukey [3] serta Gauss (yang memberi contoh radix-3 dan radix-6 langkah). Cooley dan Tukey awalnya diasumsikan bahwa radix kupu-kupu yang dibutuhkan O (r2) pekerjaan dan karenanya diperhitungkan kompleksitas untuk radix r menjadi O (r2 N / r logrN) = O (N log2 (N) r/log2r), dari perhitungan nilai r/log2r untuk nilai-nilai integer r 2-12 optimal radix ditemukan menjadi 3 (bilangan bulat terdekat dengan e, yang meminimalkan r/log2r). Analisis ini adalah salah, namun: radix-kupu juga DFT dan dapat dilakukan melalui algoritma FFT di O (log r r) operasi, maka radix r sebenarnya membatalkan dalam kompleksitas O (log r (r) N / r logrN), dan r optimal ditentukan oleh pertimbangan yang lebih rumit. Dalam prakteknya, r cukup besar (32 atau 64) yang penting agar dapat secara efektif mengeksploitasi misalnya jumlah besar prosesor register pada prosesor modern, dan bahkan tak terbatas radix r = √ N juga mencapai O (N log N) kompleksitas dan memiliki kelebihan teoritis dan praktis untuk besar N seperti yang disebutkan di atas.
Data pemesanan ulang, sedikit pembalikan, dan
algoritma di tempat
Meskipun abstrak Cooley-Tukey faktorisasi DFT, di atas, berlaku dalam beberapa bentuk untuk semua implementasi dari algoritma, keragaman jauh lebih besar ada dalam teknik untuk memesan dan mengakses data pada setiap tahap FFT. Dari minat khusus adalah masalah merancang sebuah algoritma di tempat yang menimpa input dengan data output hanya menggunakan O (1) penyimpanan tambahan.
Teknik yang paling terkenal penataan melibatkan sedikit pembalikan eksplisit untuk di tempat radix-2 algoritma. Bit pembalikan adalah permutasi dimana data pada indeks n, ditulis dalam biner dengan angka b4b3b2b1b0 (misalnya 5 digit untuk N = 32 input), ditransfer ke indeks dengan angka terbalik b0b1b2b3b4. Pertimbangkan tahap terakhir dari algoritma radix-2 DIT seperti yang disajikan di atas, di mana output ditulis di tempat atas masukan: ketika E_k dan O_k digabungkan dengan ukuran-2 DFT, dua nilai yang ditimpa oleh output . Namun, dua nilai output harus pergi di bagian pertama dan kedua dari array output, sesuai dengan bit yang paling signifikan b4 (untuk N = 32), sedangkan dua input E_k dan O_k disisipkan dalam elemen genap dan ganjil, sesuai untuk paling signifikan bit B0. Dengan demikian, dalam rangka untuk mendapatkan output di tempat yang benar, kedua bit harus ditukar. Jika Anda memasukkan semua tahap rekursif dari algoritma radix-2 Dit, semua bit harus bertukar dan dengan demikian orang harus pra-proses input (atau pasca-proses output) dengan pembalikan bit untuk mendapatkan output di-order. (Jika setiap ukuran-N / 2 subtransform adalah untuk beroperasi pada data yang berdekatan, input DIT adalah pra-diproses oleh bit-reversal.) Sejalan dengan itu, jika Anda melakukan semua langkah-langkah dalam urutan terbalik, Anda mendapatkan algoritma radix-2 DIF dengan pembalikan bit di pos-pengolahan (atau pra-pengolahan, masing-masing). Atau, beberapa aplikasi (seperti konvolusi) bekerja sama dengan baik pada data bit-terbalik, sehingga seseorang dapat melakukan transformasi maju, pengolahan, dan kemudian terbalik mengubah semua tanpa sedikit pembalikan untuk menghasilkan hasil akhir dalam tatanan alam.
Banyak pengguna FFT, bagaimanapun, lebih memilih output alami-order, dan terpisah, eksplisit tahap bit-reversal dapat memiliki dampak non-diabaikan pada perhitungan waktu, meskipun sedikit pembalikan dapat dilakukan dalam O (N) waktu dan telah menjadi subyek banyak penelitian. Juga, sementara permutasi adalah pembalikan bit dalam radix-2 kasus, itu lebih umum pembalikan sewenang-wenang (mixed-base) digit untuk campuran radix kasus, dan algoritma permutasi menjadi lebih rumit untuk menerapkan. Selain itu, diharapkan pada banyak arsitektur hardware untuk kembali urutan tahap-tahap peralihan dari algoritma FFT sehingga mereka beroperasi pada berturut-turut (atau setidaknya lebih terlokalisasi) elemen data. Untuk tujuan ini, sejumlah skema implementasi alternatif telah dirancang untuk algoritma Cooley-Tukey yang tidak memerlukan pembalikan bit dan / atau melibatkan terpisah permutasi tambahan pada tahap-tahap peralihan.
Masalahnya adalah sangat sederhana jika out-of-tempat: output array berbeda dari array input atau, sama, array tambahan dengan ukuran yang sama tersedia. The Stockham algoritma auto-sort melakukan setiap tahap FFT out-of-tempat, biasanya menulis bolak-balik antara dua array, mentransposisi satu "digit" dari indeks dengan setiap tahap, dan telah sangat populer pada SIMD arsitektur. Bahkan lebih besar potensi keuntungan SIMD (akses lebih berturut-turut) telah diusulkan untuk algoritma Pease, yang juga menata ulang out-of-tempat dengan setiap tahap, tetapi metode ini memerlukan terpisah bit / pembalikan digit dan O (N log N) penyimpanan. Satu juga dapat langsung menerapkan definisi faktorisasi Cooley-Tukey dengan eksplisit (depth-first) rekursi dan kecil sisa akar, yang menghasilkan alam-order out-of-tempat output dengan ada langkah permutasi terpisah (seperti dalam pseudocode di atas) dan bisa dikatakan memiliki manfaat lokalitas cache menyadari pada sistem dengan memori hirarkis.
Sebuah strategi yang khas untuk di tempat tanpa algoritma penyimpanan tambahan dan tanpa terpisah melewati digit-pembalikan melibatkan transposisi matriks kecil (yang menukar pasangan individu digit) pada tahap-tahap peralihan, yang dapat dikombinasikan dengan radix kupu-kupu untuk mengurangi jumlah melewati atas data.
Meskipun abstrak Cooley-Tukey faktorisasi DFT, di atas, berlaku dalam beberapa bentuk untuk semua implementasi dari algoritma, keragaman jauh lebih besar ada dalam teknik untuk memesan dan mengakses data pada setiap tahap FFT. Dari minat khusus adalah masalah merancang sebuah algoritma di tempat yang menimpa input dengan data output hanya menggunakan O (1) penyimpanan tambahan.
Teknik yang paling terkenal penataan melibatkan sedikit pembalikan eksplisit untuk di tempat radix-2 algoritma. Bit pembalikan adalah permutasi dimana data pada indeks n, ditulis dalam biner dengan angka b4b3b2b1b0 (misalnya 5 digit untuk N = 32 input), ditransfer ke indeks dengan angka terbalik b0b1b2b3b4. Pertimbangkan tahap terakhir dari algoritma radix-2 DIT seperti yang disajikan di atas, di mana output ditulis di tempat atas masukan: ketika E_k dan O_k digabungkan dengan ukuran-2 DFT, dua nilai yang ditimpa oleh output . Namun, dua nilai output harus pergi di bagian pertama dan kedua dari array output, sesuai dengan bit yang paling signifikan b4 (untuk N = 32), sedangkan dua input E_k dan O_k disisipkan dalam elemen genap dan ganjil, sesuai untuk paling signifikan bit B0. Dengan demikian, dalam rangka untuk mendapatkan output di tempat yang benar, kedua bit harus ditukar. Jika Anda memasukkan semua tahap rekursif dari algoritma radix-2 Dit, semua bit harus bertukar dan dengan demikian orang harus pra-proses input (atau pasca-proses output) dengan pembalikan bit untuk mendapatkan output di-order. (Jika setiap ukuran-N / 2 subtransform adalah untuk beroperasi pada data yang berdekatan, input DIT adalah pra-diproses oleh bit-reversal.) Sejalan dengan itu, jika Anda melakukan semua langkah-langkah dalam urutan terbalik, Anda mendapatkan algoritma radix-2 DIF dengan pembalikan bit di pos-pengolahan (atau pra-pengolahan, masing-masing). Atau, beberapa aplikasi (seperti konvolusi) bekerja sama dengan baik pada data bit-terbalik, sehingga seseorang dapat melakukan transformasi maju, pengolahan, dan kemudian terbalik mengubah semua tanpa sedikit pembalikan untuk menghasilkan hasil akhir dalam tatanan alam.
Banyak pengguna FFT, bagaimanapun, lebih memilih output alami-order, dan terpisah, eksplisit tahap bit-reversal dapat memiliki dampak non-diabaikan pada perhitungan waktu, meskipun sedikit pembalikan dapat dilakukan dalam O (N) waktu dan telah menjadi subyek banyak penelitian. Juga, sementara permutasi adalah pembalikan bit dalam radix-2 kasus, itu lebih umum pembalikan sewenang-wenang (mixed-base) digit untuk campuran radix kasus, dan algoritma permutasi menjadi lebih rumit untuk menerapkan. Selain itu, diharapkan pada banyak arsitektur hardware untuk kembali urutan tahap-tahap peralihan dari algoritma FFT sehingga mereka beroperasi pada berturut-turut (atau setidaknya lebih terlokalisasi) elemen data. Untuk tujuan ini, sejumlah skema implementasi alternatif telah dirancang untuk algoritma Cooley-Tukey yang tidak memerlukan pembalikan bit dan / atau melibatkan terpisah permutasi tambahan pada tahap-tahap peralihan.
Masalahnya adalah sangat sederhana jika out-of-tempat: output array berbeda dari array input atau, sama, array tambahan dengan ukuran yang sama tersedia. The Stockham algoritma auto-sort melakukan setiap tahap FFT out-of-tempat, biasanya menulis bolak-balik antara dua array, mentransposisi satu "digit" dari indeks dengan setiap tahap, dan telah sangat populer pada SIMD arsitektur. Bahkan lebih besar potensi keuntungan SIMD (akses lebih berturut-turut) telah diusulkan untuk algoritma Pease, yang juga menata ulang out-of-tempat dengan setiap tahap, tetapi metode ini memerlukan terpisah bit / pembalikan digit dan O (N log N) penyimpanan. Satu juga dapat langsung menerapkan definisi faktorisasi Cooley-Tukey dengan eksplisit (depth-first) rekursi dan kecil sisa akar, yang menghasilkan alam-order out-of-tempat output dengan ada langkah permutasi terpisah (seperti dalam pseudocode di atas) dan bisa dikatakan memiliki manfaat lokalitas cache menyadari pada sistem dengan memori hirarkis.
Sebuah strategi yang khas untuk di tempat tanpa algoritma penyimpanan tambahan dan tanpa terpisah melewati digit-pembalikan melibatkan transposisi matriks kecil (yang menukar pasangan individu digit) pada tahap-tahap peralihan, yang dapat dikombinasikan dengan radix kupu-kupu untuk mengurangi jumlah melewati atas data.
0 komentar:
Posting Komentar