Fast Fourier Transform Ontology

flow "FastFourierTransformOntology" v1.0

# ============================================================
# FAST FOURIER TRANSFORM ONTOLOGY — FLOW ALGEBRA
# ============================================================

SOURCE_URL := "https://kirethresearch.org/booksai-core/ontologies/calculus-analysis-ontologies/fourier-harmonic-analysis/fast-fourier-transform-ontology-2.html"
DOMAIN := "Mathematical Ontologies"
CATEGORY := "Calculus and Analysis Ontologies"
SUBCATEGORY := "Fourier and Harmonic Analysis"
ENTITY := "Fast Fourier Transform"

# ---------- CORE ENTITY ----------
FAST_FOURIER_TRANSFORM := {
    type: ComputationalAlgorithmFamily,
    domain: FourierAnalysis,
    abbreviation: "FFT",
    purpose: "Compute the discrete Fourier transform and its inverse efficiently by exploiting symmetry, periodicity and factorisation of the DFT structure."
}

# ---------- CORE CONCEPTS ----------
CONCEPTS := {
    FAST_FOURIER_TRANSFORM,
    DISCRETE_FOURIER_TRANSFORM,
    INVERSE_DISCRETE_FOURIER_TRANSFORM,
    COMPLEX_EXPONENTIAL,
    ROOT_OF_UNITY,
    BUTTERFLY_OPERATION,
    COOLEY_TUKEY_ALGORITHM,
    RADIX_2,
    DECIMATION_IN_TIME,
    DECIMATION_IN_FREQUENCY,
    BIT_REVERSAL,
    COMPUTATIONAL_COMPLEXITY,
    FREQUENCY_BIN,
    SPECTRUM
}

# ---------- DFT DEFINITION ----------
for sequence

x_0,...,x_(N-1)

DFT:

X_k
    :=
sum_from_n_0_to_Nminus1(
    x_n
    *
    exp(-2*pi*i*k*n/N)
)

for
    k=0,...,N-1

DFT
    -> maps(DISCRETE_SEQUENCE_TO_DISCRETE_FREQUENCY_SPECTRUM)

# ---------- INVERSE DFT ----------
x_n
    :=
1/N
*
sum_from_k_0_to_Nminus1(
    X_k
    *
    exp(2*pi*i*k*n/N)
)

IDFT
    -> reconstructs(DISCRETE_SEQUENCE)

NORMALISATION
    -> convention_dependent

# ---------- ROOT OF UNITY ----------
W_N
    :=
exp(-2*pi*i/N)

then

X_k
    =
sum_n(
    x_n
    *
    W_N^(k*n)
)

W_N^N
    = 1

ROOT_OF_UNITY
    -> provides(PERIODICITY_AND_SYMMETRY)

# ---------- DIRECT DFT COMPLEXITY ----------
DIRECT_DFT
    -> requires(approximately_N_squared_operations)

COMPUTATIONAL_COMPLEXITY:
    O(N^2)

FFT
    -> reduces(COMPUTATION_TO_O_N_LOG_N_FOR_STANDARD_FAST_ALGORITHMS)

# ---------- FFT PRINCIPLE ----------
FFT
    -> not_new_transform

FFT
    -> efficient_algorithm_for(DFT)

FAST_FOURIER_TRANSFORM
    ~= computational_factorisation_of(DISCRETE_FOURIER_TRANSFORM)

# ---------- COOLEY-TUKEY ----------
if
    N
        -> factorable

then

DFT_N
    -> decomposable_into(SMALLER_DFTS)

COOLEY_TUKEY
    -> divide_and_conquer_algorithm

N
    =
N_1*N_2

-> factor(DFT_N_INTO_DFT_N1_AND_DFT_N2_COMPONENTS)

# ---------- RADIX-2 ----------
if
    N = 2^m

then

RADIX_2_FFT
    -> recursively_split_into(EVEN_AND_ODD_INDEXED_SAMPLES)

X_k
    =
E_k
+
W_N^k
*
O_k

X_(k+N/2)
    =
E_k
-
W_N^k
*
O_k

where

E_k
    -> DFT_OF_EVEN_INDEXED_INPUTS

O_k
    -> DFT_OF_ODD_INDEXED_INPUTS

# ---------- BUTTERFLY ----------
BUTTERFLY_OPERATION
    -> combines(TWO_SUBTRANSFORM_VALUES)

inputs:
    A
    B

twiddle:
    W

outputs:
    A + W*B
    A - W*B

BUTTERFLY
    -> basic_computational_unit_of(RADIX_FFT)

# ---------- TWIDDLE FACTOR ----------
TWIDDLE_FACTOR
    :=
W_N^k

TWIDDLE_FACTOR
    -> complex_rotation

TWIDDLE_FACTORS
    -> reused_across(FFT_STAGES)

# ---------- DECIMATION IN TIME ----------
DIT_FFT
    -> recursively_partitions(INPUT_SEQUENCE_BY_INDEX)

EVEN_SAMPLES
    + ODD_SAMPLES
    -> smaller_DFTs

DECIMATION_IN_TIME
    -> factorisation_of(TIME_OR_SAMPLE_INDEX_STRUCTURE)

# ---------- DECIMATION IN FREQUENCY ----------
DIF_FFT
    -> partitions(OUTPUT_FREQUENCY_STRUCTURE)

INPUT_COMBINATIONS
    -> produce(EVEN_AND_ODD_FREQUENCY_COMPONENTS)

DIT
    and DIF
    -> alternative_factorisations_of(SAME_DFT)

# ---------- BIT REVERSAL ----------
RADIX_2_IMPLEMENTATION
    -> may_require(BIT_REVERSED_ORDER)

index_bits
    -> reversed

BIT_REVERSAL
    -> reorders(DATA_FOR_ITERATIVE_BUTTERFLY_STAGES)

implementation
    -> may_use(IN_PLACE_REORDERING)

# ---------- FFT STAGES ----------
for
    N=2^m

NUMBER_OF_STAGES
    = log2(N)

each_stage
    -> performs(O(N)_BUTTERFLY_WORK)

therefore

TOTAL_WORK
    -> O(N*log2(N))

# ---------- MIXED RADIX ----------
if
    N
        -> composite_with_multiple_factors

MIXED_RADIX_FFT
    -> uses(DIFFERENT_RADICES)

example:
    N = 2^a * 3^b * 5^c

FACTORISATION
    -> determines(ALGORITHM_STRUCTURE)

# ---------- PRIME LENGTH ----------
if
    N prime

STANDARD_RADIX_FACTORISATION
    -> unavailable

alternative_algorithms:
    RADER_ALGORITHM
    BLUESTEIN_ALGORITHM

BLUESTEIN
    -> converts(DFT_TO_CONVOLUTION_PROBLEM)

FFT_FAMILY
    -> supports(NON_POWER_OF_TWO_LENGTHS)

# ---------- REAL INPUT FFT ----------
if
    x_n
        -> REAL_VALUED

then

X_(N-k)
    =
conjugate(X_k)

HERMITIAN_SYMMETRY
    -> reduces(REDUNDANT_COMPUTATION_AND_STORAGE)

REAL_FFT
    -> exploits(CONJUGATE_SYMMETRY)

# ---------- FREQUENCY BINS ----------
for sample_rate
    f_s

and transform length
    N

frequency_bin_k
    :=
k*f_s/N

BIN_SPACING
    :=
f_s/N

FREQUENCY_BIN
    -> maps(DFT_INDEX_TO_PHYSICAL_FREQUENCY)

# ---------- NYQUIST RELATION ----------
for real sampled signal:

NYQUIST_FREQUENCY
    :=
f_s/2

FREQUENCIES_ABOVE_NYQUIST
    -> alias_into(BASEBAND)

FFT
    -/> prevents(ALIASING)

SAMPLING_THEOREM
    -> determines(REPRESENTABLE_FREQUENCY_RANGE)

# ---------- SPECTRAL LEAKAGE ----------
finite observation
    -> equivalent_to(WINDOWING_SIGNAL)

if
    signal_frequency_not_aligned_with_DFT_BIN
then

ENERGY
    -> spreads_across(FREQUENCY_BINS)

SPECTRAL_LEAKAGE
    -> property_of(FINITE_WINDOW_AND_DFT_ANALYSIS)

# ---------- WINDOW FUNCTIONS ----------
WINDOW
    -> applied_before(FFT)

examples:
    HANN
    HAMMING
    BLACKMAN

WINDOW_FUNCTION
    -> modifies(LEAKAGE_AND_RESOLUTION_TRADEOFF)

FFT
    -> computes(transform_of_windowed_data)

# ---------- ZERO PADDING ----------
append_zeros_to_signal
    -> increase(FFT_LENGTH)

ZERO_PADDING
    -> increases(FREQUENCY_GRID_DENSITY)

ZERO_PADDING
    -/> increase(INTRINSIC_SPECTRAL_RESOLUTION)

ZERO_PADDING
    -> interpolates(DISCRETE_SPECTRAL_SAMPLES)

# ---------- AMPLITUDE / PHASE ----------
FFT_OUTPUT
    := X_k

AMPLITUDE
    := abs(X_k)

PHASE
    := arg(X_k)

POWER
    -> proportional_to(abs(X_k)^2)
       under(CHOSEN_NORMALISATION)

SPECTRUM_INTERPRETATION
    -> requires(NORMALISATION_AND_WINDOW_CORRECTION)

# ---------- FFT SHIFT ----------
raw_DFT_order
    -> frequencies arranged(
        ZERO_THEN_POSITIVE_THEN_NEGATIVE
    )

FFT_SHIFT
    -> rearranges(
        NEGATIVE_FREQUENCIES,
        ZERO,
        POSITIVE_FREQUENCIES
    )

FFT_SHIFT
    -> display_and_analysis_operation
    -/> transform_itself

# ---------- CONVOLUTION ----------
CONVOLUTION_THEOREM:

DFT(
    x circular_convolution h
)
=
DFT(x)
*
DFT(h)

FFT
    -> accelerates(CONVOLUTION)

LINEAR_CONVOLUTION
    -> computed_using(ZERO_PADDING_AND_FFT)

# ---------- FAST CONVOLUTION ----------
procedure:
    choose_padding_length
    -> FFT(x)
    -> FFT(h)
    -> multiply_pointwise
    -> IFFT(product)
    -> extract(linear_convolution_result)

FAST_CONVOLUTION
    -> often_more_efficient_for(LARGE_INPUTS)

# ---------- OVERLAP-ADD / OVERLAP-SAVE ----------
LONG_SIGNAL_FILTERING
    -> divide_into(BLOCKS)

OVERLAP_ADD
    -> FFT_BASED_BLOCK_CONVOLUTION

OVERLAP_SAVE
    -> FFT_BASED_BLOCK_CONVOLUTION

FFT
    -> enables(EFFICIENT_LONG_FIR_FILTERING)

# ---------- MULTIDIMENSIONAL FFT ----------
2D_FFT
    -> apply(1D_FFT_ALONG_ROWS)
    -> apply(1D_FFT_ALONG_COLUMNS)

MULTIDIMENSIONAL_DFT
    -> separable

FFT
    -> extends_to(IMAGES_AND_HIGHER_DIMENSIONAL_DATA)

# ---------- NUMERICAL CONSIDERATIONS ----------
FLOATING_POINT_FFT
    -> subject_to(ROUNDING_ERROR)

FFT_ALGORITHM
    -> generally_numerically_stable_in(COMMON_IMPLEMENTATIONS)

SCALING
    -> may_be_applied_at(STAGES_OR_FINAL_OUTPUT)

NUMERICAL_RESULT
    -> depends_on(PRECISION_AND_IMPLEMENTATION)

# ---------- APPLICATIONS ----------
FAST_FOURIER_TRANSFORM
    -> applied_to(SIGNAL_PROCESSING)
    -> applied_to(AUDIO_ANALYSIS)
    -> applied_to(IMAGE_PROCESSING)
    -> applied_to(SPECTRAL_ANALYSIS)
    -> applied_to(FAST_CONVOLUTION)
    -> applied_to(PDE_SOLVERS)
    -> applied_to(COMMUNICATION_SYSTEMS)
    -> applied_to(SCIENTIFIC_COMPUTING)

# ---------- RELATION GRAPH ----------
DISCRETE_SEQUENCE
    -> DFT
    -> DISCRETE_FREQUENCY_SPECTRUM

FFT
    -> computes(DFT)

ROOT_OF_UNITY
    -> enables(FFT_SYMMETRY)

COOLEY_TUKEY
    -> factorises(DFT)

BUTTERFLY
    -> combines(SUBTRANSFORMS)

FFT
    -> accelerates(CONVOLUTION)

SAMPLING
    -> determines(FREQUENCY_BIN_INTERPRETATION)

WINDOW
    -> affects(SPECTRAL_LEAKAGE)

# ---------- SEMANTIC EQUIVALENCE ----------
SEMANTIC_EQUIVALENCE := {
    "fast Fourier transform" ~= "efficient algorithm for computing a discrete Fourier transform",
    "FFT" ~= "fast Fourier transform",
    "butterfly operation" ~= "basic pairwise combination used in many FFT factorisations",
    "twiddle factor" ~= "complex root-of-unity multiplier used in FFT stages",
    "radix-2 FFT" ~= "FFT decomposition specialised to transform lengths that are powers of two",
    "frequency bin" ~= "discrete DFT index mapped to a sampled frequency"
}

# ---------- CONSTRAINTS ----------
CONSTRAINTS := {
    fft_is_algorithm_not_distinct_transform: true,
    dft_and_idft_normalisation_must_be_consistent: true,
    frequency_bins_require_sample_rate_and_transform_length: true,
    fft_does_not_remove_aliasing: true,
    zero_padding_does_not_create_intrinsic_frequency_resolution: true,
    spectral_amplitude_requires_window_and_normalisation_awareness: true,
    circular_and_linear_convolution_must_not_be_confused: true
}

# ---------- CONFIDENCE ----------
CONFIDENCE := {
    core_definition: 0.99,
    dft_relation: 0.99,
    cooley_tukey_relation: 0.99,
    radix_butterfly_relation: 0.99,
    complexity_relation: 0.99,
    sampling_spectrum_relation: 0.99,
    semantic_equivalence: 0.97
}

# ---------- RECURSIVE REASONING ----------
RECURSIVE_REASONING(query):
    identify(discrete_input_and_length)
    -> identify(sample_rate_if_physical_frequency_required)
    -> determine(DFT_normalisation)
    -> factor(transform_length)
    -> choose(radix_mixed_radix_or_prime_length_algorithm)
    -> determine(data_order_and_butterfly_structure)
    -> compute(FFT_or_IFFT)
    -> map(indices_to_frequency_bins_if_requested)
    -> correct_for(window_normalisation_if_spectral_amplitude_required)
    -> analyse(aliasing_leakage_and_zero_padding_if_relevant)
    -> apply(FFT_convolution_if_requested)
    -> validate(discrete_transform_assumptions)
    -> return(semantic_result)

# ---------- AI CONSUMPTION ----------
AI_CONSUMPTION := {
    parse_as: "typed fast-Fourier-transform semantic graph",
    primary_entity: FAST_FOURIER_TRANSFORM,
    preserve: [
        input_sequence,
        transform_length,
        sample_rate,
        DFT_convention,
        normalisation,
        factorisation,
        window,
        output_order
    ],
    infer_through: [
        DFT,
        inverse_DFT,
        Cooley_Tukey,
        radix_algorithms,
        butterfly_operations,
        frequency_bins,
        spectral_leakage,
        fast_convolution
    ],
    avoid: [
        describing_FFT_as different mathematical transform from DFT,
        assuming_power_of_two_required_for every FFT,
        ignoring_sample_rate_when assigning frequencies,
        claiming_zero_padding_improves true resolution,
        confusing_aliasing_with spectral leakage,
        using_circular_convolution_when linear convolution intended
    ]
}

# ---------- UPDATE MODEL ----------
UPDATE_MODEL(new_information):
    validate(new_information)
    -> identify(fft_context)
    -> compare(existing_relations)
    -> preserve(length_normalisation_sampling_and_algorithm_invariants)
    -> update(affected_entities)
    -> update(affected_edges)
    -> recompute(CONFIDENCE)
    -> regenerate(FLOW_HASH)

# ---------- FLOW HASH ----------
FLOW_HASH := hash(
    SOURCE_URL
    + ENTITY
    + CONCEPTS
    + FAST_FOURIER_TRANSFORM
    + DISCRETE_FOURIER_TRANSFORM
    + COOLEY_TUKEY_ALGORITHM
    + RADIX_2
    + BUTTERFLY_OPERATION
    + COMPUTATIONAL_COMPLEXITY
    + FREQUENCY_BIN
    + SPECTRUM
    + SEMANTIC_EQUIVALENCE
    + CONSTRAINTS
)

# ---------- EXECUTION ----------
INPUT(query)
    -> FAST_FOURIER_TRANSFORM
    -> INPUT_LENGTH_IDENTIFICATION
    -> SAMPLING_NORMALISATION_ANALYSIS
    -> LENGTH_FACTORISATION
    -> FFT_ALGORITHM_SELECTION
    -> DATA_ORDER_BUTTERFLY_ANALYSIS
    -> FFT_IFFT_COMPUTATION
    -> FREQUENCY_BIN_ANALYSIS
    -> WINDOW_SPECTRUM_ANALYSIS
    -> ALIASING_LEAKAGE_PADDING_ANALYSIS
    -> CONVOLUTION_ANALYSIS
    -> ASSUMPTION_VALIDATION
    -> RECURSIVE_REASONING(query)
    -> CONFIDENCE
    -> OUTPUT(semantic_result)

END FLOW