QR decomposition apparatus and method for MIMO system

The present invention claims priority of Korean Patent Application No. 10-2007-0131836, filed on Dec. 15, 2007, which is incorporated herein by reference.

1. Field of the Invention

The present invention relates to a QR decomposition apparatus and method in a Multiple Input Multiple Output (MIMO) system; and, more particularly, to a QR decomposition apparatus and method that can reduce the number of computers by sharing hardware in an MIMO system employing Orthogonal Frequency Division Multiplexing (OFDM) technology to thereby simplify a structure of hardware.

This work was partly supported by the IT R & D program of MIC/IITA [2006-S-002-02, “IMT-Advanced Radio Transmission Technology with Low Mobility”].

2. Description of Related Art

At present, there are increasing demands for wireless communication system capable of transmitting high-quality and large-volume multimedia data by using limited frequency resources. Among the methods for transmitting large-volume data by using limited frequency resources is a Multiple Input Multiple Output (MIMO) system. An MIMO system forms a plurality of independent fading channels by using multiple antennas at transmitting and receiving ends and transmits different signals for each transmission antenna to thereby improve a data transmission rate remarkably. Thus, the MIMO system can transmit a great deal of data without broadening frequency.

However, MIMO systems are weak to inter-symbol interference and frequency selective fading that are caused during high-speed data transmission. To overcome the shortcoming, the MIMO systems employ Orthogonal Frequency Division Multiplexing (OFDM) technology. OFDM is a modulation scheme most appropriate for high-speed data transmission at present. According to OFDM, one data sequence is transmitted over subcarrier which is transmitted at a lower data transmission rate than that of the data sequence.

Typically, a channel environment for wireless communication has multiple paths, which is called multipath, due to obstacles such as buildings. Delay spread occurs in wireless channel having multipath due to the multipath. When delay spread time is longer than symbol transmission interval, inter-symbol interference (ISI) occurs. In this case, frequency selective fading occurs in a frequency domain. When a single carrier is used, an equalizer is used to remove the inter-symbol interference components. However, as data rate increases, the equalizer becomes more complicated.

When an MIMO system is combined with an OFDM system, the advantages of the MIMO system can be taken while the disadvantage of the MIMO system is offset by the OFDM system. Typically, an MIMO system has N transmission antennas and M reception antennas. A structure combining the MIMO system with the OFDM technology is referred to as a MIMO-OFDM system.

FIGS. 1A and 1B are block views showing structures of an MIMO-OFDM system. FIG. 1A is a block view illustrating a transmitting end of the MIMO-OFDM system, and FIG. 1B is a block view illustrating a receiving end of the MIMO-OFDM system.

Referring to FIG. 1A , a serial-to-parallel (S/P) converter 101 divides transmission data into a plurality of parallel data sequences. A plurality of encoders 102 encode a parallel data sequence, respectively. Each encoded data sequence is modulated in a Quadrature Amplitude Modulation (QAM) mapper 103 based on a modulation scheme, such as Binary Phase Shift Keying (BPSK), Quadrature Phase Shift Keying (QPSK), 16QAM, and 64QAM, respectively, to thereby produce modulated symbols. The modulated symbols are converted into signals of a time axis in an Inverse Fast Fourier Transformer (IFFT) 104 . A cyclic prefix (CP) inserter 105 inserts a cyclic prefix code for guard interval to the time-axis symbols. Subsequently, a digital-to-analog conversion (DAC) and radio frequency (RF) unit 106 converts the digital signals with the CP code inserted thereto into analog signals, converts the analog signals into RF signals, and sends out the RF signals through an antenna.

Referring to FIG. 1B , a digital-to-analog conversion (ADC) and RF unit 107 converts the RF signals into analog signals and converts the analog signals into digital signals. A CP remover 108 removes the CP code inserted for guard interval and transmits signals without a CP code to a Fast Fourier Transformer (FFT) 109 . The FFT 109 executes high-speed Fourier conversion onto the inputted parallel signals to thereby generate transmission data symbols. An MIMO receiver 110 estimates the generated transmission data symbols and calculates a log likelihood ratio (LLR) of the estimated symbols. Decoders decode the data sequences transmitted from the MIMO receiver 110 , respectively, and estimates transmission data. A parallel-to-serial (P/S) converter 112 converts the decoded parallel data outputted from the decoders 111 .

Examples of the MIMO receiver 110 include a Decision Feedback Equalizer (DFE), a zero forcing (ZF) device, a Minimum Mean Square Error Estimator (MMSE), and a Bell Labs Layered Space-Time (BLAST) device. As the MIMO receiver includes more transmission and reception antennas, the complexity of the MIMO receiver becomes high and, particularly, the complexity of QR decomposition increases greatly.

When it is assumed that there are M antennas and the number of reception antennas is N, a reception vector z of arbitrary subcarrier after FFT can be expressed as the following Equation 1.

The channel (H) may be expressed as H=QR after QR decomposition. Generally, the number N of reception antennas is equal to or greater than the number M of transmission antennas in an MIMO system, an upper triangular R matrix is expressed as Equation 2.

The channel matrix (H) is N×M; Q=N×N; and the upper triangular R matrix is N×M. Herein, the Q can be expressed as:

Accordingly, the modified reception vector y is expressed as the following Equation 3.

The Equation 3 can be simply expressed as follows.

Gram-Schmidt method is known as a simple method among other methods for QR decomposition. The following Equation 4 describes a typical QR decomposition method. Referring to the Equation 4, a norm, which is a vector size, is calculated first (norm1=∥q i ∥ 2 ), and a Q column value for a reception vector is calculated (q i :=q i /r i,j ) by obtaining r i,j for √{square root over (norm i )}. Subsequently, an R column value is calculated based on the obtained Q column value and the reception vector, and a Q update value and a norm update value are calculated. This process is repeated until n T is decided by the transmission and reception antennas.

To take an example where n T =8 in the Equation 4, more than 2000 multipliers and 8 dividers are required. Also, it takes 256 multipliers for Q H z real part computation. In total, the number of entire multipliers comes to more than 2200, which are too many to be realized as hardware.

An embodiment of the present invention is directed to providing a QR decomposition apparatus and method that can simplify a hardware structure by reducing the number of multipliers through hardware sharing in a Multiple Input Multiple Output (MIMO) system.

Other objects and advantages of the present invention can be understood by the following description, and become apparent with reference to the embodiments of the present invention. Also, it is obvious to those skilled in the art to which the present invention pertains that the objects and advantages of the present invention can be realized by the means as claimed and combinations thereof.

In accordance with an aspect of the present invention, there is provided a QR decomposition apparatus used for a receiver in an MIMO system, including: a norm multiplier for calculating a norm; a Q column multiplier for calculating a column value of a unitary Q matrix to thereby produce a Q matrix vector; a first storage for storing the Q matrix vector calculated in the Q column multiplier; an R row multiplier for calculating a value of an upper triangular R matrix by multiplying the Q matrix vector by a reception signal vector; and a Q update multiplier for receiving the reception signal vector and an output of the R row multiplier, calculating an Q update value through an accumulation operation, and providing the Q update value to the Q column multiplier to calculate a next Q matrix vector.

The QR decomposition apparatus further includes a second storage for receiving an output of the norm multiplier and outputting a √{square root over (norm)} value based on a lookup table; and a third storage for receiving an output of the norm multiplier and outputting a 1/√{square root over (norm)} value based on a lookup table.

In accordance with another aspect of the present invention, there is provided a QR decomposition method in an MIMO system, including: calculating an upper triangular R matrix vector by multiplying a Q matrix vector by a reception signal vector; updating the Q matrix vector through an accumulation operation based on the reception signal vector and the R matrix vector obtained in said calculating an upper triangular R matrix vector; updating a norm based on the Q matrix vector updated in said updating the Q matrix vector; and calculating a Q matrix vector based on a value obtained by the norm updated in said updating a norm and the updated Q matrix vector.

FIGS. 1A and 1B are block views showing a transmitting end and a receiving end of a typical Multiple Input Multiple Output (MIMO) system based on Orthogonal Frequency Division Multiplexing (OFDM).

FIG. 2 illustrates a typical transmission frame.

FIG. 3 shows operation timing diagrams of a Q memory and R memory in accordance with an embodiment of the present invention.

FIG. 4 shows operation timing diagrams for calculating a Q update value in accordance with an embodiment of the present invention.

FIG. 5 is a block view describing a QR decomposition apparatus in accordance with an embodiment of the present invention.

FIGS. 6 and 7 conceptually illustrate operation of a QR decomposition apparatus in accordance with an embodiment of the present invention.

FIG. 8 describes a floating point operation method.

FIG. 9 describes an operation of a ROM table based on the floating point operation method in accordance with an embodiment of the present invention.

The advantages, features and aspects of the invention will become apparent from the following description of the embodiments with reference to the accompanying drawings, which is set forth hereinafter. Also, when it is considered that detailed description on a related art to which the present invention pertains may obscure a point of the present invention, the description will not be provided herein. Hereinafter, specific embodiments of the present invention will be described in detail by referring to the accompanying drawings.

FIG. 2 shows a typical structure of a transmission frame. A typical transmission frame includes an 8-symbol long training field (LTF), a signal field (SIG) including frame information, and a plurality of data symbols. For the sake of easy explanation of the present invention, an example where M=8; N=8; and one OFDM symbol=288 samples will be described herein.

FIG. 3 shows operation timing diagrams of a memory of Q and R matrix during QR decomposition in accordance with an embodiment of the present invention.

dtct_en is an enable signal for detecting a reception signal and it is an enable signal of a reception signal z vector. dtctscnt is a sample count and there are 288 samples for one symbol. dtctsycnt is a symbol count. q1_we is an enable signal for storing a first column vector into a memory in a Q matrix. q2_we is an enable signal for storing a second column vector into the memory in the Q matrix. Q3_we through Q8_we are enable signals for storing third to eighth column vectors into the memory.

FIG. 4 shows an enable signal for calculating r k,i q k in the QR decomposition. At dtctsycnt=8, enable signals of rq1 to rq7 are 1 to calculate a Q update value of Equation 5.

FIG. 5 is a block view describing a QR decomposition apparatus in accordance with an embodiment of the present invention. The operation of the QR decomposition apparatus suggested in the present invention may be represented as the following Equation 6.

Hereinafter, a QR decomposition apparatus of the present invention will be described in detail by referring to the accompanying FIGS. 5 to 7 .

Generally, a QR decomposition apparatus includes a norm multiplier 503 , a Q column multiplier 507 , a Q memory 508 , an R row multiplier 501 , an R memory 509 , and a Q update multiplier 502 . The norm multiplier 503 calculates a norm, which is a vector size. The Q column multiplier 507 calculates values of a Q column. The Q memory 508 stores a Q matrix vector calculated in the Q column multiplier 507 . The R row multiplier 501 calculates the values of an R row. The R memory 509 stores an R matrix vector calculated in the R row multiplier 501 . The Q update multiplier 502 calculates a Q update value.

To have a close look at the constituent elements, the R row multiplier 501 calculates the values of an R row by calculating an operation of r i,j =q k H ·z i based on the Q column vector which is calculated in the Q column multiplier 507 and stored in the Q memory 508 and an inputted reception signal z vector. Since the row values (r i,j ) of the R row calculated in the R row multiplier 501 are row values of the R matrix in the QR decomposition, they are stored in the R memory 509 . Also, the R row multiplier 501 provides a value for signal field detection to a signal field detector 510 .

The Q update multiplier 502 updates a Q value by subtracting a value obtained by summing the R matrix vector calculated in the R row multiplier 501 with a previous Q update value from the reception signal vector z. The updated Q value is delivered to the Q column multiplier 507 to be used for calculation of a Q column value in the next cycle. The operation of the Q update multiplier 502 is represented in Equation 5.

The norm multiplier 503 for calculating a norm, which is a vector size, calculates a norm for q i through an operation of norm i =∥q i ∥ 2 for a channel input after initial FFT. Also, the norm multiplier 503 calculates a norm to be used in the next cycle by using the updated Q value obtained in the Q update multiplier 502 .

The output of the norm multiplier 503 is inputted to lookup table ROMs 504 and 505 , which are a 1/√{square root over (norm)} ROM 504 and a √{square root over (norm)} ROM 505 , individually. Each of the lookup table ROMs 504 and 505 output √{square root over (norm)} and 1/√{square root over (norm)} corresponding to the norm inputted through an operation of r i,j =√{square root over (norm i )}. The value 1/√{square root over (norm)} outputted from the lookup table ROM 504 is stored in a 1/√{square root over (norm)} memory 506 .

The Q column multiplier 507 receives the value outputted from the lookup table ROM 504 and the vector obtained from the calculation of the Q update multiplier 502 , and calculates column values of the Q column through an operation of q i =q i /r i,j . Since the Q column values obtained from the calculation of the Q column multiplier 507 are the result values of a QR matrix used in the signal decoding of reception antennas, they are stored in the Q memory 508 .

FIG. 6 conceptually illustrates operation of a QR decomposition apparatus in accordance with an embodiment of the present invention, and FIG. 7 illustrates a Q matrix and an R matrix calculated in a duration of 8 long training fields.

In the drawing, the QR decomposition apparatus includes R row multipliers 601 , Q update multipliers 602 , a norm update multiplier 603 , lookup table ROMs 604 , and a Q column multiplier 605 .

Referring to FIGS. 6 and 7 , the R row multipliers 601 obtains elements of an R matrix vector by multiplying a reception vector z, which is a long training field, by each column value of a Q memory and stores the elements of the R matrix vector in an R memory.

The Q update multiplier 602 updates a Q value by subtracting a value obtained by summing a previous Q update value, which is stored in the Q memory, with the R matrix vector obtained in the R row multipliers 601 from the reception signal vector z.

The norm multiplier 603 calculates a norm based on the Q update value obtained in the Q update multipliers 602 . The Q column multiplier 605 normalize enable signals of rq1 to rq7 and a value obtained based on the enable signals of rq1 to rq7 by 1/√{square root over (∥qk∥ 2 )} to thereby calculate a Q matrix. The elements of the Q matrix calculated in the Q column multiplier 605 are stored in the Q memory in response to enable signals of q1_we to q8_we. As shown in FIG. 2 , Q H z from DATA0 where data signals of y1 to y8 are received can be obtained based on a vector without additional hardware. Also, an MRC result value for detecting a signal field can be obtained by multiplying a q8 memory by a reception signal z. When a signal field is received in the same method as a long training field LTF 1 is received, the MRC can be obtained by multiplying a q1 memory by the reception signal z.

As illustrated in FIG. 7 , first elements of Q and R are obtained in an LTF 1 duration and stored in the Q and R memories. In LTF 2 to LTF 8 durations, second to eighth elements of Q and R are obtained and stored in the Q and R memories, respectively.

The process of obtaining the Q matrix and the R matrix may be divided on a cyclic basis as follows.

First, in a first cycle, a norm 1 is calculated by using q 1 , which is described as Equation 7, and the first column elements of the Q matrix are calculated based on a √{square root over (nomr 1 )} value.

norm 1 =∥q 1 ∥ 2

r 1,1 =√{square root over (norm 1 )}

q 1 =q 1 /r 1,1   Eq. 7

In the second cycle, the first elements of the R matrix are calculated by multiplying the Q matrix vector obtained based on Equation 8 by the reception vector z. Then, a Q value and a norm are updated, and second column elements of the Q matrix are calculated by using the updated Q value and the updated norm.

Subsequently, in the third cycle, the next elements of the R matrix are calculated by multiplying the Q matrix vectors obtained based on Equation 9 by the reception vector z. Then, the Q value and the norm are updated, and the next column elements of the Q matrix are calculated by using the updated Q value and the updated norm.

In the fourth cycle, the elements of the R matrix are calculated by multiplying the Q matrix vectors obtained based on Equation 10 by the reception vector z. Then, the Q value and the norm are updated, and the next column elements of the Q matrix are calculated by using the updated Q value and the updated norm.

The same process as described in the above is executed up to the seventh cycle. In the eighth cycle, the elements of the R matrix and the Q matrix are calculated as Equation 11.

Meanwhile, the MRC value for detecting a signal field is calculated as the following Equation 12.

MRC=q 1 H Z 9   Eq. 12

In the meantime, data signals of y1 to y8 can be calculated as Equation 13 based on a vector without additional hardware. Herein, j is dtctsycnt and j is equal to or greater than 10.

Q H z

y 1 =q 1 H ·z j

y 2 =q 2 H ·z j

y 3 =q 3 H ·z j

y 4 =q 4 H ·z j

y 5 =q 5 H ·z j

y 6 =q 6 H ·z j

y 7 =q 7 H ·z j

y 8 =q 8 H ·z j   Eq. 13

In the description referring to FIG. 6 , the Q matrix is an 8×8 matrix, which is [q1 q2 q3 q4 q5 q6 q7 q8], and the R matrix can be represented as follows.

The Q H z output of the R row multiplier 601 is [r1k r2k r3k r4k r5k r6k r7k r8k] T and the output of signal field detection is r1k. For convenience in describing cycles, the elements of the R matrix are expressed as follows.

Meanwhile, when a 1/∥q i ∥ 2 value is calculated using a lookup table ROM and the number of bits constituting ∥q i ∥ is great, a ROM having a very wide width is required. For example, when ∥q i ∥ includes 20 bits, the ROM table requires an address of 2 20 =1,048,576 bits. When depth also includes the same 20 bits, a very large ROM having 20,971,520 bits is required. To solve this problem, the present invention uses a floating point operation method to reduce the size of a ROM table.

FIG. 8 describes a floating point operation method. When it is assumed that there is a 20-bit unsigned signal, it can be expressed by 13 bits, including a 10-bit significant value and a 3-bit exponent.

FIG. 9 describes an operation of a ROM table based on the floating point operation method in accordance with an embodiment of the present invention.

The output of the ROM table can be obtained using the significant bits as the address in the ROM table, and the output of the exponent can be obtained through a simple bit shift. To take an example of floating point 13 bits, the width of the ROM table is 10 bits and the depth is 10 bits. Thus, the size of the ROM table comes to 10,240. Accordingly, the size and address of the ROM table can be reduced remarkably. To reduce the size and address of the ROM table, the QR decomposition apparatus of the present invention includes a floating point converter for inputting the norm transmitted from the norm multiplier or a norm update multiplier converted in the form of floating points to the ROM table by using the significant value as the address, and inputting the exponent through shift.

Although the embodiment of the present invention described above presents the QR decomposition apparatus including 8 antennas and 8 long training fields, it is obvious to those skilled in the art to which the present invention pertains that the present invention can be easily applied to cases employing different numbers of antenna and long training fields.

The method of the present invention described above may be programmed for a computer. Codes and code segments constituting the computer program may be easily inferred by a computer programmer of ordinary skill in the art to which the present invention pertains. The computer program may be stored in a computer-readable recording medium, i.e., data storage, and it may be read and executed by a computer to realize the method of the present invention. The recording medium includes all types of computer-readable recording media.

The technology of the present invention described above can simplify a hardware structure by sharing multipliers to thereby reduce the number of multipliers during QR decomposition in an MIMO receiver.

While the present invention has been described with respect to the specific embodiments, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention as defined in the following claims.