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

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

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

Не рассматривая методы экономногокодирования, укажем только основные свойства дискретного сигнала, в котором полностью устраненаизбыточность, — это равная вероятность и независимость появления символов в последовательности. В этомслучае среднее количество информации на символ равно log2 m.Примером экономного кодирования является передача речевого сигнала по цифровым каналам. Еслиориентироваться только на смысловое (информационное) содержание, то можно перейти к передаче текста соскоростью 5…10 букв в секунду.

С учетом объема алфавита в двоичном канале это потребует скоростьпередачи 25…50 бит/с. Если устранить избыточность, связанную с неодинаковой вероятностью их появленияи их корреляцией в тексте, то, как показывают расчеты, скорость передачи может быть уменьшена до 10 бит/с.Если передавать речь в цифровой форме, используя аналого-цифровое преобразование, ориентируясь толькона ширину спектра и динамический диапазон, то скорость потока двоичных символов составит 32…64кбит/с.

Такая колоссальная избыточность привела к необходимости разработки специальных кодековречевых сигналов, называемых вокодерами, которые нашли применение при передаче речи в цифровойформе по радиоканалам. Например, в сотовых системах мобильной связи стандарта GSM скоростьпередачи составляет 8,5 кбит/с, причем сохраняются не только смысловое содержание, но и индивидуальныеособенности говорящего.

Подобные кодеки находят применение и при передаче подвижных и неподвижныхизображений в цифровых телевизионных каналах.При помехоустойчивом кодировании в поток передаваемых символов вводятся дополнительные(избыточные) символы для исправления возникающих на приемной стороне ошибок.

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

Допустим, что источник обладаетмаксимальной производительностью. Тогда обязательным условием внесения избыточности являетсяувеличение числа переданных посылок за единицу времени по сравнению с их числом, поступающим отисточника. Как вносятся избыточные символы, определяет тип кода. Наиболее просто предположить, чтогруппе из k символов источника ставится в соответствие n символов, передаваемых по каналу. Такой кодназывается блочным и записывается условно как (n, k)-код. Возможны непрерывные коды, которыехарактеризуются тем, что операции кодирования и декодирования производятся над непрерывнойпоследовательностью символов без разбиения ее на блоки.Рассмотрим принципы помехоустойчивого кодирования на примере блочного двоичного кода какнаиболее простого [11, 132].

Если к символам источника добавляются избыточные символы, то код называютсистематическим. Если группе информационных символов ставится в соответствие новая группа символов,передаваемая по каналу, в которой информационных символов в явном виде нет, то код называетсянеразделимым. Теперь ответим на основной вопрос: как строить кодек, чтобы при фиксированнойизбыточности  = r/n, где r — число проверочных символов для разделимого кода, достоверность передачибыла бы максимальной? При передаче безызбыточным примитивным кодом с числом разрядов k в каждомслове все Nр = 2k комбинаций являются разрешенными и ошибка хотя бы в одном символе приводит к тому,что одна разрешенная комбинация переходит в другую и происходит ошибка в приеме сообщения.Введение избыточных символов приводит к тому, что полное число комбинаций увеличивается истановится равным N = 2n, причем часть из них N – Nр являются запрещенными и могут возникать толькотогда, когда в канале происходят ошибки.

Этот факт положен в основу обнаружения и исправления ошибок.Введем понятие кодового расстояния. Предварительно отметим, что для оценки отличия одной кодовойкомбинации от другой можно использовать расстояние Хэмминга d(Bi, Bj), определяемое числом разрядов, вкоторых одна кодовая комбинация отличается от другой.

Для двоичного кодаnd  Bi , B j    bik  b jk ,k 1гдеbikиbjk—k-eсимволыкодовыхкомбинацийBiиBjсоответственно; — символ суммирования по модулю 2. Наименьшее расстояние Хэмминга для данного кода называетсякодовым расстоянием. В дальнейшем его будем обозначать через d.При независимых ошибках в канале корректирующую способность кода удается выразить через кодовоерасстояние.

Пусть имеется код с d = 1. Учитывая, что искажение одного символа изменяет расстояниеХэмминга на одну единицу, при применении кода с d = 1 обнаруживаются не все одиночные ошибки. Длятого чтобы код мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние,равное двум. Рассуждая аналогичным образом, получаем, что для обнаружения всех ошибок кратности lтребуется код сd ≥ l + 1.Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, чем дляих обнаружения. Если кратность исправляемых ошибок равна l, то кодовое расстояние должноудовлетворять условиюd ≥ 2l + 1.Очевидно, что кодовое расстояние между разрешенными комбинациями можно сделать тем больше, чембольше избыточность. Однако при этом уменьшается длительность посылок и возрастает вероятность ошибокпри их приеме.

Поэтому вводят понятие эффективности избыточного кодирования как отношениевероятностей ошибочного приема кодовой комбинации из k информационных символов при передаче ихпримитивным и избыточным кодами:  P (k ) / P (n, k ).Если код примитивный, то ошибка возникает, когда хотя бы в одном символе при приеме произошлаошибка. Вероятность такого события равнаP (k )  1  (1  Pош.п )k  kPош.п ,где Pош.п — вероятность ошибки в приеме одного символа при передаче сообщения примитивным кодом.Для избыточного кода ошибка в приеме кодовой комбинации будет иметь место тогда, когда числоошибок превысит исправляющую способность кода tи и ее вероятностьP ( n, k ) niCni Pош.и(1  Pош.и ) n i ,i tи 1где Pош.и — вероятность ошибки в приеме одного символа при передаче избыточным кодом.Различие в Pош.п и Pош.и определяется уменьшением длительности посылки при передаче избыточнымкодом в n/k раз.

Величины Pош.п и Pош.и могут быть найдены, если известен вид модуляции и демодуляции,отношение Рс/No и длительность посылок источника.Таким образом, задача построения кода с заданной корректирующей способностью сводится кобеспечению необходимого кодового расстояния при введении избыточности.