Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 1, 2013 #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
     
  2. jcsd
  3. Mar 1, 2013 #2

    NascentOxygen

    User Avatar

    Staff: Mentor

    Try exclusive NOR, or ¬(XOR) as being equivalent to multiplication.
     
  4. Mar 1, 2013 #3
    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)
     
  5. Mar 1, 2013 #4
    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 donot 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.
     

    Attached Files:

    • mul.jpg
      mul.jpg
      File size:
      15.7 KB
      Views:
      302
  6. Mar 1, 2013 #5

    NascentOxygen

    User Avatar

    Staff: Mentor


    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:
     

    Attached Files:

  7. Mar 1, 2013 #6
    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)
     

    Attached Files:

    • xor.jpg
      xor.jpg
      File size:
      45 KB
      Views:
      306
  8. Mar 1, 2013 #7
    Thanks for the effort............I got inverted waveform with XOR no matter XNOR will help. Thanks a lot........... Sir
     
  9. Mar 1, 2013 #8
    Thankyou sir.
     
  10. Aug 15, 2013 #9
    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!
     
  11. Aug 15, 2013 #10

    NascentOxygen

    User Avatar

    Staff: Mentor

    Hi lamvo428, [Broken]

    I'm having difficulty with the concept of XORing 8 bit integers, i.e., digitised values.
     
    Last edited by a moderator: May 6, 2017
  12. Aug 15, 2013 #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.
     
  13. Aug 15, 2013 #12

    NascentOxygen

    User Avatar

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Why XOR (mod 2 addition) and multiplication are anologous?
  1. XOR Gates (Replies: 2)

  2. Is this an xor gate? (Replies: 6)

Loading...