Binary

Binary numbers are a crucial concept in the field of computer science. Computers are built on top of the binary number system, and many algorithms make use of binary numbers. In this assignment, you will be taking a look at one application involving binary numbers.

Run Length Encoding

It is sometimes important to minimize the space used for storing data. This idea of data compression can be implemented in many forms. One of the simpler techniques is known as Run Length Encoding $($RLE$).$ RLE takes advantage of the fact that in many cases, data will contain a run of repeated $0$s or $1$s$,$ and these runs can be represented by a shorter code. RLE is a technique used in some image or sound formats to reduce the overall size of the file. There are many variations of this process, but for this assignment, you will use the $3-$bit encoding version described below.

$1.$ Given binary data represented by a sequence of $0$s and $1$s$,$ break the number into runs of $0$s and $1$s and note the length of each run.

$2.$ For any run of more than $7,$ break the run into groups of $7$ or smaller.

$3.$ For each run, create an encoded form by first placing the type of run $0$ or $1$ and then the binary representation of the run's length.

$4.$ Write out the encoded form of data by taking each encoded run and separating them with spaces. Be sure to keep the original order of the data intact.

Example:

Given $11111000000010000001111111000000,$ what is the RLE form of this data?

Breaking this into runs gives us $51$s$,70$s$,11$s$,60$s$,71$s$,60$s

For each group, combine the length in binary followed by the type of run. Use spaces to

separate each run:

$110101111001011011110110$

Data compression is the ratio of the compressed data over the uncompressed data. In this case, the compressed data is $24$ bits $($including the spaces, which must be counted$),$ and the original data is $32$ bits. This gives a data compression ratio of $24/32$ or $0\mathrm{.}75.$

Answer the following questions.

$1.$ What is the RLE of the following inputs?

a$.1111111000000011$

b$.1111100000000000$

c$.1010101010101010$

$2.$ For each of your answers to question $1,$ compute the data compression ratio.

$3.$ Why must runs over $7$ be split apart in this $3-$bit encoding

scheme?

$4.$ Will this technique always result in a smaller RLE string

compared with the original data? Explain why or why not.