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": [], "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": "Positions of errors in the received (encoded) code words
", "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": "The received words, with errors applied
", "name": "received_words"}, "original": {"templateType": "anything", "group": "Ungrouped variables", "definition": "concat(original_words)", "description": "The original message
", "name": "original"}, "received": {"templateType": "anything", "group": "Ungrouped variables", "definition": "concat(received_words)", "description": "The received message
", "name": "received"}, "encoded_original_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(hamming_square_encode(word),word,original_words)", "description": "The original words, encoded using the square code
", "name": "encoded_original_words"}, "num_codewords": {"templateType": "number", "group": "Ungrouped variables", "definition": "2", "description": "Number of words in the message
", "name": "num_codewords"}, "original_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "shuffle(allwords(4,2) except codeword(\"0000\",2))[0..num_codewords]", "description": "Randomly chosen distinct codewords, except 0000
The string $\\var{received}$ was received.
", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Correct an error in a received message which was encoded using Hamming's square code
"}, "advice": "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]}$.
\nChecking the received word $\\var{received_words[0]}$
\nPut this word into a square array.
\n{check_array(received_words[0])}
\nSince we know that at most one error has occurred we can decode as follows:
\n{error_description(received_words[0])}
\nChecking the received word $\\var{received_words[1]}$
\nPut this word into a square array.
\n{check_array(received_words[1])}
\nSince we know that at most one error has occurred we can decode as follows:
\n{error_description(received_words[1])}
\nPutting these decoded messages together, we obtain $\\var{original}$ as the answer.
"}, {"name": "Hamming's [7,4] code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [], "variables": {"error_positions": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(0..6),num_codewords)", "name": "error_positions", "description": "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"], "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", "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}$.
"}, {"name": "Find all words within given Hamming distance", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"name": "Chris Graham", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/73/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}], "parts": [{"answer": "", "displayAnswer": "{sphere_string}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Enter your answer as a list of codewords, separated by commas. For example: 0000, 0001, 0002.
All words whose Hamming distance from base_word is radius.
Number of choices of digit
"}, "sphere_string": {"templateType": "anything", "group": "Ungrouped variables", "definition": "join(map(string(x),x,sphere),', ')", "name": "sphere_string", "description": "The list of words in sphere, as a string to be used as the displayed answer to the question.
The centre of the ball.
"}, "radius": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..word_length-1)", "name": "radius", "description": "Radius of the Hamming sphere
"}}, "ungrouped_variables": ["word_length", "field_size", "base_word", "radius", "sphere", "sphere_string"], "variable_groups": [], "preamble": {"css": "", "js": ""}, "variablesTest": {"condition": "len(sphere)<15 and len(sphere)>3", "maxRuns": 100}, "statement": "Find all words $w \\in \\mathbb{Z}_{\\var{field_size}}^{\\var{word_length}}$ for which $d_\\mathrm{H}(w,\\var{base_word}) = \\var{radius}$.
", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Find all words with given Hamming distance from a given codeword.
"}, "functions": {}, "advice": "Each word $w$ must differ from the word $\\var{base_word}$ in $\\var{radius}$ {pluralise(radius,\"place\",\"places\")}.
\nThere are $\\simplify{comb({word_length},{radius}) = {comb(word_length,radius)}}$ ways of choosing $\\var{radius}$ {pluralise(radius,\"digit\",\"digits\")} to change, and $\\var{field_size}-1 = \\var{field_size-1}$ {pluralise(field_size-1,\"choice\",\"choices\")} for each changed digit.
\nThat means that there are $\\simplify[]{{comb(word_length,radius)}*{field_size-1}^{radius}} = \\var{comb(word_length,radius)*(field_size-1)^radius}$ words $w$ with $d_\\mathrm{H}(w,\\var{base_word}) = \\var{radius}$.
"}, {"name": "Equivalent codes", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "tags": [], "metadata": {"description": "Compute tables of Hamming distances in given codes, then determine which codes are equivalent.
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "Determine which of the following codes in $\\mathbb{Z}_{\\var{field_size}}^{\\var{word_length}}$ are equivalent.
\n\\begin{align}
C_1 &= \\var{codes[code_order[0]]} & C_2 &= \\var{codes[code_order[1]]} \\\\
C_3 &= \\var{codes[code_order[2]]} & C_4 &= \\var{codes[code_order[3]]} \\\\
C_5 &= \\var{codes[code_order[4]]} & C_6 &= \\var{codes[code_order[5]]} \\\\
C_7 &= \\var{codes[code_order[6]]} & C_8 &= \\var{codes[code_order[7]]} \\\\
\\end{align}
First, compute tables of Hamming distances for each of the codes, and then indicate which pairs of codes are equivalent in the grid at the bottom.
", "advice": "Begin by computing a table of Hamming distances for each code.
\n| \n \\[ C_1 \\] \n{distance_table(codes[code_order[0]])} \n | \n\n \\[ C_2 \\] \n{distance_table(codes[code_order[1]])} \n | \n
| \n \\[ C_3 \\] \n{distance_table(codes[code_order[2]])} \n | \n\n \\[ C_4 \\] \n{distance_table(codes[code_order[3]])} \n | \n
| \n \\[ C_5 \\] \n{distance_table(codes[code_order[4]])} \n | \n\n \\[ C_6 \\] \n{distance_table(codes[code_order[5]])} \n | \n
| \n \\[ C_7 \\] \n{distance_table(codes[code_order[6]])} \n | \n\n \\[ C_8 \\] \n{distance_table(codes[code_order[7]])} \n | \n
First, note that every code is equivalent to itself.
\nTwo codes whose tables contain different numbers cannot be equivalent. Two codes whose tables contain the same numbers might be equivalent, but to prove equivalence you must find a composition of symbolic and positional permutations which map one code to the other.
\n$C_{\\var{equivalence_indices[0][0]}}$ and $C_{\\var{equivalence_indices[0][1]}}$ are equivalent: to obtain $C_{\\var{inverse_code_order[5]+1}}$ from $C_{\\var{inverse_code_order[0]+1}}$, {explain_permutation(composed_permutations[0])}
\n$C_{\\var{equivalence_indices[1][0]}}$ and $C_{\\var{equivalence_indices[1][1]}}$ are equivalent: to obtain $C_{\\var{inverse_code_order[6]+1}}$ from $C_{\\var{inverse_code_order[1]+1}}$, {explain_permutation(composed_permutations[1])}
\n$C_{\\var{equivalence_indices[2][0]}}$ and $C_{\\var{equivalence_indices[2][1]}}$ are equivalent: to obtain $C_{\\var{inverse_code_order[7]+1}}$ from $C_{\\var{inverse_code_order[2]+1}}$, {explain_permutation(composed_permutations[2])}
\n$C_{\\var{inverse_code_order[3]+1}}$ and $C_{\\var{inverse_code_order[4]+1}}$ are not equivalent to each other, or any of the other codes.
", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"base_codes": {"name": "base_codes", "group": "Ungrouped variables", "definition": "repeat(code(shuffle(allwords(word_length,field_size))[0..num_words]),5)", "description": "5 distinct codes which aren't equivalent to each other (enforced by testing condition)
", "templateType": "anything", "can_override": false}, "positional_permutations": {"name": "positional_permutations", "group": "Ungrouped variables", "definition": "permutations(deal(word_length),word_length)", "description": "Every possible positional permutation on the codewords
", "templateType": "anything", "can_override": false}, "equivalence_indices": {"name": "equivalence_indices", "group": "Ungrouped variables", "definition": "map(\n [min(inverse_code_order[j],inverse_code_order[j+5])+1,max(inverse_code_order[j],inverse_code_order[j+5])+1],\n j,\n 0..2\n)", "description": "For each pair of equivalent codes, sort their indices so the smallest goes first.
\n(Not really necessary, and arguably pointless because the pairs don't get shown in ascending index order)
", "templateType": "anything", "can_override": false}, "equivalence_matrix": {"name": "equivalence_matrix", "group": "Ungrouped variables", "definition": "matrix(map(\n map(\n unshuffled_equivalence_matrix[a][b],\n b,\n code_order\n ),\n a,\n code_order\n))", "description": "The matrix of equivalencies between the codes, in the order the student sees them.
", "templateType": "anything", "can_override": false}, "inverse_code_order": {"name": "inverse_code_order", "group": "Ungrouped variables", "definition": "inverse_permutation(code_order)", "description": "The inverse shuffling of the codes, so we can refer to codes $C_i$.
", "templateType": "anything", "can_override": false}, "codes": {"name": "codes", "group": "Ungrouped variables", "definition": "base_codes+equivalent_codes", "description": "All the codes shown to the student - base codes plus equivalent codes.
\nNot shown in this order!
", "templateType": "anything", "can_override": false}, "num_words": {"name": "num_words", "group": "Ungrouped variables", "definition": "4", "description": "Number of words in each code
", "templateType": "anything", "can_override": false}, "field_size": {"name": "field_size", "group": "Ungrouped variables", "definition": "2", "description": "Field each code belongs to
", "templateType": "anything", "can_override": false}, "symbolic_permutations": {"name": "symbolic_permutations", "group": "Ungrouped variables", "definition": "product_n(\n repeat(permutations(list(0..field_size-1),field_size),word_length)\n)", "description": "Every possible symbolic permutation on the codewords.
", "templateType": "anything", "can_override": false}, "unshuffled_equivalence_matrix": {"name": "unshuffled_equivalence_matrix", "group": "Ungrouped variables", "definition": "matrix([\n [1,0,0,0,0,1,0,0],\n [0,1,0,0,0,0,1,0],\n [0,0,1,0,0,0,0,1],\n [0,0,0,1,0,0,0,0],\n [0,0,0,0,1,0,0,0],\n [1,0,0,0,0,1,0,0],\n [0,1,0,0,0,0,1,0],\n [0,0,1,0,0,0,0,1]\n])", "description": "The matrix of equivalencies between the codes, before they're shuffled.
", "templateType": "anything", "can_override": false}, "word_length": {"name": "word_length", "group": "Ungrouped variables", "definition": "4", "description": "Length of words in each code
", "templateType": "anything", "can_override": false}, "equivalents_marking_matrix": {"name": "equivalents_marking_matrix", "group": "Ungrouped variables", "definition": "(\nequivalence_matrix // 1 mark for each correct tick\n- id(8)*(1-1/8) // but each tick on the diagonal is only worth 1/8\n+(equivalence_matrix-matrix(repeat(repeat(1,8),8))) // each incorrect tick subtracts 1\n)", "description": "", "templateType": "anything", "can_override": false}, "composed_permutations": {"name": "composed_permutations", "group": "Ungrouped variables", "definition": "shuffle(product(positional_permutations,symbolic_permutations))[0..3]", "description": "Three randomly-chosen compositions of a positional permutation and a symbolic permutation.
", "templateType": "anything", "can_override": false}, "equivalent_codes": {"name": "equivalent_codes", "group": "Ungrouped variables", "definition": "map(\n positional_permutation(\n symbolic_permutation(\n base_codes[j],composed_permutations[j][1]\n ),\n composed_permutations[j][0]\n ),\n j,\n 0..2\n)", "description": "For each of the first three base codes, an equivalent code produced by a positional and symbolic permutation.
", "templateType": "anything", "can_override": false}, "code_order": {"name": "code_order", "group": "Ungrouped variables", "definition": "deal(len(codes))", "description": "The order to show the codes in.
", "templateType": "anything", "can_override": false}, "word_distances": {"name": "word_distances", "group": "Ungrouped variables", "definition": "map(\n map(hamming_distance(w[0],w[1]),w,product(code[0..len(code)],code[0..len(code)])),\n code,\n codes\n)", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "// none of the base codes are equivalent to each other\nsum(map(\n if(x[0]=x[1],\n 0,\n if(equivalent(base_codes[x[0]],base_codes[x[1]]),\n 1,\n 0\n )\n ),\n x,\n product([0,1,2,3,4],[0,1,2,3,4])\n))=0\n\nand\n\n// none of the \"equivalent\" codes are exactly the same as the base code they're equivalent to\nsum(map(\n if(base_codes[j]=equivalent_codes[j],1,0),\n j,\n 0..2\n))=0", "maxRuns": "100"}, "ungrouped_variables": ["word_length", "field_size", "num_words", "base_codes", "positional_permutations", "symbolic_permutations", "composed_permutations", "equivalent_codes", "codes", "code_order", "unshuffled_equivalence_matrix", "equivalence_matrix", "inverse_code_order", "equivalence_indices", "word_distances", "equivalents_marking_matrix"], "variable_groups": [], "functions": {"distance_table": {"parameters": [["code", "code"]], "type": "html", "language": "javascript", "definition": "// table of distances between each of the words in code\n\nvar hamming_distance = Numbas.extensions.codewords.hamming_distance;\n\nvar table = document.createElement('table');\ntable.setAttribute('class','distance-table');\nvar header = document.createElement('tr');\nheader.appendChild(document.createElement('td'));\ntable.appendChild(header);\nvar rows = [];\nfor(var i=0;i$C_1$
\n| \n | $\\var{codes[code_order[0]][0]}$ | $\\var{codes[code_order[0]][1]}$ | $\\var{codes[code_order[0]][2]}$ | $\\var{codes[code_order[0]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[0]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[0]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[0]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[0]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
$C_2$
\n| \n | $\\var{codes[code_order[1]][0]}$ | $\\var{codes[code_order[1]][1]}$ | $\\var{codes[code_order[1]][2]}$ | $\\var{codes[code_order[1]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[1]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[1]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[1]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[1]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
$C_3$
\n| \n | $\\var{codes[code_order[2]][0]}$ | $\\var{codes[code_order[2]][1]}$ | $\\var{codes[code_order[2]][2]}$ | $\\var{codes[code_order[2]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[2]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[2]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[2]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[2]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
$C_4$
\n| \n | $\\var{codes[code_order[3]][0]}$ | $\\var{codes[code_order[3]][1]}$ | $\\var{codes[code_order[3]][2]}$ | $\\var{codes[code_order[3]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[3]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[3]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[3]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[3]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
$C_5$
\n| \n | $\\var{codes[code_order[4]][0]}$ | $\\var{codes[code_order[4]][1]}$ | $\\var{codes[code_order[4]][2]}$ | $\\var{codes[code_order[4]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[4]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[4]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[4]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[4]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
$C_6$
\n| \n | $\\var{codes[code_order[5]][0]}$ | $\\var{codes[code_order[5]][1]}$ | $\\var{codes[code_order[5]][2]}$ | $\\var{codes[code_order[5]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[5]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[5]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[5]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[5]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
$C_7$
\n| \n | $\\var{codes[code_order[6]][0]}$ | $\\var{codes[code_order[6]][1]}$ | $\\var{codes[code_order[6]][2]}$ | $\\var{codes[code_order[6]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[6]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[6]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[6]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[6]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
$C_8$
\n| \n | $\\var{codes[code_order[7]][0]}$ | $\\var{codes[code_order[7]][1]}$ | $\\var{codes[code_order[7]][2]}$ | $\\var{codes[code_order[7]][3]}$ |
|---|---|---|---|---|
| $\\var{codes[code_order[7]][0]}$ | \n[[0]] | \n\n | \n | \n |
| $\\var{codes[code_order[7]][1]}$ | \n[[1]] | \n[[2]] | \n\n | \n |
| $\\var{codes[code_order[7]][2]}$ | \n[[3]] | \n[[4]] | \n[[5]] | \n\n |
| $\\var{codes[code_order[7]][3]}$ | \n[[6]] | \n[[7]] | \n[[8]] | \n[[9]] | \n
In the grid below, tick each box which corresponds to a pair of equivalent codes.
", "minMarks": 0, "maxMarks": 0, "minAnswers": 0, "maxAnswers": 0, "shuffleChoices": false, "shuffleAnswers": false, "displayType": "checkbox", "warningType": "none", "showCellAnswerState": true, "choices": ["$C_1$", "$C_2$", "$C_3$", "$C_4$", "$C_5$", "$C_6$", "$C_7$", "$C_8$"], "matrix": "equivalents_marking_matrix", "layout": {"type": "strictlowertriangle", "expression": ""}, "answers": ["$C_1$", "$C_2$", "$C_3$", "$C_4$", "$C_5$", "$C_6$", "$C_7$", "$C_8$"]}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question"}, {"name": "Information rate and minimum distance", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variablesTest": {"condition": "max(minimum_distances)>1 // at least one code has minimum distance greater than 1\nand\nlen(distinct(information_rates))=len(information_rates) // all the codes have different information rates", "maxRuns": 100}, "variables": {"codes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(\n code(shuffle(allwords(word_lengths[j],2))[0..num_words[j]]),\n j,\n 0..2\n)", "name": "codes", "description": "Each code picks num_words random binary words of length word_lengths
Number of words in each code
"}, "minimum_distances": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(minimum_distance(x),x,codes)", "name": "minimum_distances", "description": "Minimum distance of each code
"}, "word_lengths": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(3..6),3)", "name": "word_lengths", "description": "Lengths of the words in each code
"}, "information_rates": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(information_rate(code),code,codes)", "name": "information_rates", "description": "Information rate of each code
"}}, "ungrouped_variables": ["word_lengths", "num_words", "codes", "minimum_distances", "information_rates"], "functions": {"distance_table": {"type": "html", "language": "javascript", "definition": "// table of distances between each of the words in code\n\nvar hamming_distance = Numbas.extensions.codewords.hamming_distance;\n\nvar table = document.createElement('table');\ntable.setAttribute('class','distance-table');\nvar header = document.createElement('tr');\nheader.appendChild(document.createElement('td'));\ntable.appendChild(header);\nvar rows = [];\nfor(var i=0;i$C_1 = \\var{codes[0]}$
\nInformation rate: [[0]]
\nMinimum distance: [[1]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customMarkingAlgorithm": "", "variableReplacementStrategy": "originalfirst", "gaps": [{"precisionPartialCredit": "0", "mustBeReduced": false, "type": "numberentry", "correctAnswerStyle": "plain", "variableReplacementStrategy": "originalfirst", "mustBeReducedPC": 0, "precisionMessage": "You have not given your answer to the correct precision.", "notationStyles": ["plain", "en", "si-en"], "correctAnswerFraction": false, "variableReplacements": [], "allowFractions": false, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "minValue": "information_rates[1]", "maxValue": "information_rates[1]", "precision": "3", "unitTests": [], "precisionType": "dp", "showPrecisionHint": false, "strictPrecision": false, "scripts": {}, "showCorrectAnswer": true, "marks": 1, "showFeedbackIcon": true}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "correctAnswerFraction": false, "minValue": "minimum_distances[1]", "maxValue": "minimum_distances[1]", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "mustBeReducedPC": 0}], "prompt": "$C_2 = \\var{codes[1]}$
\nInformation rate: [[0]]
\nMinimum distance: [[1]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customMarkingAlgorithm": "", "variableReplacementStrategy": "originalfirst", "gaps": [{"precisionPartialCredit": "0", "mustBeReduced": false, "type": "numberentry", "correctAnswerStyle": "plain", "variableReplacementStrategy": "originalfirst", "mustBeReducedPC": 0, "precisionMessage": "You have not given your answer to the correct precision.", "notationStyles": ["plain", "en", "si-en"], "correctAnswerFraction": false, "variableReplacements": [], "allowFractions": false, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "minValue": "information_rates[2]", "maxValue": "information_rates[2]", "precision": "3", "unitTests": [], "precisionType": "dp", "showPrecisionHint": false, "strictPrecision": false, "scripts": {}, "showCorrectAnswer": true, "marks": 1, "showFeedbackIcon": true}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "correctAnswerFraction": false, "minValue": "minimum_distances[2]", "maxValue": "minimum_distances[2]", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "mustBeReducedPC": 0}], "prompt": "$C_3 = \\var{codes[2]}$
\nInformation rate: [[0]]
\nMinimum distance: [[1]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}], "statement": "Find the information rates and minimum distances of the following three codes.
\nRound your answers to 3 decimal places.
", "tags": [], "rulesets": {}, "preamble": {"css": ".distance-table td {\n text-align: center;\n}\n.distance-table th:first-child {\n border-right: 1px solid black;\n}\n.distance-table tr:first-child th {\n border-bottom: 1px solid black;\n}\n.distance-table td.empty {\n background: #eee;\n}", "js": ""}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Compute the information rate and minimum distance of some binary codes.
"}, "advice": "$C_1 = \\var{codes[0]}$ has $\\var{num_words[0]}$ words, each of length $\\var{word_lengths[0]}$.
\nIts information rate is therefore $\\displaystyle\\frac{\\log_2 \\var{num_words[0]}}{\\var{word_lengths[0]}} = \\var{precround(information_rates[0],3)}$ to 3 decimal places.
\nThe minimum distance $d(C_1)$ of $C_1$ is the smallest Hamming distance between distinct codewords of $C_1$.
\nHere's a table of the Hamming distances between the words in $C_1$.
\n{distance_table(codes[0])}
\nThe minimum distance between distinct codewords of $C_1$ is $d(C_1) = \\var{minimum_distances[0]}$.
\n$C_2 = \\var{codes[1]}$ has $\\var{num_words[1]}$ words, each of length $\\var{word_lengths[1]}$.
\nIts information rate is therefore $\\displaystyle\\frac{\\log_2 \\var{num_words[1]}}{\\var{word_lengths[1]}} = \\var{precround(information_rates[1],3)}$ to 3 decimal places.
\nThe minimum distance $d(C_2)$ of $C_2$ is the smallest Hamming distance between distinct codewords of $C_2$.
\nHere's a table of the Hamming distances between the words in $C_2$.
\n{distance_table(codes[1])}
\nThe minimum distance between distinct codewords of $C_2$ is $d(C_2) = \\var{minimum_distances[1]}$.
\n$C_3 = \\var{codes[2]}$ has $\\var{num_words[2]}$ words, each of length $\\var{word_lengths[2]}$.
\nIts information rate is therefore $\\displaystyle\\frac{\\log_2 \\var{num_words[2]}}{\\var{word_lengths[2]}} = \\var{precround(information_rates[2],3)}$ to 3 decimal places.
\nThe minimum distance $d(C_3)$ of $C_3$ is the smallest Hamming distance between distinct codewords of $C_3$.
\nHere's a table of the Hamming distances between the words in $C_3$.
\n{distance_table(codes[2])}
\nThe minimum distance between distinct codewords of $C_3$ is $d(C_3) = \\var{minimum_distances[2]}$.
"}, {"name": "Upper and lower bounds for number of codewords in a maximal code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"name": "Chris Graham", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/73/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}], "parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "A maximal code over $\\mathbb{Z}_{\\var{field_sizes[0]}}$ with $n = \\var{code_lengths[0]}$ and $d = \\var{min_distances[0]}$.
\n[[0]] $\\leq M \\leq$ [[1]]
\nEnter the bounds as integers.
", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{gilbert_varshamov_bound(field_sizes[0],code_lengths[0],min_distances[0])}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{upper_bounds[0]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "A maximal code over $\\mathbb{Z}_{\\var{field_sizes[1]}}$ with $n = \\var{code_lengths[1]}$ and $d = \\var{min_distances[1]}$.
\n[[0]] $\\leq M \\leq$ [[1]]
\nEnter the bounds as integers.
", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{lower_bounds[1]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{upper_bounds[1]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "A maximal code over $\\mathbb{Z}_{\\var{field_sizes[2]}}$ with $n = \\var{code_lengths[2]}$ and $d = \\var{min_distances[2]}$.
\n[[0]] $\\leq M \\leq$ [[1]]
\nEnter the bounds as integers.
", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "{lower_bounds[2]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{upper_bounds[2]}", "showCorrectAnswer": true, "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "checkVariableNames": false, "checkingType": "absdiff", "vsetRange": [0, 1], "type": "jme", "showFeedbackIcon": true, "scripts": {}, "vsetRangePoints": 5, "expectedVariableNames": [], "unitTests": [], "checkingAccuracy": 0.001, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variables": {"errors_corrected": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(ceil(x/2)-1,x,min_distances)", "name": "errors_corrected", "description": "Number of errors corrected by each code - biggest $t$ satisfying $d \\gt 2t$.
"}, "min_distances": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(random(3..min(5,code_length-2)),code_length,code_lengths)", "name": "min_distances", "description": "Minimum distance of each code
"}, "hamming_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(hamming_bound(field_sizes[k],code_lengths[k],errors_corrected[k]),k,0..2)", "name": "hamming_bounds", "description": "Hamming bound on the maximum number of words in each code
"}, "upper_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(min(hamming_bounds[k],singleton_bounds[k]),k,0..2)", "name": "upper_bounds", "description": "Upper bound on the maximum number of words in each code - smallest of Hamming and Singleton bounds
"}, "singleton_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(singleton_bound(field_sizes[k],code_lengths[k],min_distances[k]),k,0..2)", "name": "singleton_bounds", "description": "Singleton bound on the maximum number of words in each code
"}, "lower_bounds": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(gilbert_varshamov_bound(field_sizes[k],code_lengths[k],min_distances[k]),k,0..2)", "name": "lower_bounds", "description": "Lower bound on the maximum number of words in each code - Gilbert-Varshamov bound.
"}, "code_lengths": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(random(5..log(10^9)/log(field_size)),field_size,field_sizes)", "name": "code_lengths", "description": "The lengths of words in each code.
\nTop end of the range confined so $\\text{field_size}^{\\text{code_length}} \\leq 10^9$, so the student can do all calculations on a calculator.
"}, "field_sizes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "shuffle([2,3,5,7])[0..3]", "name": "field_sizes", "description": "Size $n$ of the field $\\mathbb{Z}_n$ each code lives in.
"}}, "ungrouped_variables": ["field_sizes", "code_lengths", "min_distances", "hamming_bounds", "singleton_bounds", "upper_bounds", "lower_bounds", "errors_corrected"], "variable_groups": [], "preamble": {"css": "", "js": ""}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "Using the Hamming, Singleton and Gilbert–Varshamov bounds, give upper and lower bounds for the number of codewords in the following maximal codes with the given parameters, where $n$ is the codeword length and $d$ is the minimum distance between codewords.
\nYour bounds should be given as integers. The lower bound should be the least integer greater than or equal to the Gilbert–Varshamov bound and the upper bound the greatest integer less than or equal to the least value given by the Hamming and Singleton bounds.
", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Find upper and lower bounds on the number of codewords in three maximal codes given their codeword lengths and minimum distances.
\nUses Hamming, Singleton and Gilbert-Varshamov bounds.
"}, "functions": {}, "advice": "The Gilbert-Varshamov bound gives a lower bound for $M$. The Hamming and Singleton bounds give upper bounds, so use the lowest of those.
\nThe Gilbert-Varshamov bound gives
\n\\begin{align}
M
&\\geq \\frac{ \\var{field_sizes[0]}^{\\var{code_lengths[0]}} }{ \\sum_{i=0}^{\\var{min_distances[0]}-1} \\binom{\\var{code_lengths[0]}}{i} \\left( \\var{field_sizes[0]}-1 \\right)^{i} } \\\\ \\\\
&= \\frac{\\var{field_sizes[0]^code_lengths[0]}}{\\var{sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(min_distances[0]-1)))}} \\\\ \\\\
&\\approx \\var{precround((field_sizes[0]^code_lengths[0])/sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(min_distances[0]-1))),2)}
\\end{align}
So we can say that $M \\geq \\var{lower_bounds[0]}$.
\nThe minimum distance between codewords in this code is $\\var{min_distances[0]}$, and $d \\gt 2t$, so it corrects at most $t = \\var{errors_corrected[0]}$ {pluralise(errors_corrected[0],\"error\",\"errors\")}.
\nThe Hamming bound for $M$ is thus
\n\\begin{align}
M &\\leq \\frac{ \\var{field_sizes[0]}^{\\var{code_lengths[0]}} } { \\sum_{i=0}^{\\var{errors_corrected[0]}} \\binom{\\var{code_lengths[0]}}{i} \\left( \\var{field_sizes[0]}-1 \\right)^{i} } \\\\ \\\\
&= \\frac{\\var{field_sizes[0]^code_lengths[0]}}{\\var{sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(errors_corrected[0])))}} \\\\ \\\\
&\\approx \\var{precround((field_sizes[0]^code_lengths[0])/sum(map(comb(code_lengths[0],k)*(field_sizes[0]-1)^k,k,0..(errors_corrected[0]))),2)}
\\end{align}
So we can say that $M \\leq \\var{hamming_bounds[0]}$.
\nThe Singleton bound gives $M \\leq \\simplify[]{ {field_sizes[0]}^({code_lengths[0]}-{min_distances[0]}+1) } \\leq \\var{field_sizes[0]}^{\\var{code_lengths[0]-min_distances[0]+1}} = \\var{field_sizes[0]^(code_lengths[0]-min_distances[0]+1)}$.
\nThe {if(hamming_bounds[0]<singleton_bounds[0],\"Hamming\",\"Singleton\")} bound is lower than the {if(hamming_bounds[0]<singleton_bounds[0],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.
\nFinally, we can say that $\\var{lower_bounds[0]} \\leq M \\leq \\var{upper_bounds[0]}$.
\nThe Gilbert-Varshamov bound gives
\n\\begin{align}
M
&\\geq \\frac{ \\var{field_sizes[1]}^{\\var{code_lengths[1]}} }{ \\sum_{i=0}^{\\var{min_distances[1]}-1} \\binom{\\var{code_lengths[1]}}{i} \\left( \\var{field_sizes[1]}-1 \\right)^{i} } \\\\ \\\\
&= \\frac{\\var{field_sizes[1]^code_lengths[1]}}{\\var{sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(min_distances[1]-1)))}} \\\\ \\\\
&\\approx \\var{precround((field_sizes[1]^code_lengths[1])/sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(min_distances[1]-1))),2)}
\\end{align}
So we can say that $M \\geq \\var{lower_bounds[1]}$.
\nThe minimum distance between codewords in this code is $\\var{min_distances[1]}$, and $d \\gt 2t$, so it corrects at most $t = \\var{errors_corrected[1]}$ {pluralise(errors_corrected[1],\"error\",\"errors\")}.
\nThe Hamming bound for $M$ is thus
\n\\begin{align}
M &\\leq \\frac{ \\var{field_sizes[1]}^{\\var{code_lengths[1]}} } { \\sum_{i=0}^{\\var{errors_corrected[1]}} \\binom{\\var{code_lengths[1]}}{i} \\left( \\var{field_sizes[1]}-1 \\right)^{i} } \\\\ \\\\
&= \\frac{\\var{field_sizes[1]^code_lengths[1]}}{\\var{sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(errors_corrected[1])))}} \\\\ \\\\
&\\approx \\var{precround((field_sizes[1]^code_lengths[1])/sum(map(comb(code_lengths[1],k)*(field_sizes[1]-1)^k,k,0..(errors_corrected[1]))),2)}
\\end{align}
So we can say that $M \\leq \\var{hamming_bounds[1]}$.
\nThe Singleton bound gives $M \\leq \\simplify[]{ {field_sizes[1]}^({code_lengths[1]}-{min_distances[1]}+1) } \\leq \\var{field_sizes[1]}^{\\var{code_lengths[1]-min_distances[1]+1}} = \\var{field_sizes[1]^(code_lengths[1]-min_distances[1]+1)}$.
\nThe {if(hamming_bounds[1]<singleton_bounds[1],\"Hamming\",\"Singleton\")} bound is lower than the {if(hamming_bounds[1]<singleton_bounds[1],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.
\nFinally, we can say that $\\var{lower_bounds[1]} \\leq M \\leq \\var{upper_bounds[1]}$.
\nThe Gilbert-Varshamov bound gives
\n\\begin{align}
M
&\\geq \\frac{ \\var{field_sizes[2]}^{\\var{code_lengths[2]}} }{ \\sum_{i=0}^{\\var{min_distances[2]}-1} \\binom{\\var{code_lengths[2]}}{i} \\left( \\var{field_sizes[2]}-1 \\right)^{i} } \\\\ \\\\
&= \\frac{\\var{field_sizes[2]^code_lengths[2]}}{\\var{sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(min_distances[2]-1)))}} \\\\ \\\\
&\\approx \\var{precround((field_sizes[2]^code_lengths[2])/sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(min_distances[2]-1))),2)}
\\end{align}
So we can say that $M \\geq \\var{lower_bounds[2]}$.
\nThe minimum distance between codewords in this code is $\\var{min_distances[2]}$, and $d \\gt 2t$, so it corrects at most $t = \\var{errors_corrected[2]}$ {pluralise(errors_corrected[2],\"error\",\"errors\")}.
\nThe Hamming bound for $M$ is thus
\n\\begin{align}
M &\\leq \\frac{ \\var{field_sizes[2]}^{\\var{code_lengths[2]}} } { \\sum_{i=0}^{\\var{errors_corrected[2]}} \\binom{\\var{code_lengths[2]}}{i} \\left( \\var{field_sizes[2]}-1 \\right)^{i} } \\\\ \\\\
&= \\frac{\\var{field_sizes[2]^code_lengths[2]}}{\\var{sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(errors_corrected[2])))}} \\\\ \\\\
&\\approx \\var{precround((field_sizes[2]^code_lengths[2])/sum(map(comb(code_lengths[2],k)*(field_sizes[2]-1)^k,k,0..(errors_corrected[2]))),2)}
\\end{align}
So we can say that $M \\leq \\var{hamming_bounds[2]}$.
\nThe Singleton bound gives $M \\leq \\simplify[]{ {field_sizes[2]}^({code_lengths[2]}-{min_distances[2]}+1) } \\leq \\var{field_sizes[2]}^{\\var{code_lengths[2]-min_distances[2]+1}} = \\var{field_sizes[2]^(code_lengths[2]-min_distances[2]+1)}$.
\nThe {if(hamming_bounds[2]<singleton_bounds[2],\"Hamming\",\"Singleton\")} bound is lower than the {if(hamming_bounds[2]<singleton_bounds[2],\"Singleton\",\"Hamming\")} bound, so we use that as the upper bound for $M$.
\nFinally, we can say that $\\var{lower_bounds[2]} \\leq M \\leq \\var{upper_bounds[2]}$.
"}, {"name": "List all vectors in spanning set", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [], "variables": {"word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(random(3..6),num_parts)", "name": "word_length", "description": "Length of words in each span
"}, "spanning_set": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(set_generated_by(x),x,generators)", "name": "spanning_set", "description": "All the words in each span.
\nThe testing condition makes sure there are no more than 15 words in each span.
"}, "num_parts": {"group": "Ungrouped variables", "templateType": "anything", "definition": "3", "name": "num_parts", "description": "Number of parts in the question (i.e., number of spanning sets to generate)
"}, "field_size": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(random(2..3),num_parts)", "name": "field_size", "description": "Field size for each span
"}, "num_words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(random(2..3),num_parts)", "name": "num_words", "description": "Number of words in each span
"}, "generators": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(sort(shuffle(allwords(word_length[j],field_size[j]))[0..num_words[j]]),j,0..num_parts-1)", "name": "generators", "description": "Sets of words generating each span - shown to the student.
"}, "generated_code": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(code(x),x,spanning_set)", "name": "generated_code", "description": ""}}, "ungrouped_variables": ["num_parts", "field_size", "word_length", "num_words", "generators", "spanning_set", "generated_code"], "functions": {"show_span": {"type": "string", "language": "jme", "definition": "// LaTeX representation of a span - words separated by commas, surrounded by angle brackets\nlatex('\\\\langle '+join_words(words)+' \\\\rangle')", "parameters": [["words", "list"]]}, "join_words": {"type": "string", "language": "jme", "definition": "// LaTeX representation of a list of words, separated by commas\nlatex(join(map('\\\\mathtt{'+x+'}',x,words),','))", "parameters": [["words", "list"]]}}, "parts": [{"answer": "", "displayAnswer": "{join(map(string(x),x,spanning_set[0]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{latex(show_span(generators[0]))} \\subset \\mathbb{Z}_{\\var{field_size[0]}}^{\\var{word_length[0]}}$
", "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_spanning_set(this,variables.field_size[0],variables.generated_code[0]);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}, {"answer": "", "displayAnswer": "{join(map(string(x),x,spanning_set[1]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{latex(show_span(generators[1]))} \\subset \\mathbb{Z}_{\\var{field_size[1]}}^{\\var{word_length[1]}}$
", "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_spanning_set(this,variables.field_size[1],variables.generated_code[1]);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}, {"answer": "", "displayAnswer": "{join(map(string(x),x,spanning_set[2]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{latex(show_span(generators[2]))} \\subset \\mathbb{Z}_{\\var{field_size[2]}}^{\\var{word_length[2]}}$
", "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_spanning_set(this,variables.field_size[2],variables.generated_code[2]);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}], "statement": "List all of the vectors in the following spans.
\nEnter each answer as a list of vectors, separated by commas. For example, 000,001,002.
List all vectors in a spanning set.
\n(repeated 3 times)
"}, "advice": "$\\var{show_span(generators[0])}$ is the set of all linear combinations of the vectors $\\var{join_words(generators[0])}$.
\nEvery vector in the span is the sum of {join(list(0..field_size[0]-2),',')} or {field_size[0]-1} times each of the given vectors. That is, every vector in the span has the form
\n\\[ w = \\var{latex(join(map('\\\\lambda_{j+1} \\\\times \\\\mathtt{'+generators[0][j]+'}',j,0..num_words[0]-1),'+'))} \\]
\nThe set of vectors in the span is thus
\n\\[ \\var{latex(join_words(spanning_set[0]))} \\]
\n$\\var{show_span(generators[1])}$ is the set of all linear combinations of the vectors $\\var{join_words(generators[1])}$.
\nEvery vector in the span is the sum of {join(list(0..field_size[1]-2),',')} or {field_size[1]-1} times each of the given vectors. That is, every vector in the span has the form
\n\\[ w = \\var{latex(join(map('\\\\lambda_{j+1} \\\\times \\\\mathtt{'+generators[1][j]+'}',j,0..num_words[1]-1),'+'))} \\]
\nThe set of vectors in the span is thus
\n\\[ \\var{latex(join_words(spanning_set[1]))} \\]
\n$\\var{show_span(generators[2])}$ is the set of all linear combinations of the vectors $\\var{join_words(generators[2])}$.
\nEvery vector in the span is the sum of {join(list(0..field_size[2]-2),',')} or {field_size[2]-1} times each of the given vectors. That is, every vector in the span has the form
\n\\[ w = \\var{latex(join(map('\\\\lambda_{j+1} \\\\times \\\\mathtt{'+generators[2][j]+'}',j,0..num_words[2]-1),'+'))} \\]
\nThe set of vectors in the span is thus
\n\\[ \\var{latex(join_words(spanning_set[2]))} \\]
"}, {"name": "Find a basis for the span of a set of vectors", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{code(shown_words[0])} \\subset \\mathbb{Z}_{\\var{field_size[0]}}^{\\var{word_length[0]}}$
\n[[0]]
", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "", "displayAnswer": "{join(map(string(x),x,basis[0]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_basis(this,variables.field_size[0],variables.shown_words[0]);", "order": "instead"}, "validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "2"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{code(shown_words[1])} \\subset \\mathbb{Z}_{\\var{field_size[1]}}^{\\var{word_length[1]}}$
\n[[0]]
", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "", "displayAnswer": "{join(map(string(x),x,basis[1]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_basis(this,variables.field_size[1],variables.shown_words[1]);", "order": "instead"}, "validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "2"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{code(shown_words[2])} \\subset \\mathbb{Z}_{\\var{field_size[2]}}^{\\var{word_length[2]}}$
\n[[0]]
", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"answer": "", "displayAnswer": "{join(map(string(x),x,basis[2]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_basis(this,variables.field_size[2],variables.shown_words[2]);", "order": "instead"}, "validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "2"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variables": {"basis": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(rref[j] except zero(word_length[j],field_size[j]),j,0..num_parts-1)", "description": "", "name": "basis"}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(4..6),num_parts)", "description": "", "name": "word_length"}, "shown_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(\n shuffle(\n span[j] except zero(word_length[j],field_size[j])\n )[0..random(5..6)],\n j,\n 0..num_parts-1\n)", "description": "", "name": "shown_words"}, "rref_matrix": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(\n matrix(map(x[0..word_length[j]],x,rref[j])),\n j,\n 0..2\n)", "description": "", "name": "rref_matrix"}, "num_parts": {"templateType": "anything", "group": "Ungrouped variables", "definition": "3", "description": "", "name": "num_parts"}, "field_size": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(2,3,5),num_parts)", "description": "", "name": "field_size"}, "rref": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(reduced_row_echelon_form(x),x,shown_words)", "description": "", "name": "rref"}, "generating_set": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(shuffle(allwords(word_length[j],field_size[j]))[0..random(3..4)],j,0..num_parts-1)", "description": "", "name": "generating_set"}, "span": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(set_generated_by(x),x,generating_set)", "description": "", "name": "span"}, "codeword_matrix": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(\n matrix(map(x[0..word_length[j]],x,shown_words[j])),\n j,\n 0..2\n)", "description": "", "name": "codeword_matrix"}}, "ungrouped_variables": ["num_parts", "field_size", "word_length", "generating_set", "span", "shown_words", "codeword_matrix", "rref", "rref_matrix", "basis"], "preamble": {"css": "", "js": "question.mark_basis = function(part,field_size,shown_words) {\n with(Numbas.extensions.codewords) {\n // check input is valid and parse as a list of words\n mark_codeword_set(part,field_size,function(words) {\n // answer is valid\n part.answered = true;\n \n // check words given are linearly independent\n if(!linearly_independent(words)) {\n part.setCredit(0,\"The set of vectors you gave is not linearly independent.\");\n return;\n }\n \n // check that all of the shown words are in the set generated by the student's basis\n var span = new Code(set_generated_by(words));\n var not_generated = []\n shown_words.map(function(word) {\n if(!span.contains(word)) {\n not_generated.push(word);\n }\n });\n \n // if any words aren't generated by the basis, no marks\n if(not_generated.length) {\n part.setCredit(0,\"Your basis does not generate all of the given vectors.\");\n return;\n }\n \n // otherwise, student's basis is correct!\n part.setCredit(1,\"Your answer is correct.\");\n });\n }\n}"}, "variable_groups": [], "functions": {}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "Find bases for the spans of the following sets.
\nEnter each answer as a list of vectors separated by commas.
", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given a set of vectors, find a basis which generates their span as a subspace of $\\mathbb{Z}_n$.
"}, "advice": "We can find a basis by forming a matrix whose rows are the given vectors:
\n\\[ \\var{codeword_matrix[0]} \\]
\nRow-reduce this matrix to obtain the echelon form
\n\\[ \\var{rref_matrix[0]} \\]
\nTake the non-zero rows of this matrix as a set of basis vectors, i.e. $\\var{latex(join(map(latex(x),x,basis[0]),', '))}$. This is only one of many possible bases for the given vectors.
\nWe can find a basis by forming a matrix whose rows are the given vectors:
\n\\[ \\var{codeword_matrix[1]} \\]
\nRow-reduce this matrix to obtain the echelon form
\n\\[ \\var{rref_matrix[1]} \\]
\nTake the non-zero rows of this matrix as a set of basis vectors, i.e. $\\var{latex(join(map(latex(x),x,basis[1]),', '))}$. This is only one of many possible bases for the given vectors.
\nWe can find a basis by forming a matrix whose rows are the given vectors:
\n\\[ \\var{codeword_matrix[2]} \\]
\nRow-reduce this matrix to obtain the echelon form
\n\\[ \\var{rref_matrix[2]} \\]
\nTake the non-zero rows of this matrix as a set of basis vectors, i.e. $\\var{latex(join(map(latex(x),x,basis[2]),', '))}$. This is only one of many possible bases for the given vectors.
"}, {"name": "Find a basis for the row space of a matrix", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [], "variables": {"codeword_matrix": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(\n matrix(map(x[0..word_length[j]],x,shown_words[j])),\n j,\n 0..num_parts-1\n)", "name": "codeword_matrix", "description": ""}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(4..6),num_parts)", "name": "word_length", "description": ""}, "generating_set": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(shuffle(allwords(word_length[j],field_size[j]))[0..random(3..4)],j,0..num_parts-1)", "name": "generating_set", "description": ""}, "shown_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(shuffle(span[j] except zero(word_length[j],field_size[j]))[0..random(3..4)],j,0..num_parts-1)", "name": "shown_words", "description": ""}, "num_parts": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "num_parts", "description": ""}, "field_size": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(2,3,5),num_parts)", "name": "field_size", "description": ""}, "rref": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(reduced_row_echelon_form(x),x,shown_words)", "name": "rref", "description": ""}, "basis": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(rref[j] except zero(word_length[j],field_size[j]),j,0..num_parts-1)", "name": "basis", "description": ""}, "span": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(set_generated_by(x),x,generating_set)", "name": "span", "description": ""}, "rref_matrix": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(\n matrix(map(x[0..word_length[j]],x,rref[j])),\n j,\n 0..num_parts-1\n)", "name": "rref_matrix", "description": ""}}, "ungrouped_variables": ["num_parts", "field_size", "word_length", "generating_set", "span", "shown_words", "codeword_matrix", "rref", "rref_matrix", "basis"], "functions": {}, "preamble": {"css": "", "js": "question.mark_basis = function(part,field_size,shown_words) {\n with(Numbas.extensions.codewords) {\n // check input is valid and parse as a list of words\n mark_codeword_set(part,field_size,function(words) {\n // answer is valid\n this.answered = true;\n \n // check words given are linearly independent\n if(!linearly_independent(words)) {\n this.setCredit(0,\"The set of vectors you gave is not linearly independent.\");\n return;\n }\n \n // check that all of the shown words are in the set generated by the student's basis\n var span = new Code(set_generated_by(words));\n var not_generated = []\n shown_words.map(function(word) {\n if(!span.contains(word)) {\n not_generated.push(word);\n }\n });\n \n // if any words aren't generated by the basis, no marks\n if(not_generated.length) {\n this.setCredit(0,\"Your basis does not generate every row of the given matrix.\");\n return;\n }\n \n // otherwise, student's basis is correct!\n this.setCredit(1,\"Your answer is correct.\");\n });\n }\n}"}, "parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{matrix(map(x[0..word_length[0]],x,shown_words[0]))}$ in $\\mathbb{Z}_{\\var{field_size[0]}}$.
\n[[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "", "displayAnswer": "{join(map(string(x),x,basis[0]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_basis(this,variables.field_size[0],variables.shown_words[0]);", "order": "instead"}, "validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "2"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$\\var{matrix(map(x[0..word_length[1]],x,shown_words[1]))}$ in $\\mathbb{Z}_{\\var{field_size[1]}}$.
\n[[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "", "displayAnswer": "{join(map(string(x),x,basis[1]),',')}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {"mark": {"script": "question.mark_basis(this,variables.field_size[1],variables.shown_words[1]);", "order": "instead"}, "validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "2"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}], "statement": "Find bases for the row spaces of the following matrices.
\nEnter each answer as a list of vectors separated by commas.
", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given a matrix in the field $\\mathbb{Z}_n$. By reducing it to row-echelon form (or otherwise), find a basis for the row space of the matrix, as a list of vectors.
"}, "variablesTest": {"condition": "sum(map(\n if(linearly_independent(x),0,1),\n x,\n shown_words\n))>1", "maxRuns": 100}, "advice": "We can find a basis by row-reducing the given matrix to echelon form:
\n\\[ \\var{rref_matrix[0]} \\]
\nTake the non-zero rows of this matrix as a set of basis vectors, i.e. $\\var{latex(join(map(latex(x),x,basis[0]),', '))}$. This is only one of many possible bases for the row space of the given matrix.
\nWe can find a basis by row-reducing the given matrix to echelon form:
\n\\[ \\var{rref_matrix[1]} \\]
\nTake the non-zero rows of this matrix as a set of basis vectors, i.e. $\\var{latex(join(map(latex(x),x,basis[1]),', '))}$. This is only one of many possible bases for the row space of the given matrix.
"}, {"name": "Construct a Slepian array and find coset leaders", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "tags": [], "metadata": {"description": "Given a generating matrix for a binary linear code, construct a parity check matrix, list all the codewords, list all the words in a given coset, give coset leaders, calculate syndromes for each coset, correct a codeword with one error.
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "$C$ is a {nary} linear code with generator matrix
\n\\[ \\mathrm{G} =\\var{G} \\]
", "advice": "Since the reduced row echelon form of $\\mathrm{G}$ is in standard form, we can write down the standard parity check matrix,
\n\\[ \\mathrm{H} = \\var{G_dual} \\]
\nThe code consists of all possible combinations of the rows of $\\mathrm{G}$. There are 3 words in the basis, so $2^3 = 8$ words in the whole code $C$.
\nNow we need to write out a Slepian array for $C$. Each row of the Slepian array corresponds to a coset of $C$.
\nThere are various solutions for the Slepian array, depending on our choice of coset leaders. A natural solution is
\n{table(map(map(inline_latex(y),y,x),x,slepian_array(g_words)),[])}
\nThis is constructed by first writing out all the codewords of $C$ as the first row and then, to obtain each subsequent row, finding the word of minimum weight which isn't already in the array, and adding it to all the words of $C$.
\nThe coset containing $\\var{word}$ is the row of the Slepian array in which it occurs. That is,
\n$\\var{latex(join(map(latex(x),x,word_coset),' \\\\quad '))}$
\nThe coset leader of a coset is an element of minimum weight. There could be more than one choice of coset leader for a coset.
\nThe first column of the Slepian array gives a set of coset leaders.
\nThe syndrome of a word $w$ with respect to a parity matrix $\\mathrm{H}$ is $w\\mathrm{H^T}$.
\nFor example, the syndrome of $\\var{coset_leaders[1]}$ is
\n\\[ \\operatorname{syn} (\\var{coset_leaders[1]}) = (\\var{coset_leaders[1]}) \\var{transpose(G_dual)} = \\var{syndromes[1]} \\]
\nOne way of decoding the given word is to find it in the Slepian array, and correct it to the corresponding word in the same column of the first row.
\nAnother way is to compute its syndrome, and subtract the coset leader with the corresponding syndrome.
\nWe can find that $\\operatorname{syn}(\\var{received_word}) = \\var{syndrome(received_word,pcm)}$. This corresponds to the coset with leader $\\var{received_word-transmitted_word}$, so the received word should be corrected to $\\var{received_word} - \\var{received_word-transmitted_word} = \\var{transmitted_word}$.
", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"dimension": {"name": "dimension", "group": "Ungrouped variables", "definition": "3", "description": "Dimension of the code - number of rows in the generating matrix.
", "templateType": "anything", "can_override": false}, "unique_coset_leader_indices": {"name": "unique_coset_leader_indices", "group": "Ungrouped variables", "definition": "filter(\n len(filter(weight(slep[j][k])=weight(coset_leaders[j]),k,0..len(slep[j])-1))=1,\n j,\n 1..len(slep)-1\n)", "description": "Indices of coset leaders with only one choice of coset leader
", "templateType": "anything", "can_override": false}, "word": {"name": "word", "group": "Ungrouped variables", "definition": "random(allwords(word_length,field_size) except C_words)", "description": "A randomly chosen word not from the coset.
", "templateType": "anything", "can_override": false}, "A": {"name": "A", "group": "Ungrouped variables", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)", "description": "The generating matrix is $I_{dim}|A$, where $A$ is random.
", "templateType": "anything", "can_override": false}, "slep": {"name": "slep", "group": "Ungrouped variables", "definition": "slepian_array(g_words)", "description": "", "templateType": "anything", "can_override": false}, "C": {"name": "C", "group": "Ungrouped variables", "definition": "code(C_words)", "description": "The code generated by the generator matrix $G$
", "templateType": "anything", "can_override": false}, "syndromes": {"name": "syndromes", "group": "Ungrouped variables", "definition": "map(syndrome(x,pcm),x,coset_leaders)", "description": "", "templateType": "anything", "can_override": false}, "coset_leaders": {"name": "coset_leaders", "group": "Ungrouped variables", "definition": "map(x[0],x,slep)", "description": "", "templateType": "anything", "can_override": false}, "received_word": {"name": "received_word", "group": "Ungrouped variables", "definition": "transmitted_word+coset_leaders[random(unique_coset_leader_indices)]\n//error(transmitted_word,random(0..word_length-1))", "description": "Received word - a codeword with one error introduced.
\nThe testing condition ensures this isn't a codeword - this could happen if two codewords have Hamming distance 1, i.e. 00..1..00 is a codeword.
\nThere's always a valid codeword - the code is generated by three words but each word has length 6, so there are always at least 3 words 00..1..00 that don't belong to the code.
", "templateType": "anything", "can_override": false}, "word_length": {"name": "word_length", "group": "Ungrouped variables", "definition": "6", "description": "Length of each word in the code
", "templateType": "anything", "can_override": false}, "word_coset": {"name": "word_coset", "group": "Ungrouped variables", "definition": "slep[word_index]", "description": "The coset containing word
Dimension of the dual code
", "templateType": "anything", "can_override": false}, "q": {"name": "q", "group": "Ungrouped variables", "definition": "received_word-transmitted_word", "description": "", "templateType": "anything", "can_override": false}, "C_words": {"name": "C_words", "group": "Ungrouped variables", "definition": "set_generated_by(G_words)", "description": "", "templateType": "anything", "can_override": false}, "g_words": {"name": "g_words", "group": "Ungrouped variables", "definition": "shuffle(set_generated_by(M))[0..dimension]", "description": "The generating matrix presented to the student, as a list of codewords.
\nThe variable testing condition ensures these words are linearly independent.
", "templateType": "anything", "can_override": false}, "G_dual": {"name": "G_dual", "group": "Ungrouped variables", "definition": "codeword_matrix(pcm)", "description": "Parity check matrix for $M$ (a generator matrix for the dual code of $M$)
", "templateType": "anything", "can_override": false}, "transmitted_word": {"name": "transmitted_word", "group": "Ungrouped variables", "definition": "random(C_words except zero(word_length,field_size))", "description": "", "templateType": "anything", "can_override": false}, "pcm": {"name": "pcm", "group": "Ungrouped variables", "definition": "parity_check_matrix(M)", "description": "", "templateType": "anything", "can_override": false}, "M": {"name": "M", "group": "Ungrouped variables", "definition": "identity_left(A)", "description": "Standard generating matrix for the code.
", "templateType": "anything", "can_override": false}, "word_index": {"name": "word_index", "group": "Ungrouped variables", "definition": "let(syn_word,syndrome(word,pcm),\n sum(map(if(syndromes[x]=syn_word,x,0),x,0..len(coset_leaders)-1))\n)", "description": "The index of the coset containing word
A random generating matrix for the code, not in standard form.
", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "linearly_independent(G_words)\nand\nlen(unique_coset_leader_indices)<>0\nand\nnot (received_word in c_words)", "maxRuns": "100"}, "ungrouped_variables": ["field_size", "nary", "dimension", "word_length", "dual_dimension", "A", "M", "g_words", "g", "pcm", "G_dual", "slep", "coset_leaders", "syndromes", "C_words", "C", "word", "word_index", "word_coset", "transmitted_word", "received_word", "q", "unique_coset_leader_indices"], "variable_groups": [], "functions": {"identity_right": {"parameters": [["words", "list"]], "type": "list", "language": "javascript", "definition": "// add an identity matrix to the right of a matrix of codewords\nvar k = words.length;\nvar field_size = words[0].field_size;\nvar out = [];\nfor(var i=0;i$\\mathrm{H} = $ [[0]]
", "gaps": [{"type": "matrix", "useCustomName": false, "customName": "", "marks": "2", "scripts": {"mark": {"script": "with(Numbas.extensions.codewords) {\n\n // convert student's answer to a list of codewords\n var words = this.studentAnswer.map(function(row) {\n var digits = row.map(util.parseNumber);\n return new Numbas.extensions.codewords.Codeword(digits,variables.field_size);\n })\n\n this.answered = true;\n\n // check student's answer is the right size\n if(this.studentAnswerRows != variables.dual_dimension || this.studentAnswerColumns != variables.word_length) {\n this.setCredit(0,\"Your answer is incorrect.\");\n return;\n }\n \n // rows must be linearly independent\n if(!linearly_independent(words)) {\n this.setCredit(0,\"Your answer is incorrect.\");\n return;\n }\n \n // each row in the parity check matrix must be orthogonal to all of the words in the code\n var wrong = 0;\n words.map(function(w) {\n variables.g_words.map(function(g) {\n var t = 0;\n for(var i=0;iEnter your answer as a list of codewords separated by commas, e.g. 0000,1111,...
List the words in the coset containing $\\var{word}$.
", "answer": "", "displayAnswer": "{join(map(string(x),x,word_coset),',')}", "matchMode": "regex"}, {"type": "patternmatch", "useCustomName": false, "customName": "", "marks": "1.5", "scripts": {"mark": {"script": "with(Numbas.extensions.codewords) {\n mark_codeword_set(this,variables.field_size,function(words) {\n this.answered = true;\n\n var basis = variables.g_words;\n \n // check all words are coset leaders - they have minimum weight in their coset\n for(var i=0;iCalculate syndromes for the coset leaders. Enter them as a list of words separated by commas, e.g. 000,111,...
You receive a codeword $\\var{received_word}$ and know there has been one error. Correct the error and enter the corrected codeword.
", "answer": "{transmitted_word+''}", "displayAnswer": "{string(transmitted_word)}", "matchMode": "regex"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question"}, {"name": "Find a generator matrix for a code and decide if it is standard - binary", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [{"variables": ["word_length", "field_size", "num_words", "nary"], "name": "Setup"}, {"variables": ["num_skips", "data_vectors", "independent_combos", "extra_combos", "skips", "rest", "g_standard_bit"], "name": "Random stuff"}, {"variables": ["initial_g", "shuffled_g", "combos", "codewords", "g", "is_standard", "encoded_data_vectors"], "name": "Generator matrix"}, {"variables": ["to_decode", "decoded_word"], "name": "Invert codeword"}], "variables": {"g_standard_bit": {"templateType": "anything", "group": "Random stuff", "definition": "matrix(map(\n let(pos,skip_pos(j,skips),\n map(switch(cIf G is a standard matrix, this is $I_{num_words} + 0_{\\text{num_words} \\times \\text{word_length}}$.
\nOtherwise, it's a matrix with 1s in the leading columns, random numbers in the skipped columns when they're to the right of a leading 1, and 0 everywhere else.
"}, "rest": {"templateType": "anything", "group": "Random stuff", "definition": "matrix(repeat(\n repeat(0,num_words+len(skips))+repeat(random(0..field_size-1),word_length-num_words-len(skips)),\n num_words\n))", "name": "rest", "description": "Random numbers to add on the columns to the right of all of the leading 1s in the generator matrix.
"}, "encoded_data_vectors": {"templateType": "anything", "group": "Generator matrix", "definition": "map(\n codeword(\n vector(v)*codeword_matrix(g),\n field_size\n ),\n v,\n data_vectors\n)", "name": "encoded_data_vectors", "description": ""}, "skips": {"templateType": "anything", "group": "Random stuff", "definition": "sort(shuffle(0..num_words-1)[0..num_skips])", "name": "skips", "description": "columns which would be leading columns in a standard matrix but are instead skipped over
"}, "combos": {"templateType": "anything", "group": "Generator matrix", "definition": "independent_combos+extra_combos", "name": "combos", "description": ""}, "num_words": {"templateType": "anything", "group": "Setup", "definition": "3", "name": "num_words", "description": "The number of basis words to generate.
"}, "independent_combos": {"templateType": "anything", "group": "Random stuff", "definition": "map(\n codeword(repeat(random(0..field_size-1),j)+[random(1..field_size-1)]+repeat(0,num_words-j-1),field_size),\n j,\n 0..num_words-1\n)", "name": "independent_combos", "description": "We'll create the codewords to show the student by taking combinations of the rows of the reduced echelon matrix.
\nTo make sure they're independent, combo $n$ has a non-zero value in column $n$, zeros to the right, and any value to the left.
"}, "num_skips": {"templateType": "anything", "group": "Random stuff", "definition": "random(0,random(1..word_length-num_words))", "name": "num_skips", "description": "Number of columns to skip over in the echelon part.
\nFor a standard matrix, this is zero.
"}, "to_decode": {"templateType": "anything", "group": "Invert codeword", "definition": "random_combination(codewords)", "name": "to_decode", "description": "The codeword for which the student needs to find the corresponding data vector.
"}, "word_length": {"templateType": "anything", "group": "Setup", "definition": "5", "name": "word_length", "description": "The length of each codeword.
"}, "is_standard": {"templateType": "anything", "group": "Generator matrix", "definition": "generator_matrix_is_standard(g)", "name": "is_standard", "description": ""}, "extra_combos": {"templateType": "anything", "group": "Random stuff", "definition": "shuffle(allwords(num_words,field_size) except independent_combos)[0..2]", "name": "extra_combos", "description": "Add a couple of extra combinations which aren't already used, so the size of the set given to the student is bigger than the dimension of the generating matrix.
"}, "decoded_word": {"templateType": "anything", "group": "Invert codeword", "definition": "decode_codeword(to_decode,g)", "name": "decoded_word", "description": "Vectors which, when multiplied by the generator matrix, give the basis vectors.
"}, "initial_g": {"templateType": "anything", "group": "Generator matrix", "definition": "g_standard_bit+rest", "name": "initial_g", "description": "Reduced row echelon form generator matrix.
"}, "field_size": {"templateType": "anything", "group": "Setup", "definition": "2", "name": "field_size", "description": "The field the code is defined over.
"}, "codewords": {"templateType": "anything", "group": "Generator matrix", "definition": "map(\n codeword_sum(map(codeword(combos[y][x]*shuffled_g[x],field_size),x,0..num_words-1)),\n y,\n 0..len(combos)-1\n)", "name": "codewords", "description": "Codewords shown to the student.
\nThey're linear combinations of the rows of shuffled_g.
"}, "nary": {"templateType": "anything", "group": "Setup", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "name": "nary", "description": ""}, "g": {"templateType": "anything", "group": "Generator matrix", "definition": "generator_matrix(codewords)", "name": "g", "description": "Generator matrix for the code generated by basis.
"}, "data_vectors": {"templateType": "anything", "group": "Random stuff", "definition": "shuffle(allwords(len(g),field_size))[0..3]", "name": "data_vectors", "description": ""}, "shuffled_g": {"templateType": "anything", "group": "Generator matrix", "definition": "matrix(shuffle(map(vector(r),r,list(initial_g))))", "name": "shuffled_g", "description": "The rows of the reduced generator matrix, shuffled.
"}}, "ungrouped_variables": [], "functions": {"leading_columns": {"type": "list", "language": "javascript", "definition": "return g.map(function(row){\n for(var i=0;iYes
", "No
"], "prompt": "Is there a standard generator matrix for this code?
", "unitTests": [], "shuffleChoices": false, "showFeedbackIcon": true, "scripts": {}, "maxMarks": 0, "type": "1_n_2", "minMarks": 0, "displayColumns": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}, {"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Encode each of the following data vectors as codewords using the generator matrix you have just found.
\n$\\var{data_vectors[0]} \\mapsto $ [[0]]
\n$\\var{data_vectors[1]} \\mapsto $ [[1]]
\n$\\var{data_vectors[2]} \\mapsto $ [[2]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{string(encoded_data_vectors[0])}", "showCorrectAnswer": true, "displayAnswer": "{string(encoded_data_vectors[0])}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{string(encoded_data_vectors[1])}", "showCorrectAnswer": true, "displayAnswer": "{string(encoded_data_vectors[1])}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}, {"answer": "{string(encoded_data_vectors[2])}", "showCorrectAnswer": true, "displayAnswer": "{string(encoded_data_vectors[2])}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"answer": "{string(decoded_word)}", "showCorrectAnswer": true, "displayAnswer": "{string(decoded_word)}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "What data vector is encoded as $c = \\var{to_decode}$?
", "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "Let $C$ be the {nary} code generated by the following set of codewords.
\n\\[ \\var{join_words(codewords)} \\]
", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given a set of codewords generating a code, write down a generator matrix, encode three data vectors, and decode one codeword.
"}, "advice": "Write down the matrix whose rows are the given codewords:
\n\\[ \\var{codeword_matrix(codewords)} \\]
\nNow reduce this matrix to row echelon form. That means the first non-zero entry in each row is further right than in the row above it and that entry is a 1 and there are only zeros above and below that entry. Remove any rows made up of all zeros.
\nFrom the matrix above, we obtain:
\n\\[ \\mathrm{G} = \\var{codeword_matrix(g)} \\]
\nA generator matrix for a code is a standard generator matrix if it is of the form $(\\mathrm{I}_{k}|\\mathrm{A})$, that is, the $k \\times k$ identity matrix attached to an arbitrary matrix $\\mathrm{A}$.
\nIf a code has a standard generator matrix, the row reduced echelon form will be it.
\n$\\mathrm{G}$ is of the required form, so it is a standard generator matrix.$\\mathrm{G}$ is not of the required form, so it is not a standard generator matrix.
\nTo encode a data vector $\\mathbf{v}$, multiply it on the right by the generator matrix for the code.
\nSo we have:
\n\\begin{align}
\\simplify[rowvector]{{vector(data_vectors[0])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[0])} \\\\[0.5em]
\\simplify[rowvector]{{vector(data_vectors[1])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[1])} \\\\[0.5em]
\\simplify[rowvector]{{vector(data_vectors[2])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[2])} \\\\[0.5em]
\\end{align}
That is,
\n\\begin{align}
\\var{data_vectors[0]} &\\mapsto \\var{encoded_data_vectors[0]} \\\\[1em]
\\var{data_vectors[1]} &\\mapsto \\var{encoded_data_vectors[1]} \\\\[1em]
\\var{data_vectors[2]} &\\mapsto \\var{encoded_data_vectors[2]} \\\\[1em]
\\end{align}
We are looking for a data vector of length $\\var{len(g)}$ which is encoded as $c = \\var{to_decode}$.
\nNote that, since $\\mathrm{G}$ is in reduced echelon form, the leading non-zero entry in each row is $1$, so the elements of the data vector are the digits of $c$ corresponding to each of the columns of $G$ containing a leading non-zero entry. The leading $1$s in $\\mathrm{G}$ are in columns {join(leading_columns(g),', ')}. The corresponding digits of $c$ give the data vector $\\var{decoded_word}$.
\nWe can confirm that this vector is encoded as $c$:
\n\\[ \\simplify[rowvector]{ {vector(decoded_word)}*{codeword_matrix(g)} } = \\var[rowvector]{vector(to_decode)} \\]
"}, {"name": "Find a generator matrix for a code and decide if it is standard - ternary", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [{"variables": ["word_length", "field_size", "num_words", "nary"], "name": "Setup"}, {"variables": ["num_skips", "data_vectors", "independent_combos", "extra_combos", "skips", "rest", "g_standard_bit"], "name": "Random stuff"}, {"variables": ["initial_g", "shuffled_g", "combos", "codewords", "g", "is_standard", "encoded_data_vectors"], "name": "Generator matrix"}, {"variables": ["to_decode", "decoded_word"], "name": "Invert codeword"}], "variables": {"g_standard_bit": {"templateType": "anything", "group": "Random stuff", "definition": "matrix(map(\n let(pos,skip_pos(j,skips),\n map(switch(cIf G is a standard matrix, this is $I_{num_words} + 0_{\\text{num_words} \\times \\text{word_length}}$.
\nOtherwise, it's a matrix with 1s in the leading columns, random numbers in the skipped columns when they're to the right of a leading 1, and 0 everywhere else.
"}, "is_standard": {"templateType": "anything", "group": "Generator matrix", "definition": "generator_matrix_is_standard(g)", "name": "is_standard", "description": ""}, "skips": {"templateType": "anything", "group": "Random stuff", "definition": "sort(shuffle(0..num_words-1)[0..num_skips])", "name": "skips", "description": "columns which would be leading columns in a standard matrix but are instead skipped over
"}, "word_length": {"templateType": "anything", "group": "Setup", "definition": "6", "name": "word_length", "description": "The length of each codeword.
"}, "num_words": {"templateType": "anything", "group": "Setup", "definition": "4", "name": "num_words", "description": "The number of basis words to generate.
"}, "initial_g": {"templateType": "anything", "group": "Generator matrix", "definition": "g_standard_bit+rest", "name": "initial_g", "description": "Reduced row echelon form generator matrix.
"}, "independent_combos": {"templateType": "anything", "group": "Random stuff", "definition": "map(\n codeword(repeat(random(0..field_size-1),j)+[random(1..field_size-1)]+repeat(0,num_words-j-1),field_size),\n j,\n 0..num_words-1\n)", "name": "independent_combos", "description": "We'll create the codewords to show the student by taking combinations of the rows of the reduced echelon matrix.
\nTo make sure they're independent, combo $n$ has a non-zero value in column $n$, zeros to the right, and any value to the left.
"}, "num_skips": {"templateType": "anything", "group": "Random stuff", "definition": "random(0,random(1..word_length-num_words))", "name": "num_skips", "description": "Number of columns to skip over in the echelon part.
\nFor a standard matrix, this is zero.
"}, "codewords": {"templateType": "anything", "group": "Generator matrix", "definition": "map(\n codeword_sum(map(codeword(combos[y][x]*shuffled_g[x],field_size),x,0..num_words-1)),\n y,\n 0..len(combos)-1\n)", "name": "codewords", "description": "Codewords shown to the student.
\nThey're linear combinations of the rows of shuffled_g.
"}, "combos": {"templateType": "anything", "group": "Generator matrix", "definition": "independent_combos+extra_combos", "name": "combos", "description": ""}, "extra_combos": {"templateType": "anything", "group": "Random stuff", "definition": "shuffle(allwords(num_words,field_size) except independent_combos)[0..2]", "name": "extra_combos", "description": "Add a couple of extra combinations which aren't already used, so the size of the set given to the student is bigger than the dimension of the generating matrix.
"}, "decoded_word": {"templateType": "anything", "group": "Invert codeword", "definition": "decode_codeword(to_decode,g)", "name": "decoded_word", "description": "Vectors which, when multiplied by the generator matrix, give the basis vectors.
"}, "to_decode": {"templateType": "anything", "group": "Invert codeword", "definition": "random_combination(codewords)", "name": "to_decode", "description": "The codeword for which the student needs to find the corresponding data vector.
"}, "field_size": {"templateType": "anything", "group": "Setup", "definition": "3", "name": "field_size", "description": "The field the code is defined over.
"}, "rest": {"templateType": "anything", "group": "Random stuff", "definition": "matrix(repeat(\n repeat(0,num_words+len(skips))+repeat(random(0..field_size-1),word_length-num_words-len(skips)),\n num_words\n))", "name": "rest", "description": "Random numbers to add on the columns to the right of all of the leading 1s in the generator matrix.
"}, "nary": {"templateType": "anything", "group": "Setup", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "name": "nary", "description": ""}, "shuffled_g": {"templateType": "anything", "group": "Generator matrix", "definition": "matrix(shuffle(map(vector(r),r,list(initial_g))))", "name": "shuffled_g", "description": "The rows of the reduced generator matrix, shuffled.
"}, "g": {"templateType": "anything", "group": "Generator matrix", "definition": "generator_matrix(codewords)", "name": "g", "description": "Generator matrix for the code generated by basis.
"}, "data_vectors": {"templateType": "anything", "group": "Random stuff", "definition": "shuffle(allwords(len(g),field_size))[0..3]", "name": "data_vectors", "description": ""}, "encoded_data_vectors": {"templateType": "anything", "group": "Generator matrix", "definition": "map(\n codeword(\n vector(v)*codeword_matrix(g),\n field_size\n ),\n v,\n data_vectors\n)", "name": "encoded_data_vectors", "description": ""}}, "ungrouped_variables": [], "functions": {"leading_columns": {"type": "list", "language": "javascript", "definition": "return g.map(function(row){\n for(var i=0;iYes
", "No
"], "extendBaseMarkingAlgorithm": true, "matrix": "if(is_standard,[1,0],[0,1])", "customMarkingAlgorithm": "", "prompt": "Is there a standard generator matrix for this code?
", "unitTests": [], "shuffleChoices": false, "variableReplacementStrategy": "originalfirst", "showFeedbackIcon": true, "scripts": {}, "minMarks": 0, "type": "1_n_2", "maxMarks": 0, "displayColumns": 0, "showCorrectAnswer": true, "variableReplacements": [], "marks": 0}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Encode each of the following data vectors as codewords using the generator matrix you have just found.
\n$\\var{data_vectors[0]} \\mapsto $ [[0]]
\n$\\var{data_vectors[1]} \\mapsto $ [[1]]
\n$\\var{data_vectors[2]} \\mapsto $ [[2]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{string(encoded_data_vectors[0])}", "displayAnswer": "{string(encoded_data_vectors[0])}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}, {"answer": "{string(encoded_data_vectors[1])}", "displayAnswer": "{string(encoded_data_vectors[1])}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}, {"answer": "{string(encoded_data_vectors[2])}", "displayAnswer": "{string(encoded_data_vectors[2])}", "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, "sortAnswers": false}, {"answer": "{string(decoded_word)}", "displayAnswer": "{string(decoded_word)}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "What data vector is encoded as $c = \\var{to_decode}$?
", "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}], "statement": "Let $C$ be the {nary} code generated by the following set of codewords.
\n\\[ \\var{join_words(codewords)} \\]
", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given a set of codewords generating a code, give a generating matrix, encode three data vectors, and decode one codeword.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "Write down the matrix whose rows are the given codewords:
\n\\[ \\var{codeword_matrix(codewords)} \\]
\nNow reduce this matrix to row echelon form. That means the first non-zero entry in each row is further right than in the row above it and that entry is a 1 and there are only zeros above and below that entry. Remove any rows made up of all zeros.
\nFrom the matrix above, we obtain:
\n\\[ \\mathrm{G} = \\var{codeword_matrix(g)} \\]
\nA generator matrix for a code is a standard generator matrix if it is of the form $(\\mathrm{I}_{k}|\\mathrm{A})$, that is, the $k \\times k$ identity matrix attached to an arbitrary matrix $\\mathrm{A}$.
\nIf a code has a standard generator matrix, the row reduced echelon form will be it.
\n$\\mathrm{G}$ is of the required form, so it is a standard generator matrix.$\\mathrm{G}$ is not of the required form, so it is not a standard generator matrix.
\nTo encode a data vector $\\mathbf{v}$, multiply it on the right by the generator matrix for the code.
\nSo we have:
\n\\begin{align}
\\simplify[rowvector]{{vector(data_vectors[0])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[0])} \\\\[0.5em]
\\simplify[rowvector]{{vector(data_vectors[1])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[1])} \\\\[0.5em]
\\simplify[rowvector]{{vector(data_vectors[2])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[2])} \\\\[0.5em]
\\end{align}
That is,
\n\\begin{align}
\\var{data_vectors[0]} &\\mapsto \\var{encoded_data_vectors[0]} \\\\[1em]
\\var{data_vectors[1]} &\\mapsto \\var{encoded_data_vectors[1]} \\\\[1em]
\\var{data_vectors[2]} &\\mapsto \\var{encoded_data_vectors[2]} \\\\[1em]
\\end{align}
We are looking for a data vector of length $\\var{len(g)}$ which is encoded as $c = \\var{to_decode}$.
\nNote that, since $\\mathrm{G}$ is in reduced echelon form, the leading non-zero entry in each row is $1$, so the elements of the data vector are the digits of $c$ corresponding to each of the columns of $G$ containing a leading non-zero entry. The leading $1$s in $\\mathrm{G}$ are in columns {join(leading_columns(g),', ')}. The corresponding digits of $c$ give the data vector $\\var{decoded_word}$.
\nWe can confirm that this vector is encoded as $c$:
\n\\[ \\simplify[rowvector]{ {vector(decoded_word)}*{codeword_matrix(g)} } = \\var[rowvector]{vector(to_decode)} \\]
"}, {"name": "Find a generator matrix for a code and decide if it is standard - $\\mathbb{Z}_5$", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variablesTest": {"condition": "", "maxRuns": 100}, "variables": {"initial_g": {"templateType": "anything", "group": "Generator matrix", "definition": "g_standard_bit+rest", "name": "initial_g", "description": "Reduced row echelon form generator matrix.
"}, "g_standard_bit": {"templateType": "anything", "group": "Random stuff", "definition": "matrix(map(\n let(pos,skip_pos(j,skips),\n map(switch(cIf G is a standard matrix, this is $I_{num_words} + 0_{\\text{num_words} \\times \\text{word_length}}$.
\nOtherwise, it's a matrix with 1s in the leading columns, random numbers in the skipped columns when they're to the right of a leading 1, and 0 everywhere else.
"}, "rest": {"templateType": "anything", "group": "Random stuff", "definition": "matrix(repeat(\n repeat(0,num_words+len(skips))+repeat(random(0..field_size-1),word_length-num_words-len(skips)),\n num_words\n))", "name": "rest", "description": "Random numbers to add on the columns to the right of all of the leading 1s in the generator matrix.
"}, "is_standard": {"templateType": "anything", "group": "Generator matrix", "definition": "generator_matrix_is_standard(g)", "name": "is_standard", "description": ""}, "skips": {"templateType": "anything", "group": "Random stuff", "definition": "sort(shuffle(0..num_words-1)[0..num_skips])", "name": "skips", "description": "columns which would be leading columns in a standard matrix but are instead skipped over
"}, "word_length": {"templateType": "anything", "group": "Setup", "definition": "6", "name": "word_length", "description": "The length of each codeword.
"}, "num_words": {"templateType": "anything", "group": "Setup", "definition": "4", "name": "num_words", "description": "The number of basis words to generate.
"}, "independent_combos": {"templateType": "anything", "group": "Random stuff", "definition": "map(\n codeword(repeat(random(0..field_size-1),j)+[random(1..field_size-1)]+repeat(0,num_words-j-1),field_size),\n j,\n 0..num_words-1\n)", "name": "independent_combos", "description": "We'll create the codewords to show the student by taking combinations of the rows of the reduced echelon matrix.
\nTo make sure they're independent, combo $n$ has a non-zero value in column $n$, zeros to the right, and any value to the left.
"}, "num_skips": {"templateType": "anything", "group": "Random stuff", "definition": "random(0,random(1..word_length-num_words))", "name": "num_skips", "description": "Number of columns to skip over in the echelon part.
\nFor a standard matrix, this is zero.
"}, "combos": {"templateType": "anything", "group": "Generator matrix", "definition": "independent_combos+extra_combos", "name": "combos", "description": ""}, "extra_combos": {"templateType": "anything", "group": "Random stuff", "definition": "shuffle(allwords(num_words,field_size) except independent_combos)[0..2]", "name": "extra_combos", "description": "Add a couple of extra combinations which aren't already used, so the size of the set given to the student is bigger than the dimension of the generating matrix.
"}, "decoded_word": {"templateType": "anything", "group": "Invert codeword", "definition": "decode_codeword(to_decode,g)", "name": "decoded_word", "description": "Vectors which, when multiplied by the generator matrix, give the basis vectors.
"}, "to_decode": {"templateType": "anything", "group": "Invert codeword", "definition": "random_combination(codewords)", "name": "to_decode", "description": "The codeword for which the student needs to find the corresponding data vector.
"}, "field_size": {"templateType": "anything", "group": "Setup", "definition": "5", "name": "field_size", "description": "The field the code is defined over.
"}, "codewords": {"templateType": "anything", "group": "Generator matrix", "definition": "map(\n codeword_sum(map(codeword(combos[y][x]*shuffled_g[x],field_size),x,0..num_words-1)),\n y,\n 0..len(combos)-1\n)", "name": "codewords", "description": "Codewords shown to the student.
\nThey're linear combinations of the rows of shuffled_g.
"}, "g": {"templateType": "anything", "group": "Generator matrix", "definition": "generator_matrix(codewords)", "name": "g", "description": "Generator matrix for the code generated by basis.
"}, "shuffled_g": {"templateType": "anything", "group": "Generator matrix", "definition": "matrix(shuffle(map(vector(r),r,list(initial_g))))", "name": "shuffled_g", "description": "The rows of the reduced generator matrix, shuffled.
"}, "nary": {"templateType": "anything", "group": "Setup", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "name": "nary", "description": ""}, "data_vectors": {"templateType": "anything", "group": "Random stuff", "definition": "shuffle(allwords(len(g),field_size))[0..3]", "name": "data_vectors", "description": ""}, "encoded_data_vectors": {"templateType": "anything", "group": "Generator matrix", "definition": "map(\n codeword(\n vector(v)*codeword_matrix(g),\n field_size\n ),\n v,\n data_vectors\n)", "name": "encoded_data_vectors", "description": ""}}, "ungrouped_variables": [], "functions": {"leading_columns": {"type": "list", "language": "javascript", "definition": "return g.map(function(row){\n for(var i=0;iYes
", "No
"], "extendBaseMarkingAlgorithm": true, "matrix": "if(is_standard,[1,0],[0,1])", "customMarkingAlgorithm": "", "prompt": "Is there a standard generator matrix for this code?
", "unitTests": [], "variableReplacements": [], "shuffleChoices": false, "showFeedbackIcon": true, "scripts": {}, "maxMarks": 0, "type": "1_n_2", "minMarks": 0, "variableReplacementStrategy": "originalfirst", "displayColumns": 0, "marks": 0}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Encode each of the following data vectors as codewords using the generator matrix you have just found.
\n$\\var{data_vectors[0]} \\mapsto $ [[0]]
\n$\\var{data_vectors[1]} \\mapsto $ [[1]]
\n$\\var{data_vectors[2]} \\mapsto $ [[2]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{string(encoded_data_vectors[0])}", "displayAnswer": "{string(encoded_data_vectors[0])}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}, {"answer": "{string(encoded_data_vectors[1])}", "displayAnswer": "{string(encoded_data_vectors[1])}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}, {"answer": "{string(encoded_data_vectors[2])}", "displayAnswer": "{string(encoded_data_vectors[2])}", "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, "sortAnswers": false}, {"answer": "{string(decoded_word)}", "displayAnswer": "{string(decoded_word)}", "customMarkingAlgorithm": "", "variableReplacementStrategy": "originalfirst", "prompt": "What data vector is encoded as $c = \\var{to_decode}$?
", "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "patternmatch", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1}], "statement": "Let $C$ be the {nary} code generated by the following set of codewords.
\n\\[ \\var{join_words(codewords)} \\]
", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given a set of codewords generating a code, give a generating matrix, encode three data vectors, and decode one codeword.
"}, "advice": "Write down the matrix whose rows are the given codewords:
\n\\[ \\var{codeword_matrix(codewords)} \\]
\nNow reduce this matrix to row echelon form. That means the first non-zero entry in each row is further right than in the row above it and that entry is a 1 and there are only zeros above and below that entry. Remove any rows made up of all zeros.
\nFrom the matrix above, we obtain:
\n\\[ \\mathrm{G} = \\var{codeword_matrix(g)} \\]
\nA generator matrix for a code is a standard generator matrix if it is of the form $(\\mathrm{I}_{k}|\\mathrm{A})$, that is, the $k \\times k$ identity matrix attached to an arbitrary matrix $\\mathrm{A}$.
\nIf a code has a standard generator matrix, the row reduced echelon form will be it.
\n$\\mathrm{G}$ is of the required form, so it is a standard generator matrix.$\\mathrm{G}$ is not of the required form, so it is not a standard generator matrix.
\nTo encode a data vector $\\mathbf{v}$, multiply it on the right by the generator matrix for the code.
\nSo we have:
\n\\begin{align}
\\simplify[rowvector]{{vector(data_vectors[0])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[0])} \\\\[0.5em]
\\simplify[rowvector]{{vector(data_vectors[1])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[1])} \\\\[0.5em]
\\simplify[rowvector]{{vector(data_vectors[2])}*{codeword_matrix(g)}} &= \\var[rowvector]{vector(encoded_data_vectors[2])} \\\\[0.5em]
\\end{align}
That is,
\n\\begin{align}
\\var{data_vectors[0]} &\\mapsto \\var{encoded_data_vectors[0]} \\\\[1em]
\\var{data_vectors[1]} &\\mapsto \\var{encoded_data_vectors[1]} \\\\[1em]
\\var{data_vectors[2]} &\\mapsto \\var{encoded_data_vectors[2]} \\\\[1em]
\\end{align}
We are looking for a data vector of length $\\var{len(g)}$ which is encoded as $c = \\var{to_decode}$.
\nNote that, since $\\mathrm{G}$ is in reduced echelon form, the leading non-zero entry in each row is $1$, so the elements of the data vector are the digits of $c$ corresponding to each of the columns of $G$ containing a leading non-zero entry. The leading $1$s in $\\mathrm{G}$ are in columns {join(leading_columns(g),', ')}. The corresponding digits of $c$ give the data vector $\\var{decoded_word}$.
\nWe can confirm that this vector is encoded as $c$:
\n\\[ \\simplify[rowvector]{ {vector(decoded_word)}*{codeword_matrix(g)} } = \\var[rowvector]{vector(to_decode)} \\]
"}, {"name": "Find a parity check matrix for a linear code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}, {"name": "Chris Graham", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/369/"}], "tags": [], "metadata": {"description": "Given a generating matrix for a linear code, give a parity check matrix
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "Find a parity check matrix $\\mathrm{H}$ for the {nary} code $C$ with generator matrix
\n\\[ \\mathrm{G} =\\var{G} \\]
", "advice": "First, row-reduce $\\mathrm{G}$ to obtain a standard generator matrix $\\mathrm{M}$ for the code
\n\\[ \\mathrm{G}' = \\var{codeword_matrix(M)} \\]
\nThis is in the form $(\\mathrm{I}_{\\var{dimension}}|\\mathrm{A})$. A parity check matrix is then $(-\\mathrm{A^T}|\\mathrm{I}_{\\var{word_length}-\\var{dimension}})$, i.e.
\n\\[ \\mathrm{H} = \\var{G_dual} \\]
\nNote that this is just one possible parity-check matrix. In general any basis for the dual code $C^{\\bot}$ would do for the rows of the parity-check matrix.
", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"M": {"name": "M", "group": "Ungrouped variables", "definition": "identity_left(A)", "description": "Standard generating matrix for the code.
", "templateType": "anything", "can_override": false}, "word_length": {"name": "word_length", "group": "Ungrouped variables", "definition": "dimension+random(3..5)", "description": "Length of each word in the code
", "templateType": "anything", "can_override": false}, "dimension": {"name": "dimension", "group": "Ungrouped variables", "definition": "3", "description": "Dimension of the code - number of rows in the generating matrix.
", "templateType": "anything", "can_override": false}, "dual_dimension": {"name": "dual_dimension", "group": "Ungrouped variables", "definition": "word_length-dimension", "description": "Dimension of the dual code
", "templateType": "anything", "can_override": false}, "field_size": {"name": "field_size", "group": "Ungrouped variables", "definition": "random(2,3,5)", "description": "", "templateType": "anything", "can_override": false}, "g_words": {"name": "g_words", "group": "Ungrouped variables", "definition": "shuffle(set_generated_by(M))[0..dimension]", "description": "The generating matrix presented to the student, as a list of codewords.
\nThe variable testing condition ensures these words are linearly independent.
", "templateType": "anything", "can_override": false}, "G_dual": {"name": "G_dual", "group": "Ungrouped variables", "definition": "codeword_matrix(parity_check_matrix(M))", "description": "Parity check matrix for $M$ (a generator matrix for the dual code of $M$)
", "templateType": "anything", "can_override": false}, "g": {"name": "g", "group": "Ungrouped variables", "definition": "codeword_matrix(G_words)", "description": "A random generating matrix for the code, not in standard form.
", "templateType": "anything", "can_override": false}, "nary": {"name": "nary", "group": "Ungrouped variables", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "description": "", "templateType": "anything", "can_override": false}, "A": {"name": "A", "group": "Ungrouped variables", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)", "description": "The generating matrix is $I_{dim}|A$, where $A$ is random.
", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "linearly_independent(G_words)", "maxRuns": 100}, "ungrouped_variables": ["field_size", "nary", "dimension", "word_length", "dual_dimension", "A", "M", "g_words", "g", "G_dual"], "variable_groups": [], "functions": {"identity_right": {"parameters": [["words", "list"]], "type": "list", "language": "javascript", "definition": "var k = words.length;\nvar field_size = words[0].field_size;\nvar out = [];\nfor(var i=0;iDimension of the dual code - number of rows in the parity check matrix.
"}, "explanation": {"templateType": "anything", "group": "Ungrouped variables", "definition": "let(d,min_distance,\n switch(\n d=1,\n \"Column \"+dependent_columns[0]+\" is $\\\\mathbf{0}$, so $d(C) = 1$.\",\n d=2, \n \"There is no $\\\\mathbf{0}$ column, so $d(C) \\\\gt 1$. Columns \"+dependent_columns[0]+\" and \"+dependent_columns[1]+\" are equal, so $d(C) = 2$.\",\n d=3,\n \"There is no $\\\\mathbf{0}$ column, and no two columns are equal, so $d(C) \\\\gt 2$. The sum of columns \"+dependent_columns[0]+\",\"+dependent_columns[1]+\" and \"+dependent_columns[2]+\" is $\\\\mathbf{0}$, so $d(C)=3$.\",\n \n \"There is no $\\\\mathbf{0}$ column, and no two columns are equal, so $d(C) \\\\gt 2$. The sum of columns \"+dependent_columns[0]+\",\"+dependent_columns[1]+\",\"+dependent_columns[2]+\" and \"+dependent_columns[3]+\" is $\\\\mathbf{0}$, so $d(C)=4$.\"\n )\n)", "name": "explanation", "description": "Explanation of the derivation of the minimum distance, for the advice section.
"}, "A": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)", "name": "A", "description": "The parity check matrix is $I_{dim}|A$, where $A$ is random.
"}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "dimension+random(3..5)", "name": "word_length", "description": "Length of each word in the code
"}, "C": {"templateType": "anything", "group": "Ungrouped variables", "definition": "code(set_generated_by(parity_check_matrix(basis)))", "name": "C", "description": "The code $C$.
"}, "min_distance": {"templateType": "anything", "group": "Ungrouped variables", "definition": "minimum_distance(C)", "name": "min_distance", "description": "Minimum distance of the code $C$.
\nCould work this out by looking at the number of dependent columns, but it's nice to verify directly.
"}, "field_size": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "field_size", "description": ""}, "columns": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(codeword(x,2),x,list(transpose(H)))", "name": "columns", "description": "Columns of the parity check matrix, interpreted as codewords.
"}, "nary": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "name": "nary", "description": ""}, "dependent_columns": {"templateType": "anything", "group": "Ungrouped variables", "definition": "linearly_dependent_combination(columns)", "name": "dependent_columns", "description": "Smallest combination of columns of the parity check matrix which sum to 0.
"}, "H": {"templateType": "anything", "group": "Ungrouped variables", "definition": "codeword_matrix(basis)", "name": "H", "description": "The parity check matrix (basis for the dual code, represented as a matrix)
"}}, "ungrouped_variables": ["field_size", "nary", "dimension", "word_length", "A", "basis", "H", "C", "columns", "min_distance", "dependent_columns", "explanation"], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Compute the minimum distance between codewords of a code, given a parity check matrix.
"}, "functions": {"identity_right": {"type": "list", "language": "javascript", "definition": "var k = words.length;\nvar field_size = words[0].field_size;\nvar out = [];\nfor(var i=0;iFind the minimum distance of the binary code $C$ given by the following parity check matrix.
\n\\[ \\mathrm{H} =\\var{H} \\]
", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "advice": "The minimum distance $d(C)$ is equal to the smallest number of columns of $\\mathrm{H}$ related by a linear dependence.
\n{explanation}
"}, {"name": "Find the syndrome of a word in a linear code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [], "variables": {"word": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(\n random(set_generated_by(G_words) except (G_words+[zero(word_length,field_size)])),\n random(allwords(word_length,field_size) except zero(word_length,field_size))\n)", "description": "A randomly chosen word - 50% of the time it's picked from the code, 50% of the time it's a completely random word.
", "name": "word"}, "dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "3", "description": "Dimension of the code - number of rows in the generating matrix.
", "name": "dimension"}, "G_dual": {"group": "Ungrouped variables", "templateType": "anything", "definition": "codeword_matrix(parity_check_matrix(M))", "description": "Parity check matrix for $M$ (a generator matrix for the dual code of $M$)
", "name": "G_dual"}, "G": {"group": "Ungrouped variables", "templateType": "anything", "definition": "codeword_matrix(G_words)", "description": "A random generating matrix for the code, not in standard form.
", "name": "G"}, "M": {"group": "Ungrouped variables", "templateType": "anything", "definition": "identity_left(A)", "description": "Standard generating matrix for the code.
", "name": "M"}, "word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "dimension+random(3..5)", "description": "Length of each word in the code
", "name": "word_length"}, "word_is_in_code_explanation": {"group": "Ungrouped variables", "templateType": "anything", "definition": "if(word_is_in_code,\n \"$\\\\operatorname{syn} w = \\\\mathbf{0}$, so $w$ is in the code.\", \n \"$\\\\operatorname{syn} w \\\\neq \\\\mathbf{0}$, so $w$ is not in the code.\"\n)", "description": "", "name": "word_is_in_code_explanation"}, "G_words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "shuffle(set_generated_by(M))[0..dimension]", "description": "The generating matrix presented to the student, as a list of codewords.
\nThe variable testing condition ensures these words are linearly independent.
", "name": "G_words"}, "A": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)", "description": "The generating matrix is $I_{dim}|A$, where $A$ is random.
", "name": "A"}, "word_is_in_code": {"group": "Ungrouped variables", "templateType": "anything", "definition": "word_syndrome=zero(len(word_syndrome),field_size)", "description": "Word is in the code if its syndrome is zero.
", "name": "word_is_in_code"}, "field_size": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2,3,5)", "description": "", "name": "field_size"}, "nary": {"group": "Ungrouped variables", "templateType": "anything", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]", "description": "", "name": "nary"}, "word_syndrome": {"group": "Ungrouped variables", "templateType": "anything", "definition": "syndrome(word,parity_check_matrix(m))", "description": "Syndrome of word with respect to the parity check matrix.
", "name": "word_syndrome"}, "dual_dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "word_length-dimension", "description": "Dimension of the dual code
", "name": "dual_dimension"}}, "ungrouped_variables": ["field_size", "nary", "dimension", "word_length", "dual_dimension", "A", "M", "G_words", "G", "G_dual", "word", "word_syndrome", "word_is_in_code", "word_is_in_code_explanation"], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given a generator matrix for a linear code, write a parity check matrix, compute the syndrome of a word, and decide if it's a codeword.
"}, "functions": {"identity_right": {"type": "list", "language": "javascript", "definition": "var k = words.length;\nvar field_size = words[0].field_size;\nvar out = [];\nfor(var i=0;i$\\mathrm{H} = $ [[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "markPerCell": false, "allowFractions": false, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "correctAnswer": "G_dual", "allowResize": true, "unitTests": [], "correctAnswerFractions": false, "showFeedbackIcon": true, "scripts": {}, "type": "matrix", "numColumns": 1, "tolerance": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "3", "numRows": 1}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Find the syndrome of $\\var{word}$ with respect to the parity check matrix $\\mathrm{H}$.
\n$\\operatorname{syn}(\\var{word}) = $ [[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{word_syndrome+''}", "showCorrectAnswer": true, "displayAnswer": "{word_syndrome+''}", "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}, {"displayType": "radiogroup", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "matrix": "matrix(if(word_is_in_code,[[1],[0]],[[0],[1]]))", "choices": ["Yes
", "No
"], "prompt": "Is $\\var{word}$ a codeword?
", "unitTests": [], "shuffleChoices": false, "showFeedbackIcon": true, "scripts": {}, "maxMarks": 0, "type": "1_n_2", "minMarks": 0, "displayColumns": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "variablesTest": {"condition": "linearly_independent(G_words)", "maxRuns": 100}, "statement": "$C$ is a {nary} linear code with generator matrix
\n\\[ \\mathrm{G} =\\var{G} \\]
", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "advice": "First, row-reduce $\\mathrm{G}$ to obtain a standard generator matrix $\\mathrm{M}$ for the code
\n\\[ \\mathrm{G}' = \\var{codeword_matrix(M)} \\]
\nThis is in the form $(\\mathrm{I}_{\\var{dimension}}|\\mathrm{A})$. The standard parity check matrix is then $(-\\mathrm{A^T}|\\mathrm{I}_{\\var{word_length-dimension}})$, i.e.
\n\\[ \\mathrm{H} = \\var{G_dual} \\]
\nIf $w = \\var{word}$ then $\\operatorname{syn} w = w \\mathrm{H^T} = \\var{word_syndrome}$.
\n{word_is_in_code_explanation}
"}, {"name": "Lexicographic parity check matrix - binary ", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "parts": [{"showCorrectAnswer": true, "allowFractions": false, "correctAnswer": "codeword_matrix(pcm)", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "prompt": "Write down the lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{if(p=2,'',p)}}(\\var{rows})$.
", "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": "Use your parity-check matrix to correct the received word $\\var{received_words[0]}$.
\n[[0]]
", "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": "Use your parity-check matrix to correct the received word $\\var{received_words[1]}$.
\n[[0]]
", "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": "Positions of the error in each of the received words.
"}, "words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(hamming_encode(random_word(unencoded_length,2)),num_words)", "name": "words", "description": "Randomly chosen words from the code - pick a random string of the right length, then encode it.
\nThe testing condition makes sure they're different.
"}, "rows": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..4)", "name": "rows", "description": "Number of rows in the parity check matrix.
"}, "pcm": {"templateType": "anything", "group": "Ungrouped variables", "definition": "hamming_parity_check_matrix(p,rows)", "name": "pcm", "description": "Lexicographic parity check matrix for the code.
"}, "received_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(error(words[j],error_positions[j]),j,0..num_words-1)", "name": "received_words", "description": "Received words - introduce one error into each of the original words
"}, "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": "Amount added to the changed column in each of the received words - the syndrome will be this many times the <error_position>th column of the parity-check matrix.
\nNot really necessary for a binary code because it's always 1, but this is just copied from the n-ary question.
"}, "num_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "num_words", "description": "Number of words to decode.
"}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(p^rows-1)/(p-1)", "name": "word_length", "description": "Length of each codeword
"}, "syndromes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(syndrome(word,pcm),word,received_words)", "name": "syndromes", "description": "Syndrome of each of the received words
"}, "columns": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(codeword(x,p),x,list(transpose(codeword_matrix(pcm))))", "name": "columns", "description": "Columns of the parity check matrix.
"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "2", "name": "p", "description": "Size of the field in which the code lives
"}, "unencoded_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "word_length-rows", "name": "unencoded_length", "description": "Length of a string which can be encoded to a member of this code.
"}}, "ungrouped_variables": ["p", "rows", "pcm", "word_length", "num_words", "unencoded_length", "words", "error_positions", "received_words", "syndromes", "multiply_error", "columns"], "preamble": {"css": "", "js": ""}, "variable_groups": [], "functions": {"nth": {"type": "string", "language": "jme", "definition": "switch(\n n=1,\"first\",\n n=2,\"second\",\n n=3,\"third\",\n n+\"th\"\n)", "parameters": [["n", "number"]]}}, "variablesTest": {"condition": "len(distinct(words))=len(words)", "maxRuns": 100}, "statement": "", "tags": [], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Write down a lexicographic parity check matrix for a Hamming code and correct two received codewords.
"}, "advice": "The lexicographic parity check matrix for $\\operatorname{Ham}(\\var{rows})$ has the following properties:
\nThe unique parity-check matrix for $\\operatorname{Ham}(\\var{rows})$ with these properties is
\n\\[ \\var{codeword_matrix(pcm)} \\]
\nThe word $\\var{received_words[0]}$ has syndrome
\n\\[ (\\var{received_words[0]}) \\var{transpose(codeword_matrix(pcm))} = (\\var{syndromes[0]}) \\]
\n$\\var{syndromes[0]}$ is binary for $\\var{error_positions[0]+1}$, so the error is in the {nth(error_positions[0]+1)} digit, and we correct to $\\var{words[0]}$.
\nThe word $\\var{received_words[1]}$ has syndrome
\n\\[ (\\var{received_words[1]}) \\var{transpose(codeword_matrix(pcm))} = (\\var{syndromes[1]}) \\]
\n$\\var{syndromes[1]}$ is binary for $\\var{error_positions[1]+1}$, so the error is in the {nth(error_positions[1]+1)} digit, and we correct to $\\var{words[1]}$.
"}, {"name": "Lexicographic parity check matrix - ternary, 5-ary or 7-ary", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [], "variables": {"error_positions": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(random(0..word_length-1),num_words)", "description": "Positions of the error in each of the received words.
", "name": "error_positions"}, "words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(random_combination(gen_matrix),num_words)", "description": "Randomly chosen words from the code.
\nThe testing condition makes sure they're different.
", "name": "words"}, "rows": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2..floor(log(16*(p+1)-1)/log(p)))", "description": "Number of rows in the parity check matrix.
\nUpper bound for the random range makes sure the word length is not greater than 16.
", "name": "rows"}, "word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "(p^rows-1)/(p-1)", "description": "Length of each codeword
", "name": "word_length"}, "received_words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(error(words[j],error_positions[j]),j,0..num_words-1)", "description": "Received words - introduce one error into each of the original words
", "name": "received_words"}, "multiply_error": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map((received_words[j]-words[j])[error_positions[j]],j,0..num_words-1)", "description": "Amount added to the changed column in each of the received words - the syndrome will be this many times the <error_position>th column of the parity-check matrix.
", "name": "multiply_error"}, "num_words": {"group": "Ungrouped variables", "templateType": "anything", "definition": "2", "description": "Number of words to decode.
", "name": "num_words"}, "pcm": {"group": "Ungrouped variables", "templateType": "anything", "definition": "hamming_parity_check_matrix(p,rows)", "description": "Lexicographic parity check matrix for the code.
", "name": "pcm"}, "gen_matrix": {"group": "Ungrouped variables", "templateType": "anything", "definition": "hamming_generating_matrix(p,rows)", "description": "Generating matrix for the Hamming code
", "name": "gen_matrix"}, "syndromes": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(syndrome(word,pcm),word,received_words)", "description": "Syndrome of each of the received words
", "name": "syndromes"}, "columns": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(codeword(x,p),x,list(transpose(codeword_matrix(pcm))))", "description": "Columns of the parity check matrix.
", "name": "columns"}, "p": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(3,5,7)", "description": "Size of the field in which the code lives
", "name": "p"}}, "ungrouped_variables": ["p", "rows", "pcm", "word_length", "num_words", "gen_matrix", "words", "error_positions", "received_words", "syndromes", "multiply_error", "columns"], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Write down the lexicographic parity check matrix for a Hamming code, and correct two received codewords.
"}, "functions": {"nth": {"type": "string", "language": "jme", "definition": "switch(\n n=1,\"first\",\n n=2,\"second\",\n n=3,\"third\",\n n+\"th\"\n)", "parameters": [["n", "number"]]}}, "parts": [{"showCorrectAnswer": true, "markPerCell": false, "allowFractions": false, "customMarkingAlgorithm": "", "allowResize": true, "correctAnswer": "codeword_matrix(pcm)", "prompt": "Write down the lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$.
", "unitTests": [], "correctAnswerFractions": false, "numRows": 1, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "matrix", "numColumns": 1, "tolerance": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "2", "showFeedbackIcon": true}, {"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Use your parity-check matrix to correct the received word $\\var{received_words[0]}$.
\n[[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{words[0]+''}", "showCorrectAnswer": true, "displayAnswer": "{words[0]+''}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "1.5"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "Use your parity-check matrix to correct the received word $\\var{received_words[1]}$.
\n[[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{words[1]+''}", "showCorrectAnswer": true, "displayAnswer": "{words[1]+''}", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "matchMode": "regex", "showFeedbackIcon": true, "scripts": {}, "type": "patternmatch", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": "1.5"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}], "variablesTest": {"condition": "len(distinct(words))=len(words)", "maxRuns": 100}, "statement": "", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "advice": "The lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$ has the following properties:
\nThe unique parity-check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$ with this property is
\n\\[ \\var{codeword_matrix(pcm)} \\]
\nThe word $\\var{received_words[0]}$ has syndrome
\n\\[ (\\var{received_words[0]}) \\var{transpose(codeword_matrix(pcm))} = (\\var{syndromes[0]}) \\]
\n$(\\var{syndromes[0]}) = \\var{multiply_error[0]} \\times (\\var{columns[error_positions[0]]})$. Since $\\var{columns[error_positions[0]]}$ is the {nth(error_positions[0]+1)} column of the parity check matrix, we subtract $\\var{multiply_error[0]}$ from the {nth(error_positions[0]+1)} column to get $\\var{words[0]}$.
\nThe word $\\var{received_words[1]}$ has syndrome
\n\\[ (\\var{received_words[1]}) \\var{transpose(codeword_matrix(pcm))} = (\\var{syndromes[1]}) \\]
\n$(\\var{syndromes[1]}) = \\var{multiply_error[1]} \\times (\\var{columns[error_positions[1]]})$. Since $\\var{columns[error_positions[1]]}$ is the {nth(error_positions[1]+1)} column of the parity check matrix, we subtract $\\var{multiply_error[1]}$ from the {nth(error_positions[1]+1)} column to get $\\var{words[1]}$.
"}, {"name": "Word-length, dimension and minimum distance of Hamming codes", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [], "variables": {"binary_hamming_rows": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(4..9)", "name": "binary_hamming_rows", "description": ""}, "binary_word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "(2^binary_hamming_rows-1)", "name": "binary_word_length", "description": ""}, "simplex_word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "(simplex_prime^simplex_rows-1)/(simplex_prime-1)", "name": "simplex_word_length", "description": ""}, "hamming_prime": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(3,5,7,11)", "name": "hamming_prime", "description": ""}, "parity_hamming_dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "parity_hamming_word_length-1-parity_hamming_rows", "name": "parity_hamming_dimension", "description": ""}, "simplex_dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "simplex_rows", "name": "simplex_dimension", "description": ""}, "simplex_minimum_distance": {"group": "Ungrouped variables", "templateType": "anything", "definition": "simplex_prime^(simplex_rows-1)", "name": "simplex_minimum_distance", "description": ""}, "hamming_dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "hamming_word_length-hamming_rows", "name": "hamming_dimension", "description": ""}, "binary_dimension": {"group": "Ungrouped variables", "templateType": "anything", "definition": "binary_word_length - binary_hamming_rows", "name": "binary_dimension", "description": ""}, "simplex_prime": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(3,5,7,11)", "name": "simplex_prime", "description": ""}, "parity_hamming_word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "2^parity_hamming_rows", "name": "parity_hamming_word_length", "description": ""}, "simplex_rows": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(3..9)", "name": "simplex_rows", "description": ""}, "hamming_word_length": {"group": "Ungrouped variables", "templateType": "anything", "definition": "(hamming_prime^hamming_rows-1)/(hamming_prime-1)", "name": "hamming_word_length", "description": ""}, "parity_hamming_rows": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(3..9)", "name": "parity_hamming_rows", "description": ""}, "hamming_rows": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2..5)", "name": "hamming_rows", "description": ""}}, "ungrouped_variables": ["binary_hamming_rows", "binary_word_length", "binary_dimension", "hamming_prime", "hamming_rows", "hamming_word_length", "hamming_dimension", "parity_hamming_rows", "parity_hamming_word_length", "parity_hamming_dimension", "simplex_prime", "simplex_rows", "simplex_word_length", "simplex_dimension", "simplex_minimum_distance"], "functions": {}, "parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$C = \\mathrm{Ham}(\\var{binary_hamming_rows})$
\nWord-length: [[0]]
\nDimension: [[1]]
\nMinimum distance: [[2]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "binary_word_length", "maxValue": "binary_word_length", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "binary_dimension", "maxValue": "binary_dimension", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "3", "maxValue": "3", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$C = \\mathrm{Ham}_{\\var{hamming_prime}}(\\var{hamming_rows})$
\nWord-length: [[0]]
\nDimension: [[1]]
\nMinimum distance: [[2]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "hamming_word_length", "maxValue": "hamming_word_length", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "hamming_dimension", "maxValue": "hamming_dimension", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "3", "maxValue": "3", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$C = \\mathrm{Ham}^+(\\var{parity_hamming_rows})$
\nWord-length: [[0]]
\nDimension: [[1]]
\nMinimum distance: [[2]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "parity_hamming_word_length", "maxValue": "parity_hamming_word_length", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "parity_hamming_dimension", "maxValue": "parity_hamming_dimension", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "4", "maxValue": "4", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "$C = \\mathrm{Sim}_{\\var{simplex_prime}}(\\var{simplex_rows})$
\nWord-length: [[0]]
\nDimension: [[1]]
\nMinimum distance: [[2]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "simplex_word_length", "maxValue": "simplex_word_length", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "simplex_dimension", "maxValue": "simplex_dimension", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}, {"showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "simplex_minimum_distance", "maxValue": "simplex_minimum_distance", "unitTests": [], "correctAnswerStyle": "plain", "showFeedbackIcon": true, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "correctAnswerFraction": false, "variableReplacements": [], "marks": "0.5", "mustBeReducedPC": 0}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}], "statement": "Write down the word-length, dimension and minimum distance of $C$, where
", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "variablesTest": {"condition": "", "maxRuns": 100}, "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Compute the word length, minimum distance and dimension of some given Hamming codes.
"}, "advice": "$\\operatorname{Ham}(\\var{binary_hamming_rows})$ has word-length $\\simplify[]{2^{binary_hamming_rows}-1 = {binary_word_length}}$, dimension $\\simplify[]{{binary_word_length}-{binary_hamming_rows} = {binary_dimension}}$ and minimum distance $3$.
\n$\\operatorname{Ham}_{\\var{hamming_prime}}(\\var{hamming_rows})$ has word-length $\\simplify[]{({hamming_prime}^{hamming_rows}-1)/({hamming_prime}-1) = {hamming_word_length}}$, dimension $\\simplify[]{{hamming_word_length}-{hamming_rows} = {hamming_dimension}}$ and minimum distance $3$.
\n$\\operatorname{Ham}^+(\\var{parity_hamming_rows})$ has word-length $\\simplify[]{2^{parity_hamming_rows} = {parity_hamming_word_length}}$, dimension $\\simplify[]{{parity_hamming_word_length}-1-{parity_hamming_rows} = {parity_hamming_dimension}}$ and minimum distance $4$.
\n$\\operatorname{Sim}_{\\var{simplex_prime}}(\\var{simplex_rows})$ has word-length $\\simplify[]{({simplex_prime}^{simplex_rows}-1)/({simplex_prime}-1) = {simplex_word_length}}$, dimension $\\var{simplex_rows}$ and minimum distance $\\simplify[]{{simplex_prime}^({simplex_rows}-1)={simplex_minimum_distance}}$.
"}, {"name": "Generator matrix for Simplex code", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "tags": [], "metadata": {"description": "Write down the lexicographic parity check matrix and generator matrix for a Hamming code, which is the dual of a Simplex code, then determine if a given word is a codeword of the corresponding Simplex code.
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "", "advice": "The lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$ is
\n\\[ \\mathrm{H} = \\var{codeword_matrix(pcm)} \\]
\nPerforming the column permutation $\\var{perm_arrows(swap)}$ on $\\mathrm{H}$ gives
\n\\[ H^{\\ast} = \\var{permuted_pcm} \\]
\nwhich we can invert (via $(\\mathrm{I}|\\mathrm{A}) \\mapsto (-\\mathrm{A^T}|\\mathrm{I})$), and then perform the reverse permutation, $\\var{perm_arrows(iswap)}$ to get
\n\\[ \\mathrm{G} = \\var{codeword_matrix(gen_matrix)} \\]
\nThis is a generator matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$. It is also a parity-check matrix for its dual code $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
\nUsing $\\mathrm{G}$, we can check whether $w = \\var{word}$ is a codeword of $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$ by calculating its syndrome $w \\mathrm{G^T}$: this is $\\var{syndrome}$. The syndrome is not $\\mathbf{0}$, so $w$ is not a codeword. The syndrome is $\\mathbf{0}$, so $w$ is a codeword.
", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"syndrome": {"name": "syndrome", "group": "Word to check", "definition": "syndrome(word,gen_matrix)", "description": "Syndrome of the word with respect to the parity check matrix for the simplex code.
", "templateType": "anything", "can_override": false}, "swap": {"name": "swap", "group": "Advice", "definition": "column_swaps(p,rows)", "description": "Column permutation to get the parity-check matrix in a form to work out its dual.
", "templateType": "anything", "can_override": false}, "permuted_pcm": {"name": "permuted_pcm", "group": "Advice", "definition": "transpose(matrix(let(\n columns,list(transpose(codeword_matrix(pcm))),\n map(columns[iswap[j+1]-1],j,0..len(columns)-1)\n)))", "description": "Parity-check matrix with its columns permuted so it's in the form $(I|A)$.
", "templateType": "anything", "can_override": false}, "rows": {"name": "rows", "group": "Setup", "definition": "3", "description": "Number of rows in the parity check matrix.
", "templateType": "anything", "can_override": false}, "p": {"name": "p", "group": "Setup", "definition": "random(2,3)", "description": "Size of the field in which the code lives
", "templateType": "anything", "can_override": false}, "word_length": {"name": "word_length", "group": "Setup", "definition": "(p^rows-1)/(p-1)", "description": "Length of each codeword
", "templateType": "anything", "can_override": false}, "word": {"name": "word", "group": "Word to check", "definition": "let(in_code,set_generated_by(pcm),\n random(\n random(in_code except zero(word_length,p)),\n random_word(word_length,p)\n )\n)", "description": "Either a word from the code, or a word chosen at random from the set of all words. Only about 1.5% of the possible words belong to the code, so we get a word from the code only slightly more than half of the time.
", "templateType": "anything", "can_override": false}, "word_belongs": {"name": "word_belongs", "group": "Word to check", "definition": "is_zero(syndrome)", "description": "Does the word belong to the code? True if the syndrome is zero.
", "templateType": "anything", "can_override": false}, "iswap": {"name": "iswap", "group": "Advice", "definition": "inverse(swap)", "description": "Inverse column permutation, to get a generator matrix for the Hamming code.
", "templateType": "anything", "can_override": false}, "pcm": {"name": "pcm", "group": "Matrices", "definition": "hamming_parity_check_matrix(p,rows)", "description": "Lexicographic parity check matrix for the code. (Also a generator matrix for the simplex code)
", "templateType": "anything", "can_override": false}, "gen_matrix": {"name": "gen_matrix", "group": "Matrices", "definition": "hamming_generating_matrix(p,rows)", "description": "Generating matrix for the Hamming code (also a parity check matrix for the simplex code)
", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [{"name": "Setup", "variables": ["p", "rows", "word_length"]}, {"name": "Matrices", "variables": ["pcm", "gen_matrix"]}, {"name": "Word to check", "variables": ["word", "syndrome", "word_belongs"]}, {"name": "Advice", "variables": ["swap", "iswap", "permuted_pcm"]}], "functions": {"column_swaps": {"parameters": [["p", "number"], ["r", "number"]], "type": "permutation", "language": "javascript", "definition": "var off = 1;\nvar t = 1;\npos = [];\nfor(var i=1;iWrite down the lexicographic parity check matrix for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$.
", "correctAnswer": "codeword_matrix(pcm)", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"type": "matrix", "useCustomName": false, "customName": "", "marks": "2", "scripts": {}, "customMarkingAlgorithm": "student_bases:\n map(codeword(row,p),row,list(studentmatrix))\n\ngenerated_by_pcm:\n if(is_generated_by(student_basis, pcm),\n correct()\n ,\n incorrect(\"Your answer is not correct - this matrix does not generate $\\\\operatorname{Ham}_{\"+p+\"}(\"+correct_rows+\")$.\")\n )", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Find a generator matrix $\\mathrm{G}$ for $\\operatorname{Ham}_{\\var{p}}(\\var{rows})$.
", "correctAnswer": "codeword_matrix(gen_matrix)", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Use $\\mathrm{G}$ to determine if the word $\\var{word}$ belongs to $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
\n[[0]]
", "gaps": [{"type": "1_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["$\\var{word}$ belongs to $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
", "$\\var{word}$ does not belong to $\\operatorname{Sim}_{\\var{p}}(\\var{rows})$.
"], "matrix": "if(word_belongs,[1,0],[0,1])"}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question"}]}], "showstudentname": true, "showQuestionGroupNames": false, "type": "exam", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Questions used in a university course titled \"Coding theory\".
\nReady to use as all 20 questions are stated as ready to use.
"}, "timing": {"timedwarning": {"action": "none", "message": ""}, "timeout": {"action": "none", "message": ""}, "allowPause": true}, "duration": 0, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"name": "Bill Foster", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/6/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}], "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": []}