questions","basePath":"/gcse/computer-science/aqa/data-compression/questions","formulaUrl":null,"initialIndex":14,"initialQuestionWindow":[{"id":"2f1b531d-bb44-4867-9f10-dac80122e335","revisionId":"aa6d30ef-54a4-4397-ad14-55c36298ec6a","questionNumber":null,"questionType":"LA","specification":"","difficulty":4,"difficultyBand":"medium","totalMarks":3,"sourceTitle":null,"calculatorUse":null,"parts":[{"id":"18ad0711-25f9-41f5-afc1-6acd4b9356e6","label":null,"content":"An automated weather station in North America transmits its regional identifier, the string **APPALACHIAN**, back to a central server. To conserve transmission bandwidth, the station uses Huffman coding.\n\nTable 1 shows the Huffman codes allocated for each character in this string.\n\nCalculate how many bits of transmission bandwidth are saved if the string **APPALACHIAN** is encoded using the Huffman codes shown in **Table 1**, rather than using standard 8-bit ASCII.\n\nYou should show your working.\n\nTable 1\n\n| Character | Character frequency | Huffman code |\n| :--- | :--- | :--- |\n| A | 4 | 0 |\n| P | 2 | 10 |\n| L | 1 | 1100 |\n| C | 1 | 1101 |\n| H | 1 | 1110 |\n| I | 1 | 11110 |\n| N | 1 | 11111 |\n| **Total** | **11** | |","markscheme":"- Calculates the total size of the uncompressed string using standard 8-bit ASCII as $11 \\times 8 = 88$ bits (or 7-bit ASCII as $11 \\times 7 = 77$ bits) M1\n- Calculates the total size of the compressed string using the given Huffman codes as $30$ bits, showing the calculation: $4(1) + 2(2) + 1(4) + 1(4) + 1(4) + 1(5) + 1(5) = 30$ M1\n- Obtains the correct final answer of $58$ bits saved (or $47$ bits saved if 7-bit ASCII is used) A1","marks":3,"order":0,"markingRubric":null,"explanation":null,"options":[]}],"options":[],"explanation":null,"firstAttemptFullMarks":null},{"id":"3ed072d9-94f9-4f2f-84dc-527eef63bab5","revisionId":"82ebbba2-0158-44d8-b03a-1d63ccb018d0","questionNumber":null,"questionType":"LA","specification":"","difficulty":3,"difficultyBand":"medium","totalMarks":3,"sourceTitle":null,"calculatorUse":null,"parts":[{"id":"2c87f9f0-57ce-4faf-86e6-ac723906ada4","label":null,"content":"Use the Huffman tree in **Figure 1** to state the Huffman encoding for the string **CASK**.\n\n![Figure 1: Huffman tree diagram](https://assets.mathsgenie.co.uk/aqa-qb/53bc1599-a28f-4e05-a750-d19eee4cc24a.png)\n\n*Note: Left branches are represented by 0 and right branches are represented by 1.*","markscheme":"- Correctly encodes at least two characters (from: $C = 100$, $A = 101$, $S = 00$, $K = 110$) M1\n- Correctly encodes at least three characters, or writes a final string with at most one bit error M1\n- Concatenates the codes in the correct order to obtain the final binary representation $10010100110$ A1","marks":3,"order":0,"markingRubric":null,"explanation":null,"options":[]}],"options":[],"explanation":null,"firstAttemptFullMarks":null},{"id":"3f4426ac-0b32-41df-b196-5a05cdef83bf","revisionId":"c44f481f-c54e-44e5-b68b-b42d7cf46fb2","questionNumber":null,"questionType":"LA","specification":"","difficulty":3,"difficultyBand":"medium","totalMarks":3,"sourceTitle":null,"calculatorUse":null,"parts":[{"id":"983d3db6-08a2-47af-96d3-6c3553c6c118","label":null,"content":"Use the Huffman tree in **Figure 1** to state the Huffman encoding for the string **MIST**.\n\n![Figure 1](https://assets.mathsgenie.co.uk/aqa-qb/17a6224a-f1e7-46b3-8083-2beb1af9dbde.png)\n\n*Note: Left branches are represented by 0 and right branches are represented by 1.*","markscheme":"- Correctly identifies the Huffman code for at least 2 characters from M ($110$), I ($111$), S ($011$), or T ($10$) M1\n- Correctly identifies the Huffman code for at least 3 characters, or provides the complete string with exactly one bit error A1\n- States the correct final Huffman encoding: $11011101110$ A1","marks":3,"order":0,"markingRubric":null,"explanation":null,"options":[]}],"options":[],"explanation":null,"firstAttemptFullMarks

Data compression

Question 7

Data compression Questions

Data compression

Question 7

Data compression Questions