We propose a novel, lossless compression algorithm, based on the 2D Discrete Fast Fourier Transform, to approximate the Algorithmic (Kolmogorov) Complexity of Elementary Cellular Automata. Fast Fourier transforms are ...We propose a novel, lossless compression algorithm, based on the 2D Discrete Fast Fourier Transform, to approximate the Algorithmic (Kolmogorov) Complexity of Elementary Cellular Automata. Fast Fourier transforms are widely used in image compression but their lossy nature exclude them as viable candidates for Kolmogorov Complexity approximations. For the first time, we present a way to adapt fourier transforms for lossless image compression. The proposed method has a very strong Pearsons correlation to existing complexity metrics and we further establish its consistency as a complexity metric by confirming its measurements never exceed the complexity of nothingness and randomness (representing the lower and upper limits of complexity). Surprisingly, many of the other methods tested fail this simple sanity check. A final symmetry-based test also demonstrates our method’s superiority over existing lossless compression metrics. All complexity metrics tested, as well as the code used to generate and augment the original dataset, can be found in our github repository: ECA complexity metrics<sup>1</sup>.展开更多
Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm sa...Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,展开更多
DFT is widely applied in the field of signal process and others. Most present rapid ways of calculation are either based on paralleled computers connected by such particular systems like butterfly network, hypercube e...DFT is widely applied in the field of signal process and others. Most present rapid ways of calculation are either based on paralleled computers connected by such particular systems like butterfly network, hypercube etc; or based on the assumption of instant transportation, non-conflict communication, complete connection of paralleled processors and unlimited usable processors. However, the delay of communication in the system of information transmission cannot be ignored. This paper works on the following aspects： instant transmission, dispatching missions, and the path of information through the communication link in the computer cluster systems; layout of the dynamic FFT algorithm under the different structures of computer clusters.展开更多
针对风洞试验模型系统辨识不准确的问题,利用自适应LMS(least mean square)滤波器模型对跨声速风洞模型进行系统辨识。由于实测信号中存在多模态耦合,为了提高系统辨识精准度,首先对输入输出信号作了FRF(frequency response analysis)...针对风洞试验模型系统辨识不准确的问题,利用自适应LMS(least mean square)滤波器模型对跨声速风洞模型进行系统辨识。由于实测信号中存在多模态耦合,为了提高系统辨识精准度,首先对输入输出信号作了FRF(frequency response analysis)分析得到试验模型俯仰方向前两阶模态,其次利用快速Fourier变换进行模态解耦,接着利用自适应LMS滤波器模型、传递函数模型、多项式模型对俯仰方向单模态进行系统辨识,最后得到了基于自适应LMS滤波器模型的俯仰方向一阶、二阶模态滤波器系数。通过对比不同数学模型的输出与输入之间的相关系数和均方误差及辨识结果,表明自适应LMS滤波器模型具有更高的系统辨识精准度和更简洁的数学模型结构。为后续风洞试验模型振动主动控制计算法的设计提供有力支撑。展开更多
Accurate frequency estimation in a wideband digital receiver using the FFT algorithm encounters challenges, such as spectral leakage resulting from the FFT’s assumption of signal periodicity. High-resolution FFTs pos...Accurate frequency estimation in a wideband digital receiver using the FFT algorithm encounters challenges, such as spectral leakage resulting from the FFT’s assumption of signal periodicity. High-resolution FFTs pose computational demands, and estimating non-integer multiples of frequency resolution proves exceptionally challenging. This paper introduces two novel methods for enhanced frequency precision: polynomial interpolation and array indexing, comparing their results with super-resolution and scalloping loss. Simulation results demonstrate the effectiveness of the proposed methods in contemporary radar systems, with array indexing providing the best frequency estimation despite utilizing maximum hardware resources. The paper demonstrates a trade-off between accurate frequency estimation and hardware resources when comparing polynomial interpolation and array indexing.展开更多
文摘We propose a novel, lossless compression algorithm, based on the 2D Discrete Fast Fourier Transform, to approximate the Algorithmic (Kolmogorov) Complexity of Elementary Cellular Automata. Fast Fourier transforms are widely used in image compression but their lossy nature exclude them as viable candidates for Kolmogorov Complexity approximations. For the first time, we present a way to adapt fourier transforms for lossless image compression. The proposed method has a very strong Pearsons correlation to existing complexity metrics and we further establish its consistency as a complexity metric by confirming its measurements never exceed the complexity of nothingness and randomness (representing the lower and upper limits of complexity). Surprisingly, many of the other methods tested fail this simple sanity check. A final symmetry-based test also demonstrates our method’s superiority over existing lossless compression metrics. All complexity metrics tested, as well as the code used to generate and augment the original dataset, can be found in our github repository: ECA complexity metrics<sup>1</sup>.
基金Supported by the National Natural Science Foundation of China
文摘Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,
文摘DFT is widely applied in the field of signal process and others. Most present rapid ways of calculation are either based on paralleled computers connected by such particular systems like butterfly network, hypercube etc; or based on the assumption of instant transportation, non-conflict communication, complete connection of paralleled processors and unlimited usable processors. However, the delay of communication in the system of information transmission cannot be ignored. This paper works on the following aspects： instant transmission, dispatching missions, and the path of information through the communication link in the computer cluster systems; layout of the dynamic FFT algorithm under the different structures of computer clusters.
文摘针对风洞试验模型系统辨识不准确的问题,利用自适应LMS(least mean square)滤波器模型对跨声速风洞模型进行系统辨识。由于实测信号中存在多模态耦合,为了提高系统辨识精准度,首先对输入输出信号作了FRF(frequency response analysis)分析得到试验模型俯仰方向前两阶模态,其次利用快速Fourier变换进行模态解耦,接着利用自适应LMS滤波器模型、传递函数模型、多项式模型对俯仰方向单模态进行系统辨识,最后得到了基于自适应LMS滤波器模型的俯仰方向一阶、二阶模态滤波器系数。通过对比不同数学模型的输出与输入之间的相关系数和均方误差及辨识结果,表明自适应LMS滤波器模型具有更高的系统辨识精准度和更简洁的数学模型结构。为后续风洞试验模型振动主动控制计算法的设计提供有力支撑。
文摘Accurate frequency estimation in a wideband digital receiver using the FFT algorithm encounters challenges, such as spectral leakage resulting from the FFT’s assumption of signal periodicity. High-resolution FFTs pose computational demands, and estimating non-integer multiples of frequency resolution proves exceptionally challenging. This paper introduces two novel methods for enhanced frequency precision: polynomial interpolation and array indexing, comparing their results with super-resolution and scalloping loss. Simulation results demonstrate the effectiveness of the proposed methods in contemporary radar systems, with array indexing providing the best frequency estimation despite utilizing maximum hardware resources. The paper demonstrates a trade-off between accurate frequency estimation and hardware resources when comparing polynomial interpolation and array indexing.
