Transcript The decimal to binary algorithm explained

102
6
10 1
100
1
3
6 x 100+ 1 x 10 + 3 x 1
=613
Base 10
digits {0...9}
3
2
1
2
2
1
2
0
1
20
1
1 x 8+ 1 x 4+ 0 x 2+ 1 x 1
= 13
Base 2
digits {0, 1}
decimal
binary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
The binary equivalents of
some decimal numbers.
parent
Left child
right child
A binary tree consists
of a set of nodes each
of which can have at
most two children.
root
The top node of the tree is
called the root. A leaf is a
node with no descendants.
leaf
leaf
leaf
0
3
2
1
0
0
2
2
2
1
13 (dec)
0
0
1
20
1
The binary digits (bits) in the
computer’s memory are initially
set to zero. To represent a
number, the appropriate bits
are set to 1.
4 (dec) = 000100
Multiplying by 2 in machine
language is accomplished
by shifting left one bit.
4 (dec) = 000100
8 (dec) =
001000
Multiplying by 2 in machine
language is accomplished
by shifting left one bit.
4 (dec) = 000100
8 (dec) =
16 (dec) =
001000
010000
Multiplying by 2 in machine
language is accomplished
by shifting left one bit.
4 (dec) = 000100
5 (dec) = 000101
8 (dec) = 001000
9 (dec) = 001001
16 (dec) =
010000
17 (dec) =
010001
We obtain the next integer by
adding a 1 to the binary
number.
n
2n
2n+1
Construct a tree using the following: If
the parent ‘s node number is n, the left
child’s is 2*n and the right child‘s is 2*n
+ 1.
1
We assign 1 to the root’s node number
1
2
Then, the left child’s node number is 2
1
2
3
And the right child’s node number is 3.
1
0
2
4
3
5
6
7
A graphical way of getting the binary
equivalents of decimal numbers. Place
a 0 on each left edge.
1
0
2
3
0
4
5
6
7
A graphical way of getting the binary
equivalents of decimal numbers. Place
a 0 on each left edge.
1
0
2
3
0
0
4
5
6
7
A graphical way of getting the binary
equivalents of decimal numbers. Place
a 0 on each left edge.
1
1
0
2
3
0
0
4
5
6
7
A graphical way of getting the binary
equivalents of decimal numbers. Place
a 0 on each left edge and a 1 on each
right edge of a binary tree.
1
1
0
2
0
4
3
1
0
5
6
7
A graphical way of getting the binary
equivalents of decimal numbers. Place
a 0 on each left edge and a 1 on each
right edge of a binary tree.
1
1
0
2
0
4
3
1
0
5
6
1
7
A graphical way of getting the binary
equivalents of decimal numbers. Place
a 0 on each left edge and a 1 on each
right edge of a binary tree.
1
0
2
0
4
3
1
5
6
7
1
To convert 5 to binary, start by writing
the lower-most 1 on the path from node
5 to the root.
1
0
2
0
4
3
1
5
6
7
01
To the left of the 1, write the digit for
the next edge on the upward path to the
root, namely, 0.
1
0
2
0
4
3
1
5
6
7
101
Finally, to the left of the 0, place a 1.
This represents the node number of the
root, 1, which is the same in binary and
decimal.
1
1
0
2
0
4
100
3
1
0
5
101
1
6
7
110
111
The node numbers at the leaves
converted to binary numbers.
1
1
0
1
2
10
0
4
100
3
1
0
5
101
11
1
6
7
110
111
Placing a 0 on each left edge is
equivalent to shifting left, ie.,
multiplying by 2. Placing a 1 on
the right edge means you are
adding 1 to the left child’s value.
Express 67 in decimal
33
1
67
1 (bin)
16
1
33
1
67
11 (bin)
0
16
8
1
33
1
67
011 (bin)
0
16
0
4
33
1
8
1
67
0011 (bin)
0
0
16
0
4
33
1
2
8
1
67
00011 (bin)
1
0
0
0
16
0
4
33
1
2
8
1
67
000011 (bin)
1
0
0
0
16
0
4
33
1
2
Place 1 at the left since
the root node contains 1.
8
1
67
67 (dec) = 1000011 (bin)
American Standard Code for Information Interchange
character
a
b
c
d
e
f
g
h
i
j
k
l
m
n
ascii code
binary
97
98
99
100
101
102
103
104
105
106
107
108
109
110
1100001
1100010
1100011
1100100
1100101
1100110
1100111
1101000
1101001
1101010
1101011
1101100
1101101
1101110
The ascii code in
decimal and
binary for some
characters. Thus
it requires 7 bits
to represent
each character.
0
a
0
b
1
c
Symbol a: 0
Symbol b: 00
Symbol c : 1
The code 001 can be
decoded as aac or bc. Thus
the code is ambiguous.
0
a
Symbol a: 0
1
b
The code 01 is decoded as b.
Symbol b: 01 Before, however, you reach the
end of the string 01, you would
think that 0 corresponds to a. The
code requires you to scan ahead.
This is called non-instantaneous
code and is inefficient as coding
scheme.
If the characters are only in
the leaves, the code is
unique and instantaneous.
Such a code exhibits the
prefix property.
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
Let’s decode 10001
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
c
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
c
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
c
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
ca
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
ca
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
ca
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
10001
cab
0
0
a
1
c
1
b
Symbol a: 00
Symbol b: 01
Symbol c: 1
Letter
a
b
g
h
Frequency
11
2
9
4
Letters occurring in a paragraph
and their frequency of occurrence.
How can we encode these letters
so that the resultant code is
minimal?
A list of nodes containing the
letters and frequencies. The list
is sorted by frequency.
b, 2
h, 4
g, 9
a, 11
Remove the first two nodes, add
their frequencies, and create a
parent node with that frequency.
Letters will appear in only the
leaves of the final tree.
*, 6
b, 2
g, 9
h, 4
a, 11
Insert the parent node with its children
in its sorted position in the list. This
type of list and its operations is called
a priority queue.
*, 6
b, 2
g, 9
h, 4
a, 11
Remove the first two nodes again, add
their frequencies, and create a parent
node with that frequency.
*, 15
*, 6
b, 2
a, 11
g, 9
h, 4
Insert the parent node with its
children in its sorted position in
the list.
a, 11
*, 15
*, 6
b, 2
g, 9
h, 4
By continuing the process, we
get the final tree. The leaves are
the only nodes containing letters.
*, 26
a, 11
*, 15
*, 6
b, 2
g, 9
h, 4
This tree is called a Huffman tree.
Here it is shown with only the
leaves labeled.
a
g
b
h
Label the edges with 0’s and 1’s as
we did for the binary numbers.
0
1
0
a
0
b
1
1
g
h
The letters with their Huffman codes. The
letters with the higher frequencies have
smaller Huffman codes.
0
letter
a
g
h
b
1
0
a
0
b
1
1
g
h
frequency
11
9
4
2
Huffman code
0
11
101
100
Let’s decode 100011
0
1
0
a
0
b
1
1
g
h
100011
0
1
0
a
0
b
1
1
g
h
100011
0
1
0
a
0
b
1
1
g
h
100011
0
1
0
a
0
b
1
1
g
h
100011 We hit a leaf, print letter,
Resultant code: b
0
1
0
a
0
b
1
1
g
h
100011 We hit a leaf, print letter & return to root.
Resultant code: b
0
1
0
a
0
b
1
1
g
h
100011 We hit a leaf, print letter
Resultant code: ba
0
1
0
a
0
b
1
1
g
h
100011 We hit a leaf, print letter & return to root.
Resultant code: ba
0
1
0
a
0
b
1
1
g
h
100011
Resultant code: ba
0
1
0
a
0
b
1
1
g
h
100011 We hit a leaf and print letter.
Resultant code: bag
0
1
0
a
0
b
1
1
g
h
bag : 100011 in Huffman code
bag : 1100010
character
a
b
c
d
e
f
g
h
i
j
k
l
m
n
ascii code
binary
97
98
99
100
101
102
103
104
105
106
107
108
109
110
1100001
1100010
1100011
1100100
1100101
1100110
1100111
1101000
1101001
1101010
1101011
1101100
1101101
1101110
bag : 100011 in Huffman code
bag : 11000101100001
character
a
b
c
d
e
f
g
h
i
j
k
l
m
n
ascii code
binary
97
98
99
100
101
102
103
104
105
106
107
108
109
110
1100001
1100010
1100011
1100100
1100101
1100110
1100111
1101000
1101001
1101010
1101011
1101100
1101101
1101110
bag : 100011 in Huffman code
bag : 110001011000011100111 in ascii code
character
a
b
c
d
e
f
g
h
i
j
k
l
m
n
ascii code
binary
97
98
99
100
101
102
103
104
105
106
107
108
109
110
1100001
1100010
1100011
1100100
1100101
1100110
1100111
1101000
1101001
1101010
1101011
1101100
1101101
1101110
If you number the nodes as we did
when we converted decimal to
binary, you can get the Huffman
code from the node numbers.
2,a
7,g
12,b
13,h
Letter
a
g
h
b
2,a
7,g
12,b
13,h
Node
2
7
13
12
Binary
10
111
1101
1100
Huffman Code
0
11
101
100
The Huffman code is
obtained from the binary by
removing the leading 1.
"Baseball's Sad Lexicon"
These are the saddest of possible words:
"Tinker to Evers to Chance."
Trio of bear cubs, and fleeter than birds,
Tinker and Evers and Chance.
Ruthlessly pricking our gonfalon bubble,
Making a Giant hit into a double-Words that are heavy with nothing but trouble:
"Tinker to Evers to Chance."
Franklin Pierce Adams
http://memory.loc.gov/ammem/bbhtml/bb1.html