Part 1

**Reference Books:**

**DATA STRUCTURES****Just as discovering to style programs is important, for this reason is theunderstanding that the correct format and also usage the data. Allprograms usage some kind of data. To style programs i m sorry workcorrectly, a an excellent understanding of exactly how data is structured will berequired. **

**This module introduces you come the various creates of data usedby programs. Us shall investigate how the data is stored,accessed and its common usage in ~ programs. **

**A computer system stores details in Binary format. Binary is anumber system which supplies BITS to save data. **

**BITS****A little bit is the smallest facet of info used by a computer.A little holds one of TWO possible values, **

You are watching: Ascii requires bits for each character

You are watching: Ascii requires bits for each character

Value | Meaning |

0 | OFF |

1 | ON |

A bit which is off is additionally considered to be FALSE or not SET;a little bit which is ~ above is likewise considered to be TRUE or SET.

Because a solitary bit have the right to only save two values, bits arecombined with each other into large units in order to host a greaterrange the values.

**NIBBLE****A nibble is a group of four bits. This offers a maximum number of16 feasible different values. **

** 2 ** 4 = 16 (2 come the strength of the number of bits)It is useful, when managing groups the bits, to determinewhich little of the team has the the very least value, and also which bit has actually themost or greatest value. **

**The Least far-reaching Bit and The many Sigificant Bit****This is reputed to be little 0, and is always drawn in ~ the extremeright. The Most far-ranging bit is always shown ~ above the extremeleft, and also is the little with the greatest value. **

**The diagram below shows a NIBBLE, and also each bits position anddecimal weight value (for more information, top the module onNumber Systems). **

** 3 2 1 0 bit Number +---+---+---+---+ | | | | | +---+---+---+---+ 8 4 2 1 Decimal Weighting value MSB LSBLets consider an example of converting binary values intodecimal. **

** little bit 3 2 1 0 value 1 0 1 1 little 3 is set, therefore it has a decimal weight worth of 8 little bit 2 is no set, so it has actually a decimal weight value of 0 bit 1 is set, therefore it has actually a decimal weight value of 2 bit 0 is set, therefore it has a decimal weight worth of 1 adding up every the decimal weight values for each bit= 11 so 1011 in binary is 11 in decimal!For much more examples, top the module on Number Systems. **

**BYTES****Bytes space a grouping of 8 bits. This comprises 2 nibbles, asshown below. **

** 7 6 5 4 3 2 1 0 little Number +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ 128 64 32 16 8 4 2 1 Decimal Weighting value MSB LSBBytes are often used to store CHARACTERS.They can likewise be provided to save numeric values, **

** 0 come 255 -127 come +128**

**Binary Coded Decimal **

**Binary code decimal digits (0-9) are stood for using four bits.The valid combinations of bits and their particular values are**

Binary value | Digit |

0000 | 0 |

0001 | 1 |

0010 | 2 |

0011 | 3 |

0100 | 4 |

0101 | 5 |

0110 | 6 |

0111 | 7 |

1000 | 8 |

1001 | 9 |

The binary combine 1010 come 1111 space invalid and also are notused.

If the computer system stores one BCD digit per byte, that callednormal BCD. The unused nibble might be either all 0"s or all 1"s.

**If 2 BCD digits are stored per byte, its dubbed PackedBCD**. This wake up in data transmission wherein numbers room beingtransmitted over a communications link. Packed BCD to reduce theamount the time spent transmitting the numbers, together each data bytetransmitted outcomes in the sending out of 2 BCD digits.

Consider the save on computer of the digits 56 in packed BCD format.

7 6 5 4 3 2 1 0 bit Number +---+---+---+---+---+---+---+---+ | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | +---+---+---+---+---+---+---+---+ MSB LSBThe upper nibble holds the value 5, whilst the lower nibbleholds the worth 6.

**Status and Boolean Variables****BOOLEAN variables use a solitary bit to hold their value, so canonly assume one of two feasible states. This is one of two people 0(considered to it is in FALSE), or 1 (considered to it is in TRUE). **

**The computer system handles each boolean variable together a single bit. Ifthe little bit is TRUE, then is has actually a value of 1. If the little is FALSE,then it has the value 0. **

**When a team of bits room grouped together to form a limitedrange of values, this is well-known as a STATUS** variable.

Consider the instance in a regime where we need to keep monitor ofthe number of minutes a phone line is busy for (within thelimited selection of 0 come 60). This does not need the usage of afull integer, so part programming languages enable you come specifythe variety of bits provided to allocate to variables v limitedranges.

The benefit of this approach, is the the storage room ofstatus variables deserve to be merged together right into a single 16 or 32bits, leading to a conserving of space.

Consider where a computer system allocates 16 bits of storage perstatus variable. If we had actually three condition variables, the spaceconsumed would be 48 bits. BUT, if every the standing variables couldbe an unified and fitted into a single 16 bits of storage, we couldsave 32 bits of memory. This is very important in real-timesystems where memory an are is in ~ a premium.

Consider the adhering to diagram, which illustrates the packingof boolean and status variables together into a single byte.

7 6 5 4 3 2 1 0 little Number +---+---+---+---+---+---+---+---+ | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | +---+---+---+---+---+---+---+---+ | | | | | | | +--- regional call/TOLL call (bit 0) | | +------- expansion busy/free (bit 1) | +------------------- minutes (bits 2-4) +----------------------- expansion diverted/TRUE/FALSE

**The American traditional Code for info Interchange****ASCII is a computer system code which supplies 128 various encodingcombinations of a team of 7 bits (27 = 128) come represent, **

**personalities A to Z, both upper and also lower situation distinct characters, numbers 0 to 9 special manage codes supplied for device control**

Lets now look in ~ the encoding method. The table below showsthe bit combinations required for each character.

00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F | |

00 | NUL | SOH | STX | ETX | EOT | ENQ | ACK | BEL | BS | TAB | LF | VT | FF | CR | SO | SI |

10 | DLE | DC1 | DC2 | DC3 | DC4 | NAK | SYN | ETB | CAN | EM | SUB | ESC | FS | GS | RS | US |

20 | ! | " | # | $ | % | & | " | ( | ) | * | + | , | - | . | / | |

30 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | : | ; | ? | |||

40 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | |

50 | P | Q | R | S | T | U | V | W | X | Y | Z | < | \ | > | ^ | _ |

60 | ` | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o |

70 | p | q | r | s | t | u | v | w | x | y | z | ~ | DEL |

See more: What Is The Name Of The Two Receiving Chambers Of The Heart Flashcards

A computer system usually stores information in eight bits. Theeighth little bit is unused in ASCII, hence is normally set to 0. Somesystems may use the eight little to implement graphics or differentlanguage symbols, ie, Greek characters.

**Control password are supplied in communications and also printers. Theymay be generated from an ASCII key-board by holding under the CTRL**(control) an essential and pushing another vital (A to Z, plus {, \, >, ^,Example code the text string "Hello." in ASCII usinghexadecimal digits.

H = 48 e = 65 together = 6C l = 6C o = 6F . = 2Ethus the cable is stood for by the byte succession

48 65 6C 6C 6F 2E

**CHARACTERS****Characters room non-numeric symbols supplied to convey language andmeaning. In English, lock are an unified with other characters toform words. Examples of personalities are; **

** a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H i J K together M N O p Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 ! # $ % ^ & * ( ) _ - = + | \ ` , . / ; " < > : " ? A computer system system normally stores characters using the ASCIIcode. Each character is stored utilizing eight bits that information,giving a total variety of 256 different characters (2**8 = 256). **

**In the high level language Pascal, personalities are identified andused as follows, **

** var plus_symbol : char; begin plus_symbol := "+"; Variables offered in a Pascal routine are asserted after thekeyword var**. The over example declares the change plus_symbolto be a personality type, therefore eight bits of storage storage areallocated to keep its value (as yet undetermined).

Inside the main body that the program, after ~ the keyword **begin**,the statement presented assigns the symbol **+** come the charactervariable plus_symbol. This is equivalent to save on computer theASCII worth 2B hexadecimal in the eight bits of storage allocatedto the change plus_symbol.

**TEXT STRINGS****Text strings space a succession of personalities (ie, native or multi-character symbols). Every character is stored one after the other,each occupying eight bits of storage storage. **

**The message string Hello would certainly be save on computer as adheres to **

** +------+ | 48 | +------+ | 65 | +------+ | 6C | +------+ | 6C | +------+ | 6F | +------+ In Turbo Pascal, message strings room defined and used as follows,**

** var text_message : string<22>; begin text_message := "Welcome to message strings"; The over example declares the change text_message to it is in astring form of up to 22 personalities long (but no more!). Eightbits of memory storage room allocated to keep each personality inthe cable (a total of 22 bytes), through the value in every byte asyet undetermined. **

**Inside the main body that the program, after the keyword begin,the statement shown assigns the article Welcome to textstrings come the string variable text_message. Thisstores the ASCII value of every character right into each successivebyte of memory allocated come the variable text_message**.

**INTEGERS ****Numeric info cannot efficiently be stored making use of the ASCII format. Imagine storing thenumber 123,769 utilizing ASCII. This would certainly consume 6 bytes, and also itwould be challenging to phone call if the number was positive or negative(though we could precede it with the character + or -). **

**A an ext efficient method of storing numeric details is come usea various encoding scheme. The encoding scheme in most use isshown below, **

** Bits** 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +---+--------------------------------------------+ | S | Numeric value in Binary |+---+--------------------------------------------+ S = Sign bit Integers store totality numbers only! They do not containfractional parts. Take into consideration the examples below,

**ValidInvalid **123.987 00.0 278903123.09 The sign little bit (which is little 15) suggests whether the number ispositive or negative. A logic 1 shows negative, a reasonable 0indicates positive.

The number is converted to binary and stored in bits 0 come 14of the two bytes.

**Example** save the value +263 as an essence value. 1) The sign bit is 0. 2) The decimal value +263 is 100000111 in binary. Thus the storage in storage of the integer +263 watch like, Bits 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +---+---------------------------------------------+ | 0 | 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 | +---+---------------------------------------------+ once storing negative numbers, the number is stored using thetwo"s complement format.

In Pascal, integers are defined and also used together follows,

var whole_number : integer; start whole_number := 1267; The instance declares the variable whole_number to be aninteger type, therefore sixteen bits of memory storage room allocatedto store its value (as yet undetermined).

Inside the main body that the program, after ~ the keyword **begin**,the statement shown assigns the numeric worth 1267 come the integervariable whole_number. This is equivalent to save on computer thebit mix 0000010011110011 in the 16 bits of memoryallocated to the change whole_number.

Signed integers using 16 bits have a number range of,

-32768 come +32767 (+-2^15) come store bigger integer worths would require an ext bits. Somesystems and languages likewise support the usage of unsigned integers,which are reputed to be positive only.

**FLOATING allude NUMBERS****There are two troubles with integers; they cannot expressfractions, and the range of the number is minimal to the numberof bits used. An efficient way of storing fractions is called thefloating allude method, i m sorry involves splitting the fraction intotwo parts, one exponent and also a mantissa. **

**The exponent to represent a value elevated to the power of 2. **

**The mantissa to represent a fractional value in between 0 and also 1. **

**Consider the number **

** 12.50 The number is very first converted right into the layout **

** 2n * 0.xxxxxx whereby n **represents the exponent and 0.xxxxx is themantissa.

The computer industry agreed upon a traditional for the storageof floating suggest numbers. It is referred to as the IEEE 754 standard,and offers 32 bits of memory (for single precision), or 64 bits(for twin precision accuracy). The single precision formatlooks like,

Bits 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +---+-----------------------+---------------------------------------------------------------------+ | S | Exponent value | Mantissa worth | +---+-----------------------+---------------------------------------------------------------------+ S = Sign bit The sign little is 1 for a an unfavorable mantissa, and 0 because that apositive mantissa.

The exponent provides a bias of 127.

The mantissa is stored as a binary value using an encodingtechnique.

**Working out the FP little patterns****The number we have actually is **

**12.5 i beg your pardon expressed as fraction to the strength of 2 is, **

** 12.5 / 2 = 6.25 6.25 / 2 = 3.125 3.125 / 2 = 1.5625 1.5625 / 2 = 0.78125 NOTE: Keep separating by 2 it spins a fraction between 0 and 1results. The portion is the mantissa value, the number ofdivisions is the exponent value. **

**thus ours values currently are, **

** 0.78125 * 24 The exponent little bit pattern is stored using an overabundance of 127.This means that this value is added to the exponent as soon as storing(and subtracted once removing). **

**The exponent little pattern to keep is, **

** 4 + 127 = 131 = "10000011" together the mantissa is a confident value, the sign bit is 0. **

**The mantissa is a little more facility to occupational out. Eachbit to represent 2 come the strength of a an unfavorable number. That lookslike, **

** 1st bit of mantissa = 0.5 2nd = 0.25 3rd = 0.125 fourth = 0.0625 fifth = 0.03125 and so on The mantissa number worth we have actually is 0.78125, which in binaryis **

**11001000000000000000000(0.5 + 0.25 + 0.03125) How-ever, to do matters even more complicated, the mantissais normalized, by relocating the bit patterns come the left (each shiftsubtracts one from the exponent value) it spins the an initial 1 dropsoff. **

**The resulting sample is then stored. **

**The mantissa now becomes **

** 10010000000000000000000 and also the exponent is changed to come to be **

** 131 - 1 = 130 = "10000010" The final assembled style is, **

** Bits 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+-----------------------+---------------------------------------------------------------------+ | 0| 1 0 0 0 0 0 1 0| 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | +--+-----------------------+---------------------------------------------------------------------+ S Exponent Mantissa currently lets convert the adhering to storage format ago into adecimal number. **

** Bits 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 +--+-----------------------+---------------------------------------------------------------------+ | 1| 1 0 0 0 0 0 1 1| 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | +--+-----------------------+---------------------------------------------------------------------+ S Exponent Mantissa This provides a an unfavorable number with an exponent value of, **

** 131 - 127 = 4 and also a mantissa worth of, **

** 1.0 + 0.5 + 0.0625 = 1.5625 (the 1.0 originates from the little bit which to be shifted off when themantissa was normalized ), for this reason the number is, **

** -1.5625 * 24 = -25.0 The numeric range for floating suggest numbers making use of theIEEE-754 method, utilizing 32 bits, is **

** +- 0.838860808 * 2-128 come +- 0.838860808 * 2127 or, in decimal, **

** 2.4652 * 10-39 come 1.4272 * 1038 In Pascal, floating point numbers space defined and also used asfollows, **

**var fp_number : real; start fp_number := 12.50; The example declares the change fp_number to be afloating- allude type, hence thirty-two bits of memory storage areallocated to store its value (as however undetermined). **

**Inside the main body of the program, after the keyword begin**,the statement presented assigns the numeric worth 12.50 to the realvariable fp_number. This is equivalent to save the bitcombinations 01000001010010000000000000000000 in the thirty-twobits of storage allocated to the change fp_number.

The benefits of save on computer floating suggest numbers in this wayare,

multiplication is perform by adding exponents and mantissa"s division is carry out by subtracting exponents and also mantissa"s it is straightforward to compare 2 numbers to watch which is the better or lesser large number varieties are stored making use of relatively couple of bitsThe flaw of the storage format are,

errors are developed by relocating the mantissa bits conversion backwards and forwards bring away time