Question

Run Length Encoding

It is sometimes important to minimise 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 0s or 1s, 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 0s and 1s, break the number into runs of 0s and 1s 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 5 1s, 7 0s, 1 1s, 6 0s, 7 1s, 6 0s

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

1101 0111 1001 0110 1111 0110 is the RLE form.

Data Compression

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 0.75.

Question 1a: What is the RLE of the following?

1111100000000000

Question 1b:

What is the compression ratio for the answer to Question 1a?

Question 2a: What is the RLE of the following?

101010

Question 2b:

What is the compression ratio for the answer to Question 2a?

Could you please help with these questions with enough explanation?

Thanks a lot

Answer 1

NOTE : In the example given in the question the RLE - 1101 0111 1001 0110 1111 0110 length is calculated as 24bits with spaces included which is wrong it should be 24bits with space excluded and 29bits with space included.I have calculated the compression ratio with both space included and excluded.

If you find the answer helpful please give a thumps up!

NOTE:In this question it is given to use binary equivalent to 3 size only

First you need to know how to covert any decimal number to binary number

1. Divide the number by 2.
2. Get the integer quotient for the next iteration.
3. Get the remainder for the binary digit.
4. Repeat the steps until the quotient is equal to 0.

Question 1a: What is the RLE of the following?

1111100000000000

Answer 1a:

Step 1 : Breaking the data in the runs of 1's and 0's of length less or equal to 7

Now the data has been broken down in two parts

So,the first part of data is 11111 (contain 5 1's)    & the second part is 00000000000 (contain 11 0's)

Since the second part has more than 7 bits then we further break that part in 7 0's and 4 0's

Now, the second part is 0000000(contain 7 0's)

third part is 0000(contain 4 0's)

Step 2: Counting the number of 1's or 0's in each part and replacing that part by the data bit followed by the number of that data bit in binary form.

The first part of data is 11111 (contain 5 1's)

Since all the bits in this part is 1 therefore its data bit is 1 and it contains 5 1's.

5 in binary can be written in binary as 101.

Therefore now replacing the data of this part by it's data bit i.e. 1 followed by number of 1's in binary i.e. 101.

11111 can be replaced by 1101

The second part of data is 0000000 (contain 7 0's)

Since all the bits in this part is 0 therefore its data bit is 0 and it contains 11 0's.

7 in binary can be written in binary as 111.

Therefore now replacing the data of this part by it's data bit i.e. 0 followed by number of 0's i.e. 111.

0000000 can be replaced by 0111

The third part of data is 0000 (contain 4 0's)

Since all the bits in this part is 0 therefore its data bit is 0 and it contains 4 0's.

4 in binary can be written in binary as 100.

Therefore now replacing the data of this part by it's data bit i.e. 0 followed by number of 0's i.e. 100.

0000 can be replaced by 0100

Step 3: Joining all the parts in sequence with space between them we get the encoded data

By joining both the parts i.e. first part which is 1101 and second part which is 0111 and third part which is 0100

RLE is = 1101 0111 0100

Question 1b:What is the compression ratio for the answer to Question 1a?

Answer 1b: Input - 1111100000000000

                    RLE   -   1101 0111 0100

The number of bits in the input is = 16

The number of bits in the RLE is with space included = 14

The number of bits in the RLE is with space excluded= 12

The compression ratio is defined as = Number of bits in the RLE / Number of bits in the input

Compression ratio with space included(i.e with 14 RLE bits) = 14/16 = 0.875

Compression ratio with space excluded(i.e with 12 RLE bits) = 12/16 = 0.75

Question 2a: What is the RLE of the following?

                        101010

ANSWER 2a.

101010

Step 1:

Breaking it up

1st part = 1 (contain 1 1's)

2nd part= 0 (contain 0 0's)

3rd part = 1 (contain 1 1's)

4th part= 0 (contain 0 0's)

5th part = 1 (contain 1 1's)

6th part= 0 (contain 0 0's)

Step 2:

1st part - data bit is 1 and the number of 1's is 1

                The binary of 1 is 001

                1 can be replaced by 1001

2nd part - data bit is 0 and the number of 0's is 1

                The binary of 1 is 001

                0 can be replaced by 0001

3rd part - data bit is 1 and the number of 1's is 1

                The binary of 1 is 001

                1 can be replaced by 1001

4th part - data bit is 0 and the number of 0's is 1

                The binary of 1 is 001

                0 can be replaced by 0001

5th part - data bit is 1 and the number of 1's is 1

                The binary of 1 is 001

                1 can be replaced by 1001

6th part - data bit is 0 and the number of 0's is 1

                The binary of 1 is 001

                0 can be replaced by 0001

Step 3:

Combining all the parts

The RLE is = 1001 0001 1001 0001 1001 0001

Question 2b:

What is the compression ratio for the answer to Question 2a?

Answer 2b: Input - 101010

                    RLE   -   1001 0001 1001 0001 1001 0001

The number of bits in the input is = 6

The number of bits in the RLE is with space included = 29

The number of bits in the RLE is with space excluded= 24

The compression ratio is defined as = Number of bits in the RLE / Number of bits in the input

Compression ratio with space included(i.e with 29 RLE bits) = 29/6 = 4.83

Compression ratio with space excluded(i.e with 24 RLE bits) = 24/6 = 4