Abstract
Our research is focused on mapping binary sequences to permutation sequences. It is established
that an upper bound on the sum of the Hamming distance for all mappings exists,
and this sum is used as a criterion to ascertain how good previously known mappings
are. We further make use of permutation trellis codes to investigate the performance of
certain permutation mappings in a power-line communications system, where background
noise, narrow band noise and wide band noise are present.
A new multilevel construction is presented next that maps binary sequences to permutation
sequences, creating new mappings for which the sum of Hamming distances
are greater than previous known mappings. It also proved that for certain lengths of
sequences, the new construction can attain our new upper bound on the sum of Hamming
distances.
We further extend the multilevel construction by showing how it can be applied to
other mappings, such as permutations with repeating symbols and mappings with nonbinary
inputs. We also show that a subset of the new construction yields permutation
sequences that are able to correct insertion and deletion errors as well.
Finally, we show that long binary sequences, formed by concatenating the columns of
binary permutation matrices, are subsets of the Levenshtein insertion/deletion correcting
codes.
Prof. H. C. Ferreira