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

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

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

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

Типы ошибок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как закодировать сообщение в коде Хэмминга

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

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

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

Шаг 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), п₂ (в позиции 2), п₃ (в позиции 4) и т. д.

Шаг 3) Вычисление значения избыточного бита.

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

Два типа паритета: ?

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

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

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

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

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

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

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

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

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

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

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

2^p ? п + р + 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 для обнаружения ошибок.
• Обычными приложениями использования кода Хэмминга являются спутниковая компьютерная память, модемы, встроенные процессоры и т. д.
• Самое большое преимущество метода кода Хэмминга заключается в том, что он эффективен в сетях, где потоки данных выдаются для однобитовых ошибок.
• Самый большой недостаток метода кода Хэмминга заключается в том, что он может решить проблемы только с одним битом.
• Мы можем выполнить процесс шифрования и декодирования сообщения с помощью кода Хэмминга.