Передача данных и исправление ошибок

Ранние железнодорожные сигналы использовали белый свет для сигнала «идти» и красный свет для сигнала «стоп». Эта система беспроводной связи между начальниками станций и инженерами работала хорошо до того рокового дня, когда из ее корпуса выпала красная линза, сигнализирующая обоим встречным поездам двигаться на полной скорости. К счастью, ошибки связи редко приводят к таким катастрофам. Однако, если объединить объем цифровой информации, ежедневно передаваемой по проводам, транслируемой по земле и отражаемой от спутников, небольшое количество ошибок на передачу может привести к ошеломляющей потере глобальной пропускной способности. Для сведения к минимуму влияния ошибок передачи данных было разработано несколько методов обнаружения и исправления ошибок. Сложность и изощренность этих методов не отставала от быстрорастущих скоростей передачи и постоянно увеличивающихся источников помех, вызывающих ошибки.

Существует два основных подхода к обнаружению и исправлению ошибок в потоке цифровых данных. В первом подходе, известном как «обратная коррекция ошибок» (BEC), передатчик добавляет предварительно определенный код к данным, которые он отправляет приемнику. Изучив этот код, получатель может определить, были ли данные получены без ошибок. Если обнаружена ошибка, приемник отвечает передатчику запросом на повторную отправку данных, известным как «автоматический повторный запрос» (ARQ). Во втором подходе, называемом «упреждающее исправление ошибок» (FEC), данные кодируются таким образом, что ошибка передачи может быть не только обнаружена, но и исправлена ​​приемником, что устраняет необходимость утверждения ARQ.

В дни чрезвычайно низких скоростей передачи через выделенные проводные соединения с низким уровнем шума BEC можно было реализовать с использованием «четности» сигнала. Код обнаружения ошибок, известный как «бит четности», был сгенерирован путем суммирования количества двоичных единиц, содержащихся в пакете двоичных данных, и установки бита четности равным единице или нулю, так что общее количество двоичных единиц, включая бит четности был четным или нечетным в зависимости от использования «четности» или «нечетности». Однако при наличии нескольких ошибок существует 50%-ная вероятность того, что пакет сохранил правильную четность. Чтобы уменьшить серьезность этой проблемы, был разработан метод «контрольной суммы». Предположим, что пакет содержит четыре восьмибитных байта данных, каждый из которых представляет значение от 0 до 255. Все четыре значения суммируются, и общее количество делится на количество возможных значений в каждом байте (256). Оставшаяся часть этого деления называется контрольной суммой, и это значение добавляется к байтам данных. Хотя метод контрольной суммы более устойчив к многобитовым ошибкам, он не работает, если значение одного байта увеличивается, а значение второго байта уменьшается на ту же величину.

Поскольку в методе контрольной суммы биты неразличимы среди байтов, был разработан метод, который сохраняет уникальность каждого отдельного бита. В этом методе, если один бит перевернут, перевороту второго бита в пакете трудно компенсировать ошибку. Этот метод проверки циклическим избыточным кодом (CRC) интерпретирует каждый бит данных в пакете как коэффициент очень большого многочлена. Полученный полином делится на тщательно подобранный стандартный полином, а остаток от деления передается вместе с данными в виде контрольной суммы CRC. Способность каждого стандартного полинома CRC обнаруживать большую комбинацию ошибок различается. Некоторые популярные стандартные полиномы CRC, известные как XMODEM, сжатие ARC и CRC-32, используются Ethernet, PKZip и FDDI.

В случае удаленного передатчика, такого как космический зонд, или потоковой передачи голоса или видео в реальном времени, ARQ может быть недоступен. Метод FEC перемежает передачу данных кодами, необходимыми для исправления ошибки передачи. Долгожданный протокол беспроводной передачи данных Bluetooth использует два метода прямой коррекции ошибок, а именно 1/3 FEC и 2/3 FEC.

В 1/3 FEC передатчик просто повторяет каждый бит данных три раза подряд. Например, значение данных 101 будет отправлено как 111000111 в режиме 1/3 FEC. Если значение для 1 (111) искажено до (110) во время передачи, значение по-прежнему можно интерпретировать как 1. Обозначение 1/3 указывает, что один бит информации принимается на каждые три переданных бита. Это снижает пропускную способность до 33% от максимальной, но устраняет необходимость в ARQ. Из-за низкой пропускной способности 1/3 FEC используется для кодирования относительно короткого заголовка каждого сеанса передачи.

Работая в Bell Labs в 1948 году, Ричард В. Хэмминг разработал метод FEC, в котором простые биты четности помещались в биты данных. Каждый бит данных связан с комбинацией битов четности, и путем изучения шаблона битов четности (известного как коды Хэмминга) можно определить и исправить точный бит с ошибкой. Bluetooth использует пятибитный код Хэмминга для передачи каждых десяти битов. Результирующий 15-битный пакет состоит из двух третей данных и одной трети кодовых битов, за что получил обозначение 2/3 FEC. Этот режим FEC увеличивает пропускную способность до 66% от максимальной. Коды Хэмминга способны исправлять только один ошибочный бит, но могут обнаруживать многобитовые ошибки. Короткая 15-битная длина пакета сводит к минимуму воздействие шума, а FEC 2/3 устанавливает ARQ, если обнаружено более одной ошибки.

Доступны дополнительные методы FEC, включая методы Рида-Соломона и Витерби, а новые методы находятся в стадии разработки. По мере увеличения скорости передачи данных и перегрузки беспроводных каналов коррекция ошибок будет по-прежнему играть решающую роль. Оба фонаря работали в ту знаменитую ночь 1775 года, когда Пол Ревир увидел их на церковной колокольне. Если бы один из них потерпел неудачу, любимым развлечением американцев мог бы стать крикет.

Первоначально этот материал был опубликован как редакционная статья в журнале Scientific Computing and Instrumentation 17:10, сентябрь 2000 г., стр. 14.

Уильям Л. Уивер — адъюнкт-профессор кафедры интегрированных наук, бизнеса и технологий Университета Ла Саль в Филадельфии, штат Пенсильвания, США. Он имеет B.S. Получил двойную степень по химии и физике и получил докторскую степень. в аналитической химии с опытом в сверхбыстрой лазерной спектроскопии. Он преподает, пишет и рассказывает о применении системного мышления для разработки новых продуктов и инноваций.