// Numbas version: exam_results_page_options {"name": "Hamming's [7,4] code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"showfrontpage": false, "preventleave": false, "allowregen": true}, "question_groups": [{"questions": [{"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.

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.

\n

For each word, calculate the parity checks to establish if, and where, any error has occurred.

\n

#### Decoding the received word $\\var{received_words[0]}$

\n

Let $d_1d_2d_3d_4d_5d_6d_7 = \\var{received_words[0]}$. The parity checks give

\n

\\begin{align}
\\end{align}

\n

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])}

\n

We then delete the check digits (the first, second and fourth digits) to obtain the decoded word $\\var{original_words[0]}$.

\n

#### Decoding the received word $\\var{received_words[1]}$

\n

Let $d_1d_2d_3d_4d_5d_6d_7 = \\var{received_words[1]}$. The parity checks give

\n

\\begin{align}
\\end{align}

\n

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])}

\n

We then delete the check digits (the first, second and fourth digits) to obtain the decoded word $\\var{original_words[1]}$.

\n

Putting the two decoded words together, we obtain the decoded message $\\var{original}$.

", "contributors": [{"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/", "name": "Christian Lawson-Perfect"}], "tags": [], "type": "question", "variables": {"num_codewords": {"group": "Ungrouped variables", "name": "num_codewords", "templateType": "anything", "description": "

The number of words in the message

", "definition": "2"}, "encoded_words": {"group": "Ungrouped variables", "name": "encoded_words", "templateType": "anything", "description": "

Each of the original words, encoded using the $[7,4]$ code.

", "definition": "map(hamming_encode(word),word,original_words)"}, "error_positions": {"group": "Ungrouped variables", "name": "error_positions", "templateType": "anything", "description": "

For each encoded word, the position to introduce an error

", "definition": "repeat(random(0..6),num_codewords)"}, "received": {"group": "Ungrouped variables", "name": "received", "templateType": "anything", "description": "

The words as received, i.e. with errors introduced.

", "definition": "map(error(encoded_words[j],error_positions[j]),j,0..num_codewords-1)"}, "original": {"group": "Ungrouped variables", "name": "original", "templateType": "anything", "description": "

The unencoded message - the concatenation of the original words.

", "definition": "concat(original_words)"}, "word_parity_checks": {"group": "Ungrouped variables", "name": "word_parity_checks", "templateType": "anything", "description": "

The parity check for each received word, in the form $c_4c_2c_1$.

", "definition": "map(parity_checks(word),word,received_words)"}, "original_words": {"group": "Ungrouped variables", "name": "original_words", "templateType": "anything", "description": "

Randomly choose binary words of length 4, except 0000.

", "definition": "shuffle(allwords(4,2) except codeword(\"0000\",2))[0..num_codewords]"}, "word_error_positions": {"group": "Ungrouped variables", "name": "word_error_positions", "templateType": "anything", "description": "

The calculated positions of the errors in each received word. Should be the same as error_positions.

", "definition": "map(4*c[0]+2*c[1]+1*c[2],c,word_parity_checks)"}}, "variable_groups": [], "functions": {"error_explanation": {"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}", "language": "javascript", "type": "number", "parameters": [["position", "number"], ["corrected_word", "codeword"]]}, "parity_checks": {"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)", "language": "jme", "type": "list", "parameters": [["word", "codeword"]]}}, "rulesets": {}, "preamble": {"css": "", "js": ""}, "name": "Hamming's [7,4] code", "statement": "

A binary string was encoded using the binary Hamming $[7,4]$ code defined by (and encoded using) check digits, and then transmitted.

\n

The string $\\var{received}$ was received.

", "variablesTest": {"condition": "", "maxRuns": 100}, "parts": [{"scripts": {}, "gaps": [{"scripts": {}, "showCorrectAnswer": true, "displayAnswer": "{string(original)}", "type": "patternmatch", "unitTests": [], "marks": "2", "customMarkingAlgorithm": "", "variableReplacementStrategy": "originalfirst", "answer": "\\s*{string(original)}\\s*", "extendBaseMarkingAlgorithm": true, "variableReplacements": [], "matchMode": "regex", "showFeedbackIcon": true}], "customMarkingAlgorithm": "", "unitTests": [], "marks": 0, "variableReplacementStrategy": "originalfirst", "sortAnswers": false, "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.

\n

Original message: [[0]]

\n

", "showCorrectAnswer": true, "variableReplacements": [], "showFeedbackIcon": true, "type": "gapfill"}]}], "pickingStrategy": "all-ordered"}], "contributors": [{"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/", "name": "Christian Lawson-Perfect"}]}