конспект ТЭС кодирование сообщений нов

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

Степень различия между кодовыми комбинациями оценивается расстоянием Хэмминга (d, dх). Для любых двух двоичных комбинаций символов Ai и Aj расстояние Хэмминга dij равно числу несовпадающих в них разрядов и математически вычисляется как число единиц в сумме по модулю два этих комбинаций. Так, приведенные ниже две последовательности Ai и Aj не совпадают в трех разрядах:

101000= Ai

110010= Aj 011010

Вэтом случае dij=d=3.

Для оценки корректирующей способности заданного кода используют минимальное расстояние Хэмминга, взятое по всем парам слов. Его называют кодовое расстояние d0:

d0=min dij = dmin.

Если для какого-то кода расстояния Хэмминга принимают значения 6,3,7,5,4, то кодовое расстояние этого кода d0 = dmin =3.

С позиции теории кодирования d0 показывает, сколько символов

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

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

Доказано, что для гарантированного обнаружения ошибок кратности tобн кодовое расстояние d0 должно быть хотя бы на единицу больше кратности обнаруживаемых ошибок tобн:

d0≥ tобн +1

(3)

21

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

d0≥ 2tисп+1

(4)

Из выражений (3) и (4) следует, что кратность обнаруживаемых кодом ошибок

tобн ≤ d0-1,	(5)
а кратность исправляемых ошибок
tисп ≤ d0 −1(2)	(6)
2

Число "2" в выражении (6) вычитается при четном значении кодового расстояния d0.

Чтобы помехоустойчивый код исправлял tисп ошибок и обнаруживал tобн ошибок необходимо выполнение следующего условия

d0≥ tисп + tобн +1.

(7)

Соотношения (3), (4) и (7) являются основными для определения корректирующей способности кода, так как позволяют при заданном d0 определить кратность обнаруживаемых tобн и исправляемых tисп ошибок.

Пример 4 Кодовое расстояние корректирующего кода d0=4. Ошибки какой кратности данный код может обнаруживать и исправлять? Из (5) и (6) следует, что при d0=4 кратность обнаруживаемых ошибок tобн ≤3; кратность исправляемых ошибок tисп

=1.

22

Пример 5 Чему должно быть равно кодовое расстояние d0, достаточное для исправления трехкратных ошибок? Из (4) следует, что d0≥2 tисп+1. При tисп=3 получаем d0≥7.

Классификация помехоустойчивых кодов

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

1 По способу преобразования k информационных символов в n

кодовых символов коды подразделяются на блочные (блоковые)

инепрерывные. В блочных кодах из k информационных символов формируются r проверочных символов, которые совместно с k информационными символами образуют кодовую последовательность из n=(k+r) кодовых символов. Информационные символы каждого входного блока не оказывают влияния на формирование проверочных символов предшествующих и последующих кодовых последовательностей. Каждый блок информационных символов обрабатывается независимо от других. В непрерывных кодах формируется непрерывная кодовая последовательность кодовых символов. Четкое деление на кодовые комбинации из п символов отсутствуют. Формируемая последовательность зависит не только от информационных символов, поступивших на вход кодера в данный момент времени, но

иот предыдущих символов на входе или выходе кодера.

2 По алгоритму формирования r проверочных символов по-

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

3 По структуре кодовых последовательностей коды могут быть разделимыми и неразделимыми. В разделимых кодах есть четкое деление на блоки из k информационных символов, r проверочных символов и на кодовые последовательности из n символов. В неразделимых кодах отсутствует четкое деление на информационные и проверочные символы.

23

4 По способу передачи кодовых символов коды делятся на систематические и несистематические. В систематических кодах в канал связи первоначально передается блок из k информационных символов, а затем блок из r проверочных символов. В несистематических кодах нет четкого деления на блоки информационных и блоки проверочных символов. В канал связи кодовые символы передаются по "псевдослучайному" закону. Например, вначале может быть передано два проверочных символа, а затем - три информационных символа, потом - один проверочный, два информационных и т.д.

5 По количеству символов в кодовых последовательностях помехоустойчивые коды могут быть равномерными и неравномерными.

БЛОЧНЫЕ ПОМЕХОУСТОЙЧИВЫЕ КОДЫ

Основные параметры блочных кодов

1 Длина кодовой последовательности (комбинации) п- количество символов, выбранных для передачи сообщений.

2 Количество информационных символов k, несущих полезную информацию.

3 Количество проверочных (контрольных) символов r = n – k. 4 Скорость передачи кода R = k / n.

5 Кодовое расстояние кода d0.

6 Кратность контролируемой ошибки (tобн или tисп).

7 Вес кодовой последовательности W – определяется количеством ненулевых символов, входящих в кодовую последовательность.

8Мощность кода М. В помехоустойчивом коде М = Мразр.

Вдвоичном линейном помехоустойчивом коде М = Мразр = 2k.

Несистематические блочные коды

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

24

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

Примером кода с постоянным весом является семиэлементный телеграфный код №3 (МТК-3), рекомендованный для использования в системах с обратной связью с целью обнаружения ошибок. Вес кода равен трем следовательно, каждая разрешенная кодовая комбинация имеет три единицы и четыре нуля. В МТК-3 из общего числа кодовых комбинаций Мобщ=27=128 разрешенными являются Мразр=35.

Декодирование принятых кодовых комбинаций кода с постоянным весом сводится к вычислению их веса (подсчета числа единиц). Если вес отличается от заданного, то выносится решение, что комбинация принята с ошибками. Например, из трех принятых кодовых комбинаций 1011000, 1101010, 0101010 ошибки обнаруживаются во второй, поскольку её вес равен четырем. Кодовое расстояние кода МТК-3 d0=2. Код обнаруживает все ошибки нечетной кратности и часть ошибок четной кратности. Не обнаруживаются только так называемые ошибки смещения, сохраняющие неизменным вес комбинации (число искаженных единиц всегда равно числу искаженных нулей). Коды с постоянным весом наиболее эффективны в каналах, где вероятность ошибок смещения невелика.

Групповые систематические линейные блочные коды

Разрешенная кодовая комбинация систематического линейного блочного кода (СЛБК) имеет четкое деление на k информационных символов и r проверочных символов. Общая длина последовательности n=k+r. В канал связи передаются вначале информационные символы, а затем – проверочные. Код, построенный таким образом, обозначается (n; k) или (n; k; d0). Первое число в скобках показывает общее число символов в кодовой комбинации, второе – число информационных символов, третье – кодовое расстояние кода. Проверочные символы СЛБК формируются путем суммирования по модулю два информационных символов, стоящих на определенных позициях и, кроме того, поразрядная сумма по модулю два двух разрешенных ко-

25

довых комбинаций образует также разрешенную кодовую комбинацию. Для задания кода нет необходимости перечислять все разрешенные кодовые слова Мраз=2k. Достаточно привести всего лишь несколько и далее указать принцип или способ их преобразования. Это свойство СЛБК объясняется тем, что линейные блочные коды образуют математическую структуру, называемую группой. В общем случае, группой G называется множество элементов, на котором задана некоторая групповая операция (обозначим символом «*»). Эта операция однозначно сопоставляет двум элементам множества G третий элемент того же множества.

В случае помехоустойчивых кодов групповые коды – это такие линейные блочные коды, совокупность кодовых слов которых вместе с нулевым кодовым словом, снабженная операцией посимвольного (поразрядного) сложения по модулю два, образует группу G и соответствует основным четырем свойствам группы:

а) замкнутость: для каждой пары «а» и « b» из множества G элемент с=а*b также принадлежит множеству G;

б) ассоциативность: для всех «а», «b» и «с», из множества G выполняется условие а*(b*с)=(а*b)с;

в) существование нейтрального элемента – единицы. В множестве G существует элемент «е», называемый единичным элементом и такой, что а*е=е*а=а для любого элемента множества; г) существование обратных элементов. Для любого «а» из множества G существует некоторый элемент «b» из множества, называемый обратным элементу «а» и такой, что а* b=b*а=е. Группа G называется конечной, если она состоит из конечного числа элементов. В противном случае группа называется бесконечной. Некоторые группы обладают дополнительным свойством коммутативности: для любых «а» и « b» из группы а*b=b*а. Такие группы называют абелевыми. Далее будут рассмотрены помехоустойчивые коды, которые соответствуют

свойствам абелевых групп.

Коды с четным числом единиц

26

Код с четным числом единиц является простейшим систематическим линейным блочным кодом (n; n-1), или (k+1, k), в котором операции кодирования и декодирования проводятся как проверка на четность. Разрешенная комбинация этого кода при любом числе информационных символов имеет всего один проверочный символ. Обычно его ставят после информационных. Проверочный символ определяется из условия, что общее число единиц в разрешенном кодовом слове должно быть четным, т.е. проверочный символ должен быть равен сумме по модулю два k информационных символов.

Если разряды кодовых комбинаций пронумеровать слева направо и символы в этих разрядах обозначить для безызбыточ-

ного кода a1,a2 ... ak, а для корректирующего b1,b2 ... bk·bk+1, то процедура формирования разрешенной кодовой комбинации за-

пишется в виде:

bi = ai приi = 1,2,... ,k;	(8)
bk+1 = a1 a2 ... ak

В (8) первое равенство означает, что информационные символы при кодировании не изменяются, а второе описывает правило формирования проверочного символа. При декодировании принятая кодовая комбинация проверяется на четность (сумма по модулю два (k+1) разрядов должна быть равна нулю):

с = b1 b2 ... bk bk+1 = 0. (9)

При наличии ошибок нечетной кратности условие (9) нарушается и тем самым обнаруживается наличие ошибки. Ошибки четной кратности код (n, n-1) не обнаруживает. Кодовое расстояние кода с контролем четности d0 = 2. Из выражения (6) следует, что данный код не исправляет обнаруженные ошибки:

t	≤ d0 −2 = 0.
исп	2

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

27

Пример 6 Необходимо передать – кодом с четным числом единиц (8;7) кодовую комбинацию 1011011. Рассчитаем проверочный символ в соответствии с выражением (8):

b8=1 0 1 1 0 1 1 =1. Следовательно, передаваемая комбинация будет иметь вид В=10110111. Пусть будет принята

комбинация с одной ошибкой 10110011. Контрольная сумма с1=1 0 1 1 0 0 1 1 =1 ≠ 0, что свидетельствует о

наличии ошибки. Если же принята комбинация с двумя ошибка-

ми	11010111,	то	контрольная	сумма
с2=1 1 0 1 0 1 1 1 = 0.			Условие (9)	выполнено и
ошибка не обнаружена.

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

Общие сведения

К кодам Хэмминга относится семейство групповых систематических линейных блочных помехоустойчивых кодов с параметрами (n; k). Число проверочных символов r = n-k. Для этих кодов выполняется равенство 2r= 2n-k=1+n или n=2n-k-1= 2r-1.

Кодами Хэмминга являются коды (3;1), (7;4),(15;11), (31;26).

Кодовое расстояние кодов Хэмминга d0=3 и, соответственно, они могут гарантированно обнаруживать две ошибки и исправлять одну ошибку. Для построения кода Хэмминга нет необходимости задавать все 2k разрешенные кодовые комбинации. Достаточно выбрать определенным образом k исходных разрешенных кодовых комбинаций и затем путем их посимвольного суммирования по модулю два в различных сочетаниях получить остальные (2k-k) разрешенные последовательности. Вышеуказанные исходные кодовые комбинации называют базисными. При их выборе должны выполняться следующие условия:

а) исходные (базисные) кодовые последовательности должны выбираться различными;

б) нулевая кодовая последовательность (состоящая из одних нулей) не должна выбираться;

28

в) исходные кодовые комбинации должны быть линейнонезависимыми и образовывать алгебраическую группу по отношению к операции суммирования по модулю два;

Примечание: Линейно-независимыми являются ненулевые комбинации А1, А2…,Аk, если выполняется условие

c1 A1 c2 A2 ... ck Ak ≠ 0, где сi=0 или 1, причем хотя бы

один из коэффициентов сi≠0

г) вес (число единиц) каждой исходной кодовой последовательности должен быть не менее d0;

д) вес проверочной части исходной кодовой последовательности должен быть не менее d0-1;

е) расстояние Хэмминга d в любых парах исходных кодовых последовательностей должно быть не менее d0;

ж) минимальный вес исходной кодовой последовательности должен быть равен кодовому расстоянию d0.

Порождающая матрица

Обычно набор из k линейно независимых кодовых последовательностей, формирующих СЛБ (n; k)-код, записывают в виде матрицы, называемой производящей или порождающей (генери-

рующей) матрицей, обозначаемой как Gk,n. Матрица Gk,n содержит k строк и n столбцов, так как ее размерность (ранг) – (k×n) определяется параметрами кода n, k и r. В общем виде порождающая матрица может быть записана так:

a11 a12 ...a1k b11b12 ...b1r

a21a22 ...a2k b21b22 ...b2r
Gk,n=	,
ak 1ak 2 ...akk bk 1bk 2 ...bkr

где буквами а обозначены информационные символы, а буквами b – проверочные.

Для кодирования с помощью матрицы Gk,n ее приводят к каноническому приведенно-ступенчатому виду. Каноническая матрица Gk,n содержит две подматрицы: информационную − ран-

29

гом (k×k) и проверочную − рангом (k×r). Информационную подматрицу представляют в виде единичной квадратной матрицы Ik, у которой по главной диагонали стоят единицы, а все остальные элементы − нули. Единичная матрица Ik имеет вид:

		100...0
Ik= Ik,k=		010...0		(10)
		000...	1

Используя матрицу (10), можно сформировать любую кодовую комбинацию простого (безызбыточного) k – разрядного кода. Возможное число комбинаций равно 2k.

Для составления канонической матрицы Gk,n к информационной единичной матрице Ik приписывают справа проверочную подматрицу G*, формируемую с учетом требований, предъявляемых к исходным базисным комбинациям помехоустойчивого кода. При этом необходимо учитывать следующие свойства СЛБК: чем больше логических «1» в приписываемых строках проверочной подматрицы, тем большей корректирующей способностью обладает разрабатываемый код и тем сложнее его реализация. В качестве примера построим каноническую порождающую матрицу для кода Хэмминга (7;4;3), в котором число информационных символов k=4, общее число символов n=7.

Информационная единичная подматрица этого кода имеет вид:

1000

0100

Ik= I4,4= 0010 (11)

0001

Допишем к каждой строке матрицы Ik символы провероч-

ной подматрицы, причем вес приписываемой строки должен быть не менее d0-1=3-1=2, т.е. необходимо к каждой строке дописать по две «1». В этом случае вес каждой строки матрицы Gk,n будет равен Wстр= d0=3. Число столбцов в матрице Gk,n ока-

30