Sistem Digital : Sistem Bilangan I ( Sistem Desimal, Konversi Bilangan Biner, Representasi Heksadesimal )

Sistem Digital : Sistem Bilangan I ( Sistem Desimal, Konversi Bilangan Biner, Representasi Heksadesimal )

The Decimal System

System based on decimal digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to represent numbers. For example the number 83 means eight tens plus three :

83 = (8 * 10) + 3

The number 4728 means four thousands, seven hundreds, two tens, plus eight :

4728 = (4 * 1000) + (7 * 100) + (2 * 10) + 8

The decimal system is said to have a base, or radix, of 10. This means that each digit in the number is multiplied by 10 raised to a power corresponding to that digit’s position:

83 = (8 * 10^1) + (3 * 10^0)

4728 = (4 * 10^3) + (7 * 10^2) + (2 * 10^1) + (8 * 10^0)

Decimal Fractions

The same principle holds for decimal fractions, but negative powers of 10 are used. Thus, the decimal fraction 0.256 stands for 2 tenths plus 5 hundredths plus 6 thousandths :

0.256 = (2 * 10^-1) + (5 * 10^-2) + (6 * 10^-3) 

A number with both an integer and fractional part has digits raised to both positive and negative powers of 10 :

442.256 = (4 * 10^2) + (4 + 10^1) + (2 * 10^0) + (2 * 10^-1) + (5 * 10^-2) + (6 * 10^-3)

Most significant digit

The leftmost digit (carries the highest value)

Least significant digit

The rightmost digit

Positional Interpretation of a Decimal Number

Positional Number Systems

Each number is represented by a string of digits in which each digit position i has an associated weight ri, where r is the radix, or base, of the number system. The general form of a number in such a system with radix r is

( . . . a_3a_2a_1a_0.a_-1a_-2a_-3 . . . )r

where the value of any digit ai is an integer in the range 0 < ai < r. The dot between a_0 and a_-1 is called the radix point.

Positional Interpretation of a Number in Base 7

The Binary System

Only consists two digits, 1 and 0. Binary represented to the base of 2. The digits 1 and 0 in binary notation have the same meaning as in decimal notation :

0_2 = 0_10

1_2 = 1_10

To represent larger numbers each digit in a binary number has a value depending on its position :

10_2 = (1 * 2^1) + (0 * 2^0) = 210

11_2 = (1 * 2^1) + (1 * 2^0) = 310

100_2 = (1 * 2^2) + (0 * 2^1) + (0 * 2^0) = 410

and so on. Again, fractional values are represented with negative powers of the radix :

1001.101 = 2^3 + 2^0 + 2^-1 + 2^-3 = 9.62510

Converting Between Binary and Decimal

Binary Notation to Decimal notation :

Multiply each binary digit by the appropriate power of 2 and add the results

Decimal notation to binary notation :

Integer and fractional parts are handled separately

Integers

For the integer part, recall that in binary notation, an integer represented by

b_m-1b_m-2 . . . b_2b_1b_0

 b_i = 0 or 1

has the value

(b_m-1 * 2^m-1) + (b_m-2 * 2^m-2) + . . . + (b_1 * 2^1) + b_0

Suppose it is required to convert a decimal integer N into binary form. If we divide N by 2, in the decimal system, and obtain a quotient N_1 and a remainder R_0, we may write

N = 2 * N_1 + R_0 // R_0 = 0 or 1

Next, we divide the quotient N_1 by 2. Assume that the new quotient is N_2 and the new remainder R_1. Then :

N1 = 2 * N2 + R1 // R1 = 0 or 1

so that

N = 2(2N_2 + R_1) + R_0 = (N_2 * 2^2) + (R_1 * 2^1) + R_0

Because N >N_1 > N_2 . . . , continuing this sequence will eventually produce a quotient N_m-1 = 1 (except for the decimal integers 0 and 1, whose binary equivalents are 0 and 1, respectively) and a remainder R_m-2, which is 0 or 1. Then :

N = (1 * 2^m-1) + (R_m-2 * 2^m-2) + . . . + (R_2 * 2^2) + (R_1 * 2^1) + R_0

Which is the binary form of N. Hence, we convert from base 10 to base 2 by repeated divisions by 2. The remainders and the selesai quotient, 1, give us, in order of increasing significance, the binary digits of N.

Examples of Converting from Decimal Notation to Binary Notation for Integers

Fractions

Number with a value between 0 and 1 is represented by

0.b_-1b_-2b_-3 . . . b_i = 0 or 1

and has the value

(b_-1 * 2^-1) + (b_-2 * 2^-2) + (b_-3 * 2^-3) . . .

This can be rewritten as

2^-1 * (b_-1 + 2^-1 * (b_-2 + 2^-1 * ( b_-3 + . . . ) . . . )

Suppose we want to convert the number

F (0 < F < 1) from decimal to binary notation. We know that F can be expressed in the form

F = 2-1 * (b-1 + 2-1 * (b-2 + 2-1 * (b-3 + . . . ) . . . ))

If we multiply F by 2, we obtain,

2 * F = b_-1 + 2^-1 * (b_-2 + 2^-1 * (b_-3 + . . . ) . . . )

From this equation, we see that the integer part of (2 * F), which must be either 0 or 1 because 0 < F < 1, is simply b-1. So we can say (2 * F) = b-1 + F1, where 0 < F1 < 1 and where

F1 = 2-1 * (b-2 + 2-1 * (b-3 + 2-1 * (b-4 + . . . ) . . . ))

To find b−2, we repeat the process.

At each step, the fractional part of the number from the previous step is multiplied by 2. The digit to the left of the decimal point in the product will be 0 or 1 and contributes to the binary representation, starting with the most significant digit. The fractional part of the product is used as the multiplicand in the next step.

Examples of Converting from Decimal Notation to Binary Notation for Fractions

Hexadecimal Notation

Binary digits are grouped into sets of four bits, called a nibble. Each possible combination of four binary digits is given a symbol, as follows:

0000 = 0
0100 = 4
1000 = 8
1100 = C

0001 = 1
0101 = 5
1001 = 9
1101 = D

0010 = 2
0110 = 6
1010 = A
1110 = E

0011 = 3
0111 = 7
1011 = B
1111 = F


Because 16 symbols are used, the notation is called hexadecimal and the 16 symbols are the hexadecimal digits. Thus,

2C_16 = (2_16 * 16^1) + (C_16 * 16^0) = (2_10 * 16^1) + (12_10 * 16^0) = 44

Decimal, Binary, and Hexadecimal Table

The Reason on using Hexadecimal Notation

Sumber

http://informatika.unpar.ac.id/

Slide AOK : Sistem Bilangan

Sumber http://wikiwoh.blogspot.com

Sistem Digital : Sistem Bilangan Ii ( Representasi Bilangan Biner Negatif, Aturan Two's Complement, Dan Aturan Overflow )

Sistem Digital : Sistem Bilangan II ( Representasi Bilangan Biner Negatif, Hukum Two's Complement, dan Hukum Overflow )

Integer

In the binary number system arbitrary numbers can be represented with :

• The digits zero and one
• The minus sign (for negative numbers)
• The period, or radix point (for numbers with a fractional component)

For purposes of computer storage and processing we do not have the benefit of special symbols for the minus sign and radix point. Only binary digits (0,1) may be used to represent numbers.

Sign-Magnitude Representation

Contoh :

+18 = 00010010

-18 = 10010010

Representasi 0

+0 = 00000000

-0 = 10000000

Two's Complement Representation

Uses the most significant bit as a sign bit. It differs from sign-magnitude representation in the way that the other bits are interpreted.

Complements of Binary Numbers

1. 1’s complements
2. 2’s complements

1’s complement

Change all 1s to 0s and all 0s to 1s

2’s complement

Find 1’s complement and then add 1

Alternative Representations for 4-Bit Integers

Range Extension

Range of numbers that can be expressed is extended by increasing the bit length. In sign-magnitude notation this is accomplished by moving the sign bit to the new leftmost position and fill in with zeros. 

This procedure will not work for twos complement negative integers

• Rule is to move the sign bit to the new leftmost position and fill in with copies of the sign bit
• For positive numbers, fill in with zeros, and for negative numbers, fill in with ones
• This is called sign extension

Negation

Twos complement operation

Take the Boolean complement of each bit of the integer (including the sign bit)

Treating the result as an unsigned binary integer, add 1. The negative of the negative of that number is itself :

Negation Special Case 1

Negation Special Case 2

Addition

OVERFLOW RULE

If two numbers are added, and they are both positive or both negative, then overflow occurs if and only if the result has the opposite sign.

SUBTRACTION RULE

To subtract one number (subtrahend) from another (minuend), take the twos complement (negation) of the subtrahend and add it to the minuend.

Subtraction

Geometric Depiction of Twos Complement Integers

Multiplication Unsigned Binary Integers

Twos Complement Multiplication

Comparison

Sumber

http://informatika.unpar.ac.id/

Slide AOK : Representasi Bilangan

Sumber http://wikiwoh.blogspot.com

Sistem Digital : Algoritma Dalam Perkalian, Algoritma Perkalian Booth, Dan Pembagian

Sistem Digital : Algoritma dalam Perkalian, Algoritma Perkalian Booth, dan Pembagian

Perkalian

Pengali (Multiplier) dan yang dikalikan (Multiplicand) diload ke dalam 2 register (Q and M). Register ke-3, register A juga diharapkan dan di-inisialisasi 0. Ada juga sebuah 1-bit, register C yang di-inisialisasi 0, yang menyimpan carry bit yang dihasilkan dari penambahan.

Algoritma

Operasi perkalian sbb ( lihat algoritmanya di gambar )

• Control logic membaca bit dari multiplier, satu setiap saat. 
• Jika Q0 = 1, maka multiplicand ditambahkan ke register A dan hasilnya disimpan di register A, dengan C bit dipakai untuk overflow.
• Kemudian, semua bit dari register C, A dan Q digeser ke kanan 1 bit sehingga C bit ke An-1, A0 ke Qn-1 dan Q0 hilang.
• Jika Q0 = 0, maka tidak ada penambahan, hanya pergeseran yang dilakukan.
• Proses ini diulang untuk setiap bit dari multiplier (original)
• Hasil dari perkalian 2n bit diperoleh di dalam register A dan Q.

Contoh

Perkalian dengan Algoritma Booth

Perkalian twos complement sanggup dilakukan dengan algoritma Booth. Multiplier dan multiplicand ditempatkan pada register Q dan M. Ada sebuah register 1 bit yang secara logik ditempatkan pada LSB dari Q (Q0) darn register Q dan diberikan label Q-1. Hasil dari perkalian akan muncul di register A dan Q.

Algoritma Booth

• A dan Q-1 diinisialisasi 0. 
• Control logic akan meng-scan bit dari multiplier satu bit setiap saat. Jika setiap bit diperiksa, bit di kirinya juga diperiksa 
• Jika keduanya sama (1-1 atua 0- 0), semua bit dari register A, Q dan Q-1 digeser ke kanan 1 bit. 
• Jika kedua bit berbeda, 1-0, A dikurangi dengan M. Jika 0-1, A ditambahkan dengan M. 
• Kemudian, register A, Q dan Q-1 digeser ke kanan. 
• Pergeseran ke kanan, LSB dari A, yaitu An-1 tidak hanya digeser ke kanan (An-2) tetapi juga tinggal tetap di An-1. Ini yang disebut dengan arithmetic shift, sebab mempertahankan bit tanda.

Contoh 7x3 : Algoritma Booth

Pembagian ( of unsigned binary integers )

Perhatikan gambar, menunjukkan sebuah teladan pembagian bilangan binary integer unsigned ( tidak bertanda ).

Pertama, bit dari dividend (yang dibagi) diperiksa dari kiri ke kanan, hingga himpunan dari bit-bit menunjukkan sebuah bilangan yang lebih besar atau sama dengan divisor (pembagi); ini menyatakan bahwa divisor sanggup membagi bilangan.

Sampai tahapan tersebut, 0 ditempatkan di quetiont (hasil bagi) dari kiri ke kanan. Ketika bit-bit tersebut >= divisor, sebuah bit 1 ditempatkan pada hasil bagi dan divisor dikurangkan dari partial dividend. Hasil diacu sebagai partial remainder.

Pembagian terus dilakukan sebagai siklus, dimana pada setiap siklus bit komplemen dari dividend ditambahkan ke partial remainders hingga hasil lebih besar atau sama dengan divisor. Kemudian divisor dikurangkan dari bilangan untuk menghasilkan partial remainder baru.

Proses dilanjutkan terus hingga semua bit dari dividend habis.

Algoritma Pembagian

Gambar berikut, menunjukkan algoritma yang berkaitan dengan proses pembagian yang panjang tersebut.

• Divisor (pembagi) ditempatkan di register M, Dividend (yang dibagi) ditempatkan di register Q. Count = n (jumlah bit divisor)
• Setiap langkah, register A dan Q di-shift ke kiri 1 bit.
• M dikurangkan dari A untuk memilih apakah A membagi partial remainder (A < 0).
• Jika (A < 0?), Q0 memperoleh sebuah bit 0 dan M harus ditambahakan ke A (untuk restore) nilai sebelumnya. Jika sebaliknya (A > = 0), Q0 mendapat bit 1
• Count = count – 1 dan proses dilanjutkan sebanyak n langkah
• Pada akhirnya, quotient (hasil bagi) berada di register Q dan sisa bagi berada di register A

Proses jalannya algoritma pembagian

Jalannya algoritma

Algoritma mengasumsikan bahwa divisor V dan dividend D yakni positif dan |V| < |D|. Jika |V| = |D|, maka quotient Q = 1 dan sisa baginya (remainder) R = 0. Jika |V| > |D|, maka Q = 0 dan R = D. 

Algoritma berjalan sebagai berikut :

• Load bentuk twos complement dari divisor ke register M; yaitu register M yang berisi negatif dari divisor. Load dividend ke register A dan Q. Dividend harus diekspresikan sebagai 2n-bit bilangan positif. Contohnya: 4 bit 0111 menjadi 00000111 
• Shift A, Q ke kiri 1 posisi bit 
• Lakukan A = A – M. 
• Jika hasilnya yakni nonnegatif (MSB dari A = 0) maka Q0 ß 1; Jika hasilnya negatif (MSB dari A = 1), maka Q0 ß 0 dan lalu nilai A dikembalikan ke semula (A = A + M) 
• Ulangi langkah 2 hingga 4 sebanyak posisi bit di Q 
• Sisa bagi di A dan hasil bagi di Q

Sumber http://wikiwoh.blogspot.com

Sistem Digital : Sistem Bilangan Iii ( Representasi Floating-Point Dengan Single Precision )

Sistem Digital : Sistem Bilangan III ( Representasi Floating-Point dengan Single Precision )

Floating-Point Representation

Principles

With a fixed-point notation it is possible to represent a range of positive and negative integers centered on or near 0. By assuming a fixed binary or radix point, this format allows the representation of numbers with a fractional component as well

Limitations :

• Very large numbers cannot be represented nor can very small fractions
• The fractional part of the quotient in a division of two large numbers could be lost

Typical 32-Bit Floating-Point Format

Floating-Point

The selesai portion of the word. Any floating-point number can be expressed in many ways

Normal number

The most significant digit of the significand is nonzero

Untuk lebih sederhana operasi bilangan floating point perlu di normalkan. Bilangan normal yaitu dimana MSB dari significand yaitu nonzero. Untuk representasi binary, normal number yaitu MSB dari significand yaitu 1. 

Berikut bentuk normal nonzero number

Dimana b yaitu digit biner ( 0 atau 1)

MSB selalu 1, alasannya yaitu itu tidak perlu disimpan (secara implisit). Kaprikornus secara implisit, 23 bit untuk menyimpan 24 bit significand. Sehingga nilainya berada di antara dan sama dengan 1 s/d < 2.

Contoh bentuk yang dinormalkan

Format 32-bit floating point

Sign disimpan pada bit pertama (dari 32 bit). Bit pertama dari significand yaitu 1 dan tidak perlu disimpan pada field. Nilai 127 ditambahkan pada true exponent untuk disimpan di field exponent – disebut biased exponent representation 

Base yaitu 2 

E = exponent 

S = Significand

Contoh

Binary 1011010010001 

Dibentuk normal 1.011010010001 * 212 

Format 32 bit 

Sign = 0 (positif) 

Biased = 12 + 127 = 10001011 

Significand/Mantissa (Fractional) = 011010010001 

Bentuk floating pointnya dalam format 32

Floating Point 32 bit ke Decimal

1 10010001 10001110001000000000000 

Sign = 1 ( negative )

Exponent = 10010001 => 145 

Bilangan = (-1)1 (1.10001110001)(2145-127) = -1100011100010000000 = 407680 (decimal)

Latihan

1. Konversi bilangan decimal 3,248 x 104 ke single-precision floating-point binary?

2. Tentukan nilai binary dan decimal dari bilangan binary floating-point berikut :

0 10011000 10000100010100110000000

Expressible Numbers of Floating-point

Produce one of these conditions

Exponent overflow : A positive exponent exceeds the maximum possible exponent value. In some systems, this may be designated as +∞ or - ∞.

Exponent underflow : A negative exponent is less than the minimum possible exponent value (e.g., - 200 is less than -127) 

Significand underflow : In the process of aligning significands, digits may flow off the right end of the significand. As we will discuss, some form of rounding is required.

Significand overflow : The addition of two significands of the same sign may result in a carry out of the most significant bit. This can be fixed by realignment.

IEEE 754 Formats

Arithmetic Operations

Addition and Subtraction

Ada 4 fase dari algoritma untuk penambahan dan pengurangan 

Phase 1. Zero check : Because addition and subtraction are identical except for a sign change, the process begins by changing the sign of the subtrahend if it is a subtract operation. Next, if either operand is 0, the other is reported as the result.

Phase 2. Significand alignment : The next phase is to manipulate the numbers so that the two exponents are equal.

Phase 3. Addition : Next, the two significands are added together, taking into account their signs. Because the signs may differ, the result may be 0. There is also the possibility of significand overflow by 1 digit. If so, the significand of the result is shifted right and the exponent is incremented. An exponent overflow could occur as a result; this would be reported and the operation halted.

Phase 4. Normalization : The selesai phase normalizes the result. Normalization consists of shifting significand digits left until the most significant digit (bit, or 4 bits for base-16 exponent) is nonzero. Each shift causes a decrement of the exponent and thus could cause an exponent underflow. Finally, the result must be rounded off and then reported.

Floating-Point Addition and Subtraction Flowchart

Floating-Point Multiplication Flowchart

Floating-Point Division Flowchart

Sumber

http://informatika.unpar.ac.id/

Slide AOK : Representasi Bilangan Biner

Sumber http://wikiwoh.blogspot.com