sea_det.html

sphere decoding for MIMO communication system

disp([xHatML xHatMLV]);
fprintf(<span class="string">'Verify squared distances [wHatML wHatMLV] = '</span>);
disp([wHatML wHatMLV]);
</pre><pre class="codeoutput">Solutions                    [xHat xHatV] =    -1 -  i   -1 - 2i
                                               -1 + 2i   -1 + 3i
                                                     2         2          
                                                     i         i

Search distances             [wHat wHatV] =    31.7508   25.3356

# of expansions                  [nv nvV] =         59        13

# of flops (approx.)             [nf nfV] =       1506       352

# of leafs visited               [nl nlV] =          7         2

Verify solutions         [xHatML xHatMLV] =    -1 -  i   -1 - 2i
                                               -1 + 2i   -1 + 3i
                                                     2         2          
                                                     i         i

Verify squared distances [wHatML wHatMLV] =    31.7508   25.3356

</pre><h2>References<a name="4"></a></h2>
      <p>For more details and bibliographic information on the <tt>SEA_det</tt> algorithm and sequential decoding of lattice codes (with and without justified rectangular boundary control), please see
         the following technical report:
      </p>
      <p>K. Su, <b>Efficient ML detection for communication over MIMO channels</b>, Technical Report, Feb. 2005, University of Cambridge.
      </p>
      <p>which is available <a href="http://www.comm.utoronto.ca/~karen/research.php#SDpubs">here</a>, and its companion website:
      </p>
      <p><a href="http://www.comm.utoronto.ca/~karen/spheredec.php#SE">The
			Schnorr-Euchner Enumeration with Adaptive Search Radius</a></p>
      <p class="footer"><br>
         Published with MATLAB&reg; 7.0.1<br></p>
      <!--
##### SOURCE BEGIN #####
%% SEA_det
% A stack-based sequential depth-first decoder that returns Maximum-Likelihood
% solutions to M-QAM modulated MIMO system-type problems, i.e., a lattice
% decoder with optional justified rectangular boundary control.  In such
% problems, the depth of the search tree is known and the number of children
% per node is also fixed.
%
% Real or complex inputs are permitted.  The depth-first search is effected by
% applying the *Schnorr-Euchner (Adaptive radius)* enumeration to traverse the
% nodes of the tree.
%
% Please send comments and bug reports to [e-mail].

%% Basic Operation
% The real-valued version of this stack-based sequential decoding algorithm is
% based on a decoding tree of |m+1| levels with each node having |2*xMax|
% children.  At each stage, the node under consideration is expanded if its
% weight is less than the squared distance to nearest currently known lattice
% point.  This distance threshold is initially set to infinity.
%
% Because it is a depth-first traversal, we expand a node by computing its
% first child.  If it is a leaf node, clearly it cannot be further expanded.
% In this case, we will have found a closer lattice point than that previously
% known. Therefore we can adaptively reduce the distance threshold to reflect
% this new discovery.
%
% If the weight of the node under consideration is larger than this distance
% threshold, then the current search path is terminated because it cannot
% possibly lead to a closest lattice point. Upon path termination, the next
% node to be considered is the next sibling of its parent.

%% Detailed Parameter Specification
% If |xMax == 0|, we do not apply (rectangular, or any) boundary control. In
% other words, |SEA_det| behaves as a lattice decoder.
%
% For more sophisticated operation, |xMax| may also be a vector of length |m|.
% Then each node at the beginning of stage |j| in the tree, where the root node
% is at the beginning of stage |m| and the leaf nodes are found at the end of
% stage |1|, has |2*xMax(j)| children.  Equivalently, symbol |xHat(j)| is drawn
% from |{-xMax(j)+1,..,-1,0,1,..,xMax(j)}|.
%
% If |cplx == 1|, we consider a tree of |2*m+1| levels with each node still
% having |2*xMax| children. In addition, either |xMax| should be a
% complex-valued vector, or |imag(xMax)| will be taken to be equal to
% |real(xMax)|, i.e., a square QAM constellation will be assumed by default.
%
% If either lattice reduction assistance or MMSE pre-processing are desired,
% these operations should be applied in advance of calling |SEA_det|.
%
% Notes:
%
% - |size(H,1)| is expected to be equal to |length(y)|.
%
% - |size(H,1)| is expected to be greater than or equal to |size(H,2)|.
%
% - |size(H,2)| is expected to be equal to |m|.
%
% - |length(xMax)| is expected to be equal to either |1| or |m|.
%
% - The solution |xHat| is an integer vector; be sure to apply any necessary 
%   scaling prior to calling |SEA_det| so that this solution is appropriate.

%% Usage Example
m    = 4;                            % 4x4 MIMO system
xMax = 2;                            % 16-QAM modulation
cplx = 1;
y    = 3*(randn(m,1)+i*randn(m,1));  % generate random complex target vector
H    = randn(m,m)+i*randn(m,m);      % generate random complex channel
[xHat,wHat,nv,nf,nl] = SEA_det(m,xMax,y,H,cplx);
xMaxV = [3 3 2 1];                   % various square modulations
[xHatV,wHatV,nvV,nfV,nlV] = SEA_det(m,xMaxV,y,H,cplx);

fprintf('Solutions                     [xHat xHatV] = ');
disp([xHat xHatV]);
fprintf('Search distances              [wHat wHatV] = ');
disp([wHat wHatV]);
fprintf('# of expansions                   [nv nvV] = ');
disp([nv nvV]);
fprintf('# of flops (approx.)              [nf nfV] = ');
disp([nf nfV]);
fprintf('# of leafs visited                [nl nlV] = ');
disp([nl nlV]);

wHatML  = Inf;
wHatMLV = Inf;
xMaxT   = max(xMax,xMaxV);
for jj = -xMaxT(1)+1:xMaxT(1)
  for kk = -xMaxT(2)+1:xMaxT(2)
    for ll = -xMaxT(3)+1:xMaxT(3)
      for mm = -xMaxT(4)+1:xMaxT(4)
        for jjc = -xMaxT(1)+1:xMaxT(1)
          for kkc = -xMaxT(2)+1:xMaxT(2)
            for llc = -xMaxT(3)+1:xMaxT(3)
              for mmc = -xMaxT(4)+1:xMaxT(4)
                xHatT = [jj+i*jjc;kk+i*kkc;ll+i*llc;mm+i*mmc];
                wHatT = norm(y-H*xHatT)^2; 
                if wHatT < wHatMLV & sum([real(xHatT);imag(xHatT)]>=-repmat(xMaxV,1,2).'+1) == 8 & sum([real(xHatT);imag(xHatT)]<=repmat(xMaxV,1,2).') == 8
                  wHatMLV = wHatT;
                  xHatMLV = xHatT;
                end
                if wHatT < wHatML & sum([real(xHatT);imag(xHatT)]>=-xMax+1) == 8 & sum([real(xHatT);imag(xHatT)]<=xMax) == 8
                  wHatML = wHatT;
                  xHatML = xHatT;
                end
              end
            end
          end
        end
      end
    end
  end
end

fprintf('Verify solutions         [xHatML xHatMLV] = ');
disp([xHatML xHatMLV]);
fprintf('Verify squared distances [wHatML wHatMLV] = ');
disp([wHatML wHatMLV]);

%% References
% For more details and bibliographic information on the |SEA_det| algorithm and
% sequential decoding of lattice codes (with and without justified rectangular
% boundary control), please see the following technical report:
%
% K. Su, *Efficient ML detection for communication over MIMO channels*,
% Technical Report, Feb. 2005, University of Cambridge. 
%
% which is available http://www.comm.utoronto.ca/~karen/research.php#SDpubs,
% and its companion website:
%
% http://www.comm.utoronto.ca/~karen/spheredec.php#SE

##### SOURCE END #####
-->
   </body>
</html>