// Numbas version: exam_results_page_options {"name": "Equivalent codes", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"base_codes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(code(shuffle(allwords(word_length,field_size))[0..num_words]),5)", "name": "base_codes", "description": "

5 distinct codes which aren't equivalent to each other (enforced by testing condition)

"}, "positional_permutations": {"templateType": "anything", "group": "Ungrouped variables", "definition": "permutations(deal(word_length),word_length)", "name": "positional_permutations", "description": "

Every possible positional permutation on the codewords

"}, "equivalence_indices": {"templateType": "anything", "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)", "name": "equivalence_indices", "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)

"}, "equivalence_matrix": {"templateType": "anything", "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))", "name": "equivalence_matrix", "description": "

The matrix of equivalencies between the codes, in the order the student sees them.

"}, "inverse_code_order": {"templateType": "anything", "group": "Ungrouped variables", "definition": "inverse_permutation(code_order)", "name": "inverse_code_order", "description": "

The inverse shuffling of the codes, so we can refer to codes $C_i$.

"}, "codes": {"templateType": "anything", "group": "Ungrouped variables", "definition": "base_codes+equivalent_codes", "name": "codes", "description": "

All the codes shown to the student - base codes plus equivalent codes.

\n

Not shown in this order!

"}, "num_words": {"templateType": "anything", "group": "Ungrouped variables", "definition": "4", "name": "num_words", "description": "

Number of words in each code

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

Field each code belongs to

"}, "symbolic_permutations": {"templateType": "anything", "group": "Ungrouped variables", "definition": "product_n(\n repeat(permutations(list(0..field_size-1),field_size),word_length)\n)", "name": "symbolic_permutations", "description": "

Every possible symbolic permutation on the codewords.

"}, "unshuffled_equivalence_matrix": {"templateType": "anything", "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])", "name": "unshuffled_equivalence_matrix", "description": "

The matrix of equivalencies between the codes, before they're shuffled.

"}, "word_length": {"templateType": "anything", "group": "Ungrouped variables", "definition": "4", "name": "word_length", "description": "

Length of words in each code

"}, "equivalents_marking_matrix": {"templateType": "anything", "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)", "name": "equivalents_marking_matrix", "description": ""}, "composed_permutations": {"templateType": "anything", "group": "Ungrouped variables", "definition": "shuffle(product(positional_permutations,symbolic_permutations))[0..3]", "name": "composed_permutations", "description": "

Three randomly-chosen compositions of a positional permutation and a symbolic permutation.

"}, "equivalent_codes": {"templateType": "anything", "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)", "name": "equivalent_codes", "description": "

For each of the first three base codes, an equivalent code produced by a positional and symbolic permutation.

"}, "code_order": {"templateType": "anything", "group": "Ungrouped variables", "definition": "deal(len(codes))", "name": "code_order", "description": "

The order to show the codes in.

"}, "word_distances": {"templateType": "anything", "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)", "name": "word_distances", "description": ""}}, "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"], "name": "Equivalent codes", "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;ii){\n td.setAttribute('class','empty');\n } else {\n td.textContent = '$0$';\n }\n tr.appendChild(td);\n }\n}\nreturn table;", "parameters": [["code", "code"]]}, "product_n": {"type": "list", "language": "javascript", "definition": "return Numbas.util.product(lists);", "parameters": [["lists", "list"]]}, "inverse_permutation": {"type": "list", "language": "javascript", "definition": "var out = [];\nfor(var i=0;i1 ? 's' : '')+' $'+swapped_symbols.join(',')+'$' : '';\n\nreturn \"permute the digits of each codeword in the order $\"+position_explanation+\"$\"+symbol_explanation+\".\";", "parameters": [["permutation", "list"]]}}, "preamble": {"css": ".part .distance-table {\n margin-left: 0;\n}\n\n.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 text-align: center;\n}\n.distance-table td.empty {\n background: #eee;\n}", "js": ""}, "parts": [{"customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "prompt": "

$C_1$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

$C_2$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

$C_3$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

$C_4$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

$C_5$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

$C_6$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

$C_7$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

$C_8$

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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]}$ [[0]] [[1]] [[2]] [[3]] [[4]] [[5]] [[6]] [[7]] [[8]] [[9]]

In the grid below, tick each box which corresponds to a pair of equivalent codes.

", "type": "m_n_x", "maxAnswers": 0, "shuffleChoices": false, "variableReplacementStrategy": "originalfirst", "showFeedbackIcon": true, "minAnswers": 0, "minMarks": 0, "shuffleAnswers": false, "variableReplacements": [], "layout": {"type": "strictlowertriangle", "expression": ""}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "matrix": "equivalents_marking_matrix", "choices": ["$C_1$", "$C_2$", "$C_3$", "$C_4$", "$C_5$", "$C_6$", "$C_7$", "$C_8$"], "unitTests": [], "answers": ["$C_1$", "$C_2$", "$C_3$", "$C_4$", "$C_5$", "$C_6$", "$C_7$", "$C_8$"], "scripts": {}, "maxMarks": 0, "showCorrectAnswer": true, "marks": 0, "warningType": "none"}], "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}

\n

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.

", "tags": [], "rulesets": {}, "extensions": ["codewords", "permutations"], "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "

Compute tables of Hamming distances in given codes, then determine which codes are equivalent.

"}, "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"}, "advice": "

Begin by computing a table of Hamming distances for each code.

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
 \n\$C_1 \$\n{distance_table(codes[code_order[0]])}\n \n\$C_2 \$\n{distance_table(codes[code_order[1]])}\n \n\$C_3 \$\n{distance_table(codes[code_order[2]])}\n \n\$C_4 \$\n{distance_table(codes[code_order[3]])}\n \n\$C_5 \$\n{distance_table(codes[code_order[4]])}\n \n\$C_6 \$\n{distance_table(codes[code_order[5]])}\n \n\$C_7 \$\n{distance_table(codes[code_order[6]])}\n \n\$C_8 \$\n{distance_table(codes[code_order[7]])}\n
\n

First, note that every code is equivalent to itself.

\n

Two 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.

", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas-editor.mas.ncl.ac.uk/accounts/profile/3/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}