Получение образующего полинома для кода рида соломона. Коды Рида-Соломона

Дороги из пластмассы. Речь не про детский конструктор лего. Подобные проекты с успехом реализованы в Индии и Нидерландах. Настала ли очередь России? Ещё в апреле депутат Госдумы от ЛДПР Александр Старовойтов решил, что да. И отправил соответствующий запрос в Росавтодор. Лайф связался с ведомством и выяснил, как продвигается дело и кто поборется за право проложить пластмассовые дороги по самой большой стране мира.

Реальное продолжение "пластиковых" идей

Депутат Старовойтов не просто любитель инноваций. Ему по статусу положено искать пути решения одной из двух исконных русских проблем. Всё-таки зампред Комитета Госдумы по транспорту как-никак. В разговоре с Лайфом парламентарий сказал, что один из главных плюсов голландского проекта - это то, что "полотно будет сделано из материала, созданного из пластиковых отходов, добавленных в состав асфальта. Это улучшит качество дороги и сократит выбросы в атмосферу углекислого газа".

Инициатива была отправлена в Росавтодор ещё в апреле. В ведомстве Лайфу заявили, что с предложенным Старовойтовым к рассмотрению проектом уже ознакомились и сочли его интересным. Но с кое-какими поправками.

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

Одни плюсы?

Проект, рассмотренный Росавтодором, принадлежит перу инженеров голландской компании VolkerWessels. Он носит незамысловатое для любого англоговорящего человека название PlasticRoad (в переводе на русский - "Пластиковые дороги").

В VolkerWessels Лайфу сообщили, что при строительстве дорог предлагается использовать отдельные полые блоки, отлитые из переработанных пластиковых отходов. Такая схема должна гарантировать практически идеальное качество покрытия, а при необходимости блок можно с лёгкостью заменить на новую "запчасть".

Дорогу вполне реально построить за недели, а не за месяцы, как её асфальтового "собрата". И служить она будет в три раза дольше. Кроме того, по мнению голландцев, важным аргументом в пользу строительства является снижение выбросов углекислого газа в атмосферу во время строительства и утилизация пластикового мусора.

Ежегодно в атмосферу во всём мире "улетает" около 1,6 Мт СО2 - что составляет 2% от всех транспортных выбросов. Пока голландский проект так и остался на бумаге и от Росавтодора производители не дождались конкретики. Но разработчик технологии не теряет надежды реализовать его в течение пары лет в Роттердаме, добавили в разговоре с Лайфом в VolkerWessels. В этой связи в компании не смогли назвать себестоимость строительства такого дорожного покрытия. Но опрошенные Лайфом эксперты сошлись в том, что стоимость прокладки одного километра полотна с применением "пластиковой технологии" будет от 3 до 5% дороже "классического" варианта.

По мнению специалистов Росавтодора, необходима также специальная нормативно-правовая база, позволяющая использовать переработанный пластик в дорожном строительстве, разработка которой также невозможна без результатов испытаний в российских условиях.

Член Общественной палаты Московской области, заместитель руководителя экспертного центра Рrobok.net Андрей Мухортиков также считает, что идея голландцев заслуживает самого пристального внимания:

- Конечно, прежде всего необходимо обеспечить устойчивость такого покрытия к перепадам температур, хороший коэффициент сцепления с шинами, прочность и долговечность, - говорит эксперт. - И если по этим показателям удастся приблизиться или превзойти результаты асфальта, то применение пластикового покрытия не только улучшит характеристики дорог и удешевит их, но ещё и решит проблему вторичной переработки огромных объёмов пластика, накопленных человечеством.

Армия нам поможет

Как выяснил Лайф, Росавтодор рассматривает не только голландский проект. Выбрать есть из чего, ведь подобные технологии уже применяются во многих странах мира. В частности, в Индии.

Первая "пластиковая" дорога Jambulingam Street, построенная в 2002 году, уже успела стать местной легендой, без особых разрушений пережив бессчётное количество наводнений, несколько муссонов, постоянное тепловое воздействие и непрерывный поток автомобилей, грузовиков и авторикш. Патент на технологию строительства такой дороги в 2006 году получил Thiagarajar College of Engineering. Как стало известно Лайфу, компания уже направила предложение в Росавтодор.

В Канаде пластиковые отходы перерабатывают в воскообразное вещество, которым впоследствии заливают дорогу вместе с асфальтовой смесью. Плотность и долговечность подобного "воскового" асфальта ничем не уступает обычному. Стоимость производства такого дорожного покрытия не отличается от стоимости производства обычного асфальтового покрытия. Патент на технологию принадлежит компании GreenMantra, получившей в 2013 году от Правительства Канады инвестиции в размере $750 тыс. на развитие новой технологии.

В России придумали делать временные дороги из полимерных материалов. Пока технология, разработанная ГК "Рускомпозит", востребована армией РФ. Но, как рассказали Лайфу в компании, они могут "подогнать" её под гражданские нужды.

- Это аналог дорожных плит, которые чаще привыкли производить из железобетона, только из полимерных композитов, - сказала Лайфу пресс-секретарь "Рускомпозита" Наталья Некрасова. - Из-за особенностей материалов и строения мобильные дорожные покрытия легче железобетонных почти в пять раз, обладают положительной плавучестью и могут использоваться при строительстве временных дорог даже на болотной местности. Один километр временной дороги из таких композитных плит можно проложить за 24-36 часов. При этом сами мобильные дорожные покрытия могут быть использованы многократно: после завершения работ или проезда техники массой до 80 тонн по одному участку, временная дорога может быть демонтирована и перенесена на другой участок.

В Росавтодоре проект "Рускомпозита" также был рассмотрен. Как нам сообщили в компании, у них есть достаточно возможностей для воплощения в жизнь не только своего, но и иностранных проектов. Причём с учётом российских погодных реалий. Однако планируемый бюджет в "Рускомпозите" назвать отказались.

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

Добрый день! Меня зовут Максим, в YADRO, кроме всего прочего, я занимаюсь разработкой подсистемы, отвечающей за надежное хранение данных. Готовлю небольшой цикл статей про коды Рида-Соломона - теоретическую основу, практическую реализацию, применяемые на практике программные и аппаратные оптимизации. На Хабре и в остальной сети есть хорошие статьи по вопросам этой области - но по ним сложно разобраться, если ты новичок в теме. В этой статье я попытаюсь дать понятное введение в коды Рида-Соломона, а в следующих выпусках напишу, как все это запрограммировать.

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

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

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

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

Вычеркнем из порождающей матрицы строки, соответствующие «пропавшим» данным. В нашем случае соответствует первой строке, а – второй. Полученную матрицу умножим на вектор с данными, и в результате получим следующее уравнение:

Проблема лишь в том, что и мы потеряли, и они нам теперь неизвестны. Как мы можем их найти? Есть очень элегантное решение этой проблемы.

Вычеркнем соответствующие строки из порождающей матрицы и найдём обратную к ней. На рисунке эта обратная матрица обозначена как . Теперь домножим левую и правую части исходного уравнения на эту обратную матрицу:

Сокращая матрицы в левой части уравнения (произведение обратной и прямой матриц есть единичная матрица), и учитывая тот факт, что в правой части уравнения нет неизвестных параметров, получаем выражения для искомых и .

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

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

Вернемся к вопросу о построении порождающей матрицы. Можем ли мы выбрать числа произвольным образом? Ответ – нет. Выбирать их нужно таким образом, чтобы вне зависимости от вычеркиваемых строк, матрица оставалась обратимой. К счастью, в математике давно известны типы матриц, обладающие нужным нам свойством. Например, матрица Коши . В этом случае сам метод кодирования часто называют методом Коши-Рида-Соломона (Cauchy-Reed-Solomon). Иногда, для этих же целей используют матрицу Вандермонда , и соответственно, метод носит название Вандермонда-Рида-Соломона (Vandermonde-Reed-Solomon).

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

Поля Галуа

Итак, что такое поля Галуа? Начнём опять с поясняющих примеров. Мы все привыкли оперировать (складывать, вычитать, умножать, делить и прочее) с числами – натуральными, рациональными, вещественными. Однако, вместо привычных чисел, мы можем начать рассматривать произвольные множества объектов (конечные и/или бесконечные) и вводить на этих множествах операции, аналогичные сложению, вычитанию и т.д. Собственно говоря, математические структуры типа групп, колец, полей - это множества, на которых введены определенные операции, причем, результаты этих операций снова принадлежат исходному множеству. Например, на множестве натуральных чисел, мы можем ввести стандартные операции сложения, вычитания и умножения. Результатом опять будет натуральное число. А вот с делением все хуже, при делении двух натуральных чисел результат может быть дробным числом.

Поле – это множество, на котором заданы операции сложения, вычитания, умножения и деления. Пример - поле рациональных чисел (дробей). Поле Галуа - конечное поле (множество, содержащее конечное количество элементов). Обычно поля Галуа обозначаются как , где - количество элементов в поле. Разработаны методы построения полей необходимой размерности (если это возможно). Конечным результатом подобных построений обычно являются таблицы сложения и умножения, которые двум элементам поля ставят в соответствие третий элемент поля.

Может возникнуть вопрос – как мы всё это будем использовать? При реализации алгоритмов на ЭВМ удобно работать с байтами. Наш алгоритм может принимать на входе байт исходных данных и вычислять по ним байт избыточных. В одном байте может содержаться 256 различных значений, поэтому, мы можем создать поле и рассчитывать избыточные байт, пользуясь арифметикой полей Галуа. Сам подход к кодированию/декодированию данных (построение порождающей матрицы, обращение матрицы, умножение матрицы на столбец) остаётся таким же, как и прежде.

Хорошо, мы в итоге научились по исходным байтам конструировать дополнительные байт, которые можно использовать при сбоях. Как это всё работает в реальных системах хранения? В реальных СХД обычно работают с блоками данных фиксированного размера (в разных системах этот размер варьируется от десятков мегабайт до гигабайтов). Этот фиксированный блок разбивается на фрагментов и по ним конструируются дополнительные фрагментов.

Процесс конструирования фрагментов происходит следующим образом. Берут по одному байту из каждого из исходных фрагментов по смещению 0. По этим данным генерируется K дополнительных байтов, каждый из который идет в соответствующие дополнительные фрагменты по смещению 0. Этот процесс повторяется для смещения – 1, 2, 3,… После того, как процедура кодирования закончена, фрагменты сохраняются на разные диски. Это можно изобразить следующим образом:

При выходе из строя одного или нескольких дисков, соответствующие потерянные фрагменты реконструируются и сохраняются на других дисках.

Теоретическая часть постепенно подходит к концу, будем надеяться, что базовый принцип кодирования и декодирования данных с использованием кодов Рида-Соломона теперь более или менее понятен. Если будет интерес к данной теме, то в следующих частях можно будет более подробно остановится на арифметике полей Галуа, реализациях алгоритма кодирования/декодирования на конкретных аппаратных платформах, поговорить про техники оптимизации.

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

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

Чтобы получить более детальное представление о кодах Рида-Соломона посмотрим, какое место они занимают в классификации корректирующих кодов (рис. 4.4).

Корректирующие коды разделяются на блочные и сверточные (непрерыв­ные). Блочные коды основаны на перекодировании исходной кодовой комбина­ции (блока), содержащейk информационных символов, в передаваемую кодо­вую комбинацию, содержащуюn >k символов. Дополнительныер = n – k сим­волов зависят только отk символов исходной кодовой комбинации. Следова­тельно, кодирование и декодирование осуществляются всегда в пределах од­ной кодовой комбинации (блока). В противоположность этому всверточных кодах кодирование и декодирование осуществляются непрерывно над после­довательностью двоичных символов.

Блочные коды бывают разделимые и неразделимые. В разделимых кодах можно в каждой кодовой комбинации указать, какие символы являются инфор­мационными, а какие проверочными. Внеразделимых кодах такая возмож­ность отсутствует.

Следующая ступень классификации – систематические коды . Они отлича­ются тем, что в них проверочные символы формируются из информационных символов по определенным правилам, выражаемым математическими соотно­шениями. Например, каждый проверочный символх pj получается как линейная комбинация информационных символов

Рис. 4.4. Место кодов Рида-Соломона в классификации корректирующих кодов

где
– коэффициенты, принимающие значения 0 или 1;
. Соотношение для формирования контрольного бита проверки на четность является частным случаем.

Перейдем к более подробному знакомству с циклическими кодами .

В первую очередь введем запись кодовой комбинации или, как часто назы­вают ее в литературе, кодового вектора в виде полинома. Пусть имеется кодо­вая комбинация a 0 a 1 a 2 ...a n –1 , гдеа 0 – младший разряд кода,a n –1 – старший раз­ряд кода. Соответствующий ей полином имеет вид

,

где х – формальная переменная, вводимая только для получения записи кодо­вой комбинации в виде полинома.

Над полиномами, представляющими кодовые комбинации, определена ма­тематическая операция умножения. Особенность этой операции по сравнению с общепринятой заключается в том, что коэффициенты при х всех степеней суммируются по модулю 2, а показатели степених при перемножении сумми­руются по модулюn , поэтомух n = 1.

Далее введем понятие производящего полинома . Производящим полино­мом порядка (n – k ) может быть полином со старшей степенью х , равной (n – k ), на который без остатка делится двучлен (1 + х n ). Разрешенные кодовые комби­нации получаются перемножением полиномов порядка k – 1, выражающих исходные кодовые комбинации, на производящий полином.

Циклические коды имеют следующее основное свойство. Если кодовая ком­бинация a 0 a 1 a 2 ...a n –1 является разрешенной, то получаемая из нее путем цик­лического сдвига кодовая комбинацияa n –1 a 0 a 1 ...a n –2 также является разрешен­ной в данном коде. При записи в виде полиномов операция циклического сдви­га кодового слова сводится к умножению соответствующего полинома нах с учетом приведенных ранее правил выполнения операции умножения.

Циклический код с производящим полиномом
строится следующим об­разом.

1. Берутся полиномы
,
,
, ...,
.

2. Кодовые комбинации, соответствующие этим полиномам, записывают в виде строк матрицы G , называемойпроизводящей матрицей .

3. Формируется набор разрешенных кодовых комбинаций кода. В него вхо­дит нулевая кодовая комбинация, k кодовых комбинаций, указанных в п. 1, а также суммы их всевозможных сочетаний. Суммирование осуществляется по­разрядно, причем каждый разряд суммируется по модулю 2 . Общее число полученных таким образом разрешенных кодовых комбинаций равно 2 k , что соответствует числу информационных разрядов кода.

Для построения декодера в первую очередь получают производящий поли­ном
порядкаk для построенияисправляющей матрицы Н :

.

Строками исправляющей матрицы Н будут кодовые комбинации, определяемые полиномами
,
, ...,
, где
– это записанный в об­ратном порядке полином
. Исправляющая матрица имеетn столбцов иn – k строк.

При декодировании принятая кодовая комбинация a 0 a 1 a 2 ...a n –1 скалярно умножается на каждую строку исправляющей матрицы. Эта операция может быть записана в виде соотношения:

где h ji – элементыj -той строки матрицыН . Полученныеn – k чиселc j образуютисправляющий вектор илисиндром . Если ошибок нет, то всеc j = 0. Если же при передаче данной кодовой комбинации возникла ошибка, то некоторые из чиселc j не равны 0. По тому, какие именно элементы исправляющего вектора отличны от нуля, можно сделать вывод о том, в каких разрядах принятой кодо­вой комбинации есть ошибка и, следовательно, исправить эти ошибки.

Рассмотрим пример, часто встречающийся в литературе. Построим цикли­ческий код с n = 7;k = 4. Для этого представим двучлен 1 +х 7 в виде произве­дения :

В обычной алгебре это равенство, конечно, не выполняется, но если ис­пользовать для приведения подобных вместо обычного сложения операцию суммирования по модулю 2, а при сложении показателей степеней – операцию суммирования по модулю 7, то равенство окажется справедливым.

В качестве производящего многочлена возьмем 1 + х +х 3 . Умножаем его нах ,х 2 их 3 и получаем многочленых +х 2 +х 4 ;х 2 +х 3 +х 5 ;х 3 +х 4 +х 6 . Затем запи­сываем производящую матрицуG , причем в каждой строке матрицы младший разряд кодовой комбинации расположен первым слева.

.

Далее формируем набор из 15 допустимых кодовых комбинаций: 00000000, 1101000, 0110100, 0011010, 0001101, 1011100, 0101110, 0010111, 1000110, 0100011, 1111111, 1010001, 1000110, 0100011, 1001011. В этих записях млад­шие биты слева, а старшие – справа.

Перемножив первые два сомножителя в, получаем производящий мно­гочлен для исправляющей матрицы: 1 + х +х +х 4 . Затем умножаем его нах их 2 и получаем еще две строки этой матрицы, которая в результате имеет такой вид (в отличие от матрицыG здесь младшие разряды соответствующих поли­номов расположены справа):

.

Пусть принята кодовая комбинация 0001101, входящая в набор допустимых. Найдем скалярные произведения этой кодовой комбинации со всеми строками матрицы Н :

Пусть теперь принята кодовая комбинация 0001100, в которой последний (старший) бит содержит ошибку. Скалярные произведения принятой кодовой комбинации на строки исправляющей матрицы имеют вид:

Таким образом, получен синдром (1, 0, 0). Если ошибка оказывается в другом бите кодовой комбинации, то получается другой синдром.

Одним из важных достоинств циклических кодов является возможность построения кодирующих и декодирующих устройств в виде сдвиговых регистров с обратными связями через сумматоры по модулю 2.

Различные виды циклических кодов получаются с помощью различных про­изводящих полиномов. Существует развитая математическая теория этого во­проса . Среди большого количества циклических кодов к числу наиболее эффективных и широко используемых относятся коды Бозе-Чоудхури-Хоквингема (ВСН-коды – по первым буквам фамилий Bose,Chaudhuri,Hockwinhamили в русскоязычной записи БЧХ-коды), являющиесяобобщением кодов Хемминга на случай направления нескольких ошибок. Они образуют наилучший среди известных класснеслучайных кодов для каналов, в которых ошибки в последовательных символах возникают независимо. Например, БЧХ-код (63, 44), используемый в системе спутникового цифрового радиовещания, по­зволяет исправить 2 или 3 ошибки, обнаружить 4 или 5 ошибок на каждый блок из 63 символов. Относительная скорость такого кода равнаR = 44/63 = 0,698.

Одним из видов ВСН-кодов являются коды Рида-Соломона. Эти коды отно­сятся к недвоичным кодам , так как символами в них могут быть многоразряд­ные двоичные числа, например, целые байты. В Европейском стандарте циф­рового телевидения DVB используется код Рида-Соломона, записываемый как (204, 188, 8), где 188 – количество информационных байт в пакете транс­портного потока MPEG-2, 204 – количество байт в пакете после добавления проверочных символов, 8 – минимальное кодовое расстояние между допусти­мыми кодовыми комбинациями. Таким образом, в качестве кодовых комбина­ций берутся целые пакеты транспортного потока, содержащие 1888 = 1504 информационных бита, а добавляемые проверочные символы содержат 168 = 128 бит. Относительная скорость такого кода равна 0,92. Этот код Рида-Соломона позволяет эффективно исправлять до 8 принятых с ошибками байт в каждом транспортном пакете.

Отметим также, что используемый в цифровом телевизионном вещании код Рида-Соломона часто называют укороченным . Смысл этого термина состоит в следующем. Из теории кодов Рида-Соломона следует, что если символом кода является байт, то полная длина кодового слова должна составлять 255 байт (239 информационных и 16 проверочных). Однако, пакет транспортного потокаMPEG-2 содержит 188 байт. Чтобы согласовать размер пакета с параметра­ми кода, перед кодированием в начало каждого транспортного пакета добав­ляют 51 нулевой информационный байт, а после кодирования эти дополни­тельные нулевые байты отбрасывают.

В приемнике для каждого принятого транспортного пакета, содержащего 204 байта, вычисляются синдромы и находятся два полинома: «локатор», корни ко­торого показывают положение ошибок, и «корректор» (evaluator), дающий зна­чение ошибок. Ошибки корректируются, если это возможно. Если же коррекция невозможна (например, ошибочных байт более 8) данные в пакете не изме­няются, а сам пакет помечается путем установки флага (первый бит после синхробайта), как содержащий неустранимые ошибки. В обоих случаях 16 избы­точных байт удаляются, и после декодирования длина транспортного пакета становится равной 188 байт.