Digital Electronics: Supplement to Engs 31 / CoSc 56

The simplest digital processor simply takes in one or more input bits and maps them to an output bit. For example, take a two-bit number \(x = (x_1, x_0)\) and assert the output, \(y\text{,}\) if \(x \lt 2\text{.}\) Using mathematical notation, we can express the input-output relationship as a function, \(y=f(x)\text{,}\) and write down what the function does in a table (Figure 1.3.1). Such a tabular representation of the mapping from input bits to output bits is called a truth table.

Truth tables can have any number of inputs and outputs. Here is one with a two-bit input \(n = (n_1, n_0)\) and a four-bit output \(y = (y_3, y_2, y_1, y_0)\text{,}\) Figure 1.3.2.

The function represented by this table, \(y = f(n)\text{,}\) asserts the \(n^{th}\) output bit, \(y_n\text{.}\) It is called a one-hot decoder (because only one output is asserted, or “hot”, at a time).

With this brief introduction, watch the beginning (up to time 2:21) of the following video on truth tables.

The small digital system called a multiplexer has two one-bit data inputs, \((A, B)\text{,}\) a control bit \(S\) (“select”), and a one-bit output, \(y\text{.}\) The control bit \(S\) selects whether the output is \(y=A\) or \(y=B\text{.}\) The function of the multiplexer is described by the following if-then-else:

if S=='0' 
    then y=A;
    else y=B;
end if;

In general, a truth table with \(N\) inputs has \(2^N\) rows. Exhaustively tabulating every row can rapidly become unwieldy (4, 8, 16, 32, 64, ...) as the number of inputs increases (2, 3, 4, 5, 6, ...). Here is one way that truth tables can occasionally be compressed. Look again at the third and fourth rows of the multiplexer truth table:

The output will be TRUE if \(S\) is FALSE and \(A\) is TRUE, whether \(B\) is TRUE or FALSE. We don’t care what the value of \(B\) is, we only need to look at \(S\) and \(A\text{.}\) We can merge the two rows into one, like this, marking \(B\)’s "don’t care" status with a dash (—):

This move reduces the number of rows from eight to seven. Additional rows can be merged using “don’t care” entries, compressing the truth table to four rows.

        if x3==1 then 
            n=3; v=1;
        elsif x2==1 then 
            n=2; v=1;
        elsif x1==1 then 
            n=1; v=1;
        elsif x0==1 then 
            n=0; v=1;
        else
            n=0; v=0;
        end if;