在 Embedded system 上儲存空間是相當珍貴的,目前除了智慧型手機上有Giga等級的flash儲存空間,其他能有個8M flash已經是相當奢侈了.
在這麼小的flash中想用c++來program最大的問題就是libstdc++.so實在太肥了.
gigijoe@gigijoe-i5-2500k:/opt/arm-linux-uclibcgnueabi/lib$ ls libstdc++* -al
-rw-r--r-- 1 root root 7233624 8月 18 2010 libstdc++.a
-rwxr-xr-x 1 root root 1307 8月 18 2010 libstdc++.la
-rw-r--r-- 1 root root 7224318 8月 18 2010 libstdc++_pic.a
lrwxrwxrwx 1 root root 18 8月 18 2010 libstdc++.so -> libstdc++.so.6.0.8
lrwxrwxrwx 1 root root 18 8月 18 2010 libstdc++.so.6 -> libstdc++.so.6.0.8
-rwxr-xr-x 1 root root 3750191 8月 18 2010 libstdc++.so.6.0.8
這個library包含了c++ STL / dynamic_cast / exception等功能,往後c++11,c++14等規格再陸續實作後只會越來越大.那麼用c來program就好啦,幹嘛找麻煩用c++啊?
c++ 有許多feature能讓程式更加結構化並容易閱讀,例如 function overload.
物件導向所提供的 繼承 / 多型 更能讓整個程式有更多的彈性.
以下是在網路上找到的方式,我自己也驗證過可行.
限制是不能使用 STL / dynamic_cast / exception
http://ptspts.blogspot.tw/2010/12/how-to-write-c-program-without-libstdc.html
以g++ compile .cpp ( -fno-rtti -fno-exceptions ), 以 gcc link 所有的.o
gigijoe@gigijoe-i5-2500k:~/SourceCode/test$ ldd main
linux-gate.so.1 => (0xb773c000)
libpicowm.so (0xb7736000)
libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xb7560000)
/lib/ld-linux.so.2 (0xb773d000)
libstdc++.so 已經不再需要囉 :)
2013年6月17日 星期一
2013年3月12日 星期二
Fixed-Point Fast Fourier Transform (FFT)
Fast Fourier Transform is very important for signal processing.
This time I will demostrate Fixed-Point FFT running on embedded system.
There's NO FPU on most of embedded CPU and most of implement of FFT using floating point variable.
This means bad performance of FFT calculation, so I found an Fixed-Point FFT library Written by Tom Roberts which fit the requirement.
The purpose of using FFT is to detect DTMF in 16 bits / 8k sample rate raw sound data.
DTMF is multi-frequency signal which mixture of two difference tone.
This is the foundation of modern telephone system.
1209 Hz 1336 Hz 1477 Hz
697 Hz 1 2 3
770 Hz 4 5 6
852 Hz 7 8 9
941 Hz * 0 #
The procdure to detect DTMF is to pass raw sound data into FFT then check frequency domain to determinate which frequencies with higher energy.
1.Fixed-Point FFT
The prototype of fix_fft function
int fix_fft(short fr[], short fi[], short m, short inverse)
fr[] is the real part array, fi[] is the imaginary part array.
m is power of 2 of the array size, the array size must be power of 2.
For example the array size is 256 (2^8) then m is 8.
Pass input sound data into fr[] and leave all zero to fi[]
Return value of fix_fft is useless while forward FFT.
The result of FFT is storing in fr[] and fi[].
2.Phyical of FFT
It's not hard to realize more input data lead to more precision of result.
The input sound data is 16 bit / 8k sample rate. Assume number of input samples is 256 (2^8)
So we have 256 buckets divided over 8khz, each bucket represents 31.25 hz ( 8k hz / 256).
But, the maximum frequency we can measure is half of the sampling rate so if we sample at 8Khz our maximum is 4Khz
(this is called the Nyquist frequency).
0.000000 ~ 31.250000hz
31.250000 ~ 62.500000hz
62.500000 ~ 93.750000hz
93.750000 ~ 125.000000hz
125.000000 ~ 156.250000hz
156.250000 ~ 187.500000hz
187.500000 ~ 218.750000hz
...
...
...
3812.500000 ~ 3843.750000hz
3843.750000 ~ 3875.000000hz
3875.000000 ~ 3906.250000hz
3906.250000 ~ 3937.500000hz
3937.500000 ~ 3968.750000hz
3968.750000 ~ 4000.000000hz
So, the frequency domain is from 0 ~ 4k hz and how about the energy of each frequency range ?
energy = sqrt(fr[i]^2 + fi[i]^2), where i form 0 to 127
Then check the higher energy (Threshold) of frequency and see if the frequency fit the range of DTMF tone.
3.The source code and result
fix_fft.c
dtmf_detect.c
T159.snd
The target machine is MIPS 4KEc running 162Mhz. No FPU support.
Enable DEBUG flag to see what's going on, but terrible performance due to printf()
1.5 second sound data takes more than 4 seconds to process.
$ ./dtmf_detect T159.snd
Detect None ...
Detect None ...
Detect None ...
Detect None ...
687.500000 ~ 718.750000hz : 2838
718.750000 ~ 750.000000hz : 2271
1218.750000 ~ 1250.000000hz : 3761
Max freq : 1218.750000 ~ 1218.750000hz (Value : 3761)
dtmf is 1
687.500000 ~ 718.750000hz : 3915
718.750000 ~ 750.000000hz : 2246
1218.750000 ~ 1250.000000hz : 4853
Max freq : 1218.750000 ~ 1218.750000hz (Value : 4853)
687.500000 ~ 718.750000hz : 3762
718.750000 ~ 750.000000hz : 2243
1218.750000 ~ 1250.000000hz : 6525
Max freq : 1218.750000 ~ 1218.750000hz (Value : 6525)
687.500000 ~ 718.750000hz : 4066
718.750000 ~ 750.000000hz : 2288
1218.750000 ~ 1250.000000hz : 5760
Max freq : 1218.750000 ~ 1218.750000hz (Value : 5760)
687.500000 ~ 718.750000hz : 3601
718.750000 ~ 750.000000hz : 2086
1218.750000 ~ 1250.000000hz : 5968
Max freq : 1218.750000 ~ 1218.750000hz (Value : 5968)
687.500000 ~ 718.750000hz : 4108
718.750000 ~ 750.000000hz : 2375
1218.750000 ~ 1250.000000hz : 6532
Max freq : 1218.750000 ~ 1218.750000hz (Value : 6532)
687.500000 ~ 718.750000hz : 3330
718.750000 ~ 750.000000hz : 2034
1218.750000 ~ 1250.000000hz : 4783
Max freq : 1218.750000 ~ 1218.750000hz (Value : 4783)
687.500000 ~ 718.750000hz : 3717
718.750000 ~ 750.000000hz : 2401
1218.750000 ~ 1250.000000hz : 5406
Max freq : 1218.750000 ~ 1218.750000hz (Value : 5406)
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
750.000000 ~ 781.250000hz : 2635
781.250000 ~ 812.500000hz : 2451
1312.500000 ~ 1343.750000hz : 2238
1343.750000 ~ 1375.000000hz : 2872
Max freq : 1343.750000 ~ 1343.750000hz (Value : 2872)
dtmf is 5
750.000000 ~ 781.250000hz : 3027
781.250000 ~ 812.500000hz : 3084
1312.500000 ~ 1343.750000hz : 2692
1343.750000 ~ 1375.000000hz : 4415
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4415)
750.000000 ~ 781.250000hz : 3119
781.250000 ~ 812.500000hz : 3196
1312.500000 ~ 1343.750000hz : 3174
1343.750000 ~ 1375.000000hz : 4766
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4766)
750.000000 ~ 781.250000hz : 3127
781.250000 ~ 812.500000hz : 3333
1312.500000 ~ 1343.750000hz : 3198
1343.750000 ~ 1375.000000hz : 4750
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4750)
750.000000 ~ 781.250000hz : 3129
781.250000 ~ 812.500000hz : 3451
1312.500000 ~ 1343.750000hz : 2803
1343.750000 ~ 1375.000000hz : 4114
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4114)
750.000000 ~ 781.250000hz : 3143
781.250000 ~ 812.500000hz : 3534
1312.500000 ~ 1343.750000hz : 3393
1343.750000 ~ 1375.000000hz : 4978
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4978)
750.000000 ~ 781.250000hz : 3144
781.250000 ~ 812.500000hz : 3561
1312.500000 ~ 1343.750000hz : 2593
1343.750000 ~ 1375.000000hz : 3631
Max freq : 1343.750000 ~ 1343.750000hz (Value : 3631)
750.000000 ~ 781.250000hz : 3195
781.250000 ~ 812.500000hz : 3544
1312.500000 ~ 1343.750000hz : 3246
1343.750000 ~ 1375.000000hz : 4971
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4971)
1312.500000 ~ 1343.750000hz : 2850
1343.750000 ~ 1375.000000hz : 2935
Max freq : 1343.750000 ~ 1343.750000hz (Value : 2935)
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
843.750000 ~ 875.000000hz : 3998
1468.750000 ~ 1500.000000hz : 5109
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5109)
dtmf is 9
843.750000 ~ 875.000000hz : 4803
1468.750000 ~ 1500.000000hz : 6069
Max freq : 1468.750000 ~ 1468.750000hz (Value : 6069)
843.750000 ~ 875.000000hz : 4620
1468.750000 ~ 1500.000000hz : 5350
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5350)
843.750000 ~ 875.000000hz : 5024
1468.750000 ~ 1500.000000hz : 6536
Max freq : 1468.750000 ~ 1468.750000hz (Value : 6536)
843.750000 ~ 875.000000hz : 4157
1468.750000 ~ 1500.000000hz : 5645
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5645)
843.750000 ~ 875.000000hz : 5140
1468.750000 ~ 1500.000000hz : 5768
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5768)
843.750000 ~ 875.000000hz : 3629
1468.750000 ~ 1500.000000hz : 6446
Max freq : 1468.750000 ~ 1468.750000hz (Value : 6446)
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Number samples : 12544, Duration : 4 seconds and 84537 usecs
Disable DEBUG with good performance.
1.5 second sound data takes 31.346 ms to process.
$ ./dtmf_detect T159.snd
dtmf is 1
dtmf is 5
dtmf is 9
Number samples : 12544, Duration : 0 seconds and 31346 usecs
This time I will demostrate Fixed-Point FFT running on embedded system.
There's NO FPU on most of embedded CPU and most of implement of FFT using floating point variable.
This means bad performance of FFT calculation, so I found an Fixed-Point FFT library Written by Tom Roberts which fit the requirement.
The purpose of using FFT is to detect DTMF in 16 bits / 8k sample rate raw sound data.
DTMF is multi-frequency signal which mixture of two difference tone.
This is the foundation of modern telephone system.
1209 Hz 1336 Hz 1477 Hz
697 Hz 1 2 3
770 Hz 4 5 6
852 Hz 7 8 9
941 Hz * 0 #
The procdure to detect DTMF is to pass raw sound data into FFT then check frequency domain to determinate which frequencies with higher energy.
1.Fixed-Point FFT
The prototype of fix_fft function
int fix_fft(short fr[], short fi[], short m, short inverse)
fr[] is the real part array, fi[] is the imaginary part array.
m is power of 2 of the array size, the array size must be power of 2.
For example the array size is 256 (2^8) then m is 8.
Pass input sound data into fr[] and leave all zero to fi[]
Return value of fix_fft is useless while forward FFT.
The result of FFT is storing in fr[] and fi[].
2.Phyical of FFT
It's not hard to realize more input data lead to more precision of result.
The input sound data is 16 bit / 8k sample rate. Assume number of input samples is 256 (2^8)
So we have 256 buckets divided over 8khz, each bucket represents 31.25 hz ( 8k hz / 256).
But, the maximum frequency we can measure is half of the sampling rate so if we sample at 8Khz our maximum is 4Khz
(this is called the Nyquist frequency).
0.000000 ~ 31.250000hz
31.250000 ~ 62.500000hz
62.500000 ~ 93.750000hz
93.750000 ~ 125.000000hz
125.000000 ~ 156.250000hz
156.250000 ~ 187.500000hz
187.500000 ~ 218.750000hz
...
...
...
3812.500000 ~ 3843.750000hz
3843.750000 ~ 3875.000000hz
3875.000000 ~ 3906.250000hz
3906.250000 ~ 3937.500000hz
3937.500000 ~ 3968.750000hz
3968.750000 ~ 4000.000000hz
So, the frequency domain is from 0 ~ 4k hz and how about the energy of each frequency range ?
energy = sqrt(fr[i]^2 + fi[i]^2), where i form 0 to 127
Then check the higher energy (Threshold) of frequency and see if the frequency fit the range of DTMF tone.
3.The source code and result
fix_fft.c
dtmf_detect.c
T159.snd
The target machine is MIPS 4KEc running 162Mhz. No FPU support.
Enable DEBUG flag to see what's going on, but terrible performance due to printf()
1.5 second sound data takes more than 4 seconds to process.
$ ./dtmf_detect T159.snd
Detect None ...
Detect None ...
Detect None ...
Detect None ...
687.500000 ~ 718.750000hz : 2838
718.750000 ~ 750.000000hz : 2271
1218.750000 ~ 1250.000000hz : 3761
Max freq : 1218.750000 ~ 1218.750000hz (Value : 3761)
dtmf is 1
687.500000 ~ 718.750000hz : 3915
718.750000 ~ 750.000000hz : 2246
1218.750000 ~ 1250.000000hz : 4853
Max freq : 1218.750000 ~ 1218.750000hz (Value : 4853)
687.500000 ~ 718.750000hz : 3762
718.750000 ~ 750.000000hz : 2243
1218.750000 ~ 1250.000000hz : 6525
Max freq : 1218.750000 ~ 1218.750000hz (Value : 6525)
687.500000 ~ 718.750000hz : 4066
718.750000 ~ 750.000000hz : 2288
1218.750000 ~ 1250.000000hz : 5760
Max freq : 1218.750000 ~ 1218.750000hz (Value : 5760)
687.500000 ~ 718.750000hz : 3601
718.750000 ~ 750.000000hz : 2086
1218.750000 ~ 1250.000000hz : 5968
Max freq : 1218.750000 ~ 1218.750000hz (Value : 5968)
687.500000 ~ 718.750000hz : 4108
718.750000 ~ 750.000000hz : 2375
1218.750000 ~ 1250.000000hz : 6532
Max freq : 1218.750000 ~ 1218.750000hz (Value : 6532)
687.500000 ~ 718.750000hz : 3330
718.750000 ~ 750.000000hz : 2034
1218.750000 ~ 1250.000000hz : 4783
Max freq : 1218.750000 ~ 1218.750000hz (Value : 4783)
687.500000 ~ 718.750000hz : 3717
718.750000 ~ 750.000000hz : 2401
1218.750000 ~ 1250.000000hz : 5406
Max freq : 1218.750000 ~ 1218.750000hz (Value : 5406)
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
750.000000 ~ 781.250000hz : 2635
781.250000 ~ 812.500000hz : 2451
1312.500000 ~ 1343.750000hz : 2238
1343.750000 ~ 1375.000000hz : 2872
Max freq : 1343.750000 ~ 1343.750000hz (Value : 2872)
dtmf is 5
750.000000 ~ 781.250000hz : 3027
781.250000 ~ 812.500000hz : 3084
1312.500000 ~ 1343.750000hz : 2692
1343.750000 ~ 1375.000000hz : 4415
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4415)
750.000000 ~ 781.250000hz : 3119
781.250000 ~ 812.500000hz : 3196
1312.500000 ~ 1343.750000hz : 3174
1343.750000 ~ 1375.000000hz : 4766
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4766)
750.000000 ~ 781.250000hz : 3127
781.250000 ~ 812.500000hz : 3333
1312.500000 ~ 1343.750000hz : 3198
1343.750000 ~ 1375.000000hz : 4750
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4750)
750.000000 ~ 781.250000hz : 3129
781.250000 ~ 812.500000hz : 3451
1312.500000 ~ 1343.750000hz : 2803
1343.750000 ~ 1375.000000hz : 4114
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4114)
750.000000 ~ 781.250000hz : 3143
781.250000 ~ 812.500000hz : 3534
1312.500000 ~ 1343.750000hz : 3393
1343.750000 ~ 1375.000000hz : 4978
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4978)
750.000000 ~ 781.250000hz : 3144
781.250000 ~ 812.500000hz : 3561
1312.500000 ~ 1343.750000hz : 2593
1343.750000 ~ 1375.000000hz : 3631
Max freq : 1343.750000 ~ 1343.750000hz (Value : 3631)
750.000000 ~ 781.250000hz : 3195
781.250000 ~ 812.500000hz : 3544
1312.500000 ~ 1343.750000hz : 3246
1343.750000 ~ 1375.000000hz : 4971
Max freq : 1343.750000 ~ 1343.750000hz (Value : 4971)
1312.500000 ~ 1343.750000hz : 2850
1343.750000 ~ 1375.000000hz : 2935
Max freq : 1343.750000 ~ 1343.750000hz (Value : 2935)
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Detect None ...
843.750000 ~ 875.000000hz : 3998
1468.750000 ~ 1500.000000hz : 5109
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5109)
dtmf is 9
843.750000 ~ 875.000000hz : 4803
1468.750000 ~ 1500.000000hz : 6069
Max freq : 1468.750000 ~ 1468.750000hz (Value : 6069)
843.750000 ~ 875.000000hz : 4620
1468.750000 ~ 1500.000000hz : 5350
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5350)
843.750000 ~ 875.000000hz : 5024
1468.750000 ~ 1500.000000hz : 6536
Max freq : 1468.750000 ~ 1468.750000hz (Value : 6536)
843.750000 ~ 875.000000hz : 4157
1468.750000 ~ 1500.000000hz : 5645
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5645)
843.750000 ~ 875.000000hz : 5140
1468.750000 ~ 1500.000000hz : 5768
Max freq : 1468.750000 ~ 1468.750000hz (Value : 5768)
843.750000 ~ 875.000000hz : 3629
1468.750000 ~ 1500.000000hz : 6446
Max freq : 1468.750000 ~ 1468.750000hz (Value : 6446)
Detect None ...
Detect None ...
Detect None ...
Detect None ...
Number samples : 12544, Duration : 4 seconds and 84537 usecs
Disable DEBUG with good performance.
1.5 second sound data takes 31.346 ms to process.
$ ./dtmf_detect T159.snd
dtmf is 1
dtmf is 5
dtmf is 9
Number samples : 12544, Duration : 0 seconds and 31346 usecs
訂閱：
文章 (Atom)