// Numbas version: finer_feedback_settings
{"name": "Upper and lower bounds for maximum number of codewords", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"functions": {"hamming_bound": {"definition": "floor(p^n/(sum(\n    map(\n      comb(n,j),\n      j,\n      0..t\n))))", "type": "number", "language": "jme", "parameters": [["p", "number"], ["n", "number"], ["t", "number"]]}, "sum": {"definition": "var total = 0;\nfor(var i=0;i<list.length;i++) {\n  total += list[i];\n}\nreturn total;", "type": "number", "language": "javascript", "parameters": [["list", "list"]]}, "gilbert_varshamov_bound": {"definition": "ceil(p^n/(sum(\n    map(\n      comb(n,j),\n      j,\n      0..(d-1)\n))))", "type": "number", "language": "jme", "parameters": [["p", "number"], ["n", "number"], ["d", "number"]]}, "singleton_bound": {"definition": "p^(n-d+1)", "type": "number", "language": "jme", "parameters": [["p", "number"], ["n", "number"], ["d", "number"]]}}, "name": "Upper and lower bounds for maximum number of codewords", "tags": [], "type": "question", "advice": "<p>The Gilbert-Varshamov bound gives a lower bound for $M$. The Hamming and Singleton bounds give upper bounds, so use the lowest of those.</p>\n<h3>a)</h3>\n<p>Gilbert-Varshamov: $M \\geq&nbsp;\\frac{\\var{field_sizes[0]^code_lengths[0]}}{\\var{sum(map(comb(code_lengths[0],j),j,0..(min_distances[0]-1)))}} \\approx \\var{precround((field_sizes[0]^code_lengths[0])/sum(map(comb(code_lengths[0],j),j,0..(min_distances[0]-1))),2)}$</p>\n<p>Hamming: $M \\leq \\frac{\\var{field_sizes[0]^code_lengths[0]}}{\\var{sum(map(comb(code_lengths[0],j),j,0..(errors_corrected[0])))}} \\approx \\var{precround((field_sizes[0]^code_lengths[0])/sum(map(comb(code_lengths[0],j),j,0..(errors_corrected[0]))),2)}$</p>\n<p>Singleton: $M \\leq \\var{field_sizes[0]}^{\\var{code_lengths[0]-min_distances[0]+1}} = \\var{field_sizes[0]^(code_lengths[0]-min_distances[0]+1)}$</p>", "rulesets": {}, "parts": [{"prompt": "<p>A code over $\\mathbb{Z}_{\\var{field_sizes[0]}}$ with $n = \\var{code_lengths[0]}$ and $d = \\var{min_distances[0]}$.</p>\n<p>[[0]] $\\leq M \\leq$ [[1]]</p>\n<p>{lower_bounds}</p>\n<p>{hamming_bounds}</p>\n<p>{errors_corrected}</p>\n<p>{singleton_bounds}</p>", "marks": 0, "gaps": [{"expectedvariablenames": [], "checkingaccuracy": 0.001, "vsetrange": [0, 1], "showpreview": true, "vsetrangepoints": 5, "showCorrectAnswer": true, "scripts": {}, "answer": "{lower_bounds[0]}", "marks": 1, "checkvariablenames": false, "checkingtype": "absdiff", "type": "jme"}, {"expectedvariablenames": [], "checkingaccuracy": 0.001, "vsetrange": [0, 1], "showpreview": true, "vsetrangepoints": 5, "showCorrectAnswer": true, "scripts": {}, "answer": "{upper_bounds[0]}", "marks": 1, "checkvariablenames": false, "checkingtype": "absdiff", "type": "jme"}], "showCorrectAnswer": true, "scripts": {}, "type": "gapfill"}, {"prompt": "<p>A code over $\\mathbb{Z}_{\\var{field_sizes[1]}}$ with $n = \\var{code_lengths[1]}$ and $d = \\var{min_distances[1]}$.</p>\n<p>[[0]] $\\leq M \\leq$ [[1]]</p>", "marks": 0, "gaps": [{"expectedvariablenames": [], "checkingaccuracy": 0.001, "vsetrange": [0, 1], "showpreview": true, "vsetrangepoints": 5, "showCorrectAnswer": true, "scripts": {}, "answer": "{lower_bounds[1]}", "marks": 1, "checkvariablenames": false, "checkingtype": "absdiff", "type": "jme"}, {"expectedvariablenames": [], "checkingaccuracy": 0.001, "vsetrange": [0, 1], "showpreview": true, "vsetrangepoints": 5, "showCorrectAnswer": true, "scripts": {}, "answer": "{upper_bounds[1]}", "marks": 1, "checkvariablenames": false, "checkingtype": "absdiff", "type": "jme"}], "showCorrectAnswer": true, "scripts": {}, "type": "gapfill"}, {"prompt": "<p>A code over $\\mathbb{Z}_{\\var{field_sizes[2]}}$ with $n = \\var{code_lengths[2]}$ and $d = \\var{min_distances[2]}$.</p>\n<p>[[0]] $\\leq M \\leq$ [[1]]</p>", "marks": 0, "gaps": [{"expectedvariablenames": [], "checkingaccuracy": 0.001, "vsetrange": [0, 1], "showpreview": true, "vsetrangepoints": 5, "showCorrectAnswer": true, "scripts": {}, "answer": "{lower_bounds[2]}", "marks": 1, "checkvariablenames": false, "checkingtype": "absdiff", "type": "jme"}, {"expectedvariablenames": [], "checkingaccuracy": 0.001, "vsetrange": [0, 1], "showpreview": true, "vsetrangepoints": 5, "showCorrectAnswer": true, "scripts": {}, "answer": "{upper_bounds[2]}", "marks": 1, "checkvariablenames": false, "checkingtype": "absdiff", "type": "jme"}], "showCorrectAnswer": true, "scripts": {}, "type": "gapfill"}], "statement": "<p>Using the Hamming, Singleton and Gilbert&ndash;Varshamov bounds, give upper and lower bounds for the maximum number of codewords in the following codes:</p>", "variable_groups": [], "progress": "in-progress", "preamble": {"css": "", "js": ""}, "variables": {"field_sizes": {"definition": "shuffle([2,3,4,5,6,7])[0..3]", "templateType": "anything", "group": "Ungrouped variables", "name": "field_sizes", "description": ""}, "code_lengths": {"definition": "repeat(random(5..15),3)", "templateType": "anything", "group": "Ungrouped variables", "name": "code_lengths", "description": ""}, "min_distances": {"definition": "repeat(random(2..5),3)", "templateType": "anything", "group": "Ungrouped variables", "name": "min_distances", "description": ""}, "hamming_bounds": {"definition": "map(hamming_bound(field_sizes[j],code_lengths[j],errors_corrected[j]),j,0..2)", "templateType": "anything", "group": "Ungrouped variables", "name": "hamming_bounds", "description": ""}, "singleton_bounds": {"definition": "map(singleton_bound(field_sizes[j],code_lengths[j],min_distances[j]),j,0..2)", "templateType": "anything", "group": "Ungrouped variables", "name": "singleton_bounds", "description": ""}, "upper_bounds": {"definition": "map(min(hamming_bounds[j],singleton_bounds[j]),j,0..2)", "templateType": "anything", "group": "Ungrouped variables", "name": "upper_bounds", "description": ""}, "lower_bounds": {"definition": "map(gilbert_varshamov_bound(field_sizes[j],code_lengths[j],min_distances[j]),j,0..2)", "templateType": "anything", "group": "Ungrouped variables", "name": "lower_bounds", "description": ""}, "errors_corrected": {"definition": "map(ceil(x/2)-1,x,min_distances)", "templateType": "anything", "group": "Ungrouped variables", "name": "errors_corrected", "description": ""}}, "metadata": {"notes": "<p>Something's wrong with the calculation of the Hamming bounds.</p>\n<p>Need to make sure that the G-V bound is always less than the upper bound.</p>", "description": "", "licence": "Creative Commons Attribution 4.0 International"}, "showQuestionGroupNames": false, "question_groups": [{"name": "", "pickingStrategy": "all-ordered", "pickQuestions": 0, "questions": []}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}