// Numbas version: finer_feedback_settings
{"name": "Lexicographic parity check matrix - binary ", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"parts": [{"showCorrectAnswer": true, "allowFractions": false, "correctAnswer": "codeword_matrix(pcm)", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "prompt": "<p>Write down the lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{if(p=2,'',p)}}(\\var{rows})$.</p>", "unitTests": [], "correctAnswerFractions": false, "allowResize": true, "variableReplacementStrategy": "originalfirst", "showFeedbackIcon": true, "scripts": {}, "type": "matrix", "numColumns": 1, "tolerance": 0, "markPerCell": false, "variableReplacements": [], "marks": 1, "numRows": 1}, {"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": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{words[0]+''}", "displayAnswer": "{words[0]+''}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": 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": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{words[1]+''}", "displayAnswer": "{words[1]+''}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variables": {"error_positions": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(0..word_length-1),num_words)", "name": "error_positions", "description": "<p><span>Positions of&nbsp;the error in each&nbsp;of the&nbsp;received words.</span></p>"}, "words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(hamming_encode(random_word(unencoded_length,2)),num_words)", "name": "words", "description": "<p>Randomly chosen words from the code - pick a random string of the right length, then encode it.</p>\n<p>The testing condition makes sure they're different.</p>"}, "rows": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..4)", "name": "rows", "description": "<p>Number of rows in the parity check matrix.</p>"}, "pcm": {"templateType": "anything", "group": "Ungrouped variables", "definition": "hamming_parity_check_matrix(p,rows)", "name": "pcm", "description": "<p><span>Lexicographic parity check matrix for the code.</span></p>"}, "received_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(error(words[j],error_positions[j]),j,0..num_words-1)", "name": "received_words", "description": "<p><span>Received words - introduce one error into&nbsp;each of the original words</span></p>"}, "multiply_error": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map((received_words[j]-words[j])[error_positions[j]],j,0..num_words-1)", "name": "multiply_error", "description": "<p><span>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.</span></p>\n<p><span>Not really necessary for a&nbsp;binary code because it's always 1, but this is just copied from the&nbsp;n-ary question.</span></p>"}, "num_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "num_words", "description": "<p><span>Number of words to decode.</span></p>"}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(p^rows-1)/(p-1)", "name": "word_length", "description": "<p><span>Length of each codeword</span></p>"}, "syndromes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(syndrome(word,pcm),word,received_words)", "name": "syndromes", "description": "<p><span>Syndrome of each of the received words</span></p>"}, "columns": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(codeword(x,p),x,list(transpose(codeword_matrix(pcm))))", "name": "columns", "description": "<p><span>Columns of the parity check matrix.</span></p>"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "p", "description": "<p><span>Size </span><span>of the f</span><span>ield in which the code lives</span></p>"}, "unencoded_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "word_length-rows", "name": "unencoded_length", "description": "<p>Length of a&nbsp;string which can be encoded to a member of this code.</p>"}}, "ungrouped_variables": ["p", "rows", "pcm", "word_length", "num_words", "unencoded_length", "words", "error_positions", "received_words", "syndromes", "multiply_error", "columns"], "preamble": {"css": "", "js": ""}, "name": "Lexicographic parity check matrix - binary ", "variable_groups": [], "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"]]}}, "variablesTest": {"condition": "len(distinct(words))=len(words)", "maxRuns": 100}, "statement": "", "tags": [], "rulesets": {}, "extensions": ["codewords", "permutations"], "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Write down a lexicographic parity check matrix for a Hamming code and correct two received codewords.</p>"}, "advice": "<h4>a)</h4>\n<p>The lexicographic parity check&nbsp;matrix for&nbsp;$\\operatorname{Ham}(\\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{rows})$ with these&nbsp;properties 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><span>$\\var{syndromes[0]}$&nbsp;is binary for $\\var{error_positions[0]+1}$, so the error is in the {nth(error_positions[0]+1)} digit,&nbsp;and we correct to $\\var{words[0]}$.</span></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]}$ is binary for $\\var{error_positions[1]+1}$, so the error is in the {nth(error_positions[1]+1)} digit,&nbsp;and we correct to $\\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/"}]}