CHAPTER 3 ELEMENTARY DESIGN EXAMPLES

The purpose of this chapter is to introduce the reader to the RTM design process by posing and solving a number of elementary RT-level design problems. The problems use the modules in Chapter 2 in a straight-forward fashion to hold Booleans (bits), and unsigned, and 2's complement signed integer data. The main concepts that are introduced are data representation and defining and structuring problems for solution; also included are some uses of subroutines, clocks for timing, and the related problem of synchronizing two independent systems.

Most of the designs in this chapter, being small, are actually subprocesses that occur in larger programs. For example, the first problem, counting the number of one bits in a word, would hardly ever be done for its own sake. Not until Chapter 5 do the problems become sizable enough to constitute entire information processing tasks. We do pose a couple of the problems in this chapter to have external input and output, thus being complete systems. But these are somewhat contrived, in order to give the flavor of total systems.

However, one should not view the designs of the present chapter simply as finger exercises. As we noted in Chapter 2, one builds up subprocesses out of the basic RTM's that are used again and again in larger systems. Some of the more important of these we have called Extended RTM's\ERTM's, and this chapter includes several of them. These ERTM's package various complex forms of control, the most complex one being the K(for loop) which evokes the operation of a subsystem for a variable number of iterations. Thus, these elementary examples contain important lessons about how to build complex control. They will be useful throughout the book both as actual modules (i.e., as ERTM's) and as models for larger systems.

The design examples are presented in a uniform format. A list of keywords appear first and sometimes a brief introduction is given. The problem is then stated, design considerations (possibilities) posed, and solutions given. In most examples, additional problems (exercises) are either posed or posed and solved.

COUNTING THE NUMBER OF ONE BITS IN A WORD

KEYWORDS: Counting, parity, cost-performance tradeoff, storing data within a flowchart, termination, testing

The operation of counting the number of l's in a word is usually needed when the word is considered to represent independent conditions (i.e., the word is a 16-bit Boolean vector). The 16 individual bits might represent the indices of stations requesting attention, hence a one's bit count would correspond to the total number of stations requesting attention at one time.

PROBLEM STATEMENT

Design a system which will count the number of one bits in a 16-bit word (sometimes called tallying in a computer).

DESIGN CONSIDERATIONS

The word is held in a register of a DMgpa. The word (data) may be destroyed in the calculation. The resulting count is held in a DMgpa register. For example, the following illustrates the relationship between input and output.

80