A single deletion error correcting code (SDECC) over binary alphabet is a set of fixed-length sequences consisting of two types of symbols, 0 and 1, such that the original sequence can be recovered for at most one deletion error. There is a conjecture “the upper bound for the size of SDECC is equal to the size of Varshamov- Tenengolts (VT) code.” This conjecture had been shown to be true when the code length is ten or less. In this paper, we discuss a method for calculating this upper bound by providing an integer linear programming solver with several linear constraints. As a new result, we obtained that the tight upper bound for the size of a single deletion error correcting code of length 11 is 172. In other words, we could prove that the conjecture is true for the case where the length is 11.

We investigate group coding for arbitrary finite groups acting linearly on vector spaces. These yield robust codes based on real or complex matrix groups. We give necessary and sufficient conditions for correct subgroup decoding using geometric notions of minimal length coset representatives. The infinite family of complex reflection groups G(r, 1, n) produces effective codes of arbitrarily large size that can be decoded in relatively few steps.

This paper builds on Mittelholzer and Lahtonen's study of group codes for the Gaussian channel based on reflection groups. A careful analysis of the action of a reflection group on its roots leads to the development of improved methods for encoding and decoding. The new algorithm is proved to achieve maximum likelihood decoding. The complexity of decoding is analyzed, and it is shown that a proper choice of the sequence of subgroups used in the algorithm can yield significant gains in the efficiency of decoding.

In this correspondence, the optimality of variant-I permutation codes initially proposed by Slepian [see proc. IEEE, vol. 53, no. 3, p. 228-236, Mar. 1965] is shown in a simple way.