For each encoded word, the position to introduce an error
"}, "word_error_positions": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(4*c[0]+2*c[1]+1*c[2],c,word_parity_checks)", "name": "word_error_positions", "description": "The calculated positions of the errors in each received word. Should be the same as error_positions.
The unencoded message - the concatenation of the original words.
"}, "received": {"templateType": "anything", "group": "Ungrouped variables", "definition": "concat(received_words)", "name": "received", "description": "The received message - the concatenation of the received words
"}, "encoded_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(hamming_encode(word),word,original_words)", "name": "encoded_words", "description": "Each of the original words, encoded using the $[7,4]$ code.
"}, "num_codewords": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "num_codewords", "description": "The number of words in the message
"}, "word_parity_checks": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(parity_checks(word),word,received_words)", "name": "word_parity_checks", "description": "The parity check for each received word, in the form $c_4c_2c_1$.
"}, "original_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "shuffle(allwords(4,2) except codeword(\"0000\",2))[0..num_codewords]", "name": "original_words", "description": "Randomly choose binary words of length 4, except 0000.
The words as received, i.e. with errors introduced.
"}}, "ungrouped_variables": ["num_codewords", "original_words", "original", "encoded_words", "error_positions", "received_words", "received", "word_parity_checks", "word_error_positions"], "name": "Hamming's [7,4] code", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Decode a message of two codewords encoded using Hamming's [7,4] code, with at most one error per codeword.
"}, "functions": {"error_explanation": {"type": "number", "language": "javascript", "definition": "if(position==0) {\n return \"So there is no error in the received word.\"\n} else {\n var ordinals = [\"\",\"first\",\"second\",\"third\",\"fourth\",\"fifth\",\"sixth\",\"seventh\"];\n return \"So there is an error in the \"+ordinals[position]+\" digit, and we correct the received word to $\"+corrected_word.toLaTeX()+\"$.\";\n}", "parameters": [["position", "number"], ["corrected_word", "codeword"]]}, "parity_checks": {"type": "list", "language": "jme", "definition": "// calculate the parity checks for the given word. \n// Returns a codeword c_4c_2c_1\ncodeword(\n map(\n mod(x,2),\n x,\n [\n word[3]+word[4]+word[5]+word[6],\n word[1]+word[2]+word[5]+word[6],\n word[0]+word[2]+word[4]+word[6]\n ]\n ),\n 2\n)", "parameters": [["word", "codeword"]]}}, "parts": [{"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Assuming that the received message contains at most one error per codeword, correct any errors, and then decode to find the original binary string.
\nOriginal message: [[0]]
\n", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "\\s*{string(original)}\\s*", "showCorrectAnswer": true, "displayAnswer": "{string(original)}", "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}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "A binary string was encoded using the binary Hamming $[7,4]$ code defined by (and encoded using) check digits, and then transmitted.
\nThe string $\\var{received}$ was received.
", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "extensions": ["codewords", "permutations"], "advice": "The message we received has $\\var{len(received)}$ digits. Each codeword in Hamming's $[7,4]$ code is $7$ digits long, so we have received $\\var{num_codewords}$ words.
\nFor each word, calculate the parity checks to establish if, and where, any error has occurred.
\nLet $d_1d_2d_3d_4d_5d_6d_7 = \\var{received_words[0]}$. The parity checks give
\n\\begin{align}
c_1 &= d_1 + d_3 + d_5 + d_7 = \\simplify[]{{received_words[0][0]}+{received_words[0][2]}+{received_words[0][4]}+{received_words[0][6]}} = \\var{word_parity_checks[0][2]} \\\\
c_2 &= d_2 + d_3 + d_6 + d_7 = \\simplify[]{{received_words[0][1]}+{received_words[0][2]}+{received_words[0][5]}+{received_words[0][6]}} = \\var{word_parity_checks[0][1]} \\\\
c_4 &= d_4 + d_5 + d_6 + d_7 = \\simplify[]{{received_words[0][3]}+{received_words[0][4]}+{received_words[0][5]}+{received_words[0][6]}} = \\var{word_parity_checks[0][0]} \\\\
\\end{align}
So the checking number is $c_4c_2c_1 = \\var{word_parity_checks[0]}$, which is binary for $\\simplify[]{{4*word_parity_checks[0][0]}+{2*word_parity_checks[0][1]}+{1*word_parity_checks[0][2]}} = \\var{word_error_positions[0]}$. {error_explanation(word_error_positions[0],encoded_words[0])}
\nWe then delete the check digits (the first, second and fourth digits) to obtain the decoded word $\\var{original_words[0]}$.
\nLet $d_1d_2d_3d_4d_5d_6d_7 = \\var{received_words[1]}$. The parity checks give
\n\\begin{align}
c_1 &= d_1 + d_3 + d_5 + d_7 = \\simplify[]{{received_words[1][0]}+{received_words[1][2]}+{received_words[1][4]}+{received_words[1][6]}} = \\var{word_parity_checks[1][2]} \\\\
c_2 &= d_2 + d_3 + d_6 + d_7 = \\simplify[]{{received_words[1][1]}+{received_words[1][2]}+{received_words[1][5]}+{received_words[1][6]}} = \\var{word_parity_checks[1][1]} \\\\
c_4 &= d_4 + d_5 + d_6 + d_7 = \\simplify[]{{received_words[1][3]}+{received_words[1][4]}+{received_words[1][5]}+{received_words[1][6]}} = \\var{word_parity_checks[1][0]} \\\\
\\end{align}
So the checking number is $c_4c_2c_1 = \\var{word_parity_checks[1]}$, which is binary for $\\simplify[]{{4*word_parity_checks[1][0]}+{2*word_parity_checks[1][1]}+{1*word_parity_checks[1][2]}} = \\var{word_error_positions[1]}$. {error_explanation(word_error_positions[1],encoded_words[1])}
\nWe then delete the check digits (the first, second and fourth digits) to obtain the decoded word $\\var{original_words[1]}$.
\nPutting the two decoded words together, we obtain the decoded message $\\var{original}$.
", "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/"}]}