Файл: Методы кодирования данных (Процесс формирования цифровых сигналов).pdf

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

Среди циклических кодов важное место занимает специфическим тип кодов, предложенных Боузом и Рой-Чоудхури и независимо от них Хоквингемом. Коды Боуза-Чоудхури-Хоквингема получили аббревиатуру «БЧХ-коды» и характеризуются специфическим выбором образующего циклический код полинома, что ведет к упрощению процедуры декодирования.[7]

В циклических кодах "r" проверочных символов, добавляемых к исходным "k" информационным, могут быть получены сразу, то есть. в целом, в результате умножения исходной подлежащей передаче кодовой комбинации Q(x) простого кода на одночлен x r и прибавлением к этому произведению остатка R(x), выполненного в итоге деления произведения на порождающий полином P(x).

Во время кодирования при трансляции данных из информационных разрядов в соответствии с определёнными для каждого К. правилами реализуются дополнительные знаки — проверочные разряды. При расшифровке из принятых кодовых слов по тем же сценариям снова создают проверочные разряды и сравнивают их с изначально принятыми; если они не совпадают, то при передаче была допущена ошибка. Есть также такие коды, которые обнаруживают факт модификации послания, и коды, исправляющие ошибки, то есть такие, при помощи которых есть возможность восстановить исходные данные.

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

1.4.2 Основные параметры и построение помехоустойчивых кодов

Проблема повышения верности обусловлена не соответствием между требованиями, предъявляемыми при передаче данных и качеством реальных каналов связи. В сетях передачи данных требуется обеспечить верность не хуже 10-6 - 10-9, а при использовании реальных каналов связи и простого (первичного) кода указанная верность не превышает 10-2 - 10-5.

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

Простые коды характеризуются тем, что для передачи информации используются все кодовые слова (комбинации), количество которых равно N=qn (q - основание кода, а n - длина кода). В общем случае они могут отличаться друг от друга одним символом (элементом). Поэтому даже один ошибочно принятый символ приводит к замене одного кодового слова другим и, следовательно, к неправильному приему сообщения в целом.

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

Применение помехоустойчивых кодов для повышения верности передачи данных связанно с решением задач кодирования и декодирования.

Задача кодирования заключается в получении при передаче для каждой 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-ичного символа P_q. В таком канале с вероятностыо 1 — P_q q-ичный символ принимается верно, после его искажения с вероятностью Р_q каждое значение q-ичного символа отличается от переданного и появляется на входе декодера с одинаковой вероятностью

P_q/(q-1).

В таком канале в зависимости от кратности ошибки t вероятность ошибки декодирования

при

 при (1)

В канале, не являющемся q-ичным симметричным для кода РС, получены следующие оценки для

1/(q-1)^i-2 + 1/(q-1)ⁱ при 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; причем эта граница должна устанавливаться при проектировании выбором параметров кода.