Построение согласованной функции расстояния для простого марковского канала

Введение. Проблема исправления ошибок в канале связи может быть решена определением наиболее вероятного вектора ошибок в канале. При этом в ряде случаев решается эквивалентная задача нахождения вектора минимального веса. Это требует введения функции расстояния, согласованной с каналом связи. В классической теории кодирования традиционно используются метрики Хэмминга и Евклида, в то время как для многих каналов связи согласованные с ними функции расстояния неизвестны. Построение таких функций может снизить вероятность ошибки декодирования и является актуальной задачей. В данной работе предложено решение проблемы разработки функции декодирования, совпадающей с декодированием по максимуму правдоподобия в простом марковском канале. Метод. Выполнен анализ вероятностей векторов в простом марковском канале. Разработанная функция расстояния представлена как сумма набора коэффициентов, зависящих от параметров канала. Предложен способ вычисления коэффициентов, при которых функция является согласованной с каналом. Рассмотрено несколько аппроксимаций для случая, когда параметры канала неизвестны или известны неточно. На примере сверточного кодирования экспериментально оценено влияние предложенной функции и ее аппроксимаций на вероятность ошибки. Основные результаты. Сформулировано правило, обеспечивающее декодирование по максимуму правдоподобия в простом марковском канале. Предложенная функция расстояния согласована с каналом при любых длинах кодов, в отличие от известных марковских метрик. Рассмотрены вопросы выбора коэффициентов функции декодирующего правила, упрощающие вычисление функции с возможным нарушением согласованности. На основе полученной функции представлена экспериментальная оценка вероятности ошибки по максимуму правдоподобия для сверточного кода в простом марковском канале. Приведена оценка влияния аппроксимации коэффициентов на вероятность ошибки декодирования. Дано сравнение предложенного решения с известным классом марковских метрик. Обсуждение. Проведенные эксперименты показали, что предложенная согласованная функция и ее упрощенный вариант обеспечивают значительное снижение вероятности ошибки по сравнению с метрикой Хэмминга, а также известной марковской метрикой при низких значениях априорной вероятности битовой ошибки. Использование квантований значений функции практически не увеличивает вероятность ошибки декодирования по сравнению с декодированием по максимуму правдоподобия. Метод, основанный на анализе вероятности векторов в канале с двумя состояниями, может быть использован при разработке декодирующих функций для более сложных моделей каналов Гилберта и Гилберта–Эллиотта. Такие функции позволяют повысить надежность передачи сообщений в каналах со сложной структурой шума и обеспечивают декодирование по максимуму правдоподобия в марковском канале, в то время как традиционный подход к декорреляции канала существенно снижает пропускную способность.

1. Крук Е.А. Комбинаторное декодирование линейных блоковых кодов. Монография. СПб: ГУАП, 2007, 238 с.

2. Bogatyrev A.V., Bogatyrev V.A., Bogatyrev S.V. The probability of timeliness of a fully connected exchange in a redundant real-time communication system // Proc. of the Wave Electronics and its Application in Information and Telecommunication Systems (WECONF). 2020. P. 1–4. https://doi.org/10.1109/weconf48837.2020.9131517

3. Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S.V. Multipath transmission of heterogeneous traffic in acceptable delays with packet replication and destruction of expired replicas in the nodes that make up the path // Communications in Computer and Information Science. 2023. V. 1748. P. 104–121. https://doi.org/10.1007/978-3-031-30648-8_9

4. Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Control of multipath transmissions in the nodes of switching segments of reserved paths // Proc. of the International Conference on Information, Control, and Communication Technologies (ICCT). 2022. P. 1–5. https://doi.org/10.1109/icct56057.2022.9976839

5. Lin S., Li J. Fundamentals of Classical and Modern Error-Correcting Codes. Cambridge University Press, 2022. 840 p.

6. Gabidulin E. A brief survey of metrics in coding theory // Proc. of the Mathematics of Distances and Applications. 2012. P. 66–84.

7. Firer M., Walker J.L. Matched metrics and channels // IEEE Transactions on Information Theory. 2016. V. 62. N 3. P. 1150–1156. https://doi.org/10.1109/TIT.2015.2512596

8. D’Oliveira R., Firer M. Channel metrization // European Journal of Combinatorics. 2019. V. 80. P. 107–119. https://doi.org/10.1016/j.ejc.2018.02.026

9. Qureshi C.M. Matched metrics to the binary asymmetric channels // IEEE Transactions on Information Theory. 2019. V. 65. N 2. P. 1106– 1112. https://doi.org/10.1109/TIT.2018.2885782

10. Miyamoto G.A., Firer M. Obtaining binary perfect codes out of tilings // IEEE Transactions on Information Theory. 2020. V. 66. N 10. P. 6121–6132. https://doi.org/10.1109/TIT.2020.2988865

11. Cotardo G., Ravagnani A. Parameters of codes for the binary asymmetric channel // IEEE Transactions on Information Theory. 2022. V. 68. N 5. P. 2941–2950. https://doi.org/10.1109/TIT.2022.3147593

12. Zhang A., Jing X., Feng K. Optimal combinatorial neural codes with matched metric δr: characterization and constructions // IEEE Transactions on Information Theory. 2023. V. 69. N 8. P. 5440–5448. https://doi.org/10.1109/TIT.2023.3266010

13. Xu Y., Kan H., Han G. MacWilliams extension property with respect to weighted poset metric // IEEE Transactions on Information Theory. 2024. V. 70. N 2. P. 995–1007. https://doi.org/10.1109/TIT.2023.3328262

14. Xiao X., Vasic B., Lin S., Li J., Abdel–Ghaffar K. Quasi-cyclic LDPC codes with parity-check matrices of column weight two or more for correcting phased bursts of erasures // IEEE Transactions on Communications. 2021. V. 69. N 5. P. 2812–2823. https://doi.org/10.1109/tcomm.2021.3059001

15. Li L., Lv J., Li Y., Dai X., Wang X. Burst Error Identification Method for LDPC Coded Systems // IEEE Communications Letters. 2024. V. 28. N 7. P. 1489–1493. https://doi.org/10.1109/lcomm.2024.3391826

16. Ovchinnikov А.А., Veresova А.М., Fominykh А.А. Decoding of linear codes for single error bursts correction based on the determination of certain events // Informatsionno-upravliaiushchie sistemy [Information and Control Systems]. 2022. N 6. P. 41–52. https://doi.org/10.31799/1684-8853-2022-6-41-52

17. Исаева М.Н., Овчинников А.А. Исправление одиночных пакетов ошибок за пределами корректирующей способности кода с использованием информационных совокупностей // Научно-технический вестник информационных технологий, механики и оптики. 2024. Т. 24, N 1. С. 70–80. https://doi.org/10.17586/2226-1494-2024-24-1-70-80

18. Aharoni Z., Huleihel B., Pfister H.D., Permuter H.H. Data-Driven polar codes for unknown channels with and without memory // Proc. of the IEEE International Symposium on Information Theory (ISIT). 2023. P. 1–6. https://doi.org/10.1109/isit54713.2023.10206663

19. Fang Y., Chen J. Decoding polar codes for a generalized Gilbert-Elliott channel with unknown parameter // IEEE Transactions on Communications. 2021. V. 69. N 10. P. 6455–6468. https://doi.org/10.1109/TCOMM.2021.3095195

20. Veresova A., Fominykh A., Ovchinnikov A. About usage of metrics in decoding of LDPC codes in Two-State channels with memory // Proc. of the XVII International Symposium Problems of Redundancy in Information and Control Systems (REDUNDANCY). 2021. P. 1–6. https://doi.org/10.1109/REDUNDANCY52534.2021.9606474

21. Veresova A., Ovchinnikov A. Usage of Markov Metric in decoding of convolutional codes in Two-State channels // Proc. of the IEEE 3rd International Conference on Problems of Informatics, Electronics and Radio Engineering (PIERE). 2024. P. 1–5. https://doi.org/10.1109/piere62470.2024.10805044