Write down the lexicographic parity check matrix and generator matrix for a Hamming code, which is the dual of a Simplex code, then determine if a given word is a codeword of the corresponding Simplex code.
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "", "advice": "The lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$ is
\n\\[ \\mathrm{H} = \\var{codeword_matrix(pcm)} \\]
\nPerforming the column permutation $\\var{perm_arrows(swap)}$ on $\\mathrm{H}$ gives
\n\\[ H^{\\ast} = \\var{permuted_pcm} \\]
\nwhich we can invert (via $(\\mathrm{I}|\\mathrm{A}) \\mapsto (-\\mathrm{A^T}|\\mathrm{I})$), and then perform the reverse permutation, $\\var{perm_arrows(iswap)}$ to get
\n\\[ \\mathrm{G} = \\var{codeword_matrix(gen_matrix)} \\]
\nThis is a generator matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$. It is also a parity-check matrix for its dual code $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
\nUsing $\\mathrm{G}$, we can check whether $w = \\var{word}$ is a codeword of $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$ by calculating its syndrome $w \\mathrm{G^T}$: this is $\\var{syndrome}$. The syndrome is not $\\mathbf{0}$, so $w$ is not a codeword. The syndrome is $\\mathbf{0}$, so $w$ is a codeword.
", "rulesets": {}, "extensions": ["codewords", "permutations"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"syndrome": {"name": "syndrome", "group": "Word to check", "definition": "syndrome(word,gen_matrix)", "description": "Syndrome of the word with respect to the parity check matrix for the simplex code.
", "templateType": "anything", "can_override": false}, "swap": {"name": "swap", "group": "Advice", "definition": "column_swaps(p,rows)", "description": "Column permutation to get the parity-check matrix in a form to work out its dual.
", "templateType": "anything", "can_override": false}, "permuted_pcm": {"name": "permuted_pcm", "group": "Advice", "definition": "transpose(matrix(let(\n columns,list(transpose(codeword_matrix(pcm))),\n map(columns[iswap[j+1]-1],j,0..len(columns)-1)\n)))", "description": "Parity-check matrix with its columns permuted so it's in the form $(I|A)$.
", "templateType": "anything", "can_override": false}, "rows": {"name": "rows", "group": "Setup", "definition": "3", "description": "Number of rows in the parity check matrix.
", "templateType": "anything", "can_override": false}, "p": {"name": "p", "group": "Setup", "definition": "random(2,3)", "description": "Size of the field in which the code lives
", "templateType": "anything", "can_override": false}, "word_length": {"name": "word_length", "group": "Setup", "definition": "(p^rows-1)/(p-1)", "description": "Length of each codeword
", "templateType": "anything", "can_override": false}, "word": {"name": "word", "group": "Word to check", "definition": "let(in_code,set_generated_by(pcm),\n random(\n random(in_code except zero(word_length,p)),\n random_word(word_length,p)\n )\n)", "description": "Either a word from the code, or a word chosen at random from the set of all words. Only about 1.5% of the possible words belong to the code, so we get a word from the code only slightly more than half of the time.
", "templateType": "anything", "can_override": false}, "word_belongs": {"name": "word_belongs", "group": "Word to check", "definition": "is_zero(syndrome)", "description": "Does the word belong to the code? True if the syndrome is zero.
", "templateType": "anything", "can_override": false}, "iswap": {"name": "iswap", "group": "Advice", "definition": "inverse(swap)", "description": "Inverse column permutation, to get a generator matrix for the Hamming code.
", "templateType": "anything", "can_override": false}, "pcm": {"name": "pcm", "group": "Matrices", "definition": "hamming_parity_check_matrix(p,rows)", "description": "Lexicographic parity check matrix for the code. (Also a generator matrix for the simplex code)
", "templateType": "anything", "can_override": false}, "gen_matrix": {"name": "gen_matrix", "group": "Matrices", "definition": "hamming_generating_matrix(p,rows)", "description": "Generating matrix for the Hamming code (also a parity check matrix for the simplex code)
", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [{"name": "Setup", "variables": ["p", "rows", "word_length"]}, {"name": "Matrices", "variables": ["pcm", "gen_matrix"]}, {"name": "Word to check", "variables": ["word", "syndrome", "word_belongs"]}, {"name": "Advice", "variables": ["swap", "iswap", "permuted_pcm"]}], "functions": {"column_swaps": {"parameters": [["p", "number"], ["r", "number"]], "type": "permutation", "language": "javascript", "definition": "var off = 1;\nvar t = 1;\npos = [];\nfor(var i=1;iWrite down the lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$.
", "correctAnswer": "codeword_matrix(pcm)", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"type": "matrix", "useCustomName": false, "customName": "", "marks": "2", "scripts": {}, "customMarkingAlgorithm": "student_bases:\n map(codeword(row,p),row,list(studentmatrix))\n\ngenerated_by_pcm:\n if(is_generated_by(student_basis, pcm),\n correct()\n ,\n incorrect(\"Your answer is not correct - this matrix does not generate $\\\\operatorname{Ham}_{\"+p+\"}(\"+correct_rows+\")$.\")\n )", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Find a generator matrix $\\mathrm{G}$ for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$.
", "correctAnswer": "codeword_matrix(gen_matrix)", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"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": "Use $\\mathrm{G}$ to determine if the word $\\var{word}$ belongs to $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
\n[[0]]
", "gaps": [{"type": "1_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["$\\var{word}$ belongs to $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
", "$\\var{word}$ does not belong to $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
"], "matrix": "if(word_belongs,[1,0],[0,1])"}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}], "resources": []}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}]}