Binary, Octal and Hexadecimal Numbers

Consider a decimal number with digits a b c. We can write abc as

Similarly, in the binary system a number with digits a b c can be written as



Each digit is known as a bit and can take on only two values: 0 or 1. The left most bit is the highest-order bit and represents the most significant bit (MSB), while the lowest-order bit is the least significant bit (LSB).
Conversion from binary to decimal can be done using a set of rules, but it is much easier to use a calculator or tables (table 7.1).

  
Table 7.1:  Decimal, binary, hexadecimal and octal equivalents.

The eight octal numbers are represented with the symbols  , while the 16 hexadecimal numbers use  .
In the octal system a number with digits a b c can be written as



while one in the hexadecimal system is written as



A binary number is converted to octal by grouping the bits in groups of three, and converted to hexadecimal by grouping the bits in groups of four. Octal to hexadecimal conversion, or visa versa, is most easily performed by first converting to binary.

Example: Convert the binary number 1001 1110 to hexadecimal and to decimal.

Example: Convert the octal number  to hexadecimal.

Example: Convert the number 146 to binary by repeated subtraction of the largest power of 2 contained in the remaining number.

Example: Devise a method similar to that used in the previous problem and convert 785 to hexadecimal by subtracting powers of 16.

TRUTH TABLE

A truth table is a breakdown of a logic function by listing all possible values the function can attain. Such a table typically contains several rows and columns, with the top row representing the logical variables and combinations, in increasing complexity leading up to the final function.

In a logic function, there are three basic operations: NOT (also called inversion or negation and symbolized -), OR (also called disjunction or addition and symbolized +), and AND (also called conjunction or multiplication and symbolized *). The values of the functions are normally assigned as logic 0 = false and logic 1 = true. Thus, the following rules apply:

If A = 0, then -A = 1
If A = 1, then -A = 0
A+B = 1 except when A = 0 and B = 0
A+B = 0 if A = 0 and B = 0
A*B = 0 except when A = 1 and B = 1
A*B = 1 if A = 1 and B = 1

HOW TO MAKE TRUTH TABLE?

Truth tables provide a useful method of assessing the validity or invalidity of the form any argument. We can use the table to determine whether the entire form of the argument is true or false, based on one very simple rule: Any argument that allows for a set of all true premises with a false conclusion must be invalid. This elegant process provides us with a means of providing a logical, deductive proof that an argument form is valid. In addition, this process allows us to identify which forms are invalid, allowing for refutations by logical analogy: a process wherein one may use a ridiculous version of an opponents argument, using the precise form of his argument, to show where it the argument form reaches illogical conclusions.

To use a truth table to test an argument:

1. Make a column for each of the components used in the argument. There must be a line for each possible combination of truth values for these components. Each additional component will double the number of lines needed. A single component will need two lines. Thus, if there are n components there must be 2ⁿ lines. By using a set pattern we can be sure to have included all the possible combinations and that no combination occurs more than once. The set pattern is to alternate true with false in the first column, in the second column (if needed) alternate 2 trues with 2 falses, in the third column (if needed) alternate 4 trues with four falses, and so on (doubling the number kept together for alternation with each column one adds) until the final component's column consists of the top half true and the bottom half false.

2. Add a column for each premise and for the conclusion. This may require additional columns to enable the calculation of complex premises or conclusions. Calculate the truth values for each line in the premises' and conclusion's columns.

3. Identify the lines where the conclusion is false and check those lines to see whether there is at least one false premise on that line.

4. If there is at least one false premise on every line where the conclusion is false, the argument is valid. Otherwise, you have demonstrated the possibility of all the premises being true at the same time as the conclusion is false, which is the mark of an invalid argument.

K-MAP METHOD (KARNAUGH MAP)

The Karnaugh map (K-map for short), Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions. The Karnaugh map reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability, permitting the rapid identification and elimination of potential race hazards. 

In a Karnaugh map the boolean variables are transferred (generally from a truth table) and ordered according to the principles ofGray code in which only one variable changes in between squares. Once the table is generated and the output possibilities are transcribed, the data is arranged into the largest possible groups containing 2ⁿ cells (n=0,1,2,3...) and the minterm is generated through the axiom laws of boolean algebra.

Size of map

The size of the Karnaugh map with n Boolean variables is determined by 2ⁿ. The size of the group within a Karnaugh map with n Boolean variables and k number of terms in the resulting Boolean expression is determined by 2^nk. Common sized maps are of 2 variables which is a 2×2 map, 3 variables which is a 2×4 map, and 4 variables which is a 4×4 map.

2-variable k-map

3-variable k-map

4-variable k-map

Rules of Simplification

---

The Karnaugh map uses the following rules for the simplification of expressions by grouping together adjacent cells containing ones

• Groups may not include any cell containing a zero 
• Groups may be horizontal or vertical, but not diagonal. 
• Groups must contain 1, 2, 4, 8, or in general 2ⁿ cells.
  That is if n = 1, a group will contain two 1's since 2¹ = 2.
  If n = 2, a group will contain four 1's since 2² = 4. 
• Each group should be as large as possible. 
• Each cell containing a one must be in at least one group. 
• Groups may overlap. 
• Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell. 

HALF AND FULL ADDERS

From basic gates, we will develop a full adder circuit that adds two binary numbers. Consider adding two 2-bit binary numbers  and  .  , where  is the carry bit. The truth table for all combinations of and  is shown in table 7.5.

  
Table 7.5:  The binary addition of two 2-bit numbers. The  column.

From the truth table



The mechanization of these two equation is shown in figure 7.7.

  
Figure 7.7:  A mechanization of the half adder using an EOR and an AND gate.

This circuit is known as the half adder. It can not handle the addition of any two arbitrary numbers because it does not allow the input of a carry bit from the addition of two previous digits. A circuit that can handle these three inputs can perform the addition of any two binary numbers.
The truth table for three input variables is shown in figure 7.8.

  
Figure 7.8:  The binary addition of two 2-bit numbers. The  column.

From the truth table



This is known as majority logic. And a majority detector is shown in figure 7.9

  
Figure 7.9:  A mechanization of the majority detector.




The following device (figure 7.10) is known as a full adder and is able to add three single bits of information and return the sum bit and a carry-out bit.

  
Figure 7.10:  The full adder mechanization.

The circuit shown in figure 7.11 is able to add any two numbers of any size. The inputs are  and  , and the output is  .

  
Figure 7.11:  A circuit capable of adding two 3-bit numbers.

Example: If the input to the circuit in figure 7.12 is written as a number ABCD, write the nine numbers that will yield a true Q.  
Figure 7.12:  A typical logic function.


  
Table 7.6: The truth table for the typical logic function example.

ABCD=(2,3,6,7,11,12,13,14,15) gives Q true.

Example: Using the 2's complement convention, the 3-bit number ABC can represent the numbers from -3 to 3 as shown in table 7.7 (ignore -4). Assuming that A, B, C and  are available as inputs, the goal is to devise a circuit that will yield a 2-bit output EF that is the absolute value of the ABC number. You have available only two- and three-input AND and OR gates.

1. Fill a truth table with the ABC and EF bits.The truth table is shown in table 7.7.
   
     
   Table 7.7:  Truth table with for the ABC and EF bits.
2. Write a Boolean algebra expression for E and for F.
   
   
   
   
3. Mechanize these expressions.The mechanized expressions are shown in figure 7.13.
   
     
   Figure 7.13:  Mechanization for the ABC and EF bits.

Example: Suppose that the 2-bit binary number AB must be transmitted between devices in a noisy environment. To reduce undetected errors introduced by the transmission, an extra bit P is often included to add redundancy to the information. Assume that P is set true or false as needed to make an odd number of true bits in the resulting 3-bit number ABP. When the number is received, logic circuits are required to generate an error signal E whenever the odd number of bits condition is not met.

1. Develop a truth table of E in terms of A, B and P.The truth table is shown in table 7.8.
   
     
   Table 7.8:  Truth table for E in terms of A, B and P.
2. Write a Boolean expression for E as determined directly from the truth table.
   
3. Using De Morgan's theorem twice, reduce this expression to one EOR and one NEOR operation. (This is very similar to the half-adder problem.)
   
   
   
     
   Figure 7.14: Mechanization for E.