Теория кодирования

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

История

Зарождение теории кодирования связано с работами американского математика и инженера Клода Шеннона, который в 1948 году опубликовал статью «Математическая теория связи». В этой работе были введены фундаментальные понятия: энтропия источника, пропускная способность канала, а также сформулированы теоремы Шеннона для кодирования источника и канала. Эти теоремы установили теоретические пределы сжатия данных и надёжной передачи информации при наличии помех.

В 1949 году Роберт Фано и Марсель Гольдман разработали первые эффективные алгоритмы кодирования. В 1950-х годах Ричард Хэмминг создал первые коды, исправляющие ошибки (коды Хэмминга), что положило начало помехоустойчивому кодированию. В 1960-х годах Ирвинг Рид и Густав Соломон предложили коды Рида — Соломона, ставшие стандартом для систем хранения данных и спутниковой связи. В 1970-х годах была разработана теория циклических кодов и свёрточных кодов, а в 1990-х годах — турбо-коды и коды с низкой плотностью проверок на чётность (LDPC), приближающиеся к пределу Шеннона.

Основные понятия

Код и кодирование

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

Длина кодового слова

Каждому сообщению сопоставляется кодовое слово — конечная последовательность символов. Длина кодового слова (количество символов) может быть фиксированной (равномерное кодирование) или переменной (неравномерное кодирование).

Префиксное свойство

Код называется префиксным (или мгновенным), если ни одно кодовое слово не является началом (префиксом) другого кодового слова. Это свойство гарантирует однозначное декодирование без использования разделителей.

Энтропия и избыточность

Энтропия источника (по Шеннону) — мера неопределённости информации, выражаемая в битах на символ. Чем выше энтропия, тем больше информации содержит каждый символ. Избыточность — разность между средней длиной кодового слова и энтропией источника. Кодирование без избыточности невозможно, если требуется помехоустойчивость.

Классификация кодов

По назначению

1. Коды сжатия данных (кодирование источника) — уменьшают объём информации за счёт устранения избыточности. Примеры: код Хаффмана, арифметическое кодирование, LZW.
2. Помехоустойчивые коды (канальное кодирование) — вносят контролируемую избыточность для обнаружения и исправления ошибок. Примеры: коды Хэмминга, коды БЧХ, свёрточные коды.

По структуре

1. Блочные коды — исходные данные разбиваются на блоки фиксированной длины, каждый блок кодируется независимо. Примеры: коды Рида — Соломона, коды Голея.
2. Свёрточные коды — кодирование выполняется непрерывно, с учётом предыдущих символов. Используются в системах мобильной связи и спутниковой передачи.

По способу обнаружения ошибок

1. Коды с обнаружением ошибок — позволяют только выявить факт искажения (например, код с контролем чётности).
2. Коды с исправлением ошибок — позволяют восстановить исходное сообщение при ограниченном числе ошибок (например, коды Хэмминга).

По алфавиту

1. Двоичные коды — используют алфавит {0, 1}. Наиболее распространены в цифровых системах.
2. Небинарные коды — используют алфавит из более чем двух символов (например, коды Рида — Соломона над полем GF(256)).

Кодирование источника (сжатие данных)

Код Хаффмана

Разработан в 1952 году Дэвидом Хаффманом. Является оптимальным префиксным кодом для заданного распределения вероятностей символов. Алгоритм строит дерево кодирования: символы с большей вероятностью получают более короткие кодовые слова. Применяется в архиваторах (ZIP, RAR), форматах изображений (JPEG) и аудио (MP3).

Арифметическое кодирование

Более эффективный метод сжатия, не привязанный к отдельным символам. Весь поток данных кодируется одним дробным числом из интервала [0, 1). Используется в стандартах сжатия видео (H.264, H.265) и изображений (JPEG 2000).

LZW (Lempel-Ziv-Welch)

Словарный метод сжатия, основанный на построении динамического словаря повторяющихся последовательностей. Широко применяется в форматах GIF, TIFF и архиваторах.

Помехоустойчивое кодирование

Коды Хэмминга

Простейшие линейные блочные коды, способные исправлять одну ошибку и обнаруживать две. Параметры: (n, k) = (2^m - 1, 2^m - m - 1), где m — число проверочных бит. Например, код Хэмминга (7,4) добавляет 3 проверочных бита к 4 информационным.

Коды Рида — Соломона

Небинарные блочные коды, работающие над конечными полями. Способны исправлять пакеты ошибок (последовательности искажённых символов). Используются в компакт-дисках, QR-кодах, системах спутниковой связи (DVB-S).

Свёрточные коды

Кодирование реализуется с помощью регистров сдвига и сумматоров. Для декодирования применяется алгоритм Витерби, находящий наиболее вероятную последовательность состояний. Используются в стандартах GSM, Wi-Fi (802.11), Deep Space Network.

Турбо-коды

Изобретены в 1993 году. Представляют собой параллельное или последовательное соединение двух или более свёрточных кодов, разделённых перемежителем. Декодирование выполняется итеративно. Обеспечивают близкую к пределу Шеннона помехоустойчивость. Применяются в стандартах мобильной связи 3G/4G (UMTS, LTE).

LDPC-коды

Коды с низкой плотностью проверок на чётность, впервые предложенные Робертом Галлагером в 1963 году. Обладают разрежённой проверочной матрицей, что позволяет эффективно декодировать с помощью итеративных алгоритмов (например, алгоритм распространения доверия). Используются в стандартах Wi-Fi 6 (802.11ax), 5G NR, DVB-S2, Ethernet 10GBASE-T.

Применение

Теория кодирования лежит в основе современных цифровых технологий:

• Хранение данных: коды Рида — Соломона используются в CD, DVD, Blu-ray, RAID-системах (RAID 6).
• Передача данных: свёрточные и турбо-коды применяются в спутниковой, сотовой (GSM, 3G, 4G, 5G) и космической связи (NASA, ESA).
• Компьютерные сети: LDPC-коды в Ethernet, Wi-Fi, оптоволоконных линиях.
• Сжатие информации: код Хаффмана, арифметическое кодирование, LZW в архиваторах, мультимедийных форматах.
• Криптография: некоторые коды (например, коды Гоппы) используются в постквантовых криптосистемах (McEliece).
• Биоинформатика: кодирование генетической информации, анализ ДНК-последовательностей.

Интересные факты

• Коды Хэмминга были разработаны в 1950 году, когда Ричард Хэмминг работал в Bell Labs на релейном вычислителе. Ошибки в работе реле приводили к сбоям, и Хэмминг создал код, позволяющий автоматически исправлять одиночные ошибки.
• Коды Рида — Соломона используются в компакт-дисках с 1982 года. Благодаря этим кодам CD может воспроизводить музыку даже при наличии царапин и пыли.
• Турбо-коды, открытые в 1993 году, произвели революцию в помехоустойчивом кодировании, приблизившись к теоретическому пределу Шеннона. Их изобретатели (Клод Берру, Ален Главиё, Пьер Титимажма) получили за это премию Маркони.
• LDPC-коды, несмотря на открытие в 1963 году, не были востребованы до 1990-х из-за вычислительной сложности декодирования. С развитием микроэлектроники они стали одними из самых распространённых помехоустойчивых кодов.

Источники

• Шеннон К. Математическая теория связи // Работы по теории информации и кибернетике. — М.: ИЛ, 1963.
• Хэмминг Р. В. Коды, обнаруживающие и исправляющие ошибки // Теория кодирования. — М.: Мир, 1970.
• Галлагер Р. Коды с низкой плотностью проверок на чётность // Теория информации и кодирование. — М.: Мир, 1974.
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.
• Берру К., Главиё А., Титимажма П. Турбо-коды: новый класс помехоустойчивых кодов // IEEE Transactions on Information Theory. — 1996.
• Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988.