xiahouzuoxin/fft

fft and cross-correlation

USE GUIDE:

This project use C language to relize FFT algorithm, and then calculate cross-correlation by FFT. Use FFT to calculate cross-correlation will improve the performance from O(N^2) to O(n*log(n))

Fllow steps to use this projects:

1. make
2. make run
3. open matlab and run plot_result.m

UPDATES

1. Add and test function @fft_real and @ifft_real for Real Input Signal, In 2014.04.15
2. Replace @cos and @sin from <math.h> bu using 2 tables, In 2014.04.15

AUTHOR:

[email protected]

2014-04-09

fft's Issues

问下大神，算法转换的结果相关

我用您的算法将一个signed 16bit 44100 hz的正弦波pcm裸数据转换后，输出的结果我怎样能知道这段pcm中有44100hz的声音？测试代码如下：
`void test_file()
{
int i;
int16_t buf;
int fd = open("sin_raw_44100_pcm16bit.aiff", O_RDONLY);
if(fd < 0)
{
printf("open failed.\n");
return;
}
printf("intput:\n");
for ( i=0; i<SAMPLE_NODES; i++ )
{
buf = 0;
read(fd, &buf, 2);
x[i].real = buf/(float)1;//转成0-1间：buf/(float)32767
x[i].imag = 0.0f;
//INPUT[i]=sin(PI_2_i/SAMPLE_NODES)*1024;
printf("%f ", x[i].real);
}
close(fd);

fft(x, SAMPLE_NODES);

printf("\n\n output: \n");
for ( i=0;i<SAMPLE_NODES;i++ )  
{  
    OUTPUT[i] = sqrt(x[i].real*x[i].real + x[i].imag*x[i].imag);
    printf("%d ", OUTPUT[i]);
}
printf("\n\n");

}`
以上代码的输出部分如下，可以看到，幅值的变化范围趋势似乎是正确的：
input:
...省略
output:
338987 340422 344820 352405 363593 379048 399799 427420 464387 514759 585619 690453 858368 1165766 1897827 5795811 4875074 1650577 971440 677722 514404 410764 339350 287308 247794 216847 192012 171678 154763 140485 128308 117809 108676 100675 93616 87338 81743 76717 72191 68091 64368 60976 57869 55022 52402 49977 47744 45672 43749 41960 40291 38729 37269 35902 34619 33410 32272 31203 30191 29232 28330 27476 26661 25887 25153 24459 23794 23163 22558 21980 21430 20910 20406 19924 19459 19020 18594 18186 17797 17418 17055 16710 16373 16050 15740 15439 15150 14870 14601 14339 14086 13842 13607 13377 13156 12941 12735 12533 12338 12148 11965 11786 11612 11444 11280 11124 10965 10815 10671 10526 10387 10251 10125 9991 9868 9745 9627 9509 9398 9285 9180 9072 8969 8867 8775 8672 8578 8488 8396 8314 8220 8139 8062 7985 7896 7827 7752 7672 7602 7534 7466 7387 7325 7254 7192 7139 7060 7006 6944 6885 6825 6771 6717 6653 6608 6551 6526 6460 6407 6355 6316 6263 6225 6168 6112 6081 6033 5978 5956 5906 5862 5816 5774 5757 5704 5676 5627 5586 5560 5522 5500 5464 5424 5377 5351 5326 5281 5252 5222 5181 5167 5120 5112 5084 5048 5022 5011 4965 4928 4928 4882 4864 4832 4830 4767 4768 4754 4726 4690 4639 4628 4595 4580 4575 4526 4512 4500 4481 4468 4445 4432 4393 4389 4351 4347 4333 4315 4276 4244 4230 4230 4198 4193 4183 4148 4144 4124 4088 4083 4072 4057 4047 4021 4021 4002 3988 3960 3952 3941 3918 3901 3902 3872 3849 3836 3822 3811 3816 3797 3769 3745 3760 3716 3732 3700 3686 3680 3673 3659 3641 3638 3608 3625 3609 3582 3579 3572 3549 3549 3532 3521 3506 3512 3489 3483 3467 3456 3455 3442 3432 3422 3407 3406 3386 3388 3370 3371 3351 3340 3338 3336 3330 3313 3290 3292 3285 3272 3264 3266 3262 3249 3241 3216 3207 3202 3220 3197 3195 3187 3205 3185 3148 3161 3133 3132 3170 3138 3104 3117 3065 3080 3108 3075 3104 3046 3052 3068 3044 3074 3012 3092 3034 3015 3017 2953 2975 2989 2974 2998 2971 2964 2990 3023 2922 2935 2930 2917 2932 3013 2929 2991 2867 2955 2947 2912 2853 2887 2908 2917 2870 2882 2850 2821 2821 2945 2853 2810 2975 2763 2882 2784 2742 2925 2848 2860 2761 2796 2819 2789 2900 2858 2764 2857 2842 2844 2833 2814 2812 2704 2679 2813 2767 2813 2839 2772 2766 2816 2759 2767 2666 2704 2798 2696 2593 2773 2773 2655 2777 2740 2752 2691 2729 2699 2643 2692 2737 2696 2616 2710 2629 2625 2756 2620 2540 2723 2632 2844 2625 2640 2723 2522 2659 2682 2436 2661 2561 2797 2616 2490 2488 2693 2678 2652 2630 2535 2721 2641 2607 2485 2606 2543 2583 2662 2533 2726 2751 2530 2700 2625 2592 2778 2590 2663 2462 2598 2640 2494 2611 2636 2573 2595 2621 2436 2678 2574 2628 2434 2560 2542 2571 2458 2597 2731 2526 2488 2644 2661 2718 2521 2562 2565 2796 2603 2342 2566 2574 2675 2557 2498 2695 2594 2607 2613 2608 2595 2696 2499 2558 2676 2575 2567 2343 2605 2798 2567 2565 2526 2734 2648 2639 2486 2524 2729 2596 2457 2570 2542 2559 2434 2627 2574 2678 2436 2620 2595 2572 2635 2611 2494 2640 2598 2462 2663 2590 2778 2592 2625 2700 2529 2751 2726 2533 2662 2582 2543 2606 2485 2607 2641 2721 2535 2630 2652 2678 2693 2488 2490 2616 2797 2561 2661 2436 2682 2659 2522 2723 2640 2625 2844 2632 2723 2539 2620 2756 2625 2629 2710 2616 2696 2737 2692 2643 2699 2729 2691 2752 2740 2777 2655 2773 2773 2593 2696 2798 2704 2666 2767 2759 2816 2766 2772 2839 2813 2767 2813 2679 2704 2812 2814 2833 2844 2842 2857 2764 2858 2900 2789 2819 2796 2761 2860 2848 2925 2742 2784 2882 2763 2975 2810 2853 2945 2821 2821 2850 2882 2870 2917 2908 2887 2853 2912 2947 2955 2867 2991 2929 3013 2932 2917 2930 2935 2922 3023 2990 2964 2971 2998 2974 2989 2975 2953 3017 3015 3034 3092 3012 3074 3044 3068 3051 3046 3104 3075 3108 3080 3065 3117 3104 3138 3170 3132 3133 3161 3147 3185 3206 3187 3195 3197 3220 3202 3207 3215 3241 3249 3262 3266 3264 3272 3285 3291 3290 3313 3330 3336 3338 3340 3351 3371 3370 3388 3386 3406 3407 3422 3432 3442 3455 3456 3467 3483 3488 3512 3506 3521 3531 3549 3549 3572 3578 3581 3607 3619 3615 3640 3643 3660 3674 3681 3687 3700 3732 3716 3760 3746 3769 3797 3816 3811 3822 3836 3849 3872 3902 3900 3917 3940 3951 3959 3987 4001 4019 4018 4038 4064 4074 4084 4089 4125 4144 4149 4184 4193 4198 4231 4230 4244 4276 4315 4333 4347 4351 4389 4393 4432 4445 4468 4481 4500 4512 4526 4575 4580 4595 4628 4639 4691 4726 4754 4768 4767 4830 4832 4864 4882 4928 4928 4965 5011 5022 5048 5084 5112 5120 5167 5181 5222 5252 5281 5326 5351 5377 5424 5464 5500 5522 5560 5586 5627 5676 5704 5757 5774 5816 5862 5906 5956 5978 6033 6081 6112 6168 6225 6263 6316 6355 6407 6460 6526 6551 6608 6653 6717 6771 6825 6885 6944 7006 7060 7139 7192 7254 7325 7387 7466 7534 7602 7672 7752 7827 7896 7985 8062 8139 8220 8314 8396 8488 8578 8672 8775 8867 8969 9072 9180 9286 9398 9509 9627 9745 9868 9991 10125 10251 10387 10526 10671 10815 10965 11124 11280 11444 11612 11786 11965 12148 12338 12533 12735 12942 13156 13377 13607 13842 14086 14339 14601 14870 15150 15439 15740 16050 16373 16710 17056 17418 17797 18186 18594 19020 19459 19924 20406 20910 21429 21980 22558 23163 23794 24459 25153 25887 26661 27476 28330 29232 30191 31203 32272 33410 34619 35902 37269 38729 40291 41960 43749 45672 47744 49977 52402 55022 57869 60976 64368 68091 72191 76717 81743 87338 93615 100674 108676 117809 128308 140485 154763 171678 192012 216847 247794 287308 339350 410764 514404 677721 971439 1650575 4875070 5795808 1897826 1165765 858367 690452 585618 514758 464386 427421 399799 379047 363592 352405 344820 340422

感谢赐教