🔙 Quay lại trang tải sách pdf ebook Giáo trình tiếng Anh chuyên ngành khoa học máy tính Ebooks Nhóm Zalo Ks. Châu Vân Trung Cộng tác: Ts. Nguyễn Phi Khứ - Quang Hùng - N G I Á O T R Ì Í I H T I É H C A Í 1 H chuyên ngành ____ ____ / 7 ___________ n _________ S.Ệ-:Í • * Ị- •* B H i 1 0 ? \ x ễ = ị ỉ « . I. fị I M ‘ 1 k . NHÀ x u ấ t b ả n g ia o t h ô n g v ậ n t v f G IÁ O TR ÌN H T IẾ N G A N H C H U Y Ê N NGÀNH KHOA HỌC M Á Y TÍNH Ks. Châu Văn Trung C ộng tác: Ts. Nguyễn Phi Khứ - Quang Hùng GIÁO TRÌNH TIẾNG ANH C huyên ngành KHỠA HỌC MÁY TÍNH A course of Basic English for Computer Scienc« (D à n h ch o sinh viên K hoa học Tự n h iên - K ỹ th u ậ t - C ông ngh ệ th ô n g tin ) N H À XUẤT BẢN GIAO THÔNG VẬN TẢI Lời nói đầu Nh ằm đáp ứng nhu cầu giảng dạy và học tậ p của các sinh viên chuyên n g à n h công nghệ thô n g tin và kỹ th u ậ t m áy tín h , chúng tôi biên soạn và xuất b ản quyển "Giáo trình tiêng Anh Chuyên ngành Khoa học Máy tính". Sách gồm 9 chương, trìn h bày những vấn đề căn b ản n h ấ t của chuyên n g àn h khoa học m áy tín h như: các kh á i niệm cơ bản về m áy tín h ,th iế t k ế và hoạch đ ịn h cliưang trình, viết m ã chương trìn h và các lệ n h nh ậ p Ix u ấ t đơn giản, cấu trúc điều khiển và vấn đề viết chương trình,các h à m và thường trình con, m ảng và chuỗi, các file d ữ liệu, lập trìn h hướng đối tượng và các cấu trúc d ữ liệu. Bô cục m ỗi chương gồm p h ần mục đích yêu cầu, trìn h bày nội dung bài học theo từ n g chủ điểm bằng tiế n g A nh, chú th ích từ vựng và hướng d ẫn dịch, dọc hiểu nội dung qua tiế n g V iệt, sau cùng là bài tậ p có lời giải, bài tậ p bổ sung và đáp án. T ính đa d ạng và phong phú của nội dung và bô cục ch ặ t chẽ hợp lý, dễ học k h iế n cho giáo trìn h m ang tín h sư phạm cao, giúp người đọc dễ d àng tiế p cận với những vấn đề m à nội dung nêu ra. C húng tôi hy vọng rằ n g giáo trìn h sẽ giúp ích nhiều cho các giáo viên và sin h v iê n tro n g việc tiếp cận với nhữ ng vấn đề căn b ản n h ấ t của chuyên n g à n h khoa học m áy tính. N h ó m biên soạn Chương 1: Các khái niệm cơ bản về máy tính 7 •|LBasic Concepts ol Compulers CHAPTER Cóc khái niệm cơ bản về máy tính MỤC ĐÍCH YÊU CẦU Sau khi học xong chương này, các bạn sẽ nắm vững các khái niệm cơ bản về máy tính, cụ thể với các nội dung như sau: ♦ C o m p u te r s tr u c tu r e s C ấ u tr ú c m á y tín h ♦ B u s s tr u c tu r e C ấ u tr ú c B u s ♦ B a s ic o p e r a tio n o f th e c o m p u te r H o ạ t d ộ n g cơ b ả n c ủ a m á y tín h ♦ R e p r e s e n ta tio n o f d a ta in m e m o ry K iểu trìn h bày d ữ liệu troiig bộ n h ớ ♦ C o n v e r s io n b e tw e e n th e b in a r y , « C h u y ể n d ổ i g iữ a c á c h ê n h ị o c ta l, a n d h e x a d e c im a l s y s te m s p h ả n , b á t p h â n và th ậ p lụ c ♦ R u le s fo r f o rm in g n u m b e rs in a n y C ác q u y tắ c b iể u d iễ n cá c s ố s y s te m tr o n g b ấ t h ệ th ố n g n à o ♦ A r ith m e tic o p e r a t i o n in th e b i­ C ác p h é p to á n s ố h ọ c tr o n g các n a r y , o c ta l, a n d h e x a d e c im a l s y s ­ h ệ n h ị p h â n , th ậ p p h á n v c th ậ p te m s lụ c p h â n ♦ R e p r e s e n tin g n u m b e rs in a co m ­ T r ìn h b à y các s ố tr o n g m 1 1 m á y p u te r tính Ngoài ra, ở cuối chương còn có phần bài tập có lời giải, bài tập bổ sung và phần đáp án nhằm giúp các bạn thực hành và áp dụng một cách hiệu quả vào công việc thực tế. GIỚI THIỆU C H U N G ___________________________________ A computer is a device which, under the direction of a program, can process data, alter its own program instruction, and perform computations and logical operations without human intervention. The term program refers to a specific set of instructions given to the computer to accomplish a specific task. A pro grammer is a person or group of persons who write instructions to the computer. Programs, in general, are referred to as "software". A computer can be considered at two different levels: its architecture and its implementation. The architecture consists of the user-visible inter face as seen by the programmer. That is, the structure and operation of the computer from the programmer’^ point of view. The implementation of the computer is the construction of that interface using specific hardware (and possible software components). In ihis book we will refer to computer com ponents such as monitors, printers, keyboards, and some other of its elec tronics as "hardw are". Chapter 1: Basic Concepts of Computers HỦ ĐIỂM 1.1 COMPUTER STRUCTURES C đ u ỈP Ú C m a i j t í n h Most computer systems generally consist of three basic structures or ibsystems: the high-speed memory unit, the central processing unit, and le peripheral devices that comprise the I/O subsystem (see Fig 1-1). Fig. 1-1 Basic computer structure. /---------------- V keyboard _ _ I I Input and O u tp u t bus î I .1.1 The Memory Unit - Bộ nhớ The memory unit of the computer, also called main memory or physical lemory, stores all the in stru c tio n s a n d d a ta th at the central processing nit can directly access and execute. The memory of majority of computers onsists of chips made of metal oxide on silicon. This type of memory is Iso called Random Access M em ory or RAM. The memory of the computer is generally divided into logical units of he same size. The most common unit is called a byte. Each byte is made ip of 8 consecutive bits or binary d ig its (see Fig. 1-2). Each individual bit an be magnetized to one of two different states, hence the nam e of binary. )ne state is said to represent 1; the other represents 0. Sometimes these wo states are referred to as “On” and “Off” respectively. Each byte has associated with it a unique address. According to the :onvention used, addresses can increase from right to left or left to right see Fig. 1-3). In this book we will assume that addresses increase frorn •ight to left unless we specify otherwise. The address space is the set of all jnique addresses that a program can reference. The number of biỉó Used to represent an address determines the size of the address space. The size of Hiis snacp can be calculated by 2 where N is the number of bits used t, Chương 1: Các khái niệm cơ bản về máy tinh represent the address. It is important to observe that there is a different between the address of a memory unit and the content of that unit. Ti address of a byte is fixed whereas its content may vary. 1 byte Most significant bit7 6 5 4 3 1 «Least significant bit Fig. 1-2 Representation of a byte. 3 2 1 0 <----------------------- Fig. 1-3 Increasing addresses. Bytes are also grouped into larger units. Depending on the conventic used by the manufacturers, these larger units can be called by differej names. Table 1-1 shows the common names of some of the smaller ar larger units. Table 1-1 1 nibble 1 byte 1 word 1 longword 1 quadword 1 octaword 4 consecutive bits 8 consecutive bits 2 consecutive bytes 4 consecutive bytes 8 consecutive bytes 16 consecutive bytes As shown in Fig. 1-2, the bits of a byte are generally numbered fro right to left beginning with 0. The rightmost bit is called the le a s t sij n ific a n t b it (lsb). Likewise, the leftmost bit is called the m ost signil c a n t b it (msb). Since each bit of a byte can only store one of two values, either a zero i one, there are 28 differei 1 'configurations of bits within a byte. Each coi binati in represents a unique value. The value that each combination bits represents in a byte depend-s on" the convention used to interpret thei 10 Chapter 1: Basic Concepts of Computers 'alues (see Example 1.5). Assuming that the bits are unsigned, the decimal 'alue represented by the bits of a byte can be calculated as follows. (1) Number the bits beginning on the rightmost bit position using su perscripts. The superscript of the rightmost position is zero. The superscript of the next bit to its left is 1, the superscript of the next bit to the left is two and so on. (2) Use each superscript as the exponent of a power of 2. (3) Multiply the value of each bit by its corresponding power of 2. (4) Add the products obtained in the previous step. iXAMPLE 1.1 W hat is the decimal value of the unsigned binary configura ion 11001101? 1) Number the bits beginning on the rightm ost bit position using super scripts as shown below. lW 0 ’.’W l ° 2) Use each superscript as the exponent of a power of 2. (1*2’) + (1*26) + (0*25) + (0*24) + (1*2J) + (1*22) + (0*2') + (1*2°) 3) Multiply the value of each bit by its corresponding power and add the results (1*128) + (1*64) + (0*32) + (0*16) + (1*8) + (1*4) + (0*2) + (1*1) = 205 Therefore, the decimal value of the unsigned binary configuration 11001101 is 205. Rem em ber that 2°, by definition, is equal to 1. An other method to calculate the value of an unsigned binary number is explained in solved problem 1.19. The size of the memory of a computer, as indicated before, is measured in bytes. However, the size of the memory is generally expressed in larger units. One of the most common units is the Kilobyte or Kbyte or simply K. In computer lingo, 1 K is equal to 1024 bytes. W henever a rough approxi mation is required, IK can be considered as being equivalent to 1000 bytes. Table 1-2 shows some of the other units currently used to measure primary memory. As of the writing of this book, the Megabyte or MB (=106 bytes) is the most commonly used unit to express the size of the prim ary memory; however, it is expected that some of the larger units will be used more frequently in the near future. The symbol should be read as “approximately equal to.” Chuang 1: Cac khai ni$m cd ban ve may tinh 11 Table 1-2 1 Kilobyte =1024 bytes 1 Megabyte = 106 bytes 1 Gigabyte * 109 bytes 1 Terabyte * 1012 bytes 1 Petabyte = 1015 bytes 1 Exabyte = 1018 bytes EXAMPLE 1.2 A computer is advertised as having a primary memory of 32 Megabytes or “Megs.” W hat is the true size of the memory in bytes? 32 M b y tes = 32*10’ K bytes = 32*103*1024 b y tes = 32,768,000 b y tes 1.1.2 The Central Processing Unit - Bq xCrly trung tam The C entral P rocessing Unit (CPU) or processor is the “brain of the computer.” It is in the CPU where most of the activity that occurs inside the computer takes place. The CPU is generally subdivided into two basic subunits: the A rithm etic-Logic Unit (ALU), and the Control Unit (CU). The main activity of the CPU consists of retrieving (fetching) instruc tions from memory and executing these instructions. As the instructions are fetched from memory they are decoded. Decoding an instruction means interpreting w hat the instruction is all about and what are its operands, if any. Executing means doing what the instruction is m eant to do. The ALU or the Arithmetic-Logic Unit of the CPU, as its name implies, is where the arithm etic operations (addition, subtraction, etc.) are per formed. Similarly, other operations such as the comparison of two numbers are also carried out in the ALU. Internal to the CPU there are a number of “general” registers th at provide local, high-speed storage for the processor. Consider a typical situation where two numbers located in main memory are to be added. This operation may be executed as follows: first, the num bers, located in main memory, are fetched into the internal registers of the ALU where the addition is carried out. The sum, if necessary, may be stored back into some particular memory location. In addition to these high-speed internal registers, the CPU contains one or more “status registers” that provide information about the state of the processor, the instruction being processed, any other special condition that may have occurred, and the actions that need to be taken to handle these special conditions. 12 Chapter 1 : Basic Concepts of C o m p u te rs The Control Unit in the CPU manages the movement of data within the processor. For example, to add the numbers of the previous example, the operands had to be moved from memory to the ALU. It is the responsibil ity of the control unit to manage this movement of data. If the result of the addition is to be stored back in memory the control unit will manage this task too. Incorporated within the control unit is a decoder which deter mines the operation that the computer needs to carry out. 1.1.3 The Input and Output Unit: Bộ nhập và xuất Computers accept information via input devices. Input devices are em ployed by the user to send information to the computer. Two of the most common input devices are the keyboard and the mouse. Output devices are used to send information to the user. The most common output devices are the monitor and the printer. Other devices such as some of the external storage units (hard disks, tapes, jazz or zip drives) may serve a dual pur pose. Input and output are among the most complex operations carried out by the CPU. Details about the physical characteristics of the I/O devices and the data format that they require are handled by system programs that are invisible to the user. A discussion of the issues involved in I/O processing is beyond the scope of this book. CHÚ THÍCH TỪ VƯNG program programmer software hardware instructions and data Memory bits or binary digits Central Processing Unit Arithmetic-Logic Unit Control Unit HƯỚNG DẪN ĐỌC HIEU 1.1 chương trình người lập trình phần mềm phẩn cứng chỉ lệnh uà dữ liệu bộ nhớ các bit và các chữ số nhị phân bộ xử lý trung tám bộ logic sô học bộ điều khiển Một máy tinh là một thiết bị dưới sự điều khiển của một chương trình, cỏ thè xu ly dữ liẹu, tự nó biên đôi câu trúc chương trình, VQ thực hiện các phép tính và các phép tinh logic mà không cần sự can thiệp của con người. Thuật ngữ program chi ra một tập hạp các lệnh đặc biệt để đưa vào máy tính nhàm thực thi một nhiẹm vụ đặc biệt Chương 1: Các khái niệm cơ bản về máy tính 13 Một programmer (một người lập trình) là một người hoặc một nhóm người viết các cău lệnh cho máy tính. Nhìn chung, các chương trinh được biết như là 'software (phần mềm)'. Một máy tính có thể dược xem xét theo hai góc độ khác nhau: cấu trúc máy tính của nó và tính thực thi của nó. Cấu trúc này bao gồm giao diện người dùng hiển thị xét theo góc độ nhà lập trình. Điều này có nghĩa là cấu trúc và các phép tính toán máy tính theo quan điểm của lập trình viên. Tính thực thi của máy tính là cấu trúc của giao diện bằng cách sử dụng phần cứng (và cũng có thể là phần mềm). Trong sách này bạn sẽ tham khảo về các thành phần của máy tính chẳng hạn như màn hình, máy in, bàn phím và một số thiết bị điện tử khác dược biết như là “phần cứng”. 1.1 CẨU TRÚC MÁY TÍNH Hầu hết các hệ thống máy tính bao gồm ba cốu trúc cơ bản hoặc các hệ thống phụ: bộ nhớ tốc độ cao, bộ xử lý trung tăm, và các thiết bị ngoại vi bao gòm các hệ thống phụ n o (xem hình 1.1) 1.1.1 Bộ nhớ Bộ nhá của máy tính cũng được gọi là bộ nhớ chính hoặc bộ nhớ vật lý lưu trữ cấu trúc và dữ liệu để cho bộ nhớ trung tâm có thể truy cập và xử lý trực tiếp. Hầu hết bộ nhá của máy tính có chứa các con chip được làm từ oxit kim loại trẽn silicon. Loại bộ nhớ này còn được gọi là bộ nhớ truy cập ngẫu nhiên hoặc RAM. Bộ nhớ của máy tính thường được chia thành các đơn vị logic theo cùng kích cỡ. Các đơn vị phổ biến này cũng đượv gọi là byte. Mỗi byte được làm từ 8bit liên tục hoặc các số nhị phân (xem hình 1.2). Mỗi bít riêng lể có thể được từ hóa một trong hai trạng thái khác nhau theo tên nhị phân. Một trạng thái được mô tá là 1; trạng thai khác là 0. Dôi lúc, hai trạng thái này còn được gọi là “On” và “Off”. Mỗi tiyte liên kết vái một địa chỉ duy nhát. Dựa vào tính tỷ lệ khi sử dụng, các địa chi này có thể tăng từ phải sang trái hoặc từ trái sang phải (xem hình 1.3). Trong sách này chúng ta sẽ giả sử rằng các địa chi sẽ tăng từ phải sang trái nếu không chúng ta sẽ nói về trường hợp khác. Không gian địa chỉ là tập hợp các địa chỉ để một chương trình có thể tham chiếu, s ố các bit sử dụng để mô tả các địa chỉ được xác định bằng kích cỡ của không gian địa chỉ. Kích cỡ của không gian này có thể duạc tính bằng 2"- với n là số các bit được sử dụng đ ể mô tả địa chỉ này. Điều này rất quan trọng trong việc quan sát sự khác biệt giữa địa chỉ bộ nhá và nội dung của bộ nhớ đó. Địa chỉ của một byte là cố d in ’ll trong khi đó nội dung của nó có thể biến đổi. Các byte cũng có thể được gom nhóm để tạo thành các bộ lán hơn. Tùy 14 Chapter 1: Basic Concepts of Computers thuộc vào sự thuận lợi của các nhà sản xuất, các đan vị lớn hơn này có thể được gọi bằng nhiều tên khác nhau. Bảng 1.1 trình bày các tên phổ biến của các đơn vị nhỏ hơn và lớn han. Như được minh họa trong hình 1.2 các bit của một byte thường dược đánh số từ phải sang trái bắt dầu là 0. Bit bên phải nhát được gọi là least significant bit (Isb). Tương tự như vậy, bít bên trái nhất được gọi là most significant bit (msb). Bởi vì mỗi bít của một byte chi có thể được lưu chỉ một trong hai giá trị, hoặc là zero hoặc là 1, do dó có 2S số bit khác nhau trong một byte. Mỗi một tổ hợp mô tả cho một giá trị riêng biệt. Giá trị của mỗi tổ hợp bít mô tả trong một byte phụ thuộc vào quy ước sử dụng đ ể giải thích cho các giá trị đó (xem ví dụ 1.5). Giả sứ ràng các bít này chưa được kỷ hiệu, thì giá trị thập phán mô tả theo các bit của một byte có thể tính toán như sau: (1) Đánh số thứ tự cho các bít bắt đầu tại vị trí bít phải nhất theo cách đánh số mũ. Sô mũ của vị trí phải nhất là zero. Sô m ũ của các bit kế tiếp ở bên trái là 1, sô' mũ của bít kế tiếp ở bẽn trái là hai và .... (2) Sứ dụng mỗi số ở mũ giống như số mũ của 2. (3) Nhăn giá trị của mỗi bít với lũy thừa tương ứng là 2. (4) Cộng các tích sô được cho theo các bước. Ví dụ 1.1 Giá trị thập phân của một số nhị phân có dạng 11001101 là bao nhiêu? (1) Đánh số thứ tự các bít bắt đầu tại bit phải nhất bàng cách sử dụng số mũ như được trình bày dưới đây. f l W l W l 1 (2) Mỗi sổ mũ là lũy thừa của 2. (1*2’ ) + (1*26) + (0*25) + (0*24) + (1*23) + (1*2! ) + (0 * 2 ') + (1*2°) (3) Nhăn giá trị của mỗi bit với số mũ tương ứng rồi cộng kết quả lại (1 * 1 2 8 )+ (1 * 6 4 )+ (0 * 3 2 )+ (0 * 1 6 )+ (1 * 8 )+ (1 * 4 ) + ( 0 * 2 ) + (1*1) = 205 Do đó giá trị thập phán của một sổ nhị phân 11001101 là 205 Hãy nhó rằng 2° theo định nghĩa là 1. Các phưcmg pháp đ ể tính giá trị của một sô nhị phản được giải thích trong bài thực hành 1 19 Kích thước bộ nhớ cùa máy tính như dược trình bày trước đây được đo băng byte. Tuy nhiên kích thước bộ nhớ máy tính dược mỏ tả ở đơn vị lớn hơn. Một trong những đơn vị thường dùng là kilobyte hoặc Kbyte Chương 1: Các khái niệm cơ bản về máy tính 15 hoặc đơn giản là K. Theo ngôn ngữ máy tính, 1 K = 1024 byte. Tuy nhiên, khi tính gần đúng, một ký có thê được lẽn gần bằng 1000 byte. Bảng 1.2 trình bày các đơn vị hiện hành hiện đang sử dụng để tinh toán bộ nhớ chính. Trong sách này, Megabyte hoặc MB ( X 10e bytes) là đan vị tính toán thông dụng nhất để trình bày kích cỡ bộ nhớ chính; tuy nhiên, trong tương lai gần đây các đơn vị lớn hơn sẽ được dùng thường xuyên hơn. Ký hiệu S5 sẽ được đọc là “xấp xỉ bằng”. Ví dụ 1.2 Một máy tính được quảng cáo có bộ nhớ chính là 32 mega bytes gọi “Megs”. Vậy kích cỡ bộ nhớ là bao nhiêu byte? 32 M b y tes = 3 2 ‘ lơ 3 K bytes = 32*103*1024 bytes = 32,768,000 bytes 1.1.2 Bộ x ử lý tru n g tám Bộ xử lý trung tăm (CPU) hoặc trình xử lý là “bộ não của máy tính”. Nó nằm trong CPU nơi mà hầu hết các hoạt động diễn ra trong máy tính đều xảy ra. CPU thường được chia thành hai đơn vị con cơ bản: Đơn vị số học [Arithmetic-Logic Unit (ALU)], và Bộ điều khiển (Con trol Unit - CU). Hoạt động chính của CPU bao gồm các lệnh truy hồi (gọi lại) từ bộ nhá và chạy các lệnh này. Khi các lệnh này được gọi lại từ bộ nhá và chúng sẽ được giải mã. Việc giải mã một câu lệnh có nghĩa là giải mã ít cảu lệnh này và tất cả những toán tử của nó nếu có. Việc xử lý có nghĩa là thực thi những gì câu lệnh đó yêu cầu. ALU hoặc Arithmetic-Logic Unit (Đơn vị số học logic) của CPU,là nai mà các phép toán số học (cộng, trừ, ....) được thực thi. Tương tự, các phép toán khác chẳng hạn như so sánh giữa hai số cũng được tiến hành trong ALU. Bên trong CPU có các thanh ghi tổng quát để cung cấp vị trí, vùng lưu trữ tốc độ cao , bộ xử lý. Giả sử trong tình huống này có hai số nằm tại bộ nhớ chính dược thêm vào. Phép tính này có thể được thực hiện như sau; đầu tiên, các số nằm ở bộ nhá chính sẽ được gọi vào các thanh ghi bên trong của ALU nơi mà phép cộng được thực hiện. Nếu cần, tổng có thể được lưu trữ trở lại trong vùng nhớ đặc biệt. Ngoài những thanh ghi bên trong có tốc độ rao này, thì CPU có chứa một hoặc nhiều “thanh ghi trạng thái' để cung cấp thông tin về trạng thái của bộ xử lý này, lệnh đang được xử lý và bất kỳ các điều kiện đặc biệt nào có thể xảy ra khác, và các nành độ.ig cần thiết đ ể tác động theo một các điều kiện đặc biệt này. Bộ điều khiển trong CPU quản lý sự di chuyền dữ liệu bên trong bộ xử lý. Ví dụ để cộng thêm các sô' của ví dụ trước, các toán hạng phải dược di chuyển từ bộ nhớ sang ALM. Trách nhiệm của bộ điều khiển là quản lý sự di chuyển cửa dữ liệu. Nếu két quả của phép cộng được lưu trữ lại bèn trong bộ nhớ thì bộ điều khiển này cũng sẽ quản lý 16 Chapter 1: Basic Concepts of Computers nhiệm vụ này. Sự kết hợp bên trong bộ điều khiển là một bộ giải mă dể xác định phép toán mà máy tính cần phải thực hiện. 1.1.3 Bộ nhập và xuất Máy tính đảm nhận thông tin thông qua các thiẽt bị nhập. Các thiêt bị nhập được người dùng sử dụng dể gởi thông tin vào máy tinh. Hai thiết bị nhập phổ biến nhất dó là bàn phím và chuột. Các thiết xuất thường được sử dụng dể gởi thông tin cho người dùng. Các thiết bị xuất phổ biến đó là màn hình và máy in. Các thiết bị khác chẳng hạn như các bộ lưu trữ ngoài (các đĩa cứng, các băng từ, các đĩa ja zz hoặc zip) có thể phục vụ cho hai mục đích. Nhập va xuất là một trong các phép tính phửc tạp nhất mà CPU phải thực hiện. Các chi tiết về các kỷ tự vật lý của các thiết bị cho nhập xuất (HO) và định dạng dữ liệu mà chúng yêu cầu được xử lý bởi hệ thống chương trinh vốn không hiển thị cho người dùng, vấn đề xử lý nhập xuất (I/O ) được thảo luận sau chương này. Chương 1: Các khái niệm cơ bản về máy tính 17 CHỦ ĐIỂM 1.2 BUS STRUCTURE C au trúc Bus To transfer data within its different components the computer uses a collection of wires called a bus. A computer system typically has three such buses: the address bus, the data bus, and the control bus. The data bus is used for transm ission of data. A data bus must have as many wires as there are bits in the memory unit selected for a particular computer. To access data in memory it is necessary to issue an address to indicate its location. The CPU sends address bits to memory via the address bus. Figure 1-4 shows a two-bus structure computer. The CPU interacts with memory via the memory bus. Input and Output functions are conducted via the I/O bus. Other configurations are also used. Figure 1-5 shows a single-bus structure used in some small computers. Fig. 1-4 A two-bus structure. In p u t I /O B u s O u tp u t M a in M em o ry Memory bus Fig. 1-5 Single bus structure. C P U EXAMPLE 1.3 Assuming that the basic unit of a computer is a word, how many bits can be transferred by the data bus at any-»R e"ti^? The answer depends on the number of bits that'itfe^nta, word. Using Tablel-1 the number of bits that needs to be t r a n s ^ ^ Q U a r l i a s t 16 bits. We say at least since some additional,. eonftMl Inform ation ma4 be carried on the data bus. I "j 18 Chapter 1 : Basic Concepts of Computers CHÚ THÍCH TỪ VƯNG______________________________ _______ address bus ■ bus địa chi ♦ data bus •' bus dữ liệu ♦ control bus •' bus diều khiên ♦ Input and Output functions : các chức năng nhập và xuất HƯỚNG DẦN ĐỌC Hiểu 1ễ2 _________________________ Để vận chuyển dữ liệu bên trong các thành phần khác nhau, máy tính sử dụng một tập hợp các dây được gọi là bus. Một hệ thống máy tính thường có ba bus: bus địa chỉ, bus dữ liệu và bus điều khiển. Bus dữ liệu được dùng để chuyển tải dữ liệu. Một bus dữ liệu phải có nhiều đầu khi có nhiều bít trong bộ nhớ được chọn cho một máy tính đặc biệt. Để truy cập dữ liệu trong bộ nhớ nếu cần phải cấp phát một địa chỉ chi ra vị trí của nó. CPU này gen các bít địa chì đến bộ nhớ thông qua bus địa chỉ. Hình 1.4 hiển thị một cấu trúc hai bus của máy tính. CPU này tương tác với bộ nhớ thông qua bus bộ nhớ này. Các chức năng nhập và xuất được hướng dẫn thông qua bus 110. Các cấu hình khác cũng được sử dụng. Hình 1.5 minh họa một cấu trúc bus đơn được dùng trong nhiều máy tính nhỏ. Input Main Memory CPU Output Memory Hình 1.4 Cấu trúc hai bus Hình 1.5 Cấu trúc cứa bus dan Ví dụ 1.3 Giả sứ ràng đơn vị ca bản của một máy tính là từ có bao nhiêu bit có thề chuyền tải bởi bus dữ liệu cùng một lức? Câu trả lời dựa trên số bít trong một từ. Sử dụng bảnẹ 1.1 số các bit cân đe chuyen tữi tợo ĩ lột thời đỉẽĩTi ít nhât là 16 bit. ũ đây chúng ÍQ nói ít nhát bởi ui sẽ có một sô thông tin điều khiển có thể được mang theo bus dữ liệu. Chương 1: Các khái niệm cơ bản về máy tinh 19 CHỦ DIỄM 1.3 BASIC OPERATION OF THE COMPUTER H o g t đ ộ n g cơ t ả n c ủ a m á ij tín h As previously indicated, the operation of the computer is controlled by the instructions of a program. The CPU fetches the individual instructions directly from memory before executing them; however, before executing the instructions, how does the computer know what each instruction means? The answer to this question is easy. The computer decodes each instruc tion according to a predefined format. The general format of an instruction may look like this: operator [operandl], [operand2], [operand3] where the operator indicates the type of action to be performed (ADD, SUBTRACT, MULTIPLY, etc.) and the operands are the “pieces” of infor mation on which the action indicated by the operator is going to be per formed. The square brackets around the operands indicate that the oper ands are optional. According to this general format, an instruction may have zero, one, two, or three operands. The reader should be aware that the computer only sees a sequence of 0’s and l ’s. It does not see an opera tor like “ADD” or “SUBTRACT”; instead it sees their predefined equivalent numerical code such as 10000001 for ADD or 10000110 for MULTIPLY. The format of a typical instruction may look something like this: ADDW3 locationl, location2, result This particular instruction adds the contents of the words at the ad dresses called locationl and location2 and stores the sum at the address called result. The “W” indicates that the operands are words whereas the suffix “3” indicates that there are three operands in this instruction. This instruction requires several steps to be carried out. First, the in struction is transferred from memory into the CPU. The location of the instruction currently being executed is kept in one of the CPU special registers called the in stru ction counter (IC) or program counter (PC)-the terminology varies with the manufacturer. The instruction just fetched is stored in another special register called the Instruction R egis ter (IR). The control unit decodes the instruction and recognizes it as an ADD operation with three word operands. Then, the first operand (locationl) and second operand (location2) are fetched into two general registers. These two registers are added and the result stored back into memory in the location called result. After the two operands have been fetched the pro gram counter is updated so it points to the next instruction to be executed During this process, two additional registers facilitate the communication between the CPU and main memory. These registers are the memory a d ­ 20 Chapter 1: Basic Concepts of Computers dress register (MAR) and the m em ory d a ta register (MDR). The MAR is used to hold the address of the location to or from which data are being transferred. The MDR contains the data to be w ritten into or read out of the addressed location. EXAMPLE 1.4 Assume that a computer has two instructions for addition with the following formats: ADDW2 locationl, location2 and ADDW3 locationl, location2, result. Does it make any difference to use one instruc tion over the other? To answer this question properly we need to understand the differences between these two instruction formats. The first ADD instruction contains two word operands. Hence, the name ADDW2. Let us assume th at in this type of instruction the result of the operation, as defined by the computer manufacturer, is stored into the second operand. This type of ADD opera tion is called a destructive add instruction since the value of location2 will be replaced by the result of the addition (see Fig. 1-6). Fig. 1-6 Destructive add. The second instruction contains three word operands, hence the name ADDW3. In this type of ADD instruction the result of the addition of the first two operands is stored into the location specified by th e third operand. This type of instruction is called a non-destructive add since the values of the operands rem ain intact after the instruction is ex ecuted (see Fig. 1-7). Chương 1 : Các khái niệm cơ bản về máy tính 21 Fig. 1-7 Non-destructive add. CHÚ THÍCH TỪ VƯNG__________________________________ ♦ instruction counter or program counter; bộ đếm chương trình ♦ Instruction Register : thanh ghi lệnh ♦ memory address register ; thanh ghi địa chỉ bộ nhớ ♦ memory data register : thanh ghi dữ liệu bộ nhá HƯỚNG DẪN ĐỌC Hiểu 1 .3 _____________________________ N hư đă học ở phần trước, phép toán của máy tính dược điều khiển bởi các lệnh của chương trình. CPU gọi các lệnh đơn một cách trực tiếp từ bộ nhớ trước khi thực thi nó; tuy nhiên, trước khi thực thi cău lệnh, làm sao máy tính có thể biết được ý nghĩa của mỗi câu lệnh ? Cáu trả lời thật đơn giản. Máy tính giải mã mỗi câu lệnh dựa trên các dạng thức được định nghĩa sẵn. Dạng của cău lệnh có thể giống như sau: toán tử [toán hạngl], [toán hạng2], [toán hạng3] ở đó các toán tử chi ra loại hành động dể thực hiện các phép tính (cộng, trừ, nhăn,....) và các toán hạng là một phần của thông tin của câu lệnh trên hành động được chỉ ra bởi toán tử để được thực hiện. Các dấu ngoặc vuông xung quanh các toán hạng chỉ ra các toán hạng này là tùy ý. Dựa trên dạng thức tổng quát này, một câu lệnh có thể có zero, một, hai, hoặc ba toán hạng. Người đọc lưu ý ràng máy tính chỉ hiểu được chuỗi 0 và 1. Nếu không hiểu một toán hạng chảng hạn như “ADD” hoặc “SU BTRACT”; thay vì nó chỉ hiểu các mã tương đương được định nghĩa sẵn chẳng hạn như 10000001 cho ADD (phép cộng) hoặc 10000110 cho M ULTIPLY (phép nhăn). 22 Chapter 1: Basic Concepts of Computers Dạng thức của một lệnh thông thường có thể như sau: ADDW3 loactionl, loaction.2, result Lệnh dặc biệt này cộng nội dung của các từ tại địa chỉ được gọi là location 1 và location 2 và lưu tổng này tại địa chi gọi là kẽt quà. Từ “W” chl ra các toán hạng là từ trong khi hậu tô “3” chl ra có ba toán tử trong cáu lệnh này. Câu lệnh này yêu cầu nhiều bước thực thi. Trước tiên, câu lệnh này được chuyển từ bộ nhớ vào CPU. VỊ trí của câu lệnh hiện đang được thực thi sẽ được giữ tại một trong những thanh ghi đặc biệt của CPU dược gọi là instruction counter (IC) (bộ đêm lệnh) hoặc pro gram counter (PC) (bộ đếm chương trình) - thuật ngữ này khác nhau tùy theo nhà sán xuất. Cáu lệnh vừa mới được gọi sẽ được lưu trữ tại một thanh ghi đặc biệt khác được gọi là Instruction Register (IR) (thanh ghi lệnh). Bộ điều khiển giải mã lệnh này và nhận ra nó là ADD (phép cộng) với ba toán tử. Sau đó, toán hạng đầu tiên (loaction 1) và toán hạng thứ hai là (location 2) sẽ được gọi vào hai thanh ghi tổng quát. Hai thanh ghi này dược cộng và kết quả được lưu trở lại bộ nhớ tại vị trí gọi là kết quả. Sau khi hai toán hạng này được gọi thì bộ đếm chương trinh được cập nhật để câu lệnh tiếp theo được thực thi. Trong suốt quá trình xử lý này, hai thanh ghi cộng này làm cho việc giao tiếp giữa CPU trở nên dễ dàng hơn. N hững thanh ghi nàv là thanh ghi địa chi có memory address register (MAR) (thanh ghi địa chi bộ nhớ) và memory data register (MDR) (thanh ghi bộ nhá dữ liệu). MAR dùng đề giữ địa chỉ của vùng xuất phát hoặc đi từ dữ liệu đang được vận chuyển. MDR có chứa dư 4liệu được viết vào hoặc đọc ra vị trí địa chi. V Í DỤ 4 Giả sử ràng máy tinh có hai lệnh để thực thi phép cộng với dạng thức sau: ADDW2 loactionl, location2 và ADDW3 loactionl location2, result. Có sự khác biệt nào sử dụng một trong các chỉ lênh này? Để trả lời câu hỏi này chính xác thì chúng ta cần phải hiểu sự khác biệt giữa hai cáu lệnh. Trước tiên cảu lệnh ADD có chứa hai toán hạng. Ợ đáy, tên là ABDW2. Chúng ta giả thiết ràng trong cău lệnh này kết quả của phép toán, được xác định bởi máy tính sẽ được lưu trữ trong toan hạng thứ hữi. Loại phép tính ÆDD (cộng) này được gọi là một phép tinh cộng tiêu cực bởi vì piá trị tại location2 được thay thế bằng kết quà của phép cộng (xem hình 1.6). Câu lệnh thứ hai có chứữ ba toán hạng, ỡ đây có tên là ADDW3 Trong loại cáu lệnh ADD này kêt quả của phép cộng giữa hai toán tứ sẽ được lưu trữ trong vị trí được chỉ định ở toán hạng thứ ba. Loại cáu lệnh này được gọi là non destructive add. (cộng không phá hủy cáu V. Chương 1: Các khái niệm cơ bản về máy tính 23 trúc) bởi vì các giá trị của các toán hạng vẫn được giữ nguyên sau khi lệnh này được thực thi (xem hình 1.7) Hình 1.7 Cộng tích cực 24 Chapter 1: Basic Concepts of Computers CHỦ DIEM 1.4 REPRESENTATION OF DATA IN MEMORY Kiểu trinli bàij dữ liệu trong DỘ nnó If we could look at the content of the memory of a computer we would find that all types of data and instructions are represented using only 0 s and l ’s. Therefore, an obvious question is how can the computer tell the type of information that is stored on a particular location? The answ er is simple; the computer knows the type of data stored in a particular loca tion from the context in which the data are being used. This allows the computer to interpret it properly. Example 1.5 shows th a t a string of data may have different interpretations. EXAMPLE 1.5 Given the sequence of 4 bytes shown below, w hat would be the values of this sequence if we consider it as being formed by (a) four individual bytes? (b) two-word integers with two bytes per word? (c) a longword integer with four bytes per longword? 01100011 01100101 01000100 01000000 —f ---------------- increasing addresses The value of each individual byte can be calculated using the procedure indicated in Section 1.1.1. The subscript indicated in parenthesis at the right-hand corner of a number indicates if the number is binary (2 or deci mal (10. This number, as we will see later, is called the base or radix of the number. (a) Considering the bytes from right to left, we have 01000000(2 = o w o w o ‘o° = (1*24) = 64,,„ 01000100(2 = O W O V l W - (1*2®) + (1*22) = 64 + 4 = 68, 01100101,2 = 0’1‘l W W l " = (1*26) + (1*25) + (1*22) + (1*2°) = 64 + 32 + 4 + 1 = 101„„ 01100011,i = 071‘ 1!0403021'1° = (1*26) + (1*25) + (1*2') + (1*2°) = 64 + 32 + 2 + 1 = 99, (b) The first two-byte word consists of the two rightm ost bytes; using the procedure of Section 1.1.1 we have that oioooioooioooooo,; = o,5i“o1}o12o'TWoWoWo'o0 = (t* 2 ,4) + (l*2'°) + (l* 2 6) = 17.472, The next two-byte word is 0110001101100101. Using the procedure 0f Section 1.2.1, we have that Chương 1: Các khái niệm cơ bản về máy tính 25 0110001101100101(2 = O, , l ,4l n 0 'J0 u 0 ,or i 807l 6l 50‘'ơ 'l 20 'l o = (1*214) + (1*2'J) + (1*2?) + (1*2“) + (l*2fi) + (1*25) + (1*22) + (1*2“) = 24,445 (c) Using the procedure of Section 1.2.1 to calculate the value of the longword consisting of four bytes we have that 0311301290280270261251240231221;i020ũ 19118ũ 171160 t51H0 130 120 ll110090807160 5ơ l(y>020 .00(2 = (1'2X) + (1*2 ) + (1*2 ) + (1*224) + (1*2 ) + (1*221) + (1*2 ) + (1*2“) + (1*214) + (1 *2'°) + (1*26) = 1,667,580,992(10 1.4.1 Number Systems and Codes - Hệ thống số và mã The most commonly used numbering system is the decimal system. However, due to the binary nature of its electronic devices, the use of the decimal system by the computer is limited. Most of the data representation and arithmetic operations are carried out in the binary system or some of its “shorthand” notation such as the octal or hexadecimal systems. How ever, before considering the binary, octal, or hexadecimal systems, let us review some of the characteristics of the decimal system. The decimal system, as its name indicates, is based on the number 10. The number 10 itself is called the basis or radix of the system. In any numerical system, the basis tells us how many different symbols there are in the system. In the decimal system these symbols are called digits. They are the familiar 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Notice that they range in value from 0 to 9. This is a particular case of a more general rule that can be stated as follows: “Given any positive integer basis or radix N, there are N different indi vidual symbols that can be used to write numbers in the system. The value of these symbols ranges from 0 to N - 1:’ In addition to the binary system, the computer and telecommunication fields make extensive use of some other numerical systems. They are the octal (its basis is 8) and the hexadecimal (its basis is 16) systems. Example 1.6 explains the basic elements of these systems. EXAMPLE 1.6 How many different synrbols are there in the octal and hexadecimal systems? What are the ranges of these symbols? The basis of the octal system is 8. That is, N = 8. Therefore, there are 8 different symbols. The range of these values varies from 0 to (8 - 1). That is, from 0 to 7. These symbols are: 0, 1, 2, 3, 4, 5, 6, and 7. We call all of these symbols by their decimal names: one, two, three, and so on. The basis of the hexadecimal system is 16. That is, N = 16. Therefore there are 16 different symbols. The values of these symbols range from 0 26 Chapter 1: Basic Concepts of Computers to (16 -1) or from 0 to 15. These symbols are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. Notice that after 9, the symbols are the letters A through F. In this system, the letter A stands for 10, the B for 11, the C for 12, the D for 13, the E for 14, and the F for 15. The reason for choosing letters instead of combination of numerical symbols to represent symbols higher than 9 is to keep all symbols single characters. To indicate the basis on which a given number is w ritten, we will use a subscript at the lower right side of the number. As indicated in Section 1.4, the notation 0101|2 indicates that the number is binary. Likewise, the notation 01256(8 will indicate that the number is w ritten in base 8. When referring to numbers of the decimal system, the subscript is generally omitted. However, we will use it whenever it is necessary to clarify the text. Although the word digit generally refers to the individual symbols of the decimal system, it is also common to call the individual symbols of the other numerical systems by this name. 1.4.2 Positional Systems - Vj tri trong cac h$ All the numerical systems that we have considered so far, including the decimal system, are p ositional systems. That is, the value represented by a symbol in the numerical representation of a number depends on its posi tion in the number. For example, in the decimal system, the 4 in the number 478 represents 400 units; the 4 in the number 547 represents 40 units. This fact can be seen more clearly if we decompose the number as follows: 478 = 400 + 70 + 8 547 = 500 + 40 + 7 In any positional system, the value of any digit in the representation of a number can be calculated using the following steps: (1) Number the digits from right to left using superscripts. Begin with zero, as the superscript of the rightmost digit, and increase the superscripts by 1 as you move from left to right. (2) Use each superscript to form a power of the basis. (3) Multiply the digit s own value, in decimal, by its corresponding power of the basis. To calculate the decimal equivalent of the entire number, sum all the products obtained in step 2. EXAMPLE 1.7 W hat is the value of each digit in the number 1228,..? The basis is 10 since the number is a decimal number. To calculate the value of each digit follow the steps indicated below. (1) Number the digits using superscripts. Begin with 0 in the rightni0S(- Chiidng 1: Cac khai ni$m CO ban ve may tinh 27 position and increase the superscripts as you move from right to left. The number should look like this: 13222‘8° (2-3) Use the superscripts to form powers of the basis and multiply the digit’s own value, in decimal, by its corresponding power: The value of 1 in 1228 is equal to 1*103 = 1*1000 = 1000. The value of the first 2 (from left to right) in 1228 is equal to 2*102= 2*100 = 200 The value of the second 2 (from left to right) in 1228 is equal to 2*10' = 2*10 = 20 The value of 8 in 1228 is equal to 8*10° = 8*1 = 8. EXAMPLE 1.8 What is the value of each digit in the number 1253(g?What is the decimal equivalent of the number? The basis is 8 since the number is written in the octal system. Using a procedure sim ilar to the one in the previous example, we can use super scripts and write the number as 13225'3°. Using these superscripts as the power of the basis we have: The value of 1 in 1253 is equal to 1*83 = 1*512 = 512 The value of 2 in 1253 is equal to 2*82 = 2*64 = 128 The value of 5 in 1253 is equal to 5*8' = 5*8 = 40 The value of 3 in 1253 is equal to 3*8° = 3*1 = 3 The decimal equivalent of the number is obtained by adding all the previous products. 1253,8 ': * 8 5) + (2*82) + (5 * 8 ') + (3*8°) = (1 * 5 1 2 )+ (2*64) + ( 5 * 8 ) + ( 3 * 1 ) = 512 + 128 + 40 + 3 = 683 Notice that whenever we find the decimal equivalent of number, we also determine the individual value of each digit. We will use ¿his combined method from now on. EXAMPLE 1.9 What is the value of each digit in the number lA iF (16?What is the decimal equivalent of the number? The basis is 16 since the number is written in the hexadecimal system. Using superscripts we can write the number as 13A25'F°. To calculate the 28 Chapter 1: Basic Concepts of Computers decimal equivalent of this hexadecimal number, substitute the symbols A and F by their respective decimal equivalents of 10 and 15. The decimal equivalent of the number is obtained by adding all the previous powers. 1 A 5 F (16 = (1*163) + (10*162) + (5 * 1 6 ') + (15*16°) = (1*4096) + (1 0 * 2 5 6 )+ (5*16) + (1 5 * 1 ) = 4096 + 2560 + 8 0 + 15 = 6751 The value of 1 in 1A5F is equal to 1*163 = 1*4096 = 4096 The value of A in 1A5F is equal to 10*162 = 2*256 = 25 60 The value of 5 in 1A5F is equal to 5*16' = 5*8 = 80 The value of F in 1A5F is equal to 15*16° = 3*1 = 15 CHÚ THÍCH TỪ VỰNG. ♦ interpretations : sự giải mã ♦ positional systems : vị trí trong các hệ ♦ binary system : hệ nhị phân string of data : chuỗi dữ liệu HƯỚNG DẦN ĐỌC Hiểu CHỦ ĐIEM 1.4 Nếu chúng ta nhìn vào nội dung bộ nhớ của một máy tính thi chúng ta sẽ biết rằng tất cả các loại dữ liệu và các loại lệnh sẽ được mô tả dưới dạng 0 và 1. Vì vậy, một câu hỏi hiển nhiên là làm cách nào máy tính hiểu được loại thông tin dược lưu trữ trong vị trí đặc biệt này? Câu trả lời rất đơn giản, máy tính biết dược loại dữ liệu được lưu trữ trong vùng đặc biệt này dựa theo nội dung mà dữ liệu đang được dùng. Điều này cho phép máy tính giải mã nó một cách chính xác. Ví dụ 1.5 minh họa chuôi dừ liệu có thê có nhiều cách giải mã khác nhau. Ví dụ 1.5 Cho một chuỗi dữ liệu 4 byte được m inh họa dưới đáy giá tri của chuôi này là băng bao nhiêu nêu chúng ta xem nó ở các dạng (a) bôn byte riêng biệtĩ (b) hai từ nguyên với hai byte trên một từ? (c) một sô nguyên longword (từ dài) với bốn byte trên longword đó? 01100011 01100101 01000100 01000000 Các đ ịa chì tă n g dẫn Chương 1: Các khái niệm cơ bản về máy tính 29 Giá trị của mỗi byte có thể được tính toán bằng cách sử dụng phương pháp được hướng dẫn trong phần 1.1.1. Số mũ được chỉ trong dâu ngoặc đơn ở góc phải dưới của con sô chỉ ra ràng số đó có phải là sô nhị phản a hoặc sô thập phân a0. Con sô này chúng ta sẽ xem ở chương sau, được gọi là số cơ sở hoặc cơ số của một số. (a) Xét các byte từ phải sang trái, chúng ta có 01000000., = o w o w o ' o 0 = (1*2*; = 64, ,0 0 1 0 0 0 1 0 0 , 2 = o w o w o ' o ” = (1 *2 ) + (1*2 ) = 64 + 4 = 68,,0 01100101(2 = O V l W W l ” = (1*2‘) + (1*2!) + (1*22) + (1*2°) = 64 + 32 + 4 + 1 = 101„„ 01100011., = O W O W l 'l 0 = (l*26) + (l*2i) + (l*2') + (l*2°) = 64 + 32 + 2 + 1 = 99, (b) Từ hai byte đầu tiên có chứa hai byte ở bên phải nhất; bằng các sử dụng phương pháp ở phần 1.1.1, chúng ta có 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ., = o '5i 14o,3o ,2o " i ,w o 7i 6o w o 2o'o 0 = (1*2M) + (1*2'°) + (1*26) = ì 7.472,,0 Từ hai byte kế tiếp là 0110001101100101. Bàng cách sử dụng phương pháp ở phần 1.2.1, chúng ta có 0110001101100101(2 = 0 I51M11S0 ,20 'I0'°1, 1I'07161 W 1 20'10 = (1*2“*) + (1*2'3) + (1*29) + (1*2*) + (1*26) + (1*25) + (1*22) + (1*2°) = 24,445 (c) Bằng cách sử dụng phương pháp ở phần 1.2.2 dể tính giá trị của của số longivord có chứa bốn byte, ta có o31i 3° i2,oMo27o26i 25i 2',o23i 22i J1o20oI,i ieo ', i '‘o,5i ,4oi:,o '2o 11i loo9o8o7i <,o5o4o3o2o 1o0 (2 = (1*2W) + (1*2 ) + (1*2“ ) + (1*224) + (1*222) + (1*221) + (l* 2 's) + (1*2“ ) + (1«2U) + (1*2'°) + (1*26) = 1,667,580,992(10 1.4.1 Các hệ s ố và m ã số Hệ số thường dùng nhất là hệ thập phân. Tuy nhiên, dựa vào trạng thái nhị phân của các thiết bị điện tử, thì cách sứ dụng hệ thập phân bàng máy tính là hạn chế. Hầu hết dữ liệu được trình bày và các phép tính số học được xử lý theo hệ nhị phân hoặc một số ký hiệu tính toán của nó chẳng hạn như hệ tám (bát phân) hoặc hệ mười sáu (thập lục phân) . Tuy nhiên, trước khi xem xét các hệ nhị phăn, hệ bát phản và hệ thập lục phân, chúng ta hãy xem lại các số trong hệ thập phân. Hệ thập phân, như tên nó chỉ ra là dựa trên số 10. S ố 10 này được gọi là hệ ca sở hoặc cơ số. Trong bất kỳ hệ số nào, cơ sở này cho chúng ta biết có bao nhiêu ký tự khác nhau trong một hệ. Trong hệ thập phân 30 Chapter 1: Basic Concepts of Computers những ký hiệu này dược gọi là số. Chúng là 0, 1, 2, 3, 4, 5, 6, 7, 8 và 9. Lưu ý rằng chúng nằm trong dãy giá trị từ 0 đến 9. Đáy là một trường hợp phổ biến của nguyên tắc chung có thể được phát biểu như sau: “Cho bất kỳ s ố nguyên dương nào có cơ s ố N, với N là các ký tự ph ân biệt khác nhau mà có th ể được dù n g d ể viết các số trong hệ thống này. Giá trị của các ký tự n ày nằm trong khoảng từ 0 cho đến N -l Ngoài hệ nhị phân, máy tính và các lĩnh vực viễn thông đểu sử dụng các hệ số khác. Chúng là hệ bát phân (ca số 8) và hệ thập lục phán (cơ số 16). Ví dụ 1.6 sẽ giải thích các thành phần ca bản của hệ này. Ví dụ 1.6 Có bao nhiêu ký tự khác nhau trong hệ bát phản và hệ thập lục phăn? Dãy của lý tự này là bao nhiêu? Cơ số của hệ bát phân là 8. Nghĩa là N = 8. Do đó, có 8 ký tự khác nhau. Dãy của ký tự này biến thiên từ 0 đến (8-1). Nghĩa là tử 0 cho đến 7. Những ký tự này là : 0, 1, 2, 3, 4, 5, 6, và 7. Chúng ta gọi những ký tự này theo tên thập phân: một, hai, ba .... Ca số của hệ thập lục phân là 16. Nghĩa là N = 16. Vì vậy, có 16 ký tự khác nhau. Các giá trị của dãy ký tự này là từ 0 đến (16 - 1) hoặc từ 0 cho đến 15. Những ký tự này là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, c , D. E và F. Lưu ý rằng sau số 9, các ký tự bát đầu từ mẫu tự A cho đến F. Trong hệ này, mẫu tự A đại diện cho số 10, B cho 11, c cho 12, D cho 13, E cho 14 và F cho 15. Lý do chọn các ký tự thay vì kết hợp các số ký tự để diễn tả các số lớn hơn 9 sẽ là cúc ký tự đơn. Để mô tả cơ số của một số đã cho , chúng ta sử dụng số mủ ở góc phải dưới bên cạnh số đó. N hư được chi định trong phần 1.4 ký hieu 0101 chỉ ra ràng số đó là hệ nhị phân. Tưang tự như vậy, ký hiệu 01256 sẽ chi ra số dó được viết theo ca số 8. Khi chuyển đến hệ thập phán các số mũ thường không hiển thị. Tuy nhiên, chúng ta sẽ sử dụng no nếu cần đề làm cho text được dễ hiểu. Mặc dù, chữ số từ thường được tham chiếu đến các ký hiệu riêng biệt của hệ thập phân. Các hệ thống số khác cũng thường gọi tên này. 1.4.2 Vị tr í tron g các hệ Tât ca cạc hệ sô mà chúng ta xem xét kể cả hệ thập phản là vị trí các hệ Đó là ký hiệu mô tả giá trị trong một con số dựa trên vị trí của nó trong số đó. Ví dụ, trong hệ thập phân, số 4 trong số 478 đại diện cho 400 dim vị; sô 4 trong sô 547 đại diện cho 40 đơn vị. Cơ sở này sẽ được hiểu rõ hcm nếu chúng ta phàn tích con sô này như sau: 478 = 400 + 70 = 8 547 = 500 + 40 = 7 Chương 1: Các khái niệm cơ bản về máy tính 31 Trong bất kỳ hệ nào, giá trị của một sô trong một số mô tả có thể được tính toán bằng cách sử dụng các bước sau: (1) Đánh số mũ cho các sô từ phải sang trái. Bát đầu là số 0 cho số phải nhất, và tăng lên 1 khi bạn di chuyển qua trái. (2) Sử dụng mỗi sô mũ dưới dạng sô mủ của cơ số đó. (3) Nhăn giá trị của số nà với sô mũ của ca sổ tương ứng trong hệ thập phân. Để tính toán ra số thập phân tương ứng, hãy cộng toàn bộ các kết quả vừa tính dược ở bước 2. V í d ụ 1.7 Giá trị của mỗi con số trong sô 1228nolà bao nhiêu? Cơ số này là 10 bởi vì đây là số thập phán. Để tính giá trị của mỗi con số hãy theo các bước chi dẫn sau: (1) Đánh số phía trên cho các số. Bắt đầu từ 0 ở vị trí phải nhất và tăng lên một khi di chuyển qua trái. Số này sẽ trông giống như sau: 13222'8° (2-3) Sử dụng các sô trên là lũy thừa của cơ sô rồi nhân giá trị của nó cho số mũ tương ứng trong hệ thập phân: Giá trị cửa 1 trog 1228 là bàng 1*103 = 1*1000 = 1000. Giá trị của 2 trước (tính từ trái sang phải ) trong 1228 là bàng 2*102= 2*100 = 200 Giá trị của sô 2 thứ hai (tính từ trái sang phải) trong 1228 là bàng 2* 10' = 2*10 = 20 Giá trị của 8 trong 1228 là bằng 8*100 = 8*1= 8. V í dụ 1.8 Giá trị của mỗi con số trong số 1253(s là bằng bao nhiêu? Hãy tính giá trị thập phân tương ứng của số này? Ca số là 8 do đó sô này sẽ được viết theo hệ bát phân. Sử dụng phương pháp tương tự ở ví dụ trên, chúng ta có thể sử dụng các số trên và viết số thứ tự là 13225'3°. Sử dụng những số này dưới dạng là số mũ của cơ sô, chúng ta được: Giá trị của 1 trong 1253 là bằng 1*83 = 1*512 = 512 Giá trị của 2 trong 1253 là bàng 2*82 = 2*64 = 128 Giá trị của 5 trong 1253 là bàng 5*8‘ = 5*8 = 40 Giá trị của 3 trong 1253 là bằng 3*80 = 3*1 = 3 Giá trị thập phân tương ứng của số được tính bàng cách cộng tất cả các tích lại. 32 Chapter 1: Basic Concepts of Computers 1253,8 = (1*83) + (2*82) + (5 * 8 ') + (3*8") = (1 * 5 1 2 )+ (2 * 6 4 ) + ( 5 * 8 ) + ( 3 * 1 ) = 512 + 128 + 40 + 3 = 683 Lưu ý rằng bất khi khi nào chúng ta tìm dược giá trị thập phản tương dương, thì chúng ta cũng xác định được các giá trị cho môi sô. Chúng ta sẽ sử dụng phương pháp kết hợp này kể từ bây giờ. Ví dụ 1.9 Giá trị cùa mỗi con số trong sô 1AFỊW là bằng bao nhiêu? Giá trị thập phăn tương đương của sô này là bàng bao nhiêu? Ca số này là 16 ui vậy sô' sẽ được viết theo dạng hệ thập lục phân. Bằng cách sử dụng các số ở trên chúng ta có thể viết số thứ tự là 13A 25'F°. Để tinh giá trị thập phân tương ủng cho số thập lục phán này, hãy thay các ký tự A và F bàng các giá trị thập phản tương ứng là 10 và 15. Giá trị thập phán tương ứng của số được tính bàng cách cộng tất có các lũy thứa lại với nhau. 1 A 5 F „6 = (1*163) + (10*162) + (5 * 1 6 ') + (15*16°) = (1 * 4 0 9 6 )+ (1 0 * 2 5 6 )+ (5 * 1 6 )+ (15*1) = 4096 + 2560 + 8 0 + 15 = 6751 Giá trị của 1 trong 1A5F là 1*163 = 1*4096 = 4096 Giá trị cửa A trong 1A5F là 10*162 = 2*256 = 2560 Giá trị cửa 5 trong 1A5F là 5*16' = 5*8 = 80 Giá trị của F trong 1A5F là 15*16° =3*1 - 15 Chương 1: Các khái niệm cơ bản về máy tinh 33 CHỦ DIỄM 1.5 CONVERSION BETWEEN THE BINARY, OCTAL, AND HEXADECIMAL SYSTEMS C h u i j e n đ ể i g iữ a c á c h ê n h ị p liâ n , t á t p h â n v à t h q p lụ c p h â n Table 1-3 shows the representation of the first fifteen decimal numbers in the binary, octal, and hexadecimal systems. Notice that each unique binary sequence is equivalent to one and only one symbol in each of these systems. We can use this equivalence between the binary, octal, and hexa decimal systems as a shorthand notation to convert values between any of these bases. Table 1-3 Binary, Octal, Hexadecimal, and Decimal Equivalents. Binary Octal Hexadecimal Decimal 0001 1 1 1 0010 2 2 2 0011 3 3 3 0100 4 4 4 0101 5 5 5 0110 6 6 6 0111 7 7 7 1000 10 8 8 1001 11 9 9 1010 12 A 10 1011 13 B 11 1100 14 c 12 1101 15 D 13 1110 16 E 14 1111 17 F 15 1.5.1 Conversion from Hexadecimal to Binary and Vice Versa Given a hexadecimal number, we can find its binary equivalent by re placing each hexadecimal symbol by its corresponding binary configura tion (see Table 1-3). 34 Chapter 1: Basic Concepts o f C o m p u te rs EXAMPLE 1.10 What is the binary equivalent of the hexadecimal number AF3B1? Replacing each hexadecimal symbol by its corresponding binary sequence (see Table 1-3) we obtain A F 3 B 1 1010 1111 0011 1011 0001 Notice that to facilitate the reading of the resulting binary number we have separated it into four-bit groups. To convert binary numbers to their hexadecimal equivalents, we can follow a two-step procedure that is almost the reverse of the previous pro cess. Step 1. Form four-bit groups beginning from the rightm ost bit of the binary number. If the last group (at the leftmost position) has less than four bits, add extra zeros to the left of the bits in this group to make it a four-bit group. Step 2. Replace each four-bit group by its hexadecimal equivalent (see Table 1-3). EXAMPLE 1.11 What is the hexadecimal equivalent of the binary number shown below? 0110011110101010100111 Step 1. Forming four-bit groups beginning from the rightm ost bit we have 01 1001 1110 1010 1010 0111 Since the last group (the leftmost) has only two bits, it is necessary to add two extra zero bits to the left of these bits to make it a four-bit group. The number should look like this: 0001 1001 1110 1010 1010 0111 Step 2. Replacing each group by its hexadecimal equivalent (see Table 1-3) we obtain 19EAA7(]6 1.5.2 Converting Decimal to Other Bases The conversion of a given decimal number to another integer basis r (r > 0) is carried out by initially dividing the number by r, and then succes sively dividing the quotients by r until a zero quotient is obtained. The Chương 1: Các khái niệm cơ bản vể máy tính 35 decimal equivalent is obtained by writing the remainders of the successive divisions in the opposite order to that in which they were obtained. Ex ample 1.12 illustrates this method. EXAMPLE 1.12 What is the binary equivalent of decimal 41? Since we want to convert decimal 41 to binary, we need to divide by the binary basis, that is, r = 2. The initial number (41) is divided by 2 to obtain a quotient of 20 and a remainder of 1. The previous quotient of 20 is then divided by 2; this gives us a quotient of 10 and a remainder of 0. This new quotient of 10 is again divided by 2 to obtain 5 as the quotient and 0 as the remainder. The quotient of 5 is now divided by 2 to obtain a quotient of 2 and a remainder of 1. The new quotient is again divided by 2 to obtain a new quotient of 1 and a remainder of 0. This last quotient of 1 is divided by 2 again to obtain a quotient of 0 and a remainder of 1. Since we obtained a zero quotient the process stops. To form the binary number we write the remainders in the opposite order to that in which they were obtained, beginning with the last remainder. This process is shown below. N u m b er Q u o tie n t W hen D ividing by 2 R em ain d er 41 20 1 20 10 0 10 5 0 5 2 1 2 1 0 1 0 1 The binary equivalent of decimal 41 is 101001. That is, 41(]0 = 101001(2. We can verify this result by converting 101101 to its decimal equivalent according to the procedure of Section 1.4. l W lW l0 = (1*2!) + (0*24) + (1*23) + (0*22) + (0*2') + (1*2°) = 32 + 0 + 8 + 0 + 0 + 1 = 41 EXAMPLE 1.13 W hat is the octal representation of decimal 41? In this case we want to convert a decimal value to octal. Therefore, we need to divide by the octal basis, that is, by 8. Using the abbreviated method of the previous example we have that 36 Chapter 1: Basic Concepts of Computers N u m b er Q u o tie n t W hen R e m a in d e r D ividing by 8 t 41 5 1 5 0 5 Therefore, 41(10 = 51(8. We can verify this result by noting that 51(S = (5*8') + ( 1*8°) = ( 4 0 ) + (1) — 41(10 HƯỚNG DẪN ĐỌC HIEU CHỦ ĐIEM 1.5 ___________________ Bảng 1.3 minh họa kết quả của mười lăm số thập phân theo dạng nhị phân, bát phản và thập lục phân. Lưu ý ràng mỗi chuỗi nhị phân duy nhất tương ứng vái một và chỉ một giá trị trong hệ khác. Chúng ta có thể sử dụng bảng tương đương giữa các hệ nhị phản, bát phản và thập lục phân như là một bảng sổ tay để chuyển các giá trị giữa bất kỳ cơ sô nào. Bảng 1.3 Các giá trị tương đương giữa hệ nhị phăn, bát phân, thập lục phân và thập phân. N h ị p h ả n B á t p h â n T h ậ p lụ c p h ả n T h ậ p p h à n 0001 1 1 1 0010 2 2 2 0011 3 3 3 0100 4 4 4 0101 5 5 5 0110 6 6 6 0111 7 7 7 1000 10 8 8 1001 11 9 9 1010 13 A 10 1011 14 B 11 1100 14 c 12 1101 15 D 13 1110 16 E 14 1111 17 F 15 Chương 1: Các khái niệm cơ bản vé máy tính 37 1.5.1 Chuyển từ hệ th ập lục phán sang nhị ph án và ngược lại Cho một số thập lục phản, chúng ta có thể tìm được giá trị nhị phân tương ứng bằng cách thay thế mỗi ký tự thập lục phân bàng sô nhị phân tương ứng của nó (xem bảng 1.3). V Í D Ụ 1.10 Số nhị phân tương ứng của số thập lục phản AF3B1 là bao nhiêu? Thay mỗi ký tự thập lục phăn bằng một chuỗi nhị phán tương ứng (xem bảng 1.3), chúng ta được A F 3 B 1 1010 1111 0011 1011 0001 Lưu ý rằng đ ể dễ dọc kết quả của số nhị phân chúng ta nên chia nó theo dạng các nhóm 4 bit. Để chuyển các số nhị phân sang số thập lục phân tương ứng, chúng ta có thể thực hiện theo hai thủ tục như sau ngược lại với tiến trình trước. Bước 1. Từ nhóm 4 bít bất đầu bên phải bit dài nhất của số nhị phăn. Nếu nhóm cuối (nằm ở vị trí trái nhất) có ít hơn bốn bit, hãy thêm các bit zéro vào ở bên trái của các bit trong nhóm này đ ể tạo thành nhóm 4 bit. Bước 2. Thay mỗi nhóm bốn bit này bằng giá trị thập lục phân tương ứng (xem bảng 1.3). VI D Ụ 1.11 Giá trị thập lục phân tương ứng của sô nhị phân được trình bày dưới đăy là bao nhiẽu? 0110011110101010100111 Bước 1. Gom nhóm bôn-bit bắt đầu từ bit phải nhất chúng ta có 01 1001 1110 1010 1010 0111 Bởi vì nhóm, cuối (nhóm trái nhất) chỉ có hai bit, nó cần phải thêm hai bit zéro vào bẽn trái để tạo thành nhóm bốn bit. Sô' này sẽ trông giống như dưới đây: 0001 1001 1110 1010 1010 0111 Bước 2. Thay thế mỗi nhóm này bàng giá trị thập lục phân tương ứng (xem bảng 1.3) ta tính được 19EAA7as 1.5.2 Chuyển hệ th ập phán sang các cơ số khác Chuyển đổi một số thập phân đã cho sang cơ số r (r > 0) được tính bằng cách lấy số ban đầu chia cho r và sau đó lấy thương số chia tiếp 38 Chapter 1: Basic Concepts of Computers cho r cho đến khi nào số thương là zéro. Số thập phán tương đương dược tính bàng cách viết các số dư của phép chia theo chiều ngược lại. Ví dụ 1.12 minh hoạ phương pháp này. VÍ D Ụ 1.12 Sô' nhị phân tương ứng của số thập phần 41 là bao nhiêu'? Bởi vi chúng ta muốn chuyển số thập phán 41 sang nhị phân, thi ta cẩn phải chia cho ca số nhị phân, nghĩa là r = 2. Sô ban đầu (41) được chia cho 2 sẽ tính ra thương bàng 20 và số dư là bằng 1. Lấy số thương của 20 chia cho 2; chúng ta sẽ được số thương là 10 và số dư là 0. Lấy số thương mới này là 10 chia lại cho 2 và được kết quả là 5 và số dư là 0. Bây giờ lấy số thương 5 này chia cho 2 để được số thương bàng 2 và số còn dư là 1. Lấy số thương mới này lại chia cho 2 ta được kết quả sô thương bằng 1 và số dư bằng 0. Lấy sô thương cuối cùng là 1 chia cho 2 ta được kết quả số thương bằng 0 và phần dư bằng 1. Bởi ui chúng ta tính được số thương bằng zéro do đó quá trình thực thi này dừng lại. Để biểu diễn số nhị phán chúng ta viết các sô dư theo chiều ngược lại mà chúng ta tính toán bát đầu từ số dư cuối cùng. Tiến trình này được minh họa dưới đây. SỐ S ô th ư ư n g k h i c h ia ch ó 2 P h ẩ n d ư 41 20 1 20 10 0 10 5 0 5 2 1 2 1 0 1 0 1 Số nhị phẫn tương ứng của thăp phân 41 là 101001. Nghĩa là 41 = 101001l2. "° Chúng ta có thể kiểm chứng kết quả này bàng cách chuyển 101101 sang dạng thập phân tương ứng dựa theo cách tính toán ở phần 1.4. 150 W 0 T = (1*25) + (0*2*) + (1*25) + (0*22) + (0*2') + (1*2°) = 32 + 0 + 8 + 0 + 0 + 1 = 41 V I DỤ 1.13 Sô bát phân cùa số thập phăn 41 là bao nhiêu? Trong trường hạp này chúng ta muốn chuyển giá trị thập phán sang bát phân. Do dó, chúng cần chia theo ca sô bát phán, đó là 8. Sử Chương 1: Các khái niệm cơ bản vế máy tính 39 dụng phương pháp tắt của của ví dụ trước chúng ta được S ố T h ư ơ n g k h i c h ia P h á n d ư c h o 8 t 41 5 1 5 0 5 41 5 1 5 0 5 Do dó 41ao = 51 (g. Chúng ta có thể kiểm chứng lại kết quả này bằng cách 51,8 = (5 * 8 ')+ ( 1*8°) = (40) + ( l) ; 41(10 40 Chapter 1: Basic Concepts o f C o m p u te rs CHỦ DIEM 1.6 RULES FOR FORMING NUMBERS IN ANY SYSTEM C á c q u ij td c t iể u d iễ n các s ố tr o n g b a t cứ k ệ n à o Table 1-3 shows the equivalent of some numbers in binary, octal, and hexadecimal. In any of these systems, how do we form consecutive num bers higher than that represented by their largest individual symbol? In the decimal system, with a single digit, the largest number th a t we can form is nine. To represent numbers exceeding nine we use more than one digit as indicated below: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 .. . 90 91 92 93 94 95 % 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 . After writing all single digits, we form all two-digit combinations begin ning with 1. Then we form all two-digit combinations beginning with 2 and so on until we reach 99. After exhausting all two-digit combinations we start forming three-digit combinations; then we continue w ith all four-digits combinations and so on. This process can be continued forever. A similar procedure can be applied to other numerical systems. To form numbers higher than 7 in the octal system we use a sim ilar formation rule as shown in Table 1-3. EXAMPLE 1.14 In the hexadecimal system, how are the numbers greater than F formed? 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17 18 19 1A IB 1C ID IE IF 20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F . . . F0 FI F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF 100 101 ... and so on. Notice that, after writing all the single digits (shown in italics), it is necessary to form all possible two-digit combinations of the single digits, beginning with 1. Once this sequence has been exhausted, the two-digit combinations beginning with 2 are formed. This process is repeated until all two-digit combinations beginning with F are completed. At this mo ment, it is necessary to form all three-digit combinations, beginning with 100 and ending with FFF. The process is then repeated for all four-digit combinations and so on. Chương 1: Các khái niệm cơ bản vé máy tính 4J HƯỚNG DẪN ĐỌC Hiểu CHỦ ĐIEM 1.6 __________________ Bảng 1.3 trình bày giá trị tương dương của các sổ trong hệ nhị phân, bát phản và thập lục phân. Trong bất kỳ hệ này, cách nào chúng ta hiển thị trình bày các sô liên tục theo thứ tự sô này cao hơn số trước bằng cách nào? Trong hệ thập phân với số đơn, số lán nhất mà chúng ta biểu diễn là chín. ‘Để mô tả các sô lớn hơn chín chúng ta sử dụng nhiều số như dược minh họa dưới đây: ũ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 Sau khi viết tất cả các số dơn, chúng ta trình bày thành hai số kết hạp bắt đấu bàng 1. Sau đó chúng ta bắt đầu kết hạp hai số bằng 2 và ... cho đến 99. Sau khi đến cuối hai chữ số chúng ta bát đầu biểu diễn bằng ba số kết hợp. Sau dó chúng ta tiếp tục bằng đầu bằng bốn số kết hợp v à ..... Tiến trình này có thể được tiếp tục không dừng. Một tiến trình tương tự củng có thể áp dụng cho các hệ sô khác. Để trình bày các sô lớn han 7 trong hệ bát phân chúng ta sử dụng quy tắc tương tự như được rình bày ở bảng 1.3. VI D Ụ 1.14 Trong hệ thập lục phân, cách nào để biểu diễn các số lớn hơn F? 0 1 2 3 4 Ị 6 7 8 9 A B c D E F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E ư 20 21 22 23 24 25 lí, V 28 29 2A 2B 2C 2D 2E 2F 30 31 32 33 34 35 36 37 38 39 3A JB 3C 3D 3E 3F ... PO F1 F2 F3 F4 F5 F6 F7 F8 FV FA FB FC FD FE FF 100 101 . Lưu ỷ rằng, sau khi viết tất cả các sô đơn ra (xem các ký tự in nghiêng), nếu cần chúng ta có thể biểu diễn bằng hai số kết hợp, bắt dầu bằng 1. Khi chuỗi này kết thúc, hai số kết hợp sẽ bắt đầu bàng 2. Tiến trình này sẽ lặp lại cho đến khi nào hai sô' kết hạp bắt dầu là F. Ngay lúc này, chúng ta sẽ biểu diễn thành ba số kết hợp, bắt đầu là 100 và kết thúc là FFF. Tiến trình này lặp lại cho bốn sổ kết hợp và v,v. 42 Chapter 1: Basic Concepts of C o m p u te rs CHỦĐIỂM 1.7 ARITHMETIC OPERATIONS IN THE BINARY, OCTAL, AND HEXADECIMAL SYSTEMS C á c phép toán số học trona các kệ nhị phân, Lát phân và tỉìộp íục phân Arithmetic operations on the binary, octal, and hexadecimal systems follow similar rules to that of the decimal system. To facilitate the expla nation of arithmetic operations in any of these systems, let us review how these operations are carried out in the decimal system. Remember that in a + b, a is called the augend and b is the add en d . Likewise in c - d, c is called the m in u en d and b is the subtrahend. EXAMPLE 1.15 In the decimal system the result of adding 452 and 385 is 837. How do we obtain this result? 452 + 385 7 — Two plus five is seven. There is a single sym bol for th e n u m b e r seven. 452 + 385 37 — Five plus eig h t is th irtee n . There is no single sym bol for th e n u m b er thirteen. Since 13 = 1*10 + 3 we w rite 3 and carry 1. Notice that since thirteen is greater than nine we need more than one digit to represent thirteen. The rule for forming numbers (see Section 1.6) shows that, for number thirteen, 3 “accompanies” the num ber “one” that is carried. 1 — c arry 452 + 385 837 - O ne plus four is five. T his five plus th re e is eight. T h e re is a single symbo] for eight. EXAMPLE 1.16 When we subtract d e c i m a l 23 from decimal 4005 we obta;n 3033. How do we obtain this result? Chương 1: Các khái niệm cơ bản về máy tính 43 4015 -9 8 2 3 — Five m inus tw o is th ree. Therefore, w rite th e symbol for th ree. II 4015 - 9 8 2 33 — Since one is less th a n eig h t we “borrow” one unit from th e d ig it to th e left of th e one. T he borrow ed u n it is equivalent to "borrow ing” 10. T his 10 plus 1 is equal to 11. Therefore, w rite 3 since 11-8 = 3. 9 4015 -9 8 2 033 — T he zero to th e left of th e one became a 9 (th e basis of th e decim al system m inus 1). W rite 0 since 9 - 9 = 0. 3 4015 - 9 8 2 3033 — T he 4 to th e left of th e 0 “paid” th e 10 th a t was previously-"borrow ed” by th e 1. The 4 d ecreases to 3. 1.7.1 Addition of Binary Numbers The rules for adding or subtracting binary numbers are very similar to the ones used in the system. The major difference is that we are limited to only two digits. Table 1-4 shows the binary addition. To carry out these arithm etic operations properly it is necessary to align the n in their rightmost digit as we do in decimal arithmetic. Table 1-4 Addition of Binary Numbers. 0+0=0 0+1 = 1 1+ 0=1 1 + 1 = 0 with a carry of 1 EXAMPLE 1.17 W hat is the result of adding binary numbers 10111100 and 11001111? 44 Chapter 1ễ. Basic Concepts o f C o m p u ters 10111100 -t 11001111 1 — 0 plus 1 is 1. There is a symbol for 1. 10111100 + 11001111 11—0 plus 1 is 1. T here is a symbol for 1. 1 — carry 10111100 + 11001111 o i l *— 1 plus 1 is 0 w ith a carry of 1. 1 10111100 + 11001111 1011 — 1 (th e carry) plus 1 is 0 w ith a carry of 1. T his 0 plus 1 is 1. T h erefo re, w rite 1 an d carry 1. 1 10111100 + 11001111 01011 — 1 (th e carry) plus 1 is 0 w ith a carry of 1. T h is 0 plus 0 is 0. T h erefo re, w rite 0 an d carry 1. 1 10111100 + 11001111 001011 — l (th e carry) plus 1 is 0 w ith a carry of 1. T h is 0 plus 0 is 0. T h erefo re, w rite 0 an d carry 1. 1 10111100 + 11001111 0001011 — 1 (th e carry) plus 0 is 1. T his 1 plus 1 is 0 w ith a carry o f one. T herefore, w rite 0 an d carry 1. Chương 1: Các khái niệm cơ bản về máy tính 45 1 10111100 + 11001111 110001011 — l (th e carry) plus 1 is 0 w ith a carry of 1. T his 0 plus 1 is 1. T herefore, w rite 1 an d carry 1. Since th e re are no more digits to add we w rite th e carry (in bold) as th e leftm ost digit. The process of subtracting binary numbers is very similar to that of the decimal system. The main difference is that instead of “borrowing ten” we “borrow two” from the high-order digits (those to the left of a particular digit). EXAMPLE 1.18 Subtract 11 from 1001 in binary. 1001 -1 1 0 — 1 m inus 1 is 0. 1001 -11 10 - 0 is less th a n 1. It is necessary to borrow “tw o” u n its from th e h ig h er unit. T his tw o plus zero is two. Two m inus one is one. Therefore, w rite 1. 1001 -11 110 — T h e zero to th e left became a 1 (the basis m inus 1). T his 1 m inus th e zero of th e su b trah e n d (not show n h ere but assum ed) is 1. Therefore, w rite 1. 4001 -11 0110 — x h e leftm o st 1 paid th e “tw o” previously borrow ed by th e zero. T his 1 be com es a zero. T his zero m inus th e zero of th e su b trah en d (not show n h ere but assum ed) is 0. Since th is zero is th e leftm ost d igit it is n o t generally w ritten ; how ever, we w rite it h ere for th e sake of explanation. >.7.2 Addition and Subtraction of Hexadecimal Numbers Carrying out arithm etic operations in the binary system is an error-prone task since it is easy to get confused with so many ones and zeros. For this reason it is preferable to carry out arithmetic operations in the hexadeci­ 46 Chapter 1: Basic Concepts of Computers mal system and then transform the results back to binary if necessary. The rules for adding and subtracting numbers in the hexadecimal system are similar to the ones used for the decimal system. However, we need to keep in mind that when performing additions there will be a carry when ever we exceed the value F. Likewise, when performing subtractions, if we need to “borrow” we always “borrow sixteen” instead of “borrowing ten” as we do in the decimal system. To simplify the process of doing arithm etic operations in the hexadecimal system it is convenient to think “in deci mal” and then translate the results back to hexadecimal. The following example illustrates this process. EXAMPLE 1.19 What is the result of adding the hexadecimal numbers 1A23 and 7C28? 1A 23 + 7C28 ® T hree plus eig h t is eleven. There is a symbol for eleven. T herefore, w rite B. 1A 23 + 7C28 4B — Two plus tw o is four. T here is a symbol for four. T herefore, w rite 4. 1A23 + 7C28 64B — T h in k in g “in decim al” we have th a t ten plus tw elve is tw enty-tw o. S ince 22 = 16*1 + 6, w rite 6 an d carry 1. 1A23 + 7C28 964B - O ne (th e carry) plus one is two. T his two plus seven is nine. T h e re is a sym bol for nine. Therefore, w rite 9. EXAMPLE 1.20 What is the result of subtracting in the hexadecimal svs tem B2 from IFOOA? 1FOOA - B 2 8 — Ten m inus two is eight. T here is a symbol for eight. T herefore, w rite 8 Chương 1: Các khái niệm cơ bản về máy tinh 47 1F00A - B 2 58 — Zero is less th a n eleven. Therefore, borrow “16” from th e h ig h er unit. T his sixteen plus zero is sixteen. This sixteen m inus eleven is five. Thus, w rite 5. F 1F00A - B 2 F58 — T his zero becam e F (the basis m inus 1). This F m inus th e zero of th e su b trah en d (n o t show n but understood) is F. Therefore, w rite E E 1F00A - B 2 E F 58 *-The F “paid” th e 16 th a t was “borrowed” by th e leftm ost zero. T he F becam e an E. T his E m inus th e zero of th e subtrahend (not show n b u t understood) is E. T h ere fore, w rite E. 1F00A - B 2 1E F58 — O ne m inus th e zero of th e subtrahend (not show n but understood) is 1. Therefore, w rite 1. HƯỚNG DẪN ĐỌC HIEU CHỦ ĐIEM 1.7 __________________ 1.7 CÁC PHÉP TOÁN SỐ HỌC TRÊN HỆ NHỊ PHÀN, BÁT PHÁN VÀ THẬP LỤC PHÀN Các phép toán số học trẽn hệ nhị phân, bát phân và thập lục phán giống như quy tắc tính trong hệ thập phản. Để tiện lợi trong việc giải thích các phép tính số học trong bất kỳ các hệ, chúng ta hãy ôn lại cách mà các phép tính này trong hệ thập phân. Hãy nhớ rằng trong a + b, a được gọi là augend và b là addent. Tương tự như vậy trong c - d c được gọi là minuend và b được gọi là subtrhend. VÍ D Ụ 1.15 Trong hệ thập phăn kết quả của phép cộng 452 và 385 là 837. Chúng ta tính két quả này bàng cách nào? 452 + 385 7 — H ai cộng n ă m bàng báy. s ố báy ỉà m ột sổ đơn 50 Chapter T.ế Basic Concepts of Computers 1 10111100 + 11001111 001011 - (nhớ) cộng 1 bàng 0 nhớ 1. o cộng o bàng o. Do đó, viết 0 n h ó 1. 1 10111100 + 11001U1 0001011 — (nhớ) cộng 0 là 1. Sô 1 cộng 1 bứng 0 nhớ 1. Do dó viêt 0 nhớ 1. 1 10111100 + 11001111 110001011 — Ị (nhớ) cộng 1 bàng 0 nhớ 1. 0 cộng 1 là 1. Do đó, viết 1 n h ớ 1. BỞI vì không còn số khác đ ể cộng do đó ta viết số trái nhất. Quá trình trừ các sô nhị phân giống như sô thập phản. Khác biệt chính là thay vì mượn 10, chúng ta sẽ mượn 2 từ số ở vị trí cao hơn (nấm bên trái của số đặc biệt này). VÍ D Ụ 1.18 Trừ 1001 cho 11 theo hệ nhị phân. 1001 -1 1 0 — 1 trừ 1 bàng o 1001 -11 10 — 0 nhỏ hơn 1. Do đó mượn 2 từ đơn vị cao hơn. H ai cộng zero là hai. H ai trừ m ột là một. Do đó, viết 1. I 1001 -11 110 — zero bên trái trở th à n h 1 (lấy cơ số này trừ 1). S ố 1 n à y trừ cho zero cùa số bị trừ (được m in h họa theo đ ể bài) là 1. Do đó, viết là 1. Chương 1: Các khái niệm cơ bản vể máy tính 51 0 4001 -11 0110 — S ố tra i n hất là 1 trả ‘h a i’ dã mượn trước đó. Do dó 1 trở th à n h zero. S ố zero này trừ zero cho số trừ (không được m inh họa hưng g iả đ ịn h ) là 0. Vì số 0 ở vị tr i trái n hát do dó thường không được viết; tu y nhiên, ch ú n g ta viết ở đ â y cho p h ù hợp với giải thích. 1.7.2 Cộng và trừ các s ố th ập lục phân Việc tính toán các phép tính trong hệ nhị phân rất dễ sai bởi vì nó dễ lẫn lộn với nhiều số 1 và số 0. Vì lý do này chúng ta nên tính toán các phép sô học trong hệ thập lục phân rồi chuyển kết quả sang hệ nhị phân nếu cần. Quy tắc cộng trừ các số hệ thập tực phân cũng giống như trong hệ thập phân. Tuy nhiên, chúng ta hãy nhớ rằng khi thực hiện phép cộng sẽ nhớ khi tính toán vượt quá giá trị F. Tương tự như vậy khi thực hiện phép trừ, nếu chúng ta cần mượn thì chúng ta luôn luôn mượn 16 thay vì mượn 10 như thực hiện trong hệ thập phân. Để đơn giản hóa quá tính toán trong hệ thập lục phân, chúng ta đang dùng hệ thập phân rồi chuyển kết quả sang hệ thập lục phán. Ví dụ sau đây minh họa cho quá trình này. V Í D Ụ 1.19 Kết quả của cộng hai số thập phân 1A 23 và 7C28 bàng bao nhiêu? 1A 23 + 7C 28 B — Ha cộng tá m bàng 11. Ký tự này là 11. Do đó, v iè tl B. 1A 23 + 7C28 4B — H ai cộng h a i là bón . Ký tự này là 4, hãy viết 4. 1A 23 + 7C28 6-1H - H ãy nhớ ràng trong hệ thập ph â n , mười cộng mười hai là hai mươi hai. Bởi vì 22 = 16* 1 + 6, viết 6 và nhớ 1. 1A 23 + 7C28 964B — M ột (nhá) cộng m ột là hcu. Hai cộng bảy bàng chín. K ý tự này là chín. Do đó viết 9. 52 Chapter 1: Basic Concepts of Computers VÍ DỤ 1.20 Kết quả của trừ hai số thập phán 1F00A và B2 băng bao nhiêu? 1FOOA - B 2 g _ Mười trừ hai là tám . Ký hiệu này là tám. Do đó, viét 8. 1F00A - B 2 58 _ Zero nhỏ hơn mười một. Do đó mượn 16 từ dơn vị cao hơn. Mười sáu cộng zero băng 16. Mười sáu trừ mười m ột là năm . Do đó, viẽt là 5. F 1F00A - B 2 F5g _ S ố zero này trở th à n h F (lấy số này trừ 1). L ấy F này trừ zero của số trừ (không hiển th ị nhưng hểu ngầm ) bằng F. Do dó, viết F. E 1F00A - B 2 E F 58 — F này trả 16 dã mượn. Do đó F trở th à n h E. L ấy E trừ zero của sô' trừ (không h iển th ị như n g ngầm hiểu) là E. Do đó viết E. 1F00A - B 2 1EF58 — M ột trừ zero của số trừ (không hiến th ị nhưng ngầm hiểu) là 1. Do dó, viết 1. Chương 1: Các khái niệm cơ bản về máy tính 53 CHỦ ĐIỂM 1.8 REPRESENTING NUMBERS IN A COMPUTER T p ìn h b à ij c á c s ố tp o n g m ộ t m á ij t ín n All numerical data are represented inside the computer as a sequence of zeros and ones. The arithm etic operations, particularly the subtrac tion, raise the possibility th at the result might be negative. How does the computer know w hether a particular number represents a negative quantity or not? The answer to this question depends on the convention used to represent the numbers. In addition to the unsigned representa tion of a numerical quantity already discussed (see Section 1.1.1), there are some other conventions to represent both negative and positive numbers inside the computer. In this section we will discuss only two of these conventions (the sign-magnitude and the two’s complement). An additional convention (one’s complement) will be discussed later in the chapter (see solved problem 1.21). Any numerical convention needs to differentiate two basic elements of any given number: its sign (positive or negative) and the numerical value itself without the sign (the magni tude). When representing numbers in any of these conventions the notion of “basic unit” needs to be stated explicitly since it may vary from manufac turer to manufacturer. In addition, it is necessary to choose one of the bits of the basic unit as the “sign bit.” The leftmost bit is generally selected for this purpose. As any other bit, this bit can be 1 or 0. Computer manufactur ers have agreed to use 0 as the “positive” sign and 1 as the “negative” sign. 1.8.1 The Sign-magnitude Convention In this convention, given a basic unit of n bits, the leftmost bit is used exclusively to represent the sign. The remaining (n - 1) bits are used for the magnitude. Figure 1-2 shows that bit number 7 is considered the sign bit. The rem aining digits (0 through 6) are used to represent the magni tude. The range of numbers that can be represented in this convention varies from ^2"*' + 2n l - 1] EXAMPLE 1.21 W hat is the sign-magnitude representation of the decimal numbers -41 and +41 if the basic unit is a byte? Since the number +41 is positive we have to set the sign bit to 0. The remaining 7 bits will be used to represent the magnitude. The binary representation of decimal 41 is given by the following bi nary sequence 0101001. That is, 41(10 = 0101001(2. The sign-magnitude representation of the number is 00101001 54 Chapter 1: Basic Concepts of Computers To represent the sign-magnitude of -41 we only need to change the sign bit from zero to 1. Since the binary representation of its magnitude is the same, we have th at the sign-magnitude of -41 is 10101001(2. EXAMPLE 1.22 W hat is the decimal equivalent value of the sign-magnitude binary sequence 10110111? The number is negative since its sign (the leftmost bit) is 1. The magnitude of the number is given by the sequence of bits 0110111. Using the procedure of Section 1.1.1 we find that 0110111,2 = (1*25) + (1*2*) + (1*22) + (1*2') + (1*2°) = 32 + 16 + 4 + 2 + 1 = 55 Therefore, the decimal equivalent of the number 10110111 represented in sign-magnitude is -55. Addition of two numbers in sign-magnitude is carried out using the usual conventions of binary arithmetic. However, if both numbers have the same sign, we add their magnitude and copy the same sign. If the signs are different, we determine which number has the larger magnitude and sub tract the other from it. The sign of the result is the sign of the operand with the larger magnitude. As indicated before, given n bits, in sign-magnitude representation, the range of numbers that can be represented varies from -2n*,+ 2 " ''. There fore, if the result of an arithmetic operation falls outside th a t range, we will say that the operation causes an overflow . EXAMPLE 1.23 W hat is the decimal value of the sum of the binary num bers 10100011 and 00010110 if they are represented in sign-magnitude? Assume that the basic unit is the byte. Notice that the numbers have different signs: 10100011 is negative and 00010110 is positive. To calculate their sum, it is necessary to find out which of these two numbers has the larger magnitude. Using the proce dure of Section 1.1.1 we have that: N u m b er: 10100011 Sign: 1 (n eg ativ e) M ag n itu d e: 0100011 = (1*25) + (1 * 2 ') + (1*2") = 32 + 2 + 1 = 35 D ecim al v alu e: - 3 5 Chương 1: Các khái niệm cơ bản về máy tính 55 N u m b er: 00010110 Sign: 0 (p o sitiv e) M ag n itu d e: 0010110 = (1*24) + (1*22) + (1*2‘) -16 + 4 + 2 Decimal value: -35 = 22 D ecim al value: + 22 Value with the largest magnitude: 35 since 35 > 22. Sign of the difference: negative (sign of the number with the larger numeri cal value) Numerical value of the difference: 13(35 - 22 = 13) Therefore, the decimal value of the sum is -13. 1.8.2 The Two’s Complement Convention The tw o’s com plem ent convention or 2’s com plem ent is the most popular among computer manufacturers since it does not present any of the problems of the sign-magnitude or one’s complement (see solved prob lems 1.21 and 1.22). Positive numbers are represented using a similar procedure to that of the sign-magnitude. Given n bits, the range of num bers that can be represented in two’s complement is -2"' to 2 "1 - 1. Notice that the range of negative numbers is one larger than the range of the positive values. To represent a negative number in this convention, follow the three-step process shown below: Step 1. Express the absolute value of the number in binary. Step 2. Change all zeros to ones and all ones to zeros in the binary number obtained in the previous step. This process is called “complementing the bits.” Step 3. Add one to the binary number of step 2. In the two’s complement convention, given a negative number, to find its positive counterpart we exercise steps 2 and 3 of the previous process. EXAMPLE 1.24 W hat is the two’s complement representation of -31? Step 1. The absolute value of the number is 31. Using the procedure of Section 1.5.2, we have that the binary representation is 00011111(2. That is, 31(10 = 00011111(2. Step 2. Changing all zeros to ones and vice versa, we have that the number looks like 11100000. Step 3. Adding 1 we have that 56 Chapter 1: Basic Concepts of Computers 11100000 + 1 11100001 Therefore, the two’s complement representation o f-31 is 11100001. Notice that the sign of the result is 1 as it should be. EXAMPLE 1.25 What is the decimal positive value of the two’s complement number 11100100? Follow steps 2 and 3 of the procedure indicated above since the number is negative. Step 2. Complement all bits of the given number. That is, change 11100100 to 00011011. Step 3. Add 1 to the previous result and we have O OOllOtl+ 1 00011100 Therefore, the positive counterpart of 11100100 is 00011100. The value of the latter number can be calculated using the procedure of Section 1.1.1. Thus, the decimal positive counterpart of the given number is 28. 1.8.2.1 Arithmetic Operations in Two’s Complement To add numbers represented in two’s complement treat the numbers as unsigned integers. That is, treat the sign bit as any other bit of the num ber. Ignore any carry out of the leftmost position if there is one. To sub tract two’s complement numbers, treat the numbers as unsigned integers. If a borrow is needed in the leftmost place, borrow as if there were another bit to the left of the minuend. EXAMPLE 1.26 W hat is the result of the addition of the numbers 11000111 and 11011101 if both numbers are represented in two’s complement nota tion? W hat is the decimal value of the result? 11000111 + 11011101 0 *— 1 -*■ 1 = 0 w ith a carry of 1. W rite 0 an d carry 1. Chương 1: Các khái niệm cơ bản về máy tính 57 1 11000111 + 11011101 00 — The carry plus one is zero w ith a carry of 1. T his zero plus zero is zero. W rite 0 and carry 1. 1 11000111 + 11011101 100 — The carry plus one is zero w ith a carry of 1. T he zero plus one is one. Therefore w rite one an d carry 1. 1 11000111 + 11011101 0100 — T h e carry plus zero is one. This one plus one is zero w ith a carry of one. T h ere fore, w rite zero and carry one. 1 11000111 + 11011101 00100 — T h e carry plus zero is one. T his one plus one is zero w ith a carry of one. W rite 0 an d carry 1. 1 11000111 + 11011101 100100 — T he carry plus zero is one. T his one plus zero is one. Therefore, w rite 1. 11000111 + 11011101 0100100 — O ne plus one is zero w ith a carry of one. Therefore, w rite zero and carry one. 11000111 + 11011101 10100100 — T he carry plus one is zero w ith a carry of one. T his zero plus one is one. T herefore, w rite 1 and ignore th e carry. 58 Chapter 1: Basic Concepts of Computers The decimal value of the result is *92. Note that -92 = -57 -35. Observe that 10100100 = -92, 11000111 = -57 and 11000111 = -35. EXAMPLE 1.27 What is the result of subtracting 11011101 from 00111001? Assume that both numbers are represented in two’s complement notation. 00111001 -11011101 0 — One m inus one is zero. Therefore, w rite zero. 00111001 -11011101 00 — Zero m inus zero is zero. Therefore, w rite zero. 00111001 -11011101 00 — Zero is less th a n one. Borrow “two” from h ig h er u nit. Since tw o m inus one is one, w rite one. 0 00114001 -11011101 1100 - T h e one (show n in bold and strik eth ro u g h ) “paid ” th e u n it th a t w as borrowed by th e zero. T he one becam e a zero. Since th is zero is less th a n one, borrow “two” from th e h ig h er unit. Therefore, w rite one since tw o m inus one is one. 0 00111001 -11011101 11100 - T h e one (show n in bold and strik eth ro u g h ) “p aid ” th e u n it borrow ed in the previous step. T he one becam e a zero. Since zero is less th a n one, follow a process sim ilar to th e one described in th e previous step . T herefore, w rite one. 0 00411001 -11011101 011100 -T h e one (show n in bold an d strik eth ro u g h ) “paid” th e u n it borrow ed in th e previous step. T h e one becam e a zero. Since zero m inus is zero. T herefore, w rite zero. Chuong 1: Cac khai ni$m co ban ve may tinh 59 00111001 -11011101 1011100 — Zero is less th a n one. Borrow a “two” and w rite one since two m inus one is one. 1 «0111001 -11011101 01011100 ■ T h e zero becam e a one. W rite zero since one m inus one is zero. Notice that the previous operation assumes that there is an “invisible” one-bit to the left of the minuend. This “invisible” bit paid the 2’s borrowed by the leftmost zeros. 1.8.2.2 Overflow Conditions in Two’s Complement As indicated before, given n bits, the range of numbers that can be represented in two’s complement is -2"1 to 2"'1 -1. Whenever the result of an operation falls outside that range an overflow condition occurs. We will notice that in all overflow conditions, the sign of the result of the operation (addition or subtraction) is different than that of the operands. That is, if the operands are both positive, the result is negative or if the operands are both negative the result is positive. Solved problems 1.15 and 1.16 illus trate another method to detect if an overflow has occurred. EXAMPLE 1.28 W hat is the result of adding the following two’s comple ment numbers 11000111 and 10100100? 11000111 + 10100100 11000111 + 10100100 1 — W rite one since one plus zero is one. 11000111 + 10100100 11 — W rite one since one plus zero is one. 11000111 + 10100100 011 — W rite zero since one plus one is zero w ith a carry of one. 62 Chapter 1: Basic Concepts of Computers Table 1-5 Decimal Representation of Digits 0-9 in Two Different Weighted Codes Decimal Digit Weight 8-2-4-1 Weight 2-4-1-2 0 0000 0000 1 000 1 000 1 2 0 0 10 0 0 10 3 0 0 11 00 11 4 0 1 0 0 0 10 0 5 0 10 1 10 11 6 0 1 1 0 1100 7 0 111 1 1 0 1 8 1000 1110 9 100 1 1111 Two questions need to be answered concerning the dual representation of a digit. First, how does the computer know which one is the correct code? Second, can both be used interchangeably? The answer to the latter question is no. Only one code word can be used. However, this does not answer which of the two code words is the correct one. To answer this question satisfacto rily we need to define the notion of a self-complementing code. A code is said to be self-complementing if, given any decimal digit N and its corresponding code word X jX ^X ^ the value of 9 - N (the 9’s complement of the decimal) can be obtained by complementing the bits of the code word. We will use the notation X to indicate the complement of a bit X. EXAMPLE 1.31 The code 2-4-2-1 is self-complementing. Notice th a t in this code the 9’s complement of any decimal can be obtained by complementing the bits of its corresponding code word. Decimal (N) 2-4-2-1 9 - NRepresentation of y - N in 2-4-2-1 0 0000 9 1111 1 000 1 8 1110 2 00 10 7 110 1 3 0 0 11 6 1100 4 0 10 0 5 10 11 5 10 11 4 0 10 0 6 lion 3 0 0 11 7 110 1 2 00 10 8 1110 1 000 1 9 1111 9 0000 Chuang 1: Cac khai ni$m cd ban ve may tinh 63 1.8.3.2 American Standard Code for Information Interchange Computers are also used extensively to process alphanumeric informa tion. To carry out this task the most common approach is to encode the individual characters that need to be manipulated. On a typical English computer keyboard there are at least 128 different characters: Digits: 10 Letter (upper and lower): 52 Special symbol: 33 includes !, @, #, $, %, A, &,*, (,) etc. Control characters: 33 includes Enter, space, backspace, etc. 128 The minimum number of bits necessary to represent these many char acters is 7 since 2' = 128. The most common code in the computer industry is the 7-bit code known as the American Standard Code for Information Interchange or ASCII for short. However, since the basic un-t of storage is the byte, all ASCII codes are represented using eight bits. This leaves the most significant bit as zero. Another code used extensively by the Interna tional Business Machines Corporation is the Extended Binary Coded Deci mal Interchange Code or EBCDIC for short. In this book we only consider the ASCII code. The set of ASCII characters is shown in Chapter 3. The ASCII code w as developed by the American National Standards Institute (ANSI) to allow information exchanges between equipment created by dif ferent manufacturers. EXAMPLE 1.32 W hat is the ASCII representation of the message “Hello World”? Assume that addresses increase from left to right. A sequence of characters is represented in memory as a series of con secutive bytes. Each byte holds one ASCII character code. Using the chart in Chapter 3 (see page 64) and the hexadecimal equivalent of each charac ter the message representation is He l l o Wor l d 48 65 6C 6C 6F 20 57 6F 72 6C 64 Observe th at the space character (hex 20 or decimal 32) is a character like any other. However, the authors recognize that it is an elusive charac ter that is very difficult to see. We have also assumed that the addresses increase from left to right to facilitate the reading of the characters. 64 Chapter 1: Basic Concepts of Computers 1.8.4 Error Detection When binary data are transm itted over any type of communication line, the possibility of an error in the transmission always exists due to equip ment failure or the presence of “noise.” When an error occurs it is possible that one or more bits of a byte could change from 0 to 1 or vice versa. Whenever this happens a code word can be changed into an incorrect but valid code or to a sequence of bits which do not represent anything. In this book we will only consider the detection and correction of single errors. That is, errors where only one single bit changes. The numbers of bits that have to change within a byte before the byte is converted into an invalid code is sometimes used as a criterion for classify ing codes. If only one bit of a byte needs to change, the code is said to be a single-error-detecting code. If only two bits need to change then the code is said to be a two-error-detecting code. To detect single errors we use an extra parity check bit. A parity bit is used to ensure th a t each code word, including the parity bit, has an even numbers of l ’s (even parity) or an odd number of l ’s (odd parity). Table 1-6 shows the even parity bit for the error-detecting code 8-2-4-1. Table 1-6 Weight Decimal Digit '8-2X 1Parity Bit (even parity) 0 0000 0 1 0001 1 2 00X0 1 3 00 11 0 4 0100 1 5 0 10 1 0 6 0 1 1 0 0 7 0 111 1 8 1000 1 9 100 1 0 One of the most common tasks encountered in any computer system is that of transm itting information from one computer to another. The com puter that sends the information is called the source; the computer that receives the information is called the destination. Both sender and re ceiver follow international standards to accomplish this task. It is assumed that the transm itted signal is divided into a series of one-bit intervals of length T During each of these intervals the source will send either a 0 or a 1 (shown in Fig. 1-8 as high and lows). Chuüng 1: Câc khai niçm co ban vé mây tinh 65 To communicate among themselves, computers may follow a convention like the one illustrated in Fig. 1-9. It is the responsibility of the destina tion to detect the value and correctness of the received signal. The process that two computers may use to communicate with each other can be described as indicated below. We will use Fig. 1-9 as a refer ence. (1) If the source is not sending any message, it continuously transm its a sequence of l ’s. 1 0 1 1 0 1 0 1 Fig. 1-8 Representation of 1 and 0 as high and lows. Parity Stop bit , , bit byte being transm itted Fig. 1-9 Typical byte format for data transmission. (2) A O-bit indicates the beginning of the message. This first 0-bit is called the start bit. It is assumed that the bytes making up the message follow the start bit. (3) The parity check bit is set according to the parity convention being used (even or odd). (4) After the parity check bit another 1-bit (the stop bit) is transm it ted to indicate that the transmission of the entire byte has been completed. (5) At this point the source may continue transm itting the next byte or it may start transm itting a continuous sequence of l ’s indicating that there are no more messages for the time being. EXAMPLE 1.33 Two computers are communicating with each other using the data format convention of Fig. 1-9, the ASCII character set and even parity: The message shown below has a parity error. How does the computer recognize that an error has occurred? Can the computer tell the position of the complemented bit? Assume that the start bit is not shown. The arrow indicates the direction in which the characters need to be considered. 6 6 Chapter 1 : Basic Concepts of Computers 0101011001 0110100101 0110111101 0110110001 0110010101 0110010001 0111001111 0010000011 0110000111 0111001001 0110010101 0010000011 0110001011 0110110001 0111010111 0110010101 0010111001 Using the format of Fig. 1-9 each sequence of ten bits (one 8-bit byte, one parity check bit and one stop bit) can be considered as the representa tion of a single character of the message. Working with each group of bits separately and dropping the stop bit we can check the rightm ost bit, the parity bit (shown in bold below). 1. 010101100 ✓ 2. 011010010 ✓ 3. 011011110 ✓ 4. 011011000 ✓ 5. 011001010 6. 011001000 X 7. 011100111 8. 001000001 9. 011000011 ✓ 10. 011100100 ✓ 11. 011001010 ✓ 12. 001000001 ✓ 13. 011000101 ✓ 14. 011011000 ✓ 15. 011101011 ✓ 16. 011001010 ✓ 17. 001011100 ✓ The parity check bit of group No. 6 should be one instead of zero since we are working with even parity. Observe that the computer cannot tell the position of the erroneous complemented bit. Use the chart in Chapter 3 to decode the message. Can you guess the word that was changed? Can you tell the bit that was complemented? We leave these questions as an exercise for the reader. The previous example shows that using the parity bit alone the com puter can tell that an error has occurred but cannot tell the position of the bit that was complemented. In general, given n bits, to obtain an error-detecting code no more than half of the 2” possible combinations of these n bits can be used. In addi tion, the code words must be chosen in such a way that, for any code word to produce another valid word, at least two bits must be complemented. The minimum number of bits that need to change in a code word to produce another valid coded word is called the m in im u m d ista n c e of the code. Therefore, we can rephrase the previous statem ent by saying th at given n bits, to obtain an error-detecting code its minimum distance must be two or more. The even parity 8-4-2-1 code shown in Table 1-6 has a minimum distance of two. 1.8.5 Error Correction Once an error has been detected, there are some methods th at can be used to identify and correct the complemented bit. In this section we will consider some of the error-correcting codes. In general, a code is said to be an error-correcting code if the correct code word can always be inferred from the erroneous code. The Forward Error Correction (FEC) and the Hamming Code methods are examples of this type of code. Both methods require additional redundant bits to identify and correct the errors. Chương 1: Các khái niệm cơ bản về máy tính 67 1.8.5.1 Forward Error Correction In this correction schema, a p a rity block complements the parity bit of each byte after a predetermined number of n bytes. Each bit of the parity block checks the parity of the preceding n bits that occupy the same position in the preceding n bytes. Using both pieces of information it is possible to find and correct the bit in error. Example 1.34 illustrates this method and the use of the msb of an ASCII code as a parity bit. EXAM PLE 1 .3 4 Assume that two computers communicate with each other using ASCII code and that a parity block is transm itted every four bytes. In addition, consider that even parity is used at both the byte level and the block level. Parity bits are shown in italics and the parity block is shown in bold. Bytes Transmitted Bytes Received In th e P arity block . each b it c h e ck s th e p arity along a particular column. 01100011 71100001 01110100 71110011 00000101 01100011 71100001 01111100 71110011 00000101 E r r o r in th i s ^ row . P a rity b it (in italics) is zero b u t th e re is an odd n u m b e r of l ’s in th is E rro r in th is colum n. P arity b it of th e p arity block for th is column (in bold) is zero but th e re is an odd num ber of l ’s in th e column. It is the responsibility of the receiving computer to check the parity of every column and every row. Whenever the computer identifies the bit in error in a particular byte it complements the bit to recover from the error. 1.8.5.2 Hamming Code This method can be used to provide multiple-error detection. The funda mental principles in constructing this code for m given bits are as follows: (1) Add k additional parity checking bits denoted by pp p2, ... pk to the m given bits. The resulting code will have code words of (m + k) bits. Choose the value of k so that it satisfies the inequality 2k > r a + k + l For example, if we want to transm it four data bits (m = 4), the value of k must be 3 since 6 8 Chapter 1: Basic Concepts of Computers 23> 4 + 3 + l This result implies that we need to add three parity checking bits denoted by pp p2, and p3. (2) Number the (m + k) bits 1 through m + k; start by assigning 1 to the most significant bit and continue until you assign the value m + k to the least significant bit. Consider these numbers as the posi tions of the bits in a code word. (3) Place the checking bits in positions 1, 2, 4 . . . 2k'' of the code word. When k = 3, the checking bits are placed in positions 1, 2, and 231. That is, in positions 1, 2, and 4. The position of the bits b,, b2, b3, and b4 and the checking bits p i, p2, and p3 in the encoded word is as follows: Position —* 1 2 3 4 5 6 7 Pi P2 P3 b2 b3 b4 (4) Form k sets, P,, P2. . . Pk of binary numbers. The binary numbers in set Pi should be such that their representation has k or fewer bits and has 1 in the jth, position. Select p; in such a way th a t it has even parity in the positions indicated by the elements of the set Pj. For k = 3 form sets P p P2, and P3. The elements of each of these sets should have 3 or fewer bits in their representation. Table 1-7 shows the seven possible combinations th at we can form with 3 bits that satisfy the condition of step 4. According to this table the sets and their elements are: PI = (1,3,5,71 P2 = (2,3,6,71 P3 = 14,5,6,7) Notice th at the elements of P I have l ’s in column 1, the elements of P2 have l ’s in column 2, and the elem ents of P3 have l ’s in column 3. Table 1-7 p3 p2 p. 1. 0 0 1 2. 0 1 0 3. 0 1 1 4. 1 0 0 5. 1 0 1 6. 1 1 0 7. 1 1 1 Chương 1-ệ Các khái niệm cơ bản về máy tính 69 Therefore, select Pj so as to establish even parity in positions 1, 3, 5, and 7. select p2 so as to establish even parity in positions 2, 3, 6, and 7. select p3 so as to establish even parity in positions 4, 5, 6, and 7. (5) Form the code word to be transm itted by adding the appropriate checking digits so that the parity condition of the previous step is satisfied. EXAM PLE 1 .3 5 If the sequence 1101 (data) is to be transm itted, what is the code word if Hamming Code is used? Position 1 2 3 4 5 6 7 Pi P2 bi Pa ^2 b3 b4 Transmitted data Even parity Even parity 1 1 1 in positions in positions 1, 3, 5, 7 requires t k n t n — 1 that pi = 1 Even parity in positions 2, 3, 6, 7 requires that f t = 0 Even parity in positions 4, 5, 6, 7 requires that p, = 0 1 0 1 The code word is formed by concatenating the value of the bits in posi tions 1 through 7. In this case the actual word being transm itted is 1010101. Note: The reader should be aware that depending on how the bits are numbered we may obtain a different value. In this section, as indicated in step 2, we assign the value 1 to the most significant bit and the value 7 to the least significant bit. The code will work with either convention as long as the reader is consistent in using the numbering scheme. To locate and correct the error use the following steps: (1) Perform k parity checks on selected digits of each code word. The result of each of these parity checks is either 0 if no error has occurred or 1 if an error has been detected. (2) Using the results of the parity tests, form a binary number rkr2 . r r The decimal value of this number gives the position of the erro neous digit. 70 Chapter 1: Basic Concepts of Computers EXAMPLE 1 .3 6 Assume that the word sent is 1010101. If the word re ceived is 1011101, find the position of the bit in error using the procedure indicated above. (1) Since three checking digits were added, three parity checks need to be performed. Position Data parity check for p, = parity check for p2 = parity check for p, - 1 Pi1 1 2 p2 3 b, 1 1 5 bj 1 1 6 b3 7 1 1 1 1 rl « 0 since parity is even r2 = 0 since parity is even r3 = 1 since parity is odd The position of the erroneous bit is r3r2rj = 100. The decimal value of this number is 120'0° = 1*22 = 4. This result indicates th a t the erroneous bit occupies position 4 on the received byte as we have already assumed. The bit on the 4th position is then complemented to form the correct message. HƯỚNG DẪN ĐỌC HIEU CHỦ ĐIEM 1.8 __________________ 1.8 TRÌNH BÀY CÁC CON s ố TRONG MÁY TÍNH Tất cả các dữ liệu số được trình bày bên trong máy tính dưới dạng một chuỗi các số zero và số 1. Các phép toán học đặc biệt là phép trừ có thể có kết quả ảm. Làm sao máy tính hiểu được một số đặc biệt mô tả cho số âm? Cău trả lời này phụ thuộc vào nguyên tác sử dụng dể trình bày các con số. Cách mô tả một số không dấu đã được thảo luán (xem phần 1.1) có nhiều quy tắc trình bày các sô dương và âm trong máy tính. Trong phần này chúng ta sẽ thảo luận hai quy tắc ( dấu độ lớn và phần bù của hai). Một quy tắc bổ sung (phần bù của một) sẽ được thảo luận sau chương này. (xem bài tập 1.21). Bất kỳ quy tấc số nào cũng có hai thành phần khác biệt ca bản của một số đa cho: dấu của nó (dương hoặc ăm) và giá trị không dấu (độ lán). Khi biểu diễn các sô trong các quy tác này, khái niệm về đơn vị cơ bản cần được phát biểu chính xác bởi vì nó có thể khác nhau tùy theo nhà sản xuất. Nó cần phải chọn một trong các bit của đơn vị cơ bản là bít tín hiệu. Bít trái nhất được chọn cho mục đích này. Các bit khác có thể 1 hoặc 0. Các nhà sản xuất máy tính dồng ý sử dụng 0 như là ký hiệu “dương” và 1 là ký hiệu âm “ám ”. Chương 1: Các khái niệm cơ bản về máy tính 71 1.8.1 Quy ước về d ấ u độ lớn Trong quy ước đưoc cho bởi một đơn vị cơ bản là n bit, bit trái nhất dược dùng để mô tả tín hiệu. Các bit còn lại (n - 1) được dùng để mô tả độ lan. Hình 1.2 minh họa bít số 7 là bít tín hiệu. Các số còn lại (0 đến 6) là bit được dùng để mô tả độ lớn. Các số được mô tả trong quy tác này nằm trong 2"*' + 2"'1 - 1. V I D Ụ 1.21 Trình ờẵy dấu độ lớn của các số thập phăn - 41 và + 41 nếu đơn vị cơ bản là byte? Bởi vi sô + 41 là sô dương do đó ta sẽ đặt bit ký hiệu là 0. 7 bit còn lại sẽ được sử dụng đ ể mô tả độ lớn. Kiểu trình bày nhị phân của sổ thập phân 41 được cho bởi chuỗi thập phân 0101001. Nghĩa là 41ao = 0101001(2. Trình bày dấu độ lớn của số này là 0010100112. Để trình bày dấu độ lớn của 41 ta chỉ cần thay dổi bit tín hiệu từ zero sang 1. Vì mô tả độ lớn của số nhị phán là như nhau, do đó ta có được tín hiệu của độ lớn của - 41 là 10101001 (2. V I D Ụ 1.22 Giá trị thập phăn tương ứng của tín hiệu độ lớn của chuỗi nhị phân 1011011 là bao nhiêu? Số này là sô âm bởi vì tín hiệu của nó (ở bit trái nhất) bằng 1. Độ lớn của số được cho bởi chuỗi của bít 0110111. Bằng cách sử dụng phương pháp ở phần 1.1.1 ta tìm được. 0110111(2 = (1*25) + (1*24) + (1*22) + (1*2‘) + (1*2°) = 32 + 16 + 4 + 2 + 1 = 55 Do đó, sô thập phần tương ứng của số 10110111 được mô tả theo tín hiệu độ lớn là - 55. Cộng hai sô trong tín hiệu độ lớn dược tính bằng cách sử dụng các phép tính nhị phân thông thường. Tuy nhiên, nếu hai số này cùng dấu, chúng ta cộng độ lớn rồi sao chép dấu đó, nếu các dấu khác nhau, chúng ta xác định số nào lớn hơn và trừ cho số còn lại. Dấu của kết quả là dấu của toán hạng có độ lớn hơn. N hư đã trình bày ở trước, cho n bit, trong mô tả tín hiệu độ lớn, các số được trình bày nằm trong đoạn 2"*' + 2n i ■ 1. Do đó, nếu kết quả của phép toán nằm ngoài dãy này, ta nói phép toán này là nguyên nhăn gây ra tràn bộ nhớ. V Í D Ụ 1.23 Giá trị thập phăn của tổng hai số nhị phân 10100011 và 00010110 là bao nhiêu nếu chúng được mô tả theo dấu độ lớn? Giả sử rằng đơn vị cơ bản là byte. 72 Chapter 1: Basic Concepts of Computers Lưu ý rằng các sô có các kỷ hiệu khác nhau là: 10100011 là số ám và 00010110 là dương. Dể tính toán tổng, chúng ta cần tìm sô lớn hơn. Bàng cách sử dụng phương pháp ở phần 1.1.1 ta có được. Số: 10100011 Số : 00010110 Ký hiệu: 1 (ăm) Ký hiệu: 0 (dương) Độ lớn: 0100011 = (1*25) + (1*2') + (1*2°) Độ lớn 0010110 = (1*24) + (1*2’) + (1*2') = 32 + 2 + 1 = 16 + 4 + 2 = 35 “ 22 Giá trị thập phân:- 35 Giá trị thập phán: + 22 Giá trị lớn nhất của: 35 vì 35 > 22 Ký hiệu khác nhau: ăm ( ký hiệu của số có giá trị lớn hơn) Tính ra giá trị khác: 13(35 ■ 22) = 13) Do đó, giá trị thập phán của tổng là - 13. 1.8.2 Quy tắc p h ầ n bù của hai Quy tắc phần bù của hai hoặc phần bù 2 là phép tính phổ biến nhất của máy tính bởi vì nó không gặp bất kỳ vấn đề gì cũng như quy tắc dấu độ lớn hoặc phần bù của 1 (xem bài tập 1.21 và 1.22). Các số dương được mô tả giống như dấu độ lớn. Cho n bít, dãy các số được miêu tả trong phần bù của hai là 2"'1 cho đến 2n l - l.Lưu ý ràng dãy sô âm lớn hơn giá trị của dãy sô dương. Để mô tả một dãy số âm trong quy tác này, hãy theo ba bước sau: Bước 1. Biểu diễn giá trị tuyệt đối của số này dưới dạng nhị phán. Bước 2. Thay dổi tất cả các số zero bằng 1 và tất cả số 1 thành zero trong số nhị phân đã tính trong bước trước. Quá trình này được gọi là “phần bù của bit”. Bước 3. Thêm cộng 1 vào sô nhị phân ở bước 2. Trong quy tắc phần bù của hai, với một số âm đã cho, đ ể tìm giá trị dương tương ứng, ta thực hành các bước 2 và 3. V I D Ụ 1.24 Phần bù của hai bàng bao nhiêu ứng với số 31? Bước 1. Lấy trị tuyệt đối của sô này bàng 31. Băng cách sủ dụng phương pháp ở phần 1.5.2, chúng ta có được số nhị phân tương ứng là 00011111 a Nghĩa là 31(102 = 00011111 r Bước 2. Thay đổi tất cả số zero thành 1 và ngược lại, chúng ta có đưac số 11100000. Bước 3. Cộng 1 chúng ta có được Chương f Ể' Các khái niệm cơ bản về máy tính 73 11100000 + 1 11100001 Do đó, phần bù hai của số 31 là 11100001. Lưu ý rằng dấu của của kết quả là 1. VÍ D Ụ 1.25 Giá trị dương thập phân, của phần bù hai là 11100100 là bao nhiêu? Tuân theo các bước 2 và 3 của phương pháp chi dẫn à trên thì số này là âm. Bước 2. Lấy phần bù cho các bít của số đã cho. Do đó, nó sẽ đổi là 11100100 thành 00011011. Bước 3. Cộng 1 vào kết quả ta có 00011011+ 1 00011100 Do dó, phần dương tương ứng của 11100100 là 00011100. Giá trị của số sau có thể được tính toán bằng cách sử dụng phương pháp ở phần 1.1.1. Do đó, kết quả sô dương của sô đã cho là 28. 1.8.2.1 Các p h ép tín h số học trong p h ần bù của hai Để cộng các số được mô tả trong phần bù của hai hãy xem các số này là các sô nguyên không dấu. Điều này có nghĩa là hãy xem các ký hiệu bít như là một số nguyên khác. Bỏ qua bất kỳ giá trị nhớ nào ở vị trí trái nhất nếu có. Đề trừ các sô bù, hãy xem các sô này là số nguyên không dấu. Nếu cần mượn thêm tại vị trí bên trái, hãy mượn nếu có một bít khác nấm bên trái. VÍ D Ụ 1.26 Kết quả của phép cộng các sô 11000111 và 11011101 bàng bao nhiêu nếu cả hai số này được mô tả dưới dạng phần bù của hai? Giá trị thập phân này bằng bao nhiêu? 11000111+ 11011101 0 — 1 + 1 = 0 với 0 nhớ 1. Viết 0 nhớ 1 74________________Chapter Tễ- Basic Concepts of Computers ----------------------------- 11000111 + 11011101 00 - L ấy sô nhớ cộng với 1 bàng 0 nhớ 1. 0 cộng 0 bàng 0. Viết 0 n h ớ 1. 1 11000111+ 11011101 100 - L áy số nhớ cộng với 1 bằng 0 nhớ 1. L ấy 0 cộng 1 bằng 1. Do dó viết 1 nhớ 1. 1 11000111 + 11011101 0100 - Lấy sô nhớ cộng với 0 bàng 1. Lấy số 1 cộng vói 1 bàng 0 n h ớ 1. Do dố, viết 0 nhớ 1. 11000111 + 11011101 00100 — Lấy SO nhớ cộng 0 bàng 1. Lấy 1 cộng với 1 b àng 0 n h ó 1. V iết 0 n h à 1. 1 11000111 + 11011101 100100 -L ấy sô' nhớ cộng với 0 bàng 1. L ấ y 1 cộng 0 bàng 1. Do đó viết 1. 11000111 + 11011101 0100100 -M ột cộng m ột bàng 0 nhớ 1. Do đó, viết 0 n h ớ 1. 11000111 + 11011101 10100100 - Lấy n h á cộng 1 là 0 n h ó 1. L ấy 0 năy cộng với 1 là 1. Do đó 1 lết 1 và bó p h ầ n nhớ. Giá trị thập phân của kêt quả này là 92. Lưu ý ràng 92 = 57 - 35 Do đó 101000100 = 92, 11000111 = 57 và 11000111 = 35. VI D Ụ 1.27 Kẽt quả của phép trừ 11011101 từ 00111001 là bao nhiêu ? Giả sử cả hai sô này được trình bày dưới dạng phần bù cùa hai. Chương 1: Các khái niệm cơ bản về máy tính 75 00111001 -1 1 0 1 1 1 0 1 0 - 1 trừ 1 bằng 0. Do đó viểt 0. 00111001 -1 1 0 1 1 1 0 1 00 - 0 trừ 0 bàng 0. Do đó viết 0. 00111001 -1 1 0 1 1 1 0 1 0 0 - 0 nhỏ hơn 1, do dó mượn “h a i” từ đan vị cao hơn. Do đó 2 trừ 1 là 1, viết 1. 0 00111001 -1 1 0 1 1 1 0 1 1100 - 1 (được in đ ậ m và ké ngang) “trá lạ i” cho sổ dà mượn từ zero trưóc đó. 1 trớ th à n h 0. Bới vậy 0 nhỏ hơn 1, mượn “h a i” tín h từ đơn vị cao han. Do đổ, viết m ột từ 2 trừ 1 là 1. 0 00111001 -1 1 0 1 1 1 0 1 11100 - ỉ (được in đậm và kẻ ngang) “trả lại" cho số đã mượn từ zero trước đó. 1 trờ th à n h 0. Vi 0 nhỏ hơn 1, thực hiện theo qui trìn h tương tự n h ư qui trin h đã được m ô tả trong bước trước đó,. Do đó, viết 1. 0 00111001 -1 1 0 1 1 1 0 1 011100 - 1 (được in đ ậ m và kẻ ngang “p h á i trả" cho số được mượn ở bước trước. 1 trở th à n h 0. Bởi vì 0 trừ 0. Do đó, viết 0. 00111001 -1 1 0 1 1 1 0 1 1011100 - 0 nhỏ hơn 1. Mượn “hai" và viết 1 vì 2 trừ 1 là 1. 1 90111001 -11011101 01011100 —zero trà th à n h 1. Viết 0 bởi vi 1 ■ 1 là zero. 76 Chapter 1: Basic Concepts of Computers Lưu ý ràng giả sử phép toán ở trước có một bít không nhận thấy nằm ở bên trái của số bị trừ. Bít không nhìn thấy này sẽ trả hai dược mượn bởi zero trước đó. 1.8.2.2 Các điều kiện tràn bộ nhớ trong phần bù cùa hai. N hư hướng dẫn ở phần trước với một số n đã cho, dãy các sô được biểu diễn theo hần bù cùa hai là 2 "1 đến 2" 1 - 1. Cuối cùng kết quả của mồi phép toán nầm ngoài dãy này thì điều kiện tràn bộ nhớ xảy ra. Chúng ta thấy ràng trong tất cả điều kiện tràn bộ nhớ dấu kết quả của toán tử (cộng hoặc trừ) khác với các toán hạng khác. Điều này là vì nêu các toán hạng lại dương thì kết quả là âm hoặc nếu các toán hạng ăm thì kết quả là dương. Các bài tập 1.15 và 1.16 sẽ chi ra phương pháp khác để phát hiện việc tràn bộ nhớ có xảy ra hay không. VI DỤ 1.28 Nếu kết quả của phép cộng sô bù của hai là 11000111 và 10100100 là bằng bao nhiêu? 11000111 + 10100100 1 *“ Viết 1 bởi ui 1 cộng 0 là 1 11000111+ 10100100 “-Viết 1 bời vì một 1 cộng 0 là 1. 11000111 + 10100100 011 — Viết 0 bởi 1 cộng I là zero nhớ 1. 1 11000111 + 10100100 1011 - P hẩn nhớ cộng 0 là 1. 1 cộng 0 là 1. Vi vậy viết 1. 11000111 + 10100100 01011 — 0 cộng 0 là 0. Do đó,ụ viết 0. 11000111 + 10100100 101011 - 0 cộng 1 là 1. Viết 1. Chương 1: Các khái niệm cơ bản về máy tinh 77 n c x x m i + 10100100 1101011 — ỉ cộng 0 là 1. Do đó viết 1. 11000111 + 10100100 0 1 1 0 1 0 1 1 —2 cộng 1 là 0 nhở 1. Do đó, viết 1 và bỏ qua p hần nhớ. Lưu ý rằng một số tràn dã xảy ra bởi vỉ kết quả của phép cộng là số dương trong khi các toán hạng đều là số ăm. Giá trị này cho thấy giá trị của nó nằm ngoài dãy cho phép trong một byte theo phần bù của hai. Trong thực tế, với 8 bit các giá trị biến đổi từ -27 đến 2? - 1 hoặc từ - 128 đến 127 (xem phần 1.8.2). Giá trị tổng theo số thập phân tính là - 149. Giá trị này nằm ngoài dãy - 128 đến 127. 1.8.3 Các m ã n h ị p h â n và các m ã ch ữ sô Con ngưòi thích làm việc với các sô thập phân hơn vái chuỗi dài các sô 0 uà 1. Máy tính làm việc với các chuồi nhị phân. Đề tạo cầu nối trong việc giao tiếp giữa con người và máy móc, nhiều mã số được tạo ra nhiều đoạn mã sồ được tạo ra dể các số thập phân được mô tả theo một chuỗi các số nhị phân. Bàng cách này máy tinh có thể thực thi tất cả tính toán của nó trong hệ nhị phân rồi sau đó chuyển kết quả này sang dạng thập phản cho ứng dụng của con người. Trong phần này chúng ta sẽ xem xét một số mã quan trọng (BCD và Hamming) và các mã số ASCII. Một mã nhị phân là một nhóm n bit có 2" két hạp khác nhau của 0 và 1 với mỗi tổ hợp biểu thị cho mọt thành phần của một tập hạp đang được mã hóa. Ví dụ với 2 bít có thể biểu diễn một tập hạp gồm bốn phần tử khác nhau. Có nghĩa là chúng ta có thể biểu diễn bốn phần tử khác nhau trong một tập hạp. 2'2 tổ hạp khác nhau mà chúng ta có thể vái diễn vái hai bit là: 00, 01, 10, và 11. Chúng ta có thể liên kết mỗi tổ hợp này với mỗi phần tử riêng biệt của tập hợp khác. Khi đó chúng ta nói rằng mỗi phần tử “đại diện” cho một phần tử của tập hợp. Để mô tả một tập hợp có tám phần tử chúng ta chỉ cần ba bit ; đ ể mô tả 16 phần tử chúng ta cần bốn bit. Nếu số phần tử cần mô tả không phải là lũy thừa của hai thì mã nhị phân này sẽ có các các tổ hợp bít không xác định, vấn đề này được minh họa như sau. V Í DỤ 1.29 Có bao nhiêu bit cần dể mô tả số 10 trong chữ số thập phân? Bởi vỉ 23 < 10 < 24 do đó giá trị nhỏ nhất của bít đề mô tả số 1 = 4. Tuy nhiên, vì 2J = 16, do đó có 6 (=16 - 10) tổ hợp có 4 bit I được gán vào m ột số thập phân riêng biệt. — ---------— — -------------- --------------------- 78 Chapter 1: Basic Concepts of Computers 1.8.3.1 Cóc m ã tă n g trọng Để mô tả các chữ số thập phân bằng cách sử dụng bôn bit các mã phổ biên nhất là các mã tăng trọng. Trong loại mã này mỗi bit được gán cho một “trọng lượng”. Giá trị của mỗi chữ sô thập phăn được trình bày theo tổ hạp của các bit được xác định bàng cách nhăn mồi bit này c 10 trọng lượng của nó và cộng các tích riêng biệt này lại. Nêu w }, w2, w3 và w4 tương ứng với trọng lượng của các bít bt, b2, b3 và b t sau đo lsổ thập phân N được trình bày là N =uìtb2 + w2b2 + w3b3 + w4b4 Một chuỗi số nhị phân mô tả cho một số thập phăn được gọi là một mã từ. Bảng 1.5 trình bày hai mã nhị phân, mã này với trọng lượng 8, 4, 2 và 1 được biết như là mã BCD (Binary-Coded-Decimal). Mỗi mã từ trong BCD là một sô nhị phân tương ứng với số mà nó hiền thị. B ả n g 1.5 Bảng trình bày số thập phân từ 0 - 9 theo hai mã tăng trọng khác nhau Sô thập p hán Trọng lượng 8-2-4-1 T rọ n g lượng 2-4-1-2 0 0000 0000 1 000 1 0 0 0 1 2 0 0 10 0 0 1 0 3 0 0 11 0 0 11 4 0 10 0 0 10 0 5 0 10 1 1 0 11 6 0 1 1 0 1100 7 0 1 1 1 110 1 8 1000 1110 9 10 0 1 1111 V/ D Ụ 1.30 Trong mã 24-2-1, phần mô tả của sô thập phân 9 được cho ià 1111. Lưu ý rằng. 1*2+ 1*4+ 1*2 + 1*1 = 9 Diùư thú vị khi quan sát các n ã này là cách trinh bày của các sô tháp phân có thể không giông nhau. Hãy xeiti mã 2-4-2-1 chúng ta có thể trình bày sô thập phân 7 theo hai cách khác nhau: 1*2 + 1*4+ 0*2 + 1*1 = 7 và 0*2 +1*4 + 1*2 + 1*1 = 7 Có hai cáu hỏi quan tăm đến việc cách trình bày kép (dual) của môt chữ sô. Trước tiên, làm cách nào máy tính nhận ra mã nào là đúng? Câu hỏi thứ hai cả hai cách này có thề được dùng thay thế cho nhau Chương 1: Các khải niệm cơ bản về máy tính 79 không? Cău trả lời cho câu hỏi thứ hai là không. Chỉ có một mã từ mới dược dùng. Điều này không phải là cảu trả lời cho hai mã từ chỉ một cái đúng. Để trả lời thỏa dáng câu hỏi này, chúng ta cần phải định nghĩa khái niệm của một mã tự bù (self-complementing code). Một mã được gọi là tự bù nếu cho bất kỳ số thập phán N nào và có mã từ tương ứng X12X22X32X42, thì giá trị của 9 - N (phần bù 9 của sô thập phân này có thể xác định) bằng cách lấy phần bù theo các bit của mă từ. Chúng ta sẽ sử dụng khái niệm X để chi ra phần bù của X. V Í DỤ 1.31 Mã 2-4-2-1 là phần bù của chính nó. Lưu ý rằng trong mã này phần bù 9 cửa bất kỳ sô thập phân nào có thể được tính bàng cách lấy bù của các bít của các mã từ tương ứng, M ièu tả của 9 - N trong T h ậ p p h â n (N) 2-4-2-1 9 - N 2-4-2-1 0 0000 9 1111 1 000 1 8 1110 2 00 10 7 110 1 3 0 0 11 6 1 1 0 0 4 0 10 0 5 10 11 5 10 11 4 0 1 0 0 6 1 1 0 0 3 0 0 11 7 110 1 2 00 10 8 1 1 1 0 1 0 0 0 1 9 , 1 1 1 1 9 0 0 0 0 1.8.3.2 Mã theo tiêu chuẩn Mỹ đối vái các thông tin trao đổi Máy tính cũng được sử dụng rộng rãi để xử lý các thông tin số. Để thực hiện nhiệm vụ này, phương pháp phổ biến nhất là mã hóa các ký tự dặc biệt vốn cần được xử lý. Trên một bàn phím thông thường, tiếng Anh có ít nhất là 128 ký tự khác nhau. Các con số: 10 Mẫu tự (in hoa và thường): 52 Các ký hiệu đặc biệt: 33 bao gồm !, @, #, 2, %, A, &, * (,) v,v... Các ký tự điều khiển: 33 bao gồm Enter, space, backspace, v,v... 128 Số bit nhỏ nhất cần đ ể mô tả những ký tự này là 7 do đó 27 = 128 (xem phần 1.8.3). Mã 7 bit này là mã phổ biến nhất trong máy tính được biết như là mả tiêu chuẩn Mỹ cho trao đổi thông tin hoặc tên tắt 80 Chapter 1ữ. Basic Concepts of Computers là ASCII. Tuy nhiên, bởi vi đơn vị ca bản của việc lưu trữ là byte. Do đó, toàn bộ mã ASC II được biểu diễn bàng cách sử dụng 8 bít. Điêu này cho phép hầu hết các bit biểu thị là zero. Mã khác được sử dụng rộng rãi bởi tập đoán International Business Machines là Extended Binary Coded Decimal Interchange Code hoặc EBCDIC. Trong sách này chúng ta sẽ xem xét mã ASCII. Tập hợp của các ký tự A SC II được minh họa ở chương 3. Mă ASCII được phát triển bởi viện tiêu chuẩn quốc gia Mỹ (ANSI) để cho phép trao đổi thông tin giữa thiêt bị được tạo bởi nhiều nhà sản xuất khác nhau. VÍ DỤ 1.32 Mã ASCII mô tả thông điệp “hello World.” là g ì? Giả sử ràng địa chỉ đó tăng từ trái sang phải. Một chuỗi các ký tự được mô tả trong bộ nhá là một chuỗi các byte liên tục. Mỗi by chứa một mã ký tự bất kỳ. Sử dụng biểu đồ trong chương 3 và giá trị thập lục phân tương đương của mỗi ký tự thông diệp này được trình bày là H e 1 l o World 48 65 6C 6C 6F 20 57 6F 72 6C 64 N hận xét ràng ký tự trống (hex 20 hoặc decim al 32) là m ột kỷ tự giống như bất kỳ ký tự khác. Tuy nhiên, người đọc sẽ cảm thấy ký tự này rắc rố, đăy là m ột ký tự rất khó p h á n biệt. Chúng ta cụng có th ể giả sử ràng địa chỉ tăng từ trái sang phải đ ể thuận tiện trong việc đọc các ký tự. 1.8.4 Dò tim lỗi Khi dữ liệu nhị phân được truyền lên bất cứ kiểu đường dây truyền thông nào, thì khả năng có một lỗi khi truyền luôn luôn xảy ra do hỏng thiết bị hoặc do bởi sự hiện diện của “tiếng ồn”. Khi xảy ra lỗi thì có thể rằng có một hoặc nhiều bít của một byte thay đổi từ 0 đến 1 hoặc ngược lại. Bất cứ lúc nào điều này xảy ra thì một mã từ có thể thay đổi thành một mã không đúng nhưng vẫn có hiệu lực hoặc thành một chuỗi các bít không hiện diện ở bât cứ nơi nào. Trong sách này chúng ta chỉ quan tâm những dò tìm và chỉnh sửa các lỗi đơn có nghĩa ràng các lỗi mà ở đó chỉ có một là thay đổi. Sô các bít vòn thay đôi bên trong một byte trước khi byte được biến đổi sang một mã không có hiệu lực, dôi khi dùng làm một chuẩn mực để phân loại mã. Nêu chỉ có một bít cùa một byte cẩn thay đổi, thì mã này được gọi là mã tìm một lỗi. Nếu chỉ có hai bít cần phải thay đổi thi mã này được gọi là mã dò tìm hai lỗi. Để dò tìm các lỗi đan chúng ta sử dụng một bít kiểm tra chẩn lè (parity check) dư. Một bít chăn lè được dùng đê bảo đảm rằng mỗi mã từ phải có chứa từ bít chẩn lẻ nó có một số chẵn kiểu số 1 (gọi là được chẩn) hoặc một số lẻ cú kiểu số 1 (được lẻ). Bảng 1-6 minh họa bít chẵn ứng với mã dò tìm lỗi 8.2.4.1 Chương 1: Các khái niệm cơ bản về máy tính 81 B ảng 1-6 C hư số thập phân Trọng lượng 8 -2-41 Bit chăn lẻ 0 0000 0 1 0 0 0 1 1 2 0010 1 3 0 0 11 0 4 0 1 0 0 1 5 0 1 0 1 0 6 0 1 1 0 0 7 0 1 1 1 1 8 1000 1 9 100 1 0 Một trong những tác vụ quan trọng nhất mà chúng ta gặp phải trong bất cứ hệ thống máy tính nào đó là việc truyền thông tin từ máy tinh này sang máy tính khác. Các máy tính gửi thông tin được gọi là nguồn; các máy tính nhận thông tin được gọi là đích. Cả máy gửi và máy nhận đều tuân theo các tiêu chuẩn quốc tế để hoàn thành tác vụ này. Giả sử ràng tín hiệu được truyền được chia thành một chuỗi các đoạn 1 bít có chiều dài là T. trong suốt mỗi một đoạn này nguồn gửi hoặc một chữ 0 hoặc là một chữ số 1 (như minh họa trong hình 1-8 dưới dạng high và lows). Để giao tiếp giữa chúng, máy tính có thể tuân theo một quy ước giống như quy ước được minh họa trong hình 1.9. Đây là trách nhiệm của đích trong việc dò tìm giá trị và tính đúng đắn của tín hiệu nhận dược. Quy trình mà hai máy tính có thể sử dụng để giao tiếp với nhau có thể được mô tả như dưới đáy. Chúng ta sử dụng hình 1.9 làm ví dụ tham khảo. (1) Nếu máy nguồn hiện không gởi bất kỳ thông báo nào, thì nó tiếp tục truyền một chuỗi các sò 1. 1 0 1 1 0 1 0 1 H ìn h 1-8 Biểu diễn các số 1 và 0 ở dạng cao và thấp 82 Chapter 1: Basic Concepts of Computers Bít bát đầu byte đang được truyền bit chán lẻ b it d ừng 4 ị — ► H ìn h 1-9 Dạng byte tiêu biểu cho sự truyền dữ liệu (2) Một bít 0 cho biết phần đầu của thông điệp. Bit 0 thứ nhát này được gọi là bit bắt đầu. Người ta giả định ràng các byte hình thành nên thông điệp theo sau bít bắt dầu. (3) Bit kiểm tra tính chấn lẻ dược đặt theo qui ước về tính chẵn lè dang được sử dụng (chẵn hoặc lẻ) (4) Sau bit kiểm tra tinh chẳn lè, bit 1 khác (bít dừng) được truyền dể cho biết rằng việc truyền toàn bộ các byte đã được thực hiện hoàn tất. (5) Vào thời điểm này, máy nguồn có thể tiếp tục truyền byte kế tiếp hoặc nó có thể bát đầu truyền một chuỗi liên tục các sô 1 đ ể chi ra ràng không có thêm thông điệp nào nữa được truyền vào lức này. VI D Ụ 1.33 Hai máy tính giao tiếp với nhau bằng cách sử dụng quy ước dạng dữ liệu ở hình 1-9. bộ ký tự ASCII và tính chẵn, thông điệp như minh họa dưới đăy có một lỗi chẵn lẻ. Bằng cách nào máy tinh nhận ra rằng một lỗi xảy ra? Máy tính có thể báo vị trí của bít bổ sung hay không? giả sử rằng bít khởi động không được minh họa. M ũi tên chi ra chiều mà các ký tự cần phải được xem xét. 0101011001 0110100101 0110111101 0110110001 0110010101 0110010001 0111001111 0010000011 0110000111 0111001001 0110010101 0010000011 0110001011 0110110001 0111010111 0110010101 0010111001 Bằng cách sử dụng dạng hình 1-9 một chuỗi 10 bít, 1 byte 8 bít, 1 bít kiêm tra tính chăn lẻ và một bít ngưng có thể được xem xét dưới dạng băng cách trình bày một ký tự đơn của một thông điệp. Làm việc với môi nhóm các bít rời rạc rồi bỏ QUữ bít ngưng chúng ta. có th ể ngưng kiểm tra bít bên phải ngoài cùng bít chẵn lẻ như minh họa ở dạng in đậm dưới đây. 1. 010101100 ✓ 2. 01101001« ✓ 3. 011011110 ✓ 4 011011000 ✓ 5. 011001010 6. 011001000 * 7. 011100111 ✓ 8. 001000001 ✓ 9. 011000011 ✓ 10. 011100100 ✓ 11. 011001010 ✓ 12. 001000001 ✓ 13. 011000101 ✓ 14. 011011000 ✓ 15. OU1010U ✓ 16. 011001010 ✓ 17. 001011100 ✓