Принципы исправления ошибок

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Допустим, что нужно передать определенное количество цифр по каналу, в котором возможно возникновение ошибок, например 5, 6, 8. Если по каким либо причинам одна из цифр изменится, получатель не сможет обнаружить (и исправить) ошибку. Простейший путь обеспечения возможности обнаружения и исправления ошибки – это суммирование всех чисел и передача, кроме них самих, их суммы (19) по тому же каналу. Проверив сумму, получатель обнаружит ошибку. Он не сможет ее исправить и должен будет сделать повторный запрос. При этом только одна из цифр может быть ошибочной. Если ошибочны более чем одна цифра, то не во всех случаях ошибка может быть обнаружена. Улучшенный вариант может быть получен, если снова сложить все 4 цифры и передать вторую проверочную сумму.

-если необходима более надежная передача, то на это надо тратить больше времени;

-существует определенное ограничение на количество ошибочных цифр, которые можно обнаружить.

В примере показана возможность только обнаружения ошибки, однако существует возможность ее исправления.

Добавим

проверочных чисел:

, которые называются символами проверки на четность.

Исправление ошибки возможно, если разумным образом добавлены

проверочных символов.

Пусть

и выберем проверочные символы так, чтобы:

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

и допустим, что при передаче допущена только одна ошибка в символе

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

Если при передаче ошибки нет, т. е.

, то просто

Таким образом, ошибку можно исправить, поскольку

, а ошибочная позиция

-можно не только обнаруживать ошибки, но и исправлять их;

-можно применить различные стратегии декодирования: только обнаружение ошибок; исправление ошибок, если это возможно.

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

Таким образом, для исправления t ошибок кодовое слово должно содержать

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

В реально применяемых кодах используется арифметика конечных полей, или полей Галуа. Корректирующие коды часто основаны на коде Рида – Соломона.

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

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

Поясним процесс перемежения и деперемежения на простом примере.

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

Схема CIRC, используемая в музыкальных компакт-дисках и дисках данных CD-ROM, позволяет исправлять ошибки длиной до 3 874 бит, что составляет 2, 6 мм длины дорожки. Кроме того, использование метода интерполяции дает возможность исправлять ошибки длиной до 13 282 бит (или 8, 9 мм по длине дорожки). Интерполяция представляет собой процесс приблизительного вычисления или усреднения данных, позволяющий восстановить отсутствующие данные. Этот метод, конечно, не годится для компьютерных дисков CD-ROM, поэтому он применяется только в музыкальных компакт-дисках. Стандарт компакт-дисков Red Book определяет частоту блоков с ошибками (Block Error Rate — BLER) как отношение количества блоков с какими-либо ошибками (98 блоков в каждом секторе) ко времени их считывания, выраженному в секундах. Необходимо, чтобы полученное значение не превышало 220. Если это условие соблюдается, то компакт-диск, содержащий до 3% блоков с ошибками, все еще будет работоспособен.

Наличие дополнительного уровня обнаружения ошибок и схемы коррекции является характерной чертой музыкальных проигрывателей компакт-дисков и накопителей CD-ROM. Музыкальные проигрыватели преобразуют цифровые данные, хранящиеся на компакт-диске, в аналоговые сигналы, обрабатываемые стереофоническим усилителем. При использовании этой схемы некоторая неточность воспроизведения данных вполне допустима, так как человеческое ухо просто не в состоянии это услышать. В свою очередь, накопители CD-ROM не могут допустить какую-либо ошибку, так как каждый бит данных должен считываться предельно точно. Поэтому компакт-диски CD-ROM, наряду с основными данными, содержат большой объем дополнительной информации ЕСС. Код коррекции ошибок (ЕСС) позволяет выявлять и исправлять большинство мелких ошибок, повышая тем самым надежность и точность обработки данных до уровня, приемлемого для хранения данных.

При воспроизведении музыкального компакт-диска отсутствующие данные могут быть интерполированы, т. е. существует определенный шаблон данных, позволяющий “угадать” отсутствующие значения. Например, если три значения данных музыкального компакт-диска выражены серией последовательных чисел 10, 13 и 20, а среднее значение из-за повреждения или загрязнения поверхности диска пропущено, то его можно с достаточной степенью точности определить как 15, т. е. среднее арифметическое чисел 10 и 20. Хотя значение восстановлено неточно, слушатель не заметить этой погрешности при воспроизведении звуковой записи. Если же аналогичные значения будут на компакт-диске CD-ROM в исполняемой программе, то определить правильное значение средней выборки не получится. Метод интерполяции здесь не работает, так как команды или данные исполняемой программы должны быть безошибочны; в противном случае произойдет повреждение программы или неверное считывание данных, необходимых для выполнения вычислений. Использование ранее описанного метода при считывании исполняемой программы с диска CD-ROM практически невозможно.

Диск CD-ROM, наряду с основными данными, содержит дополнительную информацию, введенную в каждый сектор и применяемую для выявления и исправления ошибок, а также для более точного определения секторов данных. Для этого из 2 352 байт каждого сектора, используемых первоначально для хранения звуковых данных, 304 байта применяются для синхронизации (синхронизирующие биты), идентификации (биты идентификации), кода коррекции ошибок (ЕСС), обнаружения и исправления ошибок (EDC). Фактически в каждом секторе остается 2 048 байта пользовательских данных. За одну секунду считывается 75 секторов, поэтому базовая скорость считывания данных с компакт-дисков CD-ROM достигает 2 048 × 75 = 153 600 байт в секунду, что составляет 153, 6 Кбайт/с.