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": [], "name": "Find a generator matrix for a code and decide if it is standard - $\\mathbb{Z}_5$", "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.
"}, "extensions": ["codewords", "permutations"], "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)} \\]
", "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/"}]}