Код Хэмминга: примеры исправления ошибок

Содержание:

Anonim

Что такое ошибка?

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

Ошибки данных могут привести к потере важных или безопасных данных. Большая часть передачи данных в цифровых системах будет осуществляться в виде «битовой передачи». Даже небольшое изменение может повлиять на производительность всей системы. В последовательности данных, если 1 изменяется на 0 или 0 меняется на 1, это называется «битовой ошибкой».

В этом руководстве по коду Хэмминга вы узнаете:

  • Что такое ошибка?
  • Типы ошибок
  • Что такое обнаружение и исправление ошибок?
  • Что такое код Хэмминга?
  • История кода Хэмминга
  • Применение кода Хемминга:
  • Преимущества кода Хэмминга
  • Недостатки кода Хэмминга
  • Процесс кодирования сообщения с использованием кода Хэмминга
  • Процесс расшифровки сообщения в коде Хэмминга

Типы ошибок

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

  • Одноразрядные ошибки
  • Множественные битовые ошибки
  • Пакетные ошибки

Однобитовые ошибки

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

Множественные битовые ошибки

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

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

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

Изменение набора битов в последовательности данных известно как «пакетная ошибка». Этот тип ошибки данных вычисляется от изменения первого бита до изменения последнего бита.

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

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

Обнаружение ошибок - это метод обнаружения ошибок, которые присутствуют в данных, передаваемых от передатчика к приемнику в системе передачи данных.

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

Три типа кодов обнаружения ошибок:

  • Проверка четности
  • Циклический контроль избыточности (CRC)
  • Продольная проверка избыточности (LRC)

Проверка четности:

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

Продольная проверка избыточности

В этом методе обнаружения ошибок блок битов организован в табличном формате. Метод LRC помогает вычислить бит четности для каждого столбца. Набор этой четности также отправляется вместе с исходными данными. Блок четности помогает проверить избыточность.

Циклическая проверка избыточности

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

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

Что такое код Хэмминга?

Код Хэмминга - это лайнер-код, который полезен для обнаружения до двух немедленных битовых ошибок. Возможны однобитовые ошибки.

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

История кода Хэмминга

  • Код Хэмминга - это методика, созданная RWHamming для обнаружения ошибок.
  • Код Хэмминга должен применяться к блокам данных любой длины и использует взаимосвязь между данными и битами избыточности.
  • Он работал над проблемой метода исправления ошибок и разработал все более мощный массив алгоритмов, названный кодом Хэмминга.
  • В 1950 году он опубликовал код Хэмминга, который сегодня широко используется в таких приложениях, как память ECC.

Применение кода Хэмминга

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

  • Спутники
  • Компьютерная память
  • Модемы
  • PlasmaCAM
  • Открытые разъемы
  • Экранирующий провод
  • Встроенный процессор

Преимущества кода Хэмминга

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

Недостатки кода Хэмминга

  • Код обнаружения и исправления однобитовых ошибок. Однако, если обнаружена ошибка нескольких битов, то результатом может быть другой бит, который следует изменить правильно. Это может привести к дальнейшим ошибкам в данных.
  • Алгоритм кода Хэмминга может решить только проблемы с отдельными битами.

Процесс кодирования сообщения с использованием кода Хэмминга

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

  • Расчет общего количества избыточных битов.
  • Проверка положения избыточных битов.
  • Наконец, вычисление значений этих избыточных битов.

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

Шаг 1) Расчет общего количества избыточных битов.

Предположим, что сообщение содержит:

  • n - количество бит данных
  • p - количество избыточных битов, которые добавляются к нему, чтобы np мог указывать не менее (n + p + 1) различных состояний.

Здесь (n + p) обозначает местоположение ошибки в каждой из (n + p) битовых позиций, а одно дополнительное состояние указывает на отсутствие ошибки. Поскольку p битов может указывать на 2 p состояния, 2 p должно быть по крайней мере равным (n + p + 1).

Шаг 2) Установите избыточные биты в правильное положение.

Резервные биты p должны быть размещены в позициях битов степеней 2. Например, 1, 2, 4, 8, 16 и т. Д. Они обозначаются как p 1 (в позиции 1), p 2 (в позиции 2). , п 3 (на позиции 4) и т. д.

Шаг 3) Расчет значений избыточного бита.

Избыточные биты должны быть битами четности, чтобы количество единиц было четным или нечетным.

Два типа паритета -

  • Уравнивание общего числа битов в сообщении называется четностью.
  • Общее количество битов в сообщении, сделанное нечетным, называется нечетной четностью.

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

P1 - это бит четности для всех битов данных в позициях, двоичное представление которых включает 1 в менее важной позиции, не включая 1 Like (3, 5, 7, 9,

…. )

P2 - это бит четности для всех битов данных в позициях, двоичное представление которых включает 1 в позиции 2 справа, не включая 2 Like (3, 6, 7, 10, 11,

…)

P3 - это бит четности для каждого бита в позициях, двоичное представление которых включает 1 в позиции 3 справа, не включая 4 Like (5-7, 12-15,

…)

Процесс расшифровки сообщения в коде Хэмминга

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

Процесс пересчета состоит из следующих этапов:

  • Подсчет количества избыточных битов.
  • Правильное расположение всех избыточных битов.
  • Проверка четности

Шаг 1) Подсчет количества избыточных битов

Вы можете использовать ту же формулу для кодирования, количество избыточных битов

2 р ≥ п + р + 1

Здесь количество битов данных, а p - количество избыточных битов.

Шаг 2) Правильная установка всех избыточных битов

Здесь p - избыточный бит, который находится в позициях битов степеней 2, например, 1, 2, 4, 8 и т. Д.

Шаг 3) Проверка четности

Биты четности необходимо рассчитывать на основе битов данных и избыточных битов.

p1 = четность (1, 3, 5, 7, 9, 11

…)

p2 = четность (2, 3, 6, 7, 10, 11

…)

p3 = четность (4-7, 12-15, 20-23

…)

Резюме

  • Передаваемые данные могут быть повреждены во время связи
  • Три типа битовых ошибок: 1) одиночные битовые ошибки 2) множественные битовые ошибки 3) пакетные битовые ошибки.
  • Изменение одного бита во всей последовательности данных известно как «ошибка одного бита».
  • В последовательности данных, если есть изменение в двух или более битах последовательности данных от передатчика к приемнику, это известно как «множественные битовые ошибки».
  • Изменение набора битов в последовательности данных известно как «пакетная ошибка».
  • Обнаружение ошибок - это метод обнаружения ошибок, которые присутствуют в данных, передаваемых от передатчика к приемнику в системе передачи данных.
  • Три типа кодов обнаружения ошибок: 1) Проверка четности 2) Циклическая проверка избыточности (CRC) 3) Продольная проверка избыточности (LRC)
  • Код Хэмминга - это лайнер-код, который полезен для обнаружения до двух немедленных битовых ошибок. Возможны однобитовые ошибки.
  • Код Хэмминга - это методика, созданная RWHamming для обнаружения ошибок.
  • Распространенными приложениями использования кода Хемминга являются спутниковая компьютерная память, модемы, встроенный процессор и т. Д.
  • Самое большое преимущество метода кода Хэмминга заключается в том, что он эффективен в сетях, где потоки данных предназначены для однобитовых ошибок.
  • Самый большой недостаток метода кода Хэмминга заключается в том, что он может решать только проблемы с отдельными битами.
  • Мы можем выполнить процесс шифрования и декодирования сообщения с помощью кода Хэмминга.