1.2. Несколько замечаний о двоичных кодах, обнаруживающих и исправляющих ошибки

В идеальной системе двоичные символы, появляющиеся на выходе устройства, декодирующего сигналы на выходе канала двоичными символами, должны совпадать с стволами, которые поступают на вход устройства, кодирующего двоичные символы сигналами на входе канала. Однако на практике всегда есть случайные ошибки. Назначение двоичных кодов состоит в том, чтобы обнаруживать и, быть может, исправлять такие ошибки. Эти коды не могут исправлять каждую мыслимую комбинацию ошибок; они скорее предназначаются для того, чтобы исправлять наиболее правдоподобные комбинации ошибок. Ббльшая часть теории двоичных кодов основана на предположении, что каждый из символов искажается шумом независимо и что, следовательно, вероятность данной комбинации ошибок зависит только от числа ошибок. Так, например, разработаны коды, которые исправляют любую комбинацию из или меньше ошибок в блоке из символов. Подобная схема может служить подходящей моделью для некоторых каналов, однако в телефонных линиях связи или в системах хранения информации на магнитной ленте ошибки встречаются в основном пачками. Помехи в телефонной линии связи такие, как, например, молнии, длятся дольше, чем

продолжительность одного символа. Далее, дефекты магнитной ленты занимают обычно больше места, чем то, на котором записывается один символ. Поэтому нужны коды для исправления пачек ошибок. Для этой цели были разработаны некоторые очень хорошие коды, описываемые в гл. 10 и 12. Каналы связи, изображенные на рис. 1.1 и 1.2, являются односторонними. Очень часто системы связи являются двусторонними — факт, который должен быть учтен при построении кодов. В случае двустороннего канала, например, можно использовать код, обнаруживающий ошибки. Когда на каком-либо конце обнаружена ошибка, можно требовать повторения передачи и, таким образом, эффективно исправлять ошибки.

Существуют несомненные примеры односторонних каналов, в которых использование кодов, исправляющих ошибки, может уменьшить вероятность ошибки при передаче, но использование кодов, обнаруживающих ошибки, и повторной передачи этого эффекта не дает. Например, в случае хранения информации на магнитной ленте слишком поздно просить о повторной передаче после того, как лента уже хранилась неделю или месяц и при чтении записи обнаружились ошибки. Кодирование для кодов, исправляющих ошибки, лишь немного сложнее, чем для кодов, обнаруживающих ошибки. Сложного оборудования требует обычно декодирование. При передаче, например, с искусственного спутника, когда упрощение оборудования в передающей системе много важнее, чем упрощение оборудования во всей системе связи, использование кодирующего оборудования для системы исправления ошибок окажется, вероятно, более практичным, чем использование системы повторной передачи с управлением на расстоянии. Сложная процедура исправления ошибок может производиться на Земле, где ограничения, накладываемые на сложность оборудования, не являются столь жесткими. Таким образом, существуют системы, где необходимо использовать коды, не требующие каналов обратной связи, — такими кодами являются коды, исправляющие ошибки.

С другой стороны, обнаружение ошибок является по своей природе задачей много более простой, чем исправление ошибок. Так, если имеется двусторонний канал, обычно легче обеспечить обнаружение ошибок и возможность посылки требования о повторной передаче, чем воспользоваться известными в настоящее время кодами, исправляющими ошибки [92]. Некоторые коды, в особенности коды для исправления пачек ошибок, рассматриваемые в гл. 10, столь просты в осуществлении, что даже в тех случаях, когда имеется возможность повторной передачи, может оказаться разумным ввести в систему в ограниченных размерах исправление ошибок, с тем чтобы уменьшить необходимость повторных передач.

Эффективное использование каналов обратной связи для контроля ошибок еще не привлекло в теории кодирования того внимания,

которое оно заслуживает. Обратная связь наверняка может сильно упростить исправление ошибок. Существуют определенные границы эффективности простых систем обнаружения ошибок и повторной передачи, так как короткие коды не могут эффективно обнаруживать ошибки, а очень длинные коды требуют слишком частой повторной передачи. Об использовании канала обратной связи каким-либо более утонченным способом почти ничего не известно [17, 106].