// Numbas version: finer_feedback_settings
{"name": "Lexicographic parity check matrix - ternary, 5-ary or 7-ary", "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": {"error_positions": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(random(0..word_length-1),num_words)", "description": "<p>Positions of&nbsp;the error in each&nbsp;of the&nbsp;received words.</p>", "name": "error_positions"}, "words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(random_combination(gen_matrix),num_words)", "description": "<p>Randomly chosen words from the code.</p>\n<p>The testing condition makes sure they're different.</p>", "name": "words"}, "rows": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2..floor(log(16*(p+1)-1)/log(p)))", "description": "<p>Number of rows in the parity check matrix.</p>\n<p>Upper bound for the random range makes sure&nbsp;the word length is not greater than 16.</p>", "name": "rows"}, "word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "(p^rows-1)/(p-1)", "description": "<p>Length of each codeword</p>", "name": "word_length"}, "received_words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(error(words[j],error_positions[j]),j,0..num_words-1)", "description": "<p>Received words - introduce one error into&nbsp;each of the original words</p>", "name": "received_words"}, "multiply_error": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map((received_words[j]-words[j])[error_positions[j]],j,0..num_words-1)", "description": "<p>Amount added to the changed column in each of the received words - the syndrome will be this many times the &lt;error_position&gt;th column of the parity-check matrix.</p>", "name": "multiply_error"}, "num_words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "2", "description": "<p>Number of words to decode.</p>", "name": "num_words"}, "pcm": {"group": "Ungrouped variables", "templateType": "anything", "definition": "hamming_parity_check_matrix(p,rows)", "description": "<p>Lexicographic parity check matrix for the code.</p>", "name": "pcm"}, "gen_matrix": {"group": "Ungrouped variables", "templateType": "anything", "definition": "hamming_generating_matrix(p,rows)", "description": "<p>Generating matrix for the Hamming code</p>", "name": "gen_matrix"}, "syndromes": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(syndrome(word,pcm),word,received_words)", "description": "<p>Syndrome of each of the received words</p>", "name": "syndromes"}, "columns": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(codeword(x,p),x,list(transpose(codeword_matrix(pcm))))", "description": "<p>Columns of the parity check matrix.</p>", "name": "columns"}, "p": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(3,5,7)", "description": "<p>Size of the field in which the code lives</p>", "name": "p"}}, "ungrouped_variables": ["p", "rows", "pcm", "word_length", "num_words", "gen_matrix", "words", "error_positions", "received_words", "syndromes", "multiply_error", "columns"], "name": "Lexicographic parity check matrix - ternary, 5-ary or 7-ary", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Write down the lexicographic parity check matrix for a Hamming code, and correct two received codewords.</p>"}, "functions": {"nth": {"type": "string", "language": "jme", "definition": "switch(\n  n=1,\"first\",\n  n=2,\"second\",\n  n=3,\"third\",\n  n+\"<sup>th</sup>\"\n)", "parameters": [["n", "number"]]}}, "parts": [{"showCorrectAnswer": true, "markPerCell": false, "allowFractions": false, "customMarkingAlgorithm": "", "allowResize": true, "correctAnswer": "codeword_matrix(pcm)", "prompt": "<p>Write down the lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$.</p>", "unitTests": [], "correctAnswerFractions": false, "numRows": 1, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "matrix", "numColumns": 1, "tolerance": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "2", "showFeedbackIcon": true}, {"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>Use your parity-check matrix to correct the received word $\\var{received_words[0]}$.</p>\n<p>[[0]]</p>", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{words[0]+''}", "showCorrectAnswer": true, "displayAnswer": "{words[0]+''}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "1.5"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>Use your parity-check matrix to correct the received word $\\var{received_words[1]}$.</p>\n<p>[[0]]</p>", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{words[1]+''}", "showCorrectAnswer": true, "displayAnswer": "{words[1]+''}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "1.5"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}], "variablesTest": {"condition": "len(distinct(words))=len(words)", "maxRuns": 100}, "statement": "", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "extensions": ["codewords", "permutations"], "advice": "<h4>a)</h4>\n<p>The lexicographic parity check&nbsp;matrix for&nbsp;$\\operatorname{Ham}_{\\var{p}}(\\var{rows})$&nbsp;has the following properties:</p>\n<ul>\n<li><strong>Property 1:&nbsp;</strong>The first non-zero entry of each column is $1$.</li>\n<li><strong>Property 2:</strong> The columns are ordered from smallest to largest.</li>\n</ul>\n<p>The unique parity-check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$ with this property is</p>\n<p>\\[ \\var{codeword_matrix(pcm)} \\]</p>\n<h4>b)</h4>\n<p>The&nbsp;word $\\var{received_words[0]}$ has syndrome</p>\n<p>\\[ (\\var{received_words[0]}) \\var{transpose(codeword_matrix(pcm))} = (\\var{syndromes[0]}) \\]</p>\n<p>$(\\var{syndromes[0]}) = \\var{multiply_error[0]} \\times (\\var{columns[error_positions[0]]})$. Since $\\var{columns[error_positions[0]]}$ is the {nth(error_positions[0]+1)} column of the parity check matrix, we subtract $\\var{multiply_error[0]}$ from the {nth(error_positions[0]+1)} column to get $\\var{words[0]}$.</p>\n<h4>c)</h4>\n<p>The&nbsp;word $\\var{received_words[1]}$ has syndrome</p>\n<p>\\[ (\\var{received_words[1]}) \\var{transpose(codeword_matrix(pcm))} = (\\var{syndromes[1]}) \\]</p>\n<p>$(\\var{syndromes[1]}) = \\var{multiply_error[1]} \\times (\\var{columns[error_positions[1]]})$. Since $\\var{columns[error_positions[1]]}$ is the {nth(error_positions[1]+1)} column of the parity check matrix, we subtract $\\var{multiply_error[1]}$ from the {nth(error_positions[1]+1)} column to get $\\var{words[1]}$.</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/"}]}