![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Код Хемминга
Код Хемминга исправляет однократные ошибки. Опознаватель кода Хемминга строится так, чтобы полученный при проверках результат r 1, r 2, …, rn - k прямо указывал бы номер искаженного разряда. Для этого проверочные символы должны находиться на номерах позиций, которые выражаются степенью двойки (20, 21, 22, …, 2r-1). Таким образом, если нумеровать позиции слева направо, то контрольные символы должны находиться на первой, второй, четвертой и т. д. позициях. Результат первой проверки дает цифру младшего разряда синдрома в двоичной записи. Если младший разряд r 1 опознавателя содержит 1 (т.е. результат первой проверки равен 1), то искажение должно быть в одной из нечетных позиций кодовой комбинации. Следовательно, первое уравнение проверки должно содержать символы с нечетными номерами а 1, а 3, а 5, а 7 и т.д. (таблица 2).
Таблица 2 Символы разрядов опознавателя
Аналогично, во второе уравнение проверки должны входить символы, содержащие в двоичной записи номера единицы во втором разряде: а 2, а 3, а 6, а 7 и т.д. При третьей проверке должны проверяться символы а 4, а 5, а 6, а 7 и т.д.
Тогда номер позиции ошибочного символа:
a ош.= r 4× 23+ r 3× 22+ r 2× 21+ r 1× 20
С целью упрощения операций кодирования и декодирования проверочные символы размещаются так, чтобы каждый из них включался бы в минимальное число проверок. Удобно размещать контрольные символы на позициях, номера которых встречаются только в одной из проверок: 1, 2, 4, 8, …. Следовательно, в кодовой комбинации символы а 1, а 2, а 4, а 8, … должны быть проверочными, а символы а 3, а 5, а 6, а 7, …- информационными. Так как значения информационных символов заранее известны, то значения проверочных символов должны быть такими, чтобы сумма единиц в каждой проверочной группе являлась четным числом. Представим в качестве примера простую двоичную комбинацию 10011 кодом Хемминга (k =5, t =1). Из соотношения Используя уравнение проверок вычислим значения проверочных символов
a 1= a 3 a 2= a 3 a 4= a 5 a 8= a 9
Следовательно, будет передана комбинация 101100111(а 1 – а 9). Если при передаче информации произошла одиночная ошибка и была принята, например, комбинация 101101111, то декодирование дает следующий результат:
r 1= a 1 r 2= a 2 r 3= a 4 r 4= a 8
Тогда a ош.= r 4× 23+ r 3× 22+ r 2× 21+ r 1× 20 =1× 22+1× 21 = 6, т.е. искажен элемент с порядковым номером 6, его надо изменить на противоположный, т.е. на 0. Лекция 19. Кодирование информации циклическими кодами План: 1. Циклические коды 2. Полиноминальное представление циклических кодов 3. Порождающий многочлен циклического кода 4. Разделимые и неразделимые циклические коды 5. Матричное представление циклических кодов 6. Выбор образующего полинома
19.1.Циклические коды. Основные свойства и способы построения. Циклические коды получили широкое применение благодаря их эффективности при обнаружении и исправлении ошибок. Схемы кодирующих и декодирующих устройств для этих кодов чрезвычайно просты и строятся на основе обычных регистров сдвига. Название кода произошло от свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем циклической перестановки символов исходной комбинации, принадлежащей и этому же коду. Например, если комбинация a0 a1 a2 ….an-1 является разрешенной комбинацией циклического кода, то комбинация an-1 a0 a1 a2 ….an-2 тоже принадлежит этому коду.
|