Digital Communication Assignment 2018/19

Deadline

14:00 on Friday 15th December 2018

---

Instructions

Analyse properties of LZ77 coding:

1. Running time of the encoder (compression)
2. Running time of the decoder (decompression)
3. Compression ratio
4. Comparison with other compression techniques

Implement the LZ77 algorithm in Python, write a report on the above.

Mark scheme

Each of the four sections is worth 25 marks.

Within each section:

Criteria	Marks
Thoroughness	15
Clarity	10

Thoroughness:

• Different window sizes
• Different input types and sizes
• Search for maximum/minimum/average running time
• Different machines

Submission

Code and 5 page PDF report.

---

Obtaining results

Running time (for encoder and decoder)

1. Experimental Time Complexity

   • Input: Lorem ipsum text
   • Independent variable: size of input
   • Dependent variable: execution time
   • Constant variables: window size, buffer size

2. Effect of window size

   • Input: Lorem Ipsum text
   • Independent variable: window size
   • Dependent variable: execution time
   • Constant variables: input size, buffer size

3. Effect of buffer size

   • Input: Lorem Ipsum text
   • Independent variable: buffer size
   • Dependent variable: execution time
   • Constant variables: input size, window size

4. Different file types

   • Input: files
   • Independent variable: input file type
   • Dependent variable: execution time
   • Constant variables: input size, window size, buffer size

5. Different machines

   • Perform (1) on different computers and compare

Compression Ratio

1. Effect of window size

   • Input: Lorem ipsum text
   • Independent variable: window size
   • Dependent variable: compression ratio
   • Constant variables: buffer size, input size

2. Effect of buffer size

   • Input: Lorem ipsum text
   • Independent variable: buffer size
   • Dependent variable: compression ratio
   • Constant variables: window size, input size

3. Different file types

   • Input: files
   • Independent variable: input file type
   • Dependent variable: execution time
   • Constant variables: input size, window size, buffer size

Comparison with other techniques

1. Running time
2. Compression ratio