103 fft-4-tt

103 : fft-4-tt

Design render
  • Author: Foivos Chaloftis
  • Description: A simple FFT Calculator downscaled for deployment with the Tiny Tapeout 04 Physical PCB
  • GitHub repository
  • Clock: 1000 Hz

How it works

This is a simplified Fast Fourier Transform implementation (based on the radix-2 Cooley–Tukey algorithm) that can be scaled-up to larger precision and more points. Designed for low complexity circuits requiring large DFT calculations, sacrificing speed. This specific implementation offers 4-point, 8-point, and 16-point versions of the Fourier Transform, while having the precision set to 4 bits.

For the first part, it integrates reverse bit ordering, placing data to their corresponding memory address as they are being input from the user. Afterwards, data, along with the weights, are fed through a single butterfly module (2-point DFT), responsible for all the calculations, controlled by the control unit which delegates the data reading/writing throughout each clock cycle. Once finished, the data output process begins. The FFT is calculated using signed fixed-point arithmetic. The decimal range is between -1 and 0.875. Any results bigger/smaller than the previous, will be capped at the maximum/minimum value possible.

How to test

Connect the proper I/O for inserting data/controlling the circuit, and displaying/reading output. Follow the steps as shown below:

  • Step 1: Reset the IC by momentarily enabling the rst signal.
  • Step 2: Cycle through the 3 modes (0: 4-point, 1: 8-point, 2: 16-point FFT) shown on the 7-segment display using the mode_change pin, and select the mode you wish to use by using the enter pin.
  • Step 3: Insert data in the specified format (Q1.3 real and Q1.3 imaginary), and use enter pin to input each point. After inserting all data, the FFT computation will begin.
  • Step 4: Use the enter pin again to read the data from the output pins.
  • Step 5: Once all data points are read, the display will show an F, indicating that the data reading is finished.
  • Step 6: Use enter pin to repeat process form Step 2.

External hardware

2x buttons, Way to input 8-bit data, Way to display/read 8-bit data

IO

#InputOutputBidirectional
0imaginary_in[0]segment a/imaginary_out[0]mode_change
1imaginary_in[1]segment b/imaginary_out[1]enter
2imaginary_in[2]segment c/imaginary_out[2]
3imaginary_in[3]segment d/imaginary_out[3]
4real_in[0]segment e/real_out[0]
5real_in[1]segment f/real_out[1]
6real_in[2]segment g/real_out[2]
7real_in[3]dot/real_out[3]

Chip location

Controller Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux tt_um_chip_rom (Chip ROM) tt_um_factory_test (TinyTapeout 04 Factory Test) tt_um_vga_clock (VGA clock) tt_um_seven_segment_seconds (7 segment seconds) tt_um_marno_factorize (Number Factorizer) tt_um_sorter (Odd even sorter) tt_um_bulls_and_cows (The Bulls and Cows game) tt_um_loopback (TinyTapeout 04 Loopback Test Module) tt_um_devinatkin_arduino_vga (VGA Output for Arduino) tt_um_wokwi_371604537887211521 (Digital Cipher & Interlock System) tt_um_urish_simon (Simon Says game) tt_um_wokwi_372184284115580929 (YKM 7-seg driver) tt_um_currymottled (Configurable PID Block) tt_um_yeokm1_pwm_audio (PWM audio) tt_um_dcb277_ALU (4-bit ALU) tt_um_rgb_mixer (RGB Mixer) tt_um_loopback (TinyTapeout 04 Loopback Test Module) tt_um_algofoogle_raybox_zero (raybox-zero) tt_um_morningjava_top (ChipTune) tt_um_loopback (TinyTapeout 04 Loopback Test Module) tt_um_eldritch_pwm_peripheral (OpenSource PWM Peripheral) tt_um_phansel_laplace_lut (Experiment Number Six: Laplace LUT) tt_um_ks_pyamnihc (Karplus-Strong String Synthesis) tt_um_dlmiles_tt04_poc_usbdev (USB Device) tt_um_thorkn_pwmaudio (Audio-PWM-Synth) tt_um_wokwi_374029622762967041 (German Traffic Light) tt_um_dandy_dance (Dandy VGA) tt_um_robojan_top (Tiny Breakout) tt_um_vc_cpu (VC 16-bit CPU) tt_um_MichaelBell_nanoV (Risc-V Nano V) tt_um_urish_usb_cdc (USB CDC (Serial)) tt_um_tiny_processor (Tiny processor) tt_um_f_hal_fft (fft-4-tt) tt_um_tomkeddie_a (LED Panel Driver) tt_um_wokwi_370722051572189185 (OSU Counter) tt_um_wokwi_370796071922577409 (Even digits) tt_um_wokwi_370709383347782657 (Traffic light) tt_um_wokwi_371425977920989185 (Tutorial4) tt_um_riceshelley_tinyFPGA (Grain-Flex-FPGA) tt_um_mgyenik_bfcpu (BFCPU) tt_um_machinaut_systolic (AI Decelerator) tt_um_wokwi_374140166551523329 (Tiny (3-bit) LFSR) tt_um_jk2102 (Pulsed Plasma Thruster (PPT) Controller) tt_um_jayraj4021_SAP1_cpu (SAP-1 CPU) tt_um_wokwi_370533670565165057 (Impulse counter) tt_um_ashleyjr_delay_line (Delay Line) tt_um_simplepiano (Simple Piano) tt_um_wokwi_374292646686728193 (Ripple-Carry Adder) tt_um_led_multiplexer_display (Led Multiplexer Display) tt_um_mjbella_led_matrix_driver (LED Matrix Driver) tt_um_fifo_stevej (8-bit FIFO with depth 16.) tt_um_robojan_pong_top (Pong) tt_um_wokwi_374962052813090817 (8 panel display"") tt_um_wokwi_370690644715216897 (Traffic Light) tt_um_wokwi_374494377414857729 (Model Railway turntable polarity controller) tt_um_wokwi_347144898258928211 (Customizable UART string tx) tt_um_wokwi_347497504164545108 (7-Seg 'Tiny Tapeout' Display) tt_um_wokwi_347140425276981843 (UART character tx) tt_um_wokwi_347417602591556180 (Padlock) tt_um_noritsuna_8bitcounter_AI (8bits Counter by AI) tt_um_fm_transmitter (FM Transmitter) tt_um_wokwi_369864099838656513 (Test 4x4 memory) tt_um_htfab_rotfpga2 (ROTFPGA v2) tt_um_losaias (Arithmetic logic unit of four operations between two 8-bit numbers) tt_um_fir_top (FIR Filter) tt_um_santacrc_tamagotchi (Tamagotchi) tt_um_4_LUT_Baungarten (LFMPDM (Lightning Fast Matrix Programmable Design Module)) tt_um_RELOG_10M_Juan_Garcial (7 SEGMENTS CLOCK) tt_um_MultiPatternLEDSequencer_RSYO3000 (Multi Pattern LED Sequencer) tt_um_pwm (Generador de PWM) tt_um_chip_SP_measure_delay (Multi stage path for delay measurements.) tt_um_chip_SP_Soy_de_Zacapa (ASCII Text Printer Circuit) tt_um_fing_synchronizer_hga (Clock synchronizer) tt_um_db_PWM (Simple PWM Generator) tt_um_RS_Vfreq (CLK Frequency Divider) tt_um_ja_TrafficLight (UIS Traffic Light) tt_um_adder_NestorMatajira (4 bit adder ) tt_um_ALU_NicolasOrcasitas (8-bit ALU) tt_um_ccollatz_SergioOliveros (Collatz Conjecture) tt_um_wokwi_370011087462055937 (8 bit 4 data sorting network) tt_um_wokwi_374968111036708865 (BCD to 7 segments) tt_um_wokwi_374967675785369601 (4 bit full adder) tt_um_wokwi_374974793636964353 (Circuito Religioso) tt_um_wokwi_374815911155542017 (Demultiplexor NAND) tt_um_wokwi_374903567624066049 (Sumador/Sustractor de 3 bit con acarreo y prestamo) tt_um_wokwi_374515580784897025 (Hardware Lock) tt_um_wokwi_374909346558831617 (Custom falling and rising edge detection) tt_um_alu (4-bit-alu) tt_um_pong_neopixel (Angardo's pong) tt_um_LEOGLM_hamming_code_top ((11,7) hamming code encoder and decoder with UART) tt_um_adriannovosel_top (Impulse counter) tt_um_wokwi_374969806854695937 (State machine of an impulse counter) tt_um_wokwi_375061599421794305 (Logic Circuit 1) tt_um_biased_trng (Variable Duty-Cycle TRNG) tt_um_top (Modem Multimodo) tt_um_wokwi_372347167704674305 (SAR ADC Backend) tt_um_wokwi_375176944142127105 (FCFM 7-segment display) tt_um_rodrigomunoz1_rotempsensor_top (another ring oscillator based temperature sensor) tt_um_USM_temp_sens_hyst (RO-based temperature sensor with hysteresis) tt_um_FSM (Microrobotics FSM) tt_um_wokwi_375042398768251905 (MINI ALU) tt_um_wokwi_374778387606763521 (PWM Quisquilloso) tt_um_CPU (CPU 8 bit) tt_um_simple_processor_pablopabota (A Risc-V Instruction memory i2c programmer) tt_um_wokwi_375246321309880321 (IFSC 6-bit Locker) tt_um_wokwi_375217288209912833 (Randomizer and status checker) tt_um_wokwi_375245713375900673 (Simulador de cruzamento de semáforo) tt_um_wokwi_374636462642973697 (Full_adder_carry_juang_garzons) tt_um_ternaryPC_radixconvert (4-trit balanced ternary program counter and convertor) tt_um_darkfsegura_collatz (uDATAPATH_Collatz) tt_um_wokwi_375174630101280769 (Adder) tt_um_wokwi_375163050120587265 (Binary to 7 segment) tt_um_wokwi_375165100039571457 (Neuron) tt_um_silva (Later) tt_um_shift (serializer) tt_um_alu4_alonso59 (4-bits 1-channel PWM and ALU 4 bits) tt_um_mod_u_cnt_BCD (up-down counter with parallel load and BCD output) tt_um_ciro (Later) tt_um_control (Contador con carga) tt_um_onehot (onehot_decoder) tt_um_santiago (CDMA Transmitter/Receiver) tt_um_divider_urielcho (clock divider) tt_um_pwl_RaulprTech (reciprocal) tt_um_fabian (Later) tt_um_thezoq2_tmng (Time Multiplexed Nand-gate) tt_um_uninorte (Octal classifier) tt_um_dlmiles_muldiv4 (MULDIV unit (4-bit signed/unsigned)) tt_um_rs_write_decodifier_fjrn_cinvestav (RS Write Decodifier) tt_um_BounceFSM_RSX92 (Password FSM) tt_um_priority_decoder_Juan_Garcial (Priority e) tt_um_FreqMeter_Juan_Garcial (frecuencimeter) tt_um_sahrdayalfsr (lfsr random number generator) tt_um_i2c (i2c_6 bits) tt_um_wokwi_375227079413963777 (Fastest Finger) tt_um_wokwi_375300958229329921 (Fastest Finger (Clocked)) tt_um_zeptobars (Oscillators II) tt_um_rebot449_lingret_ALU_Top (Simple ALU) tt_um_loopback (TinyTapeout 04 Loopback Test Module) tt_um_wokwi_375288605206694913 (Adjustable Frequency LED Chaser) tt_um_wokwi_375310871188385793 (Simple QSPI DAC) tt_um_quardinlyttle_top (AQALU) tt_um_wokwi_375326293008530433 (Simple TMR) tt_um_chiplet_jtag (Poor Person's Boundary Scan) tt_um_wokwi_375248885704300545 (Probador de lógica básico) tt_um_rejunity_telluride2023_neuron (LIF Neuron, Telluride 2023) tt_um_kpwebb_adder (rusty_adder) Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available