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

Подумаем, сколько ошибок может обнаружить такой метод. Если при передаче неверно передан только один из битов, коли­чество единиц в сообщении стало нечётным, это и служит призна­ком ошибки при передаче. Однако исправить ошибку нельзя, по­тому что непонятно, в каком именно разряде она случилась.

Если же изменилось два бита, чётность не меняется, и такая ошибка не обнаруживается. В длинной цепочке применение бита чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, ...), а ошибки в чётном количестве разрядов остаются незаме­ченными.

Контроль с помощью бита чётности применяется для неболь­ших блоков данных (чаще всего — для каждого отдельного байта) и хорошо работает тогда, когда отдельные ошибки при передаче независимы одна от другой и встречаются редко.

Для обнаружения искажений в передаче файлов, когда может сразу возникнуть множество ошибок, используют другой метод — вычисляют контрольную сумму с помощью какой-нибудь хэш-функции (вспомните материал учебника для 10 класса). Чаще всего для этой цели применяют алгоритмы CRC (англ. Cyclic Redundancy Code — циклический избыточный код), а так­же криптографические хэш-функции MD5, SHA-1 и другие. Если контрольная сумма блока данных, вычисленная приёмником, не совпадает с контрольной суммой, записанной передающей сторо­ной, то произошла ошибка.

 

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

Значительно сложнее исправить ошибку сразу (без повторной передачи), однако в некоторых случаях и эту задачу удаётся ре​шить. Для этого требуется настолько увеличить избыточность кода (добавить «лишние» биты), что небольшое число ошибок всё равно позволяет достаточно уверенно распознать переданное сооб​щение. Например, несмотря на помехи в телефонной линии, обычно мы легко понимаем собеседника. Это значит, что речь об​ладает достаточно большой избыточностью, и это позволяет ис​правлять ошибки «на ходу».

Пусть, например, нужно передать один бит, 0 или 1. Утроим его, добавив ещё два бита, совпадающих с первым. Таким обра​зом, получаются два «правильных» сообщения:

000 и 111.

Теперь посмотрим, что получится, если при передаче одного из битов сообщения 000 произодёт ошибка и приёмник получит искажённое сообщение 001. Заметим, что оно отличается одним битом от 000 и двумя битами от второго возможного варианта — 111. Значит, скорее всего, произошла ошибка в последнем бите и сообщение нужно исправить на 000. Если приёмник получил 101, можно точно сказать, что произошла ошибка, однако попытка ис​править её приведёт к неверному варианту, так как ближайшая «правильная» последовательность — это 111. Таким образом, та​кой код обнаруживает одну или две ошибки. Кроме того, он по​зволяет исправить (!) одну ошибку, т. е. является помехоустойчивым.

---

Помехоустойчивый код — это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.

---

Выше мы фактически применили понятие «расстояния» меж​ду двумя кодами. В теории передачи информации эта величина называется расстоянием Хэмминга в честь американского матема​тика Р. Хэмминга.

---

Расстояние Хэмминга — это количество позиций, в которых различаются  два закодированных сообщения одинаковой длины.

---

Например, расстояние d между кодами 001 и 100 равно 

d(001, 100) = 2,

потому что они различаются в двух битах (эти биты подчёркну​ты). В приведённом выше примере расстояние между «правиль​ными» последовательностями (словами) равно d(000, 111) = 3. Та​кой код позволяет обнаружить одну или две ошибки и исправить одну ошибку.

В общем случае, если минимальное расстояние между «пра​вильными» словами равно d, можно обнаружить от 1 до d - 1 ошибок, потому что при этом полученный код будет отличаться от всех допустимых вариантов. Для исправления r ошибок необ​ходимо, чтобы выполнялось условие

d ≥ 2r +1.

Это значит, что слово, в котором сделано r ошибок, должно быть ближе к исходному слову (из которого оно получено искаже​нием), чем к любому другому.

Рассмотрим более сложный пример. Пусть нужно передавать три произвольных бита, обеспечив обнаружение двух любых оши​бок и исправление одной ошибки. В этом случае можно использовать, например, такой код с тремя контрольными битами (они подчеркнуты);​

000  000                                                     100  101

001  111                                                     101  010

010  011                                                     110  110

011  100                                                     111  001

Расстояние Хэмминга между любыми двумя словами в таблице не менее 3, поэтому код обнаруживает две ошибки и позволяет ис​править одну. Как же вычислить ошибочный бит?

Предположим, что было получено кодовое слово 011011. Определив расстояние Хэмминга до каждого из «правильных» слов, находим единственное слово 010011, расстояние до которого равно 1 (расстояния до остальных слов больше). Значит, скорее всего, это слово и было передано, но исказилось из-за помех.

На практике используют несколько более сложные коды, ко​торые называются кодами Хэмминга. В них информационные и контрольные биты перемешаны, и за счёт этого можно сразу, без перебора, определить номер бита, в котором произошла ошибка. Наиболее известен семибитный код, в котором 4 бита — это дан​ные, а 3 бита — контрольные. В нём минимальное расстояние между словами равно 3, поэтому он позволяет обнаружить две ошибки и исправить одну.

 

Вопросы и задания

1. В каких единицах измеряют скорость передачи данных?

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

3. Как вычисляется информационный объем данных, который можно передать за некоторое время?

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

5. Что такое избыточность сообщения? Для чего её можно использовать? Приведите примеры.

6. Как помехи влияют на передачу данных?

7. Что такое бит чётности? В каких случаях с помощью бита чётности можно обнаружить ошибку, а в каких - нельзя?

8. Можно ли исправить ошибку, обнаружив неверное значение бита четности?

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

10. Какой код называют помехоустойчивым?

11. Каково должно быть расстояние Хэмминга между двумя любыми кодами, чтобы можно было исправить две ошибки?

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

13. Сколько ошибок обнаруживает 7-битный код Хэмминга, описанный в конце параграфа, и сколько ошибок он позволяет исправить?

 

Подготовьте сообщение

а) «Алгоритмы CRC»

б) «Коды Хемминга»

---

Вернуться в главу