Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 59
Текст из файла (страница 59)
Аналогично, для исправления d ошибок в одном кодовом словетребуется код с минимальным кодовым расстоянием, равным Id + 1, так как вданном случае даже при d однобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к любому другому, и, следовательно, его можно будет однозначно восстановить.В качестве простейшего примера кода с обнаружением ошибок рассмотримкод, в котором к данным добавляется один бит четности.
Бит четности выбирается таким образом, чтобы количество единиц во всем кодовом слове было четным (или нечетным). Например, при посылке числа 10110101 с добавлением битачетности в конце оно становится равным 101101011, тогда как 10110001 преобразуется в 101100010. Код с единственным битом четности имеет кодовое расстояние, равное 2, так как любая однократная ошибка в любом разряде образуеткодовое слово с неверной четностью.
Такой код может использоваться для обнаружения однократных ошибок.В качестве простейшего примера корректирующего кода рассмотрим код,у которого есть всего четыре допустимые кодовые комбинации:23i(или нечетность) некоторой группы битов, включая себя самого. Один бит может входить в несколько различных групп битов, четность которых вычисляетсяЧтобы определить, в какие группы контрольных сумм будет входить бит данны:в k-тл позиции, следует разложить k по степеням числа 2. Например, 11 = 8 + 2 + 1а 29 =16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами, номера которых входят в этот ряд разложения (например, 11-й бит проверяется битами 1, 2 и 8).Когда прибывает кодовое слово, приемник обнуляет счетчик. Затем он проверяет каждый контрольный бит k (k = 1, 2, 4, 8,...) на четность.
Если сумма оказывается нечетной, он добавляет число k к счетчику. Если после всех проверо:счетчик равен нулю, значит, все проверки были пройдены успешно. В противногслучае он содержит номер неверного бита. Например, если ошибку дают проверки битов 1, 2 и 8, это означает, что инвертирован бит 11, так как он являете:единственным битом, контролируемым битами 1, 2 и 8. На рис.
3.7 изображен!некоторые ASCII-символы, кодированные 11-битовым кодом Хэмминга. Напоминаем, что данные хранятся в битах 3, 5, 6, 7, 9, 10 и 11.СимволASCIIКонтрольные битын100100000110010000а110000110111001001m1101101111010101010000000000, 0000011111, 1111100000 и 1111111111m110110111101010101Этот код имеет расстояние, равное 5, что означает, что он может исправлятьдвойные ошибки. Если приемник получит кодовое слово 0000000111, он поймет,что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит 0000000000 на 0000000111, ошибка будет исправлена неверно.Попробуем создать код, состоящий из т информационных и г контрольныхбитов, способный исправлять одиночные ошибки. Каждому из 2"' допустимыхсообщений будет соответствовать п недопустимых кодовых слов, отстоящих отсообщения на расстояние 1. Их можно получить инвертированием каждого из пбитов п-битового кодового слова.
Таким образом, каждому из 2'" допустимых сообщений должны соответствовать и + 1 кодовых комбинаций. Поскольку общее количество возможных кодовых комбинаций равно 2", получается, что (п + 1)2 т < 2".Так как п = т + г, это требование может быть преобразовано к виду (т + г + 1) < Т.При заданном т данная формула описывает нижний предел требуемого количества контрольных битов для возможности исправления одиночных ошибок.Этот теоретический нижний предел может быть достигнут на практике с помощью метода Хэмминга (1950). Биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4,8, 16 и т.
д.), являются контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются т битами данных. Каждый контрольный бит обеспечивает четностьi110100101101011001n110111001101010110g110011101111001111010000010011000000с110001111111000011о110111110101011111d1100100e110010111111001100x'00111000101Порядок передачи битРис. 3.7. Корректирующий код ХэммингаКоды Хэмминга позволяют исправлять только одиночные ошибки.
Однакодин не слишком хитрый трюк позволяет исправлять при помощи этого коди наборы ошибок. Для этого последовательность k кодовых слов организуетсявиде матрицы, по одному кодовому слову в ряду. Обычно данные передаются пкодовым словам, слева направо. Но чтобы иметь возможность исправлять набсры ошибок, данные из этой таблицы следует передавать по столбцу за один при234Обнаружение и исправление ошибокГлава 3. Уровень передачи данныхмежду которыми будет минимальным.
Это расстояние называется минимальнымкодовым расстоянием кода, или расстоянием всего кода в смысле Хэмминга.Способности кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для обнаружения d ошибок в одном кодовомслове необходим код с минимальным кодовым расстоянием, равным d + 1, поскольку d однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация.
Когда приемниквстречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка. Аналогично, для исправления d ошибок в одном кодовом словетребуется код с минимальным кодовым расстоянием, равным 2d + 1, так как вданном случае даже при d однобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к любому другому, и, следовательно, его можно будет однозначно восстановить.В качестве простейшего примера кода с обнаружением ошибок рассмотримкод, в котором к данным добавляется один бит четности. Бит четности выбирается таким образом, чтобы количество единиц во всем кодовом слове было четным (или нечетным). Например, при посылке числа 10110101 с добавлением битачетности в конце оно становится равным 101101011, тогда как 10110001 преобразуется в 101100010.
Код с единственным битом четности имеет кодовое расстояние, равное 2, так как любая однократная ошибка в любом разряде образуеткодовое слово с неверной четностью. Такой код может использоваться для обнаружения однократных ошибок.В качестве простейшего примера корректирующего кода рассмотрим код,у которого есть всего четыре допустимые кодовые комбинации:0000000000, 0000011111, 1111100000 и 1111111111Этот код имеет расстояние, равное 5, что означает, что он может исправлятьдвойные ошибки.
Если приемник получит кодовое слово 0000000111, он поймет,что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит 0000000000 на 0000000111, ошибка будет исправлена неверно.Попробуем создать код, состоящий из т информационных и г контрольныхбитов, способный исправлять одиночные ошибки. Каждому из 2т допустимыхсообщений будет соответствовать п недопустимых кодовых слов, отстоящих отсообщения на расстояние 1. Их можно получить инвертированием каждого из пбитов гс-битового кодового слова. Таким образом, каждому из 2т допустимых сообщений должны соответствовать п + 1 кодовых комбинаций. Поскольку общее количество возможных кодовых комбинаций равно 2", получается, что (п +1)2™ < 2".Так как п = т + г, это требование может быть преобразовано к виду (т + г + 1) < 2Г.При заданном т данная формула описывает нижний предел требуемого количества контрольных битов для возможности исправления одиночных ошибок.Этот теоретический нижний предел может быть достигнут на практике с помощью метода Хэмминга (1950).
Биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4,8, 16 и т. д.), являются контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются т битами данных. Каждый контрольный бит обеспечивает четность235(или нечетность) некоторой группы битов, включая себя самого. Один бит может входить в несколько различных групп битов, четность которых вычисляется.Чтобы определить, в какие группы контрольных сумм будет входить бит данныхв k-й позиции, следует разложить k по степеням числа 2.
Например, 11 = 8 + 2 + 1,а 29 =16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами, номера которых входят в этот ряд разложения (например, 11-й бит проверяется битами 1, 2 и 8).Когда прибывает кодовое слово, приемник обнуляет счетчик. Затем он проверяет каждый контрольный бит k(k = \, 2, 4, 8, ...) на четность. Если сумма оказывается нечетной, он добавляет число k к счетчику.
Если после всех провероксчетчик равен нулю, значит, все проверки были пройдены успешно. В противномслучае он содержит номер неверного бита. Например, если ошибку дают проверки битов 1, 2 и 8, это означает, что инвертирован бит 11, так как он являетсяединственным битом, контролируемым битами 1, 2 и 8. На рис. 3.7 изображенынекоторые ASCII-символы, кодированные 11-битовым кодом Хэмминга. Напоминаем, что данные хранятся в битах 3, 5, 6, 7, 9, 10 и 11.СимволASCIIКонтрольные битын100100000110010000а110000110111001001m110110111101010101m110110111101010101i110100101101011001n110111001101010110g110011101111001111010000010011000000с110001111111000011о110111110101011111d110010011111001100e1100101'00111000101Порядок передачи битРис. 3.7. Корректирующий код ХэммингаКоды Хэмминга позволяют исправлять только одиночные ошибки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
