📄 talg_det.html
字号:
<html xmlns:mwsh="http://www.mathworks.com/namespace/mcode/v1/syntaxhighlight.dtd">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<!--
This HTML is auto-generated from an M-file.
To make changes, update the M-file and republish this document.
-->
<title>Talg_det</title>
<meta name="generator" content="MATLAB 7.0.1">
<meta name="date" content="2006-09-06">
<meta name="m-file" content="Talg_det_doc"><style>
body {
background-color: white;
margin:10px;
}
h1 {
color: #990000;
font-size: x-large;
}
h2 {
color: #990000;
font-size: medium;
}
p.footer {
text-align: right;
font-size: xx-small;
font-weight: lighter;
font-style: italic;
color: gray;
}
pre.codeinput {
margin-left: 30px;
}
span.keyword {color: #0000FF}
span.comment {color: #228B22}
span.string {color: #A020F0}
span.untermstring {color: #B20000}
span.syscmd {color: #B28C00}
pre.showbuttons {
margin-left: 30px;
border: solid black 2px;
padding: 4px;
background: #EBEFF3;
}
pre.codeoutput {
color: gray;
font-style: italic;
}
pre.error {
color: red;
}
/* Make the text shrink to fit narrow windows, but not stretch too far in
wide windows. On Gecko-based browsers, the shrink-to-fit doesn't work. */
p,h1,h2,div {
/* for MATLAB's browser */
width: 600px;
/* for Mozilla, but the "width" tag overrides it anyway */
max-width: 600px;
/* for IE */
width:expression(document.body.clientWidth > 620 ? "600px": "auto" );
}
</style></head>
<body>
<h1>Talg_det</h1>
<introduction>
<p>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.
</p>
<p>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 <b>Ordered (Tree) Traversal Decoder</b>. 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.
</p>
<p>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.
</p>
<p>Please send comments and bug reports to <a href="mailto:karen.su@utoronto.ca">karen.su@utoronto.ca</a>.
</p>
</introduction>
<h2>Contents</h2>
<div>
<ul>
<li><a href="#1">Basic Operation</a></li>
<li><a href="#2">Detailed Parameter Specification</a></li>
<li><a href="#3">Usage Example</a></li>
<li><a href="#4">Mex Notes</a></li>
<li><a href="#5">References</a></li>
</ul>
</div>
<h2>Basic Operation<a name="1"></a></h2>
<p>The real-valued version of this stack-based sequential decoding algorithm is based on a decoding tree of <tt>m+1</tt> levels with each node having <tt>2*xMax</tt> 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 <tt>nv</tt> nodes are expanded and <tt>nn+nv+nd</tt> 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.
</p>
<p>If <tt>T</tt> 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.
</p>
<h2>Detailed Parameter Specification<a name="2"></a></h2>
<p>If <tt>T == 0</tt>, we use a heap having a reasonable maximum size of <tt>32768</tt> nodes.
</p>
<p>If <tt>xMax == 0</tt>, we do not apply (rectangular, or any) boundary control. In other words, <tt>Talg_det</tt> behaves as a lattice decoder.
</p>
<p>For more sophisticated operation, <tt>xMax</tt> may also be a vector of length <tt>m</tt>. Then each node at the beginning of stage <tt>j</tt> in the tree, where the root node is at the beginning of stage <tt>m</tt> and the leaf nodes are found at the end of stage <tt>1</tt>, has <tt>2*xMax(j)</tt> children. Equivalently, symbol <tt>xHat(j)</tt> is drawn from <tt>{-xMax(j)+1,..,-1,0,1,..,xMax(j)}</tt>.
</p>
<p>If <tt>cplx == 1</tt>, we consider a tree of <tt>2*m+1</tt> levels with each node still having <tt>2*xMax</tt> children. In addition, either <tt>xMax</tt> should be a complex-valued vector, or <tt>imag(xMax)</tt> will be taken to be equal to <tt>real(xMax)</tt>, i.e., a square QAM constellation will be assumed by default.
</p>
<p>If either lattice reduction assistance or MMSE pre-processing are desired, these operations should be applied in advance of
calling <tt>Talg_det</tt>.
</p>
<p>Notes:</p>
<p>- <tt>size(H,1)</tt> is expected to be equal to <tt>length(y)</tt>.
</p>
<p>- <tt>size(H,1)</tt> is expected to be greater than or equal to <tt>size(H,2)</tt>.
</p>
<p>- <tt>size(H,2)</tt> is expected to be equal to <tt>m</tt>.
</p>
<p>- <tt>length(xMax)</tt> is expected to be equal to either <tt>1</tt> or <tt>m</tt>.
</p>
<p>- Because of Matlab memory issues that appear to be un-trappable (R14SP1), a practical upper bound of <tt>2^15</tt> is encouraged for <tt>T</tt>. At the caller's risk it can be exceeded by explicitly setting <tt>T</tt> to a larger value.
</p>
<p>- The solution <tt>xHat</tt> is an integer vector; be sure to apply any necessary scaling prior to calling <tt>Talg_det</tt> so that this solution is appropriate.
</p>
<h2>Usage Example<a name="3"></a></h2><pre class="codeinput">T = 4; <span class="comment">% max stack size of 4</span>
m = 4; <span class="comment">% 4x4 MIMO system</span>
xMax = 2; <span class="comment">% 16-QAM modulation</span>
cplx = 1;
y = 2*(randn(m,1)+i*randn(m,1)); <span class="comment">% generate random complex target vector</span>
H = randn(m,m)+i*randn(m,m); <span class="comment">% generate random complex channel</span>
[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]; <span class="comment">% various square modulations</span>
[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(<span class="string">'Solutions [xHat0 xHat4 xHatV0 xHatV4] = '</span>);
disp([xHat0 xHat4 xHatV0 xHatV4]);
fprintf(<span class="string">'Search distances [wHat0 wHat4 wHatV0 wHatV4] = '</span>);
disp([wHat0 wHat4 wHatV0 wHatV4]);
fprintf(<span class="string">'# of expansions [nv0 nv4 nvV0 nvV4] = '</span>);
disp([nv0 nv4 nvV0 nvV4]);
fprintf(<span class="string">'# of nodes leftover [nn0 nn4 nnV0 nnV4] = '</span>);
disp([nn0 nn4 nnV0 nnV4]);
fprintf(<span class="string">'# of flops (approx.) [nf0 nf4 nfV0 nfV4] = '</span>);
disp([nf0 nf4 nfV0 nfV4]);
fprintf(<span class="string">'# of nodes dropped [nd0 nd4 ndV0 ndV4] = '</span>);
disp([nd0 nd4 ndV0 ndV4]);
wHatML = Inf;
wHatMLV = Inf;
xMaxT = max(xMax,xMaxV);
<span class="keyword">for</span> jj = -xMaxT(1)+1:xMaxT(1)
<span class="keyword">for</span> kk = -xMaxT(2)+1:xMaxT(2)
<span class="keyword">for</span> ll = -xMaxT(3)+1:xMaxT(3)
<span class="keyword">for</span> mm = -xMaxT(4)+1:xMaxT(4)
<span class="keyword">for</span> jjc = -xMaxT(1)+1:xMaxT(1)
<span class="keyword">for</span> kkc = -xMaxT(2)+1:xMaxT(2)
<span class="keyword">for</span> llc = -xMaxT(3)+1:xMaxT(3)
<span class="keyword">for</span> 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;
<span class="keyword">if</span> 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;
<span class="keyword">end</span>
<span class="keyword">if</span> wHatT < wHatML & sum([real(xHatT);imag(xHatT)]>=-xMax+1) == 8 & sum([real(xHatT);imag(xHatT)]<=xMax) == 8
wHatML = wHatT;
xHatML = xHatT;
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
fprintf(<span class="string">'Verify solution [xHatML xHatMLV] = '</span>);
disp([xHatML xHatMLV]);
fprintf(<span class="string">'Verify squared distance [wHatML wHatMLV] = '</span>);
disp([wHatML wHatMLV]);
</pre><pre class="codeoutput">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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -