Chapter 1 Data Representation & Digital Logic PDF

1 Chapter 1 Data Representation and Digital Logic ITP3901 OPERATING SYSTEMS FUNDAMENTALS  2 Data Representations  Values in digital systems consist of only 0 and 1.  A combination containing a single 0 or 1...

1 Chapter 1 Data Representation and Digital Logic ITP3901 OPERATING SYSTEMS FUNDAMENTALS  2 Data Representations  Values in digital systems consist of only 0 and 1.  A combination containing a single 0 or 1 is called a bit (Binary digit).  In general, n bits can be used to distinguish amongst 2n distinct entities.  Computers use lists of bits to represent numbers, letters, symbols, and other information. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  3 Alphanumeric Codes  An alphanumeric code is the assignment of letters and other characters to bit combinations.  These include letters, digits and special symbols.  ASCII: American Standard Code for Information Interchange. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  4 Alphanumeric Codes  7-bit to represent 128 different symbols including upper- case and lower-case letters, digits and special symbols, printable and non-printable.  8-bit extension uses the eighth bit to add error-detecting capability (parity check) for transferring codes between computers.  More details: http://www.asciitable.com/ Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  5 Double-byte Character Set  A double-byte character set (DBCS).  1 byte can represent 256 symbols.  2 bytes can represent up to 65,536 symbols.  Japanese, Korean and Chinese use DBCS.  Example: Big5, GBK and GB encoding for traditional and simplified Chinese Characters. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  6 Unicode  The Unicode is developed and maintained by the Unicode Consortium (https://home.unicode.org/ ).  It aims to be an encoding standard for handling data in ANY language.  UTF-8 is the dominant character encoding for World Wide Web (WWW).  NET/C# chose UTF-16 as the "native" encoding of Windows. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  7 Numbering System Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  8 Commonly used Numbering Systems  Binary number system (base 2), octal (base 8), and hexadecimal (base 16) number systems.  Computers only deal with binary numbers, the use of the octal and hexadecimal numbers is solely for the convenience of human people. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  9 Numbering Systems in Computer  Binary (Base 2)  e.g. 1011112  Octal (Base 8)  e.g. 168 (Digit with value 0 -7)  Hexadecimal (or Hex - Base 16)  ABCDEF16 (Digit with value 0 – F)  How to convert between different base? Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  10 Conversion from decimal to binary  Example:  Convert 345 (in decimal) to binary 345 MOD 2 = 1 (345/2 = 172) 172 MOD 2 = 0 (172/2 = 86 ) 86 MOD 2 = 0 (86/2 = 43 ) 43 MOD 2 = 1 (43/2 = 21 ) 21 MOD 2 = 1 (21/2 = 10 ) 10 MOD 2 = 0 (10/2 = 5 ) 5 MOD 2 = 1 (5/2 = 2 ) 2 MOD 2 = 0 (2/2 = 1 ) 1 MOD 2 = 1 (1/2 = 0 ) Ans: 1 0101 1001 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  Conversion from Binary, Octal, 11 Hexadecimal to Decimal - Power Series Example  Binary to Decimal: Convert 1 0101 10012 to decimal Decimal representation of 1 0101 10012 = 1 0 1 0 1 1 0 0 1 1 x 28 + 0 x 27 +1 x 26 + 0 x 25 + 1 x 24 + 1 x 23 + 0 x 22 + 0 x 21 + 1 x 20 = 34510 Example  Octal to Decimal: Convert 5318 (oct) to decimal Decimal representation of 5318 2 1 0 = 5 x 8 + 3 x 8 + 1 x 8 = 34510 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  12 Conversion from Binary to Octal Conversion from binary to oct 101 011 001 Binary to Octal 5 3 1 => 531 (oct) 000 0 001 1  By using 010 2 MOD 8 and 011 3 100 4 (MOD – find the remainder) 101 5 110 6 111 7 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  13 Conversion from Binary to Hexadecimal Binary to Hexadecimal  Conversion from binary to hex 0000 0 0001 1 1 0101 1001 0010 2 0011 3 1 5 9 => 159 (hex) 0100 4 0101 5 0110 6 0111 7  By using 1000 8 1001 9 MOD 16 1010 A (MOD – find the remainder) 1011 B 1100 C 1101 D 1110 E 1111 F Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  14 Conversion from decimal to octal or hexadecimal Example Convert 34510 to octal representation 345 MOD 8 = 1 (345/8 = 43) 43 MOD 8 = 3 (43/8 = 5 ) 5 MOD 8 = 5 Ans: 5318 Example Convert 34510 to hexadecimal representation 345 MOD 16 = 9 (345/16 = 21) 21 MOD 16 = 5 (21/16 = 1 ) 1 MOD 16 = 1 Ans: 15916 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  15 Negative numbers  Two approaches to represent negative binary number.  a signed bit to represent the positive or negative sign.  the complemented form (1’s or 2’s) of the positive number to represent a negative value. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  16 Sign bit representation  The Most Significant Bit (MSB) is used to represent the sign.  The number is positive if the sign bit is 0 and is negative if the sign bit is 1.  For example, 000001012 represents +00001012, or +510, while 100001012 means -00001012, or - 510.  Problem: 510 – 510 = 00001012 – 00001012  -10 = 000001012 + 100001012 10 = 10001010 2 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  17 Complement representation  Non-negative numbers are the same  The most significant bit still represents the sign.  Example: The 1's complement of 010011012: n = 8 (number of bits) 1’s complement of N = N'2 Toggle the number or 01001101 = (28 - 1) - N2  10110010 = (100000000 - 1) - 01001101 = 11111111 – 01001101 = 10110010 2 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  18 Complement representation  Or simply inverting (toggle) all binary digits.  For example, +510 in binary is 01012 Then, -510 in binary is 10102  Be careful ! There are two zeros. +0  000000002 -0  111111112 (Mathematically, zero is zero, there is no positive / negative zero) Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  19 8-bit 1’s complement integers 1's complement Bits Unsigned value value 0111 1111 127 127 0111 1110 126 126 0000 0010 2 2 0000 0001 1 1 0000 0000 0 0 1111 1111 255 −0 1111 1110 254 −1 1000 0010 130 −125 1000 0001 129 −126 1000 0000 128 −127 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  20 2’s complement  The 2’s complement, N"2, of an n-digit binary number, N2, is defined as: N"2 = 2n - N2 or Toggle the number + 1 01001101 = (2 - 1) - N2 + 1 n  10110010 + 1  10110011 = N’2 + 1  where N’2 is the 1’s complement representation of the number.  Or simply inverting (toggle) all binary digits and add one. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  21 8-bit 2’s complement integers 2's complement Bits Unsigned value value 0111 1111 127 127 0111 1110 126 126 0000 0010 2 2 0000 0001 1 1 0000 0000 0 0 1111 1111 255 −1 1111 1110 254 −2 1000 0010 130 −126 1000 0001 129 −127 1000 0000 128 −128 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  22 Subtraction Example: 93 - 65 93 – 65 ------------------------------- 01011101 (+93) (X) + 10111111 (-65) (28-Y) ------------------------------- 1 00011100 (+28) (X-Y) ↑ Overflow (28) Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  23 Subtraction Example: 65 - 93 65 – 93 --------------------- 01000001 (+65) + 10100011 (-93) --------------------- 11100100 (-ve)  toogle + 1 : 00011011 + 1 --------------------- 000111002 => +28 i.e. 111001002 is -2810 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  24 Floating-point numbers  To represent very large number or very small fractions.  Scientific notation: M  be, where M is the normalized mantissa; b the base and e the exponent.  Using decimal number as example: The Base, 10 for decimal, 2 for binary 4.56 can be written as 456 x 10-2 This part is an integer, Mantissa This part is another integer, we call it Exponent Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  25 Floating-point numbers The binary point is said to float, and the numbers are called floating-point numbers. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  26 Introduction to Digital Logic Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  27 What is logic gate?  Logic gates are the building blocks of digital circuits.  Combinations of logic gates form circuits designed for a specific task. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  28 Logic Gates  AND Gate  OR Gate  XOR Gate  NOT Gate  NAND Gate  NOR Gate Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  29 Logic Gate - AND  AND Gate (similar to ‘ * ‘) x, y are input, which are either TRUE (i.e. 1) or FALSE (i.e. 0). x y output 0 0 0 0 1 0 1 0 0 1 1 1 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  30 Logic Gate - OR  OR Gate ( similar to ‘ + ‘) x y output 0 0 0 0 1 1 1 0 1 1 1 1 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  31 Logic Gate - NOT  NOT Gate (Negated) Opposite to the input (or invert the input as the output) x output 0 1 1 0 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  32 Logic Gate - XOR  XOR Gate (Exclusive OR ⊕) Same as OR gate except when both input are 1, the output is 0. x y output 0 0 0 0 1 1 1 0 1 1 1 0 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  33 Logic Gate - NAND  NAND Gate (NOT + AND = NAND) With same input as AND gate but the output is negated. x y output 0 0 1 0 1 1 1 0 1 1 1 0 this circle means NOT Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  34 Logic Gate - NOR  NOR Gate (NOT + OR = NOR) The same input as OR gate but the output is negated. x y output 0 0 1 0 1 0 1 0 0 1 1 0 Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  Logic Gate – What you can 35 find in electronic components market Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  36 Integrated Circuits (IC) 12 13 8 1 2 Multiple chips (gates) combined to a circuit to solve a specific problem Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  37 One Bit Adder Consider the truth table of an one-bit adder: A B S C 0 0 0 0 S = A XOR B 0 1 1 0 C = A AND B 1 0 1 0 1 1 0 1 We then have: A S B C Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals  38 CPU Chips  The most important integrated circuit (IC) in any computer is the Central Processing Unit, or CPU. Chapter 1 - Data Representation & Digital Logic ITP3901 Operating Systems Fundamentals