// Numbas version: finer_feedback_settings {"name": "Hamming [7,4] code", "extensions": ["codewords"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"functions": {"nth": {"definition": "if(mod(n,10)<4,['th','st','nd','rd'][mod(n,10)],'th')", "type": "string", "parameters": [["n", "number"]], "language": "jme"}}, "name": "Hamming [7,4] code", "tags": [], "type": "question", "advice": "

The message received was $14$ bits long, so it consists of $2$ codewords: $\\var{received_words[0]}$ and $\\var{received_words[1]}$.

\n

In both cases we look at the check digits to see if any error has occurred.

\n

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

\n

Let $\\var{received_words[0]}$ = $d_1d_2d_3d_4d_5d_6d_7$.

\n

Compute the three binary digits of the check number:

\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]}} \\equiv \\var{check_digits[0][0]}  \\pmod 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]}} \\equiv \\var{check_digits[0][1]}  \\pmod 2 \\\\
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]}} \\equiv \\var{check_digits[0][2]}  \\pmod 2 \\\\
\\end{align}

\n

So $c_4c_2c_1 = \\var{check_numbers[0]}_2 = \\var{computed_error_digits[0]}$, i.e. the error is in the {computed_error_digits[0]}{nth(computed_error_digits[0])} digit.

\n

We can correct the received word to $\\var{encoded_words[0]}$. We can then delete the check digits $d_1$,$d_2$ and $d_4$ to decode the word as $\\var{decoded_words[0]}$.

\n

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

\n

Let $\\var{received_words[1]}$ = $d_1d_2d_3d_4d_5d_6d_7$.

\n

Compute the three binary digits of the check number:

\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]}} \\equiv \\var{check_digits[1][0]}  \\pmod 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]}} \\equiv \\var{check_digits[1][1]}  \\pmod 2 \\\\
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]}} \\equiv \\var{check_digits[1][2]}  \\pmod 2 \\\\
\\end{align}

\n

So $c_4c_2c_1 = \\var{check_numbers[1]}_2 = \\var{computed_error_digits[1]}$, i.e. the error is in the {computed_error_digits[1]}{nth(computed_error_digits[1])} digit.

\n

We can correct the received word to $\\var{encoded_words[1]}$. We can then delete the check digits $d_1$,$d_2$ and $d_4$ to decode the word as $\\var{decoded_words[1]}$.

\n

Putting the two decoded words together, we obtain the decoded string $\\var{latex(decoded_string)}$.

", "rulesets": {}, "parts": [{"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.

", "marks": 1, "showCorrectAnswer": true, "displayAnswer": "{decoded_string}", "scripts": {}, "answer": "{decoded_string}", "type": "patternmatch"}], "statement": "

A binary string was encoded using Hamming's $[7,4]$ code, and then transmitted.

\n

The string $\\var{latex(received_string)}$ was received.

", "variable_groups": [], "progress": "in-progress", "preamble": {"css": "", "js": ""}, "variables": {"received_string": {"definition": "join(received_words,'')", "templateType": "anything", "group": "Ungrouped variables", "name": "received_string", "description": ""}, "errors": {"definition": "repeat(random(0..6),num_words)", "templateType": "anything", "group": "Ungrouped variables", "name": "errors", "description": ""}, "decoded_words": {"definition": "map(hamming_decode(word),word,received_words)", "templateType": "anything", "group": "Ungrouped variables", "name": "decoded_words", "description": ""}, "decoded_string": {"definition": "join(decoded_words,'')", "templateType": "anything", "group": "Ungrouped variables", "name": "decoded_string", "description": ""}, "received_words": {"definition": "map(make_error(encoded_words[j],errors[j]),j,0..num_words-1)", "templateType": "anything", "group": "Ungrouped variables", "name": "received_words", "description": ""}, "computed_error_digits": {"definition": "map(\n check_digits[j][0] + \n check_digits[j][1]*2 +\n check_digits[j][2]*4\n,j,0..num_words-1)", "templateType": "anything", "group": "Ungrouped variables", "name": "computed_error_digits", "description": ""}, "show_errors": {"definition": "join(errors,' ')", "templateType": "anything", "group": "Ungrouped variables", "name": "show_errors", "description": ""}, "encoded_words": {"definition": "map(hamming_encode(word),word,words)", "templateType": "anything", "group": "Ungrouped variables", "name": "encoded_words", "description": ""}, "check_numbers": {"definition": "map(codeword([n[2],n[1],n[0]],2),n,check_digits)", "templateType": "anything", "group": "Ungrouped variables", "name": "check_numbers", "description": ""}, "error_messages": {"definition": "[ \"The error is in digit 1, which is a check digit, so \" ]", "templateType": "list of strings", "group": "Ungrouped variables", "name": "error_messages", "description": ""}, "word_length": {"definition": "4", "templateType": "anything", "group": "Ungrouped variables", "name": "word_length", "description": ""}, "words": {"definition": "repeat(codeword(repeat(random(1,0),word_length),2),num_words)", "templateType": "anything", "group": "Ungrouped variables", "name": "words", "description": ""}, "check_digits": {"definition": "map([\n mod(word[0]+word[2]+word[4]+word[6],2),\n mod(word[1]+word[2]+word[5]+word[6],2),\n mod(word[3]+word[4]+word[5]+word[6],2)\n],word,received_words)", "templateType": "anything", "group": "Ungrouped variables", "name": "check_digits", "description": ""}, "show_computed_error_digits": {"definition": "join(computed_error_digits,' ')", "templateType": "anything", "group": "Ungrouped variables", "name": "show_computed_error_digits", "description": ""}, "num_words": {"definition": "2", "templateType": "anything", "group": "Ungrouped variables", "name": "num_words", "description": ""}}, "metadata": {"notes": "", "description": "", "licence": "Creative Commons Attribution 4.0 International"}, "showQuestionGroupNames": false, "question_groups": [{"name": "", "pickingStrategy": "all-ordered", "pickQuestions": 0, "questions": []}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}