Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

Из примера можно сделать 2 важных вывода:

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

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

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

Пусть необходимо передать чисел: .

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

Отношение - называется скоростью кода.

В нашем примере .

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

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

;

.

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

Тогда

,

где - ошибочно принятый символ;

- возникшая в нем ошибка.

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

;

.

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

Если , то с помощью подстановки находим

; и .

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

Из примера следует:

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

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

При исправлении ошибок мы не сможем обнаружить более одной ошибки. В случае, когда ошибочны два и более символа данный метод коррекции не приемлем. Только обнаружение ошибки возможно, если ошибочны не более 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 Кбайт/с.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.