next up previous contents
Next: Complementation Up: Register-Transfer Logic Previous: Concatenation   Contents


Logical Operations

In this chapter, we define and analyze the four basic logical operations: the unary “not”, or complement, and the binary “and”, “inclusive or” and “exclusive or”. These are commonly known as bit-wise operations, as each one may be computed by performing a certain computation on each bit of its argument (in the unary case) or each pair of corresponding bits of its arguments (for binary operations). For example, the bit vector

$\displaystyle z[n$-$\displaystyle 1:0] = x[n$-$\displaystyle 1:0] \;\verb!&!\; y[n$-$\displaystyle 1:0],$

generated as the logical “and” of $ n$ -bit vectors $ x$ and $ y$ , may be specified in a bit-wise manner: for $ i=1,\ldots,n-1$ , $ z[i] = 1$ if and only if $ x[i] = y[i] = 1$ .

In the context of our formalization, however, the logical operations are more naturally defined as arithmetic functions: the complement is constructed as an arithmetic difference and the binary operations are defined by recursive formulas, which facilitate inductive proofs of their relevant properties. Among these are the bit-wise characterizations, as represented by Lemmas 3.1.8 and 3.2.10.


Subsections
David Russinoff 2007-01-02