Хэмминга CodeОбнаружение и исправление ошибок на примерах.

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

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

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

Типы ошибок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Циклическая избыточная проверка (CRM) добавляет последовательность избыточных битов в конец блока данных таким образом, чтобы полученный блок данных стал делиться нацело на второе, заранее определенное двоичное число.

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

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

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

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

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

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

Применение теории Хэмминга Code

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

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

Преимущества Хэмминга Code

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

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

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

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

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

• Рассчитайте общее количество избыточных битов.
• Определите положение избыточных битов.
• Вычислите значение каждого избыточного бита.

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

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

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

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

Шаг 2) Разместите лишние биты на своих местах.

Избыточные биты p размещаются в позициях, являющихся степенями двойки — например, 1, 2, 4, 8 и 16. Они обозначаются как p.₁ (в позиции 1), п₂ (в позиции 2), п₃ (на позиции 4) и так далее.

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

Каждый избыточный бит — это бит четности, который делает количество единиц в своей группе либо четным, либо нечетным. Существует два типа контроля четности:

• Равный паритет: Общее количество единиц в закрытых позициях становится четным.
• Нечетная четность: Общее количество единиц в закрытых позициях становится нечетным.

Каждый бит четности охватывает определенный набор позиций, определяемый двоичным представлением номеров позиций:

• p₁ Проверяет каждую позицию, двоичное значение которой имеет единицу в младшем значащем бите — позиции 1, 3, 5, 7, 9, 11 и так далее.
• p₂ Проверяет каждую позицию, двоичное значение которой имеет единицу во втором бите справа — позиции 2, 3, 6, 7, 10, 11 и так далее.
• p₃ Проверяет каждую позицию, двоичное значение которой содержит единицу в третьем бите справа — позиции с 4 по 7, с 12 по 15 и так далее.

Пример решения (7,4): Рассмотрим четыре бита данных. 1011Требуется три бита четности (2)³ = 8 ≥ 4 + 3 + 1), что дает семибитное кодовое слово, представленное в виде p₁ p₂ d₁ p₃ d₂ d₃ d₄Размещение данных приводит к позициям 3, 5, 6, 7 = 1, 0, 1, 1. Используя четность: p₁ охватывает позиции 1, 3, 5, 7 (биты 1, 0, 1 → p)₁ = 0); п₂ охватывает 2, 3, 6, 7 (биты 1, 1, 1 → p)₂ = 1); п₃ охватывает 4, 5, 6, 7 (биты 0, 1, 1 → p)₃ = 0). transmitТаким образом, кодовое слово Теда — это 0110011.

Как расшифровать сообщение в теории Хэмминга Code

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

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

Шаг 1) Подсчитайте количество избыточных битов. Используйте ту же формулу, что и для кодирования: 2^p ≥ n + p + 1, где n — количество битов данных, а p — количество избыточных битов.

Шаг 2) Правильно расположите все лишние детали. Каждый избыточный бит находится в позиции, являющейся степенью двойки — например, 1, 2, 4 и 8.

Шаг 3) Выполните проверку четности. Биты четности пересчитываются на основе битов данных и полученных избыточных битов:

• p₁ = parity(1, 3, 5, 7, 9, 11, …)
• p₂ = parity(2, 3, 6, 7, 10, 11, …)
• p₃ = parity(4–7, 12–15, 20–23, …)

Пересчитанные биты четности вместе образуют двоичное число. Если это число равно нулю, ошибки нет; в противном случае его значение указывает точное положение единственного поврежденного бита, который затем инвертируется для исправления сообщения.

Часто задаваемые вопросы (FAQ)