The following activity is from Claude E Shannon: Collected papers

Imagine that you go to the library. This library has a large selection of books — say there are 100 million

books in this library. Each book in this library is very thick — say, for example, that each book has 100

million characters (or letters) in them. When you get to this library, you will, in some random manner,

select a book to check out. This chosen book is the information source to be compressed. The compressed book is then stored on your zip disk to take home, or transmitted directly over the internet into your home, or whatever the case may be.

Mathematically, the book you select is denoted byX = ( X1, X2, X3, X4,………..). Where X represents the whole book, X1, represents the first character in the book, X2,represents the second character, and so on. Even though in reality the length of the book is finite, mathematically we assume that it has infinite length. The reasoning is that the book is so long we can just imagine that it goes on forever. Furthermore, the mathematics turns out to be surprisingly simpler if we assume an infinite length book.

To simplify the task, let us assume the book is in digital form, and it is just text and that all the characters in all the books are either a lower-case letter (`a’ through `z’) or a SPACE (e. e. cummings style of writing

shall we say). The source alphabet, A , is defined to be the set of all 27 possible values of the characters: A= {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,space}.

Activity

You are to store a digital book of 1000 million characters.

1. How much space do you need using ASCII code (8 bits per character)?

2. It is possible to use fewer fixed bits per character. What would be the least number of fixed bits per characters?

3. Without any consultation, analyze the problem and state a naïve method or algorithm to code the above given book using fewer bits?

4. How the original file size (from literal 1) compares with the compressed file (from your proposed algorithm)?

5. State how would you measure the efficiency of your proposed algorithm.

**Use the order calculator below and get started! Contact our live support team for any assistance or inquiry.**