Алгоритмы исправления ошибок в компьютерных системах и сетях

1.

Алгоритмы исправления ошибок в
компьютерных системах и сетях.

2.

Что такое алгоритмы исправления ошибок?
• Алгоритмы, разработанные для обнаружения и исправления ошибок в передаваемых данных.
• Зачем они нужны:
Обеспечивают целостность и надежность передачи информации в условиях возможных
искажений или потерь.
Важность в компьютерных системах и сетях:
В компьютерных системах и сетях передача данных подвержена различным видам помех, таким
как электромагнитные воздействия, шумы на канале связи, ошибки в программном обеспечении
и многие другие.
Алгоритмы исправления ошибок позволяют минимизировать влияние этих факторов на
надежность передачи данных и обеспечивают стабильную работу систем и сетей.

3.

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

4.

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

5.

Принцип работы
1) Представление слова в бинарном виде
2) Разбиение на блоки по 16 бит.
В данном примере получается 2 блока по
16 бит: “ha”(01000100 00111101) и
“br”(00111110 01001000)

6.

Принцип работы
3) Расстановка контрольных битов. № Контрольного бита равен числу степени 2:
20(1), 21 (2), 22 (4), 23 (8) и т.д.

7.

Принцип работы
4) Вычисление значения контрольного бита на примере блока “ha”.
Буквой X помечены контролируемые биты. Контроль битов происходит с № контрольного бита, на № битов и
через № битов. Т.е. с 1 бита(он же контрольный) контролируется количество битов равное номеру контрольного
бита(1) с промежутком в 1 бит. Так же для 2, 4, 8 и 16.

8.

Принцип работы
4) Вычисление значения контрольного бита на примере блока “ha”.
Для вычисления чему будет равен контрольный бит, нужно узнать сколько единиц контролирует каждый контрольный бит.
• Первый контрольный бит(1) будет равен единице(1). Т.к. он контролирует 5 единиц(нечетное) в кодовом слове.
• Второй контрольный бит(2) будет равен нулю(0). Т.к. он контролирует 4 единицы(чётное) в кодовом слове.
• Третий контрольный бит(4) будет равен единице(1). Т.к. он контролирует 3 единицы(нечётное) в кодовом слове.
• Четвертый контрольный бит(8) будет равен нулю(0). Т.к. он контролирует 2 единицы(чётное) в кодовом слове.
• Пятый контрольный бит(16) будет равен нулю(0). Т.к. он контролирует 4 единицы(чётное) в кодовом слове.

9.

Принцип работы
5) Высчитав контрольные биты для нашего информационного слова получаем следующее:

10.

Декодирование и исправление ошибок
Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно
пришло к нам с ошибкой. К примеру, мы получили такое (11-ый бит передался неправильно):
Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные
биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так,
посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:

11.

Декодирование и исправление ошибок
1)
2)
Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими
же контрольными битами, которые мы получили. Теперь просто сложив номера
позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию
ошибочного бита.
Теперь просто инвертировав его и отбросив контрольные биты, мы получим
исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со
второй частью сообщения.

12.

CRC алгоритм
Что такое CRC алгоритм?
CRC (Cyclic Redundancy Check) — это метод обнаружения ошибок в передаваемых данных
путем добавления к данным некоторой последовательности бит, которая вычисляется из
самих данных. При получении данных, приемник также вычисляет CRC и сравнивает
полученное значение с переданным. Если значения не совпадают, это указывает на
наличие ошибок в передаче данных.
Он широко используется в проводных и беспроводных сетях, и в устройствах хранения
данных, для проверки информации на подлинность и защиты от несанкционированного
изменения.

13.

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

14.

Обнаружение ошибок
1) К примеру, вычисление по этому алгоритму CRC для исходной последовательности
1101001110010110100
2) Выбор полинома CRC. В нашем случае выбираем полином 1011, который является
полиномом CRC-4-ITU. Также его можно представить x4+x+1. Этот полином является
полиномом 3 степени.
3) Добавление нулей к данным, а именно в количестве 3 нулей равным степени
полинома. 1101001110010110100+000.
Примечание: Данные нули гарантируют, что все биты исходной
последовательности примут участие в процессе формирования значения CRC.

15.

Обнаружение ошибок
4) Формирование выходной последовательности.
5) Выходные данные: 1101001110010110100011.
001 является тем самым CRC, который записывается
в конец выходных данных, в последующем для
обнаружения ошибок.
6) Заключительным этапом будет проверка у
Получателя. Получатель получает данные в виде
последовательности равной 1101001110010110100011
и полином равным 1011. Если при делении остаток
равен 0, значит, данные передались без ошибок,
если остаток отличный от нуля, то произошла
ошибка при передаче данных. И в дальнейшем
Получатель отправляет повторный запрос.

16.

Другие виды алгоритмов
1. Коды Рида-Соломона:
• Эти коды являются расширением кодов БЧХ и предоставляют еще большую
надежность исправления ошибок.
• Они широко используются в цифровых системах передачи данных, таких как
компакт-диски, цифровые видео и т. д.
2.Коды БЧХ (Боуза-Чоудхури-Хоквингема):
• Эти коды используются для исправления более сложных ошибок, включая
множественные ошибки.
• Они базируются на полиномиальных операциях и имеют высокую степень коррекции
ошибок.

17.

Другие виды алгоритмов
3. Турбокоды и коды LDPC (Low-Density Parity-Check):
• Эти коды являются более современными и эффективными схемами исправления
ошибок, используемыми в современных беспроводных коммуникационных системах
и стандартах передачи данных.
• Они обеспечивают высокую скорость передачи данных и надежность при условии
существенного снижения энергопотребления.
4. Коды Рида-Маллера:
• Эти коды являются расширением кодов Хэмминга и обеспечивают более высокую
степень коррекции ошибок.
• Они часто используются в цифровых сетях передачи данных и некоторых хранилищах
данных.