Appendix E / E.2

E.2 LOGIC OPERATIONS ON BINARY NUMBERS

Logic operations form the mathematical basis of all digital systems. Every computer, digital circuit, and communications encoder ultimately depends on a set of simple binary operations that manipulate signals representing true or false, or equivalently, 1 and 0. These operations are not only used in computation but also underlie the encoding, modulation, and error-detection techniques discussed throughout this book.

A logic gate implements a Boolean function—that is, a relationship between one or more input variables and a single binary output. The fundamental logic operations are AND, OR, and exclusive-OR (XOR), from which all other logical relationships (NOT, NAND, NOR, XNOR, etc.) can be derived. In digital systems, these operations act bitwise on binary data streams. For example, the binary addition rules used in Galois Fields, parity generation, and linear block coding are directly equivalent to logical XOR operations. Table E.2 Shows the truth tables for the three main operators.

Table E.2. Logic operations.

The AND Operation

The output of the AND operation (denoted by the symbol ‘.’) is true only when both of its inputs are true. For example, 1.0 is 0, 1.1 is 1.

In Boolean algebra, this is written as Y = A·B or simply Y = AB.

The OR Operation

The output of the OR operation (denoted by the symbol ‘+’) is true when either of its inputs is true. For example, 0+0 is 0, while 0+1 is 1.

In Boolean notation, Y = A + B. Although the plus sign resembles arithmetic addition, it should not be confused with ordinary algebraic addition—there is no carry between bits.

The XOR Operation

The output of the XOR operation in Table E.2 (denoted by the symbol ‘⊕’) is true when the two inputs have different values, that is, one input is true and the other input is false. For example, 1⊕0 is 1, while 1⊕1 is 0.

The Boolean expression is Y = A ⊕ B. In ordinary algebraic form over GF(2), XOR corresponds to addition modulo 2, where 1 + 1 = 0. This relationship makes XOR the fundamental operation for binary addition, parity checking, and error-control coding.

For example, in parity generation, the parity bit is the XOR of all bits in the data word. In linear block codes, codewords are produced by XORing selected message bits according to the generator matrix. In checksum or CRC computation, XOR is used repeatedly to combine partial results, as addition modulo 2 ensures no carry propagation.

Combined and Derived Logic

More complex logic expressions can be formed by combining these primitive operations. For example, Y = (A·B) + (C ⊕ D) means that Y will be true if A AND B are both true, or if C and D differ.

Derived operations include NOT (inversion), NAND (the complement of AND), NOR (the complement of OR), and XNOR (the complement of XOR, true when inputs are equal). All logic functions can be constructed from combinations of NAND or NOR gates, a property known as functional completeness.

Modulo

The modulo operation (from the Latin modulus, meaning “measure” or “small measure”) determines the remainder after division of one number by another. When we say a number a is taken modulo n—written as a mod n—we mean that only the remainder of the division of a by n is retained. For example, 17 mod 5 = 2, because 17 divided by 5 leaves a remainder of 2.

Two numbers are said to be congruent modulo n if they leave the same remainder when divided by n. This is written as a ≡ b (mod n) and means that (a–b) is an exact multiple of n.

Modulo arithmetic is therefore arithmetic “wrapped around” a fixed modulus n—see Appendix F for a more detailed discussion of finite fields, also known as Galois fields.. In digital systems, the most common case is mod 2 arithmetic, where results are restricted to 0 or 1—forming the basis of binary addition and logic operations such as XOR.