// Numbas version: finer_feedback_settings
{"name": "Find a parity check matrix for a linear code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Find a parity check matrix for a linear code", "tags": [], "metadata": {"description": "<p>Given a generating matrix for a linear code, give a parity check matrix</p>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>Find a parity check matrix $\\mathrm{H}$ for the {nary} code $C$ with generator matrix</p>\n<p>\\[ \\mathrm{G} =\\var{G} \\]</p>", "advice": "<p>First, row-reduce $\\mathrm{G}$ to obtain&nbsp;a standard generator matrix $\\mathrm{M}$ for the code</p>\n<p>\\[ \\mathrm{G}' = \\var{codeword_matrix(M)} \\]</p>\n<p>This is in the form&nbsp;$(\\mathrm{I}_{\\var{dimension}}|\\mathrm{A})$. A&nbsp;parity check matrix is then&nbsp;$(-\\mathrm{A^T}|\\mathrm{I}_{\\var{word_length}-\\var{dimension}})$, i.e.</p>\n<p>\\[ \\mathrm{H} = \\var{G_dual} \\]</p>\n<p>Note that this is just one possible parity-check matrix. In general any basis for the dual code $C^{\\bot}$ would do for the rows of the parity-check matrix.</p>", "rulesets": {}, "extensions": ["codewords", "permutations"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"M": {"name": "M", "group": "Ungrouped variables", "definition": "identity_left(A)", "description": "<p>Standard generating matrix for the code.</p>", "templateType": "anything", "can_override": false}, "word_length": {"name": "word_length", "group": "Ungrouped variables", "definition": "dimension+random(3..5)", "description": "<p>Length of each word in the code</p>", "templateType": "anything", "can_override": false}, "dimension": {"name": "dimension", "group": "Ungrouped variables", "definition": "3", "description": "<p>Dimension of the code - number of rows in the generating matrix.</p>", "templateType": "anything", "can_override": false}, "dual_dimension": {"name": "dual_dimension", "group": "Ungrouped variables", "definition": "word_length-dimension", "description": "<p>Dimension of the dual code</p>", "templateType": "anything", "can_override": false}, "field_size": {"name": "field_size", "group": "Ungrouped variables", "definition": "random(2,3,5)", "description": "", "templateType": "anything", "can_override": false}, "g_words": {"name": "g_words", "group": "Ungrouped variables", "definition": "shuffle(set_generated_by(M))[0..dimension]", "description": "<p>The&nbsp;generating matrix presented to the student, as a list of codewords.</p>\n<p>The&nbsp;variable testing condition ensures these words are linearly independent.</p>", "templateType": "anything", "can_override": false}, "G_dual": {"name": "G_dual", "group": "Ungrouped variables", "definition": "codeword_matrix(parity_check_matrix(M))", "description": "<p>Parity check matrix for $M$ (a&nbsp;generator matrix for the dual code of $M$)</p>", "templateType": "anything", "can_override": false}, "g": {"name": "g", "group": "Ungrouped variables", "definition": "codeword_matrix(G_words)", "description": "<p>A random generating matrix for the code, not in standard form.</p>", "templateType": "anything", "can_override": false}, "nary": {"name": "nary", "group": "Ungrouped variables", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "description": "", "templateType": "anything", "can_override": false}, "A": {"name": "A", "group": "Ungrouped variables", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)", "description": "<p>The generating matrix is $I_{dim}|A$, where $A$ is random.</p>", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "linearly_independent(G_words)", "maxRuns": 100}, "ungrouped_variables": ["field_size", "nary", "dimension", "word_length", "dual_dimension", "A", "M", "g_words", "g", "G_dual"], "variable_groups": [], "functions": {"identity_right": {"parameters": [["words", "list"]], "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)});"}, "identity_left": {"parameters": [["words", "list"]], "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)});"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>$\\mathrm{H} = $&nbsp;[[0]]</p>", "gaps": [{"type": "matrix", "useCustomName": false, "customName": "", "marks": "3", "scripts": {"mark": {"script": "with(Numbas.extensions.codewords) {\n\n  // convert student's answer to a list of codewords\n  var words = this.studentAnswer.map(function(row) {\n    var digits = row.map(util.parseNumber);\n    return new Numbas.extensions.codewords.Codeword(digits,variables.field_size);\n  })\n\n  this.answered = true;\n\n  // check student's answer is the right size\n  if(this.studentAnswerRows != variables.dual_dimension || this.studentAnswerColumns != variables.word_length) {\n    this.setCredit(0,\"Your answer is incorrect.\");\n    return;\n  }\n  \n  // rows must be linearly independent\n  if(!linearly_independent(words)) {\n    this.setCredit(0,\"Your answer is incorrect.\");\n    return;\n  }\n  \n  // each row in the parity check matrix must be orthogonal to all of the words in the code\n  var wrong = 0;\n  words.map(function(w) {\n    variables.g_words.map(function(g) {\n      var t = 0;\n      for(var i=0;i<w.length;i++) {\n        t += w.digits[i]*g.digits[i];\n      }\n      t = t% variables.field_size;\n      if(t!=0) {\n        wrong += 1;\n      }\n    });\n  });\n\n  if(wrong==0) {\n    this.setCredit(1,\"Your answer is correct.\");\n  } else {\n    this.setCredit(0,\"Your answer is incorrect.\");\n  }\n}", "order": "instead"}}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "G_dual", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "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/"}, {"name": "Chris Graham", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/369/"}]}]}], "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/"}, {"name": "Chris Graham", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/369/"}]}