data compression 0 reduction in the amount of space needed to store a piece of data
compression ratio - the size of the compressed data divided by the size of the original data
a data compression tecniques can be
-lossless, which means the data can be retrieved without any loss of the original information
-lossy, which means some information may be lost in the process of compaction
analog & digital information
Computers are finite!
How do we represent an infinite world?
We represent enough of the world to satisfy our computational needs and our senses of sight and sound.
Information can be represented in one of two ways: analog or digital
Analog data
-A continuous representation, analogous to the actual information it represents
Digital data
-A discrete representation, breaking the information up into separate elements.
Thermometer is an analog device.
Computers cannot work well with analog data, so we digitize the data.
Digitize
-Breaking data into pieces and representing those pieces separately.
How do we use binary to represent digitized data?
Electronic Signals
Important facts about electronic signals
-An analog signal continually fluctuates in voltage up and down
-A digital signal has only a high or low state, corresponding to the two binary digits.
-All electronic signals (both analog and digital) degrade as they moved down a line
-The voltage of the signal flcutuates tdue to envrinomental factors.
Periodically, a digital signal is reclocked to regain its original shape.
Binary Representations
One bit can be either 0 or 1
One bit can repesent two things (Why?) 0 1 2 3
Two bits can represent four things (Why?) 00 01 10 11
Chances of winning Cash 3 Lottery is 1,000. Because you have 000 & 999 and is represented by the 10^umpth power.
2^n power will get you the number in bytes. 2^1=2 2^2=4 2^3=8 2^4=16 2^5=32 2^6=64 2^7=128 2^8=256
How many things can three bits represent?
How many things can four bits represent?
How many things can five bits represent?
When you increase the number of bits it doubles.
Representing Negative Values
Signed-magnitude number representation
The sign represents the ordering, and the digitis represent the magnitude of the number.
Using two decimal digits,
let 1 through 49 represent 1 through 49
let 50 through 99 repesent -50 through -1
To perform addition, add the numbers and discard any carry.
A-B=A+(-B)
Add the negative of the second to the first.
Formula to computer the negative represesntaiton of a number
Negative(I) =10^k - I, where k is the number of digits
The presesntation is called the ten's complement.
Negative(5)=100-50=50
Negative(49)=100-49=51
Negative(35)=100-35=65
Negative(1)=100-1=99
Two's Complement
(Veritcal line is easier to read)
00000000
-128-127
Negative(128)=256-128=128
Negative(127)=256-127=129
Addition and subtraction are the same as in 10's complement arithmetic.
-127 10000001
+ 1 00000001
------
-126 10000010
Real numbers**
A number with a whole part and a fractional part
104.32, 0.999999, 357.0, and 3.14159
Positions to the right of the decimal point are the teneths position: 10^-1, 10^-2, 10^-3
Same ryles apply in binary as in decimal. Decimal point is actually the radix point. Positions to the right of the radix point binary are 2^-1 (one half) 2^-2 (one quarter), 2^-3 (one eight)
Representing text
There are finite number of caracters to represent, so list them all and assign each a binary string.
01000001=65=A
01000010=66=B
01000011=67=C
01000100=68=D
32 is the difference between capital and lower case letters on this string.
01100001=97=a
01100010=98=b
Unicode uses 16bits 2^16=65,536 (for foreign languages like Chinese...etc)
1111111111111111
ASCII stnads form American Standard Code for Information Interchange.
ASCII originally used seven bits to represent each character, allowing for 128 bits.
Text Compression
Assigning 16 bits to each character in a document uses too much files space.
We need ways to store and transmit text effeicently.
Text compression techniques.
-keyword encoding
-run-length encoding
-Huffman encoding
Keyword Encoding
Replace frequently used words with a single character.
Run-length encoding.
A signle character may bre repeated over and over again in a long squence.
Replace a repeated sequence with
-a flag character
-repeated character
-number....
Huffman Encoding
Huffman codes use variable-length bit strings to repesent each character.
More frequently used letters have shorter strings to represent them.
Morse code
ETAOINS
*_ dit and dah
Huffman