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