×

On the dual distance and the gap of a binary code. (English) Zbl 0949.94006

Authors’ introduction: The gap of a code [P. Solé and H. F. Mattson jun., The gap of a code, unpublished memorandum (1988)] like the covering radius is a parameter occuring naturally in rate distortion theory, which has been little explored so far by combinatorialists. While the covering radius measures the worst-case distortion, the gap is the average distortion. In terms of coset graph of a linear code the covering radius is the diameter [C. Delorme and P. Solé, Eur. J. Comb. 12, 95-108 (1991; Zbl 0737.05067)], while the gap is the average distance. In this note we use some results of F. Shahrokhi and L. A. Székely [Comb. Probab. Comput. 3, 523-543 (1994; Zbl 0817.05022)] on the average distance of sufficiently symmetric graphs to derive a lower bound on the gap of sufficiently symmetric codes.

MSC:

94B15 Cyclic codes
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barthélémy, J. P.; Cohen, G. D.; Lobstein, A., Complexité Algorithmique (1992), Masson: Masson Paris · Zbl 0765.68005
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance Regular Graphs (1989), Springer: Springer Berlin · Zbl 0747.05073
[3] Berger, T., Rate Distortion Theory (1971), Prentice-Hall: Prentice-Hall Englewood-Cliffs, NJ
[4] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press: Academic Press New York · Zbl 0458.05042
[5] Delorme, C.; Solé, P., Diameter, covering number, covering radius and Eigenvalues, J. Eu. de Combin., 12, 95-108 (1991) · Zbl 0737.05067
[6] Lovász, L., Combinatorial Problems and Exercises (1979), Akademiai Kiado: Akademiai Kiado Budapest · Zbl 0439.05001
[7] Mohar, B., The Laplacian spectrum of graphs, (Alavi, Y.; etal., Graph Theory, Combinatorics, and Applications (1991), Wiley: Wiley New York), 871-898 · Zbl 0840.05059
[8] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1981), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[9] Shahrokhi, F.; Székely, L. A., On canonical concurrent flows, crossing numbers and graph expansion, Combin. Probab. and Comput., 3, 4, 523-544 (1994) · Zbl 0817.05022
[10] Solé, P., The forwarding index of orbital-regular graphs, Discrete Math., 130, 171-176 (1994) · Zbl 0807.05037
[11] Solé, P., Expanding and Forwarding, Discrete Appl. Math., 58, 67-78 (1995) · Zbl 0820.05034
[12] Solé, P.; Mattson, H. F., The gap of a code (1988), unpublished memorandum
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.