A folded butterfly module performs a radix-22 butterfly operation, and includes: a buffer operable to store first and second to-be-stored data and output first and second stored data; a first multiplexer operable to output one of the second stored data and input data as first selection data; a butterfly operator performing a radix-2 butterfly operation on the first stored data and the first selection data to generate operation data and the second to-be-stored data; a second multiplexer operable to output one of the input data and the operation data as the first to-be-stored data; a third multiplexer operable to output one of the operation data and the second stored data as second selection data; and a multiplier generating output data that equal a product of the second selection data and twiddle data.