Lecture 4: Binary and Hexadecimal Number Systems



Binary and Hexadecimal Number Systems

A number system of base r, is a system that uses distinct symbols for r digits.

the decimal system (base 10) uses 10 digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

the binary system (base 2) uses 2 digits: {0 and 1}

the hexadecimal system (base 16) uses 16 digits:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}

The value of a number in base r is obtained by multiplying each digit by an integer power of r and adding all the weighted digits. For representations of positive integers, the rightmost digit has weight r0, the next digit has weight r1, the next digit has weight r2 and so on.

Examples:

Base 10: 1234 = 1X103 + 2X102 + 3X101 + 4X100

Base 2: 10010=1X24 + 0X23 + 0X22 + 1X21 + 0X20 = 16+0+0+2+0=(18)10

01101101= 0X27+1X26+1X25+0X24+1X23+1X22+0X21+1X20=

0+64+32+0+8+4+0+1 = (109)10

Base 16: 1A6 = 1X162 + 10X161 + 6X160 = 256+160+6 = (422)10

6D = 6X161 + 13X160 = 96 +13 = (109)10

Converting from positive decimal integer to binary/hexadecimal

The conversion of a decimal integer to binary is done by successive divisions by 2 and accumulation of the remainders. This gives the magnitude of the integer. Similarly, conversion of a decimal integer to hexadecimal is done by successive divisions by 16 and accumulation of the remainders.

Examples

[pic]

Converting between binary and hexadecimal (positive integers)

Each hexadecimal digit can be represented by a 4-bit binary number whose value is equal to that of the digit. To convert from hexadecimal to binary, simply replace each digit by the corresponding 4-bit binary number. To convert from binary to hexadecimal, divide the bits into groups of four (starting with the rightmost) and replace each 4-bit binary number by the corresponding hexadecimal digit. Additional 0's may be added to the left of the number.

For example

[pic]

2's complement arithmetic

In order to represent both positive and negative binary numbers, we must include a sign bit. This can be done by using the 2's complement representation as follows:

(i) For positive integers, simply put a 0 in front of the magnitude. For example, +29 = 0 11101, +87 = 0 1010111 and +142 = 0 10001110.

(ii) For negative integers, first obtain the corresponding positive integer and then negate it by inverting and adding 1. For example, the 2's complement representations for the decimal -29, -87 and -142 are given below.

[pic]

If we negate a negative number by inverting and adding 1, we will get back the original positive number.

[pic]

Rules for addition

• An n-bit number in 2's complement representation contains a total of n bits, including the sign bit. For example 1 0101001 is the 8-bit 2's complement representation of -87.

• When adding two n-bit numbers, the result should also be n bits. Any extra bits to the left are discarded.

• The position of the sign bit does not change.

• If after adding two positive numbers, the result is negative or after adding two negative numbers, the result is positive, then the corresponding result is invalid.

• Extra 0's may be added to the left of a positive number and extra 1's may be added to the left of a negative number without changing its value.

• Subtraction is equivalent to adding the negation (2's complement) of a number.

Examples:

[pic]

 

Multiplication in CRC arithmetic is straightforward as well. The steps for CRC multiplication are the same as in regular long multiplication, with two specific rules: We use OR (not XOR) operator and there are no carries. We are not using multiplication in CRC. However, here is an example of multiplication.

[pic]

The following example is actually a simple representation of a CRC. The remainder would be the actual checksum for the data.

[pic]

Polynomials

[pic]

Having reviewed CRC arithmetic, we can now choose a divisor that is to be used in the CRC calculation. The divisor in a CRC calculation is called the polynomial, or poly. In the case of CRCs, the poly is nothing more than a binary number. It gets its name because the number represents a polynomial with binary coefficients. For example:

1*(x7)+0*(x6)+0*(x5)+1*(x4)+1*(x3)+0*(x2)+1*(x1)+1*(x0) = 10011011

Polys come in various sizes. The more popular polys use 16 or 32 bit lengths. The length of a poly is determined by the position of the leftmost 1 bit.

There are many popular polys in use, or you can create your own. However, some polys are better at identifying errors or differences in data than others. With this in mind, it's a good idea to use one of the more time-tested polys than one you create.

A popular 32 bit polynomial is (0x04C11DB7), which is used in PKZip, Ethernet and FDDI. By searching on the Internet, you can find more polys that you can use in your CRCs.

Four versions of polynomials are widely used:

CRC-12 = X 12 + X 11 + X 3 + X 2 + X + 1

CRC-16 = X 16 + X 15 + X 2 + 1

CRC-CCITT = X 16 + X 12 + X 5 + 1

CRC-32 = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 +

X 5 + X 4 + X 2 + X + 1

Error:

An error E(x) will only be undetectable if it is divisible by P(X). It can be shown that all of the errors are not divisible by a suitably chosen P(x) and hence are detectable:

• All single-bit errors

• All double-bit errors, as long as P(x) has at least three 1s.

• Any odd number of errors, as long as P(x) contains a factor (X + 1)

• Any burst error for which the length of the burst is less than the length of the divisor polynomial; that is , less than or equal to the length of the FCs

• Most larger burst errors

How CRCs Work

[pic]

The purpose of error detection within file transfers is to notify the receiver that the message received is different than the message transmitted by the sender. A simple way to detect errors after a file transfer is to compare a checksum calculated before the transfer with a checksum that is generated after the transfer. The advantage of a CRC is that it is virtually impossible for a random change in a block of data to still generate the same checksum.

 

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download