Коды Рида — Соломона (англ.
Reed–Solomon codes) — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не
биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с
байтами (октетами).
История
Код Рида — Соломона был изобретён в 1960 году сотрудниками лаборатории Линкольна
Массачусетского технологического института Ирвином Ридом и Густавом Соломоном. Идея использования этого кода была представлена в статье «Polynomial Codes over Certain Finite Fields». Эффективные алгоритмы декодирования были предложены в 1969 году Элвином Берлекэмпом и Джэймсом Месси (алгоритм Берлекэмпа — Мэсси) и в 1977 году Давидом Мандельбаумом (метод, использующий Алгоритм Евклида). Первое применение код Рида — Соломона получил в 1982 году в серийном выпуске
компакт-дисков.
Где используется
Благодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин, либо передать информацию в условиях связи с большим количеством помех. В среднем для компакт-диска избыточность кода (т.е. количество дополнительных символов, благодаря которым информацию можно восстанавливать) составляет примерно 25%. Восстановить при этом можно количество данных, равное половине избыточных. Если емкость диска 700 Мб, то, получается, теоретически можно восстановить до 87,5 Мб из 700. При этом нам не обязательно знать, какой именно символ передан с ошибкой. Также стоит отметить, что вместе с кодированием используется перемежевание, когда байты разных блоков перемешиваются в определенном порядке, что в результате позволяет читать диски с обширными повреждениями, локализированными близко друг к другу (например, глубокие царапины), так как после операции, обратной перемежеванию, обширное повреждение оборачивается единичными ошибками во множестве блоков кода, которые поддаются восстановлению.
Этот алгоритм кодирования используется при передаче данных по сетям
WiMAX, в
оптических линиях
связи, в спутниковой и радиорелейной связи. Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида — Соломона.
© greenmile
Источники:
habr.com,
ru.wikipedia.org
В начало
