NEW MULTILEVEL CODES OVER GF(Q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GF(n1)(q)(n1 less-than-or-equal-to q), and both multilevel block codes and multilevel trellis codes over GF(q) are constructed. Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d(min) greater-than-or-equal-to d are presented, where n = n1n2, k = n - SIGMA(i = 1)n1 min {inverted right perpendicular d/i inverted left perpendicular - 1, n2}, n1 less-than-or-equal-to q, n2 less-than-or-equal-to q + 1, and inverted right perpendicular x inverted left perpendicular is the smallest integer larger than or equal to x. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q + 1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols, but larger distance, than the best previously known quaternary one-level block codes. Finally, it is proved that if all the component block codes are linear, the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes are also used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes, some of which have a performance/complexity advantage over one-level trellis (convolutional) codes. For small n1, the codes have simple decoding algorithms based on multistage decoding.