// Numbas version: exam_results_page_options
{"name": "Upper and lower bounds for number of codewords in a maximal code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>A maximal 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>Enter the bounds as integers.&nbsp;</p>", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{gilbert_varshamov_bound(field_sizes[0],code_lengths[0],min_distances[0])}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{upper_bounds[0]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>A maximal 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>\n<p>Enter the bounds as integers.&nbsp;</p>", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{lower_bounds[1]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{upper_bounds[1]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>A maximal 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>\n<p>Enter the bounds as integers.&nbsp;</p>", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{lower_bounds[2]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{upper_bounds[2]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variables": {"errors_corrected": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(ceil(x/2)-1,x,min_distances)", "name": "errors_corrected", "description": "<p>Number of errors corrected by each code - biggest $t$ satisfying $d \\gt 2t$.</p>"}, "min_distances": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(random(3..min(5,code_length-2)),code_length,code_lengths)", "name": "min_distances", "description": "<p>Minimum distance&nbsp;of each code</p>"}, "hamming_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(hamming_bound(field_sizes[k],code_lengths[k],errors_corrected[k]),k,0..2)", "name": "hamming_bounds", "description": "<p>Hamming bound on the maximum number of words in each code</p>"}, "upper_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(min(hamming_bounds[k],singleton_bounds[k]),k,0..2)", "name": "upper_bounds", "description": "<p>Upper bound on the maximum number of words in each code - smallest of Hamming and Singleton bounds</p>"}, "singleton_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(singleton_bound(field_sizes[k],code_lengths[k],min_distances[k]),k,0..2)", "name": "singleton_bounds", "description": "<p>Singleton bound on the maximum number of words in each code</p>"}, "lower_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(gilbert_varshamov_bound(field_sizes[k],code_lengths[k],min_distances[k]),k,0..2)", "name": "lower_bounds", "description": "<p>Lower bound on the maximum number of words in each code - Gilbert-Varshamov bound.</p>"}, "code_lengths": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(random(5..log(10^9)/log(field_size)),field_size,field_sizes)", "name": "code_lengths", "description": "<p>The lengths of words in each code.</p>\n<p>Top end of the range confined so $\\text{field_size}^{\\text{code_length}} \\leq 10^9$, so the&nbsp;student can do all calculations on a calculator.</p>"}, "field_sizes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "shuffle([2,3,5,7])[0..3]", "name": "field_sizes", "description": "<p>Size $n$ of the field $\\mathbb{Z}_n$ each code lives in.</p>"}}, "ungrouped_variables": ["field_sizes", "code_lengths", "min_distances", "hamming_bounds", "singleton_bounds", "upper_bounds", "lower_bounds", "errors_corrected"], "name": "Upper and lower bounds for number of codewords in a maximal code", "variable_groups": [], "preamble": {"css": "", "js": ""}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "<p>Using the Hamming, Singleton and Gilbert&ndash;Varshamov bounds, give upper and lower bounds for the number of codewords in the following maximal codes with the given parameters, where $n$ is the codeword length and $d$ is the minimum distance between codewords.</p>\n<p>Your bounds should be given as integers. The lower bound should be the least integer greater than or equal to the Gilbert&ndash;Varshamov bound and the upper bound the greatest integer less than or equal to the least value given by the Hamming and Singleton bounds.</p>", "tags": [], "rulesets": {}, "extensions": ["codewords", "permutations"], "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Find upper and lower bounds on the number of codewords in three maximal codes given their codeword lengths and minimum distances.</p>\n<p>Uses Hamming, Singleton and Gilbert-Varshamov bounds.</p>"}, "functions": {}, "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<h4>a)</h4>\n<p>The Gilbert-Varshamov bound gives</p>\n<p>\\begin{align}<br/>M <br/>&amp;\\geq \\frac{ \\var{field_sizes[0]}^{\\var{code_lengths[0]}} }{ \\sum_{i=0}^{\\var{min_distances[0]}-1} \\binom{\\var{code_lengths[0]}}{i} \\left( \\var{field_sizes[0]}-1 \\right)^{i} } \\\\ \\\\<br/>&amp;= \\frac{\\var{field_sizes[0]^code_lengths[0]}}{\\var{sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(min_distances[0]-1)))}} \\\\ \\\\<br/>&amp;\\approx \\var{precround((field_sizes[0]^code_lengths[0])/sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(min_distances[0]-1))),2)}<br/>\\end{align}</p>\n<p>So we can say that $M \\geq \\var{lower_bounds[0]}$.</p>\n<p>The minimum distance between codewords in this code is $\\var{min_distances[0]}$, and $d \\gt 2t$, so it corrects at most $t = \\var{errors_corrected[0]}$ {pluralise(errors_corrected[0],\"error\",\"errors\")}.</p>\n<p>The Hamming bound for $M$ is thus</p>\n<p>\\begin{align}<br/>M &amp;\\leq \\frac{ \\var{field_sizes[0]}^{\\var{code_lengths[0]}} } { \\sum_{i=0}^{\\var{errors_corrected[0]}} \\binom{\\var{code_lengths[0]}}{i} \\left( \\var{field_sizes[0]}-1 \\right)^{i} } \\\\ \\\\<br/>&amp;= \\frac{\\var{field_sizes[0]^code_lengths[0]}}{\\var{sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(errors_corrected[0])))}} \\\\ \\\\<br/>&amp;\\approx \\var{precround((field_sizes[0]^code_lengths[0])/sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(errors_corrected[0]))),2)}<br/>\\end{align}</p>\n<p>So we can say that $M \\leq \\var{hamming_bounds[0]}$.</p>\n<p>The Singleton bound gives $M \\leq \\simplify[]{ {field_sizes[0]}^({code_lengths[0]}-{min_distances[0]}+1) } \\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>\n<p>The {if(hamming_bounds[0]&lt;singleton_bounds[0],\"Hamming\",\"Singleton\")} bound is lower than the&nbsp;{if(hamming_bounds[0]&lt;singleton_bounds[0],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.</p>\n<p>Finally, we can say that $\\var{lower_bounds[0]} \\leq M \\leq \\var{upper_bounds[0]}$.</p>\n<h4>b)</h4>\n<p>The Gilbert-Varshamov bound gives</p>\n<p>\\begin{align}<br/>M <br/>&amp;\\geq \\frac{ \\var{field_sizes[1]}^{\\var{code_lengths[1]}} }{ \\sum_{i=0}^{\\var{min_distances[1]}-1} \\binom{\\var{code_lengths[1]}}{i} \\left( \\var{field_sizes[1]}-1 \\right)^{i} } \\\\ \\\\<br/>&amp;= \\frac{\\var{field_sizes[1]^code_lengths[1]}}{\\var{sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(min_distances[1]-1)))}} \\\\ \\\\<br/>&amp;\\approx \\var{precround((field_sizes[1]^code_lengths[1])/sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(min_distances[1]-1))),2)}<br/>\\end{align}</p>\n<p>So we can say that $M \\geq \\var{lower_bounds[1]}$.</p>\n<p>The minimum distance between codewords in this code is $\\var{min_distances[1]}$, and $d \\gt 2t$, so it corrects at most $t = \\var{errors_corrected[1]}$ {pluralise(errors_corrected[1],\"error\",\"errors\")}.</p>\n<p>The Hamming bound for $M$ is thus</p>\n<p>\\begin{align}<br/>M &amp;\\leq \\frac{ \\var{field_sizes[1]}^{\\var{code_lengths[1]}} } { \\sum_{i=0}^{\\var{errors_corrected[1]}} \\binom{\\var{code_lengths[1]}}{i} \\left( \\var{field_sizes[1]}-1 \\right)^{i} } \\\\ \\\\<br/>&amp;= \\frac{\\var{field_sizes[1]^code_lengths[1]}}{\\var{sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(errors_corrected[1])))}} \\\\ \\\\<br/>&amp;\\approx \\var{precround((field_sizes[1]^code_lengths[1])/sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(errors_corrected[1]))),2)}<br/>\\end{align}</p>\n<p>So we can say that $M \\leq \\var{hamming_bounds[1]}$.</p>\n<p>The Singleton bound gives $M \\leq \\simplify[]{ {field_sizes[1]}^({code_lengths[1]}-{min_distances[1]}+1) } \\leq \\var{field_sizes[1]}^{\\var{code_lengths[1]-min_distances[1]+1}} = \\var{field_sizes[1]^(code_lengths[1]-min_distances[1]+1)}$.</p>\n<p>The {if(hamming_bounds[1]&lt;singleton_bounds[1],\"Hamming\",\"Singleton\")} bound is lower than the&nbsp;{if(hamming_bounds[1]&lt;singleton_bounds[1],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.</p>\n<p>Finally, we can say that $\\var{lower_bounds[1]} \\leq M \\leq \\var{upper_bounds[1]}$.</p>\n<h4>c)</h4>\n<p>The Gilbert-Varshamov bound gives</p>\n<p>\\begin{align}<br/>M <br/>&amp;\\geq \\frac{ \\var{field_sizes[2]}^{\\var{code_lengths[2]}} }{ \\sum_{i=0}^{\\var{min_distances[2]}-1} \\binom{\\var{code_lengths[2]}}{i} \\left( \\var{field_sizes[2]}-1 \\right)^{i} } \\\\ \\\\<br/>&amp;= \\frac{\\var{field_sizes[2]^code_lengths[2]}}{\\var{sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(min_distances[2]-1)))}} \\\\ \\\\<br/>&amp;\\approx \\var{precround((field_sizes[2]^code_lengths[2])/sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(min_distances[2]-1))),2)}<br/>\\end{align}</p>\n<p>So we can say that $M \\geq \\var{lower_bounds[2]}$.</p>\n<p>The minimum distance&nbsp;between codewords in this code is $\\var{min_distances[2]}$, and $d \\gt 2t$, so it corrects at most $t = \\var{errors_corrected[2]}$ {pluralise(errors_corrected[2],\"error\",\"errors\")}.</p>\n<p>The Hamming bound for $M$ is thus</p>\n<p>\\begin{align}<br/>M &amp;\\leq \\frac{ \\var{field_sizes[2]}^{\\var{code_lengths[2]}} } { \\sum_{i=0}^{\\var{errors_corrected[2]}} \\binom{\\var{code_lengths[2]}}{i} \\left( \\var{field_sizes[2]}-1 \\right)^{i} } \\\\ \\\\<br/>&amp;= \\frac{\\var{field_sizes[2]^code_lengths[2]}}{\\var{sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(errors_corrected[2])))}} \\\\ \\\\<br/>&amp;\\approx \\var{precround((field_sizes[2]^code_lengths[2])/sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(errors_corrected[2]))),2)}<br/>\\end{align}</p>\n<p>So we can say that $M \\leq \\var{hamming_bounds[2]}$.</p>\n<p>The Singleton bound gives $M \\leq \\simplify[]{ {field_sizes[2]}^({code_lengths[2]}-{min_distances[2]}+1) } \\leq \\var{field_sizes[2]}^{\\var{code_lengths[2]-min_distances[2]+1}} = \\var{field_sizes[2]^(code_lengths[2]-min_distances[2]+1)}$.</p>\n<p>The {if(hamming_bounds[2]&lt;singleton_bounds[2],\"Hamming\",\"Singleton\")} bound is lower than the&nbsp;{if(hamming_bounds[2]&lt;singleton_bounds[2],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.</p>\n<p>Finally, we can say that $\\var{lower_bounds[2]} \\leq M \\leq \\var{upper_bounds[2]}$.</p>", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"name": "Chris Graham", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/73/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"name": "Chris Graham", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/73/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}