Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 11

A1 = 000;         A8 = 111.

Пусть теперь необходимо построить КОД,ОБЕСПЕЧИВАЮЩИЙ УСТРАНЕНИЕ

ОДНОКРАТНЫХ ОШИБОК.Выбираем в качестве первой разрешённой комбинации A1 = 000.При наличии одиночных ошибок комбинация A1 может перейти в A2 = 001,A3 = 010 или A5 = 100.Комбинации A2,A3 и A5 должны быть запрешёнными.Тогда в случае приёма одной из них выносится решение,что передана комбинация A1.

Пусть в качестве второй разрешённой комбинации выбирается комбинация,отстоящая от первой на расстоянии d = 2,например,A4 = 011.Ей соответствует подмножество запрещённых комбинаций A3 = 010,A2 = 001

и A8 = 111.Однако получилось пересечение подмножеств для A4 и A1.

При приёме A2 или A3 нельзя однозначно установить,передана комбинация A1 или A4.

Если же в качестве второй разрешённой комбинации выбрать комбинацию,отстоящую от A1 на d = 3,т.е.комбинацию A8 = 111,которой соответствует подмножество запрещённых комбинаций A4 = 011,A6 = 101 и

A7 = 110,то в этом случае подмножества запрещённых комбинаций не пересекаются.Следовательно,при d = 3 обеспечивается устранение всех одиночных ошибок.

В ОБЩЕМ СЛУЧАЕ ДЛЯ УСТРАНЕНИЯ ОШИБОК кратности S кодовое расстояние должно удовлетворять условию

d min = > t + S + 1

Аналогично рассуждая,можно установить,что для ИСПРАВЛЕНИЯ всех ошибок кратности не более S и одновременно ОБНАРУЖЕНИЯ всех ошибок кратности не более t и при t = > S кодовое расстояние должно удовлетворять условию

d min = > t + S + 1 .

ОПРЕДЕЛЕНИЕ  КОЛИЧЕСТВА  КОРРЕКТИРУЮЩИХ  СИМВОЛОВ .

При построении реальных кодов перед разработчиками стоит задача опредпления числа добавочных,корректирующих символов p = n - k,исходя из числа информационнных разрядов k,либо из общей длины кода n.

Для обнаружения и исправления одиночой ошибки соотношение между числом информационнх разрядов k и числом корректирующих разрядов p

должно удовлетворять следующим условиям

2^p = > n + 1

2^k = > 2^n/( n + 1 ).

При этом подразумевается,что общая длина кодовой комбинации

n = k + p .

Для ПРАКТИЧЕСКИХ РАСЧЁТОВ при определении p для кодов с минимальным кодовым расстоянием d = 3 удобно пользоваться выражениями,где цифра в индексе - число исправляемых ошибок,в скобках - обнаруживаемых:

p1(2) = [log 2 (n + 1)], если известна длина полной кодовой последовательности n,и

p1(2) = [log 2 {(k + 1) + [log 2 (k + 1)]}], если задано число информационных символов k (квадратные скобки означают округление).

Для кодов,ОБНАРУЖИВАЮЩИХ ВСЕ ТРЁХКРАТНЫЕ ОШИБКИ (d min = 4),

p1(3) = >1 + log 2(n + 1), или

p1(3) = >1 + log 2[(k + 1) + log 2(k + 1)],

Для кодов длиной в n символов,исправляющих одну или две ошибки

( d min = 5),

2     1

p2 = >log 2 ( C n + C n + 1 ) .

Для практических расчётов можно поьзоваться выражением

p2 = [ log 2 (n^2 + n + 1) / 2 ].

Для кодов,ИСПРАВЛЯЮЩИХ ТРИ ОШИБКИ (d min = 7),

p3 = [ log 2 (n^3 + n^2 + n + 1) / 6 ].

Для кодов,ИСПРАВЛЯЮЩИХ S ОШИБОК (d min = 2S + 1),

s    s-1                          2s-1    2s-2

log 2 (Cn + Cn  + ... + 1) < p2 < log 2 (Cn-1  + Cn-1  + ... + 1)

Выражение слева известно как нижняя граница Хэмминга,а выражение справа - как верхняя граница Варшамова - Гильберта.

Для приближённых расчётов можно пользоваться выражением:

ps = [(log 2 n^s + n^s-1 + ... + 1) / S!].

К О Д Ы   С   О Б Н А Р У Ж Е Н И Е М   О Ш И Б О К .

К О Д   С   Ч Ё Т Н Ы М   Ч И С Л О М   Е Д И Н И Ц .

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

Избыточность кода равна Kизб = p/n = 1/n.

Код позволяет обнаруживать все ошибки нечётной кратности.

К О Д   С   У Д В О Е Н И Е М   Э Л Е М Е Н Т О В .

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