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

В любом коммуникационном цифровом канале существует отличная от нуля вероятность искажения битов. Например, типичный уровень битовых ошибок, вызываемых особенностями физической среды передачи, колеблется от 10^-11 (волоконно-оптический кабель) до 10^-3 (радиоканал). Приемлемость того или иного уровня ошибок, равно как и степень надежности их обнаружения, определяются требованиями приложения. Так, аудио- и видеоприложения весьма терпимы к единичным и даже групповым битовым ошибкам, в то время, как системы электронных платежей (банкомат, например) и служба передачи файлов требуют абсолютной безошибочности.

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

Информационный блок данных, размером k бит, используется как аргумент некоторой функции F₁. Включение значения этой функции в передаваемый блок данных приводит к тому, что их совокупность удовлетворяет вполне определенному условию. Конечно, при этом размер протокольного блока увеличивается до n бит, n > k. На принятом массиве из n бит вычисляется проверочная функция F₂ и полученное значение сравнивается с множеством ее допустимых значений. Результат такого сравнения позволяет, с определенной степенью достоверности, зафиксировать наличие, или отсутствие ошибок в принятом блоке данных.

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

Очевидно, что k двоичных чисел информационного потока могут представлять 2^k информационных блоков (информационных слов) и все они – равновероятны. После выполнения операции помехоустойчивого кодирования число битов в кодовом слове увеличивается до n. Кодер должен быть построен так, чтобы не все 2ⁿ кодовых блоков (слов) были возможны, т.е. должны существовать «запрещенные» n- битовые кодовые слова, вероятность появления которых при кодировании любых информационных слов равна нулю. Зная алгоритм кодирования, всегда можно составить перечень таких «запрещенных» кодовых слов. Тогда, появление их на приемной стороне канала будет свидетельствовать о наличии ошибки в принятом блоке.

Вместе с тем, ошибки в канале могут так преобразовать исходное кодовое слово, что оно превратится в другое допустимое слово. Каждый метод кодирования характеризуется минимальным кодовым расстоянием, измеряемымминимальным числом битов, отличающих одно допустимое кодовое слово от другого. Пусть эта величина равна d. Тогда ошибка на приемном конце канала может быть обнаружена, если в принятом кодовом слове окажутся инвертированными не более (d-1) бит. Более того, используя критерий минимума расстояния между принятым кодовым словом и множеством допустимых слов, можно исправлять ошибочные кодовые слова. Последнее будет иметь успех лишь при искажении менее d/2 бит. Например, пусть допустимыми кодовыми словами являются:

00000 00000, 00000 11111, 11111 00000, 11111 11111.

В этом случае минимальное кодовое расстояние d=5. Кодовые слова, с искаженными двумя битами, могут быть верно интерпретированы по критерию близости их к допустимым. Пусть передается слово 00000 11111, а принимается A =01000 11011. Расстояния между ним и допустимыми кодовыми словами, измеренные числом единичных битов в суммах этих слов по модулю 2 без переноса, будут равны:

,

,

,

.

Таким образом, принятое кодовое слово должно быть интерпретировано как 00000 11111, и ошибка исправлена.

Вместе с тем, наличие в слове 00000 11111 трех, т.е. более , ошибок (принимается, например, слово А =00000 11000) даст:

,

,

,

.

Такое слово будет ошибочно интерпретировано как 00000 00000.

Далее будут рассмотрены несколько методов обнаружения ошибок и дана оценка их эффективности.