План-конспект урока по теме Кодировки, позволяющие обнаруживать или исправлять ошибки

Этапы урока

Содержание этапов урока

1. Организационный момент.

Цели для преподавателя:

- создать условия для возникновения у обучающихся внутренней потребности включения в учебную деятельность;

- способствовать повышению мотивации учения.

Цели для обучающихся:

- включиться в учебную деятельность;

- подготовиться к восприятию нового учебного материала.

Цели этапа занятия достигаются посредством:

-объявления темы занятия и постановки общих целей;

- разъяснения роли изучаемого содержания в процессе формирования конкретных общих и профессиональных компетенций;

- раскрытия значения изучаемого содержания для будущей профессиональной деятельности;

1. Вводный инструктаж

1.1. Проверка наличия обучающихся. Повторение техники безопасности в кабинете информатики.

Начинаем занятие. Отметим отсутствующих на занятие и проверим вашу готовность к занятию на наличие тетрадей.

1.2. Целевая установка на урок.

Сегодня у нас новая тема «Кодировки, позволяющие обнаруживать или исправлять ошибки (код Хемминга и код CRC (контрольная сумма))», запишите тему занятия в тетрадях.

Обучающиеся записывают тему занятия.

Эта тема имеет большое профессиональное значение. Она направлена на формирование такой компетенции как «организовывать собственную деятельность выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество».

2. Изучение нового учебного материала (способов действий).

Цели для преподавателя:

- познакомиться с кодировкой

- рассмотреть код Хемминга и код CRC

- познакомиться с кодом исправления ошибок

Цели для обучающихся:

- рассмотреть сервисы канального уровня

- познакомиться с основными задачами канального уровня

-рассмотреть основные способы исправления ошибок

Цели этапа занятия достигаются посредством:

- обеспечения понимания планируемого результата деятельности, основных путей его достижения;

- определения критериев, позволяющих обучающимся самостоятельно определять степень достижения запланированного результата;

- организации активной самостоятельной деятельности обучающихся по написанию лекции во время занятия.

2. Теоретическая часть.

Коды с исправлением ошибок.

Для надежной передачи кодов было предложено два основных метода. Первый - внести избыточность в форме дополнительных битов в передаваемый блок данных так, чтобы, анализируя полученный блок, можно было бы указать, где возникли искажения. Это так называемые коды с исправлением ошибок. Второй метод - внести избыточность, но лишь настолько, чтобы, анализируя полученные данные, можно было сказать: есть в переданном блоке ошибки или нет. Это так называемые коды с обнаружением ошибок.
Пусть данные занимают m разрядов, и мы добавляем r избыточных, контрольных разрядов. Нам необходимо передать слово длины n = m+r, которое называют n-битовым кодословом. Пусть у нас есть два кодослова - 10001001 и 10110001. С помощью операции EXCLUSIVE OR легко определить число различных разрядов в двух кодословах. В данном случае таких разрядов 3. Количество разных битов в двух кодословах называется расстоянием Хемминга между этими словами. Поэтому, если два кодослова находятся на расстоянии d по Хеммингу, это значит, что надо преобразовать ровно d разрядов, чтобы преобразовать одно кодослово в другое.
В силу того, что избыточные контрольные разряды могут принимать только вполне определенные значения, то не все 2ⁿ кодовых слов возможны. Зная алгоритм установки контрольных разрядов, мы можем вычислить   минимальное расстояние по Хеммингу между двумя правильными кодословами.     
Способен код исправлять ошибки или только обнаруживать их - зависит от расстояния между кодословами по Хеммингу. Если мы хотим обнаруживать d ошибок, то необходимо, чтобы два кодослова отстояли друг от друга на расстоянии d+1. Тогда, если принятый код отстоит на расстоянии k
Простым примером кода с обнаружением одной ошибки является код с битом четности. Конструкция его такова: к исходному кодослову добавляется бит четности. Если число единиц в исходном кодослове четно, то значение этого бита - 0. Если нечетно, то - 1. Кодослова с битом четности имеют расстояние Хемминга 2, так как любая ошибка в одном бите породит ошибку четности. Однако, если возможны двойные ошибки, то бит четности проблему не решит.
Для примера кода с исправлением ошибки рассмотрим код, у которого есть только четыре правильных кодослова: 0000000000, 0000011111, 1111100000, 1111111111. Расстояние по Хеммингу у этого кода 5, следовательно, он может исправлять двойные ошибки. Если получатель получит слово 0000000111, то ясно, что исходное слово имело вид 0000011111. Однако, если допустимы тройные ошибки, то 0000000111 может означать 0000000000.
Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночных ошибок. Пусть у нас есть код из m бит сообщения и r контрольных бит. Каждое из 2ⁿ правильных сообщений имеет n неправильных кодослов на расстоянии 1.   Таким образом, с каждым из 2^m кодослов связано   n+1 кодослов. Так как общее число кодослов - 2ⁿ, то (n+1)2^m≤2, учитывая, что n=m+r, получаем:   (m+r+1) ≤ 2^r
Для заданного m эта формула задает минимальное число контрольных разрядов, необходимых для исправления единичных ошибок. Этот теоретический предел достижим при использовании метода, предложенного Хеммингом. Идея его в следующем:

• Разряды кодослова нумеруются слева направо, начиная с 1.

• Все биты, номера которых являются степенью 2 (1, 2, 4, 8, 16 и т.д.) - контрольные, остальные - биты сообщения.

• Каждый контрольный бит отвечает за четность группы битов, включая себя. Чтобы определить группу битов, за четность которой отвечает определенный контрольный бит, нужно представить номер позиции каждого бита по степеням двойки. Те биты, в номера которых входит степень двойки, равная номеру контрольного бита, и есть искомая группа. Например, 11=1+2+8, 39=1+2+4+32. Таким образом, бит в позиции 11 входит в группу, контролируемую битом в позиции 2.

Получив кодослово, получатель устанавливает специальный счетчик в ноль. Затем он проверят каждый контрольный бит на предмет правильности четности. Если четность нарушена, то порядковый номер этого бита заносится в счетчик. Если после этой проверки счетчик на нуле, то все в порядке. Если нет, то он содержит номер неправильного разряда. Например, если 1, 2, 8 - ошибочные контрольные разряды, то ошибка содержится в 11-м разряде, так как только он связан одновременно с этими контрольными разрядами.
Код Хемминга может исправлять только одиночные ошибки. Однако есть прием, который позволяет распространить идеи Хемминга на случай групповых ошибок. Пусть нам надо передать k кодослов. Расположим их в виде матрицы: одно слово - строка. Обычно передают слово за словом. Но мы поступим иначе, передадим слово длины k из первых разрядов всех слов, затем - вторых, и т.д. После приема всех слов матрица восстанавливается. Если мы хотим обнаруживать групповые ошибки размера k, то в каждой строке восстановленной матрицы будет не более одной ошибки. А с одиночными ошибками код Хемминга справится.

Коды с обнаружением ошибок.

Рассмотрение кодов, обнаруживающих ошибки, начнем с небольшого примера. Пусть у нас есть канал с одиночными ошибками с частотой 10^-6 на бит. Если мы хотим исправлять единичные ошибки при передаче блока в 1000 бит,   то нам потребуется 10 контрольных бит ((m+r+1) ≤ 2^rr, где m =1000; (1001+r) ≤ 2^rr, следовательно, r = 10).  
При передаче 1 Мбит данных потребуется 10 000 контрольных бит. В то же время для обнаружения единичной ошибки достаточно одного бита четности. Поэтому, если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1001 бит дополнительно или с повторной передачей 2002 бит, вместо 10000 бит в случае кода с исправлением ошибки.
Применение техники четности «в лоб» в случае групповых ошибок не даст нужного результата. Однако ее можно скорректировать. Пусть нам требуется передать n слов по k бит. Расположим их в виде матрицы n х k. Для каждого столбца вычислим бит четности и разместим его в дополнительной строке. Матрица затем передается по строкам. При получении матрица восстанавливается, и если хоть один бит нарушен, то весь блок передается повторно.

Этот метод позволяет обнаружить групповые ошибки длины n. Против групповых ошибок длины n+1 он бессилен. В общем случае вероятность правильной передачи при длине групповой ошибки n равна 2^-n. Поэтому на практике применяют другую технику, которая называется циклическим избыточным кодом   (Cyclic Redundancy Code), или CRC-кодом.  
CRC-коды построены на рассмотрении битовой строки как строки коэффициентов полинома. Битовую строку длины k рассматривают как коэффициенты полинома степени k-1. Самый левый бит строки - коэффициент при старшей степени. Например, строка 110001 представляет полином x⁵+x⁴+x⁰.
Использование полиномиальных кодов при передаче заключается в следующем. Отправитель и получатель заранее договариваются о конкретном генераторе полиномов G(x), у которых коэффициенты при старшем члене и при младшем члене должны быть равны 1. Пусть степень G(x) равна r. Для вычисления контрольной суммы блока из m бит должно быть r
Алгоритм вычисления контрольной суммы:
Здесь r - степень G(x).

1. Добавить r нулей в конец блока так, что он содержал m+r разрядов и соответствовал полиному x^r M(x).

1. Разделить по модулю 2 полином x^r M(x) на G(x).

1. Вычесть остаток (длина которого всегда не более r разрядов) из строки, соответствующей x^r M(x), по модулю 2. Результат и есть блок с контрольной суммой (назовем его Т(х)).  

Рисунок 3-7 показывает этот алгоритм для блока 1101011011 и G(x) = х⁴+х+1.

Рисунок 3-7. Расчет контрольной суммы для полиномиального кода



Данный метод позволяет обнаруживать одиночные ошибки. Групповые ошибки длины не более r. Нечетное число отдельных ошибок. Существует три международных стандарта на вид G(x):

• CRC-12 = x¹²+x¹¹+x³+x²+x+1

• CRC-16 = x¹⁶+x¹⁵+x²+1

• CRC-CCITT = x¹⁶+x¹²+x⁵+1

CRC-12 используется для передачи символов из 6 разрядов. Два остальных - для 8-разрядных. CRC-16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечетное число изолированных ошибок с вероятностью 99,997%.

4. Задание на дом.

Цели для преподавателя:

- провести анализ и оценку успешности достижения цели урока, перспектив последующей работы;

- мобилизовать обучающихся на рефлексию результатов учебной деятельности;

- поставить цели самостоятельной работы для обучающихся (что должны сделать обучающиеся в ходе выполнения домашнего задания).

Цели для обучающихся:

- уяснить цели и содержание домашнего задания.

Цели этапа урока достигаются посредством:

- достижения открытости обучающихся в осмыслении своих действий и самооценки;

- определения для обучающихся содержания и объема домашнего задания.

4.Заключительная часть. Подведение итогов, выставление отметок.

Сегодня мы с вами: познакомились с кодировкой, рассмотрели код Хемминга и код CRC, познакомилисьс кодом исправления ошибок

4.1. Определение задания на дом.

Задание. К следующему занятию выучите лекцию. Составить инструкционную технологическую карту.