АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Самокорректирующие коды (коды Хемминга). Примеры построения кодов Хэмминга

Читайте также:
  1. IV. СХЕМА ПОСТРОЕНИЯ КОМПЛЕКСА ОБЩЕРАЗВИВАЮЩИХ УПРАЖНЕНИЙ
  2. Агрегатный индекс цен: особенности построения с учетом разных весов
  3. Алгоритм вычисления кодов Шеннона — Фано
  4. Алгоритмы диагностирования и методы их построения
  5. АНАЛИТИЧЕСКИЙ МЕТОД ПОСТРОЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
  6. Базовая модель структурного построения производственных систем
  7. БАНКОВСКАЯ СИСТЕМА И МОДЕЛИ ЕЕ ПОСТРОЕНИЯ
  8. Бюджетная система Республики Беларусь и принципы ее построения
  9. Вопрос 2. Бюджетная система Российской Федерации и принципы ее построения.
  10. Вопрос 2. Принципы построения налоговой систем
  11. Д) РОЛЬ СИНТАКСИЧЕСКИХ СВЯЗЕЙ И ХАРАКТЕРА СИНТАКСИЧЕСКОГО ПОСТРОЕНИЯ ДЛЯ РИТМА ПРОЗЫ
  12. Далее приводится пример построения сетевого графа и расчет его временных параметров.

Краткие теоретические сведения

(см.лекции)

Задание 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

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)