Transcript PPT

CS120: Lecture 2
MP Johnson
Hunter College
[email protected]
1
Agenda: data
•
•
•
•
Review ops/gates
Abstract storage: flipflops
Storage methods
representation:
–
–
–
–
Test
Images
Sound
Numbers
• Positive
• Negative
• Fractions
• Compression
2
Circuits as memory
• Flipflop: special circuit that can store data
– 1 bit per FF
To store, send
pulse in top or
bottom (0 is ddf)
Go through
3
Another FF
Go through
4
circuits
• Q: where do inputs come from?
• A: other circuits!
• Connect worker circuit to mem circuit
• This kind of mem is in RAM or maybe CPU
– Fast: measured in ns
– Fast everywhere – “random”
– But Requires constant power
5
Memory cells arranged by address
6
Metric units
• “Kilo-” normally means 1,000;
Kilobyte = 210 = 1024
• “Mega-” normally means 1,000,000;
Megabyte = 220 = 1,048,576
• “Giga-” normally means 1,000,000,000;
Megabyte = 230 = 1,073,741,824
7
Other (perm) kinds of mem
• Hard drive: Disk spins, head moves
– Partly mechanical!
– Usually larger, but slower
• Measured in ms
• Time depends somewhat on location
8
Other (perm) kinds of mem
• Optical: CD/DVD
– Slower, less random
– Read-only/read-once
• Flash: USB, MP3
• Tape: very slow,
sequential
9
Storage devices
•
•
•
•
•
•
•
Hardware varies a lot
Q: what stays the same?
A: all store bits / 1-of-2 choices
Q: why not base 3 or base 10?
A: easier!
High (voltage) v. low or pos v neg or 0 v 1
High v. low v. medium
• Q: why do we ever use base 10?
10
Claim: data = nums = bits
• Eg, letters: can’t write ‘A’ on a HD
• Q: what to do?
• A: pick some num to rep ‘A’
– Turns out: ‘A’ = 65, ‘B’ = 66
– ANSI’s ASCII
• Q: but how to rep 65?
– Can’t write num 65 on a HD
• A: write 65 in binary
11
base
• mathematically, any
base will do
• On machine, must
use base 2:
– 65 = 6*10 + 5*1
= 1*64 + 1*1
= 1*2^5 + 1*2^0
= 1000001b
•  65 + 1 = 1000001
+ 1 = 1000010
12
ANSI
• ANSI only uses 7 bits (128 vals)
• Insert a 1 at front to get 8 bits = 1 byte (255)
• Usually: think in terms of bytes, not bits
• Q: what about negatives, fractions?
• A: next time…
13
hex
• Sometimes base-16
is used for as
shorthand
– 1 base-16 val = 4 bits
• Also octal
14
Rep’ing images?
• One way:
– Bitmaps (.bmp)
– b/w: 2-d table of brightness values
• Pixel = picture element
– Col: one table each of r/g/b
– Size: 1000*1000*3 = 3MB!
• Another:
– Vector methods…
15
Rep’ing sounds?
• One way:
– Sample soundwave ampl at intervals
– Phones: 8000/s
– CD: 44,1000/s
• Another:
– MIDI
– For 10s constant tone, record tone + length
16
Data compression
• NB: vectors and MIDI sound smarter
• But whatever you do, must still be stored
as bits
• Must find a way to encode these
instructions as bits
• Harder than storing directly!
17
Base 2 v. base 10
18
Convert base10  base2
• Alg: while x is not 0
– Write x%2 to right
– Set x = x/2
19
Integers with bits
•
•
Unsigned (non-neg): just base2
Signed:
0. Just use sign bit
•
How to add/sub?
1. 1’s comp
–
–
How to add/sub?
Two 0’s
2. 2’s comp
–
–
How to add/sub?
See app. B for neg, add circuits
3. Also: excess notation (skip?)
20
Fractions in binary (naïve)
21
IEEE floating-pt standard
22
IEEE floats
• Used for all fractions in C/C++/Java
• Strength: very large range (billions)
• Weakness: merely approximate
– Can depend on order!
23
Compression
• Saw MIDI for sound
• Saw vectors for images
• Other methods:
– Relative methods for images (why works?)
• GIF, JPEG
– Relative methods for video (why works?)
• MPEG
– Run-length encoding
– Frequency-based (why works?)
– LZ (zip files)
24
Recognizing errors
• Idea: include extra info
• Parity bits:
25
Correcting errors
• “Error-correcting codes”
• If only one bad bit, can recover,e.g., 010100
26
Future
• No class Tuesday
• Reading for Wednesday is on website
• Hw posted soon (email/web)
27