Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » A First Course in Electrical and Computer Engineering » Binary Codes: From Symbols to Binary Codes

Navigation

Table of Contents

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS

    This collection is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing Society

    Click the "IEEE-SPS" link to see all content they endorse.

  • College Open Textbooks display tagshide tags

    This collection is included inLens: Community College Open Textbook Collaborative
    By: CC Open Textbook Collaborative

    Comments:

    "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, […]"

    Click the "College Open Textbooks" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "A First Course in Electrical and Computer Engineering provides readers with a comprehensive, introductory look at the world of electrical engineering. It was originally written by Louis Scharf […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Evowl

    This collection is included inLens: Rice LMS's Lens
    By: Rice LMS

    Comments:

    "Language: en"

    Click the "Evowl" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Binary Codes: From Symbols to Binary Codes

Module by: Louis Scharf. E-mail the author

Note:

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

2N-1<M2N.2N-1<M2N.
(2)

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.

Exercise 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 { | } ~

Exercise 2

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<Vi2V0M+V0M}.Ci={V:i.2V0M-V0M<Vi2V0M+V0M}.
(4)

The mapping from continuous values of V to a finite set of approximations is

Q(V)=i2V0M, if VCi.Q(V)=i2V0M,ifVCi.
(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.

Figure 1: A Quantizer
A graph showing four quadrants. The center is labeled cell C_0 and the farthest points of the x and y axes in each direction are V_0. In the upper left quadrant is the expression 2V_0/M with and arrow point to the left towards a vertical line and the mirror of this to the right of it. Below this is C_-2. In the upper right quadrant there is the expression 2V_0/M with a similar arrow line figure to its left. This one is vertical and to the left there is the expression C_2. Proceeding from the lower right to the upper left there is a series of horizontal lines stair stepping up in along a positive slope.

Example 1

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 01020102). 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)

Exercise 3

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.

Exercise 4

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.

Exercise 5

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.

Figure 2: Binary Trees and Constant-Length Codes; (a) Binary Tree, and (b) Pruned Binary Tree
(a) (b)
A pair of binary trees. The one to the right is a normal binary tree. The upper leve is labeled 0 and 1. The level below it is slit with the branches labeled from left to right 0, 1, 0, 1. Below that the final level of branches is labeled from left to right 0, 1, 0, 1, 0, 1, 0, 1. The bottom layer is labeled from left to right 000, 001, 010, 011, 100, 101, 110, 111. Below these numbers are the labels (S_0),(S_1),(S_2),(S_3),(s_4),(x),(x),(x),(x). The tree on the right is exactly the same exactly the same except the right most 1 branch has been pruned off.Figure 2(b) (image009.png)

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.

Figure 3: Binary Trees and Variable-Length Codes; (a) Binary Tree for Variable-length Code, and (b) Another Binary Tree for Variable-length Code
(a) (b)
A pair of binary trees. The one to the right is a normal binary tree. The upper leve is labeled 0 and 1. The level below it is slit with the branches labeled from left to right 0, 1, 0, 1. Below that the final level of branches is labeled from left to right 0, 1, 0, 1, 0, 1, 0, 1. The bottom layer is labeled from left to right 000, 001, 010, 011, 100, 101, 110, 111. Below these numbers are the labels (S_0),(S_1),(S_2),(S_3),(s_4),(x),(x),(x),(x). The tree on the right is exactly the same exactly the same except the right most 1 branch has been pruned off.Figure 3(b) (pic006.png)

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.

Exercise 6

Decode the following sequence of bits using code 2:

0111001111000000101100111 . 0111001111000000101100111 .
(9)
Figure 4: Left-Handed Binary Trees for Variable-Length Codes; (a) Left-handed Binary Tree, and (b) Pruned Binary Tree
(a) (b)
Two binary trees. They are shaped like a diagonal line rising up and to the right with lines descending perpendicularly at equal distances marked by a dot. The lines between these dots are labeled 0, and the lines between the beginning and end of the perpendicular lines are labeled 1. At end of each of the perpedicular lines are these labels proceeding up and to the right: 00001, 0001, 001, 01, 1. Below these labels are another set of labels again proceeding up and to the right: (S_4), (S_3), (S_2), (S_1), (S_0). The right tree is exactly the same except for the bottom most perpendicular line has been pruned and is labeled 0000 and (S_4).Figure 4(b) (pic010.png)
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

Exercise 7

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.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks