// Numbas version: finer_feedback_settings
{"name": "Find the syndrome of a word in 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": [{"variable_groups": [], "variables": {"word": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(\n  random(set_generated_by(G_words) except (G_words+[zero(word_length,field_size)])),\n  random(allwords(word_length,field_size) except zero(word_length,field_size))\n)", "description": "<p>A randomly chosen word - 50% of the time it's picked from the code, 50% of the time it's&nbsp;a completely random word.</p>", "name": "word"}, "dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "3", "description": "<p>Dimension of the code - number of rows in the generating matrix.</p>", "name": "dimension"}, "G_dual": {"group": "Ungrouped variables", "templateType": "anything", "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>", "name": "G_dual"}, "G": {"group": "Ungrouped variables", "templateType": "anything", "definition": "codeword_matrix(G_words)", "description": "<p>A random generating matrix for the code, not in standard form.</p>", "name": "G"}, "M": {"group": "Ungrouped variables", "templateType": "anything", "definition": "identity_left(A)", "description": "<p>Standard generating matrix for the code.</p>", "name": "M"}, "word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "dimension+random(3..5)", "description": "<p>Length of each word in the code</p>", "name": "word_length"}, "word_is_in_code_explanation": {"group": "Ungrouped variables", "templateType": "anything", "definition": "if(word_is_in_code,\n  \"$\\\\operatorname{syn} w = \\\\mathbf{0}$, so $w$ is in the code.\", \n  \"$\\\\operatorname{syn} w \\\\neq \\\\mathbf{0}$, so $w$ is not in the code.\"\n)", "description": "", "name": "word_is_in_code_explanation"}, "G_words": {"group": "Ungrouped variables", "templateType": "anything", "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>", "name": "G_words"}, "A": {"group": "Ungrouped variables", "templateType": "anything", "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>", "name": "A"}, "word_is_in_code": {"group": "Ungrouped variables", "templateType": "anything", "definition": "word_syndrome=zero(len(word_syndrome),field_size)", "description": "<p>Word is in the code if its syndrome is zero.</p>", "name": "word_is_in_code"}, "field_size": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2,3,5)", "description": "", "name": "field_size"}, "nary": {"group": "Ungrouped variables", "templateType": "anything", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "description": "", "name": "nary"}, "word_syndrome": {"group": "Ungrouped variables", "templateType": "anything", "definition": "syndrome(word,parity_check_matrix(m))", "description": "<p>Syndrome of word&nbsp;with respect to the parity check matrix.</p>", "name": "word_syndrome"}, "dual_dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "word_length-dimension", "description": "<p>Dimension of the dual code</p>", "name": "dual_dimension"}}, "ungrouped_variables": ["field_size", "nary", "dimension", "word_length", "dual_dimension", "A", "M", "G_words", "G", "G_dual", "word", "word_syndrome", "word_is_in_code", "word_is_in_code_explanation"], "name": "Find the syndrome of a word in a linear code", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Given a generator matrix for a linear code, write a parity check matrix, compute the syndrome of a word, and decide if it's a codeword.</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"]]}, "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>Find the standard parity check matrix $\\mathrm{H}$ for $C$.</p>\n<p>$\\mathrm{H} = $&nbsp;[[0]]</p>", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "markPerCell": false, "allowFractions": false, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "correctAnswer": "G_dual", "allowResize": true, "unitTests": [], "correctAnswerFractions": false, "showFeedbackIcon": true, "scripts": {}, "type": "matrix", "numColumns": 1, "tolerance": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "3", "numRows": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>Find the syndrome of $\\var{word}$ with respect to the parity check matrix $\\mathrm{H}$.</p>\n<p>$\\operatorname{syn}(\\var{word}) = $&nbsp;[[0]]</p>", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{word_syndrome+''}", "showCorrectAnswer": true, "displayAnswer": "{word_syndrome+''}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "2"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"displayType": "radiogroup", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "matrix": "matrix(if(word_is_in_code,[[1],[0]],[[0],[1]]))", "choices": ["<p>Yes</p>", "<p>No</p>"], "prompt": "<p>Is $\\var{word}$ a codeword?</p>", "unitTests": [], "shuffleChoices": false, "showFeedbackIcon": true, "scripts": {}, "maxMarks": 0, "type": "1_n_2", "minMarks": 0, "displayColumns": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "variablesTest": {"condition": "linearly_independent(G_words)", "maxRuns": 100}, "statement": "<p>$C$ is a {nary} linear code with generator matrix</p>\n<p>\\[ \\mathrm{G} =\\var{G} \\]</p>", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "extensions": ["codewords", "permutations"], "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})$. The standard parity check matrix is then&nbsp;$(-\\mathrm{A^T}|\\mathrm{I}_{\\var{word_length-dimension}})$, i.e.</p>\n<p>\\[ \\mathrm{H} = \\var{G_dual} \\]</p>\n<p>If $w = \\var{word}$ then $\\operatorname{syn} w = w \\mathrm{H^T} = \\var{word_syndrome}$.</p>\n<p>{word_is_in_code_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/"}]}