Как стать автором
Обновить

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

История IT
Перевод
Перевод статьи Barry A. Cipra «The Ubiquitous Reed-Solomon Codes» из журнала «SIAM news», подшивка 26-1, январь 1993 года.
*****

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

Однако, многие люди, использующие современные технологии, могут и не догадываться о важности пятистраничной статьи, появившейся в 1960 году в журнале Общества промышленной и прикладной математики. В этой статье
Читать дальше →
Всего голосов 42: ↑37 и ↓5 +32
Просмотры 15K
Комментарии 22

Коды Рида-Соломона. Простой пример

Алгоритмы *
Из песочницы
Гауссово котэБлагодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин, либо передать информацию в условиях связи с большим количеством помех. В среднем для компакт-диска избыточность кода (т.е. количество дополнительных символов, благодаря которым информацию можно восстанавливать) составляет примерно 25%. Восстановить при этом можно количество данных, равное половине избыточных. Если емкость диска 700 Мб, то, получается, теоретически можно восстановить до 87,5 Мб из 700. При этом нам не обязательно знать, какой именно символ передан с ошибкой. Также стоит отметить, что вместе с кодированием используется перемежевание, когда байты разных блоков перемешиваются в определенном порядке, что в результате позволяет читать диски с обширными повреждениями, локализированными близко друг к другу (например, глубокие царапины), так как после операции, обратной перемежеванию, обширное повреждение оборачивается единичными ошибками во множестве блоков кода, которые поддаются восстановлению.

Давайте возьмем простой пример и попробуем пройти весь путь – от кодирования до получения исходных данных на приемнике. Пусть нам нужно передать кодовое слово С, состоящее из двух чисел – 3 и 1 именно в такой последовательности, т.е. нам нужно передать вектор С=(3,1). Допустим, мы хотим исправить максимум две ошибки, не зная точно, где они могут появиться. Для этого нужно взять 2*2=4 избыточных символа. Запишем их нулями в нашем слове, т.е. С теперь равно (3,1,0,0,0,0). Далее необходимо немного разобраться с математическими особенностями.

Поля Галуа


Многие знают романтическую историю о молодом человеке, который прожил всего 20 лет и однажды ночью написал свою математическую теорию, а утром был убит на дуэли. Это Эварист Галуа. Также он несколько раз пытался поступить в университеты, однако экзаменаторы не понимали его решений, и он проваливал экзамены. Приходилось ему учиться самостоятельно. Ни Гаусс, ни Пуассон, которым он послал свои работы, также не поняли их, однако его теория отлично пригодилась в 60-х годах ХХ-го века, и активно используется в наше время как для теоретических вычислений в новых разделах математики, так и на практике.
Читать дальше →
Всего голосов 94: ↑90 и ↓4 +86
Просмотры 115K
Комментарии 32

Арифметика полей Галуа для кодирования информации кодами Рида-Соломона

Алгоритмы *

Коды Рида-Соломона относятся к недвоичным, блочным, помехоустойчивым кодам и могут использоваться в области хранения информации для избегания потери поврежденной информации.
Читать дальше →
Всего голосов 49: ↑46 и ↓3 +43
Просмотры 109K
Комментарии 15

ECMA-130 (Compact Disc) на пальцах

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

Странная вещь — любопытство. Вот на столе экземпляр CD — безнадёжно устаревшего в наш просвященный XXI век формата хранения данных; а все таки интересно, как же там хранятся данные?.. Каков сам стек хранения данных?.. Как исправляются ошибки?.. Какова избыточность кода?..

В детстве мне было достаточно знаний о лазерном луче, о какой-то головке, об «этой крутящийся штуки» и о таинственных питах.

Сказано — сделано. Проглядев стандарт ECMA-130 (есть, кстати и отечественный стандарт: ГОСТ 27667-88) обнаружил массу любопытных деталей. Например, я догадывался об избыточности, но я и подумать не мог, что для записи 700 Мб данных «в реальности» записывается 1943 Мб (То есть в 2.776 раз больше)…

Схематично весь стек можно представить картинкой:


Дальше читать
Всего голосов 22: ↑21 и ↓1 +20
Просмотры 13K
Комментарии 9

Как применение кодов избыточности в SDS помогает Яндексу дёшево и надёжно хранить данные

Блог компании Яндекс Облачные вычисления *Восстановление данных *Хранение данных *Хранилища данных *

Яндекс, как и любая другая большая интернет-компания, хранит много, а точнее очень много данных. Это и пользовательские данные из разных сервисов, и намайненные сайты, и промежуточные данные для расчёта погоды, и резервные копии баз данных. Стоимость хранения ($/ГБ) — один из важных показателей системы. В этой статье я хочу рассказать вам про один из методов, который позволил нам серьезно удешевить хранилище.




В 2015 году, как вы все помните, сильно вырос курс доллара. Точнее, расти-то он начал в конце 2014-го, но новые партии железа мы заказывали уже в 2015-м. Яндекс зарабатывает в рублях, и поэтому вместе с курсом выросла и стоимость железа для нас. Это заставило нас в очередной раз подумать о том, как сделать, чтобы в текущий кластер можно было положить больше данных. Мы такое, конечно, делаем регулярно, но в этот раз мотивация была особенно сильной.


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


Читать дальше →
Всего голосов 74: ↑71 и ↓3 +68
Просмотры 21K
Комментарии 19

Коды Рида-Соломона. Часть 1 — теория простым языком

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



Читать дальше →
Всего голосов 50: ↑50 и ↓0 +50
Просмотры 47K
Комментарии 31

Коды Рида-Соломона. Часть 2 — арифметика полей Галуа

Блог компании YADRO Алгоритмы *
Здравствуйте, друзья! В прошлый раз мы с вами начали говорить о том, как коды Рида-Соломона помогают обеспечивать необходимый уровень надежности хранения данных. Сегодня остановимся немного подробнее на арифметике полей Галуа, которая используется в расчётах.



Читать дальше →
Всего голосов 28: ↑27 и ↓1 +26
Просмотры 19K
Комментарии 5

Коды избыточности: простыми словами о том, как надёжно и дёшево хранить данные

Блог компании Яндекс Хранение данных *Хранилища данных *Распределённые системы *


Так выглядит избыточность


Коды избыточности* широко применяются в компьютерных системах для увеличения надёжности хранения данных. В Яндексе их используют в очень многих проектах. Например, применение кодов избыточности вместо репликации в нашем внутреннем объектном хранилище экономит миллионы без снижения надёжности. Но несмотря на широкое распространение, понятное описание того, как работают коды избыточности, встречается очень редко. Желающие разобраться сталкиваются примерно со следующим (из Википедии):



Меня зовут Вадим, в Яндексе я занимаюсь разработкой внутреннего объектного хранилища MDS. В этой статье я простыми словами опишу теоретические основы кодов избыточности (кодов Рида — Соломона и LRC). Расскажу, как это работает, без сложной математики и редких терминов. В конце приведу примеры использования кодов избыточности в Яндексе.


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


* Под термином «коды избыточности» в статье подразумевается инженерный термин «erasure codes».

Читать дальше →
Всего голосов 62: ↑58 и ↓4 +54
Просмотры 21K
Комментарии 32

QR-художество

Ненормальное программирование *JavaScript *Графический дизайн *

На хабре уже обсуждалось устройство QR-кодов и украшение их произвольными рисунками, но дизайнерская мысль до сих пор работала только в двух основных направлениях: замена квадратных модулей на более интересные формы, либо замена части кода рисунком. Такие художества возможны благодаря тому, что блоки данных в QR-коде дополняются кодами Рида-Соломона, позволяющими восстановить до 30% искажённых байтов. Основываясь на этом, дизайнеры QR-кодов давно уже наловчились заменять участок, занимающий до 30% площади кода, какой-нибудь картинкой. Я же решил испробовать другой подход — художественно искажать в QR-коде отдельные биты в целях получения интересного изображения. Например, в этом коде инвертированы лишь 50 модулей из 841.

Читать далее
Всего голосов 42: ↑42 и ↓0 +42
Просмотры 12K
Комментарии 11

Программная реализация умножения в полях Галуа

Занимательные задачки Алгоритмы *Разработка систем связи *
Из песочницы

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


Итак, я отвлёкся. В детстве-юношестве для помехоустойчивого кодирования можно было бы применить контроль чётности по матричному методу, но сейчас это не серьёзно. Полистав интернет я решил остановиться на кодировании по методу Рида-Соломона. Алгоритм не то, чтобы совсем новый, его ещё в первых CD применяли, но при этом, насколько мне известно, не потерявший своей актуальности и на данный момент. В этой статье о самих кодах Рида-Соломона я не буду сильно распространяться – это за меня на Хабре сделали много раз и много кто. Здесь я хочу описать реализацию алгоритма умножения в GF[256]. Тем не менее, чтобы не заставлять читателя прыгать по ссылкам, кратенько опишу зачем вообще приходится иметь дело с полями Галуа.

Читать дальше →
Всего голосов 19: ↑17 и ↓2 +15
Просмотры 10K
Комментарии 43

Арифметика с полиномами для кода Рида-Соломона

Занимательные задачки Алгоритмы *Разработка систем связи *

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

Читать дальше →
Всего голосов 17: ↑17 и ↓0 +17
Просмотры 6.8K
Комментарии 20

Кодирование Рида-Соломона для чайников

Занимательные задачки Алгоритмы *Разработка систем связи *

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

этой статьи
Всего голосов 16: ↑16 и ↓0 +16
Просмотры 11K
Комментарии 5