Курсовая работа: Проектирование системы передачи цифровых данных

Для определения мест ошибок в кодовой комбинации вводится понятие вектора ошибок. Вектор ошибок n‑разрядного кода – это n‑разрядная комбинация, единицы в которой указывают положение искажённых символов кодовой комбинации.

Вес вектора ошибки we характеризует кратность ошибки. Сумма по модулю 2 для искажённой кодовой комбинации и вектора ошибки равна исходной неискажённой комбинации.

Помехоустойчивость кодирования обеспечивается за счёт введения избыточности в кодовые комбинации. Это значит, что не все n символов кодовой комбинации используются для кодирования информации, а только какая их часть k<n. Следовательно, из всех возможных комбинаций N0 = 2n для кодирования используется Nk = 2k комбинаций, т.е. всё множество возможных кодовых комбинаций делится на две группы:

Группа Nk = 2k– разрешённых комбинаций.

Группа (N0 – Nk) = 2n– 2k – запрещённых комбинаций.

Если на приёмной стороне получена разрешённая комбинация, то считается, что искажений нет, иначе принятая комбинация искажена.

В общем случае каждая из Nk разрешённых комбинаций может трансформироваться в любую из N0 возможных комбинаций, т.е. всех возможных комбинаций может быть Nk*N0, Nk(Nk–1) переходы одних разрешённых комбинаций в другие разрешённые и Nk(N0–Nk) переходов в запрещённые комбинации.

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

.(3)

Для построения кода, обеспечивающего не только обнаружения ошибок, но и исправление ошибок. Множество запрещённых кодовых комбинаций разбивается на Nk непересекающихся подмножеств Nk, каждому из которых ставится в соответствие одна из разрешённых комбинаций. В этом случае, если принятая запрещённая комбинация принадлежит подмножеству Mi, то считается, что передана комбинация Аi и ошибка будет исправлена. Т.о. ошибка исправляется в (N0-Nk) случаях, равных количеству запрещённых комбинаций от общего числа обнаруженных ошибочных комбинаций определяется уравнением:

.(4)

Выбор способа разбиения на подмножества определяется типом ошибок. Допустим, необходимо построить код, обнаруживающий все ошибки кратностью t и меньше. Это значит, что из множества всех возможных комбинаций N0 необходимо выбрать Nk разрешённых комбинаций так, чтобы любая из них в сумме по модулю два с любым вектором ошибок E с весом we£t не была равна никакой другой разрешённой комбинации. Для этого необходимо, чтобы кодовое расстояние удовлетворяло равенству:

dmin³t + 1, (5)

где dmin – наименьшее расстояние Хэмминга.

1.1.4 Построение кода с заданной коррекцией

При рассмотрении корректирующих кодов предполагалось, что его длина n задана, а повышение корректирующей способности кода достигалось за счёт уменьшения множества Nk разрешённых комбинаций при неизменном n или уменьшении информационных символов k. На практике коды строятся в обратном порядке: вначале выбирается количество информационных символов, а затем обеспечивается необходимая корректирующая способность кода за счёт добавления избыточных символов.

Если задано число корректирующих разрядов k (), а всего в коде n разрядов, то граница Хемминга для исправления l ошибок определяется выражением:

(6)

Все корректирующие коды можно разделить на два основных класса: непрерывные (рекуррентные) и блочные. В непрерывных кодах процесс кодирования и декодирование имеет непрерывный характер. Каждый избыточный символ (проверочный) формируется по двум или нескольким информационным символам. Проверочные символы размещаются в определённом порядке между информационными символами исходной последовательности.

В блочных кодах каждому сообщению (или элементу сообщения) соответствует кодовая комбинация из n символов, которая называется блоком. Блоки кодируются и декодируются раздельно. Блочные коды могут быть равномерными, если n – постоянно, и неравномерными, если n – непостоянно. Как непрерывные, так и блочные коды в зависимости от методов размещения проверочных символов могут быть разделимыми и неразделимыми. В разделимых кодах одни символы являются информационными, а другие проверочными и служат для обнаружения и исправления ошибок. Информационные и проверочные символы занимают во всех комбинациях одни и те же позиции.

Разделимые блочные коды называют n,k‑кодами, где n – значность кода, к – число информационных символов. Разделимые блочные коды делятся на несистематические и систематические. В несистематических кодах проверочные символы представляют суммы подблоков длиной l , на которые разделена последовательность информационных символов. Такой код может обнаружить серийные ошибки с длиной серии не более l. В несистематических или линейных кодах проверочные символы определяются в результате линейных операций над определёнными информационными символами. Для двоичных кодов каждый проверочный символ выбирается таким, чтобы его сумма по mod2 с определёнными информационными символами стала равной 0. При декодировании производится проверка на четность определённых групп символов, поэтому также коды ещё называют – коды с проверкой на четность.

1.1.5 Коды Хэмминга

Двоичный код Хэмминга содержит k информационных символов и p = n ‑ k избыточных символов. Избыточная часть кода строится так, чтобы при декодировании можно было указать номер позиции, в которой произошла ошибка. Это достигается путём многократной проверки принятой комбинации на четность. Количество проверок равно количеству избыточных символов Р. При каждой проверке получают двоичный контрольный символ. Если результат проверки даёт чётное число единиц, то контрольному символу присваивается 0, иначе –1. В результате всех проверок получается p ‑разрядное двоичное число, указывающее номер искажённого символа. Для исправления ошибки достаточно проинвертировать данный символ.

Необходимое количество проверочных символов p (или значность кода n ) определяется по формуле:

Nk£ 2n/(1+n)(7)

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

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

Для упрощения операций кодирования и декодирования рекомендуется размещать проверочные символы так, чтобы каждый входил в минимальное число проверяемых групп, то есть размещать контрольные символы на позициях, номера которых встречаются только в одной из проверочных групп: 1, 2, 4, 8.(Таблица 2). Следовательно в кодовой комбинации символы а1, а2, а4, а8 . . . должны быть проверочными, а символы а3, а5, а6, а7, а9, и т. д.- информационными.

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

1.1.6 Циклические коды

Циклические коды являются наиболее простыми и эффективными для обнаружения и исправления независимых и серийных ошибок. Основным свойством циклических кодов является то, что каждая кодовая комбинация может быть получена путём циклической перестановки символов комбинации, принадлежащей данному коду, то есть если кодовый вектор V =(a0,a1,a2, . . ., an-2) принадлежит циклическому коду, то и вектор V 1 = (an‑1, a0, a1, a2, . . ., an-2) также ему принадлежит. Циклические коды записываются в виде полиномов.

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