Р.Л. Смелянский - Компьютерные сети. Том 1. Системы передачи данных (1130069), страница 27
Текст из файла (страница 27)
Ошибки могут быть одиночными, а могут возникать группами. Групповые ошибки* имеют, если можно так сказать, свои достоинства и недостатки. Их достоинство заключается в следующем. Пусть данные передаются блоками по 1000 бит, а частота ошибок 10 з на ! бит, т.е. одна ошибка на каждые 1 000 бит. Если ошибки одиночные, т. е. изолированные и независимые„то практически каждый блок данных в среднем будет содержать ошибку. Если же ошибки возникают группами по 100 сразу, то в среднем они будут содержаться в одном-двух В отечественной литературе ~акже используется термин м1акептые ошибки».
Однако чтобы избежать каких-либо ассопиапий с пакетами ленных, мы будем использовать термин «групповые ошибки» 116 блоках из каждых 100, Недостатком групповых ошибок является то, что их труднее обнаруживать и исправлять, чем одиночные. 4 у.б. Коды с исправлением ошибок К надежной передаче битов были предложены два основных подхола. Первый — внести избыточность в передаваемый блок данных в форме дополнительных битов таким образом, чтобы, анализируя -.-'":!':., 'полученный блок, можно было бы указать, где возникли искажения Это так называемые коды с исправлением ошибок [30].
Второй— внести избыточность, но лишь настолько, чтобы, анализируя полученные данные, можно было сказать, есть в переданном блоке ошибки или нет. Это так называемые коды с обнаружением ошибок !1, 16, 19, 23, 31! Пусть данные занимают т разрядов, и к ним добавляется г из'быточных контрольных разрядов. При этом необходимо передать !;:и='":"-'слово длиной и =- т + г, называемое п-битовым кодословом. Рас- 4 стояние Хемминга между двумя кодословами — это число разных разрядов в этих колословах.
Например, пусть имеется два кодослова— 10001001 и 10110001. Расстояние Хемминга между ними равно трем, ;:,11~!.'::.~::.;так как число различных разрядов в них — три. Следовательно, если ;;,;,'„:-"::" .: два кодослова находятся на расстоянии д по Хеммингу, это означает, что для преобразования одного кодослова в другое необходимо про=.,'"~!:,.'~з образовать ровно д разрядов Поскольку избьпочные контрольные разряды могут принимать ,„'1-;,.::::,'"' только вполне определенные значения, то при длине и не все 2" кодовых слов возможны. Зная алгоритм установки контрольных раз;,"','.!!х .рядов, можно вычислить минимальное расстояние Хемминга между двумя правильными кодословами. Способность кода исправлять ошибки или только обнаруживать '-;,;-:1:", " их зависит от расстояния между кодословами по Хеммингу.
Если мы хотим обнаружить д ошибок, то необходимо, чтобы правильные кодослова отстояли друг от друга на расстояние д + 1. Тогда, если минимальное расстояние принятого кола от правильных кодослов 1с < д, ", ~";;::!,'-'"';;:; ' то принятое кодослово содержит !с ошибок. Если мы хотим исправить д ошибок, то необходимо, чтобы кодослова отстояли друг от друга на расстояние 2д + !.
В этом случае, даже если переланное кодослово содержит д ошибок, оно все равно расположено ближе только к одно- !'2 му кодослову, чем к другим. Это колослово и считается правильным, и таким образом можно определить исходное слово Простым примером кода с обнаружением олной ошибки является код с битом четности, конструкция которого следующая: к исходному кодослову добавляется бит четности. Если число единиц в исходном кодослове четное, то значение этого бита нуль, а если нечетное, то — единица. В случае единичных ошибок у кодослов с битом четности расстояние Хемминга равно двУм, так как любая ошибка в 1!7 одном бите порождает ошибку четности.
Однако при возможности лвойных ошибок бит четности проблему не решает. В качестве примера кода с исправлением ошибки рассмотрим код, в котором есть только четыре правильных кодослова: 0000000000, 0000011111, 1111100000, 1111111111. Расстояние Хемминга в этом коде равно пяти, следовательно, он может исправлять двойные ошибки. Если получатель примет слово 0000000111, будет ясно, что исходное слово имело вид 0000011111.
Однако, если допустимы тройные ошибки, то полученное слово 0000000111 может означать, что исходным было слово 0000000000. Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночных ошибок. Пусть имеется код из т бит сообщения и г контрольных битов. В этом случае каждое из 2 правильных сообтцений содержит и неправильных кодослов на расстоянии Хемминга, равном единице, где л = т + г. Таким образом, с каждым из 2 кодослов связано и + 1 кодослов: и неправильных и одно правильное. Так как обшее число кодослов 2", то (и + 1)2 < 2". Учитывая, что п = гл ч г, получим отношение 1т ч г э 1) < 2". Для заданного т это отношение задает минимальное число контрольных разрядов, необходимых для исправления одиночных ошибок.
Такой теоретический предел достижим при использовании метода, предложенного Хеммингом, идея которого заключается в следующем; ° разряды кодослова нумеруются слева направо, начиная с 1; ° все биты, номера которых являются степенью 2 (т, е, 1, 2, 4, 8, 16 и т.д.) — контрольные, остальные — биты сообшения; ~ каждый контрольный бит отвечает за четность группы битов, включая себя.
Чтобы определить группу битов, за четность которой отвечает определенный контрольный бит, слелует представить номер позиции каждого бита по степеням двойки. Те биты, в номера которых входит степень двойки, равная номеру контрольного бита, и есть искомая группа. Например, 11 = 1 + 2 + 8, 39 = 1 + 2 + 4 + 32.
Таким образом, бит в позиции 11 и бит в позиции 39 входят в группу, контролируемую битом в позиции 2. Приняв кодослово, получатель устанавливает специальный счетчик в нуль, а затем проверяет каждый контрольный бит на предмет правильности четности группы битов, контролируемой этим контрольным битом. Если четность нарушена, то порядковый номер этого бита заносится в счетчик. Если после такой проверки счетчик остается на нуле, то все в порядке. Если нет, то он содержит номер неправильного разряда Например, если 1, 2, 8 — ошибочные контрольные разряды, то ошибка содержится в 1! -м разряле, так как только он связан одновременно с этими контрольными разрядами. 118 Контрольные биты ООПОО!0000 1ОП!001001 П!01010101 1 П 0 10 10101 ОПОЮП001 ОП01010ПО ПП100ПП 100ПОООООО ПП!ООООП Симеол ДБСП-код и а тп ! и в 1001000 П 00001 ПОПО! ПОП01 П01001 П ОП 10 ПООП1 ОЮОООО ПОООП е о д ПОПП 001010ПП! П00100 ПП100ПОО П00101 ООП1000101 Порллок передачи битои 'л!:,-'', :Рис.
4.2. Ис!Юльзодание кола Хеннинга для исправления ошибок передачи 4. 7. 7. Коды с абнаружениедд ашибек Рассмотрение кодов с обнаружением ошибок начнем с небольшого примера. Пусть имеется канал передачи, в котором одиночные ошибки появляются с частотой 10 ' на один бит. В случае необходи,.'с', Мости исправление единичных ошибок при передаче блока ланных Р.' размером в ! 000 бит потребуется 1О контрольных битов ((т ь ! ч- 1) < и 2', где т = 1 000, т. е, (1001 и г) < 2', следовательно, г = 10) При передаче 1 Мбит данных требуется потратить 10 000 контроль,'":,," .; ных битов.
В то же время для обнаружения единичной ошибки до- На рис. 4.2 показаны 7-разрядный А8СП-код и соответствующий .'! '-" ему 11-разрядный код Хемминга. В этом коде Хемминга разряды 1, 2, -';"'; 4, 8 — контрольные, 3-й разряд соответствует 1-му разряду исходно::;~::::;,::, го кода, а разряды 5, б, 7, 9, 10, 11 — разрядам 2, 3, 4, 5, 6, 7. В коде "--',.:; Хемминга 1-й разряд контролирует группу, в которую входят разряды ',.''-":. с номерами 3, 5, 7, 9, 11, что соответствует разрядам 1, 2, 4, 5, 7 в ис:;;.~!.-,:; ходном коде. Так как единица в этих разрядах исходного кода четная, "~.:;,' е то 1-й разряд в коде Хемминга равен нулю.
Аналогично определяет,'«:.!: ся значение остальных контрольных разрядов Кол Хемминга может исправлять только одиночные ошибки. Од- :1:.;;~".:,-';,нако существует прием, который позволяет распространить идеи 1,'. Хемминга на случай групповых ошибок. Пусть требуется передать )е ;,".;;,::"-: кодослов. Расположим их в виде матрицы: одно слово — строка. ,.",,'*=;:.! Обычно передают слово за словом, но мы поступим иначе: передадим ,,'-,.„:;-;-;.: слово длиной 7< сначала из первых разрядов всех слов, затем — из вторых и так далее, т.е.
по столбцам. После приема всех слов магри';:",.;.-". ца восстанавливается. Если необходимо обнаруживать групповые ,:..', ", ошибки размером К то в каждой строке восстановленной матрицы '~:;::::: будет не более одной ошибки, а с одиночными ошибками код Хем- !~;:, минга справится статочно одного бита четности. Следовательно, при использовании техники повторной передачи на передачу ! 000 блоков по 1000 бит в кажлом требуется потратить 1001 бит четности или с повторной передачей 2 002 бит вместо 10 000 бит в случае применения кода с исправлением ошибки. Прямое применение техники четности в случае наличия групповых ошибок не дает необходимого результата, поэтому ее следует скорректировать. Пусть требуется передать и слов по тс бит.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
