Standard array

In coding theory, a standard array (or Slepian array) is a $q^\{n-k\}$ by $q^\{k\}$ array that lists all elements of a particular $mathbb\{F\}\_q^n$ vector space. Standard arrays are used to decode linear codes; i.e. to find the corresponding codeword for the received vector or message.

Definition

A standard array for an ["n","k"] -code is a $q^\{n-k\}$ by $q^\{k\}$ array where:

# The first row lists all codewords (with the 0 codeword on the extreme left)
# Each row is a coset with the coset leader in the first column
# The entry in the i-th row and j-th column is the sum of the i-th coset leader and the j-th codeword.

For example, the ["n","k"] -code $C\_\{3\}$ = {00000, 01101, 10110, 11011} has the following standard array:

Following step 3, we complete the row by adding the coset leader to each codeword.

We then repeat steps 2 and 3 until we have completed all rows. We stop when we have reached $q^\{n-k\}\; =\; 2^\{4-2\}\; =\; 2^\{2\}\; =\; 4$ rows.

Note that in this example we could not have chosen the vector 0001 as the coset leader of the final row, even though it meets the critedia of having minimal weight (1), because the vector was already present in the array.

Decoding via standard array

To decode a vector using a standard array, subtract the error vector - or coset leader - from the vector received. The result will be one of the codewords in $C$. For example, say we are using the code C = {0000, 1011, 0101, 1110}, and have constructed the corresponding standard array, as shown from the example above. If we receive the vector 0110 as a message, we find that vector in the standard array. We then subtract the vector's coset leader, namely 1000, to get the result 1110. We have received the codeword 1110.

Decoding via a standard array is a form of nearest neighbour decoding. In practise, decoding via a standard array requires large amounts of storage - a code with 32 codewords requires a standard array with $2^\{32\}$ entries. Other forms of decoding, such as syndrome decoding, are more efficient.

Note that decoding via standard array does not guarantee that all vectors are decoded correctly. If we receive the vector 1010, using the standard array above would decode the message as 1110, a codeword distance 1 away. However, 1010 is also distance 1 away from the codeword 1011. In such a case some implementations might ask for the message to be resent. This ambiguity is another reason that different decoding methods are sometimes used.

References

* Hill, Raymond. (1988). "A First Course In Coding Theory", New York: Oxford University Press.