Заработок в интернет постоянно и регулярно платят

Алгоритмы обнаружения ошибок. Алгоритм Хэминга


1. Обнаружение ошибок.

2. Необходимость использования сложных алгоритмов.

3. Основная идея алгоритмов.

4. Полиномиальная арифметика.

5. Двоичная арифметика без переноса.

6. Алгоритмы Хэминга.


1.Обнаружение ошибок.

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

Сообщение 06 23 04
Сообщение с контрольной суммой 06 23 04 33
Сообщение после передачи 06 27 04 33

В этом примере возникла ошибка во втором байте, и вместо числа 23 было передано число 27. Такую ошибку приемник может определить, вычислив контрольную сумму (37) и сравнив ее с полученной (33). Если бы сбой произошел в четвертом байте - в самой контрольной сумме, то верное сообщение было бы забраковано. Но главная опасность в том, что ошибка может произойти как в самом сообщении, так и в контрольной сумме, причем таким образом, что контрольная сумма от неверного сообщения совпадет с неверно переданной контрольной суммой. К сожалению, полностью избежать такой ситуации нельзя, можно лишь уменьшать вероятность ее возникновения, увеличивая длину контрольной суммы.

Существуют различные методы обнаружения ошибок, некоторые из которых преобразуют сообщение, дополняя его избыточной информацией. Методы CRC (Cyclic Redundancy Codes) относятся к методам, которые оставляют без изменения исходный текст сообщения, добавляя контрольную сумму в конец. Код Хэминга добавляет биты четности в места байта, соответствующие степеням двойки

2. Необходимость использования сложных алгоритмов.

Рассмотрим предыдущий пример в ситуации, когда ошибка не может быть обнаружена:

Сообщение 06 23 04
Сообщение с контрольной суммой 06 23 04 33
Сообщение после передачи 06 27 04 37

Вероятность возникновения такой ошибки - 1/256. Для улучшения детекции ошибок можно перейти от 8-битной контрольной суммы к 16-битной, т.е. суммируя по модулю 65536. Это, очевидно, уменьшит вероятность пропуска ошибки до 1/65536. Но в данном примере увеличение длины контрольной суммы не позволит отловить ошибку. Происходит это в результате того, что при использовании в качестве контрольной функции операции сложения, почти каждый байт исходного сообщения влияет только на один байт контрольной суммы, вне зависимости от ее длины. Поэтому, помимо длины контрольной суммы, обращают внимание на такой фактор как хаотичность: формула должна позволять любому байту сообщения изменять любое количество бит контрольной суммы.

3. Основная идея алгоритмов.

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

4. Полиномиальная арифметика.

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

В связи с алгоритмами CRC часто можно встретить термин "полиномиальный". Говорят, что данный CRC алгоритм использует некий полином, и.т.п. И, вообще, говорят, что CRC алгоритмы используют полиномиальную арифметику. Что же это такое?

Делимое, делитель, частное и остаток рассматриваются не как положительные целые, а как полиномы с двоичными коэффициентами. То есть число записывается в виде двоичной строки, биты которой служат коэффициентами полинома. Например числу 23 (010111b) отвечает полином:

Мы можем осуществлять арифметические операции, понимая их как операции над полиномами. Например, умножим 13 (01101b) на 11 (01011b):

Для того, чтобы получить в ответе 143, мы должны в качестве x взять 2 и привести коэффициенты к двоичным, перенеся 1 из 3*x^3 в старшие разряды. Получаем:

Это обычная арифметика, просто основание системы счисления здесь выписано явно. Суть в том, что если мы не знаем х, то мы не можем производить переносы. Мы не знаем, что 3*x^3 это то x^4+x^3, потому что мы не знаем, что х = 2. В полиномиальной арифметике отношения между коэффициентами не определены, и коэффициенты при разных степенях полностью изолированы.

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

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =

(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =

x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 =

x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

В дальнейшем мы не будем упоминать полиномиальное представление, поскольку это может только усложнить изложение, и будем говорить об эквивалентной системе, назывемой "двоичная арифметика без переноса".

5. Двоичная арифметика без переноса.

Как нетрудно заметить с отменой переноса исчезают и различия между сложением и вычитанием. Для каждой позиции есть 4 варианта:

То есть, фактически, сложение и вычитание в этой арифметике эквивалентны операции XOR, которая является обратной самой себе, и это очень удобно.

Объединение сложения и вычитания приводит также к исчезновению строгого отношения порядка. Действительно, то что 1010b больше чем 10b остается верным, но уже нет причин полагать, что 1010b больше чем 1001b. Поэтому вводится слабое отношение порядка: число X больше числа Y если номер позиции старшей 1-ы числа X больше номера позиции старшей 1-ы числа Y ( этот номер, отсчитываемый с 0, называется длиной числа ). Умножение и деление выполняются по обычным схемам с учетом новых операций сложения и вычитания.

Полезно ввести понятия кратности и делимости. Будем говорить, что число A кратно числу B ( или A делится на B), если A можно получить складывая (XOR) результаты различных сдвигов ( влево) числа B. Например, 0111010110b кратно 011b:

Однако 0111010111b нельзя составить из сдвигов 011b, поэтому говорят, что 0111010111b не делится на 011b.

6. Код Хэминга.

Теперь, когда построена арифметика, мы можем приступить к изложению идеи алгоритма.

Закодируем очередные 4 бита вектора A (a3 a2 a1 a0)

Имеем матрицу M, состоящую из трех строк Str1 Str2 Str2

Str1=00001111

Str2=00110011

Str3=01010101

Заметим, что в столбцах стоят двоичные числа

Строим 7 бит B. Записываем в B0 B1 B2 B4 соответственно A0 A1 A2 A3 биты данных. Остальные биты - исходя из условия M*B=0. Расчет произведения Srti на B удобно произиодить с помощью команды Test. Далее по биту четности определяем норму скалярного произведения те если он 0 (JPE-соотв переход) то и произведение i го столбца на B равно 0

Проделав это вручную (сложение - XOR умножение - And или Test) имеем

b3=a0+a1+a2

b5=a0+a1+a3

b6=A0+a2+a3

Далее рассмотрим декодирование: При приеме 7 бит провряем на ошибку умножением. Если B=B+E , E= (e6 e5 e4 e3 e2 e1 e0) вектор ошибки то, очевидно, M*e<>0 Но если ошибка в одном бите из 7 (а нам важны только 0,1,2,4 й биты)то ее можно исправить по значениям

Rez1:=Srt1*B=Str1*E

Rez2:=Srt1*B=Str2*E

Rez3:=Srt1*B=Str3*E

Имеем:

неверен B0 (e0=1) при rez1=1 Rez2=1 Rez3=1

неверен B1 (e1=1) при rez1=1 Rez2=1 Rez3=0

неверен B2 (e2=1) при rez1=1 Rez2=0 Rez3=1

неверен B4 (e4=1) при rez1=0 Rez2=1 Rez3=1

Инвертируем соответствующий бит и в биты результата A A0 A1 A2 A3 запишем B0 B1 B2 B4.

Существуют различные разновидности алгоритма Хэминга. Рапример из одного байта добавкой разных комбинаций получают 12 бит (а не 14) и снова один бит можно восстановить. Идея алгоритма понятна из этого примера, вариации оставлены на рассмотрение читателю.



Заработок в интернет постоянно и регулярно платят