CN108111458A - A kind of inverse Fourier transform algorithm applied to NB-IoT - Google Patents

Abstract

The present invention provides an inverse Fourier transform algorithm applied to NB-IoT. The algorithm analyzes the characteristics of an implementation method of mapping 12 subcarriers to 128-point IDFT applied to NB-IoT, and decomposes each Useful information in the output, optimize the processing process, use the regularity of its twiddle factor, use the method of iteration and shift addition, improve the utilization rate of hardware resources, reduce the use of multipliers, which can greatly save hardware area and reduce Fu The power consumption of the Fourier inverse transform device is more critical that, compared with the traditionally used N-point IFFT module, the application of the present invention in NB-IoT can achieve lower Fourier inverse transform processing delay.

Description

An Inverse Fourier Transform Algorithm Applied to NB-IoT

technical field

The present invention relates to the field of Fourier transform algorithm in digital signal processing technology, and more specifically, relates to an inverse Fourier transform algorithm applied to NB-IoT.

Background technique

In modern wireless communication systems, Orthogonal Frequency Division Multiplexing (OFDM) is the most commonly used modulation technique. It is also a special multi-carrier transmission scheme, and its basic idea is to adopt frequency division multiplexing (FDM) technology that allows sub-channel spectrum to overlap without mutual influence. The communication system using OFDM technology has the advantages of high spectrum utilization rate, strong anti-impulse noise and anti-multipath fading ability. Among them, the fast Fourier transform (FFT, Fast Fourier Transformation) algorithm is the key technology to realize OFDM. The fast Fourier transform algorithm was proposed by J.W.Cooley and T.W.Tukey in 1965, the purpose is to reduce the calculation of Fourier transform the complexity.

With the rapid development of integrated circuit technology and digital signal processing technology, the realization of fast Fourier transform has long been possible. In the past 20 years, most companies or organizations have developed various communication systems based on OFDM technology, including the 802.11 series in wireless local area networks and the fourth-generation mobile communication system (4G) and even the fifth-generation mobile communication system under development. The next generation mobile communication system (5G). The FFT device in OFDM modulation and demodulation will directly affect the performance of the system. At present, there are many implementation methods for FFT calculation devices for OFDM systems. The basic idea is to increase the device area in exchange for high performance or reduce performance in exchange for smaller device area or a compromise between the two. In terms of implementation, the basic The methods are fast Fourier transform algorithms composed of traditional radix 2 radix 4 radix 8 and other butterfly structures. The more cascading times, the more multipliers will be consumed, which will sometimes cause waste of hardware resources and increase system performance. power consumption. With the development of low-power Internet of Things, especially the NB-IoT standard released by 3GPP in 2016, FFT modules applying NB-IoT and other low-power Internet of Things standards need to consider the requirements of low power consumption and low delay. In order to meet the timing requirements of the 4G network, the NB-IoT standard must use 128 points or more IFFT to realize the transformation from the frequency domain to the time domain, while NB-IoT only uses 12 of the 128 subcarriers, which is realized by traditional FFT Applying the 128-point IFFT method to NB-IoT will cause waste of resources and is not suitable. Therefore, it is necessary to solve the problem of how to improve resource utilization and reduce low power consumption in performing IDFT by mapping a small number of subcarriers to a majority of subcarriers.

Contents of the invention

The present invention provides an inverse Fourier transform algorithm applied to NB-IoT that can improve resource utilization and reduce low power consumption.

In order to achieve the above-mentioned technical effect, the technical scheme of the present invention is as follows:

An inverse Fourier transform algorithm applied to NB-IoT, comprising the following steps:

S1: The data to be processed is input to the input control module for data conjugate operation and serial-to-parallel conversion;

S2: The converted data is input to the shift addition and subtraction operation module for multiplication and addition of the data and the twiddle factor;

S3: The data processed in step S2 are output to 12 output control modules each time for addition and taking the conjugate sum and dividing by N, and then output the data calculated by inverse Fourier transform.

Further, the specific process of the step S2 is:

1) Divide every 12 data into 7 groups, in which the mapped positions of the two data in the paired 5 groups are symmetrical, and the two rotation factors multiplied with it are conjugated to each other, using the conjugate characteristics, share a set of twiddle factors, multiplex multipliers, and the twiddle factors at the zero position Must be 1, where n and k must be 0, this group of data does not need to be multiplied, it is directly output to the output control module, and the last group of data is left for separate multiplication;

2) Each set of data is input into a module that multiplies the twiddle factor. From step 1), it can be seen that a total of 6 sets of data need such a multiplication module. Since the multiplicand for each twiddle factor multiplication is fixed, use The shift and add method is used to split each known twiddle factor into multiple shift addition and subtraction methods, and then use conjugation. A set of data is multiplexed in the same module in two clock cycles, improving the utilization of modules. Rate;

3) The 6 sets of data obtained after multiplying the twiddle factor and the data at the zero point are output to step 3), and the 7 sets of data will be temporarily stored in the register, waiting for the next clock to be fed back to the module itself for the next time After N-1 iterations of operation, the result of N-1 inverse Fourier transform can be obtained. Among them, the 12 data input for the first time do not perform any complex multiplication operation, and are directly output to the output control module, but save the 12 pieces of data are fed back to the next operation.

Compared with the prior art, the beneficial effects of the technical solution of the present invention are:

The present invention analyzes the characteristics of an implementation method for mapping 12 subcarriers to 128-point IDFT applied to NB-IoT, decomposes useful information in each output, optimizes the processing process, and utilizes the regularity of its rotation factor to use The method of iteration and shift addition improves the utilization of hardware resources and reduces the use of multipliers, which can greatly save hardware area and reduce the power consumption of Fourier inverse transform devices. The key point is that compared with the traditional N Point IFFT module, the application of the present invention in NB-IoT can achieve lower Fourier inverse transform processing delay.

Description of drawings

Fig. 1 is the system block diagram of applying algorithm of the present invention;

Fig. 2 is a schematic diagram of shift operation feedback;

Figure 3 is the twiddle factor Real part shift addition and subtraction flow chart.

Detailed ways

The accompanying drawings are for illustrative purposes only and cannot be construed as limiting the patent;

In order to better illustrate this embodiment, some parts in the drawings will be omitted, enlarged or reduced, and do not represent the size of the actual product;

For those skilled in the art, it is understandable that some well-known structures and descriptions thereof may be omitted in the drawings.

The technical solutions of the present invention will be further described below in conjunction with the accompanying drawings and embodiments.

Example 1

An inverse Fourier transform algorithm applied to NB-IoT, comprising the following steps:

S1: The data to be processed is input to the input control module for data conjugate operation and serial-to-parallel conversion;

S2: The converted data is input to the shift addition and subtraction operation module for multiplication and addition of the data and the twiddle factor;

S3: The data processed in step S2 are output to 12 output control modules each time for addition and taking the conjugate sum and dividing by N, and then output the data calculated by inverse Fourier transform.

Further, the specific process of the step S2 is:

1) Divide every 12 data into 7 groups, in which the mapped positions of the two data in the paired 5 groups are symmetrical, and the two rotation factors multiplied with it are conjugated to each other, using the conjugate characteristics, share a set of twiddle factors, multiplex multipliers, and the twiddle factors at the zero position Must be 1, where n and k must be 0, this group of data does not need to be multiplied, it is directly output to the output control module, and the last group of data is left for separate multiplication;

2) Each set of data is input into a module that multiplies the twiddle factor. From step 1), it can be seen that a total of 6 sets of data need such a multiplication module. Since the multiplicand for each twiddle factor multiplication is fixed, use The shift and add method is used to split each known twiddle factor into multiple shift addition and subtraction methods, and then use conjugation. A set of data is multiplexed in the same module in two clock cycles, improving the utilization of modules. Rate;

3) The 6 sets of data obtained after multiplying the twiddle factor and the data at the zero point are output to step 3), and the 7 sets of data will be temporarily stored in the register, waiting for the next clock to be fed back to the module itself for the next time After N-1 iterations of operation, the result of N-1 inverse Fourier transform can be obtained. Among them, the 12 data input for the first time do not perform any complex multiplication operation, and are directly output to the output control module, but save the 12 pieces of data are fed back to the next operation.

An IDFT implementation method applied to NB-IoT of the present invention is further described in detail. It is worth reminding that the specific examples described below are examples for explaining the content of the present invention, but not limiting the present invention.

Taking the 128-point IFFT design as an example, the IDFT formula is as follows:

where 0≤k≤N-1, 0≤n≤N-1

Through the above formula, the result is only obtained by direct operation of IDFT, which requires a very large amount of calculation, and the IFFT algorithm continuously decomposes the long sequence DFT into multiple short sequence DFTs, and uses Fourier The periodicity, reducibility, and conjugate symmetry of the transformation are used to reduce the computational load of the DFT, as shown in the following table:

Note: N represents the number of FFT points

The above table shows the amount of calculation required to implement DFT/IDFT with different bases. Taking 64-point FFT as an example, the number of complex multiplication operations of direct DFT can reach 4032 times, while the Fu of base 2, base 4, and base 8 The number of complex multiplications required for the Lie transform is 256, 144, and 112 times, respectively. In addition to the Fourier transform of the pure basis structure, there are also mixed bases composed of base 2, base 4, and base 8, which are applied to Fourier transforms of various non-4 and 8 integer powers. The purpose of these applications is to solve the situation of excessive resource consumption and complex calculation in the DFT process, but the negative effect is that the control module is more complex and the delay is too large.

The present invention is especially aimed at the IFFT transformation in the NB-IoT protocol, and improves it according to the above formula to make it suitable for NB-IoT. According to 3GPP, the frame structure of NB-IoT must conform to the frame structure required by LTE in the time domain. Considering the cyclic prefix, the IDFT points of NB-IoT must be at least 128 points, and the number of effective subcarriers in NB-IoT There are only 12 points, so the number of points mapped to IDFT is only 12 points, and the rest are empty. If you simply sample the traditional optimized 128-point IFFT design, it will inevitably cause waste of hardware resources and greater delay. The present invention simplifies and improves according to above-mentioned formula, as follows:

N=128, n∈{0,1,...,N-1}, and k is determined according to the position where NB-IoT effective subcarriers are mapped, so k={0,1,2,3,4 ,5,122,123,124,125,126,127}.

After simplification, as shown in the above formula, each number output by the 128-point IDFT has 12 input data multiplied by the twiddle factor, and the value of mod(nk,N) determines the twiddle factor as shown in the following matrix,

Output n is 0 for the first number, so all twiddle factors are 1 for the first time.

For n=1, the rotation factor is The value of k is still the same as above,

For n=2, the rotation factor is The value of k is still the same as above,

For n=3, the rotation factor is The value of k is still the same as above,

As can be seen The value output for each sequence is the last output times, you can use the results obtained each time to feed back (as shown in Figure 2) back to the original module and multiplied. After such circular feedback, the output result can be obtained by performing complex addition operation.

According to the conjugate symmetry of the twiddle factors, as Therefore, for k={0, 1, 2, 3, 4, 5, 122, 123, 124, 125, 126, 127}, a total of 5 sets of conjugate twiddle factors can be obtained. Multiplying the data corresponding to each group with the twiddle factor can be simplified as follows:

For example, in a set of data, suppose one of the data A is a+b*j and the other data B is c+d*j.

Its twiddle factor C is e+f*j so its conjugate is e-f*j

Therefore, the conventional multiplication is

A*C=(a+b*j)(e+f*j)=(ae-bf)+(af+be)*j

B*conj(C)=(c+d*i)(e-f*j)=(ce+df)+(de-cf)*j

And the result of A*C can be simplified as:

((e-f)a+(a-b)f)+((a-b)f+(e+f)b)*j

It can be obtained from the above that the complex multiplication process is simplified, and only three multipliers are required for each complex multiplication. Since the multiplied twiddle factors required for each set of data are conjugate to each other, two clock cycles can be used to calculate them separately, thus reducing the required multipliers by half. These 5 sets of data can reduce 15 multipliers.

According to the above formula, the value of each output will be related to the value of the last output, that is, fixed Multiplier value, so if iterative multiplication is used, the multiplicand will always be a fixed value. The present invention utilizes the characteristics of its fixed multiplicand to The multiplication of simplifies to a shift-add.

As shown in Figure 3, When N=128, k=1, In terms of hardware implementation, taking 14-bit precision as an example (where 1 bit is a sign bit, 1 bit is an integer bit, and the rest are decimal bits), the real number representation of this twiddle factor can be obtained as binary (2'b00_1111_1111_1011), in complex number multiplication In , the number multiplied by this real number only needs to subtract the number obtained by shifting itself to the right by 10 bits (shrinking) to obtain the multiplication result, which greatly reduces hardware resources. Similarly, multiplication with other twiddle factors can save the multiplication operation and obtain the same effect in this way.

After each 6 sets of data are shifted, added and subtracted, and then added to the zero position, the output result can be obtained:

Where X'(k) is the result of the last multiplication with . For an inverse Fourier transform device suitable for NB-IoT implemented by the present invention, it needs to be divided by 128 at the end. Since the overall division by 128 is only to adjust the overall power of the communication system, according to the actual situation, divide by 128 or keep The data remains unchanged, or other operations are performed, but the final result needs to be conjugated.

The above is the specific implementation principle of the present invention. According to its principle, its implementation process is that 12 complex data are serially input into the Fourier inverse transform device of the present invention, and the 12 complex data are first added, subtracted, shifted and Feedback and other methods are used to realize the IFFT transformation from 12 points to 128 points. It does not require a large amount of RAM and multipliers during operation. In terms of delay, the IDFT of the present invention only needs 12 clock cycles at least from input to output, which is far lower than the general 128-point FFT processing delay. To sum up, the implementation case of the present invention provides an implementation method for mapping 12 subcarriers to 128-point IDFT applied to NB-IoT. Under the condition of the inverse Fourier transform of the carrier, the hardware resource consumption is less, the power consumption is lower, and the delay is less.

The same or similar reference numerals correspond to the same or similar components;

The positional relationship described in the drawings is only for illustrative purposes and cannot be construed as a limitation to this patent;

Apparently, the above-mentioned embodiments of the present invention are only examples for clearly illustrating the present invention, rather than limiting the implementation of the present invention. For those of ordinary skill in the art, other changes or changes in different forms can be made on the basis of the above description. It is not necessary and impossible to exhaustively list all the implementation manners here. All modifications, equivalent replacements and improvements made within the spirit and principles of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (2)

1. A Fourier inverse transform algorithm applied to NB-IoT, characterized in that, comprising the following steps: S1: The data to be processed is input to the input control module for data conjugate operation and serial-to-parallel conversion; S2: The converted data is input to the shift addition and subtraction operation module for multiplication and addition of the data and the twiddle factor; S3: The data processed in step S2 are output to 12 output control modules each time for addition and taking the conjugate sum and dividing by N, and then output the data calculated by inverse Fourier transform. 2. The inverse Fourier transform algorithm applied to NB-IoT according to claim 1, wherein the specific process of the step S2 is: 1) Divide every 12 data into 7 groups, in which the mapped positions of the two data in the paired 5 groups are symmetrical, and the two rotation factors multiplied with it are conjugated to each other, using the conjugate characteristics, share a set of twiddle factors, multiplex multipliers, and the twiddle factors at the zero position Must be 1, where n and k must be 0, this group of data does not need to be multiplied, it is directly output to the output control module, and the last group of data is left for separate multiplication; 2) Each set of data is input into a module that multiplies the twiddle factor. From step 1), it can be seen that a total of 6 sets of data need such a multiplication module. Since the multiplicand for each twiddle factor multiplication is fixed, use The shift and add method is used to split each known twiddle factor into multiple shift addition and subtraction methods, and then use conjugation. A set of data is multiplexed in the same module in two clock cycles, improving the utilization of modules. Rate; 3) The 6 sets of data obtained after multiplying the twiddle factor and the data at the zero point are output to step 3), and the 7 sets of data will be temporarily stored in the register, waiting for the next clock to be fed back to the module itself for the next time After N-1 iterations of operation, the result of N-1 inverse Fourier transform can be obtained. Among them, the 12 data input for the first time do not perform any complex multiplication operation, and are directly output to the output control module, but save the 12 pieces of data are fed back to the next operation.