// Numbas version: exam_results_page_options
{"name": "Hamming's square code ", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "<p>Assuming that the received message contains at most one error per codeword, correct any errors, and then decode to find the original binary string.</p>\n<p>Original message:&nbsp;[[0]]</p>\n<p></p>", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "\\s*{string(original)}\\s*", "displayAnswer": "{string(original)}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "2"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variables": {"error_positions": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(0..8),num_codewords)", "description": "<p>Positions of errors in the received (encoded) code words</p>", "name": "error_positions"}, "received_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(\n  error(encoded_original_words[j],error_positions[j]),j,0..(num_codewords-1)\n)", "description": "<p>The received words, with errors applied</p>", "name": "received_words"}, "original": {"templateType": "anything", "group": "Ungrouped variables", "definition": "concat(original_words)", "description": "<p>The original message</p>", "name": "original"}, "received": {"templateType": "anything", "group": "Ungrouped variables", "definition": "concat(received_words)", "description": "<p>The received message</p>", "name": "received"}, "encoded_original_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(hamming_square_encode(word),word,original_words)", "description": "<p>The original words, encoded using the square code</p>", "name": "encoded_original_words"}, "num_codewords": {"templateType": "number", "group": "Ungrouped variables", "definition": "2", "description": "<p>Number of words&nbsp;in the message</p>", "name": "num_codewords"}, "original_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "shuffle(allwords(4,2) except codeword(\"0000\",2))[0..num_codewords]", "description": "<p>Randomly chosen distinct codewords, except <code>0000</code></p>", "name": "original_words"}}, "ungrouped_variables": ["num_codewords", "original_words", "encoded_original_words", "error_positions", "received_words", "original", "received"], "preamble": {"css": "", "js": ""}, "name": "Hamming's square code ", "variable_groups": [], "functions": {"error_description": {"type": "string", "language": "javascript", "definition": "var ordinals = [\"first\",\"second\"];\nvar digits = word.digits.slice();\nvar sentences = [];\n\nvar n = 3;\n\nvar row_error;\nvar column_error;\nfor(var i=0;i<n-1;i++) {\n  var row_sum = 0;\n  var column_sum = 0;\n  for(var j=0;j<n-1;j++) {\n    row_sum += digits[n*i+j];\n    column_sum += digits[n*j+i];\n  }\n  if(row_sum % 2 != digits[n*i+n-1]) {\n    row_error = i;\n    sentences.push(\"The parity check in the \"+ordinals[i]+\" row is incorrect, so we know that there is an error in this row.\");\n  }\n  if(column_sum % 2 != digits[n*(n-1)+i]) {\n    column_error = i;\n    sentences.push(\"The parity check in the \"+ordinals[i]+\" column is incorrect, so we know that there is an error in this column.\");\n  }\n}\nif(row_error!==undefined) {\n  if(column_error!==undefined) {\n    sentences.push(\"So, assuming that only one error has occurred, we know that it must be the digit in the \"+ordinals[row_error]+\" row and \"+ordinals[column_error]+\" column that is wrong,\");\n    digits[row_error*n+column_error]=1-digits[row_error*n+column_error];\n  } else {\n    sentences.push(\"The column check digits are all correct, so the error must be in the \"+ordinals[row_error]+\" row check digit. So the message does not need to be corrected,\");\n  }\n} else {\n  if(column_error!==undefined) {\n    sentences.push(\"The row check digits are all correct, so the error must be in the \"+ordinals[column_error]+\" column check digit. So the message does not need to be corrected,\");\n  } else {\n    sentences.push(\"All the check digits are correct, so the message as received does not need to be corrected,\");\n  }\n}\nvar outdigits = digits.slice(0,2).concat(digits.slice(3,5));\nvar outword = new Numbas.extensions.codewords.Codeword(outdigits,2);\nreturn sentences.join(' ')+\" and we decode as $\"+outword+\"$.\";", "parameters": [["word", "codeword"]]}}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "<p>A binary string was encoded using Hamming's square code, and then transmitted.</p>\n<p>The string $\\var{received}$ was received.&nbsp;</p>", "tags": [], "rulesets": {}, "extensions": ["codewords", "permutations"], "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Correct an error in a received message which was encoded using Hamming's square code</p>"}, "advice": "<p>Since we are using the Hamming square code, each encoded code word is of length $9$. We received $18$ digits, so we have $2$ words to check and decode, $\\var{received_words[0]}$ and $\\var{received_words[1]}$.&nbsp;</p>\n<p><strong>Checking the received word $\\var{received_words[0]}$</strong></p>\n<p>Put this word into a square array.</p>\n<p>{check_array(received_words[0])}</p>\n<p>Since we know that at most one error has occurred we can decode as follows:</p>\n<p>{error_description(received_words[0])}</p>\n<p><strong>Checking the received word $\\var{received_words[1]}$</strong></p>\n<p>Put this word into a square array.</p>\n<p>{check_array(received_words[1])}<strong></strong></p>\n<p>Since we know that at most one error has occurred we can decode as follows:</p>\n<p>{error_description(received_words[1])}</p>\n<p>Putting these decoded messages together, we obtain $\\var{original}$ as the answer.</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/"}]}