Saya mencari solusi efisien waktu dan memori untuk menghitung rata-rata bergerak dalam C. Saya harus menghindari pembagian karena saya menggunakan PIC 16 yang tidak memiliki unit divisi khusus.
Saat ini, saya hanya menyimpan semua nilai dalam buffer cincin dan hanya menyimpan dan memperbarui jumlah setiap kali nilai baru tiba. Ini sangat efisien, tetapi sayangnya menggunakan sebagian besar memori saya yang tersedia ...
Jawaban:
Seperti yang disebutkan orang lain, Anda harus mempertimbangkan filter IIR (respon impuls tak terbatas) daripada filter FIR (respon impuls terbatas) yang Anda gunakan sekarang. Ada lebih dari itu, tetapi pada pandangan pertama filter FIR diimplementasikan sebagai konvolusi eksplisit dan filter IIR dengan persamaan.
Filter IIR tertentu yang sering saya gunakan dalam mikrokontroler adalah filter low pass tiang tunggal. Ini setara dengan digital dari filter analog RC sederhana. Untuk sebagian besar aplikasi, ini akan memiliki karakteristik yang lebih baik daripada filter kotak yang Anda gunakan. Sebagian besar penggunaan filter kotak yang saya temui adalah hasil dari seseorang yang tidak memperhatikan kelas pemrosesan sinyal digital, bukan karena membutuhkan karakteristik khusus mereka. Jika Anda hanya ingin menipiskan frekuensi tinggi yang Anda tahu kebisingan, filter low pass tiang tunggal lebih baik. Cara terbaik untuk mengimplementasikan satu secara digital dalam mikrokontroler biasanya:
FILT <- FILT + FF (BARU - FILT)
FILT adalah bagian dari status persisten. Ini adalah satu-satunya variabel persisten yang Anda perlukan untuk menghitung filter ini. BARU adalah nilai baru bahwa filter sedang diperbarui dengan iterasi ini. FF adalah fraksi filter , yang menyesuaikan "bobot" filter. Lihatlah algoritma ini dan lihat bahwa untuk FF = 0 filternya sangat berat karena outputnya tidak pernah berubah. Untuk FF = 1, benar-benar tidak ada filter sama sekali karena output hanya mengikuti input. Nilai yang berguna ada di antaranya. Pada sistem kecil Anda memilih FF menjadi 1/2 Nsehingga kalikan dengan FF dapat dicapai sebagai pergeseran yang tepat oleh N bit. Sebagai contoh, FF mungkin 1/16 dan kalikan dengan FF oleh karena itu pergeseran kanan 4 bit. Kalau tidak, filter ini hanya perlu satu pengurangan dan satu penambahan, meskipun angkanya biasanya harus lebih luas dari nilai input (lebih lanjut tentang ketepatan numerik di bagian terpisah di bawah).
Saya biasanya mengambil pembacaan A / D secara signifikan lebih cepat daripada yang dibutuhkan dan menerapkan dua filter ini mengalir. Ini setara dengan digital dari dua filter RC secara seri, dan dilemahkan oleh 12 dB / oktaf di atas frekuensi rolloff. Namun, untuk pembacaan A / D biasanya lebih relevan untuk melihat filter dalam domain waktu dengan mempertimbangkan respons langkahnya. Ini memberitahu Anda seberapa cepat sistem Anda akan melihat perubahan ketika hal yang Anda ukur berubah.
Untuk memfasilitasi merancang filter ini (yang hanya berarti memilih FF dan memutuskan berapa banyak dari mereka yang akan mengalir), saya menggunakan FILTBITS program saya. Anda menentukan jumlah bit shift untuk setiap FF dalam rangkaian filter berjenjang, dan menghitung respons langkah dan nilai lainnya. Sebenarnya saya biasanya menjalankan ini melalui skrip pembungkus saya PLOTFILT. Ini menjalankan FILTBITS, yang membuat file CSV, lalu memplot file CSV. Sebagai contoh, berikut adalah hasil dari "PLOTFILT 4 4":
Dua parameter untuk PLOTFILT berarti akan ada dua filter yang diturunkan dari tipe yang dijelaskan di atas. Nilai 4 menunjukkan jumlah bit shift untuk mewujudkan kalikan dengan FF. Oleh karena itu dua nilai FF adalah 1/16 dalam kasus ini.
Jejak merah adalah respons langkah unit, dan merupakan hal utama yang harus dilihat. Misalnya, ini memberi tahu Anda bahwa jika input berubah secara instan, output dari filter gabungan akan menetap hingga 90% dari nilai baru dalam 60 iterasi. Jika Anda peduli 95% waktu penyelesaian maka Anda harus menunggu sekitar 73 iterasi, dan untuk 50% waktu penyelesaian hanya 26 iterasi.
Jejak hijau menunjukkan kepada Anda output dari lonjakan amplitudo penuh. Ini memberi Anda beberapa gagasan tentang penindasan kebisingan acak. Sepertinya tidak ada sampel tunggal akan menyebabkan lebih dari 2,5% perubahan dalam output.
Jejak biru adalah untuk memberikan perasaan subjektif tentang apa yang dilakukan filter ini dengan white noise. Ini bukan tes yang ketat karena tidak ada jaminan apa sebenarnya konten dari nomor acak yang dipilih sebagai input derau untuk menjalankan PLOTFILT ini. Ini hanya untuk memberi Anda perasaan kasar tentang berapa banyak itu akan tergencet dan seberapa halus itu.
PLOTFILT, mungkin FILTBITS, dan banyak hal berguna lainnya, terutama untuk pengembangan firmware PIC tersedia di rilis perangkat lunak PIC Development Tools di halaman unduhan Perangkat Lunak saya .
Menambahkan tentang ketepatan angka
Saya melihat dari komentar dan sekarang jawaban baru bahwa ada minat mendiskusikan jumlah bit yang diperlukan untuk mengimplementasikan filter ini. Perhatikan bahwa kalikan dengan FF akan membuat bit baru Log 2 (FF) di bawah titik biner. Pada sistem kecil, FF biasanya dipilih menjadi 1/2 N sehingga penggandaan ini sebenarnya diwujudkan dengan pergeseran N bit yang tepat.
Oleh karena itu FILT biasanya merupakan integer titik tetap. Perhatikan bahwa ini tidak mengubah matematika apa pun dari sudut pandang prosesor. Misalnya, jika Anda memfilter pembacaan A / D 10 bit dan N = 4 (FF = 1/16), maka Anda memerlukan 4 bit fraksi di bawah bacaan A / D integer 10 bit. Salah satu prosesor yang paling, Anda akan melakukan operasi integer 16 bit karena pembacaan A / D 10 bit. Dalam hal ini, Anda masih dapat melakukan operasi integer 16 bit persis sama, tetapi mulai dengan pembacaan A / D dibiarkan digeser oleh 4 bit. Prosesor tidak tahu bedanya dan tidak perlu. Melakukan perhitungan matematika pada keseluruhan bilangan bulat 16 bit berfungsi baik jika Anda menganggapnya sebagai 12,4 titik tetap atau bilangan bulat 16 bit sejati (titik tetap 16,0).
Secara umum, Anda perlu menambahkan N bit setiap kutub filter jika Anda tidak ingin menambahkan suara karena representasi numerik. Pada contoh di atas, filter kedua dari dua harus memiliki 10 + 4 + 4 = 18 bit untuk tidak kehilangan informasi. Dalam prakteknya pada mesin 8 bit itu berarti Anda akan menggunakan nilai 24 bit. Secara teknis hanya kutub kedua dari dua akan membutuhkan nilai yang lebih luas, tetapi untuk kesederhanaan firmware saya biasanya menggunakan representasi yang sama, dan dengan demikian kode yang sama, untuk semua kutub filter.
Biasanya saya menulis subroutine atau makro untuk melakukan satu operasi tiang filter, kemudian menerapkannya pada setiap kutub. Apakah subrutin atau makro tergantung pada apakah siklus atau memori program lebih penting dalam proyek tertentu. Either way, saya menggunakan beberapa negara awal untuk lulus BARU ke subroutine / makro, yang memperbarui FILT, tetapi juga memuat yang ke dalam negara awal yang sama BARU masuk. Ini membuatnya mudah untuk menerapkan beberapa kutub sejak FILT diperbarui satu kutub BARU dari yang berikutnya. Saat subrutin, ada gunanya memiliki titik penunjuk ke FILT saat masuk, yang diperbarui setelah FILT saat keluar. Dengan cara itu subrutin secara otomatis beroperasi pada filter berturut-turut dalam memori jika dipanggil beberapa kali. Dengan makro Anda tidak perlu pointer karena Anda memasukkan alamat untuk beroperasi pada setiap iterasi.
Contoh Kode
Berikut adalah contoh makro seperti dijelaskan di atas untuk PIC 18:
Dan di sini adalah makro yang serupa untuk PIC 24 atau dsPIC 30 atau 33:
Kedua contoh ini diimplementasikan sebagai makro menggunakan preprocessor assembler PIC saya , yang lebih mampu daripada salah satu dari fasilitas makro bawaan.
sumber
Jika Anda dapat hidup dengan pembatasan kekuatan dua jumlah item rata-rata (yaitu 2,4,8,16,32 dll) maka pembagian dapat dengan mudah dan efisien dilakukan pada mikro kinerja rendah tanpa pembagian khusus karena itu bisa dilakukan sedikit bergeser. Setiap shift kanan adalah satu kekuatan dua mis:
atau
dll.
sumber
Ada adalah jawaban untuk bergerak benar rata penyaring (alias "gerbong filter") dengan persyaratan memori kurang, jika Anda tidak keberatan downsampling. Ini disebut filter integrator-cascaded (CIC). Idenya adalah bahwa Anda memiliki integrator yang Anda gunakan untuk perbedaan selama periode waktu tertentu, dan perangkat penghemat memori utama adalah dengan downsampling, Anda tidak harus menyimpan setiap nilai integrator. Ini dapat diimplementasikan menggunakan pseudocode berikut:
Panjang rata-rata bergerak efektif Anda adalah
decimationFactor*statesize
tetapi Anda hanya perlu menjagastatesize
sampel. Jelas Anda bisa mendapatkan kinerja yang lebih baik jika Andastatesize
dandecimationFactor
adalah kekuatan 2, sehingga divisi dan operator sisanya digantikan oleh shift dan mask-ands.Catatan tambahan: Saya setuju dengan Olin bahwa Anda harus selalu mempertimbangkan filter IIR sederhana sebelum filter rata-rata bergerak. Jika Anda tidak membutuhkan frekuensi-nol dari filter gerbong, filter low-pass 1 kutub atau 2 kutub mungkin akan berfungsi dengan baik.
Di sisi lain, jika Anda memfilter untuk tujuan penipisan (mengambil input tingkat sampel tinggi dan rata-rata untuk digunakan oleh proses laju rendah) maka filter CIC mungkin tepat seperti yang Anda cari. (terutama jika Anda dapat menggunakan Statesize = 1 dan menghindari ringbuffer sama sekali hanya dengan satu nilai integrator sebelumnya)
sumber
Ada beberapa analisis mendalam dari matematika di balik menggunakan filter IIR orde pertama yang telah dijelaskan Olin Lathrop pada pertukaran tumpukan Pemrosesan Sinyal Digital (termasuk banyak gambar cantik). Persamaan untuk filter IIR ini adalah:
y [n] = αx [n] + (1 − α) y [n − 1]
Ini dapat diimplementasikan hanya dengan menggunakan integer dan tidak ada pembagian menggunakan kode berikut (mungkin perlu beberapa debug karena saya mengetik dari memori.)
Filter ini mendekati rata-rata bergerak dari sampel K terakhir dengan menetapkan nilai alpha ke 1 / K. Lakukan ini di kode sebelumnya oleh
#define
ingBITS
ke log2 (K), yaitu untuk K = 16 setBITS
untuk 4, untuk K = 4 setBITS
ke 2, dll(Saya akan memverifikasi kode yang tercantum di sini segera setelah saya mendapatkan perubahan dan mengedit jawaban ini jika diperlukan.)
sumber
Berikut filter low-pass kutub tunggal (rata-rata bergerak, dengan frekuensi cutoff = CutoffFrequency). Sangat sederhana, sangat cepat, berfungsi dengan baik, dan hampir tanpa memori.
Catatan: Semua variabel memiliki cakupan di luar fungsi filter, kecuali yang diteruskan dalam input baru
Catatan: Ini adalah filter satu tahap. Beberapa tahap dapat digabungkan bersama untuk meningkatkan ketajaman filter. Jika Anda menggunakan lebih dari satu tahap, Anda harus menyesuaikan DecayFactor (terkait dengan Cutoff-Frequency) untuk mengkompensasi.
Dan jelas yang Anda butuhkan adalah dua garis yang ditempatkan di mana saja, mereka tidak membutuhkan fungsinya sendiri. Filter ini memang memiliki waktu ramp-up sebelum rata-rata bergerak mewakili sinyal input. Jika Anda perlu mem-bypass waktu ramp-up itu, Anda bisa menginisialisasi MovingAverage ke nilai pertama dari input baru alih-alih 0, dan berharap input baru pertama bukan merupakan pencilan.
(CutoffFrequency / SampleRate) memiliki kisaran antara 0 dan 0,5. DecayFactor adalah nilai antara 0 dan 1, biasanya mendekati 1.
Pelampung presisi tunggal cukup baik untuk sebagian besar hal, saya hanya lebih suka ganda. Jika Anda harus tetap menggunakan bilangan bulat, Anda dapat mengubah DecayFactor dan Amplitude Factor menjadi bilangan bulat pecahan, di mana pembilangnya disimpan sebagai bilangan bulat, dan penyebutnya adalah kekuatan bilangan bulat 2 (sehingga Anda dapat menggeser-geser ke kanan seperti penyebut daripada harus membagi selama loop filter). Misalnya, jika DecayFactor = 0.99, dan Anda ingin menggunakan bilangan bulat, Anda dapat mengatur DecayFactor = 0.99 * 65536 = 64881. Dan kapan pun Anda mengalikan dengan DecayFactor di loop filter Anda, cukup geser hasilnya >> 16.
Untuk informasi lebih lanjut tentang ini, buku bagus yang online, bab 19 tentang filter rekursif: http://www.dspguide.com/ch19.htm
PS Untuk paradigma Moving Average, pendekatan berbeda untuk menetapkan DecayFactor dan AmplitudeFactor yang mungkin lebih relevan dengan kebutuhan Anda, katakanlah Anda ingin yang sebelumnya, sekitar 6 item dirata-rata bersama-sama, melakukannya dengan bijaksana, Anda akan menambahkan 6 item dan dibagi dengan 6, sehingga Anda dapat mengatur AmplitudeFactor ke 1/6, dan DecayFactor ke (1.0 - AmplitudeFactor).
sumber
Anda dapat memperkirakan rata-rata bergerak untuk beberapa aplikasi dengan filter IIR sederhana.
berat adalah nilai 0,255, nilai tinggi = skala waktu lebih pendek untuk rata
Nilai = (nilai baru * berat + nilai * (256-berat)) / 256
Untuk menghindari kesalahan pembulatan, nilainya biasanya akan panjang, yang mana Anda hanya menggunakan byte urutan yang lebih tinggi sebagai nilai 'aktual' Anda.
sumber
Semua orang telah berkomentar secara menyeluruh tentang utilitas IIR vs FIR, dan pada kekuatan dua divisi. Saya hanya ingin memberikan beberapa detail implementasi. Di bawah ini berfungsi dengan baik pada mikrokontroler kecil tanpa FPU. Tidak ada perkalian, dan jika Anda menjaga N menjadi kekuatan dua, semua divisi adalah satu-bit-shifting-cycle.
Buffer ring FIR dasar: tetap menjalankan buffer dari nilai N terakhir, dan SUM yang sedang berjalan dari semua nilai dalam buffer. Setiap kali sampel baru masuk, kurangi nilai terlama di buffer dari SUM, ganti dengan sampel baru, tambahkan sampel baru ke SUM, dan hasilkan SUM / N.
Penyangga cincin IIR yang dimodifikasi: tetap menjalankan SUM dari nilai N terakhir. Setiap kali sampel baru masuk, SUM - = SUM / N, tambahkan sampel baru, dan hasilkan SUM / N.
sumber
Seperti kata mikeselectricstuff , jika Anda benar-benar perlu mengurangi kebutuhan memori Anda, dan Anda tidak keberatan respons impuls Anda menjadi eksponensial (alih-alih pulsa persegi panjang), saya akan menggunakan filter moving average eksponensial . Saya menggunakannya secara luas. Dengan jenis filter itu, Anda tidak perlu buffer apa pun. Anda tidak perlu menyimpan sampel N masa lalu. Hanya satu. Jadi, persyaratan memori Anda dikurangi oleh faktor N.
Juga, Anda tidak perlu pembagian apa pun untuk itu. Hanya perkalian. Jika Anda memiliki akses ke aritmatika titik-mengambang, gunakan perkalian titik-mengambang. Jika tidak, lakukan penggandaan bilangan bulat dan bergeser ke kanan. Namun, kami berada di 2012, dan saya akan merekomendasikan Anda untuk menggunakan kompiler (dan MCU) yang memungkinkan Anda untuk bekerja dengan angka floating-point.
Selain lebih efisien dalam memori dan lebih cepat (Anda tidak perlu memperbarui item dalam buffer melingkar), saya akan mengatakan itu juga lebih alami , karena respons impuls eksponensial lebih cocok dengan cara alam berperilaku, dalam banyak kasus.
sumber
Salah satu masalah dengan filter IIR karena hampir disentuh oleh @olin dan @supercat tetapi tampaknya diabaikan oleh orang lain adalah bahwa pembulatan ke bawah menimbulkan beberapa ketidaktepatan (dan berpotensi bias / pemotongan): dengan asumsi bahwa N adalah kekuatan dua, dan hanya aritmatika bilangan bulat adalah digunakan, hak bergeser tidak secara sistematis menghilangkan LSB sampel baru. Itu berarti bahwa berapa lama seri itu bisa, rata-rata tidak akan pernah memperhitungkannya.
Sebagai contoh, anggaplah seri menurun perlahan (8,8,8, ..., 8,7,7,7, ... 7,6,6,) dan anggap rata-rata memang 8 pada awalnya. Sampel "7" pertama akan membawa rata-rata ke 7, berapa pun kekuatan saringannya. Hanya untuk satu sampel. Kisah yang sama untuk 6, dll. Sekarang pikirkan sebaliknya: seri naik. Rata-rata akan tetap pada 7 selamanya, sampai sampel cukup besar untuk mengubahnya.
Tentu saja, Anda dapat memperbaiki "bias" dengan menambahkan 1/2 ^ N / 2, tetapi itu tidak akan benar-benar menyelesaikan masalah presisi: dalam hal itu seri penurunan akan tetap selamanya di 8 sampai sampel 8-1 / 2 ^ (N / 2). Untuk N = 4 misalnya, setiap sampel di atas nol akan menjaga rata-rata tidak berubah.
Saya percaya solusi untuk itu akan menyiratkan memegang akumulator dari LSB yang hilang. Tapi saya tidak membuatnya cukup jauh untuk memiliki kode siap, dan saya tidak yakin itu tidak akan membahayakan kekuatan IIR dalam beberapa kasus seri lainnya (misalnya apakah 7,9,7,9 akan menjadi rata-rata 8) .
@Olin, kaskade dua tahap Anda juga perlu penjelasan. Maksud Anda memegang dua nilai rata-rata dengan hasil dari yang pertama dimasukkan ke dalam yang kedua setiap iterasi? Apa manfaatnya ini?
sumber