// Numbas version: finer_feedback_settings
{"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, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"basis": {"templateType": "anything", "group": "Ungrouped variables", "definition": "identity_left(A)", "name": "basis", "description": "<p>Basis for the dual code.</p>"}, "dimension": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..5)", "name": "dimension", "description": "<p>Dimension of the dual code - number of rows in the parity check&nbsp;matrix.</p>"}, "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": "<p>Explanation of the derivation of the minimum distance, for the advice section.</p>"}, "A": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)", "name": "A", "description": "<p>The parity check&nbsp;matrix is $I_{dim}|A$, where $A$ is random.</p>"}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "dimension+random(3..5)", "name": "word_length", "description": "<p>Length of each word in the code</p>"}, "C": {"templateType": "anything", "group": "Ungrouped variables", "definition": "code(set_generated_by(parity_check_matrix(basis)))", "name": "C", "description": "<p>The code $C$.</p>"}, "min_distance": {"templateType": "anything", "group": "Ungrouped variables", "definition": "minimum_distance(C)", "name": "min_distance", "description": "<p>Minimum distance of the code $C$.</p>\n<p>Could work this out by looking at the number of dependent columns, but it's nice to verify directly.</p>"}, "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": "<p>Columns of the parity check matrix, interpreted as codewords.</p>"}, "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": "<p>Smallest combination of columns of the parity check matrix which sum to 0.</p>"}, "H": {"templateType": "anything", "group": "Ungrouped variables", "definition": "codeword_matrix(basis)", "name": "H", "description": "<p>The parity check matrix (basis for the dual code, represented as a matrix)</p>"}}, "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": "<p>Compute the minimum distance between codewords of a code, given a parity check matrix.</p>"}, "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<k;i++) {\n  var row = [];\n  for(var j=0;j<k;j++) {\n    row.push(j==i ? 1 : 0);\n  }\n  row = row.concat(words[i].digits);\n  out.push(new Numbas.extensions.codewords.Codeword(row,field_size));\n}\nreturn out.map(function(w){ return new Numbas.jme.types.TCodeword(w)});", "parameters": [["words", "list"]]}, "linearly_dependent_combination": {"type": "list", "language": "javascript", "definition": "// find a combination of columns whose sum is zero\n\nfunction sum(words) {\n  var c = words[0];\n  for(var i=1;i<words.length;i++) {\n    c = c.add(words[i]);\n  }\n  return c;\n}\n\nvar indexes = [];\nfor(var i=0;i<columns.length;i++) {\n  indexes.push(i+1);\n}\nfor(var i=1;i<columns.length;i++) {\n  var combos = Numbas.util.combinations(indexes,i);\n  for(var j=0;j<combos.length;j++) {\n    if(sum(combos[j].map(function(d){return columns[d-1]})).isZero()) {\n      return combos[j];\n    }\n  }\n}", "parameters": [["columns", "list"]]}, "identity_left": {"type": "list", "language": "javascript", "definition": "// add an identity matrix to the left of a matrix of codewords\nvar k = words.length;\nvar field_size = words[0].field_size;\nvar out = [];\nfor(var i=0;i<k;i++) {\n  var row = [];\n  for(var j=0;j<k;j++) {\n    row.push(j==i ? 1 : 0);\n  }\n  row = row.concat(words[i].digits);\n  out.push(new Numbas.extensions.codewords.Codeword(row,field_size));\n}\nreturn out.map(function(w){ return new Numbas.jme.types.TCodeword(w)});", "parameters": [["words", "list"]]}}, "parts": [{"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>$d(C) = $&nbsp;[[0]]</p>", "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": "<p>Find the minimum distance of the binary code $C$ given by the following parity check matrix.</p>\n<p>\\[ \\mathrm{H} =\\var{H} \\]</p>", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "extensions": ["codewords", "permutations"], "advice": "<p>The minimum distance $d(C)$ is equal to the smallest number of columns of $\\mathrm{H}$ related by a linear dependence.</p>\n<p>{explanation}</p>", "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/"}]}