We introduce a new construction for the balancing of non-binary sequences that make use of Gray codes for prefix coding. Our construction provides full encoding and decoding of sequences, including the prefix. This construction is based on a generalization of Knuth's parallel balancing approach, which can handle very long information sequences. However, the overall sequence-composed of the information sequence, together with the prefix-must be balanced. This is reminiscent of Knuth's serial algorithm. The encoding of our construction does not make use of lookup tables, while the decoding process is simple and can be done in parallel.

We investigate a Knuth-like scheme for balancing q-ary code words, which has the virtue that lookup tables for coding and decoding the prefix are avoided by using precoding and error correction techniques. We show how the scheme can be extended to allow for error correction of single channel errors using a fast decoding algorithm that depends on syndromes only, making it considerably faster compared with the prior art exhaustive decoding strategy. A comparison between the new and prior art schemes, both in terms of redundancy and error performance, completes the study.

We present an encoding and decoding scheme for constant weight sequences, that is, given an information sequence, the construction results in a sequence of specific weight within a certain range. The scheme uses a prefix design that is based on Gray codes. Furthermore, by adding redundant symbols we extend the range of weight values for output sequences, which is useful for some applications.

Balancing sequences over a non-binary alphabet is considered, where the algebraic sum of the components (also known as the weight) is equal to some specific value. Various schemes based on Knuth's simple binary balancing algorithm have been proposed. However, these have mostly assumed that the prefix describing the balancing point in the algorithm can easily be encoded. In this paper we show how non-binary Gray codes can be used to generate these prefixes. Together with a non-binary balancing algorithm, this forms a complete balancing system with straightforward and efficient encoding/decoding.

The recently proposed Pearson codes offer immunity against channel gain and offset mismatch. These codes have very low redundancy, but efficient coding procedures were lacking. In this paper, systematic Pearson coding schemes are presented. The redundancy of these schemes is analyzed for memoryless uniform sources. It is concluded that simple coding can be established at only a modest rate loss.

Codes are presented that can correct the deletion or the insertion of a predetermined number of adjacent bits greater than or equal to three. This extends the constructions of codes beyond those proposed by Levenshtein fifty years ago to correct one or two adjacent deletions or insertions.

Permutation codes are advantageous due to their favourable symbol diversity properties and are applied in flash memories combined with rank modulation. Codebooks traditionally consist of permutations with specific distance properties. A class of permutation codes was presented where a codeword consists of a sequence or concatenation of permutations, rather than a single permutation. These codebooks were constructed to correct substitution or deletion errors. In this paper, permutations are concatenated to form codewords with the goal of detecting and correcting adjacent transposition errors. An outer code is used to detect erroneous permutations in the codeword, using additional parity permutations. The symbol diversity of permutation codes is preserved and codebooks with higher cardinalities are constructed which result in better code rates.

A new class of permutation codes is presented where, instead of considering one permutation as a codeword, codewords consist of a sequence of permutations. The advantage of using permutations, i.e. their favourable symbol diversity properties, is preserved. Additionally, using sequences of permutations as codewords, code rates close to the optimum rate can be achieved. Firstly, the complete set of permutations is divided into subsets by using set partitioning. Binary data is then mapped to permutations from these subsets. These permutations, together with a parity permutation, will form the codeword. Two constructions will be presented: one capable of detecting and correcting substitution errors and the other capable of detecting and correcting either substitution or deletion errors.

We present a Knuth-like method for balancing q-ary codewords, which is characterized by the absence of a prefix that carries the information of the balancing index. Look-up tables for coding and decoding the prefix are avoided. We also show that this method can be extended to include error correction of single channel errors.

For communication schemes employing Frequency Hopping/Multiple Frequency Shift Keying modulation, we present an algorithm for finding good non-binary synchronization sequences, which are permutations, to be used with permutation codes to synchronize/resynchronize data in channels with background noise and interference(frequency jamming/fading). For the synchronization sequences, new analytical expressions for the probability of false acquisition are also given. Using simulation results, we show that our synchronization sequences perform better than some conventional non-binary synchronization sequences, in the presence of background noise and interference.

We propose the construction of a non-binary multiple insertion/deletion correcting code based on a binary multiple insertion/deletion correcting code. In essence, it is a generalisation of Tenengol'ts' non-binary single insertion/deletion correcting code. We evaluate the cardinality of the proposed construction based on the asymptotic upper bound on the cardinality of a maximal binary multiple insertion/deletion correcting code derived by Levenshtein.

Balancing of q-ary sequences, using a generalization of Knuth's efficient parallel balancing scheme, is considered. It is shown that the new general scheme is as simple as the original binary scheme, which lends itself to parallel decoding of the balanced sequences.

Templates are constructed to extend arbitrary additive error correcting or constrained codes, i.e., additional redundant bits are added in selected positions to balance the moment of the codeword. The original codes may have error correcting capabilities or constrained output symbols as predetermined by the usual communication system considerations, which are retained after extending the code. Using some number theoretic constructions in the literature, insertion/deletion correction can then be achieved. If the template is carefully designed, the number of additional redundant bits for the insertion/deletion correction can be kept small-in some cases of the same order as the number of parity bits in a Hamming code of comparable length.

A new way of looking at permutation distance-preserving mappings (DPMs) is presented by making use of a graph representation. The properties necessary to make such a graph distance-preserving, are also investigated. Further, this new knowledge is used to analyze previous constructions, as well as to construct a new general mapping algorithm for a previous multilevel construction.

We investigate extending a chosen block or convolutional code which has additive error correction capability, as predetermined by the usual communication systems or coding considerations. Our extension involves constructing a template to add additional redundant bits in positions, selected to balance the moment of the code word. Using some number theoretic constructions in the literature, insertion/deletion correction can then be achieved. If the template is carefully designed, the number of additional redundant bits for the insertion/deletion correction can be kept small - in some cases of the same order as for Hamming codes. Our construction technique can also be used for the systematic encoding of number theoretic codes, and furthermore have implications for other coding techniques utilizing the moment function, such as codes correcting asymmetrical errors, spectral shaping codes, or constant weight codes.

A multilevel construction is introduced to create distance-preserving mappings from binary sequences to permutation sequences. It is also shown that for certain values, the new mappings attain the upper bound on the sum of Hamming distances obtainable for such mappings, and in the other cases improve on those of previous mappings

A new general upper bound is derived on the sum of the Hamming distances between sequences when mapping from one set of sequences to another. It is shown that a similar upper bound for mappings from binary sequences to permutation sequences is a special case of this upper bound and this is used to evaluate known mappings. Also, new distance-preserving mappings (DPMs) from binary sequences to permutation sequences are presented, based on a multilevel construction. In addition to explicit distance-conserving mappings, distance-increasing, and distance-reducing mappings are also presented. Several of the new DPMs attain the upper bound

We investigate the optimal Hamming distance that is achievable when mapping binary sequences to permutation sequences. This is used to determine how close to optimum some of the known mappings are. Furthermore, using simulation results we show that mappings found by exhaustive search using optimum distance as criterion perform better than previous known mappings

We introduce the new concept of permutation trellis codes and present a generalized construction procedure, applying our technique of distance-preserving mappings. Minimum-distance decoding follows naturally, using the Viterbi algorithm. We furthermore investigate the performance of these codes when combined with multitone frequency-shift keying modulation and noncoherent detection in a diversity scheme, to make transmissions robust against narrowband, broadband, and background noise disturbances, such as those encountered in power-line communications.

We present a new insertion/deletion detection and correcting decoding scheme for convolutional codes that is based on the Viterbi decoding algorithm. Firstly, we show that, when using a coding scheme that utilises a standard rate, R=k/n, convolutional code and n Viterbi decoders in parallel, it is possible to correct up to n-1 consecutive deletions or insertions. Our results show the effectiveness of this scheme to re-establish bit-synchronisation after the deletion of bits. Further, we investigate the correction of multiple deletions or insertions using standard concatenated coding schemes employing convolutional inner codes, and Reed-Solomon outer codes.

By using a run-length representation of sequences, ways to determine suband supersequences are discussed. This is then used in determining the number of sub- and supersequences of a sequence after double insertions or deletions. It is also used in creating subsequence/supersequence books that are searched to find new double insertion/deletion correcting code books with higher cardinalities than those already known.