Linear codes extension for Numbas

You must be signed in to change notification settings

# numbas/numbas-extension-codewords

## Folders and files

NameName
Last commit message
Last commit date

Â

Â
Â
Â
Â
Â
Â

# Linear codes extension for Numbas

This extension provides a new data type and some functions to deal with linear codes.

A collection of questions created using this extension is available to reuse.

## JME data types

This extension adds two new JME data types, `Numbas.jme.types.codeword` and `Numbas.jme.types.code`.

## JME functions

### `codeword(digits,field_size)`

Create a codeword from a list or vector of digits, in Z_{field_size}. For example, `codeword([1,1,0,1],2)`

### `codeword(word_string,field_size)`

Create a codeword from a string of digits, in Z_{field_size}. For example, `codeword("11001",2)`

### `zero(word_length,field_size)`

The zero word of the given length in the field Z_{field_size}.

### `is_zero(word)`

Is `word` a zero word (are all its digits 0)?

### `latex(codeword)`

A LaTeX rendering of the given codeword.

### `word1-word2`

Subtract one codeword from another.

### `n*word` or `word*n`

Multiply a codeword by a scalar.

### `word[n]`

nth digit of codeword.

### `word[m..n]`

List of mth to nth digits of codeword.

### `weight(w)`

Hamming weight of the word.

### `allwords(word_length,field_size)`

Generate a list of all codewords of given length in Z_{field_size}.

### `random_word(word_length,field_size)`

Pick a random word of given length in Z_{field_size}.

### `random_combination(words)`

A random linear combination of the given words (from the field `Z_p`), i.e. `a_0*w_0 + a_1*w_1 + ... + a_n*w_n` where the `a_i` are elements of the field `Z_p`.

### `set_generated_by(basis)`

Returns the set of codewords generated by the given list of basis codewords.

### `is_generated_by(basis,words)`

Can all of the given words be written as a linear combination of the words in `basis`?

### `linearly_independent(basis)`

Are the given codewords linearly independent? (it checks that the set generated by the basis contains `(field_size)^(number of basis words)` words)

### `coset_containing(word,basis)`

Generate the coset containing the given word, with respect to the given generating set.

### `slepian_array(basis)`

Generate the Slepian array corresponding to the given basis set. Each row in the result is a coset, sorted by weight.

### `is_coset_leader(word,basis)`

Is the given word a coset leader in its coset? That is, does it have the minimum weight?

### `generator_matrix(words)`

A minimal set of generators for the linear code generated by the given words. If the words are linearly independent, you'll get the same number of words back, otherwise you'll get fewer.

### `parity_check_matrix(basis)`

Create a parity check matrix for the given generating set, by putting it in reduced row-echelon form `I_n|A` and returning `-A_transpose|I_(m)`.

### `lexicographic_parity_check_matrix(words)`

Create a parity check matrix for the given generating set, with columns in lexicographic order.

### `hamming_parity_check_matrix(p,r)`

Create a parity check matrix for the Hamming code `Ham_p(r)`. (`p` must be prime)

### `hamming_generating_matrix(p,r)`

Create a generating matrix for the Hamming code `Ham_p(r)`. (`p` must be prime)

### `syndrome(word,pcm)`

Compute the syndrome of the given word with respect to the given parity check matrix.

### `reduced_row_echelon_form(basis)`

Put the given list of words (interpreted as a matrix) into reduced row-echelon form.

### `codeword_matrix(words)`

Returns a matrix whose rows are the given codewords.

### `hamming_square_encode(word)`

Encode `word` using Hamming's square code.

### `hamming_square_decode(word)`

Decode (and correct up to one error in) `word` using Hamming's square code.

### `hamming_encode(word)`

Encode `word` using the general Hamming code.

### `hamming_decode(word)`

Decode (and correct up to one error in) `word` using the general Hamming code.

### `hamming_distance(word1,word2)`

Hamming distance between two codewords.

### `hamming_ball(word,radius)`

All words within given Hamming distance of the given codeword.

### `hamming_sphere(word,radius)`

All words at given Hamming distance from the given codeword.

### `concat([words])`

Concatenate a list of codewords into one codeword.

### `len(word)`

Length of a codeword.

### `error(word,position)`

Introduce an error (change a digit) at the given position. Returns a new codeword.

### `check_array(word)`

Returns a LaTeX check-array for the given word, from a Hamming square code.

### `string(word)`

String representation of a codeword.

### `latex(word)`

LaTeX representation of a codeword.

### `code([words])`

Create a code from a complete set of codewords.

### `allwords(code)`

All words belonging to the given code.

### `minimum_distance(code)`

Minimum Hamming distance between words in code.

### `information_rate(code)`

A code's information rate

### `len(code)`

Number of words in code.

### `code[n]`

nth word in code. (in the order used when you created the code object)

### `code[m..n]`

List of the mth to nth words in code.

### `positional_permutation(code,positions)`

Permute the positions of the digits in code's words, following the given order.

### `symbolic_permutation(code,symbols)`

Permute the symbols in code's words, following the given order. `symbols` is a list giving a permutation for each digit. That is, `symbols[i][j]` says what symbol `j` should change to when in position `i`.

### `equivalent(code1,code2)`

Can `code2` be obtained from `code1` by a combination of positional and symbolic permutations?

### `find_equivalence(code1,code2)`

If `code1` is equivalent to `code2`, find a combination of positional and symbolic permutations that maps `code1` to `code2`.

Returns a dictionary with keys `"positional_permutation"` and `"symbolic_permutation"` when the codes are equivalent, and `nothing` if they're not.

### `find_positional_equivalence(code1,code2)`.

If `code1` is positionally equivalent to `code2`, find a positional permutation that maps `code1` to `code2`.

Returns a list representing a permutation of codeword digits when the codes are positionally equivalent, and `nothing` if they're not.

### `find_symbolic_equivalence(code1,code2)`.

If `code1` is symbolically equivalent to `code2`, find a symbolic permutation that maps `code1` to `code2`.

Returns a list representing a permutation of the symbols for each codeword digits when the codes are symbolically equivalent, and `nothing` if they're not.

### `distance_equivalent(code1,code2)`

Is there an isomorphism between the Hamming distance tables of `code1` and `code2`?

Returns `true` if there is a permutation of the rows and columns of the Hamming distance table of `code1` that produces the table for `code2`.

### `hamming_bound(field_size,word_length,errors_corrected)`

Hamming bound on the maximum number of codewords in a code with the given parameters.

### `singleton_bound(field_size,word_length,minimum_distance)`

Singleton bound on the maximum number of codewords in a code with the given parameters.

### `gilbert_varshamov_bound(field_size,word_length,minimum_distance)`

Gilbert-Varshamov bound on the minimum number of codewords in a code with the given parameters.

## JavaScript functions

Everything lives under `Numbas.extensions.codewords`, which I'll omit from now on.

### `Codeword(digits,field_size)`

Create a codeword with the given digits, belonging to the field `Z_{field_size}`.

#### `Codeword` methods

##### `word.toString()`

String representation of the word.

##### `word.toLaTeX()`

LaTeX representation of the word.

##### `word.toJME()`

JME representation of the word.

##### `word.isZero()`

Is the word zero (are all its digits 0)?

##### `word.eq(word2)`

Is this word the same as `word2`?

##### `word.add(word2)`

Return a new word which is the sum of this word and `word2`.

##### `word.sub(word2)`

Subtract `word2` from this word (returns a new codeword object).

##### `word.negate()`

Negate this word: `w.add(w.negate()) = 0`.

##### `word.scale(n)`

Scale this word by `n` - multiply every digit by `n`.

##### `word.weight()`

Hamming weight of this word - number of non-zero digits.

##### `word.LaTeX_check_array()`

LaTeX rendering of a Hamming square code check array for this word (only makes sense if this word is a 9-digit binary word)

##### `word.hamming_ball(radius)`

Find all words within `radius` Hamming distance of this word.

##### `word.hamming_sphere(radius)`

Find all words with Hamming distance exactly `radius` from this word.

#### Static methods of the `Codeword` class

##### `fromString(str,field_size)`

Create a codeword object from a string representation, e.g. `Codeword.fromString("01001",2)`.

##### `sort(w1,w2)`

Comparison function to sort codewords lexicographically.

##### `eq(w1,w2)`

Equivalent to `w1.eq(w2)`.

### `zero_word(word_length,field_size)`

Create a zero word with the given length in the field `Z_{field_size}`.

### `allwords(word_length,field_size)`

Get all words of the given length in the field `Z_{field_size}`.

### `random_word(word_length,field_size)`

Get a random word of the given length in the field `Z_{field_size}`.

### `random_combination(basis)`

A random linear combination of the given words (from the field `Z_p`), i.e. `a_0*w_0 + a_1*w_1 + ... + a_n*w_n` where the `a_i` are elements of the field `Z_p`.

### `set_generated_by(words)`

Get all words generated by the given basis set.

### `is_generated_by(basis,words)`

Can all of the given words be written as a linear combination of the words in `basis`?

### `linearly_independent(words)`

Are all of the given words linearly independent of each other?

Words are linearly independent if `l1*w1 + l2*w2 + .. +ln*wn = 0` has no solution other than `l1=l2=...=ln=0`.

### `coset_containing(word,basis)`

Generate the coset containing the given word, with respect to the given generating set.

### `slepian_array(basis)`

Generate the Slepian array corresponding to the given basis set. Each row in the result is a coset, sorted by weight.

### `is_coset_leader(word,basis)`

Is the given word a coset leader in its coset? That is, does it have the minimum weight?

### `hamming_distance(word1,word2)`

Hamming distance between two words.

### `reduced_row_echelon_form(basis)`

Put the given list of words (interpreted as a matrix) into reduced row-echelon form by reordering and taking linear combinations.

### `generator_matrix(words)`

A minimal set of generators for the linear code generated by the given words. If the words are linearly independent, you'll get the same number of words back, otherwise you'll get fewer.

### `parity_check_matrix(basis)`

A parity check matrix for the given generating set (which should be linearly independent)

### `lexicographic_parity_check_matrix(basis)`

A parity check matrix for the given generating set, with columns in lexicographic order.

### `hamming_square_encode(word)`

Encode `word` using Hamming's square code.

### `hamming_square_decode(word)`

Decode (and correct up to one error in) `word` using Hamming's square code.

### `hamming_encode(word)`

Encode `word` using the general Hamming code.

### `hamming_decode(word)`

Decode (and correct up to one error in) `word` using the general Hamming code.

### `syndrome(word,pcm)`

Compute the syndrome of the given word with respect to the given parity check matrix.

### `hamming_parity_check_matrix(p,r)`

Create a parity check matrix for the Hamming code `Ham_p(r)`. (`p` must be prime)

### `hamming_generating_matrix(p,r)`

Create a generating matrix for the Hamming code `Ham_p(r)`. (`p` must be prime)

`Ham_p(r)` is the `p`-ary Hamming code whose PCM has `r` rows

### `Code(words)`

A wrapper object for the code containing the given words.

#### `Code` methods

##### `code.toString()`

String representation of the code - list all its words.

##### `code.toLaTeX()`

LaTeX representation of the code.

##### `code.toJME()`

JME representation of the code.

##### `code.eq(code2)`

Is this code the same as `code2`? True if they have exactly the same words.

##### `code.contains(word)`

Does this code contain `word`?

##### `code.find_equivalence(code2)`

If this code is equivalent to `code2`, return an object `{positional_permutation, symbolic_permutation}`. If not, return `null`.

Two codes are equivalent if we can get from one to the other by a combination of positional and symbolic permutations.

##### `code.equivalent(code2)`

Is this code equivalent to `code2` - can you get from one to the other by performing positional and symbolic permutations on the digits of the codewords?

##### `code.minimum_distance()`

The minimum Hamming distance between any pair of words in this code.

##### `code.information_rate()`

Information rate of the code: `log(number of words)/(log(2)*word length)`

##### `code.positional_permutation(order)`

Perform a positional permutation on the words in the code. `order` is a list, where column `i` is sent to `order[i]`. Returns a new `Code` object.

##### `code.symbolic permutation(symbols)`

Perform a symbolic permutation on the words in the code. `symbols` is a list of permutations for each digit, where symbol `j` in position `i` is changed to `symbols[i][j]`. Returns a new `Code` object.

### `hamming_bound(field_size,word_length,errors_corrected)`

Hamming bound on the maximum number of codewords in a code with the given parameters.

### `singleton_bound(field_size,word_length,minimum_distance)`

Singleton bound on the maximum number of codewords in a code with the given parameters.

### `gilbert_varshamov_bound(field_size,word_length,minimum_distance)`

Gilbert-Varshamov bound on the minimum number of codewords in a code with the given parameters.

## Marking functions

### `mark_codeword_set(part,field_size,fn)`

To be used on a "match text pattern" part, where the student's answer is a list of codewords separated by commas.

Checks that the student's answer is valid, and parses it to a list of `Codeword` objects in the given field, then calls `fn(words)`. In `fn`, `this` refers to the given `part` object.

### `validate_codeword_set(part)`

Validate a part marked by the above function. Shows a warning message if the student's answer can't be interpreted as a list of codewords separated by commas.

Linear codes extension for Numbas

## Releases

No releases published