Применение помехоустойчивых кодов для повышения верности передачи данных связанно с решением задач кодирования и декодирования.
Задача кодирования заключается в получении при передаче для каждой k - элементной комбинации из множества qk соответствующего ей кодового слова длиною n из множества qn.
Задача декодирования состоит в получении k - элементной комбинации из принятого n - разрядного кодового слова при одновременном обнаружении или исправлении ошибок. [6]
Основные параметры помехоустойчивых кодов
Длина кода - n;
Длина информационной последовательности - k;
Длина проверочной последовательности - r=n-k;
Кодовое расстояние кода - d0;
Скорость кода - R=k/n;
Избыточность кода - Rв;
Вероятность обнаружения ошибки (искажения) - РОО;
Вероятность не обнаружения ошибки (искажения) - РНО.
Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) - это число позиций, в которых они отличаются друг от друга.
Кодовое расстояние кода - это наименьшее расстояние Хэмминга между различными парами кодовых слов.
Стиранием называется "потеря" значения передаваемого символа в некоторой позиции кодового слова, которая известна.
Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим.
Построение помехоустойчивых кодов в основном связано с добавлением к исходной комбинации (k-символов) контрольных (r-символов) Закодированная комбинация будет составлять n-символов. Эти коды часто называют (n,k) - коды.
k--число символов в исходной комбинации
r--число контрольных символов
Рассмотрим основные понятия помехоустойчивого кодирования. Двоичный (n,k)-код предполагает правило перехода от комбинации из k информационных символов, общее число которых 2k, к такому же числу кодовых комбинаций длиной n (причем n > k), общее число которых 2n , т.е. к введению избыточности (для систематических кодов избыточных символов). Для кода существует множество из 2k разрешенных кодовых комбинаций длиной n, каждая из которых соответствует одной из информационных комбинаций. Если сравнить пару кодовых комбинаций длиной n символов, то число двоичных символов в которых они не совпадают, называют расстоянием. Если попарно сравнить все кодовые комбинации, минимальное из полученных расстояний называют кодовым расстоянием d, которое описывает способность кода исправлять или обнаруживать искажения в канале кодовых комбинаций.
Декодирование кода может производиться либо в режиме обнаружения ошибки, либо в режиме исправления ошибок. Если полученная из канала кодовая комбинация является одной из разрешенных, то она считается принятой правильно, хотя на самом деле могла передаваться другая разрешенная комбинация. Если принятая комбинация не является одной из разрешенных комбинаций, то в режиме обнаружения ошибки фиксируется факт обнаружения ошибки, и кодовая комбинация, в общем случае, стирается, т.е. удаляется из дальнейшей обработки, а в режиме исправления ошибки предпринимается попытка исправить искажение (исправить ошибки).
Исправление ошибки выполняется по какому-то правилу или критерию выбора разрешенной комбинации, в которую преобразуется принятая искаженная комбинация (не равная передаваемой в канал связи). При декодировании двоичных алгебраических кодов используется принцип максимума правдоподобия, в основу которого положено предположение, что в канале связи вероятность ошибки большей кратности меньше вероятности меньшей кратности. Т. е. если в канале может исказиться один из символов кодовой комбинации (кратность ошибки t = 1 ), два символа ( t = 2), три символа (t = 3) и т.д., то справедливо для вероятностей искажения Р(t = 1) > Р(t = 2) > Р(t = 3) … Если такое предположение справедливо для используемого дискретного канала, то в декодере, который не знает, что было искажено в принятой кодовой комбинации, оправдано отождествить с передаваемой комбинацией ту из разрешенных комбинаций, которая ближе по расстоянию от комбинации, подлежащей исправлению. Самая близкая (отличающаяся в меньшем числе символов) разрешенная комбинация считается переданной и объявляется результатом исправления ошибки.
При декодировании по принципу максимума правдоподобия справедливо утверждение, что код с кодовым расстоянием d правильно исправляет число ошибок t =[(d-1)/2], где [a] - меньшее целое от а. В то же время ясно, что если реальное число искаженных символов в кодовом блоке превышает величину [(d-1)/2], то произойдет неверное исправление ошибки (ошибка декодирования с вероятностью Рош ). Таким образом, код правильно исправляет ошибки с кратностью не выше [(d-1)/2], при этом число искаженных символов в принимаемой информационной последовательности уменьшается, и вносит ошибки декодирования в результате исправления ошибок с кратностью, превышающей величину [(d-1)/2], когда число искажений в информационной последовательности увеличивается (остаются искажения, полученные в канале связи, и добавляется неверное исправление в декодере). Понятно, что если в канале связи число ошибок в кодовой последовательности может превышать величину [(d-1)/2] с достаточно большой вероятностью, то реализация режима исправления ошибок может быть бесполезной или даже вредной.
В реальном канале связи часто наблюдается группирование ошибок, когда искажается не один двоичный символ, а целый пакет, длина которого может превышать величину [(d-1)/2]. Это обстоятельство является одной из причин, ограничивающей широкое применение кодов с исправлением ошибок. Для широкого применения кодов с исправлением ошибок такой код в качестве одного из своих свойств должен обеспечивать гарантированную границу для вероятности ошибки декодирования в канале связи с произвольным распределением потока ошибок в канале связи.
Обычно оценка вероятности ошибки декодирования делается для q-ичного симметричного канала при вероятности искажения q-ичного символа Pq. В таком канале с вероятностыо 1 -- Pq q-ичный символ принимается верно, после его искажения с вероятностью Рq каждое значение q-ичного символа отличается от переданного и появляется на входе декодера с одинаковой вероятностью
Pq/(q-1).
В таком канале в зависимости от кратности ошибки t вероятность ошибки декодирования
Pош(t)=0 при t ? (dРС-1)/2 =tРС
Pош(t) ? (q-1) > ? CnS (q-1)S
при d - tРС ? t ? d-1
Pош(t) ? (q-1) > ? CnS (q-1)S при t ?d (1)
В канале, не являющемся q-ичным симметричным для кода РС, получены следующие оценки для t>d -- tPc
1/(q-1)i-2 + 1/(q-1)i при tРС =1
P (t) ? (2)
1/(q-1)i-2t -1/t! при tРС ? 2
При исправлении tРС ошибок в [9] предлагается оценка
(3)
То есть, если кратность ошибки t превосходит исправляющую способность кода tpc, то в канале, не являющемся q-ичным симметричным, вероятность ошибки декодирования не зависит от основания кода q при исправлении tpc ошибок и достаточно близка к единице при малых tpc. Но q-ичный симметричный канал не существует в природе, особенно для больших q, свойство равновероятности (q--1) значений искаженного q-ичного символа для такого канала достигается применением стохастического преобразования q-ичных символов канала.[3]
Защита от ошибок в различных телекоммуникационных системах сводится к применению протоколов, содержащих описание двух основных функций: помехоустойчивого кодирования и управления передачей на конкретном протокольном уровне (для канального, сетевого и сеансового уровней) эталонной модели взаимодействия открытых систем (ЭМВОС). Защита информации в таких системах сводится не только к борьбе с независимыми искажениями в канале связи (в двоичном - симметричном канале ДСК), но и к защите от группирующихся искажений (пакетов ошибок) и от преднамеренных искажений. Выше было показано, что в канале с более сложным распределением потока ошибок, чем в ДСК, применение кодов, исправляющих ошибки, затруднено. Применение кодов с исправлением ошибок преднамеренного характера до последнего времени считалось в принципе невозможным, хотя бы для классических алгебраических кодов.
С учетом сказанного выше, можно сказать, что теория алгебраического кодирования с алгоритмом декодирования по принципу максимального правдоподобия для исправления независимых ошибок является примером того, как ошибочная постановка задачи о независимых ошибках в канале связи сводит практически на нет труды целого поколения исследователей.
Для обеспечения применения кодов, исправляющих ошибки, сформулируем два варианта постановки задачи. [4]
При этом будем учитывать требования к защите информации в современных информационных и телекоммуникационных системах.. Особенностями таких глобальных систем является передача очень больших массивов информации и использование различных каналов связи наиболее простым образом без проведения исследования их свойств, в том числе модели ошибок в них.
Первая постановка, являющаяся «мягкой», состоит в том, что применяемые коды с исправлением ошибок должны обеспечивать в канале с естественными помехами (ошибками) подвергаемую количественной оценке вероятность ошибки декодирования отдельно по следующим характерным интервалам кратности ошибки:
- кратность ошибки t меньше половины величины кодового расстояния d, т.е. t Ј [(d-1)/2]
- кратность ошибки t меньше величины кодового расстояния d, т.е. t < d
- кратность ошибки t больше величины кодового расстояния d, t > dі
Вторая постановка, являющаяся сильной, состоит в том, что применяемые коды с исправлением ошибок должны обеспечивать в канале с произвольным характером ошибок гарантированную верхнюю границу для вероятности ошибки декодирование на всем интервале возможной кратности ошибки t Ј n; причем эта граница должна устанавливаться при проектировании выбором параметров кода.
Из эвристических соображений сформулируем свойства помехоустойчивого кода с исправлением ошибок, которые позволили бы обеспечить его применение для защиты информации в современных информационных и телекоммуникационных системах в любых из существующих задачах применения.[14]
1. Код имеет режимы обнаружения и исправления ошибок с обеспечением в обоих режимах гарантированной (наперед заданной) вероятности декодирования с ошибкой в произвольном канале связи и надежным отказом от декодирования при невозможности исправления ошибки.
Страницы: 1, 2, 3, 4, 5, 6
