Образовательный портал Павла Добряка

Задача 2.3.1. Для пе­ре­да­чи чисел по ка­на­лу с по­ме­ха­ми ис­поль­зу­ет­ся код про­вер­ки чет­но­сти. Каж­дая его цифра за­пи­сы­ва­ет­ся в дво­ич­ном пред­став­ле­нии, с до­бав­ле­ни­ем незначащих нулей до длины 4, и к по­лу­чив­шей­ся по­сле­до­ва­тель­но­сти до­пи­сы­ва­ет­ся сумма её эле­мен­тов по мо­ду­лю 2 (на­при­мер, если пе­ре­даём 23, то по­лу­чим по­сле­до­ва­тель­ность 0010100110). Опре­де­ли­те, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100000100110. Если фрагмент декодировать невозможно, обозначьте его буквой X.

Теория. Сумма элементов по модулю два означает, что мы пересчитываем количество 1 в числе. Если оно четное, то мы добавляем один бит со значением 0. Если оно нечетное, то добавляем один бит со значением 1. Таким образом, с учетом дополнительного бита, в числе всегда будет четное количество 1. Если окажется, что мы приняли нечетное число, это будет означать, что при передаче сообщения по каналу связи произошла ошибка. Это простейший код, позволяющий обнаруживать ошибки.

 Подсказка

 Ход решения

Задача 2.3.2. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:

 П — 11111, О — 11000, Р — 00100, Т — 00011.

Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра разли­ча­ют­ся не менее чем в трёх по­зи­ци­ях.

 Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 00000, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).

11011 11100 00011 11000 01110

00111 11100 11110 11000 00000

 Подсказка

 Ход решения

Примечание. В отличие от предыдущей задачи, в этой задаче код позволяет не только обнаруживать ошибку, но и исправлять ошибку, если она произошла в одном бите. Кодирование от помех является очень большим разделом дискретной математики и преподаётся в вузах на профильных специальностях в течение одного семестра.