Fast Furie Transform (FFT)

 Thuật toán thực hiện chuyển đổi Fourier nhanh (FFT) cần thực hiện phép toán đảo bít chỉ số mảng dữ liệu. Đảo bít một số nguyên có nghĩa là thay đổi vị trí các bít từ trái sang phải thành từ phải sang trái. Ví dụ: 100 (số 4 thập phân) thành 001 (số 1 thập phân). Hãy viết hàm đảo bít một số nguyên biểu diễn bằng n bit.

Mô tả thuật toán Fast Furie Transform(FFT):

VD:Giả sử ta có số nguyên kiểu char biểu diễn bằng 8 bit: 11110000. Ta thực hiện việc đảo bit để thu được 1 số :00001111.

Phương pháp giải:

1.Đầu tiên ta đảo vị trí các bit liền kề nhau(cách nhau 1 đơn vị): bit 0 với bit 1, bit 2 với bit 3, ……Ta thu được kết quả: 11110000.

2.Tiếp theo ta đảo vị trí các bit có khoảng cách với nhau là 2: bít 0 với 2, 1 với 3,…..Ta thu được kết quả :11110000.

3 . Ta tiếp tục đổi vị trí các bít có khoảng cách vơi nhau là 4: bít 0 với bít 4, 1 với bít 5, 2 với bít 6, 3 với bít 7. Ta thu được kết quả: 00001111.

Vậy ta thu được một dãy bí mới là dãy bít đảo của dãy ban đầu: 00001111.

·         Với số nguyên 8 (1 byte) bít ta cần đảo vị trí 3 lần như trên.

·         Với số nguyên 16 (2 byte) bít ta cần thực hiện đảo vị trí các bit có khoảng cách là 8.

·         Với số nguyên 32 bít (4 byte) ta cần thực hiện đảo vị trí các bít co khoảng cách là 16.

Thuật toán:  Dựa vào cách làm như trên ta có thuật toán như sau

Giả sử ta có số nguyên kiểu char biểu diễn bằng 8 bít: 11001100. Ta tách chuỗi bít thành 2 chuỗi:

·         Chuỗi thứ nhất: Gồm các bít được đổi chỗ: 1010 (Ở lần đổi chỗ thứ nhất các bít cách nhau 1) gồm bit 0,2,4,6.Sau đó ta chèn dãy bít “0” vào, ta thu được 1 chuỗi gồm 8 bit như sau: 10001000 (Các bít “0” chèn vào được tô màu đỏ)

·         Chuỗi thứ 2: Gồm các bít bị đổi chỗ :1010 (Các bít 1,3,5,7). Sau đó ta cũng chèn dãy bít “0” vào chuỗi thứ 2, ta thu được chuỗi bít sau: 01000100

Bước tiếp theo ta dịch phải chuỗi bít thứ nhất, và dịch trái chuỗi bít thứ 2 sau đó “OR” hai chuỗi bít này với nhau:

·         Dịch phải chuỗi 1: 01000100

·         Dịch trái chuỗi 2:   10001000

·         OR hai chuỗi với nhau ta thu được: 11001100

Cứ làm như vậy cuối cùng ta thu được dãy bít mới là dãy bít đảo của dãy ban đầu: 00110011

Phần code: Viết bằng C

#include<stdio.h>

////  Thuật toán Fast Furie Transform đảo bít số nguyên kiểu int (4byte) //////

int Fast_Furie_Transform(int x)

{

                x=((x&0x55555555)<<1)|((x&0xAAAAAAAA)>>1);

                //x&0x55555555: Lấy vị trí các bít bị đổi chỗ//x&0xAAAAAAAA: Lấy vị trí các bít được đổi chỗ //

                // Khoảng cách giữa các bít la 1

               

                x=((x&0x33333333)<<2)|((x&0xCCCCCCCC)>>2);

                // Khoảng cách giữa các bít là 2 ///

                x=((x&0x0F0F0F0F)<<4)|((x&0xF0F0F0F0)>>4);

                // Khoảng cách giữa các bít là 4 ///

                x=((x&0x00FF00FF)<<8)|((x&0xFF00FF00)>>8);

                // Khoảng cách giữa các bít là 8 ///

                x=((x&0x0000FFFF)<<16)|((x&0xFFFF0000)>>16);

                // Khoảng cách giữa các bít là 16 ///

                return x;

}

// Hàm main()

int main(int argc, char *argv[])

{

                int x=0x12345678;// Khai báo 1 số nguyên x dạng thập lục phân

                int y = Fast_Furie_Transform(x);

                printf("\nSau khi dao bit ta thu duoc: %p\n",Fast_Furie_Transform(x));

                printf("\nSau khi dao lai: %p\n", Fast_Furie_Transform(y));

               //  “%p” : Hiển thị các số ở dạng thập lục phân

               

                return 0;

}