Computer Organization & Articture No. 6 From Apcoms

Data Representation in Computer Systems

Lecture 06

Signed Binary Numbers • In ordinary arithmetic a negative number is indicated by minus sign and positive number by plus sign. This is not possible in computers, because of hardware limitation computers must represent everything with binary digits. There are two methods to do this: – The signed magnitude convention uses the left-most bit to represent the sign (0 for positive and 1 for negative). – The signed complement system negates a number by taking its complement. • It could be either, 1’s complement representation • or 2’s complement representation.

Signed Magnitude Convention • The signed magnitude convention uses the left-most bit to represent the sign (0 for positive and 1 for negative). – The user determines whether the number is signed or unsigned – If the binary number is signed then the leftmost bit represents the sign and the rest of the bits represents the number – If the binary number is unsigned then the leftmost bit is the most significant bit of the number – For example: • 01001 can be considered as 9 (unsigned binary) or a +9 because the left most bit is zero. • On the other hand, the string of bits 11001 represents binary equivalent of 25 when considered as an unsigned number or as –9 when considered as signed number

Signed Complement System • The signed Complement System negative number is indicated by its complement (Complement of positive number) – Positive numbers always start with 0 (plus), its complement (representing negative number) will always start with 1 – Signed complement system can use either 1’s complement or 2’s complement. – For example: • +9 is represented only as 00001001 but –9 can be represented as: – 11110110 – 11110111

Signed 1’s complement representation Signed 2’s complement representation

Character Codes • Calculations aren’t useful until their results can be displayed in a manner that is meaningful to people. – We also need to store the results of calculations, and provide a means for data input. – Thus, human-understandable characters must be converted to computer-understandable bit patterns using encoding scheme.

• As computers have evolved, character codes have evolved. – Larger computer memories and storage devices permit richer character codes. – The earliest computer coding systems used six bits. – Binary-coded decimal (BCD) was one of these early codes used by IBM – BCD was extended to an 8-bit code, Extended Binary-Coded Decimal Interchange Code (EBCDIC). – EBCDIC codes supported upper and lowercase alphabetic characters, in addition to special characters, such as punctuation and control characters. • EBCDIC and BCD are still in use by IBM mainframes today.

Character Codes • The 7-bit ASCII (American Standard Code for Information Interchange) used as a replacement for 6-bit codes. – While BCD and EBCDIC were based upon punched card codes, ASCII was based upon telecommunications (Telex) codes. – ASCII was the dominant character code outside the IBM mainframe world.

• Many of today’s systems embrace Unicode, a 16-bit system that can encode the characters of every language in the world. – The Java programming language, and some operating systems use Unicode as their default character code.

• The Unicode codespace is divided into six parts. The first part is for Western alphabet codes, including English, Greek, and Russian.

Digital transmission • A computer is design to send information from one point to another • While designing a system two choices are offered: – Convert information to either a digital or analog signal

• Line coding is the process of converting binary data into digital signal – Voice, data, movies, numbers and pictures are stored in computer as binary data

Line coding technique convert the binary data into digital signal

Unipolar • Unipoar scheme is simplest, inexpensive to implement but obsolete in use – It provides the concept of encoding system

• In digital transmission voltage pulses are sent through a medium – Most encoding scheme uses to send one voltage level for zero, and another for one – The polarity of the pulse decides whether it is positive or negative

• Unipolar scheme uses only one polarity, that is assigned to one of the two binary states, normally the 1 – The other state is zero voltage

Unipolar encoding uses only one voltage level.

Unipolar encoding This scheme has two problems presence of dc component (average amplitude is non zero Lack of synchronization (if data contains long 1’s or 0’s)

I’s are encoded as a positive value 0’s are encoded as zero value

Polar • Polar encoding uses two voltage levels, one positive and one negative – Due to two voltage levels average voltage level on the line is reduced and the dc component problem is eliminated

Polar encoding uses two voltage levels (positive and negative).

Polar encoding • Nonreturn to zero (NRZ) the value of the signal is always either positive or negative, it is further categorized into: – NRZ-L (NRZ- level) the level of signal depends on the type of bit that it represents • A positive voltage means the bit is a 0 • The negative voltage means the bit is a 1 – The level of the signal is dependent on the state of the bit – The problem arise when long stream of 0 or 1s and the clock is not synch

In NRZ-L the level of the signal is dependent upon the state of the bit.

Polar encoding • NRZ-I (NRZ-invert) an inversion of the voltage level represents a 1 bit – It is a transition between positive and negative, not the voltage itself, represents a 1 bit – A 0 bit is represented by no change

In NRZ-I the signal is inverted if a 1 is encountered.

Return to Zero (RZ) • With the signal containing a stream of 1s and 0s, the receiver may looses the track of information contain in that signal – That is why a synchronization method was introduced as NRZ-I

• To ensure synchronization, there must be a signal change for each bit – The receiver can use these changes to buildup, updates and synchronize its clock – To accommodate change in each bit three signal values are required • Positive • Negative • zero

Return to Zero (RZ) • With Return to Zero (RZ) encoding, the three values to the signal can be assigned • With RZ signal changes not between bits but during each bit – Like NRZ-L, a positive voltage means a 1 and a negative voltage means 0 – With RZ , half way through each bit interval, the signal return to zero • 1 bit is represented by positive to zero • 0 bit is represented by negative to zero

RZ encoding 1 bit is represented by positive to zero 0 bit is represented by negative to zero Disadvantage: It requires two signal changes to encode 1 bit and therefore occupies more bandwidth Advantage: More effective

Manchester encoding • Also known as Manchester Phase Encoding (MPE) • It uses an inversion at the middle of each bit interval for synchronization and bit representation – A negative to positive transition represents binary 1 – A positive to negative transition represents binary 0

• By using the signal transition for dual purpose, this encoding scheme has the same level of synchronization as of RZ, but with two levels of amplitude

Manchester encoding A negative to positive transition represents binary 1 A positive to negative transition represents binary 0

Error Detection and Correction • It is physically impossible for any data recording or transmission medium to be 100% perfect 100% of the time over its entire expected useful life. – As more bits are packed onto a square centimeter of disk storage, as communications transmission speeds increase, the likelihood of error increases. – Thus, error detection and correction is critical to accurate data transmission, storage and retrieval.

• Types of errors – Single bit Error • Only one bit of a given data unit ‘ byte, character, or packet’ may changed from 1 to 0 or vice versa

– Single bit error are least likely in serial transmission • Noise must be of the duration of that bit which is rare

– Single bit error are most likely in parallel transmission • One of the line in the set is noisy will generate noise to one of the bit – The effect of single bit change is shown

Type of Error • Burst error: two or more bits in the data has changed • Effect is shown in the figure – Burst error does not necessarily occur in the consecutive bits – Length of the burst is measured from the first corrupted bit to last corrupted bit

• Most likely occur in serial transmission as the duration of the noise is normally longer than the bit on the medium – Number of affected bits depends on the data rate and duration of noise

Error Detection • The goal of error checking is – To correct the error

• For correction the error must first be detected – Error detection the first step to correct error

• Redundancy – Sending the data unit twice is one of the error detection method • The receiving device will receive both the units and a bit by bit comparison is done • The discrepancies would be discarded • Time consuming, double effort in transmission

• Instead of completely repeating all the bits, If some extra bit are appended with the data unit, this will address time and effort – This extra information attached with the data unit is known as the redundancy – As the extra bits are redundant and may be discarded

Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination. Redundancy

Types of redundancy checks

• Parity Check – The most common and economical method • a parity bit is added to every data unit so that the total number of 1s is even (or odd for odd-parity).

– Two sub parts are • Simple Parity Check: – One redundant bit “ Parity bit” is added to the data unit, to make the total number of 1s in the data unit even or odd

• Two dimensional Parity Check: – A block of bits are organized in a table parity bit is calculated on rows and column of the table

• CRC: – Based on binary division, the remainder is appended to the end of the data

Even-parity concept

Example 1 Suppose the sender wants to send the word world. In ASCII the five characters are coded as 1110111 1101111 1110010 1101100 1100100 The following shows the actual bits sent 11101110 11011110 11100100 11011000 11001001

Example 2 Now suppose the word world is received by the receiver without being corrupted in transmission. 11101110 11011110 11100100 11011000 11001001 The receiver counts the 1s in each character and comes up with even numbers (6, 6, 4, 4, 4). The data are accepted.

Example 3 Now suppose the word world is corrupted during transmission. 11111110 11011110 11101100 11011000 11001001 The receiver counts the 1s in each character and comes up with even and odd numbers (7, 6, 5, 4, 4). The receiver knows that the data are corrupted, discards them, and asks for retransmission. Simple parity check can detect all single-bit errors. It can detect burst errors only if the total number of errors in each data unit is odd.

Two dimensional Parity Check • A block of bits is organized in a table (rows and columns) – First calculate the parity bit for each data unit – Organize the data units into a table – Calculate the parity for each column to create a new row with one parity bit “ these will be the parity bit for whole block

• This method is useful to detect burst error – A redundancy of n bit can detect a burst error of n bits

Two-dimensional parity

Example 4 Suppose the following block is sent: 10101001 00111001 11011101 11100111 10101010 However, it is hit by a burst noise of length 8, and some bits are corrupted. 10100011 10001001 11011101 11100111 10101010 When the receiver checks the parity bits, some of the bits do not follow the even-parity rule and the whole block is discarded. 10100011 10001001 11011101 10101010 In two-dimensional parity11100111 check, a block of bits is

divided into rows and a redundant row of bits is added to the whole block.

Cyclic Redundancy Check (CRC) • Parity is based on binary addition, the CRC is based on binary division – Instead of adding bits to achieve a desired parity, the CRC remainder of the division is appended to the end of the data unit – CRC remainder is a result of a binary division of dividend with a predetermined divisor – The extra zeros (1 less than the divisor) are appended to the data unit – The remainder is appended to the data unit before – At the Receiver end the data unit is again divided with the same divisor • If 0 remainder no error • If remainder is non zero shows the error

Binary division in a CRC generator

Binary division in CRC checker