Коррекция ошибок Рида-Соломона
Коррекция ошибок Рида-Соломона - это прямой код коррекции ошибок. Он работает путем передискретизации полинома, построенного на основе данных. Полином оценивается в нескольких точках, и эти значения отправляются или записываются. Выборка полинома чаще, чем это необходимо, делает полином переопределенным. Если "многие" точки получены правильно, приемник может восстановить исходный полином даже при наличии "нескольких" плохих точек.
Коды Рида-Соломона используются во многих различных коммерческих приложениях, например, в CD, DVD и Blu-ray Discs, в технологиях передачи данных, таких как DSL и WiMAX, и в системах вещания, таких как DVB и ATSC.
Обзор
Коды Рида-Соломона являются блочными кодами. Это означает, что фиксированный блок входных данных обрабатывается в фиксированный блок выходных данных. В случае наиболее часто используемого R-S кода (255, 223) - 223 входных символа Рида-Соломона (каждый длиной восемь бит) кодируются в 255 выходных символов.
- Большинство схем R-S ECC являются систематическими. Это означает, что некоторая часть выходного кодового слова содержит входные данные в их исходной форме.
- Размер символа Рида-Соломона в восемь бит был выбран потому, что декодеры для больших размеров символов было бы трудно реализовать с помощью текущей технологии. Такой выбор конструкции заставляет наибольшую длину кодового слова составлять 255 символов.
- Стандартный (255, 223) код Рида-Соломона способен исправлять до 16 ошибок символов Рида-Соломона в каждом кодовом слове. Поскольку каждый символ фактически состоит из восьми бит, это означает, что код может исправить до 16 коротких всплесков ошибок, вызванных внутренним конволюционным декодером.
Код Рида-Соломона, как и конволюционный код, является прозрачным кодом. Это означает, что если символы канала были инвертированы где-то на линии, декодеры все равно будут работать. Результатом будет дополнение к исходным данным. Однако код Рида-Соломона теряет свою прозрачность, если используется виртуальное нулевое заполнение. По этой причине перед декодированием Рида-Соломона обязательно должен быть определен смысл данных (т.е. истинные или дополненные).
В случае программы Voyager R-S коды достигают почти оптимальной производительности при конкатенации с (7, 1/2) сверточным (Витерби) внутренним кодом. Поскольку для каждой исправляемой ошибки требуется два контрольных символа, это приводит к тому, что на одно кодовое слово приходится 32 контрольных символа и 223 информационных символа.
Кроме того, кодовые слова Рида-Соломона могут чередоваться на основе символов перед сверточным кодированием. Поскольку это разделяет символы в кодовом слове, становится менее вероятным, что всплеск от декодера Витерби нарушит более одного символа Рида-Соломона в одном кодовом слове.
Основная идея
Ключевая идея кода Рида-Соломона заключается в том, что кодируемые данные сначала представляются в виде многочлена. Код опирается на теорему из алгебры, которая гласит, что любые k различных точек однозначно определяют многочлен степени не более k-1.
Отправитель определяет полином степени k - 1 {\displaystyle k-1}
над конечным полем, который представляет k {\displaystyle k}
точек данных. Затем полином "кодируется" путем его оценки в различных точках, и эти значения являются тем, что фактически передается. Во время передачи некоторые из этих значений могут быть повреждены. Поэтому на самом деле передается больше, чем k точек. Если достаточное количество значений получено правильно, приемник может определить, каким был исходный полином, и декодировать исходные данные.
В том же смысле, в котором можно исправить кривую, интерполируя пробел, код Рида-Соломона может преодолеть серию ошибок в блоке данных, чтобы восстановить коэффициенты полинома, который нарисовал исходную кривую.
История
Код был изобретен в 1960 году Ирвингом С. Ридом и Густавом Соломоном, которые в то время работали в лаборатории Линкольна Массачусетского технологического института. Их основополагающая статья называлась "Полиномиальные коды над определенными конечными полями". Когда она была написана, цифровые технологии не были достаточно развиты, чтобы реализовать эту концепцию. Первым применением RS-кодов в массовых продуктах в 1982 году стал компакт-диск, где используются два чередующихся RS-кода. Эффективный алгоритм декодирования RS-кодов на больших расстояниях был разработан Элвином Берлекампом и Джеймсом Мэсси в 1969 году. Сегодня RS-коды используются в жестких дисках, DVD, телекоммуникациях и протоколах цифрового вещания.
