您尚未登录。

楼主 #1 2018-08-20 11:17:43

bunny
会员
注册时间: 2020-05-23
已发帖子: 154
积分: 154

代码超级精简的fft源码,无需移植,代码才80行

先上源代码!

#include <stdio.h>
#include <stdint.h>
#include <math.h>

typedef struct {
    float r;
    float i;
}complex;

static void butter_fly(complex* a, complex* b, const complex* c) {
    complex bc;
    bc.r = b->r * c->r - b->i * c->i;
    bc.i = b->r * c->i + b->i * c->r;
    b->r = a->r - bc.r;
    b->i = a->i - bc.i;
    a->r += bc.r;
    a->i += bc.i;
}

static uint32_t bits_reverse(uint32_t index, uint32_t bits) {
    uint32_t left, right;
    left = index << 16;
    right = index >> 16;
    index = left | right;
    left = (index << 8) & 0xff00ff00;
    right = (index >> 8) & 0x00ff00ff;
    index = left | right;
    left = (index << 4) & 0xf0f0f0f0;
    right = (index >> 4) & 0x0f0f0f0f;
    index = left | right;
    left = (index << 2) & 0xc3c3c3c3;
    right = (index >> 2) & 0x3c3c3c3c;
    index = left | right;
    left = (index << 1) & 0xa5a5a5a5;
    right = (index >> 1) & 0x5a5a5a5a;
    index = left | right;
    return index >> (32 - bits);
}

static void fft_k(complex* dat, const complex* w, uint32_t k, uint32_t k_all) {
    uint32_t i, j;
    complex* dat1;
    k_all = 1 << (k_all - k - 1);
    k = 1 << k;
    dat1 = dat + k;
    for (i = 0; i < k_all; i++) {
        for (j = 0; j < k; j++) {
            butter_fly(dat++, dat1++, w + j * k_all);
        }
        dat += k;
        dat1 += k;
    }
}

void fft_init(complex* w, uint32_t k) {
    float beta = 0.0f, dbeta = 3.1415926535f / k ;
    for ( ; k; k--) {
        w->r = cosf(beta);
        w->i = sinf(beta);
        beta += dbeta;
        w++;
    }
}

void fft(complex* dat, const complex* w, uint32_t k) {
    uint32_t i, j, n;
    complex temp;
    n = 1 << k;
    for (i = 0; i < n; i++) {
        j = bits_reverse(i, k);
        if (i <= j) {
            continue;
        }
        temp = dat[i];
        dat[i] = dat[j];
        dat[j] = temp;
    }
    for (i = 0; i < k; i++) {
        fft_k(dat, w, i, k);
    }
}

再上代码的使用方法:

#define K 4
#define N (1 << K)
static complex w[N / 2];
static complex dat[N];

int main() {
    uint32_t i;
    for (i = 0; i < N; i++) {
        dat[i].r = 0.0f;
        dat[i].i = 0.0f;
    }
    dat[0].r = 1.0f;
    dat[1].r = 1.0f;
    fft_init((complex*)w, N / 2);
    fft((complex*)dat, (const complex*)w, K);
    for (i = 0; i < N; i++) {
        printf((const char*)"dat[%d] = %f + %f * i\n", i, dat[i].r, dat[i].i);
    }
    return 0;
}

输出结果:
TIM20180820111332_20180819-2323.jpg

对比matlab输出结果:
none.jpg

最近编辑记录 xxzouzhichao (2018-08-20 11:23:56)

离线

#2 2018-08-20 11:26:21

演技担当黄晓明
会员
注册时间: 2017-10-17
已发帖子: 184
积分: 122.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

运算速度如何?  和ST的库比较一下哪个快点

最近编辑记录 演技担当黄晓明 (2018-08-20 11:30:37)

离线

#3 2018-08-20 11:30:06

BugActiveDaughter
会员
注册时间: 2017-10-17
已发帖子: 118
积分: 117.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

厉害

离线

楼主 #4 2018-08-20 11:40:24

bunny
会员
注册时间: 2020-05-23
已发帖子: 154
积分: 154

Re: 代码超级精简的fft源码,无需移植,代码才80行

演技担当黄晓明 说:

运算速度如何?  和ST的库比较一下哪个快点

stm32f030 16点fft 400us
stm32f030 64点fft 3900us
stm32f030 128点fft 9200us

开优化后128点fft 8800us

最近编辑记录 xxzouzhichao (2018-08-20 11:43:15)

离线

#5 2018-08-20 11:43:21

晕哥
管理员
注册时间: 2017-09-06
已发帖子: 9,336
积分: 9202

Re: 代码超级精简的fft源码,无需移植,代码才80行

大神这是软硬通吃,我等望尘莫及.





离线

楼主 #6 2018-08-20 11:49:59

bunny
会员
注册时间: 2020-05-23
已发帖子: 154
积分: 154

Re: 代码超级精简的fft源码,无需移植,代码才80行

演技担当黄晓明 说:

运算速度如何?  和ST的库比较一下哪个快点

mdk的库128点fft约6300us

离线

#7 2018-08-20 11:51:57

达克罗德
会员
注册时间: 2018-04-10
已发帖子: 1,138
积分: 1090.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

st的库能不需移植直接给别的CPU跑吗?

离线

楼主 #8 2018-08-20 11:54:34

bunny
会员
注册时间: 2020-05-23
已发帖子: 154
积分: 154

Re: 代码超级精简的fft源码,无需移植,代码才80行

晕哥 说:

大神这是软硬通吃,我等望尘莫及.

2013年毕业前夕照着数字信号处理的书写的,在amobbs上开源了,如今朝花夕拾,优化了一下代码风格,在挖坑网开源

离线

楼主 #9 2018-08-20 11:56:19

bunny
会员
注册时间: 2020-05-23
已发帖子: 154
积分: 154

Re: 代码超级精简的fft源码,无需移植,代码才80行

达克罗德 说:

st的库能不需移植直接给别的CPU跑吗?

我没用过stm的库,我用的mdk自带的dsp库对比的,128点比mdk的库慢了2500us

离线

#10 2018-08-20 23:05:04

sblpp
会员
注册时间: 2018-02-14
已发帖子: 164
积分: 54

Re: 代码超级精简的fft源码,无需移植,代码才80行

感谢楼主分享!牛X的很!

离线

#11 2018-08-21 10:46:39

dgtg
会员
注册时间: 2017-11-08
已发帖子: 257
积分: 216.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

大神! 我等望尘莫及!

离线

楼主 #12 2019-01-11 20:58:57

bunny
会员
注册时间: 2020-05-23
已发帖子: 154
积分: 154

Re: 代码超级精简的fft源码,无需移植,代码才80行

更正一段代码:

static uint32_t bits_reverse(uint32_t index, uint32_t bits) {
    uint32_t left, right;
    left = index << 16;
    right = index >> 16;
    index = left | right;
    left = (index << 8) & 0xff00ff00;
    right = (index >> 8) & 0x00ff00ff;
    index = left | right;
    left = (index << 4) & 0xf0f0f0f0;
    right = (index >> 4) & 0x0f0f0f0f;
    index = left | right;
    left = (index << 2) & 0xc3c3c3c3;
    right = (index >> 2) & 0x3c3c3c3c;
    index = left | right;
    left = (index << 1) & 0xa5a5a5a5;
    right = (index >> 1) & 0x5a5a5a5a;
    index = left | right;
    return index >> (32 - bits);
}

更正后:

static uint32_t bits_reverse(uint32_t index, uint32_t bits) {
    uint32_t left, right;
    left = index << 16;
    right = index >> 16;
    index = left | right;
    left = (index << 8) & 0xff00ff00;
    right = (index >> 8) & 0x00ff00ff;
    index = left | right;
    left = (index << 4) & 0xf0f0f0f0;
    right = (index >> 4) & 0x0f0f0f0f;
    index = left | right;
    left = (index << 2) & 0xc3c3c3c3;
    right = (index >> 2) & 0x3c3c3c3c;
    index = left | right;
    left = (index << 1) & 0xaaaaaaaa;
    right = (index >> 1) & 0x55555555;
    index = left | right;
    return index >> (32 - bits);
}

离线

楼主 #13 2019-01-11 22:07:58

bunny
会员
注册时间: 2020-05-23
已发帖子: 154
积分: 154

Re: 代码超级精简的fft源码,无需移植,代码才80行

xxzouzhichao 说:

更正一段代码:

static uint32_t bits_reverse(uint32_t index, uint32_t bits) {
    uint32_t left, right;
    left = index << 16;
    right = index >> 16;
    index = left | right;
    left = (index << 8) & 0xff00ff00;
    right = (index >> 8) & 0x00ff00ff;
    index = left | right;
    left = (index << 4) & 0xf0f0f0f0;
    right = (index >> 4) & 0x0f0f0f0f;
    index = left | right;
    left = (index << 2) & 0xc3c3c3c3;
    right = (index >> 2) & 0x3c3c3c3c;
    index = left | right;
    left = (index << 1) & 0xa5a5a5a5;
    right = (index >> 1) & 0x5a5a5a5a;
    index = left | right;
    return index >> (32 - bits);
}

更正后:

static uint32_t bits_reverse(uint32_t index, uint32_t bits) {
    uint32_t left, right;
    left = index << 16;
    right = index >> 16;
    index = left | right;
    left = (index << 8) & 0xff00ff00;
    right = (index >> 8) & 0x00ff00ff;
    index = left | right;
    left = (index << 4) & 0xf0f0f0f0;
    right = (index >> 4) & 0x0f0f0f0f;
    index = left | right;
    left = (index << 2) & 0xcccccccc;
    right = (index >> 2) & 0x33333333;
    index = left | right;
    left = (index << 1) & 0xaaaaaaaa;
    right = (index >> 1) & 0x55555555;
    index = left | right;
    return index >> (32 - bits);
}

离线

#14 2019-03-10 10:56:19

tink
会员
注册时间: 2019-03-09
已发帖子: 32
积分: 32

Re: 代码超级精简的fft源码,无需移植,代码才80行

mark

离线

#15 2021-04-20 21:08:13

酷酷酷
会员
注册时间: 2021-04-13
已发帖子: 48
积分: 45

Re: 代码超级精简的fft源码,无需移植,代码才80行

该评论内容与本帖子无关,鼓励各位坑友积极发言讨论与帖子有关的内容!

离线

  • 不通过:与技术无关

#16 2021-04-20 22:09:17

大帅
会员
注册时间: 2019-01-17
已发帖子: 169
积分: 128.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

谢谢分享,虽然做过24点更精简的

离线

#17 2021-04-20 23:11:29

novice
会员
注册时间: 2019-07-26
已发帖子: 112
积分: 93

Re: 代码超级精简的fft源码,无需移植,代码才80行

那个bits_reverse函数如果用编译器的intrinsic替代的话会快很多。

离线

#18 2021-04-20 23:14:53

aozima
会员
所在地: 深圳
注册时间: 2019-05-25
已发帖子: 461
积分: 328.5
个人网站

Re: 代码超级精简的fft源码,无需移植,代码才80行

挺好的,可以方便用于对比学习。

离线

#19 2021-04-22 15:42:16

笨企鹅
会员
注册时间: 2019-10-28
已发帖子: 38
积分: 37.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

谢谢分享,可以方便用于对比学习。

离线

#20 2021-04-26 14:52:27

1847123212
会员
注册时间: 2019-11-21
已发帖子: 69
积分: 45

Re: 代码超级精简的fft源码,无需移植,代码才80行

novice 说:

那个bits_reverse函数如果用编译器的intrinsic替代的话会快很多。

这个支持cotex M0 M3 M4 吗?

离线

#21 2021-04-26 15:58:19

sck852414902
会员
注册时间: 2020-12-23
已发帖子: 12
积分: 18.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

该评论内容与本帖子无关,鼓励各位坑友积极发言讨论与帖子有关的内容!

离线

  • 不通过:与技术无关

#22 2021-04-26 16:11:21

哇酷小二
管理员
所在地: 你猜
注册时间: 2020-04-22
已发帖子: 3,384
积分: 1902
个人网站

Re: 代码超级精简的fft源码,无需移植,代码才80行

sck852414902 说:

mark fft

楼主位有 收藏 功能,感谢支持。





离线

#23 2021-07-30 16:32:20

forstk
会员
注册时间: 2019-10-15
已发帖子: 15
积分: 5.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

niubility!

离线

#24 2021-07-30 20:21:34

来日方长
会员
注册时间: 2019-10-25
已发帖子: 24
积分: 20

Re: 代码超级精简的fft源码,无需移植,代码才80行

牛皮 插眼收藏一波

离线

#25 2021-08-12 09:31:54

nongxiaoming
会员
注册时间: 2019-12-23
已发帖子: 14
积分: 3

Re: 代码超级精简的fft源码,无需移植,代码才80行

arm的dsp库也是源码的,不需要移植,直接用的

离线

#26 2021-08-15 04:05:22

hoel
会员
注册时间: 2019-06-15
已发帖子: 96
积分: 31

Re: 代码超级精简的fft源码,无需移植,代码才80行

nongxiaoming 说:

arm的dsp库也是源码的,不需要移植,直接用的

你可以运行它(修改后)但性能很糟糕,我测试了 800MHZ 的性能甚至低于 100MHz Cortex M4

离线

#27 2021-08-27 10:04:54

小熊猫
会员
注册时间: 2020-05-21
已发帖子: 71
积分: 65.5

Re: 代码超级精简的fft源码,无需移植,代码才80行

该评论内容与本帖子无关,鼓励各位坑友积极发言讨论与帖子有关的内容!

离线

  • 不通过:与技术无关

#28 2024-01-24 15:10:57

yuhang
会员
注册时间: 2024-01-24
已发帖子: 2
积分: 2

Re: 代码超级精简的fft源码,无需移植,代码才80行

这个是要做优化的,利用硬件的加速模块,合理的安排计算的tap

离线

页脚

工信部备案:粤ICP备20025096号 Powered by FluxBB

感谢为中文互联网持续输出优质内容的各位老铁们。 QQ: 516333132, 微信(wechat): whycan_cn (哇酷网/挖坑网/填坑网) service@whycan.cn