1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Shannon entropy of logic gate output.

  1. Jan 1, 2016 #1
    1. The problem statement, all variables and given/known data
    A particular logic gate takes two binary inputs [itex] A[/itex] and [itex] B [/itex] and has two binary outputs [itex]A'[/itex] and [itex]B'[/itex]. I won't reproduce the truth table. Suffice to say every combination of [itex] A[/itex] and [itex]B[/itex] is given. The output is produced by [itex] A' = \text{NOT} \ A[/itex] and [itex] B' = \text{NOT} \ B [/itex]. The input has Shannon entropy of 2 bits. Show that the output has a Shannon entropy of 2 bits.

    A second logic has output produced by [itex] A' = A \ \text{OR} \ B[/itex] and [itex] B' = A \ \text{AND} \ B [/itex]. Show that the output now has an entropy of [itex] \frac32 [/itex] bits.

    2. Relevant equations
    [tex] S = - \sum_{i} k P_i \log P_i [/tex]

    3. The attempt at a solution
    From what I (don't) understand, [itex] P = \frac12 [/itex] in the first example for [itex] A, B, A',B' [/itex] so the total number of bits is the same for both input and output. For the second example, I would say [itex] P_{A'} = \frac34 [/itex] and [itex] P_{B'} = \frac14 [/itex], but that does not produce the correct number of bits.
  2. jcsd
  3. Jan 1, 2016 #2
    It helps greatly if you draw up a truth table to represent the inputs and outcomes. The [itex]P_{i}[/itex]'s that appear in the formula for Shannon entropy represent the probabilities of the various outcomes, so expressions like [itex]P_{A'}[/itex] make no sense at all.
    As a quick example to illustrate the use of the Shannon entropy formula, consider the flipping of a fair coin. There are two possible outcomes - heads or tails, each which occur with 50% probability. The Shannon entropy is then [itex]S = - \frac{1}{2} \log_{2} \frac{1}{2} - \frac{1}{2} \log_{2} \frac{1}{2} = 1 [/itex].
  4. Jan 1, 2016 #3
    Thanks. There is a truth table, so do you mean I should add one here? By [/itex] P_{A'} [/itex] I meant the probability of [itex] A' [/itex] being 1 but I agree this is confusing. I'm still not sure about the answer though. It works out fine for the first example as it is [itex] S = -4 \times \frac12 \log_2 \frac12 = 2 [/itex] but for the second example I think it is [tex]
    S = - \frac32 \log_2 \frac34 - \frac12 \log_2 \frac14. [/tex]
  5. Jan 1, 2016 #4
    Take note that there are three outcomes for the second example. Unlike the first example, the 'events' A' and B' are not independent.
    Your result doesn't agree with mine, so perhaps you might want to list down the truth table for this example?
  6. Jan 1, 2016 #5
    Oh I see where I went wrong. I'm confusing what the 'events' are. I have the correct answer now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted