MU-MIMO: one of the implementation algorithms

MU-MIMO: one of the implementation algorithms


Preface


As a supplement to my recent article I would also like to talk about the topic of MU ( M ulti U ser) MIMO. I have already mentioned Professor Haardt one very well-known article <5 channel (Down Link) based on linear methods, namely diagonalization (Block Diagonalization) of the channel. The article has an impressive number of citations , and is also the cornerstone publication for one of the exam assignments. So why not make out the basics of the proposed algorithm?



( link to the source of the image )


Problem Statement


First, let's decide in which area in the subject of MIMO we will work now.
Conventionally, all methods of transmission within the framework of MIMO technology can be divided into two main groups:


  • Spatial diversity (spatial diversity).

The main goal is to increase the noise immunity of the transmission. Spatial channels, if simplified, duplicate each other, due to which we get the best quality transmission.


Examples:
  - Block codes (for example, Alamouti scheme );
  - Codes based on the Viterbi algorithm.



The main goal is to increase transfer speed . We already discussed in the previous article that, under certain conditions, a MIMO channel can be viewed as a series of parallel SISO channels. As a matter of fact, this is the central idea of ​​spatial multiplexing: to achieve the maximum number of independent information flows. The main problem in this case is the suppression of inter-channel interference (inter-channel interference) , for which there are several classes of solutions:


- horizontal channel separation;
  - vertical (for example, V-BLAST algorithm);
  - diagonal (for example, the D-BLAST algorithm).


But this, of course, is not all.


The idea of ​​spatial multiplexing can be expanded: to separate not only channels, but also users (SDMA - Space Division Multiple Access).



( link to the source of illustration )


Consequently, in this case it is already necessary to fight with the inter-user interference (inter-user interference) . That is what the algorithm called Block diagonalization Zero-Forming was proposed, which we are considering today.


Mathematical description


We begin, as before, with the received signal model (received signal). Or rather, we will show on the diagram what goes where and what happens:



The channel matrix in this case is:


\ underset {M_R \ times M_T} {\ mathbf {H}} = \ begin {bmatrix} \ underset {M_  {R1} \ times M_T} {\ mathbf {H} _1} \\ \ underset {M_ {R2} \ times M_T} {\ mathbf {H} _2} \\. \\. \\. \\ \ underset {  M_ {RK} \ times M_T} {\ mathbf {H} _K} \ end {bmatrix} \ qquad (1)

with a total number of transmit antennas M_T and the total number of receiving antennas M_R = \ sum_ {k = 1} ^ K M_ {Rk} .


Important :
This algorithm can be applied only if the number of transmitting antennas is greater than or equal to the total number of receiving antennas:
M_R \ leq M_T


This condition directly affects the properties of diagonalization.

So, the model of the received symbols (signals) can be written in vector form as:


\ mathbf {r} = \ mathbf {D} \ left (\ mathbf {H} \ mathbf {F} \  mathbf {s} + \ mathbf {n} \ right) \ qquad (2) <> div>

However, it is more interesting to look at the formula for a specific user:


r_k = \ mathbf {D} _k \ left (\ mathbf {H} _k \ mathbf {F} _k s_k +  \ mathbf {H} _k \ sum_ {i = 1, i \ neq k} ^ K \ mathbf {F} _i s_i + n_k \ right) \ qquad (3)

Strictly speaking:


  • \ mathbf {H} _k \ mathbf {F} _k s_k is a useful signal for the k-th user,


  • \ mathbf {H} _k \ sum_ {i = 1, i \ neq k} ^ K \ mathbf {F} _i s_i is interference from other users,



  • n_k - additive noise.

Here we come to the formulation of the main task:


One can after all find such matrices \ mathbf {F} so that the interference part turned to zero!

This is what we are going to do.


Algorithm Description


We’ll take a description with an example, and as an illustration I’ll provide screenshots of firsthand , a little commenting on them.


Consider the first user:



Let's talk the basic steps:


  • We compose some matrix \ mathbf {\ hat {H} _1 from channel matrices of all other users.

  • We decompose it with the SVD method.


  • In the matrix \ mathbf {\ hat {V} _1 find the noise subspace (null-subspace) - the matrix  \ mathbf {\ hat {V} _1 ^ {(0)} (i.e., everything that goes beyond rank of the matrix  \ mathbf {\ hat {H} _1} - we denote it by d).


  • We compose some projection matrix from this noise matrix and its Hermitian conjugation \ mathbf {P_1}.



Going further:



  • Now the original part of the channel matrix \ mathbf {H} _1 Multiply with the resulting projection matrix


  • We decompose the result through SVD.


  • In the matrix \ mathbf {V_1} ^ H choose r lines where r.


  • Transpose them and get the matrix/> (or \ mathbf {M} _1> - where they are denoted as) .



And so this procedure will be repeated for each user. Isn't that the magic of mathematics: using the methods of linear algebra, we solve quite technical problems!


Note that in practice, not only the obtained pre-coding matrices are used, but both the post-processing matrices and singular value matrices (see slides ). The latter, for example, for power balancing according to the algorithm Water-pouring already familiar to us.

Model the algorithm


I think it would not be superfluous to conduct a small simulation to fix the result. For this we will use Python 3, namely:


  import numpy as np  

for basic calculations, and:


  import pandas as pd  

to display the result.


In order not to pile on, I’ll put the source code here
  class ZeroForcingBD:
  def __init __ (self, H, Mrs_arr):
  Mr, Mt = np.shape (H)
  self.mr = Mr
  self.Mt = Mt
  self.H = H
  self.Mrs_arr = Mrs_arr

  def __routines (self, H, mr, shift):

  # used in self.process () - See example above for illustration
  # inputs:
  # H - the whole channel matrix
  # mr - number of receive antennas of the i-th user
  # shift - how much receive antennas were considered before
  # outputs:
  # Uidx, Sigmaidx, Vhidx - SVD decomposition of the H_iP_i
  # d - rank of the hat H_i
  # Hidx - H_i (channel matrix for the i-th user)
  # r - rank of the H_i

  Hidx = H [0 + shift: mr + shift,:] # H_i (channel matrix for the i-th user)
  r = np.linalg.matrix_rank (Hidx) # rank of the H_i
  del_idx = [i for i in range (0 + shift, mr + shift, 1)] # row indeces of H_i in H
  H_hat_idx = np.delete (H, del_idx, 0) # hat H_i
  d = np.linalg.matrix_rank (H_hat_idx) # rank of the hat H_i
  U, Sigma, Vh = np.linalg.svd (H_hat_idx) # SVD
  Vhn = Vh [d :,:] # null-subspace of V ^ H
  Vn = np.matrix (Vhn) .H # null-subspace of V
  Pidx = np.dot (Vn, np.matrix (Vn) .H) # projection matrix
  Uidx, Sigmaidx, Vhidx = np.linalg.svd (np.dot (Hidx, Pidx)) # SVD of H_iP_i
  return Uidx, Sigmaidx, Vhidx, d, Hidx, r

  def process (self):

  # used in self.obtain_matrices ()
  # outputs:
  # F - whole filtering (pre-coding) matrix (array of arrays)
  # D - whole demodulator (post-processing) matrix (array of arrays)
  # H - the whole channel matrix (array of arrays)

  shift = 0
  H = self.H
  F = []
  D = []
  Hs = []
  for mr in self.Mrs_arr:
  Uidx, Sigmaidx, Vhidx, d, Hidx, r = self .__ routines (H, mr, shift)
  Vhidx1 = Vhidx [: r ,:] # signal subspace
  Fidx = np.matrix (Vhidx1) .H
  F.append (Fidx)
  D.append (Uidx)
  Hs.append (Hidx)
  shift = shift + mr
  return F, D, Hs

  def obtain_matrices (self):

  # used to obtain pre-coding and post-processing matrices
  # outputs:
  # FF - whole filtering (pre-coding) matrix
  # DD - whole demodulator (post-processing) matrix (array of arrays)

  F, D, Hs = self.process ()
  FF = np.hstack (F)
  # Home Task: calculation of the demodulator matrices :)
  return FF  

Suppose we have 8 transmit antennas and 3 users with 3, 2 and 3 receiving antennas, respectively:


  Mrs_arr = [3,2,3]
 # 1st user have 3 receive antennas, 2nd user - 2 receive antennas, 3d user - 3 receive antennas
 Mr = sum (Mrs_arr) # total number of the receive antennas
 Mt = 8 # total number of transmitt antennas
 H = (np.random.randn (Mr, Mt) + 1j * np.random.randn (Mr, Mt))/np.sqrt (2);  #Rayleigh flat faded channel matrix (MrxMt)  

Initialize our class and apply the appropriate methods:


  BD = ZeroForcingBD (H, Mrs_arr)

 F, D, Hs = BD.process ()
 FF = BD.obtain_matrices ()  

We lead to a readable form:


  df = pd.DataFrame (np.dot (H, FF))
 df [abs (df) .lt (1e-14)] = 0  

And let’s light up a bit for clarity (although you can do without it):


  print (pd.DataFrame (np.round (np.real (df), 100)))
  

You should have something like this:



Actually, these are the blocks, this is the diagonalization. And minimizing interference.


Such cases.


Literature


  1. Spencer, Quentin H., A. Lee Swindlehurst, and Martin Haardt. "Zero-forcing methods for downlink spatial multiplexing in multiuser MIMO channels." IEEE transactions on signal processing 52.2 (2004): 461-471.
  2. Martin Haard " Robust Transmit Processing for Multi-User MIMO Systems "

P.S.


The faculty and student fraternity my native specialty say hello!

Source text: MU-MIMO: one of the implementation algorithms