Discussion Forums

Walsh system

11 replies [Last post]
Anders Feder
Offline
Joined: 2010-04-22
Posts: 618

I've created an article here about the Walsh system employed to reduce cross-talk at the ATA, based on answers given by Billy Barrot here. Post questions and comments relating to this article or its subject in this thread

maxs-pooper-scooper
Offline
Joined: 2010-07-28
Posts: 58
walsh function wiki comments

< insert obligatory need more math comment >

It appears that essentially, we're artifically chipping the data at 12.8 kHz.  The Walsh functions are from a 256 x 256 Hadamard matrix using rows 2^k, for k=0,1, ..., 7.  This reduces the cross-talk because the Walsh functions are orthogonal.

After reading the thread with Billy Barrot's comment, was anything more found out about the harmonics due to unaligned clock phases?  I thought of two possible concerns.

1. Is the chipping rate undersampling?  For example in CDMA, the symbol duration is much greater than the chip duration.  So you receive between 64-256 chips per symbol.  If the receiver is sampling at 100 MHz, then we would be undersampled.  It might help to increase the chipping rate.

2. Due to the choice of Walsh functions, there could unlucky constructive interference due tot he phase unalignment.  Cleary the choice of Walsh functions was may to simplify the hardware.  Instead we could look at the smaller Hadamard matrices ( 16x16 or 32x32 ) to find the optimal set of 8 rows that reduce these harmonics.

Anders Feder
Offline
Joined: 2010-04-22
Posts: 618
Note that Billy Barrot has

Note that Billy Barrot has since improved the system. Maybe Gerry can tell us if the same functions are still being used.

Anders Feder
Offline
Joined: 2010-04-22
Posts: 618
I agree that more math would

I agree that more math would be desirable. I've opened this issue for the web devs.

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 732
Anders, You completely

Anders, You completely omitted everything I said in that conversation.  Thanks.

In an attempt to be scholarly I added a reference link to explain the source and the context of why the Walshing system was mentioned.  We need to be extra rigorous with citing references in the wiki. References are important because they document where the information came from, who said what, what is the context, and they provide a source of further learning.

In this particular case I feel the context of why the Walshing system was mentioned and the post explanation back-and-forth conversation is almost as important as the description of how it works.  Cite your references and don't allow this valuable information to be lost in the depths of the thousands and thousands of forum comments.

Anders Feder
Offline
Joined: 2010-04-22
Posts: 618
sigblips, please try and be a

sigblips, please try and be a little less edgy - I am not on the payroll of you or anybody else. If you are unhappy with something I do, follow the open source way and do it better yourself. Preferably without dissuading others from contributing in the process.

Like everything, this article is a work-in-progress. It is in the wiki to allow people like yourself to improve upon it. I have already asked the web people to add support for footnotes in the wiki for citations and the thread with your comments is clearly referenced in the original post in the present thread.

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 732
I am disappointed that you

I am disappointed that you don't share the same sense of importance for citing references. Most people are going to find the Walshing wiki page you created and they will have no idea of the existence of this forum page or the original source page. For them all the knowledge about Walshing will begin and end with that wiki page.

Yes, it would be nice if the setiQuest wiki wasn't just an extension of the forum layout and instead used proper wiki software. A connected talk page, version control, edit history, citations, categories, ...  It would be great but since we don't have that we will have to make due with the tools we do have.

maxs-pooper-scooper
Offline
Joined: 2010-07-28
Posts: 58
additional comments from the baudline thread

Redirected the subthread in baudline thread

From Billy Barrot The walsh functions are just analog square waves that drive a mixer, yes. They are all synchronized to each-other on an edge of the 100 Hz wave and phase locked to our master timing system.

The more I think about this, IMHO, I am going to have to respectfully disagree.  For implementation reasons, square waves at doubling frequencies makes perfect sense AND they are Walsh functions.  But a Walsh function is exactly this: Mathworld as sigblips pointed out.  A Walsh function is a row in a Hadamard matrix.

A Hadamard matrix is recursively built.  H_0 = [ + ];  H_{k+1}= [ H_k H_k; H_k -H_k ]
H_1= [ + +; + - ]
H_2= [ + + + +; + - + -; + + - -; + - - + ]
etc...

We are using rows 1, 2, 4, 8, 16, 32, 64, and 128 of H_{8} ( again for use of hardware generation ).

Walsh functions taken from the same Hadamard matrix are orthogonal ... which is why they are used for chipping ( in combination with PN sequences ) in cellular systems.

Suppose we receive two signals, R_k mixed with the Walsh function W_k. Let the processed signals have a little cross-talk. Specifically.
X_1= R_1*W_1 + a_1*R_2*W_2
X_2= R_2*W_2 + a_2*R_1*W_1

I imagine that preprocessor does something like Y_k = X_k * conj( W_k ) in which case we have:
Y_1= R_1*N and Y_2= R_2*N, where N is the length of the Walsh function. 
In this ideal case the \sum_{n=1}^N W_1[n]*conj( W_2[n] )  equals zero by orthogonality.

maxs-pooper-scooper
Offline
Joined: 2010-07-28
Posts: 58
more walsh function ( long post )

I created an Octave script ( at the bottom ) to dig deeper in this Walsh function / harmonic issue.

Based on the discussion in the forum, I assume the following setup. We received K (noisy) signals, x_1, x_2, ..., x_K. Each x_k is mixed with a Walsh function w_k.  The channel to the backend processor has some crosstalk. The backend processor receives the signal r_k= ( x_k w_k ) + \sum_{j \neq k} ( a_j x_j w_j ). The first thing the backend processor does is apply the appropriate Walsh function ( I assume this is the case; this has not been stated on the forum ).
Let y_k= r_k w_k = x_k + { \sum_{j \neq k} ( a_j x_j w_j ) } w_k. (**)

My hypothesis is that the harmonics is due to the mixing of the signal with the Walsh functions. I also propose that the harmonics would disappear if instead we overchip the samples using the Walsh function. By overchip, I mean oversample the receive samples with the Walsh functions. I will also use the term underchip. By that, I mean that the chipping rate is too low. Equivalent thinking of oversample/undersample with respect to sampling rate.

The Octave script tries to evaluate this hypothesis. For simplicity, I only use three Walsh functions. I create a noise-free cosine signal with three different propagation delays. I exaggerate the amount of crosstalk to make the harmonics more noticable. I create the underchipped system expressed in equation (**). I create an overchipped system expressed by the following equations.

r_k[Mn+m]= ( x_k[n] w_k[m] ) + \sum_{j \neq k} ( a_j x_j[n] w_j[m] ) (oo)
y_k[n]= (1/M) \sum_{m=0}^M r_k[Mn+m] w_k[m] (ooo)

where M is the overchip factor.

After running the Octave script, it is easy to see want is going on from the plots. Let upper/lower -case letter represent the frequency/time -domain for a signal. Each figure has four plots. Upper left is a plot of X_k. Upper right is a plot of W_k. Lower left is the frequency domain of the underchipped signal. Lower right is the frequency domain of the overchipped signal. In the lower plots, I also state the average sample squared error with respect to the original signal.

There was some discussion that phase misalignment in the Walsh functions could cause the harmonics. I do not believe that is the case. Clearly, in this example, we see harmonics and I specifically used perfectly phase aligned Walsh functions. Looking at the math, we can see that the phase misalignment does not cause the harmonics. Let us further express (**) by each sample and include the misalignment.
y_k[n]= r_k[n] w_k[n+p] = ( x_k[n] w_k[n] w_k[n+p] ) + { \sum_{j \neq k} ( a_j x_j[n] w_j[n] ) } w_k[n+p].

Let us go to the frequency domain
Y_k[f]= ( X_k[f]*W_k[k]*W_k[f] exp(j f p) ) + { \sum_{j \neq k} ( a_j X_j[f]*X_j[n]*W_k[f] exp(j f p ) ) }
where f is \omega and * denotes convolution.

So we see that the misalignment on causes a phase shift in the frequency domain. This would not cause harmonics to show up in the magnitude response. The cause of the harmonics can be seen in the upper right plots in the figures. In the time domain the Walsh functions are square waves. This corresponds to a sampled sinc function in the frequency domain. The frequency response of our crosstalk portion of the signal is being convolved with sinc functions twice ( two different periods ).  I believe this is causing the harmonics.

I'm waiting for my copy of SETI 2020 to arrive.  I hope the book details exactly how the Walsh funcation are used.  In mean time, if anybody with more insight to check my assumptions, that would be helpful.

begin octave code:
-----------------------------------------------

%%%% 1024 samples signal
N= 2^10; n=0:(N-1); n=n(:);

%%%% create 3 square wave walsh functions
w1=(-1).^(mod(floor(n/2^2),2)); w2=(-1).^(mod(floor(n/2^3),2)); w3=(-1).^(mod(floor(n/2^4),2));
W= [ w1 w2 w3 ];

%%%% sanity check that we create walsh functions correctly
assert( (3*N)==sum(sum( (W')*W )) ); %'))));

%%%% create noise-free signl
tau= [ 0 12 173 ];  % propagation offsets;
phi= pi / 5; idxs(:,1)= n + tau(1); idxs(:,2)= n + tau(2); idxs(:,3)= n + tau(3);
sig= cos( phi * idxs );
A=0.2; CT= [ 1.0 A A; A 1.0 A; A A 1.0; ]; %% cross talk matrix

%%%% underchipped
undr= W .* sig;

%%%% overchipped
M=32;
for k=0:(N-1) %;
for m=1:M %;
over( (M*k)+m, : )= sig(k+1,:).*W(m,:);
endfor;
endfor;

%%%% postprocessing
rcv1= undr * CT;
pst1= rcv1 .* W;

rcv2= over * CT;
for k=0:(N-1) %;
pst2(k+1,:)= (1/M) * sum( rcv2( (M*k)+(1:M), : ) .* W(1:M,:) );
endfor;

err1= sum( (pst1 - sig).^2 )/N; err2= sum( (pst2 - sig).^2 )/N;

%%%% display results
close all;
for k=1:3  %;
figure(k);
subplot(2,2,1)
plot( abs( fft( sig(:,k), 2^12 )));
title(sprintf('FFT Mag. Received Sig %i', k));
subplot(2,2,2)
plot( abs( fft( W(:,k), 2^12 )));
title(sprintf('FFT Mag. Walsh Func. %i', k));
subplot(2,2,3)
plot( abs( fft( pst1(:,k), 2^12 )));
title(sprintf('FFT Mag. (Underchipped) Sig %i: Ebar=%e', k,err1(k)));
subplot(2,2,4)
plot( abs( fft( pst2(:,k), 2^12 )));
title(sprintf('FFT Mag. (Overchipped) Sig %i: Ebar=%e', k,err2(k)));
endfor;

-----------------------------------------------
end code

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 732
I don't remember any mention

I don't remember any mention of Washing in the book SETI 2020.  It is not listed in the Index and after doing a quick scan I couldn't find any hint of it.  If you happen to find it then please let me know.

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 732
It looks like you are working

It looks like you are working with complex samples.  After the mixer at the ATA you'd think the path would be quadrature ... but I believe the optical to ADC path where the Walshing is done/undone that the signals are real and not quadrature.  The beamformers are directly after the ADC and they take in real samples.  I read this somewhere on this forum a long time ago and unfortunately I don't have a link.  I also could be wrong, so maybe a SETI Institute staff member could clear this up.

I see in a later post that your octave code is working with real samples so what I said above is for information purposes only.

maxs-pooper-scooper
Offline
Joined: 2010-07-28
Posts: 58
yeah after thinking about it more

I guessed that the mixing works on real signals.