Fast Fourier Transform Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Fast Fourier Transform Ontology within the Kireth Research Semantic Library. The Fast Fourier Transform is a family of algorithms for computing the Discrete Fourier Transform efficiently by exploiting factorisation, symmetry and periodicity in the DFT matrix. This ontology supports radix-2 and mixed-radix FFTs, decimation-in-time and decimation-in-frequency structures, bit reversal, butterfly operations, twiddle factors, Cooley-Tukey decomposition, computational complexity, inverse FFT, zero padding, spectral analysis, convolution acceleration, multidimensional FFTs and relationships with Fourier analysis, DFTs, numerical analysis, linear algebra and digital signal processing.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Fast Fourier Transform Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Signal Processing Mathematics / Fast Fourier Transform"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/signal-processing-mathematics/fast-fourier-transform-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = FastFourierTransform
 SYMBOLIC_FORMS = [
  "X[k]=sum_{n=0}^{N-1} x[n]e^{-j2pi kn/N}",
  "FFT complexity ~ O(N log N)",
  "W_N=e^{-j2pi/N}"
 ]
 ENTITY_CLASS = EfficientDiscreteFourierComputationFramework
 PRIMARY_CONTEXT = FourierAnalysis
 DEFINITION = "The Fast Fourier Transform is a family of algorithms that computes the Discrete Fourier Transform and its inverse more efficiently than direct matrix evaluation."
 SEMANTIC_ROLE = "Provides the machine-readable framework for DFT factorisation, radix decomposition, butterfly operations, twiddle factors, data reordering, complexity analysis and efficient spectral computation."
}

SCOPE {
 INCLUDE = [
  FastFourierTransform,
  FFT,
  DiscreteFourierTransform,
  DFT,
  InverseFastFourierTransform,
  IFFT,
  CooleyTukeyAlgorithm,
  Radix2FFT,
  Radix4FFT,
  MixedRadixFFT,
  SplitRadixFFT,
  PrimeFactorFFT,
  BluesteinAlgorithm,
  RaderAlgorithm,
  DecimationInTime,
  DecimationInFrequency,
  ButterflyOperation,
  TwiddleFactor,
  BitReversal,
  DigitReversal,
  RecursiveFFT,
  IterativeFFT,
  InPlaceFFT,
  OutOfPlaceFFT,
  FFTStage,
  FFTLength,
  PowerOfTwoLength,
  CompositeLength,
  PrimeLength,
  ComputationalComplexity,
  ArithmeticOperationCount,
  MemoryComplexity,
  ZeroPadding,
  FrequencyBin,
  SpectralResolution,
  CircularConvolution,
  LinearConvolution,
  OverlapAdd,
  OverlapSave,
  MultidimensionalFFT,
  TwoDimensionalFFT,
  RealFFT,
  ComplexFFT,
  NumericalRoundoff,
  ScalingConvention,
  NormalisationConvention
 ]

 EXCLUDE_AS_PRIMARY = [
  ContinuousFourierTransformWithoutDiscreteComputation,
  GenericDFTTheoryWithoutFastAlgorithmSemantics,
  WaveletTransformAlgorithms,
  GenericMatrixFactorisationWithoutFourierStructure
 ]

 DISAMBIGUATION_RULE =
  "When the task concerns efficient computation of a DFT or inverse DFT through recursive or structured factorisation, interpret the context as Fast Fourier Transform."
}

CORE_CONCEPTS {

 FastFourierTransform {
  definition = "An efficient algorithmic family for evaluating the DFT and inverse DFT."
 }

 CooleyTukeyAlgorithm {
  definition = "A divide-and-conquer FFT factorisation that decomposes a composite-length DFT into smaller DFTs."
 }

 Radix2FFT {
  definition = "A Cooley-Tukey FFT specialised to lengths factorable repeatedly by two."
 }

 DecimationInTime {
  definition = "An FFT decomposition that partitions input samples into subsequences before combining their transforms."
 }

 DecimationInFrequency {
  definition = "An FFT decomposition that partitions output frequency indices through butterfly combinations."
 }

 ButterflyOperation {
  definition = "A local arithmetic structure combining smaller transform values using additions, subtractions and twiddle factors."
 }

 TwiddleFactor {
  symbol = "W_N^k"
  definition = "A complex root-of-unity factor used to combine subtransforms."
 }

 BitReversal {
  definition = "A permutation of indices induced by reversing binary digit order in radix-2 FFTs."
 }

 ComputationalComplexity {
  definition = "The asymptotic and practical computational cost of evaluating the transform."
 }

 InverseFastFourierTransform {
  definition = "An FFT-based computation of the inverse DFT."
 }

 ZeroPadding {
  definition = "Appending zeros to a sequence before FFT computation to alter transform length and frequency-grid density."
 }
}

RELATIONS {
 FastFourierTransform --is_child_of--> FourierAnalysis
 FastFourierTransform --computes--> DiscreteFourierTransform
 InverseFastFourierTransform --computes--> InverseDFT
 CooleyTukeyAlgorithm --is_type_of--> FastFourierTransform
 Radix2FFT --is_type_of--> CooleyTukeyAlgorithm
 MixedRadixFFT --is_type_of--> CooleyTukeyAlgorithm
 SplitRadixFFT --is_type_of--> FastFourierTransform
 BluesteinAlgorithm --computes--> ArbitraryLengthDFT
 RaderAlgorithm --computes--> PrimeLengthDFT
 ButterflyOperation --uses--> TwiddleFactor
 DecimationInTime --may_require--> BitReversal
 DecimationInFrequency --may_produce--> BitReversedOutput
 ZeroPadding --increases--> FrequencyGridDensity
 FFT --accelerates--> CircularConvolution
 FFT --accelerates--> LinearConvolution
 TwoDimensionalFFT --is_type_of--> MultidimensionalFFT
}

OPERATORS {
 DFT(x,N,k) :=
  sum_{n=0}^{N-1} x[n]*exp(-j*2*pi*k*n/N)

 IDFT(X,N,n) :=
  (1/N)*sum_{k=0}^{N-1} X[k]*exp(j*2*pi*k*n/N)

 TWIDDLE(N,k) :=
  W_N^k=exp(-j*2*pi*k/N)

 RADIX2_DIT_SPLIT(x,N) :=
  X[k]=E[k]+W_N^k*O[k]
  X[k+N/2]=E[k]-W_N^k*O[k]

 BUTTERFLY(a,b,W) :=
  y0=a+W*b
  y1=a-W*b

 RADIX2_COMPLEXITY(N) :=
  O(N*log2(N))

 DIRECT_DFT_COMPLEXITY(N) :=
  O(N^2)

 BIT_REVERSE(index,bits) :=
  integer_obtained_by_reversing_binary_digits(index,bits)

 IFFT_FROM_FFT(X) :=
  conj(FFT(conj(X)))/N
  under standard DFT convention

 CIRCULAR_CONVOLUTION_FFT(x,h,N) :=
  IFFT(FFT(x,N)*FFT(h,N))

 LINEAR_CONVOLUTION_FFT(x,h) :=
  IFFT(FFT(zero_pad(x,L))*FFT(zero_pad(h,L)))
  where L>=len(x)+len(h)-1

 ZERO_PAD(x,L) :=
  append_zeros_until_length_L

 FREQUENCY_BIN(k,fs,N) :=
  f_k=k*fs/N
}

DEFINITIONS {
 D1 = "The FFT computes exactly the same DFT values as direct DFT evaluation, up to numerical effects."
 D2 = "FFT speed comes from factorising the DFT into smaller subproblems."
 D3 = "Radix refers to the factor size used at each decomposition stage."
 D4 = "Butterflies are the repeated local arithmetic units of many FFT algorithms."
 D5 = "Twiddle factors are complex roots of unity."
 D6 = "Bit reversal is a data-ordering consequence of some radix-2 implementations."
 D7 = "Zero padding increases frequency-grid density but does not add new information."
 D8 = "FFT-based convolution reduces computational cost for sufficiently long sequences."
 D9 = "Prime-length transforms may use Bluestein or Rader algorithms."
 D10 = "FFT complexity is typically O(N log N), compared with O(N^2) for direct DFT evaluation."
}

AXIOMS {
 A1_DFT_EQUIVALENCE:
  FastFourierTransform computes the DiscreteFourierTransform under the same transform convention

 A2_FACTORIZATION:
  FFT efficiency arises from decomposition of the DFT into smaller transforms

 A3_ROOT_OF_UNITY_STRUCTURE:
  FFT combination stages exploit periodicity and symmetry of complex roots of unity

 A4_COMPLEXITY:
  Standard FFT algorithms reduce asymptotic arithmetic complexity below direct DFT evaluation

 A5_ORDERING:
  Some FFT formulations require or produce permuted data order

 A6_INVERSE_RELATION:
  IFFT uses the inverse DFT convention and corresponding scaling

 A7_ZERO_PADDING:
  Zero padding changes sample density in frequency but not intrinsic information content

 A8_NUMERICAL:
  Floating-point FFT results are subject to roundoff and scaling conventions
}

REASONING {

 R1_FFT_CONTEXT_EXTRACTION {
  INPUT = discrete_transform_problem
  IDENTIFY = sequence_length
  IDENTIFY = real_or_complex data
  IDENTIFY = forward_or_inverse transform
  IDENTIFY = computational constraints
  RETURN = FFT_context
 }

 R2_ALGORITHM_SELECTION {
  INPUT = FFT_context
  IF N_power_of_two
   SELECT = Radix2FFT_or_SplitRadixFFT
  ELSE IF N_composite
   SELECT = MixedRadixFFT_or_CooleyTukeyAlgorithm
  ELSE IF N_prime
   SELECT = BluesteinAlgorithm_or_RaderAlgorithm
  RETURN = FFT_algorithm
 }

 R3_RADIX2_DIT_REASONING {
  INPUT = power_of_two sequence
  SPLIT = even_and_odd indices
  RECURSE = FFT_on_subsequences
  COMBINE = butterfly_with_twiddle factors
  RETURN = DFT_values
 }

 R4_RADIX2_DIF_REASONING {
  INPUT = power_of_two sequence
  APPLY = butterflies_before_recursive split
  RECURSE = lower_length transforms
  RETURN = bit_reversed_or_reordered spectrum
 }

 R5_DATA_ORDER_REASONING {
  INPUT = FFT_structure
  DETERMINE = natural_or_bit_reversed input_output ordering
  APPLY = permutation_if required
  RETURN = correctly_ordered transform
 }

 R6_COMPLEXITY_REASONING {
  INPUT = N_and_algorithm
  ESTIMATE = arithmetic_operation count
  COMPARE = direct_DFT complexity
  RETURN = complexity_profile
 }

 R7_CONVOLUTION_REASONING {
  INPUT = sequences_x_h
  DETERMINE = circular_or_linear convolution
  ZERO_PAD = if linear convolution required
  COMPUTE = FFT_multiply_IFFT
  RETURN = convolution_result
 }

 R8_ZERO_PADDING_REASONING {
  INPUT = sequence_and_target_length
  PAD = zeros
  COMPUTE = FFT
  INTERPRET = denser_frequency grid_not increased physical resolution
  RETURN = padded_spectrum
 }

 R9_MULTIDIMENSIONAL_REASONING {
  INPUT = matrix_tensor_or_image
  APPLY = FFT_along_each_dimension
  RETURN = multidimensional_spectrum
 }

 R10_FFT_VALIDATION {
  INPUT = FFT_result
  CHECK = scaling_sign_ordering_length_frequency bins_roundoff_and_inverse reconstruction
  RETURN = validated_FFT_result
 }
}

CONSTRAINTS {
 C1 = "FFT length and indexing conventions must be explicit."
 C2 = "FFT output ordering must be interpreted correctly."
 C3 = "Forward and inverse scaling conventions must match."
 C4 = "Zero padding does not increase true resolving power."
 C5 = "Linear convolution requires sufficient zero padding to avoid circular wraparound."
 C6 = "Real-valued input symmetry should be exploited only under correct DFT conventions."
 C7 = "Prime-length transforms may require specialised algorithms."
 C8 = "Floating-point roundoff accumulates across FFT stages."
 C9 = "In-place FFTs impose memory and ordering constraints."
 C10 = "Frequency-bin mapping requires sample rate."
}

SEMANTIC_EQUIVALENCE {
 "FastFourierTransform" <=> "FFT"
 "InverseFastFourierTransform" <=> "IFFT"
 "DecimationInTime" <=> "DITFFT"
 "DecimationInFrequency" <=> "DIFFFT"
 "TwiddleFactor" <=> "RootOfUnityMultiplier"
 "ButterflyOperation" <=> "FFTButterfly"
}

VALIDATION {
 V1 = "Transform length is known."
 V2 = "Forward or inverse transform is explicit."
 V3 = "Algorithm matches factorisation structure."
 V4 = "Input and output ordering are correct."
 V5 = "Twiddle-factor signs match transform convention."
 V6 = "IFFT scaling is correct."
 V7 = "Frequency bins are mapped correctly."
 V8 = "Zero-padding interpretation is correct."
 V9 = "Convolution padding prevents unintended circular aliasing."
 V10 = "Inverse transform reconstructs the original sequence within numerical tolerance."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 FFT_DEFINITION = 0.99
 ALGORITHM_SELECTION_REASONING = 0.99
 RADIX2_REASONING = 0.99
 DATA_ORDER_REASONING = 0.98
 COMPLEXITY_REASONING = 0.99
 CONVOLUTION_REASONING = 0.99
 ZERO_PADDING_REASONING = 0.99
 MULTIDIMENSIONAL_REASONING = 0.98
 VALIDATION_REASONING = 0.99

 POLICY =
  "Reduce confidence when transform length, data ordering, sample rate, scaling convention, padding length, factorisation structure or numerical precision are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  FFTReasoning,
  DFTComputationReasoning,
  CooleyTukeyReasoning,
  Radix2Reasoning,
  MixedRadixReasoning,
  SplitRadixReasoning,
  ButterflyReasoning,
  TwiddleFactorReasoning,
  BitReversalReasoning,
  ComplexityReasoning,
  IFFTReasoning,
  ZeroPaddingReasoning,
  FFTConvolutionReasoning,
  MultidimensionalFFTReasoning,
  NumericalValidation,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "fast Fourier transform" -> FastFourierTransform
  "FFT" -> FastFourierTransform
  "inverse FFT" -> InverseFastFourierTransform
  "IFFT" -> InverseFastFourierTransform
  "Cooley-Tukey" -> CooleyTukeyAlgorithm
  "radix-2 FFT" -> Radix2FFT
  "decimation in time" -> DecimationInTime
  "decimation in frequency" -> DecimationInFrequency
  "twiddle factor" -> TwiddleFactor
  "bit reversal" -> BitReversal
 }

 INTERPRETATION_ORDER = [
  detect_FFT_context,
  identify transform_length_sample_rate_forward_inverse_real_complex_and_memory constraints,
  classify powerOfTwo_composite_prime_or_arbitrary length,
  select radix2_mixedRadix_splitRadix_CooleyTukey_Bluestein_or_Rader algorithm,
  compute butterflies_twiddle factors_and_permutations,
  map output_to_frequency bins,
  assess complexity_roundoff_scaling_and_zero padding,
  verify inverse reconstruction_or_convolution result,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("fast Fourier transform")
  OR asks_for_efficient_DFT computation
  THEN activate(FastFourierTransformOntology)

 E2:
  IF N_is_power_of_two
  THEN consider Radix2FFT_or_SplitRadixFFT

 E3:
  IF N_has_multiple_factors
  THEN consider MixedRadixFFT_or_CooleyTukeyAlgorithm

 E4:
  IF N_is_prime
  THEN consider BluesteinAlgorithm_or_RaderAlgorithm

 E5:
  IF output_order_is_bit_reversed
  THEN reorder_before_interpretation

 E6:
  IF linear_convolution_requested
  THEN zero_pad_to_at_least len(x)+len(h)-1

 E7:
  IF zero_padding_used_for_spectrum display
  THEN state_that_intrinsic_resolution_is_unchanged

 E8:
  IF sample_rate_known
  THEN map bins_to_physical frequency

 E9:
  IF inverse_transform_required
  THEN apply matching scaling convention
}

RECURSION {
 ENTRY = FastFourierTransform

 EXPAND(FastFourierTransform) -> [
  FFT,
  DiscreteFourierTransform,
  DFT,
  InverseFastFourierTransform,
  IFFT,
  CooleyTukeyAlgorithm,
  Radix2FFT,
  Radix4FFT,
  MixedRadixFFT,
  SplitRadixFFT,
  PrimeFactorFFT,
  BluesteinAlgorithm,
  RaderAlgorithm,
  DecimationInTime,
  DecimationInFrequency,
  ButterflyOperation,
  TwiddleFactor,
  BitReversal,
  DigitReversal,
  RecursiveFFT,
  IterativeFFT,
  InPlaceFFT,
  OutOfPlaceFFT,
  FFTStage,
  FFTLength,
  PowerOfTwoLength,
  CompositeLength,
  PrimeLength,
  ComputationalComplexity,
  ArithmeticOperationCount,
  MemoryComplexity,
  ZeroPadding,
  FrequencyBin,
  SpectralResolution,
  CircularConvolution,
  LinearConvolution,
  OverlapAdd,
  OverlapSave,
  MultidimensionalFFT,
  TwoDimensionalFFT,
  RealFFT,
  ComplexFFT,
  NumericalRoundoff,
  ScalingConvention,
  NormalisationConvention
 ]

 EXPAND(AlgorithmFamilies) -> [
  CooleyTukeyAlgorithm,
  Radix2FFT,
  Radix4FFT,
  MixedRadixFFT,
  SplitRadixFFT,
  PrimeFactorFFT,
  BluesteinAlgorithm,
  RaderAlgorithm
 ]

 EXPAND(CoreOperations) -> [
  ButterflyOperation,
  TwiddleFactor,
  BitReversal,
  DigitReversal,
  RecursiveDecomposition,
  IterativeStages
 ]

 EXPAND(FFTApplications) -> [
  SpectralAnalysis,
  CircularConvolution,
  LinearConvolution,
  OverlapAdd,
  OverlapSave,
  MultidimensionalFFT
 ]

 STOP_CONDITION =
  "Stop when the transform length, FFT algorithm, factorisation, twiddle factors, ordering, scaling, complexity, frequency mapping and validation status are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Signal Processing Mathematics"

 IMMEDIATE_CONTEXTS = [
  "Fourier Analysis Ontology",
  "Fourier Transform Ontology",
  "Signal Processing Ontology",
  "Numerical Analysis Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Signal Processing Ontology",
  "Signal Processing Mathematics",
  "Fourier Analysis Ontology",
  "Fourier Transform Ontology",
  "Discrete Fourier Transform Ontologies",
  "Linear Algebra Ontologies",
  "Complex Analysis Ontologies",
  "Numerical Analysis Ontologies",
  "Algorithm Complexity Ontologies",
  "Convolution Ontologies",
  "Image Processing Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Fast Fourier Transform -> Fourier Analysis Ontology for frequency-decomposition semantics",
  "Fast Fourier Transform -> Fourier Transform Ontology for continuous-transform relationships",
  "Fast Fourier Transform -> Signal Processing Ontology for signal interpretation",
  "Fast Fourier Transform -> Discrete Fourier Transform Ontologies for exact transform definition",
  "Fast Fourier Transform -> Linear Algebra for transform-matrix factorisation",
  "Fast Fourier Transform -> Complex Analysis for roots of unity",
  "Fast Fourier Transform -> Numerical Analysis for rounding, scaling and stability",
  "Fast Fourier Transform -> Algorithm Complexity for operation-count semantics",
  "Fast Fourier Transform -> Convolution Ontologies for FFT-based convolution",
  "Fast Fourier Transform -> Image Processing for multidimensional FFT applications"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible FFT algorithms, factorisations or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve FFT-versus-DFT distinction.",
  "Preserve exact-transform equivalence.",
  "Preserve radix and factorisation semantics.",
  "Preserve butterfly and twiddle-factor semantics.",
  "Preserve data-ordering semantics.",
  "Preserve zero-padding interpretation.",
  "Preserve forward-versus-inverse scaling distinction.",
  "Preserve machine-readable FFT semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "The Fast Fourier Transform is a family of efficient algorithms for computing the Discrete Fourier Transform and its inverse."

 COMPLEXITY_SUMMARY =
  "Typical FFT algorithms reduce transform complexity from O(N^2) direct evaluation to approximately O(N log N)."

 RADIX_SUMMARY =
  "Radix algorithms decompose an N-point transform into smaller transforms according to the factors of N."

 BUTTERFLY_SUMMARY =
  "Butterflies combine subtransform values using additions, subtractions and twiddle factors."

 TWIDDLE_SUMMARY =
  "Twiddle factors are complex roots of unity used to combine recursive or staged transforms."

 ORDERING_SUMMARY =
  "Some FFT structures use bit-reversed or digit-reversed data ordering."

 ZERO_PADDING_SUMMARY =
  "Zero padding produces a denser frequency grid but does not increase the signal's intrinsic information content."

 CONVOLUTION_SUMMARY =
  "FFT multiplication followed by IFFT can compute long convolutions efficiently."

 STATUS_SUMMARY =
  "FFT results should be validated for scaling, ordering, sample-rate mapping, roundoff and inverse reconstruction."
}

FLOW {
 INPUT
 -> detect_fast_Fourier_transform_context
 -> identify sequence_length_sample_rate_real_or_complex data_forward_or_inverse transform_memory_and_speed requirements
 -> classify powerOfTwo_composite_prime_or_arbitrary length
 -> select radix2_radix4_mixedRadix_splitRadix_CooleyTukey_primeFactor_Bluestein_or_Rader algorithm
 -> decompose DFT_into smaller subtransforms
 -> apply butterfly_operations_twiddle factors_and_required permutations
 -> produce DFT_or_IFFT output
 -> map bins_to_frequency if sample_rate known
 -> evaluate computational_complexity_memory_roundoff_scaling_and_zero padding effects
 -> if_convolution_requested use FFT_multiply_IFFT with adequate padding
 -> route to Fourier_analysis Fourier_transform signal_processing DFT linear_algebra complex_analysis numerical_analysis algorithm_complexity convolution image_processing_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Fast Fourier Transform Ontology defines efficient computation of discrete Fourier transforms. It supports Cooley-Tukey factorisation, radix-2, radix-4, mixed-radix, split-radix, prime-factor, Bluestein and Rader methods, decimation in time and frequency, butterfly operations, twiddle factors, bit and digit reversal, recursive and iterative implementations, in-place and out-of-place computation, transform length classes, complexity, zero padding, frequency-bin mapping, FFT-based linear and circular convolution, overlap-add and overlap-save processing, real and complex FFTs, multidimensional FFTs, numerical roundoff and scaling conventions."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-APPLIED-MATHEMATICS-FAST-FOURIER-TRANSFORM-ONTOLOGY-V1"
}

}

END_FLOW