FE Textbook Vol. 1_IT Fundametals.pdf

New FE Textbook Vol.1 IT Fundamentals INFORMATION-TECHNOLOGY PROMOTION AGENCY, JAPAN  IT Fundamentals Introduction 1 Computers and Information Society ···································································· 2 2 Computers Within Society ························...

New FE Textbook Vol.1 IT Fundamentals INFORMATION-TECHNOLOGY PROMOTION AGENCY, JAPAN  IT Fundamentals Introduction 1 Computers and Information Society ···································································· 2 2 Computers Within Society ················································································ 4 3 The World Surrounding Computers, and the Structure of this Textbook ························· 7 4 The Relationship Between the ITEE and this Textbook ············································· 9 Chapter 1 Hardware 1 Basic Configuration of Computers ·····································································13 1 – 1 History of Computers 13 1 – 2 Five Major Units of Computers 16 2 Data Representation in Computers ····································································20 2 – 1 Data Representation 20 2 – 2 Radix and Radix Conversion 23 2 – 3 Representation Form of Data 28 3 Central Processing Unit and Main Memory Unit·····················································46 3 – 1 Configuration of CPU 46 3 – 2 Main Memory Configuration 49 3 – 3 Instruction and Addressing 52 3 – 4 Circuit Configuration of ALU 61 3 – 5 High Speed Technologies 70 4 Auxiliary Storage ···························································································78 4 – 1 Magnetic Disk 78 4 – 2 Optical Disc 86 4 – 3 Semiconductor Memory 89 4 – 4 Other Auxiliary Storage Media and Drives 90 5 Input/Output Unit ···························································································92 5 – 1 Input Unit 92 5 – 2 Output Unit 97 5 – 3 Other Input/Output Units 103 5 – 4 Input/Output Control Methods 104 5 – 5 Input/Output Interfaces 105 Exercises ···································································································· 112 Chapter 2 Information Processing System 1 Processing Type of Information Processing System ············································· 121 1 – 1 Non-interactive Processing System and Interactive Processing System 121 1 – 2 Batch Processing System and Real-time Processing System 122 1 – 3 Centralized Processing System and Distributed Processing System 124 2 Configuration of High-reliability System ····························································· 131 2 – 1 Series System 131 2 – 2 Parallel System 132 2 – 3 Multiplexing System 133 3 Evaluation of Information Processing System ····················································· 137 3 – 1 Evaluation of the Processing Power 137 3 – 2 Evaluation of Reliability 143 3 – 3 Evaluation of Cost Efficiency 151 4 Human Interface ························································································· 153 4 – 1 Human Interface Technology 153 4 – 2 Interface Design 157 5 Multimedia ································································································ 169 5 – 1 Multimedia Technology 169 5 – 2 Multimedia Application 176 Exercises ···································································································· 179 Chapter 3 Software 1 Classification of Software ·············································································· 184 1 – 1 Systematic Classification of Software 184 1 – 2 Classification by Software License 192 2 OS (Operating System) ················································································ 196 2 – 1 Functions and Configurations of OS 196 2 – 2 Management Functions of OS 197 3 Programming Languages and Language Processors ············································ 211 3 – 1 Classification of Programming Languages 211 3 – 2 Language Processor 217 3 – 3 Program Attributes 226 4 Files ········································································································ 227 4 – 1 Files and Records 227 4 – 2 File Access Methods 230 4 – 3 File Organization Formats 231 4 – 4 File Management in Small Computers 235 4 – 5 Backup 238 Exercises ···································································································· 240 Chapter 4 Database 1 Outline of Database ····················································································· 247 1 – 1 Difference Between Database and File 247 1 – 2 Database Design 248 1 – 3 DBMS (DataBase Management System) 254 2 SQL········································································································· 262 2 – 1 Data Definition 262 2 – 2 Data Manipulation 266 3 Various Databases ······················································································ 279 3 – 1 Distributed Database 279 3 – 2 Data Warehouse 280 3 – 3 Other Related Techniques 281 Exercises ···································································································· 283 Chapter 5 Network 1 Network Mechanism ···················································································· 289 1 – 1 Types and Characteristics of Networks 289 1 – 2 Basic Configuration of a Network 291 1 – 3 Basic Techniques of a Network 293 1 – 4 Transmission Control Procedures 305 1 – 5 Communication Services 310 2 Network Architecture ···················································································· 314 2 – 1 What is Network Architecture? 314 2 – 2 OSI (Open Systems Interconnection) 314 2 – 3 TCP/IP 316 3 LAN ········································································································· 319 3 – 1 Basic Techniques of a LAN 319 3 – 2 Other LAN Techniques 326 4 The Internet ······························································································· 328 4 – 1 TCP/IP Protocol 328 4 – 2 Basic Configuration of the Internet 336 4 – 3 Internet Services 337 5 Network Management ·················································································· 341 5 – 1 Network Operations Management 341 5 – 2 Network Management Techniques 342 Exercises ···································································································· 344 Section 6 Security 1 Overview of Information Security ····································································· 352 1 – 1 Concept of Information Security 352 1 – 2 Information Security Technology 361 1 – 3 Information Security Management 374 1 – 4 Information Security Agencies and Evaluation Criteria 381 2 Information Security Measures ······································································· 383 2 – 1 Human Security Measures 383 2 – 2 Technical Security Measures 384 2 – 3 Physical Security Measures 387 2 – 4 Security Implementation Technology 388 Exercises ········································································································· 396 Chapter 7 Data Structure and Algorithm 1 Data Structure ···························································································· 403 1 – 1 Array 403 1 – 2 List 405 1 – 3 Stack and Queue 407 1 – 4 Tree Structure 409 2 Basic Algorithm··························································································· 416 2 – 1 Flowchart 416 2 – 2 Data Search Process 419 2 – 3 Data Sorting Process 426 2 – 4 Other Algorithms 438 2 – 5 Algorithm Design 443 Exercises ···································································································· 445 Index························································································· 450 Introduction 1 Computers and Information Society The society in which we live today is sometimes called the “Information Society” or the “Information Processing Society.” This “Information Society” is one in which people need to create or locate, from among a flood of data, the information that is beneficial to themselves. Such an explanation may prompt the question of what is the difference between data and information. Data and information are, in fact, entirely separate things. Looking up each in the dictionary reveals the following descriptions. An example may help make the difference clear. The numeric string “20080607” is considered here. This numeric string is simply a meaningless listing of numerals as it is. (This is an example of data.) However, when “20080607” is interpreted as the “07”-th day of the “06”-th month of the year “2008”, the string comes to have a meaning, such as a “date of birth.” In this manner, data that holds meaning is called “information.” In other words, “data” becomes “information” when it comes to hold meaning. Figure I The difference between data and information What is important here is correctly interpreting “data” as “information.” For example, the numeric string that is interpreted above as a birthday could actually be the “phone number” “2008” - “0607”, or could be a “product sales record” that tells us that “product number” “200”, at “80” dollars per unit, sold “607” units. In other words, “data” can become entirely different “information,” depending on how it is interpreted. Correctly and quickly processing data is important. The tool necessary for doing so is the “computer.” 2  Introduction Figure II Data can be interpreted in many ways Figure III The computer is a tool for quickly obtaining correct information 3 2 Computers Within Society The following examples describe how computers are actually used in society. (1) POS system POS (Point Of Sales) system is a system for managing information at the point of sales. While the idea may seem complex, the system has become familiar to most people. When one buys something at a super store or a convenience store, a machine beeps when the product bar code is scanned and read. This device is the “barcode reader” that enters product data into a POS system. A barcode, which appears as a group of lines affixed to a product, represents a variety of information through the thickness and spacing of the lines. The role of “POS system” is to read this information, analyze factors such as what products are selling, and determine the number of products that are purchased. Bar code POS system terminal Barcode reader 4  Introduction (2) ATM system In a bank, there is a machine that allows the use of a card or a passbook to withdraw cash or check account balances. Users insert a card or a passbook into the machines, and enter instructions for making deposits or withdrawals along with the monetary value, or issue instructions to check account balances. The processes (e.g., the cash withdrawal) are then carried out on the basis of the personal information (e.g., the account balance) that is registered with the bank. If money is withdrawn, the amount withdrawn must be subtracted from the account balance at the same time. “ATM system” allows this process to take place without inconsistencies. This system greatly enhances convenience, by letting customers withdraw money from banks other than the one holding the deposit, and by eliminating the need to queue at a bank counter. ATM system (3) Seat reservation system A seat reservation system is used to secure a variety of reservations, ranging from a seat for a high-speed train or an airplane to a ticket for a concert or an event. Before this kind of system is created, workers had to perform reservation tasks manually. Reservations had to be performed at specified locations, which caused queues from early hours and troubles such as duplicate reservations for the same seats. The description may sound unbelievable to people who have only used modern reservation systems. Seat reservation system (4) The Internet It would be difficult to imagine anyone who does not know about “the Internet” today. Computer is used as a terminal for connecting to “the Internet.” Computer is also used in the administration and operation of “the Internet.” The Internet could truly be called a system representative of today’s information society. “Actions that people can perform through use of the Internet” can be broadly divided into “information search/transmission” and “online shopping.” 5  [Information search/transmission] This refers to the search for information that people want to know (i.e., search), and the release of information that people want to be learned by others (i.e., transmission). Today there are numerous search engines (i.e., tools to aid in investigating information), and countless websites that range from individuals to companies. An example of a website [Online shopping] This refers to the use of the Internet for shopping. At present, many companies sell their products via their own websites. There are also many virtual stores and shopping malls that sell products only on the Internet, without brick-and-mortar stores. Payments through credit cards and online banking have become increasingly common payment methods, as an environment has been prepared for convenient shopping from home. An example of online shopping 6  Introduction 3 The World Surrounding Computers, and the Structure of this Textbook Today, since computers perform a variety of jobs, the world is becoming increasingly connected around computers. The world surrounding computers today is composed of three broadly divided structural components as shown in Figure IV. Figure IV Structure of the computing world The following detailed discussion uses POS system that is introduced in the previous section “2 Computers Within Society” as an example. (1) Hardware This is the mechanical component that makes up computers. Hardware technology has seen dramatic advances in recent years, which results in creating a succession of achievements thought impossible until now. The decrease in the cost of hardware is also a major factor behind today’s proliferation of computers. In a POS system, the “barcode reader” that is used to read the bar codes on products is one component of hardware. The bar codes are read optically by lasers. You will be able to learn about such hardware mechanisms in “Chapter 1 Hardware.” The read information is not processed by the POS system terminal in the store. Instead, it is sent to and processed by a large scale computer in the head office. This form of processing is called “online transaction processing.” Today, various types of data are generated, and each type of data is processed in a variety of form. When computers break down, the resulting impact is often large and widespread. For that reason, the most appropriate form of processing must be considered, with factors such as reliability in mind. You will be able to learn the knowledge required to do so in “Chapter 2 Information Processing System.” 7 (2) Software This is the component of a computer that instructs the computer to perform activity. Computers cannot act under their own discretion, without instruction by humans. The creation of documents, the exchange of e-mails, and such other function that are made possible by using computers is due to software that performs the processing. A POS system carries out processes that include “Read bar code,” “Record data,” and “Calculate monetary amount.” In order to perform the processing, commands are issued to the hardware. (For example, the command “Read in the product bar code” is issued to a barcode reader.) Issuing these commands is the role of software. You will be able to learn about the mechanisms by which software issues orders, and ways by which resources are used efficiently, in “Chapter 3 Software.” Also, you can learn about “databases,” a means of managing and using data, in “Chapter 4 Database.” In actual processing, it is possible to check the names or unit prices of products on the basis of the data contained in product codes, as an example. In order to do so, it is necessary to think of efficient procedures for finding the target product codes from among many codes. There is a close relationship between these procedures and the structure used to record data. You will be able to learn about data structures and processing procedures in “Chapter 7 Data Structure and Algorithm.” (3) Network Network is technology for exchanging information among computers. The rapid growth of computers in recent years can be seen as a result of the rapid growth in networks. This is because jobs that once could not be performed on computers now can be, because of the exchange of information among many computers. In a POS system, data read at the store is transmitted for processing by large scale computers in the head office. Accurate and rapid transmission of the data requires knowledge of what methods and procedures to use in transmission. You will be able to learn basic knowledge about such communications in “Chapter 5 Network.” In order to combine the above (1) through (3) and perform a variety of activities accurately, rapidly, and securely, a variety of “systems” are created (with the POS system being one such example). However, we cannot use such systems, nor use data that is used on networks such as the Internet, with assurance if these are not properly and securely managed. In response, a variety of network technologies are employed to enable the secure use of systems and networks. You will be able to learn about the concepts of information security management that are used in these security technologies in “Chapter 6 Security.” 8  Introduction 4 The Relationship Between the ITEE and this Textbook The ITEE (Information Technology Engineers Examination) is a national examination that is implemented by the IPA (Information Technology Promotion Agency, Japan) as one index for the training of human resources in the information processing industry. Under a 2008 revision to the examination system, the ITEE has been mapped to Levels 1 through 3 of the Common Career/Skills Framework, with level determined upon success in the examination. Level Name of examination Targeted human resources Persons with basic knowledge of the information Level 1 IT Passport Examination technology that should be common to professionals Persons who possess the necessary basic Fundamental Information knowledge and skills for becoming advanced IT Level 2 Technology Engineer professionals, and also have acquired practical Examination capabilities for using them Persons who possess the necessary applied Applied Information knowledge and skills, and also have established a Level 3 Technology Engineer direction, for becoming advanced IT Examination professionals This textbook is structured to allow learning in technology related fields within the scope of the morning questions in the Fundamental Information Technology Engineer Examination of the ITEE. The following table shows the correspondence relationship between the chapters of this textbook and the question areas of the Fundamental Information Technology Engineer Examination. Question areas of the Fundamental Information IT Fundamentals Technology Engineer Examination 1 Basic Theory (Basic Theory [Discrete Mathematics, etc.]) Chapter 1 Hardware 2 Computer System (Computer Component) 2 Computer System (Hardware) 2 Computer System (System Component) Information Chapter 2 3 Technology Element (Human Interface) Processing System 3 Technology Element (Multimedia) Chapter 3 Software 2 Computer System (Software) Chapter 4 Database 3 Technology Element (Database) 9  Chapter 5 Network 3 Technology Element (Network) Chapter 6 Security 3 Technology Element (Security) Data Structure and Chapter 7 1 Basic Theory (Algorithm and Programming) Algorithm Areas that are within the scope of morning questions but that are not covered in this textbook can be studied in another textbook “IT Strategy and Management.” The following table shows the correspondence relationship between the chapters of “IT Strategy and Management” and the question areas of the Fundamental Information Technology Engineer Examination. Question areas of the Fundamental IT Strategy and Management Information Technology Engineer Examination 1 Basic Theory (Basic Theory [Applied Mathematics, etc.]) Corporate and Legal Chapter 1 9 Corporate and Legal Affairs (Corporate Affairs Activities) 9 Corporate and Legal Affairs (Legal Affairs) 8 Business Strategy (Business Strategy Management) Chapter 2 Business Strategy 8 Business Strategy (Technological Strategy Management) 8 Business Strategy (Business Industry) Information Systems 7 System Strategy (System Strategy) Chapter 3 Strategy 7 System Strategy (System Planning) 4 Development Technology (System Development Development Technology) Chapter 4 Technology 4 Development Technology (Software Development Management Techniques) Chapter 5 Project Management 5 Project Management (Project Management) Chapter 6 Service Management 6 Service Management (Service Management) System Audit and Chapter 7 6 Service Management (System Audit) Internal Control This textbook is organized, as noted above, so as to allow mastery of the morning questions of the Fundamental Information Technology Engineer Examination, when used together with “IT Strategy and Management.” 10  Introduction Moreover, since this textbook corresponds to Level 2 of the Common Career/Skills Framework, its study contents include the question areas of the Level 1 IT Passport Examination. The IT Passport Examination is an examination for all who have acquired the fundamental knowledge required of persons using IT. With the use of this textbook and “IT Strategy and Management,” it is possible to take the IT Passport Examination and the Fundamental Information Technology Engineer Examination in order. We hope that this textbook will be of use in improving the reader’s skills, with the aim of acquiring the desired qualifications. 11 Chapter 1 Hardware  Chapter 1 Hardware 1 Basic Configuration of Computers Various types of computers are extensively used around us. However, it has not even passed 100 years since the first computer was launched. Moreover, the basic configuration of computers has hardly changed since their initial launch. This chapter touches upon the history of computers from each generation and describes the five major units that form the basic configuration of a computer. 1 - 1 History of Computers Generations of computers are divided according to the logic gates they used. A computer consists of components known as logic gates, which correspond to the brain of the computer that is used in arithmetic operations. (1) 1st generation (1940s) The world’s first computer ENIAC was developed by J.W. Mauchly and J.P. Eckert in 1946. ENIAC used more than 18,000 vacuum tubes for its logic gates. Therefore, an enormous amount of heat was generated and the system consumed too much electricity for cooling, which even caused power outages. In those days, the computer was mainly used in ballistic calculations. However, it was necessary to replace circuit wiring according to the contents to be processed, and therefore, some people do not recognize it as a computer. It was EDSAC, developed by M.V. Wilkes in 1949, which eliminated the replacement of circuit wiring required in ENIAC. EDSAC was a computer that used a stored-program system. The stored-program system stores the contents to be processed as a program inside the computer and then runs it, and computers based on this system are also known as Neumann computers from the name of its inventor (J. Von Neumann). World’s first computer: ENIAC 13 (2) 2nd generation (1950s) While 1st generation computers were mainly used in military and research and development, UNIVAC I was launched as a commercial computer in 1951. In this generation of computers, semiconductors like transistors were used as logic gates. Semiconductors have intermediate electrical properties between conductors that pass electricity and insulators that do not pass electricity. Besides transistors, semiconductor devices include the diode (rectifying device), which only passes the electric current in one direction, and LED (Light Emitting Diode), which emits light when voltage is applied in the forward direction. Semiconductors are smaller than vacuum tubes, and their failure occurrence rate is low. Therefore, computers became compact, and their reliability increased. (3) 3rd generation (1960s) In this generation of computers, IC (Integrated Circuit) was used as a logic gate. IC implements the processing capacity of several-hundred transistors in a square silicon chip of a few millimeters, thanks to the advancement of semiconductor device technology. Computers became extremely compact and fast thanks to IC technology, and several manufacturers announced various types of computers. A typical example is IBM/360 developed by the IBM Corporation. This computer was a general-purpose computer that was capable of handling any kind of processing without any restrictions on the usage purposes. (4) 3.5th generation (1970s) In this generation, IC technology made further progress, and manufacturers began using LSI (Large Scale Integration) as logic gates. LSI has higher integration density than IC, which enabled computers to become even more compact and faster. Since computers became compact, this led to the development of control computers that are used in industrial devices and microprocessors that are used in home appliance products. Moreover, their high-speed technology led to the development of super computers that are very useful for high-speed operations in the area of scientific and engineering computations. Moreover, microcomputers were also launched as small computers for individual use. 14  Chapter 1 Hardware Super computer (5) 4th generation (1980s) Logic gate technology progressed further, and manufacturers began using VLSI (Very Large Scale Integration). Such exponential progress of hardware technology transformed the era of computers from “one computer in a company or facility” to “one computer per person.” Manufacturers started developing and selling PC (Personal Computers) for individuals, which formed the foundation of the present-day information society. Desktop computer Laptop computer In this era, the network environment was also developed, and it became common to use computers (servers) that provide services and terminals by connecting them through networks. In this usage, besides PCs, work stations that have higher performance than PCs were also used as terminals connected to networks. Moreover, the sizes of devices rapidly decreased with the development of the palm-sized PDA (Personal Digital Assistant) and smartphone; other personal digital assistants such as portable tablet terminals; and SoC (System on a Chip) and one chip microcomputers (single chip microcomputers) where functionality of computer is packed in one chip (LSI). (6) 5th generation (?) The progress of computer technology continues even today. For example, there is FPGA (Field Programmable Gate Array), which can be programmed after manufacture through 15 simulation of a design diagram. FPGA is slower than a dedicated LSI, and it is also expensive. However, as compared to implementing similar functions in software, FPGA devices are high-speed and low-cost devices, which is why they are used in home appliance products, etc. With the advancement of various technologies, computers increasingly became compact and high performance, and concentrated efforts were made so that even beginners could use them easily. Moreover, as the next generation computers, computers (e.g., computers with inference function) closer to people and more closely linked to society are being developed. Furthermore, as part of a recent trend, computers with a focus on energy conservation are also being developed. Power consumption of computers is expressed in units of Watts (W) just like general electrical appliances. Each of the components used in computers consumes power. Therefore, researchers are working on design technologies combining components that have low power consumption. 1 - 2 Five Major Units of Computers Computers are used in various fields, and there are various types of computers. However, the basic configuration elements are the same. This subsection describes the units that are used in computers. In order to explain the configuration elements of computers, a list is created for the functions that are required for computers. The easiest way to understand this is to think in terms of human action and behavior. If we think about human behavior in solving the problem “3+6= ”, it becomes as follows: 1) Look at the problem and memorize it. ↓ 2) Think about the meaning of “+”. …We know this is a sign that adds two values. ↓ 3) Memorize “9” as a result of adding “3” and “6”. ↓ Figure1-1 4) Write “9” in the answer sheet. Action and behavior of humans The five units of a computer perform this same action and behavior of humans. These units are called the five major units of a computer. 16  Chapter 1 Hardware 1) Input unit This is a unit that reads data to be processed by computer. 2) Output unit This is a unit that writes the processing results in a form that can be understood by humans. 3) Storage unit This is a unit that records data. There are main memory and auxiliary storage. 4) Arithmetic and logical unit This is a unit that performs arithmetic operations on data that is stored in the storage unit or makes a decision as per the instructions of the control unit. 5) Control unit This is a unit that interprets a command and gives instructions to the remaining four units. Below is an explanation of these units by using a specific example. When the arithmetic operation “3+6= ” is performed by a computer, a summary of the operation of each unit is as follows: 1) Enter “3+6” from the input unit, and store it in the storage unit. ↓ 2) Control unit decodes the meaning of “+”. As a result of decoding, it knows that “+” is a command for making addition. Therefore, it gives an instruction to the arithmetic and logical unit. ↓ 3) The arithmetic and logical unit fetches Figure 1-2 “3” and “6” from the storage unit, and Functioning of a computer performs the calculation. The result “9” is stored in the storage unit. ↓ 4) “9” is written from the storage unit to the output unit. Both input and output also operate on the basis of the instructions that are given by the control unit, which is not covered here. Therefore, the flow of data and control (instructions) between each unit is as shown in Figure 1-3 below. 17  Control unit Input unit Storage unit Output unit Arithmetic Control flow and logical Data flow unit Figure1-3 Flow of control and data in five major units In the storage unit, there is main memory and auxiliary storage. (In Figure 1-3, what is mentioned as the storage unit is main memory.) The differences between these two are described below. Main memory This unit can directly exchange data with the control unit and the arithmetic and logical unit, and it has a volatility characteristic (contents are lost if power supply is turned off). Auxiliary storage This unit stores data that cannot be accommodated in main memory, and it has a non-volatility characteristic (contents are not lost even if power supply is turned off). Moreover, the control unit and the arithmetic and logical unit are collectively referred to as the CPU (Central Processing Unit) or the processor. The input unit, the output unit, and 18  Chapter 1 Hardware the auxiliary storage outside the processor are also referred to as peripheral devices. Present-day computers use microprocessors (or MPU (Micro Processing Unit)), where CPU (processor) functions are consolidated into one LSI. Microprocessors are also used in home electrical appliances other than PCs. On the other hand, a semiconductor chip (LSI) where all required functions (system) including memory are integrated is referred to as SoC (System on a Chip). SoC has advantages such as high speed and low power consumption. However, it suffers from the disadvantage of high development risk. Therefore, it is also used in combination with SiP (System in a Package), which integrates multiple semiconductor chips into one package. Moreover, in a one chip microcomputer (single chip microcomputer) used in home electrical appliances, not only CPU and memory functions but also input and output functions are integrated into one semiconductor chip. In addition, there are co-processors that perform only specific processes for assisting the processor, and dedicated processors that are focused only on specific processes, unlike general purpose processors that perform various processes like in PCs. 19 2 Data Representation in Computers In order to make a computer work, it is necessary to store a program with a processing sequence and data to be processed inside the computer in advance. This section describes the methods of recording (representing) information inside computers. 2 - 1 Data Representation (1) Unit of representation Inside computers, data is recorded as electrical signals. Electric signals can basically represent only two states. Is electric current flowing? Is it not flowing? Is voltage high? Is it low? 0 and 1 are linked to these two states, and they are recorded and saved as data inside computers. In other words, data recorded by computers is represented with 0 or 1. The minimum unit that represents this 0 or 1 is called a bit. Various meanings are formed by combining 0 and 1 represented by this bit, and they are recorded as data. At this time, one unit formed by collecting 8 bits is called a byte. Figure 1-4 Bit and byte Moreover, there is a unit called word, which is formed by collecting more bits than in a byte. Word is the unit of processing inside computers, and there are 16 bits, 32 bits, 64 bits, etc. according to the model of computer used. Needless to say that if more bits can be processed at a time, then more information can be processed in a certain time. Therefore, the higher the number of bits in one word, the higher the processing speed of the computer. In most present-day computers, 1 word is 32 bits or 64 bits. 20  Chapter 1 Hardware (2) Information amount There are two types (0, 1) of information that can be represented with 1 bit, and the number of bit combinations is referred to as the information amount. The information amount that can be represented with 2 bits is of 4 types (00, 01, 10, 11), the information amount that can be represented with 3 bits is of 8 types (000, 001, 010, 011, 100, 101, 110, 111),... and so on. Figure1-5 Number of bits and information amount As shown in Figure 1-5, branches increase with the increase of every one bit used, and the information amount that can be represented keeps on doubling. In other words, the information amount that can be represented with n bits is of 2n types (2n shows the power of 2, and means multiplying 2 by itself n times). Using this concept, a summary of the information amount that can be represented with byte and word (16 bits) is given below. * Information amount of n bits = 2n types Information amount that can be represented with 1 byte (=8 bits) = 28 types = 256 types (00000000 through 11111111) Information amount that can be represented with 1 word (=16 bits) = 216 types = 65,536 types (0000000000000000 through 1111111111111111) 21  [Information amount in information theory] In the field of information theory, when event x occurs with occurrence probability (probability that a certain event occurs) P(x), the information amount that can be obtained is defined as I(x). According to this definition, the smaller P(x) is, the larger I(x) is; and the larger P(x) is, the smaller I(x) is. (This is easy to understand if the information amount is considered as the degree of surprise when an event occurs.) To explain the relation between bit and information amount, 1 bit represents the information of 0 or 1. In other words, the occurrence probability P(x) of event x, where either 0 or 1 appears, is 1/2, and so the information amount of occurrence probability 1/2 is 1 bit. Therefore, information amount n bit is an event with occurrence probability 1/2n; in other words, it means information of 2n types. (3) Prefix When data is handled, rather large numbers are handled as they are. However, it is very difficult to handle very large numbers or very small numbers without modification. Therefore, they are represented in combination with a prefix (auxiliary unit) representing a certain value. For example, even if a nurse holding a newborn baby says “He is a healthy baby boy of 3,000g,” no one would say “I lately got a little fat and became 75,000g.” Normally, one would say “75 kg.” This “k” is the prefix. “k” is a prefix that means the value “103”, and it can represent values like “75kg = 75×103g”. The readings and values of major prefixes are summarized in the table below. [Prefixes used for representing large numbers] Symbol Reading Decimal value Binary value k Kilo 103 210 M Mega 106 220 G Giga 109 230 T Tera 1012 240 P Peta 1015 250 22  Chapter 1 Hardware [Prefixes used for representing small numbers] Symbol Reading Decimal value m Milli 10−3 Μ Micro 10−6 n Nano 10−9 p Pico 10−12 Here, for prefixes that represent large numbers, binary values are also shown in the table. This is because inside computers, for representing information in binary form by using two numbers of 0 and 1, prefixes are also represented in binary form when numbers related to computers are represented (details of binary numbers are explained later). For examples, data like “1k calorie” is not related to computers. Therefore, it means 1k calorie = 1×103 calories = 1,000 calories. On other hand, data like “1k byte” is related to computers, and therefore it means 1k byte = 1×210 bytes = 1,024 bytes. However, it is almost equally related to “103≈210, 106≒220,...”, and therefore it is often treated as 1k byte = 1,000 bytes these days. Memorizing this relation helps when arithmetic calculation problems are solved. 2 - 2 Radix and Radix Conversion Decimal numbers that we normally use are numbers that are obtained by raising each digit to the power of 10 by using ten numbers from 0 through 9. (362.9)10 = 3×102 + 6×101 + 2×100 + 9×10−1 = (362.9)10 *10 in ( )10 shows that it is a decimal number. Here, the weight (10) of the decimal digit is called radix, and numbers represented with radix n are referred to as n-adic numbers. n-adic numbers are represented by using n numbers from 0 through (n−1) that are carried over when n is reached. (1) Binary numbers Binary numbers are represented by using two numbers 0 and 1 that are carried over when 2 is reached. The smallest unit of information handled inside computers is a bit, and only two numbers of 0 and 1 can be used. Therefore, computers use binary numbers that represent numerical values 23 with two numbers, 0 and 1. (101.1)2 = 1×22 + 0×21 + 1×20 + 1×2−1 = (5.5)10 * 2 in ( )2 shows that it is a binary number. Decimal numbers and their corresponding binary numbers are as shown below. Binary numbers can use only two numbers of 0 and 1 for one digit. Therefore, the number of digits quickly becomes large, compared with decimal numbers. Decimal numbers 0 1 2 3 4 5 6 7 8 9 10... Binary numbers 0 1 10 11 100 101 110 111 1000 1001 1010... Figure 1-6 Decimal numbers and corresponding binary numbers (2) Octal numbers Octal numbers are numerical values that are represented by using eight numbers from 0 through 7 and that are carried over when 8 is reached. (317.5)8 = 3×82 + 1×81 + 7×80 + 5×8−1 = (207.625)10 * 8 in ( )8 shows that it is an octal number Decimal numbers 0 1 2 3 4 5 6 7 8 9 10... Octal numbers 0 1 2 3 4 5 6 7 10 11 12... Figure 1-7 Decimal numbers and corresponding octal numbers (3) Hexadecimal numbers Hexadecimal numbers are numerical values that are represented by using sixteen numbers from 0 through 9, and A(10), B(11), C(12), D(13), E(14), and F(15) and that are carried over when 16 is reached. (1A6.E)16 = 1×162 + 10×161 + 6×160 + 14×16−1 = (422.875)10 * 16 in ( )16 shows that it is a hexadecimal number. 24  Chapter 1 Hardware Decimal numbers 0 1 2 3 4 5 6 7 8 9 10 Hexadecimal numbers 0 1 2 3 4 5 6 7 8 9 A 11 12 13 14 15 16 17 18 19 20... B C D E F 10 11 12 13 14... Figure 1-8 Decimal numbers and corresponding hexadecimal numbers (4) Relation between binary numbers, octal numbers, and hexadecimal numbers Binary numbers have an extremely large number of digits compared with decimal numbers. Although computers can handle binary numbers without problems, it is very difficult for a human being to understand when the internal status of computers is concerned. Therefore, octal numbers and hexadecimal numbers are used so that people can understand more easily. Octal numbers use the power of 8 (= 23) as the weight of each digit, and therefore the information of 3 digits of binary numbers corresponds to 1 digit of octal numbers. Binary number: (1011100.11101)2 ↓ (001 011 100. 111 010)2... Separate after every 3 digits with radix point as reference. ↓ (0 is supplemented in the parts that fall short of 3 digits.) Octal numbers: ( 1 3 4. 7 2 )8... Convert every 3 digits Hexadecimal numbers use the power of 16(= 24) as the weight of each digit, and therefore the information of 4 digits of binary numbers corresponds to 1 digit of hexadecimal numbers. Binary number: (1011100.11101)2 ↓ (0101 1100. 11100 1000)2... Separate after every 4 digits with radix point as reference. ↓ (0 is supplemented in the parts that fall short of 4 digits.) Hexadecimal number: ( 5 C. E 8 )16... Convert every 4 digits 25 (5) Radix conversion Radix conversion means changing the radix of a numerical value. It is also radix conversion to convert a binary number (radix 2) into an octal number (radix 8) or a hexadecimal number (radix 16). When radix has a constant (power) relation as in the case of binary numbers, octal numbers, and hexadecimal numbers, radix conversion can be done by consolidating multiple digits. However, when radix does not have a constant (power) relation as in the case of binary numbers and decimal numbers, it is necessary to convert through computation. 1) Radix conversion from a binary number into a decimal number Radix conversion from a binary number to a decimal number can be performed by adding the weight of each digit that is 1 in the binary number. (This is the same as adding the results that are obtained by multiplying the weight of each digit with the number (0 or 1) of each digit.) Example: Perform radix conversion of the binary number (1001101.101)2 into a decimal number. 2) Radix conversion from a decimal number into a binary number Radix conversion from a decimal number into a binary number is performed separately for the integer part and the fractional part. The integer part can be converted by repeatedly dividing by 2 until the quotient becomes 0, and then arranging the remainder of calculation results in sequence from the back. A fractional part can be converted by continuously multiplying by 2 until the fractional part in calculation results becomes 0, and then arranging the integer part of each calculation result in sequence from the front. 26  Chapter 1 Hardware Example: Perform radix conversion of the decimal number (77.625)10 into a binary number. A summary of radix conversion between decimal numbers and n-adic numbers is provided below. [Procedure of radix conversion from an n-adic number into a decimal number] Add all results obtained by multiplying the weight (power of n) of each digit by the number {from 0 through (n−1)} of each digit. [Procedure of radix conversion from a decimal number into an n-adic number] Integer part: Repeatedly divide by n until the quotient becomes 0, and then arrange the remainder of calculation results in sequence from the back. Radix part: Continuously multiply the radix part by n until the radix part in calculation results becomes 0, and then arrange the integer part of each calculation result in sequence from the front. For example, below is an example of radix conversion of the decimal number (67.6875)10 into an octal number. However, when the radix conversion from decimal to octal or hexadecimal is performed, it may be easier to convert from decimal to binary, and then convert the result into octal or hexadecimal. 27  Decimal number: (67.6875)10 = Binary number: (1000011.1011)2 = (001 000 011. 101 100)2 = Octal number: ( 1 0 3. 5 4 )8 [Fractional number that cannot be represented by the finite number of digits] When the fractional part of a decimal number is converted into an n-adic number, it gets into a loop as the fractional part of calculation results does not become 0, and it may not be converted into a finite fraction. For example, converting the decimal number (0.2)10 into a binary number gives the following. In this manner, when the results of radix conversion become an infinite fraction (or recurring fraction), numerical values are handled as approximate values inside the computer. 2 - 3 Representation Form of Data All data is represented with 0 or 1 inside computers. This representation form can be classified as follows: Figure 1-9 Representation Form of data 28  Chapter 1 Hardware 2-3-1 Character Data Inside computers, character data is represented with combinations of 0 and 1. In computers during the early stage of their development, 1 character was linked to a bit pattern of 8 bits (1 byte). Moreover, bit patterns linked to characters were referred to as character codes, with the six main character codes as described below. When data between computers is exchanged by using different character codes, character corruption (garbled characters) may occur where characters that are different from the original data are displayed. (1) ASCII code ASCII code is the character code defined by ANSI (American National Standards Institute) in 1962. It is composed of 8 bits, which include code bits (7 bits) that represent an alphabetic character or a number, and a parity bit (1 bit) that detects an error. Although it is used in PCs, it does not have any definitions concerning Japanese characters (e.g., kanji, kana). (2) ISO code ISO code is a 7-bit character code defined by the standardization agency ISO (International Organization for Standardization) on the basis of ASCII code in 1967. This character code forms the basis of character codes used in different countries all over the world. (3) JIS code JIS code is a character code that is deliberated by JISC (Japanese Industrial Standards Committee) on the basis of the Industrial Standardization Act for representing Japanese-specific characters based on the ISO code and is defined as JIS (Japanese Industrial Standards). 1) JIS 7-bit codes / JIS 8-bit codes (JIS X 0201） This character code can represent half-width katakana characters. Figure 1-10 shows the table of JIS 8-bit codes for reference. Here is how to use the table. Firstly, search in the table for the character to be represented with the code. Secondly, arrange columns (higher 4 bits) and rows (lower 4 bits) from top to bottom and left to right respectively. The arranged numbers form the character code of that character. 29  Example: Convert “JIS” into character code. Character Position in table Character code (Hexadecimal notation) J... 4th column 10th row : 0100 1010 (4A) I... 4th column 9th row : 0100 1001 (49) S... 5th column 3rd row : 0101 0011 (53) Figure 1-10 JIS 8-bit codes (JIS X 0201) 2) JIS kanji code (JIS X 0208) This is a character code for representing 1 hiragana or kanji character with 2 bytes (16 bits). 3) Shift JIS code This code system is formed by expanding JIS kanji code, and it is a character code that enables mixing of 1-byte characters and 2-byte characters without using a special switching code. (4) EBCDIC (Extended Binary Coded Decimal Interchange Code) EBCDIC is an 8-bit character code developed by the IBM Corporation of the United States. This code was originally developed by IBM for its own computers. However, 3rd generation (1960s) computers were mostly IBM computers, and therefore this code became industry standard (de facto standard) in the area of large computers. 30  Chapter 1 Hardware (5) Unicode Unicode is the character code that was developed and proposed by U.S.-based companies like Apple, IBM, and Microsoft as a 2-byte universal uniform code for smooth exchange of computer data. It supports characters of several countries such as alphabets, kanji and hiragana/katakana, Hangul characters, and Arabic letters. This was standardized by ISO as an international standard, and at present, UCS-2 (2 bytes) and UCS-4 (4 bytes) are defined. (6) EUC (Extended Unix Code) EUC (Extended Unix Code) is the character code that was defined by the AT&T Corporation for internationalization support of UNIX (an OS (Operating System), which is a software program for controlling computers). An alphanumeric character is represented with 1 byte, and a kanji or kana character is represented with 2 bytes. In this case, kanji characters are codes where the hexadecimal number “80” is added to JIS kanji code. Therefore, in the kanji part, the value of the most significant bit is “1”, and it is possible to differentiate single byte alphanumeric characters and kanji characters. Moreover, although it is not a character code, zoned decimal numbers are also classified as a code that represents character data (Details of zoned decimal numbers are explained in the next sub-subsection entitled “Numeric data”). 2-3-2 Numeric Data In broad terms, there are two methods for numeric representation inside computers. The first method is to represent numerical values with binary numbers, which is suitable for performing calculations inside computers. However, binary numbers are not easy for humans to use, and therefore there exits another method where decimal numbers are adopted to facilitate understanding for humans. (1) Decimal notation This is a numeric representation method of introducing the way of thinking about decimal numbers that are easy-to-understand for humans. In specific terms, BCD code (Binary-Coded Decimal code) where each digit of a decimal number is converted into a 4-bit binary number is used. 31  Example: Represent (2741)10 with binary-coded decimal code. Decimal numbers : 2 7 4 1 ↓ ↓ ↓ ↓ Binary-coded decimal code : 0010 0111 0100 0001 1) Zoned decimal number This is a format that represents 1 digit of a decimal number with 1 byte. A binary-coded decimal code is stored in the lower 4 bits of 1 byte corresponding to each digit, while zoned bits are stored in the higher 4 bits. However, a sign bit indicating a sign is stored in the higher 4 bits of the lowest digit. Zoned bits and sign bits differ depending on the character code used in computers. When EBCDIC is used, “1111 (F)” is stored in the zoned bit, while “1100 (C)” is stored as a sign bit if it is positive (+) and “1101 (D)” is stored as a sign bit if it is negative (−). On the other hand, when ASCII code or JIS code is used, “0011 (3)” is stored in the zoned bit. In most of the cases, the sign bit uses the same value as in the case of EBCDIC (it differs by manufacturer because there are no uniform definitions). Example: Represent (+672)10 and (−1905)10 with zoned decimal numbers (EBCDIC). 1111 0110 1111 0111 1100 0010 6 7 + 2 1111 0001 1111 1001 1111 0000 1101 0101 1 9 0 − 5 2) Packed decimal number This is a format that represents 2 digits of a decimal number with 1 byte. Each digit of a decimal number is represented with a binary-coded decimal code and this is the same as the zoned decimal number, however, it differs because the sign is shown with the lowest 4 bits, and when it falls short of a byte unit, 0 is inserted to make it a byte unit. 32  Chapter 1 Hardware Example: Represent (+672)10 and (−1905)10 with packed decimal numbers. 0110 0111 0010 1100 6 7 2 + 0000 0001 1001 0000 0101 1101 0 1 9 0 5 − If we compare zoned decimal numbers and packed decimal numbers, by packing after the omission of the zoned bits (higher 4 bits) of zoned decimal numbers, the packed decimal numbers can represent more information (digits) with fewer bytes. Moreover, it is called unpacking to represent packed decimal numbers by using zoned decimal numbers, and therefore the zoned decimal numbers are also referred to as unpacked decimal numbers. While zoned decimal numbers cannot be used in calculations, packed decimal numbers can be used in calculations. However, when decimal numbers from an input unit are entered, or when decimal numbers are sent to an output unit, it is preferable to use zoned decimal numbers because the unit (1-digit numerical value) of input/output and the unit (1 byte) of information correspond to each other. Therefore, conversion between zoned decimal numbers and packed decimal numbers is performed inside computers. Figure1-11 Conversion between zoned decimal numbers and packed decimal numbers inside computers (2) Binary notation Forms for representing numerical values as binary numbers that are easy to handle inside computers include fixed point numbers where the number of digits of integer part and fractional part are decided in advance, and floating point numbers where the position of radix point is changed according to the numerical value to be represented. 33 1) Fixed point numbers In this form of representation, numerical values are handled by fixing the radix point at a specific position. Generally, it is mostly used for handling integer numbers by fixing the position of the radix point in the least significant bit. ▲ (Position of radix point) In this form of representation, after numerical values are converted into binary numbers, they are used without modification according to the position of the radix point. Example: Represent (89)10 as an 8 bit fixed point number. (89)10=(1011001)2 ↓ 0 1 0 1 1 0 0 1 In fixed point numbers, methods of representing negative numbers (representation forms of negative numbers) are important. The two main methods are described below. A: Signed absolute value notation In this method, the most significant 1 bit is used as a sign bit, and 0 is stored in it if the numerical value is positive, while 1 is stored in it if the numerical value is negative. In the remaining bits, the binary bit string is stored as it is. Example: Represent (+89)10 and (−89)10 with an 8-bit fixed point number (signed absolute value). (89)10 = (1011001)2 (+89)10: 0 1 0 1 1 0 0 1 (−89)10: 1 1 0 1 1 0 0 1 B: Complement notation In this method, when a negative number is represented, the complement of the positive number is used. 34  Chapter 1 Hardware [Complement] By using a certain number as the reference value, the shortfall is shown with respect to this reference value. In n-adic number, there is a complement of n and a complement of n −1. Complement of n −1... Reference value is the maximum value that has the same number of digits. Complement of n... Reference value is the minimum value that has one more additional digit. The complement can be determined by subtracting from the reference value the number for which the complement is to be determined. Example 1: Determine the complement of decimal number (614)10 9’s complement 10’s complement 999 1000 − 614 − 614 385 386 Example 2: Determine the complement of binary number (01101101)2 1’s complement 2’s complement 11111111 100000000 − 01101101 − 01101101 10010010 10010011 Example: Represent (+89)10 and (−89)10 with an 8-bit fixed point number (2’s complement). (89)10 = (1011001)2 → 100000000 − 01011001 10100111 (+89)10: 0 1 0 1 1 0 0 1 (−89)10: 1 0 1 0 0 1 1 1 Generally, 2’s complement notation is often used in fixed point numbers for the following reasons. 35 1. Subtraction can be substituted for addition. When signed absolute values are used, addition or subtraction must be appropriately selected according to the first bit of each numerical value to be calculated. However, when 2’s complement is used, calculation can be performed without any selection. By using this, subtraction can be represented with addition. Example: Calculate “(15)10 − (10)10” as “(15)10 + (−10)10”. 1) Represent (−10)10 with 2’s complement. (10)10 = (1010)2 → 100000000 − 00001010 11110110 (−10)10: 1 1 1 1 0 1 1 0 2) Add (15)10 to (−10)10 represented as 2’s complement. (15)10 = (1111)2 (+15)10 0 0 0 0 1 1 1 1 00001111... (+15)10 + 11110110... (−10)10 1 00000101... (00000101)2 = (+5)10 ↑ * Discard the carry-over bit. By using this concept, a feature for subtraction is not required if computer has the feature for addition and the feature for calculating complement. Moreover, if multiplication is done with iterations of addition, and division is done with iterations of subtractions, four basic arithmetic operations (addition, subtraction, multiplication, division) can be done with addition only. 2. A wide range of numerical values can be represented. When signed absolute values are used, two types of 0s, namely (+0) and (−0), occur. However, there is only one type of 0 when 2’s complement is used. Since the information amount of identical numbers of bits is the same, 2’s complement enables the representation of a wider range of numerical values. 36  Chapter 1 Hardware Signed absolute value 2’s complement 01111111 +127 01111111 +127 01111110 +126 01111110 +126 : : : : 00000000 +0 00000000 0 10000000 −0 11111111 −1 : : 11111110 −126 10000001 −127 11111111 −127 10000000 −128 [Range of numerical values that can be represented with n bits (2’s complement)] From −2n−1 through +2n−1−1 2) Floating point numbers If the number of bits that can be used for representing numerical value is decided, the range of numerical values that can be represented with fixed point numbers is limited. Therefore, when a very large numerical value is handled, the number of bits should also be increased accordingly. However, in reality, the number of bits used for recording data cannot be increased infinitely. Therefore, floating point numbers are used to represent extremely large numbers or extremely small numbers below the radix point. Before the explanation of the representation of numbers inside computers, the mechanism of floating point numbers is explained by using decimal numbers. The case that there is the numerical value below is considered here. +456,000,000,000 For the ease of explanation, when 1 unit is used for recording a sign or one number, 13 units are required for recording this numerical value as it is. + 4 5 6 0 0 0 0 0 0 0 0 0 Here, if we convert the numerical value and then record only required information in the following manner, we can represent this numerical value with a total of 6 units. +456,000,000,000 = +0.456×1012 37  = (−1)0×0.456×1012 * (−1)0 = +1, (−1)1 = −1 Sign: Sign to show whether the numerical value is positive or negative 0 Fraction (mantissa): Numerical value to be placed after the radix 4 5 6 point Exponent: Power of 10 to be multiplied by fraction (mantissa) 1 2 This is the concept of floating point numbers. Using this concept, from extremely large numerical values to extremely small numerical values can be represented with the same number of digits. “10” in power of 10 used in representing exponent is called radix. Since a decimal number was used in this explanation, “10” was used as it is easy to understand in terms of moving the radix point. However, since binary numbers are used in computers, either “2” or “16” is used. [Basic form of floating point numbers] (−1)Sign × Fraction (mantissa) × RadixExponent In reality, the form of representation of floating point numbers used inside computers differs depending on the model. Here, we explain the single-precision floating point number (32-bit format) and double-precision floating point number (64-bit format) standardized as IEEE 754 format. A double-precision floating point number can handle a wider range of numerical values with higher precision. [Single-precision floating point number (32-bit format)] Sign Exponent Fraction (mantissa) (1 bit) (8 bits) (23 bits) [Double-precision floating point number (64-bit format)] Sign Exponent Fraction (mantissa) (1 bit) (11 bits) (52 bits) There are several forms of representation of information in each part of the floating point number format. Main forms of representation of each part are as follows: A: Sign (S) 38  Chapter 1 Hardware This is used for representing the sign of a numerical value. It is 0 for positive values, and 1 for negative values. B: Exponent (E) This is used for representing exponent with respect to radix. The two main representation methods below are used. 2’s complement: In this method, exponent is recorded as a binary number, and 2’s complement is used if it is negative (−). Excess method: This method records a value (i.e., biased value) that is obtained by adding a certain value to the exponent. The value (i.e., bias value) to be added is decided according to the number of bits of exponent. Below is an example of the excess method used with single-precision floating point numbers. Format of exponent Intended format Method name Number Information Bias value (Typical example) of bits amount Excess 127 IEEE 754 format 8 bits 256 types 127 Excess 64 IBM format 7 bits 128 types 64 C: Fraction (mantissa) (M) This is used for representing a numerical value after the radix point. In order to represent the part after the radix point, it is common to perform normalization. In this case, the integer part is either set to 0 or 1 (storing after the omission of 1 from the integer part). When the integer part is set to 0: 0.101101 → Store “101101” in fraction (mantissa) When the integer part is set to 1: 1.011010 → Store “011010” in fraction (mantissa) [Normalization] This operation is for maintaining the precision of numerical values by increasing digits that can be used in fraction (mantissa). In most cases, this is done by reducing extra 0s after the radix point. For example, in the case of the decimal number (0.000123456789)10 represented by using a 7-digit fraction (mantissa), if the 7-digit fraction is registered in fraction (mantissa) as is, the following result is obtained. 0 0 0 1 2 3 4 39  In contrast, if the 7-digit fraction is registered in fraction (mantissa) after normalization, the following result is obtained. Normalized form: 0.123456789×10−3 1 2 3 4 5 6 7 In other words, more digits can be represented if normalization is performed (the number of significant digits increases). Therefore, the precision of numerical values becomes high. Example: Express the decimal number (1234.625)10 with the single-precision floating point number (32 bits) of IEEE 754 format shown below. Sign (1 bit): Show a positive value with 0, and a negative value with 1. Exponent (8 bits): Show with excess 127 where radix is 2. Fraction (23 bits): Show with normalized expression where integer part is 1. 1) Convert the decimal number (1234.625)10 into a binary number. (1234.625)10 = (10011010010.101)2 2) Normalize the binary number determined in 1). Normalized form: +(1.0011010010101)2×210 3) Show exponent as a binary number (8 bits) of excess 127. Power of 10 → 10 + 127 = 137 → (10001001)2 4) Describe according to the form of representation. 0 10001001 00110100101010000000000 Sign (1 bit): 0 Exponent (8 bits): 10001001 Fraction (mantissa) (23 bits): 00110100101010000000000 40  Chapter 1 Hardware 2-3-3 Error Error refers to the difference between the actual value and the value represented inside the computer. When numerical values inside the computer are handled, we must pay attention to error. For example, when (0.1)10 is converted into a binary number, it is represented as follows: (0.1)10 = (0.00011001100110011...)2 The conversion result becomes a recurring fraction where “0011” is repeated an infinite number of times. However, since there is a limit for the number of bits that can be used for representing numerical values inside computers, the only option for storing in fraction (mantissa) is to store after the loop is cut in the middle. If it is 8 bits, only up to (0.00011001)2 can be stored. When this binary number is converted into a decimal number, (0.09765625)10 is obtained. In other words, this is different from the original numerical value (0.1)10 by only (0.00234375)10. This is error. (1) Rounding error Rounding error occurs when the part smaller than the least digit is rounded off, rounded up, or rounded down in order to represent the real number with the effective number of digits in the computer. When a decimal number is converted into a binary number, this kind of error occurs to represent the resulting binary number with the effective number of digits. As a measure against rounding error, there are methods such as minimizing the value of error as much as possible by changing single precision (32 bits) into double precision (64 bits). (2) Loss of trailing digits Loss of trailing digits is the error that occurs when an extremely small value is ignored at the time of computing two values: one absolute value is extremely large and the other is extremely small. Example: Calculate (0.10110011)2 × 210 + (0.11010001)2 × 2−10. 41 In order to minimize loss of trailing digits, when multiple numerical values are added with floating point radix numbers, it is necessary to take steps such as arranging all data in the ascending order of absolute value, and adding them in sequence from the top (smaller value). (3) Cancellation of significant digit Cancellation of significant digit is the error that occurs because of decline in the number of significant digits that can be trusted as numerical values when calculation is performed between almost equal numerical values. Example: Calculate (0.10110011)2 × 20 − (0.10110010)2 × 20. (4) Overflow, underflow Inside a computer, the range of numerical values that can be represented is already decided, because the limited number of bits is used for representing them. Flow is the error that occurs when the calculation results exceed this range of representation. When the calculation results exceed the maximum value of range of representation, it is referred to as overflow, and when it exceeds the minimum value, it is referred to as underflow. When it is simply referred to as “flow,” it mostly means overflow. Minimum value Maximum value Range of representation of numerical values ← ← [Underflow] ← ← → → [Overflow] → → Moreover, the following two indexes are used as the concept of evaluating these errors (whether precision is high or low). Absolute error: This is an index that evaluates on the basis of how large the actual error is. Absolute error = | True value − Computed value (including error) | 42  Chapter 1 Hardware Relative error: This is an index that evaluates on the basis of the proportion (ratio) of error with respect to true value. | True value − Computed value (including error) | Relative error = | True value | 2-3-4 Shift Operation Shift operation is the operation of shifting the position of bit to left or right. Shift operation is used in computation of numerical values, and in changing the position of bits. (1) Arithmetic shift Arithmetic shift is the shift operation used when numerical values are computed. It is mainly used in fixed point numbers that represent negative values in 2’s complement. [Rules of arithmetic shift] Do not shift the sign bit. Truncate extra bits that are shifted out as a result of the shift. Store the following bit in the empty bit position that is created as a result of the shift. In the case of left shift: 0 In the case of right shift: Same as the sign bit Example: Shift (22)10=(00010110)2 arithmetically left by 2 bits. Binary numbers have weight of power of 2 in each digit. Therefore, even for the same numeral 1, 1 as the second digit and 1 as the third digit have different meanings. 1 as second digit: (10)2 → 21 = 2 1 as third digit: (100)2 → 22 = 4 43 Because of this, computation rules of arithmetic shift can be summarized as follows: [Computation rules of arithmetic shift] With an arithmetic shift to left by n bits, the value becomes 2n times of the original number. With an arithmetic shift to right by n bits, the value becomes 2−n times of the original number. (It is the value that is obtained by dividing the original number by 2n) (2) Logical shift Logical shift is the shift operation used when the position of bits are changed. Its main difference from the arithmetic shift is that it does not treat the sign bit in a special manner. [Rules of logical shift] Shift (move) the sign bit as well. Truncate extra bits that are shifted out as a result of the shift. Store 0 in the empty bit position that is created as a result of shift. Example: Compare the results of 2-bit arithmetic shift right and 2-bit logical shift right for (−16)10 = (11110000)2. 1) Perform 2-bit arithmetic shift right. 2) Perform 2-bit logical shift right. 44  Chapter 1 Hardware Rotation shift (circular shift) is a type of logical shift. In rotation shift, the bits shifted out are circulated to the empty positions. Example: Perform 2-bit rotation shift right on (11010010)2. 45 3 Central Processing Unit and Main Memory Unit Data processing in computers takes place in the steps of “Input → Processing → Output.” Section 1 explained the CPU (Central Processing Unit) that handles “Processing” in this series of steps is composed of a control unit and an arithmetic and logical unit. This section describes more detailed operating principles of the CPU and the main memory unit that is closely related to the CPU. 3 - 1 Configuration of CPU In computers based on stored-program, programs (instructions) recorded in the main memory unit are read in the CPU one by one, and the control unit issues directions to each device on the basis of the contents of the instruction for processing. In order to carry out this operation, the CPU is composed of various devices and components. Figure 1-12 Components of CPU (1) Control unit Control unit is a unit that decodes the instruction to be executed and gives directions to each device. It is composed of a decoder (instruction decoder that interprets the instruction to be executed), etc. (2) Arithmetic and logical unit Arithmetic and logical unit is a unit that performs computations inside computers. It is composed of an ALU (Arithmetic and Logical Unit) that uses an adder for addition, a complementer for calculating complements, and such other components. 46  Chapter 1 Hardware (3) Register Register is a device used for temporarily storing various data inside the CPU. Different types of registers are available according to the type of data to be stored. The main registers (details of each register are explained later) are as follows: Instruction register It stores the instructions to be executed. It is composed of an instruction part and an address part. Instruction address register (program counter, program register) It stores the address (storing position in the main memory) of the instruction to be executed next. General register It is used for various purposes such as storing the data to be processed. Accumulator It stores the data for performing computations. It is sometimes also substituted with a general register. Base address register It stores the beginning address of a program. Index register It stores the index for address modification. Flag register It stores the information of a certain status (whether the results of computations are positive or negative, etc.). Depending on the status of this register, the next action, such as branch destination of the condition branch instruction, is decided. PSW (Program Status Word) It stores the running status of a program (value of program counter, value of flag register, etc.) (4) Clock generator Clock generator is a device for generating signals (clock signals) in order to synchronize and control the timing of operations between various devices inside computers. The speed of generating clock signals is shown with clock frequency, and MHz (Mega Hertz) (1 Million times in 1 second) is used as the unit. Usually, either the rising or falling edge of a signal is used as synchronization timing, and there is a technique called DDR (Double Data Rate) that uses both. 47  Figure 1-13 1 cycle of clock frequency (5) Bus Bus is the signal path for connecting various devices and registers, and transmitting data and control signals. Concerning the bus, there is a serial bus that sends data in the sequence of 1 bit each, and there is a parallel bus that simultaneously sends multiple bits. Performance of bus is decided by the access mode, such as the number of bits that can be sent in one clock signal (bus width) and clock signal, which is defined for each bus. [Classification according to connection point] 1) Internal bus (CPU internal bus) This is a bus used inside the CPU. 2) External bus (CPU external bus) This is a bus that connects the CPU and the external devices. The clock frequency of the external bus is generally different from that of the CPU. System bus: Collective term for the buses directly connected from CPU to outside Memory bus: Bus that is mainly connected to the main memory unit Input/output bus: Bus that is mainly connected to the input/output devices 3) Expansion bus This is a bus that connects the PC and the expansion cards. [Classification according to usage] 1) Address bus: Bus for specifying the reference address to the main memory unit 2) Control bus: Bus for giving directions to each device from the control unit 3) Data bus: Bus for exchanging data In conventional buses (Neumann architecture), the same bus was used for loading instructions and data. However, in modern-day computers, for loading instructions and data, Harvard architecture is used where independent buses are provided for loading instructions and data. The main buses presently used in PCs are shown below. Other than in PCs, various buses are used (there are also manufacturers’ specific buses). 48  Chapter 1 Hardware PCI (Peripheral Component Interconnect) This is an external bus specification defined by Intel Corporation, USA. PCI specification of bus width 32 bits, bus clock 33 MHz, and transfer rate of 133 megabytes/second is common. PCI Express (PCIe) This is an external bus specification defined by PC