ВУЗ:
distance) между двумя кодовыми комбинациями, которая будет равна количеству битов, отличающихся в этих комбинациях.
Понятие "дистанция Хэмминга" получило свое название в честь Р.В. Хэмминга
(R.W. Hamming), который провел первые исследования в области разработки кодов с исправлением ошибок. Он обра-
тился к этой проблеме в 1940-х годах по причине крайней ненадежности существовавших в то время релейных вычисли-
тельных машин. Например, дистанция Хэмминга между кодами букв А и В (рис. 1.21) равна четырем, а дистанция Хэмминга
между кодами букв В и С равна трем. Важной особенностью этого кода является то, что дистанция Хэмминга между любы-
ми двумя комбинациями будет не меньше трех. Если в результате сбоя в каком-либо отдельном бите появится ошибочное
значение, то ошибка будет легко установлена, так как получившаяся комбинация не является допустимым кодовым значени-
ем. В любой комбинации потребуется изменить не меньше трех битов, прежде чем она вновь станет допустимой.
Если в любой комбинации, показанной на рис. 1.21, возникла одиночная ошибка, то легко можно вычислить ее исход-
ное значение. Дело в том, что дистанция Хэмминга для измененной комбинации по отношению к исходной форме будет
равна единице, тогда как по отношению к другим разрешенным комбинациям она будет равна не менее чем двум. При деко-
дировании некоторого сообщения достаточно просто сравнивать каждую полученную битовую комбинацию с допустимыми
комбинациями кода, пока не будет найдена комбинация, находящаяся на дистанции, равной единице, от полученной комби-
нации. Найденная допустимая кодовая комбинация принимается за правильный символ, полученный в результате декодиро-
вания. Предположим, что получена битовая комбинация 010100. Если сравнить ее с допустимыми битовыми комбинациями
кода, то будет получена таблица дистанций, представленная на рис. 1.22. По содержанию этой таблицы можно сделать за-
ключение, что поступивший символ – это буква D, так как ее битовая комбинация в наибольшей степени соответствует по-
лученной.
Как видите, при использовании кода, представленного на рис. 1.22, действительно можно обнаружить до двух ошибок в
одной комбинации и исправить одну ошибку. Если использовать код, в котором дистанция Хэмминга между комбинациями
равняется как минимум пяти, то можно было бы обнаруживать до четырех ошибок в одной комбинации и исправлять до
двух ошибок.
Рис. 1.22. Декодирование битовой комбинации 010100
с помощью кода, представленного на рис. 1.21
Естественно, разработка эффективных кодов с достаточно длинными дистанциями Хэмминга является непростой задачей.
Для этого требуется знание такой области математики, как алгебраическая теория кодирования, которая является частью
линейной алгебры и теории матриц.
Методы коррекции ошибок широко используются в целях повышения надежности вычислительной техники. Например,
они используются в драйверах магнитных дисков большой емкости, чтобы снизить вероятность искажения хранимой ин-
формации в результате дефектов поверхности диска. Более того, главное отличие между форматом, используемым в звуко-
вых компакт-дисках, и форматом CD-ROM, предназначенным для записи компьютерных данных, заключается именно в ис-
пользовании кодов с исправлением ошибок. Функция исправления ошибок в формате CD-DA позволяет устранять только
одну ошибку на два компакт-диска, и этого вполне достаточно для аудиозаписей. Однако для компаний, поставляющих про-
граммное обеспечение, наличие ошибок в 50 % поставляемых ими компакт-дисков является совершенно недопустимым. По-
этому в формат CD-ROM включены дополнительные средства, позволяющие снизить вероятность возникновения ошибки до
одной на 20 000 компакт-дисков.
Вопросы для самопроверки
1. Приведенные ниже битовые комбинации были закодированы с использованием контроля по нечетности. Укажите комби-
нации с ошибками.
а) 10101101; б) 10000001; в) 00000000; г) 11100000; д) 11111111.
2. Могли бы Вы не заметить ошибки в байтах, представленных в первом вопросе? Поясните свой ответ.
3. Какими бы были Ваши ответы на вопросы 1 и 2, если бы в приведенных байтах использовался контроль на четность?
4. Закодируйте предложения в коде ASCII с использованием контроля по нечетности и помещением контрольного бита
в старший конец кода каждого символа:
а) Where are you?
б) "How?" Chery lasked.
в) 2 + 3 = 5.
5. Используйте представленный на рис. 1.21 код с исправлением ошибок для декодирования следующих сообщений:
а) 001111 100100 001100
б) 010001 000000 001011
(Наименьшая дистанция
Символ
Дистанция между
полученной комбинацией
битов и кодом
соответств
у
ющего символа
А
В
С
D
E
F
G
H
2
4
3
1
3
5
2
4
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
