// Numbas version: exam_results_page_options {"name": "Find the minimum distance of a code given its parity check matrix", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"basis": {"templateType": "anything", "group": "Ungrouped variables", "definition": "identity_left(A)", "name": "basis", "description": "

Basis for the dual code.

"}, "dimension": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..5)", "name": "dimension", "description": "

Dimension of the dual code - number of rows in the parity check matrix.

"}, "explanation": {"templateType": "anything", "group": "Ungrouped variables", "definition": "let(d,min_distance,\n switch(\n d=1,\n \"Column \"+dependent_columns[0]+\" is $\\\\mathbf{0}$, so $d(C) = 1$.\",\n d=2, \n \"There is no $\\\\mathbf{0}$ column, so $d(C) \\\\gt 1$. Columns \"+dependent_columns[0]+\" and \"+dependent_columns[1]+\" are equal, so $d(C) = 2$.\",\n d=3,\n \"There is no $\\\\mathbf{0}$ column, and no two columns are equal, so $d(C) \\\\gt 2$. The sum of columns \"+dependent_columns[0]+\",\"+dependent_columns[1]+\" and \"+dependent_columns[2]+\" is $\\\\mathbf{0}$, so $d(C)=3$.\",\n \n \"There is no $\\\\mathbf{0}$ column, and no two columns are equal, so $d(C) \\\\gt 2$. The sum of columns \"+dependent_columns[0]+\",\"+dependent_columns[1]+\",\"+dependent_columns[2]+\" and \"+dependent_columns[3]+\" is $\\\\mathbf{0}$, so $d(C)=4$.\"\n )\n)", "name": "explanation", "description": "

Explanation of the derivation of the minimum distance, for the advice section.

"}, "A": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)", "name": "A", "description": "

The parity check matrix is $I_{dim}|A$, where $A$ is random.

"}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "dimension+random(3..5)", "name": "word_length", "description": "

Length of each word in the code

"}, "C": {"templateType": "anything", "group": "Ungrouped variables", "definition": "code(set_generated_by(parity_check_matrix(basis)))", "name": "C", "description": "

The code $C$.

"}, "min_distance": {"templateType": "anything", "group": "Ungrouped variables", "definition": "minimum_distance(C)", "name": "min_distance", "description": "

Minimum distance of the code $C$.

\n

Could work this out by looking at the number of dependent columns, but it's nice to verify directly.

"}, "field_size": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "field_size", "description": ""}, "columns": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(codeword(x,2),x,list(transpose(H)))", "name": "columns", "description": "

Columns of the parity check matrix, interpreted as codewords.

"}, "nary": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "name": "nary", "description": ""}, "dependent_columns": {"templateType": "anything", "group": "Ungrouped variables", "definition": "linearly_dependent_combination(columns)", "name": "dependent_columns", "description": "

Smallest combination of columns of the parity check matrix which sum to 0.

"}, "H": {"templateType": "anything", "group": "Ungrouped variables", "definition": "codeword_matrix(basis)", "name": "H", "description": "

The parity check matrix (basis for the dual code, represented as a matrix)

"}}, "ungrouped_variables": ["field_size", "nary", "dimension", "word_length", "A", "basis", "H", "C", "columns", "min_distance", "dependent_columns", "explanation"], "name": "Find the minimum distance of a code given its parity check matrix", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "

Compute the minimum distance between codewords of a code, given a parity check matrix.

"}, "functions": {"identity_right": {"type": "list", "language": "javascript", "definition": "var k = words.length;\nvar field_size = words[0].field_size;\nvar out = [];\nfor(var i=0;i$d(C) =$ [[0]]

", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "min_distance", "maxValue": "min_distance", "unitTests": [], "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "scripts": {}, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "2", "showFeedbackIcon": true}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "

Find the minimum distance of the binary code $C$ given by the following parity check matrix.

\n

\$\\mathrm{H} =\\var{H} \$

", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "extensions": ["codewords", "permutations"], "advice": "

The minimum distance $d(C)$ is equal to the smallest number of columns of $\\mathrm{H}$ related by a linear dependence.

\n

{explanation}

", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"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": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}