Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика)




НазваниеКонспект лекций для студентов заочной формы обучения направления 080201 (Информатика)
страница11/11
Дата публикации23.05.2013
Размер0.94 Mb.
ТипКонспект
uchebilka.ru > Информатика > Конспект
1   2   3   4   5   6   7   8   9   10   11
^

3.10 Код Хэмминга



Наиболее распространенным систематическим линейным блочным кодом является код Хэмминга. К нему относятся коды с минимальным кодовым расстоянием dmin=3, способные исправлять однократные ошибки.
При передаче кодового слова по каналу связи возможно возникновение однократной ошибки в любом из его элементов. Количество таких ситуаций . Таким образом, для того чтобы определить место возникновения ошибки, количество комбинаций проверочных элементов 2r должно быть не меньше количества возможных ошибочных ситуаций в коде плюс ситуация, когда ошибка не возникает, т. е. должно выполняться неравенство
2r n+1. (3.16)
Из этого неравенства следует минимальное соотношение проверочных и информационных разрядов, необходимое для исправления однократных ошибок
2r -1=n. (3.17)

Для расчёта основных параметров кода Хэмминга можно задать количество проверочных элементов r, тогда длина кодовых слов n ≤ 2r-1, а количество информационных элементов k=n-r. Соотношения между r, n и k приведены в следующей таблице (табл. 3.3.)

Таблица 3.3

k

1

1

2

3

4

4

5

6

7

8

9

10

11

11

12

12

r

2

3

3

3

3

4

4

4

4

4

4

4

4

5

5

6

n

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18


Характерной особенностью проверочной матрицы кода с dmin=3 является то, что ее столбцы – различные ненулевые комбинации длины r.

Хэммингом предложено располагать столбцы проверочной матрицы так, чтобы i-й столбец матрицы и номер разряда кодовой комбинации отвечали двоичному представлению числа i. Тогда синдром исправления однократных ошибок будет двоичным представлением номера разряда, в котором произошла ошибка. Для этого проверочные разряды должны находиться не в правой части кодового слова, а в позициях, номера которых являются степенью двойки, т. е. 20, 21, 22, …, 2r-1.
Например, для r=3 проверочная матрица кода Хэмминга имеет вид

.

Для данного линейного блочного (4, 7)-кода первый, второй, четвертый разряды (u1, u2, u4) будут проверочными, а третий, пятый, шестой и седьмой разряды (u3, u5, u6, u7) – символами сообщения в том же порядке, что и кодируемое сообщение, т.е (m1, m2, m3, m4) соответственно.
Таким образом, для (k, n)-кода Хэмминга в каждом кодовом слове u=(u1, u2, u3, u4, …, u8, …, un), r=n-k битов с номерами степени 2 являются проверочными, а остальные – битами сообщения, т.е. кодирование осуществляется так:
E(m1, m2, …, mk)= (u1, u2, …, un)=(r1, r2, m1, r3, m2, m3, m4, r4, m5, m6, …, mk).
Проверочная матрица (k, n)-кода Хэмминга составляется из n=2r-1 строк и r столбцов и представляет собой двоичные комбинации числа i, где iномер столбца проверочной матрицы (разряда кодовой комбинации).
Например, для r=2, 3, 4 проверочные матрицы кода Хэмминга имеют вид

, , .
Синдром, определяющий систему проверочных уравнений кода, находится из уравнения u=0.

Например, для r=3 система проверочных уравнений будет следующей:

Отсюда проверочные разряды (контрольные суммы) находятся как

Чтобы закодировать сообщение m, в качестве ui, где i не равно степени 2, берутся соответствующие биты сообщения, а проверочные разряды с индексами степени 2 находятся из системы проверочных уравнений кода. В каждое уравнение системы входит только одна контрольная сумма.
Пример 1 Закодируем сообщение m=(0 1 1 1) (4, 7)-кодом Хэмминга.
Кодовым словом данного кода будет последовательность (u1 u2 0 u4 1 1 1), где u1, u2, u4 – контрольные суммы r1, r2, r3.

Из системы проверочных уравнений находим контрольные суммы:
r1= u1= u3+u5+u7= m1+m2+m4=0+1+1=0,

r2= u2= u3+u6+u7= m1+m3+m4=0+1+1=0,

r3= u4= u5+u6+u7= m2+m3+m4=1+1+1=1.
Таким образом, кодовым словом будет последовательность (0001111).
Декодирование кода Хэмминга происходит по следующей схеме. Определяется синдром принятой последовательности S=y, где - транспонированная проверочная матрица кода; y – принятый вектор. Если синдром равен нулевому вектору, то считается, что слово передано без ошибок, иначе значение синдрома соответствует двоичному представлению номера разряда, в котором произошла ошибка. В этом случае нужно изменить значение в ошибочном разряде, считая разряды слева направо, начиная с 1.
Пример 2 Сообщение кодируется (4, 7)-кодом Хэмминга. Принята последовательность y=(0011111). Декодируем принятый вектор.
Определяем синдром принятого вектора:

y = (0011111) = (0 1 1)=310,

т. е. ошибка произошла в третьем разряде.
Исправляем ошибку, изменяя значение в третьем бите
(0011111)  (0001111).
Переданное сообщение декодируется как
D(u1, u2, u3, u4, u5, u6, u7)=D(0001111)=(0111).

Порождающей матрицей (k, n)-кода Хэмминга является матрица (k×n), в которой столбцы с номерами не степенями 2 образуют единичную подматрицу, а остальные столбцы соответствуют проверочным уравнениям кода. Такая матрица при кодировании будет копировать биты сообщения в позиции, не степени 2, и заполнять другие позиции кода согласно системе вычисления контрольных разрядов.
Пример 3 Система проверочных уравнений (4, 7)-кода Хэмминга следующая:
r1= u1 = u3+u5+u7 = m1+m2+m4,

r2= u2 = u3+u6+u7 = m1+m3+m4,

r3= u4 = u5+u6+u7 = m2+m3+m4.
Соответственно порождающая матрица данного кода имеет вид

.

^ КОНТРОЛЬНЫЕ ВОПРОСЫ


  1. Какие коды относятся к помехоустойчивым? Какими общими свойствами они характеризуются?

  2. Для чего в помехоустойчивые коды вводится избыточность?

  3. Какие существуют классы помехоустойчивых кодов?

  4. Какие коды относятся к блочным помехоустойчивым кодам? В каких случаях их целесообразно использовать?

  5. Как определяются операции сложения и умножения в поле двоичных символов GF(2) (операции сложения и умножения по модулю 2)?

  6. Какие коды называются линейными блочными кодами? Какие коды обладают свойством систематичности?

  7. В чем заключается кодирование с проверкой на четность? Какова избыточность такого кода? В чем достоинства и недостатки этого кода?

  8. Какой канал передачи информации описывается моделью двоичного симметричного канала?

  9. В чем заключается процедура обнаружения и исправления ошибок итеративным кодом? Каковы достоинства и недостатки данного кода?

  10. Какие существуют способы задания линейных блочных кодов? Из каких основных частей строится кодовое слово линейного блочного систематического кода?

  11. Что такое система проверочных уравнений линейного блочного кода?

  12. Что такое порождающая матрица линейного блочного кода? Каковы ее свойства? Какова структура порождающей матрицы?

  13. Как, используя порождающую матрицу, построить систему проверочных уравнений линейного блочного кода?

  14. Что такое проверочная матрица линейного блочного кода? Каковы ее свойства?

  15. Какова структура проверочной матрицы линейного блочного кода? Какая часть проверочной матрицы соответствует информационным символам, а какая – проверочным?

  16. Как, используя проверочную матрицу, построить систему проверочных уравнений линейного блочного кода?

  17. Как описывается вектор ошибок в двоичном канале связи? В чем заключается задача декодирования переданного кодового слова?

  18. Что такое кодовый синдром линейного блочного кода? Как он определяется?

  19. Каким свойством характеризуется синдром принятого вектора? В каких случаях кодовый синдром не позволяет обнаружить ошибки в переданной последовательности?

  20. Как с помощью кодового синдрома обнаруживаются и исправляются ошибки линейным блочным кодом?

  21. Как определяются вес и расстояние Хэмминга для двоичных последовательностей?

  22. Что такое минимальное кодовое расстояние Хэмминга линейного блочного кода? Как оно определяется?

  23. Каково необходимое и достаточное условие обнаружения линейным блочным кодом ошибок заданной кратности?

  24. Каково необходимое и достаточное условие исправления линейным блочным кодом ошибок заданной кратности?

  25. Каковы необходимое и достаточное условия существования помехоустойчивого кода?

  26. Как определяется минимальное количество проверочных символов для линейного блочного кода с заданными характеристиками?

  27. Как построить порождающую матрицу линейного блочного кода с заданными характеристиками?

  28. Какие линейные блочные коды называются кодами Хэмминга?

  29. Как определяется количество информационных и проверочных символов для кода Хэмминга?

  30. Как строятся кодовые слова кода Хэмминга?

  31. Как составляется проверочная матрица двоичного кода Хэмминга?

  32. Чему соответствует значение синдрома при использовании кода Хэмминга?

  33. Как происходит декодирование кода Хэмминга?

  34. Как строится порождающая матрица кода Хэмминга?



Список использованной и рекомендуемой литературы


  1. Shannon C. E. A Mathematical Theory of Communication. - Reprinted with corrections from The Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, July, October, 1948. - http://www.compression.ru/download/ti.html.

  2. Лидовский В. В. Теория информации: Уч. пособие. - М.: Компания Спутник+, 2004. - 111 с. - http://www.compression.ru/download/ti.html, http://www.intuit.ru/department/calculate/infotheory.

  3. Шульгин В. И. Основы теории передачи информации. Ч. I. Экономное кодирование: Учебное пособие. – Харьков: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2002. - 100 с. - http://k501.xai.edu.ua/posobiya.php.

  4. Шульгин В. И. Основы теории передачи информации. Ч. II. Помехоустойчивое кодирование: Учебное пособие. – Харьков: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2002. – 90 с. - http://k501.xai.edu.ua/posobiya.php.

  5. Жураковський Ю. П., Полторак В. П. Теорія інформації та кодування: Підручник. – К.: Вища шк., 2002. – 90 с.

  6. Тулякова Н. О. Теория информации: Дистанционный курс. – Суми: СумДУ, 2006.

  7. Методичні вказівки до виконання контрольної роботи з дисципліни “Теорія інформації”/ Укладач: Н.О. Тулякова. – Суми: Вид-во СумДУ, 2007.-59 с.

  8. Яглом А., Яглом И. Вероятность и информация – М.: Наука, 1973.

  9. Потапов В. Н. Теория информации. Кодирование дискретных вероятностных источников: Уч. Пособие. – Новосибирск: Новосибирский гос. ун-т, 1999. - http://www.plib.ru/library/book/15591.html.

  10. Хемминг Р. В. Теория информации и теория кодирования. – М.: “Радио и связь”, 1983.

  11. Стратонович Р. Л. Теория информации. – М: Изд-во “Сов. Радио”, 1975.

  12. Чисар И., Кернер Я. Теория информации. – М.: Мир, 1985.

  13. Кузьмин И. В. Основы теории информации и кодирования. – Минск: Вышэйш. шк., 1986.

  14. Блейхер Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986.

  15. Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 1976.

1 Шеннон К. Работы по теории информации и кибернетике. – М.: Издательство иностранной литературы, 1963.

2 Яглом А., Яглом И. Вероятность и информация – М.: Наука, 1973.

i


1   2   3   4   5   6   7   8   9   10   11

Похожие:

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций 2007 Экология. Конспект лекций. Для студентов специальностей...
Экология. Конспект лекций. Для студентов специальностей 080201 «Информатика», 090220 «Оборудование химических производств и предприятий...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по дисциплине “политэкономия” для студентов 050107 заочной формы обучения
Конспект лекций по дисциплине “Политэкономия” для студентов 050107 заочной формы обучения/ Разраб. Овечкина Е. А. Северодонецк, 2000....

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций в схемах по дисциплине «организация труда менеджера»
Конспект лекций в схемах по дисциплине «Организация труда менеджера» (для студентов (для студентов 4 курса дневной и 3 курса заочной...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconХарьковская национальная академия городского хозяйства
Конспект лекций для студентов 1-го курса дневной и заочной формы обучения образовательно-квалификационного уровня бакалавр, направления...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций в схемах по дисциплине «управление персоналом»
Конспект лекций в схемах по дисциплине «Управление персоналом» (для студентов 5 курса направления подготовки 0502 “Менеджмент” специальности...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по курсу Начертательная геометрия
Конспект лекций по курсу начертательная геометрия (для студентов заочной формы обучения всех специальностей академии). Сост. Лусь...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по курсу «Организация производства»
Конспект лекций по курсу «Организация производства» (для студентов и слушателей заочной формы обучения фпоизо специальностей 050100...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций для студентов бакалавратуры 0902 «Инженерная механика» заочной формы обучения
Сила давления жидкости на криволинейные цилиндрические поверхности

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconМетодические указания для выполнения лабораторных, самостоятельных...
«Информатика и компьютерная техника» (для студентов 1-го и 2-го курсов заочной формы обучения образовательно-квалификационного уровня...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconА. Г. Шкаев твердотельная электроника
Конспект лекций предназначен для студентов очной, очно-заочной и заочной форм обучения

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<