 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Самокорректирующие коды (коды Хемминга). Примеры построения кодов Хэмминга
Краткие теоретические сведения
(см.лекции)
Задание 1
Разработать самокорректирующийся код (код Хэмминга) для бинарных слов длины m=10 и привести примеры декодирования искаженных элементарных кодов (источник помех может исказить не более одной позиции элементарного кода).
Р Е Ш Е Н И Е
1 Определим длину l элементарных кодов
2k–1 ≤ l, а 2k ³ l+1, где l = m + k (по условию задачи m = 10)
Оба неравенства выполняются для k = 4 (8 ≤ 13, 16 ³ 14), т.е для 10 информационных членов понадобятся 4 контрольных бита в элементарных кодах, общая длина которых будет равна 14.
2 Контрольные биты элементарного кода будут вычисляться так:
Ряд 1 b1 = b3+ b5 + b7 + b9 + b11 + b13 (mod 2),
Ряд 2 b2 = b3+ b6 + b7 + b10 + b11 (mod 2
Ряд 3 b4= b5+ b6 + b7 + b12 + b13 (mod 2),
Ряд 4 b8= b9+ b10 + b11 + b12 + b13 (mod 2),
3 Пример кодирования исходного элементарного сообщения (длина 10 позиций т.е m = 10)
В таблице ниже приведен пример определения контрольных бит элементарного кода (контрольный бит равен 1, если число единиц соответствующего ему ряда нечетно и 0 – если четно). Значения контрольных бит в таблице выделены курсивом.
| Номера позиций | ||||||||||||||
| Код сообщения | ||||||||||||||
| Ряд 1 | ||||||||||||||
| Ряд 2 | ||||||||||||||
| Ряд 3 | ||||||||||||||
| Ряд 4 |
4 Пример корректировки искаженного в одной позиции элементарного кода (пусть в процессе передачи по каналу связи элементарный код, представленный в строке 2 предыдущей таблицы искажен в позиции 5 вместо 1 получен 0)
| Номера позиций | Si | ||||||||||||||
| Код сообщения | |||||||||||||||
| Ряд 1 | 1= S1 | ||||||||||||||
| Ряд 2 | 0= S2 | ||||||||||||||
| Ряд 3 | 1= S3 | ||||||||||||||
| Ряд 4 | 0= S4 |
В результате подсчета кода ошибки получен следующий результат:
S = S4 S3S2 S1 = 0101 (в бинарном представлении), что соответствует 5 (т.е. ошибка в позиции 5 и для корректировки нужно 0 (поз. 5) заменить на 1). Результат восстановления приведен ниже.
| Номера позиций | ||||||||||||||
| Код полученного сообщения | ||||||||||||||
| Код сообщения после коррекции |
| Сообщение (удалены контрольные члены) |
Варианты задания 1 темы 7 для самостоятельной подготовки
Таблица вариантов к заданию 1
| Вариант | m |
ЛИТЕРАТУРА
1.Мао В. Современная криптография: теория и практика.: Пер. с англ. – М.: изд. дом «Вильямс», 2005. –768с.:ил.
2.Масленников М. Практическая криптография. –СПб.: БХВ-Петербург, 2003.—464с.:ил.
3 Нечаев В. Элементы криптографии. Основы теории защиты информации: Учеб. пособие для вузов / Под ред. В.А. Садовничего.– 2-е изд стер. – М.: Высш.шк., 2004. – 424с.
4 Яблонский С. Введение в дискретную математику: Учеб. пособие для вузов / Под ред. В.А. Садовничего.– 3-е изд стер. – М.: Высш.шк., 2002. –384с.
5.Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. – М.: изд. дом «Вильямс», 2004. –960с.:ил.
Теория алгоритмов:: Методические указания для самостоятельной подготовки к контролю знаний студентов заочного отделения направления подготовки 6.050101 «Компьютерные науки» / Сост. М.П.Богдан. – Краматорск: ДГМА, 2012. – 36 с.
Автор: Михаил Петрович Богдан,
Редактор саморедактирование
----------------------------------------------------------------------------------
ДДМА. 84313, Краматорськ, вул. Шкадінова, 72
Поиск по сайту: