Definition:Coset Decoding Table
Definition
A coset decoding table is a technique for decoding a linear $\tuple {n, k}$ code.
Let $C$ be a linear $\tuple {n, k}$ code whose master code is $\map V {n, p}$.
Let $T$ be an array constructed as follows:
- The first row consists of the codewords of $C$, starting with the zero codeword first.
 | This article, or a section of it, needs explaining. In particular: It has not yet been rigorously proved that $C$ does actually contain the zero codeword. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code. |
- Each subsequent row is a left coset of $C$.
- The entries of the first column of $T$ are the coset representatives, now called coset leaders.
- The $r$th coset leader is allocated by choosing any element of $\map V {n, p}$ of minimum weight which is not already included in the first $r - 1$ rows.
Then $T$ is a coset decoding table.
Note that it may not always be easy to find the $r$th coset leader.
Examples
Linear $\tuple {4, 2}$-code in $\Z_3$
Let $C$ be the linear code:
- $C = \set {0000, 0112, 0221, 1011, 1120, 1202, 2022, 2101, 2210}$
Then the coset decoding table $T$ for $C$ is:
- $\begin{array} {cccccccc}
0000 & 0112 & 0221 & 1011 & 1120 & 1202 & 2022 & 2101 & 2210 \\ 1000 & 1112 & 1221 & 2011 & 2120 & 2202 & 0022 & 0101 & 0210 \\ 0100 & 0212 & 0021 & 1111 & 1220 & 1002 & 2122 & 2201 & 2010 \\ 0010 & 0122 & 0201 & 1021 & 1100 & 1212 & 2002 & 2111 & 2220 \\ 0001 & 0110 & 0222 & 1012 & 1121 & 1200 & 2020 & 2102 & 2211 \\ 2000 & 2112 & 2221 & 0011 & 0120 & 0202 & 1022 & 1101 & 1210 \\ 0200 & 0012 & 0121 & 1211 & 1020 & 1102 & 2222 & 2001 & 2110 \\ 0020 & 0102 & 0211 & 1001 & 1110 & 1222 & 2012 & 2121 & 2200 \\ 0002 & 0111 & 0220 & 1010 & 1122 & 1201 & 2021 & 2100 & 2212 \\ \end{array}$
Linear $\tuple {6, 3}$-code in $\Z_2$
Let $C$ be the linear code:
- $C = \set {000000, 100110, 010101, 110011, 001011, 101101, 011110, 111000}$
Then the coset decoding table $T$ for $C$ is:
- $\begin{array} {cccccccc}
000000 & 100110 & 010101 & 110011 & 001011 & 101101 & 011110 & 111000 \\ 100000 & 000110 & 110101 & 010011 & 101011 & 001101 & 111110 & 011000 \\ 010000 & 110110 & 000101 & 100011 & 011011 & 111101 & 001110 & 101000 \\ 001000 & 101110 & 011101 & 111011 & 000011 & 100101 & 010110 & 110000 \\ 000100 & 100010 & 010001 & 110111 & 001111 & 101001 & 011010 & 111100 \\ 000010 & 100100 & 010111 & 110001 & 001001 & 101111 & 011100 & 111010 \\ 000001 & 100111 & 010100 & 110010 & 001010 & 101100 & 011111 & 111001 \\ 100001 & 000111 & 110100 & 010010 & 101010 & 001100 & 111111 & 011001 \\ \end{array}$
Also see
Sources
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $6$: Error-correcting codes