Урок 9
§6. Кодирование с обнаружением ошибок
Содержание урока
Коды с исправлением ошибок
Коды с исправлением ошибок
Значительно сложнее исправить ошибку сразу (без повторной передачи данных), однако в некоторых случаях и эту задачу удается решить. Для этого ещё больше увеличивают избыточность кода (добавляют «лишние» биты).
Когда вы говорите по телефону, иногда приходится повторять какието фразы, если собеседник не понял вас из-за помех. Эту идею можно использовать и для компьютеров, например применить код, в котором каждый бит повторяется трижды: вместо каждого нуля будем передавать кодовое слово 000, а вместо каждой единицы — кодовое слово 111.
При передаче сообщения каждый передаваемый бит повторяется три раза подряд. Могли ли быть переданы без ошибок такие сообщения?
1) 000111111111;
2) 000101000111000;
3) 111000111010111.
Как вы рассуждали?
При передаче каждой тройки одинаковых битов произошло не более одной ошибки. Какие биты пытались передать, если получены тройки битов:
001 010 011 100 101 110?
Как вы рассуждали?
Передавались сообщения, в которых каждый бит был утроен. При передаче произошли ошибки (не более одной в каждой тройке), и были получены следующие битовые цепочки:
1) 000011110101010;
2) 000101100011100;
3) 110000101010011.
Восстановите битовые цепочки (без утроения), которые передавались.
Код с утроением битов обнаруживает одну или две ошибки. Кроме того, если сделана одна ошибка, он позволяет исправить её, т. е. является помехоустойчивым.
Помехоустойчивый код — это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.
Попробуйте придумать другой трёхбитовый код (содержащий два кодовых слова), который позволяет исправлять одну ошибку и обнаруживать одну или две ошибки. Что общего в коде с утроением битов и в вашем коде?
Кроме простого дублирования битов есть и другие, более сложные помехоустойчивые коды. Например, предположим, что передаются сообщения, содержащие только четыре буквы — «П», «О», «Р», «Т». Для кодирования букв используются 5-битные кодовые слова (рис. 2.9).
Рис. 2.9
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора различаются не менее чем в трёх битах. В этом случае говорят, что расстояние Хэмминга между кодовыми словами больше или равно трём. Например, слова «П» — 111.11 и «О» — 11000 различаются в трёх последних битах, а слова «П» — 11111 и «Р» — 00100 — в четырёх битах (они подчёркнуты). Это позволяет обнаруживать и даже исправлять ошибки.
Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 00110. Определите букву, код которой отличается от этой цепочки меньше всего.
Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 10101. Определите знаки, коды которых отличаются от этой цепочки меньше всего.
Для передачи данных использовался код, заданный на рис. 2.9. При передаче каждого кодового слова произошло не более двух ошибок. Декодируйте сообщение, исправив ошибки: 00111 11100 11110 11000 00000 01110 11011 11100 00011 11000
Если ошибку исправить нельзя, поставьте символ «*».
В каком случае при использовании кода, заданного на рис. 2.9:
а) можно обнаружить ошибки, а исправить нельзя;
б) нельзя даже обнаружить ошибки?
Если все кодовые слова отличаются друг от друга не менее чем в трёх битах, такой код позволяет обнаружить одну или две ошибки. Если сделана только одна ошибка, код позволяет исправить её. Если же произошли три ошибки и более, в результате мог получиться другой правильный код, и эти ошибки обнаружить нельзя.
Следующая страница 
Выводы. Интеллект-карта
Cкачать материалы урока
