Контроль правильности передачи данных.

Основной метод: введение информационной избыточности в системы кодирования информации. При этом информационное не избыточное кодирование 2^K представляется в пространстве 2ⁿ кодовых комбинаций, где n>k – избыточное кодирование. При этом часть комбинаций во множестве 2ⁿ являются запрещенными, не используемыми при передачи информации. Правило отнесения кодовой комбинации к запрещенной или разрешенной определяется алгоритмом кодирования. Если при передачи информации возникает запретная кодовая комбинация, то процесс передачи информации считается ошибочным и принимается меры по получению правильной кодовой комбинации.

Т. к. множество 2^k является подмножеством 2ⁿ, то для того чтобы не только обнаружить, но и исправить отдельные виды ошибок необходимо, чтобы подмножество запрещенных комбинаций по классам смежности к подмножеству 2^k.

Степень корректирующей способности информативно-избыточного кодирования определяется кодовым расстоянием по Хэммингу. Под кодовым расстоянием между 2-мя кодовыми комбинациями понимается количество разрядов, которыми эти кодовые комбинации отличаются друг от друга. Систему кодирования характеризуют минимально возможным кодовым расстоянием.

Если dmin = 1 – это информационно не избыточное кодирование.

Если dmin = 2 – позволяет обнаружить одиночную ошибку.

040 Аколупин Р. (01.12)

Чтобы обнаружить двойную ошибку и исправить одиночную, надо чтобы минимальное кодовое расстояние (мин.к.р.) было не менее трех. Мин.к.р.=3 в системах кодирования по Хэммингу. Коды Хэмминга используются для контроля за передачей инф. между блоками системы при параллельной связи или при записи инф. на магнитные носители с записью по нескольким дорожкам одновременно.

Для последовательной передачи инф., а также для осуществления некоторых других видов контроля (контроль по четности) используется циклическое кодирование. Называется оно так от способа образования кодового пространства путем циклического сдвига элементов образующей матрицы кода. При этом циклический сдвиг представляется как линейная операция над кодовой комбинацией, выполняемая по соответствующему правилу. Наиболее часто в качестве алгоритмов получения циклических кодов используется операция * и / исходного полинома некоторой эффективной величины Х, представляющего инф. кодовую комбинацию, на максимальную степень этой переменной пораждающего полинома. Остаток от этого деления передается либо последними цифрами кодовой комбинации либо в соответствующем поле инф. пакета. Исходный полином F(x) инф. комбинации умножается на максимал. Степень пораждающего полинома P(x) - к т.е. F(x)*x^к иделится на P(x) => (F(x)*x^к)/P(x)=Q(x)(+)R(x), где Q(x)-частное, R(x)-остаток

E(x)=F(x)*x^к(+)R(x) => P(x)*Q(x) (+)R(+)R ; E(x)/P(x)-делится без остатка

По виду остатка можно определить характер искажения.

E(x)/P(x)=P(x)*Q(x)/P(x) (+)R(+)R=Q(x)

В данных выражениях (+)-обозначает сумму по модулю 2.

Максимал. степень и наличие остальных степеней в P(x) должно быть достаточным для получения такого кол-ва ненулевых остатков, которые бы соответствовали всем запрещенным комбинациям. Минимальная степень P(x) :к=1. Вэтом случае остаток, получаемый от деления на P(x) будет иметь разрядность 1 бит, а его величина будет равняться либо 0 либо 1.

Пример: Пусть есть кодовая комбинация 88h и P(x)=x⁴+x+1 => 10011

88h=10001000 ; к=4

1) 1000.1000.0000

сдвиг влево на 4

2)10001000000

10011

10011

10011

10011

Тогда имеем кодовую комбинацию

10011

10011

10011

10011

Свойства циклических кодов:

1) Контрольная часть не влияет на инф. часть => есть возможность ее отбрасывать, не учитывать и т.д.

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

Кроме приведенных систем кодирования могут использоваться и другие :

а) Итеративные коды

б) Сверточные коды

в) Равновесные коды

Итеративные коды

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

Поскольку dmin= П dmin ij

ij

Пусть осуществляется кодирование байт инф.(вектора), котор. Записывается блоками по 8 байт в векторе:

a₁₁ a₁₂ a₁₃ a₁₄ a₁₅ a₁₆ a₁₇ a₁₈ | p_1i

a₂₁ a₂₂ a₂₃ a₂₄ a₂₅ a₂₆ a₂₇ a₂₈ | p_2i

a₃₁ a₃₂ a₃₃ a₃₄ a₃₅ a₃₆ a₃₇ a₃₈ | p_3i

…………………………. | ….

a₈₁ a₈₂ a₃₈ a₈₄ a₈₅ a₈₆ a₈₇ a₈₈ | p_8i

p_j1 p_j2 p_j3 p_j4 p_j5 p_j6 p_j7 p_j8 | ∆_ji

Для построения итеративного кода надо осуществить контроль четности по одной координате и по другой. На приемной стороне осущ. контрольные операции по четности столбцов и строк можно обнаружить ошибки соответствующей кратности. Возникновение несимметричных ошибок (одиночных) приводит к нарушению симметрии. Т.обр. будут обнаруживаться 1-е, 2-е , 3-и ошибки, но обязательно не симметричные.