Computer Basics AND Computer Systems: Textbook For Software Design & Development Engineers
Computer Basics AND Computer Systems: Textbook For Software Design & Development Engineers
Ministry of Economy,
Trade and Industry
Textbook for
Software Design & Development Engineers
NO. 1 COMPUTER BASICS
AND
COMPUTER SYSTEMS
Second Edition
• Microsoft, MS-DOS, Microsoft Windows and Microsoft Windows NT are registered
trademarks of Microsoft Corporation of the United States in the United States and other
countries.
• The product names appearing in this textbook are trademarks or registered trademarks of
the respective manufacturers.
Table of Contents
1. Basic Theories of Information
Introduction 1-1
1.1 Data representation 1-2
1.1.1 Numeric conversion 1-2
1.1.2 Numeric representation 1-16
1.1.3 Operation and precision 1-33
1.1.4 Non-numeric value representation 1-36
1.2 Information and logic 1-40
1.2.1 Proposition logic 1-40
1.2.2 Logical operation 1-41
Exercises 1-44
2. Data Structures
3. Algorithms
Introduction 3-2
3.1 Basic of algorithms 3-2
SW No.1 COMPUTER BASICS AND COMPUTER SYSTEMS
4. Hardware
Introduction 4-2
4.1 Information element 4-3
4.1.1 Integrated circuit 4-3
4.1.2 Semiconductor memory 4-3
4.2 Processor architecture 4-6
4.2.1 Processor structure and operation principles 4-6
4.2.2 Speed performance enhancement in processor 4-21
SW No.1 COMPUTER BASICS AND COMPUTER SYSTEMS
5. Multimedia system
Index
Basic Theories of
1
Information
Chapter Objectives
Understanding the computer mechanism of data representation
and basic theories.
In particular, the binary system is an important subject to learn,
indispensable for computer data representation. However, for
people who are used to the decimal system, it is hard to become
familiar with this representation, so it be should be carefully
studied
1 Understanding a computer's basic data units such as binary
numbers, bits, bytes, words etc and their conversion from
and to decimal and hexadecimal digits.
2 Understanding basic concepts of computer internal data
representation, focusing on numeric data, character codes,
etc.
3 Understanding proposition calculus and logical operations
1- 1
Introduction
In order to make a computer work, it is necessary to convert the information we use in daily life
into a format that can be understood by the computer. For that reason, the way information is
actually represented inside a computer as well as the way it is processed will be learned here.
Binary numbers
The internal structure of a computer is composed of an enormous number of electronic circuits.
Binary numbers represent two levels of status in the electronic circuits, as in:
1- 2
• Whether the voltage is high or low
For example, setting the status where the electric current passes through (the power is on) to "1"
and the status where the electric current does not pass through (the power is off) to "0", then by
replacing the computer status or data with numeric values their representation can be easily
performed in an extremely convenient way.
The representation of decimal numbers from "0" to "10" using binary numbers is shown in
Figure 1-1-1.
Figure 1-1-1
Decimal Binary
Decimal numbers numbers numbers
and binary numbers 0
1
10 A carry occurs
11
100 A carry occurs
101
110
111
1000 A carry occurs
1001
A carry occurs 10 1010
As can be seen in this Figure, compared to the decimal system, a carry occurs more frequently in
the binary system, but since besides "0" and "1", no other figure is used, it is the most powerful
tool for the computer.
Bits
A bit (binary digit) is 1 digit of the binary system represented by "0" or "1". A bit is the smallest
unit that represent data inside the computer. 1 bit can represent only 2 values of data, "0" or "1",
but 2 bits represent 4 different values.
• 00
1- 3
• 01
• 10
• 11
However, in practice, the amount of information processed by a computer is so immense (there
are 26 values in the English alphabet alone) that the two bits, 0 and 1, are insufficient for an
information representation method.
Bytes
Compared to a bit which is the smallest unit that represent data inside the computer, a byte is a
unit that represents 8 bits of 1 character or number. Considering that a byte is equal to 8 bits, the
following is the information which can be represented with one byte, by the combination of "0"
and "1".
• 00000000.
• 00000001
• 00000010
:
:
• 11111101
• 11111110
• 11111111
The information represented by a string of "1's" and "0's" is called a bit pattern. Since 1 bit can
be represented in two ways, the combination of 8 bit patterns into 1 byte enables the representation
of 28=256 types of information. In other words, besides characters and figures, symbols such as "+"
and "-" or special symbols such as "<" and ">" can also be represented with one byte.
1- 4
Figure 1-1-2
1 byte
Types of information
that can be represented
with one byte
can be represented
256 types
However, since the number of kanji (Chinese characters) amounts to thousands, they cannot be
represented with one byte. Therefore, two bytes are connected to get 16 bits, and one kanji is
represented with two bytes. With 16 bits, 216 = 65,536 kanji can be represented.
Words
A bit is the smallest unit that represents data inside a computer and a byte is a unit that represents
1 character. However, if the computers internal operations were performed on the bit basis, the
operation speed would be slow. For that reason the idea of processing using a unit called word was
born.
Over 10 years ago, personal computers operated on words each consisting of 16 bits. Currently,
mainstream PCs use words each consisting of 32 bits.
1- 5
A hexadecimal number is a numeric value represented by 16 numerals, from "0" to "15". When it
becomes 16, a carry occurs. However, since it cannot distinguish between the "10" before a carry
has been generated, and the "10" after a carry has been generated, for purposes of convenience, in
the hexadecimal system "10" is represented by the letter "A", ""11" by "B","12" by "C", "13" by
"D", "14" by "E" and "15" by "F".
Hexa-
Figure 1-1-3 Decimal Binary Figure 1-1-3 shows the notation of the
numbers numbers decimal
Decimal numbers, numbers numbers "0" to "20" of the decimal
binary numbers, 0 system in the binary system and the
and hexadecimal numbers 1 hexadecimal system.
Focusing on the relationship between
10
the hexadecimal numbers and binary
11
numbers in this table, it can be noted
100
that 4 digits in the binary system
101 correspond to 1 digit in the hexadecimal
110 system. Therefore, binary numbers can
111 be converted to hexadecimal numbers,
1000 by replacing each group of 4 bits with a
1001 hexadecimal digit, starting from the
decimal point. (Figure 1-1-4)
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
16 10000 10
17 10001 11
18 10010 12
19 10011 13
20 10100 14
Figure 1-1-4
Binary, and hexadecimal
counting systems
1 byte Binary number
Decimal
4 bits 4 bits
point
Hexadecimal number
1- 6
different representation method is used to process numeric data. Here, radix and radix conversion,
the addition and subtraction of binary numbers and hexadecimal numbers, the representation of
negative numbers, among other points considered basic for the representation of numeric data, will
be explained.
For example, using the weight, a decimal number 1,234 would be represented as follows:
1,234 = 1 x 103 + 2 x 102 + 3 x 101 + 4 x 100
Decimal number
Figure 1-1-5
Weight of each digit of Ten Name of each digit
thousand Thousand Hundred Ten Unit
the decimal number 21998
104 103 102 101 100 Weight of each digit
In Figure 1-1-5, the weight of each digit s represented as 100, 101, 102, 103, and 104. This "10" is
called "Radix" and the value placed at the upper right of 10 is called the "Exponent". The
notation and meaning of the weight in the decimal system is explained below.
In 100, the radix 10 is multiplied 0 times by 1, so it becomes 1, in 101, the radix 10 is multiplied
0 times by itself, so it becomes 10.
Likewise, in 102, 10 is multiplied 2 times by itself, so it becomes 100; in 103, 10 is multiplied 3
times by itself, so it becomes 1000.
In this way, even when the number of digits increases. it can be easily represented by writing
down in small numbers, to the upper right of 10, the numeric value that indicates the number of
times the radix 10 is multiplied (exponent).
1- 7
b. Binary digits "weight" and its meaning
The radix of the decimal system is 10, and the radix of the binary system is 2. As in the decimal
system, the weight of each digit in the binary system is shown in Figure 1-1-6.
Figure 1-1-6
Weight of each digit of the Binary number
The notation and meaning of the weight in the binary system is explained below.
In 20, the radix 2 is multiplied 0 times by itself, so it becomes 1, in 21, the radix 2 is multiplied
only 1 time by itself, so it becomes 2. Likewise, in 22, 2 is multiplied 2 times by itself, so it
becomes 4.
To verify that the decimal number 1,998 is represented as "11111001110" in the binary system,
the weight of each of the digits represented by 1 in the binary representation should be added, as
is shown below:
1 1 1 1 1 0 0 1 1 1 0
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
210 + 29 + 28 + 27 + 26 + 23 + 22 + 21
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
= 1,024 + 512 + 256 + 128 + 64 + 8 + 4 + 2
= 1,998
1- 8
Figure 1-1-7 Unit symbol Exponent Remarks
notation
Auxiliary units 12
T (giga) 10 240
Units that
G (tera) 10 230
represent
large M (mega) 10 220
amounts k (kilo) 10 210
1
m (milli) 10-3 1,000
Units that
1
represent (micro) 10-6 1,000,000
small
amounts 1
(nano) 10-9 1,000,000,000
1
(pico) 10-12
1,000,000,000,000
It is important to note that, as indicated in the Remarks column in Figure 1-1-7, kilo is equal to 103,
but it is almost equal to 210. In other words, the kilo we ordinary use is equal to 1,000, however,
since the binary system is used in computing, 210 (1,024) is a kilo. Furthermore, if 210 and 103 are
almost equal,106 that is a mega, is almost equal to 220 and 109 a giga, is almost equal to 230.
Therefore, when it is said that a computer memory capacity is 1 kilobyte, strictly speaking, 1
kilobyte does not mean 1,000 bytes, but 1,024 bytes.
• 1 + 1 = 10 (2 in the decimal system) Main characteristic of the binary system that differ
from the decimal system
Among these additions, a carry is generated in 1 + 1 = 10
1 ← Carry
1
+ 1
10
1- 9
Example
(11010)2 + (1100)2
1 1 ← Carry
11010
+ 1100
100110
• 0-0=0
• 0 - 1 = -1
• 1-0=1
• 1-1=0
Among these subtractions, if the upper digit of 0 is 1 in 0 - 1 = -1, a "borrow" is performed.
Example
(10011)2 - (1001)2
1-10
a. Addition is performed starting at the lowest (first from the left) digit. When the addition result is
higher than 16, a carry to the upper digit is performed.
• First digit: Since 3 - 4 = -1, a borrow is performed from D in the second digit (D
becomes C). 16 (borrowed 1) + 3 - 4 = F (In the decimal system: 19 - 4 =
15)
1-11
understand the meaning of the result if it were represented by binary or hexadecimal numbers.
Therefore, the conversion amongst decimal, binary and hexadecimal numbers is necessary. This
operation is called radix conversion,
A concrete example of the conversion amongst the radixes of decimal, binary and hexadecimal
numbers which are currently used the most, will be performed below. In order to avoid confusion,
the respective radix will be written outside the parenthesis to distinguish between them. For
example:
Example (25)10
2) 25 Remainder
2) 12 ··········· 1
2) 6 ··········· 0
2) 3 ··········· 0
2) 1 ··········· 1
Quotient 0 ··········· 1
(11001)2
1-12
b. Conversion of decimal fractions
The decimal fraction is multiplied by 2, the integer and fraction portion of the product are
separated, and the integer section is extracted. Since the integer portion is the product of the
multiplication of the fraction portion by 2, it will always be "0" or "1". Next, setting aside the
integer portion, only the fraction portion is multiplied by 2. This operation is repeated until the
fraction portion becomes 0. The binary digit is obtained by placing the integer portions extracted in
the order they were extracted.
Example (0.4375)10
(0.4375)10 = (0 . 0 1 1 1 )2
It should be noted that when decimal fractions are converted into binary fractions, most of the times,
the conversion is not finished, since no matter how many times the fraction portion is multiplied
by 2, it will not become 0. In other words, the above mentioned example is that of a special decimal
fraction, but most of the decimal fractions become infinite binary fractions.
The verification of the kind of numeric values which correspond to special decimal fractions is
performed below. For example, the result of the conversion of the binary fraction 0.11111 into a
decimal fraction is as follows:
0. 1 1 1 1 1 ← Binary fractions
↓ ↓ ↓ ↓ ↓
2-1
2 -2 -3
2 2 -4
2-5 ← Weight
↓ ↓ ↓ ↓ ↓
0.5 + 0.25 + 0.125 + 0.0625 + 0.03125 = 0.96875 ← Decimal fractions
1-13
From this example, it can be understood that besides the decimal fractions that are equal to the
weight of each digit (0.5, 0.25, 0.125, .... etc,) or the decimal fractions that result from their
combination, all other decimal fractions become infinite binary fractions.
(1 1 0 1 1) 2
24 + 23 + 21 + 20 ← Weight
↓ ↓ ↓ ↓
16 + 8 + 2 + 1 = (27)10
(1 . 1 0 1) 2
1-14
each group of 4 bits.
In the event that there is a bit string with less than 4 digits, the necessary number of "0's" is added
and the string is considered as a 4 bit string.
a. Conversion of binary integers
Example (10111010001)2
Considered as 0
0 1 0 1 1 1 0 1 0 0 0 1
↓ ↓ ↓ ↓ ↓ ↓
Weight
22 20 23 22 20 20
4 + 1 8+4+1 1
↓ ↓ ↓
5 D 1 = (5 D 1)16
8 + 2+1 8 + 4 4
0 . B C 4 = (0.BC4)16
1-15
a. Conversion of hexadecimal integers
Example (38C)16 3 8 C
12
2+1 8 8+4
1 1 1 0 0 0 1 1 0 0 = (111000110)2
b. Conversion of hexadecimal fractions
Example (0.8E)16
0. 8 E
14
8 8+4+2+0
0. 1 0 0 0 1 1 1 0 = (0.10001110)2
Conversion from decimal numbers into hexadecimal numbers and from hexadecimal numbers
into decimal numbers To convert them into binary numbers, decimal numbers are divided into 2, to
convert them into hexadecimal numbers, and then they are divided into 16. Likewise, hexadecimal
numbers are converted into decimal numbers by adding up the exponents whose radixes are 16.
It should be noted that due to the general unfamiliarity with the notation of hexadecimal numbers,
ordinarily hexadecimal numbers are first converted into binary numbers to convert them into
decimal numbers.
1-16
Figure 1-1-8 Fixed point (Integers)
Binary
Data representation numbers
Numeric Floating point (Real numbers)
format data
Data
Unpacked decimal Represented using
Decimal
Character numbers decimal arithmetic
data Packed decimal
(1) Decimal digit representation
0
1
2
3 Since the binary-coded decimal code
4 is not a numeric value but a code,
5 there are only 10 patterns, and the
6 notation is performed by arranging the
7 patterns for each digit.
8
9
10
11
For example, the representation of the decimal number "789" using the binary coded decimal would
be as follows:
7 8 9
↓ ↓ ↓
(011110001001)2
0111 1000 1001
In this way, ax the number of digits of a decimal number increases, the length of the binary coded
decimal code increases as well (a group of 4 bits is added for each digit). This format is called
variable length format.
1-17
The same value as the binary coded decimal code has also been set to the least significant 4 bits of
the numeric characters of the EBCDIC, JIS II and other codes.
The binary coded decimal code is mainly used for the numeric representation of office calculations,
and according to the memory format of the computer, it is divided into unpack decimal format and
packed decimal format. And, since character codes as well as the unpacked decimal format or
packed decimal format are represented by the use of the binary coded decimal code, they are
automatically processed using the decimal arithmetic system of the computer. It is not necessary
for the user to be aware of this process.
1-18
Figure 1-1-10 Unpacked decimal format
<For +789>
<For -789>
In the unpacked decimal format, excepting the least significant byte, only half of a byte is used.
This was considered a waste of resources. This defect was eliminated by the packed decimal
format.
1-19
Figure 1-1-11 <For +789>
1 byte 1 byte
Packed decimal
format
Sign bit
<For -789>
1 byte 1 byte
Sign bit
Compared to the unpacked decimal format, the packed decimal format has the following
advantages:
• Complement representation
a. Absolute value representation of negative integers
As is shown in Figure 1-1-12, in the absolute value representation of negative integers, the first
bit represents the sign and the 7 other bits represent the numeric value (absolute).
Figure 1-1-12 Bit number
Absolute value
representation of
negative integers Decimal point
Bit string that represents the integer
Bit that indicates the sign of the integer
("0" for positive, "1" for negative)
For example, in (00001100)2, since the sign bit at the top is 0, it is a positive number. Likewise,
1-20
since the 7 other bits, which are the absolute value of the numeric value, are (0001100)2 = 22 + 23 =
(12)10, the decimal number 12 (positive number) is represented.
On the other hand, since in (10001100)2 the sign bit at the top is 1, it is a negative number. The
decimal number -12 =(negative number) is represented. However, since in this representation
method the numeric value 0 can be represented in two ways, as 00000000 (positive zero) or as
10000000 (negative zero), the operation becomes complicated, and for that reason it is not widely
used.
It should be noted that when the absolute value representation of negative numbers is performed
with 8 bits, the range of numeric values that can be represented is as follows (in decimal digits):
-127 to 127
b. Complement representation of negative integers
The complement is the number that indicates the quantity by which a numeric value falls short of
a specific numeric value. There are 2 types of radix complements, the radix complement and the
reduced radix complement.
Decimal complement
There are two types of decimal complements, "10's complement" and "9's complement." For
example, the 9's complement of a given numeric value will be the result of the subtraction of
each of the digits of this numeric value from 9. Likewise, the 10's complement of a given
numeric value will be the result of the subtraction of each of the digits of this numeric value
from 10 As a result, the 10's complement is the result of the addition of 1 to the 9's complement.
Example "9's complement" of (123)10
999
− 123
876
Example "10's complement" of (123)10
(= 999 + 1)
1000
− 123
877 1-21
Binary complement
There are two types of binary complements, "1's complement" and "2's complement".
1's complement
The "1's complement" of a give numeric value will be the result of the subtraction of each
of the digits of this numeric value from 1, as a result, all the "0" and "1" bits of the original
bit strings are switched.
For example, the "1's complement" of the bit string (10110011)2 is shown below:
10110011
↓ ← All the "0" and "1" bits of the original bit string are switched
0 1 0 0 1 1 0 0 ←"1's complement"
2's complement
"2's complement" is the "1's complement" bit string plus 1. Therefore, the "2's
complement" of the bit string (10110011)2 is obtained as follows:
10110011
↓ ← All the "0" and "1" bits of the original bit string are switched
01001100 ←"1's complement"
+ 1 ←1 is added
01001101 ←"2's complement"
"1's complement" and "2's complement" representation of negative integers
"1's complement" representation of negative integers
Sign bit: 0 for positive, 1 for negative, and both ,+0 and -0, for 0
Numeric value: "1's complement"
For example, the "1's complement" representation of the decimal number -126 will be as follows:
01111110 ← + 126
Sign → ↓ ↓ ← All the "0" and "1" bits of the original bit string are switched
10000001 ← − 126
1-22
For example, the "2's complement" representation of the decimal number -126 will be as follows:
01111110 ← + 126
Sign → ↓ ↓ ← All the "0" and "1" bits of the original bit string are switched
10000001
+ 1 ←1 is added
10000010 ← − 126
As can be observed, even for the same number the bit strings of the "1's complement" and the "2's
complement" differ. Figure 1-1-13 shows a comparison of the range of numeric values which can
be represented with 3 bits in the "1's complement" and the "2's complement" representation. From
this figure it can be noted that the range of representable numeric values with the "2's complement"
is wider. Likewise, as in the absolute value representation of negative integers, and in the
representation of negative numbers using the "1's complement", 0 can be represented both, as +0
and as -0, so the operation becomes complicated. For that reason, a great number of today's
computers have adopted the 2's complement method.
Figure 1-1-14 shows the range of representable numeric values when an n-bit binary number is
represented with the "1's complement" and "2's complement".
Figure 1-1-13 "1’s complement" "2’s complement"
"1's complement"
and "2's complement"
Figure 1-1-14
Range of representable Range of representable numeric values when an n-bit binary number is
represented using the "1’s complement" method
numeric values with
n 1 n 1
"1's complement"
and "2's complement" Range of representable numeric values when an n-bit binary number is
represented using the "2’s complement" method
n 1 n 1
1-23
Another important reason for the adoption of the 2's complement method is illustrated by the
following example.
01100100
+ 10100110
1 00001010 (Decimal digit 10)
↑
Since the bit number is 8, the 9th digit resulting from the carry is ignored.
Therefore, the reason why negative numbers are represented using the 2's complement method in
computing is that subtractions can be performed as additions. In other words, since subtractions
can be performed with addition circuits, the subtraction circuits are unnecessary, simplifying the
hardware structure.
Fixed point
a. Integer representation
The fixed point is a data representation format used mainly when integer type data is processed
(Figure 1-1-15). Therefore, the fixed point format is also called an integer type.
In the unpacked decimal format or packed decimal format, depending on the digit number of the
decimal number, the number of bytes changes, but in the fixed point format one word is
represented in a fixed length such as 16 bits and 32 bits.
For that reason, if there is an attempt to represent a numeric value that exceeds the fixed length a
problem called overflow will occur.
Figure 1-1-15
Fixed point <When 1 word is represented by 16 bits>
16 bits
Since in the fixed point format in Figure 1-1-15, where a value is represented with 15 bits, if a
negative number is represented using the 2's complement" representation, the range of
1-24
representable numeric values in the decimal system is as follows:
-215 to 215 - 1 = -32,768 to 32,767
Likewise, if one word is composed of n bits, and a negative number is represented using the "2's
complement" representation, the range of representable numeric values in the decimal system is
as follows:
-2n-1 to 2n-1 - 1
b. Fraction representation
When integers are represented, the position of the decimal point is considered to be on the right-
hand side of the least significant bit.
When fractions are represented, the position of the decimal point is considered to be immediately
preceded by the sign bit.
Integer
representation
Position of the decimal point
Sign bit
Fraction
representation
Position of the decimal point
Sign bit
Floating point
While the fixed point format represents integer type data, the floating point format is used to
represent real number type data. In ordinary mainframe computers, a maximum of 18 digit decimal
numbers only can be represented. With 18 digits, there should be almost no problem in our daily
life.
However, in a world where complicated calculations such as the ones mentioned below are
required, correct results cannot be achieved with integer type data alone.
1-25
• Ballistic calculation
Here, to make it easier to understand, the decimal system is used, but in the computer, the binary
system is used.
The floating point representation format varies depending on the computer. This is roughly
classified into the format used in mainframe computers and that defined by the IEEE (Institute of
Electrical and Electronics Engineering).
a. Floating point representation format in mainframe computers
The floating point representation format used in general purpose computers is shown in
Figure 1-1-17.
This format was adopted in the first general purpose computer in the world the "IBM
System/360" and it was called Excess 64.
1-26
Figure 1-1-17 Floating point representation format in general-purpose computers
Mantissa sign (1 bit) The position of the decimal point is considered to be here
Mantissa sign: Indicates whether the data represented in the mantissa portion is positive or negative
(0: Positive, 1: Negative)
Exponent portion: Here, 16 is considered to be the radix and a numeric value +64 is represented as the real exponent.
Mantissa portion: Here, only a binary fraction lower than 1 can be represented.
Exponent portion
The exponent portion has 7 bits, and the range of numeric values representable in the binary
system is (0000000)2 to (1111111)2 , which in the decimal system is 0 to 127. However a
numeric value 64 times larger than the real exponent is represented. For that reason, the real
exponent is equivalent to -64 to +63.
Likewise, since the radix is considered to be 16, the numeric values that can be represented with
the exponent portion range between
16-64 to 1663
Then, including the sign bit, the range of numeric values that can be represented with the
exponent portion is shown in Figure 1-1-18.
Figure 1-1-18 Range of numeric values that can be represented with the exponent portion
Mantissa portion
When the decimal fraction 0.05 is converted into a binary fraction, it becomes a repeating binary
fraction. (0.0000110011001100110011001100....)2
Figure 1-1-19 shows the representation of this fraction when the floating point format is used.
1-27
Figure 1-1-19 Representation of the binary fraction (0.0000110011001100110011001100...)2
2 160
Since the mantissa portion has 24 bits, in this case, the decimal fraction 0.05 will not be represented
correctly. (The error that occurs in this case is called a rounding error)
However, if we look at the bit pattern of the mantissa portion, we can see that the 4 top bits are 0, if
we then extract these 4 bits and shift the remaining bits to the left, 4 rounded bits can be
represented. Here, as a result of shifting the mantissa portion 4 bits to the left, the original value of
the mantissa portion was increased by 24 = 16. In order to cancel this increase it is necessary to
divide it into 16 (x16-1). Since the radix is 16, the value of the exponent portion can be set to -1. The
technique, used in this way, in order to reduce the rounding error to its minimum as well as to
maximize precision is called normalization.
Furthermore, as a result of this normalization technique, the bit strings that represent a value are
standardized. This operation is performed automatically by the hardware.
The result of the normalization of the binary fraction representation in Figure 1-1-19 is shown in
Figure 1-1-20.
Figure 1-1-20
Normalization
2 16-1
1-28
Figure 1-1-21 IEEE floating point representation format
Exponent portion
Mantissa portion (23 bits)
(8 bits)
Mantissa sign (1 bit) The position of the decimal point is considered to be here
Mantissa sign: Indicates whether the data represented in the mantissa portion is positive or negative
(0: Positive, 1: Negative)
Exponent portion: 2 is considered to be the radix, and a value resulting from the addition of 127
to the value of the original exponent portion is represented.
However, When: E 255 F Not a number
S
When: E 255 F
When: E F S 126
0.F
S
When: E F Zero
Mantissa portion: Here, only a binary fraction lower than 1 can be represented.
S
Value represented using the floating point format: 1 2E 127
The differences from the general purpose computer floating point representation format are as
follows:
• The exponent portion has 8 bits, and a value resulting from the addition of 127 to the high
value of the original exponent portion is represented. This addition to the original value is
called bias. (Figure 1-1-22).
• The mantissa portion has 23 bits and a binary fraction equivalent to the mantissa -1 is
registered. In other words, 1 is considered to be omitted.
1-29
Figure 1-1-22 Representation of the exponent portion
2 126
2 127
255
128
Bias
127
For example, if the decimal number 5 is represented using this format, it will be represented as in
Figure 1-1-23.
• If (5)10 = (101)2 = (101)2 x 22 , then, the exponent portion will be (1.01)2 - (1)2 =
(0.01)2
• If (101)2 is shifted 2 bits to the right, it becomes (1.01)2, 2-2 times the former value. In order
to normalize it, 2 is added to the exponent 0, which becomes 2. As a result, since the
exponent portion is 2 + 127 = 129, the representation will be (10000001)2.
Figure 1-1-23
Mantissa sign
Representation of
the decimal number 5 Exponent portion Mantissa part
c. Shift operation
The mechanism of the shift operation performed at the normalization is explained below.
In the binary system, each digit has a weight which is a power of 2. This is called positional
weight.
1-30
Therefore, even though the same number 1 is represented, its meaning is different to that of the 1
positioned in the second digit and the 1 positioned in the third digit.
In the shift operation, by moving the position of 1 to the left (or to the right), the multiplication and
division of numeric values can be easily performed.
The conversion into decimal numbers (100101)2 and (1001010)2, resulting from shifting the first
value 1 bit to the left , would be as follows:
(1001010)2 → 1 0 0 1 0 1 0 = 64 + 8 + 2 = (74)10
Through this conversion, it should be noted that the 1 that represented 25 before shifting, now
represents 26 , the 1 that represented 22 now represents 23 , an d the 1 that represented 20 now
represents 21. In other words, after the shift the value of each of the 1s was doubled, and the result
of the conversion into decimal system was also doubled from (37)10, to (74)10.
In short, the above mentioned result shows that by shifting a binary digit 1 to the left, its value is
doubled. Following this approach, the shift operation can be summarized by the following rules:
• When a binary number is shifted n bits to the left, its former value is increased 2n times.
• When a binary number is shifted n bits to the right, its former value is decreased 2-n times.
(The former value is divided by 2n
Arithmetic shift
The arithmetic shift is the shift operation used to calculate numeric values. It is used in the fixed
point format that represents negative numbers using the "2's complement" representation.
[Arithmetic shift rules]
0 0 0 1 0 1 1 0
0 1 0 1 1 0 0 0 = (88)10
Logical shift
The logical shift is the shift operation used in change the bit position. The big difference from the
arithmetic shift is that the sign bit is not treated differently.
• The bit to be filled into the bit position vacated as a result of the shift is 0.
After arithmetically and logically shifting (-16)10 2 bits to the right, convert each
of the results into decimal digits.
c Represent (-16)10 using the fixed point format (8 bits).
1 1 1 1 0 0 0 0
1-32
d Arithmetically shift 2 bits to the right
1 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0 = (-4)10
1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 = (60)10
0 is inserted 00
1-33
Single precision
In scientific and engineering calculations, numerical values are represented by binary digits in
word units. The word length depends on the hardware. For example, when 1 word = 16 bits, in
general terms, The format in which 1 numeric value is represented with one word .is called single
precision. The range of numeric value representable with 16bits, in case of an integer without a
sign , is indicated below.
Minimum value = ( 0000 0000 0000 0000 )2 = 0
Maximum value = ( 1111 1111 1111 1111 )2 = 65,535
In other words, values higher than 65,535 cannot be represented.
Likewise, the range of numeric values representable with 16 bits , in the case of a fraction without a
sign is indicated below.
Minimum value = ( 0000 0000 0000 0000 )2 = 2-16 0.0000152587890625000
Maximum value = ( 1111 1111 1111 1111 )2 = 1 - 2-16 0.9999847412109370000
In this case, values lower than 0.0000152587890625, and values higher than 0.999984741210937
can't be represented.
Double precision
In order to widen the range of representable numeric values, the number of digits is increased. By
representing 1 numeric value with 2 words, in comparison to the representation with 1 word, the
range of representable numeric values becomes much wider. This format is called double precision.
If 1 word = 16 bits, 1 numeric value is represented with twice as many bits, 32 bits.
Minimum value = ( 0000 0000 0000 0000 0000 0000 0000 0000 )2 = 0
Maximum value = ( 1111 1111 1111 1111 1111 1111 1111 1111 )2 = 4,294,967,295
In other words, values up to 4,294,967,295 can be represented.
Likewise, the range of numeric values representable with 32 bits , in the case of a fraction without a
sign is indicated below.
1-34
Minimum value = ( 0000 0000 0000 0000 0000 0000 0000 0000 )2 = 2-32
0.00000000023283064365387
Maximum value = ( 1111 1111 1111 1111 1111 1111 1111 1111 )2 = 1 - 2-32
0.99999999976716900000000f
(2) Operation precision
1-36
ASCII (American Standard Code for Information Interchange) code
The ASCII code was established by the U.S. standards institution, ANSI (American National
Standards Institute) in 1962. Character code of 8 bits composed by the code bit representing the
alphabet, numeric characters, etc. (7 bits) and the parity bit used to detect errors. It is used in
personal computers and in data transmission.
1-37
Shift JIS code
As was mentioned above, to represent kanji, the JIS kanji code represents 1 word with 2 bytes.
Figure 1-1-24 JIS X 0201 code table
Bit number
High-order bits
Co
lum
b8 b7 b6 b5 b4 b3 b2 b1 Row n
10 11 12 13 14 15
10
11
12
13
14
15
There are times when the JIS code and the JIS kanji code are mixed. When 1-byte codes and 2-byte
codes are mixed, their interpretation can't be performed. Therefore, a special escape code is added
to the front and back of the kanji code string. For example, a bit string of 5 kanji becomes 10 bytes
+ 2 bytes. When data is missed during data transmission, etc. recovery is difficult.
In order to find a solution to this defect, the shift JIS code that converts the characters defined in the
JIS Kanji code into another code system was created. The first byte of the shift JIS uses a code that
is not used in the JIS (1 byte) code, and, at the same time , by avoiding control character codes in
the second character, 1 byte codes and 2 byte codes can be mixed without using special escape
codes.
Unicode
The Unicode is a 2 byte code system unified to all the countries, which was proposed and
designed by Apple Computer, IBM, Microsoft, and other U.S. companies in order to smooth the
exchange of data amongst personal computers. This code was adopted by ISO as an international
standard draft.
1-38
(3) Audio representation
As has been said, the current information technology provides multimedia support, and the data
subject to processing is not limited to character data or numerical data. It also covers many kinds of
information that are used in our daily life. One of the components which compose multimedia is
audio.
The human voice is produced when the airflow generated in the lungs changes, vibrates and
resonates due to a great number of organs such as the tongue, lips, teeth, jaw, nasal cavity and vocal
cords. Since audio data has a complicated analog waveform, audio analysis is performed using a
numeric formula and once it is converted into digital codes it is processed in the computer. Word
processors that accept audio input and speaker recognition are examples of its recent applications.
(4) Image representation
In order to support current multimedia, not only audio but also image data must be processed.
Inside the computer, image data is processed as a set of dots. For that reason, the registration of the
status of each of the dots that compose an image, is the registration of the image data itself. the
easiest approach is to register two states, black and white, for each of the dots that compose an
image. In this case, 1 bit is used to register the information of each dot. Today most of the image
data is colored, so this method does not solve all problems. Therefore, the representation method
that combines the basic colors in each dot is used. Amongst computer screens, there are a great
number of systems that combine the three primary colors (Red, green and blue) in 256 levels
respectively and represent approximately 16,000,000 colors. In this case, since 8 bits are needed for
1 color, in order to register the information of 1 dot, 24 bits is used.
1-39
1.2 Information and logic
• The proposition "The wind is not blowing" is false when the proposition 1,"The wind is
blowing" is true, it is true when the proposition 1 is false.
• The proposition "The wind is blowing or it is raining" is true when both, the proposition 1
,"The wind is blowing" and the proposition 2, "It is raining," are true or when either of the
two is true. When both of them are false, it is false.
1-40
Figure 1-2-1 Truth table
1-41
The truth table is shown in Figure 1-2-3, and the result is true only when p and q are both true.
Figure 1-2-3
Truth table for
the logical product
(4) Exclusive OR
In the logical sum mentioned above, "The wind is blowing or it is raining," either "The wind is
blowing" or "It is raining" is expressed. This logical sum is true when "The wind is blowing and it
is also raining," or in other words, when both propositions are true. Ordinarily, the word "or" is
used in many cases to express exclusive meanings as "either of the two". The exclusive OR is used
to support these cases.
In the case of the exclusive OR, the logical symbol "v (EOR)" is used and it is represented as
"pvq." The result is true only when p or q, either of the two, is true. Therefore, the result is false
when p and q are both true or false. This logical operation is frequently used in programming.
Figure 1-2-5 p q p q
Truth table for T T F
the exclusive OR T F T
F T T
F F F
(
X⊕Y = X⋅Y + X⋅Y ) ( )
(( ) ) (( ) )
= X⋅Y + X ⋅ X⋅Y + Y ·········· Distribution law
= ((X + X ) ⋅ (X + Y )) ⋅ ((Y + X ) ⋅ (Y + Y )) ·········· Switching law and distribution law
= ( 1 ⋅ (X + Y )) ⋅ ((Y + X ) ⋅ 1 ) ·········· Logical sum law
= (X + Y ) ⋅ (X + Y ) ·········· Logical product law
1-43
Exercises for No.1 Chapter 1 (Basic Theories of Information)
Q1 Which of the following represents correctly the size relation amongst the following 4 prefix
symbols that represent integer exponents of 10: G (giga), k (kilo), M (mega) and T (tera)?
A. G<k<M<T B. k<G<T<M C. k<M<G<T
D. M<G<k<T E. M<T<G<k
Q4 Which of these values is the correct result of the subtraction of the hexadecimal numbers DD
and 1F "00-1F"?
A. AF B. BE C. CE D. EC E. FC
Q5 Which of these values represents in decimal numbers the result of the addition of the binary
numbers 1.1011 and 1.1101?
A. 3.1 B. 3.375 C. 3.5 D. 3.8 E. 3.9375
Q6 Which is the decimal number that can be represented without error in the binary floating
point representation?
A. 0.2 B. 0.3 C. 0.4 D. 0.5
Q7 Which of these values represent the hexadecimal fraction 0.248 in decimal fractions?
31 31 31 73
A. B. C. D.
32 125 512 512
Q8 Which is the correct bit pattern of the decimal number +432 when it is represented in the
packed decimal format? Note that the sign is represented by the last 4 bits, and that "1100"
represents positive numbers while "1101" represents negative numbers.
A. 0000 0001 1011 0000
B. 0000 0001 1011 1100
C. 0001 1011 0000 1100
D. 0100 0011 0010 1100
E. 0100 0011 0010 1101
1- 44
Q9 What is the range of the integer representable with n bits using the fixed point format that
represents a negative number with 2's complement representation? Here, the decimal point
position is on the right side of the least significant bit (LSB).
A. −2 n to 2 n-1 B. −2 n-1 to 2 n-1
C. −2 n-1 to 2 n-1 − 1 D. −2 n-1 − 1 to 2 n-1
Q10 Which of the following is the reason why in many computers the complement representation
is used to simplify the operation circuit?
A. Additions can be processed as subtractions.
B. Subtractions can be processed as additions.
C. Multiplications can be processed by the combination of additions.
D. Divisions can be processed by the combination of subtraction.
Q11 Which of these values corresponds to the representation of the decimal number -5.625 in
binary number using the 8-bit fixed point format? Here, the position of the decimal point is
between the fourth and fifth bits, and negative numbers are represented using the 2's
complement representation.
8 7 6 5 4 3 2 1
Q12 Which is the normalized representation of the decimal number 0.375? Here, the numeric
value is represented using the 16-bit floating point format and the format is indicated in the
figure. The normalization performed is an operation that adjusts the exponent portion in
order to eliminate the 0s of higher digit rather than the significant values of the mantissa
portion.
4 bits
1 bit 11 bits S: Mantissa sign (0: Positive, 1: Negative)
A 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
B 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1
C 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
D 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
Q13 Which is the value that corresponds to the result of logically shifting the hexadecimal number
ABCD two bits to the right?
A. 2AF3 B. 6AF3 C. AF34 D. EAF3
1- 45
Q14 The multiplication of binary number can be performed through the shift operation (digit
shift), and addition. To increase the binary digit m by 2n it is necessary to shift m n bits to the
left.
For example, m × 19 can be obtained through the following operation:
(Value of the result of shifting m one bit to the left) + (Value of the result of shifting m one bit to the left) + m
Which is the value of a?
A. 2 B. 3 C. 4 D. 5
Q15 The decimal number -100 is registered using the 2's complement representation in a 8-bit
register. Which of these values represent, in decimal numbers, the result of arithmetically
shifting this registration three bits to the right?
A. –33 B. –13 C. –12 D. 19
Q17 What is the minimum number of digits required for representing uniquely with the same
number of bits of the uppercase alphabetic characters (A to Z) and the numeric characters (0
to 9)?
A. 5 B. 6 C. 7 D. 8
Q18 The following truth table shows the operation results of the logical operation "x y." Which
of these expressions is equivalent to this operation?
Truth table
x y x y
True True False
True False False
False True True
False False False
Q19 Which of the following expressions is equivalent to the logical expression ( A + B )· C ? Here,
"⋅" represents the logical product (AND), "+," the logical sum (OR), and A is the negation
of A (NOT).·
A. (A· B) + C B. A⋅B⋅C
C. A+B+C D. (A · B) + C
1- 46
Data Structures
2
Chapter Objectives
Choosing the most appropriate data structure and data
description procedure is the key to creating efficient, easy-
to-understand program.
This chapter describes various data structures you must
understand as the first step to learning programming
2- 1
2.1 What is the data structure?
A set of the same kind of data processed by a computer is called a "data type". In the program
design stage, the way data should be represented and programmed into a computer must be
examined carefully, so that the most appropriate data type can be chosen. A data type that is
represented and programmed is called a "data structure".
Figure 2-1-1 shows the Classification of data structures
Figure 2-1-1 Classification of data structures
Integer type
Real number type
Character type
Simple type
Logical type
Basic data type
Enumeration type
Pointer type Partial type
List structure
Stack
Problem-oriented
data structure Queue
Created using the Tree structure
basic data structure
Hash
The basic data structure can be represented in almost all programming languages. The problem
oriented data structure is a data structure that can be effectively used to solve specific problems.
These are some problem oriented data structures that cannot be represented in programming
languages. In that case, the basic data structure is used.
2- 2
2.2 Basic data structure
2- 3
(1) Pointer type
The pointer type has an address allocated in a main memory unit. It is used to refer to variables,
file records or functions. It is used for Pascal and C but not for FORTRAN and COBOL.
Figure 2-2-1 Image of the pointer type
Pointer-type variable Variable "b"
(Address of a variable "b") Data
A 1 A 2 A 3 A i
dTwo-dimensional array
A data structure in which data is lined up in both vertical and horizontal directions is called a
two-dimensional array. Data in a vertical direction is called a row and data in the horizontal
direction is called a column. To specify an element in this array, two subscripts become
necessary: one subscript showing in an ordinal number in a vertical direction (in what column)
where a specified element is located and the other subscript showing in what ordinal number in a
horizontal direction (in what row) it is located. An array "A" located in the "i" column and "j"
row, for example, can be expressed as A(i,j).
2- 4
Figure 2-2-3 Two-dimensional array (with three rows and two columns)
Column j
A 2,1 A 2,2
A 3,1 A 3,2
When a two-dimension array is stored in a main memory unit, it takes the form of a one-
dimensional array. The two-dimension array shown in Figure 2-2-3 takes the form of a one-
dimensional array having six elements. As shown in Figure 2-2-4, data is stored sequentially in
either the direction of columns or the direction of rows. The direction in which data is stored
varies, depending on the compiler of the programming language used. In general, data is stored
vertically when FORTRAN is used and horizontally when COBOL is used.
Figure 2-2-4 How data of a two-dimensional array is stored in a main memory unit
Two-dimensional array Main memory unit
A 2,2 A 1,2
A 3,1 A 2,2
A 3,2 A 3,2
eThree-dimensional array
A three dimensional array has a data structure in which more than one-dimensional is
contained. It has a three-dimensional structure comprising planes, columns and rows as elements.
By developing a three-dimensional array into a two-dimensional one, a three dimensional array
can be handled in the same way as a two-dimensional array.
2- 5
Figure 2-2-5 Developing a three-dimensional array into a two-dimensional array
Second plane
A 2,1,1 A 2,1,2
Plane
A 2,1,1 A 2,1,2
A 1,3,1 A 1,3,2
A 1,1,1 A 1,1,2
A 1,3,1 A 1,3,2
Multidimensional arrays such as four-, five- or n- dimensional arrays can be defined. However,
there may be certain limitations to the number of definable dimensions depending on the type of
programming language or compiler.
Arrays can be classified into static and dynamic arrays according to the method used to secure an
area.
- Static array: An array for which a required area is determined by a program
- Dynamic array: An array for which a required area is determined after a subscript is used for
arraying is provided with an expression and the expression is evaluated during
execution of a program.
2- 6
Figure 2-2-6 Record type
One record (data on a student)
Student Student
number Name Marks number Name Marks
Sort type
Character type
Figure 2-2-6 shows the data structure of the record type. One record contains a student number
(integer type), a name (character type) and marks (integer type). One record type data contains a
set of records of this format. Although one-dimensional record type data can be handled in the
same way as a one- dimensional array, each data must be named for identification sine each
element contains more than one data.
(Operations +
Program
data structures)
Result
2- 7
2.3 Problem-oriented data structure
Various problem-oriented data structures can be designed using the array type, pointer type and
other basic data structures.
An element
Inoue
to be inserted
Unlike the array type structure, the list structure allows data element to be inserted or deleted
easily. The list structure is similar to the array structure in that data elements of the same type are
sequentially lined up.
The array type requires that the logical arrangement of elements is the same with the physical
arrangement of elements stored in a main memory unit. In the case of the list structure, the
logical arrangement does not need to match the physical arrangement.
The list contains cells and each cell consists of the following:
- Data section that contains data element
- Pointer section that contains an address
Therefore, the data section of a cell has the same structure as that of stored data and the pointer
section of a cell has a pointer type data structure. This means that cells represent record-type
(structure) data that contain elements of different data structures. The list contains cell addresses
in the pointer section and one cell is linked to another via a pointer.
2- 8
Figure 2-3-2 List structure
Data section Pointer section Data section Pointer section Data section Pointer section
Inserted cell
Inoue
After insertion Arai Ueki Endou
Although the list structure allows data to be inserted or deleted by simply replacing pointers, it
has the drawback that you must track each pointer one by one from the top if you want to access
specific data.
2- 9
- Bi-directional list
- Ring list
because these lists are represented in the form of a straight line, they are generically called linear
lists.
cUni-directional list
The uni-directional list is also called a one-way list. The pointer section of a cell contains the
address of a cell in which the next data is stored. By tracking these addresses one by one, you
can perform a search on data.
The first pointer is called a root or head. Because the pointer section of the last cell does not have
any address in which data can be stored. NULL (Numerical value of zero) or \ is entered in this
section.
dBi-directional list
The bi-directional list has two pointer sections ( and ) which contain cell addresses as shown
in Figure 2-3-6.
Figure 2-3-6 Bi-directional list
head tail
The pointer sections and shown in Figure 2-3-6 contains the address of the subsequent cell
and the address of the preceding cell respectively. The address of the last cell is contained in the
pointer tail. In the case of the bi-directional list, data can be tracked from the either the head or
the tail of cells.
eRing list
A bi-directional list containing NULL in the first cell is called a ring list. The pointer section of
this first cell and the pointer section containing NULL of the last cell contain addresses of one
another, thus data is in the form of a ring. Data can be searched in the same way as in the bi-
2- 10
directional list.
2.3.2 Stack
A stack is a data structure designed based on a one-dimensional array. Last stored data is read
first. It is likened to the game of quoits.
Blue
Yellow Yellow
Green Green
Red Red
Quoits are thrown in the order of red, green, yellow and blue (data input). They are retrieved one
by one (data output) in reverse order of throwing, i.e. blue, yellow, green and red. That is, blue
quoit last thrown is first retrieved.
This type of data structure which can be likened to the game of quoits is called a stack. This
system is termed the last-in first-out (LIFO) system. Storing data in a stack is called "push down
(PUSH)" and taking data from a stack is called "pop up (POP)". A variable that controls pushing
down and popping up of data is called a stack pointer.
To push down data into a stack, set the stack pointer "sp" to +1 and store data in array elements
indicated by "sp". To pop up data from a stack, take out data stored in array elements indicated
by "sp" and set the stack pointer to sp-1.
2- 11
Figure 2-3-9 Stack structure
POP PUSH
Data to take out Data to enter
sp 1 sp+1
Stack pointer sp
stack 4 Data D
stack 3 Data C
stack 2 Data B
stack 1 Data A
2.3.3 Queue
A queue is a data structure designed based on one-dimensional arrays. Data first stored is first
read. It is likened to a queue of people who are waiting in front of a cash dispenser machine of a
bank.
A data structure that allows customers to be served on the first-come first served basis is called a
queue.
This system is called the first-in first-out (FIFO) system. Two pointers that indicate the head and
tail of a queue are required for queue control. Pointers that indicate the head and tail of a queue
are represented as a front variable and a rear variable respectively. (See Figure 2-3-11.)
Administrative Accounting First sales Second sales Sales & Planning Quality management Purchasing Production
section manager section manager section manager section manager section manager section manager section manager section manager
Although each cell is linearly correlated in the list structure, data is correlated while it branches
off in the tree structure.
The tree structure consists of elements shown below:
- Node: Correspond to data
- Branch: Connecting one node to another
- Root: Highest-order node that has no parent
- Child: Node that branches off under a node
- Parent: Original data before it begins to branch
- Leaf: Lowest-order node that has no child
Figure 2-3-13 shows the tree structure.
Leaf
The binary tree has a parent-child hierarchical structure, as shown in Figure 2-3-15.
Child Child
Search 10
10 10
- Pre-order: With a root as a starting point, the left side of each node is tracked in a sequentially.
- Mid-order: With a leaf at the bottom left as a starting point, the underside of each node is
tracked in a sequential way
- Post order: With a leaf at the bottom as a starting point, the right side of each node is tracked in
a sequential way.
(2) Perfect binary tree
If a binary tree is constructed in such a way that the number of branches from a root to each leaf
along one branch is equal to or different by one from that of branches from a root to each leaf
along another branch (or if the height from a root to each leaf along one branch is equal to or
different by one from that from a root to each leaf along another branch), it is called a perfect
binary tree. Figure 2-3-17 shows a perfect binary tree that has ten nodes.
2- 14
Figure 2-3-17 Perfect binary tree
10 10
15 10 15
8 10
21
10 28
10 10
13
2- 15
efficiency will decrease. A tree structure capable of reorganizing itself is called a balanced tree.
Representative balanced trees are a B-tree and a heap.
cB-tree
A B-tree is a further developed version of a binary tree:
- End leaves are removed and each node has a number of nodes specified as "m."
- Each node has a maximum number of data specified as "m-1"
- All leaves are on the same level.
- Data contained in each node is arranged in a queue.
Because the above characteristics can increase the memory and calculation efficiency, the name
"B-tree" means a well-balanced tree.
a. Characteristics of a B-tree
- To increase the memory area usage, the number of pointers that each node has is set at m/2 or
more and m or less. The number of pointers along a route, however, is set at 2 or more.
- Each time data is deleted or added, splitting and concatenation are automatically executed so
that the number of elements of a node become m/2 or more or m or less. This allows leaves to
be always maintained on the same level.
- A search starts from the root
- Addition or deletion of data starts from a leaf
Figure 2-3-19 shows a quint-B-tree with elements | 7, 6, 10, 2, 5, 12, 4, 9, 8, 11, 1, 3 |
10 11 12
b. Deleting data
Figure 2-3-20 shows a case where the data "4" is deleted from a B-tree shown in Figure 2-3-19.
If "4" is deleted, the number of deleted elements of a node becomes one and the requirements
for a B-tree cannot be met.
2- 16
Figure 2-3-20 Wrong B-tree
10 11 12
The node form which "4" is deleted is merged with an adjacent node either to the right or the left.
Because the pointers of a parent must also be reorganized, ”6" is moved to a lower order node
and each node can be reorganized, as shown in Figure 2-3-21.
10 11 12
dHeap
A perfect binary tree that has a certain size relationship between a parent node and a child node
is called a heap. A heap is different from a binary search tree in that a heap does not have a
certain size relationship between brothers.
7 8 7 8
6 3 5 3 6 5
Because a heap has the structure of a perfect binary tree, it is a kind of organizable , balanced
tree. In the case of a heap, maximum values (or minimum values) of all data are recorded in a
root. Using this characteristic, data can be sorted by taking out data from a root in a sequential
way.
2- 17
Figure 2-3-23 Sorting data using a heap
1 2
6 6 5 5
4 5 4 2
1 3 2 1 3
3 4
4 4 3 3
3 2 1 2
2.3.5 Hash
A hash is a way of using an array-type data structure. Using a hash, you can directly access
specific data using a key without accessing recorded data one by one.
(1) Converting to a hash address
To convert a key to a hash address (subscript), a hash function is used. Representative hash
functions are
- Division method
- Registration method
- Base conversion method
cDivision method
A key is divided by a certain value (a prime number closest to the number of array elements is
usually used) and the remainder is used as the address (subscript) of a key.
Example
Key: 1234 and the number of array elements: 100
1234 97 (a prime number closest to 100) = 12 70: Address (subscript)
dRegistration method
A key is decomposed according to a certain rule and the total is used as the address (subscript) of
a key. used) and the remainder is used as the address (subscript) of a key.
2- 18
Example
Key: 1234
1234 is decomposed into 12 and 34 and both numbers are totaled.
12 + 34 = 46 : Address (subscript)
eBase conversion method
A key is normally represented in decimal numbers. This key is converted into a radix other than
decimal numbers (tertiary numbers, for example) and the result is used as the address (subscript)
of a key.
Example
Key: 1234
1 x 33 + 2 x 32 + 3 x 31 + 4 x 30 = 27 + 18 + 9 + 4 = 58 : Address (subscript)
• The value of each digit of a tertiary numbers is 3 or smaller. In this case, however, this fact
does not need to be considered.
(2) Synonym
When a key is converted to an address using a hash function, different keys can be converted to
the same address. This is called a synonym (collision) (see Figure 2-3-24). A record that can use
the converted address is called a home record and a record that cannot use it is called a synonym
record.
cSequential method
Using a sequential method, a synonym record is stored in free space that is located close to the
desired address. There is the possibility that synonyms may occur in a chain reaction.
dChain method
Using a chain method, a separate memory is established and synonym records are stored in this
area.
2- 19
In this case, it is necessary to provide a pointer that shows the address where synonym records
are stored.
Terminals are represented by themselves or are written in a type face different from the symbols
of the BNF.
Arithmetic expressions in BNF notation is shown below
2- 20
An EBNF production rule is of the form N::= E, where N is a nonterminal symbol and E is an
extended regular expression.
Like ordinary regular expressions, E may contain `|', `*', and parentheses for grouping but unlike
ordinary regular expressions,
it may contain variable symbols as well as terminal symbols.
Some additional extensions include the use of braces, {E}, or ellipses, E..., to indicate zero or
more repetitions of an item and brackets,
[E], to indicate an optional item.
2- 21
Exercises for No.1 Chapter 2 (Data Structures)
Q1 When storing a two-dimensional array "a" with ten rows and ten columns in continuous
memory space in the direction of rows, what is the address where a [5, 6] is stored? In this
question, the address is represented in decimal numbers.
Address
100
1 1
101
102
1 2
103
Q2 The figure below is a uni-directional list. Tokyo is the head of this list and the pointer
contains addresses of data shown below. Nagoya is the tail of the list and the pointer contains
0. Choose one correct way to insert Shizuoka placed at address 150 between Atami and
Hamamatsu.
Pointer for the head Address Data Pointer
10 10 Tokyo 50
30 Nagoya 0
50 Shin Yokohama 90
70 Hamamatsu 30
90 Atami 70
150 Shizuoka
a. The pointer for Shizuoka to be set to 50 and that for Hamamatsu to be set to 150
b. The pointer for Shizuoka to be set to 70 and that for Atami to be set to 150
c. The pointer for Shizuoka to be set to 90 and that for Hamamatsu to be set to 150
d. The pointer for Shizuoka to be set to 150 and that for Atami to be set to 90
Q3 What is the data structure suitable for the FIFO (first-in first-out) operation?
a. Binary tree b. Queue c. Stack d. Heap
a b c d e
1 3 3 3 6
7 4 4 7 4
3 5 6 1 3
Q5 Figure 2 is the array representation of a binary tree shown in Figure 1. What value should be
put into the space "a"?
2- 22
200 Subscript Value Pointer 1 Pointer 2
1 200 3 2
180 220 2 220 0 0
3 180 5 a
150 190 4 190 0 0
5 150 6 0
130 6 130 0 0
a. 2 b. 3 c. 4 d. 5
Q6 When the element 12 is deleted from the binary search tree shown below, which element
should be moved to the point where the element was deleted to reorganize a binary search
tree?
6
4 8
2 5 7 12
1 3 10 14
9 11 13 15
a. 9 b. 10 c. 13 d. 14
Q7 If two or less than two branches branch off from each node of a tree, such a tree is called a
binary tree. A binary tree consists of one node, a left tree and a right tree. There are three
methods of performing a search on this tree:
(1) Pre-order: A search is performed in the order of a node, a left tree and a right tree.
(2) Mid-order: A search is performed in the order of a left tree, a node and a right tree.
(3) Post-order: A search is performed in the order of a left tree, a right tree and a node.
If a search is performed using the post-order method, which can be output as the value of a node?
b e
c d f g
h i j k
Q8 A binary tree shown below can be represented using an arithmetic expression. Which
expression is correct?
2- 23
A F
B C D E
a. A + B × C + (D + E) ÷ F b. A + B × C - (D + E) ÷ F
c. A + B × C - D + E ÷ F d. A × B + C + (D - E) ÷ F
e. A × B + C - D + E ÷ F
Q9 Regarding storing data using a B-tree, choose one correct comment from the following:
a. Split and merge nodes to allow the hierarchical depth to become the same.
b. Identify the position where data is to be stored by using a certain function and key value.
c. Only sequential access to head data and subsequent data is possible.
d. There are a directory and a member. A member is a sequentially organized file.
Q10 There is a heap with the value of a parent’s node smaller than that of a child’s node. To insert
data into this heap, you can add an element to the backmost part and repeat exchanging a
parent with a child when the element is smaller than a parent. When element 7 is added to
the position * of the next heap, which element comes to the position A?
9
11 14
A
24 25 19 28
29 34
a. 7 b. 9 c. 11 d. 24 e. 25
Q11 A five-digit number (a1 a2 a3 a4 a5) must be stored in an array using the hash method. If the
hash function is defined as mod (a1+a2+a3+a4+a5, 13) and if the five-digit number is to be
stored in an array element located in the position that matches a calculated hash value, in
which position will 54321 be placed in an array shown below? Here, the mod (x, 13) value is
the remainder when x is divided by 13.
Position Array
0
1
2
⋅⋅⋅
11
12
a. 1 b. 2 c. 7 d. 11
Q12 Five data with key values distributed uniformly and randomly in the range of 1 to 1,000,000
must be registered in a hash table of 10 in size. What is the approximate probability that
2- 24
collisions occur? Here, the remainder obtained when a key value is divided by the size of a
hash table is used as a hash value.
a. 0.2 b. 0.5 c. 0.7 d. 0.9
2- 25
Algorithms
3
Chapter Objectives
The basis of programming is algorithm design. In designing the
logical structure of a program, it is important to use the most
appropriate algorithm. Also, in choosing a program from a
library, what algorithm to use is one of the most important
criteria for choosing the most appropriate program.
This chapter describes the basics of algorithm design and
representative algorithms.
1 Understanding the basics of algorithms, i.e. algorithm
definitions, design, relationships with data structures
representative methods, etc
2 Understanding the characteristic and meanings of
representative search, sort, character string processing and
file processing algorithms.
3- 1
Introduction
Using an efficient, easy to understand algorithm enables one to increase the execution speed and
decrease the number of hidden bugs. An algorithm is one of the critical factors that determine the
system performance. Also, the quality of the algorithm is used as criteria for choosing parts from
a library.
This chapter describes the basics of algorithm used for module logic design and the algorithms
used to solve typical problems. Choosing a well-known or generally used algorithm without fully
analyzing given problems should be avoided. An algorithm that is the most appropriate for
characteristics of problems must be chosen.
Evaluating algorithms themselves is also an important task. Data obtained by comparing plural
algorithms on the basis of objective figures will greatly help you choose the most appropriate
algorithm.
In this chapter, you learn the basics of algorithms so that you can design an easy to understand
module.
3- 2
(2) Algorithm and programming
An algorithm and programming are two sides of the same coin. Programming is also describing
data and algorithms in a programming language so that a computer can execute its given tasks.
In general, a program consists of algorithms and data and an algorithm consists of logic and
control.
Programming can be classified into four different types according to how algorithms are viewed.
- Procedural programming
- Functional programming
- Logic programming
- Object programming
The most appropriate type of programming must be chosen with consideration of the
characteristics of a problem.
cProcedural programming
Procedural programming is the most commonly used type of programming. This category
includes the following programming languages, FORTRAN, COBOL, PL/I, Pascal, C, etc.
Characteristic
- A program is divided into modules to make a large, complicated program easy to understand.
Coding is performed for each module
- Structured theorems are introduced to programming (to be explained later)
- Structured figures are used to compile a program
Because procedural programming is procedural (control)-oriented, they are the following
restrictions:
- In addition to a procedure (control), variables (variable names, types, sizes, etc) must be
declared.
- Instructions are executed one by one in a sequential manner (parallel processing cannot be
done).
- Comparisons and calculations must be made to solve a problem.
dFunctional programming
Functional programming is functional-oriented programming. It is used in the field of artificial
intelligence (AI), basic calculation theories and other research tasks. LISP, among others, is a
functional programming language.
Characteristic
- Unlike sequential execution type programming, expressions are built by nesting and they are
replaced with results of calculations to execute a program.
- Recursive calls can be described easily
- The level of affinity with parallel processing is high
- A calculation process or procedure does not need to be considered.
3- 3
eLogic programming
A predicate based on facts and inferences is the base of logic programming. Prolog is an example
of a logic programming language.
Characteristic
- Because facts are described based on the predicate logic, the process of programming is made
easy.
- Inferences and logical calculations can be made easily.
fObject programming
In object programming, a system is considered a group of objects. Languages include Smalltalk,
C++, Java and others.
3- 4
Figure 3-1-1 Data definition and procedure division in a COBOL program
Data definition
Procedure division
3- 5
(2) Relationships between an algorithm and then data structure
The relationships between an algorithm and the data structure can be described as follows:
cArray processing
Take a linear search algorithm (details explained in Section 3.2.1) shown in Figure 3-1-2 for
example.
Figure 3-1-2 The linear search algorithm and the data structure
Start
0 Found
or Yes
Found 1
No
TBL i Found
Search Search
Found unsuccessful successful
End
The linear search is most frequently used to search data. In performing the linear search on data,
data is searched while subscripts in an array are being incremented. The maximum number of
times the search is repeated is the size of an array. That is, if an array structure is used, the
procedure and the number of times of repetition are determined.
dFile processing
Take an algorithm for reading and printing a file shown in Figure 3-1-3 for example. (Details are
explained in section 3.2.5)
3- 6
Figure 3-1-3 Algorithm for processing a file and the data structure
Start <File>
0125 136900
A file is opened
A title is printed
0020 011100
A heading is printed 0010 050100
<Commodity <Amount
code> of sales>
A total is calculated
Editing Edit
Printing Output
A file is closed
End
The process of reading, editing and printing a file is repeated until there is no data in a file.
Because a file must be accessed in each process cycle, this task is executed in the form of a loop.
eList processing
In processing an array structure, data can be searched and updated smoothly but it takes time to
insert or delete data. Because data is arranged in queues, inserting or deleting data is inevitably
accompanied by the shifting of related data backward or forward.
Figure 3-1-4 Inserting data into an array
TBL 15 21 21 30
Shifting
18
Using the list structure, inserting or deleting data is easy. Although data is arranged in an orderly
manner in the list structure, it is arranged so in terms of logic since it does not need to be
physically arranged in sequential order.
Figure 3-1-5 List structure
Data Pointer Data Pointer Data Pointer
section section section section section section
3- 7
In the case of the list structure, data does not need to be shifted as shown in Figure 3-1-6; data
can be inserted or deleted by simply manipulating a pointer.
Figure 3-1-6 Inserting data into the list structure
Data Pointer Data Pointer Data Pointer
section section section section section section
Data Pointer
section section
3- 8
3.2 Various algorithms
An algorithm should be though out to solve each specific problem. If an algorithm that can solve
similar problems is already designed and made available, using such an algorithm will enable
you to create a better algorithm in an efficient manner.
This section describes the representative algorithms that have until now been developed in
relation to each type of problem.
TBL 15
(Match)
Data retrieval is collated with each data in a table. The algorithm is designed such that the search
is successful if there is data that matches data to retrieve and it is unsuccessful if there is no data
that matched data to retrieve.
The search procedure ends when the first successful match occurs. Therefore, this search method
is inappropriate for counting the number of data that matches data to retrieve.
dSentinel search method
3- 9
Figure 3-2-2 Sentinel search method
10
TBL
Figure 3-2-3 shows a comparison of the case where the sentinel search method is used and the
case where it is not used.
Figure 3-2-3 A comparison of the case where the sentinel search method is used and the case
where it is not used
<The case where the sentinel search method is used> <The case where the sentinel search method is not used>
Start Start
End End
3- 10
- (N x 2) times if the exhaustive search method is used
3- 11
Because elements are arranged in ascending or descending order, data smaller than reference
data does not need to be searched if data being searched is larger than reference data. Therefore,
the number of data to search can be halved after the first search - a great advantage in the search
efficiency.
3- 12
Figure 3-2-5 shows a flowchart of the binary search method.
Figure 3-2-5 Flowchart of the binary search method
Binary search method
X is input
or
Search Search
unsuccessful successful
End
<Maximum and average number of times a comparison is made: If the number of elements is N>
3- 13
3.2.2 Sort algorithm
Sorting data is reorganizing data in a specified order. Sorting data in the order of small to large
values is called ascending order sorting, and sorting data vice versa is called descending order
sorting.
If data is sorted or organized in a certain specific order (amounts of sales, commodity codes, etc),
the efficiency of the work of data processing can be increased. Therefore, the sort algorithm is
one of the most commonly used. Using this sort algorithm, one can sort numbers and characters.
This type of sorting is possible because characters are represented as character codes (internal
codes) in a computer.
Figure 3-2-6 shows various sort methods.
Figure 3-2-6 Sort methods
Internal sorting Basic exchange method
3- 14
Figure 3-2-7 shows the algorithm of the basic exchange method.
Figure 3-2-7 Steps of the basic exchange method
Compare
Compare
Exchange
Compare
Exchange
Compare
Compare
Exchange
Compare
Exchange Determined as a maximum value
Compare
Exchange
Compare
Compare
Compare
Exchange Determined
Compare
All these steps are repeated as one cycle.
<Characteristics>
- One of the simplest sort method
- the efficiency is low since data item are unconditionally compared even if they are sorted
correctly If the volume of data is large, the process is time-consuming.
3- 15
<Computational complexity>
Maximum computational complexity: O ( )
Average computational complexity: O ( )
Loop 1
Loop 2
Loop 2
Loop 1
End
3- 16
(2) Basic selection method
In the sort algorithm of the basic selection method, a data item with the smallest (or the largest)
value is first selected from all the data items and it is exchanged with the data item at the head of
an array, then the same routine is repeatedly executed on all the remaining data items. When the
correct data item enters the last position but one, data sorting is completed.
Because this method allows a remaining element with the smallest or largest value to be selected,
it is called the basic selection method.
Figure 3-2-9 shows the algorithm of the basic selection method.
Exchange
Data item with the smallest value is detected
Exchange Compare
Exchange
3- 17
Figure 3-2-10 Flowchart of the basic selection method
Basic selection method
Loop 1
MIN
Loop 2
i
TBL MIN
TBL
MIN
Loop 2
MIN
Loop 1
End
3- 18
Figure 3-2-11 Steps of the basic insertion method
Algorithm for sorting data in the ascending order
Step 1: The first and second elements in a table are compared.
Step 2: If the first element is smaller than the second, nothing is done.
Step 3: If the second element is smaller than the first, the first element is
exchanged with the second. At this point, the first and second
elements are in the correct order.
Step 4: The second and third elements are compared.
Step 5: If the second element is smaller than the third, nothing is done.
Step 6: If the third element is smaller than the second, the second element is
exchanged with the third. Then this element is compared with the
preceding element according to steps 2 and 3. These steps are repeated
till it is placed in the right position.
Step 7: Steps 4, 5 and 6 are repeated until the last element in the table is inserted
into the correct position.
This completes data sorting.
Compare
Compare
Compare Exchange
Exchange
Compare
Compare Exchange
Compare
Compare
Compare Exchange
Compare Exchange
Exchange
Compare
Compare Exchange
Compare
Compare Exchange
<Characteristics>
- One of the simplest sort methods, like the basic exchange method
- Because preceding data items have been sorted, comparison and insertion speeds are fast.
- If the volume of data is large, the process is time-consuming.
3- 19
Figure 3-2-12 shows the flowchart of the basic insertion method.
Figure 3-2-12 Flowchart of the basic insertion method
Basic insertion method
Loop 1
Loop 2
or
Loop 2
Loop 1
End
Loop 3
Loop 1
Loop 2
Loop 3
Loop 1
Loop 2 End
3- 21
(5) Shell sort method
The Shell sort method is an extended version of the basic insert method. Two items of data
located away from each other at a certain interval are picked out of a row of data and sorting is
executed while the picked data items are compared with each other. The interval is called a gap.
The gap is set large at the start of sorting; as sorting proceeds, it is gradually made smaller and
finally set to 1. There are various ways of determining this gap. If the number of data is n, a
simple way of determining the gap is [n/2], [n/4], ...1.
When the gap is finally set to 1, sorting is executed in exactly the same way as the basic insertion
method.
Using the basic insertion method, adjacent items are compared and exchanged and, therefore,
the execution speed is slow. Using the Shell sort method, pieces of data that are away from each
other and located in different positions are quickly exchanged so that data items sorted in wrong
positions can be resorted to correct positions in the earliest stages of the sorting operation. As
sorting proceeds, the gap between data items to be compared is narrowed.
Figure 3-2-14 shows the algorithm of the Shell sort method.
Figure 3-2-14 Steps of the Shell sort method
TBL 10 GAP /2
<Characteristics>
- If part of the data is already sorted, sorting can be completed very quickly.
- A high-speed sorting method that uses the basic insertion method.
3- 22
Figure 3-2-15 shows the algorithm of the Shell sort method.
Figure 3-2-15 Flowchart of the Shell sort method
Shell sort
GAP
Loop 1 Loop 3
GAP
Loop 2
Loop 2
GAP
Loop 1
GAP
End
Loop 3
GAP
Loop 4
TBL j No
TBL j GAP
Yes
TBL j GAP
GAP
Loop 4
GAP
3- 23
(6) Quick sort method
The quick sort method was designed by Hoare. It is presently the fastest sort method using the
recursive call method.
<To sort data in the ascending order>
1. A reference value (pivot or pivotal value) is chosen from the data to be sorted. Although
various values are used as reference values, a median or an intermediate value of three elements
(right, center and left elements) is usually used. We use a median value in the example of sorting
shown below.
2. Data items smaller than the pivot are moved to the left of the pivot while data items larger than
the pivot are moved to the right of it. All the data items are thus divided into two sections.
Pivot
data item
Row of
(Example) 12 11 13
3. A pivot is chosen from each section of data items so that the section is further divided into two
sections.
4. This dividing operation is repeatedly performed until only one element remains.
A method of dividing a large problem into small problems and solving each small problem
individually, like the quick sort method, is called the divide-and-conquer method.
3- 24
In performing step 3 and 4 above, the recursive call method of calling the routine itself is
generally used. This recursive call method is often used to calculate factorials. (See Figure 3-2-
19)
Figure 3-2-19 Algorithm for calculating factorials
f k
No
Yes
f k 1 k k k
End
With regard to computational complexity, if an ideal case in which a pivot that can divide data
into two sections can always be chosen, the number of comparisons will be very close to O
(nlogn). If a maximum (minimum) value in a row of data is always chosen as a pivot, the number
of comparison will become the worst, O (n2). Although computational complexity usually
indicate maximum computational complexity, a case like this may happen in which average
computational complexity becomes an important factor.
After data items are divided into two sections, data items in each section to be subjected to a
recursive processing time is O (logn) if parallel processing is executed.
Figure 3-2-20 shows the algorithm for performing quick sorting with a pivotal set at the
rightmost position of an array.
Specifically, two pointers are used and the routine proceeds from both ends to the center of a row
of data. Pointer moving from the left end to the right is "i" and one moving from the right end to
the left is "j".
3- 25
Figure 3-2-20 Algorithm of the quick sort method
Pivot
3- 26
Figure 3-2-21 shows the flowchart of the quick sort method.
Figure 3-2-21 Algorithm of the quick sort method
Receive arguments
Array to be processed: a
Start position: s e
End position: e
Loop 1
Loop 2
Divide or
Quick sort
Call itself
Loop 2
Quick sort
Call itself Loop 3
or
End
Arguments
Arguments
Loop 3
a i SAVE
a j a i
SAVE a j
Loop 1
a i SAVE
a e a i
SAVE a j
return j
3- 27
(7) Merge sort method
In the algorithm of the merge sort method, all the data items are divided into sections and sorting
is executed in each divided section. The sorted sections are merged into a sorted sequence. (See
Figure 3-2-22). Merge means comparing data items in two sorted sequences from the head and
creating one sequence of sorted data by repeatedly taking out smaller data items in a sequential
manner. If the number of data items is 2n, repeating the merge by n times will complete sorting.
If it is not 2n, some adjustment is necessary.
Figure 3-2-22 Conceptual diagram of merge sort
(Recursion) (Recursion)
Divide Divide Divide
<Characteristics>
- The recursive call and divide-and-conquer methods are used, as in the case of the quick sort
method.
- Because sequences of data items are sequentially accessed and sorted, the merge sort algorithm
is used for external sorting, for example, storing data on magnetic tapes.
<Procedure>
- Data is divided into two sections and each divided section is further subdivided until there is
only one remaining element in a sequence of data items.
- After a sequence of data items is divided, divided sections are sequentially merged.
Figures 3-2-23 and 3-2-24 shows the status of data sequences during merge sort operations and
the flowchart of the merge sort method.
3- 28
Figure 3-2-23 Status of data sequences during merge sort operations
Data sequence
First merge
(the recursion routine returns)
Second merge
(the recursion routine returns)
Third merge
(the return of the recursion routine ends)
<Sorting complete>
8
: Queen
3- 30
Figure 3-2-26 shows the flowchart of the algorithm for solving this question.
Figure 3-2-26 Flowchart of the eight-queen question
Start Queen i, F
Trial loop
F
j + 1 j
Queen , F
x j + y i + j -1
F +z i-j+8 W
W 0
Elements of array
"q" is output
j q i
End
1 x j
y i+j-1
z i-j+8
i 8
Queen i + 1, F F
F 0
0 x j
y i+j-1
z i-j+8
F or 8
Trial loop
Exit
3- 31
3.2.4 Character string processing
Characters are searched, inserted, deleted, exchanged or compressed. This section describes
character string search and compression.
(1) Character string search
To search character strings, the algorithm for searching a certain character string pattern and
locating it in character strings is sued.
cSimple collation
Text is compared character by character sequentially from the head. When a character string on
which a search should be performed is detected, the position where it is located is set as a return
value. In principle, this comparison is repeatedly executed until the first character of a character
string to search matches a character in character strings in text. If there is a match, each
remaining character of the matched character string is compared with each of a character string
to search.
Figure 3-2-27 Image of the search
10 11
TBL
(Unmatch) (Match)
The last position of a character string is set to b.
3- 32
Figure 3-2-28 Flowchart of the simple collation
Start
Loop 1
or
SW ON
Loop 2
or
TBL j k 1 S k
Loop 2
No
Yes
on SW
Loop 1
End
3- 33
Figure 3-2-29 BM method (case 1)
10 11 12 13 14 15
do not match
string
Character
string to
be searched
(Move)
In this case, a character at the tail, and all other characters in the first text portion do not match
any character of a character string to be searched. Therefore, a search point is moved by the
length of a character string to be searched to allow the next search to start from that point.
b. If there is a match with a character at the tail of a character string to be searched
Figure 3-2-30 shows the case in which a character at the tail of a character string to be searched
is compared with the text pattern, and a match is found.
(Match)
Because a character at the tail of a character string matches a character in the text, characters
that precede the matched character must be compared. If all characters match, the value of a
subscript of the first character of that matched text pattern is returned.
c. If there is a match with one character somewhere in a character string but unmatch with a
character at the tail of a character string
In the case shown in Figure 3-2-32 a character string to be searched can simply be moved.
What matters is the distance of movement.
3- 34
Figure 3-2-32 BM method (case 3)
10 11 12 13 14 15
(Match)
By storing this distance of movement in an array, a character string to be searched can be moved
to a correct position.
eKnuth-Morris-Pratt Algorithm
The matching of the pattern is done from left to right until it hits a mismatched. Information
about the matched character(s) from the left of the text to the character preceding the
mismatched character is utilized to shift the pattern to the right of the text by some distance.
The Knuth-Morris-Pratt (KMP) algorithm finds an occurrence and all occurrences of a pattern of
length m within a text in with a complexity of O(m).
3- 35
Figure 3-2-34 Image of the character string compression
10 11 12 13 14 15 16 17 18 19 20 21
TBL A
10 11 12 13 14 15 16
TBL B
Start
Loop 1
inc
Loop 2
TBL A a inc blank
or a inc
inc inc
Loop 2
inc
Loop 3
inc
TBL B b
inc TBL B b 1
TBL A a
TBL B b
a inc a
b 2 b
a 1 a
b 1 b
inc 1
Loop 1
End Loop 3
3- 36
3.2.5 File Processing
Various files are used to perform paperwork tasks. The characteristic of file processing is
processing each record one by one.
A typical file processing algorithm is as follows:
Example
Preparatory processing: Opening files, clearing counters, etc.
Main processing: Calculations, editing, outputting, etc.
End processing: Closing files, etc.
This section describes one algorithm for processing files of the same type and another algorithm
for processing files of different types.
(1) Group control in processing files of the same type
Group control (group total) is to process records with the same key as one lump. In calculating a
total of sales for each customer code (key=customer code) or an average mark for each class
(key=class code), for example, group control is an indispensable processing routine.
Example
Algorithm for reading sales files and printing a detailed listing of sales and total amounts of
sales on each day
cSales file layout
Figure 2-2-36 shows the layout of a sales file.
3- 37
dOutput format (a detailed listing of sales)
Figure 3-2-37 shows the format used to print a detailed listing of sales and total amounts of sales
on each day.
3- 38
Figure 3-2-38 shows the flowchart of the group control.
Figure 3-2-38 Flowchart of the group control
total
Loop 1
Until there is no A date of sales,
commodity codes,
sales record amounts of sales
output area
A date of sales:
The date which is Details are outputted
temporarily saved
Total + subtotal
Exit
Gross total
Sales records
are inputted
Loop 1
End
3- 39
(2) Updating more than one file
If more than one file is compared using the same criteria by matching, all files must be stored in
the sequence of keys, as in the case of the group control.
File processing tasks are as follows:
- Merging files
- Matching files
- Updating files
- Maintaining files
This section describes the task of file updating. File updating is to update master files based on
data contained in transaction files. If a master file is a sequential file, it must be completely re-
created. If a master file can be accessed randomly, a new master file does not need to be created
since records can be retrieved using keys, and updated. Here, we deal with the updating
procedure if a master file is a sequential file.
c1:1 updating
1:1 updating means updating to be executed if each one record in a master file matches each one
record in a transaction file. (See Figure 3-2-39)
Multiple files are read and processing routines are determined by comparing sizes of each key as
follows:
Size of keys
- TR key = MS key Data is updated.
- TR key > MS key Data is copied (data is written into a new master file).
- TR key < MS key Data is added to a new master file (It may be the case where this status is
considered an error and the error routine takes place).
3- 40
Figure 3-2-39 Image of the 1:1 updating
Data is already sorted
according to keys Transac- Old
(each one key in a master tion Sorted according to key values
file matches each one master
record in a transaction file). file file
Updating
New
Error listing
master
file
3- 41
Figure 3-2-40 shows the flowchart of the 1:1 updating.
Figure 3-2-40 Flowchart of the 1:1 updating
Start
Opening a file
Inputting M record
- M record: master record
Inputting T record - T record: transaction record
Loop
Until M and T keys both - M key: master key
become HIGH_VALUE - T key: transaction key
M key: T key
Updating M record
using T record
M key: T key
M record M record
new M record If there is no
new M record matching record in
a master file
Outputting new M record Outputting new M record (error routine)
Inputting T record
Loop
End
d1:n updating
1:n updating is the updating routine used if one record in a master file matches more than one record in
a transaction file. (See Figure 3-2-41)
In principle, multiple files are read, as in the case of the 1:1 updating, and processing routines are
determined by comparing sizes of keys as follows:
Sizes of keys
- TR key = MS key Data is totaled and the results are stored in a work area.
- TR key > MS key Data is updated.
- TR key < MS key Data is added to a new master file (It may be the case where this is
considered an error and the error routine takes place)
3- 42
Figure 3-2-41 Image of the 1:n updating
Data is already sorted
according to key values Transac-
(for one key in a master Old
tion master Sorted according to key values
file, there are multiple transaction
records, the number of which file file
is indicated by n)
Updating
New
master Error listing
file
3- 43
Figure 3-2-42 shows the flowchart of the 1:n updating.
Figure 3-2-42 Flowchart of the 1:n updating
Start
Opening a file
Inputting M record
Inputting T record
Work area
Loop
Until M and T keys both
become HIGH_VALUE
M key: T key
Work + amounts of
T record sales M key: T key
work
Updating M record If there is no
using work matching record in
Inputting T record a master file
M record (error routine)
new M record
Inputting T record
Work area
Inputting M record
Loop
End
3- 44
Figure 3-2-43 How the function D (x, y) works
Y-coordinate
A dot drawn by D (x, Y)
O x X-coordinate
Y-coordinate
y
y
y
y
O x x X-coordinate O x x X-coordinate
The flowchart shown in Figure 3-2-45 is an algorithm for drawing a straight line that connects
two given points in the coordinates, i.e. (x1,y1), (x2,y2) | 0<x1< x2, 0<y1, 0<y2 | . Although
this algorithm can draw straight lines running obliquely in upper or lower right directions by
drawing dots on an integer coordinate, it is designed to allow lines to look like straight lines.
Also, multiply-divide operations are kept to a minimum and add-subtract operations are mostly
used to increase the processing speed.
3- 45
Figure 3-2-45 Flowchart of straight line drawing
Start
Inputting
x1, x2, y1, y2
x2 x1 dx
y1 : y2
1 ST 1 ST
y2 y1 dy y1 y2 dy
dx : dy
D ( x1, y1 )
y1 : y2
dx 2 S
Exchanging x1 with x2
and y1 with y2
Loop 1
x1 x2
(x1, y1)
S dy S
dy 2 S
S: 0
Loop 2
y1 y2
S + dx S
y1 + ST y1 S dx S
S: 0
x1 + 1 x1
D ( x1, y1 ) S + dy S
x1 + ST x1
Loop 1
y1 + 1 y1
D ( x1, y1 )
Loop 2
End
3- 46
(2) Drawing a circle
Figure 3-2-46 shows how a circle is drawn.
y-coordinate 13
12
11
10
9 Center point (6, 8)
8
Radius: 5
7
6
5
4
3
2
1
O 1 2 3 4 5 6 7 8 9 10 11 12 13 x-coordinate
The flowchart in Figure 3-2-47 shows the algorithm for drawing a circle based on the coordinate
(x,y) of a given center point and the radius r. To draw this circle, a trigonometric function that
needs a long execution time is not used.
3- 47
Figure 3-2-47 Flowchart for drawing a circle
Start
Enter x, y, r
r wx, ws
0 wy
Loop 1
wx wy
D (x+wx, y+wy)
D (x+wx, y wy)
D (x wx, y+wy)
D (x wx, y wy)
D (x+wy, y+wx)
D (x+wy, y wx)
D (x wy, y+wx)
D (x wy, y wx)
ws wy 2 1
ws
wy 1 wy
ws : 0
ws (wx 1) 2
ws
wx
Loop 1
End
3.2.7 Graph
The graph that we discuss in this section is one made up of arcs formed by connecting more than
3- 48
one point. Basically an undirected graph is assumed. A directed graph can also be used,
depending on the type of problem to be solved.
The shortest path problem is described here as one of the representative graph problems.
(1) Shortest path problem
As shown in Figure 3-2-48, there are some routes and nodes, and the shortest route that runs
from point A to point H must be found. Because the numbers along each route show a distance,
you can see at once that the thick line is the shortest route.
The graph shown in Figure 3-2-48 that has umbers along each route to show a route distance is
called a weighted graph. Although we can discern the shortest route by sight, an algorithm must
be used to enable a computer to find the shortest route through calculations.
We will here describe three route search methods: the depth-first and the breadth first search
method which assume that the distance of each route is 1, and the Dijkstra's search method which
is a major method for finding the shortest route.
Before the chosen nodes are pushed into the stack, the node picked in step 2
above must be stored in the array. For example, if A is picked and B , C and
E are pushed into the stack, A must be stored in the elements of B, C and E.
After a target node has been put into the stack, nodes are traced one by one
sequentially to find the shortest route. (The same routine is executed in the
case shown in Figure 2-2-53.)
<Results>
A search executed with depth-first search results in the route A-C-G-H shown in figure 3-2-
51. Although the above Figures show the basic scheme of the search execution routine, what
happens during an actual search is more complex. That is, assuming that the shortest route
cannot be found, different routes are repeatedly searched, that is, as the search routine reaches
the step before the step of putting H, shown in Figure 3-2-50, step into the stack, it leaps back
to step 1 and repeats all the steps.
This routine is repeated until the stack becomes empty so that all routes are counted to find the
shortest route.
dBreadth-first search method
Using the breadth-first search method, all possible routes that can lead to a destination are
searched using the queue.
<Procedure> (Figure 3-2-52)
1. A node at the start point is put into the queue.
2. One node is picked from the queue. Nodes adjacent to the picked node are checked and those
that have never before being put into the queue are chosen. The chosen nodes are put into the
queue.
3. The node picked in step2 is stored in the array.
4. Above steps 1, 2 and 3 are repeatedly executed until a target node is reached or the queue
3- 50
becomes empty.
Before a node is put into the queue, the node picked in step 2 is stored
in the array. For example, if A is picked and B, C and E are put into the
queue, A is stored in the elements of B , C and E .
A search executed using the breadth-first search results in the shortest route A-B-F-H shown in
Figure 3-2-53. All nodes are searched one by one, as shown above, while calculations are being
made to find the best route.
eDijkstra's search method
The Dijkstra's search method is a method to which the breadth-first search method is applied.
<Procedures> (Figure 3-2-54)
1. The distance to each node adjacent to the start node is measured and the node located at the
shortest distance is chosen (this chosen node is defined as X).
2. The distance to each node adjacent to X from the start node as well as the distance to nodes
except X from the start node are measured and the node located at the shortest distance is
chosen.
3. Step 2 is repeatedly performed on all nodes until a target node is reached.
4. By adding the distance attached to each node, the shortest route can be established.
3- 51
Figure 3-2-54 Dijkstra search method
B
The distance from the start node to each adjacent node is compared
and the node located at the shortest distance is marked.
D
B F
B
F
E G
* Before a route is cut off,
the distance is considered.
(Both routes are cut off.)
B F
C H
E G
The result becomes the same
as that obtained using the
<The search is completed.> breadth-first search method.
3- 52
3.2.8 Numeric calculation
(1) Solution of algebraic equations
cBisection method
The bisection method is the simplest solution of higher degree equations. A commonly used
higher-degree equation is defined as y = f(x). and various values are assigned to x. The line is
plotted by assigning values into x. the value of x when the line intersects y = 0 (x-axis) becomes
the root of this equation.
Figure 3-2-55 is a graph plotted based on y =f(x).
y-axis
Solution
O x-axis
First
Second
Third
f(x1) . f(x2)<0 shows that there is at least one solution within the [x1,x2] region in which the line
intersects the x-axis. Using the bisection method, this [x1,x2] region is divided into two sections.
To obtain an approximate solution, the routine of dividing a region into two sections is
repeatedly executed to choose a section (indicated by <->) where there is a solution.
Step 1 The point xm that divides a region into two sections is calculated.
Step 2 Each of the divided sections [x1, xm] and [xm, x2] is checked to determine in
which section there is a solution. If f(x1) f(xm)<0, there is a solution in the left
section. If not, there is a solution in the right section.
Step 3 If f(x1) f(xm)<0, xm x2. If not, xm x1.
Step 4 A judgment made -- whether the section length | x1-x2 | is smaller than the
convergence judgment value or not -- is used to determine whether the
approximate solution has been obtained or not. If | x1-x2 | is larger than ,
the routine goes back to step 1 and repeats steps 1 through 4.
3- 53
Figure 3-2-57 shows the flowchart of the algorithm for obtaining the solution of f(x) = 0 using
the bisection method.
Figure 3-2-57 Flowchart of the algorithm for obtaining the solution of f(x) = 0 using the bisection
method
Bisection method
is output
2
End
dNewton's method
Newton's method assumes that an approximate solution of a higher degree equation is already
known. The approximate solution is repeatedly corrected to obtain a true solution. Newton's
method is superior to other methods in that the convergence speed is faster and both real and
imaginary solutions can be obtained.
3- 54
Figure 3-2-58 is a graph plotted using Newton's method.
1
1
2
2
3
3
O x-axis
Solution
3 2 1
Because the equation for a tangential line at point p1 is y-f(x1) = f'(x1)(x-x1), point x2 where a
tangential line intersects x-axis can be obtained using the following equations:
f (x i )
x i +1 = x 1 − (i = 0, 1, 2, ...)
f ′( x i )
3- 55
Figure 3-2-60 shows the flowchart of the algorithm for obtaining the solution of f (x)=0 using
Newton's method.
Figure 3-2-60 Flowchart of the algorithm for obtaining the solution of f(x) = 0 using Newton's method
Newton’s method
is output
No convergence
End
3- 56
cTrapezoidal rule
Figure 3-2-61 shows the basic concept of the trapezoidal rule.
y=f (x)
Area to be calculated
O x0 xn x-axis
y-axis
Errors occur
y=f (x)
Trapezoid
Trapezoid 3
Trapezoid 2
1
O x0 xn x-axis
Figure 3-2-62 shows the procedure for calculating an area enclosed by the curved line y = f(x),a
region along the x-axis and a portion enclosed by the x-axis.
Figure 3-2-62 Procedure for calculating an area using the trapezoidal rule
If an area is calculated using the trapezoidal rule, errors occur with respect to shaded portions, as
shown in Figure 3-2-61, sic a true area is different from a trapezoidal area. To reduce errors, the
number of trapezoids is increased.
3- 57
Figure 3-2-63 shows how an area is divided into trapezoids.
y-axis
1 4
3
0 n
S1 S2 S3 S4 Sn
y=f ( x )
y0 y1 y2 y3 y4 yn
O x0 x1 x2 x3 x4 xn x-axis
a b
h h h h h
Figure 3-2-64 shows the algorithm for calculating an area using the trapezoidal rule based on
Figure 3-2-63.
Figure 3-2-64 Algorithm of the trapezoidal rule
Step 1 The portion where integration takes place, i.e., [a, b] of y = f(x), is divided
into parts, the number of which is defined as n.
Step 2 Points where lines set at regular intervals intersect x-axis are defined as x0,
x1, x2, ..... xn from left to right.
Step 3 The values of functions at above intersection points are defined as y0, y1,
y2, .... yn.
Step 4 Points where lines set at regular intervals intersect curved lines are defined
as p0, p1, p2, .... pn. With x, y and p points connected, a trapezoid is formed.
Step 5 Providing that an area of each trapezoid is S1, S2, S3, ... Sn,
3- 58
Figure 3-2-65 shows the flowchart of the algorithm for calculating an area using a computer and
the trapezoidal rule.
Figure 3-2-65 Flowchart of the approximate area calculation using the trapezoidal rule
Start
S is output
End
dSimpson's method
Using the trapezoidal rule, a curved line is divided at regular intervals and intersection points on
the curved line are connected to form trapezoids. Areas of each trapezoid are total to obtain a
whole area. Although errors can be reduced by increasing the number of trapezoids, it still holds
that the greater the number of trapezoids, the longer it takes to execute totaling. Furthermore,
because the method is based on the scheme wherein an area enclosed by three straight lines and
one curved line is regarded as a trapezoid, there is concern over the accuracy of the
result obtained.
As a solution, Simpson's method is used as shown in Figure 3-2-66. Using this method, a curved
line is approximated to an easy-to-handle parabola to calculate an area.
3- 59
Figure 3-2-66 Area divided using Simpson's method
y-axis
2
3
1
4
0 2n
y=f(x)
S1 S2 Sn
y0 y1 y2 y3 y4 y 2n-2
y 2n
O x0 x1 x2 x3 x4 x 2n-2 x 2n x-axis
a b
h h h h h h
To calculate an area S1 enclosed by y=f(x), x= x0 ,x= x2 and x-axis shown in Figure 3-2-66
using Simpson's method, f(x) is considered a parabola that runs through p0 ,p1 and p2 , and S1 is
approximated as follows:
( y 0 + 4y 1 + y 2 )h
S1 =
3
This method is quite different from the trapezoidal rule in that an area is equally divided into 2n
(equal, even-number division), not into n.
3- 60
Figure 3-2-67 shows the algorithm for calculating an area shown in Figure 3-2-66 using
Simpson's method.
Figure 3-2-67 Algorithm for calculating an area using Simpson's method
Step 1 The section [a, b] of the function y = f(x) where integration takes place is equally
divided into 2n (equal, even-number division). H
Step 2 Points where dividing lines intersect x-axis are defined from the left as x0, x1, x2,
... x2n.
Step 3 Function values at each intersection point are defined as y0, y1, y2, ... y2n.
Step 4 Points where dividing lines intersect a curved line are defined as p0, p1, p2, ... p2n.
Step 5 Three points p2i-2(x2i-s, y2I-2), p2i-1(x2i-1, y2i-1) and p2i (x2i, y2i) in two sections are
approximated to a parabola to calculate an area Si.
y0 4y1 y2
S1
y2 4y3 y4
S2
3- 61
Figure 3-2-68 shows the flowchart of the algorithm for calculating an area using a computer and
the Simpson's method.
Figure 3-2-68 Flowchart of the area approximation calculation using Simpson's method
Simpson’s formula
s a
b
f (x) dx is calculated
(b a) (2 n) h
a x
0 S
0 i
S f
x 2 h x
i 1 i
i : n
S h S
3
S is output
End
3- 62
and C and women are named a, b, and c. the levels of fondness (high to low levels in the order
1,2 and 3) are shown in the table below:
3- 63
Example
If there are five men and women
3- 64
Figure 3-2-69 shows the flowchart of the algorithm of the stable marriage problem.
Figure 3-2-69 Flowchart of the algorithm of the stable marriage problem
1 i Loop 2
M ( j , N 1) 0
i N M ( j , k) l
i j
F ( l, N + 1) : 0
1 k
F ( l, N + 1) w l M ( j , N 1)
Proposal processing
K ( F ( l ) j w) x j F ( l , N 1)
i 1 i
x: j
Loop 1 l M ( j , N 1)
A list of partners j F ( l , N 1)
is outputted
w j
End
0 M ( j , N 1)
1 k
Loop 3
M ( j , k) l
k 1 k
Loop 3
k 1 k
Loop 2
Exit
3- 65
algorithms for obtaining the solutions whose errors or whose possibility of containing mistakes
are very small are used.
(1) Approximation algorithms
Approximation algorithms are use to obtain an approximate solution in those cases where
obtaining a true solution to a problem is impossible or it takes a very long time. Both Newton's
method and Simpson's method described in Section 2.2.8 fall under the approximation algorithm.
[Knapsack problem]
You have n goods which are different in weight and value. You want to sell them in a town but
you cannot put all of them into your knapsack. Find what combination of goods maximizes their
value.
Making the total weight equal to the knapsack weight is not always the best solution. For
example, if there were a sixth item, 9 kg in weight and 150,000 in values, the maximum value
could be obtained by packing this item alone into the knapsack. To find the best solution, all
possible combinations of goods must be considered. As goods increase in number, the number of
combinations becomes enormous, and it takes a great deal of time to find the solution. As a
solution to this, the approximation algorithm can be used.
There are n positive integers a1 ,a2 ,a3 ..... an and b1 ,b2 ,b3 ..... bn and a positive integer c. Find a
combination of x1 ,x2 ,x3 ..... xn that maximizes the total sum of bixi (i=1-n) where xi ={0,1}
and the total
3- 66
sum of aixi (i=1-n) is equal to or smaller than c.
If this formula is considered in analogy to the problem previously discussed, a is the weight of
goods, b is the value of goods, and c is the capacity of the knapsack. x is whether the good is
packed into the knapsack or not. 0 means that the good is not packed and 1 means that the good
is packed. Therefore, the knapsack problem and the solution can be expressed as follows:
a = |2, 3, 5, 7, 8 |
b = |2, 4, 8, 9, 10 |
c = 10
x = | 1,1,1, 0, 0 |
Using this formula, a search is made the 2n times o check all possible combinations of 0,1 in
array x if the approximation algorithm is not used.
Using the approximation algorithm, however, unit values of all goods are first identified. A unit
value means the value per weight and it is given by value bi weight (ai )
Unit values k = | 2/2, 4/3, 8/5, 9/7, 10/8 |
= | 1.00, 1.33, 1.60, 1.28, 1.25 |
After all unit values are identified, goods are packed into the knapsack in the order of high to low
unit values. Because goods cannot be divided, goods that exceed the unused capacity of the
knapsack cannot be packed.
cItem 3 with the highest unit value is packed: Unused capacity = 10 - 5 = 5
dItem 2 with the second highest unit value is packed: Unused capacity = 5 - 35 = 2
eItem 4 with a unit value less than that of item 2 cannot be packed : Unused capacity <the
weight of item 4
fItem 5 with a unit value less than that of item 4 cannot be packed : Unused capacity <the
weight of item 5
gItem 1 with a unit value less than that of item 5 is packed: Unused capacity = 2 - 2 = 0
This way to obtain a solution does necessarily give the best solution. If values are defined as
{2,4,8,11, 10}, the approximation algorithm gives the solution: (item1, item2, item3) = 140,000,
though we already have the best solution: (item2, item 4) = 150,000. The approximation
algorithm, however, is used in many different fields such as a method of quickly obtaining an
approximate value very close to the best solution.
Figure 3-2-70 shows the flowchart of the algorithm for solving the knapsack problem.
3- 67
Figure 3-2-70 Flowchart of the algorithm for solving the knapsack problem
[General algorithm] [Approximation algorithm]
Start Start
Loop 1
Initialize Array x
i , , ,N
0 MAX
b(i) a(i) k(i)
0 T
Loop 1
Loop 1
N
T 2
Initialize Array x
Using T as a binary number, each
digit is substituted into array w 0 MAX
0 J c J
Loop 2 Loop 2
i , , ,N All elements in
array k become 0
or J = 0
J a(i) w(i)
J
Subscript for the maximum
value in array k i
Loop 2
0 k(i)
J : c
a(i): J
0 K
x(i)
Loop 3
i , , ,N
J a(i) J
b(i) w(i)
MAX b(i) MAX
Loop 3
Loop 2
: MAX
Array x, MAX are outputted
MAX
End
Array W Array x
T + 1 T
Loop 1
End
3- 68
(2) Probability algorithm
The probability algorithm uses a probabilistic approach to find a solution using random numbers.
A probabilistic approach is one in which the appropriateness of a solution is examined in terms
of probability, or that a solution is found based on the probability of occurrence of a certain event.
This section describes the primarity test problem as an algorithm for examining the
appropriateness of a solution in terms of probability, and the case of obtaining a circular
consistent as an algorithm for finding a solution based on the probability of occurrence of a
certain event.
cPrimarily test problem
Primarity test problem is a process of checking given N (= 2s d + 1, d is an odd number) and
determining whether it is a prime number of not. To solve the primarity test problem, give N is
divided using integers 2, 3,....... , and it is considered a prime number if it is not divisible
without a remainder by any of the integer. Although a correct solution can be obtained using this
approach, a much longer time period is required to arrive at a solution if the value of N is large.
As a solution, Rabin's algorithm, designed with the following theorem is used.
[Theorem of prime numbers]
If N (= 2s d + 1, d is an odd number) is a prime number, either of two conditions shown below
stand for the arbitrarily chosen positive integer, a(>1)
- ad = 1 (mod N)
- a2kd = -1(mod N) where 0<k<S-1
If the arbitrarily chosen integer, a, does not meet the above conditions, N is considered a
composite number, not a prime number. The probability that the arbitrarily chosen integer, a, for
a composite number N can meet the above conditions is equal to or lower than 1/4. Therefore, if
the arbitrarily chose integer, a, meets the above conditions, the probability of the correctness of
the judgement that N is a prime number is equal to or higher than 3/4.
If this algorithm is used, the possibility remains that the solution given by the algorithm is
incorrect. This type of algorithm is called the probability algorithm with bounded errors. For the
above particular example, since the probability that errors will occur is sufficiently low, the
solution given by the algorithm should be considered dependable. In addition to the probability
algorithm with bounded errors, the probability algorithm with no errors is sometimes used.
Although this algorithm can theoretically assure the correctness of a given solution, it sometimes
takes too long to execute the algorithm process, or it ends up giving no definite solution.
A probability algorithm with no errors is the probabilistic quick sort algorithm. This algorithm
designed to improve efficiency by randomly rearranging input data using random numbers.
3- 69
dHow to find a circular constant
Figure 3-2-71 shows a circle of 1 in radius. The area enclosed by the axes and arc is a fourth of
that of the complete circle having a radius of 1. Therefore, it is /4 (= 1 x 1 x /4). On the other
hand, the area of a square enclosed by four lines, x = 0, x = 1, y = 0, and y = 1 is 1. If points on
this square are designated in a random manner, the probability that these designated points is
inside the circle is /4.
In the flowchart shown in Figure 3-2-71, 1,000 points are generated using the function RAN( )
that can generate random numbers between and 1. Whether generated points are inside the circle
or not is determining by measuring the straight distance from (0,0) to each point. To simplify the
calculation, the root calculation is omitted. In the case of the example shown in Figure 3-2-71, it
is judged that (xl, yl) is inside if (xl2 + yl2) < 1 and that (x2,y2) is outside if ( x22 + y22 ) > 1.
1
( 2, 2) 0 i ct
2
Loop 1
i 1000
( 1, 1)
1
RAN() x
O 1 2 1 x-axis RAN() y
x x y y
w
w:1
ct 1 ct
i 1 i
Loop 1
ct 4 i P
End
Because a circular constant obtained in this way sometimes contains errors resulting from the
characteristics inherent in methods used to generate random numbers, it is generally used in the
representation containing a standard error (solution + standard errors).
An algorithm like this one, that uses random numbers to solve mathematical problems, is called
3- 70
the Monte Carlo method.
To use a genetic algorithm, you must encode solutions to your problem in a structure that can be
stored in the computer. This object is a genome (or chromosome). The genetic algorithm creates
a population of genomes then applies crossover and mutation to the individuals in the population
to generate new individuals.
It uses various selection criteria so that it picks the best individuals for mating (and subsequent
crossover).
Your objective function determines how 'good' each individual is.
Algorithm is started with a set of solutions (represented by chromosomes) called population.
Solutions from one population are taken and used to form a new population. This is motivated by
a hope, that the new population will be better than the old one. Solutions which are selected to
form new solutions (offspring) are selected according to their fitness - the more suitable they are
the more chances they have to reproduce.
This is repeated until some condition (for example number of populations or improvement of the
3- 71
best solution) is satisfied.
You can use any representation for the individual genomes in the genetic algorithm. Holland
worked primarily with strings of bits, but you can use arrays, trees, lists, or any other object. But
you must define genetic operators (initialization, mutation, crossover, comparison) for any
representation that you decide to use.
Genetic Algorithm
1. [Start] Generate random population of n chromosomes (suitable solutions for the
problem)
2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
3. [New population] Create a new population by repeating following steps until the new
population is complete
1. [Selection] Select two parent chromosomes from a population according to their
fitness (the better fitness, the bigger chance to be selected)
2. [Crossover] With a crossover probability cross over the parents to form a new
offspring (children). If no crossover was performed, offspring is an exact copy of
parents.
3. [Mutation] With a mutation probability mutate new offspring at each locus
(position in chromosome).
4. [Accepting] Place new offspring in a new population
4. [Replace] Use new generated population for a further run of algorithm
5. [Test] If the end condition is satisfied, stop, and return the best solution in current
population
6. [Loop] Go to step 2
3- 72
Define the representation
- minimal complete representation
Define the operators
- initialization, crossover, mutation
3- 73
Mutation
These are some sample tree mutation operators. You can use more than one operator during an
evolution. The mutation operator introduces a certain amount of randomness to the search. It can
help the search find solutions that crossover alone might not encounter.
3- 74
Tree cross over operations
3- 75
Mutation operator
These are some sample list mutation operators. Notice that lists may be fixed or variable length.
Also common are order-based lists in which the sequence is important and nodes cannot be
duplicated during the genetic operations. You can use more than one operator during an
evolution.
The mutation operator introduces a certain amount of randomness to the search. It can help the
search find solutions that crossover alone might not encounter.
List crossover operators
Typically crossover is defined so that two individuals (the parents) combine to produce two
more individuals (the children). But you can define asexual crossover or single-child crossover
as well. The primary purpose of the crossover operator is to get genetic material from the
previous generation to the subsequent generation.
3- 76
Notice that lists may be fixed or variable length. Also common are order-based lists in which the
sequence is important and nodes cannot be duplicated during the genetic operations. You can use
more than one operator during an evolution.
The mutation operator introduces a certain amount of randomness to the search. It can help the
search find solutions that crossover alone might not encounter.
Array mutation operators
The lists may be fixed or variable length. Also common are order-based lists in which the
sequence is important and nodes cannot be duplicated during the genetic operations. You can use
more than one operator during an evolution.
The mutation operator introduces a certain amount of randomness to the search. It can help the
search find solutions that crossover alone might not encounter.
3- 77
Array crossover operator
The crossover is normally defined such that two individuals (the parents) combine to produce
two more individuals (the children). But you can define asexual crossover or single-child
crossover as well. The primary purpose of the crossover operator is to get genetic material from
the previous generation to the subsequent generation.
Notice that arrays may be fixed or variable length. They may also be 2 or 3 dimensional (or
more). Also common are order-based arrays in which the sequence is important and nodes
cannot be duplicated during the genetic operations. You can use more than one operator during
an evolution.
Two of the most common genetic algorithm implementations are 'simple' and 'steady state'. The
simple genetic algorithm is described by Goldberg in his 1989 book, Genetic Algorithms in
3- 78
Search and Optimization. It is a generational algorithm in which the entire population is replaced
each generation.
The steady state genetic algorithm is used by the Genitor program. In this algorithm, only a few
individuals are replaced each 'generation'. This type of replacement is often referred to as
overlapping populations.
Scaling schemes
rank (no scaling)
linear scaling ("fitness")
sigma truncation scaling
sharing (similarity scaling)
Often the objective scores must be transformed in order to help the genetic algorithm maintain
diversity or differentiate between very similar individuals. The transformation from raw
objective scores to scaled fitness scores is called scaling.
There are many different scaling algorithms. Some of the most common are linear (fitness
proportionate) scaling, sigma truncation scaling, and sharing. Linear scaling transforms the
objective score based on a linear relationship using the maximum and minimum scores in the
population as the transformation metric. Sigma truncation scaling uses the population's standard
deviation to do a similar transformation, but it truncates to zero the poor performers. Sharing
degrades the score of individuals that are similar to other individuals in the population.
Replacement schemes
replace worst
replace best
replace parent
replace random
replace most similar
Replacement schemes are used by genetic algorithms with overlapping populations to determine
how the new individuals will be assimilated into the population. Replace-worst and replace most-
similar are the only really useful replacement schemes. Sometimes replace-parent can be
effective, but usually when the parents are similar to the offspring and this is just replace-most-
similar.
Selection schemes
Rank selection
roulette wheel selection
tournament selection
uniform stochastic sampling
similarity based selection
3- 79
The selection method determines how individuals are chosen for mating. If you use a selection
method that picks only the best individual, then the population will quickly converge to that
individual. So the selector should be biased toward better individuals, but should also pick some
that aren't quite as good (but hopefully have some good genetic material in them).
Some of the more common methods include roulette wheel selection (the likelihood of picking
an individual is proportional to the individual's score), tournament selection (a number of
individuals are picked using roulette wheel selection, then the best of these is (are) chosen for
mating), and rank selection (pick the best individual every time). Threshold selection can also be
effective.
Premature convergence
Often the crossover operator and selection method are too effective and they end up driving the
genetic algorithm to create a population of individuals that are almost exactly the same. When
the population consists of similar individuals, the likelihood of finding new solutions typically
decreases.
On one hand, you want the genetic algorithm to find good individuals, but on the other you want
it to maintain diversity. Two of the most common methods for maintaining diversity are DeJong-
style crowding (named after Kenneth DeJong whose PhD thesis first explored the issue) and
Goldberg-style fitness scaling.
DeJong-style crowding is basically the same thing as replace-most-similar replacement scheme.
When new offspring are created, they replace the individuals in the population that are most
similar to them.
Fitness scaling derates the objective score of individuals that are less unique than others in the
population. By derating the scores of similar individuals, less similar individuals are more likely
to be selected for mating.
Areas of application
The following shows the different areas where genetic algorithms are applied.
scheduling/planning
packing (2D and 3D)
music generation
plant growth
catalog search
structural topology
assembly sequencing
Conclusion
In general, genetic algorithms are better than gradient search methods if your search space has
3- 80
many local optima. Since the genetic algorithm traverses the search space using the genotype
rather than the phenotype, it is less likely to get stuck on a local high or low.
Run-length encoding (RLE) is a very simple form of data compression encoding. It is based on
simple principle of encoding data. This principle is to every stream which is formed of the same
data values (repeating values are called a run) i.e sequence of repeated data values is replaced
with count number and a single value. This intuitive principle works best on certain data types in
which sequences of repeated data values can be noticed; RLE is usually applied to the files that a
contain large number of consecutive occurrences of the same byte pattern
RLE may be used on any kind of data regardless of its content, but data which is being
compressed by RLE determines how good compression ratio will be achieved. So RLE is used
on text files which contain multiple spaces for indention and formatting paragraphs, tables and
charts. Digitized signals also consist of unchanged streams so such signals can also be
compressed by RLE. A good example of such signal is monochrome images the run of characters
is replaced with the number of the same characters and a single character.
Example:
before: R T A A A A S D E E E E E
after RLE compression: R T *4A S D *5E
The Arithmetic coding with accurate probability of events gives an optimal compression.
Algorithm
With given probabilities of events, the algorithm works in these three steps.
1. The coder starts with a “current interval” [H, L) set to [0,1).
2. For each events int the input filed/file, the coder performs an (a) and (b) step.
3- 81
a. the coder subdivides current interval into subintervals, one for each event.
b. The size of a subinterval is proportion to the probability that the event will be the
next event in the field/file. the code selects the subinterval corresponding to the
event that actually occurs next and makes it the new current interval
3. The output is the last current interval. Better to say, the output are so many bits that
accurately distinguish the last current interval form all other final intervals.
The size of final interval is equal to the product of the probabilities of all individual events that
occurs in the input filed/file.
The description of algorithm in pseudocode for implementation
set Low to 0
set High to 1
while there are input symbols do
take a symbol
CodeRange = High – Low
High = Low + CodeRange * HighRange(symbol)
Low = Low + CodeRange * Low Range(symbol)
end of while
output Low
The low and high parts of subintervals are subintervals of interval [0,1]. The size of each
subinterval depends on the probability that this symbol occurs in the input field/file.
Example 1.
Table 1.
a1 2/3
b1 1/3
a2 1
3- 82
b2 1
a3 3/5
b3 2/5
The input field is given by these symbols: b1a2b3. The coding is given in table 2.
Action Subinterval
Begin [0,1)
The final interval is [23/30, 5/6). The size of this event is 1/15. That is the product of the sizes of
probabilities events in the input filed
3- 83
Example 2.
The message to be encoded is “ARITHMETIC”. There are ten symbols in the message. The
probability distribution is given in the table 3.
Symbol Subinterval
A 1/10
C 1/10
E 1/10
H 1/10
I 2/10
M 1/10
R 1/10
T 2/10
Each character is assigned the portion of the starting interval [0,1). The size of interval
corresponds to symbol’s probability of appearance.
Subinterval
Symbol
A 0,00 – 0,10
C 0,10 – 0,20
E 0,20 – 0,30
H 0,30 – 0,40
I 0,40 – 0,60
M 0,60 – 0,70
R 0,70 – 0,80
T 0,80 – 1,00
3- 84
The coding is performed in the table 5. Note, the most significant portion of a coded message
belongs to the first symbol to be encoded. In this case, the first symbol is “A” which owns range
[0, 0.1).
0,0 1,0
A 0,0 0,1
R 0,07 0,08
I 0,074 0,076
T 0,0756 0,076
H 0,07572 0,07576
M 0,07596 0,07600
E 0,075968 0,075972
T 0,0759712 0,075972
I 0,07597152 0,07597168
C 0,075971536 0,075971552
Huffman's approach uses a binary tree to convert the individual characters to codes. The idea is
3- 85
simple. Consider a binary tree in which the data items reside only in the leaves (or external
nodes). The path from the root of the tree to a given leaf can be taken as the binary code for the
data in that leaf by recording descent to the left as a 0, and descent to the right as 1.
3- 86
present. Even when working with a favorable format (an image), the compression ratios achieved
by run length encoding are very limited.
Entropy coding is probably harder than Huffman to implement. A nice feature of entropy
encoding is that the dictionary used to encode the data does not need to be stored in the output
file, thereby saving space. Unfortunately, this type of compression is limited by the size of its
data dictionary. It becomes impractical to use entropy encoding if the dictionary’s size is rather
large (the largest practical size is approximately 256). A well known use of entropy encoding is
the Lempel/Ziv/Welch algorithm, which is the basis of the Graphics Interchange Format (GIF)
image compression algorithm.
Area coding is an improved form of run length coding. It is primarily used to compress images,
since it’s algorithm (group the image into rectangular regions containing similar or identical
image characteristics) naturally represents the two dimensions of an image. Although area
coding can achieve high compression ratios, it is non-linear and therefore cannot be implemented
at a hardware level. For that reason, area coding is not highly competitive with the previously
discussed image compression algorithms.
JPEG Compression
The JPEG standard defines four variations for compression of images. These are known as
follows Sequential DCT based mode: This is the JPEG baseline format.
Sequential lossless mode: This format is defined for applications in which it would be desirable
to have no image detail lost in the compression process. This is not widely used as the
compression statistics for this method is modest compared to the other styles.
Progressive DCT based mode: This format is very similar to the Baseline mode, however instead
of processing information in one scan of the image, this mode processes in a serious of scans,
each one better defining the image from the last scan that was processed.
Hierarchical mode: This format allows a number of different resolution images to be held within
one file. This means that only one image file needs to be made for a number of resolutions it
could be viewed at. Again it uses more than one scan to define the image, the decoder simply
uses scans in order until it has reached the resolution it requires.
JPEG Baseline is the defacto standard that is used, and is the version for which this project is
based. The reasons for this are that is the simplest algorithm as well as being the most widely
supported because the JPEG standard specifies that all JPEG decoders MUST support the
baseline version, even if it uses some of the other features within the JPEG standard.
Entropy Coding
Entropy Coding is a form of compression that relies on developing "code" words in a library for
the input values or "symbols".
3- 87
A very simple implementation of entropy coding would be to describe four kinds of weather by a
2 bit binary code as follows.
Clear 00
Cloudy 01
Rainy 10
Snowy 11
This would allow a coding algorithm to describe the weather with two bits of information per
sample. This is a "fixed length" code. Fixed length codes are best applicable to applications
where each of the symbols are equally likely, that is to say where each of the weather types is
25% likely in the above example.
In most real world applications this is not the case, each of the symbols actually have different
probabilities of occurring. This leads to the use of "variable length" codes. If an event is most
likely to happen more often than the other events, then it makes sense to use a code word that is
actually shorter, or requires less information, than the other event codes.
Using the weather example again, say that each event has a probability as follows, we can
generate variable length codes
Clear 50 0
Cloudy 25 10
Now we can determine the average bit length for a code per symbol.
As can be seen, an average of 1.75 bit/symbol is more efficient then the 2 bits/symbol that the
fixed length code produced.
The codes produced for this example are found using Huffman coding, which is one of the two
options that the JPEG standard allows for. The other is known as Arithmetic Coding. This
project uses Huffman Coding for the following reasons.
3- 88
Huffman Coding is simpler.
The compressed digital video encoder scans subsections within each frame, called macro blocks,
and identifies which ones will not change position from one frame to the next. The encoder also
identifies predictor macro blocks while noting their position and direction of motion. Only the
relatively small difference, called the motion compensated residual, between each predictor
block and the affected current block is transmitted to the receiver. The receiver/decoder stores
the information that does not change from frame to frame it's buffer memory and uses it
periodically to fill in the blanks, so to speak.
A mathematical algorithm called the Discrete Cosine Transform (DCT) reorganizes the residual
difference between frames from a spatial domain into an equivalent series of coefficient numbers
in a frequency domain that can be more quickly transmitted. Quantization coding converts these
sets of coefficient numbers into even more compact representative numbers. The encoder refers
to an internal index or code book of possible representative numbers from which it selects the
code word that best matches each set of coefficients. Quantization coding also rounds off all
coefficient values, within a certain range of limits, to the same value. Although this results in an
approximation of the original signal, it is close enough to the original to be acceptable for most
viewing applications.
The MPEG video compression algorithm employs two basic techniques: block-based motion
compensation for the reduction of the temporal redundancy, and transform domain (DCT) coding
for the reduction of spatial redundancy. The motion compensation technique is applied both in
the forward (causal) and backward (non-causal) direction. The remaining signal (prediction
error) is coded using the transform-based technique. The motion predictors, called motion
vectors, are transmitted together with the spatial information.
The MPEG-2 standard uses the same set of algorithms as MPEG-1, and has an additional support
for interlaced video sources and scalability options. Although there are minor differences in the
syntax, the MPEG-2 standard is conceptually a super-set of MPEG-1, and therefore we will
3- 89
describe both as the MPEG standard when the distinction is not necessary.
Motion-compensated prediction assumes that the current picture can be locally modeled as a
translation of the pictures of some previous time. In the MPEG standard, each picture is divided
into blocks of 16 x 16 pixels, called a macroblock. Each macroblock is predicted from the
previous or future frame, by estimating the amount of the motion in the macroblock during the
frame time interval. The MPEG syntax specifies how to represent the motion information for
each macroblock
MPEG-2
One of the biggest motivations for creating the new MPEG-2 standard was to introduce the
support for interlaced video sources. Since the MPEG-1 standard was targeted at the bit rate of
around 1.5 Mbits/s, it was assumed that the source video signal will be digitized at around 352 x
240 for 60 Hz systems (e.g., in U.S.) and 352 x 288 for 50 Hz systems (e.g., in Europe). The
standard video signals carry twice the scan lines as the above sampling rates, with an interlaced
scanning order. Therefore, the simplest way of creating a half-size digital picture was simply
sampling only one field from each frame. The other field was always discarded. Since only one
field from every frame is used, these sampled fields form a progressively-scanned video
sequence. The MPEG-1 therefore addressed the coding parameters and algorithms for
progressively-scanned sequences only. However, it should be noted that the syntax of the
MPEG-1 standard does not constrain the bit rate or the picture size to any such values.
As MPEG-2 is targeted for coding broadcast-quality video signals, it is necessary to digitize the
source video at its full bandwidth, resulting in both even and odd field pictures in the sequence.
Since these two fields are separated by a time interval, coding the sequence using the MPEG-1
algorithm does not produce good quality pictures as MPEG-1 assumes that there is no time
difference between successive lines in the picture. The MPEG-2 standard provides a means of
coding interlaced pictures by including two field-based coding techniques: field-based prediction
and field-based DCT.
In MPEG-2, the term picture refers to either a frame or a field. Therefore, a coded representation
of a picture may be reconstructed to a frame or a field. During the encoding process, the encoder
has a choice of coding a frame as one frame picture or two field pictures. If the encoder decides
to code the frame as field pictures, each field is coded independently of the other, i.e., two fields
are coded as if they were two different pictures, each with one-half the vertical size of a frame.
In frame pictures, each macroblock can be predicted (using motion compensation) on a frame or
field basis. The frame-based prediction uses one motion vector per direction (forward or
backward) to describe the motion relative to the reference frame. In contrast, field-based
prediction uses two motion vectors, one from an even field and the other from an odd field.
Therefore, there can be up to four vectors (two per direction, and forward and backward
directions) per macroblock. In field pictures, the prediction is always field-based, but the
prediction may be relative to either an even or odd reference field.
3- 90
3.2.13 Memory management algorithms
Fixed Partitioning
• Partition main memory into a set of non overlapping regions called partitions
• any process whose size is less than or equal to a partition size can be loaded into the
partition
• if all partitions are occupied, the operating system can swap a process out of a partition
• a program may be too large to fit in a partition. The programmer must then design the
program with overlays
• when the module needed is not present the user program must load that module
into the program’s partition, overlaying whatever program or data are there
• Main memory use is inefficient. Any program, no matter how small, occupies an entire
partition. This is called internal fragmentation.
• Equal-size partitions was used in early IBM’s OS/MFT (Multiprogramming with a Fixed
number of Tasks)
• Equal-size partitions
• If all partitions are occupied by blocked processes, choose one process to swap
out to make room for the new process
• assign each process to the smallest partition within which it will fit
• Problem: some queues will be empty if no processes within a size range is present
3- 91
• Unequal-size partitions: use of a single queue
• When its time to load a process into main memory the smallest available partition
that will hold the process is selected
• Eventually holes are formed in main memory. This is called external fragmentation
• Must use compaction to shift processes so they are contiguous and all free memory is in
one block
• A hole of 64K is left after loading 3 processes: not enough room for another process
• Eventually each process is blocked. The OS swaps out process 2 to bring in process 4
• Eventually each process is blocked. The OS swaps out process 1 to bring in again process
2 and another hole of 96K is created...
• Possible algorithms:
3- 92
• Next-fit often leads to allocation of the largest block at the end of memory
• First-fit favors allocation near the beginning: tends to create less fragmentation then
Next-fit
• Best-fit searches for smallest block: the fragment left behind is small as possible
• main memory quickly forms holes too small to hold any process: compaction
generally needs to be done more often
Replacement Algorithm
• When all processes in main memory are blocked, the OS must choose which process to
replace
• We will discuss later such algorithms for memory management schemes using
virtual memory
Buddy System
• Memory blocks are available in size of 2K where L <= K <= U and where
• Else, split this block into two buddies, each of size 2U-1
• This process is repeated until the smallest block greater or equal to S is generated
3- 93
• The OS maintains several lists of holes
• whenever a pair of buddies in the i-list occur, they are removed from that list and
coalesced into a single hole in the (i+1)-list
• Presented with a request for an allocation of size k such that 2i-1 < k <= 2i:
• Mostly efficient when the size M of memory used by the Buddy System is a power of 2
3- 94
assembly language) represents a one-to-one transliteration of the object machine code. Some
compilers generate assembly code which is then assembled into machine code by an assembler.
A loader is a translator whose source and object languages are machine language. The source
language programs contain tables of data specifying points in the program which must be
modified if the program is to be executed. A link editor takes collections of executable programs
and links them together for actual execution. A preprocessor is a translator whose source
language is an extended form of some high-level language and whose object language is the
standard form of the high-level language.
3- 95
The main task of a compiler is to map programs in a give source language into a target language.
The source language is a programming language and the target language is machine code.
a start symbol
Language
3- 96
phase is a character stream. The output is a stream of tokens. Regular expressions are used to
define the tokens recognized by a scanner (or lexical analyzer). The scanner is implemented as a
finite state machine.
Syntax analysis
The parser groups tokens into syntactical units. The output of the parser is a parse tree
representation of the program. Context-free grammars are used to define the program structure
recognized by a parser. The parser is implemented as a push-down automaton.
Type checking
The contextual analysis phase analyzes the parse tree for context-sensitive information often
called the static semantics. The output of the contextual analysis phase is an annotated parse tree.
Attribute grammars are used to describe the static semantics of a program.
Optimizer
The optimizer applies semantics preserving transformation to the annotated parse tree to simplify
the structure of the tree and to facilitate the generation of more efficient code.
Code generation
The code generator transforms the simplified annotated parse tree into object code using rules
which denote the semantics of the source language.
3- 97
Language evaluation criteria
Readability
Simplicity of instructions
Orthogonality of instructions
Control statements
Data Types and Structures
Syntactic Issues -- identifier rules, reserved or special words, form and meaning
Writability
Flexibility and availability of control structures, data types
Simplicity and Orthogonality
Support for Abstraction
Expressitivity
Reliability
Readability and Writability
Type Checking
Exception Handling
Aliasing
Cost
Training/Learning Curve
Time to write programs
Compilation Speed/Efficiency
Execution Speed/Efficiency
Maintenance
Tradeoffs
Readability vs. Flexibility
Cost vs. Expressitivity
Type Checking vs. Abstraction and Flexibility
Design effects
1) Computer Architecture - usually will concentrate on Von Neumann architectures
2) Other architectures such as parallel processing (MIMD or SIMD) or pipelining might require
very different languages
3) Program Methodologies
Procedural vs. Functional vs. Logical vs. Object-oriented
3- 98
Implementation
1. Compilation
- Translate high-level program to machine code
- Slow translation
- Fast execution
2. Pure interpretation
- No translation
- Slow execution
- Becoming rare
3- 99
BNF Grammar
Mathematically, a BNF Grammar is given as G={alphabet, rules, <start>}
alphabet -- those symbols used in the rules (both terminals and non-terminals)
rules -- map from a non-terminal to other elements in the alphabet
<start> -- a non-terminal which must be on at least 1 rule’s left hand side
Example of grammar rules
Notice the use of both terminals and non-terminals on the right side
Parse Trees
• In a strict language, the arguments to a function are always evaluated before it is invoked.
3-100
As a result, if the evaluation of an expression exp does not terminate properly (for
example, because it generates a run-time error or enters an infinite loop), then neither will
an expression of the form f(exp). ML and Scheme are both examples of this.
• In a non-strict language, the arguments to a function are not evaluated until their values
are actually required. For example, evaluating an expression of the form f(exp) may still
terminate properly, even if evaluation of exp would not, if the value of the parameter is
not used in the body of f. Miranda and Haskell are examples of this approach.
The basic property of a declarative programming language is that a program is a theory in some
suitable logic. This property immediately gives a precise meaning to programs written in the
language. From a programmers point of the basic property is that programming is lifted to a
higher level of abstraction. At this higher level of abstraction the programmer can concentrate on
stating what is to be computed, not necessarily how it is to be computed. In Kowalski's terms
where algorithm = logic + control, the programmer gives the logic but not necessarily the
control.
Declarative languages differ from imperative languages in that they are based on an abstract
formalism, thus divorcing their semantics from the machine on which they are run. The
statements in such a language are declarative since they can be understood without reference to
machine level terms, such as side-effects. For this reason, programs in a declarative language can
act as a specification, since they can be regarded as the formal description of a problem. Other
advantages of such languages are that programs can be developed and tested bit by bit, and that
they can be systematically synthesized or transformed.
LISP [MaCarthy1965a], arguably the first implemented declarative language, was based on the
abstract formalism of the lambda calculus.
Logic Programming
For practical applications there exists one logic programming in use: Prolog. Prolog is used for a
wide variety of applications in artificial intelligence, knowledge based systems, and natural
language processing. Programs are evaluated by proving queries with respect to the given
program.
From a programming point of view Prolog provides two features not present in functional
3-101
languages, built-in search and the ability to compute with partial information. This is in contrast
to functional languages where computations always are directed, require all arguments to be
known and give exactly one answer
Accordingly, Prolog and most other logic programming languages only provide declarative
programming in the weak sense where the programmer also need to provide some control
information to get an efficient program from the declarative problem description. The method
used by many Prolog programmers is rather ad hoc: First the problem is expressed in a nice
declarative fashion as a number of predicate definitions. Then the program is tested and found
slow. To remedy the problem the original program is rewritten by adding control information
(cuts) as annotations in the original code and doing some other changes like changing the order
of arguments to predicates. The resulting program is likely to be quite different from the original
one -- and less declarative
Logical programming characteristics
In logical programming, rules are in consequence form (spot is a dog if spot is a poodle)
dog(x) if poodle(x)
mortal(x) if man(x)
Given a series of propositions, predicates and rules in clause form, resolution can prove things
are true by contradiction
Introduce the negation of what you are trying to prove
Show that with the negation, a contradiction arises with what we already know to be true
While Prolog uses predicate calculus form, it does not actually use resolution, instead it uses
backward chaining:
We know A, B, C and E are true
3-102
A and B and C --> D
D and E --> F
G and H --> F
Want to prove F, how? Backward chaining
To prove F: prove G and H, or D and E. We know E, so now prove D by proving A...
Unification
Logic programming
Prolog
Uses of logic
3-103
Expert Systems - particularly those dealing with T/F worlds (math, simple logic)
Natural Language Processing and logic-based semantic networks
Educational/Tutorial systems - teaching logic
Functional Programming
The variables and memory usage is less visible making programming easier (at least in some
situations)
It has simpler syntactic structures to deal with (since everything is a list)
The concurrency is easier to design and implement
The interpreted nature makes large systems easier to build and exploits recursion as much as
possible, more so than imperative languages
LISP
Mathematical functions
3-104
LISP
A typeless language
Data Structures: atoms and lists
Atom - any literal (char, string, number)
List - nil or ( x ) where x is an atom, a series of atoms, or a list, or any combination of these
Example of a list (A (B C D) E F)
List structures make use of pointers where each item has an info field and a next field where info
might point to an atom or another list
All program code composed of functions
Original LISP
The original idea was to make Lisp a universal Turing Machine where both data and instructions
would be treated in the same way -- therefore everything is a list including programs
Lisp’s primary function is EVAL which evaluates a list or atom at run-time
Since Lisp code is represented as lists, Lisp is interpreted
LISP functions
As stated earlier, lambda functions are nameless functions
Lisp programs can be composed of lambda functions which are executed at the command line
Lisp also has a function for defining and binding functions (that is, there are facilities for naming
functions so that you can use those by calling them from other functions)
Application
Lisp was used extensively for research in Expert Systems, Natural Language Understanding,
Machine Learning, Knowledge Representation, Speech/Vision Understanding, Robotics,
Tutorials
Mostly used in AI research
Natural Language Understanding (easy parsing partially due to recursive nature)
Expert Systems (easy rule format)
Knowledge Representation (symbolic capabilities)
Machine Learning (dynamic storage)
etc…
Also used to teach functional programming and mathematically oriented programming
Used to implement EMACS, MACSYMA and even some operating systems
Objects first introduced in Simula 67, a language mostly applied for simulations Developed more
fully in Smalltalk which brought objects into the public focus C++ is a descendent of C and
3-105
Smalltalk CLOS implemented to provide Common Lisp with full Object capabilities
Ada 95 also has full Object capabilities Java is a new generation of OOPL, safer, easier?
Objects
These are the characteristics of objects
1) Organized hierarchically with inheritance
2) Structures can be easily modified
3) Message-Passing rather than procedure calls
4) Encapsulation enforced (unlike ADTs where some PLs do not enforce this)
5) Generic nature of methods to allow for different typed objects to use the same named
operations
Inheritance
Solution to the modification problem by inheriting what was implemented for prior (parent)
classes Derived class - subclass, inherits from another class which is the superclass or parent
class. In some languages (C++), what is to be inherited can be dictated by the programmer
Some languages (C++) have multiple inheritance, others have single inheritance
Polymorphism
Polymorphic variables can reference any subclass of a given class
Dynamic type binding of variable is done when method is called This allows for flexibility in
system construction and maintenance so that variables do not have to be bound to specific types,
types can change as new objects/subclasses are added or changed
Message passing
Model which resembles the world with objects communicating via messages
Objects have their own local memory and processes (methods)
An object’s method(s) is activated as a response to a message from another object
Return response is another message
Messages can have parameters to allow for more specific communication between objects
3-106
Types of OO languages
Pure OOP - all computation done by message passing between objects (e.g. Smalltalk)
Hybrid OOP - objects make up part of the language in which computation is done by message
passing and procedure/function calls (e.g. C++, Java,
CLOS/Common Lisp)
Objects can be statically or dynamically bound and are typically referenced by pointers
Classes - object abstractions organized hierarchy.
Instances - objects created from classes
Design
Exclusivity of Objects - are all types classes or are there other types (pure vs. hybrid)
Subclass relationships - is a subclass a descendant of the class (an is-a relationship), or a
different relationship
Inheritance and information hiding - how are these provided and enforced?
Type checking and polymorphism - is this done?
Single vs. multiple inheritance - which is allowable?
Allocation and Deallocation of Objects - when and how
Dynamic vs. Static Binding of Objects
Smalltalk
Evaluation of Smalltalk
3-107
Mathematically, very limited
Less efficient than imperative languages
Because of dynamic type checking, errors are often not caught until run-time
Useful for games and graphics
First real OO language, pioneered many of the ideas now embedded in OOP
Java
Java packages
Two forms of encapsulation in Java - classes (logical encapsulations) and packages (physical
encapsulations)
Similar classes are grouped into packages
Built-in class packages include [Link], [Link], [Link], [Link] and [Link]
A class C in package P is specified as P.C
To use a package, it must be imported as in
import [Link]; to use Name’s Class or
import Name.*; to use everything
Java uses single inheritance but multiple inheritance can be simulated using the virtual class
called Interface
Java does not support generic methods but this can be done by using object inheritance
Java allows for abstract classes and methods where derived types of these abstract classes must
implement the abstract methods
(i.e. abstract classes outline what the class will do but the programmer must then finish the
3-108
implementation)
This - keyword to refer to the current object (used as a self-assignment, alias or to call the
constructor of the same class)
Instanceof - a run-time test to determine if an expression is an instance of a class
Static - allows a field in a class to become global and shared
Java Applets
Java objects are very similar to C++ and allow for similar power in programming
Unlike C++, all Java objects are explicit heap-dynamic, allocated with the new command and
deallocated automatically by the garbage collector
Unlike C++, all Java objects are referenced by a reference variable, which is like a pointer, but
safer
Control structures
Compound statements
Compound statements make control statements easier to design so that groups of instructions can
be formed inside of a selection, repetition or branch
ALGOL 60 - first PL to introduce blocks using begin-end statements
C, C++, Java - uses { } as delimiters
Selection statements
Gives a program the ability to choose which instruction(s) to next execute based on conditions
Essential for every language
Types:
1-Way Selection
2-Way Selection
3-109
3-Way Selection
Multiple Selection
N way selectors
Case statement: compare variable against a list of options, if matches then execute the statement
and end else try next list of options. In Pascal and Modula-2, variable can be any ordinal type, in
others, it must be an integer
C - uses a Switch statement where, if one list matches, the statement is executed but the
remainder of the list is checked rather than ending unless a break statement is included
Repetition statements
Every Programming language has included some form of repetition
How is repetition controlled? Should testing of whether to repeat occur before or after the loop
body is executed? (pre vs. post test)
Where should the control mechanism appear in the loop?
Iteration (Counter controlled loops)
Control is maintained by using a loop variable which is started at the initial value, compared to
the terminal value and incremented each time through the loop by a step size.
These types of loops are often supported directly in computer hardware (e.g. automatic
incrementing of loop variable)
Design
What is the Type and Scope of this loop variable?
What value does the loop variable have after termination if any?
Can the loop variable be changed during the loop?
Should the test for completion be pre- or post-test?
3-110
Should the initial and finding values be tested once or each time through?
For situations where the number of repetitions is not known before the loop proceeds -- these
loops use some testable condition
Pretest vs. posttest
Is this type of statement separate from a special kind of counter-controlled loop?
Exiting loops
Should exiting only be permitted at the end when the test returns false? Or can premature exiting
(and returning) be permitted?
Ada has loop ... end loop -- a conditionless loop (infinite loop unless a branch is used)
C and Modula-2 have unconditional exit statements (break, exit)
Multiple exits harm readability
Operators
Associativity
If two or more operators are of the same precedence, then they are usually applied in a Left-to-
Right manner
A + B + C = (A + B) + C
** (exponent) is usually Right-to-Left
A ** B ** C = A ** (B ** C)
In Ada, ** is not associative which means that you must parenthesize the expression to either
(A ** B) ** C or A ** (B ** C)
Side effects
When a function changes a parameter which is passed back or changes a global variable
Consider the expression A + Fun(A), if Fun(A) does not alter A, then the order of evaluation is
unimportant, but if
Fun changes A, then A + Fun(A) <> Fun(A) + A
In Pascal, side effects can occur using global variables or var params in functions
Side effects can be disallowed (no var params, no global vars) or evaluate all expressions L-R
putting functions at the end of the expression
type conversion
Narrowing - going from a larger type to smaller type (e.g. integer to short int)
Widening - from smaller type to larger
Widening - almost always safe, narrowing - rarely safe (lose information)
Coercion - implicit type conversion initiated by the compiler due to the use of an arithmetic
operator (e.g. dividing 2 integers in Pascal yields a real)
Context-free grammar
An important step in the automatic processing of natural or formal languages consists in breaking
down the input stream of words or characters into sentences in the relevant language and then
analyzing those sentences syntactically.
This can be done for each language on the basis of a grammar which defines:
A Context Free Grammar (CFG) is a set of recursive rewriting rules (or productions) used to
generate patterns of strings.
· A set of terminal symbols, which are the characters of the alphabet that appear in the strings
3-113
generated by the grammar.
· A set of non-terminal symbols, which are placeholders for patterns of terminal symbols that can
be generated by the non-terminal symbols.
· A set of productions, which are rules for replacing (or rewriting) non-terminal symbols (on the
left side of the production) in a string with other non-terminal or terminal symbols (on the right
side of the production).
· A start symbol, which is a special non-terminal symbol that appears in the initial string
generated by the grammar.
· Apply one of the productions with the start symbol on the left hand side, replacing the start
symbol with the right hand side of the production;
· Repeat the process of selecting non-terminal symbols in the string, and replacing them with the
right hand side of some corresponding production,
until all non-terminals have been replaced by terminal symbols.
<stmt> = Statement
<expr> = Expression
Non-terminal symbols are <stmt> and <expr>
Terminal symbols are if and else
<start> is the Start symbol
3-114
3.3 Evaluation of algorithms
Algorithms should be evaluated and selected based on certain criteria. If the most appropriate
algorithm can be found to solve the problem, the work of programming ca be done efficiently
and a high degree program can be created.
This section describes the following three algorithm evaluation criteria:
- Evaluation in terms of computational complexity (a criterion for evaluating efficiency)
- Evaluation in terms of validity (a criterion for evaluating reliability)
- Evaluation in terms of representation (a criterion for evaluating elimination of redundancy and
improvement of processing speed)
3-115
cLinear search (sequential search)
- Minimum number of times of comparison: 1 (computational complexities: O (1))
- Average number of times of comparison: n/2 (computational complexities: O (n))
- Maximum number of times of comparison: n (computational complexities: O (n))
dBinary search
- Minimum number of times of comparison: 1 (computational complexities: O (1))
- Average number of times of comparison: [log2n] (computational complexities: O ([log2n]))
- Maximum number of times of comparison: [log2n]+1 (computational complexities: O ([log2n]))
3-116
3.4 How to design algorithms
Based on data obtained by analyzing a problem and the results described in the previous
section, an algorithm is designed with the most attention given to how a solution can be had with
the highest level of efficiency. There are several methods used to design an algorithm.
Representative methods are:
- Dynamic programming method
- Greedy algorithm method
- Reduction method
(1) Dynamic programming method
In the dynamic programming method, one problem is considered to be a set of more than one
sub-problem.
Steps to follow are:
1. A problem is divided into some sub-problems.
2. A solution to each sub-problem is found.
3. Some sub-problems are put together to make a slightly larger partial problem.
4. Above steps 2 and 3 are repeated until a solution method to the original problem is found.
(2) Greedy algorithm method
In the greedy algorithm method, which is used to find a solution to an optimization problem, the
values of variables are changed by degrees depending on each present condition. For example, to
find how the number of coins can be decreased to a minimum to pay a specified amount, the
number of large to small value coins is determined using the greedy algorithm method.
Example
To pay 574,
One 500-yen coin - 74 remains
One 50-yen coin - 24 remains
Two ten-yen coins - 4 remains
Four 1-yen coins - Nothing remains
(3) Reduction method
In the reduction method, an algorithm originally designed has complexity of O (n) is subjected to
a reduction process of time length cn, so that it can be reduced to a smaller size to create a new
algorithm of O (n/x). If O (n) > cn + O (n/x) cannot be satisfied, this algorithm is meaningless.
Therefore, if n is very small, this algorithm cannot produce the expected results.
3-117
3.5 Applications of algorithms
Algorithms find usage in many areas. These include
1) Routing
2) Search engines
3) Cryptography
4) Data mining
3.5.1 Routing
1) Static routing
The shortest path to the destination is determined.
Dijkstra's algorithm is used to explore the network wavelike starting at node A and
determine at every visited node the shortest path to A and the next node on this path.
Move the wave further at the (border-) node having the shortest distance to A.
2) Dynamic routing
Distance vector routing:
Every router sends the packet over the link, using a routing table that belongs to the
shortest path.
1) Every router maintains distance table with 2 entries per destination:
– shortest known (estimated) distance to destination (#routers/hops, delay, throughput,...)
– link corresponding to this distance.
2) Every router knows (an estimate of) the distance to its direct neighbors.
3) Every router sends regularly its current distance vector to each direct neighbor
(distances only, not links).
4) On receipt of a distance table from neighbor X the router checks, if it should correct
its own entries:
– increase entry, if all neighbors report larger distances
3-118
– decrease entry, if a neighbor reports a smaller distance
Link-State Routing:
Compute shortest paths based on regularly exchanged local knowledge of the topology.
Every Router must
1. Detect its neighbors and their network addresses.
2. Measure the delay (cost) to the neighbors.
3. Compile the results of (1) and (2) into a suitable packet.
4. Send this packet to all other routers.
5. Compute the shortest path to all other routers.
3-119
These created catalogs of web pages manually. The sites must be submitted, then they
are assigned to an appropriate category. Directories can often provide better results than
search engines e.g. Yahoo
Mechanism of the search engine
Search engines have three major elements:
1) the spider (also called crawler)
This visits a web page, reads (and analyses) it, and then follows links to other pages
within the site.
2) It returns to the site on a regular basis, such as every month or two, to look for changes.
3) The index (also called catalog)
It contains information on every web page that the spider finds. It is updated, whenever
web page changes are detected. Only the pages listed in the index are available for
searching. It uses efficient data structures to support searching.
The search engine software analyses a query, searches the index for documents matching
the query, ranks the matching documents in order of relevance.
3-120
Criteria for assessing the quality of the search engine
Recall = No of relevant retrieved documents
-----------------------------------
No of relevant documents
Precision = No of relevant retrieved documents
-----------------------------------
No of retrieved documents
3-121
3.5.3 Cryptography
There are 2 kinds in use today
Symmetric key algorithms
This method uses the same key to encrypt and decrypt the message. DES (Data
Encryption Standard) is an example of this. Symmetric keys are faster than public key
algorithms. In terms of security, the encryption key must be exchanged securely.
Symmetric key Algorithms
Name Description
IDEA International Data Encryption Algorithm This uses a 128 bit key
This allows a user defined key length, data block size and number of encryption
RC5
rounds
3-122
Name Description
Diffie-Hellman This is not encryption system but a method to exchange the key over a public
key exchange communication
This is used for encrypting as well as for digital signatures. The key may be
RSA
any length
3-123
Some common message digest functions are given below
Message Digest
Description
Function
3-124
Each record is then assigned to the cluster whose centroid that is nearest. Boundaries
between clusters are drawn by utilizing the mid point between the seed points.
The centroid of each cluster is then calculated by finding the average of all the points in
the cluster. Each record is then re-assigned to the clusters created. This continues until the
boundary stops changing.
3-125
Cluster detection is used when there is a possible set of natural groupings representing
features in common. This is used when there are many competing patterns and it is
difficult to spot a single pattern. Complexity is reduced by creating clusters and other
data mining methods can be applied to the results.
Decision trees
Classification tree
This means it aids in classifying the record to a given class.
The Class probability is the confidence that a record is in a given class.
Trees grow in many forms
An example of a binary tree of non uniform depth is shown. Each node has 2 children and
the depth from root to leaf is variable. Decision trees don't necessarily have to be binary.
3-126
Use of rules
The effectiveness of a decision tree is measured by applying it to a collection of unseen
records and determining the percentage classified correctly. Each path through the tree
represents a rule. The predictive ability of the tree can be improved by pruning back some
of the weaker branches.
At each node, the following is measured
1) Number of records entering the node
2) The way the records are classified if it is a leaf node
3) The percentage of records classified correctly at this node
Decision tree building algorithms start by trying to determine the best way to split the
data between the different categories. At each level of the tree, the subsets are split
further.
3-128
Exercises for No.1 Chapter 3 (Algorithms)
Q1 What is the term used to show a algorithm that searches the elements sequentially
from the head to the foot of a table?
a. Linear b. Binary c. Hash d. Heap
Q2 Values in the array containing n elements, are sequentially compared with data X
which is data to be searched. If data X matches a certain value in the table, "exist" is
shown. Data X is stored in the position designated as index n+1.
Subscript 1 2 3 ... i ... n n+1
Value a1 a2 a3 ... ai ... an X
In the linear search algorithm shown below, what condition should be entered in the
space ?
Q3 There is array A which contain n data item sorted in the ascending order. The
following flowchart shows the routine for retrieving data x from array A using the
binary search method. Choose a correct combination of operations and enter them in
the spaces a and b. Decimal numbers of a value obtained by division should be
truncated.
Start
1 lo
n hi
( lo hi ) 2 k
A(k):x
a b
lo : hi
End
3- 129
a b
a k + l → hi k - l → lo
b k - l → hi K + l → lo
c k + l → lo k - l → hi
d k - l → lo K + l → hi
Q4 There is a table that has 2,000 different elements sorted in the ascending order of the
keys. Using a key input from outside, this table is searched using the binary search
method, and the elements that match the key are retrieved. What is the maximum
number of comparison times needed before all matching elements are found? It is
assumed that the table contains the matching key.
a. 10 b. 11 c. 12 d. 13
Q6 Concerning data sort and merge, choose the proper combinations of words and enter
them in the space .
Sorting data in the order of small- to large-value queues is referred as a b . If a target
data sequence is in an auxiliary storage, this operation is called c .
Integrating two or more files b in certain order into one file is called d .
a b c d
A descending sort external sorting merge
B ascending merge external merge sort
C descending merge internal merge sort
D ascending sort external sorting merge
E ascending merge internal merge sort
3- 130
Q7 What sort of algorithm does the following flowchart show?
Start
Repeat
n 1
1 i
Exchange
i n
A ( i ) :A (i 1)
A(i) w
A(i 1) A(i)
w A(i 1)
Exchange
Repeat
End
a. Quick sort b. Shaker sort c. Shell sort d. Insertion sort e. Bubble sort
Q8 It took 1.0 seconds for a certain computer to sort 1,000 data using the bubble sort
method. How long will it take to sort 100,000 data of the same type? The time that
it takes for a computer to bubble sort data is proportional to a square of the number of
data that is defined as n.
a. 1 b. 10 c. 100 d. 1,000 e. 10,000
3- 131
Q10 Which is an appropriate description of quick sort?
a. Compare and exchange are executed for two data away from one another at a certain distance.
This distance is gradually and continuously narrowed to sort all data.
b. The first minimum value is found in data. The second minimum value is found in data in
which the first minimum value is not included. This routine is repeatedly executed.
c. Data is divided into one group of data smaller than a reference value and the other group of
data larger than a reference value. In each group, a new reference value is then selected and
data is likewise divided into two groups based on the reference value. This routine is
repeatedly executed.
d. Adjacent data are repeatedly compared and exchanged to allow smaller data to move to the
end of a data array.
Q11 There is array TANGO whose index number starts with 0. n words are contained in
TANGO (1) through TANGO (n). A flowchart below shows the steps for reorganizing
the word table by shifting words in TANGO (1) through TANGO (n-1) backward, by
one word, to put an n-th word in TANGO (1). Enter a proper step in the space .
Start
TANGO(n) TANGO(0)
Loop
End
Q12 From the descriptions made on Newton's method, which is known as an algorithm for
obtaining an approximate solution of the equation f(x) = 0, choose the most
appropriate one.
a. Although a function, f(x), cannot be differentiated, an approximate solution can be obtained.
b. As seen from the geometrical viewpoint, the method is to obtain an approximate solution by
using a tangential line of y = f(x).
c. Two different initial values must be provided.
d. Whatever initial values are provided, an approximate value can always be obtained.
3- 132
Hardware
4
Chapter Objectives
Among computer related technology, the progress of hardware
technology is particularly remarkable.
In this chapter, the learning objective is to understand the
mechanism and functions of each of the five main units that are
basic to computer hardware. To:
1 Understand the roles and functions of the computer's five
main units
2 Understand basic operations and the registers used to
read, decode and execute the instructions and data stored in
the main storage unit by the processor (processing unit),
which is composed of the control unit and the arithmetic
unit,
3 Understand the basic approach and configuration circuits of
the arithmetic unit that performs arithmetic operations and
logical operations
4 Understand the mechanism and functions of the main
storage unit and the auxiliary storage devices used to store
data, and know their types and characteristics,
5 Understand the types and mechanisms of the input/output
units as well as the input/output control system and the
input/output interface,
6 Understand computer types and characteristics
4- 1
Introduction
The function of the hardware composing a computer can be divided broadly into the following
five categories:
• Input
• Storage
• Operation
• Control
• Output
The following are the units that implement the above mentioned functions:
• Input unit: This unit inputs the data and programs for computer processing. It is
equivalent to the human eyes and ears.
• Storage unit: This unit stores the input data and programs. It is equivalent to the memory
section of the human brain.
• Arithmetic unit: This unit conducts calculation and decision on the stored data according
to the instructions of the program. It is equivalent to the thinking section of the human
brain.
• Control unit: This unit controls the input unit, storage unit, arithmetic unit and the output
unit. It is equivalent to the human central nervous system.
• Output unit: This unit outputs the results of computer processing in a format that can be
understood by humans. It is equivalent to the human hands and mouth.
These five units are called the "computer five main units" (Figure 4-1-1)
Since the control unit and the arithmetic unit are handled as one unit, they are called the
processor (processing unit) or central processing unit (CPU). The general term "peripheral
devices" is used to refer to the input unit, the output unit and the auxiliary storage devices that
are outside the processor and exchange data with the main storage unit. Likewise, the storage
units are divided into the main storage and auxiliary storage device, depending on their functions.
4- 2
Figure 4-1-1
Computer five main units Input unit
Main
Output unit
storage unit
Control
unit
Figure 4-1-3
DRAM
RAM and ROM RAM
SRAM
Semiconductor memory
Mask ROM
ROM
User programmable ROM
4- 3
from the main storage unit at random by specifying the address.
RAMs are classified into DRAMs and SRAMs.
1) DRAM (Dynamic RAM)
A DRAM represents bits, and stores information depending on whether the part called capacitor
is being charged (status "1") or is not being charged (status "0").Since the circuits are simple and
small, RAMs of large capacity can be created at low cost. However, since the charge stored in
the capacitor is lost after a lapse of time, the memory needs to be rewritten (recharged) at regular
intervals. This operation is called refreshing. Once, DRAMs were used in the main storage unit,
but currently they are also used in storage units, etc, contained in the input/output units of
printers and other devices.
2) SDRAM (Synchronous DRAM)
Due to the progress of IC technology, and the consequential substantial improvement of the
performance of processors, the operating speed of the DRAMs that composed the storage unit
could not keep up with the operating speed of the processors. For that reason, an external clock
signal that indicates the processor operation timing is now set in the DRAM and through
synchronization with this signal, complicated address specifications are reduced and simplified,
enabling the development of DRAMs that operate at high speeds. These types of DRAMs are
called synchronous DRAMs (SDRAM).
3) SRAM (Static RAM)
SRAMs are created with a circuit called the flip-flop. The flip-flop settles the output according to
the previous input and the current input, and can preserve the status "1" and "0" inside the circuit.
Since data is not lost unless the computer is turned off, memory refreshing is not necessary.
However, since SRAM circuits are complicated, the memory capacity is smaller than that of
DRAMs and the cost is higher. However, since its processing speed is high, it is used in devices
such as the registers contained in main storage units and processors.
(2) ROM (Read Only Memory)
The ROM is semiconductor memory for read use only. Since programs and data are stored in the
ROM from the beginning, the stored information is not lost even if the computer is turned off.
This property is called non volatility.
ROMs are classified into mask ROMs and user programmable ROMs.
1) Mask ROM
Since program and data are already written in the Mask ROM before it is shipped by the
manufacturer, the user cannot add any programs or data. Mask ROMs are used in the memories
of game cassettes and IPL (Initial Program Loader) a program used to start the computer, etc.
4- 4
2) User programmable ROM
The user programmable ROM is a type of ROM, but since at the time it is shipped by the
manufacturer it has nothing stored in it, the user can write data into it once. The following types
of programmable ROM exist (Figure 4-1-4)
• PROM (Programmable ROM): Once data has been written, it cannot be erased.
• EPROM (Erasable PROM): It can be erased with ultraviolet light and rewritten.
Figure 4-1-4
User programmable ROMs PROM
EEPROM
4- 5
4.2 Processor Architecture
4- 6
Figure 4-2-1
<Processor> <Main storage unit>
Mechanism of the Control unit Address 100 Retrieve the contents of address 100
sequential control system Address 101
Arithmetic unit Address 102
Address 100
Arithmetic unit
Address 100 Address 101
Control unit Address 100 Store the addition result in address 102
Address 101
2) Arithmetic unit
The official name of the arithmetic unit is arithmetic and logic unit (ALU). This unit performs
arithmetic operations, logical operations, comparison, branch, and other processes on the data
assigned to be subject to processing. The main instructions are shown in Figure 4-2-2.
Figure 4-2-2
Basic operations Basic instructions
Functions of the
Arithmetic operations Addition, subtraction, multiplication and division
arithmetic unit
Logical operations Logical sum (OR), logical product (AND), negation (NOT)
Comparison Comparison instruction (size comparison)
Branch Branch instruction (change of the sequence of
instruction execution according to the conditions)
4- 7
a. Instruction and instruction format
Instruction
The program is a set of instructions that indicates "do..." to the computer. Since inside the
computer, data is represented in the binary system, instructions are also represented in the binary
system. The instructions represented in the binary system are called machine language
instructions. Regardless of the program language in which a program is written, at the end it is
converted into language that can be understood by the computer, machine language, in order to
be decoded and executed. Machine language instructions and instruction formats differ
depending on the computer, but, in general terms, they are composed of the following parts.
• Address part: Specifies the address and register of the main storage unit subject to
processing
Figure 4-2-3
Address part
Example of the Instruction part
32 bits
Instruction format
In practice, instruction formats differ depending on the computer. There are instructions that
have several address parts and according to the structure of the address part, there are four
address formats, from zero-address format to the three address format.
Zero-address format
The zero-address format performs operations using a dedicated register called a stack pointer.
Currently, zero-address format computers are not used. The stack pointer is the register that
stores the address to be returned to (return address) after execution completion.
Single-address format
The single-address format performs operations between the contents of the main storage unit
specified in the address and the accumulator data (Figure 4-2-5). The accumulator stores
operation values and operation results. There are cases where general-purpose registers are also
used as accumulators.
4- 8
Two-address format
The two-address format specifies two addresses and uses the address data specified on the main
storage unit.
Three-address format
The three-address format specifies two addresses to be used for the operation and the address
where the operation result is to be stored
Figure 4-2-7 Instruction part Address part Address part Address part
Three-address format
b. Instruction readout
The instruction received from the main storage unit is stored in the instruction register (IR).The
length of one word of the main storage unit is 16 bits. It is supposed that one instruction has 32s
in the computers used. One instruction is stored in two words. Therefore, the content of the
address of the main storage unit accessed is sent to the processor twice. In practice, it is
determined beforehand that in one instruction the instruction part is stored in an even address
while the address part is stored in an odd address.
+1
Control unit
c Instruction decoding
The content of the instruction part of the instruction register is transferred to a device called the
decoder. The decoder decodes the type of work indicated by the instruction and sends the signals
for the execution of the operation to each unit.
4- 9
Figure 4-2-9
Instruction decoder
Address decoder
Instruction 2
Data bus Instruction 3 Address 2
PC
Instruction
decoder +1
Signals for instruction
execution
Control unit Address 65535
Processor Read/write controller
On the other hand, the content of the address part of the instruction register is transferred to
the address bus. The content of the address of the main storage unit specified by the address bus
corresponds to the data subject to processing. According to the instruction of the instruction part,
a read/write signal is sent from the control unit to the data, subject to processing on the main
storage unit.
Figure 4-2-10
Address part and
data subject to
Specification Main storage unit
processing IR of the address
Instruction 1
Instruction Instruction of the data Address 0
part 1 part 2 subject to Instruction 2 Address 1
Address decoder
processing
PC Data subject to
processing
Instruction Address bus
decoder
Read/write sign
Control unit Address 65535
Read/write controller
Processor
Indication of Read/write
2) Instruction execution
Once the instruction content and the address of the data subject to processing are obtained, the
instruction is executed. Using the example of assembler language in which there is a one to one
correspondence with the machine language, the instruction execution control and each type of
register will be explained below.
a. Storing retrieved data
If, as a result of decoding the instruction part and the address part using the instruction decoder,
the instruction is found to say "Retrieve and transfer to the processor the contents of address
100 of the main storage unit," a place to store the retrieved contents will be needed. Therefore,
a general purpose is set in the arithmetic unit of the processor in order to store the retrieved data.
4- 10
In this example, it is assumed that there are five registers, and, for convenience, the numbers 0
to 4 will be assigned to them. Then, using the initial s of each of the general-purpose registers,
they will be represented as GR0, GR1, GR2, GR3 and GR4.
Figure 4-2-11
General-purpose IR
General-purpose register register
GR
GR
GR PC
GR
+1
GR
Instruction
decoder
Arithmetic unit Control unit
Processor
Figure 4-2-12 shows the mechanism by which the contents of address 100 of the main storage
unit passes through the data bus to be stored in general-purpose register GR1.
Decoding of readout
GR instruction
GR PC Address 100
GR
Instruction +1
GR decoder
Readout instruction
Arithmetic unit Control unit Address 65535
Read/write controller
Processor
Indication of readout instruction
b. Instruction execution
If, as a result of decoding the instruction part and the address part of the instruction register, the
instruction is found to say "Add the contents of address 100 of the main storage unit to GR1
contents and store them in GR1," the retrieved contents of address 100 have to be added to GR1
contents. The unit that performs this kind of addition and subtraction of numeric values is the
ALU (Arithmetic Logic Unit)
The ALU has the following arithmetic mechanism.
Fixed point operation mechanism to perform operations
of integer data for scientific and engineering
Floating point operation mechanism to perform operations calculations
of floating point data
Decimal operation mechanism to perform operations
of binary coded decimals in packet format for commercial data processing
It should be noted that besides arithmetic operations such as addition and subtraction, the
operation mechanism of the ALU performs logical operations such as logical products, logical
4- 11
sums and shifts.
+1 Instruction 10 Address 9
d. Flow of the instruction from its decoding to its execution and hardware structure
Figure 4-2-14 shows the hardware structure from the instruction readout to its decoding and
execution.
Data bus
GR Instruction 3 Address 2
Data bus
GR PC
Address bus
+1
GR n
Instruction
ALU decoder
Control bus
e. Various registers
Up to this point, the roles played by the instruction register, the general purpose register, etc,
have been explained, but, besides the registers, the following registers exist:
4- 12
. Program counter
. Accumulator
. Index register
. Base address register
. Program Status Word (PSW)
. Flag register
. Complement register
. Program Counter (PC)
In Figure 4-2-15, considering the procedure in which instruction "A" stored in address 101 of
the main storage unit is loaded to the processor, the following can be observed:
1. The processor specifies address 101 with the address bus
2. The control unit send the readout signal to the main storage unit
3. The main storage unit transfers the contents of address 101 to the processor using the
data bus.
At the beginning, the processor specified address 101, but under whose instructions? There is
actually a storage unit that exclusively performs this kind of instruction inside the processor. It
is called the program counter and is composed of 16 bits. The program counter is also called
the instruction address register, instruction counter or sequential control counter.
The devices, as in the program counter, are set inside the processor and temporarily store data
are known generally as registers. Among the registers, there are specialized registers whose
application is set in advance, as in the program counter's, and general purpose registers whose
application is freely decided by the program.
Figure 4-2-15
Address reading
3. The contents of the specified
address are transferred
Data bus
Control unit
1 word (16 bits) Address 65535
Read/write controller
Control bus
Computer hardware is set in such a way that when the computer is turned on, the content of the
program counter is immediately read and the address of the main storage unit to be accessed is
4- 13
verified. Likewise, every time this program counter is referred to, the content stored is
automatically "+l (instruction word length)"
Taking into account the role of the program counter, and if we consider the procedure in which
the processor loads instruction "A" stored in address 101 of the main storage unit, the following
can be observed:
1. The content stored in the program counter is referred to and the address of the main storage
unit to be accessed is verified. After it is referred to, "l" is automatically added to the content
of the program counter.
2. The processor specifies address 101 with the address bus.
3. The control unit sends the readout signal to the main storage unit.
4. The main storage unit transfers the contents of address 101 A to the processor using the data
bus.
Role of the
program counter Processor Main storage unit
1 word (16 bits) Address 0
1. The address to
Address decoder
Control unit
1 word (16 bits) Address 65535
Read/write controller
. Accumulator
The accumulator is the register used exclusively to store operation results and operation
values. Since it stores accumulating results, it is also called the accumulating device. There
are cases when the general purpose register is used as a substitute for the accumulator.
When the accumulator is used, it is called accumulator mode, when the general purpose register
is used, it is called general purpose register mode.
Data Result
Accumulating result
. Index register
When an address in the main storage unit is specified, the act of changing the address of the
address part of the instruction is called address modification. The register used to perform
4- 14
this change is the index register.
Figure 4-2-18
Main storage unit
Index register Address 0
Instruction Instruction part Address part
Address 1
Calculated address
Index register
Address 65535
. Base register
The base register is the register that stores the program top address.
Address 65535
. Flag register
The flag register stores information related to the operation result (if it is positive or negative
or 0), to the existence of carry, overflow, etc.
PSW
Store Restore
4- 15
. Complement register
The complement register generates integer complements in order to perform operations in the
addition circuit.
cImmediate specification
In the immediate specification, the data itself is contained in the address part. Since it is not
necessary to access the main storage unit address, it can be immediately executed.
Figure 4-2-24
Immediate Address part
Instruction Instruction part Data
specification
4- 16
Figure 4-2-25 Address part Main storage unit Address
Direct address Instruction Instruction part 100 Address 0
Address 1
specification Address 2
Address 3
Register number
Register number
4- 17
gBase address specification
In the base address specification, the program starting address is stored in the base register. the
result of the addition of the address contained in this base register and the address constant
becomes the effective address.
Address 100
Register number Address 101
Program
Address 150
4- 18
(4) Instruction set
When the computer executes a job requested by the user, the hardware performs the process
using several instructions needed from a group of instructions built into that computer. The set of
instructions is defined as the interface of the software and the hardware of a specific computer,
and depending on the computer, the types and number of instructions differ. This group of
instructions (the total of the instructions) is called the instruction set. As a result, computer
software packages with identical instruction sets are basically compatible.
(5) Execution control of the instruction
The execution of a program consists of the repetition of the readout of the instruction from the
main storage unit, and the decoding and execution of that instruction by the control unit. If we
arrange the operations performed by the processor during program execution, we can divide
them as follows:
• Instruction readout
• Instruction execution
cInstruction cycle and execution cycle
The series of operation consisting of the readout and the instruction stored in the main storage
unit, its storage in the instruction register contained in the processor, and the instruction decoding
using in instruction decoder, is called the instruction cycle. Likewise, the series of operations
consisting of the reading out of the data subject to processing from the main storage unit, and
writing and executing the instruction, is called the execution cycle.
a. Instruction cycle
The instruction cycle consists of the following two consecutive operations:
• According to the value of the program counter, the instruction to be executed is read out
from the address of the main storage unit, where it was stored, to be stored in the
instruction register.
• The instruction part of the instruction register is decoded using the instruction decoder,
and the address part of the data subject to processing is calculated based on the address
part of the instruction register.
The instruction cycle is also called 1 cycle, and it is also called F (fetch) cycle.
b. Execution cycle
The execution cycle consists of the following two consecutive operations:
• If the decoded instruction is readout, the data subject to processing is read out
from the specified address of the main storage unit; if it is a writing instruction, data is
written in the specified address of the main storage unit.
• In the case of readout instructions, the read out data is used to perform the operation
process.
4- 19
Taking the initial of execution, the execution cycle is also called E cycle.
c. Instruction cycle and execution cycle operations
Figure 4-2-31 shows the flow figure of the operations of the instruction cycle and execution
cycle.
Figure 4-2-31 Flow figure of the operations of the instruction cycle and execution cycle
Start
None Instruction to be
executed?
Exists
Instruction cycle
Repetition
address part of the instruction register
End
Note: There are cases where the program counter update is performed immediately after the instruction
readout, and there are cases where it is performed after the instruction execution is completed.
The processor reads out, in order, the program instructions stored in the main storage unit and
executes the program by repeating the instruction cycle and execution cycle.
(6) Hardwired-logic control and microprogramming control
The instructions set in the computer are executed using logical circuits composed of several logic
elements. In other words, logical circuits are the result of hardwiring among the logic elements;
for that reason they are called hardwired logic control system or writing logic control system.
Since the different instructions are implemented by the hardware, they have the advantage that
the operation speed is fast. Opposite to this system, there is one that executes the instructions
with the firmware.
As computer performance improves, instructions with more complicated functions become
feasible. The higher the function level of the instructions, the more complicated the control
procedure becomes. Therefore, instead of executing the instructions with hardware of
complicated wiring, an execution method using easily modifiable firmware was designed. This
method is called microprogramming control system. Compared to the hardwired logic control
4- 20
system, the operation speed of the microprogramming control system is slow, but the hardware is
simpler and corrections (debugging) are easily performed. The microprogram, which is a string
of patterns that determine whether the logic gate is to be on or off, is stored in a special memory
called control storage inside the control unit. Instructions are followed by reading out
the microprogram sequentially.
• sequential architecture
• speculative architecture
Another name for pre-fetched control is pipeline. RISC is an example of a processor that uses
pipeline processing.
(1) Pipeline processing
Sequential architecture is the process of reading, decoding and execution of the instruction till it
is finished before another instruction is fetched.
Program execution steps are
Instruction cycle c: The instruction is read from the main storage unit
Instruction cycle d: The instruction is decoded and the address calculated
Execution cycle e: The reading and writing of the main storage unit is done
Execution cycle f: The actions specified by the instruction is executed
Figure 4-2-32 Serial control processing
Time
Instruction 1 1 2 3 4
Instruction 2 1 2 3 4
Instruction 3 1 2
Instruction cycle c and execution cycle e accesses the main storage unit. Instruction cycle
dand execution f is executed within the processor.
The processor is idle when the instruction cycle cand execution cycle e are executing.
Conversely, when instruction cycle dand execution f are executing, no access to the main
storage unit is done.
The next instruction is read in and queued during this idle time. This increases processing
efficiency and this method is known as speculative control method. Pipeline processing utilizes
this speculative control method and the next set of instructions are read in and processed in
4- 21
queued to be processing.
Figure 4-2-33 Pipeline processing
Time
Instruction 1 1 2 3 4
Instruction 2 1 2 3 4
Instruction 3 1 2 3 4
Instruction 4 1 2 3 4
• Fork instructions are issued from within executing instruction. The order of execution of
the instructions is changed.
4- 22
Figure 4-2-34 Characteristics of RISC and CISC
RISC CISC
• Make up of few simple • Complex, high level type
instructions instructions
• Instructions are executed by the • Instructions are executed by
hardware the micro-program
• The size of the instruction and • There is variation in the
the execution time of each instruction size and length of
instruction is about the same execution
RISC is not optimized or the number of instruction steps is many, Efficient programs are
dependent on the optimization functions found in the compiler.
Recently, many workstations are created with the RISC architecture
(3) Parallel method
cSuper scalar architecture
Under the best conditions, the normal pipeline architecture is limited to one instruction per cycle.
The super scalar architecture allows for multiple instructions to be executed in 1 cycle. Multiple
parallel processors in the CPU allow the execution of these multiple instructions in 1 cycle.
Instructions that can executed in parallel have to be separated from the general instructions. The
architecture is known as super scalar if on average, if multiple instructions are running in 1 cycle.
Figure 4-2-35 Super scalar architecture
Instruction 1 1 2 3 4
Instruction 2 1 2 3 4
Instruction 3 1 2 3 4
Instruction 4 1 2 3 4
Instruction 5 1 2 3 4
Instruction 6 1 2 3 4
4- 23
Figure 4-2-36 Super pipeline architecture
Instruction 1 1 2 3 4
Instruction 2 1 2 3 4 pipeline
Instruction 3 1 2 3 4
Instruction 2 1' 1'' 2' 2'' 3' 3'' 4' 4'' Super pipeline
In this architecture, the next instruction starts to be executed before the end of the current
instruction. The processing volume is higher than the normal pipeline which means the
instructions have a high dependency.
The compiler's sequencing of instructions and the design of a easily processed instruction set is
important to ensure a smooth flow of the pipeline
eVLIW (Very Long Instruction Word) method
The action of coding multiple tasks in one instruction instead of having short instruction cycles
in pipeline processing is known as the VLIW method. The length of one instruction becomes
long due to the multiple tasks that are defined within it.
Figure 4-2-37 VLIW method
Instruction 1 1 2 3 4
Instruction 2 1 2 3 4
Instruction 3 1 2 3 4
4- 24
4.2.3 Operation mechanism
The procedure of the execution of logic circuits studied in Chapter 1 inside the computer will be
explained using real logical circuits. In the arithmetic unit, there are numeric operation circuits
that handle numeric values and logical circuits that perform logical operations. The following
three operations are basic in logical operations:
Likewise, according to the combination of logical circuits, circuits can be classified as follows:
• Combinational circuits: Addition circuits, identity circuits, etc that establish the output
according to current input.
• Sequential circuits: Flip-flop circuits, etc, that establish the output according to current
and past inputs.
The organization of these logical circuits is shown in Figure 4-2-39.
NOR circuit
4- 25
cAND circuit
AND circuits are the circuits that perform AND operations (logical product operations), as the
one shown in Figure 4-2-40. In these circuits, if both A and B input values are not "1," "1" is not
input. The table shown in Figure 4-2-40 is called the "truth table," and in this case, for the input
"1" (true) or "0" (false") of A and B, the operation results "1" or "0" are indicated. Likewise,
Venn diagram, which clearly represents the operation result, is also displayed.
Besides "A AND B," "AND" operations are represented as "A B" or as “A B"
Figure 4-2-40 or
Figure 4-2-41 represents a comparison between the AND circuit that performs AND operations
and a switch and a light bulb. Here, by establishing a correspondence between the switch
"opens" and "1," and between "closes" and "0," as well as between the light bulb "lights" and "1"
and "does not light" and "0" a truth table can be created.
The electric circuit is often represented using the US army MIL symbol (US MILitary standard,
MIL-STD). Figure 4-2-42 shows the AND circuit represented with the MIL symbol.
dOR circuit
OR circuits are the circuits that perform OR operations (logical sum operations), as the one
shown in Figure 4-2-43. If either A or B input value is "1," "1" is input.
Besides "A OR B," OR operations are represented as "A + B" or as "A v B"
4- 26
Figure 4-2-43 or
Truth table and OR
Venn diagram of
OR operations
Power source
eNOT circuit
NOT circuits are the circuits that perform NOT operations (negation operations), as the one
shown in Figure 4-2-46. The opposite of input value is output. The negation of "1" is "0" and the
negation of "0" is "1". Besides "NOT A, "NOT operations are represented as "A " or as " A."
Power source
4- 27
cEOR circuit (Exclusive logical sum operation circuit)
Figure 4-2-49 shows the truth table, MIL symbol and Venn diagram of EOR operations.
Besides, "A EOR B," EOR operations are represented as “A B” or as "A v B."
It should be noted that "A B" is an operation that means the same as "A B + A B."
Figure 4-2-49 Truth table, EOR symbol and Venn diagram of EOR operations
or A V B
EOR
Figure 4-2-50 Truth table, NOR symbol and Venn diagram of NOR operations
NOR
Figure 4-2-51 Truth table, NAND symbol and Venn diagram of NAND operations
NAND
fAddition circuit
Through the combination of several basic circuits and combinational circuits, circuits that
perform 1-digit binary additions called addition circuits can be created. There are two types of
addition circuits, half adder circuits and full adder circuits.
4- 28
a. Half adder circuit (HA)
The addition of the 1 digit binaries A and B, A + B can be performed in the following four
ways.
0 0 1 1
+0 +1 +0 +1
0 1 1 10
↑
Carry
The circuit that performs these binary operations is created by the combination of one AND
circuit and one EOR circuit. This circuit is called the half-adder circuit. (Figure 4-2-52)
Figure 4-2-52 Truth table of the half-adder circuit and half-adder circuit
Input Output
<Addition of two 1-digit values> <Input> EOR Circuit <Output>
Result
Carry
AND Circuit
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
+0 +1 +0 +1 +0 +1 +0 +1
0 1 1 10 1 10 10 11
The circuit that performs these binary operations is created by the combination of two half adder
circuits and one OR circuit. This circuit is called the full adder circuit.
4- 29
Figure 4-2-53 Truth table of the full adder circuit and full adder circuit
Input Output
Carry
OR Circuit
Flip-flop circuit
Input Output
NOR Circuit
4.2.4 Multi-processor
Multi-processor systems are introduced to improve the performance and reliability of the system.
Multiple processors in parallel with each processor having a dedicated function. When failure
occurs, the processor will do a switch and the remaining processors will distribute the load
among themselves.
(1) Symmetric Multi-processor
Symmetric multi-processors systems are systems where the memory is shared among all the
processors executing the same OS. Competition for the use of memory among the processors
since the memory is common to all. The means a large number of processors cannot be
connected.
Message passing distributed memory multi processor systems are systems where each processor
has its own private block of memory. A high speed input output port is used to transfer the data
between the different blocks.
(2) Array processor
High speed scientific computing is done with array processors which using pipeline processing.
Large scale or dedicated mathematical processors
4- 30
The sub units’ acts are in a queue passing the result to the next unit after it has finished its part.
This is known as vector processing. Most supercomputers utilized this method of high speed
computing.
(3) Parallel
Multiple processors cooperate with multiple tasks being performed to execute one job.
SISD (Single Instruction Single Data Stream)
One instruction stream operating on a single data element and is not parallel
SIMD (Single Instruction Multiple Data Stream)
Each instruction may operate on more than one data element and is synchronous.
Parallel SIMD
The same instruction is executed by all processors operating on different sets of data.
MIMD (Multiple Instruction Multiple Data Stream)
Each processor has its own instruction stream acts on its own data stream independent of the
other processors
4- 31
The clock reciprocal number is called clock frequency. Clock frequency is used as an index to
measure the performance of a personal computer.
Example Performance of a processor with a clock frequency of 500 MHz
500 MHz = 500 × 106 Hz = 500,000,000 Hz (times/second); 500 hundred million pulses per second
1
= 2 × 10-9 = 2 nano (seconds/times); 1 pulse for every 2 nanoseconds
0.5 × 10 9
4- 32
4.3 Memory architecture
4.3.1 Memory types
The storage function, which is the most important characteristic of the computer, is made
possible by the storage units. According to the application, the storage units are divided into
main storage unit and auxiliary storage devices.
Figure 4-3-1
Main storage unit and Brain
65534
65535
The main storage unit is composed of semiconductor elements called RAMs (Random Access
Memory). A RAM's property is such that when the computer is turned off, the contents stored
are lost. Therefore, if there is data to be saved after the process is finished, it is stored in the
auxiliary storage devices.
4- 33
(2) Auxiliary storage devices
The auxiliary storage devices are devices that play the supporting role of making up for the
shortage of storage capacity of the main storage unit. They are also called external storage units.
The auxiliary storage devices are not included among the five main units of the computer, but
they are indispensable for current computers. Large volumes of data and programs are
stored/saved in the auxiliary storage devices and when the data or program required to perform a
process is not found in the main storage unit, it is transferred (copied) from the auxiliary storage
devices to the main storage unit in order to perform the process.
Likewise, the data to be saved after the process is completed is transferred to the auxiliary
storage devices and saved there. Since the auxiliary storage devices have the property that, even
when the computer is turned off, the contents are not lost, they can be used as input/output units
of large volumes of data.
The following are the main auxiliary storage devices.
4- 34
Figure 4-3-3 Memory hierarchical structure
Hundreds of milliseconds Magnetic disk unit, magnetic tape unit, Over tens of M bytes
to hundreds of seconds optical disk unit, magneto-optical disk unit, etc. to 100G bytes
4- 35
4.3.3 Memory configuration
As was mentioned above, the memory used in the computer can be classified into hierarchies. To
provide for the occurrence of malfunctions or failures, these devices are equipped with data error
detection and error correction functions. These functions are implemented by several Error
Correcting Codes (ECC).
(1) Magnetic disk
The series of errors caused by a small scratch, etc, on a magnetic disk are called burst
errors. The Cyclic Redundancy Check code (CRC code) is adopted in the disk unit to detect thee
burst errors. Error detection is possible with the CRC code system.
(2) Magnetic tape
The magnetic tape indicates 1-bye data in the transverse direction of the tape. In order to detect
bit errors in this transverse direction, a parity check system, which can detect odd numbers of bit
errors by appending vertical parity bits, is adopted. In addition, CRC code is adopted to detect
burst errors in a transverse direction
(3) Main memory
In the main memory, due to the high probability of the occurrence of non consecutive random
errors, the Hamming code, which can detect single bit errors and double bit errors, is adopted.
It should be noted that, generally speaking, the main memory error detection is performed in
general purpose computers but it is not performed in personal computers.
(4) Memory protection system
Since various kinds of information is handled in a computer, depending on the characteristics of
the information, a function that limits the users is necessary. This function is called memory
protection and it protects the instructions and data stored in the main memory, auxiliary storage
devices and other memories under specific conditions.
When the memory is accessed, operations like the ones mentioned below are performed:
• Read
• Write
• (Instruction) execute
The right to perform these operations is called access right. Data has read/write rights, but
instructions do not have a right to write. On the other hand, instructions have a right to execute,
but data do not. When an illegal access that violates these access rights occurs, the control is
transferred to the OS as a result of the interruption handling routine.
Like wise, as protection mechanism of the main memory implemented by the hardware, the
protective boundary register system, in which a dedicated register specifies the accessible
4- 36
domains, TLB (Translation Look Aside Buffer) system, which applies the memory protection
function in a virtual address space, etc, exist.
4- 37
4.4 Auxiliary storage devices
Figure 4-4-1
Magnetic tape Magnetic tape unit
Diverse auxiliary
storage devices Magnetic disk unit
Magnetic disk
Floppy disk unit
(Flexible disk unit)
Auxiliary storage devices
Magneto-optical Magneto-optical disk unit
disk
4- 38
(1) Magnetic disk unit
Magnetic disk unit is devices that store data using magnetic disks. It is the auxiliary storage
device most widely used in today's computer systems. Magnetic disks for personal computers or
workstations are also called fixed disks or hard disks but the mechanism is the same.
Figure 4-4-2
Magnetic disk unit
cMagnetic disk
a. Track
The magnetic disk is a circular shaped magnetic body in which data is recorded along rings
called tracks. There are several tracks concentrically set on the magnetic disk. The length of the
outer track and that of the inner tracks differ, because of the difference of the storage capacity,
the volume of data stored is the same in every track.
The storage density of the disk is based on the average track length and the storage capacity
of the magnetic disk is determined by the number of tracks and the storage density of one disk.
b. Cylinder
In a magnetic disk unit, which is composed of multiple magnetic disks, the group of tracks
with the same radius on each of the disks is set as one data storage area. This storage area is
called a cylinder.
When data is stored in a cylinder, if, for example, the data cannot be completely stored on
track 0 of cylinder 1, it can be stored on track 1, track 2, etc. of the same cylinder. Therefore,
since data access can be performed without moving the access arm (that is, magnetic head), it is
4- 39
extremely efficient.
To put it in another way, the cylinder is a group of tracks that can be read and written by
multiple magnetic heads if the access arm of the magnetic disk unit is fixed.
c. Storage capacity
The storage capacity of the magnetic disk can be determined as follows:
Storage capacity of 1 track x Track number of 1 cylinder x Cylinder number of the
magnetic disk
Example
Given a magnetic disk with the following specifications, the storage capacity of this
magnetic disk is calculated:
[Magnetic disk specifications]
4- 40
• Track number /cylinder number : 19 tracks
4- 41
Figure 4-4-5 Structure of the magnetic disk unit
Recording of the character code of A
Parity bit
Track
Direction of
rotation
Magnetic disk
Reading/writing head
Rotation axis
Access
arm Magnetic
disk
• Variable type
In the variable type unit, data reading and writing is performed on a block basis, as in
the magnetic tape. A block is a group of data called record and there is an IBG between
blocks. In the unit, there is no gap between data or IBG). Reading and writing of any
number of bytes can be started from any track position
• Sector type
In the sector type, one track is divided into approximately 20 small units called sectors.
Data reading and writing is performed on a sector basis. The reading/ writing position is
specified with the sector number of the selected track
4- 42
Figure 4-4-6 Variable type and sector type
<Variable type>
Block Block Block
IBG Record Record Record IBG Record Record Record IBG Record Record Record IBG
1 Track
Data
Data A Data B Data D
C
IBG
<Sector type>
1 Sector 1 Sector 1 Sector 1 Sector
Data Data
Data A Data C
B D
Generally, the variable type is used in magnetic disks, and the sector type is used in floppy disks
and hard disks
Generally, the variable type is used in magnetic disks, and the sector type is used in floppy disks
and hard disks.
b. Parity check
When data is recorded on a magnetic disk, data is written on the track bit by bit using the
magnetic head. The same method is used to read data. When this process is performed, as in the
magnetic tape, in order to detect reading or writing errors, a parity bit (1 bit) is appended to
perform the parity check.
c. Defragmentation
In personal computer hard disks, data is stored and deleted repeatedly. Since it is improbable
that all the data to be stored will have the same size, a small volume of data can be stored after a
big volume of data is deleted, or vice versa. As a consequence, there would be free sectors
scattered about and a drop in access efficiency. This status is called defragmentation; in order to
solve it, a function called defragmentation is implemented in the OS.
eMagnetic disk unit performance
The performance of the magnetic disk unit is measured according to access time and storage
capacity. Since the storage capacity was already explained in , here, the access time
significance and the calculation method will be explained.
a. Access time
Access is the generic term for the act of reading specific data from the magnetic disk and
writing it on a specific cylinder or track. Access time is calculated through the addition of the
following:
4- 43
• Seek time
• Search time
Figure 4-4-7
Seek time Seek time
Rotation axis
Since seek time differs depending on the distance between the position of the target track and the
current position of the magnetic head, an average value is sued as the actual seek time. This
value is called average seek time.
Search time
The search time is the elapsed time until the target data reaches the magnetic head position.
(Figure 4-4-8)
Search time
Figure 4-4-8
Search time Movement
Magnetic head
Rotation axis
As with average seek time, depending on the data position, there are cases where the search
time is 0, as well as cases where a wait of 1 revolution is. Therefore, 1/2 revolution of the
magnetic disk is used as the search time. This value is called average search time.
4- 44
Data transfer time
The time elapsed between when the magnetic head data access starts and when the transfer is
completed is called data transfer time.
Therefore, the time elapsed between when the magnetic disk unit starts access and when the data
transfer is completed, that is, the access time, is calculated as follows:
Seek time + Search time + Data transfer time
Strictly speaking, as in the above mentioned formula, the time elapsed between when the access
request occurs and the magnetic disk starts operating is the access time.
Access time of the magnetic disk unit = Average seek time + Average search time +
Data transfer time
Example
Given a magnetic disk unit with the following specifications, the access time of this magnetic
disk when a record of 9,000 bytes is processed is calculated.
[Magnetic disk unit specifications]
4- 45
(2) Floppy disk unit
The floppy disk unit is also called a flexible disk unit. In floppy disk units data random access is
possible, and, since the floppy disk itself, which is storage medium, is low-priced and easy to
carry about, its use has widely spread. As an auxiliary storage device of personal computers, it is
the most ordinarily used device.
Label area
Write-protect
notch
3.5 inches
(There are also disks of 5 inches and 8 inches)
The recording method of the floppy disk is the sector method, and as it is shown in Figure 2-4-
10; the track is divided into sectors, and the data is recorded on a sector basis.
Figure 4-4-10
Data recording side
of the floppy disk
Tracks
Sector
cFloppy disk
a. Types
Among floppy disks, there are magnetic disks that measure8 inches, 5 inches and 3.5 inches, but
the most common disks today are 3.5 inch disks, while 8 and 5 inch disks are almost never used.
There are also the following 2 types of 3.5 inch floppy disks, depending on the storage density.
4- 46
Figure 4-4-11 1.4MB 1.2MB
Example of the specifications Sides available for use
of a floppy disk (2HD) Track number/side
Sector number/track
Storage capacity (B)/sector
Likewise, there is a floppy disk whose storage capacity is 120 MB (UHD) and a disk called Zip
whose storage capacity is 100 MB. Both of them are compatible with the 3.5 inch disk
(2DD/2HD), but they have not come into wide use.
b. Storage capacity
The calculation of the access time of floppy disk units is the same as that for magnetic disk
units. Therefore, here, the storage capacity of the sector method will be explained.
As was shown in Figure 4-4-11, among floppy disks, the sides available for use, the number
of tracks per side, the number of sectors per track, etc. differs.
The storage capacity of a floppy disk is calculated using the following values:
Storage capacity per sector x Number of sectors per track x Number of tracks per side x
Number of sides (One side or both sides)
Example
Given a floppy disk with the following specifications, the storage capacity is calculated.
[Specification of a floppy disk]
4- 47
floppy disk is used and the sector method, in which the tracks are divided into sectors, is the
recording method.
The number of tracks and the division of the sectors depend on the operating system used.
Therefore, when the user uses a floppy disk, it has to be initialized in the format specified by the
operating system. The process is called formatting.
When the floppy disk cartridge is installed in the floppy disk unit, the disk contained in the
cartridge rotates. The magnetic head directly traces the magnetic disk surface of the disk, in
order to read/write information; the data access time is longer than that of the magnetic disk unit
and the magnetic tape unit.
Figure 4-4-13
CD-ROM unit
4- 48
Among optical disks, there is the music CD (Compact Disc), the CD-G (CD Graphic) for image
data, the CD-I (CD Interactive) for interactive applications, the CD-R (CD Recordable), etc. And,
the as a computer storage medium, the CD-ROM (CD Read Only Memory) is widely used.
Furthermore, as an optical disk that supports the multimedia era, the DVD, which has great
capacity and high image quality and is capable of storing animated images and audio, exists.
Here, the CD ROM and the DVD specifically will be explained.
dCD-ROM
The CD used as a computer storage medium is the CD ROM. The external appearance , diameter,
thickness, etc of the CD-ROM is the same s that of a CD (diameter: 12 cm, thickness: 1.2 mm,
single disk diameter: 8 cm), but the error correction function, file system, logical format, etc.
differ. Since the CD-ROM logical format uses the international industrial standard ISO 9660, it
has high compatibility.
However, since the CD-ROM is a read only disk, data can be read but cannot be written.
a. Structure
The CD ROM, which is a disc-shaped storage medium, does not have a concentric track
structure as does the magnetic disk or floppy disk. Tracks of continuous sectors are
connected in a spiral as in vinyl records and the data is stored from the inner side to the outer
side. Figure 4-4-14 shows a magnification of the data recording surface of the CD ROM.
The CD ROM stores ")" and "1" information using the pits and lands of the data recording layer.
In order to read out data, a laser beam is applied and the optical head reads out the changes in
intensity of the reflected light.
b. Storage capacity
By creating a master disk with a negative replica of these pits and lands and pressing it against
plastic disks, a large quantity of CD ROMs can be replicated at high speed and low cost.
1 CD ROM (12 cm) has a storage capacity of approximately 600MB which makes it an
indispensable storage medium to process the enormous volume of information of multimedia
4- 49
data.
eCD ROM unit structure and performance
a. Structure
Basically, the structure of the CD ROM unit is the same as that of the magnetic disk unit. The
difference is that data is not read out using a magnetic head, but an optical head that detects the
laser beams.
b. Performance
The CD ROM unit performance is measured according to the head seek time and the data
transfer rate.
Seek time
The CD ROM seek time is extremely slow compared to that of the magnetic disk unit. While
the seek time of the magnetic disk unit is measured in tens of milliseconds, it is measured in
hundreds of milliseconds in the CD ROM unit. This is due to the use of a heavy lens in the read
head and to the CD ROM structure (the data storage format uses a spiral track as in a vinyl
record).
Transfer rate
The data transfer rate is expressed in numeric values that represent how much data can be
transferred in comparison with audio CDs. The audio CD player can read approximately 150k
bytes of data in 1 second, which is an extremely low rate as compared to computer processing
speed. Therefore, units with transfer speeds 2 times or 3 times as fast as the transfer rate for
audio CDs began to be developed and today the transfer rate has reached levels of 10 times and
20 times as fast.
fOptical disk specifications
The optical disk, which was born from the audio CD and is widely used as a computer storage
medium, has multiple variations that make the best use of its high storage capacity, portability,
mass production through press replication processing, and other advantages. The standard
specifications of these optical disks have been established and the basic standard of each of them
is called red book, yellow book, etc.
These names were given after the color of the cover of the binder in which the standard
specifications were kept.
Red Book CD CD-G addition
Figure 4-4-15
Optical disks Yellow Book CD-ROM CD-ROM XA addition
• Yellow Book
The Yellow Book is the basic CD standard and describes the physical format of the CD-
ROM. As an extension to the Yellow Book, the CD-ROM XA , which made possible
extended audio playback and multiple graphics recording, is also specified and
its specification becomes the bridge between the CD-ROM and the CD-I.
• Green Book
The Green Book describes the specifications of the CD-I (CD-Interactive), which is
capable of storing audio, images, CGs, characters, programs, data etc.
• Orange Book
The Orange Book defines the physical structure of the CD-R (CD-Recordable) , a
writable CD
Among the CD-Rs, the CD-WO (Write Once), a recordable type in which once
information is written, the content cannot be rewritten, and the CD-MO (CD-Magneto
Optical) a re-writable type which can be rewritten exist. this CD-R is used in photo CDs
(camera film images recorded in CD)
gDVD
The DVD *(Digital Versatile Disk or Digital Video Disk) is an optical disk capable of storing
approximately 2 hours of animated images and audio data. The external appearance of DVD
disks is the same as that of CD-ROMs, 12 cm of diameter and 1.2 mm of thickness. However,
while the recording side of the CD-ROM consists of one side (1 layer), the DVD has a maximum
of 2 layers, and data can be stored on both sides.
12 cm
Figure 4-4-16
DVD structure
0.6 mm Second layer
Lens
Laser beam
At present, DVD-ROMs are commercialized and can be played on DVD players. Likewise, the
use of DVD-ROM units in personal computers is expanding.
4- 51
DVD-ROM storage capacity is as follows:
4- 52
(5) Semiconductor disk unit
<Writing principles of the MO disk>
Figure 4-4-17 Rotation
Magnetic head
Data reading and writing Writing with a
magnet
operation of the magneto
MO disk
optical disk unit Heating with
laser beam
Laser head
MO cross
section
The semiconductor disk unit is a storage unit of high speed and large capacity, which uses flash
memories and other devices. In most cases, it is used in high end mainframe computers as a
storage unit positioned between the main storage unit and the auxiliary storage devices. It ha the
advantage that, despite having several G bytes of storage capacity, its access time is 1/100 that of
the magnetic disk unit.
4- 54
4.5 Input/output architecture and devices
Since there are many mechanical operations in the input devices and the output devices, a wide
gap between the operation speed of these devices and that of the processors which perform
electronic operations only, is generated. If, ignoring this operation speed gap, the processor and
the input or output device are connected, the operation speed of the whole computer system will
become slow. And as a consequence, the computer characteristic of high speed processing
becomes ineffective.
In order to solve this problem, input/output control and interruption are performed.
• DMA method
• Address bus
• Control bus
• Data bus
cAddress bus
The address bus connects the main storage unit and the processor. This bus is used for the
specification of the main storage unit address by the processor.
Figure 4-5-1
Main storage unit
Address bus 1 word (16 bits) Address 0
Address decoder
4- 55
dControl bus
The control bus connects the main control unit and the main storage unit. This bus is used for the
transmission of the instruction signal to the main storage unit from the control unit.
Figure 4-5-2
Control bus Main storage unit
1 word (16 bits) Address 0
Address decoder
1 word (16 bits) Address 1
Processor 1 word (16 bits) Address 2
Control
unit
1 word (16 bits) Address 65535
Read/write controller
Control bus
eData bus
The data bus connects the main storage unit and the processor and is used to exchange data. Only
this bus is used to exchange data between the main storage unit and the processor in both
directions.
Control
unit Address 65535
1 word (16 bits)
Read/write controller
4- 56
Figure 4-5-4
Direct control Main storage
Processor Peripheral devices
method unit
Data flow
Control flow
DMA request
Data flow
Control flow
• Serial interface
• Parallel interface
(1) Serial interface
The interface that supports serial data exchange between the computer and the input
device/output device is called the serial interface. The serial interface is the transfer method
conducted by lining up data of 8 bit or 16 bit processing units in one row and transferring one bit
at a time (Figure 4-5-6). The data transfer rate is lower than that of parallel interface, but it has
the advantage that only one transmission channel is required. Since during a serial transfer there
is no signal delay, long distance transfers can also be performed.
4- 57
The following serial interfaces are widely used:
Figure 4-5-6
Serial transfer
Data
Serial interface cable
cRS-232C
The RS-232C is an interface that connects the computer, and the modem that converts digital
signals into analog signals, or vice versa (Figure 4-5-7). This interface was standardized by EIA
(Electronic Industries Association) and the physical connector format, pin number, pin role, etc
are strictly established.
<Characteristic>
• Transfer units: the start bit that indicates the start of 1 byte data: 1 bit, the top bit that
indicates the end: 1 bit, the parity bit used for error detection: 1 bit. A total of 11 bits.
• The mainstream in transfer rates are 28.8 kbps and 33.6 kbps.
• Besides the modem, it is widely used to connect image scanners , mouse and other
peripheral devices and personal computers
Mouse
dUSB
The USB is a new interface standard by which, besides the keyboard, modem and other
peripheral devices, audio signals, image data and other input/output device data can be processed
indistinctly with one connector (Figure 4-5-8). According to the USB specification, when a
peripheral device is supported by the USB is connected, the personal computer automatically is
configured. The connection of cables has also been simplified and its use as an input/output
4- 58
interface for multimedia systems is attracting attention.
Figure 4-5-8
USB interface Modem
connection example
Keyboard
Audio equipment
eIEEE 1394
IEEE 1394 is a serial interface used to send animated image data in real time. Since real time
transfer is supported, animated images can be smoothly represented. Therefore, IEEE 1394 is
sued as a multimedia interface supporting connections such as those between digital video
cameras and personal computers.
The maximum data transfer rate is 400 Mbps and a connection of a maximum of 63 nodes can
be performed.
fIrDA (Infrared Data Association)
The IrDA is an interface for wireless (infrared) data transmission. It has the advantage that, since
connection cables are not used, layout modifications inside the office can be easily performed.
There are several IrDA versions, and the transmission speed ranges between 2.4 kbps and 4.0
Mbps. These versions are equipped in PDA (Personal Digital Assistant) and notebook type
personal computers.
• Centronics interface
4- 59
Figure 4-5-9
Parallel transfer
cCentronics interface
The Centronics interface is a printer interface developed by the U.S. company, Centronics Data
Computer (Figure 4-5-10).
It is not an interface formally standardized by an international industrial standard organization,
but, since it has been adopted by a very large number of manufacturers as the interface to
connect printers and personal computers, in practice, the Centronics interface has become the "de
facto standard printer interface).
<Characteristic>
Figure 4-5-10
Data flowing in
Centronics interface one direction
connection example
Printer
dSCSI
The SCSI was approved as a personal computer standard interface by ANSI (American National
Standards Institute).
<Characteristic>
• The transfer rate ranges between 1.5 and 4 Mbps but the transfer rate of SCSI-2, an
extensive enhancement of SCSI, is 20 Mbps.
• Up to 8 auxiliary storage devices, such as the hard disk unit and the CD-ROM unit, can
be connected one after another. This is called daisy chain. An ID (a number to
4- 60
distinguish the devices) is assigned to the connected devices and a resistor, called a
terminator, that indicates the termination, is attached. (Figure 2-5-11)
Terminator
Maximum of 8 units
eGPIB
The GPIB was originally approved as a standard interface to connect microcomputers and
measurement instruments, but it is currently an interface with a wide range of uses that connects
the microcomputer and its peripheral devices.
This interface was standardized as IEEE-488 by the U.S. Institute of Electrical and Electronics
Engineers (IEEE).
<Characteristic>
4- 61
Figure 4-5-12 synthesizes the above mentioned input/output interfaces.
Figure 4-5-12
Types of input/output Name Transfer rate
Connected
Content
Industrial
devices standard
interfaces Modem Connector format and role
28.8kbps
33.6kbps Printer Pin number and role
RS-232C 56kbps Mouse EIA standard
Plotter, etc.
Figure 4-5-13
Roles of input devices Process Process
Data result
and output devices Input Computer
Output
device
device
The input device is a device exclusively used to transfer information to the computer, and the
output device is a device that represents the result of the computer process in a format that can be
understood by us. But there is also a device equipped with both functions. It is called the
input/output device.
(1) Input devices and output devices
The device that enters data and programs into the computer is called the input device, and the
device that represents/outputs computer data and programs is called the output device.
4- 62
cInput device
An input device is a device that converts data that can be understood by humans such as numeric
values, characters, images and audio, into a data format (0 and 1 combination) that can be
understood by computers, and loads it into the computer main storage unit.
Figure 4-5-14
Input device's role
The early computers wee limited to processing characters and numeric values, but with the
progress of information technology today, computers can also process image and audio data. The
different types of input devices tat can process all these kinds of information are shown in Figure
4-5-15.
Figure 4-5-15
Various input devices Keyboard
Track ball
Image scanner
Joystick
Digitizer
Light pen
Digital camera Touch screen
dOutput device
Output device is the general term for the devices that convert the data processed in the computer
(which processes all the data using 0s and 1s to produce results which are combinations of 0s and
1s into data that can be understood by humans such as numeric values, characters, images, still
images, animated images and audio , and output it.
4- 63
Figure 4-5-16
Output device's role
As in the input devices, there are different kinds of output modes for the output devices (Figure
4-5-17), For example, if the output is divided into "Display" and "Printing," it can be classified
into the following two types:
Plotter
(2) Keyboard
The keyboard, which is the input device we find most familiar, inputs the code corresponding to
the key of the character or symbol we press in the processing unit. A keyboard layout is specified
by a JIS (Japanese Industrial Standard). However, in order to improve the efficiency of
Japanese input, some word processor manufacturers have developed unique keyboard layouts of
their own.
4- 64
Figure 4-5-18
Keyboard
Figure 4-5-19 shows the correct finger position to be assumed to press the keys. Once, one gets
used to it, it becomes easy to press the correct keys without looking at the keyboard. The typing
method is called touch typing.
Figure 4-5-20
Optical character reader (OCR)
At the beginning, the optical character reader could only read easily identifiable special printed
characters and JIS OCR fonts (Figure 4-5-21). However, at present, the character pattern
recognition has improved and even handwritten characters can be recognized.
Figure 4-5-21
OCR fonts
123 123 A C E
ABC ABC G I J
OCR-A OCR-B OCR-K
4- 65
(4) Optical mark reader (OMR)
The optical mark reader is the device that reads and inputs data according to the marks made on
marksheets.
Alphanumeric characters are printed on marksheets; the part to be input is marked with a pencil,
etc. The difference with the optical character reader is that this device does not directly recognize
the patterns of characters or numeric values, but reads them out based on the marked position
instead. The information reading principle is the same as that of the optical character reader.
based on the reflected light, this device judges whether or not marks exist and inputs the
character or numeric value corresponding to the marked position. Therefore, there are cases
where reading errors occur or reading cannot be performed -- when marksheets are dirty or
folded.
Figure 4-5-22
Optical mark reader (OMR)
Since the mark reading position is set through the program, the pattern of the marksheet can be
freely designed. In practice, marksheets are used in different fields, and are also used as answer
sheets in the Information Processing Engineer Examination.
Figure 4-5-23
Marksheet example
• Pen type
• Touch type
• Laser type
when the pen type device is used, the bar code has to be traced with LED (light emitting diode).
With the touch type device, the LED only has to be focused on the bar code (Figure 4-5-24).
4- 66
Likewise, since it his not necessarily to directly touch the bar code with the laser type device, it
is widely used in convenience stores and super markets.
Figure 4-5-24
Bar code reader
Generally, in account processing using bar codes, not only product identification and accounting
are performed, but also, based on the information input, stock control and order control are
performed.
(6) Magnetic card reader
The magnetic card reader is a device that reads and inputs the information needed from a
magnetic card.
There are different types of readers depending on the magnetic card to be read. Automatic train
ticket gate machines are also magnetic card readers.
The magnetic card is a paper or plastic card which has a magnetic strip on the surface to store
information such as numeric values and characters.
At present, as it is said, we live in a "card society" and magnetic card use has widely expanded as
paying method that replaces cash in our daily life. Among the most familiar cards, we have the
following:
• Phone cards
• Cash cards
• Credit cards
• Track ball
• Joystick
• Light pen
• Touch screen
Without the troublesome operations on keyboards, etc, using any of these devices, anybody can
easily input data while watching the screen of the display unit.
cMouse
Along with the keyboard, the mouse is the most used input device. It was named mouse due to
the similarity of its external appearance to a mouse.
Figure 4-5-25
Mouse
The mouse has a mechanism by which, when it is moved, the ball on the underside rolls, and the
screen pointer moves according to the rolled distance and direction. When the pointer has been
moved to the aimed position, by pressing the button of the mouse, the positional information is
entered. This operation is called clicking. Likewise, as it is shown in Figure 4-5-26, besides
clicking, there are other button operations such as double clicking, which mean processing the
button two times and dragging, which is the specification of an area by moving the mouse while
holding the button down, etc.
The biggest characteristic of the mouse is that, unlike the keyboard, it does not input data directly
to the computer; instead, by pointing at the icons and windows indicating the operation locations
which appear on the screen, it indicates and inputs operations to the computer. In other words,
4- 68
the mouse supports the GUI (graphical user interface) environment.
dTrack ball
The principle is the same as that of the mouse, but, since the track ball is moved directly with the
fingers, it does not require the moving space needed by the mouse. For that reason, it is often
equipped in lap top and notebook personal computers.
Figure 4-5-27
Track ball
eJoystick
With the joystick, the stick is moved back and forth as well as to the right and left, and the
pointer moves according to the direction and the angle in which the stick is moved. It can
perform the same operations as the mouse, but, since indications have to be performed with
buttons, etc. besides the stick, it is not so easy to handle as the mouse, which can be manipulated
with one hand, For that reason, joysticks are widely used for game software manipulation.
Figure 4-5-28
Joystick
fLight pen
The light pen is a device that inputs the coordinate information by pointing and tracing on the
screen of the display device directly.
Since the optical sensor at the point of the light pen detects the position of the information on the
screen and inputs it, the responsiveness is high.
As the uses of the light pen, data entry on palm top personal computers entry, and the entry of
handwritten characters into a word process can be mentioned.
4- 69
Figure 4-5-29
Light pen
gTouch screen
The touch screen, which is also called a touch panel, takes advantage of the static electricity that
passes through the human body. By directly touching with the finger the screen of the display
device, the positional information is entered. I n this mechanism, a transparent panel is attached
to the screen surface and the sensor on the panel senses changes in the voltage and detect the
touched position.
Due to the dimensions of the area touched with the finger, detailed manipulations and
instructions can not be performed, but since it can be easily manipulated by anybody, it is widely
used i the automatic teller machines (ATMs) of banks, automatic ticket vending machines at
train stations, reception/information at hospitals, etc.
Figure 2-5-30
Touch screen
4- 70
Figure 4-5-31
Image scanner
(9) Digitizer
The digitizer is a device that, by tracing a plane panel figure with a pen or cursor, detects the
coordinate’s position and, based on this consecutive coordinate information, inputs the figure.
This device is used by the CAD (Computer Aided Design) application, in which the input of
figures of high precision is required. Small sized devices are sometimes called tablets for making
a distinction.
Figure 4-5-32
Digitizer
Figure 4-5-33
Optical camera and <Optical camera> <Digital camera>
Film CCD
digital camera
mechanism
4- 71
(11) Display device
In ordinary computer systems, operations are conducted verifying on the spot the input data and
process results on the screen. The display device is one of the devices which are indispensable
for human use of computers. Displays are roughly divided into the following two types:
• Color displays
At present, color graphics displays are the standard. Furthermore, according ton the structure of
the display screen, display devices can be classified as follows:
• CRT displays
Figure 4-5-34
CRT display
a. Mechanism
As it is shown in Figure 4-5-35, in the CRT display, when struck by the electron beam, the
fluorescent screen emits light, which is displayed on the screen.
4- 72
Figure 4-5-35
CRT structure
Electron beam
Color display is generally used in CRT displays. Color images are represented by striking the
dots that contain the "three primary colors of light," R,G, and B (Red, green, blue) with the
electron beam.
Figure 4-5-36
R R R
Color screen diagram G B G B G B
magnification R R R
G B G B G B
R R R
G B G B G B
Besides the above mentioned, the screen display is equipped with an important function called
screen saver. In the CRT display, when the same screen is displayed for a long period of time,
the image of that screen is burnt into the fluorescent tube. In order to prevent
this, an animated image is displayed on the screen. This software is called screen saver.
b. Resolution
The screen size is represented by the diagonal length of the screen. According to this, there are
screens of 15 inches, 17 inches, 21 inches, etc.
The screen resolution is represented by the value of the number of dots which can be
represented in 1 screen (width x height), and resolution of 640 x 480, 800 x 600, 1024 x 768,
1280 x 1024, etc. Today, as a result of the expansion of multimedia, 1280 x 1024 resolutions has
become a de facto standard due to its capacity to process high image quality. Likewise, the CRT
display called multi scan monitor, in which the resolution can be switched according to necessity,
is expanding.
dLiquid crystal display
The liquid crystal display is a display device widely used in the display screen of calculators, etc.
(Figure 4-5-37). The liquid crystal material used has the property of aligning in one direction
when voltage is applied, changing from non transparent to transparent. The liquid crystal display
takes advantage of this property, and by controlling whether or not light passes through it with
the voltage applied, the appropriate display is produced.
Currently, the majority of liquid crystal displays are also color displays that use R, G, B color
filters.
Unlike CRT displays that require a specific depth, liquid crystal displays are thin, and moreover,
4- 73
have low power requirements. Due to these reasons, they are widely used in lap top and
notebook personal computers.
Figure 4-5-37
Liquid crystal display
• Impact printers: Print by mechanically hitting preformed characters against an ink ribbon.
4- 74
Here, among the different types of printers, the printers indicated below will be explained:
Figure 4-5-38
Dot impact printer
Figure 4-5-39
Ink-jet printer
fLaser printers
The laser printer is a page printer that, using toner (powder ink), creates the printing image of
one page on the photoreceptive drum and transfers it to the paper through the application of laser
beams.
The printing principle is the same as that of copy machines, and the character size, space
between the lines, etc can be selected freely. Figures, images, etc can also be printed and print
quality as well as printing speed are high. For that reason, it is the mainstream printer for
business use.
Figure 4-5-40
Laser printer
4- 76
4.6 Computer types
4.6.1 Computer types
Computers used in a great variety of field will be explained below.
(1) Personal computer
As the name implies, personal computers are computers that were developed for personal use,
commonly called PCs for short. Based on their external appearance, different types of personal
computers have multiplied. These personal computers can be classified as follows:
• Notebook type, the size of A4 or B5 paper, thin and light (Figure 4-6-2)
Likewise, expansion of the palm top type (Figure 4-6-3) ultra small-sized personal computers
which can be held in one's palm is starting.
On the other hand, according to the place where they are set up, and the main use purpose,
computers can be classified as follows:
• Home: Used as word processors and to play games at home and hobby
computers.
• School and enterprise: used in CAI (Computer Aided Instruction) application for
education
Likewise, considering the sue mode, up to now, stand-lone system was used in most computers,
but recently, the network system in which personal computers are connected by communication
lines is becoming the mainstream.
Figure 4-6-1
Desk-top type
4- 77
Figure 4-6-2
Notebook type
Figure 4-6-3
Palm-top type
(2) Workstation
Due to the expansion of use of personal computers, enterprises are adopting the system of one
computer per user. However, personal computers lack the capacity to perform technological
calculation processing, software development, etc. In order to solve this problem, computers
called engineering workstations
(EWS) were created. Compared to personal computers, workstations are capable of performing
high quality image processing, etc with high speed (Figure 4-6-4).
The main applications of these workstations are listed below:
4- 78
Figure 4-6-4
Workstation
Figure 4-6-5
General-purpose
computers
4- 79
• Weather forecast
Figure 4-6-6
Supercomputer
(5) Microcomputer
Microcomputers are small sized computers into which a processor is built. The computers that
are imbedded into machines, especially household appliances such as washing machines, air
conditioners and AV appliances, in order to control the machine operation are called
microcomputers. These microcomputers are electronic parts with bare integrated circuits.
According to the purpose, information on the temperature and number of revolutions can be
entered using a sensor. Since their function is to repeat the same operation, control data is
recorded in ROMs (Read Only Memory). Likewise, since the output devices are
motors or electric switches, they are also called actuators.
Figure 4-6-7
Microcomputer
4- 80
immediately controls each machine and adjusts the production process.
In addition to this, centralized control and automation have been achieved through the use of
process control computers in power system control, general building security systems, highway
traffic control, etc.
4- 81
4.7 Wireless standards and Mobile computing
Wireless LAN is an alternative to the traditional cable based LANs. It sends information
among the devices but without the constraint of physical cabling. This means wireless
Wireless is also a good choice if the physical structure of the building makes it
Portable computers benefit from the use of wireless LANs allowing them to be truly
portable without being tied by a physical wire to a network. Wireless networks can be
The common standards used are Bluetooth and IEEE 802.11 wireless Ethernet. Both
i) spread spectrum
iii) infrared.
4- 82
Spread Spectrum
This is the most commonly used transmission method for wireless LAN. The signal is
spread over a range of frequencies comprising Industry, Scientific and Medical (ISM)
bands. The frequency range is 902 MHz to 928 MHz and 2.4 GHz to 2.484 GHz. A
The signal is broadcasts over a seemingly random series of frequencies. The receiver
receives the message in synchronization with the sender. This means the message can
only be received if the frequencies are known. The frequency hopping spread spectrum
is limited to the 2.4-GHz band based on standards set by the IEEE 802.11 committee.
spectrum Redundant data bits called "chips" are added to the sequence to spread their
transmission.
4- 83
A correlator is used by the receiver to remove the chips and reduce the signal to its
original length.
The practical raw data throughput is up to 2 Mbps in the 902-MHz band and 8Mbps in
the 2.4-GHz band. Frequency hopping radios currently use less power than direct
Narrowband Microwave
dishes are used at both ends of the link. A line of sight is required for the signal
Infrared
Infrared signals are used to transmit the data. The technology is similar to those found in
The main advantage is a high bandwidth is supported. However, they can be easily
4- 84
The following compares the different kinds of Wireless LAN Transmission Techniques.
Narrowband
Spread Spectrum Infrared
Microwave
902MHz to 928 MHz ; 18.825 GHz to 19.205
Frequency 3 x 10^14 Hz
2.4 GHz to 2.4385 GHz GHz
Transmission power Less than 1 W 25 mW Not applicable
Use between
Possible with antenna No Possible
buildings
Line of sight No No Yes
Maximum coverage 30 to 240 m up to 15 km 12 to 39 m up to 1.5 km 9 to 24 m
4.7.2 Bluetooth
L. M. Ericsson invented Bluetooth in 1994. This technology is used for short range
Multiple devices can form overlapping networks called piconets in an ad-hoc fashion.
Bluetooth is a radio link and therefore does not require line-of-sight (LOS)
Piconet
4- 85
Scatternet
IEEE 802.11 is intended for use inside buildings such as offices, hospitals, banks. shops.
4- 86
4.7.4 Network Architecture
A wireless station, usually the PC or a Laptop with a wireless network interface card
(NIC), and an Access Point (AP) is used in the 802.11 network architecture. The Access
Point acts like a bridge between the wireless stations and wired networks.
1) Infrastructure Mode
2) Ad Hoc Mode.
Infrastructure Mode
The wireless stations communicate with each other through the access point. They do not
directly communicate with each other. The frames are relayed by the Access Point.
4- 87
Extended Service Set (ESS)
The access points conveys the messages with each other to carry the message from one
BSS to another.
Ad Hoc Mode
The wireless stations communicate directly with each other. They are no access points.
4- 88
4.7.5 Security
- Reaching the resources of the network by using the same wireless equipment.
prove its knowledge of a key, what is similar to the safety(security) on cable networks, in
the sense(direction) where the intruder should enter places (by using a physical key)
Eavesdropping
The generator of random numbers re-releases a sequence of keys of random bits, equal in
length to the widest possible packet, which, combined with entering or outgoing packets,
The algorithm WEP is a simple algorithm based on RSA's algorithm RC4, which has the
following properties:
1) Reasonably hard: the attack by brute force of this algorithm is difficult by the fact
that every frame is sent with a vector of initialization which re-launches the
4- 89
This is necessary to work in non connected mode, where packets can be lost, as in any
Data rate
Bluetooth has a maximum capacity of 1 Mbps. This is compared to the, now standard,
1) User mobility
2) Device portability
4- 90
This creates the need for mobile communication to integrate
1) Cellular phone
Cell phones are increasing, become smaller and have more functionality. They come
with a display and include SMS, internet and fax capabilities. Some recent models even
2) Attachable keyboard
4- 91
4.7.8 Type of software
(1) Microbrowser
These are used to view online content created by using the WML (Wireless Markup
Language). These are WAP (Wireless Application Protocol) based devices. A different
standard called i-mode is adopted in Japan using the CHTML (Compact HTML). The
new WAP 2.0 standard has adopted XHTML as the standard. XHTML merges HTML
with XML leading to a standard that allows content to be created for both the mobile and
desktop computing.
XHTML
XHTML is based on XML standards. This means a document must follow "well formed"
1) XML is case sensitive. In XHTML this means every HTML tag must be written
3) Non-empty tags must be properly nested. This means tags do not cross over each other.
In the invalid example below notice that the form and table tags are improperly nested,
4- 92
should be corrected to
4) Attribute values must be within quotes. So <form action=[Link]> is not legal but
5) All tags must be closed. For tags which don't normally have a closing element, end the
For example, <br> by itself is not legal. Rather, use <br/>. These tags may also end
like </br>, but <br/> syntax seems to work better with current browsers.
7) The first tag in a XHTML document must be <!DOCTYPE>. This tag informs the
reader which definition to use in describing the XHTML document. XHTML uses
DTD modules to translate tags. In selecting among the three DTDs follow these rules.
When writing for the most HTML compatibility use the transitional DTD :
4- 93
8) The second tag in a XHTML document must be <html> and the xmlns attribute is
mandatory.
10) Form tags must have an action attribute. For example, <form action="[Link]">
</form>
11) Style tags such as <font> and <center> have been removed. Use style sheets for
formatting.
14) Scripting elements pose a problem for XHTML compatibility. The XML parser will
parse the script as a XML document unless you enclose your script in a CDATA
<script type="text/javascript">
<![CDATA[ alert("hello"); ]]>
</script>
These are operating systems like Windows CE, Palm OS etc. There are specialized OS
4- 94
4.7.9 Mobile based protocols
1G AMPS (Advanced Analog voice service
wireless Mobile Phone Service) No data service
3G
Third generation (3G) services combine high speed mobile access with Internet Protocol
(IP)-based services Japan's NTT DoCoMo launched the world's first official 3G system
4- 95
Layers used in mobile communication
The cell phones utilizes high frequency radio waves in the range of 806 to 890 MHz or
1,850 to 1,990 MHz to communicate with cell towers. A request is made to the tower to
If sufficient resources are available at the cell tower, the switch patches the call through a
channel to the PSTN. This channel is held until the call is terminated.
4- 96
Time Division Multiplex
This acts like a time sharing mechanism where a channel gets the whole spectrum for a
certain amount of time. There is only one carrier in the medium at any time. The
throughput is high even for many users however precise synchronization is necessary.
The whole spectrum is divided into smaller frequency bands A channel gets a certain
band of the spectrum for the whole time This means no dynamic coordination is
necessary. It also works for analog signals. It becomes a waste of bandwidth if traffic is
4- 97
Time and Frequency Division Multiplex
This combines both methods A channel is allocated a certain frequency band for some
adaptive however precise coordination required GSM (Global Systems for Mobile
Each channel is assigned a unique code. The same spectrum is used by all channels at the
same time This results in bandwidth efficiency. There is no need for coordination or
synchronization It is hard to tap and almost impossible to jam It has a lower user data
rates and a more complex signal regeneration UMTS (Universal Mobile Telephone
4- 98
Location based services
This utilizes satellites to allow users to determine their position. Navigation services can
4- 99
Exercises for No.1 Chapter4 (Hardware)
Q1 What is the combination of words that should fill in the blanks of the diagram representing
the computer basic configuration?
Data flow
a
Control flow
a b c
A Arithmetic unit Main storage unit Main storage unit
B Main storage unit Control unit Arithmetic unit
C Control unit Arithmetic unit Main storage unit
D Control unit Main storage unit Arithmetic unit
Q3 Regarding the index modification of the machine language instruction, which of the following
would be the effective address?
Address in which the instruction is stored: 1000
Value of the instruction language: 100
Value of the index register: 10
Q4 Given the following circuit, when the input values are A=1, B=0, C=1, what is the appropriate
output value for P, Q and R? Here represents an AND gate, represents an
OR gate and represents a NOT gate.
A P
Q R
B
C
P Q R
A 0 1 0
B 0 1 1
C 1 0 1
D 1 1 0
4- 100
Q5 When the sum of 1-bit values A and B is represented in 2-bit values, which of the following
corresponds to the combination of the logical expression of the higher bit D and the lower bit
S? Here, " ⋅ " represents the logical product (AND), "+," the logical sum (OR) and A , the
negation (NOT) of A.
Sum of A and B
A B
C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
C S
A A B A B A B
B A B A B A B
C A B A B A B
D A B A B A B
Q6 In a computer with 3 types of instruction sets, which of the following corresponds to the
MIPS value when their respective execution speed and frequency rate are as follows?
a a b a c d
The CPI required to execute each instruction is indicated in the following table. If 1 clock
cycle of the CPU is 10 nanoseconds, how many nanoseconds will the CPU execution of this
instruction string require?
Instruction CPI
a 6
b 2
c 4
d 8
A. 20 B. 32 C. 200 D. 320
Q8 Which of the following is the method of the ordinary computer basic architecture that loads
programs and data together in a computer storage device and sequentially reads and
executes them?
A. Address method B. Virtual storage method
C. Direct program control method D. Stored program method
4- 101
Q9 Given the following magnetic disk unit specifications and conditions of the data subject to
storage, how many tracks does the necessary area have when the blocking factor is 20? Here,
the area is assigned by track and the file organization is sequential.
Magnetic disk unit specifications
Storage capacity per track 25,200 Bytes
Inter-block gap 500 Bytes
A. 80 B. 83 C. 89 D. 100
Q10 The following diagram represents the access time of the magnetic disk unit. Which is the a, b,
c and d correct combination?
Access time
a b
d
c
a b c d
A Seek time Search time Latency Data transfer time
B Seek time Latency Search time Data transfer time
C Latency Seek time Data transfer time Search time
D Latency Data transfer time Seek time Search time
Q11 Given the magnetic disk unit with the following performance, what is the average access time
in milliseconds required to read the 2,000-byte-length-block data recorded in this magnetic
disk?
Magnetic disk unit performance
Storage capacity per track (bytes) 20,000
Revolution speed (revolution/minute) 3,000
Average seek time (milliseconds) 20
A. 30 B. 31 C. 32 D. 42
Q12 Regarding the optical disk characteristics, which of the following descriptions is correct?
A. CD-ROMs have large storage capacity, but since high-level technology is required for their
manufacture, compared to magnetic disks, the cost is higher for the same amount of information.
B. In the magneto optical disk, which is one of the rewritable storage media, data is recorded by
changing the medium magnetization direction.
C. In the recordable optical disk, in which data is recorded by making microscopic holes in the
medium, data can be rewritten as many times as required.
D. Since the access mechanism of magneto optical disks is very similar to that of magnetic disks, the
average access time is also of the same level.
E. Since magneto optical disks are susceptible to heat, light and dust, compared to magnetic disks, the
magneto optical disk's durability is lower.
4- 102
Q13 Which of the following is the most appropriate explanation of mirroring, which is one of the
methods used to improve the magnetic disk unit reliability?
A. By giving a mirror-like finish to the disk surface the resistance at the time the disk rotates is
reduced.
B. The data block and the parity block are stripped and stored across multiple disks.
C. Besides the disks that record the data, another disk for parity recording is used.
D. Identical data is recorded simultaneously in separate disks.
Q14 Which is a feasible combination of interfaces for connecting the peripheral devices indicated
below? Here ATA/ATAPI-4 represents the interface that is normally called IDE.
Hard disk,
Modem Keyboard
CD-ROM
A ATA / ATAPI-4 GPIB SCSI
B GPIB SCSI RS-232C
C SCSI RS-232C USB
D USB IrDA ATA / ATAPI-4
Q15 If an image, whose height and width in pixels is 480 dots and 640 dots, respectively, is
represented in 256 types of colors: approximately how many kilo bytes would be required in
order to save this data in a storage device? It should be noted that no compression process is
performed.
A. 170 B. 310 C. 480 D. 9,840 E. 78,650
Q16 Which of the following printers uses a heating element to melt the ink of the ink ribbon and
is capable of printing on normal paper?
A. Ink-jet printer B. Thermal printer
C. Dot impact printer D. Thermal transfer printer
E. Laser printer
4- 103
Multimedia System
5
Chapter Objectives
5- 1
5.1 Multimedia System Design
Multimedia comprises a combination of
1) Audio
2) Animation
3) Video
4) Static pictures
5) Text
Multimedia uses a combination of the visual, audio and tactile senses to deliver the
message across.
5- 2
5.1.1 Types of multimedia applications
Education
The benefits of using multimedia as a training tool are
• "Just in time" training can be implemented in multimedia.
• Courses can be taken any time and anywhere. Moreover, it allows the user to
learn at their own pace.
• Interactive multimedia makes a good simulation tool.
• User interactions can be recorded, analyzed and reported.
Entertainment
Movies, Net gaming and concerts can be streamed as multimedia contents. They are
many examples of the use of multimedia effects in the movie industry. Character
Graphics is also becoming more prominent with whole clips comprising of computer
generated characters.
Marketing
5- 3
They are an increase use of multimedia in advertising. Computer characters have
sometimes replaced the real world character in the advertisement.
Shopping
Multimedia allows the users to manipulate the products in 3 dimensional spaces. This is
unlike a physical shop where it is possible to feel and touch the product. The use of
multimedia allows the display of the products as a 3 dimensional figure that can be
manipulated by the user.
In addition, the properties of the figure like color and pattern can be modified
interactively.
5- 4
5.1.3 Needs Assessment
The objectives of the multimedia production have to be clearly spelt out. As shown in the
example, above the needs of the audience varies from one group to the next.
Content for school going children need to be interesting enough to capture their attention
and convert the learning experience into a fun filled experience.
Professionals will look for knowledge based content that allow skills to be learnt in as a
short a time as possible.
Undergraduates focus on content that allows them to do their assignments easily and to
practice their skills through mock examinations and exercises provided by the contents.
Organizations will focus on improving their learning curve. The knowledge requirement
to perform the various processes in the work flow is collected and analyzed. These
knowledge requirements become the objectives.
5- 5
will be working on and what their connection to the Internet may be like (modem
vs. direct link).
• Once you have established with whom you wish to communicate you need to
think about the best way to get your ideas across.
This is where layout and design come to play.
You have to take the following criteria into consideration
1) Familiarity with the use of interactive media
2) Easy help
3) Ease of navigation
5- 6
The following are defined when creating contents
1) Objectives
2) Use the medium that best conveys the information
3) Use the multimedia as a supportive and not just for decoration
4) Synchronize the multimedia with the text or picture
5) Make the interface interactive
Match the type of testing to the information covered.
5- 7
• Web pages
The type of tool can be classified as
1) Video authoring
These are used to edit video. There include tools like Premier or AfterEffects that allow
2) Multimedia authoring
These include tools like Macromedia Director or Flash
3) Landscape generators
These include tools like Bryce, Vue
4) Character modeling
These cover tools like Poser.
5) Audio editing
There include tools like SoundForge.
6) Studio
7) PowerPoint
8) Image editing software like Photoshop
Authoring
Product
base
Presentation PowerPoint
Timeline Premier, Flash, Director
5- 8
Director
Macromedia Director uses a theatre metaphor to describe its components and its
creations are called movies.
The main screen is called the stage, the stage is always open and is behind other windows.
These include:
• the cast window which displays the cast members, that is the files, art, sound,
movies, etc that make up your production.
• The score window that keeps up with what cast member is on the stage in each
frame of a movie and controls the timing, transitions, sound timing and palettes.
• The script window is where you type in instructions to create interactive links.
Director also includes a toolbar made up of short cut icons, a control panel similar to the
controls on a VCR, and a tool palette. Because time-based authoring programs work by
displaying a series of frames, they are especially good for creating animations. It is able
to import movies, audio and pictures
5- 9
Director also has support for the 3D format. This feature is useful if the content requires
to convey spatial orientation.
Flash
Flash is similar to director. A library contains all the resources. It is intended for a 2 D
type development.
5- 10
Adobe Premier and AfterEffects
These are video editors. There support the AVI, MOV and MPEG. There also allow the
capture and output of the medium into tape.
A suitable video capture board must be used. Movies are good to showing operations.
Keep in time that the size and length of the movie may make it difficult to distribute.
Unlike Flash or Director, scripting is not supported. It is used more as a post production
tool to add the opening, closing credits. It is also used to edit the movies and add titles or
effects on the movies.
5- 11
Poser
This creates characters and allows movement to be added to the character. It outputs
static images or video.
5- 12
Depending on the communication infra-structure, the content may be distributed in
various forms.
5- 13
5.1.7 Storyboard
A preview is possible using a storyboard. It can be treated as a visual script for camera
angles, lighting, sound effects, prop arrangement, and the narrative development and
continuity.
The procedure for creating a storyboard is
5- 14
1. Give consideration to the scenarios of use which the storyboard will reflect. A
storyboard may represent several activities such as entering, saving or printing
information. Alternatively a separate storyboard may be created to represent each
distinct theme.
2. Construct the storyboard as a sequence of screen representations using separate
images to reflect changes in system appearance. Thus the storyboard indicates the
availability and purpose of dialogue windows, menu items, toolbars and icons.
3. The elements of a storyboard can be annotated with explanatory captions to aid
audience understanding and evaluation.
4. The completed storyboard can be shown to design teams as well as intended users
to solicit evaluative feedback. Several storyboards can be created and shown to an
audience in order to explore different design options.
5. It may be useful to video or audio record the feedback sessions for later review or
to show to other colleagues.
Presenting activity
The most basic activity is to display a single, non-interactive block of text, image or
video sequence. A more complex activity could involve the display of a collection of
individual images and video segments. A further refinement might involve the use of
5- 15
audio to cue the start of a video and then present a series of images each cued to certain
sections of the audio track.
Controlling activity
The most basic variation of a one-after-the-other approach is the use of a selection
structure based on menus. From an opening menu screen, the user chooses between a
number of selections. On selecting the item a single activity is usually performed, after
which the user is returned to the main menu. The menu activity in this respect is an
example of a controlling activity.
Each item has a single starting point but has multiple end points. The nature of the input
made by the user determines which of the multiple end points will be chosen.
Using this simple activity model, it is possible to identify various types of multimedia
application structures: linear presentation, data driven engine, hierarchical menu,
information retrieval and hypermedia.
Linear presentations
A linear presentation has one event after another but, for such a presentation to be of
benefit to the user, there needs to be some element of control, with the presentation
alternating between presenting and controlling activities. The controlling activities fix the
duration of the presentation.
For example, in the event of a live paper presentation at a conference, the controlling
activities would be programmed to accept cues from the speaker during their
presentation. The cues could either be keystrokes (any key) or the use of a mouse device
to move between the different screens. This allows the presentation to be synchronized
with the messages being expressed by the speaker.
A more sophisticated speaker-support presentation might allow some other forms of
information manipulation at each control point, such as the ability to go backwards or
5- 16
forwards through a presentation, or the option to jump out of the presentation into another
application.
Hierarchical menus
A menu is executed by using a presenting activity to reveal the menu, and then a
controlling activity so that the user's selection is activated. This might take the user to
another presenting activity or it might branch off to another level of the menu. When a
menu selection is completed, the user is usually returned to the menu. Likewise, when the
5- 17
user exits a sub-menu, they return to the main menu. The designer needs to ensure that
the user goes back to the main menu before closing the application.
Such a menu structure can quickly become difficult to use, especially if some of the
activities (and menu items) appear in several menus. Using a data-engine approach may
help to simplify the whole process by associating with each menu a script file that
outlines the menu items and the titles of the presentations that will be executed when
chosen. Code for a menu engine can be generated to display the menu from this file,
which then sends the name of the selected item to a single-presentation engine program.
This simplifies the menu structure down to two engine programs
— presentation and menu — and the detailed application structure is actually stored
in a
— group of text files, which will be easy to modify and
manage without conventional programming skills.
5- 18
boring; it gives your site a consistent graphic identity that reinforces a distinct sense of
"place", and that makes your site more memorable.
A consistent approach to layout and navigation allows readers to quickly adapt to your
design, and to confidently predict the location of information and navigation controls
across the pages of your site. If you choose a graphic theme, use it throughout your site.
Consistency in the use of all visual elements, tools, commands, operations and
organizational style is the foundation of good interface design.
Knowing what type of information will be covered and when and where it will appear
builds predictability into a software application.
Good mappings
There should be clear relationships between the user's actions and the machine's
responses, the controls and their effects and the state of the system and the interface.
Graphic user interfaces were designed to give people direct control over their personal
computers. Users now expect a level of design sophistication from all graphic interfaces,
including Web pages. The goal is to provide for the needs of all of your potential users,
adapting Web technology to their expectations, and never requiring the reader to simply
conform to an interface that puts unnecessary obstacles in their paths.
5.1.10 Feedback
Feedback may take the form of:
• written responses
• visual responses
• auditory responses
Ideally, the user should receive immediate full and continual feedback concerning the
results of all self-initiated and program-driven actions. This promotes a sense of progress.
Feedback from the user interface should be immediate and unambiguous, in the form of
written, visual or auditory signals indicating that the computer has received input from
5- 19
the user and is acting upon that stimulus. For instance, clicking on a screen button may
cause the button colors to reverse or a button 'click' sound may be heard.
An easily-grasped metaphor or concept
Use metaphors involving concrete, familiar ideas and make the metaphor plain so that
users have a set of expectations to apply to the computer environment. For example,
desktop
folders
trash can
menus
The metaphor can be a powerful verbal and semantic tool for conveying both superficial
and conceptual similarities between familiar and novel situations. Learned associations
should mould the metaphor because these familiar experiences help users to grasp
complex ideas.
An alternative to the metaphor is the development of a unifying concept. A concept might
be a derivative of a story line, a particular theme, or a stylized look.
Efficient navigation schema
Users should be able to find out where they are quickly and how to get back to where
they were.
The main interface problem with most Web sites is the lack of a sense of where you are
within the local organization of information. Users should always be able to return to
your home page, and to other major navigation points in your local site.
Navigation tools include
• directional devices
• maps
• headings
• visual effects
• timelines
• on-line help
• user guidance facilities
5- 20
• sound cues
System transparency
It is important that the user can 'look through' your interface and concentrate on what's
important - the information your document presents. To this end, the interface should be
transparent, concealing the complexity of the system so that the user can focus on the
tasks, rather than on the tool, the data rather than the "data container".
The user should always feel in direct control of the computer interface and should never
feel that the computer has "automatically" taken actions that could arbitrarily change the
user's preferences, destroy data, or force the user to waste time.
Data organization
Psychologically, a user needs to get closure on one stage of the interactive process in
order to move onto the next. This is accomplished by grouping information into readily
digestible units. Visually stratifying various layers of information reduces noise and
enriches the content of the display.
Good screen design creates visual logic, an optimal balance between visual sensation and
graphic or text information. A careful, systematic approach to screen design can simplify
navigation, reduce errors, and make it much easier for users to take full advantage of the
information and features of your Web site.
• Develop content before design
o design should be determined by the information you want to communicate
• Have an objective
o to educate
o to inform
o to entertain
• Establish a visual hierarchy
o emphasize important elements
o organize content logically and predictably
5- 21
Interactivity
Users want to feel they are in charge of the computer's activities. They want their
physical actions to have physical results and they want buttons, icons, menus etc. to
provide feedback.
An active participatory interface allows the users to control the environment by directly
manipulating materials. Interactivity is challenging and inspires the user to respond more
creatively. Consistency in screen design is important because of the interactive nature of
the computer interface, where visual design elements appear and disappear in response to
the user's actions.
User's actions should always be reversible.
Evaluation
User evaluation is essential during the design process. User evaluation, combined with
feedback from content specialists, keeps the developer on track.
5- 22
Answers for No.1 Chapter 1 (Basic Theories of Information)
Answer list
_____________________________________________________________
Answers
Q 1: C Q 2: B Q 3: D Q 4: B Q 5: C
Q 6: D Q 7: D Q 8: D Q 9: C Q 10: B
Q 11: C Q 12: C Q 13: A Q 14: C Q 15: B
Q 16: B Q 17: B Q 18: C Q 19: D
Q1
Answer
C. k<M<G<T
Description
K (kilo) 103
M (Mega) 106
G (Giga) 109
T (Tera) 1012
Q2
Answer
B. 1 microsecond / 1,000,000
Description
M (mili) 103
(micro) 106
N (nano) 109
P (pico) 1012
1picosecond
= 1second x 10 -12
= 1microsecond x 10 -6
6- 1
Q3
Answer
D. 10111011
Description
01010101
+01100110
10111011 ÅAnswer
Q4
Answer
B. BE
Description
Do subtraction as follows.
11011101
-00011111
10111110=(BE)16 Answer : B
6- 2
Q5
Answer
C. 3.5
Description
Do addition as follows.
1.6875
+1.8125
3.500
Q6
Answer
D. 0.5
Description
Q7
Answer
73
D.
512
Description
(0.248)16
=2x16-1+4x16-2 +8x16-3
6- 3
=(2x16x16 + 4x16 + 8)/16x16x16
=(512+64+8)/(16x16x16)=73x8/16x16x2x8
=73/512
Q8
Answer
D. 0100 0011 0010 1100
Description
In packed decimal,
Each digit is represented by 4 bit BCD code
“+” or “– “sign is represented by the last 4bit
(1100)2 for “+”, and (1101)2 for “-“
Q9
Answer
C. −2 n-1 to 2 n-1 − 1
Description
In fixed decimal format representing a negative number using 2’s complement, an n-bit
binary number can represent a number ranging from -2n-1 to 2 n-1-1.
For example, in case of 8 bits, from 1000 0000 (= -128 in decimal) to 0111 1111 (= 127 in
decimal).
6- 4
Q10
Answer
B. Subtractions can be processed as additions.
Description
Since the addition of a number and its 2’s complement make zero as shown in the following
example, 2’s complement of a number can represent a negative number.
[Example]
5 = 00000101, 2’s complement of 5 = 11111011, and those two make zero.
00000101
+11111011
100000000 (leftmost 1 is discarded because it is outside of 8 bits)
And then Introduction of negative numbers makes it possible to process subtractions (e.g.
10-7) as additions (e.g. 10+(-7)).
Q11
Answer
C. 10100110
Description
8-bit fixed decimal point format (decimal point between the 4th and 5th bits) of -5.625
8 7 6 5 4 3 2 1
1) Decimal part
5 = (0101)2
2) Fractional part
0.625 x 2 = 1.25 (0.1)2
0.25 x 2 = 0.5 (0.10) 2
0.5 x 2 = 1 (0.101) 2
By doubling the number and taking the decimal part of the result,
0.625 = (0.101)2
Therefore
5.625 = (0101.1010)2
6- 5
This is represented as 01011010 in the specified format.
2’s complement of the above is 10100110
Q12
Answer
C
0 1111 11000000000
1 bit 4bits 11bits
Description
Q13
Answer
A. 2AF3
Description
6- 6
Therefore,
0010 1010 1111 0011 = 2AF3
Q14
Answer
C. 4
Description
Q15
Answer
B. –13
Description
6- 7
2) Switch all the 0 and 1 bits of the above
0 0 0 0 1 1 0 1
(00001101)2 = (13)10
Therefore, the result is -13. The answer is B.
Q16
Answer
B. Due to the limited number of digits in the number representation, it is an error generated as a
result of rounding off, rounding up, or omitting portions smaller than the least significant
digit.
Description
A describes “overflow”
(A. It is an error generated when an operation result exceeds the maximum value that can be
processed by the computer.)
B describes “rounding error” Æ answer
C describes “cancellation”.
(C. It is an error generated due to the loss of the most significant values in the subtraction
operation of numeric values, whose absolute values are almost equal.)
D describes “Loss of Information”
(D. It is an error generated due to the loss of the least significant values of the mantissa portion
of the numeric value, with the lower exponent value in the subtraction operation of floating
point numbers.)
Q17
Answer
B. 6
Description
A to Z 26 characters
0 to 9 10 characters
To represent above 36 different characters using n bits, the following should be true.
2n >= 36
Since 25 = 32 < 36 < 64 = 26, the answer is 6 Æ B
A. 5 B. 6 C. 7 D. 8
6- 8
Q18
Answer
C. (NOT x) AND y
Description
In this question, the expression that is equivalent to the operation given in the following truth
table is to be found.
Truth table
x y x y
True True False
True False False
False True True
False False False
AND operation
x y x AND y
True True True
True False False
False True False
False False False
OR operation
x y x OR y
True True True
True False True
False True True
False False False
NOT operation
x NOT x
True False
False True
6- 9
Because of the following result, the answer is c.
x y NOT x (NOT x) AND y
True True False False
True False False False
False True True True
False False True False
Q19
Answer
D. (A · B) + C
Description
(A + B) ⋅ C X⋅C X C (A + B) C (A ⋅ B) C
6-10
Answers for No.1 Chapter 2 (Data Structures)
Answer list
_____________________________________________________________
Answers
Q 1: C Q 2: B Q 3: B Q 4: D Q 5: C
Q 6: C Q 7: D Q 8: B Q 9: A Q 10: C
Q 11: B Q 12: C
Q1
Answer
c. 190
Description
The position of a[5,6] in the array is as follows.
Q2
Answer
b. The pointer for Shizuoka to be set to 70 and that for Atami to be set to 150
Description
This unidirectional list can be visualized as follows.
6- 11
10 Tokyo-->50 ShinYokohama-->90 Atami-->70 Hamamatsu-->30 Nagoya
After inserting Shizuoka between Atami and Hamamatsu, it will be
10 Tokyo-->50 ShinYokohama-->90 Atami-->150 Shizuoka-->70 Hamamatsu-->30 Nagoya
Therefore, Shizuoka' s pointer should be 70. Atami's pointer should be 150.
Pointer for the head Address Data Pointer
10 10 Tokyo 50
30 Nagoya 0
50 Shin Yokohama 90
70 Hamamatsu 30
90 Atami 150
150 Shizuoka 70
Q3
Answer
b. Queue
Description
Queue is called the first-in first-out (FIFO) system. Æ Answer
Stack is termed the last-in first-out (LIFO) system.
Binary tree is a kind of tree structure in which order of insertion and order of access are
independent (neither FIFO or LIFO)
Heap is a kind of binary tree.
Q4
Answer
a b c d e
1 3 3 3 6
7 4 4 7 4
3 5 6 1 3
Description
Stack manages data in FILO(First In Last Out) basis.
PUSH 1-->PUSH 5-->POP-->PUSH 7-->PUSH 6-->PUSH 4-->POP-->POP-->PUSH 3
PUSH 1-->PUSH 5
5
1
6- 12
POP
1
POP-->POP
7
1
PUSH 3
3
7
1
Q5
Answer
c. 4
Description
In the above Figure 1, for each node represented by the subscript number, the Pointer1 indicates
the index value of its left child node, the Pointer2 indicates the index value of its right child node.
"a" means the index value of the 180's right node. What comes there is 190 and its index value is
4.
6- 13
Q6
Answer
c. 13
Description
In a binary tree, each node must satisfy the following.
max key value of its left nodes < its key value < min. key value of its right nodes
therefore,
the ex-12 node should have some value greater than 10 and less than 14.
6
4 8
2 5 7 12
1 3 10 14
9 11 13 15
Q7
Answer
d. hicdbjfkgea
Description
b e
c d f g
h i j k
Q8
Answer
b. A + B × C - (D + E) ÷ F
6- 14
Description
A F
B C D E
Notation
Operator
Left Right
operand operand
Therefore,
B C
represents B x C,
A x
B C
represents A + B x C
By interpreting the rest in a similar manner, the answer is
A + B x C - (D + E) / F
Q9
Answer
a. Split and merge nodes to allow the hierarchical depth to become the same.
Description
a is correct.
b refers to hash
6- 15
(b. Identify the position where data is to be stored by using a certain function and key value.)
c describes sequential access files
(c. Only sequential access to head data and subsequent data is possible.)
d represents partitioned organization files
(d. There are a directory and a member (or members). A member is a sequentially organized
file.)
Q10
Answer
c. 11
Description
In this question, the element in the position A after 7 is inserted at the “*” position is to be found.
11 14
A
24 25 19 28
29 34
11 14
24 7 19 28
29 34 24
7 14
24 11 19 28
29 34 24
6- 16
7
9 14
24 11 19 28
29 34 24
After the above swapping, the element in the position A is 11. Therefore, the answer is c.
Q11
Answer
b. 2
Description
Hash function
mod(a1 a2 a3 a4 a5, 13)
mod(54321,13)=mod(5+4+3+2+1,13)=2
Therefore index for 54321 is 2.
Q12
Answer
c. 0.7
Description
A hash table with 10 elements
Therefore the probability that synonym does not occur for 5 values is
9/10 x 8/10 x 7/10 x 6/10 = 3024/10000
The probability that collision occur is
1-0.3024=0.6976
6- 17
Answers for No.1 Chapter3 (Algorithms)
Answer list
_____________________________________________________________
Answers
Q 1: A Q 2: D Q 3: C Q 4: B Q 5: D
Q 6: D Q 7: E Q 8: E Q 9: D Q 10: C
Q 11: A Q 12: B
Q1
Answer
a. Linear
Description
a. Linear
The linear search algorithm searches the elements sequentially from the beginning to the
end of a table Æ answer
b. Binary
A binary search method is the method of narrowing down target data while successively
dividing a search area into two parts. Elements are not searched sequentially.
c. Hash
A hash is a way of using an array-type data structure. Using a hash, you can directly access
specific data using a key without accessing recorded data one by one.
d. Heap
A heap is a kind of binary search tree. It is a perfect binary tree that has a certain size
relationship between a parent node and a child node. A heap is different from a binary
search tree in that a heap does not have a certain size relationship between brothers.
6- 18
Q2
Answer
d. X = ai
Description
Subscript 1 2 3 ... i ... n n+1
Value a1 a2 a3 ... ai ... an X
The step2 through step4 form a loop.
The space represents the loop condition.
The condition for exit is either “the value is found” or “at-end is reached”.
Since “whether at end or not” is examined in the step 5, the space should be “the value is found”,
i.e. X matches the current element value. Æ the answer is d
Q3
Answer
a b
c k + l → lo k - l → hi
Description
Start
1 lo
n hi
( lo hi ) 2 k
A(k):x
a b
lo : hi
End
A binary search method is the method of narrowing down target data while successively
dividing a search area into two parts.
1) space a
If A(k) < X, further divide the higher half area into two parts, therefore “k+1 Æ lo”.
2) space b
If A(k) > X, further divide the lower half area into two parts, therefore k-1 Æ hi
6- 19
Therefore, the answer is c.
Q4
Answer
b. 11
Description
In binary search, the maximum and average number of times a comparison is made: If the
number of elements is N,
-Average number of times is [log2N]
-Maximum number of times is [log2N] +1
([ ] is a Gaussian symbol and decimal numbers of the value shown in this symbol are
truncated.)
Average number of times “k” is
1 <= 2000/2k < 2
2k <= 2000/2k < 2k+1
Here,
log21024 = log2(2)10=10 <= log22000 < log22048 = log2(2)11=11
Therefore k = 10 and the Maximum number of times is k+1 = 11
Æ the answer is b.
Q5
Answer
d. If the number of data is 10 or smaller, the average number of comparison times that the
linear search method requires, is smaller than that of the binary search method.
Description
In binary search, the maximum and number of times a comparison is made: If the number of
elements is N,
-Average number of times is [log2N]
-Maximum number of times is [log2N] +1
In linear search, the maximum number of times a comparison is made: If the number of
elements is N,
-Average number of times is N/2
-Maximum number of times is N
6- 20
a. To use the binary search method, data must be sorted.
a is correct.
b. To search 100 data using the binary search method, the maximum number of comparison
times that is needed to find the target data is 7.
if N=100, Average number of times for binary search is
log2100 < log2128 = log2(2)7
Therefore Average is 6 and Maximum is 7 Æ b is also correct.
c. If the linear search method is used, the number of comparison times does not necessarily
decrease even if the data is already sorted.
C is also correct.
d. If the number of data is 10 or smaller, the average number of comparison times that the
linear search method requires, is smaller than that of the binary search method.
if N=10,
Average number of times for linear search is 10/2 = 5
Average number of times for binary search is log210 < log2(2)4 = 4
Therefore d is incorrect Æ Answer
e. If the number of data is increased from 100 to 1,000, the number of comparison times
increases to 10 times as large as when the linear search method is used. Using the binary
search method, the number increases twice or less.
Average number of times for binary search for N=100 and N=1000 is as follows. Therefore e.
is also correct.
If N=100, log2100 < log2128 = log2(2)7
If N=1000, log21000 < log21024 = log2(2)10
Q6
Answer
a b c d
D ascending sort external sorting merge
Description
1) a, b
“Arranging data in the order of small- to large-value queues” means “ascending sort”.
2) c
If a target data sequence is in an auxiliary storage, this operation is called “external sorting”.
c.f. Internal sorting means sorting data in a main memory unit. External sorting means
sorting data stored on a magnetic disk and other auxiliary storage unit.
6- 21
3) d
Integrating two or more files sorted in certain order into one file is called “merging”
Q7
Answer
e. Bubble sort
Description
Start
Repeat
n 1
1 i
Exchange
i n
A ( i ) :A (i 1)
A(i) w
A(i 1) A(i)
w A(i 1)
Exchange
Repeat
End
In the above flowchart, A(i) and A(i+1) are compared, and if A(i) > A(i+1), they are swapped.
i.e. a pair of elements next to each other in the sequence is compared and if sequence is
wrong, swap occurs.
This describes the bubble sort. Æ the answer is e.
Q8
Answer
e. 10,000
Description
6- 22
In the bubble sort mechanism, a pair of elements next to each other in the sequence is
compared and if sequence is wrong, swap occurs.
Its computational complexity is n2 (proportional to a square of n, n: number of data)
If number of data becomes 100 times bigger than earlier (previously 1000 and now 100,000),
time for computation will be (100)2 = 10,000 times longer than earlier.
Æ the answer is e. 10,000.
Q9
Answer
d. Heap sort is a method of sorting data by representing an unsorted area as a subtree, fetching
the maximum or minimum value from the unsorted area, moving the maximum or minimum
value to a sorted area and repeating this routine to narrow down unsorted areas.
Description
a. Quick sort is a method of sorting data in sub-sequences consisting of data items fetched at
an interval and sorting smaller sub-sequences consisting of data items fetched at a smaller
interval.
This describes “Shell sort method”, in which two items of data located away from each other
at a certain interval are picked out of a data sequence.
b. Shell sort is a method of sorting data by comparing a pair of adjacent elements and
exchanging them if the second element is larger than the first.
This describes “Bubble sort method” where comparison of a pair of adjacent elements takes
place.
c. Bubble sort is a method of sorting data by setting a median reference value, allocating
elements with values larger than the reference value in one section and those with values
smaller than the reference value in the other section and repeating this routine in each
individual section.
This describes “Quick sort method”.
d. Heap sort is a method of sorting data by representing an unsorted area as a subtree, fetching
the maximum or minimum value from the unsorted area, moving the maximum or minimum
value to a sorted area and repeating this routine to narrow down unsorted areas.
This is a correct description of the Heap sort method. Æ answer
Q10
Answer
c. Data is divided into one group of data smaller than a reference value and the other group of
data larger than a reference value. In each group, a new reference value is then selected
6- 23
and data is likewise divided into two groups based on the reference value. This routine is
repeatedly executed.
Description
a. Compare and exchange are executed for two data away from one another at a certain
distance. This distance is gradually and continuously narrowed to sort all data.
a. describes the shell sort method.
b. The first minimum value is found in data. The second minimum value is found in data in
which the first minimum value is not included. This routine is repeatedly executed.
b. describes the basic selection method.
d. Adjacent data are repeatedly compared and exchanged to allow smaller data to move to the
end of a data array.
d. describes the bubble sort method.
6- 24
Q11
Answer
a. TANGO (i) → TANGO (i+1)
Description
Start
TANGO(n) TANGO(0)
Loop
End
After applying this algorithm, the word in TANGO(n) is supposed to be stored in TANGO(1),
then the remaining words are supposed to be shifted to right.
METI METI FE SW JITEC JIPDEC
TANGO(0) TANGO(1) TANGO(2) TANGO(3) TANGO(4) TANGO(5)
After doing “TANGO(5)ÆTANGO(0)”, the following should be done in the loop (whose index
“i” value changing from n-1 to 0 decrementing by 1)
TANGO(4) Æ TANGO(5)
TANGO(3) Æ TANGO(4)
6- 25
:
TANGO(0) Æ TANGO(1)
This can be described using index “I” as TANGO(i) Æ TANGO(i+1).
Therefore the answer is a.
Q12
Answer
b. As seen from the geometrical viewpoint, the method is to obtain an approximate solution by
using a tangential line of y = f(x).
Description
Step 1
A tangential line y = f(x) at point p1 of the coordinate x1, y1 is drawn and point x2 where the
tangential line intersects x-axis is obtained.
Step 2
A tangential line y = f(x) at point p2 of the coordinate x2, y2 is likewise drawn and point x1
where the tangential line intersects x-axis is obtained. As this step is repeatedly executed
the tangential line moves closer to a solution.
Step 3
The difference between adjacent approximate values obtained in step 2 is compared with a
predetermined convergence judgment value precision. Steps 1 and 2 are repeatedly
executed until this difference becomes smaller than the predetermined convergence
judgment value.
The equation for a tangential line at point p1 is y-f(x1) = f'(x1)(x-x1), point x2 where a
tangential line intersects x-axis can be obtained using the following equation:
f (x i )
x i +1 = x 1 −
f ′( x i ) (i = 0, 1, 2, ...)
6- 26
a. Although a function, f(x), cannot be differentiated, an approximate solution can be obtained.
This is incorrect because this method use differential as explained above.
d. Whatever initial values are provided, an approximate value can always be obtained.
In case f’(xn) =0, convergence will never take place, thus no approximate value can be
obtained.
6- 27
Answers for No.1 Chapter4 (Hardware)
Answer list
_____________________________________________________________
Answers
Q 1: D Q 2: A Q 3: C Q 4: A Q 5: A
Q 6: D Q 7: D Q 8: D Q 9: D Q 10: A
Q 11: C Q 12: B Q 13: D Q 14: C Q 15: B
Q 16: D
Q1
Answer
a b c
D Control unit Main storage unit Arithmetic unit
Description
b is main storage unit because data from the input device goes to this unit.
a is control unit because it performs controls over other units.
c is arithmetic unit because it exchanges data between b, i.e. main storage unit.
Q2
Answer
A. DRAM represents 1 bit depending on whether the capacitor is charged or not. It is
commonly used as a main storage unit.
Description
A. Answer
B. This describes ROM.
(B. Data is written at the time it is manufactured. It is used as a microprogramming storage
memory.)
C. This explains EPROM (Erasable and Programmable ROM).
(C. Data can be written using a special device and erased with ultraviolet light.)
D. This is for SRAM.
(D. It is composed of flip flops. The speed is high but the manufacturing cost is high as well. It
is used in cache memories, etc.)
6- 28
Q3
Answer
C. 110
Description
Since operand address is 100 and the index register value is 10,
effective address = 100+10=110 --> answer is C
Q4
Answer
P Q R
A 0 1 0
Description
Q5
Answer
C S
A A⋅B (A ⋅ B) + (A ⋅ B)
6- 29
Description
Sum of A and B
A B
C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
1) C becomes “1” only when both A and B are “1”.
Therefore C represents logical product of A and B.
i.e. C= A ⋅ B
2) S becomes “1” only when A and B are different. It becomes “0” if A and B are the same.
Therefore S represents exclusive logical sum of A and B.
i.e. S= (A ⋅ B ) + ( A ⋅ B)
Q6
Answer
D. 4
Description
MIPS value represents the number of instructions per second in unit of million (10-6)
2) Translate the above (average execution time for one instruction) into number of
instructions executable per second
Number of instructions executable per second
= 1/(0.27x10-6)
= 1/0.27 x 106
4 x 106
-->answer is D
6- 30
Q7
Answer
D. 320
Description
Q8
Answer
D. Stored program method
Description
In this question, the method that stores program and data together in memory is to be found.
The above-mentioned method is by John von Neumann, at Institute of Advanced Studies,
thus called “von Neumann architecture” or “stored program method.”
Æ The answer is D.
Q9
Answer
D. 100
Description
6- 31
= total number of records / block factor = 10000/20 = 500
4) Necessary number of tracks
= total number of blocks / number of blocks per track = 500/5=100
Q10
Answer
a b c d
A Seek time Search time Latency Data transfer time
Description
Q11
Answer
C. 32
Description
6- 32
=1 / rotation speed
=60 x 103 / 3,000 milliseconds
=20 milliseconds
Therefore
average rotation waiting time=20 2=10 milliseconds
Q12
Answer
B. In the magneto optical disk, which is one of the rewritable storage media, data is recorded
by changing the medium magnetization direction.
Description
6- 33
Q13
Answer
D. Identical data is recorded simultaneously in separate disks.
Description
A incorrect description
(A. By giving a mirror-like finish to the disk surface the resistance at the time the disk rotates is
reduced.)
B RAID5 distributes data blocks and parity blocks into multiple disks
(B. The data block and the parity block are stripped and stored across multiple disks.)
C RAID3 uses parity disk
(C. Besides the disks that record the data, another disk for parity recording is used.)
D correct (describes RAID1)
Q14
Answer
Hard disk, CD-ROM Modem Keyboard
C SCSI RS-232C USB
Description
Q15
Answer
B. 310
Description
6- 34
Q16
Answer
D. Thermal transfer printer
Description
A thermal transfer printer uses a heating element to melt the ink of the ink ribbon and is
capable of printing on normal paper.
B. Thermal printer
This uses a heating element but cannot print on normal paper.
C. Dot impact printer
This does not “melt” the ink of the ink ribbon.
A. Ink-jet printer
E. Laser printer
The above 2 does not use an ink ribbon.
6- 35
Index
A- 1
[L] perfect binary tree 2-14, 2-17 Spread Spectrum 4-83, 4-85, 4-86
pivot 3-24, 3-25 stable marriage problem 3-62
Landscape generators 5-8
pointer type 2-4 stable matching 3-63
last-in first-out 2-11
pop 2-11 stack 2-11
leaf 2-16
POP 2-11 stack pointer 2-11
LIFO 2-11
Poser 5-12 Storyboard 5-14
linear list 2-10
precision 5-16, 5-28 structure 2-2
Linear presentation 5-16
Premier 5-11 structured type 2-4
linear search 3-6, 3-11, 3-115
primarity test problem 3-69 subscript 2-4
linear search method 3-11
probability algorithm 3-65, 3-69 synonym 2-19
list structure 2-8, 2-9, 2-13
probability algorithm with synonym record 2-19
logic programming 3-4, 3-101
bounded errors 3-69
logical operation 1-1, 1-40
problem-oriented data
logical product 1-42 [T]
structure 2-8
logical shift 1-32
procedural programming 3-3 table 2-4
logical sum 1-42, 1-43
proposition 1-1, 1-40, 1-41 table search 3-9
logical symbol 1-41, 1-42
proposition logic 1-40 Third generation (3G)
logical type 2-3
push 2-12 services 4-96
loss of information 1-36
PUSH 2-12 three-dimensional array 2-6
trapezoidal rule 3-56, 3-57
[M] tree structure 2-14, 2-15
[Q]
truth table 1-40, 1-42
merge sort 3-28, 3-29
queue 2-12 two-dimensional array 2-4, 2-5
Microbrowser 4-92
quick sort 3-24, 3-25 Types of multimedia
Mobile based protocols 4-95
applications 5-3
Mobile Operating System 4-95
Monte Carlo method 3-71 [R]
Multimedia 5-2 [U]
radix 1-7, 1-8, 1-12
Multimedia authoring 5-8
radix conversion 1-7, 1-12 underflow 1-35
multiway tree 2-13
real number type 2-3 undirected graph 3-49
record type 2-7 uni-directional list 2-10
[N] recursive 3-24, 3-25 unpacked decimal format 1-18
recursive algorithm 3-29
Narrowband Microwave 4-84, 4-85
recursive call 3-24, 3-25
N-ary tree 2-13 [V]
reduction method 3-117
Needs Assessment 5-5
ring list 2-10 validity 3-115, 3-116
negation 1-41, 1-42, 1-43
root 2-16 Video authoring 5-8
Newton's method 3-54, 3-55
rounding error 1-28
node 2-14, 2-16
normalization 1-28, 1-30 [W]
NULL 2-10 [S]
WCDMA 4-96
numerical integration 3-56
scatternet 4-85 weighted graph 3-49
Selecting Authoring and WEP (Wired Equivalent
[O] delivery System 5-7 Privacy) 4-89
sentinel search method 3-10, 3-11 Wireless LAN 4-82, 4-85, 4-91
one-dimensional array 2-5, 2-12
sequential method 2-19 word 1-5, 1-24, 1-25
overflow 1-24, 1-35
Shaker sort 3-20, 3-21
Shell sort 3-22, 3-23
shift 1-28, 1-30, 1-31
[X]
[P]
shift JIS code 1-38 XHTML 4-93, 4-94, 4-95
packed decimal format 1-18, 1-19 shift operation 1-30, 1-31, 1-32
parallel transfer 4-60 shortest path problem 3-49
parent 2-13, 2-14 simple type 2-3 [Z]
partial type 2-3 Simpson's method 3-56, 3-59 zoned decimal format 1-18
A- 2