// Numbas version: exam_results_page_options {"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}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"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(cpos and c in skips,random(0,1),0),c,0..word_length-1)\n ),\n j,\n 0..num_words-1\n))", "name": "g_standard_bit", "description": "

If G is a standard matrix, this is $I_{num_words} + 0_{\\text{num_words} \\times \\text{word_length}}$.

Otherwise, 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.

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

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

They'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": [], "name": "Find a generator matrix for a code and decide if it is standard - binary", "functions": {"leading_columns": {"type": "list", "language": "javascript", "definition": "return g.map(function(row){\n for(var i=0;iIf there is a standard generator matrix for this code, enter it below. Otherwise, write down a generator matrix with the fewest possible rows, in reduced row-echelon form.

", "unitTests": [], "correctAnswerFractions": false, "numRows": 1, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "matrix", "numColumns": 1, "tolerance": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showFeedbackIcon": true}, {"displayType": "radiogroup", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "matrix": "if(is_standard,[1,0],[0,1])", "choices": ["

Yes

", "

"], "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.

$\\var{data_vectors[0]} \\mapsto $ [[0]]

$\\var{data_vectors[1]} \\mapsto $ [[1]]

$\\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.

\\[ \\var{join_words(codewords)} \\]

", "tags": [], "rulesets": {}, "extensions": ["codewords", "permutations"], "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": "

ca)

Write down the matrix whose rows are the given codewords:

\\[ \\var{codeword_matrix(codewords)} \\]

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

From the matrix above, we obtain:

\\[ \\mathrm{G} = \\var{codeword_matrix(g)} \\]

b)

A 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}$.

If a code has a standard generator matrix, the row reduced echelon form will be it.

$\\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.

c)

To encode a data vector $\\mathbf{v}$, multiply it on the right by the generator matrix for the code.

So we have:

\\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,

\\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}

d)

We are looking for a data vector of length $\\var{len(g)}$ which is encoded as $c = \\var{to_decode}$.

Note 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}$.

We can confirm that this vector is encoded as $c$:

\\[ \\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/"}]}