Standard array: Difference between revisions

Revision as of 02:53, 24 February 2008

Latest revision as of 21:44, 26 December 2023

(30 intermediate revisions by 22 users not shown)

Line 1:

{{Short description|Array for a particular vector space}}

In [[coding theory]], a '''standard array''' (or Slepian array) is a <math>q^{n-k}</math> by <math>q^{k}</math> array that lists all elements of a particular <math>\mathbb{F}_q^n</math> [[vector space]]. Standard arrays are used to [[Decoding methods|decode]] [[linear code]]s; i.e. to find the corresponding [[Code word (communication)|codeword]] for theany received vector or message.

== Definition ==

A standard array for an [''n'',''k'']-code is a <math>q^{n-k}</math> by <math>q^{k}</math> array where:

# The first row lists all [[Code word (communication)|codewords]] (with the <u>0</u> 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''5'',k''2'']-code <math>C_{3}</math> = {00000<u>0</u>, 01101, 10110, 11011} has the followinga standard array as follows:

{| class="wikitable"

|-

| <u>[[Zero vector|0]]</u>

| 01101

| 10110

Line 54 ⟶ 55:

|}

The above is only one possibility for the standard array; had 00011 been chosen as the first [[coset leader]] of weight two, another standard array representing the code would have been constructed.

(Note: the vector containing all zeros is often abbreviated as <u>0</u>.)

Note that theThe first row contains the <u>0</u> vector and the codewords of <math>C_{3}</math> (<u>0</u> itself being a codeword). Also, the leftmost column contains the vectors of [[Hamming_weightHamming weight|minimum weight]] enumerating vectors of weight 1 first and then using vectors of weight 2. Note also thatAlso each possible vector in the vector space appears exactly once.

== Constructing a standard array ==

Line 67 ⟶ 68:

# Repeat steps 2 and 3 until all rows/cosets are listed and each vector appears exactly once.

Note that addingAdding vectors is done mod q. For example, binary codes are added mod 2 (which equivalent to bit-wise XOR addition). For example, in <math>Z_{2}</math>, 11000 + 11011 = 00011.

Note also thatThat selecting different coset leaders will create a slightly different but equivalent standard array, and will not affect results when decoding. <!--TODO: proof needed? Lagrange Theorem -->

=== Construction Exampleexample ===

Let <math>C</math> be the [[Binary code|binary]] [4,2]-code. i.e. C = {0000, 1011, 0101, 1110}. To construct the standard array, we first list the codewords in a row.

{| class="wikitable"

Line 109 ⟶ 110:

| 0011

| 1101

| 11100110

|}

Line 124 ⟶ 125:

| 0011

| 1101

| 11100110

|-

| 0100

Line 137 ⟶ 138:

|}

Note that inIn this example we could not have chosen the vector 0001 as the coset leader of the final row, even though it meets the critediacriteria of having minimal weight (1), because the vector was already present in the array. We could, however, have chosen it as the first coset leader and constructed a different standard array.

== Decoding via standard array ==

Line 143 ⟶ 144:

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 <math>C</math>. 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 practisepractice, decoding via a standard array requires large amounts of storage - a code with 32 codewords requires a standard array with <math>2^{32}</math> entries. Other forms of decoding, such as [[syndrome decoding]], are more efficient.

Note that decodingDecoding 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, or the ambiguous bit may be marked as an erasure and a following [[Concatenated error correction code|outer code]] may correct it. This ambiguity is another reason that different decoding methods are sometimes used.

== See also ==

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.

* [[Linear code]]

== References ==

*{{cite book

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

|last = Hill

|first = Raymond

|author-link = Raymond Hill (computer scientist)

|title = A First Course in Coding Theory

|url = https://archive.org/details/firstcourseincod0000hill

|url-access = registration

|publisher = [[Oxford University Press]]

|series = Oxford Applied Mathematics and Computing Science series

|year = 1986

|isbn = 978-0-19-853803-5}}

[[Category:Coding theory]]