A Generalized Upper Bound and a Multilevel Construction for Distance-Preserving Mappings

Author

Swart, Theo G. ; Ferreira, Hendrik C.

Author_Institution

Electr. & Electron. Eng. Sci., Univ. of Johannesburg

Volume

52

Issue

8

fYear

2006

Firstpage

3685

Lastpage

3695

Abstract

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

Keywords

Hamming codes; binary sequences; DPM; Hamming distance; binary sequence; distance-increasing mapping; distance-preserving mapping; distance-reducing mapping; multilevel construction; permutation sequence; Africa; Australia; Binary sequences; Block codes; Convolutional codes; Error correction codes; Hamming distance; Information theory; Upper bound; Code constructions; Hamming distance; distance bounds; distance-preserving mappings (DPMs); permutation coding;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2006.878175

Filename

1661845