// 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}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "

A maximal code over $\\mathbb{Z}_{\\var{field_sizes[0]}}$ with $n = \\var{code_lengths[0]}$ and $d = \\var{min_distances[0]}$.

\n

[[0]] $\\leq M \\leq$ [[1]]

\n

Enter the bounds as integers.

", "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": "

A maximal code over $\\mathbb{Z}_{\\var{field_sizes[1]}}$ with $n = \\var{code_lengths[1]}$ and $d = \\var{min_distances[1]}$.

\n

[[0]] $\\leq M \\leq$ [[1]]

\n

Enter the bounds as integers.

", "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": "

A maximal code over $\\mathbb{Z}_{\\var{field_sizes[2]}}$ with $n = \\var{code_lengths[2]}$ and $d = \\var{min_distances[2]}$.

\n

[[0]] $\\leq M \\leq$ [[1]]

\n

Enter the bounds as integers.

", "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": "

Number of errors corrected by each code - biggest $t$ satisfying $d \\gt 2t$.

"}, "min_distances": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(random(3..min(5,code_length-2)),code_length,code_lengths)", "name": "min_distances", "description": "

Minimum distance of each code

"}, "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": "

Hamming bound on the maximum number of words in each code

"}, "upper_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(min(hamming_bounds[k],singleton_bounds[k]),k,0..2)", "name": "upper_bounds", "description": "

Upper bound on the maximum number of words in each code - smallest of Hamming and Singleton bounds

"}, "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": "

Singleton bound on the maximum number of words in each code

"}, "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": "

Lower bound on the maximum number of words in each code - Gilbert-Varshamov bound.

"}, "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": "

The lengths of words in each code.

\n

Top end of the range confined so $\\text{field_size}^{\\text{code_length}} \\leq 10^9$, so the student can do all calculations on a calculator.

"}, "field_sizes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "shuffle([2,3,5,7])[0..3]", "name": "field_sizes", "description": "

Size $n$ of the field $\\mathbb{Z}_n$ each code lives in.

"}}, "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": "

Using the Hamming, Singleton and Gilbert–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.

\n

Your bounds should be given as integers. The lower bound should be the least integer greater than or equal to the Gilbert–Varshamov bound and the upper bound the greatest integer less than or equal to the least value given by the Hamming and Singleton bounds.

", "tags": [], "rulesets": {}, "extensions": ["codewords", "permutations"], "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "

Find upper and lower bounds on the number of codewords in three maximal codes given their codeword lengths and minimum distances.

\n

Uses Hamming, Singleton and Gilbert-Varshamov bounds.

"}, "functions": {}, "advice": "

The Gilbert-Varshamov bound gives a lower bound for $M$. The Hamming and Singleton bounds give upper bounds, so use the lowest of those.

\n

a)

\n

The Gilbert-Varshamov bound gives

\n

\\begin{align}
M
&\\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} } \\\\ \\\\
&= \\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)))}} \\\\ \\\\
&\\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)}
\\end{align}

\n

So we can say that $M \\geq \\var{lower_bounds[0]}$.

\n

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\")}.

\n

The Hamming bound for $M$ is thus

\n

\\begin{align}
M &\\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} } \\\\ \\\\
&= \\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])))}} \\\\ \\\\
&\\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)}
\\end{align}

\n

So we can say that $M \\leq \\var{hamming_bounds[0]}$.

\n

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)}$.

\n

The {if(hamming_bounds[0]<singleton_bounds[0],\"Hamming\",\"Singleton\")} bound is lower than the {if(hamming_bounds[0]<singleton_bounds[0],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.

\n

Finally, we can say that $\\var{lower_bounds[0]} \\leq M \\leq \\var{upper_bounds[0]}$.

\n

b)

\n

The Gilbert-Varshamov bound gives

\n

\\begin{align}
M
&\\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} } \\\\ \\\\
&= \\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)))}} \\\\ \\\\
&\\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)}
\\end{align}

\n

So we can say that $M \\geq \\var{lower_bounds[1]}$.

\n

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\")}.

\n

The Hamming bound for $M$ is thus

\n

\\begin{align}
M &\\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} } \\\\ \\\\
&= \\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])))}} \\\\ \\\\
&\\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)}
\\end{align}

\n

So we can say that $M \\leq \\var{hamming_bounds[1]}$.

\n

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)}$.

\n

The {if(hamming_bounds[1]<singleton_bounds[1],\"Hamming\",\"Singleton\")} bound is lower than the {if(hamming_bounds[1]<singleton_bounds[1],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.

\n

Finally, we can say that $\\var{lower_bounds[1]} \\leq M \\leq \\var{upper_bounds[1]}$.

\n

c)

\n

The Gilbert-Varshamov bound gives

\n

\\begin{align}
M
&\\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} } \\\\ \\\\
&= \\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)))}} \\\\ \\\\
&\\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)}
\\end{align}

\n

So we can say that $M \\geq \\var{lower_bounds[2]}$.

\n

The minimum distance 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\")}.

\n

The Hamming bound for $M$ is thus

\n

\\begin{align}
M &\\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} } \\\\ \\\\
&= \\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])))}} \\\\ \\\\
&\\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)}
\\end{align}

\n

So we can say that $M \\leq \\var{hamming_bounds[2]}$.

\n

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)}$.

\n

The {if(hamming_bounds[2]<singleton_bounds[2],\"Hamming\",\"Singleton\")} bound is lower than the {if(hamming_bounds[2]<singleton_bounds[2],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.

\n

Finally, we can say that $\\var{lower_bounds[2]} \\leq M \\leq \\var{upper_bounds[2]}$.

", "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/"}]}