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 karen.su@utoronto.ca.
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.
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.
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]);
Solutions [xHat0 xHat4 xHatV0 xHatV4] = -1 + i -1 + i -1 -1
0 0 0 0
0 0 -1 + i -1 + i
2 - i 2 - i 1 1
Search distances [wHat0 wHat4 wHatV0 wHatV4] = 11.2992 11.2992 15.6888 15.6888
# of expansions [nv0 nv4 nvV0 nvV4] = 30 18 52 17
# of nodes leftover [nn0 nn4 nnV0 nnV4] = 30 4 50 4
# of flops (approx.) [nf0 nf4 nfV0 nfV4] = 936 558 1576 511
# of nodes dropped [nd0 nd4 ndV0 ndV4] = 0 14 0 13
Verify solution [xHatML xHatMLV] = -1 + i -1
0 0
0 -1 + i
2 - i 1
Verify squared distance [wHatML wHatMLV] = 11.2992 15.6888
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.
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 here, and its companion website: