Теория кодирования

     К комбинационным кодам можно отнести также антифединговые коды, предназначенные для обнаружения и исправления ошибок в каналах с замираниями (федингом) сигналов. Для таких каналов с группированием ошибок применяют метод перемежения символов или декорелляции ошибок. Он заключается в том, что символы, входящие в одну кодовую комбинацию, передаются не непосредственно друг за другом, а перемежаются символами других кодовых комбинаций исходного систематического или любого другого кода. Если интервал между символами, входящими в одну кодовую комбинацию, сделать длиннее "памяти" (интервала корелляции) канала с замираниями, то в пределах длительности одной исходной кодовой комбинации группирования ошибок не будет. На приёме после обратной "расфасовки" в кодовых комбинациях можно производить декодирование с обнаружением и исправлением ошибок.

     В систематических кодах различают  два метода формирования проверочной группы символов: поэлементный и в целом.

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

     Проверочная группа из r символов формируется поэлементно по соответствующему алгоритму. Коды Хемминга, имеющие dmin = 3, позволяют исправить одну ошибку

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

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

     Среди циклических кодов особое место  занимает класс кодов, предложенных Боузом и Рой-Чоудхури и независимо от них Хоквингемом . Коды Боуза-Чоудхури-Хоквингема получили сокращённое наименование БЧХ - коды и отличаются специальным выбором порождающего (образующего) циклический код полинома, что приводит к простой процедуре декодирования.[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 вероятность ошибки декодирования

     

       P_ош(t)=0 при t ≤ (d_РС-1)/2 =t_РС

       P_ош(t) ≤ (q-1) → ∑ C_n^S (q-1)^S

       при d - t_РС ≤ t ≤ d-1

       P_ош(t) ≤ (q-1) → ∑ C_n^S (q-1)^S при t ≥d (1) 

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

       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]