Transcript 09/06/04

COMS 161
Introduction to Computing
Title: The Digital Domain
Date: September 6, 2004
Lecture Number: 6
1
Announcements
• Homework 3
– Due on Friday, 09/10/04
2
Review
• Digital information
– Advantages
• Number system
– Non-positional
– Positional
• Decimal
• Octal
• Binary
3
Outline
• Binary numbers
4
Binary Number System
• Since binary digits have two possible
values they are called bits
– They only contain a little “bit” of information
– Numbers represented in binary form will
(most likely) require more digits (bits) than
the decimal form
4510  1011012
5
Binary Number System
• To represent more
information
– Lump together
multiple bits
called strings
Number of
Bits
1
2
3
4
5
6
Number of
Values
2
4
8
16
32
64
7
8
128
256
6
Binary Number System
• In general
number of values = 2number of bits
• How does 1 bit represent 2 values?
– It can have one of two values 0, 1
– Can represent two colors, black and white
– 0: black
– 1: white
• Can represent two numbers: 0, 1
7
Binary Number System
• How do 2 bits represent 4 values?
Bit Pattern
00
Numeric
Value
0
Item
Represented
Black
01
1
White
10
2
Red
11
3
Green
8
Binary Number System
• How do 3 bits represent 8 values?
Bit Pattern
Numeric Value
Item Represented
000
0
Black
001
1
White
010
2
Red
011
3
Green
100
4
Blue
101
5
Purple
110
6
Magenta
111
7
Sky blue
9
Binary Number System
• How do 4 bits represent 16 values?
Bit Pattern
Value
Bit Pattern
Value
0000
0
1000
8
0001
1
1001
9
0010
2
1010
10
0011
3
1011
11
0100
4
1100
12
0101
5
1101
13
0110
6
1110
14
0111
7
1111
15
10
Binary Number System
• Bit patterns and numeric values are
consistent with other slides
– Acceptable to add leading 0’s if desired
000  0 * 2  0 * 2  0 * 2  0  0  0  0
001  0 * 2 2  0 * 21  1* 20  0  0  1  1
2
1
0
010  0 * 2  1* 2  0 * 2  0  2  0  2
2
1
0
011  0 * 2  1* 2  1* 2  0  2  1  3
100  1* 2 2  0 * 21  0 * 20  4  0  0  4
101  1* 2 2  0 * 21  1* 20  4  0  1  5
110  1* 2 2  1* 21  0 * 20  4  2  0  6
111  1* 2 2  1* 21  1* 20  4  2  1  7
2
1
0
11
Binary Number System
• We can represent the non-negative
numbers (unsigned number)
0 – 2number of bits - 1
• How about representing negative
numbers?
– Let the left most bit represent the sign (+, -)
of the number
– Called signed magnitude representation
– [s][mag]
12
Signed Magnitude
– One less bit to represent the magnitude


001  0 * 2  1* 2   0  1  1
010  1* 2  0 * 2   2  0  2
011  1* 2  1* 2   2  1  3
100  0 * 2  0 * 2   0  0  0
101  0 * 2  1* 2   0  1  1
110  1* 2  0 * 2   2  0  2
111  1* 2  1* 2   2  1  3
000   0 * 21  0 * 20  0  0  0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
13
Signed Magnitude
• Problems
– Two values of 0
• More difficult to detect than one value of 0
– Incorrect arithmetic
• 2 – 1 = 2 + (-1) = 1
010
101
111  3  1
14
Two’s Complement Representation
• Sign bit in a sense
– Positive numbers
• The leading bit (left most) is zero
• The same as signed magnitude
– Negative numbers
• The leading bit is one
• Defined so that when added to their
corresponding positive number the answer is
zero
15
Two’s Complement Representation
Bit Pattern
Value
Bit Pattern
Value
0000
0
1000
-8
0001
1
1001
-7
0010
2
1010
-6
0011
3
1011
-5
0100
4
1100
-4
0101
5
1101
-3
0110
6
1110
-2
0111
7
1111
-1
16
Two’s Complement Representation
• Problems with signed magnitude
representation are solved with the two’s
complement representation
– There is only value of zero
– Arithmetic is correct
• Solution is in two’s complement form
• 2 – 1 = 2 + (-1) = 1
010
111
001  1
17
Binary Encoding
• Unsigned binary numbers are useful
when labeling things
• Common grouping
– 4 bits: nibble
– 8 bits: byte
• One byte represents 256 different values
or items
18
Binary Number System
– Letters in the English language
• A = 6510 = 0100 00012
• B = 6610 = 0100 00102
• …
• Z = 9010 = 0101 10102
• …
• a = 9710 = 0110 00012
• …
• Z = 12210 = 0111 10102
• Numbers are still left over for punctuation
19
Binary Number System
• Precision
– The number of bits used to represent an
item
• Letter: precision of 8 bits
• Integer (whole number): precision of 32 or 64
bits
– Always finite
• Computers have finite precision
– Presents some limitations
20
Hexadecimal Number System
• Sometimes called hex
– Positional,base-16 system
– Each digit is multiplied by a power of 16
– Sixteen unique symbols (digits)
• 0, 1, 2, …, 15
• Symbol a or A for 10
• Symbol b or B for 11
• Symbol c or C for 12
• Symbol d or D for 13
Symbol e or E for 14
Symbol f or F for 15
21
Hexadecimal Number System
• A hex number can represent 16 different
items
– Equivalent to 4 bits
– Makes it easy to convert between binary
and hex
• Group bits by 4’s from the left end
• Substitute the hex symbol
– 9010 = 0101 10102 = 5A16
» Is the base 16 really needed?
– 6610 = 0100 00102 = 4216
22
Hexadecimal Number System
• Use the backwards conversion to convert
hex to binary
– One hex digit is equivalent to 4 bits
– Substitute the binary nibble
• Always start at the right end
• Add zeros to the left end as necessary to fill in 4
bits
23
Hexadecimal Number System
HEX
DEC
BIN
0
0
0000
1
1
0001
2
2
0010
3
3
0011
4
4
0100
5
5
0101
6
6
0110
7
7
0111
8
8
1000
9
9
1001
A
10
1010
B
11
1011
C
12
1100
D
13
1101
E
14
1110
F
15
1111
24
Digitization
• The process of converting analog
information into binary
– Discrete forms are unambiguous
• Text and numbers are discrete
– Conversion of discrete to digital
• Come up with a mapping
– As we did with the letters
25
Binary Coded Decimal
• Integers (whole numbers)
– One mapping is to use its binary equivalent
• Binary Coded Decimal (BCD)
– 010 = 00002
– 110 = 00012
– …
– 910 = 10012
• Need a minimum of 4 bits to represent 10
different values
– Some 4 bit quantities are wasted
26
Binary Coded Decimal
• String of decimal digits
– Each decimal digit is represented by 4 bits
– The number of bits needed to represent
different numbers vary
– Performing arithmetic is complicated
27
Digitizing Analog Information
• Two steps
–Sampling the information
• Select discrete samples that represents the
information
–Quantizing the samples
• Discrete samples are measured
• Encoded into a binary representation
28
Digitizing Analog Information
• Sampling
– In time or space (picture)
• Quantizing
– Approximating the measured value
29
Digitizing Images
• Images are digitized
using a two step
process
• Sampling the
continuous tone
image
• Quantizing the
samples
30
Sampling Images
Sample image by pixel resolution
Spatial Sampling
Sample twodimensional space
31
Quantizing Images
All gray values in each sample are averaged
32
Quantizing Images
Different amount of sampling
33
Quantizing Images
Different amount of sampling
34
Quantizing Images
Different amount of sampling
35