Коды с исправлением ошибок

Хотя использование контрольного разряда четности и позволяет обнаружить ошибку, но не дает возможности исправить ее. Многие удивляются тому, что коды с исправлением ошибок построены таким образом, что с их помощью можно не только найти ошибку, но и исправить ее. Интуиция подсказывает нам, что мы не сможем исправить ошибку в полученном сообщении, не зная информацию, которая в нем содержится. Однако простой корректирующий код представлен на рис. 1.29.

Для того чтобы понять, как работает этот код, определим сначала расстояние Хемминга (Hamming distance) между двумя кодами как число различающихся разрядов. Это расстояние названо в честь Р. В. Хемминга (R. W. Hamming), который первым стал исследовать коды с исправлением ошибок, поняв ненадежность релейных машин в 40-х годах XX века. Например, расстояние Хемминга между кодами символов А и В равно четырем (см. рис. 1.29), а расстояние Хемминга между В и С равно трем. Важное свойство этой системы кодирования состоит в том, что расстояние Хемминга между любыми двумя кодами больше или равно трем. Поэтому если один бит в коде будет изменен, ошибку можно будет обнаружить, так как результат не будет допустимым кодом. (Для того чтобы код выглядел, как другой допустимый код, мы должны изменить по меньшей мере три бита.)

Кроме того, если появится ошибка в коде (см. рис. 1.29), мы сможем понять, как выглядел исходный код. Расстояние Хемминга между измененным кодом и исходным будет равно единице, а между ним и другими допустимыми кодами — по меньшей мере двум. Для того чтобы расшифровать сообщение, мы просто сравниваем каждый полученный код с кодами в системе до тех пор, пока не найдем код, находящийся на расстоянии, равном единице, от исходного кода. Это и будет правильный символ. Например, предположим, что мы получили код 010100. Если мы сравним его с другими кодами, то получим таблицу расстояний (рис. 1.30). Следовательно, мы можем сделать вывод, что был послан символ D, так как между его кодом и полученным кодом наименьшее расстояние.

Вы увидите, что использование этой системы (коды на рис. 1.29) позволяет обнаружить до двух ошибок в одном коде и исправить одну. Если мы создадим систему, в которой расстояние Хемминга между любыми двумя кодами будет равно самое меньшее пяти, мы сможем обнаружить до четырех ошибок в одном коде и исправить две. Конечно, создание эффективной системы кодов с большими расстояниями Хемминга представляет собой непростую задачу. В действительности, она является частью раздела математики, который называется алгебраической теорией кодов и входит в линейную алгебру и теорию матриц.

Методы исправления ошибок широко применяются для того, чтобы повысить надежность компьютерного оборудования. Например, они часто используются в дисководах для магнитных дисков большой емкости, чтобы уменьшить вероятность того, что изъян на магнитной поверхности диска разрушит данные. Кроме того, главное различие между форматом первоначальных компакт-дисков, которые использовались для звукозаписей, и более поздним форматом, который используется для хранения данных в компьютере, состоит в степени исправления ошибок. Формат CD-DA включает в себя возможности исправления ошибок, которые сводят частоту появления ошибок к одной ошибке на два компакт-диска. Этого достаточно для звукозаписи, но компании, использующие компакт-диски для поставки программного обеспечения покупателям, сказали бы, что наличие дефектов в 50 процентах дисков — слишком много. Поэтому в компакт-дисках для хранения данных применяются дополнительные возможности исправления ошибок, сокращающие вероятность появления ошибки до одной ошибки на 20 000 дисков.