КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Код Хэмминга
Код Хэмминга, являющийся групповым (n,k) кодом, с минимальным расстоянием d=3 позволяет обнаруживать и исправлять однократные ошибки. Для построения кода Хэмминга используется матрица H. , где Ak- транспонированная подматрица, En-k - единичная подматрица порядка n-k. Если Х - исходная последовательность, то произведение Х·Н=0. Пусть E - вектор ошибок. Тогда (Х+Е)·Н = Х·Н+Е·Н = 0+Е·Н=E·H - синдром или корректор, который позволяет обнаружить и исправить ошибки. Контрольные символы e1 ,e2 ,...,er образуются из информационных символов, путем линейной комбинации , где аj={0,1} - коэффициенты, взятые из подматрицы A матрицы H. Рассмотрим Построение кода Хэмминга для k=4 символам. Число контрольных символов r=n-k можно определить по неравенству Хэмминга для однократной ошибки. Но так, как нам известно, только исходное число символов k, то проще вычислить по эмпирической формуле , (5.2) где [.] - означает округление до большего ближайшего целого значения. Вычислим для k=4 . Получим код (n,k)=(7,4); n=7; k=4; r=n-k=3; d=3. Построим матрицу H. Контрольные символы ej определим по формуле . Например, . Для простоты оставляем только слагаемые с единичными коэффициентами. В результате получим систему линейных уравнений, с помощью которых вычисляются контрольные разряды. Каждый контрольный разряд является как бы дополнением для определенных информационных разрядов для проверки на четность. При декодировании вычисляем корректор K=k4k2k1 Если корректор равен нулю, следовательно, ошибок нет. Если корректор не равен нулю, то местоположение вектор-столбца матрицы H, совпадающего с вычисленным корректором, указывает место ошибки. При передаче может возникнуть двойная и более ошибка. Корректор также не будет равен нулю. В этом случае произойдет исправление случайного символа и нами будет принят неверный код. Для исключения такого автоматического исправления вводится еще один символ для проверки всей комбинации на четность. Кодовое расстояние d=4. Тогда матрица H будет иметь вид
Пример 5.4. Дана 1101 - исходная комбинация (k=4). Закодировать ее в коде Хэмминга. По формуле (5.2) находим число контрольных символов r=3. Берем регистр из 7 ячеек памяти. Размещаем исходную комбинацию в ячейках 3,5,6,7. 1 2 3 4 5 6 7 * * 1 * 1 0 1 Находим контрольные символы е4 = 5 + 6 + 7 = 1 + 0 + 1 = 0 е2 = 3 + 6 + 7 = 1 + 0 + 1 = 0 е1 = 3 + 5 + 7 = 1 + 1 + 1 = 1 Закодированная комбинация будет иметь вид 1 2 3 4 5 6 7 1 0 1 0 1 0 1 Допустим, что при передаче возникла ошибка, и мы приняли неверную комбинацию 1 2 3 4 5 6 7 1 0 1 0 1 1 1 Проверяем ее к 4 = 4 + 5 + 6 + 7 = 0 + 1 + 1 + 1 = 1 к2 = 2 + 3 + 6 + 7 = 0 + 1 + 1 + 1 = 1 к1 = 1 + 3 + 5 + 7 = 1 + 1 + 1 + 1 + 0 K= - в шестом разряде ошибка. Если бы нам понадобилось построить код и для проверки двойных ошибок, необходимо было бы ввести еще один дополнительный нулевой разряд. Получим следующий код 0 1 2 3 4 5 6 7 0 1 0 1 0 1 0 1 При передаче и возникновении ошибки код будет иметь вид 0 1 2 3 4 5 6 7 0 1 0 1 0 1 1 1 Проверка в этом случае показала бы, что корректор K=110, а проверка всей комбинации на четность E0 = 0+1+0+1+0+1+1+1=1. Это указывает на одиночную ошибку. Допускается автоматическое исправление ошибки. Существует следующий алгоритм декодирования кода Хэмминга с d=4
Код (7,4) является минимально возможным кодом с достаточно большой избыточностью. Эффективность кода (k/n) растет с увеличением длины кода
Техническая реализация кода Хэмминга Схемы кодирования и декодирования представлены на рис.5.4 и 5.5 соответственно. Устройство кодирования строится на регистре в n разрядов и r сумматоров “по модулю 2”. В ячейки 3, 5, 6, 7 вводятся исходные символы. В следующем такте формируются проверочные разряды. Закодированная комбинация может быть передана в линию последовательно или параллельно. Рис.5.4. Схема кодирования Рис.5.5. Схема декодирования
Дата добавления: 2015-07-02; Просмотров: 659; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |