Shannon entropy of logic gate output.

[Dazed&Confused]

Homework Statement

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.

Homework Equations

[tex] S = - \sum_{i} k P_i \log P_i [/tex]

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.

 

[Fightfish]

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].

 

[Dazed&Confused]

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]

 

[Fightfish]

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?

 

[Dazed&Confused]

Oh I see where I went wrong. I'm confusing what the 'events' are. I have the correct answer now.