Buku / sumber daya untuk mengimplementasikan berbagai fungsi matematika dalam aritmatika titik tetap untuk tujuan DSP

8

Saya mencari buku atau sumber daya yang mencakup hal-hal berikut secara detail:

menerapkan fungsi matematika (misalnya, logaritma, eksponensial, sinus, cosinus, terbalik) dalam aritmatika titik tetap untuk tujuan DSP.
teknik seperti menggunakan tabel pencarian, seri Taylor, dll.

Saya cukup akrab dengan pemrograman C dan lebih tertarik pada algoritma tentang bagaimana cara mengimplementasikan berbagai fungsi matematika secara efisien.

algorithms reference-request math fixed-point RuD
sumber

1

Ini hanya satu trik, tetapi sangat berguna. Ini tentang menghitung fungsi atan2, yaitu menghitung argumen dari bilangan kompleks dari bagian nyata dan imajinernya.

Matt L.

1

saya dapat memberi Anda beberapa rangkaian daya urutan terbatas yang dioptimalkan yang saya kembangkan lebih dari satu dekade lalu. selain klien awal, saya belum mendapatkan uang untuk itu sejak jadi saya pikir saya juga bisa membuatnya menjadi domain publik. awalnya ini dikembangkan untuk floating point dalam konteks di mana klien tidak dapat memasukkan stdlib dalam build. dan evaluasinya tidak terlalu sempurna. yaitu ada kesalahan, tetapi sangat kecil dan dioptimalkan untuk fungsi tertentu yang sedang dievaluasi. biar menemukan file itu, saya akan menarik koefisien dan memposting seri.

robert bristow-johnson

@ robertbristow-johnson saya berharap dapat menggunakan seri ini dan melihat bagaimana kelanjutannya! Terima kasih!

RuD

Ruchir, saya memposting seri di bawah ini. ada hal-hal yang masuk akal yang perlu Anda lakukan untuk memperluas jangkauan. seperti jika . hal serupa untuk dan sinusoid periodik. untuk exp dan log, ini akan memerlukan sedikit pergeseran aritmatika dari apa yang keluar (untuk exp) atau apa yang masuk (untuk log). saya pikir Anda bisa mengatasinya. dan, tentu saja, untuk exp dan log basis yang berbeda (seperti ), Anda hanya skala dengan konstanta yang sesuai apa yang masuk ke dan apa yang keluar dari .

2^{x} = 2^{k} \times 2^{x - k}

$2^x = 2^k \times 2^{x-k}$

k \leq x \leq k + 1

$k \le x \le k+1$

\log_{2} ()

$\log_2()$

e

$e$

2^{x}

$2^x$

\log_{2} (x)

$\log_2(x)$

robert bristow-johnson

9

bentuk polinomial umum adalah:

\begin{aligned} f (u) & = \sum_{n = 0}^{N} a_{n} u^{n} \\ = a_{0} + (a_{1} + (a_{2} + (a_{3} + . . . (a_{N - 2} + (a_{N - 1} + a_{N} u) u) u . . .) u) u) u \end{aligned}

$\begin{align} f(u) &= \sum\limits_{n=0}^{N} \ a_n \ u^n \\ \\ &= a_{\small{0}} + \Bigg(a_{\small{1}} + \bigg(a_{\small{2}} + \Big(a_{\small{3}} + \,... \big(a_{\small{N-2}} + (a_{\small{N-1}} + a_{\small{N}} \,u \,)u \, \big)u \ ...\Big)u \, \bigg)u \, \Bigg)u\\ \end{align}$

bentuk terakhir menggunakan metode Horner , yang sangat dianjurkan, terutama jika Anda melakukan ini dalam floating point presisi tunggal.

kemudian untuk beberapa fungsi spesifik:

akar pangkat dua:

\begin{aligned} f (x - 1) & \approx \sqrt{x} 1 \leq x \leq 2 N = 4 \\ a_{0} & = 1.0 \\ a_{1} & = 0.49959804148061 \\ a_{2} & = - 0.12047308243453 \\ a_{3} & = 0.04585425015501 \\ a_{4} & = - 0.01076564682800 \end{aligned}

$\begin{align} f(x-1) & \approx \sqrt{x} \quad \quad 1 \le x \le 2 \quad \quad N=4\\ a_0 & = 1.0 \\ a_1 & = 0.49959804148061 \\ a_2 & = -0.12047308243453 \\ a_3 & = 0.04585425015501 \\ a_4 & = -0.01076564682800 \\ \end{align}$

jika $2 \le x \le 4$ , gunakan di atas untuk mengevaluasi $\sqrt{\tfrac{x}{2}}$ dan gandakan hasilnya dengan $\sqrt{2}$ mendapatkan $\sqrt{x}$ . seperti $\log_2(x)$ , terapkan kekuatan $2$ scaling untuk skala argumen ke kisaran yang diperlukan.

logaritma basis 2:

\begin{aligned} x \cdot f (x - 1) & \approx \log_{2} (x) 1 \leq x \leq 2 N = 5 \\ {Sebuah}_{0} & = 1.44254494359510 \\ {Sebuah}_{1} & = - 0.7181452567504 \\ {Sebuah}_{2} & = 0.45754919692582 \\ {Sebuah}_{3} & = - 0,27790534462866 \\ {Sebuah}_{4} & = 0.121797910687826 \\ {Sebuah}_{5} & = - 0,02584144982967 \end{aligned}

$\begin{align} x\cdot f(x-1) & \approx \log_2(x) \quad \quad 1 \le x \le 2 \quad \quad N=5\\ a_0 & = 1.44254494359510 \\ a_1 & = -0.7181452567504 \\ a_2 & = 0.45754919692582 \\ a_3 & = -0.27790534462866 \\ a_4 & = 0.121797910687826 \\ a_5 & = -0.02584144982967 \\ \end{align}$

basis 2 eksponensial:

\begin{aligned} f (x) & \approx 2^{x} 0 \leq x \leq 1 N = 4 \\ {Sebuah}_{0} & = 1.0 \\ {Sebuah}_{1} & = 0.69303212081966 \\ {Sebuah}_{2} & = 0.24137976293709 \\ {Sebuah}_{3} & = 0,05203236900844 \\ {Sebuah}_{4} & = 0,01355574723481 \end{aligned}

$\begin{align} f(x) & \approx 2^x \quad \quad 0 \le x \le 1 \quad \quad N=4\\ a_0 & = 1.0 \\ a_1 & = 0.69303212081966 \\ a_2 & = 0.24137976293709 \\ a_3 & = 0.05203236900844 \\ a_4 & = 0.01355574723481 \\ \end{align}$

sinus:

\begin{aligned} x \cdot f (x^{2}) & \approx \sin (\frac{π}{2} x) - 1 \leq x \leq 1 N = 4 \\ a_{0} & = 1.57079632679490 \\ a_{1} & = - 0.64596406188166 \\ a_{2} & = 0.07969158490912 \\ a_{3} & = - 0.00467687997706 \\ a_{4} & = 0.00015303015470 \end{aligned}

$\begin{align} x\cdot f(x^2) & \approx \sin\left(\tfrac{\pi}{2} x \right) \quad \quad -1 \le x \le 1 \quad \quad N=4 \\ a_0 & = 1.57079632679490 \\ a_1 & = -0.64596406188166 \\ a_2 & = 0.07969158490912 \\ a_3 & = -0.00467687997706 \\ a_4 & = 0.00015303015470 \\ \end{align}$

cosine (gunakan sinus):

\cos (π x) = 1 - 2 \sin^{2} (\frac{π}{2} x)

$\cos(\pi x) = 1 \, - \, 2 \, \sin^2 \left(\tfrac{\pi}{2} x \right)$

garis singgung:

\tan (x) = \frac{\sin (x)}{\cos (x)}

$\tan(x) = \frac{\sin(x)}{\cos(x)}$

garis singgung terbalik:

\begin{aligned} \frac{x}{f (x^{2})} & \approx \arctan (x) - 1 \leq x \leq 1 N = 4 \\ a_{0} & = 1.0 \\ a_{1} & = 0.33288950512027 \\ a_{2} & = - 0.08467922817644 \\ a_{3} & = 0.03252232640125 \\ a_{4} & = - 0.00749305860992 \end{aligned}

$\begin{align} \frac{x}{f(x^2)} & \approx \arctan(x) \quad \quad -1 \le x \le 1 \quad \quad N=4 \\ a_0 & = 1.0 \\ a_1 & = 0.33288950512027 \\ a_2 & = -0.08467922817644 \\ a_3 & = 0.03252232640125 \\ a_4 & = -0.00749305860992 \\ \end{align}$

\arctan (x) = \frac{π}{2} - \arctan (\frac{1}{x}) 1 \leq x

$\arctan(x) = \tfrac{\pi}{2} - \arctan\left( \tfrac{1}{x} \right) \quad \quad 1 \le x$

\arctan (x) = - \frac{π}{2} - \arctan (\frac{1}{x}) x \leq - 1

$\arctan(x) = -\tfrac{\pi}{2} - \arctan\left( \tfrac{1}{x} \right) \quad \quad x \le -1$

sinus terbalik:

\arcsin (x) = \arctan (\frac{x}{\sqrt{1 - x^{2}}})

$\arcsin(x) = \arctan\left( \frac{x}{\sqrt{1-x^2}} \right)$

cosinus terbalik:

\begin{aligned} \arccos (x) & = \frac{π}{2} - \arcsin (x) \\ = \frac{π}{2} - \arctan (\frac{x}{\sqrt{1 - x^{2}}}) \end{aligned}

$\begin{align} \arccos(x) &= \frac{\pi}{2} - \arcsin(x) \\ &= \frac{\pi}{2} - \arctan\left( \frac{x}{\sqrt{1-x^2}} \right)\\ \end{align}$

robert bristow-johnson
sumber

Itu sepertinya cukup berguna! Terima kasih banyak untuk membagikannya. Tapi entri referensi pertama tetap yang man soxterbaik;)

jojek

tak tahu sox. apa yang manual katakan tentang hal itu?

robert bristow-johnson

2

Cukup

[1]    R.  Bristow-Johnson, Cookbook formulae for audio EQ biquad filter coefficients, http://musicdsp.org/files/Audio-EQ-Cookbook.txt

:)

jojek

BTW, seri ini meminimalkan kesalahan tertimbang maksimum . kesalahan tertimbang sedemikian rupa sehingga masuk akal untuk fungsi tersebut. kesalahan maksimum seragam untuk

\log_{2} ()

$\log_2()$ . kesalahan maksimum proporsional untuk

\sqrt{x}

$\sqrt{x}$ dan

2^{x}

$2^x$ . sesuatu yang mirip dengan proporsional untuk

\sin ()

$\sin()$ ada hubungannya dengan koefisien komputasi untuk filter resonan sehingga kesalahan maks

\log (f_{0})

$\log(f_0)$ diminimalkan. saya tidak ingat kriteria apa yang saya gunakan

\arctan ()

$\arctan()$ . dan untuk beberapa alasan saya tidak dapat menemukan file saya yang memberi tahu saya apa kesalahan maksimum, mengingat kisaran

x

$x$ . seseorang dengan MATLAB dapat mengetahuinya.

robert bristow-johnson

1

Anda harus merencanakan kesalahan dengan python Anda, jika Anda bisa. juga np.max(np.abs(sqrt_1px(xp)-np.sqrt(1+xp)))mungkin sebaliknya np.max(np.abs((sqrt_1px(xp)-np.sqrt(1+xp))/np.sqrt(1+xp))) dan sama untuk 2**x pembobotan kesalahan karena dosa berbeda dan saya harus menemukan bagaimana saya melakukan itu. Saya punya skrip MATLAB lama yang digunakan untuk mengurutkan pekerjaan di Oktaf, tapi sekarang saya bahkan tidak bisa mendapatkan Oktaf untuk plot di laptop G4 Mac lama saya.

robert bristow-johnson

2

Meskipun tidak spesifik untuk titik tetap, saya akan sangat merekomendasikan buku "Math Toolkit for Real-Time Programming" karya Jack Crenshaw. Muncul dengan CD dengan kode sumber.

David
sumber

2

TI memiliki perpustakaan IQMath untuk semua mikrokontroler titik tetapnya. Saya telah menemukan mereka menjadi tambang emas fungsi fixed-point matematika dan DSP tidak harus terbatas pada chip TI.

MSP430 C28X

Otto Hunt
sumber

Saya lebih tertarik pada algoritma daripada hanya penerapan fungsi

RuD

1

Perkiraan Chebyshev dapat membantu menghitung koefisien polinomial yang mendekati optimal untuk memperkirakan suatu fungsi pada rentang terbatas. Anda menjalankan aproksimasi rutin pada PC untuk mencapai serangkaian koefisien polinomial tertentu, yang kemudian dapat Anda terapkan pada platform apa pun yang Anda suka (mis. Tertanam / DSP) Cetakan kecil kurang lebih adalah sebagai berikut:

Ini hanya berfungsi untuk fungsi satu variabel; jika Anda memiliki beberapa fungsi $z=f(x,y)$ maka pendekatan Chebyshev tidak akan membantu Anda.
Fungsi yang Anda aproksimasi harus "polinomial-like". Sudut, tikungan tajam, dan banyak goyangan akan membutuhkan polinomial tingkat tinggi untuk mencapai tingkat akurasi tertentu.
Menjaga agar urutan polinomial rendah adalah penting - di atas 5 atau lebih, Anda mungkin mulai melihat kesalahan numerik.
Perkiraan Chebyshev menggunakan polinomial Chebyshev yang dievaluasi pada domain [-1,1], jadi jika rentang input untuk fungsi Anda sangat berbeda, Anda mungkin perlu mengukur / mengimbangi input dengan tepat sebelum menentukan koefisien dan sebelum menerapkannya. Misalnya, jika saya peduli dengan fungsi pada rentang input $x \in [0,20]$ maka saya mungkin mendefinisikan $u = (x\times 0.1) - 1$ maka $u$ berkisar dari -1 hingga +1 dan saya dapat mengevaluasi polinomial dalam $u$ untuk menghitung hasil yang diperlukan. Tanpa penskalaan ini, Anda dapat mengalami kesalahan numerik dengan lebih mudah - atau menyatakan dengan cara lain, untuk ketepatan yang sama Anda mungkin memerlukan panjang bit yang lebih tinggi untuk menghitung nilai antara, dan ini biasanya tidak diinginkan.

Jason S
sumber

Jason, saya tidak menggunakan polinomial Tchebyshev, tetapi saya memang menggunakan kesalahan MinMax tertimbang (kadang-kadang disebut "

L_{\infty}

$L_\infty$ norma "pada kesalahan), yang, saya pikir, sama dengan pendekatan Tchebyshev. Metode yang saya gunakan adalah Remez Exchange Algorithm.

robert bristow-johnson

Remez lebih unggul (meskipun lebih kompleks) daripada Chebyshev. Chebyshev hanya mendekati kondisi minimax, tetapi biasanya itu cukup baik.

Jason S

Buku / sumber daya untuk mengimplementasikan berbagai fungsi matematika dalam aritmatika titik tetap untuk tujuan DSP

Jawaban: