Transcript Slide 1

How to Choose a Walsh Function
Darrel Emerson
NRAO, Tucson
(1913)
What’s a Walsh Function?
•
A set of orthogonal functions
Can be made by multiplying together selected square waves of frequency 1, 2, 4, 8,16 …
[i.e. Rademacher functions R(1,t), R(2,t), R(3,t) R(4,t), R(5,t) …]
The Walsh Paley (PAL) index is formed by the sum of the square-wave indices of the
Rademacher functions
E.g
.
R(1,t)*R(2,t)*R(3,t) is a product of frequencies 1, 2 and
4
=PAL(7,t)
Product of Rade mache r Functions produce a Walsh
function
16
12
Amplitude
•
•
R(1,t)
8
R(2,t)
R(3,t)
4
PAL(7,t)
0
-4
Tim e (1 period)
Ordering Walsh Functions
• Natural or Paley order: e.g. product of square waves of
frequencies 1, 2 & 4 (Rademacher functions 1,2 & 3) = PAL(7,t)
• WAL(n,t): n=number of zero crossings in a period. Note
PAL(7,t)=WAL(5,t)
• Sequency: half the number of zero crossings in a period:
• CAL or SAL. (Strong analogy with COSINE and SINE functions.)
• Note
WAL(5,t)=SAL(3,t),
WAL(6,t)=CAL(3,t)
Mathematicians usually prefer PAL ordering.
For Communications and Signal Processing work,
Sequency is usually more convenient.
For ALMA, sometimes PAL, sometimes WAL is most
convenient
WAL12,t)
From Beauchamp, “Walsh Functions and their Applications”
Dicke Switching or Beam Switching
ON source
OFF source
PAL(1,T)
PAL(3,T)
PAL(7,T)
off – on – off – on – off – on – off – on -
Rejects DC term
off – on – on – off – off – on – on – off -
Rejects DC + linear drift
off – on – on – off – on – off – off – on -
Rejects DC + linear + quadratic drifts
PAL index (2N-1) rejects orders of drift up to (t N - 1)
ALMA WALSH MODULATION
1st
First
mixer
LO
180
180
Walsh
generators
Spur
reject
90
90
Sideband
separation
Dig.
Dig.
+
-
Antenna #1
DTS
Correlator
DTS
Antenna #2
TIMING ERRORS
• If there is a timing offset between Walsh modulation and
demodulation, there is both a loss of signal amplitude and a
loss of orthogonality.
Timing offsets at some level are inevitable, & can arise from:
– Electronic propagation delays, PLL time constants, &
software latency
– Differential delays giving spectral resolution in any
correlator (XF or FX)
Mitigation of effect of Walsh timing errors is
the subject of the remainder of this talk.
Sensitivity loss
If a Walsh-modulated signal is demodulated correctly, the
no loss of signal (Left)
If a Walsh-modulated signal is demodulated with a timing
error, there is loss of signal (loss of “coherence”) (Ri
Self product of WAL(5,t) w ith a tim e slip
Self product of WAL(5,t) with itself, no time slip
12
12
8
WAL(5,t)
WAL(5,t)
4
WAL(5,t)
Product w ithout slip
Amplitude
Amplitude
8
WAL(5,t) with a time
delay
4
Product without slip
Product with slip
Product 
0
0
-4
-4
Tim e (1 period)
Correct demodulation
Tim e (1 period)
Timing error
Loss of sensitivity, % , for timing offset of 1% of shortest bit length
2.50%
Sensitivity loss (%)
2.00%
1.50%
1.00%
0.50%
0.00%
0
20
40
60
80
100
120
140
WAL(N,t) (N~SEQUENCY * 2)
Loss of Sensitivity for a timing offset of 1% of the shortest Walsh bit length
Crosstalk, or Immunity to Correlated Spurious Signals
WAL(5,t)*[WAL(6,t)
shifted]
WAL(5,t)*WAL(6,t)
No Crosstalk
Crosstalk.
Spurious signals not
Product of WAL(5,t) with WAL(6,t) shifted
suppressed
Product 
12
12
8
8
WAL(5,t)
4
WAL(6,t)
Product
Amplitude
Amplitude
Product of WAL(5,t) with WAL(6,t)
WAL(5,t)
4
WAL(6,t) shifted
Product
0
0
-4
-4
Tim e (1 period)
Product averages to zero
Time (1 period)
Product does not average to zero
A matrix of cross-product
amplitudes
For 128-element Walsh function
set.
In WAL order
Amplitudes are shown as
0 dB, 0 dB to -20 dB, -20 to -30
dB,
with 1% timing offset.
NOT
ALLthan
CROSS-PRODUCTS
Weaker
-30 dB is left
blank.
WITH
A TIMING ERROR
GIVE CROSS-TALK
ODD * EVEN always orthogonal
ODD * ODD
never
EVEN * EVEN sometimes
Loss of sensitivity, % , for timing offset of 1% of shortest bit length
2.50%
RSS crosstalk power
Sensitivity loss (%)
2.00%
1.20%
1.50%
1.00%
0.50%
1.00%
0.00%
0
20
40
60
80
RSS Crosstalk powers (%)
WAL(N,t) (N~SEQUENCY * 2)
0.80%
0.60%
0.40%
0.20%
0.00%
0
20
40
60
80
100
120
WAL index
Crosstalk: The RSS Cross-talk amplitude of a given Walsh function,
when that function is multiplied in turn by all other different functions in a
128-function Walsh set.
140
100
120
140
Finding a good set of functions
•
It is not feasible to try all possibilities.
The number of ways of choosing r separate items from a set of N, where
order is not important, is given by:
N
( N  r) r
For N=128, r=64, this is
37
2 .39 5 1 0
Optimization strategy
1. Choose r functions at random from N, with no duplicates.
Typically for ALMA: N=128, r= # antennas = 64
2. Vary each of the r functions within that chosen set, one by one, to
optimize the property of the complete set.
3. Repeat, with a different starting seed. 10 6 to 10 7 tries.
4. Look at the statistics of the optimized sets of r functions.
Relative probability
64 Antennas: Relative probability of given level
of Xtalk occurring
1.2
1
0.8
0.6
0.4
0.2
0
Rel. Probability of
given RSS
crosstalk value
Gauss fit
3.2
3.7
4.2
RSS crosstalk, % , for 1% timing shift
From sets of 64 functions selected from 128 to give the maximum count
(=1621/2016) of zero cross-products.
The relative occurrence of a given level of RSS crosstalk between
all cross-products of that set, with 1% timing offset
Most likely level of RSS cross-talk 3.79%. Lowest 3.4%.
A possible choice of functions for 50, or 64 antennas,
from a 128-function set, chosen to:
1. Maximize number of zero cross-products (1621/2016)
2. Then minimize the RSS cross-product amplitude (3.4%)
0
1
2
3
4
7
8
11
12
15
16
22
23
24
31
32
34
35
37
39
40
44
47
48
51
52
55
56
59
61
62
63
64
67
69
71
72
79
80
81
84
87
88
89
91
94
95
96
103
104
111
112
114
115
116
119
120
121
122
123
124
125
126
127
-
-
( For the best 50 functions, omit those given in bold font.)
However, maximizing the number of zero cross-products
does not lead to the best result
64 Antennas: Relative probability of given level
of Xtalk occurring
Relative probability of given level of Xtalk occurring
1.2
1
Relative probability
Relative probability
Preselected for max # zero cross-products
Rel. Probability of
Chosen randomly
0.8
0.6
1.2
1
0.8
0.6
0.4
0.2
0
given RSS
crosstalk value
Rel. Probability ofGauss fit
given RSS
crosstalk value
3.2
3.7
RSS crosstalk, % , for 1% timing shift
0.4
0.2
0
2.00
4.2
Gauss fit
2.50
3.00
3.50
4.00
4.50
RSS crosstalk, % , for 1% timing shift
From different sets of 64 functions, chosen at random from the original 128-function
Walsh set, relative occurrence of the value of cumulative RSS of crosstalk summed
over all possible cross-products of each set.
Criteria for choosing the
subset of 64 functions from
the total set of 128 Walsh
functions
Randomly chosen, no
optimization, most probable
result
RSS
Crosstalk
Level (1%
time slip)
Number
of
zero
products
Total # crossproducts
(excluding
self-products)
Total
Sensitivity
Loss (1%
time slip)
The set of
functions:
WAL indices
3.25%
1362
2016
1%
Most subsets of 64
functions
randomly chosen
from 0-127
Random seed, selecting only
sets having the maximum
number of zero cross-products
3.79%
1621
2016
1%
(Not useful)
Random seed, then optimize
for max number of zero
products, then minimize RSS
crosstalk
3.41%
1621
2016
1%
See Table 1
Random seed, then optimize
only for max number of zero
products.
Worst crosstalk could be:
4.3%
1621
2016
1%
(Not useful)
Lowest possible sensitivity
loss, ignoring crosstalk
2.31%
1365
2016
0.50%
WAL 0-63
Worst possible sensitivity
loss, ignoring crosstalk
2.31%
1365
2016
1.50%
WAL 64-127
Random seed, then optimize
for minimum RSS crosstalk,
then minimize sensitivity loss
1.82%
1366
2016
0.80%
WAL indices
0-31,47-63,113-127
The magic set of Walsh functions for 64 ALMA antennas:
WAL indices 0-31, 47-63, 113-127
Thanks for listening.
THE END
(1913)