// Numbas version: exam_results_page_options {"name": "Find a generator matrix for a code and decide if it is standard - ternary", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"preventleave": false, "allowregen": true, "showfrontpage": false}, "question_groups": [{"questions": [{"type": "question", "tags": [], "contributors": [{"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": "Christian Lawson-Perfect"}], "name": "Find a generator matrix for a code and decide if it is standard - ternary", "preamble": {"js": "", "css": ""}, "ungrouped_variables": [], "functions": {"leading_columns": {"type": "list", "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.

", "markPerCell": false, "correctAnswerFractions": false, "marks": 1, "numColumns": 1, "unitTests": [], "variableReplacements": [], "showCorrectAnswer": true, "correctAnswer": "codeword_matrix(g)", "allowFractions": false, "extendBaseMarkingAlgorithm": true}, {"showCorrectAnswer": true, "type": "1_n_2", "variableReplacementStrategy": "originalfirst", "minMarks": 0, "choices": ["

Yes

", "

No

"], "customMarkingAlgorithm": "", "showFeedbackIcon": true, "shuffleChoices": false, "prompt": "

Is there a standard generator matrix for this code?

", "displayColumns": 0, "unitTests": [], "marks": 0, "displayType": "radiogroup", "variableReplacements": [], "maxMarks": 0, "matrix": "if(is_standard,[1,0],[0,1])", "scripts": {}, "extendBaseMarkingAlgorithm": true}, {"type": "gapfill", "variableReplacementStrategy": "originalfirst", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "showFeedbackIcon": 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]]

What data vector is encoded as $c = \\var{to_decode}$?

", "displayAnswer": "{string(decoded_word)}", "scripts": {}, "marks": 1, "matchMode": "regex", "variableReplacements": [], "showCorrectAnswer": true, "unitTests": [], "extendBaseMarkingAlgorithm": true}], "rulesets": {}, "variable_groups": [{"name": "Setup", "variables": ["word_length", "field_size", "num_words", "nary"]}, {"name": "Random stuff", "variables": ["num_skips", "data_vectors", "independent_combos", "extra_combos", "skips", "rest", "g_standard_bit"]}, {"name": "Generator matrix", "variables": ["initial_g", "shuffled_g", "combos", "codewords", "g", "is_standard", "encoded_data_vectors"]}, {"name": "Invert codeword", "variables": ["to_decode", "decoded_word"]}], "advice": "

#### ca)

\n

Write down the matrix whose rows are the given codewords:

\n

\$\\var{codeword_matrix(codewords)} \$

\n

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.

\n

From the matrix above, we obtain:

\n

\$\\mathrm{G} = \\var{codeword_matrix(g)} \$

\n

#### b)

\n

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

\n

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

\n

#### c)

\n

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

\n

So 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} \n 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} \n #### d) \n We are looking for a data vector of length \\var{len(g)} which is encoded as c = \\var{to_decode}. \n 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 1s in \\mathrm{G} are in columns {join(leading_columns(g),', ')}. The corresponding digits of c give the data vector \\var{decoded_word}. \n We can confirm that this vector is encoded as c: \n \\[ \\simplify[rowvector]{ {vector(decoded_word)}*{codeword_matrix(g)} } = \\var[rowvector]{vector(to_decode)} \

", "statement": "

Let $C$ be the {nary} code generated by the following set of codewords.

\n

\$\\var{join_words(codewords)} \$

", "extensions": ["codewords", "permutations"], "variablesTest": {"maxRuns": 100, "condition": ""}, "variables": {"encoded_data_vectors": {"group": "Generator matrix", "description": "", "name": "encoded_data_vectors", "templateType": "anything", "definition": "map(\n codeword(\n vector(v)*codeword_matrix(g),\n field_size\n ),\n v,\n data_vectors\n)"}, "field_size": {"group": "Setup", "description": "

The field the code is defined over.

", "name": "field_size", "templateType": "anything", "definition": "3"}, "is_standard": {"group": "Generator matrix", "description": "", "name": "is_standard", "templateType": "anything", "definition": "generator_matrix_is_standard(g)"}, "shuffled_g": {"group": "Generator matrix", "description": "

The rows of the reduced generator matrix, shuffled.

", "name": "shuffled_g", "templateType": "anything", "definition": "matrix(shuffle(map(vector(r),r,list(initial_g))))"}, "extra_combos": {"group": "Random stuff", "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.

", "name": "extra_combos", "templateType": "anything", "definition": "shuffle(allwords(num_words,field_size) except independent_combos)[0..2]"}, "independent_combos": {"group": "Random stuff", "description": "

We'll create the codewords to show the student by taking combinations of the rows of the reduced echelon matrix.

\n

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.

", "name": "independent_combos", "templateType": "anything", "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)"}, "word_length": {"group": "Setup", "description": "

The length of each codeword.

", "name": "word_length", "templateType": "anything", "definition": "6"}, "initial_g": {"group": "Generator matrix", "description": "

Reduced row echelon form generator matrix.

", "name": "initial_g", "templateType": "anything", "definition": "g_standard_bit+rest"}, "to_decode": {"group": "Invert codeword", "description": "

The codeword for which the student needs to find the corresponding data vector.

", "name": "to_decode", "templateType": "anything", "definition": "random_combination(codewords)"}, "g_standard_bit": {"group": "Random stuff", "description": "

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

\n

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.

", "name": "g_standard_bit", "templateType": "anything", "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))"}, "codewords": {"group": "Generator matrix", "description": "

Codewords shown to the student.

\n

They're linear combinations of the rows of shuffled_g.

", "name": "codewords", "templateType": "anything", "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)"}, "num_words": {"group": "Setup", "description": "

The number of basis words to generate.

", "name": "num_words", "templateType": "anything", "definition": "4"}, "decoded_word": {"group": "Invert codeword", "description": "

Vectors which, when multiplied by the generator matrix, give the basis vectors.

", "name": "decoded_word", "templateType": "anything", "definition": "decode_codeword(to_decode,g)"}, "rest": {"group": "Random stuff", "description": "

Random numbers to add on the columns to the right of all of the leading 1s in the generator matrix.

", "name": "rest", "templateType": "anything", "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))"}, "nary": {"group": "Setup", "description": "", "name": "nary", "templateType": "anything", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]"}, "data_vectors": {"group": "Random stuff", "description": "", "name": "data_vectors", "templateType": "anything", "definition": "shuffle(allwords(len(g),field_size))[0..3]"}, "num_skips": {"group": "Random stuff", "description": "

Number of columns to skip over in the echelon part.

\n

For a standard matrix, this is zero.

", "name": "num_skips", "templateType": "anything", "definition": "random(0,random(1..word_length-num_words))"}, "g": {"group": "Generator matrix", "description": "

Generator matrix for the code generated by basis.

", "name": "g", "templateType": "anything", "definition": "generator_matrix(codewords)"}, "skips": {"group": "Random stuff", "description": "

columns which would be leading columns in a standard matrix but are instead skipped over

", "name": "skips", "templateType": "anything", "definition": "sort(shuffle(0..num_words-1)[0..num_skips])"}, "combos": {"group": "Generator matrix", "description": "", "name": "combos", "templateType": "anything", "definition": "independent_combos+extra_combos"}}, "metadata": {"description": "

Given a set of codewords generating a code, give a generating matrix, encode three data vectors, and decode one codeword.

", "licence": "Creative Commons Attribution 4.0 International"}}], "pickingStrategy": "all-ordered"}], "contributors": [{"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": "Christian Lawson-Perfect"}]}