Точная корректирующая способность кодов Гилберта при исправлении пакетов ошибок


https://doi.org/10.15217/issn1684-8853.2016.1.80

Полный текст:


Аннотация

Постановка проблемы: для решения задачи повышения скорости обмена информацией в системах передачи и хранения данных требуется разрабатывать эффективные методы борьбы с помехами, возникающими при передаче, хранении и обработке информации, при использовании как можно меньшей избыточности. Для этого необходимо строить схемы кодирования, ориентированные на ошибки, характерные для конкретного канала связи. Большинство реальных каналов связи являются каналами с группированием ошибок, и типичная помеха в таком канале может описываться как пакет ошибок. Коды Гилберта, обладающие простыми процедурами кодирования и декодирования, хотя и имеют малое минимальное расстояние и неэффективны для исправления независимых ошибок, тем не менее могут быть использованы для исправления пакетов ошибок. Однако корректирующая способность этих кодов при исправлении пакетов ошибок оценивается лишь с помощью не всегда точных границ. Цель: получение точных значений максимальных длин исправляемых пакетов для кодов Гилберта в зависимости от параметров их конструкции. Результаты: разработана процедура, позволяющая для заданных параметров конструкции кодов Гилберта вычислять точное значение максимальной длины исправляемого пакета. В основе построения этой процедуры лежит анализ структуры проверочной матрицы кодов Гилберта, а также структуры пакетов, которые не могут быть исправлены при декодировании с помощью проверочной матрицы. Новизна результата заключается в том, что при любых параметрах конструкции процедура позволяет вычислять точное значение корректирующей способности соответствующего кода Гилберта. Практическая значимость: полученные точные значения корректирующей способности кодов Гилберта могут применяться для аналитических оценок вероятностей ошибок в каналах с памятью при использовании этих кодов, а также могут учитываться при выборе более эффективных схем кодирования в системах передачи и хранения данных.

Об авторах

Евгений Аврамович Крук
Санкт-Петербургский государственный университет аэрокосмического приборостроения
Россия


Андрей Анатольевич Овчинников
Санкт-Петербургский государственный университет аэрокосмического приборостроения
Россия


Список литературы

1. Proakis J., Salehi M. Digital Communications. - McGraw-Hill, 2007. - 1150 p.

2. Krouk E. A., Ovchinnikov A. A. Metrics for Distributed Systems // Problems of Redundancy in Information and Control Systems (REDUNDANCY): XIV Intern. Symp., 1-5 June 2014. P. 66-70. doi:10.1109/ RED.2014.7016708

3. Krouk E., Semenov S., et al. Modulation and Coding Techniques in Wireless Communications/Edited by E. Krouk, S. Semenov. - John Wiley & Sons, 2011. - 680 p. doi:10.1002/9780470976777

4. MacWilliams F., Sloane N. The Theory of Error-Correcting Codes. - North-Holland publishing company, 1983. - 782 p.

5. Lin S., Ryan W. Channel Codes: Classical and Modern. - Cambridge university press, 2009. - 710 p.

6. Gallager R. G. Low-Density Parity-Check Codes // IRE Transactions on Information Theory. Jan. 1962. Vol. 8. N 1. P. 21-28. doi:10.1109/TIT.1962.1057683

7. Gallager R. G. Low Density Parity Check Codes. - Cambridge, MA: MIT Press, 1963. - 90 p.

8. MacKay D. J. C. Good Error-Correcting Codes Based on Very Sparse Matrices // IEEE Transactions on Information Theory. Mar. 1999. Vol. 45. N 2. P. 399431. doi:10.1109/18.748992

9. MacKay D. J. C., Neal R. M. Near Shannon Limit Performance of Low Density Parity Check Codes // Electronics Letters. 13 Mar. 1997. Vol. 33. N 6. P. 457-458. doi:10.1049/el:19970362

10. Richardson T. J., Urbanke R. L. The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding // IEEE Transactions on Information Theory. Feb. 2001. Vol. 47. N 2. P. 599-618. doi:10.1109/18.910577

11. Zyablov V. V., Pinsker M.S. Estimation of the Error-Correction Complexity for Gallager Low-Density Codes // Problems of Information Transmission. 1975. Vol. 11. N 1. P. 23-36.

12. Chung S.-Y., Forney G. D., Richardson T. J., Urbanke R. On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit // Communications Letters. IEEE. Feb. 2001. Vol. 5. N 2. P. 58-60. doi:10.1109/4234.905935

13. Козлов А. В., Крук Е. А., Овчинников А. А. Подход к построению блочно-перестановочных кодов с малой плотностью проверок на четность // Изв. вузов. Приборостроение. 2013. Т. 56. № 8. С. 9-14.

14. Gilbert E. N. A Problem in Binary Encoding // Proc. of the Symp. in Applied Mathematics. 1960. Vol. 10. P. 291-297.

15. Arazi B. The Optimal Burst Error-Correcting Capability of the Codes Generated by f(x)=(x"p+1)(x"q+1)/(x+1) // Information and Control. 1978. Vol. 39. N 3. P. 303-314.

16. Bahl L., Chien R. On Gilbert Burst-Error-Correcting Codes // IEEE Transactions on Information Theory. May 1969. Vol. 15. N 3. P. 431-433. doi:10.1109/ TIT.1969.1054310

17. Neumann P. G. A Note on Gilbert Burst-Correcting Codes // IEEE Transactions on Information Theory. Jul. 1965. Vol. 11. N 3. P. 377-384. doi:10.1109/ TIT.1965.1053780

18. Zhang W., Wolf J. K. A Class of Binary Burst Error-Correcting Quasi-Cyclic Codes // IEEE Transactions on Information Theory. May 1988. Vol. 34. N 3. P. 463-479. doi:10.1109/18.6026

19. Krouk E. A., Semenov S. V. Low-Density Parity-Check Burst Error-Correcting Codes // Algebraic and Combinatorial Coding Theory: International Workshop. Leningrad, 1990. P. 121-124.


Дополнительные файлы

Для цитирования: Крук Е.А., Овчинников А.А. Точная корректирующая способность кодов Гилберта при исправлении пакетов ошибок. Информационно-управляющие системы. 2016;(1):80-87. https://doi.org/10.15217/issn1684-8853.2016.1.80

For citation: Krouk E.A., Ovchinnikov A.A. Exact Burst-Correction Capability of Gilbert Codes. Information and Control Systems. 2016;(1):80-87. (In Russ.) https://doi.org/10.15217/issn1684-8853.2016.1.80

Просмотров: 25


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)