Editing Coset (section)

== An application from coding theory ==
{{main|Standard array}}
A binary linear code is an {{mvar|n}}-dimensional subspace {{mvar|C}} of an {{mvar|m}}-dimensional vector space {{mvar|V}} over the binary field {{math|GF(2)}}. As {{mvar|V}} is an additive abelian group, {{mvar|C}} is a subgroup of this group. Codes can be used to correct errors that can occur in transmission. When a ''codeword'' (element of {{mvar|C}}) is transmitted some of its bits may be altered in the process and the task of the receiver is to determine the most likely codeword that the corrupted ''received word'' could have started out as. This procedure is called ''decoding'' and if only a few errors are made in transmission it can be done effectively with only a very few mistakes. One method used for decoding uses an arrangement of the elements of {{mvar|V}} (a received word could be any element of {{mvar|V}}) into a [[standard array]]. A standard array is a coset decomposition of {{mvar|V}} put into tabular form in a certain way. Namely, the top row of the array consists of the elements of {{mvar|C}}, written in any order, except that the zero vector should be written first. Then, an element of {{mvar|V}} with a minimal number of ones that does not already appear in the top row is selected and the coset of {{mvar|C}} containing this element is written as the second row (namely, the row is formed by taking the sum of this element with each element of {{mvar|C}} directly above it). This element is called a [[coset leader]] and there may be some choice in selecting it. Now the process is repeated, a new vector with a minimal number of ones that does not already appear is selected as a new coset leader and the coset of {{mvar|C}} containing it is the next row. The process ends when all the vectors of {{mvar|V}} have been sorted into the cosets.

An example of a standard array for the 2-dimensional code {{math|1=''C'' = {{mset|00000, 01101, 10110, 11011}}}} in the 5-dimensional space {{mvar|V}} (with 32 vectors) is as follows:

{| class="wikitable"
|-
! 00000 !! 01101 !! 10110 !! 11011
|-
| 10000 || 11101 || 00110 || 01011
|-
| 01000 || 00101 || 11110 || 10011
|-
| 00100 || 01001 || 10010 || 11111
|-
| 00010 || 01111 || 10100 || 11001
|-
| 00001 || 01100 || 10111 || 11010
|-
| 11000 || 10101 || 01110 || 00011
|-
| 10001 || 11100 || 00111 || 01010
|}

The decoding procedure is to find the received word in the table and then add to it the coset leader of the row it is in. Since in binary arithmetic adding is the same operation as subtracting, this always results in an element of {{mvar|C}}. In the event that the transmission errors occurred in precisely the non-zero positions of the coset leader the result will be the right codeword. In this example, if a single error occurs, the method will always correct it, since all possible coset leaders with a single one appear in the array.

[[Syndrome decoding]] can be used to improve the efficiency of this method. It is a method of computing the correct coset (row) that a received word will be in. For an {{mvar|n}}-dimensional code {{mvar|C}} in an {{mvar|m}}-dimensional binary vector space, a [[parity check matrix]] is an {{math|(''m'' − ''n'') × ''m''}} matrix {{mvar|H}} having the property that {{math|1='''x'''''H''<sup>T</sup> = '''0'''}} [[if and only if]] {{math|'''x'''}} is in {{mvar|C}}.<ref>The transpose matrix is used so that the vectors can be written as row vectors.</ref> The vector {{math|'''x'''''H''<sup>T</sup>}} is called the ''syndrome'' of {{math|'''x'''}}, and by [[linearity]], every vector in the same coset will have the same syndrome. To decode, the search is now reduced to finding the coset leader that has the same syndrome as the received word.<ref>{{harvnb|Rotman|2006|loc=p. 423}}</ref>