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

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

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

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

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

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

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

Код паритета

Легко включить (добавить) один бит четности либо слева от MSB, либо справа от LSB исходного битового потока. Существует два типа кодов четности, а именно четный код четности и нечетный код четности, в зависимости от типа выбранной четности.

Четный код

Значение четного бита должно быть равно нулю, если в двоичном коде присутствует четное количество единиц. В противном случае он должен быть один. Таким образом, четное число единиц присутствует в четном коде четности . Четный код четности содержит биты данных и четный бит четности.

В следующей таблице приведены коды четности, соответствующие каждому 3-битному двоичному коду. Здесь бит четности включен справа от LSB двоичного кода.

Здесь число битов, присутствующих в четных кодах четности, равно 4. Таким образом, возможное четное число единиц в этих четных кодах четности равно 0, 2 и 4.

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

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

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

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

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

Код нечетного паритета

Значение нечетного бита четности должно быть нулевым, если в двоичном коде присутствует нечетное число единиц. В противном случае, он должен быть один. Так что нечетное количество единиц присутствует в нечетном коде четности . Нечетный код четности содержит биты данных и нечетный бит четности.

В следующей таблице показаны нечетные коды четности, соответствующие каждому 3-битному двоичному коду. Здесь нечетный бит четности включен справа от LSB двоичного кода.

Здесь число битов, присутствующих в нечетных кодах четности, равно 4. Таким образом, возможное нечетное число единиц в этих нечетных кодах четности равно 1 и 3.

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

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

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

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

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

Код Хэмминга

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

Минимальное значение «k», для которого следующее соотношение является правильным (действительным), является не чем иным, как требуемым количеством битов четности.

$$2 ^ k \ geq n + k + 1$$

Куда,

«n» — количество бит в двоичном коде (информация)

‘k’ — количество бит четности

Следовательно, количество битов в коде Хэмминга равно n + k.

Пусть код Хэмминга равен $b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1}$ и битам четности $p_ {k}, p_ {k -1}, .... p_ {1}$. Мы можем поместить биты четности ‘k’ только в степени 2 позиции. В оставшихся битовых позициях мы можем разместить n бит двоичного кода.

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

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

• Найдите значение p ₁ , основанное на количестве единиц, присутствующих в позициях битов b ₃ , b ₅ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ⁰ .

• Найдите значение p ₂ , основанное на количестве единиц, присутствующих в позициях битов b ₃ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ¹ .

• Найдите значение p ₃ , основанное на количестве единиц, присутствующих в позициях битов b ₅ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ² .

• Аналогично найдите другие значения битов четности.

Найдите значение p ₁ , основанное на количестве единиц, присутствующих в позициях битов b ₃ , b ₅ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ⁰ .

Найдите значение p ₂ , основанное на количестве единиц, присутствующих в позициях битов b ₃ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ¹ .

Найдите значение p ₃ , основанное на количестве единиц, присутствующих в позициях битов b ₅ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ² .

Аналогично найдите другие значения битов четности.

Выполните эту процедуру для поиска контрольных битов .

• Найдите значение c ₁ , основанное на количестве единиц, присутствующих в битовых позициях b ₁ , b ₃ , b ₅ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ⁰ .

• Найдите значение c ₂ , основанное на количестве единиц, присутствующих в позициях битов b ₂ , b ₃ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ¹ .

• Найдите значение c ₃ , основанное на количестве единиц, присутствующих в позициях битов b ₄ , b ₅ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ² .

• Аналогично найдите другие значения контрольных битов.

Найдите значение c ₁ , основанное на количестве единиц, присутствующих в битовых позициях b ₁ , b ₃ , b ₅ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ⁰ .

Найдите значение c ₂ , основанное на количестве единиц, присутствующих в позициях битов b ₂ , b ₃ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ¹ .

Найдите значение c ₃ , основанное на количестве единиц, присутствующих в позициях битов b ₄ , b ₅ , b ₆ , b ₇ и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 ² .

Аналогично найдите другие значения контрольных битов.

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

Пример 1

Найдем код Хемминга для двоичного кода: d ₄ d ₃ d ₂ d ₁ = 1000. Рассмотрим четные биты четности.

Количество битов в данном двоичном коде равно n = 4.

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

$$2 ^ k \ geq n + k + 1$$

Подставим n = 4 в вышеприведенном математическом соотношении.

$$\ Rightarrow 2 ^ k \ geq 4 + k + 1$$

$$\ Rightarrow 2 ^ k \ geq 5 + k$$

Минимальное значение k, удовлетворяющее указанному выше соотношению, равно 3. Следовательно, нам требуется 3 бита четности p ₁ , p ₂ и p ₃ . Следовательно, количество битов в коде Хэмминга будет равно 7, поскольку в двоичном коде 4 бита и 3 бита четности. Мы должны поместить биты четности и биты двоичного кода в код Хэмминга, как показано ниже.

7-битный код Хэмминга : $b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} D_ {1} р- {2} bp_ {1}$

Подставляя биты двоичного кода, код Хэмминга будет $b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1}$. Теперь давайте найдем биты четности.

$$p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1$$

$$p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1$$

$$p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1$$

Подставляя эти биты четности, код Хэмминга будет иметь значение $b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011$.

Пример 2

В приведенном выше примере мы получили код Хэмминга в виде $b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011$. Теперь давайте найдем позицию ошибки, когда полученный код равен $b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111$.

Теперь давайте найдем контрольные биты.

$$c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1$$

$$c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1$$

$$c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0$$

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

$$c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10}$$

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