Error Detection and Correction, Standard Array, Syndrome Decoding

The theory associated with Experiment-4 is divided into two parts:

  1. Standard array decoding
  2. Syndrome decoding

1. Standard array decoding

The decoding consists of estimating the transmitted codeword corresponding to the given received vector. Standard array decoding is a method for decoding linear block codes when the noise is introduced by the binary symmetric channel (BSC) with cross-over probability pp, denoted by BSC (p)(p). For a detailed description of standard array decoding, please refer to [1] (Chapter 4, Section 3.5). We shall next briefly discuss how to construct a standard array corresponding to the given linear block code C(n,k)\mathcal{C}(n,k) and then discuss how to decode the given received vector yF2n\mathbf{y} \in \mathbb{F}_2^n using it.

Let v1,v2,,v2k\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_{2^k} be the set of codewords of the given code C(n,k)\mathcal{C}(n,k). A codeword is chosen randomly and transmitted over the BSC to get the received vector yF2n\mathbf{y} \in \mathbb{F}_2^n. Note that for the BSC(p)(p), y\mathbf{y} can be any vector in F2n\mathbb{F}_2^n, irrespective of the transmitted codeword. The core idea of standard array construction consists of dividing all possible 2n2^n vectors into 2k2^k disjoint subsets such that there is exactly one codeword in each subset. Thus the given vector y\mathbf{y} can be associated with the unique codeword that lies in the same subset as that of y\mathbf{y}, and in standard array decoding, y\mathbf{y} is decoded to this codeword.

Standard Array General

Figure 1: A general structure of the standard array

For BSC(p)(p) with p<1/2p<1/2, an optimal way of dividing these 2n2^n vectors into 2k2^k disjoint subsets provides a standard array. A standard array is a table with 2k2^k columns and 2nk2^{n-k} rows such that a distinct vector in F2n\mathbb{F}_2^n is placed in each entry of this table. For the given row, the vector in the first column is called the coset leader of that row. The procedure for constructing a standard array is provided below:

  • First row: Put the all-zero codeword in the first row and the first column. Thus, the all-zero vector is the coset leader of the first row. The remaining 2k12^k-1 non-zero codewords are placed in the remaining columns of the first row. Without loss of generality, let v1\mathbf{v}_1 be the all-zero codeword and v2,v3,,v2k\mathbf{v}_2, \mathbf{v}_3, \ldots, \mathbf{v}_{2^k} be the non-zero codewords. Then the first row of the standard array is illustrated in Figure 1.
  • Rows 22 to 2nk2^{n-k}: For the jjth row, j=2,3,,2nkj = 2, 3, \ldots, 2^{n-k}, do the following:
    • Identify a vector of minimum weight that has not appeared in the rows 11 to j1j-1. This vector is chosen as the coset leader of the jjth row. Let ej\mathbf{e}_j denote the coset leader of the jjth row.
    • The remaining entries in the jjth row are obtained by adding ej\mathbf{e}_j to the codeword corresponding to each column, i.e., the entry in the iith column is given by ej+vi\mathbf{e}_j + \mathbf{v}_i, where i=2,3,,2ki = 2, 3, \ldots, 2^{k} (see Figure 1).

Note that the set of coset leaders {e2,e3,,e2nk}\{ \mathbf{e}_2, \mathbf{e}_3, \ldots, \mathbf{e}_{2^{n-k}}\} need not be unique. Further, the non-zero codewords v2,v3,,v2k\mathbf{v}_2, \mathbf{v}_3, \ldots, \mathbf{v}_{2^k} can be placed in any order in the first row of the standard array. Hence, a standard array corresponding to the given code is not unique. Let us consider an example for standard array construction.

Example 1:
Let {00000,11111,11000,01010,10101,00111,01101,10010}\{00000, 11111, 11000, 01010, 10101, 00111, 01101, 10010\} be the set of codewords of a linear block code of length n=5n=5. Note that the dimension of this code is k=3k=3. A standard array corresponding to this code is given in Table 1. It can be verified that this standard array is not unique.

Table 1: Standard array of a linear block code of length 5

Standard Array Example

Let us now discuss how to decode the given received vector y\mathbf{y} using the standard array. This procedure is summarized below:

  • Locate y\mathbf{y} in the standard array. Suppose y\mathbf{y} lies in the iith column.
  • y\mathbf{y} is decoded as vi\mathbf{v}_i, which is the codeword corresponding to the iith column.

Suppose vi\mathbf{v}_i is the transmitted codeword and ej\mathbf{e}_j is the error introduced by the BSC, then the received vector will be y=vi+ej\mathbf{y} = \mathbf{v}_i + \mathbf{e}_j. Observe that we will be able to correct such an error pattern via standard array decoding. It can be shown that the set of 2nk2^{n-k} coset leaders are the set of error patterns that can be corrected using standard array decoding.

2. Syndrome decoding

For the given linear block code C(n,k)\mathcal{C}(n,k) with parity check matrix HH, the syndrome of the given vector yF2n\mathbf{y} \in \mathbb{F}_2^n is defined as the vector sF2nk\mathbf{s} \in \mathbb{F}_2^{n-k} given by

syHT. \mathbf{s} \coloneqq \mathbf{y}H^T.

Consider the following properties of syndromes (proofs can be found in [1]):

  • Property 1: Syndromes of the vectors that lie in the same row of the standard array are the same, i.e., for y1\mathbf{y}_{1} and y2\mathbf{y}_{2} that lie in the same row of the standard array we have y1HT=y2HT. \mathbf{y}_{1}H^T = \mathbf{y}_{2}H^T.
  • Property 2: Syndromes of the vectors that lie in different rows of the standard array are different, i.e., for y1\mathbf{y}_{1} and y3\mathbf{y}_{3} that lie in different rows of the standard array we have y1HTy3HT. \mathbf{y}_{1}H^T \neq \mathbf{y}_{3}H^T.

Properties 1 and 2 indicate that there are exactly 2nk2^{n-k} distinct syndromes and these are the syndromes of the coset leaders. One only needs to keep track of the coset leaders and their corresponding syndromes and simplify the standard array decoding procedure as follows:

  • For the given received vector y\mathbf{y}, compute its syndrome s=yHT\mathbf{s} = \mathbf{y}H^T.
  • Locate the coset leader whose syndrome is equal to this s\mathbf{s}, i.e., locate coset leader ej\mathbf{e}_j such that ejHT=s\mathbf{e}_jH^T = \mathbf{s}.
  • The decoded codeword is given by v^=y+ej\hat{\mathbf{v}} = \mathbf{y} + \mathbf{e}_j.

It can be verified that the standard array and syndrome decoding are equivalent and would decode the given y\mathbf{y} to the same codeword. The advantage of syndrome decoding is that the storage space required is less as compared with standard array decoding.