  Determining the largest size, or equivalently finding the lowest redundancy,
of q-ary codes for given length and minimum distance is one of the central and
fundamental problems in coding theory. Inspired by the construction of
Varshamov-Tenengolts (VT for short) codes via check-sums, we provide an
explicit construction of nonlinear codes with lower redundancy than linear
codes under the same length and minimum distance. Similar to the VT codes, our
construction works well for small distance (or even constant distance).
Furthermore, we design quasi-linear time decoding algorithms for both erasure
and adversary errors.
