// Numbas version: exam_results_page_options {"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}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Construct a Slepian array and find coset leaders", "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": "

a)

\n

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

\n

b)

\n

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

\n

c)

\n

Now we need to write out a Slepian array for $C$. Each row of the Slepian array corresponds to a coset of $C$.

\n

There 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)),[])}

\n

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

\n

The 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 '))}$

\n

d)

\n

The coset leader of a coset is an element of minimum weight. There could be more than one choice of coset leader for a coset.

\n

The first column of the Slepian array gives a set of coset leaders.

\n

e)

\n

The syndrome of a word $w$ with respect to a parity matrix $\\mathrm{H}$ is $w\\mathrm{H^T}$.

\n

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

\n

f)

\n

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

\n

Another way is to compute its syndrome, and subtract the coset leader with the corresponding syndrome.

\n

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

\n

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

\n

There'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

", "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}, "dual_dimension": {"name": "dual_dimension", "group": "Ungrouped variables", "definition": "word_length-dimension", "description": "

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.

\n

The 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

", "templateType": "anything", "can_override": false}, "field_size": {"name": "field_size", "group": "Ungrouped variables", "definition": "2", "description": "", "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}}, "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;iFind the standard parity check matrix $\\mathrm{H}$ for $C$.

\n

$\\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;iList all of the codewords in $C$.

\n

Enter your answer as a list of codewords separated by commas, e.g. 0000,1111,...

", "answer": "", "displayAnswer": "{join(map(string(x),x,C_words),',')}", "matchMode": "regex"}, {"type": "patternmatch", "useCustomName": false, "customName": "", "marks": 1, "scripts": {"mark": {"script": "with(Numbas.extensions.codewords) {\n mark_codeword_set(this,variables.field_size,function(words) {\n this.answered = true;\n \n var student_code = new Code(words);\n var word_coset = new Code(variables.word_coset);\n if(student_code.eq(word_coset)) {\n this.setCredit(1,\"Your answer is correct.\");\n } else {\n this.setCredit(0,\"Your answer is incorrect.\");\n }\n \n });\n}", "order": "instead"}, "validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

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;iNow give a set of coset leaders for $C$, one for each coset.

", "answer": "", "displayAnswer": "{join(map(string(x),x,coset_leaders),',')}", "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 student_code = new Code(words);\n if(student_code.eq(new Code(variables.syndromes))) {\n this.setCredit(1,\"Your answer is correct.\");\n } else {\n this.setCredit(0,\"Your answer is incorrect.\");\n }\n \n });\n}", "order": "instead"}, "validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "alwaysreplace", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Calculate syndromes for the coset leaders. Enter them as a list of words separated by commas, e.g. 000,111,...

", "answer": "{join(syndromes,',')}", "displayAnswer": "{join(map(string(x),x,syndromes),',')}", "matchMode": "regex"}, {"type": "patternmatch", "useCustomName": false, "customName": "", "marks": "1", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

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