talg_det.html

Stack-based sequential decoder for M-QAM modulated MIMO-type problems, i.e., of fixed tree depth.

Verify solution             [xHatML xHatMLV] =     -1 + i                  -1
                                                        0                   0          
                                                        0              -1 + i
                                                    2 - i                   1

Verify squared distance     [wHatML wHatMLV] =    11.2992             15.6888

</pre><h2>Mex Notes<a name="4"></a></h2>
      <p>Note that this distribution has only been tested with Matlab 7.0.1 R14SP1 in Linux and Matlab 6.5 R13 in Windows (with MSVC).
          If you are not using one of these releases, then you may need to recompile the source files to run most effectively with
         your version of Matlab.
      </p>
      <p>To recompile for Linux, open the file <tt>heap.c</tt> in your favourite editor and comment out or remove Line <tt>22</tt> (approx.), which reads <tt>#define VER7R14</tt>. Then at the Matlab prompt, type <tt>mex heap.c</tt>; a library named <tt>heap.mexglx</tt> should have been compiled.
      </p>
      <p>In Matlab for Windows, the same procedure should generate a compiled library named <tt>heap.dll</tt>.  Further, if Microsoft Visual C/C++ is installed on your system, then you will also have to open the file <tt>heap.c</tt> in your favourite editor and uncomment Line <tt>25</tt> (approx.), which reads <tt>#define MSVC</tt>.
      </p>
      <h2>References<a name="5"></a></h2>
      <p>For more details on the <tt>Talg_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/seqdecTi.php">An Ordered
				Traversal Detector, a.k.a. Priority First T-algorithm Lattice Decoder
				with Optional Justified Rectangular Boundary Control</a>.</p>
      <p class="footer"><br>
         Published with MATLAB&reg; 7.0.1<br></p>
      <!--
##### SOURCE BEGIN #####
%% Talg_det
% A stack-based sequential priority 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 priority first search is effected
% by maintaining a priority queue of nodes and expanding them in order.  Thus
% the decoder is also referred to as an *Ordered (Tree) Traversal Decoder*. In
% practice, this implementation of the sequential decoding algorithm is near-ML
% because it operates with finite memory. If that memory is exceeded, nodes are
% dropped from the stack and the number of such dropped nodes is returned.
%
% In addition, this implementation allows specification of the size of the
% finite memory block (in terms of number of nodes) allocated for its
% execution. Generally we find that restricting the sequential decoder to
% finite memory is not a major consideration, as very near-ML performance can
% be achieved with relatively low allocations.
%
% 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 with the smallest weight is expanded by
% computing its first child and next sibling nodes.  Not all computed nodes are
% eventually expanded; in particular |nv| nodes are expanded and |nn+nv+nd|
% nodes are computed.  The stack maintains a list of those nodes that are
% known, i.e., have been computed, but that have not yet been expanded. 
%
% If |T| is exceeded during the replacement of a node by its first child and
% next sibling, then the last node in the heap is dropped.  Note that this node
% may not necessarily have the largest weight, since the stack is not totally
% ordered.

%% Detailed Parameter Specification
% If |T == 0|, we use a heap having a reasonable maximum size of |32768| nodes.
%
% If |xMax == 0|, we do not apply (rectangular, or any) boundary control.  In
% other words, |Talg_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 |Talg_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|.
%
% - Because of Matlab memory issues that appear to be un-trappable (R14SP1), 
%   a practical upper bound of |2^15| is encouraged for |T|. At the caller's
%   risk it can be exceeded by explicitly setting |T| to a larger value.
%
% - The solution |xHat| is an integer vector; be sure to apply any necessary 
%   scaling prior to calling |Talg_det| so that this solution is appropriate.

%% Usage Example
T    = 4;                            % max stack size of 4
m    = 4;                            % 4x4 MIMO system
xMax = 2;                            % 16-QAM modulation
cplx = 1;
y    = 2*(randn(m,1)+i*randn(m,1));  % generate random complex target vector
H    = randn(m,m)+i*randn(m,m);      % generate random complex channel
[xHat4,wHat4,nv4,nn4,nf4,nd4] = Talg_det(T,m,xMax,y,H,cplx);
[xHat0,wHat0,nv0,nn0,nf0,nd0] = Talg_det(0,m,xMax,y,H,cplx);
xMaxV = [3 3 2 1];                   % various square modulations
[xHatV4,wHatV4,nvV4,nnV4,nfV4,ndV4] = Talg_det(T,m,xMaxV,y,H,cplx);
[xHatV0,wHatV0,nvV0,nnV0,nfV0,ndV0] = Talg_det(0,m,xMaxV,y,H,cplx);

fprintf('Solutions        [xHat0 xHat4 xHatV0 xHatV4] = ');
disp([xHat0 xHat4 xHatV0 xHatV4]);
fprintf('Search distances [wHat0 wHat4 wHatV0 wHatV4] = ');
disp([wHat0 wHat4 wHatV0 wHatV4]);
fprintf('# of expansions          [nv0 nv4 nvV0 nvV4] = ');
disp([nv0 nv4 nvV0 nvV4]);
fprintf('# of nodes leftover      [nn0 nn4 nnV0 nnV4] = ');
disp([nn0 nn4 nnV0 nnV4]);
fprintf('# of flops (approx.)     [nf0 nf4 nfV0 nfV4] = ');
disp([nf0 nf4 nfV0 nfV4]);
fprintf('# of nodes dropped       [nd0 nd4 ndV0 ndV4] = ');
disp([nd0 nd4 ndV0 ndV4]);

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 solution             [xHatML xHatMLV] = ');
disp([xHatML xHatMLV]);
fprintf('Verify squared distance     [wHatML wHatMLV] = ');
disp([wHatML wHatMLV]);

%% Mex Notes
% Note that this distribution has only been tested with Matlab 7.0.1 R14SP1 in
% Linux and Matlab 6.5 R13 in Windows (with MSVC).  If you are not using one of
% these releases, then you may need to recompile the source files to run most
% effectively with your version of Matlab.
%
% To recompile for Linux, open the file |heap.c| in your favourite editor and
% comment out or remove Line |22| (approx.), which reads |#define VER7R14|.
% Then at the Matlab prompt, type |mex heap.c|; a library named |heap.mexglx|
% should have been compiled.
%
% In Matlab for Windows, the same procedure should generate a compiled library
% named |heap.dll|.  Further, if Microsoft Visual C/C++ is installed on your
% system, then you will also have to open the file |heap.c| in your favourite
% editor and uncomment Line |25| (approx.), which reads |#define MSVC|.

%% References
% For more details on the |Talg_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/seqdecTi.php

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