Улучшения границ Левенштейна в q-ичных пространствах Хэмминга

Получены улучшения границ Левенштейна в q-ичных пространствах Хэмминга, которые учитывают дискретную природу расстояний в отличие от рассмотренного Левенштейном непрерывного поведения некоторых параметров. Разобраны первые соответствующие случаи и приведены новые границы. В частности, получены обобщения и q-ичные аналоги границы Мак-Элиса. Кроме того, приведены данные, позволяющие предположить, что такой подход дает столь же хорошие результаты, что и полное линейное программирование, и обсуждается скорость соответствующих вычислений. Наконец, представлена таблица параметров кодов, которые в случае их существования будут достигать наших границ.

Ключевые слова

Источник финансирования

Работа выполнена при частичной финансовой поддержке Национального научного фонда Болгарии (номер контракта DN02/2-13.12.2016). Работа выполнена при частичной финансовой поддержке Совета по научным исследованиям Швеции (VR) и программы ELLIIT.

Получено

13.12.2018

Дата публикации

13.12.2018

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Бойваленков П. , Мая С. , Данев Д. . Улучшения границ Левенштейна в q-ичных пространствах Хэмминга // Проблемы передачи информации – 2018. – Tом 54. – Выпуск 4 C. 35-50 [Электронный ресурс]. URL: http://ras.jes.su/ppi/s055529230003077-8-1 (дата обращения: 07.05.2024). DOI: 10.31857/S055529230003077-8
MLA	Boivalenkov, Peter, Stoyanova, Maya, Danev, Danio "Refinements of Levenshtein Bounds in q-ary Hamming Spaces." Problemy peredachi informatsii 54.4 (2018):35-50. DOI: 10.31857/S055529230003077-8
APA	Boivalenkov P., Stoyanova M., Danev D. (2018). Refinements of Levenshtein Bounds in q-ary Hamming Spaces. Problemy peredachi informatsii 54(4), pp.35-50 DOI: 10.31857/S055529230003077-8

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1191

Оценка читателей: голосов 0

1. Delsarte P., Levenshtein V.I. Association Schemes and Coding Theory // Trans. Inform. Theory. 1998. V. 44. № 6. P. 2477–2504.

2. Levenshtein V.I. Designs as Maximum Codes in Polynomial Metric Spaces // Acta Appl. Math. 1992. V. 29. № 1–2. P. 1–82.

3. Levenshtein V.I. Universal Bounds for Codes and Designs // Handbook of Coding Theory. V. I. Ch. 6. Amsterdam: Elsevier, 1998. P. 499–648.

4. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования. М.: Мир, 1976.

5. Levenshtein V.I. Krawtchouk Polynomials and Universal Bounds for Codes and Designs in Hamming Spaces // IEEE Trans. Inform. Theory. 1995. V. 41. № 5. P. 1303–1321.

6. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

7. Tiet?av?ainen A. Bounds for Binary Codes Just Outside the Plotkin Range // Inform. Control. 1980. V. 47. № 2. P. 85–93.

8. Krasikov I., Litsyn S. Linear Programming Bounds for Codes of Small Sizes // Europ. J. Combin. 1997. V. 18. № 6. P. 647–656.

9. Сидельников В.М. Овзаи мной корреляции последовательностей // ДАН СССР. 1971. Т. 196. № 3. С. 531–534.

10. Perttula A. Bounds for Binary and Nonbinary Codes Slightly Outside of the Plotkin Range: Ph.D. Thesis. Tampere Univ. of Technology. Tampere, Finland, 1982.

11. Szeg?o G. Orthogonal Polynomials. New York: Amer. Math. Soc., 1939.

12. Барг А.М., Ногин Д.Ю. Спектральный подход к границам линейного программирования для кодов // Пробл. передачи информ. 2006. Т. 42. № 2. С. 12–25.

13. Бойваленков П., Данев Д. Ограницах линейного программирования для кодов в полиномиальных метрических пространствах // Пробл. передачи информ. 1998. Т. 34. № 2. С. 16–31.

14. Krasikov I., Litsyn S., On Integral Zeros of Krawtchouk Polynomials // J. Combin. Theory Ser. A. 1996. V. 74. № 1. P. 71–99.

15. Stroeker R.J., de Weger, B.M.M. On Integral Zeroes of Binary Krawtchouk Polynomials // Nieuw Arch. Wisk. (4). 1999. V. 17. № 2. P. 175–186.

16. Bounds for Parameters of Codes. Sage Project (Software for Algebra and Geometry Experimentation). http://doc.sagemath.org/html/en/reference/coding/sage/coding/code_bounds.html.

17. Barg A., Jaffe D. Numerical Results on the Asymptotic Rate of Binary Codes // Codes and Association Schemes. DIMACS Ser., V. 56. Providence, R.I.: Amer. Math. Soc., 2001. P. 25–32.

18. Samorodnitsky A. On the Optimum of Delsarte’s Linear Program // J. Combin. Theory Ser. A. 2001. V. 96. № 2. P. 261–287.

19. Gijswijt D., Schrijver A., Tanaka H. New Upper Bounds for Nonbinary Codes Based on the Terwilliger Algebra and Semidefinite Programming // J. Combin. Theory Ser. A. 2006. V. 113. № 8. P. 1719–1731.

20. Schrijver A. New Code Upper Bounds from the Terwilliger Algebra and Semidefinite Programming // IEEE Trans. Inform. Theory. 2005. V. 51. № 8. P. 2859–2866.

21. Litjens B., Polak S., Schrijver A. Semidefinite Bounds for Nonbinary Codes Based on Quadruples // Des. Codes Cryptography. 2017. V. 84. № 1–2. P. 87–100.

22. Brouwer A.E. Tables of Codes. http://www.win.tue.nl/~aeb/.

23. Boyd S., Vandenberghe L. Convex Optimization. Cambridge: Cambridge Univ. Press, 2004.

24. Kerdock A.M. A Class of Low-Rate Nonlinear Binary Codes // Inform. Control. 1972. V. 20. P. 182–187.

25. Agrell E., Vardy A., Zeger K. A Table of Upper Bounds for Binary Codes // IEEE Trans. Inform. Theory. 2001. V. 47. № 7. P. 3004–3006.

26. Best M.R., Brouwer A.E., MacWilliams F.J., Odlyzko A.M., Sloane N.J.A. Bounds for Binary Codes of Length Less than 25 // IEEE Trans. Inform. Theory. 1978. V. 24. № 1. P. 81–93.

27. Hedayat A., Sloane N.J.A., Stufken J. Orthogonal Arrays: Theory and Applications. New York: Springer, 1999.