Коды обнаружения и исправления ошибок
Мы знаем, что биты 0 и 1 соответствуют двум разным диапазонам аналоговых напряжений. Таким образом, во время передачи двоичных данных из одной системы в другую также может добавляться шум. Из-за этого могут быть ошибки в полученных данных в другой системе.
Это означает, что бит 0 может измениться на 1 или бит 1 может измениться на 0. Мы не можем избежать помех от шума. Но мы можем сначала вернуть исходные данные, определив наличие каких-либо ошибок, а затем исправив эти ошибки. Для этого мы можем использовать следующие коды.
- Коды обнаружения ошибок
- Коды исправления ошибок
Error detection codes- используются для обнаружения ошибок, присутствующих в полученных данных (битовый поток). Эти коды содержат некоторые биты, которые включаются (добавляются) к исходному потоку битов. Эти коды обнаруживают ошибку, если она возникла при передаче исходных данных (битовый поток).Example - Код четности, код Хэмминга.
Error correction codes- используются для исправления ошибок, присутствующих в полученных данных (битовом потоке), чтобы мы получили исходные данные. Коды исправления ошибок также используют аналогичную стратегию кодов обнаружения ошибок.Example - Код Хэмминга.
Поэтому для обнаружения и исправления ошибок к битам данных во время передачи добавляются дополнительные биты.
Код четности
Легко включить (добавить) один бит четности либо слева от MSB, либо справа от LSB исходного потока битов. Существует два типа кодов четности, а именно код четности и код нечетной четности в зависимости от выбранного типа четности.
Код четности
Значение бита четности должно быть равно нулю, если в двоичном коде присутствует четное количество единиц. В противном случае он должен быть одним. Так что, четное количество единиц присутствует вeven parity code. Код четности содержит биты данных и бит четности.
В следующей таблице показаны even parity codesсоответствующий каждому 3-битному двоичному коду. Здесь бит четности включен справа от младшего разряда двоичного кода.
| Бинарный код | Бит четности | Код четности |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Здесь количество битов, присутствующих в кодах четности, равно 4. Таким образом, возможное четное количество единиц в этих кодах четности равно 0, 2 и 4.
Если другая система получает один из этих кодов четности, значит, в полученных данных нет ошибки. Биты, отличные от бита четности, такие же, как у двоичного кода.
Если другая система принимает коды четности, отличные от четных, то в полученных данных будет ошибка (и). В этом случае мы не можем предсказать исходный двоичный код, потому что нам неизвестны битовые позиции ошибки.
Следовательно, бит четности полезен только для обнаружения ошибки в полученном коде четности. Но этого недостаточно, чтобы исправить ошибку.
Код нечетной четности
Значение бита нечетной четности должно быть равно нулю, если в двоичном коде присутствует нечетное количество единиц. В противном случае он должен быть одним. Так что нечетное количество единиц присутствует вodd parity code. Код нечетной четности содержит биты данных и бит нечетной четности.
В следующей таблице показаны odd parity codesсоответствующий каждому 3-битному двоичному коду. Здесь бит нечетной четности включен справа от младшего разряда двоичного кода.
| Бинарный код | Бит нечетной четности | Код нечетной четности |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Здесь количество битов, присутствующих в кодах нечетной четности, равно 4. Таким образом, возможное нечетное количество единиц в этих кодах нечетной четности равно 1 и 3.
Если другая система получает один из этих кодов нечетной четности, значит, в полученных данных нет ошибки. Биты, отличные от бита нечетной четности, такие же, как у двоичного кода.
Если другая система принимает коды контроля четности, отличные от нечетных, значит, в полученных данных есть ошибка (и). В этом случае мы не можем предсказать исходный двоичный код, потому что нам неизвестны битовые позиции ошибки.
Следовательно, бит нечетной четности полезен только для обнаружения ошибки в принятом коде четности. Но этого недостаточно, чтобы исправить ошибку.
Код Хэмминга
Код Хэмминга полезен как для обнаружения, так и для исправления ошибок в полученных данных. Этот код использует несколько битов четности, и мы должны поместить эти биты четности в позиции степеней двойки.
В minimum value of 'k' для которого следующее соотношение является правильным (действительным) - не что иное, как необходимое количество битов четности.
$$ 2 ^ k \ geq n + k + 1 $$
Куда,
'n' - количество бит в двоичном коде (информации)
'k' - количество битов четности
Следовательно, количество битов в коде Хэмминга равно n + k.
Пусть Hamming codeэто $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & биты четности $ p_ {k}, p_ {k-1}, .... p_ {1} $. Мы можем разместить k битов четности только в степени 2. В остальных битовых позициях мы можем разместить n бит двоичного кода.
В зависимости от требований мы можем использовать либо четность, либо нечетность при формировании кода Хэмминга. Но тот же метод проверки четности следует использовать, чтобы определить, присутствует ли какая-либо ошибка в полученных данных.
Следуйте этой процедуре для поиска parity bits.
Найдите значение p1на основе количества единиц, присутствующих в позициях битов b 3 , b 5 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентных двоичных файлах имеют значение «1» вместо 2 0 .
Найдите значение p2, на основе количества единиц, присутствующих в битовых позициях b 3 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном формате имеют «1» вместо значения 2 1 .
Найдите значение p3, на основе количества единиц, присутствующих в битовых позициях b 5 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном формате имеют '1' вместо значения 2 2 .
Аналогичным образом найдите другие значения битов четности.
Следуйте этой процедуре для поиска check bits.
Найдите значение c 1 , основываясь на количестве единиц, присутствующих в позициях битов b 1 , b 3 , b 5 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентных двоичных файлах имеют '1' вместо значения 2 0 .
Найдите значение c 2 , основываясь на количестве единиц, присутствующих в битовых позициях b 2 , b 3 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном формате имеют «1» вместо значения 2 1 .
Найдите значение c 3 на основе количества единиц, присутствующих в битовых позициях b 4 , b 5 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном формате имеют '1' вместо значения 2 2 .
Аналогичным образом найдите другие значения контрольных битов.
Десятичный эквивалент контрольных битов в полученных данных дает значение битовой позиции, в которой присутствует ошибка. Просто дополните значение, присутствующее в этой битовой позиции. Следовательно, после удаления битов четности мы получим исходный двоичный код.
Пример 1
Найдем код Хэмминга для двоичного кода, d 4 d 3 d 2 d 1 = 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 1 , p 2 и p 3 . Следовательно, количество битов в коде Хэмминга будет 7, поскольку в двоичном коде 4 бита и 3 бита четности. Мы должны поместить биты четности и биты двоичного кода в код Хэмминга, как показано ниже.
В 7-bit Hamming code равно $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {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 $$
Подставляя эти биты четности, Hamming code будет $ 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 3 ) кода Хэмминга. Просто дополните значение этого бита и удалите биты четности, чтобы получить исходный двоичный код.