// Numbas version: finer_feedback_settings
{"name": "Hamming and Singleton bound", "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,k),\n      k,\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"]]}, "singleton_bound": {"definition": "p^(n-d+1)", "type": "number", "language": "jme", "parameters": [["p", "number"], ["n", "number"], ["d", "number"]]}}, "name": "Hamming and Singleton bound", "tags": [], "type": "question", "advice": "<p>The Hamming bound gives</p>\n<p>\\[ M \\leq 2^{\\var{code_length}} \\left( \\sum_{i=0}^{\\var{error}} \\binom{\\var{code_length}}{i} \\right)^{-1} = 2^{\\var{code_length}}(\\simplify[zeroTerm]{{comb(code_length,0)}+{comb(code_length,1)}+{comb(code_length,2)}+{if(error&gt;2,comb(code_length,3),0)} })^{-1} = \\frac{\\var{2^code_length}}{\\var{sum(map(comb(code_length,k),k,0..error))}} \\]</p>\n<p>giving $M \\leq \\var{hamming_bound}$.</p>\n<p>If a code corrects $t = \\var{error}$ errors it must have minimum distance $d = \\var{2*error+1}$ or $d = \\var{2*error+2}$, since $t$ is the biggest integer less than $d/2$. The Singleton bound is either</p>\n<p>\\[ 2^{\\simplify[]{{code_length} - {2*error+1} + 1}} = 2^{\\var{code_length-(2*error+1)+1}} = \\var{2^(code_length-(2*error+1)+1)}\\]</p>\n<p>or</p>\n<p>\\[ 2^{\\simplify[]{{code_length} - {2*error+2} + 1}} = 2^{\\var{code_length-(2*error+2)+1}} = \\var{2^(code_length-(2*error+2)+1)}\\]</p>\n<p>Either way, we have $M \\leq&nbsp;\\var{2^(code_length-(2*error+1)+1)}$.</p>", "rulesets": {}, "parts": [{"prompt": "<p>Using the Hamming bound, determine an upper bound on the possible number of words in $C$.</p>", "marks": 1, "maxValue": "hamming_bound", "minValue": "hamming_bound", "showCorrectAnswer": true, "scripts": {}, "type": "numberentry", "showPrecisionHint": false}, {"prompt": "<p>Compute the Singleton bound for the maximum possible number of words in $C$.</p>", "marks": 1, "maxValue": "singleton_bound", "minValue": "singleton_bound", "showCorrectAnswer": true, "scripts": {}, "type": "numberentry", "showPrecisionHint": false}], "statement": "<p>Let $C$ be a binary $\\var{error}$-error correcting code of length $\\var{code_length}$.</p>", "variable_groups": [{"variables": ["hamming_bound", "singleton_bound"], "name": "Bounds"}, {"variables": ["error", "code_length", "min_distance"], "name": "Code parameters"}], "progress": "in-progress", "preamble": {"css": "", "js": ""}, "variables": {"hamming_bound": {"definition": "hamming_bound(2,code_length,error)", "templateType": "anything", "group": "Bounds", "name": "hamming_bound", "description": ""}, "singleton_bound": {"definition": "singleton_bound(2,code_length,min_distance)", "templateType": "anything", "group": "Bounds", "name": "singleton_bound", "description": ""}, "code_length": {"definition": "random(10..25)", "templateType": "anything", "group": "Code parameters", "name": "code_length", "description": ""}, "min_distance": {"definition": "error*2+1", "templateType": "anything", "group": "Code parameters", "name": "min_distance", "description": ""}, "error": {"definition": "random(2..3)", "templateType": "anything", "group": "Code parameters", "name": "error", "description": ""}}, "metadata": {"notes": "<p>WHF: changed j to k in sum in Advice and in definition of Hamming bound function. If this is to be generalised to other fields $\\mathbb{Z}_p$ need to include a factor of $(p-1)^k$ at suitable points.</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/"}]}