Application-Specific Accelerators for Communications - Signal Processing Systems - page 737

w

1

2

i=M

1 2 w 1 2 w

i=M-1

1 2 w 1 2 w

1 2 w

i=1

Fig. 7 Calculating the distances using a tree. Partial norms, PN s, of dark nodes are less than the
threshold. White nodes are pruned out

where H QR represents the channel matrix QR decomposition, R is an upper

triangular matrix, QQ H

=

Q H y .
The norm in Eq. ( 4 ) can be computed in M iterations starting with i

I and y =

=

= M .When

s ( M + 1 ) )=

i 0.

Using the notation of [ 12 ] , at each iteration the Partial Euclidean Distances (PEDs)
at the next levels are given by

= M , i.e. the first iteration, the initial partial norm is set to zero, T M + 1 (

s ( i ) )= s ( i + 1 ) )+ | s ( i ) ) |

2

T i ( T i + 1 ( e i ( (5)

with s ( i ) =[

T ,and i

s i , s i + 1 ,..., s M ] = M , M − 1 ,..., 1, where

M
∑

s ( i ) ) | y i −

2 2

| e i ( = | R i , i s i − R i , j s j | . (6)

j = i + 1

One can envision this iterative algorithm as a tree traversal with each level of the tree
corresponding to one i value or transmit antenna, and each node having w children
based on the modulation chosen.
The norm in Eq. ( 6 ) can be computed in M iterations starting with i

M ,
where M is the number of transmit antennas. At each iteration, partial (Euclidian)
distances, PD i = |

=

M
j = i R i , j s j |

2 corresponding to the i -th level, are calculated
and added to the partial norm of the respective parent node in the ( i

y i − ∑

− 1)-th level,

PN i = PN i − 1 + PD i .When i = M , i.e. the first iteration, the initial partial norm is

set to zero, PN M + 1 = 0. Finishing the iterations gives the final value of the norm.

AsshowninFig. 7 , one can envision this iterative algorithm as a tree traversal