Самостоятельная работа №1 "Помехоустойчивые коды", 11 класс

1. Информация и информационные процессы

1. 
   Помехоустойчивые коды

1. Для передачи данных используется 8-битовый код, в котором младшие 7 бит – это ASCII-код символа, а старший бит – контрольный бит чётности. Определите коды символов, которые были переданы без ошибок, а ошибочные замените нулями. Используя таблицу ASCII (A – 65, B – 66, …, Z - 90), определите правильно принятые символы. Попытайтесь восстановить известное английское слово, связанное с информатикой, которое пытались передать (запишите после кода).

11010100 01010111 11001001 11010100 11010100 01000101 11010010

11010111 11001001 11001110 01000100 01001111 11010111 01010011

01000111 01001111 11001111 11000111 11001100 11000101

11011001 01000001 01001110 11000100 11000101 11011000

1. По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова, приведённые в задании. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Какое из перечисленных кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?
   А – 11111, Б – 11000, В – 00100, Г – ?

1) 00000 2) 00011 3) 11100 4) не подходит ни одно из указанных слов

А – 00110, Б – 11000, В – 10011, Г – ?

1) 01101 2) 01001 3) 00011 4) не подходит ни одно из указанных слов

А – 11100, Б – 00110, В – 01011, Г – ?

1) 11001 2) 10010 3) 10001 4) не подходит ни одно из указанных слов

А – 01101, Б – 00110, В – 10001, Г – ?

1) 11111 2) 11010 3) 01000 4) не подходит ни одно из указанных слов

1. 7-битовый код Хэмминга для 4-битовых данных (с 3-мя контрольными битами) строится следующим образом. Биты, номера которых равны степеням двойки – контрольные (это биты 1, 2 и 4, выделенные жёлтым фоном), остальные биты – биты данных:

Номера остальных битов раскладываются на сумму степеней двойки, например: 5 = 4 + 1. Разложение справа даёт номера контрольных битов, которые проверяют этот бит данных. Так 5-й бит проверяется контрольными битами 1 и 4.

Значение контрольного бита вычисляется как бит чётности для всех битов, которые он контролирует. Например, бит 1 контролирует биты 3, 5 и 7 (выделены голубым фоном, в их разложении есть 1). Пусть четверка данных – это 1100:

Тогда контрольный бит 1 – это бит чётности для цепочки 110, он равен 0, поскольку число единиц в блоке – чётное.

Задание: используй код Хэмминга, постройте кодовые слова для заданных данных.

Постройте таблицу кодов Хэмминга для всех двоичных кодов, соответствующих числам от 0 до 15. Для этого используйте электронные таблицы Excel. Для вычисления бита чётности примените функцию вычисления остатка от деления, которая в Excel называется ОСТАТ.

(Вставка – Объект - Лист MS Excel).

1. Код Хэмминга позволяет исправить одну ошибку и обнаружить две. Признаком ошибки (или ошибок) служит несовпадение контрольных битов со значением, которые вычислено по полученным битам данных. Например, пусть приняты данные

По битам данных (с номерами 3, 5, 6 и 7) рассчитываем значения контрольных битов, которые получаются при безошибочной передаче:

бит 1 = (бит 3 + бит 5 + бит 7) mod 2 = (1 + 1 + 0) mod 2 = 0

бит 2 = (бит 3 + бит 6 + бит 7) mod 2 = (1 + 1 + 0) mod 2 = 0 ≠ 1

бит 4 = (бит 5 + бит 6 + бит 7) mod 2 = (1 + 1 + 0) mod 2 = 0 ≠ 1

Видим, что полученные значения контрольных битов 2 и 4 не совпадают с вычисленными, поэтому при передаче были ошибки. Если предположить, что была только одна ошибка, то номер ошибочного бита вычисляется как сумма номером несовпавших контрольных битов, в данном примере это 2 + 4 = 6. Таким образом, 6-й бит принят неверно, исправленные данные выглядят так:

Это код Хэмминга для числа 1100₂ = 12.

Задание: устройство приняло приведенные в задании 7-битовые блоки, в каждом из которых не более одной ошибки. Восстановите правильные данные и запишите в десятичной системе счисления числовую последовательность, которую пытались передать.

* Используя электронные таблицы, автоматизируйте исправление ошибок: при вводе 7-битового кода Хэмминга в некоторой ячейке должен появляться номер ошибочного бита или 0, если ошибок нет (Вставка – Объект – Лист MS Excel).