1. Sort symbols according to their frequencies/probabilities, e.g., ABCDE 2. Recursively divide into two parts, each with approx. same number of counts (Huffman algorithm also valid indicated below) A simple transform coding example A Simple Transform Encoding procedure maybe described by the following steps for a 2x2 block of monochrome pixels 1. Take top left pixel as the base value for the block, pixel A 2. Calculate three other transformed values by taking the difference between these(respective) pixels and pixel A, i.e. B-A, C-A, D-A 3. Store the base pixel and the differences as the values of the transform Given the above we can easily for the forward transform and the inverse transform is trivial The above transform scheme may be used to compress data by exploiti redundancy in the data Any Redundancy in the data has been transformed to values, Xi. So We can compress the data by using fewer bits to represent the differences. I. e if we use 8 bits per pixel then the 2x2 block uses 32 bits/ If we keep 8 bits for the base pixel, XO, and assign 4 bits for each difference then we only use 20 bits Which is better than an average 5 bits/pixel 8 MARKS---BOOKWORK (c)(Show how you would use Huffman coding to encode the following set of tokens BABACACADADABBCBABEBEDDABEEEBB How is this message transmitted when encoded? The Huffman algorithm is now briefly summarised (e.g, ABC Initialization: Put all nodes in an OPEN list, keep it sorted at all times EDEY1. Sort symbols according to their frequencies/probabilities, e.g., ABCDE. 2. Recursively divide into two parts, each with approx. same number of counts. (Huffman algorithm also valid indicated below) A simple transform coding example A Simple Transform Encoding procedure maybe described by the following steps for a 2x2 block of monochrome pixels: 1. Take top left pixel as the base value for the block, pixel A. 2. Calculate three other transformed values by taking the difference between these (respective) pixels and pixel A, i.e. B-A, C-A, D-A. 3. Store the base pixel and the differences as the values of the transform. Given the above we can easily for the forward transform: and the inverse transform is trivial The above transform scheme may be used to compress data by exploiting redundancy in the data: Any Redundancy in the data has been transformed to values, Xi. So We can compress the data by using fewer bits to represent the differences. I.e if we use 8 bits per pixel then the 2x2 block uses 32 bits/ If we keep 8 bits for the base pixel, X0, and assign 4 bits for each difference then we only use 20 bits. Which is better than an average 5 bits/pixel 8 MARKS --- BOOKWORK (c) (i) Show how you would use Huffman coding to encode the following set of tokens: BABACACADADABBCBABEBEDDABEEEBB How is this message transmitted when encoded? The Huffman algorithm is now briefly summarised: 1. Initialization: Put all nodes in an OPEN list, keep it sorted at all times (e.g., ABCDE)