УДК 004

Обзор методов помехоустойчивого кодирования данных

Коваленко Константин Юрьевич – аспирант кафедры Радиофизики Института физики Казанского (Приволжского) федерального университета.

Аннотация: Одной из ключевых областей применения кодирования является радиосвязь, где помехоустойчивые коды позволяют передавать большие объемы цифровой информации с минимальным количеством ошибок. Существует множество различных помехоустойчивых кодов, начиная от простых и распространенных, таких как код Хэмминга и коды с проверкой на четность, и заканчивая передовыми разработками, такими как стеганографический алгоритм и турбокоды. В статье рассмотрены простые и современные коды, а также описано, в каких отраслях радиосвязи они наиболее часто используются. Кодирование играет важную роль в обеспечении более надежной передачи данных и защиты информации от несанкционированного доступа, а также важно в ответственных сферах, например, медицине.

Ключевые слова: кодирование, помехоустойчивое кодирование, радиосвязь, надёжность передачи данных, простые коды.

Введение

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

Простые коды

Для того, чтобы перейти к рассмотрению современных помехоустойчивых кодов, необходимо начать с базовых, так как зачастую именно они лежат в основе современных, сложных кодов. Главный недостаток таких кодов заключается в ограниченности обнаружения и исправления ошибок.

Коды с проверкой на четность являются одними из самых распространённых. Эти коды строятся с использованием одной общей проверки на четность. Это происходит путем добавления одного дополнительного бита к сообщению для обеспечения четного числа единиц в каждом слове передачи данных. Если количество единиц нечетное, то дополнительный бит устанавливается в 1, а если четное, то дополнительный бит устанавливается в 0. На приемной стороне, при получении слова, суммируются по модулю два все биты и дополнительный бит. Если результат равен 0, то сообщение передано без ошибок. Если в результате получилась 1, то сообщение содержит ошибку. С помощью этих кодов можно обнаружить единичную ошибку, но восстановить поврежденную информацию они не в состоянии. Главное преимущество кодов с проверкой на четность – простота реализации. В настоящее время эти коды используются в составе более сложных кодов, а также могут быть эффективны для коротких сообщений и каналов связи с низким уровнем помех.

Код Хэмминга – это один из наиболее распространенных методов помехоустойчивого кодирования, который позволяет обнаруживать и исправлять одиночные ошибки в передаче цифровых данных. Код Хэмминга работает путем добавления дополнительных битов в сообщение для создания определенной структуры данных, в которой биты используются для представления комбинаций битов данных и контрольных битов. В состав кода входят информационные символы длины X, а также дополнительные контрольные, количество которых в блоке равно ⌊log₂(X)⌋. В коде Хэмминга используется определенный алгоритм расчета контрольных битов, располагаемых на позициях с номерами, равными степеням двойки, который позволяет создавать более эффективные коды с более высокой помехоустойчивостью, чем коды с проверкой на четность. Контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N, используя сумму по модулю два. В результате, если при передаче данных произойдет единичная ошибка, то на приемной стороне можно обнаружить, какой бит был искажен и исправить его, или просто исправить двойную ошибку. Коды Хэмминга используются во многих областях, включая компьютерные сети, телекоммуникации, хранение данных и других местах, где точность и надежность передачи цифровых данных являются критически важными. Этот код также используется как часть более сложных кодов [1].

Циклический избыточный код – это еще один код, который занимается обнаружением ошибок, он может использоваться вместе с кодом Хэмминга и кодами с проверкой на четность. Отличительной особенностью этого кода является способ кодирования информации, основанный на свойстве деления с остатком двоичных многочленов, что позволяет с хорошей точностью определять ошибки в передаваемых сообщениях. Исходное сообщение разбивается на блоки битов, которые рассматриваются как многочлены. Затем, в случае систематического кодирования, вычисляется остаток от деления на определенный многочлен, который и является кодом для данного сообщения. Для получения кодового слова информационный и порождающий полином перемножаются в случае несистематического кодирования [2].

Код Боуза-Чоудхури-Хоквингама, или, как его еще называют, код БЧХ – это метод помехоустойчивого кодирования, позволяющий обнаруживать и исправлять одиночные и множественные ошибки в передаче цифровых данных. В последнее время был вытеснен более совершенными кодовыми алгоритмами. Этот код отличается особым выбором полинома, образующего циклический код, возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием, что облегчает декодирование передаваемой информации [3].

Блочные неравномерные коды – это класс кодов, в которых синтаксические элементы (например, символы) закодированы различным количеством битов (т.е. переменной длиной). Эти коды позволяют обнаруживать ошибки благодаря их избыточности, а также используются для сжатия данных, так как они позволяют кодировать наиболее часто встречающиеся символы более короткими кодами. Одним из примеров блочных неравномерных кодов является алгоритм Хаффмана. Он основан на принципе, что часто встречающиеся символы должны быть закодированы меньшим количеством битов, чем реже встречающиеся символы. Следуя этому принципу, алгоритм Хаффмана создает оптимальный префиксный код, то есть код, в котором нет никаких префиксов, которые являются кодами других символов. Другим примером блочных неравномерных кодов являются коды Шеннона-Фано, которые также используются для сжатия данных путем изменения длины кодированного сообщения. Неравномерные коды используются всюду: в видео- и аудио-компрессии, сжатии данных, сжатии текстовой информации и во многих других областях. особенностью этих кодов является то, что в этих алгоритмах все кодовые комбинации содержат разное количество битов при постоянной длительности импульса [2].

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

Современные помехоустойчивые коды

Более сложные алгоритмы помехоустойчивого кодирования, зачастую использующие базовые, сегодня используются повсеместно.

Код Рида-Соломона – это метод коррекции ошибок, который используется для защиты данных в цифровых коммуникационных системах, является частным случаем БЧХ-кода, используя в качестве кодового вектора не биты, а блоки, например, байты (октеты). Он был разработан в 1960-х годах Джеймсом Ридом и Густавом Соломоном. Основная идея кода Рида-Соломона заключается в добавлении избыточности в исходные данные. Кодированные данные содержат не только исходные данные, но также дополнительные данные, которые используются для детектирования и исправления ошибок. В основе кода Рида-Соломона лежит математическая теория над полем Галуа, которая позволяет генерировать кодовые слова с максимальной избыточностью. Кроме исправления ошибок, код Рида-Соломона также может восстанавливать стертые или неразборчивые символы. Этот метод кодирования предлагает более надежную защиту данных в сравнении с другими методами кодирования, в частности другими циклическими кодами и кодом Хэмминга. Код Рида-Соломона широко используется в различных сферах, включая цифровое телевидение, интернет-связь, хранение данных, обработку изображений и видео и т.д. Этот код является стандартом некоторых технологий, таких как CD-ROM, DVD, Blu-ray и QR-коды, используются в стандартах связи, в том числе Интернет, IEEE802.16 и других [2].

Низкоплотностные коды (Low-Density Parity-Check Code, LDPC) - это тип линейного блочного кода, который используется в цифровой связи для коррекции ошибок в передаче данных. Они имеют более разреженную проверочную матрицу (что и обеспечивает их "низкую плотность"). Эта разреженность матрицы позволяет использовать более быстрые алгоритмы декодирования, чем для более плотных матриц. Проверочной матрице соответствует граф Тоннера, в котором для представления столбцов проверочной матрицы определенным образом используются битовые и проверочные узлы. Все это позволяет практически вплотную приблизиться к пропускной способности канала при относительно небольшой сложности реализации. Эти коды используются в таких стандартах связи, как DVB-S2, 802.11n, 802.16e.

Кодирование Требушета (Trellis Coding) - это метод кодирования, который использует комбинацию кодирования и модуляции для обнаружения и исправления ошибок. Он использует специальные алгоритмы для определения наилучшего пути передачи данных. Однако он сложен для реализации на аппаратуре.

Код SMPTE, или двухфазный код со скачком фазы при передаче нуля, способен к самосинхронизации. SMPTE - это аббревиатура от Society of Motion Picture and Television Engineers, или Общество инженеров кино и телевидения. Это международная группа профессионалов, которые занимаются разработкой стандартов для телевизионной и киноиндустрии. Код SMPTE является одним из стандартов, который был разработан инженерами SMPTE. Этот код используется для временной синхронизации между аудио- и видеоданными в производстве телепередач и фильмов. Он обеспечивает точную и надежную временную синхронизацию между различными аудио- и видеоданными, которые могут быть произведены на разных устройствах. Код SMPTE состоит из 80-битного кодового слова, которое включает в себя информацию о временной метке, состоящей из количества часов, минут, секунд и кадров. Код SMPTE может быть записан на ленту или отправлен по цифровому каналу, и он может быть считан и использован для временной синхронизации между различными устройствами.

Код NRZ (Non-Return-to-Zero) используется в цифровой передаче данных для однократного отображения каждого бита информации в виде положительного или отрицательного уровня сигнала. Это означает, что положительный уровень сигнала соответствует одному уровню бита (обычно "1"), а отрицательный уровень соответствует другому уровню бита (обычно "0"). Одним из главных преимуществ кода NRZ является его простота и простота в реализации. К недостаткам данного метода можно отнести его чувствительность к ошибкам и потере синхронизации в случае передачи длинной последовательности нулей или единиц, низкочастотную составляющую. Код NRZ может использоваться для передачи данных на различных каналах связи, в том числе на проводных и беспроводных каналах. Он широко применяется в сетевых технологиях, таких как Ethernet, в которых используется ряд различных вариантов кодирования NRZ, таких как NRZ-L (NRZ-Level) и NRZI (NRZ-Inverted). В целом, код NRZ является простым и надежным методом передачи данных, который широко применяется в различных областях, включая сетевые технологии и цифровое телевидение [2].

Манчестерское кодирование - это метод кодирования данных, который используется в цифровой передаче информации, для того чтобы увеличить надежность и эффективность передачи данных. Он получил свое название благодаря тому, что был разработан в Манчестерском университете в Великобритании в 1949 году. Основная идея манчестерского кодирования заключается в том, чтобы преобразовать бинарный сигнал (0 или 1) в последовательность смены уровней сигнала в соответствии с определенными правилами. В манчестерском кодировании каждый бит кодируется в виде перехода сигнала с одного уровня на другой. Если бит имеет значение "1", он представлен как передний фронт сигнала, в противном случае (если бит имеет значение "0") - задний фронт сигнала. Таким образом, частота переходов сигнала удваивается. Манчестерское кодирование широко используется в современных технологиях связи, в том числе в технологиях Ethernet, Zigbee и Bluetooth. Он обладает самоснихронизацией и не имеет постоянной составляющей.

Биполярный код AMI, особенностью кодирования информации этим кодом является то, что цифровой ноль в этом коде представлен нулевым напряжением, а цифровая единица представлена другими значениями, отличными от нуля. За счет этого код имеет хорошую синхронизацию, а также довольно прост в реализации; одним из недостатков является низкая скорость передачи данных. Этот код используется в телефонной связи. Улучшенной версией кода AMI является код HDB3, который отличается от AMI тем, что вместо одного используются четыре значения для представления цифрового нуля или единицы. Этот код также используется в телефонии.

MLT-3 (Multi-Level Transmission 3) - это метод кодирования, который используется в цифровой передаче данных для преобразования цифровых данных в сигнал, который может быть передан по проводам. Преимуществом MLT-3 является его способность сократить количество ошибок в передаче данных. Вместо использования простых цифровых уровней (0 или 1), этот метод кодирования использует три уровня: положительный, нулевой и отрицательный уровни. Циклически переключения уровни напряжения, единица обозначается переходом с одного уровня сигнала на другой. Иначе, путем комбинирования этих уровней различными способами, MLT-3 может представлять два бита информации за один знак. MLT-3 широко используется в сетевых технологиях, таких как Fast Ethernet, для кодирования данных, передаваемых по витой паре. Этот метод кодирования также используется в цифровых телефонных системах и других типах цифровых коммуникационных систем [2].

Основная идея сверточных кодов заключается в том, что каждый передаваемый бит данных кодируется не только самостоятельно, но и с использованием предыдущих битов. Это позволяет добавлять избыточность для определения и исправления ошибок. Сверточные коды используются во многих сферах, включая цифровое телевидение, радио и мобильную связь, беспроводную связь, спутниковую связь, компьютерные сети и многое другое. Они позволяют увеличить скорость передачи данных и повысить надежность передачи, обеспечивая защиту от ошибок. Существует много различных вариантов сверточных кодов, каждый с различными свойствами и применениями [4].

Свёрточные коды с использованием декодера Витерби оптимальны и достаточно просты в реализации для коротких свёрточных кодов. Алгоритм Витерби является одним из методов максимального правдоподобия и работает на основе вычисления метрики состояний при декодировании. Он позволяет обработать и выделить исправленные биты из зашумленных данных при передаче. Одним из главных недостатков кодов Витерби является большая вычислительная сложность декодирования. Витерби-декодер требует вычисления большого количества метрик состояний и решения задачи нахождения наиболее вероятной последовательности кодовых символов. Этот тип кодирования используется в беспроводных сетях связи дальнего космоса IEEE802.11, IEEE802.16 CCSDS, спутниковой связи TIA-1008 и т. д.

Свёрточные коды, использующие последовательный декодер, этот метод кодирования с исправлением ошибок применяется к свёрточным кодам с большой конструктивной длиной. Последовательный декодер принимает решение на основе предыдущих принятых символов, постепенно уточняя свое решение. Такой подход уменьшает число ошибок при передаче данных. Однако, последовательный декодер может приводить к задержке при передаче данных, поскольку он требует дополнительных вычислительных ресурсов для анализа предыдущих символов и принятия решения. Кроме того, он может быть более сложным для реализации, чем декодеры, работающие за один шаг. В частности, последовательное декодирование используется в стандарте TIA-10008.

Каскадный код, или составной код, представляет собой цепочку из нескольких кодовых элементов, причем выход одного элемента является входом для следующего элемента. Каскадный код может содержать элементы с различными длинами, большим числом уровней, различными генераторными полиномами и модификациями. Они используются в различных областях, таких как цифровая связь, радио и телевидение, мобильная связь, беспроводная связь и т.д. Каскадные коды обеспечивают высокую скорость передачи данных и повышенную надежность передачи, что является очень важным фактором в современных цифровых коммуникационных системах.

Турбокоды образуются каскадированием двух или более составляющих кодов. Турбокоды имеют высокую корректирующую способность благодаря применению технологии турбо-декодирования, которая использует итерации для поиска наилучшей последовательности битов. Это позволяет корректировать ошибки, которые могут возникать в процессе передачи данных. Турбокоды широко применяются в беспроводных сетях, спутниковой связи и некоторых системах цифрового телевидения. Они также успешно используются при передаче данных в космических программных проектах. Турбокоды можно разделить на два типа: свёрточные и параллельные.

Новые подходы в помехоустойчивом кодировании, эффективные коды и важные области использования

Среди перспективных подходов к помехоустойчивости можно выделить:

стенографический подход, при котором информация помещается в больший и более устойчивый к помехам контейнер;
вариации кодов повторения-накопления для определённых условий;
проверка блоков с помощью хэш-сумм;
коды Фонтана-Фили, использующие случайные символы для построения кодов;
канальные коды для специфических условий.

Сравнивая коды, можно выделить [5]:

наилучшие пропускные характеристики демонстрируют турбокоды TPC, коды LDPC и МПДСОК, что обуславливает их широкое использование во многих стандартах связи;
менее затратными в по количеству итераций являются такие коды, как коды БЧХ и Рида-Соломона, однако имеют неудовлетворительную пропускную способность;
новые коды, такие как стеганографический алгоритм и алгоритм Кловкого-Николаева, показывают среднюю производительность по пропускной способности, однако этого недостаточно, кроме того их техническая реализация в настоящее время достаточно сложна и нуждается в доработке;
Наилучшие показатели по пропускной способности по сравнению с кодами Галагера демонстрируют коды с повторением-накоплением и их модернизированная версия IRA, однако имеют сложную структуру.

Одна из ответственных областей применения помехоустойчивого кодирования – это медицина. В медицине коды с исправлением ошибок используются для повышения надежности передачи и обработки данных. Одним из распространенных применений является обработка медицинских изображений, где высокое разрешение и точность изображений имеют решающее значение для точной диагностики и планирования лечения. В ситуациях, когда медицинские изображения должны передаваться по шумному каналу, например, по беспроводной связи в больнице или в удаленном месте, могут применяться коды с исправлением ошибок для защиты данных от искажения и обеспечения надежности, повышения точности диагностики и результатов лечения.

Коды с исправлением ошибок также можно использовать в медицинских датчиках мониторинга, где для лечения пациентов требуется точный и надежный сбор данных. Например, беспроводные датчики, которые передают медицинскому персоналу показатели жизнедеятельности, такие как частота сердечных сокращений и артериальное давление, могут подвергаться помехам от других источников в окружающей среде, что приводит к ошибкам при передаче данных. Использование кодов с исправлением ошибок может помочь предотвратить эти ошибки и обеспечить точное наблюдение за пациентами в критических ситуациях. Ещё одно неочевидное применение – импланты, в том числе не подключаемые напрямую к нервной системе. В целом, использование кодов с исправлением ошибок в медицине может помочь улучшить результаты лечения пациентов за счет повышения надежности передачи и обработки данных.

Выводы

В заключение можно отметить, что помехоустойчивое кодирование играет важную роль во многих областях. Несмотря на то, что существует множество различных подходов к помехоустойчивому кодированию, каждый из них имеет свои преимущества и недостатки в зависимости от конкретных условий передачи данных. Однако, все перечисленные подходы, такие как коды Фонтана-Фили, коды LDPC, коды Турбо и коды сверточного кодирования, обеспечивают высокую помехоустойчивость и могут быть эффективно применены в различных системах передачи данных. Более того, с развитием технологий и повышением требований к защите данных можно ожидать появления новых методов и подходов к помехоустойчивому кодированию в будущем.

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

Головин П. Б. Помехоустойчивое кодирование / П. Ю. Головин // Мировая наука. - 2017. - № 9(9) 2017. - С. 176-181.
Королёв А. И. Коды и устройства помехоустойчивого кодирования информации / А. И. Королёв - Минск, 2002. - 286 с.
Кузьмин О. В. Коды Боуза – Чоудхури – Хоквингема в системах обнаружения и исправления ошибок при передаче данных / О. В. Кузьмин, В. И. Дружинин // Современные технологии. Системный анализ. Моделирование. - 2013 - № 3(39). - С. 23-29.
Никитин Г. И. Свёрточные коды / Г. И. Никитин - Санкт-Петербург : Санкт-Петербургский Государственный Университет аэрокосмического приборостроения, 2001. - 79 с.
Костюков А. С. Помехоустойчивое кодирование в современных форматах связи / А. С. Костюков, А.В. Башкиров, Л.Н. Никитин, И.С. Бобылкин, О.Ю. Макаров // Вестник Воронежского Государственного Технического Университета. - 2019. - Т.15, № 2. - С. 132-138.

Интересная статья? Поделись ей с другими: