This module is part of the collection, A First Course in Electrical and Computer Engineering. The LaTeX source files for this collection were created using an optical character recognition technology, and because of this process there may be more errors than usual. Please contact us if you discover any errors.
Perhaps the most fundamental idea in communication theory is that arbitrary symbols may be represented by strings of binary digits. These strings are called binary words, binary addresses, or binary codes. In the simplest of cases, a finite alphabet consisting of the letters or symbols s0,s1,...,sM-1s0,s1,...,sM-1 is represented by binary codes. The obvious way to implement the representation is to let the ithith binary code be the binary representation for the subscript
i
i:
s
0
∼
000
=
a
0
s
1
∼
001
=
a
1
⋮
s
6
∼
110
=
a
6
s
7
∼
111
=
a
7
.
s
0
∼
000
=
a
0
s
1
∼
001
=
a
1
⋮
s
6
∼
110
=
a
6
s
7
∼
111
=
a
7
.
(1)The number of bits required for the binary code is
N
N where
We say, roughly, that N=log2MN=log2M.
Octal Codes. When the number of symbols is large and the corresponding binary codes contain many bits, then we typically group the bits into groups of three and replace the binary code by its corresponding octal code. For example, a seven-bit binary code maps into a three-digit octal code as follows:
0000000
∼
000
0000001
∼
001
⋮
0100110
∼
046
⋮
101111
∼
137
⋮
1111111
∼
177
.
0000000
∼
000
0000001
∼
001
⋮
0100110
∼
046
⋮
101111
∼
137
⋮
1111111
∼
177
.
(3)The octal ASCII codes for representing letters, numbers, and special characters are tabulated in Table 1.
Write out the seven-bit ASCII codes for A,q,7,and{A,q,7,and{.
Table 1: Octal ASCII Codes (from Donald E. Knuth, The TEXbook, ©1986 by the American Mathematical Society, Providence, Rhode Island p. 367, published by Addison-Wesley Publishing Co.)
| |
'0 |
'1 |
'2 |
'3 |
'4 |
'5 |
'6 |
'7 |
| '00x |
␀ |
␁ |
␂ |
␃ |
␄ |
␅ |
␆ |
␇ |
| '01x |
␈ |
␉ |
␊ |
␋ |
␌ |
␍ |
␎ |
␏ |
| '02x |
␐ |
␑ |
␒ |
␓ |
␔ |
␕ |
␖ |
␗ |
| '03x |
␘ |
␙ |
␚ |
␛ |
␜ |
␝ |
␞ |
␟ |
| '04x |
␠ |
! |
" |
# |
$ |
% |
& |
' |
| '05x |
( |
) |
* |
+ |
, |
- |
. |
/ |
| '06x |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| '07x |
8 |
9 |
: |
; |
< |
= |
> |
? |
| '10x |
@ |
A |
B |
C |
D |
E |
F |
G |
| '11x |
H |
I |
J |
K |
L |
M |
N |
O |
| '12x |
P |
Q |
R |
S |
T |
U |
V |
W |
| '13x |
X |
Y |
Z |
[ |
\ |
] |
^ |
_ |
| '14x |
` |
a |
b |
c |
d |
e |
f |
g |
| '15x |
h |
i |
j |
k |
l |
m |
n |
o |
| '16x |
p |
q |
r |
s |
t |
u |
v |
w |
| '17x |
x |
y |
z |
{ |
| |
} |
~ |
␡ |
Add a 1 or a 0 to the most significant (left-most) position of the seven-bit ASCII code to produce an eight-bit code that has even parity (even number of 1's). Give the resulting eight-bit ASCII codes and the corresponding three-digit octal codes for %, u,f,8,u,f,8,
and
++.
Quantizers and A/D Converters. What if the source alphabet is infinite? Our only hope is to approximate it with a finite collection of finite binary words. For example, suppose the output of the source is an analog voltage that lies between -V0-V0
and
+V0+V0. We might break this peak-to-peak range up into little voltage cells of size 2VMA2VMA and approximate the voltage in each cell by its midpoint. This scheme is illustrated in Figure 1. In the figure,
the cell
C
i
C
i
is defined to be the set of voltages that fall between iM-M¯2̲VpVΔiM-M¯2̲VpVΔ and i2̲VMΔ+VMAi2̲VMΔ+VMA :
Ci={V:i.2V0M-V0M<V≤i2V0M+V0M}.Ci={V:i.2V0M-V0M<V≤i2V0M+V0M}.
(4)The mapping from continuous values of V to a finite set of approximations is
Q(V)=i2V0M,
if
V∈Ci.Q(V)=i2V0M,ifV∈Ci.
(5)That is,
V
V is replaced by the quantized approximation iM2̲V0iM2̲V0 whenever
V
V lies in cell
C
i
C
i
. We may represent the quantized values iM2̲V0iM2̲V0 with binary codes by simply representing the subscript of the cell by a binary word. In a subsequent course on digital electronics and microprocessors you will study A/DA/D (analog-to-digital) converters for quantizing variables.
If M=8M=8, corresponding to a three-bit quantizer, we
may associate quantizer cells and quantized levels with binary codes as follows:
V
∈
C
-
3
⇒
V
-
3
=
(
-
3
)
2
V
0
8
∼
111
V
∈
C
-
2
⇒
V
-
2
=
(
-
2
)
2
V
0
8
∼
110
V
∈
C
-
1
⇒
V
-
1
=
(
-
1
)
2
V
0
8
∼
101
V
∈
C
0
⇒
V
0
=
0
∼
000
V
∈
C
1
⇒
V
1
=
(
1
)
2
V
0
8
∼
001
V
∈
C
2
⇒
V
2
=
(
2
)
2
V
0
8
∼
010
V
∈
C
3
⇒
V
3
=
(
3
)
2
V
0
8
∼
011
.
V
∈
C
-
3
⇒
V
-
3
=
(
-
3
)
2
V
0
8
∼
111
V
∈
C
-
2
⇒
V
-
2
=
(
-
2
)
2
V
0
8
∼
110
V
∈
C
-
1
⇒
V
-
1
=
(
-
1
)
2
V
0
8
∼
101
V
∈
C
0
⇒
V
0
=
0
∼
000
V
∈
C
1
⇒
V
1
=
(
1
)
2
V
0
8
∼
001
V
∈
C
2
⇒
V
2
=
(
2
)
2
V
0
8
∼
010
V
∈
C
3
⇒
V
3
=
(
3
)
2
V
0
8
∼
011
.
(6)This particular code is called a sign-magnitude code, wherein the most significant bit is a sign bit and the remaining bits are magnitude bits (e.g., 110∼-2110∼-2 and 010∼2010∼2). One of the defects of the sign-magnitude code is that it wastes one code by using 000 for 0 and 100 for-O. An alternative code that has many other advantages is the 2's complement code. The 2's2's complement codes for positive numbers are the same as the sign-magnitude codes, but the codes for negative numbers are generated by complementing all bits for the corresponding positive number and adding 1:
-
4
∼
100
-
3
∼
101
(
100
+
1
)
-
2
∼
110
(
101
+
1
)
-
1
∼
111
(
110
+
1
)
0
∼
000
1
∼
001
2
∼
010
3
∼
011
.
-
4
∼
100
-
3
∼
101
(
100
+
1
)
-
2
∼
110
(
101
+
1
)
-
1
∼
111
(
110
+
1
)
0
∼
000
1
∼
001
2
∼
010
3
∼
011
.
(7)
Generate the four-bit sign-magnitude and four-bit 2's complement binary codes for the numbers -8,-7,...,-1,0,1,2,...,7-8,-7,...,-1,0,1,2,...,7.
Prove that, in the 2's2's complement representation, the binary
codes for -nand+n-nand+n sum to zero. For example,
101
+
011
=
000
(
-
3
)
(
3
)
(
0
)
.
101
+
011
=
000
(
-
3
)
(
3
)
(
0
)
.
(8) In your courses on computer arithmetic you will learn how to do arithmetic in various binary-coded systems. The following problem illustrates how easy arithmetic is in 2's complement.
Generate a table of sums for all 2's2's complement numbers between -4-4 and +3. Show that the sums are correct. Use 0+0=0,0+1=1,1+0=10+0=0,0+1=1,1+0=1, and 1+1=01+1=0 with a carry into the next bit. For example, 001+001=010.001+001=010.
Binary Trees and Variable-Length Codes. The codes we have constructed so far are constant-length codes for finite alphabets that contain exactly M=2NM=2N symbols. In the case where M=8M=8 and N=3N=3, then the eight possible three-bit codes may be represented as leaves on the branching tree illustrated in Figure 2(a). The tree grows a left branch for a 0 and a right branch for a 1, until it terminates after three branchings. The three-bit codes we have studied so far reside at the terminating leaves of the binary tree. But what if our source alphabet contains just five symbols or letters? We can represent these five symbols as the three-bit symbols 000 through 100 on the binary tree. This generates a constant-length code with three unused, or illegal, symbols 101 through 111. These are marked with an "
x
x" in Figure 2(a). These unused leaves and the branches leading to them may be pruned to produce the binary tree of Figure 2(b).
If we admit variable-length codes, then we have several other options for using a binary tree to construct binary codes. Two of these codes and their corresponding binary trees are illustrated in Figure 3. If we disabuse ourselves of the notion that each code word must contain three or fewer bits, then we may construct binary trees like those of Figure 4 and generate their corresponding binary codes. In Figure 4(a), we grow a right branch after each left branch and label each leaf with a code word. In Figure 4(b), we prune off the last right branch and associatea code word with the leaf on the last left branch.
All of the codes we have generated so far are organized in Table 2. For each code, the average number of bits/symbol is tabulated. This average ranges from 2.4 to 3.0. If all symbols are equally likely to appear, then the best variable-length code would be code 2.
All of the codes we have constructed have a common characteristic: each code word is a terminating leaf on a binary tree, meaning that no code word lies along a limb of branches to another code word. We say that no code word is a prefix to another code word. This property makes each of the codes instantaneously decodable, meaning that each bit in a string of bits may be processed instantaneously (or independently) without dependence on subsequent bits.
Decode the following sequence of bits using code 2:
0111001111000000101100111
.
0111001111000000101100111
.
(9) Table 2: Variable Length Codes
| Code # |
S
0
S
0
|
S
1
S
1
|
S
2
S
2
|
S
3
S
3
|
S
4
S
4
|
Average Bits/Symbol |
| 1 |
000 |
001 |
010 |
011 |
100 |
15
/
5
=
3.0
15/5=3.0 |
| 2 |
000 |
001 |
01 |
10 |
11 |
12
/
5
=
2.4
12/5=2.4 |
| 3 |
000 |
001 |
010 |
011 |
1 |
13
/
5
=
2.6
13/5=2.6 |
| 4 |
1 |
01 |
001 |
0001 |
00001 |
15
/
5
=
3.0
15/5=3.0 |
| 5 |
1 |
01 |
001 |
0001 |
0000 |
14
/
5
=
2.8
14/5=2.8 |
Illustrate the following codes on a binary tree. Which of them
are instantaneously decodable? Which can be pruned and remain instantaneously decodable?
S
0
S
1
S
2
S
3
S
4
011
100
00
11
101
011
100
00
0
01
010
000
100
101
111
.
S
0
S
1
S
2
S
3
S
4
011
100
00
11
101
011
100
00
0
01
010
000
100
101
111
.
(10) Code #2 generated in Table 2 seems like a better code than code #5 because its average number of bits/symbol (2.4) is smaller. But what if symbol
S
0
S
0
is a very likely symbol and symbol
S
4
S
4
is a very unlikely one? Then it may well turn out that the average number of bits used by code #5 is less than the average number used by code #2. So what is the best code? The answer depends on the relative frequency of use for each symbol. We explore this question in the next section.
(What does "Endorsed by" mean?)
"Reviewer's Comments: 'I recommend this book as a "required primary textbook." This text attempts to lower the barriers for students that take courses such as Principles of Electrical Engineering, […]"