Вездесущие коды Рида-Соломона

http://www.eccpage.com/reed_solomon_codes.html
  • Перевод
Перевод статьи Barry A. Cipra «The Ubiquitous Reed-Solomon Codes» из журнала «SIAM news», подшивка 26-1, январь 1993 года.
*****

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

Однако, многие люди, использующие современные технологии, могут и не догадываться о важности пятистраничной статьи, появившейся в 1960 году в журнале Общества промышленной и прикладной математики. В этой статье под названием «Полиномиальные коды над некоторыми конечными полями» Ирвин Рид и Густав Соломон, будущие сотрудники лаборатории Линкольна Массачусетского технологического института, представили идеи, которые лежат в основе современных методов исправления ошибок, применяемых в различном оборудовании, начиная с компьютерных жестких дисков и заканчивая проигрывателями компакт-дисков. Коды Рида-Соломона (и, конечно, высокое инженерное искусство) сделали возможным отправку фотографий внешних планет солнечной системы с космического аппарата Вояджер-2 на Землю. Они дают возможность наслаждаться музыкой с поцарапанного компакт-диска. И в недалеком будущем они позволят ненасытным кабельным телевизионщикам впихнуть в свои системы более 500 каналов, а здесь и без того непаханое поле.

Краткая справка
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).

Код Рида — Соломона является частным случаем БЧХ-кода.

В настоящее время широко используется в системах восстановления данных с компакт-дисков, при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании.
Подробности — Код Рида — Соломона


«Если мы говорим о CD-проигрывателях и цифровых аудио-лентах, а также о цифровом телевидении и многих других новейших системах цифрового изображения, то для всего этого необходимо использование кодов Рида-Соломона в качестве неотъемлемой части системы», – говорит Роберт МакЭлис, эксперт по теории кодирования отделения электротехники Калифорнийского технологического института.

Почему? Потому что цифровая информация, виртуальная по определению, состоит из массива «бит» – 0 (нулей) и 1 (единиц) – и физического устройства. А любое физическое устройство, как бы хорошо оно ни было изготовлено, иногда способно путать биты. К примеру, Вояджер-2 обладал невероятно низкой мощностью передатчика – данные на десятки миллионов километров передавались почти шепотом. Дисковые накопители упаковывают данные настолько плотно, что можно (фактически) понять считывающую/записывающую головку, когда она не может сказать, где заканчивается один бит и начинается следующая единица (или ноль). При тщательном подходе к проектированию частота появления ошибок снижается, скажем так, до очень низкого уровня, который можно не принимать в расчет – промышленный стандарт для жестких дисков составляет 1 к 10 млрд. Но, учитывая объемы обработки информации в наши дни, этот «незначительный» уровень впоследствии может стать причиной ежедневных аварий. Коды, исправляющие ошибки, являются своего рода сеткой безопасности – математической страховкой от превратностей несовершенного материального мира.

Ключом к коррекции ошибок является избыточность. Действительно, простейший код коррекции ошибок – это простое повторение всего несколько раз. Если, к примеру, вы ожидаете возникновения не более одной ошибки при пересылке, то повторение каждого бита три раза и «голосование большинством» на принимающем конце гарантирует, что сообщение будет услышано правильно (например, 111 000 011 111 будет правильно услышано как 1011). В общем случае n ошибок может быть скомпенсировано путем повторения чего-то 2n + 1 раз.

Но такая коррекция ошибок «в лоб» препятствовала бы цели высокоскоростной, высокоплотной обработки информации. Можно было бы предпочесть подход, при котором добавляется только несколько дополнительных бит к исходному сообщению. Конечно, вы не можете всегда получать то, что хотите, – напоминает Мик Джаггер, – но если вы пробуете, то иногда, в самом деле, можете найти то, что вам нужно. Успех кодов Рида-Соломона подтверждает это.

К 1960 году теория кодов коррекции ошибок просуществовала всего около десяти лет. Основная теория надежной цифровой связи была сформулирована Клодом Шенноном в конце 1940-х годов. В то же самое время, Ричард Хемминг представил изящный подход к коррекции одиночных ошибок и обнаружению двойной ошибки. В течение 1950-х годов большое количество исследователей начало экспериментировать со множеством кодов коррекции ошибок. Но, по словам МакЭлиса, со своей статьей в журнале «SIAM» Рид и Соломон «сорвали куш».

Наградой же стала система кодирования, основанная на группах бит, таких как байты, вместо отдельных нулей и единиц. Эта особенность делает коды Рида-Соломона особенно полезными для противодействия групповым ошибкам: шесть последовательных битовых ошибок, например, могут затронуть максимум два байта. Так что даже версия кода Рида-Соломона с коррекцией двойной ошибки может обеспечить достаточный запас прочности. (Существующая реализация кодирования Рида-Соломона в технологии компакт-дисков позволяет преодолевать групповые ошибки длиной вплоть до 4000 последовательных бит.)

Математически, коды Рида-Соломона основаны на арифметике конечных полей. Действительно, статья 1960 года начинается с определения кода как «отображение векторного пространства размерности m над конечным полем K на векторное пространство более высокой размерности над тем же самым полем.» Начиная с исходного «сообщения» (a_0, a_1, ..., a_{m-1}), где каждое a_k является элементом поля K, кодирование Рида-Соломона порождает (P(0), P(g), P(g^2), ..., P(g^{N-1}), где N это количество элементов в K, g это генератор цикличной непустой группы в K, и P(x) это полином a_0+a_1*x+...+a_{m-1}x^{m-1}. Если N больше m, то значения P переопределяют полином, и свойства конечных полей гарантируют, что коэффициенты полинома, то есть исходное сообщение, могут быть восстановлены по любым m значениям.

Концептуально, код Рида-Соломона определяет полином путем изображения большого количества точек. И так же, как на глаз можно распознать и исправить несколько «плохих» точек в том, что является четкой параболой, код Рида-Соломона может определить неправильные значения P и все еще восстановить оригинальное сообщение. Капелька комбинаторного рассуждения (и немного линейной алгебры) устанавливает, что этот подход может исправить до s ошибок, пока m, длина сообщения, является строго менее чем N — 2s.

В сегодняшнем байто-размерном мире, например, имеет смысл определить K как поле степени 8 по Z_2, так что каждый элемент K соответствует одному байту (на компьютерном жаргоне, есть четыре бита в полубайте и два полубайта в байте). В этом случае, N = 2^8 = 256, и следовательно сообщения длиной в 251 байт могут быть восстановлены, даже если происходят две ошибки в передаче значений P(0), P(g),.. ., P(g^{255}). Это намного лучше, чем 1255 байт, требуемых при подходе «говорить-все-пять-раз».

Несмотря на свои преимущества, коды Рида-Соломона начали использоваться не сразу – они дожидались момента, когда аппаратные технологии станут более совершенными. «В 1960 году не было такого понятия, как быстрая цифровая электроника», – во всяком случае, она была не такого уровня, как сегодня, говорит МакЭлис. В работе Рида-Соломона «было предложено несколько интересных способов обработки данных, но никто не знал, осуществимо это или нет, а в 1960 году, наверное, это было неосуществимо».

Но технологии были усовершенствованы и множество исследователей начало работу по реализации кодов. Одной из ключевых фигур был Элвин Берлекэмп, профессор электротехники в Университете Калифорнии в Беркли, который изобрел эффективный алгоритм декодирования кода Рида-Соломона. Алгоритм Берлекэмпа был использован в Вояджере-2, и на его основе построено декодирование в проигрывателях компакт-дисков. Ко всему прочему, были добавлены многочисленные «навороты» (некоторые имеют фундаментальную теоретическую значимость). В компакт-дисках, например, используется версия кода Рида-Соломона с перекрестным чередованием, называемая CIRC.

Рид, ныне профессор электротехники в Университете Южной Калифорнии, по-прежнему работает над проблемами в теории кодирования. Соломон, недавно покинувший фирму «Хьюз эйркрафт компани», консультирует Лабораторию реактивного движения. Рид был в числе первых, кто увидел абстрактную алгебру в качестве основы для кодов, исправляющих ошибки.

«Оглядываясь назад, это кажется очевидным» – рассказал он «SIAM news». Тем не менее, он добавил: «когда мы публиковали статью, теория кодирования не являлась предметом обсуждения». Оба автора понимали, что был достигнут хороший результат, но они не имели представления о том, какое влияние окажет их статья. Спустя три десятилетия мы его видим. Огромное множество применений, уже существующих и планируемых, решили вопрос практичности и значимости кодов Рида-Соломона. «Ясно, что они практичны, потому что теперь их использует каждый» — говорит Берлекэмп. Миллиарды долларов в современной технологии зависят от идей, основанных на оригинальной работе Рида и Соломона. Одним словом, «это была архиважная статья», как считает МакЭлис.

— Перевод: © Wio, intnzy, aidsfrag.
Поделиться публикацией

Похожие публикации

Комментарии 22
  • НЛО прилетело и опубликовало эту надпись здесь
    +1
    > имеет смысл определить K как поле степени 8 по Z_2

    Мне кажется, в русском языке не принято такое название. Я так понимаю, речь идёт о поле F_256, оно же GF(2^8), правильно я понимаю?
      0
      в этом месте вообще корявый перевод «over» почему-то переведено не «над», а «по», хотя причем тут «по» совершенно непонятно.
        0
        Что такое «поле степени 8 над полем» я вообще не в состоянии понять.
          0
          если я правильно понимаю, мы говорим, что K поле степени n над k, если степень расширения K/k равна n. Посмотрите статью википедии (http://en.wikipedia.org/wiki/Degree_of_a_field_extension) о степенях расширений.
            0
            А, в этом смысле понятно. Но всё равно лучше так не писать.
              0
              Это устоявшаяся математическая терминология. Почему так не надо писать?
                0
                Имея в виду конкретное поле F_256, надо писать F_256. Особенно если основным полем именно оно и выступает, а не F_2. Там вон дальше многочлены сразу над F_256, так что конструкции вроде «многочлены <..> над полем <..> над полем» выглядят противоестественно.
      +4
      я нифига не понял ><
        0
        БЧХ и РС коды здорово мне подпортили нервы на сессии на 3м курсе…
        Из этой статьи не очень понятно конечно что к чему. Неплохо было бы к хабру рендер формул припаять
          +1
          В оригинале ошибка, которая перекочевала в перевод: все P(0) следует исправить на P(1), что равно P(g^0).

          Вообще, на мой взгляд, в английской вики объяснение доходчивее…
            +1
            Заметьте — опубликовали статью, их наработками пользуются миллиарды людей, компании зарабатывают триллионы долларов, а авторы, почему-то, еще не миллиардеры.

            Не то что копирасты, которые один раз подгребут под себя некий высосанный из пальца объект «intellectual property» и всю жизнь хотят с него жить.
              0
              «Капелька комбинаторного рассуждения (и немного линейной алгебры) устанавливает, что этот подход может исправить до s ошибок, пока m, длина сообщения, является строго менее чем N — 2s.»

              Что есть N в этом высказывании?
                0
                Блин, как мозг взрывался на теории кодирования, когда вручную это всё делали и выясняли, так и при прочтении статьи, чувствую, что если пытаться опять всё понять, то уборщица замучается остатки мозга со стенок отскребать o_O
                  0
                  Стоит ещё вспомнить о том, что циклические коды и cyclic redundancy check (AKA «CRC») используются например в ethernet карточках — пример поближе каждому ИТ-шнику нежели Вояджер и компакт диски (я считаю).
                    +1
                    Сочетание неуклюжего перевода и нагромождения математики не оставляет шансов на понимание статьи.
                      –1
                      Однако, многие люди, использующие современные технологии, могут и не догадываться о важности пятистраничной статьи, появившейся в 1960 году в журнале Общества промышленной и прикладной математики. В этой статье под названием «Полиномиальные коды над некоторыми конечными полями»

                      Логично.
                        0
                        Хороший пример восстанавливающих кодов,

                        www.quickpar.org.uk/
                        en.wikipedia.org/wiki/PAR2

                        В Практике использовал :)очень экономит трафик, когда rsync не способен =) делать магию


                          0
                          Да, не думал что после ВУЗа меня коснется такие, на первый взгляд, сугубо теоретические вещи, как коды Рида-Соломона. Но буквально сразу же, при написании своих фреймворков для формирования штрих-кодов, вплотную с ними столкнулся для восстановления ошибок печати/хранения и т.п. Потрясающий эффект! Например удавалось считывать значения штрихкода PDF417 после отрыва более половины площади штрихкода!

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое