<div>
	Вересова А.М., Овчинников А.А.<br />
	Построение согласованной функции расстояния для простого марковского канала</div>

2025 , ТОМ 25, НОМЕР 1 ( январь-февраль )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

Вересова А.М., Овчинников А.А.
Построение согласованной функции расстояния для простого марковского канала

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Вересова А.М., Овчинников А.А. Построение согласованной функции расстояния для простого марковского канала // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 1. С. 160–168. doi: 10.17586/2226-1494-2025-25-1-160-168

Аннотация

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

Ключевые слова: канал с конечным числом состояний, марковские цепи, согласованные метрики, декодирование по максимуму правдоподобия, правило декодирования, алгоритм Витерби

Благодарности. Статья подготовлена в результате проведения исследования в рамках Программы фундаментальных исследований Национального исследовательского университета «Высшая школа экономики» (НИУ ВШЭ), лаборатория Интернета вещей и киберфизических систем НИУ ВШЭ в Санкт-Петербурге.

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

Крук Е.А. Комбинаторное декодирование линейных блоковых кодов. Монография. СПб: ГУАП, 2007, 238 с.
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
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
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
Lin S., Li J. Fundamentals of Classical and Modern Error-Correcting Codes. Cambridge University Press, 2022. 840 p.
Gabidulin E. A brief survey of metrics in coding theory // Proc. of the Mathematics of Distances and Applications. 2012. P. 66–84
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
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
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
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
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
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
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
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
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
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
Исаева М.Н., Овчинников А.А. Исправление одиночных пакетов ошибок за пределами корректирующей способности кода с использованием информационных совокупностей // Научно-технический вестник информационных технологий, механики и оптики. 2024. Т. 24, N 1. С. 70–80. https://doi.org/10.17586/2226-1494-2024-24-1-70-80
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
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
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
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

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License