// Numbas version: exam_results_page_options {"name": "Construct a Slepian array and find coset leaders", "extensions": ["codewords", "permutations"], "custom_part_types": [], "resources": [], "navigation": {"showfrontpage": false, "preventleave": false, "allowregen": true}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"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}$.

", "preamble": {"js": "", "css": ""}, "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"}, "functions": {"inline_latex": {"language": "jme", "type": "string", "parameters": [["s", "codeword"]], "definition": "'$'+latex(s)+'$'"}, "identity_left": {"language": "javascript", "type": "list", "parameters": [["words", "list"]], "definition": "// add an identity matrix to the left 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]]

", "unitTests": [], "type": "gapfill", "gaps": [{"numColumns": 1, "allowFractions": false, "variableReplacementStrategy": "originalfirst", "unitTests": [], "showFeedbackIcon": true, "markPerCell": false, "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,...

", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "answer": "", "matchMode": "regex", "variableReplacements": []}, {"variableReplacementStrategy": "originalfirst", "unitTests": [], "type": "patternmatch", "scripts": {"validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}, "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"}}, "displayAnswer": "{join(map(string(x),x,word_coset),',')}", "showCorrectAnswer": true, "marks": 1, "showFeedbackIcon": true, "prompt": "

List the words in the coset containing $\\var{word}$.

", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "answer": "", "matchMode": "regex", "variableReplacements": []}, {"variableReplacementStrategy": "originalfirst", "unitTests": [], "type": "patternmatch", "scripts": {"validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}, "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.

", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "answer": "", "matchMode": "regex", "variableReplacements": []}, {"variableReplacementStrategy": "alwaysreplace", "unitTests": [], "type": "patternmatch", "scripts": {"validate": {"script": "return Numbas.extensions.codewords.validate_codeword_set(this);", "order": "instead"}, "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"}}, "displayAnswer": "{join(map(string(x),x,syndromes),',')}", "showCorrectAnswer": true, "marks": "1.5", "showFeedbackIcon": true, "prompt": "

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

", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "answer": "{join(syndromes,',')}", "matchMode": "regex", "variableReplacements": []}, {"variableReplacementStrategy": "originalfirst", "unitTests": [], "type": "patternmatch", "scripts": {}, "displayAnswer": "{string(transmitted_word)}", "showCorrectAnswer": true, "marks": "1", "showFeedbackIcon": true, "prompt": "

You receive a codeword $\\var{received_word}$ and know there has been one error. Correct the error and enter the corrected codeword.

", "extendBaseMarkingAlgorithm": true, "customMarkingAlgorithm": "", "answer": "{transmitted_word+''}", "matchMode": "regex", "variableReplacements": []}], "variable_groups": [], "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"], "statement": "

$C$ is a {nary} linear code with generator matrix

\n

\$\\mathrm{G} =\\var{G} \$

", "variables": {"nary": {"group": "Ungrouped variables", "name": "nary", "description": "", "templateType": "anything", "definition": "[\"\",\"unary\",\"binary\",\"ternary\",\"$4$-ary\",\"$5$-ary\"][field_size]"}, "C": {"group": "Ungrouped variables", "name": "C", "description": "

The code generated by the generator matrix $G$

", "templateType": "anything", "definition": "code(C_words)"}, "g": {"group": "Ungrouped variables", "name": "g", "description": "

A random generating matrix for the code, not in standard form.

", "templateType": "anything", "definition": "codeword_matrix(G_words)"}, "word": {"group": "Ungrouped variables", "name": "word", "description": "

A randomly chosen word not from the coset.

", "templateType": "anything", "definition": "random(allwords(word_length,field_size) except C_words)"}, "slep": {"group": "Ungrouped variables", "name": "slep", "description": "", "templateType": "anything", "definition": "slepian_array(g_words)"}, "dimension": {"group": "Ungrouped variables", "name": "dimension", "description": "

Dimension of the code - number of rows in the generating matrix.

", "templateType": "anything", "definition": "3"}, "received_word": {"group": "Ungrouped variables", "name": "received_word", "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", "definition": "transmitted_word+coset_leaders[random(unique_coset_leader_indices)]\n//error(transmitted_word,random(0..word_length-1))"}, "C_words": {"group": "Ungrouped variables", "name": "C_words", "description": "", "templateType": "anything", "definition": "set_generated_by(G_words)"}, "word_coset": {"group": "Ungrouped variables", "name": "word_coset", "description": "

The coset containing word

", "templateType": "anything", "definition": "slep[word_index]"}, "field_size": {"group": "Ungrouped variables", "name": "field_size", "description": "", "templateType": "anything", "definition": "2"}, "unique_coset_leader_indices": {"group": "Ungrouped variables", "name": "unique_coset_leader_indices", "description": "

", "templateType": "anything", "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)"}, "coset_leaders": {"group": "Ungrouped variables", "name": "coset_leaders", "description": "", "templateType": "anything", "definition": "map(x[0],x,slep)"}, "M": {"group": "Ungrouped variables", "name": "M", "description": "

Standard generating matrix for the code.

", "templateType": "anything", "definition": "identity_left(A)"}, "word_index": {"group": "Ungrouped variables", "name": "word_index", "description": "

The index of the coset containing word

", "templateType": "anything", "definition": "let(syn_word,syndrome(word,pcm),\n sum(map(if(syndromes[x]=syn_word,x,0),x,0..len(coset_leaders)-1))\n)"}, "G_dual": {"group": "Ungrouped variables", "name": "G_dual", "description": "

Parity check matrix for $M$ (a generator matrix for the dual code of $M$)

", "templateType": "anything", "definition": "codeword_matrix(pcm)"}, "syndromes": {"group": "Ungrouped variables", "name": "syndromes", "description": "", "templateType": "anything", "definition": "map(syndrome(x,pcm),x,coset_leaders)"}, "transmitted_word": {"group": "Ungrouped variables", "name": "transmitted_word", "description": "", "templateType": "anything", "definition": "random(C_words except zero(word_length,field_size))"}, "A": {"group": "Ungrouped variables", "name": "A", "description": "

The generating matrix is $I_{dim}|A$, where $A$ is random.

", "templateType": "anything", "definition": "repeat(codeword(repeat(random(0..field_size-1),word_length-dimension),field_size),dimension)"}, "q": {"group": "Ungrouped variables", "name": "q", "description": "", "templateType": "anything", "definition": "received_word-transmitted_word"}, "pcm": {"group": "Ungrouped variables", "name": "pcm", "description": "", "templateType": "anything", "definition": "parity_check_matrix(M)"}, "dual_dimension": {"group": "Ungrouped variables", "name": "dual_dimension", "description": "

Dimension of the dual code

", "templateType": "anything", "definition": "word_length-dimension"}, "word_length": {"group": "Ungrouped variables", "name": "word_length", "description": "

Length of each word in the code

", "templateType": "anything", "definition": "6"}, "g_words": {"group": "Ungrouped variables", "name": "g_words", "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", "definition": "shuffle(set_generated_by(M))[0..dimension]"}}, "type": "question", "rulesets": {}, "extensions": ["codewords", "permutations"], "name": "Construct a Slepian array and find coset leaders", "tags": [], "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/"}], "variablesTest": {"maxRuns": "100", "condition": "linearly_independent(G_words)\nand\nlen(unique_coset_leader_indices)<>0\nand\nnot (received_word in c_words)"}}]}], "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/"}]}