核心算法 (Core Algorithms)

概述

Vitis-Tutorials 的核心算法库是专为 Xilinx 自适应计算平台优化的高性能计算内核集合。这些算法覆盖了从数字信号处理、密码学到物理模拟等多个关键领域，充分利用了 FPGA 的可重构性和 AI Engine 的并行处理能力。无论是处理非标准长度的快速傅里叶变换，还是实现后量子密码学中的多项式乘法，这些内核都经过精心优化，以在吞吐量和延迟之间取得最佳平衡。

每个算法都代表了其在特定计算领域的最先进实现。从利用数论变换（NTT）加速 CRYSTALS-Kyber 等后量子密码方案，到通过多重信号分类（MUSIC）算法实现超分辨率的波达方向（DOA）估计，这些实现不仅展示了数学理论的实际应用，还针对 Xilinx 器件架构进行了深度优化。通过流水线设计、数据并行化和内存访问优化，这些算法能够处理从实时信号流到大规模粒子模拟的各种工作负载。

本系列深入探讨了每个算法的数学基础、硬件实现细节和性能优化策略。您将了解到如何通过质因数算法（PFA）处理非 2 的幂次 FFT，如何利用法罗（Farrow）结构实现任意分数延迟，以及如何通过比托尼克（Bitonic）排序网络在 SIMD 架构上实现确定性并行排序。每个章节都提供了详细的代码示例和性能基准，帮助您将这些核心算法集成到自己的 Vitis 应用中。

算法架构与数据流

下图展示了各核心算法之间的潜在数据流关系和处理链组合方式：

算法详解

质因数算法快速傅里叶变换 (Prime Factor Algorithm FFT)

该算法通过数学分解技术，将大型非 2 的幂次点 FFT（如 1008 点）拆解为多个互质的较小离散傅里叶变换（DFT）。通过复杂的内存索引置换和旋转因子优化，它克服了传统 Cooley-Tukey 算法对 2 的幂次长度的限制，在保持计算效率的同时支持任意合数长度的频谱分析。

→ 阅读详细指南

多重信号分类波达方向估计 (MUSIC DOA Estimation)

作为一种高分辨率空间谱估计算法，MUSIC 利用奇异值分解（SVD）将接收信号划分为信号子空间和噪声子空间。通过搜索噪声子空间的正交性，该算法能够超分辨率地估计多个相干或非相干信号的波达方向（DOA），显著优于传统的波束形成方法。

→ 阅读详细指南

法罗分数延迟滤波器 (Farrow Fractional Delay Filter)

该滤波器基于连续时间多项式插值结构，通过运行时调整插值系数实现任意分数样本延迟。与传统的多相滤波器组不同，Farrow 结构允许延迟参数在运行时动态变化，特别适用于异步采样率转换和数字定时恢复等需要连续可变延迟的应用场景。

→ 阅读详细指南

数论变换 (Number Theoretic Transform, NTT)

作为定义在有限域上的特殊离散傅里叶变换，NTT 通过模运算替代复数运算，避免了浮点精度误差。该算法是后量子密码学（如 CRYSTALS-Kyber 和 CRYSTALS-Dilithium）的核心组件，能够高效加速大整数多项式乘法，为同态加密和零知识证明提供硬件加速基础。

→ 阅读详细指南

N 体问题模拟 (N-Body Simulation)

该算法通过直接计算所有粒子对之间的引力或电磁力，解决计算复杂度为 O(N²) 的 N 体问题。通过优化内存访问模式和利用空间分解技术（如 Barnes-Hut 或快速多极子方法），该实现能够在三维空间中高效模拟大规模粒子系统的动力学行为，适用于天体物理学和分子动力学模拟。

→ 阅读详细指南

比托尼克排序网络 (Bitonic Sorting Network)

作为一种高度并行的确定性排序算法，比托尼克排序通过反复合并比托尼克序列实现全局排序。其规则的比较交换结构和数据无关的控制流使其特别适合 SIMD 向量架构和 AI Engine 的确定性数据路由，能够以 O(log²n) 的时间复杂度在并行硬件上完成排序任务。

→ 阅读详细指南