// 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": "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} \\]
\nThe 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$.
\nNow we need to write out a Slepian array for $C$. Each row of the Slepian array corresponds to a coset of $C$.
\nThere 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)),[])}
\nThis 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$.
\nThe 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 '))}$
\nThe coset leader of a coset is an element of minimum weight. There could be more than one choice of coset leader for a coset.
\nThe first column of the Slepian array gives a set of coset leaders.
\nThe syndrome of a word $w$ with respect to a parity matrix $\\mathrm{H}$ is $w\\mathrm{H^T}$.
\nFor 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]} \\]
\nOne 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.
\nAnother way is to compute its syndrome, and subtract the coset leader with the corresponding syndrome.
\nWe 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.
\nThe 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.
\nThere'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
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.
\nThe 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
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;i$\\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;iEnter your answer as a list of codewords separated by commas, e.g. 0000,1111,...
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;iCalculate syndromes for the coset leaders. Enter them as a list of words separated by commas, e.g. 000,111,...
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/"}]}