Материал: ОТС Лекции 1 и 2 часть

Каждый символ нового четверичного кода несёт уже не 1 дв.ед. информации (бит), а 2 дв.ед., т.к. при m=4 Hmax = log 4 =2 [бит/символ]. Энтропия этого кода максимальна, т.к. при равной вероятности каждого бита равновероятны и все дибиты.

Два символа двоичного кода длительностью 2Т несут, максимум, 2 бита информации (m=2; Hmax=1бит/символ; n=2; I = n * Hmax = 2бита). Один символ четверичного кода длительностью Т несет тоже 2 бита информации (m=4; Hmax=2бит/символ ; n=1; I = n * Hmax = 2 бита). Следовательно, мы в 2 раза увеличили скорость передачи информации. При этом помехоустойчивость приёма уменьшается.

5. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ ( КАНАЛЬНОЕ КОДИРОВАНИЕ ).

5.1. Основные определения.

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

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

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

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

кодовая комбинация отличается от другой.

кодовыми комбинациями, принадлежащими коду, - это вес Хэмминга, т.е. число ненулевых символов в векторе α , равном сумме ( xi xj ) по модулю 2. Очевидно, что 1≤d(xi,xj) ≤ n. Расстояние Хэмминга удовлетворяют аксиомам: d(xi,xj) ≥0; d(xj,xj) =0; d(xi,xj)= d(xj,xi) ; d(xi,xj) ≤ d(xi,xk)+d(xk,xj).

Вектор ошибки е - это двоичная комбинация длиной n, у которой символ “1” находится в тех позициях, где переданная и принятая комбинации не совпадают. Кратность ошибки равна весу Хемминга вектора е.

Исправляющая способность кода зависит от минимального кодового

расстояния данного кода. Минимальное кодовое расстояние: dmin=min i j d(xi,xj).

Для обнаружения одиночных ошибок минимальное кодовое расстояние между комбинациями должно равняться dmin=2. Например, для двоичного кода с основанием кода m=2 и длиной n=3 возможный набор разрешенных комбинаций с dmin=2 имеет вид:

32

Предположим, что была передана комбинация 000. В линии связи помеха исказила второй символ и мы приняли 010. Это запрещенная комбинация, т.е. декодер обнаружит ошибку. Выигрыш в помехоустойчивости получен за счет проигрыша в скорости передачи, т.к. четыре сообщения мы могли бы передавать с помощью четырех комбинаций примитивного кода с m=2, n=2: 00, 01, 10, 11. Т.о. проигрыш по скорости передачи равен 1,5. Иными словами, к

кодовой комбинации из k информационных символов 00, 01, 10, 11 добавляется (n-k) избыточных или корректирующих символов, связанных по

определенному алгоритму с информационными символами. Количество корректирующих символов характеризует избыточность кода R:

R=(n-k)/n; (5.1)

Избыточность рассмотренного выше кода равна: R=(3-2)/3=0,33.

Для обнаружения ошибок кратности k следует использовать код, имеющий

dmin= k+1.

Для исправления одиночных ошибок следует использовать код с dmin=3. Например, для кода с m=2; n=3 можно использовать комбинации:

Пусть передается комбинация 000. Допустим, что помеха исказила второй символ и мы приняли 010. Эта комбинация запрещенная, но она ближе к переданной комбинации 000 (d=1), чем к другой возможной 111 (d=2). Таким образом, мы декодируем комбинацию 010 как 000, т.е. исправляем ошибку. Выигрыш в помехоустойчивости достигается за счет еще большего проигрыша в скорости передачи, т.к. два сообщения мы могли бы передавать с помощью двух комбинаций примитивного кода с m=2, n=1: т.е. 0 и 1.Таким образом, к каждой информационной комбинации из одного символа мы добавили по 2 корректирующих (проверочных) символа.

Проигрыш по скорости передачи данного кода, исправляющего одиночные ошибки, по сравнению с примитивным или безызбыточным кодом равен 3. Избыточность этого кода равна: R=(3 -1)/3=0,667.

Для исправления ошибок с кратностью k следует использовать коды с минимальным кодовым расстоянием dmin=2k+1.

Проверка на четность.

Для обнаружения одиночных ошибок одним из наиболее совершенных способов кодирования является «проверка на четность»: к кодовой

комбинации из n информационных символов добавляется один проверочный такой, чтобы количество единиц в кодовой комбинации было четным. Например, к комбинации 0100110 добавляем проверочный символ 1, и передаем комбинацию 01001101. Одиночная ошибка делает число единиц в

33

принятой кодовой комбинации нечетным ( 3 или 5), что и обнаруживается на приеме.

5.2. Линейный двоичный блочный код.

Широко используются в технике связи линейные блочные систематические коды. Блочный код состоит из кодовых комбинаций, называемых также кодовыми словами. Длина каждого кодового слова равна n. Код - систематический, т.е. первые k символов являются информационными, а следующие (n - k) являются корректирующими. Блочный код обозначается, как код (n,k). Общее количество кодовых комбинаций равно N=mk. Если код – двоичный, то N=2k.

АЛГОРИТМ КОДИРОВАНИЯ

Рассмотрим алгоритм кодирования для двоичного блочного кода (7,3), у которого каждое слово имеет n=7 символов, из которых k=3 – информационные и (n-k)=4 – проверочные.

Алгоритм формирования кодовых комбинаций следующий: 1.Присваиваем каждому символу кода номер : a1, а2, а3, а4, а5, а6, а7.

Первые три символа (a1, а2, а3) являются информационными. Последние четыре символа - корректирующие (проверочные): а4, а5, а6, а7.

2. Составляем порождающую матрицу G. Эта матрица должна иметь n столбцов и k строк. Левая часть матрицы – это единичная матрица размером k*k. Правая часть G–это матрица-дополнение Р размером (n-k)*k:

Матрица-дополнение P имеет в данном случае вид:

0 1 1 1 P = 1 0 1 1 1 1 0 1

3. Формируем кодовые комбинации. Для этого, сначала, записываем все

возможные информационные комбинации из трех символов (всего восемь комбинаций ): 000,001,010,011,100,101, 110,111.

4. К информационным символам приписываем четыре проверочных символа, получающихся в результате умножения информационного вектора-строки

(a1a2a3) на матрицу-дополнение Р. Произведение есть вектор-строка (a4a5a6a7):

(a1a2a3) * P = (а4, а5, а6, а7)

Очевидно, для заданной матрицы Р: а4 = а2 а3; a5 = a1 а3; а6 = а1 а2; а7= а1 а2 а3;

Знак означает суммирование по модулю 2, т.е. 0 0 = 0; 1 0 = 1; 0 1 = 1; 1 1 = 0.

5. Составляем кодовую таблицу разрешенных кодовых комбинаций:

34

Для полученного кода dmin = 4, т.е. наш код может исправлять все одиночные ошибки и некоторые двойные.

АЛГОРИТМ ДЕКОДИРОВАНИЯ

Однако, количество операций необходимых для такого алгоритма быстро растет с ростом n. Более оптимальным способом является вычисление синдромов.

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

где а1, а2.....а7 - принятый кодовый символ, возможно искаженный помехой.

35