Глава 8. КОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ

8.1. ОСОБЕННОСТИ ПРИМЕНЕНИЯ КОРРЕКТИРУЮЩЕГО КОДИРОВАНИЯ

При корректирующем кодировании для повышения верности передачи информации воздействуют как на способ передачи, так и на способ приема. Применяют его в тех случаях, когда возможности других способов повышения верности исчерпаны. Это обусловлено усложнением систем связи при введении корректирующих устройств, ростом материальных затрат, а в ряде случаев и снижением надежности аппаратуры. Развитие корректирующего кодирования в значительной мере связано с внедрением автоматических и автоматизированных систем обработки информации, построенных на ЦВМ. Эти системы обычно являются важной составной частью иерархических систем более высокого ранга, таких, как автоматизированные системы управления воздушным движением, системы бронирования и продажи билетов, системы управления предприятиями и технологическими процессами. Для нормальной работы автоматизированных систем управления необходим обмен цифровой информацией между различными ЦВМ по телефонным и телеграфным каналам (передача данных). Допустимая вероятность ошибки при передаче одного бита информации в современных автоматизированных системах не должна превышать что на 3—4 порядка меньше той, которая наблюдается в реальных каналах связи. Корректирующее кодирование направлено на согласование высоких требований к верности передачи данных и низкого качества реальных каналов, плохо приспособленных для передачи данных. Применению кодирования благоприятствует то, что большинство алгоритмов кодирования и декодирования может быть реализовано не аппаратурным, а программным способом в ЦВМ.

Возможности эффективного использования реальных каналов далеко не исчерпаны. При отношениях сигнал/шум 20-30 дБ, которые имеют место в каналах, теоретическая пропускная способность каналов при сколь угодно малой вероятности ошибок может составлять 6—10 бит/с на 1 Гц полосы канала. Следовательно, теоретическая пропускная способность телеграфного канала составляет примерно 900-1200 бит/с, телефонного - 20- 30 тыс. бит/с, телевизионного — 30—50 млн. бит/с. Существующие системы позволяют получить скорость передачи информации всего

лишь 1—2 бит/с на 1 Гц полосы канала, вероятность ошибки при передаче одного бита и выше, если не используется корректирующее кодирование.

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

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

Корректирующая способность кода определяется минимальным кодовым расстоянием между разрешенными кодовыми комбинациями (см. § 1.6). Максимальную кратность обнаруживаемых ошибок определяют из следующих соображений. Если расстояние, измеренное между принятой комбинацией и какой-либо разрешенной, оказывается меньше это позволяет рассматривать принятую комбинацию как запрещенную, т. е. обнаружить ошибку. Ближайшее целое число, меньшее есть Поэтому кратность обнаруживаемых ошибок изменяется от 1 до максимальная кратность

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

другой разрешенной. Это может случиться тогда, когда сочетание ошибок изменит более половины позиций, в которых переданная комбинация отличается от какой-либо другой разрешенной. Поэтому код с расстоянием исправляет все сочетания ошибок кратности

Максимальная кратность полностью исправимых ошибок

Для обнаружения ошибок и исправления ошибок должно выполняться неравенство

Увеличение приводит к росту избыточности кода

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

Таблица 5 (см. скан)

Если ошибки независимы, то вероятность появления ошибок на выходе декодера определяют как вероятность того, что не

исправлены ошибки кратности и более (см. п. 4.3.4):

В реальных каналах имеет место группирование ошибок, поэтому для них оценка этой вероятности [10]

где а — показатель группирования ошибок в канале, который оценивают экспериментально.

В таблице 5 показаны вероятности ошибок и показатели группирования для основных видов реальных каналов

Рис. 8.1. Зависимость вероятностей некорректируемых ошибок от

Формула (8.6) справедлива при что обычно соблюдается. Для сравнения данных, получаемых по формулам (8.5), (8.6), на рис. 8.1 [10] показаны зависимости (штриховые линии) и при различных для радиотелеграфного канала с параметрами Бод. Анализ графиков показывает, что формула (8.5) дает заниженные значения вероятностей появления некорректируемых ошибок из-за того, что не учитывает групповой характер ошибок. О порядке расхождения можно судить, например, по тому, что при формула (8.5) дает тогда как в реальном канале

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

Для коррекции групповых ошибок требуется примерно в 2—3 раза меньшая избыточность. Аналогичные (8.7) соотношения более сложного характера получены с учетом группового характера ошибок и надежности корректирующих устройств. Существует информационный предел избыточности, который существенно ниже. Это объясняется тем, что избыточность вводится для наихудшего случая появления ошибок, а реально не все комбинации имеют ошибки.

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

Задачи корректирующего кодирования обычно решают при следующих предположениях: избыточность эффективного кода равна нулю, кодирование выполняется двоичными сигналами, характеристики дискретного двоичного канала известны, канал является симметричным и в общем случае с памятью (см. § 4.3).

Контрольные вопросы

(см. скан)