Why XOR (mod 2 addition) and multiplication are anologous?

[dexterdev]

Hi PF,
I have a serious doubt. In spread spectrum modulation etc we multiply the message signal with PN sequence , so as to spread it in frequency domain, good and I am OK with that. But when explanation comes multiplication becomes XOR ing in most books and articles.

How XOR can be replaced at multiplier?

-Devanand T

 

[NascentOxygen]

How XOR can be replaced at multiplier?

Try exclusive NOR, or ^¬(XOR) as being equivalent to multiplication.

 

[the_emi_guy]

This is a little counterintuitive. Here is the deal:

XOR mathematically is addition without carry.

0 xor 0= 0+0=0
1 xor 0= 1+0=1
0 xor 1= 0+1=1
1 xor 1= 1+1=0 (throwing away carry)

Addition is a linear operation only when carry is preserved. Throwing away of the carry
turns xor into a non-linear function. As a non-linear function, it has application in the signal processing function of "mixing". Multipliers are also used for mixing.

Consider two sine waves that identical except 90 degrees out of phase being multiplied. The result is a sine wave at twice the frequency. The non-linear operation of multiplication has caused a frequency doubling.

Now consider what the XOR does to two square waves 90 degrees out of phase. Draw this out for yourself, but you will find that it is a square wave at twice the freq.

The way to reconcile this with the mathematical function of multiplication is to create symmetry by allowing logic 0 to be -1, logic 1 to be +1.

square wave: -1, 1, 1,-1,-1, 1, 1
quadrature square wave: -1,-1, 1, 1,-1,-1, 1
product: 1,-1, 1,-1, 1,-1, 1

Note the product is a square wave at twice the frequency.
(adding them, and keeping the carry, produces a waveform that is not a square wave, but has frequency equal to the input square waves, i.e. no frequency translation)

 

[dexterdev]

Try exclusive NOR, or ¬(XOR) as being equivalent to multiplication.

0 multiplied by 0 = 0
0 multiplied by 1 = 0
1 multiplied by 0 = 0
1 multiplied by 1 = 1

This is what I thought binary multiplication would be...but it turns out to be AND operation.

but

0 XNOR 0 = 1
0 XNOR 1 = 0
1 XNOR 0 = 0
1 XNOR 1 = 1
and XOR is complement of XNOR , both don't seem to follow multiplication.

the_emi_guy's explanation is ok, but I have not attained peace in this matter.Please see the attached image.

 

[NascentOxygen]

and XOR is complement of XNOR , both don't seem to follow multiplication.

Task 1: Here are two ANALOGUE signals. On the axis provided, sketch what you'd expect if you were to multiply these together.

Task 2: Sketch these same waveshapes, but this time regard them as logic signals, each jumping between logic 0 and logic 1. Sketch the XOR of these.


Task 3: Compare.

 

[the_emi_guy]

0 multiplied by 0 = 0
0 multiplied by 1 = 0
1 multiplied by 0 = 0
1 multiplied by 1 = 1

This is what I thought binary multiplication would be...

XOR is *not* multiplication. It is addition with carry truncated.

XOR can be considered analogous to multiplication only if the inputs are treated as symmetrical with no DC bias for the multiplication.

DC biased
011001100 squarewave
001100110 quadrature squarewave
001000100 product (note this looks like product of biased sinewaves, see attached image)

Unbiased
-1, 1, 1,-1,-1, 1, 1,-1,-1 squarewave
-1,-1, 1, 1,-1,-1, 1, 1, quadrature squarewave
1, -1, 1,-1, 1,-1, 1,-1 product (note this looks like product of unbiased sinewaves, 2x frequency, see image)

DC biased
011001100 squarewave
001100110 quadrature squarewave
010101010 XOR (this looks like product of unbiased squarewave/sinewave, 2x frequency)

 

[dexterdev]

Try exclusive NOR, or ^¬(XOR) as being equivalent to multiplication.

Task 1: Here are two ANALOGUE signals. On the axis provided, sketch what you'd expect if you were to multiply these together.

Task 2: Sketch these same waveshapes, but this time regard them as logic signals, each jumping between logic 0 and logic 1. Sketch the XOR of these.


Task 3: Compare.

Thanks for the effort...I got inverted waveform with XOR no matter XNOR will help. Thanks a lot... Sir

 

[dexterdev]

XOR is *not* multiplication. It is addition with carry truncated.

XOR can be considered analogous to multiplication only if the inputs are treated as symmetrical with no DC bias for the multiplication.

DC biased
011001100 squarewave
001100110 quadrature squarewave
001000100 product (note this looks like product of biased sinewaves, see attached image)

Unbiased
-1, 1, 1,-1,-1, 1, 1,-1,-1 squarewave
-1,-1, 1, 1,-1,-1, 1, 1, quadrature squarewave
1, -1, 1,-1, 1,-1, 1,-1 product (note this looks like product of unbiased sinewaves, 2x frequency, see image)

DC biased
011001100 squarewave
001100110 quadrature squarewave
010101010 XOR (this looks like product of unbiased squarewave/sinewave, 2x frequency)

Thankyou sir.

 

[lamvo428]

Gentlemen, I would like to continue this discussion if possible. I like the_emi_guys explanation for a simple digital signals, but let's take it a step further.

Suppose we have this situation: 2 unbiased sine wave with amplitude -10 to 10V and different frequencies, fa and fb. We sample both sine wave with a 8 bit ADC and of course we satisfy the nyquist rate. If we XOR sine_a with sine_b, do we get fa +/- fb?

In other words, if we take the_emi_guys explanation and apply it to two real digitized sinusoid, what would we get? Why?

Let me know your thoughts. Thanks!

 

[NascentOxygen]

Suppose we have this situation: 2 unbiased sine wave with amplitude -10 to 10V and different frequencies, fa and fb. We sample both sine wave with a 8 bit ADC and of course we satisfy the nyquist rate. If we XOR sine_a with sine_b, do we get fa +/- fb?

Hi lamvo428,

I'm having difficulty with the concept of XORing 8 bit integers, i.e., digitised values.

 

[lamvo428]

Hi NascentOxygen,

Thanks for asking that question. I see that my post is not clear. When I say sine_a XOR sine_b, what I mean is:

sine_a_bit(7) XOR sine_b_bit(7) = sine_res(7)
sine_a_bit(6) XOR sine_b_bit(6) = sine_res(6)
sine_a_bit(5) XOR sine_b_bit(5) = sine_res(5)
.
.
.
sine_a_bit(0) XOR sine_b_bit(0) = sine_res(0)

What is the result of sine_res?

Does it follow the solution of multiplying two sinusoids like the output of a mixer? If we do, how and why?

I hope that clear. Let me know.

 

[NascentOxygen]

I see... It's not something I'd have thought to do, bitwise XOR.

My suggestion is that you should try it with some sample values you concoct yourself, to find out.