В каких целях спускаемые отсеки. Спускаемые аппараты. Исследования при жесткой посадке

Код Рида - Соломона был изобретён в 1960 году сотрудниками лаборатории Линкольна Ирвином Ридом (англ.) и Густавом Соломоном (англ.). Идея использования этого кода была представлена в статье «Polynomial Codes over Certain Finite Fields». Первое применение код Рида - Соломона получил в 1982 году в серийном выпуске компакт-дисков. Эффективный алгоритм декодирования был предложен в 1969 году Элвином Берлекэмпом (англ.) и Джэймсом Месси (алгоритм Берлекэмпа - Мэсси).

Формальное описание

Коды Рида - Соломона являются важным частным случаем БЧХ-кода , корни порождающего полинома которого лежат в том же поле , над каким и строится код (m = 1 ). Пусть α - элемент поля порядка . Если α - примитивный элемент, то его порядок равен q − 1 , то есть . Тогда нормированный полином g (x ) минимальной степени над полем , корнями которого являются d − 1 подряд идущих степеней элемента α , является порождающим полиномом кода Рида - Соломона над полем :

где l 0 - некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается l 0 = 1 . Степень многочлена равна d − 1 .

Длина полученного кода n , минимальное расстояние d (минимальное расстояние d линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов, см. Линейный код). Код содержит r = d − 1 = deg(g (x )) проверочных символов, где deg() обозначает степень полинома; число информационных символов k = n − r = n − d + 1 . Таким образом и код Рида - Соломона является разделимым кодом с максимальным расстоянием (является оптимальным в смысле границы Синглтона).

Кодовый полином c (x ) может быть получен из информационного полинома m (x ) , , путем перемножения m (x ) и g (x ) :

c (x ) = m (x )g (x )

Свойства

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

Теорема (граница Рейгера) . Каждый линейный блоковый код, исправляющий все пакеты длиной t и менее, должен содержать, по меньшей мере, 2t проверочных символов.

Исправление многократных ошибок

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

(q m − 1,q m − 1 − 2t ) -код Рида - Соломона над полем с кодовым расстоянием d = 2t + 1 можно рассматривать как ((q m − 1)m ,(q m − 1 − 2t )m ) -код над полем , который может исправлять любую комбинацию ошибок, сосредоточенную в t или меньшем числе блоков из m символов. Наибольшее число блоков длины m , которые может затронуть пакет длины l i , где , не превосходит t i , поэтому код, который может исправить t блоков ошибок, всегда может исправить и любую комбинацию из p пакетов общей длины l , если .

Практическая реализация

Кодирование с помощью кода Рида - Соломона может быть реализовано двумя способами: систематическим и несистематическим (см. , описание кодировщика).

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

При систематическом кодировании к информационному блоку из k символов приписываются 2t проверочных символов, при вычислении каждого проверочного символа используются все k символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить k (n − k ) операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка O (l n (n 2)) .

Кодирование

При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова S длины k на неприводимый полином при систематическом кодировании можно выполнить следующим образом:

Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.

Декодирование

Вычисляет синдром ошибки
Строит полином ошибки
Находит корни данного полинома
Определяет характер ошибки
Исправляет ошибки

Вычисление синдрома ошибки

Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.

Построение полинома ошибки

Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна 2t , что много меньше степени кодового слова n . Для получения соответствия между ошибкой и ее положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа - Месси , либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа - Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.

Нахождение корней

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

Определение характера ошибки и ее исправление

По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Эта маска накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.

Применение

В настоящий момент коды Рида - Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.

Запись и хранение информации

Код Рида - Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида - Соломона позволяют восстановить большую часть потерянной информации. Также используется при записи на такие носители, как магнитные ленты и штрихкоды.

Запись на CD-ROM

Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Так же ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25 % от исходной информации.

При записи на цифровые аудиокомпакт-диски (Compact Disc Digital Audio - CD-DA) используется стандарт Red Book . Коррекция ошибок происходит на двух уровнях C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа соответственно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символов является фатальной ошибкой и не может быть исправлено.

Беспроводная и мобильная связь

Этот алгоритм кодирования используется при передаче данных по сетям WiMAX , в оптических линиях связи , в спутниковой и радиорелейной связи . Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида - Соломона.

Примеры кодов

16-ричный (15,11) код Рида - Соломона

Пусть t = 2,l 0 = 1 . Тогда

g (x ) = (x − α)(x − α 2)(x − α 3)(x − α 4) = x 4 + α 13 x 3 + α 6 x 2 + α 3 x + α 10

Степень g (x ) равна 4, n − k = 4 и k = 11 . Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16) , что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.

8-ричный (7,3) код Рида - Соломона

Пусть t = 2,l 0 = 4 . Тогда

g (x ) = (x − α 4)(x − α 5)(x − α 6)(x − α 0) = x 4 + α 6 x 3 + α 6 x 2 + α 3 x + α

Пусть информационный многочлен имеет вид

m (x ) = α 4 x 2 + x + α 3

Кодовое слово несистематического кода запишется в виде

c (x ) = m (x )g (x ) = (α 4 x 2 + x + α 3)(x 4 + α 6 x 3 + α 6 x 2 + α 3 x + α) = α 4 x 6 + αx 5 + α 6 x 4 + 0x 3 + 0x 2 + α 5 x + α 4

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

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

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

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

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

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

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

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

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

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

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

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

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

Поля Галуа

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

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

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

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

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

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

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

УПК-8, Краснокамск

Викторина

1. Почему конструкторы предлагают покрывать спускаемые отсеки космического корабля слоем легкоплавкого материала?

Это делается для обеспечения безопасности, чтобы отсек не перегрелся. Действует так называемая абляционная защита (от англ. ablation - абляция; унос массы) - технология защиты космических кораблей.

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

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

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

Альтернативой абляционной теплозащите является использование термостойких теплозащитных плиток («Шаттл», «Буран»).

2.Можно ли пользоваться на космической станции маятниковыми часами?

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

Первые часы, совершившие полёт в космос, принадлежали Юрию Алексеевичу Гагарину. Это были советские «Штурманские». С 1994 года официальными часами Центра подготовки космонавтов стали швейцарские часы Fortis. В начале 2000 годов на МКС испытывали орбитальные часы «Космонавигатор», разработанные летчиком-космонавтом Владимиром Джанибековым. Этот прибор позволял в любой момент времени определить, над какой точкой Земли находятся корабль. Первые специальные часы для использования в открытом космосе - японские Spring Drive Spacewalk. Электронные часы на орбите не прижились. Космический корабль пронизывают частицы высокой энергии, которые выводят из строя незащищенные микросхемы

3 Можно ли в невесомости пить воду из стакана?

До первых полетов в космос ученым было во многом загадкой, как организовать в состоянии невесомости прием пищи. Было известно, что жидкость или соберется в шар, или растечется по стенкам, смачивая их. Значит, пить воду из стакана невозможно. Предлагалось космонавту высасывать её из сосуда.

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

Мы видели на сайте http://www. /watch? v=OkUIgVzanPM как американские астронавты пьют кофе. Но стакан там тоже пластиковый, его форму можно изменить. Можно выдавливать из него жидкость. Значит, воду их обычного твердого стеклянного стакана пить практически невозможно.

Сегодня у каждого члена экипажа Международной космической станции (МКС) для питья есть индивидуальный мундштук, который насаживается на шприцы разветвлённой бортовой системы водоснабжения «Родник» . Вода в системе «Родник» не простая, а посеребрённая. Её пропускают через особые серебряные фильтры , что предохраняет экипаж от возможности разнообразных инфекций.

Но возможно, в ближайшем будущем космонавты легко смогут пить воду из обычного стакана. Планируются широкомасштабные исследования поведения жидкостей и газов в невесомости на независимой от МКС платформе. Сейчас идут проектные работы, в которых участвуют преподаватели и студенты кафедры общей физики Пермского университета. Исследования в этом направлении ведутся в Перми более 30 лет.

4.Кто из космонавтов первым побывал в открытом космосе?

Первым вышел в открытый космос советский космонавт Алексей Архипович Леонов 18 марта 1965 года с борта космического корабля «Восход-2» с использованием гибкой шлюзовой камеры. Через 1 час 35 минут после старта (в начале 2-го витка) Алексей Леонов первым в мире покинул космический корабль, о чем на весь мир объявил командир корабля Павел Беляев: "Внимание! Человек вышел в космическое пространство! Человек вышел в космическое пространство!" Телевизионное изображение парящего на фоне транслировалось по всем телеканалам. В это время он удалялся от корабля на расстояние до 5.35 м. Его скафандр расходовал около 30 литров кислорода в минуту при общем запасе в 1666 литров, рассчитанном на 30 минут работы в открытом космосе. Возвращаться на корабль ему было очень трудно. Об этом он говорит в интервью со страниц журнала «Генеральный директор» (№3, 2013 г.): «Из-за деформации скафандра (он раздулся) фаланги пальцев вышли из перчаток, поэтому сматывать фал было очень трудно. Кроме того, войти в шлюз корабля ногами вперед, как положено, стало невозможно. …Паниковать было некогда: до захода в тень оставалось всего пять минут, а в тени смотать фал невозможно. …Я все время думал о том, что случится через пять минут, а что – через тридцать. И действовал исходя из этих соображений».

Общее время первого выхода составило 23 минуты 41 секунду (из них вне корабля 12 минут 9 секунд). Он провел медико-биологические исследования, помог в решении задач космической навигации. По итогам выхода был сделан вывод о возможности работать в открытом космосе.

Из-за внештатной ситуации корабль приземлился в Пермском крае, у деревни Кургановка, на границе Усольского и Соликамского районов 19 марта 1965 г. Их не сразу нашли в глухой уральской тайге. В память об этом событии в Перми появились улицы Беляева, Леонова, шоссе Космонавтов. Через три года космонавты снова побывали здесь. На месте приземления была установлена стела. Алексей Леонов не раз был гостем Перми.

Космонавты стали почетными гражданами Перми. А вообще среди почетных граждан Перми более трети связаны с космической отраслью. Ведь дорога в космос начинается у нас. В марте 1958 г. правительство СССР приняло решение о развертывании производства ракет и ракетных двигателей на пермских предприятиях. 19 крупнейших заводов и конструкторских бюро работали на космос. Ракеты, оснащенные пермскими двигателями, вывели в космос сотни космических аппаратов. Сегодня в Перми действуют три предприятия, на которых собирают отдельные узлы или целые двигатели космических ракет. «Протон-ПМ» производит жидкостные двигатели к ракетам-носителям «Протон». НПО «Искра» выпускает ракетные двигатели на твердом топливе, а Пермский завод «Машиностроитель» занимается изготовлением различных механизмов ракет.

Пермские вузы выпускают специалистов для аэрокосмической отрасли, а ещё проводят исследовательские программы по космической тематике.

В 2013 году коллектив учёных кафедры общей физики физического факультета Пермского Государственного научно-исследовательского университета снова приглашён к участию в реализации Федеральной космической программы России. Вместе со специалистами Ракетно-космической корпорации «Энергия» физики Пермского госуниверситета разработают научную аппаратуру и программу прикладных исследований для новейшего космического аппарата «ОКА-Т».