Декодирование стирания



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

Ключевые слова : стирание, двоичное декодирование стирания.

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

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

Предположим, что последовательность кодовых слов записана в строки матрицы, как показано в таблице 1.

Таблица 1

Затем столбцы считываются, давая последовательность данных

Предположим, что теперь они отправляются в виде последовательности из n пакетов данных, каждый из которых имеет длину по каналу, который подвержен потере пакетов, но где потеря пакета известна получателю (например, интернет, использующий протокол, не гарантирующий доставку, такой как UDP). На приемнике пакеты записываются в матрицу в порядке столбцов — оставляя пустой столбец, соответствующий потерянным пакетам, — а затем считываются в порядке строк. Предположим, что в этой схеме один из пакетов, скажем, третий, потерян при передаче. Тогда чередующиеся данные в приемнике, будут записаны как показано в таблице 2.

Таблица 2

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

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

Рассмотрим возможность стирания для кода с расстоянием . Один стертый символ, удаленный из кода (без дополнительных ошибок), оставляет код с минимальным расстоянием не менее . Таким образом, стертые символы могут быть «заполнены» при условии, что . Например, код Хэмминга с может исправить до 2 стираний.

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

Таблица 3

Вставка: Протокол UDP

UDP — протокол пользовательских дейтаграмм — является одним из протоколов в наборе протоколов TCP/IP. Самый распространенный протокол, TCP, обеспечивает доставку пакетов, подтверждая каждый успешно полученный пакет и повторно передавая пакеты, которые запутались или потерялись при передаче. UDP, с другой стороны, является открытым протоколом, который не гарантирует доставку пакетов. По ряду причин он имеет меньшую задержку доставки и, как следствие, представляет интерес для коммуникационных приложений, работающих в режиме, близком к реальному времени. Разработчик приложения должен бороться с потерянными пакетами, используя, например, методы коррекции ошибок.

Если есть

стирания и ошибки, они могут быть исправлены при условии, что

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

Теперь мы рассмотрим, как с помощью заданного алгоритма декодирования одновременно заполнить f пробелов и исправить e ошибок в двоичном коде. В этом случае для каждой ошибки достаточно определить, каким должно быть пропущенное значение — единицей или нулем. Алгоритм декодирования ошибок для этого случая может быть описан следующим образом:

1. Поставьте нули во все стертые координаты и декодируйте, используя обычный декодер для данного кода. Назовем полученное кодовое слово .
2. Поставьте единицы во все стертые координаты и декодируйте, используя обычный декодер для данного кода. Назовем полученное кодовое слово .
3. Найдите, какое из и ближе всего к r. Это код вывода.

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

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

и

, поэтому одно из двух декодирований должно быть правильным.

Декодирование стирания для недвоичных кодов зависит от конкретной структуры кода (например, декодирование кодов Рида-Соломона).

Литература:

1. Moon, Todd K. (2005). Error Correction Coding.