JtUIIHW

Bldg.

JAN B 1967

^ecUnical vtote 92©. 334

AN INTRODUCTION TO SAMPLED DATA

AND SWITCHING LOGIC

THOMAS L. DAVIS

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
THE NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards is a principal focal point in the Federal Government for assuring

maximum application of the physical and engineering sciences to the advancement of technology in industry and commerce. Its responsibilities include development and maintenance of the national stand- ards of measurement, and the provisions of means for making measurements consistent with those standards; determination of physical constants and properties of materials; development of methods

for testing materials, mechanisms, and structures, and making such tests as may be necessary, particularly for government agencies; cooperation in the establishment of standard practices for incorporation in codes and specifications; advisory service to government agencies on scientific and technical problems; invention and development of devices to serve special needs of the Government; assistance

to industry, business, and consumers in the development and acceptance of commercial standards and

simplified trade practice recommendations; administration of programs in cooperation with United

States business groups and standards organizations for the development of international standards of

practice; and maintenance of a clearinghouse for the collection and dissemination of scientific, technical, and engineering information. The scope of the Bureau's activities is suggested in the following

listing of its four Institutes and their organizational units. Institute for Basic Standards. Electricity. Metrology. Heat. Radiation Physics. Mechanics. Applied Mathematics. Atomic Physics. Physical Chemistry. Laboratory Astrophysics.* Radio Standards Laboratory: Radio Standards Physics; Radio Standards Engineering.** Office of Standard Ref- erence Data. Institute for Materials Research. Analytical Chemistry. Polymers. Metallurgy. Inorganic Materials. Reactor Radiations. Cryogenics.** Office of Standard Reference Materials. Central Radio Propagation Laboratory.** Ionosphere Research and Propagation. Troposphere

and Space Telecommunications. Radio Systems. Upper Atmosphere and Space Physics.

Institute for Applied Technology. Textiles and Apparel Technology Center. Building Research.

Industrial Equipment. Information Technology. Performance Test Development. Instrumentation.

Transport Systems. Office of Technical Services. Office of Weights and Measures. Office of Engineering Standards. Office of Industrial Services.

* NBS Group, Joint Institute for Laboratory Astrophysics at the University of Colorado. ** Located at Boulder, Colorado.
NATIONAL BUREAU OF STANDARDS

*£echnical ^ete 334

ISSUED April 1, 1966

AN INTRODUCTION TO SAMPLED DATA AND

SWITCHING LOGIC

Thomas L. Davis

Institute for Telecommunication Sciences and Aeronomy*

Environmental Science Services Administration

Boulder, Colorado

NBS Technical Notes are designed to supplement the Bureau's regular publications program. They provide a means for making available scientific data that are of transient or limited interest. Technical Notes may be

listed or referred to in the open literature.

''Formerly the Central Radio Propagation Laboratory of the National Bureau of Standards; CRPL was

transferred to ESSA in October 1965, but will temporarily use various NBS publication series pending

inauguration of their ESSA counterparts.

For sale by the Superintendent of Documents, U.S. Government Printing Office Washington D.C. 20402

Price: 40$

CONTENTS

Page

1. INTRODUCTION 1

2. FOUNDATIONS OF DATA ANALYSIS 2

2.1. Fourier Series and Integral Expression 2

a. Periodic Functions 2

b. Aperiodic Functions 4

c. Random Functions 6

2. 2. Auto-correlation and Power Spectra 6

a. Periodic Functions 6

b. Aperiodic Functions 7

c. Random Functions 9

2.3. Crosscorrelation and Convolution 12

a. Crosscorrelation 13

b. Convolution 15

2.4. Remarks 17

3. SAMPLED DATA THEORY 18

3.1. Introduction 18

3.2. Data Sampling 19

3.3. The Sampling Theorem 22

3.4. Recovery of Sampled Data 23

3.5. Aliasing 24

a. Description of Aliasing 24

b. Errors Due to Aliasing 24

4. BINARY NUMBERS 26

4.1. Representations of Decimal and Octal Numbers ... 26

4. 2. Binary Decision Elements 29

iii
5. SWITCHING LOGIC I 31

5.1. Boolean Algebra 31

5.2. NOR and NAND Logic 34

6. SWITCHING LOGIC II 35

7. SWITCHING LOGIC III 42

8. CONCLUSIONS 47

9. REFERENCES 48

10. APPENDICES 50

10.1. The Ideal Low-Pass Filter 50

10.2. Proof of Sampling Theorem 51

iv
AN INTRODUCTION TO SAMPLED DATA AND SWITCHING LOGIC

Thomas L. Davis

This note presents introductory material on the

subjects of Fourier series and integral representations

of data, operations on data (i. e. correlation, convolution,

and sampling), Boolean algebra, and combinatorial 3ogic

circuits. The presentation is tutorial and stresses the

operations and their effects rather than mathematical

rigor.

1. INTRODUCTION

This note contains the material for a series of lectures which were

given by the author in November 1962. These lectures were given to

prepare the personnel of the Radio Systems Division and the Central

Radio Propagation Laboratory for the training program on the use

and operation of the Radio Systems Division's analog -to -digital conversion

(ADC) system. The training program for the ADC was to be given by the

contractor supplying the equipment.

The notes have been augmented to some extent to put them in a form

more suitable for publication. They form a source of material for

members of the CRPL technical staff and others who are not required

to design digital systems, but may wish to know something about digital

and sampled data techniques.

The report covers two main subjects. The first includes Fourier

series and integral expressions of signals, correlations, description

of the sampling process, the sampling theorem, and some precautions

which must be exercised when using sampled data. The second major

Key words; switching logic, sampled data, Fourier series, Fourier

integrals, correlation, computers
subject includes Boolean algebra, combinational circuits, and minimization methods.

2. FOUNDATIONS OF DATA ANALYSIS

We are generally concerned with three types of functions. These

are periodic or recurrent signals, aperiodic or transient signals, and

random signals. The periodic and aperiodic functions may be completely

described for all time, both past and present, in terms of sin x, cos x,

e , and other simple mathematical expressions. Random functions do

not share this predictability for future time. They are completely

determined for all past time, but their future nature can only be

predicted within certain limits. We wish to study these types of functions

and some fundamental operations with them so that we may see the

operations which may be performed by a digital computer using the

sampled data and see some of the shortcomings and precautions of

data sampling techniques.

2.1. Fourier Series and Integral Expressions

a. Periodic Functions

A recurrent function, f(t), with period Ti ,may be represented by

the Fourier series expression,

00

f(t) = —£- + / (a cos nuux t+b sin nU>i t), (2-1)

2 l_j n n n=l

i_ 2TT where U)x = , angular frequency, (2-2)

li

II

2 { 2 a = —- \ f(t) cos nlUx

t dt, n = 0, 1 , 2, 3, . . . , n J-i J

Ti (2-3)

2

2-
2

b = — \ f(t) sin nuUi t dt,

n Ti J

2

There also exists an exponential form,

n = 1, 2, 3, ... (2-4)

f (t) = > F(n) exp (jnnjj t) n = -co

(2-5)

where F'"' " 2

< a

n

" JV n = 0, ±1, ±2, (2-6)

and the inverse of (2-5) is

F(n) = - \ f(t) exp (-jnu)x t) dt,

" 2

n = 0, ±1, ±2,

(2-7)

Equations (2-5) and (2-7) are Fourier Transforms of each other and

are known as a Fourier Transform Pair (FTP). F(n) may also be

expressed in complex form:

F(n) = j Ja3^ + b

s exp

c, \\ n n

b

-i / in

j ran

x

f - —

n

(2-8)

where |F(n)| = — I a

3 + b

s = amplitude spectrum, (2-9)

2 \J n n

0(n) = tan-l n

n

= phase spectrum. (2-10)

- 3-
Example: 2-1

Consider the train of rectangular pulses of width b, amplitude

E , and period T,, shown in figure 2- 1 . Then from (2-7) m

F(n) = - \ E^ exp^-jntut ) dt

E b / sin nTT - m f Ti

T, nrr exp ,Fi ,,, |

T,

(2-11)

If b =

and by (2-5)

n

F(n) = m

sin n

TT exp -J n^l I

1

n

f(t) = m

n=

sm n

n

n —

2

exp jnO)! t Ti

(2-12)

(2-13)

E 2E m + cos UM t - —- )- — cos 3UU! t - —- ). TT L \

4 )

3 \

4 J

(2-14)

The spectrum, F(n), is shown in figure 2-2.

b. Aperiodic Functions

We may write a single expression for f(t) from (2-5) and (2-7),

2

f (t) = 2, exPNntwi t )— \ f(a) exp^-jnojia jda . (2-15)

n = 2

-4-
Now let the period of f(t) increase without limit, which is the case for

an aperiodic function, and we see that

Ti —

»

00

U) X —duu

U)i - 0)

so (2-15) becomes

00 00

f(t) = — \ exp(juut) duu \ f(a) exp(-juua) da (2-16)

_ 00 _00 which may be broken down into two expressions:

00

f(t) = \ F (U)) exp(jujt) duu (2-17)

F(U)) = ~ f f(t) exp(-ju)t) dt. (2-18)

_oo Note that in (2-17) , F((J0), is the complex continuous spectrum of f(t)

and that (2-17) and (2-18) are FTP.

We may also write:

F (uu) = P (uu) + jQ(iu) (2-19)

|F(0))| = JP

3 ^) + Q

2

(uu) (2-20)

9(ou) = tan-1 -§^| (2-21) v ' P(uu) v '

Equation (2-20) is the continuous amplitude spectrum of f(t) and

(2-21) is the continuous phase spectrum of f(t).

-5-
Consider a rectangular pulse of width b and amplitude E

(figure 2-3). Then

b

2

F((U) = — \ Em

exp(-jti)t) dt (2-22)

E b , smuu — m / 2

^ V ^b (2-23)

The amplitude spectrum, F(uu), is shown in figure 2-4.

c. Random Functions

One may, under certain conditions, derive a complex spectrum for

random noise voltages. The rigorous basis for such transforms is

found in the theory of Lebesque measure and integration, a subject

far beyond the scope of this paper. A heuristic approach is, given in a paper by Bello [l964]to which the interested reader is referred.

2. 2. Auto -correlation and Power Spectra

a. Periodic Functions

The auto -correlation function for periodic functions is defined as

la

„ 2

011 (T) = t7 Vfi(t) fi(t + T) dt - (2-24)

2

Define the power spectrum,

*n (n) = \F X (n)| 2

(2 _ 25)

where Fi(n) is the spectrum of some periodic function fi(t).

-6-
Then, from (2-24) and (2-25), we may write *

00

li ( T ) = 2, $ ii(n) exp (-jn^T) (2-26)

n=- » and

Ti

1 f 2

$ ii (n) = — \ 0u (T) exp [ -jnii)1 T] dT (2-27)

1 J

Tj

2

Note that0 n (T) is even and that (2-26) and (2-27) are FTP.

Example 2-3:

E

Consider the triangle —— t, figure 2-5.

Then

Em

E

h (t) = -£± t, fx (t + T) = -2: ( t + T ) ( T - [o, b] (2-28)

and

b-T

e3

011 (T) = -q- f _"1 t (t + T) dt

6b%(^- 3b3j + Zt>3 )> T = [°' b ]

• ( 2 -29)

The autocorrelation function is plotted in figure 2-6 for b = -J-i- .

b. Aperiodic Functions

The autocorrelation function for some aperiodic function f (t) is

defined as

0u( T ) = \ fi(t) fi(t + T) dt (2-30)

*For a derivation of this and other equations in this section, refer

to Chapter 2 of Lee [ i960] .

-7-
and the energy density spectrum as

$ n (uu) = 2TT|Fx (UJ)r. (2-31)

We may now write m

0ii (T) = \ *n(uJ) exp (jiwt) duo (2-32)

and

*ii(u>) = -^ V 0ii CO exp (-ju)T) dT. (2-33)

Note that (2-32) and (2-33) are FTP, and, since (t) is an

even function, they become

0a ( T ) = \ *n (UJ) cos OJ T duu (2-34)

and

$ii(«0 = j^ \ 0n(T) COSUJT dTi (2-35)

_ 00 Example 2-4:

Consider the single rectangular pulse of width b, displaced by

t , as shown in figure 2-7.

b-to-T

X1 (T) = \ E

s dt = E

3 (b -| t|), T = [0,b] . (2-36)

J m m

-t,

Figure 2-8 is a plot of ia (T).

We speak of power and energy when discussing periodic and aperiodic

phenomena because of the ways in which they are defined. The energy in a

00 function is given by \ | f(t)| 2 dt which may be infinite for some functions.

8-
i r T/2

, The power is given by — \

| f(t)| a dt which will be finite for well behaved

-T/2

periodic functions. The condition that a function be square integrable

(i. e. the power or energy is finite) is required for the existence of a Fourier transform.

We may also find the energy density spectrum

?u (UJ) =

27F j E^ (b - | T |) cos OJTdT (2-37)

-b

E

2 b

8

, sinuu - N s "T" {2 ' 38)

(JU _ /

2n

Figure 2-9 demonstrates the shape of $n(uu).

Note that the initial displacement of the pulse, t , does not appear in

the autocorrelation function or in the energy density spectrum.

c. Random Functions

We define the basic autocorrelation function for a random function,

fi(t), as T

0ii(T) = ^

^

]

fl (t)f1 (t+l)dt. (2-39)

-T

This form is convenient for the analytical or experimental determination

of the autocorrelation function of a random variable

[Lee, I960, p. 66] . A procedure for this determination could be

programmed on a digital computer [ Blackman and Tukey, 1959; Ralston

and Wilf, I960] . This form is not very handy, however, for mathematical manipulation so a more convenient form will be introduced.

We state, without proof, the Wiener -Khintchine Theorem for Autocorrelation of Random Functions [Lee, I960, p. 93] . -9-
U (T) = \ $ 1X (u) cosuuTduu (2-40)

-CO

and °°

$ ii(w) = 2n j

^n(T) cosuit dT (2-41)

where § u (uu) is the power density spectrum. Note that (2-40) and

(2-41) are FTP.

Example 2-5:

Consider a random waveform of the type shown in figure 2-10

which has the Poisson distribution

P

?

(n;T) = ^j- exp(-kT) (2-42)

where k = average number of zero crossings per second,

T = some time interval in seconds,

n = number of crossing in T.

The autocorrelation function may then be shown to be [Lee, I960,

pp 221-224]

0u(T) = E

a exp(-2k|T|) (2-43) m

and the power density spectrum will be

00

$ ii(w) = y~ \

£2 exp(-2kK|) cosuut dT (2-44)

-00

,2 E*m 2k

(2k)2 + uus (2-45)

-10-
The autocorrelation function is shown in figure 2-11 and the power

density spectrum in figure 2-12. We see from this example how we

may determine the power density spectrum of a random signal if we

know its probability distribution or if we are able to determine the

autocorrelation function by analytical means.

While we are discussing the autocorrelation function and power

density spectrum, we should look at the concept of an integrated power

spectrum.

Consider an ideal low-pass filter which has the response characteristic shown in figure 2-13. Such a filter is not physically realizable,

(see appendix 10. 1), but we may consider it theoretically. If we have

such a filter whose cut-off frequency is variable, and connect it as shown

in figure 2-14, we may obtain a curve of the power consumed in the

resistor as a function of the cut-off frequency of the filter. When the

filter input is a random function, this curve will have the appearance

of figure 2-15. We may now plot the slope of the curve of figure 2-15

and arrive at the dotted curve of figure 2-16. This may be recognized

as the power density spectrum defined only for positive frequency. If

we divide every ordinate value by two, and plot the negative and positive

frequencies, we have $ii(uu), the solid curve of figure 2-16.

We are now in a position to define an integrated power spectrum

as the power contained in any power density spectrum up to some

frequency, uu

Su(w) = { *u(fi) dfl. (2-46)

If we wish to know the power between ou = (d. c. ) and some frequency,

0)

S(uu- ) = \ $ xl (u>) duu. (2-47) a

^uu

a

-11-
Note that the integration must include both positive and negative

frequency. The power between two frequencies, U) and ui , would be

-i» ,uu

S(u) a

) = [ a

$ 11 (uu)dua + \ § u (u))duu (2-48)

% a

2 \ $11 (uu)d(ju. (2-49)

a

Equation (2-49) can be written from (2-48) because $ ($) has

symmetry about uu = 0. A typical curve for S11 ((JD) is shown in

Figure 2-17.

Example 2-6:

Consider the power spectrum $ 99 (n) of a periodic wave which is

mixed with the power density spectrum, $n(uu) of a random wave.

Such a mixture would have the appearance of figure 2-18. If we now

integrate this mixed spectrum, we have the curve of figure 2-19 in

which the jumps are caused by the presence of the periodic components

in the spectrum and the magnitude of the jump determines the amplitude

of that particular component. In this way, we could reconstruct the

power spectrum of the original signal but no phase information would

be available.

2. 3. Crosscorrelation and Convolution

We shall now discuss crosscorrelation and convolution, but in less

detail than the Fourier series and the autocorrelation function. This

is not to detract from the importance of these functions in data analysis,

but they are made up of two functions and are not in general used to

-12-
represent a single function. An exception to this statement is the

convolution between a time function and the unit-impulse. The unitimpulse acts as a scanning function of the original time function and

reproduces it if its ordinates are stated only at the time of the unitimpulse. This type of operation will be discussed in more detail in a later section.

a. Crosscorrelation

(1) Periodic Functions. The crosscorrelation function of periodic

functions f_ (t) and f3

(t) is defined as

i r 2

012 (T) = Tx j

fl(t) fs(t+ T) dt (2_50)

-Ti

and the cross-power spectrum as

ll8 (n) = F!(n) F8 (n) (2-51)

where Fx (n) denotes the complex conjugate of Fx (n).

The autocorrelation function may be considered as a special case

of the crosscorrelation function where fx (t) and f2

(t) are equal.

From (2-50) and (2-51) we may also write

12 (T) =Y \z (n) exp MniiJi T J

(2-52)

n= and

li

h*{*) = ^T" j 0ia (T) exp | -Tx

-13-
Note that0 13 (T) and $l8 (n) are FTP.

(2) Aperiodic Functions. We define the crosscorrelation function

for aperiodic functions fx (t) and fg (t) as

'ia(T) = ( fi (t) f2

(t + T) dt (2-54)

and the cross -energy density spectrum as

$ X2 (uu) = 2ttFj. (uu) F3 (uu). (2-55)

We may now write

and

012CO = ( $ia (uu) expMuuT^duu (2-56)

*&M = ^T j^ia(T ) exp(^-ju)T^dT (2-57)

_ 00 where 12 (T) and § ia (uj) are FTP.

(3) Random Functions. The crosscorrelation function for random

functions f (t) and fs(t) is defined as

is < T > = T

^

2T~ J

fi( t

) f»( t + T

) dt • ( 2 ~ 58 ) -T

14-
We may then define a cross -power density spectrum such that

§ls(UJ) = 2n J0ls(T) exp(-J^ T )

dT (2-59)

and

0ia (T) = \ $ is(«J) expMouT jduu (2-60)

where lS {T) and $ ia (uu) are FTP.

b. Convolution

Convolution is similar to crosscor relation in that two functions

are used, one being scanned by the other. However, in convolution,

the scanning function is first folded about the origin, then shifted to

perform the scanning operation.

(1) Periodic Functions. We define the convolution of two periodic

functions, fi (t) andfg(t), as

Zl

i f

2

Pia(T) = fi(t)*fa (t) = - j fi(t)fa (T-t) dt. (2-61)

We may also write

Pia(T) = ^ Fx (n) Fa (n) exp MnUJx T j

(2-62)

n = -00

-15-
and

2

FxtnJFatn) = -i- ( p lS (T) exp ^-jnu)x T^ dT (2-63)

-T,

where p 18 (T) and Fx (n) F2 (n) are FTP,

(2) Aperiodic Functions. We define the convolution of two

aperiodic functions, fx (t) and fg (t) as

PlS (T) = fl(t)*fs (t) = j fi(t)fg (T-t)dt. (2-64)

Again we may write

and

p l2 (T) = \ 2tt Fx

(uu) F8 (oo) expMouf )

2ttFx (w) F2 (uu) = ± j

p 18 C0 expf- ja)T^)dT (2-65)

where p 13 (T) and 2ttF! (eu) F3

(uu) are FTP.

Note the similarity between the convolved power spectra and the crosspower spectra. The only difference between the two is that the complex

conjugate is not used in the convoluted power spectrum.

(3) Random Functions. Random functions are not usually

convoluted with themselves. However, random functions are used in

the convolution integral in two important ways.. The output of a linear

device (or network) is given by the convolution between the input, x

i (t), and the impulse response of the device, h (t) [Lee, I960, Chap. 13]

00 x (t) = \ h(T) x. (t-T) dT . (2-65)

I

i — 00

-16-
In the sampling process (described below in Sect. 3. 2) convolution occurs

in the frequency domain so that the output of the sampler is given by

00

Xo(uu) = \ H (v) X. (uu - v) dv. (2-66)

*J _ 00

These relationships hold equally well for periodic, aperiodic, or random

functions

.

2.4. Remarks

The purpose of this section has been to demonstrate some of the

mathematical tools of the data analyst. Specifically, we have attempted

to show how random functions may be treated in terms of power density

spectra and how periodic, aperiodic, and random functions may be

related. We have not delved too deeply into the physical significance

of the various operations for two reasons. First, to do so would require

much more time and space than are available and second, such accounts

are available in the literature in very lucid form. The reader is

specifically referred to three such accounts [Lee, i960, pp. 4-96;

Schwartz, 1959, pp. 18-72; Blackman and Tukey, 1959] which cover

the matter in some detail.

Note also that the formulas given here require time records

which are infinite in extent. Such records do not exist and could not

be used if they did. Therefore, errors due to records of finite length

must be considered. Blackman and Tukey [1959] demonstrate techniques

to compensate for finite length records and a discussion of errors which

might be expected.

17-
3. SAMPLED DATA THEORY

3.1. Introduction

We wish now to investigate some of the properties of data sampling.

The requirements for data sampling come about in two ways. Often, in

communications work, only a single channel is available for many various

data. Some method of sharing the channel by the various data must be

devised if they are all to be transmitted. One method, frequency multiplexing, associates each data signal with a carrier, then all the carriers

are mixed together in the channel and separated at the receiver. A

second method which would allow the data to be transmitted over the

common channel is time -division multiplexing. In this method, each

datum is sampled for a short time and its value transmitted over the

channel. At the receiver, each datum is reconstructed from these

samples with the aid of a synchronizing signal to identify the various

data. The theory of data sampling is important in this kind of system to

determine the number of samples per datum cycle which are required

to completely specify the signal [ Stiltz, 1961] . The second type of system which requires information about data

sampling involves the use of a high-speed digital computer to process

and analyze experimental data which are normally analog in form. The

data must be translated from analog to digital form since the computers

will only accept digital inputs. An analog-to-digital converter (ADC)

which performs this translation has a finite interval between samples as some time is required for the conversion. We shall investigate how

this sampling interval affects the maximum frequency of the data under

study and some problems which will be encountered in attempting to

reconstruct the data from its samples.

-18-
3.2. Data Sampling

Consider the single-ended chopper modulator shown in figure 3-1.

2tt The chopping signal, f (t), has frequency uu = —, where T is the

period, and is shown in figure 3-2. If the spectra of f (t) and f(t) are

F (n) and F(uu) respectively, and if f(t) is ideally band-limited to some

maximum frequency, uu , we may write

uu

f(t) = \ F(uu) exp M uut ) duu (3-1)

-UUm

and °°

f c

(t) = /j

F

c

(n) exP(J nV ) n = - 00 From example 2-1, we may write (3-2) as

f c«" = \

nn

sm —

1+2 ) cos nuu t nrr c n=l ~2~

(3-3)

Figure 3-3 shows a typical spectrum for f(t) and figure 2-2 shows a spectrum which is typical of f (t). Note that we are considering f(t)

II3

F(ul)| »

of similar shape. A periodic function will have a line spectrum over

the same range and the arguments for F(uu) will apply equally well to

any F(n) or I F(uu)[ 3 which is limited to uu [Linden, 19591 • m

If we now investigate the output conditions for the circuit of

figure 3-1, we see that f (t) will be present only when both f(t) and

f (t) are present. We may, therefore, write

f s

(t) = f(t) f c

(t). (3-4)

-19-
We also know that multiplication in the time domain corresponds to

convolution in the frequency domain [ Blackman & Tukey, 1959>

pp. 72.-73] so that we may write

f.W = j £(t)

sm

L

nTT2

m

n= i v ^ y

1 + 2 /

-* 1 cos nuu t nTT \ c (3-5)

and represent the spectrum of f (t), F (uu), obtained by convolution

of F(uu) and F (n), as shown in figure 3-4.

Let us now ask: What, if any, is the relationship between uu and a) ? If we examine figure 3-4, we see that a lower limit for uu m c (for a particular uu ) will be reached at the point where m

uu - uu = uu (3-6)

c m m

If uu were to decrease beyond this point, or U) to increase, the

c m

spectra would overlap and distortion would result. We may, therefore,

establish a relationship for uu and uu such that m c

uu cm^ 2uu (3-7)

or

uu

u> * -r^ (3-8) m 2

for the single-ended chopper modulator.

Let us now consider, for our chopping signal, a rectangular

pulse whose width is small compared to the period, instead of the

square wave we used above. Such a pulse train is shown in figure 3-5.

We shall describe the functions for this discussion with the additional

-20-
subscript 1 in order to distinguish them from the preceding discussion.

We shall continue to use the circuit of figure 3-1 to illustrate the

operation. The input signal, f (t), has spectrum F (uu), and the chopping,

l l or sampling signal, f (t) has spectrum F (n) . Then, using similar

ci ci arguments as above, we may write

uu

(t) = \

m

Fi (OU) exp ( juut ) duu

-uum

(3-9)

V \L F

C! <n)

^

{ ^V

f

1 + 2

00

. /nnT

v-« sin ——

y \ t

Li nTTT n=l

cos n(JU t c

= d 1 + 2

sin (nTTd) — — cos nuu t nTTd c n=l

(3-10)

where d = T/T, the duty cycle.

If f (t) has spectrum F (uu), we may write

si si

F (uu) = F (ID) * F (n)

si i ci

and f

, (t) = f (t) f (t)

si i ci

= fi (t) d 1 + 2

sin(nnd) v

:

' cos nuu t (nnd) c n=l

by the argument above concerning convolution.

(3-11)

-21-
The spectrum, F (uu), obtained by convolution of Fx

(uu) and F (n)

si ci of the sample signal, f (t), is shown in figure 3-6. Note the similarity

ci between this spectrum and the one of figure 3-4.

If we now make the same comparison of uu and uu which was m c made for the square-wave chopping signal, we again have the relationship

uucm£ 2uu . (3-12)

3.3. The Sampling Theorem

We state here, without proof (see appendix 10. 2), the sampling

theorem in the form given by Shannon [ 1949] :

"If a function f(t) contains no frequencies higher than W cps, it

is completely determined by giving its ordinates at a series of points

spaced —- seconds apart."

2 W

Stiltz [ 1961, p 86] gives the theorem in essentially the same

form, except that the phrase". .

. , the series extending throughout

the time domain" is added to the end of Shannon's statement.

Equation (3-12) provides a heuristic proof of the sampling*

theorem. However, there are some practical shortcomings

of the theorem which make it difficult to apply exactly to a physical

problem. The first of these shortcomings is the requirement for an

ideal band-limited spectrum. We have mentioned in a previous discussion that such a spectrum cannot be obtained with physically

realizable circuits (see appendix 10. Ifor proof). Secondly, as indicated

in the statement of the theorem by Stiltz, in order to completely

recover all phase and amplitude information of the original signal, the

samples must extend throughout all time, from negative to positive

infinity. This is obviously not practical.

Since we cannot apply the sampling theorem exactly to the

analysis of data, we should study the errors which are introduced,

uu principally by the non-zero spectrum above —- .

-22-
3.4. Recovery of Sampled Data

The recovery of data from the sampled form is often required where

a digital communication link has been used, either for communication of

data between two separated points, i. e. , telemetry, or in a closed-loop

control system. We shall describe a method, which while not physically

realizable, does give some insight into the problem of data reconstruction.

Consider the signal whose spectrum is shown in figure 3-6. We

m

c m

c wish to recover only that portion of the spectrum between —— and + —— .

If any frequency components outside of this range are included, distortion

(error) will result. We must, therefore, use an ideal low-pass filter to

select only this portion of the spectrum.

Let us next consider the Fourier transform of F (m), f (t).

si si

If we assume that d is very small, we may say that f (t) is a train of

amplitude modulated unit impulses. It is shown in appendix 10. 1 that the

response of an ideal low-pass filter to a unit impulse is given by

uo / sin uj t h(t) = f- (^f-

)

,3 - 13 '

where uo is the cutoff frequency of the filter. If, instead of §(t), the unit m

impulses, we use f (t), our sampled time function, it may be shown that

si

00

f

x (t) = 2, f ( nT ) h (t-nT) (3-14)

n = - 00

where T is the sampling period [Susskind, 1957] . Each sample of the

original function, occurring at a multiple of the sampling period, excites

sin U) t a response from the ideal low-pass filter. The sum of all

uu t c these individual outputs is the original function, f

x (t).

-23-
3.5. Aliasing

a. Description of Aliasing

We see from figure 3-6 that when uu exceeds —— , the two m 2

portions of the spectrum centered at zero and uu will overlap to some

extent depending r ° on the ratio of 0) cmto 0) . If a line is drawn at 0) /2,

c we see that, in effect, the spectrum of f(t) is folded about UJ /2,

c sometimes called the Nyquist frequency after H. Nyquist [ 1928] . This folding of the spectrum about uu / 2 "aliases" a frequency above

uu uu —c c

- to a frequency below —— . For example, consider a sampling

c frequency of uu = 10 k rad/sec. Then —— = 5 k rad/sec. If we

now sample a signal which contains a frequency component at say

6k rad/sec, then, because of the folding of the spectrum about ——

,

this component is "aliased" to 4k rad/sec. If our input signal had a component at 4k rad/sec. already, the original and aliased signals

would be added together and there would be no way to separate them.

b. Errors due to Aliasing

Since we cannot construct an ideal low-pass filter to limit the

input spectrum to uu , let us investigate the errors which are introduced

when a realizable filter is used and aliasing occurs.

Consider a filter with maximally flat amplitude response

[Martin, 1955, pp.184-191] such that

12 A

|H(u>)|- - 7

- s Mm (3-15)

1 +1 —

-24-
where

H(uu) = filter response

A = low frequency power gain (0 dB)

U0o = 3 dB frequency

m = roll -off factor

(i.e. for m = 1, roll -off = 6 dB/ octave

= 2, roll -off =12 dB/ octave

etc. )

.

The response of such a filter is shown in figure 3-7. The shaded

area to the right of -r— represents the aliasing error power, that is,

c the power which will be aliased to some frequency below —— and will

be indistinguishable from the spectral components already present

there.

uuc

If —— , the Nyquist frequency, is sufficiently in excess of uu , the cut-off frequency, we may, with negligible error, represent the

filter, as for uu > —— , as

uu S1T1 IhH - A(ir) • (3-i6)

03 C We may now find the amount of power above ——, that is, the

aliasing error power, which is given by (see 2-46)

S m

s =*- ) dU) a

(«» . ^ |h«4| dm - A y^) uu uu c c

2 ma

/,,, \

3i" ~ 1 2m-l V uu c

25-
We may also find the total signal power

s

b m -J H(u))| duu = A

s

duu

nAuu , o csc f n

2m I 2m (3-18)

The relative rms error will now be given by the square root of

the ratio of (3-15) to (3-16),

S (uu) V = , _^_ = 2

m

e \l S (uu) m n

n(2m-l)\^uu y \2rr c/

1

-1 2 (3-19)

This relative error is plotted for several values of m in figure 3-8

[Stiltz, 1961] .

4. BINARY NUMBERS

4. 1. Representation of Decimal and Octal Numbers

If we consider r as the radix of some numbering system, then

any number (x) may be represented

(x) = a a ... a a a

r n n-i a i o

n n-i s l o . . = a r + a r +...+ar+ar+ar (4

n n-i 3io

where: a = multiplier or weighting factor.

26-
For example, the decimal number (8271) may be represented as

10

8271 = 8 x 10

3 + 2 x 10 8 + 7 x 10 1 + 1 x 10° (4-2)

where r = 10,

or similarly: 8000 +200 + 70+1 = (8271) . (4-3)

10

This is the familiar decimal number system. Each weighting factor

may have as many values, or levels, as the radix. The radix exponent

is determined by its position in the number.

If we now let r = 8, the octal base, we see that the weighting

factors may only have the values through 7. If we count in this scale,

the successive numbers will be 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12,

13, 14, 15, 16, 17, 20, 21, 22, etc. and any number (x)s will be

represented as

x = a 8 + a 8 + ...+a8+a8 + a x 8 (4.4)

a n n- 1 3 1 + a o

v '

For example:

(100) =1x8 3 +0x81 + 0x8°=64+0 + = (64) . (4-5)

8 10

If we let r = 2, as in the binary number system, then each weighting

function, a , may take on only one of two values, and 1. Again we

may count in this system

0, 1, 10, 11, 100, 101, 110, 111, 1000, etc.,

and any number (x) will be represented as

3

(x) = a 2

n

+a 2

-1 +...+a2 +a 2*+ a 2 . (4-6)

2 n n-i 2 1

-27-
For example:

(101000) = 1 x 2

s + x 24 + Ix23 + 0x2 s +0x2 1 + 0x2( a

= 32+0+8 + + 0+0 = (40)

10 Note that if we consider

(4-7)

[(101) (000) ] = [50] = 5 x 8

1 + x 8° = (40) . 3 S 8 8 10 (4-8)

We may convert (40) into binary notation by a series of repeated

10 subtractions

.

So far we have considered only the direct conversion of a decimal number to a binary number. There is, however, an intermediate relationship where each decimal digit may be represented by a combination of 4 binary digits (bits). This is called the Binary-CodedDecimal (BCD) form.

TABLE 4-1

Binary-Coded D<3cimal Representation

of Decimal Numbers ; 8421

0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001

The number (8271) might be represented as

10

(8271) = (1000) (0010) (0111) (0001)

10 (4-9)

-28-
Many other combinations of BCD codes are possible such as 2421,

4221, etc. [seePhister, p. 244] .

4. 2. Binary Decision Elements

Let us now consider, instead of numbers, statements which

are either true or false. For instance, the statement A may be

either true or false, but not both. We may build other statements

upon basic statements. The outcome would depend upon the conditions

of the basic statement. For convenience, we shall represent a true

statement by the number one (1) and a false statement by the number

zero (0).

A is true, A = 1 A is false, A = (4-10)

We now introduce three combination statements:

(1) F will be true when either A is true or B is true or if

l both are true, and false otherwise. We represent this as A or B = A + B. (4-11)

F is called the "or" function (also called "inclusive or"). The circuit

l which performs this function is called the "or circuit or the "or" gate.

A logic symbol for such a circuit is shown in figure 4-1.

We may make a "table of combinations" or a "truth table" for

the "or" gate.

TABLE 4--2

Truth Table for "or" Circuit

A B F

l

1 1

1 1

1 1 1

-29-
(2) F will be true only if both A and B are true, and false

2 otherwise,

F = A and B = A x B = AB . a (4-12)

F is called the "and" function and is performed by an "and" gate,

shown symbolically in figure 4-2.

TABLE 4-3

Truth Table for "and" Circuit

A B F

a

1

1

1 1 1

(3) F will be true only when A is false and false when A is true,

3

F = A false = not A = A = A

3

(4-13)

F is the "not" function and is performed by the "not" or "inverter 1 3gate (figure 4-3).

TABLE 4-4

Truth Table for "not" Circuit

A

1

F

3

1

-30-
SWITCHING LOGIC I We shall now study an algebra which will lend more rigor and

elegance to the statements introduced above. This is the Boolean

algebra, named after the 19th century Irish mathematician, George

Boole.

5.1. Boolean Algebra

The postulates given here follow those suggested by Huntington

[ 1904] . Note that the symbol e signifies "member of" or "belongs to . " Consider a class of elements, K, and two rules of combination

11 + " and " x." Also, assume the equality " = " so that a statement

may be replaced by another which is equal to it. The postulates,

which shall form a basis for our algebra, are:

P. 1: If AeK and BeK, then (A+B)eK.

If AeK and BeK, then (AxB) = (AB)eK.

There is an element such that A+0 = A for AeK.

There is an element 1 such that Axl = A for AeK.

Whenever A and B belong to K, (A+B) = (B+A).

Whenever A and B belong to K, AB = BA.

Whenever A, B, and C belong to K, A+BC = (A+B) (A+C).

Whenever A, B, and C belong to K, A(B+C) = AB + AC.

If the and 1 of postulates 3 and 4 are unique, then

there is an element A such that AA = and A+A = 1.

There are at least two elements, X and Y, which belong

to K such that X £ Y.

Note that the postulate 7 gives rise to the idempotent relations

AA = A

A + A = A . (5-1)

Using these 10 postulates, we could proceed to develop a

P. 2

p. 3

p. 4

p. 5

p. 6

p. 7

p. 8

p. 9

P. 10:

-31-
series of identities for our algebra which would allow us to specify

functions and reduce them to their simplest form. Before doing so,

however, let us introduce an additional aid, geometric in nature,

which will make the job a little simpler.

Consider the class of mammals. Human beings are a subgroup of this class. If we represent the class of mammals by an area

in a diagram, the sub-class of humans may be represented as a smaller

area contained in the larger. This is demonstrated in figure 5-1.

Such a geometric interpretation of classes and sub-classes is called

a Venn diagram. Note that the area is not necessarily an absolute

representation of the size of the class.

We may now consider any universal class K, and two subclasses, or sub-sets, A and B. They may be represented as shown

in the Venn diagram of figure 5-2. The four areas which are labeled

with two literals (i. e. , letters) represent the intersections of A, A, B,

and B. For instance, the area AB is that area of A which is not in B.

We shall now introduce and prove a few theorems which will

complete our algebra.

Th. 1. DeMorgan's Theorem;

(XY) = X+Y, (X+Y) = XY (5-2)

This may be easily proven by use of a Venn diagram as shown

in figure 5-3a. The complement ("not") of XY is shaded in figure 5-3a.

The shaded areas in figure 5-3b are X and Y. In each case, the area

with no shading is XY and the area with any shading is XY.

Therefore, XY = X+Y.

Th. 2. Absorption Theorem:

X+XY = X, X(X+Y) = X . (5-3)

This theorem may be proven using the idempotent relationship,

-32-
(5-1), and postulate 9.

X+XY = XXl + XXY = X(l + Y) = XX 1 = x

and X(X+Y) = XX+XY = X+XY.

Th. 3. Redundant Literal Theorem;

(X+Y)Y = XY, XY+Y = X+Y. (5-4)

In each of these expressions, it may be shown that the Y literal

is not required.

(X+Y)Y = XY + YY = XY (note: YY = 0)

and XY+Y = XY+Y + YY + XY = (X+Y) (Y+Y)

Th. 4. Redundant Term Theorem:

XY + YZ + X Z = XY + XZ

A truth table will be used to prove this theorem.

X+Y (5-5)

(5-6)

TABLE 5-1

Truth Tabl e for Proof of Th eorem 4

X Y Z F

l F

2

1 1 1

1

1 1 1 1

1

1 1

1 1 1 1

1 1 1 1 1

where F = XY + YZ + XZ, F = XY + XZ.

l a Since F and F are equal, the theorem is proved.

l s

(5-7)

-33-
5.2. NOR and NAND LOGIC

In section 4. 2 above, we introduced three types of binarydecision elements, the "and" gate, the "or" gate and the "not" gate.

We shall now demonstrate two logic schemes which employ only two of

these gates. These are the NOR logic which uses the "or" and "not"

gates and the NAND logic which uses the "and" and "not" gates. In

order to make this demonstration, we must use de Morgan's theorem

XY = X + Y and X + Y = XY.

The second form is the basis for the NOR logic system. To

show this we consider some function F, take its complement, replace

l product (logical "and") terms according to de Morgan's theorem, and

recomplement to obtain the original function using only "or" and "not"

gates

.

F = (a+b+c) (x+y+z)

l F = a b c + xyz. (5-8)

l By de Morgan's theorem,

a b c = a +b+c

xyz = x+y+z. (5-9)

Substituting (5-9) into (5-8) we get

F = a+b+c + x+y=z (5-10)

l and

F = F = a+b+c + x+y+z. (5-11)

We have thus implemented a Boolean expression using only "or" and

"not" gates. No "and" gates are required.

The first form of (5-2), xy = x + y, is the basis for NAND logic.

34-
We shall demonstrate the NAND logic in a manner similar to that used

for NOR logic.

F = abc + xyz

s

3 By de Morgan's theorem,

a + b + c = abc

F = (a+b+c) (x+y+z) • (5-12)

x + y + z = xyz. (5-13)

Substituting (5-13) into (5-12) we get

F = (abc) (xyz) (5-14)

3 and

F = F = (abc) (xyz). (5-15)

3 3

No "or" gates are required.

6. SWITCHING LOGIC II We shall now introduce a standard, or canonical, form for

Boolean functions of several variables. The standard form is required

for some of the minimization methods to be discussed later.

We may express a function of n variables in one of two standard

forms, as a sum of products, or minterms, or as a product of sums,

or maxterms. The minterms and maxterms derive their names from

the fact that they are respectively the minimum and maximum areas

which may be defined on a Venn diagram. For instance, referring to

the Venn diagram of figure 5-2, the four areas labeled there with two

literals represent the four minterms of two variables, A and B. The

maxterms on the same diagram would be (A+B), (A+B), and (A+B).

Let us demonstrate the use of minterms and maxterms by defining a function f = A.

-35-
In general, a minterm, m. , is represented by

m. = (x x . . .x ), (6-1)

i is n

where n is the number of variables and the x. may or may not be complemented. A function represented by minterms would have the form

f = > m.

(6-2)

It can be shown that 2

£m= 1. (6-3)

i=0

If we wish now to find A in minterm form, from figure 5-2 we see that

AB + AB = A(B+B) = AXl = A. (6-4)

Similarly, a maxterm is generally represented by

M. = (x + x + . . . + x ), (6-5)

1 l a n

where the x. may or may not be complemented. A function represented

by maxterms would have the form

f = TTM.. (6-6)

i As with the minterms above, it can be shown that

2

n

n M. = 0. (6-7)

We now represent A in maxterm form

(A+B) (A+B) = A+AB+AB+BB = A(l + B+B)+0 = A (6-8)

-36-
A convenient method of representing minterms and maxterms

is with decimal notation. For instance, a minterm of four variables

may be written

ABCD = 1001 = 9 (6-9)

and a maxterm

(A+B+C+D)= 2. (6-10)

Using this notation, we may represent one function, A, from (6-4)

and (6-8) above:

A = ; (2,3) = n (2,3).

Example 6-1:

We shall now demonstrate how Boolean expressions may be

expanded into their minterm and maxterm form. Consider

f = AB+C(A+B) = AB+AC+BC- (6-12)

l This is a function of three variables. Therefore, for a minterm

expression, each term must be a product which includes all three

variables. We may multiply each term of (6-12) by 1 and not change

its value. In this way, we can get a minterm expression for each term,

and then add them all together.

AB = AB(C+C) = ABC + ABC

AC = AC(B+B) = ABC + ABC

BC = BC(A+A) = ABC + ABC

fi = ABC + ABC + ABC + ABC + ABC + ABC

= ABC + ABC + ABC + ABC (6-13a)

= Y (7, 6, 5,3) =) (3,5,6,7). (6-13b)

-37-

then
Consider another function of three variables

f = AB(A+C)+BC (6-14)

2 which we desire in maxterm form. We shall express the complement

of f , f , in minterm form, and then take the complement again to get

2 2 a maxterm expression for f . We may restate De Morgan's Theorem

2 (5-2) as: "In order to find the complement of a Boolean expression,

it is necessary to interchange the addition and multiplication operations

and to replace each literal with its complement. " Therefore,

f = AB(A+C) + BC

£ = (A+B + AC) (B+C) = (A+B) (B+C)

2 = AB+B+AC+BC = B+AC

We now expand f in minterm form:

2

B = B(A+A)(C+C) = ABC + ABC + ABC + ABC

AC = AC(B+B) = ABC + ABC~

f = ABC+ABC+ABC+ABC+ABC

2

f =F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C) (6-l5a)

2 2

= 11(2,6,7,3,5) = n(2,3,5,6,7) . (6-1 5b)

n

2

It should be noted that for n variables there are 2 possible functions.

For example, for two variables, there are 16 possible functions; for

3 variables, 256 possible functions; and for 6 variables, the number is

greater than 18 X lQ18

[ Chu, 1962, p. 108] .

38-
We could, using only the algebra developed so far, reduce

any given Boolean function to its simplest form. However, this becomes a very time-consuming process for more than three variables

and quite impractical when five or six variables are included. Therefore, we shall now describe some reduction, or minimization, aids

which will allow much easier simplification of Boolean expressions.

The most popular aids, for up to five or six variables,

are the Veitch and Karnaugh maps. Both are slightly different forms

of the same thing. We shall discuss the Veitch map first, then show

how it is related to the Karnaugh map.

Consider the Venn diagram of figure 5-2. We wish to

redraw this diagram so that the four areas representing the minterms

are equal. Such an equal-area map is shown in figure 6-l(a). Note

that A is always true on the left-hand half of the map and false on the

right-hand side. B is true on the upper half and false on the lower

half [figure 6- 1(b)] . This situation will hold no matter how many

variables are on the map. Each variable will be true on one -half of

the squares and falsj^ on the other half.

Figure 6-l(c) demonstrates how the minterms for two

variables are located on the map. We shall now give some examples,

using the four-variable map of figure 6-2, of simplifications possible

using the Veitch map. Consider any two adjacent squares (minterms)

on the map, say 7 and 15. Using the algebraic techniques described

above, we may simplify such an expression:

f = / (7,15) = ABCD + ABCD = (A+A)BCD = BCD. (6-15)

Note then that two adjacent squares on the map give rise to a three

literal term. Also note that the squares and 4, and 8, 4 and 12,

-39-
and 8 and 12 are adjacent in that these minterms combine to give a reduced term. We see that there are three types of adjacencies of

four squares, a row of four, as 0-1-5-4, a block of four, as 3-7-15-11,

and the four corners, 0-4-12-8. For instance, the four corners

simplify to the expression CD. Adjacencies of eight squares will

reduce to a single literal, as A, C, etc.

Example 6-2:

We shall now simplify a Boolean expression using the fourvariable Veitch map.

Consider

f = BC+BCD+ABC+BCD. (6-16)

Assume that we have derived this equation in one manner or another

and wish to check to see that it is the simplest expression which will

satisfy our conditions. Our technique is as follows: we first map the

function (6-16) onto a Veitch map similar to figure 6-2. We shall

designate a square for which the function is true with a 1 in that square.

All other squares will be left blank, but we shall understand that they

have a zero in them (figure 6-3). We may consider that the 1 or is

the multiplier of the minterm represented by that square.

In order to perform the mapping, we may expand (6-16)

into minterm form and then place the appropriate multipliers on the

map. It is much simpler, however, to map the function directly.

Note that the first term is made up of those four squares for which B

is false and C is true. We see from figure 6-2 that this corresponds

to squares 2, 3, 10, and 11. We map these terms on figure 6-3. In a similar fashion, we may map the rest of the function and arrive with

the complete map of figure 6-3. We shall now proceed to simplify the

function. We wish first to select those terms which are essential,

that is, have only one minimum combination with adjacent squares.

40-
Let us begin with the square 8. This term will combine with those

squares adjacent to it (10, or 10-11-9, or 9-13-12-14-15-11-10) or with the corners (0, or 12, or 0-4-12) or the row 10-2-0. The

minimum combination here is 0-2-10-8, since all the other combinations for which all the terms are present give a larger number of

literals. That is the combinations 8-0 or 8-10 give a three-literal

term while 0-2-10-8 gives a two-literal term. The term given by the

combination 0-2-10-8 is BD. We now place a small dot in the square

indicating that we have used it as part of an essential term. Note that

we must use every minterm at least once, but we may use it more

than once if it allows greater simplification. Similarly, we note that

the combination 3-7-15-11 gives the term CD. We now have left the

squares 4 and 5 which have more than one minimum combination. The

simplest expression will be obtained when we select the combination

4-5, since at least two terms will be required for any other. The

combination 4-5 gives the term ABC. The total expression, simplified

now from (6-16) is

f = BD+CD + ABC. (6-17)

s We have simplified an expression containing eleven literals to one

that contains only seven.

We shall now describe the Karnaugh map and show how it is

related to the Veitch map. Consider the Kanaugh map shown in

figure 6-4, on which the squares have been labeled with their minterm

designations. The labeling on the side and top of the map shows the

condition of the variable in that row or column. For instance, the 01

on the top of the second column indicates that A is false and B is true.

It may be easily verified that each variable is true on one half of the

squares of the map and false on the other half. Adjacencies on the

Veitch map are also adjacencies on the Karnaugh map, although their

-41
form may be different. For example, the four corners of the Veitch

map appear as the top row of the Karnaugh map.

We shall conclude this section with a brief discussion of

optional, or "don't care" terms. These are terms, or states, of a

system which do not occur during operation of the system. Therefore,

they may be used in the simplification process. As an example,

consider the 8421 BCD code of Table 4-1. Assume we have a circuit

which uses this particular code. We wish to convert this information

from binary to decimal for a display. We note from Table 4-1 that

the states 10 through 15 cannot occur. We may, therefore, use these

states in our simplification of the terms for the binary-to -decimal

converter. Let us consider the term 5. We could, with complete

confidence, specify that the output 5 is given for the input condition

8421. However, referring to the Veitch map shown in figure 6-5, we

see that minterm 5 will combine with minterm 13 to give (5) = 421.

10 It may be demonstrated, using the map of figure 6-5, that two 4-input,

six 3-input, and two 2-input circuits ("and" gates) are required to

completely implement the BCD-to-decimal converter.

7. SWITCHING LOGIC in

We shall now discuss one of the exhaustive tabular methods

such as might be used for a large number of variables or might be

programmed on a computer for the automatic reduction of a Boolean

expression [ Bartee, 1959] , This method, known as the QuineMcCluskey method, was originally developed by Quine but its use was

systemized and simplified by McClusky [ 1956] . We know from a study of Boolean algebra that two terms

differ only in one literal may be combined with the differing literal

removed. In the Quine method, an exhaustive comparison of the

minterms is made and then a selection is made from the remaining

-42-
terras which results in the simplest expression. The literal expression

for the minterm is used. In the McCluskey method, a numerical

description, either binary or decimal, is used to describe the minterm.

An order, or rank, is assigned to each minterm based on the number

of ones in the binary expression.

For example, 0001, OOlO, 0100, 1000 all have rank 1 0011, 0110, 0101, 1001 all have rank 2

etc.

McCluskey observed that a particular minterm need only be compared

with the minterms of next higher rank since these were the only

positions where a difference of one literal could occur.

We are required to use minterms for this method. If our

function is not specified in minterms, we must operate upon it, as shown above, to get it in this form. We shall work an example which

will demonstrate this technique. We shall include some optional terms

to show how they are used in this method.

Exampl e 7 - 1

Consider

f = ^(2,3,7,9.11,13)+^ (1,10,15) (7-1)

x

where / indicates the optional minterms. Roughly, the procedure

x

is as follows:

a) The minterms, including optional terms, are separated

according to rank and placed in a column to the left of

the page.

b) Comparisons are made between the terms in each rank

and the one above it (rank 1 compared with rank 2, etc.).

-43-
c) When a simplification is made, a check mark is placed

by the two terms and the simplified combination is placed

in a second column. Terms may be used more than once

but only one check mark need be placed by any term.

d) This process continues until all possible combinations

are made in the first column. As each simplification is

made, it is placed in the second column according to rank,

except that a blank spot occurs where the literal was

removed. For example: 1, 0001, and 3,0011, combine

to give a term in the second column, 1, 3 00-1.

e) Steps 4(a) through (d) are repeated for each column until

no further simplifications are possible. This terminates

the reduction part of the method.

f ) All unchecked terms are now collected together as "prime implicants" that is, terms which contain all

required information about the function,

g) A selection is made from the prime implicants which

gives the minimum number of terms to specify the function.

We shall now demonstrate this process. From step (a), we set up the

first column of Table 7-1. The terms are grouped according to rank

(1,2, 3, and 4). Note that the optional terms of (7-1) are included.

The simplified terms from the first column are listed in the second,

along with an indication of where they came from. Again, a separation

is made according to rank. When making comparisons in the second

column, only those terms of adjacent rank with the blank in the same

space need be compared.

44-
TABLE 7- 1 Example of the Simplification of a Boolean Function

1

Using the Quine-McCluskey Method

0001^ 1,3 00-lf 1, 3, 9,H -0-1 A

2 0010^ 1,9

2,3

-001^

001- ^

2, 3,10,11 -01- B

3 0011^ 2,10 -010 r 3, 7,11,15 --11 c

9 1001 r 9,11,13,15 1--1 D

10 1010 ' 3,7

3,11

0-11 ^

-Oil ^

i 7 0111 * 9,11 10-1 "

11 1011 *

9,13 1-01 '

13 1101^ 10,11 101- V

15 1111'' 7,15

11,15

13,15

-111 ^

1-11 «^ 11-1 *"

When all the possible comparisons have been made, all the

unchecked terms, which may appear in any column, are labeled in

the same manner as shown in Table 7-1. These unchecked terms

are the prime implicants, and we wish to select a minimum number

of them to specify our original function. In order to do this, we

construct a prime implicant table of the prime implicants and the

original minterms of the function. At this point we omit the optional

terms, since they have already contributed to the simplification

[Caldwell, 1958, pp. 145-156] .

-45-
TABLE 7 -2

P rime Implicant Tabl e

2 3 7 9 11 13

A X X X

«^B © X X

^C X © X

<D X X ©

Each minterm from the original expression must be included

at least once in our selection of prime implicants. Note that minterms

2,7, and 13 are only included once in a prime implicant. These prime

implicants then are essential terms. We must include them in order

to describe our function. We indicate this by circling the mark common

to minterm and prime implicant and placing a check mark next to the

minterm and prime implicant. Since B, C, and D must be included in

the final expression, let us see what other minterms are covered by

them. Note that B also includes 3 and 11, and D includes 9- Therefore,

all our minterms are covered and the combination of B, C, and D will

give us our simplest expression for (7-1). From table 7-1, we

see that B = XY, C = YZ, D = WZ. Therefore:

f = XY + YZ + WZ.

s (7-2)

Often there will be several choices available in the selection

of prime implicants. In such cases, there are several, non -unique

simplifications of a Boolean function. Several examples of these are

given in Chu [ 1962] and Caldwell [ 1958] .

-46-
8. CONCLUSIONS

This report is not intended as an exhaustive dissertation

on the subjects mentioned. Rather, -we have sought to cover a few

fundamentals so that the interested reader may proceed through the

literature with a minimum of effort.

Most of the information in the literature on sampled-data

systems is with regard to control and telemetry problems [Stiltz, 1961]

[Susskind, 1957] , [ Ragazzini & Franklin, 1958] . However, a very

good, general description of sampling theorems is given by Linden

[1959] . Monroe [1962] , while concerned mostly with control systems,

gives a good account of computer tie-ins with sampled-data- systems

There is a wealth of texts on the subject of logic and Boolean

algebra; Humphrey [ 1958] , and Maley and Earle [ 1962] have written

good descriptions of sequential circuits, that is, circuits whose output

depends on the history of the inputs, as well as their present states.

Maley and Earle also give a good description of NOR and NAND logic.

It is hoped that the reader who is interested in system design

using sampled data techniques or Boolean algebra will bypass the

descriptions given here and refer to the more detailed and rigorous

descriptions in the literature.

"A little learning is a dangerous thing;

Drink deep, or taste not the Pierian spring:

There shallow draughts intoxicate the brain,

And drinking largely sobers us again. " Alexander Pope

Essay on Criticism [ 1711]

47-
9. REFERENCES

1. Bartee, T.C. (1959) , Automatic design of logical networks,

Proc. WJCC, pp. 103-107.

2. Bello, P. (1964), Time -frequency duality, Trans. IEEE,

IT-10 , pp. 18-33.

3. Blackman, R. B. and J.W. Tukey(l959), The measurements

of power spectra from the point of view of communication

engineering, (Dover Publications, New York).

4. Caldwell, S.H. (1958), Switching circuits and logical design,

(John Wiley & Sons, New York).

5. Chu, Y. (1962), Digital computer design fundamentals,

(McGraw-Hill Publishing Co. , New York).

6. Humphrey, W.S., Jr. (1958), Switching circuits with computer

applications, (McGraw-Hill Publishing Co., New York, N.Y.).

7. Huntington, E. V. (1904), The algebra of logic, Trans. Amer.

Math. Soc, 5_, pp. 288-309-

8. Lee, Y.W. (i960), Statistical theory of communication, (John

Wiley & Sons, New York).

9- Linden, D. (1959)> A discussion of sampling theorems, Proc.

IRE, 47, pp. 1219-1226.

10. Maley, G. A. and J. Earle (1962), Logic design of transistor

digital computers, (Prentice-Hall Pub. Co., Englewood

Cliffs, N. J. ).

11. Martin, T.L. (1955), Electronic circuits, (Prentice-Hall

Publishing Co. , Englewood Cliffs, N. J. ).

12. Monroe, A.J. (1962), Digital processes for sampled-data

systems, (John Wiley & Sons, New York).

13. McCluskey, E. J. , Jr. (1956), Minimization of Boolean functions,

BSTJ, 35, pp. 1417-44.

-48-
14. Nyquist, H. (1928), Certain topics in telegraph transmission

theory, Trans. AIEE, pp. 617-644.

15. Phister, M., Jr. (1958), Logical design of digital computers,

(John Wiley & Sons, New York).

16. Ragazzini, J.R. and G.F. Franklin (1958), Sampled-data control

systems, (Mc-Graw-Hill Publishing Co. , New York).

17. Ralston, A., andH.S. Wilf (i960), Mathematical methods for

digital computers, (John Wiley & Sons, New York) pp. 213-220

18. Shannon, C.E. (1949), Communication in the presence of noise,

Proc. IRE, 37_, pp. 10-21.

19- Schwartz, M. (1959), Information transmission, modulation, and

noise, (McGraw-Hill Publishing Co. , New York).

20. Stiltz, H.A. (1 961 )

, Aerospace telemetry, (Prentice-Hall

Publishing Co., Englewood Cliffs, N. J.).

21. Susskind, A.K. (1957), Notes on analog-digital conversion

techniques, (M.I.T. Technology Press and John Wiley &

Sons, New York).

49-
10. APPENDICES

10.1. The Ideal Low-Pass Filter

Consider the filter whose response is shown in figure 10-1,

where G(uu) is a normalized power spectrum and H(uu) is the complex

spectrum. Such a filter has unity gain up to uu and zero gain (infinite

attenuation) for all frequencies above uu . We wish to demonstrate that

c such a filter is not physically realizable.

We know* that the frequency response of such a filter is the

Fourier transform of its response to a unit impulse, 6(t). Therefore,

we may write for the filter of figure 10-1:

h(t) = \ H(uu) expf juut ) duu

_ 00

(10-1)

where

so that

H(uu) = — , - uu < uu< uu 2 c c

0, elsewhere

uu

h(t) nexp I juut ) duu

uu

exp ( juut

2TT jt

uu

uu

h(t) =

uuc expMuu t

J -expf -K*)

n

uuc

2ju) ct

, sin uu t v (

° 1 m TT V, V J

(10-2)

cf. Lee [I960], pp. 328-330,

-50-
We see at once from(10-2) that a unit impulse, 6(t), applied

at t = excites an output from the filter for negative as well as

sin uj t positive times (from the symmetry of the function). There

c fore, we may conclude, since the filter produces an output before it receives an input, that the ideal low-pass filter is not physically

realizable.

10.2. Proof of Sampling Theorem

We shall state the sampling theorem as:

"If a function f(t) contains no frequencies higher than W cps,

it is completely determined by giving its ordinates at a series of points

spaced —- seconds apart, the series extending throughout the time

L-t VV domain".

The points spaced seconds apart will be located at

-2tt _n_ rr_ 2tt nn

uu = 2HW (10-3)

Consider the Fourier integrals:

f(t) = \ F(uu) expMout

J duu (l0-4a)

-U),

F(UJ) = r^- \ f(t) exp f -jcut ^dt . (l0-4b)

-51
Since F(uu) is limited to W cps, we may consider that it is periodic

with period 2uu . Therefore, we may write in a dual form of (2-5)

F(uu) = c exp

n

nTT

J

I ) U) for |w|<|(JU

c n= -oo where

w

-UJn is a dual of (2-7).

Now, from (l0-4a), we may write

duu

(10-5)

(10-6)

(10-7)

so that

c = JL t(_ £2 (10-8)

We may now substitute the value for c in (10-5) which determines

n nn the complex spectrum from only the ordinate values at times —W

Once the spectrum is uniquely determined, the original function is

given by (10-4a) [Linden, 1959; Monroe, 1962J.

-52-
fit)

-m

b

-*• t

Figure 2-1. Recurrent pulse train.

4 Fin)

i Em

-7 -6 *~l •- -n

-3 6 7

-5 -4 •2 -1 e 1 2 4 5

Figure 2-2. Spectrum of recurrent pulse train.

-53-
f(t)

m

-*> t

Figure 2-3. Rectangular pulse.

F(cu) E mb

Figure 2-4. Spectrum of rectangular pulse.

f(t)

f,(t+r)

f,(t)

-t

b t,

Figure 2-5. Periodic triangle for autocorrelation.

fr-cu

-54.
<£„(T)

+ T

Figure 2-6. Autocorrelation function of a triangle.

ll(T)

f,(t+T)—

*T

Figure 2-7. Single pulse Figure 2-8.

Autocorrelation of single pulse.

f *i|(CU)

-6 7T b

-47T

b

-27T JJL

b

47T

b

*cu

67T (rad/sec)

b

Figure 2-9. Energy density spectrum of a single pulse.

-55-
+ E m

-

0-

r

EmFigure 2-10. Random waveform,

^.(r)

-i.o Figure 2-11

* r(msec)

Autocorrelation function for waveform of figure 2-10

with E = 1 volt, k = 1000/ sec. m

4>n(cj)

*0J

-4000 -2000 o 2000 4000 6000 (rad/sec)

Figure 2-12. Power density spectrum for waveform of figure 2-10.

56-
H(CJ)

o cuc Figure 2-13.

Band-pass characteristic

of an ideal low-pass filter.

-OJ

* cue

Figure 2-15. Power consumed in resistor as

a function of cut-off frequency.

T o- RANDOM INPUT FUNCTION

IDEAL LOW- PASS

FILTER

H(OJ)

Figure 2-14. Measurement of the power spectrum

of a random function.

-CU

Figure 2-16. Power density spectrum of a random function.

-57
S,,(Cl))

Figure 2-17. Integrated power spectrum of a random function.

A 4>(GU)

•„(cu) * 2

( n )

-4cu, -3oj, -20Ji -CUi OJi 2dJi 3cl>i 4cl»i

Figure 2-18. Spectrum of mixed random and periodic waves

58-
* (X) -40U| -30J, -20J| -OJ, CU| 2CU, 30J| 4Gl>|

Figure 2-19- Integrated power spectrum for mixed random

and periodic waves.

f(t)

-VW-

/£ «jj> o»c

f«(t)

1

fc(t)

m

Figure 3-1. Single-ended chopper modulator

59
fc (t)

>t

II

2

Figure 3-2. Chopping signal, f (t), for figure 3-1

* OJ

Figure 3-3. Band-limited spectrum of f(t)

W>

<-T

Figure 3-5. Very narrow chopping (sampling) pulse,

•60
u3toE3|o3to

u

<pcu

u a, 3 ou

X)

CD -dn

CD E CD 3 I—

+ 00 u fl 3 CO

fn

u

O 3

<-H

-t-> ii u3 mO E3

4-JO

(Ua, co o 1 co E D 3i 3

GO E •rH 3 h +3iE3iu3

CDw

00

en

LlO3O

cda

COi CO

<Du

00 • I-l

61
I 1 I I

I * I I I

u->

m

>NU

S^

0)fl A a

1 [

<uh

1 <+H o bfl 3

fl \ i—

1

u a77 3 8 o

ccj O

> CO r-l o •H «

-z. N

Ill

fl £

o 3 •-, o

Ld -M CO O i i fl li_ fl £! VM CU CD oj 1—

1

-z.

CO _l rt -y 0_ flj <

CO

rror ly

fl

Q

LdN fl -H

_)

<

2

rt

<i ctf o

z oo

00

CDu

flOJO

(xi

±N33d3d 'U0Ud3 9NISVHV SIAIU

-62-
OJ

Figure 3-7. Response of maximally flat filter showing

aliasing error power [Stiltz, 1961] .

F. = A + B F9 = AB

Figure 4-1. Logical OR function. Figure 4-2. Logical AND function.

A or A

Figure 4-3. Logical NOT function.

63
CLASS OF /

HUMANS

CLASS OF ALL

MAMMALS

Figure 5-1. Example of a Venn diagram.

Figure 5-2. Universal class and two subsets

on a Venn diagram.

( a ) XY V///. (b) Y^S , %V///.

Figure 5-3. Proof of De Morgan's Theorem

by Venn diagrams.

•64-
AB AB

AB AB

(a)

•{ {

3 1

2

(b) (c)

Figure 6-1. Development of Veitch map,

(

12 14 6 4

I 13 15 7 5

9 II 3 1 ;

8 10 2

(

1

I 1 •

1 •

1

1 •

1 •

1 •

1 •1 •

1 •

Figure 6-2. Figure 6-3

A four-variable Veitch map. Map for solution of equa. (6-16)

CD

00

01

AB

00 01 II 10

10

4 12 8

1 5 13 9

3 7 15 1 1

2 6 14 10

Figure 6-4. Example of a Karnaugh map.

-65
X

12 X

14 6 4

X

13 X15 7 5

9 X

1 1 3 1

8

X

10 2

Figure 6-5. Veitch map for BCD-to-decimal converter,

G(CJ)

OJc

-+(!)

-0Jr

t H(CU)

1/2

-CU

CDr

Figure 10-1. Frequency response of an ideal low-pass filter.

66-

GPO 857-099

U.S. DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20230

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMER

OFFICIAL BUSINESS