Принципы построения кодов, исправляющих ошибки.

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

Дано множество W. Задано свойство S, которым обладает часть элементов этого множества W_s. Под вероятностью того, что объект обладает свойством s будем понимать отношение |W_s||/|W| или его асимптотику.

Итак, у нас есть двоичный симметричный канал. (См. определение выше). Он характеризуется единственным параметром  p – вероятностью ошибки при передаче символа.

Опредиление. Пропускная способность канала – это число C (p) = 1 – H (p), где  - энтропия канала.

Как раз для случая p=1/2 энтропия равна единице, что соответствует полной неопределенности (абсолютному беспорядку), а пропускная способность канала нулевая.

Если p>1/2, то поменяем 0 и 1 местами в определении конала. Поэтому всюду в дальнейшем считаем, что p<1/2.

В качестве защиты от ошибок мы используем некоторую конструкцию. Это (n,M,d) – код. Как мы видим, у него три параметра. Пусть t - максимальный радиус шаров с центрами в кодовых точках таких, что они не пересекаются. Очевидно, что t выражается через d и наоборот.

Схемы кодирования могут быть самые разные. Рассмотрим одну из самых известных. (Она считается наиболее естественной и соответствующей практическим задачам.)

В ее основе лежит два принципа:

1. Принцип наибольшего правдоподобия. Этот принцип вытекает из очевидного соотношения

pⁿ < p^{n- 1}(1 -p) < p^{n- 2}(1 -p)² < … < (1 -p) ⁿ               

и говорит о том, что вероятность k ошибок в кодовом слове меньше, чем вероятность s ошибок для всех s>k.

1. Принцип избыточности.

Мы в нашем рассмотрении не затрагиваем протокольные вопросы, а ограничиваемся чисто алгоритмическими, т.е кодер и декодер в процессе передачи не ведут между собой никакого диалога (например, не могут перезапрашивать один раз уже переданные символы и т.п.) В этом случае алгоритм декодирования по принятой информации должен исправлять ошибки, которые возникли при передаче. Но, если кодер просто передает в канал информацию, подлежащую передаче, ничего к ней не добавляя, то у декодера нет никакой возможности исправить ошибки. Таким образом, принцип избыточности заключается в том, что для защиты передаваемой информации используется дополнительная информация. И тут возникает уже знакомая конструкция: нужно уметь отделять кодовые точки друг от руга определенным расстоянием. А это и будут (n,M,d)- коды.

Мы считаем, что все кодовые слова имеют одинаковую длину. (Это вектора пространства Bⁿ). Информация, подлежащая передаче может быть представлена в виде последовательности двоичных слов длины k (k<n). Кодер берет эти слова и преобразует в слова длины n. Здесь и возникает избыточность за счет (n-k) символов.

Если кодер просто добавляет к словам, подлежащим передаче эти (n-k) символов, то они называются проверочными символами, а исходные k символов – информационными.

Так построенный код называется систематическим кодом.

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

Проиллюстрируем сказанное.

Пусть, например, информация, подлежащая передаче, - это битовый поток, подающийся на вход кодера. Кодер нарезает ее в виде последовательности слов длины k. Таким образом можно считать, что передаче в канал подлежат все возможные слова длины k, т.е. вектора пространства B^k, таких словам M=2 ^k . (Случай 2 ^k-1 <M<2 ^k  –можно “технически свести» к рассматриваемому, поэтому наше предположение не ограничивает общности). Кодер преобразует вектора пространства B^k в вектора пространства Bⁿ. Таким образом реализуется принцип избыточности.

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

Обозначим эти слова через α¹,α²,…,α^M, а сопоставленные им вектора пространства Bⁿ (кодовые вектора) через x¹,x²,…,x^M.

Определение. Отображение φ, ставящее в соответствие αⁱ, i=1,…,M, вектор из Bⁿ и называется кодированием или просто кодом.

Из контекста всегда видно, что понимается под кодом: множество или отображение.

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

К нему предъявляются естественные требования дешифруемости и неизбыточности. То есть, если φ(αⁱ)=xⁱ, то кодер и декодер всегда «знают» (умеют вычислять), что       Но не это является основной проблемой при построении кодов, исправляющих ошибки. Дело в том, что переданное кодером в канал слово xⁱ в результате искажения может превратиться в какое-то слово Yⁱ (это тоже вектор из Bⁿ).

Основная задача кодирования. Отображение φ должно быть построено таким образом, чтобы можно было сконструировать алгоритм преобразования Yⁱ в αⁱ.  И это должно приводить к исправлению ошибок. Поэтому под декодированием (дешифруемостью) в коде, исправляющем ошибки понимается именно данное преобразование. (Обозначим это преобразование через ψ).

Построение каждого такого кода – это отдельное достижение в математике, поэтому принято кодам давать имена их создателей: код Хэмминга, код Боуза- Чаудхури-Хоквингема (БЧХ-код), коды Гоппа и т.д.

Интуитивно ясно, что чем хуже канал (больше вероятность ошибки), тем большая требуется избыточность. Поэтому каждый код может исправить только ограниченное количество ошибок в слове определенной длины. Например, если код может исправлять не более двух ошибок в слове длины n=10, то при передаче информации по каналу с p=1/3 этот код не сможет всегда исправлять все ошибки (ниже будет показано, что среднее количество ошибок в слове в таком канале равно 3). Если же этот код используется в канале с p=1/1000, то такой код свои задачи выполнит (с «вероятностью, близкой к единице»). Таким образом, коды подбираются в соответствии с характеристиками канала.

Пример.

Мажоритарное кодирование – схема, где передатчик просто повторяет слово, подлежащее передаче в канал, p=2 q+1 >1  раз. Приемник – декодер берет экземпляров полученного слова и каждую позицию в слове дешифрует в тот символ (0 или 1). Который встречается в большей части экземпляров.

Например, двухбитовой слово a = 11 → 11|10|11|00|11|11|11 – передали по каналу 7 раз.

На первой позиции 6 раз «1» и 1 раз «0»   a = 1х.

На второй позиции 5 раз «1» и 2 раза «0»   a = 11.

Избыточность этой схемы очень большая.

Предыдущая45678910111213141516171819Следующая

Поделиться:

Воспользуйтесь поиском по сайту: