Обнаружение и исправление ошибок


Обнаружение и исправление ошибок | это... Что такое Обнаружение и исправление ошибок?

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

Для обнаружения ошибок используют коды обнаружения ошибок, для исправления — корректирующие коды (коды, исправляющие ошибки, коды с коррекцией ошибок, помехоустойчивые коды).

Содержание

  • 1 Способы борьбы с ошибками
  • 2 Коды обнаружения и исправления ошибок
    • 2.1 Блоковые коды
      • 2.1.1 Линейные коды общего вида
        • 2.1.1.1 Минимальное расстояние и корректирующая способность
        • 2.1.1.2 Коды Хемминга
        • 2.1.1.3 Общий метод декодирования линейных кодов
      • 2. 1.2 Линейные циклические коды
        • 2.1.2.1 Порождающий (генераторный) полином
        • 2.1.2.2 Коды CRC
        • 2.1.2.3 Коды БЧХ
        • 2.1.2.4 Коды коррекции ошибок Рида — Соломона
      • 2.1.3 Преимущества и недостатки блоковых кодов
    • 2.2 Свёрточные коды
      • 2.2.1 Преимущества и недостатки свёрточных кодов
    • 2.3 Каскадное кодирование. Итеративное декодирование
    • 2.4 Сетевое кодирование
    • 2.5 Оценка эффективности кодов
      • 2.5.1 Граница Хемминга и совершенные коды
      • 2.5.2 Энергетический выигрыш
    • 2.6 Применение кодов, исправляющих ошибки
  • 3 Автоматический запрос повторной передачи
    • 3.1 Запрос ARQ с остановками (stop-and-wait ARQ)
    • 3.2 Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)
    • 3.3 Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)
  • 4 См. также
  • 5 Литература
  • 6 Ссылки

Способы борьбы с ошибками

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

В системах связи возможны несколько стратегий борьбы с ошибками:

  • обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется, в основном, на канальном и транспортном уровнях;
  • обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
  • исправление ошибок (англ. forward error correction) применяется на физическом уровне.

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

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.

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

С кодами, исправляющими ошибки, тесно связаны коды обнаружения ошибок. В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

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

Блоковые коды

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

Если исходные бит код оставляет неизменными, и добавляет проверочных, такой код называется систематическим, иначе несистематическим.

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

  • способность исправлять как можно большее число ошибок,
  • как можно меньшая избыточность,
  • простота кодирования и декодирования.

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

Практически все используемые коды являются линейными. Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования.

Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует -мерное линейное подпространство (назовём его ) в -мерном линейном пространстве, изоморфное пространству -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.

Пусть  — ортогональное подпространство по отношению к , а  — матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:

Минимальное расстояние и корректирующая способность

Основная статья: Расстояние Хемминга

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях:

.

Минимальное расстояние Хемминга является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

.

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

Таким образом, получив искажённую кодовую комбинацию из , декодер принимает решение, что исходной была кодовая комбинация , исправляя тем самым не более ошибок.

Поясним на примере. Предположим, что есть два кодовых слова и , расстояние Хемминга между ними равно 3. Если было передано слово , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к любому другому, и, в частности, к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ), то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение, что передавалось слово .

Коды Хемминга

Основная статья: Код Хемминга

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром

, где  — принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.
Общий метод декодирования линейных кодов

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

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

Линейные циклические коды

Основная статья: Циклический код

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

Циклическим кодом является линейный код, обладающий следующим свойством: если является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово представляется в виде полинома . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть могут принимать значения 0 или 1.

Порождающий (генераторный) полином

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному . Порождающий полином является делителем .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

  • несистематическое кодирование осуществляется путём умножения кодируемого вектора на : ;
  • систематическое кодирование осуществляется путём «дописывания» к кодируемому слову остатка от деления на , то есть .
Коды CRC

Основная статья: Циклический избыточный код

Коды CRC (англ. cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления на . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода степень полином
CRC-12 12
CRC-16 16
CRC-CCITT 16
CRC-32 32
Коды БЧХ

Основная статья: Код Боуза — Чоудхури — Хоквингема

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически полинома на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

Основная статья: Код Рида — Соломона

Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с байтами (октетами).

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Свёрточные коды

Основная статья: Свёрточный код

Свёрточный кодер ()

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

Кодирование свёрточным кодом производится с помощью регистра сдвига, отводы от которого суммируются по модулю два. Таких сумм может быть две (чаще всего) или больше.

Декодирование свёрточных кодов, как правило, производится по алгоритму Витерби, который пытается восстановить переданную последовательность согласно критерию максимального правдоподобия.

Преимущества и недостатки свёрточных кодов

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование

Преимущества разных способов кодирования можно объединить, применив каскадное кодирование. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается код-произведение.

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

Сетевое кодирование

Оценка эффективности кодов

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

Граница Хемминга и совершенные коды

Основная статья: Граница Хэмминга

Пусть имеется двоичный блоковый код с корректирующей способностью . Тогда справедливо неравенство (называемое границей Хемминга):

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными.

Энергетический выигрыш

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

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

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

  • в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
  • в системах хранения информации, в том числе магнитных и оптических.

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

Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

Для этого метода необходим полнодуплексный канал. Передача данных от передатчика к приемнику производится одновременно. В случае ошибки передача возобновляется, начиная с ошибочного блока (то есть передается ошибочный блок и все последующие).

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также

  • Цифровая связь
  • Код ответа (Код причины завершения)
  • Линейный код
  • Циклический код
  • Код Боуза — Чоудхури — Хоквингема
  • Код Рида — Соломона
  • LDPC
  • Свёрточный код
  • Турбо-код

Литература

  • Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
  • Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
  • Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0

Ссылки

  • Помехоустойчивое кодирование (11 ноября 2001). — реферат по проблеме кодирования сообщений с исправлением ошибок. Архивировано из первоисточника 25 августа 2011. Проверено 25 декабря 2006.

Обнаружение и исправление ошибок | это... Что такое Обнаружение и исправление ошибок?

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

Для обнаружения ошибок используют коды обнаружения ошибок, для исправления — корректирующие коды (коды, исправляющие ошибки, коды с коррекцией ошибок, помехоустойчивые коды).

Содержание

  • 1 Способы борьбы с ошибками
  • 2 Коды обнаружения и исправления ошибок
    • 2.1 Блоковые коды
      • 2.1.1 Линейные коды общего вида
        • 2.1.1.1 Минимальное расстояние и корректирующая способность
        • 2.1.1.2 Коды Хемминга
        • 2.1.1.3 Общий метод декодирования линейных кодов
      • 2.1.2 Линейные циклические коды
        • 2.1.2.1 Порождающий (генераторный) полином
        • 2.1.2.2 Коды CRC
        • 2.1.2.3 Коды БЧХ
        • 2.1.2.4 Коды коррекции ошибок Рида — Соломона
      • 2.1.3 Преимущества и недостатки блоковых кодов
    • 2.2 Свёрточные коды
      • 2.2.1 Преимущества и недостатки свёрточных кодов
    • 2.3 Каскадное кодирование. Итеративное декодирование
    • 2.4 Сетевое кодирование
    • 2.5 Оценка эффективности кодов
      • 2.5.1 Граница Хемминга и совершенные коды
      • 2.5.2 Энергетический выигрыш
    • 2.6 Применение кодов, исправляющих ошибки
  • 3 Автоматический запрос повторной передачи
    • 3. 1 Запрос ARQ с остановками (stop-and-wait ARQ)
    • 3.2 Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)
    • 3.3 Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)
  • 4 См. также
  • 5 Литература
  • 6 Ссылки

Способы борьбы с ошибками

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

В системах связи возможны несколько стратегий борьбы с ошибками:

  • обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется, в основном, на канальном и транспортном уровнях;
  • обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
  • исправление ошибок (англ.  forward error correction) применяется на физическом уровне.

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

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.

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

С кодами, исправляющими ошибки, тесно связаны коды обнаружения ошибок. В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

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

Блоковые коды

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

Если исходные бит код оставляет неизменными, и добавляет проверочных, такой код называется систематическим, иначе несистематическим.

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

  • способность исправлять как можно большее число ошибок,
  • как можно меньшая избыточность,
  • простота кодирования и декодирования.

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

Практически все используемые коды являются линейными. Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования.

Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует -мерное линейное подпространство (назовём его ) в -мерном линейном пространстве, изоморфное пространству -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.

Пусть  — ортогональное подпространство по отношению к , а  — матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:

Минимальное расстояние и корректирующая способность

Основная статья: Расстояние Хемминга

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях:

.

Минимальное расстояние Хемминга является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

.

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

Таким образом, получив искажённую кодовую комбинацию из , декодер принимает решение, что исходной была кодовая комбинация , исправляя тем самым не более ошибок.

Поясним на примере. Предположим, что есть два кодовых слова и , расстояние Хемминга между ними равно 3. Если было передано слово , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к любому другому, и, в частности, к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ), то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение, что передавалось слово .

Коды Хемминга

Основная статья: Код Хемминга

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром

, где  — принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.
Общий метод декодирования линейных кодов

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

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

Линейные циклические коды

Основная статья: Циклический код

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

Циклическим кодом является линейный код, обладающий следующим свойством: если является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово представляется в виде полинома . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть могут принимать значения 0 или 1.

Порождающий (генераторный) полином

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному . Порождающий полином является делителем .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

  • несистематическое кодирование осуществляется путём умножения кодируемого вектора на : ;
  • систематическое кодирование осуществляется путём «дописывания» к кодируемому слову остатка от деления на , то есть .
Коды CRC

Основная статья: Циклический избыточный код

Коды CRC (англ.  cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления на . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода степень полином
CRC-12 12
CRC-16 16
CRC-CCITT 16
CRC-32 32
Коды БЧХ

Основная статья: Код Боуза — Чоудхури — Хоквингема

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически полинома на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

Основная статья: Код Рида — Соломона

Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с байтами (октетами).

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Свёрточные коды

Основная статья: Свёрточный код

Свёрточный кодер ()

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

Кодирование свёрточным кодом производится с помощью регистра сдвига, отводы от которого суммируются по модулю два. Таких сумм может быть две (чаще всего) или больше.

Декодирование свёрточных кодов, как правило, производится по алгоритму Витерби, который пытается восстановить переданную последовательность согласно критерию максимального правдоподобия.

Преимущества и недостатки свёрточных кодов

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование

Преимущества разных способов кодирования можно объединить, применив каскадное кодирование. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается код-произведение.

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

Сетевое кодирование

Оценка эффективности кодов

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

Граница Хемминга и совершенные коды

Основная статья: Граница Хэмминга

Пусть имеется двоичный блоковый код с корректирующей способностью . Тогда справедливо неравенство (называемое границей Хемминга):

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными.

Энергетический выигрыш

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

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

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

  • в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
  • в системах хранения информации, в том числе магнитных и оптических.

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

Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

Для этого метода необходим полнодуплексный канал. Передача данных от передатчика к приемнику производится одновременно. В случае ошибки передача возобновляется, начиная с ошибочного блока (то есть передается ошибочный блок и все последующие).

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также

  • Цифровая связь
  • Код ответа (Код причины завершения)
  • Линейный код
  • Циклический код
  • Код Боуза — Чоудхури — Хоквингема
  • Код Рида — Соломона
  • LDPC
  • Свёрточный код
  • Турбо-код

Литература

  • Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
  • Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
  • Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0

Ссылки

  • Помехоустойчивое кодирование (11 ноября 2001). — реферат по проблеме кодирования сообщений с исправлением ошибок. Архивировано из первоисточника 25 августа 2011. Проверено 25 декабря 2006.

Обнаружение и исправление ошибок в компьютерных сетях

Обзор

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

Scope

  • В этой статье мы рассмотрим обнаружение и исправление ошибок в компьютерных сетях.
  • В первую очередь изучим ошибки, и типы ошибок.
  • Затем мы рассмотрим тему обнаружения и исправления ошибок.
  • Наконец, мы рассмотрим технику исправления ошибок, то есть код Хэмминга.

Ошибки связи

Когда информация , полученная на стороне получателя , не соответствует отправленным данным. Во время передачи в двоичные данные, отправляемые от отправителя к получателю, вносятся ошибки из-за шума во время передачи. Это означает, что бит, имеющий 9Значение 0005 0 может измениться на 1 , а бит со значением 1 может измениться на 0 .

Типы ошибок

Некоторые ошибки, возникающие во время связи, приведены ниже:

Однобитовая ошибка

Как правило, только один бит полученного кадра поврежден, и поврежденный бит может находиться где угодно в рамка.

Обратитесь к изображению ниже для получения информации об однобитной ошибке

Многобитовая ошибка

Более один полученный бит в кадре признан поврежденным. Обратитесь к приведенному ниже изображению для многобитовой ошибки

Пакетная ошибка

В полученном кадре повреждено более одного последовательного бита.

Обратитесь к изображению ниже, чтобы узнать об ошибке пакетных битов

Обнаружение ошибок

Простая проверка на четность

Данные, отправленные отправителем, проходят проверку на четность:

  • 1 добавляется в качестве бита четности к блоку данных, если блок данных имеет нечетное число единиц .
  • 0 добавляется в качестве бита четности к блоку данных, если блок данных содержит четное количество единиц .

Эта процедура используется для преобразования числа из единиц в четное . И это обычно известно как проверка четности.

См. изображение ниже для простого метода проверки четности:

Недостаток:

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

Обратитесь к изображению ниже, чтобы узнать о недостатках простой метод проверки четности

Двумерная проверка четности

Для каждой строки и столбца биты проверки четности вычисляются простым методом проверки четности. Контроль четности для строк и столбцов передается вместе с данными, отправляемыми от отправителя к получателю. На стороне получателя биты четности сравниваются с вычисленной четностью полученных данных.

Обратитесь к изображению ниже для двухмерного метода проверки четности

Недостатки:

  • Если 2 бита повреждены в 1 блоке данных , а другой блок данных точно в той же позиции поврежден, тогда этот метод не в состоянии обнаружить ошибку.
  • Иногда этот метод не используется для **обнаружения 4-битных **ошибок или более чем 4-битных ошибок.

Контрольная сумма

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

  1. Сначала данные делятся на k сегментов в схеме обнаружения ошибок контрольной суммы, и каждый сегмент имеет m бит.
  2. Для нахождения суммы на стороне отправителя все сегменты складываются через арифметику с дополнением до 1 . А для определения контрольной суммы дополняем сумму.
  3. Вместе с сегментами данных передаются и сегменты контрольной суммы.
  4. Все сегменты, полученные на стороне получателя, суммируются с помощью арифметики дополнения 1S для определения суммы. Затем дополните и сумму.
  5. Полученные данные принимаются только при условии, что результат равен 0 . И если результат не 0, то он будет отброшен.

См. изображение ниже для метода контрольной суммы

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

Проверка циклическим избыточным кодом

Метод проверки циклическим избыточным кодом показан на изображении ниже.

  • Схема контрольной суммы использует метод сложения, но CRC использует двоичное деление.
  • В конец битов CRC добавляется битовая последовательность, обычно известная как проверка циклическим избыточным кодом. Это делается для того, чтобы результирующая единица данных делилась на второе заранее заданное двоичное число.
  • Принимаемые блоки данных на стороне получателя должны быть разделены на одно и то же число. Эти единицы данных принимаются и признаются правильными только при условии, что остаток от этого деления равен нулю. Остальные показывают, что данные неверны. Значит, их нужно отбросить.

См. рисунок ниже для примера метода проверки циклическим избыточным кодом

Недостатки: Проверка циклическим избыточным кодом может привести к переполнению данных .

Исправление ошибок

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

Обратное исправление ошибок

В этом методе при обнаружении какой-либо ошибки в данных на стороне получателя. Затем получатель отправляет запрос на повторную отправку всего блока данных.

Прямое исправление ошибок

В этом методе приемник использует код исправления ошибок, который автоматически исправляет ошибки.

Методы исправления ошибок

Мы можем обнаружить ошибку, используя один дополнительный бит, но мы не можем использовать этот бит для исправления. Важно знать точное местоположение ошибки, если мы хотим исправить эту ошибку. Например, чтобы узнать 9r>=d+r+1}2r>=d+r+1

Приведенная выше формула используется для определения значения r . Например, предположим, что 4 будет значением d, тогда 3 будет единственным и наименьшим значением , которое удовлетворяет этому конкретному соотношению. Код Хэмминга — это метод, разработанный Р. У. Хэммингом для определения положения бита ошибки. Этот код Хэмминга основан на взаимосвязи между избыточными битами и единицами данных, и его главное преимущество состоит в том, что его можно применять к единицам данных любой длины.

Код Хэмминга

Биты четности: Биты четности представляют собой особый тип битов, которые добавляются к исходным данным двоичных битов, чтобы сделать общее количество единиц четным или нечетным.

Четность: Для проверки четности используется следующая концепция: Значение бита четности будет равно 0 , если общее количество единиц четно, и значение бита четности может быть равно 1, если общее количество единиц 1 нечетно.

Паритет нечетности: Для проверки четности используется следующая концепция: Значение бита четности будет равно 1, если общее количество единиц четно, и значение бита четности может быть равно 0, если общее количество единиц 1 нечетно.

Код алгоритма Хэмминга:

  1. Добавьте информацию в 'd' битов к избыточным битам 'r' , чтобы сделать данные как d+r .
  2. Десятичное значение будет присвоено позиции каждой (d+r) цифр.
  3. В позициях 1,2…2k будут размещены биты 'r' .
  4. Биты четности снова вычисляются на стороне получателя. Позиция ошибки определяет десятичное значение бита четности.

Связь ч/б Позиция ошибки и двоичный номер:

Позиция ошибки Двоичный номер
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Мы используем этот пример для подробного объяснения концепции кода Хэмминга. 1010 должны быть исходными данными, которые необходимо передать. 921,21,22.

  • Позиция r1 равна 1
  • r2 позиция 2
  • r4 позиция 4

См. изображение ниже для данных с избыточными битами

Определение битов четности:

Определение бита r1

двоичное преобразование содержит 1 в первой позиции.

См. изображение ниже для нахождение значения бита r1

Из приведенного выше рисунка мы можем найти позицию с 1 в качестве первого бита в двоичном представлении: 1,3,5,6 . Теперь к этим битовым позициям применяется метод проверки на четность. Количество единиц в этих битовых позициях 2, что является четным числом, поэтому 0 является значением бита r1.

Определение бита r2 Значение бита r2 вычисляется на основе проверки четности, выполняемой для битов, доступных в позиции, двоичное преобразование которой содержит 1 на второй позиции .

Обратитесь к изображению ниже, чтобы найти значение бита r2

Из приведенного выше рисунка мы можем найти позицию, имеющую 1 , поскольку ее второй бит в двоичном представлении равен 2, 3, 6, 7 . Теперь к этим битовым позициям применяется метод проверки на четность. Количество единиц в этих битовых позициях равно 1, что является нечетным числом, поэтому 1 является значением бита r2 .

Определение бита r4 r4 Значение бита вычисляется на основе проверки четности, выполняемой для битов, доступных в позиции, двоичное преобразование которой содержит 1 в третьей позиции.

Обратитесь к изображению ниже, чтобы найти значение бита r4

Из приведенного выше рисунка мы можем найти позицию, имеющую 1 в качестве третьего бита в двоичном представлении: 4, 5, 6, 7 . Теперь к этим битовым позициям применяется метод проверки на четность. Количество единиц в этих битовых позициях 2, что является четным числом, поэтому 0 — это значение бита r4 .

Данные для передачи приведены ниже:

См. изображение ниже для данных для передачи.

Предположим, что когда данные получены на стороне получателя, значение 4-го бита изменяется на 1 с 0 . Теперь биты четности вычисляются снова, чтобы найти позицию ошибки.

Бит R1 1, 3, 5 и 7 — это позиции битов для бита r1.

Обратитесь к изображению ниже для расчета битовой четности r1

Из рисунка выше видно, что двоичное представление r1 равно 1100 . После применения метода проверки четности к битам, появляющимся в битах r4, мы получаем четное количество сумм единиц. Итак, 0 — это значение для r1 .

Бит R2 2, 3, 6 и 7 — это позиции битов для бита r2.

См. рисунок ниже для расчета Битовая четность r2

Из приведенного выше рисунка видно, что двоичное представление r2 равно 1001. После применения метода проверки на четность к битам, появляющимся в битах r4, мы получаем четное число в сумме с единицами . Итак, 0 — это значение для r2 .

Бит R4 4, 5, 6 и 7 — это позиции битов для бита r4 .

См. изображение ниже для расчета r4-битной четности

Из приведенного выше рисунка видно, что двоичное представление r4 равно 1011. После применения метода проверки четности к битам, появляющимся в битах r4, мы получаем нечетное количество сумм 1. Итак, 1 — это значение для r4 .

Избыточные биты r4r2r1 двоичное представление равно 100, которое представлено как 4 в десятичном виде. Итак, в данных на 4-й позиции ошибка и значение бита, соответствующего 4-й позиции, нужно изменить с от 1 до 0 для исправления ошибок.

Заключение

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

Обнаружение ошибок в компьютерных сетях

    Напишите статью

  • Напишите опыт интервью
  • Основы компьютерной сети

    Физический уровень

    Сетевой уровень

    Computer Network

    . Приложений

    Сетевая безопасность

    Computer Network

    .0007

    Компьютерная сеть GATE Вопросы

Улучшить статью

Сохранить статью

  • Уровень сложности: Easy
  • Последнее обновление: 28 июн, 2021

  • Читать
  • Обсудить
  • Улучшить статью

    Сохранить статью

    Ошибка
    Состояние, когда информация получателя не совпадает с информацией отправителя. Во время передачи цифровые сигналы страдают от шума, который может привести к ошибкам в двоичных битах, передаваемых от отправителя к получателю. Это означает, что бит 0 может измениться на 1 или бит 1 может измениться на 0.

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

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

    Некоторые популярные методы обнаружения ошибок:
    1. Простая проверка на четность
    2. Двумерная проверка на четность
    3. Контрольная сумма
    4. Проверка циклическим избыточным кодом

     

    1. Простая проверка на четность источник подвергается проверке битов или генератору битов четности, где четность:

    • 1 добавляется к блоку, если он содержит нечетное количество единиц, и
    • 0 добавляется, если он содержит четное количество единиц

    Эта схема делает общее количество единиц четным, поэтому она называется проверкой четности.

    2. Двумерная проверка на четность
    Биты проверки на четность вычисляются для каждой строки, что эквивалентно простой проверке на четность. Биты контроля четности также вычисляются для всех столбцов, затем оба отправляются вместе с данными. На принимающей стороне они сравниваются с битами четности, рассчитанными для полученных данных.

    3. Контрольная сумма

    • В схеме обнаружения ошибок контрольной суммы данные разбиваются на k сегментов по m бит каждый.
    • В конце отправителя сегменты складываются с использованием арифметики с дополнением до 1 для получения суммы. Сумма дополняется, чтобы получить контрольную сумму.
    • Сегмент контрольной суммы отправляется вместе с сегментами данных.
    • На стороне получателя все полученные сегменты складываются с использованием арифметики с дополнением до 1 для получения суммы. Сумма дополняется.
    • Если результат равен нулю, полученные данные принимаются; иначе отбрасывается.

    4. Проверка циклическим избыточным кодом (CRC)

    Только новые статьи

    Введите свой e-mail

    Видео-курс

    Blender для новичков

    Ваше имя:Ваш E-Mail: