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

AI Thread Summary
The discussion explores the analogy between XOR (mod 2 addition) and multiplication, particularly in the context of signal processing. XOR is described as addition without carry, which makes it a non-linear function, unlike traditional multiplication. The conversation highlights that while XOR can mimic some aspects of multiplication under specific conditions, such as treating inputs symmetrically without DC bias, it fundamentally operates differently. Participants also discuss the implications of XORing digitized sine waves and question whether this operation would yield results similar to multiplying those waves. Ultimately, the conversation emphasizes the complexities and nuances in understanding the relationship between XOR and multiplication in signal processing.
dexterdev
Messages
194
Reaction score
1
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? :confused:

-Devanand T
 
Engineering news on Phys.org
dexterdev said:
How XOR can be replaced at multiplier? :confused:

Try exclusive NOR, or ¬(XOR) as being equivalent to multiplication.
 
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)
 
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.
 

Attachments

  • mul.jpg
    mul.jpg
    11.7 KB · Views: 1,397
dexterdev said:
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.


attachment.php?attachmentid=56260.png




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. :smile:
 

Attachments

  • multiply.png
    multiply.png
    811 bytes · Views: 3,548
dexterdev said:
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)
 

Attachments

  • xor.jpg
    xor.jpg
    45 KB · Views: 1,151
NascentOxygen said:
Try exclusive NOR, or ¬(XOR) as being equivalent to multiplication.

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


attachment.php?attachmentid=56260.png




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. :smile:

Thanks for the effort...I got inverted waveform with XOR no matter XNOR will help. Thanks a lot... Sir
 
the_emi_guy said:
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.
 
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!
 
  • #10
lamvo428 said:
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.
 
Last edited by a moderator:
  • #11
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.
 
  • #12
I see... :smile: 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.
 
Back
Top