Published January 1, 2022
| Version v1
Publication
Open
Is FFT Fast Enough for Beyond 5G Communications? A Throughput-Complexity Analysis for OFDM Signals
- 1. Universidade Tecnológica Federal do Paraná
- 2. University of Coimbra
- 3. Universidade do Porto
- 4. Institute for Systems and Computer Engineering of Porto
Description
In this paper, we study the impact of computational complexity on the throughput limits of the fast Fourier transform (FFT) algorithm for orthogonal frequency division multiplexing (OFDM) waveforms. Based on the spectro-computational complexity (SC) analysis, we verify that the complexity of an N -point FFT grows faster than the number of bits in the OFDM symbol. Thus, we show that FFT nullifies the OFDM throughput on N unless the N -point discrete Fourier transform (DFT) problem verifies as Ω( N ), which remains a "fascinating" open question in theoretical computer science. Also, because FFT demands N to be a power of two 2 i ( i > 0), the spectrum widening leads to an exponential complexity on i , i.e. O (2 i i ). To overcome these limitations, we consider the alternative frequency-time transform formulation of vector OFDM (V-OFDM), in which an N -point FFT is replaced by N/L ( L >0) smaller L -point FFTs to mitigate the cyclic prefix overhead of OFDM. Building on that, we replace FFT by the straightforward DFT algorithm to release the V-OFDM parameters from growing as powers of two and to benefit from flexible numerology (e.g., L = 3, N = 156). Besides, by setting L to Θ(1), the resulting solution can run linearly on N (rather than exponentially on i ) while sustaining a non null throughput as N grows.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
في هذه الورقة، ندرس تأثير التعقيد الحسابي على حدود إنتاجية خوارزمية تحويل فورييه السريع (FFT) لأشكال موجات تعدد الإرسال بتقسيم التردد المتعامد (OFDM). استنادًا إلى تحليل التعقيد الحسابي الطيفي (SC)، نتحقق من أن تعقيد N - point FFT ينمو بشكل أسرع من عدد البتات في رمز OFDM. وبالتالي، نظهر أن FFT يلغي إنتاجية OFDM على N ما لم يتم التحقق من مشكلة تحويل فورييه المنفصل (DFT) على أنها Ω(N)، والتي تظل سؤالًا مفتوحًا "رائعًا" في علوم الكمبيوتر النظرية. أيضًا، نظرًا لأن FFT تتطلب N لتكون قوة 2 i ( i > 0)، فإن توسيع الطيف يؤدي إلى تعقيد أسي على i، أي O (2 i ). للتغلب على هذه القيود، ننظر في صيغة تحويل التردد الزمني البديلة لمتجه OFDM (V - OFDM)، حيث يتم استبدال N - point FFT بـ N/L (L >0) أصغر L - point FFTs للتخفيف من البادئة الدورية العلوية لـ OFDM. بناءً على ذلك، نستبدل FFT بخوارزمية DFT المباشرة لتحرير معلمات V - OFDM من النمو كقوى من اثنين والاستفادة من الأعداد المرنة (على سبيل المثال، L = 3، N = 156). إلى جانب ذلك، من خلال ضبط L على (1)، يمكن تشغيل الحل الناتج خطيًا على N (بدلاً من التشغيل أسيًا على i) مع الحفاظ على إنتاجية غير فارغة مع نمو N.Translated Description (French)
Dans cet article, nous étudions l'impact de la complexité de calcul sur les limites de débit de l'algorithme de transformée de Fourier rapide (FFT) pour les formes d'onde de multiplexage par répartition orthogonale de la fréquence (OFDM). Sur la base de l'analyse de la complexité spectro-computationnelle (SC), nous vérifions que la complexité d'une FFT en N points croît plus rapidement que le nombre de bits dans le symbole OFDM. Ainsi, nous montrons que la FFT annule le débit OFDM sur N à moins que le problème de transformée de Fourier discrète (DFT) à N points ne soit vérifié comme Ω(N), ce qui reste une question ouverte « fascinante » en informatique théorique. De plus, parce que la FFT exige que N soit une puissance de deux 2 i (i > 0), l'élargissement du spectre conduit à une complexité exponentielle sur i, c'est-à-dire O (2 i i). Pour surmonter ces limitations, nous considérons la formulation alternative de transformée fréquence-temps du vecteur OFDM (V-OFDM), dans laquelle une FFT de point N est remplacée par des FFT de point L plus petites N/L (L >0) pour atténuer le surdébit de préfixe cyclique de l'OFDM. Sur cette base, nous remplaçons FFT par l'algorithme DFT simple pour libérer les paramètres V-OFDM de la croissance en tant que puissances de deux et pour bénéficier d'une numérologie flexible (par exemple, L = 3, N = 156). En outre, en réglant L sur Θ(1), la solution résultante peut fonctionner linéairement sur N (plutôt qu'exponentiellement sur i) tout en maintenant un débit non nul à mesure que N croît.Translated Description (Spanish)
En este artículo, estudiamos el impacto de la complejidad computacional en los límites de rendimiento del algoritmo de transformada rápida de Fourier (FFT) para formas de onda de multiplexación por división de frecuencia ortogonal (OFDM). Con base en el análisis de complejidad espectro-computacional (SC), verificamos que la complejidad de una FFT de N puntos crece más rápido que el número de bits en el símbolo OFDM. Por lo tanto, mostramos que la FFT anula el rendimiento de OFDM en N a menos que el problema de la transformada discreta de Fourier (DFT) de N puntos se verifique como Ω(N), lo que sigue siendo una pregunta abierta "fascinante" en informática teórica. Además, debido a que la FFT exige que N sea una potencia de dos 2 i (i > 0), la ampliación del espectro conduce a una complejidad exponencial en i, es decir, O (2 i i). Para superar estas limitaciones, consideramos la formulación de transformación de frecuencia-tiempo alternativa del vector OFDM (V-OFDM), en la que una FFT de N puntos se reemplaza por FFT de N/L ( L >0) puntos L más pequeñas para mitigar la sobrecarga del prefijo cíclico de OFDM. Sobre esa base, reemplazamos la FFT por el sencillo algoritmo DFT para evitar que los parámetros V-OFDM crezcan como potencias de dos y para beneficiarnos de la numerología flexible (por ejemplo, L = 3, N = 156). Además, al establecer L en Θ(1), la solución resultante puede ejecutarse linealmente en N (en lugar de exponencialmente en i) mientras se mantiene un rendimiento no nulo a medida que N crece.Files
09905568.pdf.pdf
Files
(245 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:41f36e2e75ed79fe15744cb8b11f98c3
|
245 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- هل FFT سريع بما يكفي لتجاوز اتصالات 5G ؟ تحليل الإنتاجية والتعقيد لإشارات OFDM
- Translated title (French)
- La FFT est-elle assez rapide pour les communications au-delà de la 5G ? Une analyse de la complexité du débit pour les signaux OFDM
- Translated title (Spanish)
- ¿Es FFT lo suficientemente rápido para más allá de las comunicaciones 5G? Un análisis de complejidad de rendimiento para señales OFDM
Identifiers
- Other
- https://openalex.org/W4298178047
- DOI
- 10.1109/access.2022.3210519
References
- https://openalex.org/W1488906674
- https://openalex.org/W1986415521
- https://openalex.org/W2041101642
- https://openalex.org/W2061171222
- https://openalex.org/W2066383143
- https://openalex.org/W2067002313
- https://openalex.org/W2072892827
- https://openalex.org/W2095595785
- https://openalex.org/W2102182691
- https://openalex.org/W2132379039
- https://openalex.org/W2163218032
- https://openalex.org/W2325850497
- https://openalex.org/W2554187790
- https://openalex.org/W2570144182
- https://openalex.org/W2576286862
- https://openalex.org/W2757654596
- https://openalex.org/W2927199738
- https://openalex.org/W2943838215
- https://openalex.org/W2952782392
- https://openalex.org/W2955897898
- https://openalex.org/W2997275438
- https://openalex.org/W2999285761
- https://openalex.org/W3006725318
- https://openalex.org/W3024176145
- https://openalex.org/W3101644794
- https://openalex.org/W3105497589
- https://openalex.org/W4230200814
- https://openalex.org/W4234289378
- https://openalex.org/W4237031056
- https://openalex.org/W4292230561
- https://openalex.org/W4302616470
- https://openalex.org/W822096598